netdev - Re: [PATCHv3 bpf-next 09/13] libbpf: Add bpf_program__attach_kprobe_multi

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]

Message-ID: <YjRPZj6Z8vuLeEZo@krava>
Date:   Fri, 18 Mar 2022 10:22:46 +0100
From:   Jiri Olsa <olsajiri@...il.com>
To:     Andrii Nakryiko <andrii.nakryiko@...il.com>
Cc:     Alexei Starovoitov <alexei.starovoitov@...il.com>,
        Jiri Olsa <jolsa@...nel.org>,
        Alexei Starovoitov <ast@...nel.org>,
        Daniel Borkmann <daniel@...earbox.net>,
        Andrii Nakryiko <andrii@...nel.org>,
        Masami Hiramatsu <mhiramat@...nel.org>,
        Network Development <netdev@...r.kernel.org>,
        bpf <bpf@...r.kernel.org>, lkml <linux-kernel@...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>,
        Steven Rostedt <rostedt@...dmis.org>,
        Nick Alcock <nick.alcock@...cle.com>,
        Arnaldo Carvalho de Melo <acme@...nel.org>
Subject: Re: [PATCHv3 bpf-next 09/13] libbpf: Add
 bpf_program__attach_kprobe_multi_opts function

On Thu, Mar 17, 2022 at 10:14:28PM -0700, Andrii Nakryiko wrote:

SNIP

> > But the above needs more work.
> > Currently test_progs -t kprobe_multi
> > takes 4 seconds on lockdep+debug kernel.
> > Mainly because of the above loop.
> >
> >     18.05%  test_progs       [kernel.kallsyms]   [k]
> > kallsyms_expand_symbol.constprop.4
> >     12.53%  test_progs       libc-2.28.so        [.] _IO_vfscanf
> >      6.31%  test_progs       [kernel.kallsyms]   [k] number
> >      4.66%  test_progs       [kernel.kallsyms]   [k] format_decode
> >      4.65%  test_progs       [kernel.kallsyms]   [k] string_nocheck
> >
> > Single test_skel_api() subtest takes almost a second.
> >
> > A cache inside libbpf probably won't help.
> > Maybe introduce a bpf iterator for kallsyms?
> 
> BPF iterator for kallsyms is a great idea! So many benefits:

>   - it should be significantly more efficient *and* simpler than
> parsing /proc/kallsyms;
>   - there were some upstream patches recording ksym length (i.e.,
> function size), don't remember if that ever landed or not, but besides
> that the other complication of even exposing that to user space were
> concerns about /proc/kallsyms format being an ABI. With the BPF
> iterator we can easily provide that symbol size without any breakage.
> This would be great!

yes, great idea.. I was cc-ed on patches adding extra stuff to kallsyms:
  https://lore.kernel.org/lkml/20220208184309.148192-7-nick.alcock@oracle.com/

this could be way out ;-) cc-ing Nick

>   - we can allow parameterizing iterator with options like: skip or
> include module symbols, specify a set of types of symbols (function,
> variable, etc), etc. This would speed everything up in common cases by
> not even decompressing irrelevant names.
> 
> In short, kallsyms iterator would be an immensely useful for any sort
> of tracing tool that deals with kernel stack traces or kallsyms in
> general.

I wonder we could make some use of it in perf as well, there's some
guessing wrt symbol sizes when we parse kallsyms, so we could get
rid of it.. I will work on that and try to add this

> 
> But in this particular case, kprobe_multi_resolve_syms()
> implementation is extremely suboptimal. I didn't realize during review
> that kallsyms_lookup_name() is a linear scan... If that's not going to
> be changed to O(log(N)) some time soon, we need to reimplement
> kprobe_multi_resolve_syms(), probably.
> 
> One way would be to sort user strings lexicographically and then do a
> linear scan over all kallsyms, for each symbol perform binary search
> over a sorted array of user strings. Stop once all the positions were
> "filled in" (we'd need to keep a bitmap or bool[], probably). This way
> it's going to be O(MlogN) instead of O(MN) as it is right now.

ok, I did something similar in multi-trampoline patchset that you
suggested, I think that will work here as well

> 
> BTW, Jiri, libbpf.map is supposed to have an alphabetically ordered
> list of functions, it would be good to move
> bpf_program__attach_kprobe_multi_opts a bit higher before libbpf_*
> functions.

ah right, sry.. I'll send fix with follow up changes

thanks,
jirka