1. Patchew
  2. linux
  3. [PATCH bpf-next v10 00/13] Improve the performance of BTF type lookups with binary search
  4. View patch

[PATCH bpf-next v10 08/13] bpf: Skip anonymous types in type lookup for performance

Donglin Peng posted 13 patches 1 day ago
[PATCH bpf-next v10 08/13] bpf: Skip anonymous types in type lookup for performance
Posted by Donglin Peng 1 day ago 
From: pengdonglin <pengdonglin@xiaomi.com>

Currently, vmlinux and kernel module BTFs are unconditionally
sorted during the build phase, with named types placed at the
end. Thus, anonymous types should be skipped when starting the
search. In my vmlinux BTF, the number of anonymous types is
61,747, which means the loop count can be reduced by 61,747.

Cc: Eduard Zingerman <eddyz87@gmail.com>
Cc: Alexei Starovoitov <ast@kernel.org>
Cc: Andrii Nakryiko <andrii.nakryiko@gmail.com>
Cc: Alan Maguire <alan.maguire@oracle.com>
Cc: Ihor Solodrai <ihor.solodrai@linux.dev>
Cc: Xiaoqin Zhang <zhangxiaoqin@xiaomi.com>
Signed-off-by: pengdonglin <pengdonglin@xiaomi.com>
---
 include/linux/btf.h   |  1 +
 kernel/bpf/btf.c      | 24 ++++++++++++++++++++----
 kernel/bpf/verifier.c |  7 +------
 3 files changed, 22 insertions(+), 10 deletions(-)

diff --git a/include/linux/btf.h b/include/linux/btf.h
index f06976ffb63f..2d28f2b22ae5 100644
--- a/include/linux/btf.h
+++ b/include/linux/btf.h
@@ -220,6 +220,7 @@ bool btf_is_module(const struct btf *btf);
 bool btf_is_vmlinux(const struct btf *btf);
 struct module *btf_try_get_module(const struct btf *btf);
 u32 btf_nr_types(const struct btf *btf);
+u32 btf_sorted_start_id(const struct btf *btf);
 struct btf *btf_base_btf(const struct btf *btf);
 bool btf_type_is_i32(const struct btf_type *t);
 bool btf_type_is_i64(const struct btf_type *t);
diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c
index a9e2345558c0..3aeb4f00cbfe 100644
--- a/kernel/bpf/btf.c
+++ b/kernel/bpf/btf.c
@@ -550,6 +550,11 @@ u32 btf_nr_types(const struct btf *btf)
 	return total;
 }
 
+u32 btf_sorted_start_id(const struct btf *btf)
+{
+	return btf->sorted_start_id ?: (btf->start_id ?: 1);
+}
+
 /*
  * Assuming that types are sorted by name in ascending order.
  */
@@ -3540,9 +3545,14 @@ const char *btf_find_decl_tag_value(const struct btf *btf, const struct btf_type
 {
 	const char *value = NULL;
 	const struct btf_type *t;
+	const struct btf *base_btf = btf;
 	int len, id;
 
-	id = btf_find_next_decl_tag(btf, pt, comp_idx, tag_key, 0);
+	while (base_btf->base_btf)
+		base_btf = base_btf->base_btf;
+
+	id = btf_find_next_decl_tag(btf, pt, comp_idx, tag_key,
+				    btf_sorted_start_id(base_btf) - 1);
 	if (id < 0)
 		return ERR_PTR(id);
 
@@ -7787,6 +7797,7 @@ int btf_prepare_func_args(struct bpf_verifier_env *env, int subprog)
 	struct bpf_prog *prog = env->prog;
 	enum bpf_prog_type prog_type = prog->type;
 	struct btf *btf = prog->aux->btf;
+	struct btf *base_btf;
 	const struct btf_param *args;
 	const struct btf_type *t, *ref_t, *fn_t;
 	u32 i, nargs, btf_id;
@@ -7852,12 +7863,17 @@ int btf_prepare_func_args(struct bpf_verifier_env *env, int subprog)
 			tname);
 		return -EINVAL;
 	}
