[PATCH v5 04/10] scripts/kallsyms: generate kallsyms_best_token_table[]

[Zhen Lei]

To speed up the lookup of a symbol in the kernel, we'd better compress
the searched symbol first and then make a quick comparison based on the
compressed length and content. But the tokens in kallsyms_token_table[]
have been expanded, a more complex process is required to complete the
compression of a symbol. So generate kallsyms_best_token_table[] helps
us to compress a symbol in the kernel using a process similar to
compress_symbol().

Some minor changes have been made to reduce memory usage and improve
compression performance.
1. Some entries in best_table[] are single characters, and most of them
   are clustered together. such as a-z, A-Z, 0-9. These individual
   characters are not used in the process of compressing a symbol. Let
   kallsyms_best_token_table[i][0] = 0x00, [i][0] = number of consecutive
   single characters (for exampe, a-z is 26). When [i][0] = 0x00 is
   encountered, we can skip to the next token with two elements.
2. Now ARRAY_SIZE(kallsyms_best_token_table) is not fixed, we store
   the content of best_table[] to kallsyms_best_token_table[] in reverse
   order. That is, the higher the frequency, the lower the index.

Signed-off-by: Zhen Lei <thunder.leizhen@xxxxxxxxxx>
---
 kernel/kallsyms_internal.h |  1 +
 scripts/kallsyms.c         | 18 ++++++++++++++++++
 2 files changed, 19 insertions(+)

diff --git a/kernel/kallsyms_internal.h b/kernel/kallsyms_internal.h
index 2d0c6f2f0243a28..d9672ede8cfc215 100644
--- a/kernel/kallsyms_internal.h
+++ b/kernel/kallsyms_internal.h
@@ -26,5 +26,6 @@ extern const char kallsyms_token_table[] __weak;
 extern const u16 kallsyms_token_index[] __weak;
 
 extern const unsigned int kallsyms_markers[] __weak;
+extern const unsigned char kallsyms_best_token_table[] __weak;
 
 #endif // LINUX_KALLSYMS_INTERNAL_H_
diff --git a/scripts/kallsyms.c b/scripts/kallsyms.c
index ca378a7e9425c00..40a6fe6d14ef03f 100644
--- a/scripts/kallsyms.c
+++ b/scripts/kallsyms.c
@@ -499,6 +499,24 @@ static void write_src(void)
 	for (i = 0; i < 256; i++)
 		printf("\t.short\t%d\n", best_idx[i]);
 	printf("\n");
+
+	output_label("kallsyms_best_token_table");
+	for (i = 255, k = 0; (int)i >= 0; i--) {
+		if (best_table_len[i] <= 1) {
+			k++;
+			continue;
+		}
+
+		if (k) {
+			printf("\t.byte 0x00, 0x%02x\n", k);
+			k = 0;
+		}
+
+		printf("\t.byte 0x%02x, 0x%02x\n", best_table[i][0], best_table[i][1]);
+	}
+	if (k)
+		printf("\t.byte 0x00, 0x%02x\n", k);
+	printf("\n");
 }
 
 
-- 
2.25.1