[PATCH 0/4] support for text-relative kallsyms table

This implements text-relative kallsyms address tables. This was developed
as part of my series to implement KASLR/CONFIG_RELOCATABLE for arm64, but
I think it may be beneficial to other architectures as well, so I am
presenting it as a separate series.

The idea is that on 64-bit builds, it is rather wasteful to use absolute
addressing for kernel symbols since they are all within a couple of MBs
of each other. On top of that, the absolute addressing implies that, when
the kernel is relocated at runtime, each address in the table needs to be
fixed up individually.

Since all section-relative addresses are already emitted relative to _text,
it is quite straight-forward to record only the offset, and add the absolute
address of _text at runtime when referring to the address table.

The reduction ranges from around 250 KB uncompressed vmlinux size and 10 KB
compressed size (s390) to 3 MB/500 KB for ppc64 (although, in the latter case,
the reduction in uncompressed size is primarily __init data)

Kees Cook was so kind to test these against x86_64, and confirmed that KASLR
still operates as expected.

Ard Biesheuvel (4):
  kallsyms: add support for relative offsets in kallsyms address table
  powerpc: enable text relative kallsyms for ppc64
  s390: enable text relative kallsyms for 64-bit targets
  x86_64: enable text relative kallsyms for 64-bit targets

 arch/powerpc/Kconfig    |  1 +
 arch/s390/Kconfig       |  1 +
 arch/x86/Kconfig        |  1 +
 init/Kconfig            | 14 ++++++++
 kernel/kallsyms.c       | 35 +++++++++++++-----
 scripts/kallsyms.c      | 38 +++++++++++++++++---
 scripts/link-vmlinux.sh |  4 +++
 scripts/namespace.pl    |  1 +
 8 files changed, 82 insertions(+), 13 deletions(-)

-- 
2.5.0

Similar to how relative extables are implemented, it is possible to emit
the kallsyms table in such a way that it contains offsets relative to some
anchor point in the kernel image rather than absolute addresses. The benefit
is that such table entries are no longer subject to dynamic relocation when
the build time and runtime offsets of the kernel image are different. Also,
on 64-bit architectures, it essentially cuts the size of the address table
in half since offsets can typically be expressed in 32 bits.

Since it is useful for some architectures (like x86) to retain the ability
to emit absolute values as well, this patch adds support for both, by
emitting absolute addresses as positive 32-bit values, and addresses
relative to _text as negative values, which are subtracted from the runtime
address of _text to produce the actual address. Positive values are used as
they are found in the table.

Support for the above is enabled by setting CONFIG_KALLSYMS_TEXT_RELATIVE.

Signed-off-by: Ard Biesheuvel <redacted>
---
 init/Kconfig            | 14 ++++++++
 kernel/kallsyms.c       | 35 +++++++++++++-----
 scripts/kallsyms.c      | 38 +++++++++++++++++---
 scripts/link-vmlinux.sh |  4 +++
 scripts/namespace.pl    |  1 +
 5 files changed, 79 insertions(+), 13 deletions(-)

diff --git a/init/Kconfig b/init/Kconfig
index 5b86082fa238..73e00b040572 100644
--- a/init/Kconfig
+++ b/init/Kconfig

@@ -1427,6 +1427,20 @@ config KALLSYMS_ALL
 
 	   Say N unless you really need all symbols.
 
+config KALLSYMS_TEXT_RELATIVE
+	bool
+	help
+	  Instead of emitting them as absolute values in the native word size,
+	  emit the symbol references in the kallsyms table as 32-bit entries,
+	  each containing either an absolute value in the range [0, S32_MAX] or
+	  a text relative value in the range [_text, _text + S32_MAX], encoded
+	  as negative values.
+
+	  On 64-bit builds, this reduces the size of the address table by 50%,
+	  but more importantly, it results in entries whose values are build
+	  time constants, and no relocation pass is required at runtime to fix
+	  up the entries based on the runtime load address of the kernel.
+
 config PRINTK
 	default y
 	bool "Enable support for printk" if EXPERT

diff --git a/kernel/kallsyms.c b/kernel/kallsyms.c
index 5c5987f10819..e612f7f9e71b 100644
--- a/kernel/kallsyms.c
+++ b/kernel/kallsyms.c

@@ -38,6 +38,7 @@
  * during the second link stage.
  */
 extern const unsigned long kallsyms_addresses[] __weak;
+extern const int kallsyms_offsets[] __weak;
 extern const u8 kallsyms_names[] __weak;
 
 /*

@@ -176,6 +177,19 @@ static unsigned int get_symbol_offset(unsigned long pos)
 	return name - kallsyms_names;
 }
 
+static unsigned long kallsyms_sym_address(int idx)
+{
+	if (!IS_ENABLED(CONFIG_KALLSYMS_TEXT_RELATIVE))
+		return kallsyms_addresses[idx];
+
+	/* positive offsets are absolute values */
+	if (kallsyms_offsets[idx] >= 0)
+		return kallsyms_offsets[idx];
+
+	/* negative offsets are relative to _text - 1 */
+	return (unsigned long)_text - 1 - kallsyms_offsets[idx];
+}
+
 /* Lookup the address for this symbol. Returns 0 if not found. */
 unsigned long kallsyms_lookup_name(const char *name)
 {

@@ -187,7 +201,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_sym_address(i);
 	}
 	return module_kallsyms_lookup_name(name);
 }

