Maintaining pending transactions

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
263void 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.
309void CTxMemPool::CalculateDescendants(txiter entryit, setEntries& setDescendants) const
310{
311    (void)CalculateDescendants(*entryit, setDescendants);
312    return;
313}
314
315CTxMemPool::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
323void 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
333void 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
360void 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
388void 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
405std::vector<RemovedMempoolTransactionInfo> CTxMemPool::removeForBlock(const std::vector<CTransactionRef>& vtx)
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    lastRollingFeeUpdate = GetTime();
424    blockSinceLastRollingFeeBump = true;
425    if (!m_txgraph->DoWork(/*max_cost=*/POST_CHANGE_COST)) {
426        LogDebug(BCLog::MEMPOOL, "Mempool in non-optimal ordering after block.");
427    }
428    return txs_removed_for_block;
429}
430
431void CTxMemPool::check(const CCoinsViewCache& active_coins_tip, int64_t spendheight) const
432{
433    if (m_opts.check_ratio == 0) return;
434
435    if (FastRandomContext().randrange(m_opts.check_ratio) >= 1) return;
436
437    AssertLockHeld(::cs_main);
438    LOCK(cs);
439    LogDebug(BCLog::MEMPOOL, "Checking mempool with %u transactions and %u inputs\n", (unsigned int)mapTx.size(), (unsigned int)mapNextTx.size());
440
441    uint64_t checkTotal = 0;
442    CAmount check_total_fee{0};
443    CAmount check_total_modified_fee{0};
444    int64_t check_total_adjusted_weight{0};
445    uint64_t innerUsage = 0;
446
447    assert(!m_txgraph->IsOversized(TxGraph::Level::MAIN));
448    m_txgraph->SanityCheck();
449
450    CCoinsViewCache mempoolDuplicate(const_cast<CCoinsViewCache*>(&active_coins_tip));
451
452    const auto score_with_topo{GetSortedScoreWithTopology()};
453
454    // Number of chunks is bounded by number of transactions.
455    const auto diagram{GetFeerateDiagram()};
456    assert(diagram.size() <= score_with_topo.size() + 1);
457    assert(diagram.size() >= 1);
458
459    std::optional<txiter> last_iter = std::nullopt;
460    auto diagram_iter = diagram.cbegin();
461
462    for (const auto& it : score_with_topo) {
463        // GetSortedScoreWithTopology() contains the same chunks as the feerate
464        // diagram. We do not know where the chunk boundaries are, but we can
465        // check that there are points at which they match the cumulative fee
466        // and weight.
467        // The feerate diagram should never get behind the current transaction
468        // size totals.
469        assert(diagram_iter->size >= check_total_adjusted_weight);
470        if (diagram_iter->fee == check_total_modified_fee &&
471                diagram_iter->size == check_total_adjusted_weight) {
472            ++diagram_iter;
473        }
474        checkTotal += it->GetTxSize();
475        check_total_adjusted_weight += it->GetAdjustedWeight();
476        check_total_fee += it->GetFee();
477        check_total_modified_fee += it->GetModifiedFee();
478        innerUsage += it->DynamicMemoryUsage();
479        const CTransaction& tx = it->GetTx();
480
481        if (last_iter) {
482            assert(m_txgraph->CompareMainOrder(**last_iter, *it) < 0);
483        }
484        last_iter = it;
485
486        std::set<CTxMemPoolEntry::CTxMemPoolEntryRef, CompareIteratorByHash> setParentCheck;
487        std::set<CTxMemPoolEntry::CTxMemPoolEntryRef, CompareIteratorByHash> setParentsStored;
488        for (const CTxIn &txin : tx.vin) {
489            // Check that every mempool transaction's inputs refer to available coins, or other mempool tx's.
490            indexed_transaction_set::const_iterator it2 = mapTx.find(txin.prevout.hash);
491            if (it2 != mapTx.end()) {
492                const CTransaction& tx2 = it2->GetTx();
493                assert(tx2.vout.size() > txin.prevout.n && !tx2.vout[txin.prevout.n].IsNull());
494                setParentCheck.insert(*it2);
495            }
496            // We are iterating through the mempool entries sorted
497            // topologically and by mining score. All parents must have been
498            // checked before their children and their coins added to the
499            // mempoolDuplicate coins cache.
500            assert(mempoolDuplicate.HaveCoin(txin.prevout));