linux-kernel - Re: [RFC PATCH v7 4/7] 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: <CAErzpmsFpK47tdJ4GvwR_T1c5ie31LNwNY7ED9LReLYCbHxJTA@mail.gmail.com>
Date: Thu, 20 Nov 2025 15:41:42 +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, 
	linux-kernel@...r.kernel.org, bpf@...r.kernel.org, 
	Donglin Peng <pengdonglin@...omi.com>, Alan Maguire <alan.maguire@...cle.com>, 
	Song Liu <song@...nel.org>
Subject: Re: [RFC PATCH v7 4/7] libbpf: Optimize type lookup with binary
 search for sorted BTF

On Thu, Nov 20, 2025 at 3:47 AM Andrii Nakryiko
<andrii.nakryiko@...il.com> wrote:
>
> On Tue, Nov 18, 2025 at 7:21 PM 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 type names. For unsorted BTF
> > or when nr_sorted_types is zero, the implementation falls back to
> > the original linear search algorithm.
> >
> > 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: Song Liu <song@...nel.org>
> > Cc: Xiaoqin Zhang <zhangxiaoqin@...omi.com>
> > Signed-off-by: Donglin Peng <pengdonglin@...omi.com>
> > ---
> >  tools/lib/bpf/btf.c | 104 ++++++++++++++++++++++++++++++++++----------
> >  1 file changed, 81 insertions(+), 23 deletions(-)
> >
>
> [...]
>
> > +       const struct btf_type *t;
> > +       const char *tname;
> > +       int err = -ENOENT;
> > +
> > +       if (start_id < btf->start_id) {
> > +               err = btf_find_type_by_name_kind(btf->base_btf, start_id,
> > +                       type_name, kind);
>
> nit: align wrapped args on the second line
>
> also, we expect that err will be set to -ENOENT if we didn't find a
> match in the base BTF, right? I'm a bit uneasy about this, I'd rather
> do explicit err = -ENOENT setting for each goto out

Thanks, I will refactor it.

>
> > +               if (err > 0)
> > +                       goto out;
> > +               start_id = btf->start_id;
> > +       }
> > +
> > +       if (btf->nr_sorted_types > 0) {
> > +               /* binary search */
> > +               __s32 end_id;
> > +               int idx;
> > +
> > +               end_id = btf->start_id + btf->nr_sorted_types - 1;
> > +               idx = btf_find_type_by_name_bsearch(btf, type_name, start_id, end_id);
> > +               for (; 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))
>
> nit: please add explicit != 0 here

Thanks. I will fix it.

>
> also, why not just `return -ENOENT;`?

I thought about that, but I feel the function should return from
one place. Frankly, just returning -ENOENT is cleaner

>
> > +                               goto out;
> > +                       if (kind == -1 || btf_kind(t) == kind)
> > +                               return idx;
> > +               }
> > +       } else {
> > +               /* linear search */
> > +               __u32 i, total;
> >
> > -               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))
>
> nit: let's do explicit == 0 for strcmp, please

Thanks, I will fix it.

>
> > +                               return i;
> > +               }
> >         }
> >
> > -       return libbpf_err(-ENOENT);
> > +out:
> > +       return err;
> >  }
> >
> >  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);
> > -
> >         if (kind == BTF_KIND_UNKN || !strcmp(type_name, "void"))
> >                 return 0;
>
> this is the only thing that btf_find_by_name_kind() does on top of
> what btf_find_type_by_name_kind(), right? Any reason we can't merge
> those and keep only btf_find_by_name_kind()?

Thanks. The check exists in the original btf_find_by_name_kind.
Because btf_find_type_by_name_kind uses recursion, adding the
check there would cause it to run multiple times. I'm open to merging
the functions if the overhead is acceptable.

>
> >
> > -       for (i = start_id; i < nr_types; i++) {
> > -               const struct btf_type *t = btf__type_by_id(btf, i);
> > -               const char *name;
> > -
> > -               if (btf_kind(t) != kind)
> > -                       continue;
> > -               name = btf__name_by_offset(btf, t->name_off);
> > -               if (name && !strcmp(type_name, name))
> > -                       return i;
> > -       }
> > +       return libbpf_err(btf_find_type_by_name_kind(btf, start_id, type_name, kind));
> > +}
> >
>
> [...]