Message-ID: <CAEf4BzayHtTppa8GLFViRQRBW-dkYQ6JyVvG7HY1DBy8j_-OBg@mail.gmail.com>
Date: Fri, 7 Nov 2025 09:43:53 -0800
From: Andrii Nakryiko <andrii.nakryiko@...il.com>
To: Donglin Peng <dolinux.peng@...il.com>
Cc: Eduard Zingerman <eddyz87@...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 Thu, Nov 6, 2025 at 6:36 PM Donglin Peng <dolinux.peng@...il.com> wrote:
>
> On Thu, Nov 6, 2025 at 2:23 AM Andrii Nakryiko
> <andrii.nakryiko@...il.com> 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.
>
> Hi Andrii,
>
> I've submitted v5 implementing the sequence-based approach, and I plan
> to introduce
> the ID map approach in v6. However, I have a few remaining questions that need
> clarification:
>
> 1. ID Map Array Semantics:
>
>    -  When the ID map array specifies `[2] = 4`, does this indicate
> that the original type
>       at `start_id + 2` should be remapped to position `start_id + 4`?

I'd say that 4 should be "absolute type ID" for simplicity. Because
that's what users work with. I'd say the position ([2]) should also
map to type ID for non-split case. So for base BTF I'd require [0]=0,
i.e., id_map count should be btf__type_cnt() sized. (I can be
convinced that's wrong and inconvenient) For split BTF the situation
is of course more complicated, because requiring btf__type_cnt()-sized
array for just split BTF would be super wasteful. So for split BTF [2]
would be as you say 3rd type within split BTF, that is type
#(btf__start_id() + 2), yes.

> Should the following
>       mapping attempts be rejected:
>       a) If the target index `4` exceeds the total number of types (`nr_types`)?

yes

>       b) If multiple source types map to the same target location
> (e.g., both `[1] = 3`
>           and `[2] = 3`)?

yes (at least for now, we can lift this if we ever have a good reason
by adding some option)

>
>    - If [3] = 0, does this indicate that the type at start_id + 3 should
>      be dropped?

yes, but let's not worry about deletion right now and just reject
this. I'd like to keep this option for the future, but right now we
should reject such case.

>
>    - Does this also imply that the VOID type (ID 0) cannot be remapped
>      and must always remain unchanged?

yes, it must be always be zero, it's baked into BTF

>
>
> 2. ID Map Array Size:
>
>    - Must the ID map array size  <=  the number of BTF types? If the array
>      is smaller, should any missing types be automatically dropped?

no, it's an error, id_map size should match the number of types. For
base it should be btf__type_cnt(), for split BTF it should be
`btf__type_cnt() - btf__type_cnt(btf__base_btf(split_btf))`. (That's
one of the reasons I think we should have [0] = 0 for base, to keep
this consistent).

Powered by blists - more mailing lists