@@ -204,7 +218,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_sym_address(i));
 		if (ret != 0)
 			return ret;
 	}

@@ -220,7 +234,10 @@ 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);
+	if (!IS_ENABLED(CONFIG_KALLSYMS_TEXT_RELATIVE))
+		BUG_ON(!kallsyms_addresses);
+	else
+		BUG_ON(!kallsyms_offsets);
 
 	/* Do a binary search on the sorted kallsyms_addresses array. */
 	low = 0;

@@ -228,7 +245,7 @@ static unsigned long get_symbol_pos(unsigned long addr,
 
 	while (high - low > 1) {
 		mid = low + (high - low) / 2;
-		if (kallsyms_addresses[mid] <= addr)
+		if (kallsyms_sym_address(mid) <= addr)
 			low = mid;
 		else
 			high = mid;

@@ -238,15 +255,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_sym_address(low-1) == kallsyms_sym_address(low))
 		--low;
 
-	symbol_start = kallsyms_addresses[low];
+	symbol_start = kallsyms_sym_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_sym_address(i) > symbol_start) {
+			symbol_end = kallsyms_sym_address(i);
 			break;
 		}
 	}

@@ -470,7 +487,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_sym_address(iter->pos);
 
 	iter->type = kallsyms_get_symbol_type(off);
 

diff --git a/scripts/kallsyms.c b/scripts/kallsyms.c
index 8fa81e84e295..07656c102e60 100644
--- a/scripts/kallsyms.c
+++ b/scripts/kallsyms.c

@@ -22,6 +22,7 @@
 #include <stdlib.h>
 #include <string.h>
 #include <ctype.h>
+#include <limits.h>
 
 #ifndef ARRAY_SIZE
 #define ARRAY_SIZE(arr) (sizeof(arr) / sizeof(arr[0]))

@@ -61,6 +62,7 @@ static int all_symbols = 0;
 static int absolute_percpu = 0;
 static char symbol_prefix_char = '\0';
 static unsigned long long kernel_start_addr = 0;
+static int text_relative = 0;
 
 int token_profit[0x10000];
 

@@ -74,7 +76,7 @@ static void usage(void)
 	fprintf(stderr, "Usage: kallsyms [--all-symbols] "
 			"[--symbol-prefix=<prefix char>] "
 			"[--page-offset=<CONFIG_PAGE_OFFSET>] "
-			"< in.map > out.S\n");
+			"[--text-relative] < in.map > out.S\n");
 	exit(1);
 }
 

