From: Donglin Peng <pengdonglin@xiaomi.com>
This patch adds validation to verify BTF type name sorting, enabling
binary search optimization for lookups.
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: Song Liu <song@kernel.org>
Cc: Xiaoqin Zhang <zhangxiaoqin@xiaomi.com>
Signed-off-by: Donglin Peng <pengdonglin@xiaomi.com>
---
tools/lib/bpf/btf.c | 59 +++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 59 insertions(+)
diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c
index 1d19d95da1d0..d872abff42e1 100644
--- a/tools/lib/bpf/btf.c
+++ b/tools/lib/bpf/btf.c
@@ -903,6 +903,64 @@ int btf__resolve_type(const struct btf *btf, __u32 type_id)
return type_id;
}
+/* Anonymous types (with empty names) are considered greater than named types
+ * and are sorted after them. Two anonymous types are considered equal. Named
+ * types are compared lexicographically.
+ */
+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;
+ bool anon_a, anon_b;
+
+ na = btf__str_by_offset(btf, ta->name_off);
+ nb = btf__str_by_offset(btf, tb->name_off);
+ anon_a = str_is_empty(na);
+ anon_b = str_is_empty(nb);
+
+ if (anon_a && !anon_b)
+ return 1;
+ if (!anon_a && anon_b)
+ return -1;
+ if (anon_a && anon_b)
+ return 0;
+
+ return strcmp(na, nb);
+}
+
+/* Verifies that BTF types are sorted in ascending order according to their
+ * names, with named types appearing before anonymous types. If the ordering
+ * is correct, counts the number of named types and updates the BTF object's
+ * nr_sorted_types field.
+ */
+static void btf_check_sorted(struct btf *btf)
+{
+ const struct btf_type *t;
+ int i, k = 0, n, nr_sorted_types;
+
+ if (btf->nr_types < 2)
+ return;
+
+ nr_sorted_types = 0;
+ 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 (!str_is_empty(btf__str_by_offset(btf, t->name_off)))
+ nr_sorted_types++;
+ }
+
+ t = btf_type_by_id(btf, k);
+ if (!str_is_empty(btf__str_by_offset(btf, t->name_off)))
+ nr_sorted_types++;
+ if (nr_sorted_types)
+ btf->nr_sorted_types = nr_sorted_types;
+}
+
static __s32 btf_find_type_by_name_bsearch(const struct btf *btf, const char *name,
__s32 start_id, __s32 end_id)
{
@@ -1148,6 +1206,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 Tue, Nov 18, 2025 at 7:21 PM Donglin Peng <dolinux.peng@gmail.com> wrote:
>
> From: Donglin Peng <pengdonglin@xiaomi.com>
>
> This patch adds validation to verify BTF type name sorting, enabling
> binary search optimization for lookups.
>
> 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: Song Liu <song@kernel.org>
> Cc: Xiaoqin Zhang <zhangxiaoqin@xiaomi.com>
> Signed-off-by: Donglin Peng <pengdonglin@xiaomi.com>
> ---
> tools/lib/bpf/btf.c | 59 +++++++++++++++++++++++++++++++++++++++++++++
> 1 file changed, 59 insertions(+)
>
> diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c
> index 1d19d95da1d0..d872abff42e1 100644
> --- a/tools/lib/bpf/btf.c
> +++ b/tools/lib/bpf/btf.c
> @@ -903,6 +903,64 @@ int btf__resolve_type(const struct btf *btf, __u32 type_id)
> return type_id;
> }
>
> +/* Anonymous types (with empty names) are considered greater than named types
> + * and are sorted after them. Two anonymous types are considered equal. Named
> + * types are compared lexicographically.
> + */
> +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;
> + bool anon_a, anon_b;
> +
> + na = btf__str_by_offset(btf, ta->name_off);
> + nb = btf__str_by_offset(btf, tb->name_off);
> + anon_a = str_is_empty(na);
> + anon_b = str_is_empty(nb);
> +
> + if (anon_a && !anon_b)
> + return 1;
> + if (!anon_a && anon_b)
> + return -1;
> + if (anon_a && anon_b)
> + return 0;
any reason to hard-code that anonymous types should come *after* named
ones? That requires custom comparison logic here and resolve_btfids,
instead of just relying on btf__str_by_offset() returning valid empty
string for name_off == 0 and then sorting anon types before named
ones, following normal lexicographical sorting rules?
[...]
On Thu, Nov 20, 2025 at 3:50 AM Andrii Nakryiko
<andrii.nakryiko@gmail.com> wrote:
>
> On Tue, Nov 18, 2025 at 7:21 PM Donglin Peng <dolinux.peng@gmail.com> wrote:
> >
> > From: Donglin Peng <pengdonglin@xiaomi.com>
> >
> > This patch adds validation to verify BTF type name sorting, enabling
> > binary search optimization for lookups.
> >
> > 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: Song Liu <song@kernel.org>
> > Cc: Xiaoqin Zhang <zhangxiaoqin@xiaomi.com>
> > Signed-off-by: Donglin Peng <pengdonglin@xiaomi.com>
> > ---
> > tools/lib/bpf/btf.c | 59 +++++++++++++++++++++++++++++++++++++++++++++
> > 1 file changed, 59 insertions(+)
> >
> > diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c
> > index 1d19d95da1d0..d872abff42e1 100644
> > --- a/tools/lib/bpf/btf.c
> > +++ b/tools/lib/bpf/btf.c
> > @@ -903,6 +903,64 @@ int btf__resolve_type(const struct btf *btf, __u32 type_id)
> > return type_id;
> > }
> >
> > +/* Anonymous types (with empty names) are considered greater than named types
> > + * and are sorted after them. Two anonymous types are considered equal. Named
> > + * types are compared lexicographically.
> > + */
> > +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;
> > + bool anon_a, anon_b;
> > +
> > + na = btf__str_by_offset(btf, ta->name_off);
> > + nb = btf__str_by_offset(btf, tb->name_off);
> > + anon_a = str_is_empty(na);
> > + anon_b = str_is_empty(nb);
> > +
> > + if (anon_a && !anon_b)
> > + return 1;
> > + if (!anon_a && anon_b)
> > + return -1;
> > + if (anon_a && anon_b)
> > + return 0;
>
> any reason to hard-code that anonymous types should come *after* named
> ones? That requires custom comparison logic here and resolve_btfids,
> instead of just relying on btf__str_by_offset() returning valid empty
> string for name_off == 0 and then sorting anon types before named
> ones, following normal lexicographical sorting rules?
Thanks. I found that some kernel functions like btf_find_next_decl_tag,
bpf_core_add_cands, find_bpffs_btf_enums, and find_btf_percpu_datasec
still use linear search. Putting named types first would also help here, as
it allows anonymous types to be skipped naturally during the search.
Some of them could be refactored to use btf_find_by_name_kind, but some
would not be appropriate, such as btf_find_next_decl_tag,
bpf_core_add_cands,find_btf_percpu_datasec.
Additionally, in the linear search branch, I saw there is a NULL check for
the name returned by btf__name_by_offset. This suggests that checking
name_off == 0 alone may not be sufficient to identify an anonymous type,
which is why I used str_is_empty for a more robust check.
>
> [...]
On Thu, 2025-11-20 at 15:25 +0800, Donglin Peng wrote: [...] > Additionally, in the linear search branch, I saw there is a NULL check for > the name returned by btf__name_by_offset. This suggests that checking > name_off == 0 alone may not be sufficient to identify an anonymous type, > which is why I used str_is_empty for a more robust check. btf_str_by_offset(btf, offset) returns NULL only when 'offset' is larger then 'btf->hdr.str_len'. However, function btf_check_meta() verifies that this shall not happen by invoking btf_name_offset_valid() check. The btf_check_meta() is invoked for all types by btf_check_all_metas() called from btf_parse_base(), btf_parse_module() and btf_parse_type_sec() -> btf_parse(). So, it appears that kernel protects itself from invalid name_off values at BTF load time. [...]
On Sat, Nov 22, 2025 at 3:42 AM Eduard Zingerman <eddyz87@gmail.com> wrote: > > On Thu, 2025-11-20 at 15:25 +0800, Donglin Peng wrote: > > [...] > > > Additionally, in the linear search branch, I saw there is a NULL check for > > the name returned by btf__name_by_offset. This suggests that checking > > name_off == 0 alone may not be sufficient to identify an anonymous type, > > which is why I used str_is_empty for a more robust check. > > btf_str_by_offset(btf, offset) returns NULL only when 'offset' is > larger then 'btf->hdr.str_len'. However, function btf_check_meta() > verifies that this shall not happen by invoking > btf_name_offset_valid() check. The btf_check_meta() is invoked for all > types by btf_check_all_metas() called from btf_parse_base(), > btf_parse_module() and btf_parse_type_sec() -> btf_parse(). > > So, it appears that kernel protects itself from invalid name_off > values at BTF load time. Right. The kernel guarantees that btf_str_by_offsetnever returns NULL, and there is no NULL check performed on the name returned by btf_find_by_name_kind. The NULL check is included in the libbpf version of the function. > > [...]
On Sat, Nov 22, 2025 at 3:32 PM Donglin Peng <dolinux.peng@gmail.com> wrote: > > On Sat, Nov 22, 2025 at 3:42 AM Eduard Zingerman <eddyz87@gmail.com> wrote: > > > > On Thu, 2025-11-20 at 15:25 +0800, Donglin Peng wrote: > > > > [...] > > > > > Additionally, in the linear search branch, I saw there is a NULL check for > > > the name returned by btf__name_by_offset. This suggests that checking > > > name_off == 0 alone may not be sufficient to identify an anonymous type, > > > which is why I used str_is_empty for a more robust check. > > > > btf_str_by_offset(btf, offset) returns NULL only when 'offset' is > > larger then 'btf->hdr.str_len'. However, function btf_check_meta() > > verifies that this shall not happen by invoking > > btf_name_offset_valid() check. The btf_check_meta() is invoked for all > > types by btf_check_all_metas() called from btf_parse_base(), > > btf_parse_module() and btf_parse_type_sec() -> btf_parse(). > > > > So, it appears that kernel protects itself from invalid name_off > > values at BTF load time. > > Right. The kernel guarantees that btf_str_by_offsetnever returns NULL, > and there is no NULL check performed on the name returned by > btf_find_by_name_kind. The NULL check is included in the libbpf version > of the function. Sorry — my mistake. There’s no NULL check on the name from btf_str_by_offset in the kernel’s btf_find_by_name_kind. The libbpf version has it. > > > > > [...]
On Sat, 2025-11-22 at 16:38 +0800, Donglin Peng wrote: > On Sat, Nov 22, 2025 at 3:32 PM Donglin Peng <dolinux.peng@gmail.com> wrote: > > > > On Sat, Nov 22, 2025 at 3:42 AM Eduard Zingerman <eddyz87@gmail.com> wrote: > > > > > > On Thu, 2025-11-20 at 15:25 +0800, Donglin Peng wrote: > > > > > > [...] > > > > > > > Additionally, in the linear search branch, I saw there is a NULL check for > > > > the name returned by btf__name_by_offset. This suggests that checking > > > > name_off == 0 alone may not be sufficient to identify an anonymous type, > > > > which is why I used str_is_empty for a more robust check. > > > > > > btf_str_by_offset(btf, offset) returns NULL only when 'offset' is > > > larger then 'btf->hdr.str_len'. However, function btf_check_meta() > > > verifies that this shall not happen by invoking > > > btf_name_offset_valid() check. The btf_check_meta() is invoked for all > > > types by btf_check_all_metas() called from btf_parse_base(), > > > btf_parse_module() and btf_parse_type_sec() -> btf_parse(). > > > > > > So, it appears that kernel protects itself from invalid name_off > > > values at BTF load time. > > > > Right. The kernel guarantees that btf_str_by_offsetnever returns NULL, > > and there is no NULL check performed on the name returned by > > btf_find_by_name_kind. The NULL check is included in the libbpf version > > of the function. > > Sorry — my mistake. There’s no NULL check on the name from > btf_str_by_offset in the kernel’s btf_find_by_name_kind. The > libbpf version has it. tools/lib/bpf/btf.c:btf_sanity_check() is called from btf_new(), it calls btf_validate_type(), which does btf_validate_str(). So, ignoring the NULL case on libbpf side should be safe as well. [...]
On Tue, Nov 25, 2025 at 2:20 AM Eduard Zingerman <eddyz87@gmail.com> wrote: > > On Sat, 2025-11-22 at 16:38 +0800, Donglin Peng wrote: > > On Sat, Nov 22, 2025 at 3:32 PM Donglin Peng <dolinux.peng@gmail.com> wrote: > > > > > > On Sat, Nov 22, 2025 at 3:42 AM Eduard Zingerman <eddyz87@gmail.com> wrote: > > > > > > > > On Thu, 2025-11-20 at 15:25 +0800, Donglin Peng wrote: > > > > > > > > [...] > > > > > > > > > Additionally, in the linear search branch, I saw there is a NULL check for > > > > > the name returned by btf__name_by_offset. This suggests that checking > > > > > name_off == 0 alone may not be sufficient to identify an anonymous type, > > > > > which is why I used str_is_empty for a more robust check. > > > > > > > > btf_str_by_offset(btf, offset) returns NULL only when 'offset' is > > > > larger then 'btf->hdr.str_len'. However, function btf_check_meta() > > > > verifies that this shall not happen by invoking > > > > btf_name_offset_valid() check. The btf_check_meta() is invoked for all > > > > types by btf_check_all_metas() called from btf_parse_base(), > > > > btf_parse_module() and btf_parse_type_sec() -> btf_parse(). > > > > > > > > So, it appears that kernel protects itself from invalid name_off > > > > values at BTF load time. > > > > > > Right. The kernel guarantees that btf_str_by_offsetnever returns NULL, > > > and there is no NULL check performed on the name returned by > > > btf_find_by_name_kind. The NULL check is included in the libbpf version > > > of the function. > > > > Sorry — my mistake. There’s no NULL check on the name from > > btf_str_by_offset in the kernel’s btf_find_by_name_kind. The > > libbpf version has it. > > tools/lib/bpf/btf.c:btf_sanity_check() is called from btf_new(), > it calls btf_validate_type(), which does btf_validate_str(). > So, ignoring the NULL case on libbpf side should be safe as well. Thanks, I also noticed that too and will drop the NULL check in the next version. > > [...]
On Thu, 2025-11-20 at 15:25 +0800, Donglin Peng wrote:
> On Thu, Nov 20, 2025 at 3:50 AM Andrii Nakryiko
> <andrii.nakryiko@gmail.com> wrote:
> >
> > On Tue, Nov 18, 2025 at 7:21 PM Donglin Peng <dolinux.peng@gmail.com> wrote:
> > >
> > > From: Donglin Peng <pengdonglin@xiaomi.com>
> > >
> > > This patch adds validation to verify BTF type name sorting, enabling
> > > binary search optimization for lookups.
> > >
> > > 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: Song Liu <song@kernel.org>
> > > Cc: Xiaoqin Zhang <zhangxiaoqin@xiaomi.com>
> > > Signed-off-by: Donglin Peng <pengdonglin@xiaomi.com>
> > > ---
> > > tools/lib/bpf/btf.c | 59 +++++++++++++++++++++++++++++++++++++++++++++
> > > 1 file changed, 59 insertions(+)
> > >
> > > diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c
> > > index 1d19d95da1d0..d872abff42e1 100644
> > > --- a/tools/lib/bpf/btf.c
> > > +++ b/tools/lib/bpf/btf.c
> > > @@ -903,6 +903,64 @@ int btf__resolve_type(const struct btf *btf, __u32 type_id)
> > > return type_id;
> > > }
> > >
> > > +/* Anonymous types (with empty names) are considered greater than named types
> > > + * and are sorted after them. Two anonymous types are considered equal. Named
> > > + * types are compared lexicographically.
> > > + */
> > > +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;
> > > + bool anon_a, anon_b;
> > > +
> > > + na = btf__str_by_offset(btf, ta->name_off);
> > > + nb = btf__str_by_offset(btf, tb->name_off);
> > > + anon_a = str_is_empty(na);
> > > + anon_b = str_is_empty(nb);
> > > +
> > > + if (anon_a && !anon_b)
> > > + return 1;
> > > + if (!anon_a && anon_b)
> > > + return -1;
> > > + if (anon_a && anon_b)
> > > + return 0;
> >
> > any reason to hard-code that anonymous types should come *after* named
> > ones? That requires custom comparison logic here and resolve_btfids,
> > instead of just relying on btf__str_by_offset() returning valid empty
> > string for name_off == 0 and then sorting anon types before named
> > ones, following normal lexicographical sorting rules?
>
> Thanks. I found that some kernel functions like btf_find_next_decl_tag,
> bpf_core_add_cands, find_bpffs_btf_enums, and find_btf_percpu_datasec
> still use linear search.
- btf_find_next_decl_tag() - this function is called from:
- btf_find_decl_tag_value(), here whole scan over all BTF types is
guaranteed to happen (because btf_find_next_decl_tag() is called
twice);
- btf_prepare_func_args(), here again whole scan is guaranteed to
happen, because of the while loop starting from id == 0.
- bpf_core_add_cands() this function is called from
bpf_core_find_cands(), where it does a linear scan over all types in
kernel BTF and then a linear scan over all types in module BTFs.
(Because of how targ_start_id parameter is passed).
- find_bpffs_btf_enums() - this function does a linear scan over all
types in module BTFs.
- find_btf_percpu_datasec() - this function looks for a DATASEC with
name ".data..percpu" and returns as soon as the match is found.
Of the 4 functions above only find_btf_percpu_datasec() will return
early if BTF type with specified name is found. And it can be
converted to use btf_find_by_name_kind().
So, it appears that there should not be any performance penalty
(compared to current state of affairs) if anonymous types are put in
front. Wdyt?
> Putting named types first would also help here, as
> it allows anonymous types to be skipped naturally during the search.
> Some of them could be refactored to use btf_find_by_name_kind, but some
> would not be appropriate, such as btf_find_next_decl_tag,
> bpf_core_add_cands,find_btf_percpu_datasec.
Did you observe any performance issue if anonymous types are put in
the front?
> Additionally, in the linear search branch, I saw there is a NULL check for
> the name returned by btf__name_by_offset. This suggests that checking
> name_off == 0 alone may not be sufficient to identify an anonymous type,
> which is why I used str_is_empty for a more robust check.
>
> >
> > [...]
On Sat, Nov 22, 2025 at 3:07 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Thu, 2025-11-20 at 15:25 +0800, Donglin Peng wrote:
> > On Thu, Nov 20, 2025 at 3:50 AM Andrii Nakryiko
> > <andrii.nakryiko@gmail.com> wrote:
> > >
> > > On Tue, Nov 18, 2025 at 7:21 PM Donglin Peng <dolinux.peng@gmail.com> wrote:
> > > >
> > > > From: Donglin Peng <pengdonglin@xiaomi.com>
> > > >
> > > > This patch adds validation to verify BTF type name sorting, enabling
> > > > binary search optimization for lookups.
> > > >
> > > > 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: Song Liu <song@kernel.org>
> > > > Cc: Xiaoqin Zhang <zhangxiaoqin@xiaomi.com>
> > > > Signed-off-by: Donglin Peng <pengdonglin@xiaomi.com>
> > > > ---
> > > > tools/lib/bpf/btf.c | 59 +++++++++++++++++++++++++++++++++++++++++++++
> > > > 1 file changed, 59 insertions(+)
> > > >
> > > > diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c
> > > > index 1d19d95da1d0..d872abff42e1 100644
> > > > --- a/tools/lib/bpf/btf.c
> > > > +++ b/tools/lib/bpf/btf.c
> > > > @@ -903,6 +903,64 @@ int btf__resolve_type(const struct btf *btf, __u32 type_id)
> > > > return type_id;
> > > > }
> > > >
> > > > +/* Anonymous types (with empty names) are considered greater than named types
> > > > + * and are sorted after them. Two anonymous types are considered equal. Named
> > > > + * types are compared lexicographically.
> > > > + */
> > > > +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;
> > > > + bool anon_a, anon_b;
> > > > +
> > > > + na = btf__str_by_offset(btf, ta->name_off);
> > > > + nb = btf__str_by_offset(btf, tb->name_off);
> > > > + anon_a = str_is_empty(na);
> > > > + anon_b = str_is_empty(nb);
> > > > +
> > > > + if (anon_a && !anon_b)
> > > > + return 1;
> > > > + if (!anon_a && anon_b)
> > > > + return -1;
> > > > + if (anon_a && anon_b)
> > > > + return 0;
> > >
> > > any reason to hard-code that anonymous types should come *after* named
> > > ones? That requires custom comparison logic here and resolve_btfids,
> > > instead of just relying on btf__str_by_offset() returning valid empty
> > > string for name_off == 0 and then sorting anon types before named
> > > ones, following normal lexicographical sorting rules?
> >
> > Thanks. I found that some kernel functions like btf_find_next_decl_tag,
> > bpf_core_add_cands, find_bpffs_btf_enums, and find_btf_percpu_datasec
> > still use linear search.
>
> - btf_find_next_decl_tag() - this function is called from:
> - btf_find_decl_tag_value(), here whole scan over all BTF types is
> guaranteed to happen (because btf_find_next_decl_tag() is called
> twice);
> - btf_prepare_func_args(), here again whole scan is guaranteed to
> happen, because of the while loop starting from id == 0.
Right.
> - bpf_core_add_cands() this function is called from
> bpf_core_find_cands(), where it does a linear scan over all types in
> kernel BTF and then a linear scan over all types in module BTFs.
> (Because of how targ_start_id parameter is passed).
Right.
> - find_bpffs_btf_enums() - this function does a linear scan over all
> types in module BTFs.
I think putting names ahead is helpful here, because there is a check
(info->cmd_t && info->map_t && info->prog_t && info->attach_t) to
return early. but I think it can be converted to use btf_find_by_name_kind.
> - find_btf_percpu_datasec() - this function looks for a DATASEC with
> name ".data..percpu" and returns as soon as the match is found.
>
> Of the 4 functions above only find_btf_percpu_datasec() will return
> early if BTF type with specified name is found. And it can be
> converted to use btf_find_by_name_kind().
Thanks. I’ve looked into find_btf_percpu_datasec and we can’t use
btf_find_by_name_kind here because the search scope differs. For
a module BTF, find_btf_percpu_datasec only searches within the
module’s own BTF, whereas btf_find_by_name_kind prioritizes
searching the base BTF first. Thus, placing named types ahead is
more effective here. Besides, I found that the '.data..percpu' named
type will be placed at [1] for vmlinux BTF because the prefix '.' is
smaller than any letter, so the linear search only requires one loop to
locate it. However, if we put named types at the end, it will need more
than 60,000 loops..
>
> So, it appears that there should not be any performance penalty
> (compared to current state of affairs) if anonymous types are put in
> front. Wdyt?
>
> > Putting named types first would also help here, as
> > it allows anonymous types to be skipped naturally during the search.
> > Some of them could be refactored to use btf_find_by_name_kind, but some
> > would not be appropriate, such as btf_find_next_decl_tag,
> > bpf_core_add_cands,find_btf_percpu_datasec.
>
> Did you observe any performance issue if anonymous types are put in
> the front?
No, I have not done such a test, but based on the above analysis, the
improvement
mainly comes from find_bpffs_btf_enums and find_btf_percpu_datasec.
>
> > Additionally, in the linear search branch, I saw there is a NULL check for
> > the name returned by btf__name_by_offset. This suggests that checking
> > name_off == 0 alone may not be sufficient to identify an anonymous type,
> > which is why I used str_is_empty for a more robust check.
> >
> > >
> > > [...]
On Sat, 2025-11-22 at 15:19 +0800, Donglin Peng wrote: [...] > > - find_bpffs_btf_enums() - this function does a linear scan over all > > types in module BTFs. > > I think putting names ahead is helpful here, because there is a check > (info->cmd_t && info->map_t && info->prog_t && info->attach_t) to > return early. but I think it can be converted to use btf_find_by_name_kind. Oh, sorry, I somehow missed the early exit here. But as you say, it is a combination of 4 by-name lookups, essentially. Thus can be converted to btf_find_by_name_kind() trivially. > > - find_btf_percpu_datasec() - this function looks for a DATASEC with > > name ".data..percpu" and returns as soon as the match is found. > > > > Of the 4 functions above only find_btf_percpu_datasec() will return > > early if BTF type with specified name is found. And it can be > > converted to use btf_find_by_name_kind(). > > Thanks. I’ve looked into find_btf_percpu_datasec and we can’t use > btf_find_by_name_kind here because the search scope differs. For > a module BTF, find_btf_percpu_datasec only searches within the > module’s own BTF, whereas btf_find_by_name_kind prioritizes > searching the base BTF first. Thus, placing named types ahead is > more effective here. Besides, I found that the '.data..percpu' named > type will be placed at [1] for vmlinux BTF because the prefix '.' is > smaller than any letter, so the linear search only requires one loop to > locate it. However, if we put named types at the end, it will need more > than 60,000 loops.. But this can be easily fixed if a variant of btf_find_by_name_kind() is provided that looks for a match only in a specific BTF. Or accepts a start id parameter.
On Sat, Nov 22, 2025 at 4:50 PM Eduard Zingerman <eddyz87@gmail.com> wrote: > > On Sat, 2025-11-22 at 15:19 +0800, Donglin Peng wrote: > > [...] > > > > - find_bpffs_btf_enums() - this function does a linear scan over all > > > types in module BTFs. > > > > I think putting names ahead is helpful here, because there is a check > > (info->cmd_t && info->map_t && info->prog_t && info->attach_t) to > > return early. but I think it can be converted to use btf_find_by_name_kind. > > Oh, sorry, I somehow missed the early exit here. > But as you say, it is a combination of 4 by-name lookups, essentially. > Thus can be converted to btf_find_by_name_kind() trivially. > > > > - find_btf_percpu_datasec() - this function looks for a DATASEC with > > > name ".data..percpu" and returns as soon as the match is found. > > > > > > Of the 4 functions above only find_btf_percpu_datasec() will return > > > early if BTF type with specified name is found. And it can be > > > converted to use btf_find_by_name_kind(). > > > > Thanks. I’ve looked into find_btf_percpu_datasec and we can’t use > > btf_find_by_name_kind here because the search scope differs. For > > a module BTF, find_btf_percpu_datasec only searches within the > > module’s own BTF, whereas btf_find_by_name_kind prioritizes > > searching the base BTF first. Thus, placing named types ahead is > > more effective here. Besides, I found that the '.data..percpu' named > > type will be placed at [1] for vmlinux BTF because the prefix '.' is > > smaller than any letter, so the linear search only requires one loop to > > locate it. However, if we put named types at the end, it will need more > > than 60,000 loops.. > > But this can be easily fixed if a variant of btf_find_by_name_kind() > is provided that looks for a match only in a specific BTF. Or accepts > a start id parameter. Yes, but I'm not sure it's necessary to add a new parameter to btf_find_by_name_kind for just one use case.
On Sat, 2025-11-22 at 00:50 -0800, Eduard Zingerman wrote: [...] > > Thanks. I’ve looked into find_btf_percpu_datasec and we can’t use > > btf_find_by_name_kind here because the search scope differs. For > > a module BTF, find_btf_percpu_datasec only searches within the > > module’s own BTF, whereas btf_find_by_name_kind prioritizes > > searching the base BTF first. Thus, placing named types ahead is > > more effective here. Besides, I found that the '.data..percpu' named > > type will be placed at [1] for vmlinux BTF because the prefix '.' is > > smaller than any letter, so the linear search only requires one loop to > > locate it. However, if we put named types at the end, it will need more > > than 60,000 loops.. > > But this can be easily fixed if a variant of btf_find_by_name_kind() > is provided that looks for a match only in a specific BTF. Or accepts > a start id parameter. Also, I double checked, and for my vmlinux the id for '.data..percpu' section is 110864, the last id of all. So, having all anonymous types in front does not change status-quo compared to current implementation.
On Sat, Nov 22, 2025 at 5:05 PM Eduard Zingerman <eddyz87@gmail.com> wrote: > > On Sat, 2025-11-22 at 00:50 -0800, Eduard Zingerman wrote: > > [...] > > > > Thanks. I’ve looked into find_btf_percpu_datasec and we can’t use > > > btf_find_by_name_kind here because the search scope differs. For > > > a module BTF, find_btf_percpu_datasec only searches within the > > > module’s own BTF, whereas btf_find_by_name_kind prioritizes > > > searching the base BTF first. Thus, placing named types ahead is > > > more effective here. Besides, I found that the '.data..percpu' named > > > type will be placed at [1] for vmlinux BTF because the prefix '.' is > > > smaller than any letter, so the linear search only requires one loop to > > > locate it. However, if we put named types at the end, it will need more > > > than 60,000 loops.. > > > > But this can be easily fixed if a variant of btf_find_by_name_kind() > > is provided that looks for a match only in a specific BTF. Or accepts > > a start id parameter. > > Also, I double checked, and for my vmlinux the id for '.data..percpu' > section is 110864, the last id of all. So, having all anonymous types > in front does not change status-quo compared to current implementation. Yes. If types are sorted alphabetically, the '.data..percpu' section will have ID 1 in vmlinux BTF. In this case, linear search performance is optimal when named types are placed ahead of anonymous types. I would like to understand the benefits of having anonymous types at the front of named types.
On Sat, 2025-11-22 at 23:45 +0800, Donglin Peng wrote: > On Sat, Nov 22, 2025 at 5:05 PM Eduard Zingerman <eddyz87@gmail.com> wrote: > > > > On Sat, 2025-11-22 at 00:50 -0800, Eduard Zingerman wrote: > > > > [...] > > > > > > Thanks. I’ve looked into find_btf_percpu_datasec and we can’t use > > > > btf_find_by_name_kind here because the search scope differs. For > > > > a module BTF, find_btf_percpu_datasec only searches within the > > > > module’s own BTF, whereas btf_find_by_name_kind prioritizes > > > > searching the base BTF first. Thus, placing named types ahead is > > > > more effective here. Besides, I found that the '.data..percpu' named > > > > type will be placed at [1] for vmlinux BTF because the prefix '.' is > > > > smaller than any letter, so the linear search only requires one loop to > > > > locate it. However, if we put named types at the end, it will need more > > > > than 60,000 loops.. > > > > > > But this can be easily fixed if a variant of btf_find_by_name_kind() > > > is provided that looks for a match only in a specific BTF. Or accepts > > > a start id parameter. > > > > Also, I double checked, and for my vmlinux the id for '.data..percpu' > > section is 110864, the last id of all. So, having all anonymous types > > in front does not change status-quo compared to current implementation. > > Yes. If types are sorted alphabetically, the '.data..percpu' section will > have ID 1 in vmlinux BTF. In this case, linear search performance is > optimal when named types are placed ahead of anonymous types. > > I would like to understand the benefits of having anonymous types at the > front of named types. This will allow using strcmp() instead of btf_compare_type_names(), which we have to copy both in kernel and in libbpf. Reducing the code size and cognitive load.
On Tue, Nov 25, 2025 at 2:16 AM Eduard Zingerman <eddyz87@gmail.com> wrote: > > On Sat, 2025-11-22 at 23:45 +0800, Donglin Peng wrote: > > On Sat, Nov 22, 2025 at 5:05 PM Eduard Zingerman <eddyz87@gmail.com> wrote: > > > > > > On Sat, 2025-11-22 at 00:50 -0800, Eduard Zingerman wrote: > > > > > > [...] > > > > > > > > Thanks. I’ve looked into find_btf_percpu_datasec and we can’t use > > > > > btf_find_by_name_kind here because the search scope differs. For > > > > > a module BTF, find_btf_percpu_datasec only searches within the > > > > > module’s own BTF, whereas btf_find_by_name_kind prioritizes > > > > > searching the base BTF first. Thus, placing named types ahead is > > > > > more effective here. Besides, I found that the '.data..percpu' named > > > > > type will be placed at [1] for vmlinux BTF because the prefix '.' is > > > > > smaller than any letter, so the linear search only requires one loop to > > > > > locate it. However, if we put named types at the end, it will need more > > > > > than 60,000 loops.. > > > > > > > > But this can be easily fixed if a variant of btf_find_by_name_kind() > > > > is provided that looks for a match only in a specific BTF. Or accepts > > > > a start id parameter. > > > > > > Also, I double checked, and for my vmlinux the id for '.data..percpu' > > > section is 110864, the last id of all. So, having all anonymous types > > > in front does not change status-quo compared to current implementation. > > > > Yes. If types are sorted alphabetically, the '.data..percpu' section will > > have ID 1 in vmlinux BTF. In this case, linear search performance is > > optimal when named types are placed ahead of anonymous types. > > > > I would like to understand the benefits of having anonymous types at the > > front of named types. > > This will allow using strcmp() instead of btf_compare_type_names(), > which we have to copy both in kernel and in libbpf. Reducing the code > size and cognitive load. Thanks, I will fix it in the next version.
© 2016 - 2025 Red Hat, Inc.