[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()

[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