[PATCH v2 0/5] Speed booting by sorting exception tables at build time.

[PATCH v2 0/5] Speed booting by sorting exception tables at build time.

[David Daney]

From: David Daney <david.daney@cavium.com>

v2: Cosmetic changes only.  Cleanup makefile indentation.  Rebase MIPS
    and x86 Kconfig changes against 3.4-rc2.

    Michal Marek had suggested using $(call cmd,sortextable), but I
    wasn't able to figure out a good way to do that *and* have it print
    'SORTEX vmlinux', so I left it as I originally had it.

v1:

I noticed when booting MIPS64 kernels that sorting of the main
__ex_table was taking a long time (2,692,220 cycles or 3.3 mS at
800MHz to be exact).  That is not too bad for real silicon
implementations, but when running on a slow simulator, it can be
significant.

I can get this down to about 1,000,000 cycles by supplying a custom
swap function for the sort, but even better is to eliminate it
entirely by doing the sort at build time. That is the idea behind
this patch set.

Here is more or less what I did:

o A flag word is added to the kernel to indicate that the __ex_table
  is already sorted.  sort_main_extable() checks this and if it is
  clear, returns without doing the sort.

o I shamelessly stole code from recordmcount and created a new build
  time helper program 'sortextable'.  This is run on the final vmlinux
  image, it sorts the table, and then clears the flag word.

Potential areas for improvement:

o Sort module exception tables too.

o Get rid of the flag word, and assume that if an architecture supports
  build time sorting, that it must have been done.

o Add support for architectures other than MIPS and x86

David Daney (5):
  scripts: Add sortextable to sort the kernel's exception table.
  extable: Skip sorting if sorted at build time.
  kbuild/extable: Hook up sortextable into the build system.
  MIPS: Select BUILDTIME_EXTABLE_SORT
  x86: Select BUILDTIME_EXTABLE_SORT

 Makefile              |   10 ++
 arch/mips/Kconfig     |    1 +
 arch/x86/Kconfig      |    1 +
 init/Kconfig          |    3 +
 kernel/extable.c      |    8 ++-
 scripts/.gitignore    |    1 +
 scripts/Makefile      |    1 +
 scripts/sortextable.c |  273 +++++++++++++++++++++++++++++++++++++++++++++++++
 scripts/sortextable.h |  168 ++++++++++++++++++++++++++++++
 9 files changed, 465 insertions(+), 1 deletions(-)
 create mode 100644 scripts/sortextable.c
 create mode 100644 scripts/sortextable.h

-- 
1.7.2.3

[PATCH v1 1/5] scripts: Add sortextable to sort the kernel's exception table.

[David Daney]

From: David Daney <david.daney@cavium.com>

Using this build-time sort saves time booting as we don't have to burn
cycles sorting the exception table.

Signed-off-by: David Daney <david.daney@cavium.com>
---
 scripts/.gitignore    |    1 +
 scripts/Makefile      |    1 +
 scripts/sortextable.c |  273 +++++++++++++++++++++++++++++++++++++++++++++++++
 scripts/sortextable.h |  168 ++++++++++++++++++++++++++++++
 4 files changed, 443 insertions(+), 0 deletions(-)
 create mode 100644 scripts/sortextable.c
 create mode 100644 scripts/sortextable.h

diff --git a/scripts/.gitignore b/scripts/.gitignore
index 105b21f..65f362d 100644
--- a/scripts/.gitignore
+++ b/scripts/.gitignore
@@ -9,3 +9,4 @@ unifdef
 ihex2fw
 recordmcount
 docproc
+sortextable
diff --git a/scripts/Makefile b/scripts/Makefile
index df7678f..43e19b9 100644
--- a/scripts/Makefile
+++ b/scripts/Makefile
@@ -13,6 +13,7 @@ hostprogs-$(CONFIG_LOGO)         += pnmtologo
 hostprogs-$(CONFIG_VT)           += conmakehash
 hostprogs-$(CONFIG_IKCONFIG)     += bin2c
 hostprogs-$(BUILD_C_RECORDMCOUNT) += recordmcount
+hostprogs-$(CONFIG_BUILDTIME_EXTABLE_SORT) += sortextable
 
 always		:= $(hostprogs-y) $(hostprogs-m)
 
