[RFC PATCH 00/10] x86: undwarf unwinder

[Josh Poimboeuf]

Create a new 'undwarf' unwinder, enabled by CONFIG_UNDWARF_UNWINDER, and
plug it into the x86 unwinder framework.  Objtool is used to generate
the undwarf debuginfo.  The undwarf 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.

I'm not tied to the 'undwarf' name, other naming ideas are welcome.

Some potential future improvements:
- properly annotate or fix whitelisted functions and files
- reduce the number of base CFA registers needed in entry code
- compress undwarf debuginfo to use less memory
- make it easier to disable CONFIG_FRAME_POINTER
- add reliability checks for livepatch
- runtime NMI stack reliability checker

This code can also be found at:

  git://github.com/jpoimboe/linux undwarf-rfc

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


Undwarf debuginfo generation
============================

Overview
--------

The kernel CONFIG_UNDWARF_UNWINDER option enables objtool generation of
undwarf debuginfo, which is out-of-band data which is used by the
in-kernel undwarf unwinder.  It's similar in concept to DWARF CFI
debuginfo which would be used by a DWARF unwinder.  The difference is
that the format of the undwarf data is simpler than DWARF, which in turn
allows the unwinder to be simpler.

Objtool generates the undwarf data by piggybacking on the compile-time
stack metadata validation work described in stack-validation.txt.  After
analyzing all the code paths of a .o file, it creates an array of
'struct undwarf's and writes them to the .undwarf section.

Then at vmlinux link time, the .undwarf section is sorted by the
sorttable script.  The resulting sorted array of undwarf structs is used
by the unwinder at runtime to correlate a given text address with its
stack state.


Why not just use DWARF?
-----------------------

Undwarf has some of the same benefits as DWARF.  Unlike frame pointers,
the debuginfo is out-of-band. so it has no effect on runtime
performance.  Another benefit is that it's possible to reliably unwind
across interrupts and exceptions.

Undwarf debuginfo's advantage over DWARF itself is that it's much
simpler.  It gets rid of the 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 relatively
fast, which is important for perf and lockdep.

The undwarf format does have a few downsides.  The undwarf table takes
up extra memory -- something in the ballpark of 3-5MB, depending on the
kernel config.  In the future we may try to rearrange the data to
compress that a bit.

Another downside is that, as GCC evolves, it's conceivable that the
undwarf data may end up being *too* simple to describe the state of the
stack for certain optimizations.  Will we end up having to track the
state of more registers and eventually end up reinventing DWARF?

I think this is unlikely because GCC seems to save 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 control the format, e.g.
no complex state machines.


Why generate undwarf with objtool?
----------------------------------

It should be possible to generate the undwarf data with a simple tool
which converts DWARF to undwarf.  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.

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

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 it's much more
maintainable than DWARF CFI annotations.

So the advantages of using objtool to generate undwarf are that it gives
more accurate debuginfo, with close to zero annotations.  It also
insulates the kernel from toolchain bugs which can be very painful to
deal with in the kernel since it often has 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 flows.  If GCC optimizations become
too complicated for objtool to follow, the undwarf generation might stop
working or become incomplete.  In such a case 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.


