Branch data Line data Source code
# 1 : : // Copyright (c) 2009-2010 Satoshi Nakamoto # 2 : : // Copyright (c) 2009-2020 The Bitcoin Core developers # 3 : : // Distributed under the MIT software license, see the accompanying # 4 : : // file COPYING or http://www.opensource.org/licenses/mit-license.php. # 5 : : # 6 : : #ifndef BITCOIN_UTIL_EPOCHGUARD_H # 7 : : #define BITCOIN_UTIL_EPOCHGUARD_H # 8 : : # 9 : : #include <threadsafety.h> # 10 : : # 11 : : #include <cassert> # 12 : : # 13 : : /** Epoch: RAII-style guard for using epoch-based graph traversal algorithms. # 14 : : * When walking ancestors or descendants, we generally want to avoid # 15 : : * visiting the same transactions twice. Some traversal algorithms use # 16 : : * std::set (or setEntries) to deduplicate the transaction we visit. # 17 : : * However, use of std::set is algorithmically undesirable because it both # 18 : : * adds an asymptotic factor of O(log n) to traversals cost and triggers O(n) # 19 : : * more dynamic memory allocations. # 20 : : * In many algorithms we can replace std::set with an internal mempool # 21 : : * counter to track the time (or, "epoch") that we began a traversal, and # 22 : : * check + update a per-transaction epoch for each transaction we look at to # 23 : : * determine if that transaction has not yet been visited during the current # 24 : : * traversal's epoch. # 25 : : * Algorithms using std::set can be replaced on a one by one basis. # 26 : : * Both techniques are not fundamentally incompatible across the codebase. # 27 : : * Generally speaking, however, the remaining use of std::set for mempool # 28 : : * traversal should be viewed as a TODO for replacement with an epoch based # 29 : : * traversal, rather than a preference for std::set over epochs in that # 30 : : * algorithm. # 31 : : */ # 32 : : # 33 : : class LOCKABLE Epoch # 34 : : { # 35 : : private: # 36 : : uint64_t m_raw_epoch = 0; # 37 : : bool m_guarded = false; # 38 : : # 39 : : public: # 40 : 4825 : Epoch() = default; # 41 : : Epoch(const Epoch&) = delete; # 42 : : Epoch& operator=(const Epoch&) = delete; # 43 : : # 44 : 0 : bool guarded() const { return m_guarded; } # 45 : : # 46 : : class Marker # 47 : : { # 48 : : private: # 49 : : uint64_t m_marker = 0; # 50 : : # 51 : : // only allow modification via Epoch member functions # 52 : : friend class Epoch; # 53 : : Marker& operator=(const Marker&) = delete; # 54 : : }; # 55 : : # 56 : : class SCOPED_LOCKABLE Guard # 57 : : { # 58 : : private: # 59 : : Epoch& m_epoch; # 60 : : # 61 : : public: # 62 : : explicit Guard(Epoch& epoch) EXCLUSIVE_LOCK_FUNCTION(epoch) : m_epoch(epoch) # 63 : 293 : { # 64 : 293 : assert(!m_epoch.m_guarded); # 65 : 293 : ++m_epoch.m_raw_epoch; # 66 : 293 : m_epoch.m_guarded = true; # 67 : 293 : } # 68 : : ~Guard() UNLOCK_FUNCTION() # 69 : 293 : { # 70 : 293 : assert(m_epoch.m_guarded); # 71 : 293 : ++m_epoch.m_raw_epoch; // ensure clear separation between epochs # 72 : 293 : m_epoch.m_guarded = false; # 73 : 293 : } # 74 : : }; # 75 : : # 76 : : bool visited(Marker& marker) const EXCLUSIVE_LOCKS_REQUIRED(*this) # 77 : 4733 : { # 78 : 4733 : assert(m_guarded); # 79 [ + + ]: 4733 : if (marker.m_marker < m_raw_epoch) { # 80 : : // marker is from a previous epoch, so this is its first visit # 81 : 4727 : marker.m_marker = m_raw_epoch; # 82 : 4727 : return false; # 83 : 4727 : } else { # 84 : 6 : return true; # 85 : 6 : } # 86 : 4733 : } # 87 : : }; # 88 : : # 89 : 293 : #define WITH_FRESH_EPOCH(epoch) const Epoch::Guard PASTE2(epoch_guard_, __COUNTER__)(epoch) # 90 : : # 91 : : #endif // BITCOIN_UTIL_EPOCHGUARD_H