Hacker News Reader

Comment by ENOTTY | Hacker News Reader

Could someone knowledgable discuss the loop thing? Is it just checking for loop termination? Or does it forbid loops entirely? If it checks for loop termination, does that imply a counter value that is statically known?

View on HN

AFAIK, it forbids true loops entirely. It's verifying that the code flow graph is a DAG. You can always unroll.

One of the things I'm playing around with is higher level loop construct stolen from graphics shaders. You should still be able to guarantee termination and worse case execution time if done right.

That's right, although work is being done to improve the situation. The first is the ability to have function calls: https://patchwork.ozlabs.org/cover/848824/. This won't allow loops, but will allow for less inline boilerplate. Building on this base infra, some folks are working to add a loop counter based verification rather than forcing the user to unroll manually.

If you can call arbitrary bpf functions I would imagine it would be trivial to allow loops through recursion, perhaps borrowing the 'gas' concept from Etherium to avoid infinite recursion and/or using too much time for function application?

The entire program is still verified as a single unit, so this shouldn't allow arbitrary code graphs still.

The function call infra being added doesn't change the current DAG restrictions, meaning that the functions are verified using a whole-program analysis semantic, so it may end up working more as just a code organization tool than something fundamental. There is already an ability to tail call to other bpf functions, which does more of what you're thinking, and the bpf runtime enforces a limit of 32 of those tail calls.

Reply on news.ycombinator.com