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.
8 #include "clientversion.h"
9 #include "consensus/consensus.h"
10 #include "consensus/validation.h"
12 #include "policy/fees.h"
15 #include "utilmoneystr.h"
21 CTxMemPoolEntry::CTxMemPoolEntry(const CTransaction
& _tx
, const CAmount
& _nFee
,
22 int64_t _nTime
, double _entryPriority
,
23 unsigned int _entryHeight
, bool poolHasNoInputsOf
):
24 tx(_tx
), nFee(_nFee
), nTime(_nTime
), entryPriority(_entryPriority
), entryHeight(_entryHeight
),
25 hadNoDependencies(poolHasNoInputsOf
)
27 nTxSize
= ::GetSerializeSize(tx
, SER_NETWORK
, PROTOCOL_VERSION
);
28 nModSize
= tx
.CalculateModifiedSize(nTxSize
);
29 nUsageSize
= RecursiveDynamicUsage(tx
);
31 nCountWithDescendants
= 1;
32 nSizeWithDescendants
= nTxSize
;
33 nFeesWithDescendants
= nFee
;
36 CTxMemPoolEntry::CTxMemPoolEntry(const CTxMemPoolEntry
& other
)
42 CTxMemPoolEntry::GetPriority(unsigned int currentHeight
) const
44 CAmount nValueIn
= tx
.GetValueOut()+nFee
;
45 double deltaPriority
= ((double)(currentHeight
-entryHeight
)*nValueIn
)/nModSize
;
46 double dResult
= entryPriority
+ deltaPriority
;
50 // Update the given tx for any in-mempool descendants.
51 // Assumes that setMemPoolChildren is correct for the given tx and all
53 bool CTxMemPool::UpdateForDescendants(txiter updateIt
, int maxDescendantsToVisit
, cacheMap
&cachedDescendants
, const std::set
<uint256
> &setExclude
)
55 // Track the number of entries (outside setExclude) that we'd need to visit
56 // (will bail out if it exceeds maxDescendantsToVisit)
57 int nChildrenToVisit
= 0;
59 setEntries stageEntries
, setAllDescendants
;
60 stageEntries
= GetMemPoolChildren(updateIt
);
62 while (!stageEntries
.empty()) {
63 const txiter cit
= *stageEntries
.begin();
65 // Don't consider any more children if any descendant is dirty
68 setAllDescendants
.insert(cit
);
69 stageEntries
.erase(cit
);
70 const setEntries
&setChildren
= GetMemPoolChildren(cit
);
71 BOOST_FOREACH(const txiter childEntry
, setChildren
) {
72 cacheMap::iterator cacheIt
= cachedDescendants
.find(childEntry
);
73 if (cacheIt
!= cachedDescendants
.end()) {
74 // We've already calculated this one, just add the entries for this set
75 // but don't traverse again.
76 BOOST_FOREACH(const txiter cacheEntry
, cacheIt
->second
) {
77 // update visit count only for new child transactions
78 // (outside of setExclude and stageEntries)
79 if (setAllDescendants
.insert(cacheEntry
).second
&&
80 !setExclude
.count(cacheEntry
->GetTx().GetHash()) &&
81 !stageEntries
.count(cacheEntry
)) {
85 } else if (!setAllDescendants
.count(childEntry
)) {
86 // Schedule for later processing and update our visit count
87 if (stageEntries
.insert(childEntry
).second
&& !setExclude
.count(childEntry
->GetTx().GetHash())) {
91 if (nChildrenToVisit
> maxDescendantsToVisit
) {
96 // setAllDescendants now contains all in-mempool descendants of updateIt.
97 // Update and add to cached descendant map
98 int64_t modifySize
= 0;
99 CAmount modifyFee
= 0;
100 int64_t modifyCount
= 0;
101 BOOST_FOREACH(txiter cit
, setAllDescendants
) {
102 if (!setExclude
.count(cit
->GetTx().GetHash())) {
103 modifySize
+= cit
->GetTxSize();
104 modifyFee
+= cit
->GetFee();
106 cachedDescendants
[updateIt
].insert(cit
);
109 mapTx
.modify(updateIt
, update_descendant_state(modifySize
, modifyFee
, modifyCount
));
113 // vHashesToUpdate is the set of transaction hashes from a disconnected block
114 // which has been re-added to the mempool.
115 // for each entry, look for descendants that are outside hashesToUpdate, and
116 // add fee/size information for such descendants to the parent.
117 void CTxMemPool::UpdateTransactionsFromBlock(const std::vector
<uint256
> &vHashesToUpdate
)
120 // For each entry in vHashesToUpdate, store the set of in-mempool, but not
121 // in-vHashesToUpdate transactions, so that we don't have to recalculate
122 // descendants when we come across a previously seen entry.
123 cacheMap mapMemPoolDescendantsToUpdate
;
125 // Use a set for lookups into vHashesToUpdate (these entries are already
126 // accounted for in the state of their ancestors)
127 std::set
<uint256
> setAlreadyIncluded(vHashesToUpdate
.begin(), vHashesToUpdate
.end());
129 // Iterate in reverse, so that whenever we are looking at at a transaction
130 // we are sure that all in-mempool descendants have already been processed.
131 // This maximizes the benefit of the descendant cache and guarantees that
132 // setMemPoolChildren will be updated, an assumption made in
133 // UpdateForDescendants.
134 BOOST_REVERSE_FOREACH(const uint256
&hash
, vHashesToUpdate
) {
135 // we cache the in-mempool children to avoid duplicate updates
136 setEntries setChildren
;
137 // calculate children from mapNextTx
138 txiter it
= mapTx
.find(hash
);
139 if (it
== mapTx
.end()) {
142 std::map
<COutPoint
, CInPoint
>::iterator iter
= mapNextTx
.lower_bound(COutPoint(hash
, 0));
143 // First calculate the children, and update setMemPoolChildren to
144 // include them, and update their setMemPoolParents to include this tx.
145 for (; iter
!= mapNextTx
.end() && iter
->first
.hash
== hash
; ++iter
) {
146 const uint256
&childHash
= iter
->second
.ptx
->GetHash();
147 txiter childIter
= mapTx
.find(childHash
);
148 assert(childIter
!= mapTx
.end());
149 // We can skip updating entries we've encountered before or that
150 // are in the block (which are already accounted for).
151 if (setChildren
.insert(childIter
).second
&& !setAlreadyIncluded
.count(childHash
)) {
152 UpdateChild(it
, childIter
, true);
153 UpdateParent(childIter
, it
, true);
156 if (!UpdateForDescendants(it
, 100, mapMemPoolDescendantsToUpdate
, setAlreadyIncluded
)) {
157 // Mark as dirty if we can't do the calculation.
158 mapTx
.modify(it
, set_dirty());
163 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 */)
165 setEntries parentHashes
;
166 const CTransaction
&tx
= entry
.GetTx();
168 if (fSearchForParents
) {
169 // Get parents of this transaction that are in the mempool
170 // GetMemPoolParents() is only valid for entries in the mempool, so we
171 // iterate mapTx to find parents.
172 for (unsigned int i
= 0; i
< tx
.vin
.size(); i
++) {
173 txiter piter
= mapTx
.find(tx
.vin
[i
].prevout
.hash
);
174 if (piter
!= mapTx
.end()) {
175 parentHashes
.insert(piter
);
176 if (parentHashes
.size() + 1 > limitAncestorCount
) {
177 errString
= strprintf("too many unconfirmed parents [limit: %u]", limitAncestorCount
);
183 // If we're not searching for parents, we require this to be an
184 // entry in the mempool already.
185 txiter it
= mapTx
.iterator_to(entry
);
186 parentHashes
= GetMemPoolParents(it
);
189 size_t totalSizeWithAncestors
= entry
.GetTxSize();
191 while (!parentHashes
.empty()) {
192 txiter stageit
= *parentHashes
.begin();
194 setAncestors
.insert(stageit
);
195 parentHashes
.erase(stageit
);
196 totalSizeWithAncestors
+= stageit
->GetTxSize();
198 if (stageit
->GetSizeWithDescendants() + entry
.GetTxSize() > limitDescendantSize
) {
199 errString
= strprintf("exceeds descendant size limit for tx %s [limit: %u]", stageit
->GetTx().GetHash().ToString(), limitDescendantSize
);
201 } else if (stageit
->GetCountWithDescendants() + 1 > limitDescendantCount
) {
202 errString
= strprintf("too many descendants for tx %s [limit: %u]", stageit
->GetTx().GetHash().ToString(), limitDescendantCount
);
204 } else if (totalSizeWithAncestors
> limitAncestorSize
) {
205 errString
= strprintf("exceeds ancestor size limit [limit: %u]", limitAncestorSize
);
209 const setEntries
& setMemPoolParents
= GetMemPoolParents(stageit
);
210 BOOST_FOREACH(const txiter
&phash
, setMemPoolParents
) {
211 // If this is a new ancestor, add it.
212 if (setAncestors
.count(phash
) == 0) {
213 parentHashes
.insert(phash
);
215 if (parentHashes
.size() + setAncestors
.size() + 1 > limitAncestorCount
) {
216 errString
= strprintf("too many unconfirmed ancestors [limit: %u]", limitAncestorCount
);
225 void CTxMemPool::UpdateAncestorsOf(bool add
, txiter it
, setEntries
&setAncestors
)
227 setEntries parentIters
= GetMemPoolParents(it
);
228 // add or remove this tx as a child of each parent
229 BOOST_FOREACH(txiter piter
, parentIters
) {
230 UpdateChild(piter
, it
, add
);
232 const int64_t updateCount
= (add
? 1 : -1);
233 const int64_t updateSize
= updateCount
* it
->GetTxSize();
234 const CAmount updateFee
= updateCount
* it
->GetFee();
235 BOOST_FOREACH(txiter ancestorIt
, setAncestors
) {
236 mapTx
.modify(ancestorIt
, update_descendant_state(updateSize
, updateFee
, updateCount
));
240 void CTxMemPool::UpdateChildrenForRemoval(txiter it
)
242 const setEntries
&setMemPoolChildren
= GetMemPoolChildren(it
);
243 BOOST_FOREACH(txiter updateIt
, setMemPoolChildren
) {
244 UpdateParent(updateIt
, it
, false);
248 void CTxMemPool::UpdateForRemoveFromMempool(const setEntries
&entriesToRemove
)
250 // For each entry, walk back all ancestors and decrement size associated with this
252 const uint64_t nNoLimit
= std::numeric_limits
<uint64_t>::max();
253 BOOST_FOREACH(txiter removeIt
, entriesToRemove
) {
254 setEntries setAncestors
;
255 const CTxMemPoolEntry
&entry
= *removeIt
;
257 // Since this is a tx that is already in the mempool, we can call CMPA
258 // with fSearchForParents = false. If the mempool is in a consistent
259 // state, then using true or false should both be correct, though false
260 // should be a bit faster.
261 // However, if we happen to be in the middle of processing a reorg, then
262 // the mempool can be in an inconsistent state. In this case, the set
263 // of ancestors reachable via mapLinks will be the same as the set of
264 // ancestors whose packages include this transaction, because when we
265 // add a new transaction to the mempool in addUnchecked(), we assume it
266 // has no children, and in the case of a reorg where that assumption is
267 // false, the in-mempool children aren't linked to the in-block tx's
268 // until UpdateTransactionsFromBlock() is called.
269 // So if we're being called during a reorg, ie before
270 // UpdateTransactionsFromBlock() has been called, then mapLinks[] will
271 // differ from the set of mempool parents we'd calculate by searching,
272 // and it's important that we use the mapLinks[] notion of ancestor
273 // transactions as the set of things to update for removal.
274 CalculateMemPoolAncestors(entry
, setAncestors
, nNoLimit
, nNoLimit
, nNoLimit
, nNoLimit
, dummy
, false);
275 // Note that UpdateAncestorsOf severs the child links that point to
276 // removeIt in the entries for the parents of removeIt. This is
277 // fine since we don't need to use the mempool children of any entries
278 // to walk back over our ancestors (but we do need the mempool
280 UpdateAncestorsOf(false, removeIt
, setAncestors
);
282 // After updating all the ancestor sizes, we can now sever the link between each
283 // transaction being removed and any mempool children (ie, update setMemPoolParents
284 // for each direct child of a transaction being removed).
285 BOOST_FOREACH(txiter removeIt
, entriesToRemove
) {
286 UpdateChildrenForRemoval(removeIt
);
290 void CTxMemPoolEntry::SetDirty()
292 nCountWithDescendants
= 0;
293 nSizeWithDescendants
= nTxSize
;
294 nFeesWithDescendants
= nFee
;
297 void CTxMemPoolEntry::UpdateState(int64_t modifySize
, CAmount modifyFee
, int64_t modifyCount
)
300 nSizeWithDescendants
+= modifySize
;
301 assert(int64_t(nSizeWithDescendants
) > 0);
302 nFeesWithDescendants
+= modifyFee
;
303 assert(nFeesWithDescendants
>= 0);
304 nCountWithDescendants
+= modifyCount
;
305 assert(int64_t(nCountWithDescendants
) > 0);
309 CTxMemPool::CTxMemPool(const CFeeRate
& _minReasonableRelayFee
) :
310 nTransactionsUpdated(0)
312 _clear(); //lock free clear
314 // Sanity checks off by default for performance, because otherwise
315 // accepting transactions becomes O(N^2) where N is the number
316 // of transactions in the pool
319 minerPolicyEstimator
= new CBlockPolicyEstimator(_minReasonableRelayFee
);
320 minReasonableRelayFee
= _minReasonableRelayFee
;
323 CTxMemPool::~CTxMemPool()
325 delete minerPolicyEstimator
;
328 void CTxMemPool::pruneSpent(const uint256
&hashTx
, CCoins
&coins
)
332 std::map
<COutPoint
, CInPoint
>::iterator it
= mapNextTx
.lower_bound(COutPoint(hashTx
, 0));
334 // iterate over all COutPoints in mapNextTx whose hash equals the provided hashTx
335 while (it
!= mapNextTx
.end() && it
->first
.hash
== hashTx
) {
336 coins
.Spend(it
->first
.n
); // and remove those outputs from coins
341 unsigned int CTxMemPool::GetTransactionsUpdated() const
344 return nTransactionsUpdated
;
347 void CTxMemPool::AddTransactionsUpdated(unsigned int n
)
350 nTransactionsUpdated
+= n
;
353 bool CTxMemPool::addUnchecked(const uint256
& hash
, const CTxMemPoolEntry
&entry
, setEntries
&setAncestors
, bool fCurrentEstimate
)
355 // Add to memory pool without checking anything.
356 // Used by main.cpp AcceptToMemoryPool(), which DOES do
357 // all the appropriate checks.
359 indexed_transaction_set::iterator newit
= mapTx
.insert(entry
).first
;
360 mapLinks
.insert(make_pair(newit
, TxLinks()));
362 // Update cachedInnerUsage to include contained transaction's usage.
363 // (When we update the entry for in-mempool parents, memory usage will be
365 cachedInnerUsage
+= entry
.DynamicMemoryUsage();
367 const CTransaction
& tx
= newit
->GetTx();
368 std::set
<uint256
> setParentTransactions
;
369 for (unsigned int i
= 0; i
< tx
.vin
.size(); i
++) {
370 mapNextTx
[tx
.vin
[i
].prevout
] = CInPoint(&tx
, i
);
371 setParentTransactions
.insert(tx
.vin
[i
].prevout
.hash
);
373 // Don't bother worrying about child transactions of this one.
374 // Normal case of a new transaction arriving is that there can't be any
375 // children, because such children would be orphans.
376 // An exception to that is if a transaction enters that used to be in a block.
377 // In that case, our disconnect block logic will call UpdateTransactionsFromBlock
378 // to clean up the mess we're leaving here.
380 // Update ancestors with information about this tx
381 BOOST_FOREACH (const uint256
&phash
, setParentTransactions
) {
382 txiter pit
= mapTx
.find(phash
);
383 if (pit
!= mapTx
.end()) {
384 UpdateParent(newit
, pit
, true);
387 UpdateAncestorsOf(true, newit
, setAncestors
);
389 nTransactionsUpdated
++;
390 totalTxSize
+= entry
.GetTxSize();
391 minerPolicyEstimator
->processTransaction(entry
, fCurrentEstimate
);
396 void CTxMemPool::removeUnchecked(txiter it
)
398 const uint256 hash
= it
->GetTx().GetHash();
399 BOOST_FOREACH(const CTxIn
& txin
, it
->GetTx().vin
)
400 mapNextTx
.erase(txin
.prevout
);
402 totalTxSize
-= it
->GetTxSize();
403 cachedInnerUsage
-= it
->DynamicMemoryUsage();
404 cachedInnerUsage
-= memusage::DynamicUsage(mapLinks
[it
].parents
) + memusage::DynamicUsage(mapLinks
[it
].children
);
407 nTransactionsUpdated
++;
408 minerPolicyEstimator
->removeTx(hash
);
411 // Calculates descendants of entry that are not already in setDescendants, and adds to
412 // setDescendants. Assumes entryit is already a tx in the mempool and setMemPoolChildren
413 // is correct for tx and all descendants.
414 // Also assumes that if an entry is in setDescendants already, then all
415 // in-mempool descendants of it are already in setDescendants as well, so that we
416 // can save time by not iterating over those entries.
417 void CTxMemPool::CalculateDescendants(txiter entryit
, setEntries
&setDescendants
)
420 if (setDescendants
.count(entryit
) == 0) {
421 stage
.insert(entryit
);
423 // Traverse down the children of entry, only adding children that are not
424 // accounted for in setDescendants already (because those children have either
425 // already been walked, or will be walked in this iteration).
426 while (!stage
.empty()) {
427 txiter it
= *stage
.begin();
428 setDescendants
.insert(it
);
431 const setEntries
&setChildren
= GetMemPoolChildren(it
);
432 BOOST_FOREACH(const txiter
&childiter
, setChildren
) {
433 if (!setDescendants
.count(childiter
)) {
434 stage
.insert(childiter
);
440 void CTxMemPool::remove(const CTransaction
&origTx
, std::list
<CTransaction
>& removed
, bool fRecursive
)
442 // Remove transaction from memory pool
445 setEntries txToRemove
;
446 txiter origit
= mapTx
.find(origTx
.GetHash());
447 if (origit
!= mapTx
.end()) {
448 txToRemove
.insert(origit
);
449 } else if (fRecursive
) {
450 // If recursively removing but origTx isn't in the mempool
451 // be sure to remove any children that are in the pool. This can
452 // happen during chain re-orgs if origTx isn't re-accepted into
453 // the mempool for any reason.
454 for (unsigned int i
= 0; i
< origTx
.vout
.size(); i
++) {
455 std::map
<COutPoint
, CInPoint
>::iterator it
= mapNextTx
.find(COutPoint(origTx
.GetHash(), i
));
456 if (it
== mapNextTx
.end())
458 txiter nextit
= mapTx
.find(it
->second
.ptx
->GetHash());
459 assert(nextit
!= mapTx
.end());
460 txToRemove
.insert(nextit
);
463 setEntries setAllRemoves
;
465 BOOST_FOREACH(txiter it
, txToRemove
) {
466 CalculateDescendants(it
, setAllRemoves
);
469 setAllRemoves
.swap(txToRemove
);
471 BOOST_FOREACH(txiter it
, setAllRemoves
) {
472 removed
.push_back(it
->GetTx());
474 RemoveStaged(setAllRemoves
);
478 void CTxMemPool::removeCoinbaseSpends(const CCoinsViewCache
*pcoins
, unsigned int nMemPoolHeight
)
480 // Remove transactions spending a coinbase which are now immature
482 list
<CTransaction
> transactionsToRemove
;
483 for (indexed_transaction_set::const_iterator it
= mapTx
.begin(); it
!= mapTx
.end(); it
++) {
484 const CTransaction
& tx
= it
->GetTx();
485 BOOST_FOREACH(const CTxIn
& txin
, tx
.vin
) {
486 indexed_transaction_set::const_iterator it2
= mapTx
.find(txin
.prevout
.hash
);
487 if (it2
!= mapTx
.end())
489 const CCoins
*coins
= pcoins
->AccessCoins(txin
.prevout
.hash
);
490 if (nCheckFrequency
!= 0) assert(coins
);
491 if (!coins
|| (coins
->IsCoinBase() && ((signed long)nMemPoolHeight
) - coins
->nHeight
< COINBASE_MATURITY
)) {
492 transactionsToRemove
.push_back(tx
);
497 BOOST_FOREACH(const CTransaction
& tx
, transactionsToRemove
) {
498 list
<CTransaction
> removed
;
499 remove(tx
, removed
, true);
503 void CTxMemPool::removeConflicts(const CTransaction
&tx
, std::list
<CTransaction
>& removed
)
505 // Remove transactions which depend on inputs of tx, recursively
506 list
<CTransaction
> result
;
508 BOOST_FOREACH(const CTxIn
&txin
, tx
.vin
) {
509 std::map
<COutPoint
, CInPoint
>::iterator it
= mapNextTx
.find(txin
.prevout
);
510 if (it
!= mapNextTx
.end()) {
511 const CTransaction
&txConflict
= *it
->second
.ptx
;
512 if (txConflict
!= tx
)
514 remove(txConflict
, removed
, true);
515 ClearPrioritisation(txConflict
.GetHash());
522 * Called when a block is connected. Removes from mempool and updates the miner fee estimator.
524 void CTxMemPool::removeForBlock(const std::vector
<CTransaction
>& vtx
, unsigned int nBlockHeight
,
525 std::list
<CTransaction
>& conflicts
, bool fCurrentEstimate
)
528 std::vector
<CTxMemPoolEntry
> entries
;
529 BOOST_FOREACH(const CTransaction
& tx
, vtx
)
531 uint256 hash
= tx
.GetHash();
533 indexed_transaction_set::iterator i
= mapTx
.find(hash
);
534 if (i
!= mapTx
.end())
535 entries
.push_back(*i
);
537 BOOST_FOREACH(const CTransaction
& tx
, vtx
)
539 std::list
<CTransaction
> dummy
;
540 remove(tx
, dummy
, false);
541 removeConflicts(tx
, conflicts
);
542 ClearPrioritisation(tx
.GetHash());
544 // After the txs in the new block have been removed from the mempool, update policy estimates
545 minerPolicyEstimator
->processBlock(nBlockHeight
, entries
, fCurrentEstimate
);
546 lastRollingFeeUpdate
= GetTime();
547 blockSinceLastRollingFeeBump
= true;
550 void CTxMemPool::_clear()
556 cachedInnerUsage
= 0;
557 lastRollingFeeUpdate
= GetTime();
558 blockSinceLastRollingFeeBump
= false;
559 rollingMinimumFeeRate
= 0;
560 ++nTransactionsUpdated
;
563 void CTxMemPool::clear()
569 void CTxMemPool::check(const CCoinsViewCache
*pcoins
) const
571 if (nCheckFrequency
== 0)
574 if (insecure_rand() >= nCheckFrequency
)
577 LogPrint("mempool", "Checking mempool with %u transactions and %u inputs\n", (unsigned int)mapTx
.size(), (unsigned int)mapNextTx
.size());
579 uint64_t checkTotal
= 0;
580 uint64_t innerUsage
= 0;
582 CCoinsViewCache
mempoolDuplicate(const_cast<CCoinsViewCache
*>(pcoins
));
585 list
<const CTxMemPoolEntry
*> waitingOnDependants
;
586 for (indexed_transaction_set::const_iterator it
= mapTx
.begin(); it
!= mapTx
.end(); it
++) {
588 checkTotal
+= it
->GetTxSize();
589 innerUsage
+= it
->DynamicMemoryUsage();
590 const CTransaction
& tx
= it
->GetTx();
591 txlinksMap::const_iterator linksiter
= mapLinks
.find(it
);
592 assert(linksiter
!= mapLinks
.end());
593 const TxLinks
&links
= linksiter
->second
;
594 innerUsage
+= memusage::DynamicUsage(links
.parents
) + memusage::DynamicUsage(links
.children
);
595 bool fDependsWait
= false;
596 setEntries setParentCheck
;
597 BOOST_FOREACH(const CTxIn
&txin
, tx
.vin
) {
598 // Check that every mempool transaction's inputs refer to available coins, or other mempool tx's.
599 indexed_transaction_set::const_iterator it2
= mapTx
.find(txin
.prevout
.hash
);
600 if (it2
!= mapTx
.end()) {
601 const CTransaction
& tx2
= it2
->GetTx();
602 assert(tx2
.vout
.size() > txin
.prevout
.n
&& !tx2
.vout
[txin
.prevout
.n
].IsNull());
604 setParentCheck
.insert(it2
);
606 const CCoins
* coins
= pcoins
->AccessCoins(txin
.prevout
.hash
);
607 assert(coins
&& coins
->IsAvailable(txin
.prevout
.n
));
609 // Check whether its inputs are marked in mapNextTx.
610 std::map
<COutPoint
, CInPoint
>::const_iterator it3
= mapNextTx
.find(txin
.prevout
);
611 assert(it3
!= mapNextTx
.end());
612 assert(it3
->second
.ptx
== &tx
);
613 assert(it3
->second
.n
== i
);
616 assert(setParentCheck
== GetMemPoolParents(it
));
617 // Check children against mapNextTx
618 CTxMemPool::setEntries setChildrenCheck
;
619 std::map
<COutPoint
, CInPoint
>::const_iterator iter
= mapNextTx
.lower_bound(COutPoint(it
->GetTx().GetHash(), 0));
620 int64_t childSizes
= 0;
621 CAmount childFees
= 0;
622 for (; iter
!= mapNextTx
.end() && iter
->first
.hash
== it
->GetTx().GetHash(); ++iter
) {
623 txiter childit
= mapTx
.find(iter
->second
.ptx
->GetHash());
624 assert(childit
!= mapTx
.end()); // mapNextTx points to in-mempool transactions
625 if (setChildrenCheck
.insert(childit
).second
) {
626 childSizes
+= childit
->GetTxSize();
627 childFees
+= childit
->GetFee();
630 assert(setChildrenCheck
== GetMemPoolChildren(it
));
631 // Also check to make sure size/fees is greater than sum with immediate children.
632 // just a sanity check, not definitive that this calc is correct...
633 // also check that the size is less than the size of the entire mempool.
634 if (!it
->IsDirty()) {
635 assert(it
->GetSizeWithDescendants() >= childSizes
+ it
->GetTxSize());
636 assert(it
->GetFeesWithDescendants() >= childFees
+ it
->GetFee());
638 assert(it
->GetSizeWithDescendants() == it
->GetTxSize());
639 assert(it
->GetFeesWithDescendants() == it
->GetFee());
641 assert(it
->GetFeesWithDescendants() >= 0);
644 waitingOnDependants
.push_back(&(*it
));
646 CValidationState state
;
647 assert(CheckInputs(tx
, state
, mempoolDuplicate
, false, 0, false, NULL
));
648 UpdateCoins(tx
, state
, mempoolDuplicate
, 1000000);
651 unsigned int stepsSinceLastRemove
= 0;
652 while (!waitingOnDependants
.empty()) {
653 const CTxMemPoolEntry
* entry
= waitingOnDependants
.front();
654 waitingOnDependants
.pop_front();
655 CValidationState state
;
656 if (!mempoolDuplicate
.HaveInputs(entry
->GetTx())) {
657 waitingOnDependants
.push_back(entry
);
658 stepsSinceLastRemove
++;
659 assert(stepsSinceLastRemove
< waitingOnDependants
.size());
661 assert(CheckInputs(entry
->GetTx(), state
, mempoolDuplicate
, false, 0, false, NULL
));
662 UpdateCoins(entry
->GetTx(), state
, mempoolDuplicate
, 1000000);
663 stepsSinceLastRemove
= 0;
666 for (std::map
<COutPoint
, CInPoint
>::const_iterator it
= mapNextTx
.begin(); it
!= mapNextTx
.end(); it
++) {
667 uint256 hash
= it
->second
.ptx
->GetHash();
668 indexed_transaction_set::const_iterator it2
= mapTx
.find(hash
);
669 const CTransaction
& tx
= it2
->GetTx();
670 assert(it2
!= mapTx
.end());
671 assert(&tx
== it
->second
.ptx
);
672 assert(tx
.vin
.size() > it
->second
.n
);
673 assert(it
->first
== it
->second
.ptx
->vin
[it
->second
.n
].prevout
);
676 assert(totalTxSize
== checkTotal
);
677 assert(innerUsage
== cachedInnerUsage
);
680 void CTxMemPool::queryHashes(vector
<uint256
>& vtxid
)
685 vtxid
.reserve(mapTx
.size());
686 for (indexed_transaction_set::iterator mi
= mapTx
.begin(); mi
!= mapTx
.end(); ++mi
)
687 vtxid
.push_back(mi
->GetTx().GetHash());
690 bool CTxMemPool::lookup(uint256 hash
, CTransaction
& result
) const
693 indexed_transaction_set::const_iterator i
= mapTx
.find(hash
);
694 if (i
== mapTx
.end()) return false;
699 CFeeRate
CTxMemPool::estimateFee(int nBlocks
) const
702 return minerPolicyEstimator
->estimateFee(nBlocks
);
704 CFeeRate
CTxMemPool::estimateSmartFee(int nBlocks
, int *answerFoundAtBlocks
) const
707 return minerPolicyEstimator
->estimateSmartFee(nBlocks
, answerFoundAtBlocks
, *this);
709 double CTxMemPool::estimatePriority(int nBlocks
) const
712 return minerPolicyEstimator
->estimatePriority(nBlocks
);
714 double CTxMemPool::estimateSmartPriority(int nBlocks
, int *answerFoundAtBlocks
) const
717 return minerPolicyEstimator
->estimateSmartPriority(nBlocks
, answerFoundAtBlocks
, *this);
721 CTxMemPool::WriteFeeEstimates(CAutoFile
& fileout
) const
725 fileout
<< 109900; // version required to read: 0.10.99 or later
726 fileout
<< CLIENT_VERSION
; // version that wrote the file
727 minerPolicyEstimator
->Write(fileout
);
729 catch (const std::exception
&) {
730 LogPrintf("CTxMemPool::WriteFeeEstimates(): unable to write policy estimator data (non-fatal)\n");
737 CTxMemPool::ReadFeeEstimates(CAutoFile
& filein
)
740 int nVersionRequired
, nVersionThatWrote
;
741 filein
>> nVersionRequired
>> nVersionThatWrote
;
742 if (nVersionRequired
> CLIENT_VERSION
)
743 return error("CTxMemPool::ReadFeeEstimates(): up-version (%d) fee estimate file", nVersionRequired
);
746 minerPolicyEstimator
->Read(filein
);
748 catch (const std::exception
&) {
749 LogPrintf("CTxMemPool::ReadFeeEstimates(): unable to read policy estimator data (non-fatal)\n");
755 void CTxMemPool::PrioritiseTransaction(const uint256 hash
, const string strHash
, double dPriorityDelta
, const CAmount
& nFeeDelta
)
759 std::pair
<double, CAmount
> &deltas
= mapDeltas
[hash
];
760 deltas
.first
+= dPriorityDelta
;
761 deltas
.second
+= nFeeDelta
;
763 LogPrintf("PrioritiseTransaction: %s priority += %f, fee += %d\n", strHash
, dPriorityDelta
, FormatMoney(nFeeDelta
));
766 void CTxMemPool::ApplyDeltas(const uint256 hash
, double &dPriorityDelta
, CAmount
&nFeeDelta
) const
769 std::map
<uint256
, std::pair
<double, CAmount
> >::const_iterator pos
= mapDeltas
.find(hash
);
770 if (pos
== mapDeltas
.end())
772 const std::pair
<double, CAmount
> &deltas
= pos
->second
;
773 dPriorityDelta
+= deltas
.first
;
774 nFeeDelta
+= deltas
.second
;
777 void CTxMemPool::ClearPrioritisation(const uint256 hash
)
780 mapDeltas
.erase(hash
);
783 bool CTxMemPool::HasNoInputsOf(const CTransaction
&tx
) const
785 for (unsigned int i
= 0; i
< tx
.vin
.size(); i
++)
786 if (exists(tx
.vin
[i
].prevout
.hash
))
791 CCoinsViewMemPool::CCoinsViewMemPool(CCoinsView
*baseIn
, CTxMemPool
&mempoolIn
) : CCoinsViewBacked(baseIn
), mempool(mempoolIn
) { }
793 bool CCoinsViewMemPool::GetCoins(const uint256
&txid
, CCoins
&coins
) const {
794 // If an entry in the mempool exists, always return that one, as it's guaranteed to never
795 // conflict with the underlying cache, and it cannot have pruned entries (as it contains full)
796 // transactions. First checking the underlying cache risks returning a pruned entry instead.
798 if (mempool
.lookup(txid
, tx
)) {
799 coins
= CCoins(tx
, MEMPOOL_HEIGHT
);
802 return (base
->GetCoins(txid
, coins
) && !coins
.IsPruned());
805 bool CCoinsViewMemPool::HaveCoins(const uint256
&txid
) const {
806 return mempool
.exists(txid
) || base
->HaveCoins(txid
);
809 size_t CTxMemPool::DynamicMemoryUsage() const {
811 // Estimate the overhead of mapTx to be 9 pointers + an allocation, as no exact formula for boost::multi_index_contained is implemented.
812 return memusage::MallocUsage(sizeof(CTxMemPoolEntry
) + 9 * sizeof(void*)) * mapTx
.size() + memusage::DynamicUsage(mapNextTx
) + memusage::DynamicUsage(mapDeltas
) + memusage::DynamicUsage(mapLinks
) + cachedInnerUsage
;
815 void CTxMemPool::RemoveStaged(setEntries
&stage
) {
817 UpdateForRemoveFromMempool(stage
);
818 BOOST_FOREACH(const txiter
& it
, stage
) {
823 int CTxMemPool::Expire(int64_t time
) {
825 indexed_transaction_set::nth_index
<2>::type::iterator it
= mapTx
.get
<2>().begin();
827 while (it
!= mapTx
.get
<2>().end() && it
->GetTime() < time
) {
828 toremove
.insert(mapTx
.project
<0>(it
));
832 BOOST_FOREACH(txiter removeit
, toremove
) {
833 CalculateDescendants(removeit
, stage
);
839 bool CTxMemPool::addUnchecked(const uint256
&hash
, const CTxMemPoolEntry
&entry
, bool fCurrentEstimate
)
842 setEntries setAncestors
;
843 uint64_t nNoLimit
= std::numeric_limits
<uint64_t>::max();
845 CalculateMemPoolAncestors(entry
, setAncestors
, nNoLimit
, nNoLimit
, nNoLimit
, nNoLimit
, dummy
);
846 return addUnchecked(hash
, entry
, setAncestors
, fCurrentEstimate
);
849 void CTxMemPool::UpdateChild(txiter entry
, txiter child
, bool add
)
852 if (add
&& mapLinks
[entry
].children
.insert(child
).second
) {
853 cachedInnerUsage
+= memusage::IncrementalDynamicUsage(s
);
854 } else if (!add
&& mapLinks
[entry
].children
.erase(child
)) {
855 cachedInnerUsage
-= memusage::IncrementalDynamicUsage(s
);
859 void CTxMemPool::UpdateParent(txiter entry
, txiter parent
, bool add
)
862 if (add
&& mapLinks
[entry
].parents
.insert(parent
).second
) {
863 cachedInnerUsage
+= memusage::IncrementalDynamicUsage(s
);
864 } else if (!add
&& mapLinks
[entry
].parents
.erase(parent
)) {
865 cachedInnerUsage
-= memusage::IncrementalDynamicUsage(s
);
869 const CTxMemPool::setEntries
& CTxMemPool::GetMemPoolParents(txiter entry
) const
871 assert (entry
!= mapTx
.end());
872 txlinksMap::const_iterator it
= mapLinks
.find(entry
);
873 assert(it
!= mapLinks
.end());
874 return it
->second
.parents
;
877 const CTxMemPool::setEntries
& CTxMemPool::GetMemPoolChildren(txiter entry
) const
879 assert (entry
!= mapTx
.end());
880 txlinksMap::const_iterator it
= mapLinks
.find(entry
);
881 assert(it
!= mapLinks
.end());
882 return it
->second
.children
;
885 CFeeRate
CTxMemPool::GetMinFee(size_t sizelimit
) const {
887 if (!blockSinceLastRollingFeeBump
|| rollingMinimumFeeRate
== 0)
888 return CFeeRate(rollingMinimumFeeRate
);
890 int64_t time
= GetTime();
891 if (time
> lastRollingFeeUpdate
+ 10) {
892 double halflife
= ROLLING_FEE_HALFLIFE
;
893 if (DynamicMemoryUsage() < sizelimit
/ 4)
895 else if (DynamicMemoryUsage() < sizelimit
/ 2)
898 rollingMinimumFeeRate
= rollingMinimumFeeRate
/ pow(2.0, (time
- lastRollingFeeUpdate
) / halflife
);
899 lastRollingFeeUpdate
= time
;
901 if (rollingMinimumFeeRate
< minReasonableRelayFee
.GetFeePerK() / 2) {
902 rollingMinimumFeeRate
= 0;
906 return std::max(CFeeRate(rollingMinimumFeeRate
), minReasonableRelayFee
);
909 void CTxMemPool::trackPackageRemoved(const CFeeRate
& rate
) {
911 if (rate
.GetFeePerK() > rollingMinimumFeeRate
) {
912 rollingMinimumFeeRate
= rate
.GetFeePerK();
913 blockSinceLastRollingFeeBump
= false;
917 void CTxMemPool::TrimToSize(size_t sizelimit
) {
920 unsigned nTxnRemoved
= 0;
921 CFeeRate
maxFeeRateRemoved(0);
922 while (DynamicMemoryUsage() > sizelimit
) {
923 indexed_transaction_set::nth_index
<1>::type::iterator it
= mapTx
.get
<1>().begin();
925 // We set the new mempool min fee to the feerate of the removed set, plus the
926 // "minimum reasonable fee rate" (ie some value under which we consider txn
927 // to have 0 fee). This way, we don't allow txn to enter mempool with feerate
928 // equal to txn which were removed with no block in between.
929 CFeeRate
removed(it
->GetFeesWithDescendants(), it
->GetSizeWithDescendants());
930 removed
+= minReasonableRelayFee
;
931 trackPackageRemoved(removed
);
932 maxFeeRateRemoved
= std::max(maxFeeRateRemoved
, removed
);
935 CalculateDescendants(mapTx
.project
<0>(it
), stage
);
937 nTxnRemoved
+= stage
.size();
940 if (maxFeeRateRemoved
> CFeeRate(0))
941 LogPrint("mempool", "Removed %u txn, rolling minimum fee bumped to %s\n", nTxnRemoved
, maxFeeRateRemoved
.ToString());