diff --git a/scripts/sortextable.c b/scripts/sortextable.c
new file mode 100644
index 0000000..6546785
--- /dev/null
+++ b/scripts/sortextable.c
@@ -0,0 +1,273 @@
+/*
+ * sortextable.c: Sort the kernel's exception table
+ *
+ * Copyright 2011 Cavium, Inc.
+ *
+ * Based on code taken from recortmcount.c which is:
+ *
+ * Copyright 2009 John F. Reiser <jreiser@BitWagon.com>.  All rights reserved.
+ * Licensed under the GNU General Public License, version 2 (GPLv2).
+ *
+ * Restructured to fit Linux format, as well as other updates:
+ *  Copyright 2010 Steven Rostedt <srostedt@redhat.com>, Red Hat Inc.
+ */
+
+/*
+ * Strategy: alter the vmlinux file in-place.
+ */
+
+#include <sys/types.h>
+#include <sys/mman.h>
+#include <sys/stat.h>
+#include <getopt.h>
+#include <elf.h>
+#include <fcntl.h>
+#include <setjmp.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <unistd.h>
+
+static int fd_map;	/* File descriptor for file being modified. */
+static int mmap_failed; /* Boolean flag. */
+static void *ehdr_curr; /* current ElfXX_Ehdr *  for resource cleanup */
+static struct stat sb;	/* Remember .st_size, etc. */
+static jmp_buf jmpenv;	/* setjmp/longjmp per-file error escape */
+
+/* setjmp() return values */
+enum {
+	SJ_SETJMP = 0,  /* hardwired first return */
+	SJ_FAIL,
+	SJ_SUCCEED
+};
+
+/* Per-file resource cleanup when multiple files. */
+static void
+cleanup(void)
+{
+	if (!mmap_failed)
+		munmap(ehdr_curr, sb.st_size);
+	close(fd_map);
+}
+
+static void __attribute__((noreturn))
+fail_file(void)
+{
+	cleanup();
+	longjmp(jmpenv, SJ_FAIL);
+}
+
+static void __attribute__((noreturn))
+succeed_file(void)
+{
+	cleanup();
+	longjmp(jmpenv, SJ_SUCCEED);
+}
+
+
+/*
+ * Get the whole file as a programming convenience in order to avoid
+ * malloc+lseek+read+free of many pieces.  If successful, then mmap
+ * avoids copying unused pieces; else just read the whole file.
+ * Open for both read and write.
+ */
+static void *mmap_file(char const *fname)
+{
+	void *addr;
+
+	fd_map = open(fname, O_RDWR);
+	if (fd_map < 0 || fstat(fd_map, &sb) < 0) {
+		perror(fname);
+		fail_file();
+	}
+	if (!S_ISREG(sb.st_mode)) {
+		fprintf(stderr, "not a regular file: %s\n", fname);
+		fail_file();
+	}
+	addr = mmap(0, sb.st_size, PROT_READ|PROT_WRITE, MAP_SHARED,
+		    fd_map, 0);
+	if (addr == MAP_FAILED) {
+		mmap_failed = 1;
+		fprintf(stderr, "Could not mmap file: %s\n", fname);
+		fail_file();
+	}
+	return addr;
+}
+
+/* w8rev, w8nat, ...: Handle endianness. */
+
+static uint64_t w8rev(uint64_t const x)
+{
+	return   ((0xff & (x >> (0 * 8))) << (7 * 8))
+	       | ((0xff & (x >> (1 * 8))) << (6 * 8))
+	       | ((0xff & (x >> (2 * 8))) << (5 * 8))
+	       | ((0xff & (x >> (3 * 8))) << (4 * 8))
+	       | ((0xff & (x >> (4 * 8))) << (3 * 8))
+	       | ((0xff & (x >> (5 * 8))) << (2 * 8))
+	       | ((0xff & (x >> (6 * 8))) << (1 * 8))
+	       | ((0xff & (x >> (7 * 8))) << (0 * 8));
+}
+
+static uint32_t w4rev(uint32_t const x)
+{
+	return   ((0xff & (x >> (0 * 8))) << (3 * 8))
+	       | ((0xff & (x >> (1 * 8))) << (2 * 8))
+	       | ((0xff & (x >> (2 * 8))) << (1 * 8))
+	       | ((0xff & (x >> (3 * 8))) << (0 * 8));
+}
+
+static uint32_t w2rev(uint16_t const x)
+{
+	return   ((0xff & (x >> (0 * 8))) << (1 * 8))
+	       | ((0xff & (x >> (1 * 8))) << (0 * 8));
+}
+
+static uint64_t w8nat(uint64_t const x)
+{
+	return x;
+}
+
+static uint32_t w4nat(uint32_t const x)
+{
+	return x;
+}
+
+static uint32_t w2nat(uint16_t const x)
+{
+	return x;
+}
+
+static uint64_t (*w8)(uint64_t);
+static uint32_t (*w)(uint32_t);
+static uint32_t (*w2)(uint16_t);
+
+
+/* 32 bit and 64 bit are very similar */
+#include "sortextable.h"
+#define SORTEXTABLE_64
+#include "sortextable.h"
+
+
+static void
+do_file(char const *const fname)
+{
+	Elf32_Ehdr *const ehdr = mmap_file(fname);
+
+	ehdr_curr = ehdr;
+	w = w4nat;
+	w2 = w2nat;
+	w8 = w8nat;
+	switch (ehdr->e_ident[EI_DATA]) {
+		static unsigned int const endian = 1;
+	default:
+		fprintf(stderr, "unrecognized ELF data encoding %d: %s\n",
+			ehdr->e_ident[EI_DATA], fname);
+		fail_file();
+		break;
+	case ELFDATA2LSB:
+		if (*(unsigned char const *)&endian != 1) {
+			/* main() is big endian, file.o is little endian. */
+			w = w4rev;
+			w2 = w2rev;
+			w8 = w8rev;
+		}
+		break;
+	case ELFDATA2MSB:
+		if (*(unsigned char const *)&endian != 0) {
+			/* main() is little endian, file.o is big endian. */
+			w = w4rev;
+			w2 = w2rev;
+			w8 = w8rev;
+		}
+		break;
+	}  /* end switch */
+	if (memcmp(ELFMAG, ehdr->e_ident, SELFMAG) != 0
+	||  w2(ehdr->e_type) != ET_EXEC
+	||  ehdr->e_ident[EI_VERSION] != EV_CURRENT) {
+		fprintf(stderr, "unrecognized ET_EXEC file %s\n", fname);
+		fail_file();
+	}
+
+	switch (w2(ehdr->e_machine)) {
+	default:
+		fprintf(stderr, "unrecognized e_machine %d %s\n",
+			w2(ehdr->e_machine), fname);
+		fail_file();
+		break;
+	case EM_386:
+	case EM_MIPS:
+	case EM_X86_64:
+		break;
+	}  /* end switch */
+
+	switch (ehdr->e_ident[EI_CLASS]) {
+	default:
+		fprintf(stderr, "unrecognized ELF class %d %s\n",
+			ehdr->e_ident[EI_CLASS], fname);
+		fail_file();
+		break;
+	case ELFCLASS32:
+		if (w2(ehdr->e_ehsize) != sizeof(Elf32_Ehdr)
+		||  w2(ehdr->e_shentsize) != sizeof(Elf32_Shdr)) {
+			fprintf(stderr,
+				"unrecognized ET_EXEC file: %s\n", fname);
+			fail_file();
+		}
+		do32(ehdr, fname);
+		break;
+	case ELFCLASS64: {
+		Elf64_Ehdr *const ghdr = (Elf64_Ehdr *)ehdr;
+		if (w2(ghdr->e_ehsize) != sizeof(Elf64_Ehdr)
+		||  w2(ghdr->e_shentsize) != sizeof(Elf64_Shdr)) {
+			fprintf(stderr,
+				"unrecognized ET_EXEC file: %s\n", fname);
+			fail_file();
+		}
+		do64(ghdr, fname);
+		break;
+	}
+	}  /* end switch */
+
+	cleanup();
+}
+
+int
+main(int argc, char *argv[])
+{
+	int n_error = 0;  /* gcc-4.3.0 false positive complaint */
+	int i;
+
+	if (argc < 2) {
+		fprintf(stderr, "usage: sortextable vmlinux...\n");
+		return 0;
+	}
+
+	/* Process each file in turn, allowing deep failure. */
+	for (i = 1; i < argc; i++) {
+		char *file = argv[i];
+		int const sjval = setjmp(jmpenv);
+
+		switch (sjval) {
+		default:
+			fprintf(stderr, "internal error: %s\n", file);
+			exit(1);
+			break;
+		case SJ_SETJMP:    /* normal sequence */
+			/* Avoid problems if early cleanup() */
+			fd_map = -1;
+			ehdr_curr = NULL;
+			mmap_failed = 1;
+			do_file(file);
+			break;
+		case SJ_FAIL:    /* error in do_file or below */
+			++n_error;
+			break;
+		case SJ_SUCCEED:    /* premature success */
+			/* do nothing */
+			break;
+		}  /* end switch */
+	}
+	return !!n_error;
+}
+
+
diff --git a/scripts/sortextable.h b/scripts/sortextable.h
new file mode 100644
index 0000000..bb6aaf1
--- /dev/null
+++ b/scripts/sortextable.h
@@ -0,0 +1,168 @@
+/*
+ * sortextable.h
+ *
+ * Copyright 2011 Cavium, Inc.
+ *
+ * Some of this code was taken out of recordmcount.h written by:
+ *
+ * Copyright 2009 John F. Reiser <jreiser@BitWagon.com>.  All rights reserved.
+ * Copyright 2010 Steven Rostedt <srostedt@redhat.com>, Red Hat Inc.
+ *
+ *
+ * Licensed under the GNU General Public License, version 2 (GPLv2).
+ */
+
+#undef extable_ent_size
+#undef compare_extable
+#undef do_func
+#undef Elf_Addr
+#undef Elf_Ehdr
+#undef Elf_Shdr
+#undef Elf_Rel
+#undef Elf_Rela
+#undef Elf_Sym
+#undef ELF_R_SYM
+#undef Elf_r_sym
+#undef ELF_R_INFO
+#undef Elf_r_info
+#undef ELF_ST_BIND
+#undef ELF_ST_TYPE
+#undef fn_ELF_R_SYM
+#undef fn_ELF_R_INFO
+#undef uint_t
+#undef _w
+
+#ifdef SORTEXTABLE_64
+# define extable_ent_size	16
+# define compare_extable	compare_extable_64
+# define do_func		do64
+# define Elf_Addr		Elf64_Addr
+# define Elf_Ehdr		Elf64_Ehdr
+# define Elf_Shdr		Elf64_Shdr
+# define Elf_Rel		Elf64_Rel
+# define Elf_Rela		Elf64_Rela
+# define Elf_Sym		Elf64_Sym
+# define ELF_R_SYM		ELF64_R_SYM
+# define Elf_r_sym		Elf64_r_sym
+# define ELF_R_INFO		ELF64_R_INFO
+# define Elf_r_info		Elf64_r_info
+# define ELF_ST_BIND		ELF64_ST_BIND
+# define ELF_ST_TYPE		ELF64_ST_TYPE
+# define fn_ELF_R_SYM		fn_ELF64_R_SYM
+# define fn_ELF_R_INFO		fn_ELF64_R_INFO
+# define uint_t			uint64_t
+# define _w			w8
+#else
+# define extable_ent_size	8
+# define compare_extable	compare_extable_32
+# define do_func		do32
+# define Elf_Addr		Elf32_Addr
+# define Elf_Ehdr		Elf32_Ehdr
+# define Elf_Shdr		Elf32_Shdr
+# define Elf_Rel		Elf32_Rel
+# define Elf_Rela		Elf32_Rela
+# define Elf_Sym		Elf32_Sym
+# define ELF_R_SYM		ELF32_R_SYM
+# define Elf_r_sym		Elf32_r_sym
+# define ELF_R_INFO		ELF32_R_INFO
+# define Elf_r_info		Elf32_r_info
+# define ELF_ST_BIND		ELF32_ST_BIND
+# define ELF_ST_TYPE		ELF32_ST_TYPE
+# define fn_ELF_R_SYM		fn_ELF32_R_SYM
+# define fn_ELF_R_INFO		fn_ELF32_R_INFO
+# define uint_t			uint32_t
+# define _w			w
+#endif
+
+static int compare_extable(const void *a, const void *b)
+{
+	const uint_t *aa = a;
+	const uint_t *bb = b;
+
+	if (_w(*aa) < _w(*bb))
+		return -1;
+	if (_w(*aa) > _w(*bb))
+		return 1;
+	return 0;
+}
+
+static void
+do_func(Elf_Ehdr *const ehdr, char const *const fname)
+{
+	Elf_Shdr *shdr;
+	Elf_Shdr *shstrtab_sec;
+	Elf_Shdr *strtab_sec = NULL;
+	Elf_Shdr *symtab_sec = NULL;
+	Elf_Shdr *extab_sec = NULL;
+	Elf_Sym *sym;
+	Elf_Sym *sort_needed_sym;
+	Elf_Shdr *sort_needed_sec;
+	uint32_t *sort_done_location;
+	const char *secstrtab;
+	const char *strtab;
+	int i;
+	int idx;
+
+	shdr = (Elf_Shdr *)((void *)ehdr + _w(ehdr->e_shoff));
+	shstrtab_sec = shdr + w2(ehdr->e_shstrndx);
+	secstrtab = (const char *)ehdr + _w(shstrtab_sec->sh_offset);
+	for (i = 0; i < w2(ehdr->e_shnum); i++) {
+		idx = w(shdr[i].sh_name);
+		if (strcmp(secstrtab + idx, "__ex_table") == 0)
+			extab_sec = shdr + i;
+		if (strcmp(secstrtab + idx, ".symtab") == 0)
+			symtab_sec = shdr + i;
+		if (strcmp(secstrtab + idx, ".strtab") == 0)
+			strtab_sec = shdr + i;
+	}
+	if (strtab_sec == NULL) {
+		fprintf(stderr,	"no .strtab in  file: %s\n", fname);
+		fail_file();
+	}
+	if (symtab_sec == NULL) {
+		fprintf(stderr,	"no .symtab in  file: %s\n", fname);
+		fail_file();
+	}
+	if (extab_sec == NULL) {
+		fprintf(stderr,	"no __ex_table in  file: %s\n", fname);
+		fail_file();
+	}
+	strtab = (const char *)ehdr + _w(strtab_sec->sh_offset);
+
+	/* Sort the table in place */
+	qsort((void *)ehdr + _w(extab_sec->sh_offset),
+	      (_w(extab_sec->sh_size) / extable_ent_size),
+	      extable_ent_size, compare_extable);
+
+	/* find main_extable_sort_needed */
+	sort_needed_sym = NULL;
+	for (i = 0; i < _w(symtab_sec->sh_size) / sizeof(Elf_Sym); i++) {
+		sym = (void *)ehdr + _w(symtab_sec->sh_offset);
+		sym += i;
+		if (ELF_ST_TYPE(sym->st_info) != STT_OBJECT)
+			continue;
+		idx = w(sym->st_name);
+		if (strcmp(strtab + idx, "main_extable_sort_needed") == 0) {
+			sort_needed_sym = sym;
+			break;
+		}
+	}
+	if (sort_needed_sym == NULL) {
+		fprintf(stderr,
+			"no main_extable_sort_needed symbol in  file: %s\n",
+			fname);
+		fail_file();
+	}
+	sort_needed_sec = &shdr[w2(sort_needed_sym->st_shndx)];
+	sort_done_location = (void *)ehdr +
+		_w(sort_needed_sec->sh_offset) +
+		_w(sort_needed_sym->st_value) -
+		_w(sort_needed_sec->sh_addr);
+
+	printf("sort done marker at %lx\n",
+		(unsigned long) (_w(sort_needed_sec->sh_offset) +
+				 _w(sort_needed_sym->st_value) -
+				 _w(sort_needed_sec->sh_addr)));
+	/* We sorted it, clear the flag. */
+	*sort_done_location = 0;
+}
-- 
1.7.2.3

