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