Bitcoin ABC  0.26.3
P2P Digital Currency
txmempool.cpp
Go to the documentation of this file.
1 // Copyright (c) 2009-2010 Satoshi Nakamoto
2 // Copyright (c) 2009-2016 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 <clientversion.h>
9 #include <coins.h>
10 #include <common/system.h>
11 #include <config.h>
12 #include <consensus/consensus.h>
13 #include <consensus/tx_verify.h>
14 #include <consensus/validation.h>
15 #include <logging.h>
16 #include <policy/fees.h>
17 #include <policy/policy.h>
18 #include <reverse_iterator.h>
19 #include <undo.h>
20 #include <util/moneystr.h>
21 #include <util/time.h>
22 #include <validationinterface.h>
23 #include <version.h>
24 
25 #include <algorithm>
26 #include <cmath>
27 #include <limits>
28 
30  setEntries &setAncestors,
31  CTxMemPoolEntry::Parents &staged_ancestors) const {
32  while (!staged_ancestors.empty()) {
33  const auto stage = staged_ancestors.begin()->get();
34 
35  txiter stageit = mapTx.find(stage->GetTx().GetId());
36  assert(stageit != mapTx.end());
37  setAncestors.insert(stageit);
38  staged_ancestors.erase(staged_ancestors.begin());
39 
40  const CTxMemPoolEntry::Parents &parents =
41  (*stageit)->GetMemPoolParentsConst();
42  for (const auto &parent : parents) {
43  txiter parent_it = mapTx.find(parent.get()->GetTx().GetId());
44  assert(parent_it != mapTx.end());
45 
46  // If this is a new ancestor, add it.
47  if (setAncestors.count(parent_it) == 0) {
48  staged_ancestors.insert(parent);
49  }
50  }
51  }
52 
53  return true;
54 }
55 
57  const CTxMemPoolEntryRef &entry, setEntries &setAncestors,
58  bool fSearchForParents /* = true */) const {
59  CTxMemPoolEntry::Parents staged_ancestors;
60  const CTransaction &tx = entry->GetTx();
61 
62  if (fSearchForParents) {
63  // Get parents of this transaction that are in the mempool
64  // GetMemPoolParents() is only valid for entries in the mempool, so we
65  // iterate mapTx to find parents.
66  for (const CTxIn &in : tx.vin) {
67  std::optional<txiter> piter = GetIter(in.prevout.GetTxId());
68  if (!piter) {
69  continue;
70  }
71  staged_ancestors.insert(**piter);
72  }
73  } else {
74  // If we're not searching for parents, we require this to be an entry in
75  // the mempool already.
76  staged_ancestors = entry->GetMemPoolParentsConst();
77  }
78 
79  return CalculateAncestors(setAncestors, staged_ancestors);
80 }
81 
82 void CTxMemPool::UpdateParentsOf(bool add, txiter it) {
83  // add or remove this tx as a child of each parent
84  for (const auto &parent : (*it)->GetMemPoolParentsConst()) {
85  auto parent_it = mapTx.find(parent.get()->GetTx().GetId());
86  assert(parent_it != mapTx.end());
87  UpdateChild(parent_it, it, add);
88  }
89 }
90 
92  const CTxMemPoolEntry::Children &children =
93  (*it)->GetMemPoolChildrenConst();
94  for (const auto &child : children) {
95  auto updateIt = mapTx.find(child.get()->GetTx().GetId());
96  assert(updateIt != mapTx.end());
97  UpdateParent(updateIt, it, false);
98  }
99 }
100 
102  for (txiter removeIt : entriesToRemove) {
103  // Note that UpdateParentsOf severs the child links that point to
104  // removeIt in the entries for the parents of removeIt.
105  UpdateParentsOf(false, removeIt);
106  }
107 
108  // After updating all the parent links, we can now sever the link between
109  // each transaction being removed and any mempool children (ie, update
110  // CTxMemPoolEntry::m_parents for each direct child of a transaction being
111  // removed).
112  for (txiter removeIt : entriesToRemove) {
113  UpdateChildrenForRemoval(removeIt);
114  }
115 }
116 
118  : m_check_ratio(opts.check_ratio), m_max_size_bytes{opts.max_size_bytes},
119  m_expiry{opts.expiry}, m_min_relay_feerate{opts.min_relay_feerate},
120  m_dust_relay_feerate{opts.dust_relay_feerate},
121  m_permit_bare_multisig{opts.permit_bare_multisig},
122  m_max_datacarrier_bytes{opts.max_datacarrier_bytes},
123  m_require_standard{opts.require_standard} {
124  // lock free clear
125  _clear();
126 }
127 
129 
130 bool CTxMemPool::isSpent(const COutPoint &outpoint) const {
131  LOCK(cs);
132  return mapNextTx.count(outpoint);
133 }
134 
136  return nTransactionsUpdated;
137 }
138 
141 }
142 
144  // get a guaranteed unique id (in case tests re-use the same object)
145  entry->SetEntryId(nextEntryId++);
146 
147  // Update transaction for any feeDelta created by PrioritiseTransaction
148  {
149  Amount feeDelta = Amount::zero();
150  ApplyDelta(entry->GetTx().GetId(), feeDelta);
151  entry->UpdateFeeDelta(feeDelta);
152  }
153 
154  // Add to memory pool without checking anything.
155  // Used by AcceptToMemoryPool(), which DOES do all the appropriate checks.
156  auto [newit, inserted] = mapTx.insert(entry);
157  // Sanity check: It is a programming error if insertion fails (uniqueness
158  // invariants in mapTx are violated, etc)
159  assert(inserted);
160  // Sanity check: We should always end up inserting at the end of the
161  // entry_id index
162  assert(&*mapTx.get<entry_id>().rbegin() == &*newit);
163 
164  // Update cachedInnerUsage to include contained transaction's usage.
165  // (When we update the entry for in-mempool parents, memory usage will be
166  // further updated.)
167  cachedInnerUsage += entry->DynamicMemoryUsage();
168 
169  const CTransaction &tx = entry->GetTx();
170  std::set<TxId> setParentTransactions;
171  for (const CTxIn &in : tx.vin) {
172  mapNextTx.insert(std::make_pair(&in.prevout, &tx));
173  setParentTransactions.insert(in.prevout.GetTxId());
174  }
175  // Don't bother worrying about child transactions of this one. It is
176  // guaranteed that a new transaction arriving will not have any children,
177  // because such children would be orphans.
178 
179  // Update ancestors with information about this tx
180  for (const auto &pit : GetIterSet(setParentTransactions)) {
181  UpdateParent(newit, pit, true);
182  }
183 
184  UpdateParentsOf(true, newit);
185 
187  totalTxSize += entry->GetTxSize();
188  m_total_fee += entry->GetFee();
189 }
190 
192  // We increment mempool sequence value no matter removal reason
193  // even if not directly reported below.
194  uint64_t mempool_sequence = GetAndIncrementSequence();
195 
196  const TxId &txid = (*it)->GetTx().GetId();
197 
198  if (reason != MemPoolRemovalReason::BLOCK) {
199  // Notify clients that a transaction has been removed from the mempool
200  // for any reason except being included in a block. Clients interested
201  // in transactions included in blocks can subscribe to the
202  // BlockConnected notification.
204  (*it)->GetSharedTx(), reason, mempool_sequence);
205 
206  finalizedTxs.remove(txid);
207  }
208 
209  for (const CTxIn &txin : (*it)->GetTx().vin) {
210  mapNextTx.erase(txin.prevout);
211  }
212 
213  /* add logging because unchecked */
214  RemoveUnbroadcastTx(txid, true);
215 
216  totalTxSize -= (*it)->GetTxSize();
217  m_total_fee -= (*it)->GetFee();
218  cachedInnerUsage -= (*it)->DynamicMemoryUsage();
219  cachedInnerUsage -=
220  memusage::DynamicUsage((*it)->GetMemPoolParentsConst()) +
221  memusage::DynamicUsage((*it)->GetMemPoolChildrenConst());
222  mapTx.erase(it);
224 }
225 
226 // Calculates descendants of entry that are not already in setDescendants, and
227 // adds to setDescendants. Assumes entryit is already a tx in the mempool and
228 // CTxMemPoolEntry::m_children is correct for tx and all descendants. Also
229 // assumes that if an entry is in setDescendants already, then all in-mempool
230 // descendants of it are already in setDescendants as well, so that we can save
231 // time by not iterating over those entries.
233  setEntries &setDescendants) const {
234  setEntries stage;
235  if (setDescendants.count(entryit) == 0) {
236  stage.insert(entryit);
237  }
238  // Traverse down the children of entry, only adding children that are not
239  // accounted for in setDescendants already (because those children have
240  // either already been walked, or will be walked in this iteration).
241  while (!stage.empty()) {
242  txiter it = *stage.begin();
243  setDescendants.insert(it);
244  stage.erase(stage.begin());
245 
246  const CTxMemPoolEntry::Children &children =
247  (*it)->GetMemPoolChildrenConst();
248  for (const auto &child : children) {
249  txiter childiter = mapTx.find(child.get()->GetTx().GetId());
250  assert(childiter != mapTx.end());
251 
252  if (!setDescendants.count(childiter)) {
253  stage.insert(childiter);
254  }
255  }
256  }
257 }
258 
260  MemPoolRemovalReason reason) {
261  // Remove transaction from memory pool.
263  setEntries txToRemove;
264  txiter origit = mapTx.find(origTx.GetId());
265  if (origit != mapTx.end()) {
266  txToRemove.insert(origit);
267  } else {
268  // When recursively removing but origTx isn't in the mempool be sure to
269  // remove any children that are in the pool. This can happen during
270  // chain re-orgs if origTx isn't re-accepted into the mempool for any
271  // reason.
272  auto it = mapNextTx.lower_bound(COutPoint(origTx.GetId(), 0));
273  while (it != mapNextTx.end() &&
274  it->first->GetTxId() == origTx.GetId()) {
275  txiter nextit = mapTx.find(it->second->GetId());
276  assert(nextit != mapTx.end());
277  txToRemove.insert(nextit);
278  ++it;
279  }
280  }
281 
282  setEntries setAllRemoves;
283  for (txiter it : txToRemove) {
284  CalculateDescendants(it, setAllRemoves);
285  }
286 
287  RemoveStaged(setAllRemoves, reason);
288 }
289 
291  // Remove transactions which depend on inputs of tx, recursively
293  for (const CTxIn &txin : tx.vin) {
294  auto it = mapNextTx.find(txin.prevout);
295  if (it != mapNextTx.end()) {
296  const CTransaction &txConflict = *it->second;
297  if (txConflict != tx) {
298  ClearPrioritisation(txConflict.GetId());
300  }
301  }
302  }
303 }
304 
310 
311  lastRollingFeeUpdate = GetTime();
312  blockSinceLastRollingFeeBump = true;
313 }
314 
316  const std::vector<CTransactionRef> &vtx) {
318 
319  for (const auto &tx : vtx) {
320  // If the tx has a parent, it will be in the block as well or the block
321  // is invalid. If the tx has a child, it can remain in the tree for the
322  // next block. So we can simply remove the txs from the block with no
323  // further check.
324  finalizedTxs.remove(tx->GetId());
325  }
326 }
327 
329  mapTx.clear();
330  mapNextTx.clear();
331  totalTxSize = 0;
332  m_total_fee = Amount::zero();
333  cachedInnerUsage = 0;
334  lastRollingFeeUpdate = GetTime();
335  blockSinceLastRollingFeeBump = false;
336  rollingMinimumFeeRate = 0;
338 }
339 
341  LOCK(cs);
342  _clear();
343 }
344 
345 void CTxMemPool::check(const CCoinsViewCache &active_coins_tip,
346  int64_t spendheight) const {
347  if (m_check_ratio == 0) {
348  return;
349  }
350 
351  if (GetRand(m_check_ratio) >= 1) {
352  return;
353  }
354 
356  LOCK(cs);
358  "Checking mempool with %u transactions and %u inputs\n",
359  (unsigned int)mapTx.size(), (unsigned int)mapNextTx.size());
360 
361  uint64_t checkTotal = 0;
362  Amount check_total_fee{Amount::zero()};
363  uint64_t innerUsage = 0;
364 
365  CCoinsViewCache mempoolDuplicate(
366  const_cast<CCoinsViewCache *>(&active_coins_tip));
367 
368  for (const CTxMemPoolEntryRef &entry : mapTx.get<entry_id>()) {
369  checkTotal += entry->GetTxSize();
370  check_total_fee += entry->GetFee();
371  innerUsage += entry->DynamicMemoryUsage();
372  const CTransaction &tx = entry->GetTx();
373  innerUsage += memusage::DynamicUsage(entry->GetMemPoolParentsConst()) +
374  memusage::DynamicUsage(entry->GetMemPoolChildrenConst());
375 
376  CTxMemPoolEntry::Parents setParentCheck;
377  for (const CTxIn &txin : tx.vin) {
378  // Check that every mempool transaction's inputs refer to available
379  // coins, or other mempool tx's.
380  txiter parentIt = mapTx.find(txin.prevout.GetTxId());
381  if (parentIt != mapTx.end()) {
382  const CTransaction &parentTx = (*parentIt)->GetTx();
383  assert(parentTx.vout.size() > txin.prevout.GetN() &&
384  !parentTx.vout[txin.prevout.GetN()].IsNull());
385  setParentCheck.insert(*parentIt);
386  // also check that parents have a topological ordering before
387  // their children
388  assert((*parentIt)->GetEntryId() < entry->GetEntryId());
389  }
390  // We are iterating through the mempool entries sorted
391  // topologically.
392  // All parents must have been checked before their children and
393  // their coins added to the mempoolDuplicate coins cache.
394  assert(mempoolDuplicate.HaveCoin(txin.prevout));
395  // Check whether its inputs are marked in mapNextTx.
396  auto prevoutNextIt = mapNextTx.find(txin.prevout);
397  assert(prevoutNextIt != mapNextTx.end());
398  assert(prevoutNextIt->first == &txin.prevout);
399  assert(prevoutNextIt->second == &tx);
400  }
401  auto comp = [](const auto &a, const auto &b) -> bool {
402  return a.get()->GetTx().GetId() == b.get()->GetTx().GetId();
403  };
404  assert(setParentCheck.size() == entry->GetMemPoolParentsConst().size());
405  assert(std::equal(setParentCheck.begin(), setParentCheck.end(),
406  entry->GetMemPoolParentsConst().begin(), comp));
407 
408  // Verify ancestor state is correct.
409  setEntries setAncestors;
410  std::string dummy;
411 
412  const bool ok = CalculateMemPoolAncestors(entry, setAncestors);
413  assert(ok);
414 
415  // all ancestors should have entryId < this tx's entryId
416  for (const auto &ancestor : setAncestors) {
417  assert((*ancestor)->GetEntryId() < entry->GetEntryId());
418  }
419 
420  // Check children against mapNextTx
421  CTxMemPoolEntry::Children setChildrenCheck;
422  auto iter = mapNextTx.lower_bound(COutPoint(entry->GetTx().GetId(), 0));
423  for (; iter != mapNextTx.end() &&
424  iter->first->GetTxId() == entry->GetTx().GetId();
425  ++iter) {
426  txiter childIt = mapTx.find(iter->second->GetId());
427  // mapNextTx points to in-mempool transactions
428  assert(childIt != mapTx.end());
429  setChildrenCheck.insert(*childIt);
430  }
431  assert(setChildrenCheck.size() ==
432  entry->GetMemPoolChildrenConst().size());
433  assert(std::equal(setChildrenCheck.begin(), setChildrenCheck.end(),
434  entry->GetMemPoolChildrenConst().begin(), comp));
435 
436  // Not used. CheckTxInputs() should always pass
437  TxValidationState dummy_state;
438  Amount txfee{Amount::zero()};
439  assert(!tx.IsCoinBase());
440  assert(Consensus::CheckTxInputs(tx, dummy_state, mempoolDuplicate,
441  spendheight, txfee));
442  for (const auto &input : tx.vin) {
443  mempoolDuplicate.SpendCoin(input.prevout);
444  }
445  AddCoins(mempoolDuplicate, tx, std::numeric_limits<int>::max());
446  }
447 
448  for (auto &[_, nextTx] : mapNextTx) {
449  txiter it = mapTx.find(nextTx->GetId());
450  assert(it != mapTx.end());
451  assert(&(*it)->GetTx() == nextTx);
452  }
453 
454  assert(totalTxSize == checkTotal);
455  assert(m_total_fee == check_total_fee);
456  assert(innerUsage == cachedInnerUsage);
457 }
458 
460  const TxId &txidb) const {
461  LOCK(cs);
462  auto it1 = mapTx.find(txida);
463  if (it1 == mapTx.end()) {
464  return false;
465  }
466  auto it2 = mapTx.find(txidb);
467  if (it2 == mapTx.end()) {
468  return true;
469  }
470  return (*it1)->GetEntryId() < (*it2)->GetEntryId();
471 }
472 
473 void CTxMemPool::getAllTxIds(std::vector<TxId> &vtxid) const {
474  LOCK(cs);
475 
476  vtxid.clear();
477  vtxid.reserve(mapTx.size());
478 
479  for (const auto &entry : mapTx.get<entry_id>()) {
480  vtxid.push_back(entry->GetTx().GetId());
481  }
482 }
483 
484 static TxMempoolInfo
485 GetInfo(CTxMemPool::indexed_transaction_set::const_iterator it) {
486  return TxMempoolInfo{(*it)->GetSharedTx(), (*it)->GetTime(),
487  (*it)->GetFee(), (*it)->GetTxSize(),
488  (*it)->GetModifiedFee() - (*it)->GetFee()};
489 }
490 
491 std::vector<TxMempoolInfo> CTxMemPool::infoAll() const {
492  LOCK(cs);
493 
494  std::vector<TxMempoolInfo> ret;
495  ret.reserve(mapTx.size());
496 
497  const auto &index = mapTx.get<entry_id>();
498  for (auto it = index.begin(); it != index.end(); ++it) {
499  ret.push_back(GetInfo(mapTx.project<0>(it)));
500  }
501 
502  return ret;
503 }
504 
506  LOCK(cs);
507  indexed_transaction_set::const_iterator i = mapTx.find(txid);
508  if (i == mapTx.end()) {
509  return nullptr;
510  }
511 
512  return (*i)->GetSharedTx();
513 }
514 
515 TxMempoolInfo CTxMemPool::info(const TxId &txid) const {
516  LOCK(cs);
517  indexed_transaction_set::const_iterator i = mapTx.find(txid);
518  if (i == mapTx.end()) {
519  return TxMempoolInfo();
520  }
521 
522  return GetInfo(i);
523 }
524 
526  LOCK(cs);
527 
528  // minerPolicy uses recent blocks to figure out a reasonable fee. This
529  // may disagree with the rollingMinimumFeerate under certain scenarios
530  // where the mempool increases rapidly, or blocks are being mined which
531  // do not contain propagated transactions.
532  return std::max(m_min_relay_feerate, GetMinFee());
533 }
534 
536  const Amount nFeeDelta) {
537  {
538  LOCK(cs);
539  Amount &delta = mapDeltas[txid];
540  delta += nFeeDelta;
541  txiter it = mapTx.find(txid);
542  if (it != mapTx.end()) {
543  mapTx.modify(it, [&delta](CTxMemPoolEntryRef &e) {
544  e->UpdateFeeDelta(delta);
545  });
547  }
548  }
549  LogPrintf("PrioritiseTransaction: %s fee += %s\n", txid.ToString(),
550  FormatMoney(nFeeDelta));
551 }
552 
553 void CTxMemPool::ApplyDelta(const TxId &txid, Amount &nFeeDelta) const {
555  std::map<TxId, Amount>::const_iterator pos = mapDeltas.find(txid);
556  if (pos == mapDeltas.end()) {
557  return;
558  }
559 
560  nFeeDelta += pos->second;
561 }
562 
565  mapDeltas.erase(txid);
566 }
567 
568 const CTransaction *CTxMemPool::GetConflictTx(const COutPoint &prevout) const {
569  const auto it = mapNextTx.find(prevout);
570  return it == mapNextTx.end() ? nullptr : it->second;
571 }
572 
573 std::optional<CTxMemPool::txiter> CTxMemPool::GetIter(const TxId &txid) const {
574  auto it = mapTx.find(txid);
575  if (it != mapTx.end()) {
576  return it;
577  }
578  return std::nullopt;
579 }
580 
582 CTxMemPool::GetIterSet(const std::set<TxId> &txids) const {
584  for (const auto &txid : txids) {
585  const auto mi = GetIter(txid);
586  if (mi) {
587  ret.insert(*mi);
588  }
589  }
590  return ret;
591 }
592 
594  for (const CTxIn &in : tx.vin) {
595  if (exists(in.prevout.GetTxId())) {
596  return false;
597  }
598  }
599 
600  return true;
601 }
602 
604  const CTxMemPool &mempoolIn)
605  : CCoinsViewBacked(baseIn), mempool(mempoolIn) {}
606 
607 bool CCoinsViewMemPool::GetCoin(const COutPoint &outpoint, Coin &coin) const {
608  // Check to see if the inputs are made available by another tx in the
609  // package. These Coins would not be available in the underlying CoinsView.
610  if (auto it = m_temp_added.find(outpoint); it != m_temp_added.end()) {
611  coin = it->second;
612  return true;
613  }
614 
615  // If an entry in the mempool exists, always return that one, as it's
616  // guaranteed to never conflict with the underlying cache, and it cannot
617  // have pruned entries (as it contains full) transactions. First checking
618  // the underlying cache risks returning a pruned entry instead.
619  CTransactionRef ptx = mempool.get(outpoint.GetTxId());
620  if (ptx) {
621  if (outpoint.GetN() < ptx->vout.size()) {
622  coin = Coin(ptx->vout[outpoint.GetN()], MEMPOOL_HEIGHT, false);
623  return true;
624  }
625  return false;
626  }
627  return base->GetCoin(outpoint, coin);
628 }
629 
631  for (uint32_t n = 0; n < tx->vout.size(); ++n) {
632  m_temp_added.emplace(COutPoint(tx->GetId(), n),
633  Coin(tx->vout[n], MEMPOOL_HEIGHT, false));
634  }
635 }
636 
638  LOCK(cs);
639  // Estimate the overhead of mapTx to be 12 pointers + an allocation, as no
640  // exact formula for boost::multi_index_contained is implemented.
641  return memusage::MallocUsage(sizeof(CTxMemPoolEntry) +
642  12 * sizeof(void *)) *
643  mapTx.size() +
644  memusage::DynamicUsage(mapNextTx) +
645  memusage::DynamicUsage(mapDeltas) + cachedInnerUsage;
646 }
647 
648 void CTxMemPool::RemoveUnbroadcastTx(const TxId &txid, const bool unchecked) {
649  LOCK(cs);
650 
651  if (m_unbroadcast_txids.erase(txid)) {
652  LogPrint(
653  BCLog::MEMPOOL, "Removed %i from set of unbroadcast txns%s\n",
654  txid.GetHex(),
655  (unchecked ? " before confirmation that txn was sent out" : ""));
656  }
657 }
658 
660  MemPoolRemovalReason reason) {
663 
664  // Remove txs in reverse-topological order
665  const setRevTopoEntries stageRevTopo(stage.begin(), stage.end());
666  for (txiter it : stageRevTopo) {
667  removeUnchecked(it, reason);
668  }
669 }
670 
671 int CTxMemPool::Expire(std::chrono::seconds time) {
673  indexed_transaction_set::index<entry_time>::type::iterator it =
674  mapTx.get<entry_time>().begin();
675  setEntries toremove;
676  while (it != mapTx.get<entry_time>().end() && (*it)->GetTime() < time) {
677  toremove.insert(mapTx.project<0>(it));
678  it++;
679  }
680 
681  setEntries stage;
682  for (txiter removeit : toremove) {
683  CalculateDescendants(removeit, stage);
684  }
685 
687  return stage.size();
688 }
689 
693  int expired = Expire(GetTime<std::chrono::seconds>() - m_expiry);
694  if (expired != 0) {
696  "Expired %i transactions from the memory pool\n", expired);
697  }
698 
699  std::vector<COutPoint> vNoSpendsRemaining;
700  TrimToSize(m_max_size_bytes, &vNoSpendsRemaining);
701  for (const COutPoint &removed : vNoSpendsRemaining) {
702  coins_cache.Uncache(removed);
703  }
704 }
705 
706 void CTxMemPool::UpdateChild(txiter entry, txiter child, bool add) {
709  if (add && (*entry)->GetMemPoolChildren().insert(*child).second) {
710  cachedInnerUsage += memusage::IncrementalDynamicUsage(s);
711  } else if (!add && (*entry)->GetMemPoolChildren().erase(*child)) {
712  cachedInnerUsage -= memusage::IncrementalDynamicUsage(s);
713  }
714 }
715 
716 void CTxMemPool::UpdateParent(txiter entry, txiter parent, bool add) {
719  if (add && (*entry)->GetMemPoolParents().insert(*parent).second) {
720  cachedInnerUsage += memusage::IncrementalDynamicUsage(s);
721  } else if (!add && (*entry)->GetMemPoolParents().erase(*parent)) {
722  cachedInnerUsage -= memusage::IncrementalDynamicUsage(s);
723  }
724 }
725 
726 CFeeRate CTxMemPool::GetMinFee(size_t sizelimit) const {
727  LOCK(cs);
728  if (!blockSinceLastRollingFeeBump || rollingMinimumFeeRate == 0) {
729  return CFeeRate(int64_t(ceill(rollingMinimumFeeRate)) * SATOSHI);
730  }
731 
732  int64_t time = GetTime();
733  if (time > lastRollingFeeUpdate + 10) {
734  double halflife = ROLLING_FEE_HALFLIFE;
735  if (DynamicMemoryUsage() < sizelimit / 4) {
736  halflife /= 4;
737  } else if (DynamicMemoryUsage() < sizelimit / 2) {
738  halflife /= 2;
739  }
740 
741  rollingMinimumFeeRate =
742  rollingMinimumFeeRate /
743  pow(2.0, (time - lastRollingFeeUpdate) / halflife);
744  lastRollingFeeUpdate = time;
745  }
746  return CFeeRate(int64_t(ceill(rollingMinimumFeeRate)) * SATOSHI);
747 }
748 
751  if ((rate.GetFeePerK() / SATOSHI) > rollingMinimumFeeRate) {
752  rollingMinimumFeeRate = rate.GetFeePerK() / SATOSHI;
753  blockSinceLastRollingFeeBump = false;
754  }
755 }
756 
757 void CTxMemPool::TrimToSize(size_t sizelimit,
758  std::vector<COutPoint> *pvNoSpendsRemaining) {
760 
761  unsigned nTxnRemoved = 0;
762  CFeeRate maxFeeRateRemoved(Amount::zero());
763  while (!mapTx.empty() && DynamicMemoryUsage() > sizelimit) {
764  auto it = mapTx.get<modified_feerate>().end();
765  --it;
766 
767  // We set the new mempool min fee to the feerate of the removed
768  // transaction, plus the "minimum reasonable fee rate" (ie some value
769  // under which we consider txn to have 0 fee). This way, we don't allow
770  // txn to enter mempool with feerate equal to txn which were removed
771  // with no block in between.
772  CFeeRate removed = (*it)->GetModifiedFeeRate();
773  removed += MEMPOOL_FULL_FEE_INCREMENT;
774 
775  trackPackageRemoved(removed);
776  maxFeeRateRemoved = std::max(maxFeeRateRemoved, removed);
777 
778  setEntries stage;
779  CalculateDescendants(mapTx.project<0>(it), stage);
780  nTxnRemoved += stage.size();
781 
782  if (pvNoSpendsRemaining) {
783  for (const txiter &iter : stage) {
784  for (const CTxIn &txin : (*iter)->GetTx().vin) {
785  if (!exists(txin.prevout.GetTxId())) {
786  pvNoSpendsRemaining->push_back(txin.prevout);
787  }
788  }
789  }
790  }
791 
793  }
794 
795  if (maxFeeRateRemoved > CFeeRate(Amount::zero())) {
797  "Removed %u txn, rolling minimum fee bumped to %s\n",
798  nTxnRemoved, maxFeeRateRemoved.ToString());
799  }
800 }
801 
803  LOCK(cs);
804  return m_load_tried;
805 }
806 
807 void CTxMemPool::SetLoadTried(bool load_tried) {
808  LOCK(cs);
809  m_load_tried = load_tried;
810 }
811 
812 const std::string
814  switch (r) {
816  return "expiry";
818  return "sizelimit";
820  return "reorg";
822  return "block";
824  return "conflict";
826  return "avalanche";
827  }
828  assert(false);
829 }
static constexpr Amount SATOSHI
Definition: amount.h:143
CCoinsView backed by another CCoinsView.
Definition: coins.h:201
CCoinsView * base
Definition: coins.h:203
CCoinsView that adds a memory cache for transactions to another CCoinsView.
Definition: coins.h:221
void Uncache(const COutPoint &outpoint)
Removes the UTXO with the given outpoint from the cache, if it is not modified.
Definition: coins.cpp:330
Abstract view on the open txout dataset.
Definition: coins.h:163
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:607
std::unordered_map< COutPoint, Coin, SaltedOutpointHasher > m_temp_added
Coins made available by transactions being validated.
Definition: txmempool.h:597
CCoinsViewMemPool(CCoinsView *baseIn, const CTxMemPool &mempoolIn)
Definition: txmempool.cpp:603
void PackageAddTransaction(const CTransactionRef &tx)
Add the coins created by this transaction.
Definition: txmempool.cpp:630
const CTxMemPool & mempool
Definition: txmempool.h:600
Fee rate in satoshis per kilobyte: Amount / kB.
Definition: feerate.h:21
std::string ToString() const
Definition: feerate.cpp:57
Amount GetFeePerK() const
Return the fee in satoshis for a size of 1000 bytes.
Definition: feerate.h:54
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:20
uint32_t GetN() const
Definition: transaction.h:36
const TxId & GetTxId() const
Definition: transaction.h:35
The basic transaction that is broadcasted on the network and contained in blocks.
Definition: transaction.h:192
const std::vector< CTxOut > vout
Definition: transaction.h:207
bool IsCoinBase() const
Definition: transaction.h:252
const std::vector< CTxIn > vin
Definition: transaction.h:206
const TxId GetId() const
Definition: transaction.h:240
An input of a transaction.
Definition: transaction.h:59
COutPoint prevout
Definition: transaction.h:61
CTxMemPoolEntry stores data about the corresponding transaction, as well as data about all in-mempool...
Definition: mempool_entry.h:65
std::set< std::reference_wrapper< const CTxMemPoolEntryRef >, CompareIteratorById > Children
Definition: mempool_entry.h:73
std::set< std::reference_wrapper< const CTxMemPoolEntryRef >, CompareIteratorById > 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:209
void removeConflicts(const CTransaction &tx) EXCLUSIVE_LOCKS_REQUIRED(cs)
Definition: txmempool.cpp:290
CFeeRate estimateFee() const
Definition: txmempool.cpp:525
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:593
void ClearPrioritisation(const TxId &txid) EXCLUSIVE_LOCKS_REQUIRED(cs)
Definition: txmempool.cpp:563
std::set< txiter, CompareIteratorById > setEntries
Definition: txmempool.h:300
void RemoveUnbroadcastTx(const TxId &txid, const bool unchecked=false)
Removes a transaction from the unbroadcast set.
Definition: txmempool.cpp:648
bool GetLoadTried() const
Definition: txmempool.cpp:802
bool CalculateAncestors(setEntries &setAncestors, CTxMemPoolEntry::Parents &staged_ancestors) const EXCLUSIVE_LOCKS_REQUIRED(cs)
Helper function to calculate all in-mempool ancestors of staged_ancestors param@[in] staged_ancestors...
Definition: txmempool.cpp:29
void updateFeeForBlock() EXCLUSIVE_LOCKS_REQUIRED(cs)
Called when a block is connected.
Definition: txmempool.cpp:308
CFeeRate GetMinFee() const
The minimum fee to get into the mempool, which may itself not be enough for larger-sized transactions...
Definition: txmempool.h:440
RecursiveMutex cs
This mutex needs to be locked when accessing mapTx or other members that are guarded by it.
Definition: txmempool.h:296
void trackPackageRemoved(const CFeeRate &rate) EXCLUSIVE_LOCKS_REQUIRED(cs)
Definition: txmempool.cpp:749
void removeRecursive(const CTransaction &tx, MemPoolRemovalReason reason) EXCLUSIVE_LOCKS_REQUIRED(cs)
Definition: txmempool.cpp:259
void UpdateForRemoveFromMempool(const setEntries &entriesToRemove) EXCLUSIVE_LOCKS_REQUIRED(cs)
For each transaction being removed, update ancestors and any direct children.
Definition: txmempool.cpp:101
const int m_check_ratio
Value n means that 1 times in n we check.
Definition: txmempool.h:212
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:757
const std::chrono::seconds m_expiry
Definition: txmempool.h:334
void AddTransactionsUpdated(unsigned int n)
Definition: txmempool.cpp:139
void UpdateChildrenForRemoval(txiter entry) EXCLUSIVE_LOCKS_REQUIRED(cs)
Sever link between specified transaction and direct children.
Definition: txmempool.cpp:91
bool CompareTopologically(const TxId &txida, const TxId &txidb) const
Definition: txmempool.cpp:459
TxMempoolInfo info(const TxId &txid) const
Definition: txmempool.cpp:515
const int64_t m_max_size_bytes
Definition: txmempool.h:333
void getAllTxIds(std::vector< TxId > &vtxid) const
Definition: txmempool.cpp:473
std::atomic< uint32_t > nTransactionsUpdated
Used by getblocktemplate to trigger CreateNewBlock() invocation.
Definition: txmempool.h:214
setEntries GetIterSet(const std::set< TxId > &txids) const EXCLUSIVE_LOCKS_REQUIRED(cs)
Translate a set of txids into a set of pool iterators to avoid repeated lookups.
Definition: txmempool.cpp:582
size_t DynamicMemoryUsage() const
Definition: txmempool.cpp:637
std::vector< TxMempoolInfo > infoAll() const
Definition: txmempool.cpp:491
void LimitSize(CCoinsViewCache &coins_cache) EXCLUSIVE_LOCKS_REQUIRED(cs
Reduce the size of the mempool by expiring and then trimming the mempool.
Definition: txmempool.cpp:690
void UpdateParent(txiter entry, txiter parent, bool add) EXCLUSIVE_LOCKS_REQUIRED(cs)
Definition: txmempool.cpp:716
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:191
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:671
void clear()
Definition: txmempool.cpp:340
std::set< txiter, CompareIteratorByRevEntryId > setRevTopoEntries
Definition: txmempool.h:301
bool exists(const TxId &txid) const
Definition: txmempool.h:492
static const int ROLLING_FEE_HALFLIFE
Definition: txmempool.h:244
CTransactionRef get(const TxId &txid) const
Definition: txmempool.cpp:505
const CFeeRate m_min_relay_feerate
Definition: txmempool.h:335
void PrioritiseTransaction(const TxId &txid, const Amount nFeeDelta)
Affect CreateNewBlock prioritisation of transactions.
Definition: txmempool.cpp:535
indexed_transaction_set::nth_index< 0 >::type::const_iterator txiter
Definition: txmempool.h:299
uint64_t GetAndIncrementSequence() const EXCLUSIVE_LOCKS_REQUIRED(cs)
Guards this internal counter for external reporting.
Definition: txmempool.h:541
void UpdateChild(txiter entry, txiter child, bool add) EXCLUSIVE_LOCKS_REQUIRED(cs)
Definition: txmempool.cpp:706
void check(const CCoinsViewCache &active_coins_tip, int64_t spendheight) const EXCLUSIVE_LOCKS_REQUIRED(void addUnchecked(CTxMemPoolEntryRef 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:361
RadixTree< CTxMemPoolEntry, MemPoolEntryRadixTreeAdapter > finalizedTxs
Definition: txmempool.h:303
CTxMemPool(const Options &opts)
Create a new CTxMemPool.
Definition: txmempool.cpp:117
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:568
bool CalculateMemPoolAncestors(const CTxMemPoolEntryRef &entry, setEntries &setAncestors, bool fSearchForParents=true) const EXCLUSIVE_LOCKS_REQUIRED(cs)
Try to calculate all in-mempool ancestors of entry.
Definition: txmempool.cpp:56
void removeForFinalizedBlock(const std::vector< CTransactionRef > &vtx) EXCLUSIVE_LOCKS_REQUIRED(cs)
Definition: txmempool.cpp:315
void CalculateDescendants(txiter it, setEntries &setDescendants) const EXCLUSIVE_LOCKS_REQUIRED(cs)
Populate setDescendants with all in-mempool descendants of hash.
Definition: txmempool.cpp:232
void RemoveStaged(const setEntries &stage, MemPoolRemovalReason reason) EXCLUSIVE_LOCKS_REQUIRED(cs)
Remove a set of transactions from the mempool.
Definition: txmempool.cpp:659
void UpdateParentsOf(bool add, txiter it) EXCLUSIVE_LOCKS_REQUIRED(cs)
Update parents of it to add/remove it as a child transaction.
Definition: txmempool.cpp:82
void ApplyDelta(const TxId &txid, Amount &nFeeDelta) const EXCLUSIVE_LOCKS_REQUIRED(cs)
Definition: txmempool.cpp:553
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:807
std::optional< txiter > GetIter(const TxId &txid) const EXCLUSIVE_LOCKS_REQUIRED(cs)
Returns an iterator to the given txid, if found.
Definition: txmempool.cpp:573
void check(const CCoinsViewCache &active_coins_tip, int64_t spendheight) const EXCLUSIVE_LOCKS_REQUIRED(void cs_main
Definition: txmempool.h:362
bool isSpent(const COutPoint &outpoint) const
Definition: txmempool.cpp:130
unsigned int GetTransactionsUpdated() const
Definition: txmempool.cpp:135
void _clear() EXCLUSIVE_LOCKS_REQUIRED(cs)
Definition: txmempool.cpp:328
A UTXO entry.
Definition: coins.h:28
Definition: rcu.h:85
T * get()
Get allows to access the undelying pointer.
Definition: rcu.h:170
std::string ToString() const
Definition: uint256.h:80
std::string GetHex() const
Definition: uint256.cpp:16
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:156
#define LogPrint(category,...)
Definition: logging.h:211
#define LogPrintf(...)
Definition: logging.h:207
std::string FormatMoney(const Amount amt)
Do not use these functions to represent or parse monetary amounts to or from JSON but use AmountFromV...
Definition: moneystr.cpp:13
@ MEMPOOL
Definition: logging.h:42
bool CheckTxInputs(const CTransaction &tx, TxValidationState &state, const CCoinsViewCache &inputs, int nSpendHeight, Amount &txfee)
Check whether all inputs of this transaction are valid (no double spends and amounts).
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:27
static size_t IncrementalDynamicUsage(const std::set< X, Y > &s)
Definition: memusage.h:123
static size_t MallocUsage(size_t alloc)
Compute the total memory used by allocating alloc bytes.
Definition: memusage.h:73
static constexpr CFeeRate MEMPOOL_FULL_FEE_INCREMENT(1000 *SATOSHI)
Default for -incrementalrelayfee, which sets the minimum feerate increase for mempool limiting or BIP...
std::shared_ptr< const CTransaction > CTransactionRef
Definition: transaction.h:315
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:85
Definition: amount.h:19
static constexpr Amount zero() noexcept
Definition: amount.h:32
RCUPtr< T > remove(const KeyType &key)
Remove an element from the tree.
Definition: radix.h:181
A TxId is the identifier of a transaction.
Definition: txid.h:14
Information about a mempool transaction.
Definition: txmempool.h:127
Options struct containing options for constructing a CTxMemPool.
#define LOCK(cs)
Definition: sync.h:306
int64_t GetTime()
Definition: time.cpp:109
bilingual_str _(const char *psz)
Translation function.
Definition: translation.h:68
static TxMempoolInfo GetInfo(CTxMemPool::indexed_transaction_set::const_iterator it)
Definition: txmempool.cpp:485
const std::string RemovalReasonToString(const MemPoolRemovalReason &r) noexcept
Definition: txmempool.cpp:813
MemPoolRemovalReason
Reason why a transaction was removed from the mempool, this is passed to the notification signal.
Definition: txmempool.h:148
@ SIZELIMIT
Removed in size limiting.
@ BLOCK
Removed for block.
@ EXPIRY
Expired from mempool.
@ AVALANCHE
Removed by avalanche vote.
@ CONFLICT
Removed for conflict with in-block transaction.
@ REORG
Removed for reorganization.
static const uint32_t MEMPOOL_HEIGHT
Fake height value used in Coins to signify they are only in the memory pool(since 0....
Definition: txmempool.h:45
AssertLockHeld(pool.cs)
assert(!tx.IsCoinBase())
CMainSignals & GetMainSignals()