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 Epoch() = default; 41 Epoch(const Epoch&) = delete; 42 Epoch& operator=(const Epoch&) = delete; 43 guarded()44 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: Guard(Epoch & epoch)62 explicit Guard(Epoch& epoch) EXCLUSIVE_LOCK_FUNCTION(epoch) : m_epoch(epoch) 63 { 64 assert(!m_epoch.m_guarded); 65 ++m_epoch.m_raw_epoch; 66 m_epoch.m_guarded = true; 67 } UNLOCK_FUNCTION()68 ~Guard() UNLOCK_FUNCTION() 69 { 70 assert(m_epoch.m_guarded); 71 ++m_epoch.m_raw_epoch; // ensure clear separation between epochs 72 m_epoch.m_guarded = false; 73 } 74 }; 75 visited(Marker & marker)76 bool visited(Marker& marker) const EXCLUSIVE_LOCKS_REQUIRED(*this) 77 { 78 assert(m_guarded); 79 if (marker.m_marker < m_raw_epoch) { 80 // marker is from a previous epoch, so this is its first visit 81 marker.m_marker = m_raw_epoch; 82 return false; 83 } else { 84 return true; 85 } 86 } 87 }; 88 89 #define WITH_FRESH_EPOCH(epoch) const Epoch::Guard PASTE2(epoch_guard_, __COUNTER__)(epoch) 90 91 #endif // BITCOIN_UTIL_EPOCHGUARD_H 92