From b6d88a0e9f9aaeb47d585d79c768d457b545af90 Mon Sep 17 00:00:00 2001 From: Jeffrey Wilcke Date: Tue, 19 Jan 2016 23:50:00 +0100 Subject: core, core/vm, crypto: fixes for homestead * Removed some strange code that didn't apply state reverting properly * Refactored code setting from vm & state transition to the executioner * Updated tests --- core/block_validator.go | 11 +- core/database_util.go | 14 - core/database_util_test.go | 4 +- core/execution.go | 60 ++-- core/state/dump.go | 3 +- core/state/state_object.go | 7 +- core/state/statedb.go | 17 -- core/state_transition.go | 39 +-- core/transaction_pool.go | 625 ------------------------------------------ core/transaction_pool_test.go | 537 ------------------------------------ core/tx_pool.go | 617 +++++++++++++++++++++++++++++++++++++++++ core/tx_pool_test.go | 537 ++++++++++++++++++++++++++++++++++++ core/types/transaction.go | 23 +- core/vm/contract.go | 44 ++- core/vm/environment.go | 1 - core/vm/instructions.go | 27 +- core/vm/jit.go | 21 +- core/vm/jit_test.go | 5 + core/vm/jump_table.go | 23 +- core/vm/jump_table_test.go | 24 ++ core/vm/opcodes.go | 1 + core/vm/vm.go | 51 +--- 22 files changed, 1355 insertions(+), 1336 deletions(-) delete mode 100644 core/transaction_pool.go delete mode 100644 core/transaction_pool_test.go create mode 100644 core/tx_pool.go create mode 100644 core/tx_pool_test.go create mode 100644 core/vm/jump_table_test.go (limited to 'core') diff --git a/core/block_validator.go b/core/block_validator.go index 901744c61..73c33d8dd 100644 --- a/core/block_validator.go +++ b/core/block_validator.go @@ -117,8 +117,7 @@ func (v *BlockValidator) ValidateState(block, parent *types.Block, statedb *stat // For valid blocks this should always validate to true. rbloom := types.CreateBloom(receipts) if rbloom != header.Bloom { - //fmt.Printf("FUNKY: ValidateState: block number: %v\n", block.Number()) - return fmt.Errorf("unable to replicate block's bloom=%x", rbloom) + return fmt.Errorf("unable to replicate block's bloom=%x vs calculated bloom=%x", header.Bloom, rbloom) } // Tre receipt Trie's root (R = (Tr [[H1, R1], ... [Hn, R1]])) receiptSha := types.DeriveSha(receipts) @@ -270,10 +269,6 @@ func calcDifficultyHomestead(time, parentTime uint64, parentNumber, parentDiff * bigTime := new(big.Int).SetUint64(time) bigParentTime := new(big.Int).SetUint64(parentTime) - // for the exponential factor - periodCount := new(big.Int).Add(parentNumber, common.Big1) - periodCount.Div(periodCount, ExpDiffPeriod) - // holds intermediate values to make the algo easier to read & audit x := new(big.Int) y := new(big.Int) @@ -298,6 +293,10 @@ func calcDifficultyHomestead(time, parentTime uint64, parentNumber, parentDiff * x = params.MinimumDifficulty } + // for the exponential factor + periodCount := new(big.Int).Add(parentNumber, common.Big1) + periodCount.Div(periodCount, ExpDiffPeriod) + // the exponential factor, commonly refered to as "the bomb" // diff = diff + 2^(periodCount - 2) if periodCount.Cmp(common.Big1) > 0 { diff --git a/core/database_util.go b/core/database_util.go index 18ca1f44c..fd2b4c312 100644 --- a/core/database_util.go +++ b/core/database_util.go @@ -95,20 +95,6 @@ func GetHeadFastBlockHash(db ethdb.Database) common.Hash { return common.BytesToHash(data) } -// GetHeadBlockNum retrieves the block number of the current canonical head block. -func GetHeadBlockNum(db ethdb.Database) *big.Int { - data, _ := db.Get(headBlockKey) - if len(data) == 0 { - return nil - } - header := new(types.Header) - if err := rlp.Decode(bytes.NewReader(data), header); err != nil { - glog.V(logger.Error).Infof("invalid block header RLP for head block: %v", err) - return nil - } - return header.Number -} - // GetHeaderRLP retrieves a block header in its raw RLP database encoding, or nil // if the header's not found. func GetHeaderRLP(db ethdb.Database, hash common.Hash) rlp.RawValue { diff --git a/core/database_util_test.go b/core/database_util_test.go index 059f1ae9f..6b3793635 100644 --- a/core/database_util_test.go +++ b/core/database_util_test.go @@ -62,7 +62,7 @@ func (d *diffTest) UnmarshalJSON(b []byte) (err error) { return nil } -func TestDifficulty(t *testing.T) { +func TestDifficultyFrontier(t *testing.T) { file, err := os.Open("../tests/files/BasicTests/difficulty.json") if err != nil { t.Fatal(err) @@ -77,7 +77,7 @@ func TestDifficulty(t *testing.T) { for name, test := range tests { number := new(big.Int).Sub(test.CurrentBlocknumber, big.NewInt(1)) - diff := CalcDifficulty(test.CurrentTimestamp, test.ParentTimestamp, number, test.ParentDifficulty) + diff := calcDifficultyFrontier(test.CurrentTimestamp, test.ParentTimestamp, number, test.ParentDifficulty) if diff.Cmp(test.CurrentDifficulty) != 0 { t.Error(name, "failed. Expected", test.CurrentDifficulty, "and calculated", diff) } diff --git a/core/execution.go b/core/execution.go index 0c7e8cc9f..24c0c93ae 100644 --- a/core/execution.go +++ b/core/execution.go @@ -44,7 +44,6 @@ func DelegateCall(env vm.Environment, caller vm.ContractRef, addr common.Address originAddr := env.Origin() callerValue := caller.Value() ret, _, err = execDelegateCall(env, caller, &originAddr, &callerAddr, &addr, input, env.Db().GetCode(addr), gas, gasPrice, callerValue) - caller.SetAddress(callerAddr) return ret, err } @@ -78,15 +77,15 @@ func exec(env vm.Environment, caller vm.ContractRef, address, codeAddr *common.A var createAccount bool if address == nil { - // Generate a new address + // Create a new account on the state nonce := env.Db().GetNonce(caller.Address()) env.Db().SetNonce(caller.Address(), nonce+1) addr = crypto.CreateAddress(caller.Address(), nonce) address = &addr createAccount = true } - snapshotPreTransfer := env.MakeSnapshot() + snapshotPreTransfer := env.MakeSnapshot() var ( from = env.Db().GetAccount(caller.Address()) to vm.Account @@ -101,24 +100,38 @@ func exec(env vm.Environment, caller vm.ContractRef, address, codeAddr *common.A } } env.Transfer(from, to, value) - snapshotPostTransfer := env.MakeSnapshot() + // 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 := vm.NewContract(caller, to, value, gas, gasPrice) contract.SetCallCode(codeAddr, code) + defer contract.Finalise() ret, err = evm.Run(contract, input) - - if err != nil { - if err == vm.CodeStoreOutOfGasError { - // TODO: this is rather hacky, restore all state changes - // except sender's account nonce increment - toNonce := env.Db().GetNonce(to.Address()) - env.SetSnapshot(snapshotPostTransfer) - env.Db().SetNonce(to.Address(), toNonce) + // if the contract creation ran successfully and no errors were returned + // calculate the gas required to store the code. If the code could not + // be stored due to not enough gas set an error and let it be handled + // by the error checking condition below. + if err == nil && createAccount { + dataGas := big.NewInt(int64(len(ret))) + dataGas.Mul(dataGas, params.CreateDataGas) + if contract.UseGas(dataGas) { + env.Db().SetCode(*address, ret) } else { - env.SetSnapshot(snapshotPreTransfer) //env.Db().Set(snapshot) + err = vm.CodeStoreOutOfGasError } } + + // When an error was returned by the EVM or when setting the creation code + // above we revert to the snapshot and consume any gas remaining. Additionally + // when we're in homestead this also counts for code storage gas errors. + if err != nil && (params.IsHomestead(env.BlockNumber()) || err != vm.CodeStoreOutOfGasError) { + contract.UseGas(contract.Gas) + + env.SetSnapshot(snapshotPreTransfer) + } + return ret, addr, err } @@ -131,32 +144,27 @@ func execDelegateCall(env vm.Environment, caller vm.ContractRef, originAddr, toA return nil, common.Address{}, vm.DepthError } - if !env.CanTransfer(*originAddr, value) { - caller.ReturnGas(gas, gasPrice) - return nil, common.Address{}, ValueTransferErr("insufficient funds to transfer value. Req %v, has %v", value, env.Db().GetBalance(caller.Address())) - } - snapshot := env.MakeSnapshot() - var ( - //from = env.Db().GetAccount(*originAddr) - to vm.Account - ) + var to vm.Account if !env.Db().Exist(*toAddr) { to = env.Db().CreateAccount(*toAddr) } else { to = env.Db().GetAccount(*toAddr) } - contract := vm.NewContract(caller, to, value, gas, gasPrice) + // Iinitialise a new contract and make initialise the delegate values + contract := vm.NewContract(caller, to, value, gas, gasPrice).AsDelegate() contract.SetCallCode(codeAddr, code) - contract.DelegateCall = true + defer contract.Finalise() ret, err = evm.Run(contract, input) - if err != nil { - env.SetSnapshot(snapshot) //env.Db().Set(snapshot) + contract.UseGas(contract.Gas) + + env.SetSnapshot(snapshot) } + return ret, addr, err } diff --git a/core/state/dump.go b/core/state/dump.go index cff9c50aa..8eb03e8e4 100644 --- a/core/state/dump.go +++ b/core/state/dump.go @@ -28,6 +28,7 @@ type Account struct { Nonce uint64 `json:"nonce"` Root string `json:"root"` CodeHash string `json:"codeHash"` + Code string `json:"code"` Storage map[string]string `json:"storage"` } @@ -47,7 +48,7 @@ func (self *StateDB) RawDump() World { addr := self.trie.GetKey(it.Key) stateObject, _ := DecodeObject(common.BytesToAddress(addr), self.db, it.Value) - account := Account{Balance: stateObject.balance.String(), Nonce: stateObject.nonce, Root: common.Bytes2Hex(stateObject.Root()), CodeHash: common.Bytes2Hex(stateObject.codeHash)} + account := Account{Balance: stateObject.balance.String(), Nonce: stateObject.nonce, Root: common.Bytes2Hex(stateObject.Root()), CodeHash: common.Bytes2Hex(stateObject.codeHash), Code: common.Bytes2Hex(stateObject.Code())} account.Storage = make(map[string]string) storageIt := stateObject.trie.Iterator() diff --git a/core/state/state_object.go b/core/state/state_object.go index ebc9f8358..6095fc96a 100644 --- a/core/state/state_object.go +++ b/core/state/state_object.go @@ -211,11 +211,6 @@ func (c *StateObject) Address() common.Address { return c.address } -// Sets the address of the contract/account -func (c *StateObject) SetAddress(addr common.Address) { - c.address = addr -} - func (self *StateObject) Trie() *trie.SecureTrie { return self.trie } @@ -247,7 +242,7 @@ func (self *StateObject) Nonce() uint64 { // as a vm.Account interface that also satisfies the vm.ContractRef // interface. Interfaces are awesome. func (self *StateObject) Value() *big.Int { - return nil + panic("Value on StateObject should never be called") } func (self *StateObject) EachStorage(cb func(key, value []byte)) { diff --git a/core/state/statedb.go b/core/state/statedb.go index e1dde84d1..22ffa36a0 100644 --- a/core/state/statedb.go +++ b/core/state/statedb.go @@ -87,18 +87,6 @@ func (self *StateDB) GetLogs(hash common.Hash) vm.Logs { return self.logs[hash] } -func (self *StateDB) GetAllLogs() *map[common.Hash]vm.Logs { - copy := make(map[common.Hash]vm.Logs, len(self.logs)) - for k, v := range self.logs { - copy[k] = v - } - return © -} - -func (self *StateDB) SetAllLogs(logs *map[common.Hash]vm.Logs) { - self.logs = *logs -} - func (self *StateDB) Logs() vm.Logs { var logs vm.Logs for _, lgs := range self.logs { @@ -107,11 +95,6 @@ func (self *StateDB) Logs() vm.Logs { return logs } -// TODO: this may not be the most proper thing -func (self *StateDB) GetDB() ethdb.Database { - return self.db -} - func (self *StateDB) AddRefund(gas *big.Int) { self.refund.Add(self.refund, gas) } diff --git a/core/state_transition.go b/core/state_transition.go index 0cd226262..52a46c63d 100644 --- a/core/state_transition.go +++ b/core/state_transition.go @@ -21,7 +21,6 @@ import ( "math/big" "github.com/ethereum/go-ethereum/common" - "github.com/ethereum/go-ethereum/core/state" "github.com/ethereum/go-ethereum/core/vm" "github.com/ethereum/go-ethereum/logger" "github.com/ethereum/go-ethereum/logger/glog" @@ -225,38 +224,24 @@ func (self *StateTransition) transitionDb() (ret []byte, usedGas *big.Int, err e } vmenv := self.env - snapshot := vmenv.MakeSnapshot() - var addr common.Address + //var addr common.Address if contractCreation { - ret, addr, err = vmenv.Create(sender, self.data, self.gas, self.gasPrice, self.value) - if err == nil { - dataGas := big.NewInt(int64(len(ret))) - dataGas.Mul(dataGas, params.CreateDataGas) - if err := self.useGas(dataGas); err == nil { - self.state.SetCode(addr, ret) - } else { - if homestead { - // rollback all contract creation changes except for - // sender's incremented account nonce and gas usage - // TODO: fucking gas hack... verify potential DoS vuln - accNonce := vmenv.Db().GetNonce(sender.Address()) - logs := vmenv.Db().(*state.StateDB).GetAllLogs() - vmenv.SetSnapshot(snapshot) - vmenv.Db().SetNonce(sender.Address(), accNonce) - vmenv.Db().(*state.StateDB).SetAllLogs(logs) - self.gas = Big0 - - } - ret = nil // does not affect consensus but useful for StateTests validations - glog.V(logger.Core).Infoln("Insufficient gas for creating code. Require", dataGas, "and have", self.gas) - } + ret, _, err = vmenv.Create(sender, self.data, self.gas, self.gasPrice, self.value) + if homestead && err == vm.CodeStoreOutOfGasError { + self.gas = Big0 + } + + if err != nil { + ret = nil + glog.V(logger.Core).Infoln("VM create err:", err) } - glog.V(logger.Core).Infoln("VM create err:", err) } else { // Increment the nonce for the next transaction self.state.SetNonce(sender.Address(), self.state.GetNonce(sender.Address())+1) ret, err = vmenv.Call(sender, self.to().Address(), self.data, self.gas, self.gasPrice, self.value) - glog.V(logger.Core).Infoln("VM call err:", err) + if err != nil { + glog.V(logger.Core).Infoln("VM call err:", err) + } } if err != nil && IsValueTransferErr(err) { diff --git a/core/transaction_pool.go b/core/transaction_pool.go deleted file mode 100644 index a815c9ef0..000000000 --- a/core/transaction_pool.go +++ /dev/null @@ -1,625 +0,0 @@ -// Copyright 2014 The go-ethereum Authors -// This file is part of the go-ethereum library. -// -// The go-ethereum library is free software: you can redistribute it and/or modify -// it under the terms of the GNU Lesser General Public License as published by -// the Free Software Foundation, either version 3 of the License, or -// (at your option) any later version. -// -// The go-ethereum library is distributed in the hope that it will be useful, -// but WITHOUT ANY WARRANTY; without even the implied warranty of -// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -// GNU Lesser General Public License for more details. -// -// You should have received a copy of the GNU Lesser General Public License -// along with the go-ethereum library. If not, see . - -package core - -import ( - "errors" - "fmt" - "math/big" - "sort" - "sync" - "time" - - "github.com/ethereum/go-ethereum/common" - "github.com/ethereum/go-ethereum/core/state" - "github.com/ethereum/go-ethereum/core/types" - "github.com/ethereum/go-ethereum/event" - "github.com/ethereum/go-ethereum/logger" - "github.com/ethereum/go-ethereum/logger/glog" - "github.com/ethereum/go-ethereum/params" -) - -var ( - // Transaction Pool Errors - ErrInvalidSender = errors.New("Invalid sender") - ErrNonce = errors.New("Nonce too low") - ErrCheap = errors.New("Gas price too low for acceptance") - ErrBalance = errors.New("Insufficient balance") - ErrNonExistentAccount = errors.New("Account does not exist or account balance too low") - ErrInsufficientFunds = errors.New("Insufficient funds for gas * price + value") - ErrIntrinsicGas = errors.New("Intrinsic gas too low") - ErrGasLimit = errors.New("Exceeds block gas limit") - ErrNegativeValue = errors.New("Negative value") -) - -const ( - maxQueued = 64 // max limit of queued txs per address -) - -type stateFn func() (*state.StateDB, error) - -// TxPool contains all currently known transactions. Transactions -// enter the pool when they are received from the network or submitted -// locally. They exit the pool when they are included in the blockchain. -// -// The pool separates processable transactions (which can be applied to the -// current state) and future transactions. Transactions move between those -// two states over time as they are received and processed. -type TxPool struct { - quit chan bool // Quiting channel - currentState stateFn // The state function which will allow us to do some pre checkes - pendingState *state.ManagedState - gasLimit func() *big.Int // The current gas limit function callback - minGasPrice *big.Int - eventMux *event.TypeMux - events event.Subscription - localTx *txSet - mu sync.RWMutex - pending map[common.Hash]*types.Transaction // processable transactions - queue map[common.Address]map[common.Hash]*types.Transaction -} - -func NewTxPool(eventMux *event.TypeMux, currentStateFn stateFn, gasLimitFn func() *big.Int) *TxPool { - pool := &TxPool{ - pending: make(map[common.Hash]*types.Transaction), - queue: make(map[common.Address]map[common.Hash]*types.Transaction), - quit: make(chan bool), - eventMux: eventMux, - currentState: currentStateFn, - gasLimit: gasLimitFn, - minGasPrice: new(big.Int), - pendingState: nil, - localTx: newTxSet(), - events: eventMux.Subscribe(ChainHeadEvent{}, GasPriceChanged{}, RemovedTransactionEvent{}), - } - go pool.eventLoop() - - return pool -} - -func (pool *TxPool) eventLoop() { - // Track chain events. When a chain events occurs (new chain canon block) - // we need to know the new state. The new state will help us determine - // the nonces in the managed state - for ev := range pool.events.Chan() { - switch ev := ev.Data.(type) { - case ChainHeadEvent: - pool.mu.Lock() - pool.resetState() - pool.mu.Unlock() - case GasPriceChanged: - pool.mu.Lock() - pool.minGasPrice = ev.Price - pool.mu.Unlock() - case RemovedTransactionEvent: - pool.AddTransactions(ev.Txs) - } - } -} - -func (pool *TxPool) resetState() { - currentState, err := pool.currentState() - if err != nil { - glog.V(logger.Info).Infoln("failed to get current state: %v", err) - return - } - managedState := state.ManageState(currentState) - if err != nil { - glog.V(logger.Info).Infoln("failed to get managed state: %v", err) - return - } - pool.pendingState = managedState - - // validate the pool of pending transactions, this will remove - // any transactions that have been included in the block or - // have been invalidated because of another transaction (e.g. - // higher gas price) - pool.validatePool() - - // Loop over the pending transactions and base the nonce of the new - // pending transaction set. - for _, tx := range pool.pending { - if addr, err := tx.From(); err == nil { - // Set the nonce. Transaction nonce can never be lower - // than the state nonce; validatePool took care of that. - if pool.pendingState.GetNonce(addr) <= tx.Nonce() { - pool.pendingState.SetNonce(addr, tx.Nonce()+1) - } - } - } - // Check the queue and move transactions over to the pending if possible - // or remove those that have become invalid - pool.checkQueue() -} - -func (pool *TxPool) Stop() { - close(pool.quit) - pool.events.Unsubscribe() - glog.V(logger.Info).Infoln("Transaction pool stopped") -} - -func (pool *TxPool) State() *state.ManagedState { - pool.mu.RLock() - defer pool.mu.RUnlock() - - return pool.pendingState -} - -func (pool *TxPool) Stats() (pending int, queued int) { - pool.mu.RLock() - defer pool.mu.RUnlock() - - pending = len(pool.pending) - for _, txs := range pool.queue { - queued += len(txs) - } - return -} - -// Content retrieves the data content of the transaction pool, returning all the -// pending as well as queued transactions, grouped by account and nonce. -func (pool *TxPool) Content() (map[common.Address]map[uint64][]*types.Transaction, map[common.Address]map[uint64][]*types.Transaction) { - pool.mu.RLock() - defer pool.mu.RUnlock() - - // Retrieve all the pending transactions and sort by account and by nonce - pending := make(map[common.Address]map[uint64][]*types.Transaction) - for _, tx := range pool.pending { - account, _ := tx.From() - - owned, ok := pending[account] - if !ok { - owned = make(map[uint64][]*types.Transaction) - pending[account] = owned - } - owned[tx.Nonce()] = append(owned[tx.Nonce()], tx) - } - // Retrieve all the queued transactions and sort by account and by nonce - queued := make(map[common.Address]map[uint64][]*types.Transaction) - for account, txs := range pool.queue { - owned := make(map[uint64][]*types.Transaction) - for _, tx := range txs { - owned[tx.Nonce()] = append(owned[tx.Nonce()], tx) - } - queued[account] = owned - } - return pending, queued -} - -// SetLocal marks a transaction as local, skipping gas price -// check against local miner minimum in the future -func (pool *TxPool) SetLocal(tx *types.Transaction) { - pool.mu.Lock() - defer pool.mu.Unlock() - pool.localTx.add(tx.Hash()) -} - -// validateTx checks whether a transaction is valid according -// to the consensus rules. -func (pool *TxPool) validateTx(tx *types.Transaction) error { - // Validate sender - var ( - from common.Address - err error - ) - - local := pool.localTx.contains(tx.Hash()) - // Drop transactions under our own minimal accepted gas price - if !local && pool.minGasPrice.Cmp(tx.GasPrice()) > 0 { - return ErrCheap - } - - currentState, err := pool.currentState() - if err != nil { - return err - } - - homestead := params.IsHomestead(GetHeadBlockNum(currentState.GetDB())) - - // Validate the transaction sender and it's sig. Throw - // if the from fields is invalid. - if homestead { - from, err = tx.From() - } else { - from, err = tx.FromFrontier() - } - if err != nil { - return ErrInvalidSender - } - - // Make sure the account exist. Non existent accounts - // haven't got funds and well therefor never pass. - if !currentState.HasAccount(from) { - return ErrNonExistentAccount - } - - // Last but not least check for nonce errors - if currentState.GetNonce(from) > tx.Nonce() { - return ErrNonce - } - - // Check the transaction doesn't exceed the current - // block limit gas. - if pool.gasLimit().Cmp(tx.Gas()) < 0 { - return ErrGasLimit - } - - // Transactions can't be negative. This may never happen - // using RLP decoded transactions but may occur if you create - // a transaction using the RPC for example. - if tx.Value().Cmp(common.Big0) < 0 { - return ErrNegativeValue - } - - // Transactor should have enough funds to cover the costs - // cost == V + GP * GL - if currentState.GetBalance(from).Cmp(tx.Cost()) < 0 { - return ErrInsufficientFunds - } - - // Should supply enough intrinsic gas - intrGas := IntrinsicGas(tx.Data(), MessageCreatesContract(tx), homestead) - if tx.Gas().Cmp(intrGas) < 0 { - return ErrIntrinsicGas - } - - return nil -} - -// validate and queue transactions. -func (self *TxPool) add(tx *types.Transaction) error { - hash := tx.Hash() - - if self.pending[hash] != nil { - return fmt.Errorf("Known transaction (%x)", hash[:4]) - } - err := self.validateTx(tx) - if err != nil { - return err - } - self.queueTx(hash, tx) - - if glog.V(logger.Debug) { - var toname string - if to := tx.To(); to != nil { - toname = common.Bytes2Hex(to[:4]) - } else { - toname = "[NEW_CONTRACT]" - } - // we can ignore the error here because From is - // verified in ValidateTransaction. - f, _ := tx.From() - from := common.Bytes2Hex(f[:4]) - glog.Infof("(t) %x => %s (%v) %x\n", from, toname, tx.Value, hash) - } - - return nil -} - -// queueTx will queue an unknown transaction -func (self *TxPool) queueTx(hash common.Hash, tx *types.Transaction) { - from, _ := tx.From() // already validated - if self.queue[from] == nil { - self.queue[from] = make(map[common.Hash]*types.Transaction) - } - self.queue[from][hash] = tx -} - -// addTx will add a transaction to the pending (processable queue) list of transactions -func (pool *TxPool) addTx(hash common.Hash, addr common.Address, tx *types.Transaction) { - // init delayed since tx pool could have been started before any state sync - if pool.pendingState == nil { - pool.resetState() - } - - if _, ok := pool.pending[hash]; !ok { - pool.pending[hash] = tx - - // Increment the nonce on the pending state. This can only happen if - // the nonce is +1 to the previous one. - pool.pendingState.SetNonce(addr, tx.Nonce()+1) - // Notify the subscribers. This event is posted in a goroutine - // because it's possible that somewhere during the post "Remove transaction" - // gets called which will then wait for the global tx pool lock and deadlock. - go pool.eventMux.Post(TxPreEvent{tx}) - } -} - -// Add queues a single transaction in the pool if it is valid. -func (self *TxPool) Add(tx *types.Transaction) error { - self.mu.Lock() - defer self.mu.Unlock() - - if err := self.add(tx); err != nil { - return err - } - self.checkQueue() - return nil -} - -// AddTransactions attempts to queue all valid transactions in txs. -func (self *TxPool) AddTransactions(txs []*types.Transaction) { - self.mu.Lock() - defer self.mu.Unlock() - - for _, tx := range txs { - if err := self.add(tx); err != nil { - glog.V(logger.Debug).Infoln("tx error:", err) - } else { - h := tx.Hash() - glog.V(logger.Debug).Infof("tx %x\n", h[:4]) - } - } - - // check and validate the queueue - self.checkQueue() -} - -// GetTransaction returns a transaction if it is contained in the pool -// and nil otherwise. -func (tp *TxPool) GetTransaction(hash common.Hash) *types.Transaction { - // check the txs first - if tx, ok := tp.pending[hash]; ok { - return tx - } - // check queue - for _, txs := range tp.queue { - if tx, ok := txs[hash]; ok { - return tx - } - } - return nil -} - -// GetTransactions returns all currently processable transactions. -// The returned slice may be modified by the caller. -func (self *TxPool) GetTransactions() (txs types.Transactions) { - self.mu.Lock() - defer self.mu.Unlock() - - // check queue first - self.checkQueue() - // invalidate any txs - self.validatePool() - - txs = make(types.Transactions, len(self.pending)) - i := 0 - for _, tx := range self.pending { - txs[i] = tx - i++ - } - return txs -} - -// GetQueuedTransactions returns all non-processable transactions. -func (self *TxPool) GetQueuedTransactions() types.Transactions { - self.mu.RLock() - defer self.mu.RUnlock() - - var ret types.Transactions - for _, txs := range self.queue { - for _, tx := range txs { - ret = append(ret, tx) - } - } - sort.Sort(types.TxByNonce(ret)) - return ret -} - -// RemoveTransactions removes all given transactions from the pool. -func (self *TxPool) RemoveTransactions(txs types.Transactions) { - self.mu.Lock() - defer self.mu.Unlock() - for _, tx := range txs { - self.RemoveTx(tx.Hash()) - } -} - -// RemoveTx removes the transaction with the given hash from the pool. -func (pool *TxPool) RemoveTx(hash common.Hash) { - // delete from pending pool - delete(pool.pending, hash) - // delete from queue - for address, txs := range pool.queue { - if _, ok := txs[hash]; ok { - if len(txs) == 1 { - // if only one tx, remove entire address entry. - delete(pool.queue, address) - } else { - delete(txs, hash) - } - break - } - } -} - -// checkQueue moves transactions that have become processable to main pool. -func (pool *TxPool) checkQueue() { - // init delayed since tx pool could have been started before any state sync - if pool.pendingState == nil { - pool.resetState() - } - - var promote txQueue - for address, txs := range pool.queue { - currentState, err := pool.currentState() - if err != nil { - glog.Errorf("could not get current state: %v", err) - return - } - balance := currentState.GetBalance(address) - - var ( - guessedNonce = pool.pendingState.GetNonce(address) // nonce currently kept by the tx pool (pending state) - trueNonce = currentState.GetNonce(address) // nonce known by the last state - ) - promote = promote[:0] - for hash, tx := range txs { - // Drop processed or out of fund transactions - if tx.Nonce() < trueNonce || balance.Cmp(tx.Cost()) < 0 { - if glog.V(logger.Core) { - glog.Infof("removed tx (%v) from pool queue: low tx nonce or out of funds\n", tx) - } - delete(txs, hash) - continue - } - // Collect the remaining transactions for the next pass. - promote = append(promote, txQueueEntry{hash, address, tx}) - } - // Find the next consecutive nonce range starting at the current account nonce, - // pushing the guessed nonce forward if we add consecutive transactions. - sort.Sort(promote) - for i, entry := range promote { - // If we reached a gap in the nonces, enforce transaction limit and stop - if entry.Nonce() > guessedNonce { - if len(promote)-i > maxQueued { - if glog.V(logger.Debug) { - glog.Infof("Queued tx limit exceeded for %s. Tx %s removed\n", common.PP(address[:]), common.PP(entry.hash[:])) - } - for _, drop := range promote[i+maxQueued:] { - delete(txs, drop.hash) - } - } - break - } - // Otherwise promote the transaction and move the guess nonce if needed - pool.addTx(entry.hash, address, entry.Transaction) - delete(txs, entry.hash) - - if entry.Nonce() == guessedNonce { - guessedNonce++ - } - } - // Delete the entire queue entry if it became empty. - if len(txs) == 0 { - delete(pool.queue, address) - } - } -} - -// validatePool removes invalid and processed transactions from the main pool. -// If a transaction is removed for being invalid (e.g. out of funds), all sub- -// sequent (Still valid) transactions are moved back into the future queue. This -// is important to prevent a drained account from DOSing the network with non -// executable transactions. -func (pool *TxPool) validatePool() { - state, err := pool.currentState() - if err != nil { - glog.V(logger.Info).Infoln("failed to get current state: %v", err) - return - } - balanceCache := make(map[common.Address]*big.Int) - - // Clean up the pending pool, accumulating invalid nonces - gaps := make(map[common.Address]uint64) - - for hash, tx := range pool.pending { - sender, _ := tx.From() // err already checked - - // Perform light nonce and balance validation - balance := balanceCache[sender] - if balance == nil { - balance = state.GetBalance(sender) - balanceCache[sender] = balance - } - if past := state.GetNonce(sender) > tx.Nonce(); past || balance.Cmp(tx.Cost()) < 0 { - // Remove an already past it invalidated transaction - if glog.V(logger.Core) { - glog.Infof("removed tx (%v) from pool: low tx nonce or out of funds\n", tx) - } - delete(pool.pending, hash) - - // Track the smallest invalid nonce to postpone subsequent transactions - if !past { - if prev, ok := gaps[sender]; !ok || tx.Nonce() < prev { - gaps[sender] = tx.Nonce() - } - } - } - } - // Move all transactions after a gap back to the future queue - if len(gaps) > 0 { - for hash, tx := range pool.pending { - sender, _ := tx.From() - if gap, ok := gaps[sender]; ok && tx.Nonce() >= gap { - if glog.V(logger.Core) { - glog.Infof("postponed tx (%v) due to introduced gap\n", tx) - } - pool.queueTx(hash, tx) - delete(pool.pending, hash) - } - } - } -} - -type txQueue []txQueueEntry - -type txQueueEntry struct { - hash common.Hash - addr common.Address - *types.Transaction -} - -func (q txQueue) Len() int { return len(q) } -func (q txQueue) Swap(i, j int) { q[i], q[j] = q[j], q[i] } -func (q txQueue) Less(i, j int) bool { return q[i].Nonce() < q[j].Nonce() } - -// txSet represents a set of transaction hashes in which entries -// are automatically dropped after txSetDuration time -type txSet struct { - txMap map[common.Hash]struct{} - txOrd map[uint64]txOrdType - addPtr, delPtr uint64 -} - -const txSetDuration = time.Hour * 2 - -// txOrdType represents an entry in the time-ordered list of transaction hashes -type txOrdType struct { - hash common.Hash - time time.Time -} - -// newTxSet creates a new transaction set -func newTxSet() *txSet { - return &txSet{ - txMap: make(map[common.Hash]struct{}), - txOrd: make(map[uint64]txOrdType), - } -} - -// contains returns true if the set contains the given transaction hash -// (not thread safe, should be called from a locked environment) -func (self *txSet) contains(hash common.Hash) bool { - _, ok := self.txMap[hash] - return ok -} - -// add adds a transaction hash to the set, then removes entries older than txSetDuration -// (not thread safe, should be called from a locked environment) -func (self *txSet) add(hash common.Hash) { - self.txMap[hash] = struct{}{} - now := time.Now() - self.txOrd[self.addPtr] = txOrdType{hash: hash, time: now} - self.addPtr++ - delBefore := now.Add(-txSetDuration) - for self.delPtr < self.addPtr && self.txOrd[self.delPtr].time.Before(delBefore) { - delete(self.txMap, self.txOrd[self.delPtr].hash) - delete(self.txOrd, self.delPtr) - self.delPtr++ - } -} diff --git a/core/transaction_pool_test.go b/core/transaction_pool_test.go deleted file mode 100644 index 811e40111..000000000 --- a/core/transaction_pool_test.go +++ /dev/null @@ -1,537 +0,0 @@ -// Copyright 2015 The go-ethereum Authors -// This file is part of the go-ethereum library. -// -// The go-ethereum library is free software: you can redistribute it and/or modify -// it under the terms of the GNU Lesser General Public License as published by -// the Free Software Foundation, either version 3 of the License, or -// (at your option) any later version. -// -// The go-ethereum library is distributed in the hope that it will be useful, -// but WITHOUT ANY WARRANTY; without even the implied warranty of -// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -// GNU Lesser General Public License for more details. -// -// You should have received a copy of the GNU Lesser General Public License -// along with the go-ethereum library. If not, see . - -package core - -import ( - "crypto/ecdsa" - "math/big" - "testing" - - "github.com/ethereum/go-ethereum/common" - "github.com/ethereum/go-ethereum/core/state" - "github.com/ethereum/go-ethereum/core/types" - "github.com/ethereum/go-ethereum/crypto" - "github.com/ethereum/go-ethereum/ethdb" - "github.com/ethereum/go-ethereum/event" -) - -func transaction(nonce uint64, gaslimit *big.Int, key *ecdsa.PrivateKey) *types.Transaction { - tx, _ := types.NewTransaction(nonce, common.Address{}, big.NewInt(100), gaslimit, big.NewInt(1), nil).SignECDSA(key) - return tx -} - -func setupTxPool() (*TxPool, *ecdsa.PrivateKey) { - db, _ := ethdb.NewMemDatabase() - statedb, _ := state.New(common.Hash{}, db) - - var m event.TypeMux - key, _ := crypto.GenerateKey() - newPool := NewTxPool(&m, func() (*state.StateDB, error) { return statedb, nil }, func() *big.Int { return big.NewInt(1000000) }) - newPool.resetState() - return newPool, key -} - -func TestInvalidTransactions(t *testing.T) { - pool, key := setupTxPool() - - tx := transaction(0, big.NewInt(100), key) - if err := pool.Add(tx); err != ErrNonExistentAccount { - t.Error("expected", ErrNonExistentAccount) - } - - from, _ := tx.From() - currentState, _ := pool.currentState() - currentState.AddBalance(from, big.NewInt(1)) - if err := pool.Add(tx); err != ErrInsufficientFunds { - t.Error("expected", ErrInsufficientFunds) - } - - balance := new(big.Int).Add(tx.Value(), new(big.Int).Mul(tx.Gas(), tx.GasPrice())) - currentState.AddBalance(from, balance) - if err := pool.Add(tx); err != ErrIntrinsicGas { - t.Error("expected", ErrIntrinsicGas, "got", err) - } - - currentState.SetNonce(from, 1) - currentState.AddBalance(from, big.NewInt(0xffffffffffffff)) - tx = transaction(0, big.NewInt(100000), key) - if err := pool.Add(tx); err != ErrNonce { - t.Error("expected", ErrNonce) - } - - tx = transaction(1, big.NewInt(100000), key) - pool.minGasPrice = big.NewInt(1000) - if err := pool.Add(tx); err != ErrCheap { - t.Error("expected", ErrCheap, "got", err) - } - - pool.SetLocal(tx) - if err := pool.Add(tx); err != nil { - t.Error("expected", nil, "got", err) - } -} - -func TestTransactionQueue(t *testing.T) { - pool, key := setupTxPool() - tx := transaction(0, big.NewInt(100), key) - from, _ := tx.From() - currentState, _ := pool.currentState() - currentState.AddBalance(from, big.NewInt(1000)) - pool.queueTx(tx.Hash(), tx) - - pool.checkQueue() - if len(pool.pending) != 1 { - t.Error("expected valid txs to be 1 is", len(pool.pending)) - } - - tx = transaction(1, big.NewInt(100), key) - from, _ = tx.From() - currentState.SetNonce(from, 2) - pool.queueTx(tx.Hash(), tx) - pool.checkQueue() - if _, ok := pool.pending[tx.Hash()]; ok { - t.Error("expected transaction to be in tx pool") - } - - if len(pool.queue[from]) > 0 { - t.Error("expected transaction queue to be empty. is", len(pool.queue[from])) - } - - pool, key = setupTxPool() - tx1 := transaction(0, big.NewInt(100), key) - tx2 := transaction(10, big.NewInt(100), key) - tx3 := transaction(11, big.NewInt(100), key) - from, _ = tx1.From() - currentState, _ = pool.currentState() - currentState.AddBalance(from, big.NewInt(1000)) - pool.queueTx(tx1.Hash(), tx1) - pool.queueTx(tx2.Hash(), tx2) - pool.queueTx(tx3.Hash(), tx3) - - pool.checkQueue() - - if len(pool.pending) != 1 { - t.Error("expected tx pool to be 1, got", len(pool.pending)) - } - if len(pool.queue[from]) != 2 { - t.Error("expected len(queue) == 2, got", len(pool.queue[from])) - } -} - -func TestRemoveTx(t *testing.T) { - pool, key := setupTxPool() - tx := transaction(0, big.NewInt(100), key) - from, _ := tx.From() - currentState, _ := pool.currentState() - currentState.AddBalance(from, big.NewInt(1)) - pool.queueTx(tx.Hash(), tx) - pool.addTx(tx.Hash(), from, tx) - if len(pool.queue) != 1 { - t.Error("expected queue to be 1, got", len(pool.queue)) - } - - if len(pool.pending) != 1 { - t.Error("expected txs to be 1, got", len(pool.pending)) - } - - pool.RemoveTx(tx.Hash()) - - if len(pool.queue) > 0 { - t.Error("expected queue to be 0, got", len(pool.queue)) - } - - if len(pool.pending) > 0 { - t.Error("expected txs to be 0, got", len(pool.pending)) - } -} - -func TestNegativeValue(t *testing.T) { - pool, key := setupTxPool() - - tx, _ := types.NewTransaction(0, common.Address{}, big.NewInt(-1), big.NewInt(100), big.NewInt(1), nil).SignECDSA(key) - from, _ := tx.From() - currentState, _ := pool.currentState() - currentState.AddBalance(from, big.NewInt(1)) - if err := pool.Add(tx); err != ErrNegativeValue { - t.Error("expected", ErrNegativeValue, "got", err) - } -} - -func TestTransactionChainFork(t *testing.T) { - pool, key := setupTxPool() - addr := crypto.PubkeyToAddress(key.PublicKey) - resetState := func() { - db, _ := ethdb.NewMemDatabase() - statedb, _ := state.New(common.Hash{}, db) - pool.currentState = func() (*state.StateDB, error) { return statedb, nil } - currentState, _ := pool.currentState() - currentState.AddBalance(addr, big.NewInt(100000000000000)) - pool.resetState() - } - resetState() - - tx := transaction(0, big.NewInt(100000), key) - if err := pool.add(tx); err != nil { - t.Error("didn't expect error", err) - } - pool.RemoveTransactions([]*types.Transaction{tx}) - - // reset the pool's internal state - resetState() - if err := pool.add(tx); err != nil { - t.Error("didn't expect error", err) - } -} - -func TestTransactionDoubleNonce(t *testing.T) { - pool, key := setupTxPool() - addr := crypto.PubkeyToAddress(key.PublicKey) - resetState := func() { - db, _ := ethdb.NewMemDatabase() - statedb, _ := state.New(common.Hash{}, db) - pool.currentState = func() (*state.StateDB, error) { return statedb, nil } - currentState, _ := pool.currentState() - currentState.AddBalance(addr, big.NewInt(100000000000000)) - pool.resetState() - } - resetState() - - tx := transaction(0, big.NewInt(100000), key) - tx2 := transaction(0, big.NewInt(1000000), key) - if err := pool.add(tx); err != nil { - t.Error("didn't expect error", err) - } - if err := pool.add(tx2); err != nil { - t.Error("didn't expect error", err) - } - - pool.checkQueue() - if len(pool.pending) != 2 { - t.Error("expected 2 pending txs. Got", len(pool.pending)) - } -} - -func TestMissingNonce(t *testing.T) { - pool, key := setupTxPool() - addr := crypto.PubkeyToAddress(key.PublicKey) - currentState, _ := pool.currentState() - currentState.AddBalance(addr, big.NewInt(100000000000000)) - tx := transaction(1, big.NewInt(100000), key) - if err := pool.add(tx); err != nil { - t.Error("didn't expect error", err) - } - if len(pool.pending) != 0 { - t.Error("expected 0 pending transactions, got", len(pool.pending)) - } - if len(pool.queue[addr]) != 1 { - t.Error("expected 1 queued transaction, got", len(pool.queue[addr])) - } -} - -func TestNonceRecovery(t *testing.T) { - const n = 10 - pool, key := setupTxPool() - addr := crypto.PubkeyToAddress(key.PublicKey) - currentState, _ := pool.currentState() - currentState.SetNonce(addr, n) - currentState.AddBalance(addr, big.NewInt(100000000000000)) - pool.resetState() - tx := transaction(n, big.NewInt(100000), key) - if err := pool.Add(tx); err != nil { - t.Error(err) - } - // simulate some weird re-order of transactions and missing nonce(s) - currentState.SetNonce(addr, n-1) - pool.resetState() - if fn := pool.pendingState.GetNonce(addr); fn != n+1 { - t.Errorf("expected nonce to be %d, got %d", n+1, fn) - } -} - -func TestRemovedTxEvent(t *testing.T) { - pool, key := setupTxPool() - tx := transaction(0, big.NewInt(1000000), key) - from, _ := tx.From() - currentState, _ := pool.currentState() - currentState.AddBalance(from, big.NewInt(1000000000000)) - pool.eventMux.Post(RemovedTransactionEvent{types.Transactions{tx}}) - pool.eventMux.Post(ChainHeadEvent{nil}) - if len(pool.pending) != 1 { - t.Error("expected 1 pending tx, got", len(pool.pending)) - } -} - -// Tests that if an account runs out of funds, any pending and queued transactions -// are dropped. -func TestTransactionDropping(t *testing.T) { - // Create a test account and fund it - pool, key := setupTxPool() - account, _ := transaction(0, big.NewInt(0), key).From() - - state, _ := pool.currentState() - state.AddBalance(account, big.NewInt(1000)) - - // Add some pending and some queued transactions - var ( - tx0 = transaction(0, big.NewInt(100), key) - tx1 = transaction(1, big.NewInt(200), key) - tx10 = transaction(10, big.NewInt(100), key) - tx11 = transaction(11, big.NewInt(200), key) - ) - pool.addTx(tx0.Hash(), account, tx0) - pool.addTx(tx1.Hash(), account, tx1) - pool.queueTx(tx10.Hash(), tx10) - pool.queueTx(tx11.Hash(), tx11) - - // Check that pre and post validations leave the pool as is - if len(pool.pending) != 2 { - t.Errorf("pending transaction mismatch: have %d, want %d", len(pool.pending), 2) - } - if len(pool.queue[account]) != 2 { - t.Errorf("queued transaction mismatch: have %d, want %d", len(pool.queue), 2) - } - pool.resetState() - if len(pool.pending) != 2 { - t.Errorf("pending transaction mismatch: have %d, want %d", len(pool.pending), 2) - } - if len(pool.queue[account]) != 2 { - t.Errorf("queued transaction mismatch: have %d, want %d", len(pool.queue), 2) - } - // Reduce the balance of the account, and check that invalidated transactions are dropped - state.AddBalance(account, big.NewInt(-750)) - pool.resetState() - - if _, ok := pool.pending[tx0.Hash()]; !ok { - t.Errorf("funded pending transaction missing: %v", tx0) - } - if _, ok := pool.pending[tx1.Hash()]; ok { - t.Errorf("out-of-fund pending transaction present: %v", tx1) - } - if _, ok := pool.queue[account][tx10.Hash()]; !ok { - t.Errorf("funded queued transaction missing: %v", tx10) - } - if _, ok := pool.queue[account][tx11.Hash()]; ok { - t.Errorf("out-of-fund queued transaction present: %v", tx11) - } -} - -// Tests that if a transaction is dropped from the current pending pool (e.g. out -// of fund), all consecutive (still valid, but not executable) transactions are -// postponed back into the future queue to prevent broadcating them. -func TestTransactionPostponing(t *testing.T) { - // Create a test account and fund it - pool, key := setupTxPool() - account, _ := transaction(0, big.NewInt(0), key).From() - - state, _ := pool.currentState() - state.AddBalance(account, big.NewInt(1000)) - - // Add a batch consecutive pending transactions for validation - txns := []*types.Transaction{} - for i := 0; i < 100; i++ { - var tx *types.Transaction - if i%2 == 0 { - tx = transaction(uint64(i), big.NewInt(100), key) - } else { - tx = transaction(uint64(i), big.NewInt(500), key) - } - pool.addTx(tx.Hash(), account, tx) - txns = append(txns, tx) - } - // Check that pre and post validations leave the pool as is - if len(pool.pending) != len(txns) { - t.Errorf("pending transaction mismatch: have %d, want %d", len(pool.pending), len(txns)) - } - if len(pool.queue[account]) != 0 { - t.Errorf("queued transaction mismatch: have %d, want %d", len(pool.queue), 0) - } - pool.resetState() - if len(pool.pending) != len(txns) { - t.Errorf("pending transaction mismatch: have %d, want %d", len(pool.pending), len(txns)) - } - if len(pool.queue[account]) != 0 { - t.Errorf("queued transaction mismatch: have %d, want %d", len(pool.queue), 0) - } - // Reduce the balance of the account, and check that transactions are reorganized - state.AddBalance(account, big.NewInt(-750)) - pool.resetState() - - if _, ok := pool.pending[txns[0].Hash()]; !ok { - t.Errorf("tx %d: valid and funded transaction missing from pending pool: %v", 0, txns[0]) - } - if _, ok := pool.queue[account][txns[0].Hash()]; ok { - t.Errorf("tx %d: valid and funded transaction present in future queue: %v", 0, txns[0]) - } - for i, tx := range txns[1:] { - if i%2 == 1 { - if _, ok := pool.pending[tx.Hash()]; ok { - t.Errorf("tx %d: valid but future transaction present in pending pool: %v", i+1, tx) - } - if _, ok := pool.queue[account][tx.Hash()]; !ok { - t.Errorf("tx %d: valid but future transaction missing from future queue: %v", i+1, tx) - } - } else { - if _, ok := pool.pending[tx.Hash()]; ok { - t.Errorf("tx %d: out-of-fund transaction present in pending pool: %v", i+1, tx) - } - if _, ok := pool.queue[account][tx.Hash()]; ok { - t.Errorf("tx %d: out-of-fund transaction present in future queue: %v", i+1, tx) - } - } - } -} - -// Tests that if the transaction count belonging to a single account goes above -// some threshold, the higher transactions are dropped to prevent DOS attacks. -func TestTransactionQueueLimiting(t *testing.T) { - // Create a test account and fund it - pool, key := setupTxPool() - account, _ := transaction(0, big.NewInt(0), key).From() - - state, _ := pool.currentState() - state.AddBalance(account, big.NewInt(1000000)) - - // Keep queuing up transactions and make sure all above a limit are dropped - for i := uint64(1); i <= maxQueued+5; i++ { - if err := pool.Add(transaction(i, big.NewInt(100000), key)); err != nil { - t.Fatalf("tx %d: failed to add transaction: %v", i, err) - } - if len(pool.pending) != 0 { - t.Errorf("tx %d: pending pool size mismatch: have %d, want %d", i, len(pool.pending), 0) - } - if i <= maxQueued { - if len(pool.queue[account]) != int(i) { - t.Errorf("tx %d: queue size mismatch: have %d, want %d", i, len(pool.queue[account]), i) - } - } else { - if len(pool.queue[account]) != maxQueued { - t.Errorf("tx %d: queue limit mismatch: have %d, want %d", i, len(pool.queue[account]), maxQueued) - } - } - } -} - -// Tests that even if the transaction count belonging to a single account goes -// above some threshold, as long as the transactions are executable, they are -// accepted. -func TestTransactionPendingLimiting(t *testing.T) { - // Create a test account and fund it - pool, key := setupTxPool() - account, _ := transaction(0, big.NewInt(0), key).From() - - state, _ := pool.currentState() - state.AddBalance(account, big.NewInt(1000000)) - - // Keep queuing up transactions and make sure all above a limit are dropped - for i := uint64(0); i < maxQueued+5; i++ { - if err := pool.Add(transaction(i, big.NewInt(100000), key)); err != nil { - t.Fatalf("tx %d: failed to add transaction: %v", i, err) - } - if len(pool.pending) != int(i)+1 { - t.Errorf("tx %d: pending pool size mismatch: have %d, want %d", i, len(pool.pending), i+1) - } - if len(pool.queue[account]) != 0 { - t.Errorf("tx %d: queue size mismatch: have %d, want %d", i, len(pool.queue[account]), 0) - } - } -} - -// Tests that the transaction limits are enforced the same way irrelevant whether -// the transactions are added one by one or in batches. -func TestTransactionQueueLimitingEquivalency(t *testing.T) { testTransactionLimitingEquivalency(t, 1) } -func TestTransactionPendingLimitingEquivalency(t *testing.T) { testTransactionLimitingEquivalency(t, 0) } - -func testTransactionLimitingEquivalency(t *testing.T, origin uint64) { - // Add a batch of transactions to a pool one by one - pool1, key1 := setupTxPool() - account1, _ := transaction(0, big.NewInt(0), key1).From() - state1, _ := pool1.currentState() - state1.AddBalance(account1, big.NewInt(1000000)) - - for i := uint64(0); i < maxQueued+5; i++ { - if err := pool1.Add(transaction(origin+i, big.NewInt(100000), key1)); err != nil { - t.Fatalf("tx %d: failed to add transaction: %v", i, err) - } - } - // Add a batch of transactions to a pool in one bit batch - pool2, key2 := setupTxPool() - account2, _ := transaction(0, big.NewInt(0), key2).From() - state2, _ := pool2.currentState() - state2.AddBalance(account2, big.NewInt(1000000)) - - txns := []*types.Transaction{} - for i := uint64(0); i < maxQueued+5; i++ { - txns = append(txns, transaction(origin+i, big.NewInt(100000), key2)) - } - pool2.AddTransactions(txns) - - // Ensure the batch optimization honors the same pool mechanics - if len(pool1.pending) != len(pool2.pending) { - t.Errorf("pending transaction count mismatch: one-by-one algo: %d, batch algo: %d", len(pool1.pending), len(pool2.pending)) - } - if len(pool1.queue[account1]) != len(pool2.queue[account2]) { - t.Errorf("queued transaction count mismatch: one-by-one algo: %d, batch algo: %d", len(pool1.queue[account1]), len(pool2.queue[account2])) - } -} - -// Benchmarks the speed of validating the contents of the pending queue of the -// transaction pool. -func BenchmarkValidatePool100(b *testing.B) { benchmarkValidatePool(b, 100) } -func BenchmarkValidatePool1000(b *testing.B) { benchmarkValidatePool(b, 1000) } -func BenchmarkValidatePool10000(b *testing.B) { benchmarkValidatePool(b, 10000) } - -func benchmarkValidatePool(b *testing.B, size int) { - // Add a batch of transactions to a pool one by one - pool, key := setupTxPool() - account, _ := transaction(0, big.NewInt(0), key).From() - state, _ := pool.currentState() - state.AddBalance(account, big.NewInt(1000000)) - - for i := 0; i < size; i++ { - tx := transaction(uint64(i), big.NewInt(100000), key) - pool.addTx(tx.Hash(), account, tx) - } - // Benchmark the speed of pool validation - b.ResetTimer() - for i := 0; i < b.N; i++ { - pool.validatePool() - } -} - -// Benchmarks the speed of scheduling the contents of the future queue of the -// transaction pool. -func BenchmarkCheckQueue100(b *testing.B) { benchmarkCheckQueue(b, 100) } -func BenchmarkCheckQueue1000(b *testing.B) { benchmarkCheckQueue(b, 1000) } -func BenchmarkCheckQueue10000(b *testing.B) { benchmarkCheckQueue(b, 10000) } - -func benchmarkCheckQueue(b *testing.B, size int) { - // Add a batch of transactions to a pool one by one - pool, key := setupTxPool() - account, _ := transaction(0, big.NewInt(0), key).From() - state, _ := pool.currentState() - state.AddBalance(account, big.NewInt(1000000)) - - for i := 0; i < size; i++ { - tx := transaction(uint64(1+i), big.NewInt(100000), key) - pool.queueTx(tx.Hash(), tx) - } - // Benchmark the speed of pool validation - b.ResetTimer() - for i := 0; i < b.N; i++ { - pool.checkQueue() - } -} diff --git a/core/tx_pool.go b/core/tx_pool.go new file mode 100644 index 000000000..b8fb4cd35 --- /dev/null +++ b/core/tx_pool.go @@ -0,0 +1,617 @@ +// Copyright 2014 The go-ethereum Authors +// This file is part of the go-ethereum library. +// +// The go-ethereum library is free software: you can redistribute it and/or modify +// it under the terms of the GNU Lesser General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. +// +// The go-ethereum library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU Lesser General Public License for more details. +// +// You should have received a copy of the GNU Lesser General Public License +// along with the go-ethereum library. If not, see . + +package core + +import ( + "errors" + "fmt" + "math/big" + "sort" + "sync" + "time" + + "github.com/ethereum/go-ethereum/common" + "github.com/ethereum/go-ethereum/core/state" + "github.com/ethereum/go-ethereum/core/types" + "github.com/ethereum/go-ethereum/event" + "github.com/ethereum/go-ethereum/logger" + "github.com/ethereum/go-ethereum/logger/glog" + "github.com/ethereum/go-ethereum/params" +) + +var ( + // Transaction Pool Errors + ErrInvalidSender = errors.New("Invalid sender") + ErrNonce = errors.New("Nonce too low") + ErrCheap = errors.New("Gas price too low for acceptance") + ErrBalance = errors.New("Insufficient balance") + ErrNonExistentAccount = errors.New("Account does not exist or account balance too low") + ErrInsufficientFunds = errors.New("Insufficient funds for gas * price + value") + ErrIntrinsicGas = errors.New("Intrinsic gas too low") + ErrGasLimit = errors.New("Exceeds block gas limit") + ErrNegativeValue = errors.New("Negative value") +) + +const ( + maxQueued = 64 // max limit of queued txs per address +) + +type stateFn func() (*state.StateDB, error) + +// TxPool contains all currently known transactions. Transactions +// enter the pool when they are received from the network or submitted +// locally. They exit the pool when they are included in the blockchain. +// +// The pool separates processable transactions (which can be applied to the +// current state) and future transactions. Transactions move between those +// two states over time as they are received and processed. +type TxPool struct { + quit chan bool // Quiting channel + currentState stateFn // The state function which will allow us to do some pre checkes + pendingState *state.ManagedState + gasLimit func() *big.Int // The current gas limit function callback + minGasPrice *big.Int + eventMux *event.TypeMux + events event.Subscription + localTx *txSet + mu sync.RWMutex + pending map[common.Hash]*types.Transaction // processable transactions + queue map[common.Address]map[common.Hash]*types.Transaction + + homestead bool +} + +func NewTxPool(eventMux *event.TypeMux, currentStateFn stateFn, gasLimitFn func() *big.Int) *TxPool { + pool := &TxPool{ + pending: make(map[common.Hash]*types.Transaction), + queue: make(map[common.Address]map[common.Hash]*types.Transaction), + quit: make(chan bool), + eventMux: eventMux, + currentState: currentStateFn, + gasLimit: gasLimitFn, + minGasPrice: new(big.Int), + pendingState: nil, + localTx: newTxSet(), + events: eventMux.Subscribe(ChainHeadEvent{}, GasPriceChanged{}, RemovedTransactionEvent{}), + } + + go pool.eventLoop() + + return pool +} + +func (pool *TxPool) eventLoop() { + // Track chain events. When a chain events occurs (new chain canon block) + // we need to know the new state. The new state will help us determine + // the nonces in the managed state + for ev := range pool.events.Chan() { + switch ev := ev.Data.(type) { + case ChainHeadEvent: + pool.mu.Lock() + if ev.Block != nil && params.IsHomestead(ev.Block.Number()) { + pool.homestead = true + } + + pool.resetState() + pool.mu.Unlock() + case GasPriceChanged: + pool.mu.Lock() + pool.minGasPrice = ev.Price + pool.mu.Unlock() + case RemovedTransactionEvent: + pool.AddTransactions(ev.Txs) + } + } +} + +func (pool *TxPool) resetState() { + currentState, err := pool.currentState() + if err != nil { + glog.V(logger.Info).Infoln("failed to get current state: %v", err) + return + } + managedState := state.ManageState(currentState) + if err != nil { + glog.V(logger.Info).Infoln("failed to get managed state: %v", err) + return + } + pool.pendingState = managedState + + // validate the pool of pending transactions, this will remove + // any transactions that have been included in the block or + // have been invalidated because of another transaction (e.g. + // higher gas price) + pool.validatePool() + + // Loop over the pending transactions and base the nonce of the new + // pending transaction set. + for _, tx := range pool.pending { + if addr, err := tx.From(); err == nil { + // Set the nonce. Transaction nonce can never be lower + // than the state nonce; validatePool took care of that. + if pool.pendingState.GetNonce(addr) <= tx.Nonce() { + pool.pendingState.SetNonce(addr, tx.Nonce()+1) + } + } + } + // Check the queue and move transactions over to the pending if possible + // or remove those that have become invalid + pool.checkQueue() +} + +func (pool *TxPool) Stop() { + close(pool.quit) + pool.events.Unsubscribe() + glog.V(logger.Info).Infoln("Transaction pool stopped") +} + +func (pool *TxPool) State() *state.ManagedState { + pool.mu.RLock() + defer pool.mu.RUnlock() + + return pool.pendingState +} + +func (pool *TxPool) Stats() (pending int, queued int) { + pool.mu.RLock() + defer pool.mu.RUnlock() + + pending = len(pool.pending) + for _, txs := range pool.queue { + queued += len(txs) + } + return +} + +// Content retrieves the data content of the transaction pool, returning all the +// pending as well as queued transactions, grouped by account and nonce. +func (pool *TxPool) Content() (map[common.Address]map[uint64][]*types.Transaction, map[common.Address]map[uint64][]*types.Transaction) { + pool.mu.RLock() + defer pool.mu.RUnlock() + + // Retrieve all the pending transactions and sort by account and by nonce + pending := make(map[common.Address]map[uint64][]*types.Transaction) + for _, tx := range pool.pending { + account, _ := tx.From() + + owned, ok := pending[account] + if !ok { + owned = make(map[uint64][]*types.Transaction) + pending[account] = owned + } + owned[tx.Nonce()] = append(owned[tx.Nonce()], tx) + } + // Retrieve all the queued transactions and sort by account and by nonce + queued := make(map[common.Address]map[uint64][]*types.Transaction) + for account, txs := range pool.queue { + owned := make(map[uint64][]*types.Transaction) + for _, tx := range txs { + owned[tx.Nonce()] = append(owned[tx.Nonce()], tx) + } + queued[account] = owned + } + return pending, queued +} + +// SetLocal marks a transaction as local, skipping gas price +// check against local miner minimum in the future +func (pool *TxPool) SetLocal(tx *types.Transaction) { + pool.mu.Lock() + defer pool.mu.Unlock() + pool.localTx.add(tx.Hash()) +} + +// validateTx checks whether a transaction is valid according +// to the consensus rules. +func (pool *TxPool) validateTx(tx *types.Transaction) error { + local := pool.localTx.contains(tx.Hash()) + // Drop transactions under our own minimal accepted gas price + if !local && pool.minGasPrice.Cmp(tx.GasPrice()) > 0 { + return ErrCheap + } + + currentState, err := pool.currentState() + if err != nil { + return err + } + + from, err := tx.From() + if err != nil { + return ErrInvalidSender + } + + // Make sure the account exist. Non existent accounts + // haven't got funds and well therefor never pass. + if !currentState.HasAccount(from) { + return ErrNonExistentAccount + } + + // Last but not least check for nonce errors + if currentState.GetNonce(from) > tx.Nonce() { + return ErrNonce + } + + // Check the transaction doesn't exceed the current + // block limit gas. + if pool.gasLimit().Cmp(tx.Gas()) < 0 { + return ErrGasLimit + } + + // Transactions can't be negative. This may never happen + // using RLP decoded transactions but may occur if you create + // a transaction using the RPC for example. + if tx.Value().Cmp(common.Big0) < 0 { + return ErrNegativeValue + } + + // Transactor should have enough funds to cover the costs + // cost == V + GP * GL + if currentState.GetBalance(from).Cmp(tx.Cost()) < 0 { + return ErrInsufficientFunds + } + + intrGas := IntrinsicGas(tx.Data(), MessageCreatesContract(tx), pool.homestead) + if tx.Gas().Cmp(intrGas) < 0 { + return ErrIntrinsicGas + } + + return nil +} + +// validate and queue transactions. +func (self *TxPool) add(tx *types.Transaction) error { + hash := tx.Hash() + + if self.pending[hash] != nil { + return fmt.Errorf("Known transaction (%x)", hash[:4]) + } + err := self.validateTx(tx) + if err != nil { + return err + } + self.queueTx(hash, tx) + + if glog.V(logger.Debug) { + var toname string + if to := tx.To(); to != nil { + toname = common.Bytes2Hex(to[:4]) + } else { + toname = "[NEW_CONTRACT]" + } + // we can ignore the error here because From is + // verified in ValidateTransaction. + f, _ := tx.From() + from := common.Bytes2Hex(f[:4]) + glog.Infof("(t) %x => %s (%v) %x\n", from, toname, tx.Value, hash) + } + + return nil +} + +// queueTx will queue an unknown transaction +func (self *TxPool) queueTx(hash common.Hash, tx *types.Transaction) { + from, _ := tx.From() // already validated + if self.queue[from] == nil { + self.queue[from] = make(map[common.Hash]*types.Transaction) + } + self.queue[from][hash] = tx +} + +// addTx will add a transaction to the pending (processable queue) list of transactions +func (pool *TxPool) addTx(hash common.Hash, addr common.Address, tx *types.Transaction) { + // init delayed since tx pool could have been started before any state sync + if pool.pendingState == nil { + pool.resetState() + } + + if _, ok := pool.pending[hash]; !ok { + pool.pending[hash] = tx + + // Increment the nonce on the pending state. This can only happen if + // the nonce is +1 to the previous one. + pool.pendingState.SetNonce(addr, tx.Nonce()+1) + // Notify the subscribers. This event is posted in a goroutine + // because it's possible that somewhere during the post "Remove transaction" + // gets called which will then wait for the global tx pool lock and deadlock. + go pool.eventMux.Post(TxPreEvent{tx}) + } +} + +// Add queues a single transaction in the pool if it is valid. +func (self *TxPool) Add(tx *types.Transaction) error { + self.mu.Lock() + defer self.mu.Unlock() + + if err := self.add(tx); err != nil { + return err + } + self.checkQueue() + return nil +} + +// AddTransactions attempts to queue all valid transactions in txs. +func (self *TxPool) AddTransactions(txs []*types.Transaction) { + self.mu.Lock() + defer self.mu.Unlock() + + for _, tx := range txs { + if err := self.add(tx); err != nil { + glog.V(logger.Debug).Infoln("tx error:", err) + } else { + h := tx.Hash() + glog.V(logger.Debug).Infof("tx %x\n", h[:4]) + } + } + + // check and validate the queueue + self.checkQueue() +} + +// GetTransaction returns a transaction if it is contained in the pool +// and nil otherwise. +func (tp *TxPool) GetTransaction(hash common.Hash) *types.Transaction { + // check the txs first + if tx, ok := tp.pending[hash]; ok { + return tx + } + // check queue + for _, txs := range tp.queue { + if tx, ok := txs[hash]; ok { + return tx + } + } + return nil +} + +// GetTransactions returns all currently processable transactions. +// The returned slice may be modified by the caller. +func (self *TxPool) GetTransactions() (txs types.Transactions) { + self.mu.Lock() + defer self.mu.Unlock() + + // check queue first + self.checkQueue() + // invalidate any txs + self.validatePool() + + txs = make(types.Transactions, len(self.pending)) + i := 0 + for _, tx := range self.pending { + txs[i] = tx + i++ + } + return txs +} + +// GetQueuedTransactions returns all non-processable transactions. +func (self *TxPool) GetQueuedTransactions() types.Transactions { + self.mu.RLock() + defer self.mu.RUnlock() + + var ret types.Transactions + for _, txs := range self.queue { + for _, tx := range txs { + ret = append(ret, tx) + } + } + sort.Sort(types.TxByNonce(ret)) + return ret +} + +// RemoveTransactions removes all given transactions from the pool. +func (self *TxPool) RemoveTransactions(txs types.Transactions) { + self.mu.Lock() + defer self.mu.Unlock() + for _, tx := range txs { + self.RemoveTx(tx.Hash()) + } +} + +// RemoveTx removes the transaction with the given hash from the pool. +func (pool *TxPool) RemoveTx(hash common.Hash) { + // delete from pending pool + delete(pool.pending, hash) + // delete from queue + for address, txs := range pool.queue { + if _, ok := txs[hash]; ok { + if len(txs) == 1 { + // if only one tx, remove entire address entry. + delete(pool.queue, address) + } else { + delete(txs, hash) + } + break + } + } +} + +// checkQueue moves transactions that have become processable to main pool. +func (pool *TxPool) checkQueue() { + // init delayed since tx pool could have been started before any state sync + if pool.pendingState == nil { + pool.resetState() + } + + var promote txQueue + for address, txs := range pool.queue { + currentState, err := pool.currentState() + if err != nil { + glog.Errorf("could not get current state: %v", err) + return + } + balance := currentState.GetBalance(address) + + var ( + guessedNonce = pool.pendingState.GetNonce(address) // nonce currently kept by the tx pool (pending state) + trueNonce = currentState.GetNonce(address) // nonce known by the last state + ) + promote = promote[:0] + for hash, tx := range txs { + // Drop processed or out of fund transactions + if tx.Nonce() < trueNonce || balance.Cmp(tx.Cost()) < 0 { + if glog.V(logger.Core) { + glog.Infof("removed tx (%v) from pool queue: low tx nonce or out of funds\n", tx) + } + delete(txs, hash) + continue + } + // Collect the remaining transactions for the next pass. + promote = append(promote, txQueueEntry{hash, address, tx}) + } + // Find the next consecutive nonce range starting at the current account nonce, + // pushing the guessed nonce forward if we add consecutive transactions. + sort.Sort(promote) + for i, entry := range promote { + // If we reached a gap in the nonces, enforce transaction limit and stop + if entry.Nonce() > guessedNonce { + if len(promote)-i > maxQueued { + if glog.V(logger.Debug) { + glog.Infof("Queued tx limit exceeded for %s. Tx %s removed\n", common.PP(address[:]), common.PP(entry.hash[:])) + } + for _, drop := range promote[i+maxQueued:] { + delete(txs, drop.hash) + } + } + break + } + // Otherwise promote the transaction and move the guess nonce if needed + pool.addTx(entry.hash, address, entry.Transaction) + delete(txs, entry.hash) + + if entry.Nonce() == guessedNonce { + guessedNonce++ + } + } + // Delete the entire queue entry if it became empty. + if len(txs) == 0 { + delete(pool.queue, address) + } + } +} + +// validatePool removes invalid and processed transactions from the main pool. +// If a transaction is removed for being invalid (e.g. out of funds), all sub- +// sequent (Still valid) transactions are moved back into the future queue. This +// is important to prevent a drained account from DOSing the network with non +// executable transactions. +func (pool *TxPool) validatePool() { + state, err := pool.currentState() + if err != nil { + glog.V(logger.Info).Infoln("failed to get current state: %v", err) + return + } + balanceCache := make(map[common.Address]*big.Int) + + // Clean up the pending pool, accumulating invalid nonces + gaps := make(map[common.Address]uint64) + + for hash, tx := range pool.pending { + sender, _ := tx.From() // err already checked + + // Perform light nonce and balance validation + balance := balanceCache[sender] + if balance == nil { + balance = state.GetBalance(sender) + balanceCache[sender] = balance + } + if past := state.GetNonce(sender) > tx.Nonce(); past || balance.Cmp(tx.Cost()) < 0 { + // Remove an already past it invalidated transaction + if glog.V(logger.Core) { + glog.Infof("removed tx (%v) from pool: low tx nonce or out of funds\n", tx) + } + delete(pool.pending, hash) + + // Track the smallest invalid nonce to postpone subsequent transactions + if !past { + if prev, ok := gaps[sender]; !ok || tx.Nonce() < prev { + gaps[sender] = tx.Nonce() + } + } + } + } + // Move all transactions after a gap back to the future queue + if len(gaps) > 0 { + for hash, tx := range pool.pending { + sender, _ := tx.From() + if gap, ok := gaps[sender]; ok && tx.Nonce() >= gap { + if glog.V(logger.Core) { + glog.Infof("postponed tx (%v) due to introduced gap\n", tx) + } + pool.queueTx(hash, tx) + delete(pool.pending, hash) + } + } + } +} + +type txQueue []txQueueEntry + +type txQueueEntry struct { + hash common.Hash + addr common.Address + *types.Transaction +} + +func (q txQueue) Len() int { return len(q) } +func (q txQueue) Swap(i, j int) { q[i], q[j] = q[j], q[i] } +func (q txQueue) Less(i, j int) bool { return q[i].Nonce() < q[j].Nonce() } + +// txSet represents a set of transaction hashes in which entries +// are automatically dropped after txSetDuration time +type txSet struct { + txMap map[common.Hash]struct{} + txOrd map[uint64]txOrdType + addPtr, delPtr uint64 +} + +const txSetDuration = time.Hour * 2 + +// txOrdType represents an entry in the time-ordered list of transaction hashes +type txOrdType struct { + hash common.Hash + time time.Time +} + +// newTxSet creates a new transaction set +func newTxSet() *txSet { + return &txSet{ + txMap: make(map[common.Hash]struct{}), + txOrd: make(map[uint64]txOrdType), + } +} + +// contains returns true if the set contains the given transaction hash +// (not thread safe, should be called from a locked environment) +func (self *txSet) contains(hash common.Hash) bool { + _, ok := self.txMap[hash] + return ok +} + +// add adds a transaction hash to the set, then removes entries older than txSetDuration +// (not thread safe, should be called from a locked environment) +func (self *txSet) add(hash common.Hash) { + self.txMap[hash] = struct{}{} + now := time.Now() + self.txOrd[self.addPtr] = txOrdType{hash: hash, time: now} + self.addPtr++ + delBefore := now.Add(-txSetDuration) + for self.delPtr < self.addPtr && self.txOrd[self.delPtr].time.Before(delBefore) { + delete(self.txMap, self.txOrd[self.delPtr].hash) + delete(self.txOrd, self.delPtr) + self.delPtr++ + } +} diff --git a/core/tx_pool_test.go b/core/tx_pool_test.go new file mode 100644 index 000000000..811e40111 --- /dev/null +++ b/core/tx_pool_test.go @@ -0,0 +1,537 @@ +// Copyright 2015 The go-ethereum Authors +// This file is part of the go-ethereum library. +// +// The go-ethereum library is free software: you can redistribute it and/or modify +// it under the terms of the GNU Lesser General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. +// +// The go-ethereum library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU Lesser General Public License for more details. +// +// You should have received a copy of the GNU Lesser General Public License +// along with the go-ethereum library. If not, see . + +package core + +import ( + "crypto/ecdsa" + "math/big" + "testing" + + "github.com/ethereum/go-ethereum/common" + "github.com/ethereum/go-ethereum/core/state" + "github.com/ethereum/go-ethereum/core/types" + "github.com/ethereum/go-ethereum/crypto" + "github.com/ethereum/go-ethereum/ethdb" + "github.com/ethereum/go-ethereum/event" +) + +func transaction(nonce uint64, gaslimit *big.Int, key *ecdsa.PrivateKey) *types.Transaction { + tx, _ := types.NewTransaction(nonce, common.Address{}, big.NewInt(100), gaslimit, big.NewInt(1), nil).SignECDSA(key) + return tx +} + +func setupTxPool() (*TxPool, *ecdsa.PrivateKey) { + db, _ := ethdb.NewMemDatabase() + statedb, _ := state.New(common.Hash{}, db) + + var m event.TypeMux + key, _ := crypto.GenerateKey() + newPool := NewTxPool(&m, func() (*state.StateDB, error) { return statedb, nil }, func() *big.Int { return big.NewInt(1000000) }) + newPool.resetState() + return newPool, key +} + +func TestInvalidTransactions(t *testing.T) { + pool, key := setupTxPool() + + tx := transaction(0, big.NewInt(100), key) + if err := pool.Add(tx); err != ErrNonExistentAccount { + t.Error("expected", ErrNonExistentAccount) + } + + from, _ := tx.From() + currentState, _ := pool.currentState() + currentState.AddBalance(from, big.NewInt(1)) + if err := pool.Add(tx); err != ErrInsufficientFunds { + t.Error("expected", ErrInsufficientFunds) + } + + balance := new(big.Int).Add(tx.Value(), new(big.Int).Mul(tx.Gas(), tx.GasPrice())) + currentState.AddBalance(from, balance) + if err := pool.Add(tx); err != ErrIntrinsicGas { + t.Error("expected", ErrIntrinsicGas, "got", err) + } + + currentState.SetNonce(from, 1) + currentState.AddBalance(from, big.NewInt(0xffffffffffffff)) + tx = transaction(0, big.NewInt(100000), key) + if err := pool.Add(tx); err != ErrNonce { + t.Error("expected", ErrNonce) + } + + tx = transaction(1, big.NewInt(100000), key) + pool.minGasPrice = big.NewInt(1000) + if err := pool.Add(tx); err != ErrCheap { + t.Error("expected", ErrCheap, "got", err) + } + + pool.SetLocal(tx) + if err := pool.Add(tx); err != nil { + t.Error("expected", nil, "got", err) + } +} + +func TestTransactionQueue(t *testing.T) { + pool, key := setupTxPool() + tx := transaction(0, big.NewInt(100), key) + from, _ := tx.From() + currentState, _ := pool.currentState() + currentState.AddBalance(from, big.NewInt(1000)) + pool.queueTx(tx.Hash(), tx) + + pool.checkQueue() + if len(pool.pending) != 1 { + t.Error("expected valid txs to be 1 is", len(pool.pending)) + } + + tx = transaction(1, big.NewInt(100), key) + from, _ = tx.From() + currentState.SetNonce(from, 2) + pool.queueTx(tx.Hash(), tx) + pool.checkQueue() + if _, ok := pool.pending[tx.Hash()]; ok { + t.Error("expected transaction to be in tx pool") + } + + if len(pool.queue[from]) > 0 { + t.Error("expected transaction queue to be empty. is", len(pool.queue[from])) + } + + pool, key = setupTxPool() + tx1 := transaction(0, big.NewInt(100), key) + tx2 := transaction(10, big.NewInt(100), key) + tx3 := transaction(11, big.NewInt(100), key) + from, _ = tx1.From() + currentState, _ = pool.currentState() + currentState.AddBalance(from, big.NewInt(1000)) + pool.queueTx(tx1.Hash(), tx1) + pool.queueTx(tx2.Hash(), tx2) + pool.queueTx(tx3.Hash(), tx3) + + pool.checkQueue() + + if len(pool.pending) != 1 { + t.Error("expected tx pool to be 1, got", len(pool.pending)) + } + if len(pool.queue[from]) != 2 { + t.Error("expected len(queue) == 2, got", len(pool.queue[from])) + } +} + +func TestRemoveTx(t *testing.T) { + pool, key := setupTxPool() + tx := transaction(0, big.NewInt(100), key) + from, _ := tx.From() + currentState, _ := pool.currentState() + currentState.AddBalance(from, big.NewInt(1)) + pool.queueTx(tx.Hash(), tx) + pool.addTx(tx.Hash(), from, tx) + if len(pool.queue) != 1 { + t.Error("expected queue to be 1, got", len(pool.queue)) + } + + if len(pool.pending) != 1 { + t.Error("expected txs to be 1, got", len(pool.pending)) + } + + pool.RemoveTx(tx.Hash()) + + if len(pool.queue) > 0 { + t.Error("expected queue to be 0, got", len(pool.queue)) + } + + if len(pool.pending) > 0 { + t.Error("expected txs to be 0, got", len(pool.pending)) + } +} + +func TestNegativeValue(t *testing.T) { + pool, key := setupTxPool() + + tx, _ := types.NewTransaction(0, common.Address{}, big.NewInt(-1), big.NewInt(100), big.NewInt(1), nil).SignECDSA(key) + from, _ := tx.From() + currentState, _ := pool.currentState() + currentState.AddBalance(from, big.NewInt(1)) + if err := pool.Add(tx); err != ErrNegativeValue { + t.Error("expected", ErrNegativeValue, "got", err) + } +} + +func TestTransactionChainFork(t *testing.T) { + pool, key := setupTxPool() + addr := crypto.PubkeyToAddress(key.PublicKey) + resetState := func() { + db, _ := ethdb.NewMemDatabase() + statedb, _ := state.New(common.Hash{}, db) + pool.currentState = func() (*state.StateDB, error) { return statedb, nil } + currentState, _ := pool.currentState() + currentState.AddBalance(addr, big.NewInt(100000000000000)) + pool.resetState() + } + resetState() + + tx := transaction(0, big.NewInt(100000), key) + if err := pool.add(tx); err != nil { + t.Error("didn't expect error", err) + } + pool.RemoveTransactions([]*types.Transaction{tx}) + + // reset the pool's internal state + resetState() + if err := pool.add(tx); err != nil { + t.Error("didn't expect error", err) + } +} + +func TestTransactionDoubleNonce(t *testing.T) { + pool, key := setupTxPool() + addr := crypto.PubkeyToAddress(key.PublicKey) + resetState := func() { + db, _ := ethdb.NewMemDatabase() + statedb, _ := state.New(common.Hash{}, db) + pool.currentState = func() (*state.StateDB, error) { return statedb, nil } + currentState, _ := pool.currentState() + currentState.AddBalance(addr, big.NewInt(100000000000000)) + pool.resetState() + } + resetState() + + tx := transaction(0, big.NewInt(100000), key) + tx2 := transaction(0, big.NewInt(1000000), key) + if err := pool.add(tx); err != nil { + t.Error("didn't expect error", err) + } + if err := pool.add(tx2); err != nil { + t.Error("didn't expect error", err) + } + + pool.checkQueue() + if len(pool.pending) != 2 { + t.Error("expected 2 pending txs. Got", len(pool.pending)) + } +} + +func TestMissingNonce(t *testing.T) { + pool, key := setupTxPool() + addr := crypto.PubkeyToAddress(key.PublicKey) + currentState, _ := pool.currentState() + currentState.AddBalance(addr, big.NewInt(100000000000000)) + tx := transaction(1, big.NewInt(100000), key) + if err := pool.add(tx); err != nil { + t.Error("didn't expect error", err) + } + if len(pool.pending) != 0 { + t.Error("expected 0 pending transactions, got", len(pool.pending)) + } + if len(pool.queue[addr]) != 1 { + t.Error("expected 1 queued transaction, got", len(pool.queue[addr])) + } +} + +func TestNonceRecovery(t *testing.T) { + const n = 10 + pool, key := setupTxPool() + addr := crypto.PubkeyToAddress(key.PublicKey) + currentState, _ := pool.currentState() + currentState.SetNonce(addr, n) + currentState.AddBalance(addr, big.NewInt(100000000000000)) + pool.resetState() + tx := transaction(n, big.NewInt(100000), key) + if err := pool.Add(tx); err != nil { + t.Error(err) + } + // simulate some weird re-order of transactions and missing nonce(s) + currentState.SetNonce(addr, n-1) + pool.resetState() + if fn := pool.pendingState.GetNonce(addr); fn != n+1 { + t.Errorf("expected nonce to be %d, got %d", n+1, fn) + } +} + +func TestRemovedTxEvent(t *testing.T) { + pool, key := setupTxPool() + tx := transaction(0, big.NewInt(1000000), key) + from, _ := tx.From() + currentState, _ := pool.currentState() + currentState.AddBalance(from, big.NewInt(1000000000000)) + pool.eventMux.Post(RemovedTransactionEvent{types.Transactions{tx}}) + pool.eventMux.Post(ChainHeadEvent{nil}) + if len(pool.pending) != 1 { + t.Error("expected 1 pending tx, got", len(pool.pending)) + } +} + +// Tests that if an account runs out of funds, any pending and queued transactions +// are dropped. +func TestTransactionDropping(t *testing.T) { + // Create a test account and fund it + pool, key := setupTxPool() + account, _ := transaction(0, big.NewInt(0), key).From() + + state, _ := pool.currentState() + state.AddBalance(account, big.NewInt(1000)) + + // Add some pending and some queued transactions + var ( + tx0 = transaction(0, big.NewInt(100), key) + tx1 = transaction(1, big.NewInt(200), key) + tx10 = transaction(10, big.NewInt(100), key) + tx11 = transaction(11, big.NewInt(200), key) + ) + pool.addTx(tx0.Hash(), account, tx0) + pool.addTx(tx1.Hash(), account, tx1) + pool.queueTx(tx10.Hash(), tx10) + pool.queueTx(tx11.Hash(), tx11) + + // Check that pre and post validations leave the pool as is + if len(pool.pending) != 2 { + t.Errorf("pending transaction mismatch: have %d, want %d", len(pool.pending), 2) + } + if len(pool.queue[account]) != 2 { + t.Errorf("queued transaction mismatch: have %d, want %d", len(pool.queue), 2) + } + pool.resetState() + if len(pool.pending) != 2 { + t.Errorf("pending transaction mismatch: have %d, want %d", len(pool.pending), 2) + } + if len(pool.queue[account]) != 2 { + t.Errorf("queued transaction mismatch: have %d, want %d", len(pool.queue), 2) + } + // Reduce the balance of the account, and check that invalidated transactions are dropped + state.AddBalance(account, big.NewInt(-750)) + pool.resetState() + + if _, ok := pool.pending[tx0.Hash()]; !ok { + t.Errorf("funded pending transaction missing: %v", tx0) + } + if _, ok := pool.pending[tx1.Hash()]; ok { + t.Errorf("out-of-fund pending transaction present: %v", tx1) + } + if _, ok := pool.queue[account][tx10.Hash()]; !ok { + t.Errorf("funded queued transaction missing: %v", tx10) + } + if _, ok := pool.queue[account][tx11.Hash()]; ok { + t.Errorf("out-of-fund queued transaction present: %v", tx11) + } +} + +// Tests that if a transaction is dropped from the current pending pool (e.g. out +// of fund), all consecutive (still valid, but not executable) transactions are +// postponed back into the future queue to prevent broadcating them. +func TestTransactionPostponing(t *testing.T) { + // Create a test account and fund it + pool, key := setupTxPool() + account, _ := transaction(0, big.NewInt(0), key).From() + + state, _ := pool.currentState() + state.AddBalance(account, big.NewInt(1000)) + + // Add a batch consecutive pending transactions for validation + txns := []*types.Transaction{} + for i := 0; i < 100; i++ { + var tx *types.Transaction + if i%2 == 0 { + tx = transaction(uint64(i), big.NewInt(100), key) + } else { + tx = transaction(uint64(i), big.NewInt(500), key) + } + pool.addTx(tx.Hash(), account, tx) + txns = append(txns, tx) + } + // Check that pre and post validations leave the pool as is + if len(pool.pending) != len(txns) { + t.Errorf("pending transaction mismatch: have %d, want %d", len(pool.pending), len(txns)) + } + if len(pool.queue[account]) != 0 { + t.Errorf("queued transaction mismatch: have %d, want %d", len(pool.queue), 0) + } + pool.resetState() + if len(pool.pending) != len(txns) { + t.Errorf("pending transaction mismatch: have %d, want %d", len(pool.pending), len(txns)) + } + if len(pool.queue[account]) != 0 { + t.Errorf("queued transaction mismatch: have %d, want %d", len(pool.queue), 0) + } + // Reduce the balance of the account, and check that transactions are reorganized + state.AddBalance(account, big.NewInt(-750)) + pool.resetState() + + if _, ok := pool.pending[txns[0].Hash()]; !ok { + t.Errorf("tx %d: valid and funded transaction missing from pending pool: %v", 0, txns[0]) + } + if _, ok := pool.queue[account][txns[0].Hash()]; ok { + t.Errorf("tx %d: valid and funded transaction present in future queue: %v", 0, txns[0]) + } + for i, tx := range txns[1:] { + if i%2 == 1 { + if _, ok := pool.pending[tx.Hash()]; ok { + t.Errorf("tx %d: valid but future transaction present in pending pool: %v", i+1, tx) + } + if _, ok := pool.queue[account][tx.Hash()]; !ok { + t.Errorf("tx %d: valid but future transaction missing from future queue: %v", i+1, tx) + } + } else { + if _, ok := pool.pending[tx.Hash()]; ok { + t.Errorf("tx %d: out-of-fund transaction present in pending pool: %v", i+1, tx) + } + if _, ok := pool.queue[account][tx.Hash()]; ok { + t.Errorf("tx %d: out-of-fund transaction present in future queue: %v", i+1, tx) + } + } + } +} + +// Tests that if the transaction count belonging to a single account goes above +// some threshold, the higher transactions are dropped to prevent DOS attacks. +func TestTransactionQueueLimiting(t *testing.T) { + // Create a test account and fund it + pool, key := setupTxPool() + account, _ := transaction(0, big.NewInt(0), key).From() + + state, _ := pool.currentState() + state.AddBalance(account, big.NewInt(1000000)) + + // Keep queuing up transactions and make sure all above a limit are dropped + for i := uint64(1); i <= maxQueued+5; i++ { + if err := pool.Add(transaction(i, big.NewInt(100000), key)); err != nil { + t.Fatalf("tx %d: failed to add transaction: %v", i, err) + } + if len(pool.pending) != 0 { + t.Errorf("tx %d: pending pool size mismatch: have %d, want %d", i, len(pool.pending), 0) + } + if i <= maxQueued { + if len(pool.queue[account]) != int(i) { + t.Errorf("tx %d: queue size mismatch: have %d, want %d", i, len(pool.queue[account]), i) + } + } else { + if len(pool.queue[account]) != maxQueued { + t.Errorf("tx %d: queue limit mismatch: have %d, want %d", i, len(pool.queue[account]), maxQueued) + } + } + } +} + +// Tests that even if the transaction count belonging to a single account goes +// above some threshold, as long as the transactions are executable, they are +// accepted. +func TestTransactionPendingLimiting(t *testing.T) { + // Create a test account and fund it + pool, key := setupTxPool() + account, _ := transaction(0, big.NewInt(0), key).From() + + state, _ := pool.currentState() + state.AddBalance(account, big.NewInt(1000000)) + + // Keep queuing up transactions and make sure all above a limit are dropped + for i := uint64(0); i < maxQueued+5; i++ { + if err := pool.Add(transaction(i, big.NewInt(100000), key)); err != nil { + t.Fatalf("tx %d: failed to add transaction: %v", i, err) + } + if len(pool.pending) != int(i)+1 { + t.Errorf("tx %d: pending pool size mismatch: have %d, want %d", i, len(pool.pending), i+1) + } + if len(pool.queue[account]) != 0 { + t.Errorf("tx %d: queue size mismatch: have %d, want %d", i, len(pool.queue[account]), 0) + } + } +} + +// Tests that the transaction limits are enforced the same way irrelevant whether +// the transactions are added one by one or in batches. +func TestTransactionQueueLimitingEquivalency(t *testing.T) { testTransactionLimitingEquivalency(t, 1) } +func TestTransactionPendingLimitingEquivalency(t *testing.T) { testTransactionLimitingEquivalency(t, 0) } + +func testTransactionLimitingEquivalency(t *testing.T, origin uint64) { + // Add a batch of transactions to a pool one by one + pool1, key1 := setupTxPool() + account1, _ := transaction(0, big.NewInt(0), key1).From() + state1, _ := pool1.currentState() + state1.AddBalance(account1, big.NewInt(1000000)) + + for i := uint64(0); i < maxQueued+5; i++ { + if err := pool1.Add(transaction(origin+i, big.NewInt(100000), key1)); err != nil { + t.Fatalf("tx %d: failed to add transaction: %v", i, err) + } + } + // Add a batch of transactions to a pool in one bit batch + pool2, key2 := setupTxPool() + account2, _ := transaction(0, big.NewInt(0), key2).From() + state2, _ := pool2.currentState() + state2.AddBalance(account2, big.NewInt(1000000)) + + txns := []*types.Transaction{} + for i := uint64(0); i < maxQueued+5; i++ { + txns = append(txns, transaction(origin+i, big.NewInt(100000), key2)) + } + pool2.AddTransactions(txns) + + // Ensure the batch optimization honors the same pool mechanics + if len(pool1.pending) != len(pool2.pending) { + t.Errorf("pending transaction count mismatch: one-by-one algo: %d, batch algo: %d", len(pool1.pending), len(pool2.pending)) + } + if len(pool1.queue[account1]) != len(pool2.queue[account2]) { + t.Errorf("queued transaction count mismatch: one-by-one algo: %d, batch algo: %d", len(pool1.queue[account1]), len(pool2.queue[account2])) + } +} + +// Benchmarks the speed of validating the contents of the pending queue of the +// transaction pool. +func BenchmarkValidatePool100(b *testing.B) { benchmarkValidatePool(b, 100) } +func BenchmarkValidatePool1000(b *testing.B) { benchmarkValidatePool(b, 1000) } +func BenchmarkValidatePool10000(b *testing.B) { benchmarkValidatePool(b, 10000) } + +func benchmarkValidatePool(b *testing.B, size int) { + // Add a batch of transactions to a pool one by one + pool, key := setupTxPool() + account, _ := transaction(0, big.NewInt(0), key).From() + state, _ := pool.currentState() + state.AddBalance(account, big.NewInt(1000000)) + + for i := 0; i < size; i++ { + tx := transaction(uint64(i), big.NewInt(100000), key) + pool.addTx(tx.Hash(), account, tx) + } + // Benchmark the speed of pool validation + b.ResetTimer() + for i := 0; i < b.N; i++ { + pool.validatePool() + } +} + +// Benchmarks the speed of scheduling the contents of the future queue of the +// transaction pool. +func BenchmarkCheckQueue100(b *testing.B) { benchmarkCheckQueue(b, 100) } +func BenchmarkCheckQueue1000(b *testing.B) { benchmarkCheckQueue(b, 1000) } +func BenchmarkCheckQueue10000(b *testing.B) { benchmarkCheckQueue(b, 10000) } + +func benchmarkCheckQueue(b *testing.B, size int) { + // Add a batch of transactions to a pool one by one + pool, key := setupTxPool() + account, _ := transaction(0, big.NewInt(0), key).From() + state, _ := pool.currentState() + state.AddBalance(account, big.NewInt(1000000)) + + for i := 0; i < size; i++ { + tx := transaction(uint64(1+i), big.NewInt(100000), key) + pool.queueTx(tx.Hash(), tx) + } + // Benchmark the speed of pool validation + b.ResetTimer() + for i := 0; i < b.N; i++ { + pool.checkQueue() + } +} diff --git a/core/types/transaction.go b/core/types/transaction.go index af952e450..0c9c1ce18 100644 --- a/core/types/transaction.go +++ b/core/types/transaction.go @@ -157,7 +157,14 @@ func (tx *Transaction) Size() common.StorageSize { return common.StorageSize(c) } -// From() caches the address, allowing it to be used regardless of +// From returns the address derived from the signature (V, R, S) using secp256k1 +// eliptic curve and an error if it failed deriving or upon an incorrect +// signature. +// +// From Uses the homestead consensus rules to determine whether the signature is +// valid. +// +// From caches the address, allowing it to be used regardless of // Frontier / Homestead. however, the first time called it runs // signature validations, so we need two versions. This makes it // easier to ensure backwards compatibility of things like package rpc @@ -168,6 +175,20 @@ func (tx *Transaction) From() (common.Address, error) { return doFrom(tx, true) } +// FromFrontier returns the address derived from the signature (V, R, S) using +// secp256k1 eliptic curve and an error if it failed deriving or upon an +// incorrect signature. +// +// FromFrantier uses the frontier consensus rules to determine whether the +// signature is valid. +// +// FromFrontier caches the address, allowing it to be used regardless of +// Frontier / Homestead. however, the first time called it runs +// signature validations, so we need two versions. This makes it +// easier to ensure backwards compatibility of things like package rpc +// where eth_getblockbynumber uses tx.From() and needs to work for +// both txs before and after the first homestead block. Signatures +// valid in homestead are a subset of valid ones in Frontier) func (tx *Transaction) FromFrontier() (common.Address, error) { return doFrom(tx, false) } diff --git a/core/vm/contract.go b/core/vm/contract.go index dac81a529..d23995218 100644 --- a/core/vm/contract.go +++ b/core/vm/contract.go @@ -26,7 +26,6 @@ import ( type ContractRef interface { ReturnGas(*big.Int, *big.Int) Address() common.Address - SetAddress(common.Address) Value() *big.Int SetCode([]byte) EachStorage(cb func(key, value []byte)) @@ -35,8 +34,12 @@ type ContractRef interface { // Contract represents an ethereum contract in the state database. It contains // the the contract code, calling arguments. Contract implements ContractRef type Contract struct { - caller ContractRef - self ContractRef + // CallerAddress is the result of the caller which initialised this + // contract. However when the "call method" is delegated this value + // needs to be initialised to that of the caller's caller. + CallerAddress common.Address + caller ContractRef + self ContractRef jumpdests destinations // result of JUMPDEST analysis. @@ -51,9 +54,9 @@ type Contract struct { DelegateCall bool } -// Create a new context for the given data items. +// NewContract returns a new contract environment for the execution of EVM. func NewContract(caller ContractRef, object ContractRef, value, gas, price *big.Int) *Contract { - c := &Contract{caller: caller, self: object, Args: nil} + c := &Contract{CallerAddress: caller.Address(), caller: caller, self: object, Args: nil} if parent, ok := caller.(*Contract); ok { // Reuse JUMPDEST analysis from parent context if available. @@ -74,6 +77,16 @@ func NewContract(caller ContractRef, object ContractRef, value, gas, price *big. return c } +// 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. + c.CallerAddress = c.caller.(*Contract).CallerAddress + return c +} + // GetOp returns the n'th element in the contract's byte array func (c *Contract) GetOp(n uint64) OpCode { return OpCode(c.GetByte(n)) @@ -88,13 +101,19 @@ func (c *Contract) GetByte(n uint64) byte { return 0 } -// Return returns the given ret argument and returns any remaining gas to the -// caller -func (c *Contract) Return(ret []byte) []byte { +// Caller returns the caller of the contract. +// +// Caller will recursively call caller when the contract is a delegate +// call, including that of caller's caller. +func (c *Contract) Caller() common.Address { + return c.CallerAddress +} + +// Finalise finalises the contract and returning any remaining gas to the original +// caller. +func (c *Contract) Finalise() { // Return the remaining gas to the caller c.caller.ReturnGas(c.Gas, c.Price) - - return ret } // UseGas attempts the use gas and subtracts it and returns true on success @@ -118,11 +137,6 @@ func (c *Contract) Address() common.Address { return c.self.Address() } -// SetAddress sets the contracts address -func (c *Contract) SetAddress(addr common.Address) { - c.self.SetAddress(addr) -} - // Value returns the contracts value (sent to it from it's caller) func (c *Contract) Value() *big.Int { return c.value diff --git a/core/vm/environment.go b/core/vm/environment.go index dc60af2ca..a58e3ba2b 100644 --- a/core/vm/environment.go +++ b/core/vm/environment.go @@ -121,7 +121,6 @@ type Account interface { SetNonce(uint64) Balance() *big.Int Address() common.Address - SetAddress(common.Address) ReturnGas(*big.Int, *big.Int) SetCode([]byte) EachStorage(cb func(key, value []byte)) diff --git a/core/vm/instructions.go b/core/vm/instructions.go index 9d3d4e6fe..26f7671ff 100644 --- a/core/vm/instructions.go +++ b/core/vm/instructions.go @@ -337,13 +337,7 @@ func opOrigin(instr instruction, pc *uint64, env Environment, contract *Contract } func opCaller(instr instruction, pc *uint64, env Environment, contract *Contract, memory *Memory, stack *stack) { - var bigAddr *big.Int - if contract.DelegateCall { - bigAddr = env.Origin().Big() - } else { - bigAddr = contract.caller.Address().Big() - } - stack.push(bigAddr) + stack.push(contract.Caller().Big()) } func opCallValue(instr instruction, pc *uint64, env Environment, contract *Contract, memory *Memory, stack *stack) { @@ -514,6 +508,25 @@ func opGas(instr instruction, pc *uint64, env Environment, contract *Contract, m } func opCreate(instr instruction, pc *uint64, env Environment, contract *Contract, memory *Memory, stack *stack) { + var ( + value = stack.pop() + offset, size = stack.pop(), stack.pop() + input = memory.Get(offset.Int64(), size.Int64()) + gas = new(big.Int).Set(contract.Gas) + ) + contract.UseGas(contract.Gas) + _, addr, suberr := env.Create(contract, input, gas, contract.Price, value) + // Push item on the stack based on the returned error. If the ruleset is + // homestead we must check for CodeStoreOutOfGasError (homestead only + // rule) and treat as an error, if the ruleset is frontier we must + // ignore this error and pretend the operation was successful. + if params.IsHomestead(env.BlockNumber()) && suberr == CodeStoreOutOfGasError { + stack.push(new(big.Int)) + } else if suberr != nil && suberr != CodeStoreOutOfGasError { + stack.push(new(big.Int)) + } else { + stack.push(addr.Big()) + } } func opCall(instr instruction, pc *uint64, env Environment, contract *Contract, memory *Memory, stack *stack) { diff --git a/core/vm/jit.go b/core/vm/jit.go index 1aa7d7ef2..504aab523 100644 --- a/core/vm/jit.go +++ b/core/vm/jit.go @@ -275,6 +275,11 @@ func CompileProgram(program *Program) (err error) { program.addInstr(op, pc, opGas, nil) case CREATE: program.addInstr(op, pc, opCreate, nil) + case DELEGATECALL: + // Instruction added regardless of homestead phase. + // Homestead (and execution of the opcode) is checked during + // runtime. + program.addInstr(op, pc, opDelegateCall, nil) case CALL: program.addInstr(op, pc, opCall, nil) case CALLCODE: @@ -317,10 +322,14 @@ func runProgram(program *Program, pcstart uint64, mem *Memory, stack *stack, env }() } + homestead := params.IsHomestead(env.BlockNumber()) for pc < uint64(len(program.instructions)) { instrCount++ instr := program.instructions[pc] + if instr.Op() == DELEGATECALL && !homestead { + return nil, fmt.Errorf("Invalid opcode 0x%x", instr.Op()) + } ret, err := instr.do(program, &pc, env, contract, mem, stack) if err != nil { @@ -328,13 +337,13 @@ func runProgram(program *Program, pcstart uint64, mem *Memory, stack *stack, env } if instr.halts() { - return contract.Return(ret), nil + return ret, nil } } contract.Input = nil - return contract.Return(nil), nil + return nil, nil } // validDest checks if the given distination is a valid one given the @@ -457,7 +466,6 @@ func jitCalculateGasAndSize(env Environment, contract *Contract, instr instructi gas.Add(gas, stack.data[stack.len()-1]) if op == CALL { - //if env.Db().GetStateObject(common.BigToAddress(stack.data[stack.len()-2])) == nil { if !env.Db().Exist(common.BigToAddress(stack.data[stack.len()-2])) { gas.Add(gas, params.CallNewAccountGas) } @@ -470,6 +478,13 @@ func jitCalculateGasAndSize(env Environment, contract *Contract, instr instructi x := calcMemSize(stack.data[stack.len()-6], stack.data[stack.len()-7]) y := calcMemSize(stack.data[stack.len()-4], stack.data[stack.len()-5]) + newMemSize = common.BigMax(x, y) + case DELEGATECALL: + gas.Add(gas, stack.data[stack.len()-1]) + + x := calcMemSize(stack.data[stack.len()-5], stack.data[stack.len()-6]) + y := calcMemSize(stack.data[stack.len()-3], stack.data[stack.len()-4]) + newMemSize = common.BigMax(x, y) } quadMemGas(mem, newMemSize, gas) diff --git a/core/vm/jit_test.go b/core/vm/jit_test.go index 8c50ed0f5..e8e078a46 100644 --- a/core/vm/jit_test.go +++ b/core/vm/jit_test.go @@ -127,6 +127,8 @@ type account struct{} func (account) SubBalance(amount *big.Int) {} func (account) AddBalance(amount *big.Int) {} +func (account) SetAddress(common.Address) {} +func (account) Value() *big.Int { return nil } func (account) SetBalance(*big.Int) {} func (account) SetNonce(uint64) {} func (account) Balance() *big.Int { return nil } @@ -206,3 +208,6 @@ func (self *Env) CallCode(caller ContractRef, addr common.Address, data []byte, func (self *Env) Create(caller ContractRef, data []byte, gas, price, value *big.Int) ([]byte, common.Address, error) { return nil, common.Address{}, nil } +func (self *Env) DelegateCall(me ContractRef, addr common.Address, data []byte, gas, price *big.Int) ([]byte, error) { + return nil, nil +} diff --git a/core/vm/jump_table.go b/core/vm/jump_table.go index 222c93854..37d7bb160 100644 --- a/core/vm/jump_table.go +++ b/core/vm/jump_table.go @@ -1,13 +1,29 @@ package vm -import "math/big" +import ( + "math/big" + + "github.com/ethereum/go-ethereum/params" +) type jumpPtr struct { fn instrFn valid bool } -var jumpTable [256]jumpPtr +type vmJumpTable [256]jumpPtr + +func (jt vmJumpTable) init(blockNumber *big.Int) { + // when initialising a new VM execution we must first check the homestead + // changes. + if params.IsHomestead(blockNumber) { + jumpTable[DELEGATECALL] = jumpPtr{opDelegateCall, true} + } else { + jumpTable[DELEGATECALL] = jumpPtr{nil, false} + } +} + +var jumpTable vmJumpTable func init() { jumpTable[ADD] = jumpPtr{opAdd, true} @@ -62,10 +78,9 @@ func init() { jumpTable[PC] = jumpPtr{nil, true} jumpTable[MSIZE] = jumpPtr{opMsize, true} jumpTable[GAS] = jumpPtr{opGas, true} - jumpTable[CREATE] = jumpPtr{nil, true} + jumpTable[CREATE] = jumpPtr{opCreate, true} jumpTable[CALL] = jumpPtr{opCall, true} jumpTable[CALLCODE] = jumpPtr{opCallCode, true} - jumpTable[DELEGATECALL] = jumpPtr{opDelegateCall, true} jumpTable[LOG0] = jumpPtr{makeLog(0), true} jumpTable[LOG1] = jumpPtr{makeLog(1), true} jumpTable[LOG2] = jumpPtr{makeLog(2), true} diff --git a/core/vm/jump_table_test.go b/core/vm/jump_table_test.go new file mode 100644 index 000000000..98d34bef2 --- /dev/null +++ b/core/vm/jump_table_test.go @@ -0,0 +1,24 @@ +package vm + +import ( + "math/big" + "testing" + + "github.com/ethereum/go-ethereum/params" +) + +func TestInit(t *testing.T) { + params.HomesteadBlock = big.NewInt(1) + + jumpTable.init(big.NewInt(0)) + if jumpTable[DELEGATECALL].valid { + t.Error("Expected DELEGATECALL not to be present") + } + + for _, n := range []int64{1, 2, 100} { + jumpTable.init(big.NewInt(n)) + if !jumpTable[DELEGATECALL].valid { + t.Error("Expected DELEGATECALL to be present for block", n) + } + } +} diff --git a/core/vm/opcodes.go b/core/vm/opcodes.go index 00593ae95..7d861f1de 100644 --- a/core/vm/opcodes.go +++ b/core/vm/opcodes.go @@ -404,6 +404,7 @@ var stringToOp = map[string]OpCode{ "CALLDATALOAD": CALLDATALOAD, "CALLDATASIZE": CALLDATASIZE, "CALLDATACOPY": CALLDATACOPY, + "DELEGATECALL": DELEGATECALL, "CODESIZE": CODESIZE, "CODECOPY": CODECOPY, "GASPRICE": GASPRICE, diff --git a/core/vm/vm.go b/core/vm/vm.go index 863b2cc0d..320135ff2 100644 --- a/core/vm/vm.go +++ b/core/vm/vm.go @@ -35,6 +35,9 @@ type Vm struct { // New returns a new Vm func New(env Environment) *Vm { + // init the jump table. Also prepares the homestead changes + jumpTable.init(env.BlockNumber()) + return &Vm{env: env} } @@ -43,16 +46,6 @@ func (self *Vm) Run(contract *Contract, input []byte) (ret []byte, err error) { self.env.SetDepth(self.env.Depth() + 1) defer self.env.SetDepth(self.env.Depth() - 1) - // User defer pattern to check for an error and, based on the error being nil or not, use all gas and return. - defer func() { - if err != nil { - // In case of a VM exception (known exceptions) all gas consumed (panics NOT included). - contract.UseGas(contract.Gas) - - ret = contract.Return(nil) - } - }() - if contract.CodeAddr != nil { if p := Precompiled[contract.CodeAddr.Str()]; p != nil { return self.RunPrecompiled(p, input, contract) @@ -61,7 +54,7 @@ func (self *Vm) Run(contract *Contract, input []byte) (ret []byte, err error) { // Don't bother with the execution if there's no code. if len(contract.Code) == 0 { - return contract.Return(nil), nil + return nil, nil } var ( @@ -199,46 +192,17 @@ func (self *Vm) Run(contract *Contract, input []byte) (ret []byte, err error) { continue } - case CREATE: - var ( - value = stack.pop() - offset, size = stack.pop(), stack.pop() - input = mem.Get(offset.Int64(), size.Int64()) - gas = new(big.Int).Set(contract.Gas) - addr common.Address - ret []byte - suberr error - ) - contract.UseGas(contract.Gas) - ret, addr, suberr = self.env.Create(contract, input, gas, contract.Price, value) - if suberr != nil { - stack.push(new(big.Int)) - } else { - // gas < len(ret) * Createinstr.dataGas == NO_CODE - dataGas := big.NewInt(int64(len(ret))) - dataGas.Mul(dataGas, params.CreateDataGas) - if contract.UseGas(dataGas) { - self.env.Db().SetCode(addr, ret) - } else { - if params.IsHomestead(self.env.BlockNumber()) { - stack.push(new(big.Int)) - return nil, CodeStoreOutOfGasError - } - } - stack.push(addr.Big()) - } - case RETURN: offset, size := stack.pop(), stack.pop() ret := mem.GetPtr(offset.Int64(), size.Int64()) - return contract.Return(ret), nil + return ret, nil case SUICIDE: opSuicide(instruction{}, nil, self.env, contract, mem, stack) fallthrough case STOP: // Stop the contract - return contract.Return(nil), nil + return nil, nil } } } else { @@ -359,7 +323,6 @@ func calculateGasAndSize(env Environment, contract *Contract, caller ContractRef gas.Add(gas, stack.data[stack.len()-1]) if op == CALL { - //if env.Db().GetStateObject(common.BigToAddress(stack.data[stack.len()-2])) == nil { if !env.Db().Exist(common.BigToAddress(stack.data[stack.len()-2])) { gas.Add(gas, params.CallNewAccountGas) } @@ -392,7 +355,7 @@ func (self *Vm) RunPrecompiled(p *PrecompiledAccount, input []byte, contract *Co if contract.UseGas(gas) { ret = p.Call(input) - return contract.Return(ret), nil + return ret, nil } else { return nil, OutOfGasError } -- cgit