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] [thread-next>] [day] [month] [year] [list]

Message-ID: <CAEf4Bzajdv3Rd1xAxm_UZWBxPc8M0=VuUkfjJvOFSObOs19GbQ@mail.gmail.com>
Date: Thu, 23 Oct 2025 09:28:30 -0700
From: Andrii Nakryiko <andrii.nakryiko@...il.com>
To: Alexei Starovoitov <alexei.starovoitov@...il.com>
Cc: Donglin Peng <dolinux.peng@...il.com>, Eduard Zingerman <eddyz87@...il.com>, 
	Alexei Starovoitov <ast@...nel.org>, Alan Maguire <alan.maguire@...cle.com>, 
	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 Thu, Oct 23, 2025 at 8:53 AM Alexei Starovoitov
<alexei.starovoitov@...il.com> wrote:
>
> On Thu, Oct 23, 2025 at 3:35 AM Donglin Peng <dolinux.peng@...il.com> wrote:
> >
> > On Thu, Oct 23, 2025 at 4:50 AM Eduard Zingerman <eddyz87@...il.com> wrote:
> > >
> > > On Wed, 2025-10-22 at 11:02 +0800, Donglin Peng wrote:
> > > > On Wed, Oct 22, 2025 at 2:59 AM Eduard Zingerman <eddyz87@...il.com> wrote:
> > > > >
> > > > > On Mon, 2025-10-20 at 17:39 +0800, Donglin Peng wrote:
> > > > > > This patch implements sorting of BTF types by their kind and name,
> > > > > > enabling the use of binary search for type lookups.
> > > > > >
> > > > > > To share logic between kernel and libbpf, a new btf_sort.c file is
> > > > > > introduced containing common sorting functionality.
> > > > > >
> > > > > > The sorting is performed during btf__dedup() when the new
> > > > > > sort_by_kind_name option in btf_dedup_opts is enabled.
> > > > >
> > > > > Do we really need this option?  Dedup is free to rearrange btf types
> > > > > anyway, so why not sort always?  Is execution time a concern?
> > > >
> > > > The issue is that sorting changes the layout of BTF. Many existing selftests
> > > > rely on the current, non-sorted order for their validation checks. Introducing
> > > > this as an optional feature first allows us to run it without immediately
> > > > breaking the tests, giving us time to fix them incrementally.
> > >
> > > How many tests are we talking about?
> > > The option is an API and it stays with us forever.
> > > If the only justification for its existence is to avoid tests
> > > modification, I don't think that's enough.
> >
> > I get your point, thanks. I wonder what others think?
>
> +1 to Eduard's point.
> No new flags please. Always sort.
>
> Also I don't feel that sorting logic belongs in libbpf.
> pahole needs to dedup first, apply extra filters, add extra BTFs.
> At that point going back to libbpf and asking to sort seems odd.

Correct, I'd also not bake sorting into libbpf. Sorting order should
be determined by pahole (or whatever other producer of BTF) after all
the information is collected. So btf_dedup shouldn't sort.

But I think we should add a new API to libbpf to help with sorting.
I'd add this:

int btf__permute(struct btf *btf, int permutation, int permutation_sz);

With the idea that libbpf will renumber and reshuffle BTF data
according to permutation provided by the caller. Caller should make
sure that permutation is a valid one, of course.

 (we can also extend this to allow specifying that some types should
be dropped by mapping them to zero, I think I wanted something like
that for BTF linker at some point, don't remember details anymore; but
that's definitely not in v1)

This is useful for sorting use case (pahole build an index from old
btf type ID to new btf type ID -> libbpf shuffles bytes and renumbers
everything), but can be applied more generally (I don't remember now,
but I did have this idea earlier in response to some need for BTF
reshuffling).

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.