[PATCH v2 2/5] extable: Skip sorting if sorted at build time.

[David Daney]

From: David Daney <david.daney@cavium.com>

If the build program sortextable has already sorted the exception
table, don't sort it again.

Signed-off-by: David Daney <david.daney@cavium.com>
---
 kernel/extable.c |    8 +++++++-
 1 files changed, 7 insertions(+), 1 deletions(-)

diff --git a/kernel/extable.c b/kernel/extable.c
index 5339705..fe35a63 100644
--- a/kernel/extable.c
+++ b/kernel/extable.c
@@ -35,10 +35,16 @@ DEFINE_MUTEX(text_mutex);
 extern struct exception_table_entry __start___ex_table[];
 extern struct exception_table_entry __stop___ex_table[];
 
+/* Cleared by build time tools if the table is already sorted. */
+u32 __initdata main_extable_sort_needed = 1;
+
 /* Sort the kernel's built-in exception table */
 void __init sort_main_extable(void)
 {
-	sort_extable(__start___ex_table, __stop___ex_table);
+	if (main_extable_sort_needed)
+		sort_extable(__start___ex_table, __stop___ex_table);
+	else
+		pr_notice("__ex_table already sorted, skipping sort\n");
 }
 
 /* Given an address, look for it in the exception tables. */
