Message-ID: <CAErzpmusyOMQTcoWiT7nNa=gOAOHgdRYqVb+Dc24BaqjzzeRYw@mail.gmail.com>
Date: Fri, 19 Dec 2025 13:06:09 +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 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.

>
> > +
> > +       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.

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