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

From
Andrii Nakryiko <hidden>
Date
2020-10-29 22:46:09
Also in
bpf
Reply to
Jiri Olsa, 2020-10-29
On Thu, Oct 29, 2020 at 2:31 AM Jiri Olsa [off-list ref] wrote:
On Wed, Oct 28, 2020 at 02:15:02PM -0700, Alexei Starovoitov wrote:
quoted
On Wed, Oct 28, 2020 at 07:25:34PM +0100, Jiri Olsa wrote:
quoted
On Thu, Oct 22, 2020 at 10:21:29AM +0200, Jiri Olsa wrote:
quoted
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
Thread (47 messages) 47 messages, 5 authors, last reply 2020-10-29
Keyboard shortcuts
hback out one level
jnext message in thread / next series-diff position
kprevious message in thread / previous series-diff position
ldrill in
Escclose help / fold thread tree
?toggle this help