Message-ID: <CAErzpmtJq5Qqdvy+9B8WmvZFQxDt6jKidNqtTMezesP0b=K8ZA@mail.gmail.com>
Date: Thu, 6 Nov 2025 15:49:18 +0800
From: Donglin Peng <dolinux.peng@...il.com>
To: Andrii Nakryiko <andrii.nakryiko@...il.com>
Cc: Eduard Zingerman <eddyz87@...il.com>, ast@...nel.org, linux-kernel@...r.kernel.org, 
	bpf@...r.kernel.org, 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 Thu, Nov 6, 2025 at 2:11 AM Andrii Nakryiko
<andrii.nakryiko@...il.com> wrote:
>
> On Wed, Nov 5, 2025 at 5:48 AM Donglin Peng <dolinux.peng@...il.com> wrote:
> >
> > On Wed, Nov 5, 2025 at 9:17 AM Eduard Zingerman <eddyz87@...il.com> wrote:
> > >
> > > On Tue, 2025-11-04 at 16:54 -0800, Andrii Nakryiko wrote:
> > > > On Tue, Nov 4, 2025 at 4:19 PM Eduard Zingerman <eddyz87@...il.com> wrote:
> > > > >
> > > > > On Tue, 2025-11-04 at 16:11 -0800, Andrii Nakryiko wrote:
> > > > >
> > > > > [...]
> > > > >
> > > > > > > @@ -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.
> > > > >
> > > > > I think the idea is that there would be less strcmp's if there is a
> > > > > long sequence of items with identical names.
> > > >
> > > > Sure, it's a tradeoff. But how long is the set of duplicate name
> > > > entries we expect in kernel BTF? Additional O(logN) over 70K+ types
> > > > with high likelihood will take more comparisons.
> > >
> > > $ bpftool btf dump file vmlinux | grep '^\[' | awk '{print $3}' | sort | uniq -c | sort -k1nr | head
> > >   51737 '(anon)'
> > >     277 'bpf_kfunc'
> > >       4 'long
> > >       3 'perf_aux_event'
> > >       3 'workspace'
> > >       2 'ata_acpi_gtm'
> > >       2 'avc_cache_stats'
> > >       2 'bh_accounting'
> > >       2 'bp_cpuinfo'
> > >       2 'bpf_fastcall'
> > >
> > > 'bpf_kfunc' is probably for decl_tags.
> > > So I agree with you regarding the second binary search, it is not
> > > necessary.  But skipping all anonymous types (and thus having to
> > > maintain nr_sorted_types) might be useful, on each search two
> > > iterations would be wasted to skip those.
>
> fair enough, eliminating a big chunk of anonymous types is useful, let's do this
>
> >
> > Thank you. After removing the redundant iterations, performance increased
> > significantly compared with two iterations.
> >
> > Test Case: Locate all 58,719 named types in vmlinux BTF
> > Methodology:
> > ./vmtest.sh -- ./test_progs -t btf_permute/perf -v
> >
> > Two iterations:
> > | Condition          | Lookup Time | Improvement |
> > |--------------------|-------------|-------------|
> > | Unsorted (Linear)  | 17,282 ms   | Baseline    |
> > | Sorted (Binary)    | 19 ms       | 909x faster |
> >
> > One iteration:
> > Results:
> > | Condition          | Lookup Time | Improvement |
> > |--------------------|-------------|-------------|
> > | Unsorted (Linear)  | 17,619 ms   | Baseline    |
> > | Sorted (Binary)    | 10 ms       | 1762x faster |
> >
> > Here is the code implementation with a single iteration approach.
> > I believe this scenario differs from find_linfo because we cannot
> > determine in advance whether the specified type name will be found.
> > Please correct me if I've misunderstood anything, and I welcome any
> > guidance on this matter.
> >
> > static __s32 btf_find_type_by_name_bsearch(const struct btf *btf,
> > const char *name,
> >                                                 __s32 start_id)
> > {
> >         const struct btf_type *t;
> >         const char *tname;
> >         __s32 l, r, m, lmost = -ENOENT;
> >         int ret;
> >
> >         /* found the leftmost btf_type that matches */
> >         l = start_id;
> >         r = btf__type_cnt(btf) - 1;
> >         while (l <= r) {
> >                 m = l + (r - l) / 2;
> >                 t = btf_type_by_id(btf, m);
> >                 if (!t->name_off) {
> >                         ret = 1;
> >                 } else {
> >                         tname = btf__str_by_offset(btf, t->name_off);
> >                         ret = !tname ? 1 : strcmp(tname, name);
> >                 }
> >                 if (ret < 0) {
> >                         l = m + 1;
> >                 } else {
> >                         if (ret == 0)
> >                                 lmost = m;
> >                         r = m - 1;
> >                 }
> >         }
> >
> >         return lmost;
> > }
>
> There are different ways to implement this. At the highest level,
> implementation below just searches for leftmost element that has name
> >= the one we are searching for. One complication is that such element
> might not event exists. We can solve that checking ahead of time
> whether the rightmost type satisfied the condition, or we could do
> something similar to what I do in the loop below, where I allow l == r
> and then if that element has name >= to what we search, we exit
> because we found it. And if not, l will become larger than r, we'll
> break out of the loop and we'll know that we couldn't find the
> element. I haven't tested it, but please take a look and if you decide
> to go with such approach, do test it for edge cases, of course.
>
> /*
>  * We are searching for the smallest r such that type #r's name is >= name.
>  * It might not exist, in which case we'll have l == r + 1.
>  */
> l = start_id;
> r = btf__type_cnt(btf) - 1;
> while (l < r) {
>     m = l + (r - l) / 2;
>     t = btf_type_by_id(btf, m);
>     tname = btf__str_by_offset(btf, t->name_off);
>
>     if (strcmp(tname, name) >= 0) {
>         if (l == r)
>             return r; /* found it! */

It seems that this if condition will never hold, because a while(l < r) loop
is used. Moreover, even if the condition were to hold, it wouldn't guarantee
a successful search.

>         r = m;
>     } else {
>         l = m + 1;
>     }
> }
> /* here we know given element doesn't exist, return index beyond end of types */
> return btf__type_cnt(btf);

