Message-ID: <CAErzpmv8eBjuX-RO0nopuy8qMV7wzVxa2e+HteXfFodwbBoALg@mail.gmail.com>
Date: Wed, 5 Nov 2025 20:52:49 +0800
From: Donglin Peng <dolinux.peng@...il.com>
To: Andrii Nakryiko <andrii.nakryiko@...il.com>
Cc: ast@...nel.org, linux-kernel@...r.kernel.org, bpf@...r.kernel.org, 
	Eduard Zingerman <eddyz87@...il.com>, 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 8:11 AM Andrii Nakryiko
<andrii.nakryiko@...il.com> wrote:
>
> On Tue, Nov 4, 2025 at 5:40 AM Donglin Peng <dolinux.peng@...il.com> wrote:
> >
> > From: pengdonglin <pengdonglin@...omi.com>
> >
> > Introduce btf__permute() API to allow in-place rearrangement of BTF types.
> > This function reorganizes BTF type order according to a provided array of
> > type IDs, updating all type references to maintain consistency.
> >
> > The permutation process involves:
> > 1. Shuffling types into new order based on the provided ID mapping
> > 2. Remapping all type ID references to point to new locations
> > 3. Handling BTF extension data if provided via options
> >
> > This is particularly useful for optimizing type locality after BTF
> > deduplication or for meeting specific layout requirements in specialized
> > use cases.
> >
> > Cc: Eduard Zingerman <eddyz87@...il.com>
> > Cc: Alexei Starovoitov <ast@...nel.org>
> > Cc: Andrii Nakryiko <andrii.nakryiko@...il.com>
> > Cc: Alan Maguire <alan.maguire@...cle.com>
> > Cc: Song Liu <song@...nel.org>
> > Signed-off-by: pengdonglin <pengdonglin@...omi.com>
> > Signed-off-by: Donglin Peng <dolinux.peng@...il.com>
> > ---
> >  tools/lib/bpf/btf.c      | 161 +++++++++++++++++++++++++++++++++++++++
> >  tools/lib/bpf/btf.h      |  34 +++++++++
> >  tools/lib/bpf/libbpf.map |   1 +
> >  3 files changed, 196 insertions(+)
> >
> > diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c
> > index 5e1c09b5dce8..3bc03f7fe31f 100644
> > --- a/tools/lib/bpf/btf.c
> > +++ b/tools/lib/bpf/btf.c
> > @@ -5830,3 +5830,164 @@ int btf__relocate(struct btf *btf, const struct btf *base_btf)
> >                 btf->owns_base = false;
> >         return libbpf_err(err);
> >  }
> > +
> > +struct btf_permute {
> > +       /* .BTF section to be permuted in-place */
> > +       struct btf *btf;
> > +       struct btf_ext *btf_ext;
> > +       /* Array of type IDs used for permutation. The array length must equal
>
> /*
>  * Use this comment style
>  */

Thanks.

>
> > +        * the number of types in the BTF being permuted, excluding the special
> > +        * void type at ID 0. For split BTF, the length corresponds to the
> > +        * number of types added on top of the base BTF.
>
> many words, but what exactly ids[i] means is still not clear, actually...

Thanks. I'll clarify the description. Is the following parameter
explanation acceptable?

@param ids Array containing original type IDs (excluding VOID type ID
0) in user-defined order.
                    The array size must match btf->nr_types, which
also excludes VOID type ID 0.


>
> > +        */
> > +       __u32 *ids;
> > +       /* Array of type IDs used to map from original type ID to a new permuted
> > +        * type ID, its length equals to the above ids */
>
> wrong comment style

Thanks, I will fix it in the next version.

>
> > +       __u32 *map;
>
> "map" is a bit generic. What if we use s/ids/id_map/ and
> s/map/id_map_rev/ (for reverse)? I'd use "id_map" naming in the public
> API to make it clear that it's a mapping of IDs, not just some array
> of IDs.

Thank you for the suggestion. While I agree that renaming 'map' to 'id_map'
makes sense for clarity, but 'ids' seems correct as it denotes a collection of
IDs, not a mapping structure.

>
> > +};
> > +
> > +static int btf_permute_shuffle_types(struct btf_permute *p);
> > +static int btf_permute_remap_types(struct btf_permute *p);
> > +static int btf_permute_remap_type_id(__u32 *type_id, void *ctx);
> > +
> > +int btf__permute(struct btf *btf, __u32 *ids, const struct btf_permute_opts *opts)
>
> Let's require user to pass id_map_cnt in addition to id_map itself.
> It's easy to get this wrong (especially with that special VOID 0 type
> that has to be excluded, which I can't even make up my mind if that's
> a good idea or not), so having user explicitly say what they think is
> necessary for permutation is good.

Thank you for your suggestion. However, I am concerned that introducing
an additional `id_map_cnt` parameter could increase complexity. Specifically,
if `id_map_cnt` is less than `btf->nr_types`, we might need to consider whether
to resize the BTF. This could lead to missing types, potential ID remapping
failures, or even require BTF re-deduplication if certain name strings are no
longer referenced by any types.

