recursive EVM call trigger unrecoverable stack overflow

[jangko]

some GST test such as CallRecursiveBomb0.json will crash the test program without any stack trace, no output at all.

without any additional compiler switch, it will crash at EVM depth around 370. if I increase the stack size with --passL:"-Wl,--stack,<size>" and set the size to 5MB,10MB,20MB --> it will produce stack trace and print stack overflow error. But it will always fail around EVM depth 394 no matter how big the stack is.

EVM stack depth limit is 1024, and we are not even reach half of it.

Are we using too much stack object? Any idea?

[stefantalpalaru]

Last time we discussed this, the consensus was that it's too complicated to reduce stack usage enough to make a difference, so we should avoid recursion in the VM instead.

Some of the ideas thrown around: tail-call optimisation, segmented stacks, trampolines, an explicit loop up to the supported call depth instead of recursion.

[jangko]

I hope they are not too complicated, some refactoring to cleanup existing code would help when experimenting with those ideas.

this issue can wait until we have a more stable EVM.

[jangko]

after some refactoring, the EVM could reach 658 recursion depth.
the --passL:"-Wl,--stack,<size>" with 4MB stack also can work in release mode.
25 out of 27 'recursive' GST will pass if compiled with 4MB stack.

we can try to keep refactoring to reduce stack usage and at the same time it will simplify transformation process into non-recursive EVM.

I have experimented with state machine iterative EVM, it's ugly, complex, hard to understand, but it works.
need to find more elegant design that does not sacrifice simplicity and performance.

[jangko]

finally, we have some progress in this area.
turn out {.computedGoto.} pragma consumes a lot of stack space, I assume the compiler build jump table at the stack. we could build our own manual jump table with macro assistance. and we can continue using recursive EVM until we really, really need to switch into hard-to-do non-recursive EVM.

[mratsim]

Is the Stack Overflow from Nim 2000 function calls limit in debug or is it from a lower level?

The computed goto table should be inlined with no actual table in assembly just jmp position and no central redispatching.

Edit: probably worth it to check the assembly generated for this implementation. https://github.com/status-im/nimbus/wiki/Interpreter-optimization-resources#nim-implementation-benchmark. There shouldn't be a table only code position to jump to for each opcode.

However the recursive CALL instructions might need a trampoline of some sort.

[jangko]

after some refactoring, the EVM could reach 658 recursion depth.

Simply removing computed goto pragma allow the EVM to reach 1400+ recursion depth. there must be something on the stack. But I will take a closer look.

[jlokier]

Last time we discussed this, the consensus was that it's too complicated to reduce stack usage enough to make a difference, so we should avoid recursion in the VM instead.

Some of the ideas thrown around: tail-call optimisation, segmented stacks, trampolines, an explicit loop up to the supported call depth instead of recursion.

This makes me smile. You might enjoy the linked PR #586, which reduces worst-case EVM stack usage from 13 MB to 48 kB in a small and easy to understand patch.

#588 takes it further by eliminating recursion, and then #598 solves the problem in EVMC mode (EVMC API is intrinsically recursive, but we can still make it use less stack).

There is no realistic performance impact because it doesn't touch the interpreter loop or most ops. It uses a trampoline of sorts, i.e. a Nim closure, just for the call/create ops. The trick is that only a few opcodes trigger EVM recursion, and they are already moderately heavy, so a little transformation of those leaving everything else the same is enough. Kudos to whoever designed the EVM in the first place, for providing the Computation state that was easy to build upon.

This method is flexible enough that it can also be used to asyncify the EVM (await on SLOAD etc) without penalty to other ops or changing much code.