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

/*
 * Copyright (c) 2000 Apple Computer, Inc. All rights reserved.
 *
 * @APPLE_LICENSE_HEADER_START@
 * 
 * The contents of this file constitute Original Code as defined in and
 * are subject to the Apple Public Source License Version 1.1 (the
 * "License").  You may not use this file except in compliance with the
 * License.  Please obtain a copy of the License at
 * http://www.apple.com/publicsource and read it before using this file.
 * 
 * This 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 OR NON-INFRINGEMENT.  Please see the
 * License for the specific language governing rights and limitations
 * under the License.
 * 
 * @APPLE_LICENSE_HEADER_END@
 */
#ifndef _KERN_WAIT_QUEUE_H_
#define _KERN_WAIT_QUEUE_H_

#include <kern/kern_types.h>		/* for wait_queue_t */
#include <mach/sync_policy.h>
#include <mach/kern_return.h>		/* for kern_return_t */


#include <kern/lock.h>
#include <kern/queue.h>

/*
 *	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.
 *	WARNING: Cannot change this data structure without updating SIZEOF_WAITQUEUE
 */
typedef struct wait_queue {
    hw_lock_data_t	wq_interlock;	/* interlock */
    unsigned int                        /* flags */
    /* boolean_t */	wq_fifo:1,	/* fifo wakeup policy? */
			wq_issub:1,	/* is waitq linked? */
			wq_isprepost:1,	/* is waitq preposted? sub only */
			:0;		/* force to long boundary */
    queue_head_t	wq_queue;	/* queue of elements */
} WaitQueue;

#define SIZEOF_WAITQUEUE 	16		/* 16 bytes for wq */
#define SIZEOF_WAITQUEUE_SUB 28		/* 24 byets for wqs */
#define SIZEOF_WAITQUEUE_ELEMENT 16		/* 16 byets per wqe */
#define SIZEOF_WAITQUEUE_LINK 28		/* 28 byets per wqe */

#ifdef MACH_KERNEL_PRIVATE

/*
 *	wait_queue_sub_t
 *	This is the common definition for a subordinate 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.
 *	WARNING: Cannot change this data structure without updating SIZEOF_WAITQUEUE_SUB
 */
typedef struct wait_queue_sub {
	WaitQueue	wqs_wait_queue; /* our wait queue */
	queue_head_t	wqs_sublinks;	/* links from sub perspective */
	unsigned int 	wqs_refcount;	/* refcount for preposting */
} WaitQueueSub;


#define WAIT_QUEUE_SUB_NULL ((wait_queue_sub_t)0)


/*
 *	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 (subordinate) wait queues.
 *
 *	WARNING: The first three fields of the thread shuttle
 *	definition does not use this definition yet.  Any change in
 *	the layout here will have to be matched with a change there.
 *	WARNING: Cannot change this data structure without updating SIZEOF_WAITQUEUE_ELEMENT
 */
typedef struct wait_queue_element {
	queue_chain_t	wqe_links;	/* link of elements on this queue */
	wait_queue_t	wqe_queue;	/* queue this element is on */
	event_t		wqe_event;	/* event this element is waiting for */
} *wait_queue_element_t;


/*
 *	wait_queue_link_t
 *	Specialized wait queue element type for linking subordinate
 *	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.
 *	WARNING: Cannot change this data structure without updating SIZEOF_WAITQUEUE_LINK
 */
typedef struct wait_queue_link {
	struct wait_queue_element	wql_element;	/* element on master */
	queue_chain_t			wql_sublinks;	/* element on sub */
    wait_queue_sub_t		wql_subqueue;	/* sub queue */
} WaitQueueLink;


#define WAIT_QUEUE_LINK_NULL ((wait_queue_link_t)0)

#define wql_links wql_element.wqe_links
#define wql_queue wql_element.wqe_queue
#define wql_event wql_element.wqe_event

#define wait_queue_empty(wq)	(queue_empty(&(wq)->wq_queue))

#define wait_queue_held(wq)	(hw_lock_held(&(wq)->wq_interlock))

