Enabling yul optimizer and viaIR causes stack too deep error using Solidity 0.8.19

r0qs commented 1 year ago

Description

Hi, we recently find an issue when compiling safe-contracts in our test suite using the latest version of the Solidity compiler with the yul optimizer enabled. You can read more details and discussions about the issue here: https://github.com/ethereum/solidity/issues/14082

In summary, it throws stack too deep error (see below) when using the following compiler settings: {"viaIR":true,"optimizer":{"enabled":true, "details": {"yul": true}}}

The problem was introduced by this commit: https://github.com/safe-global/safe-contracts/commit/b9fdbde766eb0fee958cb9b12a3b3e5193fd96ae

Environment

Compiler version: 0.8.19
Compiler settings: evmVersion: 'paris', viaIR: true, optimizer: {enabled: true, details: {yul: true}}}

Steps to Reproduce

Set the .env to:

SOLIDITY_VERSION="0.8.19"
SOLIDITY_SETTINGS='{"viaIR":true,"optimizer":{"enabled":true, "details": {"yul": true}}}'

And run: yarn build. This will produce the following error:

YulException: Cannot swap Variable var_operation with Variable _1: too deep in the stack by 4 slots in [ var_operation RET var_operation var_data_length var_signatures_mpos var_signatures_mpos var_to var_refundReceiver var_gasToken var_gasPrice var_baseGas var_safeTxGas var_value var_data_174_offset var_refundReceiver var_to var_data_length var_value var_gasToken var_gasPrice var_baseGas var_safeTxGas _1 ]
No memoryguard was present. Consider using memory-safe assembly only and annotating it via 'assembly ("memory-safe") { ... }'.

Error HH600: Compilation failed

Possible solution

Add the "memory-safe" annotation to assembly code blocks when needed.

cameel commented 1 year ago

Just to clarify what I originally said in https://github.com/ethereum/solidity/pull/14086/files#discussion_r1157464962:

Actually, a small correction. @ekpyron rightly pointed out that this is happening with full optimizer enabled, so https://github.com/ethereum/solidity/issues/13972 is not really a solution. It's not something that will be fixed on compiler side because the compiler already has a mechanism to deal with it, it's simply that memory-unsafe assembly prevents that mechanism from kicking in. This will require a change on the Safe side.

Your code worked on earlier 0.8.x releases without marking assembly blocks as memory safe because it was just slightly below the complexity that triggers "Stack too deep" here. Later changes in the compiler seem to have pushed it over the edge. The compiler has a mechanism to keep it compiling (i.e. the memory mover) but that mechanism won't work in presence of memory-unsafe assembly. Your blocks may very well be memory-safe but the compiler only assumes that when they a block does not touch memory. It it does, you have to verify yourself if it's really memory safe and mark it as such manually. The memory-safe annotation was not available in 0.7.x but there's an alternative mechanism via a magic /// @solidity comment that lets you enable it in a portable way.

mmv08 commented 1 year ago

@cameel, to clarify if I'm getting it right: all assembly blocks must be memory safe for the compiler to use that mechanism?

cameel commented 1 year ago

Yes. All blocks that are included in the code a contract is built from. So e.g. if you have two different contracts in a file and they don't inherit from each other, blocks in one do not influence the other. But if both use a library function imported from a different file and that function has an unsafe block, both are affected.

Also, like I said, some blocks are implicitly safe and do not need to be explicitly annotated:

Inline assembly that neither involves any operations that access memory nor assigns to any Solidity variables in memory is automatically considered memory-safe and does not need to be annotated.

but an explicit annotation won't hurt either.

One way to check if all blocks are memory safe and there's nothing preventing the memory mover from kicking in is to check the IR output (solc --ir --optimized on the CLI, not sure if you can easily get that from Hardhat). If you see a memoryguard() instruction there, it's all safe. But if you get "Stack too deep" you don't even have to check that - the error message will tell you if it's missing (No memoryguard was present).

mmv08 commented 1 year ago

Hey @cameel I'm looking into the issue now, and I found an assembly block that's not memory safe: https://github.com/safe-global/safe-contracts/blob/e870f514ad34cd9654c72174d6d4a839e3c6639f/contracts/base/FallbackManager.sol#L64-L80

