Re: [PATCH v3 next 08/13] kallsyms: Optimise symbol name search

[Samuel Wu]

On Wed, Nov 11, 2026 at 3:59 AM David Laight
<david.laight.linux@xxxxxxxxx> wrote:
>
> Change the alphabetically ordered lookup table (kallsyms_seqs_of_names)
> to one that indexes the table of compressed names rather than the
> array of symbol values.
> This removes all the linear scans during the binary search for the symbol
> name.
> Once the name has been found a second binary search of the 'markers' array
> followed by a linear scan for the symbols address gives the symbol value.
>
> This linear scan is done once for each address returned, whereas the old
> code did the scan for each of the ~17 comparisons in the binary search
> (and the binary search was done twice for a symbol that appears once).
>
> For normal kernels the index table stays at 24 bits per symbol (now host
> ordered), but a 32 bit table is used if necessary (probably only for
> allyesconfig builds - which needs 26 bits on x86-64).
>
> Use the low bit of the index table value to indicate that the symbol has
> the same name as the previous one.
> Use this to avoid the second lookup to find if the name is unique, speed
> up the search for the first symbol with a given name, and simplify
> kallsyms_on_each_match_symbol().
>
> Speeds up lookup by name by a factor of about 12, and makes a massive
> difference to the time taken to lookup symbols that occur 100s or
> 1000s (or maybe 10000s) of times.
>
> The slowest 'lookup by name' changes being a symbol that is duplicated a lot
> to one that is very long.
>
> Build for BE kernels correctly flips the byte order in the index table.
>
> Signed-off-by: David Laight <david.laight.linux@xxxxxxxxx>
> ---
>
> v3:
> - Use a discrimant union for the name table instead of weak symbols.
>   Undefined weak symbols can't be guaranteed to be zero and a build
>   mismatch left both undefined.
> - Patch the kallsyms_off_size_24 static key from an initcall,
>   the first name lookup might not be allowed to sleep.
>   Leave a conditional in the 32bit offset case, it is unlikely
>   to be needed for a real kernel.
> - Merge in the following patch that optimised the scan for duplicates.
>
>  kernel/kallsyms.c          | 162 ++++++++++++++++++++++++-------------
>  kernel/kallsyms_internal.h |   7 +-
>  scripts/kallsyms.c         |  49 +++++++----
>  3 files changed, 148 insertions(+), 70 deletions(-)
>
> diff --git a/kernel/kallsyms.c b/kernel/kallsyms.c
> index d18d78e626db..fd42a1a8ed3e 100644
> --- a/kernel/kallsyms.c
> +++ b/kernel/kallsyms.c
> @@ -177,6 +177,36 @@ static unsigned int get_symbol_offset(unsigned long pos)
>         return name - kallsyms_names;
>  }
>
> +/*
> + * Find the value of a symbol given the offset in the compressed stream.
> + */
> +static unsigned long get_name_address(unsigned int name_offset)
> +{
> +       unsigned int low, pos, high;
> +
> +       low = 0;
> +       high = ((kallsyms_num_syms - 1) >> 8) + 1;
> +
> +       while (high - low > 1) {
> +               pos = low + (high - low) / 2;
> +               if (name_offset >= kallsyms_markers[pos])
> +                       low = pos;
> +               else
> +                       high = pos;
> +       }
> +
> +       pos = kallsyms_markers[low];
> +       for (low <<= 8; pos < name_offset; low++) {
> +               unsigned int len = kallsyms_names[pos];
> +               if (len & 0x80)
> +                       len += (kallsyms_names[pos + 1] << 7) - 0x7f;
> +               pos += 1 + len;
> +       }

Is this just get_symbol_data() from previous patch? If so, that would
make it more readable.

> +
> +       return kallsyms_sym_address(low);
> +}
> +
> +
>  unsigned long kallsyms_sym_address(int idx)
>  {
>         /* non-relocatable 32-bit kernels just embed the value directly */
> @@ -185,66 +215,87 @@ unsigned long kallsyms_sym_address(int idx)
>         return (unsigned long)offset_to_ptr(kallsyms_offsets + idx);
>  }
>
> -static unsigned int get_symbol_seq(int index)
> -{
> -       unsigned int i, seq = 0;
> +static DEFINE_STATIC_KEY_FALSE(kallsyms_off_size_24);
>
> -       for (i = 0; i < 3; i++)
> -               seq = (seq << 8) | kallsyms_seqs_of_names[3 * index + i];
> +/*
> + * Get the offset into the compressed list of names for the n'th
> + * symbol in the 'sorted by name' list.
> + * Returns 'offset << 1 | is_duplicate_name'.
> + * To save memory (the array can have 200k+ entries) the values are usually
> + * 24 bit (host ordered) but will be 32 bit if necessary.
> + */
> +static inline unsigned int get_symbol_name_offset(unsigned long index)
> +{
> +       if (static_branch_likely(&kallsyms_off_size_24) ||
> +           unlikely(kallsyms_offs_of_names.size == 24)) {
> +               u8 *off = kallsyms_offs_of_names.offs + index * 3;
> +#if !defined(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS)
> +               return ((struct {unsigned int v:24 __packed; } __packed *)off)->v;
> +#else
> +#if defined(__BIG_ENDIAN)
> +               return (*(u32 *)(off - 1)) & 0xffffff;
> +#else
> +               return (*(u32 *)(off - 1)) >> 8;
> +#endif
> +#endif
> +       }
>
> -       return seq;
> +       return ((u32 *)&kallsyms_offs_of_names.offs)[index];
>  }
>
> -static int kallsyms_lookup_names(const char *name,
> -                                unsigned int *start,
> -                                unsigned int *end)
> +static int kallsyms_set_kallsyms_off_size(void)
>  {
> +       if (kallsyms_offs_of_names.size == 24)
> +               static_branch_enable(&kallsyms_off_size_24);
> +
> +       return 0;
> +}
> +early_initcall(kallsyms_set_kallsyms_off_size);
> +
> +static int kallsyms_lookup_names(const char *name, unsigned int *start)
> +{
> +       unsigned int mid, off;
> +       int low, high;
>         int ret;
> -       int low, mid, high;

nit: any issue with mixing signed and unsigned here? Simpler to keep
them the same type if possible.

> -       unsigned int seq, off;
>         low = 0;
>         high = kallsyms_num_syms - 1;
>
> -       while (low <= high) {
> +       for (;;) {
> +               if (low > high)
> +                       return -1;
>                 mid = low + (high - low) / 2;
> -               seq = get_symbol_seq(mid);
> -               off = get_symbol_offset(seq);
> -               ret = kallsyms_strcmp_symbol(off, name);
> -               if (ret > 0)
> +               off = get_symbol_name_offset(mid);
> +               ret = kallsyms_strcmp_symbol(off >> 1, name);
> +               if (ret > 0) {
>                         low = mid + 1;
> -               else if (ret < 0)
> -                       high = mid - 1;
> -               else
> -                       break;
> -       }
> -
> -       if (low > high)
> -               return -ESRCH;
> -
> -       low = mid;
> -       while (low) {
> -               seq = get_symbol_seq(low - 1);
> -               off = get_symbol_offset(seq);
> -               if (kallsyms_strcmp_symbol(off, name) != 0)
> -                       break;
> -               low--;
> -       }
> -       *start = low;
> -
> -       if (end) {
> -               high = mid;
> -               while (high < kallsyms_num_syms - 1) {
> -                       seq = get_symbol_seq(high + 1);
> -                       off = get_symbol_offset(seq);
> -                       if (kallsyms_strcmp_symbol(off, name) != 0)
> +                       continue;
> +               }
> +               if (!ret) {
> +                       /*
> +                        * Found a match, but need the first one.
> +                        * Most symbols (and all exported/global ones) only occur
> +                        * once, most of the others only occur a small number of
> +                        * times so it is worth doing a linear scan that avoids the
> +                        * kallsyms_strcmp_symbol() call.
> +                        * However some symbols occur a large number of times
> +                        * (_sub_D_65535_0 is repeated 24610 times in an x86-64
> +                        * allyesconfig, __func__.0 442 in a more normal kernel).
> +                        * Avoid a long linear scan by returning to the binary
> +                        * search if a short linear search is fruitless.
> +                        */
> +                       unsigned int scan = 16;
> +                       while ((off & 1) && scan--)
> +                               off = get_symbol_name_offset(--mid);
> +                       if (!(off & 1))

Curious if you have numbers comparing with and without this linear
scan. Did a quick check on my desktop and phone, and ~99% of symbols
are unique already; of the ~1% that are repeated, they're generally
compiler generated local variables which I think are rare targets for
symbolization (AFAIK).

Just a vanilla lower_bound() would halve the line count of this function. :)

>                                 break;
> -                       high++;
>                 }
> -               *end = high;
> +               high = mid - 1;
>         }
>
> -       return 0;
> +       *start = mid;
> +
> +       return off;
>  }
>
>  /* Lookup the address for this symbol. Returns 0 if not found. */
> @@ -257,9 +308,9 @@ unsigned long kallsyms_lookup_name(const char *name)
>         if (!*name)
>                 return 0;
>
> -       ret = kallsyms_lookup_names(name, &i, NULL);
> -       if (!ret)
> -               return kallsyms_sym_address(get_symbol_seq(i));
> +       ret = kallsyms_lookup_names(name, &i);
> +       if (ret >= 0)
> +               return get_name_address(ret >> 1);
>
>         return module_kallsyms_lookup_name(name);
>  }
> @@ -289,17 +340,20 @@ int kallsyms_on_each_symbol(int (*fn)(void *, const char *, unsigned long),
>  int kallsyms_on_each_match_symbol(int (*fn)(void *, unsigned long),
>                                   const char *name, void *data)
>  {
> -       int ret;
> -       unsigned int i, start, end;
> +       int name_offset, ret;
> +       unsigned int sym_number;
>
> -       ret = kallsyms_lookup_names(name, &start, &end);
> -       if (ret)
> +       name_offset = kallsyms_lookup_names(name, &sym_number);
> +       if (name_offset < 0)
>                 return 0;
>
> -       for (i = start; !ret && i <= end; i++) {
> -               ret = fn(data, kallsyms_sym_address(get_symbol_seq(i)));
> +       do {
> +               ret = fn(data, get_name_address(name_offset >> 1));
> +               if (ret)
> +                       break;
>                 cond_resched();
> -       }
> +               name_offset = get_symbol_name_offset(++sym_number);
> +       } while (name_offset & 1);
>
>         return ret;
>  }
> diff --git a/kernel/kallsyms_internal.h b/kernel/kallsyms_internal.h
> index 81a867dbe57d..11fb0de92ede 100644
> --- a/kernel/kallsyms_internal.h
> +++ b/kernel/kallsyms_internal.h
> @@ -13,6 +13,11 @@ extern const char kallsyms_token_table[];
>  extern const u16 kallsyms_token_index[];
>
>  extern const unsigned int kallsyms_markers[];
> -extern const u8 kallsyms_seqs_of_names[];
> +
> +/* Although constant, size is volatile for better code generation. */
> +extern struct {
> +       volatile unsigned int size;     /* 24 or 32 */
> +       unsigned char offs[];           /* int:24[] or int:32[] */
> +} kallsyms_offs_of_names;
>
>  #endif // LINUX_KALLSYMS_INTERNAL_H_
> diff --git a/scripts/kallsyms.c b/scripts/kallsyms.c
> index 74db751600b4..930ec27a53c0 100644
> --- a/scripts/kallsyms.c
> +++ b/scripts/kallsyms.c
> @@ -403,7 +403,7 @@ static void sort_symbols_by_name(void)
>
>  static void write_src(void)
>  {
> -       unsigned int i, k, len, off, seq;
> +       unsigned int i, k, len, off, off_size, table_size;
>         unsigned int best_idx[256];
>         unsigned int *markers, markers_cnt;
>         unsigned long bin_offset = 0;
> @@ -453,7 +453,7 @@ static void write_src(void)
>                 unsigned char len[2];
>
>                 se = table[i];
> -               se->seq = i;
> +               se->seq = off;
>
>                 /* The length must be less than that of the original symbol. */
>                 if (!se->len || se->len > KSYM_NAME_LEN)
> @@ -485,7 +485,7 @@ static void write_src(void)
>                         if ((i & 0xFF) == 0)
>                                 markers[i >> 8] = off;
>
> -                       printf("\t.byte\t%u", len[0]);
> +                       printf("\t/* n:%u */\t.byte\t%u", off, len[0]);
>                         if (len_len == 2)
>                                 printf(",%u", len[1]);
>
> @@ -500,6 +500,7 @@ static void write_src(void)
>                 memcpy(se->sym, buf, se_len + 1);
>         }
>         write_incbin(&bin_offset, off);
> +       table_size = off;
>         printf(".size kallsyms_names, . - kallsyms_names\n");
>         printf("\n");
>
> @@ -560,7 +561,7 @@ static void write_src(void)
>                                out_bin_file ? '\n' : '\t');
>                 }
>                 if (!out_bin_file)
> -                       printf("/* %c %s */\n", table[i]->sym[0], table[i]->sym + 1);
> +                       printf("/* n:%u %c %s */\n", table[i]->seq, table[i]->sym[0], table[i]->sym + 1);
>         }
>         printf(".size kallsyms_offsets, . - kallsyms_offsets\n");
>         printf("\n");
> @@ -570,23 +571,41 @@ static void write_src(void)
>         sort_symbols_by_name();
>         stamp("sort by name");
>
> -       output_label("kallsyms_seqs_of_names");
> -       write_incbin_header("seq_of_names", &bin_offset);
> +       off_size = table_size < (1u << 23) ? 24 : 32;
> +       output_label("kallsyms_offs_of_names");
> +       printf("\t.long\t%u\n", off_size);
> +       write_incbin_header("offs_of_names", &bin_offset);
>         for (i = 0; i < table_cnt; i++) {
>                 se = table[i];
> -               seq = se->seq;
> +               off = se->seq << 1;
> +               if (i && se->len == table[i - 1]->len &&
> +                   !memcmp(se->sym + 1, table[i - 1]->sym + 1, se->len - 1))
> +                       /* Mark that this is a duplicate of the previous symbol */
> +                       off |= 1;
>                 if (out_bin_file) {
> -                       unsigned int seq_be = htobe32(seq);
> -                       fwrite((char *)&seq_be + 1, 1, 3, out_bin_file);
> +                       unsigned int off_te = big_endian ? htobe32(off) >> (32 - off_size): htole32(off);
> +                       fwrite(&off_te, 1, off_size / 8 , out_bin_file);
>                 } else {
> -                       /* The three spaces before the tab line up the comments */
> -                       printf("\t.byte\t%u,%u,%u   \t/* %8d %c %s */\n",
> -                               seq >> 16, (seq >> 8) & 0xff, seq & 0xff,
> -                               seq, se->sym[0], se->sym + 1);
> +                       if (off_size == 32) {
> +                               printf("\t.long\t%#4x", off);
> +                       } else {
> +                               if (big_endian)
> +                                       off = __builtin_bswap32(off) >> 8;
> +                               /* The trailing three spaces line up the comments */
> +                               printf("\t.byte\t%u,%u,%u   ",
> +                                       off & 0xff, (off >> 8) & 0xff, off >> 16);
> +                       }
> +                       printf("\t/* n:%-8d %c %s */\n",
> +                               se->seq, se->sym[0], se->sym + 1);
>                 }
>         }
> -       write_incbin(&bin_offset, table_cnt * 3);
> -       printf(".size kallsyms_seqs_of_names, . - kallsyms_seqs_of_names\n");
> +       write_incbin(&bin_offset, table_cnt * (off_size / 8));
> +       /* Add a terminator without the 'duplicate' flag. */
> +       if (off_size == 24)
> +               printf("\t.byte\t0,0,0\n");
> +       else
> +               printf("\t.long\t0\n");
> +       printf(".size kallsyms_offs_of_names, . - kallsyms_offs_of_names\n");
>
>         stamp("write name index");
>
> --
> 2.39.5
>