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

[Martin KaFai Lau <kafai@fb.com>]

On Tue, Apr 12, 2022 at 09:42:41AM -0700, Stanislav Fomichev wrote:
> On Mon, Apr 11, 2022 at 6:19 PM Martin KaFai Lau <kafai@fb.com> wrote:
> >
> > On Sat, Apr 09, 2022 at 07:04:05PM +0200, Jakub Sitnicki wrote:
> > > >> 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
> > Does L1 need to be per cgroup ?
> >
> > or different cgroups usually have a very different active(/effective) set ?
> 
> I'm assuming the suggestion is to have it per cgroup. Otherwise, if it's
> global, it's close to whatever I'm proposing in the original patch. As I
> mentioned in the commit message, in theory, all cgroup_bpf can be managed
> the way I propose to manage 10 lsm slots if we get to the point where
> 10 slots is not enough.
Ah, indeed. The global one will be similar to the original patch.  I was
thinking only use the spaces saved from list_head->hlist_head to get a
larger progs[] instead of spending it on L1 lookup table.

Also, I think u8 should be enough for the flags[].

> I've played with this mode a bit and it looks a bit complicated :-( Since it's
> per cgroup, we have to be careful to preserve this mapping during
> cgroup_bpf_inherit.
> I'll see what I can do, but I'll most likely revert to my initial
> version for now (I'll also include list_head->hlist_head conversion
> patch, very nice idea).
sgtm.

> 
> 
> 
> > >  + 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
> > >
> > > [...]