Skip to contentSkip to conversation

Significantly Improve BTF Type Lookup Performance

RFC PATCH Superseded Donglin Peng 6 participants 34 messages Oct 20, 2025 – Oct 24, 2025

Subsystems (5)
Kbuild Kselftest BPF BPF selftests +1 more subsystems

v2 of 3 Superseded Latest is v3 →

lore
Share & tools
lore
#0 lore raw

v2 cover Significantly Improve BTF Type Lookup Performance

The funcgraph-args feature currently invokes btf_find_by_name_kind() frequently, which uses a linear search algorithm. With large BTF data sets like vmlinux (containing over 80,000 named types), this results in significant performance overhead.

This patch series optimizes btf_find_by_name_kind() by:
1. Sorting BTF types by kind and name to enable binary search
2. Changing the search order to check local BTF before base BTF

Performance testing shows dramatic improvement:

 # echo 1 > options/funcgraph-args
 # echo function_graph > current_tracer

Before:

 # time cat trace | wc -l
 124176
 real    0m16.154s
 user    0m0.000s
 sys     0m15.962s

After:

 # time cat trace | wc -l
 124176
 real    0m0.948s
 user    0m0.000s
 sys     0m0.973s

This represents over 20x performance improvement for BTF type lookups.

Donglin Peng (5):
btf: search local BTF before base BTF
btf: sort BTF types by kind and name to enable binary search
libbpf: check if BTF is sorted to enable binary search selftests/bpf: add tests for BTF deduplication and sorting
btf: add CONFIG_BPF_SORT_BTF_BY_KIND_NAME

 include/linux/btf.h                          |  21 ++-
 kernel/bpf/Kconfig                           |   8 +
 kernel/bpf/Makefile                          |   1 +
 kernel/bpf/btf.c                             |  36 ++--
 kernel/bpf/btf_sort.c                        |   2 +
 scripts/Makefile.btf                         |   5 +
 tools/lib/bpf/Build                          |   2 +-
 tools/lib/bpf/btf.c                          | 169 +++++++++++++++---
 tools/lib/bpf/btf.h                          |   2 +
 tools/lib/bpf/btf_sort.c                     | 159 +++++++++++++++++
 tools/lib/bpf/libbpf_internal.h              |   6 +
 tools/testing/selftests/bpf/prog_tests/btf.c | 171 +++++++++++++++++++
 12 files changed, 541 insertions(+), 41 deletions(-)
 create mode 100644 kernel/bpf/btf_sort.c
 create mode 100644 tools/lib/bpf/btf_sort.c
Signature · 1 line
2.34.1
#1 lore raw

RFC PATCH v2 1/5 btf: search local BTF before base BTF

Change btf_find_by_name_kind() to search the local BTF first, then fall back to the base BTF. This can skip traversing the large vmlinux BTF when the target type resides in a kernel module's BTF, thereby significantly improving lookup performance.

In a test searching for the btf_type of function ext2_new_inode located in the ext2 kernel module:

Before: 408631 ns
After: 499 ns

Performance improvement: ~819x faster

Cc Eduard Zingerman <[email protected]>
Cc Alexei Starovoitov <[email protected]>
Cc Andrii Nakryiko <[email protected]>
Cc Alan Maguire <[email protected]>
Cc Song Liu <[email protected]>
---
 include/linux/btf.h |  1 +
 kernel/bpf/btf.c    | 27 ++++++++++++++++++---------
 2 files changed, 19 insertions(+), 9 deletions(-)
include/linux/btf.h +1 -0
index f06976ffb63f..ddc53a7ac7cd 100644
@@ -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_type_cnt(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);
kernel/bpf/btf.c +18 -9
index 0de8fc8a0e0b..c414cf37e1bd 100644
@@ -544,22 +544,31 @@ u32 btf_nr_types(const struct btf *btf)
 	return total;
 }
 
+u32 btf_type_cnt(const struct btf *btf)
+{
+	return btf->start_id + btf->nr_types;
+}
+
 s32 btf_find_by_name_kind(const struct btf *btf, const char *name, u8 kind)
 {
 	const struct btf_type *t;
 	const char *tname;
 	u32 i, total;
 
-	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;
+	do {
+		total = btf_type_cnt(btf);
+		for (i = btf->start_id; 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;
-	}
+			tname = btf_name_by_offset(btf, t->name_off);
+			if (!strcmp(tname, name))
+				return i;
+		}
+
+		btf = btf->base_btf;
+	} while (btf);
 
 	return -ENOENT;
 }
Signature · 1 line
2.34.1
maintainer
#2 lore raw

Re: [RFC PATCH v2 1/5] btf: search local BTF before base BTF

Quoted 12 lines · Donglin Peng

Change btf_find_by_name_kind() to search the local BTF first, then fall back to the base BTF. This can skip traversing the large vmlinux BTF when the target type resides in a kernel module's BTF, thereby significantly improving lookup performance.

In a test searching for the btf_type of function ext2_new_inode located in the ext2 kernel module:

Before: 408631 ns
After: 499 ns

Performance improvement: ~819x faster

[...]

Quoted 1 line

---

The flip makes sense, but are we sure that there are no implicit expectations to return base type in case of a name conflict?

E.g. kernel/bpf/btf.c:btf_parse_struct_metas() takes a pointer to btf instance and looks for types in alloc_obj_fields array by name (e.g. "bpf_spin_lock"). This will get confused if module declares a type with the same name. Probably not a problem in this particular case, but did you inspect other uses?

#3 lore raw

Re: [RFC PATCH v2 1/5] btf: search local BTF before base BTF

Quoted 19 lines · Eduard Zingerman
Quoted 12 lines · Donglin Peng

Change btf_find_by_name_kind() to search the local BTF first, then fall back to the base BTF. This can skip traversing the large vmlinux BTF when the target type resides in a kernel module's BTF, thereby significantly improving lookup performance.

In a test searching for the btf_type of function ext2_new_inode located in the ext2 kernel module:

Before: 408631 ns
After: 499 ns

Performance improvement: ~819x faster

[...]

Quoted 1 line

---

Quoted 8 lines

The flip makes sense, but are we sure that there are no implicit expectations to return base type in case of a name conflict?

E.g. kernel/bpf/btf.c:btf_parse_struct_metas() takes a pointer to btf instance and looks for types in alloc_obj_fields array by name (e.g. "bpf_spin_lock"). This will get confused if module declares a type with the same name. Probably not a problem in this particular case, but did you inspect other uses?

Thank you for pointing this out. I haven't checked other use cases yet, and you're right that this could indeed become a real issue if there are name conflicts between local and base types. It seems difficult to prevent this behavior entirely. Do you have any suggestions on how we should handle such potential conflicts?

maintainer
#4 lore raw

Re: [RFC PATCH v2 1/5] btf: search local BTF before base BTF

Quoted 29 lines · Donglin Peng
Quoted 19 lines · Eduard Zingerman
Quoted 12 lines · Donglin Peng

Change btf_find_by_name_kind() to search the local BTF first, then fall back to the base BTF. This can skip traversing the large vmlinux BTF when the target type resides in a kernel module's BTF, thereby significantly improving lookup performance.

In a test searching for the btf_type of function ext2_new_inode located in the ext2 kernel module:

Before: 408631 ns
After: 499 ns

Performance improvement: ~819x faster

[...]

Quoted 1 line

---

Quoted 8 lines

The flip makes sense, but are we sure that there are no implicit expectations to return base type in case of a name conflict?

E.g. kernel/bpf/btf.c:btf_parse_struct_metas() takes a pointer to btf instance and looks for types in alloc_obj_fields array by name (e.g. "bpf_spin_lock"). This will get confused if module declares a type with the same name. Probably not a problem in this particular case, but did you inspect other uses?

Quoted 5 lines

Thank you for pointing this out. I haven't checked other use cases yet, and you're right that this could indeed become a real issue if there are name conflicts between local and base types. It seems difficult to prevent this behavior entirely. Do you have any suggestions on how we should handle such potential conflicts?

What are the results of the above benchmark after sorting? If things are fast enough we might not need to do this change. Otherwise, each call to btf_find_by_name_kind() should be inspected. If necessary new APIs can be added to search only in vmlinux, or only in program, or only in module BTF.

#5 lore raw

Re: [RFC PATCH v2 1/5] btf: search local BTF before base BTF

Quoted 37 lines · Eduard Zingerman
Quoted 29 lines · Donglin Peng
Quoted 19 lines · Eduard Zingerman
Quoted 12 lines · Donglin Peng

Change btf_find_by_name_kind() to search the local BTF first, then fall back to the base BTF. This can skip traversing the large vmlinux BTF when the target type resides in a kernel module's BTF, thereby significantly improving lookup performance.

In a test searching for the btf_type of function ext2_new_inode located in the ext2 kernel module:

Before: 408631 ns
After: 499 ns

Performance improvement: ~819x faster

[...]

Quoted 1 line

---

Quoted 8 lines

The flip makes sense, but are we sure that there are no implicit expectations to return base type in case of a name conflict?

E.g. kernel/bpf/btf.c:btf_parse_struct_metas() takes a pointer to btf instance and looks for types in alloc_obj_fields array by name (e.g. "bpf_spin_lock"). This will get confused if module declares a type with the same name. Probably not a problem in this particular case, but did you inspect other uses?

Quoted 5 lines

Thank you for pointing this out. I haven't checked other use cases yet, and you're right that this could indeed become a real issue if there are name conflicts between local and base types. It seems difficult to prevent this behavior entirely. Do you have any suggestions on how we should handle such potential conflicts?

Quoted 5 lines

What are the results of the above benchmark after sorting? If things are fast enough we might not need to do this change. Otherwise, each call to btf_find_by_name_kind() should be inspected. If necessary new APIs can be added to search only in vmlinux, or only in program, or only in module BTF.

Thanks for the suggestion. I'll run some benchmarks and share my findings.

#6 lore raw

RFC PATCH v2 2/5 btf: sort BTF types by kind and name to enable binary search

In reply to Donglin Peng

This patch implements sorting of BTF types by their kind and name, enabling the use of binary search for type lookups.

To share logic between kernel and libbpf, a new btf_sort.c file is introduced containing common sorting functionality.

The sorting is performed during btf__dedup() when the new sort_by_kind_name option in btf_dedup_opts is enabled.

For vmlinux and kernel module BTF, btf_check_sorted() verifies whether the types are sorted and binary search can be used.

Cc Eduard Zingerman <[email protected]>
Cc Alexei Starovoitov <[email protected]>
Cc Andrii Nakryiko <[email protected]>
Cc Alan Maguire <[email protected]>
Cc Song Liu <[email protected]>
---
 include/linux/btf.h             |  20 +++-
 kernel/bpf/Makefile             |   1 +
 kernel/bpf/btf.c                |  39 ++++----
 kernel/bpf/btf_sort.c           |   2 +
 tools/lib/bpf/Build             |   2 +-
 tools/lib/bpf/btf.c             | 163 +++++++++++++++++++++++++++-----
 tools/lib/bpf/btf.h             |   2 +
 tools/lib/bpf/btf_sort.c        | 159 +++++++++++++++++++++++++++++++
 tools/lib/bpf/libbpf_internal.h |   6 ++
 9 files changed, 347 insertions(+), 47 deletions(-)
 create mode 100644 kernel/bpf/btf_sort.c
 create mode 100644 tools/lib/bpf/btf_sort.c
include/linux/btf.h +19 -1
index ddc53a7ac7cd..c6fe5e689ab9 100644
@@ -221,7 +221,10 @@ 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_type_cnt(const struct btf *btf);
-struct btf *btf_base_btf(const struct btf *btf);
+u32 btf_start_id(const struct btf *btf);
+u32 btf_nr_sorted_types(const struct btf *btf);
+void btf_set_nr_sorted_types(struct btf *btf, u32 nr);
+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);
 bool btf_type_is_primitive(const struct btf_type *t);
