On: Extending the Linux Kernel with Built-In Kernel He...

[monocasa]

The bytecode format of eBPF is Turing complete, it's the verification pass that makes sure the code flow graph is a DAG for instance.

cBPF was different, and only allowed you to jump forward (guaranteeing termination), but eBPF is a much more general VM.