Here we write data to the memory that may go out of the scratch space bounds, but in our case, it is OK since we never access the memory outside the assembly block. It does compile when marked memory safe. Is there a potential drawback from a security standpoint in doing so? The solidity docs about memory safety tell that memory shall be allocated via the free memory pointer in all cases. I would like to confirm if that's the only option

ekpyron commented 1 year ago

Yes, this is a security issue. It's not overly likely to become an actual issue, but by telling the compiler that this snippet is memory safe, you allow it to move variables like success and handler to memory, which would cause invalid results, since the memory used for this is will potentially be overwritten by the calldatacopy.

The issue is really on our side, since we should do a better job of localizing stack issues - it's unlikely that there is actually a stack issue in this assembly snippet, but the compiler will currently refuse to move variables to memory anywhere if it sees any memory-unsafe assembly, rather than merely refusing to move variables that can possibly overlap with such memory-unsafe assembly. But short of that being fixed on our end, I'd recommend not to declare this assembly block as memory-safe as is without changing the way it uses memory (by actually reading the value of the free memory pointer and only using memory beyond that offset, rather than overwriting arbitrarily large memory starting at offset zero).

nlordell commented 1 year ago

For context, we are re-opening this issue as there are still some non-memory-safe sections in contracts that should be changed to be memory-safe. Some examples that have been found are:

SafeTokenTransfer.sol
CompatibilityFallbackHandler (appears to be incorrectly marked as memory-safe, but lacks actual allocation by adding the length to the free memory pointer).

There may be other instances as well.

mmv08 commented 1 year ago

I'm reopening this because the error is back again. After a quick investigation, there seem to be two problematic spots:

Spotted by @nlordell in the CompatibilityFallbackHandler - https://github.com/safe-global/safe-contracts/blob/ba5324eb9609ce4290428f023843807fe46a83e2/contracts/handler/CompatibilityFallbackHandler.sol#L88 The function is mismarked memory-safe since it never updates the free memory pointer.
https://github.com/safe-global/safe-contracts/blob/main/contracts/common/SecuredTokenTransfer.sol#L18 This function writes to the scratch space. Although it's safe, the compiler doesn't allow use of the scratch space.

nlordell commented 1 year ago

Race condition!

nlordell commented 11 months ago

Hey @ekpyron and @cameel - sorry to necro this thread a bit, but we are changing all assembly to be memory safe right now, and wanted to double check something with you that isn’t clear to us.

In particular the Solidity docs state that the following memory use is safe:

Temporary memory that is located after the value of the free memory pointer at the beginning of the assembly block, i.e. memory that is “allocated” at the free memory pointer without updating the free memory pointer

One thing I wanted to confirm from @ekpyron’s comment regarding:

It's not overly likely to become an actual issue, but by telling the compiler that this snippet is memory safe, you allow it to move variables like success and handler to memory

Does the compiler guarantee this to happen before the assembly block? Otherwise, couldn’t you potentially overwrite data written to after the free memory pointer if the allocation happens within the assembly block? I.e. imagine an assembly block that does the following:

Let us say free memory pointer is at t (so let t := mload(0x40))
We do a calldatacopy(t, 0, n) for some n > 0
Later in the assembly block, we have let variable := someValue() that the compiler decides to move into memory
We make use of the data copied from step 2.

Now to clarify, is the memory location of variable guaranteed to come before t (in other words, the compiler allocates the variable memory in some “preface” code guaranteed to run before the assembly block), or would the compiler mstore(0x40, add(mload(0x40), 32)) within the assembly block around where the variable is used? If it is the latter, then that means that you need to always “allocate” to the free memory pointer otherwise, from the example above, the variable assignment from step 3 could overwrite the data copied from step 2.

Edit: I did some investigation, and it looks like the compiler is emitting memoryguard(…)s with the space for the memory variables before any user code gets run. Notably, this means that the free memory pointer is already placed past the space for variables that were moved to memory 🎉. This means that you don’t need to allocate past the free memory pointer, and can use the memory there within an assembly block and still be memory-safe (i.e. the docs are right).

Sample code that causes the compiler to move variables to memory

