[RFC PATCH v2 2/5] btf: sort BTF types by kind and name to enable binary search
From: Donglin Peng
Date: Mon Oct 20 2025 - 05:39:57 EST
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 <eddyz87@xxxxxxxxx>
Cc: Alexei Starovoitov <ast@xxxxxxxxxx>
Cc: Andrii Nakryiko <andrii.nakryiko@xxxxxxxxx>
Cc: Alan Maguire <alan.maguire@xxxxxxxxxx>
Cc: Song Liu <song@xxxxxxxxxx>
Co-developed-by: Eduard Zingerman <eddyz87@xxxxxxxxx>
Signed-off-by: pengdonglin <pengdonglin@xxxxxxxxxx>
Signed-off-by: Donglin Peng <dolinux.peng@xxxxxxxxx>
---
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
diff --git a/include/linux/btf.h b/include/linux/btf.h
index ddc53a7ac7cd..c6fe5e689ab9 100644
--- a/include/linux/btf.h
+++ b/include/linux/btf.h
@@ -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
diff --git a/kernel/bpf/Makefile b/kernel/bpf/Makefile
index 7fd0badfacb1..c9d8f986c7e1 100644
--- a/kernel/bpf/Makefile
+++ b/kernel/bpf/Makefile
@@ -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)
diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c
index c414cf37e1bd..11b05f4eb07d 100644
--- a/kernel/bpf/btf.c
+++ b/kernel/bpf/btf.c
@@ -259,6 +259,7 @@ struct btf {
void *nohdr_data;
struct btf_header hdr;
u32 nr_types; /* includes VOID for base BTF */
+ u32 nr_sorted_types;
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;
diff --git a/kernel/bpf/btf_sort.c b/kernel/bpf/btf_sort.c
new file mode 100644
index 000000000000..898f9189952c
--- /dev/null
+++ b/kernel/bpf/btf_sort.c
@@ -0,0 +1,2 @@
+// SPDX-License-Identifier: (LGPL-2.1 OR BSD-2-Clause)
+#include "../../tools/lib/bpf/btf_sort.c"
diff --git a/tools/lib/bpf/Build b/tools/lib/bpf/Build
index c80204bb72a2..ed7c2506e22d 100644
--- a/tools/lib/bpf/Build
+++ b/tools/lib/bpf/Build
@@ -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
diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c
index 18907f0fcf9f..87e47f0b78ba 100644
--- a/tools/lib/bpf/btf.c
+++ b/tools/lib/bpf/btf.c
@@ -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
diff --git a/tools/lib/bpf/btf.h b/tools/lib/bpf/btf.h
index ccfd905f03df..9a7cfe6b4bb3 100644
--- a/tools/lib/bpf/btf.h
+++ b/tools/lib/bpf/btf.h
@@ -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;
diff --git a/tools/lib/bpf/btf_sort.c b/tools/lib/bpf/btf_sort.c
new file mode 100644
index 000000000000..2ad4a56f1c08
--- /dev/null
+++ b/tools/lib/bpf/btf_sort.c
@@ -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);
+}
+
diff --git a/tools/lib/bpf/libbpf_internal.h b/tools/lib/bpf/libbpf_internal.h
index 35b2527bedec..f71f3e70c51c 100644
--- a/tools/lib/bpf/libbpf_internal.h
+++ b/tools/lib/bpf/libbpf_internal.h
@@ -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)
{
--
2.34.1