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

[Andrii Nakryiko <andrii.nakryiko@gmail.com>]

On Thu, Oct 29, 2020 at 2:31 AM Jiri Olsa <jolsa@redhat.com> wrote:
>
> On Wed, Oct 28, 2020 at 02:15:02PM -0700, Alexei Starovoitov wrote:
> > On Wed, Oct 28, 2020 at 07:25:34PM +0100, Jiri Olsa 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@kernel.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
> >
> > wait wat? kallsyms are dynamically updated. bpf adds and removes from it.
> > You even worked on some of those patches :)
>
> yes, it's tricky ;-) kallsyms_lookup_name function goes through builtin
> (compiled in) symbols and "standard modules" symbols
>
> we add bpf symbols as "pseudo module" symbol, which is not covered by
> this function search, it is covered when displaying /proc/kallsyms
> (check get_ksymbol_bpf function), same for ftrace and kprobe symbols
>
> AFAICS we use kallsyms_lookup_name only to search builtin kernel symbols,
> so we don't care it does not cover "pseudo modules"
>
> now.. what's even more funny, is that if I switch to sort/bsearch,
> performance is back on the same numbers as the current code :-\

If you do hashmap instead of RB tree or sort+bsearch, it will beat
both (assuming you have an adequate number of hash buckets, of
course).

>
> jirka
>