```solidity // SPDX-License-Identifier: 0BSD pragma solidity >=0.7 <0.9; contract A { fallback() external { assembly ("memory-safe") { let t := mload(0x40) calldatacopy(t, 0x00, 0x20) let x00 := sload(0x00) let x01 := add(x00, sload(0x01)) let x02 := add(x01, add(x00, sload(0x02))) let x03 := add(x02, add(x01, add(x00, sload(0x03)))) let x04 := add(x03, add(x02, add(x01, add(x00, sload(0x04))))) let x05 := add(x04, add(x03, add(x02, add(x01, add(x00, sload(0x05)))))) let x06 := add(x05, add(x04, add(x03, add(x02, add(x01, add(x00, sload(0x06))))))) let x07 := add(x06, add(x05, add(x04, add(x03, add(x02, add(x01, add(x00, sload(0x07)))))))) let x08 := add(x07, add(x06, add(x05, add(x04, add(x03, add(x02, add(x01, add(x00, sload(0x08))))))))) let x09 := add(x08, add(x07, add(x06, add(x05, add(x04, add(x03, add(x02, add(x01, add(x00, sload(0x09)))))))))) let x0a := add(x09, add(x08, add(x07, add(x06, add(x05, add(x04, add(x03, add(x02, add(x01, add(x00, sload(0x0a))))))))))) let x0b := add(x0a, add(x09, add(x08, add(x07, add(x06, add(x05, add(x04, add(x03, add(x02, add(x01, add(x00, sload(0x0b)))))))))))) let x0c := add(x0b, add(x0a, add(x09, add(x08, add(x07, add(x06, add(x05, add(x04, add(x03, add(x02, add(x01, add(x00, sload(0x0c))))))))))))) let x0d := add(x0c, add(x0b, add(x0a, add(x09, add(x08, add(x07, add(x06, add(x05, add(x04, add(x03, add(x02, add(x01, add(x00, sload(0x0d)))))))))))))) let x0e := add(x0d, add(x0c, add(x0b, add(x0a, add(x09, add(x08, add(x07, add(x06, add(x05, add(x04, add(x03, add(x02, add(x01, add(x00, sload(0x0e))))))))))))))) let x0f := add(x0e, add(x0d, add(x0c, add(x0b, add(x0a, add(x09, add(x08, add(x07, add(x06, add(x05, add(x04, add(x03, add(x02, add(x01, add(x00, sload(0x0f)))))))))))))))) let x10 := add(x0f, add(x0e, add(x0d, add(x0c, add(x0b, add(x0a, add(x09, add(x08, add(x07, add(x06, add(x05, add(x04, add(x03, add(x02, add(x01, add(x00, sload(0x10))))))))))))))))) let x11 := add(x10, add(x0f, add(x0e, add(x0d, add(x0c, add(x0b, add(x0a, add(x09, add(x08, add(x07, add(x06, add(x05, add(x04, add(x03, add(x02, add(x01, add(x00, sload(0x11)))))))))))))))))) let x12 := add(x11, add(x10, add(x0f, add(x0e, add(x0d, add(x0c, add(x0b, add(x0a, add(x09, add(x08, add(x07, add(x06, add(x05, add(x04, add(x03, add(x02, add(x01, add(x00, sload(0x12))))))))))))))))))) let x13 := add(x12, add(x11, add(x10, add(x0f, add(x0e, add(x0d, add(x0c, add(x0b, add(x0a, add(x09, add(x08, add(x07, add(x06, add(x05, add(x04, add(x03, add(x02, add(x01, add(x00, sload(0x13)))))))))))))))))))) let x14 := add(x13, add(x12, add(x11, add(x10, add(x0f, add(x0e, add(x0d, add(x0c, add(x0b, add(x0a, add(x09, add(x08, add(x07, add(x06, add(x05, add(x04, add(x03, add(x02, add(x01, add(x00, sload(0x14))))))))))))))))))))) let x15 := add(x14, add(x13, add(x12, add(x11, add(x10, add(x0f, add(x0e, add(x0d, add(x0c, add(x0b, add(x0a, add(x09, add(x08, add(x07, add(x06, add(x05, add(x04, add(x03, add(x02, add(x01, add(x00, sload(0x15)))))))))))))))))))))) let x16 := add(x15, add(x14, add(x13, add(x12, add(x11, add(x10, add(x0f, add(x0e, add(x0d, add(x0c, add(x0b, add(x0a, add(x09, add(x08, add(x07, add(x06, add(x05, add(x04, add(x03, add(x02, add(x01, add(x00, sload(0x16))))))))))))))))))))))) let x17 := add(x16, add(x15, add(x14, add(x13, add(x12, add(x11, add(x10, add(x0f, add(x0e, add(x0d, add(x0c, add(x0b, add(x0a, add(x09, add(x08, add(x07, add(x06, add(x05, add(x04, add(x03, add(x02, add(x01, add(x00, sload(0x17)))))))))))))))))))))))) let x18 := add(x17, add(x16, add(x15, add(x14, add(x13, add(x12, add(x11, add(x10, add(x0f, add(x0e, add(x0d, add(x0c, add(x0b, add(x0a, add(x09, add(x08, add(x07, add(x06, add(x05, add(x04, add(x03, add(x02, add(x01, add(x00, sload(0x18))))))))))))))))))))))))) let x19 := add(x18, add(x17, add(x16, add(x15, add(x14, add(x13, add(x12, add(x11, add(x10, add(x0f, add(x0e, add(x0d, add(x0c, add(x0b, add(x0a, add(x09, add(x08, add(x07, add(x06, add(x05, add(x04, add(x03, add(x02, add(x01, add(x00, sload(0x19)))))))))))))))))))))))))) let x1a := add(x19, add(x18, add(x17, add(x16, add(x15, add(x14, add(x13, add(x12, add(x11, add(x10, add(x0f, add(x0e, add(x0d, add(x0c, add(x0b, add(x0a, add(x09, add(x08, add(x07, add(x06, add(x05, add(x04, add(x03, add(x02, add(x01, add(x00, sload(0x1a))))))))))))))))))))))))))) let x1b := add(x1a, add(x19, add(x18, add(x17, add(x16, add(x15, add(x14, add(x13, add(x12, add(x11, add(x10, add(x0f, add(x0e, add(x0d, add(x0c, add(x0b, add(x0a, add(x09, add(x08, add(x07, add(x06, add(x05, add(x04, add(x03, add(x02, add(x01, add(x00, sload(0x1b)))))))))))))))))))))))))))) let x1c := add(x1b, add(x1a, add(x19, add(x18, add(x17, add(x16, add(x15, add(x14, add(x13, add(x12, add(x11, add(x10, add(x0f, add(x0e, add(x0d, add(x0c, add(x0b, add(x0a, add(x09, add(x08, add(x07, add(x06, add(x05, add(x04, add(x03, add(x02, add(x01, add(x00, sload(0x1c))))))))))))))))))))))))))))) let x1d := add(x1c, add(x1b, add(x1a, add(x19, add(x18, add(x17, add(x16, add(x15, add(x14, add(x13, add(x12, add(x11, add(x10, add(x0f, add(x0e, add(x0d, add(x0c, add(x0b, add(x0a, add(x09, add(x08, add(x07, add(x06, add(x05, add(x04, add(x03, add(x02, add(x01, add(x00, sload(0x1d)))))))))))))))))))))))))))))) let x1e := add(x1d, add(x1c, add(x1b, add(x1a, add(x19, add(x18, add(x17, add(x16, add(x15, add(x14, add(x13, add(x12, add(x11, add(x10, add(x0f, add(x0e, add(x0d, add(x0c, add(x0b, add(x0a, add(x09, add(x08, add(x07, add(x06, add(x05, add(x04, add(x03, add(x02, add(x01, add(x00, sload(0x1e))))))))))))))))))))))))))))))) let x1f := add(x1e, add(x1d, add(x1c, add(x1b, add(x1a, add(x19, add(x18, add(x17, add(x16, add(x15, add(x14, add(x13, add(x12, add(x11, add(x10, add(x0f, add(x0e, add(x0d, add(x0c, add(x0b, add(x0a, add(x09, add(x08, add(x07, add(x06, add(x05, add(x04, add(x03, add(x02, add(x01, add(x00, sload(0x1f)))))))))))))))))))))))))))))))) mstore(add(t, 0x20), x1f) return(t, 0x40) } } } ```

safe-global / safe-smart-account