core/vm: faster create/create2 (#17806)

* core/vm/runtim: benchmark create/create2

* core/vm: do less hashing in CREATE2

* core/vm: avoid storing jumpdest analysis for initcode

* core/vm: avoid unneccesary lookups, remove unused fields

* core/vm: go formatting tests

* core/vm: save jumpdest analysis locally

* core/vm: use common.Hash instead of nil, fix review comments

* core/vm: removed type destinations

* core/vm: correct check for empty hash

* eth: more elegant api_tracer

* core/vm: address review concerns

9 files changed, 163 insertions, 55 deletions

diff --git a/core/vm/analysis.go b/core/vm/analysis.go
index f9c4298d3..0ccf47b97 100644
--- a/core/vm/analysis.go
+++ b/core/vm/analysis.go
@@ -16,34 +16,6 @@
 
 package vm
 
-import (
-	"math/big"
-
-	"github.com/ethereum/go-ethereum/common"
-)
-
-// destinations stores one map per contract (keyed by hash of code).
-// The maps contain an entry for each location of a JUMPDEST
-// instruction.
-type destinations map[common.Hash]bitvec
-
-// has checks whether code has a JUMPDEST at dest.
-func (d destinations) has(codehash common.Hash, code []byte, dest *big.Int) bool {
-	// PC cannot go beyond len(code) and certainly can't be bigger than 63bits.
-	// Don't bother checking for JUMPDEST in that case.
-	udest := dest.Uint64()
-	if dest.BitLen() >= 63 || udest >= uint64(len(code)) {
-		return false
-	}
-
-	m, analysed := d[codehash]
-	if !analysed {
-		m = codeBitmap(code)
-		d[codehash] = m
-	}
-	return OpCode(code[udest]) == JUMPDEST && m.codeSegment(udest)
-}
-
 // bitvec is a bit vector which maps bytes in a program.
 // An unset bit means the byte is an opcode, a set bit means
 // it's data (i.e. argument of PUSHxx).
diff --git a/core/vm/analysis_test.go b/core/vm/analysis_test.go
index a64f90ed9..fd2d744d8 100644
--- a/core/vm/analysis_test.go
+++ b/core/vm/analysis_test.go
@@ -16,7 +16,11 @@
 
 package vm
 
-import "testing"
+import (
+	"testing"
+
+	"github.com/ethereum/go-ethereum/crypto"
+)
 
 func TestJumpDestAnalysis(t *testing.T) {
 	tests := []struct {
@@ -49,5 +53,23 @@ func TestJumpDestAnalysis(t *testing.T) {
 			t.Fatalf("expected %x, got %02x", test.exp, ret[test.which])
 		}
 	}
+}
 
+func BenchmarkJumpdestAnalysis_1200k(bench *testing.B) {
+	// 1.4 ms
+	code := make([]byte, 1200000)
+	bench.ResetTimer()
+	for i := 0; i < bench.N; i++ {
+		codeBitmap(code)
+	}
+	bench.StopTimer()
+}
+func BenchmarkJumpdestHashing_1200k(bench *testing.B) {
+	// 4 ms
+	code := make([]byte, 1200000)
+	bench.ResetTimer()
+	for i := 0; i < bench.N; i++ {
+		crypto.Keccak256Hash(code)
+	}
+	bench.StopTimer()
 }
diff --git a/core/vm/contract.go b/core/vm/contract.go
index 26bca6895..20baa6e75 100644
--- a/core/vm/contract.go
+++ b/core/vm/contract.go
@@ -49,7 +49,8 @@ type Contract struct {
 	caller        ContractRef
 	self          ContractRef
 
-	jumpdests destinations // result of JUMPDEST analysis.
+	jumpdests map[common.Hash]bitvec // Aggregated result of JUMPDEST analysis.
+	analysis  bitvec                 // Locally cached result of JUMPDEST analysis
 
 	Code     []byte
 	CodeHash common.Hash
@@ -58,21 +59,17 @@ type Contract struct {
 
 	Gas   uint64
 	value *big.Int
-
-	Args []byte
-
-	DelegateCall bool
 }
 
 // NewContract returns a new contract environment for the execution of EVM.
 func NewContract(caller ContractRef, object ContractRef, value *big.Int, gas uint64) *Contract {
-	c := &Contract{CallerAddress: caller.Address(), caller: caller, self: object, Args: nil}
+	c := &Contract{CallerAddress: caller.Address(), caller: caller, self: object}
 
 	if parent, ok := caller.(*Contract); ok {
 		// Reuse JUMPDEST analysis from parent context if available.
 		c.jumpdests = parent.jumpdests
 	} else {
-		c.jumpdests = make(destinations)
+		c.jumpdests = make(map[common.Hash]bitvec)
 	}
 
 	// Gas should be a pointer so it can safely be reduced through the run
@@ -84,10 +81,42 @@ func NewContract(caller ContractRef, object ContractRef, value *big.Int, gas uin
 	return c
 }
 
+func (c *Contract) validJumpdest(dest *big.Int) bool {
+	udest := dest.Uint64()
+	// PC cannot go beyond len(code) and certainly can't be bigger than 63bits.
+	// Don't bother checking for JUMPDEST in that case.
+	if dest.BitLen() >= 63 || udest >= uint64(len(c.Code)) {
+		return false
+	}
+	// Only JUMPDESTs allowed for destinations
+	if OpCode(c.Code[udest]) != JUMPDEST {
+		return false
+	}
+	// Do we have a contract hash already?
+	if c.CodeHash != (common.Hash{}) {
+		// Does parent context have the analysis?
+		analysis, exist := c.jumpdests[c.CodeHash]
+		if !exist {
+			// Do the analysis and save in parent context
+			// We do not need to store it in c.analysis
+			analysis = codeBitmap(c.Code)
+			c.jumpdests[c.CodeHash] = analysis
+		}
+		return analysis.codeSegment(udest)
+	}
+	// We don't have the code hash, most likely a piece of initcode not already
+	// in state trie. In that case, we do an analysis, and save it locally, so
+	// we don't have to recalculate it for every JUMP instruction in the execution
+	// However, we don't save it within the parent context
+	if c.analysis == nil {
+		c.analysis = codeBitmap(c.Code)
+	}
+	return c.analysis.codeSegment(udest)
+}
+
 // AsDelegate sets the contract to be a delegate call and returns the current
 // contract (for chaining calls)
 func (c *Contract) AsDelegate() *Contract {
-	c.DelegateCall = true
 	// NOTE: caller must, at all times be a contract. It should never happen
 	// that caller is something other than a Contract.
 	parent := c.caller.(*Contract)
@@ -138,12 +167,6 @@ func (c *Contract) Value() *big.Int {
 	return c.value
 }
 
-// SetCode sets the code to the contract
-func (c *Contract) SetCode(hash common.Hash, code []byte) {
-	c.Code = code
-	c.CodeHash = hash
-}
-
 // SetCallCode sets the code of the contract and address of the backing data
 // object
 func (c *Contract) SetCallCode(addr *common.Address, hash common.Hash, code []byte) {
@@ -151,3 +174,11 @@ func (c *Contract) SetCallCode(addr *common.Address, hash common.Hash, code []by
 	c.CodeHash = hash
 	c.CodeAddr = addr
 }
+
+// SetCodeOptionalHash can be used to provide code, but it's optional to provide hash.
+// In case hash is not provided, the jumpdest analysis will not be saved to the parent context
+func (c *Contract) SetCodeOptionalHash(addr *common.Address, codeAndHash *codeAndHash) {
+	c.Code = codeAndHash.code
+	c.CodeHash = codeAndHash.hash
+	c.CodeAddr = addr
+}
diff --git a/core/vm/evm.go b/core/vm/evm.go
index fc040c621..968d2219e 100644
--- a/core/vm/evm.go
+++ b/core/vm/evm.go
@@ -212,12 +212,12 @@ func (evm *EVM) Call(caller ContractRef, addr common.Address, input []byte, gas
 		evm.StateDB.CreateAccount(addr)
 	}
 	evm.Transfer(evm.StateDB, caller.Address(), to.Address(), value)
-
 	// Initialise a new contract and set the code that is to be used by the EVM.
 	// The contract is a scoped environment for this execution context only.
 	contract := NewContract(caller, to, value, gas)
 	contract.SetCallCode(&addr, evm.StateDB.GetCodeHash(addr), evm.StateDB.GetCode(addr))
 
+	// Even if the account has no code, we need to continue because it might be a precompile
 	start := time.Now()
 
 	// Capture the tracer start/end events in debug mode
@@ -352,8 +352,20 @@ func (evm *EVM) StaticCall(caller ContractRef, addr common.Address, input []byte
 	return ret, contract.Gas, err
 }
 
+type codeAndHash struct {
+	code []byte
+	hash common.Hash
+}
+
+func (c *codeAndHash) Hash() common.Hash {
+	if c.hash == (common.Hash{}) {
+		c.hash = crypto.Keccak256Hash(c.code)
+	}
+	return c.hash
+}
+
 // create creates a new contract using code as deployment code.
-func (evm *EVM) create(caller ContractRef, code []byte, gas uint64, value *big.Int, address common.Address) ([]byte, common.Address, uint64, error) {
+func (evm *EVM) create(caller ContractRef, codeAndHash *codeAndHash, gas uint64, value *big.Int, address common.Address) ([]byte, common.Address, uint64, error) {
 	// Depth check execution. Fail if we're trying to execute above the
 	// limit.
 	if evm.depth > int(params.CallCreateDepth) {
@@ -382,14 +394,14 @@ func (evm *EVM) create(caller ContractRef, code []byte, gas uint64, value *big.I
 	// EVM. The contract is a scoped environment for this execution context
 	// only.
 	contract := NewContract(caller, AccountRef(address), value, gas)
-	contract.SetCallCode(&address, crypto.Keccak256Hash(code), code)
+	contract.SetCodeOptionalHash(&address, codeAndHash)
 
 	if evm.vmConfig.NoRecursion && evm.depth > 0 {
 		return nil, address, gas, nil
 	}
 
 	if evm.vmConfig.Debug && evm.depth == 0 {
-		evm.vmConfig.Tracer.CaptureStart(caller.Address(), address, true, code, gas, value)
+		evm.vmConfig.Tracer.CaptureStart(caller.Address(), address, true, codeAndHash.code, gas, value)
 	}
 	start := time.Now()
 
@@ -433,7 +445,7 @@ func (evm *EVM) create(caller ContractRef, code []byte, gas uint64, value *big.I
 // Create creates a new contract using code as deployment code.
 func (evm *EVM) Create(caller ContractRef, code []byte, gas uint64, value *big.Int) (ret []byte, contractAddr common.Address, leftOverGas uint64, err error) {
 	contractAddr = crypto.CreateAddress(caller.Address(), evm.StateDB.GetNonce(caller.Address()))
-	return evm.create(caller, code, gas, value, contractAddr)
+	return evm.create(caller, &codeAndHash{code: code}, gas, value, contractAddr)
 }
 
 // Create2 creates a new contract using code as deployment code.
@@ -441,8 +453,9 @@ func (evm *EVM) Create(caller ContractRef, code []byte, gas uint64, value *big.I
 // The different between Create2 with Create is Create2 uses sha3(0xff ++ msg.sender ++ salt ++ sha3(init_code))[12:]
 // instead of the usual sender-and-nonce-hash as the address where the contract is initialized at.
 func (evm *EVM) Create2(caller ContractRef, code []byte, gas uint64, endowment *big.Int, salt *big.Int) (ret []byte, contractAddr common.Address, leftOverGas uint64, err error) {
-	contractAddr = crypto.CreateAddress2(caller.Address(), common.BigToHash(salt), code)
-	return evm.create(caller, code, gas, endowment, contractAddr)
+	codeAndHash := &codeAndHash{code: code}
+	contractAddr = crypto.CreateAddress2(caller.Address(), common.BigToHash(salt), codeAndHash.Hash().Bytes())
+	return evm.create(caller, codeAndHash, gas, endowment, contractAddr)
 }
 
 // ChainConfig returns the environment's chain configuration
diff --git a/core/vm/instructions.go b/core/vm/instructions.go
index 4d1bd4a34..9623fb8de 100644
--- a/core/vm/instructions.go
+++ b/core/vm/instructions.go
@@ -620,7 +620,7 @@ func opSstore(pc *uint64, interpreter *EVMInterpreter, contract *Contract, memor
 
 func opJump(pc *uint64, interpreter *EVMInterpreter, contract *Contract, memory *Memory, stack *Stack) ([]byte, error) {
 	pos := stack.pop()
-	if !contract.jumpdests.has(contract.CodeHash, contract.Code, pos) {
+	if !contract.validJumpdest(pos) {
 		nop := contract.GetOp(pos.Uint64())
 		return nil, fmt.Errorf("invalid jump destination (%v) %v", nop, pos)
 	}
@@ -633,7 +633,7 @@ func opJump(pc *uint64, interpreter *EVMInterpreter, contract *Contract, memory
 func opJumpi(pc *uint64, interpreter *EVMInterpreter, contract *Contract, memory *Memory, stack *Stack) ([]byte, error) {
 	pos, cond := stack.pop(), stack.pop()
 	if cond.Sign() != 0 {
-		if !contract.jumpdests.has(contract.CodeHash, contract.Code, pos) {
+		if !contract.validJumpdest(pos) {
 			nop := contract.GetOp(pos.Uint64())
 			return nil, fmt.Errorf("invalid jump destination (%v) %v", nop, pos)
 		}
diff --git a/core/vm/runtime/runtime_test.go b/core/vm/runtime/runtime_test.go
index ef664bda3..bac06e524 100644
--- a/core/vm/runtime/runtime_test.go
+++ b/core/vm/runtime/runtime_test.go
@@ -26,6 +26,7 @@ import (
 	"github.com/ethereum/go-ethereum/core/state"
 	"github.com/ethereum/go-ethereum/core/vm"
 	"github.com/ethereum/go-ethereum/ethdb"
+	"github.com/ethereum/go-ethereum/params"
 )
 
 func TestDefaults(t *testing.T) {
@@ -148,3 +149,57 @@ func BenchmarkCall(b *testing.B) {
 		}
 	}
 }
+func benchmarkEVM_Create(bench *testing.B, code string) {
+	var (
+		statedb, _ = state.New(common.Hash{}, state.NewDatabase(ethdb.NewMemDatabase()))
+		sender     = common.BytesToAddress([]byte("sender"))
+		receiver   = common.BytesToAddress([]byte("receiver"))
+	)
+
+	statedb.CreateAccount(sender)
+	statedb.SetCode(receiver, common.FromHex(code))
+	runtimeConfig := Config{
+		Origin:      sender,
+		State:       statedb,
+		GasLimit:    10000000,
+		Difficulty:  big.NewInt(0x200000),
+		Time:        new(big.Int).SetUint64(0),
+		Coinbase:    common.Address{},
+		BlockNumber: new(big.Int).SetUint64(1),
+		ChainConfig: &params.ChainConfig{
+			ChainID:             big.NewInt(1),
+			HomesteadBlock:      new(big.Int),
+			ByzantiumBlock:      new(big.Int),
+			ConstantinopleBlock: new(big.Int),
+			DAOForkBlock:        new(big.Int),
+			DAOForkSupport:      false,
+			EIP150Block:         new(big.Int),
+			EIP155Block:         new(big.Int),
+			EIP158Block:         new(big.Int),
+		},
+		EVMConfig: vm.Config{},
+	}
+	// Warm up the intpools and stuff
+	bench.ResetTimer()
+	for i := 0; i < bench.N; i++ {
+		Call(receiver, []byte{}, &runtimeConfig)
+	}
+	bench.StopTimer()
+}
+
+func BenchmarkEVM_CREATE_500(bench *testing.B) {
+	// initcode size 500K, repeatedly calls CREATE and then modifies the mem contents
+	benchmarkEVM_Create(bench, "5b6207a120600080f0600152600056")
+}
+func BenchmarkEVM_CREATE2_500(bench *testing.B) {
+	// initcode size 500K, repeatedly calls CREATE2 and then modifies the mem contents
+	benchmarkEVM_Create(bench, "5b586207a120600080f5600152600056")
+}
+func BenchmarkEVM_CREATE_1200(bench *testing.B) {
+	// initcode size 1200K, repeatedly calls CREATE and then modifies the mem contents
+	benchmarkEVM_Create(bench, "5b62124f80600080f0600152600056")
+}
+func BenchmarkEVM_CREATE2_1200(bench *testing.B) {
+	// initcode size 1200K, repeatedly calls CREATE2 and then modifies the mem contents
+	benchmarkEVM_Create(bench, "5b5862124f80600080f5600152600056")
+}
diff --git a/crypto/crypto.go b/crypto/crypto.go
index 3211957e0..9b3e76d40 100644
--- a/crypto/crypto.go
+++ b/crypto/crypto.go
@@ -77,9 +77,9 @@ func CreateAddress(b common.Address, nonce uint64) common.Address {
 }
 
 // CreateAddress2 creates an ethereum address given the address bytes, initial
-// contract code and a salt.
-func CreateAddress2(b common.Address, salt [32]byte, code []byte) common.Address {
-	return common.BytesToAddress(Keccak256([]byte{0xff}, b.Bytes(), salt[:], Keccak256(code))[12:])
+// contract code hash and a salt.
+func CreateAddress2(b common.Address, salt [32]byte, inithash []byte) common.Address {
+	return common.BytesToAddress(Keccak256([]byte{0xff}, b.Bytes(), salt[:], inithash)[12:])
 }
 
 // ToECDSA creates a private key with the given D value.
diff --git a/eth/api_tracer.go b/eth/api_tracer.go
index 5b7f168ec..80552ada8 100644
--- a/eth/api_tracer.go
+++ b/eth/api_tracer.go
@@ -391,6 +391,15 @@ func (api *PrivateDebugAPI) TraceBlockFromFile(ctx context.Context, file string,
 	return api.TraceBlock(ctx, blob, config)
 }
 
+// TraceBadBlock returns the structured logs created during the execution of a block
+// within the blockchain 'badblocks' cache
+func (api *PrivateDebugAPI) TraceBadBlock(ctx context.Context, index int, config *TraceConfig) ([]*txTraceResult, error) {
+	if blocks := api.eth.blockchain.BadBlocks(); index < len(blocks) {
+		return api.traceBlock(ctx, blocks[index], config)
+	}
+	return nil, fmt.Errorf("index out of range")
+}
+
 // traceBlock configures a new tracer according to the provided configuration, and
 // executes all the transactions contained within. The return value will be one item
 // per transaction, dependent on the requestd tracer.
diff --git a/internal/web3ext/web3ext.go b/internal/web3ext/web3ext.go
index bf4b7808f..addf3c766 100644
--- a/internal/web3ext/web3ext.go
+++ b/internal/web3ext/web3ext.go
@@ -379,6 +379,12 @@ web3._extend({
 			inputFormatter: [null, null]
 		}),
 		new web3._extend.Method({
+			name: 'traceBadBlock',
+			call: 'debug_traceBadBlock',
+			params: 1,
+			inputFormatter: [null]
+		}),
+		new web3._extend.Method({
 			name: 'traceBlockByNumber',
 			call: 'debug_traceBlockByNumber',
 			params: 2,