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
37TRACEPOINT_SEMAPHORE(mempool, added);
38TRACEPOINT_SEMAPHORE(mempool, removed);
39
40bool 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
57std::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
74std::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
91void 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
122bool 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
130CTxMemPool::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
166static 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
176CTxMemPool::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
190bool CTxMemPool::isSpent(const COutPoint& outpoint) const
191{
192    LOCK(cs);
193    return mapNextTx.count(outpoint);
194}
195
196unsigned int CTxMemPool::GetTransactionsUpdated() const
197{
198    return nTransactionsUpdated;
199}
200
201void CTxMemPool::AddTransactionsUpdated(unsigned int n)
202{
203    nTransactionsUpdated += n;
204}
205
206void 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
229void 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();