From: Donglin Peng <pengdonglin@xiaomi.com>
Improve btf_find_by_name_kind() performance by adding binary search
support for sorted types. Falls back to linear search for compatibility.
Cc: Eduard Zingerman <eddyz87@gmail.com>
Cc: Alexei Starovoitov <ast@kernel.org>
Cc: Andrii Nakryiko <andrii.nakryiko@gmail.com>
Cc: Alan Maguire <alan.maguire@oracle.com>
Cc: Ihor Solodrai <ihor.solodrai@linux.dev>
Cc: Xiaoqin Zhang <zhangxiaoqin@xiaomi.com>
Signed-off-by: Donglin Peng <pengdonglin@xiaomi.com>
---
include/linux/btf.h | 1 +
kernel/bpf/btf.c | 91 ++++++++++++++++++++++++++++++++++++++++-----
2 files changed, 83 insertions(+), 9 deletions(-)
diff --git a/include/linux/btf.h b/include/linux/btf.h
index 691f09784933..78dc79810c7d 100644
--- a/include/linux/btf.h
+++ b/include/linux/btf.h
@@ -219,6 +219,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_named_start_id(const struct btf *btf, bool own);
struct btf *btf_base_btf(const struct btf *btf);
bool btf_type_is_i32(const struct btf_type *t);
bool btf_type_is_i64(const struct btf_type *t);
diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c
index 539c9fdea41d..d1f4b984100d 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 named_start_id;
u32 types_size;
u32 data_size;
refcount_t refcnt;
@@ -494,6 +495,11 @@ static bool btf_type_is_modifier(const struct btf_type *t)
return false;
}
+static int btf_start_id(const struct btf *btf)
+{
+ return btf->start_id + (btf->base_btf ? 0 : 1);
+}
+
bool btf_type_is_void(const struct btf_type *t)
{
return t == &btf_void;
@@ -544,21 +550,85 @@ u32 btf_nr_types(const struct btf *btf)
return total;
}
+/* btf_named_start_id - Get the named starting ID for the BTF
+ * @btf: Pointer to the target BTF object
+ * @own: Flag indicating whether to query only the current BTF (true = current BTF only,
+ * false = recursively traverse the base BTF chain)
+ *
+ * Return value rules:
+ * 1. For a sorted btf, return its named_start_id
+ * 2. Else for a split BTF, return its start_id
+ * 3. Else for a base BTF, return 1
+ */
+u32 btf_named_start_id(const struct btf *btf, bool own)
+{
+ const struct btf *base_btf = btf;
+
+ while (!own && base_btf->base_btf)
+ base_btf = base_btf->base_btf;
+
+ return base_btf->named_start_id ?: (base_btf->start_id ?: 1);
+}
+
+static s32 btf_find_by_name_kind_bsearch(const struct btf *btf, const char *name)
+{
+ const struct btf_type *t;
+ const char *tname;
+ s32 l, r, m;
+
+ l = btf_named_start_id(btf, true);
+ r = btf_nr_types(btf) - 1;
+ while (l <= r) {
+ m = l + (r - l) / 2;
+ t = btf_type_by_id(btf, m);
+ tname = btf_name_by_offset(btf, t->name_off);
+ if (strcmp(tname, name) >= 0) {
+ if (l == r)
+ return r;
+ r = m;
+ } else {
+ l = m + 1;
+ }
+ }
+
+ return btf_nr_types(btf);
+}
+
s32 btf_find_by_name_kind(const struct btf *btf, const char *name, u8 kind)
{
+ const struct btf *base_btf = btf_base_btf(btf);
const struct btf_type *t;
const char *tname;
- u32 i, total;
+ s32 idx;
- total = btf_nr_types(btf);
- for (i = 1; i < total; i++) {
- t = btf_type_by_id(btf, i);
- if (BTF_INFO_KIND(t->info) != kind)
- continue;
+ if (base_btf) {
+ idx = btf_find_by_name_kind(base_btf, name, kind);
+ if (idx > 0)
+ return idx;
+ }
- tname = btf_name_by_offset(btf, t->name_off);
- if (!strcmp(tname, name))
- return i;
+ if (btf->named_start_id > 0 && name[0]) {
+ idx = btf_find_by_name_kind_bsearch(btf, name);
+ for (; idx < btf_nr_types(btf); idx++) {
+ t = btf_type_by_id(btf, idx);
+ tname = btf_name_by_offset(btf, t->name_off);
+ if (strcmp(tname, name) != 0)
+ return -ENOENT;
+ if (BTF_INFO_KIND(t->info) == kind)
+ return idx;
+ }
+ } else {
+ u32 i, total;
+
+ total = btf_nr_types(btf);
+ for (i = btf_start_id(btf); i < total; i++) {
+ t = btf_type_by_id(btf, i);
+ if (BTF_INFO_KIND(t->info) != kind)
+ continue;
+ tname = btf_name_by_offset(btf, t->name_off);
+ if (strcmp(tname, name) == 0)
+ return i;
+ }
}
return -ENOENT;
@@ -5791,6 +5861,7 @@ static struct btf *btf_parse(const union bpf_attr *attr, bpfptr_t uattr, u32 uat
goto errout;
}
env->btf = btf;
+ btf->named_start_id = 0;
data = kvmalloc(attr->btf_size, GFP_KERNEL | __GFP_NOWARN);
if (!data) {
@@ -6210,6 +6281,7 @@ static struct btf *btf_parse_base(struct btf_verifier_env *env, const char *name
btf->data = data;
btf->data_size = data_size;
btf->kernel_btf = true;
+ btf->named_start_id = 0;
snprintf(btf->name, sizeof(btf->name), "%s", name);
err = btf_parse_hdr(env);
@@ -6327,6 +6399,7 @@ static struct btf *btf_parse_module(const char *module_name, const void *data,
btf->start_id = base_btf->nr_types;
btf->start_str_off = base_btf->hdr.str_len;
btf->kernel_btf = true;
+ btf->named_start_id = 0;
snprintf(btf->name, sizeof(btf->name), "%s", module_name);
btf->data = kvmemdup(data, data_size, GFP_KERNEL | __GFP_NOWARN);
--
2.34.1On Fri, Jan 9, 2026 at 5:00 AM Donglin Peng <dolinux.peng@gmail.com> wrote:
>
> From: Donglin Peng <pengdonglin@xiaomi.com>
>
> Improve btf_find_by_name_kind() performance by adding binary search
> support for sorted types. Falls back to linear search for compatibility.
>
> Cc: Eduard Zingerman <eddyz87@gmail.com>
> Cc: Alexei Starovoitov <ast@kernel.org>
> Cc: Andrii Nakryiko <andrii.nakryiko@gmail.com>
> Cc: Alan Maguire <alan.maguire@oracle.com>
> Cc: Ihor Solodrai <ihor.solodrai@linux.dev>
> Cc: Xiaoqin Zhang <zhangxiaoqin@xiaomi.com>
> Signed-off-by: Donglin Peng <pengdonglin@xiaomi.com>
> ---
> include/linux/btf.h | 1 +
> kernel/bpf/btf.c | 91 ++++++++++++++++++++++++++++++++++++++++-----
> 2 files changed, 83 insertions(+), 9 deletions(-)
>
[...]
> s32 btf_find_by_name_kind(const struct btf *btf, const char *name, u8 kind)
> {
> + const struct btf *base_btf = btf_base_btf(btf);
> const struct btf_type *t;
> const char *tname;
> - u32 i, total;
> + s32 idx;
>
> - total = btf_nr_types(btf);
> - for (i = 1; i < total; i++) {
> - t = btf_type_by_id(btf, i);
> - if (BTF_INFO_KIND(t->info) != kind)
> - continue;
> + if (base_btf) {
> + idx = btf_find_by_name_kind(base_btf, name, kind);
> + if (idx > 0)
> + return idx;
> + }
>
> - tname = btf_name_by_offset(btf, t->name_off);
> - if (!strcmp(tname, name))
> - return i;
> + if (btf->named_start_id > 0 && name[0]) {
> + idx = btf_find_by_name_kind_bsearch(btf, name);
> + for (; idx < btf_nr_types(btf); idx++) {
same nit about inconsistent btf_nr_types() usage between two branches:
compute once early and use in both branches
(fixed up similarly to libbpf implementation; also fixed up comment style )
> + t = btf_type_by_id(btf, idx);
> + tname = btf_name_by_offset(btf, t->name_off);
> + if (strcmp(tname, name) != 0)
> + return -ENOENT;
> + if (BTF_INFO_KIND(t->info) == kind)
> + return idx;
> + }
[...]
On Wed, Jan 14, 2026 at 8:29 AM Andrii Nakryiko
<andrii.nakryiko@gmail.com> wrote:
>
> On Fri, Jan 9, 2026 at 5:00 AM Donglin Peng <dolinux.peng@gmail.com> wrote:
> >
> > From: Donglin Peng <pengdonglin@xiaomi.com>
> >
> > Improve btf_find_by_name_kind() performance by adding binary search
> > support for sorted types. Falls back to linear search for compatibility.
> >
> > Cc: Eduard Zingerman <eddyz87@gmail.com>
> > Cc: Alexei Starovoitov <ast@kernel.org>
> > Cc: Andrii Nakryiko <andrii.nakryiko@gmail.com>
> > Cc: Alan Maguire <alan.maguire@oracle.com>
> > Cc: Ihor Solodrai <ihor.solodrai@linux.dev>
> > Cc: Xiaoqin Zhang <zhangxiaoqin@xiaomi.com>
> > Signed-off-by: Donglin Peng <pengdonglin@xiaomi.com>
> > ---
> > include/linux/btf.h | 1 +
> > kernel/bpf/btf.c | 91 ++++++++++++++++++++++++++++++++++++++++-----
> > 2 files changed, 83 insertions(+), 9 deletions(-)
> >
>
> [...]
>
> > s32 btf_find_by_name_kind(const struct btf *btf, const char *name, u8 kind)
> > {
> > + const struct btf *base_btf = btf_base_btf(btf);
> > const struct btf_type *t;
> > const char *tname;
> > - u32 i, total;
> > + s32 idx;
> >
> > - total = btf_nr_types(btf);
> > - for (i = 1; i < total; i++) {
> > - t = btf_type_by_id(btf, i);
> > - if (BTF_INFO_KIND(t->info) != kind)
> > - continue;
> > + if (base_btf) {
> > + idx = btf_find_by_name_kind(base_btf, name, kind);
> > + if (idx > 0)
> > + return idx;
> > + }
> >
> > - tname = btf_name_by_offset(btf, t->name_off);
> > - if (!strcmp(tname, name))
> > - return i;
> > + if (btf->named_start_id > 0 && name[0]) {
> > + idx = btf_find_by_name_kind_bsearch(btf, name);
> > + for (; idx < btf_nr_types(btf); idx++) {
>
> same nit about inconsistent btf_nr_types() usage between two branches:
> compute once early and use in both branches
>
> (fixed up similarly to libbpf implementation; also fixed up comment style )
Thanks, I will fix it.
>
> > + t = btf_type_by_id(btf, idx);
> > + tname = btf_name_by_offset(btf, t->name_off);
> > + if (strcmp(tname, name) != 0)
> > + return -ENOENT;
> > + if (BTF_INFO_KIND(t->info) == kind)
> > + return idx;
> > + }
>
> [...]
© 2016 - 2026 Red Hat, Inc.