Frame pointers vs. DWARF – my verdict
rwmj.wordpress.com
rwmj.wordpress.com
As an alternative approach, https://github.com/mstange/samply processes data streamed from perf and unwinds it in realtime. The unwinding overhead is surprisingly low: it only takes around 1% of (single) CPU per CPU profiled. Solving the disk waste alone has been a tremendous improvement of profiling experience. As a bonus, the unwinding and symbolization works reliably while I frequently had postprocessing not terminating when using the perf CLI directly.
If you have framepointers and debug information, it is both high resolution and fast. DWARF is a fallback for not having framepointers.
If you are saying the DWARF information should be processed at the point of use and not copied and processed later, then I concur. But we should also encourage folks to compiled WITH `-fno-omit-frame-pointer` and `-g`
Edit: refer to another comment in this thread: https://news.ycombinator.com/item?id=34809265
> DWARF unwinding can show inlined functions as if they are separate stack frames. (Opinions differ as to whether or not this is an advantage.)
This conflates unwinding and symbolization. Unwinding collects the list of frames, which by definition cannot have inlined functions (functions that don't have their own frame); the unwinding mechanism does not matter here.
DWARF can be used to resolve the "stack" of inlined functions for an instruction address, even if that was collected via frame pointers. That can be done in post-processing, possibly on a different machine, so the cost does not affect the workload being profiled.
For example, using addr2line from the LLVM distribution
$ llvm-addr2line -pfi --demangle -e /path/to/unstripped/binary
# Enter instruction address in the form 0x...
# Outputs inlined stack
And on whether reporting inlined functions is important or not, at least for C++, which heavily relies on inlining to mitigate abstraction penalty, I'd say it is crucial.
The real issue with DWARF based unwinding/symbolication is that it's really complex on the user experience around it. We at Sentry support stack walking from minidumps, yet we often cannot unwind on Linux platforms on the server because executables and object files are typically not available.
Despite us supporting debuginfod (we're hitting the canonical service today only) we are unable to collect executables/object files from there, making it completely impossible to produce proper stack traces if frame pointers are omitted.
In a world were DWARF unwinding is a thing and people want to use, there has to be an ecosystem of sharing binaries too. This issue is particular bad on Android where there are millions of devices out there with tons of different proprietary system libraries linked in, destroying stacks.
Do you have a specific example of which executables are missing?
There are also other ways to get all the debug symbols but it’s much fiddlier and not nearly as nice as debuginfod. Data’s all there, finding it is harder. You can query the apt index for buildids but only for the currently released package version and not superseded ones.
There were discussions about importing all the history and a way to do it was determined but not sure where the implementation of that has gotten too.
So did they fix that eventually or is everyone just oblivious?
How I found the problem in 2012: Configuration of profiling tools for C/C++ applications under 64-bit Linux https://doi.org/10.6028/NIST.TN.1790
This is also common for samples in leaf functions.
compiler & tool chain folks tend to think (quite justifiably imo) that this and similar stuff is fine because dwarf allows reconstructing everything perfectly. The problem is just that the user experience of dwarf-based unwinding is poor, because the only implemented method in Linux is sampling the contents of the stack and doing the unwind in post processing.
Having high quality low cost stack straces is important for continuous profiling. ref Knuth.
While DWARF unwind info doesn't use that many bytes, but unfortunately reading and parsing that information is quite expensive.
For that reason I've developed a new unwinder that uses custom unwind information derived from DWARF (https://www.polarsignals.com/blog/posts/2022/11/29/profiling..., previously discussed in https://news.ycombinator.com/item?id=33788794) that runs in BPF. This new compact representation can be binary searched easily and each unwind row has a size of 16 bytes. I am currently working on reducing it down to ~10 bytes.
All the code is fully OSS (Apache 2.0 for userspace and GPL for BPF), and part of the Parca project (https://github.com/parca-dev/parca-agent). We've also given a talk this year in FOSDEM going deeper into how we made it scale for many big processes.
One suggestion: binary search has extremely poor cache behavior, and early versions of the ORC in winder (IIRC) spent considerably more time binary searching the table than actually unwinding.
There are many solutions to this. ORC (IIRC) uses a flat hint table mapping PC -> offset in the table. It’s sparse, so you look up hint[(ip-base) / divisor] and its successor to find a small range of the table to search. (Divisor is set to keep the hint table compact but still limit the main search to something small.). This gives essentially linear time lookups with simple code.
You can also use a B-tree or a similar structure. B-trees are pretty straightforward if you don’t ever need to modify them.
IIRC this gave a substantial speedup.
In our case this is not an issue yet. We split up the unwind tables in chunks of up to ~1MB so we typically have in very few L2 cache misses.
This has to be done once per frame so in my 4 year old i7 processor. There are roughly `2 L2 cache misses (+ few other misses from reading ancillary data structures) * frames`.
We have more work to do regarding benchmarks but I collected some numbers the other day and 90 frames can be walked in less than 500ns (slide 50 https://fosdem.org/2023/schedule/event/walking_stack_without...)
There are more optimisations we have in the works to make our unwinder more efficient, mostly related to fitting more data in the CPU cache and reducing cache misses.
DWARF needs to support every CPU under the sun. Every unwinder on the other hand is CPU-specific. For prodfiler.com's continuous in-production unwinding, we convert DWARF into something compact and fast-to-lookup that is then placed in eBPF maps.
It all works like a charm. We can have our cake (e.g. use RBP as GPR) and eat it too (e.g. use .eh_frame, converted at runtime into a fast-to-lookup format) to do reliable whole-system unwinding in production.
As this will take few years, in the meantime I've developed a DWARF-based unwinder in BPF [0]. Some perf maintainers showed interest in this, so thanks for bringing up the GSoC project idea, didn't occur to me!
In any case, the runtime performance hit of frame pointers is quite high, and since we do have things like DWARF (and maybe ORC someday?), I’d still argue that frame pointers aren’t necessary. It’s nice to have that extra register free!
FWIW, ORC was specifically designed to be efficient, but it was not designed to be future-proof against complex toolchain changes. Since all the ORC tooling is in the kernel, it can evolve together if needed.
(I was a bit involved in the design — I helped optimize the format to reduce cache misses on lookup.)
That's not true at all. It's in some very rare cases. Firefox I think at this point ships with framepointers enabled and so does every M1/M2 mac app and all iOS applications as it's mandatory for the calling convention on Apple.
Phoronix [3] did a test of "-fno-omit-frame-pointer" during the discussion on whether to enable the flag for Fedora, this time on x86-64. They found an average 14% performance hit on a wide variety of benchmarks.
[1] https://www.kernel.org/doc/html/latest/x86/orc-unwinder.html [2] https://lore.kernel.org/all/20170602104048.jkkzssljsompjdwy@... [3] https://www.phoronix.com/review/fedora-frame-pointer/5
Web page: "always-on profiling powered by eBPF technology."
BPF stack traces are gathered using frame pointers:
https://github.com/torvalds/linux/blob/master/kernel/bpf/sta...
https://github.com/torvalds/linux/blob/master/arch/x86/event...
https://lore.kernel.org/lkml/Yz%2FcpNTSacRMh1FK@gmail.com/
Further, precise events are fixed in Linux 6.2:
I built my company's in-house mobile crash reporter ~ 2013, based on experience building a similar system at an earlier startup. At the startup I used Google breakpad on both Android and iOS, doing all the unwinding and symbolication on the backend. iOS at least made this easy because Apple makes dSYMs readily available. On Android, you simply can't get system symbols. So you essentially can't unwind OS symbols on Android.
At current company I used PLCrashReporter on iOS. Unwinding occurs on device. Symbolication on the backend.
I tried everything with Android for native code crashes, starting with breakpad minidumps, then using every available unwinder option on Android: corkscrew, the Android fork of libunwind, the official libunwind, whatever custom unwinder Android eventually wrote. None of them work reliably for native code crashes. And good luck tracing from native code back into the ART frames.
In the end what ending up being most reliable was including the last few thousand lines of logcat (grabbed upon the app restarting after a crash since you can't reliably grab it inside the crash handler). Android's OOB crash handler for some crashes (with recent Android versions) dumps full stacks of every thread including native code and ART frames to logcat. So the crash SDK looks for that in the logcat output and includes it in the report. That at least provides a stack. Symbolicating anything but application frames is still impossible though.
And this isn't even going into esoteric things Android has done over the years just for Chrome like relocation packing:
https://android.googlesource.com/platform/bionic/+/f5e0ba94d...
To this day, I don't understand why both Apple and Google make it so difficult for an application to get access to the stack traces of its own crashes. And no, the reporting built-in to Google Play and iTunes Connect (and Xcode) are not sufficient for large usage apps or companies like mine that have lots of apps with shared SDKs and need to correlate crashes across apps.
Yeah, doing an 8KB memcopy for every profile sample sounds like a lot of overhead. Is DWARF unwinding so slow that that is actually faster?
Virgil doesn't use a frame pointer, and I sort of regret it. It uses custom unwinding information that is used during GC or throwing an exception (i.e. controlled crash). I spent considerable time optimizing both the space and time of that lookup, to the point where it's only 32 bits of metadata per call site and a few dozen instructions to walk each frame. But that was a major, major pain to debug and I found a bug in it at late as last year.
A frame pointer is also required for stack allocation of objects that aren't fully scalar-replaceable. Virgil doesn't do that yet, but aspires to someday.
No. The only reason it works like this is because the upstream Linux kernel has thus far rejected in-kernel dwarf unwinders, but copying the stack is simpler and available / implemented.
The elephant in the room btw is LBR call stacks, but they aren't exposed in the kernel/BPF yet. Userland perf has them and they recently became available on AMD.
> Why not implement your approach and mail it to LKML :-)
because this would still be an in-kernel dwarf unwinder and I would expect an instant reject, and because I am lazy and/or don’t care enough about this problem or linux to work on it. Even if people could be persuaded, I don’t have the interest or temperance to debate this with LKML.
frame pointer = 1 less register on an already set of registers under heavy strain (x86_64). I do envy risc-v with all their registers: even the load-store model of risc-v won't use enough more registers to end up with the same amount of strain as on x86_64.
If I ever have the usage of dwarf, I would build the tables manually only for what I wish to debug?... if it is possible (without the use of specialized assembler directives, because it increase significantly the technical cost of the assembler). That said, does a real, accurate and complete specification of dward exists? Because when I look at the sysv ABI or ELF, what a mess.
X86-64 is not under heavy register pressure strain. That idea is a legacy from x86 (plain, 32b).
x86-64 has the same register count as ARMv7 and few bothered disabling the frame pointer there, even though it’s a load-store architecture.
This makes the case where that one extra register name makes all the difference much rarer, arguably turning it from "I demand a compiler flag" to "Let's just hand-write the machine code for this one very special routine if our performance data suggests it's worth it".
† Internally a modern CPU has far more actual register, to enable a feature called "register renaming". But we can only talk about them using their canonical names, and x86-64 adds eight more of those.
But i agree the impact of preserving frame pointers is generally quite small and doesn’t often actually need mitigation - on amd64 there’s not much impact from losing 1 more of 16 arch registers.
https://www.agner.org/forum/viewtopic.php?t=41
Intel Alderlake has performance events for tracking it:
https://github.com/intel/perfmon/blob/974c69919b2a9dfd8278cf...
But even before this you had store to load forwarding on x86. I'm not saying you have, but before inventing a performance problem it is worth spending time trying to diagnose it with thorough profiling (e.g. [1]). The Fedora frame pointer patch did a thorough performance analysis and performance will be revisited again. Unfortunately there are a lot of arm chair performance experts who haven't spent time looking into the details.
[1] https://perf.wiki.kernel.org/index.php/Top-Down_Analysis
It would be interesting to see comparison to Intel LBR.
Also would be nice to know how profiling unwinding is done on Windows (maybe someone knows how to summon Bruce Dawson).
AFAIK frame pointers work fine for unwinding on aarch64. And on aarch64 the gcc default is not to omit frame pointers and IIRC when the default was switched at some point it was treated as a bug and reverted (not sure if required in the ABI or just strongly preferred by the community). So IME generally unwinding with frame pointers on aarch64 works more often than on amd64 since you don’t have to recompile the world.