Skip to contentSkip to conversation

Single pass kallsyms v3

PATCH In review Andi Kleen 2 participants 9 messages Feb 18, 2014

Subsystems (2)
lore
Share & tools
lore

Andi Kleen

author
#0 lore raw

Updated patchkit to enable single-pass kallsyms. This avoids linking multiple times. Needed for the link time optimization patchkit, but also useful on its own to get faster builds.

This version addresses Sam's review comments.

-Andi

author
#1 lore raw

PATCH 1/6 kbuild: Remove relocations from kallsyms table

From: Andi Kleen <[email protected]>

Remove the ELF relocations from the kallsyms_address[] table. Instead we just store offsets to _text and relocate that while accessing the kallsyms table. This is done with a new kallsyms_offsets[] table. With these changes .tmp_kallsyms*.o becomes relocation free.

In theory this would also allow to shrink the kallsyms table on 64bit by using offsets.

---
 kernel/kallsyms.c  | 27 ++++++++++++++++-----------
 scripts/kallsyms.c | 18 ++++++------------
 2 files changed, 22 insertions(+), 23 deletions(-)
kernel/kallsyms.c +16 -11
index 3127ad5..e7d7844 100644
@@ -36,7 +36,7 @@
  * These will be re-linked against their real values
  * during the second link stage.
  */
-extern const unsigned long kallsyms_addresses[] __attribute__((weak));
+extern const long kallsyms_offsets[] __attribute__((weak));
 extern const u8 kallsyms_names[] __attribute__((weak));
 
 /*
@@ -51,6 +51,11 @@ extern const u16 kallsyms_token_index[] __attribute__((weak));
 
 extern const unsigned long kallsyms_markers[] __attribute__((weak));
 
+static inline unsigned long kallsyms_address(int ind)
+{
+	return (unsigned long)RELOC_HIDE(&_text, kallsyms_offsets[ind]);
+}
+
 static inline int is_kernel_inittext(unsigned long addr)
 {
 	if (addr >= (unsigned long)_sinittext
@@ -186,7 +191,7 @@ unsigned long kallsyms_lookup_name(const char *name)
 		off = kallsyms_expand_symbol(off, namebuf, ARRAY_SIZE(namebuf));
 
 		if (strcmp(namebuf, name) == 0)
-			return kallsyms_addresses[i];
+			return kallsyms_address(i);
 	}
 	return module_kallsyms_lookup_name(name);
 }
@@ -203,7 +208,7 @@ int kallsyms_on_each_symbol(int (*fn)(void *, const char *, struct module *,
 
 	for (i = 0, off = 0; i < kallsyms_num_syms; i++) {
 		off = kallsyms_expand_symbol(off, namebuf, ARRAY_SIZE(namebuf));
-		ret = fn(data, namebuf, NULL, kallsyms_addresses[i]);
+		ret = fn(data, namebuf, NULL, kallsyms_address(i));
 		if (ret != 0)
 			return ret;
 	}
@@ -219,15 +224,15 @@ static unsigned long get_symbol_pos(unsigned long addr,
 	unsigned long i, low, high, mid;
 
 	/* This kernel should never had been booted. */
-	BUG_ON(!kallsyms_addresses);
+	BUG_ON(!kallsyms_offsets);
 
