Re: [PATCH v3 next 13/13] scripts/kallsyms: Reuse little-used compression tokens

[sashiko-bot@kernel.org]

Thank you for your contribution! Sashiko AI review found 3 potential
issues to consider:
- [Medium] scripts/kallsyms: missing syms update on split in
  uncompress_symbols()
- [Low] scripts/kallsyms: premature 3-char token disqualification in
  split_token()
- [Low] scripts/kallsyms: unreset syms.cnt and splits in
  sym_arr_free_all()
--

commit f874410df5dfe77ff678c52a66379728c6ebf5ba
Author: David Laight <david.laight.linux@gmail.com>

scripts/kallsyms: Reuse little-used compression tokens

This commit reuses compression tokens that have few remaining references by
expanding their occurrences in the symbol table back into their component
tokens when a more common token pair is available.

> diff --git a/scripts/kallsyms.c b/scripts/kallsyms.c
> index 95ccde80359f2..dc69b802478ad 100644
> --- a/scripts/kallsyms.c
> +++ b/scripts/kallsyms.c
[ ... ]
> @@ -850,6 +894,123 @@ compress_symbols(unsigned int token_idx, int compressed_chr)
>  	return subs;
>  }
>  
> +/* Change every occurance of idx back to token_pair/triple.
> + * This extends all the symbol table entries but frees up a token. */
> +static __attribute__((noinline)) void
> +uncompress_symbols(unsigned int token_pair, int idx)
> +{
> +	struct best_table *bt = best_table + idx;
> +	unsigned int sym_idx, len;
> +	unsigned char *sym, *p, *end;
> +	unsigned int substitutions;
> +	unsigned int third_char;
> +
> +	third_char = token_pair >> 16;
> +	token_pair &= 0xffff;
> +
> +	for (int j = 0; j < bt->syms.cnt; j++) {
> +		sym_idx = bt->syms.sym_indexes[j];
> +
> +		sym = table[sym_idx]->sym;
> +		len = table[sym_idx]->len;
> +		end = sym + len;
> +
> +		for (p = sym; (p = memchr(p, idx, len)); p += 2) {
> +			len = end - p - 1;
> +			if (len) {
> +				if (third_char) {
> +					/* Adding three characters */
> +					adjust_profit(sym_idx, idx, third_char, p[1], p[1]);
> +					memmove(p + 3, p + 1, len);
> +				} else {
> +					adjust_profit(sym_idx, idx, token_second(token_pair), p[1], p[1]);
> +					memmove(p + 2, p + 1, len);
> +				}
> +			}
> +			if (p != sym)
> +				adjust_profit(sym_idx, p[-1], p[-1], idx, token_first(token_pair));
> +			token_add_symbol(token_pair, sym_idx);
> +			p[0] = token_first(token_pair);
> +			p[1] = token_second(token_pair);
> +			end++;

[Severity: Medium]
Does uncompress_symbols() need to add sym_idx back to the .syms arrays of
multi-character component tokens when expanding idx into token_pair?

If a multi-character component token was previously split (clearing its
.syms.cnt) and later re-compressed so that first->str and second->str
again concatenate to bt->str across a different subset of symbols,
restoring token_first(token_pair) or token_second(token_pair) into
table[sym_idx]->sym without adding sym_idx to its best_table[].syms array
leaves that symbol untracked.  A subsequent split of that component token
will then miss table[sym_idx]->sym and leave stale token bytes behind when
the slot is reassigned.

> +			if (third_char) {
> +				token_add_symbol(token_index(p[1], third_char), sym_idx);
> +				p[2] = third_char;
> +				end++;
> +				p++;
> +			}
> +		}
> +		table[sym_idx]->len = end - sym;
> +	}
> +
> +	substitutions = bt->refs;
> +
> +	bt->refs = 0;
> +	bt->syms.cnt = 0;
> +	sym_arr_free_all(idx);

[Severity: Low]
Should sym_arr_free_all() reset best_table[ch].syms.cnt and
best_table[ch].splits instead of only clearing bt->syms.cnt here?

When optimize_result() frees a zero-reference token via sym_arr_free_all():

scripts/kallsyms.c:optimize_result() {
    ...
		if (!(first->refs -= refs) && first->len > 1)
			/* There are no references left, reuse the token. */
			to_process[idx++] = sym_arr_free_all(token_first(best));
		if (!(second->refs -= refs) && second->len > 1)
			to_process[idx++] = sym_arr_free_all(token_second(best));
    ...
}

best_table[ch].syms.cnt and best_table[ch].splits retain their values from
the old token.  When that slot is reused by compress_symbols(), new symbol
indices are merged into the stale .syms list (causing uncompress_symbols()
to scan unrelated symbols if the new token is later split), and the new
token inherits the prior token's split count (which may already be
max_splits).

> +
> +	token_profit[token_pair] += substitutions;
> +	best_table[token_first(token_pair)].refs += substitutions;
> +	best_table[token_second(token_pair)].refs += substitutions;
> +
> +	if (third_char) {
> +		best_table[third_char].refs += substitutions;
> +		token_profit[token_index(token_second(token_pair), third_char)] += substitutions;
> +	}
> +}
> +
> +static int split_token(unsigned int profit)
> +{
> +	struct best_table *bt, *first, *second;
> +	const unsigned int max_splits = 10;
> +	unsigned int i, best_token;
> +	int best_ch = -1;
> +
> +	for (i = 0; i < 256; i++) {
> +		bt = best_table + i;
> +
> +		if (bt->len == 1 || bt->refs >= profit || bt->splits >= max_splits)
> +			continue;
> +
> +		/* Ignore tokens where the original parts have been reused ... */
> +		first = &best_table[token_first(bt->token)];
> +		second = &best_table[token_second(bt->token)];
> +		if (bt->len != first->len + second->len ||
> +		    memcmp(bt->str, first->str, first->len) ||
> +		    memcmp(bt->str + first->len, second->str, second->len)) {
> +			/* ... unless they are three characters. */
> +			if (bt->len != 3 || bt->refs * 2 >= profit) {
> +				/* Don't consider again */
> +				bt->splits = max_splits;
> +				continue;
> +			}

[Severity: Low]
Does setting bt->splits = max_splits when bt->len == 3 and
bt->refs * 2 >= profit permanently disqualify 3-character tokens that only
lost to a better candidate in the current scan?

As the loop iterates, profit is lowered to the best candidate's cost
(bt->refs or bt->refs * 2).  Any later 3-character token whose original
components were reused and whose bt->refs * 2 is not strictly less than
that running minimum gets bt->splits set to max_splits, preventing it from
being split on subsequent calls to split_token().

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