| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Message-ID: <CAEf4BzY=3KWxZ1F98sE-zB0g-HKz87HJ5msBYESZ0Ri0jN=WCg@mail.gmail.com>
Date: Fri, 19 Dec 2025 09:33:33 -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 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.
> >
> > > +
> > > + 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.
>
> >
> >
> > 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