Line data Source code
1 : // Copyright (c) 2009-2010 Satoshi Nakamoto
2 : // Copyright (c) 2009-2021 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 <atomic>
10 : #include <map>
11 : #include <optional>
12 : #include <set>
13 : #include <string>
14 : #include <utility>
15 : #include <vector>
16 :
17 : #include <coins.h>
18 : #include <consensus/amount.h>
19 : #include <evo/netinfo.h>
20 : #include <gsl/pointers.h>
21 : #include <index/addressindex_types.h>
22 : #include <index/spentindex_types.h>
23 : #include <indirectmap.h>
24 : #include <netaddress.h>
25 : #include <policy/feerate.h>
26 : #include <policy/packages.h>
27 : #include <primitives/transaction.h>
28 : #include <pubkey.h>
29 : #include <random.h>
30 : #include <sync.h>
31 : #include <util/epochguard.h>
32 : #include <util/hasher.h>
33 :
34 : #include <boost/multi_index/hashed_index.hpp>
35 : #include <boost/multi_index/identity.hpp>
36 : #include <boost/multi_index/indexed_by.hpp>
37 : #include <boost/multi_index/ordered_index.hpp>
38 : #include <boost/multi_index/sequenced_index.hpp>
39 : #include <boost/multi_index/tag.hpp>
40 : #include <boost/multi_index_container.hpp>
41 :
42 : class CBlockIndex;
43 : class CChain;
44 : class CChainState;
45 : extern RecursiveMutex cs_main; // NOLINT(readability-redundant-declaration)
46 :
47 : // Forward declaration for CBLSLazyPublicKey:
48 : template<typename T> class CBLSLazyWrapper;
49 : class CBLSPublicKey;
50 : using CBLSLazyPublicKey = CBLSLazyWrapper<CBLSPublicKey>;
51 :
52 : /** Fake height value used in Coin to signify they are only in the memory pool (since 0.8) */
53 : static const uint32_t MEMPOOL_HEIGHT = 0x7FFFFFFF;
54 :
55 174 : struct LockPoints {
56 : // Will be set to the blockchain height and median time past
57 : // values that would be necessary to satisfy all relative locktime
58 : // constraints (BIP68) of this tx given our view of block chain history
59 174 : int height{0};
60 174 : int64_t time{0};
61 : // As long as the current chain descends from the highest height block
62 : // containing one of the inputs used in the calculation, then the cached
63 : // values are still valid even after a reorg.
64 174 : CBlockIndex* maxInputBlock{nullptr};
65 : };
66 :
67 : /**
68 : * Test whether the LockPoints height and time are still valid on the current chain
69 : */
70 : bool TestLockPointValidity(CChain& active_chain, const LockPoints& lp) EXCLUSIVE_LOCKS_REQUIRED(cs_main);
71 :
72 : struct CompareIteratorByHash {
73 : // SFINAE for T where T is either a pointer type (e.g., a txiter) or a reference_wrapper<T>
74 : // (e.g. a wrapped CTxMemPoolEntry&)
75 : template <typename T>
76 2052330 : bool operator()(const std::reference_wrapper<T>& a, const std::reference_wrapper<T>& b) const
77 : {
78 2052330 : return a.get().GetTx().GetHash() < b.get().GetTx().GetHash();
79 : }
80 : template <typename T>
81 63533400 : bool operator()(const T& a, const T& b) const
82 : {
83 63533400 : return a->GetTx().GetHash() < b->GetTx().GetHash();
84 : }
85 : };
86 : /** \class CTxMemPoolEntry
87 : *
88 : * CTxMemPoolEntry stores data about the corresponding transaction, as well
89 : * as data about all in-mempool transactions that depend on the transaction
90 : * ("descendant" transactions).
91 : *
92 : * When a new entry is added to the mempool, we update the descendant state
93 : * (nCountWithDescendants, nSizeWithDescendants, and nModFeesWithDescendants) for
94 : * all ancestors of the newly added transaction.
95 : *
96 : */
97 :
98 : class CTxMemPoolEntry
99 : {
100 : public:
101 : typedef std::reference_wrapper<const CTxMemPoolEntry> CTxMemPoolEntryRef;
102 : // two aliases, should the types ever diverge
103 : typedef std::set<CTxMemPoolEntryRef, CompareIteratorByHash> Parents;
104 : typedef std::set<CTxMemPoolEntryRef, CompareIteratorByHash> Children;
105 :
106 : private:
107 53808 : CTxMemPoolEntry(const CTxMemPoolEntry&) = default;
108 : struct ExplicitCopyTag {
109 : explicit ExplicitCopyTag() = default;
110 : };
111 : const CTransactionRef tx;
112 : mutable Parents m_parents;
113 : mutable Children m_children;
114 : const CAmount nFee; //!< Cached to avoid expensive parent-transaction lookups
115 : const size_t nTxSize; //!< ... and avoid recomputing tx size
116 : const size_t nUsageSize; //!< ... and total memory usage
117 : const int64_t nTime; //!< Local time when entering the mempool
118 : const unsigned int entryHeight; //!< Chain height when entering the mempool
119 : const bool spendsCoinbase; //!< keep track of transactions that spend a coinbase
120 : const int64_t sigOpCount; //!< Legacy sig ops plus P2SH sig op count
121 : CAmount m_modified_fee; //!< Used for determining the priority of the transaction for mining in a block
122 : LockPoints lockPoints; //!< Track the height and time at which tx was final
123 :
124 : // Information about descendants of this transaction that are in the
125 : // mempool; if we remove this transaction we must remove all of these
126 : // descendants as well.
127 : uint64_t nCountWithDescendants{1}; //!< number of descendant transactions
128 : uint64_t nSizeWithDescendants; //!< ... and size
129 : CAmount nModFeesWithDescendants; //!< ... and total fees (all including us)
130 :
131 : // Analogous statistics for ancestor transactions
132 : uint64_t nCountWithAncestors{1};
133 : uint64_t nSizeWithAncestors;
134 : CAmount nModFeesWithAncestors;
135 : int64_t nSigOpCountWithAncestors;
136 :
137 : public:
138 : CTxMemPoolEntry(const CTransactionRef& tx, CAmount fee,
139 : int64_t time, unsigned int entry_height,
140 : bool spends_coinbase,
141 : int64_t sigops_count, LockPoints lp);
142 :
143 26904 : CTxMemPoolEntry(ExplicitCopyTag, const CTxMemPoolEntry& entry) : CTxMemPoolEntry(entry) {}
144 : CTxMemPoolEntry& operator=(const CTxMemPoolEntry&) = delete;
145 : CTxMemPoolEntry(CTxMemPoolEntry&&) = delete;
146 : CTxMemPoolEntry& operator=(CTxMemPoolEntry&&) = delete;
147 :
148 : static constexpr ExplicitCopyTag ExplicitCopy{};
149 141393995 : const CTransaction& GetTx() const { return *this->tx; }
150 26759 : CTransactionRef GetSharedTx() const { return this->tx; }
151 138756 : const CAmount& GetFee() const { return nFee; }
152 : size_t GetTxSize() const;
153 30688273 : std::chrono::seconds GetTime() const { return std::chrono::seconds{nTime}; }
154 51459 : unsigned int GetHeight() const { return entryHeight; }
155 1769975 : int64_t GetSigOpCount() const { return sigOpCount; }
156 69759243 : CAmount GetModifiedFee() const { return m_modified_fee; }
157 52377 : size_t DynamicMemoryUsage() const { return nUsageSize; }
158 6 : const LockPoints& GetLockPoints() const { return lockPoints; }
159 :
160 : // Adjusts the descendant state.
161 : void UpdateDescendantState(int64_t modifySize, CAmount modifyFee, int64_t modifyCount);
162 : // Adjusts the ancestor state
163 : void UpdateAncestorState(int64_t modifySize, CAmount modifyFee, int64_t modifyCount, int64_t modifySigOps);
164 : // Updates the modified fees with descendants/ancestors.
165 : void UpdateModifiedFee(CAmount newFeeDelta);
166 : // Update the LockPoints after a reorg
167 : void UpdateLockPoints(const LockPoints& lp);
168 :
169 1026136 : uint64_t GetCountWithDescendants() const { return nCountWithDescendants; }
170 27599519 : uint64_t GetSizeWithDescendants() const { return nSizeWithDescendants; }
171 26572641 : CAmount GetModFeesWithDescendants() const { return nModFeesWithDescendants; }
172 :
173 3 : bool GetSpendsCoinbase() const { return spendsCoinbase; }
174 :
175 79797 : uint64_t GetCountWithAncestors() const { return nCountWithAncestors; }
176 4442461 : uint64_t GetSizeWithAncestors() const { return nSizeWithAncestors; }
177 4442461 : CAmount GetModFeesWithAncestors() const { return nModFeesWithAncestors; }
178 2131 : int64_t GetSigOpCountWithAncestors() const { return nSigOpCountWithAncestors; }
179 :
180 1129664 : const Parents& GetMemPoolParentsConst() const { return m_parents; }
181 1079470 : const Children& GetMemPoolChildrenConst() const { return m_children; }
182 2182 : Parents& GetMemPoolParents() const { return m_parents; }
183 2202 : Children& GetMemPoolChildren() const { return m_children; }
184 :
185 : mutable size_t vTxHashesIdx; //!< Index in mempool's vTxHashes
186 :
187 : // If this is a proTx, this will be the hash of the key for which this ProTx was valid
188 : mutable uint256 validForProTxKey;
189 : mutable bool isKeyChangeProTx{false};
190 : mutable Epoch::Marker m_epoch_marker; //!< epoch when last touched, useful for graph algorithms
191 : };
192 :
193 : // extracts a transaction hash from CTxMemPoolEntry or CTransactionRef
194 : struct mempoolentry_txid
195 : {
196 : typedef uint256 result_type;
197 2813634 : result_type operator() (const CTxMemPoolEntry &entry) const
198 : {
199 2813634 : return entry.GetTx().GetHash();
200 : }
201 :
202 1559 : result_type operator() (const CTransactionRef& tx) const
203 : {
204 1559 : return tx->GetHash();
205 : }
206 : };
207 :
208 : /** \class CompareTxMemPoolEntryByDescendantScore
209 : *
210 : * Sort an entry by max(score/size of entry's tx, score/size with all descendants).
211 : */
212 : class CompareTxMemPoolEntryByDescendantScore
213 : {
214 : public:
215 13286242 : bool operator()(const CTxMemPoolEntry& a, const CTxMemPoolEntry& b) const
216 : {
217 : double a_mod_fee, a_size, b_mod_fee, b_size;
218 :
219 13286242 : GetModFeeAndSize(a, a_mod_fee, a_size);
220 13286242 : GetModFeeAndSize(b, b_mod_fee, b_size);
221 :
222 : // Avoid division by rewriting (a/b > c/d) as (a*d > c*b).
223 13286242 : double f1 = a_mod_fee * b_size;
224 13286242 : double f2 = a_size * b_mod_fee;
225 :
226 13286242 : if (f1 == f2) {
227 13097618 : return a.GetTime() >= b.GetTime();
228 : }
229 188624 : return f1 < f2;
230 13286242 : }
231 :
232 : // Return the fee/size we're using for sorting this entry.
233 26572484 : void GetModFeeAndSize(const CTxMemPoolEntry &a, double &mod_fee, double &size) const
234 : {
235 : // Compare feerate with descendants to feerate of the transaction, and
236 : // return the fee/size for the max.
237 26572484 : double f1 = (double)a.GetModifiedFee() * a.GetSizeWithDescendants();
238 26572484 : double f2 = (double)a.GetModFeesWithDescendants() * a.GetTxSize();
239 :
240 26572484 : if (f2 > f1) {
241 151 : mod_fee = a.GetModFeesWithDescendants();
242 151 : size = a.GetSizeWithDescendants();
243 151 : } else {
244 26572333 : mod_fee = a.GetModifiedFee();
245 26572333 : size = a.GetTxSize();
246 : }
247 26572484 : }
248 : };
249 :
250 : /** \class CompareTxMemPoolEntryByScore
251 : *
252 : * Sort by feerate of entry (fee/size) in descending order
253 : * This is only used for transaction relay, so we use GetFee()
254 : * instead of GetModifiedFee() to avoid leaking prioritization
255 : * information via the sort order.
256 : */
257 : class CompareTxMemPoolEntryByScore
258 : {
259 : public:
260 3138 : bool operator()(const CTxMemPoolEntry& a, const CTxMemPoolEntry& b) const
261 : {
262 3138 : double f1 = (double)a.GetFee() * b.GetTxSize();
263 3138 : double f2 = (double)b.GetFee() * a.GetTxSize();
264 3138 : if (f1 == f2) {
265 3138 : return b.GetTx().GetHash() < a.GetTx().GetHash();
266 : }
267 0 : return f1 > f2;
268 3138 : }
269 : };
270 :
271 : class CompareTxMemPoolEntryByEntryTime
272 : {
273 : public:
274 2246480 : bool operator()(const CTxMemPoolEntry& a, const CTxMemPoolEntry& b) const
275 : {
276 2246480 : return a.GetTime() < b.GetTime();
277 : }
278 : };
279 :
280 : /** \class CompareTxMemPoolEntryByAncestorScore
281 : *
282 : * Sort an entry by min(score/size of entry's tx, score/size with all ancestors).
283 : */
284 : class CompareTxMemPoolEntryByAncestorFee
285 : {
286 : public:
287 : template<typename T>
288 3692522 : bool operator()(const T& a, const T& b) const
289 : {
290 : double a_mod_fee, a_size, b_mod_fee, b_size;
291 :
292 3692522 : GetModFeeAndSize(a, a_mod_fee, a_size);
293 3692522 : GetModFeeAndSize(b, b_mod_fee, b_size);
294 :
295 : // Avoid division by rewriting (a/b > c/d) as (a*d > c*b).
296 3692522 : double f1 = a_mod_fee * b_size;
297 3692522 : double f2 = a_size * b_mod_fee;
298 :
299 3692522 : if (f1 == f2) {
300 3579299 : return a.GetTx().GetHash() < b.GetTx().GetHash();
301 : }
302 113223 : return f1 > f2;
303 3692522 : }
304 :
305 : // Return the fee/size we're using for sorting this entry.
306 : template <typename T>
307 7385044 : void GetModFeeAndSize(const T &a, double &mod_fee, double &size) const
308 : {
309 : // Compare feerate with ancestors to feerate of the transaction, and
310 : // return the fee/size for the min.
311 7385044 : double f1 = (double)a.GetModifiedFee() * a.GetSizeWithAncestors();
312 7385044 : double f2 = (double)a.GetModFeesWithAncestors() * a.GetTxSize();
313 :
314 7385044 : if (f1 > f2) {
315 76 : mod_fee = a.GetModFeesWithAncestors();
316 76 : size = a.GetSizeWithAncestors();
317 76 : } else {
318 7384968 : mod_fee = a.GetModifiedFee();
319 7384968 : size = a.GetTxSize();
320 : }
321 7385044 : }
322 : };
323 :
324 : // Multi_index tag names
325 : struct descendant_score {};
326 : struct entry_time {};
327 : struct ancestor_score {};
328 :
329 : class CBlockPolicyEstimator;
330 : class CDeterministicMNManager;
331 :
332 : namespace llmq {
333 : class CInstantSendManager;
334 : };
335 :
336 : /**
337 : * Information about a mempool transaction.
338 : */
339 : struct TxMempoolInfo
340 : {
341 : /** The transaction itself */
342 : CTransactionRef tx;
343 :
344 : /** Time the transaction entered the mempool. */
345 : std::chrono::seconds m_time;
346 :
347 : /** Fee of the transaction. */
348 : CAmount fee;
349 :
350 : /** Virtual size of the transaction. */
351 : size_t vsize;
352 :
353 : /** The fee delta. */
354 : int64_t nFeeDelta;
355 : };
356 :
357 : /** Reason why a transaction was removed from the mempool,
358 : * this is passed to the notification signal.
359 : */
360 : enum class MemPoolRemovalReason {
361 : EXPIRY, //!< Expired from mempool
362 : SIZELIMIT, //!< Removed in size limiting
363 : REORG, //!< Removed for reorganization
364 : BLOCK, //!< Removed for block
365 : CONFLICT, //!< Removed for conflict with in-block transaction
366 : MANUAL //!< Removed manually
367 : };
368 :
369 : std::string RemovalReasonToString(const MemPoolRemovalReason& r) noexcept;
370 :
371 : /**
372 : * CTxMemPool stores valid-according-to-the-current-best-chain transactions
373 : * that may be included in the next block.
374 : *
375 : * Transactions are added when they are seen on the network (or created by the
376 : * local node), but not all transactions seen are added to the pool. For
377 : * example, the following new transactions will not be added to the mempool:
378 : * - a transaction which doesn't meet the minimum fee requirements.
379 : * - a new transaction that double-spends an input of a transaction already in
380 : * the pool.
381 : * - a non-standard transaction.
382 : *
383 : * CTxMemPool::mapTx, and CTxMemPoolEntry bookkeeping:
384 : *
385 : * mapTx is a boost::multi_index that sorts the mempool on 4 criteria:
386 : * - transaction hash
387 : * - descendant feerate [we use max(feerate of tx, feerate of tx with all descendants)]
388 : * - time in mempool
389 : * - ancestor feerate [we use min(feerate of tx, feerate of tx with all unconfirmed ancestors)]
390 : *
391 : * Note: the term "descendant" refers to in-mempool transactions that depend on
392 : * this one, while "ancestor" refers to in-mempool transactions that a given
393 : * transaction depends on.
394 : *
395 : * In order for the feerate sort to remain correct, we must update transactions
396 : * in the mempool when new descendants arrive. To facilitate this, we track
397 : * the set of in-mempool direct parents and direct children in mapLinks. Within
398 : * each CTxMemPoolEntry, we track the size and fees of all descendants.
399 : *
400 : * Usually when a new transaction is added to the mempool, it has no in-mempool
401 : * children (because any such children would be an orphan). So in
402 : * addUnchecked(), we:
403 : * - update a new entry's setMemPoolParents to include all in-mempool parents
404 : * - update the new entry's direct parents to include the new tx as a child
405 : * - update all ancestors of the transaction to include the new tx's size/fee
406 : *
407 : * When a transaction is removed from the mempool, we must:
408 : * - update all in-mempool parents to not track the tx in setMemPoolChildren
409 : * - update all ancestors to not include the tx's size/fees in descendant state
410 : * - update all in-mempool children to not include it as a parent
411 : *
412 : * These happen in UpdateForRemoveFromMempool(). (Note that when removing a
413 : * transaction along with its descendants, we must calculate that set of
414 : * transactions to be removed before doing the removal, or else the mempool can
415 : * be in an inconsistent state where it's impossible to walk the ancestors of
416 : * a transaction.)
417 : *
418 : * In the event of a reorg, the assumption that a newly added tx has no
419 : * in-mempool children is false. In particular, the mempool is in an
420 : * inconsistent state while new transactions are being added, because there may
421 : * be descendant transactions of a tx coming from a disconnected block that are
422 : * unreachable from just looking at transactions in the mempool (the linking
423 : * transactions may also be in the disconnected block, waiting to be added).
424 : * Because of this, there's not much benefit in trying to search for in-mempool
425 : * children in addUnchecked(). Instead, in the special case of transactions
426 : * being added from a disconnected block, we require the caller to clean up the
427 : * state, to account for in-mempool, out-of-block descendants for all the
428 : * in-block transactions by calling UpdateTransactionsFromBlock(). Note that
429 : * until this is called, the mempool state is not consistent, and in particular
430 : * mapLinks may not be correct (and therefore functions like
431 : * CalculateMemPoolAncestors() and CalculateDescendants() that rely
432 : * on them to walk the mempool are not generally safe to use).
433 : *
434 : * Computational limits:
435 : *
436 : * Updating all in-mempool ancestors of a newly added transaction can be slow,
437 : * if no bound exists on how many in-mempool ancestors there may be.
438 : * CalculateMemPoolAncestors() takes configurable limits that are designed to
439 : * prevent these calculations from being too CPU intensive.
440 : *
441 : */
442 : class CTxMemPool
443 : {
444 : protected:
445 : const int m_check_ratio; //!< Value n means that 1 times in n we check.
446 : std::atomic<unsigned int> nTransactionsUpdated{0}; //!< Used by getblocktemplate to trigger CreateNewBlock() invocation
447 : CBlockPolicyEstimator* const minerPolicyEstimator;
448 : std::atomic<CDeterministicMNManager*> m_dmnman{nullptr};
449 : std::atomic<llmq::CInstantSendManager*> m_isman{nullptr};
450 :
451 : uint64_t totalTxSize GUARDED_BY(cs); //!< sum of all mempool tx' byte sizes
452 : CAmount m_total_fee GUARDED_BY(cs); //!< sum of all mempool tx's fees (NOT modified fee)
453 : uint64_t cachedInnerUsage GUARDED_BY(cs); //!< sum of dynamic memory usage of all the map elements (NOT the maps themselves)
454 :
455 : mutable int64_t lastRollingFeeUpdate GUARDED_BY(cs);
456 : mutable bool blockSinceLastRollingFeeBump GUARDED_BY(cs);
457 : mutable double rollingMinimumFeeRate GUARDED_BY(cs); //!< minimum fee to get into the pool, decreases exponentially
458 : mutable Epoch m_epoch GUARDED_BY(cs);
459 :
460 : // In-memory counter for external mempool tracking purposes.
461 : // This number is incremented once every time a transaction
462 : // is added or removed from the mempool for any reason.
463 : mutable uint64_t m_sequence_number{1};
464 :
465 : void trackPackageRemoved(const CFeeRate& rate) EXCLUSIVE_LOCKS_REQUIRED(cs);
466 :
467 : bool m_is_loaded GUARDED_BY(cs){false};
468 :
469 : public:
470 :
471 : static const int ROLLING_FEE_HALFLIFE = 60 * 60 * 12; // public only for testing
472 :
473 : typedef boost::multi_index_container<
474 : CTxMemPoolEntry,
475 : boost::multi_index::indexed_by<
476 : // sorted by txid
477 : boost::multi_index::hashed_unique<mempoolentry_txid, SaltedTxidHasher>,
478 : // sorted by fee rate
479 : boost::multi_index::ordered_non_unique<
480 : boost::multi_index::tag<descendant_score>,
481 : boost::multi_index::identity<CTxMemPoolEntry>,
482 : CompareTxMemPoolEntryByDescendantScore
483 : >,
484 : // sorted by entry time
485 : boost::multi_index::ordered_non_unique<
486 : boost::multi_index::tag<entry_time>,
487 : boost::multi_index::identity<CTxMemPoolEntry>,
488 : CompareTxMemPoolEntryByEntryTime
489 : >,
490 : // sorted by fee rate with ancestors
491 : boost::multi_index::ordered_non_unique<
492 : boost::multi_index::tag<ancestor_score>,
493 : boost::multi_index::identity<CTxMemPoolEntry>,
494 : CompareTxMemPoolEntryByAncestorFee
495 : >
496 : >
497 : > indexed_transaction_set;
498 :
499 : /**
500 : * This mutex needs to be locked when accessing `mapTx` or other members
501 : * that are guarded by it.
502 : *
503 : * @par Consistency guarantees
504 : * By design, it is guaranteed that:
505 : * 1. Locking both `cs_main` and `mempool.cs` will give a view of mempool
506 : * that is consistent with current chain tip (`ActiveChain()` and
507 : * `CoinsTip()`) and is fully populated. Fully populated means that if the
508 : * current active chain is missing transactions that were present in a
509 : * previously active chain, all the missing transactions will have been
510 : * re-added to the mempool and should be present if they meet size and
511 : * consistency constraints.
512 : * 2. Locking `mempool.cs` without `cs_main` will give a view of a mempool
513 : * consistent with some chain that was active since `cs_main` was last
514 : * locked, and that is fully populated as described above. It is ok for
515 : * code that only needs to query or remove transactions from the mempool
516 : * to lock just `mempool.cs` without `cs_main`.
517 : *
518 : * To provide these guarantees, it is necessary to lock both `cs_main` and
519 : * `mempool.cs` whenever adding transactions to the mempool and whenever
520 : * changing the chain tip. It's necessary to keep both mutexes locked until
521 : * the mempool is consistent with the new chain tip and fully populated.
522 : */
523 : mutable RecursiveMutex cs;
524 : indexed_transaction_set mapTx GUARDED_BY(cs);
525 :
526 : using txiter = indexed_transaction_set::nth_index<0>::type::const_iterator;
527 : std::vector<std::pair<uint256, txiter> > vTxHashes GUARDED_BY(cs); //!< All tx hashes/entries in mapTx, in random order
528 :
529 : typedef std::set<txiter, CompareIteratorByHash> setEntries;
530 :
531 : uint64_t CalculateDescendantMaximum(txiter entry) const EXCLUSIVE_LOCKS_REQUIRED(cs);
532 : private:
533 : typedef std::map<txiter, setEntries, CompareIteratorByHash> cacheMap;
534 :
535 : std::map<CMempoolAddressDeltaKey, CMempoolAddressDelta, CMempoolAddressDeltaKeyCompare> mapAddress;
536 : std::map<uint256, std::vector<CMempoolAddressDeltaKey>> mapAddressInserted;
537 : std::map<CSpentIndexKey, CSpentIndexValue, CSpentIndexKeyCompare> mapSpent;
538 : std::map<uint256, std::vector<CSpentIndexKey>> mapSpentInserted;
539 :
540 : std::multimap<uint256, uint256> mapProTxRefs; // proTxHash -> transaction (all TXs that refer to an existing proTx)
541 : std::map<NetInfoEntry, uint256> mapProTxAddresses;
542 : std::map<CKeyID, uint256> mapProTxPubKeyIDs;
543 : std::map<uint256, uint256> mapProTxBlsPubKeyHashes;
544 : std::map<COutPoint, uint256> mapProTxCollaterals;
545 : std::map<uint256, int /* expiry height */> mapAssetUnlockExpiry; // tx hash -> height
546 :
547 : void UpdateParent(txiter entry, txiter parent, bool add) EXCLUSIVE_LOCKS_REQUIRED(cs);
548 : void UpdateChild(txiter entry, txiter child, bool add) EXCLUSIVE_LOCKS_REQUIRED(cs);
549 :
550 : std::vector<indexed_transaction_set::const_iterator> GetSortedDepthAndScore() const EXCLUSIVE_LOCKS_REQUIRED(cs);
551 :
552 : /**
553 : * Track locally submitted transactions to periodically retry initial broadcast.
554 : */
555 : std::set<uint256> m_unbroadcast_txids GUARDED_BY(cs);
556 :
557 :
558 : /**
559 : * Helper function to calculate all in-mempool ancestors of staged_ancestors and apply ancestor
560 : * and descendant limits (including staged_ancestors thsemselves, entry_size and entry_count).
561 : * param@[in] entry_size Virtual size to include in the limits.
562 : * param@[in] entry_count How many entries to include in the limits.
563 : * param@[in] staged_ancestors Should contain entries in the mempool.
564 : * param@[out] setAncestors Will be populated with all mempool ancestors.
565 : */
566 : bool CalculateAncestorsAndCheckLimits(size_t entry_size,
567 : size_t entry_count,
568 : setEntries& setAncestors,
569 : CTxMemPoolEntry::Parents &staged_ancestors,
570 : uint64_t limitAncestorCount,
571 : uint64_t limitAncestorSize,
572 : uint64_t limitDescendantCount,
573 : uint64_t limitDescendantSize,
574 : std::string &errString) const EXCLUSIVE_LOCKS_REQUIRED(cs);
575 :
576 : public:
577 : indirectmap<COutPoint, const CTransaction*> mapNextTx GUARDED_BY(cs);
578 : std::map<uint256, CAmount> mapDeltas GUARDED_BY(cs);
579 :
580 : /** Create a new CTxMemPool.
581 : * Sanity checks will be off by default for performance, because otherwise
582 : * accepting transactions becomes O(N^2) where N is the number of transactions
583 : * in the pool.
584 : *
585 : * @param[in] estimator is used to estimate appropriate transaction fees.
586 : * @param[in] check_ratio is the ratio used to determine how often sanity checks will run.
587 : */
588 : explicit CTxMemPool(CBlockPolicyEstimator* estimator = nullptr, int check_ratio = 0);
589 :
590 : /**
591 : * Set CDeterministicMNManager and CInstantSendManager pointers.
592 : *
593 : * Separated from constructor as it's initialized after CTxMemPool
594 : * is created. Required for ProTx processing.
595 : */
596 : void ConnectManagers(gsl::not_null<CDeterministicMNManager*> dmnman, gsl::not_null<llmq::CInstantSendManager*> isman);
597 :
598 : /**
599 : * Reset CDeterministicMNManager and CInstantSendManager pointers.
600 : *
601 : * @pre Must be called before CDeterministicMNManager and CInstantSendManager are destroyed.
602 : */
603 : void DisconnectManagers();
604 :
605 : /**
606 : * If sanity-checking is turned on, check makes sure the pool is
607 : * consistent (does not contain two transactions that spend the same inputs,
608 : * all inputs are in the mapNextTx array). If sanity-checking is turned off,
609 : * check does nothing.
610 : */
611 : void check(const CCoinsViewCache& active_coins_tip, int64_t spendheight) const EXCLUSIVE_LOCKS_REQUIRED(::cs_main);
612 :
613 : // addUnchecked must updated state for all ancestors of a given transaction,
614 : // to track size/count of descendant transactions. First version of
615 : // addUnchecked can be used to have it call CalculateMemPoolAncestors(), and
616 : // then invoke the second version.
617 : // Note that addUnchecked is ONLY called from ATMP outside of tests
618 : // and any other callers may break wallet's in-mempool tracking (due to
619 : // lack of CValidationInterface::TransactionAddedToMempool callbacks).
620 : void addUnchecked(const CTxMemPoolEntry& entry, bool validFeeEstimate = true) EXCLUSIVE_LOCKS_REQUIRED(cs, cs_main);
621 : void addUnchecked(const CTxMemPoolEntry& entry, setEntries& setAncestors, bool validFeeEstimate = true) EXCLUSIVE_LOCKS_REQUIRED(cs, cs_main);
622 :
623 : void addAddressIndex(const CTxMemPoolEntry& entry, const CCoinsViewCache& view);
624 : void getAddressIndex(const std::vector<CMempoolAddressDeltaKey>& addresses,
625 : std::vector<CMempoolAddressDeltaEntry>& results) const;
626 : void removeAddressIndex(const uint256 txhash);
627 :
628 : void addSpentIndex(const CTxMemPoolEntry& entry, const CCoinsViewCache& view);
629 : bool getSpentIndex(const CSpentIndexKey& key, CSpentIndexValue& value) const;
630 : void removeSpentIndex(const uint256 txhash);
631 :
632 : void removeRecursive(const CTransaction& tx, MemPoolRemovalReason reason) EXCLUSIVE_LOCKS_REQUIRED(cs);
633 : /** After reorg, filter the entries that would no longer be valid in the next block, and update
634 : * the entries' cached LockPoints if needed. The mempool does not have any knowledge of
635 : * consensus rules. It just applies the callable function and removes the ones for which it
636 : * returns true.
637 : * @param[in] filter_final_and_mature Predicate that checks the relevant validation rules
638 : * and updates an entry's LockPoints.
639 : * */
640 : void removeForReorg(CChain& chain, std::function<bool(txiter)> filter_final_and_mature) EXCLUSIVE_LOCKS_REQUIRED(cs, cs_main);
641 : void removeConflicts(const CTransaction& tx) EXCLUSIVE_LOCKS_REQUIRED(cs);
642 : void removeProTxPubKeyConflicts(const CTransaction &tx, const CKeyID &keyId) EXCLUSIVE_LOCKS_REQUIRED(cs);
643 : void removeProTxPubKeyConflicts(const CTransaction &tx, const CBLSLazyPublicKey &pubKey) EXCLUSIVE_LOCKS_REQUIRED(cs);
644 : void removeProTxCollateralConflicts(const CTransaction &tx, const COutPoint &collateralOutpoint) EXCLUSIVE_LOCKS_REQUIRED(cs);
645 : void removeProTxSpentCollateralConflicts(const CTransaction &tx) EXCLUSIVE_LOCKS_REQUIRED(cs);
646 : void removeProTxKeyChangedConflicts(const CTransaction &tx, const uint256& proTxHash, const uint256& newKeyHash) EXCLUSIVE_LOCKS_REQUIRED(cs);
647 : void removeProTxConflicts(const CTransaction &tx) EXCLUSIVE_LOCKS_REQUIRED(cs);
648 : void removeForBlock(const std::vector<CTransactionRef>& vtx, unsigned int nBlockHeight) EXCLUSIVE_LOCKS_REQUIRED(cs);
649 : void removeExpiredAssetUnlock(int nBlockHeight) EXCLUSIVE_LOCKS_REQUIRED(cs);
650 :
651 : void clear();
652 : void _clear() EXCLUSIVE_LOCKS_REQUIRED(cs); //lock free
653 : bool CompareDepthAndScore(const uint256& hasha, const uint256& hashb);
654 : void queryHashes(std::vector<uint256>& vtxid) const;
655 : bool isSpent(const COutPoint& outpoint) const;
656 : unsigned int GetTransactionsUpdated() const;
657 : void AddTransactionsUpdated(unsigned int n);
658 : /**
659 : * Check that none of this transactions inputs are in the mempool, and thus
660 : * the tx is not dependent on other mempool transactions to be included in a block.
661 : */
662 : bool HasNoInputsOf(const CTransaction& tx) const EXCLUSIVE_LOCKS_REQUIRED(cs);
663 :
664 : /** Affect CreateNewBlock prioritisation of transactions */
665 : void PrioritiseTransaction(const uint256& hash, const CAmount& nFeeDelta);
666 : void ApplyDelta(const uint256& hash, CAmount &nFeeDelta) const EXCLUSIVE_LOCKS_REQUIRED(cs);
667 : void ClearPrioritisation(const uint256& hash) EXCLUSIVE_LOCKS_REQUIRED(cs);
668 :
669 : /** Get the transaction in the pool that spends the same prevout */
670 : const CTransaction* GetConflictTx(const COutPoint& prevout) const EXCLUSIVE_LOCKS_REQUIRED(cs);
671 :
672 : /** Returns an iterator to the given hash, if found */
673 : std::optional<txiter> GetIter(const uint256& txid) const EXCLUSIVE_LOCKS_REQUIRED(cs);
674 :
675 : /** Translate a set of hashes into a set of pool iterators to avoid repeated lookups */
676 : setEntries GetIterSet(const std::set<uint256>& hashes) const EXCLUSIVE_LOCKS_REQUIRED(cs);
677 :
678 : /** Remove a set of transactions from the mempool.
679 : * If a transaction is in this set, then all in-mempool descendants must
680 : * also be in the set, unless this transaction is being removed for being
681 : * in a block.
682 : * Set updateDescendants to true when removing a tx that was in a block, so
683 : * that any in-mempool descendants have their ancestor state updated.
684 : */
685 : void RemoveStaged(setEntries& stage, bool updateDescendants, MemPoolRemovalReason reason) EXCLUSIVE_LOCKS_REQUIRED(cs);
686 :
687 : /** UpdateTransactionsFromBlock is called when adding transactions from a
688 : * disconnected block back to the mempool, new mempool entries may have
689 : * children in the mempool (which is generally not the case when otherwise
690 : * adding transactions).
691 : * @post updated descendant state for descendants of each transaction in
692 : * vHashesToUpdate (excluding any child transactions present in
693 : * vHashesToUpdate, which are already accounted for). Updated state
694 : * includes add fee/size information for such descendants to the
695 : * parent and updated ancestor state to include the parent.
696 : *
697 : * @param[in] vHashesToUpdate The set of txids from the
698 : * disconnected block that have been accepted back into the mempool.
699 : * @param[in] ancestor_size_limit The maximum allowed size in virtual
700 : * bytes of an entry and its ancestors
701 : * @param[in] ancestor_count_limit The maximum allowed number of
702 : * transactions including the entry and its ancestors.
703 : */
704 : void UpdateTransactionsFromBlock(const std::vector<uint256>& vHashesToUpdate,
705 : uint64_t ancestor_size_limit, uint64_t ancestor_count_limit) EXCLUSIVE_LOCKS_REQUIRED(cs, cs_main) LOCKS_EXCLUDED(m_epoch);
706 :
707 : /** Try to calculate all in-mempool ancestors of entry.
708 : * (these are all calculated including the tx itself)
709 : * limitAncestorCount = max number of ancestors
710 : * limitAncestorSize = max size of ancestors
711 : * limitDescendantCount = max number of descendants any ancestor can have
712 : * limitDescendantSize = max size of descendants any ancestor can have
713 : * errString = populated with error reason if any limits are hit
714 : * fSearchForParents = whether to search a tx's vin for in-mempool parents, or
715 : * look up parents from mapLinks. Must be true for entries not in the mempool
716 : */
717 : bool CalculateMemPoolAncestors(const CTxMemPoolEntry& entry, setEntries& setAncestors, uint64_t limitAncestorCount, uint64_t limitAncestorSize, uint64_t limitDescendantCount, uint64_t limitDescendantSize, std::string& errString, bool fSearchForParents = true) const EXCLUSIVE_LOCKS_REQUIRED(cs);
718 :
719 : /** Calculate all in-mempool ancestors of a set of transactions not already in the mempool and
720 : * check ancestor and descendant limits. Heuristics are used to estimate the ancestor and
721 : * descendant count of all entries if the package were to be added to the mempool. The limits
722 : * are applied to the union of all package transactions. For example, if the package has 3
723 : * transactions and limitAncestorCount = 25, the union of all 3 sets of ancestors (including the
724 : * transactions themselves) must be <= 22.
725 : * @param[in] package Transaction package being evaluated for acceptance
726 : * to mempool. The transactions need not be direct
727 : * ancestors/descendants of each other.
728 : * @param[in] limitAncestorCount Max number of txns including ancestors.
729 : * @param[in] limitAncestorSize Max virtual size including ancestors.
730 : * @param[in] limitDescendantCount Max number of txns including descendants.
731 : * @param[in] limitDescendantSize Max virtual size including descendants.
732 : * @param[out] errString Populated with error reason if a limit is hit.
733 : */
734 : bool CheckPackageLimits(const Package& package,
735 : uint64_t limitAncestorCount,
736 : uint64_t limitAncestorSize,
737 : uint64_t limitDescendantCount,
738 : uint64_t limitDescendantSize,
739 : std::string &errString) const EXCLUSIVE_LOCKS_REQUIRED(cs);
740 :
741 : /** Populate setDescendants with all in-mempool descendants of hash.
742 : * Assumes that setDescendants includes all in-mempool descendants of anything
743 : * already in it. */
744 : void CalculateDescendants(txiter it, setEntries& setDescendants) const EXCLUSIVE_LOCKS_REQUIRED(cs);
745 :
746 : /** The minimum fee to get into the mempool, which may itself not be enough
747 : * for larger-sized transactions.
748 : * The incrementalRelayFee policy variable is used to bound the time it
749 : * takes the fee rate to go back down all the way to 0. When the feerate
750 : * would otherwise be half of this, it is set to 0 instead.
751 : */
752 : CFeeRate GetMinFee(size_t sizelimit) const;
753 :
754 : /** Remove transactions from the mempool until its dynamic size is <= sizelimit.
755 : * pvNoSpendsRemaining, if set, will be populated with the list of outpoints
756 : * which are not in mempool which no longer have any spends in this mempool.
757 : */
758 : void TrimToSize(size_t sizelimit, std::vector<COutPoint>* pvNoSpendsRemaining = nullptr) EXCLUSIVE_LOCKS_REQUIRED(cs);
759 :
760 : /** Expire all transaction (and their dependencies) in the mempool older than time. Return the number of removed transactions.
761 : * @pre Caller must ensure that CInstantSendManager exists and has been set using
762 : * ConnectManagers() for InstantSend awareness
763 : */
764 : int Expire(std::chrono::seconds time) EXCLUSIVE_LOCKS_REQUIRED(cs);
765 :
766 : /**
767 : * Calculate the ancestor and descendant count for the given transaction.
768 : * The counts include the transaction itself.
769 : * When ancestors is non-zero (ie, the transaction itself is in the mempool),
770 : * ancestorsize and ancestorfees will also be set to the appropriate values.
771 : */
772 : void GetTransactionAncestry(const uint256& txid, size_t& ancestors, size_t& descendants, size_t* ancestorsize = nullptr, CAmount* ancestorfees = nullptr) const;
773 :
774 : /** @returns true if the mempool is fully loaded */
775 : bool IsLoaded() const;
776 :
777 : /** Sets the current loaded state */
778 : void SetIsLoaded(bool loaded);
779 :
780 65 : unsigned long size() const
781 : {
782 65 : LOCK(cs);
783 65 : return mapTx.size();
784 65 : }
785 :
786 0 : uint64_t GetTotalTxSize() const EXCLUSIVE_LOCKS_REQUIRED(cs)
787 : {
788 0 : AssertLockHeld(cs);
789 0 : return totalTxSize;
790 : }
791 :
792 0 : CAmount GetTotalFee() const EXCLUSIVE_LOCKS_REQUIRED(cs)
793 : {
794 0 : AssertLockHeld(cs);
795 0 : return m_total_fee;
796 : }
797 :
798 241 : bool exists(const uint256& hash) const
799 : {
800 241 : LOCK(cs);
801 241 : return (mapTx.count(hash) != 0);
802 241 : }
803 :
804 : CTransactionRef get(const uint256& hash) const;
805 : TxMempoolInfo info(const uint256& hash) const;
806 : std::vector<TxMempoolInfo> infoAll() const;
807 :
808 : /**
809 : * @pre Caller must ensure that CDeterministicMNManager exists and has been
810 : * set using ConnectManagers() for the CTxMemPool instance.
811 : */
812 : bool existsProviderTxConflict(const CTransaction &tx) const;
813 :
814 : size_t DynamicMemoryUsage() const;
815 :
816 : /** Adds a transaction to the unbroadcast set */
817 0 : void AddUnbroadcastTx(const uint256& txid)
818 : {
819 0 : LOCK(cs);
820 : // Sanity check the transaction is in the mempool & insert into
821 : // unbroadcast set.
822 0 : if (exists(txid)) m_unbroadcast_txids.insert(txid);
823 0 : }
824 :
825 : /** Removes a transaction from the unbroadcast set */
826 : void RemoveUnbroadcastTx(const uint256& txid, const bool unchecked = false);
827 :
828 : /** Returns transactions in unbroadcast set */
829 0 : std::set<uint256> GetUnbroadcastTxs() const
830 : {
831 0 : LOCK(cs);
832 0 : return m_unbroadcast_txids;
833 0 : }
834 :
835 : /** Returns whether a txid is in the unbroadcast set */
836 0 : bool IsUnbroadcastTx(const uint256& txid) const {
837 0 : LOCK(cs);
838 0 : return (m_unbroadcast_txids.count(txid) != 0);
839 0 : }
840 :
841 : /** Guards this internal counter for external reporting */
842 24779 : uint64_t GetAndIncrementSequence() const EXCLUSIVE_LOCKS_REQUIRED(cs) {
843 24779 : return m_sequence_number++;
844 : }
845 :
846 0 : uint64_t GetSequence() const EXCLUSIVE_LOCKS_REQUIRED(cs) {
847 0 : return m_sequence_number;
848 : }
849 :
850 : private:
851 : /** UpdateForDescendants is used by UpdateTransactionsFromBlock to update
852 : * the descendants for a single transaction that has been added to the
853 : * mempool but may have child transactions in the mempool, eg during a
854 : * chain reorg.
855 : *
856 : * @pre CTxMemPoolEntry::m_children is correct for the given tx and all
857 : * descendants.
858 : * @pre cachedDescendants is an accurate cache where each entry has all
859 : * descendants of the corresponding key, including those that should
860 : * be removed for violation of ancestor limits.
861 : * @post if updateIt has any non-excluded descendants, cachedDescendants has
862 : * a new cache line for updateIt.
863 : * @post descendants_to_remove has a new entry for any descendant which exceeded
864 : * ancestor limits relative to updateIt.
865 : *
866 : * @param[in] updateIt the entry to update for its descendants
867 : * @param[in,out] cachedDescendants a cache where each line corresponds to all
868 : * descendants. It will be updated with the descendants of the transaction
869 : * being updated, so that future invocations don't need to walk the same
870 : * transaction again, if encountered in another transaction chain.
871 : * @param[in] setExclude the set of descendant transactions in the mempool
872 : * that must not be accounted for (because any descendants in setExclude
873 : * were added to the mempool after the transaction being updated and hence
874 : * their state is already reflected in the parent state).
875 : * @param[out] descendants_to_remove Populated with the txids of entries that
876 : * exceed ancestor limits. It's the responsibility of the caller to
877 : * removeRecursive them.
878 : * @param[in] ancestor_size_limit the max number of ancestral bytes allowed
879 : * for any descendant
880 : * @param[in] ancestor_count_limit the max number of ancestor transactions
881 : * allowed for any descendant
882 : */
883 : void UpdateForDescendants(txiter updateIt, cacheMap& cachedDescendants,
884 : const std::set<uint256>& setExclude, std::set<uint256>& descendants_to_remove,
885 : uint64_t ancestor_size_limit, uint64_t ancestor_count_limit) EXCLUSIVE_LOCKS_REQUIRED(cs);
886 : /** Update ancestors of hash to add/remove it as a descendant transaction. */
887 : void UpdateAncestorsOf(bool add, txiter hash, setEntries &setAncestors) EXCLUSIVE_LOCKS_REQUIRED(cs);
888 : /** Set ancestor state for an entry */
889 : void UpdateEntryForAncestors(txiter it, const setEntries &setAncestors) EXCLUSIVE_LOCKS_REQUIRED(cs);
890 : /** For each transaction being removed, update ancestors and any direct children.
891 : * If updateDescendants is true, then also update in-mempool descendants'
892 : * ancestor state. */
893 : void UpdateForRemoveFromMempool(const setEntries &entriesToRemove, bool updateDescendants) EXCLUSIVE_LOCKS_REQUIRED(cs);
894 : /** Sever link between specified transaction and direct children. */
895 : void UpdateChildrenForRemoval(txiter entry) EXCLUSIVE_LOCKS_REQUIRED(cs);
896 :
897 : /**
898 : * addUnchecked extension for Dash-specific transactions (ProTx).
899 : */
900 : void addUncheckedProTx(CDeterministicMNManager& dmnman, indexed_transaction_set::iterator& newit,
901 : const CTransaction& tx);
902 :
903 : /** Before calling removeUnchecked for a given transaction,
904 : * UpdateForRemoveFromMempool must be called on the entire (dependent) set
905 : * of transactions being removed at the same time. We use each
906 : * CTxMemPoolEntry's setMemPoolParents in order to walk ancestors of a
907 : * given transaction that is removed, so we can't remove intermediate
908 : * transactions in a chain before we've updated all the state for the
909 : * removal.
910 : */
911 : void removeUnchecked(txiter entry, MemPoolRemovalReason reason) EXCLUSIVE_LOCKS_REQUIRED(cs);
912 : void removeUncheckedProTx(const CTransaction& tx);
913 :
914 : public:
915 : /** visited marks a CTxMemPoolEntry as having been traversed
916 : * during the lifetime of the most recently created Epoch::Guard
917 : * and returns false if we are the first visitor, true otherwise.
918 : *
919 : * An Epoch::Guard must be held when visited is called or an assert will be
920 : * triggered.
921 : *
922 : */
923 0 : bool visited(const txiter it) const EXCLUSIVE_LOCKS_REQUIRED(cs, m_epoch)
924 : {
925 0 : return m_epoch.visited(it->m_epoch_marker);
926 : }
927 :
928 : bool visited(std::optional<txiter> it) const EXCLUSIVE_LOCKS_REQUIRED(cs, m_epoch) {
929 : assert(m_epoch.guarded());
930 : return !it || visited(*it);
931 : }
932 : };
933 :
934 : /**
935 : * CCoinsView that brings transactions from a mempool into view.
936 : * It does not check for spendings by memory pool transactions.
937 : * Instead, it provides access to all Coins which are either unspent in the
938 : * base CCoinsView, are outputs from any mempool transaction, or are
939 : * tracked temporarily to allow transaction dependencies in package validation.
940 : * This allows transaction replacement to work as expected, as you want to
941 : * have all inputs "available" to check signatures, and any cycles in the
942 : * dependency graph are checked directly in AcceptToMemoryPool.
943 : * It also allows you to sign a double-spend directly in
944 : * signrawtransactionwithkey and signrawtransactionwithwallet,
945 : * as long as the conflicting transaction is not yet confirmed.
946 : */
947 : class CCoinsViewMemPool : public CCoinsViewBacked
948 : {
949 : /**
950 : * Coins made available by transactions being validated. Tracking these allows for package
951 : * validation, since we can access transaction outputs without submitting them to mempool.
952 : */
953 : std::unordered_map<COutPoint, Coin, SaltedOutpointHasher> m_temp_added;
954 : protected:
955 : const CTxMemPool& mempool;
956 :
957 : public:
958 : CCoinsViewMemPool(CCoinsView* baseIn, const CTxMemPool& mempoolIn);
959 : bool GetCoin(const COutPoint &outpoint, Coin &coin) const override;
960 : /** Add the coins created by this transaction. These coins are only temporarily stored in
961 : * m_temp_added and cannot be flushed to the back end. Only used for package validation. */
962 : void PackageAddTransaction(const CTransactionRef& tx);
963 : };
964 :
965 : /**
966 : * DisconnectedBlockTransactions
967 :
968 : * During the reorg, it's desirable to re-add previously confirmed transactions
969 : * to the mempool, so that anything not re-confirmed in the new chain is
970 : * available to be mined. However, it's more efficient to wait until the reorg
971 : * is complete and process all still-unconfirmed transactions at that time,
972 : * since we expect most confirmed transactions to (typically) still be
973 : * confirmed in the new chain, and re-accepting to the memory pool is expensive
974 : * (and therefore better to not do in the middle of reorg-processing).
975 : * Instead, store the disconnected transactions (in order!) as we go, remove any
976 : * that are included in blocks in the new chain, and then process the remaining
977 : * still-unconfirmed transactions at the end.
978 : */
979 :
980 : // multi_index tag names
981 : struct txid_index {};
982 : struct insertion_order {};
983 :
984 24311 : struct DisconnectedBlockTransactions {
985 : typedef boost::multi_index_container<
986 : CTransactionRef,
987 : boost::multi_index::indexed_by<
988 : // sorted by txid
989 : boost::multi_index::hashed_unique<
990 : boost::multi_index::tag<txid_index>,
991 : mempoolentry_txid,
992 : SaltedTxidHasher
993 : >,
994 : // sorted by order in the blockchain
995 : boost::multi_index::sequenced<
996 : boost::multi_index::tag<insertion_order>
997 : >
998 : >
999 : > indexed_disconnected_transactions;
1000 :
1001 : // It's almost certainly a logic bug if we don't clear out queuedTx before
1002 : // destruction, as we add to it while disconnecting blocks, and then we
1003 : // need to re-process remaining transactions to ensure mempool consistency.
1004 : // For now, assert() that we've emptied out this object on destruction.
1005 : // This assert() can always be removed if the reorg-processing code were
1006 : // to be refactored such that this assumption is no longer true (for
1007 : // instance if there was some other way we cleaned up the mempool after a
1008 : // reorg, besides draining this object).
1009 48622 : ~DisconnectedBlockTransactions() { assert(queuedTx.empty()); }
1010 :
1011 : indexed_disconnected_transactions queuedTx;
1012 24311 : uint64_t cachedInnerUsage = 0;
1013 :
1014 : // Estimate the overhead of queuedTx to be 6 pointers + an allocation, as
1015 : // no exact formula for boost::multi_index_contained is implemented.
1016 387 : size_t DynamicMemoryUsage() const {
1017 387 : return memusage::MallocUsage(sizeof(CTransactionRef) + 6 * sizeof(void*)) * queuedTx.size() + cachedInnerUsage;
1018 : }
1019 :
1020 387 : void addTransaction(const CTransactionRef& tx)
1021 : {
1022 387 : queuedTx.insert(tx);
1023 387 : cachedInnerUsage += RecursiveDynamicUsage(tx);
1024 387 : }
1025 :
1026 : // Remove entries based on txid_index, and update memory usage.
1027 24572 : void removeForBlock(const std::vector<CTransactionRef>& vtx)
1028 : {
1029 : // Short-circuit in the common case of a block being added to the tip
1030 24572 : if (queuedTx.empty()) {
1031 24190 : return;
1032 : }
1033 764 : for (auto const &tx : vtx) {
1034 382 : auto it = queuedTx.find(tx->GetHash());
1035 382 : if (it != queuedTx.end()) {
1036 0 : cachedInnerUsage -= RecursiveDynamicUsage(*it);
1037 0 : queuedTx.erase(it);
1038 0 : }
1039 : }
1040 24572 : }
1041 :
1042 : // Remove an entry by insertion_order index, and update memory usage.
1043 0 : void removeEntry(indexed_disconnected_transactions::index<insertion_order>::type::iterator entry)
1044 : {
1045 0 : cachedInnerUsage -= RecursiveDynamicUsage(*entry);
1046 0 : queuedTx.get<insertion_order>().erase(entry);
1047 0 : }
1048 :
1049 : void clear()
1050 : {
1051 : cachedInnerUsage = 0;
1052 : queuedTx.clear();
1053 : }
1054 : };
1055 :
1056 : #endif // BITCOIN_TXMEMPOOL_H
|
