eBPF is shown to be Turing complete, meaning it can handle any computable problem, including complex processing tasks like parsing application-level protocols and terminating TLS connections. This capability has been demonstrated through projects like Cilium and Tetragon and verified by successfully implementing Conway’s Game of Life in eBPF. While eBPF's verifier and complexity limits have evolved significantly, making it more powerful, it still may not always be the most appropriate tool for every problem.
Table of contents
Turing Completeness and Conway’s Game of LifeThe eBPF Verifier and the Complexity LimitLooping in eBPFSplitting Complexity Across Multiple eBPF ProgramsTimers in eBPFConway’s Game of Life in eBPFWhat Does This Mean?Sort: