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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
|
/*****************************************************************************
Copyright (c) 2021, 2025, Oracle and/or its affiliates.
This program is free software; you can redistribute it and/or modify it under
the terms of the GNU General Public License, version 2.0, as published by the
Free Software Foundation.
This program is designed to work with certain software (including
but not limited to OpenSSL) that is licensed under separate terms,
as designated in a particular file or component or in included license
documentation. The authors of MySQL hereby grant you an additional
permission to link the program and your derivative works with the
separately licensed software that they have either included with
the program or referenced in the documentation.
This program is distributed in the hope that it will be useful, but WITHOUT
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
FOR A PARTICULAR PURPOSE. See the GNU General Public License, version 2.0,
for more details.
You should have received a copy of the GNU General Public License along with
this program; if not, write to the Free Software Foundation, Inc.,
51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
*****************************************************************************/
/** @file include/ut0seq_lock.h
Implements a sequential lock structure for non-locking atomic read/write
operations on a complex structure.
*******************************************************************/
#ifndef ut0seq_lock_h
#define ut0seq_lock_h
#include <atomic>
#include <thread>
#include "ut0class_life_cycle.h"
namespace ut {
/** A class that allows to read value of variable of some type T atomically and
allows the value to be changed, all using lock-free operations. The type T has
to be composed of std::atomic fields only. That is because read(op_r) might read
it in parallel to write(op_w). Other than that you are allowed to use any type.
Inspired by https://www.hpl.hp.com/techreports/2012/HPL-2012-68.pdf Figure 6. */
template <typename T>
class Seq_lock : private Non_copyable {
public:
Seq_lock() = default;
template <typename... Args>
Seq_lock(Args... args) : m_value{std::forward<Args>(args)...} {}
/* This class can be made copyable, but this requires additional constructors.
*/
/** Writes a new value for the variable of type T. The op can use
memory_order_relaxed stores.
NOTE: The user needs to synchronize all calls to this method. */
template <typename Op>
void write(Op &&op) {
const auto old = m_seq.load(std::memory_order_relaxed);
/* The odd value means someone else is executing the write operation
concurrently, and this is not allowed. */
ut_ad((old & 1) == 0);
m_seq.store(old + 1, std::memory_order_relaxed);
/* This fence is meant to synchronize with the fence in read(), whenever
op() in read() happens to load-from any of the values stored by our op().
Then it would follow that load to seq_after will happen-after our
first fetch_add(1), which is all we need. See 32.9.1 of C++17 draft. */
std::atomic_thread_fence(std::memory_order_release);
op(m_value);
m_seq.store(old + 2, std::memory_order_release);
}
/* Reads the value of the stored value of type T using operation op(). The
op() can use memory_order_relaxed loads. The op() can't assume the data stored
inside T is logically consistent. Calls to this method don't need to be
synchronized. */
template <typename Op>
auto read(Op &&op) const {
int try_count = 0;
while (true) {
const auto seq_before = m_seq.load(std::memory_order_acquire);
if ((seq_before & 1) == 1) {
/* Someone is currently writing to the stored value. Try a few times to
read the seq value, if this not help, try to yield execution. */
if ((++try_count & 7) == 0) {
std::this_thread::yield();
}
continue;
}
auto res = op(m_value);
std::atomic_thread_fence(std::memory_order_acquire);
const auto seq_after = m_seq.load(std::memory_order_relaxed);
if (seq_before == seq_after) {
return res;
}
/* The begin and end seq number is different, so the value read from T may
be invalid. Let's just try again to perform the read. We do not want to
yield here, as the new seq value is already set. If it is an odd value, we
will detect it in the next loop and possibly yield. If it is even, we will
just try to read new value. */
}
/* If we got here, then op() has seen a single coherent picture of value.
We have seq_before == seq_after and it is even.
Suppose that one of the loads inside op() saw value written by some writer w
and thus our fence synchronizes-with w's fence, and thus seq_after
assignment happens-after w's first increment of seq.
Since seq_after is even, it must mean it comes from some later store in
seq's modification order, not earlier than w's final increment of seq.
And as seq_before is equal to it, it comes from the same later store.
But, seq_before was assigned using acquire load, thus it
synchronizes-with the store from which it loads, meaning that op() has
to happen-after w's final increment of seq (one might need to follow
the mutex sequence if there were other writers in between).
Thus we see that if op() sees any part of the value written by w, then
it all the other parts of value it sees are at least as fresh.
Since writers are sequenced, it is meaningful to focus on "the latest"
writer whose change our op() detected, and use it as w in above reasoning to
conclude all fragments seen by op() come from it. */
}
private:
/** Stored value. */
T m_value;
/** Sequence count. Even when the value is ready for read, odd when the value
is being written to. */
std::atomic<uint64_t> m_seq{0};
};
} // namespace ut
#endif /* ut0seq_lock_h */
|
