The untold story of BPF

This talk will uncover for the first time the true origin of ‘Extended Berkley Packet Filter’. It would be fascinating for aspiring and expert open source developers to discover BPF’s path into one of the most sophisticated and challenging parts of software stack. Innovating in the large projects like GCC, LLVM, Linux Kernel is challenging. The story of BPF is an example and a call to challenge what’s possible. Its past is a clear vision of what’s coming next.

Alexei Starovoitov

Transcript

1. The story of BPF A practical guide to land patches
2. • What BPF stands for? • Does it matter ? • The name given to an instruction set 30 years ago by Steven McCanne and Van Jacobson.
3. • Little they knew that in 2011 a startup decides to revolutionize Software Defined Networking.
4. • Physical -> Virtual • Servers -> VMs • Networking gear -> virtual routers, switches, firewalls • Virtual Machine • Technology: hypervisor • KVM, QEMU • Virtual firewall, Virtual Router, Virtual Switch • Technology: iovisor
5. One physical server: • 5 VMs • 1 router • 2 switches • 5 firewalls
6. Traditional approach • VM -> kvm.ko • Virtual router -> vrouter.ko • Virtual switch -> vswitch.ko • Virtual firewall -> vfirewall.ko
7. PLUMgrid’s solution v1 • iovisor.ko • switch, router, firewall – binary blobs of x86 code • pushed to a host by a remote controller • Including 3rd party NAT, packet captures, etc
8. • What can go wrong? • After 4Gbyte of networking traffic the kernel would crash • 32-bit overflow ? • Race condition ?
9. • What can go wrong? arch/x86/Makefile: KBUILD_CFLAGS += -mno-red-zone
10. PLUMgrid’s solution v2 • Verify x86 code • The verifier was born.
11. • Verification pain points with x86 asm • Lots of ways to compute an address. • Lots of memory access instructions. • Solution: reduced x86 instruction set. • Hack GCC x86 backend. • The first iovisor.ko had the verifier and no JIT.
12. PLUMgrid’s solution v3 • New instruction set (x86 like) • GCC backend that emits binary code • iovisor.ko • The verifier for this instruction set • JIT to x86 • No interpreter
13. How to upstream iovisor.ko ? • Talk to key people when possible • New instruction set is scary to compiler folks • Even scarier to kernel maintainers • Solution: make it look familiar
14. Make it look familiar • Is there an instruction set in the kernel with similar properties? • BPF, iptables, netfilter tables, inet_diag • Make new instruction set look as close as possible to BPF • Reuse opcode encoding and 8-byte size of insn • Call it ‘extended’ BPF
15. Next steps • Read netdev@vger mailing list for 6 month • Understand the land • Identify key people • And post the jumbo patch? No.
16. Build reputation • Find lockdep report in your area of interest.
17. My 1st kernel patch: Move module_free() of x86 JITed memory into a worker.
18. Keep building reputation… my kernel commit #5
19. Finally post eBPF patchset Did it work?
20. Finally post eBPF patchset Nope. It was rejected.
21. What is the biggest maintainer’s concern? UAPI !
22. Need a plan B for eBPF Add eBPF without exposing it in UAPI How?
23. Need a plan B for eBPF Add eBPF without exposing it in UAPI Answer: Make existing code faster
24. Rewrite existing BPF interpreter Thankfully it was easy to make it 2 times faster. 10% of the speedup came from eBPF instruction set itself. 90% of the speedup from jump-threaded implementation. That’s how ‘internal BPF’ was created.
25. Need to disambiguate two BPFs. Daniel Borkmann came up with a name ‘classic BPF’. The state of BPF in May 2014: • cBPF converter to iBPF (internal BPF) • Interpreter that runs iBPF • x86, sparc, arm JIT compilers from iBPF to native code eBPF doesn’t exist yet. There is no verifier either.
26. Where to apply iBPF ‘engine’ ? The concepts of the verifier, maps, helpers were proposed. Programs suppose to run from netif_receive_skb. The networking use case still struggles. Arguments against: - [ei]BPF instruction set is not extensible. Should be using TLV ? - u8 opcode looks small. eBPF 2.0 will be coming ? - The verifier is not supported by static analysis theory. - It bypasses networking stack.
27. If the mountain will not come to Mohammed… Strategy: Compromise on networking, pivot eBPF into tracing. Strategy: Make it look familiar. F - filter. Proposal to ‘filter’ perf events. Reuse verifier, maps, helpers concepts, but instead of network stack execute programs from perf events and kprobes.
28. Strategy: Make existing code faster. Demonstrate that BPF tracing ‘filter’ is faster than predicate tree walker. Demonstrate that BPF TC ‘classifier’ is faster than TC u32 classifier. Sad trade-off: clean design vs upstreamability.
29. Finally on September 26, 2014
30. eBPF is learning to walk. 89aa075832b0 (net: sock: allow eBPF programs to be attached to sockets, 2014-12-01) e2e9b6541dd4 (cls_bpf: add initial eBPF support for programmable classifiers, 2015-03-01) 2541517c32be (tracing, perf: Implement BPF programs attached to kprobes, 2015-03-25)
31. Are we done?
32. Are we done? Kernel was just the beginning. Landing new backend in LLVM was just as difficult.
33. LLVM community • Most developers have direct write access • Anyone can revert anyone else’s commit • s/MAINTAINERS/CODE_OWNERS.TXT/ • Back then LLVM was using SVN • Phabricator for diffs • C++ in CamelStyle
34. LLVM community • No UAPI concerns • Compiler internals are changing a lot • Backward incompatible backend changes is not a concern • Kernel UAPI doesn’t justify or restrict LLVM choices • Continuous integration and testing is mandatory • Build bots run tests right after diff lands • Backends have to contribute build bots • Many operating systems • Approved diffs might get reverted and re-landed many times • Monthly meetup at Tied House, Mountain View, CA
35. LLVM BPF backend Differential Revision: http://reviews.llvm.org/D6494 llvm-svn: 227008 llvm/CODE_OWNERS.TXT | 4 + llvm/include/llvm/ADT/Triple.h | 1 + llvm/include/llvm/IR/Intrinsics.td | 1 + llvm/include/llvm/IR/IntrinsicsBPF.td | 22 +++++ llvm/lib/Support/Triple.cpp | 8 ++ llvm/lib/Target/BPF/BPF.h | 22 +++++ llvm/lib/Target/BPF/BPF.td | 31 ++++++ llvm/lib/Target/BPF/BPFAsmPrinter.cpp | 87 +++++++++++++++++ llvm/lib/Target/BPF/BPFCallingConv.td | 29 ++++++ llvm/lib/Target/BPF/BPFFrameLowering.cpp | 39 ++++++++ llvm/lib/Target/BPF/BPFFrameLowering.h | 41 ++++++++ llvm/lib/Target/BPF/BPFISelDAGToDAG.cpp | 159 ++++++++++++++++++++++++++++++ llvm/lib/Target/BPF/BPFISelLowering.cpp | 642 +++++++++++++++++++++++++++++++++++++++++ ... llvm/lib/Target/LLVMBuild.txt | 2 +- 69 files changed, 4644 insertions(+), 1 deletion(-) Proposed in Dec 2014
36. http://reviews.llvm.org/D6494 took 2 month to land in Jan 2015 as experimental backend.
37. To graduate BPF backend from experimental status • It has to have users • It needs more than one developer • Developers must help with tree wide refactoring • Build bot
38. BPF backend in GCC • Emits BPF byte code directly. Upstream blocker. • Unlike LLVM GCC doesn’t have integrated assembler. GCC has to emit plain text • Would have to make libbfd/gas/ld work • Being lazy as an upstream strategy sometimes works too • In 2019 Oracle GCC folks implemented everything
39. Steps that did NOT help to land patches • Present at the conferences • Describe amazing future
40. Summary: Strategies to land patches • Learn the community • Understand maintainer’s concerns • Build the reputation • Make new ideas look familiar • Make existing code faster • Split big ideas into small building blocks • Be prepared to compromise
41. Thank you What questions do you have?
42. Slide 42