Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1685158 > unrolled thread

[PATCH v3 00/10] x86: ORC unwinder (previously undwarf)

Back to article view | Back to linux.kernel

Contents

  [PATCH v3 00/10] x86: ORC unwinder (previously undwarf) Josh Poimboeuf <jpoimboe@redhat.com> - 2017-07-11 17:40 +0200
    Re: [PATCH v3 00/10] x86: ORC unwinder (previously undwarf) Ingo Molnar <mingo@kernel.org> - 2017-07-12 10:30 +0200
      Re: [PATCH v3 00/10] x86: ORC unwinder (previously undwarf) Josh Poimboeuf <jpoimboe@redhat.com> - 2017-07-12 16:50 +0200
        Re: [PATCH v3 00/10] x86: ORC unwinder (previously undwarf) Ingo Molnar <mingo@kernel.org> - 2017-07-12 21:30 +0200
          Re: [PATCH v3 00/10] x86: ORC unwinder (previously undwarf) Josh Poimboeuf <jpoimboe@redhat.com> - 2017-07-14 19:20 +0200
    Re: [PATCH v3 00/10] x86: ORC unwinder (previously undwarf) Andres Freund <andres@anarazel.de> - 2017-07-12 23:50 +0200
      Re: [PATCH v3 00/10] x86: ORC unwinder (previously undwarf) Josh Poimboeuf <jpoimboe@redhat.com> - 2017-07-13 00:40 +0200
        Re: [PATCH v3 00/10] x86: ORC unwinder (previously undwarf) Andres Freund <andres@anarazel.de> - 2017-07-13 00:40 +0200
          Re: [PATCH v3 00/10] x86: ORC unwinder (previously undwarf) Josh Poimboeuf <jpoimboe@redhat.com> - 2017-07-13 00:50 +0200
            Re: [PATCH v3 00/10] x86: ORC unwinder (previously undwarf) Andres Freund <andres@anarazel.de> - 2017-07-13 01:00 +0200
        Re: [PATCH v3 00/10] x86: ORC unwinder (previously undwarf) Peter Zijlstra <peterz@infradead.org> - 2017-07-13 09:20 +0200
          Re: [PATCH v3 00/10] x86: ORC unwinder (previously undwarf) Peter Zijlstra <peterz@infradead.org> - 2017-07-13 11:00 +0200
            Re: [PATCH v3 00/10] x86: ORC unwinder (previously undwarf) Ingo Molnar <mingo@kernel.org> - 2017-07-13 11:20 +0200
              Re: [PATCH v3 00/10] x86: ORC unwinder (previously undwarf) Josh Poimboeuf <jpoimboe@redhat.com> - 2017-07-13 14:20 +0200
                Re: [PATCH v3 00/10] x86: ORC unwinder (previously undwarf) Josh Poimboeuf <jpoimboe@redhat.com> - 2017-07-13 14:30 +0200
                  Re: [PATCH v3 00/10] x86: ORC unwinder (previously undwarf) Josh Poimboeuf <jpoimboe@redhat.com> - 2017-07-13 14:40 +0200
                    Re: [PATCH v3 00/10] x86: ORC unwinder (previously undwarf) Ingo Molnar <mingo@kernel.org> - 2017-07-14 10:40 +0200
                Re: [PATCH v3 00/10] x86: ORC unwinder (previously undwarf) Ingo Molnar <mingo@kernel.org> - 2017-07-14 10:30 +0200
          Re: [PATCH v3 00/10] x86: ORC unwinder (previously undwarf) Peter Zijlstra <peterz@infradead.org> - 2017-07-13 11:00 +0200
    Re: [PATCH v3 00/10] x86: ORC unwinder (previously undwarf) Andi Kleen <andi@firstfloor.org> - 2017-07-13 00:40 +0200
      Re: [PATCH v3 00/10] x86: ORC unwinder (previously undwarf) Josh Poimboeuf <jpoimboe@redhat.com> - 2017-07-13 00:50 +0200
        Re: [PATCH v3 00/10] x86: ORC unwinder (previously undwarf) Andi Kleen <andi@firstfloor.org> - 2017-07-13 06:30 +0200
          Re: [PATCH v3 00/10] x86: ORC unwinder (previously undwarf) Josh Poimboeuf <jpoimboe@redhat.com> - 2017-07-13 15:20 +0200
        Re: [PATCH v3 00/10] x86: ORC unwinder (previously undwarf) Ingo Molnar <mingo@kernel.org> - 2017-07-13 11:30 +0200
      Re: [PATCH v3 00/10] x86: ORC unwinder (previously undwarf) Andy Lutomirski <luto@kernel.org> - 2017-07-13 01:30 +0200
      Re: [PATCH v3 00/10] x86: ORC unwinder (previously undwarf) Mike Galbraith <efault@gmx.de> - 2017-07-13 05:10 +0200
        Re: [PATCH v3 00/10] x86: ORC unwinder (previously undwarf) Andi Kleen <andi@firstfloor.org> - 2017-07-13 06:20 +0200
          Re: [PATCH v3 00/10] x86: ORC unwinder (previously undwarf) Mike Galbraith <efault@gmx.de> - 2017-07-13 06:40 +0200
            Re: [PATCH v3 00/10] x86: ORC unwinder (previously undwarf) Andi Kleen <andi@firstfloor.org> - 2017-07-13 06:50 +0200
              Re: [PATCH v3 00/10] x86: ORC unwinder (previously undwarf) Mike Galbraith <efault@gmx.de> - 2017-07-13 07:30 +0200
              Re: [PATCH v3 00/10] x86: ORC unwinder (previously undwarf) Jiri Kosina <jikos@kernel.org> - 2017-07-13 14:10 +0200

