x86: ORC unwinder (previously undwarf)

The biggest change is that undwarf was renamed to ORC. Here's the relevant explanation from the docs:

Etymology
---------

Orcs, fearsome creatures of medieval folklore, are the Dwarves' natural enemies. Similarly, the ORC unwinder was created in opposition to the complexity and slowness of DWARF.

"Although Orcs rarely consider multiple solutions to a problem, they do excel at getting things done because they are creatures of action, not thought." [3] Similarly, unlike the esoteric DWARF unwinder, the veracious ORC unwinder wastes no time or siloconic effort decoding variable-length zero-extended unsigned-integer byte-coded state-machine-based debug information entries.

Similar to how Orcs frequently unravel the well-intentioned plans of their adversaries, the ORC unwinder frequently unravels stacks with brutal, unyielding efficiency.

ORC stands for Oops Rewind Capability.

Other v3 changes:

- Rebase on tip (first 3 objtool patches were merged).
- Add Andy's patches (1-2) to fix unwinding from an empty irq stack.
- Add new patches (3-4) to fix other related issues.
- Add new patch (10) to make it easier to move from FRAME_POINTER to ORC_UNWINDER.
- Use packed struct for orc_entry (600k savings, 2% perf hit). (Ingo)
- Change the fast lookup array block size to a power of two to avoid the 'div' instruction (10% speedup).
- Allocate the fast lookup array in the vmlinux linker script, since we don't know the array size at compile time, and it's better than allocating such a big block at runtime.
- Add cache locality improvement info to docs. (Ingo)
- "orc-types.h" -> "orc_types.h" (Ingo)
- "cfa" -> "sp" (Ingo)
- struct vertical whitespace alignment (Ingo)
- short -> s16, etc (Ingo)
- asm/undwarf.h -> asm/unwind_hints.h

-----

Create a new "ORC" unwinder, enabled by CONFIG_ORC_UNWINDER, and plug it into the x86 unwinder framework. Objtool is used to generate the ORC debuginfo. The ORC debuginfo format is basically a simplified version of DWARF CFI. More details below.

The unwinder works well in my testing. It unwinds through interrupts, exceptions, and preemption, with and without frame pointers, across aligned stacks and dynamically allocated stacks. If something goes wrong during an oops, it successfully falls back to printing the '?' entries just like the frame pointer unwinder.

Some potential future improvements:
- properly annotate or fix whitelisted functions and files
- add reliability checks for livepatch
- runtime NMI stack reliability checker
- generated code integration

This code can also be found at:

https://git.kernel.org/pub/scm/linux/kernel/git/jpoimboe/linux.git orc-v3

Here's the contents of the orc-unwinder.txt file which explains the 'why' in more detail:

ORC unwinder
============

Overview
--------

The kernel CONFIG_ORC_UNWINDER option enables the ORC unwinder, which is similar in concept to a DWARF unwinder. The difference is that the format of the ORC data is much simpler than DWARF, which in turn allows the ORC unwinder to be much simpler and faster.

The ORC data consists of unwind tables which are generated by objtool. They contain out-of-band data which is used by the in-kernel ORC unwinder. Objtool generates the ORC data by first doing compile-time stack metadata validation (CONFIG_STACK_VALIDATION). After analyzing all the code paths of a .o file, it determines information about the stack state at each instruction address in the file and outputs that information to the .orc_unwind and .orc_unwind_ip sections.

The per-object ORC sections are combined at link time and are sorted and post-processed at boot time. The unwinder uses the resulting data to correlate instruction addresses with their stack states at run time.

ORC vs frame pointers
---------------------

With frame pointers enabled, GCC adds instrumentation code to every function in the kernel. The kernel's .text size increases by about 3.2%, resulting in a broad kernel-wide slowdown. Measurements by Mel Gorman [1] have shown a slowdown of 5-10% for some workloads.

In contrast, the ORC unwinder has no effect on text size or runtime performance, because the debuginfo is out of band. So if you disable frame pointers and enable the ORC unwinder, you get a nice performance improvement across the board, and still have reliable stack traces.

Ingo Molnar says:

"Note that it's not just a performance improvement, but also an instruction cache locality improvement: 3.2% .text savings almost directly transform into a similarly sized reduction in cache footprint. That can transform to even higher speedups for workloads whose cache locality is borderline."

Another benefit of ORC compared to frame pointers is that it can reliably unwind across interrupts and exceptions. Frame pointer based unwinds can sometimes skip the caller of the interrupted function, if it was a leaf function or if the interrupt hit before the frame pointer was saved.

The main disadvantage of the ORC unwinder compared to frame pointers is that it needs more memory to store the ORC unwind tables: roughly 2-4MB depending on the kernel config.

ORC vs DWARF
------------

ORC debuginfo's advantage over DWARF itself is that it's much simpler. It gets rid of the complex DWARF CFI state machine and also gets rid of the tracking of unnecessary registers. This allows the unwinder to be much simpler, meaning fewer bugs, which is especially important for mission critical oops code.

The simpler debuginfo format also enables the unwinder to be much faster than DWARF, which is important for perf and lockdep. In a basic performance test by Jiri Slaby [2], the ORC unwinder was about 20x faster than an out-of-tree DWARF unwinder. (Note: That measurement was taken before some performance tweaks were added, which doubled performance, so the speedup over DWARF may be closer to 40x.)

The ORC data format does have a few downsides compared to DWARF. The ORC unwind tables take up ~1MB more memory than DWARF eh_frame tables.

Another potential downside is that, as GCC evolves, it's conceivable that the ORC data may end up being *too* simple to describe the state of the stack for certain optimizations. But IMO this is unlikely because GCC saves the frame pointer for any unusual stack adjustments it does, so I suspect we'll really only ever need to keep track of the stack pointer and the frame pointer between call frames. But even if we do end up having to track all the registers DWARF tracks, at least we will still be able to control the format, e.g. no complex state machines.

ORC unwind table generation
---------------------------

The ORC data is generated by objtool. With the existing compile-time stack metadata validation feature, objtool already follows all code paths, and so it already has all the information it needs to be able to generate ORC data from scratch. So it's an easy step to go from stack validation to ORC data generation.

It should be possible to instead generate the ORC data with a simple tool which converts DWARF to ORC data. However, such a solution would be incomplete due to the kernel's extensive use of asm, inline asm, and special sections like exception tables.

That could be rectified by manually annotating those special code paths using GNU assembler .cfi annotations in .S files, and homegrown annotations for inline asm in .c files. But asm annotations were tried in the past and were found to be unmaintainable. They were often incorrect/incomplete and made the code harder to read and keep updated. And based on looking at glibc code, annotating inline asm in .c files might be even worse.

Objtool still needs a few annotations, but only in code which does unusual things to the stack like entry code. And even then, far fewer annotations are needed than what DWARF would need, so they're much more maintainable than DWARF CFI annotations.

So the advantages of using objtool to generate ORC data are that it gives more accurate debuginfo, with very few annotations. It also insulates the kernel from toolchain bugs which can be very painful to deal with in the kernel since we often have to workaround issues in older versions of the toolchain for years.

The downside is that the unwinder now becomes dependent on objtool's ability to reverse engineer GCC code flow. If GCC optimizations become too complicated for objtool to follow, the ORC data generation might stop working or become incomplete. (It's worth noting that livepatch already has such a dependency on objtool's ability to follow GCC code flow.)

If newer versions of GCC come up with some optimizations which break objtool, we may need to revisit the current implementation. Some possible solutions would be asking GCC to make the optimizations more palatable, or having objtool use DWARF as an additional input, or creating a GCC plugin to assist objtool with its analysis. But for now, objtool follows GCC code quite well.

Unwinder implementation details
-------------------------------

Objtool generates the ORC data by integrating with the compile-time stack metadata validation feature, which is described in detail in tools/objtool/Documentation/stack-validation.txt. After analyzing all the code paths of a .o file, it creates an array of orc_entry structs, and a parallel array of instruction addresses associated with those structs, and writes them to the .orc_unwind and .orc_unwind_ip sections respectively.

The ORC data is split into the two arrays for performance reasons, to make the searchable part of the data (.orc_unwind_ip) more compact. The arrays are sorted in parallel at boot time.

Performance is further improved by the use of a fast lookup table which is created at runtime. The fast lookup table associates a given address with a range of indices for the .orc_unwind table, so that only a small subset of the table needs to be searched.

Etymology
---------

Orcs, fearsome creatures of medieval folklore, are the Dwarves' natural enemies. Similarly, the ORC unwinder was created in opposition to the complexity and slowness of DWARF.

"Although Orcs rarely consider multiple solutions to a problem, they do excel at getting things done because they are creatures of action, not thought." [3] Similarly, unlike the esoteric DWARF unwinder, the veracious ORC unwinder wastes no time or siloconic effort decoding variable-length zero-extended unsigned-integer byte-coded state-machine-based debug information entries.

Similar to how Orcs frequently unravel the well-intentioned plans of their adversaries, the ORC unwinder frequently unravels stacks with brutal, unyielding efficiency.

ORC stands for Oops Rewind Capability.

[1] https://lkml.kernel.org/r/[email protected]
[2] https://lkml.kernel.org/r/[email protected]
[3] http://dustin.wikidot.com/half-orcs-and-orcs

Andy Lutomirski (2):
x86/entry/64: Refactor IRQ stacks and make them NMI-safe x86/entry/64: Initialize the top of the IRQ stack before switching
stacks

Josh Poimboeuf (8):
x86/dumpstack: fix occasionally missing registers x86/dumpstack: fix interrupt and exception stack boundary checks
objtool: add ORC unwind table generation
objtool, x86: add facility for asm code to provide unwind hints x86/entry/64: add unwind hint annotations
x86/asm: add unwind hint annotations to sync_core() x86/unwind: add ORC unwinder
x86/kconfig: make it easier to switch to the new ORC unwinder

 Documentation/x86/orc-unwinder.txt               | 178 +++++++
 arch/um/include/asm/unwind.h                     |   8 +
 arch/x86/Kconfig                                 |   1 +
 arch/x86/Kconfig.debug                           |  26 +-
 arch/x86/entry/Makefile                          |   1 -
 arch/x86/entry/calling.h                         |   5 +
 arch/x86/entry/entry_64.S                        | 170 +++++--
 arch/x86/include/asm/module.h                    |   9 +
 arch/x86/include/asm/orc_lookup.h                |  46 ++
 arch/x86/include/asm/orc_types.h                 | 107 +++++
 arch/x86/include/asm/processor.h                 |   3 +
 arch/x86/include/asm/unwind.h                    |  76 +--
 arch/x86/include/asm/unwind_hints.h              | 103 ++++
 arch/x86/kernel/Makefile                         |   8 +-
 arch/x86/kernel/dumpstack.c                      |  12 +-
 arch/x86/kernel/dumpstack_32.c                   |   4 +-
 arch/x86/kernel/dumpstack_64.c                   |   4 +-
 arch/x86/kernel/module.c                         |  11 +-
 arch/x86/kernel/process_64.c                     |   3 +
 arch/x86/kernel/setup.c                          |   3 +
 arch/x86/kernel/unwind_frame.c                   |  39 +-
 arch/x86/kernel/unwind_guess.c                   |   5 +
 arch/x86/kernel/unwind_orc.c                     | 576 +++++++++++++++++++++++
 arch/x86/kernel/vmlinux.lds.S                    |   3 +
 include/asm-generic/vmlinux.lds.h                |  27 +-
 lib/Kconfig.debug                                |   9 +-
 scripts/Makefile.build                           |  14 +-
 tools/objtool/Build                              |   3 +
 tools/objtool/Documentation/stack-validation.txt |  56 +--
 tools/objtool/Makefile                           |   3 +
 tools/objtool/builtin-check.c                    |   2 +-
 tools/objtool/builtin-orc.c                      |  70 +++
 tools/objtool/builtin.h                          |   1 +
 tools/objtool/check.c                            | 249 +++++++++-
 tools/objtool/check.h                            |  19 +-
 tools/objtool/elf.c                              | 212 ++++++++-
 tools/objtool/elf.h                              |  15 +-
 tools/objtool/objtool.c                          |   3 +-
 tools/objtool/{builtin.h => orc.h}               |  18 +-
 tools/objtool/orc_dump.c                         | 212 +++++++++
 tools/objtool/orc_gen.c                          | 214 +++++++++
 tools/objtool/orc_types.h                        | 107 +++++
 42 files changed, 2449 insertions(+), 186 deletions(-)
 create mode 100644 Documentation/x86/orc-unwinder.txt
 create mode 100644 arch/um/include/asm/unwind.h
 create mode 100644 arch/x86/include/asm/orc_lookup.h
 create mode 100644 arch/x86/include/asm/orc_types.h
 create mode 100644 arch/x86/include/asm/unwind_hints.h
 create mode 100644 arch/x86/kernel/unwind_orc.c
 create mode 100644 tools/objtool/builtin-orc.c
 copy tools/objtool/{builtin.h => orc.h} (69%)
 create mode 100644 tools/objtool/orc_dump.c
 create mode 100644 tools/objtool/orc_gen.c
 create mode 100644 tools/objtool/orc_types.h

2.7.5

From: Andy Lutomirski <[email protected]>

This will allow IRQ stacks to nest inside NMIs or similar entries that can happen during IRQ stack setup or teardown.