#define wait_queue_is_sub(wqs)	((wqs)->wqs_wait_queue.wq_issub)
#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)

extern int wait_queue_subordinate;
#define WAIT_QUEUE_SUBORDINATE &_wait_queue_subordinate

extern void wait_queue_init(
			wait_queue_t wait_queue,
			int policy);

extern kern_return_t wait_queue_link(
			wait_queue_t wait_queue,
			wait_queue_sub_t subordinate_queue);

extern kern_return_t wait_queue_unlink(
		        wait_queue_t wait_queue,
		        wait_queue_sub_t subordinate_queue);
extern void wait_queue_unlink_one(
			wait_queue_t wait_queue,
			wait_queue_sub_t *subordinate_queue_pointer);

extern boolean_t wait_queue_member_queue(
		        wait_queue_t wait_queue,
		        wait_queue_sub_t subordinate_queue);

extern kern_return_t clear_wait_queue_internal(
			thread_t thread,
			int result);

extern kern_return_t wait_queue_remove(
			thread_t thread);

#define wait_queue_assert_possible(thread) \
			((thread)->wait_queue == WAIT_QUEUE_NULL)


/******** Decomposed interfaces (to build higher level constructs) ***********/

extern void wait_queue_lock(
		        wait_queue_t wait_queue);

extern void wait_queue_unlock(
		        wait_queue_t wait_queue);

extern boolean_t wait_queue_lock_try(
			wait_queue_t wait_queue);

/* assert intent to wait on a locked wait queue */
extern boolean_t  wait_queue_assert_wait_locked(
			wait_queue_t wait_queue,
			event_t wait_event,
			int interruptible,
			boolean_t unlock);

/* peek to see which thread would be chosen for a wakeup - but keep on queue */
extern void wait_queue_peek_locked(
			wait_queue_t wait_queue,
			event_t event,
			thread_t *thread,
			wait_queue_t *found_queue);

/* peek to see which thread would be chosen for a wakeup - but keep on queue */
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 */
extern kern_return_t  wait_queue_wakeup_one_locked(
			wait_queue_t wait_queue,
			event_t wake_event,
			int result,
			boolean_t unlock);

/* wakeup one thread waiting for a particular event on locked queue */
extern kern_return_t  wait_queue_wakeup_one_locked(
			wait_queue_t wait_queue,
			event_t wake_event,
			int result,
			boolean_t unlock);

/* return the identity of a thread that is waiting for <wait_queue, event> */
extern thread_t wait_queue_recommend_locked(
			wait_queue_t wait_queue,
			event_t wake_event);
			
/* return identity of a thread awakened for a particular <wait_queue,event> */
extern thread_t wait_queue_wakeup_identity_locked(
			wait_queue_t wait_queue,
			event_t wake_event,
			int result,
			boolean_t unlock);

/* wakeup thread iff its still waiting for a particular event on locked queue */
extern kern_return_t wait_queue_wakeup_thread_locked(
			wait_queue_t wait_queue,
			event_t wake_event,
			thread_t thread,
			int result,
			boolean_t unlock);

#endif /* MACH_KERNEL_PRIVATE */

extern wait_queue_t wait_queue_alloc(
		        int policy);

extern void wait_queue_free(
			wait_queue_t wait_queue);

/******** Standalone interfaces (not a part of a higher construct) ************/

/* assert intent to wait on <wait_queue,event> pair */
extern boolean_t wait_queue_assert_wait(
			wait_queue_t wait_queue,
			event_t wait_event,
			int interruptible);

