Bitcoin Core 30.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(tx.GetWitnessHash(), newit);
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 // Remove entry from txns_randomized by replacing it with the back and deleting the back.
548 txns_randomized[it->idx_randomized] = std::move(txns_randomized.back());
549 txns_randomized[it->idx_randomized].second->idx_randomized = it->idx_randomized;
550 txns_randomized.pop_back();
551 if (txns_randomized.size() * 2 < txns_randomized.capacity()) {
552 txns_randomized.shrink_to_fit();
553 }
554 } else {
555 txns_randomized.clear();
556 }
557
558 totalTxSize -= it->GetTxSize();
559 m_total_fee -= it->GetFee();
560 cachedInnerUsage -= it->DynamicMemoryUsage();
561 cachedInnerUsage -= memusage::DynamicUsage(it->GetMemPoolParentsConst()) + memusage::DynamicUsage(it->GetMemPoolChildrenConst());
562 mapTx.erase(it);
564}
565
566// Calculates descendants of entry that are not already in setDescendants, and adds to
567// setDescendants. Assumes entryit is already a tx in the mempool and CTxMemPoolEntry::m_children
568// is correct for tx and all descendants.
569// Also assumes that if an entry is in setDescendants already, then all
570// in-mempool descendants of it are already in setDescendants as well, so that we
571// can save time by not iterating over those entries.
572void CTxMemPool::CalculateDescendants(txiter entryit, setEntries& setDescendants) const
573{
574 setEntries stage;
575 if (setDescendants.count(entryit) == 0) {
576 stage.insert(entryit);
577 }
578 // Traverse down the children of entry, only adding children that are not
579 // accounted for in setDescendants already (because those children have either
580 // already been walked, or will be walked in this iteration).
581 while (!stage.empty()) {
582 txiter it = *stage.begin();
583 setDescendants.insert(it);
584 stage.erase(it);
585
586 const CTxMemPoolEntry::Children& children = it->GetMemPoolChildrenConst();
587 for (const CTxMemPoolEntry& child : children) {
588 txiter childiter = mapTx.iterator_to(child);
589 if (!setDescendants.count(childiter)) {
590 stage.insert(childiter);
591 }
592 }
593 }
594}
595
597{
598 // Remove transaction from memory pool
600 Assume(!m_have_changeset);
601 setEntries txToRemove;
602 txiter origit = mapTx.find(origTx.GetHash());
603 if (origit != mapTx.end()) {
604 txToRemove.insert(origit);
605 } else {
606 // When recursively removing but origTx isn't in the mempool
607 // be sure to remove any children that are in the pool. This can
608 // happen during chain re-orgs if origTx isn't re-accepted into
609 // the mempool for any reason.
610 for (unsigned int i = 0; i < origTx.vout.size(); i++) {
611 auto it = mapNextTx.find(COutPoint(origTx.GetHash(), i));
612 if (it == mapNextTx.end())
613 continue;
614 txiter nextit = mapTx.find(it->second->GetHash());
615 assert(nextit != mapTx.end());
616 txToRemove.insert(nextit);
617 }
618 }
619 setEntries setAllRemoves;
620 for (txiter it : txToRemove) {
621 CalculateDescendants(it, setAllRemoves);
622 }
623
624 RemoveStaged(setAllRemoves, false, reason);
625}
626
627void CTxMemPool::removeForReorg(CChain& chain, std::function<bool(txiter)> check_final_and_mature)
628{
629 // Remove transactions spending a coinbase which are now immature and no-longer-final transactions
632 Assume(!m_have_changeset);
633
634 setEntries txToRemove;
635 for (indexed_transaction_set::const_iterator it = mapTx.begin(); it != mapTx.end(); it++) {
636 if (check_final_and_mature(it)) txToRemove.insert(it);
637 }
638 setEntries setAllRemoves;
639 for (txiter it : txToRemove) {
640 CalculateDescendants(it, setAllRemoves);
641 }
642 RemoveStaged(setAllRemoves, false, MemPoolRemovalReason::REORG);
643 for (indexed_transaction_set::const_iterator it = mapTx.begin(); it != mapTx.end(); it++) {
644 assert(TestLockPointValidity(chain, it->GetLockPoints()));
645 }
646}
647
649{
650 // Remove transactions which depend on inputs of tx, recursively
652 for (const CTxIn &txin : tx.vin) {
653 auto it = mapNextTx.find(txin.prevout);
654 if (it != mapNextTx.end()) {
655 const CTransaction &txConflict = *it->second;
656 if (Assume(txConflict.GetHash() != tx.GetHash()))
657 {
658 ClearPrioritisation(txConflict.GetHash());
660 }
661 }
662 }
663}
664
665void CTxMemPool::removeForBlock(const std::vector<CTransactionRef>& vtx, unsigned int nBlockHeight)
666{
667 // Remove confirmed txs and conflicts when a new block is connected, updating the fee logic
669 Assume(!m_have_changeset);
670 std::vector<RemovedMempoolTransactionInfo> txs_removed_for_block;
671 if (mapTx.size() || mapNextTx.size() || mapDeltas.size()) {
672 txs_removed_for_block.reserve(vtx.size());
673 for (const auto& tx : vtx) {
674 txiter it = mapTx.find(tx->GetHash());
675 if (it != mapTx.end()) {
676 setEntries stage;
677 stage.insert(it);
678 txs_removed_for_block.emplace_back(*it);
680 }
681 removeConflicts(*tx);
682 ClearPrioritisation(tx->GetHash());
683 }
684 }
685 if (m_opts.signals) {
686 m_opts.signals->MempoolTransactionsRemovedForBlock(txs_removed_for_block, nBlockHeight);
687 }
688 lastRollingFeeUpdate = GetTime();
689 blockSinceLastRollingFeeBump = true;
690}
691
692void CTxMemPool::check(const CCoinsViewCache& active_coins_tip, int64_t spendheight) const
693{
694 if (m_opts.check_ratio == 0) return;
695
696 if (FastRandomContext().randrange(m_opts.check_ratio) >= 1) return;
697
699 LOCK(cs);
700 LogDebug(BCLog::MEMPOOL, "Checking mempool with %u transactions and %u inputs\n", (unsigned int)mapTx.size(), (unsigned int)mapNextTx.size());
701
702 uint64_t checkTotal = 0;
703 CAmount check_total_fee{0};
704 uint64_t innerUsage = 0;
705 uint64_t prev_ancestor_count{0};
706
707 CCoinsViewCache mempoolDuplicate(const_cast<CCoinsViewCache*>(&active_coins_tip));
708
709 for (const auto& it : GetSortedDepthAndScore()) {
710 checkTotal += it->GetTxSize();
711 check_total_fee += it->GetFee();
712 innerUsage += it->DynamicMemoryUsage();
713 const CTransaction& tx = it->GetTx();
714 innerUsage += memusage::DynamicUsage(it->GetMemPoolParentsConst()) + memusage::DynamicUsage(it->GetMemPoolChildrenConst());
715 CTxMemPoolEntry::Parents setParentCheck;
716 for (const CTxIn &txin : tx.vin) {
717 // Check that every mempool transaction's inputs refer to available coins, or other mempool tx's.
718 indexed_transaction_set::const_iterator it2 = mapTx.find(txin.prevout.hash);
719 if (it2 != mapTx.end()) {
720 const CTransaction& tx2 = it2->GetTx();
721 assert(tx2.vout.size() > txin.prevout.n && !tx2.vout[txin.prevout.n].IsNull());
722 setParentCheck.insert(*it2);
723 }
724 // We are iterating through the mempool entries sorted in order by ancestor count.
725 // All parents must have been checked before their children and their coins added to
726 // the mempoolDuplicate coins cache.
727 assert(mempoolDuplicate.HaveCoin(txin.prevout));
728 // Check whether its inputs are marked in mapNextTx.
729 auto it3 = mapNextTx.find(txin.prevout);
730 assert(it3 != mapNextTx.end());
731 assert(it3->first == &txin.prevout);
732 assert(it3->second == &tx);
733 }
734 auto comp = [](const CTxMemPoolEntry& a, const CTxMemPoolEntry& b) -> bool {
735 return a.GetTx().GetHash() == b.GetTx().GetHash();
736 };
737 assert(setParentCheck.size() == it->GetMemPoolParentsConst().size());
738 assert(std::equal(setParentCheck.begin(), setParentCheck.end(), it->GetMemPoolParentsConst().begin(), comp));
739 // Verify ancestor state is correct.
740 auto ancestors{AssumeCalculateMemPoolAncestors(__func__, *it, Limits::NoLimits())};
741 uint64_t nCountCheck = ancestors.size() + 1;
742 int32_t nSizeCheck = it->GetTxSize();
743 CAmount nFeesCheck = it->GetModifiedFee();
744 int64_t nSigOpCheck = it->GetSigOpCost();
745
746 for (txiter ancestorIt : ancestors) {
747 nSizeCheck += ancestorIt->GetTxSize();
748 nFeesCheck += ancestorIt->GetModifiedFee();
749 nSigOpCheck += ancestorIt->GetSigOpCost();
750 }
751
752 assert(it->GetCountWithAncestors() == nCountCheck);
753 assert(it->GetSizeWithAncestors() == nSizeCheck);
754 assert(it->GetSigOpCostWithAncestors() == nSigOpCheck);
755 assert(it->GetModFeesWithAncestors() == nFeesCheck);
756 // Sanity check: we are walking in ascending ancestor count order.
757 assert(prev_ancestor_count <= it->GetCountWithAncestors());
758 prev_ancestor_count = it->GetCountWithAncestors();
759
760 // Check children against mapNextTx
761 CTxMemPoolEntry::Children setChildrenCheck;
762 auto iter = mapNextTx.lower_bound(COutPoint(it->GetTx().GetHash(), 0));
763 int32_t child_sizes{0};
764 for (; iter != mapNextTx.end() && iter->first->hash == it->GetTx().GetHash(); ++iter) {
765 txiter childit = mapTx.find(iter->second->GetHash());
766 assert(childit != mapTx.end()); // mapNextTx points to in-mempool transactions
767 if (setChildrenCheck.insert(*childit).second) {
768 child_sizes += childit->GetTxSize();
769 }
770 }
771 assert(setChildrenCheck.size() == it->GetMemPoolChildrenConst().size());
772 assert(std::equal(setChildrenCheck.begin(), setChildrenCheck.end(), it->GetMemPoolChildrenConst().begin(), comp));
773 // Also check to make sure size is greater than sum with immediate children.
774 // just a sanity check, not definitive that this calc is correct...
775 assert(it->GetSizeWithDescendants() >= child_sizes + it->GetTxSize());
776
777 TxValidationState dummy_state; // Not used. CheckTxInputs() should always pass
778 CAmount txfee = 0;
779 assert(!tx.IsCoinBase());
780 assert(Consensus::CheckTxInputs(tx, dummy_state, mempoolDuplicate, spendheight, txfee));
781 for (const auto& input: tx.vin) mempoolDuplicate.SpendCoin(input.prevout);
782 AddCoins(mempoolDuplicate, tx, std::numeric_limits<int>::max());
783 }
784 for (const auto& [_, next_tx] : mapNextTx) {
785 auto it = mapTx.find(next_tx->GetHash());
786 const CTransaction& tx = it->GetTx();
787 assert(it != mapTx.end());
788 assert(&tx == next_tx);
789 }
790
791 assert(totalTxSize == checkTotal);
792 assert(m_total_fee == check_total_fee);
793 assert(innerUsage == cachedInnerUsage);
794}
795
796bool CTxMemPool::CompareDepthAndScore(const Wtxid& hasha, const Wtxid& hashb) const
797{
798 /* Return `true` if hasha should be considered sooner than hashb. Namely when:
799 * a is not in the mempool, but b is
800 * both are in the mempool and a has fewer ancestors than b
801 * both are in the mempool and a has a higher score than b
802 */
803 LOCK(cs);
804 auto j{GetIter(hashb)};
805 if (!j.has_value()) return false;
806 auto i{GetIter(hasha)};
807 if (!i.has_value()) return true;
808 uint64_t counta = i.value()->GetCountWithAncestors();
809 uint64_t countb = j.value()->GetCountWithAncestors();
810 if (counta == countb) {
811 return CompareTxMemPoolEntryByScore()(*i.value(), *j.value());
812 }
813 return counta < countb;
814}
815
816namespace {
817class DepthAndScoreComparator
818{
819public:
820 bool operator()(const CTxMemPool::indexed_transaction_set::const_iterator& a, const CTxMemPool::indexed_transaction_set::const_iterator& b)
821 {
822 uint64_t counta = a->GetCountWithAncestors();
823 uint64_t countb = b->GetCountWithAncestors();
824 if (counta == countb) {
825 return CompareTxMemPoolEntryByScore()(*a, *b);
826 }
827 return counta < countb;
828 }
829};
830} // namespace
831
832std::vector<CTxMemPool::indexed_transaction_set::const_iterator> CTxMemPool::GetSortedDepthAndScore() const
833{
834 std::vector<indexed_transaction_set::const_iterator> iters;
836
837 iters.reserve(mapTx.size());
838
839 for (indexed_transaction_set::iterator mi = mapTx.begin(); mi != mapTx.end(); ++mi) {
840 iters.push_back(mi);
841 }
842 std::sort(iters.begin(), iters.end(), DepthAndScoreComparator());
843 return iters;
844}
845
846std::vector<CTxMemPoolEntryRef> CTxMemPool::entryAll() const
847{
849
850 std::vector<CTxMemPoolEntryRef> ret;
851 ret.reserve(mapTx.size());
852 for (const auto& it : GetSortedDepthAndScore()) {
853 ret.emplace_back(*it);
854 }
855 return ret;
856}
857
858std::vector<TxMempoolInfo> CTxMemPool::infoAll() const
859{
860 LOCK(cs);
861 auto iters = GetSortedDepthAndScore();
862
863 std::vector<TxMempoolInfo> ret;
864 ret.reserve(mapTx.size());
865 for (auto it : iters) {
866 ret.push_back(GetInfo(it));
867 }
868
869 return ret;
870}
871
873{
875 const auto i = mapTx.find(txid);
876 return i == mapTx.end() ? nullptr : &(*i);
877}
878
880{
881 LOCK(cs);
882 indexed_transaction_set::const_iterator i = mapTx.find(hash);
883 if (i == mapTx.end())
884 return nullptr;
885 return i->GetSharedTx();
886}
887
888void CTxMemPool::PrioritiseTransaction(const Txid& hash, const CAmount& nFeeDelta)
889{
890 {
891 LOCK(cs);
892 CAmount &delta = mapDeltas[hash];
893 delta = SaturatingAdd(delta, nFeeDelta);
894 txiter it = mapTx.find(hash);
895 if (it != mapTx.end()) {
896 mapTx.modify(it, [&nFeeDelta](CTxMemPoolEntry& e) { e.UpdateModifiedFee(nFeeDelta); });
897 // Now update all ancestors' modified fees with descendants
898 auto ancestors{AssumeCalculateMemPoolAncestors(__func__, *it, Limits::NoLimits(), /*fSearchForParents=*/false)};
899 for (txiter ancestorIt : ancestors) {
900 mapTx.modify(ancestorIt, [=](CTxMemPoolEntry& e){ e.UpdateDescendantState(0, nFeeDelta, 0);});
901 }
902 // Now update all descendants' modified fees with ancestors
903 setEntries setDescendants;
904 CalculateDescendants(it, setDescendants);
905 setDescendants.erase(it);
906 for (txiter descendantIt : setDescendants) {
907 mapTx.modify(descendantIt, [=](CTxMemPoolEntry& e){ e.UpdateAncestorState(0, nFeeDelta, 0, 0); });
908 }
910 }
911 if (delta == 0) {
912 mapDeltas.erase(hash);
913 LogPrintf("PrioritiseTransaction: %s (%sin mempool) delta cleared\n", hash.ToString(), it == mapTx.end() ? "not " : "");
914 } else {
915 LogPrintf("PrioritiseTransaction: %s (%sin mempool) fee += %s, new delta=%s\n",
916 hash.ToString(),
917 it == mapTx.end() ? "not " : "",
918 FormatMoney(nFeeDelta),
919 FormatMoney(delta));
920 }
921 }
922}
923
924void CTxMemPool::ApplyDelta(const Txid& hash, CAmount &nFeeDelta) const
925{
927 std::map<Txid, CAmount>::const_iterator pos = mapDeltas.find(hash);
928 if (pos == mapDeltas.end())
929 return;
930 const CAmount &delta = pos->second;
931 nFeeDelta += delta;
932}
933
935{
937 mapDeltas.erase(hash);
938}
939
940std::vector<CTxMemPool::delta_info> CTxMemPool::GetPrioritisedTransactions() const
941{
943 LOCK(cs);
944 std::vector<delta_info> result;
945 result.reserve(mapDeltas.size());
946 for (const auto& [txid, delta] : mapDeltas) {
947 const auto iter{mapTx.find(txid)};
948 const bool in_mempool{iter != mapTx.end()};
949 std::optional<CAmount> modified_fee;
950 if (in_mempool) modified_fee = iter->GetModifiedFee();
951 result.emplace_back(delta_info{in_mempool, delta, modified_fee, txid});
952 }
953 return result;
954}
955
957{
958 const auto it = mapNextTx.find(prevout);
959 return it == mapNextTx.end() ? nullptr : it->second;
960}
961
962std::optional<CTxMemPool::txiter> CTxMemPool::GetIter(const Txid& txid) const
963{
965 auto it = mapTx.find(txid);
966 return it != mapTx.end() ? std::make_optional(it) : std::nullopt;
967}
968
969std::optional<CTxMemPool::txiter> CTxMemPool::GetIter(const Wtxid& wtxid) const
970{
972 auto it{mapTx.project<0>(mapTx.get<index_by_wtxid>().find(wtxid))};
973 return it != mapTx.end() ? std::make_optional(it) : std::nullopt;
974}
975
976CTxMemPool::setEntries CTxMemPool::GetIterSet(const std::set<Txid>& hashes) const
977{
979 for (const auto& h : hashes) {
980 const auto mi = GetIter(h);
981 if (mi) ret.insert(*mi);
982 }
983 return ret;
984}
985
986std::vector<CTxMemPool::txiter> CTxMemPool::GetIterVec(const std::vector<Txid>& txids) const
987{
989 std::vector<txiter> ret;
990 ret.reserve(txids.size());
991 for (const auto& txid : txids) {
992 const auto it{GetIter(txid)};
993 if (!it) return {};
994 ret.push_back(*it);
995 }
996 return ret;
997}
998
1000{
1001 for (unsigned int i = 0; i < tx.vin.size(); i++)
1002 if (exists(tx.vin[i].prevout.hash))
1003 return false;
1004 return true;
1005}
1006
1007CCoinsViewMemPool::CCoinsViewMemPool(CCoinsView* baseIn, const CTxMemPool& mempoolIn) : CCoinsViewBacked(baseIn), mempool(mempoolIn) { }
1008
1009std::optional<Coin> CCoinsViewMemPool::GetCoin(const COutPoint& outpoint) const
1010{
1011 // Check to see if the inputs are made available by another tx in the package.
1012 // These Coins would not be available in the underlying CoinsView.
1013 if (auto it = m_temp_added.find(outpoint); it != m_temp_added.end()) {
1014 return it->second;
1015 }
1016
1017 // If an entry in the mempool exists, always return that one, as it's guaranteed to never
1018 // conflict with the underlying cache, and it cannot have pruned entries (as it contains full)
1019 // transactions. First checking the underlying cache risks returning a pruned entry instead.
1020 CTransactionRef ptx = mempool.get(outpoint.hash);
1021 if (ptx) {
1022 if (outpoint.n < ptx->vout.size()) {
1023 Coin coin(ptx->vout[outpoint.n], MEMPOOL_HEIGHT, false);
1024 m_non_base_coins.emplace(outpoint);
1025 return coin;
1026 }
1027 return std::nullopt;
1028 }
1029 return base->GetCoin(outpoint);
1030}
1031
1033{
1034 for (unsigned int n = 0; n < tx->vout.size(); ++n) {
1035 m_temp_added.emplace(COutPoint(tx->GetHash(), n), Coin(tx->vout[n], MEMPOOL_HEIGHT, false));
1036 m_non_base_coins.emplace(tx->GetHash(), n);
1037 }
1038}
1040{
1041 m_temp_added.clear();
1042 m_non_base_coins.clear();
1043}
1044
1046 LOCK(cs);
1047 // Estimate the overhead of mapTx to be 15 pointers + an allocation, as no exact formula for boost::multi_index_contained is implemented.
1048 return memusage::MallocUsage(sizeof(CTxMemPoolEntry) + 15 * sizeof(void*)) * mapTx.size() + memusage::DynamicUsage(mapNextTx) + memusage::DynamicUsage(mapDeltas) + memusage::DynamicUsage(txns_randomized) + cachedInnerUsage;
1049}
1050
1051void CTxMemPool::RemoveUnbroadcastTx(const Txid& txid, const bool unchecked) {
1052 LOCK(cs);
1053
1054 if (m_unbroadcast_txids.erase(txid))
1055 {
1056 LogDebug(BCLog::MEMPOOL, "Removed %i from set of unbroadcast txns%s\n", txid.GetHex(), (unchecked ? " before confirmation that txn was sent out" : ""));
1057 }
1058}
1059
1060void CTxMemPool::RemoveStaged(setEntries &stage, bool updateDescendants, MemPoolRemovalReason reason) {
1062 UpdateForRemoveFromMempool(stage, updateDescendants);
1063 for (txiter it : stage) {
1064 removeUnchecked(it, reason);
1065 }
1066}
1067
1068int CTxMemPool::Expire(std::chrono::seconds time)
1069{
1071 Assume(!m_have_changeset);
1072 indexed_transaction_set::index<entry_time>::type::iterator it = mapTx.get<entry_time>().begin();
1073 setEntries toremove;
1074 while (it != mapTx.get<entry_time>().end() && it->GetTime() < time) {
1075 toremove.insert(mapTx.project<0>(it));
1076 it++;
1077 }
1078 setEntries stage;
1079 for (txiter removeit : toremove) {
1080 CalculateDescendants(removeit, stage);
1081 }
1083 return stage.size();
1084}
1085
1086void CTxMemPool::UpdateChild(txiter entry, txiter child, bool add)
1087{
1090 if (add && entry->GetMemPoolChildren().insert(*child).second) {
1091 cachedInnerUsage += memusage::IncrementalDynamicUsage(s);
1092 } else if (!add && entry->GetMemPoolChildren().erase(*child)) {
1093 cachedInnerUsage -= memusage::IncrementalDynamicUsage(s);
1094 }
1095}
1096
1097void CTxMemPool::UpdateParent(txiter entry, txiter parent, bool add)
1098{
1101 if (add && entry->GetMemPoolParents().insert(*parent).second) {
1102 cachedInnerUsage += memusage::IncrementalDynamicUsage(s);
1103 } else if (!add && entry->GetMemPoolParents().erase(*parent)) {
1104 cachedInnerUsage -= memusage::IncrementalDynamicUsage(s);
1105 }
1106}
1107
1108CFeeRate CTxMemPool::GetMinFee(size_t sizelimit) const {
1109 LOCK(cs);
1110 if (!blockSinceLastRollingFeeBump || rollingMinimumFeeRate == 0)
1111 return CFeeRate(llround(rollingMinimumFeeRate));
1112
1113 int64_t time = GetTime();
1114 if (time > lastRollingFeeUpdate + 10) {
1115 double halflife = ROLLING_FEE_HALFLIFE;
1116 if (DynamicMemoryUsage() < sizelimit / 4)
1117 halflife /= 4;
1118 else if (DynamicMemoryUsage() < sizelimit / 2)
1119 halflife /= 2;
1120
1121 rollingMinimumFeeRate = rollingMinimumFeeRate / pow(2.0, (time - lastRollingFeeUpdate) / halflife);
1122 lastRollingFeeUpdate = time;
1123
1124 if (rollingMinimumFeeRate < (double)m_opts.incremental_relay_feerate.GetFeePerK() / 2) {
1125 rollingMinimumFeeRate = 0;
1126 return CFeeRate(0);
1127 }
1128 }
1129 return std::max(CFeeRate(llround(rollingMinimumFeeRate)), m_opts.incremental_relay_feerate);
1130}
1131
1134 if (rate.GetFeePerK() > rollingMinimumFeeRate) {
1135 rollingMinimumFeeRate = rate.GetFeePerK();
1136 blockSinceLastRollingFeeBump = false;
1137 }
1138}
1139
1140void CTxMemPool::TrimToSize(size_t sizelimit, std::vector<COutPoint>* pvNoSpendsRemaining) {
1142 Assume(!m_have_changeset);
1143
1144 unsigned nTxnRemoved = 0;
1145 CFeeRate maxFeeRateRemoved(0);
1146 while (!mapTx.empty() && DynamicMemoryUsage() > sizelimit) {
1147 indexed_transaction_set::index<descendant_score>::type::iterator it = mapTx.get<descendant_score>().begin();
1148
1149 // We set the new mempool min fee to the feerate of the removed set, plus the
1150 // "minimum reasonable fee rate" (ie some value under which we consider txn
1151 // to have 0 fee). This way, we don't allow txn to enter mempool with feerate
1152 // equal to txn which were removed with no block in between.
1153 CFeeRate removed(it->GetModFeesWithDescendants(), it->GetSizeWithDescendants());
1155 trackPackageRemoved(removed);
1156 maxFeeRateRemoved = std::max(maxFeeRateRemoved, removed);
1157
1158 setEntries stage;
1159 CalculateDescendants(mapTx.project<0>(it), stage);
1160 nTxnRemoved += stage.size();
1161
1162 std::vector<CTransaction> txn;
1163 if (pvNoSpendsRemaining) {
1164 txn.reserve(stage.size());
1165 for (txiter iter : stage)
1166 txn.push_back(iter->GetTx());
1167 }
1169 if (pvNoSpendsRemaining) {
1170 for (const CTransaction& tx : txn) {
1171 for (const CTxIn& txin : tx.vin) {
1172 if (exists(txin.prevout.hash)) continue;
1173 pvNoSpendsRemaining->push_back(txin.prevout);
1174 }
1175 }
1176 }
1177 }
1178
1179 if (maxFeeRateRemoved > CFeeRate(0)) {
1180 LogDebug(BCLog::MEMPOOL, "Removed %u txn, rolling minimum fee bumped to %s\n", nTxnRemoved, maxFeeRateRemoved.ToString());
1181 }
1182}
1183
1185 // find parent with highest descendant count
1186 std::vector<txiter> candidates;
1187 setEntries counted;
1188 candidates.push_back(entry);
1189 uint64_t maximum = 0;
1190 while (candidates.size()) {
1191 txiter candidate = candidates.back();
1192 candidates.pop_back();
1193 if (!counted.insert(candidate).second) continue;
1194 const CTxMemPoolEntry::Parents& parents = candidate->GetMemPoolParentsConst();
1195 if (parents.size() == 0) {
1196 maximum = std::max(maximum, candidate->GetCountWithDescendants());
1197 } else {
1198 for (const CTxMemPoolEntry& i : parents) {
1199 candidates.push_back(mapTx.iterator_to(i));
1200 }
1201 }
1202 }
1203 return maximum;
1204}
1205
1206void CTxMemPool::GetTransactionAncestry(const Txid& txid, size_t& ancestors, size_t& descendants, size_t* const ancestorsize, CAmount* const ancestorfees) const {
1207 LOCK(cs);
1208 auto it = mapTx.find(txid);
1209 ancestors = descendants = 0;
1210 if (it != mapTx.end()) {
1211 ancestors = it->GetCountWithAncestors();
1212 if (ancestorsize) *ancestorsize = it->GetSizeWithAncestors();
1213 if (ancestorfees) *ancestorfees = it->GetModFeesWithAncestors();
1214 descendants = CalculateDescendantMaximum(it);
1215 }
1216}
1217
1219{
1220 LOCK(cs);
1221 return m_load_tried;
1222}
1223
1224void CTxMemPool::SetLoadTried(bool load_tried)
1225{
1226 LOCK(cs);
1227 m_load_tried = load_tried;
1228}
1229
1230std::vector<CTxMemPool::txiter> CTxMemPool::GatherClusters(const std::vector<Txid>& txids) const
1231{
1233 std::vector<txiter> clustered_txs{GetIterVec(txids)};
1234 // Use epoch: visiting an entry means we have added it to the clustered_txs vector. It does not
1235 // necessarily mean the entry has been processed.
1237 for (const auto& it : clustered_txs) {
1238 visited(it);
1239 }
1240 // i = index of where the list of entries to process starts
1241 for (size_t i{0}; i < clustered_txs.size(); ++i) {
1242 // DoS protection: if there are 500 or more entries to process, just quit.
1243 if (clustered_txs.size() > 500) return {};
1244 const txiter& tx_iter = clustered_txs.at(i);
1245 for (const auto& entries : {tx_iter->GetMemPoolParentsConst(), tx_iter->GetMemPoolChildrenConst()}) {
1246 for (const CTxMemPoolEntry& entry : entries) {
1247 const auto entry_it = mapTx.iterator_to(entry);
1248 if (!visited(entry_it)) {
1249 clustered_txs.push_back(entry_it);
1250 }
1251 }
1252 }
1253 }
1254 return clustered_txs;
1255}
1256
1257std::optional<std::string> CTxMemPool::CheckConflictTopology(const setEntries& direct_conflicts)
1258{
1259 for (const auto& direct_conflict : direct_conflicts) {
1260 // Ancestor and descendant counts are inclusive of the tx itself.
1261 const auto ancestor_count{direct_conflict->GetCountWithAncestors()};
1262 const auto descendant_count{direct_conflict->GetCountWithDescendants()};
1263 const bool has_ancestor{ancestor_count > 1};
1264 const bool has_descendant{descendant_count > 1};
1265 const auto& txid_string{direct_conflict->GetSharedTx()->GetHash().ToString()};
1266 // The only allowed configurations are:
1267 // 1 ancestor and 0 descendant
1268 // 0 ancestor and 1 descendant
1269 // 0 ancestor and 0 descendant
1270 if (ancestor_count > 2) {
1271 return strprintf("%s has %u ancestors, max 1 allowed", txid_string, ancestor_count - 1);
1272 } else if (descendant_count > 2) {
1273 return strprintf("%s has %u descendants, max 1 allowed", txid_string, descendant_count - 1);
1274 } else if (has_ancestor && has_descendant) {
1275 return strprintf("%s has both ancestor and descendant, exceeding cluster limit of 2", txid_string);
1276 }
1277 // Additionally enforce that:
1278 // If we have a child, we are its only parent.
1279 // If we have a parent, we are its only child.
1280 if (has_descendant) {
1281 const auto& our_child = direct_conflict->GetMemPoolChildrenConst().begin();
1282 if (our_child->get().GetCountWithAncestors() > 2) {
1283 return strprintf("%s is not the only parent of child %s",
1284 txid_string, our_child->get().GetSharedTx()->GetHash().ToString());
1285 }
1286 } else if (has_ancestor) {
1287 const auto& our_parent = direct_conflict->GetMemPoolParentsConst().begin();
1288 if (our_parent->get().GetCountWithDescendants() > 2) {
1289 return strprintf("%s is not the only child of parent %s",
1290 txid_string, our_parent->get().GetSharedTx()->GetHash().ToString());
1291 }
1292 }
1293 }
1294 return std::nullopt;
1295}
1296
1298{
1299 LOCK(m_pool->cs);
1300 FeeFrac replacement_feerate{0, 0};
1301 for (auto it : m_entry_vec) {
1302 replacement_feerate += {it->GetModifiedFee(), it->GetTxSize()};
1303 }
1304
1305 auto err_string{m_pool->CheckConflictTopology(m_to_remove)};
1306 if (err_string.has_value()) {
1307 // Unsupported topology for calculating a feerate diagram
1308 return util::Error{Untranslated(err_string.value())};
1309 }
1310
1311 // new diagram will have chunks that consist of each ancestor of
1312 // direct_conflicts that is at its own fee/size, along with the replacement
1313 // tx/package at its own fee/size
1314
1315 // old diagram will consist of the ancestors and descendants of each element of
1316 // all_conflicts. every such transaction will either be at its own feerate (followed
1317 // by any descendant at its own feerate), or as a single chunk at the descendant's
1318 // ancestor feerate.
1319
1320 std::vector<FeeFrac> old_chunks;
1321 // Step 1: build the old diagram.
1322
1323 // The above clusters are all trivially linearized;
1324 // they have a strict topology of 1 or two connected transactions.
1325
1326 // OLD: Compute existing chunks from all affected clusters
1327 for (auto txiter : m_to_remove) {
1328 // Does this transaction have descendants?
1329 if (txiter->GetCountWithDescendants() > 1) {
1330 // Consider this tx when we consider the descendant.
1331 continue;
1332 }
1333 // Does this transaction have ancestors?
1334 FeeFrac individual{txiter->GetModifiedFee(), txiter->GetTxSize()};
1335 if (txiter->GetCountWithAncestors() > 1) {
1336 // We'll add chunks for either the ancestor by itself and this tx
1337 // by itself, or for a combined package.
1338 FeeFrac package{txiter->GetModFeesWithAncestors(), static_cast<int32_t>(txiter->GetSizeWithAncestors())};
1339 if (individual >> package) {
1340 // The individual feerate is higher than the package, and
1341 // therefore higher than the parent's fee. Chunk these
1342 // together.
1343 old_chunks.emplace_back(package);
1344 } else {
1345 // Add two points, one for the parent and one for this child.
1346 old_chunks.emplace_back(package - individual);
1347 old_chunks.emplace_back(individual);
1348 }
1349 } else {
1350 old_chunks.emplace_back(individual);
1351 }
1352 }
1353
1354 // No topology restrictions post-chunking; sort
1355 std::sort(old_chunks.begin(), old_chunks.end(), std::greater());
1356
1357 std::vector<FeeFrac> new_chunks;
1358
1359 /* Step 2: build the NEW diagram
1360 * CON = Conflicts of proposed chunk
1361 * CNK = Proposed chunk
1362 * NEW = OLD - CON + CNK: New diagram includes all chunks in OLD, minus
1363 * the conflicts, plus the proposed chunk
1364 */
1365
1366 // OLD - CON: Add any parents of direct conflicts that are not conflicted themselves
1367 for (auto direct_conflict : m_to_remove) {
1368 // If a direct conflict has an ancestor that is not in all_conflicts,
1369 // it can be affected by the replacement of the child.
1370 if (direct_conflict->GetMemPoolParentsConst().size() > 0) {
1371 // Grab the parent.
1372 const CTxMemPoolEntry& parent = direct_conflict->GetMemPoolParentsConst().begin()->get();
1373 if (!m_to_remove.contains(m_pool->mapTx.iterator_to(parent))) {
1374 // This transaction would be left over, so add to the NEW
1375 // diagram.
1376 new_chunks.emplace_back(parent.GetModifiedFee(), parent.GetTxSize());
1377 }
1378 }
1379 }
1380 // + CNK: Add the proposed chunk itself
1381 new_chunks.emplace_back(replacement_feerate);
1382
1383 // No topology restrictions post-chunking; sort
1384 std::sort(new_chunks.begin(), new_chunks.end(), std::greater());
1385 return std::make_pair(old_chunks, new_chunks);
1386}
1387
1388CTxMemPool::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)
1389{
1390 LOCK(m_pool->cs);
1391 Assume(m_to_add.find(tx->GetHash()) == m_to_add.end());
1392 auto newit = m_to_add.emplace(tx, fee, time, entry_height, entry_sequence, spends_coinbase, sigops_cost, lp).first;
1393 CAmount delta{0};
1394 m_pool->ApplyDelta(tx->GetHash(), delta);
1395 if (delta) m_to_add.modify(newit, [&delta](CTxMemPoolEntry& e) { e.UpdateModifiedFee(delta); });
1396
1397 m_entry_vec.push_back(newit);
1398 return newit;
1399}
1400
1402{
1403 LOCK(m_pool->cs);
1404 m_pool->Apply(this);
1405 m_to_add.clear();
1406 m_to_remove.clear();
1407 m_entry_vec.clear();
1408 m_ancestors.clear();
1409}
int64_t CAmount
Amount in satoshis (Can be negative)
Definition: amount.h:12
int ret
#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:1009
void Reset()
Clear m_temp_added and m_non_base_coins.
Definition: txmempool.cpp:1039
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:1007
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:1032
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
const Wtxid & GetWitnessHash() const LIFETIMEBOUND
Definition: transaction.h:344
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:1401
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:1388
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:1297
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:648
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:888
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:999
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:976
void ClearPrioritisation(const Txid &hash) EXCLUSIVE_LOCKS_REQUIRED(cs)
Definition: txmempool.cpp:934
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:962
bool GetLoadTried() const
Definition: txmempool.cpp:1218
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:1132
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:1140
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:879
size_t DynamicMemoryUsage() const
Definition: txmempool.cpp:1045
const Options m_opts
Definition: txmempool.h:421
std::vector< TxMempoolInfo > infoAll() const
Definition: txmempool.cpp:858
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:1097
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:1051
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:1068
bool CompareDepthAndScore(const Wtxid &hasha, const Wtxid &hashb) const
Definition: txmempool.cpp:796
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:627
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:986
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:832
void ApplyDelta(const Txid &hash, CAmount &nFeeDelta) const EXCLUSIVE_LOCKS_REQUIRED(cs)
Definition: txmempool.cpp:924
void RemoveStaged(setEntries &stage, bool updateDescendants, MemPoolRemovalReason reason) EXCLUSIVE_LOCKS_REQUIRED(cs)
Remove a set of transactions from the mempool.
Definition: txmempool.cpp:1060
void removeForBlock(const std::vector< CTransactionRef > &vtx, unsigned int nBlockHeight) EXCLUSIVE_LOCKS_REQUIRED(cs)
Definition: txmempool.cpp:665
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:940
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:1230
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:1086
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:1206
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:956
void CalculateDescendants(txiter it, setEntries &setDescendants) const EXCLUSIVE_LOCKS_REQUIRED(cs)
Populate setDescendants with all in-mempool descendants of hash.
Definition: txmempool.cpp:572
std::optional< std::string > CheckConflictTopology(const setEntries &direct_conflicts)
Definition: txmempool.cpp:1257
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:1224
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:846
uint64_t CalculateDescendantMaximum(txiter entry) const EXCLUSIVE_LOCKS_REQUIRED(cs)
Definition: txmempool.cpp:1184
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:872
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:56
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())