1 // Copyright (c) 2009-2010 Satoshi Nakamoto
2 // Copyright (c) 2009-2014 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
14 #include "primitives/transaction.h"
18 #include "boost/multi_index_container.hpp"
19 #include "boost/multi_index/ordered_index.hpp"
23 inline double AllowFreeThreshold()
25 return COIN
* 144 / 250;
28 inline bool AllowFree(double dPriority
)
30 // Large (in bytes) low-priority (new, small-coin) transactions
32 return dPriority
> AllowFreeThreshold();
35 /** Fake height value used in CCoins to signify they are only in the memory pool (since 0.8) */
36 static const unsigned int MEMPOOL_HEIGHT
= 0x7FFFFFFF;
40 /** \class CTxMemPoolEntry
42 * CTxMemPoolEntry stores data about the correponding transaction, as well
43 * as data about all in-mempool transactions that depend on the transaction
44 * ("descendant" transactions).
46 * When a new entry is added to the mempool, we update the descendant state
47 * (nCountWithDescendants, nSizeWithDescendants, and nFeesWithDescendants) for
48 * all ancestors of the newly added transaction.
50 * If updating the descendant state is skipped, we can mark the entry as
51 * "dirty", and set nSizeWithDescendants/nFeesWithDescendants to equal nTxSize/
52 * nTxFee. (This can potentially happen during a reorg, where we limit the
53 * amount of work we're willing to do to avoid consuming too much CPU.)
61 CAmount nFee
; //! Cached to avoid expensive parent-transaction lookups
62 size_t nTxSize
; //! ... and avoid recomputing tx size
63 size_t nModSize
; //! ... and modified size for priority
64 size_t nUsageSize
; //! ... and total memory usage
65 int64_t nTime
; //! Local time when entering the mempool
66 double dPriority
; //! Priority when entering the mempool
67 unsigned int nHeight
; //! Chain height when entering the mempool
68 bool hadNoDependencies
; //! Not dependent on any other txs when it entered the mempool
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 nFeesWithDescendants will not be
75 uint64_t nCountWithDescendants
; //! number of descendant transactions
76 uint64_t nSizeWithDescendants
; //! ... and size
77 CAmount nFeesWithDescendants
; //! ... and total fees (all including us)
80 CTxMemPoolEntry(const CTransaction
& _tx
, const CAmount
& _nFee
,
81 int64_t _nTime
, double _dPriority
, unsigned int _nHeight
, bool poolHasNoInputsOf
= false);
82 CTxMemPoolEntry(const CTxMemPoolEntry
& other
);
84 const CTransaction
& GetTx() const { return this->tx
; }
85 double GetPriority(unsigned int currentHeight
) const;
86 const CAmount
& GetFee() const { return nFee
; }
87 size_t GetTxSize() const { return nTxSize
; }
88 int64_t GetTime() const { return nTime
; }
89 unsigned int GetHeight() const { return nHeight
; }
90 bool WasClearAtEntry() const { return hadNoDependencies
; }
91 size_t DynamicMemoryUsage() const { return nUsageSize
; }
93 // Adjusts the descendant state, if this entry is not dirty.
94 void UpdateState(int64_t modifySize
, CAmount modifyFee
, int64_t modifyCount
);
96 /** We can set the entry to be dirty if doing the full calculation of in-
97 * mempool descendants will be too expensive, which can potentially happen
98 * when re-adding transactions from a block back to the mempool.
101 bool IsDirty() const { return nCountWithDescendants
== 0; }
103 uint64_t GetCountWithDescendants() const { return nCountWithDescendants
; }
104 uint64_t GetSizeWithDescendants() const { return nSizeWithDescendants
; }
105 CAmount
GetFeesWithDescendants() const { return nFeesWithDescendants
; }
108 // Helpers for modifying CTxMemPool::mapTx, which is a boost multi_index.
109 struct update_descendant_state
111 update_descendant_state(int64_t _modifySize
, CAmount _modifyFee
, int64_t _modifyCount
) :
112 modifySize(_modifySize
), modifyFee(_modifyFee
), modifyCount(_modifyCount
)
115 void operator() (CTxMemPoolEntry
&e
)
116 { e
.UpdateState(modifySize
, modifyFee
, modifyCount
); }
126 void operator() (CTxMemPoolEntry
&e
)
130 // extracts a TxMemPoolEntry's transaction hash
131 struct mempoolentry_txid
133 typedef uint256 result_type
;
134 result_type
operator() (const CTxMemPoolEntry
&entry
) const
136 return entry
.GetTx().GetHash();
140 /** \class CompareTxMemPoolEntryByFee
142 * Sort an entry by max(feerate of entry's tx, feerate with all descendants).
144 class CompareTxMemPoolEntryByFee
147 bool operator()(const CTxMemPoolEntry
& a
, const CTxMemPoolEntry
& b
)
149 bool fUseADescendants
= UseDescendantFeeRate(a
);
150 bool fUseBDescendants
= UseDescendantFeeRate(b
);
152 double aFees
= fUseADescendants
? a
.GetFeesWithDescendants() : a
.GetFee();
153 double aSize
= fUseADescendants
? a
.GetSizeWithDescendants() : a
.GetTxSize();
155 double bFees
= fUseBDescendants
? b
.GetFeesWithDescendants() : b
.GetFee();
156 double bSize
= fUseBDescendants
? b
.GetSizeWithDescendants() : b
.GetTxSize();
158 // Avoid division by rewriting (a/b > c/d) as (a*d > c*b).
159 double f1
= aFees
* bSize
;
160 double f2
= aSize
* bFees
;
163 return a
.GetTime() >= b
.GetTime();
168 // Calculate which feerate to use for an entry (avoiding division).
169 bool UseDescendantFeeRate(const CTxMemPoolEntry
&a
)
171 double f1
= (double)a
.GetFee() * a
.GetSizeWithDescendants();
172 double f2
= (double)a
.GetFeesWithDescendants() * a
.GetTxSize();
177 class CompareTxMemPoolEntryByEntryTime
180 bool operator()(const CTxMemPoolEntry
& a
, const CTxMemPoolEntry
& b
)
182 return a
.GetTime() < b
.GetTime();
186 class CBlockPolicyEstimator
;
188 /** An inpoint - a combination of a transaction and an index n into its vin */
192 const CTransaction
* ptx
;
195 CInPoint() { SetNull(); }
196 CInPoint(const CTransaction
* ptxIn
, uint32_t nIn
) { ptx
= ptxIn
; n
= nIn
; }
197 void SetNull() { ptx
= NULL
; n
= (uint32_t) -1; }
198 bool IsNull() const { return (ptx
== NULL
&& n
== (uint32_t) -1); }
199 size_t DynamicMemoryUsage() const { return 0; }
203 * CTxMemPool stores valid-according-to-the-current-best-chain
204 * transactions that may be included in the next block.
206 * Transactions are added when they are seen on the network
207 * (or created by the local node), but not all transactions seen
208 * are added to the pool: if a new transaction double-spends
209 * an input of a transaction in the pool, it is dropped,
210 * as are non-standard transactions.
212 * CTxMemPool::mapTx, and CTxMemPoolEntry bookkeeping:
214 * mapTx is a boost::multi_index that sorts the mempool on 3 criteria:
216 * - feerate [we use max(feerate of tx, feerate of tx with all descendants)]
219 * Note: the term "descendant" refers to in-mempool transactions that depend on
220 * this one, while "ancestor" refers to in-mempool transactions that a given
221 * transaction depends on.
223 * In order for the feerate sort to remain correct, we must update transactions
224 * in the mempool when new descendants arrive. To facilitate this, we track
225 * the set of in-mempool direct parents and direct children in mapLinks. Within
226 * each CTxMemPoolEntry, we track the size and fees of all descendants.
228 * Usually when a new transaction is added to the mempool, it has no in-mempool
229 * children (because any such children would be an orphan). So in
230 * addUnchecked(), we:
231 * - update a new entry's setMemPoolParents to include all in-mempool parents
232 * - update the new entry's direct parents to include the new tx as a child
233 * - update all ancestors of the transaction to include the new tx's size/fee
235 * When a transaction is removed from the mempool, we must:
236 * - update all in-mempool parents to not track the tx in setMemPoolChildren
237 * - update all ancestors to not include the tx's size/fees in descendant state
238 * - update all in-mempool children to not include it as a parent
240 * These happen in UpdateForRemoveFromMempool(). (Note that when removing a
241 * transaction along with its descendants, we must calculate that set of
242 * transactions to be removed before doing the removal, or else the mempool can
243 * be in an inconsistent state where it's impossible to walk the ancestors of
246 * In the event of a reorg, the assumption that a newly added tx has no
247 * in-mempool children is false. In particular, the mempool is in an
248 * inconsistent state while new transactions are being added, because there may
249 * be descendant transactions of a tx coming from a disconnected block that are
250 * unreachable from just looking at transactions in the mempool (the linking
251 * transactions may also be in the disconnected block, waiting to be added).
252 * Because of this, there's not much benefit in trying to search for in-mempool
253 * children in addUnchecked(). Instead, in the special case of transactions
254 * being added from a disconnected block, we require the caller to clean up the
255 * state, to account for in-mempool, out-of-block descendants for all the
256 * in-block transactions by calling UpdateTransactionsFromBlock(). Note that
257 * until this is called, the mempool state is not consistent, and in particular
258 * mapLinks may not be correct (and therefore functions like
259 * CalculateMemPoolAncestors() and CalculateDescendants() that rely
260 * on them to walk the mempool are not generally safe to use).
262 * Computational limits:
264 * Updating all in-mempool ancestors of a newly added transaction can be slow,
265 * if no bound exists on how many in-mempool ancestors there may be.
266 * CalculateMemPoolAncestors() takes configurable limits that are designed to
267 * prevent these calculations from being too CPU intensive.
269 * Adding transactions from a disconnected block can be very time consuming,
270 * because we don't have a way to limit the number of in-mempool descendants.
271 * To bound CPU processing, we limit the amount of work we're willing to do
272 * to properly update the descendant information for a tx being added from
273 * a disconnected block. If we would exceed the limit, then we instead mark
274 * the entry as "dirty", and set the feerate for sorting purposes to be equal
275 * the feerate of the transaction without any descendants.
281 bool fSanityCheck
; //! Normally false, true if -checkmempool or -regtest
282 unsigned int nTransactionsUpdated
;
283 CBlockPolicyEstimator
* minerPolicyEstimator
;
285 uint64_t totalTxSize
; //! sum of all mempool tx' byte sizes
286 uint64_t cachedInnerUsage
; //! sum of dynamic memory usage of all the map elements (NOT the maps themselves)
289 typedef boost::multi_index_container
<
291 boost::multi_index::indexed_by
<
293 boost::multi_index::ordered_unique
<mempoolentry_txid
>,
294 // sorted by fee rate
295 boost::multi_index::ordered_non_unique
<
296 boost::multi_index::identity
<CTxMemPoolEntry
>,
297 CompareTxMemPoolEntryByFee
299 // sorted by entry time
300 boost::multi_index::ordered_non_unique
<
301 boost::multi_index::identity
<CTxMemPoolEntry
>,
302 CompareTxMemPoolEntryByEntryTime
305 > indexed_transaction_set
;
307 mutable CCriticalSection cs
;
308 indexed_transaction_set mapTx
;
309 typedef indexed_transaction_set::nth_index
<0>::type::iterator txiter
;
310 struct CompareIteratorByHash
{
311 bool operator()(const txiter
&a
, const txiter
&b
) const {
312 return a
->GetTx().GetHash() < b
->GetTx().GetHash();
315 typedef std::set
<txiter
, CompareIteratorByHash
> setEntries
;
318 typedef std::map
<txiter
, setEntries
, CompareIteratorByHash
> cacheMap
;
325 typedef std::map
<txiter
, TxLinks
, CompareIteratorByHash
> txlinksMap
;
328 const setEntries
& GetMemPoolParents(txiter entry
) const;
329 const setEntries
& GetMemPoolChildren(txiter entry
) const;
330 void UpdateParent(txiter entry
, txiter parent
, bool add
);
331 void UpdateChild(txiter entry
, txiter child
, bool add
);
334 std::map
<COutPoint
, CInPoint
> mapNextTx
;
335 std::map
<uint256
, std::pair
<double, CAmount
> > mapDeltas
;
337 CTxMemPool(const CFeeRate
& _minRelayFee
);
341 * If sanity-checking is turned on, check makes sure the pool is
342 * consistent (does not contain two transactions that spend the same inputs,
343 * all inputs are in the mapNextTx array). If sanity-checking is turned off,
344 * check does nothing.
346 void check(const CCoinsViewCache
*pcoins
) const;
347 void setSanityCheck(bool _fSanityCheck
) { fSanityCheck
= _fSanityCheck
; }
349 // addUnchecked must updated state for all ancestors of a given transaction,
350 // to track size/count of descendant transactions. First version of
351 // addUnchecked can be used to have it call CalculateMemPoolAncestors(), and
352 // then invoke the second version.
353 bool addUnchecked(const uint256
& hash
, const CTxMemPoolEntry
&entry
, bool fCurrentEstimate
= true);
354 bool addUnchecked(const uint256
& hash
, const CTxMemPoolEntry
&entry
, setEntries
&setAncestors
, bool fCurrentEstimate
= true);
356 void remove(const CTransaction
&tx
, std::list
<CTransaction
>& removed
, bool fRecursive
= false);
357 void removeCoinbaseSpends(const CCoinsViewCache
*pcoins
, unsigned int nMemPoolHeight
);
358 void removeConflicts(const CTransaction
&tx
, std::list
<CTransaction
>& removed
);
359 void removeForBlock(const std::vector
<CTransaction
>& vtx
, unsigned int nBlockHeight
,
360 std::list
<CTransaction
>& conflicts
, bool fCurrentEstimate
= true);
362 void queryHashes(std::vector
<uint256
>& vtxid
);
363 void pruneSpent(const uint256
& hash
, CCoins
&coins
);
364 unsigned int GetTransactionsUpdated() const;
365 void AddTransactionsUpdated(unsigned int n
);
367 * Check that none of this transactions inputs are in the mempool, and thus
368 * the tx is not dependent on other mempool transactions to be included in a block.
370 bool HasNoInputsOf(const CTransaction
& tx
) const;
372 /** Affect CreateNewBlock prioritisation of transactions */
373 void PrioritiseTransaction(const uint256 hash
, const std::string strHash
, double dPriorityDelta
, const CAmount
& nFeeDelta
);
374 void ApplyDeltas(const uint256 hash
, double &dPriorityDelta
, CAmount
&nFeeDelta
) const;
375 void ClearPrioritisation(const uint256 hash
);
378 /** Remove a set of transactions from the mempool.
379 * If a transaction is in this set, then all in-mempool descendants must
380 * also be in the set.*/
381 void RemoveStaged(setEntries
&stage
);
383 /** When adding transactions from a disconnected block back to the mempool,
384 * new mempool entries may have children in the mempool (which is generally
385 * not the case when otherwise adding transactions).
386 * UpdateTransactionsFromBlock() will find child transactions and update the
387 * descendant state for each transaction in hashesToUpdate (excluding any
388 * child transactions present in hashesToUpdate, which are already accounted
389 * for). Note: hashesToUpdate should be the set of transactions from the
390 * disconnected block that have been accepted back into the mempool.
392 void UpdateTransactionsFromBlock(const std::vector
<uint256
> &hashesToUpdate
);
394 /** Try to calculate all in-mempool ancestors of entry.
395 * (these are all calculated including the tx itself)
396 * limitAncestorCount = max number of ancestors
397 * limitAncestorSize = max size of ancestors
398 * limitDescendantCount = max number of descendants any ancestor can have
399 * limitDescendantSize = max size of descendants any ancestor can have
400 * errString = populated with error reason if any limits are hit
401 * fSearchForParents = whether to search a tx's vin for in-mempool parents, or
402 * look up parents from mapLinks. Must be true for entries not in the mempool
404 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);
406 /** Expire all transaction (and their dependencies) in the mempool older than time. Return the number of removed transactions. */
407 int Expire(int64_t time
);
415 uint64_t GetTotalTxSize()
421 bool exists(uint256 hash
) const
424 return (mapTx
.count(hash
) != 0);
427 bool lookup(uint256 hash
, CTransaction
& result
) const;
429 /** Estimate fee rate needed to get into the next nBlocks */
430 CFeeRate
estimateFee(int nBlocks
) const;
432 /** Estimate priority needed to get into the next nBlocks */
433 double estimatePriority(int nBlocks
) const;
435 /** Write/Read estimates to disk */
436 bool WriteFeeEstimates(CAutoFile
& fileout
) const;
437 bool ReadFeeEstimates(CAutoFile
& filein
);
439 size_t DynamicMemoryUsage() const;
442 /** UpdateForDescendants is used by UpdateTransactionsFromBlock to update
443 * the descendants for a single transaction that has been added to the
444 * mempool but may have child transactions in the mempool, eg during a
445 * chain reorg. setExclude is the set of descendant transactions in the
446 * mempool that must not be accounted for (because any descendants in
447 * setExclude were added to the mempool after the transaction being
448 * updated and hence their state is already reflected in the parent
451 * If updating an entry requires looking at more than maxDescendantsToVisit
452 * transactions, outside of the ones in setExclude, then give up.
454 * cachedDescendants will be updated with the descendants of the transaction
455 * being updated, so that future invocations don't need to walk the
456 * same transaction again, if encountered in another transaction chain.
458 bool UpdateForDescendants(txiter updateIt
,
459 int maxDescendantsToVisit
,
460 cacheMap
&cachedDescendants
,
461 const std::set
<uint256
> &setExclude
);
462 /** Update ancestors of hash to add/remove it as a descendant transaction. */
463 void UpdateAncestorsOf(bool add
, txiter hash
, setEntries
&setAncestors
);
464 /** For each transaction being removed, update ancestors and any direct children. */
465 void UpdateForRemoveFromMempool(const setEntries
&entriesToRemove
);
466 /** Sever link between specified transaction and direct children. */
467 void UpdateChildrenForRemoval(txiter entry
);
468 /** Populate setDescendants with all in-mempool descendants of hash.
469 * Assumes that setDescendants includes all in-mempool descendants of anything
471 void CalculateDescendants(txiter it
, setEntries
&setDescendants
);
473 /** Before calling removeUnchecked for a given transaction,
474 * UpdateForRemoveFromMempool must be called on the entire (dependent) set
475 * of transactions being removed at the same time. We use each
476 * CTxMemPoolEntry's setMemPoolParents in order to walk ancestors of a
477 * given transaction that is removed, so we can't remove intermediate
478 * transactions in a chain before we've updated all the state for the
481 void removeUnchecked(txiter entry
);
485 * CCoinsView that brings transactions from a memorypool into view.
486 * It does not check for spendings by memory pool transactions.
488 class CCoinsViewMemPool
: public CCoinsViewBacked
494 CCoinsViewMemPool(CCoinsView
*baseIn
, CTxMemPool
&mempoolIn
);
495 bool GetCoins(const uint256
&txid
, CCoins
&coins
) const;
496 bool HaveCoins(const uint256
&txid
) const;
499 #endif // BITCOIN_TXMEMPOOL_H