From 5de2baa138cda501038a4558bc169b2cfe5b7d6b Mon Sep 17 00:00:00 2001 From: Suhas Daftuar Date: Mon, 19 Oct 2015 12:43:38 -0400 Subject: Rename CTxMemPool::remove -> removeRecursive remove is no longer called non-recursively, so simplify the logic and eliminate an unnecessary parameter --- src/txmempool.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/txmempool.h') diff --git a/src/txmempool.h b/src/txmempool.h index 7a2a1ef432..da5a97649f 100644 --- a/src/txmempool.h +++ b/src/txmempool.h @@ -428,7 +428,7 @@ public: 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& removed, bool fRecursive = false); + void removeRecursive(const CTransaction &tx, std::list& removed); void removeForReorg(const CCoinsViewCache *pcoins, unsigned int nMemPoolHeight, int flags); void removeConflicts(const CTransaction &tx, std::list& removed); void removeForBlock(const std::vector& vtx, unsigned int nBlockHeight, -- cgit v1.2.3 From 76a76321d2f36992178ddaaf4d023c5e33c14fbf Mon Sep 17 00:00:00 2001 From: Suhas Daftuar Date: Wed, 21 Oct 2015 10:18:24 -0400 Subject: Remove work limit in UpdateForDescendants() The work limit served to prevent the descendant walking algorithm from doing too much work by marking the parent transaction as dirty. However to implement ancestor tracking, it's not possible to similarly mark those descendant transactions as dirty without having to calculate them to begin with. This commit removes the work limit altogether. With appropriate chain limits (-limitdescendantcount) the concern about doing too much work inside this function should be mitigated. --- src/txmempool.h | 19 +------------------ 1 file changed, 1 insertion(+), 18 deletions(-) (limited to 'src/txmempool.h') diff --git a/src/txmempool.h b/src/txmempool.h index da5a97649f..b1b6645a06 100644 --- a/src/txmempool.h +++ b/src/txmempool.h @@ -108,13 +108,6 @@ public: // 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 - * 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 GetModFeesWithDescendants() const { return nModFeesWithDescendants; } @@ -138,12 +131,6 @@ struct update_descendant_state int64_t modifyCount; }; -struct set_dirty -{ - void operator() (CTxMemPoolEntry &e) - { e.SetDirty(); } -}; - struct update_fee_delta { update_fee_delta(int64_t _feeDelta) : feeDelta(_feeDelta) { } @@ -555,15 +542,11 @@ private: * 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, + void UpdateForDescendants(txiter updateIt, cacheMap &cachedDescendants, const std::set &setExclude); /** Update ancestors of hash to add/remove it as a descendant transaction. */ -- cgit v1.2.3 From 72abd2ce3c5ad8157d3a993693df1919a6ad79c3 Mon Sep 17 00:00:00 2001 From: Suhas Daftuar Date: Mon, 19 Oct 2015 10:54:28 -0400 Subject: Add ancestor tracking to mempool This implements caching of ancestor state to each mempool entry, similar to descendant tracking, but also including caching sigops-with-ancestors (as that metric will be helpful to future code that implements better transaction selection in CreatenewBlock). --- src/txmempool.h | 49 +++++++++++++++++++++++++++++++++++++++++++------ 1 file changed, 43 insertions(+), 6 deletions(-) (limited to 'src/txmempool.h') diff --git a/src/txmempool.h b/src/txmempool.h index b1b6645a06..0db3d5bd27 100644 --- a/src/txmempool.h +++ b/src/txmempool.h @@ -80,6 +80,12 @@ private: uint64_t nSizeWithDescendants; //! ... and size CAmount nModFeesWithDescendants; //! ... and total fees (all including us) + // Analogous statistics for ancestor transactions + uint64_t nCountWithAncestors; + uint64_t nSizeWithAncestors; + CAmount nModFeesWithAncestors; + unsigned int nSigOpCountWithAncestors; + public: CTxMemPoolEntry(const CTransaction& _tx, const CAmount& _nFee, int64_t _nTime, double _entryPriority, unsigned int _entryHeight, @@ -103,7 +109,9 @@ public: 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); + 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); // Updates the fee delta used for mining priority score, and the // modified fees with descendants. void UpdateFeeDelta(int64_t feeDelta); @@ -113,6 +121,11 @@ public: CAmount GetModFeesWithDescendants() const { return nModFeesWithDescendants; } bool GetSpendsCoinbase() const { return spendsCoinbase; } + + uint64_t GetCountWithAncestors() const { return nCountWithAncestors; } + uint64_t GetSizeWithAncestors() const { return nSizeWithAncestors; } + CAmount GetModFeesWithAncestors() const { return nModFeesWithAncestors; } + unsigned int GetSigOpCountWithAncestors() const { return nSigOpCountWithAncestors; } }; // Helpers for modifying CTxMemPool::mapTx, which is a boost multi_index. @@ -123,12 +136,28 @@ struct update_descendant_state {} void operator() (CTxMemPoolEntry &e) - { e.UpdateState(modifySize, modifyFee, modifyCount); } + { e.UpdateDescendantState(modifySize, modifyFee, modifyCount); } + + private: + int64_t modifySize; + CAmount modifyFee; + int64_t modifyCount; +}; + +struct update_ancestor_state +{ + update_ancestor_state(int64_t _modifySize, CAmount _modifyFee, int64_t _modifyCount, int _modifySigOps) : + modifySize(_modifySize), modifyFee(_modifyFee), modifyCount(_modifyCount), modifySigOps(_modifySigOps) + {} + + void operator() (CTxMemPoolEntry &e) + { e.UpdateAncestorState(modifySize, modifyFee, modifyCount, modifySigOps); } private: int64_t modifySize; CAmount modifyFee; int64_t modifyCount; + int modifySigOps; }; struct update_fee_delta @@ -440,8 +469,12 @@ public: 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); + * also be in the set, unless this transaction is being removed for being + * in a block. + * Set updateDescendants to true when removing a tx that was in a block, so + * that any in-mempool descendants have their ancestor state updated. + */ + void RemoveStaged(setEntries &stage, bool updateDescendants); /** When adding transactions from a disconnected block back to the mempool, * new mempool entries may have children in the mempool (which is generally @@ -551,8 +584,12 @@ private: const std::set &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); + /** Set ancestor state for an entry */ + void UpdateEntryForAncestors(txiter it, const setEntries &setAncestors); + /** For each transaction being removed, update ancestors and any direct children. + * If updateDescendants is true, then also update in-mempool descendants' + * ancestor state. */ + void UpdateForRemoveFromMempool(const setEntries &entriesToRemove, bool updateDescendants); /** Sever link between specified transaction and direct children. */ void UpdateChildrenForRemoval(txiter entry); -- cgit v1.2.3 From e2eeb5dda790cf301aa669704a25fb35f67400e7 Mon Sep 17 00:00:00 2001 From: Suhas Daftuar Date: Mon, 19 Oct 2015 15:15:12 -0400 Subject: Add ancestor feerate index to mempool --- src/txmempool.h | 32 +++++++++++++++++++++++++++++++- 1 file changed, 31 insertions(+), 1 deletion(-) (limited to 'src/txmempool.h') diff --git a/src/txmempool.h b/src/txmempool.h index 0db3d5bd27..3f80a6ec24 100644 --- a/src/txmempool.h +++ b/src/txmempool.h @@ -244,10 +244,34 @@ public: } }; +class CompareTxMemPoolEntryByAncestorFee +{ +public: + bool operator()(const CTxMemPoolEntry& a, const CTxMemPoolEntry& b) + { + double aFees = a.GetModFeesWithAncestors(); + double aSize = a.GetSizeWithAncestors(); + + double bFees = b.GetModFeesWithAncestors(); + double bSize = b.GetSizeWithAncestors(); + + // 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.GetTx().GetHash() < b.GetTx().GetHash(); + } + + return f1 > f2; + } +}; + // Multi_index tag names struct descendant_score {}; struct entry_time {}; struct mining_score {}; +struct ancestor_score {}; class CBlockPolicyEstimator; @@ -380,12 +404,18 @@ public: boost::multi_index::tag, boost::multi_index::identity, CompareTxMemPoolEntryByEntryTime - >, + >, // sorted by score (for mining prioritization) boost::multi_index::ordered_unique< boost::multi_index::tag, boost::multi_index::identity, CompareTxMemPoolEntryByScore + >, + // sorted by fee rate with ancestors + boost::multi_index::ordered_non_unique< + boost::multi_index::tag, + boost::multi_index::identity, + CompareTxMemPoolEntryByAncestorFee > > > indexed_transaction_set; -- cgit v1.2.3 From ce019bf90fe89c1256a89c489795987ef0b8a18f Mon Sep 17 00:00:00 2001 From: Suhas Daftuar Date: Tue, 8 Mar 2016 15:49:26 -0500 Subject: Check all ancestor state in CTxMemPool::check() --- src/txmempool.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/txmempool.h') diff --git a/src/txmempool.h b/src/txmempool.h index 3f80a6ec24..a82d17c2f8 100644 --- a/src/txmempool.h +++ b/src/txmempool.h @@ -527,7 +527,7 @@ public: * 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); + 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; /** Populate setDescendants with all in-mempool descendants of hash. * Assumes that setDescendants includes all in-mempool descendants of anything -- cgit v1.2.3