[apple/xnu.git] / osfmk / kern / wait_queue.h

/*
 * 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 <mach/mach_types.h>
#include <mach/sync_policy.h>
#include <mach/kern_return.h>		/* for kern_return_t */

#include <kern/kern_types.h>		/* for wait_queue_t */
#include <kern/queue.h>

#include <sys/cdefs.h>

#ifdef	MACH_KERNEL_PRIVATE

#include <kern/lock.h>
#include <mach/branch_predicates.h>

#include <machine/cpu_number.h>
#include <machine/machine_routines.h> /* machine_timeout_suspended() */

/*
 * The event mask is of 60 bits on 64 bit architeture and 28 bits on
 * 32 bit architecture and so we calculate its size using sizeof(long).
 * If the bitfield for wq_type and wq_fifo is changed, then value of 
 * EVENT_MASK_BITS will also change. 
 */
#define EVENT_MASK_BITS  ((sizeof(long) * 8) - 4)

/*
 * Zero out the 4 msb of the event.
 */
#define CAST_TO_EVENT_MASK(event)  (((CAST_DOWN(unsigned long, event)) << 4) >> 4)
/*
 *	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 long int                    /* flags */
    /* boolean_t */	wq_type:2,		/* only public field */
					wq_fifo:1,		/* fifo wakeup policy? */
					wq_prepost:1,	/* waitq supports prepost? set only */
					wq_eventmask:EVENT_MASK_BITS; 
    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		0x2
#define _WAIT_QUEUE_SET_inited		0x3

#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());
	}
	assert(wait_queue_held(wq));
}

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,
			wait_timeout_urgency_t urgency,
			uint64_t deadline,
			uint64_t leeway,
			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 <wait_queue,event> */
__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);

extern uint32_t num_wait_queues;
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 <wait_queue,event64> 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);

extern wait_result_t wait_queue_assert_wait64_with_leeway(
			wait_queue_t wait_queue,
			event64_t wait_event,
			wait_interrupt_t interruptible,
			wait_timeout_urgency_t urgency,
			uint64_t deadline,
			uint64_t leeway);

/* wakeup the most appropriate thread waiting on <wait_queue,event64> 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 <wait_queue,event64> 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 <wait_queue,event64> 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 <wait_queue,event> 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);

/* assert intent to wait on <wait_queue,event> pair */
extern wait_result_t wait_queue_assert_wait_with_leeway(
			wait_queue_t wait_queue,
			event_t wait_event,
			wait_interrupt_t interruptible,
			wait_timeout_urgency_t urgency,
			uint64_t deadline,
			uint64_t leeway);

/* wakeup the most appropriate thread waiting on <wait_queue,event> 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 <wait_queue,event> 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 <wait_queue,event> 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 */
Commit	Line	Data
1c79356b	1	/*
91447636	2	* Copyright (c) 2000-2005 Apple Computer, Inc. All rights reserved.
1c79356b	3	*
2d21ac55	4	* @APPLE_OSREFERENCE_LICENSE_HEADER_START@
1c79356b	5	*
2d21ac55 A	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.
8f6c56a5	14	*
2d21ac55 A	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
8f6c56a5 A	20	* EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
8f6c56a5 A	21	* INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
2d21ac55 A	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.
8f6c56a5	25	*
2d21ac55	26	* @APPLE_OSREFERENCE_LICENSE_HEADER_END@
1c79356b	27	*/
1c79356b	28
91447636	29	#ifdef KERNEL_PRIVATE
9bccf70c	30
91447636 A	31	#ifndef _KERN_WAIT_QUEUE_H_
91447636 A	32	#define _KERN_WAIT_QUEUE_H_
9bccf70c	33
91447636	34	#include <mach/mach_types.h>
1c79356b	35	#include <mach/sync_policy.h>
0b4e3aa0	36	#include <mach/kern_return.h> /* for kern_return_t */
1c79356b	37
9bccf70c	38	#include <kern/kern_types.h> /* for wait_queue_t */
316670eb	39	#include <kern/queue.h>
9bccf70c	40
91447636 A	41	#include <sys/cdefs.h>
	42
	43	#ifdef MACH_KERNEL_PRIVATE
