1#include <console/panic.h>
2#include <sch/sched.h>
3#include <sync/turnstile.h>
4#include <thread/thread.h>
5
6#include "lock_general_internal.h"
7#include "rwlock_internal.h"
8
9/* for debugging purposes - upon panic we save data in here */
10static _Atomic(struct rwlock) panic_rwlock;
11static _Atomic(struct rwlock *) panic_rwlock_addr;
12
13static void rwlock_panic(char *msg, struct rwlock *offending_lock) {
14
15 struct rwlock *panic_expected = NULL;
16 if (atomic_compare_exchange_weak_explicit(
17 &panic_rwlock_addr, &panic_expected, offending_lock,
18 memory_order_acquire, memory_order_relaxed))
19 panic_rwlock = *offending_lock;
20
21 uintptr_t v =
22 atomic_load_explicit(&offending_lock->lock_word, memory_order_relaxed);
23 panic("%s, lock = %p, contents = %p, thread = %p", msg, offending_lock, v,
24 thread_get_current());
25}
26
27/* make sure no funny business happened after acquiring a lock */
28static inline bool rwlock_locked_with_type(struct rwlock *lock,
29 enum rwlock_acquire_type type) {
30 uintptr_t word = RWLOCK_READ_LOCK_WORD(lock);
31
32 if (type == RWLOCK_ACQUIRE_WRITE)
33 return RWLOCK_GET_OWNER_FROM_WORD(word) ==
34 (uintptr_t) thread_get_current();
35
36 if (type == RWLOCK_ACQUIRE_READ)
37 return ((word & RWLOCK_READER_COUNT_MASK) &&
38 !(word & RWLOCK_WRITER_HELD_BIT));
39
40 return false;
41}
42
43/* get the mask to mask the lock to determine if we should try and acquire */
44static inline uintptr_t rwlock_get_busy_mask(enum rwlock_acquire_type t) {
45 if (t == RWLOCK_ACQUIRE_READ)
46 return RWLOCK_WRITER_HELD_BIT | RWLOCK_WRITER_WANT_BIT;
47
48 /* we just need the reader here because if there is a writer it will
49 * also set these bits and be detected */
50 return RWLOCK_READER_COUNT_MASK;
51}
52
53static inline uintptr_t rwlock_get_wait_bits(enum rwlock_acquire_type t) {
54 if (t == RWLOCK_ACQUIRE_READ)
55 return RWLOCK_WAITER_BIT;
56
57 return RWLOCK_WAITER_BIT | RWLOCK_WRITER_WANT_BIT;
58}
59
60static inline size_t rwlock_get_wait_queue(enum rwlock_acquire_type t) {
61 if (t == RWLOCK_ACQUIRE_READ)
62 return TURNSTILE_READER_QUEUE;
63
64 return TURNSTILE_WRITER_QUEUE;
65}
66
67size_t rwlock_get_backoff(size_t current_backoff) {
68 if (!current_backoff)
69 return RWLOCK_BACKOFF_DEFAULT;
70
71 if (current_backoff >= (RWLOCK_BACKOFF_MAX >> RWLOCK_BACKOFF_SHIFT))
72 return RWLOCK_BACKOFF_MAX;
73
74 size_t new_backoff = current_backoff << RWLOCK_BACKOFF_SHIFT;
75 return new_backoff > RWLOCK_BACKOFF_MAX ? RWLOCK_BACKOFF_MAX : new_backoff;
76}
77
78void rwlock_init(struct rwlock *lock, enum thread_prio_class class) {
79 lock->lock_word = 0;
80 lock->lock_word |=
81 ((class & RWLOCK_PRIO_CEIL_MASK) << RWLOCK_PRIO_CEIL_SHIFT);
82}
83
84void rwlock_lock(struct rwlock *lock, enum rwlock_acquire_type acq_type) {
85 uintptr_t lword = RWLOCK_READ_LOCK_WORD(lock);
86 kassert(RWLOCK_GET_PRIO_CEIL(lword) &&
87 "rwlock prio ceiling cannot be 0 (background)");
88
89 kassert(acq_type == RWLOCK_ACQUIRE_READ ||
90 acq_type == RWLOCK_ACQUIRE_WRITE);
91 struct thread *curr = thread_get_current();
92
93 /* fastpath */
94 if (rwlock_try_lock(lock, thread: curr, type: acq_type))
95 return;
96
97 uintptr_t old, new;
98
99 /* reset backoff once this equals global.core_count */
100 size_t looped = 0;
101 size_t backoff = RWLOCK_BACKOFF_DEFAULT;
102 size_t queue = rwlock_get_wait_queue(t: acq_type);
103
104 /* what do we mask against to see if the lock is busy? */
105 uintptr_t busy_mask = rwlock_get_busy_mask(t: acq_type);
106
107 /* what bits do we set when we decide to go wait? */
108 uintptr_t wait_bits = rwlock_get_wait_bits(t: acq_type);
109
110 /* if we are reading, we are here because there is a writer.
111 *
112 * if we are writing, we are here because there is a writer or reader.
113 *
114 * regardless, do backoff...
115 *
116 * NOTE: rwlock unlocking performs direct handoff!
117 */
118 while (true) {
119 if (!RWLOCK_BUSY(old = RWLOCK_READ_LOCK_WORD(lock), busy_mask)) {
120 if (rwlock_try_lock(lock, thread: curr, type: acq_type))
121 break;
122
123 backoff = rwlock_get_backoff(current_backoff: backoff);
124 lock_delay(backoff, RWLOCK_BACKOFF_JITTER_PCT);
125 if (++looped == global.core_count) {
126 backoff = RWLOCK_BACKOFF_DEFAULT;
127 looped = 0;
128 }
129 continue;
130 }
131
132 if (RWLOCK_GET_OWNER_FROM_WORD(old) == (uintptr_t) curr)
133 rwlock_panic(msg: "recursive lock", offending_lock: lock);
134
135 enum irql irql_out;
136 struct turnstile *ts = turnstile_lookup(obj: lock, irql_out: &irql_out);
137
138 /* try to set our wait bits, stop if lock becomes available */
139 while (true) {
140 old = RWLOCK_READ_LOCK_WORD(lock);
141
142 if (!RWLOCK_BUSY(old, busy_mask))
143 break;
144
145 new = old | wait_bits;
146
147 if (atomic_compare_exchange_weak_explicit(&lock->lock_word, &old,
148 new, memory_order_acq_rel,
149 memory_order_acquire))
150 break;
151
152 if (!RWLOCK_BUSY(old, busy_mask))
153 break;
154 }
155
156 if (!RWLOCK_BUSY(old, busy_mask)) {
157 turnstile_unlock(obj: lock, irql: irql_out);
158 continue;
159 }
160
161 /* okay we could not get the lock */
162
163 /* make sure we've set the lock bits */
164 kassert(RWLOCK_READ_LOCK_WORD(lock) & wait_bits);
165 kassert(RWLOCK_GET_PRIO_CEIL(lword) &&
166 "rwlock prio ceiling cannot be 0 (background)");
167
168 turnstile_block(ts, queue_num: queue, lock_obj: lock, lock_irql: irql_out, /* owner = */ NULL);
169
170 /* when we wake up, we will have the lock handed off to us... */
171 break;
172 }
173
174 /* make sure nothing funny happened */
175 kassert(rwlock_locked_with_type(lock, acq_type));
176 thread_boost_self(RWLOCK_GET_PRIO_CEIL(lword));
177}
178
179/* return the number of readers we want to wake,
180 * or zero if we should wake a writer */
181
182/* only to be called from exiting writers
183 *
184 * grant the lock to readers with the same or higher priority than the highest
185 * priority writer...
186 */
187size_t rwlock_get_readers_to_wake(struct turnstile *ts) {
188 struct rbt_node *wnode, *rnode, *iter;
189 struct thread *writer = NULL;
190
191 wnode = rbt_last(root: &ts->queues[TURNSTILE_WRITER_QUEUE]);
192 rnode = rbt_last(root: &ts->queues[TURNSTILE_READER_QUEUE]);
193
194 /* verify that somebody is on the queues */
195 kassert(wnode || rnode);
196
197 if (wnode)
198 writer = thread_from_wq_rbt_node(wnode);
199
200 /* for each reader that beats this priority,
201 * increment the count of readers to wake */
202 int32_t prio_to_beat = writer ? turnstile_thread_priority(t: writer) : -1;
203 size_t to_wake = 0;
204
205 rbt_for_each_reverse(iter, &ts->queues[TURNSTILE_READER_QUEUE]) {
206 struct thread *check_reader = thread_from_wq_rbt_node(iter);
207
208 /* can no longer beat the thread priority of the writer */
209 int32_t prio = turnstile_thread_priority(t: check_reader);
210
211 if (prio < prio_to_beat)
212 break;
213
214 to_wake++;
215 }
216
217 return to_wake;
218}
219
220static uintptr_t rwlock_unlock_get_val_to_sub(struct rwlock *lock) {
221 struct thread *current_thread = thread_get_current();
222 uintptr_t lock_word = RWLOCK_READ_LOCK_WORD(lock);
223 if (lock_word & RWLOCK_WRITER_HELD_BIT) {
224 if (RWLOCK_GET_OWNER_FROM_WORD(lock_word) !=
225 (uintptr_t) current_thread) {
226 rwlock_panic(msg: "non-owner thread unlocked as exclusive waiter", offending_lock: lock);
227 }
228
229 return ((uintptr_t) current_thread) | RWLOCK_WRITER_HELD_BIT;
230 } else {
231 if ((lock_word & RWLOCK_READER_COUNT_MASK) == 0)
232 rwlock_panic(msg: "reader unlocked with no readers left on lock", offending_lock: lock);
233
234 return RWLOCK_READER_COUNT_ONE;
235 }
236}
237
238void rwlock_unlock(struct rwlock *lock) {
239 /* once again, we raise the IRQL to DISPATCH to prevent
240 * us from being switched out while we unlock */
241 size_t backoff = RWLOCK_BACKOFF_DEFAULT;
242 size_t looped = 0;
243
244 /* we can cheekily use this to figure out what to "subtract from the
245 * lock" to determine what the lock word should be on unlock CAS */
246 uintptr_t val_to_subtract = rwlock_unlock_get_val_to_sub(lock);
247
248 while (true) {
249 uintptr_t old = RWLOCK_READ_LOCK_WORD(lock);
250 uintptr_t new = old - val_to_subtract;
251
252 /* there are still readers left and there are still waiters, this
253 * is not the final exit of a lock, so we just drop the lock */
254 if ((new & (RWLOCK_READER_COUNT_MASK | RWLOCK_WAITER_BIT)) !=
255 RWLOCK_WAITER_BIT) {
256 /* successful swap, we're all good */
257 if (atomic_compare_exchange_weak_explicit(&lock->lock_word, &old,
258 new, memory_order_release,
259 memory_order_relaxed))
260 break;
261
262 /* unsuccessful... try again */
263 backoff = rwlock_get_backoff(current_backoff: backoff);
264 lock_delay(backoff, RWLOCK_BACKOFF_JITTER_PCT);
265
266 /* reset if we have reached the # of CPUs */
267 if (++looped == global.core_count) {
268 looped = 0;
269 backoff = RWLOCK_BACKOFF_DEFAULT;
270 }
271
272 continue;
273 }
274
275 /* we are the last reader of a lock with waiters */
276 enum irql irql_out;
277 struct turnstile *ts = turnstile_lookup(obj: lock, irql_out: &irql_out);
278
279 struct rbt_node *wnode = rbt_last(root: &ts->queues[TURNSTILE_WRITER_QUEUE]);
280
281 struct thread *writer = wnode ? thread_from_wq_rbt_node(wnode) : NULL;
282 size_t to_wake = rwlock_get_readers_to_wake(ts);
283
284 if (writer && to_wake == 0) {
285 /* directly transfer ownership to the very next writer */
286 new = rwlock_make_write_word(lock, thread: writer);
287
288 if (ts->waiters > 1)
289 new |= RWLOCK_WAITER_BIT;
290
291 if (rbt_prev(node: wnode))
292 new |= RWLOCK_WRITER_WANT_BIT;
293
294 RWLOCK_WRITE_LOCK_WORD(lock, new);
295 turnstile_wake(ts, TURNSTILE_WRITER_QUEUE, num_threads: 1, lock_irql: irql_out);
296 } else {
297 /* give the lock to all waiters at once */
298 new = to_wake * RWLOCK_READER_COUNT_ONE;
299
300 if (ts->waiters > to_wake)
301 new |= RWLOCK_WAITER_BIT;
302
303 if (writer)
304 new |= RWLOCK_WRITER_WANT_BIT;
305
306 new |= (RWLOCK_READ_LOCK_WORD(lock) & RWLOCK_PRIO_CEIL_MASK);
307
308 RWLOCK_WRITE_LOCK_WORD(lock, new);
309 turnstile_wake(ts, TURNSTILE_READER_QUEUE, num_threads: to_wake, lock_irql: irql_out);
310 }
311
312 /* all done */
313 break;
314 }
315
316 thread_unboost_self();
317}
318
319bool rwlock_held(struct rwlock *lock, enum rwlock_acquire_type type) {
320 return rwlock_locked_with_type(lock, type);
321}
322