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: <CAErzpmt3aknKcxhbq8+=AxVJthf80-c2hFSK1RqfhwvS_9H0yg@mail.gmail.com>
Date: Wed, 17 Dec 2025 10:34:10 +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 10:32 AM Donglin Peng <dolinux.peng@...il.com> wrote:
>
> On Wed, Dec 17, 2025 at 7:38 AM Eduard Zingerman <eddyz87@...il.com> 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) {
> > > +             __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?
>
> The check for kind != -1 is unnecessary here because it has already been
> performed earlier in the logic, after btf_find_by_name_bsearch successfully
> returned a valid idx. In v8, the implementation of btf_find_by_name_bsearch
> was refined for better performance, and when idx > 0, it guarantees that the
> name has been matched.
>
> Thank you for the review.
> Donglin
>
> >
> > > +                             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.

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

> >
> > > +                             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)
> > >  {
> >
> > [...]