1c79356b A	44
1c79356b A	45	#include <kern/lock.h>
6d2010ae	46	#include <mach/branch_predicates.h>
9bccf70c	47
060df5ea A	48	#include <machine/cpu_number.h>
060df5ea A	49	#include <machine/machine_routines.h> /* machine_timeout_suspended() */
39236c6e A	50
	51	/*
	52	* The event mask is of 60 bits on 64 bit architeture and 28 bits on
	53	* 32 bit architecture and so we calculate its size using sizeof(long).
	54	* If the bitfield for wq_type and wq_fifo is changed, then value of
	55	* EVENT_MASK_BITS will also change.
	56	*/
	57	#define EVENT_MASK_BITS ((sizeof(long) * 8) - 4)
	58
	59	/*
	60	* Zero out the 4 msb of the event.
	61	*/
	62	#define CAST_TO_EVENT_MASK(event) (((CAST_DOWN(unsigned long, event)) << 4) >> 4)
1c79356b A	63	/*
	64	* wait_queue_t
	65	* This is the definition of the common event wait queue
	66	* that the scheduler APIs understand. It is used
	67	* internally by the gerneralized event waiting mechanism
	68	* (assert_wait), and also for items that maintain their
	69	* own wait queues (such as ports and semaphores).
	70	*
	71	* It is not published to other kernel components. They
	72	* can create wait queues by calling wait_queue_alloc.
	73	*
	74	* NOTE: Hardware locks are used to protect event wait
	75	* queues since interrupt code is free to post events to
	76	* them.
	77	*/
	78	typedef struct wait_queue {
39236c6e A	79	unsigned long int /* flags */
39236c6e A	80	/* boolean_t / wq_type:2, / only public field */
9bccf70c	81	wq_fifo:1, /* fifo wakeup policy? */
b0d623f7	82	wq_prepost:1, /* waitq supports prepost? set only */
39236c6e	83	wq_eventmask:EVENT_MASK_BITS;
1c79356b	84	hw_lock_data_t wq_interlock; /* interlock */
9bccf70c	85	queue_head_t wq_queue; /* queue of elements */
1c79356b A	86	} WaitQueue;
	87
	88	/*
9bccf70c A	89	* wait_queue_set_t
9bccf70c A	90	* This is the common definition for a set wait queue.
1c79356b A	91	* These can be linked as members/elements of multiple regular
	92	* wait queues. They have an additional set of linkages to
	93	* identify the linkage structures that point to them.
	94	*/
9bccf70c A	95	typedef struct wait_queue_set {
	96	WaitQueue wqs_wait_queue; /* our wait queue */
	97	queue_head_t wqs_setlinks; /* links from set perspective */
b0d623f7	98	queue_head_t wqs_preposts; /* preposted links */
9bccf70c	99	} WaitQueueSet;
1c79356b	100
9bccf70c A	101	#define wqs_type wqs_wait_queue.wq_type
9bccf70c A	102	#define wqs_fifo wqs_wait_queue.wq_fifo
b0d623f7	103	#define wqs_prepost wqs_wait_queue.wq_prepost
9bccf70c	104	#define wqs_queue wqs_wait_queue.wq_queue
1c79356b A	105
	106	/*
	107	* wait_queue_element_t
	108	* This structure describes the elements on an event wait
	109	* queue. It is the common first fields in a thread shuttle
	110	* and wait_queue_link_t. In that way, a wait queue can
	111	* consist of both thread shuttle elements and links off of
9bccf70c	112	* to other (set) wait queues.
1c79356b	113	*
9bccf70c A	114	* WARNING: These fields correspond to fields in the thread
9bccf70c A	115	* shuttle (run queue links and run queue pointer). Any change in
1c79356b A	116	* the layout here will have to be matched with a change there.
	117	*/
	118	typedef struct wait_queue_element {
	119	queue_chain_t wqe_links; /* link of elements on this queue */
9bccf70c	120	void * wqe_type; /* Identifies link vs. thread */
1c79356b	121	wait_queue_t wqe_queue; /* queue this element is on */
9bccf70c	122	} WaitQueueElement;
1c79356b	123
9bccf70c	124	typedef WaitQueueElement *wait_queue_element_t;
0b4e3aa0	125
1c79356b A	126	/*
1c79356b A	127	* wait_queue_link_t
9bccf70c	128	* Specialized wait queue element type for linking set
1c79356b A	129	* event waits queues onto a wait queue. In this way, an event
	130	* can be constructed so that any thread waiting on any number
	131	* of associated wait queues can handle the event, while letting
	132	* the thread only be linked on the single wait queue it blocked on.
	133	*
	134	* One use: ports in multiple portsets. Each thread is queued up
	135	* on the portset that it specifically blocked on during a receive
	136	* operation. Each port's event queue links in all the portset
	137	* event queues of which it is a member. An IPC event post associated
	138	* with that port may wake up any thread from any of those portsets,
	139	* or one that was waiting locally on the port itself.
	140	*/
