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 <machine/cpu_number.h>
  47
  48 /*
  49  *      wait_queue_t
  50  *      This is the definition of the common event wait queue
  51  *      that the scheduler APIs understand.  It is used
  52  *      internally by the gerneralized event waiting mechanism
  53  *      (assert_wait), and also for items that maintain their
  54  *      own wait queues (such as ports and semaphores).
  55  *
  56  *      It is not published to other kernel components.  They
  57  *      can create wait queues by calling wait_queue_alloc.
  58  *
  59  *      NOTE:  Hardware locks are used to protect event wait
  60  *      queues since interrupt code is free to post events to
  61  *      them.
  62  */
  63 typedef struct wait_queue {
  64     unsigned int                    /* flags */
  65     /* boolean_t */     wq_type:16,             /* only public field */
  66                                         wq_fifo:1,              /* fifo wakeup policy? */
  67                                         wq_isprepost:1, /* is waitq preposted? set only */
  68                                         :0;                             /* force to long boundary */
  69     hw_lock_data_t      wq_interlock;   /* interlock */
  70     queue_head_t        wq_queue;               /* queue of elements */
  71 } WaitQueue;
  72
  73 /*
  74  *      wait_queue_set_t
  75  *      This is the common definition for a set wait queue.
  76  *      These can be linked as members/elements of multiple regular
  77  *      wait queues.  They have an additional set of linkages to
  78  *      identify the linkage structures that point to them.
  79  */
  80 typedef struct wait_queue_set {
  81         WaitQueue               wqs_wait_queue; /* our wait queue */
  82         queue_head_t    wqs_setlinks;   /* links from set perspective */
  83         unsigned int    wqs_refcount;   /* refcount for preposting */
  84 } WaitQueueSet;
  85
  86 #define wqs_type                wqs_wait_queue.wq_type
  87 #define wqs_fifo                wqs_wait_queue.wq_fifo
  88 #define wqs_isprepost   wqs_wait_queue.wq_isprepost
  89 #define wqs_queue               wqs_wait_queue.wq_queue
  90
  91 /*
  92  *      wait_queue_element_t
  93  *      This structure describes the elements on an event wait
  94  *      queue.  It is the common first fields in a thread shuttle
  95  *      and wait_queue_link_t.  In that way, a wait queue can
  96  *      consist of both thread shuttle elements and links off of
  97  *      to other (set) wait queues.
  98  *
  99  *      WARNING: These fields correspond to fields in the thread
 100  *      shuttle (run queue links and run queue pointer). Any change in
 101  *      the layout here will have to be matched with a change there.
 102  */
 103 typedef struct wait_queue_element {
 104         queue_chain_t   wqe_links;      /* link of elements on this queue */
 105         void *                  wqe_type;       /* Identifies link vs. thread */
 106         wait_queue_t    wqe_queue;      /* queue this element is on */
 107 } WaitQueueElement;
 108
 109 typedef WaitQueueElement *wait_queue_element_t;
 110
 111 /*
 112  *      wait_queue_link_t
 113  *      Specialized wait queue element type for linking set
 114  *      event waits queues onto a wait queue.  In this way, an event
 115  *      can be constructed so that any thread waiting on any number
 116  *      of associated wait queues can handle the event, while letting
 117  *      the thread only be linked on the single wait queue it blocked on.
 118  *
 119  *      One use: ports in multiple portsets.  Each thread is queued up
 120  *      on the portset that it specifically blocked on during a receive
 121  *      operation.  Each port's event queue links in all the portset
 122  *      event queues of which it is a member.  An IPC event post associated
 123  *      with that port may wake up any thread from any of those portsets,
 124  *      or one that was waiting locally on the port itself.
 125  */
 126 typedef struct _wait_queue_link {
 127         WaitQueueElement                wql_element;    /* element on master */
 128         queue_chain_t                   wql_setlinks;   /* element on set */
 129     wait_queue_set_t            wql_setqueue;   /* set queue */
 130 } WaitQueueLink;
 131
 132 #define wql_links wql_element.wqe_links
 133 #define wql_type  wql_element.wqe_type
 134 #define wql_queue wql_element.wqe_queue
 135
 136 #define _WAIT_QUEUE_inited                      0xf1d0
 137 #define _WAIT_QUEUE_SET_inited          0xf1d1
 138
 139 #define wait_queue_is_queue(wq) \
 140         ((wq)->wq_type == _WAIT_QUEUE_inited)
 141
 142 #define wait_queue_is_set(wqs)  \
 143         ((wqs)->wqs_type == _WAIT_QUEUE_SET_inited)
 144
 145 #define wait_queue_is_valid(wq) \
 146         (((wq)->wq_type & ~1) == _WAIT_QUEUE_inited)
 147
 148 #define wait_queue_empty(wq)    (queue_empty(&(wq)->wq_queue))
 149
 150 #define wait_queue_held(wq)             (hw_lock_held(&(wq)->wq_interlock))
 151 #define wait_queue_lock_try(wq) (hw_lock_try(&(wq)->wq_interlock))
 152
 153 /* For x86, the hardware timeout is in TSC units. */
 154 #if defined(i386)
 155 #define hwLockTimeOut LockTimeOutTSC
 156 #else
 157 #define hwLockTimeOut LockTimeOut
 158 #endif
 159 /*
 160  * Double the standard lock timeout, because wait queues tend
 161  * to iterate over a number of threads - locking each.  If there is
 162  * a problem with a thread lock, it normally times out at the wait
 163  * queue level first, hiding the real problem.
 164  */
 165
 166 static inline void wait_queue_lock(wait_queue_t wq) {
 167         if (!hw_lock_to(&(wq)->wq_interlock, hwLockTimeOut * 2))
 168                 panic("wait queue deadlock - wq=%p, cpu=%d\n", wq, cpu_number(
 169 ));
 170 }
 171
 172 static inline void wait_queue_unlock(wait_queue_t wq) {
 173         assert(wait_queue_held(wq));
 174 #if defined(__i386__)
 175         /* DRK: On certain x86 systems, this spinlock is susceptible to
 176          * lock starvation. Hence use an unlock variant which performs
 177          * a cacheline flush to minimize cache affinity on acquisition.
 178          */
 179         i386_lock_unlock_with_flush(&(wq)->wq_interlock);
 180 #else
 181         hw_lock_unlock(&(wq)->wq_interlock);
 182 #endif
 183 }
 184
 185 #define wqs_lock(wqs)           wait_queue_lock(&(wqs)->wqs_wait_queue)
 186 #define wqs_unlock(wqs)         wait_queue_unlock(&(wqs)->wqs_wait_queue)
 187 #define wqs_lock_try(wqs)       wait_queue__try_lock(&(wqs)->wqs_wait_queue)
 188
 189 #define wait_queue_assert_possible(thread) \
 190                         ((thread)->wait_queue == WAIT_QUEUE_NULL)
 191
 192 /******** Decomposed interfaces (to build higher level constructs) ***********/
 193
 194 /* assert intent to wait on a locked wait queue */
 195 __private_extern__ wait_result_t wait_queue_assert_wait64_locked(
 196                         wait_queue_t wait_queue,
 197                         event64_t wait_event,
 198                         wait_interrupt_t interruptible,
 199                         uint64_t deadline,
 200                         thread_t thread);
 201
 202 /* pull a thread from its wait queue */
 203 __private_extern__ void wait_queue_pull_thread_locked(
 204                         wait_queue_t wait_queue,
 205                         thread_t thread,
 206                         boolean_t unlock);
 207
 208 /* wakeup all threads waiting for a particular event on locked queue */
 209 __private_extern__ kern_return_t wait_queue_wakeup64_all_locked(
 210                         wait_queue_t wait_queue,
 211                         event64_t wake_event,
 212                         wait_result_t result,
 213                         boolean_t unlock);
 214
 215 /* wakeup one thread waiting for a particular event on locked queue */
 216 __private_extern__ kern_return_t wait_queue_wakeup64_one_locked(
 217                         wait_queue_t wait_queue,
 218                         event64_t wake_event,
 219                         wait_result_t result,
 220                         boolean_t unlock);
 221
 222 /* return identity of a thread awakened for a particular <wait_queue,event> */
 223 __private_extern__ thread_t wait_queue_wakeup64_identity_locked(
 224                         wait_queue_t wait_queue,
 225                         event64_t wake_event,
 226                         wait_result_t result,
 227                         boolean_t unlock);
 228
 229 /* wakeup thread iff its still waiting for a particular event on locked queue */
 230 __private_extern__ kern_return_t wait_queue_wakeup64_thread_locked(
 231                         wait_queue_t wait_queue,
 232                         event64_t wake_event,
 233                         thread_t thread,
 234                         wait_result_t result,
 235                         boolean_t unlock);
 236
 237 #endif  /* MACH_KERNEL_PRIVATE */
 238
 239 __BEGIN_DECLS
 240
 241 /******** Semi-Public interfaces (not a part of a higher construct) ************/
 242
 243 extern unsigned int wait_queue_set_size(void);
 244 extern unsigned int wait_queue_link_size(void);
 245
 246 extern kern_return_t wait_queue_init(
 247                         wait_queue_t wait_queue,
 248                         int policy);
 249
 250 extern wait_queue_set_t wait_queue_set_alloc(
 251                         int policy);
 252
 253 extern kern_return_t wait_queue_set_init(
 254                         wait_queue_set_t set_queue,
 255                         int policy);
 256
 257 extern kern_return_t wait_queue_set_free(
 258                         wait_queue_set_t set_queue);
 259
 260 extern wait_queue_link_t wait_queue_link_alloc(
 261                         int policy);
 262
 263 extern kern_return_t wait_queue_link_free(
 264                         wait_queue_link_t link_element);
 265
 266 extern kern_return_t wait_queue_link(
 267                         wait_queue_t wait_queue,
 268                         wait_queue_set_t set_queue);
 269
 270 extern kern_return_t wait_queue_link_noalloc(
 271                         wait_queue_t wait_queue,
 272                         wait_queue_set_t set_queue,
 273                         wait_queue_link_t link);
 274
 275 extern boolean_t wait_queue_member(
 276                         wait_queue_t wait_queue,
 277                         wait_queue_set_t set_queue);
 278
 279 extern kern_return_t wait_queue_unlink(
 280                         wait_queue_t wait_queue,
 281                         wait_queue_set_t set_queue);
 282
 283 extern kern_return_t wait_queue_unlink_all(
 284                         wait_queue_t wait_queue);
 285
 286 extern kern_return_t wait_queue_unlinkall_nofree(
 287                         wait_queue_t wait_queue);
 288
 289 extern kern_return_t wait_queue_set_unlink_all(
 290                         wait_queue_set_t set_queue);
 291
 292 /* legacy API */
 293 kern_return_t wait_queue_sub_init(
 294                         wait_queue_set_t set_queue,
 295                         int policy);
 296
 297 kern_return_t wait_queue_sub_clearrefs(
 298                         wait_queue_set_t wq_set);
 299
 300 extern kern_return_t wait_subqueue_unlink_all(
 301                         wait_queue_set_t set_queue);
 302
 303 extern wait_queue_t wait_queue_alloc(
 304                         int policy);
 305
 306 extern kern_return_t wait_queue_free(
 307                         wait_queue_t wait_queue);
 308
 309 /* assert intent to wait on <wait_queue,event64> pair */
 310 extern wait_result_t wait_queue_assert_wait64(
 311                         wait_queue_t wait_queue,
 312                         event64_t wait_event,
 313                         wait_interrupt_t interruptible,
 314                         uint64_t deadline);
 315
 316 /* wakeup the most appropriate thread waiting on <wait_queue,event64> pair */
 317 extern kern_return_t wait_queue_wakeup64_one(
 318                         wait_queue_t wait_queue,
 319                         event64_t wake_event,
 320                         wait_result_t result);
 321
 322 /* wakeup all the threads waiting on <wait_queue,event64> pair */
 323 extern kern_return_t wait_queue_wakeup64_all(
 324                         wait_queue_t wait_queue,
 325                         event64_t wake_event,
 326                         wait_result_t result);
 327
 328 /* wakeup a specified thread waiting iff waiting on <wait_queue,event64> pair */
 329 extern kern_return_t wait_queue_wakeup64_thread(
 330                         wait_queue_t wait_queue,
 331                         event64_t wake_event,
 332                         thread_t thread,
 333                         wait_result_t result);
 334
 335 /*
 336  * Compatibility Wait Queue APIs based on pointer events instead of 64bit
 337  * integer events.
 338  */
 339
 340 /* assert intent to wait on <wait_queue,event> pair */
 341 extern wait_result_t wait_queue_assert_wait(
 342                         wait_queue_t wait_queue,
 343                         event_t wait_event,
 344                         wait_interrupt_t interruptible,
 345                         uint64_t deadline);
 346
 347 /* wakeup the most appropriate thread waiting on <wait_queue,event> pair */
 348 extern kern_return_t wait_queue_wakeup_one(
 349                         wait_queue_t wait_queue,
 350                         event_t wake_event,
 351                         wait_result_t result);
 352
 353 /* wakeup all the threads waiting on <wait_queue,event> pair */
 354 extern kern_return_t wait_queue_wakeup_all(
 355                         wait_queue_t wait_queue,
 356                         event_t wake_event,
 357                         wait_result_t result);
 358
 359 /* wakeup a specified thread waiting iff waiting on <wait_queue,event> pair */
 360 extern kern_return_t wait_queue_wakeup_thread(
 361                         wait_queue_t wait_queue,
 362                         event_t wake_event,
 363                         thread_t thread,
 364                         wait_result_t result);
 365
 366 __END_DECLS
 367
 368 #endif  /* _KERN_WAIT_QUEUE_H_ */
 369
 370 #endif  /* KERNEL_PRIVATE */