Message-ID: <CAErzpmtWLLYuFk3npTiOgGOKcEcH1QUGGEHLvPncVT+z261C1A@mail.gmail.com>
Date: Thu, 23 Oct 2025 18:35:13 +0800
From: Donglin Peng <dolinux.peng@...il.com>
To: Eduard Zingerman <eddyz87@...il.com>, ast@...nel.org, 
	Andrii Nakryiko <andrii.nakryiko@...il.com>, Alan Maguire <alan.maguire@...cle.com>
Cc: linux-kernel@...r.kernel.org, bpf@...r.kernel.org, 
	Song Liu <song@...nel.org>, pengdonglin <pengdonglin@...omi.com>
Subject: Re: [RFC PATCH v2 2/5] btf: sort BTF types by kind and name to enable
 binary search

On Thu, Oct 23, 2025 at 4:50 AM Eduard Zingerman <eddyz87@...il.com> wrote:
>
> On Wed, 2025-10-22 at 11:02 +0800, Donglin Peng wrote:
> > On Wed, Oct 22, 2025 at 2:59 AM Eduard Zingerman <eddyz87@...il.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.

I get your point, thanks. I wonder what others think?

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

The start_id parameter here serves the same purpose as the one in
libbpf's btf_find_by_name_kind. However, its implementation in
find_btf_by_name_kind was incorrect. I will fix this in the next version.

__s32 btf__find_by_name_kind_own(const struct btf *btf, const char *type_name,
__u32 kind)
{
return btf_find_by_name_kind(btf, btf->start_id, type_name, kind);
}

__s32 btf__find_by_name_kind(const struct btf *btf, const char *type_name,
     __u32 kind)
{
return btf_find_by_name_kind(btf, 1, type_name, kind);
}

static __s32 btf_find_by_name_kind(const struct btf *btf, int start_id,
   const char *type_name, __u32 kind)
{
__u32 i, nr_types = btf__type_cnt(btf);

if (kind == BTF_KIND_UNKN || !strcmp(type_name, "void"))
return 0;

for (i = start_id; i < nr_types; i++) {
const struct btf_type *t = btf__type_by_id(btf, i);
const char *name;

if (btf_kind(t) != kind)
continue;
name = btf__name_by_offset(btf, t->name_off);
if (name && !strcmp(type_name, name))
return i;
}

return libbpf_err(-ENOENT);

}

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

Powered by blists - more mailing lists