I think that return -ENOENT seems more reasonable.

>
>
> We could have checked instead whether strcmp(btf__str_by_offset(btf,
> btf__type_by_id(btf, btf__type_cnt() - 1)->name_off), name) < 0 and
> exit early. That's just a bit more code duplication of essentially
> what we do inside the loop, so that if (l == r) seems fine to me, but
> I'm not married to this.

Sorry, I believe that even if strcmp(btf__str_by_offset(btf,
btf__type_by_id(btf,
btf__type_cnt() - 1)->name_off), name) >= 0, it still doesn't seem to
guarantee that the search will definitely succeed.

>
> >
> > static __s32 btf_find_type_by_name_kind(const struct btf *btf, int start_id,
> >                                    const char *type_name, __u32 kind)
> > {
> >         const struct btf_type *t;
> >         const char *tname;
> >         int err = -ENOENT;
> >         __u32 total;
> >
> >         if (!btf)
> >                 goto out;
> >
> >         if (start_id < btf->start_id) {
> >                 err = btf_find_type_by_name_kind(btf->base_btf, start_id,
> >                                                  type_name, kind);
> >                 if (err == -ENOENT)
> >                         start_id = btf->start_id;
> >         }
> >
> >         if (err == -ENOENT) {
> >                 if (btf_check_sorted((struct btf *)btf)) {
> >                         /* binary search */
> >                         bool skip_first;
> >                         int ret;
> >
> >                         /* return the leftmost with maching names */
> >                         ret = btf_find_type_by_name_bsearch(btf,
> > type_name, start_id);
> >                         if (ret < 0)
> >                                 goto out;
> >                         /* skip kind checking */
> >                         if (kind == -1)
> >                                 return ret;
> >                         total = btf__type_cnt(btf);
> >                         skip_first = true;
> >                         do {
> >                                 t = btf_type_by_id(btf, ret);
> >                                 if (btf_kind(t) != kind) {
> >                                         if (skip_first) {
> >                                                 skip_first = false;
> >                                                 continue;
> >                                         }
> >                                 } else if (skip_first) {
> >                                         return ret;
> >                                 }
> >                                 if (!t->name_off)
> >                                         break;
> >                                 tname = btf__str_by_offset(btf, t->name_off);
> >                                 if (tname && !strcmp(tname, type_name))
> >                                         return ret;
> >                                 else
> >                                         break;
> >                         } while (++ret < total);
> >                 } else {
> >                         /* linear search */
> > ...
> >                 }
> >         }
> >
> > out:
> >         return err;
> > }

Powered by blists - more mailing lists