Re: [RFC PATCH v4 2/7] libbpf: Add BTF permutation support for type reordering

[Eduard Zingerman <eddyz87@gmail.com>]

On Wed, 2025-11-05 at 10:23 -0800, Andrii Nakryiko wrote:
> On Tue, Nov 4, 2025 at 5:20 PM Eduard Zingerman <eddyz87@gmail.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@gmail.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.

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.