The new macros won't work correctly if they're invoked with IRQs on. Add a check under CONFIG_DEBUG_ENTRY to detect that.

[ Use %r10 instead of %r11 in xen_do_hypervisor_callback to make objtool
and ORC unwinder's lives a little easier. ]

---
 arch/x86/Kconfig.debug       |  2 --
 arch/x86/entry/entry_64.S    | 85 +++++++++++++++++++++++++++++++-------------
 arch/x86/kernel/process_64.c |  3 ++
 3 files changed, 64 insertions(+), 26 deletions(-)

index fcb7604..353ed09 100644
@@ -305,8 +305,6 @@ config DEBUG_ENTRY
 	  Some of these sanity checks may slow down kernel entries and
 	  exits or otherwise impact performance.
 
-	  This is currently used to help test NMI code.
-
 	  If unsure, say N.
 
 config DEBUG_NMI_SELFTEST

index c3169be..2987e39 100644
@@ -279,6 +279,9 @@ __switch_to(struct task_struct *prev_p, struct task_struct *next_p)
 	struct tss_struct *tss = &per_cpu(cpu_tss, cpu);
 	unsigned prev_fsindex, prev_gsindex;
 
+	WARN_ON_ONCE(IS_ENABLED(CONFIG_DEBUG_ENTRY) &&
+		     this_cpu_read(irq_count) != -1);
+
 	switch_fpu_prepare(prev_fpu, cpu);
 
 	/* We must save %fs and %gs before load_TLS() because

2.7.5

From: Andy Lutomirski <[email protected]>

The OOPS unwinder wants the word at the top of the IRQ stack to point back to the previous stack at all times when the IRQ stack is in use. There's currently a one-instruction window in ENTER_IRQ_STACK during which this isn't the case. Fix it by writing the old RSP to the top of the IRQ stack before jumping.

This currently writes the pointer to the stack twice, which is a bit ugly. We could get rid of this by replacing irq_stack_ptr with irq_stack_ptr_minus_eight (better name welcome). OTOH, there may be all kinds of odd microarchitectural considerations in play that affect performance by a few cycles here.

---
 arch/x86/entry/entry_64.S | 24 +++++++++++++++++++++++-
 1 file changed, 23 insertions(+), 1 deletion(-)

index 0d4483a..b56f7f2 100644
@@ -469,6 +469,7 @@ END(irq_entries_start)
 	DEBUG_ENTRY_ASSERT_IRQS_OFF
 	movq	%rsp, \old_rsp
 	incl	PER_CPU_VAR(irq_count)
+	jnz	.Lirq_stack_push_old_rsp_\@
 
 	/*
 	 * Right now, if we just incremented irq_count to zero, we've

@@ -478,9 +479,30 @@ END(irq_entries_start)
 	 * it must be *extremely* careful to limit its stack usage.  This
 	 * could include kprobes and a hypothetical future IST-less #DB
 	 * handler.
+	 *
+	 * The OOPS unwinder relies on the word at the top of the IRQ
+	 * stack linking back to the previous RSP for the entire time we're
+	 * on the IRQ stack.  For this to work reliably, we need to write
+	 * it before we actually move ourselves to the IRQ stack.
+	 */
+
+	movq	\old_rsp, PER_CPU_VAR(irq_stack_union + IRQ_STACK_SIZE - 8)
+	movq	PER_CPU_VAR(irq_stack_ptr), %rsp
+
+#ifdef CONFIG_DEBUG_ENTRY
+	/*
+	 * If the first movq above becomes wrong due to IRQ stack layout
+	 * changes, the only way we'll notice is if we try to unwind right
+	 * here.  Assert that we set up the stack right to catch this type
+	 * of bug quickly.
 	 */
+	cmpq	-8(%rsp), \old_rsp
+	je	.Lirq_stack_okay\@
+	ud2
+	.Lirq_stack_okay\@:
+#endif
 
-	cmovzq	PER_CPU_VAR(irq_stack_ptr), %rsp
+.Lirq_stack_push_old_rsp_\@:
 	pushq	\old_rsp
 .endm
 

2.7.5

If two consecutive stack frames have pt_regs, the oops dump code fails to print the second frame's registers. Fix that.

---
 arch/x86/kernel/dumpstack.c | 12 +++++++-----
 1 file changed, 7 insertions(+), 5 deletions(-)

index dbce3cc..bd265a4 100644
@@ -94,6 +94,9 @@ void show_trace_log_lvl(struct task_struct *task, struct pt_regs *regs,
 		if (stack_name)
 			printk("%s <%s>\n", log_lvl, stack_name);
 
+		if (regs && on_stack(&stack_info, regs, sizeof(*regs)))
+			__show_regs(regs, 0);
+
 		/*
 		 * Scan the stack, printing any text addresses we find.  At the
 		 * same time, follow proper stack frames with the unwinder.

@@ -118,10 +121,8 @@ void show_trace_log_lvl(struct task_struct *task, struct pt_regs *regs,
 			 * Don't print regs->ip again if it was already printed
 			 * by __show_regs() below.
 			 */
-			if (regs && stack == &regs->ip) {
-				unwind_next_frame(&state);
-				continue;
-			}
+			if (regs && stack == &regs->ip)
+				goto next;
 
 			if (stack == ret_addr_p)
 				reliable = 1;

@@ -144,6 +145,7 @@ void show_trace_log_lvl(struct task_struct *task, struct pt_regs *regs,
 			if (!reliable)
 				continue;
 
+next:
 			/*
 			 * Get the next frame from the unwinder.  No need to
 			 * check for an error: if anything goes wrong, the rest

@@ -153,7 +155,7 @@ void show_trace_log_lvl(struct task_struct *task, struct pt_regs *regs,
 
 			/* if the frame has entry regs, print them */
 			regs = unwind_get_entry_regs(&state);
-			if (regs)
+			if (regs && on_stack(&stack_info, regs, sizeof(*regs)))
 				__show_regs(regs, 0);
 		}
 

2.7.5

On x86_64, the double fault exception stack is located immediately after the interrupt stack in memory. This causes confusion in the unwinder when it tries to unwind through an empty interrupt stack, where the stack pointer points to the address bordering the two stacks. The unwinder incorrectly thinks it's running on the double fault stack.

Fix this kind of stack border confusion by never considering the beginning address of an exception or interrupt stack to be part of the stack.

---
 arch/x86/kernel/dumpstack_32.c | 4 ++--
 arch/x86/kernel/dumpstack_64.c | 4 ++--
 2 files changed, 4 insertions(+), 4 deletions(-)

index e5f0b40..4f04814 100644
@@ -37,7 +37,7 @@ static bool in_hardirq_stack(unsigned long *stack, struct stack_info *info)
 	 * This is a software stack, so 'end' can be a valid stack pointer.
 	 * It just means the stack is empty.
 	 */
-	if (stack < begin || stack > end)
+	if (stack <= begin || stack > end)
 		return false;
 
 	info->type	= STACK_TYPE_IRQ;

@@ -62,7 +62,7 @@ static bool in_softirq_stack(unsigned long *stack, struct stack_info *info)
 	 * This is a software stack, so 'end' can be a valid stack pointer.
 	 * It just means the stack is empty.
 	 */
-	if (stack < begin || stack > end)
+	if (stack <= begin || stack > end)
 		return false;
 
 	info->type	= STACK_TYPE_SOFTIRQ;

index 3e1471d..225af41 100644
@@ -55,7 +55,7 @@ static bool in_exception_stack(unsigned long *stack, struct stack_info *info)
 		begin = end - (exception_stack_sizes[k] / sizeof(long));
 		regs  = (struct pt_regs *)end - 1;
 
-		if (stack < begin || stack >= end)
+		if (stack <= begin || stack >= end)
 			continue;
 
 		info->type	= STACK_TYPE_EXCEPTION + k;

@@ -78,7 +78,7 @@ static bool in_irq_stack(unsigned long *stack, struct stack_info *info)
 	 * This is a software stack, so 'end' can be a valid stack pointer.
 	 * It just means the stack is empty.
 	 */
-	if (stack < begin || stack > end)
+	if (stack <= begin || stack > end)
 		return false;
 
 	info->type	= STACK_TYPE_IRQ;

2.7.5

Now that objtool knows the states of all registers on the stack for each instruction, it's straightforward to generate debuginfo for an unwinder to use.

Instead of generating DWARF, generate a new format called ORC, which is more suitable for an in-kernel unwinder. See Documentation/x86/orc-unwinder.txt for a more detailed description of this new debuginfo format and why it's preferable to DWARF.

---
 tools/objtool/Build                              |   3 +
 tools/objtool/Documentation/stack-validation.txt |  56 ++----
 tools/objtool/builtin-check.c                    |   2 +-
 tools/objtool/builtin-orc.c                      |  70 ++++++++
 tools/objtool/builtin.h                          |   1 +
 tools/objtool/check.c                            |  58 +++++-
 tools/objtool/check.h                            |  15 +-
 tools/objtool/elf.c                              | 212 ++++++++++++++++++++--
 tools/objtool/elf.h                              |  15 +-
 tools/objtool/objtool.c                          |   3 +-
 tools/objtool/{builtin.h => orc.h}               |  18 +-
 tools/objtool/orc_dump.c                         | 212 ++++++++++++++++++++++
 tools/objtool/orc_gen.c                          | 214 +++++++++++++++++++++++
 tools/objtool/orc_types.h                        |  85 +++++++++
 14 files changed, 899 insertions(+), 65 deletions(-)
 create mode 100644 tools/objtool/builtin-orc.c
 copy tools/objtool/{builtin.h => orc.h} (69%)
 create mode 100644 tools/objtool/orc_dump.c
 create mode 100644 tools/objtool/orc_gen.c
 create mode 100644 tools/objtool/orc_types.h

index 6f2e198..749becd 100644
@@ -1,6 +1,9 @@
 objtool-y += arch/$(SRCARCH)/
 objtool-y += builtin-check.o
+objtool-y += builtin-orc.o
 objtool-y += check.o
+objtool-y += orc_gen.o
+objtool-y += orc_dump.o
 objtool-y += elf.o
 objtool-y += special.o
 objtool-y += objtool.o

index 365c34e..eedf089 100644
@@ -52,5 +52,5 @@ int cmd_check(int argc, const char **argv)
 
 	objname = argv[0];
 
-	return check(objname, nofp);
+	return check(objname, nofp, false);
 }

index 34d2ba7..dd52606 100644
@@ -18,5 +18,6 @@
 #define _BUILTIN_H
 
 extern int cmd_check(int argc, const char **argv);
+extern int cmd_orc(int argc, const char **argv);
 
 #endif /* _BUILTIN_H */

index da85f5b..046874b 100644
@@ -22,12 +22,14 @@
 #include "elf.h"
 #include "cfi.h"
 #include "arch.h"
+#include "orc.h"
 #include <linux/hashtable.h>
 
 struct insn_state {
 	struct cfi_reg cfa;
 	struct cfi_reg regs[CFI_NUM_REGS];
 	int stack_size;
+	unsigned char type;
 	bool bp_scratch;
 	bool drap;
 	int drap_reg;

@@ -48,6 +50,7 @@ struct instruction {
 	struct symbol *func;
 	struct stack_op stack_op;
 	struct insn_state state;
+	struct orc_entry orc;
 };
 
 struct objtool_file {

@@ -58,9 +61,19 @@ struct objtool_file {
 	bool ignore_unreachables, c_file;
 };
 
-int check(const char *objname, bool nofp);
+int check(const char *objname, bool nofp, bool orc);
+
+struct instruction *find_insn(struct objtool_file *file,
+			      struct section *sec, unsigned long offset);
 
 #define for_each_insn(file, insn)					\
 	list_for_each_entry(insn, &file->insn_list, list)
 
+#define sec_for_each_insn(file, sec, insn)				\
+	for (insn = find_insn(file, sec, 0);				\
+	     insn && &insn->list != &file->insn_list &&			\
+			insn->sec == sec;				\
+	     insn = list_next_entry(insn, list))
+
+
 #endif /* _CHECK_H */

index 343968b..d86e2ff1 100644
@@ -28,6 +28,13 @@
 # define elf_getshdrstrndx elf_getshstrndx
 #endif
 
+/*
+ * Fallback for systems without this "read, mmaping if possible" cmd.
+ */
+#ifndef ELF_C_READ_MMAP
+#define ELF_C_READ_MMAP ELF_C_READ
+#endif
+
 struct section {
 	struct list_head list;
 	GElf_Shdr sh;

@@ -41,6 +48,7 @@ struct section {
 	char *name;
 	int idx;
 	unsigned int len;
+	bool changed, text;
 };
 
 struct symbol {

@@ -75,7 +83,7 @@ struct elf {
 };
 
 
-struct elf *elf_open(const char *name);
+struct elf *elf_open(const char *name, int flags);
 struct section *find_section_by_name(struct elf *elf, const char *name);
 struct symbol *find_symbol_by_offset(struct section *sec, unsigned long offset);
 struct symbol *find_symbol_containing(struct section *sec, unsigned long offset);

@@ -83,6 +91,11 @@ struct rela *find_rela_by_dest(struct section *sec, unsigned long offset);
 struct rela *find_rela_by_dest_range(struct section *sec, unsigned long offset,
 				     unsigned int len);
 struct symbol *find_containing_func(struct section *sec, unsigned long offset);
+struct section *elf_create_section(struct elf *elf, const char *name, size_t
+				   entsize, int nr);
+struct section *elf_create_rela_section(struct elf *elf, struct section *base);
+int elf_rebuild_rela_section(struct section *sec);
+int elf_write(struct elf *elf);
 void elf_close(struct elf *elf);
 
 #define for_each_sec(file, sec)						\

index ecc5b1b..31e0f91 100644
@@ -42,10 +42,11 @@ struct cmd_struct {
 };
 
 static const char objtool_usage_string[] =
-	"objtool [OPTIONS] COMMAND [ARGS]";
+	"objtool COMMAND [ARGS]";
 
 static struct cmd_struct objtool_cmds[] = {
 	{"check",	cmd_check,	"Perform stack metadata validation on an object file" },
+	{"orc",		cmd_orc,	"Generate in-place ORC unwind tables for an object file" },
 };
 
 bool help;

similarity index 69%
copy from tools/objtool/builtin.h
copy to tools/objtool/orc.h
index 34d2ba7..a4139e3 100644
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2015 Josh Poimboeuf <[email protected]>
+ * Copyright (C) 2017 Josh Poimboeuf <[email protected]>
  *
  * This program is free software; you can redistribute it and/or
  * modify it under the terms of the GNU General Public License

@@ -14,9 +14,17 @@
  * You should have received a copy of the GNU General Public License
  * along with this program; if not, see <http://www.gnu.org/licenses/>.
  */
-#ifndef _BUILTIN_H
-#define _BUILTIN_H
 
-extern int cmd_check(int argc, const char **argv);
+#ifndef _ORC_H
+#define _ORC_H
 
-#endif /* _BUILTIN_H */
+#include "orc_types.h"
+
+struct objtool_file;
+
+int create_orc(struct objtool_file *file);
+int create_orc_sections(struct objtool_file *file);
+
+int orc_dump(const char *objname);
+
+#endif /* _ORC_H */

2.7.5

Some asm (and inline asm) code does special things to the stack which objtool can't understand. (Nor can GCC or GNU assembler, for that matter.) In such cases we need a facility for the code to provide annotations, so the unwinder can unwind through it.

This provides such a facility, in the form of unwind hints. They're similar to the GNU assembler .cfi* directives, but they give more information, and are needed in far fewer places, because objtool can fill in the blanks by following branches and adjusting the stack pointer for pushes and pops.

---
 .../objtool => arch/x86/include/asm}/orc_types.h   |  24 ++-
 arch/x86/include/asm/unwind_hints.h                | 103 +++++++++++
 tools/objtool/Makefile                             |   3 +
 tools/objtool/check.c                              | 191 +++++++++++++++++++--
 tools/objtool/check.h                              |   4 +-
 tools/objtool/orc_types.h                          |  22 +++
 6 files changed, 333 insertions(+), 14 deletions(-)
 copy {tools/objtool => arch/x86/include/asm}/orc_types.h (82%)
 create mode 100644 arch/x86/include/asm/unwind_hints.h

similarity index 82%
copy from tools/objtool/orc_types.h
copy to arch/x86/include/asm/orc_types.h
index fc5cf6c..7dc777a 100644
@@ -61,11 +61,19 @@
  *
  * ORC_TYPE_REGS_IRET: Used in entry code to indicate that sp_reg+sp_offset
  * points to the iret return frame.
+ *
+ * The UNWIND_HINT macros are used only for the unwind_hint struct.  They
+ * aren't used in struct orc_entry due to size and complexity constraints.
+ * Objtool converts them to real types when it converts the hints to orc
+ * entries.
  */
 #define ORC_TYPE_CALL			0
 #define ORC_TYPE_REGS			1
 #define ORC_TYPE_REGS_IRET		2
+#define UNWIND_HINT_TYPE_SAVE		3
+#define UNWIND_HINT_TYPE_RESTORE	4
 
+#ifndef __ASSEMBLY__
 /*
  * This struct is more or less a vastly simplified version of the DWARF Call
  * Frame Information standard.  It contains only the necessary parts of DWARF

@@ -80,6 +88,20 @@ struct orc_entry {
 	unsigned	sp_reg:4;
 	unsigned	bp_reg:4;
 	unsigned	type:2;
-} __packed;
+};
+
+/*
+ * This struct is used by asm and inline asm code to manually annotate the
+ * location of registers on the stack for the ORC unwinder.
+ *
+ * Type can be either ORC_TYPE_* or UNWIND_HINT_TYPE_*.
+ */
+struct unwind_hint {
+	u32		ip;
+	s16		sp_offset;
+	u8		sp_reg;
+	u8		type;
+};
+#endif /* __ASSEMBLY__ */
 
 #endif /* _ORC_TYPES_H */

index 0e2765e..3a6425f 100644
@@ -52,6 +52,9 @@ $(OBJTOOL): $(LIBSUBCMD) $(OBJTOOL_IN)
 	diff -I'^#include' arch/x86/insn/inat.h ../../arch/x86/include/asm/inat.h >/dev/null && \
 	diff -I'^#include' arch/x86/insn/inat_types.h ../../arch/x86/include/asm/inat_types.h >/dev/null) \
 	|| echo "warning: objtool: x86 instruction decoder differs from kernel" >&2 )) || true
+	@(test -d ../../kernel -a -d ../../tools -a -d ../objtool && (( \
+	diff ../../arch/x86/include/asm/orc_types.h orc_types.h >/dev/null) \
+	|| echo "warning: objtool: orc_types.h differs from kernel" >&2 )) || true
 	$(QUIET_LINK)$(CC) $(OBJTOOL_IN) $(LDFLAGS) -o $@
 
 

index 046874b..ac3d4b1 100644
@@ -43,7 +43,7 @@ struct instruction {
 	unsigned int len;
 	unsigned char type;
 	unsigned long immediate;
-	bool alt_group, visited, dead_end, ignore;
+	bool alt_group, visited, dead_end, ignore, hint, save, restore;
 	struct symbol *call_dest;
 	struct instruction *jump_dest;
 	struct list_head alts;

@@ -58,7 +58,7 @@ struct objtool_file {
 	struct list_head insn_list;
 	DECLARE_HASHTABLE(insn_hash, 16);
 	struct section *rodata, *whitelist;
-	bool ignore_unreachables, c_file;
+	bool ignore_unreachables, c_file, hints;
 };
 
 int check(const char *objname, bool nofp, bool orc);

index fc5cf6c..9c9dc57 100644
@@ -61,11 +61,19 @@
  *
  * ORC_TYPE_REGS_IRET: Used in entry code to indicate that sp_reg+sp_offset
  * points to the iret return frame.
+ *
+ * The UNWIND_HINT macros are used only for the unwind_hint struct.  They
+ * aren't used in struct orc_entry due to size and complexity constraints.
+ * Objtool converts them to real types when it converts the hints to orc
+ * entries.
  */
 #define ORC_TYPE_CALL			0
 #define ORC_TYPE_REGS			1
 #define ORC_TYPE_REGS_IRET		2
+#define UNWIND_HINT_TYPE_SAVE		3
+#define UNWIND_HINT_TYPE_RESTORE	4
 
+#ifndef __ASSEMBLY__
 /*
  * This struct is more or less a vastly simplified version of the DWARF Call
  * Frame Information standard.  It contains only the necessary parts of DWARF

@@ -82,4 +90,18 @@ struct orc_entry {
 	unsigned	type:2;
 } __packed;
 
+/*
+ * This struct is used by asm and inline asm code to manually annotate the
+ * location of registers on the stack for the ORC unwinder.
+ *
+ * Type can be either ORC_TYPE_* or UNWIND_HINT_TYPE_*.
+ */
+struct unwind_hint {
+	u32		ip;
+	s16		sp_offset;
+	u8		sp_reg;
+	u8		type;
+};
+#endif /* __ASSEMBLY__ */
+
 #endif /* _ORC_TYPES_H */

2.7.5

Add unwind hint annotations to entry_64.S. This will enable the ORC unwinder to unwind through any location in the entry code including syscalls, interrupts, and exceptions.

---
 arch/x86/entry/Makefile   |  1 -
 arch/x86/entry/calling.h  |  5 ++++
 arch/x86/entry/entry_64.S | 71 ++++++++++++++++++++++++++++++++++++++++-------
 3 files changed, 66 insertions(+), 11 deletions(-)

index 9976fce..af28a8a 100644
@@ -2,7 +2,6 @@
 # Makefile for the x86 low level entry code
 #
 
-OBJECT_FILES_NON_STANDARD_entry_$(BITS).o   := y
 OBJECT_FILES_NON_STANDARD_entry_64_compat.o := y
 
 CFLAGS_syscall_64.o		+= $(call cc-option,-Wno-override-init,)

index 05ed3d3..640aafe 100644
@@ -1,4 +1,5 @@
 #include <linux/jump_label.h>
+#include <asm/unwind_hints.h>
 
 /*
 

@@ -112,6 +113,7 @@ For 32-bit we have the following conventions - kernel is built with
 	movq %rdx, 12*8+\offset(%rsp)
 	movq %rsi, 13*8+\offset(%rsp)
 	movq %rdi, 14*8+\offset(%rsp)
+	UNWIND_HINT_REGS offset=\offset extra=0
 	.endm
 	.macro SAVE_C_REGS offset=0
 	SAVE_C_REGS_HELPER \offset, 1, 1, 1, 1

@@ -136,6 +138,7 @@ For 32-bit we have the following conventions - kernel is built with
 	movq %r12, 3*8+\offset(%rsp)
 	movq %rbp, 4*8+\offset(%rsp)
 	movq %rbx, 5*8+\offset(%rsp)
+	UNWIND_HINT_REGS offset=\offset
 	.endm
 
 	.macro RESTORE_EXTRA_REGS offset=0

@@ -145,6 +148,7 @@ For 32-bit we have the following conventions - kernel is built with
 	movq 3*8+\offset(%rsp), %r12
 	movq 4*8+\offset(%rsp), %rbp
 	movq 5*8+\offset(%rsp), %rbx
+	UNWIND_HINT_REGS offset=\offset extra=0
 	.endm
 
 	.macro RESTORE_C_REGS_HELPER rstor_rax=1, rstor_rcx=1, rstor_r11=1, rstor_r8910=1, rstor_rdx=1

@@ -167,6 +171,7 @@ For 32-bit we have the following conventions - kernel is built with
 	.endif
 	movq 13*8(%rsp), %rsi
 	movq 14*8(%rsp), %rdi
+	UNWIND_HINT_IRET_REGS offset=16*8
 	.endm
 	.macro RESTORE_C_REGS
 	RESTORE_C_REGS_HELPER 1,1,1,1,1

2.7.5

This enables objtool to grok the iret in the middle of a C function.

---
 arch/x86/include/asm/processor.h | 3 +++
 1 file changed, 3 insertions(+)

index 6a79547..b27dc9b 100644
@@ -22,6 +22,7 @@ struct vm86;
 #include <asm/nops.h>
 #include <asm/special_insns.h>
 #include <asm/fpu/types.h>
+#include <asm/unwind_hints.h>
 
 #include <linux/personality.h>
 #include <linux/cache.h>

@@ -684,6 +685,7 @@ static inline void sync_core(void)
 	unsigned int tmp;
 
 	asm volatile (
+		UNWIND_HINT_SAVE
 		"mov %%ss, %0\n\t"
 		"pushq %q0\n\t"
 		"pushq %%rsp\n\t"

@@ -693,6 +695,7 @@ static inline void sync_core(void)
 		"pushq %q0\n\t"
 		"pushq $1f\n\t"
 		"iretq\n\t"
+		UNWIND_HINT_RESTORE
 		"1:"
 		: "=&r" (tmp), "+r" (__sp) : : "cc", "memory");
 #endif

2.7.5

Add a new ORC unwinder which is enabled by CONFIG_ORC_UNWINDER. It plugs into the existing x86 unwinder framework.

It relies on objtool to generate the needed .orc_unwind and .orc_unwind_ip sections.

For more details on why ORC is used instead of DWARF, see Documentation/x86/orc-unwinder.txt.

Thanks to Andy Lutomirski for the performance improvement ideas:
splitting the ORC unwind table into two parallel arrays and creating a fast lookup table to search a subset of the unwind table.

---
 Documentation/x86/orc-unwinder.txt | 178 ++++++++++++
 arch/um/include/asm/unwind.h       |   8 +
 arch/x86/Kconfig                   |   1 +
 arch/x86/Kconfig.debug             |  25 ++
 arch/x86/include/asm/module.h      |   9 +
 arch/x86/include/asm/orc_lookup.h  |  46 +++
 arch/x86/include/asm/orc_types.h   |   2 +-
 arch/x86/include/asm/unwind.h      |  76 +++--
 arch/x86/kernel/Makefile           |   8 +-
 arch/x86/kernel/module.c           |  11 +-
 arch/x86/kernel/setup.c            |   3 +
 arch/x86/kernel/unwind_frame.c     |  39 ++-
 arch/x86/kernel/unwind_guess.c     |   5 +
 arch/x86/kernel/unwind_orc.c       | 576 +++++++++++++++++++++++++++++++++++++
 arch/x86/kernel/vmlinux.lds.S      |   3 +
 include/asm-generic/vmlinux.lds.h  |  27 +-
 lib/Kconfig.debug                  |   3 +
 scripts/Makefile.build             |  14 +-
 18 files changed, 970 insertions(+), 64 deletions(-)
 create mode 100644 Documentation/x86/orc-unwinder.txt
 create mode 100644 arch/um/include/asm/unwind.h
 create mode 100644 arch/x86/include/asm/orc_lookup.h
 create mode 100644 arch/x86/kernel/unwind_orc.c

new file mode 100644
index 0000000..d9fadba
@@ -0,0 +1,178 @@
+ORC unwinder
+============
+
+Overview
+--------
+
+The kernel CONFIG_ORC_UNWINDER option enables the ORC unwinder, which is
+similar in concept to a DWARF unwinder.  The difference is that the
+format of the ORC data is much simpler than DWARF, which in turn allows
+the ORC unwinder to be much simpler and faster.
+
+The ORC data consists of unwind tables which are generated by objtool.
+They contain out-of-band data which is used by the in-kernel ORC
+unwinder.  Objtool generates the ORC data by first doing compile-time
+stack metadata validation (CONFIG_STACK_VALIDATION).  After analyzing
+all the code paths of a .o file, it determines information about the
+stack state at each instruction address in the file and outputs that
+information to the .orc_unwind and .orc_unwind_ip sections.
+
+The per-object ORC sections are combined at link time and are sorted and
+post-processed at boot time.  The unwinder uses the resulting data to
+correlate instruction addresses with their stack states at run time.
+
+
+ORC vs frame pointers
+---------------------
+
+With frame pointers enabled, GCC adds instrumentation code to every
+function in the kernel.  The kernel's .text size increases by about
+3.2%, resulting in a broad kernel-wide slowdown.  Measurements by Mel
+Gorman [1] have shown a slowdown of 5-10% for some workloads.
+
+In contrast, the ORC unwinder has no effect on text size or runtime
+performance, because the debuginfo is out of band.  So if you disable
+frame pointers and enable the ORC unwinder, you get a nice performance
+improvement across the board, and still have reliable stack traces.
+
+Ingo Molnar says:
+
+  "Note that it's not just a performance improvement, but also an
+  instruction cache locality improvement: 3.2% .text savings almost
+  directly transform into a similarly sized reduction in cache
+  footprint. That can transform to even higher speedups for workloads
+  whose cache locality is borderline."
+
+Another benefit of ORC compared to frame pointers is that it can
+reliably unwind across interrupts and exceptions.  Frame pointer based
+unwinds can sometimes skip the caller of the interrupted function, if it
+was a leaf function or if the interrupt hit before the frame pointer was
+saved.
+
+The main disadvantage of the ORC unwinder compared to frame pointers is
+that it needs more memory to store the ORC unwind tables: roughly 2-4MB
+depending on the kernel config.
+
+
+ORC vs DWARF
+------------
+
+ORC debuginfo's advantage over DWARF itself is that it's much simpler.
+It gets rid of the complex DWARF CFI state machine and also gets rid of
+the tracking of unnecessary registers.  This allows the unwinder to be
+much simpler, meaning fewer bugs, which is especially important for
+mission critical oops code.
+
+The simpler debuginfo format also enables the unwinder to be much faster
+than DWARF, which is important for perf and lockdep.  In a basic
+performance test by Jiri Slaby [2], the ORC unwinder was about 20x
+faster than an out-of-tree DWARF unwinder.  (Note: That measurement was
+taken before some performance tweaks were added, which doubled
+performance, so the speedup over DWARF may be closer to 40x.)
+
+The ORC data format does have a few downsides compared to DWARF.  The
+ORC unwind tables take up ~1MB more memory than DWARF eh_frame tables.
+
+Another potential downside is that, as GCC evolves, it's conceivable
+that the ORC data may end up being *too* simple to describe the state of
+the stack for certain optimizations.  But IMO this is unlikely because
+GCC saves the frame pointer for any unusual stack adjustments it does,
+so I suspect we'll really only ever need to keep track of the stack
+pointer and the frame pointer between call frames.  But even if we do
+end up having to track all the registers DWARF tracks, at least we will
+still be able to control the format, e.g. no complex state machines.
+
+
+ORC unwind table generation
+---------------------------
+
+The ORC data is generated by objtool.  With the existing compile-time
+stack metadata validation feature, objtool already follows all code
+paths, and so it already has all the information it needs to be able to
+generate ORC data from scratch.  So it's an easy step to go from stack
+validation to ORC data generation.
+
+It should be possible to instead generate the ORC data with a simple
+tool which converts DWARF to ORC data.  However, such a solution would
+be incomplete due to the kernel's extensive use of asm, inline asm, and
+special sections like exception tables.
+
+That could be rectified by manually annotating those special code paths
+using GNU assembler .cfi annotations in .S files, and homegrown
+annotations for inline asm in .c files.  But asm annotations were tried
+in the past and were found to be unmaintainable.  They were often
+incorrect/incomplete and made the code harder to read and keep updated.
+And based on looking at glibc code, annotating inline asm in .c files
+might be even worse.
+
+Objtool still needs a few annotations, but only in code which does
+unusual things to the stack like entry code.  And even then, far fewer
+annotations are needed than what DWARF would need, so they're much more
+maintainable than DWARF CFI annotations.
+
+So the advantages of using objtool to generate ORC data are that it
+gives more accurate debuginfo, with very few annotations.  It also
+insulates the kernel from toolchain bugs which can be very painful to
+deal with in the kernel since we often have to workaround issues in
+older versions of the toolchain for years.
+
+The downside is that the unwinder now becomes dependent on objtool's
+ability to reverse engineer GCC code flow.  If GCC optimizations become
+too complicated for objtool to follow, the ORC data generation might
+stop working or become incomplete.  (It's worth noting that livepatch
+already has such a dependency on objtool's ability to follow GCC code
+flow.)
+
+If newer versions of GCC come up with some optimizations which break
+objtool, we may need to revisit the current implementation.  Some
+possible solutions would be asking GCC to make the optimizations more
+palatable, or having objtool use DWARF as an additional input, or
+creating a GCC plugin to assist objtool with its analysis.  But for now,
+objtool follows GCC code quite well.
+
+
+Unwinder implementation details
+-------------------------------
+
+Objtool generates the ORC data by integrating with the compile-time
+stack metadata validation feature, which is described in detail in
+tools/objtool/Documentation/stack-validation.txt.  After analyzing all
+the code paths of a .o file, it creates an array of orc_entry structs,
+and a parallel array of instruction addresses associated with those
+structs, and writes them to the .orc_unwind and .orc_unwind_ip sections
+respectively.
+
+The ORC data is split into the two arrays for performance reasons, to
+make the searchable part of the data (.orc_unwind_ip) more compact.  The
+arrays are sorted in parallel at boot time.
+
+Performance is further improved by the use of a fast lookup table which
+is created at runtime.  The fast lookup table associates a given address
+with a range of indices for the .orc_unwind table, so that only a small
+subset of the table needs to be searched.
+
+
+Etymology
+---------
+
+Orcs, fearsome creatures of medieval folklore, are the Dwarves' natural
+enemies.  Similarly, the ORC unwinder was created in opposition to the
+complexity and slowness of DWARF.
+
+"Although Orcs rarely consider multiple solutions to a problem, they do
+excel at getting things done because they are creatures of action, not
+thought." [3]  Similarly, unlike the esoteric DWARF unwinder, the
+veracious ORC unwinder wastes no time or siloconic effort decoding
+variable-length zero-extended unsigned-integer byte-coded
+state-machine-based debug information entries.
+
+Similar to how Orcs frequently unravel the well-intentioned plans of
+their adversaries, the ORC unwinder frequently unravels stacks with
+brutal, unyielding efficiency.
+
+ORC stands for Oops Rewind Capability.
+
+
+[1] https://lkml.kernel.org/r/[email protected]
+[2] https://lkml.kernel.org/r/[email protected]
+[3] http://dustin.wikidot.com/half-orcs-and-orcs

new file mode 100644
index 0000000..7ffa543
@@ -0,0 +1,8 @@
+#ifndef _ASM_UML_UNWIND_H
+#define _ASM_UML_UNWIND_H
+
+static inline void
+unwind_module_init(struct module *mod, void *orc_ip, size_t orc_ip_size,
+		   void *orc, size_t orc_size) {}
+
+#endif /* _ASM_UML_UNWIND_H */

index e767ed2..0dac5a0 100644
@@ -153,6 +153,7 @@ config X86
 	select HAVE_MEMBLOCK
 	select HAVE_MEMBLOCK_NODE_MAP
 	select HAVE_MIXED_BREAKPOINTS_REGS
+	select HAVE_MOD_ARCH_SPECIFIC
 	select HAVE_NMI
 	select HAVE_OPROFILE
 	select HAVE_OPTPROBES

index 353ed09..dc10ec6 100644
@@ -355,4 +355,29 @@ config PUNIT_ATOM_DEBUG
 	  The current power state can be read from
 	  /sys/kernel/debug/punit_atom/dev_power_state
 
+config ORC_UNWINDER
+	bool "ORC unwinder"
+	depends on X86_64
+	select STACK_VALIDATION
+	---help---
+	  This option enables the ORC (Oops Rewind Capability) unwinder for
+	  unwinding kernel stack traces.  It uses a custom data format which is
+	  a simplified version of the DWARF Call Frame Information standard.
+
+	  This unwinder is more accurate across interrupt entry frames than the
+	  frame pointer unwinder.  It can also enable a 5-10% performance
+	  improvement across the entire kernel if CONFIG_FRAME_POINTER is
+	  disabled.
+
+	  Enabling this option will increase the kernel's runtime memory usage
+	  by roughly 2-4MB, depending on your kernel config.
+
+config FRAME_POINTER_UNWINDER
+	def_bool y
+	depends on !ORC_UNWINDER && FRAME_POINTER
+
+config GUESS_UNWINDER
+	def_bool y
+	depends on !ORC_UNWINDER && !FRAME_POINTER
+
 endmenu

index e3b7819..9eb7c71 100644
@@ -2,6 +2,15 @@
 #define _ASM_X86_MODULE_H
 
 #include <asm-generic/module.h>
+#include <asm/orc_types.h>
+
+struct mod_arch_specific {
+#ifdef CONFIG_ORC_UNWINDER
+	unsigned int num_orcs;
+	int *orc_unwind_ip;
+	struct orc_entry *orc_unwind;
+#endif
+};
 
 #ifdef CONFIG_X86_64
 /* X86_64 does not define MODULE_PROC_FAMILY */

index 7dc777a..9c9dc57 100644
@@ -88,7 +88,7 @@ struct orc_entry {
 	unsigned	sp_reg:4;
 	unsigned	bp_reg:4;
 	unsigned	type:2;
-};
+} __packed;
 
 /*
  * This struct is used by asm and inline asm code to manually annotate the

index a01892b..287eac7 100644
@@ -126,11 +126,9 @@ obj-$(CONFIG_PERF_EVENTS)		+= perf_regs.o
 obj-$(CONFIG_TRACING)			+= tracepoint.o
 obj-$(CONFIG_SCHED_MC_PRIO)		+= itmt.o
 
-ifdef CONFIG_FRAME_POINTER
-obj-y					+= unwind_frame.o
-else
-obj-y					+= unwind_guess.o
-endif
+obj-$(CONFIG_ORC_UNWINDER)		+= unwind_orc.o
+obj-$(CONFIG_FRAME_POINTER_UNWINDER)	+= unwind_frame.o
+obj-$(CONFIG_GUESS_UNWINDER)		+= unwind_guess.o
 
 ###
 # 64 bit specific files

index f67bd32..62e7d70 100644
@@ -35,6 +35,7 @@
 #include <asm/page.h>
 #include <asm/pgtable.h>
 #include <asm/setup.h>
+#include <asm/unwind.h>
 
 #if 0
 #define DEBUGP(fmt, ...)				\

@@ -213,7 +214,7 @@ int module_finalize(const Elf_Ehdr *hdr,
 		    struct module *me)
 {
 	const Elf_Shdr *s, *text = NULL, *alt = NULL, *locks = NULL,
-		*para = NULL;
+		*para = NULL, *orc = NULL, *orc_ip = NULL;
 	char *secstrings = (void *)hdr + sechdrs[hdr->e_shstrndx].sh_offset;
 
 	for (s = sechdrs; s < sechdrs + hdr->e_shnum; s++) {

@@ -225,6 +226,10 @@ int module_finalize(const Elf_Ehdr *hdr,
 			locks = s;
 		if (!strcmp(".parainstructions", secstrings + s->sh_name))
 			para = s;
+		if (!strcmp(".orc_unwind", secstrings + s->sh_name))
+			orc = s;
+		if (!strcmp(".orc_unwind_ip", secstrings + s->sh_name))
+			orc_ip = s;
 	}
 
 	if (alt) {

@@ -248,6 +253,10 @@ int module_finalize(const Elf_Ehdr *hdr,
 	/* make jump label nops */
 	jump_label_apply_nops(me);
 
+	if (orc && orc_ip)
+		unwind_module_init(me, (void *)orc_ip->sh_addr, orc_ip->sh_size,
+				   (void *)orc->sh_addr, orc->sh_size);
+
 	return 0;
 }
 

