linux-kernel - Re: [PATCH bpf-next v12 04/11] 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] [day] [month] [year] [list]

Message-ID: <CAErzpmshz6pG1_0q4bH4Y2D90xZmrtR1r6AXetubaFK5JjqvgQ@mail.gmail.com>
Date: Wed, 14 Jan 2026 10:21:16 +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, 
	Donglin Peng <pengdonglin@...omi.com>, Alan Maguire <alan.maguire@...cle.com>
Subject: Re: [PATCH bpf-next v12 04/11] libbpf: Optimize type lookup with
 binary search for sorted BTF

On Wed, Jan 14, 2026 at 9:49 AM Donglin Peng <dolinux.peng@...il.com> wrote:
>
> On Wed, Jan 14, 2026 at 8:29 AM Andrii Nakryiko
> <andrii.nakryiko@...il.com> wrote:
> >
> > On Fri, Jan 9, 2026 at 5:00 AM Donglin Peng <dolinux.peng@...il.com> wrote:
> > >
> > > From: Donglin Peng <pengdonglin@...omi.com>
> > >
> > > This patch introduces binary search optimization for BTF type lookups
> > > when the BTF instance contains sorted types.
> > >
> > > The optimization significantly improves performance when searching for
> > > types in large BTF instances with sorted types. For unsorted BTF, the
> > > implementation falls back to the original linear search.
> > >
> > > 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: Donglin Peng <pengdonglin@...omi.com>
> > > ---
> > >  tools/lib/bpf/btf.c | 90 +++++++++++++++++++++++++++++++++------------
> > >  1 file changed, 66 insertions(+), 24 deletions(-)
> > >
> >
> > [...]
> >
> > >  static __s32 btf_find_by_name_kind(const struct btf *btf, int start_id,
> > > -                                  const char *type_name, __u32 kind)
> > > +                                  const char *type_name, __s32 kind)
> > >  {
> > > -       __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->named_start_id > 0 && type_name[0]) {
> > > +               start_id = max(start_id, btf->named_start_id);
> > > +               idx = btf_find_type_by_name_bsearch(btf, type_name, start_id);
> > > +               for (; idx < btf__type_cnt(btf); idx++) {
> >
> > I hope the compiler will optimize out btf__type_cnt() and won't be
> > recalculating it all the time, but I'd absolutely make sure by keeping
> > nr_types local variable which you deleted for some reason. Please
> > include in your follow up.
>
> Thanks, I will optimize it.
>
> >
> > > +                       t = btf__type_by_id(btf, idx);
> > > +                       tname = btf__str_by_offset(btf, t->name_off);
> > > +                       if (strcmp(tname, type_name) != 0)
> > > +                               return libbpf_err(-ENOENT);
> > > +                       if (kind < 0 || btf_kind(t) == kind)
> > > +                               return idx;
> > > +               }
> > > +       } else {
> > > +               __u32 i, total;
> > >
> > > -               if (btf_kind(t) != kind)
> > > -                       continue;
> > > -               name = btf__name_by_offset(btf, t->name_off);
> > > -               if (name && !strcmp(type_name, name))
> > > -                       return i;
> > > +               total = btf__type_cnt(btf);
> >
> > and here you have a local total pre-calculated. Just move it outside
> > of this if/else and use in both branches
>
> Thanks, I will fix it.
>
> >
> > (I adjusted this trivially while applying, also unified idx,i -> id

Thank you for fixing it.

>
> Thanks, I will fix it in v13.
>
> >
> >
> > > +               for (i = start_id; i < total; i++) {
> > > +                       t = btf_type_by_id(btf, i);
> > > +                       if (kind > 0 && btf_kind(t) != kind)
> > > +                               continue;
> > > +                       tname = btf__str_by_offset(btf, t->name_off);
> > > +                       if (strcmp(tname, type_name) == 0)
> > > +                               return i;
> > > +               }
> > >         }
> > >
> >
> > [...]