Re: [PATCH v2 3/3] kallsyms: Match compressed tokens on the fly during binary search

[David Laight]

On Tue, 22 Sep 2026 01:19:21 -0600
Jim Cromie <jim.cromie@xxxxxxxxx> wrote:

> kallsyms_lookup_names() runs a binary search across kallsyms_names[],
> a packed array of ~130k encoded kernel 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 raw tokens 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.
> 
> However, full string expansion is equally wasteful: roughly 16 of the
> 17 binary search steps fail within the first two characters.
> 
> Introduce kallsyms_strcmp_symbol() to compare ASCII queries against
> compressed tokens on the fly.  It walks kallsyms_token_index and
> kallsyms_token_table incrementally, matching characters directly and
> bailing out on the first character mismatch without expanding subsequent
> tokens.
> 
> This optimization:
> 
> 0. Avoids decompressing non-matching tokens, short-circuiting ~94% of
>    binary search character expansions without adding any tables in
>    .rodata.
> 
> 1. Drops the 512-byte namebuf buffer from the kernel stack in
>    kallsyms_lookup_names().
> 
> 2. Leaves sequential address ordering and kallsyms_expand_symbol()
>    streaming invariants intact for /proc/kallsyms and table walks.
> 
> Signed-off-by: Jim Cromie <jim.cromie@xxxxxxxxx>
...
> +/*
> + * 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)
> +{
> +	int skipped_first = 0;
> +	const char *tptr;
> +	unsigned int len;
> +	const u8 *data = get_symbol_data(off, &len);
> +
> +	while (len) {
> +		tptr = &kallsyms_token_table[kallsyms_token_index[*data]];
> +		data++;
> +		len--;
> +
> +		while (*tptr) {
> +			if (skipped_first) {
> +				int diff = (unsigned char)*name - (unsigned char)*tptr;
> +
> +				if (diff != 0)
> +					return diff;
> +				name++;
> +			} else {
> +				skipped_first = 1;
> +			}
> +			tptr++;
> +		}
> +	}
> +
> +	return (unsigned char)*name - '\0';
> +}

Since len can't be zero you can move the test to the bottom and remove the
skipped_first test completely. Something like:

	tptr = &kallsyms_token_table[kallsyms_token_index[*data++]] + 1;
	for (;;) {
		do {
			int diff = (unsigned char)*name++ - (unsigned char)*tptr++;
			if (diff)
				return diff;
		} while (*tptr);
		if (!--len)
			break;
		tptr = &kallsyms_token_table[kallsyms_token_index[*data++]];
	}
	return (unsigned char)*name;

Also 'char' is now 'unsigned char' in all kernel builds you don't
need the casts.
But I'd make the types explicitly 'unsigned char' just in case.

David 
		

>  
>  /*
>   * Find the offset on the compressed stream given an index in the
...