2d21ac55	141	typedef struct _wait_queue_link {
9bccf70c A	142	WaitQueueElement wql_element; /* element on master */
9bccf70c A	143	queue_chain_t wql_setlinks; /* element on set */
b0d623f7	144	queue_chain_t wql_preposts; /* element on set prepost list */
9bccf70c	145	wait_queue_set_t wql_setqueue; /* set queue */
0b4e3aa0 A	146	} WaitQueueLink;
0b4e3aa0 A	147
1c79356b	148	#define wql_links wql_element.wqe_links
9bccf70c	149	#define wql_type wql_element.wqe_type
1c79356b	150	#define wql_queue wql_element.wqe_queue
0b4e3aa0	151
39236c6e A	152	#define _WAIT_QUEUE_inited 0x2
39236c6e A	153	#define _WAIT_QUEUE_SET_inited 0x3
0b4e3aa0	154
9bccf70c A	155	#define wait_queue_is_queue(wq) \
9bccf70c A	156	((wq)->wq_type == _WAIT_QUEUE_inited)
1c79356b	157
9bccf70c A	158	#define wait_queue_is_set(wqs) \
9bccf70c A	159	((wqs)->wqs_type == _WAIT_QUEUE_SET_inited)
1c79356b	160
9bccf70c A	161	#define wait_queue_is_valid(wq) \
9bccf70c A	162	(((wq)->wq_type & ~1) == _WAIT_QUEUE_inited)
1c79356b	163
9bccf70c	164	#define wait_queue_empty(wq) (queue_empty(&(wq)->wq_queue))
2d21ac55	165
9bccf70c A	166	#define wait_queue_held(wq) (hw_lock_held(&(wq)->wq_interlock))
9bccf70c A	167	#define wait_queue_lock_try(wq) (hw_lock_try(&(wq)->wq_interlock))
1c79356b	168
2d21ac55	169	/* For x86, the hardware timeout is in TSC units. */
6d2010ae	170	#if defined(i386) \|\| defined(x86_64)
2d21ac55 A	171	#define hwLockTimeOut LockTimeOutTSC
	172	#else
	173	#define hwLockTimeOut LockTimeOut
	174	#endif
9bccf70c A	175	/*
	176	* Double the standard lock timeout, because wait queues tend
	177	* to iterate over a number of threads - locking each. If there is
	178	* a problem with a thread lock, it normally times out at the wait
	179	* queue level first, hiding the real problem.
	180	*/
1c79356b	181
0c530ab8	182	static inline void wait_queue_lock(wait_queue_t wq) {
6d2010ae	183	if (__improbable(hw_lock_to(&(wq)->wq_interlock, hwLockTimeOut * 2) == 0)) {
060df5ea	184	boolean_t wql_acquired = FALSE;
6d2010ae	185
060df5ea A	186	while (machine_timeout_suspended()) {
	187	#if defined(__i386__) \|\| defined(__x86_64__)
	188	/*
	189	* i386/x86_64 return with preemption disabled on a timeout for
	190	* diagnostic purposes.
	191	*/
	192	mp_enable_preemption();
	193	#endif
	194	if ((wql_acquired = hw_lock_to(&(wq)->wq_interlock, hwLockTimeOut * 2)))
	195	break;
	196	}
060df5ea A	197	if (wql_acquired == FALSE)
	198	panic("wait queue deadlock - wq=%p, cpu=%d\n", wq, cpu_number());
	199	}
39236c6e	200	assert(wait_queue_held(wq));
0c530ab8	201	}
060df5ea	202
0c530ab8 A	203	static inline void wait_queue_unlock(wait_queue_t wq) {
0c530ab8 A	204	assert(wait_queue_held(wq));
2d21ac55	205	hw_lock_unlock(&(wq)->wq_interlock);
0c530ab8	206	}
1c79356b	207
9bccf70c A	208	#define wqs_lock(wqs) wait_queue_lock(&(wqs)->wqs_wait_queue)
	209	#define wqs_unlock(wqs) wait_queue_unlock(&(wqs)->wqs_wait_queue)
	210	#define wqs_lock_try(wqs) wait_queue__try_lock(&(wqs)->wqs_wait_queue)
