1#include <kassert.h>
2#include <math/min_max.h>
3#include <mem/alloc.h>
4#include <mem/slab.h> /* to get SLAB_OBJ_ALIGN */
5#include <sch/sched.h>
6#include <sync/turnstile.h>
7#include <thread/thread.h>
8
9#include "mutex_internal.h"
10
11/* LOCK ORDERING: TS -> THREAD */
12
13SLAB_SIZE_REGISTER_FOR_STRUCT(turnstile, SLAB_OBJ_ALIGN_DEFAULT);
14
15/* Implements turnstiles used on synchronization objects
16 *
17 * This uses a strategy similar to later versions of Solaris
18 * and FreeBSD, kudos to all the people who worked on those operating systems!
19 *
20 * Turnstiles give us pointer-sized adaptive mutexes (very good to have).
21 *
22 * Each thread is born with a turnstile (technically, this is still
23 * *slightly* overkill because you need to have a thread to block on to even
24 * use your turnstile, so it ideally would be n_threads/2 turnstiles on the
25 * whole system, but that introduces a non-negligible amount of overhead for the
26 * extra bookkeeping, so we just give each thread one turnstile and call it a
27 * day).
28 *
29 * Whenever a thread blocks on a lock, we first go and check if the lock
30 * already has an entry in the global turnstile hash table. If it is the first
31 * thread to block on the lock (no entry in hash table), then we lend over our
32 * own turnstile and go and block. If the lock already has a turnstile, then we
33 * lend over our turnstile to the freelist of the turnstile that the lock is
34 * associated with.
35 *
36 * When a thread wakes up from the block, it takes a turnstile from the freelist
37 * of the turnstile that it is blocked on. If there are no waiters, then we
38 * don't bother with that and just take the turnstile itself (there would be no
39 * freelist) and remove it from the hash table.
40 *
41 * There is also priority inheritence which is done by walking the list of
42 * blocked threads and taking our current thread's priority and boosting
43 * threads that need the boost.
44 *
45 * The hash table per-head locks protect the hash tables adn contents of all
46 * turnstiles residing in the hash table.
47 */
48
49void turnstiles_init() {
50 global.turnstiles =
51 kmalloc(sizeof(struct turnstile_hash_table), ALLOC_FLAGS_ZERO);
52 if (!global.turnstiles)
53 panic("Could not allocate turnstile hash table");
54 for (size_t i = 0; i < TURNSTILE_HASH_SIZE; i++) {
55 spinlock_init(lock: &global.turnstiles->heads[i].lock);
56 INIT_LIST_HEAD(list: &global.turnstiles->heads[i].list);
57 }
58}
59
60#define TURNSTILE_BACKGROUND_PRIO 1
61#define TURNSTILE_TS_PRIO_BASE 2
62#define TURNSTILE_TS_PRIO_MAX 100000
63#define TURNSTILE_RT_PRIO 100001
64#define TURNSTILE_URGENT_PRIO 100002
65
66static inline enum irql
67turnstile_hash_chain_lock(struct turnstile_hash_chain *chain) {
68 return spin_lock_irq_disable(lock: &chain->lock);
69}
70
71static inline void
72turnstile_hash_chain_unlock(struct turnstile_hash_chain *chain,
73 enum irql irql) {
74 spin_unlock(lock: &chain->lock, old: irql);
75}
76
77int32_t turnstile_thread_priority(struct thread *t) {
78 switch (t->perceived_prio_class) {
79 case THREAD_PRIO_CLASS_BACKGROUND: return TURNSTILE_BACKGROUND_PRIO;
80 case THREAD_PRIO_CLASS_TIMESHARE:
81 return (TURNSTILE_TS_PRIO_BASE + t->weight) > TURNSTILE_TS_PRIO_MAX
82 ? TURNSTILE_TS_PRIO_MAX
83 : TURNSTILE_TS_PRIO_BASE + t->weight;
84 case THREAD_PRIO_CLASS_RT: return TURNSTILE_RT_PRIO;
85 case THREAD_PRIO_CLASS_URGENT: return TURNSTILE_URGENT_PRIO;
86 }
87 kassert_unreachable("thread prio class invalid");
88}
89
90static size_t turnstile_thread_get_data(struct rbt_node *n) {
91 return turnstile_thread_priority(thread_from_wq_rbt_node(n));
92}
93
94static int32_t turnstile_thread_cmp(const struct rbt_node *a,
95 const struct rbt_node *b) {
96 int32_t ta = turnstile_thread_get_data(n: (void *) a);
97 int32_t tb = turnstile_thread_get_data(n: (void *) b);
98 return ta - tb;
99}
100
101struct turnstile *turnstile_init(struct turnstile *ts) {
102 ts->lock_obj = NULL;
103 ts->waiters = 0;
104 ts->state = TURNSTILE_STATE_UNUSED;
105 ts->owner = NULL;
106
107 rbt_init(t: &ts->queues[TURNSTILE_READER_QUEUE], get_data: turnstile_thread_get_data,
108 compare: turnstile_thread_cmp);
109 rbt_init(t: &ts->queues[TURNSTILE_WRITER_QUEUE], get_data: turnstile_thread_get_data,
110 compare: turnstile_thread_cmp);
111 INIT_LIST_HEAD(list: &ts->freelist);
112 INIT_LIST_HEAD(list: &ts->hash_list);
113
114 return ts;
115}
116
117void turnstile_destroy(struct turnstile *ts) {
118 kfree(ts);
119}
120
121struct turnstile *turnstile_create(void) {
122 struct turnstile *ts = kmalloc(sizeof(struct turnstile), ALLOC_FLAGS_ZERO);
123 if (!ts)
124 return NULL;
125
126 return turnstile_init(ts);
127}
128
129static inline struct turnstile_hash_chain *turnstile_chain_for(void *obj) {
130 size_t idx = TURNSTILE_OBJECT_HASH(obj);
131 return &global.turnstiles->heads[idx];
132}
133
134static void turnstile_insert_to_freelist(struct turnstile *parent,
135 struct turnstile *child) {
136 SPINLOCK_ASSERT_HELD(&turnstile_chain_for(parent->lock_obj)->lock);
137 list_add_tail(new: &child->freelist, head: &parent->freelist);
138 child->state = TURNSTILE_STATE_IN_FREE_LIST;
139}
140
141static struct turnstile *turnstile_freelist_pop(struct turnstile *ts) {
142 struct list_head *lh = list_pop_front_init(head: &ts->freelist);
143 kassert(lh); /* we are not to call this if the freelist is empty */
144 struct turnstile *ret = turnstile_from_freelist(lh);
145 ret->state = TURNSTILE_STATE_UNUSED;
146 return ret;
147}
148
149static void turnstile_insert(struct turnstile_hash_chain *chain,
150 struct turnstile *ts, void *lock_obj) {
151 SPINLOCK_ASSERT_HELD(&chain->lock);
152 list_add_tail(new: &chain->list, head: &ts->hash_list);
153 ts->state = TURNSTILE_STATE_IN_HASH_TABLE;
154 ts->lock_obj = lock_obj;
155}
156
157static void turnstile_remove(struct turnstile_hash_chain *chain,
158 struct turnstile *ts) {
159 SPINLOCK_ASSERT_HELD(&chain->lock);
160 list_del_init(entry: &ts->hash_list);
161 ts->state = TURNSTILE_STATE_UNUSED;
162 ts->lock_obj = NULL;
163}
164
165struct turnstile *turnstile_lookup_internal(void *obj) {
166 struct turnstile_hash_chain *chain = turnstile_chain_for(obj);
167 struct list_head *pos;
168
169 struct turnstile *ts = NULL;
170 list_for_each(pos, &chain->list) {
171 if ((ts = turnstile_from_hash_list_node(pos))->lock_obj == obj)
172 goto out;
173 }
174
175out:
176 return ts;
177}
178
179struct turnstile *turnstile_lookup(void *obj, enum irql *irql_out) {
180 struct turnstile_hash_chain *chain = turnstile_chain_for(obj);
181
182 enum irql irql = turnstile_hash_chain_lock(chain);
183 struct list_head *pos;
184 struct turnstile *ts = NULL;
185
186 list_for_each(pos, &chain->list) {
187 if ((ts = turnstile_from_hash_list_node(pos))->lock_obj == obj)
188 goto out;
189 }
190
191out:
192 *irql_out = irql;
193 return ts;
194}
195
196void turnstile_pi_remove(struct turnstile *ts) {
197 if (ts->applied_pi_boost)
198 thread_uninherit_priority(class: ts->prio_class);
199
200 ts->prio_class = 0;
201 ts->applied_pi_boost = false;
202}
203
204struct thread *turnstile_dequeue_first(struct turnstile *ts, size_t queue) {
205 void *obj = ts->lock_obj;
206 struct turnstile_hash_chain *chain = turnstile_chain_for(obj);
207
208 struct rbt_node *last = rbt_last(root: &ts->queues[queue]);
209 rbt_delete(tree: &ts->queues[queue], z: last);
210 struct thread *thread = thread_from_wq_rbt_node(last);
211
212 struct turnstile *got = ts;
213 if (ts->waiters == 1) { /* last waiter, take the turnstile with you! */
214 /* you're taking the turnstile */
215 kassert(list_empty(&ts->freelist));
216 turnstile_remove(chain, ts);
217 } else {
218 /* not the last waiter, take one from the freelist */
219 kassert(!list_empty(&ts->freelist));
220 got = turnstile_freelist_pop(ts);
221 kassert(got);
222 }
223
224 /* you take this turnstile with you as you wake up please */
225 thread->turnstile = got;
226
227 /* you are no longer blocked on a lock */
228 atomic_store(&thread->blocked_ts, NULL);
229
230 /* you are also no longer a waiter */
231 ts->waiters--;
232 return thread;
233}
234
235void turnstile_wake(struct turnstile *ts, size_t queue, size_t num_threads,
236 enum irql lock_irql) {
237 /* remove from hash */
238 void *obj = ts->lock_obj;
239 struct turnstile_hash_chain *chain = turnstile_chain_for(obj);
240
241 /* un-inherit the priority we inherited */
242 turnstile_pi_remove(ts);
243
244 /* yo, wake up */
245 while (num_threads-- > 0) {
246 /* wake the one of highest priority */
247 struct thread *to_wake = turnstile_dequeue_first(ts, queue);
248 thread_wake(t: to_wake, reason: THREAD_WAKE_REASON_BLOCKING_MANUAL,
249 prio: to_wake->perceived_prio_class, wake_src: ts);
250 }
251
252 ts->owner = NULL;
253 turnstile_hash_chain_unlock(chain, irql: lock_irql);
254}
255
256void turnstile_unlock(void *obj, enum irql irql) {
257 struct turnstile_hash_chain *chain = turnstile_chain_for(obj);
258 turnstile_hash_chain_unlock(chain, irql);
259}
260
261void turnstile_propagate_boost(struct turnstile_hash_chain *locked_chain,
262 struct turnstile *ts) {
263 struct turnstile *cur_ts = ts;
264 struct thread *owner = NULL, *boosting_from = thread_get_current();
265
266 while (cur_ts) {
267 struct turnstile_hash_chain *chain =
268 turnstile_chain_for(obj: cur_ts->lock_obj);
269
270 enum irql irql = IRQL_PASSIVE_LEVEL;
271 bool unlock = false;
272
273 if (chain != locked_chain) {
274 irql = turnstile_hash_chain_lock(chain);
275 unlock = true;
276 }
277
278 owner = cur_ts->owner;
279 if (!owner) {
280 if (unlock)
281 turnstile_hash_chain_unlock(chain, irql);
282 break;
283 }
284
285 /* Apply inheritance */
286 if (!thread_inherit_priority(boosted: owner, from: boosting_from, NULL)) {
287 if (unlock)
288 turnstile_hash_chain_unlock(chain, irql);
289 break;
290 }
291
292 cur_ts->applied_pi_boost = true;
293
294 /* Speculative next hop */
295 struct turnstile *next = atomic_load(&owner->blocked_ts);
296
297 if (unlock)
298 turnstile_hash_chain_unlock(chain, irql);
299
300 /* Revalidation step */
301 if (!next)
302 break;
303
304 struct turnstile_hash_chain *next_chain =
305 turnstile_chain_for(obj: next->lock_obj);
306
307 enum irql nirql = turnstile_hash_chain_lock(chain: next_chain);
308
309 if (owner->blocked_ts != next || next->owner != owner) {
310 turnstile_hash_chain_unlock(chain: next_chain, irql: nirql);
311 break;
312 }
313
314 /* Prepare next iteration */
315 boosting_from = owner;
316
317 turnstile_hash_chain_unlock(chain: next_chain, irql: nirql);
318 cur_ts = next;
319 }
320}
321
322static void turnstile_block_on(struct turnstile *ts, size_t queue_num) {
323 struct thread *curr = thread_get_current();
324
325 atomic_store(&curr->blocked_ts, ts);
326
327 thread_prepare_to_block(t: curr, r: THREAD_BLOCK_REASON_MANUAL,
328 wait_type: THREAD_WAIT_UNINTERRUPTIBLE, expect_wake_src: ts);
329
330 rbt_insert(tree: &ts->queues[queue_num], new_node: &curr->wq_tree_node);
331}
332
333/* ok... the we first assign a turnstile to the lock object,
334 * and then we boost priorities and finally block */
335
336/* we already have preemption off when we get in here */
337struct turnstile *turnstile_block(struct turnstile *ts, size_t queue_num,
338 void *lock_obj, enum irql lock_irql,
339 struct thread *owner) {
340 struct turnstile_hash_chain *chain = turnstile_chain_for(obj: lock_obj);
341 struct thread *current_thread = thread_get_current();
342
343 struct turnstile *my_turnstile = current_thread->turnstile;
344
345 kassert(my_turnstile);
346
347 /* turnstile donation */
348 if (!ts) {
349 /* no turnstile to block on, give it ours */
350 ts = my_turnstile;
351 turnstile_insert(chain, ts, lock_obj);
352 kassert(ts->waiters == 0);
353 } else {
354 /* someone else has donated a turnstile, put ours on the freelist */
355 turnstile_insert_to_freelist(parent: ts, child: my_turnstile);
356 kassert(ts->waiters > 0);
357 kassert(ts->lock_obj == lock_obj);
358 }
359
360 current_thread->turnstile = NULL;
361 ts->owner = owner;
362
363 turnstile_propagate_boost(locked_chain: chain, ts);
364
365 ts->waiters++;
366
367 turnstile_block_on(ts, queue_num);
368
369 turnstile_hash_chain_unlock(chain, irql: lock_irql);
370
371 /* it is the waking thread's job to decrement waiters and
372 * mark me as no longer being blocked on the lock object */
373 thread_yield_until_wake_match();
374
375 thread_remove_boost();
376
377 return ts;
378}
379
380size_t turnstile_get_waiter_count(void *lock_obj) {
381 size_t count = 0;
382 struct turnstile *ts = turnstile_lookup_internal(obj: lock_obj);
383 if (ts)
384 count = ts->waiters;
385
386 return count;
387}
388