Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S933525AbdGKPeC (ORCPT ); Tue, 11 Jul 2017 11:34:02 -0400 Received: from mx1.redhat.com ([209.132.183.28]:47310 "EHLO mx1.redhat.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S933384AbdGKPeA (ORCPT ); Tue, 11 Jul 2017 11:34:00 -0400 DMARC-Filter: OpenDMARC Filter v1.3.2 mx1.redhat.com 251D680F95 Authentication-Results: ext-mx03.extmail.prod.ext.phx2.redhat.com; dmarc=none (p=none dis=none) header.from=redhat.com Authentication-Results: ext-mx03.extmail.prod.ext.phx2.redhat.com; spf=pass smtp.mailfrom=jpoimboe@redhat.com DKIM-Filter: OpenDKIM Filter v2.11.0 mx1.redhat.com 251D680F95 From: Josh Poimboeuf To: x86@kernel.org Cc: linux-kernel@vger.kernel.org, live-patching@vger.kernel.org, Linus Torvalds , Andy Lutomirski , Jiri Slaby , Ingo Molnar , "H. Peter Anvin" , Peter Zijlstra , Mike Galbraith Subject: [PATCH v3 00/10] x86: ORC unwinder (previously undwarf) Date: Tue, 11 Jul 2017 10:33:37 -0500 Message-Id: X-Greylist: Sender IP whitelisted, not delayed by milter-greylist-4.5.16 (mx1.redhat.com [10.5.110.27]); Tue, 11 Jul 2017 15:34:00 +0000 (UTC) Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 14678 Lines: 323 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/20170602104048.jkkzssljsompjdwy@suse.de [2] https://lkml.kernel.org/r/d2ca5435-6386-29b8-db87-7f227c2b713a@suse.cz [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