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: Windows password security audit tool. GUI, reports in PDF.

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

Message-ID: <CAErzpmuY0miq0B5BSF8ueY+NOTGfvcUKPbO4_W3BKX74c5K4rg@mail.gmail.com>
Date: Fri, 24 Oct 2025 11:19:55 +0800
From: Donglin Peng <dolinux.peng@...il.com>
To: Eduard Zingerman <eddyz87@...il.com>
Cc: Andrii Nakryiko <andrii.nakryiko@...il.com>, 
	Alexei Starovoitov <alexei.starovoitov@...il.com>, Alan Maguire <alan.maguire@...cle.com>, 
	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 11:15 AM Eduard Zingerman <eddyz87@...il.com> wrote:
>
> On Fri, 2025-10-24 at 11:04 +0800, Donglin Peng wrote:
> > On Fri, Oct 24, 2025 at 10:32 AM Eduard Zingerman <eddyz87@...il.com> wrote:
> > >
> > > On Fri, 2025-10-24 at 10:23 +0800, Donglin Peng wrote:
> > > > On Fri, Oct 24, 2025 at 9:59 AM Donglin Peng <dolinux.peng@...il.com> wrote:
> > > > >
> > > > > 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.
> > > >
> > > > I suggest that libbpf provides a sorting function, such as the
> > > > btf__permute suggested
> > > > by Andrii, for pahole to call. This approach allows pahole to leverage
> > > > libbpf's existing
> > > > helper functions and avoids code duplication.
> > >
> > > Could you please enumerate the functions you'd have to reimplement in
> > > pahole?
> >
> > Yes. Once the BTF types are sorted, the type IDs in both the BTF and BTF ext
> > sections must be remapped. Libbpf provides helper functions like
> > btf_field_iter_init,
> > btf_field_iter_next,
> > btf_ext_visit_type_ids
> > to iterate through the btf_field and btf_ext_info_sec entries that
> > require updating.
> > We will likely need to reimplement these three functions for this purpose.
>
> I think Andrii's suggestion is to have btf__permute in libbpf,
> as it needs all the functions you mention.
> But actual sorting can happen in pahole, then:
> - allocate array of length num-types, initialize it 0..num-types;
> - reorder it as one sees fit;
> - call btf__permute() from libbpf and get all the renamings handled by it.

Yes, the first two can be implemented in pahole, while the last one belongs
in libbpf.

>
> [...]