osfmk/kern/wait_queue.h

   1 /*
   2  * Copyright (c) 2000-2005 Apple Computer, 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 #ifdef  KERNEL_PRIVATE
  30
  31 #ifndef _KERN_WAIT_QUEUE_H_
  32 #define _KERN_WAIT_QUEUE_H_
  33
  34 #include <mach/mach_types.h>
  35 #include <mach/sync_policy.h>
  36 #include <mach/kern_return.h>           /* for kern_return_t */
  37
  38 #include <kern/kern_types.h>            /* for wait_queue_t */
  39
  40 #include <sys/cdefs.h>
  41
  42 #ifdef  MACH_KERNEL_PRIVATE
  43
  44 #include <kern/lock.h>
  45 #include <kern/queue.h>
  46 #include <mach/branch_predicates.h>
  47
  48 #include <machine/cpu_number.h>
  49 #include <machine/machine_routines.h> /* machine_timeout_suspended() */
  50 /*
  51  *      wait_queue_t
  52  *      This is the definition of the common event wait queue
  53  *      that the scheduler APIs understand.  It is used
  54  *      internally by the gerneralized event waiting mechanism
  55  *      (assert_wait), and also for items that maintain their
  56  *      own wait queues (such as ports and semaphores).
  57  *
  58  *      It is not published to other kernel components.  They
  59  *      can create wait queues by calling wait_queue_alloc.
  60  *
  61  *      NOTE:  Hardware locks are used to protect event wait
  62  *      queues since interrupt code is free to post events to
  63  *      them.
  64  */
  65 typedef struct wait_queue {
  66     unsigned int                    /* flags */
  67     /* boolean_t */     wq_type:16,             /* only public field */
  68                                         wq_fifo:1,              /* fifo wakeup policy? */
  69                                         wq_prepost:1,   /* waitq supports prepost? set only */
  70                                         :0;                             /* force to long boundary */
  71     hw_lock_data_t      wq_interlock;   /* interlock */
  72     queue_head_t        wq_queue;               /* queue of elements */
  73 } WaitQueue;
  74
  75 /*
  76  *      wait_queue_set_t
  77  *      This is the common definition for a set wait queue.
  78  *      These can be linked as members/elements of multiple regular
  79  *      wait queues.  They have an additional set of linkages to
  80  *      identify the linkage structures that point to them.
  81  */
  82 typedef struct wait_queue_set {
  83         WaitQueue               wqs_wait_queue; /* our wait queue */
  84         queue_head_t    wqs_setlinks;   /* links from set perspective */
  85         queue_head_t    wqs_preposts;   /* preposted links */
  86 } WaitQueueSet;
  87
  88 #define wqs_type                wqs_wait_queue.wq_type
  89 #define wqs_fifo                wqs_wait_queue.wq_fifo
  90 #define wqs_prepost     wqs_wait_queue.wq_prepost
  91 #define wqs_queue               wqs_wait_queue.wq_queue
  92
  93 /*
  94  *      wait_queue_element_t
  95  *      This structure describes the elements on an event wait
  96  *      queue.  It is the common first fields in a thread shuttle
  97  *      and wait_queue_link_t.  In that way, a wait queue can
  98  *      consist of both thread shuttle elements and links off of
  99  *      to other (set) wait queues.
 100  *
 101  *      WARNING: These fields correspond to fields in the thread
 102  *      shuttle (run queue links and run queue pointer). Any change in
 103  *      the layout here will have to be matched with a change there.
 104  */
 105 typedef struct wait_queue_element {
 106         queue_chain_t   wqe_links;      /* link of elements on this queue */
 107         void *                  wqe_type;       /* Identifies link vs. thread */
 108         wait_queue_t    wqe_queue;      /* queue this element is on */
 109 } WaitQueueElement;
 110
 111 typedef WaitQueueElement *wait_queue_element_t;
 112
 113 /*
 114  *      wait_queue_link_t
 115  *      Specialized wait queue element type for linking set
 116  *      event waits queues onto a wait queue.  In this way, an event
 117  *      can be constructed so that any thread waiting on any number
 118  *      of associated wait queues can handle the event, while letting
 119  *      the thread only be linked on the single wait queue it blocked on.
 120  *
 121  *      One use: ports in multiple portsets.  Each thread is queued up
 122  *      on the portset that it specifically blocked on during a receive
 123  *      operation.  Each port's event queue links in all the portset
 124  *      event queues of which it is a member.  An IPC event post associated
 125  *      with that port may wake up any thread from any of those portsets,
 126  *      or one that was waiting locally on the port itself.
 127  */
 128 typedef struct _wait_queue_link {
 129         WaitQueueElement                wql_element;    /* element on master */
 130         queue_chain_t                   wql_setlinks;   /* element on set */
 131         queue_chain_t                   wql_preposts;   /* element on set prepost list */
 132     wait_queue_set_t            wql_setqueue;   /* set queue */
 133 } WaitQueueLink;
 134
 135 #define wql_links wql_element.wqe_links
 136 #define wql_type  wql_element.wqe_type
 137 #define wql_queue wql_element.wqe_queue
 138
 139 #define _WAIT_QUEUE_inited                      0xf1d0
 140 #define _WAIT_QUEUE_SET_inited          0xf1d1
 141
 142 #define wait_queue_is_queue(wq) \
 143         ((wq)->wq_type == _WAIT_QUEUE_inited)
 144
 145 #define wait_queue_is_set(wqs)  \
 146         ((wqs)->wqs_type == _WAIT_QUEUE_SET_inited)
 147
 148 #define wait_queue_is_valid(wq) \
 149         (((wq)->wq_type & ~1) == _WAIT_QUEUE_inited)
 150
 151 #define wait_queue_empty(wq)    (queue_empty(&(wq)->wq_queue))
 152
 153 #define wait_queue_held(wq)             (hw_lock_held(&(wq)->wq_interlock))
 154 #define wait_queue_lock_try(wq) (hw_lock_try(&(wq)->wq_interlock))
 155
 156 /* For x86, the hardware timeout is in TSC units. */
 157 #if defined(i386) || defined(x86_64)
 158 #define hwLockTimeOut LockTimeOutTSC
 159 #else
 160 #define hwLockTimeOut LockTimeOut
 161 #endif
 162 /*
 163  * Double the standard lock timeout, because wait queues tend
 164  * to iterate over a number of threads - locking each.  If there is
 165  * a problem with a thread lock, it normally times out at the wait
 166  * queue level first, hiding the real problem.
 167  */
 168
 169 static inline void wait_queue_lock(wait_queue_t wq) {
 170         if (__improbable(hw_lock_to(&(wq)->wq_interlock, hwLockTimeOut * 2) == 0)) {
 171                 boolean_t wql_acquired = FALSE;
 172
 173                 while (machine_timeout_suspended()) {
 174 #if     defined(__i386__) || defined(__x86_64__)
 175 /*
 176  * i386/x86_64 return with preemption disabled on a timeout for
 177  * diagnostic purposes.
 178  */
 179                         mp_enable_preemption();
 180 #endif
 181                         if ((wql_acquired = hw_lock_to(&(wq)->wq_interlock, hwLockTimeOut * 2)))
 182                                 break;
 183                 }
 184                 if (wql_acquired == FALSE)
 185                         panic("wait queue deadlock - wq=%p, cpu=%d\n", wq, cpu_number());
 186         }
 187 }
 188
 189 static inline void wait_queue_unlock(wait_queue_t wq) {
 190         assert(wait_queue_held(wq));
 191         hw_lock_unlock(&(wq)->wq_interlock);
 192 }
 193
 194 #define wqs_lock(wqs)           wait_queue_lock(&(wqs)->wqs_wait_queue)
 195 #define wqs_unlock(wqs)         wait_queue_unlock(&(wqs)->wqs_wait_queue)
 196 #define wqs_lock_try(wqs)       wait_queue__try_lock(&(wqs)->wqs_wait_queue)
 197 #define wqs_is_preposted(wqs)   ((wqs)->wqs_prepost && !queue_empty(&(wqs)->wqs_preposts))
 198
 199 #define wql_is_preposted(wql)   ((wql)->wql_preposts.next != NULL)
 200 #define wql_clear_prepost(wql)  ((wql)->wql_preposts.next = (wql)->wql_preposts.prev = NULL)
 201
 202 #define wait_queue_assert_possible(thread) \
 203                         ((thread)->wait_queue == WAIT_QUEUE_NULL)
 204
 205 /* bootstrap interface - can allocate/link wait_queues and sets after calling this */
 206 __private_extern__ void wait_queue_bootstrap(void);
 207
 208 /******** Decomposed interfaces (to build higher level constructs) ***********/
 209
 210 /* assert intent to wait on a locked wait queue */
 211 __private_extern__ wait_result_t wait_queue_assert_wait64_locked(
 212                         wait_queue_t wait_queue,
 213                         event64_t wait_event,
 214                         wait_interrupt_t interruptible,
 215                         uint64_t deadline,
 216                         thread_t thread);
 217
 218 /* pull a thread from its wait queue */
 219 __private_extern__ void wait_queue_pull_thread_locked(
 220                         wait_queue_t wait_queue,
 221                         thread_t thread,
 222                         boolean_t unlock);
 223
 224 /* wakeup all threads waiting for a particular event on locked queue */
 225 __private_extern__ kern_return_t wait_queue_wakeup64_all_locked(
 226                         wait_queue_t wait_queue,
 227                         event64_t wake_event,
 228                         wait_result_t result,
 229                         boolean_t unlock);
 230
 231 /* wakeup one thread waiting for a particular event on locked queue */
 232 __private_extern__ kern_return_t wait_queue_wakeup64_one_locked(
 233                         wait_queue_t wait_queue,
 234                         event64_t wake_event,
 235                         wait_result_t result,
 236                         boolean_t unlock);
 237
 238 /* return identity of a thread awakened for a particular <wait_queue,event> */
 239 __private_extern__ thread_t wait_queue_wakeup64_identity_locked(
 240                         wait_queue_t wait_queue,
 241                         event64_t wake_event,
 242                         wait_result_t result,
 243                         boolean_t unlock);
 244
 245 /* wakeup thread iff its still waiting for a particular event on locked queue */
 246 __private_extern__ kern_return_t wait_queue_wakeup64_thread_locked(
 247                         wait_queue_t wait_queue,
 248                         event64_t wake_event,
 249                         thread_t thread,
 250                         wait_result_t result,
 251                         boolean_t unlock);
 252
 253 __private_extern__ uint32_t num_wait_queues;
 254 __private_extern__ struct wait_queue *wait_queues;
 255 /* The Jenkins "one at a time" hash.
 256  * TBD: There may be some value to unrolling here,
 257  * depending on the architecture.
 258  */
 259 static inline uint32_t wq_hash(char *key)
 260 {
 261         uint32_t hash = 0;
 262         size_t i, length = sizeof(char *);
 263
 264         for (i = 0; i < length; i++) {
 265                 hash += key[i];
 266                 hash += (hash << 10);
 267                 hash ^= (hash >> 6);
 268         }
 269
 270         hash += (hash << 3);
 271         hash ^= (hash >> 11);
 272         hash += (hash << 15);
 273
 274         return hash;
 275 }
 276
 277 /* TBD: It should be possible to eliminate the divide here */
 278 #define       wait_hash(event)                                          \
 279         (wq_hash((char *)&event) % (num_wait_queues))
 280
 281 #endif  /* MACH_KERNEL_PRIVATE */
 282
 283 __BEGIN_DECLS
 284
 285 /******** Semi-Public interfaces (not a part of a higher construct) ************/
 286
 287 extern unsigned int wait_queue_set_size(void);
 288 extern unsigned int wait_queue_link_size(void);
 289
 290 extern kern_return_t wait_queue_init(
 291                         wait_queue_t wait_queue,
 292                         int policy);
 293
 294 extern wait_queue_set_t wait_queue_set_alloc(
 295                         int policy);
 296
 297 extern kern_return_t wait_queue_set_init(
 298                         wait_queue_set_t set_queue,
 299                         int policy);
 300
 301 extern kern_return_t wait_queue_set_free(
 302                         wait_queue_set_t set_queue);
 303
 304 extern wait_queue_link_t wait_queue_link_alloc(
 305                         int policy);
 306
 307 extern kern_return_t wait_queue_link_free(
 308                         wait_queue_link_t link_element);
 309
 310 extern kern_return_t wait_queue_link(
 311                         wait_queue_t wait_queue,
 312                         wait_queue_set_t set_queue);
 313
 314 extern kern_return_t wait_queue_link_noalloc(
 315                         wait_queue_t wait_queue,
 316                         wait_queue_set_t set_queue,
 317                         wait_queue_link_t link);
 318
 319 extern boolean_t wait_queue_member(
 320                         wait_queue_t wait_queue,
 321                         wait_queue_set_t set_queue);
 322
 323 extern kern_return_t wait_queue_unlink(
 324                         wait_queue_t wait_queue,
 325                         wait_queue_set_t set_queue);
 326
 327 extern kern_return_t wait_queue_unlink_all(
 328                         wait_queue_t wait_queue);
 329
 330 extern kern_return_t wait_queue_set_unlink_all(
 331                         wait_queue_set_t set_queue);
 332
 333 #ifdef XNU_KERNEL_PRIVATE
 334 extern kern_return_t wait_queue_set_unlink_one(
 335                         wait_queue_set_t set_queue,
 336                         wait_queue_link_t link);
 337
 338 extern wait_queue_link_t wait_queue_link_allocate(void);
 339
 340 #endif /* XNU_KERNEL_PRIVATE */
 341
 342 /* legacy API */
 343 kern_return_t wait_queue_sub_init(
 344                         wait_queue_set_t set_queue,
 345                         int policy);
 346
 347 kern_return_t wait_queue_sub_clearrefs(
 348                         wait_queue_set_t wq_set);
 349
 350 extern kern_return_t wait_subqueue_unlink_all(
 351                         wait_queue_set_t set_queue);
 352
 353 extern wait_queue_t wait_queue_alloc(
 354                         int policy);
 355
 356 extern kern_return_t wait_queue_free(
 357                         wait_queue_t wait_queue);
 358
 359 /* assert intent to wait on <wait_queue,event64> pair */
 360 extern wait_result_t wait_queue_assert_wait64(
 361                         wait_queue_t wait_queue,
 362                         event64_t wait_event,
 363                         wait_interrupt_t interruptible,
 364                         uint64_t deadline);
 365
 366 /* wakeup the most appropriate thread waiting on <wait_queue,event64> pair */
 367 extern kern_return_t wait_queue_wakeup64_one(
 368                         wait_queue_t wait_queue,
 369                         event64_t wake_event,
 370                         wait_result_t result);
 371
 372 /* wakeup all the threads waiting on <wait_queue,event64> pair */
 373 extern kern_return_t wait_queue_wakeup64_all(
 374                         wait_queue_t wait_queue,
 375                         event64_t wake_event,
 376                         wait_result_t result);
 377
 378 /* wakeup a specified thread waiting iff waiting on <wait_queue,event64> pair */
 379 extern kern_return_t wait_queue_wakeup64_thread(
 380                         wait_queue_t wait_queue,
 381                         event64_t wake_event,
 382                         thread_t thread,
 383                         wait_result_t result);
 384
 385 /*
 386  * Compatibility Wait Queue APIs based on pointer events instead of 64bit
 387  * integer events.
 388  */
 389
 390 /* assert intent to wait on <wait_queue,event> pair */
 391 extern wait_result_t wait_queue_assert_wait(
 392                         wait_queue_t wait_queue,
 393                         event_t wait_event,
 394                         wait_interrupt_t interruptible,
 395                         uint64_t deadline);
 396
 397 /* wakeup the most appropriate thread waiting on <wait_queue,event> pair */
 398 extern kern_return_t wait_queue_wakeup_one(
 399                         wait_queue_t wait_queue,
 400                         event_t wake_event,
 401                         wait_result_t result,
 402                         int priority);
 403
 404 /* wakeup all the threads waiting on <wait_queue,event> pair */
 405 extern kern_return_t wait_queue_wakeup_all(
 406                         wait_queue_t wait_queue,
 407                         event_t wake_event,
 408                         wait_result_t result);
 409
 410 /* wakeup a specified thread waiting iff waiting on <wait_queue,event> pair */
 411 extern kern_return_t wait_queue_wakeup_thread(
 412                         wait_queue_t wait_queue,
 413                         event_t wake_event,
 414                         thread_t thread,
 415                         wait_result_t result);
 416
 417 __END_DECLS
 418
 419 #endif  /* _KERN_WAIT_QUEUE_H_ */
 420
 421 #endif  /* KERNEL_PRIVATE */