/Users/eugenesiegel/btc/bitcoin/src/util/epochguard.h
Line | Count | Source (jump to first uncovered line) |
1 | | // Copyright (c) 2009-2010 Satoshi Nakamoto |
2 | | // Copyright (c) 2009-2022 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 | | #include <util/macros.h> |
11 | | |
12 | | #include <cassert> |
13 | | |
14 | | /** Epoch: RAII-style guard for using epoch-based graph traversal algorithms. |
15 | | * When walking ancestors or descendants, we generally want to avoid |
16 | | * visiting the same transactions twice. Some traversal algorithms use |
17 | | * std::set (or setEntries) to deduplicate the transaction we visit. |
18 | | * However, use of std::set is algorithmically undesirable because it both |
19 | | * adds an asymptotic factor of O(log n) to traversals cost and triggers O(n) |
20 | | * more dynamic memory allocations. |
21 | | * In many algorithms we can replace std::set with an internal mempool |
22 | | * counter to track the time (or, "epoch") that we began a traversal, and |
23 | | * check + update a per-transaction epoch for each transaction we look at to |
24 | | * determine if that transaction has not yet been visited during the current |
25 | | * traversal's epoch. |
26 | | * Algorithms using std::set can be replaced on a one by one basis. |
27 | | * Both techniques are not fundamentally incompatible across the codebase. |
28 | | * Generally speaking, however, the remaining use of std::set for mempool |
29 | | * traversal should be viewed as a TODO for replacement with an epoch based |
30 | | * traversal, rather than a preference for std::set over epochs in that |
31 | | * algorithm. |
32 | | */ |
33 | | |
34 | | class LOCKABLE Epoch |
35 | | { |
36 | | private: |
37 | | uint64_t m_raw_epoch = 0; |
38 | | bool m_guarded = false; |
39 | | |
40 | | public: |
41 | 51.2k | Epoch() = default; |
42 | | Epoch(const Epoch&) = delete; |
43 | | Epoch& operator=(const Epoch&) = delete; |
44 | | Epoch(Epoch&&) = delete; |
45 | | Epoch& operator=(Epoch&&) = delete; |
46 | | ~Epoch() = default; |
47 | | |
48 | 0 | bool guarded() const { return m_guarded; } |
49 | | |
50 | | class Marker |
51 | | { |
52 | | private: |
53 | | uint64_t m_marker = 0; |
54 | | |
55 | | // only allow modification via Epoch member functions |
56 | | friend class Epoch; |
57 | | Marker& operator=(const Marker&) = delete; |
58 | | |
59 | | public: |
60 | 638k | Marker() = default; |
61 | | Marker(const Marker&) = default; |
62 | | Marker(Marker&&) = delete; |
63 | | Marker& operator=(Marker&&) = delete; |
64 | | ~Marker() = default; |
65 | | }; |
66 | | |
67 | | class SCOPED_LOCKABLE Guard |
68 | | { |
69 | | private: |
70 | | Epoch& m_epoch; |
71 | | |
72 | | public: |
73 | 0 | explicit Guard(Epoch& epoch) EXCLUSIVE_LOCK_FUNCTION(epoch) : m_epoch(epoch) |
74 | 0 | { |
75 | 0 | assert(!m_epoch.m_guarded); |
76 | 0 | ++m_epoch.m_raw_epoch; |
77 | 0 | m_epoch.m_guarded = true; |
78 | 0 | } |
79 | | ~Guard() UNLOCK_FUNCTION() |
80 | 0 | { |
81 | 0 | assert(m_epoch.m_guarded); |
82 | 0 | ++m_epoch.m_raw_epoch; // ensure clear separation between epochs |
83 | 0 | m_epoch.m_guarded = false; |
84 | 0 | } |
85 | | }; |
86 | | |
87 | | bool visited(Marker& marker) const EXCLUSIVE_LOCKS_REQUIRED(*this) |
88 | 0 | { |
89 | 0 | assert(m_guarded); |
90 | 0 | if (marker.m_marker < m_raw_epoch) { |
91 | | // marker is from a previous epoch, so this is its first visit |
92 | 0 | marker.m_marker = m_raw_epoch; |
93 | 0 | return false; |
94 | 0 | } else { |
95 | 0 | return true; |
96 | 0 | } |
97 | 0 | } |
98 | | }; |
99 | | |
100 | 0 | #define WITH_FRESH_EPOCH(epoch) const Epoch::Guard UNIQUE_NAME(epoch_guard_)(epoch) |
101 | | |
102 | | #endif // BITCOIN_UTIL_EPOCHGUARD_H |