index 3486d04..ecab322 100644
@@ -115,6 +115,7 @@
 #include <asm/microcode.h>
 #include <asm/mmu_context.h>
 #include <asm/kaslr.h>
+#include <asm/unwind.h>
 
 /*
  * max_low_pfn_mapped: highest direct mapped pfn under 4GB

@@ -1310,6 +1311,8 @@ void __init setup_arch(char **cmdline_p)
 	if (efi_enabled(EFI_BOOT))
 		efi_apply_memmap_quirks();
 #endif
+
+	unwind_init();
 }
 
 #ifdef CONFIG_X86_32

index b9389d7..7574ef5 100644
@@ -10,20 +10,22 @@
 
 #define FRAME_HEADER_SIZE (sizeof(long) * 2)
 
-/*
- * This disables KASAN checking when reading a value from another task's stack,
- * since the other task could be running on another CPU and could have poisoned
- * the stack in the meantime.
- */
-#define READ_ONCE_TASK_STACK(task, x)			\
-({							\
-	unsigned long val;				\
-	if (task == current)				\
-		val = READ_ONCE(x);			\
-	else						\
-		val = READ_ONCE_NOCHECK(x);		\
-	val;						\
-})
+unsigned long unwind_get_return_address(struct unwind_state *state)
+{
+	if (unwind_done(state))
+		return 0;
+
+	return __kernel_text_address(state->ip) ? state->ip : 0;
+}
+EXPORT_SYMBOL_GPL(unwind_get_return_address);
+
+unsigned long *unwind_get_return_address_ptr(struct unwind_state *state)
+{
+	if (unwind_done(state))
+		return NULL;
+
+	return state->regs ? &state->regs->ip : state->bp + 1;
+}
 
 static void unwind_dump(struct unwind_state *state)
 {

@@ -66,15 +68,6 @@ static void unwind_dump(struct unwind_state *state)
 	}
 }
 
