| 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: <CAErzpmv0KQh2-Yo1spHkTP-fkUiLeWVkJ4-R7toCUFrKVsgDhQ@mail.gmail.com>
Date: Tue, 6 Jan 2026 10:42:04 +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 Tue, Jan 6, 2026 at 8:38 AM Andrii Nakryiko
<andrii.nakryiko@...il.com> wrote:
>
> On Sun, Dec 21, 2025 at 5:58 PM Donglin Peng <dolinux.peng@...il.com> wrote:
> >
> > On Sat, Dec 20, 2025 at 5:38 PM Donglin Peng <dolinux.peng@...il.com> wrote:
> > >
> > > On Sat, Dec 20, 2025 at 1:28 AM Andrii Nakryiko
> > > <andrii.nakryiko@...il.com> wrote:
> > > >
> > > > On Thu, Dec 18, 2025 at 6:53 PM Donglin Peng <dolinux.peng@...il.com> wrote:
> > > > >
> > > > > 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.
> > > >
> > > > If you keep oscillating like that this patch set will never land. 4%
> > > > (500us) gain on artificial and unrealistic micro-benchmark is
> > > > meaningless and irrelevant, you are just adding more work for yourself
> > > > and for reviewers by constantly changing your implementation between
> > > > revisions for no good reason.
> > >
> > > Thank you, I understand and will learn from it. I think the performance gain
> > > makes sense. I’d like to share a specific real-world case where this
> > > optimization
> > > could matter: the `btf_find_by_name_kind()` function is indeed infrequently
> > > used by the BPF subsystem, but it’s heavily relied upon by the ftrace
> > > subsystem’s features like `func-args`, `funcgraph-args` [1], and the upcoming
> > > `funcgraph-retval` [2]. These features invoke the function nearly once per
> > > trace line when outputting, with a call frequency that can reach **100 kHz**
> > > in intensive tracing workloads.
> >
> > Hi Andrii,
> > I think we can refactor the code based on your suggestion like this:
> >
> > 1. If the binary search finds the matching name type, return its index.
> > Else, return btf__type_cnt(btf). It will make the code streamlined.
> > 2. Skip the name checking in the first loop to eliminate the extra strcmp.
> >
> > What do you think?
> >
> > tatic __s32 btf_find_by_name_bsearch(const struct btf *btf, const char *name,
> > __s32 start_id)
> > {
> > const struct btf_type *t;
> > const char *tname;
> > __s32 end_id = btf__type_cnt(btf) - 1;
> > __s32 l, r, m, lmost = end_id + 1;
> > int ret;
> >
> > 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;
> > }
> > }
> >
> > return lmost;
> > }
> >
> > static __s32 btf_find_by_name_kind(const struct btf *btf, int start_id,
> > const char *type_name, __u32 kind)
> > {
> > ......
> > if (btf_is_sorted(btf) && type_name[0]) {
> > bool first_loop = true;
> >
> > start_id = max(start_id, btf_sorted_start_id(btf));
> > idx = btf_find_by_name_bsearch(btf, type_name, start_id);
> > for (; idx < btf__type_cnt(btf); idx++) {
> > t = btf__type_by_id(btf, idx);
> > tname = btf__str_by_offset(btf, t->name_off);
> > if (!first_loop && strcmp(tname, type_name) != 0)
> > return libbpf_err(-ENOENT);
>
> no, let's keep it simple, please revert to previous implementation we
> agreed upon
Okay. I will do it.
>
> > if (kind == -1 || btf_kind(t) == kind)
> > return idx;
> > if (first_loop)
> > first_loop = false;
> > }
> > } else {
> > ......
> > }
> >
> > return libbpf_err(-ENOENT);
> > }
> >
> > >
> > > In such scenarios, the extra `strcmp` operations translate to ~100,000
> > > additional
> > > string comparisons per second. While this might seem negligible in isolation,
> > > the overhead accumulates under high-frequency tracing—potentially impacting
> > > latency for users relying on detailed function argument/return value tracing.
> > >
> > > Thanks again for pushing for rigor—it helps make the code more cleaner
> > > and robust.
> > >
> > > [1] https://lore.kernel.org/all/20250227185822.639418500@goodmis.org/
> > > [2] https://lore.kernel.org/all/20251215034153.2367756-1-dolinux.peng@gmail.com/
> > >
>
> [...]
Powered by blists - more mailing lists