Subject: Re: [PATCH bpf-next v3 3/7] bpf: minimize number of allocated lsm slots per program

From: Jakub Sitnicki <[email-masked]>
Date: Sat, 09 Apr 2022 19:04:05 +0200

On Fri, Apr 08, 2022 at 03:56 PM -07, Martin KaFai Lau wrote:
> On Thu, Apr 07, 2022 at 03:31:08PM -0700, Stanislav Fomichev wrote:
>> Previous patch adds 1:1 mapping between all 211 LSM hooks
>> and bpf_cgroup program array. Instead of reserving a slot per
>> possible hook, reserve 10 slots per cgroup for lsm programs.
>> Those slots are dynamically allocated on demand and reclaimed.
>> This still adds some bloat to the cgroup and brings us back to
>> roughly pre-cgroup_bpf_attach_type times.
>> 
>> It should be possible to eventually extend this idea to all hooks if
>> the memory consumption is unacceptable and shrink overall effective
>> programs array.
>> 
>> Signed-off-by: Stanislav Fomichev <[email-masked]>
>> ---
>>  include/linux/bpf-cgroup-defs.h |  4 +-
>>  include/linux/bpf_lsm.h         |  6 ---
>>  kernel/bpf/bpf_lsm.c            |  9 ++--
>>  kernel/bpf/cgroup.c             | 96 ++++++++++++++++++++++++++++-----
>>  4 files changed, 90 insertions(+), 25 deletions(-)
>> 
>> diff --git a/include/linux/bpf-cgroup-defs.h b/include/linux/bpf-cgroup-defs.h
>> index 6c661b4df9fa..d42516e86b3a 100644
>> --- a/include/linux/bpf-cgroup-defs.h
>> +++ b/include/linux/bpf-cgroup-defs.h
>> @@ -10,7 +10,9 @@
>>  
>>  struct bpf_prog_array;
>>  
>> -#define CGROUP_LSM_NUM 211 /* will be addressed in the next patch */
>> +/* Maximum number of concurrently attachable per-cgroup LSM hooks.
>> + */
>> +#define CGROUP_LSM_NUM 10
> hmm...only 10 different lsm hooks (or 10 different attach_btf_ids) can
> have BPF_LSM_CGROUP programs attached.  This feels quite limited but having
> a static 211 (and potentially growing in the future) is not good either.
> I currently do not have a better idea also. :/
>
> Have you thought about other dynamic schemes or they would be too slow ?

As long as we're talking ideas - how about a 2-level lookup?

L1: 0..255 -> { 0..31, -1 }, where -1 is inactive cgroup_bp_attach_type
L2: 0..31 -> struct bpf_prog_array * for cgroup->bpf.effective[],
             struct hlist_head [^1]  for cgroup->bpf.progs[],
             u32                     for cgroup->bpf.flags[],

This way we could have 32 distinct _active_ attachment types for each
cgroup instance, to be shared among regular cgroup attach types and BPF
LSM attach types.

It is 9 extra slots in comparison to today, so if anyone has cgroups
that make use of all available attach types at the same time, we don't
break their setup.

The L1 lookup table would still a few slots for new cgroup [^2] or LSM
hooks:

  256 - 23 (cgroup attach types) - 211 (LSM hooks) = 22

Memory bloat:

 +256 B - L1 lookup table
 + 72 B - extra effective[] slots
 + 72 B - extra progs[] slots
 + 36 B - extra flags[] slots
 -184 B - savings from switching to hlist_head
 ------
 +252 B per cgroup instance

Total cgroup_bpf{} size change - 720 B -> 968 B.

WDYT?

[^1] It looks like we can easily switch from cgroup->bpf.progs[] from
     list_head to hlist_head and save some bytes!

     We only access the list tail in __cgroup_bpf_attach(). We can
     either iterate over the list and eat the cost there or push the new
     prog onto the front.

     I think we treat cgroup->bpf.progs[] everywhere like an unordered
     set. Except for __cgroup_bpf_query, where the user might notice the
     order change in the BPF_PROG_QUERY dump.

[^2] Unrelated, but we would like to propose a
     CGROUP_INET[46]_POST_CONNECT hook in the near future to make it
     easier to bind UDP sockets to 4-tuple without creating conflicts:

     https://github.com/cloudflare/cloudflare-blog/tree/master/2022-02-connectx/ebpf_connect4
 
[...]