diff options
Diffstat (limited to 'src/txmempool.h')
| -rw-r--r-- | src/txmempool.h | 150 |
1 files changed, 115 insertions, 35 deletions
diff --git a/src/txmempool.h b/src/txmempool.h index 7b5843a8d0..386cb26d25 100644 --- a/src/txmempool.h +++ b/src/txmempool.h @@ -1,5 +1,5 @@ // Copyright (c) 2009-2010 Satoshi Nakamoto -// Copyright (c) 2009-2014 The Bitcoin Core developers +// Copyright (c) 2009-2015 The Bitcoin Core developers // Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. @@ -44,12 +44,12 @@ class CTxMemPool; * ("descendant" transactions). * * When a new entry is added to the mempool, we update the descendant state - * (nCountWithDescendants, nSizeWithDescendants, and nFeesWithDescendants) for + * (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/nFeesWithDescendants to equal nTxSize/ - * nTxFee. (This can potentially happen during a reorg, where we limit the + * "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.) * */ @@ -63,35 +63,50 @@ private: 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 + double entryPriority; //! Priority when entering the mempool + unsigned int entryHeight; //! Chain height when entering the mempool bool hadNoDependencies; //! Not dependent on any other txs when it entered the mempool + CAmount inChainInputValue; //! Sum of all txin values that are already in blockchain + bool spendsCoinbase; //! keep track of transactions that spend a coinbase + unsigned int sigOpCount; //! Legacy sig ops plus P2SH sig op count + int64_t feeDelta; //! Used for determining the priority of the transaction for mining in a block // 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 + // dirty, and nSizeWithDescendants and nModFeesWithDescendants will not be // correct. uint64_t nCountWithDescendants; //! number of descendant transactions uint64_t nSizeWithDescendants; //! ... and size - CAmount nFeesWithDescendants; //! ... and total fees (all including us) + CAmount nModFeesWithDescendants; //! ... 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); + int64_t _nTime, double _entryPriority, unsigned int _entryHeight, + bool poolHasNoInputsOf, CAmount _inChainInputValue, bool spendsCoinbase, + unsigned int nSigOps); CTxMemPoolEntry(const CTxMemPoolEntry& other); const CTransaction& GetTx() 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 { return nTxSize; } int64_t GetTime() const { return nTime; } - unsigned int GetHeight() const { return nHeight; } + unsigned int GetHeight() const { return entryHeight; } bool WasClearAtEntry() const { return hadNoDependencies; } + unsigned int GetSigOpCount() const { return sigOpCount; } + int64_t GetModifiedFee() const { return nFee + feeDelta; } 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); + // Updates the fee delta used for mining priority score, and the + // modified fees with descendants. + void UpdateFeeDelta(int64_t feeDelta); /** 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 @@ -102,7 +117,9 @@ public: uint64_t GetCountWithDescendants() const { return nCountWithDescendants; } uint64_t GetSizeWithDescendants() const { return nSizeWithDescendants; } - CAmount GetFeesWithDescendants() const { return nFeesWithDescendants; } + CAmount GetModFeesWithDescendants() const { return nModFeesWithDescendants; } + + bool GetSpendsCoinbase() const { return spendsCoinbase; } }; // Helpers for modifying CTxMemPool::mapTx, which is a boost multi_index. @@ -127,6 +144,16 @@ struct set_dirty { e.SetDirty(); } }; +struct update_fee_delta +{ + update_fee_delta(int64_t _feeDelta) : feeDelta(_feeDelta) { } + + void operator() (CTxMemPoolEntry &e) { e.UpdateFeeDelta(feeDelta); } + +private: + int64_t feeDelta; +}; + // extracts a TxMemPoolEntry's transaction hash struct mempoolentry_txid { @@ -137,27 +164,27 @@ struct mempoolentry_txid } }; -/** \class CompareTxMemPoolEntryByFee +/** \class CompareTxMemPoolEntryByDescendantScore * - * Sort an entry by max(feerate of entry's tx, feerate with all descendants). + * Sort an entry by max(score/size of entry's tx, score/size with all descendants). */ -class CompareTxMemPoolEntryByFee +class CompareTxMemPoolEntryByDescendantScore { public: bool operator()(const CTxMemPoolEntry& a, const CTxMemPoolEntry& b) { - bool fUseADescendants = UseDescendantFeeRate(a); - bool fUseBDescendants = UseDescendantFeeRate(b); + bool fUseADescendants = UseDescendantScore(a); + bool fUseBDescendants = UseDescendantScore(b); - double aFees = fUseADescendants ? a.GetFeesWithDescendants() : a.GetFee(); + double aModFee = fUseADescendants ? a.GetModFeesWithDescendants() : a.GetModifiedFee(); double aSize = fUseADescendants ? a.GetSizeWithDescendants() : a.GetTxSize(); - double bFees = fUseBDescendants ? b.GetFeesWithDescendants() : b.GetFee(); + double bModFee = fUseBDescendants ? b.GetModFeesWithDescendants() : b.GetModifiedFee(); 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; + double f1 = aModFee * bSize; + double f2 = aSize * bModFee; if (f1 == f2) { return a.GetTime() >= b.GetTime(); @@ -165,15 +192,33 @@ public: return f1 < f2; } - // Calculate which feerate to use for an entry (avoiding division). - bool UseDescendantFeeRate(const CTxMemPoolEntry &a) + // Calculate which score to use for an entry (avoiding division). + bool UseDescendantScore(const CTxMemPoolEntry &a) { - double f1 = (double)a.GetFee() * a.GetSizeWithDescendants(); - double f2 = (double)a.GetFeesWithDescendants() * a.GetTxSize(); + double f1 = (double)a.GetModifiedFee() * a.GetSizeWithDescendants(); + double f2 = (double)a.GetModFeesWithDescendants() * a.GetTxSize(); return f2 > f1; } }; +/** \class CompareTxMemPoolEntryByScore + * + * Sort by score of entry ((fee+delta)/size) in descending order + */ +class CompareTxMemPoolEntryByScore +{ +public: + bool operator()(const CTxMemPoolEntry& a, const CTxMemPoolEntry& b) + { + double f1 = (double)a.GetModifiedFee() * b.GetTxSize(); + double f2 = (double)b.GetModifiedFee() * a.GetTxSize(); + if (f1 == f2) { + return b.GetTx().GetHash() < a.GetTx().GetHash(); + } + return f1 > f2; + } +}; + class CompareTxMemPoolEntryByEntryTime { public: @@ -211,10 +256,11 @@ public: * * CTxMemPool::mapTx, and CTxMemPoolEntry bookkeeping: * - * mapTx is a boost::multi_index that sorts the mempool on 3 criteria: + * mapTx is a boost::multi_index that sorts the mempool on 4 criteria: * - transaction hash * - feerate [we use max(feerate of tx, feerate of tx with all descendants)] * - time in mempool + * - mining score (feerate modified by any fee deltas from PrioritiseTransaction) * * Note: the term "descendant" refers to in-mempool transactions that depend on * this one, while "ancestor" refers to in-mempool transactions that a given @@ -305,12 +351,17 @@ public: // sorted by fee rate boost::multi_index::ordered_non_unique< boost::multi_index::identity<CTxMemPoolEntry>, - CompareTxMemPoolEntryByFee + CompareTxMemPoolEntryByDescendantScore >, // sorted by entry time boost::multi_index::ordered_non_unique< boost::multi_index::identity<CTxMemPoolEntry>, CompareTxMemPoolEntryByEntryTime + >, + // sorted by score (for mining prioritization) + boost::multi_index::ordered_unique< + boost::multi_index::identity<CTxMemPoolEntry>, + CompareTxMemPoolEntryByScore > > > indexed_transaction_set; @@ -325,6 +376,8 @@ public: }; typedef std::set<txiter, CompareIteratorByHash> setEntries; + const setEntries & GetMemPoolParents(txiter entry) const; + const setEntries & GetMemPoolChildren(txiter entry) const; private: typedef std::map<txiter, setEntries, CompareIteratorByHash> cacheMap; @@ -336,8 +389,6 @@ private: 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); @@ -370,7 +421,7 @@ public: 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 removeForReorg(const CCoinsViewCache *pcoins, unsigned int nMemPoolHeight, int flags); void removeConflicts(const CTransaction &tx, std::list<CTransaction>& removed); void removeForBlock(const std::vector<CTransaction>& vtx, unsigned int nBlockHeight, std::list<CTransaction>& conflicts, bool fCurrentEstimate = true); @@ -420,6 +471,11 @@ public: */ 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); + /** 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); + /** The minimum fee to get into the mempool, which may itself not be enough * for larger-sized transactions. * The minReasonableRelayFee constructor arg is used to bound the time it @@ -428,8 +484,11 @@ public: */ CFeeRate GetMinFee(size_t sizelimit) const; - /** Remove transactions from the mempool until its dynamic size is <= sizelimit. */ - void TrimToSize(size_t sizelimit); + /** Remove transactions from the mempool until its dynamic size is <= sizelimit. + * pvNoSpendsRemaining, if set, will be populated with the list of transactions + * which are not in mempool which no longer have any spends in this mempool. + */ + void TrimToSize(size_t sizelimit, std::vector<uint256>* 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); @@ -454,9 +513,21 @@ public: bool lookup(uint256 hash, CTransaction& result) 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; @@ -493,10 +564,6 @@ private: 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 @@ -524,4 +591,17 @@ public: bool HaveCoins(const uint256 &txid) const; }; +// We want to sort transactions by coin age priority +typedef std::pair<double, CTxMemPool::txiter> TxCoinAgePriority; + +struct TxCoinAgePriorityCompare +{ + bool operator()(const TxCoinAgePriority& a, const TxCoinAgePriority& b) + { + if (a.first == b.first) + return CompareTxMemPoolEntryByScore()(*(b.second), *(a.second)); //Reverse order to make sort less than + return a.first < b.first; + } +}; + #endif // BITCOIN_TXMEMPOOL_H |