@@ -202,6 +204,7 @@ static int symbol_valid(struct sym_entry *s)
 	 */
 	static char *special_symbols[] = {
 		"kallsyms_addresses",
+		"kallsyms_offsets",
 		"kallsyms_num_syms",
 		"kallsyms_names",
 		"kallsyms_markers",

@@ -353,9 +356,34 @@ static void write_src(void)
 	 * .o files.  This prevents .tmp_kallsyms.o or any other
 	 * object from referencing them.
 	 */
-	output_label("kallsyms_addresses");
+	if (!text_relative)
+		output_label("kallsyms_addresses");
+	else
+		output_label("kallsyms_offsets");
+
 	for (i = 0; i < table_cnt; i++) {
-		if (!symbol_absolute(&table[i])) {
+		if (text_relative) {
+			long long offset;
+
+			if (symbol_absolute(&table[i])) {
+				offset = table[i].addr;
+				if (offset < 0 || offset > INT_MAX) {
+					fprintf(stderr, "kallsyms failure: "
+						"absolute symbol value %#llx out of range in relative mode\n",
+						table[i].addr);
+					exit(EXIT_FAILURE);
+				}
+			} else {
+				offset = _text - table[i].addr - 1;
+				if (offset < INT_MIN || offset >= 0) {
+					fprintf(stderr, "kallsyms failure: "
+						"relative symbol value %#llx out of range in relative mode\n",
+						table[i].addr);
+					exit(EXIT_FAILURE);
+				}
+			}
+			printf("\t.long\t%#x\n", (int)offset);
+		} else if (!symbol_absolute(&table[i])) {
 			if (_text <= table[i].addr)
 				printf("\tPTR\t_text + %#llx\n",
 					table[i].addr - _text);

@@ -703,7 +731,9 @@ 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
+			} else if (strcmp(argv[i], "--text-relative") == 0)
+				text_relative = 1;
+			else
 				usage();
 		}
 	} else if (argc != 1)

diff --git a/scripts/link-vmlinux.sh b/scripts/link-vmlinux.sh
index ba6c34ea5429..e0f957f6a54c 100755
--- a/scripts/link-vmlinux.sh
+++ b/scripts/link-vmlinux.sh

@@ -90,6 +90,10 @@ kallsyms()
 		kallsymopt="${kallsymopt} --absolute-percpu"
 	fi
 
+	if [ -n "${CONFIG_KALLSYMS_TEXT_RELATIVE}" ]; then
+		kallsymopt="${kallsymopt} --text-relative"
+	fi
+
 	local aflags="${KBUILD_AFLAGS} ${KBUILD_AFLAGS_KERNEL}               \
 		      ${NOSTDINC_FLAGS} ${LINUXINCLUDE} ${KBUILD_CPPFLAGS}"
 

diff --git a/scripts/namespace.pl b/scripts/namespace.pl
index a71be6b7cdec..e059ab240364 100755
--- a/scripts/namespace.pl
+++ b/scripts/namespace.pl

@@ -117,6 +117,7 @@ my %nameexception = (
     'kallsyms_names'	=> 1,
     'kallsyms_num_syms'	=> 1,
     'kallsyms_addresses'=> 1,
+    'kallsyms_offsets'	=> 1,
     '__this_module'	=> 1,
     '_etext'		=> 1,
     '_edata'		=> 1,

-- 
2.5.0

This enables the newly introduced text-relative kallsyms support when
building 64-bit targets. This cuts the size of the kallsyms address
table in half, and drastically reduces the size of the PIE dynamic
relocation section when building with CONFIG_RELOCATABLE=y (by about
3 MB for ppc64_defconfig)

Signed-off-by: Ard Biesheuvel <redacted>
---

Results for ppc64_defconfig:

BEFORE:
=======
$ size vmlinux
   text	   data	    bss	    dec	    hex	filename
19827996	2008456	 849612	22686064	15a2970	vmlinux

$ readelf -S .tmp_kallsyms2.o
There are 9 section headers, starting at offset 0x4513f8:

Section Headers:
  [Nr] Name              Type             Address           Offset
       Size              EntSize          Flags  Link  Info  Align
  ...
  [ 4] .rodata           PROGBITS         0000000000000000  00000100
       00000000001fcf00  0000000000000000   A       0     0     256
  [ 5] .rela.rodata      RELA             0000000000000000  001fd1d8
       0000000000254220  0000000000000018   I       7     4     8
  [ 6] .shstrtab         STRTAB           0000000000000000  001fd000
       0000000000000039  0000000000000000           0     0     1
  ...

$ ls -l arch/powerpc/boot/zImage
-rwxrwxr-x 2 ard ard 7533160 Jan 20 08:43 arch/powerpc/boot/zImage

AFTER:
======
$ size vmlinux
   text	   data	    bss	    dec	    hex	filename
16979516	2009992	 849612	19839120	12eb890	vmlinux

$ readelf -S .tmp_kallsyms2.o
There are 8 section headers, starting at offset 0x199bb0:

Section Headers:
  [Nr] Name              Type             Address           Offset
       Size              EntSize          Flags  Link  Info  Align
  ...
  [ 4] .rodata           PROGBITS         0000000000000000  00000100
       0000000000199900  0000000000000000   A       0     0     256
  [ 5] .shstrtab         STRTAB           0000000000000000  00199a00
       0000000000000034  0000000000000000           0     0     1
  ...

$ ls -l arch/powerpc/boot/zImage
-rwxrwxr-x 2 ard ard 6985672 Jan 20 08:45 arch/powerpc/boot/zImage
---
 arch/powerpc/Kconfig | 1 +
 1 file changed, 1 insertion(+)

diff --git a/arch/powerpc/Kconfig b/arch/powerpc/Kconfig
index 94f6c5089e0c..d1c26749632b 100644
--- a/arch/powerpc/Kconfig
+++ b/arch/powerpc/Kconfig

@@ -158,6 +158,7 @@ config PPC
 	select ARCH_HAS_DMA_SET_COHERENT_MASK
 	select ARCH_HAS_DEVMEM_IS_ALLOWED
 	select HAVE_ARCH_SECCOMP_FILTER
+	select KALLSYMS_TEXT_RELATIVE if PPC64
 
 config GENERIC_CSUM
 	def_bool CPU_LITTLE_ENDIAN

-- 
2.5.0

This enables the newly introduced text-relative kallsyms support when
building 64-bit targets. This cuts the size of the kallsyms address
table in half, reducing the memory footprint of the kernel .rodata
section by about 250 KB for a defconfig build.

Signed-off-by: Ard Biesheuvel <redacted>
---

BEFORE:
=======
$ size vmlinux
   text	   data	    bss	    dec	    hex	filename
12329586	3107008	14727792	30164386	1cc45a2	vmlinux

$ readelf -S .tmp_kallsyms2.o
There are 9 section headers, starting at offset 0x125b50:

Section Headers:
  [Nr] Name              Type             Address           Offset
       Size              EntSize          Flags  Link  Info  Align
  ...
  [ 4] .rodata           PROGBITS         0000000000000000  00000040
       0000000000125ad0  0000000000000000   A       0     0     8
  [ 5] .rela.rodata      RELA             0000000000000000  00125f28
       000000000015ead8  0000000000000018           7     4     8
  [ 6] .shstrtab         STRTAB           0000000000000000  00125b10
       0000000000000039  0000000000000000           0     0     1
  ...

$ ls -l arch/s390/boot/bzImage
-rwxrwxr-x 1 ard ard 5234224 Jan 20 08:22 arch/s390/boot/bzImage

AFTER:
======
$ size vmlinux
   text	   data	    bss	    dec	    hex	filename
12088114	3102912	14727792	29918818	1c88662	vmlinux

$ readelf -S .tmp_kallsyms2.o
There are 8 section headers, starting at offset 0xeb428:

Section Headers:
  [Nr] Name              Type             Address           Offset
  ...
  [ 4] .rodata           PROGBITS         0000000000000000  00000040
       00000000000eb3b0  0000000000000000   A       0     0     8
  [ 5] .shstrtab         STRTAB           0000000000000000  000eb3f0
       0000000000000034  0000000000000000           0     0     1
  ...

$ ls -l arch/s390/boot/bzImage
-rwxrwxr-x 1 ard ard 5224256 Jan 20 08:23 arch/s390/boot/bzImage
---
 arch/s390/Kconfig | 1 +
 1 file changed, 1 insertion(+)

diff --git a/arch/s390/Kconfig b/arch/s390/Kconfig
index dbeeb3a049f2..588160fd1db0 100644
--- a/arch/s390/Kconfig
+++ b/arch/s390/Kconfig

@@ -149,6 +149,7 @@ config S390
 	select HAVE_REGS_AND_STACK_ACCESS_API
 	select HAVE_SYSCALL_TRACEPOINTS
 	select HAVE_VIRT_CPU_ACCOUNTING
+	select KALLSYMS_TEXT_RELATIVE if 64BIT
 	select MODULES_USE_ELF_RELA
 	select NO_BOOTMEM
 	select OLD_SIGACTION

-- 
2.5.0

This enables the newly introduced text-relative kallsyms support when
building 64-bit targets. This cuts the size of the kallsyms address
table in half, reducing the memory footprint of the kernel .rodata
section by about 400 KB for a KALLSYMS_ALL build, and about 100 KB
reduction in compressed size. (with CONFIG_RELOCATABLE=y)

Signed-off-by: Ard Biesheuvel <redacted>
---
I tested this with my Ubuntu Wily box's config-4.2.0-23-generic, and
got the following results:

BEFORE:
=======
$ size vmlinux
   text	   data	    bss	    dec	    hex	filename
12972949	2213240	1482752	16668941	 fe590d	vmlinux

$ readelf -S .tmp_kallsyms2.o |less
There are 9 section headers, starting at offset 0x3e0788:

Section Headers:
  [Nr] Name              Type             Address           Offset
       Size              EntSize          Flags  Link  Info  Align
  ...
  [ 4] .rodata           PROGBITS         0000000000000000  00000040
       00000000001c7738  0000000000000000   A       0     0     8
  [ 5] .rela.rodata      RELA             0000000000000000  001c7950
       0000000000218e38  0000000000000018   I       7     4     8
  [ 6] .shstrtab         STRTAB           0000000000000000  001c7778
       0000000000000039  0000000000000000           0     0     1

$ ls -l arch/x86/boot/bzImage
-rw-rw-r-- 1 ard ard 6893168 Jan 20 09:36 arch/x86/boot/bzImage

AFTER:
======
$ size vmlinux
   text	   data	    bss	    dec	    hex	filename
12604501	2213240	1482752	16300493	 f8b9cd	vmlinux

$ readelf -S .tmp_kallsyms2.o |less
There are 8 section headers, starting at offset 0x16dd10:

Section Headers:
  [Nr] Name              Type             Address           Offset
       Size              EntSize          Flags  Link  Info  Align
  ...
  [ 4] .rodata           PROGBITS         0000000000000000  00000040
       000000000016db20  0000000000000000   A       0     0     8
  [ 5] .shstrtab         STRTAB           0000000000000000  0016db60
       0000000000000034  0000000000000000           0     0     1
  ...

$ ls -l arch/x86/boot/bzImage
-rw-rw-r-- 1 ard ard 6790224 Jan 19 22:24 arch/x86/boot/bzImage
---
 arch/x86/Kconfig | 1 +
 1 file changed, 1 insertion(+)

diff --git a/arch/x86/Kconfig b/arch/x86/Kconfig
index 4a10ba9e95da..180a94bda8d4 100644
--- a/arch/x86/Kconfig
+++ b/arch/x86/Kconfig

@@ -142,6 +142,7 @@ config X86
 	select HAVE_UNSTABLE_SCHED_CLOCK
 	select HAVE_USER_RETURN_NOTIFIER
 	select IRQ_FORCED_THREADING
+	select KALLSYMS_TEXT_RELATIVE		if X86_64
 	select MODULES_USE_ELF_RELA		if X86_64
 	select MODULES_USE_ELF_REL		if X86_32
 	select OLD_SIGACTION			if X86_32

-- 
2.5.0

On Wed, Jan 20, 2016 at 10:05:37AM +0100, Ard Biesheuvel wrote:

Please remove the "if 64BIT" since s390 is always 64BIT in the meantime.
Tested on s390 and everything seems still to work ;)

Acked-by: Heiko Carstens <redacted>

On 20 January 2016 at 10:43, Heiko Carstens [off-list ref] wrote:

On Wed, Jan 20, 2016 at 10:05:37AM +0100, Ard Biesheuvel wrote:

quoted

This enables the newly introduced text-relative kallsyms support when
building 64-bit targets. This cuts the size of the kallsyms address
table in half, reducing the memory footprint of the kernel .rodata
section by about 250 KB for a defconfig build.

Signed-off-by: Ard Biesheuvel <redacted>
---

diff --git a/arch/s390/Kconfig b/arch/s390/Kconfig
index dbeeb3a049f2..588160fd1db0 100644
--- a/arch/s390/Kconfig
+++ b/arch/s390/Kconfig

@@ -149,6 +149,7 @@ config S390
      select HAVE_REGS_AND_STACK_ACCESS_API
      select HAVE_SYSCALL_TRACEPOINTS
      select HAVE_VIRT_CPU_ACCOUNTING
+     select KALLSYMS_TEXT_RELATIVE if 64BIT

Please remove the "if 64BIT" since s390 is always 64BIT in the meantime.
Tested on s390 and everything seems still to work ;)

