Re: [RFC PATCH v2 2/5] btf: sort BTF types by kind and name to enable binary search

[Eduard Zingerman <eddyz87@gmail.com>]

On Wed, 2025-10-22 at 11:02 +0800, Donglin Peng wrote:
> On Wed, Oct 22, 2025 at 2:59 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > 
> > On Mon, 2025-10-20 at 17:39 +0800, Donglin Peng wrote:
> > > This patch implements sorting of BTF types by their kind and name,
> > > enabling the use of binary search for type lookups.
> > > 
> > > To share logic between kernel and libbpf, a new btf_sort.c file is
> > > introduced containing common sorting functionality.
> > > 
> > > The sorting is performed during btf__dedup() when the new
> > > sort_by_kind_name option in btf_dedup_opts is enabled.
> > 
> > Do we really need this option?  Dedup is free to rearrange btf types
> > anyway, so why not sort always?  Is execution time a concern?
> 
> The issue is that sorting changes the layout of BTF. Many existing selftests
> rely on the current, non-sorted order for their validation checks. Introducing
> this as an optional feature first allows us to run it without immediately
> breaking the tests, giving us time to fix them incrementally.

How many tests are we talking about?
The option is an API and it stays with us forever.
If the only justification for its existence is to avoid tests
modification, I don't think that's enough.

> > 
> > > For vmlinux and kernel module BTF, btf_check_sorted() verifies
> > > whether the types are sorted and binary search can be used.
> > 
> > [...]
> > 
> > > diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c
> > > index c414cf37e1bd..11b05f4eb07d 100644
> > > --- a/kernel/bpf/btf.c
> > > +++ b/kernel/bpf/btf.c

[...]

> > > +s32 btf_find_by_name_kind(const struct btf *btf, const char *name, u8 kind)
> > > +{
> > > +     return find_btf_by_name_kind(btf, 1, name, kind);
> >                                          ^^^
> >                 nit: this will make it impossible to find "void" w/o a special case
> >                      in the find_btf_by_name_kind(), why not start from 0?
> 
> Thanks. I referred to btf__find_by_name_kind in libbpf. In
> btf_find_by_name_kind,
> there is a special check for "void". Consequently, I've added a
> similar special check
> for "void" in find_btf_by_name_kind as well.

Yes, I see the special case in the find_btf_by_name_kind.
But wouldn't starting from 0 here avoid the need for special case?

[...]

> > > diff --git a/tools/lib/bpf/btf_sort.c b/tools/lib/bpf/btf_sort.c
> > > new file mode 100644
> > > index 000000000000..2ad4a56f1c08
> > > --- /dev/null
> > > +++ b/tools/lib/bpf/btf_sort.c
> > 
> > [...]
> > 
> > > +/*
> > > + * Sort BTF types by kind and name in ascending order, placing named types
> > > + * before anonymous ones.
> > > + */
> > > +int btf_compare_type_kinds_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;
> > > +     int ka, kb;
> > > +
> > > +     /* ta w/o name is greater than tb */
> > > +     if (!ta->name_off && tb->name_off)
> > > +             return 1;
> > > +     /* tb w/o name is smaller than ta */
> > > +     if (ta->name_off && !tb->name_off)
> > > +             return -1;
> > > +
> > > +     ka = btf_kind(ta);
> > > +     kb = btf_kind(tb);
> > > +     na = btf__str_by_offset(btf, ta->name_off);
> > > +     nb = btf__str_by_offset(btf, tb->name_off);
> > > +
> > > +     return cmp_btf_kind_name(ka, na, kb, nb);
> > 
> > If both types are anonymous and have the same kind, this will lead to
> > strcmp(NULL, NULL). On kernel side that would lead to null pointer
> > dereference.
> 
> Thanks, I've confirmed that for anonymous types, name_off is 0,
> so btf__str_by_offset returns a pointer to btf->strs_data (which
> contains a '\0' at index 0) rather than NULL. However, when name_off
> is invalid, btf__str_by_offset does return NULL. Using str_is_empty
> will correctly handle both scenarios. Unnamed types of the same kind
> shall be considered equal. I will fix it in the next version.

I see, thank you for explaining.
Checking the usage of kernel/bpf/btf.c:btf_name_valid_identifier(),
it looks like kernel validates name_off for all types.
So, your implementation should be fine.

[...]