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

[Yaxiong Tian <tianyaxiong@kylinos.cn>]

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