Acked-by: Heiko Carstens <redacted>

Thanks! Did you take a look at /proc/kallsyms, by any chance? It
should look identical with and without these patches

On Wed, Jan 20, 2016 at 11:04:24AM +0100, Ard Biesheuvel wrote:

On 20 January 2016 at 10:43, Heiko Carstens [off-list ref] wrote:

quoted

On Wed, Jan 20, 2016 at 10:05:37AM +0100, Ard Biesheuvel wrote:

quoted

This enables the newly introduced text-relative kallsyms support when
building 64-bit targets. This cuts the size of the kallsyms address
table in half, reducing the memory footprint of the kernel .rodata
section by about 250 KB for a defconfig build.

Signed-off-by: Ard Biesheuvel <redacted>
---

diff --git a/arch/s390/Kconfig b/arch/s390/Kconfig
index dbeeb3a049f2..588160fd1db0 100644
--- a/arch/s390/Kconfig
+++ b/arch/s390/Kconfig

@@ -149,6 +149,7 @@ config S390
      select HAVE_REGS_AND_STACK_ACCESS_API
      select HAVE_SYSCALL_TRACEPOINTS
      select HAVE_VIRT_CPU_ACCOUNTING
+     select KALLSYMS_TEXT_RELATIVE if 64BIT

Please remove the "if 64BIT" since s390 is always 64BIT in the meantime.
Tested on s390 and everything seems still to work ;)