-unsigned long unwind_get_return_address(struct unwind_state *state)
-{
-	if (unwind_done(state))
-		return 0;
-
-	return __kernel_text_address(state->ip) ? state->ip : 0;
-}
-EXPORT_SYMBOL_GPL(unwind_get_return_address);
-
 static size_t regs_size(struct pt_regs *regs)
 {
 	/* x86_32 regs from kernel mode are two words shorter: */

index 039f367..4f0e17b 100644
@@ -19,6 +19,11 @@ unsigned long unwind_get_return_address(struct unwind_state *state)
 }
 EXPORT_SYMBOL_GPL(unwind_get_return_address);
 
+unsigned long *unwind_get_return_address_ptr(struct unwind_state *state)
+{
+	return NULL;
+}
+
 bool unwind_next_frame(struct unwind_state *state)
 {
 	struct stack_info *info = &state->stack_info;

index c8a3b61..f05f00a 100644
@@ -24,6 +24,7 @@
 #include <asm/asm-offsets.h>
 #include <asm/thread_info.h>
 #include <asm/page_types.h>
+#include <asm/orc_lookup.h>
 #include <asm/cache.h>
 #include <asm/boot.h>
 

@@ -148,6 +149,8 @@ SECTIONS
 
 	BUG_TABLE
 
+	ORC_UNWIND_TABLE
+
 	. = ALIGN(PAGE_SIZE);
 	__vvar_page = .;
 

index 0d64658..e98b052 100644
@@ -668,6 +668,31 @@
 #define BUG_TABLE
 #endif
 
+#ifdef CONFIG_ORC_UNWINDER
+#define ORC_UNWIND_TABLE						\
+	. = ALIGN(4);							\
+	.orc_unwind_ip : AT(ADDR(.orc_unwind_ip) - LOAD_OFFSET) {	\
+		VMLINUX_SYMBOL(__start_orc_unwind_ip) = .;		\
+		KEEP(*(.orc_unwind_ip))					\
+		VMLINUX_SYMBOL(__stop_orc_unwind_ip) = .;		\
+	}								\
+	. = ALIGN(6);							\
+	.orc_unwind : AT(ADDR(.orc_unwind) - LOAD_OFFSET) {		\
+		VMLINUX_SYMBOL(__start_orc_unwind) = .;			\
+		KEEP(*(.orc_unwind))					\
+		VMLINUX_SYMBOL(__stop_orc_unwind) = .;			\
+	}								\
+	. = ALIGN(4);							\
+	.orc_lookup : AT(ADDR(.orc_lookup) - LOAD_OFFSET) {		\
+		VMLINUX_SYMBOL(orc_lookup) = .;				\
+		. += (((SIZEOF(.text) + LOOKUP_BLOCK_SIZE - 1) /	\
+			LOOKUP_BLOCK_SIZE) + 1) * 4;			\
+		VMLINUX_SYMBOL(orc_lookup_end) = .;			\
+	}
+#else
+#define ORC_UNWIND_TABLE
+#endif
+
 #ifdef CONFIG_PM_TRACE
 #define TRACEDATA							\
 	. = ALIGN(4);							\

@@ -854,7 +879,7 @@
 		DATA_DATA						\
 		CONSTRUCTORS						\
 	}								\
