[RFC PATCH v2 0/3] Speed booting by sorting ORC unwind tables at build time

[RFC PATCH v2 0/3] Speed booting by sorting ORC unwind tables at build time

[shile.zhang]

From: Shile Zhang <shile.zhang@linux.alibaba.com>

This series tries to sort the ORC unwind tables in vmlinux link phase at
build time, help to speed up kernel boot. It's significant for boot time
sensitive products, such as embedded device in IoT, or serverless in
cloud.

Thanks!

Changes from RFC v2:
- removed new added Kconfig and runtime sort code, advised by Josh Poimboeuf.
- some minor refactoring.

v1:
https://www.lkml.org/lkml/2019/11/7/611

Shile Zhang (3):
  scripts: Add sortorctable to sort ORC unwind tables
  kbuild: Sort ORC unwind tables in vmlinux link phase
  x86/unwind/orc: remove run-time ORC unwind tables sort

 arch/x86/kernel/unwind_orc.c |   7 +-
 scripts/.gitignore           |   1 +
 scripts/Makefile             |   2 +
 scripts/link-vmlinux.sh      |  14 ++
 scripts/sortorctable.c       | 251 +++++++++++++++++++++++++++++++++++
 scripts/sortorctable.h       |  26 ++++
 6 files changed, 298 insertions(+), 3 deletions(-)
 create mode 100644 scripts/sortorctable.c
 create mode 100644 scripts/sortorctable.h

-- 
2.24.0.rc2

[RFC PATCH v2 1/3] scripts: Add sortorctable to sort ORC unwind tables

[shile.zhang]

From: Shile Zhang <shile.zhang@linux.alibaba.com>

Sort orc_unwind and orc_unwind_ip tables at build time instead of runtime
in boot pharse can save more boot time.

Signed-off-by: Shile Zhang <shile.zhang@linux.alibaba.com>
---
 scripts/.gitignore     |   1 +
 scripts/Makefile       |   2 +
 scripts/sortorctable.c | 251 +++++++++++++++++++++++++++++++++++++++++
 scripts/sortorctable.h |  26 +++++
 4 files changed, 280 insertions(+)
 create mode 100644 scripts/sortorctable.c
 create mode 100644 scripts/sortorctable.h

diff --git a/scripts/.gitignore b/scripts/.gitignore
index 17f8cef88fa8..52976f32f974 100644
--- a/scripts/.gitignore
+++ b/scripts/.gitignore
@@ -12,3 +12,4 @@ asn1_compiler
 extract-cert
 sign-file
 insert-sys-cert
+sortorctable
diff --git a/scripts/Makefile b/scripts/Makefile
index 3e86b300f5a1..4473f8d7da0c 100644
--- a/scripts/Makefile
+++ b/scripts/Makefile
@@ -16,12 +16,14 @@ hostprogs-$(CONFIG_LOGO)         += pnmtologo
 hostprogs-$(CONFIG_VT)           += conmakehash
 hostprogs-$(BUILD_C_RECORDMCOUNT) += recordmcount
 hostprogs-$(CONFIG_BUILDTIME_EXTABLE_SORT) += sortextable
+hostprogs-$(CONFIG_UNWINDER_ORC) += sortorctable
 hostprogs-$(CONFIG_ASN1)	 += asn1_compiler
 hostprogs-$(CONFIG_MODULE_SIG_FORMAT) += sign-file
 hostprogs-$(CONFIG_SYSTEM_TRUSTED_KEYRING) += extract-cert
 hostprogs-$(CONFIG_SYSTEM_EXTRA_CERTIFICATE) += insert-sys-cert
 
 HOSTCFLAGS_sortextable.o = -I$(srctree)/tools/include
+HOSTCFLAGS_sortorctable.o = -I$(srctree)/tools/include
 HOSTCFLAGS_asn1_compiler.o = -I$(srctree)/include
 HOSTLDLIBS_sign-file = -lcrypto
 HOSTLDLIBS_extract-cert = -lcrypto
