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@xxxxxxxxxx/ 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
