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

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

If the symbols contain a lot of "abc" and "abd" and a few "abe" then
the compression code first substitutes (say) 'x' for "ab" giving
"xc", "xd" and "xe".
It might later substitute 'y' for "xc" and 'z' for "xd" giving
"y", "z" and "xe".
The token 'x' is then hardly used, expanding "xe" back to "abe"
costs one byte every time it is used, but frees up 'x' to be used
for a much more common symbol pair.

Add a check at the end of the compression that all the counts still match.

Increases the compression ratio by about 2% on both the 'normal'
kernel I'm building and on the x86-64 allyesconfig kernel.

For simplicity the code will only expand a token where the two tokens
that were merged are still in the table.
It might be possible to find some others, eg ones that are 3 characters.

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

diff --git a/scripts/kallsyms.c b/scripts/kallsyms.c
index 8576fe6ad90b..9dbd7c85eec1 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 short pair;		/* Original token pair for this token */
 	unsigned int   refs;		/* Number of time used in a symbol */
 } token_table[256];
 
@@ -514,6 +515,37 @@ static void build_initial_token_table(void)
 		learn_symbol(symbol[i]->sym, symbol[i]->len);
 }
 
+/* Check that the token_profit[] matches the compressed symbols. */
+static void check_tables(void)
+{
+	unsigned int save_profit[0x10000];
+	unsigned int tok_refs[256];
+	unsigned int i, j;
+
+	memcpy(save_profit, token_profit, sizeof(save_profit));
+	memset(token_profit, 0, sizeof(token_profit));
+
+	build_initial_token_table();
+
+	for (i = 0; i < 0x10000; i++) {
+		if (token_profit[i] != save_profit[i])
+			errx(1, "profit error for %u,%u (%s/%s) discrepency %u != %u\n",
+			     LEFT(i), RIGHT(i), token_table[LEFT(i)].str,
+			     token_table[RIGHT(i)].str, token_profit[i], save_profit[i]);
+	}
+
+	memset(tok_refs, 0, sizeof(tok_refs));
+	for (i = 0; i < symbol_cnt; i++)
+		for (j = 0; j < symbol[i]->len; j++)
+			tok_refs[symbol[i]->sym[j]]++;
+
+	for (i = 1; i < 256; i++) {
+		if (tok_refs[i] != token_table[i].refs)
+			errx(1, "token reference error for %u (%s) %u != %u\n",
+			     i, token_table[i].str, token_table[i].refs, tok_refs[i]);
+	}
+}
+
 static unsigned char *find_token(unsigned char *str, unsigned char *end,
 				 unsigned int want)
 {
@@ -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;
 
-		/* Generate the full name for this symbol */
 		left = &token_table[LEFT(best)];
 		right = &token_table[RIGHT(best)];
 		if (!(left->refs -= refs))
@@ -621,9 +735,10 @@ static void optimize_result(void)
 		str[len] = 0;
 		memcpy(str, left->str, left->len);
 		memcpy(str + left->len, right->str, right->len);
-		token_table[i].str = str;
-		token_table[i].len = len;
-	} while (idx);
+		free(t->str);
+		t->str = str;
+		t->len = len;
+	}
 }
 
 /* start by placing the symbols that are actually used on the table */
@@ -654,6 +769,8 @@ static void optimize_token_table(void)
 	insert_real_symbols_in_table();
 
 	optimize_result();
+
+	check_tables();
 }
 
 /* guess for "linker script provide" symbol */
-- 
2.39.5