[PATCH v3 02/20] kallsyms: index symbols by token to speed up table compression

[Lorenzo Stoakes (ARM)]

On Thu, Sep 17, 2026 at 10:27:32AM -0700, Kees Cook wrote:
> On Thu, Sep 17, 2026 at 05:06:12PM +0100, Lorenzo Stoakes (ARM) wrote:
> > diff --git a/scripts/kallsyms.c b/scripts/kallsyms.c
> > index 494852ade6d8..350d118c3b9e 100644
> > --- a/scripts/kallsyms.c
> > +++ b/scripts/kallsyms.c
> > @@ -58,12 +58,47 @@ static unsigned int table_size, table_cnt;
> >  static int all_symbols;
> >  static int pc_relative;
> >
> > +/* A dynamic array of symbols, encoded by symbol index. */
> > +struct sym_arr {
> > +	unsigned int *sym_indexes;
> > +	unsigned int cnt, cap;
> > +};
> > +
> >  static int token_profit[0x10000];
> > +static struct sym_arr token_syms[0x10000];
>
> Nit: since you're refactoring too, can 0x10000 be a #define so it's not
> open-coded 3 places? (find_best_token() uses the value too, though
> arguably it should actually just use ARRAY_SIZE(token_profit) instead).

Sure, will do!

And yeah ARRAY_SIZE() makes sense there also.

>
> > [...]
> > -static void compress_symbols(const unsigned char *str, int idx)
> > +static void compress_symbols(const unsigned char *str, int compressed_chr)
> >  {
> > -	unsigned int i, len, size;
> > +	const unsigned int token_idx = sym_token_index(str, 0);
> > +	struct sym_arr *arr = &token_syms[token_idx];
> > +	unsigned int sym_idx, j, len, size;
> >  	unsigned char *p1, *p2;
> >
> > -	for (i = 0; i < table_cnt; i++) {
> > +	/* Iterate through all symbols this token is found in and compress. */
> > +	for (j = 0; j < arr->cnt; j++) {
> > +		sym_idx = arr->sym_indexes[j];
> >
> > -		len = table[i]->len;
> > -		p1 = table[i]->sym;
> > +		len = table[sym_idx]->len;
> > +		p1 = table[sym_idx]->sym;
> >
> > -		/* find the token on the symbol */
>
> Why drop this comment? It's a little redundant to "find_token", but I
> always question comment _removal_ when it's not solving an inaccuracy.

Sometimes I lose track which bits are mine/the LLM's, but I don't love
comments that don't add all that much, and I also berate the LLM about
writing the literally worse comments I've ever seen in my life so could
have been either me or it...

Anyway, will restore!

>
> > [...]
> > @@ -536,11 +643,14 @@ static void compress_symbols(const unsigned char *str, int idx)
> >
> >  		} while (p2);
> >
> > -		table[i]->len = len;
> > +		table[sym_idx]->len = len;
> >
> > -		/* increase the counts for this symbol's new tokens */
>
> Same question here: the comment is still valid?

Ack will restore!

>
> Otherwise, looks good to me.
>
> Reviewed-by: Kees Cook <kees at kernel.org>

Thanks!

>
>
> --
> Kees Cook

--
Cheers, Lorenzo