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

[Eduard Zingerman <eddyz87@gmail.com>]

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@gmail.com> wrote:
> > 
> > On Fri, Oct 24, 2025 at 3:40 AM Andrii Nakryiko
> > <andrii.nakryiko@gmail.com> wrote:
> > > 
> > > On Thu, Oct 23, 2025 at 11:37 AM Alexei Starovoitov
> > > <alexei.starovoitov@gmail.com> wrote:
> > > > 
> > > > On Thu, Oct 23, 2025 at 9:28 AM Andrii Nakryiko
> > > > <andrii.nakryiko@gmail.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?

> > 
> > 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?