diff --git a/scripts/sortorctable.c b/scripts/sortorctable.c
new file mode 100644
index 000000000000..193e06ac2632
--- /dev/null
+++ b/scripts/sortorctable.c
@@ -0,0 +1,251 @@
+// SPDX-License-Identifier: GPL-2.0
+/*
+ * sortorctable: used to sort the ORC unwind tables
+ *
+ * Copyright (C) 2019 Alibaba Group Holding Limited. All rights reserved.
+ * Written by Shile Zhang <shile.zhang@linux.alibaba.com>
+ *
+ * Some code taken out of lib/sort.c and
+ * arch/x86/kernel/unwind_orc.c written by:
+ * Copyright (C) 2017 Josh Poimboeuf <jpoimboe@redhat.com>
+ *
+ * Strategy: alter the vmlinux file in-place
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <unistd.h>
+#include <fcntl.h>
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <string.h>
+#include <errno.h>
+#include <sys/mman.h>
+#include <elf.h>
+
+#include "sortorctable.h"
+
+int *cur_orc_ip_table;
+struct orc_entry *cur_orc_table;
+
+/**
+ * sort - sort an array of elements
+ * @base: pointer to data to sort
+ * @num: number of elements
+ * @size: size of each element
+ * @cmp_func: pointer to comparison function
+ * @swap_func: pointer to swap function
+ *
+ * This function does a heapsort on the given array. You may provide a
+ * swap_func function optimized to your element type.
+ *
+ * Sorting time is O(n log n) both on average and worst-case. While
+ * qsort is about 20% faster on average, it suffers from exploitable
+ * O(n*n) worst-case behavior and extra memory requirements that make
+ * it less suitable for kernel use.
+ */
+static void sort(void *base, size_t num, size_t size,
+	  int (*cmp_func)(const void *, const void *),
+	  void (*swap_func)(void *, void *, int size))
+{
+	/* pre-scale counters for performance */
+	int i = (num/2 - 1) * size, n = num * size, c, r;
+
+	/* heapify */
+	for ( ; i >= 0; i -= size) {
+		for (r = i; r * 2 + size < n; r  = c) {
+			c = r * 2 + size;
+			if (c < n - size &&
+					cmp_func(base + c, base + c + size) < 0)
+				c += size;
+			if (cmp_func(base + r, base + c) >= 0)
+				break;
+			swap_func(base + r, base + c, size);
+		}
+	}
+
+	/* sort */
+	for (i = n - size; i > 0; i -= size) {
+		swap_func(base, base + i, size);
+		for (r = 0; r * 2 + size < i; r = c) {
+			c = r * 2 + size;
+			if (c < i - size &&
+					cmp_func(base + c, base + c + size) < 0)
+				c += size;
+			if (cmp_func(base + r, base + c) >= 0)
+				break;
+			swap_func(base + r, base + c, size);
+		}
+	}
+}
+
+static inline unsigned long orc_ip(const int *ip)
+{
+	return (unsigned long)ip + *ip;
+}
+
+static void orc_sort_swap(void *_a, void *_b, int size)
+{
+	struct orc_entry *orc_a, *orc_b;
+	struct orc_entry orc_tmp;
+	int *a = _a, *b = _b, tmp;
+	int delta = _b - _a;
+
+	/* Swap the .orc_unwind_ip entries: */
+	tmp = *a;
+	*a = *b + delta;
+	*b = tmp - delta;
+
+	/* Swap the corresponding .orc_unwind entries: */
+	orc_a = cur_orc_table + (a - cur_orc_ip_table);
+	orc_b = cur_orc_table + (b - cur_orc_ip_table);
+	orc_tmp = *orc_a;
+	*orc_a = *orc_b;
+	*orc_b = orc_tmp;
+}
+
+static int orc_sort_cmp(const void *_a, const void *_b)
+{
+	struct orc_entry *orc_a;
+	const int *a = _a, *b = _b;
+	unsigned long a_val = orc_ip(a);
+	unsigned long b_val = orc_ip(b);
+
+	if (a_val > b_val)
+		return 1;
+	if (a_val < b_val)
+		return -1;
+
+	/*
+	 * The "weak" section terminator entries need to always be on the left
+	 * to ensure the lookup code skips them in favor of real entries.
+	 * These terminator entries exist to handle any gaps created by
+	 * whitelisted .o files which didn't get objtool generation.
+	 */
+	orc_a = cur_orc_table + (a - cur_orc_ip_table);
+	return orc_a->sp_reg == ORC_REG_UNDEFINED && !orc_a->end ? -1 : 1;
+}
+
+/* ORC unwind only supports X86_64 */
+static int do_precheck(const char *fname, void *addr)
+{
+	Elf64_Ehdr * const ehdr = addr;
+
+	if (ehdr->e_ident[EI_DATA] != ELFDATA2LSB) {
+		fprintf(stderr, "%s: unsupported ELF data encoding %d\n",
+			fname, ehdr->e_ident[EI_DATA]);
+		return 1;
+	}
+
+	if (memcmp(ELFMAG, ehdr->e_ident, SELFMAG) != 0
+	    || (ehdr->e_type != ET_EXEC && ehdr->e_type != ET_DYN)
+	    || ehdr->e_ident[EI_VERSION] != EV_CURRENT) {
+		fprintf(stderr,
+			"%s: unrecognized ET_EXEC/ET_DYN file\n", fname);
+		return 1;
+	}
+
+	if (ehdr->e_machine != EM_X86_64) {
+		fprintf(stderr, "%s: unsupported e_machine %d\n",
+			fname, ehdr->e_machine);
+		return 1;
+	}
+
+	if (ehdr->e_ident[EI_CLASS] != ELFCLASS64
+	    || ehdr->e_ehsize != sizeof(Elf64_Ehdr)
+	    || ehdr->e_shentsize != sizeof(Elf64_Shdr)) {
+		fprintf(stderr, "%s: unrecognized ELF class %d\n",
+			fname, ehdr->e_ident[EI_CLASS]);
+		return 1;
+	}
+
+	return 0;
+}
+
+static int do_sort(const char *fname, void *addr)
+{
+	unsigned int orc_size, orc_ip_size, num_entries;
+	const Elf64_Shdr *s, *_orc = NULL, *_orc_ip = NULL;
+	Elf64_Ehdr * const ehdr = (Elf64_Ehdr *)addr;
+	Elf64_Shdr * const shdr = (Elf64_Shdr *)((void *)ehdr + ehdr->e_shoff);
+	char *secstrings = (void *)ehdr + shdr[ehdr->e_shstrndx].sh_offset;
+
+	for (s = shdr; s < shdr + ehdr->e_shnum; s++) {
+		if (!strcmp(".orc_unwind_ip", secstrings + s->sh_name))
+			_orc_ip = s;
+		if (!strcmp(".orc_unwind", secstrings + s->sh_name))
+			_orc = s;
+	}
+
+	if (!_orc_ip || !_orc) {
+		fprintf(stderr,
+			"%s: cannot find ORC unwind tables\n", fname);
+		return 1;
+	}
+
+	orc_size	= _orc->sh_size;
+	orc_ip_size	= _orc_ip->sh_size;
+	num_entries	= orc_ip_size / sizeof(int);
+	cur_orc_table	= (struct orc_entry *)((void *)ehdr + _orc->sh_offset);
+	cur_orc_ip_table = (int *)((void *)ehdr + _orc_ip->sh_offset);
+
+	if (orc_ip_size % sizeof(int) != 0
+	    || orc_size % sizeof(struct orc_entry) != 0
+	    || num_entries != orc_size / sizeof(struct orc_entry)) {
+		fprintf(stderr,
+			"%s: wrong ORC unwind table entries number\n", fname);
+		return 1;
+	}
+
+	sort(cur_orc_ip_table, num_entries, sizeof(int), orc_sort_cmp,
+	     orc_sort_swap);
+
+	return 0;
+}
+
+int main(int argc, char *argv[])
+{
+	int ret = 0;
+	int fd;
+	char *fname = NULL;
+	struct stat sb;
+	void *addr = NULL;
+
+	if (argc != 2) {
+		fprintf(stderr, "usage: sortorctable vmlinux\n");
+		return 0;
+	}
+
+	fname = argv[1];
+	fd = open(fname, O_RDWR);
+	if (fd < 0 || fstat(fd, &sb) < 0) {
+		perror(fname);
+		return errno;
+	}
+
+	if (!S_ISREG(sb.st_mode)) {
+		fprintf(stderr, "'%s': not a regular file\n", fname);
+		close(fd);
+		return 1;
+	}
+
+	addr = mmap(0, sb.st_size, PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0);
+	if (addr == MAP_FAILED) {
+		fprintf(stderr, "'%s': mmap failed\n", fname);
+		close(fd);
+		return 1;
+	}
+
+	ret = do_precheck(fname, addr);
+	if (ret)
+		goto out;
+
+	ret = do_sort(fname, addr);
+
+out:
+	munmap(addr, sb.st_size);
+	close(fd);
+
+	return ret;
+}
diff --git a/scripts/sortorctable.h b/scripts/sortorctable.h
new file mode 100644
index 000000000000..af82391c70e6
--- /dev/null
+++ b/scripts/sortorctable.h
@@ -0,0 +1,26 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+/*
+ * Copyright (C) 2019 Alibaba Group Holding Limited. All rights reserved.
+ * Written by Shile Zhang <shile.zhang@linux.alibaba.com>
+ *
+ * This code was taken out of arch/x86/include/asm/orc_types.h written by:
+ * Copyright (C) 2017 Josh Poimboeuf <jpoimboe@redhat.com>
+ */
+
+#ifndef _SORTORCTABLE_H_
+#define _SORTORCTABLE_H_
+
+#include <linux/types.h>
+
+#define ORC_REG_UNDEFINED	0
+
+struct orc_entry {
+	s16		sp_offset;
+	s16		bp_offset;
+	unsigned	sp_reg:4;
+	unsigned	bp_reg:4;
+	unsigned	type:2;
+	unsigned	end:1;
+} __attribute__((packed));
+
+#endif//_SORTORCTABLE_H_
-- 
2.24.0.rc2

