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: <CAErzpmtCxPvWU03fn1+1abeCXf8KfGA+=O+7ZkMpQd-RtpM6UA@mail.gmail.com>
Date: Tue, 14 Oct 2025 09:54:24 +0800
From: Donglin Peng <dolinux.peng@...il.com>
To: Alexei Starovoitov <alexei.starovoitov@...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 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.

>
> In the other thread we discuss adding LOCSEC for ~6M. That thing should
> be pahole-sorted too.