-	BUG_TABLE
+	BUG_TABLE							\
 
 #define INIT_TEXT_SECTION(inittext_align)				\
 	. = ALIGN(inittext_align);					\

index 9c5d40a..a7abffa 100644
@@ -374,6 +374,9 @@ config STACK_VALIDATION
 	  pointers (if CONFIG_FRAME_POINTER is enabled).  This helps ensure
 	  that runtime stack traces are more reliable.
 
+	  This is also a prerequisite for generation of ORC unwind data, which
+	  is needed for CONFIG_ORC_UNWINDER.
+
 	  For more information, see
 	  tools/objtool/Documentation/stack-validation.txt.
 

index 733e044..11b5c28 100644
@@ -258,7 +258,8 @@ ifneq ($(SKIP_STACK_VALIDATION),1)
 
 __objtool_obj := $(objtree)/tools/objtool/objtool
 
-objtool_args = check
+objtool_args = $(if $(CONFIG_ORC_UNWINDER),orc generate,check)
+
 ifndef CONFIG_FRAME_POINTER
 objtool_args += --no-fp
 endif

@@ -276,6 +277,11 @@ objtool_obj = $(if $(patsubst y%,, \
 endif # SKIP_STACK_VALIDATION
 endif # CONFIG_STACK_VALIDATION
 
+# Rebuild all objects when objtool changes, or is enabled/disabled.
+objtool_dep = $(objtool_obj)					\
+	      $(wildcard include/config/orc/unwinder.h		\
+			 include/config/stack/validation.h)
+
 define rule_cc_o_c
 	$(call echo-cmd,checksrc) $(cmd_checksrc)			  \
 	$(call cmd_and_fixdep,cc_o_c)					  \

@@ -298,13 +304,13 @@ cmd_undef_syms = echo
 endif
 
 # Built-in and composite module parts
-$(obj)/%.o: $(src)/%.c $(recordmcount_source) $(objtool_obj) FORCE
+$(obj)/%.o: $(src)/%.c $(recordmcount_source) $(objtool_dep) FORCE
 	$(call cmd,force_checksrc)
 	$(call if_changed_rule,cc_o_c)
 
 # Single-part modules are special since we need to mark them in $(MODVERDIR)
 
-$(single-used-m): $(obj)/%.o: $(src)/%.c $(recordmcount_source) $(objtool_obj) FORCE
+$(single-used-m): $(obj)/%.o: $(src)/%.c $(recordmcount_source) $(objtool_dep) FORCE
 	$(call cmd,force_checksrc)
 	$(call if_changed_rule,cc_o_c)
 	@{ echo $(@:.o=.ko); echo $@; \

@@ -399,7 +405,7 @@ cmd_modversions_S =								\
 endif
 endif
 
-$(obj)/%.o: $(src)/%.S $(objtool_obj) FORCE
+$(obj)/%.o: $(src)/%.S $(objtool_dep) FORCE
 	$(call if_changed_rule,as_o_S)
 
 targets += $(real-objs-y) $(real-objs-m) $(lib-y)

2.7.5

Add a new ORC unwinder which is enabled by CONFIG_ORC_UNWINDER. It plugs into the existing x86 unwinder framework.

It relies on objtool to generate the needed .orc_unwind and .orc_unwind_ip sections.

For more details on why ORC is used instead of DWARF, see Documentation/x86/orc-unwinder.txt.

Thanks to Andy Lutomirski for the performance improvement ideas:
splitting the ORC unwind table into two parallel arrays and creating a fast lookup table to search a subset of the unwind table.

---
Slightly tweaked documentation wording, as recommended by Ingo:

"ORC unwind tables take up ~50% more RAM (+1.3MB on an x86 defconfig kernel)
than DWARF-based eh_frame tables."

 Documentation/x86/orc-unwinder.txt | 179 ++++++++++++
 arch/um/include/asm/unwind.h       |   8 +
 arch/x86/Kconfig                   |   1 +
 arch/x86/Kconfig.debug             |  25 ++
 arch/x86/include/asm/module.h      |   9 +
 arch/x86/include/asm/orc_lookup.h  |  46 +++
 arch/x86/include/asm/orc_types.h   |   2 +-
 arch/x86/include/asm/unwind.h      |  76 +++--
 arch/x86/kernel/Makefile           |   8 +-
 arch/x86/kernel/module.c           |  11 +-
 arch/x86/kernel/setup.c            |   3 +
 arch/x86/kernel/unwind_frame.c     |  39 ++-
 arch/x86/kernel/unwind_guess.c     |   5 +
 arch/x86/kernel/unwind_orc.c       | 576 +++++++++++++++++++++++++++++++++++++
 arch/x86/kernel/vmlinux.lds.S      |   3 +
 include/asm-generic/vmlinux.lds.h  |  27 +-
 lib/Kconfig.debug                  |   3 +
 scripts/Makefile.build             |  14 +-
 18 files changed, 971 insertions(+), 64 deletions(-)
 create mode 100644 Documentation/x86/orc-unwinder.txt
 create mode 100644 arch/um/include/asm/unwind.h
 create mode 100644 arch/x86/include/asm/orc_lookup.h
 create mode 100644 arch/x86/kernel/unwind_orc.c

new file mode 100644
index 0000000..af0c9a4
@@ -0,0 +1,179 @@
+ORC unwinder
+============
+
+Overview
+--------
+
+The kernel CONFIG_ORC_UNWINDER option enables the ORC unwinder, which is
+similar in concept to a DWARF unwinder.  The difference is that the
+format of the ORC data is much simpler than DWARF, which in turn allows
+the ORC unwinder to be much simpler and faster.
+
+The ORC data consists of unwind tables which are generated by objtool.
+They contain out-of-band data which is used by the in-kernel ORC
+unwinder.  Objtool generates the ORC data by first doing compile-time
+stack metadata validation (CONFIG_STACK_VALIDATION).  After analyzing
+all the code paths of a .o file, it determines information about the
+stack state at each instruction address in the file and outputs that
+information to the .orc_unwind and .orc_unwind_ip sections.
+
+The per-object ORC sections are combined at link time and are sorted and
+post-processed at boot time.  The unwinder uses the resulting data to
+correlate instruction addresses with their stack states at run time.
+
+
+ORC vs frame pointers
+---------------------
+
+With frame pointers enabled, GCC adds instrumentation code to every
+function in the kernel.  The kernel's .text size increases by about
+3.2%, resulting in a broad kernel-wide slowdown.  Measurements by Mel
+Gorman [1] have shown a slowdown of 5-10% for some workloads.
+
+In contrast, the ORC unwinder has no effect on text size or runtime
+performance, because the debuginfo is out of band.  So if you disable
+frame pointers and enable the ORC unwinder, you get a nice performance
+improvement across the board, and still have reliable stack traces.
+
+Ingo Molnar says:
+
+  "Note that it's not just a performance improvement, but also an
+  instruction cache locality improvement: 3.2% .text savings almost
+  directly transform into a similarly sized reduction in cache
+  footprint. That can transform to even higher speedups for workloads
+  whose cache locality is borderline."
+
+Another benefit of ORC compared to frame pointers is that it can
+reliably unwind across interrupts and exceptions.  Frame pointer based
+unwinds can sometimes skip the caller of the interrupted function, if it
+was a leaf function or if the interrupt hit before the frame pointer was
+saved.
+
+The main disadvantage of the ORC unwinder compared to frame pointers is
+that it needs more memory to store the ORC unwind tables: roughly 2-4MB
+depending on the kernel config.
+
+
+ORC vs DWARF
+------------
+
+ORC debuginfo's advantage over DWARF itself is that it's much simpler.
+It gets rid of the complex DWARF CFI state machine and also gets rid of
+the tracking of unnecessary registers.  This allows the unwinder to be
+much simpler, meaning fewer bugs, which is especially important for
+mission critical oops code.
+
+The simpler debuginfo format also enables the unwinder to be much faster
+than DWARF, which is important for perf and lockdep.  In a basic
+performance test by Jiri Slaby [2], the ORC unwinder was about 20x
+faster than an out-of-tree DWARF unwinder.  (Note: That measurement was
+taken before some performance tweaks were added, which doubled
+performance, so the speedup over DWARF may be closer to 40x.)
+
+The ORC data format does have a few downsides compared to DWARF.  ORC
+unwind tables take up ~50% more RAM (+1.3MB on an x86 defconfig kernel)
+than DWARF-based eh_frame tables.
+
+Another potential downside is that, as GCC evolves, it's conceivable
+that the ORC data may end up being *too* simple to describe the state of
+the stack for certain optimizations.  But IMO this is unlikely because
+GCC saves the frame pointer for any unusual stack adjustments it does,
+so I suspect we'll really only ever need to keep track of the stack
+pointer and the frame pointer between call frames.  But even if we do
+end up having to track all the registers DWARF tracks, at least we will
+still be able to control the format, e.g. no complex state machines.
+
+
+ORC unwind table generation
+---------------------------
+
+The ORC data is generated by objtool.  With the existing compile-time
+stack metadata validation feature, objtool already follows all code
+paths, and so it already has all the information it needs to be able to
+generate ORC data from scratch.  So it's an easy step to go from stack
+validation to ORC data generation.
+
+It should be possible to instead generate the ORC data with a simple
+tool which converts DWARF to ORC data.  However, such a solution would
+be incomplete due to the kernel's extensive use of asm, inline asm, and
+special sections like exception tables.
+
+That could be rectified by manually annotating those special code paths
+using GNU assembler .cfi annotations in .S files, and homegrown
+annotations for inline asm in .c files.  But asm annotations were tried
+in the past and were found to be unmaintainable.  They were often
+incorrect/incomplete and made the code harder to read and keep updated.
+And based on looking at glibc code, annotating inline asm in .c files
+might be even worse.
+
+Objtool still needs a few annotations, but only in code which does
+unusual things to the stack like entry code.  And even then, far fewer
+annotations are needed than what DWARF would need, so they're much more
+maintainable than DWARF CFI annotations.
+
+So the advantages of using objtool to generate ORC data are that it
+gives more accurate debuginfo, with very few annotations.  It also
+insulates the kernel from toolchain bugs which can be very painful to
+deal with in the kernel since we often have to workaround issues in
+older versions of the toolchain for years.
+
+The downside is that the unwinder now becomes dependent on objtool's
+ability to reverse engineer GCC code flow.  If GCC optimizations become
+too complicated for objtool to follow, the ORC data generation might
+stop working or become incomplete.  (It's worth noting that livepatch
+already has such a dependency on objtool's ability to follow GCC code
+flow.)
+
+If newer versions of GCC come up with some optimizations which break
+objtool, we may need to revisit the current implementation.  Some
+possible solutions would be asking GCC to make the optimizations more
+palatable, or having objtool use DWARF as an additional input, or
+creating a GCC plugin to assist objtool with its analysis.  But for now,
+objtool follows GCC code quite well.
+
+
+Unwinder implementation details
+-------------------------------
+
+Objtool generates the ORC data by integrating with the compile-time
+stack metadata validation feature, which is described in detail in
+tools/objtool/Documentation/stack-validation.txt.  After analyzing all
+the code paths of a .o file, it creates an array of orc_entry structs,
+and a parallel array of instruction addresses associated with those
+structs, and writes them to the .orc_unwind and .orc_unwind_ip sections
+respectively.
+
+The ORC data is split into the two arrays for performance reasons, to
+make the searchable part of the data (.orc_unwind_ip) more compact.  The
+arrays are sorted in parallel at boot time.
+
+Performance is further improved by the use of a fast lookup table which
+is created at runtime.  The fast lookup table associates a given address
+with a range of indices for the .orc_unwind table, so that only a small
+subset of the table needs to be searched.
+
+
+Etymology
+---------
+
+Orcs, fearsome creatures of medieval folklore, are the Dwarves' natural
+enemies.  Similarly, the ORC unwinder was created in opposition to the
+complexity and slowness of DWARF.
+
+"Although Orcs rarely consider multiple solutions to a problem, they do
+excel at getting things done because they are creatures of action, not
+thought." [3]  Similarly, unlike the esoteric DWARF unwinder, the
+veracious ORC unwinder wastes no time or siloconic effort decoding
+variable-length zero-extended unsigned-integer byte-coded
+state-machine-based debug information entries.
+
+Similar to how Orcs frequently unravel the well-intentioned plans of
+their adversaries, the ORC unwinder frequently unravels stacks with
+brutal, unyielding efficiency.
+
+ORC stands for Oops Rewind Capability.
+
+
+[1] https://lkml.kernel.org/r/[email protected]
+[2] https://lkml.kernel.org/r/[email protected]
+[3] http://dustin.wikidot.com/half-orcs-and-orcs

new file mode 100644
index 0000000..7ffa543
@@ -0,0 +1,8 @@
+#ifndef _ASM_UML_UNWIND_H
+#define _ASM_UML_UNWIND_H
+
+static inline void
+unwind_module_init(struct module *mod, void *orc_ip, size_t orc_ip_size,
+		   void *orc, size_t orc_size) {}
+
+#endif /* _ASM_UML_UNWIND_H */

index e767ed2..0dac5a0 100644
@@ -153,6 +153,7 @@ config X86
 	select HAVE_MEMBLOCK
 	select HAVE_MEMBLOCK_NODE_MAP
 	select HAVE_MIXED_BREAKPOINTS_REGS
+	select HAVE_MOD_ARCH_SPECIFIC
 	select HAVE_NMI
 	select HAVE_OPROFILE
 	select HAVE_OPTPROBES

index 353ed09..dc10ec6 100644
@@ -355,4 +355,29 @@ config PUNIT_ATOM_DEBUG
 	  The current power state can be read from
 	  /sys/kernel/debug/punit_atom/dev_power_state
 
+config ORC_UNWINDER
+	bool "ORC unwinder"
+	depends on X86_64
+	select STACK_VALIDATION
+	---help---
+	  This option enables the ORC (Oops Rewind Capability) unwinder for
+	  unwinding kernel stack traces.  It uses a custom data format which is
+	  a simplified version of the DWARF Call Frame Information standard.
+
+	  This unwinder is more accurate across interrupt entry frames than the
+	  frame pointer unwinder.  It can also enable a 5-10% performance
+	  improvement across the entire kernel if CONFIG_FRAME_POINTER is
+	  disabled.
+
+	  Enabling this option will increase the kernel's runtime memory usage
+	  by roughly 2-4MB, depending on your kernel config.
+
+config FRAME_POINTER_UNWINDER
+	def_bool y
+	depends on !ORC_UNWINDER && FRAME_POINTER
+
+config GUESS_UNWINDER
+	def_bool y
+	depends on !ORC_UNWINDER && !FRAME_POINTER
+
 endmenu

index e3b7819..9eb7c71 100644
@@ -2,6 +2,15 @@
 #define _ASM_X86_MODULE_H
 
 #include <asm-generic/module.h>
+#include <asm/orc_types.h>
+
+struct mod_arch_specific {
+#ifdef CONFIG_ORC_UNWINDER
+	unsigned int num_orcs;
+	int *orc_unwind_ip;
+	struct orc_entry *orc_unwind;
+#endif
+};
 
 #ifdef CONFIG_X86_64
 /* X86_64 does not define MODULE_PROC_FAMILY */

index 7dc777a..9c9dc57 100644
@@ -88,7 +88,7 @@ struct orc_entry {
 	unsigned	sp_reg:4;
 	unsigned	bp_reg:4;
 	unsigned	type:2;
-};
+} __packed;
 
 /*
  * This struct is used by asm and inline asm code to manually annotate the

index a01892b..287eac7 100644
@@ -126,11 +126,9 @@ obj-$(CONFIG_PERF_EVENTS)		+= perf_regs.o
 obj-$(CONFIG_TRACING)			+= tracepoint.o
 obj-$(CONFIG_SCHED_MC_PRIO)		+= itmt.o
 
-ifdef CONFIG_FRAME_POINTER
-obj-y					+= unwind_frame.o
-else
-obj-y					+= unwind_guess.o
-endif
+obj-$(CONFIG_ORC_UNWINDER)		+= unwind_orc.o
+obj-$(CONFIG_FRAME_POINTER_UNWINDER)	+= unwind_frame.o
+obj-$(CONFIG_GUESS_UNWINDER)		+= unwind_guess.o
 
 ###
 # 64 bit specific files

index f67bd32..62e7d70 100644
@@ -35,6 +35,7 @@
 #include <asm/page.h>
 #include <asm/pgtable.h>
 #include <asm/setup.h>
+#include <asm/unwind.h>
 
 #if 0
 #define DEBUGP(fmt, ...)				\

@@ -213,7 +214,7 @@ int module_finalize(const Elf_Ehdr *hdr,
 		    struct module *me)
 {
 	const Elf_Shdr *s, *text = NULL, *alt = NULL, *locks = NULL,
-		*para = NULL;
+		*para = NULL, *orc = NULL, *orc_ip = NULL;
 	char *secstrings = (void *)hdr + sechdrs[hdr->e_shstrndx].sh_offset;
 
 	for (s = sechdrs; s < sechdrs + hdr->e_shnum; s++) {

@@ -225,6 +226,10 @@ int module_finalize(const Elf_Ehdr *hdr,
 			locks = s;
 		if (!strcmp(".parainstructions", secstrings + s->sh_name))
 			para = s;
+		if (!strcmp(".orc_unwind", secstrings + s->sh_name))
+			orc = s;
+		if (!strcmp(".orc_unwind_ip", secstrings + s->sh_name))
+			orc_ip = s;
 	}
 
 	if (alt) {

@@ -248,6 +253,10 @@ int module_finalize(const Elf_Ehdr *hdr,
 	/* make jump label nops */
 	jump_label_apply_nops(me);
 
+	if (orc && orc_ip)
+		unwind_module_init(me, (void *)orc_ip->sh_addr, orc_ip->sh_size,
+				   (void *)orc->sh_addr, orc->sh_size);
+
 	return 0;
 }
 

index 3486d04..ecab322 100644
@@ -115,6 +115,7 @@
 #include <asm/microcode.h>
 #include <asm/mmu_context.h>
 #include <asm/kaslr.h>
+#include <asm/unwind.h>
 
 /*
  * max_low_pfn_mapped: highest direct mapped pfn under 4GB

@@ -1310,6 +1311,8 @@ void __init setup_arch(char **cmdline_p)
 	if (efi_enabled(EFI_BOOT))
 		efi_apply_memmap_quirks();
 #endif
+
+	unwind_init();
 }
 
 #ifdef CONFIG_X86_32

index b9389d7..7574ef5 100644
@@ -10,20 +10,22 @@
 
 #define FRAME_HEADER_SIZE (sizeof(long) * 2)
 
-/*
- * This disables KASAN checking when reading a value from another task's stack,
- * since the other task could be running on another CPU and could have poisoned
- * the stack in the meantime.
- */
-#define READ_ONCE_TASK_STACK(task, x)			\
-({							\
-	unsigned long val;				\
-	if (task == current)				\
-		val = READ_ONCE(x);			\
-	else						\
-		val = READ_ONCE_NOCHECK(x);		\
-	val;						\
-})
+unsigned long unwind_get_return_address(struct unwind_state *state)
+{
+	if (unwind_done(state))
+		return 0;
+
+	return __kernel_text_address(state->ip) ? state->ip : 0;
+}
+EXPORT_SYMBOL_GPL(unwind_get_return_address);
+
+unsigned long *unwind_get_return_address_ptr(struct unwind_state *state)
+{
+	if (unwind_done(state))
+		return NULL;
+
+	return state->regs ? &state->regs->ip : state->bp + 1;
+}
 
 static void unwind_dump(struct unwind_state *state)
 {

@@ -66,15 +68,6 @@ static void unwind_dump(struct unwind_state *state)
 	}
 }
 
