[PATCH v2 next 13/15] kallsyms: scripts/kallsyms: Reuse tokens that have no references

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

Keep track of the number of times each compression token is used.
If the count becomes zero (eg if the only x are in axb and y is
substituted for xb giving ay) then x can be reused.

This means that a token can refer to a long string without needing
tokens for all the shorter strings.

For my normal kernel build four tokens get reused saving 8.5k of data.
The savings may be greater if there are symbols with long matching prefix.

Signed-off-by: David Laight <david.laight.linux@gmail.com>
---
 scripts/kallsyms.c | 45 ++++++++++++++++++++++++++++++++-------------
 1 file changed, 32 insertions(+), 13 deletions(-)

diff --git a/scripts/kallsyms.c b/scripts/kallsyms.c
index ee06a9c7435f..189fb50ec8c5 100644
--- a/scripts/kallsyms.c
+++ b/scripts/kallsyms.c
@@ -76,6 +76,7 @@ static int token_profit[0x10000];
 static struct token_table {
 	char           *str;		/* Full expansion, '\0' terminated */
 	unsigned short len;		/* Length of str */
+	unsigned int   refs;		/* Number of time used in a symbol */
 } token_table[256];
 
 static void usage(void)
@@ -404,7 +405,8 @@ static void write_src(void)
 	for (i = 0; i < 256; i++) {
 		best_idx[i] = off;
 		off += token_table[i].len + 1;
-		printf("\t.asciz\t\"%s\"\n", token_table[i].str);
+		printf("\t.asciz\t\"%s\"\t/* %u: %u */\n",
+		       token_table[i].str, i, token_table[i].refs);
 	}
 	printf(".size kallsyms_token_table, . - kallsyms_token_table\n");
 	printf("\n");
@@ -512,10 +514,11 @@ static unsigned char *find_token(unsigned char *str, unsigned char *end,
  * to update the counts.
  * Marked noinline to help register allocation. compress_symbols() is only called
  * about 200 times whereas find_token() can be called well over a million times. */
-static __attribute__((noinline)) void compress_symbols(unsigned int token_pair, int idx)
+static __attribute__((noinline)) unsigned int compress_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;
@@ -535,7 +538,10 @@ static __attribute__((noinline)) void compress_symbols(unsigned int token_pair,
 		symbol[i]->len = end - sym;
 	}
 
+	substitutions = token_profit[token_pair];
 	token_profit[token_pair] = 0;
+
+	return substitutions;
 }
 
 /* search the token with the maximum profit */
@@ -558,29 +564,41 @@ static int find_best_token(void)
 /* this is the core of the algorithm: calculate the "best" table */
 static void optimize_result(void)
 {
-	int i, best;
-	unsigned int len;
+	unsigned int i, idx, len, refs;
 	struct token_table *left, *right;
+	unsigned char to_process[256];
 	char *str;
+	int best;
 
-	/* Use the '\0' symbol last so the output is unchanged */
-	for (i = 255; i >= 0; i--) {
-		/* Ignore tokens used for the original character codes. */
-		if (token_table[i].len)
-			continue;
+	/* Generate a list of the unused tokens. */
+	for (i = 0, idx = 0; i < 256; i++) {
+		if (!token_table[i].len)
+			to_process[idx++] = i;
+	}
 
+	do {
 		/* find the token pair with the best profit value */
 		best = find_best_token();
 		if (best < 0)
 			break;
+		i = to_process[--idx];
 
 		/* replace this token pair in all the valid symbols */
-		compress_symbols(best, i);
+		refs = compress_symbols(best, i);
+
+		/* Update the number of times each token is used */
+		token_table[i].refs += refs;
 
 		/* Generate the full name for this symbol */
 		left = &token_table[LEFT(best)];
 		right = &token_table[RIGHT(best)];
+		if (!(left->refs -= refs))
+			/* There are no references left, reuse the token. */
+			to_process[idx++] = LEFT(best);
+		if (!(right->refs -= refs))
+			to_process[idx++] = RIGHT(best);
 
+		/* Generate the full name for this symbol */
 		len = left->len + right->len;
 		str = xmalloc(len + 1);
 		str[len] = 0;
@@ -588,7 +606,7 @@ static void optimize_result(void)
 		memcpy(str + left->len, right->str, right->len);
 		token_table[i].str = str;
 		token_table[i].len = len;
-	}
+	} while (idx);
 }
 
 /* start by placing the symbols that are actually used on the table */
@@ -598,13 +616,14 @@ static void insert_real_symbols_in_table(void)
 
 	for (i = 0; i < symbol_cnt; i++) {
 		for (j = 0; j < symbol[i]->len; j++) {
-			token_table[symbol[i]->sym[j]].len = 1;
+			token_table[symbol[i]->sym[j]].refs++;
 		}
 	}
 
 	for (i = 0; i <= 255; i++) {
-		if (!token_table[i].len)
+		if (!token_table[i].refs)
 			continue;
+		token_table[i].len = 1;
 		token_table[i].str = xmalloc(2);
 		token_table[i].str[0] = i;
 		token_table[i].str[1] = 0;
-- 
2.39.5