linux-kernel - Re: [PATCH bpf-next v9 04/10] 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: <CAErzpmuNbJo0z_Bij_3Eejury=0pXWRb=dOMiKxK-xv7=DYWhA@mail.gmail.com>
Date: Wed, 17 Dec 2025 10:46:58 +0800
From: Donglin Peng <dolinux.peng@...il.com>
To: Eduard Zingerman <eddyz87@...il.com>
Cc: ast@...nel.org, andrii.nakryiko@...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 v9 04/10] libbpf: Optimize type lookup with
 binary search for sorted BTF

On Wed, Dec 17, 2025 at 7:43 AM Eduard Zingerman <eddyz87@...il.com> wrote:
>
> On Tue, 2025-12-16 at 15:38 -0800, Eduard Zingerman wrote:
> > On Mon, 2025-12-08 at 14:23 +0800, Donglin Peng wrote:
> >
> > [...]
> >
> > Lgtm, one question below.
> >
> > >  static __s32 btf_find_by_name_kind(const struct btf *btf, int start_id,
> > >                                const char *type_name, __u32 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->sorted_start_id > 0) {
>             ^^^^^^^^^^^^^^^^^^^^^^^^
> Also, previous implementation worked for anonymous types, but this one
> will not work because of the 'max(start_id, btf->sorted_start_id)', right?

Yes.

> Maybe check that type is not anonymous in the condition above?

Thanks, I will add the check in the next version.

>
> > > +           __s32 end_id = btf__type_cnt(btf) - 1;
> > > +
> > > +           /* skip anonymous types */
> > > +           start_id = max(start_id, btf->sorted_start_id);
> > > +           idx = btf_find_by_name_bsearch(btf, type_name, start_id, end_id);
> > > +           if (unlikely(idx < 0))
> > > +                   return libbpf_err(-ENOENT);
> > > +
> > > +           if (unlikely(kind == -1))
> > > +                   return idx;
> > > +
> > > +           t = btf_type_by_id(btf, idx);
> > > +           if (likely(BTF_INFO_KIND(t->info) == kind))
> > > +                   return idx;
> > > +
> > > +           for (idx++; 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) != 0)
> > > +                           return libbpf_err(-ENOENT);
> > > +                   if (btf_kind(t) == kind)
> >                             ^^^^^^^^^^^^^^^^^^^
> >                 Is kind != -1 check missing here?
> >
> > > +                           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);
> > > +           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) == 0)
> >
> > Nit: no need for `tname &&` part, as we found out.
> >
> > > +                           return i;
> > > +           }
> > >     }
> > >
> > >     return libbpf_err(-ENOENT);
> > >  }
> > >
> > > +/* the kind value of -1 indicates that kind matching should be skipped */
> > > +__s32 btf__find_by_name(const struct btf *btf, const char *type_name)
> > > +{
> > > +   return btf_find_by_name_kind(btf, btf->start_id, type_name, -1);
> > > +}
> > > +
> > >  __s32 btf__find_by_name_kind_own(const struct btf *btf, const char *type_name,
> > >                              __u32 kind)
> > >  {
> >
> > [...]