1#include <console/panic.h>
2#include <math/min_max.h>
3#include <sch/sched.h>
4#include <sch/wroost.h>
5#include <sync/rcu.h>
6#include <sync/turnstile.h>
7#include <thread/thread.h>
8
9#include "lock_general_internal.h"
10#include "rwlock_internal.h"
11
12#ifdef DEBUG_LOCK_CHK
13#include "lock_chk/internal.h"
14
15/* TODO: stamp at init */
16static inline void rwlock_chk_stamp(struct rwlock *lock) {
17 lock->chk.instance = lock;
18 lock->chk.type = LOCK_CHK_TYPE_RWLOCK;
19}
20#endif /* DEBUG_LOCK_CHK */
21
22/* for debugging purposes - upon panic we save data in here */
23static cc_unused struct rwlock panic_rwlock;
24static atomic(struct rwlock *) panic_rwlock_addr;
25
26static void rwlock_panic(char *msg, struct rwlock *offending_lock) {
27
28 struct rwlock *panic_expected = NULL;
29 if (atomic_cas_weak(&panic_rwlock_addr, &panic_expected, offending_lock,
30 mo_acquire, mo_rlx))
31 panic_rwlock = *offending_lock;
32
33 if (offending_lock)
34 panic_rwlock = *offending_lock;
35
36 uintptr_t v = atomic_load_rlx(&offending_lock->lock_word);
37 panic("%s, lock = %p, contents = %p, thread = %p", msg, offending_lock,
38 (void *) v, thread_get_current());
39}
40
41/* make sure no funny business happened after acquiring a lock */
42static inline bool rwlock_locked_with_type(struct rwlock *lock,
43 enum rwlock_acquire_type type) {
44 uintptr_t word = RWLOCK_READ_LOCK_WORD(lock);
45
46 if (type == RWLOCK_WRITE)
47 return RWLOCK_GET_OWNER_FROM_WORD(word) ==
48 (uintptr_t) thread_get_current();
49
50 if (type == RWLOCK_READ)
51 return ((word & RWLOCK_READER_COUNT_MASK) && !RWLOCK_WRITER_HELD(word));
52
53 return false;
54}
55
56static struct thread *rwlock_getref_owner(struct rwlock *lock) {
57 struct thread *owner;
58
59 rcu_read_lock();
60 uintptr_t word = RWLOCK_READ_LOCK_WORD(lock);
61 owner = RWLOCK_WRITER_HELD(word)
62 ? (struct thread *) RWLOCK_GET_OWNER_FROM_WORD(word)
63 : NULL;
64 if (owner && !thread_getref_rcu(t: owner))
65 owner = NULL;
66 rcu_read_unlock();
67
68 return owner;
69}
70
71/* get the mask to mask the lock to determine if we should try and acquire */
72static inline uintptr_t rwlock_get_busy_mask(enum rwlock_acquire_type t) {
73 if (t == RWLOCK_READ)
74 return RWLOCK_WRITER_HELD_BIT | RWLOCK_WRITER_WANT_BIT;
75
76 /* we just need the reader here because if there is a writer it will
77 * also set these bits and be detected */
78 return RWLOCK_READER_COUNT_MASK;
79}
80
81static inline uintptr_t rwlock_get_wait_bits(enum rwlock_acquire_type t) {
82 if (t == RWLOCK_READ)
83 return RWLOCK_WAITER_BIT;
84
85 return RWLOCK_WAITER_BIT | RWLOCK_WRITER_WANT_BIT;
86}
87
88static inline size_t rwlock_get_wait_queue(enum rwlock_acquire_type t) {
89 if (t == RWLOCK_READ)
90 return TURNSTILE_READER_QUEUE;
91
92 return TURNSTILE_WRITER_QUEUE;
93}
94
95static size_t rwlock_get_backoff(size_t current_backoff) {
96 if (!current_backoff)
97 return RWLOCK_BACKOFF_DEFAULT;
98
99 if (current_backoff >= (RWLOCK_BACKOFF_MAX >> RWLOCK_BACKOFF_SHIFT))
100 return RWLOCK_BACKOFF_MAX;
101
102 size_t new_backoff = current_backoff << RWLOCK_BACKOFF_SHIFT;
103 return MIN(new_backoff, RWLOCK_BACKOFF_MAX);
104}
105
106#ifdef DEBUG_LOCK_CHK
107
108static void rwlock_chk_state_init(struct rwlock *lock,
109 const struct lock_chk_class *class,
110 enum lock_chk_flags flags) {
111 enforce_precond((flags & ~LOCK_CHKD_FULL) == 0);
112 enforce_precond(flags == LOCK_UNCHKD || class != NULL);
113 lock->chk.flags = flags;
114 lock->chk.initialized = true;
115 atomic_store_rlx(&lock->chk.used, false);
116 lock_chk_map_runtime_init(&lock->chk.map, class);
117}
118
119static bool rwlock_idle_for_reconfiguration(struct rwlock *lock) {
120 uintptr_t word = RWLOCK_READ_LOCK_WORD(lock);
121 uintptr_t active = RWLOCK_WRITER_HELD_BIT | RWLOCK_WAITER_BIT |
122 RWLOCK_WRITER_WANT_BIT | RWLOCK_READER_COUNT_MASK;
123 return (word & active) == 0;
124}
125
126void rwlock_set_chk_flags(struct rwlock *lock, enum lock_chk_flags flags) {
127 enforce(lock->chk.initialized, UNINITIALIZED);
128 enforce(rwlock_idle_for_reconfiguration(lock));
129 enforce(!atomic_load_rlx(&lock->chk.used));
130 enforce_precond((flags & ~LOCK_CHKD_FULL) == 0);
131 lock->chk.flags = flags;
132}
133
134void rwlock_reinit_chk(struct rwlock *lock, enum thread_prio_class ceiling,
135 const struct lock_chk_class *class,
136 enum lock_chk_flags flags) {
137 enforce(lock->chk.initialized, UNINITIALIZED);
138 enforce(rwlock_idle_for_reconfiguration(lock));
139 rwlock_init_chk_full(lock, ceiling, class, flags);
140}
141
142#else /* !defined(DEBUG_LOCK_CHK) */
143
144static void rwlock_chk_state_init(struct rwlock *lock,
145 const struct lock_chk_class *class,
146 enum lock_chk_flags flags) {
147 cc_ignore(lock, class, flags);
148}
149
150void rwlock_set_chk_flags(struct rwlock *lock, enum lock_chk_flags flags) {
151 cc_ignore(lock, flags);
152}
153
154void rwlock_reinit_chk(struct rwlock *lock, enum thread_prio_class ceiling,
155 const struct lock_chk_class *class,
156 enum lock_chk_flags flags) {
157 rwlock_init_chk_full(lock, ceiling, class, flags);
158}
159
160#endif /* DEBUG_LOCK_CHK */
161
162void rwlock_init_chk_full(struct rwlock *lock, enum thread_prio_class ceiling,
163 const struct lock_chk_class *class,
164 enum lock_chk_flags flags) {
165 atomic_store_rlx(&lock->lock_word,
166 ((uintptr_t) ceiling << RWLOCK_PRIO_CEIL_SHIFT) &
167 RWLOCK_PRIO_CEIL_MASK);
168 rwlock_chk_state_init(lock, class, flags);
169}
170
171/* This prevents a lock that cannot possibly have a lower reader
172 * from going through the dance of hunting down CPUs to IPI
173 *
174 * TODO: use this */
175static cc_maybe_unused bool
176rwlock_has_lower_readers_than(struct rwlock *lock,
177 enum thread_prio_class prio) {
178 /* This is called from the writer's context, once the
179 * RWLOCK_WRITER_WANT_BIT is set. No more readers
180 * can get the lock after this point, so it is
181 * safe to snapshot the lock word like this */
182 uintptr_t word = RWLOCK_READ_LOCK_WORD(lock);
183 uintptr_t lower_mask =
184 rwlock_make_one_reader_count(base_prio: prio) - BIT(RWLOCK_READ_BIT_IDX);
185 return (word & lower_mask) != 0;
186}
187
188/* TODO:
189 *
190 * When a reader enters a rwlock, its base priority class CANNOT change.
191 *
192 * There's currently no code that changes base priorities after
193 * threads get enqueued, however, we do need to remember that there
194 * are only "safe states" that allow it to change, like lock_nesting == 0.
195 *
196 * Furthermore, this likely needs to be generic and extrapolate across
197 * mutexes and whatnot... Perhaps what we will actually do is completely
198 * get rid of this idea of a "base priority" and make ONLY the counters
199 * contribute to a perceived priority and thus the problem is solved (??).
200 */
201void rw_lock_full(struct rwlock *lock, enum rwlock_acquire_type acq_type,
202 enum lock_subclass subclass,
203 const struct lock_chk_site *site) TSA_NO_ANALYSIS {
204 cc_ignore(site);
205 enforce_precond(subclass < LOCK_CHK_MAX_SUBCLASSES, CAPACITY_EXCEEDED);
206 enforce_precond(acq_type == RWLOCK_READ || acq_type == RWLOCK_WRITE);
207
208 enforce(irq_not_in_interrupt(), INVALID_CONTEXT);
209 enforce(irql_get() <= IRQL_APC_LEVEL, INVALID_CONTEXT);
210
211#ifdef DEBUG_LOCK_CHK
212 enum lock_chk_mode chk_mode = acq_type == RWLOCK_READ
213 ? LOCK_CHK_MODE_SHARED
214 : LOCK_CHK_MODE_EXCLUSIVE;
215 struct lock_chk_acq_req req;
216 struct lock_chk_acq_token token;
217 enum lock_op_flags flags = LOCK_OP_IRQ_NONE | LOCK_OP_KIND_BLOCKING;
218 lock_chk_note_use(&lock->chk, flags);
219 bool checked_deep = lock->chk.flags != LOCK_UNCHKD;
220 if (checked_deep) {
221 rwlock_chk_stamp(lock);
222 req =
223 lock_chk_acq_req_make(&lock->chk, site, chk_mode, subclass, flags);
224 lock_chk_before_acq(&token, &req);
225 }
226#endif
227
228 uintptr_t lword = RWLOCK_READ_LOCK_WORD(lock);
229
230 /* We are using this as a potential
231 * reserved state for special rwlocks */
232 enforce(RWLOCK_GET_MAX_PRIO(lword) != 0, INVALID_STATE,
233 "rwlock max prio cannot be 0");
234
235 struct thread *curr = thread_get_current();
236 enum thread_prio_class base_class = curr->base_prio_class;
237 wroost_pre_acquire(lock, type: acq_type);
238 enforce(curr->base_prio_class <= RWLOCK_GET_MAX_PRIO(lword));
239
240 /* fastpath */
241 if (rwlock_try_lock(lock, thread: curr, type: acq_type, base: base_class))
242 goto out;
243
244 uintptr_t old, new;
245
246 /* reset backoff once this equals global.core_count */
247 size_t looped = 0;
248 size_t backoff = RWLOCK_BACKOFF_DEFAULT;
249 size_t queue = rwlock_get_wait_queue(t: acq_type);
250
251 /* what do we mask against to see if the lock is busy? */
252 uintptr_t busy_mask = rwlock_get_busy_mask(t: acq_type);
253
254 /* what bits do we set when we decide to go wait? */
255 uintptr_t wait_bits = rwlock_get_wait_bits(t: acq_type);
256
257 /* if we are reading, we are here because there is a writer.
258 *
259 * if we are writing, we are here because there is a writer or reader.
260 *
261 * regardless, do backoff...
262 *
263 * NOTE: rwlock unlocking performs direct handoff!
264 */
265 while (true) {
266 if (!RWLOCK_BUSY(old = RWLOCK_READ_LOCK_WORD(lock), busy_mask)) {
267 if (rwlock_try_lock(lock, thread: curr, type: acq_type, base: base_class))
268 break;
269
270 backoff = rwlock_get_backoff(current_backoff: backoff);
271 lock_delay(backoff, RWLOCK_BACKOFF_JITTER_PCT);
272 if (++looped == global.core_count) {
273 backoff = RWLOCK_BACKOFF_DEFAULT;
274 looped = 0;
275 }
276 continue;
277 }
278
279 if (RWLOCK_GET_OWNER_FROM_WORD(old) == (uintptr_t) curr)
280 rwlock_panic(msg: "recursive lock", offending_lock: lock);
281
282 struct turnstile *ts;
283 enum irql irql_out = turnstile_lookup(obj: lock, out_ts: &ts);
284
285 /* try to set our wait bits, stop if lock becomes available */
286 while (true) {
287 old = RWLOCK_READ_LOCK_WORD(lock);
288
289 if (!RWLOCK_BUSY(old, busy_mask))
290 break;
291
292 new = old | wait_bits;
293
294 if (atomic_cas_weak(&lock->lock_word, &old, new, mo_acq_rel,
295 mo_acquire))
296 break;
297
298 if (!RWLOCK_BUSY(old, busy_mask))
299 break;
300 }
301
302 if (!RWLOCK_BUSY(old, busy_mask)) {
303 turnstile_unlock(obj: lock, irql: irql_out);
304 continue;
305 }
306
307 /* okay we could not get the lock */
308
309 /* make sure we've set the lock bits */
310 enforce(RWLOCK_READ_LOCK_WORD(lock) & wait_bits);
311
312 struct thread *owner = rwlock_getref_owner(lock);
313 if (owner) {
314 /* Same idea as mutex.c */
315 thread_putref(t: owner);
316 }
317
318 turnstile_block(ts, queue_num: queue, lock_obj: lock, lock_irql: irql_out, owner);
319
320 /* when we wake up, we will have the lock handed off to us... */
321 break;
322 }
323
324out:
325
326 /* make sure nothing funny happened */
327 enforce(rwlock_locked_with_type(lock, acq_type));
328
329#ifdef DEBUG_LOCK_CHK
330 if (checked_deep)
331 lock_chk_acqd(&token);
332#endif
333
334 wroost_post_acquire(lock, type: acq_type);
335
336 crash_unwind_enter_rwlock(r: lock);
337}
338
339/* return the number of readers we want to wake,
340 * or zero if we should wake a writer */
341
342/* only to be called from exiting writers
343 *
344 * grant the lock to readers with the same or higher priority than the highest
345 * priority writer...
346 */
347static uintptr_t rwlock_get_readers_to_wake(struct turnstile *ts,
348 size_t *raw_count) {
349 struct rbt_node *wnode, *rnode, *iter;
350 struct thread *writer = NULL;
351
352 wnode = rbt_last(root: &ts->queues[TURNSTILE_WRITER_QUEUE]);
353 rnode = rbt_last(root: &ts->queues[TURNSTILE_READER_QUEUE]);
354
355 /* verify that somebody is on the queues */
356 enforce(wnode || rnode);
357
358 if (wnode)
359 writer = thread_from_wq_rbt_node(wnode);
360
361 /* for each reader that beats this priority,
362 * increment the count of readers to wake */
363 int32_t prio_to_beat = writer ? writer->wq_prio : -1;
364 size_t to_wake = 0;
365 *raw_count = 0;
366
367 rbt_for_each_reverse(iter, &ts->queues[TURNSTILE_READER_QUEUE]) {
368 struct thread *check_reader = thread_from_wq_rbt_node(iter);
369
370 /* can no longer beat the thread priority of the writer */
371 int32_t prio = check_reader->wq_prio;
372
373 if (prio < prio_to_beat)
374 break;
375
376 to_wake += rwlock_make_one_reader_count(base_prio: check_reader->base_prio_class);
377 *raw_count = *raw_count + 1;
378 }
379
380 return to_wake;
381}
382
383/* Wake every reader from the head to target */
384static uintptr_t rwlock_get_readers_to_wake_through(struct turnstile *ts,
385 struct thread *target,
386 size_t *raw_count) {
387 struct rbt_node *iter;
388 uintptr_t to_wake = 0;
389 *raw_count = 0;
390
391 rbt_for_each_reverse(iter, &ts->queues[TURNSTILE_READER_QUEUE]) {
392 struct thread *reader = thread_from_wq_rbt_node(iter);
393 to_wake += rwlock_make_one_reader_count(base_prio: reader->base_prio_class);
394 *raw_count = *raw_count + 1;
395
396 if (reader == target)
397 return to_wake;
398 }
399
400 unreachable("fairness target is not on the reader queue");
401}
402
403static uintptr_t
404rwlock_unlock_get_val_to_sub(struct rwlock *lock,
405 enum thread_prio_class base_class) {
406 struct thread *current_thread = thread_get_current();
407 uintptr_t lock_word = RWLOCK_READ_LOCK_WORD(lock);
408 if (RWLOCK_WRITER_HELD(lock_word)) {
409 if (RWLOCK_GET_OWNER_FROM_WORD(lock_word) !=
410 (uintptr_t) current_thread) {
411 rwlock_panic(msg: "non-owner thread unlocked as exclusive waiter", offending_lock: lock);
412 }
413
414 return ((uintptr_t) current_thread) | RWLOCK_WRITER_HELD_BIT;
415 } else {
416 if ((lock_word & RWLOCK_READER_COUNT_MASK) == 0)
417 rwlock_panic(msg: "reader unlocked with no readers left on lock", offending_lock: lock);
418
419 return rwlock_make_one_reader_count(base_prio: base_class);
420 }
421}
422
423void rw_unlock_full(struct rwlock *lock,
424 const struct lock_chk_site *site) TSA_NO_ANALYSIS {
425 cc_ignore(site);
426 enforce(irq_not_in_interrupt(), INVALID_CONTEXT);
427 enforce(irql_get() <= IRQL_APC_LEVEL, INVALID_CONTEXT);
428
429 uintptr_t lock_word = RWLOCK_READ_LOCK_WORD(lock);
430 bool is_writer = (lock_word & RWLOCK_WRITER_HELD_BIT) != 0;
431
432#ifdef DEBUG_LOCK_CHK
433 enum lock_chk_mode chk_mode =
434 is_writer ? LOCK_CHK_MODE_EXCLUSIVE : LOCK_CHK_MODE_SHARED;
435 struct lock_chk_rel_req req;
436 struct lock_chk_rel_token token;
437 bool checked_deep = lock->chk.flags != LOCK_UNCHKD;
438 if (checked_deep) {
439 rwlock_chk_stamp(lock);
440 req = lock_chk_rel_req_make(&lock->chk, site, chk_mode);
441 lock_chk_before_rel(&token, &req);
442 }
443#endif
444
445 /* once again, we raise the IRQL to DISPATCH to prevent
446 * us from being switched out while we unlock */
447 size_t backoff = RWLOCK_BACKOFF_DEFAULT;
448 size_t looped = 0;
449
450 struct thread *curr = thread_get_current();
451 enum thread_prio_class base_class = curr->base_prio_class;
452
453 /* we can cheekily use this to figure out what to "subtract from the
454 * lock" to determine what the lock word should be on unlock CAS */
455 uintptr_t val_to_subtract = rwlock_unlock_get_val_to_sub(lock, base_class);
456
457 while (true) {
458 uintptr_t old = RWLOCK_READ_LOCK_WORD(lock);
459 uintptr_t new = old - val_to_subtract;
460
461 /* there are still readers left and there are still waiters, this
462 * is not the final exit of a lock, so we just drop the lock */
463 if ((new & (RWLOCK_READER_COUNT_MASK | RWLOCK_WAITER_BIT)) !=
464 RWLOCK_WAITER_BIT) {
465 /* successful swap, we're all good */
466 if (atomic_cas_weak(&lock->lock_word, &old, new, mo_release,
467 mo_rlx))
468 break;
469
470 /* unsuccessful... try again */
471 backoff = rwlock_get_backoff(current_backoff: backoff);
472 lock_delay(backoff, RWLOCK_BACKOFF_JITTER_PCT);
473
474 /* reset if we have reached the # of CPUs */
475 if (++looped == global.core_count) {
476 looped = 0;
477 backoff = RWLOCK_BACKOFF_DEFAULT;
478 }
479
480 continue;
481 }
482
483 /* we are the last reader of a lock with waiters */
484 struct turnstile *ts;
485 enum irql irql_out = turnstile_lookup(obj: lock, out_ts: &ts);
486
487 struct rbt_node *wnode = rbt_last(root: &ts->queues[TURNSTILE_WRITER_QUEUE]);
488
489 struct thread *writer = wnode ? thread_from_wq_rbt_node(wnode) : NULL;
490 size_t to_wake = 0;
491 uintptr_t to_wake_ctr = 0;
492
493 size_t fair_queue = TURNSTILE_WRITER_QUEUE;
494 struct thread *fair = turnstile_fair_pick(ts, queue_out: &fair_queue);
495
496 if (fair && fair_queue == TURNSTILE_WRITER_QUEUE) {
497 writer = fair;
498 to_wake = 0;
499 } else if (fair) {
500 /* Wake up a superset of waiters
501 * of what pure priority ordering would.
502 *
503 * This is because fast path readers can simply trylock CAS
504 * and get the lock before any older blocked readers might
505 */
506 size_t prio_wake;
507 uintptr_t prio_ctr = rwlock_get_readers_to_wake(ts, raw_count: &prio_wake);
508 to_wake_ctr =
509 rwlock_get_readers_to_wake_through(ts, target: fair, raw_count: &to_wake);
510 if (prio_wake > to_wake) {
511 to_wake = prio_wake;
512 to_wake_ctr = prio_ctr;
513 }
514 } else {
515 to_wake_ctr = rwlock_get_readers_to_wake(ts, raw_count: &to_wake);
516 }
517
518 if (writer && to_wake == 0) {
519 /* directly transfer ownership to the next writer */
520 new = rwlock_make_write_word(lock, thread: writer);
521
522 if (ts->waiters > 1)
523 new |= RWLOCK_WAITER_BIT;
524
525 /* Still more writers? */
526 if (&writer->wq_tree_node != wnode || rbt_prev(node: wnode))
527 new |= RWLOCK_WRITER_WANT_BIT;
528
529 RWLOCK_WRITE_LOCK_WORD(lock, new);
530 turnstile_wake_handoff(ts, TURNSTILE_WRITER_QUEUE, target: writer,
531 lock_irql: irql_out);
532 } else {
533 /* give the lock to all waiters at once */
534 new = to_wake_ctr;
535
536 if (ts->waiters > to_wake)
537 new |= RWLOCK_WAITER_BIT;
538
539 if (writer)
540 new |= RWLOCK_WRITER_WANT_BIT;
541
542 new |= (RWLOCK_READ_LOCK_WORD(lock) & RWLOCK_PRIO_CEIL_MASK);
543
544 RWLOCK_WRITE_LOCK_WORD(lock, new);
545 turnstile_wake(ts, TURNSTILE_READER_QUEUE, num_threads: to_wake, lock_irql: irql_out);
546 }
547
548 /* all done */
549 break;
550 }
551
552#ifdef DEBUG_LOCK_CHK
553 if (checked_deep)
554 lock_chk_reld(&token);
555#endif /* DEBUG_LOCK_CHK */
556
557 wroost_post_release(lock, type: is_writer ? RWLOCK_WRITE : RWLOCK_READ);
558
559 crash_unwind_exit_rwlock(r: lock);
560}
561
562bool rwlock_locked(struct rwlock *lock, enum rwlock_acquire_type type) {
563 return rwlock_locked_with_type(lock, type);
564}
565
566void rwlock_assert_held_full(struct rwlock *lock, enum rwlock_acquire_type type,
567 const struct lock_chk_site *site) {
568#ifdef DEBUG_LOCK_CHK
569 rwlock_chk_stamp(lock);
570 enum lock_chk_mode chk_mode =
571 type == RWLOCK_READ ? LOCK_CHK_MODE_SHARED : LOCK_CHK_MODE_EXCLUSIVE;
572 if (lock->chk.flags != LOCK_UNCHKD &&
573 lock_chk_assert_held_deep(&lock->chk, chk_mode, /*want_held=*/true,
574 site))
575 return;
576#else
577 cc_ignore(site);
578#endif
579
580 enforce(rwlock_locked(lock, type), "rwlock not held");
581}
582
583void rwlock_assert_not_held_full(struct rwlock *lock,
584 const struct lock_chk_site *site) {
585#ifdef DEBUG_LOCK_CHK
586 rwlock_chk_stamp(lock);
587 if (lock->chk.flags != LOCK_UNCHKD &&
588 lock_chk_assert_held_deep(&lock->chk, LOCK_CHK_MODE_IGNORED,
589 /*want_held=*/false, site))
590 return;
591#else
592 cc_ignore(site);
593#endif
594
595 /* Raw fallback can only check write mode ownership, which is
596 * a small caveat of the system here, as reads can be
597 * any reader, not necessarily "this reader" */
598 enforce(!rwlock_locked(lock, RWLOCK_WRITE),
599 "rwlock unexpectedly held (write) by current thread");
600}
601