[PATCH v2 next 00/15] kallsyms: optimise symbol search by name

[PATCH v2 next 00/15] kallsyms: optimise symbol search by name

[David Laight]

These patches speed up the lookup of symbol names by a factor of about 18
while both reducing the size of the compressed data by 9.5% (for my kernel)
and speeding up the compression code itself.
As well as improving the normal symbol lookup, looking up symbols that occur
a lot of times is also massively improved.

Patch 1 is a stack buffer overrun - but in a program run during the build
    so is isn't that improtant.
Patches 2 and 4 are minor fixes.
Patch 3 is a big update to the selftest output to make it less affected by
    interrupts (etc) and visually more obvious.
Patch 5 is from Jim Cromie and optimises the name compare.
    I think this is the final version of his patch, but any one will do.
    The following patches are built on top of it.
Patches 6 and 7 improve the search by name code.
Patches 8 and 9 make the 'marker density' a kernel build option and change
    the default from 1:256 to 1:64 (one bit for two symbols).
    This change gives a 33% improvement on top of that from patches 6 and 7.
Patches 10 and 11 are preparatory changes to scripts/kallsyms.c.
Patch 12 speeds up the compression code by about 50%, it will be a more
    for kernels with a lot of long symbol names.
    Reading and writing the files isn't quick, but is faster than the
    compression code.