@@ -595,6 +598,10 @@ int get_kern_ctx_btf_id(struct bpf_verifier_log *log, enum bpf_prog_type prog_ty
 bool btf_types_are_same(const struct btf *btf1, u32 id1,
 			const struct btf *btf2, u32 id2);
 int btf_check_iter_arg(struct btf *btf, const struct btf_type *func, int arg_idx);
+int btf_compare_type_kinds_names(const void *a, const void *b, void *priv);
+s32 find_btf_by_name_kind(const struct btf *btf, int start_id, const char *type_name,
+			  u32 kind);
+void btf_check_sorted(struct btf *btf, int start_id);
 
 static inline bool btf_type_is_struct_ptr(struct btf *btf, const struct btf_type *t)
 {
@@ -683,5 +690,16 @@ static inline int btf_check_iter_arg(struct btf *btf, const struct btf_type *fun
 {
 	return -EOPNOTSUPP;
 }
+static inline int btf_compare_type_kinds_names(const void *a, const void *b, void *priv)
+{
+	return -EOPNOTSUPP;
+}
+static inline s32 find_btf_by_name_kind(const struct btf *btf, int start_id, const char *type_name,
+			  u32 kind)
+{
+	return -EOPNOTSUPP;
+}
+static inline void btf_check_sorted(struct btf *btf, int start_id);
+{}
 #endif
 #endif
kernel/bpf/Makefile +1 -0
index 7fd0badfacb1..c9d8f986c7e1 100644
@@ -56,6 +56,7 @@ obj-$(CONFIG_BPF_SYSCALL) += kmem_cache_iter.o
 ifeq ($(CONFIG_DMA_SHARED_BUFFER),y)
 obj-$(CONFIG_BPF_SYSCALL) += dmabuf_iter.o
 endif
+obj-$(CONFIG_BPF_SYSCALL) += btf_sort.o
 
 CFLAGS_REMOVE_percpu_freelist.o = $(CC_FLAGS_FTRACE)
 CFLAGS_REMOVE_bpf_lru_list.o = $(CC_FLAGS_FTRACE)
kernel/bpf/btf.c +19 -20
index c414cf37e1bd..11b05f4eb07d 100644
@@ -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;
 	u32 types_size;
 	u32 data_size;
 	refcount_t refcnt;
@@ -544,33 +545,29 @@ u32 btf_nr_types(const struct btf *btf)
 	return total;
 }
 
-u32 btf_type_cnt(const struct btf *btf)
+u32 btf_start_id(const struct btf *btf)
 {
-	return btf->start_id + btf->nr_types;
+	return btf->start_id;
 }
 
-s32 btf_find_by_name_kind(const struct btf *btf, const char *name, u8 kind)
+u32 btf_nr_sorted_types(const struct btf *btf)
 {
-	const struct btf_type *t;
-	const char *tname;
-	u32 i, total;
-
-	do {
-		total = btf_type_cnt(btf);
-		for (i = btf->start_id; i < total; i++) {
-			t = btf_type_by_id(btf, i);
-			if (BTF_INFO_KIND(t->info) != kind)
-				continue;
+	return btf->nr_sorted_types;
+}
 
-			tname = btf_name_by_offset(btf, t->name_off);
-			if (!strcmp(tname, name))
-				return i;
-		}
+void btf_set_nr_sorted_types(struct btf *btf, u32 nr)
+{
+	btf->nr_sorted_types = nr;
+}
 
-		btf = btf->base_btf;
-	} while (btf);
+u32 btf_type_cnt(const struct btf *btf)
+{
+	return btf->start_id + btf->nr_types;
+}
 
-	return -ENOENT;
+s32 btf_find_by_name_kind(const struct btf *btf, const char *name, u8 kind)
+{
+	return find_btf_by_name_kind(btf, 1, name, kind);
 }
 
 s32 bpf_find_btf_id(const char *name, u32 kind, struct btf **btf_p)
@@ -6239,6 +6236,7 @@ static struct btf *btf_parse_base(struct btf_verifier_env *env, const char *name
 	if (err)
 		goto errout;
 
+	btf_check_sorted(btf, 1);
 	refcount_set(&btf->refcnt, 1);
 
 	return btf;
@@ -6371,6 +6369,7 @@ static struct btf *btf_parse_module(const char *module_name, const void *data,
 		base_btf = vmlinux_btf;
 	}
 
+	btf_check_sorted(btf, btf_nr_types(base_btf));
 	btf_verifier_env_free(env);
 	refcount_set(&btf->refcnt, 1);
 	return btf;
kernel/bpf/btf_sort.c new file +2 -0
new file mode 100644
index 000000000000..898f9189952c
@@ -0,0 +1,2 @@
+// SPDX-License-Identifier: (LGPL-2.1 OR BSD-2-Clause)
+#include "../../tools/lib/bpf/btf_sort.c"
tools/lib/bpf/Build +1 -1
index c80204bb72a2..ed7c2506e22d 100644
@@ -1,4 +1,4 @@
 libbpf-y := libbpf.o bpf.o nlattr.o btf.o libbpf_utils.o \
 	    netlink.o bpf_prog_linfo.o libbpf_probes.o hashmap.o \
 	    btf_dump.o ringbuf.o strset.o linker.o gen_loader.o relo_core.o \
-	    usdt.o zip.o elf.o features.o btf_iter.o btf_relocate.o
+	    usdt.o zip.o elf.o features.o btf_iter.o btf_relocate.o btf_sort.o
tools/lib/bpf/btf.c +138 -25

225 lines not on this page · raw message

tools/lib/bpf/btf.h +2 -0
index ccfd905f03df..9a7cfe6b4bb3 100644
@@ -251,6 +251,8 @@ struct btf_dedup_opts {
 	size_t sz;
 	/* optional .BTF.ext info to dedup along the main BTF info */
 	struct btf_ext *btf_ext;
+	/* Sort btf_types by kind and name */
+	bool sort_by_kind_name;
 	/* force hash collisions (used for testing) */
 	bool force_collisions;
 	size_t :0;
tools/lib/bpf/btf_sort.c new file +159 -0

159 lines not on this page · raw message

tools/lib/bpf/libbpf_internal.h +6 -0
index 35b2527bedec..f71f3e70c51c 100644
@@ -248,6 +248,12 @@ const struct btf_type *skip_mods_and_typedefs(const struct btf *btf, __u32 id, _
 const struct btf_header *btf_header(const struct btf *btf);
 void btf_set_base_btf(struct btf *btf, const struct btf *base_btf);
 int btf_relocate(struct btf *btf, const struct btf *base_btf, __u32 **id_map);
+int btf_compare_type_kinds_names(const void *a, const void *b, void *priv);
+__s32 find_btf_by_name_kind(const struct btf *btf, int start_id, const char *type_name, __u32 kind);
+void btf_check_sorted(struct btf *btf, int start_id);
+__u32 btf__start_id(const struct btf *btf);
+__u32 btf__nr_sorted_types(const struct btf *btf);
+void btf__set_nr_sorted_types(struct btf *btf, __u32 nr);
 
 static inline enum btf_func_linkage btf_func_linkage(const struct btf_type *t)
 {
Signature · 1 line
2.34.1
#7 lore raw

Re: [RFC PATCH v2 2/5] btf: sort BTF types by kind and name to enable binary search

kernel test robot noticed the following build errors:

Hi Donglin,

[This is a private test report for your RFC patch.] kernel test robot noticed the following build errors:

[auto build test ERROR on bpf-next/net]
[also build test ERROR on bpf-next/master bpf/master linus/master v6.18-rc2 next-20251020] [If your patch is applied to the wrong git tree, kindly drop us a note.
And when submitting patch, we suggest to use '--base' as documented in
https://git-scm.com/docs/git-format-patch#_base_tree_information]

url:    https://github.com/intel-lab-lkp/linux/commits/Donglin-Peng/btf-search-local-BTF-before-base-BTF/20251020-174656
base:   https://git.kernel.org/pub/scm/linux/kernel/git/bpf/bpf-next.git net
patch link:    https://lore.kernel.org/r/20251020093941.548058-3-dolinux.peng%40gmail.com
patch subject: [RFC PATCH v2 2/5] btf: sort BTF types by kind and name to enable binary search
config: x86_64-buildonly-randconfig-004-20251020 (https://download.01.org/0day-ci/archive/20251020/[email protected]/config)
compiler: gcc-14 (Debian 14.2.0-19) 14.2.0
reproduce (this is a W=1 build): (https://download.01.org/0day-ci/archive/20251020/[email protected]/reproduce)

If you fix the issue in a separate patch/commit (i.e. not just a new version of the same patch/commit), kindly add following tags
| Reported-by: kernel test robot <[email protected]>
| Closes: https://lore.kernel.org/oe-kbuild-all/[email protected]/

All error/warnings (new ones prefixed by >>):

In file included from include/linux/bpf.h:29,
from include/linux/security.h:35, from include/linux/perf_event.h:53, from include/linux/trace_events.h:10, from include/trace/syscall.h:7, from include/linux/syscalls.h:95, from include/linux/syscalls_api.h:1, from kernel/sched/sched.h:61, from kernel/sched/rq-offsets.c:5:

>> include/linux/btf.h:703:1: error: expected identifier or '(' before '{' token
     703 | {}
         | ^
>> include/linux/btf.h:702:20: warning: 'btf_check_sorted' declared 'static' but never defined [-Wunused-function]
     702 | static inline void btf_check_sorted(struct btf *btf, int start_id);
         |                    ^~~~~~~~~~~~~~~~

make[3]: *** [scripts/Makefile.build:182: kernel/sched/rq-offsets.s] Error 1 shuffle=1795504952 make[3]: Target 'prepare' not remade because of errors.
make[2]: *** [Makefile:1280: prepare0] Error 2 shuffle=1795504952
make[2]: Target 'prepare' not remade because of errors.
make[1]: *** [Makefile:248: __sub-make] Error 2 shuffle=1795504952
make[1]: Target 'prepare' not remade because of errors.
make: *** [Makefile:248: __sub-make] Error 2 shuffle=1795504952
make: Target 'prepare' not remade because of errors.

vim +703 include/linux/btf.h

642
643 static inline const char *btf_name_by_offset(const struct btf *btf,
644 u32 offset)
645 {
646 return NULL;
647 }
648 static inline u32 *btf_kfunc_id_set_contains(const struct btf *btf,
649 u32 kfunc_btf_id,
650 struct bpf_prog *prog)
651
652 {
653 return NULL;
654 }
655 static inline int register_btf_kfunc_id_set(enum bpf_prog_type prog_type,
656 const struct btf_kfunc_id_set *s)
657 {
658 return 0;
659 }
660 static inline s32 btf_find_dtor_kfunc(struct btf *btf, u32 btf_id)
661 {
662 return -ENOENT;
663 }
664 static inline int register_btf_id_dtor_kfuncs(const struct btf_id_dtor_kfunc *dtors,
665 u32 add_cnt, struct module *owner)
666 {
667 return 0;
668 }
669 static inline struct btf_struct_meta *btf_find_struct_meta(const struct btf *btf, u32 btf_id)
670 {
671 return NULL;
672 }
673 static inline bool
674 btf_is_prog_ctx_type(struct bpf_verifier_log *log, const struct btf *btf,
675 const struct btf_type *t, enum bpf_prog_type prog_type,
676 int arg)
677 {
678 return false;
679 }
680 static inline int get_kern_ctx_btf_id(struct bpf_verifier_log *log,
681 enum bpf_prog_type prog_type) {
682 return -EINVAL;
683 }
684 static inline bool btf_types_are_same(const struct btf *btf1, u32 id1,
685 const struct btf *btf2, u32 id2)
686 {
687 return false;
688 }
689 static inline int btf_check_iter_arg(struct btf *btf, const struct btf_type *func, int arg_idx)
690 {
691 return -EOPNOTSUPP;
692 }
693 static inline int btf_compare_type_kinds_names(const void *a, const void *b, void *priv)
694 {
695 return -EOPNOTSUPP;
696 }
697 static inline s32 find_btf_by_name_kind(const struct btf *btf, int start_id, const char *type_name,
698 u32 kind)
699 {
700 return -EOPNOTSUPP;
701 }

 > 702	static inline void btf_check_sorted(struct btf *btf, int start_id);
 > 703	{}
Signature · 2 lines
0-DAY CI Kernel Test Service
https://github.com/intel/lkp-tests/wiki
#8 lore raw

Re: [RFC PATCH v2 2/5] btf: sort BTF types by kind and name to enable binary search

In reply to Donglin Peng
kernel test robot noticed the following build errors:

Hi Donglin,

[This is a private test report for your RFC patch.] kernel test robot noticed the following build errors:

[auto build test ERROR on bpf-next/net]
[also build test ERROR on bpf-next/master bpf/master linus/master v6.18-rc2 next-20251020] [If your patch is applied to the wrong git tree, kindly drop us a note.
And when submitting patch, we suggest to use '--base' as documented in
https://git-scm.com/docs/git-format-patch#_base_tree_information]

url:    https://github.com/intel-lab-lkp/linux/commits/Donglin-Peng/btf-search-local-BTF-before-base-BTF/20251020-174656
base:   https://git.kernel.org/pub/scm/linux/kernel/git/bpf/bpf-next.git net
patch link:    https://lore.kernel.org/r/20251020093941.548058-3-dolinux.peng%40gmail.com
patch subject: [RFC PATCH v2 2/5] btf: sort BTF types by kind and name to enable binary search
config: i386-buildonly-randconfig-003-20251021 (https://download.01.org/0day-ci/archive/20251021/[email protected]/config)
compiler: clang version 20.1.8 (https://github.com/llvm/llvm-project 87f0227cb60147a26a1eeb4fb06e3b505e9c7261)
reproduce (this is a W=1 build): (https://download.01.org/0day-ci/archive/20251021/[email protected]/reproduce)

If you fix the issue in a separate patch/commit (i.e. not just a new version of the same patch/commit), kindly add following tags
| Reported-by: kernel test robot <[email protected]>
| Closes: https://lore.kernel.org/oe-kbuild-all/[email protected]/

All errors (new ones prefixed by >>):

In file included from kernel/sched/rq-offsets.c:5:
In file included from kernel/sched/sched.h:61:
In file included from include/linux/syscalls_api.h:1:
In file included from include/linux/syscalls.h:95:
In file included from include/trace/syscall.h:7:
In file included from include/linux/trace_events.h:10:
In file included from include/linux/perf_event.h:53:
In file included from include/linux/security.h:35:
In file included from include/linux/bpf.h:29:

>> include/linux/btf.h:703:1: error: expected identifier or '('
     703 | {}
         | ^

1 error generated.
make[3]: *** [scripts/Makefile.build:182: kernel/sched/rq-offsets.s] Error 1 shuffle=3611665597 make[3]: Target 'prepare' not remade because of errors.
make[2]: *** [Makefile:1280: prepare0] Error 2 shuffle=3611665597
make[2]: Target 'prepare' not remade because of errors.
make[1]: *** [Makefile:248: __sub-make] Error 2 shuffle=3611665597
make[1]: Target 'prepare' not remade because of errors.
make: *** [Makefile:248: __sub-make] Error 2 shuffle=3611665597
make: Target 'prepare' not remade because of errors.

vim +703 include/linux/btf.h

642
643 static inline const char *btf_name_by_offset(const struct btf *btf,
644 u32 offset)
645 {
646 return NULL;
647 }
648 static inline u32 *btf_kfunc_id_set_contains(const struct btf *btf,
649 u32 kfunc_btf_id,
650 struct bpf_prog *prog)
651
652 {
653 return NULL;
654 }
655 static inline int register_btf_kfunc_id_set(enum bpf_prog_type prog_type,
656 const struct btf_kfunc_id_set *s)
657 {
658 return 0;
659 }
660 static inline s32 btf_find_dtor_kfunc(struct btf *btf, u32 btf_id)
661 {
662 return -ENOENT;
663 }
664 static inline int register_btf_id_dtor_kfuncs(const struct btf_id_dtor_kfunc *dtors,
665 u32 add_cnt, struct module *owner)
666 {
667 return 0;
668 }
669 static inline struct btf_struct_meta *btf_find_struct_meta(const struct btf *btf, u32 btf_id)
670 {
671 return NULL;
672 }
673 static inline bool
674 btf_is_prog_ctx_type(struct bpf_verifier_log *log, const struct btf *btf,
675 const struct btf_type *t, enum bpf_prog_type prog_type,
676 int arg)
677 {
678 return false;
679 }
680 static inline int get_kern_ctx_btf_id(struct bpf_verifier_log *log,
681 enum bpf_prog_type prog_type) {
682 return -EINVAL;
683 }
684 static inline bool btf_types_are_same(const struct btf *btf1, u32 id1,
685 const struct btf *btf2, u32 id2)
686 {
687 return false;
688 }
689 static inline int btf_check_iter_arg(struct btf *btf, const struct btf_type *func, int arg_idx)
690 {
691 return -EOPNOTSUPP;
692 }
693 static inline int btf_compare_type_kinds_names(const void *a, const void *b, void *priv)
694 {
695 return -EOPNOTSUPP;
696 }
697 static inline s32 find_btf_by_name_kind(const struct btf *btf, int start_id, const char *type_name,
698 u32 kind)
699 {
700 return -EOPNOTSUPP;
701 }
702 static inline void btf_check_sorted(struct btf *btf, int start_id);

 > 703	{}
Signature · 2 lines
0-DAY CI Kernel Test Service
https://github.com/intel/lkp-tests/wiki
#9 lore raw

Re: [RFC PATCH v2 2/5] btf: sort BTF types by kind and name to enable binary search

In reply to Donglin Peng
Quoted 12 lines · Donglin Peng

This patch implements sorting of BTF types by their kind and name, enabling the use of binary search for type lookups.

To share logic between kernel and libbpf, a new btf_sort.c file is introduced containing common sorting functionality.

The sorting is performed during btf__dedup() when the new sort_by_kind_name option in btf_dedup_opts is enabled.

For vmlinux and kernel module BTF, btf_check_sorted() verifies whether the types are sorted and binary search can be used.

this looks great! one thing that might make libbpf integration easier though (and Andrii can probably best answer if it's actually a problem)
- would it be possible to separate the libbpf and non-libbpf parts here; i.e have a patch that adds the libbpf stuff first, then re-use it in a separate patch for kernel sorting?

Quoted 607 lines
Cc Eduard Zingerman <[email protected]>
Cc Alexei Starovoitov <[email protected]>
Cc Andrii Nakryiko <[email protected]>
Cc Alan Maguire <[email protected]>
Cc Song Liu <[email protected]>
---
 include/linux/btf.h             |  20 +++-
 kernel/bpf/Makefile             |   1 +
 kernel/bpf/btf.c                |  39 ++++----
 kernel/bpf/btf_sort.c           |   2 +
 tools/lib/bpf/Build             |   2 +-
 tools/lib/bpf/btf.c             | 163 +++++++++++++++++++++++++++-----
 tools/lib/bpf/btf.h             |   2 +
 tools/lib/bpf/btf_sort.c        | 159 +++++++++++++++++++++++++++++++
 tools/lib/bpf/libbpf_internal.h |   6 ++
 9 files changed, 347 insertions(+), 47 deletions(-)
 create mode 100644 kernel/bpf/btf_sort.c
 create mode 100644 tools/lib/bpf/btf_sort.c
include/linux/btf.h +19 -1
index ddc53a7ac7cd..c6fe5e689ab9 100644
@@ -221,7 +221,10 @@ 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_type_cnt(const struct btf *btf);
-struct btf *btf_base_btf(const struct btf *btf);
+u32 btf_start_id(const struct btf *btf);
+u32 btf_nr_sorted_types(const struct btf *btf);
+void btf_set_nr_sorted_types(struct btf *btf, u32 nr);
+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);
 bool btf_type_is_primitive(const struct btf_type *t);
@@ -595,6 +598,10 @@ int get_kern_ctx_btf_id(struct bpf_verifier_log *log, enum bpf_prog_type prog_ty
 bool btf_types_are_same(const struct btf *btf1, u32 id1,
 			const struct btf *btf2, u32 id2);
 int btf_check_iter_arg(struct btf *btf, const struct btf_type *func, int arg_idx);
+int btf_compare_type_kinds_names(const void *a, const void *b, void *priv);
+s32 find_btf_by_name_kind(const struct btf *btf, int start_id, const char *type_name,
+			  u32 kind);
+void btf_check_sorted(struct btf *btf, int start_id);
 
 static inline bool btf_type_is_struct_ptr(struct btf *btf, const struct btf_type *t)
 {
@@ -683,5 +690,16 @@ static inline int btf_check_iter_arg(struct btf *btf, const struct btf_type *fun
 {
 	return -EOPNOTSUPP;
 }
+static inline int btf_compare_type_kinds_names(const void *a, const void *b, void *priv)
+{
+	return -EOPNOTSUPP;
+}
+static inline s32 find_btf_by_name_kind(const struct btf *btf, int start_id, const char *type_name,
+			  u32 kind)
+{
+	return -EOPNOTSUPP;
+}
+static inline void btf_check_sorted(struct btf *btf, int start_id);
+{}
 #endif
 #endif
kernel/bpf/Makefile +1 -0
index 7fd0badfacb1..c9d8f986c7e1 100644
@@ -56,6 +56,7 @@ obj-$(CONFIG_BPF_SYSCALL) += kmem_cache_iter.o
 ifeq ($(CONFIG_DMA_SHARED_BUFFER),y)
 obj-$(CONFIG_BPF_SYSCALL) += dmabuf_iter.o
 endif
+obj-$(CONFIG_BPF_SYSCALL) += btf_sort.o
 
 CFLAGS_REMOVE_percpu_freelist.o = $(CC_FLAGS_FTRACE)
 CFLAGS_REMOVE_bpf_lru_list.o = $(CC_FLAGS_FTRACE)
kernel/bpf/btf.c +19 -20
index c414cf37e1bd..11b05f4eb07d 100644
@@ -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;
 	u32 types_size;
 	u32 data_size;
 	refcount_t refcnt;
@@ -544,33 +545,29 @@ u32 btf_nr_types(const struct btf *btf)
 	return total;
 }
 
-u32 btf_type_cnt(const struct btf *btf)
+u32 btf_start_id(const struct btf *btf)
 {
-	return btf->start_id + btf->nr_types;
+	return btf->start_id;
 }
 
-s32 btf_find_by_name_kind(const struct btf *btf, const char *name, u8 kind)
+u32 btf_nr_sorted_types(const struct btf *btf)
 {
-	const struct btf_type *t;
-	const char *tname;
-	u32 i, total;
-
-	do {
-		total = btf_type_cnt(btf);
-		for (i = btf->start_id; i < total; i++) {
-			t = btf_type_by_id(btf, i);
-			if (BTF_INFO_KIND(t->info) != kind)
-				continue;
+	return btf->nr_sorted_types;
+}
 
-			tname = btf_name_by_offset(btf, t->name_off);
-			if (!strcmp(tname, name))
-				return i;
-		}
+void btf_set_nr_sorted_types(struct btf *btf, u32 nr)
+{
+	btf->nr_sorted_types = nr;
+}
 
-		btf = btf->base_btf;
-	} while (btf);
+u32 btf_type_cnt(const struct btf *btf)
+{
+	return btf->start_id + btf->nr_types;
+}
 
-	return -ENOENT;
+s32 btf_find_by_name_kind(const struct btf *btf, const char *name, u8 kind)
+{
+	return find_btf_by_name_kind(btf, 1, name, kind);
 }
 
 s32 bpf_find_btf_id(const char *name, u32 kind, struct btf **btf_p)
@@ -6239,6 +6236,7 @@ static struct btf *btf_parse_base(struct btf_verifier_env *env, const char *name
 	if (err)
 		goto errout;
 
+	btf_check_sorted(btf, 1);
 	refcount_set(&btf->refcnt, 1);
 
 	return btf;
@@ -6371,6 +6369,7 @@ static struct btf *btf_parse_module(const char *module_name, const void *data,
 		base_btf = vmlinux_btf;
 	}
 
+	btf_check_sorted(btf, btf_nr_types(base_btf));
 	btf_verifier_env_free(env);
 	refcount_set(&btf->refcnt, 1);
 	return btf;
kernel/bpf/btf_sort.c new file +2 -0
new file mode 100644
index 000000000000..898f9189952c
@@ -0,0 +1,2 @@
+// SPDX-License-Identifier: (LGPL-2.1 OR BSD-2-Clause)
+#include "../../tools/lib/bpf/btf_sort.c"
tools/lib/bpf/Build +1 -1
index c80204bb72a2..ed7c2506e22d 100644
@@ -1,4 +1,4 @@
 libbpf-y := libbpf.o bpf.o nlattr.o btf.o libbpf_utils.o \
 	    netlink.o bpf_prog_linfo.o libbpf_probes.o hashmap.o \
 	    btf_dump.o ringbuf.o strset.o linker.o gen_loader.o relo_core.o \
-	    usdt.o zip.o elf.o features.o btf_iter.o btf_relocate.o
+	    usdt.o zip.o elf.o features.o btf_iter.o btf_relocate.o btf_sort.o
tools/lib/bpf/btf.c +138 -25
index 18907f0fcf9f..87e47f0b78ba 100644
@@ -1,6 +1,9 @@
 // SPDX-License-Identifier: (LGPL-2.1 OR BSD-2-Clause)
 /* Copyright (c) 2018 Facebook */
 
+#ifndef _GNU_SOURCE
+#define _GNU_SOURCE
+#endif
 #include <byteswap.h>
 #include <endian.h>
 #include <stdio.h>
@@ -92,6 +95,9 @@ struct btf {
 	 *   - for split BTF counts number of types added on top of base BTF.
 	 */
 	__u32 nr_types;
+	/* number of named types in this BTF instance for binary search
+	 */
+	__u32 nr_sorted_types;
 	/* if not NULL, points to the base BTF on top of which the current
 	 * split BTF is based
 	 */
@@ -619,6 +625,21 @@ __u32 btf__type_cnt(const struct btf *btf)
 	return btf->start_id + btf->nr_types;
 }
 
+__u32 btf__start_id(const struct btf *btf)
+{
+	return btf->start_id;
+}
+
+__u32 btf__nr_sorted_types(const struct btf *btf)
+{
+	return btf->nr_sorted_types;
+}
+
+void btf__set_nr_sorted_types(struct btf *btf, __u32 nr)
+{
+	btf->nr_sorted_types = nr;
+}
+
 const struct btf *btf__base_btf(const struct btf *btf)
 {
 	return btf->base_btf;
@@ -915,38 +936,16 @@ __s32 btf__find_by_name(const struct btf *btf, const char *type_name)
 	return libbpf_err(-ENOENT);
 }
 
-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(-ENOENT);
-}
-
 __s32 btf__find_by_name_kind_own(const struct btf *btf, const char *type_name,
 				 __u32 kind)
 {
-	return btf_find_by_name_kind(btf, btf->start_id, type_name, kind);
+	return find_btf_by_name_kind(btf, btf->start_id, type_name, kind);
 }
 
 __s32 btf__find_by_name_kind(const struct btf *btf, const char *type_name,
 			     __u32 kind)
 {
-	return btf_find_by_name_kind(btf, 1, type_name, kind);
+	return find_btf_by_name_kind(btf, 1, type_name, kind);
 }
 
 static bool btf_is_modifiable(const struct btf *btf)
@@ -3411,6 +3410,7 @@ static int btf_dedup_struct_types(struct btf_dedup *d);
 static int btf_dedup_ref_types(struct btf_dedup *d);
 static int btf_dedup_resolve_fwds(struct btf_dedup *d);
 static int btf_dedup_compact_types(struct btf_dedup *d);
+static int btf_dedup_compact_and_sort_types(struct btf_dedup *d);
 static int btf_dedup_remap_types(struct btf_dedup *d);
 
 /*
@@ -3600,7 +3600,7 @@ int btf__dedup(struct btf *btf, const struct btf_dedup_opts *opts)
 		pr_debug("btf_dedup_ref_types failed: %s\n", errstr(err));
 		goto done;
 	}
-	err = btf_dedup_compact_types(d);
+	err = btf_dedup_compact_and_sort_types(d);
 	if (err < 0) {
 		pr_debug("btf_dedup_compact_types failed: %s\n", errstr(err));
 		goto done;
@@ -3649,6 +3649,8 @@ struct btf_dedup {
 	 * BTF is considered to be immutable.
 	 */
 	bool hypot_adjust_canon;
+	/* Sort btf_types by kind and time */
+	bool sort_by_kind_name;
 	/* Various option modifying behavior of algorithm */
 	struct btf_dedup_opts opts;
 	/* temporary strings deduplication state */
@@ -3741,6 +3743,7 @@ static struct btf_dedup *btf_dedup_new(struct btf *btf, const struct btf_dedup_o
 
 	d->btf = btf;
 	d->btf_ext = OPTS_GET(opts, btf_ext, NULL);
+	d->sort_by_kind_name = OPTS_GET(opts, sort_by_kind_name, false);
 
 	d->dedup_table = hashmap__new(hash_fn, btf_dedup_equal_fn, NULL);
 	if (IS_ERR(d->dedup_table)) {
@@ -5288,6 +5291,116 @@ static int btf_dedup_compact_types(struct btf_dedup *d)
 	return 0;
 }
 
+static __u32 *get_sorted_canon_types(struct btf_dedup *d, __u32 *cnt)
+{
+	int i, j, id, types_cnt = 0;
+	__u32 *sorted_ids;
+
+	for (i = 0, id = d->btf->start_id; i < d->btf->nr_types; i++, id++)
+		if (d->map[id] == id)
+			++types_cnt;
+
+	sorted_ids = calloc(types_cnt, sizeof(*sorted_ids));
+	if (!sorted_ids)
+		return NULL;
+
+	for (j = 0, i = 0, id = d->btf->start_id; i < d->btf->nr_types; i++, id++)
+		if (d->map[id] == id)
+			sorted_ids[j++] = id;
+
+	qsort_r(sorted_ids, types_cnt, sizeof(*sorted_ids),
+		btf_compare_type_kinds_names, d->btf);
+
+	*cnt = types_cnt;
+
+	return sorted_ids;
+}
+
+/*
+ * Compact and sort BTF types.
+ *
+ * Similar to btf_dedup_compact_types, but additionally sorts the btf_types.
+ */
+static int btf__dedup_compact_and_sort_types(struct btf_dedup *d)
+{
+	__u32 canon_types_cnt = 0, canon_types_len = 0;
+	__u32 *new_offs = NULL, *canon_types = NULL;
+	const struct btf_type *t;
+	void *p, *new_types = NULL;
+	int i, id, len, err;
+
+	/* we are going to reuse hypot_map to store compaction remapping */
+	d->hypot_map[0] = 0;
+	/* base BTF types are not renumbered */
+	for (id = 1; id < d->btf->start_id; id++)
+		d->hypot_map[id] = id;
+	for (i = 0, id = d->btf->start_id; i < d->btf->nr_types; i++, id++)
+		d->hypot_map[id] = BTF_UNPROCESSED_ID;
+
+	canon_types = get_sorted_canon_types(d, &canon_types_cnt);
+	if (!canon_types) {
+		err = -ENOMEM;
+		goto out_err;
+	}
+
+	for (i = 0; i < canon_types_cnt; i++) {
+		id = canon_types[i];
+		t = btf__type_by_id(d->btf, id);
+		len = btf_type_size(t);
+		if (len < 0) {
+			err = len;
+			goto out_err;
+		}
+		canon_types_len += len;
+	}
+
+	new_offs = calloc(canon_types_cnt, sizeof(*new_offs));
+	new_types = calloc(canon_types_len, 1);
+	if (!new_types || !new_offs) {
+		err = -ENOMEM;
+		goto out_err;
+	}
+
+	p = new_types;
+
+	for (i = 0; i < canon_types_cnt; i++) {
+		id = canon_types[i];
+		t = btf__type_by_id(d->btf, id);
+		len = btf_type_size(t);
+		memcpy(p, t, len);
+		d->hypot_map[id] = d->btf->start_id + i;
+		new_offs[i] = p - new_types;
+		p += len;
+	}
+
+	/* shrink struct btf's internal types index and update btf_header */
+	free(d->btf->types_data);
+	free(d->btf->type_offs);
+	d->btf->types_data = new_types;
+	d->btf->type_offs = new_offs;
+	d->btf->types_data_cap = canon_types_len;
+	d->btf->type_offs_cap = canon_types_cnt;
+	d->btf->nr_types = canon_types_cnt;
+	d->btf->hdr->type_len = canon_types_len;
+	d->btf->hdr->str_off = d->btf->hdr->type_len;
+	d->btf->raw_size = d->btf->hdr->hdr_len + d->btf->hdr->type_len + d->btf->hdr->str_len;
+	free(canon_types);
+	return 0;
+
+out_err:
+	free(canon_types);
+	free(new_types);
+	free(new_offs);
+	return err;
+}
+
+static int btf_dedup_compact_and_sort_types(struct btf_dedup *d)
+{
+	if (d->sort_by_kind_name)
+		return btf__dedup_compact_and_sort_types(d);
+	return btf_dedup_compact_types(d);
+}
+
 /*
  * Figure out final (deduplicated and compacted) type ID for provided original
  * `type_id` by first resolving it into corresponding canonical type ID and
tools/lib/bpf/btf.h +2 -0
index ccfd905f03df..9a7cfe6b4bb3 100644
@@ -251,6 +251,8 @@ struct btf_dedup_opts {
 	size_t sz;
 	/* optional .BTF.ext info to dedup along the main BTF info */
 	struct btf_ext *btf_ext;
+	/* Sort btf_types by kind and name */
+	bool sort_by_kind_name;
 	/* force hash collisions (used for testing) */
 	bool force_collisions;
 	size_t :0;
tools/lib/bpf/btf_sort.c new file +159 -0
new file mode 100644
index 000000000000..2ad4a56f1c08
@@ -0,0 +1,159 @@
+// SPDX-License-Identifier: (LGPL-2.1 OR BSD-2-Clause)
+
+#ifndef _GNU_SOURCE
+#define _GNU_SOURCE
+#endif
+
+#ifdef __KERNEL__
+#include <linux/bpf.h>
+#include <linux/btf.h>
+#include <linux/string.h>
+
+#define btf_type_by_id				(struct btf_type *)btf_type_by_id
+#define btf__str_by_offset			btf_str_by_offset
+#define btf__name_by_offset			btf_name_by_offset
+#define btf__type_cnt				btf_nr_types
+#define btf__start_id				btf_start_id
+#define btf__nr_sorted_types			btf_nr_sorted_types
+#define btf__set_nr_sorted_types		btf_set_nr_sorted_types
+#define btf__base_btf				btf_base_btf
+#define libbpf_err(x)				x
+
+#else
+
+#include "btf.h"
+#include "bpf.h"
+#include "libbpf.h"
+#include "libbpf_internal.h"
+
+#endif /* __KERNEL__ */
+
+/* Skip the sorted check if number of btf_types is below threshold
+ */
+#define BTF_CHECK_SORT_THRESHOLD  8
+
+struct btf;
+
+static int cmp_btf_kind_name(int ka, const char *na, int kb, const char *nb)
+{
+	return (ka - kb) ?: strcmp(na, nb);
+}
+
+/*
+ * Sort BTF types by kind and name in ascending order, placing named types
+ * before anonymous ones.
+ */
+int btf_compare_type_kinds_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;
+	int ka, kb;
+
+	/* ta w/o name is greater than tb */
+	if (!ta->name_off && tb->name_off)
+		return 1;
+	/* tb w/o name is smaller than ta */
+	if (ta->name_off && !tb->name_off)
+		return -1;
+
+	ka = btf_kind(ta);
+	kb = btf_kind(tb);
+	na = btf__str_by_offset(btf, ta->name_off);
+	nb = btf__str_by_offset(btf, tb->name_off);
+
+	return cmp_btf_kind_name(ka, na, kb, nb);
+}
+
+__s32 find_btf_by_name_kind(const struct btf *btf, int start_id,
+				   const char *type_name, __u32 kind)
+{
+	const struct btf_type *t;
+	const char *tname;
+	__u32 i, total;
+
+	if (kind == BTF_KIND_UNKN || !strcmp(type_name, "void"))
+		return 0;
+
+	do {
+		if (btf__nr_sorted_types(btf)) {
+			/* binary search */
+			__s32 start, end, mid, found = -1;
+			int ret;
+
+			start = btf__start_id(btf);
+			end = start + btf__nr_sorted_types(btf) - 1;
+			/* found the leftmost btf_type that matches */
+			while(start <= end) {
+				mid = start + (end - start) / 2;
+				t = btf_type_by_id(btf, mid);
+				tname = btf__name_by_offset(btf, t->name_off);
+				ret = cmp_btf_kind_name(BTF_INFO_KIND(t->info), tname,
+							kind, type_name);
+				if (ret == 0)
+					found = mid;
+				if (ret < 0)
+					start = mid + 1;
+				else if (ret >= 0)
+					end = mid - 1;
+			}
+
+			if (found != -1)
+				return found;
+		} else {
+			/* linear search */
+			total = btf__type_cnt(btf);
+			for (i = btf__start_id(btf); i < total; i++) {
+				t = btf_type_by_id(btf, i);
+				if (btf_kind(t) != kind)
+					continue;
+
+				tname = btf__name_by_offset(btf, t->name_off);
+				if (tname && !strcmp(tname, type_name))
+					return i;
+			}
+		}
+
+		btf = btf__base_btf(btf);
+	} while (btf && btf__start_id(btf) >= start_id);
+
+	return libbpf_err(-ENOENT);
+}
+
+void btf_check_sorted(struct btf *btf, int start_id)
+{
+	const struct btf_type *t;
+	int i, n, nr_sorted_types;
+
+	n = btf__type_cnt(btf);
+	if ((n - start_id) < BTF_CHECK_SORT_THRESHOLD)
+		return;
+
+	n--;
+	nr_sorted_types = 0;
+	for (i = start_id; i < n; i++) {
+		int k = i + 1;
+
+		t = btf_type_by_id(btf, i);
+		if (!btf__str_by_offset(btf, t->name_off))
+			return;
+
+		t = btf_type_by_id(btf, k);
+		if (!btf__str_by_offset(btf, t->name_off))
+			return;
+
+		if (btf_compare_type_kinds_names(&i, &k, btf) > 0)
+			return;
+
+		if (t->name_off)
+			nr_sorted_types++;
+	}
+
+	t = btf_type_by_id(btf, start_id);
+	if (t->name_off)
+		nr_sorted_types++;
+	if (nr_sorted_types >= BTF_CHECK_SORT_THRESHOLD)
+		btf__set_nr_sorted_types(btf, nr_sorted_types);
+}
+
tools/lib/bpf/libbpf_internal.h +6 -0
index 35b2527bedec..f71f3e70c51c 100644
@@ -248,6 +248,12 @@ const struct btf_type *skip_mods_and_typedefs(const struct btf *btf, __u32 id, _
 const struct btf_header *btf_header(const struct btf *btf);
 void btf_set_base_btf(struct btf *btf, const struct btf *base_btf);
 int btf_relocate(struct btf *btf, const struct btf *base_btf, __u32 **id_map);
+int btf_compare_type_kinds_names(const void *a, const void *b, void *priv);
+__s32 find_btf_by_name_kind(const struct btf *btf, int start_id, const char *type_name, __u32 kind);
+void btf_check_sorted(struct btf *btf, int start_id);
+__u32 btf__start_id(const struct btf *btf);
+__u32 btf__nr_sorted_types(const struct btf *btf);
+void btf__set_nr_sorted_types(struct btf *btf, __u32 nr);
 
 static inline enum btf_func_linkage btf_func_linkage(const struct btf_type *t)
 {
#10 lore raw

Re: [RFC PATCH v2 2/5] btf: sort BTF types by kind and name to enable binary search

Quoted 15 lines · Alan Maguire
Quoted 12 lines · Donglin Peng

This patch implements sorting of BTF types by their kind and name, enabling the use of binary search for type lookups.

To share logic between kernel and libbpf, a new btf_sort.c file is introduced containing common sorting functionality.

The sorting is performed during btf__dedup() when the new sort_by_kind_name option in btf_dedup_opts is enabled.

For vmlinux and kernel module BTF, btf_check_sorted() verifies whether the types are sorted and binary search can be used.

Quoted 5 lines

this looks great! one thing that might make libbpf integration easier though (and Andrii can probably best answer if it's actually a problem)
- would it be possible to separate the libbpf and non-libbpf parts here; i.e have a patch that adds the libbpf stuff first, then re-use it in a separate patch for kernel sorting?

Thanks for the suggestion, I will split it in the next version.

Quoted 609 lines
Quoted 608 lines
Cc Eduard Zingerman <[email protected]>
Cc Alexei Starovoitov <[email protected]>
Cc Andrii Nakryiko <[email protected]>
Cc Alan Maguire <[email protected]>
Cc Song Liu <[email protected]>
---
 include/linux/btf.h             |  20 +++-
 kernel/bpf/Makefile             |   1 +
 kernel/bpf/btf.c                |  39 ++++----
 kernel/bpf/btf_sort.c           |   2 +
 tools/lib/bpf/Build             |   2 +-
 tools/lib/bpf/btf.c             | 163 +++++++++++++++++++++++++++-----
 tools/lib/bpf/btf.h             |   2 +
 tools/lib/bpf/btf_sort.c        | 159 +++++++++++++++++++++++++++++++
 tools/lib/bpf/libbpf_internal.h |   6 ++
 9 files changed, 347 insertions(+), 47 deletions(-)
 create mode 100644 kernel/bpf/btf_sort.c
 create mode 100644 tools/lib/bpf/btf_sort.c
include/linux/btf.h +19 -1
index ddc53a7ac7cd..c6fe5e689ab9 100644
@@ -221,7 +221,10 @@ 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_type_cnt(const struct btf *btf);
-struct btf *btf_base_btf(const struct btf *btf);
+u32 btf_start_id(const struct btf *btf);
+u32 btf_nr_sorted_types(const struct btf *btf);
+void btf_set_nr_sorted_types(struct btf *btf, u32 nr);
+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);
 bool btf_type_is_primitive(const struct btf_type *t);
@@ -595,6 +598,10 @@ int get_kern_ctx_btf_id(struct bpf_verifier_log *log, enum bpf_prog_type prog_ty
 bool btf_types_are_same(const struct btf *btf1, u32 id1,
                      const struct btf *btf2, u32 id2);
 int btf_check_iter_arg(struct btf *btf, const struct btf_type *func, int arg_idx);
+int btf_compare_type_kinds_names(const void *a, const void *b, void *priv);
+s32 find_btf_by_name_kind(const struct btf *btf, int start_id, const char *type_name,
+                       u32 kind);
+void btf_check_sorted(struct btf *btf, int start_id);
 
 static inline bool btf_type_is_struct_ptr(struct btf *btf, const struct btf_type *t)
 {
@@ -683,5 +690,16 @@ static inline int btf_check_iter_arg(struct btf *btf, const struct btf_type *fun
 {
      return -EOPNOTSUPP;
 }
+static inline int btf_compare_type_kinds_names(const void *a, const void *b, void *priv)
+{
+     return -EOPNOTSUPP;
+}
+static inline s32 find_btf_by_name_kind(const struct btf *btf, int start_id, const char *type_name,
+                       u32 kind)
+{
+     return -EOPNOTSUPP;
+}
+static inline void btf_check_sorted(struct btf *btf, int start_id);
+{}
 #endif
 #endif
kernel/bpf/Makefile +1 -0
index 7fd0badfacb1..c9d8f986c7e1 100644
@@ -56,6 +56,7 @@ obj-$(CONFIG_BPF_SYSCALL) += kmem_cache_iter.o
 ifeq ($(CONFIG_DMA_SHARED_BUFFER),y)
 obj-$(CONFIG_BPF_SYSCALL) += dmabuf_iter.o
 endif
+obj-$(CONFIG_BPF_SYSCALL) += btf_sort.o
 
 CFLAGS_REMOVE_percpu_freelist.o = $(CC_FLAGS_FTRACE)
 CFLAGS_REMOVE_bpf_lru_list.o = $(CC_FLAGS_FTRACE)
kernel/bpf/btf.c +19 -20
index c414cf37e1bd..11b05f4eb07d 100644
@@ -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;
      u32 types_size;
      u32 data_size;
      refcount_t refcnt;
@@ -544,33 +545,29 @@ u32 btf_nr_types(const struct btf *btf)
      return total;
 }
 
-u32 btf_type_cnt(const struct btf *btf)
+u32 btf_start_id(const struct btf *btf)
 {
-     return btf->start_id + btf->nr_types;
+     return btf->start_id;
 }
 
-s32 btf_find_by_name_kind(const struct btf *btf, const char *name, u8 kind)
+u32 btf_nr_sorted_types(const struct btf *btf)
 {
-     const struct btf_type *t;
-     const char *tname;
-     u32 i, total;
-
-     do {
-             total = btf_type_cnt(btf);
-             for (i = btf->start_id; i < total; i++) {
-                     t = btf_type_by_id(btf, i);
-                     if (BTF_INFO_KIND(t->info) != kind)
-                             continue;
+     return btf->nr_sorted_types;
+}
 
-                     tname = btf_name_by_offset(btf, t->name_off);
-                     if (!strcmp(tname, name))
-                             return i;
-             }
+void btf_set_nr_sorted_types(struct btf *btf, u32 nr)
+{
+     btf->nr_sorted_types = nr;
+}
 
-             btf = btf->base_btf;
-     } while (btf);
+u32 btf_type_cnt(const struct btf *btf)
+{
+     return btf->start_id + btf->nr_types;
+}
 
-     return -ENOENT;
+s32 btf_find_by_name_kind(const struct btf *btf, const char *name, u8 kind)
+{
+     return find_btf_by_name_kind(btf, 1, name, kind);
 }
 
 s32 bpf_find_btf_id(const char *name, u32 kind, struct btf **btf_p)
@@ -6239,6 +6236,7 @@ static struct btf *btf_parse_base(struct btf_verifier_env *env, const char *name
      if (err)
              goto errout;
 
+     btf_check_sorted(btf, 1);
      refcount_set(&btf->refcnt, 1);
 
      return btf;
@@ -6371,6 +6369,7 @@ static struct btf *btf_parse_module(const char *module_name, const void *data,
              base_btf = vmlinux_btf;
      }
 
+     btf_check_sorted(btf, btf_nr_types(base_btf));
      btf_verifier_env_free(env);
      refcount_set(&btf->refcnt, 1);
      return btf;
kernel/bpf/btf_sort.c new file +2 -0
new file mode 100644
index 000000000000..898f9189952c
@@ -0,0 +1,2 @@
+// SPDX-License-Identifier: (LGPL-2.1 OR BSD-2-Clause)
+#include "../../tools/lib/bpf/btf_sort.c"
tools/lib/bpf/Build +1 -1
index c80204bb72a2..ed7c2506e22d 100644
@@ -1,4 +1,4 @@
 libbpf-y := libbpf.o bpf.o nlattr.o btf.o libbpf_utils.o \
          netlink.o bpf_prog_linfo.o libbpf_probes.o hashmap.o \
          btf_dump.o ringbuf.o strset.o linker.o gen_loader.o relo_core.o \
-         usdt.o zip.o elf.o features.o btf_iter.o btf_relocate.o
+         usdt.o zip.o elf.o features.o btf_iter.o btf_relocate.o btf_sort.o
tools/lib/bpf/btf.c +138 -25
index 18907f0fcf9f..87e47f0b78ba 100644
@@ -1,6 +1,9 @@
 // SPDX-License-Identifier: (LGPL-2.1 OR BSD-2-Clause)
 /* Copyright (c) 2018 Facebook */
 
+#ifndef _GNU_SOURCE
+#define _GNU_SOURCE
+#endif
 #include <byteswap.h>
 #include <endian.h>
 #include <stdio.h>
@@ -92,6 +95,9 @@ struct btf {
       *   - for split BTF counts number of types added on top of base BTF.
       */
      __u32 nr_types;
+     /* number of named types in this BTF instance for binary search
+      */
+     __u32 nr_sorted_types;
      /* if not NULL, points to the base BTF on top of which the current
       * split BTF is based
       */
@@ -619,6 +625,21 @@ __u32 btf__type_cnt(const struct btf *btf)
      return btf->start_id + btf->nr_types;
 }
 
+__u32 btf__start_id(const struct btf *btf)
+{
+     return btf->start_id;
+}
+
+__u32 btf__nr_sorted_types(const struct btf *btf)
+{
+     return btf->nr_sorted_types;
+}
+
+void btf__set_nr_sorted_types(struct btf *btf, __u32 nr)
+{
+     btf->nr_sorted_types = nr;
+}
+
 const struct btf *btf__base_btf(const struct btf *btf)
 {
      return btf->base_btf;
@@ -915,38 +936,16 @@ __s32 btf__find_by_name(const struct btf *btf, const char *type_name)
      return libbpf_err(-ENOENT);
 }
 
-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(-ENOENT);
-}
-
 __s32 btf__find_by_name_kind_own(const struct btf *btf, const char *type_name,
                               __u32 kind)
 {
-     return btf_find_by_name_kind(btf, btf->start_id, type_name, kind);
+     return find_btf_by_name_kind(btf, btf->start_id, type_name, kind);
 }
 
 __s32 btf__find_by_name_kind(const struct btf *btf, const char *type_name,
                           __u32 kind)
 {
-     return btf_find_by_name_kind(btf, 1, type_name, kind);
+     return find_btf_by_name_kind(btf, 1, type_name, kind);
 }
 
 static bool btf_is_modifiable(const struct btf *btf)
@@ -3411,6 +3410,7 @@ static int btf_dedup_struct_types(struct btf_dedup *d);
 static int btf_dedup_ref_types(struct btf_dedup *d);
 static int btf_dedup_resolve_fwds(struct btf_dedup *d);
 static int btf_dedup_compact_types(struct btf_dedup *d);
+static int btf_dedup_compact_and_sort_types(struct btf_dedup *d);
 static int btf_dedup_remap_types(struct btf_dedup *d);
 
 /*
@@ -3600,7 +3600,7 @@ int btf__dedup(struct btf *btf, const struct btf_dedup_opts *opts)
              pr_debug("btf_dedup_ref_types failed: %s\n", errstr(err));
              goto done;
      }
-     err = btf_dedup_compact_types(d);
+     err = btf_dedup_compact_and_sort_types(d);
      if (err < 0) {
              pr_debug("btf_dedup_compact_types failed: %s\n", errstr(err));
              goto done;
@@ -3649,6 +3649,8 @@ struct btf_dedup {
       * BTF is considered to be immutable.
       */
      bool hypot_adjust_canon;
+     /* Sort btf_types by kind and time */
+     bool sort_by_kind_name;
      /* Various option modifying behavior of algorithm */
      struct btf_dedup_opts opts;
      /* temporary strings deduplication state */
@@ -3741,6 +3743,7 @@ static struct btf_dedup *btf_dedup_new(struct btf *btf, const struct btf_dedup_o
 
      d->btf = btf;
      d->btf_ext = OPTS_GET(opts, btf_ext, NULL);
+     d->sort_by_kind_name = OPTS_GET(opts, sort_by_kind_name, false);
 
      d->dedup_table = hashmap__new(hash_fn, btf_dedup_equal_fn, NULL);
      if (IS_ERR(d->dedup_table)) {
@@ -5288,6 +5291,116 @@ static int btf_dedup_compact_types(struct btf_dedup *d)
      return 0;
 }
 
+static __u32 *get_sorted_canon_types(struct btf_dedup *d, __u32 *cnt)
+{
+     int i, j, id, types_cnt = 0;
+     __u32 *sorted_ids;
+
+     for (i = 0, id = d->btf->start_id; i < d->btf->nr_types; i++, id++)
+             if (d->map[id] == id)
+                     ++types_cnt;
+
+     sorted_ids = calloc(types_cnt, sizeof(*sorted_ids));
+     if (!sorted_ids)
+             return NULL;
+
+     for (j = 0, i = 0, id = d->btf->start_id; i < d->btf->nr_types; i++, id++)
+             if (d->map[id] == id)
+                     sorted_ids[j++] = id;
+
+     qsort_r(sorted_ids, types_cnt, sizeof(*sorted_ids),
+             btf_compare_type_kinds_names, d->btf);
+
+     *cnt = types_cnt;
+
+     return sorted_ids;
+}
+
+/*
+ * Compact and sort BTF types.
+ *
+ * Similar to btf_dedup_compact_types, but additionally sorts the btf_types.
+ */
+static int btf__dedup_compact_and_sort_types(struct btf_dedup *d)
+{
+     __u32 canon_types_cnt = 0, canon_types_len = 0;
+     __u32 *new_offs = NULL, *canon_types = NULL;
+     const struct btf_type *t;
+     void *p, *new_types = NULL;
+     int i, id, len, err;
+
+     /* we are going to reuse hypot_map to store compaction remapping */
+     d->hypot_map[0] = 0;
+     /* base BTF types are not renumbered */
+     for (id = 1; id < d->btf->start_id; id++)
+             d->hypot_map[id] = id;
+     for (i = 0, id = d->btf->start_id; i < d->btf->nr_types; i++, id++)
+             d->hypot_map[id] = BTF_UNPROCESSED_ID;
+
+     canon_types = get_sorted_canon_types(d, &canon_types_cnt);
+     if (!canon_types) {
+             err = -ENOMEM;
+             goto out_err;
+     }
+
+     for (i = 0; i < canon_types_cnt; i++) {
+             id = canon_types[i];
+             t = btf__type_by_id(d->btf, id);
+             len = btf_type_size(t);
+             if (len < 0) {
+                     err = len;
+                     goto out_err;
+             }
+             canon_types_len += len;
+     }
+
+     new_offs = calloc(canon_types_cnt, sizeof(*new_offs));
+     new_types = calloc(canon_types_len, 1);
+     if (!new_types || !new_offs) {
+             err = -ENOMEM;
+             goto out_err;
+     }
+
+     p = new_types;
+
+     for (i = 0; i < canon_types_cnt; i++) {
+             id = canon_types[i];
+             t = btf__type_by_id(d->btf, id);
+             len = btf_type_size(t);
+             memcpy(p, t, len);
+             d->hypot_map[id] = d->btf->start_id + i;
+             new_offs[i] = p - new_types;
+             p += len;
+     }
+
+     /* shrink struct btf's internal types index and update btf_header */
+     free(d->btf->types_data);
+     free(d->btf->type_offs);
+     d->btf->types_data = new_types;
+     d->btf->type_offs = new_offs;
+     d->btf->types_data_cap = canon_types_len;
+     d->btf->type_offs_cap = canon_types_cnt;
+     d->btf->nr_types = canon_types_cnt;
+     d->btf->hdr->type_len = canon_types_len;
+     d->btf->hdr->str_off = d->btf->hdr->type_len;
+     d->btf->raw_size = d->btf->hdr->hdr_len + d->btf->hdr->type_len + d->btf->hdr->str_len;
+     free(canon_types);
+     return 0;
+
+out_err:
+     free(canon_types);
+     free(new_types);
+     free(new_offs);
+     return err;
+}
+
+static int btf_dedup_compact_and_sort_types(struct btf_dedup *d)
+{
+     if (d->sort_by_kind_name)
+             return btf__dedup_compact_and_sort_types(d);
+     return btf_dedup_compact_types(d);
+}
+
 /*
  * Figure out final (deduplicated and compacted) type ID for provided original
  * `type_id` by first resolving it into corresponding canonical type ID and
tools/lib/bpf/btf.h +2 -0
index ccfd905f03df..9a7cfe6b4bb3 100644
@@ -251,6 +251,8 @@ struct btf_dedup_opts {
      size_t sz;
      /* optional .BTF.ext info to dedup along the main BTF info */
      struct btf_ext *btf_ext;
+     /* Sort btf_types by kind and name */
+     bool sort_by_kind_name;
      /* force hash collisions (used for testing) */
      bool force_collisions;
      size_t :0;
tools/lib/bpf/btf_sort.c new file +159 -0
new file mode 100644
index 000000000000..2ad4a56f1c08
@@ -0,0 +1,159 @@
+// SPDX-License-Identifier: (LGPL-2.1 OR BSD-2-Clause)
+
+#ifndef _GNU_SOURCE
+#define _GNU_SOURCE
+#endif
+
+#ifdef __KERNEL__
+#include <linux/bpf.h>
+#include <linux/btf.h>
+#include <linux/string.h>
+
+#define btf_type_by_id                               (struct btf_type *)btf_type_by_id
+#define btf__str_by_offset                   btf_str_by_offset
+#define btf__name_by_offset                  btf_name_by_offset
+#define btf__type_cnt                                btf_nr_types
+#define btf__start_id                                btf_start_id
+#define btf__nr_sorted_types                 btf_nr_sorted_types
+#define btf__set_nr_sorted_types             btf_set_nr_sorted_types
+#define btf__base_btf                                btf_base_btf
+#define libbpf_err(x)                                x
+
+#else
+
+#include "btf.h"
+#include "bpf.h"
+#include "libbpf.h"
+#include "libbpf_internal.h"
+
+#endif /* __KERNEL__ */
+
+/* Skip the sorted check if number of btf_types is below threshold
+ */
+#define BTF_CHECK_SORT_THRESHOLD  8
+
+struct btf;
+
+static int cmp_btf_kind_name(int ka, const char *na, int kb, const char *nb)
+{
+     return (ka - kb) ?: strcmp(na, nb);
+}
+
+/*
+ * Sort BTF types by kind and name in ascending order, placing named types
+ * before anonymous ones.
+ */
+int btf_compare_type_kinds_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;
+     int ka, kb;
+
+     /* ta w/o name is greater than tb */
+     if (!ta->name_off && tb->name_off)
+             return 1;
+     /* tb w/o name is smaller than ta */
+     if (ta->name_off && !tb->name_off)
+             return -1;
+
+     ka = btf_kind(ta);
+     kb = btf_kind(tb);
+     na = btf__str_by_offset(btf, ta->name_off);
+     nb = btf__str_by_offset(btf, tb->name_off);
+
+     return cmp_btf_kind_name(ka, na, kb, nb);
+}
+
+__s32 find_btf_by_name_kind(const struct btf *btf, int start_id,
+                                const char *type_name, __u32 kind)
+{
+     const struct btf_type *t;
+     const char *tname;
+     __u32 i, total;
+
+     if (kind == BTF_KIND_UNKN || !strcmp(type_name, "void"))
+             return 0;
+
+     do {
+             if (btf__nr_sorted_types(btf)) {
+                     /* binary search */
+                     __s32 start, end, mid, found = -1;
+                     int ret;
+
+                     start = btf__start_id(btf);
+                     end = start + btf__nr_sorted_types(btf) - 1;
+                     /* found the leftmost btf_type that matches */
+                     while(start <= end) {
+                             mid = start + (end - start) / 2;
+                             t = btf_type_by_id(btf, mid);
+                             tname = btf__name_by_offset(btf, t->name_off);
+                             ret = cmp_btf_kind_name(BTF_INFO_KIND(t->info), tname,
+                                                     kind, type_name);
+                             if (ret == 0)
+                                     found = mid;
+                             if (ret < 0)
+                                     start = mid + 1;
+                             else if (ret >= 0)
+                                     end = mid - 1;
+                     }
+
+                     if (found != -1)
+                             return found;
+             } else {
+                     /* linear search */
+                     total = btf__type_cnt(btf);
+                     for (i = btf__start_id(btf); i < total; i++) {
+                             t = btf_type_by_id(btf, i);
+                             if (btf_kind(t) != kind)
+                                     continue;
+
+                             tname = btf__name_by_offset(btf, t->name_off);
+                             if (tname && !strcmp(tname, type_name))
+                                     return i;
+                     }
+             }
+
+             btf = btf__base_btf(btf);
+     } while (btf && btf__start_id(btf) >= start_id);
+
+     return libbpf_err(-ENOENT);
+}
+
+void btf_check_sorted(struct btf *btf, int start_id)
+{
+     const struct btf_type *t;
+     int i, n, nr_sorted_types;
+
+     n = btf__type_cnt(btf);
+     if ((n - start_id) < BTF_CHECK_SORT_THRESHOLD)
+             return;
+
+     n--;
+     nr_sorted_types = 0;
+     for (i = start_id; i < n; i++) {
+             int k = i + 1;
+
+             t = btf_type_by_id(btf, i);
+             if (!btf__str_by_offset(btf, t->name_off))
+                     return;
+
+             t = btf_type_by_id(btf, k);
+             if (!btf__str_by_offset(btf, t->name_off))
+                     return;
+
+             if (btf_compare_type_kinds_names(&i, &k, btf) > 0)
+                     return;
+
+             if (t->name_off)
+                     nr_sorted_types++;
+     }
+
+     t = btf_type_by_id(btf, start_id);
+     if (t->name_off)
+             nr_sorted_types++;
+     if (nr_sorted_types >= BTF_CHECK_SORT_THRESHOLD)
+             btf__set_nr_sorted_types(btf, nr_sorted_types);
+}
+
tools/lib/bpf/libbpf_internal.h +6 -0
index 35b2527bedec..f71f3e70c51c 100644
@@ -248,6 +248,12 @@ const struct btf_type *skip_mods_and_typedefs(const struct btf *btf, __u32 id, _
 const struct btf_header *btf_header(const struct btf *btf);
 void btf_set_base_btf(struct btf *btf, const struct btf *base_btf);
 int btf_relocate(struct btf *btf, const struct btf *base_btf, __u32 **id_map);
+int btf_compare_type_kinds_names(const void *a, const void *b, void *priv);
+__s32 find_btf_by_name_kind(const struct btf *btf, int start_id, const char *type_name, __u32 kind);
+void btf_check_sorted(struct btf *btf, int start_id);
+__u32 btf__start_id(const struct btf *btf);
+__u32 btf__nr_sorted_types(const struct btf *btf);
+void btf__set_nr_sorted_types(struct btf *btf, __u32 nr);
 
 static inline enum btf_func_linkage btf_func_linkage(const struct btf_type *t)
 {
maintainer
#11 lore raw

Re: [RFC PATCH v2 2/5] btf: sort BTF types by kind and name to enable binary search

In reply to Donglin Peng
Quoted 8 lines · Donglin Peng

This patch implements sorting of BTF types by their kind and name, enabling the use of binary search for type lookups.

To share logic between kernel and libbpf, a new btf_sort.c file is introduced containing common sorting functionality.

The sorting is performed during btf__dedup() when the new sort_by_kind_name option in btf_dedup_opts is enabled.

Do we really need this option? Dedup is free to rearrange btf types anyway, so why not sort always? Is execution time a concern?

Quoted 2 lines

For vmlinux and kernel module BTF, btf_check_sorted() verifies whether the types are sorted and binary search can be used.

[...]

Quoted 49 lines
kernel/bpf/btf.c +10 -18
index c414cf37e1bd..11b05f4eb07d 100644
@@ -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;
 	u32 types_size;
 	u32 data_size;
 	refcount_t refcnt;
@@ -544,33 +545,29 @@ u32 btf_nr_types(const struct btf *btf)
 	return total;
 }
 
-u32 btf_type_cnt(const struct btf *btf)
+u32 btf_start_id(const struct btf *btf)
 {
-	return btf->start_id + btf->nr_types;
+	return btf->start_id;
 }
 
-s32 btf_find_by_name_kind(const struct btf *btf, const char *name, u8 kind)
+u32 btf_nr_sorted_types(const struct btf *btf)
 {
-	const struct btf_type *t;
-	const char *tname;
-	u32 i, total;
-
-	do {
-		total = btf_type_cnt(btf);
-		for (i = btf->start_id; i < total; i++) {
-			t = btf_type_by_id(btf, i);
-			if (BTF_INFO_KIND(t->info) != kind)
-				continue;
+	return btf->nr_sorted_types;
+}
 
-			tname = btf_name_by_offset(btf, t->name_off);
-			if (!strcmp(tname, name))
-				return i;
-		}
+void btf_set_nr_sorted_types(struct btf *btf, u32 nr)
+{
+	btf->nr_sorted_types = nr;
+}
 
-		btf = btf->base_btf;

kernel/bpf/btf.c u32 btf_nr_types(const struct btf *btf) · line 570

Quoted 10 lines
kernel/bpf/btf.c +7 -2
-	} while (btf);
+u32 btf_type_cnt(const struct btf *btf)
+{
+	return btf->start_id + btf->nr_types;
+}
 
-	return -ENOENT;
+s32 btf_find_by_name_kind(const struct btf *btf, const char *name, u8 kind)
+{
+	return find_btf_by_name_kind(btf, 1, name, kind);

^^^
nit: this will make it impossible to find "void" w/o a special case
in the find_btf_by_name_kind(), why not start from 0?

Quoted 3 lines
kernel/bpf/btf.c +0 -0
 }
 
 s32 bpf_find_btf_id(const char *name, u32 kind, struct btf **btf_p)

[...]

Quoted 4 lines
tools/lib/bpf/btf.c +0 -0
index 18907f0fcf9f..87e47f0b78ba 100644

[...]

tools/lib/bpf/btf.c static int btf_dedup_compact_types(struct btf_dedup *d) · line 5325

Quoted 7 lines
tools/lib/bpf/btf.c +7 -0
+/*
+ * Compact and sort BTF types.
+ *
+ * Similar to btf_dedup_compact_types, but additionally sorts the btf_types.
+ */
+static int btf__dedup_compact_and_sort_types(struct btf_dedup *d)
+{

And this function will become btf__dedup_compact_types(), if BTF will be always sorted. Thus removing some code duplication.

[...]

Quoted 5 lines
tools/lib/bpf/btf_sort.c new file +0 -0
new file mode 100644
index 000000000000..2ad4a56f1c08

[...]

Quoted 15 lines
tools/lib/bpf/btf_sort.c new file +15 -0
+/*
+ * Sort BTF types by kind and name in ascending order, placing named types
+ * before anonymous ones.
+ */
+int btf_compare_type_kinds_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;
+	int ka, kb;
+
+	/* ta w/o name is greater than tb */
+	if (!ta->name_off && tb->name_off)
+		return 1;

tools/lib/bpf/btf_sort.c line 66

Quoted 10 lines
tools/lib/bpf/btf_sort.c new file +10 -0
+	/* tb w/o name is smaller than ta */
+	if (ta->name_off && !tb->name_off)
+		return -1;
+
+	ka = btf_kind(ta);
+	kb = btf_kind(tb);
+	na = btf__str_by_offset(btf, ta->name_off);
+	nb = btf__str_by_offset(btf, tb->name_off);
+
+	return cmp_btf_kind_name(ka, na, kb, nb);

If both types are anonymous and have the same kind, this will lead to strcmp(NULL, NULL). On kernel side that would lead to null pointer dereference.

tools/lib/bpf/btf_sort.c line 70

Quoted 4 lines
tools/lib/bpf/btf_sort.c new file +4 -0
+}
+
+__s32 find_btf_by_name_kind(const struct btf *btf, int start_id,
+				   const char *type_name, __u32 kind)

Nit: having functions with names btf_find_by_name_kind and
find_btf_by_name_kind
is very confusing.
Usually we use names like __<func> for auxiliary functions like this.

Quoted 51 lines
tools/lib/bpf/btf_sort.c new file +51 -0
+{
+	const struct btf_type *t;
+	const char *tname;
+	__u32 i, total;
+
+	if (kind == BTF_KIND_UNKN || !strcmp(type_name, "void"))
+		return 0;
+
+	do {
+		if (btf__nr_sorted_types(btf)) {
+			/* binary search */
+			__s32 start, end, mid, found = -1;
+			int ret;
+
+			start = btf__start_id(btf);
+			end = start + btf__nr_sorted_types(btf) - 1;
+			/* found the leftmost btf_type that matches */
+			while(start <= end) {
+				mid = start + (end - start) / 2;
+				t = btf_type_by_id(btf, mid);
+				tname = btf__name_by_offset(btf, t->name_off);
+				ret = cmp_btf_kind_name(BTF_INFO_KIND(t->info), tname,
+							kind, type_name);
+				if (ret == 0)
+					found = mid;
+				if (ret < 0)
+					start = mid + 1;
+				else if (ret >= 0)
+					end = mid - 1;
+			}
+
+			if (found != -1)
+				return found;
+		} else {
+			/* linear search */
+			total = btf__type_cnt(btf);
+			for (i = btf__start_id(btf); i < total; i++) {
+				t = btf_type_by_id(btf, i);
+				if (btf_kind(t) != kind)
+					continue;
+
+				tname = btf__name_by_offset(btf, t->name_off);
+				if (tname && !strcmp(tname, type_name))
+					return i;
+			}
+		}
+
+		btf = btf__base_btf(btf);
+	} while (btf && btf__start_id(btf) >= start_id);
+
+	return libbpf_err(-ENOENT);

tools/lib/bpf/btf_sort.c line 131

Quoted 10 lines
tools/lib/bpf/btf_sort.c new file +10 -0
+}
+
+void btf_check_sorted(struct btf *btf, int start_id)
+{
+	const struct btf_type *t;
+	int i, n, nr_sorted_types;
+
+	n = btf__type_cnt(btf);
+	if ((n - start_id) < BTF_CHECK_SORT_THRESHOLD)
+		return;

Are there any measurable performance benefits from having this special case?

tools/lib/bpf/btf_sort.c line 140

Quoted 9 lines
tools/lib/bpf/btf_sort.c new file +9 -0
+
+	n--;
+	nr_sorted_types = 0;
+	for (i = start_id; i < n; i++) {
+		int k = i + 1;
+
+		t = btf_type_by_id(btf, i);
+		if (!btf__str_by_offset(btf, t->name_off))
+			return;

I am confused.
This effectively bans BTFs with anonymous types,
as btf__set_nr_sorted_types() wont be called if such types are found. Anonymous types are very common, e.g. all FUNC_PROTO are anonymous.

Quoted 19 lines
tools/lib/bpf/btf_sort.c new file +19 -0
+
+		t = btf_type_by_id(btf, k);
+		if (!btf__str_by_offset(btf, t->name_off))
+			return;
+
+		if (btf_compare_type_kinds_names(&i, &k, btf) > 0)
+			return;
+
+		if (t->name_off)
+			nr_sorted_types++;
+	}
+
+	t = btf_type_by_id(btf, start_id);
+	if (t->name_off)
+		nr_sorted_types++;
+	if (nr_sorted_types >= BTF_CHECK_SORT_THRESHOLD)
+		btf__set_nr_sorted_types(btf, nr_sorted_types);
+}
+

[...]

#12 lore raw

Re: [RFC PATCH v2 2/5] btf: sort BTF types by kind and name to enable binary search

Quoted 5 lines · Eduard Zingerman
Quoted 3 lines · Donglin Peng

This patch implements sorting of BTF types by their kind and name, enabling the use of binary search for type lookups.

Quoted 8 lines
Quoted 5 lines

To share logic between kernel and libbpf, a new btf_sort.c file is introduced containing common sorting functionality.

The sorting is performed during btf__dedup() when the new sort_by_kind_name option in btf_dedup_opts is enabled.

Do we really need this option? Dedup is free to rearrange btf types anyway, so why not sort always? Is execution time a concern?

The issue is that sorting changes the layout of BTF. Many existing selftests rely on the current, non-sorted order for their validation checks. Introducing this as an optional feature first allows us to run it without immediately breaking the tests, giving us time to fix them incrementally.

Quoted 61 lines
Quoted 3 lines

For vmlinux and kernel module BTF, btf_check_sorted() verifies whether the types are sorted and binary search can be used.

[...]

Quoted 55 lines
kernel/bpf/btf.c +14 -19
index c414cf37e1bd..11b05f4eb07d 100644
@@ -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;
      u32 types_size;
      u32 data_size;
      refcount_t refcnt;
@@ -544,33 +545,29 @@ u32 btf_nr_types(const struct btf *btf)
      return total;
 }
 
-u32 btf_type_cnt(const struct btf *btf)
+u32 btf_start_id(const struct btf *btf)
 {
-     return btf->start_id + btf->nr_types;
+     return btf->start_id;
 }
 
-s32 btf_find_by_name_kind(const struct btf *btf, const char *name, u8 kind)
+u32 btf_nr_sorted_types(const struct btf *btf)
 {
-     const struct btf_type *t;
-     const char *tname;
-     u32 i, total;
-
-     do {
-             total = btf_type_cnt(btf);
-             for (i = btf->start_id; i < total; i++) {
-                     t = btf_type_by_id(btf, i);
-                     if (BTF_INFO_KIND(t->info) != kind)
-                             continue;
+     return btf->nr_sorted_types;
+}
 
-                     tname = btf_name_by_offset(btf, t->name_off);
-                     if (!strcmp(tname, name))
-                             return i;
-             }
+void btf_set_nr_sorted_types(struct btf *btf, u32 nr)
+{
+     btf->nr_sorted_types = nr;
+}
 
-             btf = btf->base_btf;
-     } while (btf);
+u32 btf_type_cnt(const struct btf *btf)
+{
+     return btf->start_id + btf->nr_types;
+}
 
Quoted 7 lines

kernel/bpf/btf.c u32 btf_nr_types(const struct btf *btf) · line 570

Quoted 4 lines
kernel/bpf/btf.c +3 -1
-     return -ENOENT;
+s32 btf_find_by_name_kind(const struct btf *btf, const char *name, u8 kind)
+{
+     return find_btf_by_name_kind(btf, 1, name, kind);

^^^
nit: this will make it impossible to find "void" w/o a special case
in the find_btf_by_name_kind(), why not start from 0?

Thanks. I referred to btf__find_by_name_kind in libbpf. In btf_find_by_name_kind,
there is a special check for "void". Consequently, I've added a similar special check
for "void" in find_btf_by_name_kind as well.

Quoted 13 lines
Quoted 3 lines
kernel/bpf/btf.c +0 -0
 }
 
 s32 bpf_find_btf_id(const char *name, u32 kind, struct btf **btf_p)

[...]

Quoted 4 lines
tools/lib/bpf/btf.c +0 -0
index 18907f0fcf9f..87e47f0b78ba 100644

[...]

Quoted 10 lines

tools/lib/bpf/btf.c static int btf_dedup_compact_types(struct btf_dedup *d) · line 5325

Quoted 7 lines
tools/lib/bpf/btf.c +7 -0
+/*
+ * Compact and sort BTF types.
+ *
+ * Similar to btf_dedup_compact_types, but additionally sorts the btf_types.
+ */
+static int btf__dedup_compact_and_sort_types(struct btf_dedup *d)
+{

And this function will become btf__dedup_compact_types(), if BTF will be always sorted. Thus removing some code duplication.

Thanks for the suggestion. I think we can keep just btf__dedup_compact_and_sort_types and add a feature check before sorting, like this:

if (d->sort_by_kind_name)
qsort_r(sorted_ids, types_cnt, sizeof(*sorted_ids),
btf_compare_type_kinds_names, d->btf);

Quoted 32 lines

[...]

Quoted 5 lines
tools/lib/bpf/btf_sort.c new file +0 -0
new file mode 100644
index 000000000000..2ad4a56f1c08

[...]

Quoted 21 lines
tools/lib/bpf/btf_sort.c new file +21 -0
+/*
+ * Sort BTF types by kind and name in ascending order, placing named types
+ * before anonymous ones.
+ */
+int btf_compare_type_kinds_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;
+     int ka, kb;
+
+     /* ta w/o name is greater than tb */
+     if (!ta->name_off && tb->name_off)
+             return 1;
+     /* tb w/o name is smaller than ta */
+     if (ta->name_off && !tb->name_off)
+             return -1;
+
+     ka = btf_kind(ta);
+     kb = btf_kind(tb);
Quoted 8 lines

tools/lib/bpf/btf_sort.c line 66

Quoted 4 lines
tools/lib/bpf/btf_sort.c new file +4 -0
+     na = btf__str_by_offset(btf, ta->name_off);
+     nb = btf__str_by_offset(btf, tb->name_off);
+
+     return cmp_btf_kind_name(ka, na, kb, nb);

If both types are anonymous and have the same kind, this will lead to strcmp(NULL, NULL). On kernel side that would lead to null pointer dereference.

Thanks, I've confirmed that for anonymous types, name_off is 0, so btf__str_by_offset returns a pointer to btf->strs_data (which contains a '\0' at index 0) rather than NULL. However, when name_off is invalid, btf__str_by_offset does return NULL. Using str_is_empty will correctly handle both scenarios. Unnamed types of the same kind shall be considered equal. I will fix it in the next version.

Quoted 11 lines

tools/lib/bpf/btf_sort.c line 70

Quoted 5 lines
tools/lib/bpf/btf_sort.c new file +4 -0
+}
+
+__s32 find_btf_by_name_kind(const struct btf *btf, int start_id,
+                                const char *type_name, __u32 kind)

Nit: having functions with names btf_find_by_name_kind and
find_btf_by_name_kind
is very confusing.
Usually we use names like __<func> for auxiliary functions like this.

Agreed. The function will be updated to __btf_find_by_name_kind in the next version.

Quoted 56 lines
Quoted 56 lines
tools/lib/bpf/btf_sort.c new file +55 -0
+{
+     const struct btf_type *t;
+     const char *tname;
+     __u32 i, total;
+
+     if (kind == BTF_KIND_UNKN || !strcmp(type_name, "void"))
+             return 0;
+
+     do {
+             if (btf__nr_sorted_types(btf)) {
+                     /* binary search */
+                     __s32 start, end, mid, found = -1;
+                     int ret;
+
+                     start = btf__start_id(btf);
+                     end = start + btf__nr_sorted_types(btf) - 1;
+                     /* found the leftmost btf_type that matches */
+                     while(start <= end) {
+                             mid = start + (end - start) / 2;
+                             t = btf_type_by_id(btf, mid);
+                             tname = btf__name_by_offset(btf, t->name_off);
+                             ret = cmp_btf_kind_name(BTF_INFO_KIND(t->info), tname,
+                                                     kind, type_name);
+                             if (ret == 0)
+                                     found = mid;
+                             if (ret < 0)
+                                     start = mid + 1;
+                             else if (ret >= 0)
+                                     end = mid - 1;
+                     }
+
+                     if (found != -1)
+                             return found;
+             } else {
+                     /* linear search */
+                     total = btf__type_cnt(btf);
+                     for (i = btf__start_id(btf); i < total; i++) {
+                             t = btf_type_by_id(btf, i);
+                             if (btf_kind(t) != kind)
+                                     continue;
+
+                             tname = btf__name_by_offset(btf, t->name_off);
+                             if (tname && !strcmp(tname, type_name))
+                                     return i;
+                     }
+             }
+
+             btf = btf__base_btf(btf);
+     } while (btf && btf__start_id(btf) >= start_id);
+
+     return libbpf_err(-ENOENT);
+}
+
+void btf_check_sorted(struct btf *btf, int start_id)
+{
Quoted 8 lines

tools/lib/bpf/btf_sort.c line 131

Quoted 6 lines
tools/lib/bpf/btf_sort.c new file +6 -0
+     const struct btf_type *t;
+     int i, n, nr_sorted_types;
+
+     n = btf__type_cnt(btf);
+     if ((n - start_id) < BTF_CHECK_SORT_THRESHOLD)
+             return;

Are there any measurable performance benefits from having this special case?

Sorry, I haven't run performance tests. The number 8 comes from the theoretical equivalence point where n/2 ≈ log2(n).

Quoted 15 lines

tools/lib/bpf/btf_sort.c line 140

Quoted 10 lines
tools/lib/bpf/btf_sort.c new file +9 -0
+
+     n--;
+     nr_sorted_types = 0;
+     for (i = start_id; i < n; i++) {
+             int k = i + 1;
+
+             t = btf_type_by_id(btf, i);
+             if (!btf__str_by_offset(btf, t->name_off))
+                     return;

I am confused.
This effectively bans BTFs with anonymous types,
as btf__set_nr_sorted_types() wont be called if such types are found. Anonymous types are very common, e.g. all FUNC_PROTO are anonymous.

Thanks, I thought that for anonymous types, name_off would be 0, and btf__str_by_offset would not return NULL. However if the name_off is invalid, it will return NULL. So I plan to modify btf_compare_type_kinds_names to cover both scenarios.

Quoted 22 lines
Quoted 20 lines
tools/lib/bpf/btf_sort.c new file +19 -0
+
+             t = btf_type_by_id(btf, k);
+             if (!btf__str_by_offset(btf, t->name_off))
+                     return;
+
+             if (btf_compare_type_kinds_names(&i, &k, btf) > 0)
+                     return;
+
+             if (t->name_off)
+                     nr_sorted_types++;
+     }
+
+     t = btf_type_by_id(btf, start_id);
+     if (t->name_off)
+             nr_sorted_types++;
+     if (nr_sorted_types >= BTF_CHECK_SORT_THRESHOLD)
+             btf__set_nr_sorted_types(btf, nr_sorted_types);
+}
+

[...]

maintainer
#13 lore raw

Re: [RFC PATCH v2 2/5] btf: sort BTF types by kind and name to enable binary search

Quoted 12 lines · Donglin Peng
Quoted 11 lines · Eduard Zingerman
Quoted 8 lines · Donglin Peng

This patch implements sorting of BTF types by their kind and name, enabling the use of binary search for type lookups.

To share logic between kernel and libbpf, a new btf_sort.c file is introduced containing common sorting functionality.

The sorting is performed during btf__dedup() when the new sort_by_kind_name option in btf_dedup_opts is enabled.

Quoted 7 lines
Quoted 2 lines

Do we really need this option? Dedup is free to rearrange btf types anyway, so why not sort always? Is execution time a concern?

The issue is that sorting changes the layout of BTF. Many existing selftests rely on the current, non-sorted order for their validation checks. Introducing this as an optional feature first allows us to run it without immediately breaking the tests, giving us time to fix them incrementally.

How many tests are we talking about?
The option is an API and it stays with us forever. If the only justification for its existence is to avoid tests modification, I don't think that's enough.

Quoted 10 lines
Quoted 10 lines
Quoted 3 lines

For vmlinux and kernel module BTF, btf_check_sorted() verifies whether the types are sorted and binary search can be used.

[...]

Quoted 4 lines
kernel/bpf/btf.c +0 -0
index c414cf37e1bd..11b05f4eb07d 100644

[...]

Quoted 7 lines
Quoted 6 lines

kernel/bpf/btf.c u32 btf_nr_types(const struct btf *btf) · line 570

Quoted 3 lines
kernel/bpf/btf.c +3 -0
+s32 btf_find_by_name_kind(const struct btf *btf, const char *name, u8 kind)
+{
+     return find_btf_by_name_kind(btf, 1, name, kind);

^^^
nit: this will make it impossible to find "void" w/o a special case
in the find_btf_by_name_kind(), why not start from 0?

Quoted 5 lines

Thanks. I referred to btf__find_by_name_kind in libbpf. In btf_find_by_name_kind,
there is a special check for "void". Consequently, I've added a similar special check
for "void" in find_btf_by_name_kind as well.

Yes, I see the special case in the find_btf_by_name_kind. But wouldn't starting from 0 here avoid the need for special case?

[...]

Quoted 38 lines
Quoted 29 lines
Quoted 5 lines
tools/lib/bpf/btf_sort.c new file +0 -0
new file mode 100644
index 000000000000..2ad4a56f1c08

[...]

Quoted 21 lines
tools/lib/bpf/btf_sort.c new file +21 -0
+/*
+ * Sort BTF types by kind and name in ascending order, placing named types
+ * before anonymous ones.
+ */
+int btf_compare_type_kinds_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;
+     int ka, kb;
+
+     /* ta w/o name is greater than tb */
+     if (!ta->name_off && tb->name_off)
+             return 1;
+     /* tb w/o name is smaller than ta */
+     if (ta->name_off && !tb->name_off)
+             return -1;
+
+     ka = btf_kind(ta);
+     kb = btf_kind(tb);
Quoted 8 lines

tools/lib/bpf/btf_sort.c line 66

Quoted 4 lines
tools/lib/bpf/btf_sort.c new file +4 -0
+     na = btf__str_by_offset(btf, ta->name_off);
+     nb = btf__str_by_offset(btf, tb->name_off);
+
+     return cmp_btf_kind_name(ka, na, kb, nb);

If both types are anonymous and have the same kind, this will lead to strcmp(NULL, NULL). On kernel side that would lead to null pointer dereference.

Quoted 6 lines

Thanks, I've confirmed that for anonymous types, name_off is 0, so btf__str_by_offset returns a pointer to btf->strs_data (which contains a '\0' at index 0) rather than NULL. However, when name_off is invalid, btf__str_by_offset does return NULL. Using str_is_empty will correctly handle both scenarios. Unnamed types of the same kind shall be considered equal. I will fix it in the next version.

I see, thank you for explaining.
Checking the usage of kernel/bpf/btf.c:btf_name_valid_identifier(), it looks like kernel validates name_off for all types. So, your implementation should be fine.

[...]

#14 lore raw

Re: [RFC PATCH v2 2/5] btf: sort BTF types by kind and name to enable binary search

Quoted 22 lines · Eduard Zingerman
Quoted 12 lines · Donglin Peng
Quoted 11 lines · Eduard Zingerman
Quoted 8 lines · Donglin Peng

This patch implements sorting of BTF types by their kind and name, enabling the use of binary search for type lookups.

To share logic between kernel and libbpf, a new btf_sort.c file is introduced containing common sorting functionality.

The sorting is performed during btf__dedup() when the new sort_by_kind_name option in btf_dedup_opts is enabled.

Quoted 7 lines
Quoted 2 lines

Do we really need this option? Dedup is free to rearrange btf types anyway, so why not sort always? Is execution time a concern?

The issue is that sorting changes the layout of BTF. Many existing selftests rely on the current, non-sorted order for their validation checks. Introducing this as an optional feature first allows us to run it without immediately breaking the tests, giving us time to fix them incrementally.

Quoted 4 lines

How many tests are we talking about?
The option is an API and it stays with us forever. If the only justification for its existence is to avoid tests modification, I don't think that's enough.

I get your point, thanks. I wonder what others think?

Quoted 21 lines
Quoted 11 lines
Quoted 11 lines
Quoted 4 lines

For vmlinux and kernel module BTF, btf_check_sorted() verifies whether the types are sorted and binary search can be used.

[...]

Quoted 4 lines
kernel/bpf/btf.c +0 -0
index c414cf37e1bd..11b05f4eb07d 100644

[...]

Quoted 7 lines
Quoted 6 lines

kernel/bpf/btf.c u32 btf_nr_types(const struct btf *btf) · line 570

Quoted 3 lines
kernel/bpf/btf.c +3 -0
+s32 btf_find_by_name_kind(const struct btf *btf, const char *name, u8 kind)
+{
+     return find_btf_by_name_kind(btf, 1, name, kind);

^^^
nit: this will make it impossible to find "void" w/o a special case
in the find_btf_by_name_kind(), why not start from 0?

Quoted 8 lines
Quoted 5 lines

Thanks. I referred to btf__find_by_name_kind in libbpf. In btf_find_by_name_kind,
there is a special check for "void". Consequently, I've added a similar special check
for "void" in find_btf_by_name_kind as well.

Yes, I see the special case in the find_btf_by_name_kind. But wouldn't starting from 0 here avoid the need for special case?

The start_id parameter here serves the same purpose as the one in libbpf's btf_find_by_name_kind. However, its implementation in find_btf_by_name_kind was incorrect. I will fix this in the next version.

__s32 btf__find_by_name_kind_own(const struct btf *btf, const char *type_name, __u32 kind)
{
return btf_find_by_name_kind(btf, btf->start_id, type_name, kind); }

__s32 btf__find_by_name_kind(const struct btf *btf, const char *type_name,

     __u32 kind)

{
return btf_find_by_name_kind(btf, 1, type_name, kind); }

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(-ENOENT);

}

Quoted 54 lines

[...]

Quoted 38 lines
Quoted 29 lines
Quoted 5 lines
tools/lib/bpf/btf_sort.c new file +0 -0
new file mode 100644
index 000000000000..2ad4a56f1c08

[...]

Quoted 21 lines
tools/lib/bpf/btf_sort.c new file +21 -0
+/*
+ * Sort BTF types by kind and name in ascending order, placing named types
+ * before anonymous ones.
+ */
+int btf_compare_type_kinds_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;
+     int ka, kb;
+
+     /* ta w/o name is greater than tb */
+     if (!ta->name_off && tb->name_off)
+             return 1;
+     /* tb w/o name is smaller than ta */
+     if (ta->name_off && !tb->name_off)
+             return -1;
+
+     ka = btf_kind(ta);
+     kb = btf_kind(tb);
Quoted 8 lines

tools/lib/bpf/btf_sort.c line 66

Quoted 4 lines
tools/lib/bpf/btf_sort.c new file +4 -0
+     na = btf__str_by_offset(btf, ta->name_off);
+     nb = btf__str_by_offset(btf, tb->name_off);
+
+     return cmp_btf_kind_name(ka, na, kb, nb);

If both types are anonymous and have the same kind, this will lead to strcmp(NULL, NULL). On kernel side that would lead to null pointer dereference.

Quoted 6 lines

Thanks, I've confirmed that for anonymous types, name_off is 0, so btf__str_by_offset returns a pointer to btf->strs_data (which contains a '\0' at index 0) rather than NULL. However, when name_off is invalid, btf__str_by_offset does return NULL. Using str_is_empty will correctly handle both scenarios. Unnamed types of the same kind shall be considered equal. I will fix it in the next version.

I see, thank you for explaining.
Checking the usage of kernel/bpf/btf.c:btf_name_valid_identifier(), it looks like kernel validates name_off for all types. So, your implementation should be fine.

[...]

#15 lore raw

Re: [RFC PATCH v2 2/5] btf: sort BTF types by kind and name to enable binary search

Quoted 24 lines · Donglin Peng
Quoted 22 lines · Eduard Zingerman
Quoted 19 lines · Donglin Peng
Quoted 5 lines · Eduard Zingerman
Quoted 3 lines · Donglin Peng

This patch implements sorting of BTF types by their kind and name, enabling the use of binary search for type lookups.

Quoted 8 lines
Quoted 5 lines

To share logic between kernel and libbpf, a new btf_sort.c file is introduced containing common sorting functionality.

The sorting is performed during btf__dedup() when the new sort_by_kind_name option in btf_dedup_opts is enabled.

Do we really need this option? Dedup is free to rearrange btf types anyway, so why not sort always? Is execution time a concern?

The issue is that sorting changes the layout of BTF. Many existing selftests rely on the current, non-sorted order for their validation checks. Introducing this as an optional feature first allows us to run it without immediately breaking the tests, giving us time to fix them incrementally.

Quoted 6 lines
Quoted 4 lines

How many tests are we talking about?
The option is an API and it stays with us forever. If the only justification for its existence is to avoid tests modification, I don't think that's enough.

I get your point, thanks. I wonder what others think?

+1 to Eduard's point.
No new flags please. Always sort.

Also I don't feel that sorting logic belongs in libbpf. pahole needs to dedup first, apply extra filters, add extra BTFs. At that point going back to libbpf and asking to sort seems odd.

#16 lore raw

Re: [RFC PATCH v2 2/5] btf: sort BTF types by kind and name to enable binary search

Quoted 31 lines · Alexei Starovoitov
Quoted 29 lines · Donglin Peng
Quoted 26 lines · Eduard Zingerman
Quoted 12 lines · Donglin Peng
Quoted 11 lines · Eduard Zingerman
Quoted 8 lines · Donglin Peng

This patch implements sorting of BTF types by their kind and name, enabling the use of binary search for type lookups.

To share logic between kernel and libbpf, a new btf_sort.c file is introduced containing common sorting functionality.

The sorting is performed during btf__dedup() when the new sort_by_kind_name option in btf_dedup_opts is enabled.

Quoted 7 lines
Quoted 2 lines

Do we really need this option? Dedup is free to rearrange btf types anyway, so why not sort always? Is execution time a concern?

The issue is that sorting changes the layout of BTF. Many existing selftests rely on the current, non-sorted order for their validation checks. Introducing this as an optional feature first allows us to run it without immediately breaking the tests, giving us time to fix them incrementally.

How many tests are we talking about?
The option is an API and it stays with us forever. If the only justification for its existence is to avoid tests modification, I don't think that's enough.

Quoted 8 lines
Quoted 1 line

I get your point, thanks. I wonder what others think?

+1 to Eduard's point.
No new flags please. Always sort.

Also I don't feel that sorting logic belongs in libbpf. pahole needs to dedup first, apply extra filters, add extra BTFs. At that point going back to libbpf and asking to sort seems odd.

Correct, I'd also not bake sorting into libbpf. Sorting order should be determined by pahole (or whatever other producer of BTF) after all the information is collected. So btf_dedup shouldn't sort.

But I think we should add a new API to libbpf to help with sorting. I'd add this:

int btf__permute(struct btf *btf, int permutation, int permutation_sz);

With the idea that libbpf will renumber and reshuffle BTF data according to permutation provided by the caller. Caller should make sure that permutation is a valid one, of course.

(we can also extend this to allow specifying that some types should
be dropped by mapping them to zero, I think I wanted something like that for BTF linker at some point, don't remember details anymore; but that's definitely not in v1)

This is useful for sorting use case (pahole build an index from old btf type ID to new btf type ID -> libbpf shuffles bytes and renumbers everything), but can be applied more generally (I don't remember now, but I did have this idea earlier in response to some need for BTF reshuffling).

Speaking of flags, though. I think adding BTF_F_SORTED flag to btf_header->flags seems useful, as that would allow libbpf (and user space apps working with BTF in general) to use more optimal find_by_name implementation. The only gotcha is that old kernels enforce this btf_header->flags to be zero, so pahole would need to know not to emit this when building BTF for old kernels (or, rather, we'll just teach pahole_flags in kernel build scripts to add this going forward). This is not very important for kernel, because kernel has to validate all this anyways, but would allow saving time for user space.

#17 lore raw

Re: [RFC PATCH v2 2/5] btf: sort BTF types by kind and name to enable binary search

Quoted 12 lines · Andrii Nakryiko

Speaking of flags, though. I think adding BTF_F_SORTED flag to btf_header->flags seems useful, as that would allow libbpf (and user space apps working with BTF in general) to use more optimal find_by_name implementation. The only gotcha is that old kernels enforce this btf_header->flags to be zero, so pahole would need to know not to emit this when building BTF for old kernels (or, rather, we'll just teach pahole_flags in kernel build scripts to add this going forward). This is not very important for kernel, because kernel has to validate all this anyways, but would allow saving time for user space.

Thinking more about it... I don't think it's worth it.
It's an operational headache. I'd rather have newer pahole sort it without on/off flags and detection, so that people can upgrade pahole and build older kernels.
Also BTF_F_SORTED doesn't spell out the way it's sorted. Things may change and we will need a new flag and so on.
I think it's easier to check in the kernel and libbpf whether BTF is sorted the way they want it.
The check is simple, fast and done once. Then both (kernel and libbpf) can set an internal flag and use different functions to search within a given BTF.

#18 lore raw

Re: [RFC PATCH v2 2/5] btf: sort BTF types by kind and name to enable binary search

Quoted 16 lines · Alexei Starovoitov
Quoted 12 lines · Andrii Nakryiko

Speaking of flags, though. I think adding BTF_F_SORTED flag to btf_header->flags seems useful, as that would allow libbpf (and user space apps working with BTF in general) to use more optimal find_by_name implementation. The only gotcha is that old kernels enforce this btf_header->flags to be zero, so pahole would need to know not to emit this when building BTF for old kernels (or, rather, we'll just teach pahole_flags in kernel build scripts to add this going forward). This is not very important for kernel, because kernel has to validate all this anyways, but would allow saving time for user space.

Quoted 11 lines

Thinking more about it... I don't think it's worth it.
It's an operational headache. I'd rather have newer pahole sort it without on/off flags and detection, so that people can upgrade pahole and build older kernels.
Also BTF_F_SORTED doesn't spell out the way it's sorted. Things may change and we will need a new flag and so on.
I think it's easier to check in the kernel and libbpf whether BTF is sorted the way they want it.
The check is simple, fast and done once. Then both (kernel and libbpf) can set an internal flag and use different functions to search within a given BTF.

I guess that's fine. libbpf can do this check lazily on the first btf__find_by_name() to avoid unnecessary overhead. Agreed.

#19 lore raw

Re: [RFC PATCH v2 2/5] btf: sort BTF types by kind and name to enable binary search

Quoted 31 lines · Andrii Nakryiko
Quoted 16 lines · Alexei Starovoitov
Quoted 12 lines · Andrii Nakryiko

Speaking of flags, though. I think adding BTF_F_SORTED flag to btf_header->flags seems useful, as that would allow libbpf (and user space apps working with BTF in general) to use more optimal find_by_name implementation. The only gotcha is that old kernels enforce this btf_header->flags to be zero, so pahole would need to know not to emit this when building BTF for old kernels (or, rather, we'll just teach pahole_flags in kernel build scripts to add this going forward). This is not very important for kernel, because kernel has to validate all this anyways, but would allow saving time for user space.

Quoted 11 lines

Thinking more about it... I don't think it's worth it.
It's an operational headache. I'd rather have newer pahole sort it without on/off flags and detection, so that people can upgrade pahole and build older kernels.
Also BTF_F_SORTED doesn't spell out the way it's sorted. Things may change and we will need a new flag and so on.
I think it's easier to check in the kernel and libbpf whether BTF is sorted the way they want it.
The check is simple, fast and done once. Then both (kernel and libbpf) can set an internal flag and use different functions to search within a given BTF.

Quoted 2 lines

I guess that's fine. libbpf can do this check lazily on the first btf__find_by_name() to avoid unnecessary overhead. Agreed.

Thank you for all the feedback. Based on the suggestions above, the sorting implementation will be redesigned in the next version as follows:

1. The sorting operation will be fully handled by pahole, with no dependency on libbpf. This means users can benefit from sorting simply by upgrading their pahole version.

2. The kernel and libbpf will only be responsible for:
2.1. Checking whether the BTF data is sorted 2.2. Implementing binary search for sorted BTF

Regarding the sorting check overhead: if the runtime cost is sufficiently small, it can be performed during BTF parsing. Based on my local testing with vmlinux
BTF (containing 143,484 btf_types), this check takes at most 1.5 milliseconds
during boot. Is this 1.5ms overhead acceptable?

Are there any other suggestions?

#20 lore raw

Re: [RFC PATCH v2 2/5] btf: sort BTF types by kind and name to enable binary search

Quoted 37 lines · Donglin Peng
Quoted 31 lines · Andrii Nakryiko
Quoted 16 lines · Alexei Starovoitov
Quoted 12 lines · Andrii Nakryiko

Speaking of flags, though. I think adding BTF_F_SORTED flag to btf_header->flags seems useful, as that would allow libbpf (and user space apps working with BTF in general) to use more optimal find_by_name implementation. The only gotcha is that old kernels enforce this btf_header->flags to be zero, so pahole would need to know not to emit this when building BTF for old kernels (or, rather, we'll just teach pahole_flags in kernel build scripts to add this going forward). This is not very important for kernel, because kernel has to validate all this anyways, but would allow saving time for user space.

Quoted 11 lines

Thinking more about it... I don't think it's worth it.
It's an operational headache. I'd rather have newer pahole sort it without on/off flags and detection, so that people can upgrade pahole and build older kernels.
Also BTF_F_SORTED doesn't spell out the way it's sorted. Things may change and we will need a new flag and so on.
I think it's easier to check in the kernel and libbpf whether BTF is sorted the way they want it.
The check is simple, fast and done once. Then both (kernel and libbpf) can set an internal flag and use different functions to search within a given BTF.

Quoted 2 lines

I guess that's fine. libbpf can do this check lazily on the first btf__find_by_name() to avoid unnecessary overhead. Agreed.

Quoted 6 lines

Thank you for all the feedback. Based on the suggestions above, the sorting implementation will be redesigned in the next version as follows:

1. The sorting operation will be fully handled by pahole, with no dependency on libbpf. This means users can benefit from sorting simply by upgrading their pahole version.

I suggest that libbpf provides a sorting function, such as the btf__permute suggested
by Andrii, for pahole to call. This approach allows pahole to leverage libbpf's existing
helper functions and avoids code duplication.

Quoted 11 lines

2. The kernel and libbpf will only be responsible for:
2.1. Checking whether the BTF data is sorted 2.2. Implementing binary search for sorted BTF

Regarding the sorting check overhead: if the runtime cost is sufficiently small, it can be performed during BTF parsing. Based on my local testing with vmlinux
BTF (containing 143,484 btf_types), this check takes at most 1.5 milliseconds
during boot. Is this 1.5ms overhead acceptable?

Are there any other suggestions?

maintainer
#21 lore raw

Re: [RFC PATCH v2 2/5] btf: sort BTF types by kind and name to enable binary search

Quoted 45 lines · Donglin Peng
Quoted 37 lines · Donglin Peng
Quoted 31 lines · Andrii Nakryiko
Quoted 16 lines · Alexei Starovoitov
Quoted 12 lines · Andrii Nakryiko

Speaking of flags, though. I think adding BTF_F_SORTED flag to btf_header->flags seems useful, as that would allow libbpf (and user space apps working with BTF in general) to use more optimal find_by_name implementation. The only gotcha is that old kernels enforce this btf_header->flags to be zero, so pahole would need to know not to emit this when building BTF for old kernels (or, rather, we'll just teach pahole_flags in kernel build scripts to add this going forward). This is not very important for kernel, because kernel has to validate all this anyways, but would allow saving time for user space.

Quoted 11 lines

Thinking more about it... I don't think it's worth it.
It's an operational headache. I'd rather have newer pahole sort it without on/off flags and detection, so that people can upgrade pahole and build older kernels.
Also BTF_F_SORTED doesn't spell out the way it's sorted. Things may change and we will need a new flag and so on.
I think it's easier to check in the kernel and libbpf whether BTF is sorted the way they want it.
The check is simple, fast and done once. Then both (kernel and libbpf) can set an internal flag and use different functions to search within a given BTF.

Quoted 2 lines

I guess that's fine. libbpf can do this check lazily on the first btf__find_by_name() to avoid unnecessary overhead. Agreed.

Quoted 6 lines

Thank you for all the feedback. Based on the suggestions above, the sorting implementation will be redesigned in the next version as follows:

1. The sorting operation will be fully handled by pahole, with no dependency on libbpf. This means users can benefit from sorting simply by upgrading their pahole version.

Quoted 5 lines

I suggest that libbpf provides a sorting function, such as the btf__permute suggested
by Andrii, for pahole to call. This approach allows pahole to leverage libbpf's existing
helper functions and avoids code duplication.

Could you please enumerate the functions you'd have to reimplement in pahole?

Quoted 11 lines
Quoted 11 lines

2. The kernel and libbpf will only be responsible for:
2.1. Checking whether the BTF data is sorted 2.2. Implementing binary search for sorted BTF

Regarding the sorting check overhead: if the runtime cost is sufficiently small, it can be performed during BTF parsing. Based on my local testing with vmlinux
BTF (containing 143,484 btf_types), this check takes at most 1.5 milliseconds
during boot. Is this 1.5ms overhead acceptable?

Are there any other suggestions?

#22 lore raw

Re: [RFC PATCH v2 2/5] btf: sort BTF types by kind and name to enable binary search

Quoted 47 lines · Eduard Zingerman
Quoted 45 lines · Donglin Peng
Quoted 43 lines · Donglin Peng
Quoted 31 lines · Andrii Nakryiko
Quoted 16 lines · Alexei Starovoitov
Quoted 12 lines · Andrii Nakryiko

Speaking of flags, though. I think adding BTF_F_SORTED flag to btf_header->flags seems useful, as that would allow libbpf (and user space apps working with BTF in general) to use more optimal find_by_name implementation. The only gotcha is that old kernels enforce this btf_header->flags to be zero, so pahole would need to know not to emit this when building BTF for old kernels (or, rather, we'll just teach pahole_flags in kernel build scripts to add this going forward). This is not very important for kernel, because kernel has to validate all this anyways, but would allow saving time for user space.

Quoted 11 lines

Thinking more about it... I don't think it's worth it.
It's an operational headache. I'd rather have newer pahole sort it without on/off flags and detection, so that people can upgrade pahole and build older kernels.
Also BTF_F_SORTED doesn't spell out the way it's sorted. Things may change and we will need a new flag and so on.
I think it's easier to check in the kernel and libbpf whether BTF is sorted the way they want it.
The check is simple, fast and done once. Then both (kernel and libbpf) can set an internal flag and use different functions to search within a given BTF.

Quoted 2 lines

I guess that's fine. libbpf can do this check lazily on the first btf__find_by_name() to avoid unnecessary overhead. Agreed.

Thank you for all the feedback. Based on the suggestions above, the sorting implementation will be redesigned in the next version as follows:

1. The sorting operation will be fully handled by pahole, with no dependency on libbpf. This means users can benefit from sorting simply by upgrading their pahole version.

Quoted 8 lines
Quoted 5 lines

I suggest that libbpf provides a sorting function, such as the btf__permute suggested
by Andrii, for pahole to call. This approach allows pahole to leverage libbpf's existing
helper functions and avoids code duplication.

Could you please enumerate the functions you'd have to reimplement in pahole?

Yes. Once the BTF types are sorted, the type IDs in both the BTF and BTF ext sections must be remapped. Libbpf provides helper functions like btf_field_iter_init,
btf_field_iter_next,
btf_ext_visit_type_ids
to iterate through the btf_field and btf_ext_info_sec entries that require updating.
We will likely need to reimplement these three functions for this purpose.

Quoted 12 lines
Quoted 12 lines
Quoted 12 lines

2. The kernel and libbpf will only be responsible for:
2.1. Checking whether the BTF data is sorted 2.2. Implementing binary search for sorted BTF

Regarding the sorting check overhead: if the runtime cost is sufficiently small, it can be performed during BTF parsing. Based on my local testing with vmlinux
BTF (containing 143,484 btf_types), this check takes at most 1.5 milliseconds
during boot. Is this 1.5ms overhead acceptable?

Are there any other suggestions?

maintainer
#23 lore raw

Re: [RFC PATCH v2 2/5] btf: sort BTF types by kind and name to enable binary search

Quoted 57 lines · Donglin Peng
Quoted 47 lines · Eduard Zingerman
Quoted 45 lines · Donglin Peng
Quoted 43 lines · Donglin Peng
Quoted 31 lines · Andrii Nakryiko
Quoted 16 lines · Alexei Starovoitov
Quoted 12 lines · Andrii Nakryiko

Speaking of flags, though. I think adding BTF_F_SORTED flag to btf_header->flags seems useful, as that would allow libbpf (and user space apps working with BTF in general) to use more optimal find_by_name implementation. The only gotcha is that old kernels enforce this btf_header->flags to be zero, so pahole would need to know not to emit this when building BTF for old kernels (or, rather, we'll just teach pahole_flags in kernel build scripts to add this going forward). This is not very important for kernel, because kernel has to validate all this anyways, but would allow saving time for user space.

Quoted 11 lines

Thinking more about it... I don't think it's worth it.
It's an operational headache. I'd rather have newer pahole sort it without on/off flags and detection, so that people can upgrade pahole and build older kernels.
Also BTF_F_SORTED doesn't spell out the way it's sorted. Things may change and we will need a new flag and so on.
I think it's easier to check in the kernel and libbpf whether BTF is sorted the way they want it.
The check is simple, fast and done once. Then both (kernel and libbpf) can set an internal flag and use different functions to search within a given BTF.

Quoted 2 lines

I guess that's fine. libbpf can do this check lazily on the first btf__find_by_name() to avoid unnecessary overhead. Agreed.

Thank you for all the feedback. Based on the suggestions above, the sorting implementation will be redesigned in the next version as follows:

1. The sorting operation will be fully handled by pahole, with no dependency on libbpf. This means users can benefit from sorting simply by upgrading their pahole version.

Quoted 8 lines
Quoted 5 lines

I suggest that libbpf provides a sorting function, such as the btf__permute suggested
by Andrii, for pahole to call. This approach allows pahole to leverage libbpf's existing
helper functions and avoids code duplication.

Could you please enumerate the functions you'd have to reimplement in pahole?

Quoted 8 lines

Yes. Once the BTF types are sorted, the type IDs in both the BTF and BTF ext sections must be remapped. Libbpf provides helper functions like btf_field_iter_init,
btf_field_iter_next,
btf_ext_visit_type_ids
to iterate through the btf_field and btf_ext_info_sec entries that require updating.
We will likely need to reimplement these three functions for this purpose.

I think Andrii's suggestion is to have btf__permute in libbpf, as it needs all the functions you mention.
But actual sorting can happen in pahole, then:
- allocate array of length num-types, initialize it 0..num-types;
- reorder it as one sees fit;
- call btf__permute() from libbpf and get all the renamings handled by it.

[...]

#24 lore raw

Re: [RFC PATCH v2 2/5] btf: sort BTF types by kind and name to enable binary search

Quoted 68 lines · Eduard Zingerman
Quoted 57 lines · Donglin Peng
Quoted 47 lines · Eduard Zingerman
Quoted 45 lines · Donglin Peng
Quoted 43 lines · Donglin Peng
Quoted 31 lines · Andrii Nakryiko
Quoted 16 lines · Alexei Starovoitov
Quoted 12 lines · Andrii Nakryiko

Speaking of flags, though. I think adding BTF_F_SORTED flag to btf_header->flags seems useful, as that would allow libbpf (and user space apps working with BTF in general) to use more optimal find_by_name implementation. The only gotcha is that old kernels enforce this btf_header->flags to be zero, so pahole would need to know not to emit this when building BTF for old kernels (or, rather, we'll just teach pahole_flags in kernel build scripts to add this going forward). This is not very important for kernel, because kernel has to validate all this anyways, but would allow saving time for user space.

Quoted 11 lines

Thinking more about it... I don't think it's worth it.
It's an operational headache. I'd rather have newer pahole sort it without on/off flags and detection, so that people can upgrade pahole and build older kernels.
Also BTF_F_SORTED doesn't spell out the way it's sorted. Things may change and we will need a new flag and so on.
I think it's easier to check in the kernel and libbpf whether BTF is sorted the way they want it.
The check is simple, fast and done once. Then both (kernel and libbpf) can set an internal flag and use different functions to search within a given BTF.

Quoted 2 lines

I guess that's fine. libbpf can do this check lazily on the first btf__find_by_name() to avoid unnecessary overhead. Agreed.

Thank you for all the feedback. Based on the suggestions above, the sorting implementation will be redesigned in the next version as follows:

1. The sorting operation will be fully handled by pahole, with no dependency on libbpf. This means users can benefit from sorting simply by upgrading their pahole version.

Quoted 8 lines
Quoted 5 lines

I suggest that libbpf provides a sorting function, such as the btf__permute suggested
by Andrii, for pahole to call. This approach allows pahole to leverage libbpf's existing
helper functions and avoids code duplication.

Could you please enumerate the functions you'd have to reimplement in pahole?

Quoted 8 lines

Yes. Once the BTF types are sorted, the type IDs in both the BTF and BTF ext sections must be remapped. Libbpf provides helper functions like btf_field_iter_init,
btf_field_iter_next,
btf_ext_visit_type_ids
to iterate through the btf_field and btf_ext_info_sec entries that require updating.
We will likely need to reimplement these three functions for this purpose.

Quoted 6 lines

I think Andrii's suggestion is to have btf__permute in libbpf, as it needs all the functions you mention.
But actual sorting can happen in pahole, then:
- allocate array of length num-types, initialize it 0..num-types;
- reorder it as one sees fit;
- call btf__permute() from libbpf and get all the renamings handled by it.

Yes, the first two can be implemented in pahole, while the last one belongs in libbpf.

Quoted 2 lines

[...]

#25 lore raw

RFC PATCH v2 3/5 libbpf: check if BTF is sorted to enable binary search

In reply to Donglin Peng

Now that libbpf supports sorted BTF types, add a check to determine whether binary search can be used for type lookups.

Cc Eduard Zingerman <[email protected]>
Cc Alexei Starovoitov <[email protected]>
Cc Andrii Nakryiko <[email protected]>
Cc Alan Maguire <[email protected]>
Cc Song Liu <[email protected]>
---
 tools/lib/bpf/btf.c | 6 ++++++
 1 file changed, 6 insertions(+)
tools/lib/bpf/btf.c +6 -0
index 87e47f0b78ba..92c370fe9b79 100644
@@ -1091,6 +1091,8 @@ static struct btf *btf_new(const void *data, __u32 size, struct btf *base_btf, b
 	if (err)
 		goto done;
 
+	btf_check_sorted(btf, btf->start_id);
+
 done:
 	if (err) {
 		btf__free(btf);
@@ -1714,6 +1716,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
@@ -5456,6 +5459,9 @@ static int btf_dedup_remap_types(struct btf_dedup *d)
 		}
 	}
 
+	if (d->sort_by_kind_name)
+		btf_check_sorted(d->btf, d->btf->start_id);
+
 	if (!d->btf_ext)
 		return 0;
 
Signature · 1 line
2.34.1
#26 lore raw

RFC PATCH v2 4/5 selftests/bpf: add tests for BTF deduplication and sorting

In reply to Donglin Peng

Verify that BTF deduplication and sorting functionality works correctly

Cc Eduard Zingerman <[email protected]>
Cc Alexei Starovoitov <[email protected]>
Cc Andrii Nakryiko <[email protected]>
Cc Alan Maguire <[email protected]>
Cc Song Liu <[email protected]>
---
 tools/testing/selftests/bpf/prog_tests/btf.c | 171 +++++++++++++++++++
 1 file changed, 171 insertions(+)
tools/testing/selftests/bpf/prog_tests/btf.c +171 -0
index 8a9ba4292109..244f9d535bc2 100644
@@ -8022,6 +8022,177 @@ static struct btf_dedup_test dedup_tests[] = {
 		BTF_STR_SEC("\0foo\0x\0y\0foo_ptr"),
 	},
 },
+{
+	.descr = "dedup_sort: strings deduplication",
+	.input = {
+		.raw_types = {
+			BTF_TYPE_INT_ENC(NAME_NTH(1), BTF_INT_SIGNED, 0, 32, 4),
+			BTF_TYPE_INT_ENC(NAME_NTH(2), BTF_INT_SIGNED, 0, 64, 8),
+			BTF_TYPE_INT_ENC(NAME_NTH(3), BTF_INT_SIGNED, 0, 32, 4),
+			BTF_TYPE_INT_ENC(NAME_NTH(4), BTF_INT_SIGNED, 0, 64, 8),
+			BTF_TYPE_INT_ENC(NAME_NTH(5), BTF_INT_SIGNED, 0, 32, 4),
+			BTF_END_RAW,
+		},
+		BTF_STR_SEC("\0int\0long int\0int\0long int\0int"),
+	},
+	.expect = {
+		.raw_types = {
+			BTF_TYPE_INT_ENC(NAME_NTH(1), BTF_INT_SIGNED, 0, 32, 4),
+			BTF_TYPE_INT_ENC(NAME_NTH(2), BTF_INT_SIGNED, 0, 64, 8),
+			BTF_END_RAW,
+		},
+		BTF_STR_SEC("\0int\0long int"),
+	},
+	.opts = {
+		.sort_by_kind_name = true,
+	},
+},
+{
+	.descr = "dedup_sort: func/func_arg/var tags",
+	.input = {
+		.raw_types = {
+			/* int */
+			BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4),	/* [1] */
+			/* static int t */
+			BTF_VAR_ENC(NAME_NTH(1), 1, 0),			/* [2] */
+			/* void f(int a1, int a2) */
+			BTF_FUNC_PROTO_ENC(0, 2),			/* [3] */
+				BTF_FUNC_PROTO_ARG_ENC(NAME_NTH(2), 1),
+				BTF_FUNC_PROTO_ARG_ENC(NAME_NTH(3), 1),
+			BTF_FUNC_ENC(NAME_NTH(4), 3),			/* [4] */
+			/* tag -> t */
+			BTF_DECL_TAG_ENC(NAME_NTH(5), 2, -1),		/* [5] */
+			BTF_DECL_TAG_ENC(NAME_NTH(5), 2, -1),		/* [6] */
+			/* tag -> func */
+			BTF_DECL_TAG_ENC(NAME_NTH(5), 4, -1),		/* [7] */
+			BTF_DECL_TAG_ENC(NAME_NTH(5), 4, -1),		/* [8] */
+			/* tag -> func arg a1 */
+			BTF_DECL_TAG_ENC(NAME_NTH(5), 4, 1),		/* [9] */
+			BTF_DECL_TAG_ENC(NAME_NTH(5), 4, 1),		/* [10] */
+			BTF_END_RAW,
+		},
+		BTF_STR_SEC("\0t\0a1\0a2\0f\0tag"),
+	},
+	.expect = {
+		.raw_types = {
+			BTF_FUNC_ENC(NAME_NTH(4), 7),			/* [1] */
+			BTF_VAR_ENC(NAME_NTH(1), 6, 0),			/* [2] */
+			BTF_DECL_TAG_ENC(NAME_NTH(5), 2, -1),		/* [3] */
+			BTF_DECL_TAG_ENC(NAME_NTH(5), 1, -1),		/* [4] */
+			BTF_DECL_TAG_ENC(NAME_NTH(5), 1, 1),		/* [5] */
+			BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4),	/* [6] */
+			BTF_FUNC_PROTO_ENC(0, 2),			/* [7] */
+				BTF_FUNC_PROTO_ARG_ENC(NAME_NTH(2), 6),
+				BTF_FUNC_PROTO_ARG_ENC(NAME_NTH(3), 6),
+			BTF_END_RAW,
+		},
+		BTF_STR_SEC("\0t\0a1\0a2\0f\0tag"),
+	},
+	.opts = {
+		.sort_by_kind_name = true,
+	},
+},
+{
+	.descr = "dedup_sort: func/func_param tags",
+	.input = {
+		.raw_types = {
+			/* int */
+			BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4),	/* [1] */
+			/* void f(int a1, int a2) */
+			BTF_FUNC_PROTO_ENC(0, 2),			/* [2] */
+				BTF_FUNC_PROTO_ARG_ENC(NAME_NTH(1), 1),
+				BTF_FUNC_PROTO_ARG_ENC(NAME_NTH(2), 1),
+			BTF_FUNC_ENC(NAME_NTH(3), 2),			/* [3] */
+			/* void f(int a1, int a2) */
+			BTF_FUNC_PROTO_ENC(0, 2),			/* [4] */
+				BTF_FUNC_PROTO_ARG_ENC(NAME_NTH(1), 1),
+				BTF_FUNC_PROTO_ARG_ENC(NAME_NTH(2), 1),
+			BTF_FUNC_ENC(NAME_NTH(3), 4),			/* [5] */
+			/* tag -> f: tag1, tag2 */
+			BTF_DECL_TAG_ENC(NAME_NTH(4), 3, -1),		/* [6] */
+			BTF_DECL_TAG_ENC(NAME_NTH(5), 3, -1),		/* [7] */
+			/* tag -> f/a2: tag1, tag2 */
+			BTF_DECL_TAG_ENC(NAME_NTH(4), 3, 1),		/* [8] */
+			BTF_DECL_TAG_ENC(NAME_NTH(5), 3, 1),		/* [9] */
+			/* tag -> f: tag1, tag3 */
+			BTF_DECL_TAG_ENC(NAME_NTH(4), 5, -1),		/* [10] */
+			BTF_DECL_TAG_ENC(NAME_NTH(6), 5, -1),		/* [11] */
+			/* tag -> f/a2: tag1, tag3 */
+			BTF_DECL_TAG_ENC(NAME_NTH(4), 5, 1),		/* [12] */
+			BTF_DECL_TAG_ENC(NAME_NTH(6), 5, 1),		/* [13] */
+			BTF_END_RAW,
+		},
+		BTF_STR_SEC("\0a1\0a2\0f\0tag1\0tag2\0tag3"),
+	},
+	.expect = {
+		.raw_types = {
+			BTF_FUNC_ENC(NAME_NTH(3), 9),			/* [1] */
+			BTF_DECL_TAG_ENC(NAME_NTH(4), 1, -1),		/* [2] */
+			BTF_DECL_TAG_ENC(NAME_NTH(4), 1, 1),		/* [3] */
+			BTF_DECL_TAG_ENC(NAME_NTH(5), 1, -1),		/* [4] */
+			BTF_DECL_TAG_ENC(NAME_NTH(5), 1, 1),		/* [5] */
+			BTF_DECL_TAG_ENC(NAME_NTH(6), 1, -1),		/* [6] */
+			BTF_DECL_TAG_ENC(NAME_NTH(6), 1, 1),		/* [7] */
+			BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4),	/* [8] */
+			BTF_FUNC_PROTO_ENC(0, 2),			/* [9] */
+				BTF_FUNC_PROTO_ARG_ENC(NAME_NTH(1), 8),
+				BTF_FUNC_PROTO_ARG_ENC(NAME_NTH(2), 8),
+			BTF_END_RAW,
+		},
+		BTF_STR_SEC("\0a1\0a2\0f\0tag1\0tag2\0tag3"),
+	},
+	.opts = {
+		.sort_by_kind_name = true,
+	},
+},
+{
+	.descr = "dedup_sort: struct/struct_member tags",
+	.input = {
+		.raw_types = {
+			/* int */
+			BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4),	/* [1] */
+			BTF_STRUCT_ENC(NAME_NTH(1), 2, 8),		/* [2] */
+				BTF_MEMBER_ENC(NAME_NTH(2), 1, 0),
+				BTF_MEMBER_ENC(NAME_NTH(3), 1, 32),
+			BTF_STRUCT_ENC(NAME_NTH(1), 2, 8),		/* [3] */
+				BTF_MEMBER_ENC(NAME_NTH(2), 1, 0),
+				BTF_MEMBER_ENC(NAME_NTH(3), 1, 32),
+			/* tag -> t: tag1, tag2 */
+			BTF_DECL_TAG_ENC(NAME_NTH(4), 2, -1),		/* [4] */
+			BTF_DECL_TAG_ENC(NAME_NTH(5), 2, -1),		/* [5] */
+			/* tag -> t/m2: tag1, tag2 */
+			BTF_DECL_TAG_ENC(NAME_NTH(4), 2, 1),		/* [6] */
+			BTF_DECL_TAG_ENC(NAME_NTH(5), 2, 1),		/* [7] */
+			/* tag -> t: tag1, tag3 */
+			BTF_DECL_TAG_ENC(NAME_NTH(4), 3, -1),		/* [8] */
+			BTF_DECL_TAG_ENC(NAME_NTH(6), 3, -1),		/* [9] */
+			/* tag -> t/m2: tag1, tag3 */
+			BTF_DECL_TAG_ENC(NAME_NTH(4), 3, 1),		/* [10] */
+			BTF_DECL_TAG_ENC(NAME_NTH(6), 3, 1),		/* [11] */
+			BTF_END_RAW,
+		},
+		BTF_STR_SEC("\0t\0m1\0m2\0tag1\0tag2\0tag3"),
+	},
+	.expect = {
+		.raw_types = {
+			BTF_STRUCT_ENC(NAME_NTH(1), 2, 8),		/* [1] */
+				BTF_MEMBER_ENC(NAME_NTH(2), 8, 0),
+				BTF_MEMBER_ENC(NAME_NTH(3), 8, 32),
+			BTF_DECL_TAG_ENC(NAME_NTH(4), 1, -1),		/* [2] */
+			BTF_DECL_TAG_ENC(NAME_NTH(4), 1, 1),		/* [3] */
+			BTF_DECL_TAG_ENC(NAME_NTH(5), 1, -1),		/* [4] */
+			BTF_DECL_TAG_ENC(NAME_NTH(5), 1, 1),		/* [5] */
+			BTF_DECL_TAG_ENC(NAME_NTH(6), 1, -1),		/* [6] */
+			BTF_DECL_TAG_ENC(NAME_NTH(6), 1, 1),		/* [7] */
+			BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4),	/* [8] */
+			BTF_END_RAW,
+		},
+		BTF_STR_SEC("\0t\0m1\0m2\0tag1\0tag2\0tag3"),
+	},
+	.opts = {
+		.sort_by_kind_name = true,
+	},
+},
 };
 
 static int btf_type_size(const struct btf_type *t)
Signature · 1 line
2.34.1
maintainer
#27 lore raw

Re: [RFC PATCH v2 4/5] selftests/bpf: add tests for BTF deduplication and sorting

On Mon, 2025-10-20 at 17:39 +0800, Donglin Peng wrote:

[...]

Quoted 15 lines
tools/testing/selftests/bpf/prog_tests/btf.c +15 -0
+{
+	.descr = "dedup_sort: strings deduplication",
+	.input = {
+		.raw_types = {
+			BTF_TYPE_INT_ENC(NAME_NTH(1), BTF_INT_SIGNED, 0, 32, 4),
+			BTF_TYPE_INT_ENC(NAME_NTH(2), BTF_INT_SIGNED, 0, 64, 8),
+			BTF_TYPE_INT_ENC(NAME_NTH(3), BTF_INT_SIGNED, 0, 32, 4),
+			BTF_TYPE_INT_ENC(NAME_NTH(4), BTF_INT_SIGNED, 0, 64, 8),
+			BTF_TYPE_INT_ENC(NAME_NTH(5), BTF_INT_SIGNED, 0, 32, 4),
+			BTF_END_RAW,
+		},
+		BTF_STR_SEC("\0int\0long int\0int\0long int\0int"),
+	},
+	.expect = {
+		.raw_types = {

tools/testing/selftests/bpf/prog_tests/btf.c static struct btf_dedup_test dedup_tests[] = { · line 8049

Quoted 10 lines
tools/testing/selftests/bpf/prog_tests/btf.c +10 -0
+			BTF_TYPE_INT_ENC(NAME_NTH(1), BTF_INT_SIGNED, 0, 32, 4),
+			BTF_TYPE_INT_ENC(NAME_NTH(2), BTF_INT_SIGNED, 0, 64, 8),
+			BTF_END_RAW,
+		},
+		BTF_STR_SEC("\0int\0long int"),
+	},
+	.opts = {
+		.sort_by_kind_name = true,
+	},
+},

I think that having so many tests for this feature is redundant. E.g. above strings handling test does not seem necessary, as btf__dedup_compact_and_sort_types() does not really change anything with regards to strings handling.
I'd say that a single test including elements with and without names, and elements of different kind should suffice.

[...]

#28 lore raw

Re: [RFC PATCH v2 4/5] selftests/bpf: add tests for BTF deduplication and sorting

Quoted 29 lines · Eduard Zingerman

On Mon, 2025-10-20 at 17:39 +0800, Donglin Peng wrote:

[...]

Quoted 24 lines
tools/testing/selftests/bpf/prog_tests/btf.c +24 -0
+{
+     .descr = "dedup_sort: strings deduplication",
+     .input = {
+             .raw_types = {
+                     BTF_TYPE_INT_ENC(NAME_NTH(1), BTF_INT_SIGNED, 0, 32, 4),
+                     BTF_TYPE_INT_ENC(NAME_NTH(2), BTF_INT_SIGNED, 0, 64, 8),
+                     BTF_TYPE_INT_ENC(NAME_NTH(3), BTF_INT_SIGNED, 0, 32, 4),
+                     BTF_TYPE_INT_ENC(NAME_NTH(4), BTF_INT_SIGNED, 0, 64, 8),
+                     BTF_TYPE_INT_ENC(NAME_NTH(5), BTF_INT_SIGNED, 0, 32, 4),
+                     BTF_END_RAW,
+             },
+             BTF_STR_SEC("\0int\0long int\0int\0long int\0int"),
+     },
+     .expect = {
+             .raw_types = {
+                     BTF_TYPE_INT_ENC(NAME_NTH(1), BTF_INT_SIGNED, 0, 32, 4),
+                     BTF_TYPE_INT_ENC(NAME_NTH(2), BTF_INT_SIGNED, 0, 64, 8),
+                     BTF_END_RAW,
+             },
+             BTF_STR_SEC("\0int\0long int"),
+     },
+     .opts = {
+             .sort_by_kind_name = true,
+     },
Quoted 8 lines
Quoted 1 line

+},

I think that having so many tests for this feature is redundant. E.g. above strings handling test does not seem necessary, as btf__dedup_compact_and_sort_types() does not really change anything with regards to strings handling.
I'd say that a single test including elements with and without names, and elements of different kind should suffice.

Thanks for the suggestion.

Quoted 2 lines

[...]

#29 lore raw

RFC PATCH v2 5/5 btf: add CONFIG_BPF_SORT_BTF_BY_KIND_NAME

In reply to Donglin Peng

Pahole v1.32 and later supports BTF sorting. Add a new configuration option to control whether to enable this feature for vmlinux and kernel modules.

Cc Eduard Zingerman <[email protected]>
Cc Alexei Starovoitov <[email protected]>
Cc Andrii Nakryiko <[email protected]>
Cc Alan Maguire <[email protected]>
Cc Song Liu <[email protected]>
---
 kernel/bpf/Kconfig   | 8 ++++++++
 scripts/Makefile.btf | 5 +++++
 2 files changed, 13 insertions(+)
kernel/bpf/Kconfig +8 -0
index eb3de35734f0..08251a250f06 100644
@@ -101,4 +101,12 @@ config BPF_LSM
 
 	  If you are unsure how to answer this question, answer N.
 
+config BPF_SORT_BTF_BY_KIND_NAME
+	bool "Sort BTF types by kind and name"
+	depends on BPF_SYSCALL
+	help
+	  This option sorts BTF types in vmlinux and kernel modules by their
+	  kind and name, enabling binary search for btf_find_by_name_kind()
+	  and significantly improving its lookup performance.
+
 endmenu # "BPF subsystem"
scripts/Makefile.btf +5 -0
index db76335dd917..3f1a0b3c3f3f 100644
@@ -29,6 +29,11 @@ ifneq ($(KBUILD_EXTMOD),)
 module-pahole-flags-$(call test-ge, $(pahole-ver), 128) += --btf_features=distilled_base
 endif
 
+ifeq ($(call test-ge, $(pahole-ver), 132),y)
+pahole-flags-$(CONFIG_BPF_SORT_BTF_BY_KIND_NAME) 	+= --btf_features=sort
+module-pahole-flags-$(CONFIG_BPF_SORT_BTF_BY_KIND_NAME) += --btf_features=sort
+endif
+
 endif
 
 pahole-flags-$(CONFIG_PAHOLE_HAS_LANG_EXCLUDE)		+= --lang_exclude=rust
Signature · 1 line
2.34.1
maintainer
#30 lore raw

Re: [RFC PATCH v2 5/5] btf: add CONFIG_BPF_SORT_BTF_BY_KIND_NAME

On Mon, 2025-10-20 at 17:39 +0800, Donglin Peng wrote:

[...]

Quoted 6 lines
kernel/bpf/Kconfig +0 -0
index eb3de35734f0..08251a250f06 100644
@@ -101,4 +101,12 @@ config BPF_LSM
 

kernel/bpf/Kconfig config BPF_LSM · line 111

Quoted 10 lines
kernel/bpf/Kconfig +8 -0
 	  If you are unsure how to answer this question, answer N.
 
+config BPF_SORT_BTF_BY_KIND_NAME
+	bool "Sort BTF types by kind and name"
+	depends on BPF_SYSCALL
+	help
+	  This option sorts BTF types in vmlinux and kernel modules by their
+	  kind and name, enabling binary search for btf_find_by_name_kind()
+	  and significantly improving its lookup performance.
+

Why having this as an option?
There are no downsides to always enabling, right? The cost of sorting btf at build time should be negligible.

[...]

#31 lore raw

Re: [RFC PATCH v2 5/5] btf: add CONFIG_BPF_SORT_BTF_BY_KIND_NAME

Quoted 13 lines · Eduard Zingerman

On Mon, 2025-10-20 at 17:39 +0800, Donglin Peng wrote:

[...]

Quoted 8 lines
kernel/bpf/Kconfig +0 -0
index eb3de35734f0..08251a250f06 100644
@@ -101,4 +101,12 @@ config BPF_LSM
 
        If you are unsure how to answer this question, answer N.
 
Quoted 12 lines

kernel/bpf/Kconfig config BPF_LSM · line 111

Quoted 8 lines
kernel/bpf/Kconfig +8 -0
+config BPF_SORT_BTF_BY_KIND_NAME
+     bool "Sort BTF types by kind and name"
+     depends on BPF_SYSCALL
+     help
+       This option sorts BTF types in vmlinux and kernel modules by their
+       kind and name, enabling binary search for btf_find_by_name_kind()
+       and significantly improving its lookup performance.
+

Why having this as an option?
There are no downsides to always enabling, right? The cost of sorting btf at build time should be negligible.

Thanks, I'll remove this config option in the next version as suggested.

Quoted 2 lines

[...]

#32 lore raw

Re: [RFC PATCH v2 5/5] btf: add CONFIG_BPF_SORT_BTF_BY_KIND_NAME

In reply to Donglin Peng
Quoted 38 lines · Donglin Peng

Pahole v1.32 and later supports BTF sorting. Add a new configuration option to control whether to enable this feature for vmlinux and kernel modules.

Cc Eduard Zingerman <[email protected]>
Cc Alexei Starovoitov <[email protected]>
Cc Andrii Nakryiko <[email protected]>
Cc Alan Maguire <[email protected]>
Cc Song Liu <[email protected]>
---
 kernel/bpf/Kconfig   | 8 ++++++++
 scripts/Makefile.btf | 5 +++++
 2 files changed, 13 insertions(+)
kernel/bpf/Kconfig +8 -0
index eb3de35734f0..08251a250f06 100644
@@ -101,4 +101,12 @@ config BPF_LSM
 
 	  If you are unsure how to answer this question, answer N.
 
+config BPF_SORT_BTF_BY_KIND_NAME
+	bool "Sort BTF types by kind and name"
+	depends on BPF_SYSCALL
+	help
+	  This option sorts BTF types in vmlinux and kernel modules by their
+	  kind and name, enabling binary search for btf_find_by_name_kind()
+	  and significantly improving its lookup performance.
+
 endmenu # "BPF subsystem"
scripts/Makefile.btf +0 -0
index db76335dd917..3f1a0b3c3f3f 100644

scripts/Makefile.btf ifneq ($(KBUILD_EXTMOD),) · line 36

Quoted 8 lines
scripts/Makefile.btf +5 -0
@@ -29,6 +29,11 @@ ifneq ($(KBUILD_EXTMOD),)
 module-pahole-flags-$(call test-ge, $(pahole-ver), 128) += --btf_features=distilled_base
 endif
 
+ifeq ($(call test-ge, $(pahole-ver), 132),y)
+pahole-flags-$(CONFIG_BPF_SORT_BTF_BY_KIND_NAME) 	+= --btf_features=sort
+module-pahole-flags-$(CONFIG_BPF_SORT_BTF_BY_KIND_NAME) += --btf_features=sort
+endif
+

perhaps it's useful informationally, but you don't need to wrap the addition of the sort flag in a pahole version check; unsupported btf_features are just ignored. Also we're at v1.30 in pahole now (we'll be releasing 1.31 shortly hopefully), so any version check should be v1.30/v1.31. I'd say just leave out the version check though.

Alan

#33 lore raw

Re: [RFC PATCH v2 5/5] btf: add CONFIG_BPF_SORT_BTF_BY_KIND_NAME

Quoted 43 lines · Alan Maguire
Quoted 41 lines · Donglin Peng

Pahole v1.32 and later supports BTF sorting. Add a new configuration option to control whether to enable this feature for vmlinux and kernel modules.

Cc Eduard Zingerman <[email protected]>
Cc Alexei Starovoitov <[email protected]>
Cc Andrii Nakryiko <[email protected]>
Cc Alan Maguire <[email protected]>
Cc Song Liu <[email protected]>
---
 kernel/bpf/Kconfig   | 8 ++++++++
 scripts/Makefile.btf | 5 +++++
 2 files changed, 13 insertions(+)
kernel/bpf/Kconfig +8 -0
index eb3de35734f0..08251a250f06 100644
@@ -101,4 +101,12 @@ config BPF_LSM
 
        If you are unsure how to answer this question, answer N.
 
+config BPF_SORT_BTF_BY_KIND_NAME
+     bool "Sort BTF types by kind and name"
+     depends on BPF_SYSCALL
+     help
+       This option sorts BTF types in vmlinux and kernel modules by their
+       kind and name, enabling binary search for btf_find_by_name_kind()
+       and significantly improving its lookup performance.
+
 endmenu # "BPF subsystem"
scripts/Makefile.btf +0 -0
index db76335dd917..3f1a0b3c3f3f 100644
@@ -29,6 +29,11 @@ ifneq ($(KBUILD_EXTMOD),)
 module-pahole-flags-$(call test-ge, $(pahole-ver), 128) += --btf_features=distilled_base
 endif
 
Quoted 11 lines

scripts/Makefile.btf ifneq ($(KBUILD_EXTMOD),) · line 36

Quoted 5 lines
scripts/Makefile.btf +5 -0
+ifeq ($(call test-ge, $(pahole-ver), 132),y)
+pahole-flags-$(CONFIG_BPF_SORT_BTF_BY_KIND_NAME)     += --btf_features=sort
+module-pahole-flags-$(CONFIG_BPF_SORT_BTF_BY_KIND_NAME) += --btf_features=sort
+endif
+

perhaps it's useful informationally, but you don't need to wrap the addition of the sort flag in a pahole version check; unsupported btf_features are just ignored. Also we're at v1.30 in pahole now (we'll be releasing 1.31 shortly hopefully), so any version check should be v1.30/v1.31. I'd say just leave out the version check though.

Understood, thanks. Will do.

Quoted 2 lines

Alan