From fd6580e405699ccb051fd2a34525e48d3253673d Mon Sep 17 00:00:00 2001 From: Anthony Towns Date: Fri, 4 Dec 2020 12:49:22 +1000 Subject: [refactor] txmempool: split epoch logic into class --- src/txmempool.h | 55 +++++++++++++------------------------------------------ 1 file changed, 13 insertions(+), 42 deletions(-) (limited to 'src/txmempool.h') diff --git a/src/txmempool.h b/src/txmempool.h index c0df33fe13..7b8fe28ad7 100644 --- a/src/txmempool.h +++ b/src/txmempool.h @@ -21,6 +21,7 @@ #include #include #include +#include #include #include @@ -63,6 +64,7 @@ struct CompareIteratorByHash { return a->GetTx().GetHash() < b->GetTx().GetHash(); } }; + /** \class CTxMemPoolEntry * * CTxMemPoolEntry stores data about the corresponding transaction, as well @@ -155,7 +157,7 @@ public: Children& GetMemPoolChildren() const { return m_children; } mutable size_t vTxHashesIdx; //!< Index in mempool's vTxHashes - mutable uint64_t m_epoch; //!< epoch when last touched, useful for graph algorithms + mutable Epoch::Marker m_epoch_marker; //!< epoch when last touched, useful for graph algorithms }; // Helpers for modifying CTxMemPool::mapTx, which is a boost multi_index. @@ -485,8 +487,7 @@ private: mutable int64_t lastRollingFeeUpdate; mutable bool blockSinceLastRollingFeeBump; mutable double rollingMinimumFeeRate; //!< minimum fee to get into the pool, decreases exponentially - mutable uint64_t m_epoch{0}; - mutable bool m_has_epoch_guard{false}; + mutable Epoch m_epoch GUARDED_BY(cs); // In-memory counter for external mempool tracking purposes. // This number is incremented once every time a transaction @@ -665,7 +666,7 @@ public: * 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& vHashesToUpdate) EXCLUSIVE_LOCKS_REQUIRED(cs, cs_main); + void UpdateTransactionsFromBlock(const std::vector& vHashesToUpdate) EXCLUSIVE_LOCKS_REQUIRED(cs, cs_main) LOCKS_EXCLUDED(m_epoch); /** Try to calculate all in-mempool ancestors of entry. * (these are all calculated including the tx itself) @@ -826,52 +827,22 @@ private: */ void removeUnchecked(txiter entry, MemPoolRemovalReason reason) EXCLUSIVE_LOCKS_REQUIRED(cs); public: - /** EpochGuard: RAII-style guard for using epoch-based graph traversal algorithms. - * When walking ancestors or descendants, we generally want to avoid - * visiting the same transactions twice. Some traversal algorithms use - * std::set (or setEntries) to deduplicate the transaction we visit. - * However, use of std::set is algorithmically undesirable because it both - * adds an asymptotic factor of O(log n) to traverals cost and triggers O(n) - * more dynamic memory allocations. - * In many algorithms we can replace std::set with an internal mempool - * counter to track the time (or, "epoch") that we began a traversal, and - * check + update a per-transaction epoch for each transaction we look at to - * determine if that transaction has not yet been visited during the current - * traversal's epoch. - * Algorithms using std::set can be replaced on a one by one basis. - * Both techniques are not fundamentally incompatible across the codebase. - * Generally speaking, however, the remaining use of std::set for mempool - * traversal should be viewed as a TODO for replacement with an epoch based - * traversal, rather than a preference for std::set over epochs in that - * algorithm. - */ - class EpochGuard { - const CTxMemPool& pool; - public: - explicit EpochGuard(const CTxMemPool& in); - ~EpochGuard(); - }; - // N.B. GetFreshEpoch modifies mutable state via the EpochGuard construction - // (and later destruction) - EpochGuard GetFreshEpoch() const EXCLUSIVE_LOCKS_REQUIRED(cs); - /** visited marks a CTxMemPoolEntry as having been traversed - * during the lifetime of the most recently created EpochGuard + * during the lifetime of the most recently created Epoch::Guard * and returns false if we are the first visitor, true otherwise. * - * An EpochGuard must be held when visited is called or an assert will be + * An Epoch::Guard must be held when visited is called or an assert will be * triggered. * */ - bool visited(txiter it) const EXCLUSIVE_LOCKS_REQUIRED(cs) { - assert(m_has_epoch_guard); - bool ret = it->m_epoch >= m_epoch; - it->m_epoch = std::max(it->m_epoch, m_epoch); - return ret; + bool visited(const txiter it) const EXCLUSIVE_LOCKS_REQUIRED(cs, m_epoch) + { + return m_epoch.visited(it->m_epoch_marker); } - bool visited(Optional it) const EXCLUSIVE_LOCKS_REQUIRED(cs) { - assert(m_has_epoch_guard); + bool visited(Optional it) const EXCLUSIVE_LOCKS_REQUIRED(cs, m_epoch) + { + assert(m_epoch.guarded()); // verify guard even when it==nullopt return !it || visited(*it); } }; -- cgit v1.2.3