Page 1 of 2  [1] 2  Next page →

#1685158 — [PATCH v3 00/10] 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/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

[toc] | [next] | [standalone]

#1685621

* Josh Poimboeuf <jpoimboe@redhat.com> wrote:

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

Perfect naming!

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

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

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.)

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

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

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

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

[toc] | [prev] | [next] | [standalone]

#1685828

On Wed, Jul 12, 2017 at 10:27:10AM +0200, Ingo Molnar wrote:
> > 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.
> 
> 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.

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}.

> 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.)

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().

> > 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.
> 
> Ok, I'll start applying your patches after -rc1, unless anyone objects.

Thank you Ingo!

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

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

[toc] | [prev] | [next] | [standalone]

#1685993

* Josh Poimboeuf <jpoimboe@redhat.com> wrote:

> On Wed, Jul 12, 2017 at 10:27:10AM +0200, Ingo Molnar wrote:
> > > 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.
> > 
> > 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.
> 
> 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}.

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?

> > 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.)
> 
> 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().

Oh well...

> 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")).

Sounds good to me!

Thanks,

	Ingo

[toc] | [prev] | [next] | [standalone]

#1687574

On Wed, Jul 12, 2017 at 09:27:50PM +0200, Ingo Molnar wrote:
> 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?

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.

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

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.

> > > 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.)
> > 
> > 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().
> 
> Oh well...
> 
> > 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")).
> 
> Sounds good to me!

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

-- 
Josh

[toc] | [prev] | [next] | [standalone]

#1686065

Hi,

On 2017-07-11 10:33:37 -0500, Josh Poimboeuf wrote:
> The simpler debuginfo format also enables the unwinder to be much faster
> than DWARF, which is important for perf and lockdep.

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

[toc] | [prev] | [next] | [standalone]

#1686084

On Wed, Jul 12, 2017 at 02:49:20PM -0700, Andres Freund wrote:
> Hi,
> 
> On 2017-07-11 10:33:37 -0500, Josh Poimboeuf wrote:
> > The simpler debuginfo format also enables the unwinder to be much faster
> > than DWARF, which is important for perf and lockdep.
> 
> 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.

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

[toc] | [prev] | [next] | [standalone]

#1686088

Hi,

On 2017-07-12 17:32:25 -0500, Josh Poimboeuf wrote:
> 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.

Right, that's what I was hoping for.


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

