Message-ID: <CAEf4Bzb-mYfsBNi4NKSSiu6QQU3+5cs=uCn-8suOcFOuc-tG2w@mail.gmail.com>
Date: Thu, 6 Nov 2025 09:21:25 -0800
From: Andrii Nakryiko <andrii.nakryiko@...il.com>
To: Eduard Zingerman <eddyz87@...il.com>
Cc: Donglin Peng <dolinux.peng@...il.com>, ast@...nel.org, linux-kernel@...r.kernel.org, 
	bpf@...r.kernel.org, Alan Maguire <alan.maguire@...cle.com>, Song Liu <song@...nel.org>, 
	pengdonglin <pengdonglin@...omi.com>
Subject: Re: [RFC PATCH v4 2/7] libbpf: Add BTF permutation support for type reordering

On Wed, Nov 5, 2025 at 11:23 AM Eduard Zingerman <eddyz87@...il.com> wrote:
>
> On Wed, 2025-11-05 at 10:23 -0800, Andrii Nakryiko wrote:
> > On Tue, Nov 4, 2025 at 5:20 PM Eduard Zingerman <eddyz87@...il.com> wrote:
> > >
> > > On Tue, 2025-11-04 at 17:04 -0800, Andrii Nakryiko wrote:
> > > > On Tue, Nov 4, 2025 at 4:16 PM Eduard Zingerman <eddyz87@...il.com> wrote:
> > > > >
> > > > > On Tue, 2025-11-04 at 16:11 -0800, Andrii Nakryiko wrote:
> > > > >
> > > > > [...]
> > > > >
> > > > > > > +static int btf_permute_remap_type_id(__u32 *type_id, void *ctx)
> > > > > > > +{
> > > > > > > +       struct btf_permute *p = ctx;
> > > > > > > +       __u32 new_type_id = *type_id;
> > > > > > > +
> > > > > > > +       /* skip references that point into the base BTF */
> > > > > > > +       if (new_type_id < p->btf->start_id)
> > > > > > > +               return 0;
> > > > > > > +
> > > > > > > +       new_type_id = p->map[*type_id - p->btf->start_id];
> > > > > >
> > > > > > I'm actually confused, I thought p->ids would be the mapping from
> > > > > > original type ID (minus start_id, of course) to a new desired ID, but
> > > > > > it looks to be the other way? ids is a desired resulting *sequence* of
> > > > > > types identified by their original ID. I find it quite confusing. I
> > > > > > think about permutation as a mapping from original type ID to a new
> > > > > > type ID, am I confused?
> > > > >
> > > > > Yes, it is a desired sequence, not mapping.
> > > > > I guess its a bit simpler to use for sorting use-case, as you can just
> > > > > swap ids while sorting.
> > > >
> > > > The question is really what makes most sense as an interface. Because
> > > > for sorting cases it's just the matter of a two-line for() loop to
> > > > create ID mapping once types are sorted.
> > > >
> > > > I have slight preference for id_map approach because it is easy to
> > > > extend to the case of selectively dropping some types. We can just
> > > > define that such IDs should be mapped to zero. This will work as a
> > > > natural extension. With the desired end sequence of IDs, it's less
> > > > natural and will require more work to determine which IDs are missing
> > > > from the sequence.
> > > >
> > > > So unless there is some really good and strong reason, shall we go
> > > > with the ID mapping approach?
> > >
> > > If the interface is extended with types_cnt, as you suggest, deleting
> > > types is trivial with sequence interface as well. At-least the way it
> > > is implemented by this patch, you just copy elements from 'ids' one by
> > > one.
> >
> > But it is way less explicit and obvious way to delete element. With ID
> > map it is obvious, that type will be mapped to zero. With list of IDs,
> > you effectively search for elements that are missing, which IMO is way
> > less optimal an interface.
> >
> > So I still favor the ID map approach.
>
> You don't need to search for deleted elements with current
> implementation (assuming the ids_cnt parameter is added).
> Suppose there are 4 types + void in BTF and the 'ids' sequence looks
> as follows: {1, 3, 4}, current implementation will:
> - iterate over 'ids':
>   - copy 1 to new_types, remember to remap 1 to 1
>   - copy 3 to new_types, remember to remap 3 to 2
>   - copy 4 to new_types, remember to remap 4 to 3
> - do the remapping.

Eduard, from API perspective I very much do not like saying that "if
type ID is missing from the list -- drop it". I very much prefer "map
type you want to delete to zero". How can I be more clear about this?
I didn't even talk about implementation, I was talking about API.

>
> Consider the sorting use-case:
> - If 'ids' is the desired final order of types, libbpf needs to
>   allocate the mapping from old id to new id, as described above.
> - If 'ids' is a map from old id to new id:
>   - libbpf will have to allocate a temporary array to hold the desired
>     id sequence, to know in which order to copy the types;
>   - user will have to allocate the array for mapping.
>
> So, for id map approach it is one more allocation for no benefit.

On the libbpf side - no difference in terms of memory use. On the user
side, worst case, N * sizeof(int) temporary allocation for ID mapping.
400KB at most to resort 100K of BTF types, which takes megabytes
anyways. I don't even want to talk about the amount of memory pahole
will waste on DWARF information processing. And depending on what data
structures user code keeps for sorting indexing, this allocation might
be necessary anyways with either approach.

But this is all irrelevant. I care about the interface way more than
temporary 400KB of memory usage.

Powered by blists - more mailing lists