[PATCH v3 next 00/13] kallsyms: optimise symbol search by name

[PATCH v3 next 00/13] 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.

The technical content of these patches is the same as v2 except for an
additional compression optimisation in the final patch.
However rebasing onto 7.4-rc1 took some effort due to changes to
sripts/kallsyms.c.

Patch 1 is a stack buffer overrun - but in a program run during the build
    so is isn't that improtant.
Patch 2 improves the error reporting added for 7.4-rc1 and adds some timestamp
    output to time the different parts of the code.
Patch 3 obtains the target endianness from the elf file.
    Being run-time doesn't make any significant difference.
    (v2 extracted it from the kernel makefile.)
Patch 4 is, in some sense, a conditional revert of 83da9f3197e5 (output binary
    data speed output and kallsyms assembly).
    While the binary output does speed things up it makes debugging impossible.
    Change it to be a command line option.
    - Output the token table first and always in text - it is small.
    - Use a fixed format and fwrite() for the symbol values avoid printf.
      Reduces the time to output the symbol table from 5.8ms to 2.1ms
      (on my system, with my kernel, today).
    - The marker array is now written to bin.out in host order.
    Contains some of the changes from patch 14, but the size of the out.S
    file matters less.
Patch 5 (formally #2) is a fix to the selftest.
Patch 6 (formally #3) is a big update to the selftest output to make
    it less affected by interrupts (etc) and visually more obvious.
    Includes a very long symbol to check their handling.
The old patch 4 (error reporting) is merged elsewhere.
Patch 7 (formally #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 8 (merged #6 and #7) improve the search by name code.
    Indexing the list of names (not the values) speeds it up ~12 times.
    Marking duplicate symbols improves things as well, especially for
    symbols that appear 1000s of times.
Patches 9 (merged #8 and #9) make the 'marker density' a kernel build option
    and changes the default from 1:256 to 1:64 (one bit for two symbols).
    This change gives a 33% improvement on top of that from patch 8.
The old patch 10 is dropped.
Patch 10 (technically the same as 11, but rewritten) avoids the recursive
    expansion of compressed data. It speeds up the compression phase
    by about 17ms in 100ms.
Patch 11 (formally #12) speeds up the compression code by about 35ms
    in 100ms, it will be more for kernels with a lot of long symbol names.
Patch 12 (formally #13) reuses unused compression tokens to improve
    the compression ratio.
    (Patch 11 means they don't have to be kept to expand tokens.)
The old patch 14 is dropped, some parts went into patch 3.
Patch 13 (formally #15) improves the compression ratio by splitting little
    used tokens so that they can be used for more common token pairs.
    For v3 this includes tokens for three single characters as well
    as those where both the original tokens are still valid.
    This improves the compression ratio (for the test kernel) from 53.35%
    to 50.05%, so a 6% reduction in the datasize.

Some test output (TL;DR):

Timestamps from scrpts/kallsyms (typical values - they vary between runs):
Initial (7.4-rc1 with part of patch 4 applied):
kallsyms: stamp read elf 29.6 ms
kallsyms: stamp shrink table 0.1 ms
kallsyms: stamp sort symbols 2.2 ms
kallsyms: stamp build initial token table 10.9 ms
kallsyms: stamp insert real symbols in table 1.9 ms
kallsyms: stamp optimize result 109.5 ms
kallsyms: stamp write compressed names 11.3 ms
kallsyms: stamp write token table 0.0 ms
kallsyms: stamp write symbol values 5.8 ms
kallsyms: stamp sort by name 18.8 ms
kallsyms: stamp write name index 1.7 ms

Patch 4 (make binary data optional) changes:
kallsyms: stamp write compressed names 12.6 ms   +1.5ms
kallsyms: stamp write symbol values 2.1 ms       -3.8ms
The +1.5 comes from logic changes, the -3.8 by using fwrite() not printf().
(The all-text output is 50+ms slower overall.)

Patch 10 (fully expand tokens) changes:
kallsyms: stamp optimize result 98.2 ms           -15ms
kallsyms: stamp write compressed names 10.1 ms     -2ms 
The changes from removing the number of short memcpy() and (probably)
changing the argument to compress_symbols() from 'char *' to int.
(In fact replacing memcpy() by a byte copy loop saves ~1ms.)

Patch 11 (Optimise compress symbols) is the big one:
kallsyms: stamp optimize result 64.5 ms           -34ms
In effect that reduces the compression from O(n^2) to O(n) in the
length of the symbol.

Patches 12 and 13 find more things to compress and make
it ~13ms slower.

One obvious change that would improve things would be to throw some
(more) extra memory at the symbol table and keep the original symbol
name. That would remove all the calls to expand_symbol() and make
the loop that outputs the compressed symbols trivial.
Potentially it would let the 'sort by name' be done be a separate thread.
I didn't look at why 'read elf' takes ~30ms, nor have I timed the
old code from 7.3.

kallsyms_selftest output (run in a userspace wrapper).
(Unchanged from v2, but the kernel code changes are minimal.)
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().

Performance changes
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.

The times go down from:
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)

to:
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)

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 *:
	|      *****
	|     *******
	|    ********
	|    *********
	|    *********
	|    *********
	|   ***********
	|  ******************                               *
(That 'slowest' time looks like a lie.)

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   |
 ---------------------------------------------------------
kernel code unchanged.

Final version.
Improves the compression ratio again.
(the v3 version is slightly better - 50.05%)
 ---------------------------------------------------------
| nr_symbols | compressed size | original size | ratio(%) |
|---------------------------------------------------------|
|     123312 |       1505184   |      2969490  |  50.68   |
 ---------------------------------------------------------
kernel code unchanged again.


David Laight (12):
  scripts/kallsyms: Avoid overrunning on-stack buffer
  scripts/kallsyms: Improve error reporting
  scripts/elf-parse: add elf_map_big_endian() helper
  scripts/kallsyms: make use of binary data output optional
  kallsyms: Fix selftest startup delay
  kallsyms: Improve selftest test_perf_kallsyms_lookup_name() output
  kallsyms: Optimise symbol name search
  kallsyms: Add a kernel parameter to change the kallsyms_markers[]
    density
  scripts/kallsyms: Keep full expansion of tokens
  scripts/kallsyms: Optimise compress_symbols()
  scripts/kallsyms: Reuse tokens that have no references
  scripts/kallsyms: Reuse little-used compression tokens

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

 init/Kconfig               |  19 +
 kernel/kallsyms.c          | 262 ++++++----
 kernel/kallsyms_internal.h |   8 +-
 kernel/kallsyms_selftest.c | 173 +++++--
 scripts/elf-parse.c        |  13 +-
 scripts/elf-parse.h        |   5 +-
 scripts/kallsyms-sysmap.c  |   1 +
 scripts/kallsyms.c         | 957 ++++++++++++++++++++++++++-----------
 scripts/kallsyms.h         |   1 +
 scripts/link-vmlinux.sh    |  13 +-
 10 files changed, 1034 insertions(+), 418 deletions(-)

-- 
2.39.5

[PATCH v3 next 01/13] scripts/kallsyms: 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>
---

Unchanged from v2.

 scripts/kallsyms.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/scripts/kallsyms.c b/scripts/kallsyms.c
index ecb444078c1c..140e888bf713 100644
--- a/scripts/kallsyms.c
+++ b/scripts/kallsyms.c
@@ -398,7 +398,7 @@ static void write_src(FILE *out_bin_file, const char *out_bin_name)
 	unsigned int best_idx[256];
 	unsigned int *markers, markers_cnt;
 	long bin_start;
-	char buf[KSYM_NAME_LEN];
+	char buf[1 + KSYM_NAME_LEN];
 
 	printf("\t.section .rodata, \"a\"\n");
 
-- 
2.39.5

[PATCH v3 next 02/13] scripts/kallsyms: Improve error reporting

[David Laight]

Report fatal errors with err() not perror().

Using err/errx() adds the program name to the output and allows rather
more descriptive errors.

Add fflush() calls before checking ferror(), use errx() for these
since errno isn't valid.

Use a single error check for the length of the compressed symbol.
It must be shorter than the original length - but that isn't kept,
so check against KSYM_NAME_LEN (allowing 1 for the symbol type).

Move the usage() function to just before main().
Remove the usage text from the top of file comment and put the info
into the usage() output.
Removes the need to keep two copies of the same text in line with
the actual code.

Add a --verbose option that outputs some timestamps.

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

New patch for v3, subsumes the old patch 4.

 scripts/kallsyms.c | 146 +++++++++++++++++++++++++++------------------
 1 file changed, 88 insertions(+), 58 deletions(-)

diff --git a/scripts/kallsyms.c b/scripts/kallsyms.c
index 140e888bf713..aa3a8ec83fbb 100644
--- a/scripts/kallsyms.c
+++ b/scripts/kallsyms.c
@@ -5,15 +5,7 @@
  * This software may be used and distributed according to the terms
  * of the GNU General Public License, incorporated herein by reference.
  *
- * Usage: kallsyms [--all-symbols] [--pc-relative] [--sysmap=out.map] in out.bin > out.S
- *        kallsyms --sysmap=out.map in
- *
- *      in is vmlinux; an empty file stands for the first link, which has no
- *  symbols yet, and gives an empty table. --sysmap also writes the symbols
- *  in System.map format.
- *
- *      The byte tables go to out.bin and are pulled into out.S with .incbin;
- *  wider tables stay assembler source for endianness and relocations.
+ * Generate asm source containing a compressed copy of the kernel symbol table.
  *
  *      Table compression uses all the unused char codes on the symbols and
  *  maps these to the most used substrings (tokens). For instance, it might
@@ -26,11 +18,13 @@
  *
  */
 
+#include <err.h>
 #include <getopt.h>
 #include <stdbool.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
+#include <time.h>
 #include <ctype.h>
 #include <limits.h>
 #include <sys/stat.h>
@@ -64,6 +58,7 @@ static struct sym_entry **table;
 static unsigned int table_size, table_cnt;
 static int all_symbols;
 static int pc_relative;
+static int verbose;
 
 /* A dynamic array of symbols, encoded by symbol index. */
 struct sym_arr {
@@ -81,6 +76,23 @@ static struct sym_arr token_syms[NR_TOKENS];
 static unsigned char best_table[256][2];
 static unsigned char best_table_len[256];
 
+static void stamp(const char *where)
+{
+	static unsigned long long prev;
+	struct timespec now;
+	unsigned long long delta;
+
+	if (!verbose)
+		return;
+
+	clock_gettime(CLOCK_MONOTONIC, &now);
+	delta = now.tv_sec * 10000ull + now.tv_nsec / 100000 - prev;
+	prev += delta;
+	if (where)
+		fprintf(stderr, "kallsyms: stamp %s %llu.%llu ms\n",
+			where, delta / 10, delta % 10);
+}
+
 static unsigned int sym_arr_last(const struct sym_arr *arr)
 {
 	return arr->cnt ? arr->sym_indexes[arr->cnt - 1] : UINT_MAX;
@@ -110,14 +122,6 @@ static void sym_arr_free(struct sym_arr *arr)
 	arr->cap = 0;
 }
 
-static void usage(void)
-{
-	fprintf(stderr, "Usage: kallsyms [--all-symbols] [--pc-relative] [--sysmap=out.map]\n"
-			"                in out.bin > out.S\n"
-			"       kallsyms --sysmap=out.map vmlinux\n");
-	exit(1);
-}
-
 static char *sym_entry_name(const struct sym_entry *s)
 {
 	return (char *)s->sym + 1;
@@ -278,10 +282,8 @@ static bool file_is_empty(const char *path)
 {
 	struct stat st;
 
-	if (stat(path, &st)) {
-		perror(path);
-		exit(EXIT_FAILURE);
-	}
+	if (stat(path, &st))
+		err(EXIT_FAILURE, "stat(%s) failed", path);
 
 	return st.st_size == 0;
 }
@@ -324,10 +326,8 @@ static long bin_pos(FILE *file)
 {
 	const long pos = ftell(file);
 
-	if (pos < 0) {
-		perror("kallsyms: ftell");
-		exit(EXIT_FAILURE);
-	}
+	if (pos < 0)
+		err(EXIT_FAILURE, "ftell on bin.out file failed");
 
 	return pos;
 }
@@ -419,19 +419,10 @@ static void write_src(FILE *out_bin_file, const char *out_bin_name)
 			markers[i >> 8] = off;
 		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);
-		}
-
-		/* 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);
-		}
+		/* The length must be less than that of the original symbol. */
+		if (!table[i]->len || table[i]->len > KSYM_NAME_LEN)
+			errx(EXIT_FAILURE, "symbol %d has corrupt compressed length %d",
+			     i, table[i]->len);
 
 		/* Encode length with ULEB128. */
 		if (table[i]->len <= 0x7F) {
@@ -465,6 +456,8 @@ static void write_src(FILE *out_bin_file, const char *out_bin_name)
 
 	free(markers);
 
+	stamp("write compressed names");
+
 	output_label("kallsyms_token_table");
 	bin_start = bin_pos(out_bin_file);
 	off = 0;
@@ -483,6 +476,8 @@ static void write_src(FILE *out_bin_file, const char *out_bin_name)
 		printf("\t.short\t%d\n", best_idx[i]);
 	printf("\n");
 
+	stamp("write token table");
+
 	output_label("kallsyms_offsets");
 
 	for (i = 0; i < table_cnt; i++) {
@@ -490,7 +485,7 @@ static void write_src(FILE *out_bin_file, const char *out_bin_name)
 			long long offset = table[i]->addr - _text;
 
 			if (offset < INT_MIN || offset > INT_MAX) {
-				fprintf(stderr, "kallsyms failure: "
+				errx(EXIT_FAILURE, "kallsyms failure: "
 					"relative symbol value %#llx out of range\n",
 					table[i]->addr);
 				exit(EXIT_FAILURE);
@@ -505,6 +500,8 @@ static void write_src(FILE *out_bin_file, const char *out_bin_name)
 	printf(".size kallsyms_offsets, . - kallsyms_offsets\n");
 	printf("\n");
 
+	stamp("write symbol values");
+
 	sort_symbols_by_name();
 	output_label("kallsyms_seqs_of_names");
 	bin_start = bin_pos(out_bin_file);
@@ -515,6 +512,8 @@ static void write_src(FILE *out_bin_file, const char *out_bin_name)
 	}
 	write_incbin(out_bin_name, bin_start, bin_pos(out_bin_file));
 	printf("\n");
+
+	stamp("write name index");
 }
 
 static unsigned int token_index(unsigned char first, unsigned char second)
@@ -742,10 +741,13 @@ static void insert_real_symbols_in_table(void)
 static void optimize_token_table(void)
 {
 	build_initial_token_table();
+	stamp("build initial token table");
 
 	insert_real_symbols_in_table();
+	stamp("insert real symbols in table");
 
 	optimize_result();
+	stamp("optimize result");
 }
 
 /* guess for "linker script provide" symbol */
@@ -822,6 +824,25 @@ static void sort_symbols(void)
 	qsort(table, table_cnt, sizeof(table[0]), compare_symbols);
 }
 
+static void usage(void)
+{
+	fprintf(stderr,
+		"Usage: kallsyms [options] vmlinux out.bin > out.S\n"
+		"       kallsyms --sysmap=out.map vmlinux\n"
+		"           --all-symbols     Include all local symbols\n"
+		"           --pc-relative     Output symbols offsets\n"
+		"           --sysmap=out.map  Text map file\n"
+		"           --verbose         Extra diagnostic output\n"
+		"           vmlinux: File to read, can be empty\n"
+		"           out.S: Assembler source output file.\n"
+		"           out.bin: Binary data; included in out.S using .incbin\n"
+		"       In the second form only the symbol table out.map is generated,\n"
+		"       the compressed data is not generated.\n"
+		"       --pc-relative is required for all 64 bit kernels and relocatable\n"
+		"       32 bit ones.\n");
+	exit(EXIT_FAILURE);
+}
+
 int main(int argc, char **argv)
 {
 	const char *in, *sysmap = NULL, *out_bin_name;
@@ -832,6 +853,7 @@ int main(int argc, char **argv)
 			{"all-symbols",     no_argument, &all_symbols,     1},
 			{"pc-relative",     no_argument, &pc_relative,     1},
 			{"sysmap",    required_argument, NULL,           's'},
+			{"verbose",         no_argument, &verbose,         1},
 			{},
 		};
 
@@ -845,49 +867,57 @@ int main(int argc, char **argv)
 			usage();
 	}
 
+	stamp(NULL);
+
 	if (optind + 2 != argc && !(sysmap && optind + 1 == argc))
 		usage();
 
 	in = argv[optind];
 	if (sysmap) {
 		sysmap_out = fopen(sysmap, "w");
-		if (!sysmap_out) {
-			perror(sysmap);
-			exit(EXIT_FAILURE);
-		}
+		if (!sysmap_out)
+			err(EXIT_FAILURE, "failed to open sysmap output file %s", sysmap);
 	}
 
 	if (optind + 1 == argc) {
 		read_elf(in, sysmap_out);
-		if (ferror(sysmap_out) || fclose(sysmap_out)) {
-			perror(sysmap);
-			exit(EXIT_FAILURE);
-		}
+		fflush(sysmap_out);
+		if (ferror(sysmap_out) || fclose(sysmap_out))
+			errx(EXIT_FAILURE, "error writing sysmap file %s", sysmap);
 		return 0;
 	}
 
 	out_bin_name = argv[optind + 1];
 	out_bin_file = fopen(out_bin_name, "w");
-	if (!out_bin_file) {
-		perror(out_bin_name);
-		exit(EXIT_FAILURE);
-	}
+	if (!out_bin_file)
+		err(EXIT_FAILURE, "failed to open nin.out file %s", out_bin_name);
 
 	read_elf(in, sysmap_out);
-	if (sysmap_out && (ferror(sysmap_out) || fclose(sysmap_out))) {
-		perror(sysmap);
-		exit(EXIT_FAILURE);
+	if (sysmap_out) {
+		fflush(sysmap_out);
+		if (ferror(sysmap_out) || fclose(sysmap_out))
+			errx(EXIT_FAILURE, "error writing sysmap file %s", sysmap);
 	}
+	stamp("read elf");
+
 	shrink_table();
+	stamp("shrink table");
+
 	sort_symbols();
+	stamp("sort symbols");
+
 	optimize_token_table();
+
 	write_src(out_bin_file, out_bin_name);
 
 	/* Write errors are latched in the stream, so one check at the end covers them all. */
-	if (ferror(out_bin_file) || fclose(out_bin_file)) {
-		perror(out_bin_name);
-		exit(EXIT_FAILURE);
-	}
+	fflush(out_bin_file);
+	if (ferror(out_bin_file) || fclose(out_bin_file))
+		errx(EXIT_FAILURE, "error writing out.bin file %s", out_bin_name);
+
+	fflush(stdout);
+	if (ferror(stdout))
+		errx(EXIT_FAILURE, "error writing output file");
 
 	return 0;
 }
-- 
2.39.5

[PATCH v3 next 03/13] scripts/elf-parse: add elf_map_big_endian() helper

[David Laight]

Returns 1 for big-endian, 0 for little-endian.
While the tools are compiled for a specific architecture the target
endianness isn't easily obtainable.

Use 'const Elf_Ehdr *ehdr' for the argument, change the argument of the
very similar elf_map_machine() and elf_map_long_size() to be the same.
All the callers either pass the correct type or 'void *'.

Will be used by kallsyms.

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

New patch for v3.

 scripts/elf-parse.c | 13 +++++++------
 scripts/elf-parse.h |  5 +++--
 2 files changed, 10 insertions(+), 8 deletions(-)

diff --git a/scripts/elf-parse.c b/scripts/elf-parse.c
index ce1c2a670244..24d99ab9adc0 100644
--- a/scripts/elf-parse.c
+++ b/scripts/elf-parse.c
@@ -170,20 +170,21 @@ static int elf_parse(const char *fname, void *addr, uint32_t types)
 	return 0;
 }
 
-int elf_map_machine(void *addr)
+int elf_map_machine(const Elf_Ehdr *ehdr)
 {
-	Elf_Ehdr *ehdr = addr;
-
 	return elf_parser.r2(&ehdr->e32.e_machine);
 }
 
-int elf_map_long_size(void *addr)
+int elf_map_long_size(const Elf_Ehdr *ehdr)
 {
-	Elf_Ehdr *ehdr = addr;
-
 	return ehdr->e32.e_ident[EI_CLASS] == ELFCLASS32 ? 4 : 8;
 }
 
+int elf_map_big_endian(const Elf_Ehdr *ehdr)
+{
+	return ehdr->e32.e_ident[EI_DATA] ==  ELFDATA2MSB;
+}
+
 static void *__elf_map(char const *fname, size_t *size, uint32_t types,
 		       bool writable)
 {
diff --git a/scripts/elf-parse.h b/scripts/elf-parse.h
index c5ad754da254..72c78da5cb3a 100644
--- a/scripts/elf-parse.h
+++ b/scripts/elf-parse.h
@@ -318,8 +318,9 @@ static inline void w8le(uint64_t val, uint64_t *x)
 void *elf_map(char const *fname, size_t *size, uint32_t types);
 void *elf_map_ro(char const *fname, size_t *size, uint32_t types);
 void elf_unmap(void *addr, size_t size);
-int elf_map_machine(void *addr);
-int elf_map_long_size(void *addr);
+int elf_map_machine(const Elf_Ehdr *ehdr);
+int elf_map_long_size(const Elf_Ehdr *ehdr);
+int elf_map_big_endian(const Elf_Ehdr *ehdr);
 
 /* A mapped file with its section headers, section names and symbol table. */
 struct elf_file {
-- 
2.39.5

[PATCH v3 next 04/13] scripts/kallsyms: make use of binary data output optional

[David Laight]

While writing some of the output in binary (and using the .incbin directive
to get the assembler to read it) speeds up normal kernel builds, it makes
debugging kallsyms almost impossible.

Change the command line processing so that the out.bin file is optional,
if absent everything is written to out.S (at is was prior to 83da9f3197e5).

To make the command line parsing possible the argument to --sysmap is made
optional, if absent the sysmap output is written to stdout and the
compression code skipped.

Instead of requiring an empty input file when generating .tmp_vmlinux0.kallsyms
make the input file itself optional.

There is no need to use ftell() to find the offset in the out.bin file
(and worry about it failing), the code knows exactly how many bytes have
been written to the file - so use that instead.

To help anyone who ends up looking an hexdump of out.bin, add a text header
and 16 byte align each table.
The size is noise and it doesn't affect the assembler.

Extract the target endianness from the elf input file and use it to write
the 'markers' table array to the out.bin file.
Use fwrite() for all the symbols entries - faster than printf().

Reduces the time on my system for:
scripts/kallsyms --all-symbols --pc-relative .tmp_vmlinux2 /dev/null >/dev/null
from 194 ms to 185ms.

Output the token table first and always to out.S (it doesn't take long).
This makes the out.S file diffable even with minor changes.

The re-instated printf() use %u for bytes, shorter than 0x%02x and just
as good since the data isn't really a table with columns.
But don't worry too much about the file size when the binary file isn't
specified.

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

New patch for v3.
Makes the ols patch 14 redundant.

 scripts/kallsyms-sysmap.c |   1 +
 scripts/kallsyms.c        | 293 ++++++++++++++++++++++++--------------
 scripts/kallsyms.h        |   1 +
 scripts/link-vmlinux.sh   |   7 +-
 4 files changed, 191 insertions(+), 111 deletions(-)

diff --git a/scripts/kallsyms-sysmap.c b/scripts/kallsyms-sysmap.c
index a482968eba51..6897eddd724f 100644
--- a/scripts/kallsyms-sysmap.c
+++ b/scripts/kallsyms-sysmap.c
@@ -224,6 +224,7 @@ struct sysmap *sysmap_read(const char *path)
 		exit(EXIT_FAILURE);
 	map->syms = elf_read_symbols(&map->elf, &map->nr_syms);
 	map->addr_width = elf_map_long_size(map->elf.base) * 2;
+	map->big_endian = elf_map_big_endian(map->elf.base);
 
 	return map;
 }
diff --git a/scripts/kallsyms.c b/scripts/kallsyms.c
index aa3a8ec83fbb..74db751600b4 100644
--- a/scripts/kallsyms.c
+++ b/scripts/kallsyms.c
@@ -60,6 +60,11 @@ static int all_symbols;
 static int pc_relative;
 static int verbose;
 
+static int big_endian;	/* Extracted from the elf file */
+
+static const char *out_bin_name;
+static FILE *out_bin_file;
+
 /* A dynamic array of symbols, encoded by symbol index. */
 struct sym_arr {
 	unsigned int *sym_indexes;
@@ -278,26 +283,16 @@ static void add_table_entry(struct sym_entry *sym)
 	table[table_cnt++] = sym;
 }
 
-static bool file_is_empty(const char *path)
-{
-	struct stat st;
-
-	if (stat(path, &st))
-		err(EXIT_FAILURE, "stat(%s) failed", path);
-
-	return st.st_size == 0;
-}
-
 /*
- * Read the symbols from vmlinux, writing System.map if asked to. The first
- * link has no symbols yet: an empty file gives an empty table.
+ * Read the symbols from vmlinux, writing System.map if asked to.
+ * The first link has no symbols yet: an absent file gives an empty table.
  */
 static void read_elf(const char *path, FILE *sysmap_out)
 {
 	struct sysmap *map;
 	size_t i;
 
-	if (file_is_empty(path))
+	if (!path || !*path)
 		return;
 
 	map = sysmap_read(path);
@@ -312,6 +307,8 @@ static void read_elf(const char *path, FILE *sysmap_out)
 			add_table_entry(sym);
 	}
 
+	big_endian = map->big_endian;
+
 	sysmap_free(map);
 }
 
@@ -322,22 +319,34 @@ static void output_label(const char *label)
 	printf("%s:\n", label);
 }
 
-static long bin_pos(FILE *file)
+static void write_incbin_header(const char *msg, unsigned long *bin_offset)
 {
-	const long pos = ftell(file);
+	static unsigned char marker[18] = "################" "#";
+	static unsigned char nulls[16];
+	unsigned long off;
 
-	if (pos < 0)
-		err(EXIT_FAILURE, "ftell on bin.out file failed");
+	if (!out_bin_file)
+		return;
 
-	return pos;
+	off = *bin_offset;
+
+	/* 16 byte align and add header for diagnostic hexdumps */
+	off += fwrite(nulls, 1, -off & 15, out_bin_file);
+	off += fwrite(marker, 1, 16 + 2, out_bin_file);
+	off += fwrite(msg, 1, strlen(msg), out_bin_file);
+	off += fwrite(nulls, 1, -off & 15, out_bin_file);
+	off += fwrite(marker, 1, 16, out_bin_file);
+
+	*bin_offset = off;
 }
 
-static void write_incbin(const char *filename, long start, long end)
+static void write_incbin(unsigned long *bin_offset, unsigned long size)
 {
-	if (start >= end)
+	if (!out_bin_name || !size)
 		return;
 
-	printf("\t.incbin \"%s\", %ld, %ld\n", filename, start, end - start);
+	printf("\t.incbin \"%s\", %ld, %ld\n", out_bin_name, *bin_offset, size);
+	*bin_offset += size;
 }
 
 /* uncompress a compressed symbol. When this function is called, the best table
@@ -392,13 +401,15 @@ static void sort_symbols_by_name(void)
 	qsort(table, table_cnt, sizeof(table[0]), compare_names);
 }
 
-static void write_src(FILE *out_bin_file, const char *out_bin_name)
+static void write_src(void)
 {
-	unsigned int i, off;
+	unsigned int i, k, len, off, seq;
 	unsigned int best_idx[256];
 	unsigned int *markers, markers_cnt;
-	long bin_start;
+	unsigned long bin_offset = 0;
 	char buf[1 + KSYM_NAME_LEN];
+	struct sym_entry *se;
+	const char *sep;
 
 	printf("\t.section .rodata, \"a\"\n");
 
@@ -406,51 +417,105 @@ static void write_src(FILE *out_bin_file, const char *out_bin_name)
 	printf("\t.long\t%u\n", table_cnt);
 	printf("\n");
 
+	output_label("kallsyms_token_table");
+	off = 0;
+	for (i = 0; i < 256; i++) {
+		len = expand_symbol(best_table[i], best_table_len[i], buf);
+		best_idx[i] = off;
+		off += len + 1;
+		printf("\t.asciz\t\"%s\"\n", buf);
+	}
+	printf(".size kallsyms_token_table, . - kallsyms_token_table\n");
+	printf("\n");
+
+	output_label("kallsyms_token_index");
+	sep = "\t.short\t";
+	for (i = 0; i < 256; i++) {
+		printf("%s%d", sep, best_idx[i]);
+		sep = (i + 1) & 15 ? "," : "\n\t.short\t";
+	}
+	printf("\n");
+	printf(".size kallsyms_token_index, . - kallsyms_token_index\n");
+	printf("\n");
+
+	stamp("write token table");
+
 	/* table of offset markers, that give the offset in the compressed stream
 	 * every 256 symbols */
 	markers_cnt = (table_cnt + 255) / 256;
 	markers = xmalloc(sizeof(*markers) * markers_cnt);
 
 	output_label("kallsyms_names");
-	bin_start = bin_pos(out_bin_file);
+	write_incbin_header("names", &bin_offset);
 	off = 0;
 	for (i = 0; i < table_cnt; i++) {
-		if ((i & 0xFF) == 0)
-			markers[i >> 8] = off;
-		table[i]->seq = i;
+		unsigned int se_len, len_len;
+		unsigned char len[2];
+
+		se = table[i];
+		se->seq = i;
 
 		/* The length must be less than that of the original symbol. */
-		if (!table[i]->len || table[i]->len > KSYM_NAME_LEN)
+		if (!se->len || se->len > KSYM_NAME_LEN)
 			errx(EXIT_FAILURE, "symbol %d has corrupt compressed length %d",
-			     i, table[i]->len);
+			     i, se->len);
+
+		/* Generate the original name */
+		se_len = expand_symbol(se->sym, se->len, buf);
 
 		/* Encode length with ULEB128. */
-		if (table[i]->len <= 0x7F) {
+		if (se->len <= 0x7F) {
 			/* Most symbols use a single byte for the length. */
-			fputc(table[i]->len, out_bin_file);
-			off += table[i]->len + 1;
+			len[0] = se->len;
+			len_len = 1;
 		} else {
 			/* "Big" symbols use two bytes. */
-			fputc((table[i]->len & 0x7F) | 0x80, out_bin_file);
-			fputc((table[i]->len >> 7) & 0x7F, out_bin_file);
-			off += table[i]->len + 2;
+			len[0] = 0x80 | se->len;
+			len[1] = se->len >> 7;
+			len_len = 2;
 		}
-		fwrite(table[i]->sym, 1, table[i]->len, out_bin_file);
 
-		/*
-		 * Now that we wrote out the compressed symbol name, restore the
-		 * original name for the comments below.
-		 */
-		expand_symbol(table[i]->sym, table[i]->len, buf);
-		strcpy((char *)table[i]->sym, buf);
+		if (out_bin_file) {
+			if ((i & 0xFF) == 0)
+				markers[i >> 8] = big_endian ? htobe32(off) : htole32(off);
+
+			fwrite(len, 1, len_len, out_bin_file);
+			fwrite(se->sym, 1, se->len, out_bin_file);
+		} else {
+			if ((i & 0xFF) == 0)
+				markers[i >> 8] = off;
+
+			printf("\t.byte\t%u", len[0]);
+			if (len_len == 2)
+				printf(",%u", len[1]);
+
+			for (k = 0; k < se->len; k++)
+				printf(",%u", se->sym[k]);
+			printf("\t/* %c %s */\n", buf[0], buf + 1);
+		}
+		off += len_len + se->len;
+
+		/* Restore the original name. */
+		se->len = se_len;
+		memcpy(se->sym, buf, se_len + 1);
 	}
-	write_incbin(out_bin_name, bin_start, bin_pos(out_bin_file));
+	write_incbin(&bin_offset, 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]);
+	if (out_bin_file) {
+		write_incbin_header("markers", &bin_offset);
+		fwrite(markers, sizeof(*markers), markers_cnt, out_bin_file);
+		write_incbin(&bin_offset, sizeof(*markers) * markers_cnt);
+	} else {
+		sep = "\t.long\t";
+		for (i = 0; i < markers_cnt; i++) {
+			printf("%s%u", sep, markers[i]);
+			sep = (i + 1) & 7 ? "," : "\n\t.long\t";
+		}
+		printf("\n");
+	}
 	printf(".size kallsyms_markers, . - kallsyms_markers\n");
 	printf("\n");
 
@@ -458,31 +523,15 @@ static void write_src(FILE *out_bin_file, const char *out_bin_name)
 
 	stamp("write compressed names");
 
-	output_label("kallsyms_token_table");
-	bin_start = bin_pos(out_bin_file);
-	off = 0;
-	for (i = 0; i < 256; i++) {
-		best_idx[i] = off;
-		expand_symbol(best_table[i], best_table_len[i], buf);
-		fwrite(buf, 1, strlen(buf) + 1, out_bin_file);
-		off += strlen(buf) + 1;
-	}
-	write_incbin(out_bin_name, bin_start, bin_pos(out_bin_file));
-	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("\n");
-
-	stamp("write token table");
-
 	output_label("kallsyms_offsets");
 
 	for (i = 0; i < table_cnt; i++) {
 		if (pc_relative) {
+			/* All 64 bit builds and (at least) relocatable 32 bit ones */
+			static char line[] = "\t.long\t_text - . +123456789";
+			char *end = line + sizeof(line) - 1;
 			long long offset = table[i]->addr - _text;
+			int off32;
 
 			if (offset < INT_MIN || offset > INT_MAX) {
 				errx(EXIT_FAILURE, "kallsyms failure: "
@@ -490,12 +539,28 @@ static void write_src(FILE *out_bin_file, const char *out_bin_name)
 					table[i]->addr);
 				exit(EXIT_FAILURE);
 			}
-			printf("\t.long\t_text - . + (%d)\t/* %s */\n",
-			       (int)offset, table[i]->sym);
+
+			/* Build the line so the the faster fwrite() can be used */
+			*end-- = out_bin_file ? '\n' : '\t';
+			memset(end - 8, ' ', 8);
+			off32 = offset;
+			if (off32 < 0) {
+				end[-9] = '-';
+				offset = -off32;
+			} else {
+				end[-9] = '+';
+			}
+			do
+				*end-- = '0' + off32 % 10;
+			while (off32 /= 10);
+
+			fwrite(line, 1, sizeof(line), stdout);
 		} else {
-			printf("\t.long\t%#x\t/* %s */\n",
-			       (unsigned int)table[i]->addr, table[i]->sym);
+			printf("\t.long\t%#x%c", (unsigned int)table[i]->addr,
+			       out_bin_file ? '\n' : '\t');
 		}
+		if (!out_bin_file)
+			printf("/* %c %s */\n", table[i]->sym[0], table[i]->sym + 1);
 	}
 	printf(".size kallsyms_offsets, . - kallsyms_offsets\n");
 	printf("\n");
@@ -503,17 +568,29 @@ static void write_src(FILE *out_bin_file, const char *out_bin_name)
 	stamp("write symbol values");
 
 	sort_symbols_by_name();
+	stamp("sort by name");
+
 	output_label("kallsyms_seqs_of_names");
-	bin_start = bin_pos(out_bin_file);
+	write_incbin_header("seq_of_names", &bin_offset);
 	for (i = 0; i < table_cnt; i++) {
-		fputc(table[i]->seq >> 16, out_bin_file);
-		fputc(table[i]->seq >> 8, out_bin_file);
-		fputc(table[i]->seq >> 0, out_bin_file);
+		se = table[i];
+		seq = se->seq;
+		if (out_bin_file) {
+			unsigned int seq_be = htobe32(seq);
+			fwrite((char *)&seq_be + 1, 1, 3, out_bin_file);
+		} else {
+			/* The three spaces before the tab line up the comments */
+			printf("\t.byte\t%u,%u,%u   \t/* %8d %c %s */\n",
+				seq >> 16, (seq >> 8) & 0xff, seq & 0xff,
+				seq, se->sym[0], se->sym + 1);
+		}
 	}
-	write_incbin(out_bin_name, bin_start, bin_pos(out_bin_file));
-	printf("\n");
+	write_incbin(&bin_offset, table_cnt * 3);
+	printf(".size kallsyms_seqs_of_names, . - kallsyms_seqs_of_names\n");
 
 	stamp("write name index");
+
+	write_incbin_header("end", &bin_offset);
 }
 
 static unsigned int token_index(unsigned char first, unsigned char second)
@@ -827,13 +904,13 @@ static void sort_symbols(void)
 static void usage(void)
 {
 	fprintf(stderr,
-		"Usage: kallsyms [options] vmlinux out.bin > out.S\n"
-		"       kallsyms --sysmap=out.map vmlinux\n"
+		"Usage: kallsyms [options] [vmlinux [out.bin]] > out.S\n"
+		"       kallsyms --sysmap vmlinux > out.map\n"
 		"           --all-symbols     Include all local symbols\n"
-		"           --pc-relative     Output symbols offsets\n"
+		"           --pc-relative     Output symbol offsets\n"
 		"           --sysmap=out.map  Text map file\n"
 		"           --verbose         Extra diagnostic output\n"
-		"           vmlinux: File to read, can be empty\n"
+		"           vmlinux: File to read\n"
 		"           out.S: Assembler source output file.\n"
 		"           out.bin: Binary data; included in out.S using .incbin\n"
 		"       In the second form only the symbol table out.map is generated,\n"
@@ -845,14 +922,14 @@ static void usage(void)
 
 int main(int argc, char **argv)
 {
-	const char *in, *sysmap = NULL, *out_bin_name;
-	FILE *sysmap_out = NULL, *out_bin_file;
+	const char *sysmap = NULL;
+	FILE *sysmap_out = NULL;
 
 	while (1) {
 		static const struct option long_options[] = {
 			{"all-symbols",     no_argument, &all_symbols,     1},
 			{"pc-relative",     no_argument, &pc_relative,     1},
-			{"sysmap",    required_argument, NULL,           's'},
+			{"sysmap",    optional_argument, NULL,           's'},
 			{"verbose",         no_argument, &verbose,         1},
 			{},
 		};
@@ -862,44 +939,44 @@ int main(int argc, char **argv)
 		if (c == -1)
 			break;
 		if (c == 's')
-			sysmap = optarg;
+			sysmap = optarg ?: "";
 		else if (c != 0)
 			usage();
 	}
 
 	stamp(NULL);
 
-	if (optind + 2 != argc && !(sysmap && optind + 1 == argc))
+	if (argc - optind > 2)
 		usage();
 
-	in = argv[optind];
 	if (sysmap) {
-		sysmap_out = fopen(sysmap, "w");
-		if (!sysmap_out)
-			err(EXIT_FAILURE, "failed to open sysmap output file %s", sysmap);
-	}
-
-	if (optind + 1 == argc) {
-		read_elf(in, sysmap_out);
-		fflush(sysmap_out);
-		if (ferror(sysmap_out) || fclose(sysmap_out))
-			errx(EXIT_FAILURE, "error writing sysmap file %s", sysmap);
-		return 0;
+		if (*sysmap) {
+			sysmap_out = fopen(sysmap, "w");
+			if (!sysmap_out)
+				err(EXIT_FAILURE, "failed to open sysmap output file %s", sysmap);
+		} else {
+			/* Compressed output supressed */
+			sysmap_out = stdout;
+		}
 	}
 
-	out_bin_name = argv[optind + 1];
-	out_bin_file = fopen(out_bin_name, "w");
-	if (!out_bin_file)
-		err(EXIT_FAILURE, "failed to open nin.out file %s", out_bin_name);
-
-	read_elf(in, sysmap_out);
+	read_elf(argv[optind], sysmap_out);
 	if (sysmap_out) {
 		fflush(sysmap_out);
 		if (ferror(sysmap_out) || fclose(sysmap_out))
 			errx(EXIT_FAILURE, "error writing sysmap file %s", sysmap);
+		if (sysmap_out == stdout)
+			exit(0);
 	}
 	stamp("read elf");
 
+	if (argc - optind >= 2) {
+		out_bin_name = argv[optind + 1];
+		out_bin_file = fopen(out_bin_name, "w");
+		if (!out_bin_file)
+			err(EXIT_FAILURE, "failed to open bin.out file %s", out_bin_name);
+	}
+
 	shrink_table();
 	stamp("shrink table");
 
@@ -908,12 +985,14 @@ int main(int argc, char **argv)
 
 	optimize_token_table();
 
-	write_src(out_bin_file, out_bin_name);
+	write_src();
 
 	/* Write errors are latched in the stream, so one check at the end covers them all. */
-	fflush(out_bin_file);
-	if (ferror(out_bin_file) || fclose(out_bin_file))
-		errx(EXIT_FAILURE, "error writing out.bin file %s", out_bin_name);
+	if (out_bin_file) {
+		fflush(out_bin_file);
+		if (ferror(out_bin_file) || fclose(out_bin_file))
+			errx(EXIT_FAILURE, "error writing out.bin file %s", out_bin_name);
+	}
 
 	fflush(stdout);
 	if (ferror(stdout))
diff --git a/scripts/kallsyms.h b/scripts/kallsyms.h
index 4b2801ba6285..c5ead7e60570 100644
--- a/scripts/kallsyms.h
+++ b/scripts/kallsyms.h
@@ -34,6 +34,7 @@ struct sysmap {
 	struct sysmap_symbol *syms;
 	size_t nr_syms;
 	int addr_width;		/* hex digits of an address */
+	int big_endian;
 	struct elf_file elf;	/* the mapping the names point into */
 };
 
diff --git a/scripts/link-vmlinux.sh b/scripts/link-vmlinux.sh
index d5710e900bd4..44b5a6d78ce5 100755
--- a/scripts/link-vmlinux.sh
+++ b/scripts/link-vmlinux.sh
@@ -141,7 +141,7 @@ kallsyms()
 	fi
 
 	info KSYMS "${2}.S"
-	scripts/kallsyms ${kallsymopt} "${1}" "${2}.bin" > "${2}.S"
+	scripts/kallsyms ${kallsymopt} ${1:+"${1}" "${2}.bin"} > "${2}.S"
 
 	info AS "${2}.o"
 	${CC} ${NOSTDINC_FLAGS} ${LINUXINCLUDE} ${KBUILD_CPPFLAGS} \
@@ -162,7 +162,7 @@ sysmap_and_kallsyms()
 mksysmap()
 {
 	info SYSMAP ${2}
-	scripts/kallsyms --sysmap="${2}" "${1}"
+	scripts/kallsyms --sysmap "${1}" >"${2}"
 }
 
 sorttable()
@@ -213,8 +213,7 @@ case "${WARN_ON_UNUSED_TRACEPOINTS}" in
 esac
 
 if is_enabled CONFIG_KALLSYMS; then
-	true > .tmp_vmlinux0.syms
-	kallsyms .tmp_vmlinux0.syms .tmp_vmlinux0.kallsyms
+	kallsyms "" .tmp_vmlinux0.kallsyms
 fi
 
 if is_enabled CONFIG_KALLSYMS || is_enabled CONFIG_DEBUG_INFO_BTF; then
-- 
2.39.5

[PATCH v3 next 05/13] 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>
---

Previously patch 2.

 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 v3 next 06/13] 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.

Example output (after all these patches)
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 *:
        |         **
        |        ****
        |        ****
        |        ****
        |       ******
        |       *******
        |      *********
        |   ******************  **    * * *

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

v3:
- Previously patch 3.
- Fix build when CONFIG_KALLSYMS_ALL set.
- Fix compression ratio print (50.05% not 50.5%)

 kernel/kallsyms_selftest.c | 169 ++++++++++++++++++++++++++++---------
 1 file changed, 127 insertions(+), 42 deletions(-)

diff --git a/kernel/kallsyms_selftest.c b/kernel/kallsyms_selftest.c
index 0db79237fe54..f7fef70ed2c8 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,39 +31,60 @@ 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++;
-	kallsyms_test_var_data_static++;
+	kallsyms_test_var_data_static += kallsyms_very_long_name;
 
 	return 0;
 }
@@ -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;
@@ -148,43 +172,104 @@ static void test_kallsyms_compression_ratio(void)
 	pr_info("| nr_symbols | compressed size | original size | ratio(%%) |\n");
 	pr_info("|---------------------------------------------------------|\n");
 	ratio = (u32)div_u64(10000ULL * total_size, total_len);
-	pr_info("| %10d |    %10d   |   %10d  |  %2d.%-2d   |\n",
+	pr_info("| %10d |    %10d   |   %10d  |  %2d.%02d   |\n",
 		kallsyms_num_syms, total_size, total_len, ratio / 100, ratio % 100);
 	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 v3 next 07/13] 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>
---

Unchanged from Jim's patch.
I think this is the latest version of it, but any later changes
shouldn't cause problems.

 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 v3 next 08/13] kallsyms: Optimise symbol name search

[David Laight]

Change the alphabetically ordered lookup table (kallsyms_seqs_of_names)
to one that indexes 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 was done twice 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 26 bits on x86-64).

Use the low bit of the index table value to indicate that the symbol has
the same name as the previous one.
Use this to avoid the second lookup to find if the name is unique, speed
up the search for the first symbol with a given name, and simplify
kallsyms_on_each_match_symbol().

Speeds up lookup by name by a factor of about 12, and makes a massive
difference to the time taken to lookup symbols that occur 100s or
1000s (or maybe 10000s) of times.

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

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

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

v3:
- Use a discrimant union for the name table instead of weak symbols.
  Undefined weak symbols can't be guaranteed to be zero and a build
  mismatch left both undefined.
- Patch the kallsyms_off_size_24 static key from an initcall,
  the first name lookup might not be allowed to sleep.
  Leave a conditional in the 32bit offset case, it is unlikely
  to be needed for a real kernel.
- Merge in the following patch that optimised the scan for duplicates.

 kernel/kallsyms.c          | 162 ++++++++++++++++++++++++-------------
 kernel/kallsyms_internal.h |   7 +-
 scripts/kallsyms.c         |  49 +++++++----
 3 files changed, 148 insertions(+), 70 deletions(-)

diff --git a/kernel/kallsyms.c b/kernel/kallsyms.c
index d18d78e626db..fd42a1a8ed3e 100644
--- a/kernel/kallsyms.c
+++ b/kernel/kallsyms.c
@@ -177,6 +177,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,66 +215,87 @@ 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_FALSE(kallsyms_off_size_24);
 
-	for (i = 0; i < 3; i++)
-		seq = (seq << 8) | kallsyms_seqs_of_names[3 * index + i];
+/*
+ * Get the offset into the compressed list of names for the n'th
+ * symbol in the 'sorted by name' list.
+ * Returns 'offset << 1 | is_duplicate_name'.
+ * To save memory (the array can have 200k+ entries) the values are usually
+ * 24 bit (host ordered) but will be 32 bit if necessary.
+ */
+static inline unsigned int get_symbol_name_offset(unsigned long index)
+{
+	if (static_branch_likely(&kallsyms_off_size_24) ||
+	    unlikely(kallsyms_offs_of_names.size == 24)) {
+		u8 *off = kallsyms_offs_of_names.offs + index * 3;
+#if !defined(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS)
+		return ((struct {unsigned int v:24 __packed; } __packed *)off)->v;
+#else
+#if defined(__BIG_ENDIAN)
+		return (*(u32 *)(off - 1)) & 0xffffff;
+#else
+		return (*(u32 *)(off - 1)) >> 8;
+#endif
+#endif
+	}
 
-	return seq;
+	return ((u32 *)&kallsyms_offs_of_names.offs)[index];
 }
 
-static int kallsyms_lookup_names(const char *name,
-				 unsigned int *start,
-				 unsigned int *end)
+static int kallsyms_set_kallsyms_off_size(void)
 {
+	if (kallsyms_offs_of_names.size == 24)
+		static_branch_enable(&kallsyms_off_size_24);
+
+	return 0;
+}
+early_initcall(kallsyms_set_kallsyms_off_size);
+
+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 seq, off;
 
 	low = 0;
 	high = kallsyms_num_syms - 1;
 
-	while (low <= high) {
+	for (;;) {
+		if (low > high)
+			return -1;
 		mid = low + (high - low) / 2;
-		seq = get_symbol_seq(mid);
-		off = get_symbol_offset(seq);
-		ret = kallsyms_strcmp_symbol(off, name);
-		if (ret > 0)
+		off = get_symbol_name_offset(mid);
+		ret = kallsyms_strcmp_symbol(off >> 1, name);
+		if (ret > 0) {
 			low = mid + 1;
-		else if (ret < 0)
-			high = mid - 1;
-		else
-			break;
-	}
-
-	if (low > high)
-		return -ESRCH;
-
-	low = mid;
-	while (low) {
-		seq = get_symbol_seq(low - 1);
-		off = get_symbol_offset(seq);
-		if (kallsyms_strcmp_symbol(off, name) != 0)
-			break;
-		low--;
-	}
-	*start = low;
-
-	if (end) {
-		high = mid;
-		while (high < kallsyms_num_syms - 1) {
-			seq = get_symbol_seq(high + 1);
-			off = get_symbol_offset(seq);
-			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 0;
+	*start = mid;
+
+	return off;
 }
 
 /* Lookup the address for this symbol. Returns 0 if not found. */
@@ -257,9 +308,9 @@ unsigned long kallsyms_lookup_name(const char *name)
 	if (!*name)
 		return 0;
 
-	ret = kallsyms_lookup_names(name, &i, NULL);
-	if (!ret)
-		return kallsyms_sym_address(get_symbol_seq(i));
+	ret = kallsyms_lookup_names(name, &i);
+	if (ret >= 0)
+		return get_name_address(ret >> 1);
 
 	return module_kallsyms_lookup_name(name);
 }
@@ -289,17 +340,20 @@ 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;
 
-	ret = kallsyms_lookup_names(name, &start, &end);
-	if (ret)
+	name_offset = kallsyms_lookup_names(name, &sym_number);
+	if (name_offset < 0)
 		return 0;
 
-	for (i = start; !ret && i <= end; i++) {
-		ret = fn(data, kallsyms_sym_address(get_symbol_seq(i)));
+	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 81a867dbe57d..11fb0de92ede 100644
--- a/kernel/kallsyms_internal.h
+++ b/kernel/kallsyms_internal.h
@@ -13,6 +13,11 @@ 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[];
+
+/* Although constant, size is volatile for better code generation. */
+extern struct {
+	volatile unsigned int size;	/* 24 or 32 */
+	unsigned char offs[];		/* int:24[] or int:32[] */
+} kallsyms_offs_of_names;
 
 #endif // LINUX_KALLSYMS_INTERNAL_H_
diff --git a/scripts/kallsyms.c b/scripts/kallsyms.c
index 74db751600b4..930ec27a53c0 100644
--- a/scripts/kallsyms.c
+++ b/scripts/kallsyms.c
@@ -403,7 +403,7 @@ static void sort_symbols_by_name(void)
 
 static void write_src(void)
 {
-	unsigned int i, k, len, off, seq;
+	unsigned int i, k, len, off, off_size, table_size;
 	unsigned int best_idx[256];
 	unsigned int *markers, markers_cnt;
 	unsigned long bin_offset = 0;
@@ -453,7 +453,7 @@ static void write_src(void)
 		unsigned char len[2];
 
 		se = table[i];
-		se->seq = i;
+		se->seq = off;
 
 		/* The length must be less than that of the original symbol. */
 		if (!se->len || se->len > KSYM_NAME_LEN)
@@ -485,7 +485,7 @@ static void write_src(void)
 			if ((i & 0xFF) == 0)
 				markers[i >> 8] = off;
 
-			printf("\t.byte\t%u", len[0]);
+			printf("\t/* n:%u */\t.byte\t%u", off, len[0]);
 			if (len_len == 2)
 				printf(",%u", len[1]);
 
@@ -500,6 +500,7 @@ static void write_src(void)
 		memcpy(se->sym, buf, se_len + 1);
 	}
 	write_incbin(&bin_offset, off);
+	table_size = off;
 	printf(".size kallsyms_names, . - kallsyms_names\n");
 	printf("\n");
 
@@ -560,7 +561,7 @@ static void write_src(void)
 			       out_bin_file ? '\n' : '\t');
 		}
 		if (!out_bin_file)
-			printf("/* %c %s */\n", table[i]->sym[0], table[i]->sym + 1);
+			printf("/* n:%u %c %s */\n", table[i]->seq, table[i]->sym[0], table[i]->sym + 1);
 	}
 	printf(".size kallsyms_offsets, . - kallsyms_offsets\n");
 	printf("\n");
@@ -570,23 +571,41 @@ static void write_src(void)
 	sort_symbols_by_name();
 	stamp("sort by name");
 
-	output_label("kallsyms_seqs_of_names");
-	write_incbin_header("seq_of_names", &bin_offset);
+	off_size = table_size < (1u << 23) ? 24 : 32;
+	output_label("kallsyms_offs_of_names");
+	printf("\t.long\t%u\n", off_size);
+	write_incbin_header("offs_of_names", &bin_offset);
 	for (i = 0; i < table_cnt; i++) {
 		se = table[i];
-		seq = se->seq;
+		off = se->seq << 1;
+		if (i && se->len == table[i - 1]->len &&
+		    !memcmp(se->sym + 1, table[i - 1]->sym + 1, se->len - 1))
+			/* Mark that this is a duplicate of the previous symbol */
+			off |= 1;
 		if (out_bin_file) {
-			unsigned int seq_be = htobe32(seq);
-			fwrite((char *)&seq_be + 1, 1, 3, out_bin_file);
+			unsigned int off_te = big_endian ? htobe32(off) >> (32 - off_size): htole32(off);
+			fwrite(&off_te, 1, off_size / 8 , out_bin_file);
 		} else {
-			/* The three spaces before the tab line up the comments */
-			printf("\t.byte\t%u,%u,%u   \t/* %8d %c %s */\n",
-				seq >> 16, (seq >> 8) & 0xff, seq & 0xff,
-				seq, se->sym[0], se->sym + 1);
+			if (off_size == 32) {
+				printf("\t.long\t%#4x", off);
+			} else {
+				if (big_endian)
+					off = __builtin_bswap32(off) >> 8;
+				/* The trailing three spaces line up the comments */
+				printf("\t.byte\t%u,%u,%u   ",
+					off & 0xff, (off >> 8) & 0xff, off >> 16);
+			}
+			printf("\t/* n:%-8d %c %s */\n",
+				se->seq, se->sym[0], se->sym + 1);
 		}
 	}
-	write_incbin(&bin_offset, table_cnt * 3);
-	printf(".size kallsyms_seqs_of_names, . - kallsyms_seqs_of_names\n");
+	write_incbin(&bin_offset, table_cnt * (off_size / 8));
+	/* Add a 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_offs_of_names, . - kallsyms_offs_of_names\n");
 
 	stamp("write name index");
 
-- 
2.39.5

[PATCH v3 next 09/13] kallsyms: Add a kernel parameter to change the kallsyms_markers[] density

[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.
Write the value used to the output file to ensure the kernel uses the
correct value.

The program's default is unchanged at 1 marker per 256 symbols,
The kernel config defaults to 1 marker per 64 symbols.
This increases the static data by a little less than 1 bit for every
two symbols.

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

v3: Previously patches 8 and 9

 init/Kconfig               | 19 +++++++++++++++
 kernel/kallsyms.c          | 16 ++++++-------
 kernel/kallsyms_internal.h |  1 +
 scripts/kallsyms.c         | 49 ++++++++++++++++++++++++++------------
 scripts/link-vmlinux.sh    |  6 +++++
 5 files changed, 67 insertions(+), 24 deletions(-)

diff --git a/init/Kconfig b/init/Kconfig
index 4013781e0a02..b2db123a51d7 100644
--- a/init/Kconfig
+++ b/init/Kconfig
@@ -1908,6 +1908,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/kernel/kallsyms.c b/kernel/kallsyms.c
index fd42a1a8ed3e..2c4264a3e0c5 100644
--- a/kernel/kallsyms.c
+++ b/kernel/kallsyms.c
@@ -147,13 +147,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
@@ -161,7 +159,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;
 
 		/*
@@ -185,7 +183,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;
@@ -196,7 +194,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 11fb0de92ede..9137870ad00f 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[];
 
 /* Although constant, size is volatile for better code generation. */
diff --git a/scripts/kallsyms.c b/scripts/kallsyms.c
index 930ec27a53c0..c27aaabccd1b 100644
--- a/scripts/kallsyms.c
+++ b/scripts/kallsyms.c
@@ -59,6 +59,8 @@ static unsigned int table_size, table_cnt;
 static int all_symbols;
 static int pc_relative;
 static int verbose;
+/* Default to one kallsyms_markers[] entry for each 256 symbols */
+static unsigned long marker_shift = 8;
 
 static int big_endian;	/* Extracted from the elf file */
 
@@ -441,8 +443,8 @@ static void write_src(void)
 	stamp("write token table");
 
 	/* table of offset markers, that give the offset in the compressed stream
-	 * every 256 symbols */
-	markers_cnt = (table_cnt + 255) / 256;
+	 * every (1 << marker_shift) (typically 64 or 256) symbols */
+	markers_cnt = (table_cnt + 255) >> marker_shift;
 	markers = xmalloc(sizeof(*markers) * markers_cnt);
 
 	output_label("kallsyms_names");
@@ -476,14 +478,14 @@ static void write_src(void)
 		}
 
 		if (out_bin_file) {
-			if ((i & 0xFF) == 0)
-				markers[i >> 8] = big_endian ? htobe32(off) : htole32(off);
+			if ((i & ((1u << marker_shift) - 1)) == 0)
+				markers[i >> marker_shift] = big_endian ? htobe32(off) : htole32(off);
 
 			fwrite(len, 1, len_len, out_bin_file);
 			fwrite(se->sym, 1, se->len, out_bin_file);
 		} else {
-			if ((i & 0xFF) == 0)
-				markers[i >> 8] = off;
+			if ((i & ((1u << marker_shift) - 1)) == 0)
+				markers[i >> marker_shift] = off;
 
 			printf("\t/* n:%u */\t.byte\t%u", off, len[0]);
 			if (len_len == 2)
@@ -504,6 +506,10 @@ static void write_src(void)
 	printf(".size kallsyms_names, . - kallsyms_names\n");
 	printf("\n");
 
+	output_label("kallsyms_marker_shift");
+	printf("\t.long\t%lu\n" , marker_shift);
+	printf("\n");
+
 	output_label("kallsyms_markers");
 	if (out_bin_file) {
 		write_incbin_header("markers", &bin_offset);
@@ -926,6 +932,7 @@ static void usage(void)
 		"Usage: kallsyms [options] [vmlinux [out.bin]] > out.S\n"
 		"       kallsyms --sysmap vmlinux > out.map\n"
 		"           --all-symbols     Include all local symbols\n"
+		"           --marker-shift=n  Interval between makers (6 => 64, 8 => 256)\n"
 		"           --pc-relative     Output symbol offsets\n"
 		"           --sysmap=out.map  Text map file\n"
 		"           --verbose         Extra diagnostic output\n"
@@ -946,21 +953,33 @@ 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},
-			{"sysmap",    optional_argument, NULL,           's'},
-			{"verbose",         no_argument, &verbose,         1},
+			{"all-symbols",        no_argument, &all_symbols,     1},
+			{"marker-shift", required_argument, NULL,           'm'},
+			{"pc-relative",        no_argument, &pc_relative,     1},
+			{"sysmap",       optional_argument, NULL,           's'},
+			{"verbose",            no_argument, &verbose,         1},
 			{},
 		};
 
-		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 == 's')
+		case 0:
+			continue;
+		case 'm':
+			if (!optarg[0])
+				continue;
+			marker_shift = strtoul(optarg, NULL, 10);
+			if (marker_shift > 24)
+				usage();
+			continue;
+		case 's':
 			sysmap = optarg ?: "";
