Message-ID: <CAEf4BzY79TJ5=s4EJC-TMc+7fow9E+H0qP67h=W=+BVkbc-ocQ@mail.gmail.com>
Date: Wed, 7 Jan 2026 13:50:51 -0800
From: Andrii Nakryiko <andrii.nakryiko@...il.com>
To: Donglin Peng <dolinux.peng@...il.com>
Cc: ast@...nel.org, eddyz87@...il.com, zhangxiaoqin@...omi.com, 
	ihor.solodrai@...ux.dev, linux-kernel@...r.kernel.org, bpf@...r.kernel.org, 
	pengdonglin <pengdonglin@...omi.com>, Alan Maguire <alan.maguire@...cle.com>
Subject: Re: [PATCH bpf-next v10 05/13] libbpf: Verify BTF Sorting

On Tue, Jan 6, 2026 at 7:45 PM Donglin Peng <dolinux.peng@...il.com> wrote:
>
> On Sat, Dec 20, 2025 at 10:36 PM Donglin Peng <dolinux.peng@...il.com> wrote:
> >
> >
> >
> > On Sat, Dec 20, 2025 at 1:33 AM Andrii Nakryiko <andrii.nakryiko@...il.com> wrote:
> > >
> > > On Thu, Dec 18, 2025 at 9:06 PM Donglin Peng <dolinux.peng@...il.com> wrote:
> > > >
> > > > On Fri, Dec 19, 2025 at 7:44 AM Andrii Nakryiko
> > > > <andrii.nakryiko@...il.com> wrote:
> > > > >
> > > > > On Thu, Dec 18, 2025 at 3:31 AM Donglin Peng <dolinux.peng@...il.com> wrote:
> > > > > >
> > > > > > From: pengdonglin <pengdonglin@...omi.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@...il.com>
> > > > > > Cc: Alexei Starovoitov <ast@...nel.org>
> > > > > > Cc: Andrii Nakryiko <andrii.nakryiko@...il.com>
> > > > > > Cc: Alan Maguire <alan.maguire@...cle.com>
> > > > > > Cc: Ihor Solodrai <ihor.solodrai@...ux.dev>
> > > > > > Cc: Xiaoqin Zhang <zhangxiaoqin@...omi.com>
> > > > > > Signed-off-by: pengdonglin <pengdonglin@...omi.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.
> > > >
> > >
> > > Look, I don't know how to emphasize this enough. Any special case like
> > > this is nothing good, it adds more cases to consider and raises
> > > questions why generic case code doesn't handle such special cases. It
> > > implies that generic case handling might have some unhandled corner
> > > case that we are trying to short-circuit with early exits like this.
> > > It just basically means we don't trust our code, in a sense. It's just
> > > unnecessary and thus sloppy. Don't do this unnecessarily.
> >
> > Thank you for taking the time to explain this so clearly. I’m grateful for
> > your patience in pushing for rigor — it’s exactly the kind of scrutiny that
> > makes the codebase stronger. I’ll make sure to apply this lesson in future
> > revisions.
> >
> > >
> > > > >
> > > > > > +
> > > > > > +       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.
> > >
> > > Ah, right, we'd need to reset btf->sorted_start_id to zero in that
> > > strcmp(n1, n2) > 0 branch. Using btf->sorted_start_id directly is not
> > > the main point here, though, feel free to use a local variable, but
> > > don't add unnecessary helper functions which don't do much, but
> > > obscure the logic unnecessarily.
> >
> > Thanks, I will use a local variable and remove the helper functions.
>
> Hi Andrii,
>
> I noticed that the code above does not handle the scenario where
> only the last btf_typein a sorted BTF has a name. So I've added an
> additional check in the loop as follows:
>
> static void btf_check_sorted(struct btf *btf)
> {
>         __u32 i, n, named_start_id = 0;
>
>         n = btf__type_cnt(btf);
>         for (i = btf->start_id + 1; i < n; i++) {
>                 struct btf_type *ta = btf_type_by_id(btf, i - 1);
>                 struct btf_type *tb = btf_type_by_id(btf, i);
>                 const char *na = btf__str_by_offset(btf, ta->name_off);
>                 const char *nb = btf__str_by_offset(btf, tb->name_off);
>
>                 if (strcmp(na, nb) > 0)
>                         return;
>
>                 if (named_start_id == 0) {
>                         if (na[0] != '\0')
>                                 named_start_id = i - 1;
>                         else if (i == (n - 1) && nb[0] != '\0') /*
> only the last one has a name */
>                                 named_start_id = i;
>                 }

good observation!

How about a bit more uniform way?

if (named_start_id == 0 && na[0] != '\0')
    named_start_id = i - 1;
if (named_start_id == 0 && nb[0] != '\0')
    named_start_id = i;


less nested conditions, and code clearly says that we pick earliest
non-anon type in a comparison pair as named_start_id

>         }
>
>         if (named_start_id)
>                 btf->named_start_id = named_start_id;
> }
>
> WDYT?
>
> >
> > >
> > > >
> > > > >
> > > > >
> > > > > 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
> > > > > >

Powered by blists - more mailing lists