2 ms·
> WASM's not huge, but it's giant compared to eBPF. Yeah, I'm not sure that's accurate, and even if it were, I'm not sure that's relevant. The description of t
by naasking 8y ago
> WASM's not huge, but it's giant compared to eBPF.
Yeah, I'm not sure that's accurate, and even if it were, I'm not sure that's relevant. The description of the addressing modes in eBPF [1] means each instruction is polymorphic just like in WASM, yielding a multiplicative explosion in instructions in both cases.
Furthermore, the "extras" in WASM amounts to supporting floating point, different integral types other than 32-bit int, function calling instructions and basic loops. Hardly revolutionary or difficult to implement. Once you add those with the requisite polymorphic instructions, eBPF and WASM aren't so dissimilar. You could argue those aren't necessary, and yet they unarguably make WASM a more attractive target, and the instructions can be specifically optimized in ways that simulating them cannot be.
> * eBPF explicitly doesn't do register allocation, which simplifies code generation.
Translation: eBPF isn't fast. The majority of performance in virtual machines is from decent register allocation.
> [eBPF is a] load/store architecture, so for the vast majority of cases for both CISC and RISC architectures, there's a one to one correlation between eBPF instructions and native processor instructions, also greatly simplifying code generation.
This is shared by WASM.
> * The only actually used eBPF implementation heavily reduces the options of the code flow graph to being a not quite Turing complete subset. The code flow graph can only be a DAG, so you can rely on being able to generate programs that you can easily, statically verify will terminate.
Does not follow. CPP is guaranteed to terminate as well, and yet you can easily write macros [2] that will blow up CPP at compile-time because the generated expression is so large. Not Turing complete does entail "tractable".
> * The memory usage is a lot more explicit. The stack can be checked for worst case usage.
Useful, but this has also been done for Turing complete languages as well, so there's no a priori reason to think you can't get 90% of the same effect with WASM, and without the expressiveness headaches of dealing with non-Turing completeness.
As for verification, yes limiting expressiveness is useful for making certain properties trivial, but it also makes your tool less useful.
[1] https://www.kernel.org/doc/Documentation/networking/filter.txt https://www.kernel.org/doc/Documentation/networking/filter.t...
[2] http://p99.gforge.inria.fr/ http://p99.gforge.inria.fr/
- monocasa 8y ago> Yeah, I'm not sure that's accurate, and even if it were, I'm not sure that's relevant. The size of the verifier and runtime is absolutely relevant to keeping the TCB down to a manageable level. > The description of the addressing modes in eBPF [1] means each instruction is polymorphic just like in WASM, yielding a multiplicative explosion in instructions in both cases. There's two very different ISAs being described in that doc, the classic BPF from the 90s that resembled a CISC architectre with tons of addressing modes, and the more RISC-esque eBPF that only has the one. > Furthermore, the "extras" in WASM amounts to supporting floating point, different integral types other than 32-bit int, function calling instructions and basic loops. Hardly revolutionary or difficult to implement. Once you add those with the requisite polymorphic instructions, eBPF and WASM aren't so dissimilar. You could argue those aren't necessary, and yet they unarguably make WASM a more attractive target, and the instructions can be specifically optimized in ways that simulating them cannot be. I described above how they're different, and how that helps simplify the in kernel work for eBPF. > Translation: eBPF isn't fast. The majority of performance in virtual machines is from decent register allocation. The register allocation is done by the untrusted code and is only verified by the runtime. You can still achieve very good register usage. >> [eBPF is a] load/store architecture, so for the vast majority of cases for both CISC and RISC architectures, there's a one to one correlation between eBPF instructions and native processor instructions, also greatly simplifying code generation. > This is shared by WASM. Your [] block is telling. It cut off the first half of that clause which is necessary for my comment to make sense. WASM is a stack based machine which means you have a strict choice between fast JITed and a dead simple code generator. The two address register instruction part that you cut off is an extremely important part of that. > Does not follow. CPP is guaranteed to terminate as well, and yet you can easily write macros [2] that will blow up CPP at compile-time because the generated expression is so large. Not Turing complete does entail "tractable". I'm not sayig that it's tractable because it's turing incomplete; I'm saying that it's Turing incomplete because it's tractable. It's tractable because the code flow graph is a DAG with non infinite code size. The macro example doesn't apply because there's no in kernel expansion like that. > Useful, but this has also been done for Turing complete languages as well It's only been done for Turing complete languages by keeping to a Turing incomplete subset. That's how sel4 works for instance. > so there's no a priori reason to think you can't get 90% of the same effect with WASM, and without the expressiveness headaches of dealing with non-Turing completeness. It's the other 10% that worries me. : ) Yeah, you can get 90% of the way there in WASM, but that doesn't cut it for the use case. > As for verification, yes limiting expressiveness is useful for making certain properties trivial, but it also makes your tool less useful. Limiting expressiveness is the only way to get to verification. That's a natural consequence of the Halting problem. If you want to do crazy town stuff like getting to the point of running multi-tenant untrusted user code in kernel space, including in interrupt handlers, then you need to reduce expressiveness. Hell, even if you're compiling a regular kernel module you need to reduce expressiveness because of the environment.
- naasking 8y ago> The size of the verifier and runtime is absolutely relevant to keeping the TCB down to a manageable level. Sure, but that's not the point I was making. The missing instructions are largely polymorphic operations on various integral and floating point types. WASM verification is not as hard as you seem to be implying. > The register allocation is done by the untrusted code and is only verified by the runtime. You can still achieve very good register usage. There are ways to do this safely even in stack machines. See: http://lambda-the-ultimate.org/node/5375 http://lambda-the-ultimate.org/node/5375 > WASM is a stack based machine which means you have a strict choice between fast JITed and a dead simple code generator. A dead simple code generator that can only make use of 10 registers isn't all that compelling. Stack machines are great for compact code, and subexpression elimination and register allocation makes stack machines largely competitive with register machines. A lot of this can be moved offline as well (see link above). > The two address register instruction part that you cut off is an extremely important part of that. 2-address instructions aren't competitive on all archs. They lead to unnecessary move sequences on 3-address architectures for one. This is why register allocation belongs in the VM. > It's tractable because the code flow graph is a DAG with non infinite code size. The macro example doesn't apply because there's no in kernel expansion like that. "DAG with non-infinite code size" also describes CPP, which is why I brought it up. That property simply doesn't say much. > It's only been done for Turing complete languages by keeping to a Turing incomplete subset. That's how sel4 works for instance. Not true, it's been done for SML with region-based memory management (MLKit IIRC). Regions with lexical lifetimes are just folded into the stack, but there's no requirement to restrict yourself to a Turing incomplete fragment (although your program must terminate, obviously, but that isn't the same thing). > Limiting expressiveness is the only way to get to verification. That's a natural consequence of the Halting problem. There are various ways to restrict programs though, so you don't have to restrict a language at the syntactic level which is far more painful than alternatives. For instance, sized types to guarantee termination and estimate space use. Furthermore, as for memory and complexity analyses, there's lots of work that doesn't overly restrict expressiveness and yet can infer time, space and complexity bounds, among a few I easily found or have seen before: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.142.5728 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.142.... https://www.microsoft.com/en-us/research/publication/speed-precise-and-efficient-static-estimation-of-program-computational-complexity-2/ https://www.microsoft.com/en-us/research/publication/speed-p... https://www.tcs.ifi.lmu.de/mitarbeiter/martin-hofmann/publikationen-pdfs/c23-staticpredictionheapspaceusage.pdf https://www.tcs.ifi.lmu.de/mitarbeiter/martin-hofmann/publik... https://www.cs.ru.nl/~marko/research/pubs/2007/TFP2007.pdf https://www.cs.ru.nl/~marko/research/pubs/2007/TFP2007.pdf Not that I think these are perfect solutions, I'm just pointing out that heavily restricting program expression has various approaches, and a brute force expressiveness-limiting hammer isn't the only way. I sympathize with your goal of wanting to reduce expressiveness to make analysis easier, but that makes the project less attractive as well because targeting it is much more work, and it has strictly limited application due to those restrictions.