All of lore.kernel.org
 help / color / mirror / Atom feed
From: David Laight <david.laight.linux@gmail.com>
To: sashiko-bot@kernel.org
Cc: sashiko-reviews@lists.linux.dev, "Petr Mladek" <pmladek@suse.com>,
	"Kees Cook" <kees@kernel.org>,
	linux-kbuild@vger.kernel.org, bpf@vger.kernel.org,
	"Jim Cromie" <jim.cromie@gmail.com>,
	"Lorenzo Stoakes" <ljs@kernel.org>,
	"Luis Chamberlain" <mcgrof@kernel.org>,
	"Andrey Grodzovsky" <andrey.grodzovsky@crowdstrike.com>,
	"Steven Rostedt" <rostedt@goodmis.org>,
	"Andrii Nakryiko" <andrii@kernel.org>,
	"Samuel Wu" <wusamuel@google.com>,
	nathan@kernel.org, nsc@kernel.org
Subject: Re: [PATCH v4 next 13/13] scripts/kallsyms: Reuse little-used compression tokens
Date: Tue, 17 Nov 2026 11:06:12 +0000	[thread overview]
Message-ID: <20261117110612.1d61025a@pumpkin> (raw)
In-Reply-To: <sashiko-outbox-218682@kernel.org>

On Tue, 17 Nov 2026 10:57:57 +0000
sashiko-bot@kernel.org wrote:

> Thank you for your contribution! Sashiko AI review found 1 potential
> issue to consider:
> - [Medium] scripts/kallsyms: missing syms update on split in
>   uncompress_symbols()
> --
> 
> commit 33aea03661ccead3785f7f56d31a3c8974eb8710
> 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 them back into their component tokens or three-character strings
> when a more common token pair is available.
> 
> > diff --git a/scripts/kallsyms.c b/scripts/kallsyms.c
> > index 42a7c99585c56..976b525c4366d 100644
> > --- a/scripts/kallsyms.c
> > +++ b/scripts/kallsyms.c  
> 
> [ ... ]
> 
> > @@ -855,6 +954,125 @@ 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++;
> > +			if (third_char) {
> > +				token_add_symbol(token_index(p[1], third_char), sym_idx);
> > +				p[2] = third_char;
> > +				end++;
> > +				p++;
> > +			}
> > +		}
> > +		/* sym_idx is already in best_table[].syms from earlier. */
> > +		table[sym_idx]->len = end - sym;
> > +	}  
> 
> [Severity: Medium]
> Can uncompress_symbols() leave sym_idx missing from best_table[].syms for
> token_first(token_pair) or token_second(token_pair)?

Read the comment - it is still in the list.
Quite subtle.

David

> 
> sym_arr_free_all() clears best_table[ch].syms.cnt when a token slot loses
> all references or is uncompressed, while split_token() only checks that
> first->str and second->str still concatenate to bt->str.  If a component
> slot is freed and later reused such that first->str and second->str still
> match bt->str (either reused for the same substring or for a different
> length split of bt->str), its syms array only tracks symbols from the new
> compression and no longer contains sym_idx where bt remained compressed.
> 
> Expanding bt back into those component tokens without adding sym_idx to
> their best_table[].syms arrays triggers the errx() in check_best_refs(), or
> leaves stale token bytes in table[sym_idx]->sym if that component token is
> split again before check_tables() runs.
> 


      reply	other threads:[~2026-11-17 11:06 UTC|newest]

Thread overview: 18+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2026-11-17 10:33 [PATCH v4 next 00/13] kallsyms: optimise symbol search by name David Laight
2026-11-17 10:33 ` [PATCH v4 next 01/13] scripts/kallsyms: Avoid overrunning on-stack buffer David Laight
2026-11-17 10:33 ` [PATCH v4 next 02/13] scripts/kallsyms: Improve error reporting David Laight
2026-11-17 10:33 ` [PATCH v4 next 03/13] scripts/elf-parse: add elf_map_big_endian() helper David Laight
2026-11-17 10:33 ` [PATCH v4 next 04/13] scripts/kallsyms: make use of binary data output optional David Laight
2026-11-17 10:33 ` [PATCH v4 next 05/13] kallsyms: Fix selftest startup delay David Laight
2026-11-17 10:40   ` sashiko-bot
2026-11-17 11:06     ` David Laight
2026-11-17 10:33 ` [PATCH v4 next 06/13] kallsyms: Improve selftest test_perf_kallsyms_lookup_name() output David Laight
2026-11-17 10:33 ` [PATCH v4 next 07/13] kallsyms: Match compressed tokens on the fly during binary search David Laight
2026-11-17 10:33 ` [PATCH v4 next 08/13] kallsyms: Optimise symbol name search David Laight
2026-11-17 10:33 ` [PATCH v4 next 09/13] kallsyms: Add a kernel parameter to change the kallsyms_markers[] density David Laight
2026-11-17 10:33 ` [PATCH v4 next 10/13] scripts/kallsyms: Keep full expansion of tokens David Laight
2026-11-17 10:33 ` [PATCH v4 next 11/13] scripts/kallsyms: Optimise compress_symbols() David Laight
2026-11-17 10:33 ` [PATCH v4 next 12/13] scripts/kallsyms: Reuse tokens that have no references David Laight
2026-11-17 10:33 ` [PATCH v4 next 13/13] scripts/kallsyms: Reuse little-used compression tokens David Laight
2026-11-17 10:57   ` sashiko-bot
2026-11-17 11:06     ` David Laight [this message]

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20261117110612.1d61025a@pumpkin \
    --to=david.laight.linux@gmail.com \
    --cc=andrey.grodzovsky@crowdstrike.com \
    --cc=andrii@kernel.org \
    --cc=bpf@vger.kernel.org \
    --cc=jim.cromie@gmail.com \
    --cc=kees@kernel.org \
    --cc=linux-kbuild@vger.kernel.org \
    --cc=ljs@kernel.org \
    --cc=mcgrof@kernel.org \
    --cc=nathan@kernel.org \
    --cc=nsc@kernel.org \
    --cc=pmladek@suse.com \
    --cc=rostedt@goodmis.org \
    --cc=sashiko-bot@kernel.org \
    --cc=sashiko-reviews@lists.linux.dev \
    --cc=wusamuel@google.com \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.