-		else if (c != 0)
+			continue;
+		default:
 			usage();
+		}
+		break;
 	}
 
 	stamp(NULL);
diff --git a/scripts/link-vmlinux.sh b/scripts/link-vmlinux.sh
index 44b5a6d78ce5..61cf8f287ebe 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()
@@ -140,6 +144,8 @@ kallsyms()
 		kallsymopt="${kallsymopt} --pc-relative"
 	fi
 
+	kallsymopt="${kallsymopt} --marker-shift=$(value CONFIG_KALLSYMS_MARKER_SHIFT)"
+
 	info KSYMS "${2}.S"
 	scripts/kallsyms ${kallsymopt} ${1:+"${1}" "${2}.bin"} > "${2}.S"
 
-- 
2.39.5

[PATCH v3 next 10/13] scripts/kallsyms: Keep full expansion of tokens

[David Laight]

Expand the full string when a new compression token is allocated.
Saves the recursive expansions later on.
It 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.

Change find_best_token() to return -1 if there are no tokens
(eg if the input file is very small) to save the caller rechecking
token_profit[].

Save the original symbol name length and check that the expanded
symbol has the same length.

No change to generated output.

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

About 3ms (in 175ms) can be saved by keeping a copy of the name
itself and avoiding expand_symbol(), but it is messy.
And another 18ms by doing the alphabetic sort in a thread.

