> For that matter, even with the verifier limiting BPF programs to less than one million verified instructions, there's nothing preventing a user from attaching a 999,999 instruction BPF program that makes lots of expensive kfunc calls to every available kernel hook and slowing the system to a crawl. The point of the limit is to prevent infinite loops that might cause deadlocks, so that the system can continue to make forward progress, not to prevent BPF programs from wasting CPU time.

This makes no sense to me. What is the value of "guaranteed forward progress" if in practice that progress can be made arbitrarily slow? You can't tell someone whose system has locked up that it's not a bug because their system will unfreeze in an hour.

It seems necessary and sufficient to have some kind of counter/timer that can reliably kill BPF programs that run too long, in a safe way that leaves the kernel in a good state. Once you have that, just give up on trying to verify termination.