On Sat, 03 Oct 2026 11:27:10 -0500 Lawrence Lin via B4 Relay <[email protected]> wrote:
> From: Lawrence Lin via B4 Relay <[email protected]> > To: Steven Rostedt <[email protected]>, Masami Hiramatsu > <[email protected]>, Mark Rutland <[email protected]>, Mathieu > Desnoyers <[email protected]> > Cc: Petr Pavlu <[email protected]>, [email protected], > Stanislaw Gruszka <[email protected]>, [email protected], > [email protected], Lawrence Lin <[email protected]> > Subject: [PATCH] ftrace: Avoid quadratic symbol lookups in > ftrace_module_enable() > Date: Sat, 03 Oct 2026 11:27:10 -0500 > Reply-To: [email protected] > > From: Lawrence Lin <[email protected]> > > 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/[email protected]/ > > 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 <[email protected]> > ---
