# PVF stack metering :: discussion

It is a follow-up of my [research](https://forum.parity.io/t/pvf-deterministic-stack-limits/1090). I don't want to force anyone to read a wall of text there so I'm starting a separate topic for results and discussion.

## Synopsis
I was able to generate code which exposes a very low Wasm stack usage and a very high machine stack usage. Conditions triggering such a behavior are unlikely to be possible to analyze linearly. By induction, unlimited number of code samples expressing the same behavior and abusing our measurement can be produced.

## Discussion
My vision of the problem has changed greatly during the research. It has become rather philosophical than technical. Also, it's changed my view to the solvability of the problem in the form it was formulated. Given the question "is it possible to introduce a general heuristic which can reliably predict a size of machine stack for the given Wasm code", I'd answer "probably yes" three weeks ago, but now my answer is "probably no".

Consider the following example, oversimplified yet intuitive. Imagine that Cranelift, when it runs against `i32.const 100`, decides to do it the following way: it allocates 100 dwords on the machine stack, puts `1` into each of them and then adds them together in a sequence using a register. As a result you have `100` in your register. That behavior, albeit rather strange, would be:

* Totally legit (machine code does exactly what Wasm code does, it produces a constant with value `100`);
* Totally unpredictable from the point of view of machine stack size (we cannot induce 100 stack slots from the Wasm code itself, considering Cranelift to be a blackbox for us).

What is happening in a real code is exactly the same thing, just for more complex code snippets. A heuristic based on linear code analysis can (somewhat) predict machine stack size for the code whose logic is, let's say, normally distributed, that is, an ordinary peace of code written by a fellow developer who doesn't want to be nasty. But if you want to abuse that heuristic, you will. Considering Cranelift a blackbox with a number of dark corners, of course.

And it's totally clear for me now why it is like that. Trying to create such a heuristic we were relying on an assumption that the machine stack behavior is guided by (or at least correlates with) the Wasm stack behavior. Unfortunately, it is proven to be wrong for the Cranelift's case.

One may object that Cranelift is not a blackbox indeed, its code is open and we can grab some knowledge from its dark corners and to account it in our heuristic. Let's just add 100 stack slots when we see `i32.const 100` because we know that Cranelift does that, no matter why. It's probably possible but doesn't make any sense, because

* Cranelift's logic changes from version to version and a next version would introduce new glitches not accounted in our heuristic;
* Heuristic was supposed to be general, not bound to Cranelift;
* Heuristic that is able to catch triggering conditions of "machine stack flooding" behavior would require non-linear code analysis, but it was supposed to be simple and specifiable;
* If we want to bind ourselves to Wasmtime and Cranelift to account Cranelift's glitches in our heuristic, then the heuristic is not needed at all as we already have a [tool](https://github.com/s0me0ne-unkn0wn/pvf-stack-test) that measures stack size precisely for Wasmtime/Cranelift case.

## Conclusion
A simple heuristic metric based on linear code analisys, which would reliably predict machine stack size for a given Wasm code, cannot be produced. Unfortunately.

## Further steps
I see three ways from here:

1) To use static stack size, which doesn't sound great but is still better than to rely on an abusable metric;
2) To continue the research in the direction of non-linear code analysis and to try to produce a metric which is reliable though not simple and not easily specifiable;
3) To stick to a specific compiler and runtime environment (Wasmtime/Cranelift as an example) and to use already developed tools to measure the stack size precisely.