-- 
1.7.2.3

[PATCH v2 3/5] kbuild/extable: Hook up sortextable into the build system.

[David Daney]

From: David Daney <david.daney@cavium.com>

Define a config variable BUILDTIME_EXTABLE_SORT to control build time
sorting of the kernel's exception table.

Patch Makefile to do the sorting when BUILDTIME_EXTABLE_SORT is
selected.

Signed-off-by: David Daney <david.daney@cavium.com>
---
 Makefile     |   10 ++++++++++
 init/Kconfig |    3 +++
 2 files changed, 13 insertions(+), 0 deletions(-)

diff --git a/Makefile b/Makefile
index ae947cc..e3bbca9 100644
--- a/Makefile
+++ b/Makefile
@@ -784,6 +784,10 @@ quiet_cmd_vmlinux_version = GEN     .version
 quiet_cmd_sysmap = SYSMAP
       cmd_sysmap = $(CONFIG_SHELL) $(srctree)/scripts/mksysmap
 
+# Sort exception table at build time
+quiet_cmd_sortextable = SORTEX
+      cmd_sortextable = $(objtree)/scripts/sortextable
+
 # Link of vmlinux
 # If CONFIG_KALLSYMS is set .version is already updated
 # Generate System.map and verify that the content is consistent
@@ -796,6 +800,12 @@ define rule_vmlinux__
 	$(call cmd,vmlinux__)
 	$(Q)echo 'cmd_$@ := $(cmd_vmlinux__)' > $(@D)/.$(@F).cmd
 