v3:
- Reworked on top of the changes in 7.4-rc1
- Avoid printf("%s", NULL) on initial 'no symbol' build.
  While fine with glibc, other libs dump core.

 scripts/kallsyms.c | 156 +++++++++++++++++++++++++--------------------
 1 file changed, 88 insertions(+), 68 deletions(-)

diff --git a/scripts/kallsyms.c b/scripts/kallsyms.c
index c27aaabccd1b..cbf05972043b 100644
--- a/scripts/kallsyms.c
+++ b/scripts/kallsyms.c
@@ -36,7 +36,8 @@
 
 struct sym_entry {
 	unsigned long long addr;
-	unsigned int len;
+	unsigned short len;
+	unsigned short orig_len;
 	unsigned int seq;
 	unsigned char sym[];
 };
@@ -76,12 +77,21 @@ struct sym_arr {
 /* Every pair of bytes is a token. */
 #define NR_TOKENS	0x10000
 
+/*
+ * token_profit[token_index(first, second)] is the number of times the characters
+ * first and second 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.
+ */
 static int token_profit[NR_TOKENS];
+/* The symbols that contain each pair of characters. */
 static struct sym_arr token_syms[NR_TOKENS];
 
 /* 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 best_table {
+	char           *str;		/* Full expansion, '\0' terminated */
+	unsigned short len;		/* Length of str */
+} best_table[256];
 
 static void stamp(const char *where)
 {
@@ -199,6 +209,7 @@ static struct sym_entry *add_symbol(unsigned long long addr, char type,
 	sym = xmalloc(sizeof(*sym) + len + 1);
 	sym->addr = addr;
 	sym->len = len;
+	sym->orig_len = len;
 	sym->sym[0] = type;
 	strcpy(sym_entry_name(sym), name);
 
@@ -351,29 +362,17 @@ static void write_incbin(unsigned long *bin_offset, unsigned long size)
 	*bin_offset += size;
 }
 
-/* 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 (best_table[c][0]==c && best_table_len[c]==1) {
-			*result++ = c;
-			total++;
-		} else {
-			/* if not, recurse and expand */
-			rlen = expand_symbol(best_table[c], best_table_len[c], result);
-			total += rlen;
-			result += rlen;
-		}
-		data++;
-		len--;
+	struct best_table *bt;
+	unsigned int total = 0;
+
+	while (len--) {
+		bt = best_table + *data++;
+		memcpy(result + total, bt->str, bt->len);
+		total += bt->len;
 	}