-unsigned long unwind_get_return_address(struct unwind_state *state)
-{
-	if (unwind_done(state))
-		return 0;
-
-	return __kernel_text_address(state->ip) ? state->ip : 0;
-}
-EXPORT_SYMBOL_GPL(unwind_get_return_address);
-
 static size_t regs_size(struct pt_regs *regs)
 {
 	/* x86_32 regs from kernel mode are two words shorter: */

index 039f367..4f0e17b 100644
@@ -19,6 +19,11 @@ unsigned long unwind_get_return_address(struct unwind_state *state)
 }
 EXPORT_SYMBOL_GPL(unwind_get_return_address);
 
+unsigned long *unwind_get_return_address_ptr(struct unwind_state *state)
+{
+	return NULL;
+}
+
 bool unwind_next_frame(struct unwind_state *state)
 {
 	struct stack_info *info = &state->stack_info;

index c8a3b61..f05f00a 100644
@@ -24,6 +24,7 @@
 #include <asm/asm-offsets.h>
 #include <asm/thread_info.h>
 #include <asm/page_types.h>
+#include <asm/orc_lookup.h>
 #include <asm/cache.h>
 #include <asm/boot.h>
 

@@ -148,6 +149,8 @@ SECTIONS
 
 	BUG_TABLE
 
+	ORC_UNWIND_TABLE
+
 	. = ALIGN(PAGE_SIZE);
 	__vvar_page = .;
 

index 0d64658..e98b052 100644
@@ -668,6 +668,31 @@
 #define BUG_TABLE
 #endif
 
+#ifdef CONFIG_ORC_UNWINDER
+#define ORC_UNWIND_TABLE						\
+	. = ALIGN(4);							\
+	.orc_unwind_ip : AT(ADDR(.orc_unwind_ip) - LOAD_OFFSET) {	\
+		VMLINUX_SYMBOL(__start_orc_unwind_ip) = .;		\
+		KEEP(*(.orc_unwind_ip))					\
+		VMLINUX_SYMBOL(__stop_orc_unwind_ip) = .;		\
+	}								\
+	. = ALIGN(6);							\
+	.orc_unwind : AT(ADDR(.orc_unwind) - LOAD_OFFSET) {		\
+		VMLINUX_SYMBOL(__start_orc_unwind) = .;			\
+		KEEP(*(.orc_unwind))					\
+		VMLINUX_SYMBOL(__stop_orc_unwind) = .;			\
+	}								\
+	. = ALIGN(4);							\
+	.orc_lookup : AT(ADDR(.orc_lookup) - LOAD_OFFSET) {		\
+		VMLINUX_SYMBOL(orc_lookup) = .;				\
+		. += (((SIZEOF(.text) + LOOKUP_BLOCK_SIZE - 1) /	\
+			LOOKUP_BLOCK_SIZE) + 1) * 4;			\
+		VMLINUX_SYMBOL(orc_lookup_end) = .;			\
+	}
+#else
+#define ORC_UNWIND_TABLE
+#endif
+
 #ifdef CONFIG_PM_TRACE
 #define TRACEDATA							\
 	. = ALIGN(4);							\

@@ -854,7 +879,7 @@
 		DATA_DATA						\
 		CONSTRUCTORS						\
 	}								\