+	$(if $(CONFIG_BUILDTIME_EXTABLE_SORT),				\
+	  $(Q)$(if $($(quiet)cmd_sortextable),				\
+	    echo '  $($(quiet)cmd_sortextable)  vmlinux' &&)		\
+	  $(cmd_sortextable)  vmlinux)
+
+
 	$(Q)$(if $($(quiet)cmd_sysmap),                                      \
 	  echo '  $($(quiet)cmd_sysmap)  System.map' &&)                     \
 	$(cmd_sysmap) $@ System.map;                                         \
diff --git a/init/Kconfig b/init/Kconfig
index 6cfd71d..92a1296 100644
--- a/init/Kconfig
+++ b/init/Kconfig
@@ -27,6 +27,9 @@ config IRQ_WORK
 	bool
 	depends on HAVE_IRQ_WORK
 
+config BUILDTIME_EXTABLE_SORT
+	bool
+
 menu "General setup"
 
 config EXPERIMENTAL
-- 
1.7.2.3

[PATCH v2 4/5] MIPS: Select BUILDTIME_EXTABLE_SORT

[David Daney]

From: David Daney <david.daney@cavium.com>

We can sort the exeception table at build time for MIPS, so let's do
it.

Signed-off-by: David Daney <david.daney@cavium.com>
---
 arch/mips/Kconfig |    1 +
 1 files changed, 1 insertions(+), 0 deletions(-)

diff --git a/arch/mips/Kconfig b/arch/mips/Kconfig
index 3134457..0db1cde 100644
--- a/arch/mips/Kconfig
+++ b/arch/mips/Kconfig
@@ -29,6 +29,7 @@ config MIPS
 	select HAVE_MEMBLOCK
 	select HAVE_MEMBLOCK_NODE_MAP
 	select ARCH_DISCARD_MEMBLOCK
+	select BUILDTIME_EXTABLE_SORT
 
 menu "Machine selection"
 
-- 
1.7.2.3

[PATCH v2 5/5] x86: Select BUILDTIME_EXTABLE_SORT

[David Daney]

From: David Daney <david.daney@cavium.com>

We can sort the exeception table at build time for x86, so let's do
it.

Signed-off-by: David Daney <david.daney@cavium.com>
---
 arch/x86/Kconfig |    1 +
 1 files changed, 1 insertions(+), 0 deletions(-)

