1#include <console/panic.h>
2#include <sch/sched.h>
3#include <sync/rcu.h>
4#include <sync/turnstile.h>
5#include <thread/thread.h>
6
7#include "lock_general_internal.h"
8#include "rwlock_internal.h"
9
10#ifdef DEBUG_LOCK_CHK
11#include "lock_chk_internal.h"
12#endif /* DEBUG_LOCK_CHK */
13
14/* for debugging purposes - upon panic we save data in here */
15static struct rwlock panic_rwlock;
16static _Atomic(struct rwlock *) panic_rwlock_addr;
17
18static void rwlock_panic(char *msg, struct rwlock *offending_lock) {
19
20 struct rwlock *panic_expected = NULL;
21 if (atomic_compare_exchange_weak_explicit(
22 &panic_rwlock_addr, &panic_expected, offending_lock,
23 memory_order_acquire, memory_order_relaxed))
24 panic_rwlock = *offending_lock;
25
26 if (offending_lock)
27 panic_rwlock = *offending_lock;
28
29 uintptr_t v =
30 atomic_load_explicit(&offending_lock->lock_word, memory_order_relaxed);
31 panic("%s, lock = %p, contents = %p, thread = %p", msg, offending_lock, v,
32 thread_get_current());
33}
34
35/* make sure no funny business happened after acquiring a lock */
36static inline bool rwlock_locked_with_type(struct rwlock *lock,
37 enum rwlock_acquire_type type) {
38 uintptr_t word = RWLOCK_READ_LOCK_WORD(lock);
39
40 if (type == RWLOCK_ACQUIRE_WRITE)
41 return RWLOCK_GET_OWNER_FROM_WORD(word) ==
42 (uintptr_t) thread_get_current();
43
44 if (type == RWLOCK_ACQUIRE_READ)
45 return ((word & RWLOCK_READER_COUNT_MASK) &&
46 !(word & RWLOCK_WRITER_HELD_BIT));
47
48 return false;
49}
50
51static struct thread *rwlock_get_owner_ref(struct rwlock *lock) {
52 struct thread *owner;
53
54 rcu_read_lock();
55 uintptr_t word = RWLOCK_READ_LOCK_WORD(lock);
56 owner = (word & RWLOCK_WRITER_HELD_BIT)
57 ? (struct thread *) RWLOCK_GET_OWNER_FROM_WORD(word)
58 : NULL;
59 if (owner && !thread_get_rcu(t: owner))
60 owner = NULL;
61 rcu_read_unlock();
62
63 return owner;
64}
65
66/* get the mask to mask the lock to determine if we should try and acquire */
67static inline uintptr_t rwlock_get_busy_mask(enum rwlock_acquire_type t) {
68 if (t == RWLOCK_ACQUIRE_READ)
69 return RWLOCK_WRITER_HELD_BIT | RWLOCK_WRITER_WANT_BIT;
70
71 /* we just need the reader here because if there is a writer it will
72 * also set these bits and be detected */
73 return RWLOCK_READER_COUNT_MASK;
74}
75
76static inline uintptr_t rwlock_get_wait_bits(enum rwlock_acquire_type t) {
77 if (t == RWLOCK_ACQUIRE_READ)
78 return RWLOCK_WAITER_BIT;
79
80 return RWLOCK_WAITER_BIT | RWLOCK_WRITER_WANT_BIT;
81}
82
83static inline size_t rwlock_get_wait_queue(enum rwlock_acquire_type t) {
84 if (t == RWLOCK_ACQUIRE_READ)
85 return TURNSTILE_READER_QUEUE;
86
87 return TURNSTILE_WRITER_QUEUE;
88}
89
90size_t rwlock_get_backoff(size_t current_backoff) {
91 if (!current_backoff)
92 return RWLOCK_BACKOFF_DEFAULT;
93
94 if (current_backoff >= (RWLOCK_BACKOFF_MAX >> RWLOCK_BACKOFF_SHIFT))
95 return RWLOCK_BACKOFF_MAX;
96
97 size_t new_backoff = current_backoff << RWLOCK_BACKOFF_SHIFT;
98 return new_backoff > RWLOCK_BACKOFF_MAX ? RWLOCK_BACKOFF_MAX : new_backoff;
99}
100
101#ifdef DEBUG_LOCK_CHK
102
103static void rwlock_chk_state_init(struct rwlock *lock,
104 const struct lock_chk_class *class,
105 enum lock_chk_flags flags) {
106 kassert((flags & ~LOCK_CHKD_FULL) == 0);
107 kassert(flags == LOCK_UNCHKD || class != NULL);
108 lock->chk.flags = flags;
109 lock->chk.initialized = true;
110 atomic_store_explicit(&lock->chk.used, false, memory_order_relaxed);
111 lock_chk_map_runtime_init(&lock->chk.map, class);
112}
113
114static bool rwlock_idle_for_reconfiguration(struct rwlock *lock) {
115 uintptr_t word = RWLOCK_READ_LOCK_WORD(lock);
116 uintptr_t active = RWLOCK_WRITER_HELD_BIT | RWLOCK_WAITER_BIT |
117 RWLOCK_WRITER_WANT_BIT | RWLOCK_READER_COUNT_MASK;
118 return (word & active) == 0;
119}
120
121void rwlock_set_chk_flags(struct rwlock *lock, enum lock_chk_flags flags) {
122 kassert(lock->chk.initialized);
123 kassert(rwlock_idle_for_reconfiguration(lock));
124 kassert(!atomic_load_explicit(&lock->chk.used, memory_order_relaxed));
125 kassert((flags & ~LOCK_CHKD_FULL) == 0);
126 lock->chk.flags = flags;
127}
128
129void rwlock_reinit_chk(struct rwlock *lock, enum thread_prio_class ceiling,
130 const struct lock_chk_class *class,
131 enum lock_chk_flags flags) {
132 kassert(lock->chk.initialized);
133 kassert(rwlock_idle_for_reconfiguration(lock));
134 rwlock_init_chk_internal(lock, ceiling, class, flags);
135}
136
137#else /* !defined(DEBUG_LOCK_CHK) */
138
139static void rwlock_chk_state_init(struct rwlock *lock,
140 const struct lock_chk_class *class,
141 enum lock_chk_flags flags) {
142 unused(lock, class, flags);
143}
144
145void rwlock_set_chk_flags(struct rwlock *lock, enum lock_chk_flags flags) {
146 unused(lock, flags);
147}
148
149void rwlock_reinit_chk(struct rwlock *lock, enum thread_prio_class ceiling,
150 const struct lock_chk_class *class,
151 enum lock_chk_flags flags) {
152 rwlock_init_chk_internal(lock, ceiling, class, flags);
153}
154
155#endif /* DEBUG_LOCK_CHK */
156
157void rwlock_init_chk_internal(struct rwlock *lock,
158 enum thread_prio_class ceiling,
159 const struct lock_chk_class *class,
160 enum lock_chk_flags flags) {
161 atomic_store_explicit(&lock->lock_word,
162 ((uintptr_t) ceiling << RWLOCK_PRIO_CEIL_SHIFT) &
163 RWLOCK_PRIO_CEIL_MASK,
164 memory_order_relaxed);
165 rwlock_chk_state_init(lock, class, flags);
166}
167
168void rw_lock_internal(struct rwlock *lock, enum rwlock_acquire_type acq_type,
169 uint8_t subclass, const struct lock_chk_site *site) {
170 kassert(subclass < LOCK_CHK_MAX_SUBCLASSES);
171 kassert(acq_type == RWLOCK_ACQUIRE_READ ||
172 acq_type == RWLOCK_ACQUIRE_WRITE);
173
174 kassert(irq_not_in_interrupt());
175 kassert(irql_get() <= IRQL_APC_LEVEL);
176
177#ifdef DEBUG_LOCK_CHK
178 enum lock_chk_mode chk_mode = acq_type == RWLOCK_ACQUIRE_READ
179 ? LOCK_CHK_MODE_SHARED
180 : LOCK_CHK_MODE_EXCLUSIVE;
181 struct lock_chk_acquire_request req;
182 struct lock_chk_acquire_token token;
183 lock_chk_note_lock_use(&lock->chk, /*manages_irql=*/false,
184 /*raw_operation=*/false);
185 bool checked_deep = lock->chk.flags != LOCK_UNCHKD;
186 if (checked_deep) {
187 lock->chk.instance = lock;
188 lock->chk.type = LOCK_CHK_TYPE_RWLOCK;
189 req = lock_chk_acquire_request_make(&lock->chk, site, chk_mode,
190 LOCK_CHK_WAIT_BLOCKING, subclass,
191 false, false);
192 lock_chk_before_acquire(&token, &req);
193 }
194#endif
195
196 uintptr_t lword = RWLOCK_READ_LOCK_WORD(lock);
197 kassert(RWLOCK_GET_PRIO_CEIL(lword) != 0 &&
198 "rwlock prio ceiling cannot be 0 (background)");
199
200 struct thread *curr = thread_get_current();
201
202 /* fastpath */
203 if (rwlock_try_lock(lock, thread: curr, type: acq_type)) {
204 thread_boost_self(RWLOCK_GET_PRIO_CEIL(lword));
205#ifdef DEBUG_LOCK_CHK
206 if (checked_deep)
207 lock_chk_acquired(&token);
208#endif
209 crash_unwind_enter_rwlock(r: lock);
210 return;
211 }
212
213 uintptr_t old, new;
214
215 /* reset backoff once this equals global.core_count */
216 size_t looped = 0;
217 size_t backoff = RWLOCK_BACKOFF_DEFAULT;
218 size_t queue = rwlock_get_wait_queue(t: acq_type);
219
220 /* what do we mask against to see if the lock is busy? */
221 uintptr_t busy_mask = rwlock_get_busy_mask(t: acq_type);
222
223 /* what bits do we set when we decide to go wait? */
224 uintptr_t wait_bits = rwlock_get_wait_bits(t: acq_type);
225
226 /* if we are reading, we are here because there is a writer.
227 *
228 * if we are writing, we are here because there is a writer or reader.
229 *
230 * regardless, do backoff...
231 *
232 * NOTE: rwlock unlocking performs direct handoff!
233 */
234 while (true) {
235 if (!RWLOCK_BUSY(old = RWLOCK_READ_LOCK_WORD(lock), busy_mask)) {
236 if (rwlock_try_lock(lock, thread: curr, type: acq_type))
237 break;
238
239 backoff = rwlock_get_backoff(current_backoff: backoff);
240 lock_delay(backoff, RWLOCK_BACKOFF_JITTER_PCT);
241 if (++looped == global.core_count) {
242 backoff = RWLOCK_BACKOFF_DEFAULT;
243 looped = 0;
244 }
245 continue;
246 }
247
248 if (RWLOCK_GET_OWNER_FROM_WORD(old) == (uintptr_t) curr)
249 rwlock_panic(msg: "recursive lock", offending_lock: lock);
250
251 enum irql irql_out;
252 struct turnstile *ts = turnstile_lookup(obj: lock, irql_out: &irql_out);
253
254 /* try to set our wait bits, stop if lock becomes available */
255 while (true) {
256 old = RWLOCK_READ_LOCK_WORD(lock);
257
258 if (!RWLOCK_BUSY(old, busy_mask))
259 break;
260
261 new = old | wait_bits;
262
263 if (atomic_compare_exchange_weak_explicit(&lock->lock_word, &old,
264 new, memory_order_acq_rel,
265 memory_order_acquire))
266 break;
267
268 if (!RWLOCK_BUSY(old, busy_mask))
269 break;
270 }
271
272 if (!RWLOCK_BUSY(old, busy_mask)) {
273 turnstile_unlock(obj: lock, irql: irql_out);
274 continue;
275 }
276
277 /* okay we could not get the lock */
278
279 /* make sure we've set the lock bits */
280 kassert(RWLOCK_READ_LOCK_WORD(lock) & wait_bits);
281 kassert(RWLOCK_GET_PRIO_CEIL(lword) &&
282 "rwlock prio ceiling cannot be 0 (background)");
283
284 struct thread *owner = rwlock_get_owner_ref(lock);
285 if (owner) {
286 /* Same idea as mutex.c */
287 thread_put(t: owner);
288 }
289 turnstile_block(ts, queue_num: queue, lock_obj: lock, lock_irql: irql_out, owner);
290
291 /* when we wake up, we will have the lock handed off to us... */
292 break;
293 }
294
295 /* make sure nothing funny happened */
296 kassert(rwlock_locked_with_type(lock, acq_type));
297 thread_boost_self(RWLOCK_GET_PRIO_CEIL(lword));
298
299#ifdef DEBUG_LOCK_CHK
300 if (checked_deep)
301 lock_chk_acquired(&token);
302#endif
303 crash_unwind_enter_rwlock(r: lock);
304}
305
306/* return the number of readers we want to wake,
307 * or zero if we should wake a writer */
308
309/* only to be called from exiting writers
310 *
311 * grant the lock to readers with the same or higher priority than the highest
312 * priority writer...
313 */
314size_t rwlock_get_readers_to_wake(struct turnstile *ts) {
315 struct rbt_node *wnode, *rnode, *iter;
316 struct thread *writer = NULL;
317
318 wnode = rbt_last(root: &ts->queues[TURNSTILE_WRITER_QUEUE]);
319 rnode = rbt_last(root: &ts->queues[TURNSTILE_READER_QUEUE]);
320
321 /* verify that somebody is on the queues */
322 kassert(wnode || rnode);
323
324 if (wnode)
325 writer = thread_from_wq_rbt_node(wnode);
326
327 /* for each reader that beats this priority,
328 * increment the count of readers to wake */
329 int32_t prio_to_beat = writer ? turnstile_thread_priority(t: writer) : -1;
330 size_t to_wake = 0;
331
332 rbt_for_each_reverse(iter, &ts->queues[TURNSTILE_READER_QUEUE]) {
333 struct thread *check_reader = thread_from_wq_rbt_node(iter);
334
335 /* can no longer beat the thread priority of the writer */
336 int32_t prio = turnstile_thread_priority(t: check_reader);
337
338 if (prio < prio_to_beat)
339 break;
340
341 to_wake++;
342 }
343
344 return to_wake;
345}
346
347static uintptr_t rwlock_unlock_get_val_to_sub(struct rwlock *lock) {
348 struct thread *current_thread = thread_get_current();
349 uintptr_t lock_word = RWLOCK_READ_LOCK_WORD(lock);
350 if (lock_word & RWLOCK_WRITER_HELD_BIT) {
351 if (RWLOCK_GET_OWNER_FROM_WORD(lock_word) !=
352 (uintptr_t) current_thread) {
353 rwlock_panic(msg: "non-owner thread unlocked as exclusive waiter", offending_lock: lock);
354 }
355
356 return ((uintptr_t) current_thread) | RWLOCK_WRITER_HELD_BIT;
357 } else {
358 if ((lock_word & RWLOCK_READER_COUNT_MASK) == 0)
359 rwlock_panic(msg: "reader unlocked with no readers left on lock", offending_lock: lock);
360
361 return RWLOCK_READER_COUNT_ONE;
362 }
363}
364
365void rw_unlock_internal(struct rwlock *lock, const struct lock_chk_site *site) {
366 kassert(irq_not_in_interrupt());
367 kassert(irql_get() <= IRQL_APC_LEVEL);
368
369#ifdef DEBUG_LOCK_CHK
370 uintptr_t lock_word = RWLOCK_READ_LOCK_WORD(lock);
371 bool is_writer = (lock_word & RWLOCK_WRITER_HELD_BIT) != 0;
372 enum lock_chk_mode chk_mode =
373 is_writer ? LOCK_CHK_MODE_EXCLUSIVE : LOCK_CHK_MODE_SHARED;
374 struct lock_chk_release_request req;
375 struct lock_chk_release_token token;
376 bool checked_deep = lock->chk.flags != LOCK_UNCHKD;
377 if (checked_deep) {
378 lock->chk.instance = lock;
379 lock->chk.type = LOCK_CHK_TYPE_RWLOCK;
380 req = lock_chk_release_request_make(&lock->chk, site, chk_mode);
381 lock_chk_before_release(&token, &req);
382 }
383#endif
384
385 /* once again, we raise the IRQL to DISPATCH to prevent
386 * us from being switched out while we unlock */
387 size_t backoff = RWLOCK_BACKOFF_DEFAULT;
388 size_t looped = 0;
389
390 /* we can cheekily use this to figure out what to "subtract from the
391 * lock" to determine what the lock word should be on unlock CAS */
392 uintptr_t val_to_subtract = rwlock_unlock_get_val_to_sub(lock);
393
394 while (true) {
395 uintptr_t old = RWLOCK_READ_LOCK_WORD(lock);
396 uintptr_t new = old - val_to_subtract;
397
398 /* there are still readers left and there are still waiters, this
399 * is not the final exit of a lock, so we just drop the lock */
400 if ((new & (RWLOCK_READER_COUNT_MASK | RWLOCK_WAITER_BIT)) !=
401 RWLOCK_WAITER_BIT) {
402 /* successful swap, we're all good */
403 if (atomic_compare_exchange_weak_explicit(&lock->lock_word, &old,
404 new, memory_order_release,
405 memory_order_relaxed))
406 break;
407
408 /* unsuccessful... try again */
409 backoff = rwlock_get_backoff(current_backoff: backoff);
410 lock_delay(backoff, RWLOCK_BACKOFF_JITTER_PCT);
411
412 /* reset if we have reached the # of CPUs */
413 if (++looped == global.core_count) {
414 looped = 0;
415 backoff = RWLOCK_BACKOFF_DEFAULT;
416 }
417
418 continue;
419 }
420
421 /* we are the last reader of a lock with waiters */
422 enum irql irql_out;
423 struct turnstile *ts = turnstile_lookup(obj: lock, irql_out: &irql_out);
424
425 struct rbt_node *wnode = rbt_last(root: &ts->queues[TURNSTILE_WRITER_QUEUE]);
426
427 struct thread *writer = wnode ? thread_from_wq_rbt_node(wnode) : NULL;
428 size_t to_wake = rwlock_get_readers_to_wake(ts);
429
430 if (writer && to_wake == 0) {
431 /* directly transfer ownership to the very next writer */
432 new = rwlock_make_write_word(lock, thread: writer);
433
434 if (ts->waiters > 1)
435 new |= RWLOCK_WAITER_BIT;
436
437 if (rbt_prev(node: wnode))
438 new |= RWLOCK_WRITER_WANT_BIT;
439
440 RWLOCK_WRITE_LOCK_WORD(lock, new);
441 turnstile_wake(ts, TURNSTILE_WRITER_QUEUE, num_threads: 1, lock_irql: irql_out);
442 } else {
443 /* give the lock to all waiters at once */
444 new = to_wake * RWLOCK_READER_COUNT_ONE;
445
446 if (ts->waiters > to_wake)
447 new |= RWLOCK_WAITER_BIT;
448
449 if (writer)
450 new |= RWLOCK_WRITER_WANT_BIT;
451
452 new |= (RWLOCK_READ_LOCK_WORD(lock) & RWLOCK_PRIO_CEIL_MASK);
453
454 RWLOCK_WRITE_LOCK_WORD(lock, new);
455 turnstile_wake(ts, TURNSTILE_READER_QUEUE, num_threads: to_wake, lock_irql: irql_out);
456 }
457
458 /* all done */
459 break;
460 }
461
462#ifdef DEBUG_LOCK_CHK
463 if (checked_deep)
464 lock_chk_released(&token);
465#endif /* DEBUG_LOCK_CHK */
466 crash_unwind_exit_rwlock(r: lock);
467
468 thread_unboost_self();
469}
470
471bool rwlock_locked(struct rwlock *lock, enum rwlock_acquire_type type) {
472 return rwlock_locked_with_type(lock, type);
473}
474
475void rwlock_assert_held_internal(struct rwlock *lock,
476 enum rwlock_acquire_type type,
477 const struct lock_chk_site *site) {
478#ifdef DEBUG_LOCK_CHK
479 lock->chk.instance = lock;
480 lock->chk.type = LOCK_CHK_TYPE_RWLOCK;
481 enum lock_chk_mode chk_mode = type == RWLOCK_ACQUIRE_READ
482 ? LOCK_CHK_MODE_SHARED
483 : LOCK_CHK_MODE_EXCLUSIVE;
484 if (lock->chk.flags != LOCK_UNCHKD &&
485 lock_chk_assert_held_deep(&lock->chk, chk_mode, /*want_held=*/true,
486 site))
487 return;
488#else
489 unused(site);
490#endif
491 kassert(rwlock_locked(lock, type), "rwlock not held");
492}
493
494void rwlock_assert_not_held_internal(struct rwlock *lock,
495 const struct lock_chk_site *site) {
496#ifdef DEBUG_LOCK_CHK
497 lock->chk.instance = lock;
498 lock->chk.type = LOCK_CHK_TYPE_RWLOCK;
499 if (lock->chk.flags != LOCK_UNCHKD &&
500 lock_chk_assert_held_deep(&lock->chk, LOCK_CHK_MODE_IGNORED,
501 /*want_held=*/false, site))
502 return;
503#else
504 unused(site);
505#endif
506 /* Raw fallback can only check write mode ownership, which is
507 * a small caveat of the system here, as reads can be
508 * any reader, not necessarily "this reader".
509 *
510 * Not reporting anything at all here is better than
511 * a false positive, since it keeps the checker
512 * honest instead of spreading misinformation */
513 kassert(!rwlock_locked(lock, RWLOCK_ACQUIRE_WRITE),
514 "rwlock unexpectedly held (write) by current thread");
515}
516