[PATCH v3 next 10/13] scripts/kallsyms: Keep full expansion of tokens

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

Expand the full string when a new compression token is allocated.
Saves the recursive expansions later on.
It means that token 0 could be used earlier, but the reverse
order is maintained so that the output files can be compared.

The entries for the initial tokens [0-9A-Za-z_.] are now no different
and don't need special casing.

Change find_best_token() to return -1 if there are no tokens
(eg if the input file is very small) to save the caller rechecking
token_profit[].

Save the original symbol name length and check that the expanded
symbol has the same length.

No change to generated output.

Signed-off-by: David Laight <david.laight.linux@gmail.com>
---

About 3ms (in 175ms) can be saved by keeping a copy of the name
itself and avoiding expand_symbol(), but it is messy.
And another 18ms by doing the alphabetic sort in a thread.

v3:
- Reworked on top of the changes in 7.4-rc1
- Avoid printf("%s", NULL) on initial 'no symbol' build.
  While fine with glibc, other libs dump core.

 scripts/kallsyms.c | 156 +++++++++++++++++++++++++--------------------
 1 file changed, 88 insertions(+), 68 deletions(-)

diff --git a/scripts/kallsyms.c b/scripts/kallsyms.c
index c27aaabccd1b..cbf05972043b 100644
--- a/scripts/kallsyms.c
+++ b/scripts/kallsyms.c
@@ -36,7 +36,8 @@
 
 struct sym_entry {
 	unsigned long long addr;
-	unsigned int len;
+	unsigned short len;
+	unsigned short orig_len;
 	unsigned int seq;
 	unsigned char sym[];
 };