Acked-by: Heiko Carstens <redacted>

Thanks! Did you take a look at /proc/kallsyms, by any chance? It
should look identical with and without these patches

Close to identical, since the generated code and offsets change a bit with
your new config option enabled and disabled. But only those parts that are
linked behind kernel/kallsyms.c.

However I did run a couple of ftrace, kprobes tests and enforced call
backtraces. Everything still works.

So it looks all good.

On 20 January 2016 at 11:17, Heiko Carstens [off-list ref] wrote:

On Wed, Jan 20, 2016 at 11:04:24AM +0100, Ard Biesheuvel wrote:

quoted

On 20 January 2016 at 10:43, Heiko Carstens [off-list ref] wrote:

quoted

On Wed, Jan 20, 2016 at 10:05:37AM +0100, Ard Biesheuvel wrote:

quoted

This enables the newly introduced text-relative kallsyms support when
building 64-bit targets. This cuts the size of the kallsyms address
table in half, reducing the memory footprint of the kernel .rodata
section by about 250 KB for a defconfig build.

Signed-off-by: Ard Biesheuvel <redacted>
---

diff --git a/arch/s390/Kconfig b/arch/s390/Kconfig
index dbeeb3a049f2..588160fd1db0 100644
--- a/arch/s390/Kconfig
+++ b/arch/s390/Kconfig

@@ -149,6 +149,7 @@ config S390
      select HAVE_REGS_AND_STACK_ACCESS_API
      select HAVE_SYSCALL_TRACEPOINTS
      select HAVE_VIRT_CPU_ACCOUNTING
+     select KALLSYMS_TEXT_RELATIVE if 64BIT

Please remove the "if 64BIT" since s390 is always 64BIT in the meantime.
Tested on s390 and everything seems still to work ;)

Acked-by: Heiko Carstens <redacted>

Thanks! Did you take a look at /proc/kallsyms, by any chance? It
should look identical with and without these patches

Close to identical, since the generated code and offsets change a bit with
your new config option enabled and disabled. But only those parts that are
linked behind kernel/kallsyms.c.

However I did run a couple of ftrace, kprobes tests and enforced call
backtraces. Everything still works.

So it looks all good.

Thanks a lot!

* Ard Biesheuvel [off-list ref] wrote:

This implements text-relative kallsyms address tables. This was developed as 
part of my series to implement KASLR/CONFIG_RELOCATABLE for arm64, but I think 
it may be beneficial to other architectures as well, so I am presenting it as a 
separate series.

The idea is that on 64-bit builds, it is rather wasteful to use absolute 
addressing for kernel symbols since they are all within a couple of MBs of each 
other. On top of that, the absolute addressing implies that, when the kernel is 
relocated at runtime, each address in the table needs to be fixed up 
individually.

Since all section-relative addresses are already emitted relative to _text, it 
is quite straight-forward to record only the offset, and add the absolute 
address of _text at runtime when referring to the address table.

The reduction ranges from around 250 KB uncompressed vmlinux size and 10 KB 
compressed size (s390) to 3 MB/500 KB for ppc64 (although, in the latter case, 
the reduction in uncompressed size is primarily __init data)

So since kallsyms is in unswappable kernel RAM, the uncompressed size reduction is 
what we care about mostly. How much bootloader load times are impacted is a third 
order concern.

IOW a nice change!

Thanks,

	Ingo

On Wednesday 20 January 2016 11:33:25 Ingo Molnar wrote:

quoted

The reduction ranges from around 250 KB uncompressed vmlinux size and 10 KB 
compressed size (s390) to 3 MB/500 KB for ppc64 (although, in the latter case, 
the reduction in uncompressed size is primarily __init data)

