/src/abseil-cpp/absl/flags/internal/sequence_lock.h
Line | Count | Source (jump to first uncovered line) |
1 | | // |
2 | | // Copyright 2020 The Abseil Authors. |
3 | | // |
4 | | // Licensed under the Apache License, Version 2.0 (the "License"); |
5 | | // you may not use this file except in compliance with the License. |
6 | | // You may obtain a copy of the License at |
7 | | // |
8 | | // https://www.apache.org/licenses/LICENSE-2.0 |
9 | | // |
10 | | // Unless required by applicable law or agreed to in writing, software |
11 | | // distributed under the License is distributed on an "AS IS" BASIS, |
12 | | // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
13 | | // See the License for the specific language governing permissions and |
14 | | // limitations under the License. |
15 | | |
16 | | #ifndef ABSL_FLAGS_INTERNAL_SEQUENCE_LOCK_H_ |
17 | | #define ABSL_FLAGS_INTERNAL_SEQUENCE_LOCK_H_ |
18 | | |
19 | | #include <stddef.h> |
20 | | #include <stdint.h> |
21 | | |
22 | | #include <atomic> |
23 | | #include <cassert> |
24 | | #include <cstring> |
25 | | |
26 | | #include "absl/base/optimization.h" |
27 | | |
28 | | namespace absl { |
29 | | ABSL_NAMESPACE_BEGIN |
30 | | namespace flags_internal { |
31 | | |
32 | | // Align 'x' up to the nearest 'align' bytes. |
33 | 0 | inline constexpr size_t AlignUp(size_t x, size_t align) { |
34 | 0 | return align * ((x + align - 1) / align); |
35 | 0 | } |
36 | | |
37 | | // A SequenceLock implements lock-free reads. A sequence counter is incremented |
38 | | // before and after each write, and readers access the counter before and after |
39 | | // accessing the protected data. If the counter is verified to not change during |
40 | | // the access, and the sequence counter value was even, then the reader knows |
41 | | // that the read was race-free and valid. Otherwise, the reader must fall back |
42 | | // to a Mutex-based code path. |
43 | | // |
44 | | // This particular SequenceLock starts in an "uninitialized" state in which |
45 | | // TryRead() returns false. It must be enabled by calling MarkInitialized(). |
46 | | // This serves as a marker that the associated flag value has not yet been |
47 | | // initialized and a slow path needs to be taken. |
48 | | // |
49 | | // The memory reads and writes protected by this lock must use the provided |
50 | | // `TryRead()` and `Write()` functions. These functions behave similarly to |
51 | | // `memcpy()`, with one oddity: the protected data must be an array of |
52 | | // `std::atomic<uint64>`. This is to comply with the C++ standard, which |
53 | | // considers data races on non-atomic objects to be undefined behavior. See "Can |
54 | | // Seqlocks Get Along With Programming Language Memory Models?"[1] by Hans J. |
55 | | // Boehm for more details. |
56 | | // |
57 | | // [1] https://www.hpl.hp.com/techreports/2012/HPL-2012-68.pdf |
58 | | class SequenceLock { |
59 | | public: |
60 | 0 | constexpr SequenceLock() : lock_(kUninitialized) {} |
61 | | |
62 | | // Mark that this lock is ready for use. |
63 | 1 | void MarkInitialized() { |
64 | 1 | assert(lock_.load(std::memory_order_relaxed) == kUninitialized); |
65 | 1 | lock_.store(0, std::memory_order_release); |
66 | 1 | } |
67 | | |
68 | | // Copy "size" bytes of data from "src" to "dst", protected as a read-side |
69 | | // critical section of the sequence lock. |
70 | | // |
71 | | // Unlike traditional sequence lock implementations which loop until getting a |
72 | | // clean read, this implementation returns false in the case of concurrent |
73 | | // calls to `Write`. In such a case, the caller should fall back to a |
74 | | // locking-based slow path. |
75 | | // |
76 | | // Returns false if the sequence lock was not yet marked as initialized. |
77 | | // |
78 | | // NOTE: If this returns false, "dst" may be overwritten with undefined |
79 | | // (potentially uninitialized) data. |
80 | 0 | bool TryRead(void* dst, const std::atomic<uint64_t>* src, size_t size) const { |
81 | | // Acquire barrier ensures that no loads done by f() are reordered |
82 | | // above the first load of the sequence counter. |
83 | 0 | int64_t seq_before = lock_.load(std::memory_order_acquire); |
84 | 0 | if (ABSL_PREDICT_FALSE(seq_before & 1) == 1) return false; |
85 | 0 | RelaxedCopyFromAtomic(dst, src, size); |
86 | | // Another acquire fence ensures that the load of 'lock_' below is |
87 | | // strictly ordered after the RelaxedCopyToAtomic call above. |
88 | 0 | std::atomic_thread_fence(std::memory_order_acquire); |
89 | 0 | int64_t seq_after = lock_.load(std::memory_order_relaxed); |
90 | 0 | return ABSL_PREDICT_TRUE(seq_before == seq_after); |
91 | 0 | } |
92 | | |
93 | | // Copy "size" bytes from "src" to "dst" as a write-side critical section |
94 | | // of the sequence lock. Any concurrent readers will be forced to retry |
95 | | // until they get a read that does not conflict with this write. |
96 | | // |
97 | | // This call must be externally synchronized against other calls to Write, |
98 | | // but may proceed concurrently with reads. |
99 | 0 | void Write(std::atomic<uint64_t>* dst, const void* src, size_t size) { |
100 | | // We can use relaxed instructions to increment the counter since we |
101 | | // are extenally synchronized. The std::atomic_thread_fence below |
102 | | // ensures that the counter updates don't get interleaved with the |
103 | | // copy to the data. |
104 | 0 | int64_t orig_seq = lock_.load(std::memory_order_relaxed); |
105 | 0 | assert((orig_seq & 1) == 0); // Must be initially unlocked. |
106 | 0 | lock_.store(orig_seq + 1, std::memory_order_relaxed); |
107 | | |
108 | | // We put a release fence between update to lock_ and writes to shared data. |
109 | | // Thus all stores to shared data are effectively release operations and |
110 | | // update to lock_ above cannot be re-ordered past any of them. Note that |
111 | | // this barrier is not for the fetch_add above. A release barrier for the |
112 | | // fetch_add would be before it, not after. |
113 | 0 | std::atomic_thread_fence(std::memory_order_release); |
114 | 0 | RelaxedCopyToAtomic(dst, src, size); |
115 | | // "Release" semantics ensure that none of the writes done by |
116 | | // RelaxedCopyToAtomic() can be reordered after the following modification. |
117 | 0 | lock_.store(orig_seq + 2, std::memory_order_release); |
118 | 0 | } |
119 | | |
120 | | // Return the number of times that Write() has been called. |
121 | | // |
122 | | // REQUIRES: This must be externally synchronized against concurrent calls to |
123 | | // `Write()` or `IncrementModificationCount()`. |
124 | | // REQUIRES: `MarkInitialized()` must have been previously called. |
125 | 0 | int64_t ModificationCount() const { |
126 | 0 | int64_t val = lock_.load(std::memory_order_relaxed); |
127 | 0 | assert(val != kUninitialized && (val & 1) == 0); |
128 | 0 | return val / 2; |
129 | 0 | } |
130 | | |
131 | | // REQUIRES: This must be externally synchronized against concurrent calls to |
132 | | // `Write()` or `ModificationCount()`. |
133 | | // REQUIRES: `MarkInitialized()` must have been previously called. |
134 | 0 | void IncrementModificationCount() { |
135 | 0 | int64_t val = lock_.load(std::memory_order_relaxed); |
136 | 0 | assert(val != kUninitialized); |
137 | 0 | lock_.store(val + 2, std::memory_order_relaxed); |
138 | 0 | } |
139 | | |
140 | | private: |
141 | | // Perform the equivalent of "memcpy(dst, src, size)", but using relaxed |
142 | | // atomics. |
143 | | static void RelaxedCopyFromAtomic(void* dst, const std::atomic<uint64_t>* src, |
144 | 0 | size_t size) { |
145 | 0 | char* dst_byte = static_cast<char*>(dst); |
146 | 0 | while (size >= sizeof(uint64_t)) { |
147 | 0 | uint64_t word = src->load(std::memory_order_relaxed); |
148 | 0 | std::memcpy(dst_byte, &word, sizeof(word)); |
149 | 0 | dst_byte += sizeof(word); |
150 | 0 | src++; |
151 | 0 | size -= sizeof(word); |
152 | 0 | } |
153 | 0 | if (size > 0) { |
154 | 0 | uint64_t word = src->load(std::memory_order_relaxed); |
155 | 0 | std::memcpy(dst_byte, &word, size); |
156 | 0 | } |
157 | 0 | } |
158 | | |
159 | | // Perform the equivalent of "memcpy(dst, src, size)", but using relaxed |
160 | | // atomics. |
161 | | static void RelaxedCopyToAtomic(std::atomic<uint64_t>* dst, const void* src, |
162 | 0 | size_t size) { |
163 | 0 | const char* src_byte = static_cast<const char*>(src); |
164 | 0 | while (size >= sizeof(uint64_t)) { |
165 | 0 | uint64_t word; |
166 | 0 | std::memcpy(&word, src_byte, sizeof(word)); |
167 | 0 | dst->store(word, std::memory_order_relaxed); |
168 | 0 | src_byte += sizeof(word); |
169 | 0 | dst++; |
170 | 0 | size -= sizeof(word); |
171 | 0 | } |
172 | 0 | if (size > 0) { |
173 | 0 | uint64_t word = 0; |
174 | 0 | std::memcpy(&word, src_byte, size); |
175 | 0 | dst->store(word, std::memory_order_relaxed); |
176 | 0 | } |
177 | 0 | } |
178 | | |
179 | | static constexpr int64_t kUninitialized = -1; |
180 | | std::atomic<int64_t> lock_; |
181 | | }; |
182 | | |
183 | | } // namespace flags_internal |
184 | | ABSL_NAMESPACE_END |
185 | | } // namespace absl |
186 | | |
187 | | #endif // ABSL_FLAGS_INTERNAL_SEQUENCE_LOCK_H_ |