DWARF-Based Stack Walking Using eBPF
polarsignals.com
polarsignals.com
I'm curious what they have to say about complexity/necessity of interpreting all of DWARF. cargo-trace (an neat and conceptually similar but abandoned project, I think) [1] says:
> It can be empirically determined that almost all dwarf programs consist of a single instruction and use only three different instructions. rip+offset, rsp+offset or *cfa+offset, where cfa is the rsp value of the previous frame. The result of the unwinding is an array of instruction pointers.
Do you find this to be true? Is more complex interpreting of DWARF necessary?
And in the lkml thread linked from the article, Linus is extremely pessimistic about DWARF unwinding, [2] I'm sure not without justification. He's talking about kernel stacks, and I think the trade-off is different when you're trying to profile existing userspace applications and libraries compiled and implemented however, but nonetheless I'm curious to hear the authors say how applicable they think his points are.
The authors' pointer to .ctf_frame is also a very interesting development in this space. Not sure how long that will take to be widely usable (assuming it goes through at all).
This project looks interesting and as you mention it seems conceptually similar! I would agree with that quote, generally speaking, but I think it really depends on a binary to binary basis.
Some binaries outsource most of the work to dynamic libraries. Unfortunately, DWARF expressions are typically emitted for these program counter ranges, so it's desirable to at least implement a subset of expressions [0].
Even if that's not the case, we want to produce profiles that are as accurate as possible :)
You are totally right, they were discussing kernel stacks where stakes are higher as it needs to work perfectly, otherwise kernel live patching would not reliably work, among others. The kernel has now some unwind table format, that can be used in x86_64, called ORC [1].
That being said the parser for DWARF would still have to live in the kernel, and I am not sure if kernel devs would like to accept such a patch.
Ideally we would transition to an unwind-specific format for user-space (something like ours, for example) and perhaps have a suitable unwinder in the kernel, rather than having to implement it in a BPF program. This is something we are considering for the future, but it's not free from problems (increased executable size, redundant unwind information, etc). But this is exactly why we wanted to have a conversation with the communities interested in this work!
[0]: https://github.com/parca-dev/parca-agent/pull/1058/commits
I'm just an interested user rather than someone who has an ownership stake in any major distribution, language, library, or application, but fwiw:
I'd love for every binary/library to embed enough information to cheaply unwind during profiling [edit: and symbolize shortly afterward], in one simple format, so that this sort of profiling tool Just Works, as well as backtraces generated by the program itself (e.g. Rust's panics). I'd prefer it support inlining well (so ideally not just turning on frame pointers everywhere but that'd still be a huge improvement over the status quo). As you know, this is all a complete mess now, and I hate that. I think a reasonable amount of space overhead for this is fine. I want to be able to profile pre-packaged applications and my own Rust applications that use some C libraries without hassle. And have profiles written in a format that I can ship to another machine without trouble reading the symbols there or concern about excessive sensitive information. All stuff you've touched on. I would consider it a genuine miracle if the parties involved could all get behind this.
Full DWARF information, e.g. Rust's debug = 2 [1] (to be clear: my understanding is this is more or less to allow debuggers to print variable contents reasonably well?) is another matter. Seems like that adds a huge amount of bloat and is more rarely used. I like split debuginfo. As long as there's an easy way to get it on demand via a debuginfod service and/or installing an additional package, it's fine.
Definitely! We hope to be able to change this. There's the .ctf_frame format [0] that could be used too. While its design goals are very much aligned to ours, implementing a reader for this format in BPF will be complicated.
> and symbolize shortly afterward
Definitely, I think that C Type Format (CTF) [1] could be a candidate here. Another possibility would be to get BTF (BPF Type Format) [2] working in userspace. While it wouldn't cover everything that DWARF deals with, it might be a reasonable tradeoff for symbolization.
FWIW both in Polar Signals and Parca (our OSS offering) we resolve to async symbolization done in the server, as it's very expensive to do and we want to reduce load where the Agent runs.
[0]: https://gcc.gnu.org/wiki/cauldron2022talks
[1]: https://lwn.net/Articles/795384/#:~:text=The%20Compact%20C%2....
AFAICT from some searching this morning, CTF is implemented in the GNU toolchain (compiler -> debugger) but not at all in LLVM? so seems like it'd be a while before this really happens even if everyone gets behind that format.
> FWIW both in Polar Signals and Parca (our OSS offering) we resolve to async symbolization done in the server, as it's very expensive to do and we want to reduce load where the Agent runs.
Makes total sense for your cluster-wide always-on profiling. I've worked some with GWP [1] and Google Cloud Profiler, and they similarly defer/offload the symbolization to a dedicated service. But in a small-scale setting for e.g. a Rust std::backtrace::Backtrace with an Error or panic, I generally want to print a nice symbolized version in-process shortly after capture (or never). For small-scale on-demand profiling, similarly I likely want to symbolize soon after, although probably out-of-process.
You are right! Hopefully these formats will become standard and implemented in more toolchains. My worry is that there seem to be several "competing" formats for a more compact DWARF debug (as opposed to unwind) information. I hope this doesn't lead to more fragmentation of the ecosystem.
Definitely! I assume you work at Google, so most of your binaries probably have some crash handlers set up already, right? I find this very useful, and wish it were more commonplace. I really like Folly's implementation of this idea [0] that just requires a single line of code: `folly::symbolizer::installFatalSignalHandler()`
I did for a really long time. At a startup now.
> so most of your binaries probably have some crash handlers set up already, right?
Yes, there was nice instrumentation there too. All google3 binaries did something like InitGoogle() that set off commandline flag parsing, signal handler installation, log hooks, mlock/huge page setup, etc.
- undefined - same value - offset(N) - val_offset(N) - register(N)
I've never come across expression(E), val_expression(E), or architectural. But you definitely do need the above in the common cases.
More generally, I'm kinda confused by that quote, I think the author may be conflating DWARF expressions and stack unwinding a bit?
What I think they might have been getting at is that with DWARF expression evaluation [1] in particular (i.e. not just stack unwinding), I've never even seen +80% of the opcodes I've implemented in the wild across several programming languages and compilers. I also left about 1/4 of them unimplemented and I've never had an issue. The intention of the DWARF spec writers was to provide folks with a stack machine that was Turing-complete, but in practice, yeah, nobody really takes advantage of it because there's not really a need.
[0] https://dwarfstd.org/doc/DWARF5.pdf (section 6.4) [1] https://dwarfstd.org/doc/DWARF5.pdf (section 7.7)
I suspect they only cared about / looked at the portion of DWARF information needed for stack unwinding. I'd read the quote with that implicit qualifier after "almost all dwarf programs".
We see DWARF expressions such as `DW_CFA_def_cfa_expression` on the regular. See the "Test Plan" section and commit messages of the PR that introduced support for this particular opcode, as well as the simple executable that shows this opcode [0] and its printed unwind table [1]
[0]: https://github.com/parca-dev/parca-agent/pull/1058
[1]: https://github.com/parca-dev/testdata/blob/7f9206570a743206f...
I've never encountered a DW_CFA_def_cfa_expression before in the wild, which compilers(s) are you seeing that in out of curiosity? I see Parca supports many more languages/compilers than I do. I do support that opcode (and all the other CIE opcodes) in my debugger, I just have yet to find a compiler that generates it.
Side note, just looked through the Parca marketing materials, it looks awesome! Excited to try it out on some of my stuff and see what I can find.
Statistically speaking, a profiler has more chances of bumping into program counters (PCs) that fall in ranges defined by a larger set of DWARF opcodes. We run at 100Hz, which can quickly yield a large number of different program counters, while I assume that most debugging sessions won't hit that many different PCs.
I'm using Fedora 36 which ships `gcc (GCC) 12.2.1 20220819 (Red Hat 12.2.1-2)`
> I've been writing a debugger from scratch for the past few months
Sounds fun! Are you planning on writing about this? I am sure there would be many people interested in reading about this topic!
Either way feel free to reach out at javier @ my company's domain if you want to discuss the DWARF opcodes thing further!
I'm not sure if I plan to write about it, it doesn't feel like I'm uncovering anything that anyone can't go look up pretty easily. I've been building it mostly because I'm frustrated with all the existing tools out there, save for RemedyBG (which is awesome, but Windows-only, and I'm only on Windows every so often). However, I'm still quite a ways off from being a reasonable daily driver!
[1] https://bugzilla.mozilla.org/show_bug.cgi?id=1157194#c14
[2] https://github.com/mstange/framehop/blob/6777199dd0c2c1b3768...
There definitely is a need for better DWARF information, be it with new opcodes or not. It's just that generating them has not been a priority for compilers.
That said, we should still try to convince people!
BTW, I'm a big fan of your work, thanks for Flask and Jinja!
[0]: https://fedoraproject.org/wiki/Changes/fno-omit-frame-pointer
[1]: https://lists.fedoraproject.org/archives/list/devel@lists.fedoraproject.org/thread/OOJDAKTJB5WGMOZRXTUX7FTPFBF3H7WE/
See for instance Apple's ARM64 calling convention: https://developer.apple.com/documentation/xcode/writing-arm6...
"The frame pointer register (x29) must always address a valid frame record. Some functions — such as leaf functions or tail calls — may opt not to create an entry in this list. As a result, stack traces are always meaningful, even without debug information."
Generally, the “compile with frame pointers” request is a bit underspecified on x86-64. For example, the perf trampoline that is cited as the reason why future Python versions are going to use frame pointers itself does not have a frame pointer. (It does not clobber it, either, but backtraces through it will skip a frame.) Similarly, if you just compile glibc with frame pointers without patching a handful of assembler files, then for typical workloads, 5% to 10% of your samples will have an incomplete backtrace because the immediate caller of glibc string functions is not recorded (they don't have a frame pointer, either).
I expect this x86-64 debate will be obsolete Really Soon Now because everyone will simply copy out the shadow stack on every sample. It's even faster than frame pointer traversal because it's just an array copy. We are still looking at making DWARF backtraces a bit faster (or even the more complex unwinding case), but I doubt that this work will be impactful, given the politics involved. The shadow stack will have some performance impact, too, but it can be switched off on a per-process basis if necessary.
I watched a presentation recently by one of the core BPF contributors, in which they paint it as a safer, extended version of C:
https://www.youtube.com/watch?v=K08YCgALHDo
Is there any reason why you wouldn't want to use this to write regular, user-land applications instead of C? Could you?
(I don't know much about BPF in general)
I think this would be cool. Have you considered asking Alexei directly?
Didn't want to clutter up the mailing list with noise so I didn't reply:
https://lore.kernel.org/bpf/Y3BQGgcCMaSptEFJ@google.com/T/#t
That being said, very recently support for bounded loops landed [0]. It's very exciting and useful, and I've seen it reduce verification times significantly, but we can't use this yet as it requires kernel 5.3 or greater, and we would like to support as many users as possible!
[0]: https://lwn.net/Articles/877062/
[1]: https://github.com/iovisor/bcc/commit/38304256c49a02aecbf78f...
The way you build serious systems with BPF is that you couple a tiny straight-line BPF kernel that generates events with a userland program that consumes the events and does interesting stuff.
In the talk, he mentions adding higher-level constructs to C like lists and RB-trees that are also concurrently-safe(!!) which seem just massive to me.
It'd be stellar to be able to program in a safe C subset with some higher-level affordance like this.
There's a bunch of data structures available to BPF programs, because they can call "helpers", which are just ordinary C functions. There are concurrent semi-durable key-value stores of varying types (eBPF "maps"). These aren't written in BPF-C; they're just kernel code that BPF gets to call.
Adding new helpers is not nontrivial; you can't just load them into your kernel and call them; they're part of the kernel API.
That’s not to say that the verifier isn’t limiting and at time difficult to deal with, but I find it less of a limitation in practice than it seems at first. Much like rust’s borrow checker I do think it takes a change in mindset.
//edit
Turns out being thoughtful about this when writing the code is also helpful for performance reasons as things like loops can be unrolled which can have significant performance gains.
What happens in the case of JIT or FFI? I think I've only ever seen the Python profiler, scalene[0], handle these cases.
FFI should work as it's typically a dynamic library that's loaded at runtime. If said library has unwind information, which most compilers add it by default as it's part of the ABI (right now we support unwind information stored in the .eh_frame ELF section).
JIT'd code is not supported yet. This is something that we are already working on, though!
Sad that I am delighted by this. It seems most articles these days obfuscate their story.
We would have to modify the BPF code to handle saved return addresses in arm64, which as far as I am aware are not defined by the ABI, so they might be at any offset from the previous frame's stack pointer (what DWARF calls CFA).
There's (at least) these other things that we might want to look into, such as:
- split stacks
- pointer authentication
- unwind tables stored in a different ELF section
As you mention that you are looking into loosening the minimum kernel requirements, what is currently the primitive(s) that is dictating the minimum required version? And how do you plan to sidestep that?
Good question! We are building atop the incredible job that the BPF community does. BPF is a restricted environment [0], among others, the stack size is very small, programs have to be proved to finish, and there's no access to arbitrary kernel function.
We've done most of the work to loosen the minimum required kernel, sorry if that wasn't clear. The minimum supported kernel is 4.18.
More context, for those interested:
In order to provide an API to interact with the rest of the kernel, we use BPF helpers, which are like a library (sorta "syscalls") functions that BPF programs can make.
Not every BPF helper is available in a given kernel. The BCC project has a comprehensive and up-to-date list of the different helpers and other features and their introductory commit [1].
The minimum kernel that we can support is then decided by the most modern helper or feature we use. In our case, the most modern features we require are:
- BPF tail calls: since 4.2
- BPF Type Format (BTF): since 4.18
[0]: https://www.kernel.org/doc/html/latest/bpf/bpf_design_QA.htm...
[1]: https://github.com/iovisor/bcc/blob/master/docs/kernel-versi...
As @brancz mentioned, Delve uses DWARF unwind information to produce backtraces (they are stored in the .debug_frame section for Go).
You are right, Go enabled frame pointers for all architectures as of 1.17 [0]. This is enabled to allow profilers to work well, without having to use to techniques such as the one we describe in our post.
When it gets funny is that there's `gopclntab`, a 3rd option in Go to unwind stacks, used by `panic` and I believe other parts of the runtime. If you are interested in more details, Felix Geisendörfer's repo contains way more details [1]
[0]: https://go.dev/doc/go1.17
[1]: https://github.com/DataDog/go-profiler-notes/blob/main/stack...
Funny that you mentioned perfect hashing, I thought about this, but didn't go for this approach as it would have too many drawbacks for our use-case:
- It would further increase the complexity of the unwinder, which is already not trivial. Ideally, we would like to reduce the surface area of things that can go wrong.
- Implementing perfect hashing in BPF might be tricky for several reasons. First it might take quite a bit of precious instructions, but also, it would force us to ship a compiler to generate the BPF code in the fly rather than shipping it pre-compiled. We really want to avoid this.
- Last, it would force us to generate entries for every program counter, while thanks to using binary search we can omit redundant entries. DWARF expressions would suffer from a similar issue.