Re: [PATCH bpf-next v10 06/13] btf: Optimize type lookup with binary search

[Donglin Peng]

On Fri, Dec 19, 2025 at 5:38 AM Eduard Zingerman <eddyz87@xxxxxxxxx> wrote:
>
> On Thu, 2025-12-18 at 19:30 +0800, Donglin Peng wrote:
> > From: pengdonglin <pengdonglin@xxxxxxxxxx>
> >
> > 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@xxxxxxxxx>
> > Cc: Alexei Starovoitov <ast@xxxxxxxxxx>
> > Cc: Andrii Nakryiko <andrii.nakryiko@xxxxxxxxx>
> > Cc: Alan Maguire <alan.maguire@xxxxxxxxxx>
> > Cc: Ihor Solodrai <ihor.solodrai@xxxxxxxxx>
> > Cc: Xiaoqin Zhang <zhangxiaoqin@xxxxxxxxxx>
> > Signed-off-by: pengdonglin <pengdonglin@xxxxxxxxxx>
> > ---
>
> (One nit below).
>
> Acked-by: Eduard Zingerman <eddyz87@xxxxxxxxx>
>
> >  kernel/bpf/btf.c | 85 +++++++++++++++++++++++++++++++++++++++++++-----
> >  1 file changed, 76 insertions(+), 9 deletions(-)
> >
> > diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c
> > index 0de8fc8a0e0b..0394f0c8ef74 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 sorted_start_id;
> >       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,21 +550,79 @@ u32 btf_nr_types(const struct btf *btf)
> >       return total;
> >  }
> >
> > +static s32 btf_find_by_name_bsearch(const struct btf *btf, const char *name,
> > +                                 s32 start_id, s32 end_id)
> > +{
> > +     const struct btf_type *t;
> > +     const char *tname;
> > +     s32 l, r, m, lmost = -ENOENT;
> > +     int ret;
> > +
> > +     l = start_id;
> > +     r = end_id;
> > +     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;
> > +             }
> > +     }
> > +
> > +     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;
> > -     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->sorted_start_id > 0 && name[0]) {
>             ^^^^^^^^^^^^^^^^^^^^^^^^
> Nit: Maybe pull the is_sorted helper into this patch-set?

Thanks, will do it.

>
> > +             /* skip anonymous types */
> > +             s32 start_id = btf->sorted_start_id;
> > +             s32 end_id = btf_nr_types(btf) - 1;
> > +
> > +             idx = btf_find_by_name_bsearch(btf, name, start_id, end_id);
> > +             if (idx < 0)
> > +                     return -ENOENT;
> > +
> > +             t = btf_type_by_id(btf, idx);
> > +             if (BTF_INFO_KIND(t->info) == kind)
> > +                     return idx;
> > +
> > +             for (idx++; idx <= end_id; idx++) {
> > +                     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;
> > +             }
> > +     } else {
> > +             u32 i, total;
> > +
> > +             total = btf_nr_types(btf);
> > +             for (i = btf_start_id(btf); i < total; i++) {
> > +                     t = btf_type_by_id(btf, i);
> > +                     if (BTF_INFO_KIND(t->info) != kind)
> > +                             continue;
> > +                     tname = btf_name_by_offset(btf, t->name_off);
> > +                     if (strcmp(tname, name) == 0)
> > +                             return i;
> > +             }
> >       }
> >
> >       return -ENOENT;
> > @@ -5791,6 +5855,7 @@ static struct btf *btf_parse(const union bpf_attr *attr, bpfptr_t uattr, u32 uat
> >               goto errout;
> >       }
> >       env->btf = btf;
> > +     btf->sorted_start_id = 0;
> >
> >       data = kvmalloc(attr->btf_size, GFP_KERNEL | __GFP_NOWARN);
> >       if (!data) {
> > @@ -6210,6 +6275,7 @@ static struct btf *btf_parse_base(struct btf_verifier_env *env, const char *name
> >       btf->data = data;
> >       btf->data_size = data_size;
> >       btf->kernel_btf = true;
> > +     btf->sorted_start_id = 0;
> >       snprintf(btf->name, sizeof(btf->name), "%s", name);
> >
> >       err = btf_parse_hdr(env);
> > @@ -6327,6 +6393,7 @@ static struct btf *btf_parse_module(const char *module_name, const void *data,
> >       btf->start_id = base_btf->nr_types;
> >       btf->start_str_off = base_btf->hdr.str_len;
> >       btf->kernel_btf = true;
> > +     btf->sorted_start_id = 0;
> >       snprintf(btf->name, sizeof(btf->name), "%s", module_name);
> >
> >       btf->data = kvmemdup(data, data_size, GFP_KERNEL | __GFP_NOWARN);