Skip to contentSkip to conversation

Speed booting by sorting ORC unwind tables at build time

RFC PATCH Superseded [email protected] 2 participants 6 messages Nov 8, 2019 – Nov 11, 2019

Subsystems (3)

v2 of 6 Superseded Latest is v6 →

lore
Share & tools
lore
#0 lore raw

v2 cover Speed booting by sorting ORC unwind tables at build time

From: Shile Zhang <[email protected]>

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
Signature · 1 line
2.24.0.rc2
#1 lore raw

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

From: Shile Zhang <[email protected]>

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

---
 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
scripts/.gitignore +1 -0
index 17f8cef88fa8..52976f32f974 100644
@@ -12,3 +12,4 @@ asn1_compiler
 extract-cert
 sign-file
 insert-sys-cert
+sortorctable
scripts/Makefile +2 -0
index 3e86b300f5a1..4473f8d7da0c 100644
@@ -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
scripts/sortorctable.c new file +251 -0

251 lines not on this page · raw message

scripts/sortorctable.h new file +26 -0
new file mode 100644
index 000000000000..af82391c70e6
@@ -0,0 +1,26 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+/*
+ * Copyright (C) 2019 Alibaba Group Holding Limited. All rights reserved.
+ * Written by Shile Zhang <[email protected]>
+ *
+ * This code was taken out of arch/x86/include/asm/orc_types.h written by:
+ * Copyright (C) 2017 Josh Poimboeuf <[email protected]>
+ */
+
+#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_
Signature · 1 line
2.24.0.rc2
maintainer
#2 lore raw

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

Quoted 4 lines · On Fri, Nov 08, 2019 at 03:11:06PM +0800, [email protected] wrote:

From: Shile Zhang <[email protected]>

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.

#3 lore raw

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

Quoted 7 lines · Peter Zijlstra
Quoted 4 lines · On Fri, Nov 08, 2019 at 03:11:06PM +0800, [email protected] wrote:

From: Shile Zhang <[email protected]>

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.

#4 lore raw

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

In reply to [email protected]

From: Shile Zhang <[email protected]>

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

---
 scripts/link-vmlinux.sh | 14 ++++++++++++++
 1 file changed, 14 insertions(+)
scripts/link-vmlinux.sh +14 -0
index 06495379fcd8..dea7797fcbdc 100755
@@ -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
 
Signature · 1 line
2.24.0.rc2
#5 lore raw

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

In reply to [email protected]

From: Shile Zhang <[email protected]>

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

---
 arch/x86/kernel/unwind_orc.c | 7 ++++---
 1 file changed, 4 insertions(+), 3 deletions(-)
arch/x86/kernel/unwind_orc.c +4 -3
index 332ae6530fa8..eccb9ac1e2fe 100644
@@ -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;
Signature · 1 line
2.24.0.rc2