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