9 ms·
DWARF-Based Stack Walking Using eBPF
- jzelinskie 4y agoThis is super awesome work and a great technical explanation of a very deep topic. What happens in the case of JIT or FFI? I think I've only ever seen the Python profiler, scalene[0], handle these cases. [0]: https://github.com/plasma-umass/scalene https://github.com/plasma-umass/scalene
- javierhonduco 4y agoThanks! 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!
- brancz 4y agoLooks like there is another active submission: https://news.ycombinator.com/item?id=33788883 https://news.ycombinator.com/item?id=33788883 (maybe they can be merged since they were submitted so close to each other?)
- dang 4y agoWe merged them hither since the OP was the original post.
- pst 4y agoGiving teams more insights into their apps at runtime without requiring changes to the apps is as close as one gets to a superpower.
- javierhonduco 4y agoAgreed! I'm very happy to see that we are getting to the point where engineers that don't work at big tech companies can get these kind of insights, too.
- mzs 4y agorepo: https://github.com/parca-dev/parca-agent https://github.com/parca-dev/parca-agent
- buggy6257 4y agoI clicked this wondering if someone had made some fantastic new contraption using Dwarf Fortress. Still a very interesting read, but slightly disappointed :)
- teddyh 4y agoIt’s “DWARF-based”, not “Dwarf-Based”. No diminutive humanoids, fantastical or otherwise, were involved.
- s-urbaniak 4y agoThis is a great tool to have profiling data for "-fomit-frame-pointer" compiled code! Question: How hard is it to add ARM architectures?
- tdullien 4y agoFWIW, the prodfiler.com agent does the same, and we have experimentally working ARM unwinding, including high-level language stuff (Python, Java) mixed with native, on ARM, too.
- javierhonduco 4y agoWe don't know yet, but we are planning to start this work soon. In theory the unwind tables should be very similar thanks to still following the DWARF spec. 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
- kaeso 4y agoNice post @javierhonduco, really interesting read! 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?
- tdullien 4y agoFWIW, the prodfiler.com agent has had no-symbol stack unwinding since summer 2021, and a minimum kernel version of 4.15 :-), and happens to have a lower footprint than the solution discussed here.
- javierhonduco 4y agoThanks! :) 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.html https://www.kernel.org/doc/html/latest/bpf/bpf_design_QA.htm... [1]: https://github.com/iovisor/bcc/blob/master/docs/kernel-versions.md https://github.com/iovisor/bcc/blob/master/docs/kernel-versi...
- scottlamb 4y agoAre the authors here? Thanks for this! I'm always thrilled to see advances in profiling tools. 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). [1] https://github.com/dvc94ch/cargo-trace https://github.com/dvc94ch/cargo-trace [2] https://lkml.org/lkml/2012/2/10/356 https://lkml.org/lkml/2012/2/10/356
- javierhonduco 4y agoAuthor here! 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 https://github.com/parca-dev/parca-agent/pull/1058/commits [1]: https://lwn.net/Articles/728339/ https://lwn.net/Articles/728339/
- gavinray 4y agoI have a tangential question, more about BPF in general: 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 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)
- javierhonduco 4y ago(this talk is great!) I think this would be cool. Have you considered asking Alexei directly?
- gavinray 4y agoI did email the BPF kernel mailing list, they directed me to two user-land (user-space?) implementations of BPF but didn't say much about what "user-space BPF" meant. 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 https://lore.kernel.org/bpf/Y3BQGgcCMaSptEFJ@google.com/T/#t
- hawski 4y agoAFAIU BPF does not have loops as it is designed to be assured the execution has an end.
- javierhonduco 4y agoThat's right! There's no "traditional" loops as programs have to be proved to terminate at some point. 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/ https://lwn.net/Articles/877062/ [1]: https://github.com/iovisor/bcc/commit/38304256c49a02aecbf78f2fdc4b86d95eb8df9f https://github.com/iovisor/bcc/commit/38304256c49a02aecbf78f...
- 4y ago
- donalhunt 4y agoDupe of https://news.ycombinator.com/item?id=33788883 https://news.ycombinator.com/item?id=33788883 ?
- the_mitsuhiko 4y agoI am going to start positing this into every discussion about this topic now: can we as an industry start not omitting frame pointers? It’s not so significant (maybe puts us back three months in hardware advances) but everybody greatly benefits from that.
- brancz 4y agoCould not agree more! Unfortunately, I don't think we'll realistically be able to convince everyone, and even if we did convince everyone to have frame pointers tomorrow, it would still take years to take effect. So for the foreseeable future we'll still need things like this, even if I wish we didn't. That said, we should still try to convince people!
- javierhonduco 4y ago100% this. Disabling frame pointers is not worth it in my opinion. Hindering debugging and profiling is a massive regression. It's one of these historical (due to x86 having fewer registers) and short-term thinking changes that have unfortunately stayed with us. I'm optimistic that this can change but it will take a while. BTW, I'm a big fan of your work, thanks for Flask and Jinja!
- davemarchevsky 4y agoThere is currently a Fedora proposal to add -fno-omit-frame-pointer to default compilation flags [0](mailing list discussion: [1]). [0]: https://fedoraproject.org/wiki/Changes/fno-omit-frame-pointer [1]: https://lists.fedoraproject.org/archives/list/devel@lists.fedoraproject.org/thread/OOJDAKTJB5WGMOZRXTUX7FTPFBF3H7WE/ edit: whoops, this was already mentioned in the blog post. Should read before commenting :)
- nemetroid 4y agoBy now (but not at the time of posting), a rejected Fedora proposal.
- simscitizen 4y agoFrame pointers are enabled by default on macOS and iOS and I can't understand why they aren't enabled by default elsewhere. It just makes it so much easier to debug and profile things. See for instance Apple's ARM64 calling convention: https://developer.apple.com/documentation/xcode/writing-arm64-code-for-apple-platforms 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."
- archivator 4y agoI'd love to see a size comparison of the DWARF encoding vs the binary search map. I have a strong suspicion that there's a neat perfect hash solution to this problem - perfect hashes can encode keys in single digit #bits, and you get faster lookups.
- javierhonduco 4y agoLet me check! I don't our approach to be significantly more compact than DWARF's. DWARF is very compact despite being so much more expressive. 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.
- gumby 4y agoI clicked because I was puzzled why anyone would want to use eBPF to do this. And then the first sentence of the article said why! Sad that I am delighted by this. It seems most articles these days obfuscate their story.
- andreimatei1 4y agoVery nice work! It seems that Delve is used for inspiration and development, but Golang code is always compiled with frame pointers, I think. Is that right?
- brancz 4y agoThat's right, but Delve also needs to use DWARF to walk stacks that involve CGO, where it can't rely on frame pointers being present.
- brancz 4y agoQuick correction, actually Delve uses DWARF unwind information for every code location, including those from Go, even if frame pointers are present.
- javierhonduco 4y agoThanks! 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 https://go.dev/doc/go1.17 [1]: https://github.com/DataDog/go-profiler-notes/blob/main/stack-traces.md https://github.com/DataDog/go-profiler-notes/blob/main/stack...