* [RFC bpf-next v8 1/9] libbpf: Add BTF permutation support for type reordering
2025-11-26 8:50 [RFC bpf-next v8 0/9] Improve the performance of BTF type lookups with binary search Donglin Peng
@ 2025-11-26 8:50 ` Donglin Peng
2025-11-26 8:50 ` [RFC bpf-next v8 2/9] selftests/bpf: Add test cases for btf__permute functionality Donglin Peng
` (7 subsequent siblings)
8 siblings, 0 replies; 10+ messages in thread
From: Donglin Peng @ 2025-11-26 8:50 UTC (permalink / raw)
To: ast, andrii.nakryiko
Cc: eddyz87, zhangxiaoqin, ihor.solodrai, linux-kernel, bpf,
pengdonglin, Alan Maguire
From: pengdonglin <pengdonglin@xiaomi.com>
Introduce btf__permute() API to allow in-place rearrangement of BTF types.
This function reorganizes BTF type order according to a provided array of
type IDs, updating all type references to maintain consistency.
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: Ihor Solodrai <ihor.solodrai@linux.dev>
Cc: Xiaoqin Zhang <zhangxiaoqin@xiaomi.com>
Signed-off-by: pengdonglin <pengdonglin@xiaomi.com>
---
tools/lib/bpf/btf.c | 119 +++++++++++++++++++++++++++++++++++++++
tools/lib/bpf/btf.h | 36 ++++++++++++
tools/lib/bpf/libbpf.map | 1 +
3 files changed, 156 insertions(+)
diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c
index 84a4b0abc8be..26ebc0234b9b 100644
--- a/tools/lib/bpf/btf.c
+++ b/tools/lib/bpf/btf.c
@@ -5868,3 +5868,122 @@ 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;
+
+ /* refer to the base BTF or VOID type */
+ if (new_type_id < p->btf->start_id)
+ return 0;
+
+ if (new_type_id >= btf__type_cnt(p->btf))
+ return -EINVAL;
+
+ *type_id = p->id_map[new_type_id - p->btf->start_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 *nt, *new_types = NULL;
+ __u32 *order_map = NULL;
+ int err = 0, i;
+ __u32 id;
+
+ if (!OPTS_VALID(opts, btf_permute_opts) || id_map_cnt != btf->nr_types)
+ return libbpf_err(-EINVAL);
+
+ /* record the sequence of types */
+ order_map = calloc(id_map_cnt, 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];
+ if (id < btf->start_id || id >= btf__type_cnt(btf)) {
+ err = -EINVAL;
+ goto done;
+ }
+ id -= btf->start_id;
+ /* cannot be mapped to the same ID */
+ if (order_map[id]) {
+ err = -EINVAL;
+ goto done;
+ }
+ order_map[id] = i + btf->start_id;
+ }
+
+ p.btf = btf;
+ p.id_map = id_map;
+ nt = new_types;
+ for (i = 0; i < id_map_cnt; i++) {
+ struct btf_field_iter it;
+ const struct btf_type *t;
+ __u32 *type_id;
+ int type_size;
+
+ id = order_map[i];
+ t = btf__type_by_id(btf, id);
+ 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;
+ }
+
+ for (nt = new_types, i = 0; i < id_map_cnt; i++) {
+ btf->type_offs[i] = nt - new_types;
+ nt += btf_type_size(nt);
+ }
+
+ 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 cc01494d6210..ba67e5457e3a 100644
--- a/tools/lib/bpf/btf.h
+++ b/tools/lib/bpf/btf.h
@@ -281,6 +281,42 @@ 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`
+ *
+ * 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] 10+ messages in thread* [RFC bpf-next v8 2/9] selftests/bpf: Add test cases for btf__permute functionality
2025-11-26 8:50 [RFC bpf-next v8 0/9] Improve the performance of BTF type lookups with binary search Donglin Peng
2025-11-26 8:50 ` [RFC bpf-next v8 1/9] libbpf: Add BTF permutation support for type reordering Donglin Peng
@ 2025-11-26 8:50 ` Donglin Peng
2025-11-26 8:50 ` [RFC bpf-next v8 3/9] tools/resolve_btfids: Support BTF sorting feature Donglin Peng
` (6 subsequent siblings)
8 siblings, 0 replies; 10+ messages in thread
From: Donglin Peng @ 2025-11-26 8:50 UTC (permalink / raw)
To: ast, andrii.nakryiko
Cc: eddyz87, zhangxiaoqin, ihor.solodrai, linux-kernel, bpf,
pengdonglin, Alan Maguire
From: pengdonglin <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
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: Ihor Solodrai <ihor.solodrai@linux.dev>
Cc: Xiaoqin Zhang <zhangxiaoqin@xiaomi.com>
Signed-off-by: pengdonglin <pengdonglin@xiaomi.com>
---
.../selftests/bpf/prog_tests/btf_permute.c | 228 ++++++++++++++++++
1 file changed, 228 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..9aa71cdf984a
--- /dev/null
+++ b/tools/testing/selftests/bpf/prog_tests/btf_permute.c
@@ -0,0 +1,228 @@
+// SPDX-License-Identifier: GPL-2.0
+/* Copyright (c) 2025 Xiaomi */
+
+#include <test_progs.h>
+#include <bpf/btf.h>
+#include "btf_helpers.h"
+
+static void permute_base_check(struct btf *btf)
+{
+ 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");
+}
+
+/* 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;
+ permute_base_check(btf);
+
+ /* id_map_cnt is invalid */
+ 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;
+ /* BTF is not modified */
+ permute_base_check(btf);
+
+ /* 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;
+ /* BTF is not modified */
+ permute_base_check(btf);
+
+ /* 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;
+ /* BTF is not modified */
+ permute_base_check(btf);
+
+done:
+ btf__free(btf);
+}
+
+static void permute_split_check(struct btf *btf)
+{
+ 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 '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");
+}
+
+/* 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;
+ permute_split_check(split_btf);
+
+ /*
+ * 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;
+ /* BTF is not modified */
+ permute_split_check(split_btf);
+
+ /* 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;
+ /* BTF is not modified */
+ permute_split_check(split_btf);
+
+ /* 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;
+ /* BTF is not modified */
+ permute_split_check(split_btf);
+
+cleanup:
+ btf__free(split_btf);
+ btf__free(base_btf);
+}
+
+void test_btf_permute(void)
+{
+ if (test__start_subtest("permute_base"))
+ test_permute_base();
+ if (test__start_subtest("permute_split"))
+ test_permute_split();
+}
--
2.34.1
^ permalink raw reply related [flat|nested] 10+ messages in thread* [RFC bpf-next v8 3/9] tools/resolve_btfids: Support BTF sorting feature
2025-11-26 8:50 [RFC bpf-next v8 0/9] Improve the performance of BTF type lookups with binary search Donglin Peng
2025-11-26 8:50 ` [RFC bpf-next v8 1/9] libbpf: Add BTF permutation support for type reordering Donglin Peng
2025-11-26 8:50 ` [RFC bpf-next v8 2/9] selftests/bpf: Add test cases for btf__permute functionality Donglin Peng
@ 2025-11-26 8:50 ` Donglin Peng
2025-11-26 8:50 ` [RFC bpf-next v8 4/9] libbpf: Optimize type lookup with binary search for sorted BTF Donglin Peng
` (5 subsequent siblings)
8 siblings, 0 replies; 10+ messages in thread
From: Donglin Peng @ 2025-11-26 8:50 UTC (permalink / raw)
To: ast, andrii.nakryiko
Cc: eddyz87, zhangxiaoqin, ihor.solodrai, linux-kernel, bpf,
pengdonglin, Alan Maguire
From: pengdonglin <pengdonglin@xiaomi.com>
This introduces a new BTF sorting phase that specifically sorts
BTF types by name in ascending order, so that the binary search
can be used to look up types.
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: Ihor Solodrai <ihor.solodrai@linux.dev>
Cc: Xiaoqin Zhang <zhangxiaoqin@xiaomi.com>
Signed-off-by: pengdonglin <pengdonglin@xiaomi.com>
---
tools/bpf/resolve_btfids/main.c | 68 +++++++++++++++++++++++++++++++++
1 file changed, 68 insertions(+)
diff --git a/tools/bpf/resolve_btfids/main.c b/tools/bpf/resolve_btfids/main.c
index 4faf16b1ba6b..1d2b08bbd8c2 100644
--- a/tools/bpf/resolve_btfids/main.c
+++ b/tools/bpf/resolve_btfids/main.c
@@ -857,6 +857,71 @@ static int dump_raw_btf(struct btf *btf, const char *out_path)
return 0;
}
+/*
+ * Sort types by name in ascending order resulting in all
+ * anonymous types being placed before named types.
+ */
+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;
+
+ na = btf__str_by_offset(btf, ta->name_off);
+ nb = btf__str_by_offset(btf, tb->name_off);
+ return strcmp(na, nb);
+}
+
+static int sort_btf_by_name(struct btf *btf)
+{
+ __u32 *permute_ids = NULL, *id_map = NULL;
+ int nr_types, i, err = 0;
+ __u32 start_id = 1, id;
+
+ if (btf__base_btf(btf))
+ start_id = btf__type_cnt(btf__base_btf(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));
+
+out:
+ free(permute_ids);
+ free(id_map);
+ return err;
+}
+
+static int btf2btf(struct object *obj)
+{
+ return sort_btf_by_name(obj->btf);
+}
+
static const char * const resolve_btfids_usage[] = {
"resolve_btfids [<options>] <ELF object>",
NULL
@@ -900,6 +965,9 @@ int main(int argc, const char **argv)
if (load_btf(&obj))
goto out;
+ if (btf2btf(&obj))
+ goto out;
+
if (elf_collect(&obj))
goto out;
--
2.34.1
^ permalink raw reply related [flat|nested] 10+ messages in thread* [RFC bpf-next v8 4/9] libbpf: Optimize type lookup with binary search for sorted BTF
2025-11-26 8:50 [RFC bpf-next v8 0/9] Improve the performance of BTF type lookups with binary search Donglin Peng
` (2 preceding siblings ...)
2025-11-26 8:50 ` [RFC bpf-next v8 3/9] tools/resolve_btfids: Support BTF sorting feature Donglin Peng
@ 2025-11-26 8:50 ` Donglin Peng
2025-11-26 8:50 ` [RFC bpf-next v8 5/9] libbpf: Verify BTF Sorting Donglin Peng
` (4 subsequent siblings)
8 siblings, 0 replies; 10+ messages in thread
From: Donglin Peng @ 2025-11-26 8:50 UTC (permalink / raw)
To: ast, andrii.nakryiko
Cc: eddyz87, zhangxiaoqin, ihor.solodrai, linux-kernel, bpf,
pengdonglin, Alan Maguire
From: pengdonglin <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 types. For unsorted BTF, the
implementation falls back to the original linear search.
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: Ihor Solodrai <ihor.solodrai@linux.dev>
Cc: Xiaoqin Zhang <zhangxiaoqin@xiaomi.com>
Signed-off-by: pengdonglin <pengdonglin@xiaomi.com>
---
tools/lib/bpf/btf.c | 103 ++++++++++++++++++++++++++++++++++----------
1 file changed, 80 insertions(+), 23 deletions(-)
diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c
index 26ebc0234b9b..7f150c869bf6 100644
--- a/tools/lib/bpf/btf.c
+++ b/tools/lib/bpf/btf.c
@@ -92,6 +92,8 @@ struct btf {
* - for split BTF counts number of types added on top of base BTF.
*/
__u32 nr_types;
+ /* the start IDs of named types in sorted BTF */
+ int sorted_start_id;
/* if not NULL, points to the base BTF on top of which the current
* split BTF is based
*/
@@ -897,46 +899,98 @@ 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_by_name_bsearch(const struct btf *btf, const char *name,
+ __s32 start_id, __s32 end_id)
{
- __u32 i, nr_types = btf__type_cnt(btf);
-
- if (!strcmp(type_name, "void"))
- return 0;
-
- 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);
-
- if (name && !strcmp(type_name, name))
- return i;
+ const struct btf_type *t;
+ const char *tname;
+ __s32 l, r, m, lmost = -ENOENT;
+ int ret;
+
+ 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);
+ ret = strcmp(tname, name);
+ if (ret < 0) {
+ l = m + 1;
+ } else {
+ if (ret == 0)
+ lmost = m;
+ r = m - 1;
+ }
}
- return libbpf_err(-ENOENT);
+ return lmost;
}
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);
+ const struct btf_type *t;
+ const char *tname;
+ __s32 idx;
+
+ if (start_id < btf->start_id) {
+ idx = btf_find_by_name_kind(btf->base_btf, start_id,
+ type_name, kind);
+ if (idx >= 0)
+ return idx;
+ start_id = btf->start_id;
+ }
- if (kind == BTF_KIND_UNKN || !strcmp(type_name, "void"))
+ if (kind == BTF_KIND_UNKN || strcmp(type_name, "void") == 0)
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->sorted_start_id > 0) {
+ __s32 end_id = btf__type_cnt(btf) - 1;
+
+ /* skip anonymous types */
+ start_id = max(start_id, btf->sorted_start_id);
+ idx = btf_find_by_name_bsearch(btf, type_name, start_id, end_id);
+ if (unlikely(idx < 0))
+ return libbpf_err(-ENOENT);
+
+ if (unlikely(kind == -1))
+ return idx;
+
+ t = btf_type_by_id(btf, idx);
+ if (likely(BTF_INFO_KIND(t->info) == kind))
+ return idx;
+
+ for (idx++; 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) != 0)
+ return libbpf_err(-ENOENT);
+ if (btf_kind(t) == kind)
+ return idx;
+ }
+ } else {
+ __u32 i, total;
- if (btf_kind(t) != kind)
- continue;
- name = btf__name_by_offset(btf, t->name_off);
- 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) == 0)
+ return i;
+ }
}
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,
__u32 kind)
{
@@ -1006,6 +1060,7 @@ static struct btf *btf_new_empty(struct btf *base_btf)
btf->fd = -1;
btf->ptr_sz = sizeof(void *);
btf->swapped_endian = false;
+ btf->sorted_start_id = 0;
if (base_btf) {
btf->base_btf = base_btf;
@@ -1057,6 +1112,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->sorted_start_id = 0;
if (base_btf) {
btf->base_btf = base_btf;
@@ -1715,6 +1771,7 @@ static void btf_invalidate_raw_data(struct btf *btf)
free(btf->raw_data_swapped);
btf->raw_data_swapped = NULL;
}
+ btf->sorted_start_id = 0;
}
/* Ensure BTF is ready to be modified (by splitting into a three memory
--
2.34.1
^ permalink raw reply related [flat|nested] 10+ messages in thread* [RFC bpf-next v8 5/9] libbpf: Verify BTF Sorting
2025-11-26 8:50 [RFC bpf-next v8 0/9] Improve the performance of BTF type lookups with binary search Donglin Peng
` (3 preceding siblings ...)
2025-11-26 8:50 ` [RFC bpf-next v8 4/9] libbpf: Optimize type lookup with binary search for sorted BTF Donglin Peng
@ 2025-11-26 8:50 ` Donglin Peng
2025-11-26 8:50 ` [RFC bpf-next v8 6/9] btf: Optimize type lookup with binary search Donglin Peng
` (3 subsequent siblings)
8 siblings, 0 replies; 10+ messages in thread
From: Donglin Peng @ 2025-11-26 8:50 UTC (permalink / raw)
To: ast, andrii.nakryiko
Cc: eddyz87, zhangxiaoqin, ihor.solodrai, linux-kernel, bpf,
pengdonglin, Alan Maguire
From: pengdonglin <pengdonglin@xiaomi.com>
This patch checks whether the BTF is sorted by name in ascending
order. If sorted, binary search will be used when looking up types.
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: Ihor Solodrai <ihor.solodrai@linux.dev>
Cc: Xiaoqin Zhang <zhangxiaoqin@xiaomi.com>
Signed-off-by: pengdonglin <pengdonglin@xiaomi.com>
---
tools/lib/bpf/btf.c | 46 ++++++++++++++++++++++++++++++++++++++++++++-
1 file changed, 45 insertions(+), 1 deletion(-)
diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c
index 7f150c869bf6..a53d24704857 100644
--- a/tools/lib/bpf/btf.c
+++ b/tools/lib/bpf/btf.c
@@ -899,6 +899,49 @@ int btf__resolve_type(const struct btf *btf, __u32 type_id)
return type_id;
}
+/*
+ * Assuming that types are sorted by name in ascending order.
+ */
+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;
+
+ na = btf__str_by_offset(btf, ta->name_off);
+ nb = btf__str_by_offset(btf, tb->name_off);
+ return strcmp(na, nb);
+}
+
+static void btf_check_sorted(struct btf *btf)
+{
+ const struct btf_type *t;
+ int i, k = 0, n;
+ __u32 sorted_start_id = 0;
+
+ if (btf->nr_types < 2)
+ return;
+
+ 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 (sorted_start_id == 0 &&
+ !str_is_empty(btf__str_by_offset(btf, t->name_off)))
+ sorted_start_id = i;
+ }
+
+ t = btf_type_by_id(btf, k);
+ if (sorted_start_id == 0 &&
+ !str_is_empty(btf__str_by_offset(btf, t->name_off)))
+ sorted_start_id = k;
+ if (sorted_start_id)
+ btf->sorted_start_id = sorted_start_id;
+}
+
static __s32 btf_find_by_name_bsearch(const struct btf *btf, const char *name,
__s32 start_id, __s32 end_id)
{
@@ -935,7 +978,7 @@ static __s32 btf_find_by_name_kind(const struct btf *btf, int start_id,
if (start_id < btf->start_id) {
idx = btf_find_by_name_kind(btf->base_btf, start_id,
- type_name, kind);
+ type_name, kind);
if (idx >= 0)
return idx;
start_id = btf->start_id;
@@ -1147,6 +1190,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] 10+ messages in thread* [RFC bpf-next v8 6/9] btf: Optimize type lookup with binary search
2025-11-26 8:50 [RFC bpf-next v8 0/9] Improve the performance of BTF type lookups with binary search Donglin Peng
` (4 preceding siblings ...)
2025-11-26 8:50 ` [RFC bpf-next v8 5/9] libbpf: Verify BTF Sorting Donglin Peng
@ 2025-11-26 8:50 ` Donglin Peng
2025-11-26 8:50 ` [RFC bpf-next v8 7/9] btf: Verify BTF Sorting Donglin Peng
` (2 subsequent siblings)
8 siblings, 0 replies; 10+ messages in thread
From: Donglin Peng @ 2025-11-26 8:50 UTC (permalink / raw)
To: ast, andrii.nakryiko
Cc: eddyz87, zhangxiaoqin, ihor.solodrai, linux-kernel, bpf,
pengdonglin, Alan Maguire
From: pengdonglin <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: Ihor Solodrai <ihor.solodrai@linux.dev>
Cc: Xiaoqin Zhang <zhangxiaoqin@xiaomi.com>
Signed-off-by: pengdonglin <pengdonglin@xiaomi.com>
---
kernel/bpf/btf.c | 85 +++++++++++++++++++++++++++++++++++++++++++-----
1 file changed, 76 insertions(+), 9 deletions(-)
diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c
index 0de8fc8a0e0b..842f9c0200e4 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 sorted_start_id;
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,21 +550,79 @@ u32 btf_nr_types(const struct btf *btf)
return total;
}
+static s32 btf_find_by_name_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, lmost = -ENOENT;
+ int ret;
+
+ 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);
+ ret = strcmp(tname, name);
+ if (ret < 0) {
+ l = m + 1;
+ } else {
+ if (ret == 0)
+ lmost = m;
+ r = m - 1;
+ }
+ }
+
+ return lmost;
+}
+
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;
+ s32 idx;
- 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) {
+ idx = btf_find_by_name_kind(base_btf, name, kind);
+ if (idx > 0)
+ return idx;
+ }
- tname = btf_name_by_offset(btf, t->name_off);
- if (!strcmp(tname, name))
- return i;
+ if (btf->sorted_start_id > 0) {
+ /* skip anonymous types */
+ s32 start_id = btf->sorted_start_id;
+ s32 end_id = btf_nr_types(btf) - 1;
+
+ idx = btf_find_by_name_bsearch(btf, name, start_id, end_id);
+ if (idx < 0)
+ return -ENOENT;
+
+ t = btf_type_by_id(btf, idx);
+ if (BTF_INFO_KIND(t->info) == kind)
+ return idx;
+
+ for (idx++; idx <= end_id; idx++) {
+ t = btf_type_by_id(btf, idx);
+ tname = btf_name_by_offset(btf, t->name_off);
+ if (strcmp(tname, name) != 0)
+ return -ENOENT;
+ if (BTF_INFO_KIND(t->info) == kind)
+ return idx;
+ }
+ } else {
+ 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) == 0)
+ return i;
+ }
}
return -ENOENT;
@@ -5791,6 +5855,7 @@ static struct btf *btf_parse(const union bpf_attr *attr, bpfptr_t uattr, u32 uat
goto errout;
}
env->btf = btf;
+ btf->sorted_start_id = 0;
data = kvmalloc(attr->btf_size, GFP_KERNEL | __GFP_NOWARN);
if (!data) {
@@ -6210,6 +6275,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->sorted_start_id = 0;
snprintf(btf->name, sizeof(btf->name), "%s", name);
err = btf_parse_hdr(env);
@@ -6327,6 +6393,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->sorted_start_id = 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] 10+ messages in thread* [RFC bpf-next v8 7/9] btf: Verify BTF Sorting
2025-11-26 8:50 [RFC bpf-next v8 0/9] Improve the performance of BTF type lookups with binary search Donglin Peng
` (5 preceding siblings ...)
2025-11-26 8:50 ` [RFC bpf-next v8 6/9] btf: Optimize type lookup with binary search Donglin Peng
@ 2025-11-26 8:50 ` Donglin Peng
2025-11-26 8:50 ` [RFC bpf-next v8 8/9] bpf: Optimize the performance of find_btf_percpu_datasec Donglin Peng
2025-11-26 8:50 ` [RFC bpf-next v8 9/9] bpf: Optimize the performance of find_bpffs_btf_enums Donglin Peng
8 siblings, 0 replies; 10+ messages in thread
From: Donglin Peng @ 2025-11-26 8:50 UTC (permalink / raw)
To: ast, andrii.nakryiko
Cc: eddyz87, zhangxiaoqin, ihor.solodrai, linux-kernel, bpf,
pengdonglin, Alan Maguire
From: pengdonglin <pengdonglin@xiaomi.com>
This patch checks whether the BTF is sorted by name in ascending order.
If sorted, binary search will be used when looking up types.
Specifically, vmlinux and kernel module BTFs are always sorted during
the build phase with anonymous types placed before named types, so we
only need to identify the starting ID of named types.
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: Ihor Solodrai <ihor.solodrai@linux.dev>
Cc: Xiaoqin Zhang <zhangxiaoqin@xiaomi.com>
Signed-off-by: pengdonglin <pengdonglin@xiaomi.com>
---
kernel/bpf/btf.c | 58 ++++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 58 insertions(+)
diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c
index 842f9c0200e4..925cb524f3a8 100644
--- a/kernel/bpf/btf.c
+++ b/kernel/bpf/btf.c
@@ -550,6 +550,60 @@ u32 btf_nr_types(const struct btf *btf)
return total;
}
+/*
+ * Assuming that types are sorted by name in ascending order.
+ */
+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;
+
+ na = btf_name_by_offset(btf, ta->name_off);
+ nb = btf_name_by_offset(btf, tb->name_off);
+ return strcmp(na, nb);
+}
+
+/* Note that vmlinux and kernel module BTFs are always sorted
+ * during the building phase.
+ */
+static void btf_check_sorted(struct btf *btf)
+{
+ const struct btf_type *t;
+ bool skip_cmp = btf_is_kernel(btf);
+ u32 sorted_start_id = 0;
+ int i, n, k = 0;
+
+ if (btf->nr_types < 2)
+ return;
+
+ 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;
+
+ if (sorted_start_id == 0) {
+ t = btf_type_by_id(btf, i);
+ if (t->name_off) {
+ sorted_start_id = i;
+ if (skip_cmp)
+ break;
+ }
+ }
+ }
+
+ if (sorted_start_id == 0) {
+ t = btf_type_by_id(btf, k);
+ if (t->name_off)
+ sorted_start_id = k;
+ }
+ if (sorted_start_id)
+ btf->sorted_start_id = sorted_start_id;
+}
+
static s32 btf_find_by_name_bsearch(const struct btf *btf, const char *name,
s32 start_id, s32 end_id)
{
@@ -5889,6 +5943,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);
@@ -6296,6 +6352,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;
@@ -6430,6 +6487,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] 10+ messages in thread* [RFC bpf-next v8 8/9] bpf: Optimize the performance of find_btf_percpu_datasec
2025-11-26 8:50 [RFC bpf-next v8 0/9] Improve the performance of BTF type lookups with binary search Donglin Peng
` (6 preceding siblings ...)
2025-11-26 8:50 ` [RFC bpf-next v8 7/9] btf: Verify BTF Sorting Donglin Peng
@ 2025-11-26 8:50 ` Donglin Peng
2025-11-26 8:50 ` [RFC bpf-next v8 9/9] bpf: Optimize the performance of find_bpffs_btf_enums Donglin Peng
8 siblings, 0 replies; 10+ messages in thread
From: Donglin Peng @ 2025-11-26 8:50 UTC (permalink / raw)
To: ast, andrii.nakryiko
Cc: eddyz87, zhangxiaoqin, ihor.solodrai, linux-kernel, bpf,
pengdonglin, Alan Maguire
From: pengdonglin <pengdonglin@xiaomi.com>
Currently, vmlinux and kernel module BTFs are unconditionally
sorted during the build phase, with named types placed at the
end. Thus, anonymous types should be skipped when starting the
search. In my vmlinux BTF, the number of anonymous types is
61,747, which means the loop count can be reduced by 61,747.
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: Ihor Solodrai <ihor.solodrai@linux.dev>
Cc: Xiaoqin Zhang <zhangxiaoqin@xiaomi.com>
Signed-off-by: pengdonglin <pengdonglin@xiaomi.com>
---
include/linux/btf.h | 1 +
kernel/bpf/btf.c | 5 +++++
kernel/bpf/verifier.c | 7 +------
3 files changed, 7 insertions(+), 6 deletions(-)
diff --git a/include/linux/btf.h b/include/linux/btf.h
index f06976ffb63f..2d28f2b22ae5 100644
--- a/include/linux/btf.h
+++ b/include/linux/btf.h
@@ -220,6 +220,7 @@ bool btf_is_module(const struct btf *btf);
bool btf_is_vmlinux(const struct btf *btf);
struct module *btf_try_get_module(const struct btf *btf);
u32 btf_nr_types(const struct btf *btf);
+u32 btf_sorted_start_id(const struct btf *btf);
struct btf *btf_base_btf(const struct btf *btf);
bool btf_type_is_i32(const struct btf_type *t);
bool btf_type_is_i64(const struct btf_type *t);
diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c
index 925cb524f3a8..205b9c3bf194 100644
--- a/kernel/bpf/btf.c
+++ b/kernel/bpf/btf.c
@@ -550,6 +550,11 @@ u32 btf_nr_types(const struct btf *btf)
return total;
}
+u32 btf_sorted_start_id(const struct btf *btf)
+{
+ return btf->sorted_start_id ?: (btf->start_id ?: 1);
+}
+
/*
* Assuming that types are sorted by name in ascending order.
*/
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 10d24073c692..367699591fb0 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -20576,12 +20576,7 @@ static int find_btf_percpu_datasec(struct btf *btf)
* types to look at only module's own BTF types.
*/
n = btf_nr_types(btf);
- if (btf_is_module(btf))
- i = btf_nr_types(btf_vmlinux);
- else
- i = 1;
-
- for(; i < n; i++) {
+ for (i = btf_sorted_start_id(btf); i < n; i++) {
t = btf_type_by_id(btf, i);
if (BTF_INFO_KIND(t->info) != BTF_KIND_DATASEC)
continue;
--
2.34.1
^ permalink raw reply related [flat|nested] 10+ messages in thread* [RFC bpf-next v8 9/9] bpf: Optimize the performance of find_bpffs_btf_enums
2025-11-26 8:50 [RFC bpf-next v8 0/9] Improve the performance of BTF type lookups with binary search Donglin Peng
` (7 preceding siblings ...)
2025-11-26 8:50 ` [RFC bpf-next v8 8/9] bpf: Optimize the performance of find_btf_percpu_datasec Donglin Peng
@ 2025-11-26 8:50 ` Donglin Peng
8 siblings, 0 replies; 10+ messages in thread
From: Donglin Peng @ 2025-11-26 8:50 UTC (permalink / raw)
To: ast, andrii.nakryiko
Cc: eddyz87, zhangxiaoqin, ihor.solodrai, linux-kernel, bpf,
pengdonglin, Alan Maguire
From: pengdonglin <pengdonglin@xiaomi.com>
Currently, vmlinux BTF is unconditionally sorted during
the build phase. The function btf_find_by_name_kind
executes the binary search branch, so find_bpffs_btf_enums
can be optimized by using btf_find_by_name_kind.
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: Ihor Solodrai <ihor.solodrai@linux.dev>
Cc: Xiaoqin Zhang <zhangxiaoqin@xiaomi.com>
Signed-off-by: pengdonglin <pengdonglin@xiaomi.com>
---
kernel/bpf/inode.c | 42 +++++++++++++++++++-----------------------
1 file changed, 19 insertions(+), 23 deletions(-)
diff --git a/kernel/bpf/inode.c b/kernel/bpf/inode.c
index 81780bcf8d25..781c2c3181a4 100644
--- a/kernel/bpf/inode.c
+++ b/kernel/bpf/inode.c
@@ -605,10 +605,18 @@ struct bpffs_btf_enums {
static int find_bpffs_btf_enums(struct bpffs_btf_enums *info)
{
+ struct {
+ const struct btf_type **type;
+ const char *name;
+ } btf_enums[] = {
+ {&info->cmd_t, "bpf_cmd"},
+ {&info->map_t, "bpf_map_type"},
+ {&info->prog_t, "bpf_prog_type"},
+ {&info->attach_t, "bpf_attach_type"},
+ };
const struct btf *btf;
const struct btf_type *t;
- const char *name;
- int i, n;
+ int i, id;
memset(info, 0, sizeof(*info));
@@ -620,30 +628,18 @@ static int find_bpffs_btf_enums(struct bpffs_btf_enums *info)
info->btf = btf;
- for (i = 1, n = btf_nr_types(btf); i < n; i++) {
- t = btf_type_by_id(btf, i);
- if (!btf_type_is_enum(t))
- continue;
+ for (i = 0; i < ARRAY_SIZE(btf_enums); i++) {
+ id = btf_find_by_name_kind(btf, btf_enums[i].name,
+ BTF_KIND_ENUM);
+ if (id < 0)
+ goto out;
- name = btf_name_by_offset(btf, t->name_off);
- if (!name)
- continue;
-
- if (strcmp(name, "bpf_cmd") == 0)
- info->cmd_t = t;
- else if (strcmp(name, "bpf_map_type") == 0)
- info->map_t = t;
- else if (strcmp(name, "bpf_prog_type") == 0)
- info->prog_t = t;
- else if (strcmp(name, "bpf_attach_type") == 0)
- info->attach_t = t;
- else
- continue;
-
- if (info->cmd_t && info->map_t && info->prog_t && info->attach_t)
- return 0;
+ t = btf_type_by_id(btf, id);
+ *btf_enums[i].type = t;
}
+ return 0;
+out:
return -ESRCH;
}
--
2.34.1
^ permalink raw reply related [flat|nested] 10+ messages in thread