From a2dc074b1ddffaf4e35758835bafe14cca5f0ea7 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?P=C3=A9ter=20Szil=C3=A1gyi?= Date: Fri, 22 Jan 2016 12:05:17 +0200 Subject: core, core/types, miner: fix transaction nonce-price combo sort --- core/types/transaction.go | 85 ++++++++++++++++++++++++++++++++++-------- core/types/transaction_test.go | 57 ++++++++++++++++++++++++++++ 2 files changed, 126 insertions(+), 16 deletions(-) (limited to 'core/types') diff --git a/core/types/transaction.go b/core/types/transaction.go index 7a6c5e088..4049ae888 100644 --- a/core/types/transaction.go +++ b/core/types/transaction.go @@ -17,11 +17,13 @@ package types import ( + "container/heap" "crypto/ecdsa" "errors" "fmt" "io" "math/big" + "sort" "sync/atomic" "github.com/ethereum/go-ethereum/common" @@ -302,27 +304,78 @@ func TxDifference(a, b Transactions) (keep Transactions) { return keep } -type TxByNonce struct{ Transactions } +// TxByNonce implements the sort interface to allow sorting a list of transactions +// by their nonces. This is usually only useful for sorting transactions from a +// single account, otherwise a nonce comparison doesn't make much sense. +type TxByNonce Transactions -func (s TxByNonce) Less(i, j int) bool { - return s.Transactions[i].data.AccountNonce < s.Transactions[j].data.AccountNonce -} +func (s TxByNonce) Len() int { return len(s) } +func (s TxByNonce) Less(i, j int) bool { return s[i].data.AccountNonce < s[j].data.AccountNonce } +func (s TxByNonce) Swap(i, j int) { s[i], s[j] = s[j], s[i] } + +// TxByPrice implements both the sort and the heap interface, making it useful +// for all at once sorting as well as individually adding and removing elements. +type TxByPrice Transactions -type TxByPrice struct{ Transactions } +func (s TxByPrice) Len() int { return len(s) } +func (s TxByPrice) Less(i, j int) bool { return s[i].data.Price.Cmp(s[j].data.Price) > 0 } +func (s TxByPrice) Swap(i, j int) { s[i], s[j] = s[j], s[i] } -func (s TxByPrice) Less(i, j int) bool { - return s.Transactions[i].data.Price.Cmp(s.Transactions[j].data.Price) > 0 +func (s *TxByPrice) Push(x interface{}) { + *s = append(*s, x.(*Transaction)) } -type TxByPriceAndNonce struct{ Transactions } +func (s *TxByPrice) Pop() interface{} { + old := *s + n := len(old) + x := old[n-1] + *s = old[0 : n-1] + return x +} -func (s TxByPriceAndNonce) Less(i, j int) bool { - // we can ignore the error here. Sorting shouldn't care about validness - ifrom, _ := s.Transactions[i].From() - jfrom, _ := s.Transactions[j].From() - // favour nonce if they are from the same recipient - if ifrom == jfrom { - return s.Transactions[i].data.AccountNonce < s.Transactions[j].data.AccountNonce +// SortByPriceAndNonce sorts the transactions by price in such a way that the +// nonce orderings within a single account are maintained. +// +// Note, this is not as trivial as it seems from the first look as there are three +// different criteria that need to be taken into account (price, nonce, account +// match), which cannot be done with any plain sorting method, as certain items +// cannot be compared without context. +// +// This method first sorts the separates the list of transactions into individual +// sender accounts and sorts them by nonce. After the account nonce ordering is +// satisfied, the results are merged back together by price, always comparing only +// the head transaction from each account. This is done via a heap to keep it fast. +func SortByPriceAndNonce(txs []*Transaction) { + // Separate the transactions by account and sort by nonce + byNonce := make(map[common.Address][]*Transaction) + for _, tx := range txs { + acc, _ := tx.From() // we only sort valid txs so this cannot fail + byNonce[acc] = append(byNonce[acc], tx) + } + for _, accTxs := range byNonce { + sort.Sort(TxByNonce(accTxs)) + } + // Initialize a price based heap with the head transactions + byPrice := make(TxByPrice, 0, len(byNonce)) + for acc, accTxs := range byNonce { + byPrice = append(byPrice, accTxs[0]) + byNonce[acc] = accTxs[1:] + } + heap.Init(&byPrice) + + // Merge by replacing the best with the next from the same account + txs = txs[:0] + for len(byPrice) > 0 { + // Retrieve the next best transaction by price + best := heap.Pop(&byPrice).(*Transaction) + + // Push in its place the next transaction from the same account + acc, _ := best.From() // we only sort valid txs so this cannot fail + if accTxs, ok := byNonce[acc]; ok && len(accTxs) > 0 { + heap.Push(&byPrice, accTxs[0]) + byNonce[acc] = accTxs[1:] + } + // Accumulate the best priced transaction + txs = append(txs, best) } - return s.Transactions[i].data.Price.Cmp(s.Transactions[j].data.Price) > 0 } diff --git a/core/types/transaction_test.go b/core/types/transaction_test.go index 1c0e27d9a..62420e71f 100644 --- a/core/types/transaction_test.go +++ b/core/types/transaction_test.go @@ -117,3 +117,60 @@ func TestRecipientNormal(t *testing.T) { t.Error("derived address doesn't match") } } + +// Tests that transactions can be correctly sorted according to their price in +// decreasing order, but at the same time with increasing nonces when issued by +// the same account. +func TestTransactionPriceNonceSort(t *testing.T) { + // Generate a batch of accounts to start with + keys := make([]*ecdsa.PrivateKey, 25) + for i := 0; i < len(keys); i++ { + keys[i], _ = crypto.GenerateKey() + } + // Generate a batch of transactions with overlapping values, but shifted nonces + txs := []*Transaction{} + for start, key := range keys { + for i := 0; i < 25; i++ { + tx, _ := NewTransaction(uint64(start+i), common.Address{}, big.NewInt(100), big.NewInt(100), big.NewInt(int64(start+i)), nil).SignECDSA(key) + txs = append(txs, tx) + } + } + // Sort the transactions and cross check the nonce ordering + SortByPriceAndNonce(txs) + for i, txi := range txs { + fromi, _ := txi.From() + + // Make sure the nonce order is valid + for j, txj := range txs[i+1:] { + fromj, _ := txj.From() + + if fromi == fromj && txi.Nonce() > txj.Nonce() { + t.Errorf("invalid nonce ordering: tx #%d (A=%x N=%v) < tx #%d (A=%x N=%v)", i, fromi[:4], txi.Nonce(), i+j, fromj[:4], txj.Nonce()) + } + } + // Find the previous and next nonce of this account + prev, next := i-1, i+1 + for j := i - 1; j >= 0; j-- { + if fromj, _ := txs[j].From(); fromi == fromj { + prev = j + break + } + } + for j := i + 1; j < len(txs); j++ { + if fromj, _ := txs[j].From(); fromi == fromj { + next = j + break + } + } + // Make sure that in between the neighbor nonces, the transaction is correctly positioned price wise + for j := prev + 1; j < next; j++ { + fromj, _ := txs[j].From() + if j < i && txs[j].GasPrice().Cmp(txi.GasPrice()) < 0 { + t.Errorf("invalid gasprice ordering: tx #%d (A=%x P=%v) < tx #%d (A=%x P=%v)", j, fromj[:4], txs[j].GasPrice(), i, fromi[:4], txi.GasPrice()) + } + if j > i && txs[j].GasPrice().Cmp(txi.GasPrice()) > 0 { + t.Errorf("invalid gasprice ordering: tx #%d (A=%x P=%v) > tx #%d (A=%x P=%v)", j, fromj[:4], txs[j].GasPrice(), i, fromi[:4], txi.GasPrice()) + } + } + } +} -- cgit v1.2.3