Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20;
Date:   Fri, 18 Mar 2022 10:22:46 +0100
From:   Jiri Olsa <olsajiri@gmail.com>
To:     Andrii Nakryiko <andrii.nakryiko@gmail.com>
Cc:     Alexei Starovoitov <alexei.starovoitov@gmail.com>,
        Jiri Olsa <jolsa@kernel.org>,
        Alexei Starovoitov <ast@kernel.org>,
        Daniel Borkmann <daniel@iogearbox.net>,
        Andrii Nakryiko <andrii@kernel.org>,
        Masami Hiramatsu <mhiramat@kernel.org>,
        Network Development <netdev@vger.kernel.org>,
        bpf <bpf@vger.kernel.org>, lkml <linux-kernel@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>,
        Steven Rostedt <rostedt@goodmis.org>,
        Nick Alcock <nick.alcock@oracle.com>,
        Arnaldo Carvalho de Melo <acme@kernel.org>
Subject: Re: [PATCHv3 bpf-next 09/13] libbpf: Add
 bpf_program__attach_kprobe_multi_opts function
Message-ID: <YjRPZj6Z8vuLeEZo@krava>
References: <20220316122419.933957-1-jolsa@kernel.org>
 <20220316122419.933957-10-jolsa@kernel.org>
 <CAADnVQ+tNLEtbPY+=sZSoBicdSTx1YLgZJwnNuhnBkUcr5xozQ@mail.gmail.com>
 <CAEf4BzZtQaiUxQ-sm_hH2qKPRaqGHyOfEsW96DxtBHRaKLoL3Q@mail.gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <CAEf4BzZtQaiUxQ-sm_hH2qKPRaqGHyOfEsW96DxtBHRaKLoL3Q@mail.gmail.com>
Precedence: bulk

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