* [RFC PATCH v7 1/7] libbpf: Add BTF permutation support for type reordering
2025-11-19 3:15 [RFC PATCH v7 0/7] Improve the performance of BTF type lookups with binary search Donglin Peng
@ 2025-11-19 3:15 ` Donglin Peng
2025-11-19 18:21 ` Andrii Nakryiko
2025-11-19 3:15 ` [RFC PATCH v7 2/7] selftests/bpf: Add test cases for btf__permute functionality Donglin Peng
` (5 subsequent siblings)
6 siblings, 1 reply; 42+ messages in thread
From: Donglin Peng @ 2025-11-19 3:15 UTC (permalink / raw)
To: ast, andrii.nakryiko
Cc: eddyz87, zhangxiaoqin, linux-kernel, bpf, Donglin Peng,
Alan Maguire, Song Liu
From: Donglin Peng <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.
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>
Cc: Xiaoqin Zhang <zhangxiaoqin@xiaomi.com>
Signed-off-by: Donglin Peng <pengdonglin@xiaomi.com>
---
tools/lib/bpf/btf.c | 166 +++++++++++++++++++++++++++++++++++++++
tools/lib/bpf/btf.h | 43 ++++++++++
tools/lib/bpf/libbpf.map | 1 +
3 files changed, 210 insertions(+)
diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c
index 18907f0fcf9f..ab95ff19fde3 100644
--- a/tools/lib/bpf/btf.c
+++ b/tools/lib/bpf/btf.c
@@ -5829,3 +5829,169 @@ int btf__relocate(struct btf *btf, const struct btf *base_btf)
btf->owns_base = false;
return libbpf_err(err);
}
+
+struct btf_permute {
+ struct btf *btf;
+ __u32 *id_map;
+};
+
+/* Callback function to remap individual type ID references */
+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 or VOID */
+ if (new_type_id < p->btf->start_id)
+ return 0;
+
+ /* invalid reference id */
+ if (new_type_id >= btf__type_cnt(p->btf))
+ return -EINVAL;
+
+ new_type_id = p->id_map[new_type_id - p->btf->start_id];
+ /* reference a dropped type is not allowed */
+ if (new_type_id == 0)
+ return -EINVAL;
+
+ *type_id = new_type_id;
+ return 0;
+}
+
+int btf__permute(struct btf *btf, __u32 *id_map, __u32 id_map_cnt,
+ const struct btf_permute_opts *opts)
+{
+ struct btf_permute p;
+ struct btf_ext *btf_ext;
+ void *next_type, *end_type;
+ void *nt, *new_types = NULL;
+ int err = 0, i, new_type_len;
+ __u32 *order_map = NULL;
+ __u32 id, new_nr_types = 0;
+
+ if (!OPTS_VALID(opts, btf_permute_opts) || id_map_cnt != btf->nr_types)
+ return libbpf_err(-EINVAL);
+
+ /* used to record the storage sequence of types */
+ order_map = calloc(btf->nr_types, sizeof(*id_map));
+ if (!order_map) {
+ err = -ENOMEM;
+ goto done;
+ }
+
+ new_types = calloc(btf->hdr->type_len, 1);
+ if (!new_types) {
+ err = -ENOMEM;
+ goto done;
+ }
+
+ if (btf_ensure_modifiable(btf)) {
+ err = -ENOMEM;
+ goto done;
+ }
+
+ for (i = 0; i < id_map_cnt; i++) {
+ id = id_map[i];
+ /* Drop the specified type */
+ if (id == 0)
+ continue;
+ /* Invalid id */
+ if (id < btf->start_id || id >= btf__type_cnt(btf)) {
+ err = -EINVAL;
+ goto done;
+ }
+ id -= btf->start_id;
+ /* Multiple types cannot be mapped to the same ID */
+ if (order_map[id]) {
+ err = -EINVAL;
+ goto done;
+ }
+ order_map[id] = i + btf->start_id;
+ new_nr_types = max(id + 1, new_nr_types);
+ }
+
+ /* Check for missing IDs */
+ for (i = 0; i < new_nr_types; i++) {
+ if (order_map[i] == 0) {
+ err = -EINVAL;
+ goto done;
+ }
+ }
+
+ p.btf = btf;
+ p.id_map = id_map;
+ nt = new_types;
+ for (i = 0; i < new_nr_types; i++) {
+ struct btf_field_iter it;
+ const struct btf_type *t;
+ __u32 *type_id;
+ int type_size;
+
+ id = order_map[i];
+ /* must be a valid type ID */
+ t = btf__type_by_id(btf, id);
+ if (!t) {
+ err = -EINVAL;
+ goto done;
+ }
+ type_size = btf_type_size(t);
+ memcpy(nt, t, type_size);
+
+ /* Fix up referenced IDs for BTF */
+ err = btf_field_iter_init(&it, nt, BTF_FIELD_ITER_IDS);
+ if (err)
+ goto done;
+ while ((type_id = btf_field_iter_next(&it))) {
+ err = btf_permute_remap_type_id(type_id, &p);
+ if (err)
+ goto done;
+ }
+
+ nt += type_size;
+ }
+
+ /* Fix up referenced IDs for btf_ext */
+ btf_ext = OPTS_GET(opts, btf_ext, NULL);
+ if (btf_ext) {
+ err = btf_ext_visit_type_ids(btf_ext, btf_permute_remap_type_id, &p);
+ if (err)
+ goto done;
+ }
+
+ new_type_len = nt - new_types;
+ next_type = new_types;
+ end_type = next_type + new_type_len;
+ i = 0;
+ while (next_type + sizeof(struct btf_type) <= end_type) {
+ btf->type_offs[i++] = next_type - new_types;
+ next_type += btf_type_size(next_type);
+ }
+
+ /* Resize */
+ if (new_type_len < btf->hdr->type_len) {
+ void *tmp_types;
+
+ tmp_types = realloc(new_types, new_type_len);
+ if (new_type_len && !tmp_types) {
+ err = -ENOMEM;
+ goto done;
+ }
+ new_types = tmp_types;
+ btf->nr_types = new_nr_types;
+ btf->type_offs_cap = btf->nr_types;
+ btf->types_data_cap = new_type_len;
+ btf->hdr->type_len = new_type_len;
+ btf->hdr->str_off = new_type_len;
+ btf->raw_size = btf->hdr->hdr_len + btf->hdr->type_len + btf->hdr->str_len;
+ }
+
+ free(order_map);
+ free(btf->types_data);
+ btf->types_data = new_types;
+ return 0;
+
+done:
+ free(order_map);
+ free(new_types);
+ return libbpf_err(err);
+}
diff --git a/tools/lib/bpf/btf.h b/tools/lib/bpf/btf.h
index ccfd905f03df..e63dcce531b3 100644
--- a/tools/lib/bpf/btf.h
+++ b/tools/lib/bpf/btf.h
@@ -273,6 +273,49 @@ 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()** performs in-place BTF type rearrangement
+ * @param btf BTF object to permute
+ * @param id_map Array mapping original type IDs to new IDs
+ * @param id_map_cnt Number of elements in @id_map
+ * @param opts Optional parameters for BTF extension updates
+ * @return 0 on success, negative error code on failure
+ *
+ * **btf__permute()** rearranges BTF types according to the specified ID mapping.
+ * The @id_map array defines the new type ID for each original type ID.
+ *
+ * For **base BTF**:
+ * - @id_map must include all types from ID 1 to `btf__type_cnt(btf)-1`
+ * - @id_map_cnt should be `btf__type_cnt(btf) - 1`
+ * - Mapping uses `id_map[original_id - 1] = new_id`
+ *
+ * For **split BTF**:
+ * - @id_map should cover only split types
+ * - @id_map_cnt should be `btf__type_cnt(btf) - btf__type_cnt(btf__base_btf(btf))`
+ * - Mapping uses `id_map[original_id - btf__type_cnt(btf__base_btf(btf))] = new_id`
+ *
+ * Setting @id_map element to 0 drops the corresponding type. Dropped types must not
+ * be referenced by any retained types. After permutation, type references in BTF
+ * data and optional extension are updated automatically.
+ *
+ * Note: Dropping types may orphan some strings, requiring subsequent **btf__dedup()**
+ * to clean up unreferenced strings.
+ *
+ * On error, returns negative error code and sets errno:
+ * - `-EINVAL`: Invalid parameters or ID mapping (duplicates, out-of-range)
+ * - `-ENOMEM`: Memory allocation failure
+ */
+LIBBPF_API int btf__permute(struct btf *btf, __u32 *id_map, __u32 id_map_cnt,
+ 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.1
^ permalink raw reply related [flat|nested] 42+ messages in thread* Re: [RFC PATCH v7 1/7] libbpf: Add BTF permutation support for type reordering
2025-11-19 3:15 ` [RFC PATCH v7 1/7] libbpf: Add BTF permutation support for type reordering Donglin Peng
@ 2025-11-19 18:21 ` Andrii Nakryiko
2025-11-20 5:02 ` Donglin Peng
2025-11-20 23:21 ` Eduard Zingerman
0 siblings, 2 replies; 42+ messages in thread
From: Andrii Nakryiko @ 2025-11-19 18:21 UTC (permalink / raw)
To: Donglin Peng
Cc: ast, eddyz87, zhangxiaoqin, linux-kernel, bpf, Donglin Peng,
Alan Maguire, Song Liu
On Tue, Nov 18, 2025 at 7:21 PM Donglin Peng <dolinux.peng@gmail.com> wrote:
>
> From: Donglin Peng <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.
>
> 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>
> Cc: Xiaoqin Zhang <zhangxiaoqin@xiaomi.com>
> Signed-off-by: Donglin Peng <pengdonglin@xiaomi.com>
> ---
> tools/lib/bpf/btf.c | 166 +++++++++++++++++++++++++++++++++++++++
> tools/lib/bpf/btf.h | 43 ++++++++++
> tools/lib/bpf/libbpf.map | 1 +
> 3 files changed, 210 insertions(+)
>
> diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c
> index 18907f0fcf9f..ab95ff19fde3 100644
> --- a/tools/lib/bpf/btf.c
> +++ b/tools/lib/bpf/btf.c
> @@ -5829,3 +5829,169 @@ int btf__relocate(struct btf *btf, const struct btf *base_btf)
> btf->owns_base = false;
> return libbpf_err(err);
> }
> +
> +struct btf_permute {
> + struct btf *btf;
> + __u32 *id_map;
> +};
> +
> +/* Callback function to remap individual type ID references */
> +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 or VOID */
> + if (new_type_id < p->btf->start_id)
> + return 0;
> +
> + /* invalid reference id */
> + if (new_type_id >= btf__type_cnt(p->btf))
> + return -EINVAL;
> +
> + new_type_id = p->id_map[new_type_id - p->btf->start_id];
> + /* reference a dropped type is not allowed */
> + if (new_type_id == 0)
> + return -EINVAL;
see below, this shouldn't happen, let's drop redundant check
> +
> + *type_id = new_type_id;
> + return 0;
> +}
> +
> +int btf__permute(struct btf *btf, __u32 *id_map, __u32 id_map_cnt,
> + const struct btf_permute_opts *opts)
> +{
> + struct btf_permute p;
> + struct btf_ext *btf_ext;
> + void *next_type, *end_type;
> + void *nt, *new_types = NULL;
> + int err = 0, i, new_type_len;
> + __u32 *order_map = NULL;
> + __u32 id, new_nr_types = 0;
> +
> + if (!OPTS_VALID(opts, btf_permute_opts) || id_map_cnt != btf->nr_types)
> + return libbpf_err(-EINVAL);
> +
> + /* used to record the storage sequence of types */
> + order_map = calloc(btf->nr_types, sizeof(*id_map));
> + if (!order_map) {
> + err = -ENOMEM;
> + goto done;
> + }
> +
> + new_types = calloc(btf->hdr->type_len, 1);
> + if (!new_types) {
> + err = -ENOMEM;
> + goto done;
> + }
> +
> + if (btf_ensure_modifiable(btf)) {
> + err = -ENOMEM;
> + goto done;
> + }
> +
> + for (i = 0; i < id_map_cnt; i++) {
> + id = id_map[i];
> + /* Drop the specified type */
> + if (id == 0)
> + continue;
if we don't allow this (no support for deletion, I wouldn't rush to
add that right now)...
pw-bot: cr
> + /* Invalid id */
obvious statement, IMO, please drop the comment
> + if (id < btf->start_id || id >= btf__type_cnt(btf)) {
> + err = -EINVAL;
> + goto done;
> + }
> + id -= btf->start_id;
> + /* Multiple types cannot be mapped to the same ID */
> + if (order_map[id]) {
> + err = -EINVAL;
> + goto done;
> + }
> + order_map[id] = i + btf->start_id;
> + new_nr_types = max(id + 1, new_nr_types);
> + }
> +
> + /* Check for missing IDs */
> + for (i = 0; i < new_nr_types; i++) {
> + if (order_map[i] == 0) {
> + err = -EINVAL;
> + goto done;
> + }
> + }
... then you won't need this check at all, because we enforced that
each remapped ID is different and we have exactly nr_types of them.
Same for new_nr_types calculation above, seems redundant
> +
> + p.btf = btf;
> + p.id_map = id_map;
> + nt = new_types;
> + for (i = 0; i < new_nr_types; i++) {
> + struct btf_field_iter it;
> + const struct btf_type *t;
> + __u32 *type_id;
> + int type_size;
> +
> + id = order_map[i];
> + /* must be a valid type ID */
redundant comment, please drop
> + t = btf__type_by_id(btf, id);
> + if (!t) {
no need to check this, we already validated that all types are valid earlier
> + err = -EINVAL;
> + goto done;
> + }
> + type_size = btf_type_size(t);
> + memcpy(nt, t, type_size);
> +
> + /* Fix up referenced IDs for BTF */
> + err = btf_field_iter_init(&it, nt, BTF_FIELD_ITER_IDS);
> + if (err)
> + goto done;
> + while ((type_id = btf_field_iter_next(&it))) {
> + err = btf_permute_remap_type_id(type_id, &p);
> + if (err)
> + goto done;
> + }
> +
> + nt += type_size;
> + }
> +
> + /* Fix up referenced IDs for btf_ext */
> + btf_ext = OPTS_GET(opts, btf_ext, NULL);
> + if (btf_ext) {
> + err = btf_ext_visit_type_ids(btf_ext, btf_permute_remap_type_id, &p);
> + if (err)
> + goto done;
> + }
> +
> + new_type_len = nt - new_types;
new_type_len has to be exactly the same as the old size, this is redundant
> + next_type = new_types;
> + end_type = next_type + new_type_len;
> + i = 0;
> + while (next_type + sizeof(struct btf_type) <= end_type) {
while (next_type < end_type)?
Reference to struct btf_type is confusing, as generally type is bigger
than just sizeof(struct btf_type). But there is no need for this, with
correct code next_type < end_type is sufficient check
But really, this can also be written cleanly as a simple for loop
for (i = 0; i < nr_types; i++) {
btf->type_offs[i] = next_type - new_types;
next_type += btf_type_size(next_type);
}
> + btf->type_offs[i++] = next_type - new_types;
> + next_type += btf_type_size(next_type);
> + }
> +
> + /* Resize */
there cannot be any resizing, drop this, you only need to reassign
btf->types_data, that's all
> + if (new_type_len < btf->hdr->type_len) {
> + void *tmp_types;
> +
> + tmp_types = realloc(new_types, new_type_len);
> + if (new_type_len && !tmp_types) {
> + err = -ENOMEM;
> + goto done;
> + }
> + new_types = tmp_types;
> + btf->nr_types = new_nr_types;
> + btf->type_offs_cap = btf->nr_types;
> + btf->types_data_cap = new_type_len;
> + btf->hdr->type_len = new_type_len;
> + btf->hdr->str_off = new_type_len;
> + btf->raw_size = btf->hdr->hdr_len + btf->hdr->type_len + btf->hdr->str_len;
> + }
> +
> + free(order_map);
> + free(btf->types_data);
> + btf->types_data = new_types;
> + return 0;
> +
> +done:
> + free(order_map);
> + free(new_types);
> + return libbpf_err(err);
> +}
> diff --git a/tools/lib/bpf/btf.h b/tools/lib/bpf/btf.h
> index ccfd905f03df..e63dcce531b3 100644
> --- a/tools/lib/bpf/btf.h
> +++ b/tools/lib/bpf/btf.h
> @@ -273,6 +273,49 @@ 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()** performs in-place BTF type rearrangement
> + * @param btf BTF object to permute
> + * @param id_map Array mapping original type IDs to new IDs
> + * @param id_map_cnt Number of elements in @id_map
> + * @param opts Optional parameters for BTF extension updates
> + * @return 0 on success, negative error code on failure
> + *
> + * **btf__permute()** rearranges BTF types according to the specified ID mapping.
> + * The @id_map array defines the new type ID for each original type ID.
> + *
> + * For **base BTF**:
> + * - @id_map must include all types from ID 1 to `btf__type_cnt(btf)-1`
> + * - @id_map_cnt should be `btf__type_cnt(btf) - 1`
> + * - Mapping uses `id_map[original_id - 1] = new_id`
> + *
> + * For **split BTF**:
> + * - @id_map should cover only split types
> + * - @id_map_cnt should be `btf__type_cnt(btf) - btf__type_cnt(btf__base_btf(btf))`
> + * - Mapping uses `id_map[original_id - btf__type_cnt(btf__base_btf(btf))] = new_id`
> + *
> + * Setting @id_map element to 0 drops the corresponding type. Dropped types must not
> + * be referenced by any retained types. After permutation, type references in BTF
> + * data and optional extension are updated automatically.
let's not add deletion support just yet
> + *
> + * Note: Dropping types may orphan some strings, requiring subsequent **btf__dedup()**
> + * to clean up unreferenced strings.
one more reason to not add deletion just yet. It's good to have an API
that can express this, but we don't have to support deletion just yet.
> + *
> + * On error, returns negative error code and sets errno:
> + * - `-EINVAL`: Invalid parameters or ID mapping (duplicates, out-of-range)
> + * - `-ENOMEM`: Memory allocation failure
> + */
> +LIBBPF_API int btf__permute(struct btf *btf, __u32 *id_map, __u32 id_map_cnt,
> + 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.1
>
^ permalink raw reply [flat|nested] 42+ messages in thread* Re: [RFC PATCH v7 1/7] libbpf: Add BTF permutation support for type reordering
2025-11-19 18:21 ` Andrii Nakryiko
@ 2025-11-20 5:02 ` Donglin Peng
2025-11-20 23:21 ` Eduard Zingerman
1 sibling, 0 replies; 42+ messages in thread
From: Donglin Peng @ 2025-11-20 5:02 UTC (permalink / raw)
To: Andrii Nakryiko
Cc: ast, eddyz87, zhangxiaoqin, linux-kernel, bpf, Donglin Peng,
Alan Maguire, Song Liu
On Thu, Nov 20, 2025 at 2:22 AM Andrii Nakryiko
<andrii.nakryiko@gmail.com> wrote:
>
> On Tue, Nov 18, 2025 at 7:21 PM Donglin Peng <dolinux.peng@gmail.com> wrote:
> >
> > From: Donglin Peng <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.
> >
> > 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>
> > Cc: Xiaoqin Zhang <zhangxiaoqin@xiaomi.com>
> > Signed-off-by: Donglin Peng <pengdonglin@xiaomi.com>
> > ---
> > tools/lib/bpf/btf.c | 166 +++++++++++++++++++++++++++++++++++++++
> > tools/lib/bpf/btf.h | 43 ++++++++++
> > tools/lib/bpf/libbpf.map | 1 +
> > 3 files changed, 210 insertions(+)
> >
> > diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c
> > index 18907f0fcf9f..ab95ff19fde3 100644
> > --- a/tools/lib/bpf/btf.c
> > +++ b/tools/lib/bpf/btf.c
> > @@ -5829,3 +5829,169 @@ int btf__relocate(struct btf *btf, const struct btf *base_btf)
> > btf->owns_base = false;
> > return libbpf_err(err);
> > }
> > +
> > +struct btf_permute {
> > + struct btf *btf;
> > + __u32 *id_map;
> > +};
> > +
> > +/* Callback function to remap individual type ID references */
> > +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 or VOID */
> > + if (new_type_id < p->btf->start_id)
> > + return 0;
> > +
> > + /* invalid reference id */
> > + if (new_type_id >= btf__type_cnt(p->btf))
> > + return -EINVAL;
> > +
> > + new_type_id = p->id_map[new_type_id - p->btf->start_id];
> > + /* reference a dropped type is not allowed */
> > + if (new_type_id == 0)
> > + return -EINVAL;
>
> see below, this shouldn't happen, let's drop redundant check
Thanks, I will remove it.
>
> > +
> > + *type_id = new_type_id;
> > + return 0;
> > +}
> > +
> > +int btf__permute(struct btf *btf, __u32 *id_map, __u32 id_map_cnt,
> > + const struct btf_permute_opts *opts)
> > +{
> > + struct btf_permute p;
> > + struct btf_ext *btf_ext;
> > + void *next_type, *end_type;
> > + void *nt, *new_types = NULL;
> > + int err = 0, i, new_type_len;
> > + __u32 *order_map = NULL;
> > + __u32 id, new_nr_types = 0;
> > +
> > + if (!OPTS_VALID(opts, btf_permute_opts) || id_map_cnt != btf->nr_types)
> > + return libbpf_err(-EINVAL);
> > +
> > + /* used to record the storage sequence of types */
> > + order_map = calloc(btf->nr_types, sizeof(*id_map));
> > + if (!order_map) {
> > + err = -ENOMEM;
> > + goto done;
> > + }
> > +
> > + new_types = calloc(btf->hdr->type_len, 1);
> > + if (!new_types) {
> > + err = -ENOMEM;
> > + goto done;
> > + }
> > +
> > + if (btf_ensure_modifiable(btf)) {
> > + err = -ENOMEM;
> > + goto done;
> > + }
> > +
> > + for (i = 0; i < id_map_cnt; i++) {
> > + id = id_map[i];
> > + /* Drop the specified type */
> > + if (id == 0)
> > + continue;
>
> if we don't allow this (no support for deletion, I wouldn't rush to
> add that right now)...
Thanks, I will remove it.
>
> pw-bot: cr
>
>
> > + /* Invalid id */
>
> obvious statement, IMO, please drop the comment
Thanks, I will remove it.
>
> > + if (id < btf->start_id || id >= btf__type_cnt(btf)) {
> > + err = -EINVAL;
> > + goto done;
> > + }
> > + id -= btf->start_id;
> > + /* Multiple types cannot be mapped to the same ID */
> > + if (order_map[id]) {
> > + err = -EINVAL;
> > + goto done;
> > + }
> > + order_map[id] = i + btf->start_id;
> > + new_nr_types = max(id + 1, new_nr_types);
> > + }
> > +
> > + /* Check for missing IDs */
> > + for (i = 0; i < new_nr_types; i++) {
> > + if (order_map[i] == 0) {
> > + err = -EINVAL;
> > + goto done;
> > + }
> > + }
>
> ... then you won't need this check at all, because we enforced that
> each remapped ID is different and we have exactly nr_types of them.
> Same for new_nr_types calculation above, seems redundant
Yes, if we don't support the dropping feature, there's no need to do
this. I'll remove it.
>
> > +
> > + p.btf = btf;
> > + p.id_map = id_map;
> > + nt = new_types;
> > + for (i = 0; i < new_nr_types; i++) {
> > + struct btf_field_iter it;
> > + const struct btf_type *t;
> > + __u32 *type_id;
> > + int type_size;
> > +
> > + id = order_map[i];
> > + /* must be a valid type ID */
>
> redundant comment, please drop
Thanks, I will remove it.
>
> > + t = btf__type_by_id(btf, id);
> > + if (!t) {
>
> no need to check this, we already validated that all types are valid earlier
Thanks, I will remove it.
>
> > + err = -EINVAL;
> > + goto done;
> > + }
> > + type_size = btf_type_size(t);
> > + memcpy(nt, t, type_size);
> > +
> > + /* Fix up referenced IDs for BTF */
> > + err = btf_field_iter_init(&it, nt, BTF_FIELD_ITER_IDS);
> > + if (err)
> > + goto done;
> > + while ((type_id = btf_field_iter_next(&it))) {
> > + err = btf_permute_remap_type_id(type_id, &p);
> > + if (err)
> > + goto done;
> > + }
> > +
> > + nt += type_size;
> > + }
> > +
> > + /* Fix up referenced IDs for btf_ext */
> > + btf_ext = OPTS_GET(opts, btf_ext, NULL);
> > + if (btf_ext) {
> > + err = btf_ext_visit_type_ids(btf_ext, btf_permute_remap_type_id, &p);
> > + if (err)
> > + goto done;
> > + }
> > +
> > + new_type_len = nt - new_types;
>
>
> new_type_len has to be exactly the same as the old size, this is redundant
Yes, if we don't support the dropping feature, there's no need to do
this. I'll remove it.
>
> > + next_type = new_types;
> > + end_type = next_type + new_type_len;
> > + i = 0;
> > + while (next_type + sizeof(struct btf_type) <= end_type) {
>
> while (next_type < end_type)?
>
> Reference to struct btf_type is confusing, as generally type is bigger
> than just sizeof(struct btf_type). But there is no need for this, with
> correct code next_type < end_type is sufficient check
>
> But really, this can also be written cleanly as a simple for loop
>
> for (i = 0; i < nr_types; i++) {
> btf->type_offs[i] = next_type - new_types;
> next_type += btf_type_size(next_type);
> }
Great, thanks.
>
> > + btf->type_offs[i++] = next_type - new_types;
> > + next_type += btf_type_size(next_type);
> > + }
> > +
> > + /* Resize */
>
> there cannot be any resizing, drop this, you only need to reassign
> btf->types_data, that's all
Okay, I will do it.
>
> > + if (new_type_len < btf->hdr->type_len) {
> > + void *tmp_types;
> > +
> > + tmp_types = realloc(new_types, new_type_len);
> > + if (new_type_len && !tmp_types) {
> > + err = -ENOMEM;
> > + goto done;
> > + }
> > + new_types = tmp_types;
> > + btf->nr_types = new_nr_types;
> > + btf->type_offs_cap = btf->nr_types;
> > + btf->types_data_cap = new_type_len;
> > + btf->hdr->type_len = new_type_len;
> > + btf->hdr->str_off = new_type_len;
> > + btf->raw_size = btf->hdr->hdr_len + btf->hdr->type_len + btf->hdr->str_len;
> > + }
> > +
> > + free(order_map);
> > + free(btf->types_data);
> > + btf->types_data = new_types;
> > + return 0;
> > +
> > +done:
> > + free(order_map);
> > + free(new_types);
> > + return libbpf_err(err);
> > +}
> > diff --git a/tools/lib/bpf/btf.h b/tools/lib/bpf/btf.h
> > index ccfd905f03df..e63dcce531b3 100644
> > --- a/tools/lib/bpf/btf.h
> > +++ b/tools/lib/bpf/btf.h
> > @@ -273,6 +273,49 @@ 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()** performs in-place BTF type rearrangement
> > + * @param btf BTF object to permute
> > + * @param id_map Array mapping original type IDs to new IDs
> > + * @param id_map_cnt Number of elements in @id_map
> > + * @param opts Optional parameters for BTF extension updates
> > + * @return 0 on success, negative error code on failure
> > + *
> > + * **btf__permute()** rearranges BTF types according to the specified ID mapping.
> > + * The @id_map array defines the new type ID for each original type ID.
> > + *
> > + * For **base BTF**:
> > + * - @id_map must include all types from ID 1 to `btf__type_cnt(btf)-1`
> > + * - @id_map_cnt should be `btf__type_cnt(btf) - 1`
> > + * - Mapping uses `id_map[original_id - 1] = new_id`
> > + *
> > + * For **split BTF**:
> > + * - @id_map should cover only split types
> > + * - @id_map_cnt should be `btf__type_cnt(btf) - btf__type_cnt(btf__base_btf(btf))`
> > + * - Mapping uses `id_map[original_id - btf__type_cnt(btf__base_btf(btf))] = new_id`
> > + *
> > + * Setting @id_map element to 0 drops the corresponding type. Dropped types must not
> > + * be referenced by any retained types. After permutation, type references in BTF
> > + * data and optional extension are updated automatically.
>
> let's not add deletion support just yet
Thanks, I will modify the annotations.
>
> > + *
> > + * Note: Dropping types may orphan some strings, requiring subsequent **btf__dedup()**
> > + * to clean up unreferenced strings.
>
> one more reason to not add deletion just yet. It's good to have an API
> that can express this, but we don't have to support deletion just yet.
Thanks, I will remove it.
>
> > + *
> > + * On error, returns negative error code and sets errno:
> > + * - `-EINVAL`: Invalid parameters or ID mapping (duplicates, out-of-range)
> > + * - `-ENOMEM`: Memory allocation failure
> > + */
> > +LIBBPF_API int btf__permute(struct btf *btf, __u32 *id_map, __u32 id_map_cnt,
> > + 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.1
> >
^ permalink raw reply [flat|nested] 42+ messages in thread* Re: [RFC PATCH v7 1/7] libbpf: Add BTF permutation support for type reordering
2025-11-19 18:21 ` Andrii Nakryiko
2025-11-20 5:02 ` Donglin Peng
@ 2025-11-20 23:21 ` Eduard Zingerman
2025-11-21 14:15 ` Donglin Peng
1 sibling, 1 reply; 42+ messages in thread
From: Eduard Zingerman @ 2025-11-20 23:21 UTC (permalink / raw)
To: Andrii Nakryiko, Donglin Peng
Cc: ast, zhangxiaoqin, linux-kernel, bpf, Donglin Peng, Alan Maguire,
Song Liu
On Wed, 2025-11-19 at 10:21 -0800, Andrii Nakryiko wrote:
> On Tue, Nov 18, 2025 at 7:21 PM Donglin Peng <dolinux.peng@gmail.com> wrote:
[...]
> > + nt = new_types;
> > + for (i = 0; i < new_nr_types; i++) {
> > + struct btf_field_iter it;
> > + const struct btf_type *t;
> > + __u32 *type_id;
> > + int type_size;
> > +
> > + id = order_map[i];
> > + /* must be a valid type ID */
>
> redundant comment, please drop
>
> > + t = btf__type_by_id(btf, id);
> > + if (!t) {
>
> no need to check this, we already validated that all types are valid earlier
>
> > + err = -EINVAL;
> > + goto done;
> > + }
> > + type_size = btf_type_size(t);
> > + memcpy(nt, t, type_size);
> > +
> > + /* Fix up referenced IDs for BTF */
> > + err = btf_field_iter_init(&it, nt, BTF_FIELD_ITER_IDS);
> > + if (err)
> > + goto done;
> > + while ((type_id = btf_field_iter_next(&it))) {
> > + err = btf_permute_remap_type_id(type_id, &p);
> > + if (err)
> > + goto done;
> > + }
> > +
> > + nt += type_size;
> > + }
> > +
> > + /* Fix up referenced IDs for btf_ext */
> > + btf_ext = OPTS_GET(opts, btf_ext, NULL);
> > + if (btf_ext) {
> > + err = btf_ext_visit_type_ids(btf_ext, btf_permute_remap_type_id, &p);
> > + if (err)
> > + goto done;
> > + }
> > +
> > + new_type_len = nt - new_types;
>
>
> new_type_len has to be exactly the same as the old size, this is redundant
>
> > + next_type = new_types;
> > + end_type = next_type + new_type_len;
> > + i = 0;
> > + while (next_type + sizeof(struct btf_type) <= end_type) {
>
> while (next_type < end_type)?
>
> Reference to struct btf_type is confusing, as generally type is bigger
> than just sizeof(struct btf_type). But there is no need for this, with
> correct code next_type < end_type is sufficient check
>
> But really, this can also be written cleanly as a simple for loop
>
> for (i = 0; i < nr_types; i++) {
> btf->type_offs[i] = next_type - new_types;
> next_type += btf_type_size(next_type);
> }
>
Adding to what Andrii says, the whole group of assignments is
reducible:
+ new_type_len = nt - new_types;
+ next_type = new_types;
+ end_type = next_type + new_type_len;
=> end_type = new_types + new_type_len; // subst next_type -> new_types
=> end_type = new_types + nt - new_types; // subst new_types -> nt - new_types
=> end_type = nt
Why recomputing it in such a convoluted way?
> > + btf->type_offs[i++] = next_type - new_types;
> > + next_type += btf_type_size(next_type);
> > + }
> > +
[...]
^ permalink raw reply [flat|nested] 42+ messages in thread* Re: [RFC PATCH v7 1/7] libbpf: Add BTF permutation support for type reordering
2025-11-20 23:21 ` Eduard Zingerman
@ 2025-11-21 14:15 ` Donglin Peng
0 siblings, 0 replies; 42+ messages in thread
From: Donglin Peng @ 2025-11-21 14:15 UTC (permalink / raw)
To: Eduard Zingerman
Cc: Andrii Nakryiko, ast, zhangxiaoqin, linux-kernel, bpf,
Donglin Peng, Alan Maguire, Song Liu
On Fri, Nov 21, 2025 at 7:21 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Wed, 2025-11-19 at 10:21 -0800, Andrii Nakryiko wrote:
> > On Tue, Nov 18, 2025 at 7:21 PM Donglin Peng <dolinux.peng@gmail.com> wrote:
>
> [...]
>
> > > + nt = new_types;
> > > + for (i = 0; i < new_nr_types; i++) {
> > > + struct btf_field_iter it;
> > > + const struct btf_type *t;
> > > + __u32 *type_id;
> > > + int type_size;
> > > +
> > > + id = order_map[i];
> > > + /* must be a valid type ID */
> >
> > redundant comment, please drop
> >
> > > + t = btf__type_by_id(btf, id);
> > > + if (!t) {
> >
> > no need to check this, we already validated that all types are valid earlier
> >
> > > + err = -EINVAL;
> > > + goto done;
> > > + }
> > > + type_size = btf_type_size(t);
> > > + memcpy(nt, t, type_size);
> > > +
> > > + /* Fix up referenced IDs for BTF */
> > > + err = btf_field_iter_init(&it, nt, BTF_FIELD_ITER_IDS);
> > > + if (err)
> > > + goto done;
> > > + while ((type_id = btf_field_iter_next(&it))) {
> > > + err = btf_permute_remap_type_id(type_id, &p);
> > > + if (err)
> > > + goto done;
> > > + }
> > > +
> > > + nt += type_size;
> > > + }
> > > +
> > > + /* Fix up referenced IDs for btf_ext */
> > > + btf_ext = OPTS_GET(opts, btf_ext, NULL);
> > > + if (btf_ext) {
> > > + err = btf_ext_visit_type_ids(btf_ext, btf_permute_remap_type_id, &p);
> > > + if (err)
> > > + goto done;
> > > + }
> > > +
> > > + new_type_len = nt - new_types;
> >
> >
> > new_type_len has to be exactly the same as the old size, this is redundant
> >
> > > + next_type = new_types;
> > > + end_type = next_type + new_type_len;
> > > + i = 0;
> > > + while (next_type + sizeof(struct btf_type) <= end_type) {
> >
> > while (next_type < end_type)?
> >
> > Reference to struct btf_type is confusing, as generally type is bigger
> > than just sizeof(struct btf_type). But there is no need for this, with
> > correct code next_type < end_type is sufficient check
> >
> > But really, this can also be written cleanly as a simple for loop
> >
> > for (i = 0; i < nr_types; i++) {
> > btf->type_offs[i] = next_type - new_types;
> > next_type += btf_type_size(next_type);
> > }
> >
>
> Adding to what Andrii says, the whole group of assignments is
> reducible:
>
> + new_type_len = nt - new_types;
> + next_type = new_types;
> + end_type = next_type + new_type_len;
>
> => end_type = new_types + new_type_len; // subst next_type -> new_types
> => end_type = new_types + nt - new_types; // subst new_types -> nt - new_types
> => end_type = nt
>
> Why recomputing it in such a convoluted way?
Sorry, I referred to the implementation of btf_parse_type_sec and could have
thought more about how to refactor it.
>
> > > + btf->type_offs[i++] = next_type - new_types;
> > > + next_type += btf_type_size(next_type);
> > > + }
> > > +
>
> [...]
^ permalink raw reply [flat|nested] 42+ messages in thread
* [RFC PATCH v7 2/7] selftests/bpf: Add test cases for btf__permute functionality
2025-11-19 3:15 [RFC PATCH v7 0/7] Improve the performance of BTF type lookups with binary search Donglin Peng
2025-11-19 3:15 ` [RFC PATCH v7 1/7] libbpf: Add BTF permutation support for type reordering Donglin Peng
@ 2025-11-19 3:15 ` Donglin Peng
2025-11-19 4:51 ` Donglin Peng
` (2 more replies)
2025-11-19 3:15 ` [RFC PATCH v7 3/7] tools/resolve_btfids: Add --btf_sort option for BTF name sorting Donglin Peng
` (4 subsequent siblings)
6 siblings, 3 replies; 42+ messages in thread
From: Donglin Peng @ 2025-11-19 3:15 UTC (permalink / raw)
To: ast, andrii.nakryiko
Cc: eddyz87, zhangxiaoqin, linux-kernel, bpf, Donglin Peng,
Alan Maguire, Song Liu
From: Donglin Peng <pengdonglin@xiaomi.com>
This patch introduces test cases for the btf__permute function to ensure
it works correctly with both base BTF and split BTF scenarios.
The test suite includes:
- test_permute_base: Validates permutation on base BTF
- test_permute_split: Tests permutation on split BTF
- test_permute_drop_base: Validates type dropping on base BTF
- test_permute_drop_split: Tests type dropping on split BTF
- test_permute_drop_dedup: Tests type dropping and deduping
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>
Cc: Xiaoqin Zhang <zhangxiaoqin@xiaomi.com>
Signed-off-by: Donglin Peng <pengdonglin@xiaomi.com>
---
.../selftests/bpf/prog_tests/btf_permute.c | 608 ++++++++++++++++++
1 file changed, 608 insertions(+)
create mode 100644 tools/testing/selftests/bpf/prog_tests/btf_permute.c
diff --git a/tools/testing/selftests/bpf/prog_tests/btf_permute.c b/tools/testing/selftests/bpf/prog_tests/btf_permute.c
new file mode 100644
index 000000000000..f67bf89519b3
--- /dev/null
+++ b/tools/testing/selftests/bpf/prog_tests/btf_permute.c
@@ -0,0 +1,608 @@
+// SPDX-License-Identifier: GPL-2.0
+/* Copyright (c) 2025 Xiaomi */
+
+#include <test_progs.h>
+#include <bpf/btf.h>
+#include "btf_helpers.h"
+
+/* Ensure btf__permute work as expected with base BTF */
+static void test_permute_base(void)
+{
+ struct btf *btf;
+ __u32 permute_ids[6];
+ int start_id = 1;
+ int err;
+
+ btf = btf__new_empty();
+ if (!ASSERT_OK_PTR(btf, "empty_main_btf"))
+ return;
+
+ btf__add_int(btf, "int", 4, BTF_INT_SIGNED); /* [1] int */
+ btf__add_ptr(btf, 1); /* [2] ptr to int */
+ btf__add_struct(btf, "s1", 4); /* [3] struct s1 { */
+ btf__add_field(btf, "m", 1, 0, 0); /* int m; */
+ /* } */
+ btf__add_struct(btf, "s2", 4); /* [4] struct s2 { */
+ btf__add_field(btf, "m", 1, 0, 0); /* int m; */
+ /* } */
+ btf__add_func_proto(btf, 1); /* [5] int (*)(int *p); */
+ btf__add_func_param(btf, "p", 2);
+ btf__add_func(btf, "f", BTF_FUNC_STATIC, 5); /* [6] int f(int *p); */
+
+ VALIDATE_RAW_BTF(
+ btf,
+ "[1] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED",
+ "[2] PTR '(anon)' type_id=1",
+ "[3] STRUCT 's1' size=4 vlen=1\n"
+ "\t'm' type_id=1 bits_offset=0",
+ "[4] STRUCT 's2' size=4 vlen=1\n"
+ "\t'm' type_id=1 bits_offset=0",
+ "[5] FUNC_PROTO '(anon)' ret_type_id=1 vlen=1\n"
+ "\t'p' type_id=2",
+ "[6] FUNC 'f' type_id=5 linkage=static");
+
+ permute_ids[1 - start_id] = 4; /* [1] -> [4] */
+ permute_ids[2 - start_id] = 3; /* [2] -> [3] */
+ permute_ids[3 - start_id] = 5; /* [3] -> [5] */
+ permute_ids[4 - start_id] = 1; /* [4] -> [1] */
+ permute_ids[5 - start_id] = 6; /* [5] -> [6] */
+ permute_ids[6 - start_id] = 2; /* [6] -> [2] */
+ err = btf__permute(btf, permute_ids, ARRAY_SIZE(permute_ids), NULL);
+ if (!ASSERT_OK(err, "btf__permute_base"))
+ goto done;
+
+ VALIDATE_RAW_BTF(
+ btf,
+ "[1] STRUCT 's2' size=4 vlen=1\n"
+ "\t'm' type_id=4 bits_offset=0",
+ "[2] FUNC 'f' type_id=6 linkage=static",
+ "[3] PTR '(anon)' type_id=4",
+ "[4] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED",
+ "[5] STRUCT 's1' size=4 vlen=1\n"
+ "\t'm' type_id=4 bits_offset=0",
+ "[6] FUNC_PROTO '(anon)' ret_type_id=4 vlen=1\n"
+ "\t'p' type_id=3");
+
+ /*
+ * For base BTF, id_map_cnt must equal to the number of types
+ * include VOID type
+ */
+ permute_ids[1 - start_id] = 4; /* [1] -> [4] */
+ permute_ids[2 - start_id] = 3; /* [2] -> [3] */
+ permute_ids[3 - start_id] = 5; /* [3] -> [5] */
+ permute_ids[4 - start_id] = 1; /* [4] -> [1] */
+ permute_ids[5 - start_id] = 6; /* [5] -> [6] */
+ permute_ids[6 - start_id] = 2; /* [6] -> [2] */
+ err = btf__permute(btf, permute_ids, ARRAY_SIZE(permute_ids) - 1, NULL);
+ if (!ASSERT_ERR(err, "btf__permute_base"))
+ goto done;
+
+ VALIDATE_RAW_BTF(
+ btf,
+ "[1] STRUCT 's2' size=4 vlen=1\n"
+ "\t'm' type_id=4 bits_offset=0",
+ "[2] FUNC 'f' type_id=6 linkage=static",
+ "[3] PTR '(anon)' type_id=4",
+ "[4] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED",
+ "[5] STRUCT 's1' size=4 vlen=1\n"
+ "\t'm' type_id=4 bits_offset=0",
+ "[6] FUNC_PROTO '(anon)' ret_type_id=4 vlen=1\n"
+ "\t'p' type_id=3");
+
+ /* Multiple types can not be mapped to the same ID */
+ permute_ids[1 - start_id] = 4;
+ permute_ids[2 - start_id] = 4;
+ permute_ids[3 - start_id] = 5;
+ permute_ids[4 - start_id] = 1;
+ permute_ids[5 - start_id] = 6;
+ permute_ids[6 - start_id] = 2;
+ err = btf__permute(btf, permute_ids, ARRAY_SIZE(permute_ids), NULL);
+ if (!ASSERT_ERR(err, "btf__permute_base"))
+ goto done;
+
+ VALIDATE_RAW_BTF(
+ btf,
+ "[1] STRUCT 's2' size=4 vlen=1\n"
+ "\t'm' type_id=4 bits_offset=0",
+ "[2] FUNC 'f' type_id=6 linkage=static",
+ "[3] PTR '(anon)' type_id=4",
+ "[4] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED",
+ "[5] STRUCT 's1' size=4 vlen=1\n"
+ "\t'm' type_id=4 bits_offset=0",
+ "[6] FUNC_PROTO '(anon)' ret_type_id=4 vlen=1\n"
+ "\t'p' type_id=3");
+
+ /* Type ID must be valid */
+ permute_ids[1 - start_id] = 4;
+ permute_ids[2 - start_id] = 3;
+ permute_ids[3 - start_id] = 5;
+ permute_ids[4 - start_id] = 1;
+ permute_ids[5 - start_id] = 7;
+ permute_ids[6 - start_id] = 2;
+ err = btf__permute(btf, permute_ids, ARRAY_SIZE(permute_ids), NULL);
+ if (!ASSERT_ERR(err, "btf__permute_base"))
+ goto done;
+
+ VALIDATE_RAW_BTF(
+ btf,
+ "[1] STRUCT 's2' size=4 vlen=1\n"
+ "\t'm' type_id=4 bits_offset=0",
+ "[2] FUNC 'f' type_id=6 linkage=static",
+ "[3] PTR '(anon)' type_id=4",
+ "[4] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED",
+ "[5] STRUCT 's1' size=4 vlen=1\n"
+ "\t'm' type_id=4 bits_offset=0",
+ "[6] FUNC_PROTO '(anon)' ret_type_id=4 vlen=1\n"
+ "\t'p' type_id=3");
+
+done:
+ btf__free(btf);
+}
+
+/* Ensure btf__permute work as expected with split BTF */
+static void test_permute_split(void)
+{
+ struct btf *split_btf = NULL, *base_btf = NULL;
+ __u32 permute_ids[4];
+ int err;
+ int start_id;
+
+ base_btf = btf__new_empty();
+ if (!ASSERT_OK_PTR(base_btf, "empty_main_btf"))
+ return;
+
+ btf__add_int(base_btf, "int", 4, BTF_INT_SIGNED); /* [1] int */
+ btf__add_ptr(base_btf, 1); /* [2] ptr to int */
+ VALIDATE_RAW_BTF(
+ base_btf,
+ "[1] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED",
+ "[2] PTR '(anon)' type_id=1");
+ split_btf = btf__new_empty_split(base_btf);
+ if (!ASSERT_OK_PTR(split_btf, "empty_split_btf"))
+ goto cleanup;
+ btf__add_struct(split_btf, "s1", 4); /* [3] struct s1 { */
+ btf__add_field(split_btf, "m", 1, 0, 0); /* int m; */
+ /* } */
+ btf__add_struct(split_btf, "s2", 4); /* [4] struct s2 { */
+ btf__add_field(split_btf, "m", 1, 0, 0); /* int m; */
+ /* } */
+ btf__add_func_proto(split_btf, 1); /* [5] int (*)(int p); */
+ btf__add_func_param(split_btf, "p", 2);
+ btf__add_func(split_btf, "f", BTF_FUNC_STATIC, 5); /* [6] int f(int *p); */
+
+ VALIDATE_RAW_BTF(
+ split_btf,
+ "[1] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED",
+ "[2] PTR '(anon)' type_id=1",
+ "[3] STRUCT 's1' size=4 vlen=1\n"
+ "\t'm' type_id=1 bits_offset=0",
+ "[4] STRUCT 's2' size=4 vlen=1\n"
+ "\t'm' type_id=1 bits_offset=0",
+ "[5] FUNC_PROTO '(anon)' ret_type_id=1 vlen=1\n"
+ "\t'p' type_id=2",
+ "[6] FUNC 'f' type_id=5 linkage=static");
+
+ start_id = btf__type_cnt(base_btf);
+ permute_ids[3 - start_id] = 6; /* [3] -> [6] */
+ permute_ids[4 - start_id] = 3; /* [4] -> [3] */
+ permute_ids[5 - start_id] = 5; /* [5] -> [5] */
+ permute_ids[6 - start_id] = 4; /* [6] -> [4] */
+ err = btf__permute(split_btf, permute_ids, ARRAY_SIZE(permute_ids), NULL);
+ if (!ASSERT_OK(err, "btf__permute_split"))
+ goto cleanup;
+
+ VALIDATE_RAW_BTF(
+ split_btf,
+ "[1] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED",
+ "[2] PTR '(anon)' type_id=1",
+ "[3] STRUCT 's2' size=4 vlen=1\n"
+ "\t'm' type_id=1 bits_offset=0",
+ "[4] FUNC 'f' type_id=5 linkage=static",
+ "[5] FUNC_PROTO '(anon)' ret_type_id=1 vlen=1\n"
+ "\t'p' type_id=2",
+ "[6] STRUCT 's1' size=4 vlen=1\n"
+ "\t'm' type_id=1 bits_offset=0");
+
+ /*
+ * For split BTF, id_map_cnt must equal to the number of types
+ * added on top of base BTF
+ */
+ permute_ids[3 - start_id] = 4;
+ permute_ids[4 - start_id] = 3;
+ permute_ids[5 - start_id] = 5;
+ permute_ids[6 - start_id] = 6;
+ err = btf__permute(split_btf, permute_ids, 3, NULL);
+ if (!ASSERT_ERR(err, "btf__permute_split"))
+ goto cleanup;
+
+ VALIDATE_RAW_BTF(
+ split_btf,
+ "[1] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED",
+ "[2] PTR '(anon)' type_id=1",
+ "[3] STRUCT 's2' size=4 vlen=1\n"
+ "\t'm' type_id=1 bits_offset=0",
+ "[4] FUNC 'f' type_id=5 linkage=static",
+ "[5] FUNC_PROTO '(anon)' ret_type_id=1 vlen=1\n"
+ "\t'p' type_id=2",
+ "[6] STRUCT 's1' size=4 vlen=1\n"
+ "\t'm' type_id=1 bits_offset=0");
+
+ /* Multiple types can not be mapped to the same ID */
+ permute_ids[3 - start_id] = 4;
+ permute_ids[4 - start_id] = 3;
+ permute_ids[5 - start_id] = 3;
+ permute_ids[6 - start_id] = 6;
+ err = btf__permute(split_btf, permute_ids, 4, NULL);
+ if (!ASSERT_ERR(err, "btf__permute_split"))
+ goto cleanup;
+
+ VALIDATE_RAW_BTF(
+ split_btf,
+ "[1] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED",
+ "[2] PTR '(anon)' type_id=1",
+ "[3] STRUCT 's2' size=4 vlen=1\n"
+ "\t'm' type_id=1 bits_offset=0",
+ "[4] FUNC 'f' type_id=5 linkage=static",
+ "[5] FUNC_PROTO '(anon)' ret_type_id=1 vlen=1\n"
+ "\t'p' type_id=2",
+ "[6] STRUCT 's1' size=4 vlen=1\n"
+ "\t'm' type_id=1 bits_offset=0");
+
+ /* Can not map to base ID */
+ permute_ids[3 - start_id] = 4;
+ permute_ids[4 - start_id] = 2;
+ permute_ids[5 - start_id] = 5;
+ permute_ids[6 - start_id] = 6;
+ err = btf__permute(split_btf, permute_ids, 4, NULL);
+ if (!ASSERT_ERR(err, "btf__permute_split"))
+ goto cleanup;
+
+ VALIDATE_RAW_BTF(
+ split_btf,
+ "[1] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED",
+ "[2] PTR '(anon)' type_id=1",
+ "[3] STRUCT 's2' size=4 vlen=1\n"
+ "\t'm' type_id=1 bits_offset=0",
+ "[4] FUNC 'f' type_id=5 linkage=static",
+ "[5] FUNC_PROTO '(anon)' ret_type_id=1 vlen=1\n"
+ "\t'p' type_id=2",
+ "[6] STRUCT 's1' size=4 vlen=1\n"
+ "\t'm' type_id=1 bits_offset=0");
+
+cleanup:
+ btf__free(split_btf);
+ btf__free(base_btf);
+}
+
+/* Verify btf__permute function drops types correctly with base_btf */
+static void test_permute_drop_base(void)
+{
+ struct btf *btf;
+ __u32 permute_ids[6];
+ int start_id = 1;
+ int err;
+
+ btf = btf__new_empty();
+ if (!ASSERT_OK_PTR(btf, "empty_main_btf"))
+ return;
+
+ btf__add_int(btf, "int", 4, BTF_INT_SIGNED); /* [1] int */
+ btf__add_ptr(btf, 1); /* [2] ptr to int */
+ btf__add_struct(btf, "s1", 4); /* [3] struct s1 { */
+ btf__add_field(btf, "m", 1, 0, 0); /* int m; */
+ /* } */
+ btf__add_struct(btf, "s2", 4); /* [4] struct s2 { */
+ btf__add_field(btf, "m", 1, 0, 0); /* int m; */
+ /* } */
+ btf__add_func_proto(btf, 1); /* [5] int (*)(int *p); */
+ btf__add_func_param(btf, "p", 2);
+ btf__add_func(btf, "f", BTF_FUNC_STATIC, 5); /* [6] int f(int *p); */
+
+ VALIDATE_RAW_BTF(
+ btf,
+ "[1] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED",
+ "[2] PTR '(anon)' type_id=1",
+ "[3] STRUCT 's1' size=4 vlen=1\n"
+ "\t'm' type_id=1 bits_offset=0",
+ "[4] STRUCT 's2' size=4 vlen=1\n"
+ "\t'm' type_id=1 bits_offset=0",
+ "[5] FUNC_PROTO '(anon)' ret_type_id=1 vlen=1\n"
+ "\t'p' type_id=2",
+ "[6] FUNC 'f' type_id=5 linkage=static");
+
+ /* Drop ID 4 */
+ permute_ids[1 - start_id] = 5; /* [1] -> [5] */
+ permute_ids[2 - start_id] = 1; /* [2] -> [1] */
+ permute_ids[3 - start_id] = 2; /* [3] -> [2] */
+ permute_ids[4 - start_id] = 0; /* Drop [4] */
+ permute_ids[5 - start_id] = 3; /* [5] -> [3] */
+ permute_ids[6 - start_id] = 4; /* [6] -> [4] */
+ err = btf__permute(btf, permute_ids, ARRAY_SIZE(permute_ids), NULL);
+ if (!ASSERT_OK(err, "btf__permute_drop_base"))
+ goto done;
+
+ VALIDATE_RAW_BTF(
+ btf,
+ "[1] PTR '(anon)' type_id=5",
+ "[2] STRUCT 's1' size=4 vlen=1\n"
+ "\t'm' type_id=5 bits_offset=0",
+ "[3] FUNC_PROTO '(anon)' ret_type_id=5 vlen=1\n"
+ "\t'p' type_id=1",
+ "[4] FUNC 'f' type_id=3 linkage=static",
+ "[5] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED");
+
+ /* Continue dropping */
+ permute_ids[1 - start_id] = 1; /* [1] -> [1] */
+ permute_ids[2 - start_id] = 2; /* [2] -> [2] */
+ permute_ids[3 - start_id] = 3; /* [3] -> [3] */
+ permute_ids[4 - start_id] = 0; /* Drop [4] */
+ permute_ids[5 - start_id] = 4; /* [5] -> [4] */
+ err = btf__permute(btf, permute_ids, 5, NULL);
+ if (!ASSERT_OK(err, "btf__permute_drop_base_fail"))
+ goto done;
+
+
+ VALIDATE_RAW_BTF(
+ btf,
+ "[1] PTR '(anon)' type_id=4",
+ "[2] STRUCT 's1' size=4 vlen=1\n"
+ "\t'm' type_id=4 bits_offset=0",
+ "[3] FUNC_PROTO '(anon)' ret_type_id=4 vlen=1\n"
+ "\t'p' type_id=1",
+ "[4] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED");
+
+ /* Cannot drop the ID referenced by others */
+ permute_ids[1 - start_id] = 2;
+ permute_ids[2 - start_id] = 3;
+ permute_ids[3 - start_id] = 1;
+ permute_ids[4 - start_id] = 0; /* [4] is referenced by others */
+ err = btf__permute(btf, permute_ids, 4, NULL);
+ if (!ASSERT_ERR(err, "btf__permute_drop_base_fail"))
+ goto done;
+
+ VALIDATE_RAW_BTF(
+ btf,
+ "[1] PTR '(anon)' type_id=4",
+ "[2] STRUCT 's1' size=4 vlen=1\n"
+ "\t'm' type_id=4 bits_offset=0",
+ "[3] FUNC_PROTO '(anon)' ret_type_id=4 vlen=1\n"
+ "\t'p' type_id=1",
+ "[4] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED");
+
+ /* Drop 2 IDs at once */
+ permute_ids[1 - start_id] = 2; /* [1] -> [2] */
+ permute_ids[2 - start_id] = 0; /* Drop [2] */
+ permute_ids[3 - start_id] = 0; /* Drop [3] */
+ permute_ids[4 - start_id] = 1; /* [4] -> [1] */
+ err = btf__permute(btf, permute_ids, 4, NULL);
+ if (!ASSERT_OK(err, "btf__permute_drop_base_fail"))
+ goto done;
+
+ VALIDATE_RAW_BTF(
+ btf,
+ "[1] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED",
+ "[2] PTR '(anon)' type_id=1");
+
+ /* Drop all IDs */
+ permute_ids[1 - start_id] = 0; /* Drop [1] */
+ permute_ids[2 - start_id] = 0; /* Drop [2] */
+ err = btf__permute(btf, permute_ids, 2, NULL);
+ if (!ASSERT_OK(err, "btf__permute_drop_base_fail"))
+ goto done;
+ if (!ASSERT_EQ(btf__type_cnt(btf), 1, "btf__permute_drop_base all"))
+ goto done;
+
+done:
+ btf__free(btf);
+}
+
+/* Verify btf__permute function drops types correctly with split BTF */
+static void test_permute_drop_split(void)
+{
+ struct btf *split_btf = NULL, *base_btf = NULL;
+ __u32 permute_ids[4];
+ int err;
+ int start_id;
+
+ base_btf = btf__new_empty();
+ if (!ASSERT_OK_PTR(base_btf, "empty_main_btf"))
+ return;
+
+ btf__add_int(base_btf, "int", 4, BTF_INT_SIGNED); /* [1] int */
+ btf__add_ptr(base_btf, 1); /* [2] ptr to int */
+ VALIDATE_RAW_BTF(
+ base_btf,
+ "[1] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED",
+ "[2] PTR '(anon)' type_id=1");
+ split_btf = btf__new_empty_split(base_btf);
+ if (!ASSERT_OK_PTR(split_btf, "empty_split_btf"))
+ goto cleanup;
+ btf__add_struct(split_btf, "s1", 4); /* [3] struct s1 { */
+ btf__add_field(split_btf, "m", 1, 0, 0); /* int m; */
+ /* } */
+ btf__add_struct(split_btf, "s2", 4); /* [4] struct s2 { */
+ btf__add_field(split_btf, "m", 1, 0, 0); /* int m; */
+ /* } */
+ btf__add_func_proto(split_btf, 1); /* [5] int (*)(int p); */
+ btf__add_func_param(split_btf, "p", 2);
+ btf__add_func(split_btf, "f", BTF_FUNC_STATIC, 5); /* [6] int f(int *p); */
+
+ VALIDATE_RAW_BTF(
+ split_btf,
+ "[1] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED",
+ "[2] PTR '(anon)' type_id=1",
+ "[3] STRUCT 's1' size=4 vlen=1\n"
+ "\t'm' type_id=1 bits_offset=0",
+ "[4] STRUCT 's2' size=4 vlen=1\n"
+ "\t'm' type_id=1 bits_offset=0",
+ "[5] FUNC_PROTO '(anon)' ret_type_id=1 vlen=1\n"
+ "\t'p' type_id=2",
+ "[6] FUNC 'f' type_id=5 linkage=static");
+
+ start_id = btf__type_cnt(base_btf);
+
+ /* Drop ID 4 */
+ permute_ids[3 - start_id] = 5; /* [3] -> [5] */
+ permute_ids[4 - start_id] = 0; /* Drop [4] */
+ permute_ids[5 - start_id] = 3; /* [5] -> [3] */
+ permute_ids[6 - start_id] = 4; /* [6] -> [4] */
+ err = btf__permute(split_btf, permute_ids, ARRAY_SIZE(permute_ids), NULL);
+ if (!ASSERT_OK(err, "btf__permute_drop_split"))
+ goto cleanup;
+
+ VALIDATE_RAW_BTF(
+ split_btf,
+ "[1] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED",
+ "[2] PTR '(anon)' type_id=1",
+ "[3] FUNC_PROTO '(anon)' ret_type_id=1 vlen=1\n"
+ "\t'p' type_id=2",
+ "[4] FUNC 'f' type_id=3 linkage=static",
+ "[5] STRUCT 's1' size=4 vlen=1\n"
+ "\t'm' type_id=1 bits_offset=0");
+
+ /* Can not drop the type referenced by others */
+ permute_ids[3 - start_id] = 0; /* [3] is referenced by [4] */
+ permute_ids[4 - start_id] = 4;
+ permute_ids[5 - start_id] = 3;
+ err = btf__permute(split_btf, permute_ids, 3, NULL);
+ if (!ASSERT_ERR(err, "btf__permute_drop_split"))
+ goto cleanup;
+
+ VALIDATE_RAW_BTF(
+ split_btf,
+ "[1] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED",
+ "[2] PTR '(anon)' type_id=1",
+ "[3] FUNC_PROTO '(anon)' ret_type_id=1 vlen=1\n"
+ "\t'p' type_id=2",
+ "[4] FUNC 'f' type_id=3 linkage=static",
+ "[5] STRUCT 's1' size=4 vlen=1\n"
+ "\t'm' type_id=1 bits_offset=0");
+
+ /* Continue dropping */
+ permute_ids[3 - start_id] = 0; /* Drop [3] */
+ permute_ids[4 - start_id] = 0; /* Drop [4] */
+ permute_ids[5 - start_id] = 3; /* [5] -> [3] */
+ err = btf__permute(split_btf, permute_ids, 3, NULL);
+ if (!ASSERT_OK(err, "btf__permute_drop_split"))
+ goto cleanup;
+
+ VALIDATE_RAW_BTF(
+ split_btf,
+ "[1] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED",
+ "[2] PTR '(anon)' type_id=1",
+ "[3] STRUCT 's1' size=4 vlen=1\n"
+ "\t'm' type_id=1 bits_offset=0");
+
+ /* Continue dropping */
+ permute_ids[3 - start_id] = 0; /* Drop [3] */
+ err = btf__permute(split_btf, permute_ids, 1, NULL);
+ if (!ASSERT_OK(err, "btf__permute_drop_split"))
+ goto cleanup;
+
+ VALIDATE_RAW_BTF(
+ split_btf,
+ "[1] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED",
+ "[2] PTR '(anon)' type_id=1");
+
+cleanup:
+ btf__free(split_btf);
+ btf__free(base_btf);
+}
+
+/* Verify btf__permute then btf__dedup work correctly */
+static void test_permute_drop_dedup(void)
+{
+ struct btf *btf, *new_btf = NULL;
+ const struct btf_header *hdr;
+ const void *btf_data;
+ char expect_strs[] = "\0int\0s1\0m\0tag1\0tag2\0tag3";
+ char expect_strs_dedupped[] = "\0int\0s1\0m\0tag1";
+ __u32 permute_ids[5], btf_size;
+ int start_id = 1;
+ int err;
+
+ btf = btf__new_empty();
+ if (!ASSERT_OK_PTR(btf, "empty_main_btf"))
+ return;
+
+ btf__add_int(btf, "int", 4, BTF_INT_SIGNED); /* [1] int */
+ btf__add_struct(btf, "s1", 4); /* [2] struct s1 { */
+ btf__add_field(btf, "m", 1, 0, 0); /* int m; */
+ /* } */
+ btf__add_decl_tag(btf, "tag1", 2, -1); /* [3] tag -> s1: tag1 */
+ btf__add_decl_tag(btf, "tag2", 2, 1); /* [4] tag -> s1/m: tag2 */
+ btf__add_decl_tag(btf, "tag3", 2, 1); /* [5] tag -> s1/m: tag3 */
+
+ VALIDATE_RAW_BTF(
+ btf,
+ "[1] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED",
+ "[2] STRUCT 's1' size=4 vlen=1\n"
+ "\t'm' type_id=1 bits_offset=0",
+ "[3] DECL_TAG 'tag1' type_id=2 component_idx=-1",
+ "[4] DECL_TAG 'tag2' type_id=2 component_idx=1",
+ "[5] DECL_TAG 'tag3' type_id=2 component_idx=1");
+
+ btf_data = btf__raw_data(btf, &btf_size);
+ if (!ASSERT_OK_PTR(btf_data, "btf__raw_data"))
+ goto done;
+ hdr = btf_data;
+ if (!ASSERT_EQ(hdr->str_len, ARRAY_SIZE(expect_strs), "expect_strs"))
+ goto done;
+
+ new_btf = btf__new(btf_data, btf_size);
+ if (!ASSERT_OK_PTR(new_btf, "btf__new"))
+ goto done;
+
+ /* Drop 2 IDs result in unreferenced strings */
+ permute_ids[1 - start_id] = 3; /* [1] -> [3] */
+ permute_ids[2 - start_id] = 1; /* [2] -> [1] */
+ permute_ids[3 - start_id] = 2; /* [3] -> [2] */
+ permute_ids[4 - start_id] = 0; /* Drop result in unreferenced "tag2" */
+ permute_ids[5 - start_id] = 0; /* Drop result in unreferenced "tag3" */
+ err = btf__permute(new_btf, permute_ids, 5, NULL);
+ if (!ASSERT_OK(err, "btf__permute"))
+ goto done;
+
+ VALIDATE_RAW_BTF(
+ new_btf,
+ "[1] STRUCT 's1' size=4 vlen=1\n"
+ "\t'm' type_id=3 bits_offset=0",
+ "[2] DECL_TAG 'tag1' type_id=1 component_idx=-1",
+ "[3] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED");
+
+ btf_data = btf__raw_data(new_btf, &btf_size);
+ if (!ASSERT_OK_PTR(btf_data, "btf__raw_data"))
+ goto done;
+ hdr = btf_data;
+ if (!ASSERT_EQ(hdr->str_len, ARRAY_SIZE(expect_strs), "expect_strs"))
+ goto done;
+
+ err = btf__dedup(new_btf, NULL);
+ if (!ASSERT_OK(err, "btf__dedup"))
+ goto done;
+
+ btf_data = btf__raw_data(new_btf, &btf_size);
+ if (!ASSERT_OK_PTR(btf_data, "btf__raw_data"))
+ goto done;
+ hdr = btf_data;
+ if (!ASSERT_EQ(hdr->str_len, ARRAY_SIZE(expect_strs_dedupped), "expect_strs_dedupped"))
+ goto done;
+
+done:
+ btf__free(btf);
+ btf__free(new_btf);
+}
+
+void test_btf_permute(void)
+{
+ if (test__start_subtest("permute_base"))
+ test_permute_base();
+ if (test__start_subtest("permute_split"))
+ test_permute_split();
+ if (test__start_subtest("permute_drop_base"))
+ test_permute_drop_base();
+ if (test__start_subtest("permute_drop_split"))
+ test_permute_drop_split();
+ if (test__start_subtest("permute_drop_dedup"))
+ test_permute_drop_dedup();
+}
--
2.34.1
^ permalink raw reply related [flat|nested] 42+ messages in thread* Re: [RFC PATCH v7 2/7] selftests/bpf: Add test cases for btf__permute functionality
2025-11-19 3:15 ` [RFC PATCH v7 2/7] selftests/bpf: Add test cases for btf__permute functionality Donglin Peng
@ 2025-11-19 4:51 ` Donglin Peng
2025-11-20 23:39 ` Eduard Zingerman
2025-11-21 0:20 ` Eduard Zingerman
2 siblings, 0 replies; 42+ messages in thread
From: Donglin Peng @ 2025-11-19 4:51 UTC (permalink / raw)
To: ast, andrii.nakryiko
Cc: eddyz87, zhangxiaoqin, linux-kernel, bpf, Donglin Peng,
Alan Maguire, Song Liu
On Wed, Nov 19, 2025 at 11:21 AM Donglin Peng <dolinux.peng@gmail.com> wrote:
>
> From: Donglin Peng <pengdonglin@xiaomi.com>
>
> This patch introduces test cases for the btf__permute function to ensure
> it works correctly with both base BTF and split BTF scenarios.
>
> The test suite includes:
> - test_permute_base: Validates permutation on base BTF
> - test_permute_split: Tests permutation on split BTF
> - test_permute_drop_base: Validates type dropping on base BTF
> - test_permute_drop_split: Tests type dropping on split BTF
> - test_permute_drop_dedup: Tests type dropping and deduping
>
> 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>
> Cc: Xiaoqin Zhang <zhangxiaoqin@xiaomi.com>
> Signed-off-by: Donglin Peng <pengdonglin@xiaomi.com>
> ---
> .../selftests/bpf/prog_tests/btf_permute.c | 608 ++++++++++++++++++
> 1 file changed, 608 insertions(+)
> create mode 100644 tools/testing/selftests/bpf/prog_tests/btf_permute.c
>
> diff --git a/tools/testing/selftests/bpf/prog_tests/btf_permute.c b/tools/testing/selftests/bpf/prog_tests/btf_permute.c
> new file mode 100644
> index 000000000000..f67bf89519b3
> --- /dev/null
> +++ b/tools/testing/selftests/bpf/prog_tests/btf_permute.c
> @@ -0,0 +1,608 @@
> +// SPDX-License-Identifier: GPL-2.0
> +/* Copyright (c) 2025 Xiaomi */
> +
> +#include <test_progs.h>
> +#include <bpf/btf.h>
> +#include "btf_helpers.h"
> +
> +/* Ensure btf__permute work as expected with base BTF */
> +static void test_permute_base(void)
> +{
> + struct btf *btf;
> + __u32 permute_ids[6];
> + int start_id = 1;
> + int err;
> +
> + btf = btf__new_empty();
> + if (!ASSERT_OK_PTR(btf, "empty_main_btf"))
> + return;
> +
> + btf__add_int(btf, "int", 4, BTF_INT_SIGNED); /* [1] int */
> + btf__add_ptr(btf, 1); /* [2] ptr to int */
> + btf__add_struct(btf, "s1", 4); /* [3] struct s1 { */
> + btf__add_field(btf, "m", 1, 0, 0); /* int m; */
> + /* } */
> + btf__add_struct(btf, "s2", 4); /* [4] struct s2 { */
> + btf__add_field(btf, "m", 1, 0, 0); /* int m; */
> + /* } */
> + btf__add_func_proto(btf, 1); /* [5] int (*)(int *p); */
> + btf__add_func_param(btf, "p", 2);
> + btf__add_func(btf, "f", BTF_FUNC_STATIC, 5); /* [6] int f(int *p); */
> +
> + VALIDATE_RAW_BTF(
> + btf,
> + "[1] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED",
> + "[2] PTR '(anon)' type_id=1",
> + "[3] STRUCT 's1' size=4 vlen=1\n"
> + "\t'm' type_id=1 bits_offset=0",
> + "[4] STRUCT 's2' size=4 vlen=1\n"
> + "\t'm' type_id=1 bits_offset=0",
> + "[5] FUNC_PROTO '(anon)' ret_type_id=1 vlen=1\n"
> + "\t'p' type_id=2",
> + "[6] FUNC 'f' type_id=5 linkage=static");
> +
> + permute_ids[1 - start_id] = 4; /* [1] -> [4] */
> + permute_ids[2 - start_id] = 3; /* [2] -> [3] */
> + permute_ids[3 - start_id] = 5; /* [3] -> [5] */
> + permute_ids[4 - start_id] = 1; /* [4] -> [1] */
> + permute_ids[5 - start_id] = 6; /* [5] -> [6] */
> + permute_ids[6 - start_id] = 2; /* [6] -> [2] */
> + err = btf__permute(btf, permute_ids, ARRAY_SIZE(permute_ids), NULL);
> + if (!ASSERT_OK(err, "btf__permute_base"))
> + goto done;
> +
> + VALIDATE_RAW_BTF(
> + btf,
> + "[1] STRUCT 's2' size=4 vlen=1\n"
> + "\t'm' type_id=4 bits_offset=0",
> + "[2] FUNC 'f' type_id=6 linkage=static",
> + "[3] PTR '(anon)' type_id=4",
> + "[4] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED",
> + "[5] STRUCT 's1' size=4 vlen=1\n"
> + "\t'm' type_id=4 bits_offset=0",
> + "[6] FUNC_PROTO '(anon)' ret_type_id=4 vlen=1\n"
> + "\t'p' type_id=3");
> +
> + /*
> + * For base BTF, id_map_cnt must equal to the number of types
> + * include VOID type
> + */
My bad. I will remove those comments.
> + permute_ids[1 - start_id] = 4; /* [1] -> [4] */
> + permute_ids[2 - start_id] = 3; /* [2] -> [3] */
> + permute_ids[3 - start_id] = 5; /* [3] -> [5] */
> + permute_ids[4 - start_id] = 1; /* [4] -> [1] */
> + permute_ids[5 - start_id] = 6; /* [5] -> [6] */
> + permute_ids[6 - start_id] = 2; /* [6] -> [2] */
> + err = btf__permute(btf, permute_ids, ARRAY_SIZE(permute_ids) - 1, NULL);
> + if (!ASSERT_ERR(err, "btf__permute_base"))
> + goto done;
> +
> + VALIDATE_RAW_BTF(
> + btf,
> + "[1] STRUCT 's2' size=4 vlen=1\n"
> + "\t'm' type_id=4 bits_offset=0",
> + "[2] FUNC 'f' type_id=6 linkage=static",
> + "[3] PTR '(anon)' type_id=4",
> + "[4] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED",
> + "[5] STRUCT 's1' size=4 vlen=1\n"
> + "\t'm' type_id=4 bits_offset=0",
> + "[6] FUNC_PROTO '(anon)' ret_type_id=4 vlen=1\n"
> + "\t'p' type_id=3");
> +
> + /* Multiple types can not be mapped to the same ID */
> + permute_ids[1 - start_id] = 4;
> + permute_ids[2 - start_id] = 4;
> + permute_ids[3 - start_id] = 5;
> + permute_ids[4 - start_id] = 1;
> + permute_ids[5 - start_id] = 6;
> + permute_ids[6 - start_id] = 2;
> + err = btf__permute(btf, permute_ids, ARRAY_SIZE(permute_ids), NULL);
> + if (!ASSERT_ERR(err, "btf__permute_base"))
> + goto done;
> +
> + VALIDATE_RAW_BTF(
> + btf,
> + "[1] STRUCT 's2' size=4 vlen=1\n"
> + "\t'm' type_id=4 bits_offset=0",
> + "[2] FUNC 'f' type_id=6 linkage=static",
> + "[3] PTR '(anon)' type_id=4",
> + "[4] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED",
> + "[5] STRUCT 's1' size=4 vlen=1\n"
> + "\t'm' type_id=4 bits_offset=0",
> + "[6] FUNC_PROTO '(anon)' ret_type_id=4 vlen=1\n"
> + "\t'p' type_id=3");
> +
> + /* Type ID must be valid */
> + permute_ids[1 - start_id] = 4;
> + permute_ids[2 - start_id] = 3;
> + permute_ids[3 - start_id] = 5;
> + permute_ids[4 - start_id] = 1;
> + permute_ids[5 - start_id] = 7;
> + permute_ids[6 - start_id] = 2;
> + err = btf__permute(btf, permute_ids, ARRAY_SIZE(permute_ids), NULL);
> + if (!ASSERT_ERR(err, "btf__permute_base"))
> + goto done;
> +
> + VALIDATE_RAW_BTF(
> + btf,
> + "[1] STRUCT 's2' size=4 vlen=1\n"
> + "\t'm' type_id=4 bits_offset=0",
> + "[2] FUNC 'f' type_id=6 linkage=static",
> + "[3] PTR '(anon)' type_id=4",
> + "[4] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED",
> + "[5] STRUCT 's1' size=4 vlen=1\n"
> + "\t'm' type_id=4 bits_offset=0",
> + "[6] FUNC_PROTO '(anon)' ret_type_id=4 vlen=1\n"
> + "\t'p' type_id=3");
> +
> +done:
> + btf__free(btf);
> +}
> +
> +/* Ensure btf__permute work as expected with split BTF */
> +static void test_permute_split(void)
> +{
> + struct btf *split_btf = NULL, *base_btf = NULL;
> + __u32 permute_ids[4];
> + int err;
> + int start_id;
> +
> + base_btf = btf__new_empty();
> + if (!ASSERT_OK_PTR(base_btf, "empty_main_btf"))
> + return;
> +
> + btf__add_int(base_btf, "int", 4, BTF_INT_SIGNED); /* [1] int */
> + btf__add_ptr(base_btf, 1); /* [2] ptr to int */
> + VALIDATE_RAW_BTF(
> + base_btf,
> + "[1] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED",
> + "[2] PTR '(anon)' type_id=1");
> + split_btf = btf__new_empty_split(base_btf);
> + if (!ASSERT_OK_PTR(split_btf, "empty_split_btf"))
> + goto cleanup;
> + btf__add_struct(split_btf, "s1", 4); /* [3] struct s1 { */
> + btf__add_field(split_btf, "m", 1, 0, 0); /* int m; */
> + /* } */
> + btf__add_struct(split_btf, "s2", 4); /* [4] struct s2 { */
> + btf__add_field(split_btf, "m", 1, 0, 0); /* int m; */
> + /* } */
> + btf__add_func_proto(split_btf, 1); /* [5] int (*)(int p); */
> + btf__add_func_param(split_btf, "p", 2);
> + btf__add_func(split_btf, "f", BTF_FUNC_STATIC, 5); /* [6] int f(int *p); */
> +
> + VALIDATE_RAW_BTF(
> + split_btf,
> + "[1] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED",
> + "[2] PTR '(anon)' type_id=1",
> + "[3] STRUCT 's1' size=4 vlen=1\n"
> + "\t'm' type_id=1 bits_offset=0",
> + "[4] STRUCT 's2' size=4 vlen=1\n"
> + "\t'm' type_id=1 bits_offset=0",
> + "[5] FUNC_PROTO '(anon)' ret_type_id=1 vlen=1\n"
> + "\t'p' type_id=2",
> + "[6] FUNC 'f' type_id=5 linkage=static");
> +
> + start_id = btf__type_cnt(base_btf);
> + permute_ids[3 - start_id] = 6; /* [3] -> [6] */
> + permute_ids[4 - start_id] = 3; /* [4] -> [3] */
> + permute_ids[5 - start_id] = 5; /* [5] -> [5] */
> + permute_ids[6 - start_id] = 4; /* [6] -> [4] */
> + err = btf__permute(split_btf, permute_ids, ARRAY_SIZE(permute_ids), NULL);
> + if (!ASSERT_OK(err, "btf__permute_split"))
> + goto cleanup;
> +
> + VALIDATE_RAW_BTF(
> + split_btf,
> + "[1] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED",
> + "[2] PTR '(anon)' type_id=1",
> + "[3] STRUCT 's2' size=4 vlen=1\n"
> + "\t'm' type_id=1 bits_offset=0",
> + "[4] FUNC 'f' type_id=5 linkage=static",
> + "[5] FUNC_PROTO '(anon)' ret_type_id=1 vlen=1\n"
> + "\t'p' type_id=2",
> + "[6] STRUCT 's1' size=4 vlen=1\n"
> + "\t'm' type_id=1 bits_offset=0");
> +
> + /*
> + * For split BTF, id_map_cnt must equal to the number of types
> + * added on top of base BTF
> + */
> + permute_ids[3 - start_id] = 4;
> + permute_ids[4 - start_id] = 3;
> + permute_ids[5 - start_id] = 5;
> + permute_ids[6 - start_id] = 6;
> + err = btf__permute(split_btf, permute_ids, 3, NULL);
> + if (!ASSERT_ERR(err, "btf__permute_split"))
> + goto cleanup;
> +
> + VALIDATE_RAW_BTF(
> + split_btf,
> + "[1] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED",
> + "[2] PTR '(anon)' type_id=1",
> + "[3] STRUCT 's2' size=4 vlen=1\n"
> + "\t'm' type_id=1 bits_offset=0",
> + "[4] FUNC 'f' type_id=5 linkage=static",
> + "[5] FUNC_PROTO '(anon)' ret_type_id=1 vlen=1\n"
> + "\t'p' type_id=2",
> + "[6] STRUCT 's1' size=4 vlen=1\n"
> + "\t'm' type_id=1 bits_offset=0");
> +
> + /* Multiple types can not be mapped to the same ID */
> + permute_ids[3 - start_id] = 4;
> + permute_ids[4 - start_id] = 3;
> + permute_ids[5 - start_id] = 3;
> + permute_ids[6 - start_id] = 6;
> + err = btf__permute(split_btf, permute_ids, 4, NULL);
> + if (!ASSERT_ERR(err, "btf__permute_split"))
> + goto cleanup;
> +
> + VALIDATE_RAW_BTF(
> + split_btf,
> + "[1] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED",
> + "[2] PTR '(anon)' type_id=1",
> + "[3] STRUCT 's2' size=4 vlen=1\n"
> + "\t'm' type_id=1 bits_offset=0",
> + "[4] FUNC 'f' type_id=5 linkage=static",
> + "[5] FUNC_PROTO '(anon)' ret_type_id=1 vlen=1\n"
> + "\t'p' type_id=2",
> + "[6] STRUCT 's1' size=4 vlen=1\n"
> + "\t'm' type_id=1 bits_offset=0");
> +
> + /* Can not map to base ID */
> + permute_ids[3 - start_id] = 4;
> + permute_ids[4 - start_id] = 2;
> + permute_ids[5 - start_id] = 5;
> + permute_ids[6 - start_id] = 6;
> + err = btf__permute(split_btf, permute_ids, 4, NULL);
> + if (!ASSERT_ERR(err, "btf__permute_split"))
> + goto cleanup;
> +
> + VALIDATE_RAW_BTF(
> + split_btf,
> + "[1] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED",
> + "[2] PTR '(anon)' type_id=1",
> + "[3] STRUCT 's2' size=4 vlen=1\n"
> + "\t'm' type_id=1 bits_offset=0",
> + "[4] FUNC 'f' type_id=5 linkage=static",
> + "[5] FUNC_PROTO '(anon)' ret_type_id=1 vlen=1\n"
> + "\t'p' type_id=2",
> + "[6] STRUCT 's1' size=4 vlen=1\n"
> + "\t'm' type_id=1 bits_offset=0");
> +
> +cleanup:
> + btf__free(split_btf);
> + btf__free(base_btf);
> +}
> +
> +/* Verify btf__permute function drops types correctly with base_btf */
> +static void test_permute_drop_base(void)
> +{
> + struct btf *btf;
> + __u32 permute_ids[6];
> + int start_id = 1;
> + int err;
> +
> + btf = btf__new_empty();
> + if (!ASSERT_OK_PTR(btf, "empty_main_btf"))
> + return;
> +
> + btf__add_int(btf, "int", 4, BTF_INT_SIGNED); /* [1] int */
> + btf__add_ptr(btf, 1); /* [2] ptr to int */
> + btf__add_struct(btf, "s1", 4); /* [3] struct s1 { */
> + btf__add_field(btf, "m", 1, 0, 0); /* int m; */
> + /* } */
> + btf__add_struct(btf, "s2", 4); /* [4] struct s2 { */
> + btf__add_field(btf, "m", 1, 0, 0); /* int m; */
> + /* } */
> + btf__add_func_proto(btf, 1); /* [5] int (*)(int *p); */
> + btf__add_func_param(btf, "p", 2);
> + btf__add_func(btf, "f", BTF_FUNC_STATIC, 5); /* [6] int f(int *p); */
> +
> + VALIDATE_RAW_BTF(
> + btf,
> + "[1] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED",
> + "[2] PTR '(anon)' type_id=1",
> + "[3] STRUCT 's1' size=4 vlen=1\n"
> + "\t'm' type_id=1 bits_offset=0",
> + "[4] STRUCT 's2' size=4 vlen=1\n"
> + "\t'm' type_id=1 bits_offset=0",
> + "[5] FUNC_PROTO '(anon)' ret_type_id=1 vlen=1\n"
> + "\t'p' type_id=2",
> + "[6] FUNC 'f' type_id=5 linkage=static");
> +
> + /* Drop ID 4 */
> + permute_ids[1 - start_id] = 5; /* [1] -> [5] */
> + permute_ids[2 - start_id] = 1; /* [2] -> [1] */
> + permute_ids[3 - start_id] = 2; /* [3] -> [2] */
> + permute_ids[4 - start_id] = 0; /* Drop [4] */
> + permute_ids[5 - start_id] = 3; /* [5] -> [3] */
> + permute_ids[6 - start_id] = 4; /* [6] -> [4] */
> + err = btf__permute(btf, permute_ids, ARRAY_SIZE(permute_ids), NULL);
> + if (!ASSERT_OK(err, "btf__permute_drop_base"))
> + goto done;
> +
> + VALIDATE_RAW_BTF(
> + btf,
> + "[1] PTR '(anon)' type_id=5",
> + "[2] STRUCT 's1' size=4 vlen=1\n"
> + "\t'm' type_id=5 bits_offset=0",
> + "[3] FUNC_PROTO '(anon)' ret_type_id=5 vlen=1\n"
> + "\t'p' type_id=1",
> + "[4] FUNC 'f' type_id=3 linkage=static",
> + "[5] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED");
> +
> + /* Continue dropping */
> + permute_ids[1 - start_id] = 1; /* [1] -> [1] */
> + permute_ids[2 - start_id] = 2; /* [2] -> [2] */
> + permute_ids[3 - start_id] = 3; /* [3] -> [3] */
> + permute_ids[4 - start_id] = 0; /* Drop [4] */
> + permute_ids[5 - start_id] = 4; /* [5] -> [4] */
> + err = btf__permute(btf, permute_ids, 5, NULL);
> + if (!ASSERT_OK(err, "btf__permute_drop_base_fail"))
> + goto done;
> +
> +
> + VALIDATE_RAW_BTF(
> + btf,
> + "[1] PTR '(anon)' type_id=4",
> + "[2] STRUCT 's1' size=4 vlen=1\n"
> + "\t'm' type_id=4 bits_offset=0",
> + "[3] FUNC_PROTO '(anon)' ret_type_id=4 vlen=1\n"
> + "\t'p' type_id=1",
> + "[4] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED");
> +
> + /* Cannot drop the ID referenced by others */
> + permute_ids[1 - start_id] = 2;
> + permute_ids[2 - start_id] = 3;
> + permute_ids[3 - start_id] = 1;
> + permute_ids[4 - start_id] = 0; /* [4] is referenced by others */
> + err = btf__permute(btf, permute_ids, 4, NULL);
> + if (!ASSERT_ERR(err, "btf__permute_drop_base_fail"))
> + goto done;
> +
> + VALIDATE_RAW_BTF(
> + btf,
> + "[1] PTR '(anon)' type_id=4",
> + "[2] STRUCT 's1' size=4 vlen=1\n"
> + "\t'm' type_id=4 bits_offset=0",
> + "[3] FUNC_PROTO '(anon)' ret_type_id=4 vlen=1\n"
> + "\t'p' type_id=1",
> + "[4] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED");
> +
> + /* Drop 2 IDs at once */
> + permute_ids[1 - start_id] = 2; /* [1] -> [2] */
> + permute_ids[2 - start_id] = 0; /* Drop [2] */
> + permute_ids[3 - start_id] = 0; /* Drop [3] */
> + permute_ids[4 - start_id] = 1; /* [4] -> [1] */
> + err = btf__permute(btf, permute_ids, 4, NULL);
> + if (!ASSERT_OK(err, "btf__permute_drop_base_fail"))
> + goto done;
> +
> + VALIDATE_RAW_BTF(
> + btf,
> + "[1] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED",
> + "[2] PTR '(anon)' type_id=1");
> +
> + /* Drop all IDs */
> + permute_ids[1 - start_id] = 0; /* Drop [1] */
> + permute_ids[2 - start_id] = 0; /* Drop [2] */
> + err = btf__permute(btf, permute_ids, 2, NULL);
> + if (!ASSERT_OK(err, "btf__permute_drop_base_fail"))
> + goto done;
> + if (!ASSERT_EQ(btf__type_cnt(btf), 1, "btf__permute_drop_base all"))
> + goto done;
> +
> +done:
> + btf__free(btf);
> +}
> +
> +/* Verify btf__permute function drops types correctly with split BTF */
> +static void test_permute_drop_split(void)
> +{
> + struct btf *split_btf = NULL, *base_btf = NULL;
> + __u32 permute_ids[4];
> + int err;
> + int start_id;
> +
> + base_btf = btf__new_empty();
> + if (!ASSERT_OK_PTR(base_btf, "empty_main_btf"))
> + return;
> +
> + btf__add_int(base_btf, "int", 4, BTF_INT_SIGNED); /* [1] int */
> + btf__add_ptr(base_btf, 1); /* [2] ptr to int */
> + VALIDATE_RAW_BTF(
> + base_btf,
> + "[1] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED",
> + "[2] PTR '(anon)' type_id=1");
> + split_btf = btf__new_empty_split(base_btf);
> + if (!ASSERT_OK_PTR(split_btf, "empty_split_btf"))
> + goto cleanup;
> + btf__add_struct(split_btf, "s1", 4); /* [3] struct s1 { */
> + btf__add_field(split_btf, "m", 1, 0, 0); /* int m; */
> + /* } */
> + btf__add_struct(split_btf, "s2", 4); /* [4] struct s2 { */
> + btf__add_field(split_btf, "m", 1, 0, 0); /* int m; */
> + /* } */
> + btf__add_func_proto(split_btf, 1); /* [5] int (*)(int p); */
> + btf__add_func_param(split_btf, "p", 2);
> + btf__add_func(split_btf, "f", BTF_FUNC_STATIC, 5); /* [6] int f(int *p); */
> +
> + VALIDATE_RAW_BTF(
> + split_btf,
> + "[1] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED",
> + "[2] PTR '(anon)' type_id=1",
> + "[3] STRUCT 's1' size=4 vlen=1\n"
> + "\t'm' type_id=1 bits_offset=0",
> + "[4] STRUCT 's2' size=4 vlen=1\n"
> + "\t'm' type_id=1 bits_offset=0",
> + "[5] FUNC_PROTO '(anon)' ret_type_id=1 vlen=1\n"
> + "\t'p' type_id=2",
> + "[6] FUNC 'f' type_id=5 linkage=static");
> +
> + start_id = btf__type_cnt(base_btf);
> +
> + /* Drop ID 4 */
> + permute_ids[3 - start_id] = 5; /* [3] -> [5] */
> + permute_ids[4 - start_id] = 0; /* Drop [4] */
> + permute_ids[5 - start_id] = 3; /* [5] -> [3] */
> + permute_ids[6 - start_id] = 4; /* [6] -> [4] */
> + err = btf__permute(split_btf, permute_ids, ARRAY_SIZE(permute_ids), NULL);
> + if (!ASSERT_OK(err, "btf__permute_drop_split"))
> + goto cleanup;
> +
> + VALIDATE_RAW_BTF(
> + split_btf,
> + "[1] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED",
> + "[2] PTR '(anon)' type_id=1",
> + "[3] FUNC_PROTO '(anon)' ret_type_id=1 vlen=1\n"
> + "\t'p' type_id=2",
> + "[4] FUNC 'f' type_id=3 linkage=static",
> + "[5] STRUCT 's1' size=4 vlen=1\n"
> + "\t'm' type_id=1 bits_offset=0");
> +
> + /* Can not drop the type referenced by others */
> + permute_ids[3 - start_id] = 0; /* [3] is referenced by [4] */
> + permute_ids[4 - start_id] = 4;
> + permute_ids[5 - start_id] = 3;
> + err = btf__permute(split_btf, permute_ids, 3, NULL);
> + if (!ASSERT_ERR(err, "btf__permute_drop_split"))
> + goto cleanup;
> +
> + VALIDATE_RAW_BTF(
> + split_btf,
> + "[1] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED",
> + "[2] PTR '(anon)' type_id=1",
> + "[3] FUNC_PROTO '(anon)' ret_type_id=1 vlen=1\n"
> + "\t'p' type_id=2",
> + "[4] FUNC 'f' type_id=3 linkage=static",
> + "[5] STRUCT 's1' size=4 vlen=1\n"
> + "\t'm' type_id=1 bits_offset=0");
> +
> + /* Continue dropping */
> + permute_ids[3 - start_id] = 0; /* Drop [3] */
> + permute_ids[4 - start_id] = 0; /* Drop [4] */
> + permute_ids[5 - start_id] = 3; /* [5] -> [3] */
> + err = btf__permute(split_btf, permute_ids, 3, NULL);
> + if (!ASSERT_OK(err, "btf__permute_drop_split"))
> + goto cleanup;
> +
> + VALIDATE_RAW_BTF(
> + split_btf,
> + "[1] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED",
> + "[2] PTR '(anon)' type_id=1",
> + "[3] STRUCT 's1' size=4 vlen=1\n"
> + "\t'm' type_id=1 bits_offset=0");
> +
> + /* Continue dropping */
> + permute_ids[3 - start_id] = 0; /* Drop [3] */
> + err = btf__permute(split_btf, permute_ids, 1, NULL);
> + if (!ASSERT_OK(err, "btf__permute_drop_split"))
> + goto cleanup;
> +
> + VALIDATE_RAW_BTF(
> + split_btf,
> + "[1] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED",
> + "[2] PTR '(anon)' type_id=1");
> +
> +cleanup:
> + btf__free(split_btf);
> + btf__free(base_btf);
> +}
> +
> +/* Verify btf__permute then btf__dedup work correctly */
> +static void test_permute_drop_dedup(void)
> +{
> + struct btf *btf, *new_btf = NULL;
> + const struct btf_header *hdr;
> + const void *btf_data;
> + char expect_strs[] = "\0int\0s1\0m\0tag1\0tag2\0tag3";
> + char expect_strs_dedupped[] = "\0int\0s1\0m\0tag1";
> + __u32 permute_ids[5], btf_size;
> + int start_id = 1;
> + int err;
> +
> + btf = btf__new_empty();
> + if (!ASSERT_OK_PTR(btf, "empty_main_btf"))
> + return;
> +
> + btf__add_int(btf, "int", 4, BTF_INT_SIGNED); /* [1] int */
> + btf__add_struct(btf, "s1", 4); /* [2] struct s1 { */
> + btf__add_field(btf, "m", 1, 0, 0); /* int m; */
> + /* } */
> + btf__add_decl_tag(btf, "tag1", 2, -1); /* [3] tag -> s1: tag1 */
> + btf__add_decl_tag(btf, "tag2", 2, 1); /* [4] tag -> s1/m: tag2 */
> + btf__add_decl_tag(btf, "tag3", 2, 1); /* [5] tag -> s1/m: tag3 */
> +
> + VALIDATE_RAW_BTF(
> + btf,
> + "[1] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED",
> + "[2] STRUCT 's1' size=4 vlen=1\n"
> + "\t'm' type_id=1 bits_offset=0",
> + "[3] DECL_TAG 'tag1' type_id=2 component_idx=-1",
> + "[4] DECL_TAG 'tag2' type_id=2 component_idx=1",
> + "[5] DECL_TAG 'tag3' type_id=2 component_idx=1");
> +
> + btf_data = btf__raw_data(btf, &btf_size);
> + if (!ASSERT_OK_PTR(btf_data, "btf__raw_data"))
> + goto done;
> + hdr = btf_data;
> + if (!ASSERT_EQ(hdr->str_len, ARRAY_SIZE(expect_strs), "expect_strs"))
> + goto done;
> +
> + new_btf = btf__new(btf_data, btf_size);
> + if (!ASSERT_OK_PTR(new_btf, "btf__new"))
> + goto done;
> +
> + /* Drop 2 IDs result in unreferenced strings */
> + permute_ids[1 - start_id] = 3; /* [1] -> [3] */
> + permute_ids[2 - start_id] = 1; /* [2] -> [1] */
> + permute_ids[3 - start_id] = 2; /* [3] -> [2] */
> + permute_ids[4 - start_id] = 0; /* Drop result in unreferenced "tag2" */
> + permute_ids[5 - start_id] = 0; /* Drop result in unreferenced "tag3" */
> + err = btf__permute(new_btf, permute_ids, 5, NULL);
> + if (!ASSERT_OK(err, "btf__permute"))
> + goto done;
> +
> + VALIDATE_RAW_BTF(
> + new_btf,
> + "[1] STRUCT 's1' size=4 vlen=1\n"
> + "\t'm' type_id=3 bits_offset=0",
> + "[2] DECL_TAG 'tag1' type_id=1 component_idx=-1",
> + "[3] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED");
> +
> + btf_data = btf__raw_data(new_btf, &btf_size);
> + if (!ASSERT_OK_PTR(btf_data, "btf__raw_data"))
> + goto done;
> + hdr = btf_data;
> + if (!ASSERT_EQ(hdr->str_len, ARRAY_SIZE(expect_strs), "expect_strs"))
> + goto done;
> +
> + err = btf__dedup(new_btf, NULL);
> + if (!ASSERT_OK(err, "btf__dedup"))
> + goto done;
> +
> + btf_data = btf__raw_data(new_btf, &btf_size);
> + if (!ASSERT_OK_PTR(btf_data, "btf__raw_data"))
> + goto done;
> + hdr = btf_data;
> + if (!ASSERT_EQ(hdr->str_len, ARRAY_SIZE(expect_strs_dedupped), "expect_strs_dedupped"))
> + goto done;
> +
> +done:
> + btf__free(btf);
> + btf__free(new_btf);
> +}
> +
> +void test_btf_permute(void)
> +{
> + if (test__start_subtest("permute_base"))
> + test_permute_base();
> + if (test__start_subtest("permute_split"))
> + test_permute_split();
> + if (test__start_subtest("permute_drop_base"))
> + test_permute_drop_base();
> + if (test__start_subtest("permute_drop_split"))
> + test_permute_drop_split();
> + if (test__start_subtest("permute_drop_dedup"))
> + test_permute_drop_dedup();
> +}
> --
> 2.34.1
>
^ permalink raw reply [flat|nested] 42+ messages in thread* Re: [RFC PATCH v7 2/7] selftests/bpf: Add test cases for btf__permute functionality
2025-11-19 3:15 ` [RFC PATCH v7 2/7] selftests/bpf: Add test cases for btf__permute functionality Donglin Peng
2025-11-19 4:51 ` Donglin Peng
@ 2025-11-20 23:39 ` Eduard Zingerman
2025-11-21 14:17 ` Donglin Peng
2025-11-21 0:20 ` Eduard Zingerman
2 siblings, 1 reply; 42+ messages in thread
From: Eduard Zingerman @ 2025-11-20 23:39 UTC (permalink / raw)
To: Donglin Peng, ast, andrii.nakryiko
Cc: zhangxiaoqin, linux-kernel, bpf, Donglin Peng, Alan Maguire,
Song Liu
On Wed, 2025-11-19 at 11:15 +0800, Donglin Peng wrote:
[...]
> diff --git a/tools/testing/selftests/bpf/prog_tests/btf_permute.c b/tools/testing/selftests/bpf/prog_tests/btf_permute.c
> new file mode 100644
> index 000000000000..f67bf89519b3
> --- /dev/null
> +++ b/tools/testing/selftests/bpf/prog_tests/btf_permute.c
> @@ -0,0 +1,608 @@
> +// SPDX-License-Identifier: GPL-2.0
> +/* Copyright (c) 2025 Xiaomi */
> +
> +#include <test_progs.h>
> +#include <bpf/btf.h>
> +#include "btf_helpers.h"
> +
> +/* Ensure btf__permute work as expected with base BTF */
> +static void test_permute_base(void)
> +{
> + struct btf *btf;
> + __u32 permute_ids[6];
> + int start_id = 1;
> + int err;
> +
> + btf = btf__new_empty();
> + if (!ASSERT_OK_PTR(btf, "empty_main_btf"))
> + return;
> +
> + btf__add_int(btf, "int", 4, BTF_INT_SIGNED); /* [1] int */
> + btf__add_ptr(btf, 1); /* [2] ptr to int */
> + btf__add_struct(btf, "s1", 4); /* [3] struct s1 { */
> + btf__add_field(btf, "m", 1, 0, 0); /* int m; */
> + /* } */
> + btf__add_struct(btf, "s2", 4); /* [4] struct s2 { */
> + btf__add_field(btf, "m", 1, 0, 0); /* int m; */
> + /* } */
> + btf__add_func_proto(btf, 1); /* [5] int (*)(int *p); */
> + btf__add_func_param(btf, "p", 2);
> + btf__add_func(btf, "f", BTF_FUNC_STATIC, 5); /* [6] int f(int *p); */
> +
> + VALIDATE_RAW_BTF(
> + btf,
> + "[1] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED",
> + "[2] PTR '(anon)' type_id=1",
> + "[3] STRUCT 's1' size=4 vlen=1\n"
> + "\t'm' type_id=1 bits_offset=0",
> + "[4] STRUCT 's2' size=4 vlen=1\n"
> + "\t'm' type_id=1 bits_offset=0",
> + "[5] FUNC_PROTO '(anon)' ret_type_id=1 vlen=1\n"
> + "\t'p' type_id=2",
> + "[6] FUNC 'f' type_id=5 linkage=static");
> +
> + permute_ids[1 - start_id] = 4; /* [1] -> [4] */
> + permute_ids[2 - start_id] = 3; /* [2] -> [3] */
> + permute_ids[3 - start_id] = 5; /* [3] -> [5] */
> + permute_ids[4 - start_id] = 1; /* [4] -> [1] */
> + permute_ids[5 - start_id] = 6; /* [5] -> [6] */
> + permute_ids[6 - start_id] = 2; /* [6] -> [2] */
> + err = btf__permute(btf, permute_ids, ARRAY_SIZE(permute_ids), NULL);
> + if (!ASSERT_OK(err, "btf__permute_base"))
> + goto done;
> +
> + VALIDATE_RAW_BTF(
> + btf,
> + "[1] STRUCT 's2' size=4 vlen=1\n"
> + "\t'm' type_id=4 bits_offset=0",
> + "[2] FUNC 'f' type_id=6 linkage=static",
> + "[3] PTR '(anon)' type_id=4",
> + "[4] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED",
> + "[5] STRUCT 's1' size=4 vlen=1\n"
> + "\t'm' type_id=4 bits_offset=0",
> + "[6] FUNC_PROTO '(anon)' ret_type_id=4 vlen=1\n"
> + "\t'p' type_id=3");
> +
> + /*
> + * For base BTF, id_map_cnt must equal to the number of types
> + * include VOID type
> + */
> + permute_ids[1 - start_id] = 4; /* [1] -> [4] */
> + permute_ids[2 - start_id] = 3; /* [2] -> [3] */
> + permute_ids[3 - start_id] = 5; /* [3] -> [5] */
> + permute_ids[4 - start_id] = 1; /* [4] -> [1] */
> + permute_ids[5 - start_id] = 6; /* [5] -> [6] */
> + permute_ids[6 - start_id] = 2; /* [6] -> [2] */
> + err = btf__permute(btf, permute_ids, ARRAY_SIZE(permute_ids) - 1, NULL);
> + if (!ASSERT_ERR(err, "btf__permute_base"))
> + goto done;
> +
> + VALIDATE_RAW_BTF(
> + btf,
> + "[1] STRUCT 's2' size=4 vlen=1\n"
> + "\t'm' type_id=4 bits_offset=0",
> + "[2] FUNC 'f' type_id=6 linkage=static",
> + "[3] PTR '(anon)' type_id=4",
> + "[4] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED",
> + "[5] STRUCT 's1' size=4 vlen=1\n"
> + "\t'm' type_id=4 bits_offset=0",
> + "[6] FUNC_PROTO '(anon)' ret_type_id=4 vlen=1\n"
> + "\t'p' type_id=3");
> +
> + /* Multiple types can not be mapped to the same ID */
> + permute_ids[1 - start_id] = 4;
> + permute_ids[2 - start_id] = 4;
> + permute_ids[3 - start_id] = 5;
> + permute_ids[4 - start_id] = 1;
> + permute_ids[5 - start_id] = 6;
> + permute_ids[6 - start_id] = 2;
> + err = btf__permute(btf, permute_ids, ARRAY_SIZE(permute_ids), NULL);
> + if (!ASSERT_ERR(err, "btf__permute_base"))
> + goto done;
Nit: Maybe extract the VALIDATE_RAW_BTF as a function, so that it is
not repeated? Otherwise it is a bit harder to tell that you are
checking for BTF to be intact if error is returned.
Same for the test_permute_split() case.
> +
> + VALIDATE_RAW_BTF(
> + btf,
> + "[1] STRUCT 's2' size=4 vlen=1\n"
> + "\t'm' type_id=4 bits_offset=0",
> + "[2] FUNC 'f' type_id=6 linkage=static",
> + "[3] PTR '(anon)' type_id=4",
> + "[4] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED",
> + "[5] STRUCT 's1' size=4 vlen=1\n"
> + "\t'm' type_id=4 bits_offset=0",
> + "[6] FUNC_PROTO '(anon)' ret_type_id=4 vlen=1\n"
> + "\t'p' type_id=3");
[...]
^ permalink raw reply [flat|nested] 42+ messages in thread* Re: [RFC PATCH v7 2/7] selftests/bpf: Add test cases for btf__permute functionality
2025-11-20 23:39 ` Eduard Zingerman
@ 2025-11-21 14:17 ` Donglin Peng
0 siblings, 0 replies; 42+ messages in thread
From: Donglin Peng @ 2025-11-21 14:17 UTC (permalink / raw)
To: Eduard Zingerman
Cc: ast, andrii.nakryiko, zhangxiaoqin, linux-kernel, bpf,
Donglin Peng, Alan Maguire, Song Liu
On Fri, Nov 21, 2025 at 7:39 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Wed, 2025-11-19 at 11:15 +0800, Donglin Peng wrote:
>
> [...]
>
> > diff --git a/tools/testing/selftests/bpf/prog_tests/btf_permute.c b/tools/testing/selftests/bpf/prog_tests/btf_permute.c
> > new file mode 100644
> > index 000000000000..f67bf89519b3
> > --- /dev/null
> > +++ b/tools/testing/selftests/bpf/prog_tests/btf_permute.c
> > @@ -0,0 +1,608 @@
> > +// SPDX-License-Identifier: GPL-2.0
> > +/* Copyright (c) 2025 Xiaomi */
> > +
> > +#include <test_progs.h>
> > +#include <bpf/btf.h>
> > +#include "btf_helpers.h"
> > +
> > +/* Ensure btf__permute work as expected with base BTF */
> > +static void test_permute_base(void)
> > +{
> > + struct btf *btf;
> > + __u32 permute_ids[6];
> > + int start_id = 1;
> > + int err;
> > +
> > + btf = btf__new_empty();
> > + if (!ASSERT_OK_PTR(btf, "empty_main_btf"))
> > + return;
> > +
> > + btf__add_int(btf, "int", 4, BTF_INT_SIGNED); /* [1] int */
> > + btf__add_ptr(btf, 1); /* [2] ptr to int */
> > + btf__add_struct(btf, "s1", 4); /* [3] struct s1 { */
> > + btf__add_field(btf, "m", 1, 0, 0); /* int m; */
> > + /* } */
> > + btf__add_struct(btf, "s2", 4); /* [4] struct s2 { */
> > + btf__add_field(btf, "m", 1, 0, 0); /* int m; */
> > + /* } */
> > + btf__add_func_proto(btf, 1); /* [5] int (*)(int *p); */
> > + btf__add_func_param(btf, "p", 2);
> > + btf__add_func(btf, "f", BTF_FUNC_STATIC, 5); /* [6] int f(int *p); */
> > +
> > + VALIDATE_RAW_BTF(
> > + btf,
> > + "[1] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED",
> > + "[2] PTR '(anon)' type_id=1",
> > + "[3] STRUCT 's1' size=4 vlen=1\n"
> > + "\t'm' type_id=1 bits_offset=0",
> > + "[4] STRUCT 's2' size=4 vlen=1\n"
> > + "\t'm' type_id=1 bits_offset=0",
> > + "[5] FUNC_PROTO '(anon)' ret_type_id=1 vlen=1\n"
> > + "\t'p' type_id=2",
> > + "[6] FUNC 'f' type_id=5 linkage=static");
> > +
> > + permute_ids[1 - start_id] = 4; /* [1] -> [4] */
> > + permute_ids[2 - start_id] = 3; /* [2] -> [3] */
> > + permute_ids[3 - start_id] = 5; /* [3] -> [5] */
> > + permute_ids[4 - start_id] = 1; /* [4] -> [1] */
> > + permute_ids[5 - start_id] = 6; /* [5] -> [6] */
> > + permute_ids[6 - start_id] = 2; /* [6] -> [2] */
> > + err = btf__permute(btf, permute_ids, ARRAY_SIZE(permute_ids), NULL);
> > + if (!ASSERT_OK(err, "btf__permute_base"))
> > + goto done;
> > +
> > + VALIDATE_RAW_BTF(
> > + btf,
> > + "[1] STRUCT 's2' size=4 vlen=1\n"
> > + "\t'm' type_id=4 bits_offset=0",
> > + "[2] FUNC 'f' type_id=6 linkage=static",
> > + "[3] PTR '(anon)' type_id=4",
> > + "[4] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED",
> > + "[5] STRUCT 's1' size=4 vlen=1\n"
> > + "\t'm' type_id=4 bits_offset=0",
> > + "[6] FUNC_PROTO '(anon)' ret_type_id=4 vlen=1\n"
> > + "\t'p' type_id=3");
> > +
> > + /*
> > + * For base BTF, id_map_cnt must equal to the number of types
> > + * include VOID type
> > + */
> > + permute_ids[1 - start_id] = 4; /* [1] -> [4] */
> > + permute_ids[2 - start_id] = 3; /* [2] -> [3] */
> > + permute_ids[3 - start_id] = 5; /* [3] -> [5] */
> > + permute_ids[4 - start_id] = 1; /* [4] -> [1] */
> > + permute_ids[5 - start_id] = 6; /* [5] -> [6] */
> > + permute_ids[6 - start_id] = 2; /* [6] -> [2] */
> > + err = btf__permute(btf, permute_ids, ARRAY_SIZE(permute_ids) - 1, NULL);
> > + if (!ASSERT_ERR(err, "btf__permute_base"))
> > + goto done;
> > +
> > + VALIDATE_RAW_BTF(
> > + btf,
> > + "[1] STRUCT 's2' size=4 vlen=1\n"
> > + "\t'm' type_id=4 bits_offset=0",
> > + "[2] FUNC 'f' type_id=6 linkage=static",
> > + "[3] PTR '(anon)' type_id=4",
> > + "[4] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED",
> > + "[5] STRUCT 's1' size=4 vlen=1\n"
> > + "\t'm' type_id=4 bits_offset=0",
> > + "[6] FUNC_PROTO '(anon)' ret_type_id=4 vlen=1\n"
> > + "\t'p' type_id=3");
> > +
> > + /* Multiple types can not be mapped to the same ID */
> > + permute_ids[1 - start_id] = 4;
> > + permute_ids[2 - start_id] = 4;
> > + permute_ids[3 - start_id] = 5;
> > + permute_ids[4 - start_id] = 1;
> > + permute_ids[5 - start_id] = 6;
> > + permute_ids[6 - start_id] = 2;
> > + err = btf__permute(btf, permute_ids, ARRAY_SIZE(permute_ids), NULL);
> > + if (!ASSERT_ERR(err, "btf__permute_base"))
> > + goto done;
>
> Nit: Maybe extract the VALIDATE_RAW_BTF as a function, so that it is
> not repeated? Otherwise it is a bit harder to tell that you are
> checking for BTF to be intact if error is returned.
> Same for the test_permute_split() case.
Thanks, I will make it more clear.
>
> > +
> > + VALIDATE_RAW_BTF(
> > + btf,
> > + "[1] STRUCT 's2' size=4 vlen=1\n"
> > + "\t'm' type_id=4 bits_offset=0",
> > + "[2] FUNC 'f' type_id=6 linkage=static",
> > + "[3] PTR '(anon)' type_id=4",
> > + "[4] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED",
> > + "[5] STRUCT 's1' size=4 vlen=1\n"
> > + "\t'm' type_id=4 bits_offset=0",
> > + "[6] FUNC_PROTO '(anon)' ret_type_id=4 vlen=1\n"
> > + "\t'p' type_id=3");
>
> [...]
^ permalink raw reply [flat|nested] 42+ messages in thread
* Re: [RFC PATCH v7 2/7] selftests/bpf: Add test cases for btf__permute functionality
2025-11-19 3:15 ` [RFC PATCH v7 2/7] selftests/bpf: Add test cases for btf__permute functionality Donglin Peng
2025-11-19 4:51 ` Donglin Peng
2025-11-20 23:39 ` Eduard Zingerman
@ 2025-11-21 0:20 ` Eduard Zingerman
2 siblings, 0 replies; 42+ messages in thread
From: Eduard Zingerman @ 2025-11-21 0:20 UTC (permalink / raw)
To: Donglin Peng, ast, andrii.nakryiko
Cc: zhangxiaoqin, linux-kernel, bpf, Donglin Peng, Alan Maguire,
Song Liu
On Wed, 2025-11-19 at 11:15 +0800, Donglin Peng wrote:
> From: Donglin Peng <pengdonglin@xiaomi.com>
>
> This patch introduces test cases for the btf__permute function to ensure
> it works correctly with both base BTF and split BTF scenarios.
>
> The test suite includes:
> - test_permute_base: Validates permutation on base BTF
> - test_permute_split: Tests permutation on split BTF
> - test_permute_drop_base: Validates type dropping on base BTF
> - test_permute_drop_split: Tests type dropping on split BTF
> - test_permute_drop_dedup: Tests type dropping and deduping
>
> 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>
> Cc: Xiaoqin Zhang <zhangxiaoqin@xiaomi.com>
> Signed-off-by: Donglin Peng <pengdonglin@xiaomi.com>
> ---
Do we have an infrastructure for .btf_ext tests?
[...]
^ permalink raw reply [flat|nested] 42+ messages in thread
* [RFC PATCH v7 3/7] tools/resolve_btfids: Add --btf_sort option for BTF name sorting
2025-11-19 3:15 [RFC PATCH v7 0/7] Improve the performance of BTF type lookups with binary search Donglin Peng
2025-11-19 3:15 ` [RFC PATCH v7 1/7] libbpf: Add BTF permutation support for type reordering Donglin Peng
2025-11-19 3:15 ` [RFC PATCH v7 2/7] selftests/bpf: Add test cases for btf__permute functionality Donglin Peng
@ 2025-11-19 3:15 ` Donglin Peng
2025-11-20 21:34 ` Ihor Solodrai
2025-11-21 0:18 ` Eduard Zingerman
2025-11-19 3:15 ` [RFC PATCH v7 4/7] libbpf: Optimize type lookup with binary search for sorted BTF Donglin Peng
` (3 subsequent siblings)
6 siblings, 2 replies; 42+ messages in thread
From: Donglin Peng @ 2025-11-19 3:15 UTC (permalink / raw)
To: ast, andrii.nakryiko
Cc: eddyz87, zhangxiaoqin, linux-kernel, bpf, Donglin Peng,
Alan Maguire, Song Liu
From: Donglin Peng <pengdonglin@xiaomi.com>
This patch introduces a new --btf_sort option that leverages libbpf's
btf__permute interface to reorganize BTF layout. The implementation
sorts BTF types by name in ascending order, placing anonymous types at
the end to enable efficient binary search lookup.
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>
Cc: Xiaoqin Zhang <zhangxiaoqin@xiaomi.com>
Signed-off-by: Donglin Peng <pengdonglin@xiaomi.com>
---
scripts/Makefile.btf | 2 +
scripts/Makefile.modfinal | 1 +
scripts/link-vmlinux.sh | 1 +
tools/bpf/resolve_btfids/main.c | 200 ++++++++++++++++++++++++++++++++
4 files changed, 204 insertions(+)
diff --git a/scripts/Makefile.btf b/scripts/Makefile.btf
index db76335dd917..d5eb4ee70e88 100644
--- a/scripts/Makefile.btf
+++ b/scripts/Makefile.btf
@@ -27,6 +27,7 @@ pahole-flags-$(call test-ge, $(pahole-ver), 130) += --btf_features=attributes
ifneq ($(KBUILD_EXTMOD),)
module-pahole-flags-$(call test-ge, $(pahole-ver), 128) += --btf_features=distilled_base
+module-resolve_btfid-flags-y = --distilled_base
endif
endif
@@ -35,3 +36,4 @@ pahole-flags-$(CONFIG_PAHOLE_HAS_LANG_EXCLUDE) += --lang_exclude=rust
export PAHOLE_FLAGS := $(pahole-flags-y)
export MODULE_PAHOLE_FLAGS := $(module-pahole-flags-y)
+export MODULE_RESOLVE_BTFID_FLAGS := $(module-resolve_btfid-flags-y)
diff --git a/scripts/Makefile.modfinal b/scripts/Makefile.modfinal
index 542ba462ed3e..4481dda2f485 100644
--- a/scripts/Makefile.modfinal
+++ b/scripts/Makefile.modfinal
@@ -40,6 +40,7 @@ quiet_cmd_btf_ko = BTF [M] $@
printf "Skipping BTF generation for %s due to unavailability of vmlinux\n" $@ 1>&2; \
else \
LLVM_OBJCOPY="$(OBJCOPY)" $(PAHOLE) -J $(PAHOLE_FLAGS) $(MODULE_PAHOLE_FLAGS) --btf_base $(objtree)/vmlinux $@; \
+ $(RESOLVE_BTFIDS) -b $(objtree)/vmlinux $(MODULE_RESOLVE_BTFID_FLAGS) --btf_sort $@; \
$(RESOLVE_BTFIDS) -b $(objtree)/vmlinux $@; \
fi;
diff --git a/scripts/link-vmlinux.sh b/scripts/link-vmlinux.sh
index 433849ff7529..f21f6300815b 100755
--- a/scripts/link-vmlinux.sh
+++ b/scripts/link-vmlinux.sh
@@ -288,6 +288,7 @@ if is_enabled CONFIG_DEBUG_INFO_BTF; then
if is_enabled CONFIG_WERROR; then
RESOLVE_BTFIDS_ARGS=" --fatal_warnings "
fi
+ ${RESOLVE_BTFIDS} ${RESOLVE_BTFIDS_ARGS} --btf_sort "${VMLINUX}"
${RESOLVE_BTFIDS} ${RESOLVE_BTFIDS_ARGS} "${VMLINUX}"
fi
diff --git a/tools/bpf/resolve_btfids/main.c b/tools/bpf/resolve_btfids/main.c
index d47191c6e55e..dc0badd6f375 100644
--- a/tools/bpf/resolve_btfids/main.c
+++ b/tools/bpf/resolve_btfids/main.c
@@ -768,6 +768,195 @@ static int symbols_patch(struct object *obj)
return err < 0 ? -1 : 0;
}
+/* Anonymous types (with empty names) are considered greater than named types
+ * and are sorted after them. Two anonymous types are considered equal. Named
+ * types are compared lexicographically.
+ */
+static int cmp_type_names(const void *a, const void *b, void *priv)
+{
+ struct btf *btf = (struct btf *)priv;
+ const struct btf_type *ta = btf__type_by_id(btf, *(__u32 *)a);
+ const struct btf_type *tb = btf__type_by_id(btf, *(__u32 *)b);
+ const char *na, *nb;
+
+ if (!ta->name_off && tb->name_off)
+ return 1;
+ if (ta->name_off && !tb->name_off)
+ return -1;
+ if (!ta->name_off && !tb->name_off)
+ return 0;
+
+ na = btf__str_by_offset(btf, ta->name_off);
+ nb = btf__str_by_offset(btf, tb->name_off);
+ return strcmp(na, nb);
+}
+
+static int update_btf_section(const char *path, const struct btf *btf,
+ const char *btf_secname)
+{
+ GElf_Shdr shdr_mem, *shdr;
+ Elf_Data *btf_data = NULL;
+ Elf_Scn *scn = NULL;
+ Elf *elf = NULL;
+ const void *raw_btf_data;
+ uint32_t raw_btf_size;
+ int fd, err = -1;
+ size_t strndx;
+
+ fd = open(path, O_RDWR);
+ if (fd < 0) {
+ pr_err("FAILED to open %s\n", path);
+ return -1;
+ }
+
+ if (elf_version(EV_CURRENT) == EV_NONE) {
+ pr_err("FAILED to set libelf version");
+ goto out;
+ }
+
+ elf = elf_begin(fd, ELF_C_RDWR, NULL);
+ if (elf == NULL) {
+ pr_err("FAILED to update ELF file");
+ goto out;
+ }
+
+ elf_flagelf(elf, ELF_C_SET, ELF_F_LAYOUT);
+
+ elf_getshdrstrndx(elf, &strndx);
+ while ((scn = elf_nextscn(elf, scn)) != NULL) {
+ char *secname;
+
+ shdr = gelf_getshdr(scn, &shdr_mem);
+ if (shdr == NULL)
+ continue;
+ secname = elf_strptr(elf, strndx, shdr->sh_name);
+ if (strcmp(secname, btf_secname) == 0) {
+ btf_data = elf_getdata(scn, btf_data);
+ break;
+ }
+ }
+
+ raw_btf_data = btf__raw_data(btf, &raw_btf_size);
+
+ if (btf_data) {
+ if (raw_btf_size != btf_data->d_size) {
+ pr_err("FAILED: size mismatch");
+ goto out;
+ }
+
+ btf_data->d_buf = (void *)raw_btf_data;
+ btf_data->d_type = ELF_T_WORD;
+ elf_flagdata(btf_data, ELF_C_SET, ELF_F_DIRTY);
+
+ if (elf_update(elf, ELF_C_WRITE) >= 0)
+ err = 0;
+ }
+
+out:
+ if (fd != -1)
+ close(fd);
+ if (elf)
+ elf_end(elf);
+ return err;
+}
+
+static int sort_update_btf(struct object *obj, bool distilled_base)
+{
+ struct btf *base_btf = NULL;
+ struct btf *btf = NULL;
+ int start_id = 1, nr_types, id;
+ int err = 0, i;
+ __u32 *permute_ids = NULL, *id_map = NULL, btf_size;
+ const void *btf_data;
+ int fd;
+
+ if (obj->base_btf_path) {
+ base_btf = btf__parse(obj->base_btf_path, NULL);
+ err = libbpf_get_error(base_btf);
+ if (err) {
+ pr_err("FAILED: load base BTF from %s: %s\n",
+ obj->base_btf_path, strerror(-err));
+ return -1;
+ }
+ }
+
+ btf = btf__parse_elf_split(obj->path, base_btf);
+ err = libbpf_get_error(btf);
+ if (err) {
+ pr_err("FAILED: load BTF from %s: %s\n", obj->path, strerror(-err));
+ goto out;
+ }
+
+ if (base_btf)
+ start_id = btf__type_cnt(base_btf);
+ nr_types = btf__type_cnt(btf) - start_id;
+ if (nr_types < 2)
+ goto out;
+
+ permute_ids = calloc(nr_types, sizeof(*permute_ids));
+ if (!permute_ids) {
+ err = -ENOMEM;
+ goto out;
+ }
+
+ id_map = calloc(nr_types, sizeof(*id_map));
+ if (!id_map) {
+ err = -ENOMEM;
+ goto out;
+ }
+
+ for (i = 0, id = start_id; i < nr_types; i++, id++)
+ permute_ids[i] = id;
+
+ qsort_r(permute_ids, nr_types, sizeof(*permute_ids), cmp_type_names, btf);
+
+ for (i = 0; i < nr_types; i++) {
+ id = permute_ids[i] - start_id;
+ id_map[id] = i + start_id;
+ }
+
+ err = btf__permute(btf, id_map, nr_types, NULL);
+ if (err) {
+ pr_err("FAILED: btf permute: %s\n", strerror(-err));
+ goto out;
+ }
+
+ if (distilled_base) {
+ struct btf *new_btf = NULL, *distilled_base = NULL;
+
+ if (btf__distill_base(btf, &distilled_base, &new_btf) < 0) {
+ pr_err("FAILED to generate distilled base BTF: %s\n",
+ strerror(errno));
+ goto out;
+ }
+
+ err = update_btf_section(obj->path, new_btf, BTF_ELF_SEC);
+ if (!err) {
+ err = update_btf_section(obj->path, distilled_base, BTF_BASE_ELF_SEC);
+ if (err < 0)
+ pr_err("FAILED to update '%s'\n", BTF_BASE_ELF_SEC);
+ } else {
+ pr_err("FAILED to update '%s'\n", BTF_ELF_SEC);
+ }
+
+ btf__free(new_btf);
+ btf__free(distilled_base);
+ } else {
+ err = update_btf_section(obj->path, btf, BTF_ELF_SEC);
+ if (err < 0) {
+ pr_err("FAILED to update '%s'\n", BTF_ELF_SEC);
+ goto out;
+ }
+ }
+
+out:
+ free(permute_ids);
+ free(id_map);
+ btf__free(base_btf);
+ btf__free(btf);
+ return err;
+}
+
static const char * const resolve_btfids_usage[] = {
"resolve_btfids [<options>] <ELF object>",
NULL
@@ -787,6 +976,8 @@ int main(int argc, const char **argv)
.sets = RB_ROOT,
};
bool fatal_warnings = false;
+ bool btf_sort = false;
+ bool distilled_base = false;
struct option btfid_options[] = {
OPT_INCR('v', "verbose", &verbose,
"be more verbose (show errors, etc)"),
@@ -796,6 +987,10 @@ int main(int argc, const char **argv)
"path of file providing base BTF"),
OPT_BOOLEAN(0, "fatal_warnings", &fatal_warnings,
"turn warnings into errors"),
+ OPT_BOOLEAN(0, "btf_sort", &btf_sort,
+ "sort BTF by name in ascending order"),
+ OPT_BOOLEAN(0, "distilled_base", &distilled_base,
+ "distill base"),
OPT_END()
};
int err = -1;
@@ -807,6 +1002,11 @@ int main(int argc, const char **argv)
obj.path = argv[0];
+ if (btf_sort) {
+ err = sort_update_btf(&obj, distilled_base);
+ goto out;
+ }
+
if (elf_collect(&obj))
goto out;
--
2.34.1
^ permalink raw reply related [flat|nested] 42+ messages in thread* Re: [RFC PATCH v7 3/7] tools/resolve_btfids: Add --btf_sort option for BTF name sorting
2025-11-19 3:15 ` [RFC PATCH v7 3/7] tools/resolve_btfids: Add --btf_sort option for BTF name sorting Donglin Peng
@ 2025-11-20 21:34 ` Ihor Solodrai
2025-11-20 23:53 ` Ihor Solodrai
2025-11-21 15:36 ` Donglin Peng
2025-11-21 0:18 ` Eduard Zingerman
1 sibling, 2 replies; 42+ messages in thread
From: Ihor Solodrai @ 2025-11-20 21:34 UTC (permalink / raw)
To: Donglin Peng, ast, andrii.nakryiko
Cc: eddyz87, zhangxiaoqin, linux-kernel, bpf, Donglin Peng,
Alan Maguire, Song Liu
On 11/18/25 7:15 PM, Donglin Peng wrote:
> From: Donglin Peng <pengdonglin@xiaomi.com>
>
> This patch introduces a new --btf_sort option that leverages libbpf's
> btf__permute interface to reorganize BTF layout. The implementation
> sorts BTF types by name in ascending order, placing anonymous types at
> the end to enable efficient binary search lookup.
>
> 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>
> Cc: Xiaoqin Zhang <zhangxiaoqin@xiaomi.com>
> Signed-off-by: Donglin Peng <pengdonglin@xiaomi.com>
> ---
> scripts/Makefile.btf | 2 +
> scripts/Makefile.modfinal | 1 +
> scripts/link-vmlinux.sh | 1 +
> tools/bpf/resolve_btfids/main.c | 200 ++++++++++++++++++++++++++++++++
> 4 files changed, 204 insertions(+)
>
> diff --git a/scripts/Makefile.btf b/scripts/Makefile.btf
> index db76335dd917..d5eb4ee70e88 100644
> --- a/scripts/Makefile.btf
> +++ b/scripts/Makefile.btf
> @@ -27,6 +27,7 @@ pahole-flags-$(call test-ge, $(pahole-ver), 130) += --btf_features=attributes
>
> ifneq ($(KBUILD_EXTMOD),)
> module-pahole-flags-$(call test-ge, $(pahole-ver), 128) += --btf_features=distilled_base
> +module-resolve_btfid-flags-y = --distilled_base
> endif
>
> endif
> @@ -35,3 +36,4 @@ pahole-flags-$(CONFIG_PAHOLE_HAS_LANG_EXCLUDE) += --lang_exclude=rust
>
> export PAHOLE_FLAGS := $(pahole-flags-y)
> export MODULE_PAHOLE_FLAGS := $(module-pahole-flags-y)
> +export MODULE_RESOLVE_BTFID_FLAGS := $(module-resolve_btfid-flags-y)
> diff --git a/scripts/Makefile.modfinal b/scripts/Makefile.modfinal
> index 542ba462ed3e..4481dda2f485 100644
> --- a/scripts/Makefile.modfinal
> +++ b/scripts/Makefile.modfinal
> @@ -40,6 +40,7 @@ quiet_cmd_btf_ko = BTF [M] $@
> printf "Skipping BTF generation for %s due to unavailability of vmlinux\n" $@ 1>&2; \
> else \
> LLVM_OBJCOPY="$(OBJCOPY)" $(PAHOLE) -J $(PAHOLE_FLAGS) $(MODULE_PAHOLE_FLAGS) --btf_base $(objtree)/vmlinux $@; \
> + $(RESOLVE_BTFIDS) -b $(objtree)/vmlinux $(MODULE_RESOLVE_BTFID_FLAGS) --btf_sort $@; \
> $(RESOLVE_BTFIDS) -b $(objtree)/vmlinux $@; \
> fi;
>
> diff --git a/scripts/link-vmlinux.sh b/scripts/link-vmlinux.sh
> index 433849ff7529..f21f6300815b 100755
> --- a/scripts/link-vmlinux.sh
> +++ b/scripts/link-vmlinux.sh
> @@ -288,6 +288,7 @@ if is_enabled CONFIG_DEBUG_INFO_BTF; then
> if is_enabled CONFIG_WERROR; then
> RESOLVE_BTFIDS_ARGS=" --fatal_warnings "
> fi
> + ${RESOLVE_BTFIDS} ${RESOLVE_BTFIDS_ARGS} --btf_sort "${VMLINUX}"
> ${RESOLVE_BTFIDS} ${RESOLVE_BTFIDS_ARGS} "${VMLINUX}"
> fi
>
> diff --git a/tools/bpf/resolve_btfids/main.c b/tools/bpf/resolve_btfids/main.c
> index d47191c6e55e..dc0badd6f375 100644
> --- a/tools/bpf/resolve_btfids/main.c
> +++ b/tools/bpf/resolve_btfids/main.c
> @@ -768,6 +768,195 @@ static int symbols_patch(struct object *obj)
> return err < 0 ? -1 : 0;
> }
>
> +/* Anonymous types (with empty names) are considered greater than named types
> + * and are sorted after them. Two anonymous types are considered equal. Named
> + * types are compared lexicographically.
> + */
> +static int cmp_type_names(const void *a, const void *b, void *priv)
> +{
> + struct btf *btf = (struct btf *)priv;
> + const struct btf_type *ta = btf__type_by_id(btf, *(__u32 *)a);
> + const struct btf_type *tb = btf__type_by_id(btf, *(__u32 *)b);
> + const char *na, *nb;
> +
> + if (!ta->name_off && tb->name_off)
> + return 1;
> + if (ta->name_off && !tb->name_off)
> + return -1;
> + if (!ta->name_off && !tb->name_off)
> + return 0;
> +
> + na = btf__str_by_offset(btf, ta->name_off);
> + nb = btf__str_by_offset(btf, tb->name_off);
> + return strcmp(na, nb);
> +}
> +
> +static int update_btf_section(const char *path, const struct btf *btf,
Hi Dongling.
Thanks for working on this, it's a great optimization. Just want to
give you a heads up that I am preparing a patchset changing
resolve_btfids behavior.
In particular, instead of updating the .BTF_ids section (and now with
your and upcoming changes the .BTF section) *in-place*, resolve_btfids
will only emit the data for the sections. And then it'll be integrated
into vmlinux with objcopy and linker. We already do a similar thing
with .BTF for vmlinux [1].
For your patchset it means that the parts handling ELF update will be
unnecessary.
Also I think the --btf_sort flag is unnecessary. We probably want
kernel BTF to always be sorted in this way. And if resolve_btfids will
be handling more btf2btf transformation, we should avoid adding a
flags for every one of them.
[1] https://git.kernel.org/pub/scm/linux/kernel/git/bpf/bpf-next.git/tree/scripts/link-vmlinux.sh#n110
> + const char *btf_secname)
> +{
> + GElf_Shdr shdr_mem, *shdr;
> + Elf_Data *btf_data = NULL;
> + Elf_Scn *scn = NULL;
> + Elf *elf = NULL;
> + const void *raw_btf_data;
> + uint32_t raw_btf_size;
> + int fd, err = -1;
> + size_t strndx;
> +
> + fd = open(path, O_RDWR);
> + if (fd < 0) {
> + pr_err("FAILED to open %s\n", path);
> + return -1;
> + }
> +
> + if (elf_version(EV_CURRENT) == EV_NONE) {
> + pr_err("FAILED to set libelf version");
> + goto out;
> + }
> +
> + elf = elf_begin(fd, ELF_C_RDWR, NULL);
> + if (elf == NULL) {
> + pr_err("FAILED to update ELF file");
> + goto out;
> + }
> +
> + elf_flagelf(elf, ELF_C_SET, ELF_F_LAYOUT);
> +
> + elf_getshdrstrndx(elf, &strndx);
> + while ((scn = elf_nextscn(elf, scn)) != NULL) {
> + char *secname;
> +
> + shdr = gelf_getshdr(scn, &shdr_mem);
> + if (shdr == NULL)
> + continue;
> + secname = elf_strptr(elf, strndx, shdr->sh_name);
> + if (strcmp(secname, btf_secname) == 0) {
> + btf_data = elf_getdata(scn, btf_data);
> + break;
> + }
> + }
> +
> + raw_btf_data = btf__raw_data(btf, &raw_btf_size);
> +
> + if (btf_data) {
> + if (raw_btf_size != btf_data->d_size) {
> + pr_err("FAILED: size mismatch");
> + goto out;
> + }
> +
> + btf_data->d_buf = (void *)raw_btf_data;
> + btf_data->d_type = ELF_T_WORD;
> + elf_flagdata(btf_data, ELF_C_SET, ELF_F_DIRTY);
> +
> + if (elf_update(elf, ELF_C_WRITE) >= 0)
> + err = 0;
> + }
> +
> +out:
> + if (fd != -1)
> + close(fd);
> + if (elf)
> + elf_end(elf);
> + return err;
> +}
> +
> +static int sort_update_btf(struct object *obj, bool distilled_base)
> +{
> + struct btf *base_btf = NULL;
> + struct btf *btf = NULL;
> + int start_id = 1, nr_types, id;
> + int err = 0, i;
> + __u32 *permute_ids = NULL, *id_map = NULL, btf_size;
> + const void *btf_data;
> + int fd;
> +
> + if (obj->base_btf_path) {
> + base_btf = btf__parse(obj->base_btf_path, NULL);
> + err = libbpf_get_error(base_btf);
> + if (err) {
> + pr_err("FAILED: load base BTF from %s: %s\n",
> + obj->base_btf_path, strerror(-err));
> + return -1;
> + }
> + }
> +
> + btf = btf__parse_elf_split(obj->path, base_btf);
> + err = libbpf_get_error(btf);
> + if (err) {
> + pr_err("FAILED: load BTF from %s: %s\n", obj->path, strerror(-err));
> + goto out;
> + }
> +
> + if (base_btf)
> + start_id = btf__type_cnt(base_btf);
> + nr_types = btf__type_cnt(btf) - start_id;
> + if (nr_types < 2)
> + goto out;
> +
> + permute_ids = calloc(nr_types, sizeof(*permute_ids));
> + if (!permute_ids) {
> + err = -ENOMEM;
> + goto out;
> + }
> +
> + id_map = calloc(nr_types, sizeof(*id_map));
> + if (!id_map) {
> + err = -ENOMEM;
> + goto out;
> + }
> +
> + for (i = 0, id = start_id; i < nr_types; i++, id++)
> + permute_ids[i] = id;
> +
> + qsort_r(permute_ids, nr_types, sizeof(*permute_ids), cmp_type_names, btf);
> +
> + for (i = 0; i < nr_types; i++) {
> + id = permute_ids[i] - start_id;
> + id_map[id] = i + start_id;
> + }
> +
> + err = btf__permute(btf, id_map, nr_types, NULL);
> + if (err) {
> + pr_err("FAILED: btf permute: %s\n", strerror(-err));
> + goto out;
> + }
> +
> + if (distilled_base) {
> + struct btf *new_btf = NULL, *distilled_base = NULL;
> +
> + if (btf__distill_base(btf, &distilled_base, &new_btf) < 0) {
> + pr_err("FAILED to generate distilled base BTF: %s\n",
> + strerror(errno));
> + goto out;
> + }
> +
> + err = update_btf_section(obj->path, new_btf, BTF_ELF_SEC);
> + if (!err) {
> + err = update_btf_section(obj->path, distilled_base, BTF_BASE_ELF_SEC);
> + if (err < 0)
> + pr_err("FAILED to update '%s'\n", BTF_BASE_ELF_SEC);
> + } else {
> + pr_err("FAILED to update '%s'\n", BTF_ELF_SEC);
> + }
> +
> + btf__free(new_btf);
> + btf__free(distilled_base);
> + } else {
> + err = update_btf_section(obj->path, btf, BTF_ELF_SEC);
> + if (err < 0) {
> + pr_err("FAILED to update '%s'\n", BTF_ELF_SEC);
> + goto out;
> + }
> + }
> +
> +out:
> + free(permute_ids);
> + free(id_map);
> + btf__free(base_btf);
> + btf__free(btf);
> + return err;
> +}
> +
> static const char * const resolve_btfids_usage[] = {
> "resolve_btfids [<options>] <ELF object>",
> NULL
> @@ -787,6 +976,8 @@ int main(int argc, const char **argv)
> .sets = RB_ROOT,
> };
> bool fatal_warnings = false;
> + bool btf_sort = false;
> + bool distilled_base = false;
> struct option btfid_options[] = {
> OPT_INCR('v', "verbose", &verbose,
> "be more verbose (show errors, etc)"),
> @@ -796,6 +987,10 @@ int main(int argc, const char **argv)
> "path of file providing base BTF"),
> OPT_BOOLEAN(0, "fatal_warnings", &fatal_warnings,
> "turn warnings into errors"),
> + OPT_BOOLEAN(0, "btf_sort", &btf_sort,
> + "sort BTF by name in ascending order"),
> + OPT_BOOLEAN(0, "distilled_base", &distilled_base,
> + "distill base"),
> OPT_END()
> };
> int err = -1;
> @@ -807,6 +1002,11 @@ int main(int argc, const char **argv)
>
> obj.path = argv[0];
>
> + if (btf_sort) {
> + err = sort_update_btf(&obj, distilled_base);
> + goto out;
> + }
> +
> if (elf_collect(&obj))
> goto out;
>
^ permalink raw reply [flat|nested] 42+ messages in thread* Re: [RFC PATCH v7 3/7] tools/resolve_btfids: Add --btf_sort option for BTF name sorting
2025-11-20 21:34 ` Ihor Solodrai
@ 2025-11-20 23:53 ` Ihor Solodrai
2025-11-21 15:36 ` Donglin Peng
1 sibling, 0 replies; 42+ messages in thread
From: Ihor Solodrai @ 2025-11-20 23:53 UTC (permalink / raw)
To: Donglin Peng, ast, andrii.nakryiko, eddyz87
Cc: zhangxiaoqin, linux-kernel, bpf, Donglin Peng, Alan Maguire,
Song Liu
On 11/20/25 1:34 PM, Ihor Solodrai wrote:
> On 11/18/25 7:15 PM, Donglin Peng wrote:
>> From: Donglin Peng <pengdonglin@xiaomi.com>
>>
>> This patch introduces a new --btf_sort option that leverages libbpf's
>> btf__permute interface to reorganize BTF layout. The implementation
>> sorts BTF types by name in ascending order, placing anonymous types at
>> the end to enable efficient binary search lookup.
>>
>> [...]
>>
>> +}
>> +
>> +static int update_btf_section(const char *path, const struct btf *btf,
>
> Hi Dongling.
>
> Thanks for working on this, it's a great optimization. Just want to
> give you a heads up that I am preparing a patchset changing
> resolve_btfids behavior.
>
> In particular, instead of updating the .BTF_ids section (and now with
> your and upcoming changes the .BTF section) *in-place*, resolve_btfids
> will only emit the data for the sections. And then it'll be integrated
> into vmlinux with objcopy and linker. We already do a similar thing
> with .BTF for vmlinux [1].
>
> For your patchset it means that the parts handling ELF update will be
> unnecessary.
>
> Also I think the --btf_sort flag is unnecessary. We probably want
> kernel BTF to always be sorted in this way. And if resolve_btfids will
> be handling more btf2btf transformation, we should avoid adding a
> flags for every one of them.
The same applies to --distilled_base.
AFAIU we always want to do it, so there is not need for the
flag. Unless there is a strong use case for generating module BTF
*without* the distilled base that I am not aware of.
Maybe an explicit "--kmodule" flag would be appropriate?..
For resolve_btfids, is it reasonable to assume it's a module if --base
is passed in?
Andrii, Eduard, wdyt?
>
> [1] https://git.kernel.org/pub/scm/linux/kernel/git/bpf/bpf-next.git/tree/scripts/link-vmlinux.sh#n110
>
>
^ permalink raw reply [flat|nested] 42+ messages in thread
* Re: [RFC PATCH v7 3/7] tools/resolve_btfids: Add --btf_sort option for BTF name sorting
2025-11-20 21:34 ` Ihor Solodrai
2025-11-20 23:53 ` Ihor Solodrai
@ 2025-11-21 15:36 ` Donglin Peng
2025-11-24 19:35 ` Ihor Solodrai
1 sibling, 1 reply; 42+ messages in thread
From: Donglin Peng @ 2025-11-21 15:36 UTC (permalink / raw)
To: Ihor Solodrai
Cc: ast, andrii.nakryiko, eddyz87, zhangxiaoqin, linux-kernel, bpf,
Donglin Peng, Alan Maguire, Song Liu
On Fri, Nov 21, 2025 at 5:34 AM Ihor Solodrai <ihor.solodrai@linux.dev> wrote:
>
> On 11/18/25 7:15 PM, Donglin Peng wrote:
> > From: Donglin Peng <pengdonglin@xiaomi.com>
> >
> > This patch introduces a new --btf_sort option that leverages libbpf's
> > btf__permute interface to reorganize BTF layout. The implementation
> > sorts BTF types by name in ascending order, placing anonymous types at
> > the end to enable efficient binary search lookup.
> >
> > 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>
> > Cc: Xiaoqin Zhang <zhangxiaoqin@xiaomi.com>
> > Signed-off-by: Donglin Peng <pengdonglin@xiaomi.com>
> > ---
> > scripts/Makefile.btf | 2 +
> > scripts/Makefile.modfinal | 1 +
> > scripts/link-vmlinux.sh | 1 +
> > tools/bpf/resolve_btfids/main.c | 200 ++++++++++++++++++++++++++++++++
> > 4 files changed, 204 insertions(+)
> >
> > diff --git a/scripts/Makefile.btf b/scripts/Makefile.btf
> > index db76335dd917..d5eb4ee70e88 100644
> > --- a/scripts/Makefile.btf
> > +++ b/scripts/Makefile.btf
> > @@ -27,6 +27,7 @@ pahole-flags-$(call test-ge, $(pahole-ver), 130) += --btf_features=attributes
> >
> > ifneq ($(KBUILD_EXTMOD),)
> > module-pahole-flags-$(call test-ge, $(pahole-ver), 128) += --btf_features=distilled_base
> > +module-resolve_btfid-flags-y = --distilled_base
> > endif
> >
> > endif
> > @@ -35,3 +36,4 @@ pahole-flags-$(CONFIG_PAHOLE_HAS_LANG_EXCLUDE) += --lang_exclude=rust
> >
> > export PAHOLE_FLAGS := $(pahole-flags-y)
> > export MODULE_PAHOLE_FLAGS := $(module-pahole-flags-y)
> > +export MODULE_RESOLVE_BTFID_FLAGS := $(module-resolve_btfid-flags-y)
> > diff --git a/scripts/Makefile.modfinal b/scripts/Makefile.modfinal
> > index 542ba462ed3e..4481dda2f485 100644
> > --- a/scripts/Makefile.modfinal
> > +++ b/scripts/Makefile.modfinal
> > @@ -40,6 +40,7 @@ quiet_cmd_btf_ko = BTF [M] $@
> > printf "Skipping BTF generation for %s due to unavailability of vmlinux\n" $@ 1>&2; \
> > else \
> > LLVM_OBJCOPY="$(OBJCOPY)" $(PAHOLE) -J $(PAHOLE_FLAGS) $(MODULE_PAHOLE_FLAGS) --btf_base $(objtree)/vmlinux $@; \
> > + $(RESOLVE_BTFIDS) -b $(objtree)/vmlinux $(MODULE_RESOLVE_BTFID_FLAGS) --btf_sort $@; \
> > $(RESOLVE_BTFIDS) -b $(objtree)/vmlinux $@; \
> > fi;
> >
> > diff --git a/scripts/link-vmlinux.sh b/scripts/link-vmlinux.sh
> > index 433849ff7529..f21f6300815b 100755
> > --- a/scripts/link-vmlinux.sh
> > +++ b/scripts/link-vmlinux.sh
> > @@ -288,6 +288,7 @@ if is_enabled CONFIG_DEBUG_INFO_BTF; then
> > if is_enabled CONFIG_WERROR; then
> > RESOLVE_BTFIDS_ARGS=" --fatal_warnings "
> > fi
> > + ${RESOLVE_BTFIDS} ${RESOLVE_BTFIDS_ARGS} --btf_sort "${VMLINUX}"
> > ${RESOLVE_BTFIDS} ${RESOLVE_BTFIDS_ARGS} "${VMLINUX}"
> > fi
> >
> > diff --git a/tools/bpf/resolve_btfids/main.c b/tools/bpf/resolve_btfids/main.c
> > index d47191c6e55e..dc0badd6f375 100644
> > --- a/tools/bpf/resolve_btfids/main.c
> > +++ b/tools/bpf/resolve_btfids/main.c
> > @@ -768,6 +768,195 @@ static int symbols_patch(struct object *obj)
> > return err < 0 ? -1 : 0;
> > }
> >
> > +/* Anonymous types (with empty names) are considered greater than named types
> > + * and are sorted after them. Two anonymous types are considered equal. Named
> > + * types are compared lexicographically.
> > + */
> > +static int cmp_type_names(const void *a, const void *b, void *priv)
> > +{
> > + struct btf *btf = (struct btf *)priv;
> > + const struct btf_type *ta = btf__type_by_id(btf, *(__u32 *)a);
> > + const struct btf_type *tb = btf__type_by_id(btf, *(__u32 *)b);
> > + const char *na, *nb;
> > +
> > + if (!ta->name_off && tb->name_off)
> > + return 1;
> > + if (ta->name_off && !tb->name_off)
> > + return -1;
> > + if (!ta->name_off && !tb->name_off)
> > + return 0;
> > +
> > + na = btf__str_by_offset(btf, ta->name_off);
> > + nb = btf__str_by_offset(btf, tb->name_off);
> > + return strcmp(na, nb);
> > +}
> > +
> > +static int update_btf_section(const char *path, const struct btf *btf,
>
> Hi Dongling.
>
> Thanks for working on this, it's a great optimization. Just want to
> give you a heads up that I am preparing a patchset changing
> resolve_btfids behavior.
Thanks. I'm curious about the new behavior of resolve_btfids. Does it
replace pahole and generate the sorted .BTF data directly from the
DWARF data? Also, does its sorting method differ from the cmp_type_names
approach mentioned above — specifically, does it place named types
before all anonymous types? I'm asking because the search method
needs to be compatible with this sorting approach.
>
> In particular, instead of updating the .BTF_ids section (and now with
> your and upcoming changes the .BTF section) *in-place*, resolve_btfids
> will only emit the data for the sections. And then it'll be integrated
> into vmlinux with objcopy and linker. We already do a similar thing
> with .BTF for vmlinux [1].
>
> For your patchset it means that the parts handling ELF update will be
> unnecessary.
>
> Also I think the --btf_sort flag is unnecessary. We probably want
> kernel BTF to always be sorted in this way. And if resolve_btfids will
> be handling more btf2btf transformation, we should avoid adding a
> flags for every one of them.
>
> [1] https://git.kernel.org/pub/scm/linux/kernel/git/bpf/bpf-next.git/tree/scripts/link-vmlinux.sh#n110
>
>
> > + const char *btf_secname)
> > +{
> > + GElf_Shdr shdr_mem, *shdr;
> > + Elf_Data *btf_data = NULL;
> > + Elf_Scn *scn = NULL;
> > + Elf *elf = NULL;
> > + const void *raw_btf_data;
> > + uint32_t raw_btf_size;
> > + int fd, err = -1;
> > + size_t strndx;
> > +
> > + fd = open(path, O_RDWR);
> > + if (fd < 0) {
> > + pr_err("FAILED to open %s\n", path);
> > + return -1;
> > + }
> > +
> > + if (elf_version(EV_CURRENT) == EV_NONE) {
> > + pr_err("FAILED to set libelf version");
> > + goto out;
> > + }
> > +
> > + elf = elf_begin(fd, ELF_C_RDWR, NULL);
> > + if (elf == NULL) {
> > + pr_err("FAILED to update ELF file");
> > + goto out;
> > + }
> > +
> > + elf_flagelf(elf, ELF_C_SET, ELF_F_LAYOUT);
> > +
> > + elf_getshdrstrndx(elf, &strndx);
> > + while ((scn = elf_nextscn(elf, scn)) != NULL) {
> > + char *secname;
> > +
> > + shdr = gelf_getshdr(scn, &shdr_mem);
> > + if (shdr == NULL)
> > + continue;
> > + secname = elf_strptr(elf, strndx, shdr->sh_name);
> > + if (strcmp(secname, btf_secname) == 0) {
> > + btf_data = elf_getdata(scn, btf_data);
> > + break;
> > + }
> > + }
> > +
> > + raw_btf_data = btf__raw_data(btf, &raw_btf_size);
> > +
> > + if (btf_data) {
> > + if (raw_btf_size != btf_data->d_size) {
> > + pr_err("FAILED: size mismatch");
> > + goto out;
> > + }
> > +
> > + btf_data->d_buf = (void *)raw_btf_data;
> > + btf_data->d_type = ELF_T_WORD;
> > + elf_flagdata(btf_data, ELF_C_SET, ELF_F_DIRTY);
> > +
> > + if (elf_update(elf, ELF_C_WRITE) >= 0)
> > + err = 0;
> > + }
> > +
> > +out:
> > + if (fd != -1)
> > + close(fd);
> > + if (elf)
> > + elf_end(elf);
> > + return err;
> > +}
> > +
> > +static int sort_update_btf(struct object *obj, bool distilled_base)
> > +{
> > + struct btf *base_btf = NULL;
> > + struct btf *btf = NULL;
> > + int start_id = 1, nr_types, id;
> > + int err = 0, i;
> > + __u32 *permute_ids = NULL, *id_map = NULL, btf_size;
> > + const void *btf_data;
> > + int fd;
> > +
> > + if (obj->base_btf_path) {
> > + base_btf = btf__parse(obj->base_btf_path, NULL);
> > + err = libbpf_get_error(base_btf);
> > + if (err) {
> > + pr_err("FAILED: load base BTF from %s: %s\n",
> > + obj->base_btf_path, strerror(-err));
> > + return -1;
> > + }
> > + }
> > +
> > + btf = btf__parse_elf_split(obj->path, base_btf);
> > + err = libbpf_get_error(btf);
> > + if (err) {
> > + pr_err("FAILED: load BTF from %s: %s\n", obj->path, strerror(-err));
> > + goto out;
> > + }
> > +
> > + if (base_btf)
> > + start_id = btf__type_cnt(base_btf);
> > + nr_types = btf__type_cnt(btf) - start_id;
> > + if (nr_types < 2)
> > + goto out;
> > +
> > + permute_ids = calloc(nr_types, sizeof(*permute_ids));
> > + if (!permute_ids) {
> > + err = -ENOMEM;
> > + goto out;
> > + }
> > +
> > + id_map = calloc(nr_types, sizeof(*id_map));
> > + if (!id_map) {
> > + err = -ENOMEM;
> > + goto out;
> > + }
> > +
> > + for (i = 0, id = start_id; i < nr_types; i++, id++)
> > + permute_ids[i] = id;
> > +
> > + qsort_r(permute_ids, nr_types, sizeof(*permute_ids), cmp_type_names, btf);
> > +
> > + for (i = 0; i < nr_types; i++) {
> > + id = permute_ids[i] - start_id;
> > + id_map[id] = i + start_id;
> > + }
> > +
> > + err = btf__permute(btf, id_map, nr_types, NULL);
> > + if (err) {
> > + pr_err("FAILED: btf permute: %s\n", strerror(-err));
> > + goto out;
> > + }
> > +
> > + if (distilled_base) {
> > + struct btf *new_btf = NULL, *distilled_base = NULL;
> > +
> > + if (btf__distill_base(btf, &distilled_base, &new_btf) < 0) {
> > + pr_err("FAILED to generate distilled base BTF: %s\n",
> > + strerror(errno));
> > + goto out;
> > + }
> > +
> > + err = update_btf_section(obj->path, new_btf, BTF_ELF_SEC);
> > + if (!err) {
> > + err = update_btf_section(obj->path, distilled_base, BTF_BASE_ELF_SEC);
> > + if (err < 0)
> > + pr_err("FAILED to update '%s'\n", BTF_BASE_ELF_SEC);
> > + } else {
> > + pr_err("FAILED to update '%s'\n", BTF_ELF_SEC);
> > + }
> > +
> > + btf__free(new_btf);
> > + btf__free(distilled_base);
> > + } else {
> > + err = update_btf_section(obj->path, btf, BTF_ELF_SEC);
> > + if (err < 0) {
> > + pr_err("FAILED to update '%s'\n", BTF_ELF_SEC);
> > + goto out;
> > + }
> > + }
> > +
> > +out:
> > + free(permute_ids);
> > + free(id_map);
> > + btf__free(base_btf);
> > + btf__free(btf);
> > + return err;
> > +}
> > +
> > static const char * const resolve_btfids_usage[] = {
> > "resolve_btfids [<options>] <ELF object>",
> > NULL
> > @@ -787,6 +976,8 @@ int main(int argc, const char **argv)
> > .sets = RB_ROOT,
> > };
> > bool fatal_warnings = false;
> > + bool btf_sort = false;
> > + bool distilled_base = false;
> > struct option btfid_options[] = {
> > OPT_INCR('v', "verbose", &verbose,
> > "be more verbose (show errors, etc)"),
> > @@ -796,6 +987,10 @@ int main(int argc, const char **argv)
> > "path of file providing base BTF"),
> > OPT_BOOLEAN(0, "fatal_warnings", &fatal_warnings,
> > "turn warnings into errors"),
> > + OPT_BOOLEAN(0, "btf_sort", &btf_sort,
> > + "sort BTF by name in ascending order"),
> > + OPT_BOOLEAN(0, "distilled_base", &distilled_base,
> > + "distill base"),
> > OPT_END()
> > };
> > int err = -1;
> > @@ -807,6 +1002,11 @@ int main(int argc, const char **argv)
> >
> > obj.path = argv[0];
> >
> > + if (btf_sort) {
> > + err = sort_update_btf(&obj, distilled_base);
> > + goto out;
> > + }
> > +
> > if (elf_collect(&obj))
> > goto out;
> >
>
^ permalink raw reply [flat|nested] 42+ messages in thread* Re: [RFC PATCH v7 3/7] tools/resolve_btfids: Add --btf_sort option for BTF name sorting
2025-11-21 15:36 ` Donglin Peng
@ 2025-11-24 19:35 ` Ihor Solodrai
2025-11-25 10:54 ` Donglin Peng
0 siblings, 1 reply; 42+ messages in thread
From: Ihor Solodrai @ 2025-11-24 19:35 UTC (permalink / raw)
To: Donglin Peng
Cc: ast, andrii.nakryiko, eddyz87, zhangxiaoqin, linux-kernel, bpf,
Donglin Peng, Alan Maguire, Song Liu
On 11/21/25 7:36 AM, Donglin Peng wrote:
> On Fri, Nov 21, 2025 at 5:34 AM Ihor Solodrai <ihor.solodrai@linux.dev> wrote:
>>
>> On 11/18/25 7:15 PM, Donglin Peng wrote:
>>> From: Donglin Peng <pengdonglin@xiaomi.com>
>>>
>>> This patch introduces a new --btf_sort option that leverages libbpf's
>>> btf__permute interface to reorganize BTF layout. The implementation
>>> sorts BTF types by name in ascending order, placing anonymous types at
>>> the end to enable efficient binary search lookup.
>>
>> [...]
>>
>> Hi Dongling.
>>
>> Thanks for working on this, it's a great optimization. Just want to
>> give you a heads up that I am preparing a patchset changing
>> resolve_btfids behavior.
>
> Thanks. I'm curious about the new behavior of resolve_btfids. Does it
> replace pahole and generate the sorted .BTF data directly from the
> DWARF data? Also, does its sorting method differ from the cmp_type_names
> approach mentioned above — specifically, does it place named types
> before all anonymous types? I'm asking because the search method
> needs to be compatible with this sorting approach.
No, replacing pahole entirely isn't really feasible, and unnecessary.
TL;DR is that resolve_btfids will also do kernel-specific btf2btf
transformations. The sorting feature is independent, it's relevant
only in that it is also a btf2btf transformation and will be included
in the pipeline.
I described the approach here:
https://lore.kernel.org/dwarves/ba1650aa-fafd-49a8-bea4-bdddee7c38c9@linux.dev/
>
>>
>> In particular, instead of updating the .BTF_ids section (and now with
>> your and upcoming changes the .BTF section) *in-place*, resolve_btfids
>> will only emit the data for the sections. And then it'll be integrated
>> into vmlinux with objcopy and linker. We already do a similar thing
>> with .BTF for vmlinux [1].
>>
>> For your patchset it means that the parts handling ELF update will be
>> unnecessary.
>>
>> Also I think the --btf_sort flag is unnecessary. We probably want
>> kernel BTF to always be sorted in this way. And if resolve_btfids will
>> be handling more btf2btf transformation, we should avoid adding a
>> flags for every one of them.
>>
>> [1] https://git.kernel.org/pub/scm/linux/kernel/git/bpf/bpf-next.git/tree/scripts/link-vmlinux.sh#n110
>>
^ permalink raw reply [flat|nested] 42+ messages in thread
* Re: [RFC PATCH v7 3/7] tools/resolve_btfids: Add --btf_sort option for BTF name sorting
2025-11-24 19:35 ` Ihor Solodrai
@ 2025-11-25 10:54 ` Donglin Peng
0 siblings, 0 replies; 42+ messages in thread
From: Donglin Peng @ 2025-11-25 10:54 UTC (permalink / raw)
To: Ihor Solodrai
Cc: ast, andrii.nakryiko, eddyz87, zhangxiaoqin, linux-kernel, bpf,
Donglin Peng, Alan Maguire, Song Liu
On Tue, Nov 25, 2025 at 3:35 AM Ihor Solodrai <ihor.solodrai@linux.dev> wrote:
>
> On 11/21/25 7:36 AM, Donglin Peng wrote:
> > On Fri, Nov 21, 2025 at 5:34 AM Ihor Solodrai <ihor.solodrai@linux.dev> wrote:
> >>
> >> On 11/18/25 7:15 PM, Donglin Peng wrote:
> >>> From: Donglin Peng <pengdonglin@xiaomi.com>
> >>>
> >>> This patch introduces a new --btf_sort option that leverages libbpf's
> >>> btf__permute interface to reorganize BTF layout. The implementation
> >>> sorts BTF types by name in ascending order, placing anonymous types at
> >>> the end to enable efficient binary search lookup.
> >>
> >> [...]
> >>
> >> Hi Dongling.
> >>
> >> Thanks for working on this, it's a great optimization. Just want to
> >> give you a heads up that I am preparing a patchset changing
> >> resolve_btfids behavior.
> >
> > Thanks. I'm curious about the new behavior of resolve_btfids. Does it
> > replace pahole and generate the sorted .BTF data directly from the
> > DWARF data? Also, does its sorting method differ from the cmp_type_names
> > approach mentioned above — specifically, does it place named types
> > before all anonymous types? I'm asking because the search method
> > needs to be compatible with this sorting approach.
>
> No, replacing pahole entirely isn't really feasible, and unnecessary.
>
> TL;DR is that resolve_btfids will also do kernel-specific btf2btf
> transformations. The sorting feature is independent, it's relevant
> only in that it is also a btf2btf transformation and will be included
> in the pipeline.
>
> I described the approach here:
> https://lore.kernel.org/dwarves/ba1650aa-fafd-49a8-bea4-bdddee7c38c9@linux.dev/
Thanks for the explanation.
>
>
> >
> >>
> >> In particular, instead of updating the .BTF_ids section (and now with
> >> your and upcoming changes the .BTF section) *in-place*, resolve_btfids
> >> will only emit the data for the sections. And then it'll be integrated
> >> into vmlinux with objcopy and linker. We already do a similar thing
> >> with .BTF for vmlinux [1].
> >>
> >> For your patchset it means that the parts handling ELF update will be
> >> unnecessary.
> >>
> >> Also I think the --btf_sort flag is unnecessary. We probably want
> >> kernel BTF to always be sorted in this way. And if resolve_btfids will
> >> be handling more btf2btf transformation, we should avoid adding a
> >> flags for every one of them.
> >>
> >> [1] https://git.kernel.org/pub/scm/linux/kernel/git/bpf/bpf-next.git/tree/scripts/link-vmlinux.sh#n110
> >>
^ permalink raw reply [flat|nested] 42+ messages in thread
* Re: [RFC PATCH v7 3/7] tools/resolve_btfids: Add --btf_sort option for BTF name sorting
2025-11-19 3:15 ` [RFC PATCH v7 3/7] tools/resolve_btfids: Add --btf_sort option for BTF name sorting Donglin Peng
2025-11-20 21:34 ` Ihor Solodrai
@ 2025-11-21 0:18 ` Eduard Zingerman
2025-11-24 12:14 ` Donglin Peng
1 sibling, 1 reply; 42+ messages in thread
From: Eduard Zingerman @ 2025-11-21 0:18 UTC (permalink / raw)
To: Donglin Peng, ast, andrii.nakryiko
Cc: zhangxiaoqin, linux-kernel, bpf, Donglin Peng, Alan Maguire,
Song Liu
On Wed, 2025-11-19 at 11:15 +0800, Donglin Peng wrote:
[...]
> diff --git a/scripts/Makefile.btf b/scripts/Makefile.btf
> index db76335dd917..d5eb4ee70e88 100644
> --- a/scripts/Makefile.btf
> +++ b/scripts/Makefile.btf
> @@ -27,6 +27,7 @@ pahole-flags-$(call test-ge, $(pahole-ver), 130) += --btf_features=attributes
>
> ifneq ($(KBUILD_EXTMOD),)
> module-pahole-flags-$(call test-ge, $(pahole-ver), 128) += --btf_features=distilled_base
> +module-resolve_btfid-flags-y = --distilled_base
^^^^^^^^^^^^^^^^
This flag should be guarded by pahole version as well. However, I'd
suggest not adding this flag at all, but instead modify resolve_btfids
to check for BTF_BASE_ELF_SEC section existence and acting accordingly.
> endif
>
> endif
> @@ -35,3 +36,4 @@ pahole-flags-$(CONFIG_PAHOLE_HAS_LANG_EXCLUDE) += --lang_exclude=rust
>
> export PAHOLE_FLAGS := $(pahole-flags-y)
> export MODULE_PAHOLE_FLAGS := $(module-pahole-flags-y)
> +export MODULE_RESOLVE_BTFID_FLAGS := $(module-resolve_btfid-flags-y)
> diff --git a/scripts/Makefile.modfinal b/scripts/Makefile.modfinal
> index 542ba462ed3e..4481dda2f485 100644
> --- a/scripts/Makefile.modfinal
> +++ b/scripts/Makefile.modfinal
> @@ -40,6 +40,7 @@ quiet_cmd_btf_ko = BTF [M] $@
> printf "Skipping BTF generation for %s due to unavailability of vmlinux\n" $@ 1>&2; \
> else \
> LLVM_OBJCOPY="$(OBJCOPY)" $(PAHOLE) -J $(PAHOLE_FLAGS) $(MODULE_PAHOLE_FLAGS) --btf_base $(objtree)/vmlinux $@; \
> + $(RESOLVE_BTFIDS) -b $(objtree)/vmlinux $(MODULE_RESOLVE_BTFID_FLAGS) --btf_sort $@; \
^^^^^^^^^^
Agree with Ihor (and off-list discussion with Alexei),
this flag appears redundant. Are there situations when
one would like to avoid sorting kernel/module BTF?
> $(RESOLVE_BTFIDS) -b $(objtree)/vmlinux $@; \
> fi;
[...]
> diff --git a/tools/bpf/resolve_btfids/main.c b/tools/bpf/resolve_btfids/main.c
> index d47191c6e55e..dc0badd6f375 100644
> --- a/tools/bpf/resolve_btfids/main.c
> +++ b/tools/bpf/resolve_btfids/main.c
[...]
> +static int update_btf_section(const char *path, const struct btf *btf,
> + const char *btf_secname)
> +{
> + GElf_Shdr shdr_mem, *shdr;
> + Elf_Data *btf_data = NULL;
> + Elf_Scn *scn = NULL;
> + Elf *elf = NULL;
> + const void *raw_btf_data;
> + uint32_t raw_btf_size;
> + int fd, err = -1;
> + size_t strndx;
> +
> + fd = open(path, O_RDWR);
> + if (fd < 0) {
> + pr_err("FAILED to open %s\n", path);
> + return -1;
> + }
> +
> + if (elf_version(EV_CURRENT) == EV_NONE) {
> + pr_err("FAILED to set libelf version");
> + goto out;
> + }
> +
> + elf = elf_begin(fd, ELF_C_RDWR, NULL);
> + if (elf == NULL) {
> + pr_err("FAILED to update ELF file");
> + goto out;
> + }
> +
> + elf_flagelf(elf, ELF_C_SET, ELF_F_LAYOUT);
> +
> + elf_getshdrstrndx(elf, &strndx);
> + while ((scn = elf_nextscn(elf, scn)) != NULL) {
> + char *secname;
> +
> + shdr = gelf_getshdr(scn, &shdr_mem);
> + if (shdr == NULL)
> + continue;
> + secname = elf_strptr(elf, strndx, shdr->sh_name);
> + if (strcmp(secname, btf_secname) == 0) {
> + btf_data = elf_getdata(scn, btf_data);
> + break;
> + }
> + }
> +
> + raw_btf_data = btf__raw_data(btf, &raw_btf_size);
`btf__raw_data()` can return NULL.
> +
> + if (btf_data) {
> + if (raw_btf_size != btf_data->d_size) {
> + pr_err("FAILED: size mismatch");
> + goto out;
> + }
> +
> + btf_data->d_buf = (void *)raw_btf_data;
> + btf_data->d_type = ELF_T_WORD;
> + elf_flagdata(btf_data, ELF_C_SET, ELF_F_DIRTY);
> +
> + if (elf_update(elf, ELF_C_WRITE) >= 0)
> + err = 0;
> + }
> +
> +out:
> + if (fd != -1)
> + close(fd);
> + if (elf)
> + elf_end(elf);
> + return err;
> +}
[...]
^ permalink raw reply [flat|nested] 42+ messages in thread* Re: [RFC PATCH v7 3/7] tools/resolve_btfids: Add --btf_sort option for BTF name sorting
2025-11-21 0:18 ` Eduard Zingerman
@ 2025-11-24 12:14 ` Donglin Peng
0 siblings, 0 replies; 42+ messages in thread
From: Donglin Peng @ 2025-11-24 12:14 UTC (permalink / raw)
To: Eduard Zingerman
Cc: ast, andrii.nakryiko, zhangxiaoqin, linux-kernel, bpf,
Donglin Peng, Alan Maguire, Song Liu
On Fri, Nov 21, 2025 at 8:18 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Wed, 2025-11-19 at 11:15 +0800, Donglin Peng wrote:
>
> [...]
>
> > diff --git a/scripts/Makefile.btf b/scripts/Makefile.btf
> > index db76335dd917..d5eb4ee70e88 100644
> > --- a/scripts/Makefile.btf
> > +++ b/scripts/Makefile.btf
> > @@ -27,6 +27,7 @@ pahole-flags-$(call test-ge, $(pahole-ver), 130) += --btf_features=attributes
> >
> > ifneq ($(KBUILD_EXTMOD),)
> > module-pahole-flags-$(call test-ge, $(pahole-ver), 128) += --btf_features=distilled_base
> > +module-resolve_btfid-flags-y = --distilled_base
> ^^^^^^^^^^^^^^^^
> This flag should be guarded by pahole version as well. However, I'd
> suggest not adding this flag at all, but instead modify resolve_btfids
> to check for BTF_BASE_ELF_SEC section existence and acting accordingly.
Thanks, I will remove it in the next version.
>
> > endif
> >
> > endif
> > @@ -35,3 +36,4 @@ pahole-flags-$(CONFIG_PAHOLE_HAS_LANG_EXCLUDE) += --lang_exclude=rust
> >
> > export PAHOLE_FLAGS := $(pahole-flags-y)
> > export MODULE_PAHOLE_FLAGS := $(module-pahole-flags-y)
> > +export MODULE_RESOLVE_BTFID_FLAGS := $(module-resolve_btfid-flags-y)
> > diff --git a/scripts/Makefile.modfinal b/scripts/Makefile.modfinal
> > index 542ba462ed3e..4481dda2f485 100644
> > --- a/scripts/Makefile.modfinal
> > +++ b/scripts/Makefile.modfinal
> > @@ -40,6 +40,7 @@ quiet_cmd_btf_ko = BTF [M] $@
> > printf "Skipping BTF generation for %s due to unavailability of vmlinux\n" $@ 1>&2; \
> > else \
> > LLVM_OBJCOPY="$(OBJCOPY)" $(PAHOLE) -J $(PAHOLE_FLAGS) $(MODULE_PAHOLE_FLAGS) --btf_base $(objtree)/vmlinux $@; \
> > + $(RESOLVE_BTFIDS) -b $(objtree)/vmlinux $(MODULE_RESOLVE_BTFID_FLAGS) --btf_sort $@; \
> ^^^^^^^^^^
> Agree with Ihor (and off-list discussion with Alexei),
> this flag appears redundant. Are there situations when
> one would like to avoid sorting kernel/module BTF?
Thanks, I will make sorting unconditional.
>
> > $(RESOLVE_BTFIDS) -b $(objtree)/vmlinux $@; \
> > fi;
>
> [...]
>
> > diff --git a/tools/bpf/resolve_btfids/main.c b/tools/bpf/resolve_btfids/main.c
> > index d47191c6e55e..dc0badd6f375 100644
> > --- a/tools/bpf/resolve_btfids/main.c
> > +++ b/tools/bpf/resolve_btfids/main.c
>
> [...]
>
> > +static int update_btf_section(const char *path, const struct btf *btf,
> > + const char *btf_secname)
> > +{
> > + GElf_Shdr shdr_mem, *shdr;
> > + Elf_Data *btf_data = NULL;
> > + Elf_Scn *scn = NULL;
> > + Elf *elf = NULL;
> > + const void *raw_btf_data;
> > + uint32_t raw_btf_size;
> > + int fd, err = -1;
> > + size_t strndx;
> > +
> > + fd = open(path, O_RDWR);
> > + if (fd < 0) {
> > + pr_err("FAILED to open %s\n", path);
> > + return -1;
> > + }
> > +
> > + if (elf_version(EV_CURRENT) == EV_NONE) {
> > + pr_err("FAILED to set libelf version");
> > + goto out;
> > + }
> > +
> > + elf = elf_begin(fd, ELF_C_RDWR, NULL);
> > + if (elf == NULL) {
> > + pr_err("FAILED to update ELF file");
> > + goto out;
> > + }
> > +
> > + elf_flagelf(elf, ELF_C_SET, ELF_F_LAYOUT);
> > +
> > + elf_getshdrstrndx(elf, &strndx);
> > + while ((scn = elf_nextscn(elf, scn)) != NULL) {
> > + char *secname;
> > +
> > + shdr = gelf_getshdr(scn, &shdr_mem);
> > + if (shdr == NULL)
> > + continue;
> > + secname = elf_strptr(elf, strndx, shdr->sh_name);
> > + if (strcmp(secname, btf_secname) == 0) {
> > + btf_data = elf_getdata(scn, btf_data);
> > + break;
> > + }
> > + }
> > +
> > + raw_btf_data = btf__raw_data(btf, &raw_btf_size);
>
> `btf__raw_data()` can return NULL.
Thanks, I will fix it.
>
> > +
> > + if (btf_data) {
> > + if (raw_btf_size != btf_data->d_size) {
> > + pr_err("FAILED: size mismatch");
> > + goto out;
> > + }
> > +
> > + btf_data->d_buf = (void *)raw_btf_data;
> > + btf_data->d_type = ELF_T_WORD;
> > + elf_flagdata(btf_data, ELF_C_SET, ELF_F_DIRTY);
> > +
> > + if (elf_update(elf, ELF_C_WRITE) >= 0)
> > + err = 0;
> > + }
> > +
> > +out:
> > + if (fd != -1)
> > + close(fd);
> > + if (elf)
> > + elf_end(elf);
> > + return err;
> > +}
>
> [...]
^ permalink raw reply [flat|nested] 42+ messages in thread
* [RFC PATCH v7 4/7] libbpf: Optimize type lookup with binary search for sorted BTF
2025-11-19 3:15 [RFC PATCH v7 0/7] Improve the performance of BTF type lookups with binary search Donglin Peng
` (2 preceding siblings ...)
2025-11-19 3:15 ` [RFC PATCH v7 3/7] tools/resolve_btfids: Add --btf_sort option for BTF name sorting Donglin Peng
@ 2025-11-19 3:15 ` Donglin Peng
2025-11-19 4:11 ` bot+bpf-ci
2025-11-19 19:47 ` Andrii Nakryiko
2025-11-19 3:15 ` [RFC PATCH v7 5/7] libbpf: Implement BTF type sorting validation for binary search optimization Donglin Peng
` (2 subsequent siblings)
6 siblings, 2 replies; 42+ messages in thread
From: Donglin Peng @ 2025-11-19 3:15 UTC (permalink / raw)
To: ast, andrii.nakryiko
Cc: eddyz87, zhangxiaoqin, linux-kernel, bpf, Donglin Peng,
Alan Maguire, Song Liu
From: Donglin Peng <pengdonglin@xiaomi.com>
This patch introduces binary search optimization for BTF type lookups
when the BTF instance contains sorted types.
The optimization significantly improves performance when searching for
types in large BTF instances with sorted type names. For unsorted BTF
or when nr_sorted_types is zero, the implementation falls back to
the original linear search algorithm.
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>
Cc: Xiaoqin Zhang <zhangxiaoqin@xiaomi.com>
Signed-off-by: Donglin Peng <pengdonglin@xiaomi.com>
---
tools/lib/bpf/btf.c | 104 ++++++++++++++++++++++++++++++++++----------
1 file changed, 81 insertions(+), 23 deletions(-)
diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c
index ab95ff19fde3..1d19d95da1d0 100644
--- a/tools/lib/bpf/btf.c
+++ b/tools/lib/bpf/btf.c
@@ -92,6 +92,12 @@ struct btf {
* - for split BTF counts number of types added on top of base BTF.
*/
__u32 nr_types;
+ /* number of sorted and named types in this BTF instance:
+ * - doesn't include special [0] void type;
+ * - for split BTF counts number of sorted and named types added on
+ * top of base BTF.
+ */
+ __u32 nr_sorted_types;
/* if not NULL, points to the base BTF on top of which the current
* split BTF is based
*/
@@ -897,44 +903,93 @@ int btf__resolve_type(const struct btf *btf, __u32 type_id)
return type_id;
}
-__s32 btf__find_by_name(const struct btf *btf, const char *type_name)
+static __s32 btf_find_type_by_name_bsearch(const struct btf *btf, const char *name,
+ __s32 start_id, __s32 end_id)
{
- __u32 i, nr_types = btf__type_cnt(btf);
+ const struct btf_type *t;
+ const char *tname;
+ __s32 l, r, m;
+
+ l = start_id;
+ r = end_id;
+ while (l <= r) {
+ m = l + (r - l) / 2;
+ t = btf_type_by_id(btf, m);
+ tname = btf__str_by_offset(btf, t->name_off);
+ if (strcmp(tname, name) >= 0) {
+ if (l == r)
+ return r;
+ r = m;
+ } else {
+ l = m + 1;
+ }
+ }
- if (!strcmp(type_name, "void"))
- return 0;
+ return btf__type_cnt(btf);
+}
- for (i = 1; i < nr_types; i++) {
- const struct btf_type *t = btf__type_by_id(btf, i);
- const char *name = btf__name_by_offset(btf, t->name_off);
+static __s32 btf_find_type_by_name_kind(const struct btf *btf, int start_id,
+ const char *type_name, __u32 kind)
+{
+ const struct btf_type *t;
+ const char *tname;
+ int err = -ENOENT;
+
+ if (start_id < btf->start_id) {
+ err = btf_find_type_by_name_kind(btf->base_btf, start_id,
+ type_name, kind);
+ if (err > 0)
+ goto out;
+ start_id = btf->start_id;
+ }
+
+ if (btf->nr_sorted_types > 0) {
+ /* binary search */
+ __s32 end_id;
+ int idx;
+
+ end_id = btf->start_id + btf->nr_sorted_types - 1;
+ idx = btf_find_type_by_name_bsearch(btf, type_name, start_id, end_id);
+ for (; idx <= end_id; idx++) {
+ t = btf__type_by_id(btf, idx);
+ tname = btf__str_by_offset(btf, t->name_off);
+ if (strcmp(tname, type_name))
+ goto out;
+ if (kind == -1 || btf_kind(t) == kind)
+ return idx;
+ }
+ } else {
+ /* linear search */
+ __u32 i, total;
- if (name && !strcmp(type_name, name))
- return i;
+ total = btf__type_cnt(btf);
+ for (i = start_id; i < total; i++) {
+ t = btf_type_by_id(btf, i);
+ if (kind != -1 && btf_kind(t) != kind)
+ continue;
+ tname = btf__str_by_offset(btf, t->name_off);
+ if (tname && !strcmp(tname, type_name))
+ return i;
+ }
}
- return libbpf_err(-ENOENT);
+out:
+ return err;
}
static __s32 btf_find_by_name_kind(const struct btf *btf, int start_id,
const char *type_name, __u32 kind)
{
- __u32 i, nr_types = btf__type_cnt(btf);
-
if (kind == BTF_KIND_UNKN || !strcmp(type_name, "void"))
return 0;
- for (i = start_id; i < nr_types; i++) {
- const struct btf_type *t = btf__type_by_id(btf, i);
- const char *name;
-
- if (btf_kind(t) != kind)
- continue;
- name = btf__name_by_offset(btf, t->name_off);
- if (name && !strcmp(type_name, name))
- return i;
- }
+ return libbpf_err(btf_find_type_by_name_kind(btf, start_id, type_name, kind));
+}
- return libbpf_err(-ENOENT);
+/* the kind value of -1 indicates that kind matching should be skipped */
+__s32 btf__find_by_name(const struct btf *btf, const char *type_name)
+{
+ return btf_find_by_name_kind(btf, btf->start_id, type_name, -1);
}
__s32 btf__find_by_name_kind_own(const struct btf *btf, const char *type_name,
@@ -1006,6 +1061,7 @@ static struct btf *btf_new_empty(struct btf *base_btf)
btf->fd = -1;
btf->ptr_sz = sizeof(void *);
btf->swapped_endian = false;
+ btf->nr_sorted_types = 0;
if (base_btf) {
btf->base_btf = base_btf;
@@ -1057,6 +1113,7 @@ static struct btf *btf_new(const void *data, __u32 size, struct btf *base_btf, b
btf->start_id = 1;
btf->start_str_off = 0;
btf->fd = -1;
+ btf->nr_sorted_types = 0;
if (base_btf) {
btf->base_btf = base_btf;
@@ -1715,6 +1772,7 @@ static void btf_invalidate_raw_data(struct btf *btf)
free(btf->raw_data_swapped);
btf->raw_data_swapped = NULL;
}
+ btf->nr_sorted_types = 0;
}
/* Ensure BTF is ready to be modified (by splitting into a three memory
--
2.34.1
^ permalink raw reply related [flat|nested] 42+ messages in thread* Re: [RFC PATCH v7 4/7] libbpf: Optimize type lookup with binary search for sorted BTF
2025-11-19 3:15 ` [RFC PATCH v7 4/7] libbpf: Optimize type lookup with binary search for sorted BTF Donglin Peng
@ 2025-11-19 4:11 ` bot+bpf-ci
2025-11-19 4:43 ` Donglin Peng
2025-11-19 19:47 ` Andrii Nakryiko
1 sibling, 1 reply; 42+ messages in thread
From: bot+bpf-ci @ 2025-11-19 4:11 UTC (permalink / raw)
To: dolinux.peng, ast, andrii.nakryiko
Cc: eddyz87, zhangxiaoqin, linux-kernel, bpf, pengdonglin,
alan.maguire, song, ast, andrii, daniel, martin.lau, eddyz87,
yonghong.song, clm, ihor.solodrai
[-- Attachment #1: Type: text/plain, Size: 2920 bytes --]
> diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c
> index 71d464690..555703b37 100644
> --- a/tools/lib/bpf/btf.c
> +++ b/tools/lib/bpf/btf.c
[ ... ]
> @@ -897,44 +903,93 @@ int btf__resolve_type(const struct btf *btf, __u32 type_id)
> return type_id;
> }
>
> -__s32 btf__find_by_name(const struct btf *btf, const char *type_name)
> +static __s32 btf_find_type_by_name_bsearch(const struct btf *btf, const char *name,
> + __s32 start_id, __s32 end_id)
> {
> - __u32 i, nr_types = btf__type_cnt(btf);
> + const struct btf_type *t;
> + const char *tname;
> + __s32 l, r, m;
> +
> + l = start_id;
> + r = end_id;
> + while (l <= r) {
> + m = l + (r - l) / 2;
> + t = btf_type_by_id(btf, m);
> + tname = btf__str_by_offset(btf, t->name_off);
> + if (strcmp(tname, name) >= 0) {
^^^^^^
Can strcmp() handle a NULL tname here? The btf__str_by_offset()
function returns NULL when offset is out of range (line 1674 returns
"errno = EINVAL, NULL"), but strcmp() requires non-NULL arguments.
The original linear search code at line 971 checks "if (tname &&
!strcmp(tname, type_name))" before calling strcmp(). Should the binary
search path also check for NULL?
> + if (l == r)
> + return r;
> + r = m;
> + } else {
> + l = m + 1;
> + }
> + }
> +
> + return btf__type_cnt(btf);
> +}
> +
> +static __s32 btf_find_type_by_name_kind(const struct btf *btf, int start_id,
> + const char *type_name, __u32 kind)
> +{
> + const struct btf_type *t;
> + const char *tname;
> + int err = -ENOENT;
> +
> + if (start_id < btf->start_id) {
> + err = btf_find_type_by_name_kind(btf->base_btf, start_id,
> + type_name, kind);
> + if (err > 0)
> + goto out;
> + start_id = btf->start_id;
> + }
> +
> + if (btf->nr_sorted_types > 0) {
> + /* binary search */
> + __s32 end_id;
> + int idx;
> +
> + end_id = btf->start_id + btf->nr_sorted_types - 1;
> + idx = btf_find_type_by_name_bsearch(btf, type_name, start_id, end_id);
> + for (; idx <= end_id; idx++) {
> + t = btf__type_by_id(btf, idx);
> + tname = btf__str_by_offset(btf, t->name_off);
> + if (strcmp(tname, type_name))
^^^^^^
Same question here - can tname be NULL at this point?
> + goto out;
> + if (kind == -1 || btf_kind(t) == kind)
> + return idx;
> + }
> + } else {
> + /* linear search */
> + __u32 i, total;
> +
> + total = btf__type_cnt(btf);
> + for (i = start_id; i < total; i++) {
> + t = btf_type_by_id(btf, i);
> + if (kind != -1 && btf_kind(t) != kind)
> + continue;
> + tname = btf__str_by_offset(btf, t->name_off);
> + if (tname && !strcmp(tname, type_name))
> + return i;
> + }
> + }
[ ... ]
---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md
CI run summary: https://github.com/kernel-patches/bpf/actions/runs/19488781158
^ permalink raw reply [flat|nested] 42+ messages in thread* Re: [RFC PATCH v7 4/7] libbpf: Optimize type lookup with binary search for sorted BTF
2025-11-19 4:11 ` bot+bpf-ci
@ 2025-11-19 4:43 ` Donglin Peng
0 siblings, 0 replies; 42+ messages in thread
From: Donglin Peng @ 2025-11-19 4:43 UTC (permalink / raw)
To: bot+bpf-ci
Cc: ast, andrii.nakryiko, eddyz87, zhangxiaoqin, linux-kernel, bpf,
pengdonglin, alan.maguire, song, andrii, daniel, martin.lau,
yonghong.song, clm, ihor.solodrai
On Wed, Nov 19, 2025 at 12:11 PM <bot+bpf-ci@kernel.org> wrote:
>
> > diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c
> > index 71d464690..555703b37 100644
> > --- a/tools/lib/bpf/btf.c
> > +++ b/tools/lib/bpf/btf.c
>
> [ ... ]
>
> > @@ -897,44 +903,93 @@ int btf__resolve_type(const struct btf *btf, __u32 type_id)
> > return type_id;
> > }
> >
> > -__s32 btf__find_by_name(const struct btf *btf, const char *type_name)
> > +static __s32 btf_find_type_by_name_bsearch(const struct btf *btf, const char *name,
> > + __s32 start_id, __s32 end_id)
> > {
> > - __u32 i, nr_types = btf__type_cnt(btf);
> > + const struct btf_type *t;
> > + const char *tname;
> > + __s32 l, r, m;
> > +
> > + l = start_id;
> > + r = end_id;
> > + while (l <= r) {
> > + m = l + (r - l) / 2;
> > + t = btf_type_by_id(btf, m);
> > + tname = btf__str_by_offset(btf, t->name_off);
> > + if (strcmp(tname, name) >= 0) {
> ^^^^^^
> Can strcmp() handle a NULL tname here? The btf__str_by_offset()
> function returns NULL when offset is out of range (line 1674 returns
> "errno = EINVAL, NULL"), but strcmp() requires non-NULL arguments.
>
> The original linear search code at line 971 checks "if (tname &&
> !strcmp(tname, type_name))" before calling strcmp(). Should the binary
> search path also check for NULL?
Thank you. It is unnecessary to check for a NULL type name in this context
because the btf_check_sorted function introduced in the subsequent patch
ensures that all types accessed via binary search have non-NULL names.
Furthermore, in the current patch, nr_sorted_types is always zero, meaning
the binary search path is never exercised.
>
> > + if (l == r)
> > + return r;
> > + r = m;
> > + } else {
> > + l = m + 1;
> > + }
> > + }
> > +
> > + return btf__type_cnt(btf);
> > +}
> > +
> > +static __s32 btf_find_type_by_name_kind(const struct btf *btf, int start_id,
> > + const char *type_name, __u32 kind)
> > +{
> > + const struct btf_type *t;
> > + const char *tname;
> > + int err = -ENOENT;
> > +
> > + if (start_id < btf->start_id) {
> > + err = btf_find_type_by_name_kind(btf->base_btf, start_id,
> > + type_name, kind);
> > + if (err > 0)
> > + goto out;
> > + start_id = btf->start_id;
> > + }
> > +
> > + if (btf->nr_sorted_types > 0) {
> > + /* binary search */
> > + __s32 end_id;
> > + int idx;
> > +
> > + end_id = btf->start_id + btf->nr_sorted_types - 1;
> > + idx = btf_find_type_by_name_bsearch(btf, type_name, start_id, end_id);
> > + for (; idx <= end_id; idx++) {
> > + t = btf__type_by_id(btf, idx);
> > + tname = btf__str_by_offset(btf, t->name_off);
> > + if (strcmp(tname, type_name))
> ^^^^^^
> Same question here - can tname be NULL at this point?
Ditto.
>
> > + goto out;
> > + if (kind == -1 || btf_kind(t) == kind)
> > + return idx;
> > + }
> > + } else {
> > + /* linear search */
> > + __u32 i, total;
> > +
> > + total = btf__type_cnt(btf);
> > + for (i = start_id; i < total; i++) {
> > + t = btf_type_by_id(btf, i);
> > + if (kind != -1 && btf_kind(t) != kind)
> > + continue;
> > + tname = btf__str_by_offset(btf, t->name_off);
> > + if (tname && !strcmp(tname, type_name))
> > + return i;
> > + }
> > + }
>
> [ ... ]
>
>
> ---
> AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
> See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md
>
> CI run summary: https://github.com/kernel-patches/bpf/actions/runs/19488781158
^ permalink raw reply [flat|nested] 42+ messages in thread
* Re: [RFC PATCH v7 4/7] libbpf: Optimize type lookup with binary search for sorted BTF
2025-11-19 3:15 ` [RFC PATCH v7 4/7] libbpf: Optimize type lookup with binary search for sorted BTF Donglin Peng
2025-11-19 4:11 ` bot+bpf-ci
@ 2025-11-19 19:47 ` Andrii Nakryiko
2025-11-20 7:41 ` Donglin Peng
1 sibling, 1 reply; 42+ messages in thread
From: Andrii Nakryiko @ 2025-11-19 19:47 UTC (permalink / raw)
To: Donglin Peng
Cc: ast, eddyz87, zhangxiaoqin, linux-kernel, bpf, Donglin Peng,
Alan Maguire, Song Liu
On Tue, Nov 18, 2025 at 7:21 PM Donglin Peng <dolinux.peng@gmail.com> wrote:
>
> From: Donglin Peng <pengdonglin@xiaomi.com>
>
> This patch introduces binary search optimization for BTF type lookups
> when the BTF instance contains sorted types.
>
> The optimization significantly improves performance when searching for
> types in large BTF instances with sorted type names. For unsorted BTF
> or when nr_sorted_types is zero, the implementation falls back to
> the original linear search algorithm.
>
> 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>
> Cc: Xiaoqin Zhang <zhangxiaoqin@xiaomi.com>
> Signed-off-by: Donglin Peng <pengdonglin@xiaomi.com>
> ---
> tools/lib/bpf/btf.c | 104 ++++++++++++++++++++++++++++++++++----------
> 1 file changed, 81 insertions(+), 23 deletions(-)
>
[...]
> + const struct btf_type *t;
> + const char *tname;
> + int err = -ENOENT;
> +
> + if (start_id < btf->start_id) {
> + err = btf_find_type_by_name_kind(btf->base_btf, start_id,
> + type_name, kind);
nit: align wrapped args on the second line
also, we expect that err will be set to -ENOENT if we didn't find a
match in the base BTF, right? I'm a bit uneasy about this, I'd rather
do explicit err = -ENOENT setting for each goto out
> + if (err > 0)
> + goto out;
> + start_id = btf->start_id;
> + }
> +
> + if (btf->nr_sorted_types > 0) {
> + /* binary search */
> + __s32 end_id;
> + int idx;
> +
> + end_id = btf->start_id + btf->nr_sorted_types - 1;
> + idx = btf_find_type_by_name_bsearch(btf, type_name, start_id, end_id);
> + for (; idx <= end_id; idx++) {
> + t = btf__type_by_id(btf, idx);
> + tname = btf__str_by_offset(btf, t->name_off);
> + if (strcmp(tname, type_name))
nit: please add explicit != 0 here
also, why not just `return -ENOENT;`?
> + goto out;
> + if (kind == -1 || btf_kind(t) == kind)
> + return idx;
> + }
> + } else {
> + /* linear search */
> + __u32 i, total;
>
> - if (name && !strcmp(type_name, name))
> - return i;
> + total = btf__type_cnt(btf);
> + for (i = start_id; i < total; i++) {
> + t = btf_type_by_id(btf, i);
> + if (kind != -1 && btf_kind(t) != kind)
> + continue;
> + tname = btf__str_by_offset(btf, t->name_off);
> + if (tname && !strcmp(tname, type_name))
nit: let's do explicit == 0 for strcmp, please
> + return i;
> + }
> }
>
> - return libbpf_err(-ENOENT);
> +out:
> + return err;
> }
>
> static __s32 btf_find_by_name_kind(const struct btf *btf, int start_id,
> const char *type_name, __u32 kind)
> {
> - __u32 i, nr_types = btf__type_cnt(btf);
> -
> if (kind == BTF_KIND_UNKN || !strcmp(type_name, "void"))
> return 0;
this is the only thing that btf_find_by_name_kind() does on top of
what btf_find_type_by_name_kind(), right? Any reason we can't merge
those and keep only btf_find_by_name_kind()?
>
> - for (i = start_id; i < nr_types; i++) {
> - const struct btf_type *t = btf__type_by_id(btf, i);
> - const char *name;
> -
> - if (btf_kind(t) != kind)
> - continue;
> - name = btf__name_by_offset(btf, t->name_off);
> - if (name && !strcmp(type_name, name))
> - return i;
> - }
> + return libbpf_err(btf_find_type_by_name_kind(btf, start_id, type_name, kind));
> +}
>
[...]
^ permalink raw reply [flat|nested] 42+ messages in thread* Re: [RFC PATCH v7 4/7] libbpf: Optimize type lookup with binary search for sorted BTF
2025-11-19 19:47 ` Andrii Nakryiko
@ 2025-11-20 7:41 ` Donglin Peng
0 siblings, 0 replies; 42+ messages in thread
From: Donglin Peng @ 2025-11-20 7:41 UTC (permalink / raw)
To: Andrii Nakryiko
Cc: ast, eddyz87, zhangxiaoqin, linux-kernel, bpf, Donglin Peng,
Alan Maguire, Song Liu
On Thu, Nov 20, 2025 at 3:47 AM Andrii Nakryiko
<andrii.nakryiko@gmail.com> wrote:
>
> On Tue, Nov 18, 2025 at 7:21 PM Donglin Peng <dolinux.peng@gmail.com> wrote:
> >
> > From: Donglin Peng <pengdonglin@xiaomi.com>
> >
> > This patch introduces binary search optimization for BTF type lookups
> > when the BTF instance contains sorted types.
> >
> > The optimization significantly improves performance when searching for
> > types in large BTF instances with sorted type names. For unsorted BTF
> > or when nr_sorted_types is zero, the implementation falls back to
> > the original linear search algorithm.
> >
> > 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>
> > Cc: Xiaoqin Zhang <zhangxiaoqin@xiaomi.com>
> > Signed-off-by: Donglin Peng <pengdonglin@xiaomi.com>
> > ---
> > tools/lib/bpf/btf.c | 104 ++++++++++++++++++++++++++++++++++----------
> > 1 file changed, 81 insertions(+), 23 deletions(-)
> >
>
> [...]
>
> > + const struct btf_type *t;
> > + const char *tname;
> > + int err = -ENOENT;
> > +
> > + if (start_id < btf->start_id) {
> > + err = btf_find_type_by_name_kind(btf->base_btf, start_id,
> > + type_name, kind);
>
> nit: align wrapped args on the second line
>
> also, we expect that err will be set to -ENOENT if we didn't find a
> match in the base BTF, right? I'm a bit uneasy about this, I'd rather
> do explicit err = -ENOENT setting for each goto out
Thanks, I will refactor it.
>
> > + if (err > 0)
> > + goto out;
> > + start_id = btf->start_id;
> > + }
> > +
> > + if (btf->nr_sorted_types > 0) {
> > + /* binary search */
> > + __s32 end_id;
> > + int idx;
> > +
> > + end_id = btf->start_id + btf->nr_sorted_types - 1;
> > + idx = btf_find_type_by_name_bsearch(btf, type_name, start_id, end_id);
> > + for (; idx <= end_id; idx++) {
> > + t = btf__type_by_id(btf, idx);
> > + tname = btf__str_by_offset(btf, t->name_off);
> > + if (strcmp(tname, type_name))
>
> nit: please add explicit != 0 here
Thanks. I will fix it.
>
> also, why not just `return -ENOENT;`?
I thought about that, but I feel the function should return from
one place. Frankly, just returning -ENOENT is cleaner
>
> > + goto out;
> > + if (kind == -1 || btf_kind(t) == kind)
> > + return idx;
> > + }
> > + } else {
> > + /* linear search */
> > + __u32 i, total;
> >
> > - if (name && !strcmp(type_name, name))
> > - return i;
> > + total = btf__type_cnt(btf);
> > + for (i = start_id; i < total; i++) {
> > + t = btf_type_by_id(btf, i);
> > + if (kind != -1 && btf_kind(t) != kind)
> > + continue;
> > + tname = btf__str_by_offset(btf, t->name_off);
> > + if (tname && !strcmp(tname, type_name))
>
> nit: let's do explicit == 0 for strcmp, please
Thanks, I will fix it.
>
> > + return i;
> > + }
> > }
> >
> > - return libbpf_err(-ENOENT);
> > +out:
> > + return err;
> > }
> >
> > static __s32 btf_find_by_name_kind(const struct btf *btf, int start_id,
> > const char *type_name, __u32 kind)
> > {
> > - __u32 i, nr_types = btf__type_cnt(btf);
> > -
> > if (kind == BTF_KIND_UNKN || !strcmp(type_name, "void"))
> > return 0;
>
> this is the only thing that btf_find_by_name_kind() does on top of
> what btf_find_type_by_name_kind(), right? Any reason we can't merge
> those and keep only btf_find_by_name_kind()?
Thanks. The check exists in the original btf_find_by_name_kind.
Because btf_find_type_by_name_kind uses recursion, adding the
check there would cause it to run multiple times. I'm open to merging
the functions if the overhead is acceptable.
>
> >
> > - for (i = start_id; i < nr_types; i++) {
> > - const struct btf_type *t = btf__type_by_id(btf, i);
> > - const char *name;
> > -
> > - if (btf_kind(t) != kind)
> > - continue;
> > - name = btf__name_by_offset(btf, t->name_off);
> > - if (name && !strcmp(type_name, name))
> > - return i;
> > - }
> > + return libbpf_err(btf_find_type_by_name_kind(btf, start_id, type_name, kind));
> > +}
> >
>
> [...]
^ permalink raw reply [flat|nested] 42+ messages in thread
* [RFC PATCH v7 5/7] libbpf: Implement BTF type sorting validation for binary search optimization
2025-11-19 3:15 [RFC PATCH v7 0/7] Improve the performance of BTF type lookups with binary search Donglin Peng
` (3 preceding siblings ...)
2025-11-19 3:15 ` [RFC PATCH v7 4/7] libbpf: Optimize type lookup with binary search for sorted BTF Donglin Peng
@ 2025-11-19 3:15 ` Donglin Peng
2025-11-19 19:50 ` Andrii Nakryiko
2025-11-19 3:15 ` [RFC PATCH v7 6/7] btf: Optimize type lookup with binary search Donglin Peng
2025-11-19 3:15 ` [RFC PATCH v7 7/7] btf: Add sorting validation for " Donglin Peng
6 siblings, 1 reply; 42+ messages in thread
From: Donglin Peng @ 2025-11-19 3:15 UTC (permalink / raw)
To: ast, andrii.nakryiko
Cc: eddyz87, zhangxiaoqin, linux-kernel, bpf, Donglin Peng,
Alan Maguire, Song Liu
From: Donglin Peng <pengdonglin@xiaomi.com>
This patch adds validation to verify BTF type name sorting, enabling
binary search optimization for lookups.
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>
Cc: Xiaoqin Zhang <zhangxiaoqin@xiaomi.com>
Signed-off-by: Donglin Peng <pengdonglin@xiaomi.com>
---
tools/lib/bpf/btf.c | 59 +++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 59 insertions(+)
diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c
index 1d19d95da1d0..d872abff42e1 100644
--- a/tools/lib/bpf/btf.c
+++ b/tools/lib/bpf/btf.c
@@ -903,6 +903,64 @@ int btf__resolve_type(const struct btf *btf, __u32 type_id)
return type_id;
}
+/* Anonymous types (with empty names) are considered greater than named types
+ * and are sorted after them. Two anonymous types are considered equal. Named
+ * types are compared lexicographically.
+ */
+static int btf_compare_type_names(const void *a, const void *b, void *priv)
+{
+ struct btf *btf = (struct btf *)priv;
+ struct btf_type *ta = btf_type_by_id(btf, *(__u32 *)a);
+ struct btf_type *tb = btf_type_by_id(btf, *(__u32 *)b);
+ const char *na, *nb;
+ bool anon_a, anon_b;
+
+ na = btf__str_by_offset(btf, ta->name_off);
+ nb = btf__str_by_offset(btf, tb->name_off);
+ anon_a = str_is_empty(na);
+ anon_b = str_is_empty(nb);
+
+ if (anon_a && !anon_b)
+ return 1;
+ if (!anon_a && anon_b)
+ return -1;
+ if (anon_a && anon_b)
+ return 0;
+
+ return strcmp(na, nb);
+}
+
+/* Verifies that BTF types are sorted in ascending order according to their
+ * names, with named types appearing before anonymous types. If the ordering
+ * is correct, counts the number of named types and updates the BTF object's
+ * nr_sorted_types field.
+ */
+static void btf_check_sorted(struct btf *btf)
+{
+ const struct btf_type *t;
+ int i, k = 0, n, nr_sorted_types;
+
+ if (btf->nr_types < 2)
+ return;
+
+ nr_sorted_types = 0;
+ n = btf__type_cnt(btf) - 1;
+ for (i = btf->start_id; i < n; i++) {
+ k = i + 1;
+ if (btf_compare_type_names(&i, &k, btf) > 0)
+ return;
+ t = btf_type_by_id(btf, i);
+ if (!str_is_empty(btf__str_by_offset(btf, t->name_off)))
+ nr_sorted_types++;
+ }
+
+ t = btf_type_by_id(btf, k);
+ if (!str_is_empty(btf__str_by_offset(btf, t->name_off)))
+ nr_sorted_types++;
+ if (nr_sorted_types)
+ btf->nr_sorted_types = nr_sorted_types;
+}
+
static __s32 btf_find_type_by_name_bsearch(const struct btf *btf, const char *name,
__s32 start_id, __s32 end_id)
{
@@ -1148,6 +1206,7 @@ static struct btf *btf_new(const void *data, __u32 size, struct btf *base_btf, b
err = err ?: btf_sanity_check(btf);
if (err)
goto done;
+ btf_check_sorted(btf);
done:
if (err) {
--
2.34.1
^ permalink raw reply related [flat|nested] 42+ messages in thread* Re: [RFC PATCH v7 5/7] libbpf: Implement BTF type sorting validation for binary search optimization
2025-11-19 3:15 ` [RFC PATCH v7 5/7] libbpf: Implement BTF type sorting validation for binary search optimization Donglin Peng
@ 2025-11-19 19:50 ` Andrii Nakryiko
2025-11-20 7:25 ` Donglin Peng
0 siblings, 1 reply; 42+ messages in thread
From: Andrii Nakryiko @ 2025-11-19 19:50 UTC (permalink / raw)
To: Donglin Peng
Cc: ast, eddyz87, zhangxiaoqin, linux-kernel, bpf, Donglin Peng,
Alan Maguire, Song Liu
On Tue, Nov 18, 2025 at 7:21 PM Donglin Peng <dolinux.peng@gmail.com> wrote:
>
> From: Donglin Peng <pengdonglin@xiaomi.com>
>
> This patch adds validation to verify BTF type name sorting, enabling
> binary search optimization for lookups.
>
> 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>
> Cc: Xiaoqin Zhang <zhangxiaoqin@xiaomi.com>
> Signed-off-by: Donglin Peng <pengdonglin@xiaomi.com>
> ---
> tools/lib/bpf/btf.c | 59 +++++++++++++++++++++++++++++++++++++++++++++
> 1 file changed, 59 insertions(+)
>
> diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c
> index 1d19d95da1d0..d872abff42e1 100644
> --- a/tools/lib/bpf/btf.c
> +++ b/tools/lib/bpf/btf.c
> @@ -903,6 +903,64 @@ int btf__resolve_type(const struct btf *btf, __u32 type_id)
> return type_id;
> }
>
> +/* Anonymous types (with empty names) are considered greater than named types
> + * and are sorted after them. Two anonymous types are considered equal. Named
> + * types are compared lexicographically.
> + */
> +static int btf_compare_type_names(const void *a, const void *b, void *priv)
> +{
> + struct btf *btf = (struct btf *)priv;
> + struct btf_type *ta = btf_type_by_id(btf, *(__u32 *)a);
> + struct btf_type *tb = btf_type_by_id(btf, *(__u32 *)b);
> + const char *na, *nb;
> + bool anon_a, anon_b;
> +
> + na = btf__str_by_offset(btf, ta->name_off);
> + nb = btf__str_by_offset(btf, tb->name_off);
> + anon_a = str_is_empty(na);
> + anon_b = str_is_empty(nb);
> +
> + if (anon_a && !anon_b)
> + return 1;
> + if (!anon_a && anon_b)
> + return -1;
> + if (anon_a && anon_b)
> + return 0;
any reason to hard-code that anonymous types should come *after* named
ones? That requires custom comparison logic here and resolve_btfids,
instead of just relying on btf__str_by_offset() returning valid empty
string for name_off == 0 and then sorting anon types before named
ones, following normal lexicographical sorting rules?
[...]
^ permalink raw reply [flat|nested] 42+ messages in thread* Re: [RFC PATCH v7 5/7] libbpf: Implement BTF type sorting validation for binary search optimization
2025-11-19 19:50 ` Andrii Nakryiko
@ 2025-11-20 7:25 ` Donglin Peng
2025-11-21 19:07 ` Eduard Zingerman
2025-11-21 19:42 ` Eduard Zingerman
0 siblings, 2 replies; 42+ messages in thread
From: Donglin Peng @ 2025-11-20 7:25 UTC (permalink / raw)
To: Andrii Nakryiko
Cc: ast, eddyz87, zhangxiaoqin, linux-kernel, bpf, Donglin Peng,
Alan Maguire, Song Liu
On Thu, Nov 20, 2025 at 3:50 AM Andrii Nakryiko
<andrii.nakryiko@gmail.com> wrote:
>
> On Tue, Nov 18, 2025 at 7:21 PM Donglin Peng <dolinux.peng@gmail.com> wrote:
> >
> > From: Donglin Peng <pengdonglin@xiaomi.com>
> >
> > This patch adds validation to verify BTF type name sorting, enabling
> > binary search optimization for lookups.
> >
> > 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>
> > Cc: Xiaoqin Zhang <zhangxiaoqin@xiaomi.com>
> > Signed-off-by: Donglin Peng <pengdonglin@xiaomi.com>
> > ---
> > tools/lib/bpf/btf.c | 59 +++++++++++++++++++++++++++++++++++++++++++++
> > 1 file changed, 59 insertions(+)
> >
> > diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c
> > index 1d19d95da1d0..d872abff42e1 100644
> > --- a/tools/lib/bpf/btf.c
> > +++ b/tools/lib/bpf/btf.c
> > @@ -903,6 +903,64 @@ int btf__resolve_type(const struct btf *btf, __u32 type_id)
> > return type_id;
> > }
> >
> > +/* Anonymous types (with empty names) are considered greater than named types
> > + * and are sorted after them. Two anonymous types are considered equal. Named
> > + * types are compared lexicographically.
> > + */
> > +static int btf_compare_type_names(const void *a, const void *b, void *priv)
> > +{
> > + struct btf *btf = (struct btf *)priv;
> > + struct btf_type *ta = btf_type_by_id(btf, *(__u32 *)a);
> > + struct btf_type *tb = btf_type_by_id(btf, *(__u32 *)b);
> > + const char *na, *nb;
> > + bool anon_a, anon_b;
> > +
> > + na = btf__str_by_offset(btf, ta->name_off);
> > + nb = btf__str_by_offset(btf, tb->name_off);
> > + anon_a = str_is_empty(na);
> > + anon_b = str_is_empty(nb);
> > +
> > + if (anon_a && !anon_b)
> > + return 1;
> > + if (!anon_a && anon_b)
> > + return -1;
> > + if (anon_a && anon_b)
> > + return 0;
>
> any reason to hard-code that anonymous types should come *after* named
> ones? That requires custom comparison logic here and resolve_btfids,
> instead of just relying on btf__str_by_offset() returning valid empty
> string for name_off == 0 and then sorting anon types before named
> ones, following normal lexicographical sorting rules?
Thanks. I found that some kernel functions like btf_find_next_decl_tag,
bpf_core_add_cands, find_bpffs_btf_enums, and find_btf_percpu_datasec
still use linear search. Putting named types first would also help here, as
it allows anonymous types to be skipped naturally during the search.
Some of them could be refactored to use btf_find_by_name_kind, but some
would not be appropriate, such as btf_find_next_decl_tag,
bpf_core_add_cands,find_btf_percpu_datasec.
Additionally, in the linear search branch, I saw there is a NULL check for
the name returned by btf__name_by_offset. This suggests that checking
name_off == 0 alone may not be sufficient to identify an anonymous type,
which is why I used str_is_empty for a more robust check.
>
> [...]
^ permalink raw reply [flat|nested] 42+ messages in thread* Re: [RFC PATCH v7 5/7] libbpf: Implement BTF type sorting validation for binary search optimization
2025-11-20 7:25 ` Donglin Peng
@ 2025-11-21 19:07 ` Eduard Zingerman
2025-11-22 7:19 ` Donglin Peng
2025-11-21 19:42 ` Eduard Zingerman
1 sibling, 1 reply; 42+ messages in thread
From: Eduard Zingerman @ 2025-11-21 19:07 UTC (permalink / raw)
To: Donglin Peng, Andrii Nakryiko
Cc: ast, zhangxiaoqin, linux-kernel, bpf, Donglin Peng, Alan Maguire,
Song Liu
On Thu, 2025-11-20 at 15:25 +0800, Donglin Peng wrote:
> On Thu, Nov 20, 2025 at 3:50 AM Andrii Nakryiko
> <andrii.nakryiko@gmail.com> wrote:
> >
> > On Tue, Nov 18, 2025 at 7:21 PM Donglin Peng <dolinux.peng@gmail.com> wrote:
> > >
> > > From: Donglin Peng <pengdonglin@xiaomi.com>
> > >
> > > This patch adds validation to verify BTF type name sorting, enabling
> > > binary search optimization for lookups.
> > >
> > > 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>
> > > Cc: Xiaoqin Zhang <zhangxiaoqin@xiaomi.com>
> > > Signed-off-by: Donglin Peng <pengdonglin@xiaomi.com>
> > > ---
> > > tools/lib/bpf/btf.c | 59 +++++++++++++++++++++++++++++++++++++++++++++
> > > 1 file changed, 59 insertions(+)
> > >
> > > diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c
> > > index 1d19d95da1d0..d872abff42e1 100644
> > > --- a/tools/lib/bpf/btf.c
> > > +++ b/tools/lib/bpf/btf.c
> > > @@ -903,6 +903,64 @@ int btf__resolve_type(const struct btf *btf, __u32 type_id)
> > > return type_id;
> > > }
> > >
> > > +/* Anonymous types (with empty names) are considered greater than named types
> > > + * and are sorted after them. Two anonymous types are considered equal. Named
> > > + * types are compared lexicographically.
> > > + */
> > > +static int btf_compare_type_names(const void *a, const void *b, void *priv)
> > > +{
> > > + struct btf *btf = (struct btf *)priv;
> > > + struct btf_type *ta = btf_type_by_id(btf, *(__u32 *)a);
> > > + struct btf_type *tb = btf_type_by_id(btf, *(__u32 *)b);
> > > + const char *na, *nb;
> > > + bool anon_a, anon_b;
> > > +
> > > + na = btf__str_by_offset(btf, ta->name_off);
> > > + nb = btf__str_by_offset(btf, tb->name_off);
> > > + anon_a = str_is_empty(na);
> > > + anon_b = str_is_empty(nb);
> > > +
> > > + if (anon_a && !anon_b)
> > > + return 1;
> > > + if (!anon_a && anon_b)
> > > + return -1;
> > > + if (anon_a && anon_b)
> > > + return 0;
> >
> > any reason to hard-code that anonymous types should come *after* named
> > ones? That requires custom comparison logic here and resolve_btfids,
> > instead of just relying on btf__str_by_offset() returning valid empty
> > string for name_off == 0 and then sorting anon types before named
> > ones, following normal lexicographical sorting rules?
>
> Thanks. I found that some kernel functions like btf_find_next_decl_tag,
> bpf_core_add_cands, find_bpffs_btf_enums, and find_btf_percpu_datasec
> still use linear search.
- btf_find_next_decl_tag() - this function is called from:
- btf_find_decl_tag_value(), here whole scan over all BTF types is
guaranteed to happen (because btf_find_next_decl_tag() is called
twice);
- btf_prepare_func_args(), here again whole scan is guaranteed to
happen, because of the while loop starting from id == 0.
- bpf_core_add_cands() this function is called from
bpf_core_find_cands(), where it does a linear scan over all types in
kernel BTF and then a linear scan over all types in module BTFs.
(Because of how targ_start_id parameter is passed).
- find_bpffs_btf_enums() - this function does a linear scan over all
types in module BTFs.
- find_btf_percpu_datasec() - this function looks for a DATASEC with
name ".data..percpu" and returns as soon as the match is found.
Of the 4 functions above only find_btf_percpu_datasec() will return
early if BTF type with specified name is found. And it can be
converted to use btf_find_by_name_kind().
So, it appears that there should not be any performance penalty
(compared to current state of affairs) if anonymous types are put in
front. Wdyt?
> Putting named types first would also help here, as
> it allows anonymous types to be skipped naturally during the search.
> Some of them could be refactored to use btf_find_by_name_kind, but some
> would not be appropriate, such as btf_find_next_decl_tag,
> bpf_core_add_cands,find_btf_percpu_datasec.
Did you observe any performance issue if anonymous types are put in
the front?
> Additionally, in the linear search branch, I saw there is a NULL check for
> the name returned by btf__name_by_offset. This suggests that checking
> name_off == 0 alone may not be sufficient to identify an anonymous type,
> which is why I used str_is_empty for a more robust check.
>
> >
> > [...]
^ permalink raw reply [flat|nested] 42+ messages in thread* Re: [RFC PATCH v7 5/7] libbpf: Implement BTF type sorting validation for binary search optimization
2025-11-21 19:07 ` Eduard Zingerman
@ 2025-11-22 7:19 ` Donglin Peng
2025-11-22 8:50 ` Eduard Zingerman
0 siblings, 1 reply; 42+ messages in thread
From: Donglin Peng @ 2025-11-22 7:19 UTC (permalink / raw)
To: Eduard Zingerman
Cc: Andrii Nakryiko, ast, zhangxiaoqin, linux-kernel, bpf,
Donglin Peng, Alan Maguire, Song Liu
On Sat, Nov 22, 2025 at 3:07 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Thu, 2025-11-20 at 15:25 +0800, Donglin Peng wrote:
> > On Thu, Nov 20, 2025 at 3:50 AM Andrii Nakryiko
> > <andrii.nakryiko@gmail.com> wrote:
> > >
> > > On Tue, Nov 18, 2025 at 7:21 PM Donglin Peng <dolinux.peng@gmail.com> wrote:
> > > >
> > > > From: Donglin Peng <pengdonglin@xiaomi.com>
> > > >
> > > > This patch adds validation to verify BTF type name sorting, enabling
> > > > binary search optimization for lookups.
> > > >
> > > > 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>
> > > > Cc: Xiaoqin Zhang <zhangxiaoqin@xiaomi.com>
> > > > Signed-off-by: Donglin Peng <pengdonglin@xiaomi.com>
> > > > ---
> > > > tools/lib/bpf/btf.c | 59 +++++++++++++++++++++++++++++++++++++++++++++
> > > > 1 file changed, 59 insertions(+)
> > > >
> > > > diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c
> > > > index 1d19d95da1d0..d872abff42e1 100644
> > > > --- a/tools/lib/bpf/btf.c
> > > > +++ b/tools/lib/bpf/btf.c
> > > > @@ -903,6 +903,64 @@ int btf__resolve_type(const struct btf *btf, __u32 type_id)
> > > > return type_id;
> > > > }
> > > >
> > > > +/* Anonymous types (with empty names) are considered greater than named types
> > > > + * and are sorted after them. Two anonymous types are considered equal. Named
> > > > + * types are compared lexicographically.
> > > > + */
> > > > +static int btf_compare_type_names(const void *a, const void *b, void *priv)
> > > > +{
> > > > + struct btf *btf = (struct btf *)priv;
> > > > + struct btf_type *ta = btf_type_by_id(btf, *(__u32 *)a);
> > > > + struct btf_type *tb = btf_type_by_id(btf, *(__u32 *)b);
> > > > + const char *na, *nb;
> > > > + bool anon_a, anon_b;
> > > > +
> > > > + na = btf__str_by_offset(btf, ta->name_off);
> > > > + nb = btf__str_by_offset(btf, tb->name_off);
> > > > + anon_a = str_is_empty(na);
> > > > + anon_b = str_is_empty(nb);
> > > > +
> > > > + if (anon_a && !anon_b)
> > > > + return 1;
> > > > + if (!anon_a && anon_b)
> > > > + return -1;
> > > > + if (anon_a && anon_b)
> > > > + return 0;
> > >
> > > any reason to hard-code that anonymous types should come *after* named
> > > ones? That requires custom comparison logic here and resolve_btfids,
> > > instead of just relying on btf__str_by_offset() returning valid empty
> > > string for name_off == 0 and then sorting anon types before named
> > > ones, following normal lexicographical sorting rules?
> >
> > Thanks. I found that some kernel functions like btf_find_next_decl_tag,
> > bpf_core_add_cands, find_bpffs_btf_enums, and find_btf_percpu_datasec
> > still use linear search.
>
> - btf_find_next_decl_tag() - this function is called from:
> - btf_find_decl_tag_value(), here whole scan over all BTF types is
> guaranteed to happen (because btf_find_next_decl_tag() is called
> twice);
> - btf_prepare_func_args(), here again whole scan is guaranteed to
> happen, because of the while loop starting from id == 0.
Right.
> - bpf_core_add_cands() this function is called from
> bpf_core_find_cands(), where it does a linear scan over all types in
> kernel BTF and then a linear scan over all types in module BTFs.
> (Because of how targ_start_id parameter is passed).
Right.
> - find_bpffs_btf_enums() - this function does a linear scan over all
> types in module BTFs.
I think putting names ahead is helpful here, because there is a check
(info->cmd_t && info->map_t && info->prog_t && info->attach_t) to
return early. but I think it can be converted to use btf_find_by_name_kind.
> - find_btf_percpu_datasec() - this function looks for a DATASEC with
> name ".data..percpu" and returns as soon as the match is found.
>
> Of the 4 functions above only find_btf_percpu_datasec() will return
> early if BTF type with specified name is found. And it can be
> converted to use btf_find_by_name_kind().
Thanks. I’ve looked into find_btf_percpu_datasec and we can’t use
btf_find_by_name_kind here because the search scope differs. For
a module BTF, find_btf_percpu_datasec only searches within the
module’s own BTF, whereas btf_find_by_name_kind prioritizes
searching the base BTF first. Thus, placing named types ahead is
more effective here. Besides, I found that the '.data..percpu' named
type will be placed at [1] for vmlinux BTF because the prefix '.' is
smaller than any letter, so the linear search only requires one loop to
locate it. However, if we put named types at the end, it will need more
than 60,000 loops..
>
> So, it appears that there should not be any performance penalty
> (compared to current state of affairs) if anonymous types are put in
> front. Wdyt?
>
> > Putting named types first would also help here, as
> > it allows anonymous types to be skipped naturally during the search.
> > Some of them could be refactored to use btf_find_by_name_kind, but some
> > would not be appropriate, such as btf_find_next_decl_tag,
> > bpf_core_add_cands,find_btf_percpu_datasec.
>
> Did you observe any performance issue if anonymous types are put in
> the front?
No, I have not done such a test, but based on the above analysis, the
improvement
mainly comes from find_bpffs_btf_enums and find_btf_percpu_datasec.
>
> > Additionally, in the linear search branch, I saw there is a NULL check for
> > the name returned by btf__name_by_offset. This suggests that checking
> > name_off == 0 alone may not be sufficient to identify an anonymous type,
> > which is why I used str_is_empty for a more robust check.
> >
> > >
> > > [...]
^ permalink raw reply [flat|nested] 42+ messages in thread* Re: [RFC PATCH v7 5/7] libbpf: Implement BTF type sorting validation for binary search optimization
2025-11-22 7:19 ` Donglin Peng
@ 2025-11-22 8:50 ` Eduard Zingerman
2025-11-22 9:05 ` Eduard Zingerman
2025-11-22 15:59 ` Donglin Peng
0 siblings, 2 replies; 42+ messages in thread
From: Eduard Zingerman @ 2025-11-22 8:50 UTC (permalink / raw)
To: Donglin Peng
Cc: Andrii Nakryiko, ast, zhangxiaoqin, linux-kernel, bpf,
Donglin Peng, Alan Maguire, Song Liu
On Sat, 2025-11-22 at 15:19 +0800, Donglin Peng wrote:
[...]
> > - find_bpffs_btf_enums() - this function does a linear scan over all
> > types in module BTFs.
>
> I think putting names ahead is helpful here, because there is a check
> (info->cmd_t && info->map_t && info->prog_t && info->attach_t) to
> return early. but I think it can be converted to use btf_find_by_name_kind.
Oh, sorry, I somehow missed the early exit here.
But as you say, it is a combination of 4 by-name lookups, essentially.
Thus can be converted to btf_find_by_name_kind() trivially.
> > - find_btf_percpu_datasec() - this function looks for a DATASEC with
> > name ".data..percpu" and returns as soon as the match is found.
> >
> > Of the 4 functions above only find_btf_percpu_datasec() will return
> > early if BTF type with specified name is found. And it can be
> > converted to use btf_find_by_name_kind().
>
> Thanks. I’ve looked into find_btf_percpu_datasec and we can’t use
> btf_find_by_name_kind here because the search scope differs. For
> a module BTF, find_btf_percpu_datasec only searches within the
> module’s own BTF, whereas btf_find_by_name_kind prioritizes
> searching the base BTF first. Thus, placing named types ahead is
> more effective here. Besides, I found that the '.data..percpu' named
> type will be placed at [1] for vmlinux BTF because the prefix '.' is
> smaller than any letter, so the linear search only requires one loop to
> locate it. However, if we put named types at the end, it will need more
> than 60,000 loops..
But this can be easily fixed if a variant of btf_find_by_name_kind()
is provided that looks for a match only in a specific BTF. Or accepts
a start id parameter.
^ permalink raw reply [flat|nested] 42+ messages in thread
* Re: [RFC PATCH v7 5/7] libbpf: Implement BTF type sorting validation for binary search optimization
2025-11-22 8:50 ` Eduard Zingerman
@ 2025-11-22 9:05 ` Eduard Zingerman
2025-11-22 15:45 ` Donglin Peng
2025-11-22 15:59 ` Donglin Peng
1 sibling, 1 reply; 42+ messages in thread
From: Eduard Zingerman @ 2025-11-22 9:05 UTC (permalink / raw)
To: Donglin Peng
Cc: Andrii Nakryiko, ast, zhangxiaoqin, linux-kernel, bpf,
Donglin Peng, Alan Maguire, Song Liu
On Sat, 2025-11-22 at 00:50 -0800, Eduard Zingerman wrote:
[...]
> > Thanks. I’ve looked into find_btf_percpu_datasec and we can’t use
> > btf_find_by_name_kind here because the search scope differs. For
> > a module BTF, find_btf_percpu_datasec only searches within the
> > module’s own BTF, whereas btf_find_by_name_kind prioritizes
> > searching the base BTF first. Thus, placing named types ahead is
> > more effective here. Besides, I found that the '.data..percpu' named
> > type will be placed at [1] for vmlinux BTF because the prefix '.' is
> > smaller than any letter, so the linear search only requires one loop to
> > locate it. However, if we put named types at the end, it will need more
> > than 60,000 loops..
>
> But this can be easily fixed if a variant of btf_find_by_name_kind()
> is provided that looks for a match only in a specific BTF. Or accepts
> a start id parameter.
Also, I double checked, and for my vmlinux the id for '.data..percpu'
section is 110864, the last id of all. So, having all anonymous types
in front does not change status-quo compared to current implementation.
^ permalink raw reply [flat|nested] 42+ messages in thread
* Re: [RFC PATCH v7 5/7] libbpf: Implement BTF type sorting validation for binary search optimization
2025-11-22 9:05 ` Eduard Zingerman
@ 2025-11-22 15:45 ` Donglin Peng
2025-11-24 18:16 ` Eduard Zingerman
0 siblings, 1 reply; 42+ messages in thread
From: Donglin Peng @ 2025-11-22 15:45 UTC (permalink / raw)
To: Eduard Zingerman
Cc: Andrii Nakryiko, ast, zhangxiaoqin, linux-kernel, bpf,
Donglin Peng, Alan Maguire, Song Liu
On Sat, Nov 22, 2025 at 5:05 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Sat, 2025-11-22 at 00:50 -0800, Eduard Zingerman wrote:
>
> [...]
>
> > > Thanks. I’ve looked into find_btf_percpu_datasec and we can’t use
> > > btf_find_by_name_kind here because the search scope differs. For
> > > a module BTF, find_btf_percpu_datasec only searches within the
> > > module’s own BTF, whereas btf_find_by_name_kind prioritizes
> > > searching the base BTF first. Thus, placing named types ahead is
> > > more effective here. Besides, I found that the '.data..percpu' named
> > > type will be placed at [1] for vmlinux BTF because the prefix '.' is
> > > smaller than any letter, so the linear search only requires one loop to
> > > locate it. However, if we put named types at the end, it will need more
> > > than 60,000 loops..
> >
> > But this can be easily fixed if a variant of btf_find_by_name_kind()
> > is provided that looks for a match only in a specific BTF. Or accepts
> > a start id parameter.
>
> Also, I double checked, and for my vmlinux the id for '.data..percpu'
> section is 110864, the last id of all. So, having all anonymous types
> in front does not change status-quo compared to current implementation.
Yes. If types are sorted alphabetically, the '.data..percpu' section will
have ID 1 in vmlinux BTF. In this case, linear search performance is
optimal when named types are placed ahead of anonymous types.
I would like to understand the benefits of having anonymous types at the
front of named types.
^ permalink raw reply [flat|nested] 42+ messages in thread
* Re: [RFC PATCH v7 5/7] libbpf: Implement BTF type sorting validation for binary search optimization
2025-11-22 15:45 ` Donglin Peng
@ 2025-11-24 18:16 ` Eduard Zingerman
2025-11-25 10:53 ` Donglin Peng
0 siblings, 1 reply; 42+ messages in thread
From: Eduard Zingerman @ 2025-11-24 18:16 UTC (permalink / raw)
To: Donglin Peng
Cc: Andrii Nakryiko, ast, zhangxiaoqin, linux-kernel, bpf,
Donglin Peng, Alan Maguire, Song Liu
On Sat, 2025-11-22 at 23:45 +0800, Donglin Peng wrote:
> On Sat, Nov 22, 2025 at 5:05 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
> >
> > On Sat, 2025-11-22 at 00:50 -0800, Eduard Zingerman wrote:
> >
> > [...]
> >
> > > > Thanks. I’ve looked into find_btf_percpu_datasec and we can’t use
> > > > btf_find_by_name_kind here because the search scope differs. For
> > > > a module BTF, find_btf_percpu_datasec only searches within the
> > > > module’s own BTF, whereas btf_find_by_name_kind prioritizes
> > > > searching the base BTF first. Thus, placing named types ahead is
> > > > more effective here. Besides, I found that the '.data..percpu' named
> > > > type will be placed at [1] for vmlinux BTF because the prefix '.' is
> > > > smaller than any letter, so the linear search only requires one loop to
> > > > locate it. However, if we put named types at the end, it will need more
> > > > than 60,000 loops..
> > >
> > > But this can be easily fixed if a variant of btf_find_by_name_kind()
> > > is provided that looks for a match only in a specific BTF. Or accepts
> > > a start id parameter.
> >
> > Also, I double checked, and for my vmlinux the id for '.data..percpu'
> > section is 110864, the last id of all. So, having all anonymous types
> > in front does not change status-quo compared to current implementation.
>
> Yes. If types are sorted alphabetically, the '.data..percpu' section will
> have ID 1 in vmlinux BTF. In this case, linear search performance is
> optimal when named types are placed ahead of anonymous types.
>
> I would like to understand the benefits of having anonymous types at the
> front of named types.
This will allow using strcmp() instead of btf_compare_type_names(),
which we have to copy both in kernel and in libbpf. Reducing the code
size and cognitive load.
^ permalink raw reply [flat|nested] 42+ messages in thread
* Re: [RFC PATCH v7 5/7] libbpf: Implement BTF type sorting validation for binary search optimization
2025-11-24 18:16 ` Eduard Zingerman
@ 2025-11-25 10:53 ` Donglin Peng
0 siblings, 0 replies; 42+ messages in thread
From: Donglin Peng @ 2025-11-25 10:53 UTC (permalink / raw)
To: Eduard Zingerman
Cc: Andrii Nakryiko, ast, zhangxiaoqin, linux-kernel, bpf,
Donglin Peng, Alan Maguire, Song Liu
On Tue, Nov 25, 2025 at 2:16 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Sat, 2025-11-22 at 23:45 +0800, Donglin Peng wrote:
> > On Sat, Nov 22, 2025 at 5:05 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > >
> > > On Sat, 2025-11-22 at 00:50 -0800, Eduard Zingerman wrote:
> > >
> > > [...]
> > >
> > > > > Thanks. I’ve looked into find_btf_percpu_datasec and we can’t use
> > > > > btf_find_by_name_kind here because the search scope differs. For
> > > > > a module BTF, find_btf_percpu_datasec only searches within the
> > > > > module’s own BTF, whereas btf_find_by_name_kind prioritizes
> > > > > searching the base BTF first. Thus, placing named types ahead is
> > > > > more effective here. Besides, I found that the '.data..percpu' named
> > > > > type will be placed at [1] for vmlinux BTF because the prefix '.' is
> > > > > smaller than any letter, so the linear search only requires one loop to
> > > > > locate it. However, if we put named types at the end, it will need more
> > > > > than 60,000 loops..
> > > >
> > > > But this can be easily fixed if a variant of btf_find_by_name_kind()
> > > > is provided that looks for a match only in a specific BTF. Or accepts
> > > > a start id parameter.
> > >
> > > Also, I double checked, and for my vmlinux the id for '.data..percpu'
> > > section is 110864, the last id of all. So, having all anonymous types
> > > in front does not change status-quo compared to current implementation.
> >
> > Yes. If types are sorted alphabetically, the '.data..percpu' section will
> > have ID 1 in vmlinux BTF. In this case, linear search performance is
> > optimal when named types are placed ahead of anonymous types.
> >
> > I would like to understand the benefits of having anonymous types at the
> > front of named types.
>
> This will allow using strcmp() instead of btf_compare_type_names(),
> which we have to copy both in kernel and in libbpf. Reducing the code
> size and cognitive load.
Thanks, I will fix it in the next version.
^ permalink raw reply [flat|nested] 42+ messages in thread
* Re: [RFC PATCH v7 5/7] libbpf: Implement BTF type sorting validation for binary search optimization
2025-11-22 8:50 ` Eduard Zingerman
2025-11-22 9:05 ` Eduard Zingerman
@ 2025-11-22 15:59 ` Donglin Peng
1 sibling, 0 replies; 42+ messages in thread
From: Donglin Peng @ 2025-11-22 15:59 UTC (permalink / raw)
To: Eduard Zingerman
Cc: Andrii Nakryiko, ast, zhangxiaoqin, linux-kernel, bpf,
Donglin Peng, Alan Maguire, Song Liu
On Sat, Nov 22, 2025 at 4:50 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Sat, 2025-11-22 at 15:19 +0800, Donglin Peng wrote:
>
> [...]
>
> > > - find_bpffs_btf_enums() - this function does a linear scan over all
> > > types in module BTFs.
> >
> > I think putting names ahead is helpful here, because there is a check
> > (info->cmd_t && info->map_t && info->prog_t && info->attach_t) to
> > return early. but I think it can be converted to use btf_find_by_name_kind.
>
> Oh, sorry, I somehow missed the early exit here.
> But as you say, it is a combination of 4 by-name lookups, essentially.
> Thus can be converted to btf_find_by_name_kind() trivially.
>
> > > - find_btf_percpu_datasec() - this function looks for a DATASEC with
> > > name ".data..percpu" and returns as soon as the match is found.
> > >
> > > Of the 4 functions above only find_btf_percpu_datasec() will return
> > > early if BTF type with specified name is found. And it can be
> > > converted to use btf_find_by_name_kind().
> >
> > Thanks. I’ve looked into find_btf_percpu_datasec and we can’t use
> > btf_find_by_name_kind here because the search scope differs. For
> > a module BTF, find_btf_percpu_datasec only searches within the
> > module’s own BTF, whereas btf_find_by_name_kind prioritizes
> > searching the base BTF first. Thus, placing named types ahead is
> > more effective here. Besides, I found that the '.data..percpu' named
> > type will be placed at [1] for vmlinux BTF because the prefix '.' is
> > smaller than any letter, so the linear search only requires one loop to
> > locate it. However, if we put named types at the end, it will need more
> > than 60,000 loops..
>
> But this can be easily fixed if a variant of btf_find_by_name_kind()
> is provided that looks for a match only in a specific BTF. Or accepts
> a start id parameter.
Yes, but I'm not sure it's necessary to add a new parameter to
btf_find_by_name_kind for just one use case.
^ permalink raw reply [flat|nested] 42+ messages in thread
* Re: [RFC PATCH v7 5/7] libbpf: Implement BTF type sorting validation for binary search optimization
2025-11-20 7:25 ` Donglin Peng
2025-11-21 19:07 ` Eduard Zingerman
@ 2025-11-21 19:42 ` Eduard Zingerman
2025-11-22 7:32 ` Donglin Peng
1 sibling, 1 reply; 42+ messages in thread
From: Eduard Zingerman @ 2025-11-21 19:42 UTC (permalink / raw)
To: Donglin Peng, Andrii Nakryiko
Cc: ast, zhangxiaoqin, linux-kernel, bpf, Donglin Peng, Alan Maguire,
Song Liu
On Thu, 2025-11-20 at 15:25 +0800, Donglin Peng wrote:
[...]
> Additionally, in the linear search branch, I saw there is a NULL check for
> the name returned by btf__name_by_offset. This suggests that checking
> name_off == 0 alone may not be sufficient to identify an anonymous type,
> which is why I used str_is_empty for a more robust check.
btf_str_by_offset(btf, offset) returns NULL only when 'offset' is
larger then 'btf->hdr.str_len'. However, function btf_check_meta()
verifies that this shall not happen by invoking
btf_name_offset_valid() check. The btf_check_meta() is invoked for all
types by btf_check_all_metas() called from btf_parse_base(),
btf_parse_module() and btf_parse_type_sec() -> btf_parse().
So, it appears that kernel protects itself from invalid name_off
values at BTF load time.
[...]
^ permalink raw reply [flat|nested] 42+ messages in thread
* Re: [RFC PATCH v7 5/7] libbpf: Implement BTF type sorting validation for binary search optimization
2025-11-21 19:42 ` Eduard Zingerman
@ 2025-11-22 7:32 ` Donglin Peng
2025-11-22 8:38 ` Donglin Peng
0 siblings, 1 reply; 42+ messages in thread
From: Donglin Peng @ 2025-11-22 7:32 UTC (permalink / raw)
To: Eduard Zingerman
Cc: Andrii Nakryiko, ast, zhangxiaoqin, linux-kernel, bpf,
Donglin Peng, Alan Maguire, Song Liu
On Sat, Nov 22, 2025 at 3:42 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Thu, 2025-11-20 at 15:25 +0800, Donglin Peng wrote:
>
> [...]
>
> > Additionally, in the linear search branch, I saw there is a NULL check for
> > the name returned by btf__name_by_offset. This suggests that checking
> > name_off == 0 alone may not be sufficient to identify an anonymous type,
> > which is why I used str_is_empty for a more robust check.
>
> btf_str_by_offset(btf, offset) returns NULL only when 'offset' is
> larger then 'btf->hdr.str_len'. However, function btf_check_meta()
> verifies that this shall not happen by invoking
> btf_name_offset_valid() check. The btf_check_meta() is invoked for all
> types by btf_check_all_metas() called from btf_parse_base(),
> btf_parse_module() and btf_parse_type_sec() -> btf_parse().
>
> So, it appears that kernel protects itself from invalid name_off
> values at BTF load time.
Right. The kernel guarantees that btf_str_by_offsetnever returns NULL,
and there is no NULL check performed on the name returned by
btf_find_by_name_kind. The NULL check is included in the libbpf version
of the function.
>
> [...]
^ permalink raw reply [flat|nested] 42+ messages in thread
* Re: [RFC PATCH v7 5/7] libbpf: Implement BTF type sorting validation for binary search optimization
2025-11-22 7:32 ` Donglin Peng
@ 2025-11-22 8:38 ` Donglin Peng
2025-11-24 18:20 ` Eduard Zingerman
0 siblings, 1 reply; 42+ messages in thread
From: Donglin Peng @ 2025-11-22 8:38 UTC (permalink / raw)
To: Eduard Zingerman
Cc: Andrii Nakryiko, ast, zhangxiaoqin, linux-kernel, bpf,
Donglin Peng, Alan Maguire, Song Liu
On Sat, Nov 22, 2025 at 3:32 PM Donglin Peng <dolinux.peng@gmail.com> wrote:
>
> On Sat, Nov 22, 2025 at 3:42 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
> >
> > On Thu, 2025-11-20 at 15:25 +0800, Donglin Peng wrote:
> >
> > [...]
> >
> > > Additionally, in the linear search branch, I saw there is a NULL check for
> > > the name returned by btf__name_by_offset. This suggests that checking
> > > name_off == 0 alone may not be sufficient to identify an anonymous type,
> > > which is why I used str_is_empty for a more robust check.
> >
> > btf_str_by_offset(btf, offset) returns NULL only when 'offset' is
> > larger then 'btf->hdr.str_len'. However, function btf_check_meta()
> > verifies that this shall not happen by invoking
> > btf_name_offset_valid() check. The btf_check_meta() is invoked for all
> > types by btf_check_all_metas() called from btf_parse_base(),
> > btf_parse_module() and btf_parse_type_sec() -> btf_parse().
> >
> > So, it appears that kernel protects itself from invalid name_off
> > values at BTF load time.
>
> Right. The kernel guarantees that btf_str_by_offsetnever returns NULL,
> and there is no NULL check performed on the name returned by
> btf_find_by_name_kind. The NULL check is included in the libbpf version
> of the function.
Sorry — my mistake. There’s no NULL check on the name from
btf_str_by_offset in the kernel’s btf_find_by_name_kind. The
libbpf version has it.
>
> >
> > [...]
^ permalink raw reply [flat|nested] 42+ messages in thread
* Re: [RFC PATCH v7 5/7] libbpf: Implement BTF type sorting validation for binary search optimization
2025-11-22 8:38 ` Donglin Peng
@ 2025-11-24 18:20 ` Eduard Zingerman
2025-11-25 10:52 ` Donglin Peng
0 siblings, 1 reply; 42+ messages in thread
From: Eduard Zingerman @ 2025-11-24 18:20 UTC (permalink / raw)
To: Donglin Peng
Cc: Andrii Nakryiko, ast, zhangxiaoqin, linux-kernel, bpf,
Donglin Peng, Alan Maguire, Song Liu
On Sat, 2025-11-22 at 16:38 +0800, Donglin Peng wrote:
> On Sat, Nov 22, 2025 at 3:32 PM Donglin Peng <dolinux.peng@gmail.com> wrote:
> >
> > On Sat, Nov 22, 2025 at 3:42 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > >
> > > On Thu, 2025-11-20 at 15:25 +0800, Donglin Peng wrote:
> > >
> > > [...]
> > >
> > > > Additionally, in the linear search branch, I saw there is a NULL check for
> > > > the name returned by btf__name_by_offset. This suggests that checking
> > > > name_off == 0 alone may not be sufficient to identify an anonymous type,
> > > > which is why I used str_is_empty for a more robust check.
> > >
> > > btf_str_by_offset(btf, offset) returns NULL only when 'offset' is
> > > larger then 'btf->hdr.str_len'. However, function btf_check_meta()
> > > verifies that this shall not happen by invoking
> > > btf_name_offset_valid() check. The btf_check_meta() is invoked for all
> > > types by btf_check_all_metas() called from btf_parse_base(),
> > > btf_parse_module() and btf_parse_type_sec() -> btf_parse().
> > >
> > > So, it appears that kernel protects itself from invalid name_off
> > > values at BTF load time.
> >
> > Right. The kernel guarantees that btf_str_by_offsetnever returns NULL,
> > and there is no NULL check performed on the name returned by
> > btf_find_by_name_kind. The NULL check is included in the libbpf version
> > of the function.
>
> Sorry — my mistake. There’s no NULL check on the name from
> btf_str_by_offset in the kernel’s btf_find_by_name_kind. The
> libbpf version has it.
tools/lib/bpf/btf.c:btf_sanity_check() is called from btf_new(),
it calls btf_validate_type(), which does btf_validate_str().
So, ignoring the NULL case on libbpf side should be safe as well.
[...]
^ permalink raw reply [flat|nested] 42+ messages in thread
* Re: [RFC PATCH v7 5/7] libbpf: Implement BTF type sorting validation for binary search optimization
2025-11-24 18:20 ` Eduard Zingerman
@ 2025-11-25 10:52 ` Donglin Peng
0 siblings, 0 replies; 42+ messages in thread
From: Donglin Peng @ 2025-11-25 10:52 UTC (permalink / raw)
To: Eduard Zingerman
Cc: Andrii Nakryiko, ast, zhangxiaoqin, linux-kernel, bpf,
Donglin Peng, Alan Maguire, Song Liu
On Tue, Nov 25, 2025 at 2:20 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Sat, 2025-11-22 at 16:38 +0800, Donglin Peng wrote:
> > On Sat, Nov 22, 2025 at 3:32 PM Donglin Peng <dolinux.peng@gmail.com> wrote:
> > >
> > > On Sat, Nov 22, 2025 at 3:42 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > > >
> > > > On Thu, 2025-11-20 at 15:25 +0800, Donglin Peng wrote:
> > > >
> > > > [...]
> > > >
> > > > > Additionally, in the linear search branch, I saw there is a NULL check for
> > > > > the name returned by btf__name_by_offset. This suggests that checking
> > > > > name_off == 0 alone may not be sufficient to identify an anonymous type,
> > > > > which is why I used str_is_empty for a more robust check.
> > > >
> > > > btf_str_by_offset(btf, offset) returns NULL only when 'offset' is
> > > > larger then 'btf->hdr.str_len'. However, function btf_check_meta()
> > > > verifies that this shall not happen by invoking
> > > > btf_name_offset_valid() check. The btf_check_meta() is invoked for all
> > > > types by btf_check_all_metas() called from btf_parse_base(),
> > > > btf_parse_module() and btf_parse_type_sec() -> btf_parse().
> > > >
> > > > So, it appears that kernel protects itself from invalid name_off
> > > > values at BTF load time.
> > >
> > > Right. The kernel guarantees that btf_str_by_offsetnever returns NULL,
> > > and there is no NULL check performed on the name returned by
> > > btf_find_by_name_kind. The NULL check is included in the libbpf version
> > > of the function.
> >
> > Sorry — my mistake. There’s no NULL check on the name from
> > btf_str_by_offset in the kernel’s btf_find_by_name_kind. The
> > libbpf version has it.
>
> tools/lib/bpf/btf.c:btf_sanity_check() is called from btf_new(),
> it calls btf_validate_type(), which does btf_validate_str().
> So, ignoring the NULL case on libbpf side should be safe as well.
Thanks, I also noticed that too and will drop the NULL check in the next
version.
>
> [...]
^ permalink raw reply [flat|nested] 42+ messages in thread
* [RFC PATCH v7 6/7] btf: Optimize type lookup with binary search
2025-11-19 3:15 [RFC PATCH v7 0/7] Improve the performance of BTF type lookups with binary search Donglin Peng
` (4 preceding siblings ...)
2025-11-19 3:15 ` [RFC PATCH v7 5/7] libbpf: Implement BTF type sorting validation for binary search optimization Donglin Peng
@ 2025-11-19 3:15 ` Donglin Peng
2025-11-19 3:15 ` [RFC PATCH v7 7/7] btf: Add sorting validation for " Donglin Peng
6 siblings, 0 replies; 42+ messages in thread
From: Donglin Peng @ 2025-11-19 3:15 UTC (permalink / raw)
To: ast, andrii.nakryiko
Cc: eddyz87, zhangxiaoqin, linux-kernel, bpf, Donglin Peng,
Alan Maguire, Song Liu
From: Donglin Peng <pengdonglin@xiaomi.com>
Improve btf_find_by_name_kind() performance by adding binary search
support for sorted types. Falls back to linear search for compatibility.
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>
Cc: Xiaoqin Zhang <zhangxiaoqin@xiaomi.com>
Signed-off-by: Donglin Peng <pengdonglin@xiaomi.com>
---
kernel/bpf/btf.c | 83 ++++++++++++++++++++++++++++++++++++++++++------
1 file changed, 73 insertions(+), 10 deletions(-)
diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c
index 0de8fc8a0e0b..5dd2c40d4874 100644
--- a/kernel/bpf/btf.c
+++ b/kernel/bpf/btf.c
@@ -259,6 +259,7 @@ struct btf {
void *nohdr_data;
struct btf_header hdr;
u32 nr_types; /* includes VOID for base BTF */
+ u32 nr_sorted_types; /* exclude VOID for base BTF */
u32 types_size;
u32 data_size;
refcount_t refcnt;
@@ -494,6 +495,11 @@ static bool btf_type_is_modifier(const struct btf_type *t)
return false;
}
+static int btf_start_id(const struct btf *btf)
+{
+ return btf->start_id + (btf->base_btf ? 0 : 1);
+}
+
bool btf_type_is_void(const struct btf_type *t)
{
return t == &btf_void;
@@ -544,24 +550,78 @@ u32 btf_nr_types(const struct btf *btf)
return total;
}
+static s32 btf_find_by_name_kind_bsearch(const struct btf *btf, const char *name,
+ s32 start_id, s32 end_id)
+{
+ const struct btf_type *t;
+ const char *tname;
+ s32 l, r, m;
+
+ l = start_id;
+ r = end_id;
+ while (l <= r) {
+ m = l + (r - l) / 2;
+ t = btf_type_by_id(btf, m);
+ tname = btf_name_by_offset(btf, t->name_off);
+ if (strcmp(tname, name) >= 0) {
+ if (l == r)
+ return r;
+ r = m;
+ } else {
+ l = m + 1;
+ }
+ }
+
+ return btf_nr_types(btf);
+}
+
s32 btf_find_by_name_kind(const struct btf *btf, const char *name, u8 kind)
{
+ const struct btf *base_btf = btf_base_btf(btf);
const struct btf_type *t;
const char *tname;
- u32 i, total;
+ int err = -ENOENT;
- total = btf_nr_types(btf);
- for (i = 1; i < total; i++) {
- t = btf_type_by_id(btf, i);
- if (BTF_INFO_KIND(t->info) != kind)
- continue;
+ if (base_btf) {
+ err = btf_find_by_name_kind(base_btf, name, kind);
+ if (err > 0)
+ goto out;
+ }
- tname = btf_name_by_offset(btf, t->name_off);
- if (!strcmp(tname, name))
- return i;
+ if (btf->nr_sorted_types > 0) {
+ /* binary search */
+ s32 start_id, end_id;
+ u32 idx;
+
+ start_id = btf_start_id(btf);
+ end_id = start_id + btf->nr_sorted_types - 1;
+ idx = btf_find_by_name_kind_bsearch(btf, name, start_id, end_id);
+ for (; idx <= end_id; idx++) {
+ t = btf_type_by_id(btf, idx);
+ tname = btf_name_by_offset(btf, t->name_off);
+ if (strcmp(tname, name))
+ goto out;
+ if (BTF_INFO_KIND(t->info) == kind)
+ return idx;
+ }
+ } else {
+ /* linear search */
+ u32 i, total;
+
+ total = btf_nr_types(btf);
+ for (i = btf_start_id(btf); i < total; i++) {
+ t = btf_type_by_id(btf, i);
+ if (BTF_INFO_KIND(t->info) != kind)
+ continue;
+
+ tname = btf_name_by_offset(btf, t->name_off);
+ if (!strcmp(tname, name))
+ return i;
+ }
}
- return -ENOENT;
+out:
+ return err;
}
s32 bpf_find_btf_id(const char *name, u32 kind, struct btf **btf_p)
@@ -5791,6 +5851,7 @@ static struct btf *btf_parse(const union bpf_attr *attr, bpfptr_t uattr, u32 uat
goto errout;
}
env->btf = btf;
+ btf->nr_sorted_types = 0;
data = kvmalloc(attr->btf_size, GFP_KERNEL | __GFP_NOWARN);
if (!data) {
@@ -6210,6 +6271,7 @@ static struct btf *btf_parse_base(struct btf_verifier_env *env, const char *name
btf->data = data;
btf->data_size = data_size;
btf->kernel_btf = true;
+ btf->nr_sorted_types = 0;
snprintf(btf->name, sizeof(btf->name), "%s", name);
err = btf_parse_hdr(env);
@@ -6327,6 +6389,7 @@ static struct btf *btf_parse_module(const char *module_name, const void *data,
btf->start_id = base_btf->nr_types;
btf->start_str_off = base_btf->hdr.str_len;
btf->kernel_btf = true;
+ btf->nr_sorted_types = 0;
snprintf(btf->name, sizeof(btf->name), "%s", module_name);
btf->data = kvmemdup(data, data_size, GFP_KERNEL | __GFP_NOWARN);
--
2.34.1
^ permalink raw reply related [flat|nested] 42+ messages in thread* [RFC PATCH v7 7/7] btf: Add sorting validation for binary search
2025-11-19 3:15 [RFC PATCH v7 0/7] Improve the performance of BTF type lookups with binary search Donglin Peng
` (5 preceding siblings ...)
2025-11-19 3:15 ` [RFC PATCH v7 6/7] btf: Optimize type lookup with binary search Donglin Peng
@ 2025-11-19 3:15 ` Donglin Peng
6 siblings, 0 replies; 42+ messages in thread
From: Donglin Peng @ 2025-11-19 3:15 UTC (permalink / raw)
To: ast, andrii.nakryiko
Cc: eddyz87, zhangxiaoqin, linux-kernel, bpf, Donglin Peng,
Alan Maguire, Song Liu
From: Donglin Peng <pengdonglin@xiaomi.com>
Implement validation of BTF type ordering to enable efficient binary
search for sorted BTF.
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>
Cc: Xiaoqin Zhang <zhangxiaoqin@xiaomi.com>
Signed-off-by: Donglin Peng <pengdonglin@xiaomi.com>
---
kernel/bpf/btf.c | 64 ++++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 64 insertions(+)
diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c
index 5dd2c40d4874..e9d102360292 100644
--- a/kernel/bpf/btf.c
+++ b/kernel/bpf/btf.c
@@ -550,6 +550,66 @@ u32 btf_nr_types(const struct btf *btf)
return total;
}
+/* Anonymous types (with empty names) are considered greater than named types
+ * and are sorted after them. Two anonymous types are considered equal. Named
+ * types are compared lexicographically.
+ */
+static int btf_compare_type_names(const void *a, const void *b, void *priv)
+{
+ struct btf *btf = (struct btf *)priv;
+ const struct btf_type *ta = btf_type_by_id(btf, *(__u32 *)a);
+ const struct btf_type *tb = btf_type_by_id(btf, *(__u32 *)b);
+ const char *na, *nb;
+
+ if (!ta->name_off && tb->name_off)
+ return 1;
+ if (ta->name_off && !tb->name_off)
+ return -1;
+ if (!ta->name_off && !tb->name_off)
+ return 0;
+
+ na = btf_name_by_offset(btf, ta->name_off);
+ nb = btf_name_by_offset(btf, tb->name_off);
+ return strcmp(na, nb);
+}
+
+/* Verifies that BTF types are sorted in ascending order according to their
+ * names, with named types appearing before anonymous types. If the ordering
+ * is correct, counts the number of named types and updates the BTF object's
+ * nr_sorted_types field. Note that vmlinux and kernel module BTFs are sorted
+ * during the building phase, so the validation logic only needs to count the
+ * named types.
+ */
+static void btf_check_sorted(struct btf *btf)
+{
+ const struct btf_type *t;
+ int i, n, k = 0, nr_sorted_types;
+ bool skip_cmp = btf_is_kernel(btf);
+
+ if (btf->nr_types < 2)
+ return;
+
+ nr_sorted_types = 0;
+ n = btf_nr_types(btf) - 1;
+ for (i = btf_start_id(btf); i < n; i++) {
+ k = i + 1;
+ if (!skip_cmp && btf_compare_type_names(&i, &k, btf) > 0)
+ return;
+
+ t = btf_type_by_id(btf, i);
+ if (t->name_off)
+ nr_sorted_types++;
+ else if (skip_cmp)
+ break;
+ }
+
+ t = btf_type_by_id(btf, k);
+ if (t->name_off)
+ nr_sorted_types++;
+ if (nr_sorted_types)
+ btf->nr_sorted_types = nr_sorted_types;
+}
+
static s32 btf_find_by_name_kind_bsearch(const struct btf *btf, const char *name,
s32 start_id, s32 end_id)
{
@@ -5885,6 +5945,8 @@ static struct btf *btf_parse(const union bpf_attr *attr, bpfptr_t uattr, u32 uat
if (err)
goto errout;
+ btf_check_sorted(btf);
+
struct_meta_tab = btf_parse_struct_metas(&env->log, btf);
if (IS_ERR(struct_meta_tab)) {
err = PTR_ERR(struct_meta_tab);
@@ -6292,6 +6354,7 @@ static struct btf *btf_parse_base(struct btf_verifier_env *env, const char *name
if (err)
goto errout;
+ btf_check_sorted(btf);
refcount_set(&btf->refcnt, 1);
return btf;
@@ -6426,6 +6489,7 @@ static struct btf *btf_parse_module(const char *module_name, const void *data,
}
btf_verifier_env_free(env);
+ btf_check_sorted(btf);
refcount_set(&btf->refcnt, 1);
return btf;
--
2.34.1
^ permalink raw reply related [flat|nested] 42+ messages in thread