-	BUG_TABLE
+	BUG_TABLE							\
 
 #define INIT_TEXT_SECTION(inittext_align)				\
 	. = ALIGN(inittext_align);					\

index 9c5d40a..a7abffa 100644
@@ -374,6 +374,9 @@ config STACK_VALIDATION
 	  pointers (if CONFIG_FRAME_POINTER is enabled).  This helps ensure
 	  that runtime stack traces are more reliable.
 
+	  This is also a prerequisite for generation of ORC unwind data, which
+	  is needed for CONFIG_ORC_UNWINDER.
+
 	  For more information, see
 	  tools/objtool/Documentation/stack-validation.txt.
 

index 733e044..11b5c28 100644
@@ -258,7 +258,8 @@ ifneq ($(SKIP_STACK_VALIDATION),1)
 
 __objtool_obj := $(objtree)/tools/objtool/objtool
 
-objtool_args = check
+objtool_args = $(if $(CONFIG_ORC_UNWINDER),orc generate,check)
+
 ifndef CONFIG_FRAME_POINTER
 objtool_args += --no-fp
 endif

@@ -276,6 +277,11 @@ objtool_obj = $(if $(patsubst y%,, \
 endif # SKIP_STACK_VALIDATION
 endif # CONFIG_STACK_VALIDATION
 
+# Rebuild all objects when objtool changes, or is enabled/disabled.
+objtool_dep = $(objtool_obj)					\
+	      $(wildcard include/config/orc/unwinder.h		\
+			 include/config/stack/validation.h)
+
 define rule_cc_o_c
 	$(call echo-cmd,checksrc) $(cmd_checksrc)			  \
 	$(call cmd_and_fixdep,cc_o_c)					  \

@@ -298,13 +304,13 @@ cmd_undef_syms = echo
 endif
 
 # Built-in and composite module parts
-$(obj)/%.o: $(src)/%.c $(recordmcount_source) $(objtool_obj) FORCE
+$(obj)/%.o: $(src)/%.c $(recordmcount_source) $(objtool_dep) FORCE
 	$(call cmd,force_checksrc)
 	$(call if_changed_rule,cc_o_c)
 
 # Single-part modules are special since we need to mark them in $(MODVERDIR)
 
-$(single-used-m): $(obj)/%.o: $(src)/%.c $(recordmcount_source) $(objtool_obj) FORCE
+$(single-used-m): $(obj)/%.o: $(src)/%.c $(recordmcount_source) $(objtool_dep) FORCE
 	$(call cmd,force_checksrc)
 	$(call if_changed_rule,cc_o_c)
 	@{ echo $(@:.o=.ko); echo $@; \

@@ -399,7 +405,7 @@ cmd_modversions_S =								\
 endif
 endif
 
-$(obj)/%.o: $(src)/%.S $(objtool_obj) FORCE
+$(obj)/%.o: $(src)/%.S $(objtool_dep) FORCE
 	$(call if_changed_rule,as_o_S)
 
 targets += $(real-objs-y) $(real-objs-m) $(lib-y)

2.7.5

Yeah, maybe so. Since the task_on_another_cpu() check above is racy, here it's remotely possible that the task has since starting executing and has poisoned the stack memory we're about to read.

I don't know how realistic that scenario is, but it wouldn't hurt to add a couple of READ_ONCE_NOCHECKs here for the 'frame' dereferences.

Josh

A couple of Kconfig changes which make it much easier to switch to the new CONFIG_ORC_UNWINDER:

1) Remove x86 dependencies on CONFIG_FRAME_POINTER for lockdep, latencytop, and fault injection. x86 has a 'guess' unwinder which just scans the stack for kernel text addresses. It's not 100% accurate but in many cases it's good enough. This allows those users who don't want the text overhead of the frame pointer or ORC unwinders to still use these features. More importantly, this also makes it much more straightforward to disable frame pointers.

2) Make CONFIG_ORC_UNWINDER depend on !CONFIG_FRAME_POINTER. While it would be possible to have both enabled, it doesn't really make sense to do so. So enforce a sane configuration to prevent the user from making a dumb mistake.

With these changes, when you disable CONFIG_FRAME_POINTER, "make oldconfig" will ask if you want to enable CONFIG_ORC_UNWINDER.

---
 arch/x86/Kconfig.debug | 7 +++----
 lib/Kconfig.debug      | 6 +++---
 2 files changed, 6 insertions(+), 7 deletions(-)

index dc10ec6..268a318 100644
@@ -357,7 +357,7 @@ config PUNIT_ATOM_DEBUG
 
 config ORC_UNWINDER
 	bool "ORC unwinder"
-	depends on X86_64
+	depends on X86_64 && !FRAME_POINTER
 	select STACK_VALIDATION
 	---help---
 	  This option enables the ORC (Oops Rewind Capability) unwinder for

@@ -365,9 +365,8 @@ config ORC_UNWINDER
 	  a simplified version of the DWARF Call Frame Information standard.
 
 	  This unwinder is more accurate across interrupt entry frames than the
-	  frame pointer unwinder.  It can also enable a 5-10% performance
-	  improvement across the entire kernel if CONFIG_FRAME_POINTER is
-	  disabled.
+	  frame pointer unwinder.  It also enables a 5-10% performance
+	  improvement across the entire kernel compared to frame pointers.
 
 	  Enabling this option will increase the kernel's runtime memory usage
 	  by roughly 2-4MB, depending on your kernel config.

index a7abffa..325c1c5 100644
@@ -1113,7 +1113,7 @@ config LOCKDEP
 	bool
 	depends on DEBUG_KERNEL && TRACE_IRQFLAGS_SUPPORT && STACKTRACE_SUPPORT && LOCKDEP_SUPPORT
 	select STACKTRACE
-	select FRAME_POINTER if !MIPS && !PPC && !ARM_UNWIND && !S390 && !MICROBLAZE && !ARC && !SCORE
+	select FRAME_POINTER if !MIPS && !PPC && !ARM_UNWIND && !S390 && !MICROBLAZE && !ARC && !SCORE && !X86
 	select KALLSYMS
 	select KALLSYMS_ALL
 

@@ -1504,7 +1504,7 @@ config FAULT_INJECTION_STACKTRACE_FILTER
 	depends on FAULT_INJECTION_DEBUG_FS && STACKTRACE_SUPPORT
 	depends on !X86_64
 	select STACKTRACE
-	select FRAME_POINTER if !MIPS && !PPC && !S390 && !MICROBLAZE && !ARM_UNWIND && !ARC && !SCORE
+	select FRAME_POINTER if !MIPS && !PPC && !S390 && !MICROBLAZE && !ARM_UNWIND && !ARC && !SCORE && !X86
 	help
 	  Provide stacktrace filter for fault-injection capabilities
 

@@ -1513,7 +1513,7 @@ config LATENCYTOP
 	depends on DEBUG_KERNEL
 	depends on STACKTRACE_SUPPORT
 	depends on PROC_FS
-	select FRAME_POINTER if !MIPS && !PPC && !S390 && !MICROBLAZE && !ARM_UNWIND && !ARC
+	select FRAME_POINTER if !MIPS && !PPC && !S390 && !MICROBLAZE && !ARM_UNWIND && !ARC && !X86
 	select KALLSYMS
 	select KALLSYMS_ALL
 	select STACKTRACE

2.7.5

Perfect naming!

(ORC might also stand for "Optimized Rewind Capability".)

BTW., we should perhaps consolidate our unwinder related Kconfig space, hierarchically:

CONFIG_UNWINDER
CONFIG_UNWINDER_ORC
CONFIG_UNWINDER_FRAME_POINTERS

Note that as a side effect it would be a valid small systems build option to have no unwinder at all, if CONFIG_EXPERT=y is set and such: !CONFIG_UNWINDER=n would be a sibling to !CONFIG_BUG.

CONFIG_FRAME_POINTERS et al would be left for architectures where it has a meaning beyond backtrace generation. (Not sure whether there's any such architectures.)

Ok, I'll start applying your patches after -rc1, unless anyone objects.

Could we also write this in percentage, not absolute RAM size - i.e. ORC unwind tables take 30% more RAM (+0.7 MB on an x86 defconfig kernel) than DWARF eh_frame tables.

Thanks,

Ingo

So is the idea that CONFIG_UNWINDER=n means "use the 'guess' unwinder"? Or should it mean that the unwind API isn't available?

Without frame pointers and orc, it defaults to the 'guess' unwinder, for which the only overhead is a tiny amount of code. It's still technically considered an unwinder because it plugs into the unwind interfaces (unwind_start(), unwind_next_frame(), etc) and is used for things like /proc/<pid>/stack.

So I'm not really sure CONFIG_UNWINDER=n would make sense. Maybe there should just be a multiple-choice where you have to choose one of CONFIG_UNWINDER_{ORC,FRAME_POINTER,GUESS}.

Well, on x86, hardened usercopy relies on frame pointers, but not the unwinder. It does the frame pointer walk manually to avoid the full unwinder overhead. See arch_within_stack_frames().

Thank you Ingo!

Ok, how about:

"Orc unwind tables take up ~50% more RAM (+1.3MB on an x86 defconfig kernel) than DWARF eh_frame tables."

(My previous 1MB number was from my distro-based config, and it also forgot to take into account the fast lookup table (".orc_lookup")).

Josh

Ok, you are right.

Maybe we could offer a menu of unwinders - i.e. make the whole Kconfig interface a bit nicer:

CONFIG_UNWINDER_FRAME_POINTER
CONFIG_UNWINDER_ORC
CONFIG_UNWINDER_GUESS

... or so?

Default would be the historic FRAME_POINTER, at least initially, I think.

I wouldn't mind making CONFIG_UNWINDER_ORC the new default either, due to the non-trivial speedup it offers - but maybe folks would object?

Oh well...

Sounds good to me!

Thanks,

Ingo

So far I haven't been able to figure out how to make the above three options into a multiple choice selection, such that allnoconfig selects CONFIG_UNWINDER_GUESS and alldefconfig selects CONFIG_UNWINDER_FRAME_POINTER.

I *think* I should be able to do it by setting the choice default to FRAME_POINTER, and setting the 'allnoconfig_y' option for UNWINDER_GUESS. But kconfig apparently doesn't support 'allnoconfig_y' for choice selections yet. I may need to modify kconfig for that.

But IMO, this change can come later, and the current patches should be fine to merge as-is. And it might make sense to delay such a patch anyway, see below.

Personally I wouldn't have an objection to making ORC the default, though we should probably wait to give it some burn-in time first.

If we *do* decide to eventually make it the default, we could flip the switch at the same time we introduced the multiple-choice config and rename above. That way, users of "make oldconfig" would see the change and would be encouraged to switch ORC.

Ok, I'll post a v3.1 of patch 9 with the changed wording.

Josh

I don't think that's a problem: the scheduler preemption model Kconfig setup has similar behavior - allyesconfig does not enable CONFIG_PREEMPT=y.

The new x86 default will eventually be the Orc unwinder, but not initially.

Sure, that's what testing is for.

I disagree, as the current Kconfig layout actively hinders the 'more testing'
part: you can only enable Orc if you knew how to do it, and 99% of our testers won't bother. In practice that's a testing coverage that is close to not testing it at all ...

BTW., I think this aspect of the hardened user-copy is crazy stuff - there can be many stack frames, and this adds a serious amount of overhead even with frame pointers...

I think the current behavior is fine: if frame pointers are disabled then arch_within_stack_frames() returns NOT_STACK. Maybe it could do a few sanity
checks: we do know the kernel stack range and we could check alignment as well.

Thanks,

Ingo

[ Adding Kees to CC for the hardened usercopy discussion. ]

Kees, FYI: frame pointers may be disabled by default on x86 relatively soon (presumably weeks or months) in favor of the ORC unwinder. So the hardened usercopy stack walk will no longer work as advertised.

Using the ORC unwinder for hardened usercopy would probably be pretty bad performance-wise. I'm not sure what else could be done. Ingo did have a few ideas for sanity checks:

I believe it checks the kernel stack range already in check_stack_object() before deciding whether to call arch_within_stack_frames(). It also has an overlapping stack check.

Josh

Right, pointers starting in the stack are already checked to not go beyond the stack.

As far as dropping inter-frame overflow checking, while I'd prefer to keep it, but its benefit in my mind is already pretty minimal since it already doesn't protect/exclude the stack canary. And since this is a check for a linear overflow (i.e. a contiguous access) we're mostly protected by the existing stack canary for writes. For reads, we do risk allowing return addresses to get exposed, though without the frame pointer, we've got even less to expose in the first place.

So, mainly, I'm fine with this. I'm slightly sad, but it's not a huge loss. The main benefit of usercopy hardening is the slab cache object size protections...

-Kees

Kees Cook
Pixel Security

Hi,

Is this going to be usable for userland call-graphs as well? If one converts dwarf to that, I mean? Because right now with perf dwarf is often the only thing that works properly through libc, as libc isn't compiled with fps and has hardcoded asm not preserving fp. lbr isn't available for many events, and often not at all available in VMs etc.

Regards,

Andres

Just to clarify, these patches are completely separate from DWARF and shouldn't break any existing DWARF-based functionality for user space tooling. So perf can still use DWARF for user space binaries just fine.

(Also, tools which rely on CONFIG_DEBUG_INFO for kernel debugging, like gdb and crash, will continue to work.)

If you want perf to be able to use ORC instead of DWARF for user space binaries, that's not currently possible, though I don't see any technical blockers for doing so. Perf would need to be taught to read ORC data.

And I think it should be possible to convert DWARF to ORC, assuming the DWARF data is trusted. We could probably add an objtool subcommand for that.

Josh

Hi,

Right, that's what I was hoping for.

That'd be pretty helpful.

Greetings,

Andres Freund

Can I ask why? Is DWARF too slow, or is it something else?

Josh

Both. Dwarf is really slow and uses a lot of space - on a bigger machine it's often nearly unusable. Secondly dwarf isn't available for BPF based stuff, IIUC because the kernel has to create a full backtrace there (rather than saving enough data that userland can do so). Which wasn't "allowed" to be done in-kernel w/ dwarf, just fp so far.

- Andres

So the problem with userspace stuff is that the unwind data isn't readily available from NMI context.

So the kernel unwinder will trigger a fault and abort.

The very best we can hope for is using the EH [*] stuff that all binaries actually have _and_ map. The only problem is that most programs don't actually use the EH stuff much so while its mapped, its not actually paged in, so we're still stuck.

[*] C++ ABI requires EH bits for stack unwinding for exception handling and the like, and because C++ can unwind through C code, C ABI also mandates EH bits be present.

ORC doesn't much change this. What is currently an option is for perf to simply copy out the top n-Kb of the stack for each sample (talk about expensive) and then have userspace unwind it. And for userspace unwinding in userspace, libunwind and the like are fine, I see absolutely no reason to use ORC bits here.

One gloriously ugly hack would be to delay the userspace unwind to return-to-userspace, at which point we have a schedulable context and can take faults.

Of course, then you have to somehow identify this later unwind sample with all relevant prior samples and stitch the whole thing back together, but that should be doable.

In fact, it would be at all hard to do, just queue a task_work from the NMI and have that do the EH based unwind.

+not

I don't think it's ugly, and it has various advantages:

This would have a couple of advantages:

- as you mention, being able to fault in debug info and generally do IO/scheduling,

- profiling overhead would be accounted to the task context that generates it, not the NMI context,

- there would be a natural batching/coalescing optimization if multiple events hit the same system call: the user-space backtrace would only have to be looked up once for all samples that got collected.

This could be done by separating the user-space backtrace into a separate event, and perf tooling would then apply the same user-space backtrace to all prior kernel samples.

I.e. the ring-buffer would have trace entries like:

[ kernel sample #1, with kernel backtrace #1 ]
[ kernel sample #2, with kernel backtrace #2 ]
[ kernel sample #3, with kernel backtrace #3 ]
[ user-space backtrace #1 at syscall return ]
...

Note how the three kernel samples didn't have to do any user-space unwinding at all, so the user-space unwinding overhead got reduced by a factor of 3.

Tooling would know that 'user-space backtrace #1' applies to the previous three kernel samples.

Or so?

Thanks,

Ingo

BTW, while we're throwing out ideas for this, here's another idea, though it's almost certainly not a good one :-)

For user space stack unwinding, the kernel could emulate what the kernel 'guess' unwinder does by scanning the user space stack and returning all the text addresses it finds.

The results wouldn't be 100% accurate, but they could end up being useful over time.

Josh

And to expound further on the bad idea, maybe the "bad" addresses could be filtered out somehow in post-processing (insert lots of hand waving).

Josh

To clarify, text address would mean any address in a VMA with the executable bit set.

And some details on the post-processing: in most cases it should be possible to determine which of the found stack addresses are valid by looking at the call instructions immediately preceding the stack text addresses, and making sure the call target points to the same function as the previously found address. But of course that wouldn't work for indirect calls.

Josh

I believe this is similar to how OProfile did graph/dwarf profiling, by saving a copy of the stack and post-processing it.

By my best recollection (but I haven't used OProfile that much) it was both a performance nightmare, was limited (because it only saved a part of the stack), and was rather fragile as well, because it depended on the task VM being post-processable.

I think the highest quality implementation is to generate the call trace either in hardware (LBR), or as close to the event as possible: generate the kernel call chain in the PMI context, and the user-space call chain before user-space executes again (at the latest). Call chain generation should be roughly O(chain_depth), which both FP and ORC ensures.

Thanks,

Ingo

User-space stacks tend to be much larger than kernel stacks, the cost of doing such a full scan on every PMI would kill a lot of profiling workloads.

Thanks,

Ingo

Find compile tested patch below, someone needs to teach this userspace thing about it though.. Not sure I can still make sense of that code.

---
 include/linux/perf_event.h      |  1 +
 include/uapi/linux/perf_event.h | 14 ++++++-
 kernel/events/callchain.c       | 86 ++++++++++++++++++++++++++++++++++++++---
 kernel/events/core.c            | 18 +++------
 4 files changed, 100 insertions(+), 19 deletions(-)

index a3b873fc59e4..241251533e39 100644
@@ -682,6 +682,7 @@ struct perf_event {
 	int				pending_disable;
 	struct irq_work			pending;
 
+	struct callback_head		pending_callchain;
 	atomic_t			event_limit;
 
 	/* address range filters */

index 642db5fa3286..342def57ef34 100644
@@ -368,7 +368,8 @@ struct perf_event_attr {
 				context_switch :  1, /* context switch data */
 				write_backward :  1, /* Write ring buffer from end to beginning */
 				namespaces     :  1, /* include namespaces data */
-				__reserved_1   : 35;
+				delayed_user_callchain   : 1, /* ... */
+				__reserved_1   : 34;
 
 	union {
 		__u32		wakeup_events;	  /* wakeup every n events */

@@ -915,6 +916,17 @@ enum perf_event_type {
 	 */
 	PERF_RECORD_NAMESPACES			= 16,
 
+	/*
+	 * struct {
+	 *	struct perf_event_header	header;
+	 *	{ u64			nr,
+	 *	  u64			ips[nr];  } && PERF_SAMPLE_CALLCHAIN
+	 *	struct sample_id		sample_id;
+	 * };
+	 *
+	 */
+	PERF_RECORD_CALLCHAIN			= 17,
+
 	PERF_RECORD_MAX,			/* non-ABI */
 };
 

index 426c2ffba16d..26aed7bfbb6a 100644
@@ -5857,19 +5857,12 @@ void perf_output_sample(struct perf_output_handle *handle,
 		perf_output_read(handle, event);
 
 	if (sample_type & PERF_SAMPLE_CALLCHAIN) {
-		if (data->callchain) {
-			int size = 1;
-
-			if (data->callchain)
-				size += data->callchain->nr;
+		int size = 1;
 
-			size *= sizeof(u64);
+		size += data->callchain->nr;
+		size *= sizeof(u64);
 
-			__output_copy(handle, data->callchain, size);
-		} else {
-			u64 nr = 0;
-			perf_output_put(handle, nr);
-		}
+		__output_copy(handle, data->callchain, size);
 	}
 
 	if (sample_type & PERF_SAMPLE_RAW) {

@@ -6010,8 +6003,7 @@ void perf_prepare_sample(struct perf_event_header *header,
 
 		data->callchain = perf_callchain(event, regs);
 
-		if (data->callchain)
-			size += data->callchain->nr;
+		size += data->callchain->nr;
 
 		header->size += size * sizeof(u64);
 	}

On Tue, Jul 25, 2017 at 01:55:12PM +0200, Peter Zijlstra wrote:

SNIP

Right, so I put all the magic in the callchain code itself, which would make that a wee bit harder. But yes, putting all the USER stuff in there makes sense.

I haven't checked task_work specifically, but a bunch of the exit work is permitted to sleep, which is potentially useful.

If this becomes successful enough that we could eventually deprecate the old code, I wonder if copy_from_user_nmi() could go away? :)

Yes.

So we still use that for things like the PEBS IP fixup for older CPUs. That needs to read the userspace code.

Also, since all this is optional on userspace asking for the new format, we will probably (forever) need to support userspace not asking for it.

Correct, I have been thinking on how to do that but haven't found anything particularly nice yet.

That is one I hadn't thought of, but basically task_work_add() will fail if the task is too far gone. At that point we should fallback to the 'old' behaviour and simply include the information in the kernel SAMPLE record.

Can we have an option to just use dwarf instead? For people who don't want to waste a MB+ to solve a problem that doesn't exist (as proven by many years of opensuse kernel experience)

As far as I can tell this whole thing has only downsides compared to the dwarf unwinder that was earlier proposed. I don't see a single advantage.

-Andi

Improved speed, reliability, maintainability. Are those not advantages?

Josh

Ok. We'll see how it works out.

The memory overhead is quite bad though. You're basically undoing many years of efforts to shrink kernel text. I hope this can be still done better.

-Andi

If we're talking *text*, this further shrinks text size by 3% because frame pointers can be disabled.

As far as the data size goes, is anyone *truly* impacted by that extra 1MB or so? If you're enabling a DWARF/ORC unwinder, you're already signing up for a few extra megs anyway.

I do have a vague idea about how to reduce the data size, if/when the size becomes a problem. Basically there's a *lot* of duplication in the ORC data:

  $ tools/objtool/objtool orc dump vmlinux | wc -l
  311095

  $ tools/objtool/objtool orc dump vmlinux |cut -d' ' -f2- |sort |uniq |wc -l
  345

So that's over 300,000 6-byte entries, only 345 of which are unique. There should be a way to compress that. However, it will probably require sacrificing some combination of speed and simplicity.

Josh

Exactly, and all these advantages of the ORC debuginfo over DWARF debuginfo are enabled by an unwinding optimized data format that the kernel project generates, controls and is able to trust inherently.

DWARF generated by external tooling can just never reach that level of trust, without insane amounts of formal verification.

Even if ORC was _slower_ its reliability would be reason enough to merge. The fact that it's 20-40 times faster than the DWARF unwinder is really just icing on the cake.

BTW., as a side note, (and I hope my optimism isn't premature), I believe the ORC unwinder is a prime example of where Linus's stubborness resisting poor concepts paid off in the long run: had we merged the DWARF unwinder years ago we'd never have gained the ORC unwinder. We quite literally had to wait over a decade, but good things happened in the end.

Thanks,

Ingo

If someone wanted to write an in-kernel DWARF parser that hooked into the same machinery that Josh is using and comes with a complete formal verification package, I might not object, with the caveat that it's likely to be *much* slower than ORC. By complete formal verification, I mean that a user tool running the exact same code, compiled with strong sanitization, should decode the tables for every single kernel IP and confirm that (a) the output is sane, (b) the output matches what objtool says it should do and (c) doesn't crash.

I'm not sure I see the point, though. I also think that Linus would object, since I asked him quite recently and he said he'd object.

Sure the dwarf unwinder works well for crashes, but at the price of demolishing ftrace/perf utility.

-Mike

You mean the unwind performance?

That's a valid concern, but neither ORC nor dwarf are likely to address it. However most usages of ftrace/perf shouldn't be that depending on unwind performance -- just lower the frequency of your events.

The only possible win is if the win from not using FP code is significant enough. On the x86 side the only modern CPUs that should really care about this are Atoms.

-Andi

Yeah, it hurts.. massively, has even been known to kill big boxen.

Nope, they all care. Measure performance delta of fast/light stuff.

Maybe I'm expecting too much good stuff to follow, but don't spoil it for me, I think I'm looking at a real winner :)

-Mike

Why was that?

Well if your test cares that much about function overhead you may want to try LTO. It can get rid of a lot of functions by doing cross file inlining.

https://git.kernel.org/pub/scm/linux/kernel/git/ak/linux-misc.git/log/?h=lto-411-2

It's somewhat surprising. It would be good to under stand why that happens. Is it icache misses, data cache misses for the stack, or simply more instructions executed, or worse tail calls?

-Andi

Presuming you mean the big box bit, danged if I know, I haven't personally met that, only the massive overhead.

No idea.  It was speculated that it was register loss, but I played with that, saw nearly zero delta until I stole too many.

-Mike