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

From
Jiri Olsa <hidden>
Date
2020-10-29 09:34:02
Also in
bpf
Reply to
Andrii Nakryiko, 2020-10-28
On Wed, Oct 28, 2020 at 03:40:46PM -0700, Andrii Nakryiko wrote:
On Wed, Oct 28, 2020 at 3:29 PM Jiri Olsa [off-list ref] 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
what about kernel modules then?
please check my answer to Alexei, I just answered it there

thanks,
jirka
quoted
jirka
quoted
---
 kernel/kallsyms.c | 95 ++++++++++++++++++++++++++++++++++++++++++-----
 1 file changed, 86 insertions(+), 9 deletions(-)
[...]
  
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