1 // Copyright (c) 2009-2010 Satoshi Nakamoto
2 // Copyright (c) 2009-2016 The Bitcoin Core developers
3 // Distributed under the MIT software license, see the accompanying
4 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
6 #ifndef BITCOIN_TXMEMPOOL_H
7 #define BITCOIN_TXMEMPOOL_H
18 #include "indirectmap.h"
19 #include "policy/feerate.h"
20 #include "primitives/transaction.h"
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>
29 #include <boost/signals2/signal.hpp>
34 /** Fake height value used in Coin to signify they are only in the memory pool (since 0.8) */
35 static const uint32_t MEMPOOL_HEIGHT
= 0x7FFFFFFF;
39 // Will be set to the blockchain height and median time past
40 // values that would be necessary to satisfy all relative locktime
41 // constraints (BIP68) of this tx given our view of block chain history
44 // As long as the current chain descends from the highest height block
45 // containing one of the inputs used in the calculation, then the cached
46 // values are still valid even after a reorg.
47 CBlockIndex
* maxInputBlock
;
49 LockPoints() : height(0), time(0), maxInputBlock(NULL
) { }
54 /** \class CTxMemPoolEntry
56 * CTxMemPoolEntry stores data about the corresponding transaction, as well
57 * as data about all in-mempool transactions that depend on the transaction
58 * ("descendant" transactions).
60 * When a new entry is added to the mempool, we update the descendant state
61 * (nCountWithDescendants, nSizeWithDescendants, and nModFeesWithDescendants) for
62 * all ancestors of the newly added transaction.
70 CAmount nFee
; //!< Cached to avoid expensive parent-transaction lookups
71 size_t nTxWeight
; //!< ... and avoid recomputing tx weight (also used for GetTxSize())
72 size_t nUsageSize
; //!< ... and total memory usage
73 int64_t nTime
; //!< Local time when entering the mempool
74 unsigned int entryHeight
; //!< Chain height when entering the mempool
75 bool spendsCoinbase
; //!< keep track of transactions that spend a coinbase
76 int64_t sigOpCost
; //!< Total sigop cost
77 int64_t feeDelta
; //!< Used for determining the priority of the transaction for mining in a block
78 LockPoints lockPoints
; //!< Track the height and time at which tx was final
80 // Information about descendants of this transaction that are in the
81 // mempool; if we remove this transaction we must remove all of these
82 // descendants as well.
83 uint64_t nCountWithDescendants
; //!< number of descendant transactions
84 uint64_t nSizeWithDescendants
; //!< ... and size
85 CAmount nModFeesWithDescendants
; //!< ... and total fees (all including us)
87 // Analogous statistics for ancestor transactions
88 uint64_t nCountWithAncestors
;
89 uint64_t nSizeWithAncestors
;
90 CAmount nModFeesWithAncestors
;
91 int64_t nSigOpCostWithAncestors
;
94 CTxMemPoolEntry(const CTransactionRef
& _tx
, const CAmount
& _nFee
,
95 int64_t _nTime
, unsigned int _entryHeight
,
97 int64_t nSigOpsCost
, LockPoints lp
);
99 CTxMemPoolEntry(const CTxMemPoolEntry
& other
);
101 const CTransaction
& GetTx() const { return *this->tx
; }
102 CTransactionRef
GetSharedTx() const { return this->tx
; }
103 const CAmount
& GetFee() const { return nFee
; }
104 size_t GetTxSize() const;
105 size_t GetTxWeight() const { return nTxWeight
; }
106 int64_t GetTime() const { return nTime
; }
107 unsigned int GetHeight() const { return entryHeight
; }
108 int64_t GetSigOpCost() const { return sigOpCost
; }
109 int64_t GetModifiedFee() const { return nFee
+ feeDelta
; }
110 size_t DynamicMemoryUsage() const { return nUsageSize
; }
111 const LockPoints
& GetLockPoints() const { return lockPoints
; }
113 // Adjusts the descendant state.
114 void UpdateDescendantState(int64_t modifySize
, CAmount modifyFee
, int64_t modifyCount
);
115 // Adjusts the ancestor state
116 void UpdateAncestorState(int64_t modifySize
, CAmount modifyFee
, int64_t modifyCount
, int modifySigOps
);
117 // Updates the fee delta used for mining priority score, and the
118 // modified fees with descendants.
119 void UpdateFeeDelta(int64_t feeDelta
);
120 // Update the LockPoints after a reorg
121 void UpdateLockPoints(const LockPoints
& lp
);
123 uint64_t GetCountWithDescendants() const { return nCountWithDescendants
; }
124 uint64_t GetSizeWithDescendants() const { return nSizeWithDescendants
; }
125 CAmount
GetModFeesWithDescendants() const { return nModFeesWithDescendants
; }
127 bool GetSpendsCoinbase() const { return spendsCoinbase
; }
129 uint64_t GetCountWithAncestors() const { return nCountWithAncestors
; }
130 uint64_t GetSizeWithAncestors() const { return nSizeWithAncestors
; }
131 CAmount
GetModFeesWithAncestors() const { return nModFeesWithAncestors
; }
132 int64_t GetSigOpCostWithAncestors() const { return nSigOpCostWithAncestors
; }
134 mutable size_t vTxHashesIdx
; //!< Index in mempool's vTxHashes
137 // Helpers for modifying CTxMemPool::mapTx, which is a boost multi_index.
138 struct update_descendant_state
140 update_descendant_state(int64_t _modifySize
, CAmount _modifyFee
, int64_t _modifyCount
) :
141 modifySize(_modifySize
), modifyFee(_modifyFee
), modifyCount(_modifyCount
)
144 void operator() (CTxMemPoolEntry
&e
)
145 { e
.UpdateDescendantState(modifySize
, modifyFee
, modifyCount
); }
153 struct update_ancestor_state
155 update_ancestor_state(int64_t _modifySize
, CAmount _modifyFee
, int64_t _modifyCount
, int64_t _modifySigOpsCost
) :
156 modifySize(_modifySize
), modifyFee(_modifyFee
), modifyCount(_modifyCount
), modifySigOpsCost(_modifySigOpsCost
)
159 void operator() (CTxMemPoolEntry
&e
)
160 { e
.UpdateAncestorState(modifySize
, modifyFee
, modifyCount
, modifySigOpsCost
); }
166 int64_t modifySigOpsCost
;
169 struct update_fee_delta
171 update_fee_delta(int64_t _feeDelta
) : feeDelta(_feeDelta
) { }
173 void operator() (CTxMemPoolEntry
&e
) { e
.UpdateFeeDelta(feeDelta
); }
179 struct update_lock_points
181 update_lock_points(const LockPoints
& _lp
) : lp(_lp
) { }
183 void operator() (CTxMemPoolEntry
&e
) { e
.UpdateLockPoints(lp
); }
186 const LockPoints
& lp
;
189 // extracts a transaction hash from CTxMempoolEntry or CTransactionRef
190 struct mempoolentry_txid
192 typedef uint256 result_type
;
193 result_type
operator() (const CTxMemPoolEntry
&entry
) const
195 return entry
.GetTx().GetHash();
198 result_type
operator() (const CTransactionRef
& tx
) const
200 return tx
->GetHash();
204 /** \class CompareTxMemPoolEntryByDescendantScore
206 * Sort an entry by max(score/size of entry's tx, score/size with all descendants).
208 class CompareTxMemPoolEntryByDescendantScore
211 bool operator()(const CTxMemPoolEntry
& a
, const CTxMemPoolEntry
& b
)
213 bool fUseADescendants
= UseDescendantScore(a
);
214 bool fUseBDescendants
= UseDescendantScore(b
);
216 double aModFee
= fUseADescendants
? a
.GetModFeesWithDescendants() : a
.GetModifiedFee();
217 double aSize
= fUseADescendants
? a
.GetSizeWithDescendants() : a
.GetTxSize();
219 double bModFee
= fUseBDescendants
? b
.GetModFeesWithDescendants() : b
.GetModifiedFee();
220 double bSize
= fUseBDescendants
? b
.GetSizeWithDescendants() : b
.GetTxSize();
222 // Avoid division by rewriting (a/b > c/d) as (a*d > c*b).
223 double f1
= aModFee
* bSize
;
224 double f2
= aSize
* bModFee
;
227 return a
.GetTime() >= b
.GetTime();
232 // Calculate which score to use for an entry (avoiding division).
233 bool UseDescendantScore(const CTxMemPoolEntry
&a
)
235 double f1
= (double)a
.GetModifiedFee() * a
.GetSizeWithDescendants();
236 double f2
= (double)a
.GetModFeesWithDescendants() * a
.GetTxSize();
241 /** \class CompareTxMemPoolEntryByScore
243 * Sort by score of entry ((fee+delta)/size) in descending order
245 class CompareTxMemPoolEntryByScore
248 bool operator()(const CTxMemPoolEntry
& a
, const CTxMemPoolEntry
& b
)
250 double f1
= (double)a
.GetModifiedFee() * b
.GetTxSize();
251 double f2
= (double)b
.GetModifiedFee() * a
.GetTxSize();
253 return b
.GetTx().GetHash() < a
.GetTx().GetHash();
259 class CompareTxMemPoolEntryByEntryTime
262 bool operator()(const CTxMemPoolEntry
& a
, const CTxMemPoolEntry
& b
)
264 return a
.GetTime() < b
.GetTime();
268 class CompareTxMemPoolEntryByAncestorFee
271 bool operator()(const CTxMemPoolEntry
& a
, const CTxMemPoolEntry
& b
)
273 double aFees
= a
.GetModFeesWithAncestors();
274 double aSize
= a
.GetSizeWithAncestors();
276 double bFees
= b
.GetModFeesWithAncestors();
277 double bSize
= b
.GetSizeWithAncestors();
279 // Avoid division by rewriting (a/b > c/d) as (a*d > c*b).
280 double f1
= aFees
* bSize
;
281 double f2
= aSize
* bFees
;
284 return a
.GetTx().GetHash() < b
.GetTx().GetHash();
291 // Multi_index tag names
292 struct descendant_score
{};
293 struct entry_time
{};
294 struct mining_score
{};
295 struct ancestor_score
{};
297 class CBlockPolicyEstimator
;
300 * Information about a mempool transaction.
304 /** The transaction itself */
307 /** Time the transaction entered the mempool. */
310 /** Feerate of the transaction. */
313 /** The fee delta. */
317 /** Reason why a transaction was removed from the mempool,
318 * this is passed to the notification signal.
320 enum class MemPoolRemovalReason
{
321 UNKNOWN
= 0, //! Manually removed or unknown reason
322 EXPIRY
, //! Expired from mempool
323 SIZELIMIT
, //! Removed in size limiting
324 REORG
, //! Removed for reorganization
325 BLOCK
, //! Removed for block
326 CONFLICT
, //! Removed for conflict with in-block transaction
327 REPLACED
//! Removed for replacement
330 class SaltedTxidHasher
334 const uint64_t k0
, k1
;
339 size_t operator()(const uint256
& txid
) const {
340 return SipHashUint256(k0
, k1
, txid
);
345 * CTxMemPool stores valid-according-to-the-current-best-chain transactions
346 * that may be included in the next block.
348 * Transactions are added when they are seen on the network (or created by the
349 * local node), but not all transactions seen are added to the pool. For
350 * example, the following new transactions will not be added to the mempool:
351 * - a transaction which doesn't meet the minimum fee requirements.
352 * - a new transaction that double-spends an input of a transaction already in
353 * the pool where the new transaction does not meet the Replace-By-Fee
354 * requirements as defined in BIP 125.
355 * - a non-standard transaction.
357 * CTxMemPool::mapTx, and CTxMemPoolEntry bookkeeping:
359 * mapTx is a boost::multi_index that sorts the mempool on 4 criteria:
361 * - feerate [we use max(feerate of tx, feerate of tx with all descendants)]
363 * - mining score (feerate modified by any fee deltas from PrioritiseTransaction)
365 * Note: the term "descendant" refers to in-mempool transactions that depend on
366 * this one, while "ancestor" refers to in-mempool transactions that a given
367 * transaction depends on.
369 * In order for the feerate sort to remain correct, we must update transactions
370 * in the mempool when new descendants arrive. To facilitate this, we track
371 * the set of in-mempool direct parents and direct children in mapLinks. Within
372 * each CTxMemPoolEntry, we track the size and fees of all descendants.
374 * Usually when a new transaction is added to the mempool, it has no in-mempool
375 * children (because any such children would be an orphan). So in
376 * addUnchecked(), we:
377 * - update a new entry's setMemPoolParents to include all in-mempool parents
378 * - update the new entry's direct parents to include the new tx as a child
379 * - update all ancestors of the transaction to include the new tx's size/fee
381 * When a transaction is removed from the mempool, we must:
382 * - update all in-mempool parents to not track the tx in setMemPoolChildren
383 * - update all ancestors to not include the tx's size/fees in descendant state
384 * - update all in-mempool children to not include it as a parent
386 * These happen in UpdateForRemoveFromMempool(). (Note that when removing a
387 * transaction along with its descendants, we must calculate that set of
388 * transactions to be removed before doing the removal, or else the mempool can
389 * be in an inconsistent state where it's impossible to walk the ancestors of
392 * In the event of a reorg, the assumption that a newly added tx has no
393 * in-mempool children is false. In particular, the mempool is in an
394 * inconsistent state while new transactions are being added, because there may
395 * be descendant transactions of a tx coming from a disconnected block that are
396 * unreachable from just looking at transactions in the mempool (the linking
397 * transactions may also be in the disconnected block, waiting to be added).
398 * Because of this, there's not much benefit in trying to search for in-mempool
399 * children in addUnchecked(). Instead, in the special case of transactions
400 * being added from a disconnected block, we require the caller to clean up the
401 * state, to account for in-mempool, out-of-block descendants for all the
402 * in-block transactions by calling UpdateTransactionsFromBlock(). Note that
403 * until this is called, the mempool state is not consistent, and in particular
404 * mapLinks may not be correct (and therefore functions like
405 * CalculateMemPoolAncestors() and CalculateDescendants() that rely
406 * on them to walk the mempool are not generally safe to use).
408 * Computational limits:
410 * Updating all in-mempool ancestors of a newly added transaction can be slow,
411 * if no bound exists on how many in-mempool ancestors there may be.
412 * CalculateMemPoolAncestors() takes configurable limits that are designed to
413 * prevent these calculations from being too CPU intensive.
419 uint32_t nCheckFrequency
; //!< Value n means that n times in 2^32 we check.
420 unsigned int nTransactionsUpdated
; //!< Used by getblocktemplate to trigger CreateNewBlock() invocation
421 CBlockPolicyEstimator
* minerPolicyEstimator
;
423 uint64_t totalTxSize
; //!< sum of all mempool tx's virtual sizes. Differs from serialized tx size since witness data is discounted. Defined in BIP 141.
424 uint64_t cachedInnerUsage
; //!< sum of dynamic memory usage of all the map elements (NOT the maps themselves)
426 mutable int64_t lastRollingFeeUpdate
;
427 mutable bool blockSinceLastRollingFeeBump
;
428 mutable double rollingMinimumFeeRate
; //!< minimum fee to get into the pool, decreases exponentially
430 void trackPackageRemoved(const CFeeRate
& rate
);
434 static const int ROLLING_FEE_HALFLIFE
= 60 * 60 * 12; // public only for testing
436 typedef boost::multi_index_container
<
438 boost::multi_index::indexed_by
<
440 boost::multi_index::hashed_unique
<mempoolentry_txid
, SaltedTxidHasher
>,
441 // sorted by fee rate
442 boost::multi_index::ordered_non_unique
<
443 boost::multi_index::tag
<descendant_score
>,
444 boost::multi_index::identity
<CTxMemPoolEntry
>,
445 CompareTxMemPoolEntryByDescendantScore
447 // sorted by entry time
448 boost::multi_index::ordered_non_unique
<
449 boost::multi_index::tag
<entry_time
>,
450 boost::multi_index::identity
<CTxMemPoolEntry
>,
451 CompareTxMemPoolEntryByEntryTime
453 // sorted by score (for mining prioritization)
454 boost::multi_index::ordered_unique
<
455 boost::multi_index::tag
<mining_score
>,
456 boost::multi_index::identity
<CTxMemPoolEntry
>,
457 CompareTxMemPoolEntryByScore
459 // sorted by fee rate with ancestors
460 boost::multi_index::ordered_non_unique
<
461 boost::multi_index::tag
<ancestor_score
>,
462 boost::multi_index::identity
<CTxMemPoolEntry
>,
463 CompareTxMemPoolEntryByAncestorFee
466 > indexed_transaction_set
;
468 mutable CCriticalSection cs
;
469 indexed_transaction_set mapTx
;
471 typedef indexed_transaction_set::nth_index
<0>::type::iterator txiter
;
472 std::vector
<std::pair
<uint256
, txiter
> > vTxHashes
; //!< All tx witness hashes/entries in mapTx, in random order
474 struct CompareIteratorByHash
{
475 bool operator()(const txiter
&a
, const txiter
&b
) const {
476 return a
->GetTx().GetHash() < b
->GetTx().GetHash();
479 typedef std::set
<txiter
, CompareIteratorByHash
> setEntries
;
481 const setEntries
& GetMemPoolParents(txiter entry
) const;
482 const setEntries
& GetMemPoolChildren(txiter entry
) const;
484 typedef std::map
<txiter
, setEntries
, CompareIteratorByHash
> cacheMap
;
491 typedef std::map
<txiter
, TxLinks
, CompareIteratorByHash
> txlinksMap
;
494 void UpdateParent(txiter entry
, txiter parent
, bool add
);
495 void UpdateChild(txiter entry
, txiter child
, bool add
);
497 std::vector
<indexed_transaction_set::const_iterator
> GetSortedDepthAndScore() const;
500 indirectmap
<COutPoint
, const CTransaction
*> mapNextTx
;
501 std::map
<uint256
, CAmount
> mapDeltas
;
503 /** Create a new CTxMemPool.
505 CTxMemPool(CBlockPolicyEstimator
* estimator
= nullptr);
508 * If sanity-checking is turned on, check makes sure the pool is
509 * consistent (does not contain two transactions that spend the same inputs,
510 * all inputs are in the mapNextTx array). If sanity-checking is turned off,
511 * check does nothing.
513 void check(const CCoinsViewCache
*pcoins
) const;
514 void setSanityCheck(double dFrequency
= 1.0) { nCheckFrequency
= dFrequency
* 4294967295.0; }
516 // addUnchecked must updated state for all ancestors of a given transaction,
517 // to track size/count of descendant transactions. First version of
518 // addUnchecked can be used to have it call CalculateMemPoolAncestors(), and
519 // then invoke the second version.
520 bool addUnchecked(const uint256
& hash
, const CTxMemPoolEntry
&entry
, bool validFeeEstimate
= true);
521 bool addUnchecked(const uint256
& hash
, const CTxMemPoolEntry
&entry
, setEntries
&setAncestors
, bool validFeeEstimate
= true);
523 void removeRecursive(const CTransaction
&tx
, MemPoolRemovalReason reason
= MemPoolRemovalReason::UNKNOWN
);
524 void removeForReorg(const CCoinsViewCache
*pcoins
, unsigned int nMemPoolHeight
, int flags
);
525 void removeConflicts(const CTransaction
&tx
);
526 void removeForBlock(const std::vector
<CTransactionRef
>& vtx
, unsigned int nBlockHeight
);
529 void _clear(); //lock free
530 bool CompareDepthAndScore(const uint256
& hasha
, const uint256
& hashb
);
531 void queryHashes(std::vector
<uint256
>& vtxid
);
532 bool isSpent(const COutPoint
& outpoint
);
533 unsigned int GetTransactionsUpdated() const;
534 void AddTransactionsUpdated(unsigned int n
);
536 * Check that none of this transactions inputs are in the mempool, and thus
537 * the tx is not dependent on other mempool transactions to be included in a block.
539 bool HasNoInputsOf(const CTransaction
& tx
) const;
541 /** Affect CreateNewBlock prioritisation of transactions */
542 void PrioritiseTransaction(const uint256
& hash
, const CAmount
& nFeeDelta
);
543 void ApplyDelta(const uint256 hash
, CAmount
&nFeeDelta
) const;
544 void ClearPrioritisation(const uint256 hash
);
547 /** Remove a set of transactions from the mempool.
548 * If a transaction is in this set, then all in-mempool descendants must
549 * also be in the set, unless this transaction is being removed for being
551 * Set updateDescendants to true when removing a tx that was in a block, so
552 * that any in-mempool descendants have their ancestor state updated.
554 void RemoveStaged(setEntries
&stage
, bool updateDescendants
, MemPoolRemovalReason reason
= MemPoolRemovalReason::UNKNOWN
);
556 /** When adding transactions from a disconnected block back to the mempool,
557 * new mempool entries may have children in the mempool (which is generally
558 * not the case when otherwise adding transactions).
559 * UpdateTransactionsFromBlock() will find child transactions and update the
560 * descendant state for each transaction in vHashesToUpdate (excluding any
561 * child transactions present in vHashesToUpdate, which are already accounted
562 * for). Note: vHashesToUpdate should be the set of transactions from the
563 * disconnected block that have been accepted back into the mempool.
565 void UpdateTransactionsFromBlock(const std::vector
<uint256
> &vHashesToUpdate
);
567 /** Try to calculate all in-mempool ancestors of entry.
568 * (these are all calculated including the tx itself)
569 * limitAncestorCount = max number of ancestors
570 * limitAncestorSize = max size of ancestors
571 * limitDescendantCount = max number of descendants any ancestor can have
572 * limitDescendantSize = max size of descendants any ancestor can have
573 * errString = populated with error reason if any limits are hit
574 * fSearchForParents = whether to search a tx's vin for in-mempool parents, or
575 * look up parents from mapLinks. Must be true for entries not in the mempool
577 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;
579 /** Populate setDescendants with all in-mempool descendants of hash.
580 * Assumes that setDescendants includes all in-mempool descendants of anything
582 void CalculateDescendants(txiter it
, setEntries
&setDescendants
);
584 /** The minimum fee to get into the mempool, which may itself not be enough
585 * for larger-sized transactions.
586 * The incrementalRelayFee policy variable is used to bound the time it
587 * takes the fee rate to go back down all the way to 0. When the feerate
588 * would otherwise be half of this, it is set to 0 instead.
590 CFeeRate
GetMinFee(size_t sizelimit
) const;
592 /** Remove transactions from the mempool until its dynamic size is <= sizelimit.
593 * pvNoSpendsRemaining, if set, will be populated with the list of outpoints
594 * which are not in mempool which no longer have any spends in this mempool.
596 void TrimToSize(size_t sizelimit
, std::vector
<COutPoint
>* pvNoSpendsRemaining
=NULL
);
598 /** Expire all transaction (and their dependencies) in the mempool older than time. Return the number of removed transactions. */
599 int Expire(int64_t time
);
601 /** Returns false if the transaction is in the mempool and not within the chain limit specified. */
602 bool TransactionWithinChainLimit(const uint256
& txid
, size_t chainLimit
) const;
610 uint64_t GetTotalTxSize()
616 bool exists(uint256 hash
) const
619 return (mapTx
.count(hash
) != 0);
622 bool exists(const COutPoint
& outpoint
) const
625 auto it
= mapTx
.find(outpoint
.hash
);
626 return (it
!= mapTx
.end() && outpoint
.n
< it
->GetTx().vout
.size());
629 CTransactionRef
get(const uint256
& hash
) const;
630 TxMempoolInfo
info(const uint256
& hash
) const;
631 std::vector
<TxMempoolInfo
> infoAll() const;
633 size_t DynamicMemoryUsage() const;
635 boost::signals2::signal
<void (CTransactionRef
)> NotifyEntryAdded
;
636 boost::signals2::signal
<void (CTransactionRef
, MemPoolRemovalReason
)> NotifyEntryRemoved
;
639 /** UpdateForDescendants is used by UpdateTransactionsFromBlock to update
640 * the descendants for a single transaction that has been added to the
641 * mempool but may have child transactions in the mempool, eg during a
642 * chain reorg. setExclude is the set of descendant transactions in the
643 * mempool that must not be accounted for (because any descendants in
644 * setExclude were added to the mempool after the transaction being
645 * updated and hence their state is already reflected in the parent
648 * cachedDescendants will be updated with the descendants of the transaction
649 * being updated, so that future invocations don't need to walk the
650 * same transaction again, if encountered in another transaction chain.
652 void UpdateForDescendants(txiter updateIt
,
653 cacheMap
&cachedDescendants
,
654 const std::set
<uint256
> &setExclude
);
655 /** Update ancestors of hash to add/remove it as a descendant transaction. */
656 void UpdateAncestorsOf(bool add
, txiter hash
, setEntries
&setAncestors
);
657 /** Set ancestor state for an entry */
658 void UpdateEntryForAncestors(txiter it
, const setEntries
&setAncestors
);
659 /** For each transaction being removed, update ancestors and any direct children.
660 * If updateDescendants is true, then also update in-mempool descendants'
662 void UpdateForRemoveFromMempool(const setEntries
&entriesToRemove
, bool updateDescendants
);
663 /** Sever link between specified transaction and direct children. */
664 void UpdateChildrenForRemoval(txiter entry
);
666 /** Before calling removeUnchecked for a given transaction,
667 * UpdateForRemoveFromMempool must be called on the entire (dependent) set
668 * of transactions being removed at the same time. We use each
669 * CTxMemPoolEntry's setMemPoolParents in order to walk ancestors of a
670 * given transaction that is removed, so we can't remove intermediate
671 * transactions in a chain before we've updated all the state for the
674 void removeUnchecked(txiter entry
, MemPoolRemovalReason reason
= MemPoolRemovalReason::UNKNOWN
);
678 * CCoinsView that brings transactions from a memorypool into view.
679 * It does not check for spendings by memory pool transactions.
681 class CCoinsViewMemPool
: public CCoinsViewBacked
684 const CTxMemPool
& mempool
;
687 CCoinsViewMemPool(CCoinsView
* baseIn
, const CTxMemPool
& mempoolIn
);
688 bool GetCoin(const COutPoint
&outpoint
, Coin
&coin
) const;
689 bool HaveCoin(const COutPoint
&outpoint
) const;
693 * DisconnectedBlockTransactions
695 * During the reorg, it's desirable to re-add previously confirmed transactions
696 * to the mempool, so that anything not re-confirmed in the new chain is
697 * available to be mined. However, it's more efficient to wait until the reorg
698 * is complete and process all still-unconfirmed transactions at that time,
699 * since we expect most confirmed transactions to (typically) still be
700 * confirmed in the new chain, and re-accepting to the memory pool is expensive
701 * (and therefore better to not do in the middle of reorg-processing).
702 * Instead, store the disconnected transactions (in order!) as we go, remove any
703 * that are included in blocks in the new chain, and then process the remaining
704 * still-unconfirmed transactions at the end.
707 // multi_index tag names
708 struct txid_index
{};
709 struct insertion_order
{};
711 struct DisconnectedBlockTransactions
{
712 typedef boost::multi_index_container
<
714 boost::multi_index::indexed_by
<
716 boost::multi_index::hashed_unique
<
717 boost::multi_index::tag
<txid_index
>,
721 // sorted by order in the blockchain
722 boost::multi_index::sequenced
<
723 boost::multi_index::tag
<insertion_order
>
726 > indexed_disconnected_transactions
;
728 // It's almost certainly a logic bug if we don't clear out queuedTx before
729 // destruction, as we add to it while disconnecting blocks, and then we
730 // need to re-process remaining transactions to ensure mempool consistency.
731 // For now, assert() that we've emptied out this object on destruction.
732 // This assert() can always be removed if the reorg-processing code were
733 // to be refactored such that this assumption is no longer true (for
734 // instance if there was some other way we cleaned up the mempool after a
735 // reorg, besides draining this object).
736 ~DisconnectedBlockTransactions() { assert(queuedTx
.empty()); }
738 indexed_disconnected_transactions queuedTx
;
739 uint64_t cachedInnerUsage
= 0;
741 // Estimate the overhead of queuedTx to be 6 pointers + an allocation, as
742 // no exact formula for boost::multi_index_contained is implemented.
743 size_t DynamicMemoryUsage() const {
744 return memusage::MallocUsage(sizeof(CTransactionRef
) + 6 * sizeof(void*)) * queuedTx
.size() + cachedInnerUsage
;
747 void addTransaction(const CTransactionRef
& tx
)
750 cachedInnerUsage
+= RecursiveDynamicUsage(tx
);
753 // Remove entries based on txid_index, and update memory usage.
754 void removeForBlock(const std::vector
<CTransactionRef
>& vtx
)
756 // Short-circuit in the common case of a block being added to the tip
757 if (queuedTx
.empty()) {
760 for (auto const &tx
: vtx
) {
761 auto it
= queuedTx
.find(tx
->GetHash());
762 if (it
!= queuedTx
.end()) {
763 cachedInnerUsage
-= RecursiveDynamicUsage(*it
);
769 // Remove an entry by insertion_order index, and update memory usage.
770 void removeEntry(indexed_disconnected_transactions::index
<insertion_order
>::type::iterator entry
)
772 cachedInnerUsage
-= RecursiveDynamicUsage(*entry
);
773 queuedTx
.get
<insertion_order
>().erase(entry
);
778 cachedInnerUsage
= 0;
783 #endif // BITCOIN_TXMEMPOOL_H