/* 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,
			int result);

/* 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,
			int 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,
			int result);

#endif /* _KERN_WAIT_QUEUE_H_ */
Commit	Line	Data
1c79356b A	1	/*
	2	* Copyright (c) 2000 Apple Computer, Inc. All rights reserved.
	3	*
	4	* @APPLE_LICENSE_HEADER_START@
	5	*
	6	* The contents of this file constitute Original Code as defined in and
	7	* are subject to the Apple Public Source License Version 1.1 (the
	8	* "License"). You may not use this file except in compliance with the
	9	* License. Please obtain a copy of the License at
	10	* http://www.apple.com/publicsource and read it before using this file.
	11	*
	12	* This Original Code and all software distributed under the License are
	13	* distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
	14	* EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
	15	* INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
	16	* FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT. Please see the
	17	* License for the specific language governing rights and limitations
	18	* under the License.
	19	*
	20	* @APPLE_LICENSE_HEADER_END@
	21	*/
	22	#ifndef _KERN_WAIT_QUEUE_H_
	23	#define _KERN_WAIT_QUEUE_H_
	24
	25	#include <kern/kern_types.h> /* for wait_queue_t */
	26	#include <mach/sync_policy.h>
0b4e3aa0	27	#include <mach/kern_return.h> /* for kern_return_t */
1c79356b	28
1c79356b A	29
	30	#include <kern/lock.h>
	31	#include <kern/queue.h>
	32
	33	/*
	34	* wait_queue_t
	35	* This is the definition of the common event wait queue
	36	* that the scheduler APIs understand. It is used
	37	* internally by the gerneralized event waiting mechanism
	38	* (assert_wait), and also for items that maintain their
	39	* own wait queues (such as ports and semaphores).
	40	*
	41	* It is not published to other kernel components. They
	42	* can create wait queues by calling wait_queue_alloc.
	43	*
	44	* NOTE: Hardware locks are used to protect event wait
	45	* queues since interrupt code is free to post events to
	46	* them.
0b4e3aa0	47	* WARNING: Cannot change this data structure without updating SIZEOF_WAITQUEUE
1c79356b A	48	*/
	49	typedef struct wait_queue {
	50	hw_lock_data_t wq_interlock; /* interlock */
	51	unsigned int /* flags */
	52	/* boolean_t / wq_fifo:1, / fifo wakeup policy? */
	53	wq_issub:1, /* is waitq linked? */
0b4e3aa0	54	wq_isprepost:1, /* is waitq preposted? sub only */
1c79356b A	55	:0; /* force to long boundary */
	56	queue_head_t wq_queue; /* queue of elements */
	57	} WaitQueue;
	58
0b4e3aa0 A	59	#define SIZEOF_WAITQUEUE 16 /* 16 bytes for wq */
	60	#define SIZEOF_WAITQUEUE_SUB 28 /* 24 byets for wqs */
	61	#define SIZEOF_WAITQUEUE_ELEMENT 16 /* 16 byets per wqe */
	62	#define SIZEOF_WAITQUEUE_LINK 28 /* 28 byets per wqe */
	63
	64	#ifdef MACH_KERNEL_PRIVATE
	65
1c79356b A	66	/*
	67	* wait_queue_sub_t
	68	* This is the common definition for a subordinate wait queue.
	69	* These can be linked as members/elements of multiple regular
	70	* wait queues. They have an additional set of linkages to
	71	* identify the linkage structures that point to them.
0b4e3aa0	72	* WARNING: Cannot change this data structure without updating SIZEOF_WAITQUEUE_SUB
1c79356b A	73	*/
	74	typedef struct wait_queue_sub {
	75	WaitQueue wqs_wait_queue; /* our wait queue */
	76	queue_head_t wqs_sublinks; /* links from sub perspective */
0b4e3aa0	77	unsigned int wqs_refcount; /* refcount for preposting */
1c79356b A	78	} WaitQueueSub;
1c79356b A	79
1c79356b A	80
	81	#define WAIT_QUEUE_SUB_NULL ((wait_queue_sub_t)0)
	82
	83
	84	/*
	85	* wait_queue_element_t
	86	* This structure describes the elements on an event wait
	87	* queue. It is the common first fields in a thread shuttle
	88	* and wait_queue_link_t. In that way, a wait queue can
	89	* consist of both thread shuttle elements and links off of
	90	* to other (subordinate) wait queues.
	91	*
	92	* WARNING: The first three fields of the thread shuttle
	93	* definition does not use this definition yet. Any change in
	94	* the layout here will have to be matched with a change there.
0b4e3aa0	95	* WARNING: Cannot change this data structure without updating SIZEOF_WAITQUEUE_ELEMENT
1c79356b A	96	*/
	97	typedef struct wait_queue_element {
	98	queue_chain_t wqe_links; /* link of elements on this queue */
	99	wait_queue_t wqe_queue; /* queue this element is on */
	100	event_t wqe_event; /* event this element is waiting for */
	101	} *wait_queue_element_t;
	102
