[PATCH v2 03/21] kallsyms: output binary data to speed output and kallsyms assembly

["Lorenzo Stoakes (ARM)" <ljs@kernel.org>]

kallsyms generates an assembly file that consists mostly of .byte entries
containing compressed names, token strings and name-sorted sequence
numbers.

For an x86-64 build with 158k symbols that is a 37 MiB .S file which takes
0.57s to assemble each of the two to three times it is built over a kernel
build.

Each time it is generated it also takes kallsyms a similar amount of time
to output it.

Avoid this overhead by instead outputting this data as binary and importing
it into the assembly using the .incbin directive.

Tables that are wider than a byte remain part of the assembly to ensure
endianness and relative relocations are performed correctly.

With this change, the output assembly file shrinks from 37 MiB to 9.8 MiB,
with a 2.6 MiB binary data file alongside it, and the object remains
identical.

The generated binary file is deleted correctly on build clean along with
all other ephemeral data.

On an x86-64 system with CONFIG_KALLSYMS_ALL set:

                       before   after    delta
  scripts/kallsyms     0.24s    0.18s    0.06s
  assemble             0.57s    0.16s    0.41s

Per kallsyms invocation/assembly, for a total of 0.47s time saving upon
invocation.

An incremental build on the same system was reduced from 11.15s to 9.65s,
indicating a total of 1.5 seconds saved over the build.

The kallsyms runs and their assembly are on the serial tail of every build
that links vmlinux, no-op builds are unchanged.

Whole build, 128-thread Threadripper 9980X, best of N runs:

                                         before   after     delta
                                         -------------------------------
  x86 defconfig, touch mm/vma.c, gcc       10.6s     9.7s    -0.89s (-8%)
  x86 defconfig, touch mm/vma.c, clang     10.5s     9.3s     -1.2s (-11%)
  x86 defconfig, clean, gcc                31.3s    30.3s     -1.0s (-3%)
  x86 defconfig, clean, clang              33.3s    31.7s     -1.6s (-5%)
  x86 allmodconfig, touch mm/vma.c, gcc    38.7s    37.2s     -1.4s (-4%)
  x86 allmodconfig, touch mm/vma.c, clang  39.1s    36.4s     -2.6s (-7%)

Assisted-by: LLM
Signed-off-by: Lorenzo Stoakes (ARM) <ljs@kernel.org>
---
 scripts/kallsyms.c      | 84 ++++++++++++++++++++++++++++++++++++-------------
 scripts/link-vmlinux.sh |  2 +-
 2 files changed, 64 insertions(+), 22 deletions(-)

diff --git a/scripts/kallsyms.c b/scripts/kallsyms.c
index 350d118c3b9e..89f5207f74d2 100644
--- a/scripts/kallsyms.c
+++ b/scripts/kallsyms.c
@@ -5,7 +5,10 @@
  * 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] in.map > out.S
+ * Usage: kallsyms [--all-symbols] [--pc-relative] in.map out.bin > out.S
+ *
+ *      The byte tables go to out.bin and are pulled into out.S with .incbin;
+ *  wider tables stay assembler source for endianness and relocations.
  *
  *      Table compression uses all the unused char codes on the symbols and
  *  maps these to the most used substrings (tokens). For instance, it might
@@ -102,7 +105,7 @@ static void sym_arr_free(struct sym_arr *arr)
 
 static void usage(void)
 {
-	fprintf(stderr, "Usage: kallsyms [--all-symbols] in.map > out.S\n");
+	fprintf(stderr, "Usage: kallsyms [--all-symbols] [--pc-relative] in.map out.bin > out.S\n");
 	exit(1);
 }
 
@@ -319,6 +322,26 @@ static void output_label(const char *label)
 	printf("%s:\n", label);
 }
 
