Memory allocation in for-loops are never treated as temporary

brockelmore commented 1 year ago

Description

An effective memory leak in for-loops or while loops leads to blowup in evm memory usage. The compiler does not recognize basically any memory storage as temporary inside a for-loop so there is a boatload of unnecessary memory expansions.

Environment

Compiler version: 0.8.17, via-ir true or false, 10m optimizer runs
Target EVM version (as per compiler settings): latest
Framework/IDE (e.g. Truffle or Remix): Foundry
EVM execution environment / backend / blockchain client: REVM
Operating system: MacOS

Steps to Reproduce

// SPDX-License-Identifier: UNLICENSED
pragma solidity >=0.6.2 <0.9.0;

import "forge-std/Test.sol";

contract OutOfGas is Test {

    function testOutOfGas() public {
        vm.pauseGasMetering();

        for(uint256 i = 0; i <= 129100; i++){
            console2.log("Run #", i, gasleft());
        }
    }
}

alternative, abi.encode version:

// SPDX-License-Identifier: UNLICENSED
pragma solidity >=0.6.2 <0.9.0;

import "forge-std/Test.sol";

contract OutOfGas is Test {

    function testOutOfGas() public {
        vm.pauseGasMetering();

        mineSalt(bytes32(uint256(1)));
    }

    function mineSalt(bytes32 bytecodeHash) internal pure returns (bytes32 salt) {
        uint256 targetStart = uint16(bytes2(hex"1234"));
        uint256 targetEnd = uint16(bytes2(hex"5678"));

        uint256 i;
        address addr;

        while (uint16(uint160(addr) >> 144) != targetStart || uint16(uint160(addr)) != targetEnd) {
            salt = bytes32(i);
            // computeCreate2Address uses keccak256 + abi.encodePacked
            addr = computeCreate2Address(salt, bytecodeHash, address(2000));
            i += 1;
        }
    }
}

here is a foundry.toml to use:

[profile.default]
auto_detect_solc = false
bytecode_hash = "none"
ffi = true
fuzz = { runs = 256 }
gas_reports = ["*"]
libs = ["lib"]
optimizer = true
optimizer_runs = 10_000_000
memory_limit = 33554432 # default limit
via-ir = true
out = "out"
solc = "0.8.17"
src = "src"
test = "test"

while the above wouldn't be possible in normal deployed applications, it highlights that there are unneeded free memory pointer updates and treating memory variables as permanent inside a for-loop when unnecessary. The above in latest foundry errors out with OutOfGas but only because of our imposed memory limit of 33.5mb per call frame. This means that for each iteration we are expanding memory. It affects non-function call loops (i.e. abi.encode and its variants) as well.

frangio commented 1 year ago

There are some issues related to this already: https://github.com/ethereum/solidity/issues/12335, https://github.com/ethereum/solidity/issues/5107

What's interesting about how this interacts with for loops or while loops is that a programmer might analyze a function and conclude it should run in linear or sublinear time/gas, but instead get quadratic gas due to memory expansion. This should be considered a serious issue.

cameel commented 1 year ago

Currently the plan is to tackle these issues in Q3: #13722.

ekpyron commented 1 year ago

Yeah, this is a known issue and we'll get to it this year - closing this as duplicate of the linked issues.

ethereum / solidity