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: <CAErzpmtLMd6pS9OfeS1=_VTyUqPNfNa4J7d1m_ydC=u4_k8Cbw@mail.gmail.com>
Date: Wed, 17 Dec 2025 10:32:55 +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: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.
>
> > +                             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)
> >  {
>
> [...]