linux-kernel - Re: [PATCH bpf-next v12 06/11] btf: Optimize type lookup with binary search

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: <CAEf4BzZfm=AxAC6TB_OLcKZeH=M=Z=AFftSoCZg-pJ7ChQyZYA@mail.gmail.com>
Date: Tue, 13 Jan 2026 16:29:39 -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, 
	ihor.solodrai@...ux.dev, linux-kernel@...r.kernel.org, bpf@...r.kernel.org, 
	Donglin Peng <pengdonglin@...omi.com>, Alan Maguire <alan.maguire@...cle.com>
Subject: Re: [PATCH bpf-next v12 06/11] btf: Optimize type lookup with binary search

On Fri, Jan 9, 2026 at 5:00 AM Donglin Peng <dolinux.peng@...il.com> wrote:
>
> From: Donglin Peng <pengdonglin@...omi.com>
>
> Improve btf_find_by_name_kind() performance by adding binary search
> support for sorted types. Falls back to linear search for compatibility.
>
> 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: Ihor Solodrai <ihor.solodrai@...ux.dev>
> Cc: Xiaoqin Zhang <zhangxiaoqin@...omi.com>
> Signed-off-by: Donglin Peng <pengdonglin@...omi.com>
> ---
>  include/linux/btf.h |  1 +
>  kernel/bpf/btf.c    | 91 ++++++++++++++++++++++++++++++++++++++++-----
>  2 files changed, 83 insertions(+), 9 deletions(-)
>

[...]

>  s32 btf_find_by_name_kind(const struct btf *btf, const char *name, u8 kind)
>  {
> +       const struct btf *base_btf = btf_base_btf(btf);
>         const struct btf_type *t;
>         const char *tname;
> -       u32 i, total;
> +       s32 idx;
>
> -       total = btf_nr_types(btf);
> -       for (i = 1; i < total; i++) {
> -               t = btf_type_by_id(btf, i);
> -               if (BTF_INFO_KIND(t->info) != kind)
> -                       continue;
> +       if (base_btf) {
> +               idx = btf_find_by_name_kind(base_btf, name, kind);
> +               if (idx > 0)
> +                       return idx;
> +       }
>
> -               tname = btf_name_by_offset(btf, t->name_off);
> -               if (!strcmp(tname, name))
> -                       return i;
> +       if (btf->named_start_id > 0 && name[0]) {
> +               idx = btf_find_by_name_kind_bsearch(btf, name);
> +               for (; idx < btf_nr_types(btf); idx++) {

same nit about inconsistent btf_nr_types() usage between two branches:
compute once early and use in both branches

(fixed up similarly to libbpf implementation; also fixed up comment style )

> +                       t = btf_type_by_id(btf, idx);
> +                       tname = btf_name_by_offset(btf, t->name_off);
> +                       if (strcmp(tname, name) != 0)
> +                               return -ENOENT;
> +                       if (BTF_INFO_KIND(t->info) == kind)
> +                               return idx;
> +               }

[...]