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#ifndef _TURNSTILE_H_
30#define _TURNSTILE_H_
31
32#include <mach/mach_types.h>
33#include <mach/kern_return.h>
34#include <sys/cdefs.h>
35
36#if PRIVATE
37#define TURNSTILE_MAX_HOP_DEFAULT (10)
38struct turnstile_stats {
39 uint64_t ts_priority_propagation;
40 uint64_t ts_no_inheritor;
41 uint64_t ts_thread_runnable;
42 uint64_t ts_no_priority_change_required;
43 uint64_t ts_above_ui_pri_change;
44 uint64_t ts_no_turnstile;
45};
46#endif
47
48#ifdef KERNEL_PRIVATE
49#include <kern/queue.h>
50#include <sys/queue.h>
51#include <kern/waitq.h>
52#include <kern/priority_queue.h>
53#include <os/refcnt.h>
54#include <kern/assert.h>
55#include <kern/kern_types.h>
56
57/*
58 * turnstile_type_t : Indicates the type of primitive the turnstile is associated with
59 * Please populate turnstile_promote_policy array if a new type is added here.
60 */
61typedef enum __attribute__((packed)) turnstile_type {
62 TURNSTILE_NONE = 0,
63 TURNSTILE_KERNEL_MUTEX = 1,
64 TURNSTILE_ULOCK = 2,
65 TURNSTILE_PTHREAD_MUTEX = 3,
66 TURNSTILE_SYNC_IPC = 4,
67 TURNSTILE_WORKLOOPS = 5,
68 TURNSTILE_WORKQS = 6,
69 TURNSTILE_KNOTE = 7,
70 TURNSTILE_TOTAL_TYPES = 8,
71} turnstile_type_t;
72
73/*
74 * For each type of turnstile, following are the type of
75 * inheritors passed:
76 *
77 * TURNSTILE_KERNEL_MUTEX
78 * Interlock: kernel mutex interlock.
79 * Inheritor: threads.
80 * Lock order: turnstile lock, thread lock.
81 *
82 * TURNSTILE_ULOCK
83 * Interlock: ulocks interlock.
84 * Inheritor: threads.
85 * Lock order: turnstile lock, thread lock.
86 *
87 * TURNSTILE_PTHREAD_MUTEX
88 * Interlock: pthread mtx interlock.
89 * Inheritor: threads.
90 * Lock order: turnstile lock, thread lock.
91 *
92 * TURNSTILE_SYNC_IPC
93 * Interlock: port's mqueue lock
94 * Inheritor: turnstile (of port in which we are enqueued or WL turnstile.
95 * Lock order: Our turnstile, then turnstile of the port we are enqueued in.
96 * Port circularity will make sure there is never a cycle formation
97 * and lock order is maintained.
98 *
99 * TURNSTILE_WORKLOOPS
100 * Interlock:
101 * - kq req lock
102 * - wq lock when "filt_wlworkq_interlock_needed() is true"
103 * Inheritor: thread, turnstile (of workq)
104 * Lock order: turnstile lock, thread lock
105 * WL turnstile lock, Workq turnstile lock
106 *
107 * TURNSTILE_WORKQS
108 * Interlock: workqueue lock
109 * Inheritor: thread
110 * Lock order: turnstile lock, thread lock.
111 *
112 * TURNSTILE_KNOTE
113 * Interlock: the knote lock
114 * Inheritor: WL turnstile
115 */
116
117typedef enum __attribute__((flag_enum)) turnstile_promote_policy {
118 TURNSTILE_PROMOTE_NONE = 0,
119 TURNSTILE_KERNEL_PROMOTE = 0x1,
120 TURNSTILE_USER_PROMOTE = 0x2,
121 TURNSTILE_USER_IPC_PROMOTE = 0x4,
122} turnstile_promote_policy_t;
123
124/*
125 * Turnstile state flags
126 *
127 * The turnstile state flags represent the current ownership of a turnstile.
128 * The supported flags are:
129 * - TURNSTILE_STATE_THREAD : Turnstile is attached to a thread
130 * - TURNSTILE_STATE_FREELIST : Turnstile is hanging off the freelist of another turnstile
131 * - TURNSTILE_STATE_HASHTABLE : Turnstile is in the global hash table as the turnstile for a primitive
132 * - TURNSTILE_STATE_PROPRIETOR : Turnstile is attached to a proprietor
133 *
134 * The flag updates are done while holding the primitive interlock.
135 * */
136
137#define TURNSTILE_STATE_THREAD 0x1
138#define TURNSTILE_STATE_FREELIST 0x2
139#define TURNSTILE_STATE_HASHTABLE 0x4
140#define TURNSTILE_STATE_PROPRIETOR 0x8
141
142/* Helper macros to set/unset turnstile state flags */
143#if DEVELOPMENT || DEBUG
144
145#define turnstile_state_init(ts, state) \
146MACRO_BEGIN \
147 ts->ts_state = state; \
148MACRO_END
149
150#define turnstile_state_add(ts, state) \
151MACRO_BEGIN \
152 assert((ts->ts_state & (state)) == 0); \
153 ts->ts_state |= state; \
154MACRO_END
155
156#define turnstile_state_remove(ts, state) \
157MACRO_BEGIN \
158 assert(ts->ts_state & (state)); \
159 ts->ts_state &= ~(state); \
160MACRO_END
161
162#else /* DEVELOPMENT || DEBUG */
163
164#define turnstile_state_init(ts, state) \
165MACRO_BEGIN \
166 (void)ts; \
167MACRO_END
168
169#define turnstile_state_add(ts, state) \
170MACRO_BEGIN \
171 (void)ts; \
172MACRO_END
173
174#define turnstile_state_remove(ts, state) \
175MACRO_BEGIN \
176 (void)ts; \
177MACRO_END
178
179#endif /* DEVELOPMENT || DEBUG */
180
181/* Foward declaration of turnstile */
182struct turnstile;
183
184/*
185 * Turnstile update flags
186 *
187 * TURNSTILE_IMMEDIATE_UPDATE
188 * When passed to turnstile_update_inheritor
189 * update the inheritor of the turnstile in
190 * the same call.
191 *
192 * TURNSTILE_DELAYED_UPDATE
193 * When passed to turnstile_update_inheritor
194 * it stashed the inheritor on the thread and
195 * turnstile's inheritor is updated in
196 * assert wait.
197 *
198 * TURNSTILE_INHERITOR_THREAD
199 * The turnstile inheritor is of type thread.
200 *
201 * TURNSTILE_INHERITOR_TURNSTILE
202 * The turnstile inheritor is of type turnstile.
203 *
204 * TURNSTILE_INHERITOR_WORKQ
205 * The turnstile inheritor is of type workqueue
206 *
207 * TURNSTILE_INHERITOR_NEEDS_PRI_UPDATE
208 * The inheritor needs a chain priority update.
209 *
210 * TURNSTILE_NEEDS_PRI_UPDATE
211 * Current turnstile needs a chain priority update.
212 *
213 * Locking order for passing thread and turnstile as inheritor
214 *
215 * Thread as an inheritor:
216 * When thread is passed as an inheritor of a turnstile
217 * turnstile lock is taken and then thread lock.
218 *
219 * Turnstile as in inheritor:
220 * When turnstile (T1) is passed as an inheritor of
221 * a turnstile (T2), turnstile lock of T2 is taken
222 * and then turnstile lock of T1 is taken.
223 *
224 * Caution: While passing turnstile as an inheritor, its
225 * job of the adopter to make sure that there is no
226 * lock inversion.
227 */
228typedef enum __attribute__((flag_enum)) __attribute__((packed)) turnstile_update_flags {
229 TURNSTILE_UPDATE_FLAGS_NONE = 0,
230 TURNSTILE_IMMEDIATE_UPDATE = 0x1,
231 TURNSTILE_DELAYED_UPDATE = 0x2,
232 TURNSTILE_INHERITOR_THREAD = 0x4,
233 TURNSTILE_INHERITOR_TURNSTILE = 0x8,
234 TURNSTILE_INHERITOR_NEEDS_PRI_UPDATE = 0x10,
235 TURNSTILE_NEEDS_PRI_UPDATE = 0x20,
236 TURNSTILE_INHERITOR_WORKQ = 0x40,
237 TURNSTILE_UPDATE_BOOST = 0x80,
238} turnstile_update_flags_t;
239
240#define TURNSTILE_NULL ((struct turnstile *)0)
241
242typedef void * turnstile_inheritor_t;
243
244#define TURNSTILE_INHERITOR_NULL NULL
245
246#ifdef XNU_KERNEL_PRIVATE
247
248/* Turnstile stats update flags
249 *
250 * TSU_TURNSTILE_BLOCK_COUNT
251 * thread blocking on turnstile waitq, increment global
252 * thread block on turnstile count.
253 *
254 * TSU_REGULAR_WAITQ_BLOCK_COUNT
255 * thread blocking on regular waitq, increment global
256 * thread block on regular waitq count.
257 *
258 * TSU_PRI_PROPAGATION
259 * turnstile propagation update stopped at nth hop, update
260 * priority change count for nth element in stats array.
261 *
262 * TSU_NO_INHERITOR
263 * turnstile propagation update stopped due to turnstile
264 * not having an inheritor after nth hop, update the no
265 * inheritor count for nth element in the stats array.
266 *
267 * TSU_NO_TURNSTILE
268 * turnstile propagation update stopped due to thread
269 * not blocked on a turnstile waitq after nth hop, update
270 * the no turnstile count for the nth element in the stats
271 * array.
272 *
273 * TSU_NO_PRI_CHANGE_NEEDED
274 * turnstile propagation update stopped due to thread or
275 * turnstile having the correct priority or not blocked.
276 * update the no priority change count for the nth element
277 * in the stats array.
278 *
279 * TSU_THREAD_RUNNABLE
280 * turnstile propagation update stopped due to thread
281 * being runnable, update the thread runnable count for
282 * the nth element in the stats array.
283 *
284 * TSU_ABOVE_UI_PRI_CHANGE
285 * turnstile propagation caused an above UI priority change.
286 */
287typedef enum __attribute__((flag_enum)) turnstile_stats_update_flags {
288 TSU_FLAGS_NONE = 0,
289 TSU_TURNSTILE_BLOCK_COUNT = 0x1,
290 TSU_REGULAR_WAITQ_BLOCK_COUNT = 0x2,
291 TSU_PRI_PROPAGATION = 0x4,
292 TSU_NO_INHERITOR = 0x8,
293 TSU_NO_TURNSTILE = 0x10,
294 TSU_NO_PRI_CHANGE_NEEDED = 0x20,
295 TSU_THREAD_RUNNABLE = 0x40,
296 TSU_ABOVE_UI_PRI_CHANGE = 0x80,
297 TSU_THREAD_ARG = 0x100,
298 TSU_TURNSTILE_ARG = 0x200,
299 TSU_BOOST_ARG = 0x400,
300} turnstile_stats_update_flags_t;
301
302SLIST_HEAD(turnstile_list, turnstile);
303
304struct turnstile {
305 struct waitq ts_waitq; /* waitq embedded in turnstile */
306 turnstile_inheritor_t ts_inheritor; /* thread/turnstile inheriting the priority (IL, WL) */
307 union {
308 struct turnstile_list ts_free_turnstiles; /* turnstile free list (IL) */
309 SLIST_ENTRY(turnstile) ts_free_elm; /* turnstile free list element (IL) */
310 };
311 struct priority_queue ts_inheritor_queue; /* Queue of turnstile with us as an inheritor (WL) */
312 union {
313 struct priority_queue_entry ts_inheritor_links; /* Inheritor queue links */
314 queue_chain_t ts_deallocate_link; /* thread deallocate link */
315 };
316 SLIST_ENTRY(turnstile) ts_htable_link; /* linkage for turnstile in global hash table */
317 uintptr_t ts_proprietor; /* hash key lookup turnstile (IL) */
318 os_refcnt_t ts_refcount; /* reference count for turnstiles */
319 _Atomic uint32_t ts_type_gencount; /* gen count used for priority chaining (IL), type of turnstile (IL) */
320 uint32_t ts_port_ref; /* number of explicit refs from ports on send turnstile */
321 turnstile_update_flags_t ts_inheritor_flags; /* flags for turnstile inheritor (IL, WL) */
322 uint8_t ts_priority; /* priority of turnstile (WL) */
323
324#if DEVELOPMENT || DEBUG
325 uint8_t ts_state; /* current state of turnstile (IL) */
326 queue_chain_t ts_global_elm; /* global turnstile chain */
327 thread_t ts_thread; /* thread the turnstile is attached to */
328 thread_t ts_prev_thread; /* thread the turnstile was attached before donation */
329#endif
330};
331
332#define waitq_to_turnstile(waitq) __container_of(waitq, struct turnstile, ts_waitq)
333
334/* IL - interlock, WL - turnstile lock i.e. waitq lock */
335
336#define TURNSTILE_PROPRIETOR_NULL 0
337
338/*
339 * Name: turnstiles_init
340 *
341 * Description: Initialize turnstile sub system.
342 *
343 * Args: None.
344 *
345 * Returns: None.
346 */
347void
348turnstiles_init(void);
349
350/*
351 * Name: turnstile_alloc
352 *
353 * Description: Allocate a turnstile.
354 *
355 * Args: None.
356 *
357 * Returns:
358 * turnstile on Success.
359 */
360struct turnstile *
361turnstile_alloc(void);
362
363/*
364 * Name: turnstile_destroy
365 *
366 * Description: Deallocates the turnstile.
367 *
368 * Args:
369 * Arg1: turnstile
370 *
371 * Returns: None.
372 */
373void
374turnstile_destroy(struct turnstile *turnstile);
375
376/*
377 * Name: turnstile_reference
378 *
379 * Description: Take a reference on the turnstile.
380 *
381 * Arg1: turnstile
382 *
383 * Returns: None.
384 */
385void
386turnstile_reference(struct turnstile *turnstile);
387
388/*
389 * Name: turnstile_deallocate
390 *
391 * Description: Drop a reference on the turnstile.
392 * Destroy the turnstile if the last ref.
393 *
394 * Arg1: turnstile
395 *
396 * Returns: None.
397 */
398void
399turnstile_deallocate(struct turnstile *turnstile);
400
401/*
402 * Name: turnstile_deallocate_safe
403 *
404 * Description: Drop a reference on the turnstile safely without triggering zfree.
405 *
406 * Arg1: turnstile
407 *
408 * Returns: None.
409 */
410void
411turnstile_deallocate_safe(struct turnstile *turnstile);
412
413/*
414 * Name: turnstile_recompute_priority_locked
415 *
416 * Description: Update turnstile priority based
417 * on highest waiter thread and highest blocking
418 * turnstile.
419 *
420 * Args: turnstile
421 *
422 * Returns: TRUE: if the turnstile priority changed and needs propagation.
423 * FALSE: if the turnstile priority did not change or it does not need propagation.
424 *
425 * Condition: turnstile locked
426 */
427boolean_t
428turnstile_recompute_priority_locked(
429 struct turnstile *turnstile);
430
431/*
432 * Name: turnstile_recompute_priority
433 *
434 * Description: Update turnstile priority based
435 * on highest waiter thread and highest blocking
436 * turnstile.
437 *
438 * Args: turnstile
439 *
440 * Returns: TRUE: if the turnstile priority changed and needs propagation.
441 * FALSE: if the turnstile priority did not change or it does not need propagation.
442 */
443boolean_t
444turnstile_recompute_priority(
445 struct turnstile *turnstile);
446
447/*
448 * Name: turnstile_workq_proprietor_of_max_turnstile
449 *
450 * Description: Returns the highest priority and proprietor of a turnstile
451 * pushing on a workqueue turnstile.
452 *
453 * This will not return waiters that are at priority
454 * MAXPRI_THROTTLE or lower.
455 *
456 * Args: turnstile
457 *
458 * Returns:
459 * Priority of the max entry, or 0
460 * Pointer to the max entry proprietor
461 */
462int
463turnstile_workq_proprietor_of_max_turnstile(
464 struct turnstile *turnstile,
465 uintptr_t *proprietor);
466
467/*
468 * Name: turnstile_cleanup
469 *
470 * Description: Update priority of a turnstile inheritor
471 * if needed.
472 *
473 * Args: inheritor and flags passed on thread struct.
474 *
475 * Returns: None.
476 */
477void
478turnstile_cleanup(void);
479
480/*
481 * Name: turnstile_update_inheritor_locked
482 *
483 * Description: Update the inheritor of the turnstile and boost the
484 * inheritor, called with turnstile locked.
485 *
486 * Args:
487 * Arg1: turnstile
488 * Implicit arg: new inheritor value is stashed in current thread's struct
489 *
490 * Returns:
491 * old inheritor reference is returned on current thread's struct.
492 */
493void
494turnstile_update_inheritor_locked(struct turnstile *turnstile);
495
496/*
497 * Name: thread_get_inheritor_turnstile_priority
498 *
499 * Description: Get the max priority of all the inheritor turnstiles
500 *
501 * Arg1: thread
502 *
503 * Returns: Max priority of all the inheritor turnstiles.
504 *
505 * Condition: thread locked
506 */
507int
508thread_get_inheritor_turnstile_priority(thread_t thread);
509
510/*
511 * Name: thread_get_waiting_turnstile
512 *
513 * Description: Get the turnstile if the thread is waiting on a turnstile.
514 *
515 * Arg1: thread
516 *
517 * Returns: turnstile: if the thread is blocked on a turnstile.
518 * TURNSTILE_NULL: otherwise.
519 *
520 * Condition: thread locked.
521 */
522struct turnstile *
523thread_get_waiting_turnstile(thread_t thread);
524
525/*
526 * Name: turnstile_lookup_by_proprietor
527 *
528 * Description: Get turnstile for a proprietor from global
529 * turnstile hash.
530 *
531 * Arg1: port
532 *
533 * Returns: turnstile: if the proprietor has a turnstile.
534 * TURNSTILE_NULL: otherwise.
535 *
536 * Condition: proprietor interlock held.
537 */
538struct turnstile *
539turnstile_lookup_by_proprietor(uintptr_t proprietor);
540
541/*
542 * Name: turnstile_stats_update
543 *
544 * Description: Function to update turnstile stats for dev kernel.
545 *
546 * Arg1: hops : number of thread hops in priority propagation
547 * Arg2: flags : turnstile stats update flags
548 * Arg3: inheritor: inheritor
549 *
550 * Returns: Nothing
551 */
552void
553turnstile_stats_update(
554 int hop __assert_only,
555 turnstile_stats_update_flags_t flags __assert_only,
556 turnstile_inheritor_t inheritor __assert_only);
557
558#if DEVELOPMENT || DEBUG
559
560/* Functions used by debug test primitive exported by sysctls */
561int
562tstile_test_prim_lock(boolean_t use_hashtable);
563
564int
565tstile_test_prim_unlock(boolean_t use_hashtable);
566
567int
568turnstile_get_boost_stats_sysctl(void *req);
569int
570turnstile_get_unboost_stats_sysctl(void *req);
571#endif /* DEVELOPMENT || DEBUG */
572#endif /* XNU_KERNEL_PRIVATE */
573
574/* Interface */
575
576/*
577 * Name: turnstile_prepare
578 *
579 * Description: Transfer current thread's turnstile to primitive or it's free turnstile list.
580 * Function is called holding the interlock (spinlock) of the primitive.
581 * The turnstile returned by this function is safe to use untill the thread calls turnstile_complete.
582 * When no turnstile is provided explicitly, the calling thread will not have a turnstile attached to
583 * it untill it calls turnstile_complete.
584 *
585 * Args:
586 * Arg1: proprietor
587 * Arg2: pointer in primitive struct to store turnstile
588 * Arg3: turnstile to use instead of taking it from thread.
589 * Arg4: type of primitive
590 *
591 * Returns:
592 * turnstile.
593 */
594struct turnstile *
595turnstile_prepare(
596 uintptr_t proprietor,
597 struct turnstile **tstore,
598 struct turnstile *turnstile,
599 turnstile_type_t type);
600
601/*
602 * Name: turnstile_complete
603 *
604 * Description: Transfer the primitive's turnstile or from it's freelist to current thread.
605 * Function is called holding the interlock (spinlock) of the primitive.
606 * Current thread will have a turnstile attached to it after this call.
607 *
608 * Args:
609 * Arg1: proprietor
610 * Arg2: pointer in primitive struct to update turnstile
611 * Arg3: pointer to store the returned turnstile instead of attaching it to thread
612 *
613 * Returns:
614 * None.
615 */
616void
617turnstile_complete(
618 uintptr_t proprietor,
619 struct turnstile **tstore,
620 struct turnstile **turnstile);
621
622/*
623 * Name: turnstile_update_inheritor
624 *
625 * Description: Update the inheritor of the turnstile and boost the
626 * inheritor. It will take a thread reference on the inheritor.
627 * Called with the interlock of the primitive held.
628 *
629 * Args:
630 * Arg1: turnstile
631 * Arg2: inheritor
632 * Arg3: flags - TURNSTILE_DELAYED_UPDATE - update will happen later in assert_wait
633 *
634 * Returns:
635 * old inheritor reference is stashed on current thread's struct.
636 */
637void
638turnstile_update_inheritor(
639 struct turnstile *turnstile,
640 turnstile_inheritor_t new_inheritor,
641 turnstile_update_flags_t flags);
642
643typedef enum turnstile_update_complete_flags {
644 TURNSTILE_INTERLOCK_NOT_HELD = 0x1,
645 TURNSTILE_INTERLOCK_HELD = 0x2,
646} turnstile_update_complete_flags_t;
647
648/*
649 * Name: turnstile_update_inheritor_complete
650 *
651 * Description: Update turnstile inheritor's priority and propagate the
652 * priority if the inheritor is blocked on a turnstile.
653 * Consumes thread ref of old inheritor returned by
654 * turnstile_update_inheritor. Recursive priority update
655 * will only happen when called with interlock dropped.
656 *
657 * Args:
658 * Arg1: turnstile
659 * Arg2: interlock held
660 *
661 * Returns: None.
662 */
663void
664turnstile_update_inheritor_complete(
665 struct turnstile *turnstile,
666 turnstile_update_complete_flags_t flags);
667
668#endif /* KERNEL_PRIVATE */
669#if XNU_KERNEL_PRIVATE
670
671struct workqueue;
672
673/* pthread_workqueue.c */
674extern void workq_reference(struct workqueue *wq);
675extern void workq_deallocate_safe(struct workqueue *wq);
676extern void workq_destroy(struct workqueue *wq);
677extern bool workq_is_current_thread_updating_turnstile(struct workqueue *wq);
678extern void workq_schedule_creator_turnstile_redrive(struct workqueue *wq,
679 bool locked);
680
681/* thread.c */
682extern void workq_deallocate_enqueue(struct workqueue *wq);
683
684#endif /* XNU_KERNEL_PRIVATE */
685
686#endif /* _TURNSTILE_H_ */
687