[RFC PATCH v2 2/3] kbuild: Sort ORC unwind tables in vmlinux link phase

[shile.zhang]

From: Shile Zhang <shile.zhang@linux.alibaba.com>

Sort the ORC unwind tables in vmlinux link phase, only for ORC unwinder.

Signed-off-by: Shile Zhang <shile.zhang@linux.alibaba.com>
---
 scripts/link-vmlinux.sh | 14 ++++++++++++++
 1 file changed, 14 insertions(+)

diff --git a/scripts/link-vmlinux.sh b/scripts/link-vmlinux.sh
index 06495379fcd8..dea7797fcbdc 100755
--- a/scripts/link-vmlinux.sh
+++ b/scripts/link-vmlinux.sh
@@ -183,6 +183,11 @@ sortextable()
 	${objtree}/scripts/sortextable ${1}
 }
 
+sortorctable()
+{
+	${objtree}/scripts/sortorctable ${1}
+}
+
 # Delete output files in case of error
 cleanup()
 {
@@ -303,6 +308,15 @@ if [ -n "${CONFIG_BUILDTIME_EXTABLE_SORT}" ]; then
 	sortextable vmlinux
 fi
 
+if [ -n "${CONFIG_UNWINDER_ORC}" ]; then
+	info SORTORC vmlinux
+	if ! sortorctable vmlinux; then
+		echo >&2 Failed to sort ORC unwind tables
+		echo >&2 Check what is wrong and try again
+		exit 1
+	fi
+fi
+
 info SYSMAP System.map
 mksysmap vmlinux System.map
 
-- 
2.24.0.rc2

[RFC PATCH v2 3/3] x86/unwind/orc: remove run-time ORC unwind tables sort

[shile.zhang]

From: Shile Zhang <shile.zhang@linux.alibaba.com>

The orc_unwind and orc_unwind_ip tables are sorted in vmlinux link phase
at build time, just remove the run-time sort.

Signed-off-by: Shile Zhang <shile.zhang@linux.alibaba.com>
---
 arch/x86/kernel/unwind_orc.c | 7 ++++---
 1 file changed, 4 insertions(+), 3 deletions(-)

diff --git a/arch/x86/kernel/unwind_orc.c b/arch/x86/kernel/unwind_orc.c
index 332ae6530fa8..eccb9ac1e2fe 100644
--- a/arch/x86/kernel/unwind_orc.c
+++ b/arch/x86/kernel/unwind_orc.c
@@ -273,9 +273,10 @@ void __init unwind_init(void)
 		return;
 	}
 
