aboutsummaryrefslogtreecommitdiffstats
path: root/core/tx_list.go
blob: c3ddf3148ecc90ed76567eea5c6bce3b32663388 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
// Copyright 2016 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 <http://www.gnu.org/licenses/>.

package core

import (
    "container/heap"
    "math"
    "math/big"
    "sort"

    "github.com/ethereum/go-ethereum/core/types"
)

// nonceHeap is a heap.Interface implementation over 64bit unsigned integers for
// retrieving sorted transactions from the possibly gapped future queue.
type nonceHeap []uint64

func (h nonceHeap) Len() int           { return len(h) }
func (h nonceHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h nonceHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *nonceHeap) Push(x interface{}) {
    *h = append(*h, x.(uint64))
}

func (h *nonceHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

// txSortedMap is a nonce->transaction hash map with a heap based index to allow
// iterating over the contents in a nonce-incrementing way.
type txSortedMap struct {
    items map[uint64]*types.Transaction // Hash map storing the transaction data
    index *nonceHeap                    // Heap of nonces of all the stored transactions (non-strict mode)
    cache types.Transactions            // Cache of the transactions already sorted
}

// newTxSortedMap creates a new sorted transaction map.
func newTxSortedMap() *txSortedMap {
    return &txSortedMap{
        items: make(map[uint64]*types.Transaction),
        index: &nonceHeap{},
    }
}

// Get retrieves the current transactions associated with the given nonce.
func (m *txSortedMap) Get(nonce uint64) *types.Transaction {
    return m.items[nonce]
}

// Put inserts a new transaction into the map, also updating the map's nonce
// index. If a transaction already exists with the same nonce, it's overwritten.
func (m *txSortedMap) Put(tx *types.Transaction) {
    nonce := tx.Nonce()
    if m.items[nonce] == nil {
        heap.Push(m.index, nonce)
    }
    m.items[nonce], m.cache = tx, nil
}

// Forward removes all transactions from the map with a nonce lower than the
// provided threshold. Every removed transaction is returned for any post-removal
// maintenance.
func (m *txSortedMap) Forward(threshold uint64) types.Transactions {
    var removed types.Transactions

    // Pop off heap items until the threshold is reached
    for m.index.Len() > 0 && (*m.index)[0] < threshold {
        nonce := heap.Pop(m.index).(uint64)
        removed = append(removed, m.items[nonce])
        delete(m.items, nonce)
    }
    // If we had a cached order, shift the front
    if m.cache != nil {
        m.cache = m.cache[len(removed):]
    }
    return removed
}

// Filter iterates over the list of transactions and removes all of them for which
// the specified function evaluates to true.
func (m *txSortedMap) Filter(filter func(*types.Transaction) bool) types.Transactions {
    var removed types.Transactions

    // Collect all the transactions to filter out
    for nonce, tx := range m.items {
        if filter(tx) {
            removed = append(removed, tx)
            delete(m.items, nonce)
        }
    }
    // If transactions were removed, the heap and cache are ruined
    if len(removed) > 0 {
        *m.index = make([]uint64, 0, len(m.items))
        for nonce, _ := range m.items {
            *m.index = append(*m.index, nonce)
        }
        heap.Init(m.index)

        m.cache = nil
    }
    return removed
}

// Cap places a hard limit on the number of items, returning all transactions
// exceeding that limit.
func (m *txSortedMap) Cap(threshold int) types.Transactions {
    // Short circuit if the number of items is under the limit
    if len(m.items) <= threshold {
        return nil
    }
    // Otherwise gather and drop the highest nonce'd transactions
    var drops types.Transactions

    sort.Sort(*m.index)
    for size := len(m.items); size > threshold; size-- {
        drops = append(drops, m.items[(*m.index)[size-1]])
        delete(m.items, (*m.index)[size-1])
    }
    *m.index = (*m.index)[:threshold]
    heap.Init(m.index)

    // If we had a cache, shift the back
    if m.cache != nil {
        m.cache = m.cache[:len(m.cache)-len(drops)]
    }
    return drops
}

// Remove deletes a transaction from the maintained map, returning whether the
// transaction was found.
func (m *txSortedMap) Remove(nonce uint64) bool {
    // Short circuit if no transaction is present
    _, ok := m.items[nonce]
    if !ok {
        return false
    }
    // Otherwise delete the transaction and fix the heap index
    for i := 0; i < m.index.Len(); i++ {
        if (*m.index)[i] == nonce {
            heap.Remove(m.index, i)
            break
        }
    }
    delete(m.items, nonce)
    m.cache = nil

    return true
}

// Ready retrieves a sequentially increasing list of transactions starting at the
// provided nonce that is ready for processing. The returned transactions will be
// removed from the list.
//
// Note, all transactions with nonces lower than start will also be returned to
// prevent getting into and invalid state. This is not something that should ever
// happen but better to be self correcting than failing!
func (m *txSortedMap) Ready(start uint64) types.Transactions {
    // Short circuit if no transactions are available
    if m.index.Len() == 0 || (*m.index)[0] > start {
        return nil
    }
    // Otherwise start accumulating incremental transactions
    var ready types.Transactions
    for next := (*m.index)[0]; m.index.Len() > 0 && (*m.index)[0] == next; next++ {
        ready = append(ready, m.items[next])
        delete(m.items, next)
        heap.Pop(m.index)
    }
    m.cache = nil

    return ready
}

// Len returns the length of the transaction map.
func (m *txSortedMap) Len() int {
    return len(m.items)
}

// Flatten creates a nonce-sorted slice of transactions based on the loosely
// sorted internal representation. The result of the sorting is cached in case
// it's requested again before any modifications are made to the contents.
func (m *txSortedMap) Flatten() types.Transactions {
    // If the sorting was not cached yet, create and cache it
    if m.cache == nil {
        m.cache = make(types.Transactions, 0, len(m.items))
        for _, tx := range m.items {
            m.cache = append(m.cache, tx)
        }
        sort.Sort(types.TxByNonce(m.cache))
    }
    // Copy the cache to prevent accidental modifications
    txs := make(types.Transactions, len(m.cache))
    copy(txs, m.cache)
    return txs
}

// txList is a "list" of transactions belonging to an account, sorted by account
// nonce. The same type can be used both for storing contiguous transactions for
// the executable/pending queue; and for storing gapped transactions for the non-
// executable/future queue, with minor behavoiral changes.
type txList struct {
    strict  bool         // Whether nonces are strictly continuous or not
    txs     *txSortedMap // Heap indexed sorted hash map of the transactions
    costcap *big.Int     // Price of the highest costing transaction (reset only if exceeds balance)
}

// newTxList create a new transaction list for maintaining nonce-indexable fast,
// gapped, sortable transaction lists.
func newTxList(strict bool) *txList {
    return &txList{
        strict:  strict,
        txs:     newTxSortedMap(),
        costcap: new(big.Int),
    }
}

// Add tries to insert a new transaction into the list, returning whether the
// transaction was accepted, and if yes, any previous transaction it replaced.
//
// If the new transaction is accepted into the list, the lists' cost threshold
// is also potentially updated.
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
    }
    // Otherwise overwrite the old transaction with the current one
    l.txs.Put(tx)
    if cost := tx.Cost(); l.costcap.Cmp(cost) < 0 {
        l.costcap = cost
    }
    return true, old
}

