Upgrade to Pro — share decks privately, control downloads, hide ads and more …

eBPF's Abilities and Limitations: The Truth

eBPF's Abilities and Limitations: The Truth

Presented with John Fastabend at KubeCon EU 2024 in Paris

eBPF is proving to be a great platform for cloud native infrastructure tooling, with several CNCF projects leveraging it to implement networking, security and observability capabilities from within the kernel. But as with any new technology, there are various myths and uncertainties circulating about it in the community, particularly around its limitations: you might hear that it’s not Turing complete, that it can’t be used for anything that involves state, or that it can’t be used to parse Layer 7 protocols. In this talk we’ll disprove all these rumors with demonstrations including:

* Looping in eBPF
* Leveraging maps for state
* An eBPF implementation of a Turing machine equivalent

This doesn’t mean eBPF is the right hammer for every nail; using the Cilium project as an example we’ll discuss why not every feature is implemented in the kernel. (Yet?)

Liz Rice

April 03, 2024
Tweet

More Decks by Liz Rice

Other Decks in Programming

Transcript

  1. eBPF’s Abilities and Limitations: The Truth Liz Rice | @lizrice

    Chief Open Source Officer, Isovalent Emeritus Chair, CNCF TOC CNCF & OpenUK boards John Fastabend | @jrfastab Principal Software Engineer, Isovalent
  2. Are these statements true? “Implementing HTTP/2, or terminating TLS, are

    simply not possible in eBPF: they’re too complex” “eBPF is not Turing complete” Hint: these were all said by people who don’t work on eBPF
  3. Turing completeness This is not a computer science class Can

    we use eBPF for arbitrarily complex tasks? • Ability to process arbitrarily large amounts of data • Unbounded loops • Memory for storing state
  4. Turing completeness Turing complete examples: All the common general purpose

    programming languages. C/C++, Java, Python, Go But also lots of other less practical (for programmers) environments. One Instruction Set Computer (OISC), X86 MMU, Conway’s Game of Life Some domains benefit from bounded computation: An HTTP parser guaranteeing no packet can DDOS the environment Syscall/Kernel tracing DSL with bounded/enforced maximum overhead
  5. Conway’s Game Of Life This is not a computer science

    class Can we use eBPF for Conway’s Game Of Life? From playgameoflife.com
  6. userspace kernel app event system calls eBPF program 🔍 verifier

    eBPF verifier core safety principles 1. Read memory only with correct permissions 2. All writes to valid and safe memory 3. Valid in-bounds and well formed control flow 4. BPF execution on-cpu time is bounded: a. program sleeps b. schedules callback, iterators, next event c. program completes 5. Acquire/Release and reference count semantics a. Locks, RCU, socket ref, …
  7. eBPF game of life program static int do_game(void) { copy_cellmap();

    next_generation (); send_update(); return run_next(2); } int nextX(uint cell) { uint x, count; uint k = 0; struct cellmap *m; char *cellp; m = lookup_elem(&b, &k); if (!m) return -1; cellp = (char *)m->temp; for (x = 0; x < W; x++) { if (cell_off > MAX) continue; cell++; } return cell; } int next_generation(void) { uint cell; uint y; cell = 0; for (y=0; y < H; y++) cell = nextX(cell); return 0; }
  8. Are eBPF programs limited to a few instructions? Verifier has

    limits to ensure verifier completes in reasonable amount of time: 1. (sub)program Instruction limit 2. Verifier step limit a. DFS traversal to check program DAG, unbounded loops, and jumps 4.14 4.19 5.4 5.15 6.1 unpriv 4096 4096 4096 4096 4096 privilege 4096 4096 1M 1M 1M
  9. Consider 1M instruction limit for ‘modern’ stable kernels: • Doom:

    ~<100k instructions • Envoy: ~15M instructions • Clang: ~26M instructions 4.14 4.19 5.4 5.15 6.1 unpriv 4096 4096 4096 4096 4096 privilege 4096 4096 1M 1M 1M Are eBPF programs limited to a few instructions?
  10. Consider 1M instruction limit for ‘modern’ stable kernels: • Doom:

    ~<100k instructions • Envoy: ~15M instructions • Clang: ~26M instructions 4.14 4.19 5.4 5.15 6.1 unpriv 4096 4096 4096 4096 4096 privilege 4096 4096 1M 1M 1M 1M << 15M Stay tuned, we will address this shortly But what about loops John? Are eBPF programs limited to a few instructions?
  11. Can eBPF programs only jump forwards? No loops → write

    out instructions several times → unroll compiler directive Basic math shows this can be problematic: 64 X 64 Grid ->4096 “cells” to visit each iteration 1M / 4K -> 250 iterations before 1M limit int next_generation(void) { uint cell; uint y; cell = 0; for (y=0; y < H; y++) cell = nextX(cell); return 0; }
  12. No loops → write out instructions several times → unroll

    compiler directive Basic math shows this can be problematic: 64 X 64 Grid ->4096 “cells” to visit each iteration 1M / 4K -> 250 iterations before 1M limit Not even an approximation of a forever tape !!! int next_generation(void) { uint cell; uint y; cell = 0; for (y=0; y < H; y++) cell = nextX(cell); return 0; } Can eBPF programs only jump forwards?
  13. No loops → write out instructions several times → unroll

    compiler directive → loops Verifier ensures loops terminate in finite steps → bpf_loop(u32 nr, void *callback, void *ctx, u64 flags) Insert “intrinsic” loop logic verifier inserts counter int next_generation(void) { uint cell; uint y; cell = 0; for (y=0; y < H; y++) cell = nextX(cell); return 0; } If we bound our loops or use bpf helper to insert bounds, we can loop for (y=0; y < H; y++) Can eBPF programs only jump forwards?
  14. No loops → write out instructions several times → unroll

    compiler directive → loops Verifier ensures loops terminate in finite steps → bpf_loop(u32 nr, void *callback, void *ctx, u64 flags) Insert “intrinsic” loop logic verifier inserts counter 4.14 4.19 5.4 5.15 6.1 Loops unroll unroll loop* loops bpf_loop int next_generation(void) { uint cell; uint y; cell = 0; for (y=0; y < H; y++) cell = nextX(cell); return 0; } Can eBPF programs only jump forwards?
  15. No loops → write out instructions several times → unroll

    compiler directive → loops Verifier ensures loops terminate in finite steps → bpf_loop(u32 nr, void *callback, void *ctx, u64 flags) Insert “intrinsic” loop logic verifier inserts counter 4.14 4.19 5.4 5.15 6.1 Loops unroll unroll loop* loops bpf_loop 6.9 may_goto int next_generation(void) { uint cell; uint y; cell = 0; for (y=0; y < H; y++) cell = nextX(cell); return 0; } Can eBPF programs only jump forwards?
  16. Are eBPF programs limited to a few instructions? Consider 1M

    instruction limit for ‘modern’ stable kernels: • Doom: ~<100k instructions • Envoy: ~15M instructions • Clang: ~26M instructions 4.14 4.19 5.4 5.15 6.1 privilege 4096 4096 1M 1M 1M 1M << 15M But what about loops John? Verifier has limits to ensure verifier completes in reasonable amount of time: 1. (sub)program Instruction limit 2. Verifier step limit
  17. Are eBPF programs limited to a few M++ instructions? Verifier

    has limits to ensure verifier completes in reasonable amount of time: 1. (sub)program Instruction limit 2. Verifier step limit subprogram ~function Verifier operates on subprograms. Max subprograms is an internal detail, but (tail calls) limit is 31 pushing to at least 31M instructions Clang: ~26M instructions can back of napkin fit inside a BPF Linux runtime.
  18. Are eBPF programs limited to a few M++ instructions? Verifier

    has limits to ensure verifier completes in reasonable amount of time: 1. (sub)program Instruction limit 2. Verifier step limit subprogram ~function Verifier operates on subprograms. Max subprograms is an internal detail, but (tail calls) limit is 31 pushing to at least 31M instructions Clang: ~26M instructions can back of napkin fit inside a BPF Linux runtime. Caution 1: Writing C-like code the compiler, verifier and human can all agree on at these scales requires skill and practice. Good news, core group of folks are working hard to make this easier.
  19. Are eBPF programs limited to a few M++ instructions? Verifier

    has limits to ensure verifier completes in reasonable amount of time: 1. (sub)program Instruction limit 2. Verifier step limit subprogram ~function Verifier operates on subprograms. Max subprograms is an internal detail, but (tail calls) limit is 31 pushing to at least 31M instructions Clang: ~26M instructions can back of napkin fit inside a BPF Linux runtime. Caution 2: This may become addictive and you may try to start trying to port doom, quake, tetris and other artifacts into BPF.
  20. Do eBPF programs have to terminate? Yes and No: BPF

    execution on-cpu time is bounded the BPF program must release the CPU. How can a BPF program release the CPU: • Reach end of the BPF program • Iterator programs are specially designed to walk arbitrary lists of objects v5.8 • Sleep on page fault or other memory operation. v5.10 • Timer callback (restart my program at funcA at time X, X may be 0). v5.15 static int do_game(void) { copy_cellmap(); next_generation (); send_update(); return run_next(2); }
  21. Can eBPF programs allocate memory? Maps as memory management system.

    int nextX(uint cell) { uint x, count; uint k = 0; struct cellmap *m; char *cellp; m = lookup_elem(&b, &k); if (!m) return -1; [...] } BPF array maps can be arbitrarily large as long as they fit inside system memory limits. 6.9 will introduce bpf_arena() a 4GB 32bit pointer vaddr space.
  22. Are these statements true? No! “Implementing HTTP/2, or terminating TLS,

    are simply not possible in eBPF: they’re too complex” “eBPF is not Turing complete” They might not be implemented today, but they are possible