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 */ 63typedef 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 */ 80typedef 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 */ 103typedef 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 109typedef 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 */ 126typedef 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 166static 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 172static 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 243extern unsigned int wait_queue_set_size(void); 244extern unsigned int wait_queue_link_size(void); 245 246extern kern_return_t wait_queue_init( 247 wait_queue_t wait_queue, 248 int policy); 249 250extern wait_queue_set_t wait_queue_set_alloc( 251 int policy); 252 253extern kern_return_t wait_queue_set_init( 254 wait_queue_set_t set_queue, 255 int policy); 256 257extern kern_return_t wait_queue_set_free( 258 wait_queue_set_t set_queue); 259 260extern wait_queue_link_t wait_queue_link_alloc( 261 int policy); 262 263extern kern_return_t wait_queue_link_free( 264 wait_queue_link_t link_element); 265 266extern kern_return_t wait_queue_link( 267 wait_queue_t wait_queue, 268 wait_queue_set_t set_queue); 269 270extern 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 275extern boolean_t wait_queue_member( 276 wait_queue_t wait_queue, 277 wait_queue_set_t set_queue); 278 279extern kern_return_t wait_queue_unlink( 280 wait_queue_t wait_queue, 281 wait_queue_set_t set_queue); 282 283extern kern_return_t wait_queue_unlink_all( 284 wait_queue_t wait_queue); 285 286extern kern_return_t wait_queue_unlinkall_nofree( 287 wait_queue_t wait_queue); 288 289extern kern_return_t wait_queue_set_unlink_all( 290 wait_queue_set_t set_queue); 291 292/* legacy API */ 293kern_return_t wait_queue_sub_init( 294 wait_queue_set_t set_queue, 295 int policy); 296 297kern_return_t wait_queue_sub_clearrefs( 298 wait_queue_set_t wq_set); 299 300extern kern_return_t wait_subqueue_unlink_all( 301 wait_queue_set_t set_queue); 302 303extern wait_queue_t wait_queue_alloc( 304 int policy); 305 306extern kern_return_t wait_queue_free( 307 wait_queue_t wait_queue); 308 309/* assert intent to wait on <wait_queue,event64> pair */ 310extern 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 */ 317extern 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 */ 323extern 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 */ 329extern 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 */ 341extern 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 */ 348extern 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 */ 354extern 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 */ 360extern 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 */ 371