// Forward removes all transactions from the list with a nonce lower than the
// provided threshold. Every removed transaction is returned for any post-removal
// maintenance.
func (l *txList) Forward(threshold uint64) types.Transactions {
    return l.txs.Forward(threshold)
}

// Filter removes all transactions from the list with a cost higher than the
// provided threshold. Every removed transaction is returned for any post-removal
// maintenance. Strict-mode invalidated transactions are also returned.
//
// This method uses the cached costcap to quickly decide if there's even a point
// in calculating all the costs or if the balance covers all. If the threshold is
// lower than the costcap, the costcap will be reset to a new high after removing
// expensive the too transactions.
func (l *txList) Filter(threshold *big.Int) (types.Transactions, types.Transactions) {
    // If all transactions are below the threshold, short circuit
    if l.costcap.Cmp(threshold) <= 0 {
        return nil, nil
    }
    l.costcap = new(big.Int).Set(threshold) // Lower the cap to the threshold

    // Filter out all the transactions above the account's funds
    removed := l.txs.Filter(func(tx *types.Transaction) bool { return tx.Cost().Cmp(threshold) > 0 })

    // If the list was strict, filter anything above the lowest nonce
    var invalids types.Transactions
    if l.strict && len(removed) > 0 {
        lowest := uint64(math.MaxUint64)
        for _, tx := range removed {
            if nonce := tx.Nonce(); lowest > nonce {
                lowest = nonce
            }
        }
        invalids = l.txs.Filter(func(tx *types.Transaction) bool { return tx.Nonce() > lowest })
    }
    return removed, invalids
}

// Cap places a hard limit on the number of items, returning all transactions
// exceeding that limit.
func (l *txList) Cap(threshold int) types.Transactions {
    return l.txs.Cap(threshold)
}

// Remove deletes a transaction from the maintained list, returning whether the
// transaction was found, and also returning any transaction invalidated due to
// the deletion (strict mode only).
func (l *txList) Remove(tx *types.Transaction) (bool, types.Transactions) {
    // Remove the transaction from the set
    nonce := tx.Nonce()
    if removed := l.txs.Remove(nonce); !removed {
        return false, nil
    }
    // In strict mode, filter out non-executable transactions
    if l.strict {
        return true, l.txs.Filter(func(tx *types.Transaction) bool { return tx.Nonce() > nonce })
    }
    return true, nil
}

// Ready retrieves a sequentially increasing list of transactions starting at the
// provided nonce that is ready for processing. The returned transactions will be
// removed from the list.
//
// Note, all transactions with nonces lower than start will also be returned to
// prevent getting into and invalid state. This is not something that should ever
// happen but better to be self correcting than failing!
func (l *txList) Ready(start uint64) types.Transactions {
    return l.txs.Ready(start)
}

// Len returns the length of the transaction list.
func (l *txList) Len() int {
    return l.txs.Len()
}

// Empty returns whether the list of transactions is empty or not.
func (l *txList) Empty() bool {
    return l.Len() == 0
}

// Flatten creates a nonce-sorted slice of transactions based on the loosely
// sorted internal representation. The result of the sorting is cached in case
// it's requested again before any modifications are made to the contents.
func (l *txList) Flatten() types.Transactions {
    return l.txs.Flatten()
}