Bounded loops in BPF programs

Posted Dec 3, 2018 23:16 UTC (Mon) by rvolgers (guest, #63218)
Parent article: Bounded loops in BPF programs

> But BPF is an unstructured virtual machine language that doesn't contain information about loops, so the verifier has to figure out where they are itself.

This is why WebAssembly is explicit about control flow nesting and doesn't allow arbitrary jumps. Wouldn't be surprised at all if eventually BPF gets replaced with some fancy formally-verified minimal WebAssembly JIT from Google or something.

Bounded loops in BPF programs

Posted Dec 3, 2018 23:52 UTC (Mon) by roc (subscriber, #30627) [Link] (6 responses)

One of the key steps in compiling arbitrary C code to asm.js/Webassembly is/was the Relooper algorithm to turn unstructured control flow back into structured control flow. That's probably relevant here: http://mozakai.blogspot.com/2012/05/reloop-all-blocks.html

Bounded loops in BPF programs

Posted Dec 4, 2018 0:48 UTC (Tue) by rvolgers (guest, #63218) [Link] (2 responses)

The nice thing is that with WebAssembly this work is performed by the compiler, so for the BPF use case that would mean userland instead of in the kernel.

Either way there is still the problem of doing something with those loops to make sure they complete within a certain number of iterations though.

Bounded loops in BPF programs

Posted Dec 5, 2018 8:18 UTC (Wed) by edeloget (subscriber, #88392) [Link] (1 responses)

> The nice thing is that with WebAssembly this work is performed by the compiler, so for the BPF use case that would mean userland instead of in the kernel.

That, in turn, means that if I handcraft the code I send to the kernel, it will then have no way to perform the needed verifications :) Does not sound that great :)

Bounded loops in BPF programs

Posted Dec 9, 2018 1:05 UTC (Sun) by nteon (subscriber, #53899) [Link]

I think you misunderstand things -- you cannot encode unstructured control flow in WebAssembly, it doesn't have the primitives (which is why the compiler has to turn unstructured control flow into structured). If you handcraft WebAssembly, by definition it would be using structured control flow and would be in a format that allows easy verification.

Bounded loops in BPF programs

Posted Dec 5, 2018 23:30 UTC (Wed) by wahern (subscriber, #37304) [Link] (2 responses)

The Relooper algorithm isn't much better, if at all. Per the original paper, Emscripten: an LLVM-to-JavaScript compiler:

In general though, this is not always easy or even practical – there may not be a straightforward high-level loop structure corresponding to the low-level one, if for example the original C code relied heavily on goto instructions. In practice, however, almost all real-world C and C++ code tends to be amenable to loop recreation.

Of course "almost all" code is amenable because very little code comprises the more critical, performant inner loops and state machines--the parts which often heavily rely on goto.

Arguably if JavaScript had goto there likely never would have been a need to create and rely on the Relooper, and WebAssembly may have turned out differently. Lua 5.2 added a goto construct precisely because it made code generation so much easier. I suspect that eventually much BPF code will be generated from high-level DSLs. Not everybody will be using the same toolchains and libraries, and not having a goto construct is a serious headache when machine generating code. Generating performant assembly from a task-specific, declarative DSL is often trivial; much less so if you now need to implement a relooper or integrate a relooper library.

WebAssembly was originally envisioned as a simple, pure stack-based VM where variable scoping and structured blocks naturally aligned with the overall design. A goto construct was unfathomable. But then WebAssembly got much more complex and the simple stack-based design fell away. I suspect adding a goto construct could have been possible after the original, simpler concept gave way, and I wouldn't rule out its addition in the future. Gotos (including computed gotos) are still very useful in performant C code because optimizing compilers still can't do the job--in real-world code the best switch-statement optimizations still can't come close to idiomatic use of gotos and computed gotos. Like with JIT compiling, microbenchmarks and theoretical optimizations never quite make the transition to the real-world undiminished. Performance demands may still necessitate goto.

Bounded loops in BPF programs

Posted Dec 6, 2018 0:30 UTC (Thu) by wahern (subscriber, #37304) [Link] (1 responses)

> WebAssembly was originally envisioned as a simple, pure stack-based VM where variable scoping and structured blocks naturally aligned with the overall design.

What I had in mind here was the transition from the AST-based bytecode format to the structured stack machine format. The transition shifted WASM in the direction of a model where you could contemplate adding gotos. The transition happened because implementations were *already* using modern compiler techniques, like SSA transforms. Adding a goto construct with a sophisticated verifier is much less of a leap than when your machine model is based directly on ASTs.

For more context see https://github.com/WebAssembly/design/issues/755 and https://docs.google.com/document/d/1CieRxPy3Fp62LQdtWfhym...

Bounded loops in BPF programs

Posted May 12, 2019 11:16 UTC (Sun) by ibukanov (subscriber, #3942) [Link]

One of design goals of WebAssembly was fast verification to minimize loading time. Explicit goto significantly increase complexity of the verifier.

Bounded loops in BPF programs

Posted Dec 4, 2018 12:20 UTC (Tue) by nix (subscriber, #2304) [Link] (3 responses)

That would mean redoing all the JITters and everything, and breaking userspace and everything else that's grown up aroud the BPF world unless you also implement a BPF->kWASM translator. Honestly, compared to adding a few instructions (that the verifier replaces, so they don't even need JIT or interpreter support) this seems like a ridiculously heavy hammer.

(And why would Google have a WASM JITter suitable for running in *kernelspace* anyway?)

Bounded loops in BPF programs

Posted Dec 4, 2018 12:31 UTC (Tue) by roc (subscriber, #30627) [Link] (2 responses)

There's a pathological pattern that might be at work here.

1) We have a framework X.
2) X is missing a small feature. Framework Y has that feature, and is overall great, but it's more complex than we need right now, and besides the cost of migrating from X to Y for just this one feature can't be justified.
3) Add feature to X.
4) Goto 1.

Duplicating effort along the path of least resistance, one feature at a time.

"duplicating effort along the path of least resistance"

Posted Dec 4, 2018 14:30 UTC (Tue) by Herve5 (subscriber, #115399) [Link]

Indeed, this was a perfect comment, that I can see applying in a dozen industrial areas other than software, just around myself... I'll retain your wording :-D

Bounded loops in BPF programs

Posted Dec 4, 2018 20:02 UTC (Tue) by simcop2387 (subscriber, #101710) [Link]

This raises the question, and it's a big one. Does framework Y have things we don't want in framework X? If that answer is yes then that's a reason we can't use it directly. And at least with WebAssembly and BPF that answer is probably yes, there's a lot of foreign call support in webassembly that'd have to be removed and then other bits that would have to be reimplemented from BPF to make it work for the use cases where BPF is used in the kernel. I think in the end you'd end up with an incompatible with either hybrid framework Z that's a mishmash of X and Y, and I'm not sure that's better.