MySQL 8.0.31
Source Code Documentation
ut0seq_lock.h
Go to the documentation of this file.
1/*****************************************************************************
2
3Copyright (c) 2021, 2022, Oracle and/or its affiliates.
4
5This program is free software; you can redistribute it and/or modify it under
6the terms of the GNU General Public License, version 2.0, as published by the
7Free Software Foundation.
8
9This program is also distributed with certain software (including but not
10limited to OpenSSL) that is licensed under separate terms, as designated in a
11particular file or component or in included license documentation. The authors
12of MySQL hereby grant you an additional permission to link the program and
13your derivative works with the separately licensed software that they have
14included with MySQL.
15
16This program is distributed in the hope that it will be useful, but WITHOUT
17ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
18FOR A PARTICULAR PURPOSE. See the GNU General Public License, version 2.0,
19for more details.
20
21You should have received a copy of the GNU General Public License along with
22this program; if not, write to the Free Software Foundation, Inc.,
2351 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
24
25*****************************************************************************/
26
27/** @file include/ut0seq_lock.h
28 Implements a sequential lock structure for non-locking atomic read/write
29 operations on a complex structure.
30
31 *******************************************************************/
32
33#ifndef ut0seq_lock_h
34#define ut0seq_lock_h
35
36#include <atomic>
37#include <thread>
38
39#include "ut0class_life_cycle.h"
40
41namespace ut {
42/** A class that allows to read value of variable of some type T atomically and
43allows the value to be changed, all using lock-free operations. The type T has
44to be composed of std::atomic fields only. That is because read(op_r) might read
45it in parallel to write(op_w). Other than that you are allowed to use any type.
46Inspired by https://www.hpl.hp.com/techreports/2012/HPL-2012-68.pdf Figure 6. */
47template <typename T>
48class Seq_lock : private Non_copyable {
49 public:
50 Seq_lock() = default;
51
52 template <typename... Args>
53 Seq_lock(Args... args) : m_value{std::forward<Args>(args)...} {}
54 /* This class can be made copyable, but this requires additional constructors.
55 */
56
57 /** Writes a new value for the variable of type T. The op can use
58 memory_order_relaxed stores.
59 NOTE: The user needs to synchronize all calls to this method. */
60 template <typename Op>
61 void write(Op &&op) {
62 const auto old = m_seq.load(std::memory_order_relaxed);
63 /* The odd value means someone else is executing the write operation
64 concurrently, and this is not allowed. */
65 ut_ad((old & 1) == 0);
66 m_seq.store(old + 1, std::memory_order_relaxed);
67 /* This fence is meant to synchronize with the fence in read(), whenever
68 op() in read() happens to load-from any of the values stored by our op().
69 Then it would follow that load to seq_after will happen-after our
70 first fetch_add(1), which is all we need. See 32.9.1 of C++17 draft. */
71 std::atomic_thread_fence(std::memory_order_release);
72 op(m_value);
73 m_seq.store(old + 2, std::memory_order_release);
74 }
75 /* Reads the value of the stored value of type T using operation op(). The
76 op() can use memory_order_relaxed loads. The op() can't assume the data stored
77 inside T is logically consistent. Calls to this method don't need to be
78 synchronized. */
79 template <typename Op>
80 auto read(Op &&op) const {
81 int try_count = 0;
82 while (true) {
83 const auto seq_before = m_seq.load(std::memory_order_acquire);
84 if ((seq_before & 1) == 1) {
85 /* Someone is currently writing to the stored value. Try a few times to
86 read the seq value, if this not help, try to yield execution. */
87 if ((++try_count & 7) == 0) {
88 std::this_thread::yield();
89 }
90 continue;
91 }
92 auto res = op(m_value);
93 std::atomic_thread_fence(std::memory_order_acquire);
94 const auto seq_after = m_seq.load(std::memory_order_relaxed);
95 if (seq_before == seq_after) {
96 return res;
97 }
98 /* The begin and end seq number is different, so the value read from T may
99 be invalid. Let's just try again to perform the read. We do not want to
100 yield here, as the new seq value is already set. If it is an odd value, we
101 will detect it in the next loop and possibly yield. If it is even, we will
102 just try to read new value. */
103 }
104 /* If we got here, then op() has seen a single coherent picture of value.
105 We have seq_before == seq_after and it is even.
106 Suppose that one of the loads inside op() saw value written by some writer w
107 and thus our fence synchronizes-with w's fence, and thus seq_after
108 assignment happens-after w's first increment of seq.
109 Since seq_after is even, it must mean it comes from some later store in
110 seq's modification order, not earlier than w's final increment of seq.
111 And as seq_before is equal to it, it comes from the same later store.
112 But, seq_before was assigned using acquire load, thus it
113 synchronizes-with the store from which it loads, meaning that op() has
114 to happen-after w's final increment of seq (one might need to follow
115 the mutex sequence if there were other writers in between).
116 Thus we see that if op() sees any part of the value written by w, then
117 it all the other parts of value it sees are at least as fresh.
118 Since writers are sequenced, it is meaningful to focus on "the latest"
119 writer whose change our op() detected, and use it as w in above reasoning to
120 conclude all fragments seen by op() come from it. */
121 }
122
123 private:
124 /** Stored value. */
126 /** Sequence count. Even when the value is ready for read, odd when the value
127 is being written to. */
128 std::atomic<uint64_t> m_seq{0};
129};
130} // namespace ut
131
132#endif /* ut0seq_lock_h */
A utility class which, if inherited from, prevents the descendant class from being copied,...
Definition: ut0class_life_cycle.h:40
A class that allows to read value of variable of some type T atomically and allows the value to be ch...
Definition: ut0seq_lock.h:48
void write(Op &&op)
Writes a new value for the variable of type T.
Definition: ut0seq_lock.h:61
std::atomic< uint64_t > m_seq
Sequence count.
Definition: ut0seq_lock.h:128
T m_value
Stored value.
Definition: ut0seq_lock.h:125
auto read(Op &&op) const
Definition: ut0seq_lock.h:80
Seq_lock()=default
Seq_lock(Args... args)
Definition: ut0seq_lock.h:53
Definition: varlen_sort.h:183
This file contains a set of libraries providing overloads for regular dynamic allocation routines whi...
Definition: aligned_alloc.h:47
Utilities related to class lifecycle.
#define ut_ad(EXPR)
Debug assertion.
Definition: ut0dbg.h:68