| 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: <CAEf4BzZrZZ-YHHAUE-izLaAexm4VZ7aCurKnOofCtKaV=D9qvQ@mail.gmail.com>
Date: Fri, 19 Dec 2025 09:28:22 -0800
From: Andrii Nakryiko <andrii.nakryiko@...il.com>
To: Donglin Peng <dolinux.peng@...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 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.
>
> 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.
Right, start_id has to be passed in. But end_id is always the same, so
maybe determine it internally instead? And let's not return -ENOENT
from btf_find_by_name_bsearch(), as I mentioned before, it would be
more streamlined if you return btf__type_cnt(btf) if search failed.
>
> >
> > > + 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.
>
see above, by returning btf__type_cnt() you won't even have this error
handling, you'll just go through normal loop checking for a match and
won't find anything, returning -ENOENT then.
> >
> > > +
> > > + 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.
>
If you decide to change implementation due to some unforeseen factors
(like concern about 4% microbenchmark improvement), it would be
helpful for you to call this out in a reply to the original
discussion. A line somewhere in the cover letter changelog is way too
easy to miss and that doesn't give me an opportunity to stop you
before you go and produce another revision that I'll then be
rejecting.
> >
> > > + 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