Line data Source code
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>
13 : #include <consensus/validation.h>
14 : #include <logging.h>
15 : #include <policy/fees.h>
16 : #include <policy/policy.h>
17 2 : #include <policy/settings.h>
18 2 : #include <reverse_iterator.h>
19 : #include <util/check.h>
20 : #include <util/moneystr.h>
21 : #include <util/overflow.h>
22 : #include <util/result.h>
23 : #include <util/time.h>
24 : #include <util/trace.h>
25 : #include <util/translation.h>
26 : #include <validationinterface.h>
27 :
28 : #include <cmath>
29 : #include <numeric>
30 : #include <optional>
31 : #include <string_view>
32 : #include <utility>
33 :
34 0 : bool TestLockPointValidity(CChain& active_chain, const LockPoints& lp)
35 : {
36 0 : AssertLockHeld(cs_main);
37 : // If there are relative lock times then the maxInputBlock will be set
38 : // If there are no relative lock times, the LockPoints don't depend on the chain
39 0 : if (lp.maxInputBlock) {
40 : // Check whether active_chain is an extension of the block at which the LockPoints
41 : // calculation was valid. If not LockPoints are no longer valid
42 0 : if (!active_chain.Contains(lp.maxInputBlock)) {
43 0 : return false;
44 : }
45 0 : }
46 :
47 : // LockPoints still valid
48 0 : return true;
49 0 : }
50 :
51 0 : void CTxMemPool::UpdateForDescendants(txiter updateIt, cacheMap& cachedDescendants,
52 : const std::set<uint256>& setExclude, std::set<uint256>& descendants_to_remove)
53 : {
54 0 : CTxMemPoolEntry::Children stageEntries, descendants;
55 0 : stageEntries = updateIt->GetMemPoolChildrenConst();
56 :
57 0 : while (!stageEntries.empty()) {
58 0 : const CTxMemPoolEntry& descendant = *stageEntries.begin();
59 0 : descendants.insert(descendant);
60 0 : stageEntries.erase(descendant);
61 0 : const CTxMemPoolEntry::Children& children = descendant.GetMemPoolChildrenConst();
62 0 : for (const CTxMemPoolEntry& childEntry : children) {
63 0 : cacheMap::iterator cacheIt = cachedDescendants.find(mapTx.iterator_to(childEntry));
64 0 : if (cacheIt != cachedDescendants.end()) {
65 : // We've already calculated this one, just add the entries for this set
66 : // but don't traverse again.
67 0 : for (txiter cacheEntry : cacheIt->second) {
68 0 : descendants.insert(*cacheEntry);
69 : }
70 0 : } else if (!descendants.count(childEntry)) {
71 : // Schedule for later processing
72 0 : stageEntries.insert(childEntry);
73 0 : }
74 2 : }
75 : }
76 : // descendants now contains all in-mempool descendants of updateIt.
77 : // Update and add to cached descendant map
78 0 : int32_t modifySize = 0;
79 0 : CAmount modifyFee = 0;
80 0 : int64_t modifyCount = 0;
81 0 : for (const CTxMemPoolEntry& descendant : descendants) {
82 0 : if (!setExclude.count(descendant.GetTx().GetHash())) {
83 0 : modifySize += descendant.GetTxSize();
84 0 : modifyFee += descendant.GetModifiedFee();
85 0 : modifyCount++;
86 0 : cachedDescendants[updateIt].insert(mapTx.iterator_to(descendant));
87 : // Update ancestor state for each descendant
88 0 : mapTx.modify(mapTx.iterator_to(descendant), [=](CTxMemPoolEntry& e) {
89 0 : e.UpdateAncestorState(updateIt->GetTxSize(), updateIt->GetModifiedFee(), 1, updateIt->GetSigOpCost());
90 0 : });
91 : // Don't directly remove the transaction here -- doing so would
92 : // invalidate iterators in cachedDescendants. Mark it for removal
93 : // by inserting into descendants_to_remove.
94 0 : if (descendant.GetCountWithAncestors() > uint64_t(m_limits.ancestor_count) || descendant.GetSizeWithAncestors() > m_limits.ancestor_size_vbytes) {
95 0 : descendants_to_remove.insert(descendant.GetTx().GetHash());
96 0 : }
97 0 : }
98 : }
99 0 : mapTx.modify(updateIt, [=](CTxMemPoolEntry& e) { e.UpdateDescendantState(modifySize, modifyFee, modifyCount); });
100 0 : }
101 :
102 0 : void CTxMemPool::UpdateTransactionsFromBlock(const std::vector<uint256>& vHashesToUpdate)
103 : {
104 0 : AssertLockHeld(cs);
105 : // For each entry in vHashesToUpdate, store the set of in-mempool, but not
106 : // in-vHashesToUpdate transactions, so that we don't have to recalculate
107 : // descendants when we come across a previously seen entry.
108 0 : cacheMap mapMemPoolDescendantsToUpdate;
109 :
110 : // Use a set for lookups into vHashesToUpdate (these entries are already
111 : // accounted for in the state of their ancestors)
112 0 : std::set<uint256> setAlreadyIncluded(vHashesToUpdate.begin(), vHashesToUpdate.end());
113 :
114 0 : std::set<uint256> descendants_to_remove;
115 :
116 : // Iterate in reverse, so that whenever we are looking at a transaction
117 : // we are sure that all in-mempool descendants have already been processed.
118 : // This maximizes the benefit of the descendant cache and guarantees that
119 : // CTxMemPoolEntry::m_children will be updated, an assumption made in
120 : // UpdateForDescendants.
121 0 : for (const uint256 &hash : reverse_iterate(vHashesToUpdate)) {
122 : // calculate children from mapNextTx
123 0 : txiter it = mapTx.find(hash);
124 0 : if (it == mapTx.end()) {
125 0 : continue;
126 : }
127 0 : auto iter = mapNextTx.lower_bound(COutPoint(hash, 0));
128 : // First calculate the children, and update CTxMemPoolEntry::m_children to
129 : // include them, and update their CTxMemPoolEntry::m_parents to include this tx.
130 : // we cache the in-mempool children to avoid duplicate updates
131 : {
132 0 : WITH_FRESH_EPOCH(m_epoch);
133 0 : for (; iter != mapNextTx.end() && iter->first->hash == hash; ++iter) {
134 0 : const uint256 &childHash = iter->second->GetHash();
135 0 : txiter childIter = mapTx.find(childHash);
136 0 : assert(childIter != mapTx.end());
137 : // We can skip updating entries we've encountered before or that
138 : // are in the block (which are already accounted for).
139 0 : if (!visited(childIter) && !setAlreadyIncluded.count(childHash)) {
140 0 : UpdateChild(it, childIter, true);
141 0 : UpdateParent(childIter, it, true);
142 0 : }
143 0 : }
144 0 : } // release epoch guard for UpdateForDescendants
145 0 : UpdateForDescendants(it, mapMemPoolDescendantsToUpdate, setAlreadyIncluded, descendants_to_remove);
146 : }
147 :
148 0 : for (const auto& txid : descendants_to_remove) {
149 : // This txid may have been removed already in a prior call to removeRecursive.
150 : // Therefore we ensure it is not yet removed already.
151 0 : if (const std::optional<txiter> txiter = GetIter(txid)) {
152 0 : removeRecursive((*txiter)->GetTx(), MemPoolRemovalReason::SIZELIMIT);
153 0 : }
154 : }
155 0 : }
156 :
157 9600 : util::Result<CTxMemPool::setEntries> CTxMemPool::CalculateAncestorsAndCheckLimits(
158 : int64_t entry_size,
159 : size_t entry_count,
160 : CTxMemPoolEntry::Parents& staged_ancestors,
161 : const Limits& limits) const
162 : {
163 9600 : int64_t totalSizeWithAncestors = entry_size;
164 9600 : setEntries ancestors;
165 :
166 10910 : while (!staged_ancestors.empty()) {
167 2022 : const CTxMemPoolEntry& stage = staged_ancestors.begin()->get();
168 2022 : txiter stageit = mapTx.iterator_to(stage);
169 :
170 2022 : ancestors.insert(stageit);
171 2022 : staged_ancestors.erase(stage);
172 2022 : totalSizeWithAncestors += stageit->GetTxSize();
173 :
174 2022 : if (stageit->GetSizeWithDescendants() + entry_size > limits.descendant_size_vbytes) {
175 132 : return util::Error{Untranslated(strprintf("exceeds descendant size limit for tx %s [limit: %u]", stageit->GetTx().GetHash().ToString(), limits.descendant_size_vbytes))};
176 1890 : } else if (stageit->GetCountWithDescendants() + entry_count > static_cast<uint64_t>(limits.descendant_count)) {
177 447 : return util::Error{Untranslated(strprintf("too many descendants for tx %s [limit: %u]", stageit->GetTx().GetHash().ToString(), limits.descendant_count))};
178 1443 : } else if (totalSizeWithAncestors > limits.ancestor_size_vbytes) {
179 127 : return util::Error{Untranslated(strprintf("exceeds ancestor size limit [limit: %u]", limits.ancestor_size_vbytes))};
180 : }
181 :
182 1316 : const CTxMemPoolEntry::Parents& parents = stageit->GetMemPoolParentsConst();
183 1358 : for (const CTxMemPoolEntry& parent : parents) {
184 48 : txiter parent_it = mapTx.iterator_to(parent);
185 :
186 : // If this is a new ancestor, add it.
187 48 : if (ancestors.count(parent_it) == 0) {
188 48 : staged_ancestors.insert(parent);
189 48 : }
190 48 : if (staged_ancestors.size() + ancestors.size() + entry_count > static_cast<uint64_t>(limits.ancestor_count)) {
191 6 : return util::Error{Untranslated(strprintf("too many unconfirmed ancestors [limit: %u]", limits.ancestor_count))};
192 : }
193 : }
194 : }
195 :
196 8888 : return ancestors;
197 9600 : }
198 :
199 16 : bool CTxMemPool::CheckPackageLimits(const Package& package,
200 : const int64_t total_vsize,
201 : std::string &errString) const
202 : {
203 16 : size_t pack_count = package.size();
204 :
205 : // Package itself is busting mempool limits; should be rejected even if no staged_ancestors exist
206 16 : if (pack_count > static_cast<uint64_t>(m_limits.ancestor_count)) {
207 3 : errString = strprintf("package count %u exceeds ancestor count limit [limit: %u]", pack_count, m_limits.ancestor_count);
208 3 : return false;
209 13 : } else if (pack_count > static_cast<uint64_t>(m_limits.descendant_count)) {
210 8 : errString = strprintf("package count %u exceeds descendant count limit [limit: %u]", pack_count, m_limits.descendant_count);
211 8 : return false;
212 5 : } else if (total_vsize > m_limits.ancestor_size_vbytes) {
213 0 : errString = strprintf("package size %u exceeds ancestor size limit [limit: %u]", total_vsize, m_limits.ancestor_size_vbytes);
214 0 : return false;
215 5 : } else if (total_vsize > m_limits.descendant_size_vbytes) {
216 1 : errString = strprintf("package size %u exceeds descendant size limit [limit: %u]", total_vsize, m_limits.descendant_size_vbytes);
217 1 : return false;
218 : }
219 :
220 4 : CTxMemPoolEntry::Parents staged_ancestors;
221 12 : for (const auto& tx : package) {
222 24 : for (const auto& input : tx->vin) {
223 16 : std::optional<txiter> piter = GetIter(input.prevout.hash);
224 16 : if (piter) {
225 0 : staged_ancestors.insert(**piter);
226 0 : if (staged_ancestors.size() + package.size() > static_cast<uint64_t>(m_limits.ancestor_count)) {
227 0 : errString = strprintf("too many unconfirmed parents [limit: %u]", m_limits.ancestor_count);
228 0 : return false;
229 : }
230 0 : }
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 8 : const auto ancestors{CalculateAncestorsAndCheckLimits(total_vsize, package.size(),
237 4 : staged_ancestors, m_limits)};
238 : // It's possible to overestimate the ancestor/descendant totals.
239 4 : if (!ancestors.has_value()) errString = "possibly " + util::ErrorString(ancestors).original;
240 4 : return ancestors.has_value();
241 16 : }
242 :
243 10084 : util::Result<CTxMemPool::setEntries> CTxMemPool::CalculateMemPoolAncestors(
244 : const CTxMemPoolEntry &entry,
245 : const Limits& limits,
246 : bool fSearchForParents /* = true */) const
247 : {
248 10084 : CTxMemPoolEntry::Parents staged_ancestors;
249 10084 : const CTransaction &tx = entry.GetTx();
250 :
251 10084 : 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 20097 : for (unsigned int i = 0; i < tx.vin.size(); i++) {
256 13552 : std::optional<txiter> piter = GetIter(tx.vin[i].prevout.hash);
257 13552 : if (piter) {
258 3956 : staged_ancestors.insert(**piter);
259 3956 : if (staged_ancestors.size() + 1 > static_cast<uint64_t>(limits.ancestor_count)) {
260 488 : return util::Error{Untranslated(strprintf("too many unconfirmed parents [limit: %u]", limits.ancestor_count))};
261 : }
262 3468 : }
263 13064 : }
264 6545 : } 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 3051 : txiter it = mapTx.iterator_to(entry);
268 3051 : staged_ancestors = it->GetMemPoolParentsConst();
269 : }
270 :
271 9596 : return CalculateAncestorsAndCheckLimits(entry.GetTxSize(), /*entry_count=*/1, staged_ancestors,
272 9596 : limits);
273 10084 : }
274 :
275 5056 : CTxMemPool::setEntries CTxMemPool::AssumeCalculateMemPoolAncestors(
276 : std::string_view calling_fn_name,
277 : const CTxMemPoolEntry &entry,
278 : const Limits& limits,
279 : bool fSearchForParents /* = true */) const
280 : {
281 5056 : auto result{CalculateMemPoolAncestors(entry, limits, fSearchForParents)};
282 5056 : if (!Assume(result)) {
283 0 : 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 0 : }
286 5056 : return std::move(result).value_or(CTxMemPool::setEntries{});
287 5056 : }
288 :
289 4319 : void CTxMemPool::UpdateAncestorsOf(bool add, txiter it, setEntries &setAncestors)
290 : {
291 4319 : const CTxMemPoolEntry::Parents& parents = it->GetMemPoolParentsConst();
292 : // add or remove this tx as a child of each parent
293 5011 : for (const CTxMemPoolEntry& parent : parents) {
294 692 : UpdateChild(mapTx.iterator_to(parent), it, add);
295 : }
296 4319 : const int32_t updateCount = (add ? 1 : -1);
297 4319 : const int32_t updateSize{updateCount * it->GetTxSize()};
298 4319 : const CAmount updateFee = updateCount * it->GetModifiedFee();
299 5037 : for (txiter ancestorIt : setAncestors) {
300 1436 : mapTx.modify(ancestorIt, [=](CTxMemPoolEntry& e) { e.UpdateDescendantState(updateSize, updateFee, updateCount); });
301 : }
302 4319 : }
303 :
304 2211 : void CTxMemPool::UpdateEntryForAncestors(txiter it, const setEntries &setAncestors)
305 4860 : {
306 2211 : int64_t updateCount = setAncestors.size();
307 2211 : int64_t updateSize = 0;
308 7071 : CAmount updateFee = 0;
309 7071 : int64_t updateSigOpsCost = 0;
310 7432 : for (txiter ancestorIt : setAncestors) {
311 361 : updateSize += ancestorIt->GetTxSize();
312 5221 : updateFee += ancestorIt->GetModifiedFee();
313 5221 : updateSigOpsCost += ancestorIt->GetSigOpCost();
314 4860 : }
315 9282 : mapTx.modify(it, [=](CTxMemPoolEntry& e){ e.UpdateAncestorState(updateSize, updateFee, updateCount, updateSigOpsCost); });
316 2211 : }
317 :
318 2108 : void CTxMemPool::UpdateChildrenForRemoval(txiter it)
319 : {
320 6968 : const CTxMemPoolEntry::Children& children = it->GetMemPoolChildrenConst();
321 2108 : for (const CTxMemPoolEntry& updateIt : children) {
322 0 : UpdateParent(mapTx.iterator_to(updateIt), it, false);
323 : }
324 6968 : }
325 :
326 7301 : void 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 7301 : 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 0 : for (txiter removeIt : entriesToRemove) {
338 0 : setEntries setDescendants;
339 0 : CalculateDescendants(removeIt, setDescendants);
340 0 : setDescendants.erase(removeIt); // don't update state for self
341 0 : int32_t modifySize = -removeIt->GetTxSize();
342 0 : CAmount modifyFee = -removeIt->GetModifiedFee();
343 0 : int modifySigOps = -removeIt->GetSigOpCost();
344 0 : for (txiter dit : setDescendants) {
345 0 : mapTx.modify(dit, [=](CTxMemPoolEntry& e){ e.UpdateAncestorState(modifySize, modifyFee, -1, modifySigOps); });
346 : }
347 0 : }
348 0 : }
349 9409 : for (txiter removeIt : entriesToRemove) {
350 2108 : 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 : // addUnchecked(), 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 2108 : 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 2108 : UpdateAncestorsOf(false, removeIt, ancestors);
374 2108 : }
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 9409 : for (txiter removeIt : entriesToRemove) {
379 2108 : UpdateChildrenForRemoval(removeIt);
380 : }
381 7301 : }
382 :
383 857 : void CTxMemPoolEntry::UpdateDescendantState(int32_t modifySize, CAmount modifyFee, int64_t modifyCount)
384 : {
385 857 : nSizeWithDescendants += modifySize;
386 857 : assert(nSizeWithDescendants > 0);
387 857 : nModFeesWithDescendants = SaturatingAdd(nModFeesWithDescendants, modifyFee);
388 857 : m_count_with_descendants += modifyCount;
389 857 : assert(m_count_with_descendants > 0);
390 857 : }
391 :
392 2211 : void CTxMemPoolEntry::UpdateAncestorState(int32_t modifySize, CAmount modifyFee, int64_t modifyCount, int64_t modifySigOps)
393 : {
394 2211 : nSizeWithAncestors += modifySize;
395 2211 : assert(nSizeWithAncestors > 0);
396 2211 : nModFeesWithAncestors = SaturatingAdd(nModFeesWithAncestors, modifyFee);
397 2211 : m_count_with_ancestors += modifyCount;
398 2211 : assert(m_count_with_ancestors > 0);
399 2211 : nSigOpCostWithAncestors += modifySigOps;
400 2211 : assert(int(nSigOpCostWithAncestors) >= 0);
401 2211 : }
402 :
403 9720 : CTxMemPool::CTxMemPool(const Options& opts)
404 4860 : : m_check_ratio{opts.check_ratio},
405 4860 : minerPolicyEstimator{opts.estimator},
406 4860 : m_max_size_bytes{opts.max_size_bytes},
407 4860 : m_expiry{opts.expiry},
408 4860 : m_incremental_relay_feerate{opts.incremental_relay_feerate},
409 4860 : m_min_relay_feerate{opts.min_relay_feerate},
410 4860 : m_dust_relay_feerate{opts.dust_relay_feerate},
411 4860 : m_permit_bare_multisig{opts.permit_bare_multisig},
412 4860 : m_max_datacarrier_bytes{opts.max_datacarrier_bytes},
413 4860 : m_require_standard{opts.require_standard},
414 4860 : m_full_rbf{opts.full_rbf},
415 4860 : m_limits{opts.limits}
416 : {
417 4860 : }
418 :
419 0 : bool CTxMemPool::isSpent(const COutPoint& outpoint) const
420 : {
421 0 : LOCK(cs);
422 0 : return mapNextTx.count(outpoint);
423 0 : }
424 :
425 0 : unsigned int CTxMemPool::GetTransactionsUpdated() const
426 : {
427 0 : return nTransactionsUpdated;
428 : }
429 :
430 201 : void CTxMemPool::AddTransactionsUpdated(unsigned int n)
431 : {
432 201 : nTransactionsUpdated += n;
433 201 : }
434 :
435 2211 : void CTxMemPool::addUnchecked(const CTxMemPoolEntry &entry, setEntries &setAncestors, bool validFeeEstimate)
436 : {
437 : // Add to memory pool without checking anything.
438 : // Used by AcceptToMemoryPool(), which DOES do
439 : // all the appropriate checks.
440 2211 : indexed_transaction_set::iterator newit = mapTx.insert(entry).first;
441 :
442 : // Update transaction for any feeDelta created by PrioritiseTransaction
443 2211 : CAmount delta{0};
444 2211 : ApplyDelta(entry.GetTx().GetHash(), delta);
445 : // The following call to UpdateModifiedFee assumes no previous fee modifications
446 2211 : Assume(entry.GetFee() == entry.GetModifiedFee());
447 2211 : if (delta) {
448 654 : mapTx.modify(newit, [&delta](CTxMemPoolEntry& e) { e.UpdateModifiedFee(delta); });
449 327 : }
450 :
451 : // Update cachedInnerUsage to include contained transaction's usage.
452 : // (When we update the entry for in-mempool parents, memory usage will be
453 : // further updated.)
454 2211 : cachedInnerUsage += entry.DynamicMemoryUsage();
455 :
456 2211 : const CTransaction& tx = newit->GetTx();
457 2211 : std::set<uint256> setParentTransactions;
458 7016 : for (unsigned int i = 0; i < tx.vin.size(); i++) {
459 4805 : mapNextTx.insert(std::make_pair(&tx.vin[i].prevout, &tx));
460 4805 : setParentTransactions.insert(tx.vin[i].prevout.hash);
461 4805 : }
462 : // Don't bother worrying about child transactions of this one.
463 : // Normal case of a new transaction arriving is that there can't be any
464 : // children, because such children would be orphans.
465 : // An exception to that is if a transaction enters that used to be in a block.
466 : // In that case, our disconnect block logic will call UpdateTransactionsFromBlock
467 : // to clean up the mess we're leaving here.
468 :
469 : // Update ancestors with information about this tx
470 2559 : for (const auto& pit : GetIterSet(setParentTransactions)) {
471 348 : UpdateParent(newit, pit, true);
472 : }
473 2211 : UpdateAncestorsOf(true, newit, setAncestors);
474 2211 : UpdateEntryForAncestors(newit, setAncestors);
475 :
476 2211 : nTransactionsUpdated++;
477 2211 : totalTxSize += entry.GetTxSize();
478 2211 : m_total_fee += entry.GetFee();
479 2211 : if (minerPolicyEstimator) {
480 0 : minerPolicyEstimator->processTransaction(entry, validFeeEstimate);
481 0 : }
482 :
483 2211 : vTxHashes.emplace_back(tx.GetWitnessHash(), newit);
484 2211 : newit->vTxHashesIdx = vTxHashes.size() - 1;
485 :
486 : TRACE3(mempool, added,
487 : entry.GetTx().GetHash().data(),
488 : entry.GetTxSize(),
489 : entry.GetFee()
490 : );
491 2211 : }
492 :
493 2108 : void CTxMemPool::removeUnchecked(txiter it, MemPoolRemovalReason reason)
494 : {
495 : // We increment mempool sequence value no matter removal reason
496 : // even if not directly reported below.
497 2108 : uint64_t mempool_sequence = GetAndIncrementSequence();
498 :
499 2108 : if (reason != MemPoolRemovalReason::BLOCK) {
500 : // Notify clients that a transaction has been removed from the mempool
501 : // for any reason except being included in a block. Clients interested
502 : // in transactions included in blocks can subscribe to the BlockConnected
503 : // notification.
504 309 : GetMainSignals().TransactionRemovedFromMempool(it->GetSharedTx(), reason, mempool_sequence);
505 309 : }
506 : TRACE5(mempool, removed,
507 : it->GetTx().GetHash().data(),
508 : RemovalReasonToString(reason).c_str(),
509 : it->GetTxSize(),
510 : it->GetFee(),
511 : std::chrono::duration_cast<std::chrono::duration<std::uint64_t>>(it->GetTime()).count()
512 : );
513 :
514 2108 : const uint256 hash = it->GetTx().GetHash();
515 6741 : for (const CTxIn& txin : it->GetTx().vin)
516 4633 : mapNextTx.erase(txin.prevout);
517 :
518 2108 : RemoveUnbroadcastTx(hash, true /* add logging because unchecked */ );
519 :
520 2108 : if (vTxHashes.size() > 1) {
521 397 : vTxHashes[it->vTxHashesIdx] = std::move(vTxHashes.back());
522 397 : vTxHashes[it->vTxHashesIdx].second->vTxHashesIdx = it->vTxHashesIdx;
523 397 : vTxHashes.pop_back();
524 397 : if (vTxHashes.size() * 2 < vTxHashes.capacity())
525 28 : vTxHashes.shrink_to_fit();
526 397 : } else
527 1711 : vTxHashes.clear();
528 :
529 2108 : totalTxSize -= it->GetTxSize();
530 2108 : m_total_fee -= it->GetFee();
531 2108 : cachedInnerUsage -= it->DynamicMemoryUsage();
532 2108 : cachedInnerUsage -= memusage::DynamicUsage(it->GetMemPoolParentsConst()) + memusage::DynamicUsage(it->GetMemPoolChildrenConst());
533 2108 : mapTx.erase(it);
534 2108 : nTransactionsUpdated++;
535 2108 : if (minerPolicyEstimator) {minerPolicyEstimator->removeTx(hash, false);}
536 2108 : }
537 :
538 : // Calculates descendants of entry that are not already in setDescendants, and adds to
539 : // setDescendants. Assumes entryit is already a tx in the mempool and CTxMemPoolEntry::m_children
540 : // is correct for tx and all descendants.
541 : // Also assumes that if an entry is in setDescendants already, then all
542 : // in-mempool descendants of it are already in setDescendants as well, so that we
543 : // can save time by not iterating over those entries.
544 2817 : void CTxMemPool::CalculateDescendants(txiter entryit, setEntries& setDescendants) const
545 : {
546 2817 : setEntries stage;
547 2817 : if (setDescendants.count(entryit) == 0) {
548 2806 : stage.insert(entryit);
549 2806 : }
550 : // Traverse down the children of entry, only adding children that are not
551 : // accounted for in setDescendants already (because those children have either
552 : // already been walked, or will be walked in this iteration).
553 5927 : while (!stage.empty()) {
554 3110 : txiter it = *stage.begin();
555 3110 : setDescendants.insert(it);
556 3110 : stage.erase(it);
557 :
558 3110 : const CTxMemPoolEntry::Children& children = it->GetMemPoolChildrenConst();
559 3438 : for (const CTxMemPoolEntry& child : children) {
560 328 : txiter childiter = mapTx.iterator_to(child);
561 328 : if (!setDescendants.count(childiter)) {
562 304 : stage.insert(childiter);
563 304 : }
564 : }
565 : }
566 2817 : }
567 :
568 1568 : void CTxMemPool::removeRecursive(const CTransaction &origTx, MemPoolRemovalReason reason)
569 : {
570 : // Remove transaction from memory pool
571 1568 : AssertLockHeld(cs);
572 1568 : setEntries txToRemove;
573 1568 : txiter origit = mapTx.find(origTx.GetHash());
574 1568 : if (origit != mapTx.end()) {
575 1568 : txToRemove.insert(origit);
576 1568 : } else {
577 : // When recursively removing but origTx isn't in the mempool
578 : // be sure to remove any children that are in the pool. This can
579 : // happen during chain re-orgs if origTx isn't re-accepted into
580 : // the mempool for any reason.
581 0 : for (unsigned int i = 0; i < origTx.vout.size(); i++) {
582 0 : auto it = mapNextTx.find(COutPoint(origTx.GetHash(), i));
583 0 : if (it == mapNextTx.end())
584 0 : continue;
585 0 : txiter nextit = mapTx.find(it->second->GetHash());
586 0 : assert(nextit != mapTx.end());
587 0 : txToRemove.insert(nextit);
588 0 : }
589 : }
590 1568 : setEntries setAllRemoves;
591 3136 : for (txiter it : txToRemove) {
592 1568 : CalculateDescendants(it, setAllRemoves);
593 : }
594 :
595 1568 : RemoveStaged(setAllRemoves, false, reason);
596 1568 : }
597 :
598 0 : void CTxMemPool::removeForReorg(CChain& chain, std::function<bool(txiter)> check_final_and_mature)
599 : {
600 : // Remove transactions spending a coinbase which are now immature and no-longer-final transactions
601 0 : AssertLockHeld(cs);
602 0 : AssertLockHeld(::cs_main);
603 :
604 0 : setEntries txToRemove;
605 0 : for (indexed_transaction_set::const_iterator it = mapTx.begin(); it != mapTx.end(); it++) {
606 0 : if (check_final_and_mature(it)) txToRemove.insert(it);
607 0 : }
608 0 : setEntries setAllRemoves;
609 0 : for (txiter it : txToRemove) {
610 0 : CalculateDescendants(it, setAllRemoves);
611 : }
612 0 : RemoveStaged(setAllRemoves, false, MemPoolRemovalReason::REORG);
613 0 : for (indexed_transaction_set::const_iterator it = mapTx.begin(); it != mapTx.end(); it++) {
614 0 : assert(TestLockPointValidity(chain, it->GetLockPoints()));
615 0 : }
616 0 : }
617 :
618 201 : void CTxMemPool::removeConflicts(const CTransaction &tx)
619 : {
620 : // Remove transactions which depend on inputs of tx, recursively
621 201 : AssertLockHeld(cs);
622 402 : for (const CTxIn &txin : tx.vin) {
623 201 : auto it = mapNextTx.find(txin.prevout);
624 201 : if (it != mapNextTx.end()) {
625 0 : const CTransaction &txConflict = *it->second;
626 0 : if (txConflict != tx)
627 : {
628 0 : ClearPrioritisation(txConflict.GetHash());
629 0 : removeRecursive(txConflict, MemPoolRemovalReason::CONFLICT);
630 0 : }
631 0 : }
632 : }
633 201 : }
634 :
635 : /**
636 : * Called when a block is connected. Removes from mempool and updates the miner fee estimator.
637 : */
638 201 : void CTxMemPool::removeForBlock(const std::vector<CTransactionRef>& vtx, unsigned int nBlockHeight)
639 : {
640 201 : AssertLockHeld(cs);
641 201 : std::vector<const CTxMemPoolEntry*> entries;
642 402 : for (const auto& tx : vtx)
643 : {
644 201 : uint256 hash = tx->GetHash();
645 :
646 201 : indexed_transaction_set::iterator i = mapTx.find(hash);
647 201 : if (i != mapTx.end())
648 0 : entries.push_back(&*i);
649 : }
650 : // Before the txs in the new block have been removed from the mempool, update policy estimates
651 201 : if (minerPolicyEstimator) {minerPolicyEstimator->processBlock(nBlockHeight, entries);}
652 402 : for (const auto& tx : vtx)
653 : {
654 201 : txiter it = mapTx.find(tx->GetHash());
655 201 : if (it != mapTx.end()) {
656 0 : setEntries stage;
657 0 : stage.insert(it);
658 0 : RemoveStaged(stage, true, MemPoolRemovalReason::BLOCK);
659 0 : }
660 201 : removeConflicts(*tx);
661 201 : ClearPrioritisation(tx->GetHash());
662 : }
663 201 : lastRollingFeeUpdate = GetTime();
664 201 : blockSinceLastRollingFeeBump = true;
665 201 : }
666 :
667 6628 : void CTxMemPool::check(const CCoinsViewCache& active_coins_tip, int64_t spendheight) const
668 : {
669 6628 : if (m_check_ratio == 0) return;
670 :
671 6628 : if (GetRand(m_check_ratio) >= 1) return;
672 :
673 6628 : AssertLockHeld(::cs_main);
674 6628 : LOCK(cs);
675 6628 : LogPrint(BCLog::MEMPOOL, "Checking mempool with %u transactions and %u inputs\n", (unsigned int)mapTx.size(), (unsigned int)mapNextTx.size());
676 :
677 6628 : uint64_t checkTotal = 0;
678 6628 : CAmount check_total_fee{0};
679 6628 : uint64_t innerUsage = 0;
680 6628 : uint64_t prev_ancestor_count{0};
681 :
682 6628 : CCoinsViewCache mempoolDuplicate(const_cast<CCoinsViewCache*>(&active_coins_tip));
683 :
684 8633 : for (const auto& it : GetSortedDepthAndScore()) {
685 2005 : checkTotal += it->GetTxSize();
686 2005 : check_total_fee += it->GetFee();
687 2005 : innerUsage += it->DynamicMemoryUsage();
688 2005 : const CTransaction& tx = it->GetTx();
689 2005 : innerUsage += memusage::DynamicUsage(it->GetMemPoolParentsConst()) + memusage::DynamicUsage(it->GetMemPoolChildrenConst());
690 2005 : CTxMemPoolEntry::Parents setParentCheck;
691 6314 : for (const CTxIn &txin : tx.vin) {
692 : // Check that every mempool transaction's inputs refer to available coins, or other mempool tx's.
693 4309 : indexed_transaction_set::const_iterator it2 = mapTx.find(txin.prevout.hash);
694 4309 : if (it2 != mapTx.end()) {
695 643 : const CTransaction& tx2 = it2->GetTx();
696 643 : assert(tx2.vout.size() > txin.prevout.n && !tx2.vout[txin.prevout.n].IsNull());
697 643 : setParentCheck.insert(*it2);
698 643 : }
699 : // We are iterating through the mempool entries sorted in order by ancestor count.
700 : // All parents must have been checked before their children and their coins added to
701 : // the mempoolDuplicate coins cache.
702 4309 : assert(mempoolDuplicate.HaveCoin(txin.prevout));
703 : // Check whether its inputs are marked in mapNextTx.
704 4309 : auto it3 = mapNextTx.find(txin.prevout);
705 4309 : assert(it3 != mapNextTx.end());
706 4309 : assert(it3->first == &txin.prevout);
707 4309 : assert(it3->second == &tx);
708 : }
709 546 : auto comp = [](const CTxMemPoolEntry& a, const CTxMemPoolEntry& b) -> bool {
710 546 : return a.GetTx().GetHash() == b.GetTx().GetHash();
711 : };
712 2005 : assert(setParentCheck.size() == it->GetMemPoolParentsConst().size());
713 2005 : assert(std::equal(setParentCheck.begin(), setParentCheck.end(), it->GetMemPoolParentsConst().begin(), comp));
714 : // Verify ancestor state is correct.
715 2005 : auto ancestors{AssumeCalculateMemPoolAncestors(__func__, *it, Limits::NoLimits())};
716 2005 : uint64_t nCountCheck = ancestors.size() + 1;
717 2005 : int32_t nSizeCheck = it->GetTxSize();
718 2005 : CAmount nFeesCheck = it->GetModifiedFee();
719 2005 : int64_t nSigOpCheck = it->GetSigOpCost();
720 :
721 2290 : for (txiter ancestorIt : ancestors) {
722 285 : nSizeCheck += ancestorIt->GetTxSize();
723 285 : nFeesCheck += ancestorIt->GetModifiedFee();
724 285 : nSigOpCheck += ancestorIt->GetSigOpCost();
725 : }
726 :
727 2005 : assert(it->GetCountWithAncestors() == nCountCheck);
728 2005 : assert(it->GetSizeWithAncestors() == nSizeCheck);
729 2005 : assert(it->GetSigOpCostWithAncestors() == nSigOpCheck);
730 2005 : assert(it->GetModFeesWithAncestors() == nFeesCheck);
731 : // Sanity check: we are walking in ascending ancestor count order.
732 2005 : assert(prev_ancestor_count <= it->GetCountWithAncestors());
733 2005 : prev_ancestor_count = it->GetCountWithAncestors();
734 :
735 : // Check children against mapNextTx
736 2005 : CTxMemPoolEntry::Children setChildrenCheck;
737 2005 : auto iter = mapNextTx.lower_bound(COutPoint(it->GetTx().GetHash(), 0));
738 2005 : int32_t child_sizes{0};
739 4545 : for (; iter != mapNextTx.end() && iter->first->hash == it->GetTx().GetHash(); ++iter) {
740 643 : txiter childit = mapTx.find(iter->second->GetHash());
741 643 : assert(childit != mapTx.end()); // mapNextTx points to in-mempool transactions
742 643 : if (setChildrenCheck.insert(*childit).second) {
743 273 : child_sizes += childit->GetTxSize();
744 273 : }
745 643 : }
746 2005 : assert(setChildrenCheck.size() == it->GetMemPoolChildrenConst().size());
747 2005 : assert(std::equal(setChildrenCheck.begin(), setChildrenCheck.end(), it->GetMemPoolChildrenConst().begin(), comp));
748 : // Also check to make sure size is greater than sum with immediate children.
749 : // just a sanity check, not definitive that this calc is correct...
750 2005 : assert(it->GetSizeWithDescendants() >= child_sizes + it->GetTxSize());
751 :
752 2005 : TxValidationState dummy_state; // Not used. CheckTxInputs() should always pass
753 2005 : CAmount txfee = 0;
754 2005 : assert(!tx.IsCoinBase());
755 2005 : assert(Consensus::CheckTxInputs(tx, dummy_state, mempoolDuplicate, spendheight, txfee));
756 6314 : for (const auto& input: tx.vin) mempoolDuplicate.SpendCoin(input.prevout);
757 2005 : AddCoins(mempoolDuplicate, tx, std::numeric_limits<int>::max());
758 2005 : }
759 10937 : for (auto it = mapNextTx.cbegin(); it != mapNextTx.cend(); it++) {
760 4309 : uint256 hash = it->second->GetHash();
761 4309 : indexed_transaction_set::const_iterator it2 = mapTx.find(hash);
762 4309 : const CTransaction& tx = it2->GetTx();
763 4309 : assert(it2 != mapTx.end());
764 4309 : assert(&tx == it->second);
765 4309 : }
766 :
767 6628 : assert(totalTxSize == checkTotal);
768 6628 : assert(m_total_fee == check_total_fee);
769 6628 : assert(innerUsage == cachedInnerUsage);
770 6628 : }
771 :
772 0 : bool CTxMemPool::CompareDepthAndScore(const uint256& hasha, const uint256& hashb, bool wtxid)
773 : {
774 : /* Return `true` if hasha should be considered sooner than hashb. Namely when:
775 : * a is not in the mempool, but b is
776 : * both are in the mempool and a has fewer ancestors than b
777 : * both are in the mempool and a has a higher score than b
778 : */
779 0 : LOCK(cs);
780 0 : indexed_transaction_set::const_iterator j = wtxid ? get_iter_from_wtxid(hashb) : mapTx.find(hashb);
781 0 : if (j == mapTx.end()) return false;
782 0 : indexed_transaction_set::const_iterator i = wtxid ? get_iter_from_wtxid(hasha) : mapTx.find(hasha);
783 0 : if (i == mapTx.end()) return true;
784 0 : uint64_t counta = i->GetCountWithAncestors();
785 0 : uint64_t countb = j->GetCountWithAncestors();
786 0 : if (counta == countb) {
787 0 : return CompareTxMemPoolEntryByScore()(*i, *j);
788 : }
789 0 : return counta < countb;
790 0 : }
791 :
792 : namespace {
793 : class DepthAndScoreComparator
794 : {
795 : public:
796 1482 : bool operator()(const CTxMemPool::indexed_transaction_set::const_iterator& a, const CTxMemPool::indexed_transaction_set::const_iterator& b)
797 : {
798 1482 : uint64_t counta = a->GetCountWithAncestors();
799 1482 : uint64_t countb = b->GetCountWithAncestors();
800 1482 : if (counta == countb) {
801 388 : return CompareTxMemPoolEntryByScore()(*a, *b);
802 : }
803 1094 : return counta < countb;
804 1482 : }
805 : };
806 : } // namespace
807 :
808 13055 : std::vector<CTxMemPool::indexed_transaction_set::const_iterator> CTxMemPool::GetSortedDepthAndScore() const
809 : {
810 13055 : std::vector<indexed_transaction_set::const_iterator> iters;
811 13055 : AssertLockHeld(cs);
812 :
813 13055 : iters.reserve(mapTx.size());
814 :
815 17065 : for (indexed_transaction_set::iterator mi = mapTx.begin(); mi != mapTx.end(); ++mi) {
816 4010 : iters.push_back(mi);
817 4010 : }
818 13055 : std::sort(iters.begin(), iters.end(), DepthAndScoreComparator());
819 13055 : return iters;
820 13055 : }
821 :
822 1568 : void CTxMemPool::queryHashes(std::vector<uint256>& vtxid) const
823 : {
824 1568 : LOCK(cs);
825 1568 : auto iters = GetSortedDepthAndScore();
826 :
827 1568 : vtxid.clear();
828 1568 : vtxid.reserve(mapTx.size());
829 :
830 1671 : for (auto it : iters) {
831 103 : vtxid.push_back(it->GetTx().GetHash());
832 : }
833 1568 : }
834 :
835 1902 : static TxMempoolInfo GetInfo(CTxMemPool::indexed_transaction_set::const_iterator it) {
836 1902 : return TxMempoolInfo{it->GetSharedTx(), it->GetTime(), it->GetFee(), it->GetTxSize(), it->GetModifiedFee() - it->GetFee()};
837 0 : }
838 :
839 4859 : std::vector<TxMempoolInfo> CTxMemPool::infoAll() const
840 : {
841 4859 : LOCK(cs);
842 4859 : auto iters = GetSortedDepthAndScore();
843 :
844 4859 : std::vector<TxMempoolInfo> ret;
845 4859 : ret.reserve(mapTx.size());
846 6761 : for (auto it : iters) {
847 1902 : ret.push_back(GetInfo(it));
848 : }
849 :
850 4859 : return ret;
851 4859 : }
852 :
853 84171 : CTransactionRef CTxMemPool::get(const uint256& hash) const
854 : {
855 84171 : LOCK(cs);
856 84171 : indexed_transaction_set::const_iterator i = mapTx.find(hash);
857 84171 : if (i == mapTx.end())
858 52853 : return nullptr;
859 31318 : return i->GetSharedTx();
860 84171 : }
861 :
862 0 : TxMempoolInfo CTxMemPool::info(const GenTxid& gtxid) const
863 : {
864 0 : LOCK(cs);
865 0 : indexed_transaction_set::const_iterator i = (gtxid.IsWtxid() ? get_iter_from_wtxid(gtxid.GetHash()) : mapTx.find(gtxid.GetHash()));
866 0 : if (i == mapTx.end())
867 0 : return TxMempoolInfo();
868 0 : return GetInfo(i);
869 0 : }
870 :
871 0 : TxMempoolInfo CTxMemPool::info_for_relay(const GenTxid& gtxid, uint64_t last_sequence) const
872 : {
873 0 : LOCK(cs);
874 0 : indexed_transaction_set::const_iterator i = (gtxid.IsWtxid() ? get_iter_from_wtxid(gtxid.GetHash()) : mapTx.find(gtxid.GetHash()));
875 0 : if (i != mapTx.end() && i->GetSequence() < last_sequence) {
876 0 : return GetInfo(i);
877 : } else {
878 0 : return TxMempoolInfo();
879 : }
880 0 : }
881 :
882 2324 : void CTxMemPool::PrioritiseTransaction(const uint256& hash, const CAmount& nFeeDelta)
883 : {
884 : {
885 2324 : LOCK(cs);
886 2324 : CAmount &delta = mapDeltas[hash];
887 2324 : delta = SaturatingAdd(delta, nFeeDelta);
888 2324 : txiter it = mapTx.find(hash);
889 2324 : if (it != mapTx.end()) {
890 278 : mapTx.modify(it, [&nFeeDelta](CTxMemPoolEntry& e) { e.UpdateModifiedFee(nFeeDelta); });
891 : // Now update all ancestors' modified fees with descendants
892 139 : auto ancestors{AssumeCalculateMemPoolAncestors(__func__, *it, Limits::NoLimits(), /*fSearchForParents=*/false)};
893 278 : for (txiter ancestorIt : ancestors) {
894 278 : mapTx.modify(ancestorIt, [=](CTxMemPoolEntry& e){ e.UpdateDescendantState(0, nFeeDelta, 0);});
895 : }
896 : // Now update all descendants' modified fees with ancestors
897 139 : setEntries setDescendants;
898 139 : CalculateDescendants(it, setDescendants);
899 139 : setDescendants.erase(it);
900 139 : for (txiter descendantIt : setDescendants) {
901 0 : mapTx.modify(descendantIt, [=](CTxMemPoolEntry& e){ e.UpdateAncestorState(0, nFeeDelta, 0, 0); });
902 : }
903 139 : ++nTransactionsUpdated;
904 139 : }
905 2324 : if (delta == 0) {
906 0 : mapDeltas.erase(hash);
907 0 : LogPrintf("PrioritiseTransaction: %s (%sin mempool) delta cleared\n", hash.ToString(), it == mapTx.end() ? "not " : "");
908 0 : } else {
909 2324 : LogPrintf("PrioritiseTransaction: %s (%sin mempool) fee += %s, new delta=%s\n",
910 : hash.ToString(),
911 : it == mapTx.end() ? "not " : "",
912 : FormatMoney(nFeeDelta),
913 : FormatMoney(delta));
914 : }
915 2324 : }
916 2324 : }
917 :
918 7258 : void CTxMemPool::ApplyDelta(const uint256& hash, CAmount &nFeeDelta) const
919 : {
920 7258 : AssertLockHeld(cs);
921 7258 : std::map<uint256, CAmount>::const_iterator pos = mapDeltas.find(hash);
922 7258 : if (pos == mapDeltas.end())
923 5640 : return;
924 1618 : const CAmount &delta = pos->second;
925 1618 : nFeeDelta += delta;
926 7258 : }
927 :
928 201 : void CTxMemPool::ClearPrioritisation(const uint256& hash)
929 : {
930 201 : AssertLockHeld(cs);
931 201 : mapDeltas.erase(hash);
932 201 : }
933 :
934 0 : std::vector<CTxMemPool::delta_info> CTxMemPool::GetPrioritisedTransactions() const
935 : {
936 0 : AssertLockNotHeld(cs);
937 0 : LOCK(cs);
938 0 : std::vector<delta_info> result;
939 0 : result.reserve(mapDeltas.size());
940 0 : for (const auto& [txid, delta] : mapDeltas) {
941 0 : const auto iter{mapTx.find(txid)};
942 0 : const bool in_mempool{iter != mapTx.end()};
943 0 : std::optional<CAmount> modified_fee;
944 0 : if (in_mempool) modified_fee = iter->GetModifiedFee();
945 0 : result.emplace_back(delta_info{in_mempool, delta, modified_fee, txid});
946 : }
947 0 : return result;
948 0 : }
949 :
950 248763 : const CTransaction* CTxMemPool::GetConflictTx(const COutPoint& prevout) const
951 : {
952 248763 : const auto it = mapNextTx.find(prevout);
953 248763 : return it == mapNextTx.end() ? nullptr : it->second;
954 : }
955 :
956 18536 : std::optional<CTxMemPool::txiter> CTxMemPool::GetIter(const uint256& txid) const
957 : {
958 18536 : auto it = mapTx.find(txid);
959 18536 : if (it != mapTx.end()) return it;
960 13616 : return std::nullopt;
961 18536 : }
962 :
963 6526 : CTxMemPool::setEntries CTxMemPool::GetIterSet(const std::set<uint256>& hashes) const
964 : {
965 6526 : CTxMemPool::setEntries ret;
966 11010 : for (const auto& h : hashes) {
967 4484 : const auto mi = GetIter(h);
968 4484 : if (mi) ret.insert(*mi);
969 : }
970 6526 : return ret;
971 6526 : }
972 :
973 0 : std::vector<CTxMemPool::txiter> CTxMemPool::GetIterVec(const std::vector<uint256>& txids) const
974 : {
975 0 : AssertLockHeld(cs);
976 0 : std::vector<txiter> ret;
977 0 : ret.reserve(txids.size());
978 0 : for (const auto& txid : txids) {
979 0 : const auto it{GetIter(txid)};
980 0 : if (!it) return {};
981 0 : ret.push_back(*it);
982 : }
983 0 : return ret;
984 0 : }
985 :
986 0 : bool CTxMemPool::HasNoInputsOf(const CTransaction &tx) const
987 : {
988 0 : for (unsigned int i = 0; i < tx.vin.size(); i++)
989 0 : if (exists(GenTxid::Txid(tx.vin[i].prevout.hash)))
990 0 : return false;
991 0 : return true;
992 0 : }
993 :
994 15344 : CCoinsViewMemPool::CCoinsViewMemPool(CCoinsView* baseIn, const CTxMemPool& mempoolIn) : CCoinsViewBacked(baseIn), mempool(mempoolIn) { }
995 :
996 79316 : bool CCoinsViewMemPool::GetCoin(const COutPoint &outpoint, Coin &coin) const {
997 : // Check to see if the inputs are made available by another tx in the package.
998 : // These Coins would not be available in the underlying CoinsView.
999 79316 : if (auto it = m_temp_added.find(outpoint); it != m_temp_added.end()) {
1000 379 : coin = it->second;
1001 379 : return true;
1002 : }
1003 :
1004 : // If an entry in the mempool exists, always return that one, as it's guaranteed to never
1005 : // conflict with the underlying cache, and it cannot have pruned entries (as it contains full)
1006 : // transactions. First checking the underlying cache risks returning a pruned entry instead.
1007 78937 : CTransactionRef ptx = mempool.get(outpoint.hash);
1008 78937 : if (ptx) {
1009 30443 : if (outpoint.n < ptx->vout.size()) {
1010 30443 : coin = Coin(ptx->vout[outpoint.n], MEMPOOL_HEIGHT, false);
1011 30443 : m_non_base_coins.emplace(outpoint);
1012 30443 : return true;
1013 : } else {
1014 0 : return false;
1015 : }
1016 : }
1017 48494 : return base->GetCoin(outpoint, coin);
1018 79316 : }
1019 :
1020 1150 : void CCoinsViewMemPool::PackageAddTransaction(const CTransactionRef& tx)
1021 : {
1022 10866 : for (unsigned int n = 0; n < tx->vout.size(); ++n) {
1023 9716 : m_temp_added.emplace(COutPoint(tx->GetHash(), n), Coin(tx->vout[n], MEMPOOL_HEIGHT, false));
1024 9716 : m_non_base_coins.emplace(COutPoint(tx->GetHash(), n));
1025 9716 : }
1026 1150 : }
1027 5532 : void CCoinsViewMemPool::Reset()
1028 : {
1029 5532 : m_temp_added.clear();
1030 5532 : m_non_base_coins.clear();
1031 5532 : }
1032 :
1033 18489 : size_t CTxMemPool::DynamicMemoryUsage() const {
1034 18489 : LOCK(cs);
1035 : // Estimate the overhead of mapTx to be 15 pointers + an allocation, as no exact formula for boost::multi_index_contained is implemented.
1036 18489 : return memusage::MallocUsage(sizeof(CTxMemPoolEntry) + 15 * sizeof(void*)) * mapTx.size() + memusage::DynamicUsage(mapNextTx) + memusage::DynamicUsage(mapDeltas) + memusage::DynamicUsage(vTxHashes) + cachedInnerUsage;
1037 18489 : }
1038 :
1039 2108 : void CTxMemPool::RemoveUnbroadcastTx(const uint256& txid, const bool unchecked) {
1040 2108 : LOCK(cs);
1041 :
1042 2108 : if (m_unbroadcast_txids.erase(txid))
1043 : {
1044 0 : LogPrint(BCLog::MEMPOOL, "Removed %i from set of unbroadcast txns%s\n", txid.GetHex(), (unchecked ? " before confirmation that txn was sent out" : ""));
1045 0 : }
1046 2108 : }
1047 :
1048 7301 : void CTxMemPool::RemoveStaged(setEntries &stage, bool updateDescendants, MemPoolRemovalReason reason) {
1049 7301 : AssertLockHeld(cs);
1050 7301 : UpdateForRemoveFromMempool(stage, updateDescendants);
1051 9409 : for (txiter it : stage) {
1052 2108 : removeUnchecked(it, reason);
1053 : }
1054 7301 : }
1055 :
1056 3338 : int CTxMemPool::Expire(std::chrono::seconds time)
1057 : {
1058 3338 : AssertLockHeld(cs);
1059 3338 : indexed_transaction_set::index<entry_time>::type::iterator it = mapTx.get<entry_time>().begin();
1060 3338 : setEntries toremove;
1061 6049 : while (it != mapTx.get<entry_time>().end() && it->GetTime() < time) {
1062 102 : toremove.insert(mapTx.project<0>(it));
1063 102 : it++;
1064 : }
1065 3338 : setEntries stage;
1066 3440 : for (txiter removeit : toremove) {
1067 102 : CalculateDescendants(removeit, stage);
1068 : }
1069 3338 : RemoveStaged(stage, false, MemPoolRemovalReason::EXPIRY);
1070 3338 : return stage.size();
1071 3338 : }
1072 :
1073 0 : void CTxMemPool::addUnchecked(const CTxMemPoolEntry &entry, bool validFeeEstimate)
1074 : {
1075 0 : auto ancestors{AssumeCalculateMemPoolAncestors(__func__, entry, Limits::NoLimits())};
1076 0 : return addUnchecked(entry, ancestors, validFeeEstimate);
1077 0 : }
1078 :
1079 692 : void CTxMemPool::UpdateChild(txiter entry, txiter child, bool add)
1080 : {
1081 692 : AssertLockHeld(cs);
1082 692 : CTxMemPoolEntry::Children s;
1083 692 : if (add && entry->GetMemPoolChildren().insert(*child).second) {
1084 348 : cachedInnerUsage += memusage::IncrementalDynamicUsage(s);
1085 692 : } else if (!add && entry->GetMemPoolChildren().erase(*child)) {
1086 344 : cachedInnerUsage -= memusage::IncrementalDynamicUsage(s);
1087 344 : }
1088 692 : }
1089 :
1090 348 : void CTxMemPool::UpdateParent(txiter entry, txiter parent, bool add)
1091 : {
1092 348 : AssertLockHeld(cs);
1093 348 : CTxMemPoolEntry::Parents s;
1094 348 : if (add && entry->GetMemPoolParents().insert(*parent).second) {
1095 348 : cachedInnerUsage += memusage::IncrementalDynamicUsage(s);
1096 348 : } else if (!add && entry->GetMemPoolParents().erase(*parent)) {
1097 0 : cachedInnerUsage -= memusage::IncrementalDynamicUsage(s);
1098 0 : }
1099 348 : }
1100 :
1101 3879 : CFeeRate CTxMemPool::GetMinFee(size_t sizelimit) const {
1102 3879 : LOCK(cs);
1103 3879 : if (!blockSinceLastRollingFeeBump || rollingMinimumFeeRate == 0)
1104 3656 : return CFeeRate(llround(rollingMinimumFeeRate));
1105 :
1106 223 : int64_t time = GetTime();
1107 223 : if (time > lastRollingFeeUpdate + 10) {
1108 3 : double halflife = ROLLING_FEE_HALFLIFE;
1109 3 : if (DynamicMemoryUsage() < sizelimit / 4)
1110 0 : halflife /= 4;
1111 3 : else if (DynamicMemoryUsage() < sizelimit / 2)
1112 0 : halflife /= 2;
1113 :
1114 3 : rollingMinimumFeeRate = rollingMinimumFeeRate / pow(2.0, (time - lastRollingFeeUpdate) / halflife);
1115 3 : lastRollingFeeUpdate = time;
1116 :
1117 3 : if (rollingMinimumFeeRate < (double)m_incremental_relay_feerate.GetFeePerK() / 2) {
1118 3 : rollingMinimumFeeRate = 0;
1119 3 : return CFeeRate(0);
1120 : }
1121 0 : }
1122 220 : return std::max(CFeeRate(llround(rollingMinimumFeeRate)), m_incremental_relay_feerate);
1123 3879 : }
1124 :
1125 184 : void CTxMemPool::trackPackageRemoved(const CFeeRate& rate) {
1126 184 : AssertLockHeld(cs);
1127 184 : if (rate.GetFeePerK() > rollingMinimumFeeRate) {
1128 183 : rollingMinimumFeeRate = rate.GetFeePerK();
1129 183 : blockSinceLastRollingFeeBump = false;
1130 183 : }
1131 184 : }
1132 :
1133 3338 : void CTxMemPool::TrimToSize(size_t sizelimit, std::vector<COutPoint>* pvNoSpendsRemaining) {
1134 3338 : AssertLockHeld(cs);
1135 :
1136 3338 : unsigned nTxnRemoved = 0;
1137 3338 : CFeeRate maxFeeRateRemoved(0);
1138 3522 : while (!mapTx.empty() && DynamicMemoryUsage() > sizelimit) {
1139 184 : indexed_transaction_set::index<descendant_score>::type::iterator it = mapTx.get<descendant_score>().begin();
1140 :
1141 : // We set the new mempool min fee to the feerate of the removed set, plus the
1142 : // "minimum reasonable fee rate" (ie some value under which we consider txn
1143 : // to have 0 fee). This way, we don't allow txn to enter mempool with feerate
1144 : // equal to txn which were removed with no block in between.
1145 184 : CFeeRate removed(it->GetModFeesWithDescendants(), it->GetSizeWithDescendants());
1146 184 : removed += m_incremental_relay_feerate;
1147 184 : trackPackageRemoved(removed);
1148 184 : maxFeeRateRemoved = std::max(maxFeeRateRemoved, removed);
1149 :
1150 184 : setEntries stage;
1151 184 : CalculateDescendants(mapTx.project<0>(it), stage);
1152 184 : nTxnRemoved += stage.size();
1153 :
1154 184 : std::vector<CTransaction> txn;
1155 184 : if (pvNoSpendsRemaining) {
1156 184 : txn.reserve(stage.size());
1157 381 : for (txiter iter : stage)
1158 197 : txn.push_back(iter->GetTx());
1159 184 : }
1160 184 : RemoveStaged(stage, false, MemPoolRemovalReason::SIZELIMIT);
1161 184 : if (pvNoSpendsRemaining) {
1162 381 : for (const CTransaction& tx : txn) {
1163 591 : for (const CTxIn& txin : tx.vin) {
1164 394 : if (exists(GenTxid::Txid(txin.prevout.hash))) continue;
1165 328 : pvNoSpendsRemaining->push_back(txin.prevout);
1166 : }
1167 : }
1168 184 : }
1169 184 : }
1170 :
1171 3338 : if (maxFeeRateRemoved > CFeeRate(0)) {
1172 154 : LogPrint(BCLog::MEMPOOL, "Removed %u txn, rolling minimum fee bumped to %s\n", nTxnRemoved, maxFeeRateRemoved.ToString());
1173 154 : }
1174 3338 : }
1175 :
1176 0 : uint64_t CTxMemPool::CalculateDescendantMaximum(txiter entry) const {
1177 : // find parent with highest descendant count
1178 0 : std::vector<txiter> candidates;
1179 0 : setEntries counted;
1180 0 : candidates.push_back(entry);
1181 0 : uint64_t maximum = 0;
1182 0 : while (candidates.size()) {
1183 0 : txiter candidate = candidates.back();
1184 0 : candidates.pop_back();
1185 0 : if (!counted.insert(candidate).second) continue;
1186 0 : const CTxMemPoolEntry::Parents& parents = candidate->GetMemPoolParentsConst();
1187 0 : if (parents.size() == 0) {
1188 0 : maximum = std::max(maximum, candidate->GetCountWithDescendants());
1189 0 : } else {
1190 0 : for (const CTxMemPoolEntry& i : parents) {
1191 0 : candidates.push_back(mapTx.iterator_to(i));
1192 : }
1193 : }
1194 : }
1195 0 : return maximum;
1196 0 : }
1197 :
1198 0 : void CTxMemPool::GetTransactionAncestry(const uint256& txid, size_t& ancestors, size_t& descendants, size_t* const ancestorsize, CAmount* const ancestorfees) const {
1199 0 : LOCK(cs);
1200 0 : auto it = mapTx.find(txid);
1201 0 : ancestors = descendants = 0;
1202 0 : if (it != mapTx.end()) {
1203 0 : ancestors = it->GetCountWithAncestors();
1204 0 : if (ancestorsize) *ancestorsize = it->GetSizeWithAncestors();
1205 0 : if (ancestorfees) *ancestorfees = it->GetModFeesWithAncestors();
1206 0 : descendants = CalculateDescendantMaximum(it);
1207 0 : }
1208 0 : }
1209 :
1210 0 : bool CTxMemPool::GetLoadTried() const
1211 : {
1212 0 : LOCK(cs);
1213 0 : return m_load_tried;
1214 0 : }
1215 :
1216 0 : void CTxMemPool::SetLoadTried(bool load_tried)
1217 : {
1218 0 : LOCK(cs);
1219 0 : m_load_tried = load_tried;
1220 0 : }
1221 :
1222 0 : std::vector<CTxMemPool::txiter> CTxMemPool::GatherClusters(const std::vector<uint256>& txids) const
1223 : {
1224 0 : AssertLockHeld(cs);
1225 0 : std::vector<txiter> clustered_txs{GetIterVec(txids)};
1226 : // Use epoch: visiting an entry means we have added it to the clustered_txs vector. It does not
1227 : // necessarily mean the entry has been processed.
1228 0 : WITH_FRESH_EPOCH(m_epoch);
1229 0 : for (const auto& it : clustered_txs) {
1230 0 : visited(it);
1231 : }
1232 : // i = index of where the list of entries to process starts
1233 0 : for (size_t i{0}; i < clustered_txs.size(); ++i) {
1234 : // DoS protection: if there are 500 or more entries to process, just quit.
1235 0 : if (clustered_txs.size() > 500) return {};
1236 0 : const txiter& tx_iter = clustered_txs.at(i);
1237 0 : for (const auto& entries : {tx_iter->GetMemPoolParentsConst(), tx_iter->GetMemPoolChildrenConst()}) {
1238 0 : for (const CTxMemPoolEntry& entry : entries) {
1239 0 : const auto entry_it = mapTx.iterator_to(entry);
1240 0 : if (!visited(entry_it)) {
1241 0 : clustered_txs.push_back(entry_it);
1242 0 : }
1243 : }
1244 : }
1245 0 : }
1246 0 : return clustered_txs;
1247 0 : }
|
