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 #define wait_queue_held(wq)             (hw_lock_held(&(wq)->wq_interlock))
 150 #define wait_queue_lock_try(wq) (hw_lock_try(&(wq)->wq_interlock))
 151
 152 /*
 153  * Double the standard lock timeout, because wait queues tend
 154  * to iterate over a number of threads - locking each.  If there is
 155  * a problem with a thread lock, it normally times out at the wait
 156  * queue level first, hiding the real problem.
 157  */
 158 #define wait_queue_lock(wq)     \
 159         ((void) (!hw_lock_to(&(wq)->wq_interlock, LockTimeOut * 2) ? \
 160                  panic("wait queue deadlock - wq=0x%x, cpu=%d\n", \
 161                        wq, cpu_number()) : 0))
 162
 163 #define wait_queue_unlock(wq) \
 164         (assert(wait_queue_held(wq)), hw_lock_unlock(&(wq)->wq_interlock))
 165
 166 #define wqs_lock(wqs)           wait_queue_lock(&(wqs)->wqs_wait_queue)
 167 #define wqs_unlock(wqs)         wait_queue_unlock(&(wqs)->wqs_wait_queue)
 168 #define wqs_lock_try(wqs)       wait_queue__try_lock(&(wqs)->wqs_wait_queue)
 169
 170 #define wait_queue_assert_possible(thread) \
 171                         ((thread)->wait_queue == WAIT_QUEUE_NULL)
 172
 173 /******** Decomposed interfaces (to build higher level constructs) ***********/
 174
 175 /* assert intent to wait on a locked wait queue */
 176 __private_extern__ wait_result_t wait_queue_assert_wait64_locked(
 177                         wait_queue_t wait_queue,
 178                         event64_t wait_event,
 179                         wait_interrupt_t interruptible,
 180                         uint64_t deadline,
 181                         thread_t thread);
 182
 183 /* peek to see which thread would be chosen for a wakeup - but keep on queue */
 184 __private_extern__ void wait_queue_peek64_locked(
 185                         wait_queue_t wait_queue,
 186                         event64_t event,
 187                         thread_t *thread,
 188                         wait_queue_t *found_queue);
 189
 190 /* peek to see which thread would be chosen for a wakeup - but keep on queue */
 191 __private_extern__ void wait_queue_pull_thread_locked(
 192                         wait_queue_t wait_queue,
 193                         thread_t thread,
 194                         boolean_t unlock);
 195
 196 /* wakeup all threads waiting for a particular event on locked queue */
 197 __private_extern__ kern_return_t wait_queue_wakeup64_all_locked(
 198                         wait_queue_t wait_queue,
 199                         event64_t wake_event,
 200                         wait_result_t result,
 201                         boolean_t unlock);
 202
 203 /* wakeup one thread waiting for a particular event on locked queue */
 204 __private_extern__ kern_return_t wait_queue_wakeup64_one_locked(
 205                         wait_queue_t wait_queue,
 206                         event64_t wake_event,
 207                         wait_result_t result,
 208                         boolean_t unlock);
 209
 210 /* return identity of a thread awakened for a particular <wait_queue,event> */
 211 __private_extern__ thread_t wait_queue_wakeup64_identity_locked(
 212                         wait_queue_t wait_queue,
 213                         event64_t wake_event,
 214                         wait_result_t result,
 215                         boolean_t unlock);
 216
 217 /* wakeup thread iff its still waiting for a particular event on locked queue */
 218 __private_extern__ kern_return_t wait_queue_wakeup64_thread_locked(
 219                         wait_queue_t wait_queue,
 220                         event64_t wake_event,
 221                         thread_t thread,
 222                         wait_result_t result,
 223                         boolean_t unlock);
 224
 225 #endif  /* MACH_KERNEL_PRIVATE */
 226
 227 __BEGIN_DECLS
 228
 229 /******** Semi-Public interfaces (not a part of a higher construct) ************/
 230
 231 extern unsigned int wait_queue_set_size(void);
 232 extern unsigned int wait_queue_link_size(void);
 233
 234 extern kern_return_t wait_queue_init(
 235                         wait_queue_t wait_queue,
 236                         int policy);
 237
 238 extern wait_queue_set_t wait_queue_set_alloc(
 239                         int policy);
 240
 241 extern kern_return_t wait_queue_set_init(
 242                         wait_queue_set_t set_queue,
 243                         int policy);
 244
 245 extern kern_return_t wait_queue_set_free(
 246                         wait_queue_set_t set_queue);
 247
 248 extern wait_queue_link_t wait_queue_link_alloc(
 249                         int policy);
 250
 251 extern kern_return_t wait_queue_link_free(
 252                         wait_queue_link_t link_element);
 253
 254 extern kern_return_t wait_queue_link(
 255                         wait_queue_t wait_queue,
 256                         wait_queue_set_t set_queue);
 257
 258 extern kern_return_t wait_queue_link_noalloc(
 259                         wait_queue_t wait_queue,
 260                         wait_queue_set_t set_queue,
 261                         wait_queue_link_t link);
 262
 263 extern boolean_t wait_queue_member(
 264                         wait_queue_t wait_queue,
 265                         wait_queue_set_t set_queue);
 266
 267 extern kern_return_t wait_queue_unlink(
 268                         wait_queue_t wait_queue,
 269                         wait_queue_set_t set_queue);
 270
 271 extern kern_return_t wait_queue_unlink_all(
 272                         wait_queue_t wait_queue);
 273
 274 extern kern_return_t wait_queue_unlinkall_nofree(
 275                         wait_queue_t wait_queue);
 276
 277 extern kern_return_t wait_queue_set_unlink_all(
 278                         wait_queue_set_t set_queue);
 279
 280 /* legacy API */
 281 kern_return_t wait_queue_sub_init(
 282                         wait_queue_set_t set_queue,
 283                         int policy);
 284
 285 kern_return_t wait_queue_sub_clearrefs(
 286                         wait_queue_set_t wq_set);
 287
 288 extern kern_return_t wait_subqueue_unlink_all(
 289                         wait_queue_set_t set_queue);
 290
 291 extern wait_queue_t wait_queue_alloc(
 292                         int policy);
 293
 294 extern kern_return_t wait_queue_free(
 295                         wait_queue_t wait_queue);
 296
 297 /* assert intent to wait on <wait_queue,event64> pair */
 298 extern wait_result_t wait_queue_assert_wait64(
 299                         wait_queue_t wait_queue,
 300                         event64_t wait_event,
 301                         wait_interrupt_t interruptible,
 302                         uint64_t deadline);
 303
 304 /* wakeup the most appropriate thread waiting on <wait_queue,event64> pair */
 305 extern kern_return_t wait_queue_wakeup64_one(
 306                         wait_queue_t wait_queue,
 307                         event64_t wake_event,
 308                         wait_result_t result);
 309
 310 /* wakeup all the threads waiting on <wait_queue,event64> pair */
 311 extern kern_return_t wait_queue_wakeup64_all(
 312                         wait_queue_t wait_queue,
 313                         event64_t wake_event,
 314                         wait_result_t result);
 315
 316 /* wakeup a specified thread waiting iff waiting on <wait_queue,event64> pair */
 317 extern kern_return_t wait_queue_wakeup64_thread(
 318                         wait_queue_t wait_queue,
 319                         event64_t wake_event,
 320                         thread_t thread,
 321                         wait_result_t result);
 322
 323 /*
 324  * Compatibility Wait Queue APIs based on pointer events instead of 64bit
 325  * integer events.
 326  */
 327
 328 /* assert intent to wait on <wait_queue,event> pair */
 329 extern wait_result_t wait_queue_assert_wait(
 330                         wait_queue_t wait_queue,
 331                         event_t wait_event,
 332                         wait_interrupt_t interruptible,
 333                         uint64_t deadline);
 334
 335 /* wakeup the most appropriate thread waiting on <wait_queue,event> pair */
 336 extern kern_return_t wait_queue_wakeup_one(
 337                         wait_queue_t wait_queue,
 338                         event_t wake_event,
 339                         wait_result_t result);
 340
 341 /* wakeup all the threads waiting on <wait_queue,event> pair */
 342 extern kern_return_t wait_queue_wakeup_all(
 343                         wait_queue_t wait_queue,
 344                         event_t wake_event,
 345                         wait_result_t result);
 346
 347 /* wakeup a specified thread waiting iff waiting on <wait_queue,event> pair */
 348 extern kern_return_t wait_queue_wakeup_thread(
 349                         wait_queue_t wait_queue,
 350                         event_t wake_event,
 351                         thread_t thread,
 352                         wait_result_t result);
 353
 354 __END_DECLS
 355
 356 #endif  /* _KERN_WAIT_QUEUE_H_ */
 357
 358 #endif  /* KERNEL_PRIVATE */