-	*result=0;
+	result[total] = 0;
 
 	return total;
 }
@@ -405,7 +404,7 @@ static void sort_symbols_by_name(void)
 
 static void write_src(void)
 {
-	unsigned int i, k, len, off, off_size, table_size;
+	unsigned int i, k, off, off_size, table_size;
 	unsigned int best_idx[256];
 	unsigned int *markers, markers_cnt;
 	unsigned long bin_offset = 0;
@@ -422,10 +421,9 @@ static void write_src(void)
 	output_label("kallsyms_token_table");
 	off = 0;
 	for (i = 0; i < 256; i++) {
-		len = expand_symbol(best_table[i], best_table_len[i], buf);
 		best_idx[i] = off;
-		off += len + 1;
-		printf("\t.asciz\t\"%s\"\n", buf);
+		off += best_table[i].len + 1;
+		printf("\t.asciz\t\"%s\"\n", best_table[i].str);
 	}
 	printf(".size kallsyms_token_table, . - kallsyms_token_table\n");
 	printf("\n");
@@ -451,19 +449,15 @@ static void write_src(void)
 	write_incbin_header("names", &bin_offset);
 	off = 0;
 	for (i = 0; i < table_cnt; i++) {
-		unsigned int se_len, len_len;
+		unsigned int len_len;
 		unsigned char len[2];
 
 		se = table[i];
 		se->seq = off;
 
-		/* The length must be less than that of the original symbol. */
-		if (!se->len || se->len > KSYM_NAME_LEN)
-			errx(EXIT_FAILURE, "symbol %d has corrupt compressed length %d",
-			     i, se->len);
-
-		/* Generate the original name */
-		se_len = expand_symbol(se->sym, se->len, buf);
+		/* Generate the original name in a temporary buffer */
+		if (expand_symbol(se->sym, se->len, buf) != se->orig_len)
+			errx(EXIT_FAILURE, "symbol %d has corrupt compressed data", i);
 
 		/* Encode length with ULEB128. */
 		if (se->len <= 0x7F) {
@@ -498,8 +492,8 @@ static void write_src(void)
 		off += len_len + se->len;
 
 		/* Restore the original name. */
-		se->len = se_len;
-		memcpy(se->sym, buf, se_len + 1);
+		se->len = se->orig_len;
+		memcpy(se->sym, buf, se->len + 1);
 	}
 	write_incbin(&bin_offset, off);
 	table_size = off;
@@ -618,7 +612,7 @@ static void write_src(void)
 	write_incbin_header("end", &bin_offset);
 }
 
-static unsigned int token_index(unsigned char first, unsigned char second)
+static unsigned int token_index(unsigned int first, unsigned int second)
 {
 	return first + (second << 8);
 }
@@ -628,6 +622,16 @@ static unsigned int sym_token_index(const unsigned char *symbol, int first_idx)
 	return token_index(symbol[first_idx], symbol[first_idx + 1]);
 }
 
