txmempool.cpp
1 // Copyright (c) 2009-2010 Satoshi Nakamoto 2 // Copyright (c) 2009-present 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 <policy/policy.h> 15 #include <policy/settings.h> 16 #include <random.h> 17 #include <tinyformat.h> 18 #include <util/check.h> 19 #include <util/feefrac.h> 20 #include <util/log.h> 21 #include <util/moneystr.h> 22 #include <util/overflow.h> 23 #include <util/result.h> 24 #include <util/time.h> 25 #include <util/trace.h> 26 #include <util/translation.h> 27 #include <validationinterface.h> 28 29 #include <algorithm> 30 #include <cmath> 31 #include <numeric> 32 #include <optional> 33 #include <ranges> 34 #include <string_view> 35 #include <utility> 36 37 TRACEPOINT_SEMAPHORE(mempool, added); 38 TRACEPOINT_SEMAPHORE(mempool, removed); 39 40 bool TestLockPointValidity(CChain& active_chain, const LockPoints& lp) 41 { 42 AssertLockHeld(cs_main); 43 // If there are relative lock times then the maxInputBlock will be set 44 // If there are no relative lock times, the LockPoints don't depend on the chain 45 if (lp.maxInputBlock) { 46 // Check whether active_chain is an extension of the block at which the LockPoints 47 // calculation was valid. If not LockPoints are no longer valid 48 if (!active_chain.Contains(lp.maxInputBlock)) { 49 return false; 50 } 51 } 52 53 // LockPoints still valid 54 return true; 55 } 56 57 std::vector<CTxMemPoolEntry::CTxMemPoolEntryRef> CTxMemPool::GetChildren(const CTxMemPoolEntry& entry) const 58 { 59 std::vector<CTxMemPoolEntry::CTxMemPoolEntryRef> ret; 60 const auto& hash = entry.GetTx().GetHash(); 61 { 62 LOCK(cs); 63 auto iter = mapNextTx.lower_bound(COutPoint(hash, 0)); 64 for (; iter != mapNextTx.end() && iter->first->hash == hash; ++iter) { 65 ret.emplace_back(*(iter->second)); 66 } 67 } 68 std::ranges::sort(ret, CompareIteratorByHash{}); 69 auto removed = std::ranges::unique(ret, [](auto& a, auto& b) noexcept { return &a.get() == &b.get(); }); 70 ret.erase(removed.begin(), removed.end()); 71 return ret; 72 } 73 74 std::vector<CTxMemPoolEntry::CTxMemPoolEntryRef> CTxMemPool::GetParents(const CTxMemPoolEntry& entry) const 75 { 76 LOCK(cs); 77 std::vector<CTxMemPoolEntry::CTxMemPoolEntryRef> ret; 78 std::set<Txid> inputs; 79 for (const auto& txin : entry.GetTx().vin) { 80 inputs.insert(txin.prevout.hash); 81 } 82 for (const auto& hash : inputs) { 83 std::optional<txiter> piter = GetIter(hash); 84 if (piter) { 85 ret.emplace_back(**piter); 86 } 87 } 88 return ret; 89 } 90 91 void CTxMemPool::UpdateTransactionsFromBlock(const std::vector<Txid>& vHashesToUpdate) 92 { 93 AssertLockHeld(cs); 94 95 // Iterate in reverse, so that whenever we are looking at a transaction 96 // we are sure that all in-mempool descendants have already been processed. 97 for (const Txid& hash : vHashesToUpdate | std::views::reverse) { 98 // calculate children from mapNextTx 99 txiter it = mapTx.find(hash); 100 if (it == mapTx.end()) { 101 continue; 102 } 103 auto iter = mapNextTx.lower_bound(COutPoint(hash, 0)); 104 { 105 for (; iter != mapNextTx.end() && iter->first->hash == hash; ++iter) { 106 txiter childIter = iter->second; 107 assert(childIter != mapTx.end()); 108 // Add dependencies that are discovered between transactions in the 109 // block and transactions that were in the mempool to txgraph. 110 m_txgraph->AddDependency(/*parent=*/*it, /*child=*/*childIter); 111 } 112 } 113 } 114 115 auto txs_to_remove = m_txgraph->Trim(); // Enforce cluster size limits. 116 for (auto txptr : txs_to_remove) { 117 const CTxMemPoolEntry& entry = *(static_cast<const CTxMemPoolEntry*>(txptr)); 118 removeUnchecked(mapTx.iterator_to(entry), MemPoolRemovalReason::SIZELIMIT); 119 } 120 } 121 122 bool CTxMemPool::HasDescendants(const Txid& txid) const 123 { 124 LOCK(cs); 125 auto entry = GetEntry(txid); 126 if (!entry) return false; 127 return m_txgraph->GetDescendants(*entry, TxGraph::Level::MAIN).size() > 1; 128 } 129 130 CTxMemPool::setEntries CTxMemPool::CalculateMemPoolAncestors(const CTxMemPoolEntry &entry) const 131 { 132 auto ancestors = m_txgraph->GetAncestors(entry, TxGraph::Level::MAIN); 133 setEntries ret; 134 if (ancestors.size() > 0) { 135 for (auto ancestor : ancestors) { 136 if (ancestor != &entry) { 137 ret.insert(mapTx.iterator_to(static_cast<const CTxMemPoolEntry&>(*ancestor))); 138 } 139 } 140 return ret; 141 } 142 143 // If we didn't get anything back, the transaction is not in the graph. 144 // Find each parent and call GetAncestors on each. 145 setEntries staged_parents; 146 const CTransaction &tx = entry.GetTx(); 147 148 // Get parents of this transaction that are in the mempool 149 for (unsigned int i = 0; i < tx.vin.size(); i++) { 150 std::optional<txiter> piter = GetIter(tx.vin[i].prevout.hash); 151 if (piter) { 152 staged_parents.insert(*piter); 153 } 154 } 155 156 for (const auto& parent : staged_parents) { 157 auto parent_ancestors = m_txgraph->GetAncestors(*parent, TxGraph::Level::MAIN); 158 for (auto ancestor : parent_ancestors) { 159 ret.insert(mapTx.iterator_to(static_cast<const CTxMemPoolEntry&>(*ancestor))); 160 } 161 } 162 163 return ret; 164 } 165 166 static CTxMemPool::Options&& Flatten(CTxMemPool::Options&& opts, bilingual_str& error) 167 { 168 opts.check_ratio = std::clamp<int>(opts.check_ratio, 0, 1'000'000); 169 int64_t cluster_limit_bytes = opts.limits.cluster_size_vbytes * 40; 170 if (opts.max_size_bytes < 0 || (opts.max_size_bytes > 0 && opts.max_size_bytes < cluster_limit_bytes)) { 171 error = strprintf(_("-maxmempool must be at least %d MB"), std::ceil(cluster_limit_bytes / 1'000'000.0)); 172 } 173 return std::move(opts); 174 } 175 176 CTxMemPool::CTxMemPool(Options opts, bilingual_str& error) 177 : m_opts{Flatten(std::move(opts), error)} 178 { 179 m_txgraph = MakeTxGraph( 180 /*max_cluster_count=*/m_opts.limits.cluster_count, 181 /*max_cluster_size=*/m_opts.limits.cluster_size_vbytes * WITNESS_SCALE_FACTOR, 182 /*acceptable_cost=*/ACCEPTABLE_COST, 183 /*fallback_order=*/[&](const TxGraph::Ref& a, const TxGraph::Ref& b) noexcept { 184 const Txid& txid_a = static_cast<const CTxMemPoolEntry&>(a).GetTx().GetHash(); 185 const Txid& txid_b = static_cast<const CTxMemPoolEntry&>(b).GetTx().GetHash(); 186 return txid_a <=> txid_b; 187 }); 188 } 189 190 bool CTxMemPool::isSpent(const COutPoint& outpoint) const 191 { 192 LOCK(cs); 193 return mapNextTx.count(outpoint); 194 } 195 196 unsigned int CTxMemPool::GetTransactionsUpdated() const 197 { 198 return nTransactionsUpdated; 199 } 200 201 void CTxMemPool::AddTransactionsUpdated(unsigned int n) 202 { 203 nTransactionsUpdated += n; 204 } 205 206 void CTxMemPool::Apply(ChangeSet* changeset) 207 { 208 AssertLockHeld(cs); 209 m_txgraph->CommitStaging(); 210 211 RemoveStaged(changeset->m_to_remove, MemPoolRemovalReason::REPLACED); 212 213 for (size_t i=0; i<changeset->m_entry_vec.size(); ++i) { 214 auto tx_entry = changeset->m_entry_vec[i]; 215 // First splice this entry into mapTx. 216 auto node_handle = changeset->m_to_add.extract(tx_entry); 217 auto result = mapTx.insert(std::move(node_handle)); 218 219 Assume(result.inserted); 220 txiter it = result.position; 221 222 addNewTransaction(it); 223 } 224 if (!m_txgraph->DoWork(/*max_cost=*/POST_CHANGE_COST)) { 225 LogDebug(BCLog::MEMPOOL, "Mempool in non-optimal ordering after addition(s)."); 226 } 227 } 228 229 void CTxMemPool::addNewTransaction(CTxMemPool::txiter newit) 230 { 231 const CTxMemPoolEntry& entry = *newit; 232 233 // Update cachedInnerUsage to include contained transaction's usage. 234 // (When we update the entry for in-mempool parents, memory usage will be 235 // further updated.) 236 cachedInnerUsage += entry.DynamicMemoryUsage(); 237 238 const CTransaction& tx = newit->GetTx(); 239 for (unsigned int i = 0; i < tx.vin.size(); i++) { 240 mapNextTx.insert(std::make_pair(&tx.vin[i].prevout, newit)); 241 } 242 // Don't bother worrying about child transactions of this one. 243 // Normal case of a new transaction arriving is that there can't be any 244 // children, because such children would be orphans. 245 // An exception to that is if a transaction enters that used to be in a block. 246 // In that case, our disconnect block logic will call UpdateTransactionsFromBlock 247 // to clean up the mess we're leaving here. 248 249 nTransactionsUpdated++; 250 totalTxSize += entry.GetTxSize(); 251 m_total_fee += entry.GetFee(); 252 253 txns_randomized.emplace_back(tx.GetWitnessHash(), newit); 254 newit->idx_randomized = txns_randomized.size() - 1; 255 256 TRACEPOINT(mempool, added, 257 entry.GetTx().GetHash().data(), 258 entry.GetTxSize(), 259 entry.GetFee() 260 ); 261 } 262 263 void CTxMemPool::removeUnchecked(txiter it, MemPoolRemovalReason reason) 264 { 265 // We increment mempool sequence value no matter removal reason 266 // even if not directly reported below. 267 uint64_t mempool_sequence = GetAndIncrementSequence(); 268 269 if (reason != MemPoolRemovalReason::BLOCK && m_opts.signals) { 270 // Notify clients that a transaction has been removed from the mempool 271 // for any reason except being included in a block. Clients interested 272 // in transactions included in blocks can subscribe to the BlockConnected 273 // notification. 274 m_opts.signals->TransactionRemovedFromMempool(it->GetSharedTx(), reason, mempool_sequence); 275 } 276 TRACEPOINT(mempool, removed, 277 it->GetTx().GetHash().data(), 278 RemovalReasonToString(reason).c_str(), 279 it->GetTxSize(), 280 it->GetFee(), 281 std::chrono::duration_cast<std::chrono::duration<std::uint64_t>>(it->GetTime()).count() 282 ); 283 284 for (const CTxIn& txin : it->GetTx().vin) 285 mapNextTx.erase(txin.prevout); 286 287 RemoveUnbroadcastTx(it->GetTx().GetHash(), true /* add logging because unchecked */); 288 289 if (txns_randomized.size() > 1) { 290 // Remove entry from txns_randomized by replacing it with the back and deleting the back. 291 txns_randomized[it->idx_randomized] = std::move(txns_randomized.back()); 292 txns_randomized[it->idx_randomized].second->idx_randomized = it->idx_randomized; 293 txns_randomized.pop_back(); 294 if (txns_randomized.size() * 2 < txns_randomized.capacity()) { 295 txns_randomized.shrink_to_fit(); 296 } 297 } else { 298 txns_randomized.clear(); 299 } 300 301 totalTxSize -= it->GetTxSize(); 302 m_total_fee -= it->GetFee(); 303 cachedInnerUsage -= it->DynamicMemoryUsage(); 304 mapTx.erase(it); 305 nTransactionsUpdated++; 306 } 307 308 // Calculates descendants of given entry and adds to setDescendants. 309 void CTxMemPool::CalculateDescendants(txiter entryit, setEntries& setDescendants) const 310 { 311 (void)CalculateDescendants(*entryit, setDescendants); 312 return; 313 } 314 315 CTxMemPool::txiter CTxMemPool::CalculateDescendants(const CTxMemPoolEntry& entry, setEntries& setDescendants) const 316 { 317 for (auto tx : m_txgraph->GetDescendants(entry, TxGraph::Level::MAIN)) { 318 setDescendants.insert(mapTx.iterator_to(static_cast<const CTxMemPoolEntry&>(*tx))); 319 } 320 return mapTx.iterator_to(entry); 321 } 322 323 void CTxMemPool::removeRecursive(CTxMemPool::txiter to_remove, MemPoolRemovalReason reason) 324 { 325 AssertLockHeld(cs); 326 Assume(!m_have_changeset); 327 auto descendants = m_txgraph->GetDescendants(*to_remove, TxGraph::Level::MAIN); 328 for (auto tx: descendants) { 329 removeUnchecked(mapTx.iterator_to(static_cast<const CTxMemPoolEntry&>(*tx)), reason); 330 } 331 } 332 333 void CTxMemPool::removeRecursive(const CTransaction &origTx, MemPoolRemovalReason reason) 334 { 335 // Remove transaction from memory pool 336 AssertLockHeld(cs); 337 Assume(!m_have_changeset); 338 txiter origit = mapTx.find(origTx.GetHash()); 339 if (origit != mapTx.end()) { 340 removeRecursive(origit, reason); 341 } else { 342 // When recursively removing but origTx isn't in the mempool 343 // be sure to remove any descendants that are in the pool. This can 344 // happen during chain re-orgs if origTx isn't re-accepted into 345 // the mempool for any reason. 346 auto iter = mapNextTx.lower_bound(COutPoint(origTx.GetHash(), 0)); 347 std::vector<const TxGraph::Ref*> to_remove; 348 while (iter != mapNextTx.end() && iter->first->hash == origTx.GetHash()) { 349 to_remove.emplace_back(&*(iter->second)); 350 ++iter; 351 } 352 auto all_removes = m_txgraph->GetDescendantsUnion(to_remove, TxGraph::Level::MAIN); 353 for (auto ref : all_removes) { 354 auto tx = mapTx.iterator_to(static_cast<const CTxMemPoolEntry&>(*ref)); 355 removeUnchecked(tx, reason); 356 } 357 } 358 } 359 360 void CTxMemPool::removeForReorg(CChain& chain, std::function<bool(txiter)> check_final_and_mature) 361 { 362 // Remove transactions spending a coinbase which are now immature and no-longer-final transactions 363 AssertLockHeld(cs); 364 AssertLockHeld(::cs_main); 365 Assume(!m_have_changeset); 366 367 std::vector<const TxGraph::Ref*> to_remove; 368 for (txiter it = mapTx.begin(); it != mapTx.end(); it++) { 369 if (check_final_and_mature(it)) { 370 to_remove.emplace_back(&*it); 371 } 372 } 373 374 auto all_to_remove = m_txgraph->GetDescendantsUnion(to_remove, TxGraph::Level::MAIN); 375 376 for (auto ref : all_to_remove) { 377 auto it = mapTx.iterator_to(static_cast<const CTxMemPoolEntry&>(*ref)); 378 removeUnchecked(it, MemPoolRemovalReason::REORG); 379 } 380 for (indexed_transaction_set::const_iterator it = mapTx.begin(); it != mapTx.end(); it++) { 381 assert(TestLockPointValidity(chain, it->GetLockPoints())); 382 } 383 if (!m_txgraph->DoWork(/*max_cost=*/POST_CHANGE_COST)) { 384 LogDebug(BCLog::MEMPOOL, "Mempool in non-optimal ordering after reorg."); 385 } 386 } 387 388 void CTxMemPool::removeConflicts(const CTransaction &tx) 389 { 390 // Remove transactions which depend on inputs of tx, recursively 391 AssertLockHeld(cs); 392 for (const CTxIn &txin : tx.vin) { 393 auto it = mapNextTx.find(txin.prevout); 394 if (it != mapNextTx.end()) { 395 const CTransaction &txConflict = it->second->GetTx(); 396 if (Assume(txConflict.GetHash() != tx.GetHash())) 397 { 398 ClearPrioritisation(txConflict.GetHash()); 399 removeRecursive(it->second, MemPoolRemovalReason::CONFLICT); 400 } 401 } 402 } 403 } 404 405 void CTxMemPool::removeForBlock(const std::vector<CTransactionRef>& vtx, unsigned int nBlockHeight) 406 { 407 // Remove confirmed txs and conflicts when a new block is connected, updating the fee logic 408 AssertLockHeld(cs); 409 Assume(!m_have_changeset); 410 std::vector<RemovedMempoolTransactionInfo> txs_removed_for_block; 411 if (mapTx.size() || mapNextTx.size() || mapDeltas.size()) { 412 txs_removed_for_block.reserve(vtx.size()); 413 for (const auto& tx : vtx) { 414 txiter it = mapTx.find(tx->GetHash()); 415 if (it != mapTx.end()) { 416 txs_removed_for_block.emplace_back(*it); 417 removeUnchecked(it, MemPoolRemovalReason::BLOCK); 418 } 419 removeConflicts(*tx); 420 ClearPrioritisation(tx->GetHash()); 421 } 422 } 423 if (m_opts.signals) { 424 m_opts.signals->MempoolTransactionsRemovedForBlock(txs_removed_for_block, nBlockHeight); 425 } 426 lastRollingFeeUpdate = GetTime(); 427 blockSinceLastRollingFeeBump = true; 428 if (!m_txgraph->DoWork(/*max_cost=*/POST_CHANGE_COST)) { 429 LogDebug(BCLog::MEMPOOL, "Mempool in non-optimal ordering after block."); 430 } 431 } 432 433 void CTxMemPool::check(const CCoinsViewCache& active_coins_tip, int64_t spendheight) const 434 { 435 if (m_opts.check_ratio == 0) return; 436 437 if (FastRandomContext().randrange(m_opts.check_ratio) >= 1) return; 438 439 AssertLockHeld(::cs_main); 440 LOCK(cs); 441 LogDebug(BCLog::MEMPOOL, "Checking mempool with %u transactions and %u inputs\n", (unsigned int)mapTx.size(), (unsigned int)mapNextTx.size()); 442 443 uint64_t checkTotal = 0; 444 CAmount check_total_fee{0}; 445 CAmount check_total_modified_fee{0}; 446 int64_t check_total_adjusted_weight{0}; 447 uint64_t innerUsage = 0; 448 449 assert(!m_txgraph->IsOversized(TxGraph::Level::MAIN)); 450 m_txgraph->SanityCheck(); 451 452 CCoinsViewCache mempoolDuplicate(const_cast<CCoinsViewCache*>(&active_coins_tip)); 453 454 const auto score_with_topo{GetSortedScoreWithTopology()}; 455 456 // Number of chunks is bounded by number of transactions. 457 const auto diagram{GetFeerateDiagram()}; 458 assert(diagram.size() <= score_with_topo.size() + 1); 459 assert(diagram.size() >= 1); 460 461 std::optional<Wtxid> last_wtxid = std::nullopt; 462 auto diagram_iter = diagram.cbegin(); 463 464 for (const auto& it : score_with_topo) { 465 // GetSortedScoreWithTopology() contains the same chunks as the feerate 466 // diagram. We do not know where the chunk boundaries are, but we can 467 // check that there are points at which they match the cumulative fee 468 // and weight. 469 // The feerate diagram should never get behind the current transaction 470 // size totals. 471 assert(diagram_iter->size >= check_total_adjusted_weight); 472 if (diagram_iter->fee == check_total_modified_fee && 473 diagram_iter->size == check_total_adjusted_weight) { 474 ++diagram_iter; 475 } 476 checkTotal += it->GetTxSize(); 477 check_total_adjusted_weight += it->GetAdjustedWeight(); 478 check_total_fee += it->GetFee(); 479 check_total_modified_fee += it->GetModifiedFee(); 480 innerUsage += it->DynamicMemoryUsage(); 481 const CTransaction& tx = it->GetTx(); 482 483 // CompareMiningScoreWithTopology should agree with GetSortedScoreWithTopology() 484 if (last_wtxid) { 485 assert(CompareMiningScoreWithTopology(*last_wtxid, tx.GetWitnessHash())); 486 } 487 last_wtxid = tx.GetWitnessHash(); 488 489 std::set<CTxMemPoolEntry::CTxMemPoolEntryRef, CompareIteratorByHash> setParentCheck; 490 std::set<CTxMemPoolEntry::CTxMemPoolEntryRef, CompareIteratorByHash> setParentsStored; 491 for (const CTxIn &txin : tx.vin) { 492 // Check that every mempool transaction's inputs refer to available coins, or other mempool tx's. 493 indexed_transaction_set::const_iterator it2 = mapTx.find(txin.prevout.hash); 494 if (it2 != mapTx.end()) { 495 const CTransaction& tx2 = it2->GetTx(); 496 assert(tx2.vout.size() > txin.prevout.n && !tx2.vout[txin.prevout.n].IsNull()); 497 setParentCheck.insert(*it2); 498 } 499 // We are iterating through the mempool entries sorted 500 // topologically and by mining score. All parents must have been 501 // checked before their children and their coins added to the 502 // mempoolDuplicate coins cache. 503 assert(mempoolDuplicate.HaveCoin(txin.prevout)); 504 // Check whether its inputs are marked in mapNextTx. 505 auto it3 = mapNextTx.find(txin.prevout); 506 assert(it3 != mapNextTx.end()); 507 assert(it3->first == &txin.prevout); 508 assert(&it3->second->GetTx() == &tx); 509 } 510 auto comp = [](const CTxMemPoolEntry& a, const CTxMemPoolEntry& b) -> bool { 511 return a.GetTx().GetHash() == b.GetTx().GetHash(); 512 }; 513 for (auto &txentry : GetParents(*it)) { 514 setParentsStored.insert(dynamic_cast<const CTxMemPoolEntry&>(txentry.get())); 515 } 516 assert(setParentCheck.size() == setParentsStored.size()); 517 assert(std::equal(setParentCheck.begin(), setParentCheck.end(), setParentsStored.begin(), comp)); 518 519 // Check children against mapNextTx 520 std::set<CTxMemPoolEntry::CTxMemPoolEntryRef, CompareIteratorByHash> setChildrenCheck; 521 std::set<CTxMemPoolEntry::CTxMemPoolEntryRef, CompareIteratorByHash> setChildrenStored; 522 auto iter = mapNextTx.lower_bound(COutPoint(it->GetTx().GetHash(), 0)); 523 for (; iter != mapNextTx.end() && iter->first->hash == it->GetTx().GetHash(); ++iter) { 524 txiter childit = iter->second; 525 assert(childit != mapTx.end()); // mapNextTx points to in-mempool transactions 526 setChildrenCheck.insert(*childit); 527 } 528 for (auto &txentry : GetChildren(*it)) { 529 setChildrenStored.insert(dynamic_cast<const CTxMemPoolEntry&>(txentry.get())); 530 } 531 assert(setChildrenCheck.size() == setChildrenStored.size()); 532 assert(std::equal(setChildrenCheck.begin(), setChildrenCheck.end(), setChildrenStored.begin(), comp)); 533 534 TxValidationState dummy_state; // Not used. CheckTxInputs() should always pass 535 CAmount txfee = 0; 536 assert(!tx.IsCoinBase()); 537 assert(Consensus::CheckTxInputs(tx, dummy_state, mempoolDuplicate, spendheight, txfee)); 538 for (const auto& input: tx.vin) mempoolDuplicate.SpendCoin(input.prevout); 539 AddCoins(mempoolDuplicate, tx, std::numeric_limits<int>::max()); 540 } 541 for (auto it = mapNextTx.cbegin(); it != mapNextTx.cend(); it++) { 542 indexed_transaction_set::const_iterator it2 = it->second; 543 assert(it2 != mapTx.end()); 544 } 545 546 ++diagram_iter; 547 assert(diagram_iter == diagram.cend()); 548 549 assert(totalTxSize == checkTotal); 550 assert(m_total_fee == check_total_fee); 551 assert(diagram.back().fee == check_total_modified_fee); 552 assert(diagram.back().size == check_total_adjusted_weight); 553 assert(innerUsage == cachedInnerUsage); 554 } 555 556 bool CTxMemPool::CompareMiningScoreWithTopology(const Wtxid& hasha, const Wtxid& hashb) const 557 { 558 /* Return `true` if hasha should be considered sooner than hashb, namely when: 559 * a is not in the mempool but b is, or 560 * both are in the mempool but a is sorted before b in the total mempool ordering 561 * (which takes dependencies and (chunk) feerates into account). 562 */ 563 LOCK(cs); 564 auto j{GetIter(hashb)}; 565 if (!j.has_value()) return false; 566 auto i{GetIter(hasha)}; 567 if (!i.has_value()) return true; 568 569 return m_txgraph->CompareMainOrder(*i.value(), *j.value()) < 0; 570 } 571 572 std::vector<CTxMemPool::indexed_transaction_set::const_iterator> CTxMemPool::GetSortedScoreWithTopology() const 573 { 574 std::vector<indexed_transaction_set::const_iterator> iters; 575 AssertLockHeld(cs); 576 577 iters.reserve(mapTx.size()); 578 579 for (indexed_transaction_set::iterator mi = mapTx.begin(); mi != mapTx.end(); ++mi) { 580 iters.push_back(mi); 581 } 582 std::sort(iters.begin(), iters.end(), [this](const auto& a, const auto& b) EXCLUSIVE_LOCKS_REQUIRED(cs) noexcept { 583 return m_txgraph->CompareMainOrder(*a, *b) < 0; 584 }); 585 return iters; 586 } 587 588 std::vector<CTxMemPoolEntryRef> CTxMemPool::entryAll() const 589 { 590 AssertLockHeld(cs); 591 592 std::vector<CTxMemPoolEntryRef> ret; 593 ret.reserve(mapTx.size()); 594 for (const auto& it : GetSortedScoreWithTopology()) { 595 ret.emplace_back(*it); 596 } 597 return ret; 598 } 599 600 std::vector<TxMempoolInfo> CTxMemPool::infoAll() const 601 { 602 LOCK(cs); 603 auto iters = GetSortedScoreWithTopology(); 604 605 std::vector<TxMempoolInfo> ret; 606 ret.reserve(mapTx.size()); 607 for (auto it : iters) { 608 ret.push_back(GetInfo(it)); 609 } 610 611 return ret; 612 } 613 614 const CTxMemPoolEntry* CTxMemPool::GetEntry(const Txid& txid) const 615 { 616 AssertLockHeld(cs); 617 const auto i = mapTx.find(txid); 618 return i == mapTx.end() ? nullptr : &(*i); 619 } 620 621 CTransactionRef CTxMemPool::get(const Txid& hash) const 622 { 623 LOCK(cs); 624 indexed_transaction_set::const_iterator i = mapTx.find(hash); 625 if (i == mapTx.end()) 626 return nullptr; 627 return i->GetSharedTx(); 628 } 629 630 void CTxMemPool::PrioritiseTransaction(const Txid& hash, const CAmount& nFeeDelta) 631 { 632 { 633 LOCK(cs); 634 CAmount &delta = mapDeltas[hash]; 635 delta = SaturatingAdd(delta, nFeeDelta); 636 txiter it = mapTx.find(hash); 637 if (it != mapTx.end()) { 638 // PrioritiseTransaction calls stack on previous ones. Set the new 639 // transaction fee to be current modified fee + feedelta. 640 it->UpdateModifiedFee(nFeeDelta); 641 m_txgraph->SetTransactionFee(*it, it->GetModifiedFee()); 642 ++nTransactionsUpdated; 643 } 644 if (delta == 0) { 645 mapDeltas.erase(hash); 646 LogInfo("PrioritiseTransaction: %s (%sin mempool) delta cleared\n", hash.ToString(), it == mapTx.end() ? "not " : ""); 647 } else { 648 LogInfo("PrioritiseTransaction: %s (%sin mempool) fee += %s, new delta=%s\n", 649 hash.ToString(), 650 it == mapTx.end() ? "not " : "", 651 FormatMoney(nFeeDelta), 652 FormatMoney(delta)); 653 } 654 } 655 } 656 657 void CTxMemPool::ApplyDelta(const Txid& hash, CAmount &nFeeDelta) const 658 { 659 AssertLockHeld(cs); 660 std::map<Txid, CAmount>::const_iterator pos = mapDeltas.find(hash); 661 if (pos == mapDeltas.end()) 662 return; 663 const CAmount &delta = pos->second; 664 nFeeDelta += delta; 665 } 666 667 void CTxMemPool::ClearPrioritisation(const Txid& hash) 668 { 669 AssertLockHeld(cs); 670 mapDeltas.erase(hash); 671 } 672 673 std::vector<CTxMemPool::delta_info> CTxMemPool::GetPrioritisedTransactions() const 674 { 675 AssertLockNotHeld(cs); 676 LOCK(cs); 677 std::vector<delta_info> result; 678 result.reserve(mapDeltas.size()); 679 for (const auto& [txid, delta] : mapDeltas) { 680 const auto iter{mapTx.find(txid)}; 681 const bool in_mempool{iter != mapTx.end()}; 682 std::optional<CAmount> modified_fee; 683 if (in_mempool) modified_fee = iter->GetModifiedFee(); 684 result.emplace_back(delta_info{in_mempool, delta, modified_fee, txid}); 685 } 686 return result; 687 } 688 689 const CTransaction* CTxMemPool::GetConflictTx(const COutPoint& prevout) const 690 { 691 const auto it = mapNextTx.find(prevout); 692 return it == mapNextTx.end() ? nullptr : &(it->second->GetTx()); 693 } 694 695 std::optional<CTxMemPool::txiter> CTxMemPool::GetIter(const Txid& txid) const 696 { 697 AssertLockHeld(cs); 698 auto it = mapTx.find(txid); 699 return it != mapTx.end() ? std::make_optional(it) : std::nullopt; 700 } 701 702 std::optional<CTxMemPool::txiter> CTxMemPool::GetIter(const Wtxid& wtxid) const 703 { 704 AssertLockHeld(cs); 705 auto it{mapTx.project<0>(mapTx.get<index_by_wtxid>().find(wtxid))}; 706 return it != mapTx.end() ? std::make_optional(it) : std::nullopt; 707 } 708 709 CTxMemPool::setEntries CTxMemPool::GetIterSet(const std::set<Txid>& hashes) const 710 { 711 CTxMemPool::setEntries ret; 712 for (const auto& h : hashes) { 713 const auto mi = GetIter(h); 714 if (mi) ret.insert(*mi); 715 } 716 return ret; 717 } 718 719 std::vector<CTxMemPool::txiter> CTxMemPool::GetIterVec(const std::vector<Txid>& txids) const 720 { 721 AssertLockHeld(cs); 722 std::vector<txiter> ret; 723 ret.reserve(txids.size()); 724 for (const auto& txid : txids) { 725 const auto it{GetIter(txid)}; 726 if (!it) return {}; 727 ret.push_back(*it); 728 } 729 return ret; 730 } 731 732 bool CTxMemPool::HasNoInputsOf(const CTransaction &tx) const 733 { 734 for (unsigned int i = 0; i < tx.vin.size(); i++) 735 if (exists(tx.vin[i].prevout.hash)) 736 return false; 737 return true; 738 } 739 740 CCoinsViewMemPool::CCoinsViewMemPool(CCoinsView* baseIn, const CTxMemPool& mempoolIn) : CCoinsViewBacked(baseIn), mempool(mempoolIn) { } 741 742 std::optional<Coin> CCoinsViewMemPool::GetCoin(const COutPoint& outpoint) const 743 { 744 // Check to see if the inputs are made available by another tx in the package. 745 // These Coins would not be available in the underlying CoinsView. 746 if (auto it = m_temp_added.find(outpoint); it != m_temp_added.end()) { 747 return it->second; 748 } 749 750 // If an entry in the mempool exists, always return that one, as it's guaranteed to never 751 // conflict with the underlying cache, and it cannot have pruned entries (as it contains full) 752 // transactions. First checking the underlying cache risks returning a pruned entry instead. 753 CTransactionRef ptx = mempool.get(outpoint.hash); 754 if (ptx) { 755 if (outpoint.n < ptx->vout.size()) { 756 Coin coin(ptx->vout[outpoint.n], MEMPOOL_HEIGHT, false); 757 m_non_base_coins.emplace(outpoint); 758 return coin; 759 } 760 return std::nullopt; 761 } 762 return base->GetCoin(outpoint); 763 } 764 765 void CCoinsViewMemPool::PackageAddTransaction(const CTransactionRef& tx) 766 { 767 for (unsigned int n = 0; n < tx->vout.size(); ++n) { 768 m_temp_added.emplace(COutPoint(tx->GetHash(), n), Coin(tx->vout[n], MEMPOOL_HEIGHT, false)); 769 m_non_base_coins.emplace(tx->GetHash(), n); 770 } 771 } 772 void CCoinsViewMemPool::Reset() 773 { 774 m_temp_added.clear(); 775 m_non_base_coins.clear(); 776 } 777 778 size_t CTxMemPool::DynamicMemoryUsage() const { 779 LOCK(cs); 780 // Estimate the overhead of mapTx to be 9 pointers (3 pointers per index) + an allocation, as no exact formula for boost::multi_index_contained is implemented. 781 return memusage::MallocUsage(sizeof(CTxMemPoolEntry) + 9 * sizeof(void*)) * mapTx.size() + memusage::DynamicUsage(mapNextTx) + memusage::DynamicUsage(mapDeltas) + memusage::DynamicUsage(txns_randomized) + m_txgraph->GetMainMemoryUsage() + cachedInnerUsage; 782 } 783 784 void CTxMemPool::RemoveUnbroadcastTx(const Txid& txid, const bool unchecked) { 785 LOCK(cs); 786 787 if (m_unbroadcast_txids.erase(txid)) 788 { 789 LogDebug(BCLog::MEMPOOL, "Removed %s from set of unbroadcast txns%s", txid.GetHex(), (unchecked ? " before confirmation that txn was sent out" : "")); 790 } 791 } 792 793 void CTxMemPool::RemoveStaged(setEntries &stage, MemPoolRemovalReason reason) { 794 AssertLockHeld(cs); 795 for (txiter it : stage) { 796 removeUnchecked(it, reason); 797 } 798 } 799 800 bool CTxMemPool::CheckPolicyLimits(const CTransactionRef& tx) 801 { 802 LOCK(cs); 803 // Use ChangeSet interface to check whether the cluster count 804 // limits would be violated. Note that the changeset will be destroyed 805 // when it goes out of scope. 806 auto changeset = GetChangeSet(); 807 (void) changeset->StageAddition(tx, /*fee=*/0, /*time=*/0, /*entry_height=*/0, /*entry_sequence=*/0, /*spends_coinbase=*/false, /*sigops_cost=*/0, LockPoints{}); 808 return changeset->CheckMemPoolPolicyLimits(); 809 } 810 811 int CTxMemPool::Expire(std::chrono::seconds time) 812 { 813 AssertLockHeld(cs); 814 Assume(!m_have_changeset); 815 indexed_transaction_set::index<entry_time>::type::iterator it = mapTx.get<entry_time>().begin(); 816 setEntries toremove; 817 while (it != mapTx.get<entry_time>().end() && it->GetTime() < time) { 818 toremove.insert(mapTx.project<0>(it)); 819 it++; 820 } 821 setEntries stage; 822 for (txiter removeit : toremove) { 823 CalculateDescendants(removeit, stage); 824 } 825 RemoveStaged(stage, MemPoolRemovalReason::EXPIRY); 826 return stage.size(); 827 } 828 829 CFeeRate CTxMemPool::GetMinFee(size_t sizelimit) const { 830 LOCK(cs); 831 if (!blockSinceLastRollingFeeBump || rollingMinimumFeeRate == 0) 832 return CFeeRate(llround(rollingMinimumFeeRate)); 833 834 int64_t time = GetTime(); 835 if (time > lastRollingFeeUpdate + 10) { 836 double halflife = ROLLING_FEE_HALFLIFE; 837 if (DynamicMemoryUsage() < sizelimit / 4) 838 halflife /= 4; 839 else if (DynamicMemoryUsage() < sizelimit / 2) 840 halflife /= 2; 841 842 rollingMinimumFeeRate = rollingMinimumFeeRate / pow(2.0, (time - lastRollingFeeUpdate) / halflife); 843 lastRollingFeeUpdate = time; 844 845 if (rollingMinimumFeeRate < (double)m_opts.incremental_relay_feerate.GetFeePerK() / 2) { 846 rollingMinimumFeeRate = 0; 847 return CFeeRate(0); 848 } 849 } 850 return std::max(CFeeRate(llround(rollingMinimumFeeRate)), m_opts.incremental_relay_feerate); 851 } 852 853 void CTxMemPool::trackPackageRemoved(const CFeeRate& rate) { 854 AssertLockHeld(cs); 855 if (rate.GetFeePerK() > rollingMinimumFeeRate) { 856 rollingMinimumFeeRate = rate.GetFeePerK(); 857 blockSinceLastRollingFeeBump = false; 858 } 859 } 860 861 void CTxMemPool::TrimToSize(size_t sizelimit, std::vector<COutPoint>* pvNoSpendsRemaining) { 862 AssertLockHeld(cs); 863 Assume(!m_have_changeset); 864 865 unsigned nTxnRemoved = 0; 866 CFeeRate maxFeeRateRemoved(0); 867 868 while (!mapTx.empty() && DynamicMemoryUsage() > sizelimit) { 869 const auto &[worst_chunk, feeperweight] = m_txgraph->GetWorstMainChunk(); 870 FeePerVSize feerate = ToFeePerVSize(feeperweight); 871 CFeeRate removed{feerate.fee, feerate.size}; 872 873 // We set the new mempool min fee to the feerate of the removed set, plus the 874 // "minimum reasonable fee rate" (ie some value under which we consider txn 875 // to have 0 fee). This way, we don't allow txn to enter mempool with feerate 876 // equal to txn which were removed with no block in between. 877 removed += m_opts.incremental_relay_feerate; 878 trackPackageRemoved(removed); 879 maxFeeRateRemoved = std::max(maxFeeRateRemoved, removed); 880 881 nTxnRemoved += worst_chunk.size(); 882 883 std::vector<CTransaction> txn; 884 if (pvNoSpendsRemaining) { 885 txn.reserve(worst_chunk.size()); 886 for (auto ref : worst_chunk) { 887 txn.emplace_back(static_cast<const CTxMemPoolEntry&>(*ref).GetTx()); 888 } 889 } 890 891 setEntries stage; 892 for (auto ref : worst_chunk) { 893 stage.insert(mapTx.iterator_to(static_cast<const CTxMemPoolEntry&>(*ref))); 894 } 895 for (auto e : stage) { 896 removeUnchecked(e, MemPoolRemovalReason::SIZELIMIT); 897 } 898 if (pvNoSpendsRemaining) { 899 for (const CTransaction& tx : txn) { 900 for (const CTxIn& txin : tx.vin) { 901 if (exists(txin.prevout.hash)) continue; 902 pvNoSpendsRemaining->push_back(txin.prevout); 903 } 904 } 905 } 906 } 907 908 if (maxFeeRateRemoved > CFeeRate(0)) { 909 LogDebug(BCLog::MEMPOOL, "Removed %u txn, rolling minimum fee bumped to %s\n", nTxnRemoved, maxFeeRateRemoved.ToString()); 910 } 911 } 912 913 std::tuple<size_t, size_t, CAmount> CTxMemPool::CalculateAncestorData(const CTxMemPoolEntry& entry) const 914 { 915 auto ancestors = m_txgraph->GetAncestors(entry, TxGraph::Level::MAIN); 916 917 size_t ancestor_count = ancestors.size(); 918 size_t ancestor_size = 0; 919 CAmount ancestor_fees = 0; 920 for (auto tx: ancestors) { 921 const CTxMemPoolEntry& anc = static_cast<const CTxMemPoolEntry&>(*tx); 922 ancestor_size += anc.GetTxSize(); 923 ancestor_fees += anc.GetModifiedFee(); 924 } 925 return {ancestor_count, ancestor_size, ancestor_fees}; 926 } 927 928 std::tuple<size_t, size_t, CAmount> CTxMemPool::CalculateDescendantData(const CTxMemPoolEntry& entry) const 929 { 930 auto descendants = m_txgraph->GetDescendants(entry, TxGraph::Level::MAIN); 931 size_t descendant_count = descendants.size(); 932 size_t descendant_size = 0; 933 CAmount descendant_fees = 0; 934 935 for (auto tx: descendants) { 936 const CTxMemPoolEntry &desc = static_cast<const CTxMemPoolEntry&>(*tx); 937 descendant_size += desc.GetTxSize(); 938 descendant_fees += desc.GetModifiedFee(); 939 } 940 return {descendant_count, descendant_size, descendant_fees}; 941 } 942 943 void CTxMemPool::GetTransactionAncestry(const Txid& txid, size_t& ancestors, size_t& cluster_count, size_t* const ancestorsize, CAmount* const ancestorfees) const { 944 LOCK(cs); 945 auto it = mapTx.find(txid); 946 ancestors = cluster_count = 0; 947 if (it != mapTx.end()) { 948 auto [ancestor_count, ancestor_size, ancestor_fees] = CalculateAncestorData(*it); 949 ancestors = ancestor_count; 950 if (ancestorsize) *ancestorsize = ancestor_size; 951 if (ancestorfees) *ancestorfees = ancestor_fees; 952 cluster_count = m_txgraph->GetCluster(*it, TxGraph::Level::MAIN).size(); 953 } 954 } 955 956 bool CTxMemPool::GetLoadTried() const 957 { 958 LOCK(cs); 959 return m_load_tried; 960 } 961 962 void CTxMemPool::SetLoadTried(bool load_tried) 963 { 964 LOCK(cs); 965 m_load_tried = load_tried; 966 } 967 968 std::vector<CTxMemPool::txiter> CTxMemPool::GatherClusters(const std::vector<Txid>& txids) const 969 { 970 AssertLockHeld(cs); 971 972 std::vector<CTxMemPool::txiter> ret; 973 std::set<const CTxMemPoolEntry*> unique_cluster_representatives; 974 for (auto txid : txids) { 975 auto it = mapTx.find(txid); 976 if (it != mapTx.end()) { 977 // Note that TxGraph::GetCluster will return results in graph 978 // order, which is deterministic (as long as we are not modifying 979 // the graph). 980 auto cluster = m_txgraph->GetCluster(*it, TxGraph::Level::MAIN); 981 if (unique_cluster_representatives.insert(static_cast<const CTxMemPoolEntry*>(&(**cluster.begin()))).second) { 982 for (auto tx : cluster) { 983 ret.emplace_back(mapTx.iterator_to(static_cast<const CTxMemPoolEntry&>(*tx))); 984 } 985 } 986 } 987 } 988 if (ret.size() > 500) { 989 return {}; 990 } 991 return ret; 992 } 993 994 util::Result<std::pair<std::vector<FeeFrac>, std::vector<FeeFrac>>> CTxMemPool::ChangeSet::CalculateChunksForRBF() 995 { 996 LOCK(m_pool->cs); 997 998 if (!CheckMemPoolPolicyLimits()) { 999 return util::Error{Untranslated("cluster size limit exceeded")}; 1000 } 1001 1002 return m_pool->m_txgraph->GetMainStagingDiagrams(); 1003 } 1004 1005 CTxMemPool::ChangeSet::TxHandle CTxMemPool::ChangeSet::StageAddition(const CTransactionRef& tx, const CAmount fee, int64_t time, unsigned int entry_height, uint64_t entry_sequence, bool spends_coinbase, int64_t sigops_cost, LockPoints lp) 1006 { 1007 LOCK(m_pool->cs); 1008 Assume(m_to_add.find(tx->GetHash()) == m_to_add.end()); 1009 Assume(!m_dependencies_processed); 1010 1011 // We need to process dependencies after adding a new transaction. 1012 m_dependencies_processed = false; 1013 1014 CAmount delta{0}; 1015 m_pool->ApplyDelta(tx->GetHash(), delta); 1016 1017 FeePerWeight feerate(fee, GetSigOpsAdjustedWeight(GetTransactionWeight(*tx), sigops_cost, ::nBytesPerSigOp)); 1018 auto newit = m_to_add.emplace(tx, fee, time, entry_height, entry_sequence, spends_coinbase, sigops_cost, lp).first; 1019 m_pool->m_txgraph->AddTransaction(const_cast<CTxMemPoolEntry&>(*newit), feerate); 1020 if (delta) { 1021 newit->UpdateModifiedFee(delta); 1022 m_pool->m_txgraph->SetTransactionFee(*newit, newit->GetModifiedFee()); 1023 } 1024 1025 m_entry_vec.push_back(newit); 1026 1027 return newit; 1028 } 1029 1030 void CTxMemPool::ChangeSet::StageRemoval(CTxMemPool::txiter it) 1031 { 1032 LOCK(m_pool->cs); 1033 m_pool->m_txgraph->RemoveTransaction(*it); 1034 m_to_remove.insert(it); 1035 } 1036 1037 void CTxMemPool::ChangeSet::Apply() 1038 { 1039 LOCK(m_pool->cs); 1040 if (!m_dependencies_processed) { 1041 ProcessDependencies(); 1042 } 1043 m_pool->Apply(this); 1044 m_to_add.clear(); 1045 m_to_remove.clear(); 1046 m_entry_vec.clear(); 1047 m_ancestors.clear(); 1048 } 1049 1050 void CTxMemPool::ChangeSet::ProcessDependencies() 1051 { 1052 LOCK(m_pool->cs); 1053 Assume(!m_dependencies_processed); // should only call this once. 1054 for (const auto& entryptr : m_entry_vec) { 1055 for (const auto &txin : entryptr->GetSharedTx()->vin) { 1056 std::optional<txiter> piter = m_pool->GetIter(txin.prevout.hash); 1057 if (!piter) { 1058 auto it = m_to_add.find(txin.prevout.hash); 1059 if (it != m_to_add.end()) { 1060 piter = std::make_optional(it); 1061 } 1062 } 1063 if (piter) { 1064 m_pool->m_txgraph->AddDependency(/*parent=*/**piter, /*child=*/*entryptr); 1065 } 1066 } 1067 } 1068 m_dependencies_processed = true; 1069 return; 1070 } 1071 1072 bool CTxMemPool::ChangeSet::CheckMemPoolPolicyLimits() 1073 { 1074 LOCK(m_pool->cs); 1075 if (!m_dependencies_processed) { 1076 ProcessDependencies(); 1077 } 1078 1079 return !m_pool->m_txgraph->IsOversized(TxGraph::Level::TOP); 1080 } 1081 1082 std::vector<FeePerWeight> CTxMemPool::GetFeerateDiagram() const 1083 { 1084 FeePerWeight zero{}; 1085 std::vector<FeePerWeight> ret; 1086 1087 ret.emplace_back(zero); 1088 1089 StartBlockBuilding(); 1090 1091 std::vector<CTxMemPoolEntry::CTxMemPoolEntryRef> dummy; 1092 1093 FeePerWeight last_selection = GetBlockBuilderChunk(dummy); 1094 while (last_selection != FeePerWeight{}) { 1095 last_selection += ret.back(); 1096 ret.emplace_back(last_selection); 1097 IncludeBuilderChunk(); 1098 last_selection = GetBlockBuilderChunk(dummy); 1099 } 1100 StopBlockBuilding(); 1101 return ret; 1102 }