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.
8 #include "consensus/consensus.h"
9 #include "consensus/tx_verify.h"
10 #include "consensus/validation.h"
11 #include "validation.h"
12 #include "policy/policy.h"
13 #include "policy/fees.h"
17 #include "utilmoneystr.h"
20 CTxMemPoolEntry::CTxMemPoolEntry(const CTransactionRef
& _tx
, const CAmount
& _nFee
,
21 int64_t _nTime
, unsigned int _entryHeight
,
22 bool _spendsCoinbase
, int64_t _sigOpsCost
, LockPoints lp
):
23 tx(_tx
), nFee(_nFee
), nTime(_nTime
), entryHeight(_entryHeight
),
24 spendsCoinbase(_spendsCoinbase
), sigOpCost(_sigOpsCost
), lockPoints(lp
)
26 nTxWeight
= GetTransactionWeight(*tx
);
27 nUsageSize
= RecursiveDynamicUsage(tx
);
29 nCountWithDescendants
= 1;
30 nSizeWithDescendants
= GetTxSize();
31 nModFeesWithDescendants
= nFee
;
35 nCountWithAncestors
= 1;
36 nSizeWithAncestors
= GetTxSize();
37 nModFeesWithAncestors
= nFee
;
38 nSigOpCostWithAncestors
= sigOpCost
;
41 CTxMemPoolEntry::CTxMemPoolEntry(const CTxMemPoolEntry
& other
)
46 void CTxMemPoolEntry::UpdateFeeDelta(int64_t newFeeDelta
)
48 nModFeesWithDescendants
+= newFeeDelta
- feeDelta
;
49 nModFeesWithAncestors
+= newFeeDelta
- feeDelta
;
50 feeDelta
= newFeeDelta
;
53 void CTxMemPoolEntry::UpdateLockPoints(const LockPoints
& lp
)
58 size_t CTxMemPoolEntry::GetTxSize() const
60 return GetVirtualTransactionSize(nTxWeight
, sigOpCost
);
63 // Update the given tx for any in-mempool descendants.
64 // Assumes that setMemPoolChildren is correct for the given tx and all
66 void CTxMemPool::UpdateForDescendants(txiter updateIt
, cacheMap
&cachedDescendants
, const std::set
<uint256
> &setExclude
)
68 setEntries stageEntries
, setAllDescendants
;
69 stageEntries
= GetMemPoolChildren(updateIt
);
71 while (!stageEntries
.empty()) {
72 const txiter cit
= *stageEntries
.begin();
73 setAllDescendants
.insert(cit
);
74 stageEntries
.erase(cit
);
75 const setEntries
&setChildren
= GetMemPoolChildren(cit
);
76 BOOST_FOREACH(const txiter childEntry
, setChildren
) {
77 cacheMap::iterator cacheIt
= cachedDescendants
.find(childEntry
);
78 if (cacheIt
!= cachedDescendants
.end()) {
79 // We've already calculated this one, just add the entries for this set
80 // but don't traverse again.
81 BOOST_FOREACH(const txiter cacheEntry
, cacheIt
->second
) {
82 setAllDescendants
.insert(cacheEntry
);
84 } else if (!setAllDescendants
.count(childEntry
)) {
85 // Schedule for later processing
86 stageEntries
.insert(childEntry
);
90 // setAllDescendants now contains all in-mempool descendants of updateIt.
91 // Update and add to cached descendant map
92 int64_t modifySize
= 0;
93 CAmount modifyFee
= 0;
94 int64_t modifyCount
= 0;
95 BOOST_FOREACH(txiter cit
, setAllDescendants
) {
96 if (!setExclude
.count(cit
->GetTx().GetHash())) {
97 modifySize
+= cit
->GetTxSize();
98 modifyFee
+= cit
->GetModifiedFee();
100 cachedDescendants
[updateIt
].insert(cit
);
101 // Update ancestor state for each descendant
102 mapTx
.modify(cit
, update_ancestor_state(updateIt
->GetTxSize(), updateIt
->GetModifiedFee(), 1, updateIt
->GetSigOpCost()));
105 mapTx
.modify(updateIt
, update_descendant_state(modifySize
, modifyFee
, modifyCount
));
108 // vHashesToUpdate is the set of transaction hashes from a disconnected block
109 // which has been re-added to the mempool.
110 // for each entry, look for descendants that are outside vHashesToUpdate, and
111 // add fee/size information for such descendants to the parent.
112 // for each such descendant, also update the ancestor state to include the parent.
113 void CTxMemPool::UpdateTransactionsFromBlock(const std::vector
<uint256
> &vHashesToUpdate
)
116 // For each entry in vHashesToUpdate, store the set of in-mempool, but not
117 // in-vHashesToUpdate transactions, so that we don't have to recalculate
118 // descendants when we come across a previously seen entry.
119 cacheMap mapMemPoolDescendantsToUpdate
;
121 // Use a set for lookups into vHashesToUpdate (these entries are already
122 // accounted for in the state of their ancestors)
123 std::set
<uint256
> setAlreadyIncluded(vHashesToUpdate
.begin(), vHashesToUpdate
.end());
125 // Iterate in reverse, so that whenever we are looking at at a transaction
126 // we are sure that all in-mempool descendants have already been processed.
127 // This maximizes the benefit of the descendant cache and guarantees that
128 // setMemPoolChildren will be updated, an assumption made in
129 // UpdateForDescendants.
130 BOOST_REVERSE_FOREACH(const uint256
&hash
, vHashesToUpdate
) {
131 // we cache the in-mempool children to avoid duplicate updates
132 setEntries setChildren
;
133 // calculate children from mapNextTx
134 txiter it
= mapTx
.find(hash
);
135 if (it
== mapTx
.end()) {
138 auto iter
= mapNextTx
.lower_bound(COutPoint(hash
, 0));
139 // First calculate the children, and update setMemPoolChildren to
140 // include them, and update their setMemPoolParents to include this tx.
141 for (; iter
!= mapNextTx
.end() && iter
->first
->hash
== hash
; ++iter
) {
142 const uint256
&childHash
= iter
->second
->GetHash();
143 txiter childIter
= mapTx
.find(childHash
);
144 assert(childIter
!= mapTx
.end());
145 // We can skip updating entries we've encountered before or that
146 // are in the block (which are already accounted for).
147 if (setChildren
.insert(childIter
).second
&& !setAlreadyIncluded
.count(childHash
)) {
148 UpdateChild(it
, childIter
, true);
149 UpdateParent(childIter
, it
, true);
152 UpdateForDescendants(it
, mapMemPoolDescendantsToUpdate
, setAlreadyIncluded
);
156 bool CTxMemPool::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
160 setEntries parentHashes
;
161 const CTransaction
&tx
= entry
.GetTx();
163 if (fSearchForParents
) {
164 // Get parents of this transaction that are in the mempool
165 // GetMemPoolParents() is only valid for entries in the mempool, so we
166 // iterate mapTx to find parents.
167 for (unsigned int i
= 0; i
< tx
.vin
.size(); i
++) {
168 txiter piter
= mapTx
.find(tx
.vin
[i
].prevout
.hash
);
169 if (piter
!= mapTx
.end()) {
170 parentHashes
.insert(piter
);
171 if (parentHashes
.size() + 1 > limitAncestorCount
) {
172 errString
= strprintf("too many unconfirmed parents [limit: %u]", limitAncestorCount
);
178 // If we're not searching for parents, we require this to be an
179 // entry in the mempool already.
180 txiter it
= mapTx
.iterator_to(entry
);
181 parentHashes
= GetMemPoolParents(it
);
184 size_t totalSizeWithAncestors
= entry
.GetTxSize();
186 while (!parentHashes
.empty()) {
187 txiter stageit
= *parentHashes
.begin();
189 setAncestors
.insert(stageit
);
190 parentHashes
.erase(stageit
);
191 totalSizeWithAncestors
+= stageit
->GetTxSize();
193 if (stageit
->GetSizeWithDescendants() + entry
.GetTxSize() > limitDescendantSize
) {
194 errString
= strprintf("exceeds descendant size limit for tx %s [limit: %u]", stageit
->GetTx().GetHash().ToString(), limitDescendantSize
);
196 } else if (stageit
->GetCountWithDescendants() + 1 > limitDescendantCount
) {
197 errString
= strprintf("too many descendants for tx %s [limit: %u]", stageit
->GetTx().GetHash().ToString(), limitDescendantCount
);
199 } else if (totalSizeWithAncestors
> limitAncestorSize
) {
200 errString
= strprintf("exceeds ancestor size limit [limit: %u]", limitAncestorSize
);
204 const setEntries
& setMemPoolParents
= GetMemPoolParents(stageit
);
205 BOOST_FOREACH(const txiter
&phash
, setMemPoolParents
) {
206 // If this is a new ancestor, add it.
207 if (setAncestors
.count(phash
) == 0) {
208 parentHashes
.insert(phash
);
210 if (parentHashes
.size() + setAncestors
.size() + 1 > limitAncestorCount
) {
211 errString
= strprintf("too many unconfirmed ancestors [limit: %u]", limitAncestorCount
);
220 void CTxMemPool::UpdateAncestorsOf(bool add
, txiter it
, setEntries
&setAncestors
)
222 setEntries parentIters
= GetMemPoolParents(it
);
223 // add or remove this tx as a child of each parent
224 BOOST_FOREACH(txiter piter
, parentIters
) {
225 UpdateChild(piter
, it
, add
);
227 const int64_t updateCount
= (add
? 1 : -1);
228 const int64_t updateSize
= updateCount
* it
->GetTxSize();
229 const CAmount updateFee
= updateCount
* it
->GetModifiedFee();
230 BOOST_FOREACH(txiter ancestorIt
, setAncestors
) {
231 mapTx
.modify(ancestorIt
, update_descendant_state(updateSize
, updateFee
, updateCount
));
235 void CTxMemPool::UpdateEntryForAncestors(txiter it
, const setEntries
&setAncestors
)
237 int64_t updateCount
= setAncestors
.size();
238 int64_t updateSize
= 0;
239 CAmount updateFee
= 0;
240 int64_t updateSigOpsCost
= 0;
241 BOOST_FOREACH(txiter ancestorIt
, setAncestors
) {
242 updateSize
+= ancestorIt
->GetTxSize();
243 updateFee
+= ancestorIt
->GetModifiedFee();
244 updateSigOpsCost
+= ancestorIt
->GetSigOpCost();
246 mapTx
.modify(it
, update_ancestor_state(updateSize
, updateFee
, updateCount
, updateSigOpsCost
));
249 void CTxMemPool::UpdateChildrenForRemoval(txiter it
)
251 const setEntries
&setMemPoolChildren
= GetMemPoolChildren(it
);
252 BOOST_FOREACH(txiter updateIt
, setMemPoolChildren
) {
253 UpdateParent(updateIt
, it
, false);
257 void CTxMemPool::UpdateForRemoveFromMempool(const setEntries
&entriesToRemove
, bool updateDescendants
)
259 // For each entry, walk back all ancestors and decrement size associated with this
261 const uint64_t nNoLimit
= std::numeric_limits
<uint64_t>::max();
262 if (updateDescendants
) {
263 // updateDescendants should be true whenever we're not recursively
264 // removing a tx and all its descendants, eg when a transaction is
265 // confirmed in a block.
266 // Here we only update statistics and not data in mapLinks (which
267 // we need to preserve until we're finished with all operations that
268 // need to traverse the mempool).
269 BOOST_FOREACH(txiter removeIt
, entriesToRemove
) {
270 setEntries setDescendants
;
271 CalculateDescendants(removeIt
, setDescendants
);
272 setDescendants
.erase(removeIt
); // don't update state for self
273 int64_t modifySize
= -((int64_t)removeIt
->GetTxSize());
274 CAmount modifyFee
= -removeIt
->GetModifiedFee();
275 int modifySigOps
= -removeIt
->GetSigOpCost();
276 BOOST_FOREACH(txiter dit
, setDescendants
) {
277 mapTx
.modify(dit
, update_ancestor_state(modifySize
, modifyFee
, -1, modifySigOps
));
281 BOOST_FOREACH(txiter removeIt
, entriesToRemove
) {
282 setEntries setAncestors
;
283 const CTxMemPoolEntry
&entry
= *removeIt
;
285 // Since this is a tx that is already in the mempool, we can call CMPA
286 // with fSearchForParents = false. If the mempool is in a consistent
287 // state, then using true or false should both be correct, though false
288 // should be a bit faster.
289 // However, if we happen to be in the middle of processing a reorg, then
290 // the mempool can be in an inconsistent state. In this case, the set
291 // of ancestors reachable via mapLinks will be the same as the set of
292 // ancestors whose packages include this transaction, because when we
293 // add a new transaction to the mempool in addUnchecked(), we assume it
294 // has no children, and in the case of a reorg where that assumption is
295 // false, the in-mempool children aren't linked to the in-block tx's
296 // until UpdateTransactionsFromBlock() is called.
297 // So if we're being called during a reorg, ie before
298 // UpdateTransactionsFromBlock() has been called, then mapLinks[] will
299 // differ from the set of mempool parents we'd calculate by searching,
300 // and it's important that we use the mapLinks[] notion of ancestor
301 // transactions as the set of things to update for removal.
302 CalculateMemPoolAncestors(entry
, setAncestors
, nNoLimit
, nNoLimit
, nNoLimit
, nNoLimit
, dummy
, false);
303 // Note that UpdateAncestorsOf severs the child links that point to
304 // removeIt in the entries for the parents of removeIt.
305 UpdateAncestorsOf(false, removeIt
, setAncestors
);
307 // After updating all the ancestor sizes, we can now sever the link between each
308 // transaction being removed and any mempool children (ie, update setMemPoolParents
309 // for each direct child of a transaction being removed).
310 BOOST_FOREACH(txiter removeIt
, entriesToRemove
) {
311 UpdateChildrenForRemoval(removeIt
);
315 void CTxMemPoolEntry::UpdateDescendantState(int64_t modifySize
, CAmount modifyFee
, int64_t modifyCount
)
317 nSizeWithDescendants
+= modifySize
;
318 assert(int64_t(nSizeWithDescendants
) > 0);
319 nModFeesWithDescendants
+= modifyFee
;
320 nCountWithDescendants
+= modifyCount
;
321 assert(int64_t(nCountWithDescendants
) > 0);
324 void CTxMemPoolEntry::UpdateAncestorState(int64_t modifySize
, CAmount modifyFee
, int64_t modifyCount
, int modifySigOps
)
326 nSizeWithAncestors
+= modifySize
;
327 assert(int64_t(nSizeWithAncestors
) > 0);
328 nModFeesWithAncestors
+= modifyFee
;
329 nCountWithAncestors
+= modifyCount
;
330 assert(int64_t(nCountWithAncestors
) > 0);
331 nSigOpCostWithAncestors
+= modifySigOps
;
332 assert(int(nSigOpCostWithAncestors
) >= 0);
335 CTxMemPool::CTxMemPool(CBlockPolicyEstimator
* estimator
) :
336 nTransactionsUpdated(0), minerPolicyEstimator(estimator
)
338 _clear(); //lock free clear
340 // Sanity checks off by default for performance, because otherwise
341 // accepting transactions becomes O(N^2) where N is the number
342 // of transactions in the pool
346 void CTxMemPool::pruneSpent(const uint256
&hashTx
, CCoins
&coins
)
350 auto it
= mapNextTx
.lower_bound(COutPoint(hashTx
, 0));
352 // iterate over all COutPoints in mapNextTx whose hash equals the provided hashTx
353 while (it
!= mapNextTx
.end() && it
->first
->hash
== hashTx
) {
354 coins
.Spend(it
->first
->n
); // and remove those outputs from coins
359 unsigned int CTxMemPool::GetTransactionsUpdated() const
362 return nTransactionsUpdated
;
365 void CTxMemPool::AddTransactionsUpdated(unsigned int n
)
368 nTransactionsUpdated
+= n
;
371 bool CTxMemPool::addUnchecked(const uint256
& hash
, const CTxMemPoolEntry
&entry
, setEntries
&setAncestors
, bool validFeeEstimate
)
373 NotifyEntryAdded(entry
.GetSharedTx());
374 // Add to memory pool without checking anything.
375 // Used by AcceptToMemoryPool(), which DOES do
376 // all the appropriate checks.
378 indexed_transaction_set::iterator newit
= mapTx
.insert(entry
).first
;
379 mapLinks
.insert(make_pair(newit
, TxLinks()));
381 // Update transaction for any feeDelta created by PrioritiseTransaction
382 // TODO: refactor so that the fee delta is calculated before inserting
384 std::map
<uint256
, CAmount
>::const_iterator pos
= mapDeltas
.find(hash
);
385 if (pos
!= mapDeltas
.end()) {
386 const CAmount
&delta
= pos
->second
;
388 mapTx
.modify(newit
, update_fee_delta(delta
));
392 // Update cachedInnerUsage to include contained transaction's usage.
393 // (When we update the entry for in-mempool parents, memory usage will be
395 cachedInnerUsage
+= entry
.DynamicMemoryUsage();
397 const CTransaction
& tx
= newit
->GetTx();
398 std::set
<uint256
> setParentTransactions
;
399 for (unsigned int i
= 0; i
< tx
.vin
.size(); i
++) {
400 mapNextTx
.insert(std::make_pair(&tx
.vin
[i
].prevout
, &tx
));
401 setParentTransactions
.insert(tx
.vin
[i
].prevout
.hash
);
403 // Don't bother worrying about child transactions of this one.
404 // Normal case of a new transaction arriving is that there can't be any
405 // children, because such children would be orphans.
406 // An exception to that is if a transaction enters that used to be in a block.
407 // In that case, our disconnect block logic will call UpdateTransactionsFromBlock
408 // to clean up the mess we're leaving here.
410 // Update ancestors with information about this tx
411 BOOST_FOREACH (const uint256
&phash
, setParentTransactions
) {
412 txiter pit
= mapTx
.find(phash
);
413 if (pit
!= mapTx
.end()) {
414 UpdateParent(newit
, pit
, true);
417 UpdateAncestorsOf(true, newit
, setAncestors
);
418 UpdateEntryForAncestors(newit
, setAncestors
);
420 nTransactionsUpdated
++;
421 totalTxSize
+= entry
.GetTxSize();
422 if (minerPolicyEstimator
) {minerPolicyEstimator
->processTransaction(entry
, validFeeEstimate
);}
424 vTxHashes
.emplace_back(tx
.GetWitnessHash(), newit
);
425 newit
->vTxHashesIdx
= vTxHashes
.size() - 1;
430 void CTxMemPool::removeUnchecked(txiter it
, MemPoolRemovalReason reason
)
432 NotifyEntryRemoved(it
->GetSharedTx(), reason
);
433 const uint256 hash
= it
->GetTx().GetHash();
434 BOOST_FOREACH(const CTxIn
& txin
, it
->GetTx().vin
)
435 mapNextTx
.erase(txin
.prevout
);
437 if (vTxHashes
.size() > 1) {
438 vTxHashes
[it
->vTxHashesIdx
] = std::move(vTxHashes
.back());
439 vTxHashes
[it
->vTxHashesIdx
].second
->vTxHashesIdx
= it
->vTxHashesIdx
;
440 vTxHashes
.pop_back();
441 if (vTxHashes
.size() * 2 < vTxHashes
.capacity())
442 vTxHashes
.shrink_to_fit();
446 totalTxSize
-= it
->GetTxSize();
447 cachedInnerUsage
-= it
->DynamicMemoryUsage();
448 cachedInnerUsage
-= memusage::DynamicUsage(mapLinks
[it
].parents
) + memusage::DynamicUsage(mapLinks
[it
].children
);
451 nTransactionsUpdated
++;
452 if (minerPolicyEstimator
) {minerPolicyEstimator
->removeTx(hash
, false);}
455 // Calculates descendants of entry that are not already in setDescendants, and adds to
456 // setDescendants. Assumes entryit is already a tx in the mempool and setMemPoolChildren
457 // is correct for tx and all descendants.
458 // Also assumes that if an entry is in setDescendants already, then all
459 // in-mempool descendants of it are already in setDescendants as well, so that we
460 // can save time by not iterating over those entries.
461 void CTxMemPool::CalculateDescendants(txiter entryit
, setEntries
&setDescendants
)
464 if (setDescendants
.count(entryit
) == 0) {
465 stage
.insert(entryit
);
467 // Traverse down the children of entry, only adding children that are not
468 // accounted for in setDescendants already (because those children have either
469 // already been walked, or will be walked in this iteration).
470 while (!stage
.empty()) {
471 txiter it
= *stage
.begin();
472 setDescendants
.insert(it
);
475 const setEntries
&setChildren
= GetMemPoolChildren(it
);
476 BOOST_FOREACH(const txiter
&childiter
, setChildren
) {
477 if (!setDescendants
.count(childiter
)) {
478 stage
.insert(childiter
);
484 void CTxMemPool::removeRecursive(const CTransaction
&origTx
, MemPoolRemovalReason reason
)
486 // Remove transaction from memory pool
489 setEntries txToRemove
;
490 txiter origit
= mapTx
.find(origTx
.GetHash());
491 if (origit
!= mapTx
.end()) {
492 txToRemove
.insert(origit
);
494 // When recursively removing but origTx isn't in the mempool
495 // be sure to remove any children that are in the pool. This can
496 // happen during chain re-orgs if origTx isn't re-accepted into
497 // the mempool for any reason.
498 for (unsigned int i
= 0; i
< origTx
.vout
.size(); i
++) {
499 auto it
= mapNextTx
.find(COutPoint(origTx
.GetHash(), i
));
500 if (it
== mapNextTx
.end())
502 txiter nextit
= mapTx
.find(it
->second
->GetHash());
503 assert(nextit
!= mapTx
.end());
504 txToRemove
.insert(nextit
);
507 setEntries setAllRemoves
;
508 BOOST_FOREACH(txiter it
, txToRemove
) {
509 CalculateDescendants(it
, setAllRemoves
);
512 RemoveStaged(setAllRemoves
, false, reason
);
516 void CTxMemPool::removeForReorg(const CCoinsViewCache
*pcoins
, unsigned int nMemPoolHeight
, int flags
)
518 // Remove transactions spending a coinbase which are now immature and no-longer-final transactions
520 setEntries txToRemove
;
521 for (indexed_transaction_set::const_iterator it
= mapTx
.begin(); it
!= mapTx
.end(); it
++) {
522 const CTransaction
& tx
= it
->GetTx();
523 LockPoints lp
= it
->GetLockPoints();
524 bool validLP
= TestLockPointValidity(&lp
);
525 if (!CheckFinalTx(tx
, flags
) || !CheckSequenceLocks(tx
, flags
, &lp
, validLP
)) {
526 // Note if CheckSequenceLocks fails the LockPoints may still be invalid
527 // So it's critical that we remove the tx and not depend on the LockPoints.
528 txToRemove
.insert(it
);
529 } else if (it
->GetSpendsCoinbase()) {
530 BOOST_FOREACH(const CTxIn
& txin
, tx
.vin
) {
531 indexed_transaction_set::const_iterator it2
= mapTx
.find(txin
.prevout
.hash
);
532 if (it2
!= mapTx
.end())
534 const CCoins
*coins
= pcoins
->AccessCoins(txin
.prevout
.hash
);
535 if (nCheckFrequency
!= 0) assert(coins
);
536 if (!coins
|| (coins
->IsCoinBase() && ((signed long)nMemPoolHeight
) - coins
->nHeight
< COINBASE_MATURITY
)) {
537 txToRemove
.insert(it
);
543 mapTx
.modify(it
, update_lock_points(lp
));
546 setEntries setAllRemoves
;
547 for (txiter it
: txToRemove
) {
548 CalculateDescendants(it
, setAllRemoves
);
550 RemoveStaged(setAllRemoves
, false, MemPoolRemovalReason::REORG
);
553 void CTxMemPool::removeConflicts(const CTransaction
&tx
)
555 // Remove transactions which depend on inputs of tx, recursively
557 BOOST_FOREACH(const CTxIn
&txin
, tx
.vin
) {
558 auto it
= mapNextTx
.find(txin
.prevout
);
559 if (it
!= mapNextTx
.end()) {
560 const CTransaction
&txConflict
= *it
->second
;
561 if (txConflict
!= tx
)
563 ClearPrioritisation(txConflict
.GetHash());
564 removeRecursive(txConflict
, MemPoolRemovalReason::CONFLICT
);
571 * Called when a block is connected. Removes from mempool and updates the miner fee estimator.
573 void CTxMemPool::removeForBlock(const std::vector
<CTransactionRef
>& vtx
, unsigned int nBlockHeight
)
576 std::vector
<const CTxMemPoolEntry
*> entries
;
577 for (const auto& tx
: vtx
)
579 uint256 hash
= tx
->GetHash();
581 indexed_transaction_set::iterator i
= mapTx
.find(hash
);
582 if (i
!= mapTx
.end())
583 entries
.push_back(&*i
);
585 // Before the txs in the new block have been removed from the mempool, update policy estimates
586 if (minerPolicyEstimator
) {minerPolicyEstimator
->processBlock(nBlockHeight
, entries
);}
587 for (const auto& tx
: vtx
)
589 txiter it
= mapTx
.find(tx
->GetHash());
590 if (it
!= mapTx
.end()) {
593 RemoveStaged(stage
, true, MemPoolRemovalReason::BLOCK
);
595 removeConflicts(*tx
);
596 ClearPrioritisation(tx
->GetHash());
598 lastRollingFeeUpdate
= GetTime();
599 blockSinceLastRollingFeeBump
= true;
602 void CTxMemPool::_clear()
608 cachedInnerUsage
= 0;
609 lastRollingFeeUpdate
= GetTime();
610 blockSinceLastRollingFeeBump
= false;
611 rollingMinimumFeeRate
= 0;
612 ++nTransactionsUpdated
;
615 void CTxMemPool::clear()
621 void CTxMemPool::check(const CCoinsViewCache
*pcoins
) const
623 if (nCheckFrequency
== 0)
626 if (GetRand(std::numeric_limits
<uint32_t>::max()) >= nCheckFrequency
)
629 LogPrint(BCLog::MEMPOOL
, "Checking mempool with %u transactions and %u inputs\n", (unsigned int)mapTx
.size(), (unsigned int)mapNextTx
.size());
631 uint64_t checkTotal
= 0;
632 uint64_t innerUsage
= 0;
634 CCoinsViewCache
mempoolDuplicate(const_cast<CCoinsViewCache
*>(pcoins
));
635 const int64_t nSpendHeight
= GetSpendHeight(mempoolDuplicate
);
638 std::list
<const CTxMemPoolEntry
*> waitingOnDependants
;
639 for (indexed_transaction_set::const_iterator it
= mapTx
.begin(); it
!= mapTx
.end(); it
++) {
641 checkTotal
+= it
->GetTxSize();
642 innerUsage
+= it
->DynamicMemoryUsage();
643 const CTransaction
& tx
= it
->GetTx();
644 txlinksMap::const_iterator linksiter
= mapLinks
.find(it
);
645 assert(linksiter
!= mapLinks
.end());
646 const TxLinks
&links
= linksiter
->second
;
647 innerUsage
+= memusage::DynamicUsage(links
.parents
) + memusage::DynamicUsage(links
.children
);
648 bool fDependsWait
= false;
649 setEntries setParentCheck
;
650 int64_t parentSizes
= 0;
651 int64_t parentSigOpCost
= 0;
652 BOOST_FOREACH(const CTxIn
&txin
, tx
.vin
) {
653 // Check that every mempool transaction's inputs refer to available coins, or other mempool tx's.
654 indexed_transaction_set::const_iterator it2
= mapTx
.find(txin
.prevout
.hash
);
655 if (it2
!= mapTx
.end()) {
656 const CTransaction
& tx2
= it2
->GetTx();
657 assert(tx2
.vout
.size() > txin
.prevout
.n
&& !tx2
.vout
[txin
.prevout
.n
].IsNull());
659 if (setParentCheck
.insert(it2
).second
) {
660 parentSizes
+= it2
->GetTxSize();
661 parentSigOpCost
+= it2
->GetSigOpCost();
664 const CCoins
* coins
= pcoins
->AccessCoins(txin
.prevout
.hash
);
665 assert(coins
&& coins
->IsAvailable(txin
.prevout
.n
));
667 // Check whether its inputs are marked in mapNextTx.
668 auto it3
= mapNextTx
.find(txin
.prevout
);
669 assert(it3
!= mapNextTx
.end());
670 assert(it3
->first
== &txin
.prevout
);
671 assert(it3
->second
== &tx
);
674 assert(setParentCheck
== GetMemPoolParents(it
));
675 // Verify ancestor state is correct.
676 setEntries setAncestors
;
677 uint64_t nNoLimit
= std::numeric_limits
<uint64_t>::max();
679 CalculateMemPoolAncestors(*it
, setAncestors
, nNoLimit
, nNoLimit
, nNoLimit
, nNoLimit
, dummy
);
680 uint64_t nCountCheck
= setAncestors
.size() + 1;
681 uint64_t nSizeCheck
= it
->GetTxSize();
682 CAmount nFeesCheck
= it
->GetModifiedFee();
683 int64_t nSigOpCheck
= it
->GetSigOpCost();
685 BOOST_FOREACH(txiter ancestorIt
, setAncestors
) {
686 nSizeCheck
+= ancestorIt
->GetTxSize();
687 nFeesCheck
+= ancestorIt
->GetModifiedFee();
688 nSigOpCheck
+= ancestorIt
->GetSigOpCost();
691 assert(it
->GetCountWithAncestors() == nCountCheck
);
692 assert(it
->GetSizeWithAncestors() == nSizeCheck
);
693 assert(it
->GetSigOpCostWithAncestors() == nSigOpCheck
);
694 assert(it
->GetModFeesWithAncestors() == nFeesCheck
);
696 // Check children against mapNextTx
697 CTxMemPool::setEntries setChildrenCheck
;
698 auto iter
= mapNextTx
.lower_bound(COutPoint(it
->GetTx().GetHash(), 0));
699 int64_t childSizes
= 0;
700 for (; iter
!= mapNextTx
.end() && iter
->first
->hash
== it
->GetTx().GetHash(); ++iter
) {
701 txiter childit
= mapTx
.find(iter
->second
->GetHash());
702 assert(childit
!= mapTx
.end()); // mapNextTx points to in-mempool transactions
703 if (setChildrenCheck
.insert(childit
).second
) {
704 childSizes
+= childit
->GetTxSize();
707 assert(setChildrenCheck
== GetMemPoolChildren(it
));
708 // Also check to make sure size is greater than sum with immediate children.
709 // just a sanity check, not definitive that this calc is correct...
710 assert(it
->GetSizeWithDescendants() >= childSizes
+ it
->GetTxSize());
713 waitingOnDependants
.push_back(&(*it
));
715 CValidationState state
;
716 bool fCheckResult
= tx
.IsCoinBase() ||
717 Consensus::CheckTxInputs(tx
, state
, mempoolDuplicate
, nSpendHeight
);
718 assert(fCheckResult
);
719 UpdateCoins(tx
, mempoolDuplicate
, 1000000);
722 unsigned int stepsSinceLastRemove
= 0;
723 while (!waitingOnDependants
.empty()) {
724 const CTxMemPoolEntry
* entry
= waitingOnDependants
.front();
725 waitingOnDependants
.pop_front();
726 CValidationState state
;
727 if (!mempoolDuplicate
.HaveInputs(entry
->GetTx())) {
728 waitingOnDependants
.push_back(entry
);
729 stepsSinceLastRemove
++;
730 assert(stepsSinceLastRemove
< waitingOnDependants
.size());
732 bool fCheckResult
= entry
->GetTx().IsCoinBase() ||
733 Consensus::CheckTxInputs(entry
->GetTx(), state
, mempoolDuplicate
, nSpendHeight
);
734 assert(fCheckResult
);
735 UpdateCoins(entry
->GetTx(), mempoolDuplicate
, 1000000);
736 stepsSinceLastRemove
= 0;
739 for (auto it
= mapNextTx
.cbegin(); it
!= mapNextTx
.cend(); it
++) {
740 uint256 hash
= it
->second
->GetHash();
741 indexed_transaction_set::const_iterator it2
= mapTx
.find(hash
);
742 const CTransaction
& tx
= it2
->GetTx();
743 assert(it2
!= mapTx
.end());
744 assert(&tx
== it
->second
);
747 assert(totalTxSize
== checkTotal
);
748 assert(innerUsage
== cachedInnerUsage
);
751 bool CTxMemPool::CompareDepthAndScore(const uint256
& hasha
, const uint256
& hashb
)
754 indexed_transaction_set::const_iterator i
= mapTx
.find(hasha
);
755 if (i
== mapTx
.end()) return false;
756 indexed_transaction_set::const_iterator j
= mapTx
.find(hashb
);
757 if (j
== mapTx
.end()) return true;
758 uint64_t counta
= i
->GetCountWithAncestors();
759 uint64_t countb
= j
->GetCountWithAncestors();
760 if (counta
== countb
) {
761 return CompareTxMemPoolEntryByScore()(*i
, *j
);
763 return counta
< countb
;
767 class DepthAndScoreComparator
770 bool operator()(const CTxMemPool::indexed_transaction_set::const_iterator
& a
, const CTxMemPool::indexed_transaction_set::const_iterator
& b
)
772 uint64_t counta
= a
->GetCountWithAncestors();
773 uint64_t countb
= b
->GetCountWithAncestors();
774 if (counta
== countb
) {
775 return CompareTxMemPoolEntryByScore()(*a
, *b
);
777 return counta
< countb
;
782 std::vector
<CTxMemPool::indexed_transaction_set::const_iterator
> CTxMemPool::GetSortedDepthAndScore() const
784 std::vector
<indexed_transaction_set::const_iterator
> iters
;
787 iters
.reserve(mapTx
.size());
789 for (indexed_transaction_set::iterator mi
= mapTx
.begin(); mi
!= mapTx
.end(); ++mi
) {
792 std::sort(iters
.begin(), iters
.end(), DepthAndScoreComparator());
796 void CTxMemPool::queryHashes(std::vector
<uint256
>& vtxid
)
799 auto iters
= GetSortedDepthAndScore();
802 vtxid
.reserve(mapTx
.size());
804 for (auto it
: iters
) {
805 vtxid
.push_back(it
->GetTx().GetHash());
809 static TxMempoolInfo
GetInfo(CTxMemPool::indexed_transaction_set::const_iterator it
) {
810 return TxMempoolInfo
{it
->GetSharedTx(), it
->GetTime(), CFeeRate(it
->GetFee(), it
->GetTxSize()), it
->GetModifiedFee() - it
->GetFee()};
813 std::vector
<TxMempoolInfo
> CTxMemPool::infoAll() const
816 auto iters
= GetSortedDepthAndScore();
818 std::vector
<TxMempoolInfo
> ret
;
819 ret
.reserve(mapTx
.size());
820 for (auto it
: iters
) {
821 ret
.push_back(GetInfo(it
));
827 CTransactionRef
CTxMemPool::get(const uint256
& hash
) const
830 indexed_transaction_set::const_iterator i
= mapTx
.find(hash
);
831 if (i
== mapTx
.end())
833 return i
->GetSharedTx();
836 TxMempoolInfo
CTxMemPool::info(const uint256
& hash
) const
839 indexed_transaction_set::const_iterator i
= mapTx
.find(hash
);
840 if (i
== mapTx
.end())
841 return TxMempoolInfo();
845 void CTxMemPool::PrioritiseTransaction(const uint256
& hash
, const CAmount
& nFeeDelta
)
849 CAmount
&delta
= mapDeltas
[hash
];
851 txiter it
= mapTx
.find(hash
);
852 if (it
!= mapTx
.end()) {
853 mapTx
.modify(it
, update_fee_delta(delta
));
854 // Now update all ancestors' modified fees with descendants
855 setEntries setAncestors
;
856 uint64_t nNoLimit
= std::numeric_limits
<uint64_t>::max();
858 CalculateMemPoolAncestors(*it
, setAncestors
, nNoLimit
, nNoLimit
, nNoLimit
, nNoLimit
, dummy
, false);
859 BOOST_FOREACH(txiter ancestorIt
, setAncestors
) {
860 mapTx
.modify(ancestorIt
, update_descendant_state(0, nFeeDelta
, 0));
862 // Now update all descendants' modified fees with ancestors
863 setEntries setDescendants
;
864 CalculateDescendants(it
, setDescendants
);
865 setDescendants
.erase(it
);
866 BOOST_FOREACH(txiter descendantIt
, setDescendants
) {
867 mapTx
.modify(descendantIt
, update_ancestor_state(0, nFeeDelta
, 0, 0));
869 ++nTransactionsUpdated
;
872 LogPrintf("PrioritiseTransaction: %s feerate += %s\n", hash
.ToString(), FormatMoney(nFeeDelta
));
875 void CTxMemPool::ApplyDelta(const uint256 hash
, CAmount
&nFeeDelta
) const
878 std::map
<uint256
, CAmount
>::const_iterator pos
= mapDeltas
.find(hash
);
879 if (pos
== mapDeltas
.end())
881 const CAmount
&delta
= pos
->second
;
885 void CTxMemPool::ClearPrioritisation(const uint256 hash
)
888 mapDeltas
.erase(hash
);
891 bool CTxMemPool::HasNoInputsOf(const CTransaction
&tx
) const
893 for (unsigned int i
= 0; i
< tx
.vin
.size(); i
++)
894 if (exists(tx
.vin
[i
].prevout
.hash
))
899 CCoinsViewMemPool::CCoinsViewMemPool(CCoinsView
* baseIn
, const CTxMemPool
& mempoolIn
) : CCoinsViewBacked(baseIn
), mempool(mempoolIn
) { }
901 bool CCoinsViewMemPool::GetCoins(const uint256
&txid
, CCoins
&coins
) const {
902 // If an entry in the mempool exists, always return that one, as it's guaranteed to never
903 // conflict with the underlying cache, and it cannot have pruned entries (as it contains full)
904 // transactions. First checking the underlying cache risks returning a pruned entry instead.
905 CTransactionRef ptx
= mempool
.get(txid
);
907 coins
= CCoins(*ptx
, MEMPOOL_HEIGHT
);
910 return (base
->GetCoins(txid
, coins
) && !coins
.IsPruned());
913 bool CCoinsViewMemPool::HaveCoins(const uint256
&txid
) const {
914 return mempool
.exists(txid
) || base
->HaveCoins(txid
);
917 size_t CTxMemPool::DynamicMemoryUsage() const {
919 // Estimate the overhead of mapTx to be 15 pointers + an allocation, as no exact formula for boost::multi_index_contained is implemented.
920 return memusage::MallocUsage(sizeof(CTxMemPoolEntry
) + 15 * sizeof(void*)) * mapTx
.size() + memusage::DynamicUsage(mapNextTx
) + memusage::DynamicUsage(mapDeltas
) + memusage::DynamicUsage(mapLinks
) + memusage::DynamicUsage(vTxHashes
) + cachedInnerUsage
;
923 void CTxMemPool::RemoveStaged(setEntries
&stage
, bool updateDescendants
, MemPoolRemovalReason reason
) {
925 UpdateForRemoveFromMempool(stage
, updateDescendants
);
926 BOOST_FOREACH(const txiter
& it
, stage
) {
927 removeUnchecked(it
, reason
);
931 int CTxMemPool::Expire(int64_t time
) {
933 indexed_transaction_set::index
<entry_time
>::type::iterator it
= mapTx
.get
<entry_time
>().begin();
935 while (it
!= mapTx
.get
<entry_time
>().end() && it
->GetTime() < time
) {
936 toremove
.insert(mapTx
.project
<0>(it
));
940 BOOST_FOREACH(txiter removeit
, toremove
) {
941 CalculateDescendants(removeit
, stage
);
943 RemoveStaged(stage
, false, MemPoolRemovalReason::EXPIRY
);
947 bool CTxMemPool::addUnchecked(const uint256
&hash
, const CTxMemPoolEntry
&entry
, bool validFeeEstimate
)
950 setEntries setAncestors
;
951 uint64_t nNoLimit
= std::numeric_limits
<uint64_t>::max();
953 CalculateMemPoolAncestors(entry
, setAncestors
, nNoLimit
, nNoLimit
, nNoLimit
, nNoLimit
, dummy
);
954 return addUnchecked(hash
, entry
, setAncestors
, validFeeEstimate
);
957 void CTxMemPool::UpdateChild(txiter entry
, txiter child
, bool add
)
960 if (add
&& mapLinks
[entry
].children
.insert(child
).second
) {
961 cachedInnerUsage
+= memusage::IncrementalDynamicUsage(s
);
962 } else if (!add
&& mapLinks
[entry
].children
.erase(child
)) {
963 cachedInnerUsage
-= memusage::IncrementalDynamicUsage(s
);
967 void CTxMemPool::UpdateParent(txiter entry
, txiter parent
, bool add
)
970 if (add
&& mapLinks
[entry
].parents
.insert(parent
).second
) {
971 cachedInnerUsage
+= memusage::IncrementalDynamicUsage(s
);
972 } else if (!add
&& mapLinks
[entry
].parents
.erase(parent
)) {
973 cachedInnerUsage
-= memusage::IncrementalDynamicUsage(s
);
977 const CTxMemPool::setEntries
& CTxMemPool::GetMemPoolParents(txiter entry
) const
979 assert (entry
!= mapTx
.end());
980 txlinksMap::const_iterator it
= mapLinks
.find(entry
);
981 assert(it
!= mapLinks
.end());
982 return it
->second
.parents
;
985 const CTxMemPool::setEntries
& CTxMemPool::GetMemPoolChildren(txiter entry
) const
987 assert (entry
!= mapTx
.end());
988 txlinksMap::const_iterator it
= mapLinks
.find(entry
);
989 assert(it
!= mapLinks
.end());
990 return it
->second
.children
;
993 CFeeRate
CTxMemPool::GetMinFee(size_t sizelimit
) const {
995 if (!blockSinceLastRollingFeeBump
|| rollingMinimumFeeRate
== 0)
996 return CFeeRate(rollingMinimumFeeRate
);
998 int64_t time
= GetTime();
999 if (time
> lastRollingFeeUpdate
+ 10) {
1000 double halflife
= ROLLING_FEE_HALFLIFE
;
1001 if (DynamicMemoryUsage() < sizelimit
/ 4)
1003 else if (DynamicMemoryUsage() < sizelimit
/ 2)
1006 rollingMinimumFeeRate
= rollingMinimumFeeRate
/ pow(2.0, (time
- lastRollingFeeUpdate
) / halflife
);
1007 lastRollingFeeUpdate
= time
;
1009 if (rollingMinimumFeeRate
< (double)incrementalRelayFee
.GetFeePerK() / 2) {
1010 rollingMinimumFeeRate
= 0;
1014 return std::max(CFeeRate(rollingMinimumFeeRate
), incrementalRelayFee
);
1017 void CTxMemPool::trackPackageRemoved(const CFeeRate
& rate
) {
1019 if (rate
.GetFeePerK() > rollingMinimumFeeRate
) {
1020 rollingMinimumFeeRate
= rate
.GetFeePerK();
1021 blockSinceLastRollingFeeBump
= false;
1025 void CTxMemPool::TrimToSize(size_t sizelimit
, std::vector
<uint256
>* pvNoSpendsRemaining
) {
1028 unsigned nTxnRemoved
= 0;
1029 CFeeRate
maxFeeRateRemoved(0);
1030 while (!mapTx
.empty() && DynamicMemoryUsage() > sizelimit
) {
1031 indexed_transaction_set::index
<descendant_score
>::type::iterator it
= mapTx
.get
<descendant_score
>().begin();
1033 // We set the new mempool min fee to the feerate of the removed set, plus the
1034 // "minimum reasonable fee rate" (ie some value under which we consider txn
1035 // to have 0 fee). This way, we don't allow txn to enter mempool with feerate
1036 // equal to txn which were removed with no block in between.
1037 CFeeRate
removed(it
->GetModFeesWithDescendants(), it
->GetSizeWithDescendants());
1038 removed
+= incrementalRelayFee
;
1039 trackPackageRemoved(removed
);
1040 maxFeeRateRemoved
= std::max(maxFeeRateRemoved
, removed
);
1043 CalculateDescendants(mapTx
.project
<0>(it
), stage
);
1044 nTxnRemoved
+= stage
.size();
1046 std::vector
<CTransaction
> txn
;
1047 if (pvNoSpendsRemaining
) {
1048 txn
.reserve(stage
.size());
1049 BOOST_FOREACH(txiter iter
, stage
)
1050 txn
.push_back(iter
->GetTx());
1052 RemoveStaged(stage
, false, MemPoolRemovalReason::SIZELIMIT
);
1053 if (pvNoSpendsRemaining
) {
1054 BOOST_FOREACH(const CTransaction
& tx
, txn
) {
1055 BOOST_FOREACH(const CTxIn
& txin
, tx
.vin
) {
1056 if (exists(txin
.prevout
.hash
))
1058 auto iter
= mapNextTx
.lower_bound(COutPoint(txin
.prevout
.hash
, 0));
1059 if (iter
== mapNextTx
.end() || iter
->first
->hash
!= txin
.prevout
.hash
)
1060 pvNoSpendsRemaining
->push_back(txin
.prevout
.hash
);
1066 if (maxFeeRateRemoved
> CFeeRate(0)) {
1067 LogPrint(BCLog::MEMPOOL
, "Removed %u txn, rolling minimum fee bumped to %s\n", nTxnRemoved
, maxFeeRateRemoved
.ToString());
1071 bool CTxMemPool::TransactionWithinChainLimit(const uint256
& txid
, size_t chainLimit
) const {
1073 auto it
= mapTx
.find(txid
);
1074 return it
== mapTx
.end() || (it
->GetCountWithAncestors() < chainLimit
&&
1075 it
->GetCountWithDescendants() < chainLimit
);