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"
20 CTxMemPoolEntry::CTxMemPoolEntry(const CTransaction
& _tx
, const CAmount
& _nFee
,
21 int64_t _nTime
, double _dPriority
,
22 unsigned int _nHeight
, bool poolHasNoInputsOf
):
23 tx(_tx
), nFee(_nFee
), nTime(_nTime
), dPriority(_dPriority
), nHeight(_nHeight
),
24 hadNoDependencies(poolHasNoInputsOf
)
26 nTxSize
= ::GetSerializeSize(tx
, SER_NETWORK
, PROTOCOL_VERSION
);
27 nModSize
= tx
.CalculateModifiedSize(nTxSize
);
28 nUsageSize
= RecursiveDynamicUsage(tx
);
30 nCountWithDescendants
= 1;
31 nSizeWithDescendants
= nTxSize
;
32 nFeesWithDescendants
= nFee
;
35 CTxMemPoolEntry::CTxMemPoolEntry(const CTxMemPoolEntry
& other
)
41 CTxMemPoolEntry::GetPriority(unsigned int currentHeight
) const
43 CAmount nValueIn
= tx
.GetValueOut()+nFee
;
44 double deltaPriority
= ((double)(currentHeight
-nHeight
)*nValueIn
)/nModSize
;
45 double dResult
= dPriority
+ deltaPriority
;
49 // Update the given tx for any in-mempool descendants.
50 // Assumes that setMemPoolChildren is correct for the given tx and all
52 bool CTxMemPool::UpdateForDescendants(txiter updateIt
, int maxDescendantsToVisit
, cacheMap
&cachedDescendants
, const std::set
<uint256
> &setExclude
)
54 // Track the number of entries (outside setExclude) that we'd need to visit
55 // (will bail out if it exceeds maxDescendantsToVisit)
56 int nChildrenToVisit
= 0;
58 setEntries stageEntries
, setAllDescendants
;
59 stageEntries
= GetMemPoolChildren(updateIt
);
61 while (!stageEntries
.empty()) {
62 const txiter cit
= *stageEntries
.begin();
64 // Don't consider any more children if any descendant is dirty
67 setAllDescendants
.insert(cit
);
68 stageEntries
.erase(cit
);
69 const setEntries
&setChildren
= GetMemPoolChildren(cit
);
70 BOOST_FOREACH(const txiter childEntry
, setChildren
) {
71 cacheMap::iterator cacheIt
= cachedDescendants
.find(childEntry
);
72 if (cacheIt
!= cachedDescendants
.end()) {
73 // We've already calculated this one, just add the entries for this set
74 // but don't traverse again.
75 BOOST_FOREACH(const txiter cacheEntry
, cacheIt
->second
) {
76 // update visit count only for new child transactions
77 // (outside of setExclude and stageEntries)
78 if (setAllDescendants
.insert(cacheEntry
).second
&&
79 !setExclude
.count(cacheEntry
->GetTx().GetHash()) &&
80 !stageEntries
.count(cacheEntry
)) {
84 } else if (!setAllDescendants
.count(childEntry
)) {
85 // Schedule for later processing and update our visit count
86 if (stageEntries
.insert(childEntry
).second
&& !setExclude
.count(childEntry
->GetTx().GetHash())) {
90 if (nChildrenToVisit
> maxDescendantsToVisit
) {
95 // setAllDescendants now contains all in-mempool descendants of updateIt.
96 // Update and add to cached descendant map
97 int64_t modifySize
= 0;
98 CAmount modifyFee
= 0;
99 int64_t modifyCount
= 0;
100 BOOST_FOREACH(txiter cit
, setAllDescendants
) {
101 if (!setExclude
.count(cit
->GetTx().GetHash())) {
102 modifySize
+= cit
->GetTxSize();
103 modifyFee
+= cit
->GetFee();
105 cachedDescendants
[updateIt
].insert(cit
);
108 mapTx
.modify(updateIt
, update_descendant_state(modifySize
, modifyFee
, modifyCount
));
112 // vHashesToUpdate is the set of transaction hashes from a disconnected block
113 // which has been re-added to the mempool.
114 // for each entry, look for descendants that are outside hashesToUpdate, and
115 // add fee/size information for such descendants to the parent.
116 void CTxMemPool::UpdateTransactionsFromBlock(const std::vector
<uint256
> &vHashesToUpdate
)
119 // For each entry in vHashesToUpdate, store the set of in-mempool, but not
120 // in-vHashesToUpdate transactions, so that we don't have to recalculate
121 // descendants when we come across a previously seen entry.
122 cacheMap mapMemPoolDescendantsToUpdate
;
124 // Use a set for lookups into vHashesToUpdate (these entries are already
125 // accounted for in the state of their ancestors)
126 std::set
<uint256
> setAlreadyIncluded(vHashesToUpdate
.begin(), vHashesToUpdate
.end());
128 // Iterate in reverse, so that whenever we are looking at at a transaction
129 // we are sure that all in-mempool descendants have already been processed.
130 // This maximizes the benefit of the descendant cache and guarantees that
131 // setMemPoolChildren will be updated, an assumption made in
132 // UpdateForDescendants.
133 BOOST_REVERSE_FOREACH(const uint256
&hash
, vHashesToUpdate
) {
134 // we cache the in-mempool children to avoid duplicate updates
135 setEntries setChildren
;
136 // calculate children from mapNextTx
137 txiter it
= mapTx
.find(hash
);
138 if (it
== mapTx
.end()) {
141 std::map
<COutPoint
, CInPoint
>::iterator iter
= mapNextTx
.lower_bound(COutPoint(hash
, 0));
142 // First calculate the children, and update setMemPoolChildren to
143 // include them, and update their setMemPoolParents to include this tx.
144 for (; iter
!= mapNextTx
.end() && iter
->first
.hash
== hash
; ++iter
) {
145 const uint256
&childHash
= iter
->second
.ptx
->GetHash();
146 txiter childIter
= mapTx
.find(childHash
);
147 assert(childIter
!= mapTx
.end());
148 // We can skip updating entries we've encountered before or that
149 // are in the block (which are already accounted for).
150 if (setChildren
.insert(childIter
).second
&& !setAlreadyIncluded
.count(childHash
)) {
151 UpdateChild(it
, childIter
, true);
152 UpdateParent(childIter
, it
, true);
155 if (!UpdateForDescendants(it
, 100, mapMemPoolDescendantsToUpdate
, setAlreadyIncluded
)) {
156 // Mark as dirty if we can't do the calculation.
157 mapTx
.modify(it
, set_dirty());
162 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 */)
164 setEntries parentHashes
;
165 const CTransaction
&tx
= entry
.GetTx();
167 if (fSearchForParents
) {
168 // Get parents of this transaction that are in the mempool
169 // GetMemPoolParents() is only valid for entries in the mempool, so we
170 // iterate mapTx to find parents.
171 for (unsigned int i
= 0; i
< tx
.vin
.size(); i
++) {
172 txiter piter
= mapTx
.find(tx
.vin
[i
].prevout
.hash
);
173 if (piter
!= mapTx
.end()) {
174 parentHashes
.insert(piter
);
175 if (parentHashes
.size() + 1 > limitAncestorCount
) {
176 errString
= strprintf("too many unconfirmed parents [limit: %u]", limitAncestorCount
);
182 // If we're not searching for parents, we require this to be an
183 // entry in the mempool already.
184 txiter it
= mapTx
.iterator_to(entry
);
185 parentHashes
= GetMemPoolParents(it
);
188 size_t totalSizeWithAncestors
= entry
.GetTxSize();
190 while (!parentHashes
.empty()) {
191 txiter stageit
= *parentHashes
.begin();
193 setAncestors
.insert(stageit
);
194 parentHashes
.erase(stageit
);
195 totalSizeWithAncestors
+= stageit
->GetTxSize();
197 if (stageit
->GetSizeWithDescendants() + entry
.GetTxSize() > limitDescendantSize
) {
198 errString
= strprintf("exceeds descendant size limit for tx %s [limit: %u]", stageit
->GetTx().GetHash().ToString(), limitDescendantSize
);
200 } else if (stageit
->GetCountWithDescendants() + 1 > limitDescendantCount
) {
201 errString
= strprintf("too many descendants for tx %s [limit: %u]", stageit
->GetTx().GetHash().ToString(), limitDescendantCount
);
203 } else if (totalSizeWithAncestors
> limitAncestorSize
) {
204 errString
= strprintf("exceeds ancestor size limit [limit: %u]", limitAncestorSize
);
208 const setEntries
& setMemPoolParents
= GetMemPoolParents(stageit
);
209 BOOST_FOREACH(const txiter
&phash
, setMemPoolParents
) {
210 // If this is a new ancestor, add it.
211 if (setAncestors
.count(phash
) == 0) {
212 parentHashes
.insert(phash
);
214 if (parentHashes
.size() + setAncestors
.size() + 1 > limitAncestorCount
) {
215 errString
= strprintf("too many unconfirmed ancestors [limit: %u]", limitAncestorCount
);
224 void CTxMemPool::UpdateAncestorsOf(bool add
, txiter it
, setEntries
&setAncestors
)
226 setEntries parentIters
= GetMemPoolParents(it
);
227 // add or remove this tx as a child of each parent
228 BOOST_FOREACH(txiter piter
, parentIters
) {
229 UpdateChild(piter
, it
, add
);
231 const int64_t updateCount
= (add
? 1 : -1);
232 const int64_t updateSize
= updateCount
* it
->GetTxSize();
233 const CAmount updateFee
= updateCount
* it
->GetFee();
234 BOOST_FOREACH(txiter ancestorIt
, setAncestors
) {
235 mapTx
.modify(ancestorIt
, update_descendant_state(updateSize
, updateFee
, updateCount
));
239 void CTxMemPool::UpdateChildrenForRemoval(txiter it
)
241 const setEntries
&setMemPoolChildren
= GetMemPoolChildren(it
);
242 BOOST_FOREACH(txiter updateIt
, setMemPoolChildren
) {
243 UpdateParent(updateIt
, it
, false);
247 void CTxMemPool::UpdateForRemoveFromMempool(const setEntries
&entriesToRemove
)
249 // For each entry, walk back all ancestors and decrement size associated with this
251 const uint64_t nNoLimit
= std::numeric_limits
<uint64_t>::max();
252 BOOST_FOREACH(txiter removeIt
, entriesToRemove
) {
253 setEntries setAncestors
;
254 const CTxMemPoolEntry
&entry
= *removeIt
;
256 // Since this is a tx that is already in the mempool, we can call CMPA
257 // with fSearchForParents = false. If the mempool is in a consistent
258 // state, then using true or false should both be correct, though false
259 // should be a bit faster.
260 // However, if we happen to be in the middle of processing a reorg, then
261 // the mempool can be in an inconsistent state. In this case, the set
262 // of ancestors reachable via mapLinks will be the same as the set of
263 // ancestors whose packages include this transaction, because when we
264 // add a new transaction to the mempool in addUnchecked(), we assume it
265 // has no children, and in the case of a reorg where that assumption is
266 // false, the in-mempool children aren't linked to the in-block tx's
267 // until UpdateTransactionsFromBlock() is called.
268 // So if we're being called during a reorg, ie before
269 // UpdateTransactionsFromBlock() has been called, then mapLinks[] will
270 // differ from the set of mempool parents we'd calculate by searching,
271 // and it's important that we use the mapLinks[] notion of ancestor
272 // transactions as the set of things to update for removal.
273 CalculateMemPoolAncestors(entry
, setAncestors
, nNoLimit
, nNoLimit
, nNoLimit
, nNoLimit
, dummy
, false);
274 // Note that UpdateAncestorsOf severs the child links that point to
275 // removeIt in the entries for the parents of removeIt. This is
276 // fine since we don't need to use the mempool children of any entries
277 // to walk back over our ancestors (but we do need the mempool
279 UpdateAncestorsOf(false, removeIt
, setAncestors
);
281 // After updating all the ancestor sizes, we can now sever the link between each
282 // transaction being removed and any mempool children (ie, update setMemPoolParents
283 // for each direct child of a transaction being removed).
284 BOOST_FOREACH(txiter removeIt
, entriesToRemove
) {
285 UpdateChildrenForRemoval(removeIt
);
289 void CTxMemPoolEntry::SetDirty()
291 nCountWithDescendants
= 0;
292 nSizeWithDescendants
= nTxSize
;
293 nFeesWithDescendants
= nFee
;
296 void CTxMemPoolEntry::UpdateState(int64_t modifySize
, CAmount modifyFee
, int64_t modifyCount
)
299 nSizeWithDescendants
+= modifySize
;
300 assert(int64_t(nSizeWithDescendants
) > 0);
301 nFeesWithDescendants
+= modifyFee
;
302 assert(nFeesWithDescendants
>= 0);
303 nCountWithDescendants
+= modifyCount
;
304 assert(int64_t(nCountWithDescendants
) > 0);
308 CTxMemPool::CTxMemPool(const CFeeRate
& _minRelayFee
) :
309 nTransactionsUpdated(0)
311 // Sanity checks off by default for performance, because otherwise
312 // accepting transactions becomes O(N^2) where N is the number
313 // of transactions in the pool
314 fSanityCheck
= false;
316 minerPolicyEstimator
= new CBlockPolicyEstimator(_minRelayFee
);
319 CTxMemPool::~CTxMemPool()
321 delete minerPolicyEstimator
;
324 void CTxMemPool::pruneSpent(const uint256
&hashTx
, CCoins
&coins
)
328 std::map
<COutPoint
, CInPoint
>::iterator it
= mapNextTx
.lower_bound(COutPoint(hashTx
, 0));
330 // iterate over all COutPoints in mapNextTx whose hash equals the provided hashTx
331 while (it
!= mapNextTx
.end() && it
->first
.hash
== hashTx
) {
332 coins
.Spend(it
->first
.n
); // and remove those outputs from coins
337 unsigned int CTxMemPool::GetTransactionsUpdated() const
340 return nTransactionsUpdated
;
343 void CTxMemPool::AddTransactionsUpdated(unsigned int n
)
346 nTransactionsUpdated
+= n
;
349 bool CTxMemPool::addUnchecked(const uint256
& hash
, const CTxMemPoolEntry
&entry
, setEntries
&setAncestors
, bool fCurrentEstimate
)
351 // Add to memory pool without checking anything.
352 // Used by main.cpp AcceptToMemoryPool(), which DOES do
353 // all the appropriate checks.
355 indexed_transaction_set::iterator newit
= mapTx
.insert(entry
).first
;
356 mapLinks
.insert(make_pair(newit
, TxLinks()));
358 // Update cachedInnerUsage to include contained transaction's usage.
359 // (When we update the entry for in-mempool parents, memory usage will be
361 cachedInnerUsage
+= entry
.DynamicMemoryUsage();
363 const CTransaction
& tx
= newit
->GetTx();
364 std::set
<uint256
> setParentTransactions
;
365 for (unsigned int i
= 0; i
< tx
.vin
.size(); i
++) {
366 mapNextTx
[tx
.vin
[i
].prevout
] = CInPoint(&tx
, i
);
367 setParentTransactions
.insert(tx
.vin
[i
].prevout
.hash
);
369 // Don't bother worrying about child transactions of this one.
370 // Normal case of a new transaction arriving is that there can't be any
371 // children, because such children would be orphans.
372 // An exception to that is if a transaction enters that used to be in a block.
373 // In that case, our disconnect block logic will call UpdateTransactionsFromBlock
374 // to clean up the mess we're leaving here.
376 // Update ancestors with information about this tx
377 BOOST_FOREACH (const uint256
&phash
, setParentTransactions
) {
378 txiter pit
= mapTx
.find(phash
);
379 if (pit
!= mapTx
.end()) {
380 UpdateParent(newit
, pit
, true);
383 UpdateAncestorsOf(true, newit
, setAncestors
);
385 nTransactionsUpdated
++;
386 totalTxSize
+= entry
.GetTxSize();
387 minerPolicyEstimator
->processTransaction(entry
, fCurrentEstimate
);
392 void CTxMemPool::removeUnchecked(txiter it
)
394 const uint256 hash
= it
->GetTx().GetHash();
395 BOOST_FOREACH(const CTxIn
& txin
, it
->GetTx().vin
)
396 mapNextTx
.erase(txin
.prevout
);
398 totalTxSize
-= it
->GetTxSize();
399 cachedInnerUsage
-= it
->DynamicMemoryUsage();
400 cachedInnerUsage
-= memusage::DynamicUsage(mapLinks
[it
].parents
) + memusage::DynamicUsage(mapLinks
[it
].children
);
403 nTransactionsUpdated
++;
404 minerPolicyEstimator
->removeTx(hash
);
407 // Calculates descendants of entry that are not already in setDescendants, and adds to
408 // setDescendants. Assumes entryit is already a tx in the mempool and setMemPoolChildren
409 // is correct for tx and all descendants.
410 // Also assumes that if an entry is in setDescendants already, then all
411 // in-mempool descendants of it are already in setDescendants as well, so that we
412 // can save time by not iterating over those entries.
413 void CTxMemPool::CalculateDescendants(txiter entryit
, setEntries
&setDescendants
)
416 if (setDescendants
.count(entryit
) == 0) {
417 stage
.insert(entryit
);
419 // Traverse down the children of entry, only adding children that are not
420 // accounted for in setDescendants already (because those children have either
421 // already been walked, or will be walked in this iteration).
422 while (!stage
.empty()) {
423 txiter it
= *stage
.begin();
424 setDescendants
.insert(it
);
427 const setEntries
&setChildren
= GetMemPoolChildren(it
);
428 BOOST_FOREACH(const txiter
&childiter
, setChildren
) {
429 if (!setDescendants
.count(childiter
)) {
430 stage
.insert(childiter
);
436 void CTxMemPool::remove(const CTransaction
&origTx
, std::list
<CTransaction
>& removed
, bool fRecursive
)
438 // Remove transaction from memory pool
441 setEntries txToRemove
;
442 txiter origit
= mapTx
.find(origTx
.GetHash());
443 if (origit
!= mapTx
.end()) {
444 txToRemove
.insert(origit
);
445 } else if (fRecursive
) {
446 // If recursively removing but origTx isn't in the mempool
447 // be sure to remove any children that are in the pool. This can
448 // happen during chain re-orgs if origTx isn't re-accepted into
449 // the mempool for any reason.
450 for (unsigned int i
= 0; i
< origTx
.vout
.size(); i
++) {
451 std::map
<COutPoint
, CInPoint
>::iterator it
= mapNextTx
.find(COutPoint(origTx
.GetHash(), i
));
452 if (it
== mapNextTx
.end())
454 txiter nextit
= mapTx
.find(it
->second
.ptx
->GetHash());
455 assert(nextit
!= mapTx
.end());
456 txToRemove
.insert(nextit
);
459 setEntries setAllRemoves
;
461 BOOST_FOREACH(txiter it
, txToRemove
) {
462 CalculateDescendants(it
, setAllRemoves
);
465 setAllRemoves
.swap(txToRemove
);
467 BOOST_FOREACH(txiter it
, setAllRemoves
) {
468 removed
.push_back(it
->GetTx());
470 RemoveStaged(setAllRemoves
);
474 void CTxMemPool::removeCoinbaseSpends(const CCoinsViewCache
*pcoins
, unsigned int nMemPoolHeight
)
476 // Remove transactions spending a coinbase which are now immature
478 list
<CTransaction
> transactionsToRemove
;
479 for (indexed_transaction_set::const_iterator it
= mapTx
.begin(); it
!= mapTx
.end(); it
++) {
480 const CTransaction
& tx
= it
->GetTx();
481 BOOST_FOREACH(const CTxIn
& txin
, tx
.vin
) {
482 indexed_transaction_set::const_iterator it2
= mapTx
.find(txin
.prevout
.hash
);
483 if (it2
!= mapTx
.end())
485 const CCoins
*coins
= pcoins
->AccessCoins(txin
.prevout
.hash
);
486 if (fSanityCheck
) assert(coins
);
487 if (!coins
|| (coins
->IsCoinBase() && ((signed long)nMemPoolHeight
) - coins
->nHeight
< COINBASE_MATURITY
)) {
488 transactionsToRemove
.push_back(tx
);
493 BOOST_FOREACH(const CTransaction
& tx
, transactionsToRemove
) {
494 list
<CTransaction
> removed
;
495 remove(tx
, removed
, true);
499 void CTxMemPool::removeConflicts(const CTransaction
&tx
, std::list
<CTransaction
>& removed
)
501 // Remove transactions which depend on inputs of tx, recursively
502 list
<CTransaction
> result
;
504 BOOST_FOREACH(const CTxIn
&txin
, tx
.vin
) {
505 std::map
<COutPoint
, CInPoint
>::iterator it
= mapNextTx
.find(txin
.prevout
);
506 if (it
!= mapNextTx
.end()) {
507 const CTransaction
&txConflict
= *it
->second
.ptx
;
508 if (txConflict
!= tx
)
510 remove(txConflict
, removed
, true);
517 * Called when a block is connected. Removes from mempool and updates the miner fee estimator.
519 void CTxMemPool::removeForBlock(const std::vector
<CTransaction
>& vtx
, unsigned int nBlockHeight
,
520 std::list
<CTransaction
>& conflicts
, bool fCurrentEstimate
)
523 std::vector
<CTxMemPoolEntry
> entries
;
524 BOOST_FOREACH(const CTransaction
& tx
, vtx
)
526 uint256 hash
= tx
.GetHash();
528 indexed_transaction_set::iterator i
= mapTx
.find(hash
);
529 if (i
!= mapTx
.end())
530 entries
.push_back(*i
);
532 BOOST_FOREACH(const CTransaction
& tx
, vtx
)
534 std::list
<CTransaction
> dummy
;
535 remove(tx
, dummy
, false);
536 removeConflicts(tx
, conflicts
);
537 ClearPrioritisation(tx
.GetHash());
539 // After the txs in the new block have been removed from the mempool, update policy estimates
540 minerPolicyEstimator
->processBlock(nBlockHeight
, entries
, fCurrentEstimate
);
543 void CTxMemPool::clear()
550 cachedInnerUsage
= 0;
551 ++nTransactionsUpdated
;
554 void CTxMemPool::check(const CCoinsViewCache
*pcoins
) const
559 LogPrint("mempool", "Checking mempool with %u transactions and %u inputs\n", (unsigned int)mapTx
.size(), (unsigned int)mapNextTx
.size());
561 uint64_t checkTotal
= 0;
562 uint64_t innerUsage
= 0;
564 CCoinsViewCache
mempoolDuplicate(const_cast<CCoinsViewCache
*>(pcoins
));
567 list
<const CTxMemPoolEntry
*> waitingOnDependants
;
568 for (indexed_transaction_set::const_iterator it
= mapTx
.begin(); it
!= mapTx
.end(); it
++) {
570 checkTotal
+= it
->GetTxSize();
571 innerUsage
+= it
->DynamicMemoryUsage();
572 const CTransaction
& tx
= it
->GetTx();
573 txlinksMap::const_iterator linksiter
= mapLinks
.find(it
);
574 assert(linksiter
!= mapLinks
.end());
575 const TxLinks
&links
= linksiter
->second
;
576 innerUsage
+= memusage::DynamicUsage(links
.parents
) + memusage::DynamicUsage(links
.children
);
577 bool fDependsWait
= false;
578 setEntries setParentCheck
;
579 BOOST_FOREACH(const CTxIn
&txin
, tx
.vin
) {
580 // Check that every mempool transaction's inputs refer to available coins, or other mempool tx's.
581 indexed_transaction_set::const_iterator it2
= mapTx
.find(txin
.prevout
.hash
);
582 if (it2
!= mapTx
.end()) {
583 const CTransaction
& tx2
= it2
->GetTx();
584 assert(tx2
.vout
.size() > txin
.prevout
.n
&& !tx2
.vout
[txin
.prevout
.n
].IsNull());
586 setParentCheck
.insert(it2
);
588 const CCoins
* coins
= pcoins
->AccessCoins(txin
.prevout
.hash
);
589 assert(coins
&& coins
->IsAvailable(txin
.prevout
.n
));
591 // Check whether its inputs are marked in mapNextTx.
592 std::map
<COutPoint
, CInPoint
>::const_iterator it3
= mapNextTx
.find(txin
.prevout
);
593 assert(it3
!= mapNextTx
.end());
594 assert(it3
->second
.ptx
== &tx
);
595 assert(it3
->second
.n
== i
);
598 assert(setParentCheck
== GetMemPoolParents(it
));
599 // Check children against mapNextTx
600 CTxMemPool::setEntries setChildrenCheck
;
601 std::map
<COutPoint
, CInPoint
>::const_iterator iter
= mapNextTx
.lower_bound(COutPoint(it
->GetTx().GetHash(), 0));
602 int64_t childSizes
= 0;
603 CAmount childFees
= 0;
604 for (; iter
!= mapNextTx
.end() && iter
->first
.hash
== it
->GetTx().GetHash(); ++iter
) {
605 txiter childit
= mapTx
.find(iter
->second
.ptx
->GetHash());
606 assert(childit
!= mapTx
.end()); // mapNextTx points to in-mempool transactions
607 if (setChildrenCheck
.insert(childit
).second
) {
608 childSizes
+= childit
->GetTxSize();
609 childFees
+= childit
->GetFee();
612 assert(setChildrenCheck
== GetMemPoolChildren(it
));
613 // Also check to make sure size/fees is greater than sum with immediate children.
614 // just a sanity check, not definitive that this calc is correct...
615 // also check that the size is less than the size of the entire mempool.
616 if (!it
->IsDirty()) {
617 assert(it
->GetSizeWithDescendants() >= childSizes
+ it
->GetTxSize());
618 assert(it
->GetFeesWithDescendants() >= childFees
+ it
->GetFee());
620 assert(it
->GetSizeWithDescendants() == it
->GetTxSize());
621 assert(it
->GetFeesWithDescendants() == it
->GetFee());
623 assert(it
->GetFeesWithDescendants() >= 0);
626 waitingOnDependants
.push_back(&(*it
));
628 CValidationState state
;
629 assert(CheckInputs(tx
, state
, mempoolDuplicate
, false, 0, false, NULL
));
630 UpdateCoins(tx
, state
, mempoolDuplicate
, 1000000);
633 unsigned int stepsSinceLastRemove
= 0;
634 while (!waitingOnDependants
.empty()) {
635 const CTxMemPoolEntry
* entry
= waitingOnDependants
.front();
636 waitingOnDependants
.pop_front();
637 CValidationState state
;
638 if (!mempoolDuplicate
.HaveInputs(entry
->GetTx())) {
639 waitingOnDependants
.push_back(entry
);
640 stepsSinceLastRemove
++;
641 assert(stepsSinceLastRemove
< waitingOnDependants
.size());
643 assert(CheckInputs(entry
->GetTx(), state
, mempoolDuplicate
, false, 0, false, NULL
));
644 UpdateCoins(entry
->GetTx(), state
, mempoolDuplicate
, 1000000);
645 stepsSinceLastRemove
= 0;
648 for (std::map
<COutPoint
, CInPoint
>::const_iterator it
= mapNextTx
.begin(); it
!= mapNextTx
.end(); it
++) {
649 uint256 hash
= it
->second
.ptx
->GetHash();
650 indexed_transaction_set::const_iterator it2
= mapTx
.find(hash
);
651 const CTransaction
& tx
= it2
->GetTx();
652 assert(it2
!= mapTx
.end());
653 assert(&tx
== it
->second
.ptx
);
654 assert(tx
.vin
.size() > it
->second
.n
);
655 assert(it
->first
== it
->second
.ptx
->vin
[it
->second
.n
].prevout
);
658 assert(totalTxSize
== checkTotal
);
659 assert(innerUsage
== cachedInnerUsage
);
662 void CTxMemPool::queryHashes(vector
<uint256
>& vtxid
)
667 vtxid
.reserve(mapTx
.size());
668 for (indexed_transaction_set::iterator mi
= mapTx
.begin(); mi
!= mapTx
.end(); ++mi
)
669 vtxid
.push_back(mi
->GetTx().GetHash());
672 bool CTxMemPool::lookup(uint256 hash
, CTransaction
& result
) const
675 indexed_transaction_set::const_iterator i
= mapTx
.find(hash
);
676 if (i
== mapTx
.end()) return false;
681 CFeeRate
CTxMemPool::estimateFee(int nBlocks
) const
684 return minerPolicyEstimator
->estimateFee(nBlocks
);
686 double CTxMemPool::estimatePriority(int nBlocks
) const
689 return minerPolicyEstimator
->estimatePriority(nBlocks
);
693 CTxMemPool::WriteFeeEstimates(CAutoFile
& fileout
) const
697 fileout
<< 109900; // version required to read: 0.10.99 or later
698 fileout
<< CLIENT_VERSION
; // version that wrote the file
699 minerPolicyEstimator
->Write(fileout
);
701 catch (const std::exception
&) {
702 LogPrintf("CTxMemPool::WriteFeeEstimates(): unable to write policy estimator data (non-fatal)\n");
709 CTxMemPool::ReadFeeEstimates(CAutoFile
& filein
)
712 int nVersionRequired
, nVersionThatWrote
;
713 filein
>> nVersionRequired
>> nVersionThatWrote
;
714 if (nVersionRequired
> CLIENT_VERSION
)
715 return error("CTxMemPool::ReadFeeEstimates(): up-version (%d) fee estimate file", nVersionRequired
);
718 minerPolicyEstimator
->Read(filein
);
720 catch (const std::exception
&) {
721 LogPrintf("CTxMemPool::ReadFeeEstimates(): unable to read policy estimator data (non-fatal)\n");
727 void CTxMemPool::PrioritiseTransaction(const uint256 hash
, const string strHash
, double dPriorityDelta
, const CAmount
& nFeeDelta
)
731 std::pair
<double, CAmount
> &deltas
= mapDeltas
[hash
];
732 deltas
.first
+= dPriorityDelta
;
733 deltas
.second
+= nFeeDelta
;
735 LogPrintf("PrioritiseTransaction: %s priority += %f, fee += %d\n", strHash
, dPriorityDelta
, FormatMoney(nFeeDelta
));
738 void CTxMemPool::ApplyDeltas(const uint256 hash
, double &dPriorityDelta
, CAmount
&nFeeDelta
) const
741 std::map
<uint256
, std::pair
<double, CAmount
> >::const_iterator pos
= mapDeltas
.find(hash
);
742 if (pos
== mapDeltas
.end())
744 const std::pair
<double, CAmount
> &deltas
= pos
->second
;
745 dPriorityDelta
+= deltas
.first
;
746 nFeeDelta
+= deltas
.second
;
749 void CTxMemPool::ClearPrioritisation(const uint256 hash
)
752 mapDeltas
.erase(hash
);
755 bool CTxMemPool::HasNoInputsOf(const CTransaction
&tx
) const
757 for (unsigned int i
= 0; i
< tx
.vin
.size(); i
++)
758 if (exists(tx
.vin
[i
].prevout
.hash
))
763 CCoinsViewMemPool::CCoinsViewMemPool(CCoinsView
*baseIn
, CTxMemPool
&mempoolIn
) : CCoinsViewBacked(baseIn
), mempool(mempoolIn
) { }
765 bool CCoinsViewMemPool::GetCoins(const uint256
&txid
, CCoins
&coins
) const {
766 // If an entry in the mempool exists, always return that one, as it's guaranteed to never
767 // conflict with the underlying cache, and it cannot have pruned entries (as it contains full)
768 // transactions. First checking the underlying cache risks returning a pruned entry instead.
770 if (mempool
.lookup(txid
, tx
)) {
771 coins
= CCoins(tx
, MEMPOOL_HEIGHT
);
774 return (base
->GetCoins(txid
, coins
) && !coins
.IsPruned());
777 bool CCoinsViewMemPool::HaveCoins(const uint256
&txid
) const {
778 return mempool
.exists(txid
) || base
->HaveCoins(txid
);
781 size_t CTxMemPool::DynamicMemoryUsage() const {
783 // Estimate the overhead of mapTx to be 9 pointers + an allocation, as no exact formula for boost::multi_index_contained is implemented.
784 return memusage::MallocUsage(sizeof(CTxMemPoolEntry
) + 9 * sizeof(void*)) * mapTx
.size() + memusage::DynamicUsage(mapNextTx
) + memusage::DynamicUsage(mapDeltas
) + memusage::DynamicUsage(mapLinks
) + cachedInnerUsage
;
787 void CTxMemPool::RemoveStaged(setEntries
&stage
) {
789 UpdateForRemoveFromMempool(stage
);
790 BOOST_FOREACH(const txiter
& it
, stage
) {
795 int CTxMemPool::Expire(int64_t time
) {
797 indexed_transaction_set::nth_index
<2>::type::iterator it
= mapTx
.get
<2>().begin();
799 while (it
!= mapTx
.get
<2>().end() && it
->GetTime() < time
) {
800 toremove
.insert(mapTx
.project
<0>(it
));
804 BOOST_FOREACH(txiter removeit
, toremove
) {
805 CalculateDescendants(removeit
, stage
);
811 bool CTxMemPool::addUnchecked(const uint256
&hash
, const CTxMemPoolEntry
&entry
, bool fCurrentEstimate
)
814 setEntries setAncestors
;
815 uint64_t nNoLimit
= std::numeric_limits
<uint64_t>::max();
817 CalculateMemPoolAncestors(entry
, setAncestors
, nNoLimit
, nNoLimit
, nNoLimit
, nNoLimit
, dummy
);
818 return addUnchecked(hash
, entry
, setAncestors
, fCurrentEstimate
);
821 void CTxMemPool::UpdateChild(txiter entry
, txiter child
, bool add
)
824 if (add
&& mapLinks
[entry
].children
.insert(child
).second
) {
825 cachedInnerUsage
+= memusage::IncrementalDynamicUsage(s
);
826 } else if (!add
&& mapLinks
[entry
].children
.erase(child
)) {
827 cachedInnerUsage
-= memusage::IncrementalDynamicUsage(s
);
831 void CTxMemPool::UpdateParent(txiter entry
, txiter parent
, bool add
)
834 if (add
&& mapLinks
[entry
].parents
.insert(parent
).second
) {
835 cachedInnerUsage
+= memusage::IncrementalDynamicUsage(s
);
836 } else if (!add
&& mapLinks
[entry
].parents
.erase(parent
)) {
837 cachedInnerUsage
-= memusage::IncrementalDynamicUsage(s
);
841 const CTxMemPool::setEntries
& CTxMemPool::GetMemPoolParents(txiter entry
) const
843 assert (entry
!= mapTx
.end());
844 txlinksMap::const_iterator it
= mapLinks
.find(entry
);
845 assert(it
!= mapLinks
.end());
846 return it
->second
.parents
;
849 const CTxMemPool::setEntries
& CTxMemPool::GetMemPoolChildren(txiter entry
) const
851 assert (entry
!= mapTx
.end());
852 txlinksMap::const_iterator it
= mapLinks
.find(entry
);
853 assert(it
!= mapLinks
.end());
854 return it
->second
.children
;