Re: [PATCH v3 next 07/13] kallsyms: Match compressed tokens on the fly during binary search

From: Samuel Wu

Date: Fri Nov 13 2026 - 19:56:11 EST


On Wed, Nov 11, 2026 at 3:59 AM David Laight
<david.laight.linux@xxxxxxxxx> wrote:
>
> From: Jim Cromie <jim.cromie@xxxxxxxxx>
>
> kallsyms_lookup_names() runs a binary search across ~184k tokenized
> (compressed) symbols. For each of the ~17 comparisons in the search, it
> currently decompresses the candidate symbol into a temporary buffer on
> the stack before calling strcmp().
>
> Comparing tokenized symbols directly in compressed space is
> impossible. The BPE token table assigns values by frequency, not
> alphabetical order (e.g. token 0x05 might expand to "zebra" while 0x42
> expands to "apple"), so comparing raw token values scrambles
> lexicographical order. Even sorting the token table alphabetically
> wouldn't help; "bpf_" and "bpf_foo_" do not *have* a determinative
> sorting order, because the suffixes following those tokens would
> matter.
>
> However, full string expansion at every step is equally wasteful: of
> the ~17 strcmps in the binary search, only the last needs to check
> all N chars in both strings, earlier steps will know +/- outcome at
> char 0,1,2..N-1.
>
> However, full string expansion at every step is equally wasteful: of
> the ~17 strcmp()s in the binary search, only the final matching step
> needs to test all characters. Earlier non-matching steps diverge at
> the first differing character (0..N-1), but the baseline expands every
> candidate symbol to the stack unconditionally, before comparing.
>
> So we introduce kallsyms_strcmp_symbol() to compare ASCII search_name
> against tokenized symbols on the fly. Like strcmp, it tests the
> strings char by char, but when it hits a token in the symbol-string,
> it continues the char-test against that token-string, which is in
> kallsyms_token_table[]. It returns +- on 1st mismatch.
>
> Measured across all ~184k symbols via CONFIG_KALLSYMS_SELFTEST, this
> shaves ~530 ns (~14%) off average kallsyms_lookup_name() latency (from
> ~3810 ns to ~3280 ns on the default 256:1 baseline) and drops the
> 512-byte namebuf buffer stack-alloc in kallsyms_lookup_names().
>
> Signed-off-by: Jim Cromie <jim.cromie@xxxxxxxxx>
> Signed-off-by: David Laight <david.laight.linux@xxxxxxxxx>
> ---
>
> Unchanged from Jim's patch.
> I think this is the latest version of it, but any later changes
> shouldn't cause problems.
>
> kernel/kallsyms.c | 94 +++++++++++++++++++++++++++++------------------
> 1 file changed, 59 insertions(+), 35 deletions(-)
>
> diff --git a/kernel/kallsyms.c b/kernel/kallsyms.c
> index aec2f06858af..d18d78e626db 100644
> --- a/kernel/kallsyms.c
> +++ b/kernel/kallsyms.c
> @@ -34,6 +34,21 @@
>
> #include "kallsyms_internal.h"
>
> +/*
> + * Get the compressed symbol length and data pointer.
> + */
> +static inline const u8 *get_symbol_data(unsigned int off, unsigned int *len)
> +{
> + const u8 *p = &kallsyms_names[off];
> + unsigned int l = *p++;
> +
> + if (unlikely(l & 0x80))
> + l = (l & 0x7F) | (*p++ << 7);
> + *len = l;
> +
> + return p;
> +}
> +
> /*
> * Expand a compressed symbol data into the resulting uncompressed string,
> * if uncompressed string is too long (>= maxlen), it will be truncated,
> @@ -42,28 +57,12 @@
> static unsigned int kallsyms_expand_symbol(unsigned int off,
> char *result, size_t maxlen)
> {
> - int len, skipped_first = 0;
> + int skipped_first = 0;
> const char *tptr;
> - const u8 *data;
> + unsigned int len;
> + const u8 *data = get_symbol_data(off, &len);
>
> - /* Get the compressed symbol length from the first symbol byte. */
> - data = &kallsyms_names[off];
> - len = *data;
> - data++;
> - off++;
> -
> - /* If MSB is 1, it is a "big" symbol, so needs an additional byte. */
> - if ((len & 0x80) != 0) {
> - len = (len & 0x7F) | (*data << 7);
> - data++;
> - off++;
> - }
> -
> - /*
> - * Update the offset to return the offset for the next symbol on
> - * the compressed stream.
> - */
> - off += len;
> + off = (data - kallsyms_names) + len;
>
> /*
> * For every byte on the compressed symbol data, copy the table
> @@ -101,14 +100,43 @@ static unsigned int kallsyms_expand_symbol(unsigned int off,
> */
> static char kallsyms_get_symbol_type(unsigned int off)
> {
> - /*
> - * Get just the first code, look it up in the token table,
> - * and return the first char from this token. If MSB of length
> - * is 1, it is a "big" symbol, so needs an additional byte.
> - */
> - if (kallsyms_names[off] & 0x80)
> - off++;
> - return kallsyms_token_table[kallsyms_token_index[kallsyms_names[off + 1]]];
> + unsigned int len;
> + const u8 *data = get_symbol_data(off, &len);
> +
> + return kallsyms_token_table[kallsyms_token_index[*data]];
> +}
> +
> +/*
> + * Compare an uncompressed ASCII string against a compressed symbol table entry.
> + * Returns negative if name < sym, positive if name > sym, 0 if equal.
> + * Exits immediately on the first mismatched character without decompressing
> + * the rest of the symbol name.
> + */
> +static int kallsyms_strcmp_symbol(unsigned int off, const char *name)
> +{
> + const char *tptr;
> + unsigned int len;
> + const u8 *data = get_symbol_data(off, &len);
> +
> + tptr = &kallsyms_token_table[kallsyms_token_index[*data++]] + 1;
> + while (*tptr) {
> + int diff = (unsigned char)*name++ - (unsigned char)*tptr++;
> +
> + if (diff)
> + return diff;
> + }
> +
> + while (--len) {
> + tptr = &kallsyms_token_table[kallsyms_token_index[*data++]];
> + do {
> + int diff = (unsigned char)*name++ - (unsigned char)*tptr++;
> +
> + if (diff)
> + return diff;
> + } while (*tptr);
> + }
> +
> + return (unsigned char)*name;
> }
>
>
> @@ -174,7 +202,6 @@ static int kallsyms_lookup_names(const char *name,
> int ret;
> int low, mid, high;
> unsigned int seq, off;
> - char namebuf[KSYM_NAME_LEN];
>
> low = 0;
> high = kallsyms_num_syms - 1;
> @@ -183,8 +210,7 @@ static int kallsyms_lookup_names(const char *name,
> mid = low + (high - low) / 2;
> seq = get_symbol_seq(mid);
> off = get_symbol_offset(seq);
> - kallsyms_expand_symbol(off, namebuf, ARRAY_SIZE(namebuf));
> - ret = strcmp(name, namebuf);
> + ret = kallsyms_strcmp_symbol(off, name);
> if (ret > 0)
> low = mid + 1;
> else if (ret < 0)
> @@ -200,8 +226,7 @@ static int kallsyms_lookup_names(const char *name,
> while (low) {
> seq = get_symbol_seq(low - 1);
> off = get_symbol_offset(seq);
> - kallsyms_expand_symbol(off, namebuf, ARRAY_SIZE(namebuf));
> - if (strcmp(name, namebuf))
> + if (kallsyms_strcmp_symbol(off, name) != 0)
> break;
> low--;
> }
> @@ -212,8 +237,7 @@ static int kallsyms_lookup_names(const char *name,
> while (high < kallsyms_num_syms - 1) {
> seq = get_symbol_seq(high + 1);
> off = get_symbol_offset(seq);
> - kallsyms_expand_symbol(off, namebuf, ARRAY_SIZE(namebuf));
> - if (strcmp(name, namebuf))
> + if (kallsyms_strcmp_symbol(off, name) != 0)
> break;
> high++;
> }
> --
> 2.39.5
>

Reviewed-by: Samuel Wu <wusamuel@xxxxxxxxxx>