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