1/* @title: Sequence Lock */
2#pragma once
3#include <atomic.h>
4#include <compiler/atomic.h>
5#include <compiler/core.h>
6#include <enforce.h>
7#include <sch/irql.h>
8#include <stdbool.h>
9#include <stdint.h>
10#include <sync/spinlock.h>
11
12/* The naming here is rather... unpleasant, so it's worth specifying upfront:
13 *
14 * seqcount_ is for all the struct seqcount functions, seq_ and seqlock_
15 * are for the struct seqlock functions, we keep it this way so that
16 * function signatures don't explode in length, and to mirror
17 * the general naming conventions of the lock primitives with lock
18 * in their name (see spinlock.h, rwlock.h)
19 *
20 * (begin_|end_)(read|write)(_raw)(_high)(_retry)
21 *
22 * is the syntax ordering, broadly */
23
24/*
25 * Sequence counters for lock free reader
26 * synchronization with serialized writers
27 *
28 * Odd sequence indicates an in progress write,
29 * even count indicates quiescent data.
30 *
31 * TODO: the thread API and thread.c uses what is effectively
32 * a sequence counter, just not with this API. someday we can change it over
33 */
34struct seqcount {
35 atomic_uint32_t sequence;
36};
37typedef struct seqcount seqcount_t;
38
39#define SEQCOUNT_INIT \
40 (struct seqcount) { \
41 .sequence = ATOMIC_VAR_INIT(0) \
42 }
43
44static inline void seqcount_init(struct seqcount *s) {
45 atomic_store_rlx(&s->sequence, 0);
46}
47
48static inline uint32_t seqcount_read_raw(const struct seqcount *s) {
49 return atomic_load_rlx(&s->sequence);
50}
51
52static inline uint32_t seqcount_begin_read_raw(const struct seqcount *s) {
53 uint32_t ret = seqcount_read_raw(s);
54 ca_rmb();
55 return ret;
56}
57
58/*
59 * Wait for any active writer to complete and return
60 * the sequence with acquire barrier
61 */
62static inline uint32_t seqcount_begin_read(const struct seqcount *s) {
63 while (true) {
64 uint32_t seq = seqcount_read_raw(s);
65 if (cc_likely((seq & 1) == 0)) {
66 ca_rmb();
67 return seq;
68 }
69 cpu_pause();
70 }
71}
72
73/* Check for change since `start` */
74static inline bool seqcount_read_retry(const struct seqcount *s,
75 uint32_t start) {
76 ca_rmb();
77 return cc_unlikely(seqcount_read_raw(s) != start);
78}
79
80/*
81 * NOTE: the separate rlx load and store here is intentional:
82 * atomic_fetch_add is RMW, and unneeded when there is only one writer
83 */
84
85/* even to odd with wmb */
86static inline void seqcount_begin_write(struct seqcount *s) {
87 uint32_t seq = seqcount_read_raw(s);
88 atomic_store_rlx(&s->sequence, seq + 1);
89 ca_wmb();
90}
91
92/* odd to even with wmb */
93static inline void seqcount_end_write(struct seqcount *s) {
94 ca_wmb();
95 uint32_t seq = seqcount_read_raw(s);
96 atomic_store_rlx(&s->sequence, seq + 1);
97}
98
99/*
100 * Sequence Lock (seqlock)
101 *
102 * Combines a sequence counter with a spinlock to serialize writers
103 */
104struct seqlock {
105 struct seqcount seqcount;
106 struct spinlock lock;
107};
108typedef struct seqlock seqlock_t;
109
110static inline void seqlock_init_chk_full(struct seqlock *sl,
111 const struct lock_chk_class *class,
112 enum lock_chk_flags flags) {
113 cc_ignore(class, flags);
114 seqcount_init(s: &sl->seqcount);
115 spinlock_init_chk(&sl->lock, class, flags);
116}
117
118#define SEQLOCK_INIT_CHK(class_, flags_) \
119 (struct seqlock) { \
120 .seqcount = SEQCOUNT_INIT, \
121 .lock = SPINLOCK_INIT_CHK((class_), (flags_)) \
122 }
123
124#define SEQLOCK_INIT SEQLOCK_INIT_CHK(NULL, LOCK_CHKD_FULL)
125#define SEQLOCK_DEFINE(id) struct seqlock id = SEQLOCK_INIT
126#define SEQLOCK_DEFINE_CHK(id, class_, flags_) \
127 struct seqlock id = SEQLOCK_INIT_CHK((class_), (flags_))
128
129#ifdef DEBUG_LOCK_CHK
130
131#define seqlock_init_chk(sl_, class_, flags_) \
132 seqlock_init_chk_full((sl_), (class_), (flags_))
133#define seqlock_init_auto_internal(sl_, flags_) \
134 do { \
135 static const struct lock_chk_class __auto_class = { \
136 .name = #sl_, \
137 .file = __RELFILE__, \
138 .line = __LINE__, \
139 }; \
140 seqlock_init_chk_full((sl_), &__auto_class, (flags_)); \
141 } while (0)
142
143#else /* !defined(DEBUG_LOCK_CHK) */
144
145#define seqlock_init_chk(sl_, class_, flags_) \
146 seqlock_init_chk_full((sl_), NULL, LOCK_UNCHKD)
147#define seqlock_init_auto_internal(sl_, flags_) \
148 seqlock_init_chk_full((sl_), NULL, LOCK_UNCHKD)
149
150#endif /* DEBUG_LOCK_CHK */
151
152#define seqlock_init_1(sl_) seqlock_init_2(sl_, LOCK_CHKD_FULL)
153#define seqlock_init_2(sl_, flags_) seqlock_init_auto_internal((sl_), (flags_))
154#define seqlock_init(...) PP_CALL(seqlock_init, __VA_ARGS__)
155
156static inline uint32_t seq_begin_read(const struct seqlock *sl) {
157 return seqcount_begin_read(s: &sl->seqcount);
158}
159
160static inline bool seq_read_retry(const struct seqlock *sl, uint32_t start) {
161 return seqcount_read_retry(s: &sl->seqcount, start);
162}
163
164static inline uint32_t seq_begin_read_raw(const struct seqlock *sl) {
165 return seqcount_begin_read_raw(s: &sl->seqcount);
166}
167
168static inline uint32_t seq_read_raw(const struct seqlock *sl) {
169 return seqcount_read_raw(s: &sl->seqcount);
170}
171
172static inline cc_warn_unused_result enum irql seq_write_lock(struct seqlock *sl)
173 TSA_ACQUIRES_SPIN(&sl->lock) {
174 enum irql irql = spin_lock(&sl->lock);
175 seqcount_begin_write(s: &sl->seqcount);
176 return irql;
177}
178
179/* Writer APIs */
180static inline cc_warn_unused_result enum irql
181seq_write_lock_high(struct seqlock *sl) TSA_ACQUIRES_SPIN(&sl->lock) {
182 enum irql irql = spin_lock_high(&sl->lock);
183 seqcount_begin_write(s: &sl->seqcount);
184 return irql;
185}
186
187static inline void seq_write_unlock(struct seqlock *sl, enum irql old)
188 TSA_RELEASES_SPIN(&sl->lock) {
189 seqcount_end_write(s: &sl->seqcount);
190 spin_unlock(&sl->lock, old);
191}
192
193/* Raw, no IRQL */
194static inline void seq_write_lock_raw(struct seqlock *sl)
195 TSA_ACQUIRES(&sl->lock) {
196 spin_lock_raw(&sl->lock);
197 seqcount_begin_write(s: &sl->seqcount);
198}
199
200static inline void seq_write_unlock_raw(struct seqlock *sl)
201 TSA_RELEASES(&sl->lock) {
202 seqcount_end_write(s: &sl->seqcount);
203 spin_unlock_raw(&sl->lock);
204}
205
206/* Trylock */
207static inline cc_warn_unused_result bool seq_try_write_lock(struct seqlock *sl,
208 enum irql *out)
209 TSA_TRY_ACQUIRES(true, &sl->lock) {
210 if (spin_trylock(&sl->lock, out)) {
211 seqcount_begin_write(s: &sl->seqcount);
212 return true;
213 }
214 return false;
215}
216
217static inline cc_warn_unused_result bool
218seq_try_write_lock_high(struct seqlock *sl, enum irql *out)
219 TSA_TRY_ACQUIRES(true, &sl->lock) {
220 if (spin_trylock_high(&sl->lock, out)) {
221 seqcount_begin_write(s: &sl->seqcount);
222 return true;
223 }
224 return false;
225}
226
227static inline cc_warn_unused_result bool
228seq_try_write_lock_raw(struct seqlock *sl) TSA_TRY_ACQUIRES(true, &sl->lock) {
229 if (spin_trylock_raw(&sl->lock)) {
230 seqcount_begin_write(s: &sl->seqcount);
231 return true;
232 }
233 return false;
234}
235
236/* Query */
237static inline bool seqlock_is_writing(const struct seqlock *sl) {
238 return (seqcount_read_raw(s: &sl->seqcount) & 1) != 0;
239}
240
241static inline bool seqlock_held(const struct seqlock *sl) {
242 return spinlock_locked(lock: (struct spinlock *) &sl->lock);
243}
244
245#define SEQLOCK_ASSERT_HELD(sl) enforce(seqlock_held(sl))
246
247static inline cc_always_inline
248cc_unused void seqcount_write_guard_exit(struct seqcount **s) {
249 if (*s)
250 seqcount_end_write(s: *s);
251}
252
253static inline cc_always_inline cc_unused struct seqcount *
254seqcount_write_guard_enter(struct seqcount *s) {
255 seqcount_begin_write(s);
256 return s;
257}
258
259struct seqlock_write_guard {
260 struct seqlock *sl;
261 enum irql irql;
262};
263
264struct seqlock_write_raw_guard {
265 struct seqlock *sl;
266};
267
268static inline cc_always_inline cc_unused void
269seqlock_write_guard_assume(struct seqlock *sl)
270 TSA_ASSERT_CAPABILITY(&sl->lock) {
271 cc_ignore(sl);
272}
273
274static inline cc_always_inline cc_unused void seqlock_write_guard_exit(
275 struct seqlock_write_guard *g) TSA_RELEASES_SPIN_IRQL TSA_NO_ANALYSIS {
276 if (g->sl)
277 seq_write_unlock(sl: g->sl, old: g->irql);
278}
279
280static inline cc_always_inline cc_unused struct seqlock_write_guard
281seqlock_write_guard_enter(struct seqlock *sl)
282 TSA_ACQUIRES_SPIN_IRQL TSA_NO_ANALYSIS {
283 return (struct seqlock_write_guard) {
284 .sl = sl,
285 .irql = seq_write_lock(sl),
286 };
287}
288
289static inline cc_always_inline cc_unused struct seqlock_write_guard
290seqlock_write_high_guard_enter(struct seqlock *sl)
291 TSA_ACQUIRES_SPIN_IRQL TSA_NO_ANALYSIS {
292 return (struct seqlock_write_guard) {
293 .sl = sl,
294 .irql = seq_write_lock_high(sl),
295 };
296}
297
298static inline cc_always_inline cc_unused void seqlock_write_raw_guard_exit(
299 struct seqlock_write_raw_guard *g) TSA_NO_ANALYSIS {
300 if (g->sl)
301 seq_write_unlock_raw(sl: g->sl);
302}
303
304static inline cc_always_inline cc_unused struct seqlock_write_raw_guard
305seqlock_write_raw_guard_enter(struct seqlock *sl) TSA_NO_ANALYSIS {
306 seq_write_lock_raw(sl);
307 return (struct seqlock_write_raw_guard) {.sl = sl};
308}
309
310#define seqcount_write_guard(s_) \
311 cc_cleanup(seqcount_write_guard_exit) struct seqcount *PP_CONCAT( \
312 seqc_guard_, __COUNTER__) = seqcount_write_guard_enter(s_)
313
314#define seq_write_guard(sl_) \
315 cc_cleanup(seqlock_write_guard_exit) struct seqlock_write_guard PP_CONCAT( \
316 seq_wguard_, __COUNTER__) = \
317 (seqlock_write_guard_assume(sl_), seqlock_write_guard_enter(sl_))
318
319#define seq_write_guard_high(sl_) \
320 cc_cleanup(seqlock_write_guard_exit) struct seqlock_write_guard PP_CONCAT( \
321 seq_wguard_high_, __COUNTER__) = \
322 (seqlock_write_guard_assume(sl_), seqlock_write_high_guard_enter(sl_))
323
324#define seq_write_guard_raw(sl_) \
325 cc_cleanup(seqlock_write_raw_guard_exit) struct seqlock_write_raw_guard \
326 PP_CONCAT(seq_wguard_raw_, __COUNTER__) = \
327 (seqlock_write_guard_assume(sl_), seqlock_write_raw_guard_enter(sl_))
328