Re: [RFC PATCH] ftrace: speed up module enable by binary searching module symbols

[Yaxiong Tian]

On 2026/10/17 02:07, Steven Rostedt wrote:
> On Wed, 16 Sep 2026 16:27:15 +0800
> Yaxiong Tian <tianyaxiong@xxxxxxxxxx> wrote:
>
> Hi Yaxiong,
>
> I've been traveling since September 14th to October 10th and my backlog is
> very long. Unfortunately, I will not be able to look at this patch until
> after the merge window. But it is not forgotten, just postponed.
>
> -- Steve
>
Thanks for letting me know — completely understandable. No rush; I'll
wait until after the merge window. Looking forward to your feedback when
you get to it.


>
>> Loading a module with many functions takes seconds, almost all of it in
>> ftrace_module_enable().  amdgpu modules stall for about ten seconds, and
>> disabling CONFIG_DYNAMIC_FTRACE makes the stall disappear.
>>
>> Every record is validated by test_for_valid_rec(), which resolves its ip
>> through kallsyms_lookup(); for a module address that ends up in
>> find_kallsyms_symbol(), which walks the whole module symbol table from
>> index 1.  The core kernel instead binary searches its sorted kallsyms
>> table in get_symbol_pos().  So only modules pay, and the cost is
>> quadratic: both the record count and the symbol count grow with the
>> module.  An amdgpu.ko from this tree has 17282 records and 55332 symbol
>> table entries.
>>
>> Fix this by collecting the addresses of a module's symbols once, sorting
>> them, and binary searching that array instead of walking the table once
>> per record; a loaded module's symbol table cannot change, so the array
>> stays valid for the whole pass.  What comes back is what the linear scan
>> returned: the same entries are skipped - SHN_UNDEF, unnamed and mapping
>> symbols - and the closest address not below the base of the record's
>> memory region is taken.  Whenever the array cannot answer, because it
>> could not be built or because no such symbol exists, the record is handed
>> to test_for_valid_rec(), so the rest of kallsyms_lookup() still has its
>> say and no verdict can change.
>>
>> On the machine that reported the stall, modprobe of that amdgpu.ko takes
>> 12.242 s before and 2.870 s after, and the time spent inside ftrace_lock
>> drops from 9.368 s to 1.585 ms - 15.195 ms if the price of building the
>> array is included, that build being 13.6 ms, 0.15% of the 9.37 s saved.
>> The array costs O(symbols * log symbols), it does not grow with the
>> record count.  Across the 74 modules loaded at boot, total lock time
>> drops from 491 ms to 2.33 ms.
>>
>> Signed-off-by: Yaxiong Tian <tianyaxiong@xxxxxxxxxx>