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

From: Zhen Lei
Date: Fri Sep 23 2022 - 07:22:27 EST


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