diff options
Diffstat (limited to 'src/txmempool.h')
| -rw-r--r-- | src/txmempool.h | 222 |
1 files changed, 135 insertions, 87 deletions
diff --git a/src/txmempool.h b/src/txmempool.h index 8a8039ded1..0316b42ba2 100644 --- a/src/txmempool.h +++ b/src/txmempool.h @@ -16,6 +16,7 @@ #include "amount.h" #include "coins.h" #include "indirectmap.h" +#include "policy/feerate.h" #include "primitives/transaction.h" #include "sync.h" #include "random.h" @@ -23,26 +24,15 @@ #include "boost/multi_index_container.hpp" #include "boost/multi_index/ordered_index.hpp" #include "boost/multi_index/hashed_index.hpp" +#include <boost/multi_index/sequenced_index.hpp> #include <boost/signals2/signal.hpp> class CAutoFile; class CBlockIndex; -inline double AllowFreeThreshold() -{ - return COIN * 144 / 250; -} - -inline bool AllowFree(double dPriority) -{ - // Large (in bytes) low-priority (new, small-coin) transactions - // need a fee. - return dPriority > AllowFreeThreshold(); -} - -/** Fake height value used in CCoins to signify they are only in the memory pool (since 0.8) */ -static const unsigned int MEMPOOL_HEIGHT = 0x7FFFFFFF; +/** Fake height value used in Coin to signify they are only in the memory pool (since 0.8) */ +static const uint32_t MEMPOOL_HEIGHT = 0x7FFFFFFF; struct LockPoints { @@ -71,11 +61,6 @@ class CTxMemPool; * (nCountWithDescendants, nSizeWithDescendants, and nModFeesWithDescendants) for * all ancestors of the newly added transaction. * - * If updating the descendant state is skipped, we can mark the entry as - * "dirty", and set nSizeWithDescendants/nModFeesWithDescendants to equal nTxSize/ - * nFee+feeDelta. (This can potentially happen during a reorg, where we limit the - * amount of work we're willing to do to avoid consuming too much CPU.) - * */ class CTxMemPoolEntry @@ -84,12 +69,9 @@ private: CTransactionRef tx; CAmount nFee; //!< Cached to avoid expensive parent-transaction lookups size_t nTxWeight; //!< ... and avoid recomputing tx weight (also used for GetTxSize()) - size_t nModSize; //!< ... and modified size for priority size_t nUsageSize; //!< ... and total memory usage int64_t nTime; //!< Local time when entering the mempool - double entryPriority; //!< Priority when entering the mempool unsigned int entryHeight; //!< Chain height when entering the mempool - CAmount inChainInputValue; //!< Sum of all txin values that are already in blockchain bool spendsCoinbase; //!< keep track of transactions that spend a coinbase int64_t sigOpCost; //!< Total sigop cost int64_t feeDelta; //!< Used for determining the priority of the transaction for mining in a block @@ -97,9 +79,7 @@ private: // Information about descendants of this transaction that are in the // mempool; if we remove this transaction we must remove all of these - // descendants as well. if nCountWithDescendants is 0, treat this entry as - // dirty, and nSizeWithDescendants and nModFeesWithDescendants will not be - // correct. + // descendants as well. uint64_t nCountWithDescendants; //!< number of descendant transactions uint64_t nSizeWithDescendants; //!< ... and size CAmount nModFeesWithDescendants; //!< ... and total fees (all including us) @@ -112,19 +92,14 @@ private: public: CTxMemPoolEntry(const CTransactionRef& _tx, const CAmount& _nFee, - int64_t _nTime, double _entryPriority, unsigned int _entryHeight, - CAmount _inChainInputValue, bool spendsCoinbase, + int64_t _nTime, unsigned int _entryHeight, + bool spendsCoinbase, int64_t nSigOpsCost, LockPoints lp); CTxMemPoolEntry(const CTxMemPoolEntry& other); const CTransaction& GetTx() const { return *this->tx; } CTransactionRef GetSharedTx() const { return this->tx; } - /** - * Fast calculation of lower bound of current priority as update - * from entry priority. Only inputs that were originally in-chain will age. - */ - double GetPriority(unsigned int currentHeight) const; const CAmount& GetFee() const { return nFee; } size_t GetTxSize() const; size_t GetTxWeight() const { return nTxWeight; } @@ -135,7 +110,7 @@ public: size_t DynamicMemoryUsage() const { return nUsageSize; } const LockPoints& GetLockPoints() const { return lockPoints; } - // Adjusts the descendant state, if this entry is not dirty. + // Adjusts the descendant state. void UpdateDescendantState(int64_t modifySize, CAmount modifyFee, int64_t modifyCount); // Adjusts the ancestor state void UpdateAncestorState(int64_t modifySize, CAmount modifyFee, int64_t modifyCount, int modifySigOps); @@ -211,7 +186,7 @@ private: const LockPoints& lp; }; -// extracts a TxMemPoolEntry's transaction hash +// extracts a transaction hash from CTxMempoolEntry or CTransactionRef struct mempoolentry_txid { typedef uint256 result_type; @@ -219,6 +194,11 @@ struct mempoolentry_txid { return entry.GetTx().GetHash(); } + + result_type operator() (const CTransactionRef& tx) const + { + return tx->GetHash(); + } }; /** \class CompareTxMemPoolEntryByDescendantScore @@ -347,6 +327,20 @@ enum class MemPoolRemovalReason { REPLACED //! Removed for replacement }; +class SaltedTxidHasher +{ +private: + /** Salt */ + const uint64_t k0, k1; + +public: + SaltedTxidHasher(); + + size_t operator()(const uint256& txid) const { + return SipHashUint256(k0, k1, txid); + } +}; + /** * CTxMemPool stores valid-according-to-the-current-best-chain transactions * that may be included in the next block. @@ -418,20 +412,12 @@ enum class MemPoolRemovalReason { * CalculateMemPoolAncestors() takes configurable limits that are designed to * prevent these calculations from being too CPU intensive. * - * Adding transactions from a disconnected block can be very time consuming, - * because we don't have a way to limit the number of in-mempool descendants. - * To bound CPU processing, we limit the amount of work we're willing to do - * to properly update the descendant information for a tx being added from - * a disconnected block. If we would exceed the limit, then we instead mark - * the entry as "dirty", and set the feerate for sorting purposes to be equal - * the feerate of the transaction without any descendants. - * */ class CTxMemPool { private: uint32_t nCheckFrequency; //!< Value n means that n times in 2^32 we check. - unsigned int nTransactionsUpdated; + unsigned int nTransactionsUpdated; //!< Used by getblocktemplate to trigger CreateNewBlock() invocation CBlockPolicyEstimator* minerPolicyEstimator; 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. @@ -512,12 +498,11 @@ private: public: indirectmap<COutPoint, const CTransaction*> mapNextTx; - std::map<uint256, std::pair<double, CAmount> > mapDeltas; + std::map<uint256, CAmount> mapDeltas; /** Create a new CTxMemPool. */ - CTxMemPool(const CFeeRate& _minReasonableRelayFee); - ~CTxMemPool(); + CTxMemPool(CBlockPolicyEstimator* estimator = nullptr); /** * If sanity-checking is turned on, check makes sure the pool is @@ -544,7 +529,7 @@ public: void _clear(); //lock free bool CompareDepthAndScore(const uint256& hasha, const uint256& hashb); void queryHashes(std::vector<uint256>& vtxid); - void pruneSpent(const uint256& hash, CCoins &coins); + bool isSpent(const COutPoint& outpoint); unsigned int GetTransactionsUpdated() const; void AddTransactionsUpdated(unsigned int n); /** @@ -554,8 +539,8 @@ public: bool HasNoInputsOf(const CTransaction& tx) const; /** Affect CreateNewBlock prioritisation of transactions */ - void PrioritiseTransaction(const uint256& hash, double dPriorityDelta, const CAmount& nFeeDelta); - void ApplyDeltas(const uint256 hash, double &dPriorityDelta, CAmount &nFeeDelta) const; + void PrioritiseTransaction(const uint256& hash, const CAmount& nFeeDelta); + void ApplyDelta(const uint256 hash, CAmount &nFeeDelta) const; void ClearPrioritisation(const uint256 hash); public: @@ -572,12 +557,12 @@ public: * new mempool entries may have children in the mempool (which is generally * not the case when otherwise adding transactions). * UpdateTransactionsFromBlock() will find child transactions and update the - * descendant state for each transaction in hashesToUpdate (excluding any - * child transactions present in hashesToUpdate, which are already accounted - * for). Note: hashesToUpdate should be the set of transactions from the + * descendant state for each transaction in vHashesToUpdate (excluding any + * child transactions present in vHashesToUpdate, which are already accounted + * for). Note: vHashesToUpdate should be the set of transactions from the * disconnected block that have been accepted back into the mempool. */ - void UpdateTransactionsFromBlock(const std::vector<uint256> &hashesToUpdate); + void UpdateTransactionsFromBlock(const std::vector<uint256> &vHashesToUpdate); /** Try to calculate all in-mempool ancestors of entry. * (these are all calculated including the tx itself) @@ -605,10 +590,10 @@ public: CFeeRate GetMinFee(size_t sizelimit) const; /** Remove transactions from the mempool until its dynamic size is <= sizelimit. - * pvNoSpendsRemaining, if set, will be populated with the list of transactions + * pvNoSpendsRemaining, if set, will be populated with the list of outpoints * which are not in mempool which no longer have any spends in this mempool. */ - void TrimToSize(size_t sizelimit, std::vector<uint256>* pvNoSpendsRemaining=NULL); + void TrimToSize(size_t sizelimit, std::vector<COutPoint>* pvNoSpendsRemaining=NULL); /** Expire all transaction (and their dependencies) in the mempool older than time. Return the number of removed transactions. */ int Expire(int64_t time); @@ -634,32 +619,17 @@ public: return (mapTx.count(hash) != 0); } + bool exists(const COutPoint& outpoint) const + { + LOCK(cs); + auto it = mapTx.find(outpoint.hash); + return (it != mapTx.end() && outpoint.n < it->GetTx().vout.size()); + } + CTransactionRef get(const uint256& hash) const; TxMempoolInfo info(const uint256& hash) const; std::vector<TxMempoolInfo> infoAll() const; - /** Estimate fee rate needed to get into the next nBlocks - * If no answer can be given at nBlocks, return an estimate - * at the lowest number of blocks where one can be given - */ - CFeeRate estimateSmartFee(int nBlocks, int *answerFoundAtBlocks = NULL) const; - - /** Estimate fee rate needed to get into the next nBlocks */ - CFeeRate estimateFee(int nBlocks) const; - - /** Estimate priority needed to get into the next nBlocks - * If no answer can be given at nBlocks, return an estimate - * at the lowest number of blocks where one can be given - */ - double estimateSmartPriority(int nBlocks, int *answerFoundAtBlocks = NULL) const; - - /** Estimate priority needed to get into the next nBlocks */ - double estimatePriority(int nBlocks) const; - - /** Write/Read estimates to disk */ - bool WriteFeeEstimates(CAutoFile& fileout) const; - bool ReadFeeEstimates(CAutoFile& filein); - size_t DynamicMemoryUsage() const; boost::signals2::signal<void (CTransactionRef)> NotifyEntryAdded; @@ -715,20 +685,98 @@ protected: public: CCoinsViewMemPool(CCoinsView* baseIn, const CTxMemPool& mempoolIn); - bool GetCoins(const uint256 &txid, CCoins &coins) const; - bool HaveCoins(const uint256 &txid) const; + bool GetCoin(const COutPoint &outpoint, Coin &coin) const; + bool HaveCoin(const COutPoint &outpoint) const; }; -// We want to sort transactions by coin age priority -typedef std::pair<double, CTxMemPool::txiter> TxCoinAgePriority; +/** + * DisconnectedBlockTransactions + + * During the reorg, it's desirable to re-add previously confirmed transactions + * to the mempool, so that anything not re-confirmed in the new chain is + * available to be mined. However, it's more efficient to wait until the reorg + * is complete and process all still-unconfirmed transactions at that time, + * since we expect most confirmed transactions to (typically) still be + * confirmed in the new chain, and re-accepting to the memory pool is expensive + * (and therefore better to not do in the middle of reorg-processing). + * Instead, store the disconnected transactions (in order!) as we go, remove any + * that are included in blocks in the new chain, and then process the remaining + * still-unconfirmed transactions at the end. + */ -struct TxCoinAgePriorityCompare -{ - bool operator()(const TxCoinAgePriority& a, const TxCoinAgePriority& b) +// multi_index tag names +struct txid_index {}; +struct insertion_order {}; + +struct DisconnectedBlockTransactions { + typedef boost::multi_index_container< + CTransactionRef, + boost::multi_index::indexed_by< + // sorted by txid + boost::multi_index::hashed_unique< + boost::multi_index::tag<txid_index>, + mempoolentry_txid, + SaltedTxidHasher + >, + // sorted by order in the blockchain + boost::multi_index::sequenced< + boost::multi_index::tag<insertion_order> + > + > + > indexed_disconnected_transactions; + + // It's almost certainly a logic bug if we don't clear out queuedTx before + // destruction, as we add to it while disconnecting blocks, and then we + // need to re-process remaining transactions to ensure mempool consistency. + // For now, assert() that we've emptied out this object on destruction. + // This assert() can always be removed if the reorg-processing code were + // to be refactored such that this assumption is no longer true (for + // instance if there was some other way we cleaned up the mempool after a + // reorg, besides draining this object). + ~DisconnectedBlockTransactions() { assert(queuedTx.empty()); } + + indexed_disconnected_transactions queuedTx; + uint64_t cachedInnerUsage = 0; + + // Estimate the overhead of queuedTx to be 6 pointers + an allocation, as + // no exact formula for boost::multi_index_contained is implemented. + size_t DynamicMemoryUsage() const { + return memusage::MallocUsage(sizeof(CTransactionRef) + 6 * sizeof(void*)) * queuedTx.size() + cachedInnerUsage; + } + + void addTransaction(const CTransactionRef& tx) + { + queuedTx.insert(tx); + cachedInnerUsage += RecursiveDynamicUsage(tx); + } + + // Remove entries based on txid_index, and update memory usage. + void removeForBlock(const std::vector<CTransactionRef>& vtx) + { + // Short-circuit in the common case of a block being added to the tip + if (queuedTx.empty()) { + return; + } + for (auto const &tx : vtx) { + auto it = queuedTx.find(tx->GetHash()); + if (it != queuedTx.end()) { + cachedInnerUsage -= RecursiveDynamicUsage(*it); + queuedTx.erase(it); + } + } + } + + // Remove an entry by insertion_order index, and update memory usage. + void removeEntry(indexed_disconnected_transactions::index<insertion_order>::type::iterator entry) + { + cachedInnerUsage -= RecursiveDynamicUsage(*entry); + queuedTx.get<insertion_order>().erase(entry); + } + + void clear() { - if (a.first == b.first) - return CompareTxMemPoolEntryByScore()(*(b.second), *(a.second)); //Reverse order to make sort less than - return a.first < b.first; + cachedInnerUsage = 0; + queuedTx.clear(); } }; |