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

From: Jiri Olsa <jolsa@redhat.com>
To: Alexei Starovoitov <alexei.starovoitov@gmail.com>
Cc: "Jiri Olsa" <jolsa@kernel.org>,
	"Alexei Starovoitov" <ast@kernel.org>,
	"Daniel Borkmann" <daniel@iogearbox.net>,
	"Andrii Nakryiko" <andriin@fb.com>,
	netdev@vger.kernel.org, bpf@vger.kernel.org,
	"Martin KaFai Lau" <kafai@fb.com>,
	"Song Liu" <songliubraving@fb.com>, "Yonghong Song" <yhs@fb.com>,
	"John Fastabend" <john.fastabend@gmail.com>,
	"KP Singh" <kpsingh@chromium.org>, "Daniel Xu" <dxu@dxuuu.xyz>,
	"Steven Rostedt" <rostedt@goodmis.org>,
	"Jesper Brouer" <jbrouer@redhat.com>,
	"Toke Høiland-Jørgensen" <toke@redhat.com>,
	"Viktor Malik" <vmalik@redhat.com>
Subject: Re: [RFC bpf-next 07/16] kallsyms: Use rb tree for kallsyms name search
Date: Thu, 29 Oct 2020 10:29:53 +0100	[thread overview]
Message-ID: <20201029092953.GA3027684@krava> (raw)
In-Reply-To: <20201028211502.ishg56ogvjuj7t4w@ast-mbp.dhcp.thefacebook.com>

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 :-\

jirka