>
> > +{
> > +       struct btf_permute p;
> > +       int i, err = 0;
> > +       __u32 *map = NULL;
> > +
> > +       if (!OPTS_VALID(opts, btf_permute_opts) || !ids)
>
> libbpf doesn't protect against NULL passed for mandatory parameters,
> please drop !ids check

Thanks, I will fix it.

>
> > +               return libbpf_err(-EINVAL);
> > +
> > +       map = calloc(btf->nr_types, sizeof(*map));
> > +       if (!map) {
> > +               err = -ENOMEM;
> > +               goto done;
> > +       }
> > +
> > +       for (i = 0; i < btf->nr_types; i++)
> > +               map[i] = BTF_UNPROCESSED_ID;
> > +
> > +       p.btf = btf;
> > +       p.btf_ext = OPTS_GET(opts, btf_ext, NULL);
> > +       p.ids = ids;
> > +       p.map = map;
> > +
> > +       if (btf_ensure_modifiable(btf)) {
> > +               err = -ENOMEM;
> > +               goto done;
> > +       }
> > +       err = btf_permute_shuffle_types(&p);
> > +       if (err < 0) {
> > +               pr_debug("btf_permute_shuffle_types failed: %s\n", errstr(err));
>
> let's drop these pr_debug(), I don't think it's something we expect to ever see

Thanks, I will remove it.

>
> > +               goto done;
> > +       }
> > +       err = btf_permute_remap_types(&p);
> > +       if (err < 0) {
> > +               pr_debug("btf_permute_remap_types failed: %s\n", errstr(err));
>
> ditto

Thanks, I will remove it.

>
> > +               goto done;
> > +       }
> > +
> > +done:
> > +       free(map);
> > +       return libbpf_err(err);
> > +}
> > +
> > +/* Shuffle BTF types.
> > + *
> > + * Rearranges types according to the permutation map in p->ids. The p->map
> > + * array stores the mapping from original type IDs to new shuffled IDs,
> > + * which is used in the next phase to update type references.
> > + *
> > + * Validates that all IDs in the permutation array are valid and unique.
> > + */
> > +static int btf_permute_shuffle_types(struct btf_permute *p)
> > +{
> > +       struct btf *btf = p->btf;
> > +       const struct btf_type *t;
> > +       __u32 *new_offs = NULL, *map;
> > +       void *nt, *new_types = NULL;
> > +       int i, id, len, err;
> > +
> > +       new_offs = calloc(btf->nr_types, sizeof(*new_offs));
>
> we don't really need to allocate memory and maintain this, we can just
> shift types around and then do what btf_parse_type_sec() does -- just
> go over types one by one and calculate offsets, and update them
> in-place inside btf->type_offs

Thank you for the suggestion. However, this approach is not viable because
the `btf__type_by_id()` function relies critically on the integrity of the
`btf->type_offs` data structure. Attempting to modify `type_offs` through
in-place operations could corrupt memory and lead to segmentation faults
due to invalid pointer dereferencing.

>
> > +       new_types = calloc(btf->hdr->type_len, 1);
> > +       if (!new_offs || !new_types) {
> > +               err = -ENOMEM;
> > +               goto out_err;
> > +       }
> > +
> > +       nt = new_types;
> > +       for (i = 0; i < btf->nr_types; i++) {
> > +               id = p->ids[i];
> > +               /* type IDs from base_btf and the VOID type are not allowed */
> > +               if (id < btf->start_id) {
> > +                       err = -EINVAL;
> > +                       goto out_err;
> > +               }
> > +               /* must be a valid type ID */
> > +               t = btf__type_by_id(btf, id);
> > +               if (!t) {
> > +                       err = -EINVAL;
> > +                       goto out_err;
> > +               }
> > +               map = &p->map[id - btf->start_id];
> > +               /* duplicate type IDs are not allowed */
> > +               if (*map != BTF_UNPROCESSED_ID) {
>
> there is no need for BTF_UNPROCESSED_ID, zero is a perfectly valid
> value to use as "not yet set" value, as we don't allow remapping VOID
> 0 to anything anyways.

Thanks, I will fix it.

>
> > +                       err = -EINVAL;
> > +                       goto out_err;
> > +               }
> > +               len = btf_type_size(t);
> > +               memcpy(nt, t, len);
>
> once you memcpy() data, you can use that btf_field_iter_init +
> btf_field_iter_next to *trivially* remap all IDs, no need for patch 1
> refactoring, IMO. And no need for two-phase approach either.
>
> > +               new_offs[i] = nt - new_types;
> > +               *map = btf->start_id + i;
> > +               nt += len;
> > +       }
> > +
> > +       free(btf->types_data);
> > +       free(btf->type_offs);
> > +       btf->types_data = new_types;
> > +       btf->type_offs = new_offs;
> > +       return 0;
> > +
> > +out_err:
> > +       free(new_offs);
> > +       free(new_types);
> > +       return err;
> > +}
> > +
> > +/* Callback function to remap individual type ID references
> > + *
> > + * This callback is invoked by btf_remap_types() for each type ID reference
> > + * found in the BTF data. It updates the reference to point to the new
> > + * permuted type ID using the mapping table.
> > + */
> > +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?
>
>
> > +       if (new_type_id > BTF_MAX_NR_TYPES)
> > +               return -EINVAL;
> > +
> > +       *type_id = new_type_id;
> > +       return 0;
> > +}
>
> [...]

Powered by blists - more mailing lists