There is a widespread perception that DWARF-based unwinders are slow and crashy. For example, a famous rant by Linus: https://lkml.org/lkml/2012/2/10/356. That rant applies to one specific Linux sub-project. User space has its own challenges with DWARF-based unwinding. The kernel uses an alternative called ORC. At least two efforts now aim to replace or amend DWARF unwinding in user space. And of course, there is a somewhat popular movement to build everything with frame pointers. But frame pointers don’t make all backtraces perfect. Not for CPU profiling, where profiling “ticks” in epilogues, prologues, or PLT are common. And imperfect backtraces can be confusing and painful to deal with.
We can do much better than that.
So for the last few months I was building aw-backtrace. aw-backtrace is the DWARF-based unwinder that won't crash and is very quick. It is a good-sized step towards perfect backtraces.
While I cannot “mathematically prove” that aw-backtrace cannot crash, I did put a serious effort into performing bounds checking for all the accesses, both for reading “DWARF stuff” and for reading register values from the stack.
Here is a quick introduction to DWARF unwind info. Every compiled function has FDE (slight simplification, but good enough for an intro). Each compile unit (.o file) has a CIE that describes language and architectural defaults (e.g., x86 functions start with the return address pushed on the stack). Another notion in the unwind info is the CFA, which is basically the stack pointer at the call site. Unwind info typically looks like: “to establish CFA take RSP register and add 16, then to take return address read machine word at CFA - 8, value of the RBP register is saved at CFA - 16”. This is represented as a sequence of CFI instructions that define such unwind info for each instruction in the function. Tools like readelf (with the -wf flag) can dump this and show you what it looks like. Alternatively, checking the compiler's assembly output is useful too, e.g., on godbolt: https://godbolt.org/z/dErnbcnT1
What makes DWARF unwinding a slightly harder target is that it was originally produced for debug info and was intentionally very powerful and general. But that means nearly unbounded complexity. Stuff like an arbitrarily deep stack of .cfi_remember_state. In practice, as we know from ORC and related efforts, compilers produce a fairly limited “shape” of unwind info. There are occasional non-trivial DWARF unwind info. For example, some hero has put into glibc for Linux/x86-64 (but I think only there) a very elaborate unwind info for signal trampolines. Because describing the restoration of every register from ucontext’s gregs fields involves indirections, it is full of DWARF expressions. Another very smart example is unwind info for the PLT section produced by the GNU linker (but for some reason the LLVM linker doesn’t produce any unwind info for PLTs).
For aw-backtrace, the explicit choice is to keep things safe. So it supports only a practical subset of unwind info, roughly on par with SFrame V3. aw-backtrace special-cases and explicitly handles known unusual cases like signal handler trampolines or the PLT. There are currently few functions that I see in libc (e.g., longjmp) and OpenSSL where unwind info is too advanced for aw-backtrace. I plan to address this eventually, but what it has now comfortably covers the vast majority of code.
I believe what compromised DWARF backtracers before is that backtracing was so far always just a side effect of more general code for propagating exceptions. If we’re in the middle of unwinding a stack for an exception and face a function with broken or excessively complex unwind info, there is nowhere to go anyway. With backtracing, you can always stop unwinding. Yes, truncated backtraces are imperfect. But crashing or hanging is much worse.
How do I know that uncommon unwind info is rare? It is straightforward to dump unwind info and grep for DWARF expressions. But also because I single-stepped through a bunch of code while comparing the actual backtrace with what aw-backtrace produces.
It is actually a somewhat remarkable piece. Grown out of my earlier effort to “torture” atfork handling in gperftools. I have code that sets the x86 TF flag, which makes the CPU “single step”. Stepping delivers an interrupt to the kernel, which passes it to user space as SIGTRAP. From that SIGTRAP handler, we run the comparer. To speed this up, I built a “mini interpreter” for the common subset of x86 instructions, so we don’t go through the interrupt/signal boundary every time. There are, of course, a bunch of nasty details, like fighting with other code for altstack or dealing with SIGTRAP masking. So it is by no means perfect. Some details are in the README, and the code is hopefully not too large and somewhat readable. I am actively replacing it with a portable solution that single-steps via a QEMU plugin.
Another part of the DWARF inspection sub-effort is the unwind-check tool I released together with aw-backtrace. It disassembles the code, compares its effects with unwind info, and complains if there is a mismatch. It already found 2 bugs in LLVM (but thankfully the mismatches are relatively short and don’t cross call-sites). In the future, I hope and expect compilers will “never again” produce bad unwind info. Because verifying unwind info is relatively straightforward.
And finally I have things to say about backtracing speed. We will likely never fully match the speed of trivial frame-pointer-based backtracers, but it is relatively easy to come very close. The key is caching. Workloads that capture many backtraces tend to step through the same call sites. Implementing a lockless, async-signal-safe cache was a mild challenge, but ultimately it is just a matter of engineering. The README has some details, and the code should be very readable too (for now, the focus was to keep things mega-simple; I undid the more advanced caching and eviction approach so the code is hopefully easy to verify and understand).
Beyond caching, yes, DWARF unwind info is by no means perfect for performance. Those inconvenient augmentation details. Or having to decode padding NOPs in CIE. But the basic stuff (redundant instructions in CIEs, basic prologue/epilogue bits) is basically very bounded in size and thus in decoding cost. The bigger inefficiency is having to advance sequentially from the start of the function to where we need to unwind.
In most cases, even larger functions are fairly straightforward. Most of such functions are covered by one or two large advances. But sometimes unwind info gets large when smaller advances occur between CFI updates. This happens more easily for functions that pass arguments on the stack, since pushing or popping anything updates frame size; in the common case of using stack pointer-based frame layout, it requires updating unwind info.
aw-backtrace comes with a recursion-test benchmark that artificially produces such a case. On those larger functions, one step of unwinding could approach 100 nanoseconds even in the cache-hot micro-benchmark. Thankfully such cases are not very common. I perf-recorded a kernel build, so most profiling ticks are in the guts of gcc, and the average number of CFI instructions per frame I see in this profile is around 19. Not great, but not too bad either. SQLite’s benchmark comes in at around 26. So still not a disaster.
In short, we could make unwinding much cheaper, and likely encode much tighter as well. But what we have today is already close enough to be useful in practice and not orders of magnitude worse. We can work with that. Especially given that caching more or less obviates the need for quick DWARF decoding.
Of course, the biggest performance bonus of aw-backtrace is that it unlocks wins of -fomit-frame-pointer.