diff --git a/arch/x86/Kconfig b/arch/x86/Kconfig
index 1d14cc6..2f925cc 100644
--- a/arch/x86/Kconfig
+++ b/arch/x86/Kconfig
@@ -82,6 +82,7 @@ config X86
 	select ARCH_HAVE_NMI_SAFE_CMPXCHG
 	select GENERIC_IOMAP
 	select DCACHE_WORD_ACCESS if !DEBUG_PAGEALLOC
+	select BUILDTIME_EXTABLE_SORT
 
 config INSTRUCTION_DECODER
 	def_bool (KPROBES || PERF_EVENTS)
-- 
1.7.2.3

Re: [PATCH v1 1/5] scripts: Add sortextable to sort the kernel's exception table.

[H. Peter Anvin]

I committed this into the tip tree, but I realized something scary on
the way home... this program is broken: it doesn't handle the
relocations that go with the entries.  Specifically, it needs to not
just handle __ex_table, it also needs to handle the corresponding
entries in .rel__ex_table.

On x86-32, in particular, *most*, but not *all*, extable relocations
will have an R_386_32 relocation on it, so the resulting binary will
"mostly work"... but the ELF metadata will be wrong, and pretty much any
user of the try/catch mechanism will be broken, unless your kernel
happens to be located at its preferred address.

This needs to be addressed, either by adjusting the exception table to
be relative (which would be good for code size on 64-bit platforms)
*and* zero out the .rel__ex_table section or by making the program
actually sort the relocations correctly.

	-hpa

On 04/19/2012 02:59 PM, David Daney wrote:
> +
> +/* w8rev, w8nat, ...: Handle endianness. */
> +
> +static uint64_t w8rev(uint64_t const x)
> +{
> +	return   ((0xff & (x >> (0 * 8))) << (7 * 8))
> +	       | ((0xff & (x >> (1 * 8))) << (6 * 8))
> +	       | ((0xff & (x >> (2 * 8))) << (5 * 8))
> +	       | ((0xff & (x >> (3 * 8))) << (4 * 8))
> +	       | ((0xff & (x >> (4 * 8))) << (3 * 8))
> +	       | ((0xff & (x >> (5 * 8))) << (2 * 8))
> +	       | ((0xff & (x >> (6 * 8))) << (1 * 8))
> +	       | ((0xff & (x >> (7 * 8))) << (0 * 8));
> +}
> +
> +static uint32_t w4rev(uint32_t const x)
> +{
> +	return   ((0xff & (x >> (0 * 8))) << (3 * 8))
> +	       | ((0xff & (x >> (1 * 8))) << (2 * 8))
> +	       | ((0xff & (x >> (2 * 8))) << (1 * 8))
> +	       | ((0xff & (x >> (3 * 8))) << (0 * 8));
> +}
> +
> +static uint32_t w2rev(uint16_t const x)
> +{
> +	return   ((0xff & (x >> (0 * 8))) << (1 * 8))
> +	       | ((0xff & (x >> (1 * 8))) << (0 * 8));
> +}
> +
> +static uint64_t w8nat(uint64_t const x)
> +{
> +	return x;
> +}
> +
> +static uint32_t w4nat(uint32_t const x)
> +{
> +	return x;
> +}
> +
> +static uint32_t w2nat(uint16_t const x)
> +{
> +	return x;
> +}
> +
> +static uint64_t (*w8)(uint64_t);
> +static uint32_t (*w)(uint32_t);
> +static uint32_t (*w2)(uint16_t);

