[PATCH 2/3] kallsyms: Add 3-byte index into compressed symbols to replace marker scans

[Jim Cromie]

The compressed symbol table (kallsyms_names) packs ~130k kernel symbol
names, in address order, into variable-length records with format
[<len>][<tokenized-strings-wo-\0>].

This layout optimizes address-to-name mapping, but name-to-address
lookups require a linear scan.  To accelerate lookups, kallsyms_markers
was added to record the offset of every 256th entry, cutting the
worst-case walk from 130k to ~128 hops on average.  However, this
still leaves substantial work: during a 17-step binary search in
kallsyms_lookup_names(), the marker walk repeats at every step
(17 * 128), decoding ~2,176 record length headers per lookup.
Address-to-name resolution (sprint_symbol) pays the same 0..255 hop
penalty on every call.

Introduce kallsyms_names_offsets, a 3-byte-per-symbol direct index into
the compressed kallsyms_names table.  scripts/kallsyms.c emits this
table at build-time while writing kallsyms_names, capturing the exact
byte offset for each symbol.  Using 24 bits covers up to 16 MiB of
compressed symbol names, easily spanning the ~2.3 MiB table while
saving 25% space compared to u32 entries.

With kallsyms_names_offsets:

0. get_symbol_offset() performs an O(1) 3-byte table lookup, eliminating
   the ~2,176 header scans per name search.

1. Drop the legacy kallsyms_markers table, saving ~2 KiB of .rodata.

2. Unroll the shift loop in get_symbol_seq() to match
   get_symbol_offset() as a direct 3-byte big-endian load.

Signed-off-by: Jim Cromie <jim.cromie@xxxxxxxxx>
---
 kernel/kallsyms.c          | 43 +++++++------------------------------------
 kernel/kallsyms_internal.h |  2 +-
 scripts/kallsyms.c         | 30 ++++++++++++++----------------
 3 files changed, 22 insertions(+), 53 deletions(-)

diff --git a/kernel/kallsyms.c b/kernel/kallsyms.c
index b9e573e9a10b..21adc5b74ec5 100644
--- a/kernel/kallsyms.c
+++ b/kernel/kallsyms.c
@@ -113,40 +113,14 @@ static char kallsyms_get_symbol_type(unsigned int off)
 
 
 /*
- * Find the offset on the compressed stream given and index in the
+ * Find the offset on the compressed table given an index in the
  * kallsyms array.
  */
-static unsigned int get_symbol_offset(unsigned long pos)
+static inline unsigned int get_symbol_offset(unsigned long pos)
 {
-	const u8 *name;
-	int i, len;
+	const u8 *p = &kallsyms_names_offsets[3 * pos];
 
-	/*
-	 * Use the closest marker we have. We have markers every 256 positions,
-	 * so that should be close enough.
-	 */
-	name = &kallsyms_names[kallsyms_markers[pos >> 8]];
-
-	/*
-	 * Sequentially scan all the symbols up to the point we're searching
-	 * for. Every symbol is stored in a [<len>][<len> bytes of data] format,
-	 * so we just need to add the len to the current pointer for every
-	 * symbol we wish to skip.
-	 */
-	for (i = 0; i < (pos & 0xFF); i++) {
-		len = *name;
-
-		/*
-		 * If MSB is 1, it is a "big" symbol, so we need to look into
-		 * the next byte (and skip it, too).
-		 */
-		if ((len & 0x80) != 0)
-			len = ((len & 0x7F) | (name[1] << 7)) + 1;
-
-		name = name + len + 1;
-	}
-
-	return name - kallsyms_names;
+	return (p[0] << 16) | (p[1] << 8) | p[2];
 }
 
 unsigned long kallsyms_sym_address(int idx)
@@ -157,14 +131,11 @@ unsigned long kallsyms_sym_address(int idx)
 	return (unsigned long)offset_to_ptr(kallsyms_offsets + idx);
 }
 