-	/* Sort the .orc_unwind and .orc_unwind_ip tables: */
-	sort(__start_orc_unwind_ip, num_entries, sizeof(int), orc_sort_cmp,
-	     orc_sort_swap);
+	/*
+	 * Note, orc_unwind and orc_unwind_ip tables has been sorted in
+	 * vmlinux link phase at build time. Its ready for binary search.
+	 */
 
 	/* Initialize the fast lookup table: */
 	lookup_num_blocks = orc_lookup_end - orc_lookup;
-- 
2.24.0.rc2

Re: [RFC PATCH v2 1/3] scripts: Add sortorctable to sort ORC unwind tables

[Peter Zijlstra]

On Fri, Nov 08, 2019 at 03:11:06PM +0800, shile.zhang@linux.alibaba.com wrote:
> From: Shile Zhang <shile.zhang@linux.alibaba.com>
> 
> Sort orc_unwind and orc_unwind_ip tables at build time instead of runtime
> in boot pharse can save more boot time.

I still object to adding a copy of sortextable instead of making one
tool for all sorts.

Re: [RFC PATCH v2 1/3] scripts: Add sortorctable to sort ORC unwind tables

[Shile Zhang]

On 2019/11/8 17:55, Peter Zijlstra wrote:
> On Fri, Nov 08, 2019 at 03:11:06PM +0800, shile.zhang@linux.alibaba.com wrote:
>> From: Shile Zhang <shile.zhang@linux.alibaba.com>
>>
>> Sort orc_unwind and orc_unwind_ip tables at build time instead of runtime
>> in boot pharse can save more boot time.
> I still object to adding a copy of sortextable instead of making one
> tool for all sorts.

I got your point, thanks for your kindly advice!
I'll try to do rework it soon.