Message-ID: <CAErzpmv99TG_pjyjcQd5xjC7M+yUGs6SNtL9b3nJQAC8z-nafw@mail.gmail.com>
Date: Wed, 7 Jan 2026 11:45:29 +0800
From: Donglin Peng <dolinux.peng@...il.com>
To: Andrii Nakryiko <andrii.nakryiko@...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 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;
                }
        }

        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