+
+	base_btf = btf;
+	while (base_btf->base_btf)
+		base_btf = base_btf->base_btf;
+
 	/* Convert BTF function arguments into verifier types.
 	 * Only PTR_TO_CTX and SCALAR are supported atm.
 	 */
 	for (i = 0; i < nargs; i++) {
 		u32 tags = 0;
-		int id = 0;
+		int id = btf_sorted_start_id(base_btf) - 1;
 
 		/* 'arg:<tag>' decl_tag takes precedence over derivation of
 		 * register type from BTF type itself
@@ -9338,7 +9354,7 @@ bpf_core_find_cands(struct bpf_core_ctx *ctx, u32 local_type_id)
 	}
 
 	/* Attempt to find target candidates in vmlinux BTF first */
-	cands = bpf_core_add_cands(cands, main_btf, 1);
+	cands = bpf_core_add_cands(cands, main_btf, btf_sorted_start_id(main_btf));
 	if (IS_ERR(cands))
 		return ERR_CAST(cands);
 
@@ -9370,7 +9386,7 @@ bpf_core_find_cands(struct bpf_core_ctx *ctx, u32 local_type_id)
 		 */
 		btf_get(mod_btf);
 		spin_unlock_bh(&btf_idr_lock);
-		cands = bpf_core_add_cands(cands, mod_btf, btf_nr_types(main_btf));
+		cands = bpf_core_add_cands(cands, mod_btf, btf_sorted_start_id(mod_btf));
 		btf_put(mod_btf);
 		if (IS_ERR(cands))
 			return ERR_CAST(cands);
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index d6b8a77fbe3b..1a9da59d8589 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -20651,12 +20651,7 @@ static int find_btf_percpu_datasec(struct btf *btf)
 	 * types to look at only module's own BTF types.
 	 */
 	n = btf_nr_types(btf);
-	if (btf_is_module(btf))
-		i = btf_nr_types(btf_vmlinux);
-	else
-		i = 1;
-
-	for(; i < n; i++) {
+	for (i = btf_sorted_start_id(btf); i < n; i++) {
 		t = btf_type_by_id(btf, i);
 		if (BTF_INFO_KIND(t->info) != BTF_KIND_DATASEC)
 			continue;
-- 
2.34.1
Re: [PATCH bpf-next v10 08/13] bpf: Skip anonymous types in type lookup for performance
Posted by Eduard Zingerman 13 hours ago 
On Thu, 2025-12-18 at 19:30 +0800, Donglin Peng wrote:
> From: pengdonglin <pengdonglin@xiaomi.com>
> 
> Currently, vmlinux and kernel module BTFs are unconditionally
> sorted during the build phase, with named types placed at the
> end. Thus, anonymous types should be skipped when starting the
> search. In my vmlinux BTF, the number of anonymous types is
> 61,747, which means the loop count can be reduced by 61,747.
> 
> Cc: Eduard Zingerman <eddyz87@gmail.com>
> Cc: Alexei Starovoitov <ast@kernel.org>
> Cc: Andrii Nakryiko <andrii.nakryiko@gmail.com>
> Cc: Alan Maguire <alan.maguire@oracle.com>
> Cc: Ihor Solodrai <ihor.solodrai@linux.dev>
> Cc: Xiaoqin Zhang <zhangxiaoqin@xiaomi.com>
> Signed-off-by: pengdonglin <pengdonglin@xiaomi.com>
> ---

Acked-by: Eduard Zingerman <eddyz87@gmail.com>

[...]
Re: [PATCH bpf-next v10 08/13] bpf: Skip anonymous types in type lookup for performance
Posted by Eduard Zingerman 13 hours ago 
On Thu, 2025-12-18 at 19:30 +0800, Donglin Peng wrote:
> From: pengdonglin <pengdonglin@xiaomi.com>
> 
> Currently, vmlinux and kernel module BTFs are unconditionally
> sorted during the build phase, with named types placed at the
> end. Thus, anonymous types should be skipped when starting the
> search. In my vmlinux BTF, the number of anonymous types is
> 61,747, which means the loop count can be reduced by 61,747.
> 
> Cc: Eduard Zingerman <eddyz87@gmail.com>
> Cc: Alexei Starovoitov <ast@kernel.org>
> Cc: Andrii Nakryiko <andrii.nakryiko@gmail.com>
> Cc: Alan Maguire <alan.maguire@oracle.com>
> Cc: Ihor Solodrai <ihor.solodrai@linux.dev>
> Cc: Xiaoqin Zhang <zhangxiaoqin@xiaomi.com>
> Signed-off-by: pengdonglin <pengdonglin@xiaomi.com>
> ---

Acked-by: Eduard Zingerman <eddyz87@gmail.com>

>  include/linux/btf.h   |  1 +
>  kernel/bpf/btf.c      | 24 ++++++++++++++++++++----
>  kernel/bpf/verifier.c |  7 +------
>  3 files changed, 22 insertions(+), 10 deletions(-)
> 
> diff --git a/include/linux/btf.h b/include/linux/btf.h
> index f06976ffb63f..2d28f2b22ae5 100644
> --- a/include/linux/btf.h
> +++ b/include/linux/btf.h
> @@ -220,6 +220,7 @@ bool btf_is_module(const struct btf *btf);
>  bool btf_is_vmlinux(const struct btf *btf);
>  struct module *btf_try_get_module(const struct btf *btf);
>  u32 btf_nr_types(const struct btf *btf);
> +u32 btf_sorted_start_id(const struct btf *btf);
>  struct btf *btf_base_btf(const struct btf *btf);
>  bool btf_type_is_i32(const struct btf_type *t);
>  bool btf_type_is_i64(const struct btf_type *t);
> diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c
> index a9e2345558c0..3aeb4f00cbfe 100644
> --- a/kernel/bpf/btf.c
> +++ b/kernel/bpf/btf.c
> @@ -550,6 +550,11 @@ u32 btf_nr_types(const struct btf *btf)
>  	return total;
>  }
>  
> +u32 btf_sorted_start_id(const struct btf *btf)

Nit: the name is a bit confusing, given that it not always returns the
     start id for sorted part. btf_maybe_first_named_id?
     Can't figure out a good name :(

> +{
> +	return btf->sorted_start_id ?: (btf->start_id ?: 1);
> +}
> +
>  /*
>   * Assuming that types are sorted by name in ascending order.
>   */

[...]
Re: [PATCH bpf-next v10 08/13] bpf: Skip anonymous types in type lookup for performance
Posted by Andrii Nakryiko 11 hours ago 
On Thu, Dec 18, 2025 at 2:21 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Thu, 2025-12-18 at 19:30 +0800, Donglin Peng wrote:
> > From: pengdonglin <pengdonglin@xiaomi.com>
> >
> > Currently, vmlinux and kernel module BTFs are unconditionally
> > sorted during the build phase, with named types placed at the
> > end. Thus, anonymous types should be skipped when starting the
> > search. In my vmlinux BTF, the number of anonymous types is
> > 61,747, which means the loop count can be reduced by 61,747.
> >
> > Cc: Eduard Zingerman <eddyz87@gmail.com>
> > Cc: Alexei Starovoitov <ast@kernel.org>
> > Cc: Andrii Nakryiko <andrii.nakryiko@gmail.com>
> > Cc: Alan Maguire <alan.maguire@oracle.com>
> > Cc: Ihor Solodrai <ihor.solodrai@linux.dev>
> > Cc: Xiaoqin Zhang <zhangxiaoqin@xiaomi.com>
> > Signed-off-by: pengdonglin <pengdonglin@xiaomi.com>
> > ---
>
> Acked-by: Eduard Zingerman <eddyz87@gmail.com>
>
> >  include/linux/btf.h   |  1 +
> >  kernel/bpf/btf.c      | 24 ++++++++++++++++++++----
> >  kernel/bpf/verifier.c |  7 +------
> >  3 files changed, 22 insertions(+), 10 deletions(-)
> >
> > diff --git a/include/linux/btf.h b/include/linux/btf.h
> > index f06976ffb63f..2d28f2b22ae5 100644
> > --- a/include/linux/btf.h
> > +++ b/include/linux/btf.h
> > @@ -220,6 +220,7 @@ bool btf_is_module(const struct btf *btf);
> >  bool btf_is_vmlinux(const struct btf *btf);
> >  struct module *btf_try_get_module(const struct btf *btf);
> >  u32 btf_nr_types(const struct btf *btf);
> > +u32 btf_sorted_start_id(const struct btf *btf);
> >  struct btf *btf_base_btf(const struct btf *btf);
> >  bool btf_type_is_i32(const struct btf_type *t);
> >  bool btf_type_is_i64(const struct btf_type *t);
> > diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c
> > index a9e2345558c0..3aeb4f00cbfe 100644
> > --- a/kernel/bpf/btf.c
> > +++ b/kernel/bpf/btf.c
> > @@ -550,6 +550,11 @@ u32 btf_nr_types(const struct btf *btf)
> >       return total;
> >  }
> >
> > +u32 btf_sorted_start_id(const struct btf *btf)
>
> Nit: the name is a bit confusing, given that it not always returns the
>      start id for sorted part. btf_maybe_first_named_id?
>      Can't figure out a good name :(

yeah, I agree, it is quite confusing overall. I think we should at
least add comments why we start with something different than 1 in
those few places where we use this optimization...

let's name it btf_named_start_id() and specify in the comment that for
non-sorted BTFs we conservatively fallback to the first type.

btw, maybe it would be good to have two versions of this (or bool
flag,but we all hate bool flags) to either return own start id (i.e.,
ignoring base BTF) or recursively go down to the base BTF.

Having that

while (base_btf->base_btf)
    base_btf = base_btf->base_btf;

logic in a few places looks a bit too low-level and distracting, IMO.

>
> > +{
> > +     return btf->sorted_start_id ?: (btf->start_id ?: 1);
> > +}
> > +
> >  /*
> >   * Assuming that types are sorted by name in ascending order.
> >   */
>
> [...]
Re: [PATCH bpf-next v10 08/13] bpf: Skip anonymous types in type lookup for performance
Posted by Donglin Peng 6 hours ago 
On Fri, Dec 19, 2025 at 7:59 AM Andrii Nakryiko
<andrii.nakryiko@gmail.com> wrote:
>
> On Thu, Dec 18, 2025 at 2:21 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
> >
> > On Thu, 2025-12-18 at 19:30 +0800, Donglin Peng wrote:
> > > From: pengdonglin <pengdonglin@xiaomi.com>
> > >
> > > Currently, vmlinux and kernel module BTFs are unconditionally
> > > sorted during the build phase, with named types placed at the
> > > end. Thus, anonymous types should be skipped when starting the
> > > search. In my vmlinux BTF, the number of anonymous types is
> > > 61,747, which means the loop count can be reduced by 61,747.
> > >
> > > Cc: Eduard Zingerman <eddyz87@gmail.com>
> > > Cc: Alexei Starovoitov <ast@kernel.org>
> > > Cc: Andrii Nakryiko <andrii.nakryiko@gmail.com>
> > > Cc: Alan Maguire <alan.maguire@oracle.com>
> > > Cc: Ihor Solodrai <ihor.solodrai@linux.dev>
> > > Cc: Xiaoqin Zhang <zhangxiaoqin@xiaomi.com>
> > > Signed-off-by: pengdonglin <pengdonglin@xiaomi.com>
> > > ---
> >
> > Acked-by: Eduard Zingerman <eddyz87@gmail.com>
> >
> > >  include/linux/btf.h   |  1 +
> > >  kernel/bpf/btf.c      | 24 ++++++++++++++++++++----
> > >  kernel/bpf/verifier.c |  7 +------
> > >  3 files changed, 22 insertions(+), 10 deletions(-)
> > >
> > > diff --git a/include/linux/btf.h b/include/linux/btf.h
> > > index f06976ffb63f..2d28f2b22ae5 100644
> > > --- a/include/linux/btf.h
> > > +++ b/include/linux/btf.h
> > > @@ -220,6 +220,7 @@ bool btf_is_module(const struct btf *btf);
> > >  bool btf_is_vmlinux(const struct btf *btf);
> > >  struct module *btf_try_get_module(const struct btf *btf);
> > >  u32 btf_nr_types(const struct btf *btf);
> > > +u32 btf_sorted_start_id(const struct btf *btf);
> > >  struct btf *btf_base_btf(const struct btf *btf);
> > >  bool btf_type_is_i32(const struct btf_type *t);
> > >  bool btf_type_is_i64(const struct btf_type *t);
> > > diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c
> > > index a9e2345558c0..3aeb4f00cbfe 100644
> > > --- a/kernel/bpf/btf.c
> > > +++ b/kernel/bpf/btf.c
> > > @@ -550,6 +550,11 @@ u32 btf_nr_types(const struct btf *btf)
> > >       return total;
> > >  }
> > >
> > > +u32 btf_sorted_start_id(const struct btf *btf)
> >
> > Nit: the name is a bit confusing, given that it not always returns the
> >      start id for sorted part. btf_maybe_first_named_id?
> >      Can't figure out a good name :(
>
> yeah, I agree, it is quite confusing overall. I think we should at
> least add comments why we start with something different than 1 in
> those few places where we use this optimization...

Thanks, I will add comments to make it more clear.

>
> let's name it btf_named_start_id() and specify in the comment that for
> non-sorted BTFs we conservatively fallback to the first type.

Thanks, I will do it.

>
> btw, maybe it would be good to have two versions of this (or bool
> flag,but we all hate bool flags) to either return own start id (i.e.,
> ignoring base BTF) or recursively go down to the base BTF.

Thanks, I will implement it.

>
> Having that
>
> while (base_btf->base_btf)
>     base_btf = base_btf->base_btf;
>
> logic in a few places looks a bit too low-level and distracting, IMO.

Agreed.

>
> >
> > > +{
> > > +     return btf->sorted_start_id ?: (btf->start_id ?: 1);
> > > +}
> > > +
> > >  /*
> > >   * Assuming that types are sorted by name in ascending order.
> > >   */
> >
> > [...]

Patchew 2.1-devel-b67e4c2

© 2016 - 2025 Red Hat, Inc.