Re: [RFC PATCH v3] bpf: Using binary search to improve the performance of btf_find_by_name_kind

Alan Maguire
2024-06-17T14:19:41Z

On 15/06/2024 15:59, Donglin Peng wrote:
> On Sat, Jun 15, 2024 at 7:49 PM Donglin Peng <dolinux.peng@gmail.com> wrote:
>>
>> On Tue, Jun 11, 2024 at 6:13 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>>>
>>> On Sat, 2024-06-08 at 07:08 -0700, Donglin Peng wrote:
>>>
>>> [...]
>>>
>>>> Changes in RFC v3:
>>>> - Sort the btf types during the build process in order to reduce memory usage
>>>> and decrease boot time.
>>>>
>>>> RFC v2:
>>>> - https://lore.kernel.org/all/20230909091646.420163-1-pengdonglin@sangfor.com.cn
>>>> ---
>>>> include/linux/btf.h | 1 +
>>>> kernel/bpf/btf.c | 160 +++++++++++++++++++++++++++++++++---
>>>
>>> I think that kernel part is in a good shape,
>>> please split it as a separate commit.
>>
>> Okay, thanks.
>>
>>>
>>>> tools/lib/bpf/btf.c | 195 ++++++++++++++++++++++++++++++++++++++++++++
>>>> 3 files changed, 345 insertions(+), 11 deletions(-)
>>>
>>> [...]
>>>
>>>> diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c
>>>> index 2d0840ef599a..93c1ab677bfa 100644
>>>
>>> I'm not sure that libbpf is the best place to put this functionality,
>>> as there might be different kinds of orderings
>>> (e.g. see a fresh commit to bpftool to output stable vmlinux.h:
>>> 94133cf24bb3 "bpftool: Introduce btf c dump sorting").
>>
>> Thanks, I think it would be better to put it into the libbpf. However, I would
>> also like to hear the opinions of others.
>>
>>>
>>> I'm curious what Andrii, Alan and Arnaldo think on libbpf vs pahole
>>> for this feature.
>>>
>>> Also, I have a selftests build failure with this patch-set
>>> (and I suspect that a bunch of dedup test cases would need an update):
>
> Yes，many test cases need to be updated as the BTF layout is modified
> unconditionally.
>

If the plan is to fold the sorting into dedup, pahole will inherit it by
default I suppose. Would it be worth making sorting optional (or at
least providing a way to switch if off) via a dedup_opts option? If we
had an on/off switch we could control sorting via a --btf_features
option to pahole.

One thing we lose with sorting is that currently the base and often-used
types tend to cluster at initial BTF ids, so in some cases linear
searches find what they're looking for pretty quickly. Would it be worth
maintaining a name-sorted index for BTF perhaps? That would mean not
changing type id order (so linear search is unaffected), but for
btf_find_by_name_kind() searches the index could be used.

See the btf_relocate.c code at [1] for an example of this where a
name-based sort index is constructed for the smaller distilled base BTF.

[1]