linux-kernel - Re: [RFC PATCH v3] bpf: Using binary search to improve the performance of 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 for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date: Mon, 17 Jun 2024 15:18:38 +0100
From: Alan Maguire <alan.maguire@...cle.com>
To: Donglin Peng <dolinux.peng@...il.com>,
        Eduard Zingerman <eddyz87@...il.com>
Cc: ast@...nel.org, andrii <andrii@...nel.org>, acme@...nel.org,
        daniel@...earbox.net, mhiramat@...nel.org, song@...nel.org,
        haoluo@...gle.com, yonghong.song@...ux.dev, bpf@...r.kernel.org,
        linux-kernel@...r.kernel.org
Subject: Re: [RFC PATCH v3] bpf: Using binary search to improve the
 performance of btf_find_by_name_kind

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