Line data Source code
1 : // Copyright (c) 2009-2010 Satoshi Nakamoto
2 : // Copyright (c) 2009-2014 The Bitcoin developers
3 : // Copyright (c) 2016-2021 The PIVX Core developers
4 : // Distributed under the MIT software license, see the accompanying
5 : // file COPYING or http://www.opensource.org/licenses/mit-license.php.
6 :
7 : #ifndef PIVX_TXMEMPOOL_H
8 : #define PIVX_TXMEMPOOL_H
9 :
10 : #include <list>
11 : #include <memory>
12 : #include <set>
13 :
14 : #include "amount.h"
15 : #include "coins.h"
16 : #include "crypto/siphash.h"
17 : #include "indirectmap.h"
18 : #include "policy/feerate.h"
19 : #include "primitives/transaction.h"
20 : #include "sync.h"
21 : #include "random.h"
22 : #include "netaddress.h"
23 :
24 : #include "boost/multi_index_container.hpp"
25 : #include "boost/multi_index/ordered_index.hpp"
26 : #include "boost/multi_index/hashed_index.hpp"
27 : #include <boost/multi_index/sequenced_index.hpp>
28 :
29 : class CAutoFile;
30 : class CBLSPublicKey;
31 :
32 :
33 : /** Fake height value used in Coin to signify they are only in the memory pool (since 0.8) */
34 : static const uint32_t MEMPOOL_HEIGHT = 0x7FFFFFFF;
35 :
36 : class CTxMemPool;
37 :
38 : /** \class CTxMemPoolEntry
39 : *
40 : * CTxMemPoolEntry stores data about the corresponding transaction, as well
41 : * as data about all in-mempool transactions that depend on the transaction
42 : * ("descendant" transactions).
43 : *
44 : * When a new entry is added to the mempool, we update the descendant state
45 : * (nCountWithDescendants, nSizeWithDescendants, and nModFeesWithDescendants) for
46 : * all ancestors of the newly added transaction.
47 : *
48 : * If updating the descendant state is skipped, we can mark the entry as
49 : * "dirty", and set nSizeWithDescendants/nModFeesWithDescendants to equal nTxSize/
50 : * nFee+feeDelta. (This can potentially happen during a reorg, where we limit the
51 : * amount of work we're willing to do to avoid consuming too much CPU.)
52 : *
53 : */
54 765106 : class CTxMemPoolEntry
55 : {
56 : private:
57 : CTransactionRef tx;
58 : CAmount nFee; //! Cached to avoid expensive parent-transaction lookups
59 : size_t nTxSize; //! ... and avoid recomputing tx size
60 : size_t nUsageSize; //! ... and total memory usage
61 : CFeeRate feeRate; //! ... and fee per kB
62 : bool hasZerocoins{false}; //! ... and checking if it contains zPIV (mints/spends)
63 : bool m_isShielded{false}; //! ... and checking if it contains shielded spends/outputs
64 : int64_t nTime; //! Local time when entering the mempool
65 : unsigned int entryHeight; //! Chain height when entering the mempool
66 : bool spendsCoinbaseOrCoinstake; //! keep track of transactions that spend a coinbase or a coinstake
67 : unsigned int sigOpCount; //! Legacy sig ops plus P2SH sig op count
68 : int64_t feeDelta; //! Used for determining the priority of the transaction for mining in a block
69 :
70 : // Information about descendants of this transaction that are in the
71 : // mempool; if we remove this transaction we must remove all of these
72 : // descendants as well. if nCountWithDescendants is 0, treat this entry as
73 : // dirty, and nSizeWithDescendants and nModFeesWithDescendants will not be
74 : // correct.
75 : uint64_t nCountWithDescendants; //! number of descendant transactions
76 : uint64_t nSizeWithDescendants; //! ... and size
77 : CAmount nModFeesWithDescendants; //! ... and total fees (all including us)
78 :
79 : // Analogous statistics for ancestor transactions
80 : uint64_t nCountWithAncestors;
81 : uint64_t nSizeWithAncestors;
82 : CAmount nModFeesWithAncestors;
83 : unsigned int nSigOpCountWithAncestors;
84 :
85 : public:
86 : CTxMemPoolEntry(const CTransactionRef& _tx, const CAmount& _nFee,
87 : int64_t _nTime, unsigned int _entryHeight,
88 : bool _spendsCoinbaseOrCoinstake, unsigned int nSigOps);
89 :
90 345209694 : const CTransaction& GetTx() const { return *this->tx; }
91 8672457 : std::shared_ptr<const CTransaction> GetSharedTx() const { return this->tx; }
92 1577195 : const CAmount& GetFee() const { return nFee; }
93 22458551 : size_t GetTxSize() const { return nTxSize; }
94 398895 : int64_t GetTime() const { return nTime; }
95 312039 : unsigned int GetHeight() const { return entryHeight; }
96 315574 : bool HasZerocoins() const { return hasZerocoins; }
97 478923 : bool IsShielded() const { return m_isShielded; }
98 11290898 : unsigned int GetSigOpCount() const { return sigOpCount; }
99 6894081 : int64_t GetModifiedFee() const { return nFee + feeDelta; }
100 3455596 : size_t DynamicMemoryUsage() const { return nUsageSize; }
101 :
102 : // Adjusts the descendant state, if this entry is not dirty.
103 : void UpdateDescendantState(int64_t modifySize, CAmount modifyFee, int64_t modifyCount);
104 : // Adjusts the ancestor state
105 : void UpdateAncestorState(int64_t modifySize, CAmount modifyFee, int64_t modifyCount, int modifySigOps);
106 : // Updates the fee delta used for mining priority score, and the
107 : // modified fees with descendants.
108 : void UpdateFeeDelta(int64_t feeDelta);
109 :
110 2671661 : uint64_t GetCountWithDescendants() const { return nCountWithDescendants; }
111 5894660 : uint64_t GetSizeWithDescendants() const { return nSizeWithDescendants; }
112 145938 : CAmount GetModFeesWithDescendants() const { return nModFeesWithDescendants; }
113 :
114 60327 : bool GetSpendsCoinbaseOrCoinstake() const { return spendsCoinbaseOrCoinstake; }
115 :
116 29367966 : uint64_t GetCountWithAncestors() const { return nCountWithAncestors; }
117 3575187 : uint64_t GetSizeWithAncestors() const { return nSizeWithAncestors; }
118 3575187 : CAmount GetModFeesWithAncestors() const { return nModFeesWithAncestors; }
119 3442218 : unsigned int GetSigOpCountWithAncestors() const { return nSigOpCountWithAncestors; }
120 : };
121 :
122 : // Helpers for modifying CTxMemPool::mapTx, which is a boost multi_index.
123 : struct update_descendant_state
124 : {
125 2623612 : update_descendant_state(int64_t _modifySize, CAmount _modifyFee, int64_t _modifyCount) :
126 2623612 : modifySize(_modifySize), modifyFee(_modifyFee), modifyCount(_modifyCount)
127 : {}
128 :
129 2623612 : void operator() (CTxMemPoolEntry &e)
130 2623612 : { e.UpdateDescendantState(modifySize, modifyFee, modifyCount); }
131 :
132 : private:
133 : int64_t modifySize;
134 : CAmount modifyFee;
135 : int64_t modifyCount;
136 : };
137 :
138 : struct update_ancestor_state
139 : {
140 271139 : update_ancestor_state(int64_t _modifySize, CAmount _modifyFee, int64_t _modifyCount, int _modifySigOps) :
141 271139 : modifySize(_modifySize), modifyFee(_modifyFee), modifyCount(_modifyCount), modifySigOps(_modifySigOps)
142 : {}
143 :
144 271139 : void operator() (CTxMemPoolEntry &e)
145 271139 : { e.UpdateAncestorState(modifySize, modifyFee, modifyCount, modifySigOps); }
146 :
147 : private:
148 : int64_t modifySize;
149 : CAmount modifyFee;
150 : int64_t modifyCount;
151 : int modifySigOps;
152 : };
153 :
154 : struct update_fee_delta
155 : {
156 2 : explicit update_fee_delta(int64_t _feeDelta) : feeDelta(_feeDelta) { }
157 :
158 2 : void operator() (CTxMemPoolEntry &e) { e.UpdateFeeDelta(feeDelta); }
159 :
160 : private:
161 : int64_t feeDelta;
162 : };
163 :
164 : // extracts a transaction hash from CTxMempoolEntry or CTransactionRef
165 : struct mempoolentry_txid
166 : {
167 : typedef uint256 result_type;
168 18708596 : result_type operator() (const CTxMemPoolEntry &entry) const
169 : {
170 15813806 : return entry.GetTx().GetHash();
171 : }
172 :
173 277034 : result_type operator() (const CTransactionRef& tx) const
174 : {
175 277034 : return tx->GetHash();
176 : }
177 : };
178 :
179 : /** \class CompareTxMemPoolEntryByDescendantScore
180 : *
181 : * Sort an entry by max(score/size of entry's tx, score/size with all descendants).
182 : */
183 : class CompareTxMemPoolEntryByDescendantScore
184 : {
185 : public:
186 43984449 : bool operator()(const CTxMemPoolEntry& a, const CTxMemPoolEntry& b) const
187 : {
188 43984449 : bool fUseADescendants = UseDescendantScore(a);
189 43984449 : bool fUseBDescendants = UseDescendantScore(b);
190 :
191 43149189 : double aModFee = fUseADescendants ? a.GetModFeesWithDescendants() : a.GetModifiedFee();
192 43984449 : double aSize = fUseADescendants ? a.GetSizeWithDescendants() : a.GetTxSize();
193 :
194 43984449 : double bModFee = fUseBDescendants ? b.GetModFeesWithDescendants() : b.GetModifiedFee();
195 43984449 : double bSize = fUseBDescendants ? b.GetSizeWithDescendants() : b.GetTxSize();
196 :
197 : // Avoid division by rewriting (a/b > c/d) as (a*d > c*b).
198 43984449 : double f1 = aModFee * bSize;
199 43984449 : double f2 = aSize * bModFee;
200 :
201 43984449 : if (f1 == f2) {
202 41495529 : return a.GetTime() >= b.GetTime();
203 : }
204 2488948 : return f1 < f2;
205 : }
206 :
207 : // Calculate which score to use for an entry (avoiding division).
208 43984449 : bool UseDescendantScore(const CTxMemPoolEntry &a) const
209 : {
210 43984449 : double f1 = (double)a.GetModifiedFee() * a.GetSizeWithDescendants();
211 43984449 : double f2 = (double)a.GetModFeesWithDescendants() * a.GetTxSize();
212 43984449 : return f2 > f1;
213 : }
214 : };
215 :
216 : /** \class CompareTxMemPoolEntryByScore
217 : *
218 : * Sort by score of entry ((fee+delta)/size) in descending order
219 : */
220 : class CompareTxMemPoolEntryByScore
221 : {
222 : public:
223 34199516 : bool operator()(const CTxMemPoolEntry& a, const CTxMemPoolEntry& b) const
224 : {
225 34199516 : double f1 = (double)a.GetModifiedFee() * b.GetTxSize();
226 34199516 : double f2 = (double)b.GetModifiedFee() * a.GetTxSize();
227 34199516 : if (f1 == f2) {
228 18618987 : return b.GetTx().GetHash() < a.GetTx().GetHash();
229 : }
230 15580433 : return f1 > f2;
231 : }
232 : };
233 :
234 : class CompareTxMemPoolEntryByEntryTime
235 : {
236 : public:
237 8920579 : bool operator()(const CTxMemPoolEntry& a, const CTxMemPoolEntry& b) const
238 : {
239 8920579 : return a.GetTime() < b.GetTime();
240 : }
241 : };
242 :
243 : class CompareTxMemPoolEntryByAncestorFee
244 : {
245 : public:
246 8888669 : bool operator()(const CTxMemPoolEntry& a, const CTxMemPoolEntry& b) const
247 : {
248 8888669 : double aFees = a.GetModFeesWithAncestors();
249 8888669 : double aSize = a.GetSizeWithAncestors();
250 :
251 8888669 : double bFees = b.GetModFeesWithAncestors();
252 8888669 : double bSize = b.GetSizeWithAncestors();
253 :
254 : // Avoid division by rewriting (a/b > c/d) as (a*d > c*b).
255 8888669 : double f1 = aFees * bSize;
256 8888669 : double f2 = aSize * bFees;
257 :
258 8888669 : if (f1 == f2) {
259 7525077 : return a.GetTx().GetHash() < b.GetTx().GetHash();
260 : }
261 :
262 1363583 : return f1 > f2;
263 : }
264 : };
265 :
266 : // Multi_index tag names
267 : struct descendant_score {};
268 : struct entry_time {};
269 : struct mining_score {};
270 : struct ancestor_score {};
271 :
272 : class CBlockPolicyEstimator;
273 :
274 : /**
275 : * Information about a mempool transaction.
276 : */
277 56692 : struct TxMempoolInfo
278 : {
279 : /** The transaction itself */
280 : CTransactionRef tx;
281 :
282 : /** Time the transaction entered the mempool. */
283 : int64_t nTime;
284 :
285 : /** Feerate of the transaction. */
286 : CFeeRate feeRate;
287 :
288 : /** The fee delta. */
289 : int64_t nFeeDelta;
290 : };
291 :
292 : /** Reason why a transaction was removed from the mempool,
293 : * this is passed to the notification signal.
294 : */
295 : enum class MemPoolRemovalReason {
296 : UNKNOWN = 0, //! Manually removed or unknown reason
297 : EXPIRY, //! Expired from mempool
298 : SIZELIMIT, //! Removed in size limiting
299 : REORG, //! Removed for reorganization
300 : BLOCK, //! Removed for block
301 : CONFLICT, //! Removed for conflict with in-block transaction
302 : REPLACED //! Removed for replacement
303 : };
304 :
305 : /**
306 : * CTxMemPool stores valid-according-to-the-current-best-chain
307 : * transactions that may be included in the next block.
308 : *
309 : * Transactions are added when they are seen on the network
310 : * (or created by the local node), but not all transactions seen
311 : * are added to the pool: if a new transaction double-spends
312 : * an input of a transaction in the pool, it is dropped,
313 : * as are non-standard transactions.
314 : *
315 : * CTxMemPool::mapTx, and CTxMemPoolEntry bookkeeping:
316 : *
317 : * mapTx is a boost::multi_index that sorts the mempool on 4 criteria:
318 : * - transaction hash
319 : * - feerate [we use max(feerate of tx, feerate of tx with all descendants)]
320 : * - time in mempool
321 : * - mining score (feerate modified by any fee deltas from PrioritiseTransaction)
322 :
323 : *
324 : * Note: the term "descendant" refers to in-mempool transactions that depend on
325 : * this one, while "ancestor" refers to in-mempool transactions that a given
326 : * transaction depends on.
327 : *
328 : * In order for the feerate sort to remain correct, we must update transactions
329 : * in the mempool when new descendants arrive. To facilitate this, we track
330 : * the set of in-mempool direct parents and direct children in mapLinks. Within
331 : * each CTxMemPoolEntry, we track the size and fees of all descendants.
332 : *
333 : * Usually when a new transaction is added to the mempool, it has no in-mempool
334 : * children (because any such children would be an orphan). So in
335 : * addUnchecked(), we:
336 : * - update a new entry's setMemPoolParents to include all in-mempool parents
337 : * - update the new entry's direct parents to include the new tx as a child
338 : * - update all ancestors of the transaction to include the new tx's size/fee
339 : *
340 : * When a transaction is removed from the mempool, we must:
341 : * - update all in-mempool parents to not track the tx in setMemPoolChildren
342 : * - update all ancestors to not include the tx's size/fees in descendant state
343 : * - update all in-mempool children to not include it as a parent
344 : *
345 : * These happen in UpdateForRemoveFromMempool(). (Note that when removing a
346 : * transaction along with its descendants, we must calculate that set of
347 : * transactions to be removed before doing the removal, or else the mempool can
348 : * be in an inconsistent state where it's impossible to walk the ancestors of
349 : * a transaction.)
350 : *
351 : * In the event of a reorg, the assumption that a newly added tx has no
352 : * in-mempool children is false. In particular, the mempool is in an
353 : * inconsistent state while new transactions are being added, because there may
354 : * be descendant transactions of a tx coming from a disconnected block that are
355 : * unreachable from just looking at transactions in the mempool (the linking
356 : * transactions may also be in the disconnected block, waiting to be added).
357 : * Because of this, there's not much benefit in trying to search for in-mempool
358 : * children in addUnchecked(). Instead, in the special case of transactions
359 : * being added from a disconnected block, we require the caller to clean up the
360 : * state, to account for in-mempool, out-of-block descendants for all the
361 : * in-block transactions by calling UpdateTransactionsFromBlock(). Note that
362 : * until this is called, the mempool state is not consistent, and in particular
363 : * mapLinks may not be correct (and therefore functions like
364 : * CalculateMemPoolAncestors() and CalculateDescendants() that rely
365 : * on them to walk the mempool are not generally safe to use).
366 : *
367 : * Computational limits:
368 : *
369 : * Updating all in-mempool ancestors of a newly added transaction can be slow,
370 : * if no bound exists on how many in-mempool ancestors there may be.
371 : * CalculateMemPoolAncestors() takes configurable limits that are designed to
372 : * prevent these calculations from being too CPU intensive.
373 : *
374 : * Adding transactions from a disconnected block can be very time consuming,
375 : * because we don't have a way to limit the number of in-mempool descendants.
376 : * To bound CPU processing, we limit the amount of work we're willing to do
377 : * to properly update the descendant information for a tx being added from
378 : * a disconnected block. If we would exceed the limit, then we instead mark
379 : * the entry as "dirty", and set the feerate for sorting purposes to be equal
380 : * the feerate of the transaction without any descendants.
381 : *
382 : */
383 : class CTxMemPool
384 : {
385 : private:
386 : uint32_t nCheckFrequency; //! Value n means that n times in 2^32 we check.
387 : unsigned int nTransactionsUpdated;
388 : CBlockPolicyEstimator* minerPolicyEstimator;
389 :
390 : CFeeRate minRelayFee; //! Passed to constructor to avoid dependency on main
391 : uint64_t totalTxSize; //! sum of all mempool tx' byte sizes
392 : uint64_t cachedInnerUsage; //! sum of dynamic memory usage of all the map elements (NOT the maps themselves)
393 :
394 : CFeeRate minReasonableRelayFee;
395 :
396 : mutable int64_t lastRollingFeeUpdate;
397 : mutable bool blockSinceLastRollingFeeBump;
398 : mutable double rollingMinimumFeeRate; //! minimum fee to get into the pool, decreases exponentially
399 :
400 : void trackPackageRemoved(const CFeeRate& rate);
401 :
402 : // Shielded txes
403 : std::map<uint256, CTransactionRef> mapSaplingNullifiers;
404 : void checkNullifiers() const;
405 :
406 : bool m_is_loaded GUARDED_BY(cs){false};
407 :
408 : public:
409 :
410 : static const int ROLLING_FEE_HALFLIFE = 60 * 60 * 12; // public only for testing
411 :
412 : typedef boost::multi_index_container<
413 : CTxMemPoolEntry,
414 : boost::multi_index::indexed_by<
415 : // sorted by txid
416 : boost::multi_index::hashed_unique<mempoolentry_txid, SaltedIdHasher>,
417 : // sorted by fee rate
418 : boost::multi_index::ordered_non_unique<
419 : boost::multi_index::tag<descendant_score>,
420 : boost::multi_index::identity<CTxMemPoolEntry>,
421 : CompareTxMemPoolEntryByDescendantScore
422 : >,
423 : // sorted by entry time
424 : boost::multi_index::ordered_non_unique<
425 : boost::multi_index::tag<entry_time>,
426 : boost::multi_index::identity<CTxMemPoolEntry>,
427 : CompareTxMemPoolEntryByEntryTime
428 : >,
429 : // sorted by score (for mining prioritization)
430 : boost::multi_index::ordered_unique<
431 : boost::multi_index::tag<mining_score>,
432 : boost::multi_index::identity<CTxMemPoolEntry>,
433 : CompareTxMemPoolEntryByScore
434 : >,
435 : // sorted by fee rate with ancestors
436 : boost::multi_index::ordered_non_unique<
437 : boost::multi_index::tag<ancestor_score>,
438 : boost::multi_index::identity<CTxMemPoolEntry>,
439 : CompareTxMemPoolEntryByAncestorFee
440 : >
441 : >
442 : > indexed_transaction_set;
443 :
444 : /**
445 : * This mutex needs to be locked when accessing `mapTx` or other members
446 : * that are guarded by it.
447 : *
448 : * @par Consistency guarantees
449 : *
450 : * By design, it is guaranteed that:
451 : *
452 : * 1. Locking both `cs_main` and `mempool.cs` will give a view of mempool
453 : * that is consistent with current chain tip (`::ChainActive()` and
454 : * `CoinsTip()`) and is fully populated. Fully populated means that if the
455 : * current active chain is missing transactions that were present in a
456 : * previously active chain, all the missing transactions will have been
457 : * re-added to the mempool and should be present if they meet size and
458 : * consistency constraints.
459 : *
460 : * 2. Locking `mempool.cs` without `cs_main` will give a view of a mempool
461 : * consistent with some chain that was active since `cs_main` was last
462 : * locked, and that is fully populated as described above. It is ok for
463 : * code that only needs to query or remove transactions from the mempool
464 : * to lock just `mempool.cs` without `cs_main`.
465 : *
466 : * To provide these guarantees, it is necessary to lock both `cs_main` and
467 : * `mempool.cs` whenever adding transactions to the mempool and whenever
468 : * changing the chain tip. It's necessary to keep both mutexes locked until
469 : * the mempool is consistent with the new chain tip and fully populated.
470 : */
471 : mutable RecursiveMutex cs;
472 : indexed_transaction_set mapTx;
473 :
474 : typedef indexed_transaction_set::nth_index<0>::type::iterator txiter;
475 :
476 : struct CompareIteratorByHash {
477 342030358 : bool operator()(const txiter &a, const txiter &b) const {
478 335021358 : return a->GetTx().GetHash() < b->GetTx().GetHash();
479 : }
480 : };
481 : typedef std::set<txiter, CompareIteratorByHash> setEntries;
482 :
483 : const setEntries & GetMemPoolParents(txiter entry) const;
484 : const setEntries & GetMemPoolChildren(txiter entry) const;
485 :
486 : private:
487 : typedef std::map<txiter, setEntries, CompareIteratorByHash> cacheMap;
488 :
489 191011 : struct TxLinks {
490 : setEntries parents;
491 : setEntries children;
492 : };
493 :
494 : typedef std::map<txiter, TxLinks, CompareIteratorByHash> txlinksMap;
495 : txlinksMap mapLinks;
496 :
497 : std::multimap<uint256, uint256> mapProTxRefs; // proTxHash -> transaction (all TXs that refer to an existing proTx)
498 : std::map<CService, uint256> mapProTxAddresses;
499 : std::map<CKeyID, uint256> mapProTxPubKeyIDs;
500 : std::map<uint256, uint256> mapProTxBlsPubKeyHashes;
501 : std::map<COutPoint, uint256> mapProTxCollaterals;
502 :
503 : void UpdateParent(txiter entry, txiter parent, bool add);
504 : void UpdateChild(txiter entry, txiter child, bool add);
505 :
506 : std::vector<indexed_transaction_set::const_iterator> GetSortedDepthAndScore() const;
507 :
508 : public:
509 : indirectmap<COutPoint, CTransactionRef> mapNextTx;
510 : std::map<uint256, CAmount> mapDeltas;
511 :
512 : /** Create a new CTxMemPool.
513 : * minReasonableRelayFee should be a feerate which is, roughly, somewhere
514 : * around what it "costs" to relay a transaction around the network and
515 : * below which we would reasonably say a transaction has 0-effective-fee.
516 : */
517 : explicit CTxMemPool(const CFeeRate& _minReasonableRelayFee);
518 : ~CTxMemPool();
519 :
520 : /**
521 : * If sanity-checking is turned on, check makes sure the pool is
522 : * consistent (does not contain two transactions that spend the same inputs,
523 : * all inputs are in the mapNextTx array). If sanity-checking is turned off,
524 : * check does nothing.
525 : */
526 : void check(const CCoinsViewCache *pcoins) const;
527 382 : void setSanityCheck(double dFrequency = 1.0) { nCheckFrequency = dFrequency * 4294967295.0; }
528 :
529 : // addUnchecked must updated state for all ancestors of a given transaction,
530 : // to track size/count of descendant transactions. First version of
531 : // addUnchecked can be used to have it call CalculateMemPoolAncestors(), and
532 : // then invoke the second version.
533 : // Note that addUnchecked is ONLY called from ATMP outside of tests
534 : // and any other callers may break wallet's in-mempool tracking (due to
535 : // lack of CValidationInterface::TransactionAddedToMempool callbacks).
536 : bool addUnchecked(const uint256& hash, const CTxMemPoolEntry& entry, bool validFeeEstimate = true);
537 : bool addUnchecked(const uint256& hash, const CTxMemPoolEntry &entry, setEntries &setAncestors, bool validFeeEstimate = true);
538 :
539 : void removeRecursive(const CTransaction& tx, MemPoolRemovalReason reason = MemPoolRemovalReason::UNKNOWN);
540 : void removeForReorg(const CCoinsViewCache* pcoins, unsigned int nMemPoolHeight, int flags);
541 : void removeWithAnchor(const uint256& invalidRoot);
542 : void removeConflicts(const CTransaction& tx);
543 : void removeForBlock(const std::vector<CTransactionRef>& vtx, unsigned int nBlockHeight);
544 :
545 : void clear();
546 : void _clear(); // lock-free
547 : bool CompareDepthAndScore(const uint256& hasha, const uint256& hashb);
548 : void queryHashes(std::vector<uint256>& vtxid);
549 : void getTransactions(std::set<uint256>& setTxid);
550 : bool isSpent(const COutPoint& outpoint);
551 : unsigned int GetTransactionsUpdated() const;
552 : void AddTransactionsUpdated(unsigned int n);
553 : /**
554 : * Check that none of this transactions inputs are in the mempool, and thus
555 : * the tx is not dependent on other mempool transactions to be included in a block.
556 : */
557 : bool HasNoInputsOf(const CTransaction& tx) const;
558 :
559 : /** Affect CreateNewBlock prioritisation of transactions */
560 : void PrioritiseTransaction(const uint256& hash, const CAmount& nFeeDelta);
561 : void ApplyDelta(const uint256& hash, CAmount& nFeeDelta) const;
562 : void ClearPrioritisation(const uint256 hash);
563 :
564 : bool nullifierExists(const uint256& nullifier) const;
565 :
566 : /** Remove a set of transactions from the mempool.
567 : * If a transaction is in this set, then all in-mempool descendants must
568 : * also be in the set, unless this transaction is being removed for being
569 : * in a block.
570 : * Set updateDescendants to true when removing a tx that was in a block, so
571 : * that any in-mempool descendants have their ancestor state updated.
572 : */
573 : void RemoveStaged(setEntries &stage, bool updateDescendants, MemPoolRemovalReason reason = MemPoolRemovalReason::UNKNOWN);
574 :
575 : /** When adding transactions from a disconnected block back to the mempool,
576 : * new mempool entries may have children in the mempool (which is generally
577 : * not the case when otherwise adding transactions).
578 : * UpdateTransactionsFromBlock() will find child transactions and update the
579 : * descendant state for each transaction in hashesToUpdate (excluding any
580 : * child transactions present in hashesToUpdate, which are already accounted
581 : * for). Note: hashesToUpdate should be the set of transactions from the
582 : * disconnected block that have been accepted back into the mempool.
583 : */
584 : void UpdateTransactionsFromBlock(const std::vector<uint256> &hashesToUpdate);
585 :
586 : /** Try to calculate all in-mempool ancestors of entry.
587 : * (these are all calculated including the tx itself)
588 : * limitAncestorCount = max number of ancestors
589 : * limitAncestorSize = max size of ancestors
590 : * limitDescendantCount = max number of descendants any ancestor can have
591 : * limitDescendantSize = max size of descendants any ancestor can have
592 : * errString = populated with error reason if any limits are hit
593 : * fSearchForParents = whether to search a tx's vin for in-mempool parents, or
594 : * look up parents from mapLinks. Must be true for entries not in the mempool
595 : */
596 : bool CalculateMemPoolAncestors(const CTxMemPoolEntry &entry, setEntries &setAncestors, uint64_t limitAncestorCount, uint64_t limitAncestorSize, uint64_t limitDescendantCount, uint64_t limitDescendantSize, std::string &errString, bool fSearchForParents = true) const;
597 :
598 : /** Populate setDescendants with all in-mempool descendants of hash.
599 : * Assumes that setDescendants includes all in-mempool descendants of anything
600 : * already in it. */
601 : void CalculateDescendants(txiter it, setEntries &setDescendants);
602 :
603 : /** The minimum fee to get into the mempool, which may itself not be enough
604 : * for larger-sized transactions.
605 : * The minReasonableRelayFee constructor arg is used to bound the time it
606 : * takes the fee rate to go back down all the way to 0. When the feerate
607 : * would otherwise be half of this, it is set to 0 instead.
608 : */
609 : CFeeRate GetMinFee(size_t sizelimit) const;
610 :
611 : /** Remove transactions from the mempool until its dynamic size is <= sizelimit.
612 : * pvNoSpendsRemaining, if set, will be populated with the list of transactions
613 : * which are not in mempool which no longer have any spends in this mempool.
614 : */
615 : void TrimToSize(size_t sizelimit, std::vector<COutPoint>* pvNoSpendsRemaining = nullptr);
616 :
617 : /** Expire all transaction (and their dependencies) in the mempool older than time. Return the number of removed transactions. */
618 : int Expire(int64_t time);
619 :
620 : /** Returns false if the transaction is in the mempool and not within the chain limit specified. */
621 : bool TransactionWithinChainLimit(const uint256& txid, size_t chainLimit) const;
622 :
623 : /** @returns true if the mempool is fully loaded */
624 : bool IsLoaded() const;
625 :
626 : /** Sets the current loaded state */
627 : void SetIsLoaded(bool loaded);
628 :
629 9783 : unsigned long size() const
630 : {
631 9783 : LOCK(cs);
632 9783 : return mapTx.size();
633 : }
634 378 : uint64_t GetTotalTxSize()
635 : {
636 378 : LOCK(cs);
637 378 : return totalTxSize;
638 : }
639 :
640 878852 : bool exists(uint256 hash) const
641 : {
642 878852 : LOCK(cs);
643 1757706 : return (mapTx.count(hash) != 0);
644 : }
645 :
646 0 : bool exists(const COutPoint& outpoint) const
647 : {
648 0 : LOCK(cs);
649 0 : auto it = mapTx.find(outpoint.hash);
650 0 : return (it != mapTx.end() && outpoint.n < it->GetTx().vout.size());
651 : }
652 :
653 : CTransactionRef get(const uint256& hash) const;
654 : TxMempoolInfo info(const uint256& hash) const;
655 : std::vector<TxMempoolInfo> infoAll() const;
656 :
657 : bool existsProviderTxConflict(const CTransaction &tx) const;
658 : void removeProTxReferences(const uint256& proTxHash, MemPoolRemovalReason reason);
659 :
660 : /** Estimate fee rate needed to get into the next nBlocks
661 : * If no answer can be given at nBlocks, return an estimate
662 : * at the lowest number of blocks where one can be given
663 : */
664 : CFeeRate estimateSmartFee(int nBlocks, int *answerFoundAtBlocks = nullptr) const;
665 :
666 : /** Estimate fee rate needed to get into the next nBlocks */
667 : CFeeRate estimateFee(int nBlocks) const;
668 :
669 : /** Write/Read estimates to disk */
670 : bool WriteFeeEstimates(CAutoFile& fileout) const;
671 : bool ReadFeeEstimates(CAutoFile& filein);
672 :
673 : size_t DynamicMemoryUsage() const;
674 :
675 : private:
676 : /** UpdateForDescendants is used by UpdateTransactionsFromBlock to update
677 : * the descendants for a single transaction that has been added to the
678 : * mempool but may have child transactions in the mempool, eg during a
679 : * chain reorg. setExclude is the set of descendant transactions in the
680 : * mempool that must not be accounted for (because any descendants in
681 : * setExclude were added to the mempool after the transaction being
682 : * updated and hence their state is already reflected in the parent
683 : * state).
684 : *
685 : * cachedDescendants will be updated with the descendants of the transaction
686 : * being updated, so that future invocations don't need to walk the
687 : * same transaction again, if encountered in another transaction chain.
688 : */
689 : void UpdateForDescendants(txiter updateIt,
690 : cacheMap &cachedDescendants,
691 : const std::set<uint256> &setExclude);
692 : /** Update ancestors of hash to add/remove it as a descendant transaction. */
693 : void UpdateAncestorsOf(bool add, txiter hash, setEntries &setAncestors);
694 : /** Set ancestor state for an entry */
695 : void UpdateEntryForAncestors(txiter it, const setEntries &setAncestors);
696 : /** For each transaction being removed, update ancestors and any direct children.
697 : * If updateDescendants is true, then also update in-mempool descendants'
698 : * ancestor state. */
699 : void UpdateForRemoveFromMempool(const setEntries &entriesToRemove, bool updateDescendants);
700 : /** Sever link between specified transaction and direct children. */
701 : void UpdateChildrenForRemoval(txiter entry);
702 :
703 : /** Before calling removeUnchecked for a given transaction,
704 : * UpdateForRemoveFromMempool must be called on the entire (dependent) set
705 : * of transactions being removed at the same time. We use each
706 : * CTxMemPoolEntry's setMemPoolParents in order to walk ancestors of a
707 : * given transaction that is removed, so we can't remove intermediate
708 : * transactions in a chain before we've updated all the state for the
709 : * removal.
710 : */
711 : void removeUnchecked(txiter entry, MemPoolRemovalReason reason = MemPoolRemovalReason::UNKNOWN);
712 :
713 : /** Special txes **/
714 : void addUncheckedSpecialTx(const CTransaction& tx);
715 : void removeUncheckedSpecialTx(const CTransaction& tx);
716 : void removeProTxPubKeyConflicts(const CTransaction &tx, const CKeyID &keyId);
717 : void removeProTxPubKeyConflicts(const CTransaction& tx, const CBLSPublicKey& pubKey);
718 : void removeProTxCollateralConflicts(const CTransaction &tx, const COutPoint &collateralOutpoint);
719 : void removeProTxSpentCollateralConflicts(const CTransaction &tx);
720 : void removeProTxConflicts(const CTransaction &tx);
721 :
722 : };
723 :
724 : /**
725 : * CCoinsView that brings transactions from a memorypool into view.
726 : * It does not check for spendings by memory pool transactions.
727 : */
728 280826 : class CCoinsViewMemPool : public CCoinsViewBacked
729 : {
730 : protected:
731 : CTxMemPool& mempool;
732 :
733 : public:
734 : CCoinsViewMemPool(CCoinsView* baseIn, CTxMemPool& mempoolIn);
735 : bool GetCoin(const COutPoint& outpoint, Coin& coin) const;
736 : bool HaveCoin(const COutPoint& outpoint) const;
737 : bool GetNullifier(const uint256& nullifier) const;
738 : };
739 :
740 : /**
741 : * DisconnectedBlockTransactions
742 : * During the reorg, it's desirable to re-add previously confirmed transactions
743 : * to the mempool, so that anything not re-confirmed in the new chain is
744 : * available to be mined. However, it's more efficient to wait until the reorg
745 : * is complete and process all still-unconfirmed transactions at that time,
746 : * since we expect most confirmed transactions to (typically) still be
747 : * confirmed in the new chain, and re-accepting to the memory pool is expensive
748 : * (and therefore better to not do in the middle of reorg-processing).
749 : * Instead, store the disconnected transactions (in order!) as we go, remove any
750 : * that are included in blocks in the new chain, and then process the remaining
751 : * still-unconfirmed transactions at the end.
752 : */
753 :
754 : // multi_index tag names
755 : struct txid_index {};
756 : struct insertion_order {};
757 :
758 41555 : struct DisconnectedBlockTransactions {
759 : typedef boost::multi_index_container<
760 : CTransactionRef,
761 : boost::multi_index::indexed_by<
762 : // sorted by txid
763 : boost::multi_index::hashed_unique<
764 : boost::multi_index::tag<txid_index>,
765 : mempoolentry_txid,
766 : SaltedIdHasher
767 : >,
768 : // sorted by order in the blockchain
769 : boost::multi_index::sequenced<
770 : boost::multi_index::tag<insertion_order>
771 : >
772 : >
773 : > indexed_disconnected_transactions;
774 :
775 : // It's almost certainly a logic bug if we don't clear out queuedTx before
776 : // destruction, as we add to it while disconnecting blocks, and then we
777 : // need to re-process remaining transactions to ensure mempool consistency.
778 : // For now, assert() that we've emptied out this object on destruction.
779 : // This assert() can always be removed if the reorg-processing code were
780 : // to be refactored such that this assumption is no longer true (for
781 : // instance if there was some other way we cleaned up the mempool after a
782 : // reorg, besides draining this object).
783 41555 : ~DisconnectedBlockTransactions() { assert(queuedTx.empty()); }
784 :
785 : indexed_disconnected_transactions queuedTx;
786 : uint64_t cachedInnerUsage = 0;
787 :
788 : // Estimate the overhead of queuedTx to be 6 pointers + an allocation, as
789 : // no exact formula for boost::multi_index_contained is implemented.
790 10176 : size_t DynamicMemoryUsage() const {
791 10176 : return memusage::MallocUsage(sizeof(CTransactionRef) + 6 * sizeof(void*)) * queuedTx.size() + cachedInnerUsage;
792 : }
793 :
794 88675 : void addTransaction(const CTransactionRef& tx)
795 : {
796 88675 : queuedTx.insert(tx);
797 88675 : cachedInnerUsage += memusage::RecursiveDynamicUsage(tx);
798 88675 : }
799 :
800 : // Remove entries based on txid_index, and update memory usage.
801 41568 : void removeForBlock(const std::vector<CTransactionRef>& vtx)
802 : {
803 : // Short-circuit in the common case of a block being added to the tip
804 41568 : if (queuedTx.empty()) {
805 : return;
806 : }
807 25336 : for (auto const &tx : vtx) {
808 25217 : auto it = queuedTx.find(tx->GetHash());
809 25217 : if (it != queuedTx.end()) {
810 20053 : cachedInnerUsage -= memusage::RecursiveDynamicUsage(*it);
811 20053 : queuedTx.erase(it);
812 : }
813 : }
814 : }
815 :
816 : // Remove an entry by insertion_order index, and update memory usage.
817 9847 : void removeEntry(indexed_disconnected_transactions::index<insertion_order>::type::iterator entry)
818 : {
819 9847 : cachedInnerUsage -= memusage::RecursiveDynamicUsage(*entry);
820 9847 : queuedTx.get<insertion_order>().erase(entry);
821 9847 : }
822 :
823 : void clear()
824 : {
825 : cachedInnerUsage = 0;
826 : queuedTx.clear();
827 : }
828 : };
829 :
830 : #endif // PIVX_TXMEMPOOL_H
|