So since kallsyms is in unswappable kernel RAM, the uncompressed size reduction is 
what we care about mostly. How much bootloader load times are impacted is a third 
order concern.

IOW a nice change!

I think some people care a lot about the compressed size as well:

http://git.openwrt.org/?p=openwrt.git;a=blob;f=target/linux/generic/patches-4.4/203-kallsyms_uncompressed.patch;h=cf8a447bbcd5b1621d4edc36a69fe0ad384fe53f;hb=HEAD

This has been in openwrt.git for ages, because a lot of the target devices
are much more limited on flash memory size (4MB typically) than they are
on RAM size (at least 32MB).

	Arnd

On Wed, Jan 20, 2016 at 1:05 AM, Ard Biesheuvel
[off-list ref] wrote:

This enables the newly introduced text-relative kallsyms support when
building 64-bit targets. This cuts the size of the kallsyms address
table in half, reducing the memory footprint of the kernel .rodata
section by about 400 KB for a KALLSYMS_ALL build, and about 100 KB
reduction in compressed size. (with CONFIG_RELOCATABLE=y)

Signed-off-by: Ard Biesheuvel <redacted>

Tested-by: Kees Cook <redacted>

-Kees

-- 
Kees Cook
Chrome OS & Brillo Security

On Wed, Jan 20, 2016 at 1:05 AM, Ard Biesheuvel
[off-list ref] wrote:

Similar to how relative extables are implemented, it is possible to emit
the kallsyms table in such a way that it contains offsets relative to some
anchor point in the kernel image rather than absolute addresses. The benefit
is that such table entries are no longer subject to dynamic relocation when
the build time and runtime offsets of the kernel image are different. Also,
on 64-bit architectures, it essentially cuts the size of the address table
in half since offsets can typically be expressed in 32 bits.

Since it is useful for some architectures (like x86) to retain the ability
to emit absolute values as well, this patch adds support for both, by
emitting absolute addresses as positive 32-bit values, and addresses
relative to _text as negative values, which are subtracted from the runtime
address of _text to produce the actual address. Positive values are used as
they are found in the table.

Support for the above is enabled by setting CONFIG_KALLSYMS_TEXT_RELATIVE.

Signed-off-by: Ard Biesheuvel <redacted>

Reviewed-by: Kees Cook <redacted>

A nice space-saver! :)

-Kees

-- 
Kees Cook
Chrome OS & Brillo Security

On Wed, 2016-01-20 at 10:05 +0100, Ard Biesheuvel wrote:

This enables the newly introduced text-relative kallsyms support when
building 64-bit targets. This cuts the size of the kallsyms address
table in half, and drastically reduces the size of the PIE dynamic
relocation section when building with CONFIG_RELOCATABLE=y (by about
3 MB for ppc64_defconfig)

Signed-off-by: Ard Biesheuvel <redacted>
---

Results for ppc64_defconfig:

BEFORE:
=======
$ size vmlinux
   text	   data	    bss	    dec	    hex	filename
19827996	2008456	 849612	22686064	15a2970	vmlinux

$ readelf -S .tmp_kallsyms2.o
There are 9 section headers, starting at offset 0x4513f8:

Section Headers:
  [Nr] Name              Type             Address           Offset
       Size              EntSize          Flags  Link  Info  Align
  ...
  [ 4] .rodata           PROGBITS         0000000000000000  00000100
       00000000001fcf00  0000000000000000   A       0     0     256
  [ 5] .rela.rodata      RELA             0000000000000000  001fd1d8
       0000000000254220  0000000000000018   I       7     4     8
  [ 6] .shstrtab         STRTAB           0000000000000000  001fd000
       0000000000000039  0000000000000000           0     0     1
  ...

$ ls -l arch/powerpc/boot/zImage
-rwxrwxr-x 2 ard ard 7533160 Jan 20 08:43 arch/powerpc/boot/zImage

AFTER:
======
$ size vmlinux
   text	   data	    bss	    dec	    hex	filename
16979516	2009992	 849612	19839120	12eb890	vmlinux

$ readelf -S .tmp_kallsyms2.o
There are 8 section headers, starting at offset 0x199bb0:

Section Headers:
  [Nr] Name              Type             Address           Offset
       Size              EntSize          Flags  Link  Info  Align
  ...
  [ 4] .rodata           PROGBITS         0000000000000000  00000100
       0000000000199900  0000000000000000   A       0     0     256
  [ 5] .shstrtab         STRTAB           0000000000000000  00199a00
       0000000000000034  0000000000000000           0     0     1
  ...

$ ls -l arch/powerpc/boot/zImage
-rwxrwxr-x 2 ard ard 6985672 Jan 20 08:45 arch/powerpc/boot/zImage

Nice space saving, thanks very much.

I've booted this on a bunch of machines and it seems to be working fine.

Tested-by: Michael Ellerman <mpe@ellerman.id.au> (powerpc)

cheers

Ard Biesheuvel [off-list ref] writes:

This implements text-relative kallsyms address tables. This was developed
as part of my series to implement KASLR/CONFIG_RELOCATABLE for arm64, but
I think it may be beneficial to other architectures as well, so I am
presenting it as a separate series.

Nice work!

AFAICT this should work for every arch, as long as they start with _text
(esp: data and init must be > _text).  In addition, it's not harmful on
32 bit archs.