-	/* Do a binary search on the sorted kallsyms_addresses array. */
+	/* Do a binary search on the sorted kallsyms_offsets array. */
 	low = 0;
 	high = kallsyms_num_syms;
 
 	while (high - low > 1) {
 		mid = low + (high - low) / 2;
-		if (kallsyms_addresses[mid] <= addr)
+		if (kallsyms_address(mid) <= addr)
 			low = mid;
 		else
 			high = mid;
@@ -237,15 +242,15 @@ static unsigned long get_symbol_pos(unsigned long addr,
 	 * Search for the first aliased symbol. Aliased
 	 * symbols are symbols with the same address.
 	 */
-	while (low && kallsyms_addresses[low-1] == kallsyms_addresses[low])
+	while (low && kallsyms_address(low - 1) == kallsyms_address(low))
 		--low;
 
-	symbol_start = kallsyms_addresses[low];
+	symbol_start = kallsyms_address(low);
 
 	/* Search for next non-aliased symbol. */
 	for (i = low + 1; i < kallsyms_num_syms; i++) {
-		if (kallsyms_addresses[i] > symbol_start) {
-			symbol_end = kallsyms_addresses[i];
+		if (kallsyms_address(i) > symbol_start) {
+			symbol_end = kallsyms_address(i);
 			break;
 		}
 	}
@@ -469,7 +474,7 @@ static unsigned long get_ksymbol_core(struct kallsym_iter *iter)
 	unsigned off = iter->nameoff;
 
 	iter->module_name[0] = '\0';
-	iter->value = kallsyms_addresses[iter->pos];
+	iter->value = kallsyms_address(iter->pos);
 
 	iter->type = kallsyms_get_symbol_type(off);
 
scripts/kallsyms.c +6 -12
index 10085de..56f5986 100644
@@ -190,7 +190,7 @@ static int symbol_valid(struct sym_entry *s)
 	 * specified so exclude them to get a stable symbol list.
 	 */
 	static char *special_symbols[] = {
-		"kallsyms_addresses",
+		"kallsyms_offsets",
 		"kallsyms_num_syms",
 		"kallsyms_names",
 		"kallsyms_markers",
@@ -322,19 +322,13 @@ static void write_src(void)
 	 * symbols that are declared static and are private to their
 	 * .o files.  This prevents .tmp_kallsyms.o or any other
 	 * object from referencing them.
+	 *
+	 * We do the offsets to _text now in kallsyms.c at runtime,
+	 * to get a relocationless symbol table.
 	 */
-	output_label("kallsyms_addresses");
+	output_label("kallsyms_offsets");
 	for (i = 0; i < table_cnt; i++) {
-		if (toupper(table[i].sym[0]) != 'A') {
-			if (_text <= table[i].addr)
-				printf("\tPTR\t_text + %#llx\n",
-					table[i].addr - _text);
-			else
-				printf("\tPTR\t_text - %#llx\n",
-					_text - table[i].addr);
-		} else {
-			printf("\tPTR\t%#llx\n", table[i].addr);
-		}
+		printf("\tPTR\t%#llx\n", table[i].addr - _text);
 	}
 	printf("\n");
 
Signature · 1 line
1.8.5.2
#2 lore raw

Re: [PATCH 1/6] kbuild: Remove relocations from kallsyms table

Quoted 11 lines · Andi Kleen

From: Andi Kleen <[email protected]>

Remove the ELF relocations from the kallsyms_address[] table. Instead we just store offsets to _text and relocate that while accessing the kallsyms table. This is done with a new kallsyms_offsets[] table. With these changes .tmp_kallsyms*.o becomes relocation free.

In theory this would also allow to shrink the kallsyms table on 64bit by using offsets.

Why not do that, then?

-hpa

author
#3 lore raw

Re: [PATCH 1/6] kbuild: Remove relocations from kallsyms table

Quoted 9 lines · H. Peter Anvin
Quoted 8 lines · Andi Kleen

From: Andi Kleen <[email protected]>

Remove the ELF relocations from the kallsyms_address[] table. Instead we just store offsets to _text and relocate that while accessing the kallsyms table. This is done with a new kallsyms_offsets[] table. With these changes .tmp_kallsyms*.o becomes relocation free.

Quoted 5 lines
Quoted 3 lines

In theory this would also allow to shrink the kallsyms table on 64bit by using offsets.

Why not do that, then?

I tried it once, but it didn't boot for some reason. Didn't have time to track it down so I removed it. Could be done as followon work.

-Andi

author
#4 lore raw

PATCH 2/6 kbuild: Put kallsyms into own section

In reply to Andi Kleen

From: Andi Kleen <[email protected]>

Put the kallsyms information into an own .kallsyms section. This makes it easier to patch the kallsyms inside the executable. Otherwise it shouldn't change anything.

---
 include/asm-generic/vmlinux.lds.h | 4 ++++
 scripts/kallsyms.c                | 2 +-
 2 files changed, 5 insertions(+), 1 deletion(-)
include/asm-generic/vmlinux.lds.h +4 -0
index bc2121f..6214f18 100644
@@ -280,6 +280,10 @@
 									\
 	TRACEDATA							\
 									\
+	.kallsyms          : AT(ADDR(.kallsyms) - LOAD_OFFSET) {	\
+		*(.kallsyms)						\
+	}								\
+									\
 	/* Kernel symbol table: Normal symbols */			\
 	__ksymtab         : AT(ADDR(__ksymtab) - LOAD_OFFSET) {		\
 		VMLINUX_SYMBOL(__start___ksymtab) = .;			\
scripts/kallsyms.c +1 -1
index 56f5986..ceef756 100644
@@ -314,7 +314,7 @@ static void write_src(void)
 	printf("#define ALGN .align 4\n");
 	printf("#endif\n");
 
-	printf("\t.section .rodata, \"a\"\n");
+	printf("\t.section .kallsyms, \"a\"\n");
 
 	/* Provide proper symbols relocatability by their '_text'
 	 * relativeness.  The symbol names cannot be used to construct
Signature · 1 line
1.8.5.2
author
#5 lore raw

PATCH 3/6 kbuild: Don't include const variable in kallsyms with !KALLSYMS_ALL

In reply to Andi Kleen

From: Andi Kleen <[email protected]>

const variables are put into the text segment, so !KALLSYMS_ALL includes them into the kallsyms section. Remove them to make the kallsyms smaller. This also avoids some problems with LTO. The way LTO generates the first pass kallsyms cannot handle variables currently, so if we don't filter them out the first and second level pass differ too much.

---
 scripts/kallsyms.c | 5 +++++
 1 file changed, 5 insertions(+)
scripts/kallsyms.c +5 -0
index ceef756..d79027e 100644
@@ -151,6 +151,11 @@ static int read_symbol(FILE *in, struct sym_entry *s)
 	/* exclude debugging symbols */
 	else if (stype == 'N')
 		return -1;
+	/* Don't include const symbols in the text section
+	 * unless --all-symbols is specified.
+	 */
+	else if (toupper(stype) != 'T' && !all_symbols)
+		return -1;
 
 	/* include the type field in the symbol name, so that it gets
 	 * compressed together */
Signature · 1 line
1.8.5.2
author
#6 lore raw

PATCH 4/6 kbuild: Support padding in kallsyms tables v2

In reply to Andi Kleen

From: Andi Kleen <[email protected]>

Add support for padding the variable length tables in kallsyms. This adds a new --pad=XXX option to kallsyms to specify the table lengths, and another option --pad-file=X to write the table lengths to a file. Then when a table is shorter than the padding add the necessary padding at the end.

This allows to replace an existing symbol table later with a different one that may differ slightly.

Add 5% slack for now in case the prediction is too small (can happen with LTO)

v2: Fix build error, found by Markus Trippelsdorf.

---
 scripts/kallsyms.c | 93 ++++++++++++++++++++++++++++++++++++++++++++++++++++--
 1 file changed, 90 insertions(+), 3 deletions(-)
scripts/kallsyms.c +90 -3
index d79027e..293c9eb 100644
@@ -23,6 +23,13 @@
 #include <string.h>
 #include <ctype.h>
 
+/*
+ * The ratio to increase the padding, by how much the final kallsyms
+ * can be larger. This is for symbols that are not visible before
+ * final linking.
+ */
+#define PAD_RATIO 20 /* 1/x = ~5% */
+
 #ifndef ARRAY_SIZE
 #define ARRAY_SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
 #endif
@@ -41,6 +48,14 @@ struct text_range {
 	unsigned long long start, end;
 };
 
+enum pads {
+	PAD_OFF,
+	PAD_NAMES,
+	PAD_MARKERS,
+	PAD_TOKTAB,
+	NUM_PAD
+};
+
 static unsigned long long _text;
 static struct text_range text_ranges[] = {
 	{ "_stext",     "_etext"     },
@@ -69,6 +84,7 @@ static void usage(void)
 	fprintf(stderr, "Usage: kallsyms [--all-symbols] "
 			"[--symbol-prefix=<prefix char>] "
 			"[--page-offset=<CONFIG_PAGE_OFFSET>] "
+			"[--pad=A,B,C] [--pad-file=name] "
 			"< in.map > out.S\n");
 	exit(1);
 }
@@ -303,7 +319,14 @@ static int expand_symbol(unsigned char *data, int len, char *result)
 	return total;
 }
 
-static void write_src(void)
+static void bad_padding(char *msg, int diff)
+{
+	fprintf(stderr, "kallsyms: %s padding too short: %d missing\n",
+			msg, diff);
+	exit(EXIT_FAILURE);
+}
+
+static void write_src(int *pad, int *opad)
 {
 	unsigned int i, k, off;
 	unsigned int best_idx[256];
@@ -335,6 +358,16 @@ static void write_src(void)
 	for (i = 0; i < table_cnt; i++) {
 		printf("\tPTR\t%#llx\n", table[i].addr - _text);
 	}
+	if (pad) {
+		if (i > pad[PAD_OFF])
+			bad_padding("address pointers", i - pad[PAD_OFF]);
+		for (; i < pad[PAD_OFF]; i++)
+			printf("\tPTR\t0\n");
+	} else {
+		for (i = 0; i < table_cnt / PAD_RATIO; i++)
+			printf("\tPTR\t0\n");
+		opad[PAD_OFF] = table_cnt + table_cnt/PAD_RATIO;
+	}
 	printf("\n");
 
 	output_label("kallsyms_num_syms");
@@ -363,11 +396,31 @@ static void write_src(void)
 
 		off += table[i].len + 1;
 	}
+	if (pad) {
+		if (off > pad[PAD_NAMES])
+			bad_padding("name table", off - pad[PAD_NAMES]);
+		if (off < pad[PAD_NAMES])
+			printf("\t.fill %d,1,0\n", pad[PAD_NAMES] - off);
+	} else {
+		printf("\t.fill %d,1,0\n", off/PAD_RATIO);
+		off += off/PAD_RATIO;
+		opad[PAD_NAMES] = off;
+	}
 	printf("\n");
 
 	output_label("kallsyms_markers");
 	for (i = 0; i < ((table_cnt + 255) >> 8); i++)
 		printf("\tPTR\t%d\n", markers[i]);
+	if (pad) {
+		if (i > pad[PAD_MARKERS])
+			bad_padding("markers", i - pad[PAD_MARKERS]);
+		for (; i < pad[PAD_MARKERS]; i++)
+			printf("\tPTR\t0\n");
+	} else {
+		for (k = 0; k < i/PAD_RATIO; k++)
+			printf("\tPTR\t0\n");
+		opad[PAD_MARKERS] = i + i/PAD_RATIO;
+	}
 	printf("\n");
 
 	free(markers);
@@ -380,6 +433,16 @@ static void write_src(void)
 		printf("\t.asciz\t\"%s\"\n", buf);
 		off += strlen(buf) + 1;
 	}
+	if (pad) {
+		if (off > pad[PAD_TOKTAB])
+			bad_padding("token table", off - pad[PAD_TOKTAB]);
+		if (off < pad[PAD_TOKTAB])
+			printf("\t.fill %d,1,0\n", pad[PAD_TOKTAB] - off);
+	} else {
+		printf("\t.fill %d,1,0\n", off/PAD_RATIO);
+		off += off/PAD_RATIO;
+		opad[PAD_TOKTAB] = off;
+	}
 	printf("\n");
 
 	output_label("kallsyms_token_index");
@@ -647,6 +710,10 @@ static void sort_symbols(void)
 
 int main(int argc, char **argv)
 {
+	int inpad[NUM_PAD], opad[NUM_PAD];
+	int *inpadp = NULL;
+	FILE *opadf = NULL;
+
 	if (argc >= 2) {
 		int i;
 		for (i = 1; i < argc; i++) {
@@ -661,6 +728,22 @@ int main(int argc, char **argv)
 			} else if (strncmp(argv[i], "--page-offset=", 14) == 0) {
 				const char *p = &argv[i][14];
 				kernel_start_addr = strtoull(p, NULL, 16);
+			} else if (strncmp(argv[i], "--pad=", 6) == 0) {
+				inpadp = inpad;
+				if (sscanf(argv[i] + 6, "%d,%d,%d,%d",
+					   inpad + 0,
+					   inpad + 1,
+					   inpad + 2,
+					   inpad + 3) != NUM_PAD) {
+					fprintf(stderr, "Bad pad list\n");
+					exit(EXIT_FAILURE);
+				}
+			} else if (strncmp(argv[i], "--pad-file=", 11) == 0) {
+				opadf = fopen(argv[i] + 11, "w");
+				if (!opadf) {
+					fprintf(stderr, "Cannot open %s", argv[i]+11);
+					exit(EXIT_FAILURE);
+				}
 			} else
 				usage();
 		}
@@ -670,7 +753,11 @@ int main(int argc, char **argv)
 	read_map(stdin);
 	sort_symbols();
 	optimize_token_table();
-	write_src();
-
+	write_src(inpadp, opad);
+	if (opadf) {
+		fprintf(opadf, "--pad=%d,%d,%d,%d\n",
+			opad[0], opad[1], opad[2], opad[3]);
+		fclose(opadf);
+	}
 	return 0;
 }
Signature · 1 line
1.8.5.2
author
#7 lore raw

PATCH 5/6 kbuild: Use single pass kallsyms

In reply to Andi Kleen

From: Andi Kleen <[email protected]>

kallsyms currenly links the kernel upto three times (in addition to another one for modpost checks)

Linking can be a quite slow operation, especially when the kernel has a lot of debug information (lots of IO), or Link Time Optimization is used.

Final linking is also a non parallelizable bottlneck, so it's always good to do it less.

Use a different kallsyms method to avoid this:
- generate a initial kallsyms table from the top level object files
- This table is usually a super set of the final table, but without final addresses and some extra symbols (e.g. discard and local symbols)
- Use this table to link the vmlinux
- Then generate a new kallsyms table with padding so that all symbols stay at the same offsets. This works because the new table is smaller or the same than the original one.
We let the first kallsyms generate a padding file and then use it on the next link.
- Then finally patch in the new table into the vmlinux

The size difference between the two tables is typically small, so the additional padding is not a problem (a few hundred bytes in my kernels)

Right now we still do two links. One to generate the kernel, and another one to generate the vmlinux.o for modpost.

On my slowish laptop this cuts down the final serialized phase of a moderate size kernel build (just relinking vmlinux) by 1/3, from ~30s to 20s

Tested on x86, tests on other architectures would be appreciated.

---
 scripts/Makefile        |  2 +-
 scripts/elf_file_offset | 24 +++++++++++++
 scripts/kallsyms.c      | 10 ++++--
 scripts/link-vmlinux.sh | 92 ++++++++++++++++++++-----------------------------
 scripts/patchfile.c     | 81 +++++++++++++++++++++++++++++++++++++++++++
 5 files changed, 151 insertions(+), 58 deletions(-)
 create mode 100644 scripts/elf_file_offset
 create mode 100644 scripts/patchfile.c
scripts/Makefile +1 -1
index 01e7adb..9c84464 100644
@@ -10,7 +10,7 @@
 
 HOST_EXTRACFLAGS += -I$(srctree)/tools/include
 
-hostprogs-$(CONFIG_KALLSYMS)     += kallsyms
+hostprogs-$(CONFIG_KALLSYMS)     += kallsyms patchfile
 hostprogs-$(CONFIG_LOGO)         += pnmtologo
 hostprogs-$(CONFIG_VT)           += conmakehash
 hostprogs-$(CONFIG_IKCONFIG)     += bin2c
scripts/elf_file_offset new file +24 -0
new file mode 100644
index 0000000..2c8ee49
@@ -0,0 +1,24 @@
+#!/bin/bash
+# find the file offset of a section in a ELF file
+# objdump --section-headers elf-file |
+# gawk -f elf_file_offset filesize=SIZE section=SECTIONNAME
+# gawk needed for strtonum()
+#Idx Name          Size      VMA               LMA               File off  Algn
+#  4 .kallsyms     001fd648  ffffffff81b1c068  0000000001b1c068  00d1c068  2**3
+
+$2 == section {
+	old = strtonum("0x" $3)
+	new = strtonum(filesize)
+	if (old < new) {
+		print "Not enough padding in vmlinux for new kallsyms, missing",new-old > "/dev/stderr"
+		print "Please lower (=increase) PAD_RATIO in kallsyms.c"
+		exit 1
+	}
+	print "0x" $6
+	# XXX doesn't exit in gawk 4.1.0 ?!?
+	#exit(0)
+}
+#END {
+#    print section " not found" > "/dev/stderr"
+#    exit 1
+#}
scripts/kallsyms.c +8 -2
index 293c9eb..566e53e 100644
@@ -192,15 +192,19 @@ static int symbol_valid_tr(struct sym_entry *s)
 {
 	size_t i;
 	struct text_range *tr;
+	int valid = 0;
 
 	for (i = 0; i < ARRAY_SIZE(text_ranges); ++i) {
 		tr = &text_ranges[i];
 
+		if (tr->start && tr->end)
+			valid++;
+
 		if (s->addr >= tr->start && s->addr <= tr->end)
 			return 1;
 	}
 
-	return 0;
+	return valid ? 0 : 1;
 }
 
 static int symbol_valid(struct sym_entry *s)
@@ -242,11 +246,13 @@ static int symbol_valid(struct sym_entry *s)
 		 * the kallsyms data are added.  If these symbols move then
 		 * they may get dropped in pass 2, which breaks the kallsyms
 		 * rules.
+		 * But don't do this for predicted fake symbols with 0 value.
 		 */
-		if ((s->addr == text_range_text->end &&
+		if (((s->addr == text_range_text->end &&
 				strcmp((char *)s->sym + offset, text_range_text->etext)) ||
 		    (s->addr == text_range_inittext->end &&
 				strcmp((char *)s->sym + offset, text_range_inittext->etext)))
+			&& text_range_text->end != 0)
 			return 0;
 	}
 
scripts/link-vmlinux.sh +37 -55

120 lines not on this page · raw message

scripts/patchfile.c new file +81 -0

81 lines not on this page · raw message

Signature · 1 line
1.8.5.2
author
#8 lore raw

PATCH 6/6 kbuild: Remove .dot postfixes in kallsyms

In reply to Andi Kleen

From: Andi Kleen <[email protected]>

For static and some LTO symbols gcc generates .XXXX postfixes. Remove those from the kallsyms, as they are not useful to the user and makes it much larger. This also avoids some issues with LTO.

---
 scripts/kallsyms.c | 7 ++++++-
 1 file changed, 6 insertions(+), 1 deletion(-)
scripts/kallsyms.c +6 -1
index 566e53e..94e0502 100644
@@ -122,7 +122,7 @@ static int read_symbol_tr(const char *sym, unsigned long long addr)
 static int read_symbol(FILE *in, struct sym_entry *s)
 {
 	char str[500];
-	char *sym, stype;
+	char *sym, stype, *dot;
 	int rc;
 
 	rc = fscanf(in, "%llx %c %499s\n", &s->addr, &stype, str);
@@ -138,6 +138,11 @@ static int read_symbol(FILE *in, struct sym_entry *s)
 		return -1;
 	}
 
+	/* Drop static .XXXX postfixes */
+	dot = strchr(str, '.');
+	if (dot)
+		*dot = 0;
+
 	sym = str;
 	/* skip prefix char */
 	if (symbol_prefix_char && str[0] == symbol_prefix_char)
Signature · 1 line
1.8.5.2