0b4e3aa0	103
1c79356b A	104	/*
	105	* wait_queue_link_t
	106	* Specialized wait queue element type for linking subordinate
	107	* event waits queues onto a wait queue. In this way, an event
	108	* can be constructed so that any thread waiting on any number
	109	* of associated wait queues can handle the event, while letting
	110	* the thread only be linked on the single wait queue it blocked on.
	111	*
	112	* One use: ports in multiple portsets. Each thread is queued up
	113	* on the portset that it specifically blocked on during a receive
	114	* operation. Each port's event queue links in all the portset
	115	* event queues of which it is a member. An IPC event post associated
	116	* with that port may wake up any thread from any of those portsets,
	117	* or one that was waiting locally on the port itself.
0b4e3aa0	118	* WARNING: Cannot change this data structure without updating SIZEOF_WAITQUEUE_LINK
1c79356b A	119	*/
	120	typedef struct wait_queue_link {
	121	struct wait_queue_element wql_element; /* element on master */
1c79356b	122	queue_chain_t wql_sublinks; /* element on sub */
0b4e3aa0 A	123	wait_queue_sub_t wql_subqueue; /* sub queue */
	124	} WaitQueueLink;
	125
1c79356b A	126
	127	#define WAIT_QUEUE_LINK_NULL ((wait_queue_link_t)0)
	128
	129	#define wql_links wql_element.wqe_links
	130	#define wql_queue wql_element.wqe_queue
	131	#define wql_event wql_element.wqe_event
	132
0b4e3aa0 A	133	#define wait_queue_empty(wq) (queue_empty(&(wq)->wq_queue))
	134
	135	#define wait_queue_held(wq) (hw_lock_held(&(wq)->wq_interlock))
	136
	137	#define wait_queue_is_sub(wqs) ((wqs)->wqs_wait_queue.wq_issub)
	138	#define wqs_lock(wqs) wait_queue_lock(&(wqs)->wqs_wait_queue)
	139	#define wqs_unlock(wqs) wait_queue_unlock(&(wqs)->wqs_wait_queue)
	140	#define wqs_lock_try(wqs) wait_queue__try_lock(&(wqs)->wqs_wait_queue)
	141
1c79356b A	142	extern int wait_queue_subordinate;
	143	#define WAIT_QUEUE_SUBORDINATE &_wait_queue_subordinate
	144
	145	extern void wait_queue_init(
	146	wait_queue_t wait_queue,
	147	int policy);
	148
	149	extern kern_return_t wait_queue_link(
	150	wait_queue_t wait_queue,
	151	wait_queue_sub_t subordinate_queue);
	152
	153	extern kern_return_t wait_queue_unlink(
	154	wait_queue_t wait_queue,
	155	wait_queue_sub_t subordinate_queue);
	156	extern void wait_queue_unlink_one(
	157	wait_queue_t wait_queue,
	158	wait_queue_sub_t *subordinate_queue_pointer);
	159
	160	extern boolean_t wait_queue_member_queue(
	161	wait_queue_t wait_queue,
	162	wait_queue_sub_t subordinate_queue);
	163
	164	extern kern_return_t clear_wait_queue_internal(
	165	thread_t thread,
	166	int result);
	167
	168	extern kern_return_t wait_queue_remove(
	169	thread_t thread);
	170
	171	#define wait_queue_assert_possible(thread) \
	172	((thread)->wait_queue == WAIT_QUEUE_NULL)
	173
	174
