1/*
2 * Copyright (c) 2017-2020 Apple Inc. All rights reserved.
3 *
4 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
5 *
6 * This file contains Original Code and/or Modifications of Original Code
7 * as defined in and that are subject to the Apple Public Source License
8 * Version 2.0 (the 'License'). You may not use this file except in
9 * compliance with the License. The rights granted to you under the License
10 * may not be used to create, or enable the creation or redistribution of,
11 * unlawful or unlicensed copies of an Apple operating system, or to
12 * circumvent, violate, or enable the circumvention or violation of, any
13 * terms of an Apple operating system software license agreement.
14 *
15 * Please obtain a copy of the License at
16 * http://www.opensource.apple.com/apsl/ and read it before using this file.
17 *
18 * The Original Code and all software distributed under the License are
19 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
20 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
21 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
22 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
23 * Please see the License for the specific language governing rights and
24 * limitations under the License.
25 *
26 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
27 */
28
29#include <kern/turnstile.h>
30#include <kern/cpu_data.h>
31#include <kern/mach_param.h>
32#include <kern/kern_types.h>
33#include <kern/assert.h>
34#include <kern/kalloc.h>
35#include <kern/thread.h>
36#include <kern/clock.h>
37#include <kern/policy_internal.h>
38#include <kern/task.h>
39#include <kern/waitq.h>
40#include <kern/sched_prim.h>
41#include <kern/zalloc.h>
42#include <kern/debug.h>
43#include <kern/compact_id.h>
44#include <machine/limits.h>
45#include <machine/atomic.h>
46
47#include <pexpert/pexpert.h>
48#include <os/hash.h>
49#include <libkern/section_keywords.h>
50
51static TUNABLE(int, turnstile_max_hop, "turnstile_max_hop", TURNSTILE_MAX_HOP_DEFAULT);
52COMPACT_ID_TABLE_DEFINE(static, ctsid_table);
53static_assert(CTSID_MAX <= COMPACT_ID_MAX);
54static SECURITY_READ_ONLY_LATE(uint32_t) ctsid_nonce;
55
56ZONE_DEFINE_ID(ZONE_ID_TURNSTILE, "turnstiles", struct turnstile,
57 ZC_ZFREE_CLEARMEM);
58
59static struct mpsc_daemon_queue turnstile_deallocate_queue;
60#define TURNSTILES_CHUNK (THREAD_CHUNK)
61
62/* Global table for turnstile promote policy for all type of turnstiles */
63static const turnstile_promote_policy_t turnstile_promote_policy[TURNSTILE_TOTAL_TYPES] = {
64 [TURNSTILE_NONE] = TURNSTILE_PROMOTE_NONE,
65 [TURNSTILE_KERNEL_MUTEX] = TURNSTILE_KERNEL_PROMOTE,
66 [TURNSTILE_ULOCK] = TURNSTILE_USER_PROMOTE,
67 [TURNSTILE_PTHREAD_MUTEX] = TURNSTILE_USER_PROMOTE,
68 [TURNSTILE_SYNC_IPC] = TURNSTILE_USER_IPC_PROMOTE,
69 [TURNSTILE_WORKLOOPS] = TURNSTILE_USER_IPC_PROMOTE,
70 [TURNSTILE_WORKQS] = TURNSTILE_USER_IPC_PROMOTE,
71 [TURNSTILE_KNOTE] = TURNSTILE_USER_IPC_PROMOTE,
72 [TURNSTILE_SLEEP_INHERITOR] = TURNSTILE_KERNEL_PROMOTE,
73 [TURNSTILE_EPOCH_KERNEL] = TURNSTILE_KERNEL_PROMOTE,
74 [TURNSTILE_EPOCH_USER] = TURNSTILE_USER_PROMOTE,
75};
76
77/* Global table for turnstile hash lock policy for all type of turnstiles */
78static const turnstile_hash_lock_policy_t turnstile_hash_lock_policy[TURNSTILE_TOTAL_TYPES] = {
79 [TURNSTILE_NONE] = TURNSTILE_HASH_LOCK_POLICY_NONE,
80 [TURNSTILE_KERNEL_MUTEX] = TURNSTILE_HASH_LOCK_POLICY_NONE,
81 [TURNSTILE_ULOCK] = TURNSTILE_HASH_LOCK_POLICY_NONE,
82 [TURNSTILE_PTHREAD_MUTEX] = TURNSTILE_HASH_LOCK_POLICY_NONE,
83 [TURNSTILE_SYNC_IPC] = TURNSTILE_HASH_LOCK_POLICY_NONE,
84 [TURNSTILE_WORKLOOPS] = TURNSTILE_HASH_LOCK_POLICY_NONE,
85 [TURNSTILE_WORKQS] = TURNSTILE_HASH_LOCK_POLICY_NONE,
86 [TURNSTILE_KNOTE] = TURNSTILE_HASH_LOCK_POLICY_NONE,
87 [TURNSTILE_SLEEP_INHERITOR] = (TURNSTILE_IRQ_UNSAFE_HASH | TURNSTILE_LOCKED_HASH),
88 [TURNSTILE_EPOCH_KERNEL] = TURNSTILE_HASH_LOCK_POLICY_NONE,
89 [TURNSTILE_EPOCH_USER] = TURNSTILE_HASH_LOCK_POLICY_NONE,
90};
91
92os_refgrp_decl(static, turnstile_refgrp, "turnstile", NULL);
93
94#if DEVELOPMENT || DEBUG
95static LCK_GRP_DECLARE(turnstiles_dev_lock_grp, "turnstile_dev_lock");
96
97/* Array to store stats for multi-hop boosting */
98static struct turnstile_stats turnstile_boost_stats[TURNSTILE_MAX_HOP_DEFAULT] = {};
99static struct turnstile_stats turnstile_unboost_stats[TURNSTILE_MAX_HOP_DEFAULT] = {};
100uint64_t thread_block_on_turnstile_count;
101uint64_t thread_block_on_regular_waitq_count;
102#endif /* DEVELOPMENT || DEBUG */
103
104#ifndef max
105#define max(a, b) (((a) > (b)) ? (a) : (b))
106#endif /* max */
107
108/* Static function declarations */
109static turnstile_type_t
110turnstile_get_type(struct turnstile *turnstile);
111static bool
112turnstile_is_send_turnstile(struct turnstile *turnstile);
113static uint32_t
114turnstile_get_gencount(struct turnstile *turnstile);
115static void
116turnstile_set_type_and_increment_gencount(struct turnstile *turnstile, turnstile_type_t type);
117static void
118turnstile_destroy(struct turnstile *turnstile);
119static void
120turnstile_update_inheritor_workq_priority_chain(struct turnstile *in_turnstile, spl_t s);
121static void
122turnstile_update_inheritor_thread_priority_chain(struct turnstile **in_turnstile,
123 thread_t *out_thread, int total_hop, turnstile_stats_update_flags_t tsu_flags);
124static void
125turnstile_update_inheritor_turnstile_priority_chain(struct turnstile **in_out_turnstile,
126 int total_hop, turnstile_stats_update_flags_t tsu_flags);
127static void
128thread_update_waiting_turnstile_priority_chain(thread_t *in_thread,
129 struct turnstile **out_turnstile, int thread_hop, int total_hop,
130 turnstile_stats_update_flags_t tsu_flags);
131static boolean_t
132turnstile_update_turnstile_promotion_locked(struct turnstile *dst_turnstile,
133 struct turnstile *src_turnstile);
134static boolean_t
135turnstile_update_turnstile_promotion(struct turnstile *dst_turnstile,
136 struct turnstile *src_turnstile);
137static boolean_t
138turnstile_need_turnstile_promotion_update(struct turnstile *dst_turnstile,
139 struct turnstile *src_turnstile);
140static boolean_t
141turnstile_add_turnstile_promotion(struct turnstile *dst_turnstile,
142 struct turnstile *src_turnstile);
143static boolean_t
144turnstile_remove_turnstile_promotion(struct turnstile *dst_turnstile,
145 struct turnstile *src_turnstile);
146static boolean_t
147turnstile_update_thread_promotion_locked(struct turnstile *dst_turnstile,
148 thread_t thread);
149static boolean_t
150turnstile_need_thread_promotion_update(struct turnstile *dst_turnstile,
151 thread_t thread);
152static boolean_t
153thread_add_turnstile_promotion(
154 thread_t thread, struct turnstile *turnstile);
155static boolean_t
156thread_remove_turnstile_promotion(
157 thread_t thread, struct turnstile *turnstile);
158static boolean_t
159thread_needs_turnstile_promotion_update(thread_t thread,
160 struct turnstile *turnstile);
161static boolean_t
162thread_update_turnstile_promotion(
163 thread_t thread, struct turnstile *turnstile);
164static boolean_t
165thread_update_turnstile_promotion_locked(
166 thread_t thread, struct turnstile *turnstile);
167static boolean_t
168workq_add_turnstile_promotion(
169 struct workqueue *wq_inheritor, struct turnstile *turnstile);
170static turnstile_stats_update_flags_t
171thread_get_update_flags_for_turnstile_propagation_stoppage(thread_t thread);
172static turnstile_stats_update_flags_t
173turnstile_get_update_flags_for_above_UI_pri_change(struct turnstile *turnstile);
174static void turnstile_stash_inheritor(turnstile_inheritor_t new_inheritor,
175 turnstile_update_flags_t flags);
176static int turnstile_compute_thread_push(struct turnstile *turnstile, thread_t thread);
177
178#if DEVELOPMENT || DEBUG
179/* Test primitives and interfaces for testing turnstiles */
180struct tstile_test_prim {
181 struct turnstile *ttprim_turnstile;
182 thread_t ttprim_owner;
183 lck_spin_t ttprim_interlock;
184 uint32_t tt_prim_waiters;
185};
186
187struct tstile_test_prim test_prim_ts_inline;
188struct tstile_test_prim test_prim_global_htable;
189struct tstile_test_prim test_prim_global_ts_kernel;
190struct tstile_test_prim test_prim_global_ts_kernel_hash;
191
192static void
193tstile_test_prim_init(struct tstile_test_prim *test_prim_ptr);
194#endif
195
196union turnstile_type_gencount {
197 uint32_t value;
198 struct {
199 uint32_t ts_type:(8 * sizeof(turnstile_type_t)),
200 ts_gencount: (8 * (sizeof(uint32_t) - sizeof(turnstile_type_t)));
201 };
202};
203
204static turnstile_type_t
205turnstile_get_type(struct turnstile *turnstile)
206{
207 union turnstile_type_gencount type_and_gencount;
208
209 type_and_gencount.value = atomic_load_explicit(&turnstile->ts_type_gencount, memory_order_relaxed);
210 return (turnstile_type_t) type_and_gencount.ts_type;
211}
212
213/* Only safe to be called from stackshot context */
214static bool
215turnstile_is_send_turnstile(struct turnstile *turnstile)
216{
217 if (not_in_kdp) {
218 panic("turnstile_is_send_turnstile() called outside of kernel debugger context");
219 }
220
221 if (turnstile_get_type(turnstile) == TURNSTILE_SYNC_IPC) {
222 ipc_port_t port = (ipc_port_t) turnstile->ts_proprietor;
223
224 return port_send_turnstile(port) == turnstile;
225 }
226
227 return false;
228}
229
230/* Only safe to be called from stackshot context */
231static bool
232turnstile_is_receive_turnstile(struct turnstile *turnstile)
233{
234 if (not_in_kdp) {
235 panic("turnstile_is_receive_turnstile() called outside of kernel debugger context");
236 }
237
238 if (turnstile_get_type(turnstile) == TURNSTILE_SYNC_IPC) {
239 ipc_port_t port = (ipc_port_t) turnstile->ts_proprietor;
240
241 return *port_rcv_turnstile_address(port) == turnstile;
242 }
243
244 return false;
245}
246
247static uint32_t
248turnstile_get_gencount(struct turnstile *turnstile)
249{
250 union turnstile_type_gencount type_and_gencount;
251
252 type_and_gencount.value = atomic_load_explicit(&turnstile->ts_type_gencount, memory_order_relaxed);
253 return (uint32_t) type_and_gencount.ts_gencount;
254}
255
256static void
257turnstile_set_type_and_increment_gencount(struct turnstile *turnstile, turnstile_type_t type)
258{
259 union turnstile_type_gencount type_and_gencount;
260
261 /* No need to compare exchange since the store happens under interlock of the primitive */
262 type_and_gencount.value = atomic_load_explicit(&turnstile->ts_type_gencount, memory_order_relaxed);
263 type_and_gencount.ts_type = type;
264 type_and_gencount.ts_gencount++;
265 atomic_store_explicit(&turnstile->ts_type_gencount, type_and_gencount.value, memory_order_relaxed);
266}
267
268
269/* Turnstile hashtable Implementation */
270
271/*
272 * Maximum number of buckets in the turnstile hashtable. This number affects the
273 * performance of the hashtable since it determines the hash collision
274 * rate. To experiment with the number of buckets in this hashtable use the
275 * "ts_htable_buckets" boot-arg.
276 */
277#define TURNSTILE_HTABLE_BUCKETS_DEFAULT 32
278#define TURNSTILE_HTABLE_BUCKETS_MAX 1024
279
280SLIST_HEAD(turnstile_hashlist, turnstile);
281
282struct turnstile_htable_bucket {
283 lck_spin_t ts_ht_bucket_lock;
284 struct turnstile_hashlist ts_ht_bucket_list;
285};
286
287SECURITY_READ_ONLY_LATE(static uint32_t) ts_htable_buckets;
288/* Global hashtable for turnstiles managed with interrupts disabled */
289SECURITY_READ_ONLY_LATE(static struct turnstile_htable_bucket *)turnstile_htable_irq_safe;
290/* Global hashtable for turnstiles managed with interrupts enabled */
291SECURITY_READ_ONLY_LATE(static struct turnstile_htable_bucket *)turnstile_htable;
292
293
294/* Bucket locks for turnstile hashtable */
295LCK_GRP_DECLARE(turnstiles_htable_lock_grp, "turnstiles_htable_locks");
296
297#define turnstile_bucket_lock_init(bucket) \
298 lck_spin_init(&bucket->ts_ht_bucket_lock, &turnstiles_htable_lock_grp, LCK_ATTR_NULL)
299#define turnstile_bucket_lock(bucket) \
300 lck_spin_lock_grp(&bucket->ts_ht_bucket_lock, &turnstiles_htable_lock_grp)
301#define turnstile_bucket_unlock(bucket) \
302 lck_spin_unlock(&bucket->ts_ht_bucket_lock)
303
304#define kdp_turnstile_bucket_is_locked(bucket) \
305 kdp_lck_spin_is_acquired(&bucket->ts_ht_bucket_lock)
306
307/*
308 * Name: turnstiles_hashtable_init
309 *
310 * Description: Initializes the global turnstile hash table.
311 *
312 * Args:
313 * None
314 *
315 * Returns:
316 * None
317 */
318static void
319turnstiles_hashtable_init(void)
320{
321 /* Initialize number of buckets in the hashtable */
322 if (PE_parse_boot_argn(arg_string: "ts_htable_buckets", arg_ptr: &ts_htable_buckets, max_arg: sizeof(ts_htable_buckets)) != TRUE) {
323 ts_htable_buckets = TURNSTILE_HTABLE_BUCKETS_DEFAULT;
324 }
325
326 assert(ts_htable_buckets <= TURNSTILE_HTABLE_BUCKETS_MAX);
327 uint32_t ts_htable_size = ts_htable_buckets * sizeof(struct turnstile_htable_bucket);
328 turnstile_htable_irq_safe = zalloc_permanent(ts_htable_size, ZALIGN_PTR);
329 if (turnstile_htable_irq_safe == NULL) {
330 panic("Turnstiles hash table memory allocation failed!");
331 }
332
333 turnstile_htable = zalloc_permanent(ts_htable_size, ZALIGN_PTR);
334 if (turnstile_htable == NULL) {
335 panic("Turnstiles hash table memory allocation failed!");
336 }
337
338 /* Initialize all the buckets of the hashtables */
339 for (uint32_t i = 0; i < ts_htable_buckets; i++) {
340 struct turnstile_htable_bucket *ts_bucket = &(turnstile_htable_irq_safe[i]);
341 turnstile_bucket_lock_init(ts_bucket);
342 SLIST_INIT(&ts_bucket->ts_ht_bucket_list);
343
344 ts_bucket = &(turnstile_htable[i]);
345 turnstile_bucket_lock_init(ts_bucket);
346 SLIST_INIT(&ts_bucket->ts_ht_bucket_list);
347 }
348}
349
350/*
351 * Name: turnstile_freelist_empty
352 *
353 * Description: Checks if the turnstile's freelist is empty
354 * Should be called with the primitive IL held.
355 *
356 * Args:
357 * Arg1: turnstile
358 *
359 * Returns:
360 * true if freelist is empty; false otherwise
361 */
362static inline boolean_t
363turnstile_freelist_empty(
364 struct turnstile *ts)
365{
366 return SLIST_EMPTY(&ts->ts_free_turnstiles);
367}
368
369
370/*
371 * Name: turnstile_freelist_insert
372 *
373 * Description: Inserts the turnstile into the freelist of another turnstile
374 * Should be called with the primitive IL held.
375 *
376 * Args:
377 * Arg1: primitive turnstile
378 * Arg2: turnstile to add to the freelist
379 *
380 * Returns:
381 * None
382 */
383static void
384turnstile_freelist_insert(
385 struct turnstile *dst_ts,
386 struct turnstile *free_ts)
387{
388 assert(turnstile_get_type(dst_ts) == turnstile_get_type(free_ts));
389 assert(dst_ts->ts_proprietor == free_ts->ts_proprietor);
390 turnstile_state_add(free_ts, TURNSTILE_STATE_FREELIST);
391 SLIST_INSERT_HEAD(&dst_ts->ts_free_turnstiles, free_ts, ts_free_elm);
392}
393
394/*
395 * Name: turnstile_freelist_remove
396 *
397 * Description: Removes a turnstile from the freelist of a turnstile
398 * Should be called with the primitive IL held.
399 *
400 * Args:
401 * Arg1: primitive turnstile
402 *
403 * Returns:
404 * turnstile removed from the freelist
405 */
406static struct turnstile *
407turnstile_freelist_remove(
408 struct turnstile *ts)
409{
410 struct turnstile *ret_turnstile = TURNSTILE_NULL;
411 assert(!SLIST_EMPTY(&ts->ts_free_turnstiles));
412 ret_turnstile = SLIST_FIRST(&ts->ts_free_turnstiles);
413 SLIST_REMOVE_HEAD(&ts->ts_free_turnstiles, ts_free_elm);
414 assert(ret_turnstile != TURNSTILE_NULL);
415 turnstile_state_remove(ret_turnstile, TURNSTILE_STATE_FREELIST);
416 /* Need to initialize the list again, since head and elm are in union */
417 SLIST_INIT(&ret_turnstile->ts_free_turnstiles);
418 return ret_turnstile;
419}
420
421/*
422 * Name: turnstile_hash
423 *
424 * Description: Calculates the hash bucket index for a given proprietor
425 *
426 * Args:
427 * Arg1: proprietor (key) for hashing
428 *
429 * Returns:
430 * hash table bucket index for provided proprietor
431 */
432static inline uint32_t
433turnstile_hash(uintptr_t proprietor)
434{
435 uint32_t hash = os_hash_kernel_pointer(pointer: (void *)proprietor);
436 return hash & (ts_htable_buckets - 1);
437}
438
439static inline struct turnstile_htable_bucket *
440turnstile_get_bucket(uint32_t index, turnstile_type_t type)
441{
442 struct turnstile_htable_bucket *ts_bucket;
443 int hash_policy = turnstile_hash_lock_policy[type];
444
445 if (hash_policy & TURNSTILE_IRQ_UNSAFE_HASH) {
446 ts_bucket = &(turnstile_htable[index]);
447 } else {
448 ts_bucket = &(turnstile_htable_irq_safe[index]);
449 }
450
451 return ts_bucket;
452}
453
454/*
455 * Name: turnstile_hash_bucket_lock
456 *
457 * Description: locks the spinlock associated with proprietor's bucket.
458 * if proprietor is specified the index for the hash will be
459 * recomputed and returned in index_proprietor,
460 * otherwise the value save in index_proprietor is used as index.
461 *
462 * Args:
463 * Arg1: proprietor (key) for hashing
464 * Arg2: index for proprietor in the hash
465 * Arg3: turnstile type
466 *
467 * Returns: old value of irq if irq were disabled before acquiring the lock.
468 */
469unsigned
470turnstile_hash_bucket_lock(uintptr_t proprietor, uint32_t *index_proprietor, turnstile_type_t type)
471{
472 struct turnstile_htable_bucket *ts_bucket;
473 int hash_policy = turnstile_hash_lock_policy[type];
474 bool irq_safe = !(hash_policy & TURNSTILE_IRQ_UNSAFE_HASH);
475 spl_t ret = 0;
476 uint32_t index;
477
478 /*
479 * If the proprietor is specified, the caller doesn't know
480 * the index in the hash, so compute it.
481 * Otherwise use the value of index provided.
482 */
483 if (proprietor) {
484 index = turnstile_hash(proprietor);
485 *index_proprietor = index;
486 } else {
487 index = *index_proprietor;
488 }
489
490 ts_bucket = turnstile_get_bucket(index, type);
491
492 if (irq_safe) {
493 ret = splsched();
494 }
495
496 turnstile_bucket_lock(ts_bucket);
497
498 return ret;
499}
500
501/*
502 * Name: turnstile_hash_bucket_unlock
503 *
504 * Description: unlocks the spinlock associated with proprietor's bucket.
505 * if proprietor is specified the index for the hash will be
506 * recomputed and returned in index_proprietor,
507 * otherwise the value save in index_proprietor is used as index.
508 *
509 * Args:
510 * Arg1: proprietor (key) for hashing
511 * Arg2: index for proprietor in the hash
512 * Arg3: turnstile type
513 * Arg4: irq value returned by turnstile_hash_bucket_lock
514 *
515 */
516void
517turnstile_hash_bucket_unlock(uintptr_t proprietor, uint32_t *index_proprietor, turnstile_type_t type, unsigned s)
518{
519 struct turnstile_htable_bucket *ts_bucket;
520 int hash_policy = turnstile_hash_lock_policy[type];
521 bool irq_safe = !(hash_policy & TURNSTILE_IRQ_UNSAFE_HASH);
522 uint32_t index;
523
524 /*
525 * If the proprietor is specified, the caller doesn't know
526 * the index in the hash, so compute it.
527 * Otherwise use the value of index provided.
528 */
529 if (proprietor) {
530 index = turnstile_hash(proprietor);
531 *index_proprietor = index;
532 } else {
533 index = *index_proprietor;
534 }
535 ts_bucket = turnstile_get_bucket(index, type);
536
537 turnstile_bucket_unlock(ts_bucket);
538 if (irq_safe) {
539 splx(s);
540 }
541}
542
543/*
544 * Name: turnstile_htable_lookup_add
545 *
546 * Description: Lookup the proprietor in the global turnstile hash table.
547 * If an entry is present, add the new turnstile to the entry's freelist.
548 * Otherwise add the passed in turnstile for that proprietor.
549 * The routine assumes that the turnstile->proprietor does not change
550 * while the turnstile is in the global hash table.
551 *
552 * Args:
553 * Arg1: proprietor
554 * Arg2: new turnstile for primitive
555 * Arg3: turnstile_type_t type
556 *
557 * Returns:
558 * Previous turnstile for proprietor in the hash table
559 */
560static struct turnstile *
561turnstile_htable_lookup_add(
562 uintptr_t proprietor,
563 struct turnstile *new_turnstile,
564 turnstile_type_t type)
565{
566 uint32_t index = turnstile_hash(proprietor);
567 assert(index < ts_htable_buckets);
568 struct turnstile_htable_bucket *ts_bucket;
569 int hash_policy = turnstile_hash_lock_policy[type];
570 bool needs_lock = !(hash_policy & TURNSTILE_LOCKED_HASH);
571 bool irq_safe = !(hash_policy & TURNSTILE_IRQ_UNSAFE_HASH);
572 spl_t s;
573
574 ts_bucket = turnstile_get_bucket(index, type);
575
576 if (needs_lock) {
577 if (irq_safe) {
578 s = splsched();
579 }
580 turnstile_bucket_lock(ts_bucket);
581 }
582
583 struct turnstile *ts;
584
585 SLIST_FOREACH(ts, &ts_bucket->ts_ht_bucket_list, ts_htable_link) {
586 if (ts->ts_proprietor == proprietor) {
587 /*
588 * Found an entry in the hashtable for this proprietor; add thread turnstile to freelist
589 * and return this turnstile
590 */
591 if (needs_lock) {
592 turnstile_bucket_unlock(ts_bucket);
593 if (irq_safe) {
594 splx(s);
595 }
596 }
597 turnstile_freelist_insert(dst_ts: ts, free_ts: new_turnstile);
598 return ts;
599 }
600 }
601
602 /* No entry for this proprietor; add the new turnstile in the hash table */
603 SLIST_INSERT_HEAD(&ts_bucket->ts_ht_bucket_list, new_turnstile, ts_htable_link);
604 turnstile_state_add(new_turnstile, TURNSTILE_STATE_HASHTABLE);
605 if (needs_lock) {
606 turnstile_bucket_unlock(ts_bucket);
607 if (irq_safe) {
608 splx(s);
609 }
610 }
611 /* Since there was no previous entry for this proprietor, return TURNSTILE_NULL */
612 return TURNSTILE_NULL;
613}
614
615/*
616 * Name: turnstable_htable_lookup_remove
617 *
618 * Description: Lookup the proprietor in the global turnstile hash table.
619 * For the turnstile in the hash table, if the freelist has turnstiles on it
620 * return one of them from the freelist. Otherwise remove the turnstile from
621 * the hashtable and return that.
622 * The routine assumes that the turnstile->proprietor does not change
623 * while the turnstile is in the global hash table.
624 *
625 * Args:
626 * Arg1: proprietor
627 * Arg2: free turnstile to be returned
628 * Arg3: turnstile_type_t type
629 *
630 * Returns:
631 * turnstile for this proprietor in the hashtable after the removal
632 */
633static struct turnstile *
634turnstable_htable_lookup_remove(
635 uintptr_t proprietor,
636 struct turnstile **free_turnstile,
637 turnstile_type_t type)
638{
639 uint32_t index = turnstile_hash(proprietor);
640 assert(index < ts_htable_buckets);
641 struct turnstile_htable_bucket *ts_bucket;
642 struct turnstile *ret_turnstile = TURNSTILE_NULL;
643 int hash_policy = turnstile_hash_lock_policy[type];
644 bool needs_lock = !(hash_policy & TURNSTILE_LOCKED_HASH);
645 bool irq_safe = !(hash_policy & TURNSTILE_IRQ_UNSAFE_HASH);
646 spl_t s;
647
648 ts_bucket = turnstile_get_bucket(index, type);
649
650 if (needs_lock) {
651 if (irq_safe) {
652 s = splsched();
653 }
654 turnstile_bucket_lock(ts_bucket);
655 }
656
657 struct turnstile *ts, **prev_tslink;
658 /* Find the turnstile for the given proprietor in the hashtable */
659 SLIST_FOREACH_PREVPTR(ts, prev_tslink, &ts_bucket->ts_ht_bucket_list, ts_htable_link) {
660 if (ts->ts_proprietor == proprietor) {
661 ret_turnstile = ts;
662 break;
663 }
664 }
665 assert(ret_turnstile != TURNSTILE_NULL);
666
667 /* Check if the turnstile has any turnstiles on its freelist */
668 if (turnstile_freelist_empty(ts: ret_turnstile)) {
669 /* No turnstiles on the freelist; remove the turnstile from the hashtable and mark it freed */
670 *prev_tslink = SLIST_NEXT(ret_turnstile, ts_htable_link);
671 turnstile_state_remove(ret_turnstile, TURNSTILE_STATE_HASHTABLE);
672 if (needs_lock) {
673 turnstile_bucket_unlock(ts_bucket);
674 if (irq_safe) {
675 splx(s);
676 }
677 }
678 *free_turnstile = ret_turnstile;
679 return TURNSTILE_NULL;
680 } else {
681 /*
682 * Turnstile has free turnstiles on its list; leave the hashtable unchanged
683 * and return the first turnstile in the freelist as the free turnstile
684 */
685 if (needs_lock) {
686 turnstile_bucket_unlock(ts_bucket);
687 if (irq_safe) {
688 splx(s);
689 }
690 }
691 *free_turnstile = turnstile_freelist_remove(ts: ret_turnstile);
692 return ret_turnstile;
693 }
694}
695
696/*
697 * Name: turnstile_htable_lookup
698 *
699 * Description: Lookup the proprietor in the global turnstile hash table.
700 * The routine assumes that the turnstile->proprietor does not change
701 * while the turnstile is in the global hash table.
702 *
703 * Args:
704 * Arg1: proprietor
705 * Arg2: turnstile_type_t type
706 *
707 * Returns:
708 * Turnstile for proprietor in the hash table
709 */
710static struct turnstile *
711turnstile_htable_lookup(
712 uintptr_t proprietor,
713 turnstile_type_t type)
714{
715 uint32_t index = turnstile_hash(proprietor);
716 assert(index < ts_htable_buckets);
717 bool kdp_ctx = !not_in_kdp;
718 struct turnstile_htable_bucket *ts_bucket = turnstile_get_bucket(index, type);
719 int hash_policy = turnstile_hash_lock_policy[type];
720 bool needs_lock = !(hash_policy & TURNSTILE_LOCKED_HASH);
721 bool irq_safe = !(hash_policy & TURNSTILE_IRQ_UNSAFE_HASH);
722 spl_t s;
723
724 if (needs_lock) {
725 if (irq_safe && !kdp_ctx) {
726 s = splsched();
727 }
728
729 if (kdp_ctx) {
730 if (kdp_turnstile_bucket_is_locked(ts_bucket)) {
731 /* This should move to TURNSTILE_BUSY once 51725781 is in the build */
732 return TURNSTILE_NULL;
733 }
734 } else {
735 turnstile_bucket_lock(ts_bucket);
736 }
737 }
738 struct turnstile *ts = TURNSTILE_NULL;
739 struct turnstile *ret_turnstile = TURNSTILE_NULL;
740
741 SLIST_FOREACH(ts, &ts_bucket->ts_ht_bucket_list, ts_htable_link) {
742 if (ts->ts_proprietor == proprietor) {
743 /* Found an entry in the hashtable for this proprietor */
744 ret_turnstile = ts;
745 break;
746 }
747 }
748
749 if (needs_lock && !kdp_ctx) {
750 turnstile_bucket_unlock(ts_bucket);
751 if (irq_safe) {
752 splx(s);
753 }
754 }
755
756 return ret_turnstile;
757}
758
759/*
760 * Name: turnstile_deallocate_queue_invoke
761 *
762 * Description: invoke function for the asynchronous turnstile deallocation
763 * queue
764 *
765 * Arg1: &turnstile_deallocate_queue
766 * Arg2: a pointer to the turnstile ts_deallocate_link member of a tunrstile to
767 * destroy.
768 *
769 * Returns: None.
770 */
771static void
772turnstile_deallocate_queue_invoke(mpsc_queue_chain_t e,
773 __assert_only mpsc_daemon_queue_t dq)
774{
775 struct turnstile *ts;
776
777 ts = mpsc_queue_element(e, struct turnstile, ts_deallocate_link);
778 assert(dq == &turnstile_deallocate_queue);
779 turnstile_destroy(turnstile: ts);
780}
781
782/*
783 * Name: turnstiles_init
784 *
785 * Description: Initialize turnstile sub system.
786 *
787 * Args: None.
788 *
789 * Returns: None.
790 */
791void
792turnstiles_init(void)
793{
794 ctsid_nonce = (uint32_t)early_random() & CTSID_MASK;
795 turnstiles_hashtable_init();
796
797 thread_deallocate_daemon_register_queue(dq: &turnstile_deallocate_queue,
798 invoke: turnstile_deallocate_queue_invoke);
799
800#if DEVELOPMENT || DEBUG
801 /* Initialize turnstile test primitive */
802 tstile_test_prim_init(&test_prim_ts_inline);
803 tstile_test_prim_init(&test_prim_global_htable);
804 tstile_test_prim_init(&test_prim_global_ts_kernel);
805 tstile_test_prim_init(&test_prim_global_ts_kernel_hash);
806#endif
807}
808
809/*
810 * Name: turnstile_alloc
811 *
812 * Description: Allocate a turnstile.
813 *
814 * Args: None.
815 *
816 * Returns:
817 * turnstile on Success.
818 */
819struct turnstile *
820turnstile_alloc(void)
821{
822 struct turnstile *turnstile = TURNSTILE_NULL;
823
824 turnstile = zalloc_id(ZONE_ID_TURNSTILE, Z_WAITOK | Z_ZERO | Z_NOFAIL);
825
826 /* Initialize the waitq */
827 waitq_init(waitq: &turnstile->ts_waitq, type: WQT_TURNSTILE,
828 SYNC_POLICY_REVERSED | SYNC_POLICY_INIT_LOCKED);
829
830 SLIST_INIT(&turnstile->ts_free_turnstiles);
831
832 turnstile_set_type_and_increment_gencount(turnstile, type: TURNSTILE_NONE);
833 turnstile_state_init(turnstile, TURNSTILE_STATE_THREAD);
834 os_ref_init_raw(&turnstile->ts_refcount, &turnstile_refgrp);
835 priority_queue_init(que: &turnstile->ts_inheritor_queue);
836
837#if DEVELOPMENT || DEBUG
838 turnstile->ts_thread = current_thread();
839#endif
840
841 waitq_unlock(wq: &turnstile->ts_waitq);
842
843 return turnstile;
844}
845
846/*
847 * Name: turnstile_reference
848 *
849 * Description: Take a reference on the turnstile.
850 *
851 * Arg1: turnstile
852 *
853 * Returns: None.
854 */
855void
856turnstile_reference(struct turnstile *turnstile)
857{
858 if (turnstile == TURNSTILE_NULL) {
859 return;
860 }
861
862 zone_id_require(zone_id: ZONE_ID_TURNSTILE, elem_size: sizeof(struct turnstile), addr: turnstile);
863
864 os_ref_retain_raw(&turnstile->ts_refcount, &turnstile_refgrp);
865}
866
867/*
868 * Name: turnstile_deallocate
869 *
870 * Description: Drop a reference on the turnstile.
871 * Destroy the turnstile if the last ref.
872 *
873 * Arg1: turnstile
874 *
875 * Returns: None.
876 */
877void
878turnstile_deallocate(struct turnstile *turnstile)
879{
880 if (turnstile == TURNSTILE_NULL) {
881 return;
882 }
883
884 if (__improbable(os_ref_release_raw(&turnstile->ts_refcount,
885 &turnstile_refgrp) == 0)) {
886 assert(SLIST_EMPTY(&turnstile->ts_free_turnstiles));
887 turnstile_destroy(turnstile);
888 }
889}
890
891/*
892 * Name: turnstile_deallocate_safe
893 *
894 * Description: Drop a reference on the turnstile safely without triggering zfree.
895 *
896 * Arg1: turnstile
897 *
898 * Returns: None.
899 */
900void
901turnstile_deallocate_safe(struct turnstile *turnstile)
902{
903 if (turnstile == TURNSTILE_NULL) {
904 return;
905 }
906
907 if (__improbable(os_ref_release_raw(&turnstile->ts_refcount,
908 &turnstile_refgrp) == 0)) {
909 assert(SLIST_EMPTY(&turnstile->ts_free_turnstiles));
910 mpsc_daemon_enqueue(dq: &turnstile_deallocate_queue,
911 elm: &turnstile->ts_deallocate_link, options: MPSC_QUEUE_DISABLE_PREEMPTION);
912 }
913}
914
915/*
916 * Name: turnstile_destroy
917 *
918 * Description: Deallocates the turnstile.
919 *
920 * Args:
921 * Arg1: turnstile
922 *
923 * Returns: None.
924 */
925static void
926turnstile_destroy(struct turnstile *turnstile)
927{
928 assert3u(turnstile->ts_compact_id, ==, 0);
929 assert3u(turnstile->ts_prim_count, ==, 0);
930 assert3p(turnstile->ts_inheritor, ==, TURNSTILE_INHERITOR_NULL);
931 assert3u(turnstile->ts_state, ==, TURNSTILE_STATE_THREAD);
932
933 waitq_deinit(waitq: &turnstile->ts_waitq);
934
935 zfree_id(ZONE_ID_TURNSTILE, turnstile);
936}
937
938static uint32_t
939ctsid_mangle(compact_id_t cid)
940{
941 return (cid == ctsid_nonce ? CTSID_MASK : cid) ^ ctsid_nonce;
942}
943
944static compact_id_t
945ctsid_unmangle(uint32_t ctsid)
946{
947 ctsid ^= ctsid_nonce;
948 return ctsid == CTSID_MASK ? ctsid_nonce : ctsid;
949}
950
951uint32_t
952turnstile_compact_id_get(void)
953{
954 compact_id_t cid;
955
956 cid = compact_id_get(table: &ctsid_table, CTSID_MAX, NULL);
957 return ctsid_mangle(cid);
958}
959
960void
961turnstile_compact_id_put(uint32_t ctsid)
962{
963 assert3u(ctsid, !=, 0);
964 compact_id_put(table: &ctsid_table, compact_id: ctsid_unmangle(ctsid));
965}
966
967/*
968 * Name: turnstile_get_by_id
969 *
970 * Description: Resolve a turnstile by compact ID
971 *
972 * Args:
973 * Arg1: turnstile compact ID
974 *
975 * Returns: a turnstile
976 */
977struct turnstile *
978turnstile_get_by_id(uint32_t tsid)
979{
980 struct turnstile *ts = TURNSTILE_NULL;
981
982 if (tsid) {
983 ts = *compact_id_resolve(table: &ctsid_table, compact_id: ctsid_unmangle(ctsid: tsid));
984 assert(ts && ts->ts_compact_id == tsid);
985 }
986 return ts;
987}
988
989/*
990 * Name: turnstile_prepare variants
991 *
992 * Description: Transfer current thread's turnstile to primitive or it's free turnstile list.
993 * Function is called holding the interlock (spinlock) of the primitive.
994 */
995static struct turnstile *
996turnstile_prepare_common(
997 uintptr_t proprietor,
998 thread_t thread,
999 struct turnstile *incoming,
1000 turnstile_type_t type)
1001{
1002 struct turnstile *thread_turnstile = incoming;
1003
1004 /* Get the thread's turnstile if no turnstile provided */
1005 if (thread_turnstile == TURNSTILE_NULL) {
1006 thread_turnstile = thread->turnstile;
1007 assert(thread_turnstile != TURNSTILE_NULL);
1008 assert(thread->inheritor == NULL);
1009 thread->turnstile = TURNSTILE_NULL;
1010 }
1011
1012 /* Prepare the thread turnstile to be the primitive turnstile */
1013 SLIST_INIT(&thread_turnstile->ts_free_turnstiles);
1014 turnstile_set_type_and_increment_gencount(turnstile: thread_turnstile, type);
1015 thread_turnstile->ts_inheritor = TURNSTILE_INHERITOR_NULL;
1016 thread_turnstile->ts_proprietor = proprietor;
1017 turnstile_state_remove(thread_turnstile, TURNSTILE_STATE_THREAD);
1018
1019 thread_turnstile->ts_priority = 0;
1020#if DEVELOPMENT || DEBUG
1021 thread_turnstile->ts_prev_thread = thread_turnstile->ts_thread;
1022 thread_turnstile->ts_thread = NULL;
1023#endif
1024
1025 return thread_turnstile;
1026}
1027
1028struct turnstile *
1029turnstile_prepare(
1030 uintptr_t proprietor,
1031 struct turnstile **tstore,
1032 struct turnstile *turnstile,
1033 turnstile_type_t type)
1034{
1035 thread_t thread = current_thread();
1036 struct turnstile *ret_turnstile = TURNSTILE_NULL;
1037 struct turnstile *thread_turnstile;
1038
1039 thread_turnstile = turnstile_prepare_common(proprietor, thread,
1040 incoming: turnstile, type);
1041
1042 /*
1043 * If the primitive stores the turnstile,
1044 * If there is already a turnstile, put the thread_turnstile if the primitive currently does not have a
1045 * turnstile.
1046 * Else, add the thread turnstile to freelist of the primitive turnstile.
1047 */
1048 ret_turnstile = *tstore;
1049 if (*tstore == TURNSTILE_NULL) {
1050 turnstile_state_add(thread_turnstile, TURNSTILE_STATE_PROPRIETOR);
1051 *tstore = thread_turnstile;
1052 KERNEL_DEBUG_CONSTANT_IST(KDEBUG_TRACE,
1053 (TURNSTILE_CODE(TURNSTILE_FREELIST_OPERATIONS, (TURNSTILE_PREPARE))) | DBG_FUNC_NONE,
1054 VM_KERNEL_UNSLIDE_OR_PERM(thread_turnstile),
1055 VM_KERNEL_UNSLIDE_OR_PERM(proprietor),
1056 turnstile_get_type(thread_turnstile), 0, 0);
1057 } else {
1058 turnstile_freelist_insert(dst_ts: ret_turnstile, free_ts: thread_turnstile);
1059 }
1060 ret_turnstile = *tstore;
1061
1062 return ret_turnstile;
1063}
1064
1065struct turnstile *
1066turnstile_prepare_compact_id(
1067 uintptr_t proprietor,
1068 uint32_t compact_id,
1069 turnstile_type_t type)
1070{
1071 thread_t thread = current_thread();
1072 struct turnstile *ret_turnstile = TURNSTILE_NULL;
1073 struct turnstile *thread_turnstile;
1074 uint32_t ctsid = thread->ctsid;
1075
1076 thread_turnstile = turnstile_prepare_common(proprietor, thread,
1077 TURNSTILE_NULL, type);
1078
1079 assert3u(ctsid, !=, 0);
1080 thread_turnstile->ts_compact_id = ctsid;
1081 thread->ctsid = 0;
1082
1083 /*
1084 * If the primitive stores the turnstile,
1085 * If there is already a turnstile, put the thread_turnstile if the primitive currently does not have a
1086 * turnstile.
1087 * Else, add the thread turnstile to freelist of the primitive turnstile.
1088 */
1089 if (compact_id == 0) {
1090 turnstile_state_add(thread_turnstile, TURNSTILE_STATE_PROPRIETOR);
1091 ret_turnstile = thread_turnstile;
1092 *compact_id_resolve(table: &ctsid_table, compact_id: ctsid_unmangle(ctsid)) = ret_turnstile;
1093 KERNEL_DEBUG_CONSTANT_IST(KDEBUG_TRACE,
1094 (TURNSTILE_CODE(TURNSTILE_FREELIST_OPERATIONS, (TURNSTILE_PREPARE))) | DBG_FUNC_NONE,
1095 VM_KERNEL_UNSLIDE_OR_PERM(thread_turnstile),
1096 VM_KERNEL_UNSLIDE_OR_PERM(proprietor),
1097 turnstile_get_type(thread_turnstile), 0, 0);
1098 } else {
1099 ret_turnstile = turnstile_get_by_id(tsid: compact_id);
1100 turnstile_freelist_insert(dst_ts: ret_turnstile, free_ts: thread_turnstile);
1101 }
1102
1103 return ret_turnstile;
1104}
1105
1106struct turnstile *
1107turnstile_prepare_hash(
1108 uintptr_t proprietor,
1109 turnstile_type_t type)
1110{
1111 thread_t thread = current_thread();
1112 struct turnstile *ret_turnstile = TURNSTILE_NULL;
1113 struct turnstile *thread_turnstile;
1114
1115 thread_turnstile = turnstile_prepare_common(proprietor, thread,
1116 TURNSTILE_NULL, type);
1117
1118 /*
1119 * Lookup the primitive in the turnstile hash table and see if it already has an entry.
1120 */
1121 ret_turnstile = turnstile_htable_lookup_add(proprietor, new_turnstile: thread_turnstile, type);
1122 if (ret_turnstile == NULL) {
1123 ret_turnstile = thread_turnstile;
1124 KERNEL_DEBUG_CONSTANT_IST(KDEBUG_TRACE,
1125 (TURNSTILE_CODE(TURNSTILE_FREELIST_OPERATIONS, (TURNSTILE_PREPARE))) | DBG_FUNC_NONE,
1126 VM_KERNEL_UNSLIDE_OR_PERM(thread_turnstile),
1127 VM_KERNEL_UNSLIDE_OR_PERM(proprietor),
1128 turnstile_get_type(thread_turnstile), 0, 0);
1129 }
1130
1131 return ret_turnstile;
1132}
1133
1134/*
1135 * Name: turnstile_complete variants
1136 *
1137 * Description: Transfer the primitive's turnstile or from it's freelist to current thread.
1138 * Current thread will have a turnstile attached to it after this call.
1139 */
1140static void
1141turnstile_complete_common(
1142 uintptr_t proprietor __kdebug_only,
1143 thread_t thread,
1144 struct turnstile *thread_turnstile,
1145 struct turnstile *primitive_turnstile,
1146 struct turnstile **out_turnstile)
1147{
1148 if (primitive_turnstile == NULL) {
1149 /*
1150 * Primitive no longer has a turnstile associated with it, thread_turnstile
1151 * was the last turnstile attached to primitive, clear out the inheritor and
1152 * set the old inheritor for turnstile cleanup.
1153 */
1154 if (thread_turnstile->ts_inheritor != TURNSTILE_INHERITOR_NULL) {
1155 turnstile_update_inheritor(turnstile: thread_turnstile, TURNSTILE_INHERITOR_NULL,
1156 flags: (TURNSTILE_IMMEDIATE_UPDATE | TURNSTILE_INHERITOR_THREAD));
1157 /*
1158 * old inheritor is set in curret thread and its priority propagation
1159 * will happen in turnstile cleanup call
1160 */
1161 }
1162 thread_turnstile->ts_proprietor = TURNSTILE_PROPRIETOR_NULL;
1163 assert(thread_turnstile->ts_inheritor == TURNSTILE_INHERITOR_NULL);
1164
1165 KERNEL_DEBUG_CONSTANT_IST(KDEBUG_TRACE,
1166 (TURNSTILE_CODE(TURNSTILE_FREELIST_OPERATIONS, (TURNSTILE_COMPLETE))) | DBG_FUNC_NONE,
1167 VM_KERNEL_UNSLIDE_OR_PERM(thread_turnstile),
1168 VM_KERNEL_UNSLIDE_OR_PERM(proprietor),
1169 turnstile_get_type(thread_turnstile), 0, 0);
1170 } else {
1171 /* If primitive's turnstile needs priority update, set it up for turnstile cleanup */
1172 if (turnstile_recompute_priority(turnstile: primitive_turnstile)) {
1173 turnstile_reference(turnstile: primitive_turnstile);
1174 thread->inheritor = primitive_turnstile;
1175 thread->inheritor_flags = (TURNSTILE_INHERITOR_TURNSTILE |
1176 TURNSTILE_INHERITOR_NEEDS_PRI_UPDATE);
1177 }
1178 }
1179
1180 turnstile_set_type_and_increment_gencount(turnstile: thread_turnstile, type: TURNSTILE_NONE);
1181#if DEVELOPMENT || DEBUG
1182 thread_turnstile->ts_prev_thread = NULL;
1183 thread_turnstile->ts_thread = thread;
1184#endif
1185
1186 turnstile_state_add(thread_turnstile, TURNSTILE_STATE_THREAD);
1187 if (out_turnstile == NULL) {
1188 /* Prepare the turnstile to become the thread's turnstile */
1189 thread->turnstile = thread_turnstile;
1190 } else {
1191 *out_turnstile = thread_turnstile;
1192 }
1193}
1194
1195void
1196turnstile_complete(
1197 uintptr_t proprietor,
1198 struct turnstile **tstore,
1199 struct turnstile **out_turnstile,
1200 turnstile_type_t type __unused)
1201{
1202 thread_t thread = current_thread();
1203 struct turnstile *primitive_turnstile = TURNSTILE_NULL;
1204 struct turnstile *thread_turnstile = TURNSTILE_NULL;
1205
1206 assert(thread->inheritor == NULL);
1207
1208 /*
1209 * If the primitive stores the turnstile, check if the primitive turnstile
1210 * has any turnstiles on its freelist.
1211 */
1212 assert(*tstore != TURNSTILE_NULL);
1213 if (turnstile_freelist_empty(ts: *tstore)) {
1214 /* Last turnstile scenario; remove the primitive->turnstile */
1215 thread_turnstile = *tstore;
1216 *tstore = TURNSTILE_NULL;
1217 turnstile_state_remove(thread_turnstile, TURNSTILE_STATE_PROPRIETOR);
1218 } else {
1219 /* Freelist has turnstiles; remove one from the freelist */
1220 thread_turnstile = turnstile_freelist_remove(ts: *tstore);
1221 }
1222 primitive_turnstile = *tstore;
1223
1224 turnstile_complete_common(proprietor, thread, thread_turnstile,
1225 primitive_turnstile, out_turnstile);
1226}
1227
1228bool
1229turnstile_complete_compact_id(
1230 uintptr_t proprietor,
1231 struct turnstile *primitive_turnstile,
1232 turnstile_type_t type __unused)
1233{
1234 thread_t thread = current_thread();
1235 struct turnstile *thread_turnstile = TURNSTILE_NULL;
1236 bool was_last = turnstile_freelist_empty(ts: primitive_turnstile);
1237 uint32_t ctsid;
1238
1239 assert(thread->inheritor == NULL);
1240
1241 assert(primitive_turnstile != TURNSTILE_NULL);
1242 if (was_last) {
1243 /* Last turnstile scenario; remove the primitive->turnstile */
1244 thread_turnstile = primitive_turnstile;
1245 turnstile_state_remove(thread_turnstile, TURNSTILE_STATE_PROPRIETOR);
1246 primitive_turnstile = TURNSTILE_NULL;
1247 } else {
1248 /* Freelist has turnstiles; remove one from the freelist */
1249 thread_turnstile = turnstile_freelist_remove(ts: primitive_turnstile);
1250 }
1251
1252 ctsid = thread_turnstile->ts_compact_id;
1253 assert3u(ctsid, !=, 0);
1254 thread_turnstile->ts_compact_id = 0;
1255 thread->ctsid = ctsid;
1256 if (was_last) {
1257 *compact_id_resolve(table: &ctsid_table, compact_id: ctsid_unmangle(ctsid)) = NULL;
1258 }
1259
1260 turnstile_complete_common(proprietor, thread, thread_turnstile,
1261 primitive_turnstile, NULL);
1262
1263 return was_last;
1264}
1265
1266void
1267turnstile_complete_hash(
1268 uintptr_t proprietor,
1269 turnstile_type_t type)
1270{
1271 thread_t thread = current_thread();
1272 struct turnstile *primitive_turnstile = TURNSTILE_NULL;
1273 struct turnstile *thread_turnstile = TURNSTILE_NULL;
1274
1275 assert(thread->inheritor == NULL);
1276
1277 /* Use the global hash to find and remove a turnstile */
1278 primitive_turnstile = turnstable_htable_lookup_remove(proprietor, free_turnstile: &thread_turnstile, type);
1279
1280 turnstile_complete_common(proprietor, thread, thread_turnstile,
1281 primitive_turnstile, NULL);
1282}
1283
1284/*
1285 * Name: turnstile_kernel_update_inheritor_on_wake_locked
1286 *
1287 * Description: Set thread as the inheritor of the turnstile and
1288 * boost the inheritor.
1289 * Args:
1290 * Arg1: turnstile
1291 * Arg2: new_inheritor
1292 * Arg3: flags
1293 *
1294 * Called with turnstile locked
1295 */
1296void
1297turnstile_kernel_update_inheritor_on_wake_locked(
1298 struct turnstile *turnstile,
1299 turnstile_inheritor_t new_inheritor,
1300 turnstile_update_flags_t flags __assert_only)
1301{
1302 /* for now only kernel primitives are allowed to call this function */
1303 __assert_only turnstile_promote_policy_t policy =
1304 turnstile_promote_policy[turnstile_get_type(turnstile)];
1305
1306 assert(flags & TURNSTILE_INHERITOR_THREAD);
1307 assert(policy == TURNSTILE_KERNEL_PROMOTE || policy == TURNSTILE_USER_PROMOTE);
1308
1309 turnstile_stash_inheritor(new_inheritor: (thread_t)new_inheritor, flags: TURNSTILE_INHERITOR_THREAD);
1310 /*
1311 * new_inheritor has just been removed from the turnstile waitq,
1312 * the turnstile new priority needs to be recomputed so that
1313 * when new_inheritor will become this turnstile inheritor can
1314 * inherit the correct priority.
1315 */
1316 turnstile_recompute_priority_locked(turnstile);
1317 turnstile_update_inheritor_locked(turnstile);
1318}
1319
1320/*
1321 * Name: turnstile_update_inheritor_locked
1322 *
1323 * Description: Update the inheritor of the turnstile and boost the
1324 * inheritor, called with turnstile locked.
1325 *
1326 * Args:
1327 * Arg1: turnstile
1328 * Implicit arg: new inheritor value is stashed in current thread's struct
1329 *
1330 * Returns:
1331 * old inheritor reference is returned on current thread's struct.
1332 */
1333void
1334turnstile_update_inheritor_locked(
1335 struct turnstile *turnstile)
1336{
1337 turnstile_inheritor_t old_inheritor = turnstile->ts_inheritor;
1338 turnstile_update_flags_t old_inheritor_flags = turnstile->ts_inheritor_flags;
1339 thread_t thread = current_thread();
1340 boolean_t old_inheritor_needs_update = FALSE;
1341 boolean_t new_inheritor_needs_update = FALSE;
1342 turnstile_stats_update_flags_t tsu_flags =
1343 turnstile_get_update_flags_for_above_UI_pri_change(turnstile);
1344
1345 assert(waitq_held(&turnstile->ts_waitq));
1346
1347 /*
1348 * Get the new inheritor value from current thread's
1349 * struct, the value was stashed by turnstile_update_inheritor
1350 */
1351 turnstile_inheritor_t new_inheritor = thread->inheritor;
1352 turnstile_update_flags_t new_inheritor_flags = thread->inheritor_flags;
1353
1354 switch (turnstile_promote_policy[turnstile_get_type(turnstile)]) {
1355 case TURNSTILE_USER_PROMOTE:
1356 case TURNSTILE_USER_IPC_PROMOTE:
1357 break;
1358 case TURNSTILE_KERNEL_PROMOTE:
1359 /* some sanity checks, turnstile kernel can push just between threads */
1360 if (old_inheritor) {
1361 assert(old_inheritor_flags & TURNSTILE_INHERITOR_THREAD);
1362 }
1363
1364 if (new_inheritor) {
1365 assert(new_inheritor_flags & TURNSTILE_INHERITOR_THREAD);
1366 }
1367
1368 break;
1369 default:
1370 panic("turnstile promotion for type %d not yet implemented", turnstile_get_type(turnstile));
1371 }
1372
1373 /* Check if update is needed */
1374 if (old_inheritor == new_inheritor && old_inheritor == NULL) {
1375 goto done;
1376 }
1377
1378 if (old_inheritor == new_inheritor) {
1379 if (new_inheritor_flags & TURNSTILE_INHERITOR_THREAD) {
1380 thread_t thread_inheritor = (thread_t)new_inheritor;
1381
1382 assert(old_inheritor_flags & TURNSTILE_INHERITOR_THREAD);
1383
1384 /* adjust turnstile position in the thread's inheritor list */
1385 new_inheritor_needs_update = thread_update_turnstile_promotion(
1386 thread: thread_inheritor, turnstile);
1387 } else if (new_inheritor_flags & TURNSTILE_INHERITOR_TURNSTILE) {
1388 struct turnstile *inheritor_turnstile = new_inheritor;
1389
1390 assert(old_inheritor_flags & TURNSTILE_INHERITOR_TURNSTILE);
1391
1392 new_inheritor_needs_update = turnstile_update_turnstile_promotion(
1393 dst_turnstile: inheritor_turnstile, src_turnstile: turnstile);
1394 } else if (new_inheritor_flags & TURNSTILE_INHERITOR_WORKQ) {
1395 /*
1396 * When we are still picking "WORKQ" then possible racing
1397 * updates will call redrive through their own propagation
1398 * and we don't need to update anything here.
1399 */
1400 turnstile_stats_update(hop: 1, flags: TSU_NO_PRI_CHANGE_NEEDED |
1401 TSU_TURNSTILE_ARG | TSU_BOOST_ARG, inheritor: turnstile);
1402 } else {
1403 panic("Inheritor flags lost along the way");
1404 }
1405
1406 /* Update turnstile stats */
1407 if (!new_inheritor_needs_update) {
1408 turnstile_stats_update(hop: 1, flags: TSU_PRI_PROPAGATION |
1409 TSU_TURNSTILE_ARG | TSU_BOOST_ARG | tsu_flags, inheritor: turnstile);
1410 }
1411 goto done;
1412 }
1413
1414 if (old_inheritor != NULL) {
1415 if (old_inheritor_flags & TURNSTILE_INHERITOR_THREAD) {
1416 thread_t thread_inheritor = (thread_t)old_inheritor;
1417
1418 /* remove turnstile from thread's inheritor list */
1419 old_inheritor_needs_update = thread_remove_turnstile_promotion(thread: thread_inheritor, turnstile);
1420 } else if (old_inheritor_flags & TURNSTILE_INHERITOR_TURNSTILE) {
1421 struct turnstile *old_turnstile = old_inheritor;
1422
1423 old_inheritor_needs_update = turnstile_remove_turnstile_promotion(
1424 dst_turnstile: old_turnstile, src_turnstile: turnstile);
1425 } else if (old_inheritor_flags & TURNSTILE_INHERITOR_WORKQ) {
1426 /*
1427 * We don't need to do anything when the push was WORKQ
1428 * because nothing is pushed on in the first place.
1429 */
1430 turnstile_stats_update(hop: 1, flags: TSU_NO_PRI_CHANGE_NEEDED |
1431 TSU_TURNSTILE_ARG, inheritor: turnstile);
1432 } else {
1433 panic("Inheritor flags lost along the way");
1434 }
1435 /* Update turnstile stats */
1436 if (!old_inheritor_needs_update) {
1437 turnstile_stats_update(hop: 1, flags: TSU_PRI_PROPAGATION | TSU_TURNSTILE_ARG,
1438 inheritor: turnstile);
1439 }
1440 }
1441
1442 if (new_inheritor != NULL) {
1443 if (new_inheritor_flags & TURNSTILE_INHERITOR_THREAD) {
1444 thread_t thread_inheritor = (thread_t)new_inheritor;
1445
1446 assert(new_inheritor_flags & TURNSTILE_INHERITOR_THREAD);
1447 /* add turnstile to thread's inheritor list */
1448 new_inheritor_needs_update = thread_add_turnstile_promotion(
1449 thread: thread_inheritor, turnstile);
1450 } else if (new_inheritor_flags & TURNSTILE_INHERITOR_TURNSTILE) {
1451 struct turnstile *new_turnstile = new_inheritor;
1452
1453 new_inheritor_needs_update = turnstile_add_turnstile_promotion(
1454 dst_turnstile: new_turnstile, src_turnstile: turnstile);
1455 } else if (new_inheritor_flags & TURNSTILE_INHERITOR_WORKQ) {
1456 struct workqueue *wq_inheritor = new_inheritor;
1457
1458 new_inheritor_needs_update = workq_add_turnstile_promotion(
1459 wq_inheritor, turnstile);
1460 if (!new_inheritor_needs_update) {
1461 turnstile_stats_update(hop: 1, flags: TSU_NO_PRI_CHANGE_NEEDED |
1462 TSU_TURNSTILE_ARG | TSU_BOOST_ARG, inheritor: turnstile);
1463 }
1464 } else {
1465 panic("Inheritor flags lost along the way");
1466 }
1467 /* Update turnstile stats */
1468 if (!new_inheritor_needs_update) {
1469 turnstile_stats_update(hop: 1, flags: TSU_PRI_PROPAGATION |
1470 TSU_TURNSTILE_ARG | TSU_BOOST_ARG | tsu_flags, inheritor: turnstile);
1471 }
1472 }
1473
1474done:
1475 if (old_inheritor_needs_update) {
1476 old_inheritor_flags |= TURNSTILE_INHERITOR_NEEDS_PRI_UPDATE;
1477 }
1478
1479 /*
1480 * If new inheritor needs priority updated, then set TURNSTILE_NEEDS_PRI_UPDATE
1481 * on the old_inheritor_flags which will be copied to the thread.
1482 */
1483 if (new_inheritor_needs_update) {
1484 old_inheritor_flags |= TURNSTILE_NEEDS_PRI_UPDATE;
1485 }
1486
1487 turnstile->ts_inheritor = new_inheritor;
1488 turnstile->ts_inheritor_flags = new_inheritor_flags;
1489 thread->inheritor = old_inheritor;
1490 thread->inheritor_flags = old_inheritor_flags;
1491 return;
1492}
1493
1494/*
1495 * Name: turnstile_stash_inheritor
1496 *
1497 * Description: Save the new inheritor reference of the turnstile on the
1498 * current thread. It will take a thread reference on the inheritor.
1499 * Called with the interlock of the primitive held.
1500 *
1501 * Args:
1502 * Arg1: inheritor
1503 * Arg2: flags
1504 *
1505 * Returns:
1506 * old inheritor reference is stashed on current thread's struct.
1507 */
1508static void
1509turnstile_stash_inheritor(
1510 turnstile_inheritor_t new_inheritor,
1511 turnstile_update_flags_t flags)
1512{
1513 thread_t thread = current_thread();
1514
1515 /*
1516 * Set the inheritor on calling thread struct, no need
1517 * to take the turnstile waitq lock since the inheritor
1518 * is protected by the primitive's interlock
1519 */
1520 assert(thread->inheritor == TURNSTILE_INHERITOR_NULL);
1521 thread->inheritor = new_inheritor;
1522 thread->inheritor_flags = TURNSTILE_UPDATE_FLAGS_NONE;
1523 if (new_inheritor == TURNSTILE_INHERITOR_NULL) {
1524 /* nothing to retain or remember */
1525 } else if (flags & TURNSTILE_INHERITOR_THREAD) {
1526 thread->inheritor_flags |= TURNSTILE_INHERITOR_THREAD;
1527 thread_reference(thread: (thread_t)new_inheritor);
1528 } else if (flags & TURNSTILE_INHERITOR_TURNSTILE) {
1529 thread->inheritor_flags |= TURNSTILE_INHERITOR_TURNSTILE;
1530 turnstile_reference(turnstile: (struct turnstile *)new_inheritor);
1531 } else if (flags & TURNSTILE_INHERITOR_WORKQ) {
1532 thread->inheritor_flags |= TURNSTILE_INHERITOR_WORKQ;
1533 workq_reference(wq: (struct workqueue *)new_inheritor);
1534 } else {
1535 panic("Missing type in flags (%x) for inheritor (%p)", flags,
1536 new_inheritor);
1537 }
1538}
1539
1540/*
1541 * Name: turnstile_update_inheritor
1542 *
1543 * Description: Update the inheritor of the turnstile and boost the
1544 * inheritor. It will take a thread reference on the inheritor.
1545 * Called with the interlock of the primitive held.
1546 *
1547 * Args:
1548 * Arg1: turnstile
1549 * Arg2: inheritor
1550 * Arg3: flags - TURNSTILE_DELAYED_UPDATE - update will happen later in assert_wait
1551 *
1552 * Returns:
1553 * old inheritor reference is stashed on current thread's struct.
1554 */
1555void
1556turnstile_update_inheritor(
1557 struct turnstile *turnstile,
1558 turnstile_inheritor_t new_inheritor,
1559 turnstile_update_flags_t flags)
1560{
1561 spl_t spl;
1562
1563 turnstile_stash_inheritor(new_inheritor, flags);
1564
1565 /* Do not perform the update if delayed update is specified */
1566 if (flags & TURNSTILE_DELAYED_UPDATE) {
1567 return;
1568 }
1569
1570 /* lock the turnstile waitq */
1571 spl = splsched();
1572 waitq_lock(wq: &turnstile->ts_waitq);
1573
1574 turnstile_update_inheritor_locked(turnstile);
1575
1576 waitq_unlock(wq: &turnstile->ts_waitq);
1577 splx(spl);
1578
1579 return;
1580}
1581
1582
1583/*
1584 * Name: turnstile_need_thread_promotion_update
1585 *
1586 * Description: Check if thread's place in the turnstile waitq needs to be updated.
1587 *
1588 * Arg1: dst turnstile
1589 * Arg2: thread
1590 *
1591 * Returns: TRUE: if turnstile_update_thread_promotion_locked needs to be called.
1592 * FALSE: otherwise.
1593 *
1594 * Condition: thread locked.
1595 */
1596static boolean_t
1597turnstile_need_thread_promotion_update(
1598 struct turnstile *dst_turnstile,
1599 thread_t thread)
1600{
1601 int thread_link_priority;
1602 boolean_t needs_update = FALSE;
1603
1604 thread_link_priority = priority_queue_entry_sched_pri(
1605 &dst_turnstile->ts_waitq.waitq_prio_queue,
1606 &thread->wait_prioq_links);
1607
1608 int priority = turnstile_compute_thread_push(turnstile: dst_turnstile, thread);
1609
1610 needs_update = (thread_link_priority == priority) ? FALSE : TRUE;
1611
1612 return needs_update;
1613}
1614
1615/*
1616 * Name: turnstile_priority_queue_update_entry_key
1617 *
1618 * Description: Updates the priority of an entry in a priority queue
1619 *
1620 * Arg1: a turnstile/thread/... priority queue
1621 * Arg2: the element to change the priority of
1622 * Arg3: the new priority
1623 *
1624 * Returns: whether the maximum priority of the queue changed.
1625 */
1626static boolean_t
1627turnstile_priority_queue_update_entry_key(struct priority_queue_sched_max *q,
1628 priority_queue_entry_sched_t elt, priority_queue_key_t pri)
1629{
1630 priority_queue_key_t old_key = priority_queue_max_sched_pri(q);
1631
1632 if (priority_queue_entry_sched_pri(q, elt) < pri) {
1633 priority_queue_entry_set_sched_pri(q, elt, pri, false);
1634 if (priority_queue_entry_increased(que: q, elt)) {
1635 return old_key != priority_queue_max_sched_pri(q);
1636 }
1637 } else if (priority_queue_entry_sched_pri(q, elt) > pri) {
1638 priority_queue_entry_set_sched_pri(q, elt, pri, false);
1639 if (priority_queue_entry_decreased(que: q, elt)) {
1640 return old_key != priority_queue_max_sched_pri(q);
1641 }
1642 }
1643
1644 return FALSE;
1645}
1646
1647/*
1648 * Name: turnstile_update_thread_promotion_locked
1649 *
1650 * Description: Update dst turnstile's inheritor link since one of the waiting
1651 * thread's priority has changed.
1652 *
1653 * Arg1: dst turnstile
1654 * Arg2: thread
1655 *
1656 * Returns: TRUE: if the dst turnstile priority has changed and needs propagation.
1657 * FALSE: if the dst turnstile priority did not change or it does not need propagation.
1658 *
1659 * Condition: dst turnstile and thread are locked.
1660 */
1661static boolean_t
1662turnstile_update_thread_promotion_locked(
1663 struct turnstile *dst_turnstile,
1664 thread_t thread)
1665{
1666 int thread_link_priority;
1667
1668 int priority = turnstile_compute_thread_push(turnstile: dst_turnstile, thread);
1669
1670 thread_link_priority = priority_queue_entry_sched_pri(
1671 &dst_turnstile->ts_waitq.waitq_prio_queue,
1672 &thread->wait_prioq_links);
1673
1674 if (priority != thread_link_priority) {
1675 KERNEL_DEBUG_CONSTANT_IST(KDEBUG_TRACE,
1676 (TURNSTILE_CODE(TURNSTILE_HEAP_OPERATIONS, (THREAD_MOVED_IN_TURNSTILE_WAITQ))) | DBG_FUNC_NONE,
1677 VM_KERNEL_UNSLIDE_OR_PERM(dst_turnstile),
1678 thread_tid(thread),
1679 priority,
1680 thread_link_priority, 0);
1681 }
1682
1683 if (!turnstile_priority_queue_update_entry_key(
1684 q: &dst_turnstile->ts_waitq.waitq_prio_queue,
1685 elt: &thread->wait_prioq_links, pri: (priority_queue_key_t)priority)) {
1686 return FALSE;
1687 }
1688
1689 /* Update dst turnstile's priority */
1690 return turnstile_recompute_priority_locked(turnstile: dst_turnstile);
1691}
1692
1693/*
1694 * Name: thread_add_turnstile_promotion
1695 *
1696 * Description: Add a turnstile to thread's inheritor list and update thread's priority.
1697 *
1698 * Arg1: thread
1699 * Arg2: turnstile
1700 *
1701 * Returns: TRUE: if the thread's priority has changed and needs propagation.
1702 * FALSE: if the thread's priority did not change or it does not need propagation.
1703 *
1704 * Condition: turnstile locked.
1705 */
1706static boolean_t
1707thread_add_turnstile_promotion(
1708 thread_t thread,
1709 struct turnstile *turnstile)
1710{
1711 boolean_t needs_update = FALSE;
1712
1713 /* Update the pairing heap */
1714 thread_lock(thread);
1715
1716 KERNEL_DEBUG_CONSTANT_IST(KDEBUG_TRACE,
1717 (TURNSTILE_CODE(TURNSTILE_HEAP_OPERATIONS, (TURNSTILE_ADDED_TO_THREAD_HEAP))) | DBG_FUNC_NONE,
1718 thread_tid(thread),
1719 VM_KERNEL_UNSLIDE_OR_PERM(turnstile),
1720 turnstile->ts_priority, 0, 0);
1721
1722 priority_queue_entry_init(&turnstile->ts_inheritor_links);
1723
1724 switch (turnstile_promote_policy[turnstile_get_type(turnstile)]) {
1725 case TURNSTILE_USER_PROMOTE:
1726 case TURNSTILE_USER_IPC_PROMOTE:
1727
1728 priority_queue_entry_set_sched_pri(&thread->base_inheritor_queue,
1729 &turnstile->ts_inheritor_links, turnstile->ts_priority, false);
1730 if (priority_queue_insert(que: &thread->base_inheritor_queue,
1731 elt: &turnstile->ts_inheritor_links)) {
1732 needs_update = thread_recompute_user_promotion_locked(thread);
1733 }
1734
1735 break;
1736 case TURNSTILE_KERNEL_PROMOTE:
1737
1738 priority_queue_entry_set_sched_pri(&thread->sched_inheritor_queue,
1739 &turnstile->ts_inheritor_links, turnstile->ts_priority, false);
1740 if (priority_queue_insert(que: &thread->sched_inheritor_queue,
1741 elt: &turnstile->ts_inheritor_links)) {
1742 needs_update = thread_recompute_kernel_promotion_locked(thread);
1743 }
1744
1745 break;
1746 default:
1747 panic("turnstile promotion for type %d not yet implemented", turnstile_get_type(turnstile));
1748 }
1749
1750 /* Update turnstile stats */
1751 if (!needs_update) {
1752 turnstile_stats_update(hop: 1,
1753 flags: thread_get_update_flags_for_turnstile_propagation_stoppage(thread) |
1754 TSU_TURNSTILE_ARG | TSU_BOOST_ARG,
1755 inheritor: turnstile);
1756 }
1757
1758 thread_unlock(thread);
1759
1760 return needs_update;
1761}
1762
1763/*
1764 * Name: thread_remove_turnstile_promotion
1765 *
1766 * Description: Remove turnstile from thread's inheritor list and update thread's priority.
1767 *
1768 * Arg1: thread
1769 * Arg2: turnstile
1770 *
1771 * Returns: TRUE: if the thread's priority has changed and needs propagation.
1772 * FALSE: if the thread's priority did not change or it does not need propagation.
1773 *
1774 * Condition: turnstile locked.
1775 */
1776static boolean_t
1777thread_remove_turnstile_promotion(
1778 thread_t thread,
1779 struct turnstile *turnstile)
1780{
1781 boolean_t needs_update = FALSE;
1782
1783 thread_lock(thread);
1784
1785 KERNEL_DEBUG_CONSTANT_IST(KDEBUG_TRACE,
1786 (TURNSTILE_CODE(TURNSTILE_HEAP_OPERATIONS, (TURNSTILE_REMOVED_FROM_THREAD_HEAP))) | DBG_FUNC_NONE,
1787 thread_tid(thread),
1788 VM_KERNEL_UNSLIDE_OR_PERM(turnstile),
1789 0, 0, 0);
1790
1791 /* Update the pairing heap */
1792
1793 switch (turnstile_promote_policy[turnstile_get_type(turnstile)]) {
1794 case TURNSTILE_USER_PROMOTE:
1795 case TURNSTILE_USER_IPC_PROMOTE:
1796 if (priority_queue_remove(que: &thread->base_inheritor_queue,
1797 elt: &turnstile->ts_inheritor_links)) {
1798 needs_update = thread_recompute_user_promotion_locked(thread);
1799 }
1800 break;
1801 case TURNSTILE_KERNEL_PROMOTE:
1802 if (priority_queue_remove(que: &thread->sched_inheritor_queue,
1803 elt: &turnstile->ts_inheritor_links)) {
1804 needs_update = thread_recompute_kernel_promotion_locked(thread);
1805 }
1806 break;
1807 default:
1808 panic("turnstile promotion for type %d not yet implemented", turnstile_get_type(turnstile));
1809 }
1810
1811 /* Update turnstile stats */
1812 if (!needs_update) {
1813 turnstile_stats_update(hop: 1,
1814 flags: thread_get_update_flags_for_turnstile_propagation_stoppage(thread) | TSU_TURNSTILE_ARG,
1815 inheritor: turnstile);
1816 }
1817
1818 thread_unlock(thread);
1819
1820 return needs_update;
1821}
1822
1823/*
1824 * Name: thread_needs_turnstile_promotion_update
1825 *
1826 * Description: Check if turnstile position in thread's inheritor list needs to be updated.
1827 *
1828 * Arg1: thread
1829 * Arg2: turnstile
1830 *
1831 * Returns: TRUE: if thread_update_turnstile_promotion needs to be called.
1832 * FALSE: otherwise.
1833 *
1834 * Condition: turnstile locked.
1835 */
1836static boolean_t
1837thread_needs_turnstile_promotion_update(
1838 thread_t thread __assert_only,
1839 struct turnstile *turnstile)
1840{
1841 boolean_t needs_update = FALSE;
1842 int turnstile_link_priority = 0;
1843
1844 switch (turnstile_promote_policy[turnstile_get_type(turnstile)]) {
1845 case TURNSTILE_USER_PROMOTE:
1846 case TURNSTILE_USER_IPC_PROMOTE:
1847 turnstile_link_priority = priority_queue_entry_sched_pri(
1848 &thread->base_inheritor_queue,
1849 &turnstile->ts_inheritor_links);
1850 break;
1851 case TURNSTILE_KERNEL_PROMOTE:
1852 turnstile_link_priority = priority_queue_entry_sched_pri(
1853 &thread->sched_inheritor_queue,
1854 &turnstile->ts_inheritor_links);
1855 break;
1856 default:
1857 panic("turnstile promotion for type %d not yet implemented", turnstile_get_type(turnstile));
1858 }
1859
1860 needs_update = (turnstile_link_priority == turnstile->ts_priority) ? FALSE : TRUE;
1861 return needs_update;
1862}
1863
1864/*
1865 * Name: thread_update_turnstile_promotion_locked
1866 *
1867 * Description: Update turnstile position in thread's inheritor list and update thread's priority.
1868 *
1869 * Arg1: thread
1870 * Arg2: turnstile
1871 *
1872 * Returns: TRUE: if the thread's priority has changed and needs propagation.
1873 * FALSE: if the thread's priority did not change or it does not need propagation.
1874 *
1875 * Condition: turnstile and thread are locked.
1876 */
1877static boolean_t
1878thread_update_turnstile_promotion_locked(
1879 thread_t thread,
1880 struct turnstile *turnstile)
1881{
1882 boolean_t needs_update = FALSE;
1883 int turnstile_link_priority = 0;
1884
1885 switch (turnstile_promote_policy[turnstile_get_type(turnstile)]) {
1886 case TURNSTILE_USER_PROMOTE:
1887 case TURNSTILE_USER_IPC_PROMOTE:
1888 turnstile_link_priority = priority_queue_entry_sched_pri(
1889 &thread->base_inheritor_queue,
1890 &turnstile->ts_inheritor_links);
1891
1892 if (turnstile_priority_queue_update_entry_key(q: &(thread->base_inheritor_queue),
1893 elt: &turnstile->ts_inheritor_links, pri: turnstile->ts_priority)) {
1894 needs_update = thread_recompute_user_promotion_locked(thread);
1895 }
1896 break;
1897 case TURNSTILE_KERNEL_PROMOTE:
1898 turnstile_link_priority = priority_queue_entry_sched_pri(
1899 &thread->sched_inheritor_queue,
1900 &turnstile->ts_inheritor_links);
1901
1902 if (turnstile_priority_queue_update_entry_key(q: &(thread->sched_inheritor_queue),
1903 elt: &turnstile->ts_inheritor_links, pri: turnstile->ts_priority)) {
1904 needs_update = thread_recompute_kernel_promotion_locked(thread);
1905 }
1906 break;
1907 default:
1908 panic("turnstile promotion for type %d not yet implemented", turnstile_get_type(turnstile));
1909 }
1910
1911 if (turnstile->ts_priority != turnstile_link_priority) {
1912 KERNEL_DEBUG_CONSTANT_IST(KDEBUG_TRACE,
1913 (TURNSTILE_CODE(TURNSTILE_HEAP_OPERATIONS, (TURNSTILE_MOVED_IN_THREAD_HEAP))) | DBG_FUNC_NONE,
1914 thread_tid(thread),
1915 VM_KERNEL_UNSLIDE_OR_PERM(turnstile),
1916 turnstile->ts_priority,
1917 turnstile_link_priority, 0);
1918 }
1919
1920 return needs_update;
1921}
1922
1923
1924/*
1925 * Name: thread_update_turnstile_promotion
1926 *
1927 * Description: Update turnstile position in thread's inheritor list and update thread's priority.
1928 *
1929 * Arg1: thread
1930 * Arg2: turnstile
1931 *
1932 * Returns: TRUE: if the thread's priority has changed and needs propagation.
1933 * FALSE: if the thread's priority did not change or it does not need propagation.
1934 *
1935 * Condition: turnstile locked.
1936 */
1937static boolean_t
1938thread_update_turnstile_promotion(
1939 thread_t thread,
1940 struct turnstile *turnstile)
1941{
1942 /* Before grabbing the thread lock, check if update is needed */
1943 boolean_t needs_update = thread_needs_turnstile_promotion_update(thread, turnstile);
1944
1945 if (!needs_update) {
1946 turnstile_stats_update(hop: 1, flags: TSU_NO_PRI_CHANGE_NEEDED |
1947 TSU_TURNSTILE_ARG | TSU_BOOST_ARG, inheritor: turnstile);
1948 return needs_update;
1949 }
1950
1951 thread_lock(thread);
1952
1953 /* Update the pairing heap */
1954 needs_update = thread_update_turnstile_promotion_locked(thread, turnstile);
1955
1956 /* Update turnstile stats */
1957 if (!needs_update) {
1958 turnstile_stats_update(hop: 1,
1959 flags: thread_get_update_flags_for_turnstile_propagation_stoppage(thread) |
1960 TSU_TURNSTILE_ARG | TSU_BOOST_ARG,
1961 inheritor: turnstile);
1962 }
1963
1964 thread_unlock(thread);
1965
1966 return needs_update;
1967}
1968
1969
1970/*
1971 * Name: thread_get_inheritor_turnstile_sched_priority
1972 *
1973 * Description: Get the max sched priority of all the inheritor turnstiles
1974 *
1975 * Arg1: thread
1976 *
1977 * Returns: Max sched priority of all the inheritor turnstiles.
1978 *
1979 * Condition: thread locked
1980 */
1981int
1982thread_get_inheritor_turnstile_sched_priority(thread_t thread)
1983{
1984 struct turnstile *max_turnstile;
1985
1986 max_turnstile = priority_queue_max(&thread->sched_inheritor_queue,
1987 struct turnstile, ts_inheritor_links);
1988
1989 if (max_turnstile) {
1990 return priority_queue_entry_sched_pri(
1991 &thread->sched_inheritor_queue,
1992 &max_turnstile->ts_inheritor_links);
1993 }
1994
1995 return 0;
1996}
1997
1998/*
1999 * Name: thread_get_inheritor_turnstile_base_priority
2000 *
2001 * Description: Get the max base priority of all the inheritor turnstiles
2002 *
2003 * Arg1: thread
2004 *
2005 * Returns: Max base priority of all the inheritor turnstiles.
2006 *
2007 * Condition: thread locked
2008 */
2009int
2010thread_get_inheritor_turnstile_base_priority(thread_t thread)
2011{
2012 struct turnstile *max_turnstile;
2013
2014 max_turnstile = priority_queue_max(&thread->base_inheritor_queue,
2015 struct turnstile, ts_inheritor_links);
2016
2017 if (max_turnstile) {
2018 return priority_queue_entry_sched_pri(
2019 &thread->base_inheritor_queue,
2020 &max_turnstile->ts_inheritor_links);
2021 }
2022
2023 return 0;
2024}
2025
2026
2027/*
2028 * Name: thread_get_waiting_turnstile
2029 *
2030 * Description: Get the turnstile if the thread is waiting on a turnstile.
2031 *
2032 * Arg1: thread
2033 *
2034 * Returns: turnstile: if the thread is blocked on a turnstile.
2035 * TURNSTILE_NULL: otherwise.
2036 *
2037 * Condition: thread locked.
2038 */
2039struct turnstile *
2040thread_get_waiting_turnstile(thread_t thread)
2041{
2042 waitq_t waitq = thread->waitq;
2043
2044 /* Check if the thread is on a waitq */
2045 if (waitq_is_null(wq: waitq)) {
2046 return TURNSTILE_NULL;
2047 }
2048
2049 switch (waitq_type(wq: waitq)) {
2050 case WQT_PORT:
2051 return waitq.wq_q->waitq_ts;
2052
2053 case WQT_TURNSTILE:
2054 return waitq_to_turnstile(waitq.wq_q);
2055
2056 default:
2057 return TURNSTILE_NULL;
2058 }
2059}
2060
2061/*
2062 * Name: turnstile_lookup_by_proprietor
2063 *
2064 * Description: Get turnstile for a proprietor from global
2065 * turnstile hash.
2066 *
2067 * Arg1: port
2068 * Arg2: turnstile_type_t type
2069 *
2070 * Returns: turnstile: if the proprietor has a turnstile.
2071 * TURNSTILE_NULL: otherwise.
2072 *
2073 * Condition: proprietor interlock held.
2074 */
2075struct turnstile *
2076turnstile_lookup_by_proprietor(uintptr_t proprietor, turnstile_type_t type)
2077{
2078 return turnstile_htable_lookup(proprietor, type);
2079}
2080
2081/*
2082 * Name: thread_get_update_flags_for_turnstile_propagation_stoppage
2083 *
2084 * Description: Get the turnstile stats flags based on the thread wait status.
2085 *
2086 * Arg1: thread
2087 *
2088 * Returns: TSU_THREAD_RUNNABLE: if the thread is runnable.
2089 * TSU_NO_TURNSTILE: if thread waiting on a regular waitq.
2090 * TSU_NO_PRI_CHANGE_NEEDED: otherwise.
2091 *
2092 * Condition: thread locked.
2093 */
2094static turnstile_stats_update_flags_t
2095thread_get_update_flags_for_turnstile_propagation_stoppage(thread_t thread)
2096{
2097 waitq_t waitq = thread->waitq;
2098
2099 /* Check if the thread is on a waitq */
2100 if (waitq_is_null(wq: waitq)) {
2101 return TSU_THREAD_RUNNABLE;
2102 }
2103
2104 /* Get the safeq if the waitq is a port queue */
2105 switch (waitq_type(wq: waitq)) {
2106 case WQT_PORT:
2107 if (waitq.wq_q->waitq_ts) {
2108 return TSU_NO_PRI_CHANGE_NEEDED;
2109 }
2110 return TSU_NO_TURNSTILE;
2111
2112 case WQT_TURNSTILE:
2113 /* Thread blocked on turnstile waitq but no propagation needed */
2114 return TSU_NO_PRI_CHANGE_NEEDED;
2115
2116 default:
2117 return TSU_NO_TURNSTILE;
2118 }
2119}
2120
2121
2122/*
2123 * Name: turnstile_get_update_flags_for_above_UI_pri_change
2124 *
2125 * Description: Get the turnstile stats flags based on the turnstile priority.
2126 *
2127 * Arg1: turnstile
2128 *
2129 * Returns: TSU_ABOVE_UI_PRI_CHANGE: if turnstile priority is above 47 and it is not an ulock.
2130 * TSU_FLAGS_NONE: otherwise.
2131 *
2132 * Condition: turnstile locked.
2133 */
2134static turnstile_stats_update_flags_t
2135turnstile_get_update_flags_for_above_UI_pri_change(struct turnstile *turnstile)
2136{
2137 if (turnstile->ts_priority >
2138 (thread_qos_policy_params.qos_pri[THREAD_QOS_USER_INTERACTIVE] + 1) &&
2139 turnstile_get_type(turnstile) != TURNSTILE_ULOCK) {
2140 return TSU_ABOVE_UI_PRI_CHANGE;
2141 }
2142
2143 return TSU_FLAGS_NONE;
2144}
2145
2146
2147/*
2148 * Name: workq_add_turnstile_promotion
2149 *
2150 * Description: Connect the workqueue turnstile to the workqueue as a fake
2151 * inheritor
2152 *
2153 * Arg1: workqueue
2154 * Arg2: turnstile
2155 *
2156 * Condition: turnstile locked.
2157 */
2158static boolean_t
2159workq_add_turnstile_promotion(
2160 struct workqueue *wq_inheritor __unused,
2161 struct turnstile *turnstile)
2162{
2163 /*
2164 * If the push is higher than MAXPRI_THROTTLE then the workqueue should
2165 * bring up a thread.
2166 */
2167 return turnstile->ts_priority > MAXPRI_THROTTLE;
2168}
2169
2170/*
2171 * Name: turnstile_need_turnstile_promotion_update
2172 *
2173 * Description: Check if turnstile position in turnstile's inheritor list needs to be updated.
2174 *
2175 * Arg1: dst turnstile
2176 * Arg2: src turnstile
2177 *
2178 * Returns: TRUE: if turnstile_update_turnstile_promotion needs to be called.
2179 * FALSE: otherwise.
2180 *
2181 * Condition: src turnstile locked.
2182 */
2183static boolean_t
2184turnstile_need_turnstile_promotion_update(
2185 struct turnstile *dst_turnstile __assert_only,
2186 struct turnstile *src_turnstile)
2187{
2188 int src_turnstile_link_priority;
2189 boolean_t needs_update = FALSE;
2190
2191 src_turnstile_link_priority = priority_queue_entry_sched_pri(
2192 &dst_turnstile->ts_inheritor_queue,
2193 &src_turnstile->ts_inheritor_links);
2194
2195 needs_update = (src_turnstile_link_priority == src_turnstile->ts_priority) ? FALSE : TRUE;
2196 return needs_update;
2197}
2198
2199/*
2200 * Name: turnstile_update_turnstile_promotion_locked
2201 *
2202 * Description: Update dst turnstile's inheritor link since src turnstile's
2203 * promote priority has changed.
2204 *
2205 * Arg1: dst turnstile
2206 * Arg2: src turnstile
2207 *
2208 * Returns: TRUE: if the dst turnstile priority has changed and needs propagation.
2209 * FALSE: if the dst turnstile priority did not change or it does not need propagation.
2210 *
2211 * Condition: src and dst turnstile locked.
2212 */
2213static boolean_t
2214turnstile_update_turnstile_promotion_locked(
2215 struct turnstile *dst_turnstile,
2216 struct turnstile *src_turnstile)
2217{
2218 int src_turnstile_link_priority;
2219 src_turnstile_link_priority = priority_queue_entry_sched_pri(
2220 &dst_turnstile->ts_inheritor_queue,
2221 &src_turnstile->ts_inheritor_links);
2222
2223 if (src_turnstile->ts_priority != src_turnstile_link_priority) {
2224 KERNEL_DEBUG_CONSTANT_IST(KDEBUG_TRACE,
2225 (TURNSTILE_CODE(TURNSTILE_HEAP_OPERATIONS, (TURNSTILE_MOVED_IN_TURNSTILE_HEAP))) | DBG_FUNC_NONE,
2226 VM_KERNEL_UNSLIDE_OR_PERM(dst_turnstile),
2227 VM_KERNEL_UNSLIDE_OR_PERM(src_turnstile),
2228 src_turnstile->ts_priority, src_turnstile_link_priority, 0);
2229 }
2230
2231 if (!turnstile_priority_queue_update_entry_key(
2232 q: &dst_turnstile->ts_inheritor_queue, elt: &src_turnstile->ts_inheritor_links,
2233 pri: src_turnstile->ts_priority)) {
2234 return FALSE;
2235 }
2236
2237 /* Update dst turnstile's priority */
2238 return turnstile_recompute_priority_locked(turnstile: dst_turnstile);
2239}
2240
2241/*
2242 * Name: turnstile_update_turnstile_promotion
2243 *
2244 * Description: Update dst turnstile's inheritor link since src turnstile's
2245 * promote priority has changed.
2246 *
2247 * Arg1: dst turnstile
2248 * Arg2: src turnstile
2249 *
2250 * Returns: TRUE: if the dst turnstile priority has changed and needs propagation.
2251 * FALSE: if the dst turnstile priority did not change or it does not need propagation.
2252 *
2253 * Condition: src turnstile locked.
2254 */
2255static boolean_t
2256turnstile_update_turnstile_promotion(
2257 struct turnstile *dst_turnstile,
2258 struct turnstile *src_turnstile)
2259{
2260 /* Check if update is needed before grabbing the src turnstile lock */
2261 boolean_t needs_update = turnstile_need_turnstile_promotion_update(dst_turnstile, src_turnstile);
2262 if (!needs_update) {
2263 turnstile_stats_update(hop: 1, flags: TSU_NO_PRI_CHANGE_NEEDED |
2264 TSU_TURNSTILE_ARG | TSU_BOOST_ARG,
2265 inheritor: src_turnstile);
2266 return needs_update;
2267 }
2268
2269 /* Update the pairing heap */
2270 waitq_lock(wq: &dst_turnstile->ts_waitq);
2271 needs_update = turnstile_update_turnstile_promotion_locked(dst_turnstile, src_turnstile);
2272
2273 /* Update turnstile stats */
2274 if (!needs_update) {
2275 turnstile_stats_update(hop: 1,
2276 flags: (dst_turnstile->ts_inheritor ? TSU_NO_PRI_CHANGE_NEEDED : TSU_NO_INHERITOR) |
2277 TSU_TURNSTILE_ARG | TSU_BOOST_ARG, inheritor: src_turnstile);
2278 }
2279 waitq_unlock(wq: &dst_turnstile->ts_waitq);
2280 return needs_update;
2281}
2282
2283/*
2284 * Name: turnstile_add_turnstile_promotion
2285 *
2286 * Description: Add src turnstile to dst turnstile's inheritor link
2287 * and update dst turnstile's priority.
2288 *
2289 * Arg1: dst turnstile
2290 * Arg2: src turnstile
2291 *
2292 * Returns: TRUE: if the dst turnstile priority has changed and needs propagation.
2293 * FALSE: if the dst turnstile priority did not change or it does not need propagation.
2294 *
2295 * Condition: src turnstile locked.
2296 */
2297static boolean_t
2298turnstile_add_turnstile_promotion(
2299 struct turnstile *dst_turnstile,
2300 struct turnstile *src_turnstile)
2301{
2302 boolean_t needs_update = FALSE;
2303
2304 /* Update the pairing heap */
2305 waitq_lock(wq: &dst_turnstile->ts_waitq);
2306
2307 KERNEL_DEBUG_CONSTANT_IST(KDEBUG_TRACE,
2308 (TURNSTILE_CODE(TURNSTILE_HEAP_OPERATIONS, (TURNSTILE_ADDED_TO_TURNSTILE_HEAP))) | DBG_FUNC_NONE,
2309 VM_KERNEL_UNSLIDE_OR_PERM(dst_turnstile),
2310 VM_KERNEL_UNSLIDE_OR_PERM(src_turnstile),
2311 src_turnstile->ts_priority, 0, 0);
2312
2313 priority_queue_entry_init(&src_turnstile->ts_inheritor_links);
2314 priority_queue_entry_set_sched_pri(&dst_turnstile->ts_inheritor_queue,
2315 &src_turnstile->ts_inheritor_links, src_turnstile->ts_priority, false);
2316 if (priority_queue_insert(que: &dst_turnstile->ts_inheritor_queue,
2317 elt: &src_turnstile->ts_inheritor_links)) {
2318 /* Update dst turnstile priority */
2319 needs_update = turnstile_recompute_priority_locked(turnstile: dst_turnstile);
2320 }
2321
2322 /* Update turnstile stats */
2323 if (!needs_update) {
2324 turnstile_stats_update(hop: 1,
2325 flags: (dst_turnstile->ts_inheritor ? TSU_NO_PRI_CHANGE_NEEDED : TSU_NO_INHERITOR) |
2326 TSU_TURNSTILE_ARG | TSU_BOOST_ARG, inheritor: src_turnstile);
2327 }
2328
2329 waitq_unlock(wq: &dst_turnstile->ts_waitq);
2330 return needs_update;
2331}
2332
2333/*
2334 * Name: turnstile_remove_turnstile_promotion
2335 *
2336 * Description: Remove src turnstile from dst turnstile's inheritor link
2337 * and update dst turnstile's priority.
2338 *
2339 * Arg1: dst turnstile
2340 * Arg2: src turnstile
2341 *
2342 * Returns: TRUE: if the dst turnstile priority has changed and needs propagation.
2343 * FALSE: if the dst turnstile priority did not change or it does not need propagation.
2344 *
2345 * Condition: src turnstile locked.
2346 */
2347static boolean_t
2348turnstile_remove_turnstile_promotion(
2349 struct turnstile *dst_turnstile,
2350 struct turnstile *src_turnstile)
2351{
2352 boolean_t needs_update = FALSE;
2353
2354 /* Update the pairing heap */
2355 waitq_lock(wq: &dst_turnstile->ts_waitq);
2356
2357 KERNEL_DEBUG_CONSTANT_IST(KDEBUG_TRACE,
2358 (TURNSTILE_CODE(TURNSTILE_HEAP_OPERATIONS, (TURNSTILE_REMOVED_FROM_TURNSTILE_HEAP))) | DBG_FUNC_NONE,
2359 VM_KERNEL_UNSLIDE_OR_PERM(dst_turnstile),
2360 VM_KERNEL_UNSLIDE_OR_PERM(src_turnstile),
2361 0, 0, 0);
2362
2363 if (priority_queue_remove(que: &dst_turnstile->ts_inheritor_queue,
2364 elt: &src_turnstile->ts_inheritor_links)) {
2365 /* Update dst turnstile priority */
2366 needs_update = turnstile_recompute_priority_locked(turnstile: dst_turnstile);
2367 }
2368
2369 /* Update turnstile stats */
2370 if (!needs_update) {
2371 turnstile_stats_update(hop: 1,
2372 flags: (dst_turnstile->ts_inheritor ? TSU_NO_PRI_CHANGE_NEEDED : TSU_NO_INHERITOR) |
2373 TSU_TURNSTILE_ARG, inheritor: src_turnstile);
2374 }
2375
2376 waitq_unlock(wq: &dst_turnstile->ts_waitq);
2377 return needs_update;
2378}
2379
2380/*
2381 * Name: turnstile_compute_thread_push
2382 *
2383 * Description: Compute the priority at which the thread will push
2384 * on the turnstile.
2385 *
2386 * Arg1: turnstile
2387 * Arg2: thread
2388 *
2389 * Condition: wq locked
2390 */
2391static int
2392turnstile_compute_thread_push(
2393 struct turnstile *turnstile,
2394 thread_t thread)
2395{
2396 int priority = 0;
2397 switch (turnstile_promote_policy[turnstile_get_type(turnstile)]) {
2398 case TURNSTILE_USER_PROMOTE:
2399 case TURNSTILE_USER_IPC_PROMOTE:
2400 priority = thread->base_pri;
2401 break;
2402 case TURNSTILE_KERNEL_PROMOTE:
2403 /*
2404 * Ideally this should be policy based
2405 * according to the turnstile type.
2406 *
2407 * The priority with which each thread pushes on
2408 * a primitive should be primitive dependent.
2409 */
2410 priority = thread->sched_pri;
2411 priority = MAX(priority, thread->base_pri);
2412 priority = MAX(priority, BASEPRI_DEFAULT);
2413 priority = MIN(priority, MAXPRI_PROMOTE);
2414 break;
2415 default:
2416 panic("turnstile promotion for type %d not yet implemented", turnstile_get_type(turnstile));
2417 }
2418
2419 return priority;
2420}
2421
2422/*
2423 * Name: turnstile_waitq_add_thread_priority_queue
2424 *
2425 * Description: add thread to the turnstile wq
2426 *
2427 * Arg1: turnstile wq
2428 * Arg2: thread to add
2429 *
2430 * Condition: wq locked
2431 */
2432void
2433turnstile_waitq_add_thread_priority_queue(
2434 struct waitq *wq,
2435 thread_t thread)
2436{
2437 struct turnstile *turnstile = waitq_to_turnstile(wq);
2438 int priority = turnstile_compute_thread_push(turnstile, thread);
2439
2440 KERNEL_DEBUG_CONSTANT_IST(KDEBUG_TRACE,
2441 (TURNSTILE_CODE(TURNSTILE_HEAP_OPERATIONS, (THREAD_ADDED_TO_TURNSTILE_WAITQ))) | DBG_FUNC_NONE,
2442 VM_KERNEL_UNSLIDE_OR_PERM(turnstile),
2443 thread_tid(thread),
2444 priority, 0, 0);
2445 /*
2446 * For turnstile queues (which use priority queues),
2447 * insert the thread in the heap based on its priority.
2448 * Note that the priority queue implementation
2449 * is currently not stable, so does not maintain fifo for
2450 * threads at the same pri. Also, if the pri
2451 * of the thread changes while its blocked in the waitq,
2452 * the thread position should be updated in the priority
2453 * queue by calling priority queue increase/decrease
2454 * operations.
2455 */
2456 priority_queue_entry_init(&thread->wait_prioq_links);
2457 priority_queue_entry_set_sched_pri(&wq->waitq_prio_queue,
2458 &thread->wait_prioq_links, priority, false);
2459 priority_queue_insert(que: &wq->waitq_prio_queue,
2460 elt: &thread->wait_prioq_links);
2461}
2462
2463/*
2464 * Name: turnstile_recompute_priority_locked
2465 *
2466 * Description: Update turnstile priority based
2467 * on highest waiter thread and highest blocking
2468 * turnstile.
2469 *
2470 * Args: turnstile
2471 *
2472 * Returns: TRUE: if the turnstile priority changed and needs propagation.
2473 * FALSE: if the turnstile priority did not change or it does not need propagation.
2474 *
2475 * Condition: turnstile locked
2476 */
2477boolean_t
2478turnstile_recompute_priority_locked(
2479 struct turnstile *turnstile)
2480{
2481 int old_priority;
2482 int new_priority;
2483 boolean_t needs_priority_update = FALSE;
2484 thread_t max_thread = THREAD_NULL;
2485 struct turnstile *max_turnstile;
2486 int thread_max_pri = 0;
2487 int turnstile_max_pri = 0;
2488
2489 switch (turnstile_promote_policy[turnstile_get_type(turnstile)]) {
2490 case TURNSTILE_USER_PROMOTE:
2491 case TURNSTILE_USER_IPC_PROMOTE:
2492 case TURNSTILE_KERNEL_PROMOTE:
2493
2494 old_priority = turnstile->ts_priority;
2495
2496 max_thread = priority_queue_max(&turnstile->ts_waitq.waitq_prio_queue,
2497 struct thread, wait_prioq_links);
2498
2499 if (max_thread) {
2500 thread_max_pri = priority_queue_entry_sched_pri(
2501 &turnstile->ts_waitq.waitq_prio_queue,
2502 &max_thread->wait_prioq_links);
2503 }
2504
2505 max_turnstile = priority_queue_max(&turnstile->ts_inheritor_queue,
2506 struct turnstile, ts_inheritor_links);
2507
2508 if (max_turnstile) {
2509 assert(turnstile_promote_policy[turnstile_get_type(turnstile)] != TURNSTILE_KERNEL_PROMOTE);
2510 turnstile_max_pri = priority_queue_entry_sched_pri(
2511 &turnstile->ts_inheritor_queue,
2512 &max_turnstile->ts_inheritor_links);
2513 }
2514
2515 new_priority = max(thread_max_pri, turnstile_max_pri);
2516 turnstile->ts_priority = (uint8_t)new_priority;
2517
2518 if (old_priority != new_priority) {
2519 KERNEL_DEBUG_CONSTANT_IST(KDEBUG_TRACE,
2520 (TURNSTILE_CODE(TURNSTILE_PRIORITY_OPERATIONS,
2521 (TURNSTILE_PRIORITY_CHANGE))) | DBG_FUNC_NONE,
2522 VM_KERNEL_UNSLIDE_OR_PERM(turnstile),
2523 new_priority,
2524 old_priority,
2525 0, 0);
2526 }
2527 needs_priority_update = (!(old_priority == new_priority)) &&
2528 (turnstile->ts_inheritor != NULL);
2529 break;
2530
2531 case TURNSTILE_PROMOTE_NONE:
2532 /* The turnstile was repurposed, do nothing */
2533 break;
2534
2535 default:
2536
2537 panic("Needs implementation for turnstile_recompute_priority");
2538 break;
2539 }
2540 return needs_priority_update;
2541}
2542
2543
2544/*
2545 * Name: turnstile_recompute_priority
2546 *
2547 * Description: Update turnstile priority based
2548 * on highest waiter thread and highest blocking
2549 * turnstile.
2550 *
2551 * Args: turnstile
2552 *
2553 * Returns: TRUE: if the turnstile priority changed and needs propagation.
2554 * FALSE: if the turnstile priority did not change or it does not need propagation.
2555 */
2556boolean_t
2557turnstile_recompute_priority(
2558 struct turnstile *turnstile)
2559{
2560 boolean_t needs_priority_update = FALSE;
2561 spl_t s = splsched();
2562
2563 waitq_lock(wq: &turnstile->ts_waitq);
2564
2565 needs_priority_update = turnstile_recompute_priority_locked(turnstile);
2566
2567 waitq_unlock(wq: &turnstile->ts_waitq);
2568 splx(s);
2569 return needs_priority_update;
2570}
2571
2572
2573/*
2574 * Name: turnstile_workq_proprietor_of_max_turnstile
2575 *
2576 * Description: Returns the highest priority and proprietor of a turnstile
2577 * pushing on a workqueue turnstile.
2578 *
2579 * This will not return waiters that are at priority
2580 * MAXPRI_THROTTLE or lower.
2581 *
2582 * Args: turnstile
2583 *
2584 * Returns:
2585 * Priority of the max entry, or 0
2586 * Pointer to the max entry proprietor
2587 */
2588int
2589turnstile_workq_proprietor_of_max_turnstile(
2590 struct turnstile *turnstile,
2591 uintptr_t *proprietor_out)
2592{
2593 struct turnstile *max_turnstile;
2594 int max_priority = 0;
2595 uintptr_t proprietor = 0;
2596
2597 assert(turnstile_get_type(turnstile) == TURNSTILE_WORKQS);
2598
2599 spl_t s = splsched();
2600
2601 waitq_lock(wq: &turnstile->ts_waitq);
2602
2603 max_turnstile = priority_queue_max(&turnstile->ts_inheritor_queue,
2604 struct turnstile, ts_inheritor_links);
2605 if (max_turnstile) {
2606 max_priority = priority_queue_entry_sched_pri(
2607 &turnstile->ts_inheritor_queue,
2608 &max_turnstile->ts_inheritor_links);
2609 proprietor = max_turnstile->ts_proprietor;
2610 }
2611
2612 waitq_unlock(wq: &turnstile->ts_waitq);
2613 splx(s);
2614
2615 if (max_priority <= MAXPRI_THROTTLE) {
2616 max_priority = 0;
2617 proprietor = 0;
2618 }
2619 if (proprietor_out) {
2620 *proprietor_out = proprietor;
2621 }
2622 return max_priority;
2623}
2624
2625/*
2626 * Name: turnstile_workloop_pusher_info
2627 *
2628 * Description: Returns the priority of the turnstile push for a workloop,
2629 * and the thread or knote responsible for this push.
2630 *
2631 * Args: workloop turnstile
2632 *
2633 * Returns:
2634 * Priority of the push or 0
2635 * Thread (with a +1 reference) with that push or THREAD_NULL.
2636 * Port (with a +1 reference) with that push, or IP_NULL.
2637 * Sync IPC knote with the highest push (or NULL)
2638 */
2639int
2640turnstile_workloop_pusher_info(
2641 struct turnstile *turnstile,
2642 thread_t *thread_out,
2643 ipc_port_t *port_out,
2644 struct knote **knote_out)
2645{
2646 struct turnstile *max_ts;
2647 thread_t max_thread;
2648 int max_thread_pri = 0;
2649 int max_ts_pri = 0;
2650 ipc_port_t port;
2651
2652 assert(turnstile_get_type(turnstile) == TURNSTILE_WORKLOOPS);
2653
2654 spl_t s = splsched();
2655 waitq_lock(wq: &turnstile->ts_waitq);
2656
2657 max_thread = priority_queue_max(&turnstile->ts_waitq.waitq_prio_queue,
2658 struct thread, wait_prioq_links);
2659 if (max_thread) {
2660 max_thread_pri = priority_queue_entry_sched_pri(
2661 &turnstile->ts_waitq.waitq_prio_queue,
2662 &max_thread->wait_prioq_links);
2663 }
2664
2665 max_ts = priority_queue_max(&turnstile->ts_inheritor_queue,
2666 struct turnstile, ts_inheritor_links);
2667 if (max_ts) {
2668 max_ts_pri = priority_queue_entry_sched_pri(
2669 &turnstile->ts_inheritor_queue,
2670 &max_ts->ts_inheritor_links);
2671 }
2672
2673 /*
2674 * Reasons to push on a workloop turnstile are:
2675 *
2676 * 1. threads in dispatch sync
2677 *
2678 * 2. sync IPC pushes, which in turn have 4 sub-cases:
2679 *
2680 * 2.a. special reply port or receive right pushing through a knote
2681 * turnstile,
2682 *
2683 * 2.b. special reply port stashed on a knote, pushing on the workloop
2684 * directly,
2685 *
2686 * 2.c. receive right stashed on a knote, pushing on the workloop
2687 * directly,
2688 *
2689 * 2.d. a receive right monitored by a knote, pushing on the workloop
2690 * directly.
2691 *
2692 * See ipc_port_send_update_inheritor(), ipc_port_recv_update_inheritor().
2693 *
2694 * Note: dereferencing the knote in the caller is safe provided this
2695 * function i scalled under the proper interlocks (the filt_wllock + req
2696 * lock) which serializes with the knote going away.
2697 */
2698 if (max_thread_pri > max_ts_pri) {
2699 thread_reference(thread: max_thread);
2700 *thread_out = max_thread;
2701 *port_out = NULL;
2702 *knote_out = NULL;
2703 } else if (max_ts_pri) {
2704 switch (turnstile_get_type(turnstile: max_ts)) {
2705 case TURNSTILE_KNOTE:
2706 /* 2.a. */
2707 *thread_out = THREAD_NULL;
2708 *port_out = IP_NULL;
2709 *knote_out = (struct knote *)max_ts->ts_proprietor;
2710 break;
2711
2712 case TURNSTILE_SYNC_IPC:
2713 /* 2.[bcd] */
2714 port = (ipc_port_t)max_ts->ts_proprietor;
2715 ip_reference(port);
2716 *thread_out = THREAD_NULL;
2717 *port_out = port;
2718 *knote_out = NULL;
2719 break;
2720
2721 default:
2722 panic("Unexpected type for turnstile %p", max_ts);
2723 }
2724 } else {
2725 *thread_out = THREAD_NULL;
2726 *port_out = IP_NULL;
2727 *knote_out = NULL;
2728 }
2729
2730 waitq_unlock(wq: &turnstile->ts_waitq);
2731 splx(s);
2732
2733 return max(max_thread_pri, max_ts_pri);
2734}
2735
2736/*
2737 * Name: turnstile_has_waiters
2738 *
2739 * Description: returns if there are waiters on the turnstile
2740 *
2741 * Arg1: turnstile: turnstile
2742 *
2743 * Returns: TRUE if there are waiters, FALSE otherwise.
2744 */
2745
2746boolean_t
2747turnstile_has_waiters(struct turnstile *turnstile)
2748{
2749 boolean_t ret;
2750
2751 spl_t s = splsched();
2752 waitq_lock(wq: &turnstile->ts_waitq);
2753 ret = !priority_queue_empty(&turnstile->ts_waitq.waitq_prio_queue);
2754 waitq_unlock(wq: &turnstile->ts_waitq);
2755 splx(s);
2756
2757 return ret;
2758}
2759
2760/*
2761 * Name: turnstile_update_inheritor_priority_chain
2762 *
2763 * Description: Update turnstile inheritor's priority and propagate
2764 * the priority if the inheritor is blocked on a turnstile.
2765 *
2766 * Arg1: inheritor
2767 * Arg2: inheritor flags
2768 *
2769 * Returns: None.
2770 */
2771static void
2772turnstile_update_inheritor_priority_chain(
2773 turnstile_inheritor_t inheritor,
2774 turnstile_update_flags_t turnstile_flags)
2775{
2776 struct turnstile *turnstile = TURNSTILE_NULL;
2777 thread_t thread = THREAD_NULL;
2778 int total_hop = 0, thread_hop = 0;
2779 spl_t s;
2780 turnstile_stats_update_flags_t tsu_flags = ((turnstile_flags & TURNSTILE_UPDATE_BOOST) ?
2781 TSU_BOOST_ARG : TSU_FLAGS_NONE) | TSU_PRI_PROPAGATION;
2782
2783 if (inheritor == NULL) {
2784 return;
2785 }
2786
2787 s = splsched();
2788
2789 if (turnstile_flags & TURNSTILE_INHERITOR_THREAD) {
2790 thread = inheritor;
2791 thread_lock(thread);
2792 thread_recompute_user_promotion_locked(thread);
2793 thread_recompute_kernel_promotion_locked(thread);
2794 } else if (turnstile_flags & TURNSTILE_INHERITOR_TURNSTILE) {
2795 turnstile = inheritor;
2796 waitq_lock(wq: &turnstile->ts_waitq);
2797 turnstile_recompute_priority_locked(turnstile);
2798 tsu_flags |= turnstile_get_update_flags_for_above_UI_pri_change(turnstile);
2799 } else {
2800 /*
2801 * we should never call turnstile_update_inheritor_priority_chain()
2802 * for a workqueue, they have no "chain" after them.
2803 */
2804 assert((turnstile_flags & TURNSTILE_INHERITOR_WORKQ) == 0);
2805 }
2806
2807 while (turnstile != TURNSTILE_NULL || thread != THREAD_NULL) {
2808 if (turnstile != TURNSTILE_NULL) {
2809 if (turnstile->ts_inheritor == NULL) {
2810 turnstile_stats_update(hop: total_hop + 1, flags: TSU_NO_INHERITOR |
2811 TSU_TURNSTILE_ARG | tsu_flags,
2812 inheritor: turnstile);
2813 waitq_unlock(wq: &turnstile->ts_waitq);
2814 turnstile = TURNSTILE_NULL;
2815 break;
2816 }
2817 if (turnstile->ts_inheritor_flags & TURNSTILE_INHERITOR_THREAD) {
2818 turnstile_update_inheritor_thread_priority_chain(in_turnstile: &turnstile, out_thread: &thread,
2819 total_hop, tsu_flags);
2820 } else if (turnstile->ts_inheritor_flags & TURNSTILE_INHERITOR_TURNSTILE) {
2821 turnstile_update_inheritor_turnstile_priority_chain(in_out_turnstile: &turnstile,
2822 total_hop, tsu_flags);
2823 } else if (turnstile->ts_inheritor_flags & TURNSTILE_INHERITOR_WORKQ) {
2824 turnstile_update_inheritor_workq_priority_chain(in_turnstile: turnstile, s);
2825 turnstile_stats_update(hop: total_hop + 1, flags: TSU_NO_PRI_CHANGE_NEEDED | tsu_flags,
2826 NULL);
2827 return;
2828 } else {
2829 panic("Inheritor flags not passed in turnstile_update_inheritor");
2830 }
2831 } else if (thread != THREAD_NULL) {
2832 thread_update_waiting_turnstile_priority_chain(in_thread: &thread, out_turnstile: &turnstile,
2833 thread_hop, total_hop, tsu_flags);
2834 thread_hop++;
2835 }
2836 total_hop++;
2837 }
2838
2839 splx(s);
2840 return;
2841}
2842
2843/*
2844 * Name: turnstile_update_inheritor_complete
2845 *
2846 * Description: Update turnstile inheritor's priority and propagate the
2847 * priority if the inheritor is blocked on a turnstile.
2848 * Consumes thread ref of old inheritor returned by
2849 * turnstile_update_inheritor. Recursive priority update
2850 * will only happen when called with interlock dropped.
2851 *
2852 * Args:
2853 * Arg1: turnstile
2854 * Arg2: interlock held
2855 *
2856 * Returns: None.
2857 */
2858void
2859turnstile_update_inheritor_complete(
2860 struct turnstile *turnstile,
2861 turnstile_update_complete_flags_t flags __unused)
2862{
2863 thread_t thread = current_thread();
2864
2865 turnstile_update_flags_t inheritor_flags = thread->inheritor_flags;
2866
2867 turnstile_cleanup();
2868
2869 /* Perform priority update for new inheritor */
2870 if (inheritor_flags & TURNSTILE_NEEDS_PRI_UPDATE) {
2871 turnstile_update_inheritor_priority_chain(inheritor: turnstile,
2872 turnstile_flags: TURNSTILE_INHERITOR_TURNSTILE | TURNSTILE_UPDATE_BOOST);
2873 }
2874}
2875
2876/*
2877 * Name: turnstile_cleanup
2878 *
2879 * Description: Update priority of a turnstile inheritor
2880 * if needed.
2881 *
2882 * Args: inheritor and flags passed on thread struct.
2883 *
2884 * Returns: None.
2885 */
2886void
2887turnstile_cleanup(void)
2888{
2889 thread_t thread = current_thread();
2890
2891 /* Get the old inheritor from calling thread struct */
2892 turnstile_inheritor_t old_inheritor = thread->inheritor;
2893 turnstile_update_flags_t inheritor_flags = thread->inheritor_flags;
2894 thread->inheritor = THREAD_NULL;
2895 thread->inheritor_flags = TURNSTILE_UPDATE_FLAGS_NONE;
2896
2897 if (old_inheritor == TURNSTILE_INHERITOR_NULL) {
2898 /* no cleanup to do */
2899 return;
2900 }
2901
2902 /* Perform priority demotion for old inheritor */
2903 if (inheritor_flags & TURNSTILE_INHERITOR_NEEDS_PRI_UPDATE) {
2904 turnstile_update_inheritor_priority_chain(inheritor: old_inheritor,
2905 turnstile_flags: inheritor_flags);
2906 }
2907
2908 /* Drop thread reference for old inheritor */
2909 if (inheritor_flags & TURNSTILE_INHERITOR_THREAD) {
2910 thread_deallocate_safe(thread: old_inheritor);
2911 } else if (inheritor_flags & TURNSTILE_INHERITOR_TURNSTILE) {
2912 turnstile_deallocate_safe(turnstile: (struct turnstile *)old_inheritor);
2913 } else if (inheritor_flags & TURNSTILE_INHERITOR_WORKQ) {
2914 workq_deallocate_safe(wq: (struct workqueue *)old_inheritor);
2915 } else {
2916 panic("Inheritor flags lost along the way");
2917 }
2918}
2919
2920/*
2921 * Name: turnstile_update_thread_priority_chain
2922 *
2923 * Description: Priority of a thread blocked on a turnstile
2924 * has changed, update the turnstile priority.
2925 *
2926 * Arg1: thread: thread whose priority has changed.
2927 *
2928 * Returns: None.
2929 */
2930void
2931turnstile_update_thread_priority_chain(thread_t thread)
2932{
2933 turnstile_update_inheritor_priority_chain(inheritor: thread,
2934 turnstile_flags: TURNSTILE_INHERITOR_THREAD | TURNSTILE_UPDATE_BOOST);
2935}
2936
2937/*
2938 * Name: turnstile_update_inheritor_workq_priority_chain
2939 *
2940 * Description: Helper function to update turnstile's inheritor(workq)
2941 * priority and possibly redrive thread creation
2942 *
2943 * Arg1: turnstile: turnstile
2944 * Arg2: s: whether iterrupts are disabled.
2945 *
2946 * Condition: turnstile is locked on entry, it is unlocked on exit,
2947 * and interrupts re-enabled.
2948 */
2949static void
2950turnstile_update_inheritor_workq_priority_chain(struct turnstile *turnstile, spl_t s)
2951{
2952 struct workqueue *wq = turnstile->ts_inheritor;
2953 bool workq_lock_held = workq_is_current_thread_updating_turnstile(wq);
2954
2955 if (__improbable(turnstile->ts_priority <= MAXPRI_THROTTLE)) {
2956 waitq_unlock(wq: &turnstile->ts_waitq);
2957 splx(s);
2958 return;
2959 }
2960
2961 if (!workq_lock_held) {
2962 workq_reference(wq);
2963 disable_preemption();
2964 }
2965 waitq_unlock(wq: &turnstile->ts_waitq);
2966 splx(s);
2967
2968 workq_schedule_creator_turnstile_redrive(wq, locked: workq_lock_held);
2969
2970 if (!workq_lock_held) {
2971 enable_preemption();
2972 workq_deallocate_safe(wq);
2973 }
2974}
2975
2976/*
2977 * Name: turnstile_update_inheritor_thread_priority_chain
2978 *
2979 * Description: Helper function to update turnstile's inheritor(thread)
2980 * priority.
2981 *
2982 * Arg1: in_turnstile: address to turnstile
2983 * Arg2: out_thread: address to return the thread inheritor
2984 * Arg3: thread_hop: number to thread hop in propagation chain
2985 * Arg4: tsu_flags: turnstile update flags
2986 *
2987 * Returns: Implicit returns locked thread in out_thread if it needs
2988 * further propagation.
2989 *
2990 * Condition: *in_turnstile is locked on entry, it is unlocked on exit and
2991 * *in_turnstile is set to NULL.
2992 */
2993static void
2994turnstile_update_inheritor_thread_priority_chain(
2995 struct turnstile **in_turnstile,
2996 thread_t *out_thread,
2997 int total_hop,
2998 turnstile_stats_update_flags_t tsu_flags)
2999{
3000 boolean_t needs_update = FALSE;
3001 struct turnstile *turnstile = *in_turnstile;
3002 thread_t thread_inheritor = turnstile->ts_inheritor;
3003 boolean_t first_update = !total_hop;
3004
3005 assert(turnstile->ts_inheritor_flags & TURNSTILE_INHERITOR_THREAD);
3006 *in_turnstile = TURNSTILE_NULL;
3007
3008 /* Check if update is needed before grabbing the thread lock */
3009 needs_update = thread_needs_turnstile_promotion_update(thread: thread_inheritor, turnstile);
3010 if (!needs_update && !first_update) {
3011 turnstile_stats_update(hop: total_hop + 1, flags: TSU_NO_PRI_CHANGE_NEEDED |
3012 TSU_TURNSTILE_ARG | tsu_flags, inheritor: turnstile);
3013 waitq_unlock(wq: &turnstile->ts_waitq);
3014 return;
3015 }
3016
3017 thread_lock(thread_inheritor);
3018
3019 /* adjust turnstile position in the thread's inheritor list */
3020 needs_update = thread_update_turnstile_promotion_locked(
3021 thread: thread_inheritor, turnstile);
3022
3023 /*
3024 * Check if thread needs further priority propagation,
3025 * since the first hop priority update was done in
3026 * turnstile_update_inheritor, do not bailout if it is
3027 * the first update as needs_update flag would evaluate to
3028 * false for that case.
3029 */
3030 if (!needs_update && !first_update) {
3031 /* Update turnstile stats before returning */
3032 turnstile_stats_update(hop: total_hop + 1,
3033 flags: (thread_get_update_flags_for_turnstile_propagation_stoppage(thread: thread_inheritor)) |
3034 TSU_TURNSTILE_ARG | tsu_flags,
3035 inheritor: turnstile);
3036 thread_unlock(thread_inheritor);
3037 waitq_unlock(wq: &turnstile->ts_waitq);
3038 return;
3039 }
3040
3041 /* Unlock the turnstile and update the thread */
3042 waitq_unlock(wq: &turnstile->ts_waitq);
3043 *out_thread = thread_inheritor;
3044 return;
3045}
3046
3047/*
3048 * Name: turnstile_update_inheritor_turnstile_priority_chain
3049 *
3050 * Description: Helper function to update turnstile's inheritor(turnstile)
3051 * priority.
3052 *
3053 * Arg1: in_out_turnstile: address to turnstile
3054 * Arg2: thread_hop: number of thread hop in propagation chain
3055 * Arg3: tsu_flags: turnstile update flags
3056 *
3057 * Returns: Implicit returns locked turnstile in in_out_turnstile if it needs
3058 * further propagation.
3059 *
3060 * Condition: *in_out_turnstile is locked on entry, *in_out_turnstile on exit,
3061 * but the value of *in_out_turnstile might change and turnstile lock
3062 * will be dropped for old value and will be acquired for the new value.
3063 */
3064static void
3065turnstile_update_inheritor_turnstile_priority_chain(
3066 struct turnstile **in_out_turnstile,
3067 int total_hop,
3068 turnstile_stats_update_flags_t tsu_flags)
3069{
3070 boolean_t needs_update = FALSE;
3071 struct turnstile *turnstile = *in_out_turnstile;
3072 struct turnstile *inheritor_turnstile = turnstile->ts_inheritor;
3073 boolean_t first_update = !total_hop;
3074
3075 assert(turnstile->ts_inheritor_flags & TURNSTILE_INHERITOR_TURNSTILE);
3076 *in_out_turnstile = TURNSTILE_NULL;
3077
3078 /* Check if the inheritor turnstile needs to be updated before grabbing the lock */
3079 needs_update = turnstile_need_turnstile_promotion_update(dst_turnstile: inheritor_turnstile, src_turnstile: turnstile);
3080 if (!needs_update && !first_update) {
3081 turnstile_stats_update(hop: total_hop + 1, flags: TSU_NO_PRI_CHANGE_NEEDED |
3082 TSU_TURNSTILE_ARG | tsu_flags,
3083 inheritor: turnstile);
3084 waitq_unlock(wq: &turnstile->ts_waitq);
3085 return;
3086 }
3087
3088 waitq_lock(wq: &inheritor_turnstile->ts_waitq);
3089
3090 needs_update = turnstile_update_turnstile_promotion_locked(
3091 dst_turnstile: inheritor_turnstile, src_turnstile: turnstile);
3092
3093 /*
3094 * Check if turnstile needs further priority propagation,
3095 * since the first hop priority update was done in
3096 * turnstile_update_inheritor, do not bailout if it is
3097 * the first update as needs_update flag would evaluate to
3098 * false for that case.
3099 */
3100 if (!needs_update && !first_update) {
3101 /* Update turnstile stats before returning */
3102 turnstile_stats_update(hop: total_hop + 1,
3103 flags: (inheritor_turnstile->ts_inheritor ? TSU_NO_PRI_CHANGE_NEEDED : TSU_NO_INHERITOR) |
3104 TSU_TURNSTILE_ARG | tsu_flags,
3105 inheritor: turnstile);
3106 waitq_unlock(wq: &inheritor_turnstile->ts_waitq);
3107 waitq_unlock(wq: &turnstile->ts_waitq);
3108 return;
3109 }
3110
3111 /* Unlock the outer turnstile and update the inner turnstile */
3112 waitq_unlock(wq: &turnstile->ts_waitq);
3113 *in_out_turnstile = inheritor_turnstile;
3114 return;
3115}
3116
3117/*
3118 * Name: thread_update_waiting_turnstile_priority_chain
3119 *
3120 * Description: Helper function to update thread's waiting
3121 * turnstile priority.
3122 *
3123 * Arg1: in_thread: pointer to thread
3124 * Arg2: out_turnstile: pointer to turnstile to return to caller
3125 * Arg3: thread_hop: Number of thread hops visited
3126 * Arg4: total_hop: total hops visited
3127 * Arg5: tsu_flags: turnstile update flags
3128 *
3129 * Returns: *out_turnstile returns the inheritor if it needs further propagation.
3130 *
3131 * Condition: *in_thread locked on entry, unlocked on exit and set to NULL.
3132 */
3133static void
3134thread_update_waiting_turnstile_priority_chain(
3135 thread_t *in_thread,
3136 struct turnstile **out_turnstile,
3137 int thread_hop,
3138 int total_hop,
3139 turnstile_stats_update_flags_t tsu_flags)
3140{
3141 boolean_t needs_update = FALSE;
3142 thread_t thread = *in_thread;
3143 struct turnstile *waiting_turnstile = TURNSTILE_NULL;
3144 uint32_t turnstile_gencount;
3145 boolean_t first_update = !total_hop;
3146
3147 *in_thread = THREAD_NULL;
3148
3149 /* Check if thread waiting on a turnstile */
3150 waiting_turnstile = thread_get_waiting_turnstile(thread);
3151
3152 if (waiting_turnstile == TURNSTILE_NULL || thread_hop > turnstile_max_hop) {
3153 KERNEL_DEBUG_CONSTANT_IST(KDEBUG_TRACE,
3154 (TURNSTILE_CODE(TURNSTILE_HEAP_OPERATIONS,
3155 (waiting_turnstile ? TURNSTILE_UPDATE_STOPPED_BY_LIMIT : THREAD_NOT_WAITING_ON_TURNSTILE)
3156 )) | DBG_FUNC_NONE,
3157 thread_tid(thread),
3158 turnstile_max_hop,
3159 thread_hop,
3160 VM_KERNEL_UNSLIDE_OR_PERM(waiting_turnstile), 0);
3161 turnstile_stats_update(hop: total_hop + 1, flags: TSU_NO_TURNSTILE |
3162 TSU_THREAD_ARG | tsu_flags, inheritor: thread);
3163 thread_unlock(thread);
3164 return;
3165 }
3166
3167 /* Check if the thread needs to update the waiting turnstile */
3168 needs_update = turnstile_need_thread_promotion_update(dst_turnstile: waiting_turnstile, thread);
3169 if (!needs_update && !first_update) {
3170 turnstile_stats_update(hop: total_hop + 1, flags: TSU_NO_PRI_CHANGE_NEEDED |
3171 TSU_THREAD_ARG | tsu_flags, inheritor: thread);
3172 thread_unlock(thread);
3173 return;
3174 }
3175
3176 /* take a reference on thread, turnstile and snapshot of gencount */
3177 turnstile_gencount = turnstile_get_gencount(turnstile: waiting_turnstile);
3178 turnstile_reference(turnstile: waiting_turnstile);
3179 thread_reference(thread);
3180
3181 /* drop the thread lock and acquire the turnstile lock */
3182 thread_unlock(thread);
3183 waitq_lock(wq: &waiting_turnstile->ts_waitq);
3184 thread_lock(thread);
3185
3186 /* Check if the gencount matches and thread is still waiting on same turnstile */
3187 if (turnstile_gencount != turnstile_get_gencount(turnstile: waiting_turnstile) ||
3188 waiting_turnstile != thread_get_waiting_turnstile(thread)) {
3189 turnstile_stats_update(hop: total_hop + 1, flags: TSU_NO_PRI_CHANGE_NEEDED |
3190 TSU_THREAD_ARG | tsu_flags, inheritor: thread);
3191 /* No updates required, bail out */
3192 thread_unlock(thread);
3193 waitq_unlock(wq: &waiting_turnstile->ts_waitq);
3194 thread_deallocate_safe(thread);
3195 turnstile_deallocate_safe(turnstile: waiting_turnstile);
3196 return;
3197 }
3198
3199 /*
3200 * The thread is waiting on the waiting_turnstile and we have thread lock,
3201 * we can drop the thread and turnstile reference since its on waitq and
3202 * it could not be removed from the waitq without the thread lock.
3203 */
3204 thread_deallocate_safe(thread);
3205 turnstile_deallocate_safe(turnstile: waiting_turnstile);
3206
3207 /* adjust thread's position on turnstile waitq */
3208 needs_update = turnstile_update_thread_promotion_locked(dst_turnstile: waiting_turnstile, thread);
3209
3210 /*
3211 * Check if thread needs further priority propagation,
3212 * since the first hop priority update was done in
3213 * turnstile_update_inheritor, do not bailout if it is
3214 * the first update as needs_update flag would evaluate to
3215 * false for that case.
3216 */
3217 if (!needs_update && !first_update) {
3218 turnstile_stats_update(hop: total_hop + 1,
3219 flags: (waiting_turnstile->ts_inheritor ? TSU_NO_PRI_CHANGE_NEEDED : TSU_NO_INHERITOR) |
3220 TSU_THREAD_ARG | tsu_flags, inheritor: thread);
3221 thread_unlock(thread);
3222 waitq_unlock(wq: &waiting_turnstile->ts_waitq);
3223 return;
3224 }
3225
3226 /* drop the thread lock and update the turnstile */
3227 thread_unlock(thread);
3228 *out_turnstile = waiting_turnstile;
3229}
3230
3231/*
3232 * Name: turnstile_stats_update
3233 *
3234 * Description: Function to update turnstile stats for dev kernel.
3235 *
3236 * Arg1: hops : number of thread hops in priority propagation
3237 * Arg2: flags : turnstile stats update flags
3238 * Arg3: inheritor: inheritor
3239 *
3240 * Returns: Nothing
3241 */
3242void
3243turnstile_stats_update(
3244 int hop __assert_only,
3245 turnstile_stats_update_flags_t flags __assert_only,
3246 turnstile_inheritor_t inheritor __assert_only)
3247{
3248#if DEVELOPMENT || DEBUG
3249 if (flags & TSU_TURNSTILE_BLOCK_COUNT) {
3250 os_atomic_inc(&thread_block_on_turnstile_count, relaxed);
3251 }
3252
3253 if (flags & TSU_REGULAR_WAITQ_BLOCK_COUNT) {
3254 os_atomic_inc(&thread_block_on_regular_waitq_count, relaxed);
3255 }
3256
3257 if (hop > TURNSTILE_MAX_HOP_DEFAULT || hop == 0) {
3258 return;
3259 }
3260
3261 assert(hop >= 0);
3262
3263 /*
3264 * Check if turnstile stats needs to be updated.
3265 * Bail out if the turnstile or thread does not
3266 * have any user promotion.
3267 * Bail out if it is the first hop of WQ turnstile
3268 * since WQ's use of a turnstile for the admission check
3269 * introduces a lot of noise due to state changes.
3270 */
3271 if (flags & TSU_TURNSTILE_ARG) {
3272 struct turnstile *ts = (struct turnstile *)inheritor;
3273 if (ts->ts_priority == 0) {
3274 return;
3275 }
3276
3277 if (hop == 1 && turnstile_get_type(ts) == TURNSTILE_WORKQS) {
3278 return;
3279 }
3280 } else if (flags & TSU_THREAD_ARG) {
3281 thread_t thread = (thread_t)inheritor;
3282 if (thread->user_promotion_basepri == 0) {
3283 return;
3284 }
3285 } else {
3286 assert(inheritor == NULL);
3287 }
3288
3289 struct turnstile_stats *turnstile_stats;
3290 if (flags & TSU_BOOST_ARG) {
3291 turnstile_stats = turnstile_boost_stats;
3292 } else {
3293 turnstile_stats = turnstile_unboost_stats;
3294 }
3295
3296 if (flags & TSU_PRI_PROPAGATION) {
3297 os_atomic_inc(&turnstile_stats[hop - 1].ts_priority_propagation, relaxed);
3298 }
3299
3300 if (flags & TSU_NO_INHERITOR) {
3301 os_atomic_inc(&turnstile_stats[hop - 1].ts_no_inheritor, relaxed);
3302 }
3303
3304 if (flags & TSU_NO_TURNSTILE) {
3305 os_atomic_inc(&turnstile_stats[hop - 1].ts_no_turnstile, relaxed);
3306 }
3307
3308 if (flags & TSU_NO_PRI_CHANGE_NEEDED) {
3309 os_atomic_inc(&turnstile_stats[hop - 1].ts_no_priority_change_required, relaxed);
3310 }
3311
3312 if (flags & TSU_THREAD_RUNNABLE) {
3313 os_atomic_inc(&turnstile_stats[hop - 1].ts_thread_runnable, relaxed);
3314 }
3315
3316 if (flags & TSU_ABOVE_UI_PRI_CHANGE) {
3317 os_atomic_inc(&turnstile_stats[hop - 1].ts_above_ui_pri_change, relaxed);
3318 }
3319#endif
3320}
3321
3322#define STACKSHOT_TURNSTILE_FLAGS_MODE(flags) ((flags) & ~STACKSHOT_TURNSTILE_STATUS_PORTFLAGS)
3323#define STACKSHOT_TURNSTILE_FLAGS_PORT(flags) ((flags) & STACKSHOT_TURNSTILE_STATUS_PORTFLAGS)
3324#define STACKSHOT_TURNSTILE_FLAGS_WITHPORT(flags, port) \
3325 (STACKSHOT_TURNSTILE_FLAGS_MODE(flags) | STACKSHOT_TURNSTILE_FLAGS_PORT(port))
3326
3327static uint64_t
3328kdp_turnstile_traverse_inheritor_chain(struct turnstile *ts, uint64_t *flags, uint8_t *hops, struct ipc_service_port_label **isplp)
3329{
3330 uint8_t unknown_hops;
3331
3332 if (waitq_held(wq: &ts->ts_waitq)) {
3333 *flags |= STACKSHOT_TURNSTILE_STATUS_LOCKED_WAITQ;
3334 return 0;
3335 }
3336
3337 *hops = *hops + 1;
3338 unknown_hops = *hops;
3339
3340 /*
3341 * If we find a port along the way, include it. Do this first so the
3342 * furthest one wins.
3343 */
3344 if (turnstile_is_send_turnstile(turnstile: ts)) {
3345 ipc_port_t port = (ipc_port_t)ts->ts_proprietor;
3346
3347 if (port && ip_active(port) && port->ip_service_port && port->ip_splabel != NULL) {
3348 *flags = STACKSHOT_TURNSTILE_FLAGS_WITHPORT(*flags, STACKSHOT_TURNSTILE_STATUS_SENDPORT);
3349 *isplp = (struct ipc_service_port_label *)port->ip_splabel;
3350 }
3351 }
3352 if (turnstile_is_receive_turnstile(turnstile: ts)) {
3353 ipc_port_t port = (ipc_port_t)ts->ts_proprietor;
3354 if (port && ip_active(port) && port->ip_service_port && port->ip_splabel != NULL) {
3355 *flags = STACKSHOT_TURNSTILE_FLAGS_WITHPORT(*flags, STACKSHOT_TURNSTILE_STATUS_RECEIVEPORT);
3356 *isplp = (struct ipc_service_port_label *)port->ip_splabel;
3357 }
3358 }
3359 /*
3360 * If a turnstile is inheriting our priority, recurse. If we get back *exactly* UNKNOWN,
3361 * continue on, since we may be able to give a more specific answer. To
3362 * give an accurate hops count, we reset *hops, saving the recursive value in
3363 * unknown_hops to use if we can't give a better answer.
3364 */
3365 if (ts->ts_inheritor_flags & TURNSTILE_INHERITOR_TURNSTILE) {
3366 uint8_t pre_hops = *hops;
3367 uint64_t ret = kdp_turnstile_traverse_inheritor_chain(ts: ts->ts_inheritor, flags, hops, isplp);
3368 /*
3369 * Note that while flags is usually |=ed, we're checking with != here to
3370 * make sure we only replace *exactly* UNKNOWN, ignoring the portflags.
3371 */
3372 if (ret != 0 || STACKSHOT_TURNSTILE_FLAGS_MODE(*flags) != STACKSHOT_TURNSTILE_STATUS_UNKNOWN) {
3373 return ret;
3374 }
3375 /* restore original hops value, saving the new one if we fall through to unknown */
3376 unknown_hops = *hops;
3377 *hops = pre_hops;
3378 *flags = STACKSHOT_TURNSTILE_FLAGS_PORT(*flags);
3379 }
3380
3381 if (ts->ts_inheritor_flags & TURNSTILE_INHERITOR_THREAD) {
3382 *flags |= STACKSHOT_TURNSTILE_STATUS_THREAD;
3383 return (uint64_t) thread_tid(thread: ts->ts_inheritor);
3384 }
3385
3386 if (ts->ts_inheritor_flags & TURNSTILE_INHERITOR_WORKQ) {
3387 *flags |= STACKSHOT_TURNSTILE_STATUS_WORKQUEUE;
3388 return VM_KERNEL_UNSLIDE_OR_PERM(ts->ts_inheritor);
3389 }
3390
3391 /*
3392 * If we found a send turnstile, try to get the task that the turnstile's
3393 * port is in the ipc space of
3394 */
3395 if (turnstile_is_send_turnstile(turnstile: ts)) {
3396 ipc_port_t port = (ipc_port_t)ts->ts_proprietor;
3397
3398 if (port && ip_active(port)) {
3399 if (ip_mq_lock_held_kdp(port)) {
3400 *flags |= STACKSHOT_TURNSTILE_STATUS_HELD_IPLOCK;
3401 return 0;
3402 }
3403 if (port->ip_receiver_name != 0 && port->ip_receiver) {
3404 ipc_space_t space = (ipc_space_t) port->ip_receiver;
3405 task_t dest_task = space->is_task;
3406
3407 if (dest_task != TASK_NULL) {
3408 *flags |= STACKSHOT_TURNSTILE_STATUS_BLOCKED_ON_TASK;
3409 return pid_from_task(task: dest_task);
3410 }
3411 }
3412 }
3413 }
3414
3415 if (turnstile_is_receive_turnstile(turnstile: ts)) {
3416 ipc_port_t port = (ipc_port_t)ts->ts_proprietor;
3417 if (port && ip_active(port)) {
3418 if (ip_mq_lock_held_kdp(port)) {
3419 *flags |= STACKSHOT_TURNSTILE_STATUS_HELD_IPLOCK;
3420 return 0;
3421 }
3422 if (port->ip_specialreply) {
3423 /* try getting the pid stored in the port */
3424 uint64_t pid_candidate = ipc_special_reply_get_pid_locked(port);
3425
3426 if (pid_candidate) {
3427 *flags |= STACKSHOT_TURNSTILE_STATUS_BLOCKED_ON_TASK;
3428 return pid_candidate;
3429 }
3430 }
3431 }
3432 }
3433
3434 *hops = unknown_hops;
3435 *flags |= STACKSHOT_TURNSTILE_STATUS_UNKNOWN;
3436 return 0;
3437}
3438
3439void
3440kdp_turnstile_fill_tsinfo(struct turnstile *ts, thread_turnstileinfo_v2_t *tsinfo, struct ipc_service_port_label **isplp)
3441{
3442 uint64_t final_inheritor;
3443 uint64_t flags = 0;
3444 uint8_t hops = 0;
3445
3446 tsinfo->turnstile_context = 0;
3447 tsinfo->number_of_hops = 0;
3448 tsinfo->turnstile_priority = 0;
3449
3450 assert(ts != TURNSTILE_NULL);
3451
3452 if (waitq_held(wq: &ts->ts_waitq)) {
3453 tsinfo->turnstile_flags |= STACKSHOT_TURNSTILE_STATUS_LOCKED_WAITQ;
3454 return;
3455 }
3456
3457 final_inheritor = kdp_turnstile_traverse_inheritor_chain(ts, flags: &flags, hops: &hops, isplp);
3458
3459 /* store some metadata about the turnstile itself */
3460 tsinfo->turnstile_flags = flags;
3461 tsinfo->number_of_hops = hops;
3462 tsinfo->turnstile_priority = ts->ts_priority;
3463 tsinfo->turnstile_context = final_inheritor;
3464}
3465
3466#if DEVELOPMENT || DEBUG
3467
3468int sysctl_io_opaque(void *req, void *pValue, size_t valueSize, int *changed);
3469
3470/*
3471 * Name: turnstile_get_boost_stats_sysctl
3472 *
3473 * Description: Function to get turnstile stats.
3474 *
3475 * Args: req : opaque struct to pass to sysctl_io_opaque
3476 *
3477 * Returns: errorno
3478 */
3479int
3480turnstile_get_boost_stats_sysctl(
3481 void *req)
3482{
3483 return sysctl_io_opaque(req, turnstile_boost_stats, sizeof(struct turnstile_stats) * TURNSTILE_MAX_HOP_DEFAULT, NULL);
3484}
3485
3486/*
3487 * Name: get_turnstile_stats_sysctl
3488 *
3489 * Description: Function to get turnstile stats.
3490 *
3491 * Args: req : opaque struct to pass to sysctl_io_opaque
3492 *
3493 * Returns: errorno
3494 */
3495int
3496turnstile_get_unboost_stats_sysctl(
3497 void *req)
3498{
3499 return sysctl_io_opaque(req, turnstile_unboost_stats, sizeof(struct turnstile_stats) * TURNSTILE_MAX_HOP_DEFAULT, NULL);
3500}
3501
3502/* Testing interface for Development kernels */
3503#define tstile_test_prim_lock_interlock(test_prim) \
3504 lck_spin_lock(&test_prim->ttprim_interlock)
3505#define tstile_test_prim_unlock_interlock(test_prim) \
3506 lck_spin_unlock(&test_prim->ttprim_interlock)
3507
3508static void
3509tstile_test_prim_init(struct tstile_test_prim *test_prim)
3510{
3511 test_prim->ttprim_turnstile = TURNSTILE_NULL;
3512 test_prim->ttprim_owner = NULL;
3513 lck_spin_init(&test_prim->ttprim_interlock, &turnstiles_dev_lock_grp, LCK_ATTR_NULL);
3514 test_prim->tt_prim_waiters = 0;
3515}
3516
3517int
3518tstile_test_prim_lock(int val)
3519{
3520 struct tstile_test_prim *test_prim;
3521 boolean_t use_hashtable;
3522 turnstile_type_t type;
3523 wait_interrupt_t wait_type;
3524
3525 switch (val) {
3526 case SYSCTL_TURNSTILE_TEST_USER_DEFAULT:
3527 test_prim = &test_prim_ts_inline;
3528 use_hashtable = FALSE;
3529 wait_type = THREAD_ABORTSAFE;
3530 type = TURNSTILE_ULOCK;
3531 break;
3532 case SYSCTL_TURNSTILE_TEST_USER_HASHTABLE:
3533 test_prim = &test_prim_global_htable;
3534 use_hashtable = TRUE;
3535 wait_type = THREAD_ABORTSAFE;
3536 type = TURNSTILE_ULOCK;
3537 break;
3538 case SYSCTL_TURNSTILE_TEST_KERNEL_DEFAULT:
3539 test_prim = &test_prim_global_ts_kernel;
3540 use_hashtable = FALSE;
3541 wait_type = THREAD_UNINT | THREAD_WAIT_NOREPORT_USER;
3542 type = TURNSTILE_KERNEL_MUTEX;
3543 break;
3544 case SYSCTL_TURNSTILE_TEST_KERNEL_HASHTABLE:
3545 test_prim = &test_prim_global_ts_kernel_hash;
3546 use_hashtable = TRUE;
3547 wait_type = THREAD_UNINT | THREAD_WAIT_NOREPORT_USER;
3548 type = TURNSTILE_KERNEL_MUTEX;
3549 break;
3550
3551 default:
3552 return -1;
3553 }
3554
3555lock_start:
3556
3557 /* take the interlock of the primitive */
3558 tstile_test_prim_lock_interlock(test_prim);
3559
3560 /* Check if the lock is available */
3561 if (test_prim->ttprim_owner == NULL && test_prim->tt_prim_waiters == 0) {
3562 thread_reference(current_thread());
3563 test_prim->ttprim_owner = current_thread();
3564 tstile_test_prim_unlock_interlock(test_prim);
3565 return 0;
3566 }
3567
3568 struct turnstile *prim_turnstile = TURNSTILE_NULL;
3569
3570 /* primitive locked, get a turnstile */
3571 if (use_hashtable) {
3572 prim_turnstile = turnstile_prepare_hash((uintptr_t)test_prim, type);
3573 } else {
3574 prim_turnstile = turnstile_prepare((uintptr_t)test_prim,
3575 &test_prim->ttprim_turnstile, TURNSTILE_NULL, type);
3576 }
3577
3578 assert(prim_turnstile != TURNSTILE_NULL);
3579
3580 /* This is contented acquire case */
3581 if (test_prim->ttprim_owner == NULL) {
3582 thread_reference(current_thread());
3583 test_prim->ttprim_owner = current_thread();
3584
3585 /* Update the turnstile owner */
3586 turnstile_update_inheritor(prim_turnstile,
3587 current_thread(),
3588 (TURNSTILE_IMMEDIATE_UPDATE | TURNSTILE_INHERITOR_THREAD));
3589
3590 turnstile_update_inheritor_complete(prim_turnstile, TURNSTILE_INTERLOCK_HELD);
3591
3592 if (use_hashtable) {
3593 turnstile_complete_hash((uintptr_t)test_prim, type);
3594 } else {
3595 turnstile_complete((uintptr_t)test_prim,
3596 &test_prim->ttprim_turnstile, NULL, type);
3597 }
3598
3599 tstile_test_prim_unlock_interlock(test_prim);
3600
3601 turnstile_cleanup();
3602 return 0;
3603 }
3604
3605 test_prim->tt_prim_waiters++;
3606 turnstile_update_inheritor(prim_turnstile,
3607 test_prim->ttprim_owner,
3608 (TURNSTILE_DELAYED_UPDATE | TURNSTILE_INHERITOR_THREAD));
3609
3610 waitq_assert_wait64(&prim_turnstile->ts_waitq,
3611 CAST_EVENT64_T(test_prim), wait_type,
3612 TIMEOUT_WAIT_FOREVER);
3613
3614 /* drop the interlock */
3615 tstile_test_prim_unlock_interlock(test_prim);
3616
3617 turnstile_update_inheritor_complete(prim_turnstile, TURNSTILE_INTERLOCK_NOT_HELD);
3618
3619 wait_result_t result;
3620 result = thread_block(THREAD_CONTINUE_NULL);
3621
3622 /* re-acquire the interlock to get turnstile back */
3623 tstile_test_prim_lock_interlock(test_prim);
3624 test_prim->tt_prim_waiters--;
3625
3626 if (use_hashtable) {
3627 turnstile_complete_hash((uintptr_t)test_prim, type);
3628 } else {
3629 turnstile_complete((uintptr_t)test_prim,
3630 &test_prim->ttprim_turnstile, NULL, type);
3631 }
3632
3633 tstile_test_prim_unlock_interlock(test_prim);
3634
3635 turnstile_cleanup();
3636
3637 /* Return if thread interrupted */
3638 if (result == THREAD_INTERRUPTED) {
3639 return 1;
3640 }
3641
3642 goto lock_start;
3643}
3644
3645int
3646tstile_test_prim_unlock(int val)
3647{
3648 struct tstile_test_prim *test_prim;
3649 boolean_t use_hashtable;
3650 turnstile_type_t type;
3651
3652 switch (val) {
3653 case SYSCTL_TURNSTILE_TEST_USER_DEFAULT:
3654 test_prim = &test_prim_ts_inline;
3655 use_hashtable = FALSE;
3656 type = TURNSTILE_ULOCK;
3657 break;
3658 case SYSCTL_TURNSTILE_TEST_USER_HASHTABLE:
3659 test_prim = &test_prim_global_htable;
3660 use_hashtable = TRUE;
3661 type = TURNSTILE_ULOCK;
3662 break;
3663 case SYSCTL_TURNSTILE_TEST_KERNEL_DEFAULT:
3664 test_prim = &test_prim_global_ts_kernel;
3665 use_hashtable = FALSE;
3666 type = TURNSTILE_KERNEL_MUTEX;
3667 break;
3668 case SYSCTL_TURNSTILE_TEST_KERNEL_HASHTABLE:
3669 test_prim = &test_prim_global_ts_kernel_hash;
3670 use_hashtable = TRUE;
3671 type = TURNSTILE_KERNEL_MUTEX;
3672 break;
3673 default:
3674 return -1;
3675 }
3676
3677 /* take the interlock of the primitive */
3678 tstile_test_prim_lock_interlock(test_prim);
3679
3680 if (test_prim->ttprim_owner == NULL) {
3681 tstile_test_prim_unlock_interlock(test_prim);
3682 return 1;
3683 }
3684
3685 /* Check if the lock is contended */
3686 if (test_prim->ttprim_owner != NULL && test_prim->tt_prim_waiters == 0) {
3687 /* lock is not contended */
3688 thread_t old_owner = test_prim->ttprim_owner;
3689 test_prim->ttprim_owner = NULL;
3690 tstile_test_prim_unlock_interlock(test_prim);
3691
3692 thread_deallocate(old_owner);
3693 return 0;
3694 }
3695
3696 struct turnstile *prim_turnstile = TURNSTILE_NULL;
3697
3698 thread_t old_owner = test_prim->ttprim_owner;
3699 test_prim->ttprim_owner = NULL;
3700
3701 /* primitive locked, get a turnstile */
3702 if (use_hashtable) {
3703 prim_turnstile = turnstile_prepare_hash((uintptr_t)test_prim, type);
3704 } else {
3705 prim_turnstile = turnstile_prepare((uintptr_t)test_prim,
3706 &test_prim->ttprim_turnstile, TURNSTILE_NULL, type);
3707 }
3708
3709 assert(prim_turnstile != TURNSTILE_NULL);
3710
3711 /* Update the turnstile owner */
3712 turnstile_update_inheritor(prim_turnstile,
3713 NULL,
3714 (TURNSTILE_IMMEDIATE_UPDATE | TURNSTILE_INHERITOR_THREAD));
3715
3716 waitq_wakeup64_one(&prim_turnstile->ts_waitq,
3717 CAST_EVENT64_T(test_prim),
3718 THREAD_AWAKENED, WAITQ_WAKEUP_DEFAULT);
3719
3720 turnstile_update_inheritor_complete(prim_turnstile, TURNSTILE_INTERLOCK_HELD);
3721
3722 if (use_hashtable) {
3723 turnstile_complete_hash((uintptr_t)test_prim, type);
3724 } else {
3725 turnstile_complete((uintptr_t)test_prim,
3726 &test_prim->ttprim_turnstile, NULL, type);
3727 }
3728
3729 tstile_test_prim_unlock_interlock(test_prim);
3730
3731 turnstile_cleanup();
3732
3733 if (old_owner) {
3734 /* Changing this to thread_deallocate_safe to exercise thread_deallocate_safe path */
3735 thread_deallocate_safe(old_owner);
3736 }
3737
3738 return 0;
3739}
3740
3741#endif
3742