+static unsigned int token_first(unsigned int token)
+{
+	return token & 0xff;
+}
+
+static unsigned int token_second(unsigned int token)
+{
+	return token >> 8;
+}
+
 /* table lookup compression functions */
 
 /* count all the possible tokens in a symbol */
@@ -718,22 +722,23 @@ 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 = token_index(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 = token_index(token_second(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 compressed_chr)
+static void compress_symbols(unsigned int token_idx, int compressed_chr)
 {
-	const unsigned int token_idx = sym_token_index(str, 0);
 	struct sym_arr *arr = &token_syms[token_idx];
 	unsigned int sym_idx, j, len, size;
 	unsigned char *p1, *p2;
@@ -746,7 +751,7 @@ static void compress_symbols(const unsigned char *str, int compressed_chr)
 		p1 = table[sym_idx]->sym;
 
 		/* find the token on the symbol */
-		p2 = find_token(p1, len, str);
+		p2 = find_token(p1, len, token_idx);
 		if (!p2) continue;
 
 		/* decrease the counts for this symbol's tokens */
@@ -765,7 +770,7 @@ static void compress_symbols(const unsigned char *str, int compressed_chr)
 			if (size < 2) break;
 
 			/* find the token on the symbol */
-			p2 = find_token(p1, size, str);
+			p2 = find_token(p1, size, token_idx);
 
 		} while (p2);
 
@@ -785,8 +790,8 @@ static int find_best_token(void)
 {
 	int i, best, bestprofit;
 
-	bestprofit=-10000;
-	best = 0;
+	bestprofit = 0;
+	best = -1;
 
 	for (i = 0; i < ARRAY_SIZE(token_profit); i++) {
 		if (token_profit[i] > bestprofit) {
@@ -800,29 +805,39 @@ static int find_best_token(void)
 /* this is the core of the algorithm: calculate the "best" table */
 static void optimize_result(void)
 {
+	struct best_table *bt, *first, *second;
+	unsigned int len;
 	int i, best;
+	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--) {
+		bt = best_table + i;
+		/* Ignore tokens used for the original character codes. */
+		if (bt->len)
+			continue;
 
-		/* if this table slot is empty (it is not used by an actual
-		 * original char code */
-		if (!best_table_len[i]) {
-
-			/* find the token with the best profit value */
-			best = find_best_token();
-			if (token_profit[best] == 0)
-				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;
+		/* Find the token that appears most often. */
+		best = find_best_token();
+		if (best < 0)
+			break;
 
-			/* replace this token in all the valid symbols */
-			compress_symbols(best_table[i], i);
-		}
+		/* Replace this token in all the valid symbols. */
+		compress_symbols(best, i);
+
+		/* Generate the full name for this token ... */
+		first = best_table + token_first(best);
+		second = best_table + token_second(best);
+		len = first->len + second->len;
+		str = xmalloc(len + 1);
+		str[len] = 0;
+		memcpy(str, first->str, first->len);
+		memcpy(str + first->len, second->str, second->len);
+
+		/* ... and save. */
+		free(bt->str);
+		bt->str = str;
+		bt->len = len;
 	}
 }
 
@@ -834,10 +849,15 @@ static void insert_real_symbols_in_table(void)
 	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;
+			best_table[c].len = 1;
 		}
 	}
+
+	for (i = 0; i <= 255; i++) {
+		best_table[i].str = xmalloc(2);
+		best_table[i].str[0] = best_table[i].len ? i : 0;
+		best_table[i].str[1] = 0;
+	}
 }
 
 static void optimize_token_table(void)
-- 
2.39.5

[PATCH v3 next 11/13] 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.

On my system this reduces the execution time for optimize_result()
from 98ms to 64ms

The gain will be far more for kernels containing very long symbol names.

Add a function to verify the compression tables are correct.
Call before generating the output when 'incbin' isn't being used.

Output file unchanged.

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

Formally patch 12, rebased on 7.4-rc1

 scripts/kallsyms.c | 169 ++++++++++++++++++++++++++++-----------------
 1 file changed, 105 insertions(+), 64 deletions(-)

diff --git a/scripts/kallsyms.c b/scripts/kallsyms.c
index cbf05972043b..4da613e8e728 100644
--- a/scripts/kallsyms.c
+++ b/scripts/kallsyms.c
@@ -634,22 +634,79 @@ static unsigned int token_second(unsigned int token)
 
 /* table lookup compression functions */
 
-/* count all the possible tokens in a symbol */
-static void learn_symbol(const unsigned char *symbol, int len)
+/* Check that the compression data is consistent. */
+static void check_tables(void)
 {
-	int i;
+	struct {
+		unsigned int refs;
+		unsigned int idx;
+	} tok_info[NR_TOKENS], *ti;
+	unsigned int sym_idx, token;
+	unsigned char *cp, *end;
+	struct sym_arr *sa;
+	unsigned int i, idx;
+
+	memset(&tok_info, 0, sizeof(tok_info));
+
+	/* Check that token_syms[]->sym_indexes is correctly sorted. */
+	for (token = 0; token < NR_TOKENS; token++) {
+		sa = token_syms + token;
+		for (i = 0; i + 1 < sa->cnt; i++) {
+			if (sa->sym_indexes[i] < sa->sym_indexes[i + 1])
+				continue;
+			errx(EXIT_FAILURE, "sym_indexes[%x (%s/%s)] missorted at %u %u >= %u",
+			     token, best_table[token_first(token)].str,
+			     best_table[token_second(token)].str,
+			     i, sa->sym_indexes[i], sa->sym_indexes[i + 1]);
+		}
+	}
 
-	for (i = 0; i < len - 1; i++)
-		token_profit[sym_token_index(symbol, i)]++;
+	/* Check that every token pair is in token_syms[]->sym_indexes[]. */
+	for (sym_idx = 0; sym_idx < table_cnt; sym_idx++) {
+		cp = table[sym_idx]->sym;
+		end = cp + table[sym_idx]->len;
+		/* Scan all pairs */
+		while (++cp < end) {
+			token = token_index(cp[-1], cp[0]);
+			ti = tok_info + token;
+			ti->refs++;
+
+			/* token_syms[]->sym_indexes holds symbol numbers in order. */
+			sa = token_syms + token;
+			for (idx = ti->idx; idx < sa->cnt; idx++) {
+				if (sym_idx == sa->sym_indexes[idx])
+					break;
+			}
+			if (idx >= sa->cnt) {
+				char buf[1 + KSYM_NAME_LEN];
+				expand_symbol(table[sym_idx]->sym, table[sym_idx]->len, buf);
+				errx(EXIT_FAILURE,
+				     "symbol %u (%s) not in sym_indexes[] for token %x (%s/%s)",
+				     sym_idx, buf, token, best_table[cp[-1]].str,
+				     best_table[cp[0]].str);
+			}
+			ti->idx = idx;
+		}
+	}
+
+	/* Check the reference counts for all tokens. */
+	for (idx = 0; idx < NR_TOKENS; idx++) {
+		if (tok_info[idx].refs != token_profit[idx]) {
+			errx(EXIT_FAILURE, "profit error for %x (%s/%s) discrepency %u != %u",
+			     idx, best_table[token_first(idx)].str,
+			     best_table[token_second(idx)].str,
+			     tok_info[idx].refs, token_profit[idx]);
+		}
+	}
 }
 
-/* decrease the count for all the possible tokens in a symbol */
-static void forget_symbol(const unsigned char *symbol, int len)
+/* count all the possible tokens in a symbol */
+static void learn_symbol(const unsigned char *symbol, int len)
 {
 	int i;
 
 	for (i = 0; i < len - 1; i++)
-		token_profit[sym_token_index(symbol, i)]--;
+		token_profit[sym_token_index(symbol, i)]++;
 }
 
 static void token_add_symbol(unsigned int token_idx, unsigned int sym_idx)
@@ -675,23 +732,14 @@ static void symbol_index_all_tokens(const unsigned char *symbol, int len,
 	}
 }
 
