Expand description

The pass that tries to make stack overflows deterministic, by introducing an upper bound of the stack size.

This pass introduces a global mutable variable to track stack height, and instruments all calls with preamble and postamble.

Stack height is increased prior the call. Otherwise, the check would be made after the stack frame is allocated.

The preamble is inserted before the call. It increments the global stack height variable with statically determined “stack cost” of the callee. If after the increment the stack height exceeds the limit (specified by the rules) then execution traps. Otherwise, the call is executed.

The postamble is inserted after the call. The purpose of the postamble is to decrease the stack height by the “stack cost” of the callee function.

Note, that we can’t instrument all possible ways to return from the function. The simplest example would be a trap issued by the host function. That means stack height global won’t be equal to zero upon the next execution after such trap.

Thunks

Because stack height is increased prior the call few problems arises:

  • Stack height isn’t increased upon an entry to the first function, i.e. exported function.
  • Start function is executed externally (similar to exported functions).
  • It is statically unknown what function will be invoked in an indirect call.

The solution for this problems is to generate a intermediate functions, called ‘thunks’, which will increase before and decrease the stack height after the call to original function, and then make exported function and table entries, start section to point to a corresponding thunks.

Stack cost

Stack cost of the function is calculated as a sum of it’s locals and the maximal height of the value stack.

All values are treated equally, as they have the same size.

The rationale is that this makes it possible to use the following very naive wasm executor:

  • values are implemented by a union, so each value takes a size equal to the size of the largest possible value type this union can hold. (In MVP it is 8 bytes)
  • each value from the value stack is placed on the native stack.
  • each local variable and function argument is placed on the native stack.
  • arguments pushed by the caller are copied into callee stack rather than shared between the frames.
  • upon entry into the function entire stack frame is allocated.

Structs

  • Error that occured during processing the module.

Functions