linux-kernel - Re: [RFC PATCH v7 4/7] libbpf: Optimize type lookup with binary search for sorted BTF

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

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <CAErzpmssZXDx_beSbxVpNnJBM+uQEx0HMUxMLi=DUy-RkM8oAg@mail.gmail.com>
Date: Wed, 19 Nov 2025 12:43:40 +0800
From: Donglin Peng <dolinux.peng@...il.com>
To: bot+bpf-ci@...nel.org
Cc: ast@...nel.org, andrii.nakryiko@...il.com, eddyz87@...il.com, 
	zhangxiaoqin@...omi.com, linux-kernel@...r.kernel.org, bpf@...r.kernel.org, 
	pengdonglin@...omi.com, alan.maguire@...cle.com, song@...nel.org, 
	andrii@...nel.org, daniel@...earbox.net, martin.lau@...nel.org, 
	yonghong.song@...ux.dev, clm@...a.com, ihor.solodrai@...ux.dev
Subject: Re: [RFC PATCH v7 4/7] libbpf: Optimize type lookup with binary
 search for sorted BTF

On Wed, Nov 19, 2025 at 12:11 PM <bot+bpf-ci@...nel.org> wrote:
>
> > diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c
> > index 71d464690..555703b37 100644
> > --- a/tools/lib/bpf/btf.c
> > +++ b/tools/lib/bpf/btf.c
>
> [ ... ]
>
> > @@ -897,44 +903,93 @@ int btf__resolve_type(const struct btf *btf, __u32 type_id)
> >       return type_id;
> >  }
> >
> > -__s32 btf__find_by_name(const struct btf *btf, const char *type_name)
> > +static __s32 btf_find_type_by_name_bsearch(const struct btf *btf, const char *name,
> > +                                             __s32 start_id, __s32 end_id)
> >  {
> > -     __u32 i, nr_types = btf__type_cnt(btf);
> > +     const struct btf_type *t;
> > +     const char *tname;
> > +     __s32 l, r, m;
> > +
> > +     l = start_id;
> > +     r = end_id;
> > +     while (l <= r) {
> > +             m = l + (r - l) / 2;
> > +             t = btf_type_by_id(btf, m);
> > +             tname = btf__str_by_offset(btf, t->name_off);
> > +             if (strcmp(tname, name) >= 0) {
>                     ^^^^^^
> Can strcmp() handle a NULL tname here? The btf__str_by_offset()
> function returns NULL when offset is out of range (line 1674 returns
> "errno = EINVAL, NULL"), but strcmp() requires non-NULL arguments.
>
> The original linear search code at line 971 checks "if (tname &&
> !strcmp(tname, type_name))" before calling strcmp(). Should the binary
> search path also check for NULL?

Thank you. It is unnecessary to check for a NULL type name in this context
because the btf_check_sorted function introduced in the subsequent patch
ensures that all types accessed via binary search have non-NULL names.

Furthermore, in the current patch, nr_sorted_types is always zero, meaning
the binary search path is never exercised.

>
> > +                     if (l == r)
> > +                             return r;
> > +                     r = m;
> > +             } else {
> > +                     l = m + 1;
> > +             }
> > +     }
> > +
> > +     return btf__type_cnt(btf);
> > +}
> > +
> > +static __s32 btf_find_type_by_name_kind(const struct btf *btf, int start_id,
> > +                                const char *type_name, __u32 kind)
> > +{
> > +     const struct btf_type *t;
> > +     const char *tname;
> > +     int err = -ENOENT;
> > +
> > +     if (start_id < btf->start_id) {
> > +             err = btf_find_type_by_name_kind(btf->base_btf, start_id,
> > +                     type_name, kind);
> > +             if (err > 0)
> > +                     goto out;
> > +             start_id = btf->start_id;
> > +     }
> > +
> > +     if (btf->nr_sorted_types > 0) {
> > +             /* binary search */
> > +             __s32 end_id;
> > +             int idx;
> > +
> > +             end_id = btf->start_id + btf->nr_sorted_types - 1;
> > +             idx = btf_find_type_by_name_bsearch(btf, type_name, start_id, end_id);
> > +             for (; idx <= end_id; idx++) {
> > +                     t = btf__type_by_id(btf, idx);
> > +                     tname = btf__str_by_offset(btf, t->name_off);
> > +                     if (strcmp(tname, type_name))
>                             ^^^^^^
> Same question here - can tname be NULL at this point?

Ditto.

>
> > +                             goto out;
> > +                     if (kind == -1 || btf_kind(t) == kind)
> > +                             return idx;
> > +             }
> > +     } else {
> > +             /* linear search */
> > +             __u32 i, total;
> > +
> > +             total = btf__type_cnt(btf);
> > +             for (i = start_id; i < total; i++) {
> > +                     t = btf_type_by_id(btf, i);
> > +                     if (kind != -1 && btf_kind(t) != kind)
> > +                             continue;
> > +                     tname = btf__str_by_offset(btf, t->name_off);
> > +                     if (tname && !strcmp(tname, type_name))
> > +                             return i;
> > +             }
> > +     }
>
> [ ... ]
>
>
> ---
> AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
> See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md
>
> CI run summary: https://github.com/kernel-patches/bpf/actions/runs/19488781158