[PATCH v2 next 07/15] kallsyms: Optimise detection of duplicate symbol names

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

While most symbol names are unique, some local symbols have duplicate names.
The first (usually lowest address) one is expected to be returned.

After the binary search finds a match, insted of doing a lookup of the
preceeding symbol to check it isn't a duplicate use the low bit of the
name offset to indicate this is a duplicate of the previous symbol.

If a short linear search fails to find a non-duplicate repeat the binary
search because some symbols (eg __func__.0) can occur hundreds of times.
(Or tens of thousands of times in an allyesconfig kernel.)

Change kallsyms_on_each_match_symbol() to do a linear scan until it finds
a non-duplicate instead does the search in kallsyms_lookup_names().
Add a zero marker to the end of the table so that scan terminates for the
last symbol.

The slowest 'lookup by name' changes being a symbol that is duplicated a lot
to one that is very long.

Rename the kallsyms_off_24/32_of_names symbols to ensure code mismatch
causes a link fail.

Stealing a bit from the name offset means that 32bit offsets are needed
if the compressed name table exceeds 8GB rather than 16GB.
The table for the kernel I'm building is about 1.5GB.

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

diff --git a/kernel/kallsyms.c b/kernel/kallsyms.c
index 31451feac822..e393ede35111 100644
--- a/kernel/kallsyms.c
+++ b/kernel/kallsyms.c
@@ -117,7 +117,7 @@ static int kallsyms_strcmp_symbol(unsigned int off, const char *name)
 {
 	const char *tptr;
 	unsigned int len;
-	const u8 *data = get_symbol_data(off, &len);
+	const u8 *data = get_symbol_data(off >> 1, &len);
 
 	tptr = &kallsyms_token_table[kallsyms_token_index[*data++]] + 1;
 	while (*tptr) {
@@ -221,8 +221,8 @@ static DEFINE_STATIC_KEY_TRUE(kallsyms_off_size_24);
 static inline unsigned int get_symbol_name_offset(unsigned long index)
 {
 	if (static_branch_likely(&kallsyms_off_size_24))
-		return kallsyms_off24_of_names[index].v;
-	return kallsyms_off32_of_names[index];
+		return kallsyms_off_24_of_names[index].v;
+	return kallsyms_off_32_of_names[index];
 }
 
 static void set_kallsyms_off_size(void)
@@ -231,58 +231,51 @@ static void set_kallsyms_off_size(void)
 		static_branch_disable(&kallsyms_off_size_24);
 }
 
-static int kallsyms_lookup_names(const char *name,
-				 unsigned int *start,
-				 unsigned int *end)
+static int kallsyms_lookup_names(const char *name, unsigned int *start)
 {
+	unsigned int mid, off;
+	int low, high;
 	int ret;
-	int low, mid, high;
-	unsigned int off;
 
 	DO_ONCE_LITE(set_kallsyms_off_size);
 
 	low = 0;
 	high = kallsyms_num_syms - 1;
 
-	while (low <= high) {
+	for (;;) {
+		if (low > high)
+			return -1;
 		mid = low + (high - low) / 2;
 		off = get_symbol_name_offset(mid);
 		ret = kallsyms_strcmp_symbol(off, name);
-		if (ret > 0)
+		if (ret > 0) {
 			low = mid + 1;
-		else if (ret < 0)
-			high = mid - 1;
-		else
-			break;
-	}
-
-	if (low > high)
-		return -1;
-
-	ret = off;
-
-	low = mid;
-	while (low) {
-		off = get_symbol_name_offset(low - 1);
-		if (kallsyms_strcmp_symbol(off, name) != 0)
-			break;
-		low--;
-		ret = off;
-	}
-	*start = low;
-
-	if (end) {
-		high = mid;
-		while (high < kallsyms_num_syms - 1) {
-			off = get_symbol_name_offset(high + 1);
-			if (kallsyms_strcmp_symbol(off, name) != 0)
+			continue;
+		}
+		if (!ret) {
+			/*
+			* Found a match, but need the first one.
+			* Most symbols (and all exported/global ones) only occur
+			* once, most of the others only occur a small number of
+			* times so it is worth doing a linear scan that avoids the
+			* kallsyms_strcmp_symbol() call.
+			* However some symbols occur a large number of times
+			* (_sub_D_65535_0 is repeated 24610 times in an x86-64
+			* allyesconfig, __func__.0 442 in a more normal kernel).
+			* Avoid a long linear scan by returning to the binary
+			* search if a short linear search is fruitless.
+			*/
+			unsigned int scan = 16;
+			while ((off & 1) && scan--)
+				off = get_symbol_name_offset(--mid);
+			if (!(off & 1))
 				break;
-			high++;
 		}
-		*end = high;
+		high = mid - 1;
 	}
 
-	return ret;
+	*start = mid;
+	return off;
 }
 
 /* Lookup the address for this symbol. Returns 0 if not found. */
@@ -295,9 +288,9 @@ unsigned long kallsyms_lookup_name(const char *name)
 	if (!*name)
 		return 0;
 
-	ret = kallsyms_lookup_names(name, &i, NULL);
+	ret = kallsyms_lookup_names(name, &i);
 	if (ret >= 0)
-		return get_name_address(ret);
+		return get_name_address(ret >> 1);
 
 	return module_kallsyms_lookup_name(name);
 }
@@ -328,18 +321,19 @@ int kallsyms_on_each_match_symbol(int (*fn)(void *, unsigned long),
 				  const char *name, void *data)
 {
 	int name_offset, ret;
-	unsigned int sym_number, last;
+	unsigned int sym_number;
 
-	name_offset = kallsyms_lookup_names(name, &sym_number, &last);
+	name_offset = kallsyms_lookup_names(name, &sym_number);
 	if (name_offset < 0)
 		return 0;
 
-	for (;; name_offset = get_symbol_name_offset(sym_number)) {
-		ret = fn(data, get_name_address(name_offset));
-		if (ret || ++sym_number > last)
+	do {
+		ret = fn(data, get_name_address(name_offset >> 1));
+		if (ret)
 			break;
 		cond_resched();
-	}
+		name_offset = get_symbol_name_offset(++sym_number);
+	} while (name_offset & 1);
 
 	return ret;
 }
diff --git a/kernel/kallsyms_internal.h b/kernel/kallsyms_internal.h
index ec6eca5654e6..e4a1f737aed1 100644
--- a/kernel/kallsyms_internal.h
+++ b/kernel/kallsyms_internal.h
@@ -15,7 +15,7 @@ extern const u16 kallsyms_token_index[];
 extern const unsigned int kallsyms_markers[];
 
 extern const unsigned int kallsyms_off_size;
-extern struct { unsigned int v:24 __packed; } __packed kallsyms_off24_of_names[] __weak;
-extern u32 kallsyms_off32_of_names[] __weak;
+extern struct { unsigned int v:24 __packed; } __packed kallsyms_off_24_of_names[] __weak;
+extern u32 kallsyms_off_32_of_names[] __weak;
 
 #endif // LINUX_KALLSYMS_INTERNAL_H_
diff --git a/scripts/kallsyms.c b/scripts/kallsyms.c
index a02fa17428d3..2e579e1cf7de 100644
--- a/scripts/kallsyms.c
+++ b/scripts/kallsyms.c
@@ -433,11 +433,14 @@ static void write_src(void)
 	printf("\n");
 
 	sort_symbols_by_name();
-	off_size = table_size < (1u << 24) ? 24 : 32;
+	off_size = table_size < (1u << 23) ? 24 : 32;
 	output_value("kallsyms_off_size", off_size);
-	output_label(off_size == 24 ? "kallsyms_off24_of_names" : "kallsyms_off32_of_names");
+	output_label(off_size == 24 ? "kallsyms_off_24_of_names" : "kallsyms_off_32_of_names");
 	for (i = 0; i < table_cnt; i++) {
-		off = table[i]->seq;
+		off = table[i]->seq << 1;
+		if (i && !strcmp((char *)table[i - 1]->sym + 1, (char *)table[i]->sym + 1))
+			/* Mark that this is a duplicate of the previous symbol */
+			off |= 1;
 		if (off_size == 24) {
 #ifdef CONFIG_CPU_BIG_ENDIAN
 			off = __builtin_bswap32(off) >> 8;
@@ -449,7 +452,12 @@ static void write_src(void)
 			printf("\t.long\t%#04x\t/* %s */\n", off, table[i]->sym);
 		}
 	}
-	printf(".size kallsyms_off%d_of_names, . - kallsyms_off%d_of_names\n", off_size, off_size);
+	/* Terminator without the 'duplicate' flag. */
+	if (off_size == 24)
+		printf("\t.byte\t0,0,0\n");
+	else
+		printf("\t.long\t0\n");
+	printf(".size kallsyms_off_%d_of_names, . - kallsyms_off_%d_of_names\n", off_size, off_size);
 
 	fflush(stdout);
 	if (ferror(stdout))
-- 
2.39.5