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

[sashiko-bot@kernel.org]

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
[ ... ]
> @@ -561,6 +593,47 @@ static __attribute__((noinline)) unsigned int compress_symbols(unsigned int toke
>  	return substitutions;
>  }
>  
> +/* Change every occurance of idx back to token_pair.
> + * This extends all the symbol table entries but frees up a token. */
> +static __attribute__((noinline)) void uncompress_symbols(unsigned int token_pair, int idx)
> +{
> +	unsigned int i, len;
> +	unsigned char *sym, *p, *end;
> +	unsigned int substitutions;
> +
> +	for (i = 0; i < symbol_cnt; i++) {
> +		sym = symbol[i]->sym;
> +		len = symbol[i]->len;
> +		p = memchr(sym, idx, len);
> +		if (!p)
> +			continue;
> +		end = sym + len;
> +
> +		do {
> +			len = end - p - 1;
> +			end++;
> +			if (len) {
> +				adjust_profit(idx, RIGHT(token_pair), p[1], p[1]);
> +				memmove(p + 2, p + 1, len);
> +			}
> +			p[0] = LEFT(token_pair);
> +			p[1] = RIGHT(token_pair);
> +			if (p != sym)
> +				adjust_profit(p[-1], p[-1], idx, LEFT(token_pair));
> +			p = memchr(p + 2, idx, len);
> +		} while (p);
> +		symbol[i]->len = end - sym;
> +	}
> +
> +	substitutions = token_table[idx].refs;
> +
> +	token_profit[token_pair] += substitutions;
> +
> +	token_table[idx].refs = 0;
> +	token_table[LEFT(token_pair)].refs += substitutions;
> +	token_table[RIGHT(token_pair)].refs += substitutions;
> +}
> +
>  /* search the token with the maximum profit */
>  static int find_best_token(void)
>  {
> @@ -578,14 +651,47 @@ static int find_best_token(void)
>  	return best;
>  }
>  
> +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;
> +}
> +
>  /* this is the core of the algorithm: calculate the "best" table */
>  static void optimize_result(void)
>  {
> -	unsigned int i, idx, len, refs;
> -	struct token_table *left, *right;
> +	struct token_table *t, *left, *right;
>  	unsigned char to_process[256];
> +	unsigned int idx, len, refs;
> +	int i, best;
>  	char *str;
> -	int best;
>  
>  	/* Generate a list of the unused tokens. */
>  	for (i = 0, idx = 0; i < 256; i++) {
> @@ -593,20 +699,28 @@ static void optimize_result(void)
>  			to_process[idx++] = i;
>  	}
>  
> -	do {
> +	for (;;) {
>  		/* find the token pair with the best profit value */
>  		best = find_best_token();
>  		if (best < 0)
>  			break;
> -		i = to_process[--idx];
> +		if (idx) {
> +			i = to_process[--idx];
> +		} else {
> +			/* Try to free up a little-used token. */
> +			i = split_token(token_profit[best]);
> +			if (i < 0)
> +				break;
> +		}
>  
>  		/* replace this token pair in all the valid symbols */
>  		refs = compress_symbols(best, i);
> +		t = &token_table[i];
>  
>  		/* Update the number of times each token is used */
> -		token_table[i].refs += refs;
> +		t->refs += refs;
> +		t->pair = 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().

If idx == 0 and a splittable token s representing PAIR(y, z) has
refs < token_table[s].refs < token_profit[PAIR(x, x)] (for example, two
occurrences of [x, x, x] giving token_profit[PAIR(x, x)] = 4 and actual
refs = 2, while token s has token_table[s].refs = 3):

1. optimize_result() calls split_token(4), which selects token s (since
3 < 4) and calls uncompress_symbols(PAIR(y, z), s), setting
token_profit[PAIR(y, z)] = 3. Then compress_symbols(PAIR(x, x), s) performs
only refs = 2 substitutions, setting token_table[s].refs = 2 and
token_table[s].pair = PAIR(x, x).

2. On the next iteration, find_best_token() selects PAIR(y, z) with profit 3.
split_token(3) selects token s again because token_table[s].refs (2) < 3 and
token_table[x] is still valid. uncompress_symbols(PAIR(x, x), s) restores the
two [x, x, x] runs and sets token_profit[PAIR(x, x)] back to 4 (2 from
adjust_profit(s, x, x, x) in the loop plus 2 from substitutions). Then
compress_symbols(PAIR(y, z), s) sets token_table[s].refs = 3.

Would this cause optimize_result() to alternate between splitting and
compressing PAIR(x, x) and PAIR(y, z) indefinitely?

>  
> -		/* Generate the full name for this symbol */
>  		left = &token_table[LEFT(best)];
>  		right = &token_table[RIGHT(best)];
[ ... ]

ওয়াট

-- 
Sashiko AI review · https://sashiko.dev/#/patchset/20261018155206.132411-1-david.laight.linux@gmail.com?part=15