| 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
| ||
|
Message-ID: <CAEf4Bzb3Eu0J83O=Y4KA-LkzBMjtx7cbonxPzkiduzZ1Pedajg@mail.gmail.com>
Date: Wed, 5 Nov 2025 10:11:13 -0800
From: Andrii Nakryiko <andrii.nakryiko@...il.com>
To: Donglin Peng <dolinux.peng@...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 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! */
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);
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.
>
> 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