Roc Toolkit internal modules
Roc Toolkit: real-time audio streaming
Loading...
Searching...
No Matches
seqlock.h
Go to the documentation of this file.
1/*
2 * Copyright (c) 2020 Roc Streaming authors
3 *
4 * This Source Code Form is subject to the terms of the Mozilla Public
5 * License, v. 2.0. If a copy of the MPL was not distributed with this
6 * file, You can obtain one at http://mozilla.org/MPL/2.0/.
7 */
8
9//! @file roc_core/seqlock.h
10//! @brief Seqlock.
11
12#ifndef ROC_CORE_SEQLOCK_H_
13#define ROC_CORE_SEQLOCK_H_
14
15#include "roc_core/atomic_ops.h"
18#include "roc_core/stddefs.h"
19
20namespace roc {
21namespace core {
22
23//! Type for holding seqlock value version.
24//! Version is changed each value update.
25//! May wrap.
27
28//! Check if given seqlock version corresponds to dirty value.
30 return (ver & 1) != 0;
31}
32
33//! Seqlock.
34//!
35//! Provides safe concurrent access to a single value.
36//! Provides sequential consistency.
37//! Optimized for infrequent writes and frequent reads.
38//! Writes are lock-free and take priority over reads.
39//!
40//! See details on the barriers here:
41//! https://elixir.bootlin.com/linux/latest/source/include/linux/seqlock.h
42//! https://www.hpl.hp.com/techreports/2012/HPL-2012-68.pdf
43template <class T> class Seqlock : public NonCopyable<> {
44public:
45 //! Initialize with given value.
46 explicit Seqlock(T value)
47 : val_(value)
48 , ver_(0) {
49 }
50
51 //! Load value version.
52 //! Wait-free.
53 inline seqlock_version_t version() const {
54 return load_version_();
55 }
56
57 //! Store value.
58 //! Can be called concurrently, but only one concurrent call will succeed.
59 //! Is both lock-free and wait-free, i.e. it never waits for sleeping threads
60 //! and never spins.
61 //! After this call returns, any thread calling wait_load() is guaranteed to
62 //! get the updated value, and try_load() is guaranteed either return the
63 //! updated value or fail (if changes are not fully published yet).
64 inline bool try_store(const T& value) {
66 return try_store_(value, ver);
67 }
68
69 //! Store value.
70 //! Like try_store(), but also returns updated version.
71 inline bool try_store_ver(const T& value, seqlock_version_t& ver) {
72 return try_store_(value, ver);
73 }
74
75 //! Store value.
76 //! Can NOT be called concurrently, assumes that writes are serialized.
77 //! Is both lock-free and wait-free, i.e. it never waits for sleeping threads
78 //! and never spins.
79 //! After this call returns, any thread calling wait_load() is guaranteed to
80 //! get the updated value, and try_load() is guaranteed either return the
81 //! updated value or fail (if changes are not fully published yet).
82 inline void exclusive_store(const T& value) {
84 exclusive_store_(value, ver);
85 }
86
87 //! Store value.
88 //! Like exclusive_store(), but also returns updated version.
89 inline void exclusive_store_ver(const T& value, seqlock_version_t& ver) {
90 exclusive_store_(value, ver);
91 }
92
93 //! Try to load value.
94 //! Returns true if the value was loaded.
95 //! May return false if concurrent store is currently in progress.
96 //! Is both lock-free and wait-free, i.e. it never waits for sleeping threads
97 //! and never spins.
98 inline bool try_load(T& value) const {
100 return try_load_repeat_(value, ver);
101 }
102
103 //! Try to load value and version.
104 //! Like try_load(), but also returns version.
105 inline bool try_load_ver(T& value, seqlock_version_t& ver) const {
106 return try_load_repeat_(value, ver);
107 }
108
109 //! Load value.
110 //! May spin until concurrent store completes.
111 //! Is NOT lock-free (or wait-free).
112 inline T wait_load() const {
113 T value;
115 wait_load_(value, ver);
116 return value;
117 }
118
119 //! Load value and version.
120 //! Like wait_load(), but also returns version.
121 inline void wait_load_ver(T& value, seqlock_version_t& ver) const {
122 wait_load_(value, ver);
123 }
124
125private:
126 inline seqlock_version_t load_version_() const {
127 return AtomicOps::load_seq_cst(ver_);
128 }
129
130 inline void exclusive_store_(const T& value, seqlock_version_t& ver) {
132 AtomicOps::store_relaxed(ver_, ver0 + 1);
134
135 volatile_copy_(val_, value);
137
138 ver = ver0 + 2;
139 AtomicOps::store_relaxed(ver_, ver);
140 }
141
142 inline bool try_store_(const T& value, seqlock_version_t& ver) {
144 if (ver0 & 1) {
145 return false;
146 }
147
148 if (!AtomicOps::compare_exchange_relaxed(ver_, ver0, ver0 + 1)) {
149 return false;
150 }
152
153 volatile_copy_(val_, value);
155
156 ver = ver0 + 2;
157 AtomicOps::store_relaxed(ver_, ver);
158
159 return true;
160 }
161
162 inline void wait_load_(T& value, seqlock_version_t& ver) const {
163 while (!try_load_(value, ver)) {
164 cpu_relax();
165 }
166 }
167
168 // If the concurrent store is running and is not sleeping, retrying 3 times
169 // should be enough to succeed. This may fail if the concurrent store was
170 // preempted in the middle, of if there are multiple concurrent stores.
171 inline bool try_load_repeat_(T& value, seqlock_version_t& ver) const {
172 if (try_load_(value, ver)) {
173 return true;
174 }
175 if (try_load_(value, ver)) {
176 return true;
177 }
178 if (try_load_(value, ver)) {
179 return true;
180 }
181 return false;
182 }
183
184 inline bool try_load_(T& value, seqlock_version_t& ver) const {
187
188 volatile_copy_(value, val_);
190
191 ver = AtomicOps::load_relaxed(ver_);
192 return ((ver0 & 1) == 0 && ver0 == ver);
193 }
194
195 // We use hand-rolled loop instead of memcpy() or default (trivial) copy constructor
196 // to be sure that the copying will be covered by our memory fences. On some
197 // platforms, memcpy() and copy constructor may be implemented using streaming
198 // instructions which may ignore memory fences.
199 static void volatile_copy_(volatile T& dst, const volatile T& src) {
200 volatile char* dst_ptr = reinterpret_cast<volatile char*>(&dst);
201 const volatile char* src_ptr = reinterpret_cast<const volatile char*>(&src);
202
203 for (size_t n = 0; n < sizeof(T); n++) {
204 dst_ptr[n] = src_ptr[n];
205 }
206 }
207
208 T val_;
210};
211
212} // namespace core
213} // namespace roc
214
215#endif // ROC_CORE_SEQLOCK_H_
static void store_relaxed(T1 &var, T2 val)
Atomic store (no barrier).
Definition atomic_ops.h:66
static void fence_seq_cst()
Full memory barrier.
Definition atomic_ops.h:36
static void fence_acquire()
Acquire memory barrier.
Definition atomic_ops.h:26
static T load_relaxed(const T &var)
Atomic load (no barrier).
Definition atomic_ops.h:46
static void fence_release()
Release memory barrier.
Definition atomic_ops.h:31
static bool compare_exchange_relaxed(T1 &var, T1 &exp, T2 des)
Atomic compare-and-swap (no barrier).
Definition atomic_ops.h:117
static T load_seq_cst(const T &var)
Atomic load (full barrier).
Definition atomic_ops.h:56
Base class for non-copyable objects.
Definition noncopyable.h:23
bool try_store(const T &value)
Store value. Can be called concurrently, but only one concurrent call will succeed....
Definition seqlock.h:64
void exclusive_store(const T &value)
Store value. Can NOT be called concurrently, assumes that writes are serialized. Is both lock-free an...
Definition seqlock.h:82
bool try_load_ver(T &value, seqlock_version_t &ver) const
Try to load value and version. Like try_load(), but also returns version.
Definition seqlock.h:105
seqlock_version_t version() const
Load value version. Wait-free.
Definition seqlock.h:53
bool try_store_ver(const T &value, seqlock_version_t &ver)
Store value. Like try_store(), but also returns updated version.
Definition seqlock.h:71
void exclusive_store_ver(const T &value, seqlock_version_t &ver)
Store value. Like exclusive_store(), but also returns updated version.
Definition seqlock.h:89
Seqlock(T value)
Initialize with given value.
Definition seqlock.h:46
void wait_load_ver(T &value, seqlock_version_t &ver) const
Load value and version. Like wait_load(), but also returns version.
Definition seqlock.h:121
T wait_load() const
Load value. May spin until concurrent store completes. Is NOT lock-free (or wait-free).
Definition seqlock.h:112
bool try_load(T &value) const
Try to load value. Returns true if the value was loaded. May return false if concurrent store is curr...
Definition seqlock.h:98
Shared ownership intrusive pointer.
Definition shared_ptr.h:32
CPU-specific instructions.
bool seqlock_version_is_dirty(seqlock_version_t ver)
Check if given seqlock version corresponds to dirty value.
Definition seqlock.h:29
void cpu_relax()
CPU pause instruction.
uint32_t seqlock_version_t
Type for holding seqlock value version. Version is changed each value update. May wrap.
Definition seqlock.h:26
Root namespace.
Non-copyable object.
Commonly used types and functions.