linux-kernel - Re: [RFC PATCH v2 2/5] btf: sort BTF types by kind and name to enable binary search

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 for Android: free password hash cracker in your pocket

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

Message-ID: <CAErzpmtMPuGBhisLOaZMyzM5u3=0QrmZcuWqNgbMrceEEPN3TA@mail.gmail.com>
Date: Fri, 24 Oct 2025 09:59:29 +0800
From: Donglin Peng <dolinux.peng@...il.com>
To: Andrii Nakryiko <andrii.nakryiko@...il.com>, 
	Alexei Starovoitov <alexei.starovoitov@...il.com>, Eduard Zingerman <eddyz87@...il.com>, 
	Alan Maguire <alan.maguire@...cle.com>
Cc: Alexei Starovoitov <ast@...nel.org>, LKML <linux-kernel@...r.kernel.org>, 
	bpf <bpf@...r.kernel.org>, Song Liu <song@...nel.org>, 
	pengdonglin <pengdonglin@...omi.com>
Subject: Re: [RFC PATCH v2 2/5] btf: sort BTF types by kind and name to enable
 binary search

On Fri, Oct 24, 2025 at 3:40 AM Andrii Nakryiko
<andrii.nakryiko@...il.com> wrote:
>
> On Thu, Oct 23, 2025 at 11:37 AM Alexei Starovoitov
> <alexei.starovoitov@...il.com> wrote:
> >
> > On Thu, Oct 23, 2025 at 9:28 AM Andrii Nakryiko
> > <andrii.nakryiko@...il.com> wrote:
> > >
> > >
> > > Speaking of flags, though. I think adding BTF_F_SORTED flag to
> > > btf_header->flags seems useful, as that would allow libbpf (and user
> > > space apps working with BTF in general) to use more optimal
> > > find_by_name implementation. The only gotcha is that old kernels
> > > enforce this btf_header->flags to be zero, so pahole would need to
> > > know not to emit this when building BTF for old kernels (or, rather,
> > > we'll just teach pahole_flags in kernel build scripts to add this
> > > going forward). This is not very important for kernel, because kernel
> > > has to validate all this anyways, but would allow saving time for user
> > > space.
> >
> > Thinking more about it... I don't think it's worth it.
> > It's an operational headache. I'd rather have newer pahole sort it
> > without on/off flags and detection, so that people can upgrade
> > pahole and build older kernels.
> > Also BTF_F_SORTED doesn't spell out the way it's sorted.
> > Things may change and we will need a new flag and so on.
> > I think it's easier to check in the kernel and libbpf whether
> > BTF is sorted the way they want it.
> > The check is simple, fast and done once. Then both (kernel and libbpf) can
> > set an internal flag and use different functions to search
> > within a given BTF.
>
> I guess that's fine. libbpf can do this check lazily on the first
> btf__find_by_name() to avoid unnecessary overhead. Agreed.

Thank you for all the feedback. Based on the suggestions above, the sorting
implementation will be redesigned in the next version as follows:

1. The sorting operation will be fully handled by pahole, with no dependency on
libbpf. This means users can benefit from sorting simply by upgrading their
pahole version.

2. The kernel and libbpf will only be responsible for:
    2.1. Checking whether the BTF data is sorted
    2.2. Implementing binary search for sorted BTF

Regarding the sorting check overhead: if the runtime cost is sufficiently small,
it can be performed during BTF parsing. Based on my local testing with vmlinux
 BTF (containing 143,484 btf_types), this check takes at most 1.5 milliseconds
during boot. Is this 1.5ms overhead acceptable?

Are there any other suggestions?