linux-kernel - Re: [RFC PATCH v4 5/7] 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: <CAADnVQKxqScrBhTKOXcwSL_mVXE36YQ_yQX7qwg8C3X1ZnXHnA@mail.gmail.com>
Date: Tue, 4 Nov 2025 09:14:46 -0800
From: Alexei Starovoitov <alexei.starovoitov@...il.com>
To: Donglin Peng <dolinux.peng@...il.com>
Cc: Alexei Starovoitov <ast@...nel.org>, LKML <linux-kernel@...r.kernel.org>, 
	bpf <bpf@...r.kernel.org>, Eduard Zingerman <eddyz87@...il.com>, 
	Andrii Nakryiko <andrii.nakryiko@...il.com>, Alan Maguire <alan.maguire@...cle.com>, 
	Song Liu <song@...nel.org>, pengdonglin <pengdonglin@...omi.com>
Subject: Re: [RFC PATCH v4 5/7] btf: Optimize type lookup with binary search

On Tue, Nov 4, 2025 at 5:41 AM Donglin Peng <dolinux.peng@...il.com> wrote:
>
> From: pengdonglin <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: Song Liu <song@...nel.org>
> Signed-off-by: pengdonglin <pengdonglin@...omi.com>
> Signed-off-by: Donglin Peng <dolinux.peng@...il.com>
> ---
>  kernel/bpf/btf.c | 111 ++++++++++++++++++++++++++++++++++++++++++-----
>  1 file changed, 101 insertions(+), 10 deletions(-)
>
> diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c
> index 0de8fc8a0e0b..da35d8636b9b 100644
> --- a/kernel/bpf/btf.c
> +++ b/kernel/bpf/btf.c
> @@ -259,6 +259,7 @@ struct btf {
>         void *nohdr_data;
>         struct btf_header hdr;
>         u32 nr_types; /* includes VOID for base BTF */
> +       u32 nr_sorted_types; /* exclude VOID for base BTF */
>         u32 types_size;
>         u32 data_size;
>         refcount_t refcnt;
> @@ -494,6 +495,11 @@ static bool btf_type_is_modifier(const struct btf_type *t)
>         return false;
>  }
>
> +static int btf_start_id(const struct btf *btf)
> +{
> +       return btf->start_id + (btf->base_btf ? 0 : 1);
> +}
> +
>  bool btf_type_is_void(const struct btf_type *t)
>  {
>         return t == &btf_void;
> @@ -544,24 +550,109 @@ u32 btf_nr_types(const struct btf *btf)
>         return total;
>  }
>
> -s32 btf_find_by_name_kind(const struct btf *btf, const char *name, u8 kind)
> +/* 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_by_name_kind_bsearch(const struct btf *btf, const char *name,
> +                                               s32 *left, s32 *right)
>  {
>         const struct btf_type *t;
>         const char *tname;
> -       u32 i, total;
> +       s32 l, r, m, lmost, rmost;
> +       int ret;
>
> -       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;
> +       /* found the leftmost btf_type that matches */
> +       l = *left;
> +       r = *right;
> +       lmost = -1;
> +       while (l <= r) {
> +               m = l + (r - l) / 2;
> +               t = btf_type_by_id(btf, m);
> +               tname = btf_name_by_offset(btf, t->name_off);
> +               ret = strcmp(tname, name);
> +               if (ret < 0) {
> +                       l = m + 1;
> +               } else {
> +                       if (ret == 0)
> +                               lmost = m;
> +                       r = m - 1;
> +               }
> +       }
>
> +       if (lmost == -1)
> +               return -ENOENT;
> +
> +       /* found the rightmost btf_type that matches */
> +       l = lmost;
> +       r = *right;
> +       rmost = -1;
> +       while (l <= r) {
> +               m = l + (r - l) / 2;
> +               t = btf_type_by_id(btf, m);
>                 tname = btf_name_by_offset(btf, t->name_off);
> -               if (!strcmp(tname, name))
> -                       return i;
> +               ret = strcmp(tname, name);
> +               if (ret <= 0) {
> +                       if (ret == 0)
> +                               rmost = m;
> +                       l = m + 1;
> +               } else {
> +                       r = m - 1;
> +               }
>         }
>
> -       return -ENOENT;
> +       *left = lmost;
> +       *right = rmost;
> +       return lmost;
> +}
> +
> +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;
> +       int err = -ENOENT;
> +
> +       if (base_btf)
> +               err = btf_find_by_name_kind(base_btf, name, kind);
> +
> +       if (err == -ENOENT) {

Please avoid the needless indent.

> +               if (btf->nr_sorted_types) {

looks buggy,
since you init it to btf->nr_sorted_types = BTF_NEED_SORT_CHECK;

Also AI is right. Init the field in the same patch.

pw-bot: cr