-/*
- * The symbol just got compressed. The only parts of the symbol that changed
- * meaningfully are those containing the newly assigned compressed char, so
- * index those.
- */
-static void symbol_index_new_tokens(const unsigned char *symbol, int len,
-				    unsigned int sym_idx, int compressed_chr)
+static void adjust_profit(unsigned int sym_idx,
+			  unsigned int old_first, unsigned int new_first,
+			  unsigned int old_second, unsigned int new_second)
 {
-	int i;
+	token_profit[token_index(old_first, old_second)]--;
+	token_profit[token_index(new_first, new_second)]++;
 
-	for (i = 0; i < len - 1; i++) {
-		const unsigned int token_idx = sym_token_index(symbol, i);
-
-		if (symbol[i] == compressed_chr ||
-		    symbol[i + 1] == compressed_chr)
-			token_add_symbol(token_idx, sym_idx);
-	}
+	token_add_symbol(token_index(new_first, new_second), sym_idx);
 }
 
 static void build_initial_token_table(void)
@@ -721,13 +769,12 @@ static void build_initial_token_table(void)
 		symbol_index_all_tokens(table[i]->sym, table[i]->len, i);
 }
 
-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 = token_index(0, *str++);
-	int i;
 
-	for (i = 0; i < len - 1; i++) {
+	while (str < end) {
 		token = token_index(token_second(token), *str++);
 		if (token == want)
 			return str - 2;
@@ -736,53 +783,42 @@ 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_idx, int compressed_chr)
+ * to update the counts.
+ * Marked noinline to help register allocation. */
+static __attribute__((noinline)) void
+compress_symbols(unsigned int token_idx, int compressed_chr)
 {
 	struct sym_arr *arr = &token_syms[token_idx];
-	unsigned int sym_idx, j, len, size;
-	unsigned char *p1, *p2;
+	unsigned int sym_idx, j, len;
+	unsigned char *sym, *p, *end;
+	struct sym_entry *se;
 
 	/* Iterate through all symbols this token is found in and compress. */
 	for (j = 0; j < arr->cnt; j++) {
 		sym_idx = arr->sym_indexes[j];
 
-		len = table[sym_idx]->len;
-		p1 = table[sym_idx]->sym;
-
-		/* find the token on the symbol */
-		p2 = find_token(p1, len, token_idx);
-		if (!p2) continue;
-
-		/* decrease the counts for this symbol's tokens */
-		forget_symbol(table[sym_idx]->sym, len);
-
-		size = len;
-
-		do {
-			*p2 = compressed_chr;
-			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_idx);
-
-		} while (p2);
-
-		table[sym_idx]->len = len;
-
-		/* increase the counts for this symbol's new tokens */
-		learn_symbol(table[sym_idx]->sym, len);
-		symbol_index_new_tokens(table[sym_idx]->sym, len, sym_idx,
-					compressed_chr);
+		se = table[sym_idx];
+		sym = se->sym;
+		end = sym + se->len;
+
+		for (p = sym; (p = find_token(p, end, token_idx)); p++) {
+			len = end - p - 2;
+			end--;
+			*p = compressed_chr;
+			if (p != sym)
+				adjust_profit(sym_idx, p[-1], p[-1],
+					      token_first(token_idx), compressed_chr);
+			if (!len)
+				break;
+			adjust_profit(sym_idx, token_second(token_idx), compressed_chr, p[2], p[2]);
+			memmove(p + 1, p + 2, len);
+		}
+		se->len = end - sym;
 	}
 
-	sym_arr_free(arr); /* No symbol contains this token any more. */
+	/* No symbol contains this token any more. */
+	token_profit[token_idx] = 0;
+	sym_arr_free(arr);
 }
 
 /* search the token with the maximum profit */
