linux-kernel - Re: [RFC PATCH v4 3/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: <CAEf4BzaxU1ea_cVRRD9EenTusDy54tuEpbFqoDQUZVf46zdawg@mail.gmail.com>
Date: Tue, 4 Nov 2025 16:11:36 -0800
From: Andrii Nakryiko <andrii.nakryiko@...il.com>
To: Donglin Peng <dolinux.peng@...il.com>
Cc: ast@...nel.org, linux-kernel@...r.kernel.org, bpf@...r.kernel.org, 
	Eduard Zingerman <eddyz87@...il.com>, Alan Maguire <alan.maguire@...cle.com>, Song Liu <song@...nel.org>, 
	pengdonglin <pengdonglin@...omi.com>
Subject: Re: [RFC PATCH v4 3/7] libbpf: Optimize type lookup with binary
 search for sorted BTF

On Tue, Nov 4, 2025 at 5:40 AM Donglin Peng <dolinux.peng@...il.com> wrote:
>
> From: pengdonglin <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>
> Signed-off-by: pengdonglin <pengdonglin@...omi.com>
> Signed-off-by: Donglin Peng <dolinux.peng@...il.com>
> ---
>  tools/lib/bpf/btf.c | 142 +++++++++++++++++++++++++++++++++++++-------
>  1 file changed, 119 insertions(+), 23 deletions(-)
>
> diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c
> index 3bc03f7fe31f..5af14304409c 100644
> --- a/tools/lib/bpf/btf.c
> +++ b/tools/lib/bpf/btf.c
> @@ -92,6 +92,12 @@ struct btf {
>          *   - for split BTF counts number of types added on top of base BTF.
>          */
>         __u32 nr_types;
> +       /* number of sorted and named types in this BTF instance:
> +        *   - doesn't include special [0] void type;
> +        *   - for split BTF counts number of sorted and named types added on
> +        *     top of base BTF.
> +        */
> +       __u32 nr_sorted_types;

we don't need to know the count of sorted types, all we need is a
tristate value: a) data is sorted, b) data is not sorted, c) we don't
know yet. And zero should be treated as "we don't know yet". This is
trivial to do with an enum.

>         /* if not NULL, points to the base BTF on top of which the current
>          * split BTF is based
>          */
> @@ -897,44 +903,134 @@ int btf__resolve_type(const struct btf *btf, __u32 type_id)
>         return type_id;
>  }
>
> -__s32 btf__find_by_name(const struct btf *btf, const char *type_name)
> +/*
> + * Find BTF types with matching names within the [left, right] index range.
> + * On success, updates *left and *right to the boundaries of the matching range
> + * and returns the leftmost matching index.
> + */
> +static __s32 btf_find_type_by_name_bsearch(const struct btf *btf, const char *name,
> +                                               __s32 *left, __s32 *right)

I thought we discussed this, why do you need "right"? Two binary
searches where one would do just fine.


Also this isn't quite the same approach as in find_linfo() in
kernel/bpf/log.c, that one doesn't have extra ret == 0 condition

pw-bot: cr

>  {
> -       __u32 i, nr_types = btf__type_cnt(btf);
> +       const struct btf_type *t;
> +       const char *tname;
> +       __s32 l, r, m, lmost, rmost;
> +       int ret;
> +

[...]