diff options
author | Wladimir J. van der Laan <laanwj@protonmail.com> | 2021-02-24 09:07:10 +0100 |
---|---|---|
committer | Wladimir J. van der Laan <laanwj@protonmail.com> | 2021-02-24 09:57:21 +0100 |
commit | b59f2787e53318caad6d3292de2cc6e17995d277 (patch) | |
tree | bb9418e42c437df99130c8ad220d53336120836c /src/util | |
parent | 587c986ccf88daef5e979eaa91163349e36a544d (diff) | |
parent | fd6580e405699ccb051fd2a34525e48d3253673d (diff) | |
download | bitcoin-b59f2787e53318caad6d3292de2cc6e17995d277.tar.xz |
Merge #18017: txmempool: split epoch logic into class
fd6580e405699ccb051fd2a34525e48d3253673d [refactor] txmempool: split epoch logic into class (Anthony Towns)
Pull request description:
Splits the epoch logic introduced in #17925 into a separate class.
Uses clang's thread safety annotations and encapsulates the data more strongly to reduce chances of bugs from API misuse.
ACKs for top commit:
jonatack:
ACK fd6580e405699ccb051fd2a34525e48d3253673d using clang thread safety annotations looks like a very good idea, and the encapsulation this change adds should improve robustness (and possible unit test-ability) of the code. Verified that changing some of the locking duly provoked build-time warnings with Clang 9 on Debian and that small changes in the new `Epoch` class were covered by failing functional test assertions in `mempool_updatefromblock.py`, `mempool_resurrect.py`, and `mempool_reorg.py`
hebasto:
re-ACK fd6580e405699ccb051fd2a34525e48d3253673d, since my [previous](https://github.com/bitcoin/bitcoin/pull/18017#pullrequestreview-569619362) review:
Tree-SHA512: 7004623faa02b56639aa05ab7a078320a6d8d54ec62d8022876221e33f350f47df51ddff056c0de5be798f8eb39b5c03c2d3f035698555d70abc218e950f2f8c
Diffstat (limited to 'src/util')
-rw-r--r-- | src/util/epochguard.h | 91 |
1 files changed, 91 insertions, 0 deletions
diff --git a/src/util/epochguard.h b/src/util/epochguard.h new file mode 100644 index 0000000000..1570ec4eb4 --- /dev/null +++ b/src/util/epochguard.h @@ -0,0 +1,91 @@ +// Copyright (c) 2009-2010 Satoshi Nakamoto +// Copyright (c) 2009-2020 The Bitcoin Core developers +// Distributed under the MIT software license, see the accompanying +// file COPYING or http://www.opensource.org/licenses/mit-license.php. + +#ifndef BITCOIN_UTIL_EPOCHGUARD_H +#define BITCOIN_UTIL_EPOCHGUARD_H + +#include <threadsafety.h> + +#include <cassert> + +/** Epoch: 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 traversals 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 LOCKABLE Epoch +{ +private: + uint64_t m_raw_epoch = 0; + bool m_guarded = false; + +public: + Epoch() = default; + Epoch(const Epoch&) = delete; + Epoch& operator=(const Epoch&) = delete; + + bool guarded() const { return m_guarded; } + + class Marker + { + private: + uint64_t m_marker = 0; + + // only allow modification via Epoch member functions + friend class Epoch; + Marker& operator=(const Marker&) = delete; + }; + + class SCOPED_LOCKABLE Guard + { + private: + Epoch& m_epoch; + + public: + explicit Guard(Epoch& epoch) EXCLUSIVE_LOCK_FUNCTION(epoch) : m_epoch(epoch) + { + assert(!m_epoch.m_guarded); + ++m_epoch.m_raw_epoch; + m_epoch.m_guarded = true; + } + ~Guard() UNLOCK_FUNCTION() + { + assert(m_epoch.m_guarded); + ++m_epoch.m_raw_epoch; // ensure clear separation between epochs + m_epoch.m_guarded = false; + } + }; + + bool visited(Marker& marker) const EXCLUSIVE_LOCKS_REQUIRED(*this) + { + assert(m_guarded); + if (marker.m_marker < m_raw_epoch) { + // marker is from a previous epoch, so this is its first visit + marker.m_marker = m_raw_epoch; + return false; + } else { + return true; + } + } +}; + +#define WITH_FRESH_EPOCH(epoch) const Epoch::Guard PASTE2(epoch_guard_, __COUNTER__)(epoch) + +#endif // BITCOIN_UTIL_EPOCHGUARD_H |