From a2f23ca9b181fa4409fdee3076316f3127038b9b Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?P=C3=A9ter=20Szil=C3=A1gyi?= Date: Tue, 16 May 2017 22:07:27 +0300 Subject: cmd, core, eth, miner: remove txpool gas price limits (#14442) --- core/events.go | 4 - core/tx_list.go | 166 ++++++++++++++++++++++++++++++- core/tx_pool.go | 269 +++++++++++++++++++++++++++++++++++++-------------- core/tx_pool_test.go | 261 +++++++++++++++++++++++++++++++++++++++++++++---- 4 files changed, 599 insertions(+), 101 deletions(-) (limited to 'core') diff --git a/core/events.go b/core/events.go index 106b52c80..ce1f5aebc 100644 --- a/core/events.go +++ b/core/events.go @@ -17,8 +17,6 @@ package core import ( - "math/big" - "github.com/ethereum/go-ethereum/common" "github.com/ethereum/go-ethereum/core/types" ) @@ -67,8 +65,6 @@ type ChainUncleEvent struct { type ChainHeadEvent struct{ Block *types.Block } -type GasPriceChanged struct{ Price *big.Int } - // Mining operation events type StartMining struct{} type TopMining struct{} diff --git a/core/tx_list.go b/core/tx_list.go index 535cb9dd6..eb380da0b 100644 --- a/core/tx_list.go +++ b/core/tx_list.go @@ -22,7 +22,9 @@ import ( "math/big" "sort" + "github.com/ethereum/go-ethereum/common" "github.com/ethereum/go-ethereum/core/types" + "github.com/ethereum/go-ethereum/log" ) // nonceHeap is a heap.Interface implementation over 64bit unsigned integers for @@ -53,11 +55,11 @@ type txSortedMap struct { cache types.Transactions // Cache of the transactions already sorted } -// newTxSortedMap creates a new sorted transaction map. +// newTxSortedMap creates a new nonce-sorted transaction map. func newTxSortedMap() *txSortedMap { return &txSortedMap{ items: make(map[uint64]*types.Transaction), - index: &nonceHeap{}, + index: new(nonceHeap), } } @@ -233,6 +235,12 @@ func newTxList(strict bool) *txList { } } +// Overlaps returns whether the transaction specified has the same nonce as one +// already contained within the list. +func (l *txList) Overlaps(tx *types.Transaction) bool { + return l.txs.Get(tx.Nonce()) != nil +} + // Add tries to insert a new transaction into the list, returning whether the // transaction was accepted, and if yes, any previous transaction it replaced. // @@ -241,8 +249,11 @@ func newTxList(strict bool) *txList { func (l *txList) Add(tx *types.Transaction) (bool, *types.Transaction) { // If there's an older better transaction, abort old := l.txs.Get(tx.Nonce()) - if old != nil && old.GasPrice().Cmp(tx.GasPrice()) >= 0 { - return false, nil + if old != nil { + threshold := new(big.Int).Div(new(big.Int).Mul(old.GasPrice(), big.NewInt(100+minPriceBumpPercent)), big.NewInt(100)) + if threshold.Cmp(tx.GasPrice()) >= 0 { + return false, nil + } } // Otherwise overwrite the old transaction with the current one l.txs.Put(tx) @@ -340,3 +351,150 @@ func (l *txList) Empty() bool { func (l *txList) Flatten() types.Transactions { return l.txs.Flatten() } + +// priceHeap is a heap.Interface implementation over transactions for retrieving +// price-sorted transactions to discard when the pool fills up. +type priceHeap []*types.Transaction + +func (h priceHeap) Len() int { return len(h) } +func (h priceHeap) Less(i, j int) bool { return h[i].GasPrice().Cmp(h[j].GasPrice()) < 0 } +func (h priceHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] } + +func (h *priceHeap) Push(x interface{}) { + *h = append(*h, x.(*types.Transaction)) +} + +func (h *priceHeap) Pop() interface{} { + old := *h + n := len(old) + x := old[n-1] + *h = old[0 : n-1] + return x +} + +// txPricedList is a price-sorted heap to allow operating on transactions pool +// contents in a price-incrementing way. +type txPricedList struct { + all *map[common.Hash]*types.Transaction // Pointer to the map of all transactions + items *priceHeap // Heap of prices of all the stored transactions + stales int // Number of stale price points to (re-heap trigger) +} + +// newTxPricedList creates a new price-sorted transaction heap. +func newTxPricedList(all *map[common.Hash]*types.Transaction) *txPricedList { + return &txPricedList{ + all: all, + items: new(priceHeap), + } +} + +// Put inserts a new transaction into the heap. +func (l *txPricedList) Put(tx *types.Transaction) { + heap.Push(l.items, tx) +} + +// Removed notifies the prices transaction list that an old transaction dropped +// from the pool. The list will just keep a counter of stale objects and update +// the heap if a large enough ratio of transactions go stale. +func (l *txPricedList) Removed() { + // Bump the stale counter, but exit if still too low (< 25%) + l.stales++ + if l.stales <= len(*l.items)/4 { + return + } + // Seems we've reached a critical number of stale transactions, reheap + reheap := make(priceHeap, 0, len(*l.all)) + + l.stales, l.items = 0, &reheap + for _, tx := range *l.all { + *l.items = append(*l.items, tx) + } + heap.Init(l.items) +} + +// Discard finds all the transactions below the given price threshold, drops them +// from the priced list and returs them for further removal from the entire pool. +func (l *txPricedList) Cap(threshold *big.Int, local *txSet) types.Transactions { + drop := make(types.Transactions, 0, 128) // Remote underpriced transactions to drop + save := make(types.Transactions, 0, 64) // Local underpriced transactions to keep + + for len(*l.items) > 0 { + // Discard stale transactions if found during cleanup + tx := heap.Pop(l.items).(*types.Transaction) + + hash := tx.Hash() + if _, ok := (*l.all)[hash]; !ok { + l.stales-- + continue + } + // Stop the discards if we've reached the threshold + if tx.GasPrice().Cmp(threshold) >= 0 { + break + } + // Non stale transaction found, discard unless local + if local.contains(hash) { + save = append(save, tx) + } else { + drop = append(drop, tx) + } + } + for _, tx := range save { + heap.Push(l.items, tx) + } + return drop +} + +// Underpriced checks whether a transaction is cheaper than (or as cheap as) the +// lowest priced transaction currently being tracked. +func (l *txPricedList) Underpriced(tx *types.Transaction, local *txSet) bool { + // Local transactions cannot be underpriced + if local.contains(tx.Hash()) { + return false + } + // Discard stale price points if found at the heap start + for len(*l.items) > 0 { + head := []*types.Transaction(*l.items)[0] + if _, ok := (*l.all)[head.Hash()]; !ok { + l.stales-- + heap.Pop(l.items) + continue + } + break + } + // Check if the transaction is underpriced or not + if len(*l.items) == 0 { + log.Error("Pricing query for empty pool") // This cannot happen, print to catch programming errors + return false + } + cheapest := []*types.Transaction(*l.items)[0] + return cheapest.GasPrice().Cmp(tx.GasPrice()) >= 0 +} + +// Discard finds a number of most underpriced transactions, removes them from the +// priced list and returs them for further removal from the entire pool. +func (l *txPricedList) Discard(count int, local *txSet) types.Transactions { + drop := make(types.Transactions, 0, count) // Remote underpriced transactions to drop + save := make(types.Transactions, 0, 64) // Local underpriced transactions to keep + + for len(*l.items) > 0 && count > 0 { + // Discard stale transactions if found during cleanup + tx := heap.Pop(l.items).(*types.Transaction) + + hash := tx.Hash() + if _, ok := (*l.all)[hash]; !ok { + l.stales-- + continue + } + // Non stale transaction found, discard unless local + if local.contains(hash) { + save = append(save, tx) + } else { + drop = append(drop, tx) + count-- + } + } + for _, tx := range save { + heap.Push(l.items, tx) + } + return drop +} diff --git a/core/tx_pool.go b/core/tx_pool.go index 49bd81e48..a0373ca7d 100644 --- a/core/tx_pool.go +++ b/core/tx_pool.go @@ -36,23 +36,26 @@ import ( 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") - 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") + ErrInvalidSender = errors.New("invalid sender") + ErrNonce = errors.New("nonce too low") + ErrUnderpriced = errors.New("transaction underpriced") + ErrReplaceUnderpriced = errors.New("replacement transaction underpriced") + ErrBalance = errors.New("insufficient balance") + 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") ) var ( - minPendingPerAccount = uint64(16) // Min number of guaranteed transaction slots per address - maxPendingTotal = uint64(4096) // Max limit of pending transactions from all accounts (soft) - maxQueuedPerAccount = uint64(64) // Max limit of queued transactions per address - maxQueuedInTotal = uint64(1024) // Max limit of queued transactions from all accounts - maxQueuedLifetime = 3 * time.Hour // Max amount of time transactions from idle accounts are queued - evictionInterval = time.Minute // Time interval to check for evictable transactions + minPendingPerAccount = uint64(16) // Min number of guaranteed transaction slots per address + maxPendingTotal = uint64(4096) // Max limit of pending transactions from all accounts (soft) + maxQueuedPerAccount = uint64(64) // Max limit of queued transactions per address + maxQueuedTotal = uint64(1024) // Max limit of queued transactions from all accounts + maxQueuedLifetime = 3 * time.Hour // Max amount of time transactions from idle accounts are queued + minPriceBumpPercent = int64(10) // Minimum price bump needed to replace an old transaction + evictionInterval = time.Minute // Time interval to check for evictable transactions + statsReportInterval = 8 * time.Second // Time interval to report transaction pool stats ) var ( @@ -69,7 +72,8 @@ var ( queuedNofundsCounter = metrics.NewCounter("txpool/queued/nofunds") // Dropped due to out-of-funds // General tx metrics - invalidTxCounter = metrics.NewCounter("txpool/invalid") + invalidTxCounter = metrics.NewCounter("txpool/invalid") + underpricedTxCounter = metrics.NewCounter("txpool/underpriced") ) type stateFn func() (*state.StateDB, error) @@ -86,17 +90,18 @@ type TxPool struct { currentState stateFn // The state function which will allow us to do some pre checks pendingState *state.ManagedState gasLimit func() *big.Int // The current gas limit function callback - minGasPrice *big.Int + gasPrice *big.Int eventMux *event.TypeMux events *event.TypeMuxSubscription - localTx *txSet + locals *txSet signer types.Signer mu sync.RWMutex pending map[common.Address]*txList // All currently processable transactions queue map[common.Address]*txList // Queued but non-processable transactions - all map[common.Hash]*types.Transaction // All transactions to allow lookups beats map[common.Address]time.Time // Last heartbeat from each known account + all map[common.Hash]*types.Transaction // All transactions to allow lookups + priced *txPricedList // All transactions sorted by price wg sync.WaitGroup // for shutdown sync quit chan struct{} @@ -110,18 +115,18 @@ func NewTxPool(config *params.ChainConfig, eventMux *event.TypeMux, currentState signer: types.NewEIP155Signer(config.ChainId), pending: make(map[common.Address]*txList), queue: make(map[common.Address]*txList), - all: make(map[common.Hash]*types.Transaction), beats: make(map[common.Address]time.Time), + all: make(map[common.Hash]*types.Transaction), eventMux: eventMux, currentState: currentStateFn, gasLimit: gasLimitFn, - minGasPrice: new(big.Int), + gasPrice: big.NewInt(1), pendingState: nil, - localTx: newTxSet(), - events: eventMux.Subscribe(ChainHeadEvent{}, GasPriceChanged{}, RemovedTransactionEvent{}), + locals: newTxSet(), + events: eventMux.Subscribe(ChainHeadEvent{}, RemovedTransactionEvent{}), quit: make(chan struct{}), } - + pool.priced = newTxPricedList(&pool.all) pool.resetState() pool.wg.Add(2) @@ -134,27 +139,48 @@ func NewTxPool(config *params.ChainConfig, eventMux *event.TypeMux, currentState func (pool *TxPool) eventLoop() { defer pool.wg.Done() + // Start a ticker and keep track of interesting pool stats to report + var prevPending, prevQueued, prevStales int + + report := time.NewTicker(statsReportInterval) + defer report.Stop() + // 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 { - if pool.config.IsHomestead(ev.Block.Number()) { - pool.homestead = true + for { + select { + // Handle any events fired by the system + case ev, ok := <-pool.events.Chan(): + if !ok { + return + } + switch ev := ev.Data.(type) { + case ChainHeadEvent: + pool.mu.Lock() + if ev.Block != nil { + if pool.config.IsHomestead(ev.Block.Number()) { + pool.homestead = true + } } + pool.resetState() + pool.mu.Unlock() + + case RemovedTransactionEvent: + pool.AddBatch(ev.Txs) } - pool.resetState() - pool.mu.Unlock() - case GasPriceChanged: - pool.mu.Lock() - pool.minGasPrice = ev.Price - pool.mu.Unlock() - case RemovedTransactionEvent: - pool.AddBatch(ev.Txs) + // Handle stats reporting ticks + case <-report.C: + pool.mu.RLock() + pending, queued := pool.stats() + stales := pool.priced.stales + pool.mu.RUnlock() + + if pending != prevPending || queued != prevQueued || stales != prevStales { + log.Debug("Transaction pool status report", "executable", pending, "queued", queued, "stales", stales) + prevPending, prevQueued, prevStales = pending, queued, stales + } } } } @@ -191,6 +217,27 @@ func (pool *TxPool) Stop() { log.Info("Transaction pool stopped") } +// GasPrice returns the current gas price enforced by the transaction pool. +func (pool *TxPool) GasPrice() *big.Int { + pool.mu.RLock() + defer pool.mu.RUnlock() + + return new(big.Int).Set(pool.gasPrice) +} + +// SetGasPrice updates the minimum price required by the transaction pool for a +// new transaction, and drops all transactions below this threshold. +func (pool *TxPool) SetGasPrice(price *big.Int) { + pool.mu.Lock() + defer pool.mu.Unlock() + + pool.gasPrice = price + for _, tx := range pool.priced.Cap(price, pool.locals) { + pool.removeTx(tx.Hash()) + } + log.Info("Transaction pool price threshold updated", "price", price) +} + func (pool *TxPool) State() *state.ManagedState { pool.mu.RLock() defer pool.mu.RUnlock() @@ -200,17 +247,25 @@ func (pool *TxPool) State() *state.ManagedState { // Stats retrieves the current pool stats, namely the number of pending and the // number of queued (non-executable) transactions. -func (pool *TxPool) Stats() (pending int, queued int) { +func (pool *TxPool) Stats() (int, int) { pool.mu.RLock() defer pool.mu.RUnlock() + return pool.stats() +} + +// stats retrieves the current pool stats, namely the number of pending and the +// number of queued (non-executable) transactions. +func (pool *TxPool) stats() (int, int) { + pending := 0 for _, list := range pool.pending { pending += list.Len() } + queued := 0 for _, list := range pool.queue { queued += list.Len() } - return + return pending, queued } // Content retrieves the data content of the transaction pool, returning all the @@ -260,16 +315,16 @@ func (pool *TxPool) Pending() (map[common.Address]types.Transactions, error) { func (pool *TxPool) SetLocal(tx *types.Transaction) { pool.mu.Lock() defer pool.mu.Unlock() - pool.localTx.add(tx.Hash()) + pool.locals.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()) + local := pool.locals.contains(tx.Hash()) // Drop transactions under our own minimal accepted gas price - if !local && pool.minGasPrice.Cmp(tx.GasPrice()) > 0 { - return ErrCheap + if !local && pool.gasPrice.Cmp(tx.GasPrice()) > 0 { + return ErrUnderpriced } currentState, err := pool.currentState() @@ -314,31 +369,72 @@ func (pool *TxPool) validateTx(tx *types.Transaction) error { } // add validates a transaction and inserts it into the non-executable queue for -// later pending promotion and execution. -func (pool *TxPool) add(tx *types.Transaction) error { +// later pending promotion and execution. If the transaction is a replacement for +// an already pending or queued one, it overwrites the previous and returns this +// so outer code doesn't uselessly call promote. +func (pool *TxPool) add(tx *types.Transaction) (bool, error) { // If the transaction is already known, discard it hash := tx.Hash() if pool.all[hash] != nil { log.Trace("Discarding already known transaction", "hash", hash) - return fmt.Errorf("known transaction: %x", hash) + return false, fmt.Errorf("known transaction: %x", hash) } - // Otherwise ensure basic validation passes and queue it up + // If the transaction fails basic validation, discard it if err := pool.validateTx(tx); err != nil { log.Trace("Discarding invalid transaction", "hash", hash, "err", err) invalidTxCounter.Inc(1) - return err + return false, err + } + // If the transaction pool is full, discard underpriced transactions + if uint64(len(pool.all)) >= maxPendingTotal+maxQueuedTotal { + // If the new transaction is underpriced, don't accept it + if pool.priced.Underpriced(tx, pool.locals) { + log.Trace("Discarding underpriced transaction", "hash", hash, "price", tx.GasPrice()) + underpricedTxCounter.Inc(1) + return false, ErrUnderpriced + } + // New transaction is better than our worse ones, make room for it + drop := pool.priced.Discard(len(pool.all)-int(maxPendingTotal+maxQueuedTotal-1), pool.locals) + for _, tx := range drop { + log.Trace("Discarding freshly underpriced transaction", "hash", tx.Hash(), "price", tx.GasPrice()) + underpricedTxCounter.Inc(1) + pool.removeTx(tx.Hash()) + } } - pool.enqueueTx(hash, tx) + // If the transaction is replacing an already pending one, do directly + from, _ := types.Sender(pool.signer, tx) // already validated + if list := pool.pending[from]; list != nil && list.Overlaps(tx) { + // Nonce already pending, check if required price bump is met + inserted, old := list.Add(tx) + if !inserted { + pendingDiscardCounter.Inc(1) + return false, ErrReplaceUnderpriced + } + // New transaction is better, replace old one + if old != nil { + delete(pool.all, old.Hash()) + pool.priced.Removed() + pendingReplaceCounter.Inc(1) + } + pool.all[tx.Hash()] = tx + pool.priced.Put(tx) - // Print a log message if low enough level is set - log.Debug("Pooled new transaction", "hash", hash, "from", log.Lazy{Fn: func() common.Address { from, _ := types.Sender(pool.signer, tx); return from }}, "to", tx.To()) - return nil + log.Trace("Pooled new executable transaction", "hash", hash, "from", from, "to", tx.To()) + return old != nil, nil + } + // New transaction isn't replacing a pending one, push into queue + replace, err := pool.enqueueTx(hash, tx) + if err != nil { + return false, err + } + log.Trace("Pooled new future transaction", "hash", hash, "from", from, "to", tx.To()) + return replace, nil } // enqueueTx inserts a new transaction into the non-executable transaction queue. // // Note, this method assumes the pool lock is held! -func (pool *TxPool) enqueueTx(hash common.Hash, tx *types.Transaction) { +func (pool *TxPool) enqueueTx(hash common.Hash, tx *types.Transaction) (bool, error) { // Try to insert the transaction into the future queue from, _ := types.Sender(pool.signer, tx) // already validated if pool.queue[from] == nil { @@ -346,15 +442,19 @@ func (pool *TxPool) enqueueTx(hash common.Hash, tx *types.Transaction) { } inserted, old := pool.queue[from].Add(tx) if !inserted { + // An older transaction was better, discard this queuedDiscardCounter.Inc(1) - return // An older transaction was better, discard this + return false, ErrReplaceUnderpriced } // Discard any previous transaction and mark this if old != nil { delete(pool.all, old.Hash()) + pool.priced.Removed() queuedReplaceCounter.Inc(1) } pool.all[hash] = tx + pool.priced.Put(tx) + return old != nil, nil } // promoteTx adds a transaction to the pending (processable) list of transactions. @@ -371,16 +471,23 @@ func (pool *TxPool) promoteTx(addr common.Address, hash common.Hash, tx *types.T if !inserted { // An older transaction was better, discard this delete(pool.all, hash) + pool.priced.Removed() + pendingDiscardCounter.Inc(1) return } // Otherwise discard any previous transaction and mark this if old != nil { delete(pool.all, old.Hash()) + pool.priced.Removed() + pendingReplaceCounter.Inc(1) } - pool.all[hash] = tx // Failsafe to work around direct pending inserts (tests) - + // Failsafe to work around direct pending inserts (tests) + if pool.all[hash] == nil { + pool.all[hash] = tx + pool.priced.Put(tx) + } // Set the potentially new pending nonce and notify any subsystems of the new tx pool.beats[addr] = time.Now() pool.pendingState.SetNonce(addr, tx.Nonce()+1) @@ -392,16 +499,19 @@ func (pool *TxPool) Add(tx *types.Transaction) error { pool.mu.Lock() defer pool.mu.Unlock() - if err := pool.add(tx); err != nil { + // Try to inject the transaction and update any state + replace, err := pool.add(tx) + if err != nil { return err } - state, err := pool.currentState() if err != nil { return err } - pool.promoteExecutables(state) - + // If we added a new transaction, run promotion checks and return + if !replace { + pool.promoteExecutables(state) + } return nil } @@ -411,10 +521,13 @@ func (pool *TxPool) AddBatch(txs []*types.Transaction) error { defer pool.mu.Unlock() // Add the batch of transaction, tracking the accepted ones - added := 0 + replaced, added := true, 0 for _, tx := range txs { - if err := pool.add(tx); err == nil { + if replace, err := pool.add(tx); err == nil { added++ + if !replace { + replaced = false + } } } // Only reprocess the internal state if something was actually added @@ -423,7 +536,9 @@ func (pool *TxPool) AddBatch(txs []*types.Transaction) error { if err != nil { return err } - pool.promoteExecutables(state) + if !replaced { + pool.promoteExecutables(state) + } } return nil } @@ -467,6 +582,7 @@ func (pool *TxPool) removeTx(hash common.Hash) { // Remove it from the list of known transactions delete(pool.all, hash) + pool.priced.Removed() // Remove the transaction from the pending lists and reset the account nonce if pending := pool.pending[addr]; pending != nil { @@ -506,28 +622,31 @@ func (pool *TxPool) promoteExecutables(state *state.StateDB) { // Drop all transactions that are deemed too old (low nonce) for _, tx := range list.Forward(state.GetNonce(addr)) { hash := tx.Hash() - log.Debug("Removed old queued transaction", "hash", hash) + log.Trace("Removed old queued transaction", "hash", hash) delete(pool.all, hash) + pool.priced.Removed() } // Drop all transactions that are too costly (low balance) drops, _ := list.Filter(state.GetBalance(addr)) for _, tx := range drops { hash := tx.Hash() - log.Debug("Removed unpayable queued transaction", "hash", hash) + log.Trace("Removed unpayable queued transaction", "hash", hash) delete(pool.all, hash) + pool.priced.Removed() queuedNofundsCounter.Inc(1) } // Gather all executable transactions and promote them for _, tx := range list.Ready(pool.pendingState.GetNonce(addr)) { hash := tx.Hash() - log.Debug("Promoting queued transaction", "hash", hash) + log.Trace("Promoting queued transaction", "hash", hash) pool.promoteTx(addr, hash, tx) } // Drop all transactions over the allowed limit for _, tx := range list.Cap(int(maxQueuedPerAccount)) { hash := tx.Hash() - log.Debug("Removed cap-exceeding queued transaction", "hash", hash) + log.Trace("Removed cap-exceeding queued transaction", "hash", hash) delete(pool.all, hash) + pool.priced.Removed() queuedRLCounter.Inc(1) } queued += uint64(list.Len()) @@ -551,7 +670,7 @@ func (pool *TxPool) promoteExecutables(state *state.StateDB) { if uint64(list.Len()) > minPendingPerAccount { // Skip local accounts as pools should maintain backlogs for themselves for _, tx := range list.txs.items { - if !pool.localTx.contains(tx.Hash()) { + if !pool.locals.contains(tx.Hash()) { spammers.Push(addr, float32(list.Len())) } break // Checking on transaction for locality is enough @@ -593,7 +712,7 @@ func (pool *TxPool) promoteExecutables(state *state.StateDB) { pendingRLCounter.Inc(int64(pendingBeforeCap - pending)) } // If we've queued more transactions than the hard limit, drop oldest ones - if queued > maxQueuedInTotal { + if queued > maxQueuedTotal { // Sort all accounts with queued transactions by heartbeat addresses := make(addresssByHeartbeat, 0, len(pool.queue)) for addr := range pool.queue { @@ -602,7 +721,7 @@ func (pool *TxPool) promoteExecutables(state *state.StateDB) { sort.Sort(addresses) // Drop transactions until the total is below the limit - for drop := queued - maxQueuedInTotal; drop > 0; { + for drop := queued - maxQueuedTotal; drop > 0; { addr := addresses[len(addresses)-1] list := pool.queue[addr.address] @@ -639,20 +758,22 @@ func (pool *TxPool) demoteUnexecutables(state *state.StateDB) { // Drop all transactions that are deemed too old (low nonce) for _, tx := range list.Forward(nonce) { hash := tx.Hash() - log.Debug("Removed old pending transaction", "hash", hash) + log.Trace("Removed old pending transaction", "hash", hash) delete(pool.all, hash) + pool.priced.Removed() } // Drop all transactions that are too costly (low balance), and queue any invalids back for later drops, invalids := list.Filter(state.GetBalance(addr)) for _, tx := range drops { hash := tx.Hash() - log.Debug("Removed unpayable pending transaction", "hash", hash) + log.Trace("Removed unpayable pending transaction", "hash", hash) delete(pool.all, hash) + pool.priced.Removed() pendingNofundsCounter.Inc(1) } for _, tx := range invalids { hash := tx.Hash() - log.Debug("Demoting pending transaction", "hash", hash) + log.Trace("Demoting pending transaction", "hash", hash) pool.enqueueTx(hash, tx) } // Delete the entire queue entry if it became empty. diff --git a/core/tx_pool_test.go b/core/tx_pool_test.go index 765577933..e773daa2c 100644 --- a/core/tx_pool_test.go +++ b/core/tx_pool_test.go @@ -33,7 +33,11 @@ import ( ) func transaction(nonce uint64, gaslimit *big.Int, key *ecdsa.PrivateKey) *types.Transaction { - tx, _ := types.SignTx(types.NewTransaction(nonce, common.Address{}, big.NewInt(100), gaslimit, big.NewInt(1), nil), types.HomesteadSigner{}, key) + return pricedTransaction(nonce, gaslimit, big.NewInt(1), key) +} + +func pricedTransaction(nonce uint64, gaslimit, gasprice *big.Int, key *ecdsa.PrivateKey) *types.Transaction { + tx, _ := types.SignTx(types.NewTransaction(nonce, common.Address{}, big.NewInt(100), gaslimit, gasprice, nil), types.HomesteadSigner{}, key) return tx } @@ -151,9 +155,9 @@ func TestInvalidTransactions(t *testing.T) { } 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.gasPrice = big.NewInt(1000) + if err := pool.Add(tx); err != ErrUnderpriced { + t.Error("expected", ErrUnderpriced, "got", err) } pool.SetLocal(tx) @@ -262,14 +266,14 @@ func TestTransactionChainFork(t *testing.T) { resetState() tx := transaction(0, big.NewInt(100000), key) - if err := pool.add(tx); err != nil { + if _, err := pool.add(tx); err != nil { t.Error("didn't expect error", err) } pool.RemoveBatch([]*types.Transaction{tx}) // reset the pool's internal state resetState() - if err := pool.add(tx); err != nil { + if _, err := pool.add(tx); err != nil { t.Error("didn't expect error", err) } } @@ -293,11 +297,11 @@ func TestTransactionDoubleNonce(t *testing.T) { tx3, _ := types.SignTx(types.NewTransaction(0, common.Address{}, big.NewInt(100), big.NewInt(1000000), big.NewInt(1), nil), signer, key) // Add the first two transaction, ensure higher priced stays only - if err := pool.add(tx1); err != nil { - t.Error("didn't expect error", err) + if replace, err := pool.add(tx1); err != nil || replace { + t.Errorf("first transaction insert failed (%v) or reported replacement (%v)", err, replace) } - if err := pool.add(tx2); err != nil { - t.Error("didn't expect error", err) + if replace, err := pool.add(tx2); err != nil || !replace { + t.Errorf("second transaction insert failed (%v) or not reported replacement (%v)", err, replace) } state, _ := pool.currentState() pool.promoteExecutables(state) @@ -308,9 +312,7 @@ func TestTransactionDoubleNonce(t *testing.T) { t.Errorf("transaction mismatch: have %x, want %x", tx.Hash(), tx2.Hash()) } // Add the thid transaction and ensure it's not saved (smaller price) - if err := pool.add(tx3); err != nil { - t.Error("didn't expect error", err) - } + pool.add(tx3) pool.promoteExecutables(state) if pool.pending[addr].Len() != 1 { t.Error("expected 1 pending transactions, got", pool.pending[addr].Len()) @@ -330,7 +332,7 @@ func TestMissingNonce(t *testing.T) { currentState, _ := pool.currentState() currentState.AddBalance(addr, big.NewInt(100000000000000)) tx := transaction(1, big.NewInt(100000), key) - if err := pool.add(tx); err != nil { + if _, err := pool.add(tx); err != nil { t.Error("didn't expect error", err) } if len(pool.pending) != 0 { @@ -557,8 +559,8 @@ func TestTransactionQueueAccountLimiting(t *testing.T) { // some threshold, the higher transactions are dropped to prevent DOS attacks. func TestTransactionQueueGlobalLimiting(t *testing.T) { // Reduce the queue limits to shorten test time - defer func(old uint64) { maxQueuedInTotal = old }(maxQueuedInTotal) - maxQueuedInTotal = maxQueuedPerAccount * 3 + defer func(old uint64) { maxQueuedTotal = old }(maxQueuedTotal) + maxQueuedTotal = maxQueuedPerAccount * 3 // Create the pool to test the limit enforcement with db, _ := ethdb.NewMemDatabase() @@ -578,7 +580,7 @@ func TestTransactionQueueGlobalLimiting(t *testing.T) { // Generate and queue a batch of transactions nonces := make(map[common.Address]uint64) - txs := make(types.Transactions, 0, 3*maxQueuedInTotal) + txs := make(types.Transactions, 0, 3*maxQueuedTotal) for len(txs) < cap(txs) { key := keys[rand.Intn(len(keys))] addr := crypto.PubkeyToAddress(key.PublicKey) @@ -596,8 +598,8 @@ func TestTransactionQueueGlobalLimiting(t *testing.T) { } queued += list.Len() } - if queued > int(maxQueuedInTotal) { - t.Fatalf("total transactions overflow allowance: %d > %d", queued, maxQueuedInTotal) + if queued > int(maxQueuedTotal) { + t.Fatalf("total transactions overflow allowance: %d > %d", queued, maxQueuedTotal) } } @@ -791,6 +793,227 @@ func TestTransactionPendingMinimumAllowance(t *testing.T) { } } +// Tests that setting the transaction pool gas price to a higher value correctly +// discards everything cheaper than that and moves any gapped transactions back +// from the pending pool to the queue. +// +// Note, local transactions are never allowed to be dropped. +func TestTransactionPoolRepricing(t *testing.T) { + // Create the pool to test the pricing enforcement with + db, _ := ethdb.NewMemDatabase() + statedb, _ := state.New(common.Hash{}, db) + + pool := NewTxPool(params.TestChainConfig, new(event.TypeMux), func() (*state.StateDB, error) { return statedb, nil }, func() *big.Int { return big.NewInt(1000000) }) + pool.resetState() + + // Create a number of test accounts and fund them + state, _ := pool.currentState() + + keys := make([]*ecdsa.PrivateKey, 3) + for i := 0; i < len(keys); i++ { + keys[i], _ = crypto.GenerateKey() + state.AddBalance(crypto.PubkeyToAddress(keys[i].PublicKey), big.NewInt(1000000)) + } + // Generate and queue a batch of transactions, both pending and queued + txs := types.Transactions{} + + txs = append(txs, pricedTransaction(0, big.NewInt(100000), big.NewInt(2), keys[0])) + txs = append(txs, pricedTransaction(1, big.NewInt(100000), big.NewInt(1), keys[0])) + txs = append(txs, pricedTransaction(2, big.NewInt(100000), big.NewInt(2), keys[0])) + + txs = append(txs, pricedTransaction(1, big.NewInt(100000), big.NewInt(2), keys[1])) + txs = append(txs, pricedTransaction(2, big.NewInt(100000), big.NewInt(1), keys[1])) + txs = append(txs, pricedTransaction(3, big.NewInt(100000), big.NewInt(2), keys[1])) + + txs = append(txs, pricedTransaction(0, big.NewInt(100000), big.NewInt(1), keys[2])) + pool.SetLocal(txs[len(txs)-1]) // prevent this one from ever being dropped + + // Import the batch and that both pending and queued transactions match up + pool.AddBatch(txs) + + pending, queued := pool.stats() + if pending != 4 { + t.Fatalf("pending transactions mismatched: have %d, want %d", pending, 4) + } + if queued != 3 { + t.Fatalf("queued transactions mismatched: have %d, want %d", queued, 3) + } + // Reprice the pool and check that underpriced transactions get dropped + pool.SetGasPrice(big.NewInt(2)) + + pending, queued = pool.stats() + if pending != 2 { + t.Fatalf("pending transactions mismatched: have %d, want %d", pending, 2) + } + if queued != 3 { + t.Fatalf("queued transactions mismatched: have %d, want %d", queued, 3) + } + // Check that we can't add the old transactions back + if err := pool.Add(pricedTransaction(1, big.NewInt(100000), big.NewInt(1), keys[0])); err != ErrUnderpriced { + t.Fatalf("adding underpriced pending transaction error mismatch: have %v, want %v", err, ErrUnderpriced) + } + if err := pool.Add(pricedTransaction(2, big.NewInt(100000), big.NewInt(1), keys[1])); err != ErrUnderpriced { + t.Fatalf("adding underpriced queued transaction error mismatch: have %v, want %v", err, ErrUnderpriced) + } + // However we can add local underpriced transactions + tx := pricedTransaction(1, big.NewInt(100000), big.NewInt(1), keys[2]) + + pool.SetLocal(tx) // prevent this one from ever being dropped + if err := pool.Add(tx); err != nil { + t.Fatalf("failed to add underpriced local transaction: %v", err) + } + if pending, _ = pool.stats(); pending != 3 { + t.Fatalf("pending transactions mismatched: have %d, want %d", pending, 3) + } +} + +// Tests that when the pool reaches its global transaction limit, underpriced +// transactions are gradually shifted out for more expensive ones and any gapped +// pending transactions are moved into te queue. +// +// Note, local transactions are never allowed to be dropped. +func TestTransactionPoolUnderpricing(t *testing.T) { + // Reduce the queue limits to shorten test time + defer func(old uint64) { maxPendingTotal = old }(maxPendingTotal) + maxPendingTotal = 2 + + defer func(old uint64) { maxQueuedTotal = old }(maxQueuedTotal) + maxQueuedTotal = 2 + + // Create the pool to test the pricing enforcement with + db, _ := ethdb.NewMemDatabase() + statedb, _ := state.New(common.Hash{}, db) + + pool := NewTxPool(params.TestChainConfig, new(event.TypeMux), func() (*state.StateDB, error) { return statedb, nil }, func() *big.Int { return big.NewInt(1000000) }) + pool.resetState() + + // Create a number of test accounts and fund them + state, _ := pool.currentState() + + keys := make([]*ecdsa.PrivateKey, 3) + for i := 0; i < len(keys); i++ { + keys[i], _ = crypto.GenerateKey() + state.AddBalance(crypto.PubkeyToAddress(keys[i].PublicKey), big.NewInt(1000000)) + } + // Generate and queue a batch of transactions, both pending and queued + txs := types.Transactions{} + + txs = append(txs, pricedTransaction(0, big.NewInt(100000), big.NewInt(1), keys[0])) + txs = append(txs, pricedTransaction(1, big.NewInt(100000), big.NewInt(2), keys[0])) + + txs = append(txs, pricedTransaction(1, big.NewInt(100000), big.NewInt(1), keys[1])) + + txs = append(txs, pricedTransaction(0, big.NewInt(100000), big.NewInt(1), keys[2])) + pool.SetLocal(txs[len(txs)-1]) // prevent this one from ever being dropped + + // Import the batch and that both pending and queued transactions match up + pool.AddBatch(txs) + + pending, queued := pool.stats() + if pending != 3 { + t.Fatalf("pending transactions mismatched: have %d, want %d", pending, 3) + } + if queued != 1 { + t.Fatalf("queued transactions mismatched: have %d, want %d", queued, 1) + } + // Ensure that adding an underpriced transaction on block limit fails + if err := pool.Add(pricedTransaction(0, big.NewInt(100000), big.NewInt(1), keys[1])); err != ErrUnderpriced { + t.Fatalf("adding underpriced pending transaction error mismatch: have %v, want %v", err, ErrUnderpriced) + } + // Ensure that adding high priced transactions drops cheap ones, but not own + if err := pool.Add(pricedTransaction(0, big.NewInt(100000), big.NewInt(3), keys[1])); err != nil { + t.Fatalf("failed to add well priced transaction: %v", err) + } + if err := pool.Add(pricedTransaction(2, big.NewInt(100000), big.NewInt(4), keys[1])); err != nil { + t.Fatalf("failed to add well priced transaction: %v", err) + } + if err := pool.Add(pricedTransaction(3, big.NewInt(100000), big.NewInt(5), keys[1])); err != nil { + t.Fatalf("failed to add well priced transaction: %v", err) + } + pending, queued = pool.stats() + if pending != 2 { + t.Fatalf("pending transactions mismatched: have %d, want %d", pending, 2) + } + if queued != 2 { + t.Fatalf("queued transactions mismatched: have %d, want %d", queued, 2) + } + // Ensure that adding local transactions can push out even higher priced ones + tx := pricedTransaction(1, big.NewInt(100000), big.NewInt(0), keys[2]) + + pool.SetLocal(tx) // prevent this one from ever being dropped + if err := pool.Add(tx); err != nil { + t.Fatalf("failed to add underpriced local transaction: %v", err) + } + pending, queued = pool.stats() + if pending != 2 { + t.Fatalf("pending transactions mismatched: have %d, want %d", pending, 2) + } + if queued != 2 { + t.Fatalf("queued transactions mismatched: have %d, want %d", queued, 2) + } +} + +// Tests that the pool rejects replacement transactions that don't meet the minimum +// price bump required. +func TestTransactionReplacement(t *testing.T) { + // Create the pool to test the pricing enforcement with + db, _ := ethdb.NewMemDatabase() + statedb, _ := state.New(common.Hash{}, db) + + pool := NewTxPool(params.TestChainConfig, new(event.TypeMux), func() (*state.StateDB, error) { return statedb, nil }, func() *big.Int { return big.NewInt(1000000) }) + pool.resetState() + + // Create a a test account to add transactions with + key, _ := crypto.GenerateKey() + + state, _ := pool.currentState() + state.AddBalance(crypto.PubkeyToAddress(key.PublicKey), big.NewInt(1000000000)) + + // Add pending transactions, ensuring the minimum price bump is enforced for replacement (for ultra low prices too) + price := int64(100) + threshold := (price * (100 + minPriceBumpPercent)) / 100 + + if err := pool.Add(pricedTransaction(0, big.NewInt(100000), big.NewInt(1), key)); err != nil { + t.Fatalf("failed to add original cheap pending transaction: %v", err) + } + if err := pool.Add(pricedTransaction(0, big.NewInt(100001), big.NewInt(1), key)); err != ErrReplaceUnderpriced { + t.Fatalf("original cheap pending transaction replacement error mismatch: have %v, want %v", err, ErrReplaceUnderpriced) + } + if err := pool.Add(pricedTransaction(0, big.NewInt(100000), big.NewInt(2), key)); err != nil { + t.Fatalf("failed to replace original cheap pending transaction: %v", err) + } + + if err := pool.Add(pricedTransaction(0, big.NewInt(100000), big.NewInt(price), key)); err != nil { + t.Fatalf("failed to add original proper pending transaction: %v", err) + } + if err := pool.Add(pricedTransaction(0, big.NewInt(100000), big.NewInt(threshold), key)); err != ErrReplaceUnderpriced { + t.Fatalf("original proper pending transaction replacement error mismatch: have %v, want %v", err, ErrReplaceUnderpriced) + } + if err := pool.Add(pricedTransaction(0, big.NewInt(100000), big.NewInt(threshold+1), key)); err != nil { + t.Fatalf("failed to replace original proper pending transaction: %v", err) + } + // Add queued transactions, ensuring the minimum price bump is enforced for replacement (for ultra low prices too) + if err := pool.Add(pricedTransaction(2, big.NewInt(100000), big.NewInt(1), key)); err != nil { + t.Fatalf("failed to add original queued transaction: %v", err) + } + if err := pool.Add(pricedTransaction(2, big.NewInt(100001), big.NewInt(1), key)); err != ErrReplaceUnderpriced { + t.Fatalf("original queued transaction replacement error mismatch: have %v, want %v", err, ErrReplaceUnderpriced) + } + if err := pool.Add(pricedTransaction(2, big.NewInt(100000), big.NewInt(2), key)); err != nil { + t.Fatalf("failed to replace original queued transaction: %v", err) + } + + if err := pool.Add(pricedTransaction(2, big.NewInt(100000), big.NewInt(price), key)); err != nil { + t.Fatalf("failed to add original queued transaction: %v", err) + } + if err := pool.Add(pricedTransaction(2, big.NewInt(100001), big.NewInt(threshold), key)); err != ErrReplaceUnderpriced { + t.Fatalf("original queued transaction replacement error mismatch: have %v, want %v", err, ErrReplaceUnderpriced) + } + if err := pool.Add(pricedTransaction(2, big.NewInt(100000), big.NewInt(threshold+1), key)); err != nil { + t.Fatalf("failed to replace original queued transaction: %v", err) + } +} + // Benchmarks the speed of validating the contents of the pending queue of the // transaction pool. func BenchmarkPendingDemotion100(b *testing.B) { benchmarkPendingDemotion(b, 100) } -- cgit v1.2.3