Message-ID: <CAEf4BzbSMwW4es5D9i=bpSjALo8u+oW-9vdQ7=DBoTBtMoJ1Tg@mail.gmail.com>
Date: Thu, 18 Dec 2025 15:29: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, 
	ihor.solodrai@...ux.dev, linux-kernel@...r.kernel.org, bpf@...r.kernel.org, 
	pengdonglin <pengdonglin@...omi.com>, Alan Maguire <alan.maguire@...cle.com>
Subject: Re: [PATCH bpf-next v10 04/13] libbpf: Optimize type lookup with
 binary search for sorted BTF

On Thu, Dec 18, 2025 at 3:31 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 types. For unsorted BTF, the
> implementation falls back to the original linear search.
>
> 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: pengdonglin <pengdonglin@...omi.com>
> ---
>  tools/lib/bpf/btf.c | 103 ++++++++++++++++++++++++++++++++++----------
>  1 file changed, 80 insertions(+), 23 deletions(-)
>

[...]

> +       l = start_id;
> +       r = end_id;
> +       while (l <= r) {
> +               m = l + (r - l) / 2;
> +               t = btf_type_by_id(btf, m);
> +               tname = btf__str_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;
> +               }
>         }

this differs from what we discussed in [0], you said you'll use that
approach. Can you please elaborate on why you didn't?

  [0] https://lore.kernel.org/bpf/CAEf4Bzb3Eu0J83O=Y4KA-LkzBMjtx7cbonxPzkiduzZ1Pedajg@mail.gmail.com/

>
> -       return libbpf_err(-ENOENT);
> +       return lmost;
>  }
>
>  static __s32 btf_find_by_name_kind(const struct btf *btf, int start_id,
>                                    const char *type_name, __u32 kind)

kind is defined as u32 but you expect caller to pass -1 to ignore the
kind. Use int here.

>  {
> -       __u32 i, nr_types = btf__type_cnt(btf);
> +       const struct btf_type *t;
> +       const char *tname;
> +       __s32 idx;
> +
> +       if (start_id < btf->start_id) {
> +               idx = btf_find_by_name_kind(btf->base_btf, start_id,
> +                                           type_name, kind);
> +               if (idx >= 0)
> +                       return idx;
> +               start_id = btf->start_id;
> +       }
>
> -       if (kind == BTF_KIND_UNKN || !strcmp(type_name, "void"))
> +       if (kind == BTF_KIND_UNKN || strcmp(type_name, "void") == 0)
>                 return 0;
>
> -       for (i = start_id; i < nr_types; i++) {
> -               const struct btf_type *t = btf__type_by_id(btf, i);
> -               const char *name;
> +       if (btf->sorted_start_id > 0 && type_name[0]) {
> +               __s32 end_id = btf__type_cnt(btf) - 1;
> +
> +               /* skip anonymous types */
> +               start_id = max(start_id, btf->sorted_start_id);

can sorted_start_id ever be smaller than start_id?

> +               idx = btf_find_by_name_bsearch(btf, type_name, start_id, end_id);

is there ever a time when btf_find_by_name_bsearch() will work with
different start_id and end_id? why is this not done inside the
btf_find_by_name_bsearch()?

> +               if (unlikely(idx < 0))
> +                       return libbpf_err(-ENOENT);

pass through error returned from btf_find_by_name_bsearch(), why redefining it?

> +
> +               if (unlikely(kind == -1))
> +                       return idx;
> +
> +               t = btf_type_by_id(btf, idx);
> +               if (likely(BTF_INFO_KIND(t->info) == kind))

use btf_kind(), but this whole extra check is just unnecessary, this
should be done in the loop below. We talked about all this already,
why do I feel like I'm being ignored?..

> +                       return idx;

drop all these likely and unlikely micro optimizations, please


> +
> +               for (idx++; 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) != 0)
> +                               return libbpf_err(-ENOENT);
> +                       if (btf_kind(t) == kind)
> +                               return idx;
> +               }
> +       } else {
> +               __u32 i, total;
>
> -               if (btf_kind(t) != kind)
> -                       continue;
> -               name = btf__name_by_offset(btf, t->name_off);
> -               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)

nit: kind < 0, no need to hard-code -1

> +                               continue;
> +                       tname = btf__str_by_offset(btf, t->name_off);
> +                       if (strcmp(tname, type_name) == 0)
> +                               return i;
> +               }
>         }
>
>         return libbpf_err(-ENOENT);
>  }
>

[...]

Powered by blists - more mailing lists