Page MenuHomePhabricator
Files F13115727

D8733.diff
No OneTemporary
Actions

D8733.diff
View Options

diff --git a/src/txmempool.h b/src/txmempool.h
--- a/src/txmempool.h
+++ b/src/txmempool.h
@@ -159,6 +159,8 @@
//! Index in mempool's vTxHashes
mutable size_t vTxHashesIdx;
+ //! epoch when last touched, useful for graph algorithms
+ mutable uint64_t m_epoch;
};
// Helpers for modifying CTxMemPool::mapTx, which is a boost multi_index.
@@ -481,6 +483,8 @@
mutable bool blockSinceLastRollingFeeBump;
//! minimum fee to get into the pool, decreases exponentially
mutable double rollingMinimumFeeRate;
+ mutable uint64_t m_epoch;
+ mutable bool m_has_epoch_guard;
void trackPackageRemoved(const CFeeRate &rate) EXCLUSIVE_LOCKS_REQUIRED(cs);
@@ -824,6 +828,59 @@
*/
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:
+ 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
+ * 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
+ * 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(std::optional<txiter> it) const EXCLUSIVE_LOCKS_REQUIRED(cs) {
+ assert(m_has_epoch_guard);
+ return !it || visited(*it);
+ }
};
/**
diff --git a/src/txmempool.cpp b/src/txmempool.cpp
--- a/src/txmempool.cpp
+++ b/src/txmempool.cpp
@@ -32,7 +32,7 @@
: tx(_tx), nFee(_nFee), nTxSize(tx->GetTotalSize()),
nUsageSize(RecursiveDynamicUsage(tx)), nTime(_nTime),
entryHeight(_entryHeight), spendsCoinbase(_spendsCoinbase),
- sigOpCount(_sigOpsCount), lockPoints(lp) {
+ sigOpCount(_sigOpsCount), lockPoints(lp), m_epoch(0) {
nCountWithDescendants = 1;
nSizeWithDescendants = GetTxSize();
nSigOpCountWithDescendants = sigOpCount;
@@ -151,8 +151,6 @@
// setMemPoolChildren will be updated, an assumption made in
// UpdateForDescendants.
for (const TxId &txid : reverse_iterate(txidsToUpdate)) {
- // we cache the in-mempool children to avoid duplicate updates
- setEntries setChildren;
// calculate children from mapNextTx
txiter it = mapTx.find(txid);
if (it == mapTx.end()) {
@@ -162,19 +160,23 @@
auto iter = mapNextTx.lower_bound(COutPoint(txid, 0));
// First calculate the children, and update setMemPoolChildren to
// include them, and update their setMemPoolParents to include this tx.
- for (; iter != mapNextTx.end() && iter->first->GetTxId() == txid;
- ++iter) {
- const TxId &childTxId = iter->second->GetId();
- txiter childIter = mapTx.find(childTxId);
- assert(childIter != mapTx.end());
- // We can skip updating entries we've encountered before or that are
- // in the block (which are already accounted for).
- if (setChildren.insert(childIter).second &&
- !setAlreadyIncluded.count(childTxId)) {
- UpdateChild(it, childIter, true);
- UpdateParent(childIter, it, true);
+ // we cache the in-mempool children to avoid duplicate updates
+ {
+ const auto epoch = GetFreshEpoch();
+ for (; iter != mapNextTx.end() && iter->first->GetTxId() == txid;
+ ++iter) {
+ const TxId &childTxId = iter->second->GetId();
+ txiter childIter = mapTx.find(childTxId);
+ assert(childIter != mapTx.end());
+ // We can skip updating entries we've encountered before or that
+ // are in the block (which are already accounted for).
+ if (!visited(childIter) &&
+ !setAlreadyIncluded.count(childTxId)) {
+ UpdateChild(it, childIter, true);
+ UpdateParent(childIter, it, true);
+ }
}
- }
+ } // release epoch guard for UpdateForDescendants
UpdateForDescendants(it, mapMemPoolDescendantsToUpdate,
setAlreadyIncluded);
}
@@ -387,7 +389,8 @@
assert(int(nSigOpCountWithAncestors) >= 0);
}
-CTxMemPool::CTxMemPool() : nTransactionsUpdated(0) {
+CTxMemPool::CTxMemPool()
+ : nTransactionsUpdated(0), m_epoch(0), m_has_epoch_guard(false) {
// lock free clear
_clear();
@@ -1424,3 +1427,19 @@
std::chrono::hours{
gArgs.GetArg("-mempoolexpiry", DEFAULT_MEMPOOL_EXPIRY)});
}
+
+CTxMemPool::EpochGuard CTxMemPool::GetFreshEpoch() const {
+ return EpochGuard(*this);
+}
+
+CTxMemPool::EpochGuard::EpochGuard(const CTxMemPool &in) : pool(in) {
+ assert(!pool.m_has_epoch_guard);
+ ++pool.m_epoch;
+ pool.m_has_epoch_guard = true;
+}
+
+CTxMemPool::EpochGuard::~EpochGuard() {
+ // prevents stale results being used
+ ++pool.m_epoch;
+ pool.m_has_epoch_guard = false;
+}

File Metadata

Mime Type
text/plain
Expires
Sat, Mar 1, 11:53 (4 h, 1 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
5187716
Default Alt Text
D8733.diff (6 KB)

Event Timeline