[for-next][PATCH] ftrace: Use kallsyms binary search for single-symbol lookup

[Steven Rostedt]

  git://git.kernel.org/pub/scm/linux/kernel/git/trace/linux-trace.git
ftrace/for-next

Head SHA1: 93e8fd1a565eb5d0c0bbcb18d00095ad255b6ecb


Andrey Grodzovsky (1):
      ftrace: Use kallsyms binary search for single-symbol lookup

----
 kernel/trace/ftrace.c | 22 ++++++++++++++++++++++
 1 file changed, 22 insertions(+)
---------------------------
commit 93e8fd1a565eb5d0c0bbcb18d00095ad255b6ecb
Author: Andrey Grodzovsky <andrey.grodzovsky@xxxxxxxxxxxxxxx>
Date:   Mon Mar 2 15:08:36 2026 -0500

    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@xxxxxxxxxxxxxxx>
    Link: https://patch.msgid.link/20260302200837.317907-3-andrey.grodzovsky@xxxxxxxxxxxxxxx
    Signed-off-by: Andrey Grodzovsky <andrey.grodzovsky@xxxxxxxxxxxxxxx>
    Signed-off-by: Steven Rostedt (Google) <rostedt@xxxxxxxxxxx>

diff --git a/kernel/trace/ftrace.c b/kernel/trace/ftrace.c
index 413310912609..7eac1472cc57 100644
--- a/kernel/trace/ftrace.c
+++ b/kernel/trace/ftrace.c
@@ -9267,6 +9267,15 @@ static int kallsyms_callback(void *data, const char *name, unsigned long addr)
  * @addrs array, which needs to be big enough to store at least @cnt
  * addresses.
  *
+ * For a single symbol (cnt == 1), uses kallsyms_lookup_name() which
+ * performs an O(log N) binary search via the sorted kallsyms index.
+ * This avoids the full O(N) linear scan over all kernel symbols that
+ * the multi-symbol path requires.
+ *
+ * For multiple symbols, uses a single-pass linear scan via
+ * kallsyms_on_each_symbol() with binary search into the sorted input
+ * array.
+ *
  * Returns: 0 if all provided symbols are found, -ESRCH otherwise.
  */
 int ftrace_lookup_symbols(const char **sorted_syms, size_t cnt, unsigned long *addrs)
@@ -9274,6 +9283,19 @@ int ftrace_lookup_symbols(const char **sorted_syms, size_t cnt, unsigned long *a
 	struct kallsyms_data args;
 	int found_all;
 
+	/* Fast path: single symbol uses O(log N) binary search */
+	if (cnt == 1) {
+		addrs[0] = kallsyms_lookup_name(sorted_syms[0]);
+		if (addrs[0] && ftrace_location(addrs[0]))
+			return 0;
+		/*
+		 * Binary lookup can fail for duplicate symbol names
+		 * where the first match is not ftrace-instrumented.
+		 * Retry with linear scan.
+		 */
+	}
+
+	/* Batch path: single-pass O(N) linear scan */
 	memset(addrs, 0, sizeof(*addrs) * cnt);
 	args.addrs = addrs;
 	args.syms = sorted_syms;