[PATCH] ftrace: Avoid quadratic symbol lookups in ftrace_module_enable()

[PATCH] ftrace: Avoid quadratic symbol lookups in ftrace_module_enable()

[Lawrence Lin via B4 Relay]

From: Lawrence Lin <deduce@gmail.com>

Since commit b39181f7c690 ("ftrace: Add FTRACE_MCOUNT_MAX_OFFSET to avoid
adding weak function"), ftrace_module_enable() calls test_for_valid_rec()
for every ftrace record of a module being loaded. test_for_valid_rec()
resolves the record address with kallsyms_lookup(), and for a module
address find_kallsyms_symbol() scans the whole symbol table of the module.
Loading a module therefore costs O(records * symbols), all of it under
ftrace_lock.

For large drivers this dominates module load time. amdgpu.ko has 16821
ftrace records and about 67000 defined symbols. On a Ryzen 3 3200U
(x86_64, v7.2.5, amdgpu loaded from the initramfs), amdgpu finishes
initializing 6.2 s into boot without this patch and 1.8 s with it, and
the kernel part of boot reported by systemd-analyze drops from 6.87 s to
2.47 s (four boots each). Loading radeon and nouveau, which have no
hardware on that machine, goes from 170 ms to 87 ms and from 520 ms to
145 ms. Commit 4099b98203d6 ("ftrace: Fix softlockup in
ftrace_module_enable") already had to add a cond_resched() to this loop
because of amdgpu.

Instead of one lookup per record, collect the addresses of the module's
symbols once, using the same filters as find_kallsyms_symbol(), sort them
into a temporary array, and binary search it for each record. A record is
valid when the closest symbol at or below its address lies in the same
module memory region and no more than FTRACE_MCOUNT_MAX_OFFSET below it,
which is exactly what test_for_valid_rec() checks. If the array cannot be
allocated, the per-record lookup is used as before.

An earlier attempt [1] sorted the module symbol table itself to speed up
every lookup. Its review pointed out that livepatch relocations index into
that table, that the sort is not stable for aliases, and that data
symbols and weak functions need care. This change leaves the symbol table
untouched and only compares addresses, applying the same filters as
find_kallsyms_symbol(), so none of these apply.

[1] https://lore.kernel.org/all/20260327110005.16499-2-stf_xl@wp.pl/

Fixes: b39181f7c690 ("ftrace: Add FTRACE_MCOUNT_MAX_OFFSET to avoid adding weak function")
Assisted-by: Claude:claude-opus-5-5
Signed-off-by: Lawrence Lin <deduce@gmail.com>
---
Tested on x86_64 (Ryzen 3 3200U, amdgpu):

- v7.2.5, with and without the patch, same config: the boot numbers
  above, and an identical available_filter_functions (85769 entries,
  16821 of them in amdgpu).
- v7.3-rc5 with a debug build that runs test_for_valid_rec() and the new
  check side by side for every record: 141 modules loaded at boot plus
  the selftest modules, and no record on which the two disagree.
- v7.3-rc5, with and without the patch: the ftrace selftests (159
  passed, 0 failed, the same unresolved and xfail cases on both), all
  eight livepatch selftests, samples/livepatch loaded, disabled and
  unloaded, and FTRACE_STARTUP_TEST.
- ftrace.o builds without warnings at W=1 for x86_64 (KALLSYMS_ALL=y
  and =n, MODULES=n, LIVEPATCH=y), ppc64le, and arm64, which does not
  define FTRACE_MCOUNT_MAX_OFFSET and keeps the existing path.

Not tested: running on powerpc, the other architecture that defines
FTRACE_MCOUNT_MAX_OFFSET, and building 32-bit powerpc (the cross
toolchain used here could not enable the function tracer).

This follows Petr's suggestion of a separate sorted array from the
review of [1], kept local to ftrace. Stanislaw, Cc'd as the author of
that series.
---
 kernel/trace/ftrace.c | 127 +++++++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 126 insertions(+), 1 deletion(-)

diff --git a/kernel/trace/ftrace.c b/kernel/trace/ftrace.c
index 673a54fdf392..36c97c605fb5 100644
--- a/kernel/trace/ftrace.c
+++ b/kernel/trace/ftrace.c
@@ -18,6 +18,7 @@
 #include <linux/clocksource.h>
 #include <linux/sched/task.h>
 #include <linux/kallsyms.h>
+#include <linux/module_symbol.h>
 #include <linux/security.h>
 #include <linux/seq_file.h>
 #include <linux/tracefs.h>
@@ -4385,6 +4386,109 @@ static int test_for_valid_rec(struct dyn_ftrace *rec)
 	return 1;
 }
 
+#if defined(CONFIG_MODULES) && defined(CONFIG_KALLSYMS)
+#define FTRACE_MOD_SYMS
+/*
+ * test_for_valid_rec() resolves an address with kallsyms_lookup(), which
+ * scans the whole symbol table of a module. Calling it for every record of
+ * a module being loaded costs O(records * symbols): several seconds for a
+ * driver as large as amdgpu, all of it under ftrace_lock. Sort the symbol
+ * addresses of the module once instead and binary search them. The module
+ * symbol table itself is left untouched, as livepatch relies on its order.
+ */
+struct ftrace_mod_syms {
+	unsigned long *addrs;
+	unsigned int nr;
+};
+
+static int ftrace_cmp_addr(const void *a, const void *b)
+{
+	unsigned long x = *(const unsigned long *)a;
+	unsigned long y = *(const unsigned long *)b;
+
+	return x < y ? -1 : x > y;
+}
+
+/* Collect the symbols find_kallsyms_symbol() would consider. */
+static void ftrace_mod_syms_init(struct ftrace_mod_syms *syms,
+				 struct module *mod)
+{
+	/* A coming module cannot have its kallsyms replaced under us. */
+	struct mod_kallsyms *kallsyms = rcu_dereference_raw(mod->kallsyms);
+	unsigned int i;
+
+	syms->nr = 0;
+	syms->addrs = kvmalloc_array(kallsyms->num_symtab,
+				     sizeof(*syms->addrs), GFP_KERNEL);
+	if (!syms->addrs)
+		return;
+
+	for (i = 1; i < kallsyms->num_symtab; i++) {
+		const Elf_Sym *sym = &kallsyms->symtab[i];
+		const char *name = kallsyms->strtab + sym->st_name;
+
+		if (sym->st_shndx == SHN_UNDEF || *name == '\0' ||
+		    is_mapping_symbol(name))
+			continue;
+		syms->addrs[syms->nr++] = kallsyms_symbol_value(sym);
+	}
+
+	sort(syms->addrs, syms->nr, sizeof(*syms->addrs), ftrace_cmp_addr, NULL);
+}
+
+/* Same answer as test_for_valid_rec(), using the sorted addresses. */
+static int test_for_valid_mod_rec(struct ftrace_mod_syms *syms,
+				  struct module *mod, struct dyn_ftrace *rec)
+{
+	unsigned long ip = rec->ip, base, best;
+	unsigned int lo = 0, hi = syms->nr, mid;
+	struct module_memory *mod_mem = NULL;
+
+	if (!syms->addrs)
+		return test_for_valid_rec(rec);
+
+	for_each_mod_mem_type(type) {
+#ifndef CONFIG_KALLSYMS_ALL
+		if (!mod_mem_type_is_text(type))
+			continue;
+#endif
+		if (within_module_mem_type(ip, mod, type)) {
+			mod_mem = &mod->mem[type];
+			break;
+		}
+	}
+	if (!mod_mem)
+		goto invalid;
+	base = (unsigned long)mod_mem->base;
+
+	/* Find the last symbol at or below ip. */
+	while (lo < hi) {
+		mid = lo + (hi - lo) / 2;
+		if (syms->addrs[mid] <= ip)
+			lo = mid + 1;
+		else
+			hi = mid;
+	}
+	if (!lo)
+		goto invalid;
+	best = syms->addrs[lo - 1];
+
+	/* Weak functions can cause invalid addresses */
+	if (best < base || ip - best > FTRACE_MCOUNT_MAX_OFFSET)
+		goto invalid;
+	return 1;
+
+invalid:
+	rec->flags |= FTRACE_FL_DISABLED;
+	return 0;
+}
+
+static void ftrace_mod_syms_free(struct ftrace_mod_syms *syms)
+{
+	kvfree(syms->addrs);
+}
+#endif
+
 static struct workqueue_struct *ftrace_check_wq __initdata;
 static struct work_struct ftrace_check_work __initdata;
 
@@ -8010,11 +8114,30 @@ void ftrace_release_mod(struct module *mod)
 	}
 }
 
