Message-ID: <CAErzpmu_FD_mHcU4uL0XpNU00XngY-1vN5OkKcBBfH2Mr-vY9A@mail.gmail.com>
Date: Fri, 7 Nov 2025 12:57:28 +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>, zhangxiaoqin@...omi.com
Subject: Re: [RFC PATCH v4 3/7] libbpf: Optimize type lookup with binary
 search for sorted BTF

On Fri, Nov 7, 2025 at 1:31 AM Andrii Nakryiko
<andrii.nakryiko@...il.com> wrote:
>
> On Wed, Nov 5, 2025 at 11:49 PM Donglin Peng <dolinux.peng@...il.com> wrote:
> >
> > 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
>
> It should be `while (l <= r)`, I forgot to update it, but I mentioned
> that I do want to allow l == r condition.
>
> > is used. Moreover, even if the condition were to hold, it wouldn't guarantee
> > a successful search.
>
> Elaborate please on "wouldn't guarantee a successful search".

I think a successful search is that we can successfully find the element that
we want.

>
> >
> > >         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.
>
> Think how you will be using this inside btf_find_type_by_name_kind():
>
>
> int idx = btf_find_by_name_bsearch(btf, name);
>
> for (int n = btf__type_cnt(btf); idx < n; idx++) {
>     struct btf_type *t = btf__type_by_id(btf, idx);
>     const char *tname = btf__str_by_offset(btf, t->name_off);
>     if (strcmp(tname, name) != 0)
>         return -ENOENT;
>     if (btf_kind(t) == kind)
>         return idx;
> }
> return -ENOENT;

Thanks, it seems cleaner.

>
>
> Having btf_find_by_name_bsearch() return -ENOENT instead of
> btf__type_cnt() just will require extra explicit -ENOENT handling. And
> given the function now can return "error", we'd need to either handle
> other non-ENOENT errors, to at least leave comment that this should
> never happen, though interface itself looks like it could.
>
> This is relatively minor and its all internal implementation, so we
> can change that later. But I'm explaining my reasons for why I'd
> return index of non-existing type after the end, just like you'd do
> with pointer-based interfaces that return pointer after the last
> element.

Thanks, I see.

>
>
> >
> > >
> > >
> > > 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.
>
> If the last element has >= name, search will definitely find at least
> that element. What do you mean by "succeed"? All I care about here is

Thank you. By "successful search," I mean finding the exact matching
element we're looking for—not just the first element that meets the "≥"
condition.

Here's a concrete example to illustrate the issue:

Base BTF contains: {"A", "C", "E", "F"}
Split BTF contains: {"B", "D"}
Target search: "D" in split BTF

The current implementation recursively searches from the base BTF first.
While "D" is lexicographically ≤ "F" (the last element in base BTF), "D" doesn't
actually exist in the base BTF. When the binary search reaches the l
== r condition,
it returns the index of "E" instead.

This requires an extra name comparison check after btf_find_by_name_bsearch
returns, which could be avoided in the first loop iteration if the
search directly
identified exact matches.

int idx = btf_find_by_name_bsearch(btf, name);

for (int n = btf__type_cnt(btf); idx < n; idx++) {
    struct btf_type *t = btf__type_by_id(btf, idx);
    const char *tname = btf__str_by_offset(btf, t->name_off);
    if (strcmp(tname, name) != 0)  <<< This check is redundant on the first loop
                                                            iteration
when a matching index is found
        return -ENOENT;
    if (btf_kind(t) == kind)
        return idx;
}
return -ENOENT;

I tested this with a simple program searching for 3 in {0, 1, 2, 4, 5}:

int main(int argc, char *argv[])
{
        int values[] = {0, 1, 2, 4, 5};
        int to_find;
        int i;

        to_find = atoi(argv[1]);;

        for (i = 0; i < ARRAY_SIZE(values); i++)
                printf("[%d] = %d\n", i , values[i]);

        printf("To Find %d\n", to_find);

        {
                int l, m, r;

                l = 0;
                r = ARRAY_SIZE(values) - 1;

                while (l <= r) {
                        m = l + (r- l) / 2;
                        if (values[m] >= to_find) {
                                if (l == r) {
                                        printf("!!!! Found: [%d] ==>
%d\n", r, values[r]);
                                        break;
                                }
                                r = m;
                        } else {
                                l = m + 1;
                        }
                }

                printf("END: l: %d, r: %d\n", l, r);
        }

        return 0;
}

Output:
[0] = 0
[1] = 1
[2] = 2
[3] = 4
[4] = 5
To Find 3
!!!! Found: [3] ==> 4
END: l: 3, r: 3

The search returns index 3 (value 4), which is the first value ≥ 3,
but since 4 ≠ 3,
it's not an exact match. Thus, the algorithm cannot guarantee a
successful search
for the exact element without additional checks.

> that binary search loop doesn't loop forever and it returns correct
> index (or detects that no element can be found).
>
> >
> > >
> > > >
> > > > 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