Solidity: Recursion stack overflow - Out of stack PUSH1 1/1024

[loredanacirstea]

Description

The recursion limit is not an out of gas exception. Instead, I get a stack exception.

The error on Ganache is:

RuntimeError: VM Exception while processing transaction: stack overflow

The error in Remix, when I execute the call on Kovan is:

The execution failed due to an exception. Out of stack PUSH1 1/1024

Can be seen here: https://kovan.etherscan.io/tx/0x09b3f100f3786290c8383847e002f4d32e72984d1cb54bab9095115d616d2c8f

Environment

• Compiler version: 0.7.0, 0.6.x
• Target EVM version (as per compiler settings): default
• Framework/IDE (e.g. Truffle or Remix): Remix & custom setup
• EVM execution environment / backend / blockchain client: Remix JS VM (crashes), Kovan(through Metamask), Ganache
• Operating system: web, macos

Steps to Reproduce

Deploy the following and call. Calldata doesn't matter. It just runs eval 203 times. And you get the above error.
If you change to 202, you get the correct computation result (203).

The issue may be related to input/output arguments for the eval function. When you reduce the number of input/outputs, the steps required to obtain the overflow increase by ~100 / argument.

object "RecursionStackOverflow" {
    code {
        datacopy(0, dataoffset("Runtime"), datasize("Runtime"))
        return(0, datasize("Runtime"))
    }
    object "Runtime" {
    code {

        let end, response := eval(0, 0)

        function eval(data_ptr, env_ptr) -> end_ptr, result_ptr {
            let stepcount := mload(0x20)
            if gt(stepcount, 203) { mstore(0, stepcount) return(0, 32) }
            mstore(0x20, add(stepcount, 1))

            let rootid := 3

            switch rootid

            // number
            case 1 {

            }

            // function
            case 3 {

            }

            default {

            }
            let ee, rrr := eval(data_ptr, env_ptr)
        }

    }}
}

[loredanacirstea]

Is it an issue that can be fixed?

[axic]

The EVM has a value stack limit and you keep growing the stack with recursive calls. I suggest to rework your code to not use recursive calls and then the compiler has a chance to reduce stack usage.

[loredanacirstea]

Unfortunately, removing recursion is not an option.
So, the only solution would be changing the compiler or me working directly in assembly & handling stack & memory management.
Thank you for the fast answer.

[axic]

How would you improve the compiler to use less stack during recursion?

[loredanacirstea]

By saving in memory when the stack is not enough and keeping on the stack one single pointer to the pointers of frames saved in memory.

[axic]

General stack to memory elevation is being considered and prototyped, but that will be extremely expensive in your case if you need to keep a recursive function.

[loredanacirstea]

That is very good news. Expensive is fine.
How can I help? Solving this issue is urgent/important for me.

[ekpyron]

Short answer: I think our current work on memory variables won't apply here and there's not much the compiler can do to help here in the immediate future, so you will have to reduce the stack strain manually in assembly. Once we have a new Yul dialect with memory objects that might change, but there's no ETA for that, unfortunately (but hopefully we will get there in the next months, feel free to chime in at https://github.com/ethereum/solidity/issues/5107 - any input on that is highly appreciated).

Long answer:

Well, we are prototyping moving stack variables to memory, if needed, as an optimization step after Solidity to Yul code generation (the latest prototype of that is https://github.com/ethereum/solidity/pull/9162) - I guess that's what you were referring to @axic? But that's different from the situation here. First of all the idea for that is to only do it when we can be sure that solidity's memory management (with a free memory pointer at 0x40 that is initialized using a special builtin) is used and not in general (if it works out we could consider exposing it to general Yul, though, documenting that eligible Yul code has to interact with memory in a specific way). But more importantly, we specifically excluded recursive functions for the first prototype, since they complicate this a lot (so far we're working with static memory frames to avoid the need of actual memory management and frame pointers). And generally with that prototype we're mainly trying to solve errors due to too many local variables in solidity which will become unreachable due to the EVM only providing access to 16 stack slots, which is a problem already at compile time, not errors due to the limit of 1024 stack slots in the EVM at runtime due to the call stack. So none of this will help with this problem directly.

By saving in memory when the stack is not enough and keeping on the stack one single pointer to the pointers of frames saved in memory.

Yes, this is the way to go, I think. More optimally, the frame pointer itself would even be stored at some fixed memory location instead (the pointer to the previous frame being saved as part of the current frame, I sketched an example of that below). Then you only need one stack slot for the return JUMPDEST that's implicit in the recursive call. If the call was tail-recursive, even that JUMPDEST could be avoided allowing infinite recursion (up to the gas limit), but I think we're lacking the required optimization for that so far. (Also it should be possible to rewrite any tail-recursive function as loop and since you said that that's not an option, I guess that won't work in your case anyways).

But I think there's (1) no general way to decide whether the compiler should save things to memory instead of stack (in your example 200 iterations do work and the compiler cannot really know if that's enough or you need more than that, at least in generall, when this may depend on calldata) and (2) even if the compiler wanted to do that, there would be no natural place in memory for storing variables, unless we force some form of specific memory management. As mentioned above, the latter would go along the lines of the planned "Yul with memory objects" dialect - in that dialect we can consider using either some heuristics or some special syntax to force a function to use memory variables instead of stack variables. But unfortunately, there's no fixed time frame for that to be finished (but as said above, feel free to chime in on that in https://github.com/ethereum/solidity/issues/5107, we're still trying to finalize the concept and some input from heavy Yul users would be most welcome).

