Bitcoin Core  24.99.0
P2P Digital Currency
txmempool.cpp
Go to the documentation of this file.
1 // Copyright (c) 2009-2010 Satoshi Nakamoto
2 // Copyright (c) 2009-2021 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 <chain.h>
9 #include <coins.h>
10 #include <consensus/consensus.h>
11 #include <consensus/tx_verify.h>
12 #include <consensus/validation.h>
13 #include <policy/fees.h>
14 #include <policy/policy.h>
15 #include <policy/settings.h>
16 #include <reverse_iterator.h>
17 #include <util/check.h>
18 #include <util/moneystr.h>
19 #include <util/overflow.h>
20 #include <util/system.h>
21 #include <util/time.h>
22 #include <validationinterface.h>
23 
24 #include <cmath>
25 #include <optional>
26 
27 bool TestLockPointValidity(CChain& active_chain, const LockPoints& lp)
28 {
30  // If there are relative lock times then the maxInputBlock will be set
31  // If there are no relative lock times, the LockPoints don't depend on the chain
32  if (lp.maxInputBlock) {
33  // Check whether active_chain is an extension of the block at which the LockPoints
34  // calculation was valid. If not LockPoints are no longer valid
35  if (!active_chain.Contains(lp.maxInputBlock)) {
36  return false;
37  }
38  }
39 
40  // LockPoints still valid
41  return true;
42 }
43 
45  int64_t time, unsigned int entry_height,
46  bool spends_coinbase, int64_t sigops_cost, LockPoints lp)
47  : tx{tx},
48  nFee{fee},
49  nTxWeight(GetTransactionWeight(*tx)),
50  nUsageSize{RecursiveDynamicUsage(tx)},
51  nTime{time},
52  entryHeight{entry_height},
53  spendsCoinbase{spends_coinbase},
54  sigOpCost{sigops_cost},
55  m_modified_fee{nFee},
56  lockPoints{lp},
57  nSizeWithDescendants{GetTxSize()},
58  nModFeesWithDescendants{nFee},
59  nSizeWithAncestors{GetTxSize()},
60  nModFeesWithAncestors{nFee},
61  nSigOpCostWithAncestors{sigOpCost} {}
62 
64 {
68 }
69 
71 {
72  lockPoints = lp;
73 }
74 
76 {
78 }
79 
80 void CTxMemPool::UpdateForDescendants(txiter updateIt, cacheMap& cachedDescendants,
81  const std::set<uint256>& setExclude, std::set<uint256>& descendants_to_remove)
82 {
83  CTxMemPoolEntry::Children stageEntries, descendants;
84  stageEntries = updateIt->GetMemPoolChildrenConst();
85 
86  while (!stageEntries.empty()) {
87  const CTxMemPoolEntry& descendant = *stageEntries.begin();
88  descendants.insert(descendant);
89  stageEntries.erase(descendant);
90  const CTxMemPoolEntry::Children& children = descendant.GetMemPoolChildrenConst();
91  for (const CTxMemPoolEntry& childEntry : children) {
92  cacheMap::iterator cacheIt = cachedDescendants.find(mapTx.iterator_to(childEntry));
93  if (cacheIt != cachedDescendants.end()) {
94  // We've already calculated this one, just add the entries for this set
95  // but don't traverse again.
96  for (txiter cacheEntry : cacheIt->second) {
97  descendants.insert(*cacheEntry);
98  }
99  } else if (!descendants.count(childEntry)) {
100  // Schedule for later processing
101  stageEntries.insert(childEntry);
102  }
103  }
104  }
105  // descendants now contains all in-mempool descendants of updateIt.
106  // Update and add to cached descendant map
107  int64_t modifySize = 0;
108  CAmount modifyFee = 0;
109  int64_t modifyCount = 0;
110  for (const CTxMemPoolEntry& descendant : descendants) {
111  if (!setExclude.count(descendant.GetTx().GetHash())) {
112  modifySize += descendant.GetTxSize();
113  modifyFee += descendant.GetModifiedFee();
114  modifyCount++;
115  cachedDescendants[updateIt].insert(mapTx.iterator_to(descendant));
116  // Update ancestor state for each descendant
117  mapTx.modify(mapTx.iterator_to(descendant), [=](CTxMemPoolEntry& e) {
118  e.UpdateAncestorState(updateIt->GetTxSize(), updateIt->GetModifiedFee(), 1, updateIt->GetSigOpCost());
119  });
120  // Don't directly remove the transaction here -- doing so would
121  // invalidate iterators in cachedDescendants. Mark it for removal
122  // by inserting into descendants_to_remove.
123  if (descendant.GetCountWithAncestors() > uint64_t(m_limits.ancestor_count) || descendant.GetSizeWithAncestors() > uint64_t(m_limits.ancestor_size_vbytes)) {
124  descendants_to_remove.insert(descendant.GetTx().GetHash());
125  }
126  }
127  }
128  mapTx.modify(updateIt, [=](CTxMemPoolEntry& e) { e.UpdateDescendantState(modifySize, modifyFee, modifyCount); });
129 }
130 
131 void CTxMemPool::UpdateTransactionsFromBlock(const std::vector<uint256>& vHashesToUpdate)
132 {
134  // For each entry in vHashesToUpdate, store the set of in-mempool, but not
135  // in-vHashesToUpdate transactions, so that we don't have to recalculate
136  // descendants when we come across a previously seen entry.
137  cacheMap mapMemPoolDescendantsToUpdate;
138 
139  // Use a set for lookups into vHashesToUpdate (these entries are already
140  // accounted for in the state of their ancestors)
141  std::set<uint256> setAlreadyIncluded(vHashesToUpdate.begin(), vHashesToUpdate.end());
142 
143  std::set<uint256> descendants_to_remove;
144 
145  // Iterate in reverse, so that whenever we are looking at a transaction
146  // we are sure that all in-mempool descendants have already been processed.
147  // This maximizes the benefit of the descendant cache and guarantees that
148  // CTxMemPool::m_children will be updated, an assumption made in
149  // UpdateForDescendants.
150  for (const uint256 &hash : reverse_iterate(vHashesToUpdate)) {
151  // calculate children from mapNextTx
152  txiter it = mapTx.find(hash);
153  if (it == mapTx.end()) {
154  continue;
155  }
156  auto iter = mapNextTx.lower_bound(COutPoint(hash, 0));
157  // First calculate the children, and update CTxMemPool::m_children to
158  // include them, and update their CTxMemPoolEntry::m_parents to include this tx.
159  // we cache the in-mempool children to avoid duplicate updates
160  {
162  for (; iter != mapNextTx.end() && iter->first->hash == hash; ++iter) {
163  const uint256 &childHash = iter->second->GetHash();
164  txiter childIter = mapTx.find(childHash);
165  assert(childIter != mapTx.end());
166  // We can skip updating entries we've encountered before or that
167  // are in the block (which are already accounted for).
168  if (!visited(childIter) && !setAlreadyIncluded.count(childHash)) {
169  UpdateChild(it, childIter, true);
170  UpdateParent(childIter, it, true);
171  }
172  }
173  } // release epoch guard for UpdateForDescendants
174  UpdateForDescendants(it, mapMemPoolDescendantsToUpdate, setAlreadyIncluded, descendants_to_remove);
175  }
176 
177  for (const auto& txid : descendants_to_remove) {
178  // This txid may have been removed already in a prior call to removeRecursive.
179  // Therefore we ensure it is not yet removed already.
180  if (const std::optional<txiter> txiter = GetIter(txid)) {
182  }
183  }
184 }
185 
187  size_t entry_count,
188  setEntries& setAncestors,
189  CTxMemPoolEntry::Parents& staged_ancestors,
190  uint64_t limitAncestorCount,
191  uint64_t limitAncestorSize,
192  uint64_t limitDescendantCount,
193  uint64_t limitDescendantSize,
194  std::string &errString) const
195 {
196  size_t totalSizeWithAncestors = entry_size;
197 
198  while (!staged_ancestors.empty()) {
199  const CTxMemPoolEntry& stage = staged_ancestors.begin()->get();
200  txiter stageit = mapTx.iterator_to(stage);
201 
202  setAncestors.insert(stageit);
203  staged_ancestors.erase(stage);
204  totalSizeWithAncestors += stageit->GetTxSize();
205 
206  if (stageit->GetSizeWithDescendants() + entry_size > limitDescendantSize) {
207  errString = strprintf("exceeds descendant size limit for tx %s [limit: %u]", stageit->GetTx().GetHash().ToString(), limitDescendantSize);
208  return false;
209  } else if (stageit->GetCountWithDescendants() + entry_count > limitDescendantCount) {
210  errString = strprintf("too many descendants for tx %s [limit: %u]", stageit->GetTx().GetHash().ToString(), limitDescendantCount);
211  return false;
212  } else if (totalSizeWithAncestors > limitAncestorSize) {
213  errString = strprintf("exceeds ancestor size limit [limit: %u]", limitAncestorSize);
214  return false;
215  }
216 
217  const CTxMemPoolEntry::Parents& parents = stageit->GetMemPoolParentsConst();
218  for (const CTxMemPoolEntry& parent : parents) {
219  txiter parent_it = mapTx.iterator_to(parent);
220 
221  // If this is a new ancestor, add it.
222  if (setAncestors.count(parent_it) == 0) {
223  staged_ancestors.insert(parent);
224  }
225  if (staged_ancestors.size() + setAncestors.size() + entry_count > limitAncestorCount) {
226  errString = strprintf("too many unconfirmed ancestors [limit: %u]", limitAncestorCount);
227  return false;
228  }
229  }
230  }
231 
232  return true;
233 }
234 
236  uint64_t limitAncestorCount,
237  uint64_t limitAncestorSize,
238  uint64_t limitDescendantCount,
239  uint64_t limitDescendantSize,
240  std::string &errString) const
241 {
242  CTxMemPoolEntry::Parents staged_ancestors;
243  size_t total_size = 0;
244  for (const auto& tx : package) {
245  total_size += GetVirtualTransactionSize(*tx);
246  for (const auto& input : tx->vin) {
247  std::optional<txiter> piter = GetIter(input.prevout.hash);
248  if (piter) {
249  staged_ancestors.insert(**piter);
250  if (staged_ancestors.size() + package.size() > limitAncestorCount) {
251  errString = strprintf("too many unconfirmed parents [limit: %u]", limitAncestorCount);
252  return false;
253  }
254  }
255  }
256  }
257  // When multiple transactions are passed in, the ancestors and descendants of all transactions
258  // considered together must be within limits even if they are not interdependent. This may be
259  // stricter than the limits for each individual transaction.
260  setEntries setAncestors;
261  const auto ret = CalculateAncestorsAndCheckLimits(total_size, package.size(),
262  setAncestors, staged_ancestors,
263  limitAncestorCount, limitAncestorSize,
264  limitDescendantCount, limitDescendantSize, errString);
265  // It's possible to overestimate the ancestor/descendant totals.
266  if (!ret) errString.insert(0, "possibly ");
267  return ret;
268 }
269 
271  setEntries &setAncestors,
272  uint64_t limitAncestorCount,
273  uint64_t limitAncestorSize,
274  uint64_t limitDescendantCount,
275  uint64_t limitDescendantSize,
276  std::string &errString,
277  bool fSearchForParents /* = true */) const
278 {
279  CTxMemPoolEntry::Parents staged_ancestors;
280  const CTransaction &tx = entry.GetTx();
281 
282  if (fSearchForParents) {
283  // Get parents of this transaction that are in the mempool
284  // GetMemPoolParents() is only valid for entries in the mempool, so we
285  // iterate mapTx to find parents.
286  for (unsigned int i = 0; i < tx.vin.size(); i++) {
287  std::optional<txiter> piter = GetIter(tx.vin[i].prevout.hash);
288  if (piter) {
289  staged_ancestors.insert(**piter);
290  if (staged_ancestors.size() + 1 > limitAncestorCount) {
291  errString = strprintf("too many unconfirmed parents [limit: %u]", limitAncestorCount);
292  return false;
293  }
294  }
295  }
296  } else {
297  // If we're not searching for parents, we require this to already be an
298  // entry in the mempool and use the entry's cached parents.
299  txiter it = mapTx.iterator_to(entry);
300  staged_ancestors = it->GetMemPoolParentsConst();
301  }
302 
303  return CalculateAncestorsAndCheckLimits(entry.GetTxSize(), /*entry_count=*/1,
304  setAncestors, staged_ancestors,
305  limitAncestorCount, limitAncestorSize,
306  limitDescendantCount, limitDescendantSize, errString);
307 }
308 
309 void CTxMemPool::UpdateAncestorsOf(bool add, txiter it, setEntries &setAncestors)
310 {
311  const CTxMemPoolEntry::Parents& parents = it->GetMemPoolParentsConst();
312  // add or remove this tx as a child of each parent
313  for (const CTxMemPoolEntry& parent : parents) {
314  UpdateChild(mapTx.iterator_to(parent), it, add);
315  }
316  const int64_t updateCount = (add ? 1 : -1);
317  const int64_t updateSize = updateCount * it->GetTxSize();
318  const CAmount updateFee = updateCount * it->GetModifiedFee();
319  for (txiter ancestorIt : setAncestors) {
320  mapTx.modify(ancestorIt, [=](CTxMemPoolEntry& e) { e.UpdateDescendantState(updateSize, updateFee, updateCount); });
321  }
322 }
323 
325 {
326  int64_t updateCount = setAncestors.size();
327  int64_t updateSize = 0;
328  CAmount updateFee = 0;
329  int64_t updateSigOpsCost = 0;
330  for (txiter ancestorIt : setAncestors) {
331  updateSize += ancestorIt->GetTxSize();
332  updateFee += ancestorIt->GetModifiedFee();
333  updateSigOpsCost += ancestorIt->GetSigOpCost();
334  }
335  mapTx.modify(it, [=](CTxMemPoolEntry& e){ e.UpdateAncestorState(updateSize, updateFee, updateCount, updateSigOpsCost); });
336 }
337 
339 {
340  const CTxMemPoolEntry::Children& children = it->GetMemPoolChildrenConst();
341  for (const CTxMemPoolEntry& updateIt : children) {
342  UpdateParent(mapTx.iterator_to(updateIt), it, false);
343  }
344 }
345 
346 void CTxMemPool::UpdateForRemoveFromMempool(const setEntries &entriesToRemove, bool updateDescendants)
347 {
348  // For each entry, walk back all ancestors and decrement size associated with this
349  // transaction
350  const uint64_t nNoLimit = std::numeric_limits<uint64_t>::max();
351  if (updateDescendants) {
352  // updateDescendants should be true whenever we're not recursively
353  // removing a tx and all its descendants, eg when a transaction is
354  // confirmed in a block.
355  // Here we only update statistics and not data in CTxMemPool::Parents
356  // and CTxMemPoolEntry::Children (which we need to preserve until we're
357  // finished with all operations that need to traverse the mempool).
358  for (txiter removeIt : entriesToRemove) {
359  setEntries setDescendants;
360  CalculateDescendants(removeIt, setDescendants);
361  setDescendants.erase(removeIt); // don't update state for self
362  int64_t modifySize = -((int64_t)removeIt->GetTxSize());
363  CAmount modifyFee = -removeIt->GetModifiedFee();
364  int modifySigOps = -removeIt->GetSigOpCost();
365  for (txiter dit : setDescendants) {
366  mapTx.modify(dit, [=](CTxMemPoolEntry& e){ e.UpdateAncestorState(modifySize, modifyFee, -1, modifySigOps); });
367  }
368  }
369  }
370  for (txiter removeIt : entriesToRemove) {
371  setEntries setAncestors;
372  const CTxMemPoolEntry &entry = *removeIt;
373  std::string dummy;
374  // Since this is a tx that is already in the mempool, we can call CMPA
375  // with fSearchForParents = false. If the mempool is in a consistent
376  // state, then using true or false should both be correct, though false
377  // should be a bit faster.
378  // However, if we happen to be in the middle of processing a reorg, then
379  // the mempool can be in an inconsistent state. In this case, the set
380  // of ancestors reachable via GetMemPoolParents()/GetMemPoolChildren()
381  // will be the same as the set of ancestors whose packages include this
382  // transaction, because when we add a new transaction to the mempool in
383  // addUnchecked(), we assume it has no children, and in the case of a
384  // reorg where that assumption is false, the in-mempool children aren't
385  // linked to the in-block tx's until UpdateTransactionsFromBlock() is
386  // called.
387  // So if we're being called during a reorg, ie before
388  // UpdateTransactionsFromBlock() has been called, then
389  // GetMemPoolParents()/GetMemPoolChildren() will differ from the set of
390  // mempool parents we'd calculate by searching, and it's important that
391  // we use the cached notion of ancestor transactions as the set of
392  // things to update for removal.
393  CalculateMemPoolAncestors(entry, setAncestors, nNoLimit, nNoLimit, nNoLimit, nNoLimit, dummy, false);
394  // Note that UpdateAncestorsOf severs the child links that point to
395  // removeIt in the entries for the parents of removeIt.
396  UpdateAncestorsOf(false, removeIt, setAncestors);
397  }
398  // After updating all the ancestor sizes, we can now sever the link between each
399  // transaction being removed and any mempool children (ie, update CTxMemPoolEntry::m_parents
400  // for each direct child of a transaction being removed).
401  for (txiter removeIt : entriesToRemove) {
402  UpdateChildrenForRemoval(removeIt);
403  }
404 }
405 
406 void CTxMemPoolEntry::UpdateDescendantState(int64_t modifySize, CAmount modifyFee, int64_t modifyCount)
407 {
408  nSizeWithDescendants += modifySize;
409  assert(int64_t(nSizeWithDescendants) > 0);
411  nCountWithDescendants += modifyCount;
412  assert(int64_t(nCountWithDescendants) > 0);
413 }
414 
415 void CTxMemPoolEntry::UpdateAncestorState(int64_t modifySize, CAmount modifyFee, int64_t modifyCount, int64_t modifySigOps)
416 {
417  nSizeWithAncestors += modifySize;
418  assert(int64_t(nSizeWithAncestors) > 0);
420  nCountWithAncestors += modifyCount;
421  assert(int64_t(nCountWithAncestors) > 0);
422  nSigOpCostWithAncestors += modifySigOps;
423  assert(int(nSigOpCostWithAncestors) >= 0);
424 }
425 
427  : m_check_ratio{opts.check_ratio},
428  minerPolicyEstimator{opts.estimator},
429  m_max_size_bytes{opts.max_size_bytes},
430  m_expiry{opts.expiry},
431  m_incremental_relay_feerate{opts.incremental_relay_feerate},
432  m_min_relay_feerate{opts.min_relay_feerate},
433  m_dust_relay_feerate{opts.dust_relay_feerate},
434  m_permit_bare_multisig{opts.permit_bare_multisig},
435  m_max_datacarrier_bytes{opts.max_datacarrier_bytes},
436  m_require_standard{opts.require_standard},
437  m_full_rbf{opts.full_rbf},
438  m_limits{opts.limits}
439 {
440  _clear(); //lock free clear
441 }
442 
443 bool CTxMemPool::isSpent(const COutPoint& outpoint) const
444 {
445  LOCK(cs);
446  return mapNextTx.count(outpoint);
447 }
448 
450 {
451  return nTransactionsUpdated;
452 }
453 
455 {
457 }
458 
459 void CTxMemPool::addUnchecked(const CTxMemPoolEntry &entry, setEntries &setAncestors, bool validFeeEstimate)
460 {
461  // Add to memory pool without checking anything.
462  // Used by AcceptToMemoryPool(), which DOES do
463  // all the appropriate checks.
464  indexed_transaction_set::iterator newit = mapTx.insert(entry).first;
465 
466  // Update transaction for any feeDelta created by PrioritiseTransaction
467  CAmount delta{0};
468  ApplyDelta(entry.GetTx().GetHash(), delta);
469  // The following call to UpdateModifiedFee assumes no previous fee modifications
470  Assume(entry.GetFee() == entry.GetModifiedFee());
471  if (delta) {
472  mapTx.modify(newit, [&delta](CTxMemPoolEntry& e) { e.UpdateModifiedFee(delta); });
473  }
474 
475  // Update cachedInnerUsage to include contained transaction's usage.
476  // (When we update the entry for in-mempool parents, memory usage will be
477  // further updated.)
478  cachedInnerUsage += entry.DynamicMemoryUsage();
479 
480  const CTransaction& tx = newit->GetTx();
481  std::set<uint256> setParentTransactions;
482  for (unsigned int i = 0; i < tx.vin.size(); i++) {
483  mapNextTx.insert(std::make_pair(&tx.vin[i].prevout, &tx));
484  setParentTransactions.insert(tx.vin[i].prevout.hash);
485  }
486  // Don't bother worrying about child transactions of this one.
487  // Normal case of a new transaction arriving is that there can't be any
488  // children, because such children would be orphans.
489  // An exception to that is if a transaction enters that used to be in a block.
490  // In that case, our disconnect block logic will call UpdateTransactionsFromBlock
491  // to clean up the mess we're leaving here.
492 
493  // Update ancestors with information about this tx
494  for (const auto& pit : GetIterSet(setParentTransactions)) {
495  UpdateParent(newit, pit, true);
496  }
497  UpdateAncestorsOf(true, newit, setAncestors);
498  UpdateEntryForAncestors(newit, setAncestors);
499 
501  totalTxSize += entry.GetTxSize();
502  m_total_fee += entry.GetFee();
503  if (minerPolicyEstimator) {
504  minerPolicyEstimator->processTransaction(entry, validFeeEstimate);
505  }
506 
507  vTxHashes.emplace_back(tx.GetWitnessHash(), newit);
508  newit->vTxHashesIdx = vTxHashes.size() - 1;
509 }
510 
512 {
513  // We increment mempool sequence value no matter removal reason
514  // even if not directly reported below.
515  uint64_t mempool_sequence = GetAndIncrementSequence();
516 
517  if (reason != MemPoolRemovalReason::BLOCK) {
518  // Notify clients that a transaction has been removed from the mempool
519  // for any reason except being included in a block. Clients interested
520  // in transactions included in blocks can subscribe to the BlockConnected
521  // notification.
522  GetMainSignals().TransactionRemovedFromMempool(it->GetSharedTx(), reason, mempool_sequence);
523  }
524 
525  const uint256 hash = it->GetTx().GetHash();
526  for (const CTxIn& txin : it->GetTx().vin)
527  mapNextTx.erase(txin.prevout);
528 
529  RemoveUnbroadcastTx(hash, true /* add logging because unchecked */ );
530 
531  if (vTxHashes.size() > 1) {
532  vTxHashes[it->vTxHashesIdx] = std::move(vTxHashes.back());
533  vTxHashes[it->vTxHashesIdx].second->vTxHashesIdx = it->vTxHashesIdx;
534  vTxHashes.pop_back();
535  if (vTxHashes.size() * 2 < vTxHashes.capacity())
536  vTxHashes.shrink_to_fit();
537  } else
538  vTxHashes.clear();
539 
540  totalTxSize -= it->GetTxSize();
541  m_total_fee -= it->GetFee();
542  cachedInnerUsage -= it->DynamicMemoryUsage();
543  cachedInnerUsage -= memusage::DynamicUsage(it->GetMemPoolParentsConst()) + memusage::DynamicUsage(it->GetMemPoolChildrenConst());
544  mapTx.erase(it);
547 }
548 
549 // Calculates descendants of entry that are not already in setDescendants, and adds to
550 // setDescendants. Assumes entryit is already a tx in the mempool and CTxMemPoolEntry::m_children
551 // is correct for tx and all descendants.
552 // Also assumes that if an entry is in setDescendants already, then all
553 // in-mempool descendants of it are already in setDescendants as well, so that we
554 // can save time by not iterating over those entries.
555 void CTxMemPool::CalculateDescendants(txiter entryit, setEntries& setDescendants) const
556 {
557  setEntries stage;
558  if (setDescendants.count(entryit) == 0) {
559  stage.insert(entryit);
560  }
561  // Traverse down the children of entry, only adding children that are not
562  // accounted for in setDescendants already (because those children have either
563  // already been walked, or will be walked in this iteration).
564  while (!stage.empty()) {
565  txiter it = *stage.begin();
566  setDescendants.insert(it);
567  stage.erase(it);
568 
569  const CTxMemPoolEntry::Children& children = it->GetMemPoolChildrenConst();
570  for (const CTxMemPoolEntry& child : children) {
571  txiter childiter = mapTx.iterator_to(child);
572  if (!setDescendants.count(childiter)) {
573  stage.insert(childiter);
574  }
575  }
576  }
577 }
578 
580 {
581  // Remove transaction from memory pool
583  setEntries txToRemove;
584  txiter origit = mapTx.find(origTx.GetHash());
585  if (origit != mapTx.end()) {
586  txToRemove.insert(origit);
587  } else {
588  // When recursively removing but origTx isn't in the mempool
589  // be sure to remove any children that are in the pool. This can
590  // happen during chain re-orgs if origTx isn't re-accepted into
591  // the mempool for any reason.
592  for (unsigned int i = 0; i < origTx.vout.size(); i++) {
593  auto it = mapNextTx.find(COutPoint(origTx.GetHash(), i));
594  if (it == mapNextTx.end())
595  continue;
596  txiter nextit = mapTx.find(it->second->GetHash());
597  assert(nextit != mapTx.end());
598  txToRemove.insert(nextit);
599  }
600  }
601  setEntries setAllRemoves;
602  for (txiter it : txToRemove) {
603  CalculateDescendants(it, setAllRemoves);
604  }
605 
606  RemoveStaged(setAllRemoves, false, reason);
607 }
608 
609 void CTxMemPool::removeForReorg(CChain& chain, std::function<bool(txiter)> check_final_and_mature)
610 {
611  // Remove transactions spending a coinbase which are now immature and no-longer-final transactions
614 
615  setEntries txToRemove;
616  for (indexed_transaction_set::const_iterator it = mapTx.begin(); it != mapTx.end(); it++) {
617  if (check_final_and_mature(it)) txToRemove.insert(it);
618  }
619  setEntries setAllRemoves;
620  for (txiter it : txToRemove) {
621  CalculateDescendants(it, setAllRemoves);
622  }
623  RemoveStaged(setAllRemoves, false, MemPoolRemovalReason::REORG);
624  for (indexed_transaction_set::const_iterator it = mapTx.begin(); it != mapTx.end(); it++) {
625  assert(TestLockPointValidity(chain, it->GetLockPoints()));
626  }
627 }
628 
630 {
631  // Remove transactions which depend on inputs of tx, recursively
633  for (const CTxIn &txin : tx.vin) {
634  auto it = mapNextTx.find(txin.prevout);
635  if (it != mapNextTx.end()) {
636  const CTransaction &txConflict = *it->second;
637  if (txConflict != tx)
638  {
639  ClearPrioritisation(txConflict.GetHash());
641  }
642  }
643  }
644 }
645 
649 void CTxMemPool::removeForBlock(const std::vector<CTransactionRef>& vtx, unsigned int nBlockHeight)
650 {
652  std::vector<const CTxMemPoolEntry*> entries;
653  for (const auto& tx : vtx)
654  {
655  uint256 hash = tx->GetHash();
656 
657  indexed_transaction_set::iterator i = mapTx.find(hash);
658  if (i != mapTx.end())
659  entries.push_back(&*i);
660  }
661  // Before the txs in the new block have been removed from the mempool, update policy estimates
662  if (minerPolicyEstimator) {minerPolicyEstimator->processBlock(nBlockHeight, entries);}
663  for (const auto& tx : vtx)
664  {
665  txiter it = mapTx.find(tx->GetHash());
666  if (it != mapTx.end()) {
667  setEntries stage;
668  stage.insert(it);
670  }
671  removeConflicts(*tx);
673  }
674  lastRollingFeeUpdate = GetTime();
675  blockSinceLastRollingFeeBump = true;
676 }
677 
679 {
680  vTxHashes.clear();
681  mapTx.clear();
682  mapNextTx.clear();
683  totalTxSize = 0;
684  m_total_fee = 0;
685  cachedInnerUsage = 0;
686  lastRollingFeeUpdate = GetTime();
687  blockSinceLastRollingFeeBump = false;
688  rollingMinimumFeeRate = 0;
690 }
691 
693 {
694  LOCK(cs);
695  _clear();
696 }
697 
698 void CTxMemPool::check(const CCoinsViewCache& active_coins_tip, int64_t spendheight) const
699 {
700  if (m_check_ratio == 0) return;
701 
702  if (GetRand(m_check_ratio) >= 1) return;
703 
705  LOCK(cs);
706  LogPrint(BCLog::MEMPOOL, "Checking mempool with %u transactions and %u inputs\n", (unsigned int)mapTx.size(), (unsigned int)mapNextTx.size());
707 
708  uint64_t checkTotal = 0;
709  CAmount check_total_fee{0};
710  uint64_t innerUsage = 0;
711  uint64_t prev_ancestor_count{0};
712 
713  CCoinsViewCache mempoolDuplicate(const_cast<CCoinsViewCache*>(&active_coins_tip));
714 
715  for (const auto& it : GetSortedDepthAndScore()) {
716  checkTotal += it->GetTxSize();
717  check_total_fee += it->GetFee();
718  innerUsage += it->DynamicMemoryUsage();
719  const CTransaction& tx = it->GetTx();
720  innerUsage += memusage::DynamicUsage(it->GetMemPoolParentsConst()) + memusage::DynamicUsage(it->GetMemPoolChildrenConst());
721  CTxMemPoolEntry::Parents setParentCheck;
722  for (const CTxIn &txin : tx.vin) {
723  // Check that every mempool transaction's inputs refer to available coins, or other mempool tx's.
724  indexed_transaction_set::const_iterator it2 = mapTx.find(txin.prevout.hash);
725  if (it2 != mapTx.end()) {
726  const CTransaction& tx2 = it2->GetTx();
727  assert(tx2.vout.size() > txin.prevout.n && !tx2.vout[txin.prevout.n].IsNull());
728  setParentCheck.insert(*it2);
729  }
730  // We are iterating through the mempool entries sorted in order by ancestor count.
731  // All parents must have been checked before their children and their coins added to
732  // the mempoolDuplicate coins cache.
733  assert(mempoolDuplicate.HaveCoin(txin.prevout));
734  // Check whether its inputs are marked in mapNextTx.
735  auto it3 = mapNextTx.find(txin.prevout);
736  assert(it3 != mapNextTx.end());
737  assert(it3->first == &txin.prevout);
738  assert(it3->second == &tx);
739  }
740  auto comp = [](const CTxMemPoolEntry& a, const CTxMemPoolEntry& b) -> bool {
741  return a.GetTx().GetHash() == b.GetTx().GetHash();
742  };
743  assert(setParentCheck.size() == it->GetMemPoolParentsConst().size());
744  assert(std::equal(setParentCheck.begin(), setParentCheck.end(), it->GetMemPoolParentsConst().begin(), comp));
745  // Verify ancestor state is correct.
746  setEntries setAncestors;
747  uint64_t nNoLimit = std::numeric_limits<uint64_t>::max();
748  std::string dummy;
749  CalculateMemPoolAncestors(*it, setAncestors, nNoLimit, nNoLimit, nNoLimit, nNoLimit, dummy);
750  uint64_t nCountCheck = setAncestors.size() + 1;
751  uint64_t nSizeCheck = it->GetTxSize();
752  CAmount nFeesCheck = it->GetModifiedFee();
753  int64_t nSigOpCheck = it->GetSigOpCost();
754 
755  for (txiter ancestorIt : setAncestors) {
756  nSizeCheck += ancestorIt->GetTxSize();
757  nFeesCheck += ancestorIt->GetModifiedFee();
758  nSigOpCheck += ancestorIt->GetSigOpCost();
759  }
760 
761  assert(it->GetCountWithAncestors() == nCountCheck);
762  assert(it->GetSizeWithAncestors() == nSizeCheck);
763  assert(it->GetSigOpCostWithAncestors() == nSigOpCheck);
764  assert(it->GetModFeesWithAncestors() == nFeesCheck);
765  // Sanity check: we are walking in ascending ancestor count order.
766  assert(prev_ancestor_count <= it->GetCountWithAncestors());
767  prev_ancestor_count = it->GetCountWithAncestors();
768 
769  // Check children against mapNextTx
770  CTxMemPoolEntry::Children setChildrenCheck;
771  auto iter = mapNextTx.lower_bound(COutPoint(it->GetTx().GetHash(), 0));
772  uint64_t child_sizes = 0;
773  for (; iter != mapNextTx.end() && iter->first->hash == it->GetTx().GetHash(); ++iter) {
774  txiter childit = mapTx.find(iter->second->GetHash());
775  assert(childit != mapTx.end()); // mapNextTx points to in-mempool transactions
776  if (setChildrenCheck.insert(*childit).second) {
777  child_sizes += childit->GetTxSize();
778  }
779  }
780  assert(setChildrenCheck.size() == it->GetMemPoolChildrenConst().size());
781  assert(std::equal(setChildrenCheck.begin(), setChildrenCheck.end(), it->GetMemPoolChildrenConst().begin(), comp));
782  // Also check to make sure size is greater than sum with immediate children.
783  // just a sanity check, not definitive that this calc is correct...
784  assert(it->GetSizeWithDescendants() >= child_sizes + it->GetTxSize());
785 
786  TxValidationState dummy_state; // Not used. CheckTxInputs() should always pass
787  CAmount txfee = 0;
788  assert(!tx.IsCoinBase());
789  assert(Consensus::CheckTxInputs(tx, dummy_state, mempoolDuplicate, spendheight, txfee));
790  for (const auto& input: tx.vin) mempoolDuplicate.SpendCoin(input.prevout);
791  AddCoins(mempoolDuplicate, tx, std::numeric_limits<int>::max());
792  }
793  for (auto it = mapNextTx.cbegin(); it != mapNextTx.cend(); it++) {
794  uint256 hash = it->second->GetHash();
795  indexed_transaction_set::const_iterator it2 = mapTx.find(hash);
796  const CTransaction& tx = it2->GetTx();
797  assert(it2 != mapTx.end());
798  assert(&tx == it->second);
799  }
800 
801  assert(totalTxSize == checkTotal);
802  assert(m_total_fee == check_total_fee);
803  assert(innerUsage == cachedInnerUsage);
804 }
805 
806 bool CTxMemPool::CompareDepthAndScore(const uint256& hasha, const uint256& hashb, bool wtxid)
807 {
808  LOCK(cs);
809  indexed_transaction_set::const_iterator i = wtxid ? get_iter_from_wtxid(hasha) : mapTx.find(hasha);
810  if (i == mapTx.end()) return false;
811  indexed_transaction_set::const_iterator j = wtxid ? get_iter_from_wtxid(hashb) : mapTx.find(hashb);
812  if (j == mapTx.end()) return true;
813  uint64_t counta = i->GetCountWithAncestors();
814  uint64_t countb = j->GetCountWithAncestors();
815  if (counta == countb) {
816  return CompareTxMemPoolEntryByScore()(*i, *j);
817  }
818  return counta < countb;
819 }
820 
821 namespace {
822 class DepthAndScoreComparator
823 {
824 public:
825  bool operator()(const CTxMemPool::indexed_transaction_set::const_iterator& a, const CTxMemPool::indexed_transaction_set::const_iterator& b)
826  {
827  uint64_t counta = a->GetCountWithAncestors();
828  uint64_t countb = b->GetCountWithAncestors();
829  if (counta == countb) {
830  return CompareTxMemPoolEntryByScore()(*a, *b);
831  }
832  return counta < countb;
833  }
834 };
835 } // namespace
836 
837 std::vector<CTxMemPool::indexed_transaction_set::const_iterator> CTxMemPool::GetSortedDepthAndScore() const
838 {
839  std::vector<indexed_transaction_set::const_iterator> iters;
841 
842  iters.reserve(mapTx.size());
843 
844  for (indexed_transaction_set::iterator mi = mapTx.begin(); mi != mapTx.end(); ++mi) {
845  iters.push_back(mi);
846  }
847  std::sort(iters.begin(), iters.end(), DepthAndScoreComparator());
848  return iters;
849 }
850 
851 void CTxMemPool::queryHashes(std::vector<uint256>& vtxid) const
852 {
853  LOCK(cs);
854  auto iters = GetSortedDepthAndScore();
855 
856  vtxid.clear();
857  vtxid.reserve(mapTx.size());
858 
859  for (auto it : iters) {
860  vtxid.push_back(it->GetTx().GetHash());
861  }
862 }
863 
864 static TxMempoolInfo GetInfo(CTxMemPool::indexed_transaction_set::const_iterator it) {
865  return TxMempoolInfo{it->GetSharedTx(), it->GetTime(), it->GetFee(), it->GetTxSize(), it->GetModifiedFee() - it->GetFee()};
866 }
867 
868 std::vector<TxMempoolInfo> CTxMemPool::infoAll() const
869 {
870  LOCK(cs);
871  auto iters = GetSortedDepthAndScore();
872 
873  std::vector<TxMempoolInfo> ret;
874  ret.reserve(mapTx.size());
875  for (auto it : iters) {
876  ret.push_back(GetInfo(it));
877  }
878 
879  return ret;
880 }
881 
883 {
884  LOCK(cs);
885  indexed_transaction_set::const_iterator i = mapTx.find(hash);
886  if (i == mapTx.end())
887  return nullptr;
888  return i->GetSharedTx();
889 }
890 
892 {
893  LOCK(cs);
894  indexed_transaction_set::const_iterator i = (gtxid.IsWtxid() ? get_iter_from_wtxid(gtxid.GetHash()) : mapTx.find(gtxid.GetHash()));
895  if (i == mapTx.end())
896  return TxMempoolInfo();
897  return GetInfo(i);
898 }
899 
900 void CTxMemPool::PrioritiseTransaction(const uint256& hash, const CAmount& nFeeDelta)
901 {
902  {
903  LOCK(cs);
904  CAmount &delta = mapDeltas[hash];
905  delta = SaturatingAdd(delta, nFeeDelta);
906  txiter it = mapTx.find(hash);
907  if (it != mapTx.end()) {
908  mapTx.modify(it, [&nFeeDelta](CTxMemPoolEntry& e) { e.UpdateModifiedFee(nFeeDelta); });
909  // Now update all ancestors' modified fees with descendants
910  setEntries setAncestors;
911  uint64_t nNoLimit = std::numeric_limits<uint64_t>::max();
912  std::string dummy;
913  CalculateMemPoolAncestors(*it, setAncestors, nNoLimit, nNoLimit, nNoLimit, nNoLimit, dummy, false);
914  for (txiter ancestorIt : setAncestors) {
915  mapTx.modify(ancestorIt, [=](CTxMemPoolEntry& e){ e.UpdateDescendantState(0, nFeeDelta, 0);});
916  }
917  // Now update all descendants' modified fees with ancestors
918  setEntries setDescendants;
919  CalculateDescendants(it, setDescendants);
920  setDescendants.erase(it);
921  for (txiter descendantIt : setDescendants) {
922  mapTx.modify(descendantIt, [=](CTxMemPoolEntry& e){ e.UpdateAncestorState(0, nFeeDelta, 0, 0); });
923  }
925  }
926  }
927  LogPrintf("PrioritiseTransaction: %s fee += %s\n", hash.ToString(), FormatMoney(nFeeDelta));
928 }
929 
930 void CTxMemPool::ApplyDelta(const uint256& hash, CAmount &nFeeDelta) const
931 {
933  std::map<uint256, CAmount>::const_iterator pos = mapDeltas.find(hash);
934  if (pos == mapDeltas.end())
935  return;
936  const CAmount &delta = pos->second;
937  nFeeDelta += delta;
938 }
939 
941 {
943  mapDeltas.erase(hash);
944 }
945 
947 {
948  const auto it = mapNextTx.find(prevout);
949  return it == mapNextTx.end() ? nullptr : it->second;
950 }
951 
952 std::optional<CTxMemPool::txiter> CTxMemPool::GetIter(const uint256& txid) const
953 {
954  auto it = mapTx.find(txid);
955  if (it != mapTx.end()) return it;
956  return std::nullopt;
957 }
958 
959 CTxMemPool::setEntries CTxMemPool::GetIterSet(const std::set<uint256>& hashes) const
960 {
962  for (const auto& h : hashes) {
963  const auto mi = GetIter(h);
964  if (mi) ret.insert(*mi);
965  }
966  return ret;
967 }
968 
970 {
971  for (unsigned int i = 0; i < tx.vin.size(); i++)
972  if (exists(GenTxid::Txid(tx.vin[i].prevout.hash)))
973  return false;
974  return true;
975 }
976 
977 CCoinsViewMemPool::CCoinsViewMemPool(CCoinsView* baseIn, const CTxMemPool& mempoolIn) : CCoinsViewBacked(baseIn), mempool(mempoolIn) { }
978 
979 bool CCoinsViewMemPool::GetCoin(const COutPoint &outpoint, Coin &coin) const {
980  // Check to see if the inputs are made available by another tx in the package.
981  // These Coins would not be available in the underlying CoinsView.
982  if (auto it = m_temp_added.find(outpoint); it != m_temp_added.end()) {
983  coin = it->second;
984  return true;
985  }
986 
987  // If an entry in the mempool exists, always return that one, as it's guaranteed to never
988  // conflict with the underlying cache, and it cannot have pruned entries (as it contains full)
989  // transactions. First checking the underlying cache risks returning a pruned entry instead.
990  CTransactionRef ptx = mempool.get(outpoint.hash);
991  if (ptx) {
992  if (outpoint.n < ptx->vout.size()) {
993  coin = Coin(ptx->vout[outpoint.n], MEMPOOL_HEIGHT, false);
994  return true;
995  } else {
996  return false;
997  }
998  }
999  return base->GetCoin(outpoint, coin);
1000 }
1001 
1003 {
1004  for (unsigned int n = 0; n < tx->vout.size(); ++n) {
1005  m_temp_added.emplace(COutPoint(tx->GetHash(), n), Coin(tx->vout[n], MEMPOOL_HEIGHT, false));
1006  }
1007 }
1008 
1010  LOCK(cs);
1011  // Estimate the overhead of mapTx to be 15 pointers + an allocation, as no exact formula for boost::multi_index_contained is implemented.
1012  return memusage::MallocUsage(sizeof(CTxMemPoolEntry) + 15 * sizeof(void*)) * mapTx.size() + memusage::DynamicUsage(mapNextTx) + memusage::DynamicUsage(mapDeltas) + memusage::DynamicUsage(vTxHashes) + cachedInnerUsage;
1013 }
1014 
1015 void CTxMemPool::RemoveUnbroadcastTx(const uint256& txid, const bool unchecked) {
1016  LOCK(cs);
1017 
1018  if (m_unbroadcast_txids.erase(txid))
1019  {
1020  LogPrint(BCLog::MEMPOOL, "Removed %i from set of unbroadcast txns%s\n", txid.GetHex(), (unchecked ? " before confirmation that txn was sent out" : ""));
1021  }
1022 }
1023 
1024 void CTxMemPool::RemoveStaged(setEntries &stage, bool updateDescendants, MemPoolRemovalReason reason) {
1025  AssertLockHeld(cs);
1026  UpdateForRemoveFromMempool(stage, updateDescendants);
1027  for (txiter it : stage) {
1028  removeUnchecked(it, reason);
1029  }
1030 }
1031 
1032 int CTxMemPool::Expire(std::chrono::seconds time)
1033 {
1034  AssertLockHeld(cs);
1035  indexed_transaction_set::index<entry_time>::type::iterator it = mapTx.get<entry_time>().begin();
1036  setEntries toremove;
1037  while (it != mapTx.get<entry_time>().end() && it->GetTime() < time) {
1038  toremove.insert(mapTx.project<0>(it));
1039  it++;
1040  }
1041  setEntries stage;
1042  for (txiter removeit : toremove) {
1043  CalculateDescendants(removeit, stage);
1044  }
1046  return stage.size();
1047 }
1048 
1049 void CTxMemPool::addUnchecked(const CTxMemPoolEntry &entry, bool validFeeEstimate)
1050 {
1051  setEntries setAncestors;
1052  uint64_t nNoLimit = std::numeric_limits<uint64_t>::max();
1053  std::string dummy;
1054  CalculateMemPoolAncestors(entry, setAncestors, nNoLimit, nNoLimit, nNoLimit, nNoLimit, dummy);
1055  return addUnchecked(entry, setAncestors, validFeeEstimate);
1056 }
1057 
1058 void CTxMemPool::UpdateChild(txiter entry, txiter child, bool add)
1059 {
1060  AssertLockHeld(cs);
1062  if (add && entry->GetMemPoolChildren().insert(*child).second) {
1063  cachedInnerUsage += memusage::IncrementalDynamicUsage(s);
1064  } else if (!add && entry->GetMemPoolChildren().erase(*child)) {
1065  cachedInnerUsage -= memusage::IncrementalDynamicUsage(s);
1066  }
1067 }
1068 
1069 void CTxMemPool::UpdateParent(txiter entry, txiter parent, bool add)
1070 {
1071  AssertLockHeld(cs);
1073  if (add && entry->GetMemPoolParents().insert(*parent).second) {
1074  cachedInnerUsage += memusage::IncrementalDynamicUsage(s);
1075  } else if (!add && entry->GetMemPoolParents().erase(*parent)) {
1076  cachedInnerUsage -= memusage::IncrementalDynamicUsage(s);
1077  }
1078 }
1079 
1080 CFeeRate CTxMemPool::GetMinFee(size_t sizelimit) const {
1081  LOCK(cs);
1082  if (!blockSinceLastRollingFeeBump || rollingMinimumFeeRate == 0)
1083  return CFeeRate(llround(rollingMinimumFeeRate));
1084 
1085  int64_t time = GetTime();
1086  if (time > lastRollingFeeUpdate + 10) {
1087  double halflife = ROLLING_FEE_HALFLIFE;
1088  if (DynamicMemoryUsage() < sizelimit / 4)
1089  halflife /= 4;
1090  else if (DynamicMemoryUsage() < sizelimit / 2)
1091  halflife /= 2;
1092 
1093  rollingMinimumFeeRate = rollingMinimumFeeRate / pow(2.0, (time - lastRollingFeeUpdate) / halflife);
1094  lastRollingFeeUpdate = time;
1095 
1096  if (rollingMinimumFeeRate < (double)m_incremental_relay_feerate.GetFeePerK() / 2) {
1097  rollingMinimumFeeRate = 0;
1098  return CFeeRate(0);
1099  }
1100  }
1101  return std::max(CFeeRate(llround(rollingMinimumFeeRate)), m_incremental_relay_feerate);
1102 }
1103 
1105  AssertLockHeld(cs);
1106  if (rate.GetFeePerK() > rollingMinimumFeeRate) {
1107  rollingMinimumFeeRate = rate.GetFeePerK();
1108  blockSinceLastRollingFeeBump = false;
1109  }
1110 }
1111 
1112 void CTxMemPool::TrimToSize(size_t sizelimit, std::vector<COutPoint>* pvNoSpendsRemaining) {
1113  AssertLockHeld(cs);
1114 
1115  unsigned nTxnRemoved = 0;
1116  CFeeRate maxFeeRateRemoved(0);
1117  while (!mapTx.empty() && DynamicMemoryUsage() > sizelimit) {
1118  indexed_transaction_set::index<descendant_score>::type::iterator it = mapTx.get<descendant_score>().begin();
1119 
1120  // We set the new mempool min fee to the feerate of the removed set, plus the
1121  // "minimum reasonable fee rate" (ie some value under which we consider txn
1122  // to have 0 fee). This way, we don't allow txn to enter mempool with feerate
1123  // equal to txn which were removed with no block in between.
1124  CFeeRate removed(it->GetModFeesWithDescendants(), it->GetSizeWithDescendants());
1125  removed += m_incremental_relay_feerate;
1126  trackPackageRemoved(removed);
1127  maxFeeRateRemoved = std::max(maxFeeRateRemoved, removed);
1128 
1129  setEntries stage;
1130  CalculateDescendants(mapTx.project<0>(it), stage);
1131  nTxnRemoved += stage.size();
1132 
1133  std::vector<CTransaction> txn;
1134  if (pvNoSpendsRemaining) {
1135  txn.reserve(stage.size());
1136  for (txiter iter : stage)
1137  txn.push_back(iter->GetTx());
1138  }
1140  if (pvNoSpendsRemaining) {
1141  for (const CTransaction& tx : txn) {
1142  for (const CTxIn& txin : tx.vin) {
1143  if (exists(GenTxid::Txid(txin.prevout.hash))) continue;
1144  pvNoSpendsRemaining->push_back(txin.prevout);
1145  }
1146  }
1147  }
1148  }
1149 
1150  if (maxFeeRateRemoved > CFeeRate(0)) {
1151  LogPrint(BCLog::MEMPOOL, "Removed %u txn, rolling minimum fee bumped to %s\n", nTxnRemoved, maxFeeRateRemoved.ToString());
1152  }
1153 }
1154 
1156  // find parent with highest descendant count
1157  std::vector<txiter> candidates;
1158  setEntries counted;
1159  candidates.push_back(entry);
1160  uint64_t maximum = 0;
1161  while (candidates.size()) {
1162  txiter candidate = candidates.back();
1163  candidates.pop_back();
1164  if (!counted.insert(candidate).second) continue;
1165  const CTxMemPoolEntry::Parents& parents = candidate->GetMemPoolParentsConst();
1166  if (parents.size() == 0) {
1167  maximum = std::max(maximum, candidate->GetCountWithDescendants());
1168  } else {
1169  for (const CTxMemPoolEntry& i : parents) {
1170  candidates.push_back(mapTx.iterator_to(i));
1171  }
1172  }
1173  }
1174  return maximum;
1175 }
1176 
1177 void CTxMemPool::GetTransactionAncestry(const uint256& txid, size_t& ancestors, size_t& descendants, size_t* const ancestorsize, CAmount* const ancestorfees) const {
1178  LOCK(cs);
1179  auto it = mapTx.find(txid);
1180  ancestors = descendants = 0;
1181  if (it != mapTx.end()) {
1182  ancestors = it->GetCountWithAncestors();
1183  if (ancestorsize) *ancestorsize = it->GetSizeWithAncestors();
1184  if (ancestorfees) *ancestorfees = it->GetModFeesWithAncestors();
1185  descendants = CalculateDescendantMaximum(it);
1186  }
1187 }
1188 
1190 {
1191  LOCK(cs);
1192  return m_load_tried;
1193 }
1194 
1195 void CTxMemPool::SetLoadTried(bool load_tried)
1196 {
1197  LOCK(cs);
1198  m_load_tried = load_tried;
1199 }
int64_t CAmount
Amount in satoshis (Can be negative)
Definition: amount.h:12
int ret
RecursiveMutex cs_main
Mutex to guard access to validation specific variables, such as reading or changing the chainstate.
Definition: validation.cpp:121
#define Assume(val)
Assume is the identity function.
Definition: check.h:86
void processTransaction(const CTxMemPoolEntry &entry, bool validFeeEstimate) EXCLUSIVE_LOCKS_REQUIRED(!m_cs_fee_estimator)
Process a transaction accepted to the mempool.
Definition: fees.cpp:557
void processBlock(unsigned int nBlockHeight, std::vector< const CTxMemPoolEntry * > &entries) EXCLUSIVE_LOCKS_REQUIRED(!m_cs_fee_estimator)
Process all the transactions that have been included in a block.
Definition: fees.cpp:624
bool removeTx(uint256 hash, bool inBlock) EXCLUSIVE_LOCKS_REQUIRED(!m_cs_fee_estimator)
Remove a transaction from the mempool tracking stats.
Definition: fees.cpp:509
An in-memory indexed chain of blocks.
Definition: chain.h:423
bool Contains(const CBlockIndex *pindex) const
Efficiently check whether a block is present in this chain.
Definition: chain.h:453
CCoinsView backed by another CCoinsView.
Definition: coins.h:194
CCoinsView * base
Definition: coins.h:196
CCoinsView that adds a memory cache for transactions to another CCoinsView.
Definition: coins.h:213
Abstract view on the open txout dataset.
Definition: coins.h:157
virtual bool GetCoin(const COutPoint &outpoint, Coin &coin) const
Retrieve the Coin (unspent transaction output) for a given outpoint.
Definition: coins.cpp:13
bool GetCoin(const COutPoint &outpoint, Coin &coin) const override
Retrieve the Coin (unspent transaction output) for a given outpoint.
Definition: txmempool.cpp:979
std::unordered_map< COutPoint, Coin, SaltedOutpointHasher > m_temp_added
Coins made available by transactions being validated.
Definition: txmempool.h:913
CCoinsViewMemPool(CCoinsView *baseIn, const CTxMemPool &mempoolIn)
Definition: txmempool.cpp:977
void PackageAddTransaction(const CTransactionRef &tx)
Add the coins created by this transaction.
Definition: txmempool.cpp:1002
const CTxMemPool & mempool
Definition: txmempool.h:915
Fee rate in satoshis per kilovirtualbyte: CAmount / kvB.
Definition: feerate.h:33
std::string ToString(const FeeEstimateMode &fee_estimate_mode=FeeEstimateMode::BTC_KVB) const
Definition: feerate.cpp:39
CAmount GetFeePerK() const
Return the fee in satoshis for a vsize of 1000 vbytes.
Definition: feerate.h:65
void TransactionRemovedFromMempool(const CTransactionRef &, MemPoolRemovalReason, uint64_t mempool_sequence)
An outpoint - a combination of a transaction hash and an index n into its vout.
Definition: transaction.h:35
uint32_t n
Definition: transaction.h:38
uint256 hash
Definition: transaction.h:37
The basic transaction that is broadcasted on the network and contained in blocks.
Definition: transaction.h:288
const std::vector< CTxOut > vout
Definition: transaction.h:299
const uint256 & GetHash() const
Definition: transaction.h:330
bool IsCoinBase() const
Definition: transaction.h:343
const std::vector< CTxIn > vin
Definition: transaction.h:298
const uint256 & GetWitnessHash() const
Definition: transaction.h:331
An input of a transaction.
Definition: transaction.h:74
COutPoint prevout
Definition: transaction.h:76
CTxMemPoolEntry stores data about the corresponding transaction, as well as data about all in-mempool...
Definition: txmempool.h:89
CTxMemPoolEntry(const CTransactionRef &tx, CAmount fee, int64_t time, unsigned int entry_height, bool spends_coinbase, int64_t sigops_cost, LockPoints lp)
Definition: txmempool.cpp:44
CAmount m_modified_fee
Used for determining the priority of the transaction for mining in a block.
Definition: txmempool.h:107
const int64_t sigOpCost
Total sigop cost.
Definition: txmempool.h:106
const size_t nTxWeight
... and avoid recomputing tx weight (also used for GetTxSize())
Definition: txmempool.h:101
int64_t nSigOpCostWithAncestors
Definition: txmempool.h:121
const CTransaction & GetTx() const
Definition: txmempool.h:129
void UpdateDescendantState(int64_t modifySize, CAmount modifyFee, int64_t modifyCount)
Definition: txmempool.cpp:406
void UpdateLockPoints(const LockPoints &lp)
Definition: txmempool.cpp:70
CAmount nModFeesWithAncestors
Definition: txmempool.h:120
uint64_t nCountWithDescendants
number of descendant transactions
Definition: txmempool.h:113
size_t GetTxSize() const
Definition: txmempool.cpp:75
void UpdateAncestorState(int64_t modifySize, CAmount modifyFee, int64_t modifyCount, int64_t modifySigOps)
Definition: txmempool.cpp:415
uint64_t nSizeWithDescendants
... and size
Definition: txmempool.h:114
void UpdateModifiedFee(CAmount fee_diff)
Definition: txmempool.cpp:63
size_t DynamicMemoryUsage() const
Definition: txmempool.h:138
std::set< CTxMemPoolEntryRef, CompareIteratorByHash > Children
Definition: txmempool.h:94
CAmount nModFeesWithDescendants
... and total fees (all including us)
Definition: txmempool.h:115
uint64_t nCountWithAncestors
Definition: txmempool.h:118
LockPoints lockPoints
Track the height and time at which tx was final.
Definition: txmempool.h:108
CAmount GetModifiedFee() const
Definition: txmempool.h:137
uint64_t nSizeWithAncestors
Definition: txmempool.h:119
const CAmount & GetFee() const
Definition: txmempool.h:131
const Children & GetMemPoolChildrenConst() const
Definition: txmempool.h:162
std::set< CTxMemPoolEntryRef, CompareIteratorByHash > Parents
Definition: txmempool.h:93
CTxMemPool stores valid-according-to-the-current-best-chain transactions that may be included in the ...
Definition: txmempool.h:432
void removeConflicts(const CTransaction &tx) EXCLUSIVE_LOCKS_REQUIRED(cs)
Definition: txmempool.cpp:629
std::atomic< unsigned int > nTransactionsUpdated
Used by getblocktemplate to trigger CreateNewBlock() invocation.
Definition: txmempool.h:435
void RemoveUnbroadcastTx(const uint256 &txid, const bool unchecked=false)
Removes a transaction from the unbroadcast set.
Definition: txmempool.cpp:1015
void PrioritiseTransaction(const uint256 &hash, const CAmount &nFeeDelta)
Affect CreateNewBlock prioritisation of transactions.
Definition: txmempool.cpp:900
bool HasNoInputsOf(const CTransaction &tx) const EXCLUSIVE_LOCKS_REQUIRED(cs)
Check that none of this transactions inputs are in the mempool, and thus the tx is not dependent on o...
Definition: txmempool.cpp:969
void UpdateEntryForAncestors(txiter it, const setEntries &setAncestors) EXCLUSIVE_LOCKS_REQUIRED(cs)
Set ancestor state for an entry.
Definition: txmempool.cpp:324
bool GetLoadTried() const
Definition: txmempool.cpp:1189
bool visited(const txiter it) const EXCLUSIVE_LOCKS_REQUIRED(cs
visited marks a CTxMemPoolEntry as having been traversed during the lifetime of the most recently cre...
CFeeRate GetMinFee() const
The minimum fee to get into the mempool, which may itself not be enough for larger-sized transactions...
Definition: txmempool.h:716
RecursiveMutex cs
This mutex needs to be locked when accessing mapTx or other members that are guarded by it.
Definition: txmempool.h:521
void ClearPrioritisation(const uint256 &hash) EXCLUSIVE_LOCKS_REQUIRED(cs)
Definition: txmempool.cpp:940
void trackPackageRemoved(const CFeeRate &rate) EXCLUSIVE_LOCKS_REQUIRED(cs)
Definition: txmempool.cpp:1104
void removeRecursive(const CTransaction &tx, MemPoolRemovalReason reason) EXCLUSIVE_LOCKS_REQUIRED(cs)
Definition: txmempool.cpp:579
void check(const CCoinsViewCache &active_coins_tip, int64_t spendheight) const EXCLUSIVE_LOCKS_REQUIRED(void addUnchecked(const CTxMemPoolEntry &entry, bool validFeeEstimate=true) EXCLUSIVE_LOCKS_REQUIRED(cs
If sanity-checking is turned on, check makes sure the pool is consistent (does not contain two transa...
Definition: txmempool.h:605
const int m_check_ratio
Value n means that 1 times in n we check.
Definition: txmempool.h:434
void TrimToSize(size_t sizelimit, std::vector< COutPoint > *pvNoSpendsRemaining=nullptr) EXCLUSIVE_LOCKS_REQUIRED(cs)
Remove transactions from the mempool until its dynamic size is <= sizelimit.
Definition: txmempool.cpp:1112
void UpdateTransactionsFromBlock(const std::vector< uint256 > &vHashesToUpdate) EXCLUSIVE_LOCKS_REQUIRED(cs
UpdateTransactionsFromBlock is called when adding transactions from a disconnected block back to the ...
Definition: txmempool.cpp:131
return !it visited * it
Definition: txmempool.h:890
void AddTransactionsUpdated(unsigned int n)
Definition: txmempool.cpp:454
void UpdateChildrenForRemoval(txiter entry) EXCLUSIVE_LOCKS_REQUIRED(cs)
Sever link between specified transaction and direct children.
Definition: txmempool.cpp:338
std::optional< txiter > GetIter(const uint256 &txid) const EXCLUSIVE_LOCKS_REQUIRED(cs)
Returns an iterator to the given hash, if found.
Definition: txmempool.cpp:952
CTransactionRef get(const uint256 &hash) const
Definition: txmempool.cpp:882
size_t DynamicMemoryUsage() const
Definition: txmempool.cpp:1009
std::vector< TxMempoolInfo > infoAll() const
Definition: txmempool.cpp:868
void GetTransactionAncestry(const uint256 &txid, size_t &ancestors, size_t &descendants, size_t *ancestorsize=nullptr, CAmount *ancestorfees=nullptr) const
Calculate the ancestor and descendant count for the given transaction.
Definition: txmempool.cpp:1177
void UpdateParent(txiter entry, txiter parent, bool add) EXCLUSIVE_LOCKS_REQUIRED(cs)
Definition: txmempool.cpp:1069
void removeUnchecked(txiter entry, MemPoolRemovalReason reason) EXCLUSIVE_LOCKS_REQUIRED(cs)
Before calling removeUnchecked for a given transaction, UpdateForRemoveFromMempool must be called on ...
Definition: txmempool.cpp:511
int Expire(std::chrono::seconds time) EXCLUSIVE_LOCKS_REQUIRED(cs)
Expire all transaction (and their dependencies) in the mempool older than time.
Definition: txmempool.cpp:1032
void clear()
Definition: txmempool.cpp:692
txiter get_iter_from_wtxid(const uint256 &wtxid) const EXCLUSIVE_LOCKS_REQUIRED(cs)
Definition: txmempool.h:777
void UpdateAncestorsOf(bool add, txiter hash, setEntries &setAncestors) EXCLUSIVE_LOCKS_REQUIRED(cs)
Update ancestors of hash to add/remove it as a descendant transaction.
Definition: txmempool.cpp:309
CBlockPolicyEstimator *const minerPolicyEstimator
Definition: txmempool.h:436
bool CheckPackageLimits(const Package &package, uint64_t limitAncestorCount, uint64_t limitAncestorSize, uint64_t limitDescendantCount, uint64_t limitDescendantSize, std::string &errString) const EXCLUSIVE_LOCKS_REQUIRED(cs)
Calculate all in-mempool ancestors of a set of transactions not already in the mempool and check ance...
Definition: txmempool.cpp:235
void removeForReorg(CChain &chain, std::function< bool(txiter)> filter_final_and_mature) EXCLUSIVE_LOCKS_REQUIRED(cs
After reorg, filter the entries that would no longer be valid in the next block, and update the entri...
Definition: txmempool.cpp:609
TxMempoolInfo info(const GenTxid &gtxid) const
Definition: txmempool.cpp:891
void ApplyDelta(const uint256 &hash, CAmount &nFeeDelta) const EXCLUSIVE_LOCKS_REQUIRED(cs)
Definition: txmempool.cpp:930
void UpdateForDescendants(txiter updateIt, cacheMap &cachedDescendants, const std::set< uint256 > &setExclude, std::set< uint256 > &descendants_to_remove) EXCLUSIVE_LOCKS_REQUIRED(cs)
UpdateForDescendants is used by UpdateTransactionsFromBlock to update the descendants for a single tr...
Definition: txmempool.cpp:80
bool 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 EXCLUSIVE_LOCKS_REQUIRED(cs)
Try to calculate all in-mempool ancestors of entry.
Definition: txmempool.cpp:270
static const int ROLLING_FEE_HALFLIFE
Definition: txmempool.h:460
std::set< txiter, CompareIteratorByHash > setEntries
Definition: txmempool.h:527
std::vector< indexed_transaction_set::const_iterator > GetSortedDepthAndScore() const EXCLUSIVE_LOCKS_REQUIRED(cs)
Definition: txmempool.cpp:837
void RemoveStaged(setEntries &stage, bool updateDescendants, MemPoolRemovalReason reason) EXCLUSIVE_LOCKS_REQUIRED(cs)
Remove a set of transactions from the mempool.
Definition: txmempool.cpp:1024
void removeForBlock(const std::vector< CTransactionRef > &vtx, unsigned int nBlockHeight) EXCLUSIVE_LOCKS_REQUIRED(cs)
Called when a block is connected.
Definition: txmempool.cpp:649
void queryHashes(std::vector< uint256 > &vtxid) const
Definition: txmempool.cpp:851
indexed_transaction_set::nth_index< 0 >::type::const_iterator txiter
Definition: txmempool.h:524
uint64_t GetAndIncrementSequence() const EXCLUSIVE_LOCKS_REQUIRED(cs)
Guards this internal counter for external reporting.
Definition: txmempool.h:814
void UpdateChild(txiter entry, txiter child, bool add) EXCLUSIVE_LOCKS_REQUIRED(cs)
Definition: txmempool.cpp:1058
bool exists(const GenTxid &gtxid) const
Definition: txmempool.h:767
std::map< txiter, setEntries, CompareIteratorByHash > cacheMap
Definition: txmempool.h:531
bool m_epoch
Definition: txmempool.h:883
CTxMemPool(const Options &opts)
Create a new CTxMemPool.
Definition: txmempool.cpp:426
const CFeeRate m_incremental_relay_feerate
Definition: txmempool.h:571
setEntries GetIterSet(const std::set< uint256 > &hashes) const EXCLUSIVE_LOCKS_REQUIRED(cs)
Translate a set of hashes into a set of pool iterators to avoid repeated lookups.
Definition: txmempool.cpp:959
const CTransaction * GetConflictTx(const COutPoint &prevout) const EXCLUSIVE_LOCKS_REQUIRED(cs)
Get the transaction in the pool that spends the same prevout.
Definition: txmempool.cpp:946
bool CompareDepthAndScore(const uint256 &hasha, const uint256 &hashb, bool wtxid=false)
Definition: txmempool.cpp:806
void CalculateDescendants(txiter it, setEntries &setDescendants) const EXCLUSIVE_LOCKS_REQUIRED(cs)
Populate setDescendants with all in-mempool descendants of hash.
Definition: txmempool.cpp:555
const Limits m_limits
Definition: txmempool.h:581
void check(const CCoinsViewCache &active_coins_tip, int64_t spendheight) const EXCLUSIVE_LOCKS_REQUIRED(void cs_main
Definition: txmempool.h:605
void SetLoadTried(bool load_tried)
Set whether or not we've made an attempt to load the mempool (regardless of whether the attempt was s...
Definition: txmempool.cpp:1195
void UpdateForRemoveFromMempool(const setEntries &entriesToRemove, bool updateDescendants) EXCLUSIVE_LOCKS_REQUIRED(cs)
For each transaction being removed, update ancestors and any direct children.
Definition: txmempool.cpp:346
bool CalculateAncestorsAndCheckLimits(size_t entry_size, size_t entry_count, setEntries &setAncestors, CTxMemPoolEntry::Parents &staged_ancestors, uint64_t limitAncestorCount, uint64_t limitAncestorSize, uint64_t limitDescendantCount, uint64_t limitDescendantSize, std::string &errString) const EXCLUSIVE_LOCKS_REQUIRED(cs)
Helper function to calculate all in-mempool ancestors of staged_ancestors and apply ancestor and desc...
Definition: txmempool.cpp:186
uint64_t CalculateDescendantMaximum(txiter entry) const EXCLUSIVE_LOCKS_REQUIRED(cs)
Definition: txmempool.cpp:1155
bool isSpent(const COutPoint &outpoint) const
Definition: txmempool.cpp:443
unsigned int GetTransactionsUpdated() const
Definition: txmempool.cpp:449
void _clear() EXCLUSIVE_LOCKS_REQUIRED(cs)
Definition: txmempool.cpp:678
A UTXO entry.
Definition: coins.h:31
Sort by feerate of entry (fee/size) in descending order This is only used for transaction relay,...
Definition: txmempool.h:251
A generic txid reference (txid or wtxid).
Definition: transaction.h:419
bool IsWtxid() const
Definition: transaction.h:427
const uint256 & GetHash() const
Definition: transaction.h:428
static GenTxid Txid(const uint256 &hash)
Definition: transaction.h:425
std::string ToString() const
Definition: uint256.cpp:64
std::string GetHex() const
Definition: uint256.cpp:20
256-bit opaque blob.
Definition: uint256.h:119
void AddCoins(CCoinsViewCache &cache, const CTransaction &tx, int nHeight, bool check_for_overwrite)
Utility function to add all of a transaction's outputs to a cache.
Definition: coins.cpp:115
static int64_t GetTransactionWeight(const CTransaction &tx)
Definition: validation.h:148
static size_t RecursiveDynamicUsage(const CScript &script)
Definition: core_memusage.h:12
#define WITH_FRESH_EPOCH(epoch)
Definition: epochguard.h:100
#define LogPrint(category,...)
Definition: logging.h:243
#define LogPrintf(...)
Definition: logging.h:234
bool spendsCoinbase
unsigned int sigOpCost
LockPoints lp
std::string FormatMoney(const CAmount n)
Money parsing/formatting utilities.
Definition: moneystr.cpp:16
@ MEMPOOL
Definition: logging.h:42
bool CheckTxInputs(const CTransaction &tx, TxValidationState &state, const CCoinsViewCache &inputs, int nSpendHeight, CAmount &txfee)
Check whether all inputs of this transaction are valid (no double spends and amounts) This does not m...
Definition: tx_verify.cpp:168
static size_t DynamicUsage(const int8_t &v)
Dynamic memory usage for built-in types is zero.
Definition: memusage.h:28
static size_t IncrementalDynamicUsage(const std::set< X, Y > &s)
Definition: memusage.h:104
static size_t MallocUsage(size_t alloc)
Compute the total memory used by allocating alloc bytes.
Definition: memusage.h:49
T SaturatingAdd(const T i, const T j) noexcept
Definition: overflow.h:33
std::vector< CTransactionRef > Package
A package is an ordered list of transactions.
Definition: packages.h:44
unsigned int nBytesPerSigOp
Definition: settings.cpp:10
int64_t GetVirtualTransactionSize(int64_t nWeight, int64_t nSigOpCost, unsigned int bytes_per_sigop)
Compute the virtual transaction size (weight reinterpreted as bytes).
Definition: policy.cpp:295
std::shared_ptr< const CTransaction > CTransactionRef
Definition: transaction.h:414
T GetRand(T nMax=std::numeric_limits< T >::max()) noexcept
Generate a uniform random integer of type T in the range [0..nMax) nMax defaults to std::numeric_limi...
Definition: random.h:79
reverse_range< T > reverse_iterate(T &x)
CBlockIndex * maxInputBlock
Definition: txmempool.h:53
Information about a mempool transaction.
Definition: txmempool.h:329
int64_t ancestor_count
The maximum allowed number of transactions in a package including the entry and its ancestors.
int64_t ancestor_size_vbytes
The maximum allowed size in virtual bytes of an entry and its ancestors within a package.
Options struct containing options for constructing a CTxMemPool.
#define LOCK(cs)
Definition: sync.h:261
int64_t GetTime()
Definition: time.cpp:117
#define strprintf
Format arguments and return the string or write to given std::ostream (see tinyformat::format doc for...
Definition: tinyformat.h:1164
bool TestLockPointValidity(CChain &active_chain, const LockPoints &lp)
Test whether the LockPoints height and time are still valid on the current chain.
Definition: txmempool.cpp:27
static TxMempoolInfo GetInfo(CTxMemPool::indexed_transaction_set::const_iterator it)
Definition: txmempool.cpp:864
MemPoolRemovalReason
Reason why a transaction was removed from the mempool, this is passed to the notification signal.
Definition: txmempool.h:349
@ SIZELIMIT
Removed in size limiting.
@ BLOCK
Removed for block.
@ EXPIRY
Expired from mempool.
@ CONFLICT
Removed for conflict with in-block transaction.
@ REORG
Removed for reorganization.
static const uint32_t MEMPOOL_HEIGHT
Fake height value used in Coin to signify they are only in the memory pool (since 0....
Definition: txmempool.h:42
AssertLockHeld(pool.cs)
assert(!tx.IsCoinBase())
CMainSignals & GetMainSignals()