blob: 7f6477fb3b48064535a9c34bdd764daf9ef2f505 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
|
// Copyright (c) 2009-2010 Satoshi Nakamoto
// Copyright (c) 2009-2021 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 <util/macros.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;
Epoch(Epoch&&) = delete;
Epoch& operator=(Epoch&&) = delete;
~Epoch() = default;
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;
public:
Marker() = default;
Marker(const Marker&) = default;
Marker(Marker&&) = delete;
Marker& operator=(Marker&&) = delete;
~Marker() = default;
};
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 UNIQUE_NAME(epoch_guard_)(epoch)
#endif // BITCOIN_UTIL_EPOCHGUARD_H
|