@@ -870,6 +906,11 @@ static void optimize_token_table(void)
 
 	optimize_result();
 	stamp("optimize result");
+
+	if (!out_bin_file) {
+		check_tables();
+		stamp("check tables");
+	}
 }
 
 /* guess for "linker script provide" symbol */
-- 
2.39.5

[PATCH v3 next 12/13] 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.

Output the counts in comments in the output file.

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>
--

v3: Formally patch 13, rebased on 7.4-rc1

 scripts/kallsyms.c | 72 ++++++++++++++++++++++++++++++++++++----------
 1 file changed, 57 insertions(+), 15 deletions(-)

diff --git a/scripts/kallsyms.c b/scripts/kallsyms.c
index 4da613e8e728..2f517873e9b4 100644
--- a/scripts/kallsyms.c
+++ b/scripts/kallsyms.c
@@ -91,6 +91,7 @@ static struct sym_arr token_syms[NR_TOKENS];
 static struct best_table {
 	char           *str;		/* Full expansion, '\0' terminated */
 	unsigned short len;		/* Length of str */
+	unsigned int   refs;		/* Number of times used in a symbol */
 } best_table[256];
 
 static void stamp(const char *where)
@@ -423,7 +424,8 @@ static void write_src(void)
 	for (i = 0; i < 256; i++) {
 		best_idx[i] = off;
 		off += best_table[i].len + 1;
-		printf("\t.asciz\t\"%s\"\n", best_table[i].str);
+		printf("\t.asciz\t\"%s\"\t/* %u: refs %u */\n",
+		       best_table[i].str, i, best_table[i].refs);
 	}
 	printf(".size kallsyms_token_table, . - kallsyms_token_table\n");
 	printf("\n");
@@ -641,12 +643,14 @@ static void check_tables(void)
 		unsigned int refs;
 		unsigned int idx;
 	} tok_info[NR_TOKENS], *ti;
+	unsigned int tok_refs[256];
 	unsigned int sym_idx, token;
 	unsigned char *cp, *end;
 	struct sym_arr *sa;
 	unsigned int i, idx;
 
 	memset(&tok_info, 0, sizeof(tok_info));
+	memset(&tok_refs, 0, sizeof(tok_refs));
 
 	/* Check that token_syms[]->sym_indexes is correctly sorted. */
 	for (token = 0; token < NR_TOKENS; token++) {
@@ -665,8 +669,10 @@ static void check_tables(void)
 	for (sym_idx = 0; sym_idx < table_cnt; sym_idx++) {
 		cp = table[sym_idx]->sym;
 		end = cp + table[sym_idx]->len;
+		tok_refs[*cp]++;
 		/* Scan all pairs */
 		while (++cp < end) {
+			tok_refs[*cp]++;
 			token = token_index(cp[-1], cp[0]);
 			ti = tok_info + token;
 			ti->refs++;
@@ -690,6 +696,12 @@ static void check_tables(void)
 	}
 
 	/* Check the reference counts for all tokens. */
+	for (i = 0; i < 256; i++) {
+		if (tok_refs[i] != best_table[i].refs)
+			errx(EXIT_FAILURE, "token reference error for %u (%s) %u != %u",
+			     i, best_table[i].str, best_table[i].refs, tok_refs[i]);
+	}
+
 	for (idx = 0; idx < NR_TOKENS; idx++) {
 		if (tok_info[idx].refs != token_profit[idx]) {
 			errx(EXIT_FAILURE, "profit error for %x (%s/%s) discrepency %u != %u",
@@ -698,6 +710,7 @@ static void check_tables(void)
 			     tok_info[idx].refs, token_profit[idx]);
 		}
 	}
+
 }
 
 /* count all the possible tokens in a symbol */
@@ -720,6 +733,19 @@ static void token_add_symbol(unsigned int token_idx, unsigned int sym_idx)
 	sym_arr_add(arr, sym_idx);
 }
 
