osfmk/kern/waitq.h

   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
  47 /*
  48  * Constants and types used in the waitq APIs
  49  */
  50 #define WAITQ_ALL_PRIORITIES   (-1)
  51 #define WAITQ_PROMOTE_PRIORITY (-2)
  52 #define WAITQ_PROMOTE_ON_WAKE  (-3)
  53
  54 typedef enum e_waitq_lock_state {
  55         WAITQ_KEEP_LOCKED    = 0x01,
  56         WAITQ_UNLOCK         = 0x02,
  57         WAITQ_SHOULD_LOCK    = 0x04,
  58         WAITQ_ALREADY_LOCKED = 0x08,
  59         WAITQ_DONT_LOCK      = 0x10,
  60 } waitq_lock_state_t;
  61
  62 /* Opaque sizes and alignment used for struct verification */
  63 #if __arm__ || __arm64__
  64         #define WQ_OPAQUE_ALIGN   __BIGGEST_ALIGNMENT__
  65         #define WQS_OPAQUE_ALIGN  __BIGGEST_ALIGNMENT__
  66         #if __arm__
  67                 #define WQ_OPAQUE_SIZE   32
  68                 #define WQS_OPAQUE_SIZE  48
  69         #else
  70                 #define WQ_OPAQUE_SIZE   40
  71                 #define WQS_OPAQUE_SIZE  56
  72         #endif
  73 #elif __x86_64__
  74         #define WQ_OPAQUE_ALIGN   8
  75         #define WQS_OPAQUE_ALIGN  8
  76         #define WQ_OPAQUE_SIZE   48
  77         #define WQS_OPAQUE_SIZE  64
  78 #else
  79         #error Unknown size requirement
  80 #endif
  81
  82 #ifdef MACH_KERNEL_PRIVATE
  83
  84 #include <kern/spl.h>
  85 #include <kern/simple_lock.h>
  86
  87 #include <machine/cpu_number.h>
  88 #include <machine/machine_routines.h> /* machine_timeout_suspended() */
  89
  90 /*
  91  * The event mask is of 57 bits on 64 bit architeture and 25 bits on
  92  * 32 bit architecture and so we calculate its size using sizeof(long).
  93  * If the bitfield for wq_type and wq_fifo is changed, then value of
  94  * EVENT_MASK_BITS will also change.
  95  *
  96  * New plan: this is an optimization anyway, so I'm stealing 32bits
  97  * from the mask to shrink the waitq object even further.
  98  */
  99 #define _EVENT_MASK_BITS   ((sizeof(uint32_t) * 8) - 7)
 100
 101
 102 enum waitq_type {
 103         WQT_INVALID = 0,
 104         WQT_QUEUE   = 0x2,
 105         WQT_SET     = 0x3,
 106 };
 107
 108 #if CONFIG_WAITQ_STATS
 109 #define NWAITQ_BTFRAMES 5
 110 struct wq_stats {
 111         uint64_t waits;
 112         uint64_t wakeups;
 113         uint64_t clears;
 114         uint64_t failed_wakeups;
 115
 116         uintptr_t last_wait[NWAITQ_BTFRAMES];
 117         uintptr_t last_wakeup[NWAITQ_BTFRAMES];
 118         uintptr_t last_failed_wakeup[NWAITQ_BTFRAMES];
 119 };
 120 #endif
 121
 122 /*
 123  *      struct waitq
 124  *
 125  *      This is the definition of the common event wait queue
 126  *      that the scheduler APIs understand.  It is used
 127  *      internally by the gerneralized event waiting mechanism
 128  *      (assert_wait), and also for items that maintain their
 129  *      own wait queues (such as ports and semaphores).
 130  *
 131  *      It is not published to other kernel components.
 132  *
 133  *      NOTE:  Hardware locks are used to protect event wait
 134  *      queues since interrupt code is free to post events to
 135  *      them.
 136  */
 137 struct waitq {
 138         uint32_t /* flags */
 139             waitq_type:2,        /* only public field */
 140             waitq_fifo:1,        /* fifo wakeup policy? */
 141             waitq_prepost:1,     /* waitq supports prepost? */
 142             waitq_irq:1,         /* waitq requires interrupts disabled */
 143             waitq_isvalid:1,     /* waitq structure is valid */
 144             waitq_turnstile_or_port:1,     /* waitq is embedded in a turnstile (if irq safe), or port (if not irq safe) */
 145             waitq_eventmask:_EVENT_MASK_BITS;
 146         /* the wait queue set (set-of-sets) to which this queue belongs */
 147 #if __arm64__
 148         hw_lock_bit_t   waitq_interlock;        /* interlock */
 149 #else
 150         hw_lock_data_t  waitq_interlock;        /* interlock */
 151 #endif /* __arm64__ */
 152
 153         uint64_t waitq_set_id;
 154         uint64_t waitq_prepost_id;
 155         union {
 156                 queue_head_t            waitq_queue;            /* queue of elements */
 157                 struct priority_queue   waitq_prio_queue;       /* priority ordered queue of elements */
 158         };
 159 };
 160
 161 static_assert(sizeof(struct waitq) == WQ_OPAQUE_SIZE, "waitq structure size mismatch");
 162 static_assert(__alignof(struct waitq) == WQ_OPAQUE_ALIGN, "waitq structure alignment mismatch");
 163
 164 /*
 165  *      struct waitq_set
 166  *
 167  *      This is the common definition for a set wait queue.
 168  */
 169 struct waitq_set {
 170         struct waitq wqset_q;
 171         uint64_t     wqset_id;
 172         union {
 173                 uint64_t     wqset_prepost_id;
 174                 void        *wqset_prepost_hook;
 175         };
 176 };
 177
 178 #define WQSET_NOT_LINKED       ((uint64_t)(~0))
 179 static_assert(sizeof(struct waitq_set) == WQS_OPAQUE_SIZE, "waitq_set structure size mismatch");
 180 static_assert(__alignof(struct waitq_set) == WQS_OPAQUE_ALIGN, "waitq_set structure alignment mismatch");
 181
 182 extern void waitq_bootstrap(void);
 183
 184 #define waitq_is_queue(wq) \
 185         ((wq)->waitq_type == WQT_QUEUE)
 186
 187 #define waitq_is_turnstile_queue(wq) \
 188         (((wq)->waitq_irq) && (wq)->waitq_turnstile_or_port)
 189
 190 #define waitq_is_port_queue(wq) \
 191         (!((wq)->waitq_irq) && (wq)->waitq_turnstile_or_port)
 192
 193 #define waitq_is_set(wq) \
 194         ((wq)->waitq_type == WQT_SET && ((struct waitq_set *)(wq))->wqset_id != 0)
 195
 196 #define waitqs_is_set(wqs) \
 197         (((wqs)->wqset_q.waitq_type == WQT_SET) && ((wqs)->wqset_id != 0))
 198
 199 #define waitq_valid(wq) \
 200         ((wq) != NULL && (wq)->waitq_isvalid)
 201
 202 #define waitqs_is_linked(wqs) \
 203         (((wqs)->wqset_id != WQSET_NOT_LINKED) && ((wqs)->wqset_id != 0))
 204
 205 /*
 206  * Invalidate a waitq. The only valid waitq functions to call after this are:
 207  *      waitq_deinit()
 208  *      waitq_set_deinit()
 209  */
 210 extern void waitq_invalidate_locked(struct waitq *wq);
 211
 212 static inline boolean_t
 213 waitq_empty(struct waitq *wq)
 214 {
 215         if (waitq_is_turnstile_queue(wq)) {
 216                 return priority_queue_empty(&(wq->waitq_prio_queue));
 217         } else {
 218                 return queue_empty(&(wq->waitq_queue));
 219         }
 220 }
 221
 222 extern lck_grp_t waitq_lck_grp;
 223
 224 #if __arm64__
 225
 226 #define waitq_held(wq) \
 227         (hw_lock_bit_held(&(wq)->waitq_interlock, LCK_ILOCK))
 228
 229 #define waitq_lock_try(wq) \
 230         (hw_lock_bit_try(&(wq)->waitq_interlock, LCK_ILOCK, &waitq_lck_grp))
 231
 232 #else
 233
 234 #define waitq_held(wq) \
 235         (hw_lock_held(&(wq)->waitq_interlock))
 236
 237 #define waitq_lock_try(wq) \
 238         (hw_lock_try(&(wq)->waitq_interlock, &waitq_lck_grp))
 239
 240 #endif /* __arm64__ */
 241
 242 #define waitq_wait_possible(thread) \
 243         ((thread)->waitq == NULL)
 244
 245 extern void waitq_lock(struct waitq *wq);
 246
 247 #define waitq_set_lock(wqs)             waitq_lock(&(wqs)->wqset_q)
 248 #define waitq_set_unlock(wqs)           waitq_unlock(&(wqs)->wqset_q)
 249 #define waitq_set_lock_try(wqs)         waitq_lock_try(&(wqs)->wqset_q)
 250 #define waitq_set_can_prepost(wqs)      (waitqs_is_set(wqs) && \
 251                                          (wqs)->wqset_q.waitq_prepost)
 252 #define waitq_set_maybe_preposted(wqs)  ((wqs)->wqset_q.waitq_prepost && \
 253                                          (wqs)->wqset_prepost_id > 0)
 254 #define waitq_set_has_prepost_hook(wqs) (waitqs_is_set(wqs) && \
 255                                          !((wqs)->wqset_q.waitq_prepost) && \
 256                                          (wqs)->wqset_prepost_hook)
 257
 258 /* assert intent to wait on a locked wait queue */
 259 extern wait_result_t waitq_assert_wait64_locked(struct waitq *waitq,
 260     event64_t wait_event,
 261     wait_interrupt_t interruptible,
 262     wait_timeout_urgency_t urgency,
 263     uint64_t deadline,
 264     uint64_t leeway,
 265     thread_t thread);
 266
 267 /* pull a thread from its wait queue */
 268 extern int waitq_pull_thread_locked(struct waitq *waitq, thread_t thread);
 269
 270 /* wakeup all threads waiting for a particular event on locked queue */
 271 extern kern_return_t waitq_wakeup64_all_locked(struct waitq *waitq,
 272     event64_t wake_event,
 273     wait_result_t result,
 274     uint64_t *reserved_preposts,
 275     int priority,
 276     waitq_lock_state_t lock_state);
 277
 278 /* wakeup one thread waiting for a particular event on locked queue */
 279 extern kern_return_t waitq_wakeup64_one_locked(struct waitq *waitq,
 280     event64_t wake_event,
 281     wait_result_t result,
 282     uint64_t *reserved_preposts,
 283     int priority,
 284     waitq_lock_state_t lock_state);
 285
 286 /* return identity of a thread awakened for a particular <wait_queue,event> */
 287 extern thread_t
 288 waitq_wakeup64_identify_locked(struct waitq     *waitq,
 289     event64_t        wake_event,
 290     wait_result_t    result,
 291     spl_t            *spl,
 292     uint64_t         *reserved_preposts,
 293     int              priority,
 294     waitq_lock_state_t lock_state);
 295
 296 /* wakeup thread iff its still waiting for a particular event on locked queue */
 297 extern kern_return_t waitq_wakeup64_thread_locked(struct waitq *waitq,
 298     event64_t wake_event,
 299     thread_t thread,
 300     wait_result_t result,
 301     waitq_lock_state_t lock_state);
 302
 303 /* clear all preposts generated by the given waitq */
 304 extern int waitq_clear_prepost_locked(struct waitq *waitq);
 305
 306 /* clear all preposts from the given wait queue set */
 307 extern void waitq_set_clear_preposts_locked(struct waitq_set *wqset);
 308
 309 /* unlink the given waitq from all sets - returns unlocked */
 310 extern kern_return_t waitq_unlink_all_unlock(struct waitq *waitq);
 311
 312 /* unlink the given waitq set from all waitqs and waitq sets - returns unlocked */
 313 extern kern_return_t waitq_set_unlink_all_unlock(struct waitq_set *wqset);
 314
 315
 316
 317 /*
 318  * clear a thread's boosted priority
 319  * (given via WAITQ_PROMOTE_PRIORITY in the wakeup function)
 320  */
 321 extern void waitq_clear_promotion_locked(struct waitq *waitq,
 322     thread_t thread);
 323
 324 /*
 325  * waitq iteration
 326  */
 327
 328 enum waitq_iteration_constant {
 329         WQ_ITERATE_DROPPED             = -4,
 330         WQ_ITERATE_INVALID             = -3,
 331         WQ_ITERATE_ABORTED             = -2,
 332         WQ_ITERATE_FAILURE             = -1,
 333         WQ_ITERATE_SUCCESS             =  0,
 334         WQ_ITERATE_CONTINUE            =  1,
 335         WQ_ITERATE_BREAK               =  2,
 336         WQ_ITERATE_BREAK_KEEP_LOCKED   =  3,
 337         WQ_ITERATE_INVALIDATE_CONTINUE =  4,
 338         WQ_ITERATE_RESTART             =  5,
 339         WQ_ITERATE_FOUND               =  6,
 340         WQ_ITERATE_UNLINKED            =  7,
 341 };
 342
 343 /* callback invoked with both 'waitq' and 'wqset' locked */
 344 typedef int (*waitq_iterator_t)(void *ctx, struct waitq *waitq,
 345     struct waitq_set *wqset);
 346
 347 /* iterate over all sets to which waitq belongs */
 348 extern int waitq_iterate_sets(struct waitq *waitq, void *ctx,
 349     waitq_iterator_t it);
 350
 351 /* iterator over all waitqs that have preposted to wqset */
 352 extern int waitq_set_iterate_preposts(struct waitq_set *wqset,
 353     void *ctx, waitq_iterator_t it);
 354
 355 /*
 356  * prepost reservation
 357  */
 358 extern uint64_t waitq_prepost_reserve(struct waitq *waitq, int extra,
 359     waitq_lock_state_t lock_state);
 360
 361 extern void waitq_prepost_release_reserve(uint64_t id);
 362
 363 #else /* !MACH_KERNEL_PRIVATE */
 364
 365 /*
 366  * The opaque waitq structure is here mostly for AIO and selinfo,
 367  * but could potentially be used by other BSD subsystems.
 368  */
 369 struct waitq { char opaque[WQ_OPAQUE_SIZE]; } __attribute__((aligned(WQ_OPAQUE_ALIGN)));
 370 struct waitq_set { char opaque[WQS_OPAQUE_SIZE]; } __attribute__((aligned(WQS_OPAQUE_ALIGN)));
 371
 372 #endif  /* MACH_KERNEL_PRIVATE */
 373
 374
 375 __BEGIN_DECLS
 376
 377 /*
 378  * waitq init
 379  */
 380 extern kern_return_t waitq_init(struct waitq *waitq, int policy);
 381 extern void waitq_deinit(struct waitq *waitq);
 382
 383 /*
 384  * global waitqs
 385  */
 386 extern struct waitq *_global_eventq(char *event, size_t event_length);
 387 #define global_eventq(event) _global_eventq((char *)&(event), sizeof(event))
 388
 389 extern struct waitq *global_waitq(int index);
 390
 391 typedef uint16_t waitq_set_prepost_hook_t;
 392
 393 /*
 394  * set alloc/init/free
 395  */
 396 extern struct waitq_set *waitq_set_alloc(int policy,
 397     waitq_set_prepost_hook_t *prepost_hook);
 398
 399 extern kern_return_t waitq_set_init(struct waitq_set *wqset,
 400     int policy, uint64_t *reserved_link,
 401     waitq_set_prepost_hook_t *prepost_hook);
 402
 403 extern void waitq_set_deinit(struct waitq_set *wqset);
 404
 405 extern kern_return_t waitq_set_free(struct waitq_set *wqset);
 406
 407 #if DEVELOPMENT || DEBUG
 408 extern int sysctl_helper_waitq_set_nelem(void);
 409 #if CONFIG_WAITQ_DEBUG
 410 extern uint64_t wqset_id(struct waitq_set *wqset);
 411
 412 struct waitq *wqset_waitq(struct waitq_set *wqset);
 413 #endif /* CONFIG_WAITQ_DEBUG */
 414 #endif /* DEVELOPMENT || DEBUG */
 415
 416
 417 /*
 418  * set membership
 419  */
 420 extern uint64_t waitq_link_reserve(struct waitq *waitq);
 421 extern void waitq_set_lazy_init_link(struct waitq_set *wqset);
 422 extern boolean_t waitq_set_should_lazy_init_link(struct waitq_set *wqset);
 423
 424 extern void waitq_link_release(uint64_t id);
 425
 426 extern boolean_t waitq_member(struct waitq *waitq, struct waitq_set *wqset);
 427
 428 /* returns true if the waitq is in at least 1 set */
 429 extern boolean_t waitq_in_set(struct waitq *waitq);
 430
 431
 432 /* on success, consumes an reserved_link reference */
 433 extern kern_return_t waitq_link(struct waitq *waitq,
 434     struct waitq_set *wqset,
 435     waitq_lock_state_t lock_state,
 436     uint64_t *reserved_link);
 437
 438 extern kern_return_t waitq_unlink(struct waitq *waitq, struct waitq_set *wqset);
 439
 440 extern kern_return_t waitq_unlink_all(struct waitq *waitq);
 441
 442 extern kern_return_t waitq_set_unlink_all(struct waitq_set *wqset);
 443
 444 /*
 445  * preposts
 446  */
 447 extern void waitq_clear_prepost(struct waitq *waitq);
 448
 449 extern void waitq_set_clear_preposts(struct waitq_set *wqset);
 450
 451 /*
 452  * interfaces used primarily by the select/kqueue subsystems
 453  */
 454 extern uint64_t waitq_get_prepost_id(struct waitq *waitq);
 455 extern void     waitq_unlink_by_prepost_id(uint64_t wqp_id, struct waitq_set *wqset);
 456 extern struct waitq *waitq_lock_by_prepost_id(uint64_t wqp_id);
 457
 458 /*
 459  * waitq attributes
 460  */
 461 extern int waitq_is_valid(struct waitq *waitq);
 462
 463 extern int waitq_set_is_valid(struct waitq_set *wqset);
 464
 465 extern int waitq_is_global(struct waitq *waitq);
 466
 467 extern int waitq_irq_safe(struct waitq *waitq);
 468
 469 extern struct waitq * waitq_get_safeq(struct waitq *waitq);
 470
 471 #if CONFIG_WAITQ_STATS
 472 /*
 473  * waitq statistics
 474  */
 475 #define WAITQ_STATS_VERSION 1
 476 struct wq_table_stats {
 477         uint32_t version;
 478         uint32_t table_elements;
 479         uint32_t table_used_elems;
 480         uint32_t table_elem_sz;
 481         uint32_t table_slabs;
 482         uint32_t table_slab_sz;
 483
 484         uint64_t table_num_allocs;
 485         uint64_t table_num_preposts;
 486         uint64_t table_num_reservations;
 487
 488         uint64_t table_max_used;
 489         uint64_t table_avg_used;
 490         uint64_t table_max_reservations;
 491         uint64_t table_avg_reservations;
 492 };
 493
 494 extern void waitq_link_stats(struct wq_table_stats *stats);
 495 extern void waitq_prepost_stats(struct wq_table_stats *stats);
 496 #endif /* CONFIG_WAITQ_STATS */
 497
 498 /*
 499  *
 500  * higher-level waiting APIs
 501  *
 502  */
 503
 504 /* assert intent to wait on <waitq,event64> pair */
 505 extern wait_result_t waitq_assert_wait64(struct waitq *waitq,
 506     event64_t wait_event,
 507     wait_interrupt_t interruptible,
 508     uint64_t deadline);
 509
 510 extern wait_result_t waitq_assert_wait64_leeway(struct waitq *waitq,
 511     event64_t wait_event,
 512     wait_interrupt_t interruptible,
 513     wait_timeout_urgency_t urgency,
 514     uint64_t deadline,
 515     uint64_t leeway);
 516
 517 /* wakeup the most appropriate thread waiting on <waitq,event64> pair */
 518 extern kern_return_t waitq_wakeup64_one(struct waitq *waitq,
 519     event64_t wake_event,
 520     wait_result_t result,
 521     int priority);
 522
 523 /* wakeup all the threads waiting on <waitq,event64> pair */
 524 extern kern_return_t waitq_wakeup64_all(struct waitq *waitq,
 525     event64_t wake_event,
 526     wait_result_t result,
 527     int priority);
 528
 529 #ifdef  XNU_KERNEL_PRIVATE
 530
 531 /* wakeup a specified thread iff it's waiting on <waitq,event64> pair */
 532 extern kern_return_t waitq_wakeup64_thread(struct waitq *waitq,
 533     event64_t wake_event,
 534     thread_t thread,
 535     wait_result_t result);
 536
 537 /* return a reference to the thread that was woken up */
 538 extern thread_t
 539 waitq_wakeup64_identify(struct waitq    *waitq,
 540     event64_t       wake_event,
 541     wait_result_t   result,
 542     int             priority);
 543
 544 /* take the waitq lock */
 545 extern void waitq_unlock(struct waitq *wq);
 546
 547 #endif /* XNU_KERNEL_PRIVATE */
 548
 549 __END_DECLS
 550
 551 #endif  /* KERNEL_PRIVATE */
 552 #endif  /* _WAITQ_H_ */