Patch 13 reuses unused compression tokens to improve the compression ratio.
    (Patch 11 means they don't have to be kept to expand tokens.)
Patch 14 just shortens the output file.
    I didn't go as far as replacing all the printf("%u", x) with
    fputs(str[x], stdout) - but that is a lot faster.
Patch 15 improves the compression ratio by splitting little used tokens so that
    they can be used for more common token pairs.

Most of the testing was done with a rather hacked together userspace wrapper
that contains enough #defines to compile the kernel files as a user program.
The program and its Makefile could be commited somewhere - suggestions?

As well as my normal kernel (I've booted a kernel containing most of the changes)
I've run the tests on an x86-64 allyesconfig build, the timings are similar.
I've not run the selftests on the allyesconfig with the original code - I don't
want to think how long it would take!

Some test ouput...

kallsyms_selftest output (run in a userspace wrapper).
The results are comparable to each other, but the in-kernel results
seem to be faster (possibly due to optimisation choices for functions
like memcpy().

TL;DR
The average value is a much better indication of speed than the
fastest (usually the middle of the table).
The slow times are likely to be worse than the figures imply, the tests
take long enough that the cpu clock frequency is likely to increase.

Baseline (based  on 7.3.0-rc4):
 ---------------------------------------------------------
| nr_symbols | compressed size | original size | ratio(%) |
|---------------------------------------------------------|
|     123312 |       1584006   |      2969490  |  53.34   |
 ---------------------------------------------------------
kallsyms_on_each_symbol() traverse all: 7507638 ns
kallsyms_on_each_match_symbol() traverse all: 9418 ns
kallsyms_lookup_name() looked up 123312 symbols, average 3753 ns
	fastest 341 ns (bpf_get_netns_cookie_sock_ops_proto)
	slowest 78069 ns (__func__.0)
	Distribution, 1280ns per column, 8714 counts per *:
	|  *
	|  *
	|  *
	|  *
	|  **
	| ***
	| ***
	|************ ****************                 ***************

After 'Match compressed tokens on the fly during binary search'.
This doesn't make much difference (yet) because the linear scan dominates.
 ---------------------------------------------------------
| nr_symbols | compressed size | original size | ratio(%) |
|---------------------------------------------------------|
|     123312 |       1584006   |      2969490  |  53.34   |
 ---------------------------------------------------------
kallsyms_on_each_symbol() traverse all: 7521035 ns
kallsyms_on_each_match_symbol() traverse all: 7986 ns
kallsyms_lookup_name() looked up 123312 symbols, average 3661 ns
	fastest 411 ns (pciehp_poll_mode)
	slowest 76677 ns (__func__.0)
	Distribution, 1280ns per column, 8759 counts per *:
	|  *
	|  *
	|  *
	|  *
	|  *
	| ***
	| ***
	|******** *  *   **    **   **                            ***

After 'Optimise symbol name search'.
 ---------------------------------------------------------
| nr_symbols | compressed size | original size | ratio(%) |
|---------------------------------------------------------|
|     123312 |       1584006   |      2969490  |  53.34   |
 ---------------------------------------------------------
kallsyms_on_each_symbol() traverse all: 7547445 ns
kallsyms_on_each_match_symbol() traverse all: 1733 ns
kallsyms_lookup_name() looked up 123312 symbols, average 377 ns
	fastest 90 ns (pkcs1pad_create)
	slowest 4578 ns (io_register_clone_buffers)
	Distribution, 80ns per column, 3494 counts per *:
	|   ***
	|   ***
	|   ***
	|  *****
	|  *****
	|  *****
	|  ******
	| *******************           ***        *              *

After 'Optimise detection of duplicate symbol names'
marker density 256:
 ---------------------------------------------------------
| nr_symbols | compressed size | original size | ratio(%) |
|---------------------------------------------------------|
|     123312 |       1584006   |      2969490  |  53.34   |
 ---------------------------------------------------------
kallsyms_on_each_symbol() traverse all: 7620445 ns
kallsyms_on_each_match_symbol() traverse all: 2976 ns
kallsyms_lookup_name() looked up 123312 symbols, average 336 ns
	fastest 90 ns (shmem_unuse)
	slowest 2044 ns (The_time_has_come_the_Walrus_said_To_talk_of_many_things_Of_sho)
	Distribution, 40ns per column, 1912 counts per *:
	|      *****
	|     *******
	|    ********
	|    *********
	|    *********
	|    *********
	|   ***********
	|  ******************                               *

With the marker denstity reduced to 64
 ---------------------------------------------------------
| nr_symbols | compressed size | original size | ratio(%) |
|---------------------------------------------------------|
|     123312 |       1584006   |      2969490  |  53.34   |
 ---------------------------------------------------------
kallsyms_on_each_symbol() traverse all: 7654179 ns
kallsyms_on_each_match_symbol() traverse all: 2405 ns
kallsyms_lookup_name() looked up 123312 symbols, average 204 ns
	fastest 60 ns (_rs.0)
	slowest 802 ns (The_time_has_come_the_Walrus_said_To_talk_of_many_things_Of_sho)
	Distribution, 20ns per column, 2783 counts per *:
	|         **
	|        ****
	|        ****
	|        *****
	|       ******
	|       *******
	|      *********
	|   **********************               *

After 'Reuse tokens that have no references'.
Improves the compressions ratio slightly.
 ---------------------------------------------------------
| nr_symbols | compressed size | original size | ratio(%) |
|---------------------------------------------------------|
|     123312 |       1575323   |      2969490  |  53.05   |
 ---------------------------------------------------------
kallsyms_on_each_symbol() traverse all: 7652996 ns
kallsyms_on_each_match_symbol() traverse all: 2625 ns
kallsyms_lookup_name() looked up 123312 symbols, average 203 ns
	fastest 60 ns (_rs.0)
	slowest 831 ns (The_time_has_come_the_Walrus_said_To_talk_of_many_things_Of_sho)
	Distribution, 20ns per column, 2876 counts per *:
	|         **
	|        ****
	|        ****
	|        *****
	|       ******
	|       *******
	|      *********
	|   ********************   *     *        *


Final version.
Improves the compression ratio again.
 ---------------------------------------------------------
| nr_symbols | compressed size | original size | ratio(%) |
|---------------------------------------------------------|
|     123312 |       1505184   |      2969490  |  50.68   |
 ---------------------------------------------------------
kallsyms_on_each_symbol() traverse all: 7742950 ns
kallsyms_on_each_match_symbol() traverse all: 951 ns
kallsyms_lookup_name() looked up 123312 symbols, average 200 ns
	fastest 60 ns (_rs.0)
	slowest 662 ns (The_time_has_come_the_Walrus_said_To_talk_of_many_things_Of_sho)
	Distribution, 20ns per column, 2916 counts per *:
	|         **
	|        ****
	|        ****
	|        ****
	|       ******
	|       *******
	|      *********
	|   ******************  **    * * *


David Laight (14):
  kallsyms: scripts/kallsyms.c: Avoid overrunning on-stack buffer
  kallsyms: Fix selftest startup delay
  kallsyms: Improve selftest test_perf_kallsyms_lookup_name() output
  kallsyms: scripts/kallsyms: Check for output file write errors
  kallsyms: Optimise symbol name search
  kallsyms: Optimise detection of duplicate symbol names
  kallsyms: Support changing the density of the kallsyms_markers[] array
  kallsyms: Add a kernel parameter for the marker shift
  kallsyms: scripts/kallsyms: Rename some variables for clarity
  kallsyms: scripts/kallsyms: Keep full expansion of tokens
  kallsyms: scripts/kallsyms: Optimise compress_symbols()
  kallsyms: scripts/kallsyms: Reuse tokens that have no references
  kallsyms: scripts/kallsyms: Reduce the output file size
  kallsyms: scripts/kallsyms: Improve compression by about 2%

Jim Cromie (1):
  kallsyms: Match compressed tokens on the fly during binary search

 init/Kconfig               |  19 ++
 kernel/kallsyms.c          | 242 +++++++++------
 kernel/kallsyms_internal.h |   6 +-
 kernel/kallsyms_selftest.c | 169 ++++++++---
 scripts/Makefile           |   1 +
 scripts/kallsyms.c         | 586 ++++++++++++++++++++++++-------------
 scripts/link-vmlinux.sh    |   6 +
 7 files changed, 687 insertions(+), 342 deletions(-)

-- 
2.39.5

[PATCH v2 next 01/15] kallsyms: scripts/kallsyms.c: Avoid overrunning on-stack buffer

[David Laight]

A maximum length symbol can be KSYM_NAME_LEN long (including the '\0').
But the name being compressed contains a leading symbol type (e.g. T).
So when the compressed name is expanded (after the hex is written out)
the buffer needs to be KSYM_NAME_LEN+1 bytes long to allow to both the
symbol type and the '\0'.
But it is declared 'char buf[KSYM_NAME_LEN] so a maximal length name
overwrites something on stack.

Found by code inspection, seems to have been broken before the code
was imported into git.

I expect there aren't any maximal length symbols and/or the byte that
is overwritten is something that is either zero or 'don't care'.

Signed-off-by: David Laight <david.laight.linux@gmail.com>
---
 scripts/kallsyms.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/scripts/kallsyms.c b/scripts/kallsyms.c
index 494852ade6d8..bda8921c95ef 100644
--- a/scripts/kallsyms.c
+++ b/scripts/kallsyms.c
@@ -341,7 +341,7 @@ static void write_src(void)
 	unsigned int i, k, off;
 	unsigned int best_idx[256];
 	unsigned int *markers, markers_cnt;
-	char buf[KSYM_NAME_LEN];
+	char buf[1 + KSYM_NAME_LEN];
 
 	printf("\t.section .rodata, \"a\"\n");
 
-- 
2.39.5

[PATCH v2 next 02/15] kallsyms: Fix selftest startup delay

[David Laight]

The kallsym_selftest code clearly intends to sleep until initialisation
is complete in order to get more reproducable timings.

Replace the schedule_timeout() calls with schedule_timeout_idle()
so that the thread actually sleeps.
Poll every second (not every 5) for SYSTEM_RUNNING and then wait
another 10 seconds before starting the tests, otherwise the tests
start as soon an init is executed.

This code is in the initial 2022 import of the tests.

Signed-off-by: David Laight <david.laight.linux@gmail.com>
---
 kernel/kallsyms_selftest.c | 4 +++-
 1 file changed, 3 insertions(+), 1 deletion(-)

diff --git a/kernel/kallsyms_selftest.c b/kernel/kallsyms_selftest.c
index 8f6c4e9b3a1c..0db79237fe54 100644
--- a/kernel/kallsyms_selftest.c
+++ b/kernel/kallsyms_selftest.c
@@ -411,9 +411,11 @@ static int test_entry(void *p)
 {
 	int ret;
 
+	pr_info("waiting\n");
 	do {
-		schedule_timeout(5 * HZ);
+		schedule_timeout_idle(HZ);
 	} while (system_state != SYSTEM_RUNNING);
+	schedule_timeout_idle(10 * HZ);
 
 	pr_info("start\n");
 	ret = test_kallsyms_basic_function();
-- 
2.39.5

[PATCH v2 next 03/15] kallsyms: Improve selftest test_perf_kallsyms_lookup_name() output

[David Laight]

- Improve the test stability/reproducability by taking the faster of
  two calls to kallsyms_lookup_name().
- Check that kallsyms_lookup_name() returns the expected address
  unless the symbol is duplicated.
- Report the names of the min/max symbols.
- Output an 8 line 64 entry histogram of the times taken.
- This shows there is a reasonably normal distribution with a small
  number of much slower outliers that don't really affect the average.

Additionally:
- Add a very long symbol to check the handling of two byte lengths.
- Do the test_perf_kallsyms_lookup_name() last because it can take long
  enough that the CPU frequency changes and the times reported by the
  other tests can change.
- Mark the 4 test functions noinline_for_stack since they all have a
  quite large on-stack structure.

Signed-off-by: David Laight <david.laight.linux@gmail.com>
---
 kernel/kallsyms_selftest.c | 165 ++++++++++++++++++++++++++++---------
 1 file changed, 125 insertions(+), 40 deletions(-)

diff --git a/kernel/kallsyms_selftest.c b/kernel/kallsyms_selftest.c
index 0db79237fe54..9072bd91c318 100644
--- a/kernel/kallsyms_selftest.c
+++ b/kernel/kallsyms_selftest.c
@@ -22,6 +22,8 @@
 
 
 #define MAX_NUM_OF_RECORDS		64
+#define HISTOGRAM_BUCKETS		64
+#define HISTOGRAM_RESOLUTION		10
 
 struct test_stat {
 	int min;
@@ -29,35 +31,56 @@ struct test_stat {
 	int save_cnt;
 	int real_cnt;
 	int perf;
-	u64 sum;
 	char *name;
 	unsigned long addr;
 	unsigned long addrs[MAX_NUM_OF_RECORDS];
 };
 
+struct lookup_name_info {
+	unsigned int count;
+	unsigned int min;
+	unsigned int max;
+	u64 sum;
+	char min_name[64];
+	char max_name[64];
+	unsigned int histogram[HISTOGRAM_BUCKETS];
+	unsigned int scale;
+};
+
 struct test_item {
 	char *name;
 	unsigned long addr;
 };
 
-#define ITEM_FUNC(s)				\
-	{					\
-		.name = #s,			\
-		.addr = (unsigned long)s,	\
-	}
-
-#define ITEM_DATA(s)				\
+#define _TEST_ITEM(s)				\
 	{					\
 		.name = #s,			\
 		.addr = (unsigned long)&s,	\
 	}
 
+#define TEST_ITEM(s) _TEST_ITEM(s)
 
 static int kallsyms_test_var_bss_static;
 static int kallsyms_test_var_data_static = 1;
 int kallsyms_test_var_bss;
 int kallsyms_test_var_data = 1;
 
+/* This is 509 characters, compresses to about 330 */
+#define kallsyms_very_long_name \
+The_time_has_come_the_Walrus_said_To_talk_of_many_things\
+_Of_shoes_and_ships_and_sealing_wax_Of_cabbages_and_kings\
+_And_why_the_sea_is_boiling_hot_And_whether_pigs_have_wings\
+\
+_O_Oysters_said_the_Carpenter_Youve_had_a_pleasant_run\
+_Shall_we_be_trotting_home_again_But_answer_came_there_none\
+_And_this_was_scarcely_odd_because_Theyd_eaten_every_one\
+\
+_The_moon_was_shining_sulkily_Because_she_thought_the_sun\
+_Had_got_no_business_to_be_there_After_the_day_was_done\
+_Its_very_rude_of_him_she_said_To_come_and_spoil_the_fun
+
+static int kallsyms_very_long_name = 1;
+
 static int kallsyms_test_func_static(void)
 {
 	kallsyms_test_var_bss_static++;
@@ -79,16 +102,17 @@ __weak int kallsyms_test_func_weak(void)
 }
 
 static struct test_item test_items[] = {
-	ITEM_FUNC(kallsyms_test_func_static),
-	ITEM_FUNC(kallsyms_test_func),
-	ITEM_FUNC(kallsyms_test_func_weak),
-	ITEM_FUNC(vmalloc_noprof),
-	ITEM_FUNC(vfree),
+	TEST_ITEM(kallsyms_test_func_static),
+	TEST_ITEM(kallsyms_test_func),
+	TEST_ITEM(kallsyms_test_func_weak),
+	TEST_ITEM(vmalloc_noprof),
+	TEST_ITEM(vfree),
 #ifdef CONFIG_KALLSYMS_ALL
-	ITEM_DATA(kallsyms_test_var_bss_static),
-	ITEM_DATA(kallsyms_test_var_data_static),
-	ITEM_DATA(kallsyms_test_var_bss),
-	ITEM_DATA(kallsyms_test_var_data),
+	TEST_ITEM(kallsyms_test_var_bss_static),
+	TEST_ITEM(kallsyms_test_var_data_static),
+	TEST_ITEM(kallsyms_very_long_name),
+	TEST_ITEM(kallsyms_test_var_bss),
+	TEST_ITEM(kallsyms_test_var_data),
 #endif
 };
 
@@ -101,7 +125,7 @@ static int stat_symbol_len(void *data, const char *name, unsigned long addr)
 	return 0;
 }
 
-static void test_kallsyms_compression_ratio(void)
+static noinline_for_stack void test_kallsyms_compression_ratio(void)
 {
 	u32 pos, off, len, num;
 	u32 ratio, total_size, total_len = 0;
@@ -153,38 +177,99 @@ static void test_kallsyms_compression_ratio(void)
 	pr_info(" ---------------------------------------------------------\n");
 }
 
+static int is_duplicate(void *data, unsigned long addr)
+{
+	return (*(int *)data)++;
+}
+
 static int lookup_name(void *data, const char *name, unsigned long addr)
 {
-	u64 t0, t1, t;
-	struct test_stat *stat = (struct test_stat *)data;
+	struct lookup_name_info *info = data;
+	unsigned int i, t0, t1, t;
+	unsigned long got_addr;
 
+	/* Improve the stability by taking the fastest of two calls. */
 	t0 = ktime_get_ns();
 	(void)kallsyms_lookup_name(name);
 	t1 = ktime_get_ns();
-
 	t = t1 - t0;
-	if (t < stat->min)
-		stat->min = t;
+	got_addr = kallsyms_lookup_name(name);
+	t0 = ktime_get_ns();
+	if (t0 - t1 < t)
+		t = t0 - t1;
 
-	if (t > stat->max)
-		stat->max = t;
+	if (addr != got_addr) {
+		int c = 0;
 
-	stat->real_cnt++;
-	stat->sum += t;
+		if (!kallsyms_on_each_match_symbol(is_duplicate, name, &c)) {
+			pr_info("got %ld not %ld for %s\n", got_addr, addr, name);
+			return 1;
+		}
+	}
+
+	info->count++;
+	info->sum += t;
+
+	if (t < info->min) {
+		info->min = t;
+		strscpy(info->min_name, name);
+	}
+
+	if (t > info->max) {
+		info->max = t;
+		strscpy(info->max_name, name);
+	}
+
+	/* Create a histogram of the times */
+	t = (t / HISTOGRAM_RESOLUTION) >> info->scale;
+	while (t >= HISTOGRAM_BUCKETS) {
+		t >>= 1;
+		info->scale++;
+		for (i = 0; i < HISTOGRAM_BUCKETS / 2; i++)
+			info->histogram[i] = info->histogram[2 * i] + info->histogram[2 * i + 1];
+		for (; i < HISTOGRAM_BUCKETS; i++)
+			info->histogram[i] = 0;
+	}
+	info->histogram[t]++;
 
 	return 0;
 }
 
-static void test_perf_kallsyms_lookup_name(void)
+static noinline_for_stack void test_perf_kallsyms_lookup_name(void)
 {
-	struct test_stat stat;
-
-	memset(&stat, 0, sizeof(stat));
-	stat.min = INT_MAX;
-	kallsyms_on_each_symbol(lookup_name, &stat);
-	pr_info("kallsyms_lookup_name() looked up %d symbols\n", stat.real_cnt);
-	pr_info("The time spent on each symbol is (ns): min=%d, max=%d, avg=%lld\n",
-		stat.min, stat.max, div_u64(stat.sum, stat.real_cnt));
+	struct lookup_name_info info;
+	unsigned int idx, scale, row;
+	char line[HISTOGRAM_BUCKETS];
+	int len;
+
+	memset(&info, 0, sizeof(info));
+	info.min = ~0u;
+	kallsyms_on_each_symbol(lookup_name, &info);
+	pr_info("kallsyms_lookup_name() looked up %d symbols, average %lld ns\n",
+		info.count, div_u64(info.sum, info.count));
+	pr_info("\tfastest %u ns (%s)\n", info.min, info.min_name);
+	pr_info("\tslowest %u ns (%s)\n", info.max, info.max_name);
+
+	scale = 0;
+	for (idx = 0; idx < HISTOGRAM_BUCKETS; idx++) {
+		if (scale < info.histogram[idx])
+			scale = info.histogram[idx];
+	}
+	row = 8;
+	scale /= row;
+	pr_info("\tDistribution, %uns per column, %u counts per *:\n",
+		HISTOGRAM_RESOLUTION << info.scale, scale);
+	while (row--) {
+		memset(line, ' ', sizeof(line));
+		len = 0;
+		for (idx = 0; idx < HISTOGRAM_BUCKETS; idx++) {
+			if (info.histogram[idx] > row * scale) {
+				len = idx + 1;
+				line[idx] = '*';
+			}
+		}
+		pr_info("\t|%.*s\n", len, line);
+	}
 }
 
 static int find_symbol(void *data, const char *name, unsigned long addr)
@@ -207,7 +292,7 @@ static int find_symbol(void *data, const char *name, unsigned long addr)
 	return 0;
 }
 
-static void test_perf_kallsyms_on_each_symbol(void)
+static noinline_for_stack void test_perf_kallsyms_on_each_symbol(void)
 {
 	u64 t0, t1;
 	struct test_stat stat;
@@ -240,7 +325,7 @@ static int match_symbol(void *data, unsigned long addr)
 	return 0;
 }
 
-static void test_perf_kallsyms_on_each_match_symbol(void)
+static noinline_for_stack void test_perf_kallsyms_on_each_match_symbol(void)
 {
 	u64 t0, t1;
 	struct test_stat stat;
@@ -254,7 +339,7 @@ static void test_perf_kallsyms_on_each_match_symbol(void)
 	pr_info("kallsyms_on_each_match_symbol() traverse all: %lld ns\n", t1 - t0);
 }
 
-static int test_kallsyms_basic_function(void)
+static noinline_for_stack int test_kallsyms_basic_function(void)
 {
 	int i, j, ret;
 	int next = 0, nr_failed = 0;
@@ -425,9 +510,9 @@ static int test_entry(void *p)
 	}
 
 	test_kallsyms_compression_ratio();
-	test_perf_kallsyms_lookup_name();
 	test_perf_kallsyms_on_each_symbol();
 	test_perf_kallsyms_on_each_match_symbol();
+	test_perf_kallsyms_lookup_name();
 	pr_info("finish\n");
 
 	return 0;
-- 
2.39.5

[PATCH v2 next 04/15] kallsyms: scripts/kallsyms: Check for output file write errors

[David Laight]

Exit with an error status if any writes to the output file fail.
The file is big and it might the point where 'disk full' is reached.

Use errx() for all the error exits to simplify the code and ensure
the program name is added.

Signed-off-by: David Laight <david.laight.linux@gmail.com>
---
 scripts/kallsyms.c | 46 +++++++++++++++++++---------------------------
 1 file changed, 19 insertions(+), 27 deletions(-)

diff --git a/scripts/kallsyms.c b/scripts/kallsyms.c
index bda8921c95ef..2e936317fb09 100644
--- a/scripts/kallsyms.c
+++ b/scripts/kallsyms.c
@@ -18,6 +18,7 @@
  *
  */
 
+#include <err.h>
 #include <errno.h>
 #include <getopt.h>
 #include <stdbool.h>
@@ -135,18 +136,16 @@ static struct sym_entry *read_symbol(FILE *in, char **buf, size_t *buf_len)
 
 	addr = strtoull(*buf, &p, 16);
 
-	if (*buf == p || *p++ != ' ' || !isascii((type = *p++)) || *p++ != ' ') {
-		fprintf(stderr, "line format error\n");
-		exit(EXIT_FAILURE);
-	}
+	if (*buf == p || *p++ != ' ' || !isascii((type = *p++)) || *p++ != ' ')
+		errx(1, "line format error");
 
 	name = p;
 	len = strlen(name);
 
 	if (len >= KSYM_NAME_LEN) {
-		fprintf(stderr, "Symbol %s too long for kallsyms (%zu >= %d).\n"
-				"Please increase KSYM_NAME_LEN both in kernel and kallsyms.c\n",
-			name, len, KSYM_NAME_LEN);
+		warnx("Symbol %s too long for kallsyms (%zu >= %d).\n"
+		      "Please increase KSYM_NAME_LEN both in kernel and kallsyms.c",
+		      name, len, KSYM_NAME_LEN);
 		return NULL;
 	}
 
@@ -253,10 +252,8 @@ static void read_map(const char *in)
 	size_t buflen = 0;
 
 	fp = fopen(in, "r");
-	if (!fp) {
-		perror(in);
-		exit(1);
-	}
+	if (!fp)
+		err(1, "failed to open %s", in);
 
 	while (!feof(fp)) {
 		sym = read_symbol(fp, &buf, &buflen);
@@ -362,18 +359,12 @@ static void write_src(void)
 		table[i]->seq = i;
 
 		/* There cannot be any symbol of length zero. */
-		if (table[i]->len == 0) {
-			fprintf(stderr, "kallsyms failure: "
-				"unexpected zero symbol length\n");
-			exit(EXIT_FAILURE);
-		}
+		if (table[i]->len == 0)
+			errx(1, "unexpected zero symbol length");
 
 		/* Only lengths that fit in up-to-two-byte ULEB128 are supported. */
-		if (table[i]->len > 0x3FFF) {
-			fprintf(stderr, "kallsyms failure: "
-				"unexpected huge symbol length\n");
-			exit(EXIT_FAILURE);
-		}
+		if (table[i]->len > 0x3FFF)
+			errx(1, "unexpected huge symbol length");
 
 		/* Encode length with ULEB128. */
 		if (table[i]->len <= 0x7F) {
@@ -431,12 +422,9 @@ static void write_src(void)
 		if (pc_relative) {
 			long long offset = table[i]->addr - _text;
 
-			if (offset < INT_MIN || offset > INT_MAX) {
-				fprintf(stderr, "kallsyms failure: "
-					"relative symbol value %#llx out of range\n",
-					table[i]->addr);
-				exit(EXIT_FAILURE);
-			}
+			if (offset < INT_MIN || offset > INT_MAX)
+				errx(1, "relative symbol value %#llx out of range",
+				     table[i]->addr);
 			printf("\t.long\t_text - . + (%d)\t/* %s */\n",
 			       (int)offset, table[i]->sym);
 		} else {
@@ -456,6 +444,10 @@ static void write_src(void)
 			(unsigned char)(table[i]->seq >> 0),
 		       table[i]->sym);
 	printf("\n");
+
+	fflush(stdout);
+	if (ferror(stdout))
+		errx(1, "error writing to output file");
 }
 
 
-- 
2.39.5

[PATCH v2 next 05/15] kallsyms: Match compressed tokens on the fly during binary search

[David Laight]

From: Jim Cromie <jim.cromie@gmail.com>

kallsyms_lookup_names() runs a binary search across ~184k tokenized
(compressed) symbols.  For each of the ~17 comparisons in the search, it
currently decompresses the candidate symbol into a temporary buffer on
the stack before calling strcmp().

Comparing tokenized symbols directly in compressed space is
impossible.  The BPE token table assigns values by frequency, not
alphabetical order (e.g. token 0x05 might expand to "zebra" while 0x42
expands to "apple"), so comparing raw token values scrambles
lexicographical order.  Even sorting the token table alphabetically
wouldn't help; "bpf_" and "bpf_foo_" do not *have* a determinative
sorting order, because the suffixes following those tokens would
matter.

However, full string expansion at every step is equally wasteful: of
the ~17 strcmps in the binary search, only the last needs to check
all N chars in both strings, earlier steps will know +/- outcome at
char 0,1,2..N-1.

However, full string expansion at every step is equally wasteful: of
the ~17 strcmp()s in the binary search, only the final matching step
needs to test all characters.  Earlier non-matching steps diverge at
the first differing character (0..N-1), but the baseline expands every
candidate symbol to the stack unconditionally, before comparing.

So we introduce kallsyms_strcmp_symbol() to compare ASCII search_name
against tokenized symbols on the fly.  Like strcmp, it tests the
strings char by char, but when it hits a token in the symbol-string,
it continues the char-test against that token-string, which is in
kallsyms_token_table[].  It returns +- on 1st mismatch.

Measured across all ~184k symbols via CONFIG_KALLSYMS_SELFTEST, this
shaves ~530 ns (~14%) off average kallsyms_lookup_name() latency (from
~3810 ns to ~3280 ns on the default 256:1 baseline) and drops the
512-byte namebuf buffer stack-alloc in kallsyms_lookup_names().

Signed-off-by: Jim Cromie <jim.cromie@gmail.com>
Signed-off-by: David Laight <david.laight.linux@gmail.com>
---
 kernel/kallsyms.c | 94 +++++++++++++++++++++++++++++------------------
 1 file changed, 59 insertions(+), 35 deletions(-)

diff --git a/kernel/kallsyms.c b/kernel/kallsyms.c
index aec2f06858af..d18d78e626db 100644
--- a/kernel/kallsyms.c
+++ b/kernel/kallsyms.c
@@ -34,6 +34,21 @@
 
 #include "kallsyms_internal.h"
 
+/*
+ * Get the compressed symbol length and data pointer.
+ */
+static inline const u8 *get_symbol_data(unsigned int off, unsigned int *len)
+{
+	const u8 *p = &kallsyms_names[off];
+	unsigned int l = *p++;
+
+	if (unlikely(l & 0x80))
+		l = (l & 0x7F) | (*p++ << 7);
+	*len = l;
+
+	return p;
+}
+
 /*
  * Expand a compressed symbol data into the resulting uncompressed string,
  * if uncompressed string is too long (>= maxlen), it will be truncated,
@@ -42,28 +57,12 @@
 static unsigned int kallsyms_expand_symbol(unsigned int off,
 					   char *result, size_t maxlen)
 {
-	int len, skipped_first = 0;
+	int skipped_first = 0;
 	const char *tptr;
-	const u8 *data;
+	unsigned int len;
+	const u8 *data = get_symbol_data(off, &len);
 
-	/* Get the compressed symbol length from the first symbol byte. */
-	data = &kallsyms_names[off];
-	len = *data;
-	data++;
-	off++;
-
-	/* If MSB is 1, it is a "big" symbol, so needs an additional byte. */
-	if ((len & 0x80) != 0) {
-		len = (len & 0x7F) | (*data << 7);
-		data++;
-		off++;
-	}
-
-	/*
-	 * Update the offset to return the offset for the next symbol on
-	 * the compressed stream.
-	 */
-	off += len;
+	off = (data - kallsyms_names) + len;
 
 	/*
 	 * For every byte on the compressed symbol data, copy the table
@@ -101,14 +100,43 @@ static unsigned int kallsyms_expand_symbol(unsigned int off,
  */
 static char kallsyms_get_symbol_type(unsigned int off)
 {
-	/*
-	 * Get just the first code, look it up in the token table,
-	 * and return the first char from this token. If MSB of length
-	 * is 1, it is a "big" symbol, so needs an additional byte.
-	 */
-	if (kallsyms_names[off] & 0x80)
-		off++;
-	return kallsyms_token_table[kallsyms_token_index[kallsyms_names[off + 1]]];
+	unsigned int len;
+	const u8 *data = get_symbol_data(off, &len);
+
+	return kallsyms_token_table[kallsyms_token_index[*data]];
+}
+
+/*
+ * Compare an uncompressed ASCII string against a compressed symbol table entry.
+ * Returns negative if name < sym, positive if name > sym, 0 if equal.
+ * Exits immediately on the first mismatched character without decompressing
+ * the rest of the symbol name.
+ */
+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);
+
+	tptr = &kallsyms_token_table[kallsyms_token_index[*data++]] + 1;
+	while (*tptr) {
+		int diff = (unsigned char)*name++ - (unsigned char)*tptr++;
+
+		if (diff)
+			return diff;
+	}
+
+	while (--len) {
+		tptr = &kallsyms_token_table[kallsyms_token_index[*data++]];
+		do {
+			int diff = (unsigned char)*name++ - (unsigned char)*tptr++;
+
+			if (diff)
+				return diff;
+		} while (*tptr);
+	}
+
+	return (unsigned char)*name;
 }
 
 
@@ -174,7 +202,6 @@ static int kallsyms_lookup_names(const char *name,
 	int ret;
 	int low, mid, high;
 	unsigned int seq, off;
-	char namebuf[KSYM_NAME_LEN];
 
 	low = 0;
 	high = kallsyms_num_syms - 1;
@@ -183,8 +210,7 @@ static int kallsyms_lookup_names(const char *name,
 		mid = low + (high - low) / 2;
 		seq = get_symbol_seq(mid);
 		off = get_symbol_offset(seq);
-		kallsyms_expand_symbol(off, namebuf, ARRAY_SIZE(namebuf));
-		ret = strcmp(name, namebuf);
+		ret = kallsyms_strcmp_symbol(off, name);
 		if (ret > 0)
 			low = mid + 1;
 		else if (ret < 0)
@@ -200,8 +226,7 @@ static int kallsyms_lookup_names(const char *name,
 	while (low) {
 		seq = get_symbol_seq(low - 1);
 		off = get_symbol_offset(seq);
-		kallsyms_expand_symbol(off, namebuf, ARRAY_SIZE(namebuf));
-		if (strcmp(name, namebuf))
+		if (kallsyms_strcmp_symbol(off, name) != 0)
 			break;
 		low--;
 	}
@@ -212,8 +237,7 @@ static int kallsyms_lookup_names(const char *name,
 		while (high < kallsyms_num_syms - 1) {
 			seq = get_symbol_seq(high + 1);
 			off = get_symbol_offset(seq);
-			kallsyms_expand_symbol(off, namebuf, ARRAY_SIZE(namebuf));
-			if (strcmp(name, namebuf))
+			if (kallsyms_strcmp_symbol(off, name) != 0)
 				break;
 			high++;
 		}
-- 
2.39.5

[PATCH v2 next 06/15] kallsyms: Optimise symbol name search

[David Laight]

Change the alphabetically ordered lookup table (kallsyms_seqs_of_names)
with one that indexed the table of compressed names rather than the
array of symbol values.
This removes all the linear scans during the binary search for the symbol
name.
Once the name has been found a second binary search of the 'markers' array
followed by a linear scan for the symbols address gives the symbol value.

This linear scan is done once for each address returned, whereas the old
code did the scan for each of the ~17 comparisons in the binary search
(and the binary search is done at least two times for a symbol that appears
once).

For normal kernels the index table stays at 24 bits per symbol (now host
ordered), but a 32 bit table is used if necessary (probably only for
allyesconfig builds - which needs 25 bits on x86-64).

Speeds up lookup by name by a factor of about 12.

Build for BE kernels correctly flips the byte order in the index table.

Signed-off-by: David Laight <david.laight.linux@gmail.com>
---

Changes for v2 (previously patch 2):
- Fixed the upper bound in get_name_address() so there isn't a long
  linear scan for items near the upper limit.
- The table entry size (24/32 bits) is read from a (constant) variable
  to avoid relying on detecting undefined 'weak' symbols.
- A static branch is used to select between the two table sizes.
  This needs to be initialised very early (really just after the other
  code patching) and non of the initcall lists seem to be early enough,
  so I've initialised it on the first call using DO_ONCE_LITE().
  The overhead of that shouldn't be measurable.

 kernel/kallsyms.c          | 86 ++++++++++++++++++++++++++++----------
 kernel/kallsyms_internal.h |  5 ++-
 scripts/Makefile           |  1 +
 scripts/kallsyms.c         | 56 ++++++++++++++-----------
 4 files changed, 99 insertions(+), 49 deletions(-)

diff --git a/kernel/kallsyms.c b/kernel/kallsyms.c
index d18d78e626db..31451feac822 100644
--- a/kernel/kallsyms.c
+++ b/kernel/kallsyms.c
@@ -25,6 +25,7 @@
 #include <linux/filter.h>
 #include <linux/ftrace.h>
 #include <linux/kprobes.h>
+#include <linux/once_lite.h>
 #include <linux/build_bug.h>
 #include <linux/compiler.h>
 #include <linux/module.h>
@@ -177,6 +178,36 @@ static unsigned int get_symbol_offset(unsigned long pos)
 	return name - kallsyms_names;
 }
 
+/*
+ * Find the value of a symbol given the offset in the compressed stream.
+ */
+static unsigned long get_name_address(unsigned int name_offset)
+{
+	unsigned int low, pos, high;
+
+	low = 0;
+	high = ((kallsyms_num_syms - 1) >> 8) + 1;
+
+	while (high - low > 1) {
+		pos = low + (high - low) / 2;
+		if (name_offset >= kallsyms_markers[pos])
+			low = pos;
+		else
+			high = pos;
+	}
+
+	pos = kallsyms_markers[low];
+	for (low <<= 8; pos < name_offset; low++) {
+		unsigned int len = kallsyms_names[pos];
+		if (len & 0x80)
+			len += (kallsyms_names[pos + 1] << 7) - 0x7f;
+		pos += 1 + len;
+	}
+
+	return kallsyms_sym_address(low);
+}
+
+
 unsigned long kallsyms_sym_address(int idx)
 {
 	/* non-relocatable 32-bit kernels just embed the value directly */
@@ -185,14 +216,19 @@ unsigned long kallsyms_sym_address(int idx)
 	return (unsigned long)offset_to_ptr(kallsyms_offsets + idx);
 }
 
-static unsigned int get_symbol_seq(int index)
-{
-	unsigned int i, seq = 0;
+static DEFINE_STATIC_KEY_TRUE(kallsyms_off_size_24);
 
-	for (i = 0; i < 3; i++)
-		seq = (seq << 8) | kallsyms_seqs_of_names[3 * index + i];
+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 seq;
+static void set_kallsyms_off_size(void)
+{
+	if (kallsyms_off_size != 24)
+		static_branch_disable(&kallsyms_off_size_24);
 }
 
 static int kallsyms_lookup_names(const char *name,
@@ -201,15 +237,16 @@ static int kallsyms_lookup_names(const char *name,
 {
 	int ret;
 	int low, mid, high;
-	unsigned int seq, off;
+	unsigned int off;
+
+	DO_ONCE_LITE(set_kallsyms_off_size);
 
 	low = 0;
 	high = kallsyms_num_syms - 1;
 
 	while (low <= high) {
 		mid = low + (high - low) / 2;
-		seq = get_symbol_seq(mid);
-		off = get_symbol_offset(seq);
+		off = get_symbol_name_offset(mid);
 		ret = kallsyms_strcmp_symbol(off, name);
 		if (ret > 0)
 			low = mid + 1;
@@ -220,23 +257,24 @@ static int kallsyms_lookup_names(const char *name,
 	}
 
 	if (low > high)
-		return -ESRCH;
+		return -1;
+
+	ret = off;
 
 	low = mid;
 	while (low) {
-		seq = get_symbol_seq(low - 1);
-		off = get_symbol_offset(seq);
+		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) {
-			seq = get_symbol_seq(high + 1);
-			off = get_symbol_offset(seq);
+			off = get_symbol_name_offset(high + 1);
 			if (kallsyms_strcmp_symbol(off, name) != 0)
 				break;
 			high++;
@@ -244,7 +282,7 @@ static int kallsyms_lookup_names(const char *name,
 		*end = high;
 	}
 
-	return 0;
+	return ret;
 }
 
 /* Lookup the address for this symbol. Returns 0 if not found. */
@@ -258,8 +296,8 @@ unsigned long kallsyms_lookup_name(const char *name)
 		return 0;
 
 	ret = kallsyms_lookup_names(name, &i, NULL);
-	if (!ret)
-		return kallsyms_sym_address(get_symbol_seq(i));
+	if (ret >= 0)
+		return get_name_address(ret);
 
 	return module_kallsyms_lookup_name(name);
 }
@@ -289,15 +327,17 @@ int kallsyms_on_each_symbol(int (*fn)(void *, const char *, unsigned long),
 int kallsyms_on_each_match_symbol(int (*fn)(void *, unsigned long),
 				  const char *name, void *data)
 {
-	int ret;
-	unsigned int i, start, end;
+	int name_offset, ret;
+	unsigned int sym_number, last;
 
-	ret = kallsyms_lookup_names(name, &start, &end);
-	if (ret)
+	name_offset = kallsyms_lookup_names(name, &sym_number, &last);
+	if (name_offset < 0)
 		return 0;
 
-	for (i = start; !ret && i <= end; i++) {
-		ret = fn(data, kallsyms_sym_address(get_symbol_seq(i)));
+	for (;; name_offset = get_symbol_name_offset(sym_number)) {
+		ret = fn(data, get_name_address(name_offset));
+		if (ret || ++sym_number > last)
+			break;
 		cond_resched();
 	}
 
diff --git a/kernel/kallsyms_internal.h b/kernel/kallsyms_internal.h
index 81a867dbe57d..ec6eca5654e6 100644
--- a/kernel/kallsyms_internal.h
+++ b/kernel/kallsyms_internal.h
@@ -13,6 +13,9 @@ extern const char kallsyms_token_table[];
 extern const u16 kallsyms_token_index[];
 
 extern const unsigned int kallsyms_markers[];
-extern const u8 kallsyms_seqs_of_names[];
+
+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;
 
 #endif // LINUX_KALLSYMS_INTERNAL_H_
diff --git a/scripts/Makefile b/scripts/Makefile
index 3434a82a119f..b481c2b291bb 100644
--- a/scripts/Makefile
+++ b/scripts/Makefile
@@ -29,6 +29,7 @@ generate_rust_target-rust := y
 rustdoc_test_builder-rust := y
 rustdoc_test_gen-rust := y
 
+HOSTCFLAGS_kallsyms.o += $(if $(CONFIG_CPU_BIG_ENDIAN),-DCONFIG_CPU_BIG_ENDIAN)
 HOSTCFLAGS_tracepoint-update.o = -I$(srctree)/tools/include
 HOSTCFLAGS_elf-parse.o = -I$(srctree)/tools/include
 HOSTCFLAGS_sorttable.o = -I$(srctree)/tools/include
diff --git a/scripts/kallsyms.c b/scripts/kallsyms.c
index 2e936317fb09..a02fa17428d3 100644
--- a/scripts/kallsyms.c
+++ b/scripts/kallsyms.c
@@ -281,6 +281,14 @@ static void output_label(const char *label)
 	printf("%s:\n", label);
 }
 
+static void output_value(const char *label, unsigned int value)
+{
+	output_label(label);
+	printf("\t.long\t%u\n", value);
+	printf(".size %s, 4\n", label);
+	printf("\n");
+}
+
 /* uncompress a compressed symbol. When this function is called, the best table
  * might still be compressed itself, so the function needs to be recursive */
 static int expand_symbol(const unsigned char *data, int len, char *result)
@@ -335,28 +343,18 @@ static void sort_symbols_by_name(void)
 
 static void write_src(void)
 {
-	unsigned int i, k, off;
+	unsigned int i, k, off, off_size, table_size;
 	unsigned int best_idx[256];
-	unsigned int *markers, markers_cnt;
 	char buf[1 + KSYM_NAME_LEN];
 
 	printf("\t.section .rodata, \"a\"\n");
 
-	output_label("kallsyms_num_syms");
-	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_value("kallsyms_num_syms", table_cnt);
 
 	output_label("kallsyms_names");
 	off = 0;
 	for (i = 0; i < table_cnt; i++) {
-		if ((i & 0xFF) == 0)
-			markers[i >> 8] = off;
-		table[i]->seq = i;
+		table[i]->seq = off;
 
 		/* There cannot be any symbol of length zero. */
 		if (table[i]->len == 0)
@@ -389,17 +387,16 @@ static void write_src(void)
 		strcpy((char *)table[i]->sym, buf);
 		printf("\t/* %s */\n", table[i]->sym);
 	}
+	table_size = off;
 	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]);
+	for (i = 0; i < table_cnt; i += 256)
+		printf("\t.long\t%u\n", table[i]->seq);
 	printf(".size kallsyms_markers, . - kallsyms_markers\n");
 	printf("\n");
 
-	free(markers);
-
 	output_label("kallsyms_token_table");
 	off = 0;
 	for (i = 0; i < 256; i++) {
@@ -436,14 +433,23 @@ static void write_src(void)
 	printf("\n");
 
 	sort_symbols_by_name();
-	output_label("kallsyms_seqs_of_names");
-	for (i = 0; i < table_cnt; i++)
-		printf("\t.byte 0x%02x, 0x%02x, 0x%02x\t/* %s */\n",
-			(unsigned char)(table[i]->seq >> 16),
-			(unsigned char)(table[i]->seq >> 8),
-			(unsigned char)(table[i]->seq >> 0),
-		       table[i]->sym);
-	printf("\n");
+	off_size = table_size < (1u << 24) ? 24 : 32;
+	output_value("kallsyms_off_size", off_size);
+	output_label(off_size == 24 ? "kallsyms_off24_of_names" : "kallsyms_off32_of_names");
+	for (i = 0; i < table_cnt; i++) {
+		off = table[i]->seq;
+		if (off_size == 24) {
+#ifdef CONFIG_CPU_BIG_ENDIAN
+			off = __builtin_bswap32(off) >> 8;
+#endif
+			printf("\t.byte\t0x%02x, 0x%02x, 0x%02x\t/* %s */\n",
+				off & 0xff, (off >> 8) & 0xff, off >> 16,
+			       table[i]->sym);
+		} else {
+			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);
 
 	fflush(stdout);
 	if (ferror(stdout))
-- 
2.39.5

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

[David Laight]

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

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

[David Laight]

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

[PATCH v2 next 09/15] kallsyms: Add a kernel parameter for the marker shift

[David Laight]

Set the default to 6 (one marker every 64 symbols).
Improves symbol lookup by name by about 35% (over an interval of 256).
Net improvement for the patch series is about 18 times.

Static data increases by a little less than 1 bit for every 2 symbols.

Signed-off-by: David Laight <david.laight.linux@gmail.com>
---
 init/Kconfig            | 19 +++++++++++++++++++
 scripts/link-vmlinux.sh |  6 ++++++
 2 files changed, 25 insertions(+)

diff --git a/init/Kconfig b/init/Kconfig
index 8583d9f06c52..2d0716662c67 100644
--- a/init/Kconfig
+++ b/init/Kconfig
@@ -2101,6 +2101,25 @@ config KALLSYMS
 	  symbolic stack backtraces. This increases the size of the kernel
 	  somewhat, as all symbols have to be loaded into the kernel image.
 
+config KALLSYMS_MARKER_SHIFT
+	int "Interval between kallsyms markers (6 => 64, 8 => 256)"
+	depends on KALLSYMS
+	default 6
+	range 0 24
+	help
+	  Set the interval between the kallsyms marker entries as a power of 2.
+
+	  This bounds the linear search when locating the name of a symbol
+	  from its index in the array of values (and v.v.).
+
+	  Smaller values speed up the search but increase the memory footprint.
+	  Values below 5 (one 32 bit marker every 32 symbols) are unlikely to
+	  make a significant difference because other parts of the code
+	  dominate.
+
+	  The default of 6 is a reasonable compromise. It makes looking up a
+	  symbol by name around 35% faster than setting it to 8.
+
 config KALLSYMS_SELFTEST
 	bool "Test the basic functions and performance of kallsyms"
 	depends on KALLSYMS
diff --git a/scripts/link-vmlinux.sh b/scripts/link-vmlinux.sh
index ab0b8125c8cb..12b119d024b4 100755
--- a/scripts/link-vmlinux.sh
+++ b/scripts/link-vmlinux.sh
@@ -37,6 +37,10 @@ is_enabled() {
 	grep -q "^$1=y" include/config/auto.conf
 }
 
+value() {
+	sed -n "/^$1=/{s///;p;q}" include/config/auto.conf
+}
+
 # Nice output in kbuild format
 # Will be suppressed by "make -s"
 info()
@@ -131,6 +135,8 @@ kallsyms()
 		kallsymopt="${kallsymopt} --pc-relative"
 	fi
 
+	kallsymopt="${kallsymopt} --marker-shift=$(value CONFIG_KALLSYMS_MARKER_SHIFT)"
+
 	info KSYMS "${2}.S"
 	scripts/kallsyms ${kallsymopt} "${1}" > "${2}.S"
 
-- 
2.39.5

[PATCH v2 next 10/15] kallsyms: scripts/kallsyms: Rename some variables for clarity

[David Laight]

Rename the array that holds the symbol table from table[] to symbol[].
The typical use is then symbol[i] - giving the data for the i'th symbol.
Rename table_size to symbol_table_size and table_cnt to symbol_cnt to match.
Save repetetive code by using struct sym_entry *se = symbol[i] in loops.
(That might make the code better because it saves reloading the pointers,
or make it worse because it causes a spill to stack.)

Add a comment block explaining token_profit[] (it used to have a short
comment when it was the 'profit' field of a struct) and add defines
LEFT(), RIGHT() and PAIR() for converting token pairs to/from indexes.

Put the two arrays that contain info about the tokens used the
compressed data into an 'array of struct'.
This should give better d-cache locality.
No idea why they were called best_table[] - the search gives the
'best token' but the value is a 'token' not a 'best'.
(You can't use 'symbol' for the compression output because the code
is compressing a symbol table.)

No logic changes and the output file is unchanged.

Signed-off-by: David Laight <david.laight.linux@gmail.com>
---
 scripts/kallsyms.c | 154 ++++++++++++++++++++++++---------------------
 1 file changed, 83 insertions(+), 71 deletions(-)

diff --git a/scripts/kallsyms.c b/scripts/kallsyms.c
index d2d3ac8c33a1..5603b2a6c77b 100644
--- a/scripts/kallsyms.c
+++ b/scripts/kallsyms.c
@@ -54,19 +54,29 @@ static struct addr_range text_ranges[] = {
 #define text_range_text     (&text_ranges[0])
 #define text_range_inittext (&text_ranges[1])
 
-static struct sym_entry **table;
-static unsigned int table_size, table_cnt;
+static struct sym_entry **symbol;
+static unsigned int symbol_table_size, symbol_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;
 
+/*
+ * token_profit[PAIR(left, right)] is the number of times the characters
+ * left and right appear adjacent (in that order) and is usually the same
+ * as the number of bytes saved (the profit) by replacing the pair with
+ * a single byte token.
+ */
+#define LEFT(pair) ((pair) & 0xff)
+#define RIGHT(pair) ((pair) >> 8)
+#define PAIR(left, right) ((left) | (right) << 8)
 static int token_profit[0x10000];
 
 /* the table that holds the result of the compression */
-static unsigned char best_table[256][2];
-static unsigned char best_table_len[256];
-
+static struct token_table {
+	unsigned short len;
+	unsigned char  ch[2];
+} token_table[256];
 
 static void usage(void)
 {
@@ -234,16 +244,16 @@ static void shrink_table(void)
 	unsigned int i, pos;
 
 	pos = 0;
-	for (i = 0; i < table_cnt; i++) {
-		if (symbol_valid(table[i])) {
+	for (i = 0; i < symbol_cnt; i++) {
+		if (symbol_valid(symbol[i])) {
 			if (pos != i)
-				table[pos] = table[i];
+				symbol[pos] = symbol[i];
 			pos++;
 		} else {
-			free(table[i]);
+			free(symbol[i]);
 		}
 	}
-	table_cnt = pos;
+	symbol_cnt = pos;
 }
 
 static void read_map(const char *in)
@@ -262,14 +272,14 @@ static void read_map(const char *in)
 		if (!sym)
 			continue;
 
-		sym->seq = table_cnt;
+		sym->seq = symbol_cnt;
 
-		if (table_cnt >= table_size) {
-			table_size += 10000;
-			table = xrealloc(table, sizeof(*table) * table_size);
+		if (symbol_cnt >= symbol_table_size) {
+			symbol_table_size += 10000;
+			symbol = xrealloc(symbol, sizeof(*symbol) * symbol_table_size);
 		}
 
-		table[table_cnt++] = sym;
+		symbol[symbol_cnt++] = sym;
 	}
 
 	free(buf);
@@ -301,12 +311,12 @@ static int expand_symbol(const unsigned char *data, int len, char *result)
 		c = *data;
 		/* if the table holds a single char that is the same as the one
 		 * we are looking for, then end the search */
-		if (best_table[c][0]==c && best_table_len[c]==1) {
+		if (token_table[c].ch[0] == c && token_table[c].len == 1) {
 			*result++ = c;
 			total++;
 		} else {
 			/* if not, recurse and expand */
-			rlen = expand_symbol(best_table[c], best_table_len[c], result);
+			rlen = expand_symbol(token_table[c].ch, token_table[c].len, result);
 			total += rlen;
 			result += rlen;
 		}
@@ -340,7 +350,7 @@ static int compare_names(const void *a, const void *b)
 
 static void sort_symbols_by_name(void)
 {
-	qsort(table, table_cnt, sizeof(table[0]), compare_names);
+	qsort(symbol, symbol_cnt, sizeof(symbol[0]), compare_names);
 }
 
 static void write_src(void)
@@ -348,46 +358,47 @@ static void write_src(void)
 	unsigned int i, k, off, off_size, table_size;
 	unsigned int best_idx[256];
 	char buf[1 + KSYM_NAME_LEN];
+	struct sym_entry *se;
 
 	printf("\t.section .rodata, \"a\"\n");
 
-	output_value("kallsyms_num_syms", table_cnt);
+	output_value("kallsyms_num_syms", symbol_cnt);
 
 	output_label("kallsyms_names");
 	off = 0;
-	for (i = 0; i < table_cnt; i++) {
-		table[i]->seq = off;
+	for (i = 0; i < symbol_cnt; i++) {
+		se = symbol[i];
+		se->seq = off;
 
 		/* There cannot be any symbol of length zero. */
-		if (table[i]->len == 0)
+		if (se->len == 0)
 			errx(1, "unexpected zero symbol length");
 
 		/* Only lengths that fit in up-to-two-byte ULEB128 are supported. */
-		if (table[i]->len > 0x3FFF)
+		if (se->len > 0x3FFF)
 			errx(1, "unexpected huge symbol length");
 
 		/* Encode length with ULEB128. */
-		if (table[i]->len <= 0x7F) {
+		if (se->len <= 0x7F) {
 			/* Most symbols use a single byte for the length. */
-			printf("\t.byte 0x%02x", table[i]->len);
-			off += table[i]->len + 1;
+			printf("\t.byte 0x%02x", se->len);
+			off += se->len + 1;
 		} else {
 			/* "Big" symbols use two bytes. */
 			printf("\t.byte 0x%02x, 0x%02x",
-				(table[i]->len & 0x7F) | 0x80,
-				(table[i]->len >> 7) & 0x7F);
-			off += table[i]->len + 2;
+				(se->len & 0x7F) | 0x80, (se->len >> 7) & 0x7F);
+			off += se->len + 2;
 		}
-		for (k = 0; k < table[i]->len; k++)
-			printf(", 0x%02x", table[i]->sym[k]);
+		for (k = 0; k < se->len; k++)
+			printf(", 0x%02x", se->sym[k]);
 
 		/*
 		 * Now that we wrote out the compressed symbol name, restore the
 		 * original name and print it in the comment.
 		 */
-		expand_symbol(table[i]->sym, table[i]->len, buf);
-		strcpy((char *)table[i]->sym, buf);
-		printf("\t/* %s */\n", table[i]->sym);
+		expand_symbol(se->sym, se->len, buf);
+		strcpy((char *)se->sym, buf);
+		printf("\t/* %s */\n", se->sym);
 	}
 	table_size = off;
 	printf(".size kallsyms_names, . - kallsyms_names\n");
@@ -395,8 +406,8 @@ static void write_src(void)
 
 	output_value("kallsyms_marker_shift", marker_shift);
 	output_label("kallsyms_markers");
-	for (i = 0; i < table_cnt; i += 1u << marker_shift)
-		printf("\t.long\t%u\n", table[i]->seq);
+	for (i = 0; i < symbol_cnt; i += 1u << marker_shift)
+		printf("\t.long\t%u\n", symbol[i]->seq);
 	printf(".size kallsyms_markers, . - kallsyms_markers\n");
 	printf("\n");
 
@@ -404,7 +415,7 @@ static void write_src(void)
 	off = 0;
 	for (i = 0; i < 256; i++) {
 		best_idx[i] = off;
-		expand_symbol(best_table[i], best_table_len[i], buf);
+		expand_symbol(token_table[i].ch, token_table[i].len, buf);
 		printf("\t.asciz\t\"%s\"\n", buf);
 		off += strlen(buf) + 1;
 	}
@@ -418,18 +429,19 @@ static void write_src(void)
 
 	output_label("kallsyms_offsets");
 
-	for (i = 0; i < table_cnt; i++) {
+	for (i = 0; i < symbol_cnt; i++) {
+		se = symbol[i];
 		if (pc_relative) {
-			long long offset = table[i]->addr - _text;
+			long long offset = se->addr - _text;
 
 			if (offset < INT_MIN || offset > INT_MAX)
 				errx(1, "relative symbol value %#llx out of range",
-				     table[i]->addr);
+				     se->addr);
 			printf("\t.long\t_text - . + (%d)\t/* %s */\n",
-			       (int)offset, table[i]->sym);
+			       (int)offset, se->sym);
 		} else {
 			printf("\t.long\t%#x\t/* %s */\n",
-			       (unsigned int)table[i]->addr, table[i]->sym);
+			       (unsigned int)se->addr, se->sym);
 		}
 	}
 	printf(".size kallsyms_offsets, . - kallsyms_offsets\n");
@@ -439,9 +451,10 @@ static void write_src(void)
 	off_size = table_size < (1u << 23) ? 24 : 32;
 	output_value("kallsyms_off_size", off_size);
 	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 << 1;
-		if (i && !strcmp((char *)table[i - 1]->sym + 1, (char *)table[i]->sym + 1))
+	for (i = 0; i < symbol_cnt; i++) {
+		se = symbol[i];
+		off = se->seq << 1;
+		if (i && !strcmp((char *)symbol[i - 1]->sym + 1, (char *)se->sym + 1))
 			/* Mark that this is a duplicate of the previous symbol */
 			off |= 1;
 		if (off_size == 24) {
@@ -449,10 +462,9 @@ static void write_src(void)
 			off = __builtin_bswap32(off) >> 8;
 #endif
 			printf("\t.byte\t0x%02x, 0x%02x, 0x%02x\t/* %s */\n",
-				off & 0xff, (off >> 8) & 0xff, off >> 16,
-			       table[i]->sym);
+				off & 0xff, (off >> 8) & 0xff, off >> 16, se->sym);
 		} else {
-			printf("\t.long\t%#04x\t/* %s */\n", off, table[i]->sym);
+			printf("\t.long\t%#04x\t/* %s */\n", off, se->sym);
 		}
 	}
 	/* Terminator without the 'duplicate' flag. */
@@ -471,21 +483,21 @@ static void write_src(void)
 /* table lookup compression functions */
 
 /* count all the possible tokens in a symbol */
-static void learn_symbol(const unsigned char *symbol, int len)
+static void learn_symbol(const unsigned char *sym, int len)
 {
 	int i;
 
 	for (i = 0; i < len - 1; i++)
-		token_profit[ symbol[i] + (symbol[i + 1] << 8) ]++;
+		token_profit[PAIR(sym[i], sym[i + 1])]++;
 }
 
 /* decrease the count for all the possible tokens in a symbol */
-static void forget_symbol(const unsigned char *symbol, int len)
+static void forget_symbol(const unsigned char *sym, int len)
 {
 	int i;
 
 	for (i = 0; i < len - 1; i++)
-		token_profit[ symbol[i] + (symbol[i + 1] << 8) ]--;
+		token_profit[PAIR(sym[i], sym[i + 1])]--;
 }
 
 /* do the initial token count */
@@ -493,8 +505,8 @@ static void build_initial_token_table(void)
 {
 	unsigned int i;
 
-	for (i = 0; i < table_cnt; i++)
-		learn_symbol(table[i]->sym, table[i]->len);
+	for (i = 0; i < symbol_cnt; i++)
+		learn_symbol(symbol[i]->sym, symbol[i]->len);
 }
 
 static unsigned char *find_token(unsigned char *str, int len,
@@ -516,17 +528,17 @@ static void compress_symbols(const unsigned char *str, int idx)
 	unsigned int i, len, size;
 	unsigned char *p1, *p2;
 
-	for (i = 0; i < table_cnt; i++) {
+	for (i = 0; i < symbol_cnt; i++) {
 
-		len = table[i]->len;
-		p1 = table[i]->sym;
+		len = symbol[i]->len;
+		p1 = symbol[i]->sym;
 
 		/* find the token on the symbol */
 		p2 = find_token(p1, len, str);
 		if (!p2) continue;
 
 		/* decrease the counts for this symbol's tokens */
-		forget_symbol(table[i]->sym, len);
+		forget_symbol(symbol[i]->sym, len);
 
 		size = len;
 
@@ -545,10 +557,10 @@ static void compress_symbols(const unsigned char *str, int idx)
 
 		} while (p2);
 
-		table[i]->len = len;
+		symbol[i]->len = len;
 
 		/* increase the counts for this symbol's new tokens */
-		learn_symbol(table[i]->sym, len);
+		learn_symbol(symbol[i]->sym, len);
 	}
 }
 
@@ -580,7 +592,7 @@ static void optimize_result(void)
 
 		/* if this table slot is empty (it is not used by an actual
 		 * original char code */
-		if (!best_table_len[i]) {
+		if (!token_table[i].len) {
 
 			/* find the token with the best profit value */
 			best = find_best_token();
@@ -588,12 +600,12 @@ static void optimize_result(void)
 				break;
 
 			/* place it in the "best" table */
-			best_table_len[i] = 2;
-			best_table[i][0] = best & 0xFF;
-			best_table[i][1] = (best >> 8) & 0xFF;
+			token_table[i].len = 2;
+			token_table[i].ch[0] = LEFT(best);
+			token_table[i].ch[1] = RIGHT(best);
 
 			/* replace this token in all the valid symbols */
-			compress_symbols(best_table[i], i);
+			compress_symbols(token_table[i].ch, i);
 		}
 	}
 }
@@ -603,11 +615,11 @@ static void insert_real_symbols_in_table(void)
 {
 	unsigned int i, j, c;
 
-	for (i = 0; i < table_cnt; i++) {
-		for (j = 0; j < table[i]->len; j++) {
-			c = table[i]->sym[j];
-			best_table[c][0]=c;
-			best_table_len[c]=1;
+	for (i = 0; i < symbol_cnt; i++) {
+		for (j = 0; j < symbol[i]->len; j++) {
+			c = symbol[i]->sym[j];
+			token_table[c].ch[0] = c;
+			token_table[c].len = 1;
 		}
 	}
 }
@@ -692,7 +704,7 @@ static int compare_symbols(const void *a, const void *b)
 
 static void sort_symbols(void)
 {
-	qsort(table, table_cnt, sizeof(table[0]), compare_symbols);
+	qsort(symbol, symbol_cnt, sizeof(symbol[0]), compare_symbols);
 }
 
 int main(int argc, char **argv)
-- 
2.39.5

[PATCH v2 next 11/15] kallsyms: scripts/kallsyms: Keep full expansion of tokens

[David Laight]

Expand the full string when a new token is allocated.
Saves the recursive expansions later on.
It probably means that token 0 could be used earlier, but the reverse
order is maintained so that the output files can be compared.

The entries for the initial tokens [0-9A-Za-z_.] are now no different
and don't need special casing.

No change to generated output.

Signed-off-by: David Laight <david.laight.linux@gmail.com>
---
 scripts/kallsyms.c | 117 +++++++++++++++++++++++----------------------
 1 file changed, 60 insertions(+), 57 deletions(-)

diff --git a/scripts/kallsyms.c b/scripts/kallsyms.c
index 5603b2a6c77b..9e1bc0fdaa9f 100644
--- a/scripts/kallsyms.c
+++ b/scripts/kallsyms.c
@@ -74,8 +74,8 @@ static int token_profit[0x10000];
 
 /* the table that holds the result of the compression */
 static struct token_table {
-	unsigned short len;
-	unsigned char  ch[2];
+	char           *str;		/* Full expansion, '\0' terminated */
+	unsigned short len;		/* Length of str */
 } token_table[256];
 
 static void usage(void)
@@ -301,29 +301,17 @@ static void output_value(const char *label, unsigned int value)
 	printf("\n");
 }
 
-/* uncompress a compressed symbol. When this function is called, the best table
- * might still be compressed itself, so the function needs to be recursive */
-static int expand_symbol(const unsigned char *data, int len, char *result)
+static unsigned int expand_symbol(const unsigned char *data, int len, char *result)
 {
-	int c, rlen, total=0;
-
-	while (len) {
-		c = *data;
-		/* if the table holds a single char that is the same as the one
-		 * we are looking for, then end the search */
-		if (token_table[c].ch[0] == c && token_table[c].len == 1) {
-			*result++ = c;
-			total++;
-		} else {
-			/* if not, recurse and expand */
-			rlen = expand_symbol(token_table[c].ch, token_table[c].len, result);
-			total += rlen;
-			result += rlen;
-		}
-		data++;
-		len--;
+	struct token_table *tt;
+	unsigned int total = 0;
+
+	while (len--) {
+		tt = token_table + *data++;
+		memcpy(result + total, tt->str, tt->len);
+		total += tt->len;
 	}
-	*result=0;
+	result[total] = 0;
 
 	return total;
 }
@@ -396,8 +384,8 @@ static void write_src(void)
 		 * Now that we wrote out the compressed symbol name, restore the
 		 * original name and print it in the comment.
 		 */
-		expand_symbol(se->sym, se->len, buf);
-		strcpy((char *)se->sym, buf);
+		se->len = expand_symbol(se->sym, se->len, buf);
+		memcpy(se->sym, buf, se->len + 1);
 		printf("\t/* %s */\n", se->sym);
 	}
 	table_size = off;
@@ -415,9 +403,8 @@ static void write_src(void)
 	off = 0;
 	for (i = 0; i < 256; i++) {
 		best_idx[i] = off;
-		expand_symbol(token_table[i].ch, token_table[i].len, buf);
-		printf("\t.asciz\t\"%s\"\n", buf);
-		off += strlen(buf) + 1;
+		off += token_table[i].len + 1;
+		printf("\t.asciz\t\"%s\"\n", token_table[i].str);
 	}
 	printf(".size kallsyms_token_table, . - kallsyms_token_table\n");
 	printf("\n");
@@ -454,7 +441,8 @@ static void write_src(void)
 	for (i = 0; i < symbol_cnt; i++) {
 		se = symbol[i];
 		off = se->seq << 1;
-		if (i && !strcmp((char *)symbol[i - 1]->sym + 1, (char *)se->sym + 1))
+		if (i && symbol[i - 1]->len == se->len &&
+		    !memcmp(symbol[i - 1]->sym + 1, se->sym + 1, se->len - 1))
 			/* Mark that this is a duplicate of the previous symbol */
 			off |= 1;
 		if (off_size == 24) {
@@ -510,20 +498,22 @@ static void build_initial_token_table(void)
 }
 
 static unsigned char *find_token(unsigned char *str, int len,
-				 const unsigned char *token)
+				 unsigned int want)
 {
+	unsigned int token = PAIR(0, *str++);
 	int i;
 
 	for (i = 0; i < len - 1; i++) {
-		if (str[i] == token[0] && str[i+1] == token[1])
-			return &str[i];
+		token = PAIR(RIGHT(token), *str++);
+		if (token == want)
+			return str - 2;
 	}
 	return NULL;
 }
 
 /* replace a given token in all the valid symbols. Use the sampled symbols
  * to update the counts */
-static void compress_symbols(const unsigned char *str, int idx)
+static void compress_symbols(unsigned int token_pair, int idx)
 {
 	unsigned int i, len, size;
 	unsigned char *p1, *p2;
@@ -534,7 +524,7 @@ static void compress_symbols(const unsigned char *str, int idx)
 		p1 = symbol[i]->sym;
 
 		/* find the token on the symbol */
-		p2 = find_token(p1, len, str);
+		p2 = find_token(p1, len, token_pair);
 		if (!p2) continue;
 
 		/* decrease the counts for this symbol's tokens */
@@ -553,7 +543,7 @@ static void compress_symbols(const unsigned char *str, int idx)
 			if (size < 2) break;
 
 			/* find the token on the symbol */
-			p2 = find_token(p1, size, str);
+			p2 = find_token(p1, size, token_pair);
 
 		} while (p2);
 
@@ -569,8 +559,8 @@ static int find_best_token(void)
 {
 	int i, best, bestprofit;
 
-	bestprofit=-10000;
-	best = 0;
+	bestprofit = 0;
+	best = -1;
 
 	for (i = 0; i < 0x10000; i++) {
 		if (token_profit[i] > bestprofit) {
@@ -585,43 +575,56 @@ static int find_best_token(void)
 static void optimize_result(void)
 {
 	int i, best;
+	unsigned int len;
+	struct token_table *left, *right;
+	char *str;
 
-	/* using the '\0' symbol last allows compress_symbols to use standard
-	 * fast string functions */
+	/* Use the '\0' symbol last so the output is unchanged */
 	for (i = 255; i >= 0; i--) {
+		/* Ignore tokens used for the original character codes. */
+		if (token_table[i].len)
+			continue;
 
-		/* if this table slot is empty (it is not used by an actual
-		 * original char code */
-		if (!token_table[i].len) {
+		/* find the token pair with the best profit value */
+		best = find_best_token();
+		if (best < 0)
+			break;
 
-			/* find the token with the best profit value */
-			best = find_best_token();
-			if (token_profit[best] == 0)
-				break;
+		/* replace this token pair in all the valid symbols */
+		compress_symbols(best, i);
 
-			/* place it in the "best" table */
-			token_table[i].len = 2;
-			token_table[i].ch[0] = LEFT(best);
-			token_table[i].ch[1] = RIGHT(best);
+		/* Generate the full name for this symbol */
+		left = &token_table[LEFT(best)];
+		right = &token_table[RIGHT(best)];
 
-			/* replace this token in all the valid symbols */
-			compress_symbols(token_table[i].ch, i);
-		}
+		len = left->len + right->len;
+		str = xmalloc(len + 1);
+		str[len] = 0;
+		memcpy(str, left->str, left->len);
+		memcpy(str + left->len, right->str, right->len);
+		token_table[i].str = str;
+		token_table[i].len = len;
 	}
 }
 
 /* start by placing the symbols that are actually used on the table */
 static void insert_real_symbols_in_table(void)
 {
-	unsigned int i, j, c;
+	unsigned int i, j;
 
 	for (i = 0; i < symbol_cnt; i++) {
 		for (j = 0; j < symbol[i]->len; j++) {
-			c = symbol[i]->sym[j];
-			token_table[c].ch[0] = c;
-			token_table[c].len = 1;
+			token_table[symbol[i]->sym[j]].len = 1;
 		}
 	}
+
+	for (i = 0; i <= 255; i++) {
+		if (!token_table[i].len)
+			continue;
+		token_table[i].str = xmalloc(2);
+		token_table[i].str[0] = i;
+		token_table[i].str[1] = 0;
+	}
 }
 
 static void optimize_token_table(void)
-- 
2.39.5

[PATCH v2 next 12/15] kallsyms: scripts/kallsyms: Optimise compress_symbols()

[David Laight]

When (say) axyb is replaced with azb instead of decrementing the
token_profit[] value for every pair of token in the old string before
the substitution and then incrementing it afterwards just decrement
the counts for ax and yb and increment the ones for az and zb.
Set the count for xy (the number of actual substitions) to zero
afterwards.

This pretty much halves the time taken to do the actual compression
which is by far largest part of the entire process.

Output file unchanged.

Signed-off-by: David Laight <david.laight.linux@gmail.com>
---
 scripts/kallsyms.c | 74 ++++++++++++++++++----------------------------
 1 file changed, 29 insertions(+), 45 deletions(-)

diff --git a/scripts/kallsyms.c b/scripts/kallsyms.c
index 9e1bc0fdaa9f..ee06a9c7435f 100644
--- a/scripts/kallsyms.c
+++ b/scripts/kallsyms.c
@@ -479,13 +479,11 @@ static void learn_symbol(const unsigned char *sym, int len)
 		token_profit[PAIR(sym[i], sym[i + 1])]++;
 }
 
-/* decrease the count for all the possible tokens in a symbol */
-static void forget_symbol(const unsigned char *sym, int len)
+static void adjust_profit(unsigned int old_left, unsigned int new_left,
+			  unsigned int old_right, unsigned int new_right)
 {
-	int i;
-
-	for (i = 0; i < len - 1; i++)
-		token_profit[PAIR(sym[i], sym[i + 1])]--;
+	token_profit[PAIR(old_left, old_right)]--;
+	token_profit[PAIR(new_left, new_right)]++;
 }
 
 /* do the initial token count */
@@ -497,13 +495,12 @@ static void build_initial_token_table(void)
 		learn_symbol(symbol[i]->sym, symbol[i]->len);
 }
 
-static unsigned char *find_token(unsigned char *str, int len,
+static unsigned char *find_token(unsigned char *str, unsigned char *end,
 				 unsigned int want)
 {
 	unsigned int token = PAIR(0, *str++);
-	int i;
 
-	for (i = 0; i < len - 1; i++) {
+	while (str < end) {
 		token = PAIR(RIGHT(token), *str++);
 		if (token == want)
 			return str - 2;
@@ -512,46 +509,33 @@ static unsigned char *find_token(unsigned char *str, int len,
 }
 
 /* replace a given token in all the valid symbols. Use the sampled symbols
- * to update the counts */
-static void compress_symbols(unsigned int token_pair, int idx)
+ * to update the counts.
+ * Marked noinline to help register allocation. compress_symbols() is only called
+ * about 200 times whereas find_token() can be called well over a million times. */
+static __attribute__((noinline)) void compress_symbols(unsigned int token_pair, int idx)
 {
-	unsigned int i, len, size;
-	unsigned char *p1, *p2;
+	unsigned int i, len;
+	unsigned char *sym, *p, *end;
 
 	for (i = 0; i < symbol_cnt; i++) {
-
-		len = symbol[i]->len;
-		p1 = symbol[i]->sym;
-
-		/* find the token on the symbol */
-		p2 = find_token(p1, len, token_pair);
-		if (!p2) continue;
-
-		/* decrease the counts for this symbol's tokens */
-		forget_symbol(symbol[i]->sym, len);
-
-		size = len;
-
-		do {
-			*p2 = idx;
-			p2++;
-			size -= (p2 - p1);
-			memmove(p2, p2 + 1, size);
-			p1 = p2;
-			len--;
-
-			if (size < 2) break;
-
-			/* find the token on the symbol */
-			p2 = find_token(p1, size, token_pair);
-
-		} while (p2);
-
-		symbol[i]->len = len;
-
-		/* increase the counts for this symbol's new tokens */
-		learn_symbol(symbol[i]->sym, len);
+		sym = symbol[i]->sym;
+		end = sym + symbol[i]->len;
+
+		for (p = sym; (p = find_token(p, end, token_pair)); p++) {
+			len = end - p - 2;
+			end--;
+			*p = idx;
+			if (p != sym)
+				adjust_profit(p[-1], p[-1], LEFT(token_pair), idx);
+			if (!len)
+				break;
+			adjust_profit(RIGHT(token_pair), idx, p[2], p[2]);
+			memmove(p + 1, p + 2, len);
+		}
+		symbol[i]->len = end - sym;
 	}
+
+	token_profit[token_pair] = 0;
 }
 
 /* search the token with the maximum profit */
-- 
2.39.5

[PATCH v2 next 13/15] kallsyms: scripts/kallsyms: Reuse tokens that have no references

[David Laight]

Keep track of the number of times each compression token is used.
If the count becomes zero (eg if the only x are in axb and y is
substituted for xb giving ay) then x can be reused.

This means that a token can refer to a long string without needing
tokens for all the shorter strings.

For my normal kernel build four tokens get reused saving 8.5k of data.
The savings may be greater if there are symbols with long matching prefix.

Signed-off-by: David Laight <david.laight.linux@gmail.com>
---
 scripts/kallsyms.c | 45 ++++++++++++++++++++++++++++++++-------------
 1 file changed, 32 insertions(+), 13 deletions(-)

diff --git a/scripts/kallsyms.c b/scripts/kallsyms.c
index ee06a9c7435f..189fb50ec8c5 100644
--- a/scripts/kallsyms.c
+++ b/scripts/kallsyms.c
@@ -76,6 +76,7 @@ static int token_profit[0x10000];
 static struct token_table {
 	char           *str;		/* Full expansion, '\0' terminated */
 	unsigned short len;		/* Length of str */
+	unsigned int   refs;		/* Number of time used in a symbol */
 } token_table[256];
 
 static void usage(void)
@@ -404,7 +405,8 @@ static void write_src(void)
 	for (i = 0; i < 256; i++) {
 		best_idx[i] = off;
 		off += token_table[i].len + 1;
-		printf("\t.asciz\t\"%s\"\n", token_table[i].str);
+		printf("\t.asciz\t\"%s\"\t/* %u: %u */\n",
+		       token_table[i].str, i, token_table[i].refs);
 	}
 	printf(".size kallsyms_token_table, . - kallsyms_token_table\n");
 	printf("\n");
@@ -512,10 +514,11 @@ static unsigned char *find_token(unsigned char *str, unsigned char *end,
  * to update the counts.
  * Marked noinline to help register allocation. compress_symbols() is only called
  * about 200 times whereas find_token() can be called well over a million times. */
-static __attribute__((noinline)) void compress_symbols(unsigned int token_pair, int idx)
+static __attribute__((noinline)) unsigned int compress_symbols(unsigned int token_pair, int idx)
 {
 	unsigned int i, len;
 	unsigned char *sym, *p, *end;
+	unsigned int substitutions;
 
 	for (i = 0; i < symbol_cnt; i++) {
 		sym = symbol[i]->sym;
@@ -535,7 +538,10 @@ static __attribute__((noinline)) void compress_symbols(unsigned int token_pair,
 		symbol[i]->len = end - sym;
 	}
 
+	substitutions = token_profit[token_pair];
 	token_profit[token_pair] = 0;
+
+	return substitutions;
 }
 
 /* search the token with the maximum profit */
@@ -558,29 +564,41 @@ static int find_best_token(void)
 /* this is the core of the algorithm: calculate the "best" table */
 static void optimize_result(void)
 {
-	int i, best;
-	unsigned int len;
+	unsigned int i, idx, len, refs;
 	struct token_table *left, *right;
+	unsigned char to_process[256];
 	char *str;
+	int best;
 
-	/* Use the '\0' symbol last so the output is unchanged */
-	for (i = 255; i >= 0; i--) {
-		/* Ignore tokens used for the original character codes. */
-		if (token_table[i].len)
-			continue;
+	/* Generate a list of the unused tokens. */
+	for (i = 0, idx = 0; i < 256; i++) {
+		if (!token_table[i].len)
+			to_process[idx++] = i;
+	}
 
+	do {
 		/* find the token pair with the best profit value */
 		best = find_best_token();
 		if (best < 0)
 			break;
+		i = to_process[--idx];
 
 		/* replace this token pair in all the valid symbols */
-		compress_symbols(best, i);
+		refs = compress_symbols(best, i);
+
+		/* Update the number of times each token is used */
+		token_table[i].refs += refs;
 
 		/* Generate the full name for this symbol */
 		left = &token_table[LEFT(best)];
 		right = &token_table[RIGHT(best)];
+		if (!(left->refs -= refs))
+			/* There are no references left, reuse the token. */
+			to_process[idx++] = LEFT(best);
+		if (!(right->refs -= refs))
+			to_process[idx++] = RIGHT(best);
 
+		/* Generate the full name for this symbol */
 		len = left->len + right->len;
 		str = xmalloc(len + 1);
 		str[len] = 0;
@@ -588,7 +606,7 @@ static void optimize_result(void)
 		memcpy(str + left->len, right->str, right->len);
 		token_table[i].str = str;
 		token_table[i].len = len;
-	}
+	} while (idx);
 }
 
 /* start by placing the symbols that are actually used on the table */
@@ -598,13 +616,14 @@ static void insert_real_symbols_in_table(void)
 
 	for (i = 0; i < symbol_cnt; i++) {
 		for (j = 0; j < symbol[i]->len; j++) {
-			token_table[symbol[i]->sym[j]].len = 1;
+			token_table[symbol[i]->sym[j]].refs++;
 		}
 	}
 
 	for (i = 0; i <= 255; i++) {
-		if (!token_table[i].len)
+		if (!token_table[i].refs)
 			continue;
+		token_table[i].len = 1;
 		token_table[i].str = xmalloc(2);
 		token_table[i].str[0] = i;
 		token_table[i].str[1] = 0;
-- 
2.39.5

[PATCH 14/15] kallsyms: scripts/kallsyms: Reduce the output file size

[David Laight]

The output file isn't normally looked at by anyone; so doesn't need
redundant information or formatting.
Reduce the size somewhat:
- Use "%u" instead of " 0x%02x" for byte values.
  Remove some other spaces.
- Only include the symbol name once.
  Put the offset into the compressed symbol names in all three per-symbol
  tables so that the lines can be cross-referenced if necessary.
- Output the kallsyms_token_index table and kallsyms_markers with
  multiple values per line.
- Add the missing .size for kallsyms_token_index.
- Output the token table first.
There is still enough information to help debug the code.

All the printfs are slow - but find_token() dominates everything.

Reduces the file size by about 25%.

Signed-off-by: David Laight <david.laight.linux@gmail.com>
---
 scripts/kallsyms.c | 93 +++++++++++++++++++++++++++-------------------
 1 file changed, 55 insertions(+), 38 deletions(-)

diff --git a/scripts/kallsyms.c b/scripts/kallsyms.c
index 189fb50ec8c5..8576fe6ad90b 100644
--- a/scripts/kallsyms.c
+++ b/scripts/kallsyms.c
@@ -350,6 +350,30 @@ static void write_src(void)
 	struct sym_entry *se;
 
 	printf("\t.section .rodata, \"a\"\n");
+	printf("\n");
+
+	output_label("kallsyms_token_table");
+	off = 0;
+	for (i = 0; i < 256; i++) {
+		best_idx[i] = off;
+		off += token_table[i].len + 1;
+		printf("\t.asciz\t\"%s\"\t/* %u: %u */\n",
+		       token_table[i].str, i, token_table[i].refs);
+	}
+	printf(".size kallsyms_token_table, . - kallsyms_token_table\n");
+	printf("\n");
+
+	output_label("kallsyms_token_index");
+	for (i = 0; i < 256; i++) {
+		if (i & 15)
+			printf(",");
+		else
+			printf("\n\t.short\t" + !i);
+		printf("%u", best_idx[i]);
+	}
+	printf("\n");
+	printf(".size kallsyms_token_index, . - kallsyms_token_index\n");
+	printf("\n");
 
 	output_value("kallsyms_num_syms", symbol_cnt);
 
@@ -359,35 +383,37 @@ static void write_src(void)
 		se = symbol[i];
 		se->seq = off;
 
-		/* There cannot be any symbol of length zero. */
-		if (se->len == 0)
-			errx(1, "unexpected zero symbol length");
+		/* The length must be less than that of the original symbol. */
+		if (!se->len || se->len > KSYM_NAME_LEN)
+			errx(1, "symbol %d has corrupt compressed length %d\n",
+			     i, se->len);
 
-		/* Only lengths that fit in up-to-two-byte ULEB128 are supported. */
-		if (se->len > 0x3FFF)
-			errx(1, "unexpected huge symbol length");
+		/*
+		 * Output the number that identifies the symbol at the start
+		 * of the line so that they line up nicely.
+		 */
+		printf("\t/* n:%u */\t.byte\t", off);
 
 		/* Encode length with ULEB128. */
 		if (se->len <= 0x7F) {
 			/* Most symbols use a single byte for the length. */
-			printf("\t.byte 0x%02x", se->len);
+			printf("%u", se->len);
 			off += se->len + 1;
 		} else {
 			/* "Big" symbols use two bytes. */
-			printf("\t.byte 0x%02x, 0x%02x",
-				(se->len & 0x7F) | 0x80, (se->len >> 7) & 0x7F);
+			printf("%u,%u", (se->len & 0x7F) | 0x80, (se->len >> 7) & 0x7F);
 			off += se->len + 2;
 		}
 		for (k = 0; k < se->len; k++)
-			printf(", 0x%02x", se->sym[k]);
+			printf(",%u", se->sym[k]);
+		printf("\n");
 
 		/*
 		 * Now that we wrote out the compressed symbol name, restore the
-		 * original name and print it in the comment.
+		 * original name.
 		 */
 		se->len = expand_symbol(se->sym, se->len, buf);
 		memcpy(se->sym, buf, se->len + 1);
-		printf("\t/* %s */\n", se->sym);
 	}
 	table_size = off;
 	printf(".size kallsyms_names, . - kallsyms_names\n");
@@ -395,25 +421,15 @@ static void write_src(void)
 
 	output_value("kallsyms_marker_shift", marker_shift);
 	output_label("kallsyms_markers");
-	for (i = 0; i < symbol_cnt; i += 1u << marker_shift)
-		printf("\t.long\t%u\n", symbol[i]->seq);
-	printf(".size kallsyms_markers, . - kallsyms_markers\n");
-	printf("\n");
-
-	output_label("kallsyms_token_table");
-	off = 0;
-	for (i = 0; i < 256; i++) {
-		best_idx[i] = off;
-		off += token_table[i].len + 1;
-		printf("\t.asciz\t\"%s\"\t/* %u: %u */\n",
-		       token_table[i].str, i, token_table[i].refs);
+	for (i = 0, k = 0; i < symbol_cnt; i += 1u << marker_shift, k++) {
+		if (k & 7)
+			printf(",");
+		else
+			printf("\n\t.long\t" + !k);
+		printf("%u", symbol[i]->seq);
 	}
-	printf(".size kallsyms_token_table, . - kallsyms_token_table\n");
 	printf("\n");
-
-	output_label("kallsyms_token_index");
-	for (i = 0; i < 256; i++)
-		printf("\t.short\t%d\n", best_idx[i]);
+	printf(".size kallsyms_markers, . - kallsyms_markers\n");
 	printf("\n");
 
 	output_label("kallsyms_offsets");
@@ -424,13 +440,13 @@ static void write_src(void)
 			long long offset = se->addr - _text;
 
 			if (offset < INT_MIN || offset > INT_MAX)
-				errx(1, "relative symbol value %#llx out of range",
-				     se->addr);
-			printf("\t.long\t_text - . + (%d)\t/* %s */\n",
-			       (int)offset, se->sym);
+				errx(1, "relative symbol %s value %#llx out of range\n",
+					se->sym + 1, se->addr);
+			printf("\t.long\t_text-.+%d\t/* n:%u %c %s */\n",
+			       (int)offset, se->seq, se->sym[0], se->sym + 1);
 		} else {
-			printf("\t.long\t%#x\t/* %s */\n",
-			       (unsigned int)se->addr, se->sym);
+			printf("\t.long\t%#x\t/* n:%u %c %s */\n",
+			       (unsigned int)se->addr, se->seq, se->sym[0], se->sym + 1);
 		}
 	}
 	printf(".size kallsyms_offsets, . - kallsyms_offsets\n");
@@ -451,10 +467,11 @@ static void write_src(void)
 #ifdef CONFIG_CPU_BIG_ENDIAN
 			off = __builtin_bswap32(off) >> 8;
 #endif
-			printf("\t.byte\t0x%02x, 0x%02x, 0x%02x\t/* %s */\n",
-				off & 0xff, (off >> 8) & 0xff, off >> 16, se->sym);
+			/* The three spaces before the tab line up the comments */
+			printf("\t.byte\t%u,%u,%u   \t/* n:%u */\n",
+				off & 0xff, (off >> 8) & 0xff, off >> 16, se->seq);
 		} else {
-			printf("\t.long\t%#04x\t/* %s */\n", off, se->sym);
+			printf("\t.long\t%#04x\t/* n:%u */\n", off, se->seq);
 		}
 	}
 	/* Terminator without the 'duplicate' flag. */
-- 
2.39.5

[PATCH 15/15] kallsyms: scripts/kallsyms: Improve compression by about 2%

[David Laight]

If the symbols contain a lot of "abc" and "abd" and a few "abe" then
the compression code first substitutes (say) 'x' for "ab" giving
"xc", "xd" and "xe".
It might later substitute 'y' for "xc" and 'z' for "xd" giving
"y", "z" and "xe".
The token 'x' is then hardly used, expanding "xe" back to "abe"
costs one byte every time it is used, but frees up 'x' to be used
for a much more common symbol pair.

Add a check at the end of the compression that all the counts still match.

Increases the compression ratio by about 2% on both the 'normal'
kernel I'm building and on the x86-64 allyesconfig kernel.

For simplicity the code will only expand a token where the two tokens
that were merged are still in the table.
It might be possible to find some others, eg ones that are 3 characters.

Signed-off-by: David Laight <david.laight.linux@gmail.com>
---
 scripts/kallsyms.c | 137 +++++++++++++++++++++++++++++++++++++++++----
 1 file changed, 127 insertions(+), 10 deletions(-)

diff --git a/scripts/kallsyms.c b/scripts/kallsyms.c
index 8576fe6ad90b..9dbd7c85eec1 100644
--- a/scripts/kallsyms.c
+++ b/scripts/kallsyms.c
@@ -76,6 +76,7 @@ static int token_profit[0x10000];
 static struct token_table {
 	char           *str;		/* Full expansion, '\0' terminated */
 	unsigned short len;		/* Length of str */
+	unsigned short pair;		/* Original token pair for this token */
 	unsigned int   refs;		/* Number of time used in a symbol */
 } token_table[256];
 
@@ -514,6 +515,37 @@ static void build_initial_token_table(void)
 		learn_symbol(symbol[i]->sym, symbol[i]->len);
 }
 
+/* Check that the token_profit[] matches the compressed symbols. */
+static void check_tables(void)
+{
+	unsigned int save_profit[0x10000];
+	unsigned int tok_refs[256];
+	unsigned int i, j;
+
+	memcpy(save_profit, token_profit, sizeof(save_profit));
+	memset(token_profit, 0, sizeof(token_profit));
+
+	build_initial_token_table();
+
+	for (i = 0; i < 0x10000; i++) {
+		if (token_profit[i] != save_profit[i])
+			errx(1, "profit error for %u,%u (%s/%s) discrepency %u != %u\n",
+			     LEFT(i), RIGHT(i), token_table[LEFT(i)].str,
+			     token_table[RIGHT(i)].str, token_profit[i], save_profit[i]);
+	}
+
+	memset(tok_refs, 0, sizeof(tok_refs));
+	for (i = 0; i < symbol_cnt; i++)
+		for (j = 0; j < symbol[i]->len; j++)
+			tok_refs[symbol[i]->sym[j]]++;
+
+	for (i = 1; i < 256; i++) {
+		if (tok_refs[i] != token_table[i].refs)
+			errx(1, "token reference error for %u (%s) %u != %u\n",
+			     i, token_table[i].str, token_table[i].refs, tok_refs[i]);
+	}
+}
+
 static unsigned char *find_token(unsigned char *str, unsigned char *end,
 				 unsigned int want)
 {
@@ -561,6 +593,47 @@ static __attribute__((noinline)) unsigned int compress_symbols(unsigned int toke
 	return substitutions;
 }
 
+/* Change every occurance of idx back to token_pair.
+ * This extends all the symbol table entries but frees up a token. */
+static __attribute__((noinline)) void uncompress_symbols(unsigned int token_pair, int idx)
+{
+	unsigned int i, len;
+	unsigned char *sym, *p, *end;
+	unsigned int substitutions;
+
+	for (i = 0; i < symbol_cnt; i++) {
+		sym = symbol[i]->sym;
+		len = symbol[i]->len;
+		p = memchr(sym, idx, len);
+		if (!p)
+			continue;
+		end = sym + len;
+
+		do {
+			len = end - p - 1;
+			end++;
+			if (len) {
+				adjust_profit(idx, RIGHT(token_pair), p[1], p[1]);
+				memmove(p + 2, p + 1, len);
+			}
+			p[0] = LEFT(token_pair);
+			p[1] = RIGHT(token_pair);
+			if (p != sym)
+				adjust_profit(p[-1], p[-1], idx, LEFT(token_pair));
+			p = memchr(p + 2, idx, len);
+		} while (p);
+		symbol[i]->len = end - sym;
+	}
+
+	substitutions = token_table[idx].refs;
+
+	token_profit[token_pair] += substitutions;
+
+	token_table[idx].refs = 0;
+	token_table[LEFT(token_pair)].refs += substitutions;
+	token_table[RIGHT(token_pair)].refs += substitutions;
+}
+
 /* search the token with the maximum profit */
 static int find_best_token(void)
 {
@@ -578,14 +651,47 @@ static int find_best_token(void)
 	return best;
 }
 
+static int split_token(unsigned int profit)
+{
+	struct token_table *tt, *left, *right;
+	unsigned int i;
+	int best = -1;
+
+	for (i = 0; i < 256; i++) {
+		tt = token_table + i;
+
+		if (tt->len == 1 || tt->refs >= profit)
+			continue;
+
+		/* Ignore tokens where the original parts have be reused */
+		left = &token_table[LEFT(tt->pair)];
+		right = &token_table[RIGHT(tt->pair)];
+		if (tt->len != left->len + right->len ||
+		    memcmp(tt->str, left->str, left->len) ||
+		    memcmp(tt->str + left->len, right->str, right->len))
+			continue;
+
+		best = i;
+		if (tt->refs == 2)
+			break;
+		profit = tt->refs;
+	}
+	if (best < 0)
+		return -1;
+
+	uncompress_symbols(token_table[best].pair, best);
+
+	return best;
+}
+
 /* this is the core of the algorithm: calculate the "best" table */
 static void optimize_result(void)
 {
-	unsigned int i, idx, len, refs;
-	struct token_table *left, *right;
+	struct token_table *t, *left, *right;
 	unsigned char to_process[256];
+	unsigned int idx, len, refs;
+	int i, best;
 	char *str;
-	int best;
 
 	/* Generate a list of the unused tokens. */
 	for (i = 0, idx = 0; i < 256; i++) {
@@ -593,20 +699,28 @@ static void optimize_result(void)
 			to_process[idx++] = i;
 	}
 
-	do {
+	for (;;) {
 		/* find the token pair with the best profit value */
 		best = find_best_token();
 		if (best < 0)
 			break;
-		i = to_process[--idx];
+		if (idx) {
+			i = to_process[--idx];
+		} else {
+			/* Try to free up a little-used token. */
+			i = split_token(token_profit[best]);
+			if (i < 0)
+				break;
+		}
 
 		/* replace this token pair in all the valid symbols */
 		refs = compress_symbols(best, i);
+		t = &token_table[i];
 
 		/* Update the number of times each token is used */
-		token_table[i].refs += refs;
+		t->refs += refs;
+		t->pair = best;
 
-		/* Generate the full name for this symbol */
 		left = &token_table[LEFT(best)];
 		right = &token_table[RIGHT(best)];
 		if (!(left->refs -= refs))
@@ -621,9 +735,10 @@ static void optimize_result(void)
 		str[len] = 0;
 		memcpy(str, left->str, left->len);
 		memcpy(str + left->len, right->str, right->len);
-		token_table[i].str = str;
-		token_table[i].len = len;
-	} while (idx);
+		free(t->str);
+		t->str = str;
+		t->len = len;
+	}
 }
 
 /* start by placing the symbols that are actually used on the table */
@@ -654,6 +769,8 @@ static void optimize_token_table(void)
 	insert_real_symbols_in_table();
 
 	optimize_result();
+
+	check_tables();
 }
 
 /* guess for "linker script provide" symbol */
-- 
2.39.5

Re: [PATCH v2 next 11/15] kallsyms: scripts/kallsyms: Keep full expansion of tokens

[sashiko-bot]

Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [High] kallsyms: NULL token_table[].str passed to printf() in write_src()
--

commit b464b94e58431a4ad1ec112c739d63f16547b8f2
Author: David Laight <david.laight.linux@gmail.com>

kallsyms: scripts/kallsyms: Keep full expansion of tokens

This commit stores the full NUL-terminated string expansion for each token
in token_table[] as tokens are allocated, avoiding recursive symbol
expansions later.

> diff --git a/scripts/kallsyms.c b/scripts/kallsyms.c
> index 5603b2a6c77bd..9e1bc0fdaa9f2 100644
> --- a/scripts/kallsyms.c
> +++ b/scripts/kallsyms.c
[ ... ]
> @@ -415,9 +403,8 @@ static void write_src(void)
>  	off = 0;
>  	for (i = 0; i < 256; i++) {
>  		best_idx[i] = off;
> -		expand_symbol(token_table[i].ch, token_table[i].len, buf);
> -		printf("\t.asciz\t\"%s\"\n", buf);
> -		off += strlen(buf) + 1;
> +		off += token_table[i].len + 1;
> +		printf("\t.asciz\t\"%s\"\n", token_table[i].str);
>  	}
>  	printf(".size kallsyms_token_table, . - kallsyms_token_table\n");
>  	printf("\n");

[Severity: High]
Can token_table[i].str be NULL here when some token slots remain unused?

In insert_real_symbols_in_table(), token_table[i].str is only allocated for
character codes present in the input symbols:

	for (i = 0; i <= 255; i++) {
		if (!token_table[i].len)
			continue;
		token_table[i].str = xmalloc(2);
		token_table[i].str[0] = i;
		token_table[i].str[1] = 0;
	}

Then in optimize_result(), the loop stops early as soon as find_best_token()
finds no remaining token pairs with positive profit:

		best = find_best_token();
		if (best < 0)
			break;

Any remaining unused entries in token_table[] keep len == 0 and str == NULL.
During pass 0 in scripts/link-vmlinux.sh, kallsyms is invoked on an empty
symbol file (.tmp_vmlinux0.syms), leaving all 256 token_table[i].str
pointers as NULL.

Previously, expand_symbol() wrote an empty string into buf when len was 0.
Passing a NULL token_table[i].str to printf("%s") in write_src() causes a
segmentation fault on non-glibc hosts (such as musl) or prints "(null)" on
glibc hosts while advancing off by only 1 byte, which corrupts
kallsyms_token_table and best_idx[].

-- 
Sashiko AI review · https://sashiko.dev/#/patchset/20261018155206.132411-1-david.laight.linux@gmail.com?part=11

Re: [PATCH v2 next 03/15] kallsyms: Improve selftest test_perf_kallsyms_lookup_name() output

[sashiko-bot]

Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [Medium] kallsyms: unused variable kallsyms_very_long_name when !CONFIG_KALLSYMS_ALL
--

commit 3e15f2fb96b74e4386511b5db1ead3ae1d1fdf8a
Author: David Laight <david.laight.linux@gmail.com>

kallsyms: Improve selftest test_perf_kallsyms_lookup_name() output

This commit improves the kallsyms_lookup_name() performance selftest by
measuring the faster of two lookups, verifying returned addresses, printing
an 8-line histogram of lookup times, and adding a very long symbol to test
two-byte length handling.

> diff --git a/kernel/kallsyms_selftest.c b/kernel/kallsyms_selftest.c
> index 0db79237fe548..9072bd91c318c 100644
> --- a/kernel/kallsyms_selftest.c
> +++ b/kernel/kallsyms_selftest.c
> @@ -29,35 +31,56 @@ struct test_stat {

[ ... ]

> +/* This is 509 characters, compresses to about 330 */
> +#define kallsyms_very_long_name \
> +The_time_has_come_the_Walrus_said_To_talk_of_many_things\
> +_Of_shoes_and_ships_and_sealing_wax_Of_cabbages_and_kings\
> +_And_why_the_sea_is_boiling_hot_And_whether_pigs_have_wings\
> +\
> +_O_Oysters_said_the_Carpenter_Youve_had_a_pleasant_run\
> +_Shall_we_be_trotting_home_again_But_answer_came_there_none\
> +_And_this_was_scarcely_odd_because_Theyd_eaten_every_one\
> +\
> +_The_moon_was_shining_sulkily_Because_she_thought_the_sun\
> +_Had_got_no_business_to_be_there_After_the_day_was_done\
> +_Its_very_rude_of_him_she_said_To_come_and_spoil_the_fun
> +
> +static int kallsyms_very_long_name = 1;
> +
>  static int kallsyms_test_func_static(void)
>  {
>  	kallsyms_test_var_bss_static++;
> @@ -79,16 +102,17 @@ __weak int kallsyms_test_func_weak(void)
>  }
>  
>  static struct test_item test_items[] = {
> -	ITEM_FUNC(kallsyms_test_func_static),
> -	ITEM_FUNC(kallsyms_test_func),
> -	ITEM_FUNC(kallsyms_test_func_weak),
> -	ITEM_FUNC(vmalloc_noprof),
> -	ITEM_FUNC(vfree),
> +	TEST_ITEM(kallsyms_test_func_static),
> +	TEST_ITEM(kallsyms_test_func),
> +	TEST_ITEM(kallsyms_test_func_weak),
> +	TEST_ITEM(vmalloc_noprof),
> +	TEST_ITEM(vfree),
>  #ifdef CONFIG_KALLSYMS_ALL
> -	ITEM_DATA(kallsyms_test_var_bss_static),
> -	ITEM_DATA(kallsyms_test_var_data_static),
> -	ITEM_DATA(kallsyms_test_var_bss),
> -	ITEM_DATA(kallsyms_test_var_data),
> +	TEST_ITEM(kallsyms_test_var_bss_static),
> +	TEST_ITEM(kallsyms_test_var_data_static),
> +	TEST_ITEM(kallsyms_very_long_name),
> +	TEST_ITEM(kallsyms_test_var_bss),
> +	TEST_ITEM(kallsyms_test_var_data),
>  #endif
>  };

[Severity: Medium]
When CONFIG_KALLSYMS_SELFTEST=y and CONFIG_KALLSYMS_ALL=n, will
kallsyms_very_long_name trigger an unused-variable compiler warning?

Unlike kallsyms_test_var_bss_static and kallsyms_test_var_data_static, which
are incremented inside kallsyms_test_func_static(), kallsyms_very_long_name
is defined unconditionally as a static variable in
kernel/kallsyms_selftest.c, while its only reference in test_items[] is
guarded by #ifdef CONFIG_KALLSYMS_ALL.

Should kallsyms_very_long_name also be referenced in
kallsyms_test_func_static() or guarded by #ifdef CONFIG_KALLSYMS_ALL?

[ ... ]

-- 
Sashiko AI review · https://sashiko.dev/#/patchset/20261018155206.132411-1-david.laight.linux@gmail.com?part=3

Re: [PATCH 15/15] kallsyms: scripts/kallsyms: Improve compression by about 2%

[sashiko-bot]

Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [Medium] kallsyms: infinite loop in optimize_result() on self-overlapping token pairs
--

commit 36121744ef0b7fd951486247d0297f67eaca31d8
Author: David Laight <david.laight.linux@gmail.com>

kallsyms: scripts/kallsyms: Improve compression by about 2%

This commit improves kallsyms compression by expanding infrequently used
merged tokens back into their original constituent pairs when no unused
tokens remain, freeing slots for more profitable token pairs.

> diff --git a/scripts/kallsyms.c b/scripts/kallsyms.c
> index 8576fe6ad90b7..9dbd7c85eec1e 100644
> --- a/scripts/kallsyms.c
> +++ b/scripts/kallsyms.c
[ ... ]
> @@ -561,6 +593,47 @@ static __attribute__((noinline)) unsigned int compress_symbols(unsigned int toke
>  	return substitutions;
>  }
>  
> +/* Change every occurance of idx back to token_pair.
> + * This extends all the symbol table entries but frees up a token. */
> +static __attribute__((noinline)) void uncompress_symbols(unsigned int token_pair, int idx)
> +{
> +	unsigned int i, len;
> +	unsigned char *sym, *p, *end;
> +	unsigned int substitutions;
> +
> +	for (i = 0; i < symbol_cnt; i++) {
> +		sym = symbol[i]->sym;
> +		len = symbol[i]->len;
> +		p = memchr(sym, idx, len);
> +		if (!p)
> +			continue;
> +		end = sym + len;
> +
> +		do {
> +			len = end - p - 1;
> +			end++;
> +			if (len) {
> +				adjust_profit(idx, RIGHT(token_pair), p[1], p[1]);
> +				memmove(p + 2, p + 1, len);
> +			}
> +			p[0] = LEFT(token_pair);
> +			p[1] = RIGHT(token_pair);
> +			if (p != sym)
> +				adjust_profit(p[-1], p[-1], idx, LEFT(token_pair));
> +			p = memchr(p + 2, idx, len);
> +		} while (p);
> +		symbol[i]->len = end - sym;
> +	}
> +
> +	substitutions = token_table[idx].refs;
> +
> +	token_profit[token_pair] += substitutions;
> +
> +	token_table[idx].refs = 0;
> +	token_table[LEFT(token_pair)].refs += substitutions;
> +	token_table[RIGHT(token_pair)].refs += substitutions;
> +}
> +
>  /* search the token with the maximum profit */
>  static int find_best_token(void)
>  {
> @@ -578,14 +651,47 @@ static int find_best_token(void)
>  	return best;
>  }
>  
> +static int split_token(unsigned int profit)
> +{
> +	struct token_table *tt, *left, *right;
> +	unsigned int i;
> +	int best = -1;
> +
> +	for (i = 0; i < 256; i++) {
> +		tt = token_table + i;
> +
> +		if (tt->len == 1 || tt->refs >= profit)
> +			continue;
> +
> +		/* Ignore tokens where the original parts have be reused */
> +		left = &token_table[LEFT(tt->pair)];
> +		right = &token_table[RIGHT(tt->pair)];
> +		if (tt->len != left->len + right->len ||
> +		    memcmp(tt->str, left->str, left->len) ||
> +		    memcmp(tt->str + left->len, right->str, right->len))
> +			continue;
> +
> +		best = i;
> +		if (tt->refs == 2)
> +			break;
> +		profit = tt->refs;
> +	}
> +	if (best < 0)
> +		return -1;
> +
> +	uncompress_symbols(token_table[best].pair, best);
> +
> +	return best;
> +}
> +
>  /* this is the core of the algorithm: calculate the "best" table */
>  static void optimize_result(void)
>  {
> -	unsigned int i, idx, len, refs;
> -	struct token_table *left, *right;
> +	struct token_table *t, *left, *right;
>  	unsigned char to_process[256];
> +	unsigned int idx, len, refs;
> +	int i, best;
>  	char *str;
> -	int best;
>  
>  	/* Generate a list of the unused tokens. */
>  	for (i = 0, idx = 0; i < 256; i++) {
> @@ -593,20 +699,28 @@ static void optimize_result(void)
>  			to_process[idx++] = i;
>  	}
>  
> -	do {
> +	for (;;) {
>  		/* find the token pair with the best profit value */
>  		best = find_best_token();
>  		if (best < 0)
>  			break;
> -		i = to_process[--idx];
> +		if (idx) {
> +			i = to_process[--idx];
> +		} else {
> +			/* Try to free up a little-used token. */
> +			i = split_token(token_profit[best]);
> +			if (i < 0)
> +				break;
> +		}
>  
>  		/* replace this token pair in all the valid symbols */
>  		refs = compress_symbols(best, i);
> +		t = &token_table[i];
>  
>  		/* Update the number of times each token is used */
> -		token_table[i].refs += refs;
> +		t->refs += refs;
> +		t->pair = best;

[Severity: Medium]
Can optimize_result() enter an infinite loop when find_best_token() selects a
homogeneous token pair best = PAIR(x, x) that overlaps with itself in runs of
3 or more identical tokens?

For a homogeneous pair PAIR(x, x) where LEFT(best) == RIGHT(best),
learn_symbol() and uncompress_symbols() count every adjacent pair, so a run
of [x, x, x] increments token_profit[PAIR(x, x)] by 2. However, when
compress_symbols(PAIR(x, x), i) replaces the first pair to form [i, x], it
calls:

    adjust_profit(RIGHT(token_pair), idx, p[2], p[2]);

which is adjust_profit(x, i, x, x), decrementing token_profit[PAIR(x, x)] by
1 for each triple. As a result, compress_symbols() performs fewer
substitutions (refs) than the initial token_profit[best] passed to
split_token().

If idx == 0 and a splittable token s representing PAIR(y, z) has
refs < token_table[s].refs < token_profit[PAIR(x, x)] (for example, two
occurrences of [x, x, x] giving token_profit[PAIR(x, x)] = 4 and actual
refs = 2, while token s has token_table[s].refs = 3):

1. optimize_result() calls split_token(4), which selects token s (since
3 < 4) and calls uncompress_symbols(PAIR(y, z), s), setting
token_profit[PAIR(y, z)] = 3. Then compress_symbols(PAIR(x, x), s) performs
only refs = 2 substitutions, setting token_table[s].refs = 2 and
token_table[s].pair = PAIR(x, x).

2. On the next iteration, find_best_token() selects PAIR(y, z) with profit 3.
split_token(3) selects token s again because token_table[s].refs (2) < 3 and
token_table[x] is still valid. uncompress_symbols(PAIR(x, x), s) restores the
two [x, x, x] runs and sets token_profit[PAIR(x, x)] back to 4 (2 from
adjust_profit(s, x, x, x) in the loop plus 2 from substitutions). Then
compress_symbols(PAIR(y, z), s) sets token_table[s].refs = 3.

Would this cause optimize_result() to alternate between splitting and
compressing PAIR(x, x) and PAIR(y, z) indefinitely?

>  
> -		/* Generate the full name for this symbol */
>  		left = &token_table[LEFT(best)];
>  		right = &token_table[RIGHT(best)];
[ ... ]

ওয়াট

-- 
Sashiko AI review · https://sashiko.dev/#/patchset/20261018155206.132411-1-david.laight.linux@gmail.com?part=15

Re: [PATCH 14/15] kallsyms: scripts/kallsyms: Reduce the output file size

[sashiko-bot]

Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [High] kallsyms: NULL dereference and offset mismatch in write_src() on unused tokens
--

commit 20102d6e3b81d88a59f6ac3b9732c8a7b28d3f98
Author: David Laight <david.laight.linux@gmail.com>

kallsyms: scripts/kallsyms: Reduce the output file size

This commit reduces the size of the assembly output generated by
scripts/kallsyms by formatting byte values in decimal, packing multiple
values per line for kallsyms_token_index and kallsyms_markers, moving the
token tables first, and replacing duplicate symbol name comments with
symbol offsets.

> diff --git a/scripts/kallsyms.c b/scripts/kallsyms.c
> index 189fb50ec8c58..8576fe6ad90b7 100644
> --- a/scripts/kallsyms.c
> +++ b/scripts/kallsyms.c
> @@ -350,6 +350,30 @@ static void write_src(void)
>  	struct sym_entry *se;
>  
>  	printf("\t.section .rodata, \"a\"\n");
> +	printf("\n");
> +
> +	output_label("kallsyms_token_table");
> +	off = 0;
> +	for (i = 0; i < 256; i++) {
> +		best_idx[i] = off;
> +		off += token_table[i].len + 1;
> +		printf("\t.asciz\t\"%s\"\t/* %u: %u */\n",
> +		       token_table[i].str, i, token_table[i].refs);
> +	}

[Severity: High]
Can token_table[i].str be NULL here when fewer than 256 tokens are
populated?

During pass 0 of a CONFIG_KALLSYMS=y build, scripts/link-vmlinux.sh runs
scripts/kallsyms on an empty symbol file:

scripts/link-vmlinux.sh:kallsyms_step() {
    ...
    if is_enabled CONFIG_KALLSYMS; then
        true > .tmp_vmlinux0.syms
        kallsyms .tmp_vmlinux0.syms .tmp_vmlinux0.kallsyms
    fi
    ...
}

When symbol_cnt is 0 (or whenever the input symbols do not populate all
256 entries), insert_real_symbols_in_table() leaves token_table[i].str as
NULL and token_table[i].len as 0 for unreferenced tokens:

scripts/kallsyms.c:insert_real_symbols_in_table() {
    ...
    for (i = 0; i <= 255; i++) {
        if (!token_table[i].refs)
            continue;
        token_table[i].len = 1;
        token_table[i].str = xmalloc(2);
        token_table[i].str[0] = i;
        token_table[i].str[1] = 0;
    }
}

In optimize_result(), find_best_token() then returns -1 and breaks out of
the loop before filling the remaining unused tokens.

When write_src() passes token_table[i].str to printf("%s"), isn't that
undefined behavior that segfaults on non-glibc hosts (such as musl)? Also,
on glibc hosts where printf("%s", NULL) outputs "(null)" (7 bytes
including the NUL terminator in .asciz), off is only incremented by
token_table[i].len + 1 (1 byte), which mismatches the actual size emitted
into kallsyms_token_table and corrupts the offsets recorded in best_idx[].

[ ... ]

-- 
Sashiko AI review · https://sashiko.dev/#/patchset/20261018155206.132411-1-david.laight.linux@gmail.com?part=14

Re: [PATCH v2 next 06/15] kallsyms: Optimise symbol name search

[sashiko-bot]

Thank you for your contribution! Sashiko AI review found 2 potential issue(s) to consider:
- [High] kallsyms: race in set_kallsyms_off_size() causes NULL dereference
- [High] kallsyms: set_kallsyms_off_size() sleeps in atomic context
--

commit d36232e927821c82911022ce5bae7cb3de465edd
Author: David Laight <david.laight.linux@gmail.com>

kallsyms: Optimise symbol name search

This commit optimizes symbol name lookups by indexing the compressed
names table directly instead of the array of symbol values. It supports
both 24-bit and 32-bit offset tables, selecting between them using a
static branch initialized on the first symbol lookup.

> diff --git a/kernel/kallsyms.c b/kernel/kallsyms.c
> index d18d78e626db2..31451feac8221 100644
> --- a/kernel/kallsyms.c
> +++ b/kernel/kallsyms.c

[ ... ]

> @@ -185,14 +216,19 @@ unsigned long kallsyms_sym_address(int idx)
>  	return (unsigned long)offset_to_ptr(kallsyms_offsets + idx);
>  }
>  
> -static unsigned int get_symbol_seq(int index)
> -{
> -	unsigned int i, seq = 0;
> +static DEFINE_STATIC_KEY_TRUE(kallsyms_off_size_24);
>  
> -	for (i = 0; i < 3; i++)
> -		seq = (seq << 8) | kallsyms_seqs_of_names[3 * index + i];
> +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 seq;
> +static void set_kallsyms_off_size(void)
> +{
> +	if (kallsyms_off_size != 24)
> +		static_branch_disable(&kallsyms_off_size_24);
>  }

[Severity: High]
Can calling static_branch_disable() in set_kallsyms_off_size() sleep in
an atomic or early-boot context when kallsyms_off_size != 24?

static_branch_disable() calls static_key_disable() in
kernel/jump_label.c, which acquires cpus_read_lock() and
jump_label_mutex:

kernel/jump_label.c:static_key_disable() {
	cpus_read_lock();
	static_key_disable_cpuslocked(key);
	cpus_read_unlock();
}

However, kallsyms_lookup_name() -> kallsyms_lookup_names() can be called
first from contexts where sleeping is not allowed:

- lib/codetag.c:get_symbol() calls kallsyms_lookup_name() under
  preempt_disable():

	preempt_disable();
	ret = mod ?
		(void *)find_kallsyms_symbol_value(mod, buf) :
		(void *)kallsyms_lookup_name(buf);
	preempt_enable();

- mm/alloc_tag.c:alloc_tag_sec_init() calls kallsyms_lookup_name() during
  start_kernel() -> mm_core_init() while interrupts are disabled and
  before poking_init().

- Non-sleepable runtime or debugger callers such as
  bpf_kallsyms_lookup_name(), kdbgetsymval(), and xmon also invoke
  kallsyms_lookup_name().

>  
>  static int kallsyms_lookup_names(const char *name,
> @@ -201,15 +237,16 @@ static int kallsyms_lookup_names(const char *name,
>  {
>  	int ret;
>  	int low, mid, high;
> -	unsigned int seq, off;
> +	unsigned int off;
> +
> +	DO_ONCE_LITE(set_kallsyms_off_size);
>  
>  	low = 0;
>  	high = kallsyms_num_syms - 1;
>  
>  	while (low <= high) {
>  		mid = low + (high - low) / 2;
> -		seq = get_symbol_seq(mid);
> -		off = get_symbol_offset(seq);
> +		off = get_symbol_name_offset(mid);

[Severity: High]
Does DO_ONCE_LITE(set_kallsyms_off_size) allow a concurrent caller to
dereference NULL in get_symbol_name_offset() when kallsyms_off_size == 32?

In scripts/kallsyms.c:write_src(), only kallsyms_off24_of_names or
kallsyms_off32_of_names is emitted, and both are declared __weak in
kernel/kallsyms_internal.h:

extern struct { unsigned int v:24 __packed; } __packed kallsyms_off24_of_names[] __weak;
extern u32 kallsyms_off32_of_names[] __weak;

When kallsyms_off_size == 32, kallsyms_off24_of_names resolves to NULL,
while kallsyms_off_size_24 starts enabled via
DEFINE_STATIC_KEY_TRUE(kallsyms_off_size_24).

In include/linux/once_lite.h, __ONCE_LITE_IF() sets __already_done = true
before executing set_kallsyms_off_size() and does not wait for it to
finish:

		if (unlikely(__ret_cond) && unlikely(!__already_done)) {
			__already_done = true;
			__ret_once = true;
		}

If two CPUs call kallsyms_lookup_names() concurrently for the first time
while the first CPU is still inside set_kallsyms_off_size() ->
static_branch_disable(&kallsyms_off_size_24), the second CPU sees
__already_done == true and proceeds directly to
get_symbol_name_offset(mid). Since kallsyms_off_size_24 has not been
patched yet, get_symbol_name_offset() evaluates
kallsyms_off24_of_names[index].v and dereferences NULL.

[ ... ]

>
>
>
>
>

-- 
Sashiko AI review · https://sashiko.dev/#/patchset/20261018155206.132411-1-david.laight.linux@gmail.com?part=6

Re: [PATCH v2 next 11/15] kallsyms: scripts/kallsyms: Keep full expansion of tokens

[David Laight]

On Sun, 18 Oct 2026 16:00:02 +0000
sashiko-bot@kernel.org wrote:

> Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
> - [High] kallsyms: NULL token_table[].str passed to printf() in write_src()
> --
> 
> commit b464b94e58431a4ad1ec112c739d63f16547b8f2
> Author: David Laight <david.laight.linux@gmail.com>
> 
> kallsyms: scripts/kallsyms: Keep full expansion of tokens
> 
> This commit stores the full NUL-terminated string expansion for each token
> in token_table[] as tokens are allocated, avoiding recursive symbol
> expansions later.
> 
> > diff --git a/scripts/kallsyms.c b/scripts/kallsyms.c
> > index 5603b2a6c77bd..9e1bc0fdaa9f2 100644
> > --- a/scripts/kallsyms.c
> > +++ b/scripts/kallsyms.c  
> [ ... ]
> > @@ -415,9 +403,8 @@ static void write_src(void)
> >  	off = 0;
> >  	for (i = 0; i < 256; i++) {
> >  		best_idx[i] = off;
> > -		expand_symbol(token_table[i].ch, token_table[i].len, buf);
> > -		printf("\t.asciz\t\"%s\"\n", buf);
> > -		off += strlen(buf) + 1;
> > +		off += token_table[i].len + 1;
> > +		printf("\t.asciz\t\"%s\"\n", token_table[i].str);
> >  	}
> >  	printf(".size kallsyms_token_table, . - kallsyms_token_table\n");
> >  	printf("\n");  
> 
> [Severity: High]
> Can token_table[i].str be NULL here when some token slots remain unused?

Probably :-(

> In insert_real_symbols_in_table(), token_table[i].str is only allocated for
> character codes present in the input symbols:
> 
> 	for (i = 0; i <= 255; i++) {
> 		if (!token_table[i].len)
> 			continue;
> 		token_table[i].str = xmalloc(2);
> 		token_table[i].str[0] = i;
> 		token_table[i].str[1] = 0;
> 	}
> 
> Then in optimize_result(), the loop stops early as soon as find_best_token()
> finds no remaining token pairs with positive profit:
> 
> 		best = find_best_token();
> 		if (best < 0)
> 			break;
> 
> Any remaining unused entries in token_table[] keep len == 0 and str == NULL.
> During pass 0 in scripts/link-vmlinux.sh, kallsyms is invoked on an empty
> symbol file (.tmp_vmlinux0.syms), leaving all 256 token_table[i].str
> pointers as NULL.
> 
> Previously, expand_symbol() wrote an empty string into buf when len was 0.
> Passing a NULL token_table[i].str to printf("%s") in write_src() causes a
> segmentation fault on non-glibc hosts (such as musl) or prints "(null)" on
> glibc hosts while advancing off by only 1 byte, which corrupts
> kallsyms_token_table and best_idx[].

For glibc builds it won't really matter - that corrupt file doesn't matter
and in reality there are always enough symbols.

I'll add ?: "" to the code.

David

Re: [PATCH 14/15] kallsyms: scripts/kallsyms: Reduce the output file size

[David Laight]

On Sun, 18 Oct 2026 16:05:41 +0000
sashiko-bot@kernel.org wrote:

> Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
> - [High] kallsyms: NULL dereference and offset mismatch in write_src() on unused tokens
> --
> 
> commit 20102d6e3b81d88a59f6ac3b9732c8a7b28d3f98
> Author: David Laight <david.laight.linux@gmail.com>
> 
> kallsyms: scripts/kallsyms: Reduce the output file size
> 
> This commit reduces the size of the assembly output generated by
> scripts/kallsyms by formatting byte values in decimal, packing multiple
> values per line for kallsyms_token_index and kallsyms_markers, moving the
> token tables first, and replacing duplicate symbol name comments with
> symbol offsets.
> 
> > diff --git a/scripts/kallsyms.c b/scripts/kallsyms.c
> > index 189fb50ec8c58..8576fe6ad90b7 100644
> > --- a/scripts/kallsyms.c
> > +++ b/scripts/kallsyms.c
> > @@ -350,6 +350,30 @@ static void write_src(void)
> >  	struct sym_entry *se;
> >  
> >  	printf("\t.section .rodata, \"a\"\n");
> > +	printf("\n");
> > +
> > +	output_label("kallsyms_token_table");
> > +	off = 0;
> > +	for (i = 0; i < 256; i++) {
> > +		best_idx[i] = off;
> > +		off += token_table[i].len + 1;
> > +		printf("\t.asciz\t\"%s\"\t/* %u: %u */\n",
> > +		       token_table[i].str, i, token_table[i].refs);
> > +	}  
> 
> [Severity: High]
> Can token_table[i].str be NULL here when fewer than 256 tokens are
> populated?

This is the same issue it found earlier in patch 11.

David

> 
> During pass 0 of a CONFIG_KALLSYMS=y build, scripts/link-vmlinux.sh runs
> scripts/kallsyms on an empty symbol file:
> 
> scripts/link-vmlinux.sh:kallsyms_step() {
>     ...
>     if is_enabled CONFIG_KALLSYMS; then
>         true > .tmp_vmlinux0.syms
>         kallsyms .tmp_vmlinux0.syms .tmp_vmlinux0.kallsyms
>     fi
>     ...
> }
> 
> When symbol_cnt is 0 (or whenever the input symbols do not populate all
> 256 entries), insert_real_symbols_in_table() leaves token_table[i].str as
> NULL and token_table[i].len as 0 for unreferenced tokens:
> 
> scripts/kallsyms.c:insert_real_symbols_in_table() {
>     ...
>     for (i = 0; i <= 255; i++) {
>         if (!token_table[i].refs)
>             continue;
>         token_table[i].len = 1;
>         token_table[i].str = xmalloc(2);
>         token_table[i].str[0] = i;
>         token_table[i].str[1] = 0;
>     }
> }
> 
> In optimize_result(), find_best_token() then returns -1 and breaks out of
> the loop before filling the remaining unused tokens.
> 
> When write_src() passes token_table[i].str to printf("%s"), isn't that
> undefined behavior that segfaults on non-glibc hosts (such as musl)? Also,
> on glibc hosts where printf("%s", NULL) outputs "(null)" (7 bytes
> including the NUL terminator in .asciz), off is only incremented by
> token_table[i].len + 1 (1 byte), which mismatches the actual size emitted
> into kallsyms_token_table and corrupts the offsets recorded in best_idx[].
> 
> [ ... ]
> 

Re: [PATCH v2 next 06/15] kallsyms: Optimise symbol name search

[David Laight]

On Sun, 18 Oct 2026 16:15:56 +0000
sashiko-bot@kernel.org wrote:

> Thank you for your contribution! Sashiko AI review found 2 potential issue(s) to consider:
> - [High] kallsyms: race in set_kallsyms_off_size() causes NULL dereference
> - [High] kallsyms: set_kallsyms_off_size() sleeps in atomic context
> --
> 
> commit d36232e927821c82911022ce5bae7cb3de465edd
> Author: David Laight <david.laight.linux@gmail.com>
> 
> kallsyms: Optimise symbol name search
> 
> This commit optimizes symbol name lookups by indexing the compressed
> names table directly instead of the array of symbol values. It supports
> both 24-bit and 32-bit offset tables, selecting between them using a
> static branch initialized on the first symbol lookup.
> 
> > diff --git a/kernel/kallsyms.c b/kernel/kallsyms.c
> > index d18d78e626db2..31451feac8221 100644
> > --- a/kernel/kallsyms.c
> > +++ b/kernel/kallsyms.c  
> 
> [ ... ]
> 
> > @@ -185,14 +216,19 @@ unsigned long kallsyms_sym_address(int idx)
> >  	return (unsigned long)offset_to_ptr(kallsyms_offsets + idx);
> >  }
> >  
> > -static unsigned int get_symbol_seq(int index)
> > -{
> > -	unsigned int i, seq = 0;
> > +static DEFINE_STATIC_KEY_TRUE(kallsyms_off_size_24);
> >  
> > -	for (i = 0; i < 3; i++)
> > -		seq = (seq << 8) | kallsyms_seqs_of_names[3 * index + i];
> > +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 seq;
> > +static void set_kallsyms_off_size(void)
> > +{
> > +	if (kallsyms_off_size != 24)
> > +		static_branch_disable(&kallsyms_off_size_24);
> >  }  
> 
> [Severity: High]
> Can calling static_branch_disable() in set_kallsyms_off_size() sleep in
> an atomic or early-boot context when kallsyms_off_size != 24?

Any suggestions on how to get the static branch set early enough?

...
> 
> [Severity: High]
> Does DO_ONCE_LITE(set_kallsyms_off_size) allow a concurrent caller to
> dereference NULL in get_symbol_name_offset() when kallsyms_off_size == 32?

I should have just open-code the 'do once'.
It doesn't matter if it is called twice.

But it looks as though I can't patch the code from there anyway.

David

Re: [PATCH 15/15] kallsyms: scripts/kallsyms: Improve compression by about 2%

[David Laight]

On Sun, 18 Oct 2026 16:05:10 +0000
sashiko-bot@kernel.org wrote:

> Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
> - [Medium] kallsyms: infinite loop in optimize_result() on self-overlapping token pairs
> --
> 
> commit 36121744ef0b7fd951486247d0297f67eaca31d8
> Author: David Laight <david.laight.linux@gmail.com>
> 
> kallsyms: scripts/kallsyms: Improve compression by about 2%
> 
> This commit improves kallsyms compression by expanding infrequently used
> merged tokens back into their original constituent pairs when no unused
> tokens remain, freeing slots for more profitable token pairs.
> 
> > diff --git a/scripts/kallsyms.c b/scripts/kallsyms.c
> > index 8576fe6ad90b7..9dbd7c85eec1e 100644
> > --- a/scripts/kallsyms.c
> > +++ b/scripts/kallsyms.c  
...
> > +static int split_token(unsigned int profit)
> > +{
> > +	struct token_table *tt, *left, *right;
> > +	unsigned int i;
> > +	int best = -1;
> > +
> > +	for (i = 0; i < 256; i++) {
> > +		tt = token_table + i;
> > +
> > +		if (tt->len == 1 || tt->refs >= profit)
> > +			continue;
> > +
> > +		/* Ignore tokens where the original parts have be reused */
> > +		left = &token_table[LEFT(tt->pair)];
> > +		right = &token_table[RIGHT(tt->pair)];
> > +		if (tt->len != left->len + right->len ||
> > +		    memcmp(tt->str, left->str, left->len) ||
> > +		    memcmp(tt->str + left->len, right->str, right->len))
> > +			continue;
> > +
> > +		best = i;
> > +		if (tt->refs == 2)
> > +			break;
> > +		profit = tt->refs;
> > +	}
> > +	if (best < 0)
> > +		return -1;
> > +
> > +	uncompress_symbols(token_table[best].pair, best);
> > +
> > +	return best;
> > +}
> > +
>...
> 
> [Severity: Medium]
> Can optimize_result() enter an infinite loop when find_best_token() selects a
> homogeneous token pair best = PAIR(x, x) that overlaps with itself in runs of
> 3 or more identical tokens?
> 
> For a homogeneous pair PAIR(x, x) where LEFT(best) == RIGHT(best),
> learn_symbol() and uncompress_symbols() count every adjacent pair, so a run
> of [x, x, x] increments token_profit[PAIR(x, x)] by 2. However, when
> compress_symbols(PAIR(x, x), i) replaces the first pair to form [i, x], it
> calls:
> 
>     adjust_profit(RIGHT(token_pair), idx, p[2], p[2]);
> 
> which is adjust_profit(x, i, x, x), decrementing token_profit[PAIR(x, x)] by
> 1 for each triple. As a result, compress_symbols() performs fewer
> substitutions (refs) than the initial token_profit[best] passed to
> split_token().

(Well done for spotting that one - it got me confused at one point.
It is one reason why calling it 'profit' (historical name) is wrong.)

In theory maybe, in practise no.
There are two characters that get repeated more than twice (and I don't
remember seeing any repeated tokens.)
They are '_' and 'm'; "__" is by far the most common pair, "mmm" appears
in _commmon_choices_show() in drivers/acpi/platform_profile.c
(and looks like a typo).
A token is allocated to "mm" but there are enough different uses that
it isn't going to get split.

I will put a check in the next version.
(probably just avoiding splitting XX.)

David