That'd be pretty helpful.

Greetings,

Andres Freund

[toc] | [prev] | [next] | [standalone]

#1686097

On Wed, Jul 12, 2017 at 03:36:05PM -0700, Andres Freund wrote:
> Hi,
> 
> On 2017-07-12 17:32:25 -0500, Josh Poimboeuf wrote:
> > 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.
> 
> Right, that's what I was hoping for.
> 
> 
> > 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.
> 
> That'd be pretty helpful.

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

-- 
Josh

[toc] | [prev] | [next] | [standalone]

#1686106

On 2017-07-12 17:40:45 -0500, Josh Poimboeuf wrote:
> On Wed, Jul 12, 2017 at 03:36:05PM -0700, Andres Freund wrote:
> > Hi,
> > 
> > On 2017-07-12 17:32:25 -0500, Josh Poimboeuf wrote:
> > > 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.
> > 
> > Right, that's what I was hoping for.
> > 
> > 
> > > 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.
> > 
> > That'd be pretty helpful.
> 
> Can I ask why?  Is DWARF too slow, or is it something else?

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

[toc] | [prev] | [next] | [standalone]

#1686310

On Wed, Jul 12, 2017 at 05:32:25PM -0500, Josh Poimboeuf wrote:
> 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.

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.

[toc] | [prev] | [next] | [standalone]

#1686388

On Thu, Jul 13, 2017 at 10:50:15AM +0200, Peter Zijlstra wrote:
> On Thu, Jul 13, 2017 at 09:12:53AM +0200, Peter Zijlstra wrote:
> > On Wed, Jul 12, 2017 at 05:32:25PM -0500, Josh Poimboeuf wrote:
> > > 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.
> > 
> > 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.
> 
> 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

+not

> NMI and have that do the EH based unwind.

[toc] | [prev] | [next] | [standalone]

#1686396

* Peter Zijlstra <peterz@infradead.org> wrote:

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

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

> > 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 not be at all hard to do, just queue a task_work from the 
> > NMI and have that do the EH based unwind.

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

[toc] | [prev] | [next] | [standalone]

#1686486

On Thu, Jul 13, 2017 at 11:19:11AM +0200, Ingo Molnar wrote:
> 
> * Peter Zijlstra <peterz@infradead.org> wrote:
> 
> > > 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.
> 
> I don't think it's ugly, and it has various advantages:
> 
> > > 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 not be at all hard to do, just queue a task_work from the 
> > > NMI and have that do the EH based unwind.
> 
> 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?

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

[toc] | [prev] | [next] | [standalone]

#1686497

On Thu, Jul 13, 2017 at 07:17:55AM -0500, Josh Poimboeuf wrote:
> 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.

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

[toc] | [prev] | [next] | [standalone]

#1686503

On Thu, Jul 13, 2017 at 07:21:15AM -0500, Josh Poimboeuf wrote:
> On Thu, Jul 13, 2017 at 07:17:55AM -0500, Josh Poimboeuf wrote:
> > 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.

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

> > The results wouldn't be 100% accurate, but they could end up being
> > useful over time.
> 
> 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).

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

[toc] | [prev] | [next] | [standalone]

#1687160

* Josh Poimboeuf <jpoimboe@redhat.com> wrote:

> > > The results wouldn't be 100% accurate, but they could end up being useful 
> > > over time.
> > 
> > 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).
> 
> 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.

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

[toc] | [prev] | [next] | [standalone]

#1687149

* Josh Poimboeuf <jpoimboe@redhat.com> wrote:

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

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

[toc] | [prev] | [next] | [standalone]

#1686390

On Thu, Jul 13, 2017 at 09:12:53AM +0200, Peter Zijlstra wrote:
> On Wed, Jul 12, 2017 at 05:32:25PM -0500, Josh Poimboeuf wrote:
> > 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.
> 
> 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.

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.

[toc] | [prev] | [next] | [standalone]

#1686079

Josh Poimboeuf <jpoimboe@redhat.com> writes:
>
> 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.
>
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

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | linux.kernel

csiph-web