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.