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@xxxxxxxxxx> wrote:

> From: Lawrence Lin via B4 Relay <devnull+deduce.gmail.com@xxxxxxxxxx>
> To: Steven Rostedt <rostedt@xxxxxxxxxxx>,   Masami Hiramatsu <mhiramat@xxxxxxxxxx>, Mark Rutland <mark.rutland@xxxxxxx>,   Mathieu Desnoyers <mathieu.desnoyers@xxxxxxxxxxxx>
> Cc: Petr Pavlu <petr.pavlu@xxxxxxxx>, linux-modules@xxxxxxxxxxxxxxx,   Stanislaw Gruszka <stf_xl@xxxxx>, linux-kernel@xxxxxxxxxxxxxxx,   linux-trace-kernel@xxxxxxxxxxxxxxx, Lawrence Lin <deduce@xxxxxxxxx>
> Subject: [PATCH] ftrace: Avoid quadratic symbol lookups in  ftrace_module_enable()
> Date: Sat, 03 Oct 2026 11:27:10 -0500
> Reply-To: deduce@xxxxxxxxx
> 
> From: Lawrence Lin <deduce@xxxxxxxxx>
> 
> 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@xxxxx/
> 
> 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@xxxxxxxxx>
> ---