-static unsigned int get_symbol_seq(int index)
+static inline unsigned int get_symbol_seq(int index)
 {
-	unsigned int i, seq = 0;
-
-	for (i = 0; i < 3; i++)
-		seq = (seq << 8) | kallsyms_seqs_of_names[3 * index + i];
+	const u8 *p = &kallsyms_seqs_of_names[3 * index];
 
-	return seq;
+	return (p[0] << 16) | (p[1] << 8) | p[2];
 }
 
 static int kallsyms_lookup_names(const char *name,
diff --git a/kernel/kallsyms_internal.h b/kernel/kallsyms_internal.h
index 81a867dbe57d..430abccfab63 100644
--- a/kernel/kallsyms_internal.h
+++ b/kernel/kallsyms_internal.h
@@ -12,7 +12,7 @@ extern const unsigned int kallsyms_num_syms;
 extern const char kallsyms_token_table[];
 extern const u16 kallsyms_token_index[];
 
-extern const unsigned int kallsyms_markers[];
+extern const u8 kallsyms_names_offsets[];
 extern const u8 kallsyms_seqs_of_names[];
 
 #endif // LINUX_KALLSYMS_INTERNAL_H_
diff --git a/scripts/kallsyms.c b/scripts/kallsyms.c
index d996a43c4078..83a8747269ff 100644
--- a/scripts/kallsyms.c
+++ b/scripts/kallsyms.c
@@ -44,6 +44,7 @@ struct sym_entry {
 	unsigned long long addr;
 	unsigned int len;
 	unsigned int seq;
+	unsigned int byte_off;
 	unsigned char sym[];
 };
 
@@ -393,7 +394,6 @@ static void write_src(FILE *out_bin_file, const char *out_bin_name)
 {
 	unsigned int i, off;
 	unsigned int best_idx[256];
-	unsigned int *markers, markers_cnt;
 	long bin_start;
 	char buf[KSYM_NAME_LEN];
 
@@ -403,18 +403,12 @@ static void write_src(FILE *out_bin_file, const char *out_bin_name)
 	printf("\t.long\t%u\n", table_cnt);
 	printf("\n");
 
-	/* table of offset markers, that give the offset in the compressed stream
-	 * every 256 symbols */
-	markers_cnt = (table_cnt + 255) / 256;
-	markers = xmalloc(sizeof(*markers) * markers_cnt);
-
 	output_label("kallsyms_names");
 	bin_start = bin_pos(out_bin_file);
 	off = 0;
 	for (i = 0; i < table_cnt; i++) {
-		if ((i & 0xFF) == 0)
-			markers[i >> 8] = off;
 		table[i]->seq = i;
+		table[i]->byte_off = off;
 
 		/* There cannot be any symbol of length zero. */
 		if (table[i]->len == 0) {
@@ -454,14 +448,6 @@ static void write_src(FILE *out_bin_file, const char *out_bin_name)
 	printf(".size kallsyms_names, . - kallsyms_names\n");
 	printf("\n");
 
-	output_label("kallsyms_markers");
-	for (i = 0; i < markers_cnt; i++)
-		printf("\t.long\t%u\n", markers[i]);
-	printf(".size kallsyms_markers, . - kallsyms_markers\n");
-	printf("\n");
-
-	free(markers);
-
 	output_label("kallsyms_token_table");
 	bin_start = bin_pos(out_bin_file);
 	off = 0;
@@ -478,6 +464,7 @@ static void write_src(FILE *out_bin_file, const char *out_bin_name)
 	output_label("kallsyms_token_index");
 	for (i = 0; i < 256; i++)
 		printf("\t.short\t%d\n", best_idx[i]);
+	printf(".size kallsyms_token_index, . - kallsyms_token_index\n");
 	printf("\n");
 
 	output_label("kallsyms_offsets");
@@ -502,6 +489,16 @@ static void write_src(FILE *out_bin_file, const char *out_bin_name)
 	printf(".size kallsyms_offsets, . - kallsyms_offsets\n");
 	printf("\n");
 
+	output_label("kallsyms_names_offsets");
+	for (i = 0; i < table_cnt; i++)
+		printf("\t.byte 0x%02x, 0x%02x, 0x%02x\t/* %s */\n",
+			(unsigned char)(table[i]->byte_off >> 16),
+			(unsigned char)(table[i]->byte_off >> 8),
+			(unsigned char)(table[i]->byte_off >> 0),
+		       table[i]->sym);
+	printf(".size kallsyms_names_offsets, . - kallsyms_names_offsets\n");
+	printf("\n");
+
 	sort_symbols_by_name();
 	output_label("kallsyms_seqs_of_names");
 	bin_start = bin_pos(out_bin_file);
@@ -511,6 +508,7 @@ static void write_src(FILE *out_bin_file, const char *out_bin_name)
 		fputc(table[i]->seq >> 0, out_bin_file);
 	}
 	write_incbin(out_bin_name, bin_start, bin_pos(out_bin_file));
+	printf(".size kallsyms_seqs_of_names, . - kallsyms_seqs_of_names\n");
 	printf("\n");
 }
 

-- 
2.55.0