linux-kernel - Re: [PATCH v4 3/3] libbpf: 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: Windows password security audit tool. GUI, reports in PDF.

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

Message-ID: <CAEf4BzYZgAPZSQTTk20s8vUwDMipe+0HRyKNnQchM+C10-1qOQ@mail.gmail.com>
Date: Tue, 29 Oct 2024 15:15:34 -0700
From: Andrii Nakryiko <andrii.nakryiko@...il.com>
To: Donglin Peng <dolinux.peng@...il.com>
Cc: andrii@...nel.org, eddyz87@...il.com, ast@...nel.org, rostedt@...dmis.org, 
	mhiramat@...nel.org, bpf@...r.kernel.org, linux-trace-kernel@...r.kernel.org, 
	linux-kselftest@...r.kernel.org, linux-kernel@...r.kernel.org
Subject: Re: [PATCH v4 3/3] libbpf: Using binary search to improve the
 performance of btf__find_by_name_kind

On Mon, Oct 28, 2024 at 5:22 PM Donglin Peng <dolinux.peng@...il.com> wrote:
>
> Currently, we are only using the linear search method to find the type id
> by the name, which has a time complexity of O(n). This change involves
> sorting the names of btf types in ascending order and using binary search,
> which has a time complexity of O(log(n)).
>
> Another change is the search direction, where we search the BTF first and
> then its base.
>
> Signed-off-by: Donglin Peng <dolinux.peng@...il.com>
> ---
>  tools/lib/bpf/btf.c | 159 ++++++++++++++++++++++++++++++++++++++------
>  1 file changed, 140 insertions(+), 19 deletions(-)
>

same complaints as with kernel-side implementation

I'm not sure if this is the right approach, overall. I can see how
pre-sorting might be useful if done by pahole. But then I'd say we
should record some bit somewhere in btf_header claiming that this is
sorted BTF, and then if that bit is set and we confirmed (on the
kernel side) that sorting is indeed correct (and if not, reject, don't
silently ignore), then we can use that sorting to our advantage.

I don't think libbpf should unconditionally sort or check sorting in
the way that you implemented.

> diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c
> index 5290e9d59997..cbf88a6b92e5 100644
> --- a/tools/lib/bpf/btf.c
> +++ b/tools/lib/bpf/btf.c
> @@ -94,6 +94,10 @@ struct btf {
>          *   - for split BTF counts number of types added on top of base BTF.
>          */
>         __u32 nr_types;
> +       /* number of types in this BTF instance which are sorted by name:
> +        *   - doesn't include special [0] void type;
> +        */
> +       __u32 nr_types_sorted;
>         /* if not NULL, points to the base BTF on top of which the current
>          * split BTF is based
>          */

[...]