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>
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;
38 // Will be set to the blockchain height and median time past
39 // values that would be necessary to satisfy all relative locktime
40 // constraints (BIP68) of this tx given our view of block chain history
43 // As long as the current chain descends from the highest height block
44 // containing one of the inputs used in the calculation, then the cached
45 // values are still valid even after a reorg.
46 CBlockIndex
* maxInputBlock
;
48 LockPoints() : height(0), time(0), maxInputBlock(nullptr) { }
53 /** \class CTxMemPoolEntry
55 * CTxMemPoolEntry stores data about the corresponding transaction, as well
56 * as data about all in-mempool transactions that depend on the transaction
57 * ("descendant" transactions).
59 * When a new entry is added to the mempool, we update the descendant state
60 * (nCountWithDescendants, nSizeWithDescendants, and nModFeesWithDescendants) for
61 * all ancestors of the newly added transaction.
69 CAmount nFee
; //!< Cached to avoid expensive parent-transaction lookups
70 size_t nTxWeight
; //!< ... and avoid recomputing tx weight (also used for GetTxSize())
71 size_t nUsageSize
; //!< ... and total memory usage
72 int64_t nTime
; //!< Local time when entering the mempool
73 unsigned int entryHeight
; //!< Chain height when entering the mempool
74 bool spendsCoinbase
; //!< keep track of transactions that spend a coinbase
75 int64_t sigOpCost
; //!< Total sigop cost
76 int64_t feeDelta
; //!< Used for determining the priority of the transaction for mining in a block
77 LockPoints lockPoints
; //!< Track the height and time at which tx was final
79 // Information about descendants of this transaction that are in the
80 // mempool; if we remove this transaction we must remove all of these
81 // descendants as well.
82 uint64_t nCountWithDescendants
; //!< number of descendant transactions
83 uint64_t nSizeWithDescendants
; //!< ... and size
84 CAmount nModFeesWithDescendants
; //!< ... and total fees (all including us)
86 // Analogous statistics for ancestor transactions
87 uint64_t nCountWithAncestors
;
88 uint64_t nSizeWithAncestors
;
89 CAmount nModFeesWithAncestors
;
90 int64_t nSigOpCostWithAncestors
;
93 CTxMemPoolEntry(const CTransactionRef
& _tx
, const CAmount
& _nFee
,
94 int64_t _nTime
, unsigned int _entryHeight
,
96 int64_t nSigOpsCost
, LockPoints lp
);
98 const CTransaction
& GetTx() const { return *this->tx
; }
99 CTransactionRef
GetSharedTx() const { return this->tx
; }
100 const CAmount
& GetFee() const { return nFee
; }
101 size_t GetTxSize() const;
102 size_t GetTxWeight() const { return nTxWeight
; }
103 int64_t GetTime() const { return nTime
; }
104 unsigned int GetHeight() const { return entryHeight
; }
105 int64_t GetSigOpCost() const { return sigOpCost
; }
106 int64_t GetModifiedFee() const { return nFee
+ feeDelta
; }
107 size_t DynamicMemoryUsage() const { return nUsageSize
; }
108 const LockPoints
& GetLockPoints() const { return lockPoints
; }
110 // Adjusts the descendant state.
111 void UpdateDescendantState(int64_t modifySize
, CAmount modifyFee
, int64_t modifyCount
);
112 // Adjusts the ancestor state
113 void UpdateAncestorState(int64_t modifySize
, CAmount modifyFee
, int64_t modifyCount
, int modifySigOps
);
114 // Updates the fee delta used for mining priority score, and the
115 // modified fees with descendants.
116 void UpdateFeeDelta(int64_t feeDelta
);
117 // Update the LockPoints after a reorg
118 void UpdateLockPoints(const LockPoints
& lp
);
120 uint64_t GetCountWithDescendants() const { return nCountWithDescendants
; }
121 uint64_t GetSizeWithDescendants() const { return nSizeWithDescendants
; }
122 CAmount
GetModFeesWithDescendants() const { return nModFeesWithDescendants
; }
124 bool GetSpendsCoinbase() const { return spendsCoinbase
; }
126 uint64_t GetCountWithAncestors() const { return nCountWithAncestors
; }
127 uint64_t GetSizeWithAncestors() const { return nSizeWithAncestors
; }
128 CAmount
GetModFeesWithAncestors() const { return nModFeesWithAncestors
; }
129 int64_t GetSigOpCostWithAncestors() const { return nSigOpCostWithAncestors
; }
131 mutable size_t vTxHashesIdx
; //!< Index in mempool's vTxHashes
134 // Helpers for modifying CTxMemPool::mapTx, which is a boost multi_index.
135 struct update_descendant_state
137 update_descendant_state(int64_t _modifySize
, CAmount _modifyFee
, int64_t _modifyCount
) :
138 modifySize(_modifySize
), modifyFee(_modifyFee
), modifyCount(_modifyCount
)
141 void operator() (CTxMemPoolEntry
&e
)
142 { e
.UpdateDescendantState(modifySize
, modifyFee
, modifyCount
); }
150 struct update_ancestor_state
152 update_ancestor_state(int64_t _modifySize
, CAmount _modifyFee
, int64_t _modifyCount
, int64_t _modifySigOpsCost
) :
153 modifySize(_modifySize
), modifyFee(_modifyFee
), modifyCount(_modifyCount
), modifySigOpsCost(_modifySigOpsCost
)
156 void operator() (CTxMemPoolEntry
&e
)
157 { e
.UpdateAncestorState(modifySize
, modifyFee
, modifyCount
, modifySigOpsCost
); }
163 int64_t modifySigOpsCost
;
166 struct update_fee_delta
168 explicit update_fee_delta(int64_t _feeDelta
) : feeDelta(_feeDelta
) { }
170 void operator() (CTxMemPoolEntry
&e
) { e
.UpdateFeeDelta(feeDelta
); }
176 struct update_lock_points
178 explicit update_lock_points(const LockPoints
& _lp
) : lp(_lp
) { }
180 void operator() (CTxMemPoolEntry
&e
) { e
.UpdateLockPoints(lp
); }
183 const LockPoints
& lp
;
186 // extracts a transaction hash from CTxMempoolEntry or CTransactionRef
187 struct mempoolentry_txid
189 typedef uint256 result_type
;
190 result_type
operator() (const CTxMemPoolEntry
&entry
) const
192 return entry
.GetTx().GetHash();
195 result_type
operator() (const CTransactionRef
& tx
) const
197 return tx
->GetHash();
201 /** \class CompareTxMemPoolEntryByDescendantScore
203 * Sort an entry by max(score/size of entry's tx, score/size with all descendants).
205 class CompareTxMemPoolEntryByDescendantScore
208 bool operator()(const CTxMemPoolEntry
& a
, const CTxMemPoolEntry
& b
)
210 bool fUseADescendants
= UseDescendantScore(a
);
211 bool fUseBDescendants
= UseDescendantScore(b
);
213 double aModFee
= fUseADescendants
? a
.GetModFeesWithDescendants() : a
.GetModifiedFee();
214 double aSize
= fUseADescendants
? a
.GetSizeWithDescendants() : a
.GetTxSize();
216 double bModFee
= fUseBDescendants
? b
.GetModFeesWithDescendants() : b
.GetModifiedFee();
217 double bSize
= fUseBDescendants
? b
.GetSizeWithDescendants() : b
.GetTxSize();
219 // Avoid division by rewriting (a/b > c/d) as (a*d > c*b).
220 double f1
= aModFee
* bSize
;
221 double f2
= aSize
* bModFee
;
224 return a
.GetTime() >= b
.GetTime();
229 // Calculate which score to use for an entry (avoiding division).
230 bool UseDescendantScore(const CTxMemPoolEntry
&a
)
232 double f1
= (double)a
.GetModifiedFee() * a
.GetSizeWithDescendants();
233 double f2
= (double)a
.GetModFeesWithDescendants() * a
.GetTxSize();
238 /** \class CompareTxMemPoolEntryByScore
240 * Sort by score of entry ((fee+delta)/size) in descending order
242 class CompareTxMemPoolEntryByScore
245 bool operator()(const CTxMemPoolEntry
& a
, const CTxMemPoolEntry
& b
)
247 double f1
= (double)a
.GetModifiedFee() * b
.GetTxSize();
248 double f2
= (double)b
.GetModifiedFee() * a
.GetTxSize();
250 return b
.GetTx().GetHash() < a
.GetTx().GetHash();
256 class CompareTxMemPoolEntryByEntryTime
259 bool operator()(const CTxMemPoolEntry
& a
, const CTxMemPoolEntry
& b
)
261 return a
.GetTime() < b
.GetTime();
265 class CompareTxMemPoolEntryByAncestorFee
268 bool operator()(const CTxMemPoolEntry
& a
, const CTxMemPoolEntry
& b
)
270 double aFees
= a
.GetModFeesWithAncestors();
271 double aSize
= a
.GetSizeWithAncestors();
273 double bFees
= b
.GetModFeesWithAncestors();
274 double bSize
= b
.GetSizeWithAncestors();
276 // Avoid division by rewriting (a/b > c/d) as (a*d > c*b).
277 double f1
= aFees
* bSize
;
278 double f2
= aSize
* bFees
;
281 return a
.GetTx().GetHash() < b
.GetTx().GetHash();
288 // Multi_index tag names
289 struct descendant_score
{};
290 struct entry_time
{};
291 struct mining_score
{};
292 struct ancestor_score
{};
294 class CBlockPolicyEstimator
;
297 * Information about a mempool transaction.
301 /** The transaction itself */
304 /** Time the transaction entered the mempool. */
307 /** Feerate of the transaction. */
310 /** The fee delta. */
314 /** Reason why a transaction was removed from the mempool,
315 * this is passed to the notification signal.
317 enum class MemPoolRemovalReason
{
318 UNKNOWN
= 0, //! Manually removed or unknown reason
319 EXPIRY
, //! Expired from mempool
320 SIZELIMIT
, //! Removed in size limiting
321 REORG
, //! Removed for reorganization
322 BLOCK
, //! Removed for block
323 CONFLICT
, //! Removed for conflict with in-block transaction
324 REPLACED
//! Removed for replacement
327 class SaltedTxidHasher
331 const uint64_t k0
, k1
;
336 size_t operator()(const uint256
& txid
) const {
337 return SipHashUint256(k0
, k1
, txid
);
342 * CTxMemPool stores valid-according-to-the-current-best-chain transactions
343 * that may be included in the next block.
345 * Transactions are added when they are seen on the network (or created by the
346 * local node), but not all transactions seen are added to the pool. For
347 * example, the following new transactions will not be added to the mempool:
348 * - a transaction which doesn't meet the minimum fee requirements.
349 * - a new transaction that double-spends an input of a transaction already in
350 * the pool where the new transaction does not meet the Replace-By-Fee
351 * requirements as defined in BIP 125.
352 * - a non-standard transaction.
354 * CTxMemPool::mapTx, and CTxMemPoolEntry bookkeeping:
356 * mapTx is a boost::multi_index that sorts the mempool on 4 criteria:
358 * - feerate [we use max(feerate of tx, feerate of tx with all descendants)]
360 * - mining score (feerate modified by any fee deltas from PrioritiseTransaction)
362 * Note: the term "descendant" refers to in-mempool transactions that depend on
363 * this one, while "ancestor" refers to in-mempool transactions that a given
364 * transaction depends on.
366 * In order for the feerate sort to remain correct, we must update transactions
367 * in the mempool when new descendants arrive. To facilitate this, we track
368 * the set of in-mempool direct parents and direct children in mapLinks. Within
369 * each CTxMemPoolEntry, we track the size and fees of all descendants.
371 * Usually when a new transaction is added to the mempool, it has no in-mempool
372 * children (because any such children would be an orphan). So in
373 * addUnchecked(), we:
374 * - update a new entry's setMemPoolParents to include all in-mempool parents
375 * - update the new entry's direct parents to include the new tx as a child
376 * - update all ancestors of the transaction to include the new tx's size/fee
378 * When a transaction is removed from the mempool, we must:
379 * - update all in-mempool parents to not track the tx in setMemPoolChildren
380 * - update all ancestors to not include the tx's size/fees in descendant state
381 * - update all in-mempool children to not include it as a parent
383 * These happen in UpdateForRemoveFromMempool(). (Note that when removing a
384 * transaction along with its descendants, we must calculate that set of
385 * transactions to be removed before doing the removal, or else the mempool can
386 * be in an inconsistent state where it's impossible to walk the ancestors of
389 * In the event of a reorg, the assumption that a newly added tx has no
390 * in-mempool children is false. In particular, the mempool is in an
391 * inconsistent state while new transactions are being added, because there may
392 * be descendant transactions of a tx coming from a disconnected block that are
393 * unreachable from just looking at transactions in the mempool (the linking
394 * transactions may also be in the disconnected block, waiting to be added).
395 * Because of this, there's not much benefit in trying to search for in-mempool
396 * children in addUnchecked(). Instead, in the special case of transactions
397 * being added from a disconnected block, we require the caller to clean up the
398 * state, to account for in-mempool, out-of-block descendants for all the
399 * in-block transactions by calling UpdateTransactionsFromBlock(). Note that
400 * until this is called, the mempool state is not consistent, and in particular
401 * mapLinks may not be correct (and therefore functions like
402 * CalculateMemPoolAncestors() and CalculateDescendants() that rely
403 * on them to walk the mempool are not generally safe to use).
405 * Computational limits:
407 * Updating all in-mempool ancestors of a newly added transaction can be slow,
408 * if no bound exists on how many in-mempool ancestors there may be.
409 * CalculateMemPoolAncestors() takes configurable limits that are designed to
410 * prevent these calculations from being too CPU intensive.
416 uint32_t nCheckFrequency
; //!< Value n means that n times in 2^32 we check.
417 unsigned int nTransactionsUpdated
; //!< Used by getblocktemplate to trigger CreateNewBlock() invocation
418 CBlockPolicyEstimator
* minerPolicyEstimator
;
420 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.
421 uint64_t cachedInnerUsage
; //!< sum of dynamic memory usage of all the map elements (NOT the maps themselves)
423 mutable int64_t lastRollingFeeUpdate
;
424 mutable bool blockSinceLastRollingFeeBump
;
425 mutable double rollingMinimumFeeRate
; //!< minimum fee to get into the pool, decreases exponentially
427 void trackPackageRemoved(const CFeeRate
& rate
);
431 static const int ROLLING_FEE_HALFLIFE
= 60 * 60 * 12; // public only for testing
433 typedef boost::multi_index_container
<
435 boost::multi_index::indexed_by
<
437 boost::multi_index::hashed_unique
<mempoolentry_txid
, SaltedTxidHasher
>,
438 // sorted by fee rate
439 boost::multi_index::ordered_non_unique
<
440 boost::multi_index::tag
<descendant_score
>,
441 boost::multi_index::identity
<CTxMemPoolEntry
>,
442 CompareTxMemPoolEntryByDescendantScore
444 // sorted by entry time
445 boost::multi_index::ordered_non_unique
<
446 boost::multi_index::tag
<entry_time
>,
447 boost::multi_index::identity
<CTxMemPoolEntry
>,
448 CompareTxMemPoolEntryByEntryTime
450 // sorted by score (for mining prioritization)
451 boost::multi_index::ordered_unique
<
452 boost::multi_index::tag
<mining_score
>,
453 boost::multi_index::identity
<CTxMemPoolEntry
>,
454 CompareTxMemPoolEntryByScore
456 // sorted by fee rate with ancestors
457 boost::multi_index::ordered_non_unique
<
458 boost::multi_index::tag
<ancestor_score
>,
459 boost::multi_index::identity
<CTxMemPoolEntry
>,
460 CompareTxMemPoolEntryByAncestorFee
463 > indexed_transaction_set
;
465 mutable CCriticalSection cs
;
466 indexed_transaction_set mapTx
;
468 typedef indexed_transaction_set::nth_index
<0>::type::iterator txiter
;
469 std::vector
<std::pair
<uint256
, txiter
> > vTxHashes
; //!< All tx witness hashes/entries in mapTx, in random order
471 struct CompareIteratorByHash
{
472 bool operator()(const txiter
&a
, const txiter
&b
) const {
473 return a
->GetTx().GetHash() < b
->GetTx().GetHash();
476 typedef std::set
<txiter
, CompareIteratorByHash
> setEntries
;
478 const setEntries
& GetMemPoolParents(txiter entry
) const;
479 const setEntries
& GetMemPoolChildren(txiter entry
) const;
481 typedef std::map
<txiter
, setEntries
, CompareIteratorByHash
> cacheMap
;
488 typedef std::map
<txiter
, TxLinks
, CompareIteratorByHash
> txlinksMap
;
491 void UpdateParent(txiter entry
, txiter parent
, bool add
);
492 void UpdateChild(txiter entry
, txiter child
, bool add
);
494 std::vector
<indexed_transaction_set::const_iterator
> GetSortedDepthAndScore() const;
497 indirectmap
<COutPoint
, const CTransaction
*> mapNextTx
;
498 std::map
<uint256
, CAmount
> mapDeltas
;
500 /** Create a new CTxMemPool.
502 explicit CTxMemPool(CBlockPolicyEstimator
* estimator
= nullptr);
505 * If sanity-checking is turned on, check makes sure the pool is
506 * consistent (does not contain two transactions that spend the same inputs,
507 * all inputs are in the mapNextTx array). If sanity-checking is turned off,
508 * check does nothing.
510 void check(const CCoinsViewCache
*pcoins
) const;
511 void setSanityCheck(double dFrequency
= 1.0) { nCheckFrequency
= dFrequency
* 4294967295.0; }
513 // addUnchecked must updated state for all ancestors of a given transaction,
514 // to track size/count of descendant transactions. First version of
515 // addUnchecked can be used to have it call CalculateMemPoolAncestors(), and
516 // then invoke the second version.
517 bool addUnchecked(const uint256
& hash
, const CTxMemPoolEntry
&entry
, bool validFeeEstimate
= true);
518 bool addUnchecked(const uint256
& hash
, const CTxMemPoolEntry
&entry
, setEntries
&setAncestors
, bool validFeeEstimate
= true);
520 void removeRecursive(const CTransaction
&tx
, MemPoolRemovalReason reason
= MemPoolRemovalReason::UNKNOWN
);
521 void removeForReorg(const CCoinsViewCache
*pcoins
, unsigned int nMemPoolHeight
, int flags
);
522 void removeConflicts(const CTransaction
&tx
);
523 void removeForBlock(const std::vector
<CTransactionRef
>& vtx
, unsigned int nBlockHeight
);
526 void _clear(); //lock free
527 bool CompareDepthAndScore(const uint256
& hasha
, const uint256
& hashb
);
528 void queryHashes(std::vector
<uint256
>& vtxid
);
529 bool isSpent(const COutPoint
& outpoint
);
530 unsigned int GetTransactionsUpdated() const;
531 void AddTransactionsUpdated(unsigned int n
);
533 * Check that none of this transactions inputs are in the mempool, and thus
534 * the tx is not dependent on other mempool transactions to be included in a block.
536 bool HasNoInputsOf(const CTransaction
& tx
) const;
538 /** Affect CreateNewBlock prioritisation of transactions */
539 void PrioritiseTransaction(const uint256
& hash
, const CAmount
& nFeeDelta
);
540 void ApplyDelta(const uint256 hash
, CAmount
&nFeeDelta
) const;
541 void ClearPrioritisation(const uint256 hash
);
544 /** Remove a set of transactions from the mempool.
545 * If a transaction is in this set, then all in-mempool descendants must
546 * also be in the set, unless this transaction is being removed for being
548 * Set updateDescendants to true when removing a tx that was in a block, so
549 * that any in-mempool descendants have their ancestor state updated.
551 void RemoveStaged(setEntries
&stage
, bool updateDescendants
, MemPoolRemovalReason reason
= MemPoolRemovalReason::UNKNOWN
);
553 /** When adding transactions from a disconnected block back to the mempool,
554 * new mempool entries may have children in the mempool (which is generally
555 * not the case when otherwise adding transactions).
556 * UpdateTransactionsFromBlock() will find child transactions and update the
557 * descendant state for each transaction in vHashesToUpdate (excluding any
558 * child transactions present in vHashesToUpdate, which are already accounted
559 * for). Note: vHashesToUpdate should be the set of transactions from the
560 * disconnected block that have been accepted back into the mempool.
562 void UpdateTransactionsFromBlock(const std::vector
<uint256
> &vHashesToUpdate
);
564 /** Try to calculate all in-mempool ancestors of entry.
565 * (these are all calculated including the tx itself)
566 * limitAncestorCount = max number of ancestors
567 * limitAncestorSize = max size of ancestors
568 * limitDescendantCount = max number of descendants any ancestor can have
569 * limitDescendantSize = max size of descendants any ancestor can have
570 * errString = populated with error reason if any limits are hit
571 * fSearchForParents = whether to search a tx's vin for in-mempool parents, or
572 * look up parents from mapLinks. Must be true for entries not in the mempool
574 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;
576 /** Populate setDescendants with all in-mempool descendants of hash.
577 * Assumes that setDescendants includes all in-mempool descendants of anything
579 void CalculateDescendants(txiter it
, setEntries
&setDescendants
);
581 /** The minimum fee to get into the mempool, which may itself not be enough
582 * for larger-sized transactions.
583 * The incrementalRelayFee policy variable is used to bound the time it
584 * takes the fee rate to go back down all the way to 0. When the feerate
585 * would otherwise be half of this, it is set to 0 instead.
587 CFeeRate
GetMinFee(size_t sizelimit
) const;
589 /** Remove transactions from the mempool until its dynamic size is <= sizelimit.
590 * pvNoSpendsRemaining, if set, will be populated with the list of outpoints
591 * which are not in mempool which no longer have any spends in this mempool.
593 void TrimToSize(size_t sizelimit
, std::vector
<COutPoint
>* pvNoSpendsRemaining
=nullptr);
595 /** Expire all transaction (and their dependencies) in the mempool older than time. Return the number of removed transactions. */
596 int Expire(int64_t time
);
598 /** Returns false if the transaction is in the mempool and not within the chain limit specified. */
599 bool TransactionWithinChainLimit(const uint256
& txid
, size_t chainLimit
) const;
607 uint64_t GetTotalTxSize() const
613 bool exists(uint256 hash
) const
616 return (mapTx
.count(hash
) != 0);
619 CTransactionRef
get(const uint256
& hash
) const;
620 TxMempoolInfo
info(const uint256
& hash
) const;
621 std::vector
<TxMempoolInfo
> infoAll() const;
623 size_t DynamicMemoryUsage() const;
625 boost::signals2::signal
<void (CTransactionRef
)> NotifyEntryAdded
;
626 boost::signals2::signal
<void (CTransactionRef
, MemPoolRemovalReason
)> NotifyEntryRemoved
;
629 /** UpdateForDescendants is used by UpdateTransactionsFromBlock to update
630 * the descendants for a single transaction that has been added to the
631 * mempool but may have child transactions in the mempool, eg during a
632 * chain reorg. setExclude is the set of descendant transactions in the
633 * mempool that must not be accounted for (because any descendants in
634 * setExclude were added to the mempool after the transaction being
635 * updated and hence their state is already reflected in the parent
638 * cachedDescendants will be updated with the descendants of the transaction
639 * being updated, so that future invocations don't need to walk the
640 * same transaction again, if encountered in another transaction chain.
642 void UpdateForDescendants(txiter updateIt
,
643 cacheMap
&cachedDescendants
,
644 const std::set
<uint256
> &setExclude
);
645 /** Update ancestors of hash to add/remove it as a descendant transaction. */
646 void UpdateAncestorsOf(bool add
, txiter hash
, setEntries
&setAncestors
);
647 /** Set ancestor state for an entry */
648 void UpdateEntryForAncestors(txiter it
, const setEntries
&setAncestors
);
649 /** For each transaction being removed, update ancestors and any direct children.
650 * If updateDescendants is true, then also update in-mempool descendants'
652 void UpdateForRemoveFromMempool(const setEntries
&entriesToRemove
, bool updateDescendants
);
653 /** Sever link between specified transaction and direct children. */
654 void UpdateChildrenForRemoval(txiter entry
);
656 /** Before calling removeUnchecked for a given transaction,
657 * UpdateForRemoveFromMempool must be called on the entire (dependent) set
658 * of transactions being removed at the same time. We use each
659 * CTxMemPoolEntry's setMemPoolParents in order to walk ancestors of a
660 * given transaction that is removed, so we can't remove intermediate
661 * transactions in a chain before we've updated all the state for the
664 void removeUnchecked(txiter entry
, MemPoolRemovalReason reason
= MemPoolRemovalReason::UNKNOWN
);
668 * CCoinsView that brings transactions from a memorypool into view.
669 * It does not check for spendings by memory pool transactions.
670 * Instead, it provides access to all Coins which are either unspent in the
671 * base CCoinsView, or are outputs from any mempool transaction!
672 * This allows transaction replacement to work as expected, as you want to
673 * have all inputs "available" to check signatures, and any cycles in the
674 * dependency graph are checked directly in AcceptToMemoryPool.
675 * It also allows you to sign a double-spend directly in signrawtransaction,
676 * as long as the conflicting transaction is not yet confirmed.
678 class CCoinsViewMemPool
: public CCoinsViewBacked
681 const CTxMemPool
& mempool
;
684 CCoinsViewMemPool(CCoinsView
* baseIn
, const CTxMemPool
& mempoolIn
);
685 bool GetCoin(const COutPoint
&outpoint
, Coin
&coin
) const override
;
689 * DisconnectedBlockTransactions
691 * During the reorg, it's desirable to re-add previously confirmed transactions
692 * to the mempool, so that anything not re-confirmed in the new chain is
693 * available to be mined. However, it's more efficient to wait until the reorg
694 * is complete and process all still-unconfirmed transactions at that time,
695 * since we expect most confirmed transactions to (typically) still be
696 * confirmed in the new chain, and re-accepting to the memory pool is expensive
697 * (and therefore better to not do in the middle of reorg-processing).
698 * Instead, store the disconnected transactions (in order!) as we go, remove any
699 * that are included in blocks in the new chain, and then process the remaining
700 * still-unconfirmed transactions at the end.
703 // multi_index tag names
704 struct txid_index
{};
705 struct insertion_order
{};
707 struct DisconnectedBlockTransactions
{
708 typedef boost::multi_index_container
<
710 boost::multi_index::indexed_by
<
712 boost::multi_index::hashed_unique
<
713 boost::multi_index::tag
<txid_index
>,
717 // sorted by order in the blockchain
718 boost::multi_index::sequenced
<
719 boost::multi_index::tag
<insertion_order
>
722 > indexed_disconnected_transactions
;
724 // It's almost certainly a logic bug if we don't clear out queuedTx before
725 // destruction, as we add to it while disconnecting blocks, and then we
726 // need to re-process remaining transactions to ensure mempool consistency.
727 // For now, assert() that we've emptied out this object on destruction.
728 // This assert() can always be removed if the reorg-processing code were
729 // to be refactored such that this assumption is no longer true (for
730 // instance if there was some other way we cleaned up the mempool after a
731 // reorg, besides draining this object).
732 ~DisconnectedBlockTransactions() { assert(queuedTx
.empty()); }
734 indexed_disconnected_transactions queuedTx
;
735 uint64_t cachedInnerUsage
= 0;
737 // Estimate the overhead of queuedTx to be 6 pointers + an allocation, as
738 // no exact formula for boost::multi_index_contained is implemented.
739 size_t DynamicMemoryUsage() const {
740 return memusage::MallocUsage(sizeof(CTransactionRef
) + 6 * sizeof(void*)) * queuedTx
.size() + cachedInnerUsage
;
743 void addTransaction(const CTransactionRef
& tx
)
746 cachedInnerUsage
+= RecursiveDynamicUsage(tx
);
749 // Remove entries based on txid_index, and update memory usage.
750 void removeForBlock(const std::vector
<CTransactionRef
>& vtx
)
752 // Short-circuit in the common case of a block being added to the tip
753 if (queuedTx
.empty()) {
756 for (auto const &tx
: vtx
) {
757 auto it
= queuedTx
.find(tx
->GetHash());
758 if (it
!= queuedTx
.end()) {
759 cachedInnerUsage
-= RecursiveDynamicUsage(*it
);
765 // Remove an entry by insertion_order index, and update memory usage.
766 void removeEntry(indexed_disconnected_transactions::index
<insertion_order
>::type::iterator entry
)
768 cachedInnerUsage
-= RecursiveDynamicUsage(*entry
);
769 queuedTx
.get
<insertion_order
>().erase(entry
);
774 cachedInnerUsage
= 0;
779 #endif // BITCOIN_TXMEMPOOL_H