| 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: <CAErzpmv1N1JA+=c6xxdYTqANqSBRaRauD2wzZiwUS+VeWQG14A@mail.gmail.com>
Date: Fri, 19 Dec 2025 10:53:10 +0800
From: Donglin Peng <dolinux.peng@...il.com>
To: Andrii Nakryiko <andrii.nakryiko@...il.com>
Cc: ast@...nel.org, eddyz87@...il.com, zhangxiaoqin@...omi.com,
ihor.solodrai@...ux.dev, linux-kernel@...r.kernel.org, bpf@...r.kernel.org,
pengdonglin <pengdonglin@...omi.com>, Alan Maguire <alan.maguire@...cle.com>
Subject: Re: [PATCH bpf-next v10 04/13] libbpf: Optimize type lookup with
binary search for sorted BTF
On Fri, Dec 19, 2025 at 7:29 AM Andrii Nakryiko
<andrii.nakryiko@...il.com> wrote:
>
> On Thu, Dec 18, 2025 at 3:31 AM Donglin Peng <dolinux.peng@...il.com> wrote:
> >
> > From: pengdonglin <pengdonglin@...omi.com>
> >
> > This patch introduces binary search optimization for BTF type lookups
> > when the BTF instance contains sorted types.
> >
> > The optimization significantly improves performance when searching for
> > types in large BTF instances with sorted types. For unsorted BTF, the
> > implementation falls back to the original linear search.
> >
> > Cc: Eduard Zingerman <eddyz87@...il.com>
> > Cc: Alexei Starovoitov <ast@...nel.org>
> > Cc: Andrii Nakryiko <andrii.nakryiko@...il.com>
> > Cc: Alan Maguire <alan.maguire@...cle.com>
> > Cc: Ihor Solodrai <ihor.solodrai@...ux.dev>
> > Cc: Xiaoqin Zhang <zhangxiaoqin@...omi.com>
> > Signed-off-by: pengdonglin <pengdonglin@...omi.com>
> > ---
> > tools/lib/bpf/btf.c | 103 ++++++++++++++++++++++++++++++++++----------
> > 1 file changed, 80 insertions(+), 23 deletions(-)
> >
>
> [...]
>
> > + l = start_id;
> > + r = end_id;
> > + while (l <= r) {
> > + m = l + (r - l) / 2;
> > + t = btf_type_by_id(btf, m);
> > + tname = btf__str_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;
> > + }
> > }
>
> this differs from what we discussed in [0], you said you'll use that
> approach. Can you please elaborate on why you didn't?
>
> [0] https://lore.kernel.org/bpf/CAEf4Bzb3Eu0J83O=Y4KA-LkzBMjtx7cbonxPzkiduzZ1Pedajg@mail.gmail.com/
Yes. As mentioned in the v8 changelog [1], the binary search approach
you referenced was implemented in versions v6 and v7 [2]. However,
testing revealed a slight performance regression. The root cause was
an extra strcmp operation introduced in v7, as discussed in [3]. Therefore,
in v8, I reverted to the approach from v5 [4] and refactored it for clarity.
Benchmark results show that v8 achieves a 4.2% performance improvement
over v7. If we don't care the performance gain, I will revert to the approach
in v7 in the next version.
[1] https://lore.kernel.org/bpf/20251126085025.784288-1-dolinux.peng@gmail.com/
[2] https://lore.kernel.org/all/20251119031531.1817099-1-dolinux.peng@gmail.com/
[3] https://lore.kernel.org/all/CAEf4BzaqEPD46LddJHO1-k5KPGyVWf6d=duDAxG1q=jykJkMBg@mail.gmail.com/
[4] https://lore.kernel.org/all/20251106131956.1222864-4-dolinux.peng@gmail.com/
>
> >
> > - return libbpf_err(-ENOENT);
> > + return lmost;
> > }
> >
> > static __s32 btf_find_by_name_kind(const struct btf *btf, int start_id,
> > const char *type_name, __u32 kind)
>
> kind is defined as u32 but you expect caller to pass -1 to ignore the
> kind. Use int here.
Thanks, I will fix it.
>
> > {
> > - __u32 i, nr_types = btf__type_cnt(btf);
> > + const struct btf_type *t;
> > + const char *tname;
> > + __s32 idx;
> > +
> > + if (start_id < btf->start_id) {
> > + idx = btf_find_by_name_kind(btf->base_btf, start_id,
> > + type_name, kind);
> > + if (idx >= 0)
> > + return idx;
> > + start_id = btf->start_id;
> > + }
> >
> > - if (kind == BTF_KIND_UNKN || !strcmp(type_name, "void"))
> > + if (kind == BTF_KIND_UNKN || strcmp(type_name, "void") == 0)
> > return 0;
> >
> > - for (i = start_id; i < nr_types; i++) {
> > - const struct btf_type *t = btf__type_by_id(btf, i);
> > - const char *name;
> > + if (btf->sorted_start_id > 0 && type_name[0]) {
> > + __s32 end_id = btf__type_cnt(btf) - 1;
> > +
> > + /* skip anonymous types */
> > + start_id = max(start_id, btf->sorted_start_id);
>
> can sorted_start_id ever be smaller than start_id?
>
> > + idx = btf_find_by_name_bsearch(btf, type_name, start_id, end_id);
>
> is there ever a time when btf_find_by_name_bsearch() will work with
> different start_id and end_id? why is this not done inside the
> btf_find_by_name_bsearch()?
Because the start_id could be specified by the caller.
>
> > + if (unlikely(idx < 0))
> > + return libbpf_err(-ENOENT);
>
> pass through error returned from btf_find_by_name_bsearch(), why redefining it?
Thanks, I will fix it.
>
> > +
> > + if (unlikely(kind == -1))
> > + return idx;
> > +
> > + t = btf_type_by_id(btf, idx);
> > + if (likely(BTF_INFO_KIND(t->info) == kind))
>
> use btf_kind(), but this whole extra check is just unnecessary, this
Thanks, I will do it.
> should be done in the loop below. We talked about all this already,
> why do I feel like I'm being ignored?..
Sorry for the confusion, and absolutely not ignoring you.
>
> > + return idx;
>
> drop all these likely and unlikely micro optimizations, please
Thanks, I will do it.
>
>
> > +
> > + for (idx++; idx <= end_id; idx++) {
> > + t = btf__type_by_id(btf, idx);
> > + tname = btf__str_by_offset(btf, t->name_off);
> > + if (strcmp(tname, type_name) != 0)
> > + return libbpf_err(-ENOENT);
> > + if (btf_kind(t) == kind)
> > + return idx;
> > + }
> > + } else {
> > + __u32 i, total;
> >
> > - if (btf_kind(t) != kind)
> > - continue;
> > - name = btf__name_by_offset(btf, t->name_off);
> > - if (name && !strcmp(type_name, name))
> > - return i;
> > + total = btf__type_cnt(btf);
> > + for (i = start_id; i < total; i++) {
> > + t = btf_type_by_id(btf, i);
> > + if (kind != -1 && btf_kind(t) != kind)
>
> nit: kind < 0, no need to hard-code -1
Good, I will fix it.
>
> > + continue;
> > + tname = btf__str_by_offset(btf, t->name_off);
> > + if (strcmp(tname, type_name) == 0)
> > + return i;
> > + }
> > }
> >
> > return libbpf_err(-ENOENT);
> > }
> >
>
> [...]
Powered by blists - more mailing lists