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

[Alan Maguire]

On 15/06/2024 15:59, Donglin Peng wrote:
> On Sat, Jun 15, 2024 at 7:49 PM Donglin Peng <dolinux.peng@xxxxxxxxx> wrote:
>>
>> On Tue, Jun 11, 2024 at 6:13 PM Eduard Zingerman <eddyz87@xxxxxxxxx> 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@xxxxxxxxxxxxxx
>>>> ---
>>>>  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]
https://lore.kernel.org/bpf/20240613095014.357981-4-alan.maguire@xxxxxxxxxx/