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 | 46 ++++++++++++++++++++++++++++++++++++++++++++-
1 file changed, 45 insertions(+), 1 deletion(-)
diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c
index 7f150c869bf6..a53d24704857 100644
--- a/tools/lib/bpf/btf.c
+++ b/tools/lib/bpf/btf.c
@@ -899,6 +899,49 @@ 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(const void *a, const void *b, void *priv)
+{
+ struct btf *btf = (struct btf *)priv;
+ struct btf_type *ta = btf_type_by_id(btf, *(__u32 *)a);
+ struct btf_type *tb = btf_type_by_id(btf, *(__u32 *)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;
+ int i, k = 0, n;
+ __u32 sorted_start_id = 0;
+
+ if (btf->nr_types < 2)
+ return;
+
+ n = btf__type_cnt(btf) - 1;
+ for (i = btf->start_id; i < n; i++) {
+ k = i + 1;
+ if (btf_compare_type_names(&i, &k, btf) > 0)
+ return;
+ t = btf_type_by_id(btf, i);
+ if (sorted_start_id == 0 &&
+ !str_is_empty(btf__str_by_offset(btf, t->name_off)))
+ sorted_start_id = i;
+ }
+
+ t = btf_type_by_id(btf, k);
+ if (sorted_start_id == 0 &&
+ !str_is_empty(btf__str_by_offset(btf, t->name_off)))
+ sorted_start_id = k;
+ 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)
{
@@ -935,7 +978,7 @@ static __s32 btf_find_by_name_kind(const struct btf *btf, int start_id,
if (start_id < btf->start_id) {
idx = btf_find_by_name_kind(btf->base_btf, start_id,
- type_name, kind);
+ type_name, kind);
if (idx >= 0)
return idx;
start_id = btf->start_id;
@@ -1147,6 +1190,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.1On Mon, 2025-12-08 at 14:23 +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>
> ---
> tools/lib/bpf/btf.c | 46 ++++++++++++++++++++++++++++++++++++++++++++-
> 1 file changed, 45 insertions(+), 1 deletion(-)
>
> diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c
> index 7f150c869bf6..a53d24704857 100644
> --- a/tools/lib/bpf/btf.c
> +++ b/tools/lib/bpf/btf.c
> @@ -899,6 +899,49 @@ 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(const void *a, const void *b, void *priv)
This can be declared as ...(u32 a, u32 b, struct btf *btf).
> +{
> + struct btf *btf = (struct btf *)priv;
> + struct btf_type *ta = btf_type_by_id(btf, *(__u32 *)a);
> + struct btf_type *tb = btf_type_by_id(btf, *(__u32 *)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;
> + int i, k = 0, n;
> + __u32 sorted_start_id = 0;
> +
> + if (btf->nr_types < 2)
> + return;
> +
> + n = btf__type_cnt(btf) - 1;
> + for (i = btf->start_id; i < n; i++) {
> + k = i + 1;
> + if (btf_compare_type_names(&i, &k, btf) > 0)
> + return;
> + t = btf_type_by_id(btf, i);
> + if (sorted_start_id == 0 &&
> + !str_is_empty(btf__str_by_offset(btf, t->name_off)))
^^^^^^^^
Nit: broken indentation.
> + sorted_start_id = i;
> + }
> +
> + t = btf_type_by_id(btf, k);
Nit: please use 'n' instead of 'k'.
Maybe just change condition in the loop and avoid the second part?
E.g.:
n = btf__type_cnt(btf);
for (...) {
...
if (k < n && btf_compare_type_names(a: &i, b: &k, priv: btf) > 0)
return;
...
}
A bit shorter/simpler this way.
> + if (sorted_start_id == 0 &&
> + !str_is_empty(btf__str_by_offset(btf, t->name_off)))
> + sorted_start_id = k;
> + 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)
> {
> @@ -935,7 +978,7 @@ static __s32 btf_find_by_name_kind(const struct btf *btf, int start_id,
>
> if (start_id < btf->start_id) {
> idx = btf_find_by_name_kind(btf->base_btf, start_id,
> - type_name, kind);
> + type_name, kind);
Nit: shouldn't be in this patch.
> if (idx >= 0)
> return idx;
> start_id = btf->start_id;
> @@ -1147,6 +1190,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) {
On Wed, Dec 17, 2025 at 8:32 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Mon, 2025-12-08 at 14:23 +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>
> > ---
> > tools/lib/bpf/btf.c | 46 ++++++++++++++++++++++++++++++++++++++++++++-
> > 1 file changed, 45 insertions(+), 1 deletion(-)
> >
> > diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c
> > index 7f150c869bf6..a53d24704857 100644
> > --- a/tools/lib/bpf/btf.c
> > +++ b/tools/lib/bpf/btf.c
> > @@ -899,6 +899,49 @@ 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(const void *a, const void *b, void *priv)
>
> This can be declared as ...(u32 a, u32 b, struct btf *btf).
Thanks, I will fix it in the next version.
>
> > +{
> > + struct btf *btf = (struct btf *)priv;
> > + struct btf_type *ta = btf_type_by_id(btf, *(__u32 *)a);
> > + struct btf_type *tb = btf_type_by_id(btf, *(__u32 *)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;
> > + int i, k = 0, n;
> > + __u32 sorted_start_id = 0;
> > +
> > + if (btf->nr_types < 2)
> > + return;
> > +
> > + n = btf__type_cnt(btf) - 1;
> > + for (i = btf->start_id; i < n; i++) {
> > + k = i + 1;
> > + if (btf_compare_type_names(&i, &k, btf) > 0)
> > + return;
> > + t = btf_type_by_id(btf, i);
> > + if (sorted_start_id == 0 &&
> > + !str_is_empty(btf__str_by_offset(btf, t->name_off)))
> ^^^^^^^^
> Nit: broken indentation.
Thanks, I will fix it.
>
> > + sorted_start_id = i;
> > + }
> > +
> > + t = btf_type_by_id(btf, k);
>
> Nit: please use 'n' instead of 'k'.
Thanks, I agree, although k equals n at this point.
> Maybe just change condition in the loop and avoid the second part?
> E.g.:
>
> n = btf__type_cnt(btf);
> for (...) {
> ...
> if (k < n && btf_compare_type_names(a: &i, b: &k, priv: btf) > 0)
> return;
> ...
> }
>
> A bit shorter/simpler this way.
Great, I agree and will fix it in the next version.
>
> > + if (sorted_start_id == 0 &&
> > + !str_is_empty(btf__str_by_offset(btf, t->name_off)))
> > + sorted_start_id = k;
> > + 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)
> > {
> > @@ -935,7 +978,7 @@ static __s32 btf_find_by_name_kind(const struct btf *btf, int start_id,
> >
> > if (start_id < btf->start_id) {
> > idx = btf_find_by_name_kind(btf->base_btf, start_id,
> > - type_name, kind);
> > + type_name, kind);
>
> Nit: shouldn't be in this patch.
Thanks, I will fix it in the next version.
>
> > if (idx >= 0)
> > return idx;
> > start_id = btf->start_id;
> > @@ -1147,6 +1190,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) {
>
© 2016 - 2026 Red Hat, Inc.