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

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

[Yaxiong Tian]

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@kylinos.cn>
---
 kernel/trace/ftrace.c | 131 +++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 130 insertions(+), 1 deletion(-)

diff --git a/kernel/trace/ftrace.c b/kernel/trace/ftrace.c
index 673a54fdf392..92ba9a4dfa69 100644
--- a/kernel/trace/ftrace.c
+++ b/kernel/trace/ftrace.c
@@ -26,6 +26,7 @@
 #include <linux/uaccess.h>
 #include <linux/bsearch.h>
 #include <linux/module.h>
+#include <linux/module_symbol.h>
 #include <linux/ftrace.h>
 #include <linux/sysctl.h>
 #include <linux/slab.h>
@@ -8010,11 +8011,137 @@ void ftrace_release_mod(struct module *mod)
 	}
 }
 
+#ifdef FTRACE_MCOUNT_MAX_OFFSET
+/*
+ * ftrace_module_enable() validates every record with test_for_valid_rec(),
+ * which walks the whole symbol table of a module for each address in it, so a
+ * large module loads in quadratic time.  Search a sorted copy of the symbol
+ * addresses instead, the way get_symbol_pos() searches the kallsyms table.
+ * The array is an accelerator only; records it cannot resolve are tested the
+ * old way, so the verdict does not change.
+ */
+struct ftrace_mod_syms {
+	unsigned int	nr;
+	unsigned long	addr[];	/* sorted, @nr entries */
+};
+
+static int ftrace_mod_syms_cmp(const void *a, const void *b)
+{
+	unsigned long va = *(const unsigned long *)a;
+	unsigned long vb = *(const unsigned long *)b;
+
+	return (va > vb) - (va < vb);
+}
+
+static struct ftrace_mod_syms *ftrace_mod_syms_alloc(struct module *mod)
+{
+	struct mod_kallsyms *kallsyms;
+	struct ftrace_mod_syms *syms;
+	unsigned int i, nr = 0;
+
+	/* mod->kallsyms is not replaced until do_init_module() returns. */
+	rcu_read_lock();
+	kallsyms = rcu_dereference(mod->kallsyms);
+	rcu_read_unlock();
+
+	if (!kallsyms || kallsyms->num_symtab < 2)
+		return NULL;
+
+	syms = kvmalloc(struct_size(syms, addr, kallsyms->num_symtab),
+			GFP_KERNEL);
+	if (!syms)
+		return NULL;
+
+	/* The symbols find_kallsyms_symbol() would consider. */
+	for (i = 1; i < kallsyms->num_symtab; i++) {
+		const Elf_Sym *sym = &kallsyms->symtab[i];
+		const char *name = kallsyms->strtab + sym->st_name;
+
+		if (sym->st_shndx == SHN_UNDEF || !*name ||
+		    is_mapping_symbol(name))
+			continue;
+
+		syms->addr[nr++] = kallsyms_symbol_value(sym);
+	}
+	syms->nr = nr;
+
+	if (nr > 1)
+		sort(syms->addr, nr, sizeof(syms->addr[0]), ftrace_mod_syms_cmp,
+		     NULL);
+
+	return syms;
+}
+
+/* The verdict test_for_valid_rec() would give, without walking the table. */
+static bool ftrace_mod_rec_is_valid(struct module *mod,
+				    const struct ftrace_mod_syms *syms,
+				    struct dyn_ftrace *rec)
+{
+	unsigned long base, best;
+	unsigned int lo, hi;
+
+	if (!syms)
+		return test_for_valid_rec(rec) != 0;
+
+	/* A record is in executable memory; anything else kallsyms answers. */
+	if (within_module_mem_type(rec->ip, mod, MOD_TEXT))
+		base = (unsigned long)mod->mem[MOD_TEXT].base;
+	else if (within_module_mem_type(rec->ip, mod, MOD_INIT_TEXT))
+		base = (unsigned long)mod->mem[MOD_INIT_TEXT].base;
+	else
+		return test_for_valid_rec(rec) != 0;
+
+	/* The closest address at or below @rec->ip, if there is one. */
+	best = 0;
+	for (lo = 0, hi = syms->nr; lo < hi; ) {
+		unsigned int mid = lo + (hi - lo) / 2;
+
+		if (syms->addr[mid] <= rec->ip)
+			lo = mid + 1;
+		else
+			hi = mid;
+	}
+	if (lo)
+		best = syms->addr[lo - 1];
+
+	/*
+	 * No symbol, or only ones below @base: let kallsyms_lookup() answer,
+	 * as it also looks in the BPF and ftrace trampoline tables.
+	 */
+	if (best < base)
+		return test_for_valid_rec(rec) != 0;
+
+	return rec->ip - best <= FTRACE_MCOUNT_MAX_OFFSET;
+}
+#else
+struct ftrace_mod_syms;
+
+static inline struct ftrace_mod_syms *ftrace_mod_syms_alloc(struct module *mod)
+{
+	return NULL;
+}
+
+static inline bool ftrace_mod_rec_is_valid(struct module *mod,
+					   const struct ftrace_mod_syms *syms,
+					   struct dyn_ftrace *rec)
+{
+	return test_for_valid_rec(rec) != 0;
+}
+#endif /* FTRACE_MCOUNT_MAX_OFFSET */
+
 void ftrace_module_enable(struct module *mod)
 {
+	struct ftrace_mod_syms *syms;
 	struct dyn_ftrace *rec;
 	struct ftrace_page *pg;
 
+	/*
+	 * Allocates, so build it before taking ftrace_lock.  It is skipped when
+	 * ftrace never came up, where the loop below would not run anyway; that
+	 * also makes reading ftrace_disabled without the lock safe.
+	 */
+	syms = ftrace_disabled ? NULL : ftrace_mod_syms_alloc(mod);
+
 	mutex_lock(&ftrace_lock);
 
 	if (ftrace_disabled)
@@ -8050,7 +8177,7 @@ void ftrace_module_enable(struct module *mod)
 		cond_resched();
 
 		/* Weak functions should still be ignored */
-		if (!test_for_valid_rec(rec)) {
+		if (!ftrace_mod_rec_is_valid(mod, syms, rec)) {
 			/* Clear all other flags. Should not be enabled anyway */
 			rec->flags = FTRACE_FL_DISABLED;
 			continue;
@@ -8087,6 +8214,8 @@ void ftrace_module_enable(struct module *mod)
  out_unlock:
 	mutex_unlock(&ftrace_lock);
 
+	kvfree(syms);
+
 	process_cached_mods(mod->name);
 }
 
-- 
2.43.0

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

[Steven Rostedt]

On Wed, 16 Sep 2026 16:27:15 +0800
Yaxiong Tian <tianyaxiong@kylinos.cn> 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



> 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@kylinos.cn>

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@kylinos.cn> 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@kylinos.cn>

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

[Masami Hiramatsu]

Hi,

On Wed, 16 Sep 2026 16:27:15 +0800, Yaxiong Tian <tianyaxiong@kylinos.cn> wrote:

> diff --git a/kernel/trace/ftrace.c b/kernel/trace/ftrace.c
> --- a/kernel/trace/ftrace.c
> +++ b/kernel/trace/ftrace.c
> @@ -8010,11 +8011,137 @@ void ftrace_release_mod(struct module *mod)
> +
> +	/* mod->kallsyms is not replaced until do_init_module() returns. */
> +	rcu_read_lock();
> +	kallsyms = rcu_dereference(mod->kallsyms);

Consider using rcu_access_pointer(mod->kallsyms) or
rcu_dereference_raw(mod->kallsyms) rather than a transient
rcu_read_lock()/rcu_read_unlock() pair.

> +	rcu_read_unlock();
> +
> +	if (!kallsyms || kallsyms->num_symtab < 2)
> [...]
> +	 * ftrace never came up, where the loop below would not run anyway; that
> +	 * also makes reading ftrace_disabled without the lock safe.
> +	 */
> +	syms = ftrace_disabled ? NULL : ftrace_mod_syms_alloc(mod);

Because ftrace_disabled is one-way flag, if you find ftrace_disabled here,
you can return from this function soon.

Thanks,

> +
>  	mutex_lock(&ftrace_lock);
>  

-- 
Masami Hiramatsu (Google) <mhiramat@kernel.org>

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

[Yaxiong Tian]

On 2026/10/19 23:25, Masami Hiramatsu (Google) wrote:
> Hi,
>
> On Wed, 16 Sep 2026 16:27:15 +0800, Yaxiong Tian <tianyaxiong@kylinos.cn> wrote:
>
>> diff --git a/kernel/trace/ftrace.c b/kernel/trace/ftrace.c
>> --- a/kernel/trace/ftrace.c
>> +++ b/kernel/trace/ftrace.c
>> @@ -8010,11 +8011,137 @@ void ftrace_release_mod(struct module *mod)
>> +
>> +	/* mod->kallsyms is not replaced until do_init_module() returns. */
>> +	rcu_read_lock();
>> +	kallsyms = rcu_dereference(mod->kallsyms);
> Consider using rcu_access_pointer(mod->kallsyms) or
> rcu_dereference_raw(mod->kallsyms) rather than a transient
> rcu_read_lock()/rcu_read_unlock() pair.
Agreed, I will use rcu_dereference_raw() and drop the lock pair.

>> +	rcu_read_unlock();
>> +
>> +	if (!kallsyms || kallsyms->num_symtab < 2)
>> [...]
>> +	 * ftrace never came up, where the loop below would not run anyway; that
>> +	 * also makes reading ftrace_disabled without the lock safe.
>> +	 */
>> +	syms = ftrace_disabled ? NULL : ftrace_mod_syms_alloc(mod);
> Because ftrace_disabled is one-way flag, if you find ftrace_disabled here,
> you can return from this function soon.
>
> Thanks,
Right. I will check it once before the allocation and jump to a common
out_cached_mods label, so ftrace_lock is not taken at all in that case and
process_cached_mods() still runs exactly once. I keep the second check
under the lock because ftrace_kill() can set the flag after the unlocked
read.

    if (ftrace_disabled)
        goto out_cached_mods;

    syms = ftrace_mod_syms_alloc(mod);

    mutex_lock(&ftrace_lock);

    if (ftrace_disabled)
        goto out_unlock;
    ...
 out_unlock:
    mutex_unlock(&ftrace_lock);
    kvfree(syms);
 out_cached_mods:
    process_cached_mods(mod->name);

>> +
>>  	mutex_lock(&ftrace_lock);
>>  

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

[Steven Rostedt]

On Wed, 16 Sep 2026 16:27:15 +0800
Yaxiong Tian <tianyaxiong@kylinos.cn> wrote:
> 
> Signed-off-by: Yaxiong Tian <tianyaxiong@kylinos.cn>
> ---
>  kernel/trace/ftrace.c | 131 +++++++++++++++++++++++++++++++++++++++++-
>  1 file changed, 130 insertions(+), 1 deletion(-)
> 
> diff --git a/kernel/trace/ftrace.c b/kernel/trace/ftrace.c
> index 673a54fdf392..92ba9a4dfa69 100644
> --- a/kernel/trace/ftrace.c
> +++ b/kernel/trace/ftrace.c
> @@ -26,6 +26,7 @@
>  #include <linux/uaccess.h>
>  #include <linux/bsearch.h>
>  #include <linux/module.h>
> +#include <linux/module_symbol.h>
>  #include <linux/ftrace.h>
>  #include <linux/sysctl.h>
>  #include <linux/slab.h>
> @@ -8010,11 +8011,137 @@ void ftrace_release_mod(struct module *mod)
>  	}
>  }
>  
> +#ifdef FTRACE_MCOUNT_MAX_OFFSET
> +/*
> + * ftrace_module_enable() validates every record with test_for_valid_rec(),
> + * which walks the whole symbol table of a module for each address in it, so a
> + * large module loads in quadratic time.  Search a sorted copy of the symbol
> + * addresses instead, the way get_symbol_pos() searches the kallsyms table.
> + * The array is an accelerator only; records it cannot resolve are tested the
> + * old way, so the verdict does not change.
> + */
> +struct ftrace_mod_syms {
> +	unsigned int	nr;
> +	unsigned long	addr[];	/* sorted, @nr entries */
> +};
> +
> +static int ftrace_mod_syms_cmp(const void *a, const void *b)
> +{
> +	unsigned long va = *(const unsigned long *)a;
> +	unsigned long vb = *(const unsigned long *)b;
> +
> +	return (va > vb) - (va < vb);
> +}

