/
pending_txs.go
146 lines (133 loc) · 4.9 KB
/
pending_txs.go
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
// Package pendingtxs exposes the AccountPendingTxs type, which keeps track of transactions that haven't been applied to
// global state yet. If also provides projectors that predict an account's nonce and balance after those transactions
// would be applied.
package pendingtxs
import (
"bytes"
"github.com/spacemeshos/go-spacemesh/common/types"
"sync"
)
type nanoTx struct {
Amount uint64
Fee uint64
HighestLayerIncludedIn types.LayerID
}
// AccountPendingTxs indexes the pending transactions (those that are in the mesh, but haven't been applied yet) of a
// specific account.
type AccountPendingTxs struct {
PendingTxs map[uint64]map[types.TransactionID]nanoTx // nonce -> TxID -> nanoTx
mu sync.RWMutex
}
// NewAccountPendingTxs returns a new, initialized AccountPendingTxs structure.
func NewAccountPendingTxs() *AccountPendingTxs {
return &AccountPendingTxs{
PendingTxs: make(map[uint64]map[types.TransactionID]nanoTx),
}
}
// Add adds transactions to a specific layer. It also updates the highest layer each transaction is included in, if this
// transaction is already indexed.
func (apt *AccountPendingTxs) Add(layer types.LayerID, txs ...*types.Transaction) {
apt.mu.Lock()
for _, tx := range txs {
existing, found := apt.PendingTxs[tx.AccountNonce]
if !found {
existing = make(map[types.TransactionID]nanoTx)
apt.PendingTxs[tx.AccountNonce] = existing
}
if existing[tx.ID()].HighestLayerIncludedIn > layer {
layer = existing[tx.ID()].HighestLayerIncludedIn
}
existing[tx.ID()] = nanoTx{
Amount: tx.Amount,
Fee: tx.Fee,
HighestLayerIncludedIn: layer,
}
}
apt.mu.Unlock()
}
// RemoveAccepted removes a list of accepted transactions from the AccountPendingTxs. Since the given transactions were
// accepted, any other version of the transaction with the same nonce is also discarded.
func (apt *AccountPendingTxs) RemoveAccepted(accepted []*types.Transaction) {
apt.mu.Lock()
for _, tx := range accepted {
delete(apt.PendingTxs, tx.AccountNonce)
}
apt.mu.Unlock()
}
// RemoveRejected removes a list of rejected transactions from the AccountPendingTxs, assuming they were rejected in the
// given layer. If any of the listed transactions also appears in a higher layer than the one given, it will not be
// removed.
func (apt *AccountPendingTxs) RemoveRejected(rejected []*types.Transaction, layer types.LayerID) {
apt.mu.Lock()
for _, tx := range rejected {
existing, found := apt.PendingTxs[tx.AccountNonce]
if found {
if existing[tx.ID()].HighestLayerIncludedIn > layer {
continue
}
delete(existing, tx.ID())
if len(existing) == 0 {
delete(apt.PendingTxs, tx.AccountNonce)
}
}
}
apt.mu.Unlock()
}
// RemoveNonce removes any transaction with the given nonce from AccountPendingTxs. For each transaction removed it also
// calls the given deleteTx function with the corresponding transaction ID.
func (apt *AccountPendingTxs) RemoveNonce(nonce uint64, deleteTx func(id types.TransactionID)) {
apt.mu.Lock()
for id := range apt.PendingTxs[nonce] {
deleteTx(id)
}
delete(apt.PendingTxs, nonce)
apt.mu.Unlock()
}
// GetProjection provides projected nonce and balance after valid transactions in the AccountPendingTxs would be
// applied. Since determining which transactions are valid depends on the previous nonce and balance, those must be
// provided.
func (apt *AccountPendingTxs) GetProjection(prevNonce, prevBalance uint64) (nonce, balance uint64) {
_, nonce, balance = apt.ValidTxs(prevNonce, prevBalance)
return nonce, balance
}
// ValidTxs provides a list of valid transaction IDs that can be applied from the AccountPendingTxs and a final nonce
// and balance if they would be applied. The validity of transactions depends on the previous nonce and balance, so
// those must be provided.
func (apt *AccountPendingTxs) ValidTxs(prevNonce, prevBalance uint64) (txIds []types.TransactionID, nonce, balance uint64) {
nonce, balance = prevNonce, prevBalance
apt.mu.RLock()
for {
txs, found := apt.PendingTxs[nonce]
if !found {
break // no transactions found with required nonce
}
id := validTxWithHighestFee(txs, balance)
if id == types.EmptyTransactionID {
break // all transactions would overdraft the account
}
txIds = append(txIds, id)
tx := txs[id]
balance -= tx.Amount + tx.Fee
nonce++
}
apt.mu.RUnlock()
return txIds, nonce, balance
}
// IsEmpty is true if there are no transactions in this object.
func (apt *AccountPendingTxs) IsEmpty() bool {
apt.mu.RLock()
defer apt.mu.RUnlock()
return len(apt.PendingTxs) == 0
}
func validTxWithHighestFee(txs map[types.TransactionID]nanoTx, balance uint64) types.TransactionID {
bestID := types.EmptyTransactionID
var maxFee uint64
for id, tx := range txs {
if (tx.Fee > maxFee || (tx.Fee == maxFee && bytes.Compare(id[:], bestID[:]) < 0)) &&
balance >= (tx.Amount+tx.Fee) {
maxFee = tx.Fee
bestID = id
}
}
return bestID
}