+static unsigned int sym_arr_free_all(unsigned int ch)
+{
+	unsigned int i;
+
+	/* Just zero the counts, the entries are about to be reused. */
+	for (i = 0; i < 256; i++) {
+		token_syms[token_index(i, ch)].cnt = 0;
+		token_syms[token_index(ch, i)].cnt = 0;
+	}
+
+	return ch;
+}
+
 static void symbol_index_all_tokens(const unsigned char *symbol, int len,
 				    unsigned int sym_idx)
 {
@@ -785,11 +811,11 @@ static unsigned char *find_token(unsigned char *str, unsigned char *end,
 /* replace a given token in all the valid symbols. Use the sampled symbols
  * to update the counts.
  * Marked noinline to help register allocation. */
-static __attribute__((noinline)) void
+static __attribute__((noinline)) unsigned int
 compress_symbols(unsigned int token_idx, int compressed_chr)
 {
 	struct sym_arr *arr = &token_syms[token_idx];
-	unsigned int sym_idx, j, len;
+	unsigned int sym_idx, j, len, subs;
 	unsigned char *sym, *p, *end;
 	struct sym_entry *se;
 
@@ -817,8 +843,11 @@ compress_symbols(unsigned int token_idx, int compressed_chr)
 	}
 
 	/* No symbol contains this token any more. */
+	subs = token_profit[token_idx];
 	token_profit[token_idx] = 0;
 	sym_arr_free(arr);
+
+	return subs;
 }
 
 /* search the token with the maximum profit */
@@ -842,28 +871,40 @@ static int find_best_token(void)
 static void optimize_result(void)
 {
 	struct best_table *bt, *first, *second;
-	unsigned int len;
+	unsigned char to_process[256];
+	unsigned int idx, len, refs;
 	int i, best;
 	char *str;
 
-	/* Use the '\0' symbol last so the output is unchanged */
-	for (i = 255; i >= 0; i--) {
-		bt = best_table + i;
-		/* Ignore tokens used for the original character codes. */
-		if (bt->len)
-			continue;
+	/* Generate a list of the unused tokens. */
+	for (i = 0, idx = 0; i < 256; i++) {
+		if (!best_table[i].len)
+			to_process[idx++] = i;
+	}
 
-		/* Find the token that appears most often. */
+	while (idx) {
+		/* find the token that appears most often */
 		best = find_best_token();
 		if (best < 0)
 			break;
+		i = to_process[--idx];
 
 		/* Replace this token in all the valid symbols. */
-		compress_symbols(best, i);
+		refs = compress_symbols(best, i);
 
-		/* Generate the full name for this token ... */
+		bt = best_table + i;
 		first = best_table + token_first(best);
 		second = best_table + token_second(best);
+
+		/* Update the number of times each token is used. */
+		bt->refs += refs;
+		if (!(first->refs -= refs) && first->len > 1)
+			/* There are no references left, reuse the token. */
+			to_process[idx++] = sym_arr_free_all(token_first(best));
+		if (!(second->refs -= refs) && second->len > 1)
+			to_process[idx++] = sym_arr_free_all(token_second(best));
+
+		/* Generate the full name for this token ... */
 		len = first->len + second->len;
 		str = xmalloc(len + 1);
 		str[len] = 0;
@@ -885,13 +926,14 @@ static void insert_real_symbols_in_table(void)
 	for (i = 0; i < table_cnt; i++) {
 		for (j = 0; j < table[i]->len; j++) {
 			c = table[i]->sym[j];
-			best_table[c].len = 1;
+			best_table[c].refs++;
 		}
 	}
 
 	for (i = 0; i <= 255; i++) {
 		best_table[i].str = xmalloc(2);
-		best_table[i].str[0] = best_table[i].len ? i : 0;
+		best_table[i].len = best_table[i].refs ? 1 : 0;
+		best_table[i].str[0] = best_table[i].refs ? i : 0;
 		best_table[i].str[1] = 0;
 	}
 }
-- 
2.39.5

[PATCH v3 next 13/13] scripts/kallsyms: Reuse little-used compression tokens

[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 3% on both the 'normal'
kernel I'm building and on the x86-64 allyesconfig kernel.
Since the compression ration is about 50% this is a 6% reduction.

For simplicity the code will only expand tokens where the two tokens
that were merged are still in the table and tokens that expand to
three characters (which are never removed).

It is possible to find some others, but the cost of locating them
adds completity and slows down the build and the gains are limited.

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

v3:
- Formally patch 15, rebased on 7.4-rc1
- Additionally support splitting tokens that contain three characters.

 scripts/kallsyms.c | 223 +++++++++++++++++++++++++++++++++++++++------
 1 file changed, 196 insertions(+), 27 deletions(-)

diff --git a/scripts/kallsyms.c b/scripts/kallsyms.c
index 2f517873e9b4..8370347a9ab0 100644
--- a/scripts/kallsyms.c
+++ b/scripts/kallsyms.c
@@ -91,7 +91,10 @@ static struct sym_arr token_syms[NR_TOKENS];
 static struct best_table {
 	char           *str;		/* Full expansion, '\0' terminated */
 	unsigned short len;		/* Length of str */
+	unsigned short token;		/* Original token pair for this entry */
+	unsigned char  splits;		/* Number of times this token has been split */
 	unsigned int   refs;		/* Number of times used in a symbol */
+	struct sym_arr syms;		/* Symbols using this token (if len != 1) */
 } best_table[256];
 
 static void stamp(const char *where)
@@ -111,11 +114,6 @@ static void stamp(const char *where)
 			where, delta / 10, delta % 10);
 }
 
-static unsigned int sym_arr_last(const struct sym_arr *arr)
-{
-	return arr->cnt ? arr->sym_indexes[arr->cnt - 1] : UINT_MAX;
-}
-
 static void sym_arr_maybe_expand(struct sym_arr *arr)
 {
 	if (arr->cap > arr->cnt)
@@ -126,10 +124,55 @@ static void sym_arr_maybe_expand(struct sym_arr *arr)
 				    arr->cap * sizeof(*arr->sym_indexes));
 }
 
-static void sym_arr_add(struct sym_arr *arr, unsigned int sym_idx)
+static void sym_arr_add(struct sym_arr *sa, unsigned int sym_idx)
 {
-	sym_arr_maybe_expand(arr);
-	arr->sym_indexes[arr->cnt++] = sym_idx;
+	unsigned int cnt = sa->cnt;
+	unsigned int lo, hi, try;
+	unsigned int *syms;
+
+	/* Ensure there is space to add a new entry */
+	sym_arr_maybe_expand(sa);
+	syms = sa->sym_indexes;
+
+	/* Mostly we are adding a new symbol in number order */
+	if (!cnt || sym_idx > syms[cnt - 1]) {
+		syms[cnt] = sym_idx;
+		sa->cnt = cnt + 1;
+		return;
+	}
+
+	/* Or we found the same pair of characters twice in the same symbol */
+	if (sym_idx == syms[cnt - 1])
+		return;
+
+	/* split_token() can generate an out of order reference, insert. */
+	if (sym_idx <= syms[0]) {
+		if (sym_idx == syms[0])
+			return;
+		try = 0;
+	} else {
+		lo = 0;
+		hi = cnt - 1;
+		for (;;) {
+			try = (lo + hi) / 2;
+			if (sym_idx == syms[try])
+				/* Already present - common. */
+				return;
+			if (try == lo)
+				break;
+			if (sym_idx > syms[try])
+				lo = try;
+			else
+				hi = try;
+		}
+		try++;
+	}
+
+	/* Insert before syms[try] */
+	syms += try;
+	memmove(syms + 1, syms, (cnt - try) * sizeof(*syms));
+	*syms = sym_idx;
+	sa->cnt = cnt + 1;
 }
 
 static void sym_arr_free(struct sym_arr *arr)
@@ -140,6 +183,15 @@ static void sym_arr_free(struct sym_arr *arr)
 	arr->cap = 0;
 }
 
+static void sym_arr_prealloc(struct sym_arr *sa, unsigned int count)
+{
+	if (sa->cap >= count)
+		return;
+
+	sa->cap = count;
+	sa->sym_indexes = xrealloc(sa->sym_indexes, count * sizeof(sa->sym_indexes[0]));
+}
+
 static char *sym_entry_name(const struct sym_entry *s)
 {
 	return (char *)s->sym + 1;
@@ -724,13 +776,7 @@ static void learn_symbol(const unsigned char *symbol, int len)
 
 static void token_add_symbol(unsigned int token_idx, unsigned int sym_idx)
 {
-	struct sym_arr *arr = &token_syms[token_idx];
-
-	/* Symbol indexes kept in sorted order, check for duplicate. */
-	if (sym_arr_last(arr) == sym_idx)
-		return;
-
-	sym_arr_add(arr, sym_idx);
+	sym_arr_add(&token_syms[token_idx], sym_idx);
 }
 
 static unsigned int sym_arr_free_all(unsigned int ch)
@@ -779,16 +825,8 @@ static void build_initial_token_table(void)
 	 * The initial occurrence counts tell us exactly how much memory should
 	 * be reserved for each token's symbol array.
 	 */
-	for (i = 0; i < ARRAY_SIZE(token_syms); i++) {
-		const int nr_syms = token_profit[i];
-
-		if (!nr_syms)
-			continue;
-
-		token_syms[i].cap = nr_syms;
-		token_syms[i].sym_indexes =
-			xmalloc(nr_syms * sizeof(unsigned int));
-	}
+	for (i = 0; i < ARRAY_SIZE(token_syms); i++)
+		sym_arr_prealloc(&token_syms[i], token_profit[i]);
 
 	/* For every symbol, index every token -> symbol it is present in. */
 	for (i = 0; i < table_cnt; i++)
@@ -819,6 +857,8 @@ compress_symbols(unsigned int token_idx, int compressed_chr)
 	unsigned char *sym, *p, *end;
 	struct sym_entry *se;
 
+	sym_arr_prealloc(&best_table[compressed_chr].syms, token_profit[token_idx]);
+
 	/* Iterate through all symbols this token is found in and compress. */
 	for (j = 0; j < arr->cnt; j++) {
 		sym_idx = arr->sym_indexes[j];
@@ -839,7 +879,11 @@ compress_symbols(unsigned int token_idx, int compressed_chr)
 			adjust_profit(sym_idx, token_second(token_idx), compressed_chr, p[2], p[2]);
 			memmove(p + 1, p + 2, len);
 		}
+		if (se->len == end - sym)
+			/* No substitutions. */
+			continue;
 		se->len = end - sym;
+		sym_arr_add(&best_table[compressed_chr].syms, sym_idx);
 	}
 
 	/* No symbol contains this token any more. */
@@ -850,6 +894,123 @@ compress_symbols(unsigned int token_idx, int compressed_chr)
 	return subs;
 }
 
+/* Change every occurance of idx back to token_pair/triple.
+ * This extends all the symbol table entries but frees up a token. */
+static __attribute__((noinline)) void
+uncompress_symbols(unsigned int token_pair, int idx)
+{
+	struct best_table *bt = best_table + idx;
+	unsigned int sym_idx, len;
+	unsigned char *sym, *p, *end;
+	unsigned int substitutions;
+	unsigned int third_char;
+
+	third_char = token_pair >> 16;
+	token_pair &= 0xffff;
+
+	for (int j = 0; j < bt->syms.cnt; j++) {
+		sym_idx = bt->syms.sym_indexes[j];
+
+		sym = table[sym_idx]->sym;
+		len = table[sym_idx]->len;
+		end = sym + len;
+
+		for (p = sym; (p = memchr(p, idx, len)); p += 2) {
+			len = end - p - 1;
+			if (len) {
+				if (third_char) {
+					/* Adding three characters */
+					adjust_profit(sym_idx, idx, third_char, p[1], p[1]);
+					memmove(p + 3, p + 1, len);
+				} else {
+					adjust_profit(sym_idx, idx, token_second(token_pair), p[1], p[1]);
+					memmove(p + 2, p + 1, len);
+				}
+			}
+			if (p != sym)
+				adjust_profit(sym_idx, p[-1], p[-1], idx, token_first(token_pair));
+			token_add_symbol(token_pair, sym_idx);
+			p[0] = token_first(token_pair);
+			p[1] = token_second(token_pair);
+			end++;
+			if (third_char) {
+				token_add_symbol(token_index(p[1], third_char), sym_idx);
+				p[2] = third_char;
+				end++;
+				p++;
+			}
+		}
+		table[sym_idx]->len = end - sym;
+	}
+
+	substitutions = bt->refs;
+
+	bt->refs = 0;
+	bt->syms.cnt = 0;
+	sym_arr_free_all(idx);
+
+	token_profit[token_pair] += substitutions;
+	best_table[token_first(token_pair)].refs += substitutions;
+	best_table[token_second(token_pair)].refs += substitutions;
+
+	if (third_char) {
+		best_table[third_char].refs += substitutions;
+		token_profit[token_index(token_second(token_pair), third_char)] += substitutions;
+	}
+}
+
+static int split_token(unsigned int profit)
+{
+	struct best_table *bt, *first, *second;
+	const unsigned int max_splits = 10;
+	unsigned int i, best_token;
+	int best_ch = -1;
+
+	for (i = 0; i < 256; i++) {
+		bt = best_table + i;
+
+		if (bt->len == 1 || bt->refs >= profit || bt->splits >= max_splits)
+			continue;
+
+		/* Ignore tokens where the original parts have been reused ... */
+		first = &best_table[token_first(bt->token)];
+		second = &best_table[token_second(bt->token)];
+		if (bt->len != first->len + second->len ||
+		    memcmp(bt->str, first->str, first->len) ||
+		    memcmp(bt->str + first->len, second->str, second->len)) {
+			/* ... unless they are three characters. */
+			if (bt->len != 3 || bt->refs * 2 >= profit) {
+				/* Don't consider again */
+				bt->splits = max_splits;
+				continue;
+			}
+			best_token = token_index(bt->str[0], bt->str[1]) | bt->str[2] << 16;
+			profit = bt->refs * 2;
+		} else {
+			best_token = bt->token;
+			profit = bt->refs;
+		}
+
+		best_ch = i;
+	}
+	if (best_ch < 0)
+		return -1;
+
+	/*
+	 * Triplets (eg foo_xxx_bar) count as two pairs (in token_profit[]) but
+	 * the substitution only saves one byte making the recently merged token
+	 * a candidate for splitting again. This might cause an infinite loop.
+	 * But I have seen t_/alloc_tag get merged then t_alloc_tag/_cntr merged
+	 * leaving a single referece to t_alloc_tag - so it is split again.
+	 * So only allow a token to be split a few times.
+	 */
+	best_table[best_ch].splits++;
+
+	uncompress_symbols(best_token, best_ch);
+
+	return best_ch;
+}
+
 /* search the token with the maximum profit */
 static int find_best_token(void)
 {
@@ -882,17 +1043,25 @@ static void optimize_result(void)
 			to_process[idx++] = i;
 	}
 
-	while (idx) {
+	for (;;) {
 		/* find the token that appears most often */
 		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 in all the valid symbols. */
 		refs = compress_symbols(best, i);
 
 		bt = best_table + i;
+		bt->token = best;
 		first = best_table + token_first(best);
 		second = best_table + token_second(best);
 
-- 
2.39.5