+#ifndef FTRACE_MOD_SYMS
+struct ftrace_mod_syms { };
+
+static inline void ftrace_mod_syms_init(struct ftrace_mod_syms *syms,
+					struct module *mod) { }
+
+static inline int test_for_valid_mod_rec(struct ftrace_mod_syms *syms,
+					 struct module *mod,
+					 struct dyn_ftrace *rec)
+{
+	return test_for_valid_rec(rec);
+}
+
+static inline void ftrace_mod_syms_free(struct ftrace_mod_syms *syms) { }
+#endif
+
 void ftrace_module_enable(struct module *mod)
 {
+	struct ftrace_mod_syms syms;
 	struct dyn_ftrace *rec;
 	struct ftrace_page *pg;
 
+	ftrace_mod_syms_init(&syms, mod);
+
 	mutex_lock(&ftrace_lock);
 
 	if (ftrace_disabled)
@@ -8050,7 +8173,7 @@ void ftrace_module_enable(struct module *mod)
 		cond_resched();
 
 		/* Weak functions should still be ignored */
-		if (!test_for_valid_rec(rec)) {
+		if (!test_for_valid_mod_rec(&syms, mod, rec)) {
 			/* Clear all other flags. Should not be enabled anyway */
 			rec->flags = FTRACE_FL_DISABLED;
 			continue;
@@ -8087,6 +8210,8 @@ void ftrace_module_enable(struct module *mod)
  out_unlock:
 	mutex_unlock(&ftrace_lock);
 
+	ftrace_mod_syms_free(&syms);
+
 	process_cached_mods(mod->name);
 }
 

---
base-commit: e767a4ea70a3992c37ed604157d32f0dfbf9b1e3
change-id: 20261003-ftrace-mod-bsearch-534a86527ee5

Best regards,
--  
Lawrence Lin <deduce@gmail.com>

Re: [PATCH] ftrace: Avoid quadratic symbol lookups in ftrace_module_enable()

[Lawrence Lin]

Krzysztof Wilczyński reviewed this off-list while looking at carrying it
in a distribution kernel, and raised two points. I'd like to bring them
here, with numbers, before sending a v2. Cc'ing him.

1. ftrace_cmp_addr() duplicates ftrace_cmp_ips().

Agreed. For v2 I have dropped ftrace_cmp_addr() and moved
ftrace_cmp_ips() up, above the FTRACE_MCOUNT_MAX_OFFSET block, so that
ftrace_process_locs() still sees it on architectures that don't define
FTRACE_MCOUNT_MAX_OFFSET. That builds on x86_64 and arm64, and on x86_64
with CONFIG_MODULES=n.

2. Should the sort use sort_nonatomic()?

I timed the collection and the sort with ktime_get_ns() on a Ryzen 3
3200U (v7.3-rc5 plus this patch, debug printk only):

  module     addresses   collect     sort()
  amdgpu        64983    0.41 ms    36.4 ms
  mac80211       8199    0.11 ms    12.0 ms
  nouveau       19354    0.06 ms     9.6 ms
  kvm            7993    0.07 ms     7.9 ms
  radeon         9882    0.03 ms     4.6 ms
  all 141 modules loaded at boot:
                         1.09 ms    94.3 ms

So the sort dominates the new code, and amdgpu spends 36 ms in it.
It runs in ftrace_module_enable() before ftrace_lock is taken, so it is
sleepable and is preempted normally under full or lazy preemption.
What it does not have is a resched point, which only matters for
PREEMPT_NONE and PREEMPT_VOLUNTARY. sort_nonatomic() would add one, but
commit 340e3c5165d4 ("iommu/arm-smmu-v3: Replace sort_nonatomic() with
sort()") removed its last caller with the intent of dropping it, so I'd
rather not add a user. For comparison, the lookups this replaces took
about 4 s for amdgpu on this machine under ftrace_lock, and needed the
cond_resched() from commit 4099b98203d6 ("ftrace: Fix softlockup in
ftrace_module_enable").

Is 36 ms without a resched point acceptable here, or would you prefer
something else?

For reference, the cold-boot A/B with v1 and the v2 change, on the same
machine with a distribution kernel (linux-omarchy 7.2.5, amdgpu from the
initramfs, three boots each):

                     stock     v1        v2
  amdgpu probed      6.17 s    2.03 s    2.03 s
  kernel (systemd)   6.64 s    2.48 s    2.50 s
  modprobe radeon    155 ms     83 ms     83 ms
  modprobe nouveau   468 ms    141 ms    138 ms

(medians; radeon and nouveau have no device on this machine). The list
of functions in available_filter_functions is identical across the three
(84301 entries), and none of the boots logged a warning or soft lockup.

The same three kernels on a faster machine, a Ryzen AI MAX+ 395
(Strix Halo), three boots each:

                     stock     v1        v2
  amdgpu probed      4.84 s    3.80 s    3.81 s
  modprobe radeon     47 ms     32 ms     32 ms
  modprobe nouveau   130 ms     60 ms     59 ms

The saving is smaller there, about 1 s for amdgpu rather than 4 s, as
expected with a cheaper per-symbol lookup. available_filter_functions is
again identical across the three (84676 entries), and no boot logged a
warning or soft lockup. The systemd kernel time is left out because on
this machine it includes a LUKS passphrase prompt.

Unless there are other comments, I'll send v2 with the change in (1)
and these numbers in the changelog in a few days.

Thanks,
Lawrence

Re: [PATCH] ftrace: Avoid quadratic symbol lookups in ftrace_module_enable()

[David Laight]

On Sat, 03 Oct 2026 11:27:10 -0500
Lawrence Lin via B4 Relay <devnull+deduce.gmail.com@kernel.org> wrote:

> From: Lawrence Lin via B4 Relay <devnull+deduce.gmail.com@kernel.org>
> To: Steven Rostedt <rostedt@goodmis.org>,   Masami Hiramatsu <mhiramat@kernel.org>, Mark Rutland <mark.rutland@arm.com>,   Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
> Cc: Petr Pavlu <petr.pavlu@suse.com>, linux-modules@vger.kernel.org,   Stanislaw Gruszka <stf_xl@wp.pl>, linux-kernel@vger.kernel.org,   linux-trace-kernel@vger.kernel.org, Lawrence Lin <deduce@gmail.com>
> Subject: [PATCH] ftrace: Avoid quadratic symbol lookups in  ftrace_module_enable()
> Date: Sat, 03 Oct 2026 11:27:10 -0500
> Reply-To: deduce@gmail.com
> 
> From: Lawrence Lin <deduce@gmail.com>
> 
> Since commit b39181f7c690 ("ftrace: Add FTRACE_MCOUNT_MAX_OFFSET to avoid
> adding weak function"), ftrace_module_enable() calls test_for_valid_rec()
> for every ftrace record of a module being loaded. test_for_valid_rec()
> resolves the record address with kallsyms_lookup(), and for a module
> address find_kallsyms_symbol() scans the whole symbol table of the module.
> Loading a module therefore costs O(records * symbols), all of it under
> ftrace_lock.
> 
> For large drivers this dominates module load time. amdgpu.ko has 16821
> ftrace records and about 67000 defined symbols. On a Ryzen 3 3200U
> (x86_64, v7.2.5, amdgpu loaded from the initramfs), amdgpu finishes
> initializing 6.2 s into boot without this patch and 1.8 s with it, and
> the kernel part of boot reported by systemd-analyze drops from 6.87 s to
> 2.47 s (four boots each). Loading radeon and nouveau, which have no
> hardware on that machine, goes from 170 ms to 87 ms and from 520 ms to
> 145 ms. Commit 4099b98203d6 ("ftrace: Fix softlockup in
> ftrace_module_enable") already had to add a cond_resched() to this loop
> because of amdgpu.
> 
> Instead of one lookup per record, collect the addresses of the module's
> symbols once, using the same filters as find_kallsyms_symbol(), sort them
> into a temporary array, and binary search it for each record. A record is
> valid when the closest symbol at or below its address lies in the same
> module memory region and no more than FTRACE_MCOUNT_MAX_OFFSET below it,
> which is exactly what test_for_valid_rec() checks. If the array cannot be
> allocated, the per-record lookup is used as before.
> 
> An earlier attempt [1] sorted the module symbol table itself to speed up
> every lookup. Its review pointed out that livepatch relocations index into
> that table, that the sort is not stable for aliases, and that data
> symbols and weak functions need care. This change leaves the symbol table
> untouched and only compares addresses, applying the same filters as
> find_kallsyms_symbol(), so none of these apply.

Surely it would be better to add the sorted index as part of module load
so that all symbol lookups could make use of it?

I think the existing symbols are in an array, so you can reduce the data
size significantly by saving an index rather than a pointer.
With enough __packed you can use an array of 'unsigned int idx:24' so that
each index is only three bytes (rather than 8 for a pointer).

There are also places where the symbols are looked up by name.
That needs a second sorted index table.
Although alphabetically sorting the names during build might be possible
and doesn't have the same problems as sorting by value.

David

> 
> [1] https://lore.kernel.org/all/20260327110005.16499-2-stf_xl@wp.pl/
> 
> Fixes: b39181f7c690 ("ftrace: Add FTRACE_MCOUNT_MAX_OFFSET to avoid adding weak function")
> Assisted-by: Claude:claude-opus-5-5
> Signed-off-by: Lawrence Lin <deduce@gmail.com>
> ---

Re: [PATCH] ftrace: Avoid quadratic symbol lookups in ftrace_module_enable()

[Lawrence Lin]

On Sun, 4 Oct 2026 10:00:30 +0100, David Laight wrote:
> Surely it would be better to add the sorted index as part of module load
> so that all symbol lookups could make use of it?

A sorted index used by every lookup is roughly what [1] tried, and its
review showed what that involves: aliases, livepatch's references into
the symbol table, and the lookups by name. I'd rather leave that to the
module maintainers.

For this problem, Steve's reply suggests something smaller. The weak
locations can be dropped once at module load, so ftrace no longer looks
up symbols per record, and no index is needed. I'm prototyping that now.

Re: [PATCH] ftrace: Avoid quadratic symbol lookups in ftrace_module_enable()

[Steven Rostedt]

On Sat, 03 Oct 2026 11:27:10 -0500
Lawrence Lin via B4 Relay <devnull+deduce.gmail.com@kernel.org> wrote:

> From: Lawrence Lin <deduce@gmail.com>
> 
> Since commit b39181f7c690 ("ftrace: Add FTRACE_MCOUNT_MAX_OFFSET to avoid
> adding weak function"), ftrace_module_enable() calls test_for_valid_rec()
> for every ftrace record of a module being loaded. test_for_valid_rec()
> resolves the record address with kallsyms_lookup(), and for a module
> address find_kallsyms_symbol() scans the whole symbol table of the module.
> Loading a module therefore costs O(records * symbols), all of it under
> ftrace_lock.

Honestly, I think we can revert commit b39181f7c690.

Since commit ef378c3b823385 ("scripts/sorttable: Zero out weak
functions in mcount_loc table"), I believe that commit has become
obsolete. I just kept it because I didn't want to add regressions.

It would be interesting if it actually triggers (finds something). If
it doesn't, then I think we should just remove that code instead of
adding more complexity to it.

-- Steve

Re: [PATCH] ftrace: Avoid quadratic symbol lookups in ftrace_module_enable()

[Lawrence Lin]

On Sun, 4 Oct 2026 05:09:04 -0400, Steven Rostedt wrote:
> It would be interesting if it actually triggers (finds something). If
> it doesn't, then I think we should just remove that code instead of
> adding more complexity to it.

It does trigger, but only for modules. On x86_64 v7.2.5 with kvm loaded,
available_filter_functions has 18 __ftrace_invalid_address___ entries,
all of them in [kvm] and none in vmlinux. Each one is a __weak default
from virt/kvm/ (kvm_arch_vm_compat_ioctl, kvm_arch_shutdown,
kvm_arch_dy_runnable, ...) that arch/x86/kvm/ overrides inside the same
kvm.ko. In kvm.ko, no symbol covers any of the 18 addresses, and each
body is a stub that returns, returns a constant, or tail calls.

ef378c3b823385 fixed this for vmlinux at build time, but sorttable only
runs on vmlinux, so modules still depend on the check. In its changelog
you wrote that "the real solution is to not add a weak function into
the ftrace table in the first place". For modules, that can be done at
load time, and it would make this patch much smaller.

ftrace_module_init() runs after the module's symbols are set up and
before any record exists, and ftrace_process_locs() already sorts the
module's locations and skips zero entries. A location is valid exactly
when some symbol, under the filters find_kallsyms_symbol() applies, lies
within FTRACE_MCOUNT_MAX_OFFSET below it. So one pass over the module's
symbols, with a binary search of the sorted locations for each symbol,
can mark the valid locations in a bitmap, one bit per location. The
remaining locations can then be zeroed before the records are created.
ftrace_module_enable() would then drop its test_for_valid_rec() call,
and the weak stubs would disappear from available_filter_functions the
same way they did for vmlinux.

That keeps the work out of ftrace_lock, avoids sorting the symbols and
replaces the 500 KB array with a bitmap of a few KB, at the cost of a
small iterator in kernel/module/kallsyms.c, since the symbol filters
live there.

Would you take a v2 along those lines? I'm starting a prototype now and
will measure it on the same machine with the same boots as v1. Then
I'll post the numbers with the v2.