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