/* * Copyright (c) 2000-2005 Apple Computer, Inc. All rights reserved. * * @APPLE_OSREFERENCE_LICENSE_HEADER_START@ * * This file contains Original Code and/or Modifications of Original Code * as defined in and that are subject to the Apple Public Source License * Version 2.0 (the 'License'). You may not use this file except in * compliance with the License. The rights granted to you under the License * may not be used to create, or enable the creation or redistribution of, * unlawful or unlicensed copies of an Apple operating system, or to * circumvent, violate, or enable the circumvention or violation of, any * terms of an Apple operating system software license agreement. * * Please obtain a copy of the License at * http://www.opensource.apple.com/apsl/ and read it before using this file. * * The Original Code and all software distributed under the License are * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. * Please see the License for the specific language governing rights and * limitations under the License. * * @APPLE_OSREFERENCE_LICENSE_HEADER_END@ */ #ifdef KERNEL_PRIVATE #ifndef _KERN_WAIT_QUEUE_H_ #define _KERN_WAIT_QUEUE_H_ #include #include #include /* for kern_return_t */ #include /* for wait_queue_t */ #include #include #ifdef MACH_KERNEL_PRIVATE #include #include #include #include /* machine_timeout_suspended() */ /* * wait_queue_t * This is the definition of the common event wait queue * that the scheduler APIs understand. It is used * internally by the gerneralized event waiting mechanism * (assert_wait), and also for items that maintain their * own wait queues (such as ports and semaphores). * * It is not published to other kernel components. They * can create wait queues by calling wait_queue_alloc. * * NOTE: Hardware locks are used to protect event wait * queues since interrupt code is free to post events to * them. */ typedef struct wait_queue { unsigned int /* flags */ /* boolean_t */ wq_type:16, /* only public field */ wq_fifo:1, /* fifo wakeup policy? */ wq_prepost:1, /* waitq supports prepost? set only */ :0; /* force to long boundary */ hw_lock_data_t wq_interlock; /* interlock */ queue_head_t wq_queue; /* queue of elements */ } WaitQueue; /* * wait_queue_set_t * This is the common definition for a set wait queue. * These can be linked as members/elements of multiple regular * wait queues. They have an additional set of linkages to * identify the linkage structures that point to them. */ typedef struct wait_queue_set { WaitQueue wqs_wait_queue; /* our wait queue */ queue_head_t wqs_setlinks; /* links from set perspective */ queue_head_t wqs_preposts; /* preposted links */ } WaitQueueSet; #define wqs_type wqs_wait_queue.wq_type #define wqs_fifo wqs_wait_queue.wq_fifo #define wqs_prepost wqs_wait_queue.wq_prepost #define wqs_queue wqs_wait_queue.wq_queue /* * wait_queue_element_t * This structure describes the elements on an event wait * queue. It is the common first fields in a thread shuttle * and wait_queue_link_t. In that way, a wait queue can * consist of both thread shuttle elements and links off of * to other (set) wait queues. * * WARNING: These fields correspond to fields in the thread * shuttle (run queue links and run queue pointer). Any change in * the layout here will have to be matched with a change there. */ typedef struct wait_queue_element { queue_chain_t wqe_links; /* link of elements on this queue */ void * wqe_type; /* Identifies link vs. thread */ wait_queue_t wqe_queue; /* queue this element is on */ } WaitQueueElement; typedef WaitQueueElement *wait_queue_element_t; /* * wait_queue_link_t * Specialized wait queue element type for linking set * event waits queues onto a wait queue. In this way, an event * can be constructed so that any thread waiting on any number * of associated wait queues can handle the event, while letting * the thread only be linked on the single wait queue it blocked on. * * One use: ports in multiple portsets. Each thread is queued up * on the portset that it specifically blocked on during a receive * operation. Each port's event queue links in all the portset * event queues of which it is a member. An IPC event post associated * with that port may wake up any thread from any of those portsets, * or one that was waiting locally on the port itself. */ typedef struct _wait_queue_link { WaitQueueElement wql_element; /* element on master */ queue_chain_t wql_setlinks; /* element on set */ queue_chain_t wql_preposts; /* element on set prepost list */ wait_queue_set_t wql_setqueue; /* set queue */ } WaitQueueLink; #define wql_links wql_element.wqe_links #define wql_type wql_element.wqe_type #define wql_queue wql_element.wqe_queue #define _WAIT_QUEUE_inited 0xf1d0 #define _WAIT_QUEUE_SET_inited 0xf1d1 #define wait_queue_is_queue(wq) \ ((wq)->wq_type == _WAIT_QUEUE_inited) #define wait_queue_is_set(wqs) \ ((wqs)->wqs_type == _WAIT_QUEUE_SET_inited) #define wait_queue_is_valid(wq) \ (((wq)->wq_type & ~1) == _WAIT_QUEUE_inited) #define wait_queue_empty(wq) (queue_empty(&(wq)->wq_queue)) #define wait_queue_held(wq) (hw_lock_held(&(wq)->wq_interlock)) #define wait_queue_lock_try(wq) (hw_lock_try(&(wq)->wq_interlock)) /* For x86, the hardware timeout is in TSC units. */ #if defined(i386) || defined(x86_64) #define hwLockTimeOut LockTimeOutTSC #else #define hwLockTimeOut LockTimeOut #endif /* * Double the standard lock timeout, because wait queues tend * to iterate over a number of threads - locking each. If there is * a problem with a thread lock, it normally times out at the wait * queue level first, hiding the real problem. */ static inline void wait_queue_lock(wait_queue_t wq) { if (__improbable(hw_lock_to(&(wq)->wq_interlock, hwLockTimeOut * 2) == 0)) { boolean_t wql_acquired = FALSE; while (machine_timeout_suspended()) { #if defined(__i386__) || defined(__x86_64__) /* * i386/x86_64 return with preemption disabled on a timeout for * diagnostic purposes. */ mp_enable_preemption(); #endif if ((wql_acquired = hw_lock_to(&(wq)->wq_interlock, hwLockTimeOut * 2))) break; } if (wql_acquired == FALSE) panic("wait queue deadlock - wq=%p, cpu=%d\n", wq, cpu_number()); } } static inline void wait_queue_unlock(wait_queue_t wq) { assert(wait_queue_held(wq)); hw_lock_unlock(&(wq)->wq_interlock); } #define wqs_lock(wqs) wait_queue_lock(&(wqs)->wqs_wait_queue) #define wqs_unlock(wqs) wait_queue_unlock(&(wqs)->wqs_wait_queue) #define wqs_lock_try(wqs) wait_queue__try_lock(&(wqs)->wqs_wait_queue) #define wqs_is_preposted(wqs) ((wqs)->wqs_prepost && !queue_empty(&(wqs)->wqs_preposts)) #define wql_is_preposted(wql) ((wql)->wql_preposts.next != NULL) #define wql_clear_prepost(wql) ((wql)->wql_preposts.next = (wql)->wql_preposts.prev = NULL) #define wait_queue_assert_possible(thread) \ ((thread)->wait_queue == WAIT_QUEUE_NULL) /* bootstrap interface - can allocate/link wait_queues and sets after calling this */ __private_extern__ void wait_queue_bootstrap(void); /******** Decomposed interfaces (to build higher level constructs) ***********/ /* assert intent to wait on a locked wait queue */ __private_extern__ wait_result_t wait_queue_assert_wait64_locked( wait_queue_t wait_queue, event64_t wait_event, wait_interrupt_t interruptible, uint64_t deadline, thread_t thread); /* pull a thread from its wait queue */ __private_extern__ void wait_queue_pull_thread_locked( wait_queue_t wait_queue, thread_t thread, boolean_t unlock); /* wakeup all threads waiting for a particular event on locked queue */ __private_extern__ kern_return_t wait_queue_wakeup64_all_locked( wait_queue_t wait_queue, event64_t wake_event, wait_result_t result, boolean_t unlock); /* wakeup one thread waiting for a particular event on locked queue */ __private_extern__ kern_return_t wait_queue_wakeup64_one_locked( wait_queue_t wait_queue, event64_t wake_event, wait_result_t result, boolean_t unlock); /* return identity of a thread awakened for a particular */ __private_extern__ thread_t wait_queue_wakeup64_identity_locked( wait_queue_t wait_queue, event64_t wake_event, wait_result_t result, boolean_t unlock); /* wakeup thread iff its still waiting for a particular event on locked queue */ __private_extern__ kern_return_t wait_queue_wakeup64_thread_locked( wait_queue_t wait_queue, event64_t wake_event, thread_t thread, wait_result_t result, boolean_t unlock); __private_extern__ uint32_t num_wait_queues; __private_extern__ struct wait_queue *wait_queues; /* The Jenkins "one at a time" hash. * TBD: There may be some value to unrolling here, * depending on the architecture. */ static inline uint32_t wq_hash(char *key) { uint32_t hash = 0; size_t i, length = sizeof(char *); for (i = 0; i < length; i++) { hash += key[i]; hash += (hash << 10); hash ^= (hash >> 6); } hash += (hash << 3); hash ^= (hash >> 11); hash += (hash << 15); hash &= (num_wait_queues - 1); return hash; } #define wait_hash(event) wq_hash((char *)&event) #endif /* MACH_KERNEL_PRIVATE */ __BEGIN_DECLS /******** Semi-Public interfaces (not a part of a higher construct) ************/ extern unsigned int wait_queue_set_size(void); extern unsigned int wait_queue_link_size(void); extern kern_return_t wait_queue_init( wait_queue_t wait_queue, int policy); extern wait_queue_set_t wait_queue_set_alloc( int policy); extern kern_return_t wait_queue_set_init( wait_queue_set_t set_queue, int policy); extern kern_return_t wait_queue_set_free( wait_queue_set_t set_queue); extern wait_queue_link_t wait_queue_link_alloc( int policy); extern kern_return_t wait_queue_link_free( wait_queue_link_t link_element); extern kern_return_t wait_queue_link( wait_queue_t wait_queue, wait_queue_set_t set_queue); extern kern_return_t wait_queue_link_noalloc( wait_queue_t wait_queue, wait_queue_set_t set_queue, wait_queue_link_t link); extern boolean_t wait_queue_member( wait_queue_t wait_queue, wait_queue_set_t set_queue); extern kern_return_t wait_queue_unlink( wait_queue_t wait_queue, wait_queue_set_t set_queue); extern kern_return_t wait_queue_unlink_all( wait_queue_t wait_queue); extern kern_return_t wait_queue_set_unlink_all( wait_queue_set_t set_queue); #ifdef XNU_KERNEL_PRIVATE extern kern_return_t wait_queue_set_unlink_one( wait_queue_set_t set_queue, wait_queue_link_t link); extern kern_return_t wait_queue_unlink_nofree( wait_queue_t wait_queue, wait_queue_set_t set_queue, wait_queue_link_t *wqlp); extern kern_return_t wait_queue_unlink_all_nofree( wait_queue_t wait_queue, queue_t links); extern kern_return_t wait_queue_set_unlink_all_nofree( wait_queue_set_t set_queue, queue_t links); extern wait_queue_link_t wait_queue_link_allocate(void); #endif /* XNU_KERNEL_PRIVATE */ /* legacy API */ kern_return_t wait_queue_sub_init( wait_queue_set_t set_queue, int policy); kern_return_t wait_queue_sub_clearrefs( wait_queue_set_t wq_set); extern kern_return_t wait_subqueue_unlink_all( wait_queue_set_t set_queue); extern wait_queue_t wait_queue_alloc( int policy); extern kern_return_t wait_queue_free( wait_queue_t wait_queue); /* assert intent to wait on pair */ extern wait_result_t wait_queue_assert_wait64( wait_queue_t wait_queue, event64_t wait_event, wait_interrupt_t interruptible, uint64_t deadline); /* wakeup the most appropriate thread waiting on pair */ extern kern_return_t wait_queue_wakeup64_one( wait_queue_t wait_queue, event64_t wake_event, wait_result_t result); /* wakeup all the threads waiting on pair */ extern kern_return_t wait_queue_wakeup64_all( wait_queue_t wait_queue, event64_t wake_event, wait_result_t result); /* wakeup a specified thread waiting iff waiting on pair */ extern kern_return_t wait_queue_wakeup64_thread( wait_queue_t wait_queue, event64_t wake_event, thread_t thread, wait_result_t result); /* * Compatibility Wait Queue APIs based on pointer events instead of 64bit * integer events. */ /* assert intent to wait on pair */ extern wait_result_t wait_queue_assert_wait( wait_queue_t wait_queue, event_t wait_event, wait_interrupt_t interruptible, uint64_t deadline); /* wakeup the most appropriate thread waiting on pair */ extern kern_return_t wait_queue_wakeup_one( wait_queue_t wait_queue, event_t wake_event, wait_result_t result, int priority); /* wakeup all the threads waiting on pair */ extern kern_return_t wait_queue_wakeup_all( wait_queue_t wait_queue, event_t wake_event, wait_result_t result); /* wakeup a specified thread waiting iff waiting on pair */ extern kern_return_t wait_queue_wakeup_thread( wait_queue_t wait_queue, event_t wake_event, thread_t thread, wait_result_t result); __END_DECLS #endif /* _KERN_WAIT_QUEUE_H_ */ #endif /* KERNEL_PRIVATE */