]> git.ipfire.org Git - thirdparty/linux.git/commit
ftrace: Use kallsyms binary search for single-symbol lookup
authorAndrey Grodzovsky <andrey.grodzovsky@crowdstrike.com>
Mon, 2 Mar 2026 20:08:36 +0000 (15:08 -0500)
committerSteven Rostedt (Google) <rostedt@goodmis.org>
Wed, 1 Apr 2026 20:58:36 +0000 (16:58 -0400)
commit93e8fd1a565eb5d0c0bbcb18d00095ad255b6ecb
treebf651a854cc548e815b5be82e626e9adaf4f91b2
parentc369299895a591d96745d6492d4888259b004a9e
ftrace: Use kallsyms binary search for single-symbol lookup

When ftrace_lookup_symbols() is called with a single symbol (cnt == 1),
use kallsyms_lookup_name() for O(log N) binary search instead of the
full linear scan via kallsyms_on_each_symbol().

ftrace_lookup_symbols() was designed for batch resolution of many
symbols in a single pass.  For large cnt this is efficient: a single
O(N) walk over all symbols with O(log cnt) binary search into the
sorted input array.  But for cnt == 1 it still decompresses all ~200K
kernel symbols only to match one.

kallsyms_lookup_name() uses the sorted kallsyms index and needs only
~17 decompressions for a single lookup.

This is the common path for kprobe.session with exact function names,
where libbpf sends one symbol per BPF_LINK_CREATE syscall.

If binary lookup fails (duplicate symbol names where the first match
is not ftrace-instrumented), the function falls through to the existing
linear scan path.

Before (cnt=1, 50 kprobe.session programs):
  Attach: 858 ms  (kallsyms_expand_symbol 25% of CPU)

After:
  Attach:  52 ms  (16x faster)

Cc: <bpf@vger.kernel.org>
Link: https://patch.msgid.link/20260302200837.317907-3-andrey.grodzovsky@crowdstrike.com
Signed-off-by: Andrey Grodzovsky <andrey.grodzovsky@crowdstrike.com>
Signed-off-by: Steven Rostedt (Google) <rostedt@goodmis.org>
kernel/trace/ftrace.c