IOW, I'd like to turn it on for everyone and discard some code.  But
it's easier to roll in like you've done first.

Should we enable it by default for every arch for now, and see what
happens?

Thanks!
Rusty.

The idea is that on 64-bit builds, it is rather wasteful to use absolute
addressing for kernel symbols since they are all within a couple of MBs
of each other. On top of that, the absolute addressing implies that, when
the kernel is relocated at runtime, each address in the table needs to be
fixed up individually.

Since all section-relative addresses are already emitted relative to _text,
it is quite straight-forward to record only the offset, and add the absolute
address of _text at runtime when referring to the address table.

The reduction ranges from around 250 KB uncompressed vmlinux size and 10 KB
compressed size (s390) to 3 MB/500 KB for ppc64 (although, in the latter case,
the reduction in uncompressed size is primarily __init data)

Kees Cook was so kind to test these against x86_64, and confirmed that KASLR
still operates as expected.

Ard Biesheuvel (4):
  kallsyms: add support for relative offsets in kallsyms address table
  powerpc: enable text relative kallsyms for ppc64
  s390: enable text relative kallsyms for 64-bit targets
  x86_64: enable text relative kallsyms for 64-bit targets

 arch/powerpc/Kconfig    |  1 +
 arch/s390/Kconfig       |  1 +
 arch/x86/Kconfig        |  1 +
 init/Kconfig            | 14 ++++++++
 kernel/kallsyms.c       | 35 +++++++++++++-----
 scripts/kallsyms.c      | 38 +++++++++++++++++---
 scripts/link-vmlinux.sh |  4 +++
 scripts/namespace.pl    |  1 +
 8 files changed, 82 insertions(+), 13 deletions(-)

-- 
2.5.0

On 21 January 2016 at 06:10, Rusty Russell [off-list ref] wrote:

Ard Biesheuvel [off-list ref] writes:

quoted

This implements text-relative kallsyms address tables. This was developed
as part of my series to implement KASLR/CONFIG_RELOCATABLE for arm64, but
I think it may be beneficial to other architectures as well, so I am
presenting it as a separate series.

Nice work!

Thanks

AFAICT this should work for every arch, as long as they start with _text
(esp: data and init must be > _text).  In addition, it's not harmful on
32 bit archs.

IOW, I'd like to turn it on for everyone and discard some code.  But
it's easier to roll in like you've done first.

Should we enable it by default for every arch for now, and see what
happens?

As you say, this only works if every symbol >= _text, which is
obviously not the case per the conditional in scripts/kallsyms.c,
which emits _text + n or _text - n depending on whether the symbol
precedes or follows _text. The git log tells me for which arch this
was originally implemented, but it does not tell me which other archs
have come to rely on it in the meantime.

On top of that, ia64 fails to build with this option, since it has
some whitelisted absolute symbols that look suspiciously like they
could be emitted as _text relative (and it does not even matter in the
absence of CONFIG_RELOCATABLE on ia64, afaict) but I don't know
whether we can just override their types as T, since it would also
change the type in the contents of /proc/kallsyms. So some guidance
would be appreciated here.

So I agree that it would be preferred to have a single code path, but
I would need some help validating it on architectures I don't have
access to.

Thanks,
Ard.

quoted

The idea is that on 64-bit builds, it is rather wasteful to use absolute
addressing for kernel symbols since they are all within a couple of MBs
of each other. On top of that, the absolute addressing implies that, when
the kernel is relocated at runtime, each address in the table needs to be
fixed up individually.

Since all section-relative addresses are already emitted relative to _text,
it is quite straight-forward to record only the offset, and add the absolute
address of _text at runtime when referring to the address table.

The reduction ranges from around 250 KB uncompressed vmlinux size and 10 KB
compressed size (s390) to 3 MB/500 KB for ppc64 (although, in the latter case,
the reduction in uncompressed size is primarily __init data)

Kees Cook was so kind to test these against x86_64, and confirmed that KASLR
still operates as expected.

Ard Biesheuvel (4):
  kallsyms: add support for relative offsets in kallsyms address table
  powerpc: enable text relative kallsyms for ppc64
  s390: enable text relative kallsyms for 64-bit targets
  x86_64: enable text relative kallsyms for 64-bit targets

 arch/powerpc/Kconfig    |  1 +
 arch/s390/Kconfig       |  1 +
 arch/x86/Kconfig        |  1 +
 init/Kconfig            | 14 ++++++++
 kernel/kallsyms.c       | 35 +++++++++++++-----
 scripts/kallsyms.c      | 38 +++++++++++++++++---
 scripts/link-vmlinux.sh |  4 +++
 scripts/namespace.pl    |  1 +
 8 files changed, 82 insertions(+), 13 deletions(-)

--
2.5.0

On 21 January 2016 at 07:45, Ard Biesheuvel [off-list ref] wrote:

On 21 January 2016 at 06:10, Rusty Russell [off-list ref] wrote:

quoted

Ard Biesheuvel [off-list ref] writes:

quoted

This implements text-relative kallsyms address tables. This was developed
as part of my series to implement KASLR/CONFIG_RELOCATABLE for arm64, but
I think it may be beneficial to other architectures as well, so I am
presenting it as a separate series.

Nice work!

Thanks

quoted

