From: pengdonglin <pengdonglin@xiaomi.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@gmail.com>
Cc: Alexei Starovoitov <ast@kernel.org>
Cc: Andrii Nakryiko <andrii.nakryiko@gmail.com>
Cc: Alan Maguire <alan.maguire@oracle.com>
Cc: Song Liu <song@kernel.org>
Signed-off-by: pengdonglin <pengdonglin@xiaomi.com>
Signed-off-by: Donglin Peng <dolinux.peng@gmail.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
+ * 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.
+ */
+ __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 */
+ __u32 *map;
+};
+
+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)
+{
+ struct btf_permute p;
+ int i, err = 0;
+ __u32 *map = NULL;
+
+ if (!OPTS_VALID(opts, btf_permute_opts) || !ids)
+ 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));
+ goto done;
+ }
+ err = btf_permute_remap_types(&p);
+ if (err < 0) {
+ pr_debug("btf_permute_remap_types failed: %s\n", errstr(err));
+ 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));
+ 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) {
+ err = -EINVAL;
+ goto out_err;
+ }
+ len = btf_type_size(t);
+ memcpy(nt, t, len);
+ 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];
+ if (new_type_id > BTF_MAX_NR_TYPES)
+ return -EINVAL;
+
+ *type_id = new_type_id;
+ return 0;
+}
+
+/* Remap referenced type IDs into permuted type IDs.
+ *
+ * After BTF types are permuted, their final type IDs may differ from original
+ * ones. The map from original to a corresponding permuted type ID is stored
+ * in btf_permute->map and is populated during shuffle phase. During remapping
+ * phase we are rewriting all type IDs referenced from any BTF type (e.g.,
+ * struct fields, func proto args, etc) to their final deduped type IDs.
+ */
+static int btf_permute_remap_types(struct btf_permute *p)
+{
+ return btf_remap_types(p->btf, p->btf_ext, btf_permute_remap_type_id, p);
+}
+
diff --git a/tools/lib/bpf/btf.h b/tools/lib/bpf/btf.h
index ccfd905f03df..441f6445d762 100644
--- a/tools/lib/bpf/btf.h
+++ b/tools/lib/bpf/btf.h
@@ -273,6 +273,40 @@ LIBBPF_API int btf__dedup(struct btf *btf, const struct btf_dedup_opts *opts);
*/
LIBBPF_API int btf__relocate(struct btf *btf, const struct btf *base_btf);
+struct btf_permute_opts {
+ size_t sz;
+ /* optional .BTF.ext info along the main BTF info */
+ struct btf_ext *btf_ext;
+ size_t :0;
+};
+#define btf_permute_opts__last_field btf_ext
+
+/**
+ * @brief **btf__permute()** rearranges BTF types in-place according to specified mapping
+ * @param btf BTF object to permute
+ * @param ids Array defining new type order. Must contain exactly btf->nr_types elements,
+ * each being a valid type ID in range [btf->start_id, btf->start_id + btf->nr_types - 1]
+ * @param opts Optional parameters, including BTF extension data for reference updates
+ * @return 0 on success, negative error code on failure
+ *
+ * **btf__permute()** performs an in-place permutation of BTF types, rearranging them
+ * according to the order specified in @p ids array. After reordering, all type references
+ * within the BTF data and optional BTF extension are updated to maintain consistency.
+ *
+ * The permutation process consists of two phases:
+ * 1. Type shuffling: Physical reordering of type data in memory
+ * 2. Reference remapping: Updating all type ID references to new locations
+ *
+ * This is particularly useful for optimizing type locality after BTF deduplication
+ * or for meeting specific layout requirements in specialized use cases.
+ *
+ * On error, negative error code is returned and errno is set appropriately.
+ * Common error codes include:
+ * - -EINVAL: Invalid parameters or invalid ID mapping (e.g., duplicate IDs, out-of-range IDs)
+ * - -ENOMEM: Memory allocation failure during permutation process
+ */
+LIBBPF_API int btf__permute(struct btf *btf, __u32 *ids, const struct btf_permute_opts *opts);
+
struct btf_dump;
struct btf_dump_opts {
diff --git a/tools/lib/bpf/libbpf.map b/tools/lib/bpf/libbpf.map
index 8ed8749907d4..b778e5a5d0a8 100644
--- a/tools/lib/bpf/libbpf.map
+++ b/tools/lib/bpf/libbpf.map
@@ -451,4 +451,5 @@ LIBBPF_1.7.0 {
global:
bpf_map__set_exclusive_program;
bpf_map__exclusive_program;
+ btf__permute;
} LIBBPF_1.6.0;
--
2.34.1On Tue, Nov 4, 2025 at 5:40 AM Donglin Peng <dolinux.peng@gmail.com> wrote:
>
> From: pengdonglin <pengdonglin@xiaomi.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@gmail.com>
> Cc: Alexei Starovoitov <ast@kernel.org>
> Cc: Andrii Nakryiko <andrii.nakryiko@gmail.com>
> Cc: Alan Maguire <alan.maguire@oracle.com>
> Cc: Song Liu <song@kernel.org>
> Signed-off-by: pengdonglin <pengdonglin@xiaomi.com>
> Signed-off-by: Donglin Peng <dolinux.peng@gmail.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;
> +}
[...]
On Wed, Nov 5, 2025 at 8:11 AM Andrii Nakryiko
<andrii.nakryiko@gmail.com> wrote:
>
> On Tue, Nov 4, 2025 at 5:40 AM Donglin Peng <dolinux.peng@gmail.com> wrote:
> >
> > From: pengdonglin <pengdonglin@xiaomi.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@gmail.com>
> > Cc: Alexei Starovoitov <ast@kernel.org>
> > Cc: Andrii Nakryiko <andrii.nakryiko@gmail.com>
> > Cc: Alan Maguire <alan.maguire@oracle.com>
> > Cc: Song Liu <song@kernel.org>
> > Signed-off-by: pengdonglin <pengdonglin@xiaomi.com>
> > Signed-off-by: Donglin Peng <dolinux.peng@gmail.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;
> > +}
>
> [...]
On Wed, Nov 5, 2025 at 4:53 AM Donglin Peng <dolinux.peng@gmail.com> wrote:
>
> On Wed, Nov 5, 2025 at 8:11 AM Andrii Nakryiko
> <andrii.nakryiko@gmail.com> wrote:
> >
> > On Tue, Nov 4, 2025 at 5:40 AM Donglin Peng <dolinux.peng@gmail.com> wrote:
> > >
> > > From: pengdonglin <pengdonglin@xiaomi.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@gmail.com>
> > > Cc: Alexei Starovoitov <ast@kernel.org>
> > > Cc: Andrii Nakryiko <andrii.nakryiko@gmail.com>
> > > Cc: Alan Maguire <alan.maguire@oracle.com>
> > > Cc: Song Liu <song@kernel.org>
> > > Signed-off-by: pengdonglin <pengdonglin@xiaomi.com>
> > > Signed-off-by: Donglin Peng <dolinux.peng@gmail.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
Users don't have access to btf->nr_types, so referring to it in API
description seems wrong.
But also, this all will change if we allow removing types, because
then array size might be smaller. But is it intentionally smaller or
user made a mistake? Let's go with the ID map approach, please.
> 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.
>
No, if the user provided a wrong id_map_cnt, it's an error and we
return -EINVAL. No resizing.
> >
> > > +{
> > > + struct btf_permute p;
> > > + int i, err = 0;
> > > + __u32 *map = NULL;
> > > +
> > > + if (!OPTS_VALID(opts, btf_permute_opts) || !ids)
> >
[...]
> > > + 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.
Huh? By the time this API returns, we'll fix up type_offs, users will
never notice. And to recalculate new type_offs we don't need
type_offs. One of us is missing something important, what is it?
[...]
On Thu, Nov 6, 2025 at 2:29 AM Andrii Nakryiko
<andrii.nakryiko@gmail.com> wrote:
>
> On Wed, Nov 5, 2025 at 4:53 AM Donglin Peng <dolinux.peng@gmail.com> wrote:
> >
> > On Wed, Nov 5, 2025 at 8:11 AM Andrii Nakryiko
> > <andrii.nakryiko@gmail.com> wrote:
> > >
> > > On Tue, Nov 4, 2025 at 5:40 AM Donglin Peng <dolinux.peng@gmail.com> wrote:
> > > >
> > > > From: pengdonglin <pengdonglin@xiaomi.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@gmail.com>
> > > > Cc: Alexei Starovoitov <ast@kernel.org>
> > > > Cc: Andrii Nakryiko <andrii.nakryiko@gmail.com>
> > > > Cc: Alan Maguire <alan.maguire@oracle.com>
> > > > Cc: Song Liu <song@kernel.org>
> > > > Signed-off-by: pengdonglin <pengdonglin@xiaomi.com>
> > > > Signed-off-by: Donglin Peng <dolinux.peng@gmail.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
>
> Users don't have access to btf->nr_types, so referring to it in API
> description seems wrong.
>
> But also, this all will change if we allow removing types, because
> then array size might be smaller. But is it intentionally smaller or
> user made a mistake? Let's go with the ID map approach, please.
Thanks. I can implement both approaches, then we can assess their
pros and cons.
>
> > 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.
> >
>
> No, if the user provided a wrong id_map_cnt, it's an error and we
> return -EINVAL. No resizing.
>
> > >
> > > > +{
> > > > + struct btf_permute p;
> > > > + int i, err = 0;
> > > > + __u32 *map = NULL;
> > > > +
> > > > + if (!OPTS_VALID(opts, btf_permute_opts) || !ids)
> > >
>
> [...]
>
> > > > + 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.
>
> Huh? By the time this API returns, we'll fix up type_offs, users will
> never notice. And to recalculate new type_offs we don't need
> type_offs. One of us is missing something important, what is it?
Thanks, however the bad news is that the btf__type_by_id is indeed called
within the API.
static int btf_permute_shuffle_types(struct btf_permute *p)
{
struct btf *btf = p->btf;
const struct btf_type *t;
__u32 *new_offs = NULL, *ids_map;
void *nt, *new_types = NULL;
int i, id, len, err;
new_offs = calloc(btf->nr_types, sizeof(*new_offs));
new_types = calloc(btf->hdr->type_len, 1);
......
nt = new_types;
for (i = 0; i < btf->nr_types; i++) {
id = p->ids[i];
......
/* must be a valid type ID */
t = btf__type_by_id(btf, id); <<<<<<<<<<<<<
......
len = btf_type_size(t);
memcpy(nt, t, len);
new_offs[i] = nt - new_types;
*ids_map = btf->start_id + i;
nt += len;
}
......
}
>
> [...]
On Wed, Nov 5, 2025 at 11:31 PM Donglin Peng <dolinux.peng@gmail.com> wrote:
>
> On Thu, Nov 6, 2025 at 2:29 AM Andrii Nakryiko
> <andrii.nakryiko@gmail.com> wrote:
> >
> > On Wed, Nov 5, 2025 at 4:53 AM Donglin Peng <dolinux.peng@gmail.com> wrote:
> > >
> > > On Wed, Nov 5, 2025 at 8:11 AM Andrii Nakryiko
> > > <andrii.nakryiko@gmail.com> wrote:
> > > >
> > > > On Tue, Nov 4, 2025 at 5:40 AM Donglin Peng <dolinux.peng@gmail.com> wrote:
> > > > >
> > > > > From: pengdonglin <pengdonglin@xiaomi.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@gmail.com>
> > > > > Cc: Alexei Starovoitov <ast@kernel.org>
> > > > > Cc: Andrii Nakryiko <andrii.nakryiko@gmail.com>
> > > > > Cc: Alan Maguire <alan.maguire@oracle.com>
> > > > > Cc: Song Liu <song@kernel.org>
> > > > > Signed-off-by: pengdonglin <pengdonglin@xiaomi.com>
> > > > > Signed-off-by: Donglin Peng <dolinux.peng@gmail.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
> >
> > Users don't have access to btf->nr_types, so referring to it in API
> > description seems wrong.
> >
> > But also, this all will change if we allow removing types, because
> > then array size might be smaller. But is it intentionally smaller or
> > user made a mistake? Let's go with the ID map approach, please.
>
> Thanks. I can implement both approaches, then we can assess their
> pros and cons.
>
> >
> > > 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.
> > >
> >
> > No, if the user provided a wrong id_map_cnt, it's an error and we
> > return -EINVAL. No resizing.
> >
> > > >
> > > > > +{
> > > > > + struct btf_permute p;
> > > > > + int i, err = 0;
> > > > > + __u32 *map = NULL;
> > > > > +
> > > > > + if (!OPTS_VALID(opts, btf_permute_opts) || !ids)
> > > >
> >
> > [...]
> >
> > > > > + 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.
> >
> > Huh? By the time this API returns, we'll fix up type_offs, users will
> > never notice. And to recalculate new type_offs we don't need
> > type_offs. One of us is missing something important, what is it?
>
> Thanks, however the bad news is that the btf__type_by_id is indeed called
> within the API.
>
> static int btf_permute_shuffle_types(struct btf_permute *p)
> {
> struct btf *btf = p->btf;
> const struct btf_type *t;
> __u32 *new_offs = NULL, *ids_map;
> void *nt, *new_types = NULL;
> int i, id, len, err;
>
> new_offs = calloc(btf->nr_types, sizeof(*new_offs));
> new_types = calloc(btf->hdr->type_len, 1);
> ......
> nt = new_types;
> for (i = 0; i < btf->nr_types; i++) {
> id = p->ids[i];
> ......
> /* must be a valid type ID */
> t = btf__type_by_id(btf, id); <<<<<<<<<<<<<
You are still on the old types layout and old type_offs at that point.
You are not using your new_offs here *anyways*
> ......
> len = btf_type_size(t);
> memcpy(nt, t, len);
> new_offs[i] = nt - new_types;
> *ids_map = btf->start_id + i;
> nt += len;
> }
> ......
... you will recalculate and update type_offs here ... well past
btf__type_by_id() usage ...
> }
>
> >
> > [...]
On Fri, Nov 7, 2025 at 1:13 AM Andrii Nakryiko
<andrii.nakryiko@gmail.com> wrote:
>
> On Wed, Nov 5, 2025 at 11:31 PM Donglin Peng <dolinux.peng@gmail.com> wrote:
> >
> > On Thu, Nov 6, 2025 at 2:29 AM Andrii Nakryiko
> > <andrii.nakryiko@gmail.com> wrote:
> > >
> > > On Wed, Nov 5, 2025 at 4:53 AM Donglin Peng <dolinux.peng@gmail.com> wrote:
> > > >
> > > > On Wed, Nov 5, 2025 at 8:11 AM Andrii Nakryiko
> > > > <andrii.nakryiko@gmail.com> wrote:
> > > > >
> > > > > On Tue, Nov 4, 2025 at 5:40 AM Donglin Peng <dolinux.peng@gmail.com> wrote:
> > > > > >
> > > > > > From: pengdonglin <pengdonglin@xiaomi.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@gmail.com>
> > > > > > Cc: Alexei Starovoitov <ast@kernel.org>
> > > > > > Cc: Andrii Nakryiko <andrii.nakryiko@gmail.com>
> > > > > > Cc: Alan Maguire <alan.maguire@oracle.com>
> > > > > > Cc: Song Liu <song@kernel.org>
> > > > > > Signed-off-by: pengdonglin <pengdonglin@xiaomi.com>
> > > > > > Signed-off-by: Donglin Peng <dolinux.peng@gmail.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
> > >
> > > Users don't have access to btf->nr_types, so referring to it in API
> > > description seems wrong.
> > >
> > > But also, this all will change if we allow removing types, because
> > > then array size might be smaller. But is it intentionally smaller or
> > > user made a mistake? Let's go with the ID map approach, please.
> >
> > Thanks. I can implement both approaches, then we can assess their
> > pros and cons.
> >
> > >
> > > > 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.
> > > >
> > >
> > > No, if the user provided a wrong id_map_cnt, it's an error and we
> > > return -EINVAL. No resizing.
> > >
> > > > >
> > > > > > +{
> > > > > > + struct btf_permute p;
> > > > > > + int i, err = 0;
> > > > > > + __u32 *map = NULL;
> > > > > > +
> > > > > > + if (!OPTS_VALID(opts, btf_permute_opts) || !ids)
> > > > >
> > >
> > > [...]
> > >
> > > > > > + 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.
> > >
> > > Huh? By the time this API returns, we'll fix up type_offs, users will
> > > never notice. And to recalculate new type_offs we don't need
> > > type_offs. One of us is missing something important, what is it?
> >
> > Thanks, however the bad news is that the btf__type_by_id is indeed called
> > within the API.
> >
> > static int btf_permute_shuffle_types(struct btf_permute *p)
> > {
> > struct btf *btf = p->btf;
> > const struct btf_type *t;
> > __u32 *new_offs = NULL, *ids_map;
> > void *nt, *new_types = NULL;
> > int i, id, len, err;
> >
> > new_offs = calloc(btf->nr_types, sizeof(*new_offs));
> > new_types = calloc(btf->hdr->type_len, 1);
> > ......
> > nt = new_types;
> > for (i = 0; i < btf->nr_types; i++) {
> > id = p->ids[i];
> > ......
> > /* must be a valid type ID */
> > t = btf__type_by_id(btf, id); <<<<<<<<<<<<<
>
> You are still on the old types layout and old type_offs at that point.
> You are not using your new_offs here *anyways*
>
> > ......
> > len = btf_type_size(t);
> > memcpy(nt, t, len);
> > new_offs[i] = nt - new_types;
> > *ids_map = btf->start_id + i;
> > nt += len;
> > }
> > ......
>
> ... you will recalculate and update type_offs here ... well past
> btf__type_by_id() usage ...
Thanks, I see. We need to add another for loop for this update, but
the cost is minimal compared to the memory savings. I will fix it in
v6.
>
> > }
> >
> > >
> > > [...]
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.
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?
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.
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.
On Thu, Nov 6, 2025 at 2:23 AM Andrii Nakryiko
<andrii.nakryiko@gmail.com> 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.
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`?
Should the following
mapping attempts be rejected:
a) If the target index `4` exceeds the total number of types (`nr_types`)?
b) If multiple source types map to the same target location
(e.g., both `[1] = 3`
and `[2] = 3`)?
- If [3] = 0, does this indicate that the type at start_id + 3 should
be dropped?
- Does this also imply that the VOID type (ID 0) cannot be remapped
and must always remain unchanged?
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?
On Thu, Nov 6, 2025 at 6:36 PM Donglin Peng <dolinux.peng@gmail.com> wrote:
>
> On Thu, Nov 6, 2025 at 2:23 AM Andrii Nakryiko
> <andrii.nakryiko@gmail.com> 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.
>
> 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).
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.
On Wed, Nov 5, 2025 at 11:23 AM Eduard Zingerman <eddyz87@gmail.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@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.
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.
On Wed, Nov 5, 2025 at 9:20 AM 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.
Thank you. I also favor the sequence interface approach.
if I understand correctly, using the ID mapping method would require
creating an additional ID array to cache the ordering for each type,
which appears more complex. Furthermore, generating an ID map might
not be straightforward for end users in the sorting scenario, IMO.
On Wed, Nov 5, 2025 at 5:19 AM Donglin Peng <dolinux.peng@gmail.com> wrote:
>
> On Wed, Nov 5, 2025 at 9:20 AM 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.
>
> Thank you. I also favor the sequence interface approach.
> if I understand correctly, using the ID mapping method would require
> creating an additional ID array to cache the ordering for each type,
> which appears more complex. Furthermore, generating an ID map might
> not be straightforward for end users in the sorting scenario, IMO.
Additional array on user side or inside libbpf's implementation? But
even if on the user side, a few temporary extra kilobytes to sort BTF
doesn't seem like a big limitation (definitely not for pahole, for
example).
On Tue, 2025-11-04 at 21:40 +0800, Donglin Peng wrote:
> From: pengdonglin <pengdonglin@xiaomi.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@gmail.com>
> Cc: Alexei Starovoitov <ast@kernel.org>
> Cc: Andrii Nakryiko <andrii.nakryiko@gmail.com>
> Cc: Alan Maguire <alan.maguire@oracle.com>
> Cc: Song Liu <song@kernel.org>
> Signed-off-by: pengdonglin <pengdonglin@xiaomi.com>
> Signed-off-by: Donglin Peng <dolinux.peng@gmail.com>
Acked-by: Eduard Zingerman <eddyz87@gmail.com>
[...]
> --- a/tools/lib/bpf/btf.h
> +++ b/tools/lib/bpf/btf.h
> @@ -273,6 +273,40 @@ LIBBPF_API int btf__dedup(struct btf *btf, const struct btf_dedup_opts *opts);
> */
> LIBBPF_API int btf__relocate(struct btf *btf, const struct btf *base_btf);
>
> +struct btf_permute_opts {
> + size_t sz;
> + /* optional .BTF.ext info along the main BTF info */
> + struct btf_ext *btf_ext;
> + size_t :0;
> +};
> +#define btf_permute_opts__last_field btf_ext
> +
> +/**
> + * @brief **btf__permute()** rearranges BTF types in-place according to specified mapping
> + * @param btf BTF object to permute
> + * @param ids Array defining new type order. Must contain exactly btf->nr_types elements,
> + * each being a valid type ID in range [btf->start_id, btf->start_id + btf->nr_types - 1]
> + * @param opts Optional parameters, including BTF extension data for reference updates
> + * @return 0 on success, negative error code on failure
> + *
> + * **btf__permute()** performs an in-place permutation of BTF types, rearranging them
> + * according to the order specified in @p ids array. After reordering, all type references
> + * within the BTF data and optional BTF extension are updated to maintain consistency.
> + *
> + * The permutation process consists of two phases:
> + * 1. Type shuffling: Physical reordering of type data in memory
> + * 2. Reference remapping: Updating all type ID references to new locations
Nit: Please drop this paragraph: it is an implementation detail, not
user-facing behavior, and it is obvious from the function code.
> + *
> + * This is particularly useful for optimizing type locality after BTF deduplication
> + * or for meeting specific layout requirements in specialized use cases.
Nit: Please drop this paragraph as well.
> + *
> + * On error, negative error code is returned and errno is set appropriately.
> + * Common error codes include:
> + * - -EINVAL: Invalid parameters or invalid ID mapping (e.g., duplicate IDs, out-of-range IDs)
> + * - -ENOMEM: Memory allocation failure during permutation process
> + */
> +LIBBPF_API int btf__permute(struct btf *btf, __u32 *ids, const struct btf_permute_opts *opts);
> +
> struct btf_dump;
>
> struct btf_dump_opts {
[...]
On Wed, Nov 5, 2025 at 7:45 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Tue, 2025-11-04 at 21:40 +0800, Donglin Peng wrote:
> > From: pengdonglin <pengdonglin@xiaomi.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@gmail.com>
> > Cc: Alexei Starovoitov <ast@kernel.org>
> > Cc: Andrii Nakryiko <andrii.nakryiko@gmail.com>
> > Cc: Alan Maguire <alan.maguire@oracle.com>
> > Cc: Song Liu <song@kernel.org>
> > Signed-off-by: pengdonglin <pengdonglin@xiaomi.com>
> > Signed-off-by: Donglin Peng <dolinux.peng@gmail.com>
>
> Acked-by: Eduard Zingerman <eddyz87@gmail.com>
>
> [...]
>
> > --- a/tools/lib/bpf/btf.h
> > +++ b/tools/lib/bpf/btf.h
> > @@ -273,6 +273,40 @@ LIBBPF_API int btf__dedup(struct btf *btf, const struct btf_dedup_opts *opts);
> > */
> > LIBBPF_API int btf__relocate(struct btf *btf, const struct btf *base_btf);
> >
> > +struct btf_permute_opts {
> > + size_t sz;
> > + /* optional .BTF.ext info along the main BTF info */
> > + struct btf_ext *btf_ext;
> > + size_t :0;
> > +};
> > +#define btf_permute_opts__last_field btf_ext
> > +
> > +/**
> > + * @brief **btf__permute()** rearranges BTF types in-place according to specified mapping
> > + * @param btf BTF object to permute
> > + * @param ids Array defining new type order. Must contain exactly btf->nr_types elements,
> > + * each being a valid type ID in range [btf->start_id, btf->start_id + btf->nr_types - 1]
> > + * @param opts Optional parameters, including BTF extension data for reference updates
> > + * @return 0 on success, negative error code on failure
> > + *
> > + * **btf__permute()** performs an in-place permutation of BTF types, rearranging them
> > + * according to the order specified in @p ids array. After reordering, all type references
> > + * within the BTF data and optional BTF extension are updated to maintain consistency.
> > + *
> > + * The permutation process consists of two phases:
> > + * 1. Type shuffling: Physical reordering of type data in memory
> > + * 2. Reference remapping: Updating all type ID references to new locations
>
> Nit: Please drop this paragraph: it is an implementation detail, not
> user-facing behavior, and it is obvious from the function code.
Thanks, I will fix it in the next version.
>
> > + *
> > + * This is particularly useful for optimizing type locality after BTF deduplication
> > + * or for meeting specific layout requirements in specialized use cases.
>
> Nit: Please drop this paragraph as well.
Thanks, I will fix it in the next version.
>
> > + *
> > + * On error, negative error code is returned and errno is set appropriately.
> > + * Common error codes include:
> > + * - -EINVAL: Invalid parameters or invalid ID mapping (e.g., duplicate IDs, out-of-range IDs)
> > + * - -ENOMEM: Memory allocation failure during permutation process
> > + */
> > +LIBBPF_API int btf__permute(struct btf *btf, __u32 *ids, const struct btf_permute_opts *opts);
> > +
> > struct btf_dump;
> >
> > struct btf_dump_opts {
>
> [...]
© 2016 - 2026 Red Hat, Inc.