1 #ifndef _WAITQ_H_ 2 #define _WAITQ_H_ 3 /* 4 * Copyright (c) 2014-2015 Apple Computer, Inc. All rights reserved. 5 * 6 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@ 7 * 8 * This file contains Original Code and/or Modifications of Original Code 9 * as defined in and that are subject to the Apple Public Source License 10 * Version 2.0 (the 'License'). You may not use this file except in 11 * compliance with the License. The rights granted to you under the License 12 * may not be used to create, or enable the creation or redistribution of, 13 * unlawful or unlicensed copies of an Apple operating system, or to 14 * circumvent, violate, or enable the circumvention or violation of, any 15 * terms of an Apple operating system software license agreement. 16 * 17 * Please obtain a copy of the License at 18 * http://www.opensource.apple.com/apsl/ and read it before using this file. 19 * 20 * The Original Code and all software distributed under the License are 21 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER 22 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, 23 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, 24 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. 25 * Please see the License for the specific language governing rights and 26 * limitations under the License. 27 * 28 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@ 29 */ 30 #ifdef KERNEL_PRIVATE 31 32 #include <mach/mach_types.h> 33 #include <mach/sync_policy.h> 34 #include <mach/kern_return.h> /* for kern_return_t */ 35 36 #include <kern/kern_types.h> /* for wait_queue_t */ 37 #include <kern/queue.h> 38 #include <kern/assert.h> 39 40 #include <sys/cdefs.h> 41 42 #ifdef XNU_KERNEL_PRIVATE 43 /* priority queue static asserts fail for __ARM64_ARCH_8_32__ kext builds */ 44 #include <kern/priority_queue.h> 45 #endif /* XNU_KERNEL_PRIVATE */ 46 #ifdef MACH_KERNEL_PRIVATE 47 #include <kern/spl.h> 48 #include <kern/ticket_lock.h> 49 50 #include <machine/cpu_number.h> 51 #include <machine/machine_routines.h> /* machine_timeout_suspended() */ 52 #endif /* MACH_KERNEL_PRIVATE */ 53 54 __BEGIN_DECLS 55 56 #pragma GCC visibility push(hidden) 57 58 /* 59 * Constants and types used in the waitq APIs 60 */ 61 #define WAITQ_ALL_PRIORITIES (-1) 62 #define WAITQ_PROMOTE_PRIORITY (-2) 63 #define WAITQ_PROMOTE_ON_WAKE (-3) 64 65 typedef enum e_waitq_lock_state { 66 WAITQ_KEEP_LOCKED = 0x01, 67 WAITQ_UNLOCK = 0x02, 68 WAITQ_SHOULD_LOCK = 0x04, 69 WAITQ_ALREADY_LOCKED = 0x08, 70 WAITQ_DONT_LOCK = 0x10, 71 } waitq_lock_state_t; 72 73 /* Opaque sizes and alignment used for struct verification */ 74 #if __arm__ || __arm64__ 75 #define WQ_OPAQUE_ALIGN __BIGGEST_ALIGNMENT__ 76 #define WQS_OPAQUE_ALIGN __BIGGEST_ALIGNMENT__ 77 #if __arm__ 78 #define WQ_OPAQUE_SIZE 32 79 #define WQS_OPAQUE_SIZE 48 80 #else 81 #define WQ_OPAQUE_SIZE 40 82 #define WQS_OPAQUE_SIZE 56 83 #endif 84 #elif __x86_64__ 85 #define WQ_OPAQUE_ALIGN 8 86 #define WQS_OPAQUE_ALIGN 8 87 #define WQ_OPAQUE_SIZE 48 88 #define WQS_OPAQUE_SIZE 64 89 #else 90 #error Unknown size requirement 91 #endif 92 93 typedef struct { 94 uint64_t wqr_value __kernel_ptr_semantics; 95 } waitq_ref_t; 96 97 #define WAITQ_REF_NULL ((waitq_ref_t){ 0 }) 98 99 #ifdef MACH_KERNEL_PRIVATE 100 101 enum waitq_type { 102 WQT_INVALID = 0, 103 WQT_TSPROXY = 0x1, 104 WQT_QUEUE = 0x2, 105 WQT_SET = 0x3, 106 }; 107 108 __options_decl(waitq_options_t, uint32_t, { 109 WQ_OPTION_NONE = 0, 110 WQ_OPTION_HANDOFF = 1, 111 }); 112 113 #if CONFIG_WAITQ_STATS 114 #define NWAITQ_BTFRAMES 5 115 struct wq_stats { 116 uint64_t waits; 117 uint64_t wakeups; 118 uint64_t clears; 119 uint64_t failed_wakeups; 120 121 uintptr_t last_wait[NWAITQ_BTFRAMES]; 122 uintptr_t last_wakeup[NWAITQ_BTFRAMES]; 123 uintptr_t last_failed_wakeup[NWAITQ_BTFRAMES]; 124 }; 125 #endif 126 127 /* 128 * The waitq needs WAITQ_FLAGS_BITS, which leaves 25 or 57 bits 129 * for the eventmask. 130 */ 131 #define WAITQ_FLAGS_BITS 6 132 #define _EVENT_MASK_BITS (8 * sizeof(waitq_flags_t) - WAITQ_FLAGS_BITS) 133 134 #if __arm64__ 135 typedef uint32_t waitq_flags_t; 136 #else 137 typedef unsigned long waitq_flags_t; 138 #endif 139 140 /* Make sure the port abuse of bits doesn't overflow the evntmask size */ 141 #define WAITQ_FLAGS_OVERFLOWS(...) \ 142 (sizeof(struct { waitq_flags_t bits : WAITQ_FLAGS_BITS, __VA_ARGS__; }) \ 143 > sizeof(waitq_flags_t)) 144 145 #define WAITQ_FLAGS(prefix, ...) \ 146 struct { \ 147 waitq_flags_t /* flags */ \ 148 prefix##_type:2, /* only public field */ \ 149 prefix##_fifo:1, /* fifo wakeup policy? */ \ 150 prefix##_irq:1, /* waitq requires interrupts disabled */ \ 151 prefix##_turnstile:1, /* waitq is embedded in a turnstile */ \ 152 prefix##_portset:1 /* waitq is embedded in port-set */ \ 153 - 2 * WAITQ_FLAGS_OVERFLOWS(__VA_ARGS__), \ 154 __VA_ARGS__; \ 155 } 156 157 /* 158 * struct waitq 159 * 160 * This is the definition of the common event wait queue 161 * that the scheduler APIs understand. It is used 162 * internally by the gerneralized event waiting mechanism 163 * (assert_wait), and also for items that maintain their 164 * own wait queues (such as ports and semaphores). 165 * 166 * It is not published to other kernel components. 167 * 168 * NOTE: Hardware locks are used to protect event wait 169 * queues since interrupt code is free to post events to 170 * them. 171 */ 172 struct waitq { 173 /* waitq_eventmask: the wait queue set (set-of-sets) to which this queue belongs */ 174 WAITQ_FLAGS(waitq, waitq_eventmask:_EVENT_MASK_BITS); 175 hw_lck_ticket_t waitq_interlock; 176 uint8_t waitq_padding[sizeof(waitq_flags_t) - sizeof(hw_lck_ticket_t)]; 177 waitq_ref_t waitq_set_id; 178 uint64_t waitq_prepost_id; 179 union { 180 /* queue of elements - used for waitq not embedded in turnstile or ports */ 181 queue_head_t waitq_queue; 182 183 /* priority ordered queue of elements - used for waitqs embedded in turnstiles */ 184 struct priority_queue_sched_max waitq_prio_queue; 185 186 /* 187 * used for waitqs embedded in ports 188 * 189 * waitq_ts: used to store receive turnstile of the port 190 * 191 * waitq_tspriv: non special-reply port, used to store the 192 * watchport element for port used to store 193 * receive turnstile of the port 194 * 195 * waitq_priv_pid: special-reply port, used to store the pid 196 * that copies out the send once right of the 197 * special-reply port. 198 */ 199 struct { 200 struct turnstile *waitq_ts; 201 union { 202 void *waitq_tspriv; 203 int waitq_priv_pid; 204 }; 205 }; 206 }; 207 }; 208 209 static_assert(sizeof(struct waitq) == WQ_OPAQUE_SIZE, "waitq structure size mismatch"); 210 static_assert(__alignof(struct waitq) == WQ_OPAQUE_ALIGN, "waitq structure alignment mismatch"); 211 212 /* 213 * struct waitq_set 214 * 215 * This is the common definition for a set wait queue. 216 */ 217 struct waitq_set { 218 struct waitq wqset_q; 219 uint64_t wqset_id; 220 uint64_t wqset_prepost_id; 221 }; 222 223 #define WQSET_PREPOSTED_ANON ((uint64_t)(~0)) 224 #define WQSET_NOT_LINKED ((uint64_t)(~0)) 225 static_assert(sizeof(struct waitq_set) == WQS_OPAQUE_SIZE, "waitq_set structure size mismatch"); 226 static_assert(__alignof(struct waitq_set) == WQS_OPAQUE_ALIGN, "waitq_set structure alignment mismatch"); 227 228 extern void waitq_bootstrap(void); 229 230 #define waitq_is_queue(wq) \ 231 ((wq)->waitq_type == WQT_QUEUE) 232 233 #define waitq_is_turnstile_proxy(wq) \ 234 ((wq)->waitq_type == WQT_TSPROXY) 235 236 #define waitq_is_turnstile_queue(wq) \ 237 (((wq)->waitq_irq) && (wq)->waitq_turnstile) 238 239 #define waitq_is_set(wq) \ 240 ((wq)->waitq_type == WQT_SET && ((struct waitq_set *)(wq))->wqset_id != 0) 241 242 #define waitqs_is_set(wqs) \ 243 (((wqs)->wqset_q.waitq_type == WQT_SET) && ((wqs)->wqset_id != 0)) 244 245 #define waitq_valid(wq) \ 246 ((wq) != NULL && (wq)->waitq_interlock.lck_valid) 247 248 #define waitqs_is_linked(wqs) \ 249 (((wqs)->wqset_id != WQSET_NOT_LINKED) && ((wqs)->wqset_id != 0)) 250 251 /* in ipc_pset.c */ 252 extern void ipc_pset_prepost(struct waitq_set *wqset, struct waitq *waitq); 253 254 extern lck_grp_t waitq_lck_grp; 255 256 #define waitq_held(wq) \ 257 hw_lck_ticket_held(&(wq)->waitq_interlock) 258 259 #define waitq_lock_try(wq) \ 260 hw_lck_ticket_lock_try(&(wq)->waitq_interlock, &waitq_lck_grp) 261 262 #define waitq_wait_possible(thread) \ 263 ((thread)->waitq == NULL) 264 265 extern bool waitq_lock_allow_invalid(struct waitq *wq) __result_use_check; 266 267 #define waitq_set_lock(wqs) waitq_lock(&(wqs)->wqset_q) 268 #define waitq_set_unlock(wqs) waitq_unlock(&(wqs)->wqset_q) 269 #define waitq_set_lock_try(wqs) waitq_lock_try(&(wqs)->wqset_q) 270 271 /* assert intent to wait on a locked wait queue */ 272 extern wait_result_t waitq_assert_wait64_locked(struct waitq *waitq, 273 event64_t wait_event, 274 wait_interrupt_t interruptible, 275 wait_timeout_urgency_t urgency, 276 uint64_t deadline, 277 uint64_t leeway, 278 thread_t thread); 279 280 /* pull a thread from its wait queue */ 281 extern bool waitq_pull_thread_locked(struct waitq *waitq, thread_t thread); 282 283 /* wakeup all threads waiting for a particular event on locked queue */ 284 extern kern_return_t waitq_wakeup64_all_locked(struct waitq *waitq, 285 event64_t wake_event, 286 wait_result_t result, 287 uint64_t *reserved_preposts, 288 int priority, 289 waitq_lock_state_t lock_state); 290 291 /* wakeup one thread waiting for a particular event on locked queue */ 292 extern kern_return_t waitq_wakeup64_one_locked(struct waitq *waitq, 293 event64_t wake_event, 294 wait_result_t result, 295 uint64_t *reserved_preposts, 296 int priority, 297 waitq_lock_state_t lock_state, 298 waitq_options_t options); 299 300 /* return identity of a thread awakened for a particular <wait_queue,event> */ 301 extern thread_t waitq_wakeup64_identify_locked(struct waitq *waitq, 302 event64_t wake_event, 303 wait_result_t result, 304 spl_t *spl, 305 uint64_t *reserved_preposts, 306 int priority, 307 waitq_lock_state_t lock_state); 308 309 /* wakeup thread iff its still waiting for a particular event on locked queue */ 310 extern kern_return_t waitq_wakeup64_thread_locked(struct waitq *waitq, 311 event64_t wake_event, 312 thread_t thread, 313 wait_result_t result, 314 waitq_lock_state_t lock_state); 315 316 /* clear all preposts generated by the given waitq */ 317 extern int waitq_clear_prepost_locked(struct waitq *waitq); 318 319 /* unlink the given waitq from all sets - returns unlocked */ 320 extern void waitq_unlink_all_unlock(struct waitq *waitq); 321 322 /* unlink the given waitq set from all waitqs and waitq sets - returns unlocked */ 323 extern kern_return_t waitq_set_unlink_all_unlock(struct waitq_set *wqset); 324 325 /* unlink the given waitq from all sets and add it to give set - returns unlocked */ 326 extern void waitq_unlink_all_relink_unlock( 327 struct waitq *waitq, 328 struct waitq_set *wqset); 329 330 /* 331 * clear a thread's boosted priority 332 * (given via WAITQ_PROMOTE_PRIORITY in the wakeup function) 333 */ 334 extern void waitq_clear_promotion_locked(struct waitq *waitq, 335 thread_t thread); 336 337 /* 338 * waitq iteration 339 */ 340 341 enum waitq_iteration_constant { 342 WQ_ITERATE_DROPPED = -4, 343 WQ_ITERATE_INVALID = -3, 344 WQ_ITERATE_ABORTED = -2, 345 WQ_ITERATE_FAILURE = -1, 346 WQ_ITERATE_SUCCESS = 0, 347 WQ_ITERATE_CONTINUE = 1, 348 WQ_ITERATE_BREAK = 2, 349 WQ_ITERATE_BREAK_KEEP_LOCKED = 3, 350 WQ_ITERATE_INVALIDATE_CONTINUE = 4, 351 WQ_ITERATE_RESTART = 5, 352 WQ_ITERATE_FOUND = 6, 353 WQ_ITERATE_UNLINKED = 7, 354 }; 355 356 /* iterator over all waitqs that have preposted to wqset */ 357 typedef enum waitq_iteration_constant (^ waitq_iterator_t)(struct waitq *); 358 extern int waitq_set_iterate_preposts(struct waitq_set *wqset, waitq_iterator_t it); 359 360 /* 361 * prepost reservation 362 */ 363 extern uint64_t waitq_prepost_reserve(struct waitq *waitq, int extra, 364 waitq_lock_state_t lock_state); 365 366 extern void waitq_prepost_release_reserve(uint64_t id); 367 368 #else /* !MACH_KERNEL_PRIVATE */ 369 370 /* 371 * The opaque waitq structure is here mostly for AIO and selinfo, 372 * but could potentially be used by other BSD subsystems. 373 */ 374 struct waitq { char opaque[WQ_OPAQUE_SIZE]; } __attribute__((aligned(WQ_OPAQUE_ALIGN))); 375 struct waitq_set { char opaque[WQS_OPAQUE_SIZE]; } __attribute__((aligned(WQS_OPAQUE_ALIGN))); 376 377 #endif /* MACH_KERNEL_PRIVATE */ 378 379 /* 380 * waitq init 381 */ 382 extern void waitq_init(struct waitq *waitq, int policy); 383 extern void waitq_deinit(struct waitq *waitq); 384 385 /* 386 * Invalidate a waitq. 387 */ 388 extern void waitq_invalidate(struct waitq *wq); 389 390 /* 391 * global waitqs 392 */ 393 extern struct waitq *_global_eventq(char *event, size_t event_length); 394 #define global_eventq(event) _global_eventq((char *)&(event), sizeof(event)) 395 396 extern struct waitq *global_waitq(int index); 397 398 /* 399 * set init/deinit 400 */ 401 extern void waitq_set_init(struct waitq_set *wqset, int policy); 402 403 extern void waitq_set_reset_anon_prepost(struct waitq_set *wqset); 404 405 extern void waitq_set_deinit(struct waitq_set *wqset); 406 407 extern void waitq_set_deinit_and_unlock(struct waitq_set *wqset); 408 409 #if DEVELOPMENT || DEBUG 410 extern int sysctl_helper_waitq_set_nelem(void); 411 #endif /* DEVELOPMENT || DEBUG */ 412 413 /* 414 * set membership 415 */ 416 extern waitq_ref_t waitq_link_reserve(void); 417 extern void waitq_set_lazy_init_link(struct waitq_set *wqset); 418 419 extern void waitq_link_release(waitq_ref_t ref); 420 421 extern bool waitq_member_locked(struct waitq *waitq, struct waitq_set *wqset); 422 423 /* on success, consumes an reserved_link reference */ 424 extern kern_return_t waitq_link(struct waitq *waitq, 425 struct waitq_set *wqset, 426 waitq_lock_state_t lock_state, 427 waitq_ref_t *reserved_link); 428 429 extern kern_return_t waitq_unlink(struct waitq *waitq, struct waitq_set *wqset); 430 431 extern kern_return_t waitq_unlink_locked(struct waitq *waitq, struct waitq_set *wqset); 432 433 /* 434 * interfaces used primarily by the select/kqueue subsystems 435 */ 436 extern uint64_t waitq_get_prepost_id(struct waitq *waitq); 437 extern void waitq_unlink_by_prepost_id(uint64_t wqp_id, struct waitq_set *wqset); 438 extern struct waitq *waitq_lock_by_prepost_id(uint64_t wqp_id); 439 440 /* 441 * waitq attributes 442 */ 443 extern bool waitq_is_valid(struct waitq *waitq); 444 445 extern bool waitq_set_is_valid(struct waitq_set *wqset); 446 447 extern bool waitq_is_global(struct waitq *waitq); 448 449 extern bool waitq_irq_safe(struct waitq *waitq); 450 451 #if CONFIG_WAITQ_STATS 452 /* 453 * waitq statistics 454 */ 455 #define WAITQ_STATS_VERSION 1 456 struct wq_table_stats { 457 uint32_t version; 458 uint32_t table_elements; 459 uint32_t table_used_elems; 460 uint32_t table_elem_sz; 461 uint32_t table_slabs; 462 uint32_t table_slab_sz; 463 464 uint64_t table_num_allocs; 465 uint64_t table_num_preposts; 466 uint64_t table_num_reservations; 467 468 uint64_t table_max_used; 469 uint64_t table_avg_used; 470 uint64_t table_max_reservations; 471 uint64_t table_avg_reservations; 472 }; 473 474 extern void waitq_link_stats(struct wq_table_stats *stats); 475 extern void waitq_prepost_stats(struct wq_table_stats *stats); 476 #endif /* CONFIG_WAITQ_STATS */ 477 478 /* 479 * 480 * higher-level waiting APIs 481 * 482 */ 483 484 /* assert intent to wait on <waitq,event64> pair */ 485 extern wait_result_t waitq_assert_wait64(struct waitq *waitq, 486 event64_t wait_event, 487 wait_interrupt_t interruptible, 488 uint64_t deadline); 489 490 extern wait_result_t waitq_assert_wait64_leeway(struct waitq *waitq, 491 event64_t wait_event, 492 wait_interrupt_t interruptible, 493 wait_timeout_urgency_t urgency, 494 uint64_t deadline, 495 uint64_t leeway); 496 497 /* wakeup the most appropriate thread waiting on <waitq,event64> pair */ 498 extern kern_return_t waitq_wakeup64_one(struct waitq *waitq, 499 event64_t wake_event, 500 wait_result_t result, 501 int priority); 502 503 /* wakeup all the threads waiting on <waitq,event64> pair */ 504 extern kern_return_t waitq_wakeup64_all(struct waitq *waitq, 505 event64_t wake_event, 506 wait_result_t result, 507 int priority); 508 509 #ifdef XNU_KERNEL_PRIVATE 510 511 /* wakeup a specified thread iff it's waiting on <waitq,event64> pair */ 512 extern kern_return_t waitq_wakeup64_thread(struct waitq *waitq, 513 event64_t wake_event, 514 thread_t thread, 515 wait_result_t result); 516 517 /* return a reference to the thread that was woken up */ 518 extern thread_t waitq_wakeup64_identify(struct waitq *waitq, 519 event64_t wake_event, 520 wait_result_t result, 521 int priority); 522 523 extern void waitq_lock(struct waitq *wq); 524 525 extern void waitq_unlock(struct waitq *wq); 526 527 #endif /* XNU_KERNEL_PRIVATE */ 528 529 #pragma GCC visibility pop 530 531 __END_DECLS 532 533 #endif /* KERNEL_PRIVATE */ 534 #endif /* _WAITQ_H_ */ 535