> "if this exceeds some limits or bogs down system for more than X milliseconds, disable and give error".
AFAIK indefinite loops in a BPF are not allowed: The kernel eBPF verifier will reject to load such programs. So the execution time of BPF programs will not be variable time and will be predictive.
I'm not sure if users need to care about the cases of long execution times when no loops are allowed.
>If true, that would imply BPF programs are not Turing complete.
It's not intended to be turing complete, just to be useful enough while provably not harming the system (e.g. by never terminating). There's quite a good write-up at https://lwn.net/Articles/773605/
You are right, eBPF is non-Turing complete. To be precise I heard that the kernel eBPF verifier ensures the flow of a BPF program is a kind of a DAG (no cycles = no loops). So eBPF VM is definitely not a general-purpose machine.
Actually they now allow bounded loops (such which you could theoretically unroll complete). It's mentioned in the talk, too. There is also a limit on the number of instructions a program can have I wonder if bounded loops multiply the "numbe of instructions" per iteration with the upper bound of t the number of persons for this?
I think it's one of the bigger misconceptions that programs have to be Turing complete to be useful, or even that functions should be allowed to be Turing complete by default. In fact, in many cases, we should probably have been programming in a way where functions are not Turing complete by default, just as in some modern languages, functions are not allowed to modify global state by defaults (functions are pure by default).
The programming language Zig is aiming to be able to calculate the stack requirements for a given function. This has enormous benefits if you can do it in areas like embedded software. You can guarantee that you don't run out of memory (functions in Zig can't use an allocator without permission either). But to do this, functions can't do recursion, and probably can't be Turing complete in general. I don't think Zig will ban recursion, but it will give you some powerful tools/options if you avoid it where you can.
Brendan Gregg talks about it in the talk in the link at 17:50.
Here is a short transcription (not verbatim):
> People have asked if BPF is Turing Complete. Is is possible to have a BPF program that can run BPF programs? We have had some serious discussions, as are we there yet. And the answer is no. The answer is no because the verifier rejects unbounded loops and so that there is some things that are not possible. There are bounded loops in BPF now.
That is a generally-useful property in various contexts, such as user-defined stream-processing functions running on shared systems. Long ago my main contribution to the re-write of the "Liverpool sort program" for processing nuclear physics data tapes was ensuring that the DSL wasn't Turing complete, to ensure progress would be made.
That was specifically a design goal to make sure their runtime is bounded, and most tasks, especially in that problem space, can be done without being turing-complete.
AFAIK indefinite loops in a BPF are not allowed: The kernel eBPF verifier will reject to load such programs. So the execution time of BPF programs will not be variable time and will be predictive.
I'm not sure if users need to care about the cases of long execution times when no loops are allowed.