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: <CAErzpmsuf0e9O4p1srdadoCwn7zNN6rEb8wt5yEOT0FByx5RJw@mail.gmail.com>
Date: Wed, 30 Oct 2024 23:24:13 +0800
From: Donglin Peng <dolinux.peng@...il.com>
To: Andrii Nakryiko <andrii.nakryiko@...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 Wed, Oct 30, 2024 at 6:15 AM Andrii Nakryiko
<andrii.nakryiko@...il.com> wrote:
>
> 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.

Thank you, I also agree. we could utilize a bit of the flags within the
btf_header structure to indicate if the btf file has been sorted.

>
> 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
> >          */
>
> [...]