From: pengdonglin <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: pengdonglin <pengdonglin@xiaomi.com>
---
 kernel/bpf/btf.c | 56 ++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 56 insertions(+)

diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c
index 0394f0c8ef74..a9e2345558c0 100644
--- a/kernel/bpf/btf.c
+++ b/kernel/bpf/btf.c
@@ -550,6 +550,60 @@ u32 btf_nr_types(const struct btf *btf)
 	return total;
 }
 
+/*
+ * Assuming that types are sorted by name in ascending order.
+ */
+static int btf_compare_type_names(u32 *a, u32 *b, const struct btf *btf)
+{
+	const struct btf_type *ta = btf_type_by_id(btf, *a);
+	const struct btf_type *tb = btf_type_by_id(btf, *b);
+	const char *na, *nb;
+
+	na = btf_name_by_offset(btf, ta->name_off);
+	nb = btf_name_by_offset(btf, tb->name_off);
+	return strcmp(na, nb);
+}
+
+/* Note that vmlinux and kernel module BTFs are always sorted
+ * during the building phase.
+ */
+static void btf_check_sorted(struct btf *btf)
+{
+	const struct btf_type *t;
+	u32 sorted_start_id;
+	u32 i, n, k;
+
+	if (btf_is_kernel(btf) && !btf_is_module(btf)) {
+		for (i = btf_start_id(btf); i < n; i++) {
+			t = btf_type_by_id(btf, i);
+			if (t->name_off) {
+				btf->sorted_start_id = i;
+				return;
+			}
+		}
+	}
+
+	if (btf->nr_types < 2)
+		return;
+
+	sorted_start_id = 0;
+	n = btf_nr_types(btf);
+	for (i = btf_start_id(btf); i < n; i++) {
+		k = i + 1;
+		if (k < n && btf_compare_type_names(&i, &k, btf) > 0)
+			return;
+
+		if (sorted_start_id == 0) {
+			t = btf_type_by_id(btf, i);
+			if (t->name_off)
+				sorted_start_id = i;
+		}
+	}
+
+	if (sorted_start_id)
+		btf->sorted_start_id = sorted_start_id;
+}
+
 static s32 btf_find_by_name_bsearch(const struct btf *btf, const char *name,
 				    s32 start_id, s32 end_id)
 {
@@ -6296,6 +6350,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;
@@ -6430,6 +6485,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 Thu, Dec 18, 2025 at 3:31 AM Donglin Peng <dolinux.peng@gmail.com> wrote:
>
> From: pengdonglin <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: pengdonglin <pengdonglin@xiaomi.com>
> ---
>  kernel/bpf/btf.c | 56 ++++++++++++++++++++++++++++++++++++++++++++++++
>  1 file changed, 56 insertions(+)
>

please make sure to apply feedback received for libbpf-side
implementation for kernel-side implementations as well

> diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c
> index 0394f0c8ef74..a9e2345558c0 100644
> --- a/kernel/bpf/btf.c
> +++ b/kernel/bpf/btf.c
> @@ -550,6 +550,60 @@ u32 btf_nr_types(const struct btf *btf)
>         return total;
>  }
>

[...]

On Fri, Dec 19, 2025 at 7:46 AM Andrii Nakryiko
<andrii.nakryiko@gmail.com> wrote:
>
> On Thu, Dec 18, 2025 at 3:31 AM Donglin Peng <dolinux.peng@gmail.com> wrote:
> >
> > From: pengdonglin <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: pengdonglin <pengdonglin@xiaomi.com>
> > ---
> >  kernel/bpf/btf.c | 56 ++++++++++++++++++++++++++++++++++++++++++++++++
> >  1 file changed, 56 insertions(+)
> >
>
> please make sure to apply feedback received for libbpf-side
> implementation for kernel-side implementations as well

Thanks, I will do it.

>
> > diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c
> > index 0394f0c8ef74..a9e2345558c0 100644
> > --- a/kernel/bpf/btf.c
> > +++ b/kernel/bpf/btf.c
> > @@ -550,6 +550,60 @@ u32 btf_nr_types(const struct btf *btf)
> >         return total;
> >  }
> >
>
> [...]

On Thu, 2025-12-18 at 19:30 +0800, Donglin Peng wrote:
> From: pengdonglin <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: pengdonglin <pengdonglin@xiaomi.com>
> ---

Lgtm, but please take a look at a few nits.

>  kernel/bpf/btf.c | 56 ++++++++++++++++++++++++++++++++++++++++++++++++
>  1 file changed, 56 insertions(+)
> 
> diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c
> index 0394f0c8ef74..a9e2345558c0 100644
> --- a/kernel/bpf/btf.c
> +++ b/kernel/bpf/btf.c
> @@ -550,6 +550,60 @@ u32 btf_nr_types(const struct btf *btf)
>  	return total;
>  }
>  
> +/*
> + * Assuming that types are sorted by name in ascending order.
> + */
> +static int btf_compare_type_names(u32 *a, u32 *b, const struct btf *btf)

Nit: no need for 'a' and 'b' to be pointers.

