Re: [PATCH 15/15] kallsyms: scripts/kallsyms: Improve compression by about 2%

[David Laight <david.laight.linux@gmail.com>]

On Sun, 18 Oct 2026 16:05:10 +0000
sashiko-bot@kernel.org wrote:

> Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
> - [Medium] kallsyms: infinite loop in optimize_result() on self-overlapping token pairs
> --
> 
> commit 36121744ef0b7fd951486247d0297f67eaca31d8
> Author: David Laight <david.laight.linux@gmail.com>
> 
> kallsyms: scripts/kallsyms: Improve compression by about 2%
> 
> This commit improves kallsyms compression by expanding infrequently used
> merged tokens back into their original constituent pairs when no unused
> tokens remain, freeing slots for more profitable token pairs.
> 
> > diff --git a/scripts/kallsyms.c b/scripts/kallsyms.c
> > index 8576fe6ad90b7..9dbd7c85eec1e 100644
> > --- a/scripts/kallsyms.c
> > +++ b/scripts/kallsyms.c  
...
> > +static int split_token(unsigned int profit)
> > +{
> > +	struct token_table *tt, *left, *right;
> > +	unsigned int i;
> > +	int best = -1;
> > +
> > +	for (i = 0; i < 256; i++) {
> > +		tt = token_table + i;
> > +
> > +		if (tt->len == 1 || tt->refs >= profit)
> > +			continue;
> > +
> > +		/* Ignore tokens where the original parts have be reused */
> > +		left = &token_table[LEFT(tt->pair)];
> > +		right = &token_table[RIGHT(tt->pair)];
> > +		if (tt->len != left->len + right->len ||
> > +		    memcmp(tt->str, left->str, left->len) ||
> > +		    memcmp(tt->str + left->len, right->str, right->len))
> > +			continue;
> > +
> > +		best = i;
> > +		if (tt->refs == 2)
> > +			break;
> > +		profit = tt->refs;
> > +	}
> > +	if (best < 0)
> > +		return -1;
> > +
> > +	uncompress_symbols(token_table[best].pair, best);
> > +
> > +	return best;
> > +}
> > +
>...
> 
> [Severity: Medium]
> Can optimize_result() enter an infinite loop when find_best_token() selects a
> homogeneous token pair best = PAIR(x, x) that overlaps with itself in runs of
> 3 or more identical tokens?
> 
> For a homogeneous pair PAIR(x, x) where LEFT(best) == RIGHT(best),
> learn_symbol() and uncompress_symbols() count every adjacent pair, so a run
> of [x, x, x] increments token_profit[PAIR(x, x)] by 2. However, when
> compress_symbols(PAIR(x, x), i) replaces the first pair to form [i, x], it
> calls:
> 
>     adjust_profit(RIGHT(token_pair), idx, p[2], p[2]);
> 
> which is adjust_profit(x, i, x, x), decrementing token_profit[PAIR(x, x)] by
> 1 for each triple. As a result, compress_symbols() performs fewer
> substitutions (refs) than the initial token_profit[best] passed to
> split_token().

(Well done for spotting that one - it got me confused at one point.
It is one reason why calling it 'profit' (historical name) is wrong.)

In theory maybe, in practise no.
There are two characters that get repeated more than twice (and I don't
remember seeing any repeated tokens.)
They are '_' and 'm'; "__" is by far the most common pair, "mmm" appears
in _commmon_choices_show() in drivers/acpi/platform_profile.c
(and looks like a typo).
A token is allocated to "mm" but there are enough different uses that
it isn't going to get split.

I will put a check in the next version.
(probably just avoiding splitting XX.)

David