netdev - Re: [RFC bpf-next 07/16] kallsyms: Use rb tree for kallsyms name search

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]

Date:   Thu, 29 Oct 2020 10:33:43 +0100
From:   Jiri Olsa <jolsa@...hat.com>
To:     Andrii Nakryiko <andrii.nakryiko@...il.com>
Cc:     Jiri Olsa <jolsa@...nel.org>, Alexei Starovoitov <ast@...nel.org>,
        Daniel Borkmann <daniel@...earbox.net>,
        Andrii Nakryiko <andriin@...com>,
        Networking <netdev@...r.kernel.org>, bpf <bpf@...r.kernel.org>,
        Martin KaFai Lau <kafai@...com>,
        Song Liu <songliubraving@...com>, Yonghong Song <yhs@...com>,
        John Fastabend <john.fastabend@...il.com>,
        KP Singh <kpsingh@...omium.org>, Daniel Xu <dxu@...uu.xyz>,
        Steven Rostedt <rostedt@...dmis.org>,
        Jesper Brouer <jbrouer@...hat.com>,
        Toke Høiland-Jørgensen <toke@...hat.com>,
        Viktor Malik <vmalik@...hat.com>
Subject: Re: [RFC bpf-next 07/16] kallsyms: Use rb tree for kallsyms name
 search

On Wed, Oct 28, 2020 at 03:40:46PM -0700, Andrii Nakryiko wrote:
> On Wed, Oct 28, 2020 at 3:29 PM Jiri Olsa <jolsa@...hat.com> wrote:
> >
> > On Thu, Oct 22, 2020 at 10:21:29AM +0200, Jiri Olsa wrote:
> > > The kallsyms_expand_symbol function showed in several bpf related
> > > profiles, because it's doing linear search.
> > >
> > > Before:
> > >
> > >  Performance counter stats for './src/bpftrace -ve kfunc:__x64_sys_s* \
> > >    { printf("test\n"); } i:ms:10 { printf("exit\n"); exit();}' (5 runs):
> > >
> > >      2,535,458,767      cycles:k                         ( +-  0.55% )
> > >        940,046,382      cycles:u                         ( +-  0.27% )
> > >
> > >              33.60 +- 3.27 seconds time elapsed  ( +-  9.73% )
> > >
> > > Loading all the vmlinux symbols in rbtree and and switch to rbtree
> > > search in kallsyms_lookup_name function to save few cycles and time.
> > >
> > > After:
> > >
> > >  Performance counter stats for './src/bpftrace -ve kfunc:__x64_sys_s* \
> > >    { printf("test\n"); } i:ms:10 { printf("exit\n"); exit();}' (5 runs):
> > >
> > >      2,199,433,771      cycles:k                         ( +-  0.55% )
> > >        936,105,469      cycles:u                         ( +-  0.37% )
> > >
> > >              26.48 +- 3.57 seconds time elapsed  ( +- 13.49% )
> > >
> > > Each symbol takes 160 bytes, so for my .config I've got about 18 MBs
> > > used for 115285 symbols.
> > >
> > > Signed-off-by: Jiri Olsa <jolsa@...nel.org>
> >
> > FYI there's init_kprobes dependency on kallsyms_lookup_name in early
> > init call, so this won't work as it is :-\ will address this in v2
> >
> > also I'll switch to sorted array and bsearch, because kallsyms is not
> > dynamically updated
> 
> what about kernel modules then?

please check my answer to Alexei, I just answered it there

thanks,
jirka

> 
> >
> > jirka
> >
> > > ---
> > >  kernel/kallsyms.c | 95 ++++++++++++++++++++++++++++++++++++++++++-----
> > >  1 file changed, 86 insertions(+), 9 deletions(-)
> > >
> 
> [...]
>