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