1 // Copyright (c) 2009-2010 Satoshi Nakamoto
2 // Copyright (c) 2009-2018 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.
5
6 #include <txmempool.h>
7
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>
14 #include <reverse_iterator.h>
15 #include <streams.h>
16 #include <timedata.h>
17 #include <util/system.h>
18 #include <util/moneystr.h>
19 #include <util/time.h>
20
CTxMemPoolEntry(const CTransactionRef & _tx,const CAmount & _nFee,int64_t _nTime,unsigned int _entryHeight,bool _spendsCoinbase,int64_t _sigOpsCost,LockPoints lp)21 CTxMemPoolEntry::CTxMemPoolEntry(const CTransactionRef& _tx, const CAmount& _nFee,
22 int64_t _nTime, unsigned int _entryHeight,
23 bool _spendsCoinbase, int64_t _sigOpsCost, LockPoints lp)
24 : tx(_tx), nFee(_nFee), nTxWeight(GetTransactionWeight(*tx)), nUsageSize(RecursiveDynamicUsage(tx)), nTime(_nTime), entryHeight(_entryHeight),
25 spendsCoinbase(_spendsCoinbase), sigOpCost(_sigOpsCost), lockPoints(lp)
26 {
27 nCountWithDescendants = 1;
28 nSizeWithDescendants = GetTxSize();
29 nModFeesWithDescendants = nFee;
30
31 feeDelta = 0;
32
33 nCountWithAncestors = 1;
34 nSizeWithAncestors = GetTxSize();
35 nModFeesWithAncestors = nFee;
36 nSigOpCostWithAncestors = sigOpCost;
37 }
38
UpdateFeeDelta(int64_t newFeeDelta)39 void CTxMemPoolEntry::UpdateFeeDelta(int64_t newFeeDelta)
40 {
41 nModFeesWithDescendants += newFeeDelta - feeDelta;
42 nModFeesWithAncestors += newFeeDelta - feeDelta;
43 feeDelta = newFeeDelta;
44 }
45
UpdateLockPoints(const LockPoints & lp)46 void CTxMemPoolEntry::UpdateLockPoints(const LockPoints& lp)
47 {
48 lockPoints = lp;
49 }
50
GetTxSize() const51 size_t CTxMemPoolEntry::GetTxSize() const
52 {
53 return GetVirtualTransactionSize(nTxWeight, sigOpCost);
54 }
55
56 // Update the given tx for any in-mempool descendants.
57 // Assumes that setMemPoolChildren is correct for the given tx and all
58 // descendants.
UpdateForDescendants(txiter updateIt,cacheMap & cachedDescendants,const std::set<uint256> & setExclude)59 void CTxMemPool::UpdateForDescendants(txiter updateIt, cacheMap &cachedDescendants, const std::set<uint256> &setExclude)
60 {
61 setEntries stageEntries, setAllDescendants;
62 stageEntries = GetMemPoolChildren(updateIt);
63
64 while (!stageEntries.empty()) {
65 const txiter cit = *stageEntries.begin();
66 setAllDescendants.insert(cit);
67 stageEntries.erase(cit);
68 const setEntries &setChildren = GetMemPoolChildren(cit);
69 for (txiter childEntry : setChildren) {
70 cacheMap::iterator cacheIt = cachedDescendants.find(childEntry);
71 if (cacheIt != cachedDescendants.end()) {
72 // We've already calculated this one, just add the entries for this set
73 // but don't traverse again.
74 for (txiter cacheEntry : cacheIt->second) {
75 setAllDescendants.insert(cacheEntry);
76 }
77 } else if (!setAllDescendants.count(childEntry)) {
78 // Schedule for later processing
79 stageEntries.insert(childEntry);
80 }
81 }
82 }
83 // setAllDescendants now contains all in-mempool descendants of updateIt.
84 // Update and add to cached descendant map
85 int64_t modifySize = 0;
86 CAmount modifyFee = 0;
87 int64_t modifyCount = 0;
88 for (txiter cit : setAllDescendants) {
89 if (!setExclude.count(cit->GetTx().GetHash())) {
90 modifySize += cit->GetTxSize();
91 modifyFee += cit->GetModifiedFee();
92 modifyCount++;
93 cachedDescendants[updateIt].insert(cit);
94 // Update ancestor state for each descendant
95 mapTx.modify(cit, update_ancestor_state(updateIt->GetTxSize(), updateIt->GetModifiedFee(), 1, updateIt->GetSigOpCost()));
96 }
97 }
98 mapTx.modify(updateIt, update_descendant_state(modifySize, modifyFee, modifyCount));
99 }
100
101 // vHashesToUpdate is the set of transaction hashes from a disconnected block
102 // which has been re-added to the mempool.
103 // for each entry, look for descendants that are outside vHashesToUpdate, and
104 // add fee/size information for such descendants to the parent.
105 // for each such descendant, also update the ancestor state to include the parent.
UpdateTransactionsFromBlock(const std::vector<uint256> & vHashesToUpdate)106 void CTxMemPool::UpdateTransactionsFromBlock(const std::vector<uint256> &vHashesToUpdate)
107 {
108 LOCK(cs);
109 // For each entry in vHashesToUpdate, store the set of in-mempool, but not
110 // in-vHashesToUpdate transactions, so that we don't have to recalculate
111 // descendants when we come across a previously seen entry.
112 cacheMap mapMemPoolDescendantsToUpdate;
113
114 // Use a set for lookups into vHashesToUpdate (these entries are already
115 // accounted for in the state of their ancestors)
116 std::set<uint256> setAlreadyIncluded(vHashesToUpdate.begin(), vHashesToUpdate.end());
117
118 // Iterate in reverse, so that whenever we are looking at a transaction
119 // we are sure that all in-mempool descendants have already been processed.
120 // This maximizes the benefit of the descendant cache and guarantees that
121 // setMemPoolChildren will be updated, an assumption made in
122 // UpdateForDescendants.
123 for (const uint256 &hash : reverse_iterate(vHashesToUpdate)) {
124 // we cache the in-mempool children to avoid duplicate updates
125 setEntries setChildren;
126 // calculate children from mapNextTx
127 txiter it = mapTx.find(hash);
128 if (it == mapTx.end()) {
129 continue;
130 }
131 auto iter = mapNextTx.lower_bound(COutPoint(hash, 0));
132 // First calculate the children, and update setMemPoolChildren to
133 // include them, and update their setMemPoolParents to include this tx.
134 for (; iter != mapNextTx.end() && iter->first->hash == hash; ++iter) {
135 const uint256 &childHash = iter->second->GetHash();
136 txiter childIter = mapTx.find(childHash);
137 assert(childIter != mapTx.end());
138 // We can skip updating entries we've encountered before or that
139 // are in the block (which are already accounted for).
140 if (setChildren.insert(childIter).second && !setAlreadyIncluded.count(childHash)) {
141 UpdateChild(it, childIter, true);
142 UpdateParent(childIter, it, true);
143 }
144 }
145 UpdateForDescendants(it, mapMemPoolDescendantsToUpdate, setAlreadyIncluded);
146 }
147 }
148
CalculateMemPoolAncestors(const CTxMemPoolEntry & entry,setEntries & setAncestors,uint64_t limitAncestorCount,uint64_t limitAncestorSize,uint64_t limitDescendantCount,uint64_t limitDescendantSize,std::string & errString,bool fSearchForParents) const149 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
150 {
151 setEntries parentHashes;
152 const CTransaction &tx = entry.GetTx();
153
154 if (fSearchForParents) {
155 // Get parents of this transaction that are in the mempool
156 // GetMemPoolParents() is only valid for entries in the mempool, so we
157 // iterate mapTx to find parents.
158 for (unsigned int i = 0; i < tx.vin.size(); i++) {
159 boost::optional<txiter> piter = GetIter(tx.vin[i].prevout.hash);
160 if (piter) {
161 parentHashes.insert(*piter);
162 if (parentHashes.size() + 1 > limitAncestorCount) {
163 errString = strprintf("too many unconfirmed parents [limit: %u]", limitAncestorCount);
164 return false;
165 }
166 }
167 }
168 } else {
169 // If we're not searching for parents, we require this to be an
170 // entry in the mempool already.
171 txiter it = mapTx.iterator_to(entry);
172 parentHashes = GetMemPoolParents(it);
173 }
174
175 size_t totalSizeWithAncestors = entry.GetTxSize();
176
177 while (!parentHashes.empty()) {
178 txiter stageit = *parentHashes.begin();
179
180 setAncestors.insert(stageit);
181 parentHashes.erase(stageit);
182 totalSizeWithAncestors += stageit->GetTxSize();
183
184 if (stageit->GetSizeWithDescendants() + entry.GetTxSize() > limitDescendantSize) {
185 errString = strprintf("exceeds descendant size limit for tx %s [limit: %u]", stageit->GetTx().GetHash().ToString(), limitDescendantSize);
186 return false;
187 } else if (stageit->GetCountWithDescendants() + 1 > limitDescendantCount) {
188 errString = strprintf("too many descendants for tx %s [limit: %u]", stageit->GetTx().GetHash().ToString(), limitDescendantCount);
189 return false;
190 } else if (totalSizeWithAncestors > limitAncestorSize) {
191 errString = strprintf("exceeds ancestor size limit [limit: %u]", limitAncestorSize);
192 return false;
193 }
194
195 const setEntries & setMemPoolParents = GetMemPoolParents(stageit);
196 for (txiter phash : setMemPoolParents) {
197 // If this is a new ancestor, add it.
198 if (setAncestors.count(phash) == 0) {
199 parentHashes.insert(phash);
200 }
201 if (parentHashes.size() + setAncestors.size() + 1 > limitAncestorCount) {
202 errString = strprintf("too many unconfirmed ancestors [limit: %u]", limitAncestorCount);
203 return false;
204 }
205 }
206 }
207
208 return true;
209 }
210
UpdateAncestorsOf(bool add,txiter it,setEntries & setAncestors)211 void CTxMemPool::UpdateAncestorsOf(bool add, txiter it, setEntries &setAncestors)
212 {
213 setEntries parentIters = GetMemPoolParents(it);
214 // add or remove this tx as a child of each parent
215 for (txiter piter : parentIters) {
216 UpdateChild(piter, it, add);
217 }
218 const int64_t updateCount = (add ? 1 : -1);
219 const int64_t updateSize = updateCount * it->GetTxSize();
220 const CAmount updateFee = updateCount * it->GetModifiedFee();
221 for (txiter ancestorIt : setAncestors) {
222 mapTx.modify(ancestorIt, update_descendant_state(updateSize, updateFee, updateCount));
223 }
224 }
225
UpdateEntryForAncestors(txiter it,const setEntries & setAncestors)226 void CTxMemPool::UpdateEntryForAncestors(txiter it, const setEntries &setAncestors)
227 {
228 int64_t updateCount = setAncestors.size();
229 int64_t updateSize = 0;
230 CAmount updateFee = 0;
231 int64_t updateSigOpsCost = 0;
232 for (txiter ancestorIt : setAncestors) {
233 updateSize += ancestorIt->GetTxSize();
234 updateFee += ancestorIt->GetModifiedFee();
235 updateSigOpsCost += ancestorIt->GetSigOpCost();
236 }
237 mapTx.modify(it, update_ancestor_state(updateSize, updateFee, updateCount, updateSigOpsCost));
238 }
239
UpdateChildrenForRemoval(txiter it)240 void CTxMemPool::UpdateChildrenForRemoval(txiter it)
241 {
242 const setEntries &setMemPoolChildren = GetMemPoolChildren(it);
243 for (txiter updateIt : setMemPoolChildren) {
244 UpdateParent(updateIt, it, false);
245 }
246 }
247
UpdateForRemoveFromMempool(const setEntries & entriesToRemove,bool updateDescendants)248 void CTxMemPool::UpdateForRemoveFromMempool(const setEntries &entriesToRemove, bool updateDescendants)
249 {
250 // For each entry, walk back all ancestors and decrement size associated with this
251 // transaction
252 const uint64_t nNoLimit = std::numeric_limits<uint64_t>::max();
253 if (updateDescendants) {
254 // updateDescendants should be true whenever we're not recursively
255 // removing a tx and all its descendants, eg when a transaction is
256 // confirmed in a block.
257 // Here we only update statistics and not data in mapLinks (which
258 // we need to preserve until we're finished with all operations that
259 // need to traverse the mempool).
260 for (txiter removeIt : entriesToRemove) {
261 setEntries setDescendants;
262 CalculateDescendants(removeIt, setDescendants);
263 setDescendants.erase(removeIt); // don't update state for self
264 int64_t modifySize = -((int64_t)removeIt->GetTxSize());
265 CAmount modifyFee = -removeIt->GetModifiedFee();
266 int modifySigOps = -removeIt->GetSigOpCost();
267 for (txiter dit : setDescendants) {
268 mapTx.modify(dit, update_ancestor_state(modifySize, modifyFee, -1, modifySigOps));
269 }
270 }
271 }
272 for (txiter removeIt : entriesToRemove) {
273 setEntries setAncestors;
274 const CTxMemPoolEntry &entry = *removeIt;
275 std::string dummy;
276 // Since this is a tx that is already in the mempool, we can call CMPA
277 // with fSearchForParents = false. If the mempool is in a consistent
278 // state, then using true or false should both be correct, though false
279 // should be a bit faster.
280 // However, if we happen to be in the middle of processing a reorg, then
281 // the mempool can be in an inconsistent state. In this case, the set
282 // of ancestors reachable via mapLinks will be the same as the set of
283 // ancestors whose packages include this transaction, because when we
284 // add a new transaction to the mempool in addUnchecked(), we assume it
285 // has no children, and in the case of a reorg where that assumption is
286 // false, the in-mempool children aren't linked to the in-block tx's
287 // until UpdateTransactionsFromBlock() is called.
288 // So if we're being called during a reorg, ie before
289 // UpdateTransactionsFromBlock() has been called, then mapLinks[] will
290 // differ from the set of mempool parents we'd calculate by searching,
291 // and it's important that we use the mapLinks[] notion of ancestor
292 // transactions as the set of things to update for removal.
293 CalculateMemPoolAncestors(entry, setAncestors, nNoLimit, nNoLimit, nNoLimit, nNoLimit, dummy, false);
294 // Note that UpdateAncestorsOf severs the child links that point to
295 // removeIt in the entries for the parents of removeIt.
296 UpdateAncestorsOf(false, removeIt, setAncestors);
297 }
298 // After updating all the ancestor sizes, we can now sever the link between each
299 // transaction being removed and any mempool children (ie, update setMemPoolParents
300 // for each direct child of a transaction being removed).
301 for (txiter removeIt : entriesToRemove) {
302 UpdateChildrenForRemoval(removeIt);
303 }
304 }
305
UpdateDescendantState(int64_t modifySize,CAmount modifyFee,int64_t modifyCount)306 void CTxMemPoolEntry::UpdateDescendantState(int64_t modifySize, CAmount modifyFee, int64_t modifyCount)
307 {
308 nSizeWithDescendants += modifySize;
309 assert(int64_t(nSizeWithDescendants) > 0);
310 nModFeesWithDescendants += modifyFee;
311 nCountWithDescendants += modifyCount;
312 assert(int64_t(nCountWithDescendants) > 0);
313 }
314
UpdateAncestorState(int64_t modifySize,CAmount modifyFee,int64_t modifyCount,int64_t modifySigOps)315 void CTxMemPoolEntry::UpdateAncestorState(int64_t modifySize, CAmount modifyFee, int64_t modifyCount, int64_t modifySigOps)
316 {
317 nSizeWithAncestors += modifySize;
318 assert(int64_t(nSizeWithAncestors) > 0);
319 nModFeesWithAncestors += modifyFee;
320 nCountWithAncestors += modifyCount;
321 assert(int64_t(nCountWithAncestors) > 0);
322 nSigOpCostWithAncestors += modifySigOps;
323 assert(int(nSigOpCostWithAncestors) >= 0);
324 }
325
CTxMemPool(CBlockPolicyEstimator * estimator)326 CTxMemPool::CTxMemPool(CBlockPolicyEstimator* estimator) :
327 nTransactionsUpdated(0), minerPolicyEstimator(estimator)
328 {
329 _clear(); //lock free clear
330
331 // Sanity checks off by default for performance, because otherwise
332 // accepting transactions becomes O(N^2) where N is the number
333 // of transactions in the pool
334 nCheckFrequency = 0;
335 }
336
isSpent(const COutPoint & outpoint) const337 bool CTxMemPool::isSpent(const COutPoint& outpoint) const
338 {
339 LOCK(cs);
340 return mapNextTx.count(outpoint);
341 }
342
GetTransactionsUpdated() const343 unsigned int CTxMemPool::GetTransactionsUpdated() const
344 {
345 LOCK(cs);
346 return nTransactionsUpdated;
347 }
348
AddTransactionsUpdated(unsigned int n)349 void CTxMemPool::AddTransactionsUpdated(unsigned int n)
350 {
351 LOCK(cs);
352 nTransactionsUpdated += n;
353 }
354
addUnchecked(const CTxMemPoolEntry & entry,setEntries & setAncestors,bool validFeeEstimate)355 void CTxMemPool::addUnchecked(const CTxMemPoolEntry &entry, setEntries &setAncestors, bool validFeeEstimate)
356 {
357 NotifyEntryAdded(entry.GetSharedTx());
358 // Add to memory pool without checking anything.
359 // Used by AcceptToMemoryPool(), which DOES do
360 // all the appropriate checks.
361 indexed_transaction_set::iterator newit = mapTx.insert(entry).first;
362 mapLinks.insert(make_pair(newit, TxLinks()));
363
364 // Update transaction for any feeDelta created by PrioritiseTransaction
365 // TODO: refactor so that the fee delta is calculated before inserting
366 // into mapTx.
367 CAmount delta{0};
368 ApplyDelta(entry.GetTx().GetHash(), delta);
369 if (delta) {
370 mapTx.modify(newit, update_fee_delta(delta));
371 }
372
373 // Update cachedInnerUsage to include contained transaction's usage.
374 // (When we update the entry for in-mempool parents, memory usage will be
375 // further updated.)
376 cachedInnerUsage += entry.DynamicMemoryUsage();
377
378 const CTransaction& tx = newit->GetTx();
379 std::set<uint256> setParentTransactions;
380 for (unsigned int i = 0; i < tx.vin.size(); i++) {
381 mapNextTx.insert(std::make_pair(&tx.vin[i].prevout, &tx));
382 setParentTransactions.insert(tx.vin[i].prevout.hash);
383 }
384 // Don't bother worrying about child transactions of this one.
385 // Normal case of a new transaction arriving is that there can't be any
386 // children, because such children would be orphans.
387 // An exception to that is if a transaction enters that used to be in a block.
388 // In that case, our disconnect block logic will call UpdateTransactionsFromBlock
389 // to clean up the mess we're leaving here.
390
391 // Update ancestors with information about this tx
392 for (const auto& pit : GetIterSet(setParentTransactions)) {
393 UpdateParent(newit, pit, true);
394 }
395 UpdateAncestorsOf(true, newit, setAncestors);
396 UpdateEntryForAncestors(newit, setAncestors);
397
398 nTransactionsUpdated++;
399 totalTxSize += entry.GetTxSize();
400 if (minerPolicyEstimator) {minerPolicyEstimator->processTransaction(entry, validFeeEstimate);}
401
402 vTxHashes.emplace_back(tx.GetWitnessHash(), newit);
403 newit->vTxHashesIdx = vTxHashes.size() - 1;
404 }
405
removeUnchecked(txiter it,MemPoolRemovalReason reason)406 void CTxMemPool::removeUnchecked(txiter it, MemPoolRemovalReason reason)
407 {
408 NotifyEntryRemoved(it->GetSharedTx(), reason);
409 const uint256 hash = it->GetTx().GetHash();
410 for (const CTxIn& txin : it->GetTx().vin)
411 mapNextTx.erase(txin.prevout);
412
413 if (vTxHashes.size() > 1) {
414 vTxHashes[it->vTxHashesIdx] = std::move(vTxHashes.back());
415 vTxHashes[it->vTxHashesIdx].second->vTxHashesIdx = it->vTxHashesIdx;
416 vTxHashes.pop_back();
417 if (vTxHashes.size() * 2 < vTxHashes.capacity())
418 vTxHashes.shrink_to_fit();
419 } else
420 vTxHashes.clear();
421
422 totalTxSize -= it->GetTxSize();
423 cachedInnerUsage -= it->DynamicMemoryUsage();
424 cachedInnerUsage -= memusage::DynamicUsage(mapLinks[it].parents) + memusage::DynamicUsage(mapLinks[it].children);
425 mapLinks.erase(it);
426 mapTx.erase(it);
427 nTransactionsUpdated++;
428 if (minerPolicyEstimator) {minerPolicyEstimator->removeTx(hash, false);}
429 }
430
431 // Calculates descendants of entry that are not already in setDescendants, and adds to
432 // setDescendants. Assumes entryit is already a tx in the mempool and setMemPoolChildren
433 // is correct for tx and all descendants.
434 // Also assumes that if an entry is in setDescendants already, then all
435 // in-mempool descendants of it are already in setDescendants as well, so that we
436 // can save time by not iterating over those entries.
CalculateDescendants(txiter entryit,setEntries & setDescendants) const437 void CTxMemPool::CalculateDescendants(txiter entryit, setEntries& setDescendants) const
438 {
439 setEntries stage;
440 if (setDescendants.count(entryit) == 0) {
441 stage.insert(entryit);
442 }
443 // Traverse down the children of entry, only adding children that are not
444 // accounted for in setDescendants already (because those children have either
445 // already been walked, or will be walked in this iteration).
446 while (!stage.empty()) {
447 txiter it = *stage.begin();
448 setDescendants.insert(it);
449 stage.erase(it);
450
451 const setEntries &setChildren = GetMemPoolChildren(it);
452 for (txiter childiter : setChildren) {
453 if (!setDescendants.count(childiter)) {
454 stage.insert(childiter);
455 }
456 }
457 }
458 }
459
removeRecursive(const CTransaction & origTx,MemPoolRemovalReason reason)460 void CTxMemPool::removeRecursive(const CTransaction &origTx, MemPoolRemovalReason reason)
461 {
462 // Remove transaction from memory pool
463 {
464 LOCK(cs);
465 setEntries txToRemove;
466 txiter origit = mapTx.find(origTx.GetHash());
467 if (origit != mapTx.end()) {
468 txToRemove.insert(origit);
469 } else {
470 // When recursively removing but origTx isn't in the mempool
471 // be sure to remove any children that are in the pool. This can
472 // happen during chain re-orgs if origTx isn't re-accepted into
473 // the mempool for any reason.
474 for (unsigned int i = 0; i < origTx.vout.size(); i++) {
475 auto it = mapNextTx.find(COutPoint(origTx.GetHash(), i));
476 if (it == mapNextTx.end())
477 continue;
478 txiter nextit = mapTx.find(it->second->GetHash());
479 assert(nextit != mapTx.end());
480 txToRemove.insert(nextit);
481 }
482 }
483 setEntries setAllRemoves;
484 for (txiter it : txToRemove) {
485 CalculateDescendants(it, setAllRemoves);
486 }
487
488 RemoveStaged(setAllRemoves, false, reason);
489 }
490 }
491
removeForReorg(const CCoinsViewCache * pcoins,unsigned int nMemPoolHeight,int flags)492 void CTxMemPool::removeForReorg(const CCoinsViewCache *pcoins, unsigned int nMemPoolHeight, int flags)
493 {
494 // Remove transactions spending a coinbase which are now immature and no-longer-final transactions
495 LOCK(cs);
496 setEntries txToRemove;
497 for (indexed_transaction_set::const_iterator it = mapTx.begin(); it != mapTx.end(); it++) {
498 const CTransaction& tx = it->GetTx();
499 LockPoints lp = it->GetLockPoints();
500 bool validLP = TestLockPointValidity(&lp);
501 if (!CheckFinalTx(tx, flags) || !CheckSequenceLocks(*this, tx, flags, &lp, validLP)) {
502 // Note if CheckSequenceLocks fails the LockPoints may still be invalid
503 // So it's critical that we remove the tx and not depend on the LockPoints.
504 txToRemove.insert(it);
505 } else if (it->GetSpendsCoinbase()) {
506 for (const CTxIn& txin : tx.vin) {
507 indexed_transaction_set::const_iterator it2 = mapTx.find(txin.prevout.hash);
508 if (it2 != mapTx.end())
509 continue;
510 const Coin &coin = pcoins->AccessCoin(txin.prevout);
511 if (nCheckFrequency != 0) assert(!coin.IsSpent());
512 if (coin.IsSpent() || (coin.IsCoinBase() && ((signed long)nMemPoolHeight) - coin.nHeight < COINBASE_MATURITY)) {
513 txToRemove.insert(it);
514 break;
515 }
516 }
517 }
518 if (!validLP) {
519 mapTx.modify(it, update_lock_points(lp));
520 }
521 }
522 setEntries setAllRemoves;
523 for (txiter it : txToRemove) {
524 CalculateDescendants(it, setAllRemoves);
525 }
526 RemoveStaged(setAllRemoves, false, MemPoolRemovalReason::REORG);
527 }
528
removeConflicts(const CTransaction & tx)529 void CTxMemPool::removeConflicts(const CTransaction &tx)
530 {
531 // Remove transactions which depend on inputs of tx, recursively
532 AssertLockHeld(cs);
533 for (const CTxIn &txin : tx.vin) {
534 auto it = mapNextTx.find(txin.prevout);
535 if (it != mapNextTx.end()) {
536 const CTransaction &txConflict = *it->second;
537 if (txConflict != tx)
538 {
539 ClearPrioritisation(txConflict.GetHash());
540 removeRecursive(txConflict, MemPoolRemovalReason::CONFLICT);
541 }
542 }
543 }
544 }
545
546 /**
547 * Called when a block is connected. Removes from mempool and updates the miner fee estimator.
548 */
removeForBlock(const std::vector<CTransactionRef> & vtx,unsigned int nBlockHeight)549 void CTxMemPool::removeForBlock(const std::vector<CTransactionRef>& vtx, unsigned int nBlockHeight)
550 {
551 LOCK(cs);
552 std::vector<const CTxMemPoolEntry*> entries;
553 for (const auto& tx : vtx)
554 {
555 uint256 hash = tx->GetHash();
556
557 indexed_transaction_set::iterator i = mapTx.find(hash);
558 if (i != mapTx.end())
559 entries.push_back(&*i);
560 }
561 // Before the txs in the new block have been removed from the mempool, update policy estimates
562 if (minerPolicyEstimator) {minerPolicyEstimator->processBlock(nBlockHeight, entries);}
563 for (const auto& tx : vtx)
564 {
565 txiter it = mapTx.find(tx->GetHash());
566 if (it != mapTx.end()) {
567 setEntries stage;
568 stage.insert(it);
569 RemoveStaged(stage, true, MemPoolRemovalReason::BLOCK);
570 }
571 removeConflicts(*tx);
572 ClearPrioritisation(tx->GetHash());
573 }
574 lastRollingFeeUpdate = GetTime();
575 blockSinceLastRollingFeeBump = true;
576 }
577
_clear()578 void CTxMemPool::_clear()
579 {
580 mapLinks.clear();
581 mapTx.clear();
582 mapNextTx.clear();
583 totalTxSize = 0;
584 cachedInnerUsage = 0;
585 lastRollingFeeUpdate = GetTime();
586 blockSinceLastRollingFeeBump = false;
587 rollingMinimumFeeRate = 0;
588 ++nTransactionsUpdated;
589 }
590
clear()591 void CTxMemPool::clear()
592 {
593 LOCK(cs);
594 _clear();
595 }
596
CheckInputsAndUpdateCoins(const CTransaction & tx,CCoinsViewCache & mempoolDuplicate,const int64_t spendheight)597 static void CheckInputsAndUpdateCoins(const CTransaction& tx, CCoinsViewCache& mempoolDuplicate, const int64_t spendheight)
598 {
599 CValidationState state;
600 CAmount txfee = 0;
601 bool fCheckResult = tx.IsCoinBase() || Consensus::CheckTxInputs(tx, state, mempoolDuplicate, spendheight, txfee);
602 assert(fCheckResult);
603 UpdateCoins(tx, mempoolDuplicate, 1000000);
604 }
605
check(const CCoinsViewCache * pcoins) const606 void CTxMemPool::check(const CCoinsViewCache *pcoins) const
607 {
608 LOCK(cs);
609 if (nCheckFrequency == 0)
610 return;
611
612 if (GetRand(std::numeric_limits<uint32_t>::max()) >= nCheckFrequency)
613 return;
614
615 LogPrint(BCLog::MEMPOOL, "Checking mempool with %u transactions and %u inputs\n", (unsigned int)mapTx.size(), (unsigned int)mapNextTx.size());
616
617 uint64_t checkTotal = 0;
618 uint64_t innerUsage = 0;
619
620 CCoinsViewCache mempoolDuplicate(const_cast<CCoinsViewCache*>(pcoins));
621 const int64_t spendheight = GetSpendHeight(mempoolDuplicate);
622
623 std::list<const CTxMemPoolEntry*> waitingOnDependants;
624 for (indexed_transaction_set::const_iterator it = mapTx.begin(); it != mapTx.end(); it++) {
625 unsigned int i = 0;
626 checkTotal += it->GetTxSize();
627 innerUsage += it->DynamicMemoryUsage();
628 const CTransaction& tx = it->GetTx();
629 txlinksMap::const_iterator linksiter = mapLinks.find(it);
630 assert(linksiter != mapLinks.end());
631 const TxLinks &links = linksiter->second;
632 innerUsage += memusage::DynamicUsage(links.parents) + memusage::DynamicUsage(links.children);
633 bool fDependsWait = false;
634 setEntries setParentCheck;
635 for (const CTxIn &txin : tx.vin) {
636 // Check that every mempool transaction's inputs refer to available coins, or other mempool tx's.
637 indexed_transaction_set::const_iterator it2 = mapTx.find(txin.prevout.hash);
638 if (it2 != mapTx.end()) {
639 const CTransaction& tx2 = it2->GetTx();
640 assert(tx2.vout.size() > txin.prevout.n && !tx2.vout[txin.prevout.n].IsNull());
641 fDependsWait = true;
642 setParentCheck.insert(it2);
643 } else {
644 assert(pcoins->HaveCoin(txin.prevout));
645 }
646 // Check whether its inputs are marked in mapNextTx.
647 auto it3 = mapNextTx.find(txin.prevout);
648 assert(it3 != mapNextTx.end());
649 assert(it3->first == &txin.prevout);
650 assert(it3->second == &tx);
651 i++;
652 }
653 assert(setParentCheck == GetMemPoolParents(it));
654 // Verify ancestor state is correct.
655 setEntries setAncestors;
656 uint64_t nNoLimit = std::numeric_limits<uint64_t>::max();
657 std::string dummy;
658 CalculateMemPoolAncestors(*it, setAncestors, nNoLimit, nNoLimit, nNoLimit, nNoLimit, dummy);
659 uint64_t nCountCheck = setAncestors.size() + 1;
660 uint64_t nSizeCheck = it->GetTxSize();
661 CAmount nFeesCheck = it->GetModifiedFee();
662 int64_t nSigOpCheck = it->GetSigOpCost();
663
664 for (txiter ancestorIt : setAncestors) {
665 nSizeCheck += ancestorIt->GetTxSize();
666 nFeesCheck += ancestorIt->GetModifiedFee();
667 nSigOpCheck += ancestorIt->GetSigOpCost();
668 }
669
670 assert(it->GetCountWithAncestors() == nCountCheck);
671 assert(it->GetSizeWithAncestors() == nSizeCheck);
672 assert(it->GetSigOpCostWithAncestors() == nSigOpCheck);
673 assert(it->GetModFeesWithAncestors() == nFeesCheck);
674
675 // Check children against mapNextTx
676 CTxMemPool::setEntries setChildrenCheck;
677 auto iter = mapNextTx.lower_bound(COutPoint(it->GetTx().GetHash(), 0));
678 uint64_t child_sizes = 0;
679 for (; iter != mapNextTx.end() && iter->first->hash == it->GetTx().GetHash(); ++iter) {
680 txiter childit = mapTx.find(iter->second->GetHash());
681 assert(childit != mapTx.end()); // mapNextTx points to in-mempool transactions
682 if (setChildrenCheck.insert(childit).second) {
683 child_sizes += childit->GetTxSize();
684 }
685 }
686 assert(setChildrenCheck == GetMemPoolChildren(it));
687 // Also check to make sure size is greater than sum with immediate children.
688 // just a sanity check, not definitive that this calc is correct...
689 assert(it->GetSizeWithDescendants() >= child_sizes + it->GetTxSize());
690
691 if (fDependsWait)
692 waitingOnDependants.push_back(&(*it));
693 else {
694 CheckInputsAndUpdateCoins(tx, mempoolDuplicate, spendheight);
695 }
696 }
697 unsigned int stepsSinceLastRemove = 0;
698 while (!waitingOnDependants.empty()) {
699 const CTxMemPoolEntry* entry = waitingOnDependants.front();
700 waitingOnDependants.pop_front();
701 if (!mempoolDuplicate.HaveInputs(entry->GetTx())) {
702 waitingOnDependants.push_back(entry);
703 stepsSinceLastRemove++;
704 assert(stepsSinceLastRemove < waitingOnDependants.size());
705 } else {
706 CheckInputsAndUpdateCoins(entry->GetTx(), mempoolDuplicate, spendheight);
707 stepsSinceLastRemove = 0;
708 }
709 }
710 for (auto it = mapNextTx.cbegin(); it != mapNextTx.cend(); it++) {
711 uint256 hash = it->second->GetHash();
712 indexed_transaction_set::const_iterator it2 = mapTx.find(hash);
713 const CTransaction& tx = it2->GetTx();
714 assert(it2 != mapTx.end());
715 assert(&tx == it->second);
716 }
717
718 assert(totalTxSize == checkTotal);
719 assert(innerUsage == cachedInnerUsage);
720 }
721
CompareDepthAndScore(const uint256 & hasha,const uint256 & hashb)722 bool CTxMemPool::CompareDepthAndScore(const uint256& hasha, const uint256& hashb)
723 {
724 LOCK(cs);
725 indexed_transaction_set::const_iterator i = mapTx.find(hasha);
726 if (i == mapTx.end()) return false;
727 indexed_transaction_set::const_iterator j = mapTx.find(hashb);
728 if (j == mapTx.end()) return true;
729 uint64_t counta = i->GetCountWithAncestors();
730 uint64_t countb = j->GetCountWithAncestors();
731 if (counta == countb) {
732 return CompareTxMemPoolEntryByScore()(*i, *j);
733 }
734 return counta < countb;
735 }
736
737 namespace {
738 class DepthAndScoreComparator
739 {
740 public:
operator ()(const CTxMemPool::indexed_transaction_set::const_iterator & a,const CTxMemPool::indexed_transaction_set::const_iterator & b)741 bool operator()(const CTxMemPool::indexed_transaction_set::const_iterator& a, const CTxMemPool::indexed_transaction_set::const_iterator& b)
742 {
743 uint64_t counta = a->GetCountWithAncestors();
744 uint64_t countb = b->GetCountWithAncestors();
745 if (counta == countb) {
746 return CompareTxMemPoolEntryByScore()(*a, *b);
747 }
748 return counta < countb;
749 }
750 };
751 } // namespace
752
GetSortedDepthAndScore() const753 std::vector<CTxMemPool::indexed_transaction_set::const_iterator> CTxMemPool::GetSortedDepthAndScore() const
754 {
755 std::vector<indexed_transaction_set::const_iterator> iters;
756 AssertLockHeld(cs);
757
758 iters.reserve(mapTx.size());
759
760 for (indexed_transaction_set::iterator mi = mapTx.begin(); mi != mapTx.end(); ++mi) {
761 iters.push_back(mi);
762 }
763 std::sort(iters.begin(), iters.end(), DepthAndScoreComparator());
764 return iters;
765 }
766
queryHashes(std::vector<uint256> & vtxid)767 void CTxMemPool::queryHashes(std::vector<uint256>& vtxid)
768 {
769 LOCK(cs);
770 auto iters = GetSortedDepthAndScore();
771
772 vtxid.clear();
773 vtxid.reserve(mapTx.size());
774
775 for (auto it : iters) {
776 vtxid.push_back(it->GetTx().GetHash());
777 }
778 }
779
GetInfo(CTxMemPool::indexed_transaction_set::const_iterator it)780 static TxMempoolInfo GetInfo(CTxMemPool::indexed_transaction_set::const_iterator it) {
781 return TxMempoolInfo{it->GetSharedTx(), it->GetTime(), CFeeRate(it->GetFee(), it->GetTxSize()), it->GetModifiedFee() - it->GetFee()};
782 }
783
infoAll() const784 std::vector<TxMempoolInfo> CTxMemPool::infoAll() const
785 {
786 LOCK(cs);
787 auto iters = GetSortedDepthAndScore();
788
789 std::vector<TxMempoolInfo> ret;
790 ret.reserve(mapTx.size());
791 for (auto it : iters) {
792 ret.push_back(GetInfo(it));
793 }
794
795 return ret;
796 }
797
get(const uint256 & hash) const798 CTransactionRef CTxMemPool::get(const uint256& hash) const
799 {
800 LOCK(cs);
801 indexed_transaction_set::const_iterator i = mapTx.find(hash);
802 if (i == mapTx.end())
803 return nullptr;
804 return i->GetSharedTx();
805 }
806
info(const uint256 & hash) const807 TxMempoolInfo CTxMemPool::info(const uint256& hash) const
808 {
809 LOCK(cs);
810 indexed_transaction_set::const_iterator i = mapTx.find(hash);
811 if (i == mapTx.end())
812 return TxMempoolInfo();
813 return GetInfo(i);
814 }
815
PrioritiseTransaction(const uint256 & hash,const CAmount & nFeeDelta)816 void CTxMemPool::PrioritiseTransaction(const uint256& hash, const CAmount& nFeeDelta)
817 {
818 {
819 LOCK(cs);
820 CAmount &delta = mapDeltas[hash];
821 delta += nFeeDelta;
822 txiter it = mapTx.find(hash);
823 if (it != mapTx.end()) {
824 mapTx.modify(it, update_fee_delta(delta));
825 // Now update all ancestors' modified fees with descendants
826 setEntries setAncestors;
827 uint64_t nNoLimit = std::numeric_limits<uint64_t>::max();
828 std::string dummy;
829 CalculateMemPoolAncestors(*it, setAncestors, nNoLimit, nNoLimit, nNoLimit, nNoLimit, dummy, false);
830 for (txiter ancestorIt : setAncestors) {
831 mapTx.modify(ancestorIt, update_descendant_state(0, nFeeDelta, 0));
832 }
833 // Now update all descendants' modified fees with ancestors
834 setEntries setDescendants;
835 CalculateDescendants(it, setDescendants);
836 setDescendants.erase(it);
837 for (txiter descendantIt : setDescendants) {
838 mapTx.modify(descendantIt, update_ancestor_state(0, nFeeDelta, 0, 0));
839 }
840 ++nTransactionsUpdated;
841 }
842 }
843 LogPrintf("PrioritiseTransaction: %s feerate += %s\n", hash.ToString(), FormatMoney(nFeeDelta));
844 }
845
ApplyDelta(const uint256 hash,CAmount & nFeeDelta) const846 void CTxMemPool::ApplyDelta(const uint256 hash, CAmount &nFeeDelta) const
847 {
848 LOCK(cs);
849 std::map<uint256, CAmount>::const_iterator pos = mapDeltas.find(hash);
850 if (pos == mapDeltas.end())
851 return;
852 const CAmount &delta = pos->second;
853 nFeeDelta += delta;
854 }
855
ClearPrioritisation(const uint256 hash)856 void CTxMemPool::ClearPrioritisation(const uint256 hash)
857 {
858 LOCK(cs);
859 mapDeltas.erase(hash);
860 }
861
GetConflictTx(const COutPoint & prevout) const862 const CTransaction* CTxMemPool::GetConflictTx(const COutPoint& prevout) const
863 {
864 const auto it = mapNextTx.find(prevout);
865 return it == mapNextTx.end() ? nullptr : it->second;
866 }
867
GetIter(const uint256 & txid) const868 boost::optional<CTxMemPool::txiter> CTxMemPool::GetIter(const uint256& txid) const
869 {
870 auto it = mapTx.find(txid);
871 if (it != mapTx.end()) return it;
872 return boost::optional<txiter>{};
873 }
874
GetIterSet(const std::set<uint256> & hashes) const875 CTxMemPool::setEntries CTxMemPool::GetIterSet(const std::set<uint256>& hashes) const
876 {
877 CTxMemPool::setEntries ret;
878 for (const auto& h : hashes) {
879 const auto mi = GetIter(h);
880 if (mi) ret.insert(*mi);
881 }
882 return ret;
883 }
884
HasNoInputsOf(const CTransaction & tx) const885 bool CTxMemPool::HasNoInputsOf(const CTransaction &tx) const
886 {
887 for (unsigned int i = 0; i < tx.vin.size(); i++)
888 if (exists(tx.vin[i].prevout.hash))
889 return false;
890 return true;
891 }
892
CCoinsViewMemPool(CCoinsView * baseIn,const CTxMemPool & mempoolIn)893 CCoinsViewMemPool::CCoinsViewMemPool(CCoinsView* baseIn, const CTxMemPool& mempoolIn) : CCoinsViewBacked(baseIn), mempool(mempoolIn) { }
894
GetCoin(const COutPoint & outpoint,Coin & coin) const895 bool CCoinsViewMemPool::GetCoin(const COutPoint &outpoint, Coin &coin) const {
896 // If an entry in the mempool exists, always return that one, as it's guaranteed to never
897 // conflict with the underlying cache, and it cannot have pruned entries (as it contains full)
898 // transactions. First checking the underlying cache risks returning a pruned entry instead.
899 CTransactionRef ptx = mempool.get(outpoint.hash);
900 if (ptx) {
901 if (outpoint.n < ptx->vout.size()) {
902 coin = Coin(ptx->vout[outpoint.n], MEMPOOL_HEIGHT, false);
903 return true;
904 } else {
905 return false;
906 }
907 }
908 return base->GetCoin(outpoint, coin);
909 }
910
DynamicMemoryUsage() const911 size_t CTxMemPool::DynamicMemoryUsage() const {
912 LOCK(cs);
913 // Estimate the overhead of mapTx to be 12 pointers + an allocation, as no exact formula for boost::multi_index_contained is implemented.
914 return memusage::MallocUsage(sizeof(CTxMemPoolEntry) + 12 * sizeof(void*)) * mapTx.size() + memusage::DynamicUsage(mapNextTx) + memusage::DynamicUsage(mapDeltas) + memusage::DynamicUsage(mapLinks) + memusage::DynamicUsage(vTxHashes) + cachedInnerUsage;
915 }
916
RemoveStaged(setEntries & stage,bool updateDescendants,MemPoolRemovalReason reason)917 void CTxMemPool::RemoveStaged(setEntries &stage, bool updateDescendants, MemPoolRemovalReason reason) {
918 AssertLockHeld(cs);
919 UpdateForRemoveFromMempool(stage, updateDescendants);
920 for (txiter it : stage) {
921 removeUnchecked(it, reason);
922 }
923 }
924
Expire(int64_t time)925 int CTxMemPool::Expire(int64_t time) {
926 LOCK(cs);
927 indexed_transaction_set::index<entry_time>::type::iterator it = mapTx.get<entry_time>().begin();
928 setEntries toremove;
929 while (it != mapTx.get<entry_time>().end() && it->GetTime() < time) {
930 toremove.insert(mapTx.project<0>(it));
931 it++;
932 }
933 setEntries stage;
934 for (txiter removeit : toremove) {
935 CalculateDescendants(removeit, stage);
936 }
937 RemoveStaged(stage, false, MemPoolRemovalReason::EXPIRY);
938 return stage.size();
939 }
940
addUnchecked(const CTxMemPoolEntry & entry,bool validFeeEstimate)941 void CTxMemPool::addUnchecked(const CTxMemPoolEntry &entry, bool validFeeEstimate)
942 {
943 setEntries setAncestors;
944 uint64_t nNoLimit = std::numeric_limits<uint64_t>::max();
945 std::string dummy;
946 CalculateMemPoolAncestors(entry, setAncestors, nNoLimit, nNoLimit, nNoLimit, nNoLimit, dummy);
947 return addUnchecked(entry, setAncestors, validFeeEstimate);
948 }
949
UpdateChild(txiter entry,txiter child,bool add)950 void CTxMemPool::UpdateChild(txiter entry, txiter child, bool add)
951 {
952 setEntries s;
953 if (add && mapLinks[entry].children.insert(child).second) {
954 cachedInnerUsage += memusage::IncrementalDynamicUsage(s);
955 } else if (!add && mapLinks[entry].children.erase(child)) {
956 cachedInnerUsage -= memusage::IncrementalDynamicUsage(s);
957 }
958 }
959
UpdateParent(txiter entry,txiter parent,bool add)960 void CTxMemPool::UpdateParent(txiter entry, txiter parent, bool add)
961 {
962 setEntries s;
963 if (add && mapLinks[entry].parents.insert(parent).second) {
964 cachedInnerUsage += memusage::IncrementalDynamicUsage(s);
965 } else if (!add && mapLinks[entry].parents.erase(parent)) {
966 cachedInnerUsage -= memusage::IncrementalDynamicUsage(s);
967 }
968 }
969
GetMemPoolParents(txiter entry) const970 const CTxMemPool::setEntries & CTxMemPool::GetMemPoolParents(txiter entry) const
971 {
972 assert (entry != mapTx.end());
973 txlinksMap::const_iterator it = mapLinks.find(entry);
974 assert(it != mapLinks.end());
975 return it->second.parents;
976 }
977
GetMemPoolChildren(txiter entry) const978 const CTxMemPool::setEntries & CTxMemPool::GetMemPoolChildren(txiter entry) const
979 {
980 assert (entry != mapTx.end());
981 txlinksMap::const_iterator it = mapLinks.find(entry);
982 assert(it != mapLinks.end());
983 return it->second.children;
984 }
985
GetMinFee(size_t sizelimit) const986 CFeeRate CTxMemPool::GetMinFee(size_t sizelimit) const {
987 LOCK(cs);
988 if (!blockSinceLastRollingFeeBump || rollingMinimumFeeRate == 0)
989 return CFeeRate(llround(rollingMinimumFeeRate));
990
991 int64_t time = GetTime();
992 if (time > lastRollingFeeUpdate + 10) {
993 double halflife = ROLLING_FEE_HALFLIFE;
994 if (DynamicMemoryUsage() < sizelimit / 4)
995 halflife /= 4;
996 else if (DynamicMemoryUsage() < sizelimit / 2)
997 halflife /= 2;
998
999 rollingMinimumFeeRate = rollingMinimumFeeRate / pow(2.0, (time - lastRollingFeeUpdate) / halflife);
1000 lastRollingFeeUpdate = time;
1001
1002 if (rollingMinimumFeeRate < (double)incrementalRelayFee.GetFeePerK() / 2) {
1003 rollingMinimumFeeRate = 0;
1004 return CFeeRate(0);
1005 }
1006 }
1007 return std::max(CFeeRate(llround(rollingMinimumFeeRate)), incrementalRelayFee);
1008 }
1009
trackPackageRemoved(const CFeeRate & rate)1010 void CTxMemPool::trackPackageRemoved(const CFeeRate& rate) {
1011 AssertLockHeld(cs);
1012 if (rate.GetFeePerK() > rollingMinimumFeeRate) {
1013 rollingMinimumFeeRate = rate.GetFeePerK();
1014 blockSinceLastRollingFeeBump = false;
1015 }
1016 }
1017
TrimToSize(size_t sizelimit,std::vector<COutPoint> * pvNoSpendsRemaining)1018 void CTxMemPool::TrimToSize(size_t sizelimit, std::vector<COutPoint>* pvNoSpendsRemaining) {
1019 LOCK(cs);
1020
1021 unsigned nTxnRemoved = 0;
1022 CFeeRate maxFeeRateRemoved(0);
1023 while (!mapTx.empty() && DynamicMemoryUsage() > sizelimit) {
1024 indexed_transaction_set::index<descendant_score>::type::iterator it = mapTx.get<descendant_score>().begin();
1025
1026 // We set the new mempool min fee to the feerate of the removed set, plus the
1027 // "minimum reasonable fee rate" (ie some value under which we consider txn
1028 // to have 0 fee). This way, we don't allow txn to enter mempool with feerate
1029 // equal to txn which were removed with no block in between.
1030 CFeeRate removed(it->GetModFeesWithDescendants(), it->GetSizeWithDescendants());
1031 removed += incrementalRelayFee;
1032 trackPackageRemoved(removed);
1033 maxFeeRateRemoved = std::max(maxFeeRateRemoved, removed);
1034
1035 setEntries stage;
1036 CalculateDescendants(mapTx.project<0>(it), stage);
1037 nTxnRemoved += stage.size();
1038
1039 std::vector<CTransaction> txn;
1040 if (pvNoSpendsRemaining) {
1041 txn.reserve(stage.size());
1042 for (txiter iter : stage)
1043 txn.push_back(iter->GetTx());
1044 }
1045 RemoveStaged(stage, false, MemPoolRemovalReason::SIZELIMIT);
1046 if (pvNoSpendsRemaining) {
1047 for (const CTransaction& tx : txn) {
1048 for (const CTxIn& txin : tx.vin) {
1049 if (exists(txin.prevout.hash)) continue;
1050 pvNoSpendsRemaining->push_back(txin.prevout);
1051 }
1052 }
1053 }
1054 }
1055
1056 if (maxFeeRateRemoved > CFeeRate(0)) {
1057 LogPrint(BCLog::MEMPOOL, "Removed %u txn, rolling minimum fee bumped to %s\n", nTxnRemoved, maxFeeRateRemoved.ToString());
1058 }
1059 }
1060
CalculateDescendantMaximum(txiter entry) const1061 uint64_t CTxMemPool::CalculateDescendantMaximum(txiter entry) const {
1062 // find parent with highest descendant count
1063 std::vector<txiter> candidates;
1064 setEntries counted;
1065 candidates.push_back(entry);
1066 uint64_t maximum = 0;
1067 while (candidates.size()) {
1068 txiter candidate = candidates.back();
1069 candidates.pop_back();
1070 if (!counted.insert(candidate).second) continue;
1071 const setEntries& parents = GetMemPoolParents(candidate);
1072 if (parents.size() == 0) {
1073 maximum = std::max(maximum, candidate->GetCountWithDescendants());
1074 } else {
1075 for (txiter i : parents) {
1076 candidates.push_back(i);
1077 }
1078 }
1079 }
1080 return maximum;
1081 }
1082
GetTransactionAncestry(const uint256 & txid,size_t & ancestors,size_t & descendants) const1083 void CTxMemPool::GetTransactionAncestry(const uint256& txid, size_t& ancestors, size_t& descendants) const {
1084 LOCK(cs);
1085 auto it = mapTx.find(txid);
1086 ancestors = descendants = 0;
1087 if (it != mapTx.end()) {
1088 ancestors = it->GetCountWithAncestors();
1089 descendants = CalculateDescendantMaximum(it);
1090 }
1091 }
1092
SaltedTxidHasher()1093 SaltedTxidHasher::SaltedTxidHasher() : k0(GetRand(std::numeric_limits<uint64_t>::max())), k1(GetRand(std::numeric_limits<uint64_t>::max())) {}
1094