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