b0d623f7 A	211	#define wqs_is_preposted(wqs) ((wqs)->wqs_prepost && !queue_empty(&(wqs)->wqs_preposts))
	212
	213	#define wql_is_preposted(wql) ((wql)->wql_preposts.next != NULL)
	214	#define wql_clear_prepost(wql) ((wql)->wql_preposts.next = (wql)->wql_preposts.prev = NULL)
1c79356b A	215
	216	#define wait_queue_assert_possible(thread) \
	217	((thread)->wait_queue == WAIT_QUEUE_NULL)
	218
b0d623f7 A	219	/* bootstrap interface - can allocate/link wait_queues and sets after calling this */
	220	__private_extern__ void wait_queue_bootstrap(void);
	221
1c79356b A	222	/****** Decomposed interfaces (to build higher level constructs) *********/
1c79356b A	223
1c79356b	224	/* assert intent to wait on a locked wait queue */
9bccf70c	225	__private_extern__ wait_result_t wait_queue_assert_wait64_locked(
1c79356b	226	wait_queue_t wait_queue,
9bccf70c A	227	event64_t wait_event,
9bccf70c A	228	wait_interrupt_t interruptible,
39236c6e	229	wait_timeout_urgency_t urgency,
91447636	230	uint64_t deadline,
39236c6e	231	uint64_t leeway,
55e303ae	232	thread_t thread);
1c79356b	233
2d21ac55	234	/* pull a thread from its wait queue */
9bccf70c	235	__private_extern__ void wait_queue_pull_thread_locked(
1c79356b A	236	wait_queue_t wait_queue,
	237	thread_t thread,
	238	boolean_t unlock);
	239
	240	/* wakeup all threads waiting for a particular event on locked queue */
9bccf70c	241	__private_extern__ kern_return_t wait_queue_wakeup64_all_locked(
1c79356b	242	wait_queue_t wait_queue,
9bccf70c A	243	event64_t wake_event,
9bccf70c A	244	wait_result_t result,
1c79356b A	245	boolean_t unlock);
	246
	247	/* wakeup one thread waiting for a particular event on locked queue */
9bccf70c	248	__private_extern__ kern_return_t wait_queue_wakeup64_one_locked(
1c79356b	249	wait_queue_t wait_queue,
9bccf70c A	250	event64_t wake_event,
9bccf70c A	251	wait_result_t result,
1c79356b A	252	boolean_t unlock);
1c79356b A	253
1c79356b	254	/* return identity of a thread awakened for a particular <wait_queue,event> */
9bccf70c	255	__private_extern__ thread_t wait_queue_wakeup64_identity_locked(
1c79356b	256	wait_queue_t wait_queue,
9bccf70c A	257	event64_t wake_event,
9bccf70c A	258	wait_result_t result,
1c79356b A	259	boolean_t unlock);
	260
	261	/* wakeup thread iff its still waiting for a particular event on locked queue */
