diff options
Diffstat (limited to 'src/txmempool.h')
| -rw-r--r-- | src/txmempool.h | 309 |
1 files changed, 305 insertions, 4 deletions
diff --git a/src/txmempool.h b/src/txmempool.h index ea36ce1ad5..c0eef0dd22 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: @@ -46,10 +67,18 @@ private: 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, bool poolHasNoInputsOf = false); - CTxMemPoolEntry(); CTxMemPoolEntry(const CTxMemPoolEntry& other); const CTransaction& GetTx() const { return this->tx; } @@ -60,6 +89,98 @@ public: 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(); } +}; + +// 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; @@ -87,6 +208,71 @@ 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 { @@ -99,8 +285,46 @@ private: 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; @@ -116,7 +340,13 @@ public: void check(const CCoinsViewCache *pcoins) const; void setSanityCheck(bool _fSanityCheck) { fSanityCheck = _fSanityCheck; } + // 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); @@ -138,6 +368,35 @@ public: 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 + * fSearchForParents = whether to search a tx's vin for in-mempool parents, or + * look up parents from mapLinks. Must be true for entries not in the mempool + */ + 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); + unsigned long size() { LOCK(cs); @@ -169,6 +428,48 @@ public: 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); }; /** |