Branch data Line data Source code
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 : : #ifndef BITCOIN_TXMEMPOOL_H
7 : : #define BITCOIN_TXMEMPOOL_H
8 : :
9 : : #include <coins.h>
10 : : #include <consensus/amount.h>
11 : : #include <indirectmap.h>
12 : : #include <kernel/cs_main.h>
13 : : #include <kernel/mempool_entry.h> // IWYU pragma: export
14 : : #include <kernel/mempool_limits.h> // IWYU pragma: export
15 : : #include <kernel/mempool_options.h> // IWYU pragma: export
16 : : #include <kernel/mempool_removal_reason.h> // IWYU pragma: export
17 : : #include <policy/feerate.h>
18 : : #include <policy/packages.h>
19 : : #include <primitives/transaction.h>
20 : : #include <primitives/transaction_identifier.h>
21 : : #include <sync.h>
22 : : #include <txgraph.h>
23 : : #include <util/feefrac.h>
24 : : #include <util/hasher.h>
25 : : #include <util/not_null.h>
26 : : #include <util/result.h>
27 : :
28 : : #include <boost/multi_index/hashed_index.hpp>
29 : : #include <boost/multi_index/identity.hpp>
30 : : #include <boost/multi_index/indexed_by.hpp>
31 : : #include <boost/multi_index/ordered_index.hpp>
32 : : #include <boost/multi_index/sequenced_index.hpp>
33 : : #include <boost/multi_index/tag.hpp>
34 : : #include <boost/multi_index_container.hpp>
35 : :
36 : : #include <atomic>
37 : : #include <map>
38 : : #include <optional>
39 : : #include <set>
40 : : #include <string>
41 : : #include <string_view>
42 : : #include <utility>
43 : : #include <vector>
44 : :
45 : : class CChain;
46 : : class ValidationSignals;
47 : :
48 : : struct bilingual_str;
49 : :
50 : : /** Fake height value used in Coin to signify they are only in the memory pool (since 0.8) */
51 : : inline constexpr uint32_t MEMPOOL_HEIGHT = 0x7FFFFFFF;
52 : :
53 : : /** How much linearization cost required for TxGraph clusters to have
54 : : * "acceptable" quality, if they cannot be optimally linearized with less cost. */
55 : : inline constexpr uint64_t ACCEPTABLE_COST = 75'000;
56 : :
57 : : /** How much work we ask TxGraph to do after a mempool change occurs (either
58 : : * due to a changeset being applied, a new block being found, or a reorg). */
59 : : inline constexpr uint64_t POST_CHANGE_COST = 5 * ACCEPTABLE_COST;
60 : :
61 : : /**
62 : : * Test whether the LockPoints height and time are still valid on the current chain
63 : : */
64 : : bool TestLockPointValidity(CChain& active_chain, const LockPoints& lp) EXCLUSIVE_LOCKS_REQUIRED(cs_main);
65 : :
66 : : // extracts a transaction hash from CTxMemPoolEntry or CTransactionRef
67 : : struct mempoolentry_txid
68 : : {
69 : : typedef Txid result_type;
70 : 96789 : result_type operator() (const CTxMemPoolEntry &entry) const
71 : : {
72 [ + + ][ + - : 96789 : return entry.GetTx().GetHash();
+ + - - ]
73 : : }
74 : :
75 : : result_type operator() (const CTransactionRef& tx) const
76 : : {
77 : : return tx->GetHash();
78 : : }
79 : : };
80 : :
81 : : // extracts a transaction witness-hash from CTxMemPoolEntry or CTransactionRef
82 : : struct mempoolentry_wtxid
83 : : {
84 : : typedef Wtxid result_type;
85 : 78278 : result_type operator() (const CTxMemPoolEntry &entry) const
86 : : {
87 [ + + ]: 78278 : return entry.GetTx().GetWitnessHash();
[ + - - + ]
88 : : }
89 : :
90 : : result_type operator() (const CTransactionRef& tx) const
91 : : {
92 : : return tx->GetWitnessHash();
93 : : }
94 : : };
95 : :
96 : : class CompareTxMemPoolEntryByEntryTime
97 : : {
98 : : public:
99 : 408602 : bool operator()(const CTxMemPoolEntry& a, const CTxMemPoolEntry& b) const
100 : : {
101 : 408602 : return a.GetTime() < b.GetTime();
102 : : }
103 : : };
104 : :
105 : : // Multi_index tag names
106 : : struct entry_time {};
107 : : struct index_by_wtxid {};
108 : :
109 : : /**
110 : : * Information about a mempool transaction.
111 : : */
112 [ # # ][ # # : 0 : struct TxMempoolInfo
# # # # #
# ][ # # #
# # # ][ #
# # # #
# ]
113 : : {
114 : : /** The transaction itself */
115 : : CTransactionRef tx;
116 : :
117 : : /** Time the transaction entered the mempool. */
118 : : std::chrono::seconds m_time;
119 : :
120 : : /** Fee of the transaction. */
121 : : CAmount fee;
122 : :
123 : : /** Virtual size of the transaction. */
124 : : int32_t vsize;
125 : :
126 : : /** The fee delta. */
127 : : int64_t nFeeDelta;
128 : : };
129 : :
130 : : /**
131 : : * CTxMemPool stores valid-according-to-the-current-best-chain transactions
132 : : * that may be included in the next block.
133 : : *
134 : : * Transactions are added when they are seen on the network (or created by the
135 : : * local node), but not all transactions seen are added to the pool. For
136 : : * example, the following new transactions will not be added to the mempool:
137 : : * - a transaction which doesn't meet the minimum fee requirements.
138 : : * - a new transaction that double-spends an input of a transaction already in
139 : : * the pool where the new transaction does not meet the Replace-By-Fee
140 : : * requirements as defined in doc/policy/mempool-replacements.md.
141 : : * - a non-standard transaction.
142 : : *
143 : : * TxGraph (CTxMemPool::m_txgraph) provides an abstraction layer for separating
144 : : * the transaction graph parts of the mempool from the rest of the
145 : : * Bitcoin-specific logic. Specifically, TxGraph handles (for each transaction)
146 : : * managing the in-mempool parents and children, and has knowledge of the fee
147 : : * and size of every transaction. It uses this to partition the mempool into
148 : : * connected clusters, and it implements (among other things):
149 : : * - limits on the size of a cluster (in both number of transactions
150 : : * and total weight)
151 : : * - sorting the mempool optimally for block inclusion, taking into account
152 : : * dependencies
153 : : * - selecting transactions for removal due to cluster size limit violations
154 : : * after a reorg.
155 : : * See txgraph.h and txgraph.cpp for more details.
156 : : *
157 : : * CTxMemPool itself handles the Bitcoin-specific parts of mempool
158 : : * transactions; it stores the full transaction inside CTxMemPoolEntry, along
159 : : * with other consensus-specific fields (such as whether a transaction spends a
160 : : * coinbase, or the LockPoints for transaction finality). And it provides
161 : : * interfaces to the rest of the codebase, such as:
162 : : * - to validation for replace-by-fee calculations and cluster size limits
163 : : * when evaluating unconfirmed transactions
164 : : * - to validation for evicting transactions due to expiry or the mempool size
165 : : * limit being hit
166 : : * - to validation for updating the mempool to be consistent with the best
167 : : * chain after a new block is connected or after a reorg.
168 : : * - to net_processing for ordering transactions that are to-be-announced to
169 : : * other peers
170 : : * - to RPC code for inspecting the mempool
171 : : *
172 : : * (Many of these interfaces are just wrappers around corresponding TxGraph
173 : : * functions.)
174 : : *
175 : : * Within CTxMemPool, the mempool entries are stored in a boost::multi_index
176 : : * mapTx, which sorts the mempool on 3 criteria:
177 : : * - transaction hash (txid)
178 : : * - witness-transaction hash (wtxid)
179 : : * - time in mempool
180 : : *
181 : : * We also maintain a map from COutPoint to the (in-mempool) transaction that
182 : : * spends it (mapNextTx). This allows us to recover from a reorg and find
183 : : * transactions in the mempool that conflict with transactions that are
184 : : * confirmed in a block.
185 : : *
186 : : */
187 : : class CTxMemPool
188 : : {
189 : : protected:
190 : : std::atomic<unsigned int> nTransactionsUpdated{0}; //!< Used by getblocktemplate to trigger CreateNewBlock() invocation
191 : :
192 : : uint64_t totalTxSize GUARDED_BY(cs){0}; //!< sum of all mempool tx's virtual sizes. Differs from serialized tx size since witness data is discounted. Defined in BIP 141.
193 : : CAmount m_total_fee GUARDED_BY(cs){0}; //!< sum of all mempool tx's fees (NOT modified fee)
194 : : uint64_t cachedInnerUsage GUARDED_BY(cs){0}; //!< sum of dynamic memory usage of all the map elements (NOT the maps themselves)
195 : :
196 : : mutable int64_t lastRollingFeeUpdate GUARDED_BY(cs){GetTime()};
197 : : mutable bool blockSinceLastRollingFeeBump GUARDED_BY(cs){false};
198 : : mutable double rollingMinimumFeeRate GUARDED_BY(cs){0}; //!< minimum fee to get into the pool, decreases exponentially
199 : :
200 : : // In-memory counter for external mempool tracking purposes.
201 : : // This number is incremented once every time a transaction
202 : : // is added or removed from the mempool for any reason.
203 : : mutable uint64_t m_sequence_number GUARDED_BY(cs){1};
204 : :
205 : : void trackPackageRemoved(const CFeeRate& rate) EXCLUSIVE_LOCKS_REQUIRED(cs);
206 : :
207 : : bool m_load_tried GUARDED_BY(cs){false};
208 : :
209 : : CFeeRate GetMinFee(size_t sizelimit) const;
210 : :
211 : : public:
212 : :
213 : : static constexpr int ROLLING_FEE_HALFLIFE{60 * 60 * 12}; // public only for testing
214 : :
215 : : using indexed_transaction_set = boost::multi_index_container<
216 : : CTxMemPoolEntry,
217 : : boost::multi_index::indexed_by<
218 : : // sorted by txid
219 : : boost::multi_index::hashed_unique<mempoolentry_txid, SaltedTxidHasher>,
220 : : // sorted by wtxid
221 : : boost::multi_index::hashed_unique<
222 : : boost::multi_index::tag<index_by_wtxid>,
223 : : mempoolentry_wtxid,
224 : : SaltedWtxidHasher
225 : : >,
226 : : // sorted by entry time
227 : : boost::multi_index::ordered_non_unique<
228 : : boost::multi_index::tag<entry_time>,
229 : : boost::multi_index::identity<CTxMemPoolEntry>,
230 : : CompareTxMemPoolEntryByEntryTime
231 : : >
232 : : >
233 : : >;
234 : :
235 : : /**
236 : : * This mutex needs to be locked when accessing `mapTx` or other members
237 : : * that are guarded by it.
238 : : *
239 : : * @par Consistency guarantees
240 : : * By design, it is guaranteed that:
241 : : * 1. Locking both `cs_main` and `mempool.cs` will give a view of mempool
242 : : * that is consistent with current chain tip (`ActiveChain()` and
243 : : * `CoinsTip()`) and is fully populated. Fully populated means that if the
244 : : * current active chain is missing transactions that were present in a
245 : : * previously active chain, all the missing transactions will have been
246 : : * re-added to the mempool and should be present if they meet size and
247 : : * consistency constraints.
248 : : * 2. Locking `mempool.cs` without `cs_main` will give a view of a mempool
249 : : * consistent with some chain that was active since `cs_main` was last
250 : : * locked, and that is fully populated as described above. It is ok for
251 : : * code that only needs to query or remove transactions from the mempool
252 : : * to lock just `mempool.cs` without `cs_main`.
253 : : *
254 : : * To provide these guarantees, it is necessary to lock both `cs_main` and
255 : : * `mempool.cs` whenever adding transactions to the mempool and whenever
256 : : * changing the chain tip. It's necessary to keep both mutexes locked until
257 : : * the mempool is consistent with the new chain tip and fully populated.
258 : : */
259 : : mutable RecursiveMutex cs ACQUIRED_AFTER(::cs_main);
260 : : std::unique_ptr<TxGraph> m_txgraph GUARDED_BY(cs);
261 : : mutable std::unique_ptr<TxGraph::BlockBuilder> m_builder GUARDED_BY(cs);
262 : : indexed_transaction_set mapTx GUARDED_BY(cs);
263 : :
264 : : using txiter = indexed_transaction_set::nth_index<0>::type::const_iterator;
265 : : std::vector<std::pair<Wtxid, txiter>> txns_randomized GUARDED_BY(cs); //!< All transactions in mapTx with their wtxids, in arbitrary order
266 : :
267 : : typedef std::set<txiter, CompareIteratorByHash> setEntries;
268 : :
269 : : using Limits = kernel::MemPoolLimits;
270 : :
271 : : std::tuple<size_t, size_t, CAmount> CalculateAncestorData(const CTxMemPoolEntry& entry) const EXCLUSIVE_LOCKS_REQUIRED(cs);
272 : : std::tuple<size_t, size_t, CAmount> CalculateDescendantData(const CTxMemPoolEntry& entry) const EXCLUSIVE_LOCKS_REQUIRED(cs);
273 [ - + + - ]: 1 : int64_t GetDescendantCount(txiter it) const { LOCK(cs); return m_txgraph->GetDescendants(*it, TxGraph::Level::MAIN).size(); }
274 [ - + + - ]: 11 : int64_t GetDescendantCount(const CTxMemPoolEntry &e) const { LOCK(cs); return m_txgraph->GetDescendants(e, TxGraph::Level::MAIN).size(); }
275 [ - + + - ]: 12 : int64_t GetAncestorCount(const CTxMemPoolEntry &e) const { LOCK(cs); return m_txgraph->GetAncestors(e, TxGraph::Level::MAIN).size(); }
276 : : std::vector<CTxMemPoolEntry::CTxMemPoolEntryRef> GetChildren(const CTxMemPoolEntry &entry) const;
277 : : std::vector<CTxMemPoolEntry::CTxMemPoolEntryRef> GetParents(const CTxMemPoolEntry &entry) const;
278 : :
279 : : private:
280 : : std::vector<indexed_transaction_set::const_iterator> GetSortedScoreWithTopology() const EXCLUSIVE_LOCKS_REQUIRED(cs);
281 : :
282 : : /**
283 : : * Track locally submitted transactions to periodically retry initial broadcast.
284 : : */
285 : : std::set<Txid> m_unbroadcast_txids GUARDED_BY(cs);
286 : :
287 : 0 : static TxMempoolInfo GetInfo(CTxMemPool::indexed_transaction_set::const_iterator it)
288 : : {
289 [ # # # # : 0 : return TxMempoolInfo{it->GetSharedTx(), it->GetTime(), it->GetFee(), it->GetTxSize(), it->GetModifiedFee() - it->GetFee()};
# # ]
290 : : }
291 : :
292 : : // Helper to remove all transactions that conflict with a given
293 : : // transaction (used for transactions appearing in a block).
294 : : void removeConflicts(const CTransaction& tx) EXCLUSIVE_LOCKS_REQUIRED(cs);
295 : :
296 : : public:
297 : : indirectmap<COutPoint, txiter> mapNextTx GUARDED_BY(cs);
298 : : std::map<Txid, CAmount> mapDeltas GUARDED_BY(cs);
299 : :
300 : : using Options = kernel::MemPoolOptions;
301 : :
302 : : const Options m_opts;
303 : :
304 : : /** Create a new CTxMemPool.
305 : : * Sanity checks will be off by default for performance, because otherwise
306 : : * accepting transactions becomes O(N^2) where N is the number of transactions
307 : : * in the pool.
308 : : */
309 : : explicit CTxMemPool(Options opts, bilingual_str& error);
310 : :
311 : : /**
312 : : * If sanity-checking is turned on, check makes sure the pool is
313 : : * consistent (does not contain two transactions that spend the same inputs,
314 : : * all inputs are in the mapNextTx array). If sanity-checking is turned off,
315 : : * check does nothing.
316 : : */
317 : : void check(const CCoinsViewCache& active_coins_tip, int64_t spendheight) const EXCLUSIVE_LOCKS_REQUIRED(::cs_main);
318 : :
319 : : /**
320 : : * Remove a transaction from the mempool along with any descendants.
321 : : * If the transaction is not already in the mempool, find any descendants
322 : : * and remove them.
323 : : */
324 : : void removeRecursive(const CTransaction& tx, MemPoolRemovalReason reason) EXCLUSIVE_LOCKS_REQUIRED(cs);
325 : : /** After reorg, filter the entries that would no longer be valid in the next block, and update
326 : : * the entries' cached LockPoints if needed. The mempool does not have any knowledge of
327 : : * consensus rules. It just applies the callable function and removes the ones for which it
328 : : * returns true.
329 : : * @param[in] filter_final_and_mature Predicate that checks the relevant validation rules
330 : : * and updates an entry's LockPoints.
331 : : * */
332 : : void removeForReorg(CChain& chain, std::function<bool(txiter)> filter_final_and_mature) EXCLUSIVE_LOCKS_REQUIRED(cs, cs_main);
333 : : std::vector<RemovedMempoolTransactionInfo> removeForBlock(const std::vector<CTransactionRef>& vtx) EXCLUSIVE_LOCKS_REQUIRED(cs);
334 : :
335 : : /** Look up wtxids in the mempool and (partially) sort by mining score.
336 : : *
337 : : * The @p n_to_sort best entries are removed from @p wtxids and their
338 : : * corresponding txiter entries are returned. In addition wtxids
339 : : * that are duplicates or were not found in the mempool are silently
340 : : * dropped from @p wtxids. The returned vector is ordered from best
341 : : * to worst (by CompareMainOrder). Entries remaining in @p wtxids
342 : : * are in unspecified order.
343 : : *
344 : : * Note that the returned `txiter` values may become invalidated once
345 : : * mempool.cs is released.
346 : : */
347 : : std::vector<txiter> ExtractBestByMiningScoreWithTopology(std::vector<Wtxid>& wtxids, size_t n_to_sort) const EXCLUSIVE_LOCKS_REQUIRED(cs);
348 : : bool isSpent(const COutPoint& outpoint) const;
349 : : unsigned int GetTransactionsUpdated() const;
350 : : void AddTransactionsUpdated(unsigned int n);
351 : : /**
352 : : * Check that none of this transactions inputs are in the mempool, and thus
353 : : * the tx is not dependent on other mempool transactions to be included in a block.
354 : : */
355 : : bool HasNoInputsOf(const CTransaction& tx) const EXCLUSIVE_LOCKS_REQUIRED(cs);
356 : :
357 : : /** Affect CreateNewBlock prioritisation of transactions */
358 : : void PrioritiseTransaction(const Txid& hash, const CAmount& nFeeDelta);
359 : : void ApplyDelta(const Txid& hash, CAmount &nFeeDelta) const EXCLUSIVE_LOCKS_REQUIRED(cs);
360 : : void ClearPrioritisation(const Txid& hash) EXCLUSIVE_LOCKS_REQUIRED(cs);
361 : :
362 : : struct delta_info {
363 : : /** Whether this transaction is in the mempool. */
364 : : const bool in_mempool;
365 : : /** The fee delta added using PrioritiseTransaction(). */
366 : : const CAmount delta;
367 : : /** The modified fee (base fee + delta) of this entry. Only present if in_mempool=true. */
368 : : std::optional<CAmount> modified_fee;
369 : : /** The prioritised transaction's txid. */
370 : : const Txid txid;
371 : : };
372 : : /** Return a vector of all entries in mapDeltas with their corresponding delta_info. */
373 : : std::vector<delta_info> GetPrioritisedTransactions() const EXCLUSIVE_LOCKS_REQUIRED(!cs);
374 : :
375 : : /** Get the transaction in the pool that spends the same prevout */
376 : : const CTransaction* GetConflictTx(const COutPoint& prevout) const EXCLUSIVE_LOCKS_REQUIRED(cs);
377 : :
378 : : /** Returns an iterator to the given hash, if found */
379 : : std::optional<txiter> GetIter(const Txid& txid) const EXCLUSIVE_LOCKS_REQUIRED(cs);
380 : : std::optional<txiter> GetIter(const Wtxid& wtxid) const EXCLUSIVE_LOCKS_REQUIRED(cs);
381 : :
382 : : /** Translate a set of hashes into a set of pool iterators to avoid repeated lookups.
383 : : * Does not require that all of the hashes correspond to actual transactions in the mempool,
384 : : * only returns the ones that exist. */
385 : : setEntries GetIterSet(const std::set<Txid>& hashes) const EXCLUSIVE_LOCKS_REQUIRED(cs);
386 : :
387 : : /** Translate a list of hashes into a list of mempool iterators to avoid repeated lookups.
388 : : * The nth element in txids becomes the nth element in the returned vector. If any of the txids
389 : : * don't actually exist in the mempool, returns an empty vector. */
390 : : std::vector<txiter> GetIterVec(const std::vector<Txid>& txids) const EXCLUSIVE_LOCKS_REQUIRED(cs);
391 : :
392 : : /** UpdateTransactionsFromBlock is called when adding transactions from a
393 : : * disconnected block back to the mempool, new mempool entries may have
394 : : * children in the mempool (which is generally not the case when otherwise
395 : : * adding transactions).
396 : : * @post updated descendant state for descendants of each transaction in
397 : : * vHashesToUpdate (excluding any child transactions present in
398 : : * vHashesToUpdate, which are already accounted for). Updated state
399 : : * includes add fee/size information for such descendants to the
400 : : * parent and updated ancestor state to include the parent.
401 : : *
402 : : * @param[in] vHashesToUpdate The set of txids from the
403 : : * disconnected block that have been accepted back into the mempool.
404 : : */
405 : : void UpdateTransactionsFromBlock(const std::vector<Txid>& vHashesToUpdate) EXCLUSIVE_LOCKS_REQUIRED(cs, cs_main);
406 : :
407 : : std::vector<FeePerWeight> GetFeerateDiagram() const EXCLUSIVE_LOCKS_REQUIRED(cs);
408 : 0 : FeePerWeight GetMainChunkFeerate(const CTxMemPoolEntry& tx) const EXCLUSIVE_LOCKS_REQUIRED(cs) {
409 : 0 : return m_txgraph->GetMainChunkFeerate(tx);
410 : : }
411 : 0 : std::vector<const CTxMemPoolEntry*> GetCluster(Txid txid) const EXCLUSIVE_LOCKS_REQUIRED(cs) {
412 : 0 : auto tx = GetIter(txid);
413 [ # # ]: 0 : if (!tx) return {};
414 : 0 : auto cluster = m_txgraph->GetCluster(**tx, TxGraph::Level::MAIN);
415 : 0 : std::vector<const CTxMemPoolEntry*> ret;
416 [ # # # # ]: 0 : ret.reserve(cluster.size());
417 [ # # ]: 0 : for (const auto& tx : cluster) {
418 [ # # ]: 0 : ret.emplace_back(static_cast<const CTxMemPoolEntry*>(tx));
419 : : }
420 : 0 : return ret;
421 : 0 : }
422 : :
423 : :
424 : 13 : size_t GetUniqueClusterCount(const setEntries& iters_conflicting) const EXCLUSIVE_LOCKS_REQUIRED(cs) {
425 : 13 : std::vector<const TxGraph::Ref *> entries;
426 [ + - ]: 13 : entries.reserve(iters_conflicting.size());
427 [ + + ]: 329 : for (auto it : iters_conflicting) {
428 [ + - ]: 316 : entries.emplace_back(&*it);
429 : : }
430 [ - + ]: 13 : Assume(!m_txgraph->IsOversized(TxGraph::Level::MAIN));
431 [ - + ]: 13 : return m_txgraph->CountDistinctClusters(entries, TxGraph::Level::MAIN);
432 : 13 : }
433 : :
434 : : /**
435 : : * Calculate all in-mempool ancestors of entry (not including the tx itself)
436 : : *
437 : : * @param[in] entry CTxMemPoolEntry of which all in-mempool ancestors are calculated
438 : : *
439 : : * @return all in-mempool ancestors
440 : : */
441 : : setEntries CalculateMemPoolAncestors(const CTxMemPoolEntry& entry) const EXCLUSIVE_LOCKS_REQUIRED(cs);
442 : :
443 : : bool HasDescendants(const Txid& txid) const;
444 : :
445 : : /** Collect the entire cluster of connected transactions for each transaction in txids.
446 : : * All txids must correspond to transaction entries in the mempool, otherwise this returns an
447 : : * empty vector. This call will also exit early and return an empty vector if it collects 500 or
448 : : * more transactions as a DoS protection. */
449 : : std::vector<txiter> GatherClusters(const std::vector<Txid>& txids) const EXCLUSIVE_LOCKS_REQUIRED(cs);
450 : :
451 : : /** Populate setDescendants with all in-mempool descendants of given transaction.
452 : : * Assumes that setDescendants includes all in-mempool descendants of anything
453 : : * already in it. */
454 : : void CalculateDescendants(txiter it, setEntries& setDescendants) const EXCLUSIVE_LOCKS_REQUIRED(cs);
455 : : CTxMemPool::txiter CalculateDescendants(const CTxMemPoolEntry& entry, setEntries& setDescendants) const EXCLUSIVE_LOCKS_REQUIRED(cs);
456 : :
457 : : /** The minimum fee to get into the mempool, which may itself not be enough
458 : : * for larger-sized transactions.
459 : : * The m_incremental_relay_feerate policy variable is used to bound the time it
460 : : * takes the fee rate to go back down all the way to 0. When the feerate
461 : : * would otherwise be half of this, it is set to 0 instead.
462 : : */
463 : 152 : CFeeRate GetMinFee() const {
464 [ + - ][ + - : 152 : return GetMinFee(m_opts.max_size_bytes);
+ - + - +
- ]
465 : : }
466 : :
467 : : /** Remove transactions from the mempool until its dynamic size is <= sizelimit.
468 : : * pvNoSpendsRemaining, if set, will be populated with the list of outpoints
469 : : * which are not in mempool which no longer have any spends in this mempool.
470 : : */
471 : : void TrimToSize(size_t sizelimit, std::vector<COutPoint>* pvNoSpendsRemaining = nullptr) EXCLUSIVE_LOCKS_REQUIRED(cs);
472 : :
473 : : /** Expire all transaction (and their dependencies) in the mempool older than time. Return the number of removed transactions. */
474 : : int Expire(std::chrono::seconds time) EXCLUSIVE_LOCKS_REQUIRED(cs);
475 : :
476 : : /**
477 : : * Calculate the ancestor and cluster count for the given transaction.
478 : : * The counts include the transaction itself.
479 : : * When ancestors is non-zero (ie, the transaction itself is in the mempool),
480 : : * ancestorsize and ancestorfees will also be set to the appropriate values.
481 : : */
482 : : void GetTransactionAncestry(const Txid& txid, size_t& ancestors, size_t& cluster_count, size_t* ancestorsize = nullptr, CAmount* ancestorfees = nullptr) const;
483 : :
484 : : /**
485 : : * @returns true if an initial attempt to load the persisted mempool was made, regardless of
486 : : * whether the attempt was successful or not
487 : : */
488 : : bool GetLoadTried() const;
489 : :
490 : : /**
491 : : * Set whether or not an initial attempt to load the persisted mempool was made (regardless
492 : : * of whether the attempt was successful or not)
493 : : */
494 : : void SetLoadTried(bool load_tried);
495 : :
496 : 5299323 : unsigned long size() const
497 : : {
498 : 5299323 : LOCK(cs);
499 [ + - ]: 5299323 : return mapTx.size();
500 : 5299323 : }
501 : :
502 : 16941 : uint64_t GetTotalTxSize() const EXCLUSIVE_LOCKS_REQUIRED(cs)
503 : : {
504 : 16941 : AssertLockHeld(cs);
505 [ + - + + : 16941 : return totalTxSize;
+ + + + +
+ ][ # # ]
506 : : }
507 : :
508 : 0 : CAmount GetTotalFee() const EXCLUSIVE_LOCKS_REQUIRED(cs)
509 : : {
510 : 0 : AssertLockHeld(cs);
511 [ # # ]: 0 : return m_total_fee;
512 : : }
513 : :
514 : 981 : bool exists(const Txid& txid) const
515 : : {
516 : 981 : LOCK(cs);
517 [ + - ]: 981 : return (mapTx.count(txid) != 0);
518 : 981 : }
519 : :
520 : 255 : bool exists(const Wtxid& wtxid) const
521 : : {
522 : 255 : LOCK(cs);
523 [ + - ]: 255 : return (mapTx.get<index_by_wtxid>().count(wtxid) != 0);
524 : 255 : }
525 : :
526 : : const CTxMemPoolEntry* GetEntry(const Txid& txid) const LIFETIMEBOUND EXCLUSIVE_LOCKS_REQUIRED(cs);
527 : :
528 : : /**
529 : : * Return a mempool transaction with a given hash.
530 : : *
531 : : * @param[in] hash the txid
532 : : * @returns the tx if found, otherwise nullptr
533 : : */
534 : : CTransactionRef get(const Txid& hash) const;
535 : :
536 : : /**
537 : : * Return a mempool transaction with a given witness hash.
538 : : *
539 : : * @param[in] hash the wtxid
540 : : * @returns the tx if found, otherwise nullptr
541 : : */
542 : : CTransactionRef get(const Wtxid& hash) const;
543 : :
544 : : template <TxidOrWtxid T>
545 : 0 : TxMempoolInfo info(const T& id) const
546 : : {
547 : 0 : LOCK(cs);
548 [ # # ]: 0 : auto i{GetIter(id)};
549 [ # # # # ]: 0 : return i.has_value() ? GetInfo(*i) : TxMempoolInfo{};
550 : 0 : }
551 : :
552 : : /** Returns info for a transaction if its entry_sequence < last_sequence */
553 : : template <TxidOrWtxid T>
554 : 0 : TxMempoolInfo info_for_relay(const T& id, uint64_t last_sequence) const
555 : : {
556 : 0 : LOCK(cs);
557 [ # # ]: 0 : auto i{GetIter(id)};
558 [ # # # # : 0 : return (i.has_value() && i.value()->GetSequence() < last_sequence) ? GetInfo(*i) : TxMempoolInfo{};
# # ]
559 : 0 : }
560 : :
561 : : std::vector<CTxMemPoolEntryRef> entryAll() const EXCLUSIVE_LOCKS_REQUIRED(cs);
562 : : std::vector<TxMempoolInfo> infoAll() const;
563 : :
564 : : size_t DynamicMemoryUsage() const;
565 : :
566 : : /** Adds a transaction to the unbroadcast set */
567 : 1 : void AddUnbroadcastTx(const Txid& txid)
568 : : {
569 : 1 : LOCK(cs);
570 : : // Sanity check the transaction is in the mempool & insert into
571 : : // unbroadcast set.
572 [ + - + - : 1 : if (exists(txid)) m_unbroadcast_txids.insert(txid);
+ - ]
573 : 1 : };
574 : :
575 : : bool CheckPolicyLimits(const CTransactionRef& tx);
576 : :
577 : : /** Removes a transaction from the unbroadcast set */
578 : : void RemoveUnbroadcastTx(const Txid& txid, bool unchecked = false);
579 : :
580 : : /** Returns a copy of the unbroadcast txid set */
581 : 1 : std::set<Txid> GetUnbroadcastTxs() const
582 : : {
583 : 1 : LOCK(cs);
584 [ + - + - ]: 1 : return m_unbroadcast_txids;
585 : 1 : }
586 : :
587 : 0 : size_t GetUnbroadcastTxCount() const
588 : : {
589 : 0 : LOCK(cs);
590 [ # # ]: 0 : return m_unbroadcast_txids.size();
591 : 0 : }
592 : :
593 : : /** Returns whether a txid is in the unbroadcast set */
594 : 0 : bool IsUnbroadcastTx(const Txid& txid) const EXCLUSIVE_LOCKS_REQUIRED(cs)
595 : : {
596 : 0 : AssertLockHeld(cs);
597 : 0 : return m_unbroadcast_txids.contains(txid);
598 : : }
599 : :
600 : : /** Guards this internal counter for external reporting */
601 : 222 : uint64_t GetAndIncrementSequence() const EXCLUSIVE_LOCKS_REQUIRED(cs) {
602 [ + - + - ]: 222 : return m_sequence_number++;
[ + + # # ]
603 : : }
604 : :
605 : 142 : uint64_t GetSequence() const EXCLUSIVE_LOCKS_REQUIRED(cs) {
606 [ # # ]: 142 : return m_sequence_number;
607 : : }
608 : :
609 : : private:
610 : : /** Remove a set of transactions from the mempool.
611 : : * If a transaction is in this set, then all in-mempool descendants must
612 : : * also be in the set, unless this transaction is being removed for being
613 : : * in a block.
614 : : */
615 : : void RemoveStaged(setEntries& stage, MemPoolRemovalReason reason) EXCLUSIVE_LOCKS_REQUIRED(cs);
616 : :
617 : : /* Helper for the public removeRecursive() */
618 : : void removeRecursive(txiter to_remove, MemPoolRemovalReason reason) EXCLUSIVE_LOCKS_REQUIRED(cs);
619 : :
620 : : /* Removal from the mempool also triggers removal of the entry's Ref from txgraph. */
621 : : void removeUnchecked(txiter entry, MemPoolRemovalReason reason) EXCLUSIVE_LOCKS_REQUIRED(cs);
622 : : public:
623 : : /*
624 : : * CTxMemPool::ChangeSet:
625 : : *
626 : : * This class is used for all mempool additions and associated removals (eg
627 : : * due to rbf). Removals that don't need to be evaluated for acceptance,
628 : : * such as removing transactions that appear in a block, or due to reorg,
629 : : * or removals related to mempool limiting or expiry do not need to use
630 : : * this.
631 : : *
632 : : * Callers can interleave calls to StageAddition()/StageRemoval(), and
633 : : * removals may be invoked in any order, but additions must be done in a
634 : : * topological order in the case of transaction packages (ie, parents must
635 : : * be added before children).
636 : : *
637 : : * CalculateChunksForRBF() can be used to calculate the feerate diagram of
638 : : * the proposed set of new transactions and compare with the existing
639 : : * mempool.
640 : : *
641 : : * CalculateMemPoolAncestors() calculates the in-mempool (not including
642 : : * what is in the change set itself) ancestors of a given transaction.
643 : : *
644 : : * Apply() will apply the removals and additions that are staged into the
645 : : * mempool.
646 : : *
647 : : * Only one changeset may exist at a time. While a changeset is
648 : : * outstanding, no removals or additions may be made directly to the
649 : : * mempool.
650 : : */
651 : : class ChangeSet {
652 : : public:
653 : 19079 : explicit ChangeSet(CTxMemPool* pool) : m_pool(pool) { m_pool->m_txgraph->StartStaging(); }
654 : 19079 : ~ChangeSet() EXCLUSIVE_LOCKS_REQUIRED(m_pool->cs) {
655 : 19079 : AssertLockHeld(m_pool->cs);
656 [ + + ]: 19079 : if (m_pool->m_txgraph->HaveStaging()) {
657 : 48 : m_pool->m_txgraph->AbortStaging();
658 : : }
659 : 19079 : m_pool->m_have_changeset = false;
660 : 19079 : }
661 : :
662 : : ChangeSet(const ChangeSet&) = delete;
663 : : ChangeSet& operator=(const ChangeSet&) = delete;
664 : :
665 : : using TxHandle = CTxMemPool::txiter;
666 : :
667 : : TxHandle StageAddition(const CTransactionRef& tx, CAmount fee, int64_t time, unsigned int entry_height, uint64_t entry_sequence, bool spends_coinbase, int64_t sigops_cost, LockPoints lp);
668 : :
669 : : void StageRemoval(CTxMemPool::txiter it);
670 : :
671 [ + + ]: 113 : const CTxMemPool::setEntries& GetRemovals() const { return m_to_remove; }
672 : :
673 : : /** Check if any cluster limits are exceeded. Returns true if pass, false if fail. */
674 : : bool CheckMemPoolPolicyLimits();
675 : :
676 : 2 : CTxMemPool::setEntries CalculateMemPoolAncestors(TxHandle tx)
677 : : {
678 : : // Look up transaction in our cache first
679 : 2 : auto it = m_ancestors.find(tx);
680 [ - + ]: 2 : if (it != m_ancestors.end()) return it->second;
681 : :
682 : : // If not found, try to have the mempool calculate it, and cache
683 : : // for later.
684 : 2 : LOCK(m_pool->cs);
685 [ + - ]: 2 : auto ret = m_pool->CalculateMemPoolAncestors(*tx);
686 [ + - ]: 2 : m_ancestors.try_emplace(tx, ret);
687 : 2 : return ret;
688 [ + - ]: 4 : }
689 : :
690 : 4 : std::vector<CTransactionRef> GetAddedTxns() const {
691 : 4 : std::vector<CTransactionRef> ret;
692 [ - + + - ]: 4 : ret.reserve(m_entry_vec.size());
693 [ + + ]: 12 : for (const auto& entry : m_entry_vec) {
694 [ + - + - ]: 24 : ret.emplace_back(entry->GetSharedTx());
695 : : }
696 : 4 : return ret;
697 : 0 : }
698 : :
699 : : /**
700 : : * Calculate the sorted chunks for the old and new mempool relating to the
701 : : * clusters that would be affected by a potential replacement transaction.
702 : : *
703 : : * @return old and new diagram pair respectively, or an error string if the conflicts don't match a calculable topology
704 : : */
705 : : util::Result<std::pair<std::vector<FeeFrac>, std::vector<FeeFrac>>> CalculateChunksForRBF();
706 : :
707 [ - + + + : 11 : size_t GetTxCount() const { return m_entry_vec.size(); }
- + + - ]
708 [ + - + - ]: 3 : const CTransaction& GetAddedTxn(size_t index) const { return m_entry_vec.at(index)->GetTx(); }
709 : :
710 : : void Apply() EXCLUSIVE_LOCKS_REQUIRED(cs_main);
711 : :
712 : : private:
713 : : void ProcessDependencies();
714 : :
715 : : CTxMemPool* m_pool;
716 : : CTxMemPool::indexed_transaction_set m_to_add;
717 : : std::vector<CTxMemPool::txiter> m_entry_vec; // track the added transactions' insertion order
718 : : // map from the m_to_add index to the ancestors for the transaction
719 : : std::map<CTxMemPool::txiter, CTxMemPool::setEntries, CompareIteratorByHash> m_ancestors;
720 : : CTxMemPool::setEntries m_to_remove;
721 : : bool m_dependencies_processed{false};
722 : :
723 : : friend class CTxMemPool;
724 : : };
725 : :
726 : 19079 : util::NotNullUniquePtr<ChangeSet> GetChangeSet() EXCLUSIVE_LOCKS_REQUIRED(cs)
727 : : {
728 : 19079 : Assume(!m_have_changeset);
729 : 19079 : m_have_changeset = true;
730 : 19079 : return util::NotNull{std::make_unique<ChangeSet>(this)};
731 : : }
732 : :
733 : : bool m_have_changeset GUARDED_BY(cs){false};
734 : :
735 : : friend class CTxMemPool::ChangeSet;
736 : :
737 : : private:
738 : : // Apply the given changeset to the mempool, by removing transactions in
739 : : // the to_remove set and adding transactions in the to_add set.
740 : : void Apply(CTxMemPool::ChangeSet* changeset) EXCLUSIVE_LOCKS_REQUIRED(cs);
741 : :
742 : : // addNewTransaction must update state for all ancestors of a given transaction,
743 : : // to track size/count of descendant transactions. First version of
744 : : // addNewTransaction can be used to have it call CalculateMemPoolAncestors(), and
745 : : // then invoke the second version.
746 : : // Note that addNewTransaction is ONLY called (via Apply()) from ATMP
747 : : // outside of tests and any other callers may break wallet's in-mempool
748 : : // tracking (due to lack of CValidationInterface::TransactionAddedToMempool
749 : : // callbacks).
750 : : void addNewTransaction(CTxMemPool::txiter it) EXCLUSIVE_LOCKS_REQUIRED(cs);
751 : : public:
752 [ - + ]: 10306 : void StartBlockBuilding() const EXCLUSIVE_LOCKS_REQUIRED(cs) { assert(!m_builder); m_builder = m_txgraph->GetBlockBuilder(); }
753 : 52407 : FeePerWeight GetBlockBuilderChunk(std::vector<CTxMemPoolEntry::CTxMemPoolEntryRef>& entries) const EXCLUSIVE_LOCKS_REQUIRED(cs)
754 : : {
755 [ - + ]: 52407 : if (!m_builder) { return {}; }
756 : :
757 : 52407 : auto res = m_builder->GetCurrentChunk();
758 [ + + ]: 52407 : if (!res) { return {}; }
759 : :
760 [ + - ]: 42104 : auto [chunk_entries, chunk_feerate] = *res;
761 [ + + ]: 84278 : for (TxGraph::Ref* ref : chunk_entries) {
762 [ + - ]: 42174 : entries.emplace_back(static_cast<const CTxMemPoolEntry&>(*ref));
763 : : }
764 : 42104 : return chunk_feerate;
765 : 94511 : }
766 : 41257 : void IncludeBuilderChunk() const EXCLUSIVE_LOCKS_REQUIRED(cs) { m_builder->Include(); }
767 : 844 : void SkipBuilderChunk() const EXCLUSIVE_LOCKS_REQUIRED(cs) { m_builder->Skip(); }
768 [ + - ]: 10306 : void StopBlockBuilding() const EXCLUSIVE_LOCKS_REQUIRED(cs) { m_builder.reset(); }
769 : : };
770 : :
771 : : /**
772 : : * CCoinsView that brings transactions from a mempool into view.
773 : : * It does not check for spendings by memory pool transactions.
774 : : * Instead, it provides access to all Coins which are either unspent in the
775 : : * base CCoinsView, are outputs from any mempool transaction, or are
776 : : * tracked temporarily to allow transaction dependencies in package validation.
777 : : * This allows transaction replacement to work as expected, as you want to
778 : : * have all inputs "available" to check signatures, and any cycles in the
779 : : * dependency graph are checked directly in AcceptToMemoryPool.
780 : : * It also allows you to sign a double-spend directly in
781 : : * signrawtransactionwithkey and signrawtransactionwithwallet,
782 : : * as long as the conflicting transaction is not yet confirmed.
783 : : */
784 : : class CCoinsViewMemPool : public CCoinsViewBacked
785 : : {
786 : : /**
787 : : * Coins made available by transactions being validated. Tracking these allows for package
788 : : * validation, since we can access transaction outputs without submitting them to mempool.
789 : : */
790 : : std::unordered_map<COutPoint, Coin, SaltedOutpointHasher> m_temp_added;
791 : :
792 : : /**
793 : : * Set of all coins that have been fetched from mempool or created using PackageAddTransaction
794 : : * (not base). Used to track the origin of a coin, see GetNonBaseCoins().
795 : : */
796 : : mutable std::unordered_set<COutPoint, SaltedOutpointHasher> m_non_base_coins;
797 : : protected:
798 : : const CTxMemPool& mempool;
799 : :
800 : : public:
801 : : CCoinsViewMemPool(CCoinsView* baseIn, const CTxMemPool& mempoolIn);
802 : : /** GetCoin, returning whether it exists and is not spent. Also updates m_non_base_coins if the
803 : : * coin is not fetched from base. May populate the base view on cache misses. */
804 : : std::optional<Coin> GetCoin(const COutPoint& outpoint) const override;
805 : : /** Add the coins created by this transaction. These coins are only temporarily stored in
806 : : * m_temp_added and cannot be flushed to the back end. Only used for package validation. */
807 : : void PackageAddTransaction(const CTransactionRef& tx);
808 : : /** Get all coins in m_non_base_coins. */
809 : 267 : const std::unordered_set<COutPoint, SaltedOutpointHasher>& GetNonBaseCoins() const { return m_non_base_coins; }
810 : : /** Clear m_temp_added and m_non_base_coins. */
811 : : void Reset();
812 : : };
813 : : #endif // BITCOIN_TXMEMPOOL_H
|