9bccf70c	262	__private_extern__ kern_return_t wait_queue_wakeup64_thread_locked(
1c79356b	263	wait_queue_t wait_queue,
9bccf70c	264	event64_t wake_event,
1c79356b	265	thread_t thread,
9bccf70c	266	wait_result_t result,
1c79356b A	267	boolean_t unlock);
1c79356b A	268
39236c6e A	269	extern uint32_t num_wait_queues;
39236c6e A	270	extern struct wait_queue *wait_queues;
b0d623f7 A	271	/* The Jenkins "one at a time" hash.
	272	* TBD: There may be some value to unrolling here,
	273	* depending on the architecture.
	274	*/
	275	static inline uint32_t wq_hash(char *key)
	276	{
	277	uint32_t hash = 0;
	278	size_t i, length = sizeof(char *);
	279
	280	for (i = 0; i < length; i++) {
	281	hash += key[i];
	282	hash += (hash << 10);
	283	hash ^= (hash >> 6);
	284	}
	285
	286	hash += (hash << 3);
	287	hash ^= (hash >> 11);
	288	hash += (hash << 15);
	289
316670eb	290	hash &= (num_wait_queues - 1);
b0d623f7 A	291	return hash;
	292	}
	293
316670eb	294	#define wait_hash(event) wq_hash((char *)&event)
b0d623f7	295
91447636 A	296	#endif /* MACH_KERNEL_PRIVATE */
	297
	298	__BEGIN_DECLS
1c79356b	299
9bccf70c A	300	/****** Semi-Public interfaces (not a part of a higher construct) **********/
9bccf70c A	301
91447636 A	302	extern unsigned int wait_queue_set_size(void);
	303	extern unsigned int wait_queue_link_size(void);
	304
9bccf70c A	305	extern kern_return_t wait_queue_init(
	306	wait_queue_t wait_queue,
	307	int policy);
	308
	309	extern wait_queue_set_t wait_queue_set_alloc(
	310	int policy);
	311
91447636 A	312	extern kern_return_t wait_queue_set_init(
	313	wait_queue_set_t set_queue,
	314	int policy);
	315
9bccf70c A	316	extern kern_return_t wait_queue_set_free(
	317	wait_queue_set_t set_queue);
	318
	319	extern wait_queue_link_t wait_queue_link_alloc(
	320	int policy);
	321
	322	extern kern_return_t wait_queue_link_free(
	323	wait_queue_link_t link_element);
	324
91447636 A	325	extern kern_return_t wait_queue_link(
	326	wait_queue_t wait_queue,
	327	wait_queue_set_t set_queue);
9bccf70c	328
91447636 A	329	extern kern_return_t wait_queue_link_noalloc(
	330	wait_queue_t wait_queue,
	331	wait_queue_set_t set_queue,
	332	wait_queue_link_t link);
1c79356b	333
91447636	334	extern boolean_t wait_queue_member(
9bccf70c A	335	wait_queue_t wait_queue,
	336	wait_queue_set_t set_queue);
	337
	338	extern kern_return_t wait_queue_unlink(
	339	wait_queue_t wait_queue,
	340	wait_queue_set_t set_queue);
	341
	342	extern kern_return_t wait_queue_unlink_all(
1c79356b A	343	wait_queue_t wait_queue);
1c79356b A	344
9bccf70c A	345	extern kern_return_t wait_queue_set_unlink_all(
	346	wait_queue_set_t set_queue);
	347
6d2010ae A	348	#ifdef XNU_KERNEL_PRIVATE
	349	extern kern_return_t wait_queue_set_unlink_one(
	350	wait_queue_set_t set_queue,
	351	wait_queue_link_t link);
	352
316670eb A	353	extern kern_return_t wait_queue_unlink_nofree(
	354	wait_queue_t wait_queue,
	355	wait_queue_set_t set_queue,
	356	wait_queue_link_t *wqlp);
	357
	358	extern kern_return_t wait_queue_unlink_all_nofree(
	359	wait_queue_t wait_queue,
	360	queue_t links);
	361
	362	extern kern_return_t wait_queue_set_unlink_all_nofree(
	363	wait_queue_set_t set_queue,
	364	queue_t links);
	365
6d2010ae A	366	extern wait_queue_link_t wait_queue_link_allocate(void);
	367
	368	#endif /* XNU_KERNEL_PRIVATE */
	369
