1/*
2 * Copyright (c) 2017 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 <machine/machlimits.h>
44#include <machine/atomic.h>
45
46#include <pexpert/pexpert.h>
47#include <libkern/section_keywords.h>
48
49static zone_t turnstiles_zone;
50static int turnstile_max_hop;
51#define MAX_TURNSTILES (thread_max)
52#define TURNSTILES_CHUNK (THREAD_CHUNK)
53
54/* Global table for turnstile promote policy for all type of turnstiles */
55turnstile_promote_policy_t turnstile_promote_policy[TURNSTILE_TOTAL_TYPES] = {
56 [TURNSTILE_NONE] = TURNSTILE_PROMOTE_NONE,
57 [TURNSTILE_KERNEL_MUTEX] = TURNSTILE_KERNEL_PROMOTE,
58 [TURNSTILE_ULOCK] = TURNSTILE_USER_PROMOTE,
59 [TURNSTILE_PTHREAD_MUTEX] = TURNSTILE_USER_PROMOTE,
60 [TURNSTILE_SYNC_IPC] = TURNSTILE_USER_IPC_PROMOTE,
61 [TURNSTILE_WORKLOOPS] = TURNSTILE_USER_IPC_PROMOTE,
62 [TURNSTILE_WORKQS] = TURNSTILE_USER_IPC_PROMOTE,
63 [TURNSTILE_KNOTE] = TURNSTILE_USER_IPC_PROMOTE,
64};
65
66os_refgrp_decl(static, turnstile_refgrp, "turnstile", NULL);
67
68#if DEVELOPMENT || DEBUG
69static queue_head_t turnstiles_list;
70static lck_spin_t global_turnstile_lock;
71
72lck_grp_t turnstiles_dev_lock_grp;
73lck_attr_t turnstiles_dev_lock_attr;
74lck_grp_attr_t turnstiles_dev_lock_grp_attr;
75
76#define global_turnstiles_lock_init() \
77 lck_spin_init(&global_turnstile_lock, &turnstiles_dev_lock_grp, &turnstiles_dev_lock_attr)
78#define global_turnstiles_lock_destroy() \
79 lck_spin_destroy(&global_turnstile_lock, &turnstiles_dev_lock_grp)
80#define global_turnstiles_lock() \
81 lck_spin_lock(&global_turnstile_lock)
82#define global_turnstiles_lock_try() \
83 lck_spin_try_lock(&global_turnstile_lock)
84#define global_turnstiles_unlock() \
85 lck_spin_unlock(&global_turnstile_lock)
86
87/* Array to store stats for multi-hop boosting */
88static struct turnstile_stats turnstile_boost_stats[TURNSTILE_MAX_HOP_DEFAULT] = {};
89static struct turnstile_stats turnstile_unboost_stats[TURNSTILE_MAX_HOP_DEFAULT] = {};
90uint64_t thread_block_on_turnstile_count;
91uint64_t thread_block_on_regular_waitq_count;
92
93#endif
94
95#ifndef max
96#define max(a,b) (((a) > (b)) ? (a) : (b))
97#endif /* max */
98
99/* Static function declarations */
100static turnstile_type_t
101turnstile_get_type(struct turnstile *turnstile);
102static uint32_t
103turnstile_get_gencount(struct turnstile *turnstile);
104static void
105turnstile_set_type_and_increment_gencount(struct turnstile *turnstile, turnstile_type_t type);
106static void
107turnstile_init(struct turnstile *turnstile);
108static void
109turnstile_update_inheritor_workq_priority_chain(struct turnstile *in_turnstile, spl_t s);
110static void
111turnstile_update_inheritor_thread_priority_chain(struct turnstile **in_turnstile,
112 thread_t *out_thread, int total_hop, turnstile_stats_update_flags_t tsu_flags);
113static void
114turnstile_update_inheritor_turnstile_priority_chain(struct turnstile **in_out_turnstile,
115 int total_hop, turnstile_stats_update_flags_t tsu_flags);
116static void
117thread_update_waiting_turnstile_priority_chain(thread_t *in_thread,
118 struct turnstile **out_turnstile, int thread_hop, int total_hop,
119 turnstile_stats_update_flags_t tsu_flags);
120static boolean_t
121turnstile_update_turnstile_promotion_locked(struct turnstile *dst_turnstile,
122 struct turnstile *src_turnstile);
123static boolean_t
124turnstile_update_turnstile_promotion(struct turnstile *dst_turnstile,
125 struct turnstile *src_turnstile);
126static boolean_t
127turnstile_need_turnstile_promotion_update(struct turnstile *dst_turnstile,
128 struct turnstile *src_turnstile);
129static boolean_t
130turnstile_add_turnstile_promotion(struct turnstile *dst_turnstile,
131 struct turnstile *src_turnstile);
132static boolean_t
133turnstile_remove_turnstile_promotion(struct turnstile *dst_turnstile,
134 struct turnstile *src_turnstile);
135static boolean_t
136turnstile_update_thread_promotion_locked(struct turnstile *dst_turnstile,
137 thread_t thread);
138static boolean_t
139turnstile_need_thread_promotion_update(struct turnstile *dst_turnstile,
140 thread_t thread);
141static boolean_t
142thread_add_turnstile_promotion(
143 thread_t thread, struct turnstile *turnstile);
144static boolean_t
145thread_remove_turnstile_promotion(
146 thread_t thread, struct turnstile *turnstile);
147static boolean_t
148thread_needs_turnstile_promotion_update(thread_t thread,
149 struct turnstile *turnstile);
150static boolean_t
151thread_update_turnstile_promotion(
152 thread_t thread, struct turnstile *turnstile);
153static boolean_t
154thread_update_turnstile_promotion_locked(
155 thread_t thread, struct turnstile *turnstile);
156static boolean_t
157workq_add_turnstile_promotion(
158 struct workqueue *wq_inheritor, struct turnstile *turnstile);
159static turnstile_stats_update_flags_t
160thread_get_update_flags_for_turnstile_propagation_stoppage(thread_t thread);
161static turnstile_stats_update_flags_t
162turnstile_get_update_flags_for_above_UI_pri_change(struct turnstile *turnstile);
163
164#if DEVELOPMENT || DEBUG
165/* Test primitives and interfaces for testing turnstiles */
166struct tstile_test_prim {
167 struct turnstile *ttprim_turnstile;
168 thread_t ttprim_owner;
169 lck_spin_t ttprim_interlock;
170 uint32_t tt_prim_waiters;
171};
172
173struct tstile_test_prim *test_prim_ts_inline;
174struct tstile_test_prim *test_prim_global_htable;
175static void
176tstile_test_prim_init(struct tstile_test_prim **test_prim_ptr);
177#endif
178
179union turnstile_type_gencount {
180 uint32_t value;
181 struct {
182 uint32_t ts_type:(8 * sizeof(turnstile_type_t)),
183 ts_gencount: (8 *(sizeof(uint32_t) - sizeof(turnstile_type_t)));
184 };
185};
186
187static turnstile_type_t
188turnstile_get_type(struct turnstile *turnstile)
189{
190 union turnstile_type_gencount type_and_gencount;
191
192 type_and_gencount.value = atomic_load_explicit(&turnstile->ts_type_gencount, memory_order_relaxed);
193 return (turnstile_type_t) type_and_gencount.ts_type;
194}
195
196static uint32_t
197turnstile_get_gencount(struct turnstile *turnstile)
198{
199 union turnstile_type_gencount type_and_gencount;
200
201 type_and_gencount.value = atomic_load_explicit(&turnstile->ts_type_gencount, memory_order_relaxed);
202 return (uint32_t) type_and_gencount.ts_gencount;
203}
204
205static void
206turnstile_set_type_and_increment_gencount(struct turnstile *turnstile, turnstile_type_t type)
207{
208 union turnstile_type_gencount type_and_gencount;
209
210 /* No need to compare exchange since the store happens under interlock of the primitive */
211 type_and_gencount.value = atomic_load_explicit(&turnstile->ts_type_gencount, memory_order_relaxed);
212 type_and_gencount.ts_type = type;
213 type_and_gencount.ts_gencount++;
214 atomic_store_explicit(&turnstile->ts_type_gencount, type_and_gencount.value, memory_order_relaxed);
215}
216
217
218/* Turnstile hashtable Implementation */
219
220/*
221 * Maximum number of buckets in the turnstile hashtable. This number affects the
222 * performance of the hashtable since it determines the hash collision
223 * rate. To experiment with the number of buckets in this hashtable use the
224 * "ts_htable_buckets" boot-arg.
225 */
226#define TURNSTILE_HTABLE_BUCKETS_DEFAULT 32
227#define TURNSTILE_HTABLE_BUCKETS_MAX 1024
228
229SLIST_HEAD(turnstile_hashlist, turnstile);
230
231struct turnstile_htable_bucket {
232 lck_spin_t ts_ht_bucket_lock;
233 struct turnstile_hashlist ts_ht_bucket_list;
234};
235
236SECURITY_READ_ONLY_LATE(static uint32_t) ts_htable_buckets;
237/* Global hashtable for turnstiles */
238SECURITY_READ_ONLY_LATE(static struct turnstile_htable_bucket *)turnstile_htable;
239
240/* Bucket locks for turnstile hashtable */
241lck_grp_t turnstiles_htable_lock_grp;
242lck_attr_t turnstiles_htable_lock_attr;
243lck_grp_attr_t turnstiles_htable_lock_grp_attr;
244
245#define turnstile_bucket_lock_init(bucket) \
246 lck_spin_init(&bucket->ts_ht_bucket_lock, &turnstiles_htable_lock_grp, &turnstiles_htable_lock_attr)
247#define turnstile_bucket_lock(bucket) \
248 lck_spin_lock(&bucket->ts_ht_bucket_lock)
249#define turnstile_bucket_unlock(bucket) \
250 lck_spin_unlock(&bucket->ts_ht_bucket_lock)
251
252/*
253 * Name: turnstiles_hashtable_init
254 *
255 * Description: Initializes the global turnstile hash table.
256 *
257 * Args:
258 * None
259 *
260 * Returns:
261 * None
262 */
263static void
264turnstiles_hashtable_init(void)
265{
266 /* Initialize number of buckets in the hashtable */
267 if (PE_parse_boot_argn("ts_htable_buckets", &ts_htable_buckets, sizeof(ts_htable_buckets)) != TRUE)
268 ts_htable_buckets = TURNSTILE_HTABLE_BUCKETS_DEFAULT;
269
270 assert(ts_htable_buckets <= TURNSTILE_HTABLE_BUCKETS_MAX);
271 uint32_t ts_htable_size = ts_htable_buckets * sizeof(struct turnstile_htable_bucket);
272 turnstile_htable = (struct turnstile_htable_bucket *)kalloc(ts_htable_size);
273 if (turnstile_htable == NULL)
274 panic("Turnstiles hash table memory allocation failed!");
275
276 lck_grp_attr_setdefault(&turnstiles_htable_lock_grp_attr);
277 lck_grp_init(&turnstiles_htable_lock_grp, "turnstiles_htable_locks", &turnstiles_htable_lock_grp_attr);
278 lck_attr_setdefault(&turnstiles_htable_lock_attr);
279
280 /* Initialize all the buckets of the hashtable */
281 for (uint32_t i = 0; i < ts_htable_buckets; i++) {
282 struct turnstile_htable_bucket *ts_bucket = &(turnstile_htable[i]);
283 turnstile_bucket_lock_init(ts_bucket);
284 SLIST_INIT(&ts_bucket->ts_ht_bucket_list);
285 }
286}
287
288/*
289 * Name: turnstile_freelist_empty
290 *
291 * Description: Checks if the turnstile's freelist is empty
292 * Should be called with the primitive IL held.
293 *
294 * Args:
295 * Arg1: turnstile
296 *
297 * Returns:
298 * true if freelist is empty; false otherwise
299 */
300static inline boolean_t
301turnstile_freelist_empty(
302 struct turnstile *ts)
303{
304 return SLIST_EMPTY(&ts->ts_free_turnstiles);
305}
306
307
308/*
309 * Name: turnstile_freelist_insert
310 *
311 * Description: Inserts the turnstile into the freelist of another turnstile
312 * Should be called with the primitive IL held.
313 *
314 * Args:
315 * Arg1: primitive turnstile
316 * Arg2: turnstile to add to the freelist
317 *
318 * Returns:
319 * None
320 */
321static void
322turnstile_freelist_insert(
323 struct turnstile *dst_ts,
324 struct turnstile *free_ts)
325{
326 assert(turnstile_get_type(dst_ts) == turnstile_get_type(free_ts));
327 assert(dst_ts->ts_proprietor == free_ts->ts_proprietor);
328 turnstile_state_add(free_ts, TURNSTILE_STATE_FREELIST);
329 SLIST_INSERT_HEAD(&dst_ts->ts_free_turnstiles, free_ts, ts_free_elm);
330}
331
332/*
333 * Name: turnstile_freelist_remove
334 *
335 * Description: Removes a turnstile from the freelist of a turnstile
336 * Should be called with the primitive IL held.
337 *
338 * Args:
339 * Arg1: primitive turnstile
340 *
341 * Returns:
342 * turnstile removed from the freelist
343 */
344static struct turnstile *
345turnstile_freelist_remove(
346 struct turnstile *ts)
347{
348 struct turnstile *ret_turnstile = TURNSTILE_NULL;
349 assert(!SLIST_EMPTY(&ts->ts_free_turnstiles));
350 ret_turnstile = SLIST_FIRST(&ts->ts_free_turnstiles);
351 SLIST_REMOVE_HEAD(&ts->ts_free_turnstiles, ts_free_elm);
352 assert(ret_turnstile != TURNSTILE_NULL);
353 turnstile_state_remove(ret_turnstile, TURNSTILE_STATE_FREELIST);
354 /* Need to initialize the list again, since head and elm are in union */
355 SLIST_INIT(&ret_turnstile->ts_free_turnstiles);
356 return ret_turnstile;
357}
358
359/*
360 * Name: turnstile_hash
361 *
362 * Description: Calculates the hash bucket index for a given proprietor
363 *
364 * Args:
365 * Arg1: proprietor (key) for hashing
366 *
367 * Returns:
368 * hash table bucket index for provided proprietor
369 */
370static inline uint32_t
371turnstile_hash(uintptr_t proprietor)
372{
373 char *key = (char *)&proprietor;
374 uint32_t hash = jenkins_hash(key, sizeof(key));
375 hash &= (ts_htable_buckets - 1);
376 return hash;
377}
378
379/*
380 * Name: turnstile_htable_lookup_add
381 *
382 * Description: Lookup the proprietor in the global turnstile hash table.
383 * If an entry is present, add the new turnstile to the entry's freelist.
384 * Otherwise add the passed in turnstile for that proprietor.
385 * The routine assumes that the turnstile->proprietor does not change
386 * while the turnstile is in the global hash table.
387 *
388 * Args:
389 * Arg1: proprietor
390 * Arg2: new turnstile for primitive
391 *
392 * Returns:
393 * Previous turnstile for proprietor in the hash table
394 */
395static struct turnstile *
396turnstile_htable_lookup_add(
397 uintptr_t proprietor,
398 struct turnstile *new_turnstile)
399{
400 uint32_t index = turnstile_hash(proprietor);
401 assert(index < ts_htable_buckets);
402 struct turnstile_htable_bucket *ts_bucket = &(turnstile_htable[index]);
403 spl_t s;
404
405 s = splsched();
406 turnstile_bucket_lock(ts_bucket);
407 struct turnstile *ts;
408
409 SLIST_FOREACH(ts, &ts_bucket->ts_ht_bucket_list, ts_htable_link) {
410 if (ts->ts_proprietor == proprietor) {
411 /*
412 * Found an entry in the hashtable for this proprietor; add thread turnstile to freelist
413 * and return this turnstile
414 */
415 turnstile_bucket_unlock(ts_bucket);
416 splx(s);
417 turnstile_freelist_insert(ts, new_turnstile);
418 return ts;
419 }
420 }
421
422 /* No entry for this proprietor; add the new turnstile in the hash table */
423 SLIST_INSERT_HEAD(&ts_bucket->ts_ht_bucket_list, new_turnstile, ts_htable_link);
424 turnstile_state_add(new_turnstile, TURNSTILE_STATE_HASHTABLE);
425 turnstile_bucket_unlock(ts_bucket);
426 splx(s);
427 /* Since there was no previous entry for this proprietor, return TURNSTILE_NULL */
428 return TURNSTILE_NULL;
429}
430
431/*
432 * Name: turnstable_htable_lookup_remove
433 *
434 * Description: Lookup the proprietor in the global turnstile hash table.
435 * For the turnstile in the hash table, if the freelist has turnstiles on it
436 * return one of them from the freelist. Otherwise remove the turnstile from
437 * the hashtable and return that.
438 * The routine assumes that the turnstile->proprietor does not change
439 * while the turnstile is in the global hash table.
440 *
441 * Args:
442 * Arg1: proprietor
443 * Arg2: free turnstile to be returned
444 *
445 * Returns:
446 * turnstile for this proprietor in the hashtable after the removal
447 */
448static struct turnstile *
449turnstable_htable_lookup_remove(
450 uintptr_t proprietor,
451 struct turnstile **free_turnstile)
452{
453 uint32_t index = turnstile_hash(proprietor);
454 assert(index < ts_htable_buckets);
455 struct turnstile_htable_bucket *ts_bucket = &(turnstile_htable[index]);
456 struct turnstile *ret_turnstile = TURNSTILE_NULL;
457 spl_t s;
458
459 s = splsched();
460 turnstile_bucket_lock(ts_bucket);
461 struct turnstile *ts, **prev_tslink;
462 /* Find the turnstile for the given proprietor in the hashtable */
463 SLIST_FOREACH_PREVPTR(ts, prev_tslink, &ts_bucket->ts_ht_bucket_list, ts_htable_link) {
464 if (ts->ts_proprietor == proprietor) {
465 ret_turnstile = ts;
466 break;
467 }
468 }
469 assert(ret_turnstile != TURNSTILE_NULL);
470
471 /* Check if the turnstile has any turnstiles on its freelist */
472 if (turnstile_freelist_empty(ret_turnstile)) {
473 /* No turnstiles on the freelist; remove the turnstile from the hashtable and mark it freed */
474 *prev_tslink = SLIST_NEXT(ret_turnstile, ts_htable_link);
475 turnstile_state_remove(ret_turnstile, TURNSTILE_STATE_HASHTABLE);
476 turnstile_bucket_unlock(ts_bucket);
477 splx(s);
478 *free_turnstile = ret_turnstile;
479 return TURNSTILE_NULL;
480 } else {
481 /*
482 * Turnstile has free turnstiles on its list; leave the hashtable unchanged
483 * and return the first turnstile in the freelist as the free turnstile
484 */
485 turnstile_bucket_unlock(ts_bucket);
486 splx(s);
487 *free_turnstile = turnstile_freelist_remove(ret_turnstile);
488 return ret_turnstile;
489 }
490}
491
492/*
493 * Name: turnstile_htable_lookup
494 *
495 * Description: Lookup the proprietor in the global turnstile hash table.
496 * The routine assumes that the turnstile->proprietor does not change
497 * while the turnstile is in the global hash table.
498 *
499 * Args:
500 * Arg1: proprietor
501 *
502 * Returns:
503 * Turnstile for proprietor in the hash table
504 */
505static struct turnstile *
506turnstile_htable_lookup(
507 uintptr_t proprietor)
508{
509 uint32_t index = turnstile_hash(proprietor);
510 assert(index < ts_htable_buckets);
511 struct turnstile_htable_bucket *ts_bucket = &(turnstile_htable[index]);
512 spl_t s;
513
514 s = splsched();
515 turnstile_bucket_lock(ts_bucket);
516 struct turnstile *ts = TURNSTILE_NULL;
517 struct turnstile *ret_turnstile = TURNSTILE_NULL;
518
519 SLIST_FOREACH(ts, &ts_bucket->ts_ht_bucket_list, ts_htable_link) {
520 if (ts->ts_proprietor == proprietor) {
521 /* Found an entry in the hashtable for this proprietor */
522 ret_turnstile = ts;
523 break;
524 }
525 }
526
527 turnstile_bucket_unlock(ts_bucket);
528 splx(s);
529 return ret_turnstile;
530}
531
532/*
533 * Name: turnstiles_init
534 *
535 * Description: Initialize turnstile sub system.
536 *
537 * Args: None.
538 *
539 * Returns: None.
540 */
541void
542turnstiles_init(void)
543{
544 turnstiles_zone = zinit(sizeof(struct turnstile),
545 MAX_TURNSTILES * sizeof(struct turnstile),
546 TURNSTILES_CHUNK * sizeof(struct turnstile),
547 "turnstiles");
548
549 if (!PE_parse_boot_argn("turnstile_max_hop", &turnstile_max_hop, sizeof(turnstile_max_hop))) {
550 turnstile_max_hop = TURNSTILE_MAX_HOP_DEFAULT;
551 }
552
553 turnstiles_hashtable_init();
554
555#if DEVELOPMENT || DEBUG
556 /* Initialize the global turnstile locks and lock group */
557
558 lck_grp_attr_setdefault(&turnstiles_dev_lock_grp_attr);
559 lck_grp_init(&turnstiles_dev_lock_grp, "turnstiles_dev_lock", &turnstiles_dev_lock_grp_attr);
560 lck_attr_setdefault(&turnstiles_dev_lock_attr);
561 global_turnstiles_lock_init();
562
563 queue_init(&turnstiles_list);
564
565 /* Initialize turnstile test primitive */
566 tstile_test_prim_init(&test_prim_ts_inline);
567 tstile_test_prim_init(&test_prim_global_htable);
568#endif
569 return;
570}
571
572/*
573 * Name: turnstile_alloc
574 *
575 * Description: Allocate a turnstile.
576 *
577 * Args: None.
578 *
579 * Returns:
580 * turnstile on Success.
581 */
582struct turnstile *
583turnstile_alloc(void)
584{
585 struct turnstile *turnstile = TURNSTILE_NULL;
586
587 turnstile = zalloc(turnstiles_zone);
588 turnstile_init(turnstile);
589
590#if DEVELOPMENT || DEBUG
591 /* Add turnstile to global list */
592 global_turnstiles_lock();
593 queue_enter(&turnstiles_list, turnstile,
594 struct turnstile *, ts_global_elm);
595 global_turnstiles_unlock();
596#endif
597 return turnstile;
598}
599
600/*
601 * Name: turnstile_init
602 *
603 * Description: Initialize the turnstile.
604 *
605 * Args:
606 * Arg1: turnstile to initialize
607 *
608 * Returns: None.
609 */
610static void
611turnstile_init(struct turnstile *turnstile)
612{
613 kern_return_t kret;
614
615 /* Initialize the waitq */
616 kret = waitq_init(&turnstile->ts_waitq, SYNC_POLICY_DISABLE_IRQ | SYNC_POLICY_REVERSED |
617 SYNC_POLICY_TURNSTILE);
618 assert(kret == KERN_SUCCESS);
619
620 turnstile->ts_inheritor = TURNSTILE_INHERITOR_NULL;
621 SLIST_INIT(&turnstile->ts_free_turnstiles);
622 turnstile->ts_type_gencount = 0;
623 turnstile_set_type_and_increment_gencount(turnstile, TURNSTILE_NONE);
624 turnstile_state_init(turnstile, TURNSTILE_STATE_THREAD);
625 os_ref_init_count(&turnstile->ts_refcount, &turnstile_refgrp, 1);
626 turnstile->ts_proprietor = TURNSTILE_PROPRIETOR_NULL;
627 turnstile->ts_priority = MAXPRI_THROTTLE;
628 turnstile->ts_inheritor_flags = TURNSTILE_UPDATE_FLAGS_NONE;
629 turnstile->ts_port_ref = 0;
630 priority_queue_init(&turnstile->ts_inheritor_queue,
631 PRIORITY_QUEUE_BUILTIN_MAX_HEAP);
632
633#if DEVELOPMENT || DEBUG
634 turnstile->ts_thread = current_thread();
635 turnstile->ts_prev_thread = NULL;
636#endif
637}
638
639/*
640 * Name: turnstile_reference
641 *
642 * Description: Take a reference on the turnstile.
643 *
644 * Arg1: turnstile
645 *
646 * Returns: None.
647 */
648void
649turnstile_reference(struct turnstile *turnstile)
650{
651 if (turnstile == TURNSTILE_NULL) {
652 return;
653 }
654 os_ref_retain(&turnstile->ts_refcount);
655}
656
657/*
658 * Name: turnstile_deallocate
659 *
660 * Description: Drop a reference on the turnstile.
661 * Destroy the turnstile if the last ref.
662 *
663 * Arg1: turnstile
664 *
665 * Returns: None.
666 */
667void
668turnstile_deallocate(struct turnstile *turnstile)
669{
670 if (turnstile == TURNSTILE_NULL) {
671 return;
672 }
673
674 if (__improbable(os_ref_release(&turnstile->ts_refcount) == 0)) {
675 turnstile_destroy(turnstile);
676 }
677}
678
679/*
680 * Name: turnstile_deallocate_safe
681 *
682 * Description: Drop a reference on the turnstile safely without triggering zfree.
683 *
684 * Arg1: turnstile
685 *
686 * Returns: None.
687 */
688void
689turnstile_deallocate_safe(struct turnstile *turnstile)
690{
691 if (turnstile == TURNSTILE_NULL) {
692 return;
693 }
694
695 if (__improbable(os_ref_release(&turnstile->ts_refcount) == 0)) {
696 /* enqueue the turnstile for thread deallocate deamon to call turnstile_destroy */
697 turnstile_deallocate_enqueue(turnstile);
698 }
699}
700
701/*
702 * Name: turnstile_destroy
703 *
704 * Description: Deallocates the turnstile.
705 *
706 * Args:
707 * Arg1: turnstile
708 *
709 * Returns: None.
710 */
711void
712turnstile_destroy(struct turnstile *turnstile)
713{
714 /* destroy the waitq */
715 waitq_deinit(&turnstile->ts_waitq);
716
717 assert(turnstile->ts_inheritor == TURNSTILE_INHERITOR_NULL);
718 assert(SLIST_EMPTY(&turnstile->ts_free_turnstiles));
719 assert(turnstile->ts_state & TURNSTILE_STATE_THREAD);
720#if DEVELOPMENT || DEBUG
721 /* Remove turnstile from global list */
722 global_turnstiles_lock();
723 queue_remove(&turnstiles_list, turnstile,
724 struct turnstile *, ts_global_elm);
725 global_turnstiles_unlock();
726#endif
727 zfree(turnstiles_zone, turnstile);
728}
729
730/*
731 * Name: turnstile_prepare
732 *
733 * Description: Transfer current thread's turnstile to primitive or it's free turnstile list.
734 * Function is called holding the interlock (spinlock) of the primitive.
735 * The turnstile returned by this function is safe to use untill the thread calls turnstile_complete.
736 * When no turnstile is provided explicitly, the calling thread will not have a turnstile attached to
737 * it untill it calls turnstile_complete.
738 *
739 * Args:
740 * Arg1: proprietor
741 * Arg2: pointer in primitive struct to store turnstile
742 * Arg3: turnstile to use instead of taking it from thread.
743 * Arg4: type of primitive
744 *
745 * Returns:
746 * turnstile.
747 */
748struct turnstile *
749turnstile_prepare(
750 uintptr_t proprietor,
751 struct turnstile **tstore,
752 struct turnstile *turnstile,
753 turnstile_type_t type)
754{
755 thread_t thread = current_thread();
756 struct turnstile *ret_turnstile = TURNSTILE_NULL;
757 struct turnstile *thread_turnstile = turnstile;
758
759 /* Get the thread's turnstile if no turnstile provided */
760 if (thread_turnstile == TURNSTILE_NULL) {
761 thread_turnstile = thread->turnstile;
762 assert(thread_turnstile != TURNSTILE_NULL);
763 assert(thread->inheritor == NULL);
764 thread->turnstile = TURNSTILE_NULL;
765 }
766
767 /* Prepare the thread turnstile to be the primitive turnstile */
768 SLIST_INIT(&thread_turnstile->ts_free_turnstiles);
769 turnstile_set_type_and_increment_gencount(thread_turnstile, type);
770 thread_turnstile->ts_inheritor = TURNSTILE_INHERITOR_NULL;
771 thread_turnstile->ts_proprietor = proprietor;
772 turnstile_state_remove(thread_turnstile, TURNSTILE_STATE_THREAD);
773
774 thread_turnstile->ts_priority = MAXPRI_THROTTLE;
775#if DEVELOPMENT || DEBUG
776 thread_turnstile->ts_prev_thread = thread_turnstile->ts_thread;
777 thread_turnstile->ts_thread = NULL;
778#endif
779
780 if (tstore != NULL) {
781 /*
782 * If the primitive stores the turnstile,
783 * If there is already a turnstile, put the thread_turnstile if the primitive currently does not have a
784 * turnstile.
785 * Else, add the thread turnstile to freelist of the primitive turnstile.
786 */
787 ret_turnstile = *tstore;
788 if (*tstore == TURNSTILE_NULL) {
789 turnstile_state_add(thread_turnstile, TURNSTILE_STATE_PROPRIETOR);
790 *tstore = thread_turnstile;
791 KERNEL_DEBUG_CONSTANT_IST(KDEBUG_TRACE,
792 (TURNSTILE_CODE(TURNSTILE_FREELIST_OPERATIONS, (TURNSTILE_PREPARE))) | DBG_FUNC_NONE,
793 VM_KERNEL_UNSLIDE_OR_PERM(thread_turnstile),
794 VM_KERNEL_UNSLIDE_OR_PERM(proprietor),
795 turnstile_get_type(thread_turnstile), 0, 0);
796 } else {
797 turnstile_freelist_insert(ret_turnstile, thread_turnstile);
798 }
799 ret_turnstile = *tstore;
800 } else {
801 /*
802 * Lookup the primitive in the turnstile hash table and see if it already has an entry.
803 */
804 ret_turnstile = turnstile_htable_lookup_add(proprietor, thread_turnstile);
805 if (ret_turnstile == NULL) {
806 ret_turnstile = thread_turnstile;
807 KERNEL_DEBUG_CONSTANT_IST(KDEBUG_TRACE,
808 (TURNSTILE_CODE(TURNSTILE_FREELIST_OPERATIONS, (TURNSTILE_PREPARE))) | DBG_FUNC_NONE,
809 VM_KERNEL_UNSLIDE_OR_PERM(thread_turnstile),
810 VM_KERNEL_UNSLIDE_OR_PERM(proprietor),
811 turnstile_get_type(thread_turnstile), 0, 0);
812 }
813 }
814
815 return ret_turnstile;
816}
817
818/*
819 * Name: turnstile_complete
820 *
821 * Description: Transfer the primitive's turnstile or from it's freelist to current thread.
822 * Function is called holding the interlock (spinlock) of the primitive.
823 * Current thread will have a turnstile attached to it after this call.
824 *
825 * Args:
826 * Arg1: proprietor
827 * Arg2: pointer in primitive struct to update turnstile
828 * Arg3: pointer to store the returned turnstile instead of attaching it to thread
829 *
830 * Returns:
831 * None.
832 */
833void
834turnstile_complete(
835 uintptr_t proprietor,
836 struct turnstile **tstore,
837 struct turnstile **out_turnstile)
838{
839 thread_t thread = current_thread();
840 struct turnstile *primitive_turnstile = TURNSTILE_NULL;
841 struct turnstile *thread_turnstile = TURNSTILE_NULL;
842
843 assert(thread->inheritor == NULL);
844
845 if (tstore != NULL) {
846 /*
847 * If the primitive stores the turnstile, check if the primitive turnstile
848 * has any turnstiles on its freelist.
849 */
850 assert(*tstore != TURNSTILE_NULL);
851 if (turnstile_freelist_empty(*tstore)) {
852 /* Last turnstile scenario; remove the primitive->turnstile */
853 thread_turnstile = *tstore;
854 *tstore = TURNSTILE_NULL;
855 turnstile_state_remove(thread_turnstile, TURNSTILE_STATE_PROPRIETOR);
856 } else {
857 /* Freelist has turnstiles; remove one from the freelist */
858 thread_turnstile = turnstile_freelist_remove(*tstore);
859 }
860 primitive_turnstile = *tstore;
861 } else {
862 /* Use the global hash to find and remove a turnstile */
863 primitive_turnstile = turnstable_htable_lookup_remove(proprietor, &thread_turnstile);
864 }
865 if (primitive_turnstile == NULL) {
866 /*
867 * Primitive no longer has a turnstile associated with it, thread_turnstile
868 * was the last turnstile attached to primitive, clear out the inheritor and
869 * set the old inheritor for turnstile cleanup.
870 */
871 if (thread_turnstile->ts_inheritor != TURNSTILE_INHERITOR_NULL) {
872 turnstile_update_inheritor(thread_turnstile, TURNSTILE_INHERITOR_NULL,
873 (TURNSTILE_IMMEDIATE_UPDATE | TURNSTILE_INHERITOR_THREAD));
874 /*
875 * old inheritor is set in curret thread and its priority propagation
876 * will happen in turnstile cleanup call
877 */
878 }
879 assert(thread_turnstile->ts_inheritor == TURNSTILE_INHERITOR_NULL);
880
881 KERNEL_DEBUG_CONSTANT_IST(KDEBUG_TRACE,
882 (TURNSTILE_CODE(TURNSTILE_FREELIST_OPERATIONS, (TURNSTILE_COMPLETE))) | DBG_FUNC_NONE,
883 VM_KERNEL_UNSLIDE_OR_PERM(thread_turnstile),
884 VM_KERNEL_UNSLIDE_OR_PERM(proprietor),
885 turnstile_get_type(thread_turnstile), 0, 0);
886 } else {
887 /* If primitive's turnstile needs priority update, set it up for turnstile cleanup */
888 if (turnstile_recompute_priority(primitive_turnstile)) {
889 turnstile_reference(primitive_turnstile);
890 thread->inheritor = primitive_turnstile;
891 thread->inheritor_flags = (TURNSTILE_INHERITOR_TURNSTILE |
892 TURNSTILE_INHERITOR_NEEDS_PRI_UPDATE);
893 }
894 }
895
896 turnstile_set_type_and_increment_gencount(thread_turnstile, TURNSTILE_NONE);
897#if DEVELOPMENT || DEBUG
898 thread_turnstile->ts_prev_thread = NULL;
899 thread_turnstile->ts_thread = thread;
900#endif
901
902 turnstile_state_add(thread_turnstile, TURNSTILE_STATE_THREAD);
903 if (out_turnstile == NULL) {
904 /* Prepare the turnstile to become the thread's turnstile */
905 thread->turnstile = thread_turnstile;
906 } else {
907 *out_turnstile = thread_turnstile;
908 }
909 return;
910}
911
912/*
913 * Name: turnstile_update_inheritor_locked
914 *
915 * Description: Update the inheritor of the turnstile and boost the
916 * inheritor, called with turnstile locked.
917 *
918 * Args:
919 * Arg1: turnstile
920 * Implicit arg: new inheritor value is stashed in current thread's struct
921 *
922 * Returns:
923 * old inheritor reference is returned on current thread's struct.
924 */
925void
926turnstile_update_inheritor_locked(
927 struct turnstile *turnstile)
928{
929 turnstile_inheritor_t old_inheritor = turnstile->ts_inheritor;
930 turnstile_update_flags_t old_inheritor_flags = turnstile->ts_inheritor_flags;
931 thread_t thread = current_thread();
932 boolean_t old_inheritor_needs_update = FALSE;
933 boolean_t new_inheritor_needs_update = FALSE;
934 turnstile_stats_update_flags_t tsu_flags =
935 turnstile_get_update_flags_for_above_UI_pri_change(turnstile);
936
937 assert(waitq_held(&turnstile->ts_waitq));
938
939 /*
940 * Get the new inheritor value from current thread's
941 * struct, the value was stashed by turnstile_update_inheritor
942 */
943 turnstile_inheritor_t new_inheritor = thread->inheritor;
944 turnstile_update_flags_t new_inheritor_flags = thread->inheritor_flags;
945
946 switch (turnstile_promote_policy[turnstile_get_type(turnstile)]) {
947 case TURNSTILE_USER_PROMOTE:
948 case TURNSTILE_USER_IPC_PROMOTE:
949
950 /* Check if update is needed */
951 if (old_inheritor == new_inheritor && old_inheritor == NULL) {
952 break;
953 }
954
955 if (old_inheritor == new_inheritor) {
956 if (new_inheritor_flags & TURNSTILE_INHERITOR_THREAD) {
957 thread_t thread_inheritor = (thread_t)new_inheritor;
958
959 assert(old_inheritor_flags & TURNSTILE_INHERITOR_THREAD);
960
961 /* adjust turnstile position in the thread's inheritor list */
962 new_inheritor_needs_update = thread_update_turnstile_promotion(
963 thread_inheritor, turnstile);
964
965 } else if (new_inheritor_flags & TURNSTILE_INHERITOR_TURNSTILE) {
966 struct turnstile *inheritor_turnstile = new_inheritor;
967
968 assert(old_inheritor_flags & TURNSTILE_INHERITOR_TURNSTILE);
969
970 new_inheritor_needs_update = turnstile_update_turnstile_promotion(
971 inheritor_turnstile, turnstile);
972
973 } else if (new_inheritor_flags & TURNSTILE_INHERITOR_WORKQ) {
974 /*
975 * When we are still picking "WORKQ" then possible racing
976 * updates will call redrive through their own propagation
977 * and we don't need to update anything here.
978 */
979 turnstile_stats_update(1, TSU_NO_PRI_CHANGE_NEEDED |
980 TSU_TURNSTILE_ARG | TSU_BOOST_ARG, turnstile);
981 } else {
982 panic("Inheritor flags lost along the way");
983 }
984
985 /* Update turnstile stats */
986 if (!new_inheritor_needs_update) {
987 turnstile_stats_update(1, TSU_PRI_PROPAGATION |
988 TSU_TURNSTILE_ARG | TSU_BOOST_ARG | tsu_flags, turnstile);
989 }
990 break;
991 }
992
993 if (old_inheritor != NULL) {
994 if (old_inheritor_flags & TURNSTILE_INHERITOR_THREAD) {
995 thread_t thread_inheritor = (thread_t)old_inheritor;
996
997 /* remove turnstile from thread's inheritor list */
998 old_inheritor_needs_update = thread_remove_turnstile_promotion(thread_inheritor, turnstile);
999
1000 } else if (old_inheritor_flags & TURNSTILE_INHERITOR_TURNSTILE) {
1001 struct turnstile *old_turnstile = old_inheritor;
1002
1003 old_inheritor_needs_update = turnstile_remove_turnstile_promotion(
1004 old_turnstile, turnstile);
1005
1006 } else if (old_inheritor_flags & TURNSTILE_INHERITOR_WORKQ) {
1007 /*
1008 * We don't need to do anything when the push was WORKQ
1009 * because nothing is pushed on in the first place.
1010 */
1011 turnstile_stats_update(1, TSU_NO_PRI_CHANGE_NEEDED |
1012 TSU_TURNSTILE_ARG, turnstile);
1013 } else {
1014 panic("Inheritor flags lost along the way");
1015 }
1016 /* Update turnstile stats */
1017 if (!old_inheritor_needs_update) {
1018 turnstile_stats_update(1, TSU_PRI_PROPAGATION | TSU_TURNSTILE_ARG,
1019 turnstile);
1020 }
1021 }
1022
1023 if (new_inheritor != NULL) {
1024 if (new_inheritor_flags & TURNSTILE_INHERITOR_THREAD) {
1025 thread_t thread_inheritor = (thread_t)new_inheritor;
1026
1027 assert(new_inheritor_flags & TURNSTILE_INHERITOR_THREAD);
1028 /* add turnstile to thread's inheritor list */
1029 new_inheritor_needs_update = thread_add_turnstile_promotion(
1030 thread_inheritor, turnstile);
1031
1032 } else if (new_inheritor_flags & TURNSTILE_INHERITOR_TURNSTILE) {
1033 struct turnstile *new_turnstile = new_inheritor;
1034
1035 new_inheritor_needs_update = turnstile_add_turnstile_promotion(
1036 new_turnstile, turnstile);
1037
1038 } else if (new_inheritor_flags & TURNSTILE_INHERITOR_WORKQ) {
1039 struct workqueue *wq_inheritor = new_inheritor;
1040
1041 new_inheritor_needs_update = workq_add_turnstile_promotion(
1042 wq_inheritor, turnstile);
1043 if (!new_inheritor_needs_update) {
1044 turnstile_stats_update(1, TSU_NO_PRI_CHANGE_NEEDED |
1045 TSU_TURNSTILE_ARG | TSU_BOOST_ARG, turnstile);
1046 }
1047 } else {
1048 panic("Inheritor flags lost along the way");
1049 }
1050 /* Update turnstile stats */
1051 if (!new_inheritor_needs_update) {
1052 turnstile_stats_update(1, TSU_PRI_PROPAGATION |
1053 TSU_TURNSTILE_ARG | TSU_BOOST_ARG | tsu_flags,turnstile);
1054 }
1055 }
1056
1057 break;
1058
1059 case TURNSTILE_KERNEL_PROMOTE:
1060 break;
1061 default:
1062 panic("turnstile promotion for type %d not yet implemented", turnstile_get_type(turnstile));
1063 }
1064
1065 if (old_inheritor_needs_update) {
1066 old_inheritor_flags |= TURNSTILE_INHERITOR_NEEDS_PRI_UPDATE;
1067 }
1068
1069 /*
1070 * If new inheritor needs priority updated, then set TURNSTILE_NEEDS_PRI_UPDATE
1071 * on the old_inheritor_flags which will be copied to the thread.
1072 */
1073 if (new_inheritor_needs_update) {
1074 old_inheritor_flags |= TURNSTILE_NEEDS_PRI_UPDATE;
1075 }
1076
1077 turnstile->ts_inheritor = new_inheritor;
1078 turnstile->ts_inheritor_flags = new_inheritor_flags;
1079 thread->inheritor = old_inheritor;
1080 thread->inheritor_flags = old_inheritor_flags;
1081 return;
1082}
1083
1084/*
1085 * Name: turnstile_update_inheritor
1086 *
1087 * Description: Update the inheritor of the turnstile and boost the
1088 * inheritor. It will take a thread reference on the inheritor.
1089 * Called with the interlock of the primitive held.
1090 *
1091 * Args:
1092 * Arg1: turnstile
1093 * Arg2: inheritor
1094 * Arg3: flags - TURNSTILE_DELAYED_UPDATE - update will happen later in assert_wait
1095 *
1096 * Returns:
1097 * old inheritor reference is stashed on current thread's struct.
1098 */
1099void
1100turnstile_update_inheritor(
1101 struct turnstile *turnstile,
1102 turnstile_inheritor_t new_inheritor,
1103 turnstile_update_flags_t flags)
1104{
1105 thread_t thread = current_thread();
1106 spl_t spl;
1107
1108 /*
1109 * Set the inheritor on calling thread struct, no need
1110 * to take the turnstile waitq lock since the inheritor
1111 * is protected by the primitive's interlock
1112 */
1113 assert(thread->inheritor == TURNSTILE_INHERITOR_NULL);
1114 thread->inheritor = new_inheritor;
1115 thread->inheritor_flags = TURNSTILE_UPDATE_FLAGS_NONE;
1116 if (new_inheritor == TURNSTILE_INHERITOR_NULL) {
1117 /* nothing to retain or remember */
1118 } else if (flags & TURNSTILE_INHERITOR_THREAD) {
1119 thread->inheritor_flags |= TURNSTILE_INHERITOR_THREAD;
1120 thread_reference((thread_t)new_inheritor);
1121 } else if (flags & TURNSTILE_INHERITOR_TURNSTILE) {
1122 thread->inheritor_flags |= TURNSTILE_INHERITOR_TURNSTILE;
1123 turnstile_reference((struct turnstile *)new_inheritor);
1124 } else if (flags & TURNSTILE_INHERITOR_WORKQ) {
1125 thread->inheritor_flags |= TURNSTILE_INHERITOR_WORKQ;
1126 workq_reference((struct workqueue *)new_inheritor);
1127 } else {
1128 panic("Missing type in flags (%x) for inheritor (%p)", flags,
1129 new_inheritor);
1130 }
1131
1132 /* Do not perform the update if delayed update is specified */
1133 if (flags & TURNSTILE_DELAYED_UPDATE) {
1134 return;
1135 }
1136
1137 /* lock the turnstile waitq */
1138 spl = splsched();
1139 waitq_lock(&turnstile->ts_waitq);
1140
1141 turnstile_update_inheritor_locked(turnstile);
1142
1143 waitq_unlock(&turnstile->ts_waitq);
1144 splx(spl);
1145
1146 return;
1147}
1148
1149
1150/*
1151 * Name: turnstile_need_thread_promotion_update
1152 *
1153 * Description: Check if thread's place in the turnstile waitq needs to be updated.
1154 *
1155 * Arg1: dst turnstile
1156 * Arg2: thread
1157 *
1158 * Returns: TRUE: if turnstile_update_thread_promotion_locked needs to be called.
1159 * FALSE: otherwise.
1160 *
1161 * Condition: thread locked.
1162 */
1163static boolean_t
1164turnstile_need_thread_promotion_update(
1165 struct turnstile *dst_turnstile __assert_only,
1166 thread_t thread)
1167{
1168 int thread_link_priority;
1169 boolean_t needs_update = FALSE;
1170
1171 thread_link_priority = priority_queue_entry_key(&(dst_turnstile->ts_waitq.waitq_prio_queue),
1172 &(thread->wait_prioq_links));
1173
1174 needs_update = (thread_link_priority == thread->base_pri) ? FALSE : TRUE;
1175 return needs_update;
1176}
1177
1178/*
1179 * Name: turnstile_priority_queue_update_entry_key
1180 *
1181 * Description: Updates the priority of an entry in a priority queue
1182 *
1183 * Arg1: a turnstile/thread/... priority queue
1184 * Arg2: the element to change the priority of
1185 * Arg3: the new priority
1186 *
1187 * Returns: whether the maximum priority of the queue changed.
1188 */
1189static boolean_t
1190turnstile_priority_queue_update_entry_key(struct priority_queue *q,
1191 priority_queue_entry_t elt, priority_queue_key_t pri)
1192{
1193 priority_queue_key_t old_key = priority_queue_max_key(q);
1194
1195 if (priority_queue_entry_key(q, elt) < pri) {
1196 if (priority_queue_entry_increase(q, elt, pri,
1197 PRIORITY_QUEUE_SCHED_PRI_MAX_HEAP_COMPARE)) {
1198 return old_key != priority_queue_max_key(q);
1199 }
1200 } else if (priority_queue_entry_key(q, elt) > pri) {
1201 if (priority_queue_entry_decrease(q, elt, pri,
1202 PRIORITY_QUEUE_SCHED_PRI_MAX_HEAP_COMPARE)) {
1203 return old_key != priority_queue_max_key(q);
1204 }
1205 }
1206
1207 return FALSE;
1208}
1209
1210/*
1211 * Name: turnstile_update_thread_promotion_locked
1212 *
1213 * Description: Update dst turnstile's inheritor link since one of the waiting
1214 * thread's priority has changed.
1215 *
1216 * Arg1: dst turnstile
1217 * Arg2: thread
1218 *
1219 * Returns: TRUE: if the dst turnstile priority has changed and needs propagation.
1220 * FALSE: if the dst turnstile priority did not change or it does not need propagation.
1221 *
1222 * Condition: dst turnstile and thread are locked.
1223 */
1224static boolean_t
1225turnstile_update_thread_promotion_locked(
1226 struct turnstile *dst_turnstile,
1227 thread_t thread)
1228{
1229 int thread_link_priority = priority_queue_entry_key(&(dst_turnstile->ts_waitq.waitq_prio_queue),
1230 &(thread->wait_prioq_links));
1231
1232 if (thread->base_pri != thread_link_priority) {
1233 KERNEL_DEBUG_CONSTANT_IST(KDEBUG_TRACE,
1234 (TURNSTILE_CODE(TURNSTILE_HEAP_OPERATIONS, (THREAD_MOVED_IN_TURNSTILE_WAITQ))) | DBG_FUNC_NONE,
1235 VM_KERNEL_UNSLIDE_OR_PERM(dst_turnstile),
1236 thread_tid(thread),
1237 thread->base_pri,
1238 thread_link_priority, 0);
1239 }
1240
1241 if (!turnstile_priority_queue_update_entry_key(
1242 &dst_turnstile->ts_waitq.waitq_prio_queue,
1243 &thread->wait_prioq_links, thread->base_pri)) {
1244 return FALSE;
1245 }
1246
1247 /* Update dst turnstile's priority */
1248 return turnstile_recompute_priority_locked(dst_turnstile);
1249}
1250
1251
1252/*
1253 * Name: thread_add_turnstile_promotion
1254 *
1255 * Description: Add a turnstile to thread's inheritor list and update thread's priority.
1256 *
1257 * Arg1: thread
1258 * Arg2: turnstile
1259 *
1260 * Returns: TRUE: if the thread's priority has changed and needs propagation.
1261 * FALSE: if the thread's priority did not change or it does not need propagation.
1262 *
1263 * Condition: turnstile locked.
1264 */
1265static boolean_t
1266thread_add_turnstile_promotion(
1267 thread_t thread,
1268 struct turnstile *turnstile)
1269{
1270 boolean_t needs_update = FALSE;
1271
1272 /* Update the pairing heap */
1273 thread_lock(thread);
1274
1275 KERNEL_DEBUG_CONSTANT_IST(KDEBUG_TRACE,
1276 (TURNSTILE_CODE(TURNSTILE_HEAP_OPERATIONS, (TURNSTILE_ADDED_TO_THREAD_HEAP))) | DBG_FUNC_NONE,
1277 thread_tid(thread),
1278 VM_KERNEL_UNSLIDE_OR_PERM(turnstile),
1279 turnstile->ts_priority, 0, 0);
1280
1281 priority_queue_entry_init(&(turnstile->ts_inheritor_links));
1282 if (priority_queue_insert(&thread->inheritor_queue,
1283 &turnstile->ts_inheritor_links, turnstile->ts_priority,
1284 PRIORITY_QUEUE_SCHED_PRI_MAX_HEAP_COMPARE)) {
1285 /* Update thread priority */
1286 needs_update = thread_recompute_user_promotion_locked(thread);
1287 }
1288
1289 /* Update turnstile stats */
1290 if (!needs_update) {
1291 turnstile_stats_update(1,
1292 thread_get_update_flags_for_turnstile_propagation_stoppage(thread) |
1293 TSU_TURNSTILE_ARG | TSU_BOOST_ARG,
1294 turnstile);
1295 }
1296
1297 thread_unlock(thread);
1298 return needs_update;
1299}
1300
1301
1302/*
1303 * Name: thread_remove_turnstile_promotion
1304 *
1305 * Description: Remove turnstile from thread's inheritor list and update thread's priority.
1306 *
1307 * Arg1: thread
1308 * Arg2: turnstile
1309 *
1310 * Returns: TRUE: if the thread's priority has changed and needs propagation.
1311 * FALSE: if the thread's priority did not change or it does not need propagation.
1312 *
1313 * Condition: turnstile locked.
1314 */
1315static boolean_t
1316thread_remove_turnstile_promotion(
1317 thread_t thread,
1318 struct turnstile *turnstile)
1319{
1320 boolean_t needs_update = FALSE;
1321
1322 /* Update the pairing heap */
1323 thread_lock(thread);
1324
1325 KERNEL_DEBUG_CONSTANT_IST(KDEBUG_TRACE,
1326 (TURNSTILE_CODE(TURNSTILE_HEAP_OPERATIONS, (TURNSTILE_REMOVED_FROM_THREAD_HEAP))) | DBG_FUNC_NONE,
1327 thread_tid(thread),
1328 VM_KERNEL_UNSLIDE_OR_PERM(turnstile),
1329 0, 0, 0);
1330
1331 if (priority_queue_remove(&thread->inheritor_queue,
1332 &turnstile->ts_inheritor_links,
1333 PRIORITY_QUEUE_SCHED_PRI_MAX_HEAP_COMPARE)) {
1334 /* Update thread priority */
1335 needs_update = thread_recompute_user_promotion_locked(thread);
1336 }
1337
1338 /* Update turnstile stats */
1339 if (!needs_update) {
1340 turnstile_stats_update(1,
1341 thread_get_update_flags_for_turnstile_propagation_stoppage(thread) | TSU_TURNSTILE_ARG,
1342 turnstile);
1343 }
1344
1345 thread_unlock(thread);
1346 return needs_update;
1347}
1348
1349/*
1350 * Name: thread_needs_turnstile_promotion_update
1351 *
1352 * Description: Check if turnstile position in thread's inheritor list needs to be updated.
1353 *
1354 * Arg1: thread
1355 * Arg2: turnstile
1356 *
1357 * Returns: TRUE: if thread_update_turnstile_promotion needs to be called.
1358 * FALSE: otherwise.
1359 *
1360 * Condition: turnstile locked.
1361 */
1362static boolean_t
1363thread_needs_turnstile_promotion_update(
1364 thread_t thread __assert_only,
1365 struct turnstile *turnstile)
1366{
1367 boolean_t needs_update = FALSE;
1368 int turnstile_link_priority;
1369
1370 /* Update the pairing heap */
1371 turnstile_link_priority = priority_queue_entry_key(&(thread->inheritor_queue),
1372 &(turnstile->ts_inheritor_links));
1373
1374 needs_update = (turnstile_link_priority == turnstile->ts_priority) ? FALSE : TRUE;
1375 return needs_update;
1376}
1377
1378/*
1379 * Name: thread_update_turnstile_promotion_locked
1380 *
1381 * Description: Update turnstile position in thread's inheritor list and update thread's priority.
1382 *
1383 * Arg1: thread
1384 * Arg2: turnstile
1385 *
1386 * Returns: TRUE: if the thread's priority has changed and needs propagation.
1387 * FALSE: if the thread's priority did not change or it does not need propagation.
1388 *
1389 * Condition: turnstile and thread are locked.
1390 */
1391static boolean_t
1392thread_update_turnstile_promotion_locked(
1393 thread_t thread,
1394 struct turnstile *turnstile)
1395{
1396 int turnstile_link_priority = priority_queue_entry_key(&(thread->inheritor_queue),
1397 &(turnstile->ts_inheritor_links));
1398
1399 if (turnstile->ts_priority != turnstile_link_priority) {
1400 KERNEL_DEBUG_CONSTANT_IST(KDEBUG_TRACE,
1401 (TURNSTILE_CODE(TURNSTILE_HEAP_OPERATIONS, (TURNSTILE_MOVED_IN_THREAD_HEAP))) | DBG_FUNC_NONE,
1402 thread_tid(thread),
1403 VM_KERNEL_UNSLIDE_OR_PERM(turnstile),
1404 turnstile->ts_priority,
1405 turnstile_link_priority, 0);
1406 }
1407
1408 if (!turnstile_priority_queue_update_entry_key(&thread->inheritor_queue,
1409 &turnstile->ts_inheritor_links, turnstile->ts_priority)) {
1410 return FALSE;
1411 }
1412
1413 /* Update thread priority */
1414 return thread_recompute_user_promotion_locked(thread);
1415}
1416
1417
1418/*
1419 * Name: thread_update_turnstile_promotion
1420 *
1421 * Description: Update turnstile position in thread's inheritor list and update thread's priority.
1422 *
1423 * Arg1: thread
1424 * Arg2: turnstile
1425 *
1426 * Returns: TRUE: if the thread's priority has changed and needs propagation.
1427 * FALSE: if the thread's priority did not change or it does not need propagation.
1428 *
1429 * Condition: turnstile locked.
1430 */
1431static boolean_t
1432thread_update_turnstile_promotion(
1433 thread_t thread,
1434 struct turnstile *turnstile)
1435{
1436 /* Before grabbing the thread lock, check if update is needed */
1437 boolean_t needs_update = thread_needs_turnstile_promotion_update(thread, turnstile);
1438
1439 if (!needs_update) {
1440 turnstile_stats_update(1, TSU_NO_PRI_CHANGE_NEEDED |
1441 TSU_TURNSTILE_ARG | TSU_BOOST_ARG, turnstile);
1442 return needs_update;
1443 }
1444
1445 /* Update the pairing heap */
1446 thread_lock(thread);
1447 needs_update = thread_update_turnstile_promotion_locked(thread, turnstile);
1448
1449 /* Update turnstile stats */
1450 if (!needs_update) {
1451 turnstile_stats_update(1,
1452 thread_get_update_flags_for_turnstile_propagation_stoppage(thread) |
1453 TSU_TURNSTILE_ARG | TSU_BOOST_ARG,
1454 turnstile);
1455 }
1456 thread_unlock(thread);
1457 return needs_update;
1458}
1459
1460
1461/*
1462 * Name: thread_get_inheritor_turnstile_priority
1463 *
1464 * Description: Get the max priority of all the inheritor turnstiles
1465 *
1466 * Arg1: thread
1467 *
1468 * Returns: Max priority of all the inheritor turnstiles.
1469 *
1470 * Condition: thread locked
1471 */
1472int
1473thread_get_inheritor_turnstile_priority(thread_t thread)
1474{
1475 struct turnstile *max_turnstile;
1476
1477 max_turnstile = priority_queue_max(&thread->inheritor_queue,
1478 struct turnstile, ts_inheritor_links);
1479
1480 if (max_turnstile) {
1481 return priority_queue_entry_key(&thread->inheritor_queue,
1482 &max_turnstile->ts_inheritor_links);
1483 }
1484
1485 return MAXPRI_THROTTLE;
1486}
1487
1488
1489/*
1490 * Name: thread_get_waiting_turnstile
1491 *
1492 * Description: Get the turnstile if the thread is waiting on a turnstile.
1493 *
1494 * Arg1: thread
1495 *
1496 * Returns: turnstile: if the thread is blocked on a turnstile.
1497 * TURNSTILE_NULL: otherwise.
1498 *
1499 * Condition: thread locked.
1500 */
1501struct turnstile *
1502thread_get_waiting_turnstile(thread_t thread)
1503{
1504 struct turnstile *turnstile = TURNSTILE_NULL;
1505 struct waitq *waitq = thread->waitq;
1506
1507 /* Check if the thread is on a waitq */
1508 if (waitq == NULL) {
1509 return turnstile;
1510 }
1511
1512 /* Get the safeq if the waitq is a port queue */
1513 if (waitq_is_port_queue(waitq)) {
1514 waitq = waitq_get_safeq(waitq);
1515 }
1516
1517 /* Check if the waitq is a turnstile queue */
1518 if (waitq_is_turnstile_queue(waitq)) {
1519 turnstile = waitq_to_turnstile(waitq);
1520 }
1521 return turnstile;
1522}
1523
1524
1525/*
1526 * Name: turnstile_lookup_by_proprietor
1527 *
1528 * Description: Get turnstile for a proprietor from global
1529 * turnstile hash.
1530 *
1531 * Arg1: port
1532 *
1533 * Returns: turnstile: if the proprietor has a turnstile.
1534 * TURNSTILE_NULL: otherwise.
1535 *
1536 * Condition: proprietor interlock held.
1537 */
1538struct turnstile *
1539turnstile_lookup_by_proprietor(uintptr_t proprietor)
1540{
1541 return turnstile_htable_lookup(proprietor);
1542}
1543
1544
1545/*
1546 * Name: thread_get_update_flags_for_turnstile_propagation_stoppage
1547 *
1548 * Description: Get the turnstile stats flags based on the thread wait status.
1549 *
1550 * Arg1: thread
1551 *
1552 * Returns: TSU_THREAD_RUNNABLE: if the thread is runnable.
1553 * TSU_NO_TURNSTILE: if thread waiting on a regular waitq.
1554 * TSU_NO_PRI_CHANGE_NEEDED: otherwise.
1555 *
1556 * Condition: thread locked.
1557 */
1558static turnstile_stats_update_flags_t
1559thread_get_update_flags_for_turnstile_propagation_stoppage(thread_t thread)
1560{
1561 struct waitq *waitq = thread->waitq;
1562
1563 /* Check if the thread is on a waitq */
1564 if (waitq == NULL) {
1565 return TSU_THREAD_RUNNABLE;
1566 }
1567
1568 /* Get the safeq if the waitq is a port queue */
1569 if (waitq_is_port_queue(waitq)) {
1570 waitq = waitq_get_safeq(waitq);
1571 }
1572
1573 /* Check if the waitq is a turnstile queue */
1574 if (!waitq_is_turnstile_queue(waitq)) {
1575 return TSU_NO_TURNSTILE;
1576 }
1577
1578 /* Thread blocked on turnstile waitq but no propagation needed */
1579 return TSU_NO_PRI_CHANGE_NEEDED;
1580}
1581
1582
1583/*
1584 * Name: turnstile_get_update_flags_for_above_UI_pri_change
1585 *
1586 * Description: Get the turnstile stats flags based on the turnstile priority.
1587 *
1588 * Arg1: turnstile
1589 *
1590 * Returns: TSU_ABOVE_UI_PRI_CHANGE: if turnstile priority is above 47 and it is not an ulock.
1591 * TSU_FLAGS_NONE: otherwise.
1592 *
1593 * Condition: turnstile locked.
1594 */
1595static turnstile_stats_update_flags_t
1596turnstile_get_update_flags_for_above_UI_pri_change(struct turnstile *turnstile)
1597{
1598 if (turnstile->ts_priority >
1599 (thread_qos_policy_params.qos_pri[THREAD_QOS_USER_INTERACTIVE] + 1) &&
1600 turnstile_get_type(turnstile) != TURNSTILE_ULOCK) {
1601 return TSU_ABOVE_UI_PRI_CHANGE;
1602
1603 }
1604
1605 return TSU_FLAGS_NONE;
1606}
1607
1608
1609/*
1610 * Name: workq_add_turnstile_promotion
1611 *
1612 * Description: Connect the workqueue turnstile to the workqueue as a fake
1613 * inheritor
1614 *
1615 * Arg1: workqueue
1616 * Arg2: turnstile
1617 *
1618 * Condition: turnstile locked.
1619 */
1620static boolean_t
1621workq_add_turnstile_promotion(
1622 struct workqueue *wq_inheritor __unused,
1623 struct turnstile *turnstile)
1624{
1625 /*
1626 * If the push is higher than MAXPRI_THROTTLE then the workqueue should
1627 * bring up a thread.
1628 */
1629 return turnstile->ts_priority > MAXPRI_THROTTLE;
1630}
1631
1632/*
1633 * Name: turnstile_need_turnstile_promotion_update
1634 *
1635 * Description: Check if turnstile position in turnstile's inheritor list needs to be updated.
1636 *
1637 * Arg1: dst turnstile
1638 * Arg2: src turnstile
1639 *
1640 * Returns: TRUE: if turnstile_update_turnstile_promotion needs to be called.
1641 * FALSE: otherwise.
1642 *
1643 * Condition: src turnstile locked.
1644 */
1645static boolean_t
1646turnstile_need_turnstile_promotion_update(
1647 struct turnstile *dst_turnstile __assert_only,
1648 struct turnstile *src_turnstile)
1649{
1650 int src_turnstile_link_priority;
1651 boolean_t needs_update = FALSE;
1652
1653 src_turnstile_link_priority = priority_queue_entry_key(&(dst_turnstile->ts_inheritor_queue),
1654 &(src_turnstile->ts_inheritor_links));
1655
1656 needs_update = (src_turnstile_link_priority == src_turnstile->ts_priority) ? FALSE : TRUE;
1657 return needs_update;
1658}
1659
1660/*
1661 * Name: turnstile_update_turnstile_promotion_locked
1662 *
1663 * Description: Update dst turnstile's inheritor link since src turnstile's
1664 * promote priority has changed.
1665 *
1666 * Arg1: dst turnstile
1667 * Arg2: src turnstile
1668 *
1669 * Returns: TRUE: if the dst turnstile priority has changed and needs propagation.
1670 * FALSE: if the dst turnstile priority did not change or it does not need propagation.
1671 *
1672 * Condition: src and dst turnstile locked.
1673 */
1674static boolean_t
1675turnstile_update_turnstile_promotion_locked(
1676 struct turnstile *dst_turnstile,
1677 struct turnstile *src_turnstile)
1678{
1679 int src_turnstile_link_priority;
1680 src_turnstile_link_priority = priority_queue_entry_key(&(dst_turnstile->ts_inheritor_queue),
1681 &(src_turnstile->ts_inheritor_links));
1682
1683 if (src_turnstile->ts_priority != src_turnstile_link_priority) {
1684 KERNEL_DEBUG_CONSTANT_IST(KDEBUG_TRACE,
1685 (TURNSTILE_CODE(TURNSTILE_HEAP_OPERATIONS, (TURNSTILE_MOVED_IN_TURNSTILE_HEAP))) | DBG_FUNC_NONE,
1686 VM_KERNEL_UNSLIDE_OR_PERM(dst_turnstile),
1687 VM_KERNEL_UNSLIDE_OR_PERM(src_turnstile),
1688 src_turnstile->ts_priority, src_turnstile_link_priority, 0);
1689 }
1690
1691 if (!turnstile_priority_queue_update_entry_key(
1692 &dst_turnstile->ts_inheritor_queue, &src_turnstile->ts_inheritor_links,
1693 src_turnstile->ts_priority)) {
1694 return FALSE;
1695 }
1696
1697 /* Update dst turnstile's priority */
1698 return turnstile_recompute_priority_locked(dst_turnstile);
1699}
1700
1701/*
1702 * Name: turnstile_update_turnstile_promotion
1703 *
1704 * Description: Update dst turnstile's inheritor link since src turnstile's
1705 * promote priority has changed.
1706 *
1707 * Arg1: dst turnstile
1708 * Arg2: src turnstile
1709 *
1710 * Returns: TRUE: if the dst turnstile priority has changed and needs propagation.
1711 * FALSE: if the dst turnstile priority did not change or it does not need propagation.
1712 *
1713 * Condition: src turnstile locked.
1714 */
1715static boolean_t
1716turnstile_update_turnstile_promotion(
1717 struct turnstile *dst_turnstile,
1718 struct turnstile *src_turnstile)
1719{
1720 /* Check if update is needed before grabbing the src turnstile lock */
1721 boolean_t needs_update = turnstile_need_turnstile_promotion_update(dst_turnstile, src_turnstile);
1722 if (!needs_update) {
1723 turnstile_stats_update(1, TSU_NO_PRI_CHANGE_NEEDED |
1724 TSU_TURNSTILE_ARG | TSU_BOOST_ARG,
1725 src_turnstile);
1726 return needs_update;
1727 }
1728
1729 /* Update the pairing heap */
1730 waitq_lock(&dst_turnstile->ts_waitq);
1731 needs_update = turnstile_update_turnstile_promotion_locked(dst_turnstile, src_turnstile);
1732
1733 /* Update turnstile stats */
1734 if (!needs_update) {
1735 turnstile_stats_update(1,
1736 (dst_turnstile->ts_inheritor ? TSU_NO_PRI_CHANGE_NEEDED : TSU_NO_INHERITOR) |
1737 TSU_TURNSTILE_ARG | TSU_BOOST_ARG, src_turnstile);
1738 }
1739 waitq_unlock(&dst_turnstile->ts_waitq);
1740 return needs_update;
1741}
1742
1743/*
1744 * Name: turnstile_add_turnstile_promotion
1745 *
1746 * Description: Add src turnstile to dst turnstile's inheritor link
1747 * and update dst turnstile's priority.
1748 *
1749 * Arg1: dst turnstile
1750 * Arg2: src turnstile
1751 *
1752 * Returns: TRUE: if the dst turnstile priority has changed and needs propagation.
1753 * FALSE: if the dst turnstile priority did not change or it does not need propagation.
1754 *
1755 * Condition: src turnstile locked.
1756 */
1757static boolean_t
1758turnstile_add_turnstile_promotion(
1759 struct turnstile *dst_turnstile,
1760 struct turnstile *src_turnstile)
1761{
1762 boolean_t needs_update = FALSE;
1763
1764 /* Update the pairing heap */
1765 waitq_lock(&dst_turnstile->ts_waitq);
1766
1767 KERNEL_DEBUG_CONSTANT_IST(KDEBUG_TRACE,
1768 (TURNSTILE_CODE(TURNSTILE_HEAP_OPERATIONS, (TURNSTILE_ADDED_TO_TURNSTILE_HEAP))) | DBG_FUNC_NONE,
1769 VM_KERNEL_UNSLIDE_OR_PERM(dst_turnstile),
1770 VM_KERNEL_UNSLIDE_OR_PERM(src_turnstile),
1771 src_turnstile->ts_priority, 0, 0);
1772
1773 priority_queue_entry_init(&(src_turnstile->ts_inheritor_links));
1774 if (priority_queue_insert(&dst_turnstile->ts_inheritor_queue,
1775 &src_turnstile->ts_inheritor_links, src_turnstile->ts_priority,
1776 PRIORITY_QUEUE_SCHED_PRI_MAX_HEAP_COMPARE)) {
1777 /* Update dst turnstile priority */
1778 needs_update = turnstile_recompute_priority_locked(dst_turnstile);
1779 }
1780
1781 /* Update turnstile stats */
1782 if (!needs_update) {
1783 turnstile_stats_update(1,
1784 (dst_turnstile->ts_inheritor ? TSU_NO_PRI_CHANGE_NEEDED : TSU_NO_INHERITOR) |
1785 TSU_TURNSTILE_ARG | TSU_BOOST_ARG, src_turnstile);
1786 }
1787
1788 waitq_unlock(&dst_turnstile->ts_waitq);
1789 return needs_update;
1790}
1791
1792/*
1793 * Name: turnstile_remove_turnstile_promotion
1794 *
1795 * Description: Remove src turnstile from dst turnstile's inheritor link
1796 * and update dst turnstile's priority.
1797 *
1798 * Arg1: dst turnstile
1799 * Arg2: src turnstile
1800 *
1801 * Returns: TRUE: if the dst turnstile priority has changed and needs propagation.
1802 * FALSE: if the dst turnstile priority did not change or it does not need propagation.
1803 *
1804 * Condition: src turnstile locked.
1805 */
1806static boolean_t
1807turnstile_remove_turnstile_promotion(
1808 struct turnstile *dst_turnstile,
1809 struct turnstile *src_turnstile)
1810{
1811 boolean_t needs_update = FALSE;
1812
1813 /* Update the pairing heap */
1814 waitq_lock(&dst_turnstile->ts_waitq);
1815
1816 KERNEL_DEBUG_CONSTANT_IST(KDEBUG_TRACE,
1817 (TURNSTILE_CODE(TURNSTILE_HEAP_OPERATIONS, (TURNSTILE_REMOVED_FROM_TURNSTILE_HEAP))) | DBG_FUNC_NONE,
1818 VM_KERNEL_UNSLIDE_OR_PERM(dst_turnstile),
1819 VM_KERNEL_UNSLIDE_OR_PERM(src_turnstile),
1820 0, 0, 0);
1821
1822 if (priority_queue_remove(&dst_turnstile->ts_inheritor_queue,
1823 &src_turnstile->ts_inheritor_links,
1824 PRIORITY_QUEUE_SCHED_PRI_MAX_HEAP_COMPARE)) {
1825 /* Update dst turnstile priority */
1826 needs_update = turnstile_recompute_priority_locked(dst_turnstile);
1827 }
1828
1829 /* Update turnstile stats */
1830 if (!needs_update) {
1831 turnstile_stats_update(1,
1832 (dst_turnstile->ts_inheritor ? TSU_NO_PRI_CHANGE_NEEDED : TSU_NO_INHERITOR) |
1833 TSU_TURNSTILE_ARG, src_turnstile);
1834 }
1835
1836 waitq_unlock(&dst_turnstile->ts_waitq);
1837 return needs_update;
1838}
1839
1840/*
1841 * Name: turnstile_recompute_priority_locked
1842 *
1843 * Description: Update turnstile priority based
1844 * on highest waiter thread and highest blocking
1845 * turnstile.
1846 *
1847 * Args: turnstile
1848 *
1849 * Returns: TRUE: if the turnstile priority changed and needs propagation.
1850 * FALSE: if the turnstile priority did not change or it does not need propagation.
1851 *
1852 * Condition: turnstile locked
1853 */
1854boolean_t
1855turnstile_recompute_priority_locked(
1856 struct turnstile *turnstile)
1857{
1858 int old_priority;
1859 int new_priority;
1860 boolean_t needs_priority_update = FALSE;
1861 thread_t max_thread = THREAD_NULL;
1862 struct turnstile *max_turnstile;
1863 int thread_max_pri = MAXPRI_THROTTLE;
1864 int turnstile_max_pri = MAXPRI_THROTTLE;
1865
1866 switch (turnstile_promote_policy[turnstile_get_type(turnstile)]) {
1867
1868 case TURNSTILE_USER_PROMOTE:
1869 case TURNSTILE_USER_IPC_PROMOTE:
1870
1871 old_priority = turnstile->ts_priority;
1872
1873 max_thread = priority_queue_max(&turnstile->ts_waitq.waitq_prio_queue,
1874 struct thread, wait_prioq_links);
1875
1876 if (max_thread) {
1877 thread_max_pri = priority_queue_entry_key(&turnstile->ts_waitq.waitq_prio_queue,
1878 &max_thread->wait_prioq_links);
1879 }
1880
1881 max_turnstile = priority_queue_max(&turnstile->ts_inheritor_queue,
1882 struct turnstile, ts_inheritor_links);
1883
1884 if (max_turnstile) {
1885 turnstile_max_pri = priority_queue_entry_key(&turnstile->ts_inheritor_queue,
1886 &max_turnstile->ts_inheritor_links);
1887 }
1888
1889 new_priority = max(thread_max_pri, turnstile_max_pri);
1890 turnstile->ts_priority = new_priority;
1891
1892 if (old_priority != new_priority) {
1893 KERNEL_DEBUG_CONSTANT_IST(KDEBUG_TRACE,
1894 (TURNSTILE_CODE(TURNSTILE_PRIORITY_OPERATIONS,
1895 (TURNSTILE_PRIORITY_CHANGE))) | DBG_FUNC_NONE,
1896 VM_KERNEL_UNSLIDE_OR_PERM(turnstile),
1897 new_priority,
1898 old_priority,
1899 0, 0);
1900 }
1901 needs_priority_update = (!(old_priority == new_priority)) &&
1902 (turnstile->ts_inheritor != NULL);
1903 break;
1904
1905 case TURNSTILE_PROMOTE_NONE:
1906 case TURNSTILE_KERNEL_PROMOTE:
1907
1908 /* The turnstile was repurposed, do nothing */
1909 break;
1910
1911 default:
1912
1913 panic("Needs implementation for turnstile_recompute_priority");
1914 break;
1915
1916 }
1917 return needs_priority_update;
1918
1919}
1920
1921
1922/*
1923 * Name: turnstile_recompute_priority
1924 *
1925 * Description: Update turnstile priority based
1926 * on highest waiter thread and highest blocking
1927 * turnstile.
1928 *
1929 * Args: turnstile
1930 *
1931 * Returns: TRUE: if the turnstile priority changed and needs propagation.
1932 * FALSE: if the turnstile priority did not change or it does not need propagation.
1933 */
1934boolean_t
1935turnstile_recompute_priority(
1936 struct turnstile *turnstile)
1937{
1938 boolean_t needs_priority_update = FALSE;
1939 spl_t s = splsched();
1940
1941 waitq_lock(&turnstile->ts_waitq);
1942
1943 needs_priority_update = turnstile_recompute_priority_locked(turnstile);
1944
1945 waitq_unlock(&turnstile->ts_waitq);
1946 splx(s);
1947 return needs_priority_update;
1948
1949}
1950
1951
1952/*
1953 * Name: turnstile_workq_proprietor_of_max_turnstile
1954 *
1955 * Description: Returns the highest priority and proprietor of a turnstile
1956 * pushing on a workqueue turnstile.
1957 *
1958 * This will not return waiters that are at priority
1959 * MAXPRI_THROTTLE or lower.
1960 *
1961 * Args: turnstile
1962 *
1963 * Returns:
1964 * Priority of the max entry, or 0
1965 * Pointer to the max entry proprietor
1966 */
1967int
1968turnstile_workq_proprietor_of_max_turnstile(
1969 struct turnstile *turnstile,
1970 uintptr_t *proprietor_out)
1971{
1972 struct turnstile *max_turnstile;
1973 int max_priority = 0;
1974 uintptr_t proprietor = 0;
1975
1976 assert(turnstile_get_type(turnstile) == TURNSTILE_WORKQS);
1977
1978 spl_t s = splsched();
1979
1980 waitq_lock(&turnstile->ts_waitq);
1981
1982 max_turnstile = priority_queue_max(&turnstile->ts_inheritor_queue,
1983 struct turnstile, ts_inheritor_links);
1984 if (max_turnstile) {
1985 max_priority = priority_queue_entry_key(&turnstile->ts_inheritor_queue,
1986 &max_turnstile->ts_inheritor_links);
1987 proprietor = max_turnstile->ts_proprietor;
1988 }
1989
1990 waitq_unlock(&turnstile->ts_waitq);
1991 splx(s);
1992
1993 if (max_priority <= MAXPRI_THROTTLE) {
1994 max_priority = 0;
1995 proprietor = 0;
1996 }
1997 if (proprietor_out) *proprietor_out = proprietor;
1998 return max_priority;
1999}
2000
2001
2002/*
2003 * Name: turnstile_update_inheritor_priority_chain
2004 *
2005 * Description: Update turnstile inheritor's priority and propagate
2006 * the priority if the inheritor is blocked on a turnstile.
2007 *
2008 * Arg1: inheritor
2009 * Arg2: inheritor flags
2010 *
2011 * Returns: None.
2012 */
2013static void
2014turnstile_update_inheritor_priority_chain(
2015 turnstile_inheritor_t inheritor,
2016 turnstile_update_flags_t turnstile_flags)
2017{
2018 struct turnstile *turnstile = TURNSTILE_NULL;
2019 thread_t thread = THREAD_NULL;
2020 int total_hop = 0, thread_hop = 0;
2021 spl_t s;
2022 turnstile_stats_update_flags_t tsu_flags = ((turnstile_flags & TURNSTILE_UPDATE_BOOST) ?
2023 TSU_BOOST_ARG : TSU_FLAGS_NONE) | TSU_PRI_PROPAGATION;
2024
2025 if (inheritor == NULL) {
2026 return;
2027 }
2028
2029 s = splsched();
2030
2031 if (turnstile_flags & TURNSTILE_INHERITOR_THREAD) {
2032 thread = inheritor;
2033 thread_lock(thread);
2034 //TODO: Need to call sched promotion for kernel mutex.
2035 thread_recompute_user_promotion_locked(thread);
2036 } else if (turnstile_flags & TURNSTILE_INHERITOR_TURNSTILE) {
2037 turnstile = inheritor;
2038 waitq_lock(&turnstile->ts_waitq);
2039 turnstile_recompute_priority_locked(turnstile);
2040 tsu_flags |= turnstile_get_update_flags_for_above_UI_pri_change(turnstile);
2041 } else {
2042 /*
2043 * we should never call turnstile_update_inheritor_priority_chain()
2044 * for a workqueue, they have no "chain" after them.
2045 */
2046 assert((turnstile_flags & TURNSTILE_INHERITOR_WORKQ) == 0);
2047 }
2048
2049 while (turnstile != TURNSTILE_NULL || thread != THREAD_NULL) {
2050 if (turnstile != TURNSTILE_NULL) {
2051 if (turnstile->ts_inheritor == NULL) {
2052 turnstile_stats_update(total_hop + 1, TSU_NO_INHERITOR |
2053 TSU_TURNSTILE_ARG | tsu_flags,
2054 turnstile);
2055 waitq_unlock(&turnstile->ts_waitq);
2056 turnstile = TURNSTILE_NULL;
2057 break;
2058 }
2059 if (turnstile->ts_inheritor_flags & TURNSTILE_INHERITOR_THREAD) {
2060 turnstile_update_inheritor_thread_priority_chain(&turnstile, &thread,
2061 total_hop, tsu_flags);
2062
2063 } else if (turnstile->ts_inheritor_flags & TURNSTILE_INHERITOR_TURNSTILE) {
2064 turnstile_update_inheritor_turnstile_priority_chain(&turnstile,
2065 total_hop, tsu_flags);
2066
2067 } else if (turnstile->ts_inheritor_flags & TURNSTILE_INHERITOR_WORKQ) {
2068 turnstile_update_inheritor_workq_priority_chain(turnstile, s);
2069 turnstile_stats_update(total_hop + 1, TSU_NO_PRI_CHANGE_NEEDED | tsu_flags,
2070 NULL);
2071 return;
2072
2073 } else {
2074 panic("Inheritor flags not passed in turnstile_update_inheritor");
2075 }
2076 } else if (thread != THREAD_NULL) {
2077 thread_update_waiting_turnstile_priority_chain(&thread, &turnstile,
2078 thread_hop, total_hop, tsu_flags);
2079 thread_hop++;
2080 }
2081 total_hop++;
2082 }
2083
2084 splx(s);
2085 return;
2086}
2087
2088/*
2089 * Name: turnstile_update_inheritor_complete
2090 *
2091 * Description: Update turnstile inheritor's priority and propagate the
2092 * priority if the inheritor is blocked on a turnstile.
2093 * Consumes thread ref of old inheritor returned by
2094 * turnstile_update_inheritor. Recursive priority update
2095 * will only happen when called with interlock dropped.
2096 *
2097 * Args:
2098 * Arg1: turnstile
2099 * Arg2: interlock held
2100 *
2101 * Returns: None.
2102 */
2103void
2104turnstile_update_inheritor_complete(
2105 struct turnstile *turnstile,
2106 turnstile_update_complete_flags_t flags __unused)
2107{
2108 thread_t thread = current_thread();
2109
2110 turnstile_update_flags_t inheritor_flags = thread->inheritor_flags;
2111
2112 turnstile_cleanup();
2113
2114 /* Perform priority update for new inheritor */
2115 if (inheritor_flags & TURNSTILE_NEEDS_PRI_UPDATE) {
2116 turnstile_update_inheritor_priority_chain(turnstile,
2117 TURNSTILE_INHERITOR_TURNSTILE | TURNSTILE_UPDATE_BOOST);
2118 }
2119}
2120
2121/*
2122 * Name: turnstile_cleanup
2123 *
2124 * Description: Update priority of a turnstile inheritor
2125 * if needed.
2126 *
2127 * Args: inheritor and flags passed on thread struct.
2128 *
2129 * Returns: None.
2130 */
2131void
2132turnstile_cleanup(void)
2133{
2134 thread_t thread = current_thread();
2135
2136 /* Get the old inheritor from calling thread struct */
2137 turnstile_inheritor_t old_inheritor = thread->inheritor;
2138 turnstile_update_flags_t inheritor_flags = thread->inheritor_flags;
2139 thread->inheritor = THREAD_NULL;
2140 thread->inheritor_flags = TURNSTILE_UPDATE_FLAGS_NONE;
2141
2142 if (old_inheritor == TURNSTILE_INHERITOR_NULL) {
2143 /* no cleanup to do */
2144 return;
2145 }
2146
2147 /* Perform priority demotion for old inheritor */
2148 if (inheritor_flags & TURNSTILE_INHERITOR_NEEDS_PRI_UPDATE) {
2149 turnstile_update_inheritor_priority_chain(old_inheritor,
2150 inheritor_flags);
2151 }
2152
2153 /* Drop thread reference for old inheritor */
2154 if (inheritor_flags & TURNSTILE_INHERITOR_THREAD) {
2155 thread_deallocate_safe(old_inheritor);
2156 } else if (inheritor_flags & TURNSTILE_INHERITOR_TURNSTILE) {
2157 turnstile_deallocate_safe((struct turnstile *)old_inheritor);
2158 } else if (inheritor_flags & TURNSTILE_INHERITOR_WORKQ) {
2159 workq_deallocate_safe((struct workqueue *)old_inheritor);
2160 } else {
2161 panic("Inheritor flags lost along the way");
2162 }
2163}
2164
2165/*
2166 * Name: turnstile_update_inheritor_workq_priority_chain
2167 *
2168 * Description: Helper function to update turnstile's inheritor(workq)
2169 * priority and possibly redrive thread creation
2170 *
2171 * Arg1: turnstile: turnstile
2172 * Arg2: s: whether iterrupts are disabled.
2173 *
2174 * Condition: turnstile is locked on entry, it is unlocked on exit,
2175 * and interrupts re-enabled.
2176 */
2177static void
2178turnstile_update_inheritor_workq_priority_chain(struct turnstile *turnstile, spl_t s)
2179{
2180 struct workqueue *wq = turnstile->ts_inheritor;
2181 bool workq_lock_held = workq_is_current_thread_updating_turnstile(wq);
2182
2183 if (__improbable(turnstile->ts_priority <= MAXPRI_THROTTLE)) {
2184 waitq_unlock(&turnstile->ts_waitq);
2185 splx(s);
2186 return;
2187 }
2188
2189 if (!workq_lock_held) workq_reference(wq);
2190 waitq_unlock(&turnstile->ts_waitq);
2191 splx(s);
2192
2193 workq_schedule_creator_turnstile_redrive(wq, workq_lock_held);
2194
2195 if (!workq_lock_held) workq_deallocate_safe(wq);
2196}
2197
2198/*
2199 * Name: turnstile_update_inheritor_thread_priority_chain
2200 *
2201 * Description: Helper function to update turnstile's inheritor(thread)
2202 * priority.
2203 *
2204 * Arg1: in_turnstile: address to turnstile
2205 * Arg2: out_thread: address to return the thread inheritor
2206 * Arg3: thread_hop: number to thread hop in propagation chain
2207 * Arg4: tsu_flags: turnstile update flags
2208 *
2209 * Returns: Implicit returns locked thread in out_thread if it needs
2210 * further propagation.
2211 *
2212 * Condition: *in_turnstile is locked on entry, it is unlocked on exit and
2213 * *in_turnstile is set to NULL.
2214 */
2215static void
2216turnstile_update_inheritor_thread_priority_chain(
2217 struct turnstile **in_turnstile,
2218 thread_t *out_thread,
2219 int total_hop,
2220 turnstile_stats_update_flags_t tsu_flags)
2221{
2222 boolean_t needs_update = FALSE;
2223 struct turnstile *turnstile = *in_turnstile;
2224 thread_t thread_inheritor = turnstile->ts_inheritor;
2225 boolean_t first_update = !total_hop;
2226
2227 assert(turnstile->ts_inheritor_flags & TURNSTILE_INHERITOR_THREAD);
2228 *in_turnstile = TURNSTILE_NULL;
2229
2230 /* Check if update is needed before grabbing the thread lock */
2231 needs_update = thread_needs_turnstile_promotion_update(thread_inheritor, turnstile);
2232 if (!needs_update && !first_update) {
2233 turnstile_stats_update(total_hop + 1, TSU_NO_PRI_CHANGE_NEEDED |
2234 TSU_TURNSTILE_ARG | tsu_flags, turnstile);
2235 waitq_unlock(&turnstile->ts_waitq);
2236 return;
2237 }
2238
2239 thread_lock(thread_inheritor);
2240
2241 /* adjust turnstile position in the thread's inheritor list */
2242 needs_update = thread_update_turnstile_promotion_locked(
2243 thread_inheritor, turnstile);
2244
2245 /*
2246 * Check if thread needs further priority propagation,
2247 * since the first hop priority update was done in
2248 * turnstile_update_inheritor, do not bailout if it is
2249 * the first update as needs_update flag would evaluate to
2250 * false for that case.
2251 */
2252 if (!needs_update && !first_update) {
2253 /* Update turnstile stats before returning */
2254 turnstile_stats_update(total_hop + 1,
2255 (thread_get_update_flags_for_turnstile_propagation_stoppage(thread_inheritor)) |
2256 TSU_TURNSTILE_ARG | tsu_flags,
2257 turnstile);
2258 thread_unlock(thread_inheritor);
2259 waitq_unlock(&turnstile->ts_waitq);
2260 return;
2261 }
2262
2263 /* Unlock the turnstile and update the thread */
2264 waitq_unlock(&turnstile->ts_waitq);
2265 *out_thread = thread_inheritor;
2266 return;
2267}
2268
2269/*
2270 * Name: turnstile_update_inheritor_turnstile_priority_chain
2271 *
2272 * Description: Helper function to update turnstile's inheritor(turnstile)
2273 * priority.
2274 *
2275 * Arg1: in_out_turnstile: address to turnstile
2276 * Arg2: thread_hop: number of thread hop in propagation chain
2277 * Arg3: tsu_flags: turnstile update flags
2278 *
2279 * Returns: Implicit returns locked turnstile in in_out_turnstile if it needs
2280 * further propagation.
2281 *
2282 * Condition: *in_out_turnstile is locked on entry, *in_out_turnstile on exit,
2283 * but the value of *in_out_turnstile might change and turnstile lock
2284 * will be dropped for old value and will be acquired for the new value.
2285 */
2286static void
2287turnstile_update_inheritor_turnstile_priority_chain(
2288 struct turnstile **in_out_turnstile,
2289 int total_hop,
2290 turnstile_stats_update_flags_t tsu_flags)
2291{
2292 boolean_t needs_update = FALSE;
2293 struct turnstile *turnstile = *in_out_turnstile;
2294 struct turnstile *inheritor_turnstile = turnstile->ts_inheritor;
2295 boolean_t first_update = !total_hop;
2296
2297 assert(turnstile->ts_inheritor_flags & TURNSTILE_INHERITOR_TURNSTILE);
2298 *in_out_turnstile = TURNSTILE_NULL;
2299
2300 /* Check if the inheritor turnstile needs to be updated before grabbing the lock */
2301 needs_update = turnstile_need_turnstile_promotion_update(inheritor_turnstile, turnstile);
2302 if (!needs_update && !first_update) {
2303 turnstile_stats_update(total_hop + 1, TSU_NO_PRI_CHANGE_NEEDED |
2304 TSU_TURNSTILE_ARG | tsu_flags,
2305 turnstile);
2306 waitq_unlock(&turnstile->ts_waitq);
2307 return;
2308 }
2309
2310 waitq_lock(&inheritor_turnstile->ts_waitq);
2311
2312 needs_update = turnstile_update_turnstile_promotion_locked(
2313 inheritor_turnstile, turnstile);
2314
2315 /*
2316 * Check if turnstile needs further priority propagation,
2317 * since the first hop priority update was done in
2318 * turnstile_update_inheritor, do not bailout if it is
2319 * the first update as needs_update flag would evaluate to
2320 * false for that case.
2321 */
2322 if (!needs_update && !first_update) {
2323 /* Update turnstile stats before returning */
2324 turnstile_stats_update(total_hop + 1,
2325 (inheritor_turnstile->ts_inheritor ? TSU_NO_PRI_CHANGE_NEEDED : TSU_NO_INHERITOR) |
2326 TSU_TURNSTILE_ARG | tsu_flags,
2327 turnstile);
2328 waitq_unlock(&inheritor_turnstile->ts_waitq);
2329 waitq_unlock(&turnstile->ts_waitq);
2330 return;
2331 }
2332
2333 /* Unlock the outer turnstile and update the inner turnstile */
2334 waitq_unlock(&turnstile->ts_waitq);
2335 *in_out_turnstile = inheritor_turnstile;
2336 return;
2337}
2338
2339/*
2340 * Name: thread_update_waiting_turnstile_priority_chain
2341 *
2342 * Description: Helper function to update thread's waiting
2343 * turnstile priority.
2344 *
2345 * Arg1: in_thread: pointer to thread
2346 * Arg2: out_turnstile: pointer to turnstile to return to caller
2347 * Arg3: thread_hop: Number of thread hops visited
2348 * Arg4: total_hop: total hops visited
2349 * Arg5: tsu_flags: turnstile update flags
2350 *
2351 * Returns: *out_turnstile returns the inheritor if it needs further propagation.
2352 *
2353 * Condition: *in_thread locked on entry, unlocked on exit and set to NULL.
2354 */
2355static void
2356thread_update_waiting_turnstile_priority_chain(
2357 thread_t *in_thread,
2358 struct turnstile **out_turnstile,
2359 int thread_hop,
2360 int total_hop,
2361 turnstile_stats_update_flags_t tsu_flags)
2362{
2363 boolean_t needs_update = FALSE;
2364 thread_t thread = *in_thread;
2365 struct turnstile *waiting_turnstile = TURNSTILE_NULL;
2366 uint32_t turnstile_gencount;
2367 boolean_t first_update = !total_hop;
2368
2369 *in_thread = THREAD_NULL;
2370
2371 /* Check if thread waiting on a turnstile */
2372 waiting_turnstile = thread_get_waiting_turnstile(thread);
2373
2374 if (waiting_turnstile == TURNSTILE_NULL || thread_hop > turnstile_max_hop) {
2375 KERNEL_DEBUG_CONSTANT_IST(KDEBUG_TRACE,
2376 (TURNSTILE_CODE(TURNSTILE_HEAP_OPERATIONS,
2377 (waiting_turnstile ? TURNSTILE_UPDATE_STOPPED_BY_LIMIT : THREAD_NOT_WAITING_ON_TURNSTILE)
2378 )) | DBG_FUNC_NONE,
2379 thread_tid(thread),
2380 turnstile_max_hop,
2381 thread_hop,
2382 VM_KERNEL_UNSLIDE_OR_PERM(waiting_turnstile), 0);
2383 turnstile_stats_update(total_hop + 1, TSU_NO_TURNSTILE |
2384 TSU_THREAD_ARG | tsu_flags, thread);
2385 thread_unlock(thread);
2386 return;
2387 }
2388
2389 /* Check if the thread needs to update the waiting turnstile */
2390 needs_update = turnstile_need_thread_promotion_update(waiting_turnstile, thread);
2391 if (!needs_update && !first_update) {
2392 turnstile_stats_update(total_hop + 1, TSU_NO_PRI_CHANGE_NEEDED |
2393 TSU_THREAD_ARG | tsu_flags, thread);
2394 thread_unlock(thread);
2395 return;
2396 }
2397
2398 /* take a reference on thread, turnstile and snapshot of gencount */
2399 turnstile_gencount = turnstile_get_gencount(waiting_turnstile);
2400 turnstile_reference(waiting_turnstile);
2401 thread_reference(thread);
2402
2403 /* drop the thread lock and acquire the turnstile lock */
2404 thread_unlock(thread);
2405 waitq_lock(&waiting_turnstile->ts_waitq);
2406 thread_lock(thread);
2407
2408 /* Check if the gencount matches and thread is still waiting on same turnstile */
2409 if (turnstile_gencount != turnstile_get_gencount(waiting_turnstile) ||
2410 waiting_turnstile != thread_get_waiting_turnstile(thread)) {
2411 turnstile_stats_update(total_hop + 1, TSU_NO_PRI_CHANGE_NEEDED |
2412 TSU_THREAD_ARG | tsu_flags, thread);
2413 /* No updates required, bail out */
2414 thread_unlock(thread);
2415 waitq_unlock(&waiting_turnstile->ts_waitq);
2416 thread_deallocate_safe(thread);
2417 turnstile_deallocate_safe(waiting_turnstile);
2418 return;
2419 }
2420
2421 /*
2422 * The thread is waiting on the waiting_turnstile and we have thread lock,
2423 * we can drop the thread and turnstile reference since its on waitq and
2424 * it could not be removed from the waitq without the thread lock.
2425 */
2426 thread_deallocate_safe(thread);
2427 turnstile_deallocate_safe(waiting_turnstile);
2428
2429 /* adjust thread's position on turnstile waitq */
2430 needs_update = turnstile_update_thread_promotion_locked(waiting_turnstile, thread);
2431
2432 /*
2433 * Check if thread needs further priority propagation,
2434 * since the first hop priority update was done in
2435 * turnstile_update_inheritor, do not bailout if it is
2436 * the first update as needs_update flag would evaluate to
2437 * false for that case.
2438 */
2439 if (!needs_update && !first_update) {
2440 turnstile_stats_update(total_hop + 1,
2441 (waiting_turnstile->ts_inheritor ? TSU_NO_PRI_CHANGE_NEEDED : TSU_NO_INHERITOR) |
2442 TSU_THREAD_ARG | tsu_flags, thread);
2443 thread_unlock(thread);
2444 waitq_unlock(&waiting_turnstile->ts_waitq);
2445 return;
2446 }
2447
2448 /* drop the thread lock and update the turnstile */
2449 thread_unlock(thread);
2450 *out_turnstile = waiting_turnstile;
2451}
2452
2453/*
2454 * Name: turnstile_stats_update
2455 *
2456 * Description: Function to update turnstile stats for dev kernel.
2457 *
2458 * Arg1: hops : number of thread hops in priority propagation
2459 * Arg2: flags : turnstile stats update flags
2460 * Arg3: inheritor: inheritor
2461 *
2462 * Returns: Nothing
2463 */
2464void
2465turnstile_stats_update(
2466 int hop __assert_only,
2467 turnstile_stats_update_flags_t flags __assert_only,
2468 turnstile_inheritor_t inheritor __assert_only)
2469{
2470#if DEVELOPMENT || DEBUG
2471 if (flags & TSU_TURNSTILE_BLOCK_COUNT) {
2472 os_atomic_inc(&thread_block_on_turnstile_count, relaxed);
2473 }
2474
2475 if (flags & TSU_REGULAR_WAITQ_BLOCK_COUNT) {
2476 os_atomic_inc(&thread_block_on_regular_waitq_count, relaxed);
2477 }
2478
2479 if (hop > TURNSTILE_MAX_HOP_DEFAULT || hop == 0) {
2480 return;
2481 }
2482
2483 assert(hop >= 0);
2484
2485 /*
2486 * Check if turnstile stats needs to be updated.
2487 * Bail out if the turnstile or thread does not
2488 * have any user promotion, i.e. pri 4.
2489 * Bail out if it is the first hop of WQ turnstile
2490 * since WQ's use of a turnstile for the admission check
2491 * introduces a lot of noise due to state changes.
2492 */
2493 if (flags & TSU_TURNSTILE_ARG) {
2494 struct turnstile *ts = (struct turnstile *)inheritor;
2495 if (ts->ts_priority <= MAXPRI_THROTTLE) {
2496 return;
2497 }
2498
2499 if (hop == 1 && turnstile_get_type(ts) == TURNSTILE_WORKQS) {
2500 return;
2501 }
2502 } else if (flags & TSU_THREAD_ARG) {
2503 thread_t thread = (thread_t)inheritor;
2504 if (thread->user_promotion_basepri <= MAXPRI_THROTTLE) {
2505 return;
2506 }
2507 } else {
2508 assert(inheritor == NULL);
2509 }
2510
2511 struct turnstile_stats *turnstile_stats;
2512 if (flags & TSU_BOOST_ARG) {
2513 turnstile_stats = turnstile_boost_stats;
2514 } else {
2515 turnstile_stats = turnstile_unboost_stats;
2516 }
2517
2518 if (flags & TSU_PRI_PROPAGATION) {
2519 os_atomic_inc(&turnstile_stats[hop - 1].ts_priority_propagation, relaxed);
2520 }
2521
2522 if (flags & TSU_NO_INHERITOR) {
2523 os_atomic_inc(&turnstile_stats[hop - 1].ts_no_inheritor, relaxed);
2524 }
2525
2526 if (flags & TSU_NO_TURNSTILE) {
2527 os_atomic_inc(&turnstile_stats[hop - 1].ts_no_turnstile, relaxed);
2528 }
2529
2530 if (flags & TSU_NO_PRI_CHANGE_NEEDED) {
2531 os_atomic_inc(&turnstile_stats[hop - 1].ts_no_priority_change_required, relaxed);
2532 }
2533
2534 if (flags & TSU_THREAD_RUNNABLE) {
2535 os_atomic_inc(&turnstile_stats[hop - 1].ts_thread_runnable, relaxed);
2536 }
2537
2538 if (flags & TSU_ABOVE_UI_PRI_CHANGE) {
2539 os_atomic_inc(&turnstile_stats[hop - 1].ts_above_ui_pri_change, relaxed);
2540 }
2541#endif
2542}
2543
2544
2545#if DEVELOPMENT || DEBUG
2546
2547int sysctl_io_opaque(void *req,void *pValue, size_t valueSize, int *changed);
2548
2549/*
2550 * Name: turnstile_get_boost_stats_sysctl
2551 *
2552 * Description: Function to get turnstile stats.
2553 *
2554 * Args: req : opaque struct to pass to sysctl_io_opaque
2555 *
2556 * Returns: errorno
2557 */
2558int
2559turnstile_get_boost_stats_sysctl(
2560 void *req)
2561{
2562 return sysctl_io_opaque(req, turnstile_boost_stats, sizeof (struct turnstile_stats) * TURNSTILE_MAX_HOP_DEFAULT, NULL);
2563}
2564
2565/*
2566 * Name: get_turnstile_stats_sysctl
2567 *
2568 * Description: Function to get turnstile stats.
2569 *
2570 * Args: req : opaque struct to pass to sysctl_io_opaque
2571 *
2572 * Returns: errorno
2573 */
2574int
2575turnstile_get_unboost_stats_sysctl(
2576 void *req)
2577{
2578 return sysctl_io_opaque(req, turnstile_unboost_stats, sizeof (struct turnstile_stats) * TURNSTILE_MAX_HOP_DEFAULT, NULL);
2579}
2580
2581/* Testing interface for Development kernels */
2582#define tstile_test_prim_lock_interlock(test_prim) \
2583 lck_spin_lock(&test_prim->ttprim_interlock)
2584#define tstile_test_prim_unlock_interlock(test_prim) \
2585 lck_spin_unlock(&test_prim->ttprim_interlock)
2586
2587static void
2588tstile_test_prim_init(struct tstile_test_prim **test_prim_ptr)
2589{
2590 struct tstile_test_prim *test_prim = (struct tstile_test_prim *) kalloc(sizeof(struct tstile_test_prim));
2591
2592 test_prim->ttprim_turnstile = TURNSTILE_NULL;
2593 test_prim->ttprim_owner = NULL;
2594 lck_spin_init(&test_prim->ttprim_interlock, &turnstiles_dev_lock_grp, &turnstiles_dev_lock_attr);
2595 test_prim->tt_prim_waiters = 0;
2596
2597 *test_prim_ptr = test_prim;
2598 return;
2599}
2600
2601int
2602tstile_test_prim_lock(boolean_t use_hashtable)
2603{
2604 struct tstile_test_prim *test_prim = use_hashtable ? test_prim_global_htable : test_prim_ts_inline;
2605lock_start:
2606 /* take the interlock of the primitive */
2607 tstile_test_prim_lock_interlock(test_prim);
2608
2609 /* Check if the lock is available */
2610 if (test_prim->ttprim_owner == NULL && test_prim->tt_prim_waiters == 0) {
2611 thread_reference(current_thread());
2612 test_prim->ttprim_owner = current_thread();
2613 tstile_test_prim_unlock_interlock(test_prim);
2614 return 0;
2615 }
2616
2617 struct turnstile *prim_turnstile = TURNSTILE_NULL;
2618
2619 /* primitive locked, get a turnstile */
2620 prim_turnstile = turnstile_prepare((uintptr_t)test_prim,
2621 use_hashtable ? NULL : &test_prim->ttprim_turnstile,
2622 TURNSTILE_NULL, TURNSTILE_ULOCK);
2623
2624 assert(prim_turnstile != TURNSTILE_NULL);
2625
2626 /* This is contented acquire case */
2627 if (test_prim->ttprim_owner == NULL) {
2628 thread_reference(current_thread());
2629 test_prim->ttprim_owner = current_thread();
2630
2631 /* Update the turnstile owner */
2632 turnstile_update_inheritor(prim_turnstile,
2633 current_thread(),
2634 (TURNSTILE_IMMEDIATE_UPDATE | TURNSTILE_INHERITOR_THREAD));
2635
2636 turnstile_update_inheritor_complete(prim_turnstile, TURNSTILE_INTERLOCK_HELD);
2637
2638 turnstile_complete((uintptr_t)test_prim,
2639 use_hashtable ? NULL : &test_prim->ttprim_turnstile, NULL);
2640
2641 tstile_test_prim_unlock_interlock(test_prim);
2642
2643 turnstile_cleanup();
2644
2645 return 0;
2646 }
2647
2648 test_prim->tt_prim_waiters++;
2649 turnstile_update_inheritor(prim_turnstile,
2650 test_prim->ttprim_owner,
2651 (TURNSTILE_DELAYED_UPDATE | TURNSTILE_INHERITOR_THREAD));
2652
2653 waitq_assert_wait64(&prim_turnstile->ts_waitq,
2654 CAST_EVENT64_T(test_prim), THREAD_ABORTSAFE,
2655 TIMEOUT_WAIT_FOREVER);
2656
2657 /* drop the interlock */
2658 tstile_test_prim_unlock_interlock(test_prim);
2659
2660 turnstile_update_inheritor_complete(prim_turnstile, TURNSTILE_INTERLOCK_NOT_HELD);
2661
2662 wait_result_t result;
2663 result = thread_block(THREAD_CONTINUE_NULL);
2664
2665 /* re-acquire the interlock to get turnstile back */
2666 tstile_test_prim_lock_interlock(test_prim);
2667 test_prim->tt_prim_waiters--;
2668 turnstile_complete((uintptr_t)test_prim,
2669 use_hashtable ? NULL : &test_prim->ttprim_turnstile, NULL);
2670
2671 tstile_test_prim_unlock_interlock(test_prim);
2672
2673 turnstile_cleanup();
2674
2675 /* Return if thread interrupted */
2676 if (result == THREAD_INTERRUPTED) {
2677 return 1;
2678 }
2679
2680 goto lock_start;
2681}
2682
2683int
2684tstile_test_prim_unlock(boolean_t use_hashtable)
2685{
2686
2687 struct tstile_test_prim *test_prim = use_hashtable ? test_prim_global_htable : test_prim_ts_inline;
2688 /* take the interlock of the primitive */
2689 tstile_test_prim_lock_interlock(test_prim);
2690
2691 if (test_prim->ttprim_owner == NULL) {
2692 tstile_test_prim_unlock_interlock(test_prim);
2693 return 1;
2694 }
2695
2696 /* Check if the lock is contended */
2697 if (test_prim->ttprim_owner != NULL && test_prim->tt_prim_waiters == 0) {
2698 /* lock is not contended */
2699 thread_t old_owner = test_prim->ttprim_owner;
2700 test_prim->ttprim_owner = NULL;
2701 tstile_test_prim_unlock_interlock(test_prim);
2702
2703 thread_deallocate(old_owner);
2704 return 0;
2705 }
2706
2707 struct turnstile *prim_turnstile = TURNSTILE_NULL;
2708
2709 thread_t old_owner = test_prim->ttprim_owner;
2710 test_prim->ttprim_owner = NULL;
2711
2712 /* primitive locked, get a turnstile */
2713 prim_turnstile = turnstile_prepare((uintptr_t)test_prim,
2714 use_hashtable ? NULL : &test_prim->ttprim_turnstile,
2715 TURNSTILE_NULL, TURNSTILE_ULOCK);
2716
2717 assert(prim_turnstile != TURNSTILE_NULL);
2718
2719 /* Update the turnstile owner */
2720 turnstile_update_inheritor(prim_turnstile,
2721 NULL,
2722 (TURNSTILE_IMMEDIATE_UPDATE | TURNSTILE_INHERITOR_THREAD));
2723
2724 waitq_wakeup64_one(&prim_turnstile->ts_waitq,
2725 CAST_EVENT64_T(test_prim),
2726 THREAD_AWAKENED, WAITQ_SELECT_MAX_PRI);
2727
2728 turnstile_update_inheritor_complete(prim_turnstile, TURNSTILE_INTERLOCK_HELD);
2729
2730 turnstile_complete((uintptr_t)test_prim,
2731 use_hashtable ? NULL : &test_prim->ttprim_turnstile, NULL);
2732
2733 tstile_test_prim_unlock_interlock(test_prim);
2734
2735 turnstile_cleanup();
2736
2737 if (old_owner) {
2738 /* Changing this to thread_deallocate_safe to exercise thread_deallocate_safe path */
2739 thread_deallocate_safe(old_owner);
2740 }
2741
2742 return 0;
2743}
2744
2745#endif
2746