Line data Source code
1 : // Copyright (c) 2009-2010 Satoshi Nakamoto
2 : // Copyright (c) 2009-2020 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 <set>
12 : #include <string>
13 : #include <utility>
14 : #include <vector>
15 :
16 : #include <amount.h>
17 : #include <coins.h>
18 : #include <crypto/siphash.h>
19 : #include <indirectmap.h>
20 : #include <optional.h>
21 : #include <policy/feerate.h>
22 : #include <primitives/transaction.h>
23 : #include <sync.h>
24 : #include <random.h>
25 :
26 : #include <boost/multi_index_container.hpp>
27 : #include <boost/multi_index/hashed_index.hpp>
28 : #include <boost/multi_index/ordered_index.hpp>
29 : #include <boost/multi_index/sequenced_index.hpp>
30 :
31 : class CBlockIndex;
32 : extern RecursiveMutex cs_main;
33 :
34 : /** Fake height value used in Coin to signify they are only in the memory pool (since 0.8) */
35 : static const uint32_t MEMPOOL_HEIGHT = 0x7FFFFFFF;
36 :
37 : struct LockPoints
38 : {
39 : // Will be set to the blockchain height and median time past
40 : // values that would be necessary to satisfy all relative locktime
41 : // constraints (BIP68) of this tx given our view of block chain history
42 : int height;
43 : int64_t time;
44 : // As long as the current chain descends from the highest height block
45 : // containing one of the inputs used in the calculation, then the cached
46 : // values are still valid even after a reorg.
47 : CBlockIndex* maxInputBlock;
48 :
49 67878 : LockPoints() : height(0), time(0), maxInputBlock(nullptr) { }
50 : };
51 :
52 : struct CompareIteratorByHash {
53 : // SFINAE for T where T is either a pointer type (e.g., a txiter) or a reference_wrapper<T>
54 : // (e.g. a wrapped CTxMemPoolEntry&)
55 : template <typename T>
56 347230693 : bool operator()(const std::reference_wrapper<T>& a, const std::reference_wrapper<T>& b) const
57 : {
58 347230693 : return a.get().GetTx().GetHash() < b.get().GetTx().GetHash();
59 : }
60 : template <typename T>
61 894989019 : bool operator()(const T& a, const T& b) const
62 : {
63 894989019 : return a->GetTx().GetHash() < b->GetTx().GetHash();
64 : }
65 : };
66 : /** \class CTxMemPoolEntry
67 : *
68 : * CTxMemPoolEntry stores data about the corresponding transaction, as well
69 : * as data about all in-mempool transactions that depend on the transaction
70 : * ("descendant" transactions).
71 : *
72 : * When a new entry is added to the mempool, we update the descendant state
73 : * (nCountWithDescendants, nSizeWithDescendants, and nModFeesWithDescendants) for
74 : * all ancestors of the newly added transaction.
75 : *
76 : */
77 :
78 554248 : class CTxMemPoolEntry
79 : {
80 : public:
81 : typedef std::reference_wrapper<const CTxMemPoolEntry> CTxMemPoolEntryRef;
82 : // two aliases, should the types ever diverge
83 : typedef std::set<CTxMemPoolEntryRef, CompareIteratorByHash> Parents;
84 : typedef std::set<CTxMemPoolEntryRef, CompareIteratorByHash> Children;
85 :
86 : private:
87 : const CTransactionRef tx;
88 : mutable Parents m_parents;
89 : mutable Children m_children;
90 : const CAmount nFee; //!< Cached to avoid expensive parent-transaction lookups
91 : const size_t nTxWeight; //!< ... and avoid recomputing tx weight (also used for GetTxSize())
92 : const size_t nUsageSize; //!< ... and total memory usage
93 : const int64_t nTime; //!< Local time when entering the mempool
94 : const unsigned int entryHeight; //!< Chain height when entering the mempool
95 : const bool spendsCoinbase; //!< keep track of transactions that spend a coinbase
96 : const int64_t sigOpCost; //!< Total sigop cost
97 : int64_t feeDelta; //!< Used for determining the priority of the transaction for mining in a block
98 : LockPoints lockPoints; //!< Track the height and time at which tx was final
99 :
100 : // Information about descendants of this transaction that are in the
101 : // mempool; if we remove this transaction we must remove all of these
102 : // descendants as well.
103 : uint64_t nCountWithDescendants; //!< number of descendant transactions
104 : uint64_t nSizeWithDescendants; //!< ... and size
105 : CAmount nModFeesWithDescendants; //!< ... and total fees (all including us)
106 :
107 : // Analogous statistics for ancestor transactions
108 : uint64_t nCountWithAncestors;
109 : uint64_t nSizeWithAncestors;
110 : CAmount nModFeesWithAncestors;
111 : int64_t nSigOpCostWithAncestors;
112 :
113 : public:
114 : CTxMemPoolEntry(const CTransactionRef& _tx, const CAmount& _nFee,
115 : int64_t _nTime, unsigned int _entryHeight,
116 : bool spendsCoinbase,
117 : int64_t nSigOpsCost, LockPoints lp);
118 :
119 2575619272 : const CTransaction& GetTx() const { return *this->tx; }
120 94328 : CTransactionRef GetSharedTx() const { return this->tx; }
121 29467218 : const CAmount& GetFee() const { return nFee; }
122 : size_t GetTxSize() const;
123 64979 : size_t GetTxWeight() const { return nTxWeight; }
124 45219833 : std::chrono::seconds GetTime() const { return std::chrono::seconds{nTime}; }
125 140151 : unsigned int GetHeight() const { return entryHeight; }
126 8003563 : int64_t GetSigOpCost() const { return sigOpCost; }
127 153005165 : int64_t GetModifiedFee() const { return nFee + feeDelta; }
128 5222196 : size_t DynamicMemoryUsage() const { return nUsageSize; }
129 734 : const LockPoints& GetLockPoints() const { return lockPoints; }
130 :
131 : // Adjusts the descendant state.
132 : void UpdateDescendantState(int64_t modifySize, CAmount modifyFee, int64_t modifyCount);
133 : // Adjusts the ancestor state
134 : void UpdateAncestorState(int64_t modifySize, CAmount modifyFee, int64_t modifyCount, int64_t modifySigOps);
135 : // Updates the fee delta used for mining priority score, and the
136 : // modified fees with descendants.
137 : void UpdateFeeDelta(int64_t feeDelta);
138 : // Update the LockPoints after a reorg
139 : void UpdateLockPoints(const LockPoints& lp);
140 :
141 5142640 : uint64_t GetCountWithDescendants() const { return nCountWithDescendants; }
142 88599965 : uint64_t GetSizeWithDescendants() const { return nSizeWithDescendants; }
143 78465777 : CAmount GetModFeesWithDescendants() const { return nModFeesWithDescendants; }
144 :
145 730 : bool GetSpendsCoinbase() const { return spendsCoinbase; }
146 :
147 33693337 : uint64_t GetCountWithAncestors() const { return nCountWithAncestors; }
148 22815433 : uint64_t GetSizeWithAncestors() const { return nSizeWithAncestors; }
149 22868786 : CAmount GetModFeesWithAncestors() const { return nModFeesWithAncestors; }
150 5149779 : int64_t GetSigOpCostWithAncestors() const { return nSigOpCostWithAncestors; }
151 :
152 20606659 : const Parents& GetMemPoolParentsConst() const { return m_parents; }
153 16584572 : const Children& GetMemPoolChildrenConst() const { return m_children; }
154 167000 : Parents& GetMemPoolParents() const { return m_parents; }
155 103537 : Children& GetMemPoolChildren() const { return m_children; }
156 :
157 : mutable size_t vTxHashesIdx; //!< Index in mempool's vTxHashes
158 : mutable uint64_t m_epoch; //!< epoch when last touched, useful for graph algorithms
159 : };
160 :
161 : // Helpers for modifying CTxMemPool::mapTx, which is a boost multi_index.
162 : struct update_descendant_state
163 : {
164 6116410 : update_descendant_state(int64_t _modifySize, CAmount _modifyFee, int64_t _modifyCount) :
165 3058205 : modifySize(_modifySize), modifyFee(_modifyFee), modifyCount(_modifyCount)
166 6116410 : {}
167 :
168 3058205 : void operator() (CTxMemPoolEntry &e)
169 3058205 : { e.UpdateDescendantState(modifySize, modifyFee, modifyCount); }
170 :
171 : private:
172 : int64_t modifySize;
173 : CAmount modifyFee;
174 : int64_t modifyCount;
175 : };
176 :
177 : struct update_ancestor_state
178 : {
179 128868 : update_ancestor_state(int64_t _modifySize, CAmount _modifyFee, int64_t _modifyCount, int64_t _modifySigOpsCost) :
180 64434 : modifySize(_modifySize), modifyFee(_modifyFee), modifyCount(_modifyCount), modifySigOpsCost(_modifySigOpsCost)
181 128868 : {}
182 :
183 64434 : void operator() (CTxMemPoolEntry &e)
184 64434 : { e.UpdateAncestorState(modifySize, modifyFee, modifyCount, modifySigOpsCost); }
185 :
186 : private:
187 : int64_t modifySize;
188 : CAmount modifyFee;
189 : int64_t modifyCount;
190 : int64_t modifySigOpsCost;
191 : };
192 :
193 : struct update_fee_delta
194 : {
195 34 : explicit update_fee_delta(int64_t _feeDelta) : feeDelta(_feeDelta) { }
196 :
197 17 : void operator() (CTxMemPoolEntry &e) { e.UpdateFeeDelta(feeDelta); }
198 :
199 : private:
200 : int64_t feeDelta;
201 : };
202 :
203 : struct update_lock_points
204 : {
205 4 : explicit update_lock_points(const LockPoints& _lp) : lp(_lp) { }
206 :
207 2 : void operator() (CTxMemPoolEntry &e) { e.UpdateLockPoints(lp); }
208 :
209 : private:
210 : const LockPoints& lp;
211 : };
212 :
213 : // extracts a transaction hash from CTxMemPoolEntry or CTransactionRef
214 : struct mempoolentry_txid
215 : {
216 : typedef uint256 result_type;
217 27415030 : result_type operator() (const CTxMemPoolEntry &entry) const
218 : {
219 27415030 : return entry.GetTx().GetHash();
220 : }
221 :
222 31959 : result_type operator() (const CTransactionRef& tx) const
223 : {
224 31959 : return tx->GetHash();
225 : }
226 : };
227 :
228 : // extracts a transaction witness-hash from CTxMemPoolEntry or CTransactionRef
229 : struct mempoolentry_wtxid
230 : {
231 : typedef uint256 result_type;
232 7849323 : result_type operator() (const CTxMemPoolEntry &entry) const
233 : {
234 7849323 : return entry.GetTx().GetWitnessHash();
235 : }
236 :
237 : result_type operator() (const CTransactionRef& tx) const
238 : {
239 : return tx->GetWitnessHash();
240 : }
241 : };
242 :
243 :
244 : /** \class CompareTxMemPoolEntryByDescendantScore
245 : *
246 : * Sort an entry by max(score/size of entry's tx, score/size with all descendants).
247 : */
248 : class CompareTxMemPoolEntryByDescendantScore
249 : {
250 : public:
251 32517439 : bool operator()(const CTxMemPoolEntry& a, const CTxMemPoolEntry& b) const
252 : {
253 32517439 : double a_mod_fee, a_size, b_mod_fee, b_size;
254 :
255 32517439 : GetModFeeAndSize(a, a_mod_fee, a_size);
256 32517439 : GetModFeeAndSize(b, b_mod_fee, b_size);
257 :
258 : // Avoid division by rewriting (a/b > c/d) as (a*d > c*b).
259 32517439 : double f1 = a_mod_fee * b_size;
260 32517439 : double f2 = a_size * b_mod_fee;
261 :
262 32517439 : if (f1 == f2) {
263 15830236 : return a.GetTime() >= b.GetTime();
264 : }
265 16687203 : return f1 < f2;
266 32517439 : }
267 :
268 : // Return the fee/size we're using for sorting this entry.
269 65034878 : void GetModFeeAndSize(const CTxMemPoolEntry &a, double &mod_fee, double &size) const
270 : {
271 : // Compare feerate with descendants to feerate of the transaction, and
272 : // return the fee/size for the max.
273 65034878 : double f1 = (double)a.GetModifiedFee() * a.GetSizeWithDescendants();
274 65034878 : double f2 = (double)a.GetModFeesWithDescendants() * a.GetTxSize();
275 :
276 65034878 : if (f2 > f1) {
277 13319971 : mod_fee = a.GetModFeesWithDescendants();
278 13319971 : size = a.GetSizeWithDescendants();
279 13319971 : } else {
280 51714907 : mod_fee = a.GetModifiedFee();
281 51714907 : size = a.GetTxSize();
282 : }
283 65034878 : }
284 : };
285 :
286 : /** \class CompareTxMemPoolEntryByScore
287 : *
288 : * Sort by feerate of entry (fee/size) in descending order
289 : * This is only used for transaction relay, so we use GetFee()
290 : * instead of GetModifiedFee() to avoid leaking prioritization
291 : * information via the sort order.
292 : */
293 : class CompareTxMemPoolEntryByScore
294 : {
295 : public:
296 14211774 : bool operator()(const CTxMemPoolEntry& a, const CTxMemPoolEntry& b) const
297 : {
298 14211774 : double f1 = (double)a.GetFee() * b.GetTxSize();
299 14211774 : double f2 = (double)b.GetFee() * a.GetTxSize();
300 14211774 : if (f1 == f2) {
301 7023833 : return b.GetTx().GetHash() < a.GetTx().GetHash();
302 : }
303 7187941 : return f1 > f2;
304 14211774 : }
305 : };
306 :
307 : class CompareTxMemPoolEntryByEntryTime
308 : {
309 : public:
310 6731083 : bool operator()(const CTxMemPoolEntry& a, const CTxMemPoolEntry& b) const
311 : {
312 6731083 : return a.GetTime() < b.GetTime();
313 : }
314 : };
315 :
316 : /** \class CompareTxMemPoolEntryByAncestorScore
317 : *
318 : * Sort an entry by min(score/size of entry's tx, score/size with all ancestors).
319 : */
320 : class CompareTxMemPoolEntryByAncestorFee
321 : {
322 : public:
323 : template<typename T>
324 8266726 : bool operator()(const T& a, const T& b) const
325 : {
326 8266726 : double a_mod_fee, a_size, b_mod_fee, b_size;
327 :
328 8266726 : GetModFeeAndSize(a, a_mod_fee, a_size);
329 8266726 : GetModFeeAndSize(b, b_mod_fee, b_size);
330 :
331 : // Avoid division by rewriting (a/b > c/d) as (a*d > c*b).
332 8266726 : double f1 = a_mod_fee * b_size;
333 8266726 : double f2 = a_size * b_mod_fee;
334 :
335 8266726 : if (f1 == f2) {
336 4431798 : return a.GetTx().GetHash() < b.GetTx().GetHash();
337 : }
338 3834928 : return f1 > f2;
339 8266726 : }
340 :
341 : // Return the fee/size we're using for sorting this entry.
342 : template <typename T>
343 16533452 : void GetModFeeAndSize(const T &a, double &mod_fee, double &size) const
344 : {
345 : // Compare feerate with ancestors to feerate of the transaction, and
346 : // return the fee/size for the min.
347 16533452 : double f1 = (double)a.GetModifiedFee() * a.GetSizeWithAncestors();
348 16533452 : double f2 = (double)a.GetModFeesWithAncestors() * a.GetTxSize();
349 :
350 16533452 : if (f1 > f2) {
351 4256933 : mod_fee = a.GetModFeesWithAncestors();
352 4256933 : size = a.GetSizeWithAncestors();
353 4256933 : } else {
354 12276519 : mod_fee = a.GetModifiedFee();
355 12276519 : size = a.GetTxSize();
356 : }
357 16533452 : }
358 : };
359 :
360 : // Multi_index tag names
361 : struct descendant_score {};
362 : struct entry_time {};
363 : struct ancestor_score {};
364 : struct index_by_wtxid {};
365 :
366 : class CBlockPolicyEstimator;
367 :
368 : /**
369 : * Information about a mempool transaction.
370 : */
371 62652 : struct TxMempoolInfo
372 : {
373 : /** The transaction itself */
374 : CTransactionRef tx;
375 :
376 : /** Time the transaction entered the mempool. */
377 : std::chrono::seconds m_time;
378 :
379 : /** Fee of the transaction. */
380 : CAmount fee;
381 :
382 : /** Virtual size of the transaction. */
383 : size_t vsize;
384 :
385 : /** The fee delta. */
386 : int64_t nFeeDelta;
387 : };
388 :
389 : /** Reason why a transaction was removed from the mempool,
390 : * this is passed to the notification signal.
391 : */
392 : enum class MemPoolRemovalReason {
393 : EXPIRY, //!< Expired from mempool
394 : SIZELIMIT, //!< Removed in size limiting
395 : REORG, //!< Removed for reorganization
396 : BLOCK, //!< Removed for block
397 : CONFLICT, //!< Removed for conflict with in-block transaction
398 : REPLACED, //!< Removed for replacement
399 : };
400 :
401 : class SaltedTxidHasher
402 : {
403 : private:
404 : /** Salt */
405 : const uint64_t k0, k1;
406 :
407 : public:
408 : SaltedTxidHasher();
409 :
410 30205937 : size_t operator()(const uint256& txid) const {
411 30205937 : return SipHashUint256(k0, k1, txid);
412 : }
413 : };
414 :
415 : /**
416 : * CTxMemPool stores valid-according-to-the-current-best-chain transactions
417 : * that may be included in the next block.
418 : *
419 : * Transactions are added when they are seen on the network (or created by the
420 : * local node), but not all transactions seen are added to the pool. For
421 : * example, the following new transactions will not be added to the mempool:
422 : * - a transaction which doesn't meet the minimum fee requirements.
423 : * - a new transaction that double-spends an input of a transaction already in
424 : * the pool where the new transaction does not meet the Replace-By-Fee
425 : * requirements as defined in BIP 125.
426 : * - a non-standard transaction.
427 : *
428 : * CTxMemPool::mapTx, and CTxMemPoolEntry bookkeeping:
429 : *
430 : * mapTx is a boost::multi_index that sorts the mempool on 5 criteria:
431 : * - transaction hash (txid)
432 : * - witness-transaction hash (wtxid)
433 : * - descendant feerate [we use max(feerate of tx, feerate of tx with all descendants)]
434 : * - time in mempool
435 : * - ancestor feerate [we use min(feerate of tx, feerate of tx with all unconfirmed ancestors)]
436 : *
437 : * Note: the term "descendant" refers to in-mempool transactions that depend on
438 : * this one, while "ancestor" refers to in-mempool transactions that a given
439 : * transaction depends on.
440 : *
441 : * In order for the feerate sort to remain correct, we must update transactions
442 : * in the mempool when new descendants arrive. To facilitate this, we track
443 : * the set of in-mempool direct parents and direct children in mapLinks. Within
444 : * each CTxMemPoolEntry, we track the size and fees of all descendants.
445 : *
446 : * Usually when a new transaction is added to the mempool, it has no in-mempool
447 : * children (because any such children would be an orphan). So in
448 : * addUnchecked(), we:
449 : * - update a new entry's setMemPoolParents to include all in-mempool parents
450 : * - update the new entry's direct parents to include the new tx as a child
451 : * - update all ancestors of the transaction to include the new tx's size/fee
452 : *
453 : * When a transaction is removed from the mempool, we must:
454 : * - update all in-mempool parents to not track the tx in setMemPoolChildren
455 : * - update all ancestors to not include the tx's size/fees in descendant state
456 : * - update all in-mempool children to not include it as a parent
457 : *
458 : * These happen in UpdateForRemoveFromMempool(). (Note that when removing a
459 : * transaction along with its descendants, we must calculate that set of
460 : * transactions to be removed before doing the removal, or else the mempool can
461 : * be in an inconsistent state where it's impossible to walk the ancestors of
462 : * a transaction.)
463 : *
464 : * In the event of a reorg, the assumption that a newly added tx has no
465 : * in-mempool children is false. In particular, the mempool is in an
466 : * inconsistent state while new transactions are being added, because there may
467 : * be descendant transactions of a tx coming from a disconnected block that are
468 : * unreachable from just looking at transactions in the mempool (the linking
469 : * transactions may also be in the disconnected block, waiting to be added).
470 : * Because of this, there's not much benefit in trying to search for in-mempool
471 : * children in addUnchecked(). Instead, in the special case of transactions
472 : * being added from a disconnected block, we require the caller to clean up the
473 : * state, to account for in-mempool, out-of-block descendants for all the
474 : * in-block transactions by calling UpdateTransactionsFromBlock(). Note that
475 : * until this is called, the mempool state is not consistent, and in particular
476 : * mapLinks may not be correct (and therefore functions like
477 : * CalculateMemPoolAncestors() and CalculateDescendants() that rely
478 : * on them to walk the mempool are not generally safe to use).
479 : *
480 : * Computational limits:
481 : *
482 : * Updating all in-mempool ancestors of a newly added transaction can be slow,
483 : * if no bound exists on how many in-mempool ancestors there may be.
484 : * CalculateMemPoolAncestors() takes configurable limits that are designed to
485 : * prevent these calculations from being too CPU intensive.
486 : *
487 : */
488 5970 : class CTxMemPool
489 : {
490 : private:
491 : uint32_t nCheckFrequency GUARDED_BY(cs); //!< Value n means that n times in 2^32 we check.
492 : std::atomic<unsigned int> nTransactionsUpdated; //!< Used by getblocktemplate to trigger CreateNewBlock() invocation
493 : CBlockPolicyEstimator* minerPolicyEstimator;
494 :
495 : uint64_t totalTxSize; //!< sum of all mempool tx's virtual sizes. Differs from serialized tx size since witness data is discounted. Defined in BIP 141.
496 : uint64_t cachedInnerUsage; //!< sum of dynamic memory usage of all the map elements (NOT the maps themselves)
497 :
498 : mutable int64_t lastRollingFeeUpdate;
499 : mutable bool blockSinceLastRollingFeeBump;
500 : mutable double rollingMinimumFeeRate; //!< minimum fee to get into the pool, decreases exponentially
501 : mutable uint64_t m_epoch;
502 : mutable bool m_has_epoch_guard;
503 :
504 : void trackPackageRemoved(const CFeeRate& rate) EXCLUSIVE_LOCKS_REQUIRED(cs);
505 :
506 : bool m_is_loaded GUARDED_BY(cs){false};
507 :
508 : public:
509 :
510 : static const int ROLLING_FEE_HALFLIFE = 60 * 60 * 12; // public only for testing
511 :
512 : typedef boost::multi_index_container<
513 : CTxMemPoolEntry,
514 : boost::multi_index::indexed_by<
515 : // sorted by txid
516 : boost::multi_index::hashed_unique<mempoolentry_txid, SaltedTxidHasher>,
517 : // sorted by wtxid
518 : boost::multi_index::hashed_unique<
519 : boost::multi_index::tag<index_by_wtxid>,
520 : mempoolentry_wtxid,
521 : SaltedTxidHasher
522 : >,
523 : // sorted by fee rate
524 : boost::multi_index::ordered_non_unique<
525 : boost::multi_index::tag<descendant_score>,
526 : boost::multi_index::identity<CTxMemPoolEntry>,
527 : CompareTxMemPoolEntryByDescendantScore
528 : >,
529 : // sorted by entry time
530 : boost::multi_index::ordered_non_unique<
531 : boost::multi_index::tag<entry_time>,
532 : boost::multi_index::identity<CTxMemPoolEntry>,
533 : CompareTxMemPoolEntryByEntryTime
534 : >,
535 : // sorted by fee rate with ancestors
536 : boost::multi_index::ordered_non_unique<
537 : boost::multi_index::tag<ancestor_score>,
538 : boost::multi_index::identity<CTxMemPoolEntry>,
539 : CompareTxMemPoolEntryByAncestorFee
540 : >
541 : >
542 : > indexed_transaction_set;
543 :
544 : /**
545 : * This mutex needs to be locked when accessing `mapTx` or other members
546 : * that are guarded by it.
547 : *
548 : * @par Consistency guarantees
549 : *
550 : * By design, it is guaranteed that:
551 : *
552 : * 1. Locking both `cs_main` and `mempool.cs` will give a view of mempool
553 : * that is consistent with current chain tip (`::ChainActive()` and
554 : * `CoinsTip()`) and is fully populated. Fully populated means that if the
555 : * current active chain is missing transactions that were present in a
556 : * previously active chain, all the missing transactions will have been
557 : * re-added to the mempool and should be present if they meet size and
558 : * consistency constraints.
559 : *
560 : * 2. Locking `mempool.cs` without `cs_main` will give a view of a mempool
561 : * consistent with some chain that was active since `cs_main` was last
562 : * locked, and that is fully populated as described above. It is ok for
563 : * code that only needs to query or remove transactions from the mempool
564 : * to lock just `mempool.cs` without `cs_main`.
565 : *
566 : * To provide these guarantees, it is necessary to lock both `cs_main` and
567 : * `mempool.cs` whenever adding transactions to the mempool and whenever
568 : * changing the chain tip. It's necessary to keep both mutexes locked until
569 : * the mempool is consistent with the new chain tip and fully populated.
570 : */
571 : mutable RecursiveMutex cs;
572 : indexed_transaction_set mapTx GUARDED_BY(cs);
573 :
574 : using txiter = indexed_transaction_set::nth_index<0>::type::const_iterator;
575 : std::vector<std::pair<uint256, txiter>> vTxHashes GUARDED_BY(cs); //!< All tx witness hashes/entries in mapTx, in random order
576 :
577 : typedef std::set<txiter, CompareIteratorByHash> setEntries;
578 :
579 : uint64_t CalculateDescendantMaximum(txiter entry) const EXCLUSIVE_LOCKS_REQUIRED(cs);
580 : private:
581 : typedef std::map<txiter, setEntries, CompareIteratorByHash> cacheMap;
582 :
583 :
584 : void UpdateParent(txiter entry, txiter parent, bool add) EXCLUSIVE_LOCKS_REQUIRED(cs);
585 : void UpdateChild(txiter entry, txiter child, bool add) EXCLUSIVE_LOCKS_REQUIRED(cs);
586 :
587 : std::vector<indexed_transaction_set::const_iterator> GetSortedDepthAndScore() const EXCLUSIVE_LOCKS_REQUIRED(cs);
588 :
589 : /**
590 : * track locally submitted transactions to periodically retry initial broadcast
591 : * map of txid -> wtxid
592 : */
593 : std::map<uint256, uint256> m_unbroadcast_txids GUARDED_BY(cs);
594 :
595 : public:
596 : indirectmap<COutPoint, const CTransaction*> mapNextTx GUARDED_BY(cs);
597 : std::map<uint256, CAmount> mapDeltas;
598 :
599 : /** Create a new CTxMemPool.
600 : */
601 : explicit CTxMemPool(CBlockPolicyEstimator* estimator = nullptr);
602 :
603 : /**
604 : * If sanity-checking is turned on, check makes sure the pool is
605 : * consistent (does not contain two transactions that spend the same inputs,
606 : * all inputs are in the mapNextTx array). If sanity-checking is turned off,
607 : * check does nothing.
608 : */
609 : void check(const CCoinsViewCache *pcoins) const;
610 603 : void setSanityCheck(double dFrequency = 1.0) { LOCK(cs); nCheckFrequency = static_cast<uint32_t>(dFrequency * 4294967295.0); }
611 :
612 : // addUnchecked must updated state for all ancestors of a given transaction,
613 : // to track size/count of descendant transactions. First version of
614 : // addUnchecked can be used to have it call CalculateMemPoolAncestors(), and
615 : // then invoke the second version.
616 : // Note that addUnchecked is ONLY called from ATMP outside of tests
617 : // and any other callers may break wallet's in-mempool tracking (due to
618 : // lack of CValidationInterface::TransactionAddedToMempool callbacks).
619 : void addUnchecked(const CTxMemPoolEntry& entry, bool validFeeEstimate = true) EXCLUSIVE_LOCKS_REQUIRED(cs, cs_main);
620 : void addUnchecked(const CTxMemPoolEntry& entry, setEntries& setAncestors, bool validFeeEstimate = true) EXCLUSIVE_LOCKS_REQUIRED(cs, cs_main);
621 :
622 : void removeRecursive(const CTransaction& tx, MemPoolRemovalReason reason) EXCLUSIVE_LOCKS_REQUIRED(cs);
623 : void removeForReorg(const CCoinsViewCache* pcoins, unsigned int nMemPoolHeight, int flags) EXCLUSIVE_LOCKS_REQUIRED(cs, cs_main);
624 : void removeConflicts(const CTransaction& tx) EXCLUSIVE_LOCKS_REQUIRED(cs);
625 : void removeForBlock(const std::vector<CTransactionRef>& vtx, unsigned int nBlockHeight) EXCLUSIVE_LOCKS_REQUIRED(cs);
626 :
627 : void clear();
628 : void _clear() EXCLUSIVE_LOCKS_REQUIRED(cs); //lock free
629 : bool CompareDepthAndScore(const uint256& hasha, const uint256& hashb, bool wtxid=false);
630 : void queryHashes(std::vector<uint256>& vtxid) const;
631 : bool isSpent(const COutPoint& outpoint) const;
632 : unsigned int GetTransactionsUpdated() const;
633 : void AddTransactionsUpdated(unsigned int n);
634 : /**
635 : * Check that none of this transactions inputs are in the mempool, and thus
636 : * the tx is not dependent on other mempool transactions to be included in a block.
637 : */
638 : bool HasNoInputsOf(const CTransaction& tx) const EXCLUSIVE_LOCKS_REQUIRED(cs);
639 :
640 : /** Affect CreateNewBlock prioritisation of transactions */
641 : void PrioritiseTransaction(const uint256& hash, const CAmount& nFeeDelta);
642 : void ApplyDelta(const uint256& hash, CAmount &nFeeDelta) const EXCLUSIVE_LOCKS_REQUIRED(cs);
643 : void ClearPrioritisation(const uint256& hash) EXCLUSIVE_LOCKS_REQUIRED(cs);
644 :
645 : /** Get the transaction in the pool that spends the same prevout */
646 : const CTransaction* GetConflictTx(const COutPoint& prevout) const EXCLUSIVE_LOCKS_REQUIRED(cs);
647 :
648 : /** Returns an iterator to the given hash, if found */
649 : Optional<txiter> GetIter(const uint256& txid) const EXCLUSIVE_LOCKS_REQUIRED(cs);
650 :
651 : /** Translate a set of hashes into a set of pool iterators to avoid repeated lookups */
652 : setEntries GetIterSet(const std::set<uint256>& hashes) const EXCLUSIVE_LOCKS_REQUIRED(cs);
653 :
654 : /** Remove a set of transactions from the mempool.
655 : * If a transaction is in this set, then all in-mempool descendants must
656 : * also be in the set, unless this transaction is being removed for being
657 : * in a block.
658 : * Set updateDescendants to true when removing a tx that was in a block, so
659 : * that any in-mempool descendants have their ancestor state updated.
660 : */
661 : void RemoveStaged(setEntries& stage, bool updateDescendants, MemPoolRemovalReason reason) EXCLUSIVE_LOCKS_REQUIRED(cs);
662 :
663 : /** When adding transactions from a disconnected block back to the mempool,
664 : * new mempool entries may have children in the mempool (which is generally
665 : * not the case when otherwise adding transactions).
666 : * UpdateTransactionsFromBlock() will find child transactions and update the
667 : * descendant state for each transaction in vHashesToUpdate (excluding any
668 : * child transactions present in vHashesToUpdate, which are already accounted
669 : * for). Note: vHashesToUpdate should be the set of transactions from the
670 : * disconnected block that have been accepted back into the mempool.
671 : */
672 : void UpdateTransactionsFromBlock(const std::vector<uint256>& vHashesToUpdate) EXCLUSIVE_LOCKS_REQUIRED(cs, cs_main);
673 :
674 : /** Try to calculate all in-mempool ancestors of entry.
675 : * (these are all calculated including the tx itself)
676 : * limitAncestorCount = max number of ancestors
677 : * limitAncestorSize = max size of ancestors
678 : * limitDescendantCount = max number of descendants any ancestor can have
679 : * limitDescendantSize = max size of descendants any ancestor can have
680 : * errString = populated with error reason if any limits are hit
681 : * fSearchForParents = whether to search a tx's vin for in-mempool parents, or
682 : * look up parents from mapLinks. Must be true for entries not in the mempool
683 : */
684 : 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);
685 :
686 : /** Populate setDescendants with all in-mempool descendants of hash.
687 : * Assumes that setDescendants includes all in-mempool descendants of anything
688 : * already in it. */
689 : void CalculateDescendants(txiter it, setEntries& setDescendants) const EXCLUSIVE_LOCKS_REQUIRED(cs);
690 :
691 : /** The minimum fee to get into the mempool, which may itself not be enough
692 : * for larger-sized transactions.
693 : * The incrementalRelayFee policy variable is used to bound the time it
694 : * takes the fee rate to go back down all the way to 0. When the feerate
695 : * would otherwise be half of this, it is set to 0 instead.
696 : */
697 : CFeeRate GetMinFee(size_t sizelimit) const;
698 :
699 : /** Remove transactions from the mempool until its dynamic size is <= sizelimit.
700 : * pvNoSpendsRemaining, if set, will be populated with the list of outpoints
701 : * which are not in mempool which no longer have any spends in this mempool.
702 : */
703 : void TrimToSize(size_t sizelimit, std::vector<COutPoint>* pvNoSpendsRemaining = nullptr) EXCLUSIVE_LOCKS_REQUIRED(cs);
704 :
705 : /** Expire all transaction (and their dependencies) in the mempool older than time. Return the number of removed transactions. */
706 : int Expire(std::chrono::seconds time) EXCLUSIVE_LOCKS_REQUIRED(cs);
707 :
708 : /**
709 : * Calculate the ancestor and descendant count for the given transaction.
710 : * The counts include the transaction itself.
711 : */
712 : void GetTransactionAncestry(const uint256& txid, size_t& ancestors, size_t& descendants) const;
713 :
714 : /** @returns true if the mempool is fully loaded */
715 : bool IsLoaded() const;
716 :
717 : /** Sets the current loaded state */
718 : void SetIsLoaded(bool loaded);
719 :
720 10235 : unsigned long size() const
721 : {
722 10235 : LOCK(cs);
723 10235 : return mapTx.size();
724 10235 : }
725 :
726 830 : uint64_t GetTotalTxSize() const EXCLUSIVE_LOCKS_REQUIRED(cs)
727 : {
728 830 : AssertLockHeld(cs);
729 830 : return totalTxSize;
730 : }
731 :
732 2230385 : bool exists(const GenTxid& gtxid) const
733 : {
734 2230385 : LOCK(cs);
735 2230385 : if (gtxid.IsWtxid()) {
736 34056 : return (mapTx.get<index_by_wtxid>().count(gtxid.GetHash()) != 0);
737 : }
738 2196329 : return (mapTx.count(gtxid.GetHash()) != 0);
739 2230385 : }
740 2196207 : bool exists(const uint256& txid) const { return exists(GenTxid{false, txid}); }
741 :
742 : CTransactionRef get(const uint256& hash) const;
743 137654 : txiter get_iter_from_wtxid(const uint256& wtxid) const EXCLUSIVE_LOCKS_REQUIRED(cs)
744 : {
745 137654 : AssertLockHeld(cs);
746 137654 : return mapTx.project<0>(mapTx.get<index_by_wtxid>().find(wtxid));
747 : }
748 : TxMempoolInfo info(const uint256& hash) const;
749 : TxMempoolInfo info(const GenTxid& gtxid) const;
750 : std::vector<TxMempoolInfo> infoAll() const;
751 :
752 : size_t DynamicMemoryUsage() const;
753 :
754 : /** Adds a transaction to the unbroadcast set */
755 8945 : void AddUnbroadcastTx(const uint256& txid, const uint256& wtxid) {
756 8945 : LOCK(cs);
757 : // Sanity Check: the transaction should also be in the mempool
758 8945 : if (exists(txid)) {
759 8945 : m_unbroadcast_txids[txid] = wtxid;
760 8945 : }
761 8945 : }
762 :
763 : /** Removes a transaction from the unbroadcast set */
764 : void RemoveUnbroadcastTx(const uint256& txid, const bool unchecked = false);
765 :
766 : /** Returns transactions in unbroadcast set */
767 1325 : std::map<uint256, uint256> GetUnbroadcastTxs() const {
768 1325 : LOCK(cs);
769 1325 : return m_unbroadcast_txids;
770 1325 : }
771 :
772 : /** Returns whether a txid is in the unbroadcast set */
773 53353 : bool IsUnbroadcastTx(const uint256& txid) const EXCLUSIVE_LOCKS_REQUIRED(cs)
774 : {
775 53353 : AssertLockHeld(cs);
776 53353 : return m_unbroadcast_txids.count(txid) != 0;
777 : }
778 :
779 : private:
780 : /** UpdateForDescendants is used by UpdateTransactionsFromBlock to update
781 : * the descendants for a single transaction that has been added to the
782 : * mempool but may have child transactions in the mempool, eg during a
783 : * chain reorg. setExclude is the set of descendant transactions in the
784 : * mempool that must not be accounted for (because any descendants in
785 : * setExclude were added to the mempool after the transaction being
786 : * updated and hence their state is already reflected in the parent
787 : * state).
788 : *
789 : * cachedDescendants will be updated with the descendants of the transaction
790 : * being updated, so that future invocations don't need to walk the
791 : * same transaction again, if encountered in another transaction chain.
792 : */
793 : void UpdateForDescendants(txiter updateIt,
794 : cacheMap &cachedDescendants,
795 : const std::set<uint256> &setExclude) EXCLUSIVE_LOCKS_REQUIRED(cs);
796 : /** Update ancestors of hash to add/remove it as a descendant transaction. */
797 : void UpdateAncestorsOf(bool add, txiter hash, setEntries &setAncestors) EXCLUSIVE_LOCKS_REQUIRED(cs);
798 : /** Set ancestor state for an entry */
799 : void UpdateEntryForAncestors(txiter it, const setEntries &setAncestors) EXCLUSIVE_LOCKS_REQUIRED(cs);
800 : /** For each transaction being removed, update ancestors and any direct children.
801 : * If updateDescendants is true, then also update in-mempool descendants'
802 : * ancestor state. */
803 : void UpdateForRemoveFromMempool(const setEntries &entriesToRemove, bool updateDescendants) EXCLUSIVE_LOCKS_REQUIRED(cs);
804 : /** Sever link between specified transaction and direct children. */
805 : void UpdateChildrenForRemoval(txiter entry) EXCLUSIVE_LOCKS_REQUIRED(cs);
806 :
807 : /** Before calling removeUnchecked for a given transaction,
808 : * UpdateForRemoveFromMempool must be called on the entire (dependent) set
809 : * of transactions being removed at the same time. We use each
810 : * CTxMemPoolEntry's setMemPoolParents in order to walk ancestors of a
811 : * given transaction that is removed, so we can't remove intermediate
812 : * transactions in a chain before we've updated all the state for the
813 : * removal.
814 : */
815 : void removeUnchecked(txiter entry, MemPoolRemovalReason reason) EXCLUSIVE_LOCKS_REQUIRED(cs);
816 : public:
817 : /** EpochGuard: RAII-style guard for using epoch-based graph traversal algorithms.
818 : * When walking ancestors or descendants, we generally want to avoid
819 : * visiting the same transactions twice. Some traversal algorithms use
820 : * std::set (or setEntries) to deduplicate the transaction we visit.
821 : * However, use of std::set is algorithmically undesirable because it both
822 : * adds an asymptotic factor of O(log n) to traverals cost and triggers O(n)
823 : * more dynamic memory allocations.
824 : * In many algorithms we can replace std::set with an internal mempool
825 : * counter to track the time (or, "epoch") that we began a traversal, and
826 : * check + update a per-transaction epoch for each transaction we look at to
827 : * determine if that transaction has not yet been visited during the current
828 : * traversal's epoch.
829 : * Algorithms using std::set can be replaced on a one by one basis.
830 : * Both techniques are not fundamentally incompatible across the codebase.
831 : * Generally speaking, however, the remaining use of std::set for mempool
832 : * traversal should be viewed as a TODO for replacement with an epoch based
833 : * traversal, rather than a preference for std::set over epochs in that
834 : * algorithm.
835 : */
836 : class EpochGuard {
837 : const CTxMemPool& pool;
838 : public:
839 : EpochGuard(const CTxMemPool& in);
840 : ~EpochGuard();
841 : };
842 : // N.B. GetFreshEpoch modifies mutable state via the EpochGuard construction
843 : // (and later destruction)
844 : EpochGuard GetFreshEpoch() const EXCLUSIVE_LOCKS_REQUIRED(cs);
845 :
846 : /** visited marks a CTxMemPoolEntry as having been traversed
847 : * during the lifetime of the most recently created EpochGuard
848 : * and returns false if we are the first visitor, true otherwise.
849 : *
850 : * An EpochGuard must be held when visited is called or an assert will be
851 : * triggered.
852 : *
853 : */
854 4724 : bool visited(txiter it) const EXCLUSIVE_LOCKS_REQUIRED(cs) {
855 4724 : assert(m_has_epoch_guard);
856 4724 : bool ret = it->m_epoch >= m_epoch;
857 4724 : it->m_epoch = std::max(it->m_epoch, m_epoch);
858 4724 : return ret;
859 : }
860 :
861 : bool visited(Optional<txiter> it) const EXCLUSIVE_LOCKS_REQUIRED(cs) {
862 : assert(m_has_epoch_guard);
863 : return !it || visited(*it);
864 : }
865 : };
866 :
867 : /**
868 : * CCoinsView that brings transactions from a mempool into view.
869 : * It does not check for spendings by memory pool transactions.
870 : * Instead, it provides access to all Coins which are either unspent in the
871 : * base CCoinsView, or are outputs from any mempool transaction!
872 : * This allows transaction replacement to work as expected, as you want to
873 : * have all inputs "available" to check signatures, and any cycles in the
874 : * dependency graph are checked directly in AcceptToMemoryPool.
875 : * It also allows you to sign a double-spend directly in
876 : * signrawtransactionwithkey and signrawtransactionwithwallet,
877 : * as long as the conflicting transaction is not yet confirmed.
878 : */
879 99068 : class CCoinsViewMemPool : public CCoinsViewBacked
880 : {
881 : protected:
882 : const CTxMemPool& mempool;
883 :
884 : public:
885 : CCoinsViewMemPool(CCoinsView* baseIn, const CTxMemPool& mempoolIn);
886 : bool GetCoin(const COutPoint &outpoint, Coin &coin) const override;
887 : };
888 :
889 : /**
890 : * DisconnectedBlockTransactions
891 :
892 : * During the reorg, it's desirable to re-add previously confirmed transactions
893 : * to the mempool, so that anything not re-confirmed in the new chain is
894 : * available to be mined. However, it's more efficient to wait until the reorg
895 : * is complete and process all still-unconfirmed transactions at that time,
896 : * since we expect most confirmed transactions to (typically) still be
897 : * confirmed in the new chain, and re-accepting to the memory pool is expensive
898 : * (and therefore better to not do in the middle of reorg-processing).
899 : * Instead, store the disconnected transactions (in order!) as we go, remove any
900 : * that are included in blocks in the new chain, and then process the remaining
901 : * still-unconfirmed transactions at the end.
902 : */
903 :
904 : // multi_index tag names
905 : struct txid_index {};
906 : struct insertion_order {};
907 :
908 133305 : struct DisconnectedBlockTransactions {
909 : typedef boost::multi_index_container<
910 : CTransactionRef,
911 : boost::multi_index::indexed_by<
912 : // sorted by txid
913 : boost::multi_index::hashed_unique<
914 : boost::multi_index::tag<txid_index>,
915 : mempoolentry_txid,
916 : SaltedTxidHasher
917 : >,
918 : // sorted by order in the blockchain
919 : boost::multi_index::sequenced<
920 : boost::multi_index::tag<insertion_order>
921 : >
922 : >
923 : > indexed_disconnected_transactions;
924 :
925 : // It's almost certainly a logic bug if we don't clear out queuedTx before
926 : // destruction, as we add to it while disconnecting blocks, and then we
927 : // need to re-process remaining transactions to ensure mempool consistency.
928 : // For now, assert() that we've emptied out this object on destruction.
929 : // This assert() can always be removed if the reorg-processing code were
930 : // to be refactored such that this assumption is no longer true (for
931 : // instance if there was some other way we cleaned up the mempool after a
932 : // reorg, besides draining this object).
933 88870 : ~DisconnectedBlockTransactions() { assert(queuedTx.empty()); }
934 :
935 : indexed_disconnected_transactions queuedTx;
936 44435 : uint64_t cachedInnerUsage = 0;
937 :
938 : // Estimate the overhead of queuedTx to be 6 pointers + an allocation, as
939 : // no exact formula for boost::multi_index_contained is implemented.
940 6342 : size_t DynamicMemoryUsage() const {
941 6342 : return memusage::MallocUsage(sizeof(CTransactionRef) + 6 * sizeof(void*)) * queuedTx.size() + cachedInnerUsage;
942 : }
943 :
944 9301 : void addTransaction(const CTransactionRef& tx)
945 : {
946 9301 : queuedTx.insert(tx);
947 9301 : cachedInnerUsage += RecursiveDynamicUsage(tx);
948 9301 : }
949 :
950 : // Remove entries based on txid_index, and update memory usage.
951 46544 : void removeForBlock(const std::vector<CTransactionRef>& vtx)
952 : {
953 : // Short-circuit in the common case of a block being added to the tip
954 46544 : if (queuedTx.empty()) {
955 : return;
956 : }
957 7800 : for (auto const &tx : vtx) {
958 5036 : auto it = queuedTx.find(tx->GetHash());
959 5036 : if (it != queuedTx.end()) {
960 53 : cachedInnerUsage -= RecursiveDynamicUsage(*it);
961 53 : queuedTx.erase(it);
962 53 : }
963 5036 : }
964 46544 : }
965 :
966 : // Remove an entry by insertion_order index, and update memory usage.
967 3205 : void removeEntry(indexed_disconnected_transactions::index<insertion_order>::type::iterator entry)
968 : {
969 3205 : cachedInnerUsage -= RecursiveDynamicUsage(*entry);
970 3205 : queuedTx.get<insertion_order>().erase(entry);
971 3205 : }
972 :
973 : void clear()
974 : {
975 : cachedInnerUsage = 0;
976 : queuedTx.clear();
977 : }
978 : };
979 :
980 : #endif // BITCOIN_TXMEMPOOL_H
|
