[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 <kern/assert.h>

#include <sys/cdefs.h>

#ifdef	MACH_KERNEL_PRIVATE

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