1 // Copyright (c) 2009-2010 Satoshi Nakamoto 2 // Copyright (c) 2009-2018 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 <memory> 10 #include <set> 11 #include <map> 12 #include <vector> 13 #include <utility> 14 #include <string> 15 16 #include <amount.h> 17 #include <coins.h> 18 #include <crypto/siphash.h> 19 #include <indirectmap.h> 20 #include <policy/feerate.h> 21 #include <primitives/transaction.h> 22 #include <sync.h> 23 #include <random.h> 24 25 #include <boost/multi_index_container.hpp> 26 #include <boost/multi_index/hashed_index.hpp> 27 #include <boost/multi_index/ordered_index.hpp> 28 #include <boost/multi_index/sequenced_index.hpp> 29 #include <boost/signals2/signal.hpp> 30 31 class CBlockIndex; 32 extern CCriticalSection 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 LockPointsLockPoints49 LockPoints() : height(0), time(0), maxInputBlock(nullptr) { } 50 }; 51 52 class CTxMemPool; 53 54 /** \class CTxMemPoolEntry 55 * 56 * CTxMemPoolEntry stores data about the corresponding transaction, as well 57 * as data about all in-mempool transactions that depend on the transaction 58 * ("descendant" transactions). 59 * 60 * When a new entry is added to the mempool, we update the descendant state 61 * (nCountWithDescendants, nSizeWithDescendants, and nModFeesWithDescendants) for 62 * all ancestors of the newly added transaction. 63 * 64 */ 65 66 class CTxMemPoolEntry 67 { 68 private: 69 const CTransactionRef tx; 70 const CAmount nFee; //!< Cached to avoid expensive parent-transaction lookups 71 const size_t nTxWeight; //!< ... and avoid recomputing tx weight (also used for GetTxSize()) 72 const size_t nUsageSize; //!< ... and total memory usage 73 const int64_t nTime; //!< Local time when entering the mempool 74 const unsigned int entryHeight; //!< Chain height when entering the mempool 75 const bool spendsCoinbase; //!< keep track of transactions that spend a coinbase 76 const int64_t sigOpCost; //!< Total sigop cost 77 int64_t feeDelta; //!< Used for determining the priority of the transaction for mining in a block 78 LockPoints lockPoints; //!< Track the height and time at which tx was final 79 80 // Information about descendants of this transaction that are in the 81 // mempool; if we remove this transaction we must remove all of these 82 // descendants as well. 83 uint64_t nCountWithDescendants; //!< number of descendant transactions 84 uint64_t nSizeWithDescendants; //!< ... and size 85 CAmount nModFeesWithDescendants; //!< ... and total fees (all including us) 86 87 // Analogous statistics for ancestor transactions 88 uint64_t nCountWithAncestors; 89 uint64_t nSizeWithAncestors; 90 CAmount nModFeesWithAncestors; 91 int64_t nSigOpCostWithAncestors; 92 93 public: 94 CTxMemPoolEntry(const CTransactionRef& _tx, const CAmount& _nFee, 95 int64_t _nTime, unsigned int _entryHeight, 96 bool spendsCoinbase, 97 int64_t nSigOpsCost, LockPoints lp); 98 GetTx()99 const CTransaction& GetTx() const { return *this->tx; } GetSharedTx()100 CTransactionRef GetSharedTx() const { return this->tx; } GetFee()101 const CAmount& GetFee() const { return nFee; } 102 size_t GetTxSize() const; GetTxWeight()103 size_t GetTxWeight() const { return nTxWeight; } GetTime()104 int64_t GetTime() const { return nTime; } GetHeight()105 unsigned int GetHeight() const { return entryHeight; } GetSigOpCost()106 int64_t GetSigOpCost() const { return sigOpCost; } GetModifiedFee()107 int64_t GetModifiedFee() const { return nFee + feeDelta; } DynamicMemoryUsage()108 size_t DynamicMemoryUsage() const { return nUsageSize; } GetLockPoints()109 const LockPoints& GetLockPoints() const { return lockPoints; } 110 111 // Adjusts the descendant state. 112 void UpdateDescendantState(int64_t modifySize, CAmount modifyFee, int64_t modifyCount); 113 // Adjusts the ancestor state 114 void UpdateAncestorState(int64_t modifySize, CAmount modifyFee, int64_t modifyCount, int64_t modifySigOps); 115 // Updates the fee delta used for mining priority score, and the 116 // modified fees with descendants. 117 void UpdateFeeDelta(int64_t feeDelta); 118 // Update the LockPoints after a reorg 119 void UpdateLockPoints(const LockPoints& lp); 120 GetCountWithDescendants()121 uint64_t GetCountWithDescendants() const { return nCountWithDescendants; } GetSizeWithDescendants()122 uint64_t GetSizeWithDescendants() const { return nSizeWithDescendants; } GetModFeesWithDescendants()123 CAmount GetModFeesWithDescendants() const { return nModFeesWithDescendants; } 124 GetSpendsCoinbase()125 bool GetSpendsCoinbase() const { return spendsCoinbase; } 126 GetCountWithAncestors()127 uint64_t GetCountWithAncestors() const { return nCountWithAncestors; } GetSizeWithAncestors()128 uint64_t GetSizeWithAncestors() const { return nSizeWithAncestors; } GetModFeesWithAncestors()129 CAmount GetModFeesWithAncestors() const { return nModFeesWithAncestors; } GetSigOpCostWithAncestors()130 int64_t GetSigOpCostWithAncestors() const { return nSigOpCostWithAncestors; } 131 132 mutable size_t vTxHashesIdx; //!< Index in mempool's vTxHashes 133 }; 134 135 // Helpers for modifying CTxMemPool::mapTx, which is a boost multi_index. 136 struct update_descendant_state 137 { update_descendant_stateupdate_descendant_state138 update_descendant_state(int64_t _modifySize, CAmount _modifyFee, int64_t _modifyCount) : 139 modifySize(_modifySize), modifyFee(_modifyFee), modifyCount(_modifyCount) 140 {} 141 operatorupdate_descendant_state142 void operator() (CTxMemPoolEntry &e) 143 { e.UpdateDescendantState(modifySize, modifyFee, modifyCount); } 144 145 private: 146 int64_t modifySize; 147 CAmount modifyFee; 148 int64_t modifyCount; 149 }; 150 151 struct update_ancestor_state 152 { update_ancestor_stateupdate_ancestor_state153 update_ancestor_state(int64_t _modifySize, CAmount _modifyFee, int64_t _modifyCount, int64_t _modifySigOpsCost) : 154 modifySize(_modifySize), modifyFee(_modifyFee), modifyCount(_modifyCount), modifySigOpsCost(_modifySigOpsCost) 155 {} 156 operatorupdate_ancestor_state157 void operator() (CTxMemPoolEntry &e) 158 { e.UpdateAncestorState(modifySize, modifyFee, modifyCount, modifySigOpsCost); } 159 160 private: 161 int64_t modifySize; 162 CAmount modifyFee; 163 int64_t modifyCount; 164 int64_t modifySigOpsCost; 165 }; 166 167 struct update_fee_delta 168 { update_fee_deltaupdate_fee_delta169 explicit update_fee_delta(int64_t _feeDelta) : feeDelta(_feeDelta) { } 170 operatorupdate_fee_delta171 void operator() (CTxMemPoolEntry &e) { e.UpdateFeeDelta(feeDelta); } 172 173 private: 174 int64_t feeDelta; 175 }; 176 177 struct update_lock_points 178 { update_lock_pointsupdate_lock_points179 explicit update_lock_points(const LockPoints& _lp) : lp(_lp) { } 180 operatorupdate_lock_points181 void operator() (CTxMemPoolEntry &e) { e.UpdateLockPoints(lp); } 182 183 private: 184 const LockPoints& lp; 185 }; 186 187 // extracts a transaction hash from CTxMempoolEntry or CTransactionRef 188 struct mempoolentry_txid 189 { 190 typedef uint256 result_type; operatormempoolentry_txid191 result_type operator() (const CTxMemPoolEntry &entry) const 192 { 193 return entry.GetTx().GetHash(); 194 } 195 operatormempoolentry_txid196 result_type operator() (const CTransactionRef& tx) const 197 { 198 return tx->GetHash(); 199 } 200 }; 201 202 /** \class CompareTxMemPoolEntryByDescendantScore 203 * 204 * Sort an entry by max(score/size of entry's tx, score/size with all descendants). 205 */ 206 class CompareTxMemPoolEntryByDescendantScore 207 { 208 public: operator()209 bool operator()(const CTxMemPoolEntry& a, const CTxMemPoolEntry& b) const 210 { 211 double a_mod_fee, a_size, b_mod_fee, b_size; 212 213 GetModFeeAndSize(a, a_mod_fee, a_size); 214 GetModFeeAndSize(b, b_mod_fee, b_size); 215 216 // Avoid division by rewriting (a/b > c/d) as (a*d > c*b). 217 double f1 = a_mod_fee * b_size; 218 double f2 = a_size * b_mod_fee; 219 220 if (f1 == f2) { 221 return a.GetTime() >= b.GetTime(); 222 } 223 return f1 < f2; 224 } 225 226 // Return the fee/size we're using for sorting this entry. GetModFeeAndSize(const CTxMemPoolEntry & a,double & mod_fee,double & size)227 void GetModFeeAndSize(const CTxMemPoolEntry &a, double &mod_fee, double &size) const 228 { 229 // Compare feerate with descendants to feerate of the transaction, and 230 // return the fee/size for the max. 231 double f1 = (double)a.GetModifiedFee() * a.GetSizeWithDescendants(); 232 double f2 = (double)a.GetModFeesWithDescendants() * a.GetTxSize(); 233 234 if (f2 > f1) { 235 mod_fee = a.GetModFeesWithDescendants(); 236 size = a.GetSizeWithDescendants(); 237 } else { 238 mod_fee = a.GetModifiedFee(); 239 size = a.GetTxSize(); 240 } 241 } 242 }; 243 244 /** \class CompareTxMemPoolEntryByScore 245 * 246 * Sort by feerate of entry (fee/size) in descending order 247 * This is only used for transaction relay, so we use GetFee() 248 * instead of GetModifiedFee() to avoid leaking prioritization 249 * information via the sort order. 250 */ 251 class CompareTxMemPoolEntryByScore 252 { 253 public: operator()254 bool operator()(const CTxMemPoolEntry& a, const CTxMemPoolEntry& b) const 255 { 256 double f1 = (double)a.GetFee() * b.GetTxSize(); 257 double f2 = (double)b.GetFee() * a.GetTxSize(); 258 if (f1 == f2) { 259 return b.GetTx().GetHash() < a.GetTx().GetHash(); 260 } 261 return f1 > f2; 262 } 263 }; 264 265 class CompareTxMemPoolEntryByEntryTime 266 { 267 public: operator()268 bool operator()(const CTxMemPoolEntry& a, const CTxMemPoolEntry& b) const 269 { 270 return a.GetTime() < b.GetTime(); 271 } 272 }; 273 274 /** \class CompareTxMemPoolEntryByAncestorScore 275 * 276 * Sort an entry by min(score/size of entry's tx, score/size with all ancestors). 277 */ 278 class CompareTxMemPoolEntryByAncestorFee 279 { 280 public: 281 template<typename T> operator()282 bool operator()(const T& a, const T& b) const 283 { 284 double a_mod_fee, a_size, b_mod_fee, b_size; 285 286 GetModFeeAndSize(a, a_mod_fee, a_size); 287 GetModFeeAndSize(b, b_mod_fee, b_size); 288 289 // Avoid division by rewriting (a/b > c/d) as (a*d > c*b). 290 double f1 = a_mod_fee * b_size; 291 double f2 = a_size * b_mod_fee; 292 293 if (f1 == f2) { 294 return a.GetTx().GetHash() < b.GetTx().GetHash(); 295 } 296 return f1 > f2; 297 } 298 299 // Return the fee/size we're using for sorting this entry. 300 template <typename T> GetModFeeAndSize(const T & a,double & mod_fee,double & size)301 void GetModFeeAndSize(const T &a, double &mod_fee, double &size) const 302 { 303 // Compare feerate with ancestors to feerate of the transaction, and 304 // return the fee/size for the min. 305 double f1 = (double)a.GetModifiedFee() * a.GetSizeWithAncestors(); 306 double f2 = (double)a.GetModFeesWithAncestors() * a.GetTxSize(); 307 308 if (f1 > f2) { 309 mod_fee = a.GetModFeesWithAncestors(); 310 size = a.GetSizeWithAncestors(); 311 } else { 312 mod_fee = a.GetModifiedFee(); 313 size = a.GetTxSize(); 314 } 315 } 316 }; 317 318 // Multi_index tag names 319 struct descendant_score {}; 320 struct entry_time {}; 321 struct ancestor_score {}; 322 323 class CBlockPolicyEstimator; 324 325 /** 326 * Information about a mempool transaction. 327 */ 328 struct TxMempoolInfo 329 { 330 /** The transaction itself */ 331 CTransactionRef tx; 332 333 /** Time the transaction entered the mempool. */ 334 int64_t nTime; 335 336 /** Feerate of the transaction. */ 337 CFeeRate feeRate; 338 339 /** The fee delta. */ 340 int64_t nFeeDelta; 341 }; 342 343 /** Reason why a transaction was removed from the mempool, 344 * this is passed to the notification signal. 345 */ 346 enum class MemPoolRemovalReason { 347 UNKNOWN = 0, //!< Manually removed or unknown reason 348 EXPIRY, //!< Expired from mempool 349 SIZELIMIT, //!< Removed in size limiting 350 REORG, //!< Removed for reorganization 351 BLOCK, //!< Removed for block 352 CONFLICT, //!< Removed for conflict with in-block transaction 353 REPLACED, //!< Removed for replacement 354 }; 355 356 class SaltedTxidHasher 357 { 358 private: 359 /** Salt */ 360 const uint64_t k0, k1; 361 362 public: 363 SaltedTxidHasher(); 364 operator()365 size_t operator()(const uint256& txid) const { 366 return SipHashUint256(k0, k1, txid); 367 } 368 }; 369 370 /** 371 * CTxMemPool stores valid-according-to-the-current-best-chain transactions 372 * that may be included in the next block. 373 * 374 * Transactions are added when they are seen on the network (or created by the 375 * local node), but not all transactions seen are added to the pool. For 376 * example, the following new transactions will not be added to the mempool: 377 * - a transaction which doesn't meet the minimum fee requirements. 378 * - a new transaction that double-spends an input of a transaction already in 379 * the pool where the new transaction does not meet the Replace-By-Fee 380 * requirements as defined in BIP 125. 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 private: 445 uint32_t nCheckFrequency GUARDED_BY(cs); //!< Value n means that n times in 2^32 we check. 446 unsigned int nTransactionsUpdated; //!< Used by getblocktemplate to trigger CreateNewBlock() invocation 447 CBlockPolicyEstimator* minerPolicyEstimator; 448 449 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. 450 uint64_t cachedInnerUsage; //!< sum of dynamic memory usage of all the map elements (NOT the maps themselves) 451 452 mutable int64_t lastRollingFeeUpdate; 453 mutable bool blockSinceLastRollingFeeBump; 454 mutable double rollingMinimumFeeRate; //!< minimum fee to get into the pool, decreases exponentially 455 456 void trackPackageRemoved(const CFeeRate& rate) EXCLUSIVE_LOCKS_REQUIRED(cs); 457 458 public: 459 460 static const int ROLLING_FEE_HALFLIFE = 60 * 60 * 12; // public only for testing 461 462 typedef boost::multi_index_container< 463 CTxMemPoolEntry, 464 boost::multi_index::indexed_by< 465 // sorted by txid 466 boost::multi_index::hashed_unique<mempoolentry_txid, SaltedTxidHasher>, 467 // sorted by fee rate 468 boost::multi_index::ordered_non_unique< 469 boost::multi_index::tag<descendant_score>, 470 boost::multi_index::identity<CTxMemPoolEntry>, 471 CompareTxMemPoolEntryByDescendantScore 472 >, 473 // sorted by entry time 474 boost::multi_index::ordered_non_unique< 475 boost::multi_index::tag<entry_time>, 476 boost::multi_index::identity<CTxMemPoolEntry>, 477 CompareTxMemPoolEntryByEntryTime 478 >, 479 // sorted by fee rate with ancestors 480 boost::multi_index::ordered_non_unique< 481 boost::multi_index::tag<ancestor_score>, 482 boost::multi_index::identity<CTxMemPoolEntry>, 483 CompareTxMemPoolEntryByAncestorFee 484 > 485 > 486 > indexed_transaction_set; 487 488 /** 489 * This mutex needs to be locked when accessing `mapTx` or other members 490 * that are guarded by it. 491 * 492 * @par Consistency guarantees 493 * 494 * By design, it is guaranteed that: 495 * 496 * 1. Locking both `cs_main` and `mempool.cs` will give a view of mempool 497 * that is consistent with current chain tip (`chainActive` and 498 * `pcoinsTip`) and is fully populated. Fully populated means that if the 499 * current active chain is missing transactions that were present in a 500 * previously active chain, all the missing transactions will have been 501 * re-added to the mempool and should be present if they meet size and 502 * consistency constraints. 503 * 504 * 2. Locking `mempool.cs` without `cs_main` will give a view of a mempool 505 * consistent with some chain that was active since `cs_main` was last 506 * locked, and that is fully populated as described above. It is ok for 507 * code that only needs to query or remove transactions from the mempool 508 * to lock just `mempool.cs` without `cs_main`. 509 * 510 * To provide these guarantees, it is necessary to lock both `cs_main` and 511 * `mempool.cs` whenever adding transactions to the mempool and whenever 512 * changing the chain tip. It's necessary to keep both mutexes locked until 513 * the mempool is consistent with the new chain tip and fully populated. 514 * 515 * @par Consistency bug 516 * 517 * The second guarantee above is not currently enforced, but 518 * https://github.com/bitcoin/bitcoin/pull/14193 will fix it. No known code 519 * in bitcoin currently depends on second guarantee, but it is important to 520 * fix for third party code that needs be able to frequently poll the 521 * mempool without locking `cs_main` and without encountering missing 522 * transactions during reorgs. 523 */ 524 mutable RecursiveMutex cs; 525 indexed_transaction_set mapTx GUARDED_BY(cs); 526 527 using txiter = indexed_transaction_set::nth_index<0>::type::const_iterator; 528 std::vector<std::pair<uint256, txiter> > vTxHashes; //!< All tx witness hashes/entries in mapTx, in random order 529 530 struct CompareIteratorByHash { operatorCompareIteratorByHash531 bool operator()(const txiter &a, const txiter &b) const { 532 return a->GetTx().GetHash() < b->GetTx().GetHash(); 533 } 534 }; 535 typedef std::set<txiter, CompareIteratorByHash> setEntries; 536 537 const setEntries & GetMemPoolParents(txiter entry) const EXCLUSIVE_LOCKS_REQUIRED(cs); 538 const setEntries & GetMemPoolChildren(txiter entry) const EXCLUSIVE_LOCKS_REQUIRED(cs); 539 uint64_t CalculateDescendantMaximum(txiter entry) const EXCLUSIVE_LOCKS_REQUIRED(cs); 540 private: 541 typedef std::map<txiter, setEntries, CompareIteratorByHash> cacheMap; 542 543 struct TxLinks { 544 setEntries parents; 545 setEntries children; 546 }; 547 548 typedef std::map<txiter, TxLinks, CompareIteratorByHash> txlinksMap; 549 txlinksMap mapLinks; 550 551 void UpdateParent(txiter entry, txiter parent, bool add); 552 void UpdateChild(txiter entry, txiter child, bool add); 553 554 std::vector<indexed_transaction_set::const_iterator> GetSortedDepthAndScore() const EXCLUSIVE_LOCKS_REQUIRED(cs); 555 556 public: 557 indirectmap<COutPoint, const CTransaction*> mapNextTx GUARDED_BY(cs); 558 std::map<uint256, CAmount> mapDeltas; 559 560 /** Create a new CTxMemPool. 561 */ 562 explicit CTxMemPool(CBlockPolicyEstimator* estimator = nullptr); 563 564 /** 565 * If sanity-checking is turned on, check makes sure the pool is 566 * consistent (does not contain two transactions that spend the same inputs, 567 * all inputs are in the mapNextTx array). If sanity-checking is turned off, 568 * check does nothing. 569 */ 570 void check(const CCoinsViewCache *pcoins) const; 571 void setSanityCheck(double dFrequency = 1.0) { LOCK(cs); nCheckFrequency = static_cast<uint32_t>(dFrequency * 4294967295.0); } 572 573 // addUnchecked must updated state for all ancestors of a given transaction, 574 // to track size/count of descendant transactions. First version of 575 // addUnchecked can be used to have it call CalculateMemPoolAncestors(), and 576 // then invoke the second version. 577 // Note that addUnchecked is ONLY called from ATMP outside of tests 578 // and any other callers may break wallet's in-mempool tracking (due to 579 // lack of CValidationInterface::TransactionAddedToMempool callbacks). 580 void addUnchecked(const CTxMemPoolEntry& entry, bool validFeeEstimate = true) EXCLUSIVE_LOCKS_REQUIRED(cs, cs_main); 581 void addUnchecked(const CTxMemPoolEntry& entry, setEntries& setAncestors, bool validFeeEstimate = true) EXCLUSIVE_LOCKS_REQUIRED(cs, cs_main); 582 583 void removeRecursive(const CTransaction &tx, MemPoolRemovalReason reason = MemPoolRemovalReason::UNKNOWN); 584 void removeForReorg(const CCoinsViewCache *pcoins, unsigned int nMemPoolHeight, int flags) EXCLUSIVE_LOCKS_REQUIRED(cs_main); 585 void removeConflicts(const CTransaction &tx) EXCLUSIVE_LOCKS_REQUIRED(cs); 586 void removeForBlock(const std::vector<CTransactionRef>& vtx, unsigned int nBlockHeight); 587 588 void clear(); 589 void _clear() EXCLUSIVE_LOCKS_REQUIRED(cs); //lock free 590 bool CompareDepthAndScore(const uint256& hasha, const uint256& hashb); 591 void queryHashes(std::vector<uint256>& vtxid); 592 bool isSpent(const COutPoint& outpoint) const; 593 unsigned int GetTransactionsUpdated() const; 594 void AddTransactionsUpdated(unsigned int n); 595 /** 596 * Check that none of this transactions inputs are in the mempool, and thus 597 * the tx is not dependent on other mempool transactions to be included in a block. 598 */ 599 bool HasNoInputsOf(const CTransaction& tx) const; 600 601 /** Affect CreateNewBlock prioritisation of transactions */ 602 void PrioritiseTransaction(const uint256& hash, const CAmount& nFeeDelta); 603 void ApplyDelta(const uint256 hash, CAmount &nFeeDelta) const; 604 void ClearPrioritisation(const uint256 hash); 605 606 /** Get the transaction in the pool that spends the same prevout */ 607 const CTransaction* GetConflictTx(const COutPoint& prevout) const EXCLUSIVE_LOCKS_REQUIRED(cs); 608 609 /** Returns an iterator to the given hash, if found */ 610 boost::optional<txiter> GetIter(const uint256& txid) const EXCLUSIVE_LOCKS_REQUIRED(cs); 611 612 /** Translate a set of hashes into a set of pool iterators to avoid repeated lookups */ 613 setEntries GetIterSet(const std::set<uint256>& hashes) const EXCLUSIVE_LOCKS_REQUIRED(cs); 614 615 /** Remove a set of transactions from the mempool. 616 * If a transaction is in this set, then all in-mempool descendants must 617 * also be in the set, unless this transaction is being removed for being 618 * in a block. 619 * Set updateDescendants to true when removing a tx that was in a block, so 620 * that any in-mempool descendants have their ancestor state updated. 621 */ 622 void RemoveStaged(setEntries &stage, bool updateDescendants, MemPoolRemovalReason reason = MemPoolRemovalReason::UNKNOWN) EXCLUSIVE_LOCKS_REQUIRED(cs); 623 624 /** When adding transactions from a disconnected block back to the mempool, 625 * new mempool entries may have children in the mempool (which is generally 626 * not the case when otherwise adding transactions). 627 * UpdateTransactionsFromBlock() will find child transactions and update the 628 * descendant state for each transaction in vHashesToUpdate (excluding any 629 * child transactions present in vHashesToUpdate, which are already accounted 630 * for). Note: vHashesToUpdate should be the set of transactions from the 631 * disconnected block that have been accepted back into the mempool. 632 */ 633 void UpdateTransactionsFromBlock(const std::vector<uint256>& vHashesToUpdate) EXCLUSIVE_LOCKS_REQUIRED(cs_main); 634 635 /** Try to calculate all in-mempool ancestors of entry. 636 * (these are all calculated including the tx itself) 637 * limitAncestorCount = max number of ancestors 638 * limitAncestorSize = max size of ancestors 639 * limitDescendantCount = max number of descendants any ancestor can have 640 * limitDescendantSize = max size of descendants any ancestor can have 641 * errString = populated with error reason if any limits are hit 642 * fSearchForParents = whether to search a tx's vin for in-mempool parents, or 643 * look up parents from mapLinks. Must be true for entries not in the mempool 644 */ 645 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); 646 647 /** Populate setDescendants with all in-mempool descendants of hash. 648 * Assumes that setDescendants includes all in-mempool descendants of anything 649 * already in it. */ 650 void CalculateDescendants(txiter it, setEntries& setDescendants) const EXCLUSIVE_LOCKS_REQUIRED(cs); 651 652 /** The minimum fee to get into the mempool, which may itself not be enough 653 * for larger-sized transactions. 654 * The incrementalRelayFee policy variable is used to bound the time it 655 * takes the fee rate to go back down all the way to 0. When the feerate 656 * would otherwise be half of this, it is set to 0 instead. 657 */ 658 CFeeRate GetMinFee(size_t sizelimit) const; 659 660 /** Remove transactions from the mempool until its dynamic size is <= sizelimit. 661 * pvNoSpendsRemaining, if set, will be populated with the list of outpoints 662 * which are not in mempool which no longer have any spends in this mempool. 663 */ 664 void TrimToSize(size_t sizelimit, std::vector<COutPoint>* pvNoSpendsRemaining=nullptr); 665 666 /** Expire all transaction (and their dependencies) in the mempool older than time. Return the number of removed transactions. */ 667 int Expire(int64_t time); 668 669 /** 670 * Calculate the ancestor and descendant count for the given transaction. 671 * The counts include the transaction itself. 672 */ 673 void GetTransactionAncestry(const uint256& txid, size_t& ancestors, size_t& descendants) const; 674 size()675 unsigned long size() const 676 { 677 LOCK(cs); 678 return mapTx.size(); 679 } 680 GetTotalTxSize()681 uint64_t GetTotalTxSize() const 682 { 683 LOCK(cs); 684 return totalTxSize; 685 } 686 exists(const uint256 & hash)687 bool exists(const uint256& hash) const 688 { 689 LOCK(cs); 690 return (mapTx.count(hash) != 0); 691 } 692 693 CTransactionRef get(const uint256& hash) const; 694 TxMempoolInfo info(const uint256& hash) const; 695 std::vector<TxMempoolInfo> infoAll() const; 696 697 size_t DynamicMemoryUsage() const; 698 699 boost::signals2::signal<void (CTransactionRef)> NotifyEntryAdded; 700 boost::signals2::signal<void (CTransactionRef, MemPoolRemovalReason)> NotifyEntryRemoved; 701 702 private: 703 /** UpdateForDescendants is used by UpdateTransactionsFromBlock to update 704 * the descendants for a single transaction that has been added to the 705 * mempool but may have child transactions in the mempool, eg during a 706 * chain reorg. setExclude is the set of descendant transactions in the 707 * mempool that must not be accounted for (because any descendants in 708 * setExclude were added to the mempool after the transaction being 709 * updated and hence their state is already reflected in the parent 710 * state). 711 * 712 * cachedDescendants will be updated with the descendants of the transaction 713 * being updated, so that future invocations don't need to walk the 714 * same transaction again, if encountered in another transaction chain. 715 */ 716 void UpdateForDescendants(txiter updateIt, 717 cacheMap &cachedDescendants, 718 const std::set<uint256> &setExclude) EXCLUSIVE_LOCKS_REQUIRED(cs); 719 /** Update ancestors of hash to add/remove it as a descendant transaction. */ 720 void UpdateAncestorsOf(bool add, txiter hash, setEntries &setAncestors) EXCLUSIVE_LOCKS_REQUIRED(cs); 721 /** Set ancestor state for an entry */ 722 void UpdateEntryForAncestors(txiter it, const setEntries &setAncestors) EXCLUSIVE_LOCKS_REQUIRED(cs); 723 /** For each transaction being removed, update ancestors and any direct children. 724 * If updateDescendants is true, then also update in-mempool descendants' 725 * ancestor state. */ 726 void UpdateForRemoveFromMempool(const setEntries &entriesToRemove, bool updateDescendants) EXCLUSIVE_LOCKS_REQUIRED(cs); 727 /** Sever link between specified transaction and direct children. */ 728 void UpdateChildrenForRemoval(txiter entry) EXCLUSIVE_LOCKS_REQUIRED(cs); 729 730 /** Before calling removeUnchecked for a given transaction, 731 * UpdateForRemoveFromMempool must be called on the entire (dependent) set 732 * of transactions being removed at the same time. We use each 733 * CTxMemPoolEntry's setMemPoolParents in order to walk ancestors of a 734 * given transaction that is removed, so we can't remove intermediate 735 * transactions in a chain before we've updated all the state for the 736 * removal. 737 */ 738 void removeUnchecked(txiter entry, MemPoolRemovalReason reason = MemPoolRemovalReason::UNKNOWN) EXCLUSIVE_LOCKS_REQUIRED(cs); 739 }; 740 741 /** 742 * CCoinsView that brings transactions from a mempool into view. 743 * It does not check for spendings by memory pool transactions. 744 * Instead, it provides access to all Coins which are either unspent in the 745 * base CCoinsView, or are outputs from any mempool transaction! 746 * This allows transaction replacement to work as expected, as you want to 747 * have all inputs "available" to check signatures, and any cycles in the 748 * dependency graph are checked directly in AcceptToMemoryPool. 749 * It also allows you to sign a double-spend directly in 750 * signrawtransactionwithkey and signrawtransactionwithwallet, 751 * as long as the conflicting transaction is not yet confirmed. 752 */ 753 class CCoinsViewMemPool : public CCoinsViewBacked 754 { 755 protected: 756 const CTxMemPool& mempool; 757 758 public: 759 CCoinsViewMemPool(CCoinsView* baseIn, const CTxMemPool& mempoolIn); 760 bool GetCoin(const COutPoint &outpoint, Coin &coin) const override; 761 }; 762 763 /** 764 * DisconnectedBlockTransactions 765 766 * During the reorg, it's desirable to re-add previously confirmed transactions 767 * to the mempool, so that anything not re-confirmed in the new chain is 768 * available to be mined. However, it's more efficient to wait until the reorg 769 * is complete and process all still-unconfirmed transactions at that time, 770 * since we expect most confirmed transactions to (typically) still be 771 * confirmed in the new chain, and re-accepting to the memory pool is expensive 772 * (and therefore better to not do in the middle of reorg-processing). 773 * Instead, store the disconnected transactions (in order!) as we go, remove any 774 * that are included in blocks in the new chain, and then process the remaining 775 * still-unconfirmed transactions at the end. 776 */ 777 778 // multi_index tag names 779 struct txid_index {}; 780 struct insertion_order {}; 781 782 struct DisconnectedBlockTransactions { 783 typedef boost::multi_index_container< 784 CTransactionRef, 785 boost::multi_index::indexed_by< 786 // sorted by txid 787 boost::multi_index::hashed_unique< 788 boost::multi_index::tag<txid_index>, 789 mempoolentry_txid, 790 SaltedTxidHasher 791 >, 792 // sorted by order in the blockchain 793 boost::multi_index::sequenced< 794 boost::multi_index::tag<insertion_order> 795 > 796 > 797 > indexed_disconnected_transactions; 798 799 // It's almost certainly a logic bug if we don't clear out queuedTx before 800 // destruction, as we add to it while disconnecting blocks, and then we 801 // need to re-process remaining transactions to ensure mempool consistency. 802 // For now, assert() that we've emptied out this object on destruction. 803 // This assert() can always be removed if the reorg-processing code were 804 // to be refactored such that this assumption is no longer true (for 805 // instance if there was some other way we cleaned up the mempool after a 806 // reorg, besides draining this object). ~DisconnectedBlockTransactionsDisconnectedBlockTransactions807 ~DisconnectedBlockTransactions() { assert(queuedTx.empty()); } 808 809 indexed_disconnected_transactions queuedTx; 810 uint64_t cachedInnerUsage = 0; 811 812 // Estimate the overhead of queuedTx to be 6 pointers + an allocation, as 813 // no exact formula for boost::multi_index_contained is implemented. DynamicMemoryUsageDisconnectedBlockTransactions814 size_t DynamicMemoryUsage() const { 815 return memusage::MallocUsage(sizeof(CTransactionRef) + 6 * sizeof(void*)) * queuedTx.size() + cachedInnerUsage; 816 } 817 addTransactionDisconnectedBlockTransactions818 void addTransaction(const CTransactionRef& tx) 819 { 820 queuedTx.insert(tx); 821 cachedInnerUsage += RecursiveDynamicUsage(tx); 822 } 823 824 // Remove entries based on txid_index, and update memory usage. removeForBlockDisconnectedBlockTransactions825 void removeForBlock(const std::vector<CTransactionRef>& vtx) 826 { 827 // Short-circuit in the common case of a block being added to the tip 828 if (queuedTx.empty()) { 829 return; 830 } 831 for (auto const &tx : vtx) { 832 auto it = queuedTx.find(tx->GetHash()); 833 if (it != queuedTx.end()) { 834 cachedInnerUsage -= RecursiveDynamicUsage(*it); 835 queuedTx.erase(it); 836 } 837 } 838 } 839 840 // Remove an entry by insertion_order index, and update memory usage. removeEntryDisconnectedBlockTransactions841 void removeEntry(indexed_disconnected_transactions::index<insertion_order>::type::iterator entry) 842 { 843 cachedInnerUsage -= RecursiveDynamicUsage(*entry); 844 queuedTx.get<insertion_order>().erase(entry); 845 } 846 clearDisconnectedBlockTransactions847 void clear() 848 { 849 cachedInnerUsage = 0; 850 queuedTx.clear(); 851 } 852 }; 853 854 #endif // BITCOIN_TXMEMPOOL_H 855