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

[Steven Rostedt <rostedt@goodmis.org>]

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);
>  }
>