Maximum evaluation stack depth

[lars-t-hansen]

Should there be a limit (for the sake of interoperability) on the depth of the abstract evaluation stack, to be enforced by the validator, as we enforce other limits?

We have limits on parameters and locals, but the number of outstanding values to be consumed also affects the stack frame size, trivially so in simple compilers, but even in optimizing compilers we can force arbitrarily many values to be held in temps.

The spec says that there may be limits on the nesting depth of structured control instructions but that's at best vaguely related (and we've codified no such limits yet, from what I can tell).

The Firefox baseline compiler has a hard stack frame limit that's there just as a guard against overflow attacks, it's arbitrarily 256KB now. I believe our main JIT has an arbitrary hard limit as well. Most likely other implementations are in the same situation. It might be useful to coordinate this.

[rossberg]

The spec says that there may be a limit on the number of frames on the stack (under Execution). Do you have something else in mind? I don't think it would be possible to standardise any concrete number, since the size of stack frames depends on far too many implementation details and variables that might even change dynamically and interferes with optimisations like inlining. In other words, even a single engine does not have predictable limits in any metric that is useful to producers.

[lars-t-hansen]

Yes, I'm thinking within a single function.

Consider:

var k = 50000;
var s = "";
for (let i=0; i < k; i++ )
    s += "(i64.add (get_local 0) (i64.const " + i + "))\n";
for (let i=0; i < k-1; i++ )
    s += "i64.add\n";
s = `(module (func (export "f") (param i64) (result i64)` + s + `))`;
var bin = wasmTextToBinary(s);
var mod = new WebAssembly.Module(bin);

The resulting wasm program blows the static stack frame limit in our baseline compiler because it naively stacks intermediate non-constant results, and there are 50K of those.

I agree that there are many implementation variations that make it hard to predict how large a stack frame should be or could be, but if we could all agree on an upper limit for how many values we can push on the abstract evaluation stack within a single function activation then it would be possible to test for this and to interoperate better.

[rossberg]

Ah, I see. That is currently covered broadly by the possible restriction on "the number of values on the stack". And yes, that would be easy to put a concrete number on if we wanted.

[jjpe]

I've just seen this. Experience has taught me that a call stack size of less than 2 MB is extremely low to the point that recursion as a technique simply cannot be relied upon without running a real risk of stack overflow. I agree that some limit is a good idea, but does it really have to be this low?
Perhaps even better, it would be good if the standard specifies some sort of mechanism that allow users of a WASM implementation to override the default the stack size, similarly to what native OSes have today.

[lars-t-hansen]

@jjpe, this bug is (was) about the size of individual stack frames, fairly abstractly in terms of the number of items "pushed" onto a frame during evaluation. You seem to be worried about the size of the stack as a whole (the sum of the sizes of frames on the stack at run-time). I agree that this is an important consideration in practice, but it's not clear the standard can say much about it because implementations vary so much and the precise limit may change greatly across different hardware platforms. This is what @rossberg meant above when he wrote "I don't think it would be possible to standardise any concrete number, since the size of stack frames depends on far too many implementation details and variables that might even change dynamically and interferes with optimisations like inlining."

However, if you think you want to take that discussion further I think you should open a new Issue for it so that we have a separate place to discuss it.

[lars-t-hansen]

And of course, it's always possible to file bugs against individual implementations; if you have reasonable wasm content that blows the stack, such a bug would be taken seriously.

[verbessern]

I don't know about the maximum, but I think a minimum is also nice to be considered. That will allow the generators, to ensure that a program could run everywhere.

[verbessern]

When I think a little more @lars-t-hansen and @rossberg , I think the issue can be solved indirectly. The execution of a function must be proceeded by a maximum evaluation stack depth calculation, that will be performed only at loading time, or at least no more then ones (because the functions can't change at runtime). The maximum depth is calculable, because the structured control flow instructions ensure that the current execution block will be executed from its start to some point (break or end). Consequently, its not possible to push to the stack in a loop for example, because when the loop is restarted with a break (to its start), the current evaluation stack values are removed (I think). When that depth is known (maximum possible nested blocks and the maximum operands in the stack for each block) then this problem moves to the time when the function is called, and is there enough space to allocate (in what ever way and wherever) for the whole, worse case, execution of the function.

ps. that also make the stack overflow problem per function call, not per instruction.

[jjpe]

What happens when you throw arbitrary recursion into the mix?
I think that at that point any guarantee you could possibly make about maximum stack usage goes out the window, because the stack usage can depend on run-time input and thus can grow arbitrarily large.

Hence hard stack limits on non-WASM platforms e.g. Linux, Windows and MacOS.

[verbessern]

You will not have enough memory to allocate the frame for a function call and will have a trap at the time of the call, or you will have a limit of the total frames on the stack and will trap when it is reached.

[jjpe]

So in effect a programmer using recursion is punished by the WASM system?
That seems unwise as recursion is a legitimate technique to solve problems, e.g. in extant code bases looking to make the step to WASM.

[verbessern]

I don't understand that "So in effect a programmer using recursion is punished by the WASM system?". The WASM "system" does not imply infinite memory.

[jjpe]

I never claimed it does, or that it can for that matter.

You will not have enough memory to allocate the frame for a function call and will have a trap at the time of the call, or you will have a limit of the total frames on the stack and will trap when it is reached.

But if the first of the 2 options presented here is true, it seems that even something as simple as calling a function recursively would not do the expected thing, and instead it would just trap, which means the program is aborted.
If option 2 is true, from the perspective of a recursive function it would look a lot like it does now, i.e. it works, up to some (perhaps user-definable) limit.

[verbessern]

I think the important word here is "expected". For some, it could be expected the function to trap, when there is not enough stack for its execution. For some, it could be normal the program to crash. I claim that its normal a function to result in a trap, that could be from the fact that there is no more stack. I would call that function, a gracefully terminating itself one. Also when a trap occurs the program is not aborted, because subsequent calls can still be performed from the embedder.

[verbessern]

However, that may require the implementation to precalculate the stack usage, as in the current specs that is (I think) possible, it may not always be the case. Its hard to say what is best, but crashing for seems unwise, its far better to trap. Some day, when the exceptions are part of the specs, maybe the stack overflow could be an exception, and then a program could behave correctly even if there is no more stack available, not just to crash and open a door for some hungry vulnerabilities.