Message-ID: <CAEf4BzaQ9k=_JwpmkjnbN8o0XaA=EGcP-=CBxmXLc3kzh3aY3A@mail.gmail.com>
Date: Tue, 4 Nov 2025 16:11:28 -0800
From: Andrii Nakryiko <andrii.nakryiko@...il.com>
To: Donglin Peng <dolinux.peng@...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 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
 */

> +        * 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...

> +        */
> +       __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

> +       __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.

> +};
> +
> +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.

> +{
> +       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

> +               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

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

ditto

> +               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

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

> +                       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