From: Donglin Peng <pengdonglin@xiaomi.com>
This patch checks whether the BTF is sorted by name in ascending order.
If sorted, binary search will be used when looking up types.
Specifically, vmlinux and kernel module BTFs are always sorted during
the build phase with anonymous types placed before named types, so we
only need to identify the starting ID of named types.
Cc: Eduard Zingerman <eddyz87@gmail.com>
Cc: Alexei Starovoitov <ast@kernel.org>
Cc: Andrii Nakryiko <andrii.nakryiko@gmail.com>
Cc: Alan Maguire <alan.maguire@oracle.com>
Cc: Ihor Solodrai <ihor.solodrai@linux.dev>
Cc: Xiaoqin Zhang <zhangxiaoqin@xiaomi.com>
Signed-off-by: Donglin Peng <pengdonglin@xiaomi.com>
---
kernel/bpf/btf.c | 42 ++++++++++++++++++++++++++++++++++++++++++
1 file changed, 42 insertions(+)
diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c
index d1f4b984100d..12eecf59d71f 100644
--- a/kernel/bpf/btf.c
+++ b/kernel/bpf/btf.c
@@ -550,6 +550,46 @@ u32 btf_nr_types(const struct btf *btf)
return total;
}
+/* Note that vmlinux and kernel module BTFs are always sorted
+ * during the building phase.
+ */
+static void btf_check_sorted(struct btf *btf)
+{
+ u32 i, n, named_start_id = 0;
+
+ n = btf_nr_types(btf);
+ if (btf_is_vmlinux(btf)) {
+ for (i = btf_start_id(btf); i < n; i++) {
+ const struct btf_type *t = btf_type_by_id(btf, i);
+ const char *n = btf_name_by_offset(btf, t->name_off);
+
+ if (n[0] != '\0') {
+ btf->named_start_id = i;
+ return;
+ }
+ }
+ return;
+ }
+
+ for (i = btf_start_id(btf) + 1; i < n; i++) {
+ const struct btf_type *ta = btf_type_by_id(btf, i - 1);
+ const struct btf_type *tb = btf_type_by_id(btf, i);
+ const char *na = btf_name_by_offset(btf, ta->name_off);
+ const char *nb = btf_name_by_offset(btf, tb->name_off);
+
+ if (strcmp(na, nb) > 0)
+ return;
+
+ if (named_start_id == 0 && na[0] != '\0')
+ named_start_id = i - 1;
+ if (named_start_id == 0 && nb[0] != '\0')
+ named_start_id = i;
+ }
+
+ if (named_start_id)
+ btf->named_start_id = named_start_id;
+}
+
/* 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,
@@ -6302,6 +6342,7 @@ static struct btf *btf_parse_base(struct btf_verifier_env *env, const char *name
if (err)
goto errout;
+ btf_check_sorted(btf);
refcount_set(&btf->refcnt, 1);
return btf;
@@ -6436,6 +6477,7 @@ static struct btf *btf_parse_module(const char *module_name, const void *data,
}
btf_verifier_env_free(env);
+ btf_check_sorted(btf);
refcount_set(&btf->refcnt, 1);
return btf;
--
2.34.1On Fri, Jan 9, 2026 at 5:00 AM Donglin Peng <dolinux.peng@gmail.com> wrote:
>
> From: Donglin Peng <pengdonglin@xiaomi.com>
>
> This patch checks whether the BTF is sorted by name in ascending order.
> If sorted, binary search will be used when looking up types.
>
> Specifically, vmlinux and kernel module BTFs are always sorted during
> the build phase with anonymous types placed before named types, so we
> only need to identify the starting ID of named types.
>
> Cc: Eduard Zingerman <eddyz87@gmail.com>
> Cc: Alexei Starovoitov <ast@kernel.org>
> Cc: Andrii Nakryiko <andrii.nakryiko@gmail.com>
> Cc: Alan Maguire <alan.maguire@oracle.com>
> Cc: Ihor Solodrai <ihor.solodrai@linux.dev>
> Cc: Xiaoqin Zhang <zhangxiaoqin@xiaomi.com>
> Signed-off-by: Donglin Peng <pengdonglin@xiaomi.com>
> ---
> kernel/bpf/btf.c | 42 ++++++++++++++++++++++++++++++++++++++++++
> 1 file changed, 42 insertions(+)
>
> diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c
> index d1f4b984100d..12eecf59d71f 100644
> --- a/kernel/bpf/btf.c
> +++ b/kernel/bpf/btf.c
> @@ -550,6 +550,46 @@ u32 btf_nr_types(const struct btf *btf)
> return total;
> }
>
> +/* Note that vmlinux and kernel module BTFs are always sorted
wrong comment style, I'll fix it up when applying, but keep this in
mind for the future
> + * during the building phase.
> + */
> +static void btf_check_sorted(struct btf *btf)
> +{
> + u32 i, n, named_start_id = 0;
> +
> + n = btf_nr_types(btf);
> + if (btf_is_vmlinux(btf)) {
> + for (i = btf_start_id(btf); i < n; i++) {
> + const struct btf_type *t = btf_type_by_id(btf, i);
> + const char *n = btf_name_by_offset(btf, t->name_off);
> +
> + if (n[0] != '\0') {
> + btf->named_start_id = i;
> + return;
> + }
> + }
> + return;
> + }
> +
> + for (i = btf_start_id(btf) + 1; i < n; i++) {
> + const struct btf_type *ta = btf_type_by_id(btf, i - 1);
> + const struct btf_type *tb = btf_type_by_id(btf, i);
> + const char *na = btf_name_by_offset(btf, ta->name_off);
> + const char *nb = btf_name_by_offset(btf, tb->name_off);
> +
> + if (strcmp(na, nb) > 0)
> + return;
> +
> + if (named_start_id == 0 && na[0] != '\0')
> + named_start_id = i - 1;
> + if (named_start_id == 0 && nb[0] != '\0')
> + named_start_id = i;
> + }
> +
> + if (named_start_id)
> + btf->named_start_id = named_start_id;
> +}
> +
> /* 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,
> @@ -6302,6 +6342,7 @@ static struct btf *btf_parse_base(struct btf_verifier_env *env, const char *name
> if (err)
> goto errout;
>
> + btf_check_sorted(btf);
> refcount_set(&btf->refcnt, 1);
>
> return btf;
> @@ -6436,6 +6477,7 @@ static struct btf *btf_parse_module(const char *module_name, const void *data,
> }
>
> btf_verifier_env_free(env);
> + btf_check_sorted(btf);
> refcount_set(&btf->refcnt, 1);
> return btf;
>
> --
> 2.34.1
>
On Wed, Jan 14, 2026 at 8:30 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>
> >
> > This patch checks whether the BTF is sorted by name in ascending order.
> > If sorted, binary search will be used when looking up types.
> >
> > Specifically, vmlinux and kernel module BTFs are always sorted during
> > the build phase with anonymous types placed before named types, so we
> > only need to identify the starting ID of named types.
> >
> > Cc: Eduard Zingerman <eddyz87@gmail.com>
> > Cc: Alexei Starovoitov <ast@kernel.org>
> > Cc: Andrii Nakryiko <andrii.nakryiko@gmail.com>
> > Cc: Alan Maguire <alan.maguire@oracle.com>
> > Cc: Ihor Solodrai <ihor.solodrai@linux.dev>
> > Cc: Xiaoqin Zhang <zhangxiaoqin@xiaomi.com>
> > Signed-off-by: Donglin Peng <pengdonglin@xiaomi.com>
> > ---
> > kernel/bpf/btf.c | 42 ++++++++++++++++++++++++++++++++++++++++++
> > 1 file changed, 42 insertions(+)
> >
> > diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c
> > index d1f4b984100d..12eecf59d71f 100644
> > --- a/kernel/bpf/btf.c
> > +++ b/kernel/bpf/btf.c
> > @@ -550,6 +550,46 @@ u32 btf_nr_types(const struct btf *btf)
> > return total;
> > }
> >
> > +/* Note that vmlinux and kernel module BTFs are always sorted
>
> wrong comment style, I'll fix it up when applying, but keep this in
> mind for the future
Thanks, I understood.
>
>
> > + * during the building phase.
> > + */
> > +static void btf_check_sorted(struct btf *btf)
> > +{
> > + u32 i, n, named_start_id = 0;
> > +
> > + n = btf_nr_types(btf);
> > + if (btf_is_vmlinux(btf)) {
> > + for (i = btf_start_id(btf); i < n; i++) {
> > + const struct btf_type *t = btf_type_by_id(btf, i);
> > + const char *n = btf_name_by_offset(btf, t->name_off);
> > +
> > + if (n[0] != '\0') {
> > + btf->named_start_id = i;
> > + return;
> > + }
> > + }
> > + return;
> > + }
> > +
> > + for (i = btf_start_id(btf) + 1; i < n; i++) {
> > + const struct btf_type *ta = btf_type_by_id(btf, i - 1);
> > + const struct btf_type *tb = btf_type_by_id(btf, i);
> > + const char *na = btf_name_by_offset(btf, ta->name_off);
> > + const char *nb = btf_name_by_offset(btf, tb->name_off);
> > +
> > + if (strcmp(na, nb) > 0)
> > + return;
> > +
> > + if (named_start_id == 0 && na[0] != '\0')
> > + named_start_id = i - 1;
> > + if (named_start_id == 0 && nb[0] != '\0')
> > + named_start_id = i;
> > + }
> > +
> > + if (named_start_id)
> > + btf->named_start_id = named_start_id;
> > +}
> > +
> > /* 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,
> > @@ -6302,6 +6342,7 @@ static struct btf *btf_parse_base(struct btf_verifier_env *env, const char *name
> > if (err)
> > goto errout;
> >
> > + btf_check_sorted(btf);
> > refcount_set(&btf->refcnt, 1);
> >
> > return btf;
> > @@ -6436,6 +6477,7 @@ static struct btf *btf_parse_module(const char *module_name, const void *data,
> > }
> >
> > btf_verifier_env_free(env);
> > + btf_check_sorted(btf);
> > refcount_set(&btf->refcnt, 1);
> > return btf;
> >
> > --
> > 2.34.1
> >
© 2016 - 2026 Red Hat, Inc.