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