linux-kernel - Re: [PATCH bpf-next v10 04/13] 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: <CAEf4BzbbRP6ftHE0q5cDLJ9EhaSP+Ssy7rMJjFSn2GDrSL8O-Q@mail.gmail.com>
Date: Thu, 18 Dec 2025 17:01:27 -0800
From: Andrii Nakryiko <andrii.nakryiko@...il.com>
To: Eduard Zingerman <eddyz87@...il.com>
Cc: Donglin Peng <dolinux.peng@...il.com>, ast@...nel.org, 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 04/13] libbpf: Optimize type lookup with
 binary search for sorted BTF

On Thu, Dec 18, 2025 at 4:25 PM Eduard Zingerman <eddyz87@...il.com> wrote:
>
> On Thu, 2025-12-18 at 16:19 -0800, Andrii Nakryiko wrote:
> > On Thu, Dec 18, 2025 at 4:13 PM Eduard Zingerman <eddyz87@...il.com> wrote:
> > >
> > > On Thu, 2025-12-18 at 15:29 -0800, Andrii Nakryiko wrote:
> > >
> > > [...]
> > >
> > > > >  static __s32 btf_find_by_name_kind(const struct btf *btf, int start_id,
> > > > >                                    const char *type_name, __u32 kind)
> > > >
> > > > kind is defined as u32 but you expect caller to pass -1 to ignore the
> > > > kind. Use int here.
> > > >
> > > > >  {
> > > > > -       __u32 i, nr_types = btf__type_cnt(btf);
> > > > > +       const struct btf_type *t;
> > > > > +       const char *tname;
> > > > > +       __s32 idx;
> > > > > +
> > > > > +       if (start_id < btf->start_id) {
> > > > > +               idx = btf_find_by_name_kind(btf->base_btf, start_id,
> > > > > +                                           type_name, kind);
> > > > > +               if (idx >= 0)
> > > > > +                       return idx;
> > > > > +               start_id = btf->start_id;
> > > > > +       }
> > > > >
> > > > > -       if (kind == BTF_KIND_UNKN || !strcmp(type_name, "void"))
> > > > > +       if (kind == BTF_KIND_UNKN || strcmp(type_name, "void") == 0)
> > > > >                 return 0;
> > > > >
> > > > > -       for (i = start_id; i < nr_types; i++) {
> > > > > -               const struct btf_type *t = btf__type_by_id(btf, i);
> > > > > -               const char *name;
> > > > > +       if (btf->sorted_start_id > 0 && type_name[0]) {
> > > > > +               __s32 end_id = btf__type_cnt(btf) - 1;
> > > > > +
> > > > > +               /* skip anonymous types */
> > > > > +               start_id = max(start_id, btf->sorted_start_id);
> > > >
> > > > can sorted_start_id ever be smaller than start_id?
> > >
> > > sorted_start_id can be zero, at two callsites for this function
> > > start_id is passed as btf->start_id and 1.
> >
> > Can it with the check above?
> >
> >   if (btf->sorted_start_id > 0 && type_name[0]) {
> >
> >
> > This branch is a known sorted case. That's why all these start_id
> > manipulations look weird and sloppy.
>
> Oops, it cannot.
> But still it feels strange to pass a 'start_id' parameter to a
> function and rely at exact values passed at callsites. Replace the
> parameter with boolean 'own'?

hm.. looking around a bit more, it seems like passed-in start_id might
be useful for iterator-like searches. We don't use that right now, but
maybe we should preserve this behavior? And then max() does make sense
(though "skip anonymous types" is a bit too brief, I'd mention that
start_id might be within the named types intentionally and we need to
jump forward)

>
> > >
> > > >
> > > > > +               idx = btf_find_by_name_bsearch(btf, type_name, start_id, end_id);
> > > >
> > > > is there ever a time when btf_find_by_name_bsearch() will work with
> > > > different start_id and end_id? why is this not done inside the
> > > > btf_find_by_name_bsearch()?
> > > >
> > >
> > > [...]