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

On Sat, 03 Oct 2026 11:27:10 -0500
Lawrence Lin via B4 Relay [off-list ref] 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 <redacted>
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 <redacted>

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/ (local)

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 <redacted>
---