diff options
Diffstat (limited to 'src/txmempool.h')
| -rw-r--r-- | src/txmempool.h | 334 |
1 files changed, 323 insertions, 11 deletions
diff --git a/src/txmempool.h b/src/txmempool.h index 0732af67e6..f0c3f7e0f1 100644 --- a/src/txmempool.h +++ b/src/txmempool.h @@ -7,12 +7,17 @@ #define BITCOIN_TXMEMPOOL_H #include <list> +#include <set> #include "amount.h" #include "coins.h" #include "primitives/transaction.h" #include "sync.h" +#undef foreach +#include "boost/multi_index_container.hpp" +#include "boost/multi_index/ordered_index.hpp" + class CAutoFile; inline double AllowFreeThreshold() @@ -30,9 +35,25 @@ inline bool AllowFree(double dPriority) /** 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; -/** - * CTxMemPool stores these: +class CTxMemPool; + +/** \class CTxMemPoolEntry + * + * CTxMemPoolEntry stores data about the correponding transaction, as well + * as data about all in-mempool transactions that depend on the transaction + * ("descendant" transactions). + * + * When a new entry is added to the mempool, we update the descendant state + * (nCountWithDescendants, nSizeWithDescendants, and nFeesWithDescendants) 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/nFeesWithDescendants to equal nTxSize/ + * nTxFee. (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 { private: @@ -40,14 +61,24 @@ private: CAmount nFee; //! Cached to avoid expensive parent-transaction lookups size_t nTxSize; //! ... and avoid recomputing tx size 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 dPriority; //! Priority when entering the mempool unsigned int nHeight; //! Chain height when entering the mempool + bool hadNoDependencies; //! Not dependent on any other txs when it entered the mempool + + // 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 nFeesWithDescendants will not be + // correct. + uint64_t nCountWithDescendants; //! number of descendant transactions + uint64_t nSizeWithDescendants; //! ... and size + CAmount nFeesWithDescendants; //! ... and total fees (all including us) public: CTxMemPoolEntry(const CTransaction& _tx, const CAmount& _nFee, - int64_t _nTime, double _dPriority, unsigned int _nHeight); - CTxMemPoolEntry(); + int64_t _nTime, double _dPriority, unsigned int _nHeight, bool poolHasNoInputsOf = false); CTxMemPoolEntry(const CTxMemPoolEntry& other); const CTransaction& GetTx() const { return this->tx; } @@ -56,9 +87,103 @@ public: size_t GetTxSize() const { return nTxSize; } int64_t GetTime() const { return nTime; } unsigned int GetHeight() const { return nHeight; } + bool WasClearAtEntry() const { return hadNoDependencies; } + size_t DynamicMemoryUsage() const { return nUsageSize; } + + // Adjusts the descendant state, if this entry is not dirty. + void UpdateState(int64_t modifySize, CAmount modifyFee, int64_t modifyCount); + + /** We can set the entry to be dirty if doing the full calculation of in- + * mempool descendants will be too expensive, which can potentially happen + * when re-adding transactions from a block back to the mempool. + */ + void SetDirty(); + bool IsDirty() const { return nCountWithDescendants == 0; } + + uint64_t GetCountWithDescendants() const { return nCountWithDescendants; } + uint64_t GetSizeWithDescendants() const { return nSizeWithDescendants; } + CAmount GetFeesWithDescendants() const { return nFeesWithDescendants; } +}; + +// Helpers for modifying CTxMemPool::mapTx, which is a boost multi_index. +struct update_descendant_state +{ + update_descendant_state(int64_t _modifySize, CAmount _modifyFee, int64_t _modifyCount) : + modifySize(_modifySize), modifyFee(_modifyFee), modifyCount(_modifyCount) + {} + + void operator() (CTxMemPoolEntry &e) + { e.UpdateState(modifySize, modifyFee, modifyCount); } + + private: + int64_t modifySize; + CAmount modifyFee; + int64_t modifyCount; +}; + +struct set_dirty +{ + void operator() (CTxMemPoolEntry &e) + { e.SetDirty(); } }; -class CMinerPolicyEstimator; +// extracts a TxMemPoolEntry's transaction hash +struct mempoolentry_txid +{ + typedef uint256 result_type; + result_type operator() (const CTxMemPoolEntry &entry) const + { + return entry.GetTx().GetHash(); + } +}; + +/** \class CompareTxMemPoolEntryByFee + * + * Sort an entry by max(feerate of entry's tx, feerate with all descendants). + */ +class CompareTxMemPoolEntryByFee +{ +public: + bool operator()(const CTxMemPoolEntry& a, const CTxMemPoolEntry& b) + { + bool fUseADescendants = UseDescendantFeeRate(a); + bool fUseBDescendants = UseDescendantFeeRate(b); + + double aFees = fUseADescendants ? a.GetFeesWithDescendants() : a.GetFee(); + double aSize = fUseADescendants ? a.GetSizeWithDescendants() : a.GetTxSize(); + + double bFees = fUseBDescendants ? b.GetFeesWithDescendants() : b.GetFee(); + double bSize = fUseBDescendants ? b.GetSizeWithDescendants() : b.GetTxSize(); + + // Avoid division by rewriting (a/b > c/d) as (a*d > c*b). + double f1 = aFees * bSize; + double f2 = aSize * bFees; + + if (f1 == f2) { + return a.GetTime() < b.GetTime(); + } + return f1 > f2; + } + + // Calculate which feerate to use for an entry (avoiding division). + bool UseDescendantFeeRate(const CTxMemPoolEntry &a) + { + double f1 = (double)a.GetFee() * a.GetSizeWithDescendants(); + double f2 = (double)a.GetFeesWithDescendants() * a.GetTxSize(); + return f2 > f1; + } +}; + +class CompareTxMemPoolEntryByEntryTime +{ +public: + bool operator()(const CTxMemPoolEntry& a, const CTxMemPoolEntry& b) + { + return a.GetTime() < b.GetTime(); + } +}; + +class CBlockPolicyEstimator; /** An inpoint - a combination of a transaction and an index n into its vin */ class CInPoint @@ -71,6 +196,7 @@ public: CInPoint(const CTransaction* ptxIn, uint32_t nIn) { ptx = ptxIn; n = nIn; } void SetNull() { ptx = NULL; n = (uint32_t) -1; } bool IsNull() const { return (ptx == NULL && n == (uint32_t) -1); } + size_t DynamicMemoryUsage() const { return 0; } }; /** @@ -82,20 +208,123 @@ public: * are added to the pool: if a new transaction double-spends * an input of a transaction in the pool, it is dropped, * as are non-standard transactions. + * + * CTxMemPool::mapTx, and CTxMemPoolEntry bookkeeping: + * + * mapTx is a boost::multi_index that sorts the mempool on 2 criteria: + * - transaction hash + * - feerate [we use max(feerate of tx, feerate of tx with all descendants)] + * + * Note: the term "descendant" refers to in-mempool transactions that depend on + * this one, while "ancestor" refers to in-mempool transactions that a given + * transaction depends on. + * + * In order for the feerate sort to remain correct, we must update transactions + * in the mempool when new descendants arrive. To facilitate this, we track + * the set of in-mempool direct parents and direct children in mapLinks. Within + * each CTxMemPoolEntry, we track the size and fees of all descendants. + * + * Usually when a new transaction is added to the mempool, it has no in-mempool + * children (because any such children would be an orphan). So in + * addUnchecked(), we: + * - update a new entry's setMemPoolParents to include all in-mempool parents + * - update the new entry's direct parents to include the new tx as a child + * - update all ancestors of the transaction to include the new tx's size/fee + * + * When a transaction is removed from the mempool, we must: + * - update all in-mempool parents to not track the tx in setMemPoolChildren + * - update all ancestors to not include the tx's size/fees in descendant state + * - update all in-mempool children to not include it as a parent + * + * These happen in UpdateForRemoveFromMempool(). (Note that when removing a + * transaction along with its descendants, we must calculate that set of + * transactions to be removed before doing the removal, or else the mempool can + * be in an inconsistent state where it's impossible to walk the ancestors of + * a transaction.) + * + * In the event of a reorg, the assumption that a newly added tx has no + * in-mempool children is false. In particular, the mempool is in an + * inconsistent state while new transactions are being added, because there may + * be descendant transactions of a tx coming from a disconnected block that are + * unreachable from just looking at transactions in the mempool (the linking + * transactions may also be in the disconnected block, waiting to be added). + * Because of this, there's not much benefit in trying to search for in-mempool + * children in addUnchecked(). Instead, in the special case of transactions + * being added from a disconnected block, we require the caller to clean up the + * state, to account for in-mempool, out-of-block descendants for all the + * in-block transactions by calling UpdateTransactionsFromBlock(). Note that + * until this is called, the mempool state is not consistent, and in particular + * mapLinks may not be correct (and therefore functions like + * CalculateMemPoolAncestors() and CalculateDescendants() that rely + * on them to walk the mempool are not generally safe to use). + * + * Computational limits: + * + * Updating all in-mempool ancestors of a newly added transaction can be slow, + * if no bound exists on how many in-mempool ancestors there may be. + * 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: bool fSanityCheck; //! Normally false, true if -checkmempool or -regtest unsigned int nTransactionsUpdated; - CMinerPolicyEstimator* minerPolicyEstimator; + CBlockPolicyEstimator* minerPolicyEstimator; - CFeeRate minRelayFee; //! Passed to constructor to avoid dependency on main uint64_t totalTxSize; //! sum of all mempool tx' byte sizes + uint64_t cachedInnerUsage; //! sum of dynamic memory usage of all the map elements (NOT the maps themselves) public: + typedef boost::multi_index_container< + CTxMemPoolEntry, + boost::multi_index::indexed_by< + // sorted by txid + boost::multi_index::ordered_unique<mempoolentry_txid>, + // sorted by fee rate + boost::multi_index::ordered_non_unique< + boost::multi_index::identity<CTxMemPoolEntry>, + CompareTxMemPoolEntryByFee + > + > + > indexed_transaction_set; + mutable CCriticalSection cs; - std::map<uint256, CTxMemPoolEntry> mapTx; + indexed_transaction_set mapTx; + typedef indexed_transaction_set::nth_index<0>::type::iterator txiter; + struct CompareIteratorByHash { + bool operator()(const txiter &a, const txiter &b) const { + return a->GetTx().GetHash() < b->GetTx().GetHash(); + } + }; + typedef std::set<txiter, CompareIteratorByHash> setEntries; + +private: + typedef std::map<txiter, setEntries, CompareIteratorByHash> cacheMap; + + struct TxLinks { + setEntries parents; + setEntries children; + }; + + typedef std::map<txiter, TxLinks, CompareIteratorByHash> txlinksMap; + txlinksMap mapLinks; + + const setEntries & GetMemPoolParents(txiter entry) const; + const setEntries & GetMemPoolChildren(txiter entry) const; + void UpdateParent(txiter entry, txiter parent, bool add); + void UpdateChild(txiter entry, txiter child, bool add); + +public: std::map<COutPoint, CInPoint> mapNextTx; std::map<uint256, std::pair<double, CAmount> > mapDeltas; @@ -111,35 +340,74 @@ public: void check(const CCoinsViewCache *pcoins) const; void setSanityCheck(bool _fSanityCheck) { fSanityCheck = _fSanityCheck; } - bool addUnchecked(const uint256& hash, const CTxMemPoolEntry &entry); + // addUnchecked must updated state for all ancestors of a given transaction, + // to track size/count of descendant transactions. First version of + // addUnchecked can be used to have it call CalculateMemPoolAncestors(), and + // then invoke the second version. + bool addUnchecked(const uint256& hash, const CTxMemPoolEntry &entry, bool fCurrentEstimate = true); + bool addUnchecked(const uint256& hash, const CTxMemPoolEntry &entry, setEntries &setAncestors, bool fCurrentEstimate = true); + void remove(const CTransaction &tx, std::list<CTransaction>& removed, bool fRecursive = false); void removeCoinbaseSpends(const CCoinsViewCache *pcoins, unsigned int nMemPoolHeight); void removeConflicts(const CTransaction &tx, std::list<CTransaction>& removed); void removeForBlock(const std::vector<CTransaction>& vtx, unsigned int nBlockHeight, - std::list<CTransaction>& conflicts); + std::list<CTransaction>& conflicts, bool fCurrentEstimate = true); void clear(); void queryHashes(std::vector<uint256>& vtxid); void pruneSpent(const uint256& hash, CCoins &coins); unsigned int GetTransactionsUpdated() const; void AddTransactionsUpdated(unsigned int n); + /** + * Check that none of this transactions inputs are in the mempool, and thus + * the tx is not dependent on other mempool transactions to be included in a block. + */ + bool HasNoInputsOf(const CTransaction& tx) const; /** Affect CreateNewBlock prioritisation of transactions */ void PrioritiseTransaction(const uint256 hash, const std::string strHash, double dPriorityDelta, const CAmount& nFeeDelta); void ApplyDeltas(const uint256 hash, double &dPriorityDelta, CAmount &nFeeDelta); void ClearPrioritisation(const uint256 hash); +public: + /** Remove a set of transactions from the mempool. + * If a transaction is in this set, then all in-mempool descendants must + * also be in the set.*/ + void RemoveStaged(setEntries &stage); + + /** When adding transactions from a disconnected block back to the mempool, + * 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 + * disconnected block that have been accepted back into the mempool. + */ + void UpdateTransactionsFromBlock(const std::vector<uint256> &hashesToUpdate); + + /** Try to calculate all in-mempool ancestors of entry. + * (these are all calculated including the tx itself) + * limitAncestorCount = max number of ancestors + * limitAncestorSize = max size of ancestors + * limitDescendantCount = max number of descendants any ancestor can have + * limitDescendantSize = max size of descendants any ancestor can have + * errString = populated with error reason if any limits are hit + */ + bool CalculateMemPoolAncestors(const CTxMemPoolEntry &entry, setEntries &setAncestors, uint64_t limitAncestorCount, uint64_t limitAncestorSize, uint64_t limitDescendantCount, uint64_t limitDescendantSize, std::string &errString); + unsigned long size() { LOCK(cs); return mapTx.size(); } + uint64_t GetTotalTxSize() { LOCK(cs); return totalTxSize; } - bool exists(uint256 hash) + bool exists(uint256 hash) const { LOCK(cs); return (mapTx.count(hash) != 0); @@ -156,6 +424,50 @@ public: /** Write/Read estimates to disk */ bool WriteFeeEstimates(CAutoFile& fileout) const; bool ReadFeeEstimates(CAutoFile& filein); + + size_t DynamicMemoryUsage() const; + +private: + /** UpdateForDescendants is used by UpdateTransactionsFromBlock to update + * the descendants for a single transaction that has been added to the + * mempool but may have child transactions in the mempool, eg during a + * chain reorg. setExclude is the set of descendant transactions in the + * mempool that must not be accounted for (because any descendants in + * setExclude were added to the mempool after the transaction being + * updated and hence their state is already reflected in the parent + * state). + * + * If updating an entry requires looking at more than maxDescendantsToVisit + * transactions, outside of the ones in setExclude, then give up. + * + * cachedDescendants will be updated with the descendants of the transaction + * being updated, so that future invocations don't need to walk the + * same transaction again, if encountered in another transaction chain. + */ + bool UpdateForDescendants(txiter updateIt, + int maxDescendantsToVisit, + cacheMap &cachedDescendants, + const std::set<uint256> &setExclude); + /** Update ancestors of hash to add/remove it as a descendant transaction. */ + void UpdateAncestorsOf(bool add, txiter hash, setEntries &setAncestors); + /** For each transaction being removed, update ancestors and any direct children. */ + void UpdateForRemoveFromMempool(const setEntries &entriesToRemove); + /** Sever link between specified transaction and direct children. */ + void UpdateChildrenForRemoval(txiter entry); + /** Populate setDescendants with all in-mempool descendants of hash. + * Assumes that setDescendants includes all in-mempool descendants of anything + * already in it. */ + void CalculateDescendants(txiter it, setEntries &setDescendants); + + /** Before calling removeUnchecked for a given transaction, + * UpdateForRemoveFromMempool must be called on the entire (dependent) set + * of transactions being removed at the same time. We use each + * CTxMemPoolEntry's setMemPoolParents in order to walk ancestors of a + * given transaction that is removed, so we can't remove intermediate + * transactions in a chain before we've updated all the state for the + * removal. + */ + void removeUnchecked(txiter entry); }; /** |