osfmk/kern/wait_queue.h

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