Stylistic note: these should use the <tools/*_byteshift.h> headers now.

	-hpa


-- 
H. Peter Anvin, Intel Open Source Technology Center
I work for Intel.  I don't speak on their behalf.

Re: [PATCH v1 1/5] scripts: Add sortextable to sort the kernel's exception table.

[David Daney]

On 04/19/2012 06:44 PM, H. Peter Anvin wrote:
> I committed this into the tip tree, but I realized something scary on
> the way home... this program is broken: it doesn't handle the
> relocations that go with the entries.  Specifically, it needs to not
> just handle __ex_table, it also needs to handle the corresponding
> entries in .rel__ex_table.
>
> On x86-32, in particular, *most*, but not *all*, extable relocations
> will have an R_386_32 relocation on it, so the resulting binary will
> "mostly work"... but the ELF metadata will be wrong, and pretty much any
> user of the try/catch mechanism will be broken, unless your kernel
> happens to be located at its preferred address.
>
> This needs to be addressed, either by adjusting the exception table to
> be relative (which would be good for code size on 64-bit platforms)
> *and* zero out the .rel__ex_table section or by making the program
> actually sort the relocations correctly.

Crap.

I hadn't considered that the image was relocatable.  Our MIPS kernels 
never have relocations.

I am working on a version of this that handles the relocations.  It 
shouldn't be too difficult.


> 	-hpa
>
> On 04/19/2012 02:59 PM, David Daney wrote:
>> +
>> +/* w8rev, w8nat, ...: Handle endianness. */
>> +
>> +static uint64_t w8rev(uint64_t const x)
>> +{
>> +	return   ((0xff&  (x>>  (0 * 8)))<<  (7 * 8))
>> +	       | ((0xff&  (x>>  (1 * 8)))<<  (6 * 8))
>> +	       | ((0xff&  (x>>  (2 * 8)))<<  (5 * 8))
>> +	       | ((0xff&  (x>>  (3 * 8)))<<  (4 * 8))
>> +	       | ((0xff&  (x>>  (4 * 8)))<<  (3 * 8))
>> +	       | ((0xff&  (x>>  (5 * 8)))<<  (2 * 8))
>> +	       | ((0xff&  (x>>  (6 * 8)))<<  (1 * 8))
>> +	       | ((0xff&  (x>>  (7 * 8)))<<  (0 * 8));
>> +}
>> +
>> +static uint32_t w4rev(uint32_t const x)
>> +{
>> +	return   ((0xff&  (x>>  (0 * 8)))<<  (3 * 8))
>> +	       | ((0xff&  (x>>  (1 * 8)))<<  (2 * 8))
>> +	       | ((0xff&  (x>>  (2 * 8)))<<  (1 * 8))
>> +	       | ((0xff&  (x>>  (3 * 8)))<<  (0 * 8));
>> +}
>> +
>> +static uint32_t w2rev(uint16_t const x)
>> +{
>> +	return   ((0xff&  (x>>  (0 * 8)))<<  (1 * 8))
>> +	       | ((0xff&  (x>>  (1 * 8)))<<  (0 * 8));
>> +}
>> +
>> +static uint64_t w8nat(uint64_t const x)
>> +{
>> +	return x;
>> +}
>> +
>> +static uint32_t w4nat(uint32_t const x)
>> +{
>> +	return x;
>> +}
>> +
>> +static uint32_t w2nat(uint16_t const x)
>> +{
>> +	return x;
>> +}
>> +
>> +static uint64_t (*w8)(uint64_t);
>> +static uint32_t (*w)(uint32_t);
>> +static uint32_t (*w2)(uint16_t);
> Stylistic note: these should use the<tools/*_byteshift.h>  headers now.

I will try to use those.

Thanks,
David Daney

Re: [PATCH v1 1/5] scripts: Add sortextable to sort the kernel's exception table.

[Linus Torvalds]

On Thu, Apr 19, 2012 at 8:17 PM, David Daney <david.s.daney@gmail.com> wrote:
>
> I hadn't considered that the image was relocatable.  Our MIPS kernels never
> have relocations.
>
> I am working on a version of this that handles the relocations.  It
> shouldn't be too difficult.

It might be better to just make the rule be that we don't have
relocations there - make everything relative to the start of the code
segment or something.

On x86, we already use that _ASM_EXTABLE() macro to hide the
differences between x86-64 and x86-32. So it should be be somewhat
easy to make that same macro make it relative to the code start, and
at the same time also make the exception table perhaps be two 32-bit
words rather than two pointers.

So it would shrink the exception table and avoid relocations at the
same time. Win-win. No?

                      Linus

Re: [PATCH v1 1/5] scripts: Add sortextable to sort the kernel's exception table.

[H. Peter Anvin]

On 04/19/2012 08:31 PM, Linus Torvalds wrote:
> On Thu, Apr 19, 2012 at 8:17 PM, David Daney <david.s.daney@gmail.com> wrote:
>>
>> I hadn't considered that the image was relocatable.  Our MIPS kernels never
>> have relocations.
>>
>> I am working on a version of this that handles the relocations.  It
>> shouldn't be too difficult.
> 
> It might be better to just make the rule be that we don't have
> relocations there - make everything relative to the start of the code
> segment or something.
> 
> On x86, we already use that _ASM_EXTABLE() macro to hide the
> differences between x86-64 and x86-32. So it should be be somewhat
> easy to make that same macro make it relative to the code start, and
> at the same time also make the exception table perhaps be two 32-bit
> words rather than two pointers.
> 
> So it would shrink the exception table and avoid relocations at the
> same time. Win-win. No?
> 

I don't think we can get _ASM_EXTABLE() to do that work for us, because
we'd need to subtract symbols from two different sections.  We would
need the postprocessing tool to take care this, but guess what, we can
do exactly that (and then, as I mentioned, just zero out the relocation
section.)

	-hpa

Re: [PATCH v1 1/5] scripts: Add sortextable to sort the kernel's exception table.

[H. Peter Anvin]

On 04/19/2012 08:42 PM, H. Peter Anvin wrote:
> 
> I don't think we can get _ASM_EXTABLE() to do that work for us, because
> we'd need to subtract symbols from two different sections.  We would
> need the postprocessing tool to take care this, but guess what, we can
> do exactly that (and then, as I mentioned, just zero out the relocation
> section.)
> 

Ah, apparently it is possible to generate relocations relative to the
start of the current section:

# define _ASM_EXTABLE(from,to)      			\
        __ASM_EX_SEC ;              			\
        _ASM_ALIGN ;                			\
        .long (from)-__ex_table,(to)-__ex_table ;       \
        .previous

Then all the postprocessor would have to do is to zero out the
relocation section, and we would always just add the base of the
particular __ex_table section.

We need to make sure the module loader works, too, and not to break the
__{get,put}_user_ex macros (which would need to use a new variant of
_ASM_EXTABLE()).

There is still a disturbing number of open-coded __ex_table instances
too; those all need to be converted.

Looks like a worthwhile project but not for tonight.

All of this is for x86... other architectures would need to be converted
in whatever way is appropriate.

	-hpa

Re: [PATCH v1 1/5] scripts: Add sortextable to sort the kernel's exception table.

[H. Peter Anvin]

On 04/19/2012 09:49 PM, H. Peter Anvin wrote:
> 
> Ah, apparently it is possible to generate relocations relative to the
> start of the current section.
> 

Nevermind... I'm wrong.  The assembler will generate them but the linker
will produce garbage.

So I think using PC-relative relocations and have the postprocessor (or
the sort in the module loader) convert them to section-relative makes
sense...

	-hpa

Re: [PATCH v1 1/5] scripts: Add sortextable to sort the kernel's exception table.

[Sam Ravnborg]

On Thu, Apr 19, 2012 at 02:59:55PM -0700, David Daney wrote:
> From: David Daney <david.daney@cavium.com>
> 
> Using this build-time sort saves time booting as we don't have to burn
> cycles sorting the exception table.
> 
> Signed-off-by: David Daney <david.daney@cavium.com>
> ---
>  scripts/.gitignore    |    1 +
>  scripts/Makefile      |    1 +
>  scripts/sortextable.c |  273 +++++++++++++++++++++++++++++++++++++++++++++++++
>  scripts/sortextable.h |  168 ++++++++++++++++++++++++++++++

If there is only a single file including the .h file - then there is no gain.
Just fold it into the .c file.


	Sam

Re: [PATCH v2 3/5] kbuild/extable: Hook up sortextable into the build system.

[Sam Ravnborg]

On Thu, Apr 19, 2012 at 02:59:57PM -0700, David Daney wrote:
> From: David Daney <david.daney@cavium.com>
> 
> Define a config variable BUILDTIME_EXTABLE_SORT to control build time
> sorting of the kernel's exception table.
> 
> Patch Makefile to do the sorting when BUILDTIME_EXTABLE_SORT is
> selected.
> 
> Signed-off-by: David Daney <david.daney@cavium.com>
> ---
>  Makefile     |   10 ++++++++++
>  init/Kconfig |    3 +++
>  2 files changed, 13 insertions(+), 0 deletions(-)
> 
> diff --git a/Makefile b/Makefile
> index ae947cc..e3bbca9 100644
> --- a/Makefile
> +++ b/Makefile
> @@ -784,6 +784,10 @@ quiet_cmd_vmlinux_version = GEN     .version
>  quiet_cmd_sysmap = SYSMAP
>        cmd_sysmap = $(CONFIG_SHELL) $(srctree)/scripts/mksysmap
>  
> +# Sort exception table at build time
> +quiet_cmd_sortextable = SORTEX
> +      cmd_sortextable = $(objtree)/scripts/sortextable
> +
>  # Link of vmlinux
>  # If CONFIG_KALLSYMS is set .version is already updated
>  # Generate System.map and verify that the content is consistent
> @@ -796,6 +800,12 @@ define rule_vmlinux__
>  	$(call cmd,vmlinux__)
>  	$(Q)echo 'cmd_$@ := $(cmd_vmlinux__)' > $(@D)/.$(@F).cmd
>  
> +	$(if $(CONFIG_BUILDTIME_EXTABLE_SORT),				\
> +	  $(Q)$(if $($(quiet)cmd_sortextable),				\
> +	    echo '  $($(quiet)cmd_sortextable)  vmlinux' &&)		\
> +	  $(cmd_sortextable)  vmlinux)
> +
> +

Anything that add complexity to the top-level Makefile is bad :-(
I once looked at moving all the final link stuff to a script.
Maybe it is time to open that again...


> +config BUILDTIME_EXTABLE_SORT
> +	bool
> +
Please add a comment about what this symbol is used for.
Also we often name such symbols: HAVE_*

	Sam

Re: [PATCH v1 1/5] scripts: Add sortextable to sort the kernel's exception table.

[David Daney]

On 04/20/2012 07:59 AM, Sam Ravnborg wrote:
> On Thu, Apr 19, 2012 at 02:59:55PM -0700, David Daney wrote:
>> From: David Daney<david.daney@cavium.com>
>>
>> Using this build-time sort saves time booting as we don't have to burn
>> cycles sorting the exception table.
>>
>> Signed-off-by: David Daney<david.daney@cavium.com>
>> ---
>>   scripts/.gitignore    |    1 +
>>   scripts/Makefile      |    1 +
>>   scripts/sortextable.c |  273 +++++++++++++++++++++++++++++++++++++++++++++++++
>>   scripts/sortextable.h |  168 ++++++++++++++++++++++++++++++
>
> If there is only a single file including the .h file - then there is no gain.
> Just fold it into the .c file.
>

s/single file/single site/, and I am in complete agreement.  However 
this patch doesn't meet that criterion.  In this particular case, there 
is more to the patch than just the diffstat.

David Daney