linux-kernel - Re: [RFC PATCH v4 3/7] libbpf: Optimize type lookup with binary search for sorted BTF

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <CAErzpmsoNO66S8ER8EfmH-9H_iMAEWQGtKNEF=767-n3SR-JJQ@mail.gmail.com>
Date: Thu, 6 Nov 2025 14:10:11 +0800
From: Donglin Peng <dolinux.peng@...il.com>
To: Eduard Zingerman <eddyz87@...il.com>, Andrii Nakryiko <andrii.nakryiko@...il.com>
Cc: 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 12:52 AM Eduard Zingerman <eddyz87@...il.com> wrote:
>
> On Wed, 2025-11-05 at 21:48 +0800, Donglin Peng 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.
> >
> > 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.
>
> Could you please also check if there is a difference between having
> nr_sorted_types as is and having it equal to nr_types?
> Want to understand if this optimization is necessary.

Yes, here is the result:

| Condition                                       | Lookup Time   |
Improvement  |
|----------------------------------------------|------------------
--|------------------|
| Unsorted (Linear)                          | 16666461 us   | Baseline       |
| Sorted (Binary) nr__types             | 9957 us           | 1673x faster |
| Sorted (Binary) nr_sorted_types   | 9337 us           | 1785x faster |

Using nr_sorted_types provides an additional 6% performance improvement
over nr_types.

>
> [...]