1/* @title: Sequence Lock */
2#pragma once
3#include <compiler.h>
4#include <kassert.h>
5#include <sch/irql.h>
6#include <stdatomic.h>
7#include <stdbool.h>
8#include <stdint.h>
9#include <sync/spinlock.h>
10
11/* The naming here is rather... unpleasant, so it's worth specifying upfront:
12 *
13 * seqcount_ is for all the struct seqcount functions, seq_ and seqlock_
14 * are for the struct seqlock functions, we keep it this way so that
15 * function signatures don't explode in length, and to mirror
16 * the general naming conventions of the lock primitives with lock
17 * in their name (see spinlock.h, rwlock.h)
18 *
19 * (begin_|end_)(read|write)(_raw)(_irq_disable)(_retry)
20 *
21 * is the syntax ordering, broadly */
22
23/*
24 * Sequence counters for lock free reader
25 * synchronization with serialized writers
26 *
27 * Odd sequence indicates an in progress write,
28 * even count indicates quiescent data.
29 *
30 * TODO: the thread API and thread.c uses what is effectively
31 * a sequence counter, just not with this API. someday we can change it over
32 */
33struct seqcount {
34 _Atomic uint32_t sequence;
35};
36typedef struct seqcount seqcount_t;
37
38#define SEQCOUNT_INIT \
39 (struct seqcount) { \
40 .sequence = ATOMIC_VAR_INIT(0) \
41 }
42
43static inline void seqcount_init(struct seqcount *s) {
44 atomic_store_explicit(&s->sequence, 0, memory_order_relaxed);
45}
46
47static inline uint32_t seqcount_read_raw(const struct seqcount *s) {
48 return atomic_load_explicit(&s->sequence, memory_order_relaxed);
49}
50
51static inline uint32_t seqcount_begin_read_raw(const struct seqcount *s) {
52 uint32_t ret = seqcount_read_raw(s);
53 smp_rmb();
54 return ret;
55}
56
57/*
58 * Wait for any active writer to complete and return
59 * the sequence with acquire barrier
60 */
61static inline uint32_t seqcount_begin_read(const struct seqcount *s) {
62 while (true) {
63 uint32_t seq = seqcount_read_raw(s);
64 if (likely((seq & 1) == 0)) {
65 smp_rmb();
66 return seq;
67 }
68 cpu_relax();
69 }
70}
71
72/* Check for change since `start` */
73static inline bool seqcount_read_retry(const struct seqcount *s,
74 uint32_t start) {
75 smp_rmb();
76 return unlikely(seqcount_read_raw(s) != start);
77}
78
79/*
80 * NOTE: the separate relaxed load and store here is intentional:
81 * atomic_fetch_add is RMW, and unneeded when there is only one writer
82 */
83
84/* even to odd with wmb */
85static inline void seqcount_begin_write(struct seqcount *s) {
86 uint32_t seq = seqcount_read_raw(s);
87 atomic_store_explicit(&s->sequence, seq + 1, memory_order_relaxed);
88 smp_wmb();
89}
90
91/* odd to even with wmb */
92static inline void seqcount_end_write(struct seqcount *s) {
93 smp_wmb();
94 uint32_t seq = seqcount_read_raw(s);
95 atomic_store_explicit(&s->sequence, seq + 1, memory_order_relaxed);
96}
97
98/*
99 * Sequence Lock (seqlock)
100 *
101 * Combines a sequence counter with a spinlock to serialize writers
102 */
103struct seqlock {
104 struct seqcount seqcount;
105 struct spinlock lock;
106};
107typedef struct seqlock seqlock_t;
108
109static inline void seqlock_init_chk_internal(struct seqlock *sl,
110 const struct lock_chk_class *class,
111 enum lock_chk_flags flags) {
112 seqcount_init(s: &sl->seqcount);
113 spinlock_init_chk(&sl->lock, class, flags);
114}
115
116#define SEQLOCK_INIT_CHK(class_, flags_) \
117 (struct seqlock) { \
118 .seqcount = SEQCOUNT_INIT, \
119 .lock = SPINLOCK_INIT_CHK((class_), (flags_)) \
120 }
121
122#define SEQLOCK_INIT SEQLOCK_INIT_CHK(NULL, LOCK_CHKD_FULL)
123#define SEQLOCK_DEFINE(id) struct seqlock id = SEQLOCK_INIT
124#define SEQLOCK_DEFINE_CHK(id, class_, flags_) \
125 struct seqlock id = SEQLOCK_INIT_CHK((class_), (flags_))
126
127#ifdef DEBUG_LOCK_CHK
128
129#define seqlock_init_chk(sl_, class_, flags_) \
130 seqlock_init_chk_internal((sl_), (class_), (flags_))
131#define seqlock_init_auto_internal(sl_, flags_) \
132 do { \
133 static const struct lock_chk_class __auto_class = { \
134 .name = #sl_, \
135 .file = __RELFILE__, \
136 .line = __LINE__, \
137 }; \
138 seqlock_init_chk_internal((sl_), &__auto_class, (flags_)); \
139 } while (0)
140
141#else /* !defined(DEBUG_LOCK_CHK) */
142
143#define seqlock_init_chk(sl_, class_, flags_) \
144 seqlock_init_chk_internal((sl_), NULL, LOCK_UNCHKD)
145#define seqlock_init_auto_internal(sl_, flags_) \
146 seqlock_init_chk_internal((sl_), NULL, LOCK_UNCHKD)
147
148#endif /* DEBUG_LOCK_CHK */
149
150#define seqlock_init_1(sl_) seqlock_init_auto_internal((sl_), LOCK_CHKD_FULL)
151#define seqlock_init_2(sl_, flags_) seqlock_init_auto_internal((sl_), (flags_))
152#define seqlock_init(...) \
153 _DISPATCH(seqlock_init, PP_NARG(__VA_ARGS__))(__VA_ARGS__)
154
155static inline uint32_t seq_begin_read(const struct seqlock *sl) {
156 return seqcount_begin_read(s: &sl->seqcount);
157}
158
159static inline bool seq_read_retry(const struct seqlock *sl, uint32_t start) {
160 return seqcount_read_retry(s: &sl->seqcount, start);
161}
162
163static inline uint32_t seq_begin_read_raw(const struct seqlock *sl) {
164 return seqcount_begin_read_raw(s: &sl->seqcount);
165}
166
167static inline uint32_t seq_read_raw(const struct seqlock *sl) {
168 return seqcount_read_raw(s: &sl->seqcount);
169}
170
171static inline enum irql __warn_unused_result
172seq_write_lock(struct seqlock *sl) {
173 enum irql irql = spin_lock(&sl->lock);
174 seqcount_begin_write(s: &sl->seqcount);
175 return irql;
176}
177
178/* Writer APIs */
179static inline enum irql __warn_unused_result
180seq_write_lock_irq_disable(struct seqlock *sl) {
181 enum irql irql = spin_lock_irq_disable(&sl->lock);
182 seqcount_begin_write(s: &sl->seqcount);
183 return irql;
184}
185
186static inline void seq_write_unlock(struct seqlock *sl, enum irql old) {
187 seqcount_end_write(s: &sl->seqcount);
188 spin_unlock(&sl->lock, old);
189}
190
191/* Raw, no IRQL */
192static inline void seq_write_lock_raw(struct seqlock *sl) {
193 spin_lock_raw(&sl->lock);
194 seqcount_begin_write(s: &sl->seqcount);
195}
196
197static inline void seq_write_unlock_raw(struct seqlock *sl) {
198 seqcount_end_write(s: &sl->seqcount);
199 spin_unlock_raw(&sl->lock);
200}
201
202/* Trylock */
203static inline bool __warn_unused_result seq_try_write_lock(struct seqlock *sl,
204 enum irql *out) {
205 if (spin_trylock(&sl->lock, out)) {
206 seqcount_begin_write(s: &sl->seqcount);
207 return true;
208 }
209 return false;
210}
211
212static inline bool __warn_unused_result
213seq_try_write_lock_irq_disable(struct seqlock *sl, enum irql *out) {
214 if (spin_trylock_irq_disable(&sl->lock, out)) {
215 seqcount_begin_write(s: &sl->seqcount);
216 return true;
217 }
218 return false;
219}
220
221static inline bool __warn_unused_result
222seq_try_write_lock_raw(struct seqlock *sl) {
223 if (spin_trylock_raw(&sl->lock)) {
224 seqcount_begin_write(s: &sl->seqcount);
225 return true;
226 }
227 return false;
228}
229
230/* Query */
231static inline bool seqlock_is_writing(const struct seqlock *sl) {
232 return (seqcount_read_raw(s: &sl->seqcount) & 1) != 0;
233}
234
235static inline bool seqlock_held(const struct seqlock *sl) {
236 return spinlock_locked(lock: (struct spinlock *) &sl->lock);
237}
238
239#define SEQLOCK_ASSERT_HELD(sl) kassert(seqlock_held(sl))
240