osfmk/kern/wait_queue.h

   1 /*
   2  * Copyright (c) 2000 Apple Computer, Inc. All rights reserved.
   3  *
   4  * @APPLE_LICENSE_HEADER_START@
   5  *
   6  * Copyright (c) 1999-2003 Apple Computer, Inc.  All Rights Reserved.
   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. Please obtain a copy of the License at
  12  * http://www.opensource.apple.com/apsl/ and read it before using this
  13  * file.
  14  *
  15  * The Original Code and all software distributed under the License are
  16  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  17  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  18  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  19  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  20  * Please see the License for the specific language governing rights and
  21  * limitations under the License.
  22  *
  23  * @APPLE_LICENSE_HEADER_END@
  24  */
  25 #ifndef _KERN_WAIT_QUEUE_H_
  26 #define _KERN_WAIT_QUEUE_H_
  27
  28 #include <sys/appleapiopts.h>
  29
  30 #ifdef  __APPLE_API_PRIVATE
  31
  32 #include <mach/sync_policy.h>
  33 #include <mach/kern_return.h>           /* for kern_return_t */
  34
  35 #include <kern/kern_types.h>            /* for wait_queue_t */
  36
  37 #ifdef MACH_KERNEL_PRIVATE
  38
  39 #include <kern/lock.h>
  40 #include <kern/queue.h>
  41
  42
  43 /*
  44  *      wait_queue_t
  45  *      This is the definition of the common event wait queue
  46  *      that the scheduler APIs understand.  It is used
  47  *      internally by the gerneralized event waiting mechanism
  48  *      (assert_wait), and also for items that maintain their
  49  *      own wait queues (such as ports and semaphores).
  50  *
  51  *      It is not published to other kernel components.  They
  52  *      can create wait queues by calling wait_queue_alloc.
  53  *
  54  *      NOTE:  Hardware locks are used to protect event wait
  55  *      queues since interrupt code is free to post events to
  56  *      them.
  57  */
  58 typedef struct wait_queue {
  59     unsigned int                    /* flags */
  60     /* boolean_t */     wq_type:16,             /* only public field */
  61                                         wq_fifo:1,              /* fifo wakeup policy? */
  62                                         wq_isprepost:1, /* is waitq preposted? set only */
  63                                         :0;                             /* force to long boundary */
  64     hw_lock_data_t      wq_interlock;   /* interlock */
  65     queue_head_t        wq_queue;               /* queue of elements */
  66 } WaitQueue;
  67
  68 /*
  69  *      wait_queue_set_t
  70  *      This is the common definition for a set wait queue.
  71  *      These can be linked as members/elements of multiple regular
  72  *      wait queues.  They have an additional set of linkages to
  73  *      identify the linkage structures that point to them.
  74  */
  75 typedef struct wait_queue_set {
  76         WaitQueue               wqs_wait_queue; /* our wait queue */
  77         queue_head_t    wqs_setlinks;   /* links from set perspective */
  78         unsigned int    wqs_refcount;   /* refcount for preposting */
  79 } WaitQueueSet;
  80
  81 #define wqs_type                wqs_wait_queue.wq_type
  82 #define wqs_fifo                wqs_wait_queue.wq_fifo
  83 #define wqs_isprepost   wqs_wait_queue.wq_isprepost
  84 #define wqs_queue               wqs_wait_queue.wq_queue
  85
  86 /*
  87  *      wait_queue_element_t
  88  *      This structure describes the elements on an event wait
  89  *      queue.  It is the common first fields in a thread shuttle
  90  *      and wait_queue_link_t.  In that way, a wait queue can
  91  *      consist of both thread shuttle elements and links off of
  92  *      to other (set) wait queues.
  93  *
  94  *      WARNING: These fields correspond to fields in the thread
  95  *      shuttle (run queue links and run queue pointer). Any change in
  96  *      the layout here will have to be matched with a change there.
  97  */
  98 typedef struct wait_queue_element {
  99         queue_chain_t   wqe_links;      /* link of elements on this queue */
 100         void *                  wqe_type;       /* Identifies link vs. thread */
 101         wait_queue_t    wqe_queue;      /* queue this element is on */
 102 } WaitQueueElement;
 103
 104 typedef WaitQueueElement *wait_queue_element_t;
 105
 106 /*
 107  *      wait_queue_link_t
 108  *      Specialized wait queue element type for linking set
 109  *      event waits queues onto a wait queue.  In this way, an event
 110  *      can be constructed so that any thread waiting on any number
 111  *      of associated wait queues can handle the event, while letting
 112  *      the thread only be linked on the single wait queue it blocked on.
 113  *
 114  *      One use: ports in multiple portsets.  Each thread is queued up
 115  *      on the portset that it specifically blocked on during a receive
 116  *      operation.  Each port's event queue links in all the portset
 117  *      event queues of which it is a member.  An IPC event post associated
 118  *      with that port may wake up any thread from any of those portsets,
 119  *      or one that was waiting locally on the port itself.
 120  */
 121 typedef struct wait_queue_link {
 122         WaitQueueElement                wql_element;    /* element on master */
 123         queue_chain_t                   wql_setlinks;   /* element on set */
 124     wait_queue_set_t            wql_setqueue;   /* set queue */
 125 } WaitQueueLink;
 126
 127 #define wql_links wql_element.wqe_links
 128 #define wql_type  wql_element.wqe_type
 129 #define wql_queue wql_element.wqe_queue
 130
 131 #define _WAIT_QUEUE_inited                      0xf1d0
 132 #define _WAIT_QUEUE_SET_inited          0xf1d1
 133
 134 #define wait_queue_is_queue(wq) \
 135         ((wq)->wq_type == _WAIT_QUEUE_inited)
 136
 137 #define wait_queue_is_set(wqs)  \
 138         ((wqs)->wqs_type == _WAIT_QUEUE_SET_inited)
 139
 140 #define wait_queue_is_valid(wq) \
 141         (((wq)->wq_type & ~1) == _WAIT_QUEUE_inited)
 142
 143 #define wait_queue_empty(wq)    (queue_empty(&(wq)->wq_queue))
 144 #define wait_queue_held(wq)             (hw_lock_held(&(wq)->wq_interlock))
 145 #define wait_queue_lock_try(wq) (hw_lock_try(&(wq)->wq_interlock))
 146
 147 /*
 148  * Double the standard lock timeout, because wait queues tend
 149  * to iterate over a number of threads - locking each.  If there is
 150  * a problem with a thread lock, it normally times out at the wait
 151  * queue level first, hiding the real problem.
 152  */
 153 #define wait_queue_lock(wq)     \
 154         ((void) (!hw_lock_to(&(wq)->wq_interlock, LockTimeOut * 2) ? \
 155                  panic("wait queue deadlock - wq=0x%x, cpu=%d\n", \
 156                        wq, cpu_number()) : 0))
 157
 158 #define wait_queue_unlock(wq) \
 159         (assert(wait_queue_held(wq)), hw_lock_unlock(&(wq)->wq_interlock))
 160
 161 #define wqs_lock(wqs)           wait_queue_lock(&(wqs)->wqs_wait_queue)
 162 #define wqs_unlock(wqs)         wait_queue_unlock(&(wqs)->wqs_wait_queue)
 163 #define wqs_lock_try(wqs)       wait_queue__try_lock(&(wqs)->wqs_wait_queue)
 164
 165 #define wait_queue_assert_possible(thread) \
 166                         ((thread)->wait_queue == WAIT_QUEUE_NULL)
 167
 168 /******** Decomposed interfaces (to build higher level constructs) ***********/
 169
 170 /* assert intent to wait on a locked wait queue */
 171 __private_extern__ wait_result_t wait_queue_assert_wait64_locked(
 172                         wait_queue_t wait_queue,
 173                         event64_t wait_event,
 174                         wait_interrupt_t interruptible,
 175                         boolean_t unlock);
 176
 177 /* peek to see which thread would be chosen for a wakeup - but keep on queue */
 178 __private_extern__ void wait_queue_peek64_locked(
 179                         wait_queue_t wait_queue,
 180                         event64_t event,
 181                         thread_t *thread,
 182                         wait_queue_t *found_queue);
 183
 184 /* peek to see which thread would be chosen for a wakeup - but keep on queue */
 185 __private_extern__ void wait_queue_pull_thread_locked(
 186                         wait_queue_t wait_queue,
 187                         thread_t thread,
 188                         boolean_t unlock);
 189
 190 /* wakeup all threads waiting for a particular event on locked queue */
 191 __private_extern__ kern_return_t wait_queue_wakeup64_all_locked(
 192                         wait_queue_t wait_queue,
 193                         event64_t wake_event,
 194                         wait_result_t result,
 195                         boolean_t unlock);
 196
 197 /* wakeup one thread waiting for a particular event on locked queue */
 198 __private_extern__ kern_return_t wait_queue_wakeup64_one_locked(
 199                         wait_queue_t wait_queue,
 200                         event64_t wake_event,
 201                         wait_result_t result,
 202                         boolean_t unlock);
 203
 204 /* return identity of a thread awakened for a particular <wait_queue,event> */
 205 __private_extern__ thread_t wait_queue_wakeup64_identity_locked(
 206                         wait_queue_t wait_queue,
 207                         event64_t wake_event,
 208                         wait_result_t result,
 209                         boolean_t unlock);
 210
 211 /* wakeup thread iff its still waiting for a particular event on locked queue */
 212 __private_extern__ kern_return_t wait_queue_wakeup64_thread_locked(
 213                         wait_queue_t wait_queue,
 214                         event64_t wake_event,
 215                         thread_t thread,
 216                         wait_result_t result,
 217                         boolean_t unlock);
 218
 219 #endif /* MACH_KERNEL_PRIVATE */
 220
 221 #ifdef __APPLE_API_UNSTABLE
 222 /******** Semi-Public interfaces (not a part of a higher construct) ************/
 223
 224 extern kern_return_t wait_queue_init(
 225                         wait_queue_t wait_queue,
 226                         int policy);
 227
 228 extern wait_queue_set_t wait_queue_set_alloc(
 229                         int policy);
 230
 231 extern kern_return_t wait_queue_set_free(
 232                         wait_queue_set_t set_queue);
 233
 234 extern wait_queue_link_t wait_queue_link_alloc(
 235                         int policy);
 236
 237 extern kern_return_t wait_queue_link_free(
 238                         wait_queue_link_t link_element);
 239
 240 #endif /* __APPLE_API_UNSTABLE */
 241
 242 #ifdef __APPLE_API_EVOLVING
 243
 244 extern wait_queue_t wait_queue_alloc(
 245                         int policy);
 246
 247 extern kern_return_t wait_queue_free(
 248                         wait_queue_t wait_queue);
 249
 250 extern kern_return_t wait_queue_link(
 251                         wait_queue_t wait_queue,
 252                         wait_queue_set_t set_queue);
 253
 254 extern kern_return_t wait_queue_unlink(
 255                         wait_queue_t wait_queue,
 256                         wait_queue_set_t set_queue);
 257
 258 extern kern_return_t wait_queue_unlink_all(
 259                         wait_queue_t wait_queue);
 260
 261 extern kern_return_t wait_queue_set_unlink_all(
 262                         wait_queue_set_t set_queue);
 263
 264 /* assert intent to wait on <wait_queue,event64> pair */
 265 extern wait_result_t wait_queue_assert_wait64(
 266                         wait_queue_t wait_queue,
 267                         event64_t wait_event,
 268                         wait_interrupt_t interruptible);
 269
 270 /* wakeup the most appropriate thread waiting on <wait_queue,event64> pair */
 271 extern kern_return_t wait_queue_wakeup64_one(
 272                         wait_queue_t wait_queue,
 273                         event64_t wake_event,
 274                         wait_result_t result);
 275
 276 /* wakeup all the threads waiting on <wait_queue,event64> pair */
 277 extern kern_return_t wait_queue_wakeup64_all(
 278                         wait_queue_t wait_queue,
 279                         event64_t wake_event,
 280                         wait_result_t result);
 281
 282 /* wakeup a specified thread waiting iff waiting on <wait_queue,event64> pair */
 283 extern kern_return_t wait_queue_wakeup64_thread(
 284                         wait_queue_t wait_queue,
 285                         event64_t wake_event,
 286                         thread_t thread,
 287                         wait_result_t result);
 288
 289 #endif  /* __APPLE_API_EVOLVING */
 290
 291 /*
 292  * Compatibility Wait Queue APIs based on pointer events instead of 64bit
 293  * integer events.
 294  */
 295
 296 /* assert intent to wait on <wait_queue,event> pair */
 297 extern wait_result_t wait_queue_assert_wait(
 298                         wait_queue_t wait_queue,
 299                         event_t wait_event,
 300                         wait_interrupt_t interruptible);
 301
 302 /* wakeup the most appropriate thread waiting on <wait_queue,event> pair */
 303 extern kern_return_t wait_queue_wakeup_one(
 304                         wait_queue_t wait_queue,
 305                         event_t wake_event,
 306                         wait_result_t result);
 307
 308 /* wakeup all the threads waiting on <wait_queue,event> pair */
 309 extern kern_return_t wait_queue_wakeup_all(
 310                         wait_queue_t wait_queue,
 311                         event_t wake_event,
 312                         wait_result_t result);
 313
 314 /* wakeup a specified thread waiting iff waiting on <wait_queue,event> pair */
 315 extern kern_return_t wait_queue_wakeup_thread(
 316                         wait_queue_t wait_queue,
 317                         event_t wake_event,
 318                         thread_t thread,
 319                         wait_result_t result);
 320
 321 #endif  /* __APPLE_API_PRIVATE */
 322
 323 #endif /* _KERN_WAIT_QUEUE_H_ */