[PATCH v2 next 08/15] kallsyms: Support changing the density of the kallsyms_markers[] array

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

The density is a tradeoff between data size and execution speed.
Reducing it from 256 to 64 gives a 35% improvement for name lookups.

Change scripts/kallsyms to take the density from a --marker-shift command
line parameter so that it can be build specific.
The default is unchanged at 1 marker per 256 symbols.

Signed-off-by: David Laight <david.laight.linux@gmail.com>
---
 kernel/kallsyms.c          | 16 +++++++---------
 kernel/kallsyms_internal.h |  1 +
 scripts/kallsyms.c         | 30 ++++++++++++++++++++++--------
 3 files changed, 30 insertions(+), 17 deletions(-)

diff --git a/kernel/kallsyms.c b/kernel/kallsyms.c
index e393ede35111..ff2da8c8f7e3 100644
--- a/kernel/kallsyms.c
+++ b/kernel/kallsyms.c
@@ -148,13 +148,11 @@ static int kallsyms_strcmp_symbol(unsigned int off, const char *name)
 static unsigned int get_symbol_offset(unsigned long pos)
 {
 	const u8 *name;
-	int i, len;
+	int len;
 
-	/*
-	 * 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]];
+	/* Scan from the marker before the requested symbol number */
+	name = &kallsyms_names[kallsyms_markers[pos >> kallsyms_marker_shift]];
+	pos &= (1 << kallsyms_marker_shift) - 1;
 
 	/*
 	 * Sequentially scan all the symbols up to the point we're searching
@@ -162,7 +160,7 @@ static unsigned int get_symbol_offset(unsigned long pos)
 	 * 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++) {
+	while (pos--) {
 		len = *name;
 
 		/*
@@ -186,7 +184,7 @@ static unsigned long get_name_address(unsigned int name_offset)
 	unsigned int low, pos, high;
 
 	low = 0;
-	high = ((kallsyms_num_syms - 1) >> 8) + 1;
+	high = ((kallsyms_num_syms - 1) >> kallsyms_marker_shift) + 1;
 
 	while (high - low > 1) {
 		pos = low + (high - low) / 2;
@@ -197,7 +195,7 @@ static unsigned long get_name_address(unsigned int name_offset)
 	}
 
 	pos = kallsyms_markers[low];
-	for (low <<= 8; pos < name_offset; low++) {
+	for (low <<= kallsyms_marker_shift; pos < name_offset; low++) {
 		unsigned int len = kallsyms_names[pos];
 		if (len & 0x80)
 			len += (kallsyms_names[pos + 1] << 7) - 0x7f;
diff --git a/kernel/kallsyms_internal.h b/kernel/kallsyms_internal.h
index e4a1f737aed1..b98469b5c2f5 100644
--- a/kernel/kallsyms_internal.h
+++ b/kernel/kallsyms_internal.h
@@ -12,6 +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_marker_shift;
 extern const unsigned int kallsyms_markers[];
 
 extern const unsigned int kallsyms_off_size;
diff --git a/scripts/kallsyms.c b/scripts/kallsyms.c
index 2e579e1cf7de..d2d3ac8c33a1 100644
--- a/scripts/kallsyms.c
+++ b/scripts/kallsyms.c
@@ -58,6 +58,8 @@ static struct sym_entry **table;
 static unsigned int table_size, table_cnt;
 static int all_symbols;
 static int pc_relative;
+/* Default to one kallsyms_markers[] entry for each 256 symbols */
+static unsigned long marker_shift = 8;
 
 static int token_profit[0x10000];
 
@@ -68,7 +70,7 @@ static unsigned char best_table_len[256];
 
 static void usage(void)
 {
-	fprintf(stderr, "Usage: kallsyms [--all-symbols] in.map > out.S\n");
+	fprintf(stderr, "Usage: kallsyms [--all-symbols] [--pc-relative] [--marker-shift=n] in.map > out.S\n");
 	exit(1);
 }
 
@@ -391,8 +393,9 @@ static void write_src(void)
 	printf(".size kallsyms_names, . - kallsyms_names\n");
 	printf("\n");
 
+	output_value("kallsyms_marker_shift", marker_shift);
 	output_label("kallsyms_markers");
-	for (i = 0; i < table_cnt; i += 256)
+	for (i = 0; i < table_cnt; i += 1u << marker_shift)
 		printf("\t.long\t%u\n", table[i]->seq);
 	printf(".size kallsyms_markers, . - kallsyms_markers\n");
 	printf("\n");
@@ -696,17 +699,28 @@ int main(int argc, char **argv)
 {
 	while (1) {
 		static const struct option long_options[] = {
-			{"all-symbols",     no_argument, &all_symbols,     1},
-			{"pc-relative",     no_argument, &pc_relative,     1},
+			{"all-symbols", no_argument, &all_symbols, 1},
+			{"pc-relative", no_argument, &pc_relative, 1},
+			{"marker-shift", required_argument, NULL, 'm'},
 			{},
 		};
 
-		int c = getopt_long(argc, argv, "", long_options, NULL);
-
-		if (c == -1)
+		switch (getopt_long(argc, argv, "", long_options, NULL)) {
+		case -1:
 			break;
-		if (c != 0)
+		case 0:
+			continue;
+		case 'm':
+			if (!optarg[0])
+				continue;
+			marker_shift = strtoul(optarg, NULL, 10);
+			if (marker_shift > 24)
+				usage();
+			continue;
+		default:
 			usage();
+		}
+		break;
 	}
 
 	if (optind >= argc)
-- 
2.39.5