Re: [RFC PATCH v7 4/7] libbpf: Optimize type lookup with binary search for sorted BTF

[Andrii Nakryiko]

On Tue, Nov 18, 2025 at 7:21 PM Donglin Peng <dolinux.peng@xxxxxxxxx> wrote:
>
> From: Donglin Peng <pengdonglin@xxxxxxxxxx>
>
> 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@xxxxxxxxx>
> Cc: Alexei Starovoitov <ast@xxxxxxxxxx>
> Cc: Andrii Nakryiko <andrii.nakryiko@xxxxxxxxx>
> Cc: Alan Maguire <alan.maguire@xxxxxxxxxx>
> Cc: Song Liu <song@xxxxxxxxxx>
> Cc: Xiaoqin Zhang <zhangxiaoqin@xxxxxxxxxx>
> Signed-off-by: Donglin Peng <pengdonglin@xxxxxxxxxx>
> ---
>  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));
> +}
>

[...]