1#include <enforce.h>
2#include <math/min_max.h>
3#include <mem/alloc.h>
4#include <mem/nofail.h>
5#include <mem/slab.h> /* to get SLAB_OBJ_ALIGN */
6#include <sch/sched.h>
7#include <sync/rcu.h>
8#include <sync/turnstile.h>
9#include <thread/thread.h>
10
11/* LOCK ORDERING: wroost_lock -> chain -> thread.wait_lock ->
12 * header / runqueues -> thread lock -> pi_lock */
13
14SLAB_SIZE_REGISTER_FOR_STRUCT(turnstile, SLAB_OBJ_ALIGN_DEFAULT);
15
16/* Implements turnstiles used on synchronization objects
17 *
18 * This uses a strategy similar to later versions of Solaris
19 * and FreeBSD, kudos to all the people who worked on those operating systems!
20 *
21 * Turnstiles give us pointer-sized adaptive mutexes (very good to have).
22 *
23 * Each thread is born with a turnstile (technically, this is still
24 * *slightly* overkill because you need to have a thread to block on to even
25 * use your turnstile, so it ideally would be thread_count/2 turnstiles on the
26 * whole system, but that introduces a non-negligible amount of overhead for the
27 * extra bookkeeping, so we just give each thread one turnstile and call it a
28 * day).
29 *
30 * Whenever a thread blocks on a lock, we first go and check if the lock
31 * already has an entry in the global turnstile hash table. If it is the first
32 * thread to block on the lock (no entry in hash table), then we lend over our
33 * own turnstile and go and block. If the lock already has a turnstile, then we
34 * lend over our turnstile to the freelist of the turnstile that the lock is
35 * associated with.
36 *
37 * When a thread wakes up from the block, it takes a turnstile from the freelist
38 * of the turnstile that it is blocked on. If there are no waiters, then we
39 * don't bother with that and just take the turnstile itself (there would be no
40 * freelist) and remove it from the hash table.
41 *
42 * There is also priority inheritence which is done by walking the list of
43 * blocked threads and taking our current thread's priority and boosting
44 * threads that need the boost.
45 *
46 * The hash table per-head locks protect the hash tables and contents of all
47 * turnstiles residing in the hash table.
48 */
49
50LOCK_CHK_CLASS_DEFINE_LOCAL(turnstile_chain);
51
52void turnstiles_init(void) {
53 global.turnstiles = nofail_vnew(global.turnstiles, ALLOC_ZERO);
54 for (size_t i = 0; i < TURNSTILE_HASH_SIZE; i++) {
55 spinlock_init_chk(&global.turnstiles->heads[i].lock,
56 LOCK_CHK_CLASS(turnstile_chain), LOCK_CHKD_FULL);
57 list_head_init(h: &global.turnstiles->heads[i].list);
58 }
59}
60
61#define TURNSTILE_BACKGROUND_PRIO 1
62#define TURNSTILE_TS_PRIO_BASE 2
63#define TURNSTILE_TS_PRIO_MAX 100000
64#define TURNSTILE_RT_PRIO 100001
65#define TURNSTILE_URGENT_PRIO 100002
66
67static inline enum irql
68turnstile_hash_chain_lock(struct turnstile_hash_chain *chain) TSA_NO_ANALYSIS {
69 return spin_lock_high(&chain->lock);
70}
71
72static inline void
73turnstile_hash_chain_unlock(struct turnstile_hash_chain *chain,
74 enum irql irql) TSA_NO_ANALYSIS {
75 spin_unlock(&chain->lock, irql);
76}
77
78int32_t turnstile_thread_priority(struct thread *t) {
79 switch (t->perceived_prio_class) {
80 case THREAD_PRIO_CLASS_BACKGROUND: return TURNSTILE_BACKGROUND_PRIO;
81 case THREAD_PRIO_CLASS_TIMESHARE:
82 return (TURNSTILE_TS_PRIO_BASE + t->weight) > TURNSTILE_TS_PRIO_MAX
83 ? TURNSTILE_TS_PRIO_MAX
84 : TURNSTILE_TS_PRIO_BASE + t->weight;
85 case THREAD_PRIO_CLASS_REALTIME: return TURNSTILE_RT_PRIO;
86 case THREAD_PRIO_CLASS_URGENT: return TURNSTILE_URGENT_PRIO;
87 }
88 unreachable("thread prio class invalid");
89}
90
91/* NOTE: we copy the computed turnstile wait queue key and then put it
92 * in wq_prio. This is because threads can change the actual priority (class,
93 * or the weights for timesharing threads) without holding the hash
94 * chain lock, which would lead to keys in the tree shifting about,
95 * and some bigger problems for other readers.
96 *
97 * We do eventually turnstile_requeue_waiter though. */
98static size_t turnstile_thread_get_data(struct rbt_node *n) {
99 return thread_from_wq_rbt_node(n)->wq_prio;
100}
101
102static int32_t turnstile_thread_cmp(const struct rbt_node *a,
103 const struct rbt_node *b) {
104 int32_t ta = turnstile_thread_get_data(n: (void *) a);
105 int32_t tb = turnstile_thread_get_data(n: (void *) b);
106 return ta - tb;
107}
108
109struct turnstile *turnstile_init(struct turnstile *ts) {
110 thread_wait_header_init(header: &ts->wait);
111 ts->lock_obj = NULL;
112 ts->waiters = 0;
113 ts->state = TURNSTILE_STATE_UNUSED;
114 ts->owner = NULL;
115 ts->pi = THREAD_CLASS_DONATION_EMPTY;
116 ts->next_wait_seq = 0;
117 ts->handoffs = 0;
118
119 rbt_init(t: &ts->queues[TURNSTILE_READER_QUEUE], get_data: turnstile_thread_get_data,
120 compare: turnstile_thread_cmp);
121 rbt_init(t: &ts->queues[TURNSTILE_WRITER_QUEUE], get_data: turnstile_thread_get_data,
122 compare: turnstile_thread_cmp);
123 list_head_init(h: &ts->freelist);
124 list_node_init(n: &ts->hash_list);
125
126 return ts;
127}
128
129void turnstile_destroy(struct turnstile *ts) {
130 vfree(ts);
131}
132
133struct turnstile *turnstile_create(void) {
134 struct turnstile *ts = vnew(ts, ALLOC_ZERO);
135 if (!ts)
136 return NULL;
137
138 return turnstile_init(ts);
139}
140
141static inline struct turnstile_hash_chain *turnstile_chain_for(void *obj) {
142 size_t idx = TURNSTILE_OBJECT_HASH(obj);
143 return &global.turnstiles->heads[idx];
144}
145
146static void turnstile_insert_to_freelist(struct turnstile *parent,
147 struct turnstile *child) {
148 SPINLOCK_ASSERT_HELD(&turnstile_chain_for(parent->lock_obj)->lock);
149 list_head_push_back(h: &parent->freelist, n: &child->freelist_node);
150 child->state = TURNSTILE_STATE_IN_FREE_LIST;
151}
152
153static struct turnstile *turnstile_freelist_pop(struct turnstile *ts) {
154 struct list_node *lh = list_head_pop_front_init(h: &ts->freelist);
155 enforce(lh); /* we are not to call this if the freelist is empty */
156 struct turnstile *ret = turnstile_from_freelist(lh);
157 ret->state = TURNSTILE_STATE_UNUSED;
158 return ret;
159}
160
161static void turnstile_insert(struct turnstile_hash_chain *chain,
162 struct turnstile *ts, void *lock_obj) {
163 SPINLOCK_ASSERT_HELD(&chain->lock);
164 list_head_push_back(h: &chain->list, n: &ts->hash_list);
165 ts->state = TURNSTILE_STATE_IN_HASH_TABLE;
166 ts->lock_obj = lock_obj;
167 ts->handoffs = 0;
168}
169
170static void turnstile_remove(struct turnstile_hash_chain *chain,
171 struct turnstile *ts) {
172 SPINLOCK_ASSERT_HELD(&chain->lock);
173 list_node_delete_init(n: &ts->hash_list);
174 ts->state = TURNSTILE_STATE_UNUSED;
175 ts->lock_obj = NULL;
176}
177
178struct turnstile_wait_snapshot {
179 struct turnstile *ts;
180 void *lock_obj;
181 uint64_t epoch;
182};
183
184static bool turnstile_snapshot_wait(struct thread *thread,
185 struct turnstile_wait_snapshot *wait) {
186 enum irql irql = spin_lock_high(&thread->wait_lock);
187 struct thread_wait_block *block = thread->active_wait_blocks;
188 bool valid =
189 block == thread->wait_blocks &&
190 thread->wait_block_count > THREAD_WAIT_BLOCK_SYNC &&
191 block[THREAD_WAIT_BLOCK_SYNC].state == THREAD_WAIT_BLOCK_ACTIVE;
192
193 if (valid) {
194 wait->ts = atomic_load_acq(&thread->blocked_ts);
195 wait->lock_obj = block[THREAD_WAIT_BLOCK_SYNC].object;
196 wait->epoch = atomic_load_rlx(&thread->wait_epoch);
197 valid = wait->ts != NULL;
198 }
199
200 spin_unlock(&thread->wait_lock, irql);
201 return valid;
202}
203
204static void turnstile_requeue_waiter(struct turnstile *ts,
205 struct thread *thread) {
206 SPINLOCK_ASSERT_HELD(&turnstile_chain_for(ts->lock_obj)->lock);
207
208 int32_t prio = turnstile_thread_priority(t: thread);
209 if (thread->wq_prio == prio)
210 return;
211
212 for (size_t queue = 0; queue < TURNSTILE_NUM_QUEUES; queue++) {
213 struct rbt *tree = &ts->queues[queue];
214 if (!rbt_has_node(tree, node: &thread->wq_tree_node))
215 continue;
216
217 thread->wq_prio = prio;
218 rbt_reinsert(tree, node: &thread->wq_tree_node);
219 return;
220 }
221}
222
223static struct turnstile *turnstile_lookup_internal(void *obj) {
224 struct turnstile_hash_chain *chain = turnstile_chain_for(obj);
225 struct list_node *pos;
226
227 list_for_each(pos, &chain->list) {
228 struct turnstile *ts = turnstile_from_hash_list_node(pos);
229 if (ts->lock_obj == obj)
230 return ts;
231 }
232
233 return NULL;
234}
235
236enum irql turnstile_lookup(void *obj, struct turnstile **out_ts) {
237 struct turnstile_hash_chain *chain = turnstile_chain_for(obj);
238
239 enum irql irql = turnstile_hash_chain_lock(chain);
240 if (out_ts)
241 *out_ts = turnstile_lookup_internal(obj);
242 return irql;
243}
244
245static void turnstile_pi_remove(struct turnstile *ts) {
246 SPINLOCK_ASSERT_HELD(&turnstile_chain_for(ts->lock_obj)->lock);
247
248 thread_uninherit_priority(d: &ts->pi);
249}
250
251static struct thread *turnstile_dequeue(struct turnstile *ts, size_t queue,
252 struct rbt_node *node) {
253 void *obj = ts->lock_obj;
254 struct turnstile_hash_chain *chain = turnstile_chain_for(obj);
255
256 rbt_delete(tree: &ts->queues[queue], z: node);
257 struct thread *thread = thread_from_wq_rbt_node(node);
258
259 atomic_store_release(&thread->blocked_ts, NULL);
260
261 struct turnstile *got = ts;
262 if (ts->waiters == 1) { /* last waiter, take the turnstile with you! */
263 /* you're taking the turnstile */
264 enforce(list_head_empty(&ts->freelist));
265 turnstile_remove(chain, ts);
266 } else {
267 /* not the last waiter, take one from the freelist */
268 enforce(!list_head_empty(&ts->freelist));
269 got = enforce(turnstile_freelist_pop(ts));
270 }
271
272 /* you take this turnstile with you as you wake up please */
273 thread->turnstile = got;
274
275 /* you are also no longer a waiter */
276 ts->waiters--;
277 return thread;
278}
279
280static struct thread *turnstile_dequeue_first(struct turnstile *ts,
281 size_t queue) {
282 return turnstile_dequeue(ts, queue, node: rbt_last(root: &ts->queues[queue]));
283}
284
285static int turnstile_prio_band(int32_t prio) {
286 if (prio < TURNSTILE_TS_PRIO_BASE)
287 return 0;
288
289 if (prio <= TURNSTILE_TS_PRIO_MAX)
290 return 1;
291
292 return prio == TURNSTILE_RT_PRIO ? 2 : 3;
293}
294
295/* Fairly pick so high prio waiters can't prevent
296 * low prio waiters from waking */
297struct thread *turnstile_fair_pick(struct turnstile *ts, size_t *queue_out) {
298 SPINLOCK_ASSERT_HELD(&turnstile_chain_for(ts->lock_obj)->lock);
299
300 if (++ts->handoffs < TURNSTILE_BYPASS_LIMIT)
301 return NULL;
302
303 ts->handoffs = 0;
304
305 int32_t top = INT32_MIN;
306 for (size_t q = 0; q < TURNSTILE_NUM_QUEUES; q++) {
307 struct rbt_node *n = rbt_last(root: &ts->queues[q]);
308 if (n && thread_from_wq_rbt_node(n)->wq_prio > top)
309 top = thread_from_wq_rbt_node(n)->wq_prio;
310 }
311
312 if (top == INT32_MIN)
313 return NULL;
314
315 int band = turnstile_prio_band(prio: top);
316 struct thread *oldest = NULL;
317 struct rbt_node *it;
318
319 for (size_t q = 0; q < TURNSTILE_NUM_QUEUES; q++) {
320 rbt_for_each_reverse(it, &ts->queues[q]) {
321 struct thread *w = thread_from_wq_rbt_node(it);
322 if (turnstile_prio_band(prio: w->wq_prio) != band)
323 break; /* reverse order, everything after would be lower */
324
325 if (!oldest || w->wq_seq < oldest->wq_seq) {
326 oldest = w;
327 *queue_out = q;
328 }
329 }
330 }
331
332 return oldest;
333}
334
335void turnstile_wake(struct turnstile *ts, size_t queue, size_t num_threads,
336 enum irql lock_irql) {
337 /* remove from hash */
338 void *obj = ts->lock_obj;
339 struct turnstile_hash_chain *chain = turnstile_chain_for(obj);
340 SPINLOCK_ASSERT_HELD(&chain->lock);
341
342 /* un-inherit the priority we inherited */
343 turnstile_pi_remove(ts);
344
345 ts->owner = NULL;
346
347 struct thread *to_wake, *tmp;
348 struct list_head wake_list;
349 list_head_init(h: &wake_list);
350
351 while (num_threads-- > 0) {
352 /* wake the one of highest priority */
353 to_wake = turnstile_dequeue_first(ts, queue);
354 list_head_push_back(h: &wake_list, n: &to_wake->wq_list_node);
355 }
356
357 turnstile_hash_chain_unlock(chain, irql: lock_irql);
358
359 list_for_each_entry_safe(to_wake, tmp, &wake_list, wq_list_node) {
360 list_node_delete(n: &to_wake->wq_list_node);
361 enforce(
362 thread_wait_satisfy(&to_wake->wait_blocks[THREAD_WAIT_BLOCK_SYNC],
363 THREAD_WAKE_REASON_BLOCKING_MANUAL, NULL));
364 }
365}
366
367static enum thread_prio_class turnstile_waiter_class(struct rbt_node *n) {
368 struct thread *t = thread_from_wq_rbt_node(n);
369 spin_guard_high(&t->pi_lock);
370 return t->perceived_prio_class;
371}
372
373void turnstile_wake_handoff(struct turnstile *ts, size_t queue,
374 struct thread *target, enum irql lock_irql) {
375 void *obj = ts->lock_obj;
376 struct turnstile_hash_chain *chain = turnstile_chain_for(obj);
377 SPINLOCK_ASSERT_HELD(&chain->lock);
378
379 /* un-inherit the priority we inherited */
380 turnstile_pi_remove(ts);
381 ts->owner = NULL;
382
383 struct rbt_node *head = rbt_last(root: &ts->queues[queue]);
384 enforce(head);
385 struct rbt_node *first = target ? &target->wq_tree_node : head;
386 enforce(rbt_has_node(&ts->queues[queue], first));
387 struct thread *new_owner = thread_from_wq_rbt_node(first);
388
389 if (ts->waiters > 1) {
390 bool any_pi = false;
391 enum thread_prio_class top = THREAD_PRIO_CLASS_BACKGROUND;
392
393 for (size_t q = 0; q < TURNSTILE_NUM_QUEUES; q++) {
394 /* highest remaining waiter once new_owner leaves this queue */
395 struct rbt_node *n;
396 if (q != queue) {
397 n = rbt_last(root: &ts->queues[q]);
398 } else if (first == head) {
399 n = rbt_prev(node: head);
400 } else {
401 n = head;
402 }
403
404 if (!n)
405 continue;
406
407 enum thread_prio_class prio_class = turnstile_waiter_class(n);
408 if (!any_pi || prio_class > top)
409 top = prio_class;
410
411 any_pi = true;
412 }
413
414 if (any_pi) {
415 ts->owner = new_owner;
416 thread_donate_class(boosted: new_owner, class: top, d: &ts->pi);
417 }
418 }
419
420 struct thread *to_wake = turnstile_dequeue(ts, queue, node: first);
421 enforce(to_wake == new_owner);
422
423 turnstile_hash_chain_unlock(chain, irql: lock_irql);
424
425 enforce(thread_wait_satisfy(&to_wake->wait_blocks[THREAD_WAIT_BLOCK_SYNC],
426 THREAD_WAKE_REASON_BLOCKING_MANUAL, NULL));
427}
428
429void turnstile_unlock(void *obj, enum irql irql) {
430 struct turnstile_hash_chain *chain = turnstile_chain_for(obj);
431 turnstile_hash_chain_unlock(chain, irql);
432}
433
434bool turnstile_propagate_wroost(struct wroost_percpu_data *pcd,
435 struct thread *t) {
436 struct turnstile_hash_chain *chain = NULL;
437 enum irql irql = IRQL_NONE;
438 struct thread *waiter = t;
439 int bother_self = 0;
440
441 rcu_read_lock();
442
443 while (true) {
444 struct turnstile_wait_snapshot next_wait, cur_wait;
445
446 if (!turnstile_snapshot_wait(thread: waiter, wait: &next_wait))
447 break;
448
449 /* TODO: I should add debug stuff to this */
450 struct turnstile_hash_chain *next_chain =
451 turnstile_chain_for(obj: next_wait.lock_obj);
452
453 if (next_chain != chain) {
454 if (chain)
455 turnstile_hash_chain_unlock(chain, irql);
456
457 chain = next_chain;
458 irql = turnstile_hash_chain_lock(chain);
459 }
460
461 /* Look it up again */
462 struct turnstile *cur_ts =
463 turnstile_lookup_internal(obj: next_wait.lock_obj);
464
465 bool ts_valid = cur_ts && cur_ts == next_wait.ts;
466 bool snapshot = turnstile_snapshot_wait(thread: waiter, wait: &cur_wait);
467 bool curr_valid = snapshot && cur_wait.ts == cur_ts &&
468 cur_wait.lock_obj == next_wait.lock_obj &&
469 cur_wait.epoch == next_wait.epoch;
470
471 if (!ts_valid || !curr_valid)
472 break;
473
474 turnstile_requeue_waiter(ts: cur_ts, thread: waiter);
475
476 /* TODO: thread_inherit_priority and wroost integration */
477 struct thread *owner = cur_ts->owner;
478 if (!owner)
479 break;
480
481 struct wroost_kicks kicks = {0};
482
483 /* Technically we only need to wroost_merge_kicks
484 * IFF thread_inherit_priority succeeds, because on failure, no
485 * PI happened, but merging regardless is harmless */
486 bool inherited =
487 thread_inherit_priority(boosted: owner, from: waiter, d: &cur_ts->pi, kicks_out: &kicks);
488 bother_self += wroost_merge_kicks(pcd, kicks: &kicks);
489 if (!inherited)
490 break;
491
492 waiter = owner;
493 }
494
495 if (chain)
496 turnstile_hash_chain_unlock(chain, irql);
497
498 rcu_read_unlock();
499
500 return bother_self > 0;
501}
502
503static enum irql
504turnstile_propagate_boost(struct turnstile_hash_chain *locked_chain,
505 struct turnstile *ts, enum irql irql) {
506 struct turnstile_hash_chain *chain = locked_chain;
507 struct turnstile *cur_ts = ts;
508 struct thread *boosting_from = thread_get_current();
509
510 /* RCU keeps threads alive when reading owners,
511 * and we re-hash objects upon lookup */
512 rcu_read_lock();
513
514 while (true) {
515 struct thread *owner = cur_ts->owner;
516 if (!owner)
517 break;
518
519 if (!thread_inherit_priority(boosted: owner, from: boosting_from, d: &cur_ts->pi,
520 /* kicks_out = */ NULL))
521 break;
522
523 struct turnstile_wait_snapshot next_wait, cur_wait;
524 if (!turnstile_snapshot_wait(thread: owner, wait: &next_wait))
525 break;
526
527 struct turnstile_hash_chain *next_chain =
528 turnstile_chain_for(obj: next_wait.lock_obj);
529
530 if (next_chain != chain) {
531 turnstile_hash_chain_unlock(chain, irql);
532 chain = next_chain;
533 irql = turnstile_hash_chain_lock(chain);
534 }
535
536 /* Lookup again */
537 cur_ts = turnstile_lookup_internal(obj: next_wait.lock_obj);
538
539 bool ts_valid = cur_ts == next_wait.ts;
540 bool snapshot = turnstile_snapshot_wait(thread: owner, wait: &cur_wait);
541 bool curr_valid = snapshot && cur_wait.ts == cur_ts &&
542 cur_wait.epoch == next_wait.epoch;
543
544 if (!ts_valid || !curr_valid)
545 break;
546
547 turnstile_requeue_waiter(ts: cur_ts, thread: owner);
548
549 boosting_from = owner;
550 }
551
552 if (chain != locked_chain) {
553 turnstile_hash_chain_unlock(chain, irql);
554 irql = turnstile_hash_chain_lock(chain: locked_chain);
555 }
556
557 rcu_read_unlock();
558 return irql;
559}
560
561static void turnstile_block_on(struct turnstile *ts, size_t queue_num) {
562 struct thread *curr = thread_get_current();
563
564 enforce(!atomic_load_acq(&curr->blocked_ts));
565 atomic_store_release(&curr->blocked_ts, ts);
566
567 wroost_pre_wait(curr);
568 thread_wait_prepare_one(header: &ts->wait, object: ts->lock_obj,
569 type: THREAD_WAIT_UNINTERRUPTIBLE,
570 reason: THREAD_BLOCK_REASON_MANUAL);
571
572 curr->wq_prio = turnstile_thread_priority(t: curr);
573 curr->wq_seq = ts->next_wait_seq++;
574 rbt_insert(tree: &ts->queues[queue_num], new_node: &curr->wq_tree_node);
575}
576
577/* ok... the we first assign a turnstile to the lock object,
578 * and then we boost priorities and finally block */
579
580/* we already have preemption off when we get in here */
581struct turnstile *turnstile_block(struct turnstile *ts, size_t queue_num,
582 void *lock_obj, enum irql lock_irql,
583 struct thread *owner) {
584 struct turnstile_hash_chain *chain = turnstile_chain_for(obj: lock_obj);
585 struct thread *current_thread = thread_get_current();
586
587 struct turnstile *my_turnstile = current_thread->turnstile;
588
589 enforce(my_turnstile);
590
591 /* turnstile donation */
592 if (!ts) {
593 /* no turnstile to block on, give it ours */
594 ts = my_turnstile;
595 turnstile_insert(chain, ts, lock_obj);
596 enforce(ts->waiters == 0);
597 } else {
598 /* someone else has donated a turnstile, put ours on the freelist */
599 turnstile_insert_to_freelist(parent: ts, child: my_turnstile);
600 enforce(ts->waiters > 0);
601 enforce(ts->lock_obj == lock_obj);
602 }
603
604 current_thread->turnstile = NULL;
605
606 /* Re-initialize */
607 if (ts->pi.active && ts->pi.target != owner)
608 turnstile_pi_remove(ts);
609
610 ts->owner = owner;
611
612 ts->waiters++;
613
614 turnstile_block_on(ts, queue_num);
615
616 lock_irql = turnstile_propagate_boost(locked_chain: chain, ts, irql: lock_irql);
617
618 turnstile_hash_chain_unlock(chain, irql: lock_irql);
619
620 /* it is the waking thread's job to decrement waiters */
621 thread_wait_complete();
622
623 thread_remove_boost();
624
625 return current_thread->turnstile;
626}
627
628size_t turnstile_get_waiter_count(void *lock_obj) {
629 struct turnstile *ts = turnstile_lookup_internal(obj: lock_obj);
630 return ts ? ts->waiters : 0;
631}
632