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