Interesting compare technique. I usually do:

static int ftrace_mod_syms_cmp(const void *a, const void *b)
{
	unsigned long va = *(const unsigned long *)a;
	unsigned long vb = *(const unsigned long *)b;

	if (va < vb)
		return -1;

	return va > vb;
}

But I wanted to compare them, so I wrote this:

int cmp1(const void *a, const void *b)
{
        int A = *(const int *)a;
        int B = *(const int *)b;

        return (A > B) - (A < B);
}

int cmp2(const void *a, const void *b)
{
        int A = *(const int *)a;
        int B = *(const int *)b;

        if (A < B)
                return -1;
        return A > B;
}

And complied with gcc with -O2 and the result was this:

0000000000000000 <cmp1>:
   0:   8b 06                   mov    (%rsi),%eax
   2:   39 07                   cmp    %eax,(%rdi)
   4:   0f 9f c0                setg   %al
   7:   0f 9c c2                setl   %dl
   a:   0f b6 d2                movzbl %dl,%edx
   d:   0f b6 c0                movzbl %al,%eax
  10:   29 d0                   sub    %edx,%eax
  12:   c3                      ret
  13:   66 90                   xchg   %ax,%ax
  15:   66 66 2e 0f 1f 84 00    data16 cs nopw 0x0(%rax,%rax,1)
  1c:   00 00 00 00 