91447636 A	370	/* legacy API */
	371	kern_return_t wait_queue_sub_init(
	372	wait_queue_set_t set_queue,
	373	int policy);
	374
	375	kern_return_t wait_queue_sub_clearrefs(
	376	wait_queue_set_t wq_set);
	377
	378	extern kern_return_t wait_subqueue_unlink_all(
	379	wait_queue_set_t set_queue);
	380
	381	extern wait_queue_t wait_queue_alloc(
	382	int policy);
	383
	384	extern kern_return_t wait_queue_free(
	385	wait_queue_t wait_queue);
	386
9bccf70c A	387	/* assert intent to wait on <wait_queue,event64> pair */
	388	extern wait_result_t wait_queue_assert_wait64(
	389	wait_queue_t wait_queue,
	390	event64_t wait_event,
91447636 A	391	wait_interrupt_t interruptible,
91447636 A	392	uint64_t deadline);
9bccf70c	393
39236c6e A	394	extern wait_result_t wait_queue_assert_wait64_with_leeway(
	395	wait_queue_t wait_queue,
	396	event64_t wait_event,
	397	wait_interrupt_t interruptible,
	398	wait_timeout_urgency_t urgency,
	399	uint64_t deadline,
	400	uint64_t leeway);
	401
9bccf70c A	402	/* wakeup the most appropriate thread waiting on <wait_queue,event64> pair */
	403	extern kern_return_t wait_queue_wakeup64_one(
	404	wait_queue_t wait_queue,
	405	event64_t wake_event,
	406	wait_result_t result);
	407
	408	/* wakeup all the threads waiting on <wait_queue,event64> pair */
	409	extern kern_return_t wait_queue_wakeup64_all(
	410	wait_queue_t wait_queue,
	411	event64_t wake_event,
	412	wait_result_t result);
	413
	414	/* wakeup a specified thread waiting iff waiting on <wait_queue,event64> pair */
	415	extern kern_return_t wait_queue_wakeup64_thread(
	416	wait_queue_t wait_queue,
	417	event64_t wake_event,
	418	thread_t thread,
	419	wait_result_t result);
	420
9bccf70c A	421	/*
	422	* Compatibility Wait Queue APIs based on pointer events instead of 64bit
	423	* integer events.
	424	*/
1c79356b A	425
1c79356b A	426	/* assert intent to wait on <wait_queue,event> pair */
9bccf70c	427	extern wait_result_t wait_queue_assert_wait(
1c79356b A	428	wait_queue_t wait_queue,
1c79356b A	429	event_t wait_event,
91447636 A	430	wait_interrupt_t interruptible,
91447636 A	431	uint64_t deadline);
1c79356b	432
39236c6e A	433	/* assert intent to wait on <wait_queue,event> pair */
	434	extern wait_result_t wait_queue_assert_wait_with_leeway(
	435	wait_queue_t wait_queue,
	436	event_t wait_event,
	437	wait_interrupt_t interruptible,
	438	wait_timeout_urgency_t urgency,
	439	uint64_t deadline,
	440	uint64_t leeway);
	441
1c79356b	442	/* wakeup the most appropriate thread waiting on <wait_queue,event> pair */
9bccf70c	443	extern kern_return_t wait_queue_wakeup_one(
1c79356b A	444	wait_queue_t wait_queue,
1c79356b A	445	event_t wake_event,
6d2010ae A	446	wait_result_t result,
6d2010ae A	447	int priority);
1c79356b A	448
1c79356b A	449	/* wakeup all the threads waiting on <wait_queue,event> pair */
9bccf70c	450	extern kern_return_t wait_queue_wakeup_all(
1c79356b A	451	wait_queue_t wait_queue,
1c79356b A	452	event_t wake_event,
9bccf70c	453	wait_result_t result);
1c79356b A	454
1c79356b A	455	/* wakeup a specified thread waiting iff waiting on <wait_queue,event> pair */
9bccf70c	456	extern kern_return_t wait_queue_wakeup_thread(
1c79356b A	457	wait_queue_t wait_queue,
	458	event_t wake_event,
	459	thread_t thread,
9bccf70c A	460	wait_result_t result);
9bccf70c A	461
91447636 A	462	__END_DECLS
	463
	464	#endif /* _KERN_WAIT_QUEUE_H_ */
1c79356b	465
91447636	466	#endif /* KERNEL_PRIVATE */