So for the time being I think you have to manage this manually. I'm imagining something like this:

I'm assuming MEMORY_FRAME_POINTER to be any fixed otherwise unused memory location, FREE_MEMORY a memory location beyond any other memory location that is used by the rest of the code and due to the function in question having two arguments and two return values MEMORY_FRAME_SIZE as 0xA0 (4*0x20 plus an additional 0x20 for saving the old frame pointer).

object "RecursionStackOverflow" {
    code {
        datacopy(0, dataoffset("Runtime"), datasize("Runtime"))
        return(0, datasize("Runtime"))
    }
    object "Runtime" {
    code {

        let currentMemoryFrame := FREE_MEMORY // or whatever memory offset is beyond what the rest of the code uses
        // in more complex cases this will have to use some full-blown memory management mechanism
        // set call arguments:
        mstore(add(currentMemoryFrame, 0x20), 0) // first argument
        mstore(add(currentMemoryFrame, 0x40), 0) // second argument
        mstore(MEMORY_FRAME_POINTER, currentMemoryFrame)

        eval()

        // fetch return values
        let end := mload(add(currentMemoryFrame,  0x60))
        let response := mload(add(currentMemoryFrame,  0x80))

        function eval() {
          {
            // fetch current memory frame
            let currentMemoryFrame := mload(MEMORY_FRAME_POINTER)
            // fetch arguments
            let data_ptr := mload(add(currentMemoryFrame, 0x20)
            let env_ptr := mload(add(currentMemoryFrame, 0x40))

            let stepcount := mload(0x20)
            if gt(stepcount, 203) { mstore(0, stepcount) return(0, 32) }
            mstore(0x20, add(stepcount, 1))

            let rootid := 3

            switch rootid

            // number
            case 1 {

            }

            // function
            case 3 {

            }

            default {

            }

            // prepare memory frame for the next recursive call
            let nextMemoryFrame := add(currentMemoryFrame, MEMORY_FRAME_SIZE)
            // save the current memory frame pointer in the next memory frame
            mstore(nextMemoryFrame, currentMemoryFrame)
            // set arguments for the next recursive call
            mstore(add(nextMemoryFrame, 0x20), data_ptr)
            mstore(add(nextMemoryFrame, 0x40), env_ptr)
            // update memory frame for recursive call
            mstore(MEMORY_FRAME_POINTER, nextMemoryFrame)
        } // The entire stack should be popped at the end of the block. Note that the Yul optimizer must be enabled for that to work.
        // it's important that there is not a single local variable in scope here, but everything is stored in memory instead
        eval()
        {
            // fetch memory frame of the recursive call
            let recursiveCallMemoryFramePointer := mload(MEMORY_FRAME_POINTER)
            // fetch our own memory frame
            let currentMemoryFramePointer := mload(recursiveCallMemoryFramePointer)
            // fetch the return values of the recursive call
            let ee := mload(add(recursiveCallMemoryFramePointer, 0x60)
            let rr := mload(add(recursiveCallMemoryFramePointer, 0x80)
            // restore to original memory frame pointer
            mstore(MEMORY_FRAME_POINTER, currentMemoryFramePointer)

            let end_ptr, result_ptr
            /// ... further computation calculating end_ptr and result_ptr

            // store our return values
            mstore(add(currentMemoryFramePointer, 0x60), end_ptr)
            mstore(add(currentMemoryFramePointer, 0x80), result_ptr)
        }
        }

    }}
}

That's the best I can come up with - I'd expect a construct like that to support roughly 1024 iterations (due to the implicit JUMPDEST). Depending on the exact function this can either be optimized a bit (e.g. sharing memory slots for arguments and return values may be an option) or it needs even more complex memory management (in case you have multiple recursive functions calling each other or you may need unbounded memory within the function), as for example linked-list memory management as sketched in https://github.com/ethereum/solidity/issues/5766#issuecomment-452636221 . Let me know if you have a more optimal approach, I'd be rather curious and might use it for the continuation of https://github.com/ethereum/solidity/pull/9162 after we will finally have https://github.com/ethereum/solidity/issues/5107 !

[loredanacirstea]

Thank you for the very detailed & useful answer.
I was trying your code example, but I still need to make some changes for it to work and it is getting late, so I will continue in the morning and come back with results.

[loredanacirstea]

It seems the issue is in the optimizer. The stack is not cleared after the unnamed blocks finish - at least this is what the Remix debugger shows me.
E.g. when entering the eval() inside the main eval() function, the previous stack is not cleared. I am talking about:

         mstore(MEMORY_FRAME_POINTER, nextMemoryFrame)
        } // The entire stack should be popped at the end of the block. Note that the Yul optimizer must be enabled for that to work.
        // it's important that there is not a single local variable in scope here, but everything is stored in memory instead
        eval()
        {

I tried: (code & results: https://gist.github.com/loredanacirstea/92d2dd1127fb95ea05d4cec671d02a91)

• 0.7.0 solc.js in Remix, optimizations enabled
• 0.7.0 solc in my local setup with:
  
  
  
  • solc --strict-assembly --optimize --optimize-runs=200 contracts/recursive_test.sol - with or without blocks, the resulting bytecode was the same
  
  
  • solc --optimize --optimize-runs=200 -o build --bin --ast-json --asm contracts/recursive_test_wrap.sol - with Yul code wrapped in a Solidity contract, in the fallback function.
  
  
• deploying the solc produced bytecode directly
• assembling the asm output separately (made a plugin for Remix for this https://github.com/loredanacirstea/mevm) & deploying it.
• Ropsten, Ganache, JS VM(Remix)

Results were the same: 168 steps worked, 169 steps crashed with stack overflow.

[ekpyron]

Yes, you're right, the optimizer actually messes this up, hm...

The issue is that the optimizer doesn't know what we're trying to do and after optimization we end up with:

           function eval()
            {
                let _1 := 0x20
                let _currentMemoryFrame := mload(_1)
                let data_ptr := mload(add(_currentMemoryFrame, _1))
                let env_ptr := mload(add(_currentMemoryFrame, 0x40))
                let _2 := 0
                let stepcount := mload(_2)
                if gt(stepcount, 169)
                {
                    mstore(_2, stepcount)
                    return(_2, _1)
                }
                mstore(_2, add(stepcount, 1))
                let nextMemoryFrame := add(_currentMemoryFrame, 0xa0)
                mstore(nextMemoryFrame, _currentMemoryFrame)
                mstore(add(_currentMemoryFrame, 192), data_ptr)
                mstore(add(_currentMemoryFrame, 224), env_ptr)
                mstore(_1, nextMemoryFrame)
                eval()
                let currentMemoryFramePointer := mload(mload(_1))
                mstore(_1, currentMemoryFramePointer)
                mstore(add(currentMemoryFramePointer, 0x60), _2)
                mstore(add(currentMemoryFramePointer, 0x80), _2)
            }

So the optimizer destroyed the property that no stack variables from before the recursive eval() call are still used afterwards, since it's trying to be clever and reuses _1 and _2...

As a quick solution, in case you don't rely on the optimizer otherwise, you could disable it, except for the stack optimization, that would be solc --strict-assembly --optimize --yul-optimizations "" (popping unused variables from stack is part of the transformation from yul to evm bytecode that is enabled if optimization is enabled in general, but --yul-optimizations "" will disable all other optimiser steps). I think/hope that should in fact work.

But it's of course annoying not being able to actually use the optimiser, but I'm not sure there's a way around that at this point...

[ekpyron]

Adjusting the optimiser sequence slightly to
solc --strict-assembly --optimize --yul-optimizations "dhfoDgvulfnTUtnIf[xarrscLMcCTUtTOntnfDIulLculVculjjeulxarulrulxarrcLgvifCTUcarrLsTOtfDncarrIulcT]jmuljuljulVcTOculjmul"
should also preserve the needed property, at least for the code here https://gist.github.com/loredanacirstea/92d2dd1127fb95ea05d4cec671d02a91 - (I added T, the "LiteralMaterializer" to the end of the inner [] sequence, otherwise it's the default sequence) - but that's fragile and may or may not break with any change to the code...

[loredanacirstea]

It worked: 1015 steps with solc --strict-assembly --optimize --yul-optimizations ""
I will look into yul optimizer options, but I already consider this issue solved - from my part, it can be closed.

[ekpyron]

Nice! And it was quite an interesting issue - I hope in the future we'll have more progress on https://github.com/ethereum/solidity/issues/5107 and https://github.com/ethereum/solidity/pull/9162 and will at some point arrive at a stage, in which the compiler will be able to handle cases like this on its own.
I'm still closing this issue then, though, for now.