From: Alan Maguire <alan.maguire@oracle.com>
To: Donglin Peng <dolinux.peng@gmail.com>,
Alexei Starovoitov <alexei.starovoitov@gmail.com>
Cc: Andrii Nakryiko <andrii.nakryiko@gmail.com>,
Andrii Nakryiko <andrii@kernel.org>,
LKML <linux-kernel@vger.kernel.org>,
linux-trace-kernel <linux-trace-kernel@vger.kernel.org>,
bpf <bpf@vger.kernel.org>, Eduard Zingerman <eddyz87@gmail.com>,
Alexei Starovoitov <ast@kernel.org>, Song Liu <song@kernel.org>,
Masami Hiramatsu <mhiramat@kernel.org>,
Steven Rostedt <rostedt@goodmis.org>,
pengdonglin <pengdonglin@xiaomi.com>
Subject: Re: [RFC PATCH v1] btf: Sort BTF types by name and kind to optimize btf_find_by_name_kind lookup
Date: Tue, 14 Oct 2025 09:05:50 +0100 [thread overview]
Message-ID: <7f770a27-6ca6-463f-9145-5c795e0b3f40@oracle.com> (raw)
In-Reply-To: <CAErzpmu0Zjo0+_r-iBWoAOUiqbC9=sJmJDtLtAANVRU9P-pytg@mail.gmail.com>
On 14/10/2025 05:53, Donglin Peng wrote:
> On Tue, Oct 14, 2025 at 10:48 AM Alexei Starovoitov
> <alexei.starovoitov@gmail.com> wrote:
>>
>> On Mon, Oct 13, 2025 at 6:54 PM Donglin Peng <dolinux.peng@gmail.com> wrote:
>>>
>>> On Tue, Oct 14, 2025 at 8:22 AM Alexei Starovoitov
>>> <alexei.starovoitov@gmail.com> wrote:
>>>>
>>>> On Mon, Oct 13, 2025 at 5:15 PM Andrii Nakryiko
>>>> <andrii.nakryiko@gmail.com> wrote:
>>>>>
>>>>> On Mon, Oct 13, 2025 at 4:53 PM Alexei Starovoitov
>>>>> <alexei.starovoitov@gmail.com> wrote:
>>>>>>
>>>>>> On Mon, Oct 13, 2025 at 4:40 PM Andrii Nakryiko
>>>>>> <andrii.nakryiko@gmail.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.
>
> Apologies for the formatting issues in my previous email—sending this again
> for clarity.
>
> Thank you for your feedback. Your concerns are completely valid.
>
> I’d like to suggest a dual-mechanism approach:
> 1. If BTF is generated by a newer pahole (with pre-sorting support), the
> kernel would use the pre-sorted data directly.
> 2. For BTF from older pahole versions, the kernel would handle sorting
> at load time or later.
>
> This would provide performance benefits immediately while preserving
> backward compatibility. The kernel-side sorting would remain intact
> moving forward, avoiding future churn.
>
If you're taking the approach of doing both - which is best I think -
I'd suggest it might be helpful to look at the bpf_relocate.c code; it's
shared between libbpf and kernel, so you could potentially add shared
code to do sorting in libbpf (which pahole would use) and the kernel
would use too; this would help ensure the behaviour is identical.
Maybe for pahole/libbpf sorting could be done via a new BTF dedup()
option, since dedup is the time we finalize the BTF representation?
Alan
next prev parent reply other threads:[~2025-10-14 8:06 UTC|newest]
Thread overview: 14+ messages / expand[flat|nested] mbox.gz Atom feed top
2025-10-13 13:15 pengdonglin
2025-10-13 23:40 ` Andrii Nakryiko
2025-10-13 23:53 ` Alexei Starovoitov
2025-10-14 0:15 ` Andrii Nakryiko
2025-10-14 0:22 ` Alexei Starovoitov
2025-10-14 1:54 ` Donglin Peng
2025-10-14 2:48 ` Alexei Starovoitov
2025-10-14 4:53 ` Donglin Peng
2025-10-14 8:05 ` Alan Maguire [this message]
2025-10-15 1:12 ` Donglin Peng
2025-10-15 1:54 ` Alexei Starovoitov
2025-10-15 3:43 ` Donglin Peng
2025-10-15 9:15 ` Alan Maguire
2025-10-14 1:54 ` Donglin Peng
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=7f770a27-6ca6-463f-9145-5c795e0b3f40@oracle.com \
--to=alan.maguire@oracle.com \
--cc=alexei.starovoitov@gmail.com \
--cc=andrii.nakryiko@gmail.com \
--cc=andrii@kernel.org \
--cc=ast@kernel.org \
--cc=bpf@vger.kernel.org \
--cc=dolinux.peng@gmail.com \
--cc=eddyz87@gmail.com \
--cc=linux-kernel@vger.kernel.org \
--cc=linux-trace-kernel@vger.kernel.org \
--cc=mhiramat@kernel.org \
--cc=pengdonglin@xiaomi.com \
--cc=rostedt@goodmis.org \
--cc=song@kernel.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox
all inboxes | Powered by JetHome®