> +{
> +	const struct btf_type *ta = btf_type_by_id(btf, *a);
> +	const struct btf_type *tb = btf_type_by_id(btf, *b);
> +	const char *na, *nb;
> +
> +	na = btf_name_by_offset(btf, ta->name_off);
> +	nb = btf_name_by_offset(btf, tb->name_off);
> +	return strcmp(na, nb);
> +}
> +
> +/* Note that vmlinux and kernel module BTFs are always sorted
> + * during the building phase.
> + */
> +static void btf_check_sorted(struct btf *btf)
> +{
> +	const struct btf_type *t;
> +	u32 sorted_start_id;
> +	u32 i, n, k;
> +
> +	if (btf_is_kernel(btf) && !btf_is_module(btf)) {
            ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Nit: there is a btf_is_vmlinux() helper, which does the same thing.

> +		for (i = btf_start_id(btf); i < n; i++) {
> +			t = btf_type_by_id(btf, i);
> +			if (t->name_off) {
> +				btf->sorted_start_id = i;
> +				return;
> +			}
> +		}

Nit: return here?

> +	}
> +
> +	if (btf->nr_types < 2)
> +		return;
> +
> +	sorted_start_id = 0;
> +	n = btf_nr_types(btf);
> +	for (i = btf_start_id(btf); i < n; i++) {
> +		k = i + 1;
> +		if (k < n && btf_compare_type_names(&i, &k, btf) > 0)
> +			return;
> +
> +		if (sorted_start_id == 0) {
> +			t = btf_type_by_id(btf, i);
> +			if (t->name_off)
> +				sorted_start_id = i;
> +		}
> +	}
> +
> +	if (sorted_start_id)
> +		btf->sorted_start_id = sorted_start_id;
> +}
> +
>  static s32 btf_find_by_name_bsearch(const struct btf *btf, const char *name,
>  				    s32 start_id, s32 end_id)
>  {
> @@ -6296,6 +6350,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;
> @@ -6430,6 +6485,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;
>  

On Fri, Dec 19, 2025 at 5:43 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Thu, 2025-12-18 at 19:30 +0800, Donglin Peng wrote:
> > From: pengdonglin <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: pengdonglin <pengdonglin@xiaomi.com>
> > ---
>
> Lgtm, but please take a look at a few nits.
>
> >  kernel/bpf/btf.c | 56 ++++++++++++++++++++++++++++++++++++++++++++++++
> >  1 file changed, 56 insertions(+)
> >
> > diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c
> > index 0394f0c8ef74..a9e2345558c0 100644
> > --- a/kernel/bpf/btf.c
> > +++ b/kernel/bpf/btf.c
> > @@ -550,6 +550,60 @@ u32 btf_nr_types(const struct btf *btf)
> >       return total;
> >  }
> >
> > +/*
> > + * Assuming that types are sorted by name in ascending order.
> > + */
> > +static int btf_compare_type_names(u32 *a, u32 *b, const struct btf *btf)
>
> Nit: no need for 'a' and 'b' to be pointers.

Thank you. I will remove this function in the next version, as
suggested by Adrill.

>
> > +{
> > +     const struct btf_type *ta = btf_type_by_id(btf, *a);
> > +     const struct btf_type *tb = btf_type_by_id(btf, *b);
> > +     const char *na, *nb;
> > +
> > +     na = btf_name_by_offset(btf, ta->name_off);
> > +     nb = btf_name_by_offset(btf, tb->name_off);
> > +     return strcmp(na, nb);
> > +}
> > +
> > +/* Note that vmlinux and kernel module BTFs are always sorted
> > + * during the building phase.
> > + */
> > +static void btf_check_sorted(struct btf *btf)
> > +{
> > +     const struct btf_type *t;
> > +     u32 sorted_start_id;
> > +     u32 i, n, k;
> > +
> > +     if (btf_is_kernel(btf) && !btf_is_module(btf)) {
>             ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
> Nit: there is a btf_is_vmlinux() helper, which does the same thing.

Good catch.

>
> > +             for (i = btf_start_id(btf); i < n; i++) {
> > +                     t = btf_type_by_id(btf, i);
> > +                     if (t->name_off) {
> > +                             btf->sorted_start_id = i;
> > +                             return;
> > +                     }
> > +             }
>
> Nit: return here?

Agreed.

>
> > +     }
> > +
> > +     if (btf->nr_types < 2)
> > +             return;
> > +
> > +     sorted_start_id = 0;
> > +     n = btf_nr_types(btf);
> > +     for (i = btf_start_id(btf); i < n; i++) {
> > +             k = i + 1;
> > +             if (k < n && btf_compare_type_names(&i, &k, btf) > 0)
> > +                     return;
> > +
> > +             if (sorted_start_id == 0) {
> > +                     t = btf_type_by_id(btf, i);
> > +                     if (t->name_off)
> > +                             sorted_start_id = i;
> > +             }
> > +     }
> > +
> > +     if (sorted_start_id)
> > +             btf->sorted_start_id = sorted_start_id;
> > +}
> > +
> >  static s32 btf_find_by_name_bsearch(const struct btf *btf, const char *name,
> >                                   s32 start_id, s32 end_id)
> >  {
> > @@ -6296,6 +6350,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;
> > @@ -6430,6 +6485,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;
> >