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