Josh Poimboeuf (10):
  objtool: move checking code to check.c
  objtool, x86: add several functions and files to the objtool whitelist
  objtool: stack validation 2.0
  objtool: add undwarf debuginfo generation
  objtool, x86: add facility for asm code to provide CFI hints
  x86/entry: add CFI hint undwarf annotations
  x86/asm: add CFI hint annotations to sync_core()
  extable: rename 'sortextable' script to 'sorttable'
  extable: add undwarf table sorting ability to sorttable script
  x86/unwind: add undwarf unwinder

 Documentation/dontdiff                           |    2 +-
 arch/um/include/asm/unwind.h                     |    7 +
 arch/x86/Kconfig                                 |    1 +
 arch/x86/Kconfig.debug                           |   26 +
 arch/x86/crypto/Makefile                         |    2 +
 arch/x86/crypto/sha1-mb/Makefile                 |    2 +
 arch/x86/crypto/sha256-mb/Makefile               |    2 +
 arch/x86/entry/Makefile                          |    1 -
 arch/x86/entry/calling.h                         |    5 +
 arch/x86/entry/entry_64.S                        |   56 +-
 arch/x86/include/asm/module.h                    |    8 +
 arch/x86/include/asm/processor.h                 |    3 +
 arch/x86/include/asm/undwarf-types.h             |  100 ++
 arch/x86/include/asm/undwarf.h                   |   97 ++
 arch/x86/include/asm/unwind.h                    |   64 +-
 arch/x86/kernel/Makefile                         |    9 +-
 arch/x86/kernel/acpi/Makefile                    |    2 +
 arch/x86/kernel/kprobes/opt.c                    |    9 +-
 arch/x86/kernel/module.c                         |    9 +-
 arch/x86/kernel/reboot.c                         |    2 +
 arch/x86/kernel/unwind_frame.c                   |   39 +-
 arch/x86/kernel/unwind_guess.c                   |    5 +
 arch/x86/kernel/unwind_undwarf.c                 |  402 +++++++
 arch/x86/kvm/svm.c                               |    2 +
 arch/x86/kvm/vmx.c                               |    3 +
 arch/x86/lib/msr-reg.S                           |    8 +-
 arch/x86/net/Makefile                            |    2 +
 arch/x86/platform/efi/Makefile                   |    1 +
 arch/x86/power/Makefile                          |    2 +
 arch/x86/xen/Makefile                            |    3 +
 include/asm-generic/vmlinux.lds.h                |   14 +
 init/Kconfig                                     |    4 +
 kernel/kexec_core.c                              |    4 +-
 lib/Kconfig.debug                                |    3 +
 scripts/.gitignore                               |    2 +-
 scripts/Makefile                                 |    4 +-
 scripts/Makefile.build                           |    3 +-
 scripts/link-vmlinux.sh                          |   12 +-
 scripts/{sortextable.c => sorttable.c}           |  182 +--
 scripts/{sortextable.h => sorttable.h}           |   69 +-
 tools/objtool/Build                              |    3 +
 tools/objtool/Documentation/stack-validation.txt |  194 ++--
 tools/objtool/Documentation/undwarf.txt          |   99 ++
 tools/objtool/Makefile                           |    5 +-
 tools/objtool/arch.h                             |   64 +-
 tools/objtool/arch/x86/decode.c                  |  400 ++++++-
 tools/objtool/builtin-check.c                    | 1280 +---------------------
 tools/objtool/builtin-undwarf.c                  |   70 ++
 tools/objtool/builtin.h                          |    1 +
 tools/objtool/cfi.h                              |   55 +
 tools/objtool/{builtin-check.c => check.c}       |  868 +++++++++++----
 tools/objtool/check.h                            |   69 ++
 tools/objtool/elf.c                              |  247 ++++-
 tools/objtool/elf.h                              |    8 +-
 tools/objtool/objtool.c                          |    3 +-
 tools/objtool/special.c                          |    6 +-
 tools/objtool/undwarf-types.h                    |  100 ++
 tools/objtool/undwarf.c                          |  308 ++++++
 tools/objtool/{builtin.h => undwarf.h}           |   19 +-
 59 files changed, 3124 insertions(+), 1846 deletions(-)
 create mode 100644 arch/um/include/asm/unwind.h
 create mode 100644 arch/x86/include/asm/undwarf-types.h
 create mode 100644 arch/x86/include/asm/undwarf.h
 create mode 100644 arch/x86/kernel/unwind_undwarf.c
 rename scripts/{sortextable.c => sorttable.c} (71%)
 rename scripts/{sortextable.h => sorttable.h} (77%)
 create mode 100644 tools/objtool/Documentation/undwarf.txt
 create mode 100644 tools/objtool/builtin-undwarf.c
 create mode 100644 tools/objtool/cfi.h
 copy tools/objtool/{builtin-check.c => check.c} (62%)
 create mode 100644 tools/objtool/check.h
 create mode 100644 tools/objtool/undwarf-types.h
 create mode 100644 tools/objtool/undwarf.c
 copy tools/objtool/{builtin.h => undwarf.h} (64%)

-- 
2.7.4