linux-kernel - Re: [RFC PATCH v1] btf: Sort BTF types by name and kind to optimize btf_find_by_name

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: <CAADnVQ+2JSxb7Uca4hOm7UQjfP48RDTXf=g1a4syLpRjWRx9qg@mail.gmail.com>
Date: Mon, 13 Oct 2025 19:48:24 -0700
From: Alexei Starovoitov <alexei.starovoitov@...il.com>
To: Donglin Peng <dolinux.peng@...il.com>
Cc: Andrii Nakryiko <andrii.nakryiko@...il.com>, Andrii Nakryiko <andrii@...nel.org>, 
	LKML <linux-kernel@...r.kernel.org>, 
	linux-trace-kernel <linux-trace-kernel@...r.kernel.org>, bpf <bpf@...r.kernel.org>, 
	Eduard Zingerman <eddyz87@...il.com>, Alexei Starovoitov <ast@...nel.org>, Song Liu <song@...nel.org>, 
	Masami Hiramatsu <mhiramat@...nel.org>, Steven Rostedt <rostedt@...dmis.org>, 
	pengdonglin <pengdonglin@...omi.com>
Subject: Re: [RFC PATCH v1] btf: Sort BTF types by name and kind to optimize
 btf_find_by_name_kind lookup

On Mon, Oct 13, 2025 at 6:54 PM Donglin Peng <dolinux.peng@...il.com> wrote:
>
> On Tue, Oct 14, 2025 at 8:22 AM Alexei Starovoitov
> <alexei.starovoitov@...il.com> wrote:
> >
> > On Mon, Oct 13, 2025 at 5:15 PM Andrii Nakryiko
> > <andrii.nakryiko@...il.com> wrote:
> > >
> > > On Mon, Oct 13, 2025 at 4:53 PM Alexei Starovoitov
> > > <alexei.starovoitov@...il.com> wrote:
> > > >
> > > > On Mon, Oct 13, 2025 at 4:40 PM Andrii Nakryiko
> > > > <andrii.nakryiko@...il.com> wrote:
> > > > >
> > > > > Just a few observations (if we decide to do the sorting of BTF by name
> > > > > in the kernel):
> > > >
> > > > iirc we discussed it in the past and decided to do sorting in pahole
> > > > and let the kernel verify whether it's sorted or not.
> > > > Then no extra memory is needed.
> > > > Or was that idea discarded for some reason?
> > >
> > > Don't really remember at this point, tbh. Pre-sorting should work
> > > (though I'd argue that then we should only sort by name to make this
> > > sorting universally useful, doing linear search over kinds is fast,
> > > IMO). Pre-sorting won't work for program BTFs, don't know how
> > > important that is. This indexing on demand approach would be
> > > universal. ¯\_(ツ)_/¯
> > >
> > > Overall, paying 300KB for sorted index for vmlinux BTF for cases where
> > > we repeatedly need this seems ok to me, tbh.
> >
> > If pahole sorting works I don't see why consuming even 300k is ok.
> > kallsyms are sorted during the build too.
>
> Thanks. We did discuss pre-sorting in pahole in the threads:
>
> https://lore.kernel.org/all/CAADnVQLMHUNE95eBXdy6=+gHoFHRsihmQ75GZvGy-hSuHoaT5A@mail.gmail.com/
> https://lore.kernel.org/all/CAEf4BzaXHrjoEWmEcvK62bqKuT3de__+juvGctR3=e8avRWpMQ@mail.gmail.com/
>
> However, since that approach depends on newer pahole features and
> btf_find_by_name_kind is already being called quite frequently, I suggest
> we first implement sorting within the kernel, and subsequently add pre-sorting
> support in pahole.

and then what? Remove it from the kernel when pahole is newer?
I'd rather not do this churn in the first place.

Since you revived that thread from 2024 and did not
follow up with pahole changes since then, I don't believe that
you will do them if we land kernel changes first.