@@ -76,12 +77,21 @@ struct sym_arr {
 /* Every pair of bytes is a token. */
 #define NR_TOKENS	0x10000
 
+/*
+ * token_profit[token_index(first, second)] is the number of times the characters
+ * first and second appear adjacent (in that order) and is usually the same
+ * as the number of bytes saved (the profit) by replacing the pair with
+ * a single byte token.
+ */
 static int token_profit[NR_TOKENS];
+/* The symbols that contain each pair of characters. */
 static struct sym_arr token_syms[NR_TOKENS];
 
 /* the table that holds the result of the compression */
-static unsigned char best_table[256][2];
-static unsigned char best_table_len[256];
+static struct best_table {
+	char           *str;		/* Full expansion, '\0' terminated */
+	unsigned short len;		/* Length of str */
+} best_table[256];
 
 static void stamp(const char *where)
 {
@@ -199,6 +209,7 @@ static struct sym_entry *add_symbol(unsigned long long addr, char type,
 	sym = xmalloc(sizeof(*sym) + len + 1);
 	sym->addr = addr;
 	sym->len = len;
+	sym->orig_len = len;
 	sym->sym[0] = type;
 	strcpy(sym_entry_name(sym), name);
 
@@ -351,29 +362,17 @@ static void write_incbin(unsigned long *bin_offset, unsigned long size)
 	*bin_offset += size;
 }
 
-/* uncompress a compressed symbol. When this function is called, the best table
- * might still be compressed itself, so the function needs to be recursive */
-static int expand_symbol(const unsigned char *data, int len, char *result)
+static unsigned int expand_symbol(const unsigned char *data, int len, char *result)
 {
-	int c, rlen, total=0;
-
-	while (len) {
-		c = *data;
-		/* if the table holds a single char that is the same as the one
-		 * we are looking for, then end the search */
-		if (best_table[c][0]==c && best_table_len[c]==1) {
-			*result++ = c;
-			total++;
-		} else {
-			/* if not, recurse and expand */
-			rlen = expand_symbol(best_table[c], best_table_len[c], result);
-			total += rlen;
-			result += rlen;
-		}
-		data++;
-		len--;
+	struct best_table *bt;
+	unsigned int total = 0;
+
+	while (len--) {
+		bt = best_table + *data++;
+		memcpy(result + total, bt->str, bt->len);
+		total += bt->len;
 	}
-	*result=0;
+	result[total] = 0;
 
 	return total;
 }
@@ -405,7 +404,7 @@ static void sort_symbols_by_name(void)
 
 static void write_src(void)
 {
-	unsigned int i, k, len, off, off_size, table_size;
+	unsigned int i, k, off, off_size, table_size;
 	unsigned int best_idx[256];
 	unsigned int *markers, markers_cnt;
 	unsigned long bin_offset = 0;
@@ -422,10 +421,9 @@ static void write_src(void)
 	output_label("kallsyms_token_table");
 	off = 0;
 	for (i = 0; i < 256; i++) {
-		len = expand_symbol(best_table[i], best_table_len[i], buf);
 		best_idx[i] = off;
-		off += len + 1;
-		printf("\t.asciz\t\"%s\"\n", buf);
+		off += best_table[i].len + 1;
+		printf("\t.asciz\t\"%s\"\n", best_table[i].str);
 	}
 	printf(".size kallsyms_token_table, . - kallsyms_token_table\n");
 	printf("\n");
@@ -451,19 +449,15 @@ static void write_src(void)
 	write_incbin_header("names", &bin_offset);
 	off = 0;
 	for (i = 0; i < table_cnt; i++) {
-		unsigned int se_len, len_len;
+		unsigned int len_len;
 		unsigned char len[2];
 
 		se = table[i];
 		se->seq = off;
 
-		/* The length must be less than that of the original symbol. */
-		if (!se->len || se->len > KSYM_NAME_LEN)
-			errx(EXIT_FAILURE, "symbol %d has corrupt compressed length %d",
-			     i, se->len);
-
-		/* Generate the original name */
-		se_len = expand_symbol(se->sym, se->len, buf);
+		/* Generate the original name in a temporary buffer */
+		if (expand_symbol(se->sym, se->len, buf) != se->orig_len)
+			errx(EXIT_FAILURE, "symbol %d has corrupt compressed data", i);
 
 		/* Encode length with ULEB128. */
 		if (se->len <= 0x7F) {
@@ -498,8 +492,8 @@ static void write_src(void)
 		off += len_len + se->len;
 
 		/* Restore the original name. */
-		se->len = se_len;
-		memcpy(se->sym, buf, se_len + 1);
+		se->len = se->orig_len;
+		memcpy(se->sym, buf, se->len + 1);
 	}
 	write_incbin(&bin_offset, off);
 	table_size = off;
@@ -618,7 +612,7 @@ static void write_src(void)
 	write_incbin_header("end", &bin_offset);
 }
 
-static unsigned int token_index(unsigned char first, unsigned char second)
+static unsigned int token_index(unsigned int first, unsigned int second)
 {
 	return first + (second << 8);
 }
@@ -628,6 +622,16 @@ static unsigned int sym_token_index(const unsigned char *symbol, int first_idx)
 	return token_index(symbol[first_idx], symbol[first_idx + 1]);
 }
 
+static unsigned int token_first(unsigned int token)
+{
+	return token & 0xff;
+}
+
+static unsigned int token_second(unsigned int token)
+{
+	return token >> 8;
+}
+
 /* table lookup compression functions */
 
 /* count all the possible tokens in a symbol */
@@ -718,22 +722,23 @@ static void build_initial_token_table(void)
 }
 
 static unsigned char *find_token(unsigned char *str, int len,
-				 const unsigned char *token)
+				 unsigned int want)
 {
+	unsigned int token = token_index(0, *str++);
 	int i;
 
 	for (i = 0; i < len - 1; i++) {
-		if (str[i] == token[0] && str[i+1] == token[1])
-			return &str[i];
+		token = token_index(token_second(token), *str++);
+		if (token == want)
+			return str - 2;
 	}
 	return NULL;
 }
 
 /* replace a given token in all the valid symbols. Use the sampled symbols
  * to update the counts */
-static void compress_symbols(const unsigned char *str, int compressed_chr)
+static void compress_symbols(unsigned int token_idx, int compressed_chr)
 {
-	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;
@@ -746,7 +751,7 @@ static void compress_symbols(const unsigned char *str, int compressed_chr)
 		p1 = table[sym_idx]->sym;
 
 		/* find the token on the symbol */
-		p2 = find_token(p1, len, str);
+		p2 = find_token(p1, len, token_idx);
 		if (!p2) continue;
 
 		/* decrease the counts for this symbol's tokens */
@@ -765,7 +770,7 @@ static void compress_symbols(const unsigned char *str, int compressed_chr)
 			if (size < 2) break;
 
 			/* find the token on the symbol */
-			p2 = find_token(p1, size, str);
+			p2 = find_token(p1, size, token_idx);
 
 		} while (p2);
 
@@ -785,8 +790,8 @@ static int find_best_token(void)
 {
 	int i, best, bestprofit;
 
-	bestprofit=-10000;
-	best = 0;
+	bestprofit = 0;
+	best = -1;
 
 	for (i = 0; i < ARRAY_SIZE(token_profit); i++) {
 		if (token_profit[i] > bestprofit) {
@@ -800,29 +805,39 @@ static int find_best_token(void)
 /* this is the core of the algorithm: calculate the "best" table */
 static void optimize_result(void)
 {
+	struct best_table *bt, *first, *second;
+	unsigned int len;
 	int i, best;
+	char *str;
 
-	/* using the '\0' symbol last allows compress_symbols to use standard
-	 * fast string functions */
+	/* Use the '\0' symbol last so the output is unchanged */
 	for (i = 255; i >= 0; i--) {
+		bt = best_table + i;
+		/* Ignore tokens used for the original character codes. */
+		if (bt->len)
+			continue;
 
-		/* if this table slot is empty (it is not used by an actual
-		 * original char code */
-		if (!best_table_len[i]) {
-
-			/* find the token with the best profit value */
-			best = find_best_token();
-			if (token_profit[best] == 0)
-				break;
-
-			/* place it in the "best" table */
-			best_table_len[i] = 2;
-			best_table[i][0] = best & 0xFF;
-			best_table[i][1] = (best >> 8) & 0xFF;
+		/* Find the token that appears most often. */
+		best = find_best_token();
+		if (best < 0)
+			break;
 
-			/* replace this token in all the valid symbols */
-			compress_symbols(best_table[i], i);
-		}
+		/* Replace this token in all the valid symbols. */
+		compress_symbols(best, i);
+
+		/* Generate the full name for this token ... */
+		first = best_table + token_first(best);
+		second = best_table + token_second(best);
+		len = first->len + second->len;
+		str = xmalloc(len + 1);
+		str[len] = 0;
+		memcpy(str, first->str, first->len);
+		memcpy(str + first->len, second->str, second->len);
+
+		/* ... and save. */
+		free(bt->str);
+		bt->str = str;
+		bt->len = len;
 	}
 }
 
@@ -834,10 +849,15 @@ static void insert_real_symbols_in_table(void)
 	for (i = 0; i < table_cnt; i++) {
 		for (j = 0; j < table[i]->len; j++) {
 			c = table[i]->sym[j];
-			best_table[c][0]=c;
-			best_table_len[c]=1;
+			best_table[c].len = 1;
 		}
 	}
+
+	for (i = 0; i <= 255; i++) {
+		best_table[i].str = xmalloc(2);
+		best_table[i].str[0] = best_table[i].len ? i : 0;
+		best_table[i].str[1] = 0;
+	}
 }
 
 static void optimize_token_table(void)
-- 
2.39.5