1c79356b A	175
	176	/****** Decomposed interfaces (to build higher level constructs) *********/
	177
	178	extern void wait_queue_lock(
	179	wait_queue_t wait_queue);
	180
	181	extern void wait_queue_unlock(
	182	wait_queue_t wait_queue);
	183
	184	extern boolean_t wait_queue_lock_try(
	185	wait_queue_t wait_queue);
	186
	187	/* assert intent to wait on a locked wait queue */
0b4e3aa0	188	extern boolean_t wait_queue_assert_wait_locked(
1c79356b A	189	wait_queue_t wait_queue,
	190	event_t wait_event,
	191	int interruptible,
	192	boolean_t unlock);
	193
	194	/* peek to see which thread would be chosen for a wakeup - but keep on queue */
	195	extern void wait_queue_peek_locked(
	196	wait_queue_t wait_queue,
	197	event_t event,
	198	thread_t *thread,
	199	wait_queue_t *found_queue);
	200
	201	/* peek to see which thread would be chosen for a wakeup - but keep on queue */
	202	extern void wait_queue_pull_thread_locked(
	203	wait_queue_t wait_queue,
	204	thread_t thread,
	205	boolean_t unlock);
	206
	207	/* wakeup all threads waiting for a particular event on locked queue */
	208	extern kern_return_t wait_queue_wakeup_one_locked(
	209	wait_queue_t wait_queue,
	210	event_t wake_event,
	211	int result,
	212	boolean_t unlock);
	213
	214	/* wakeup one thread waiting for a particular event on locked queue */
	215	extern kern_return_t wait_queue_wakeup_one_locked(
	216	wait_queue_t wait_queue,
	217	event_t wake_event,
	218	int result,
	219	boolean_t unlock);
	220
	221	/* return the identity of a thread that is waiting for <wait_queue, event> */
	222	extern thread_t wait_queue_recommend_locked(
	223	wait_queue_t wait_queue,
	224	event_t wake_event);
	225
	226	/* return identity of a thread awakened for a particular <wait_queue,event> */
	227	extern thread_t wait_queue_wakeup_identity_locked(
	228	wait_queue_t wait_queue,
	229	event_t wake_event,
	230	int result,
	231	boolean_t unlock);
	232
	233	/* wakeup thread iff its still waiting for a particular event on locked queue */
	234	extern kern_return_t wait_queue_wakeup_thread_locked(
	235	wait_queue_t wait_queue,
	236	event_t wake_event,
	237	thread_t thread,
	238	int result,
	239	boolean_t unlock);
	240
	241	#endif /* MACH_KERNEL_PRIVATE */
	242
	243	extern wait_queue_t wait_queue_alloc(
	244	int policy);
	245
	246	extern void wait_queue_free(
	247	wait_queue_t wait_queue);
	248
	249	/****** Standalone interfaces (not a part of a higher construct) **********/
	250
	251	/* assert intent to wait on <wait_queue,event> pair */
0b4e3aa0	252	extern boolean_t wait_queue_assert_wait(
1c79356b A	253	wait_queue_t wait_queue,
	254	event_t wait_event,
	255	int interruptible);
	256
	257	/* wakeup the most appropriate thread waiting on <wait_queue,event> pair */
	258	extern kern_return_t wait_queue_wakeup_one(
	259	wait_queue_t wait_queue,
	260	event_t wake_event,
	261	int result);
	262
	263	/* wakeup all the threads waiting on <wait_queue,event> pair */
	264	extern kern_return_t wait_queue_wakeup_all(
	265	wait_queue_t wait_queue,
	266	event_t wake_event,
	267	int result);
	268
	269	/* wakeup a specified thread waiting iff waiting on <wait_queue,event> pair */
	270	extern kern_return_t wait_queue_wakeup_thread(
	271	wait_queue_t wait_queue,
	272	event_t wake_event,
	273	thread_t thread,
	274	int result);
	275
	276	#endif /* _KERN_WAIT_QUEUE_H_ */