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

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

[David Daney]

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

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

Any comments most welcome,

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

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

[Mike Frysinger]

[-- Attachment #1: Type: Text/Plain, Size: 805 bytes --]

On Friday 18 November 2011 14:37:44 David Daney wrote:
> --- /dev/null
> +++ b/scripts/sortextable.c
>
> +/*
> + * sortextable.c: Sort the kernel's exception table
> + *
> + * Copyright 2011 Cavium, Inc.
> + *
> + * Based on code taken from recortmcount.c which is:

seems like it'd be nice if the duplicate helper funcs were placed in a common 
header file rather than copying & pasting between them.

> +	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 */

unlike recordmcount, this file doesn't do anything arch specific.  so let's just 
delete this and be done.
-mike

[-- Attachment #2: This is a digitally signed message part. --]
[-- Type: application/pgp-signature, Size: 836 bytes --]

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

[David Daney]

On 11/20/2011 03:22 PM, Mike Frysinger wrote:
> On Friday 18 November 2011 14:37:44 David Daney wrote:
>> --- /dev/null
>> +++ b/scripts/sortextable.c
>>
>> +/*
>> + * sortextable.c: Sort the kernel's exception table
>> + *
>> + * Copyright 2011 Cavium, Inc.
>> + *
>> + * Based on code taken from recortmcount.c which is:
>
> seems like it'd be nice if the duplicate helper funcs were placed in a common
> header file rather than copying&  pasting between them.
>

Yes, I may try to factor out some common code if we decide to move 
forward with the patch set.


>> +	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 */
>
> unlike recordmcount, this file doesn't do anything arch specific.  so let's just
> delete this and be done.

Not really true at this point.  We don't know the size or layout of the 
architecture specific exception table entries, likewise for 
CONFIG_ARCH_HAS_SORT_EXTABLE, we don't even know how to do the comparison.

I was trying to be a little conservative and only apply the build time 
sort to configurations that I could test.

David Daney

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

[Mike Frysinger]

[-- Attachment #1: Type: Text/Plain, Size: 1743 bytes --]

On Monday 21 November 2011 13:25:36 David Daney wrote:
> On 11/20/2011 03:22 PM, Mike Frysinger wrote:
> > On Friday 18 November 2011 14:37:44 David Daney wrote:
> >> +	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 */
> > 
> > unlike recordmcount, this file doesn't do anything arch specific.  so
> > let's just delete this and be done.
> 
> Not really true at this point.  We don't know the size or layout of the
> architecture specific exception table entries, likewise for
> CONFIG_ARCH_HAS_SORT_EXTABLE, we don't even know how to do the comparison.

all of your code that i could see is based on "is it 32bit or is it 64bit".  
there is no code that says "if it's x86, we need to do XXX".

when i look in the kernel, we have common code behind ARCH_HAS_SORT_EXTABLE.  
so you could easily do the same thing:

scripts/sortextable.c:
	#ifdef ARCH_HAS_SORT_EXTABLE
		switch (w2(ehdr->e_machine)) {
		default:
			fprintf(stderr, "unrecognized e_machine %d %s\n",
				w2(ehdr->e_machine), fname);
			... return a unique exit code like 77 ...
			break;
		/* add arch sorting info here */
		}  /* end switch */
	#endif

kernel/extable.c:
	#if defined(ARCH_HAS_SORT_EXTABLE) && !defined(ARCH_HAS_SORTED_EXTABLE)
	void __init sort_main_extable(void)
	{
		sort_extable(__start___ex_table, __stop___ex_table);
	}
	#endif

this way all the people not doing unique stuff work out of the box.  only the 
people who are doing funky stuff need to extend things.
-mike

[-- Attachment #2: This is a digitally signed message part. --]
[-- Type: application/pgp-signature, Size: 836 bytes --]

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

[David Daney]

On 11/21/2011 10:50 AM, Mike Frysinger wrote:
> On Monday 21 November 2011 13:25:36 David Daney wrote:
>> On 11/20/2011 03:22 PM, Mike Frysinger wrote:
>>> On Friday 18 November 2011 14:37:44 David Daney wrote:
>>>> +	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 */
>>>
>>> unlike recordmcount, this file doesn't do anything arch specific.  so
>>> let's just delete this and be done.
>>
>> Not really true at this point.  We don't know the size or layout of the
>> architecture specific exception table entries, likewise for
>> CONFIG_ARCH_HAS_SORT_EXTABLE, we don't even know how to do the comparison.
>
> all of your code that i could see is based on "is it 32bit or is it 64bit".
> there is no code that says "if it's x86, we need to do XXX".

At this point there is no need.  MIPS, i386 and x86_64 all store the key 
in the first word of a two word structure.

If there were some architecture that didn't fit this model, we would 
have to create a special sorting function and select it (and perhaps 
other parameters as well) in that switch statement.


>
> when i look in the kernel, we have common code behind ARCH_HAS_SORT_EXTABLE.
> so you could easily do the same thing:
>
> scripts/sortextable.c:
> 	#ifdef ARCH_HAS_SORT_EXTABLE
> 		switch (w2(ehdr->e_machine)) {
> 		default:
> 			fprintf(stderr, "unrecognized e_machine %d %s\n",
> 				w2(ehdr->e_machine), fname);
> 			... return a unique exit code like 77 ...
> 			break;
> 		/* add arch sorting info here */
> 		}  /* end switch */
> 	#endif
>
> kernel/extable.c:
> 	#if defined(ARCH_HAS_SORT_EXTABLE)&&  !defined(ARCH_HAS_SORTED_EXTABLE)
> 	void __init sort_main_extable(void)
> 	{
> 		sort_extable(__start___ex_table, __stop___ex_table);
> 	}
> 	#endif
>


Yes, I am familiar with that code.  One thing to keep in mind is that 
the compiler has access to struct exception_table_entry, and can easily 
figure out both how big the structure is *and* where the insn field is 
within the structure.

This is not the case for the author of sortextable.  Except for MIPS, 
MIPS64, i386 and x86_64, I know neither the size of struct 
exception_table_entry, nor the offset of its insn field.

For those with knowledge of the inner working of other architectures, it 
may be as simple as a two line patch to add support, but it isn't 
something that I want to take responsibility for at this point

> this way all the people not doing unique stuff work out of the box.  only the
> people who are doing funky stuff need to extend things.

I didn't want to include something like this that I cannot test.  An 
unsorted (or improperly sorted) exception table is not necessarily 
something that will be noticeable by simply booting the kernel.  Your 
only indication may be a panic or OOPS under rarely encountered conditions.

David Daney

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

[Mike Frysinger]

[-- Attachment #1: Type: Text/Plain, Size: 3496 bytes --]

On Monday 21 November 2011 14:16:04 David Daney wrote:
> On 11/21/2011 10:50 AM, Mike Frysinger wrote:
> > On Monday 21 November 2011 13:25:36 David Daney wrote:
> >> On 11/20/2011 03:22 PM, Mike Frysinger wrote:
> >>> On Friday 18 November 2011 14:37:44 David Daney wrote:
> >>>> +	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 */
> >>> 
> >>> unlike recordmcount, this file doesn't do anything arch specific.  so
> >>> let's just delete this and be done.
> >> 
> >> Not really true at this point.  We don't know the size or layout of the
> >> architecture specific exception table entries, likewise for
> >> CONFIG_ARCH_HAS_SORT_EXTABLE, we don't even know how to do the
> >> comparison.
> > 
> > all of your code that i could see is based on "is it 32bit or is it
> > 64bit". there is no code that says "if it's x86, we need to do XXX".
> 
> At this point there is no need.  MIPS, i386 and x86_64 all store the key
> in the first word of a two word structure.
> 
> If there were some architecture that didn't fit this model, we would
> have to create a special sorting function and select it (and perhaps
> other parameters as well) in that switch statement.

that's trivial to check:
	sed -n '/^struct exception_table_entry/,/};/p'\
		arch/*/include/asm/uaccess* include/asm-generic/uaccess.h 

and indeed, the only arches that don't follow this model are the ones that 
define ARCH_HAS_SORT_EXTABLE.

> > when i look in the kernel, we have common code behind
> > ARCH_HAS_SORT_EXTABLE. so you could easily do the same thing:
> > 
> > scripts/sortextable.c:
> > 	#ifdef ARCH_HAS_SORT_EXTABLE
> > 	
> > 		switch (w2(ehdr->e_machine)) {
> > 		
> > 		default:
> > 			fprintf(stderr, "unrecognized e_machine %d %s\n",
> > 			
> > 				w2(ehdr->e_machine), fname);
> > 			
> > 			... return a unique exit code like 77 ...
> > 			break;
> > 		
> > 		/* add arch sorting info here */
> > 		}  /* end switch */
> > 	
> > 	#endif
> > 
> > kernel/extable.c:
> > 	#if defined(ARCH_HAS_SORT_EXTABLE)&&  !defined(ARCH_HAS_SORTED_EXTABLE)
> > 	void __init sort_main_extable(void)
> > 	{
> > 	
> > 		sort_extable(__start___ex_table, __stop___ex_table);
> > 	
> > 	}
> > 	#endif
> 
> Yes, I am familiar with that code.  One thing to keep in mind is that
> the compiler has access to struct exception_table_entry, and can easily
> figure out both how big the structure is *and* where the insn field is
> within the structure.
> 
> This is not the case for the author of sortextable.  Except for MIPS,
> MIPS64, i386 and x86_64, I know neither the size of struct
> exception_table_entry, nor the offset of its insn field.

a trivial sed/grep gets you the answer: they're all the same

> > this way all the people not doing unique stuff work out of the box.  only
> > the people who are doing funky stuff need to extend things.
> 
> I didn't want to include something like this that I cannot test.  An
> unsorted (or improperly sorted) exception table is not necessarily
> something that will be noticeable by simply booting the kernel.  Your
> only indication may be a panic or OOPS under rarely encountered conditions.

this is what linux-next is for :)
-mike

[-- Attachment #2: This is a digitally signed message part. --]
[-- Type: application/pgp-signature, Size: 836 bytes --]

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

[H. Peter Anvin]

On 11/18/2011 11:37 AM, 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.
> 

If we're going to do this at build time, I would suggest using a
collisionless hash instead.  The lookup time for those are O(1), but
they definitely need to be done at build time.

	-hpa

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

[H. Peter Anvin]

On 11/20/2011 03:26 PM, H. Peter Anvin wrote:
> On 11/18/2011 11:37 AM, 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.
>>
> 
> If we're going to do this at build time, I would suggest using a
> collisionless hash instead.  The lookup time for those are O(1), but
> they definitely need to be done at build time.
> 

I have some code for generating these kinds of tables, they just need to
be hooked up.  I will dig it up later today or tomorrow.

	-hpa

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

[David Woodhouse]

[-- Attachment #1: Type: text/plain, Size: 302 bytes --]

On Sun, 2011-11-20 at 15:26 -0800, H. Peter Anvin wrote:
> If we're going to do this at build time, I would suggest using a
> collisionless hash instead.  The lookup time for those are O(1), but
> they definitely need to be done at build time. 

Is the lookup time really an issue?

-- 
dwmw2

[-- Attachment #2: smime.p7s --]
[-- Type: application/x-pkcs7-signature, Size: 5818 bytes --]

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

[H. Peter Anvin]

On 11/20/2011 03:28 PM, David Woodhouse wrote:
> On Sun, 2011-11-20 at 15:26 -0800, H. Peter Anvin wrote:
>> If we're going to do this at build time, I would suggest using a
>> collisionless hash instead.  The lookup time for those are O(1), but
>> they definitely need to be done at build time. 
> 
> Is the lookup time really an issue?
> 

Probably not a big one (in most scenarios), but with better exception
handling it might stretch the usability of exceptions.  The bigger thing
is that once you're doing a build-time special handler for this
*anyway*, you might as well drive the cost of the lookup to functionally
zero.

	-hpa

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

[David Daney]

On 11/20/2011 03:26 PM, H. Peter Anvin wrote:
> On 11/18/2011 11:37 AM, 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.
>>
>
> If we're going to do this at build time, I would suggest using a
> collisionless hash instead.  The lookup time for those are O(1), but
> they definitely need to be done at build time.
>

It is my understanding that such a hash table would be sparsely 
populated, so space would have to be reserved for the empty buckets. 
The current patch, which works in-place on the fully linked vmlinux, 
doesn't have to worry about finding enough space for the table.

If we were to do the collisionless hash, we would somehow have to 
reserve space for the empty buckets.

On my test kernel, there were only 1453 entries in the exception table, 
So doing the binary search takes a maximum of 11 loads.

So, I guess I am not strongly opposed to using a collisionless hash, but 
I think it may not be worth the extra effort.

David Daney

[PATCH RFC 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 RFC 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 dab8610..747074e 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 43298f9..b1bcfbd 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

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

[Michal Marek]

On 18.11.2011 20:37, David Daney wrote:
> +	$(if $(CONFIG_BUILDTIME_EXTABLE_SORT),				\
> +	$(Q)$(if $($(quiet)cmd_sortextable),				\
> +	  echo '  $($(quiet)cmd_sortextable)  vmlinux' &&)		\
> +	  $(cmd_sortextable)  vmlinux)

Why do you opencode $(call cmd,sortextable) here?

Michal

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

[David Daney]

On 11/20/2011 05:45 AM, Michal Marek wrote:
> On 18.11.2011 20:37, David Daney wrote:
>> +	$(if $(CONFIG_BUILDTIME_EXTABLE_SORT),				\
>> +	$(Q)$(if $($(quiet)cmd_sortextable),				\
>> +	  echo '  $($(quiet)cmd_sortextable)  vmlinux'&&)		\
>> +	  $(cmd_sortextable)  vmlinux)
>
> Why do you opencode $(call cmd,sortextable) here?
>

Mostly just mimicking the other code in the vicinity.

I will try to improve it in the next version of the patch.

Thanks,
David Daney

[PATCH RFC 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 0c55582..adfe083 100644
--- a/arch/mips/Kconfig
+++ b/arch/mips/Kconfig
@@ -25,6 +25,7 @@ config MIPS
 	select GENERIC_IRQ_SHOW
 	select HAVE_ARCH_JUMP_LABEL
 	select IRQ_FORCED_THREADING
+	select BUILDTIME_EXTABLE_SORT
 
 menu "Machine selection"
 
-- 
1.7.2.3

[PATCH RFC 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 cb9a104..c6b52a6 100644
--- a/arch/x86/Kconfig
+++ b/arch/x86/Kconfig
@@ -75,6 +75,7 @@ config X86
 	select HAVE_BPF_JIT if (X86_64 && NET)
 	select CLKEVT_I8253
 	select ARCH_HAVE_NMI_SAFE_CMPXCHG
+	select BUILDTIME_EXTABLE_SORT
 
 config INSTRUCTION_DECODER
 	def_bool (KPROBES || PERF_EVENTS)
-- 
1.7.2.3

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

[Mike Frysinger]

[-- Attachment #1: Type: Text/Plain, Size: 1256 bytes --]

On Friday 18 November 2011 14:37:43 David Daney wrote:
> 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've seen this perf hit in my simulation runs too

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

i don't see much here that is arch-specific.  why have a knob at all ?  let's 
just jump in with both feet and do this for everyone :).
-mike

[-- Attachment #2: This is a digitally signed message part. --]
[-- Type: application/pgp-signature, Size: 836 bytes --]