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.

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>
---
 tools/lib/bpf/btf.c | 41 +++++++++++++++++++++++++++++++++++++++++
 1 file changed, 41 insertions(+)

diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c
index 2facb57d7e5f..c63d46b7d74b 100644
--- a/tools/lib/bpf/btf.c
+++ b/tools/lib/bpf/btf.c
@@ -899,6 +899,46 @@ int btf__resolve_type(const struct btf *btf, __u32 type_id)
 	return type_id;
 }
 
+/*
+ * Assuming that types are sorted by name in ascending order.
+ */
+static int btf_compare_type_names(__u32 *a, __u32 *b, const struct btf *btf)
+{
+	struct btf_type *ta = btf_type_by_id(btf, *a);
+	struct btf_type *tb = btf_type_by_id(btf, *b);
+	const char *na, *nb;
+
+	na = btf__str_by_offset(btf, ta->name_off);
+	nb = btf__str_by_offset(btf, tb->name_off);
+	return strcmp(na, nb);
+}
+
+static void btf_check_sorted(struct btf *btf)
+{
+	const struct btf_type *t;
+	__u32 i, k, n;
+	__u32 sorted_start_id;
+
+	if (btf->nr_types < 2)
+		return;
+
+	sorted_start_id = 0;
+	n = btf__type_cnt(btf);
+	for (i = btf->start_id; 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)
 {
@@ -1147,6 +1187,7 @@ static struct btf *btf_new(const void *data, __u32 size, struct btf *base_btf, b
 	err = err ?: btf_sanity_check(btf);
 	if (err)
 		goto done;
+	btf_check_sorted(btf);
 
 done:
 	if (err) {
-- 
2.34.1

On Thu, Dec 18, 2025 at 3:31 AM Donglin Peng <dolinux.peng@gmail.com> wrote:
>
> From: pengdonglin <pengdonglin@xiaomi.com>
>

typo in subject: "Sorting" -> "sorting", it looks weird capitalized like that

> This patch checks whether the BTF is sorted by name in ascending
> order. If sorted, binary search will be used when looking up 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>
> ---
>  tools/lib/bpf/btf.c | 41 +++++++++++++++++++++++++++++++++++++++++
>  1 file changed, 41 insertions(+)
>
> diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c
> index 2facb57d7e5f..c63d46b7d74b 100644
> --- a/tools/lib/bpf/btf.c
> +++ b/tools/lib/bpf/btf.c
> @@ -899,6 +899,46 @@ int btf__resolve_type(const struct btf *btf, __u32 type_id)
>         return type_id;
>  }
>
> +/*
> + * Assuming that types are sorted by name in ascending order.
> + */

Unnecessary comment, and no, btf_compare_type_names() itself makes no
such assumption, it just compares two provided types by name. Drop the
comment, please.

> +static int btf_compare_type_names(__u32 *a, __u32 *b, const struct btf *btf)
> +{
> +       struct btf_type *ta = btf_type_by_id(btf, *a);
> +       struct btf_type *tb = btf_type_by_id(btf, *b);
> +       const char *na, *nb;
> +
> +       na = btf__str_by_offset(btf, ta->name_off);
> +       nb = btf__str_by_offset(btf, tb->name_off);
> +       return strcmp(na, nb);
> +}

you use this function only in one place, there is no real point having
it, especially that it uses **a pointer to type ID** as an
interface... just inline its logic in that one loop below

> +
> +static void btf_check_sorted(struct btf *btf)
> +{
> +       const struct btf_type *t;
> +       __u32 i, k, n;
> +       __u32 sorted_start_id;
> +
> +       if (btf->nr_types < 2)
> +               return;

why special casing? does it not work with nr_types = 0 or nr_types = 1?

> +
> +       sorted_start_id = 0;

nit: initialize in declaration


> +       n = btf__type_cnt(btf);
> +       for (i = btf->start_id; 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)

I'd check actual string, not name_off. Technically, you can have empty
string with non-zero name_off, so why assume anything here?

> +                               sorted_start_id = i;
> +               }
> +       }
> +
> +       if (sorted_start_id)
> +               btf->sorted_start_id = sorted_start_id;

You actually made code more complicated by extracting that
btf_compare_type_names(). Compare to:

n = btf__type_cnt(btf);
btf->sorted_start_id = 0;
for (i = btf->start_id + 1; i < n; i++) {
   struct btf_type *t1 = btf_type_by_id(btf, i - 1);
   struct btf_type *t2 = btf_type_by_id(btf, i);
   const char *n1 = btf__str_by_offset(btf, t1->name_off);
   const char *n2 = btf__str_by_offset(btf, t2->name_off);

   if (strcmp(n1, n2) > 0)
        return;
   if (btf->sorted_start_id == 0 && n1[0] != '\0')
        btf->sorted_start_id = i - 1;
}


No extra k<n checks, no extra type_by_id lookups. It's minimalistic
and cleaner. And if it so happens that we get single type BTF that is
technically sorted, it doesn't matter, we always fallback to faster
linear search anyways.

Keep it simple.

> +}
> +
>  static __s32 btf_find_by_name_bsearch(const struct btf *btf, const char *name,
>                                                 __s32 start_id, __s32 end_id)
>  {
> @@ -1147,6 +1187,7 @@ static struct btf *btf_new(const void *data, __u32 size, struct btf *base_btf, b
>         err = err ?: btf_sanity_check(btf);
>         if (err)
>                 goto done;
> +       btf_check_sorted(btf);
>
>  done:
>         if (err) {
> --
> 2.34.1
>

On Fri, Dec 19, 2025 at 7:44 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>
> >
>
> typo in subject: "Sorting" -> "sorting", it looks weird capitalized like that

Thanks, I will do it.

>
> > This patch checks whether the BTF is sorted by name in ascending
> > order. If sorted, binary search will be used when looking up 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>
> > ---
> >  tools/lib/bpf/btf.c | 41 +++++++++++++++++++++++++++++++++++++++++
> >  1 file changed, 41 insertions(+)
> >
> > diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c
> > index 2facb57d7e5f..c63d46b7d74b 100644
> > --- a/tools/lib/bpf/btf.c
> > +++ b/tools/lib/bpf/btf.c
> > @@ -899,6 +899,46 @@ int btf__resolve_type(const struct btf *btf, __u32 type_id)
> >         return type_id;
> >  }
> >
> > +/*
> > + * Assuming that types are sorted by name in ascending order.
> > + */
>
> Unnecessary comment, and no, btf_compare_type_names() itself makes no
> such assumption, it just compares two provided types by name. Drop the
> comment, please.
>
> > +static int btf_compare_type_names(__u32 *a, __u32 *b, const struct btf *btf)
> > +{
> > +       struct btf_type *ta = btf_type_by_id(btf, *a);
> > +       struct btf_type *tb = btf_type_by_id(btf, *b);
> > +       const char *na, *nb;
> > +
> > +       na = btf__str_by_offset(btf, ta->name_off);
> > +       nb = btf__str_by_offset(btf, tb->name_off);
> > +       return strcmp(na, nb);
> > +}
>
> you use this function only in one place, there is no real point having
> it, especially that it uses **a pointer to type ID** as an
> interface... just inline its logic in that one loop below
>
> > +
> > +static void btf_check_sorted(struct btf *btf)
> > +{
> > +       const struct btf_type *t;
> > +       __u32 i, k, n;
> > +       __u32 sorted_start_id;
> > +
> > +       if (btf->nr_types < 2)
> > +               return;
>
> why special casing? does it not work with nr_types = 0 or nr_types = 1?

No. I just think it doesn't make any sense to check the sorting
of BTF with zero or only one type.

>
> > +
> > +       sorted_start_id = 0;
>
> nit: initialize in declaration

Thanks, I will do it.

>
>
> > +       n = btf__type_cnt(btf);
> > +       for (i = btf->start_id; 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)
>
> I'd check actual string, not name_off. Technically, you can have empty
> string with non-zero name_off, so why assume anything here?

Thanks, I will do it.

>
> > +                               sorted_start_id = i;
> > +               }
> > +       }
> > +
> > +       if (sorted_start_id)
> > +               btf->sorted_start_id = sorted_start_id;
>
> You actually made code more complicated by extracting that
> btf_compare_type_names(). Compare to:
>
> n = btf__type_cnt(btf);
> btf->sorted_start_id = 0;
> for (i = btf->start_id + 1; i < n; i++) {
>    struct btf_type *t1 = btf_type_by_id(btf, i - 1);
>    struct btf_type *t2 = btf_type_by_id(btf, i);
>    const char *n1 = btf__str_by_offset(btf, t1->name_off);
>    const char *n2 = btf__str_by_offset(btf, t2->name_off);
>
>    if (strcmp(n1, n2) > 0)
>         return;
>    if (btf->sorted_start_id == 0 && n1[0] != '\0')
>         btf->sorted_start_id = i - 1;
> }

Thanks. I believe we shouldn't directly assign a value to
`btf->sorted_start_id` within the for loop, because
`btf->sorted_start_id` might be non-zero even when the
BTF isn't sorted.

>
>
> No extra k<n checks, no extra type_by_id lookups. It's minimalistic
> and cleaner. And if it so happens that we get single type BTF that is
> technically sorted, it doesn't matter, we always fallback to faster
> linear search anyways.
>
> Keep it simple.

Thank you. I will adopt this method in the next version.

>
> > +}
> > +
> >  static __s32 btf_find_by_name_bsearch(const struct btf *btf, const char *name,
> >                                                 __s32 start_id, __s32 end_id)
> >  {
> > @@ -1147,6 +1187,7 @@ static struct btf *btf_new(const void *data, __u32 size, struct btf *base_btf, b
> >         err = err ?: btf_sanity_check(btf);
> >         if (err)
> >                 goto done;
> > +       btf_check_sorted(btf);
> >
> >  done:
> >         if (err) {
> > --
> > 2.34.1
> >

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.
> 
> 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>
> ---

(But could you please fix the btf_compare_type_names() prototype?)

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

>  tools/lib/bpf/btf.c | 41 +++++++++++++++++++++++++++++++++++++++++
>  1 file changed, 41 insertions(+)
> 
> diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c
> index 2facb57d7e5f..c63d46b7d74b 100644
> --- a/tools/lib/bpf/btf.c
> +++ b/tools/lib/bpf/btf.c
> @@ -899,6 +899,46 @@ int btf__resolve_type(const struct btf *btf, __u32 type_id)
>  	return type_id;
>  }
>  
> +/*
> + * 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: still no need for 'a' and 'b' to be pointers.

> +{
> +	struct btf_type *ta = btf_type_by_id(btf, *a);
> +	struct btf_type *tb = btf_type_by_id(btf, *b);
> +	const char *na, *nb;
> +
> +	na = btf__str_by_offset(btf, ta->name_off);
> +	nb = btf__str_by_offset(btf, tb->name_off);
> +	return strcmp(na, nb);
> +}

[...]