+static long bin_pos(FILE *file)
+{
+	const long pos = ftell(file);
+
+	if (pos < 0) {
+		perror("kallsyms: ftell");
+		exit(EXIT_FAILURE);
+	}
+
+	return pos;
+}
+
+static void write_incbin(const char *filename, long start, long end)
+{
+	if (start >= end)
+		return;
+
+	printf("\t.incbin \"%s\", %ld, %ld\n", filename, start, end - start);
+}
+
 /* 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)
@@ -371,11 +394,12 @@ static void sort_symbols_by_name(void)
 	qsort(table, table_cnt, sizeof(table[0]), compare_names);
 }
 
-static void write_src(void)
+static void write_src(FILE *out_bin_file, const char *out_bin_name)
 {
-	unsigned int i, k, off;
+	unsigned int i, off;
 	unsigned int best_idx[256];
 	unsigned int *markers, markers_cnt;
+	long bin_start;
 	char buf[KSYM_NAME_LEN];
 
 	printf("\t.section .rodata, \"a\"\n");
@@ -390,6 +414,7 @@ static void write_src(void)
 	markers = xmalloc(sizeof(*markers) * markers_cnt);
 
 	output_label("kallsyms_names");
+	bin_start = bin_pos(out_bin_file);
 	off = 0;
 	for (i = 0; i < table_cnt; i++) {
 		if ((i & 0xFF) == 0)
@@ -413,26 +438,24 @@ static void write_src(void)
 		/* Encode length with ULEB128. */
 		if (table[i]->len <= 0x7F) {
 			/* Most symbols use a single byte for the length. */
-			printf("\t.byte 0x%02x", table[i]->len);
+			fputc(table[i]->len, out_bin_file);
 			off += table[i]->len + 1;
 		} else {
 			/* "Big" symbols use two bytes. */
-			printf("\t.byte 0x%02x, 0x%02x",
-				(table[i]->len & 0x7F) | 0x80,
-				(table[i]->len >> 7) & 0x7F);
+			fputc((table[i]->len & 0x7F) | 0x80, out_bin_file);
+			fputc((table[i]->len >> 7) & 0x7F, out_bin_file);
 			off += table[i]->len + 2;
 		}
-		for (k = 0; k < table[i]->len; k++)
-			printf(", 0x%02x", table[i]->sym[k]);
+		fwrite(table[i]->sym, 1, table[i]->len, out_bin_file);
 
 		/*
 		 * Now that we wrote out the compressed symbol name, restore the
-		 * original name and print it in the comment.
+		 * original name for the comments below.
 		 */
 		expand_symbol(table[i]->sym, table[i]->len, buf);
 		strcpy((char *)table[i]->sym, buf);
-		printf("\t/* %s */\n", table[i]->sym);
 	}
+	write_incbin(out_bin_name, bin_start, bin_pos(out_bin_file));
 	printf(".size kallsyms_names, . - kallsyms_names\n");
 	printf("\n");
 
@@ -445,13 +468,15 @@ static void write_src(void)
 	free(markers);
 
 	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);
-		printf("\t.asciz\t\"%s\"\n", 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");
 
@@ -484,12 +509,13 @@ static void write_src(void)
 
 	sort_symbols_by_name();
 	output_label("kallsyms_seqs_of_names");
-	for (i = 0; i < table_cnt; i++)
-		printf("\t.byte 0x%02x, 0x%02x, 0x%02x\t/* %s */\n",
-			(unsigned char)(table[i]->seq >> 16),
-			(unsigned char)(table[i]->seq >> 8),
-			(unsigned char)(table[i]->seq >> 0),
-		       table[i]->sym);
+	bin_start = bin_pos(out_bin_file);
+	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);
+	}
+	write_incbin(out_bin_name, bin_start, bin_pos(out_bin_file));
 	printf("\n");
 }
 
@@ -798,6 +824,9 @@ static void sort_symbols(void)
 
 int main(int argc, char **argv)
 {
+	const char *out_bin_name;
+	FILE *out_bin_file;
+
 	while (1) {
 		static const struct option long_options[] = {
 			{"all-symbols",     no_argument, &all_symbols,     1},
@@ -813,14 +842,27 @@ int main(int argc, char **argv)
 			usage();
 	}
 
-	if (optind >= argc)
+	if (optind + 2 != argc)
 		usage();
 
+	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);
+	}
+
 	read_map(argv[optind]);
 	shrink_table();
 	sort_symbols();
 	optimize_token_table();
-	write_src();
+	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);
+	}
 
 	return 0;
 }
diff --git a/scripts/link-vmlinux.sh b/scripts/link-vmlinux.sh
index ab0b8125c8cb..e88604150d2c 100755
--- a/scripts/link-vmlinux.sh
+++ b/scripts/link-vmlinux.sh
@@ -132,7 +132,7 @@ kallsyms()
 	fi
 
 	info KSYMS "${2}.S"
-	scripts/kallsyms ${kallsymopt} "${1}" > "${2}.S"
+	scripts/kallsyms ${kallsymopt} "${1}" "${2}.bin" > "${2}.S"
 
 	info AS "${2}.o"
 	${CC} ${NOSTDINC_FLAGS} ${LINUXINCLUDE} ${KBUILD_CPPFLAGS} \

-- 
2.55.0