osfmk/kern/wait_queue.h

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