Bitcoin Core  27.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-2022 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 <common/system.h>
11 #include <consensus/consensus.h>
12 #include <consensus/tx_verify.h>
13 #include <consensus/validation.h>
14 #include <logging.h>
15 #include <policy/policy.h>
16 #include <policy/settings.h>
17 #include <random.h>
18 #include <reverse_iterator.h>
19 #include <util/check.h>
20 #include <util/feefrac.h>
21 #include <util/moneystr.h>
22 #include <util/overflow.h>
23 #include <util/result.h>
24 #include <util/time.h>
25 #include <util/trace.h>
26 #include <util/translation.h>
27 #include <validationinterface.h>
28 
29 #include <cmath>
30 #include <numeric>
31 #include <optional>
32 #include <string_view>
33 #include <utility>
34 
35 bool TestLockPointValidity(CChain& active_chain, const LockPoints& lp)
36 {
38  // If there are relative lock times then the maxInputBlock will be set
39  // If there are no relative lock times, the LockPoints don't depend on the chain
40  if (lp.maxInputBlock) {
41  // Check whether active_chain is an extension of the block at which the LockPoints
42  // calculation was valid. If not LockPoints are no longer valid
43  if (!active_chain.Contains(lp.maxInputBlock)) {
44  return false;
45  }
46  }
47 
48  // LockPoints still valid
49  return true;
50 }
51 
52 void CTxMemPool::UpdateForDescendants(txiter updateIt, cacheMap& cachedDescendants,
53  const std::set<uint256>& setExclude, std::set<uint256>& descendants_to_remove)
54 {
55  CTxMemPoolEntry::Children stageEntries, descendants;
56  stageEntries = updateIt->GetMemPoolChildrenConst();
57 
58  while (!stageEntries.empty()) {
59  const CTxMemPoolEntry& descendant = *stageEntries.begin();
60  descendants.insert(descendant);
61  stageEntries.erase(descendant);
62  const CTxMemPoolEntry::Children& children = descendant.GetMemPoolChildrenConst();
63  for (const CTxMemPoolEntry& childEntry : children) {
64  cacheMap::iterator cacheIt = cachedDescendants.find(mapTx.iterator_to(childEntry));
65  if (cacheIt != cachedDescendants.end()) {
66  // We've already calculated this one, just add the entries for this set
67  // but don't traverse again.
68  for (txiter cacheEntry : cacheIt->second) {
69  descendants.insert(*cacheEntry);
70  }
71  } else if (!descendants.count(childEntry)) {
72  // Schedule for later processing
73  stageEntries.insert(childEntry);
74  }
75  }
76  }
77  // descendants now contains all in-mempool descendants of updateIt.
78  // Update and add to cached descendant map
79  int32_t modifySize = 0;
80  CAmount modifyFee = 0;
81  int64_t modifyCount = 0;
82  for (const CTxMemPoolEntry& descendant : descendants) {
83  if (!setExclude.count(descendant.GetTx().GetHash())) {
84  modifySize += descendant.GetTxSize();
85  modifyFee += descendant.GetModifiedFee();
86  modifyCount++;
87  cachedDescendants[updateIt].insert(mapTx.iterator_to(descendant));
88  // Update ancestor state for each descendant
89  mapTx.modify(mapTx.iterator_to(descendant), [=](CTxMemPoolEntry& e) {
90  e.UpdateAncestorState(updateIt->GetTxSize(), updateIt->GetModifiedFee(), 1, updateIt->GetSigOpCost());
91  });
92  // Don't directly remove the transaction here -- doing so would
93  // invalidate iterators in cachedDescendants. Mark it for removal
94  // by inserting into descendants_to_remove.
95  if (descendant.GetCountWithAncestors() > uint64_t(m_limits.ancestor_count) || descendant.GetSizeWithAncestors() > m_limits.ancestor_size_vbytes) {
96  descendants_to_remove.insert(descendant.GetTx().GetHash());
97  }
98  }
99  }
100  mapTx.modify(updateIt, [=](CTxMemPoolEntry& e) { e.UpdateDescendantState(modifySize, modifyFee, modifyCount); });
101 }
102 
103 void CTxMemPool::UpdateTransactionsFromBlock(const std::vector<uint256>& vHashesToUpdate)
104 {
106  // For each entry in vHashesToUpdate, store the set of in-mempool, but not
107  // in-vHashesToUpdate transactions, so that we don't have to recalculate
108  // descendants when we come across a previously seen entry.
109  cacheMap mapMemPoolDescendantsToUpdate;
110 
111  // Use a set for lookups into vHashesToUpdate (these entries are already
112  // accounted for in the state of their ancestors)
113  std::set<uint256> setAlreadyIncluded(vHashesToUpdate.begin(), vHashesToUpdate.end());
114 
115  std::set<uint256> descendants_to_remove;
116 
117  // Iterate in reverse, so that whenever we are looking at a transaction
118  // we are sure that all in-mempool descendants have already been processed.
119  // This maximizes the benefit of the descendant cache and guarantees that
120  // CTxMemPoolEntry::m_children will be updated, an assumption made in
121  // UpdateForDescendants.
122  for (const uint256 &hash : reverse_iterate(vHashesToUpdate)) {
123  // calculate children from mapNextTx
124  txiter it = mapTx.find(hash);
125  if (it == mapTx.end()) {
126  continue;
127  }
128  auto iter = mapNextTx.lower_bound(COutPoint(Txid::FromUint256(hash), 0));
129  // First calculate the children, and update CTxMemPoolEntry::m_children to
130  // include them, and update their CTxMemPoolEntry::m_parents to include this tx.
131  // we cache the in-mempool children to avoid duplicate updates
132  {
134  for (; iter != mapNextTx.end() && iter->first->hash == hash; ++iter) {
135  const uint256 &childHash = iter->second->GetHash();
136  txiter childIter = mapTx.find(childHash);
137  assert(childIter != mapTx.end());
138  // We can skip updating entries we've encountered before or that
139  // are in the block (which are already accounted for).
140  if (!visited(childIter) && !setAlreadyIncluded.count(childHash)) {
141  UpdateChild(it, childIter, true);
142  UpdateParent(childIter, it, true);
143  }
144  }
145  } // release epoch guard for UpdateForDescendants
146  UpdateForDescendants(it, mapMemPoolDescendantsToUpdate, setAlreadyIncluded, descendants_to_remove);
147  }
148 
149  for (const auto& txid : descendants_to_remove) {
150  // This txid may have been removed already in a prior call to removeRecursive.
151  // Therefore we ensure it is not yet removed already.
152  if (const std::optional<txiter> txiter = GetIter(txid)) {
154  }
155  }
156 }
157 
159  int64_t entry_size,
160  size_t entry_count,
161  CTxMemPoolEntry::Parents& staged_ancestors,
162  const Limits& limits) const
163 {
164  int64_t totalSizeWithAncestors = entry_size;
165  setEntries ancestors;
166 
167  while (!staged_ancestors.empty()) {
168  const CTxMemPoolEntry& stage = staged_ancestors.begin()->get();
169  txiter stageit = mapTx.iterator_to(stage);
170 
171  ancestors.insert(stageit);
172  staged_ancestors.erase(stage);
173  totalSizeWithAncestors += stageit->GetTxSize();
174 
175  if (stageit->GetSizeWithDescendants() + entry_size > limits.descendant_size_vbytes) {
176  return util::Error{Untranslated(strprintf("exceeds descendant size limit for tx %s [limit: %u]", stageit->GetTx().GetHash().ToString(), limits.descendant_size_vbytes))};
177  } else if (stageit->GetCountWithDescendants() + entry_count > static_cast<uint64_t>(limits.descendant_count)) {
178  return util::Error{Untranslated(strprintf("too many descendants for tx %s [limit: %u]", stageit->GetTx().GetHash().ToString(), limits.descendant_count))};
179  } else if (totalSizeWithAncestors > limits.ancestor_size_vbytes) {
180  return util::Error{Untranslated(strprintf("exceeds ancestor size limit [limit: %u]", limits.ancestor_size_vbytes))};
181  }
182 
183  const CTxMemPoolEntry::Parents& parents = stageit->GetMemPoolParentsConst();
184  for (const CTxMemPoolEntry& parent : parents) {
185  txiter parent_it = mapTx.iterator_to(parent);
186 
187  // If this is a new ancestor, add it.
188  if (ancestors.count(parent_it) == 0) {
189  staged_ancestors.insert(parent);
190  }
191  if (staged_ancestors.size() + ancestors.size() + entry_count > static_cast<uint64_t>(limits.ancestor_count)) {
192  return util::Error{Untranslated(strprintf("too many unconfirmed ancestors [limit: %u]", limits.ancestor_count))};
193  }
194  }
195  }
196 
197  return ancestors;
198 }
199 
201  const int64_t total_vsize) const
202 {
203  size_t pack_count = package.size();
204 
205  // Package itself is busting mempool limits; should be rejected even if no staged_ancestors exist
206  if (pack_count > static_cast<uint64_t>(m_limits.ancestor_count)) {
207  return util::Error{Untranslated(strprintf("package count %u exceeds ancestor count limit [limit: %u]", pack_count, m_limits.ancestor_count))};
208  } else if (pack_count > static_cast<uint64_t>(m_limits.descendant_count)) {
209  return util::Error{Untranslated(strprintf("package count %u exceeds descendant count limit [limit: %u]", pack_count, m_limits.descendant_count))};
210  } else if (total_vsize > m_limits.ancestor_size_vbytes) {
211  return util::Error{Untranslated(strprintf("package size %u exceeds ancestor size limit [limit: %u]", total_vsize, m_limits.ancestor_size_vbytes))};
212  } else if (total_vsize > m_limits.descendant_size_vbytes) {
213  return util::Error{Untranslated(strprintf("package size %u exceeds descendant size limit [limit: %u]", total_vsize, m_limits.descendant_size_vbytes))};
214  }
215 
216  CTxMemPoolEntry::Parents staged_ancestors;
217  for (const auto& tx : package) {
218  for (const auto& input : tx->vin) {
219  std::optional<txiter> piter = GetIter(input.prevout.hash);
220  if (piter) {
221  staged_ancestors.insert(**piter);
222  if (staged_ancestors.size() + package.size() > static_cast<uint64_t>(m_limits.ancestor_count)) {
223  return util::Error{Untranslated(strprintf("too many unconfirmed parents [limit: %u]", m_limits.ancestor_count))};
224  }
225  }
226  }
227  }
228  // When multiple transactions are passed in, the ancestors and descendants of all transactions
229  // considered together must be within limits even if they are not interdependent. This may be
230  // stricter than the limits for each individual transaction.
231  const auto ancestors{CalculateAncestorsAndCheckLimits(total_vsize, package.size(),
232  staged_ancestors, m_limits)};
233  // It's possible to overestimate the ancestor/descendant totals.
234  if (!ancestors.has_value()) return util::Error{Untranslated("possibly " + util::ErrorString(ancestors).original)};
235  return {};
236 }
237 
239  const CTxMemPoolEntry &entry,
240  const Limits& limits,
241  bool fSearchForParents /* = true */) const
242 {
243  CTxMemPoolEntry::Parents staged_ancestors;
244  const CTransaction &tx = entry.GetTx();
245 
246  if (fSearchForParents) {
247  // Get parents of this transaction that are in the mempool
248  // GetMemPoolParents() is only valid for entries in the mempool, so we
249  // iterate mapTx to find parents.
250  for (unsigned int i = 0; i < tx.vin.size(); i++) {
251  std::optional<txiter> piter = GetIter(tx.vin[i].prevout.hash);
252  if (piter) {
253  staged_ancestors.insert(**piter);
254  if (staged_ancestors.size() + 1 > static_cast<uint64_t>(limits.ancestor_count)) {
255  return util::Error{Untranslated(strprintf("too many unconfirmed parents [limit: %u]", limits.ancestor_count))};
256  }
257  }
258  }
259  } else {
260  // If we're not searching for parents, we require this to already be an
261  // entry in the mempool and use the entry's cached parents.
262  txiter it = mapTx.iterator_to(entry);
263  staged_ancestors = it->GetMemPoolParentsConst();
264  }
265 
266  return CalculateAncestorsAndCheckLimits(entry.GetTxSize(), /*entry_count=*/1, staged_ancestors,
267  limits);
268 }
269 
271  std::string_view calling_fn_name,
272  const CTxMemPoolEntry &entry,
273  const Limits& limits,
274  bool fSearchForParents /* = true */) const
275 {
276  auto result{CalculateMemPoolAncestors(entry, limits, fSearchForParents)};
277  if (!Assume(result)) {
278  LogPrintLevel(BCLog::MEMPOOL, BCLog::Level::Error, "%s: CalculateMemPoolAncestors failed unexpectedly, continuing with empty ancestor set (%s)\n",
279  calling_fn_name, util::ErrorString(result).original);
280  }
281  return std::move(result).value_or(CTxMemPool::setEntries{});
282 }
283 
284 void CTxMemPool::UpdateAncestorsOf(bool add, txiter it, setEntries &setAncestors)
285 {
286  const CTxMemPoolEntry::Parents& parents = it->GetMemPoolParentsConst();
287  // add or remove this tx as a child of each parent
288  for (const CTxMemPoolEntry& parent : parents) {
289  UpdateChild(mapTx.iterator_to(parent), it, add);
290  }
291  const int32_t updateCount = (add ? 1 : -1);
292  const int32_t updateSize{updateCount * it->GetTxSize()};
293  const CAmount updateFee = updateCount * it->GetModifiedFee();
294  for (txiter ancestorIt : setAncestors) {
295  mapTx.modify(ancestorIt, [=](CTxMemPoolEntry& e) { e.UpdateDescendantState(updateSize, updateFee, updateCount); });
296  }
297 }
298 
300 {
301  int64_t updateCount = setAncestors.size();
302  int64_t updateSize = 0;
303  CAmount updateFee = 0;
304  int64_t updateSigOpsCost = 0;
305  for (txiter ancestorIt : setAncestors) {
306  updateSize += ancestorIt->GetTxSize();
307  updateFee += ancestorIt->GetModifiedFee();
308  updateSigOpsCost += ancestorIt->GetSigOpCost();
309  }
310  mapTx.modify(it, [=](CTxMemPoolEntry& e){ e.UpdateAncestorState(updateSize, updateFee, updateCount, updateSigOpsCost); });
311 }
312 
314 {
315  const CTxMemPoolEntry::Children& children = it->GetMemPoolChildrenConst();
316  for (const CTxMemPoolEntry& updateIt : children) {
317  UpdateParent(mapTx.iterator_to(updateIt), it, false);
318  }
319 }
320 
321 void CTxMemPool::UpdateForRemoveFromMempool(const setEntries &entriesToRemove, bool updateDescendants)
322 {
323  // For each entry, walk back all ancestors and decrement size associated with this
324  // transaction
325  if (updateDescendants) {
326  // updateDescendants should be true whenever we're not recursively
327  // removing a tx and all its descendants, eg when a transaction is
328  // confirmed in a block.
329  // Here we only update statistics and not data in CTxMemPool::Parents
330  // and CTxMemPoolEntry::Children (which we need to preserve until we're
331  // finished with all operations that need to traverse the mempool).
332  for (txiter removeIt : entriesToRemove) {
333  setEntries setDescendants;
334  CalculateDescendants(removeIt, setDescendants);
335  setDescendants.erase(removeIt); // don't update state for self
336  int32_t modifySize = -removeIt->GetTxSize();
337  CAmount modifyFee = -removeIt->GetModifiedFee();
338  int modifySigOps = -removeIt->GetSigOpCost();
339  for (txiter dit : setDescendants) {
340  mapTx.modify(dit, [=](CTxMemPoolEntry& e){ e.UpdateAncestorState(modifySize, modifyFee, -1, modifySigOps); });
341  }
342  }
343  }
344  for (txiter removeIt : entriesToRemove) {
345  const CTxMemPoolEntry &entry = *removeIt;
346  // Since this is a tx that is already in the mempool, we can call CMPA
347  // with fSearchForParents = false. If the mempool is in a consistent
348  // state, then using true or false should both be correct, though false
349  // should be a bit faster.
350  // However, if we happen to be in the middle of processing a reorg, then
351  // the mempool can be in an inconsistent state. In this case, the set
352  // of ancestors reachable via GetMemPoolParents()/GetMemPoolChildren()
353  // will be the same as the set of ancestors whose packages include this
354  // transaction, because when we add a new transaction to the mempool in
355  // addUnchecked(), we assume it has no children, and in the case of a
356  // reorg where that assumption is false, the in-mempool children aren't
357  // linked to the in-block tx's until UpdateTransactionsFromBlock() is
358  // called.
359  // So if we're being called during a reorg, ie before
360  // UpdateTransactionsFromBlock() has been called, then
361  // GetMemPoolParents()/GetMemPoolChildren() will differ from the set of
362  // mempool parents we'd calculate by searching, and it's important that
363  // we use the cached notion of ancestor transactions as the set of
364  // things to update for removal.
365  auto ancestors{AssumeCalculateMemPoolAncestors(__func__, entry, Limits::NoLimits(), /*fSearchForParents=*/false)};
366  // Note that UpdateAncestorsOf severs the child links that point to
367  // removeIt in the entries for the parents of removeIt.
368  UpdateAncestorsOf(false, removeIt, ancestors);
369  }
370  // After updating all the ancestor sizes, we can now sever the link between each
371  // transaction being removed and any mempool children (ie, update CTxMemPoolEntry::m_parents
372  // for each direct child of a transaction being removed).
373  for (txiter removeIt : entriesToRemove) {
374  UpdateChildrenForRemoval(removeIt);
375  }
376 }
377 
378 void CTxMemPoolEntry::UpdateDescendantState(int32_t modifySize, CAmount modifyFee, int64_t modifyCount)
379 {
380  nSizeWithDescendants += modifySize;
383  m_count_with_descendants += modifyCount;
385 }
386 
387 void CTxMemPoolEntry::UpdateAncestorState(int32_t modifySize, CAmount modifyFee, int64_t modifyCount, int64_t modifySigOps)
388 {
389  nSizeWithAncestors += modifySize;
392  m_count_with_ancestors += modifyCount;
394  nSigOpCostWithAncestors += modifySigOps;
395  assert(int(nSigOpCostWithAncestors) >= 0);
396 }
397 
399  : m_check_ratio{opts.check_ratio},
400  m_max_size_bytes{opts.max_size_bytes},
401  m_expiry{opts.expiry},
402  m_incremental_relay_feerate{opts.incremental_relay_feerate},
403  m_min_relay_feerate{opts.min_relay_feerate},
404  m_dust_relay_feerate{opts.dust_relay_feerate},
405  m_permit_bare_multisig{opts.permit_bare_multisig},
406  m_max_datacarrier_bytes{opts.max_datacarrier_bytes},
407  m_require_standard{opts.require_standard},
408  m_full_rbf{opts.full_rbf},
409  m_persist_v1_dat{opts.persist_v1_dat},
410  m_limits{opts.limits},
411  m_signals{opts.signals}
412 {
413 }
414 
415 bool CTxMemPool::isSpent(const COutPoint& outpoint) const
416 {
417  LOCK(cs);
418  return mapNextTx.count(outpoint);
419 }
420 
422 {
423  return nTransactionsUpdated;
424 }
425 
427 {
429 }
430 
431 void CTxMemPool::addUnchecked(const CTxMemPoolEntry &entry, setEntries &setAncestors)
432 {
433  // Add to memory pool without checking anything.
434  // Used by AcceptToMemoryPool(), which DOES do
435  // all the appropriate checks.
436  indexed_transaction_set::iterator newit = mapTx.emplace(CTxMemPoolEntry::ExplicitCopy, entry).first;
437 
438  // Update transaction for any feeDelta created by PrioritiseTransaction
439  CAmount delta{0};
440  ApplyDelta(entry.GetTx().GetHash(), delta);
441  // The following call to UpdateModifiedFee assumes no previous fee modifications
442  Assume(entry.GetFee() == entry.GetModifiedFee());
443  if (delta) {
444  mapTx.modify(newit, [&delta](CTxMemPoolEntry& e) { e.UpdateModifiedFee(delta); });
445  }
446 
447  // Update cachedInnerUsage to include contained transaction's usage.
448  // (When we update the entry for in-mempool parents, memory usage will be
449  // further updated.)
450  cachedInnerUsage += entry.DynamicMemoryUsage();
451 
452  const CTransaction& tx = newit->GetTx();
453  std::set<Txid> setParentTransactions;
454  for (unsigned int i = 0; i < tx.vin.size(); i++) {
455  mapNextTx.insert(std::make_pair(&tx.vin[i].prevout, &tx));
456  setParentTransactions.insert(tx.vin[i].prevout.hash);
457  }
458  // Don't bother worrying about child transactions of this one.
459  // Normal case of a new transaction arriving is that there can't be any
460  // children, because such children would be orphans.
461  // An exception to that is if a transaction enters that used to be in a block.
462  // In that case, our disconnect block logic will call UpdateTransactionsFromBlock
463  // to clean up the mess we're leaving here.
464 
465  // Update ancestors with information about this tx
466  for (const auto& pit : GetIterSet(setParentTransactions)) {
467  UpdateParent(newit, pit, true);
468  }
469  UpdateAncestorsOf(true, newit, setAncestors);
470  UpdateEntryForAncestors(newit, setAncestors);
471 
473  totalTxSize += entry.GetTxSize();
474  m_total_fee += entry.GetFee();
475 
476  txns_randomized.emplace_back(newit->GetSharedTx());
477  newit->idx_randomized = txns_randomized.size() - 1;
478 
479  TRACE3(mempool, added,
480  entry.GetTx().GetHash().data(),
481  entry.GetTxSize(),
482  entry.GetFee()
483  );
484 }
485 
487 {
488  // We increment mempool sequence value no matter removal reason
489  // even if not directly reported below.
490  uint64_t mempool_sequence = GetAndIncrementSequence();
491 
492  if (reason != MemPoolRemovalReason::BLOCK && m_signals) {
493  // Notify clients that a transaction has been removed from the mempool
494  // for any reason except being included in a block. Clients interested
495  // in transactions included in blocks can subscribe to the BlockConnected
496  // notification.
497  m_signals->TransactionRemovedFromMempool(it->GetSharedTx(), reason, mempool_sequence);
498  }
499  TRACE5(mempool, removed,
500  it->GetTx().GetHash().data(),
501  RemovalReasonToString(reason).c_str(),
502  it->GetTxSize(),
503  it->GetFee(),
504  std::chrono::duration_cast<std::chrono::duration<std::uint64_t>>(it->GetTime()).count()
505  );
506 
507  for (const CTxIn& txin : it->GetTx().vin)
508  mapNextTx.erase(txin.prevout);
509 
510  RemoveUnbroadcastTx(it->GetTx().GetHash(), true /* add logging because unchecked */);
511 
512  if (txns_randomized.size() > 1) {
513  // Update idx_randomized of the to-be-moved entry.
514  Assert(GetEntry(txns_randomized.back()->GetHash()))->idx_randomized = it->idx_randomized;
515  // Remove entry from txns_randomized by replacing it with the back and deleting the back.
516  txns_randomized[it->idx_randomized] = std::move(txns_randomized.back());
517  txns_randomized.pop_back();
518  if (txns_randomized.size() * 2 < txns_randomized.capacity())
519  txns_randomized.shrink_to_fit();
520  } else
521  txns_randomized.clear();
522 
523  totalTxSize -= it->GetTxSize();
524  m_total_fee -= it->GetFee();
525  cachedInnerUsage -= it->DynamicMemoryUsage();
526  cachedInnerUsage -= memusage::DynamicUsage(it->GetMemPoolParentsConst()) + memusage::DynamicUsage(it->GetMemPoolChildrenConst());
527  mapTx.erase(it);
529 }
530 
531 // Calculates descendants of entry that are not already in setDescendants, and adds to
532 // setDescendants. Assumes entryit is already a tx in the mempool and CTxMemPoolEntry::m_children
533 // is correct for tx and all descendants.
534 // Also assumes that if an entry is in setDescendants already, then all
535 // in-mempool descendants of it are already in setDescendants as well, so that we
536 // can save time by not iterating over those entries.
537 void CTxMemPool::CalculateDescendants(txiter entryit, setEntries& setDescendants) const
538 {
539  setEntries stage;
540  if (setDescendants.count(entryit) == 0) {
541  stage.insert(entryit);
542  }
543  // Traverse down the children of entry, only adding children that are not
544  // accounted for in setDescendants already (because those children have either
545  // already been walked, or will be walked in this iteration).
546  while (!stage.empty()) {
547  txiter it = *stage.begin();
548  setDescendants.insert(it);
549  stage.erase(it);
550 
551  const CTxMemPoolEntry::Children& children = it->GetMemPoolChildrenConst();
552  for (const CTxMemPoolEntry& child : children) {
553  txiter childiter = mapTx.iterator_to(child);
554  if (!setDescendants.count(childiter)) {
555  stage.insert(childiter);
556  }
557  }
558  }
559 }
560 
562 {
563  // Remove transaction from memory pool
565  setEntries txToRemove;
566  txiter origit = mapTx.find(origTx.GetHash());
567  if (origit != mapTx.end()) {
568  txToRemove.insert(origit);
569  } else {
570  // When recursively removing but origTx isn't in the mempool
571  // be sure to remove any children that are in the pool. This can
572  // happen during chain re-orgs if origTx isn't re-accepted into
573  // the mempool for any reason.
574  for (unsigned int i = 0; i < origTx.vout.size(); i++) {
575  auto it = mapNextTx.find(COutPoint(origTx.GetHash(), i));
576  if (it == mapNextTx.end())
577  continue;
578  txiter nextit = mapTx.find(it->second->GetHash());
579  assert(nextit != mapTx.end());
580  txToRemove.insert(nextit);
581  }
582  }
583  setEntries setAllRemoves;
584  for (txiter it : txToRemove) {
585  CalculateDescendants(it, setAllRemoves);
586  }
587 
588  RemoveStaged(setAllRemoves, false, reason);
589 }
590 
591 void CTxMemPool::removeForReorg(CChain& chain, std::function<bool(txiter)> check_final_and_mature)
592 {
593  // Remove transactions spending a coinbase which are now immature and no-longer-final transactions
596 
597  setEntries txToRemove;
598  for (indexed_transaction_set::const_iterator it = mapTx.begin(); it != mapTx.end(); it++) {
599  if (check_final_and_mature(it)) txToRemove.insert(it);
600  }
601  setEntries setAllRemoves;
602  for (txiter it : txToRemove) {
603  CalculateDescendants(it, setAllRemoves);
604  }
605  RemoveStaged(setAllRemoves, false, MemPoolRemovalReason::REORG);
606  for (indexed_transaction_set::const_iterator it = mapTx.begin(); it != mapTx.end(); it++) {
607  assert(TestLockPointValidity(chain, it->GetLockPoints()));
608  }
609 }
610 
612 {
613  // Remove transactions which depend on inputs of tx, recursively
615  for (const CTxIn &txin : tx.vin) {
616  auto it = mapNextTx.find(txin.prevout);
617  if (it != mapNextTx.end()) {
618  const CTransaction &txConflict = *it->second;
619  if (txConflict != tx)
620  {
621  ClearPrioritisation(txConflict.GetHash());
623  }
624  }
625  }
626 }
627 
631 void CTxMemPool::removeForBlock(const std::vector<CTransactionRef>& vtx, unsigned int nBlockHeight)
632 {
634  std::vector<RemovedMempoolTransactionInfo> txs_removed_for_block;
635  txs_removed_for_block.reserve(vtx.size());
636  for (const auto& tx : vtx)
637  {
638  txiter it = mapTx.find(tx->GetHash());
639  if (it != mapTx.end()) {
640  setEntries stage;
641  stage.insert(it);
642  txs_removed_for_block.emplace_back(*it);
644  }
645  removeConflicts(*tx);
647  }
648  if (m_signals) {
649  m_signals->MempoolTransactionsRemovedForBlock(txs_removed_for_block, nBlockHeight);
650  }
651  lastRollingFeeUpdate = GetTime();
652  blockSinceLastRollingFeeBump = true;
653 }
654 
655 void CTxMemPool::check(const CCoinsViewCache& active_coins_tip, int64_t spendheight) const
656 {
657  if (m_check_ratio == 0) return;
658 
659  if (GetRand(m_check_ratio) >= 1) return;
660 
662  LOCK(cs);
663  LogPrint(BCLog::MEMPOOL, "Checking mempool with %u transactions and %u inputs\n", (unsigned int)mapTx.size(), (unsigned int)mapNextTx.size());
664 
665  uint64_t checkTotal = 0;
666  CAmount check_total_fee{0};
667  uint64_t innerUsage = 0;
668  uint64_t prev_ancestor_count{0};
669 
670  CCoinsViewCache mempoolDuplicate(const_cast<CCoinsViewCache*>(&active_coins_tip));
671 
672  for (const auto& it : GetSortedDepthAndScore()) {
673  checkTotal += it->GetTxSize();
674  check_total_fee += it->GetFee();
675  innerUsage += it->DynamicMemoryUsage();
676  const CTransaction& tx = it->GetTx();
677  innerUsage += memusage::DynamicUsage(it->GetMemPoolParentsConst()) + memusage::DynamicUsage(it->GetMemPoolChildrenConst());
678  CTxMemPoolEntry::Parents setParentCheck;
679  for (const CTxIn &txin : tx.vin) {
680  // Check that every mempool transaction's inputs refer to available coins, or other mempool tx's.
681  indexed_transaction_set::const_iterator it2 = mapTx.find(txin.prevout.hash);
682  if (it2 != mapTx.end()) {
683  const CTransaction& tx2 = it2->GetTx();
684  assert(tx2.vout.size() > txin.prevout.n && !tx2.vout[txin.prevout.n].IsNull());
685  setParentCheck.insert(*it2);
686  }
687  // We are iterating through the mempool entries sorted in order by ancestor count.
688  // All parents must have been checked before their children and their coins added to
689  // the mempoolDuplicate coins cache.
690  assert(mempoolDuplicate.HaveCoin(txin.prevout));
691  // Check whether its inputs are marked in mapNextTx.
692  auto it3 = mapNextTx.find(txin.prevout);
693  assert(it3 != mapNextTx.end());
694  assert(it3->first == &txin.prevout);
695  assert(it3->second == &tx);
696  }
697  auto comp = [](const CTxMemPoolEntry& a, const CTxMemPoolEntry& b) -> bool {
698  return a.GetTx().GetHash() == b.GetTx().GetHash();
699  };
700  assert(setParentCheck.size() == it->GetMemPoolParentsConst().size());
701  assert(std::equal(setParentCheck.begin(), setParentCheck.end(), it->GetMemPoolParentsConst().begin(), comp));
702  // Verify ancestor state is correct.
703  auto ancestors{AssumeCalculateMemPoolAncestors(__func__, *it, Limits::NoLimits())};
704  uint64_t nCountCheck = ancestors.size() + 1;
705  int32_t nSizeCheck = it->GetTxSize();
706  CAmount nFeesCheck = it->GetModifiedFee();
707  int64_t nSigOpCheck = it->GetSigOpCost();
708 
709  for (txiter ancestorIt : ancestors) {
710  nSizeCheck += ancestorIt->GetTxSize();
711  nFeesCheck += ancestorIt->GetModifiedFee();
712  nSigOpCheck += ancestorIt->GetSigOpCost();
713  }
714 
715  assert(it->GetCountWithAncestors() == nCountCheck);
716  assert(it->GetSizeWithAncestors() == nSizeCheck);
717  assert(it->GetSigOpCostWithAncestors() == nSigOpCheck);
718  assert(it->GetModFeesWithAncestors() == nFeesCheck);
719  // Sanity check: we are walking in ascending ancestor count order.
720  assert(prev_ancestor_count <= it->GetCountWithAncestors());
721  prev_ancestor_count = it->GetCountWithAncestors();
722 
723  // Check children against mapNextTx
724  CTxMemPoolEntry::Children setChildrenCheck;
725  auto iter = mapNextTx.lower_bound(COutPoint(it->GetTx().GetHash(), 0));
726  int32_t child_sizes{0};
727  for (; iter != mapNextTx.end() && iter->first->hash == it->GetTx().GetHash(); ++iter) {
728  txiter childit = mapTx.find(iter->second->GetHash());
729  assert(childit != mapTx.end()); // mapNextTx points to in-mempool transactions
730  if (setChildrenCheck.insert(*childit).second) {
731  child_sizes += childit->GetTxSize();
732  }
733  }
734  assert(setChildrenCheck.size() == it->GetMemPoolChildrenConst().size());
735  assert(std::equal(setChildrenCheck.begin(), setChildrenCheck.end(), it->GetMemPoolChildrenConst().begin(), comp));
736  // Also check to make sure size is greater than sum with immediate children.
737  // just a sanity check, not definitive that this calc is correct...
738  assert(it->GetSizeWithDescendants() >= child_sizes + it->GetTxSize());
739 
740  TxValidationState dummy_state; // Not used. CheckTxInputs() should always pass
741  CAmount txfee = 0;
742  assert(!tx.IsCoinBase());
743  assert(Consensus::CheckTxInputs(tx, dummy_state, mempoolDuplicate, spendheight, txfee));
744  for (const auto& input: tx.vin) mempoolDuplicate.SpendCoin(input.prevout);
745  AddCoins(mempoolDuplicate, tx, std::numeric_limits<int>::max());
746  }
747  for (auto it = mapNextTx.cbegin(); it != mapNextTx.cend(); it++) {
748  uint256 hash = it->second->GetHash();
749  indexed_transaction_set::const_iterator it2 = mapTx.find(hash);
750  const CTransaction& tx = it2->GetTx();
751  assert(it2 != mapTx.end());
752  assert(&tx == it->second);
753  }
754 
755  assert(totalTxSize == checkTotal);
756  assert(m_total_fee == check_total_fee);
757  assert(innerUsage == cachedInnerUsage);
758 }
759 
760 bool CTxMemPool::CompareDepthAndScore(const uint256& hasha, const uint256& hashb, bool wtxid)
761 {
762  /* Return `true` if hasha should be considered sooner than hashb. Namely when:
763  * a is not in the mempool, but b is
764  * both are in the mempool and a has fewer ancestors than b
765  * both are in the mempool and a has a higher score than b
766  */
767  LOCK(cs);
768  indexed_transaction_set::const_iterator j = wtxid ? get_iter_from_wtxid(hashb) : mapTx.find(hashb);
769  if (j == mapTx.end()) return false;
770  indexed_transaction_set::const_iterator i = wtxid ? get_iter_from_wtxid(hasha) : mapTx.find(hasha);
771  if (i == mapTx.end()) return true;
772  uint64_t counta = i->GetCountWithAncestors();
773  uint64_t countb = j->GetCountWithAncestors();
774  if (counta == countb) {
775  return CompareTxMemPoolEntryByScore()(*i, *j);
776  }
777  return counta < countb;
778 }
779 
780 namespace {
781 class DepthAndScoreComparator
782 {
783 public:
784  bool operator()(const CTxMemPool::indexed_transaction_set::const_iterator& a, const CTxMemPool::indexed_transaction_set::const_iterator& b)
785  {
786  uint64_t counta = a->GetCountWithAncestors();
787  uint64_t countb = b->GetCountWithAncestors();
788  if (counta == countb) {
789  return CompareTxMemPoolEntryByScore()(*a, *b);
790  }
791  return counta < countb;
792  }
793 };
794 } // namespace
795 
796 std::vector<CTxMemPool::indexed_transaction_set::const_iterator> CTxMemPool::GetSortedDepthAndScore() const
797 {
798  std::vector<indexed_transaction_set::const_iterator> iters;
800 
801  iters.reserve(mapTx.size());
802 
803  for (indexed_transaction_set::iterator mi = mapTx.begin(); mi != mapTx.end(); ++mi) {
804  iters.push_back(mi);
805  }
806  std::sort(iters.begin(), iters.end(), DepthAndScoreComparator());
807  return iters;
808 }
809 
810 static TxMempoolInfo GetInfo(CTxMemPool::indexed_transaction_set::const_iterator it) {
811  return TxMempoolInfo{it->GetSharedTx(), it->GetTime(), it->GetFee(), it->GetTxSize(), it->GetModifiedFee() - it->GetFee()};
812 }
813 
814 std::vector<CTxMemPoolEntryRef> CTxMemPool::entryAll() const
815 {
817 
818  std::vector<CTxMemPoolEntryRef> ret;
819  ret.reserve(mapTx.size());
820  for (const auto& it : GetSortedDepthAndScore()) {
821  ret.emplace_back(*it);
822  }
823  return ret;
824 }
825 
826 std::vector<TxMempoolInfo> CTxMemPool::infoAll() const
827 {
828  LOCK(cs);
829  auto iters = GetSortedDepthAndScore();
830 
831  std::vector<TxMempoolInfo> ret;
832  ret.reserve(mapTx.size());
833  for (auto it : iters) {
834  ret.push_back(GetInfo(it));
835  }
836 
837  return ret;
838 }
839 
840 const CTxMemPoolEntry* CTxMemPool::GetEntry(const Txid& txid) const
841 {
843  const auto i = mapTx.find(txid);
844  return i == mapTx.end() ? nullptr : &(*i);
845 }
846 
848 {
849  LOCK(cs);
850  indexed_transaction_set::const_iterator i = mapTx.find(hash);
851  if (i == mapTx.end())
852  return nullptr;
853  return i->GetSharedTx();
854 }
855 
857 {
858  LOCK(cs);
859  indexed_transaction_set::const_iterator i = (gtxid.IsWtxid() ? get_iter_from_wtxid(gtxid.GetHash()) : mapTx.find(gtxid.GetHash()));
860  if (i == mapTx.end())
861  return TxMempoolInfo();
862  return GetInfo(i);
863 }
864 
865 TxMempoolInfo CTxMemPool::info_for_relay(const GenTxid& gtxid, uint64_t last_sequence) const
866 {
867  LOCK(cs);
868  indexed_transaction_set::const_iterator i = (gtxid.IsWtxid() ? get_iter_from_wtxid(gtxid.GetHash()) : mapTx.find(gtxid.GetHash()));
869  if (i != mapTx.end() && i->GetSequence() < last_sequence) {
870  return GetInfo(i);
871  } else {
872  return TxMempoolInfo();
873  }
874 }
875 
876 void CTxMemPool::PrioritiseTransaction(const uint256& hash, const CAmount& nFeeDelta)
877 {
878  {
879  LOCK(cs);
880  CAmount &delta = mapDeltas[hash];
881  delta = SaturatingAdd(delta, nFeeDelta);
882  txiter it = mapTx.find(hash);
883  if (it != mapTx.end()) {
884  mapTx.modify(it, [&nFeeDelta](CTxMemPoolEntry& e) { e.UpdateModifiedFee(nFeeDelta); });
885  // Now update all ancestors' modified fees with descendants
886  auto ancestors{AssumeCalculateMemPoolAncestors(__func__, *it, Limits::NoLimits(), /*fSearchForParents=*/false)};
887  for (txiter ancestorIt : ancestors) {
888  mapTx.modify(ancestorIt, [=](CTxMemPoolEntry& e){ e.UpdateDescendantState(0, nFeeDelta, 0);});
889  }
890  // Now update all descendants' modified fees with ancestors
891  setEntries setDescendants;
892  CalculateDescendants(it, setDescendants);
893  setDescendants.erase(it);
894  for (txiter descendantIt : setDescendants) {
895  mapTx.modify(descendantIt, [=](CTxMemPoolEntry& e){ e.UpdateAncestorState(0, nFeeDelta, 0, 0); });
896  }
898  }
899  if (delta == 0) {
900  mapDeltas.erase(hash);
901  LogPrintf("PrioritiseTransaction: %s (%sin mempool) delta cleared\n", hash.ToString(), it == mapTx.end() ? "not " : "");
902  } else {
903  LogPrintf("PrioritiseTransaction: %s (%sin mempool) fee += %s, new delta=%s\n",
904  hash.ToString(),
905  it == mapTx.end() ? "not " : "",
906  FormatMoney(nFeeDelta),
907  FormatMoney(delta));
908  }
909  }
910 }
911 
912 void CTxMemPool::ApplyDelta(const uint256& hash, CAmount &nFeeDelta) const
913 {
915  std::map<uint256, CAmount>::const_iterator pos = mapDeltas.find(hash);
916  if (pos == mapDeltas.end())
917  return;
918  const CAmount &delta = pos->second;
919  nFeeDelta += delta;
920 }
921 
923 {
925  mapDeltas.erase(hash);
926 }
927 
928 std::vector<CTxMemPool::delta_info> CTxMemPool::GetPrioritisedTransactions() const
929 {
931  LOCK(cs);
932  std::vector<delta_info> result;
933  result.reserve(mapDeltas.size());
934  for (const auto& [txid, delta] : mapDeltas) {
935  const auto iter{mapTx.find(txid)};
936  const bool in_mempool{iter != mapTx.end()};
937  std::optional<CAmount> modified_fee;
938  if (in_mempool) modified_fee = iter->GetModifiedFee();
939  result.emplace_back(delta_info{in_mempool, delta, modified_fee, txid});
940  }
941  return result;
942 }
943 
945 {
946  const auto it = mapNextTx.find(prevout);
947  return it == mapNextTx.end() ? nullptr : it->second;
948 }
949 
950 std::optional<CTxMemPool::txiter> CTxMemPool::GetIter(const uint256& txid) const
951 {
952  auto it = mapTx.find(txid);
953  if (it != mapTx.end()) return it;
954  return std::nullopt;
955 }
956 
957 CTxMemPool::setEntries CTxMemPool::GetIterSet(const std::set<Txid>& hashes) const
958 {
960  for (const auto& h : hashes) {
961  const auto mi = GetIter(h);
962  if (mi) ret.insert(*mi);
963  }
964  return ret;
965 }
966 
967 std::vector<CTxMemPool::txiter> CTxMemPool::GetIterVec(const std::vector<uint256>& txids) const
968 {
970  std::vector<txiter> ret;
971  ret.reserve(txids.size());
972  for (const auto& txid : txids) {
973  const auto it{GetIter(txid)};
974  if (!it) return {};
975  ret.push_back(*it);
976  }
977  return ret;
978 }
979 
981 {
982  for (unsigned int i = 0; i < tx.vin.size(); i++)
983  if (exists(GenTxid::Txid(tx.vin[i].prevout.hash)))
984  return false;
985  return true;
986 }
987 
988 CCoinsViewMemPool::CCoinsViewMemPool(CCoinsView* baseIn, const CTxMemPool& mempoolIn) : CCoinsViewBacked(baseIn), mempool(mempoolIn) { }
989 
990 bool CCoinsViewMemPool::GetCoin(const COutPoint &outpoint, Coin &coin) const {
991  // Check to see if the inputs are made available by another tx in the package.
992  // These Coins would not be available in the underlying CoinsView.
993  if (auto it = m_temp_added.find(outpoint); it != m_temp_added.end()) {
994  coin = it->second;
995  return true;
996  }
997 
998  // If an entry in the mempool exists, always return that one, as it's guaranteed to never
999  // conflict with the underlying cache, and it cannot have pruned entries (as it contains full)
1000  // transactions. First checking the underlying cache risks returning a pruned entry instead.
1001  CTransactionRef ptx = mempool.get(outpoint.hash);
1002  if (ptx) {
1003  if (outpoint.n < ptx->vout.size()) {
1004  coin = Coin(ptx->vout[outpoint.n], MEMPOOL_HEIGHT, false);
1005  m_non_base_coins.emplace(outpoint);
1006  return true;
1007  } else {
1008  return false;
1009  }
1010  }
1011  return base->GetCoin(outpoint, coin);
1012 }
1013 
1015 {
1016  for (unsigned int n = 0; n < tx->vout.size(); ++n) {
1017  m_temp_added.emplace(COutPoint(tx->GetHash(), n), Coin(tx->vout[n], MEMPOOL_HEIGHT, false));
1018  m_non_base_coins.emplace(tx->GetHash(), n);
1019  }
1020 }
1022 {
1023  m_temp_added.clear();
1024  m_non_base_coins.clear();
1025 }
1026 
1028  LOCK(cs);
1029  // Estimate the overhead of mapTx to be 15 pointers + an allocation, as no exact formula for boost::multi_index_contained is implemented.
1030  return memusage::MallocUsage(sizeof(CTxMemPoolEntry) + 15 * sizeof(void*)) * mapTx.size() + memusage::DynamicUsage(mapNextTx) + memusage::DynamicUsage(mapDeltas) + memusage::DynamicUsage(txns_randomized) + cachedInnerUsage;
1031 }
1032 
1033 void CTxMemPool::RemoveUnbroadcastTx(const uint256& txid, const bool unchecked) {
1034  LOCK(cs);
1035 
1036  if (m_unbroadcast_txids.erase(txid))
1037  {
1038  LogPrint(BCLog::MEMPOOL, "Removed %i from set of unbroadcast txns%s\n", txid.GetHex(), (unchecked ? " before confirmation that txn was sent out" : ""));
1039  }
1040 }
1041 
1042 void CTxMemPool::RemoveStaged(setEntries &stage, bool updateDescendants, MemPoolRemovalReason reason) {
1043  AssertLockHeld(cs);
1044  UpdateForRemoveFromMempool(stage, updateDescendants);
1045  for (txiter it : stage) {
1046  removeUnchecked(it, reason);
1047  }
1048 }
1049 
1050 int CTxMemPool::Expire(std::chrono::seconds time)
1051 {
1052  AssertLockHeld(cs);
1053  indexed_transaction_set::index<entry_time>::type::iterator it = mapTx.get<entry_time>().begin();
1054  setEntries toremove;
1055  while (it != mapTx.get<entry_time>().end() && it->GetTime() < time) {
1056  toremove.insert(mapTx.project<0>(it));
1057  it++;
1058  }
1059  setEntries stage;
1060  for (txiter removeit : toremove) {
1061  CalculateDescendants(removeit, stage);
1062  }
1064  return stage.size();
1065 }
1066 
1067 void CTxMemPool::addUnchecked(const CTxMemPoolEntry &entry)
1068 {
1069  auto ancestors{AssumeCalculateMemPoolAncestors(__func__, entry, Limits::NoLimits())};
1070  return addUnchecked(entry, ancestors);
1071 }
1072 
1073 void CTxMemPool::UpdateChild(txiter entry, txiter child, bool add)
1074 {
1075  AssertLockHeld(cs);
1077  if (add && entry->GetMemPoolChildren().insert(*child).second) {
1078  cachedInnerUsage += memusage::IncrementalDynamicUsage(s);
1079  } else if (!add && entry->GetMemPoolChildren().erase(*child)) {
1080  cachedInnerUsage -= memusage::IncrementalDynamicUsage(s);
1081  }
1082 }
1083 
1084 void CTxMemPool::UpdateParent(txiter entry, txiter parent, bool add)
1085 {
1086  AssertLockHeld(cs);
1088  if (add && entry->GetMemPoolParents().insert(*parent).second) {
1089  cachedInnerUsage += memusage::IncrementalDynamicUsage(s);
1090  } else if (!add && entry->GetMemPoolParents().erase(*parent)) {
1091  cachedInnerUsage -= memusage::IncrementalDynamicUsage(s);
1092  }
1093 }
1094 
1095 CFeeRate CTxMemPool::GetMinFee(size_t sizelimit) const {
1096  LOCK(cs);
1097  if (!blockSinceLastRollingFeeBump || rollingMinimumFeeRate == 0)
1098  return CFeeRate(llround(rollingMinimumFeeRate));
1099 
1100  int64_t time = GetTime();
1101  if (time > lastRollingFeeUpdate + 10) {
1102  double halflife = ROLLING_FEE_HALFLIFE;
1103  if (DynamicMemoryUsage() < sizelimit / 4)
1104  halflife /= 4;
1105  else if (DynamicMemoryUsage() < sizelimit / 2)
1106  halflife /= 2;
1107 
1108  rollingMinimumFeeRate = rollingMinimumFeeRate / pow(2.0, (time - lastRollingFeeUpdate) / halflife);
1109  lastRollingFeeUpdate = time;
1110 
1111  if (rollingMinimumFeeRate < (double)m_incremental_relay_feerate.GetFeePerK() / 2) {
1112  rollingMinimumFeeRate = 0;
1113  return CFeeRate(0);
1114  }
1115  }
1116  return std::max(CFeeRate(llround(rollingMinimumFeeRate)), m_incremental_relay_feerate);
1117 }
1118 
1120  AssertLockHeld(cs);
1121  if (rate.GetFeePerK() > rollingMinimumFeeRate) {
1122  rollingMinimumFeeRate = rate.GetFeePerK();
1123  blockSinceLastRollingFeeBump = false;
1124  }
1125 }
1126 
1127 void CTxMemPool::TrimToSize(size_t sizelimit, std::vector<COutPoint>* pvNoSpendsRemaining) {
1128  AssertLockHeld(cs);
1129 
1130  unsigned nTxnRemoved = 0;
1131  CFeeRate maxFeeRateRemoved(0);
1132  while (!mapTx.empty() && DynamicMemoryUsage() > sizelimit) {
1133  indexed_transaction_set::index<descendant_score>::type::iterator it = mapTx.get<descendant_score>().begin();
1134 
1135  // We set the new mempool min fee to the feerate of the removed set, plus the
1136  // "minimum reasonable fee rate" (ie some value under which we consider txn
1137  // to have 0 fee). This way, we don't allow txn to enter mempool with feerate
1138  // equal to txn which were removed with no block in between.
1139  CFeeRate removed(it->GetModFeesWithDescendants(), it->GetSizeWithDescendants());
1140  removed += m_incremental_relay_feerate;
1141  trackPackageRemoved(removed);
1142  maxFeeRateRemoved = std::max(maxFeeRateRemoved, removed);
1143 
1144  setEntries stage;
1145  CalculateDescendants(mapTx.project<0>(it), stage);
1146  nTxnRemoved += stage.size();
1147 
1148  std::vector<CTransaction> txn;
1149  if (pvNoSpendsRemaining) {
1150  txn.reserve(stage.size());
1151  for (txiter iter : stage)
1152  txn.push_back(iter->GetTx());
1153  }
1155  if (pvNoSpendsRemaining) {
1156  for (const CTransaction& tx : txn) {
1157  for (const CTxIn& txin : tx.vin) {
1158  if (exists(GenTxid::Txid(txin.prevout.hash))) continue;
1159  pvNoSpendsRemaining->push_back(txin.prevout);
1160  }
1161  }
1162  }
1163  }
1164 
1165  if (maxFeeRateRemoved > CFeeRate(0)) {
1166  LogPrint(BCLog::MEMPOOL, "Removed %u txn, rolling minimum fee bumped to %s\n", nTxnRemoved, maxFeeRateRemoved.ToString());
1167  }
1168 }
1169 
1171  // find parent with highest descendant count
1172  std::vector<txiter> candidates;
1173  setEntries counted;
1174  candidates.push_back(entry);
1175  uint64_t maximum = 0;
1176  while (candidates.size()) {
1177  txiter candidate = candidates.back();
1178  candidates.pop_back();
1179  if (!counted.insert(candidate).second) continue;
1180  const CTxMemPoolEntry::Parents& parents = candidate->GetMemPoolParentsConst();
1181  if (parents.size() == 0) {
1182  maximum = std::max(maximum, candidate->GetCountWithDescendants());
1183  } else {
1184  for (const CTxMemPoolEntry& i : parents) {
1185  candidates.push_back(mapTx.iterator_to(i));
1186  }
1187  }
1188  }
1189  return maximum;
1190 }
1191 
1192 void CTxMemPool::GetTransactionAncestry(const uint256& txid, size_t& ancestors, size_t& descendants, size_t* const ancestorsize, CAmount* const ancestorfees) const {
1193  LOCK(cs);
1194  auto it = mapTx.find(txid);
1195  ancestors = descendants = 0;
1196  if (it != mapTx.end()) {
1197  ancestors = it->GetCountWithAncestors();
1198  if (ancestorsize) *ancestorsize = it->GetSizeWithAncestors();
1199  if (ancestorfees) *ancestorfees = it->GetModFeesWithAncestors();
1200  descendants = CalculateDescendantMaximum(it);
1201  }
1202 }
1203 
1205 {
1206  LOCK(cs);
1207  return m_load_tried;
1208 }
1209 
1210 void CTxMemPool::SetLoadTried(bool load_tried)
1211 {
1212  LOCK(cs);
1213  m_load_tried = load_tried;
1214 }
1215 
1216 std::vector<CTxMemPool::txiter> CTxMemPool::GatherClusters(const std::vector<uint256>& txids) const
1217 {
1218  AssertLockHeld(cs);
1219  std::vector<txiter> clustered_txs{GetIterVec(txids)};
1220  // Use epoch: visiting an entry means we have added it to the clustered_txs vector. It does not
1221  // necessarily mean the entry has been processed.
1223  for (const auto& it : clustered_txs) {
1224  visited(it);
1225  }
1226  // i = index of where the list of entries to process starts
1227  for (size_t i{0}; i < clustered_txs.size(); ++i) {
1228  // DoS protection: if there are 500 or more entries to process, just quit.
1229  if (clustered_txs.size() > 500) return {};
1230  const txiter& tx_iter = clustered_txs.at(i);
1231  for (const auto& entries : {tx_iter->GetMemPoolParentsConst(), tx_iter->GetMemPoolChildrenConst()}) {
1232  for (const CTxMemPoolEntry& entry : entries) {
1233  const auto entry_it = mapTx.iterator_to(entry);
1234  if (!visited(entry_it)) {
1235  clustered_txs.push_back(entry_it);
1236  }
1237  }
1238  }
1239  }
1240  return clustered_txs;
1241 }
1242 
1243 std::optional<std::string> CTxMemPool::CheckConflictTopology(const setEntries& direct_conflicts)
1244 {
1245  for (const auto& direct_conflict : direct_conflicts) {
1246  // Ancestor and descendant counts are inclusive of the tx itself.
1247  const auto ancestor_count{direct_conflict->GetCountWithAncestors()};
1248  const auto descendant_count{direct_conflict->GetCountWithDescendants()};
1249  const bool has_ancestor{ancestor_count > 1};
1250  const bool has_descendant{descendant_count > 1};
1251  const auto& txid_string{direct_conflict->GetSharedTx()->GetHash().ToString()};
1252  // The only allowed configurations are:
1253  // 1 ancestor and 0 descendant
1254  // 0 ancestor and 1 descendant
1255  // 0 ancestor and 0 descendant
1256  if (ancestor_count > 2) {
1257  return strprintf("%s has %u ancestors, max 1 allowed", txid_string, ancestor_count - 1);
1258  } else if (descendant_count > 2) {
1259  return strprintf("%s has %u descendants, max 1 allowed", txid_string, descendant_count - 1);
1260  } else if (has_ancestor && has_descendant) {
1261  return strprintf("%s has both ancestor and descendant, exceeding cluster limit of 2", txid_string);
1262  }
1263  // Additionally enforce that:
1264  // If we have a child, we are its only parent.
1265  // If we have a parent, we are its only child.
1266  if (has_descendant) {
1267  const auto& our_child = direct_conflict->GetMemPoolChildrenConst().begin();
1268  if (our_child->get().GetCountWithAncestors() > 2) {
1269  return strprintf("%s is not the only parent of child %s",
1270  txid_string, our_child->get().GetSharedTx()->GetHash().ToString());
1271  }
1272  } else if (has_ancestor) {
1273  const auto& our_parent = direct_conflict->GetMemPoolParentsConst().begin();
1274  if (our_parent->get().GetCountWithDescendants() > 2) {
1275  return strprintf("%s is not the only child of parent %s",
1276  txid_string, our_parent->get().GetSharedTx()->GetHash().ToString());
1277  }
1278  }
1279  }
1280  return std::nullopt;
1281 }
1282 
1283 util::Result<std::pair<std::vector<FeeFrac>, std::vector<FeeFrac>>> CTxMemPool::CalculateFeerateDiagramsForRBF(CAmount replacement_fees, int64_t replacement_vsize, const setEntries& direct_conflicts, const setEntries& all_conflicts)
1284 {
1285  Assume(replacement_vsize > 0);
1286 
1287  auto err_string{CheckConflictTopology(direct_conflicts)};
1288  if (err_string.has_value()) {
1289  // Unsupported topology for calculating a feerate diagram
1290  return util::Error{Untranslated(err_string.value())};
1291  }
1292 
1293  // new diagram will have chunks that consist of each ancestor of
1294  // direct_conflicts that is at its own fee/size, along with the replacement
1295  // tx/package at its own fee/size
1296 
1297  // old diagram will consist of each element of all_conflicts either at
1298  // its own feerate (followed by any descendant at its own feerate) or as a
1299  // single chunk at its descendant's ancestor feerate.
1300 
1301  std::vector<FeeFrac> old_chunks;
1302  // Step 1: build the old diagram.
1303 
1304  // The above clusters are all trivially linearized;
1305  // they have a strict topology of 1 or two connected transactions.
1306 
1307  // OLD: Compute existing chunks from all affected clusters
1308  for (auto txiter : all_conflicts) {
1309  // Does this transaction have descendants?
1310  if (txiter->GetCountWithDescendants() > 1) {
1311  // Consider this tx when we consider the descendant.
1312  continue;
1313  }
1314  // Does this transaction have ancestors?
1315  FeeFrac individual{txiter->GetModifiedFee(), txiter->GetTxSize()};
1316  if (txiter->GetCountWithAncestors() > 1) {
1317  // We'll add chunks for either the ancestor by itself and this tx
1318  // by itself, or for a combined package.
1319  FeeFrac package{txiter->GetModFeesWithAncestors(), static_cast<int32_t>(txiter->GetSizeWithAncestors())};
1320  if (individual > package) {
1321  // The individual feerate is higher than the package, and
1322  // therefore higher than the parent's fee. Chunk these
1323  // together.
1324  old_chunks.emplace_back(package);
1325  } else {
1326  // Add two points, one for the parent and one for this child.
1327  old_chunks.emplace_back(package - individual);
1328  old_chunks.emplace_back(individual);
1329  }
1330  } else {
1331  old_chunks.emplace_back(individual);
1332  }
1333  }
1334 
1335  // No topology restrictions post-chunking; sort
1336  std::sort(old_chunks.begin(), old_chunks.end(), std::greater());
1337  std::vector<FeeFrac> old_diagram = BuildDiagramFromChunks(old_chunks);
1338 
1339  std::vector<FeeFrac> new_chunks;
1340 
1341  /* Step 2: build the NEW diagram
1342  * CON = Conflicts of proposed chunk
1343  * CNK = Proposed chunk
1344  * NEW = OLD - CON + CNK: New diagram includes all chunks in OLD, minus
1345  * the conflicts, plus the proposed chunk
1346  */
1347 
1348  // OLD - CON: Add any parents of direct conflicts that are not conflicted themselves
1349  for (auto direct_conflict : direct_conflicts) {
1350  // If a direct conflict has an ancestor that is not in all_conflicts,
1351  // it can be affected by the replacement of the child.
1352  if (direct_conflict->GetMemPoolParentsConst().size() > 0) {
1353  // Grab the parent.
1354  const CTxMemPoolEntry& parent = direct_conflict->GetMemPoolParentsConst().begin()->get();
1355  if (!all_conflicts.count(mapTx.iterator_to(parent))) {
1356  // This transaction would be left over, so add to the NEW
1357  // diagram.
1358  new_chunks.emplace_back(parent.GetModifiedFee(), parent.GetTxSize());
1359  }
1360  }
1361  }
1362  // + CNK: Add the proposed chunk itself
1363  new_chunks.emplace_back(replacement_fees, int32_t(replacement_vsize));
1364 
1365  // No topology restrictions post-chunking; sort
1366  std::sort(new_chunks.begin(), new_chunks.end(), std::greater());
1367  std::vector<FeeFrac> new_diagram = BuildDiagramFromChunks(new_chunks);
1368  return std::make_pair(old_diagram, new_diagram);
1369 }
int64_t CAmount
Amount in satoshis (Can be negative)
Definition: amount.h:12
int ret
#define Assert(val)
Identity function.
Definition: check.h:77
#define Assume(val)
Assume is the identity function.
Definition: check.h:89
An in-memory indexed chain of blocks.
Definition: chain.h:418
bool Contains(const CBlockIndex *pindex) const
Efficiently check whether a block is present in this chain.
Definition: chain.h:448
CCoinsView backed by another CCoinsView.
Definition: coins.h:210
CCoinsView * base
Definition: coins.h:212
CCoinsView that adds a memory cache for transactions to another CCoinsView.
Definition: coins.h:229
Abstract view on the open txout dataset.
Definition: coins.h:173
virtual bool GetCoin(const COutPoint &outpoint, Coin &coin) const
Retrieve the Coin (unspent transaction output) for a given outpoint.
Definition: coins.cpp:12
bool GetCoin(const COutPoint &outpoint, Coin &coin) const override
GetCoin, returning whether it exists and is not spent.
Definition: txmempool.cpp:990
void Reset()
Clear m_temp_added and m_non_base_coins.
Definition: txmempool.cpp:1021
std::unordered_map< COutPoint, Coin, SaltedOutpointHasher > m_temp_added
Coins made available by transactions being validated.
Definition: txmempool.h:853
CCoinsViewMemPool(CCoinsView *baseIn, const CTxMemPool &mempoolIn)
Definition: txmempool.cpp:988
std::unordered_set< COutPoint, SaltedOutpointHasher > m_non_base_coins
Set of all coins that have been fetched from mempool or created using PackageAddTransaction (not base...
Definition: txmempool.h:859
void PackageAddTransaction(const CTransactionRef &tx)
Add the coins created by this transaction.
Definition: txmempool.cpp:1014
const CTxMemPool & mempool
Definition: txmempool.h:861
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
An outpoint - a combination of a transaction hash and an index n into its vout.
Definition: transaction.h:29
uint32_t n
Definition: transaction.h:32
Txid hash
Definition: transaction.h:31
The basic transaction that is broadcasted on the network and contained in blocks.
Definition: transaction.h:296
const Txid & GetHash() const LIFETIMEBOUND
Definition: transaction.h:343
const std::vector< CTxOut > vout
Definition: transaction.h:307
bool IsCoinBase() const
Definition: transaction.h:356
const std::vector< CTxIn > vin
Definition: transaction.h:306
An input of a transaction.
Definition: transaction.h:67
COutPoint prevout
Definition: transaction.h:69
CTxMemPoolEntry stores data about the corresponding transaction, as well as data about all in-mempool...
Definition: mempool_entry.h:66
int64_t nSigOpCostWithAncestors
int64_t m_count_with_descendants
number of descendant transactions
Definition: mempool_entry.h:96
void UpdateAncestorState(int32_t modifySize, CAmount modifyFee, int64_t modifyCount, int64_t modifySigOps)
Definition: txmempool.cpp:387
const CTransaction & GetTx() const
const Parents & GetMemPoolParentsConst() const
CAmount nModFeesWithAncestors
void UpdateModifiedFee(CAmount fee_diff)
size_t DynamicMemoryUsage() const
std::set< CTxMemPoolEntryRef, CompareIteratorByHash > Children
Definition: mempool_entry.h:71
CAmount nModFeesWithDescendants
... and total fees (all including us)
Definition: mempool_entry.h:99
int32_t GetTxSize() const
int64_t nSizeWithDescendants
... and size
Definition: mempool_entry.h:98
int64_t m_count_with_ancestors
void UpdateDescendantState(int32_t modifySize, CAmount modifyFee, int64_t modifyCount)
Definition: txmempool.cpp:378
CAmount GetModifiedFee() const
const CAmount & GetFee() const
static constexpr ExplicitCopyTag ExplicitCopy
int64_t nSizeWithAncestors
const Children & GetMemPoolChildrenConst() const
std::set< CTxMemPoolEntryRef, CompareIteratorByHash > Parents
Definition: mempool_entry.h:70
CTxMemPool stores valid-according-to-the-current-best-chain transactions that may be included in the ...
Definition: txmempool.h:302
void removeConflicts(const CTransaction &tx) EXCLUSIVE_LOCKS_REQUIRED(cs)
Definition: txmempool.cpp:611
std::atomic< unsigned int > nTransactionsUpdated
Used by getblocktemplate to trigger CreateNewBlock() invocation.
Definition: txmempool.h:305
void RemoveUnbroadcastTx(const uint256 &txid, const bool unchecked=false)
Removes a transaction from the unbroadcast set.
Definition: txmempool.cpp:1033
void PrioritiseTransaction(const uint256 &hash, const CAmount &nFeeDelta)
Affect CreateNewBlock prioritisation of transactions.
Definition: txmempool.cpp:876
setEntries AssumeCalculateMemPoolAncestors(std::string_view calling_fn_name, const CTxMemPoolEntry &entry, const Limits &limits, bool fSearchForParents=true) const EXCLUSIVE_LOCKS_REQUIRED(cs)
Same as CalculateMemPoolAncestors, but always returns a (non-optional) setEntries.
Definition: txmempool.cpp:270
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:980
setEntries GetIterSet(const std::set< Txid > &hashes) const EXCLUSIVE_LOCKS_REQUIRED(cs)
Translate a set of hashes into a set of pool iterators to avoid repeated lookups.
Definition: txmempool.cpp:957
std::vector< txiter > GetIterVec(const std::vector< uint256 > &txids) const EXCLUSIVE_LOCKS_REQUIRED(cs)
Translate a list of hashes into a list of mempool iterators to avoid repeated lookups.
Definition: txmempool.cpp:967
ValidationSignals *const m_signals
Definition: txmempool.h:452
void UpdateEntryForAncestors(txiter it, const setEntries &setAncestors) EXCLUSIVE_LOCKS_REQUIRED(cs)
Set ancestor state for an entry.
Definition: txmempool.cpp:299
bool GetLoadTried() const
Definition: txmempool.cpp:1204
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:627
RecursiveMutex cs
This mutex needs to be locked when accessing mapTx or other members that are guarded by it.
Definition: txmempool.h:390
void ClearPrioritisation(const uint256 &hash) EXCLUSIVE_LOCKS_REQUIRED(cs)
Definition: txmempool.cpp:922
void trackPackageRemoved(const CFeeRate &rate) EXCLUSIVE_LOCKS_REQUIRED(cs)
Definition: txmempool.cpp:1119
util::Result< setEntries > CalculateMemPoolAncestors(const CTxMemPoolEntry &entry, const Limits &limits, bool fSearchForParents=true) const EXCLUSIVE_LOCKS_REQUIRED(cs)
Try to calculate all in-mempool ancestors of entry.
Definition: txmempool.cpp:238
void removeRecursive(const CTransaction &tx, MemPoolRemovalReason reason) EXCLUSIVE_LOCKS_REQUIRED(cs)
Definition: txmempool.cpp:561
const int m_check_ratio
Value n means that 1 times in n we check.
Definition: txmempool.h:304
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:1127
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:103
return !it visited * it
Definition: txmempool.h:830
void AddTransactionsUpdated(unsigned int n)
Definition: txmempool.cpp:426
void UpdateChildrenForRemoval(txiter entry) EXCLUSIVE_LOCKS_REQUIRED(cs)
Sever link between specified transaction and direct children.
Definition: txmempool.cpp:313
std::optional< txiter > GetIter(const uint256 &txid) const EXCLUSIVE_LOCKS_REQUIRED(cs)
Returns an iterator to the given hash, if found.
Definition: txmempool.cpp:950
util::Result< setEntries > CalculateAncestorsAndCheckLimits(int64_t entry_size, size_t entry_count, CTxMemPoolEntry::Parents &staged_ancestors, const Limits &limits) const EXCLUSIVE_LOCKS_REQUIRED(cs)
Helper function to calculate all in-mempool ancestors of staged_ancestors and apply ancestor and desc...
Definition: txmempool.cpp:158
CTransactionRef get(const uint256 &hash) const
Definition: txmempool.cpp:847
size_t DynamicMemoryUsage() const
Definition: txmempool.cpp:1027
std::vector< TxMempoolInfo > infoAll() const
Definition: txmempool.cpp:826
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:1192
void UpdateParent(txiter entry, txiter parent, bool add) EXCLUSIVE_LOCKS_REQUIRED(cs)
Definition: txmempool.cpp:1084
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:486
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:1050
txiter get_iter_from_wtxid(const uint256 &wtxid) const EXCLUSIVE_LOCKS_REQUIRED(cs)
Definition: txmempool.h:690
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:284
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:591
util::Result< void > CheckPackageLimits(const Package &package, int64_t total_vsize) 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:200
TxMempoolInfo info(const GenTxid &gtxid) const
Definition: txmempool.cpp:856
std::vector< txiter > GatherClusters(const std::vector< uint256 > &txids) const EXCLUSIVE_LOCKS_REQUIRED(cs)
Collect the entire cluster of connected transactions for each transaction in txids.
Definition: txmempool.cpp:1216
void ApplyDelta(const uint256 &hash, CAmount &nFeeDelta) const EXCLUSIVE_LOCKS_REQUIRED(cs)
Definition: txmempool.cpp:912
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:52
static const int ROLLING_FEE_HALFLIFE
Definition: txmempool.h:329
std::set< txiter, CompareIteratorByHash > setEntries
Definition: txmempool.h:396
std::vector< indexed_transaction_set::const_iterator > GetSortedDepthAndScore() const EXCLUSIVE_LOCKS_REQUIRED(cs)
Definition: txmempool.cpp:796
void RemoveStaged(setEntries &stage, bool updateDescendants, MemPoolRemovalReason reason) EXCLUSIVE_LOCKS_REQUIRED(cs)
Remove a set of transactions from the mempool.
Definition: txmempool.cpp:1042
void removeForBlock(const std::vector< CTransactionRef > &vtx, unsigned int nBlockHeight) EXCLUSIVE_LOCKS_REQUIRED(cs)
Called when a block is connected.
Definition: txmempool.cpp:631
std::vector< delta_info > GetPrioritisedTransactions() const EXCLUSIVE_LOCKS_REQUIRED(!cs)
Return a vector of all entries in mapDeltas with their corresponding delta_info.
Definition: txmempool.cpp:928
indexed_transaction_set::nth_index< 0 >::type::const_iterator txiter
Definition: txmempool.h:393
uint64_t GetAndIncrementSequence() const EXCLUSIVE_LOCKS_REQUIRED(cs)
Guards this internal counter for external reporting.
Definition: txmempool.h:732
void UpdateChild(txiter entry, txiter child, bool add) EXCLUSIVE_LOCKS_REQUIRED(cs)
Definition: txmempool.cpp:1073
TxMempoolInfo info_for_relay(const GenTxid &gtxid, uint64_t last_sequence) const
Returns info for a transaction if its entry_sequence < last_sequence.
Definition: txmempool.cpp:865
bool exists(const GenTxid &gtxid) const
Definition: txmempool.h:678
std::map< txiter, setEntries, CompareIteratorByHash > cacheMap
Definition: txmempool.h:402
bool m_epoch
Definition: txmempool.h:823
CTxMemPool(const Options &opts)
Create a new CTxMemPool.
Definition: txmempool.cpp:398
const CFeeRate m_incremental_relay_feerate
Definition: txmempool.h:441
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:944
bool CompareDepthAndScore(const uint256 &hasha, const uint256 &hashb, bool wtxid=false)
Definition: txmempool.cpp:760
void CalculateDescendants(txiter it, setEntries &setDescendants) const EXCLUSIVE_LOCKS_REQUIRED(cs)
Populate setDescendants with all in-mempool descendants of hash.
Definition: txmempool.cpp:537
const Limits m_limits
Definition: txmempool.h:450
std::optional< std::string > CheckConflictTopology(const setEntries &direct_conflicts)
Definition: txmempool.cpp:1243
util::Result< std::pair< std::vector< FeeFrac >, std::vector< FeeFrac > > > CalculateFeerateDiagramsForRBF(CAmount replacement_fees, int64_t replacement_vsize, const setEntries &direct_conflicts, const setEntries &all_conflicts) EXCLUSIVE_LOCKS_REQUIRED(cs)
Calculate the old and new mempool feerate diagrams relating to the clusters that would be affected by...
Definition: txmempool.cpp:1283
void check(const CCoinsViewCache &active_coins_tip, int64_t spendheight) const EXCLUSIVE_LOCKS_REQUIRED(void cs_main
Definition: txmempool.h:476
void SetLoadTried(bool load_tried)
Set whether or not an initial attempt to load the persisted mempool was made (regardless of whether t...
Definition: txmempool.cpp:1210
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:321
std::vector< CTxMemPoolEntryRef > entryAll() const EXCLUSIVE_LOCKS_REQUIRED(cs)
Definition: txmempool.cpp:814
uint64_t CalculateDescendantMaximum(txiter entry) const EXCLUSIVE_LOCKS_REQUIRED(cs)
Definition: txmempool.cpp:1170
bool isSpent(const COutPoint &outpoint) const
Definition: txmempool.cpp:415
const CTxMemPoolEntry * GetEntry(const Txid &txid) const LIFETIMEBOUND EXCLUSIVE_LOCKS_REQUIRED(cs)
Definition: txmempool.cpp:840
unsigned int GetTransactionsUpdated() const
Definition: txmempool.cpp:421
void check(const CCoinsViewCache &active_coins_tip, int64_t spendheight) const EXCLUSIVE_LOCKS_REQUIRED(void addUnchecked(const CTxMemPoolEntry &entry) 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:476
A UTXO entry.
Definition: coins.h:32
Sort by feerate of entry (fee/size) in descending order This is only used for transaction relay,...
Definition: txmempool.h:135
A generic txid reference (txid or wtxid).
Definition: transaction.h:428
bool IsWtxid() const
Definition: transaction.h:436
const uint256 & GetHash() const LIFETIMEBOUND
Definition: transaction.h:437
static GenTxid Txid(const uint256 &hash)
Definition: transaction.h:434
void MempoolTransactionsRemovedForBlock(const std::vector< RemovedMempoolTransactionInfo > &, unsigned int nBlockHeight)
void TransactionRemovedFromMempool(const CTransactionRef &, MemPoolRemovalReason, uint64_t mempool_sequence)
std::string ToString() const
Definition: uint256.cpp:55
std::string GetHex() const
Definition: uint256.cpp:11
static transaction_identifier FromUint256(const uint256 &id)
constexpr const std::byte * data() const
256-bit opaque blob.
Definition: uint256.h:106
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:117
RecursiveMutex cs_main
Mutex to guard access to validation specific variables, such as reading or changing the chainstate.
Definition: cs_main.cpp:8
#define WITH_FRESH_EPOCH(epoch)
Definition: epochguard.h:100
#define LogPrintLevel(category, level,...)
Definition: logging.h:252
#define LogPrint(category,...)
Definition: logging.h:264
#define LogPrintf(...)
Definition: logging.h:245
LockPoints lp
std::string RemovalReasonToString(const MemPoolRemovalReason &r) noexcept
MemPoolRemovalReason
Reason why a transaction was removed from the mempool, this is passed to the notification signal.
@ 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.
std::string FormatMoney(const CAmount n)
Money parsing/formatting utilities.
Definition: moneystr.cpp:16
@ MEMPOOL
Definition: logging.h:43
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:30
static size_t IncrementalDynamicUsage(const std::set< X, Y > &s)
Definition: memusage.h:106
static size_t MallocUsage(size_t alloc)
Compute the total memory used by allocating alloc bytes.
Definition: memusage.h:51
bilingual_str ErrorString(const Result< T > &result)
Definition: result.h:81
ValidationSignals & m_signals
Definition: interfaces.cpp:476
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:50
std::shared_ptr< const CTransaction > CTransactionRef
Definition: transaction.h:423
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:81
reverse_range< T > reverse_iterate(T &x)
Data structure storing a fee and size, ordered by increasing fee/size.
Definition: feefrac.h:39
CBlockIndex * maxInputBlock
Definition: mempool_entry.h:35
Information about a mempool transaction.
Definition: txmempool.h:211
Options struct containing limit options for a CTxMemPool.
static constexpr MemPoolLimits NoLimits()
int64_t descendant_count
The maximum allowed number of transactions in a package including the entry and its descendants.
int64_t descendant_size_vbytes
The maximum allowed size in virtual bytes of an entry and its descendants within a package.
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 AssertLockNotHeld(cs)
Definition: sync.h:147
#define LOCK(cs)
Definition: sync.h:257
int64_t GetTime()
Definition: time.cpp:97
#define strprintf
Format arguments and return the string or write to given std::ostream (see tinyformat::format doc for...
Definition: tinyformat.h:1162
#define TRACE3(context, event, a, b, c)
Definition: trace.h:35
#define TRACE5(context, event, a, b, c, d, e)
Definition: trace.h:37
bilingual_str Untranslated(std::string original)
Mark a bilingual_str as untranslated.
Definition: translation.h:48
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:35
static TxMempoolInfo GetInfo(CTxMemPool::indexed_transaction_set::const_iterator it)
Definition: txmempool.cpp:810
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:47
std::vector< FeeFrac > BuildDiagramFromChunks(const Span< const FeeFrac > chunks)
Takes the pre-computed and topologically-valid chunks and generates a fee diagram which starts at Fee...
Definition: feefrac.cpp:10
AssertLockHeld(pool.cs)
assert(!tx.IsCoinBase())