AFAICT this should work for every arch, as long as they start with _text
(esp: data and init must be > _text).  In addition, it's not harmful on
32 bit archs.

IOW, I'd like to turn it on for everyone and discard some code.  But
it's easier to roll in like you've done first.

Should we enable it by default for every arch for now, and see what
happens?

As you say, this only works if every symbol >= _text, which is
obviously not the case per the conditional in scripts/kallsyms.c,
which emits _text + n or _text - n depending on whether the symbol
precedes or follows _text. The git log tells me for which arch this
was originally implemented, but it does not tell me which other archs
have come to rely on it in the meantime.

On top of that, ia64 fails to build with this option, since it has
some whitelisted absolute symbols that look suspiciously like they
could be emitted as _text relative (and it does not even matter in the
absence of CONFIG_RELOCATABLE on ia64, afaict) but I don't know
whether we can just override their types as T, since it would also
change the type in the contents of /proc/kallsyms. So some guidance
would be appreciated here.

Digging a little deeper, it appears that it would be non-trivial to
port this to ia64:

...
a000000000040720 A __kernel_syscall_via_break
a000000000040740 A __kernel_sigtramp
a000000000040a00 A __kernel_syscall_via_epc
a000000100000000 T ia64_ivt
a000000100000000 T __start_ivt_text
a000000100000000 T _stext
a000000100000000 T _text
...

The top three symbols are the absolute symbols that are explicitly
whitelisted by scripts/kallsyms.c, and they are too far from 0 and too
far from _text to be representable in 32 bits

So I agree that it would be preferred to have a single code path, but
I would need some help validating it on architectures I don't have
access to.

Thanks,
Ard.

quoted

quoted

The idea is that on 64-bit builds, it is rather wasteful to use absolute
addressing for kernel symbols since they are all within a couple of MBs
of each other. On top of that, the absolute addressing implies that, when
the kernel is relocated at runtime, each address in the table needs to be
fixed up individually.

Since all section-relative addresses are already emitted relative to _text,
it is quite straight-forward to record only the offset, and add the absolute
address of _text at runtime when referring to the address table.

The reduction ranges from around 250 KB uncompressed vmlinux size and 10 KB
compressed size (s390) to 3 MB/500 KB for ppc64 (although, in the latter case,
the reduction in uncompressed size is primarily __init data)

Kees Cook was so kind to test these against x86_64, and confirmed that KASLR
still operates as expected.

Ard Biesheuvel (4):
  kallsyms: add support for relative offsets in kallsyms address table
  powerpc: enable text relative kallsyms for ppc64
  s390: enable text relative kallsyms for 64-bit targets
  x86_64: enable text relative kallsyms for 64-bit targets

 arch/powerpc/Kconfig    |  1 +
 arch/s390/Kconfig       |  1 +
 arch/x86/Kconfig        |  1 +
 init/Kconfig            | 14 ++++++++
 kernel/kallsyms.c       | 35 +++++++++++++-----
 scripts/kallsyms.c      | 38 +++++++++++++++++---
 scripts/link-vmlinux.sh |  4 +++
 scripts/namespace.pl    |  1 +
 8 files changed, 82 insertions(+), 13 deletions(-)

--
2.5.0

Ard Biesheuvel [off-list ref] writes:

On 21 January 2016 at 07:45, Ard Biesheuvel [off-list ref] wrote:

quoted

On 21 January 2016 at 06:10, Rusty Russell [off-list ref] wrote:

quoted

Ard Biesheuvel [off-list ref] writes:

quoted

This implements text-relative kallsyms address tables. This was developed
as part of my series to implement KASLR/CONFIG_RELOCATABLE for arm64, but
I think it may be beneficial to other architectures as well, so I am
presenting it as a separate series.

Nice work!

Thanks

quoted

AFAICT this should work for every arch, as long as they start with _text
(esp: data and init must be > _text).  In addition, it's not harmful on
32 bit archs.

IOW, I'd like to turn it on for everyone and discard some code.  But
it's easier to roll in like you've done first.

Should we enable it by default for every arch for now, and see what
happens?

As you say, this only works if every symbol >= _text, which is
obviously not the case per the conditional in scripts/kallsyms.c,
which emits _text + n or _text - n depending on whether the symbol
precedes or follows _text. The git log tells me for which arch this
was originally implemented, but it does not tell me which other archs
have come to rely on it in the meantime.

On top of that, ia64 fails to build with this option, since it has
some whitelisted absolute symbols that look suspiciously like they
could be emitted as _text relative (and it does not even matter in the
absence of CONFIG_RELOCATABLE on ia64, afaict) but I don't know
whether we can just override their types as T, since it would also
change the type in the contents of /proc/kallsyms. So some guidance
would be appreciated here.

Digging a little deeper, it appears that it would be non-trivial to
port this to ia64:

...
a000000000040720 A __kernel_syscall_via_break
a000000000040740 A __kernel_sigtramp
a000000000040a00 A __kernel_syscall_via_epc
a000000100000000 T ia64_ivt
a000000100000000 T __start_ivt_text
a000000100000000 T _stext
a000000100000000 T _text
...

The top three symbols are the absolute symbols that are explicitly
whitelisted by scripts/kallsyms.c, and they are too far from 0 and too
far from _text to be representable in 32 bits

How annoying.  OK, until ia64 is removed, we'll leave the option.

Thanks,
Rusty.