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] [thread-next>] [day] [month] [year] [list]

Message-ID: <CAEf4BzaT0RR=iVpgnBOXQpHN++6Soz4ECAYex6bpd2zficSCRQ@mail.gmail.com>
Date: Wed, 19 Nov 2025 11:47:38 -0800
From: Andrii Nakryiko <andrii.nakryiko@...il.com>
To: Donglin Peng <dolinux.peng@...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 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

> +               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

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

> +                               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

> +                               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()?

>
> -       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));
> +}
>

[...]