0000000000000020 <cmp2>:
  20:   8b 06                   mov    (%rsi),%eax
  22:   39 07                   cmp    %eax,(%rdi)
  24:   ba ff ff ff ff          mov    $0xffffffff,%edx
  29:   0f 9f c0                setg   %al
  2c:   0f b6 c0                movzbl %al,%eax
  2f:   0f 4c c2                cmovl  %edx,%eax
  32:   c3                      ret

It looks like my version is a bit better with gcc.

I complied with clang and it did this:

0000000000000000 <cmp1>:
   0:   8b 07                   mov    (%rdi),%eax
   2:   3b 06                   cmp    (%rsi),%eax
   4:   0f 9c c0                setl   %al
   7:   0f 9f c1                setg   %cl
   a:   28 c1                   sub    %al,%cl
   c:   0f be c1                movsbl %cl,%eax
   f:   c3                      ret

0000000000000010 <cmp2>:
  10:   8b 07                   mov    (%rdi),%eax
  12:   3b 06                   cmp    (%rsi),%eax
  14:   0f 9c c0                setl   %al
  17:   0f 9f c1                setg   %cl
  1a:   28 c1                   sub    %al,%cl
  1c:   0f be c1                movsbl %cl,%eax
  1f:   c3                      ret

Which made the two identical!

Probably just a nit, but food for thought if you want to keep your method
or switch to mine ;-) I won't be picky about it.


> +
> +static struct ftrace_mod_syms *ftrace_mod_syms_alloc(struct module *mod)
> +{
> +	struct mod_kallsyms *kallsyms;
> +	struct ftrace_mod_syms *syms;
> +	unsigned int i, nr = 0;
> +
> +	/* mod->kallsyms is not replaced until do_init_module() returns. */
> +	rcu_read_lock();
> +	kallsyms = rcu_dereference(mod->kallsyms);
> +	rcu_read_unlock();

The above was already discussed.

> +
> +	if (!kallsyms || kallsyms->num_symtab < 2)
> +		return NULL;
> +
> +	syms = kvmalloc(struct_size(syms, addr, kallsyms->num_symtab),
> +			GFP_KERNEL);
> +	if (!syms)
> +		return NULL;
> +
> +	/* The symbols find_kallsyms_symbol() would consider. */
> +	for (i = 1; i < kallsyms->num_symtab; i++) {
> +		const Elf_Sym *sym = &kallsyms->symtab[i];
> +		const char *name = kallsyms->strtab + sym->st_name;
> +
> +		if (sym->st_shndx == SHN_UNDEF || !*name ||
> +		    is_mapping_symbol(name))
> +			continue;
> +
> +		syms->addr[nr++] = kallsyms_symbol_value(sym);
> +	}
> +	syms->nr = nr;
> +
> +	if (nr > 1)
> +		sort(syms->addr, nr, sizeof(syms->addr[0]), ftrace_mod_syms_cmp,
> +		     NULL);
> +
> +	return syms;
> +}
> +
> +/* The verdict test_for_valid_rec() would give, without walking the table. */
> +static bool ftrace_mod_rec_is_valid(struct module *mod,
> +				    const struct ftrace_mod_syms *syms,
> +				    struct dyn_ftrace *rec)
> +{
> +	unsigned long base, best;
> +	unsigned int lo, hi;
> +
> +	if (!syms)
> +		return test_for_valid_rec(rec) != 0;
> +
> +	/* A record is in executable memory; anything else kallsyms answers. */
> +	if (within_module_mem_type(rec->ip, mod, MOD_TEXT))
> +		base = (unsigned long)mod->mem[MOD_TEXT].base;
> +	else if (within_module_mem_type(rec->ip, mod, MOD_INIT_TEXT))
> +		base = (unsigned long)mod->mem[MOD_INIT_TEXT].base;
> +	else
> +		return test_for_valid_rec(rec) != 0;
> +
> +	/* The closest address at or below @rec->ip, if there is one. */
> +	best = 0;
> +	for (lo = 0, hi = syms->nr; lo < hi; ) {
> +		unsigned int mid = lo + (hi - lo) / 2;
> +
> +		if (syms->addr[mid] <= rec->ip)
> +			lo = mid + 1;
> +		else
> +			hi = mid;
> +	}
> +	if (lo)
> +		best = syms->addr[lo - 1];
> +
> +	/*
> +	 * No symbol, or only ones below @base: let kallsyms_lookup() answer,
> +	 * as it also looks in the BPF and ftrace trampoline tables.
> +	 */
> +	if (best < base)
> +		return test_for_valid_rec(rec) != 0;
> +
> +	return rec->ip - best <= FTRACE_MCOUNT_MAX_OFFSET;
> +}
> +#else
> +struct ftrace_mod_syms;
> +
> +static inline struct ftrace_mod_syms *ftrace_mod_syms_alloc(struct module *mod)
> +{
> +	return NULL;
> +}
> +
> +static inline bool ftrace_mod_rec_is_valid(struct module *mod,
> +					   const struct ftrace_mod_syms *syms,
> +					   struct dyn_ftrace *rec)
> +{
> +	return test_for_valid_rec(rec) != 0;
> +}
> +#endif /* FTRACE_MCOUNT_MAX_OFFSET */
> +
>  void ftrace_module_enable(struct module *mod)
>  {
> +	struct ftrace_mod_syms *syms;

Hmm, remove this...


>  	struct dyn_ftrace *rec;
>  	struct ftrace_page *pg;
>  
> +	/*
> +	 * Allocates, so build it before taking ftrace_lock.  It is skipped when
> +	 * ftrace never came up, where the loop below would not run anyway; that
> +	 * also makes reading ftrace_disabled without the lock safe.
> +	 */
> +	syms = ftrace_disabled ? NULL : ftrace_mod_syms_alloc(mod);

and make the above:

	struct ftrace_mod_syms *syms __free(kvfree) =
		ftrace_disabled ? NULL : ftrace_mod_syms_alloc(mod);


> +
>  	mutex_lock(&ftrace_lock);
>  
>  	if (ftrace_disabled)
> @@ -8050,7 +8177,7 @@ void ftrace_module_enable(struct module *mod)
>  		cond_resched();
>  
>  		/* Weak functions should still be ignored */
> -		if (!test_for_valid_rec(rec)) {
> +		if (!ftrace_mod_rec_is_valid(mod, syms, rec)) {
>  			/* Clear all other flags. Should not be enabled anyway */
>  			rec->flags = FTRACE_FL_DISABLED;
>  			continue;
> @@ -8087,6 +8214,8 @@ void ftrace_module_enable(struct module *mod)
>   out_unlock:
>  	mutex_unlock(&ftrace_lock);
>  
> +	kvfree(syms);

Then we can also remove that.

Thanks,

-- Steve

> +
>  	process_cached_mods(mod->name);
>  }
>  

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

[Yaxiong Tian]

On 2026/11/5 02:43, Steven Rostedt wrote:
> On Wed, 16 Sep 2026 16:27:15 +0800
> Yaxiong Tian <tianyaxiong@kylinos.cn> wrote:
>
> +static int ftrace_mod_syms_cmp(const void *a, const void *b)
> +{
> +	unsigned long va = *(const unsigned long *)a;
> +	unsigned long vb = *(const unsigned long *)b;
> +
> +	return (va > vb) - (va < vb);
> +}
> Interesting compare technique. I usually do:
>
> static int ftrace_mod_syms_cmp(const void *a, const void *b)
> {
> 	unsigned long va = *(const unsigned long *)a;
> 	unsigned long vb = *(const unsigned long *)b;
>
> 	if (va < vb)
> 		return -1;
>
> 	return va > vb;
> }
>
> But I wanted to compare them, so I wrote this:
>
> int cmp1(const void *a, const void *b)
> {
>         int A = *(const int *)a;
>         int B = *(const int *)b;
>
>         return (A > B) - (A < B);
> }
>
> int cmp2(const void *a, const void *b)
> {
>         int A = *(const int *)a;
>         int B = *(const int *)b;
>
>         if (A < B)
>                 return -1;
>         return A > B;
> }
>
> And complied with gcc with -O2 and the result was this:
>
> 0000000000000000 <cmp1>:
>    0:   8b 06                   mov    (%rsi),%eax
>    2:   39 07                   cmp    %eax,(%rdi)
>    4:   0f 9f c0                setg   %al
>    7:   0f 9c c2                setl   %dl
>    a:   0f b6 d2                movzbl %dl,%edx
>    d:   0f b6 c0                movzbl %al,%eax
>   10:   29 d0                   sub    %edx,%eax
>   12:   c3                      ret
>   13:   66 90                   xchg   %ax,%ax
>   15:   66 66 2e 0f 1f 84 00    data16 cs nopw 0x0(%rax,%rax,1)
>   1c:   00 00 00 00 
>
> 0000000000000020 <cmp2>:
>   20:   8b 06                   mov    (%rsi),%eax
>   22:   39 07                   cmp    %eax,(%rdi)
>   24:   ba ff ff ff ff          mov    $0xffffffff,%edx
>   29:   0f 9f c0                setg   %al
>   2c:   0f b6 c0                movzbl %al,%eax
>   2f:   0f 4c c2                cmovl  %edx,%eax
>   32:   c3                      ret
>
> It looks like my version is a bit better with gcc.
>
> I complied with clang and it did this:
>
> 0000000000000000 <cmp1>:
>    0:   8b 07                   mov    (%rdi),%eax
>    2:   3b 06                   cmp    (%rsi),%eax
>    4:   0f 9c c0                setl   %al
>    7:   0f 9f c1                setg   %cl
>    a:   28 c1                   sub    %al,%cl
>    c:   0f be c1                movsbl %cl,%eax
>    f:   c3                      ret
>
> 0000000000000010 <cmp2>:
>   10:   8b 07                   mov    (%rdi),%eax
>   12:   3b 06                   cmp    (%rsi),%eax
>   14:   0f 9c c0                setl   %al
>   17:   0f 9f c1                setg   %cl
>   1a:   28 c1                   sub    %al,%cl
>   1c:   0f be c1                movsbl %cl,%eax
>   1f:   c3                      ret
>
> Which made the two identical!
>
> Probably just a nit, but food for thought if you want to keep your method
> or switch to mine ;-) I won't be picky about it.

I didn't think about the assembly side of this at the time ;-), and your
version is valuable for this kind of optimization.

I tried both with the type we actually use (unsigned long, -O2; the
counts include ret):

gcc 12.3.0:
0000000000000000 <cmp1>:
   0:    48 8b 0f                 mov    (%rdi),%rcx
   3:    48 8b 16                 mov    (%rsi),%rdx
   6:    31 c0                    xor    %eax,%eax
   8:    48 39 ca                 cmp    %rcx,%rdx
   b:    0f 92 c0                 setb   %al
   e:    48 39 d1                 cmp    %rdx,%rcx
  11:    83 d8 00                 sbb    $0x0,%eax
  14:    c3                       ret
                              (8 insns, branchless)

0000000000000020 <cmp2>:
  20:    48 8b 17                 mov    (%rdi),%rdx
  23:    48 8b 0e                 mov    (%rsi),%rcx
  26:    b8 ff ff ff ff           mov    $0xffffffff,%eax
  2b:    48 39 ca                 cmp    %rcx,%rdx
  2e:    72 08                    jb     38 <cmp2+0x18>
  30:    31 c0                    xor    %eax,%eax
  32:    48 39 d1                 cmp    %rdx,%rcx
  35:    0f 92 c0                 setb   %al
  38:    c3                       ret
                              (9 insns, with a data-dependent branch)

clang 17.0.6:
0000000000000000 <cmp1>:
   0:    48 8b 0f                 mov    (%rdi),%rcx
   3:    31 c0                    xor    %eax,%eax
   5:    48 3b 0e                 cmp    (%rsi),%rcx
   8:    0f 97 c0                 seta   %al
   b:    83 d8 00                 sbb    $0x0,%eax
   e:    c3                       ret
                              (6 insns, branchless)

0000000000000010 <cmp2>:
  10:    48 8b 07                 mov    (%rdi),%rax
  13:    31 c9                    xor    %ecx,%ecx
  15:    48 3b 06                 cmp    (%rsi),%rax
  18:    0f 97 c1                 seta   %cl
  1b:    b8 ff ff ff ff           mov    $0xffffffff,%eax
  20:    0f 43 c1                 cmovae %ecx,%eax
  23: c3                       ret
                              (7 insns, branchless)

Your version is one instruction shorter for int, but for 64-bit gcc needs a
second compare after the branch to tell > from ==, and picks a branch
instead
of cmov, which is worse for a sort comparator.  So I kept the subtract form.

>
>> +
>> +static struct ftrace_mod_syms *ftrace_mod_syms_alloc(struct module *mod)
>> +{
>> +	struct mod_kallsyms *kallsyms;
>> +	struct ftrace_mod_syms *syms;
>> +	unsigned int i, nr = 0;
>> +
>> +	/* mod->kallsyms is not replaced until do_init_module() returns. */
>> +	rcu_read_lock();
>> +	kallsyms = rcu_dereference(mod->kallsyms);
>> +	rcu_read_unlock();
> The above was already discussed.
>
>> +
>> +	if (!kallsyms || kallsyms->num_symtab < 2)
>> +		return NULL;
>> +
>> +	syms = kvmalloc(struct_size(syms, addr, kallsyms->num_symtab),
>> +			GFP_KERNEL);
>> +	if (!syms)
>> +		return NULL;
>> +
>> +	/* The symbols find_kallsyms_symbol() would consider. */
>> +	for (i = 1; i < kallsyms->num_symtab; i++) {
>> +		const Elf_Sym *sym = &kallsyms->symtab[i];
>> +		const char *name = kallsyms->strtab + sym->st_name;
>> +
>> +		if (sym->st_shndx == SHN_UNDEF || !*name ||
>> +		    is_mapping_symbol(name))
>> +			continue;
>> +
>> +		syms->addr[nr++] = kallsyms_symbol_value(sym);
>> +	}
>> +	syms->nr = nr;
>> +
>> +	if (nr > 1)
>> +		sort(syms->addr, nr, sizeof(syms->addr[0]), ftrace_mod_syms_cmp,
>> +		     NULL);
>> +
>> +	return syms;
>> +}
>> +
>> +/* The verdict test_for_valid_rec() would give, without walking the table. */
>> +static bool ftrace_mod_rec_is_valid(struct module *mod,
>> +				    const struct ftrace_mod_syms *syms,
>> +				    struct dyn_ftrace *rec)
>> +{
>> +	unsigned long base, best;
>> +	unsigned int lo, hi;
>> +
>> +	if (!syms)
>> +		return test_for_valid_rec(rec) != 0;
>> +
>> +	/* A record is in executable memory; anything else kallsyms answers. */
>> +	if (within_module_mem_type(rec->ip, mod, MOD_TEXT))
>> +		base = (unsigned long)mod->mem[MOD_TEXT].base;
>> +	else if (within_module_mem_type(rec->ip, mod, MOD_INIT_TEXT))
>> +		base = (unsigned long)mod->mem[MOD_INIT_TEXT].base;
>> +	else
>> +		return test_for_valid_rec(rec) != 0;
>> +
>> +	/* The closest address at or below @rec->ip, if there is one. */
>> +	best = 0;
>> +	for (lo = 0, hi = syms->nr; lo < hi; ) {
>> +		unsigned int mid = lo + (hi - lo) / 2;
>> +
>> +		if (syms->addr[mid] <= rec->ip)
>> +			lo = mid + 1;
>> +		else
>> +			hi = mid;
>> +	}
>> +	if (lo)
>> +		best = syms->addr[lo - 1];
>> +
>> +	/*
>> +	 * No symbol, or only ones below @base: let kallsyms_lookup() answer,
>> +	 * as it also looks in the BPF and ftrace trampoline tables.
>> +	 */
>> +	if (best < base)
>> +		return test_for_valid_rec(rec) != 0;
>> +
>> +	return rec->ip - best <= FTRACE_MCOUNT_MAX_OFFSET;
>> +}
>> +#else
>> +struct ftrace_mod_syms;
>> +
>> +static inline struct ftrace_mod_syms *ftrace_mod_syms_alloc(struct module *mod)
>> +{
>> +	return NULL;
>> +}
>> +
>> +static inline bool ftrace_mod_rec_is_valid(struct module *mod,
>> +					   const struct ftrace_mod_syms *syms,
>> +					   struct dyn_ftrace *rec)
>> +{
>> +	return test_for_valid_rec(rec) != 0;
>> +}
>> +#endif /* FTRACE_MCOUNT_MAX_OFFSET */
>> +
>>  void ftrace_module_enable(struct module *mod)
>>  {
>> +	struct ftrace_mod_syms *syms;
> Hmm, remove this...
>
>
>>  	struct dyn_ftrace *rec;
>>  	struct ftrace_page *pg;
>>  
>> +	/*
>> +	 * Allocates, so build it before taking ftrace_lock.  It is skipped when
>> +	 * ftrace never came up, where the loop below would not run anyway; that
>> +	 * also makes reading ftrace_disabled without the lock safe.
>> +	 */
>> +	syms = ftrace_disabled ? NULL : ftrace_mod_syms_alloc(mod);
> and make the above:
>
> 	struct ftrace_mod_syms *syms __free(kvfree) =
> 		ftrace_disabled ? NULL : ftrace_mod_syms_alloc(mod);
>
>
>> +
>>  	mutex_lock(&ftrace_lock);
>>  
>>  	if (ftrace_disabled)
>> @@ -8050,7 +8177,7 @@ void ftrace_module_enable(struct module *mod)
>>  		cond_resched();
>>  
>>  		/* Weak functions should still be ignored */
>> -		if (!test_for_valid_rec(rec)) {
>> +		if (!ftrace_mod_rec_is_valid(mod, syms, rec)) {
>>  			/* Clear all other flags. Should not be enabled anyway */
>>  			rec->flags = FTRACE_FL_DISABLED;
>>  			continue;
>> @@ -8087,6 +8214,8 @@ void ftrace_module_enable(struct module *mod)
>>   out_unlock:
>>  	mutex_unlock(&ftrace_lock);
>>  
>> +	kvfree(syms);
> Then we can also remove that.

Done as suggested; the explicit kvfree() is gone.  The v2 also carries the
rcu_dereference_raw() change discussed earlier.

I will send the v2 shortly, after I finish testing it today.

Thanks,
Yaxiong


>
> Thanks,
>
> -- Steve
>
>> +
>>  	process_cached_mods(mod->name);
>>  }
>>