xnu-201.42.3.tar.gz

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

/*
 * 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@
 */
/*
 * @OSF_FREE_COPYRIGHT@
 */
/* 
 * Mach Operating System
 * Copyright (c) 1991,1990,1989,1988,1987 Carnegie Mellon University
 * All Rights Reserved.
 * 
 * Permission to use, copy, modify and distribute this software and its
 * documentation is hereby granted, provided that both the copyright
 * notice and this permission notice appear in all copies of the
 * software, derivative works or modified versions, and any portions
 * thereof, and that both notices appear in supporting documentation.
 * 
 * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
 * CONDITION.  CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR
 * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
 * 
 * Carnegie Mellon requests users of this software to return to
 * 
 *  Software Distribution Coordinator  or  Software.Distribution@CS.CMU.EDU
 *  School of Computer Science
 *  Carnegie Mellon University
 *  Pittsburgh PA 15213-3890
 * 
 * any improvements or extensions that they make and grant Carnegie Mellon
 * the rights to redistribute these changes.
 */
/*
 */
/*
 *	File:	wait_queue.c (adapted from sched_prim.c)
 *	Author:	Avadis Tevanian, Jr.
 *	Date:	1986
 *
 *	Primitives for manipulating wait queues: either global
 *	ones from sched_prim.c, or private ones associated with
 *	particular structures(pots, semaphores, etc..).
 */

#include <kern/kern_types.h>
#include <kern/simple_lock.h>
#include <kern/kalloc.h>
#include <kern/queue.h>
#include <kern/spl.h>
#include <mach/sync_policy.h>

#include <kern/sched_prim.h>
#include <kern/wait_queue.h>

void
wait_queue_init(
        wait_queue_t wq,
	int policy)
{
	wq->wq_fifo = (policy == SYNC_POLICY_FIFO);
	wq->wq_issub = FALSE;
	queue_init(&wq->wq_queue);
	hw_lock_init(&wq->wq_interlock);
}

void
wait_queue_sub_init(
        wait_queue_sub_t wqsub,
	int policy)
{
	wait_queue_init(&wqsub->wqs_wait_queue, policy);
	wqsub->wqs_wait_queue.wq_issub = TRUE;
	if ( policy & SYNC_POLICY_PREPOST) {
		wqsub->wqs_wait_queue.wq_isprepost = TRUE;
		wqsub->wqs_refcount = 0;
	} else 
		wqsub->wqs_wait_queue.wq_isprepost = FALSE;
	queue_init(&wqsub->wqs_sublinks);
}

void
wait_queue_sub_clearrefs(
        wait_queue_sub_t wq_sub)
{
	assert(wait_queue_is_sub(wq_sub));

	wqs_lock(wq_sub);

	wq_sub->wqs_refcount = 0;

	wqs_unlock(wq_sub);

}

void
wait_queue_link_init(
	wait_queue_link_t wql)
{
	queue_init(&wql->wql_links);
	queue_init(&wql->wql_sublinks);
	wql->wql_queue = WAIT_QUEUE_NULL;
	wql->wql_subqueue = WAIT_QUEUE_SUB_NULL;
	wql->wql_event = NO_EVENT;
}

/*
 *     Routine:        wait_queue_alloc
 *     Purpose:
 *             Allocate and initialize a wait queue for use outside of
 *             of the mach part of the kernel.
 *
 *     Conditions:
 *             Nothing locked - can block.
 *
 *     Returns:
 *             The allocated and initialized wait queue
 *             WAIT_QUEUE_NULL if there is a resource shortage
 */
wait_queue_t
wait_queue_alloc(
         int policy)
{
	wait_queue_t wq;

	wq = (wait_queue_t) kalloc(sizeof(struct wait_queue));
	if (wq != WAIT_QUEUE_NULL)
		wait_queue_init(wq, policy);
	return wq;
}

/*
 *     Routine:        wait_queue_free
 *     Purpose:
 *             Free an allocated wait queue.
 *
 *     Conditions:
 *             Nothing locked - can block.
 */
void
wait_queue_free(
	wait_queue_t wq)
{
	assert(queue_empty(&wq->wq_queue));
	kfree((vm_offset_t)wq, sizeof(struct wait_queue));
}


/*
 *	Routine:	wait_queue_lock
 *	Purpose:
 *		Lock the wait queue.
 *	Conditions:
 *		the appropriate spl level (if any) is already raised.
 */
void
wait_queue_lock(
        wait_queue_t wq)
{
#ifdef __ppc__
	vm_offset_t pc;

        /*
         * 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.
         */
	pc = GET_RETURN_PC(&wq);
	if (!hw_lock_to(&wq->wq_interlock, LockTimeOut * 2)) {
		panic("wait queue deadlock detection - wq=0x%x, cpu=%d, ret=0x%x\n", wq, cpu_number(), pc);
	}
#else
	hw_lock_lock(&wq->wq_interlock);
#endif
}

/*
 *	Routine:	wait_queue_lock_try
 *	Purpose:
 *		Try to lock the wait queue without waiting
 *	Conditions:
 *		the appropriate spl level (if any) is already raised.
 *  Returns:
 *		TRUE if the lock was acquired
 *		FALSE if we would have needed to wait
 */
boolean_t
wait_queue_lock_try(
        wait_queue_t wq)
{
	return hw_lock_try(&wq->wq_interlock);
}

/*
 *	Routine:	wait_queue_unlock
 *	Purpose:
 *		unlock the wait queue
 *	Conditions:
 *		The wait queue is assumed locked.
 *		appropriate spl level is still maintained
 */
void
wait_queue_unlock(
	wait_queue_t wq)
{
	assert(hw_lock_held(&wq->wq_interlock));

	hw_lock_unlock(&wq->wq_interlock);
}

int _wait_queue_subordinate; /* phoney event for subordinate wait q elements */

	
/*
 *	Routine:	wait_queue_member_locked
 *	Purpose:
 *		Indicate if this sub queue is a member of the queue
 *	Conditions:
 *		The wait queue is locked
 *		The sub queue is just that, a sub queue
 */
boolean_t
wait_queue_member_locked(
	wait_queue_t wq,
	wait_queue_sub_t wq_sub)
{
	wait_queue_element_t wq_element;
	queue_t q;

	assert(wait_queue_held(wq));
	assert(wait_queue_is_sub(wq_sub));

	q = &wq->wq_queue;

	wq_element = (wait_queue_element_t) queue_first(q);
	while (!queue_end(q, (queue_entry_t)wq_element)) {

		if ((wq_element->wqe_event == WAIT_QUEUE_SUBORDINATE)) {
			wait_queue_link_t wql = (wait_queue_link_t)wq_element;

			if (wql->wql_subqueue == wq_sub)
				return TRUE;
		}
		wq_element = (wait_queue_element_t)
			     queue_next((queue_t) wq_element);
	}
	return FALSE;
}
	

/*
 *	Routine:	wait_queue_member
 *	Purpose:
 *		Indicate if this sub queue is a member of the queue
 *	Conditions:
 *		The sub queue is just that, a sub queue
 */
boolean_t
wait_queue_member(
	wait_queue_t wq,
	wait_queue_sub_t wq_sub)
{
	boolean_t ret;
	spl_t s;

	assert(wait_queue_is_sub(wq_sub));

	s = splsched();
	wait_queue_lock(wq);
	ret = wait_queue_member_locked(wq, wq_sub);
	wait_queue_unlock(wq);
	splx(s);

	return ret;
}

/*
 *	Routine:	wait_queue_link
 *	Purpose:
 *		Insert a subordinate wait queue into a wait queue.  This
 *		requires us to link the two together using a wait_queue_link
 *		structure that we allocate.
 *	Conditions:
 *		The wait queue being inserted must be inited as a sub queue
 *		The sub waitq is not already linked
 *
 */
kern_return_t
wait_queue_link(
	wait_queue_t wq,
	wait_queue_sub_t wq_sub)
{
	wait_queue_link_t wql;
	spl_t s;

	assert(wait_queue_is_sub(wq_sub));
	assert(!wait_queue_member(wq, wq_sub));

	wql = (wait_queue_link_t) kalloc(sizeof(struct wait_queue_link));
	if (wql == WAIT_QUEUE_LINK_NULL)
		return KERN_RESOURCE_SHORTAGE;
	
	wait_queue_link_init(wql);

	s = splsched();
	wait_queue_lock(wq);
	wqs_lock(wq_sub);

	wql->wql_queue = wq;
	wql->wql_subqueue = wq_sub;
	wql->wql_event = WAIT_QUEUE_SUBORDINATE;
	queue_enter(&wq->wq_queue, wql, wait_queue_link_t, wql_links);
	queue_enter(&wq_sub->wqs_sublinks, wql, wait_queue_link_t, wql_sublinks);
	
	wqs_unlock(wq_sub);
	wait_queue_unlock(wq);
	splx(s);

	return KERN_SUCCESS;
}	
/*
 *	Routine:	wait_queue_link_noalloc
 *	Purpose:
 *		Insert a subordinate wait queue into a wait queue.  This
 *		requires us to link the two together using a wait_queue_link
 *		structure that we allocate.
 *	Conditions:
 *		The wait queue being inserted must be inited as a sub queue
 *		The sub waitq is not already linked
 *
 */
kern_return_t
wait_queue_link_noalloc(
	wait_queue_t wq,
	wait_queue_sub_t wq_sub,
	wait_queue_link_t wql)
{
	spl_t s;

	assert(wait_queue_is_sub(wq_sub));
	assert(!wait_queue_member(wq, wq_sub));

	wait_queue_link_init(wql);

	s = splsched();
	wait_queue_lock(wq);
	wqs_lock(wq_sub);

	wql->wql_queue = wq;
	wql->wql_subqueue = wq_sub;
	wql->wql_event = WAIT_QUEUE_SUBORDINATE;
	queue_enter(&wq->wq_queue, wql, wait_queue_link_t, wql_links);
	queue_enter(&wq_sub->wqs_sublinks, wql, wait_queue_link_t, wql_sublinks);
	
	wqs_unlock(wq_sub);
	wait_queue_unlock(wq);
	splx(s);

	return KERN_SUCCESS;
}	

/*
 *	Routine:	wait_queue_unlink
 *	Purpose:
 *		Remove the linkage between a wait queue and its subordinate.
 *	Conditions:
 *		The wait queue being must be a member sub queue
 */
kern_return_t
wait_queue_unlink(
	wait_queue_t wq,
	wait_queue_sub_t wq_sub)
{
	wait_queue_element_t wq_element;
	queue_t q;
	spl_t s;

	assert(wait_queue_is_sub(wq_sub));
	assert(wait_queue_member(wq, wq_sub));

	s = splsched();
	wait_queue_lock(wq);
	wqs_lock(wq_sub);

	q = &wq->wq_queue;

	wq_element = (wait_queue_element_t) queue_first(q);
	while (!queue_end(q, (queue_entry_t)wq_element)) {

		if (wq_element->wqe_event == WAIT_QUEUE_SUBORDINATE) {
			wait_queue_link_t wql = (wait_queue_link_t)wq_element;
			queue_t sq;
			
			if (wql->wql_subqueue == wq_sub) {
				sq = &wq_sub->wqs_sublinks;
				queue_remove(q, wql, wait_queue_link_t, wql_links);
				queue_remove(sq, wql, wait_queue_link_t, wql_sublinks);
				wqs_unlock(wq_sub);
				wait_queue_unlock(wq);
				splx(s);
				kfree((vm_offset_t)wql,sizeof(struct wait_queue_link));
				return;
			}
		}

		wq_element = (wait_queue_element_t)
			     queue_next((queue_t) wq_element);
	}
	panic("wait_queue_unlink");
}	

/*
 *	Routine:	wait_queue_unlink_nofree
 *	Purpose:
 *		Remove the linkage between a wait queue and its subordinate. Do not deallcoate the wql
 *	Conditions:
 *		The wait queue being must be a member sub queue
 */
kern_return_t
wait_queue_unlink_nofree(
	wait_queue_t wq,
	wait_queue_sub_t wq_sub)
{
	wait_queue_element_t wq_element;
	queue_t q;

	assert(wait_queue_is_sub(wq_sub));

	q = &wq->wq_queue;

	wq_element = (wait_queue_element_t) queue_first(q);
	while (!queue_end(q, (queue_entry_t)wq_element)) {

		if (wq_element->wqe_event == WAIT_QUEUE_SUBORDINATE) {
			wait_queue_link_t wql = (wait_queue_link_t)wq_element;
			queue_t sq;
			
			if (wql->wql_subqueue == wq_sub) {
				sq = &wq_sub->wqs_sublinks;
				queue_remove(q, wql, wait_queue_link_t, wql_links);
				queue_remove(sq, wql, wait_queue_link_t, wql_sublinks);
				return(KERN_SUCCESS);
			}
		}

		wq_element = (wait_queue_element_t)
			     queue_next((queue_t) wq_element);
	}
	/* due to dropping the sub's lock to get to this routine we can see
	 * no entries in waitqueue. It is valid case, so we should just return
	 */
	return(KERN_FAILURE);
}

/*
 *	Routine:	wait_subqueue_unlink_all
 *	Purpose:
 *		Remove the linkage between a wait queue and its subordinate.
 *	Conditions:
 *		The wait queue being must be a member sub queue
 */
kern_return_t
wait_subqueue_unlink_all(
	wait_queue_sub_t wq_sub)
{
	wait_queue_link_t wql;
	wait_queue_t wq;
	queue_t q;
	kern_return_t kret;
	spl_t s;

	assert(wait_queue_is_sub(wq_sub));

retry:
	s = splsched();
	wqs_lock(wq_sub);

	q = &wq_sub->wqs_sublinks;

	wql = (wait_queue_link_t)queue_first(q);
	while (!queue_end(q, (queue_entry_t)wql)) {
		wq = wql->wql_queue;
		if (wait_queue_lock_try(wq)) {
#if 0
			queue_t q1;

				q1 = &wq->wq_queue;

				queue_remove(q1, wql, wait_queue_link_t, wql_links);
				queue_remove(q, wql, wait_queue_link_t, wql_sublinks);
#else
				if ((kret = wait_queue_unlink_nofree(wq, wq_sub)) != KERN_SUCCESS) {
				queue_remove(q, wql, wait_queue_link_t, wql_sublinks);

}
#endif
				wait_queue_unlock(wq);
				wql = (wait_queue_link_t)queue_first(q);
		} else {
			wqs_unlock(wq_sub);
			splx(s);
			mutex_pause();
			goto retry;
		}
	}
	wqs_unlock(wq_sub);
	splx(s);
	return(KERN_SUCCESS);
}	


/*
 *	Routine:	wait_queue_unlinkall_nofree
 *	Purpose:
 *		Remove the linkage between a wait queue and all subordinates.
 */

kern_return_t
wait_queue_unlinkall_nofree(
	wait_queue_t wq)
{
	wait_queue_element_t wq_element;
	wait_queue_sub_t wq_sub;
	queue_t q;
	spl_t s;


	s = splsched();
	wait_queue_lock(wq);

	q = &wq->wq_queue;

	wq_element = (wait_queue_element_t) queue_first(q);
	while (!queue_end(q, (queue_entry_t)wq_element)) {

		if (wq_element->wqe_event == WAIT_QUEUE_SUBORDINATE) {
			wait_queue_link_t wql = (wait_queue_link_t)wq_element;
			queue_t sq;
			
				wq_sub = wql->wql_subqueue;
				wqs_lock(wq_sub);
				sq = &wq_sub->wqs_sublinks;
				queue_remove(q, wql, wait_queue_link_t, wql_links);
				queue_remove(sq, wql, wait_queue_link_t, wql_sublinks);
				wqs_unlock(wq_sub);
				wq_element = (wait_queue_element_t) queue_first(q);
		} else {
			wq_element = (wait_queue_element_t)
			     queue_next((queue_t) wq_element);
		}

	}
	wait_queue_unlock(wq);
	splx(s);

	return(KERN_SUCCESS);
}	
/*
 *	Routine:	wait_queue_unlink_one
 *	Purpose:
 *		Find and unlink one subordinate wait queue
 *	Conditions:
 *		Nothing of interest locked.
 */
void
wait_queue_unlink_one(
	wait_queue_t wq,
	wait_queue_sub_t *wq_subp)
{
	wait_queue_element_t wq_element;
	queue_t q;
	spl_t s;

	s = splsched();
	wait_queue_lock(wq);

	q = &wq->wq_queue;

	wq_element = (wait_queue_element_t) queue_first(q);
	while (!queue_end(q, (queue_entry_t)wq_element)) {

		if (wq_element->wqe_event == WAIT_QUEUE_SUBORDINATE) {
			wait_queue_link_t wql = (wait_queue_link_t)wq_element;
			wait_queue_sub_t wq_sub = wql->wql_subqueue;
			queue_t sq;

			wqs_lock(wq_sub);
			sq = &wq_sub->wqs_sublinks;
			queue_remove(q, wql, wait_queue_link_t, wql_links);
			queue_remove(sq, wql, wait_queue_link_t, wql_sublinks);
			wqs_unlock(wq_sub);
			wait_queue_unlock(wq);
			splx(s);
			kfree((vm_offset_t)wql,sizeof(struct wait_queue_link));
			*wq_subp = wq_sub;
			return;
		}

		wq_element = (wait_queue_element_t)
			     queue_next((queue_t) wq_element);
	}
	wait_queue_unlock(wq);
	splx(s);
	*wq_subp = WAIT_QUEUE_SUB_NULL;
}	

/*
 *	Routine:	wait_queue_assert_wait_locked
 *	Purpose:
 *		Insert the current thread into the supplied wait queue
 *		waiting for a particular event to be posted to that queue.
 *
 *	Conditions:
 *		The wait queue is assumed locked.
 *
 */
boolean_t
wait_queue_assert_wait_locked(
	wait_queue_t wq,
	event_t event,
	int interruptible,
	boolean_t unlock)
{
	thread_t thread = current_thread();
	boolean_t ret;


	if (wq->wq_issub && wq->wq_isprepost) {
		wait_queue_sub_t wqs = (wait_queue_sub_t)wq;

		if (wqs->wqs_refcount > 0) {
			if (unlock)
				wait_queue_unlock(wq);
			return(FALSE);
		}
	}

	thread_lock(thread);

	/*
	 * This is the extent to which we currently take scheduling attributes
	 * into account.  If the thread is vm priviledged, we stick it at
	 * the front of the queue.  Later, these queues will honor the policy
	 * value set at wait_queue_init time.
	 */
	if (thread->vm_privilege)
		enqueue_head(&wq->wq_queue, (queue_entry_t) thread);
	else
		enqueue_tail(&wq->wq_queue, (queue_entry_t) thread);
	thread->wait_event = event;
	thread->wait_queue = wq;
	thread_mark_wait_locked(thread, interruptible);
	thread_unlock(thread);
	if (unlock)
		wait_queue_unlock(wq);
	return(TRUE);
}

/*
 *	Routine:	wait_queue_assert_wait
 *	Purpose:
 *		Insert the current thread into the supplied wait queue
 *		waiting for a particular event to be posted to that queue.
 *
 *	Conditions:
 *		nothing of interest locked.
 */
boolean_t
wait_queue_assert_wait(
	wait_queue_t wq,
	event_t event,
	int interruptible)
{
	spl_t s;
	boolean_t ret;

	s = splsched();
	wait_queue_lock(wq);
	ret = wait_queue_assert_wait_locked(wq, event, interruptible, TRUE);
	/* wait queue unlocked */
	splx(s);
	return(ret);
}


/*
 *	Routine:	wait_queue_select_all
 *	Purpose:
 *		Select all threads off a wait queue that meet the
 *		supplied criteria.
 *
 *	Conditions:
 *		at splsched
 *		wait queue locked
 *		wake_queue initialized and ready for insertion
 *		possibly recursive
 *
 *	Returns:
 *		a queue of locked threads
 */
void
_wait_queue_select_all(
	wait_queue_t wq,
	event_t event,
	queue_t wake_queue)
{
	wait_queue_element_t wq_element;
	wait_queue_element_t wqe_next;
	queue_t q;

	q = &wq->wq_queue;

	wq_element = (wait_queue_element_t) queue_first(q);
	while (!queue_end(q, (queue_entry_t)wq_element)) {
		wqe_next = (wait_queue_element_t)
			   queue_next((queue_t) wq_element);

		/*
		 * We may have to recurse if this is a compound wait queue.
		 */
		if (wq_element->wqe_event == WAIT_QUEUE_SUBORDINATE) {
			wait_queue_link_t wql = (wait_queue_link_t)wq_element;
			wait_queue_t sub_queue;

			/*
			 * We have to check the subordinate wait queue.
			 */
			sub_queue = (wait_queue_t)wql->wql_subqueue;
			wait_queue_lock(sub_queue);
			if (sub_queue->wq_isprepost) {
				wait_queue_sub_t wqs = (wait_queue_sub_t)sub_queue;
				
				/*
				 * Preposting is only for subordinates and wait queue
				 * is the first element of subordinate 
				 */
				wqs->wqs_refcount++;
			}
			if (! wait_queue_empty(sub_queue)) 
				_wait_queue_select_all(sub_queue, event, wake_queue);
			wait_queue_unlock(sub_queue);
		} else {
			
			/*
			 * Otherwise, its a thread.  If it is waiting on
			 * the event we are posting to this queue, pull
			 * it off the queue and stick it in out wake_queue.
			 */
			thread_t t = (thread_t)wq_element;

			if (t->wait_event == event) {
				thread_lock(t);
				remqueue(q, (queue_entry_t) t);
				enqueue (wake_queue, (queue_entry_t) t);
				t->wait_queue = WAIT_QUEUE_NULL;
				t->wait_event = NO_EVENT;
				t->at_safe_point = FALSE;
				/* returned locked */
			}
		}
		wq_element = wqe_next;
	}
}

/*
 *      Routine:        wait_queue_wakeup_all_locked
 *      Purpose:
 *              Wakeup some number of threads that are in the specified
 *              wait queue and waiting on the specified event.
 *      Conditions:
 *              wait queue already locked (may be released).
 *      Returns:
 *              KERN_SUCCESS - Threads were woken up
 *              KERN_NOT_WAITING - No threads were waiting <wq,event> pair
 */
kern_return_t
wait_queue_wakeup_all_locked(
        wait_queue_t wq,
        event_t event,
        int result,
        boolean_t unlock)
{
        queue_head_t wake_queue_head;
        queue_t q = &wake_queue_head;
        kern_return_t ret = KERN_NOT_WAITING;

        assert(wait_queue_held(wq));

        queue_init(q);

        /*
         * Select the threads that we will wake up.  The threads
         * are returned to us locked and cleanly removed from the
         * wait queue.
         */
        _wait_queue_select_all(wq, event, q);
        if (unlock)
            wait_queue_unlock(wq);

        /*
         * For each thread, set it running.
         */
        while (!queue_empty (q)) {
                thread_t thread = (thread_t) dequeue(q);
                thread_go_locked(thread, result);
                thread_unlock(thread);
                ret = KERN_SUCCESS;
        }
        return ret;
}


/*
 *      Routine:        wait_queue_wakeup_all
 *      Purpose:
 *              Wakeup some number of threads that are in the specified
 *              wait queue and waiting on the specified event.
 *
 *      Conditions:
 *              Nothing locked
 *
 *      Returns:
 *              KERN_SUCCESS - Threads were woken up
 *              KERN_NOT_WAITING - No threads were waiting <wq,event> pair
 */
kern_return_t
wait_queue_wakeup_all(
        wait_queue_t wq,
        event_t event,
        int result)
{
        kern_return_t ret;
        spl_t s;

        s = splsched();
        wait_queue_lock(wq);
        ret = wait_queue_wakeup_all_locked(wq, event, result, TRUE);
        /* lock released */
        splx(s);

        return ret;
}

/*
 *	Routine:	wait_queue_select_one
 *	Purpose:
 *		Select the best thread off a wait queue that meet the
 *		supplied criteria.
 * 	Conditions:
 *		at splsched
 *		wait queue locked
 *		possibly recursive
 * 	Returns:
 *		a locked thread - if one found
 *	Note:
 *		This is where the sync policy of the wait queue comes
 *		into effect.  For now, we just assume FIFO.
 */
thread_t
_wait_queue_select_one(
	wait_queue_t wq,
	event_t event)
{
	wait_queue_element_t wq_element;
	wait_queue_element_t wqe_next;
	thread_t t = THREAD_NULL;
	queue_t q;

	assert(wq->wq_fifo);

	q = &wq->wq_queue;

	wq_element = (wait_queue_element_t) queue_first(q);
	while (!queue_end(q, (queue_entry_t)wq_element)) {
		wqe_next = (wait_queue_element_t)
			       queue_next((queue_t) wq_element);

		/*
		 * We may have to recurse if this is a compound wait queue.
		 */
		if (wq_element->wqe_event == WAIT_QUEUE_SUBORDINATE) {
			wait_queue_link_t wql = (wait_queue_link_t)wq_element;
			wait_queue_t sub_queue;

			/*
			 * We have to check the subordinate wait queue.
			 */
			sub_queue = (wait_queue_t)wql->wql_subqueue;
			wait_queue_lock(sub_queue);
			if (! wait_queue_empty(sub_queue)) {
				t = _wait_queue_select_one(sub_queue, event);
			}
			wait_queue_unlock(sub_queue);
			if (t != THREAD_NULL)
				return t;
		} else {
			
			/*
			 * Otherwise, its a thread.  If it is waiting on
			 * the event we are posting to this queue, pull
			 * it off the queue and stick it in out wake_queue.
			 */
			thread_t t = (thread_t)wq_element;

			if (t->wait_event == event) {
				thread_lock(t);
				remqueue(q, (queue_entry_t) t);
				t->wait_queue = WAIT_QUEUE_NULL;
				t->wait_event = NO_EVENT;
				t->at_safe_point = FALSE;
				return t;	/* still locked */
			}
		}
		wq_element = wqe_next;
	}
	return THREAD_NULL;
}

/*
 *	Routine:	wait_queue_peek_locked
 *	Purpose:
 *		Select the best thread from a wait queue that meet the
 *		supplied criteria, but leave it on the queue you it was
 *		found on.  The thread, and the actual wait_queue the
 *		thread was found on are identified.
 * 	Conditions:
 *		at splsched
 *		wait queue locked
 *		possibly recursive
 * 	Returns:
 *		a locked thread - if one found
 *		a locked waitq - the one the thread was found on
 *	Note:
 *		Only the waitq the thread was actually found on is locked
 *		after this.
 */
void
wait_queue_peek_locked(
	wait_queue_t wq,
	event_t event,
	thread_t *tp,
	wait_queue_t *wqp)
{
	wait_queue_element_t wq_element;
	wait_queue_element_t wqe_next;
	thread_t t;
	queue_t q;

	assert(wq->wq_fifo);

	*tp = THREAD_NULL;

	q = &wq->wq_queue;

	wq_element = (wait_queue_element_t) queue_first(q);
	while (!queue_end(q, (queue_entry_t)wq_element)) {
		wqe_next = (wait_queue_element_t)
			       queue_next((queue_t) wq_element);

		/*
		 * We may have to recurse if this is a compound wait queue.
		 */
		if (wq_element->wqe_event == WAIT_QUEUE_SUBORDINATE) {
			wait_queue_link_t wql = (wait_queue_link_t)wq_element;
			wait_queue_t sub_queue;

			/*
			 * We have to check the subordinate wait queue.
			 */
			sub_queue = (wait_queue_t)wql->wql_subqueue;
			wait_queue_lock(sub_queue);
			if (! wait_queue_empty(sub_queue)) {
				wait_queue_peek_locked(sub_queue, event, tp, wqp);
			}
			if (*tp != THREAD_NULL)
				return;  /* thread and its waitq locked */

			wait_queue_unlock(sub_queue);
		} else {
			
			/*
			 * Otherwise, its a thread.  If it is waiting on
			 * the event we are posting to this queue, return
			 * it locked, but leave it on the queue.
			 */
			thread_t t = (thread_t)wq_element;

			if (t->wait_event == event) {
				thread_lock(t);
				*tp = t;
				*wqp = wq;
				return;
			}
		}
		wq_element = wqe_next;
	}
}

/*
 *	Routine:	wait_queue_pull_thread_locked
 *	Purpose:
 *		Pull a thread that was previously "peeked" off the wait
 *		queue and (possibly) unlock the waitq.
 * 	Conditions:
 *		at splsched
 *		wait queue locked
 *		thread locked
 * 	Returns:
 *		with the thread still locked.
 */
void
wait_queue_pull_thread_locked(
	wait_queue_t waitq,
	thread_t thread,
	boolean_t unlock)
{

	assert(thread->wait_queue == waitq);

	remqueue(&waitq->wq_queue, (queue_entry_t)thread );
	thread->wait_queue = WAIT_QUEUE_NULL;
	thread->wait_event = NO_EVENT;
	thread->at_safe_point = FALSE;
	if (unlock)
		wait_queue_unlock(waitq);
}


/*
 *	Routine:	wait_queue_select_thread
 *	Purpose:
 *		Look for a thread and remove it from the queues, if
 *		(and only if) the thread is waiting on the supplied
 *		<wait_queue, event> pair.
 * 	Conditions:
 *		at splsched
 *		wait queue locked
 *		possibly recursive
 * 	Returns:
 *		KERN_NOT_WAITING: Thread is not waiting here.
 *		KERN_SUCCESS: It was, and is now removed (returned locked)
 */
kern_return_t
_wait_queue_select_thread(
	wait_queue_t wq,
	event_t event,
	thread_t thread)
{
	wait_queue_element_t wq_element;
	wait_queue_element_t wqe_next;
	kern_return_t res = KERN_NOT_WAITING;
	queue_t q = &wq->wq_queue;

	assert(wq->wq_fifo);

	thread_lock(thread);
	if ((thread->wait_queue == wq) && (thread->wait_event == event)) {
		remqueue(q, (queue_entry_t) thread);
		thread->at_safe_point = FALSE;
		thread->wait_event = NO_EVENT;
		thread->wait_queue = WAIT_QUEUE_NULL;
		/* thread still locked */
		return KERN_SUCCESS;
	}
	thread_unlock(thread);
	
	/*
	 * The wait_queue associated with the thread may be one of this
	 * wait queue's subordinates.  Go see.  If so, removing it from
	 * there is like removing it from here.
	 */
	wq_element = (wait_queue_element_t) queue_first(q);
	while (!queue_end(q, (queue_entry_t)wq_element)) {
		wqe_next = (wait_queue_element_t)
			       queue_next((queue_t) wq_element);

		if (wq_element->wqe_event == WAIT_QUEUE_SUBORDINATE) {
			wait_queue_link_t wql = (wait_queue_link_t)wq_element;
			wait_queue_t sub_queue;

			sub_queue = (wait_queue_t)wql->wql_subqueue;
			wait_queue_lock(sub_queue);
			if (! wait_queue_empty(sub_queue)) {
				res = _wait_queue_select_thread(sub_queue,
								event,
								thread);
			}
			wait_queue_unlock(sub_queue);
			if (res == KERN_SUCCESS)
				return KERN_SUCCESS;
		}
		wq_element = wqe_next;
	}
	return res;
}


/*
 *	Routine:	wait_queue_wakeup_identity_locked
 *	Purpose:
 *		Select a single thread that is most-eligible to run and set
 *		set it running.  But return the thread locked.
 *
 * 	Conditions:
 *		at splsched
 *		wait queue locked
 *		possibly recursive
 * 	Returns:
 *		a pointer to the locked thread that was awakened
 */
thread_t
wait_queue_wakeup_identity_locked(
	wait_queue_t wq,
	event_t event,
	int result,
	boolean_t unlock)
{
	thread_t thread;

	assert(wait_queue_held(wq));

	thread = _wait_queue_select_one(wq, event);
	if (unlock)
		wait_queue_unlock(wq);

	if (thread)
		thread_go_locked(thread, result);
	return thread;  /* still locked if not NULL */
}


/*
 *	Routine:	wait_queue_wakeup_one_locked
 *	Purpose:
 *		Select a single thread that is most-eligible to run and set
 *		set it runnings.
 *
 * 	Conditions:
 *		at splsched
 *		wait queue locked
 *		possibly recursive
 * 	Returns:
 *		KERN_SUCCESS: It was, and is, now removed.
 *		KERN_NOT_WAITING - No thread was waiting <wq,event> pair
 */
kern_return_t
wait_queue_wakeup_one_locked(
	wait_queue_t wq,
	event_t event,
	int result,
	boolean_t unlock)
{
	thread_t thread;

	assert(wait_queue_held(wq));

	thread = _wait_queue_select_one(wq, event);
	if (unlock)
		wait_queue_unlock(wq);

	if (thread) {
		thread_go_locked(thread, result);
		thread_unlock(thread);
		return KERN_SUCCESS;
	}

	return KERN_NOT_WAITING;
}

/*
 *	Routine:	wait_queue_wakeup_one
 *	Purpose:
 *		Wakeup the most appropriate thread that is in the specified
 *		wait queue for the specified event.
 *
 *	Conditions:
 *		Nothing locked
 *
 *	Returns:
 *		KERN_SUCCESS - Thread was woken up
 *		KERN_NOT_WAITING - No thread was waiting <wq,event> pair
 */
kern_return_t
wait_queue_wakeup_one(
	wait_queue_t wq,
	event_t event,
	int result)
{
	thread_t thread;
	spl_t s;

	s = splsched();
	wait_queue_lock(wq);
	thread = _wait_queue_select_one(wq, event);
	wait_queue_unlock(wq);

	if (thread) {
		thread_go_locked(thread, result);
		thread_unlock(thread);
		splx(s);
		return KERN_SUCCESS;
	}

	splx(s);
	return KERN_NOT_WAITING;
}



/*
 *	Routine:	wait_queue_wakeup_thread_locked
 *	Purpose:
 *		Wakeup the particular thread that was specified if and only
 *		it was in this wait queue (or one of it's subordinate queues)
 *		and waiting on the specified event.
 *
 *		This is much safer than just removing the thread from
 *		whatever wait queue it happens to be on.  For instance, it
 *		may have already been awoken from the wait you intended to
 *		interrupt and waited on something else (like another
 *		semaphore).
 *	Conditions:
 *		at splsched
 *		wait queue already locked (may be released).
 *	Returns:
 *		KERN_SUCCESS - the thread was found waiting and awakened
 *		KERN_NOT_WAITING - the thread was not waiting here
 */
kern_return_t
wait_queue_wakeup_thread_locked(
	wait_queue_t wq,
	event_t event,
	thread_t thread,
	int result,
	boolean_t unlock)
{
	kern_return_t res;

	assert(wait_queue_held(wq));

	/*
	 * See if the thread was still waiting there.  If so, it got
	 * dequeued and returned locked.
	 */
	res = _wait_queue_select_thread(wq, event, thread);
	if (unlock)
	    wait_queue_unlock(wq);

	if (res != KERN_SUCCESS)
		return KERN_NOT_WAITING;

	thread_go_locked(thread, result);
	thread_unlock(thread);
	return KERN_SUCCESS;
}

/*
 *	Routine:	wait_queue_wakeup_thread
 *	Purpose:
 *		Wakeup the particular thread that was specified if and only
 *		it was in this wait queue (or one of it's subordinate queues)
 *		and waiting on the specified event.
 *
 *		This is much safer than just removing the thread from
 *		whatever wait queue it happens to be on.  For instance, it
 *		may have already been awoken from the wait you intended to
 *		interrupt and waited on something else (like another
 *		semaphore).
 *	Conditions:
 *		nothing of interest locked
 *		we need to assume spl needs to be raised
 *	Returns:
 *		KERN_SUCCESS - the thread was found waiting and awakened
 *		KERN_NOT_WAITING - the thread was not waiting here
 */
kern_return_t
wait_queue_wakeup_thread(
	wait_queue_t wq,
	event_t event,
	thread_t thread,
	int result)
{
	kern_return_t res;
	spl_t s;

	s = splsched();
	wait_queue_lock(wq);
	res = _wait_queue_select_thread(wq, event, thread);
	wait_queue_unlock(wq);

	if (res == KERN_SUCCESS) {
		thread_go_locked(thread, result);
		thread_unlock(thread);
		splx(s);
		return KERN_SUCCESS;
	}
	splx(s);
	return KERN_NOT_WAITING;
}


/*
 *	Routine:	wait_queue_remove
 *	Purpose:
 *		Normal removal operations from wait queues drive from the
 *		wait queue to select a thread.  However, if a thread is
 *		interrupted out of a wait, this routine is called to
 *		remove it from whatever wait queue it may be in.
 *
 *	Conditions:
 *		splsched
 *		thread locked on entry and exit, but may be dropped.
 *
 *	Returns:
 *		KERN_SUCCESS - if thread was in a wait queue
 *		KERN_NOT_WAITING - it was not
 */
kern_return_t
wait_queue_remove(
        thread_t thread)
{
	wait_queue_t wq = thread->wait_queue;

	if (wq == WAIT_QUEUE_NULL)
		return KERN_NOT_WAITING;

	/*
	 * have to get the locks again in the right order.
	 */
	thread_unlock(thread);
	wait_queue_lock(wq);
	thread_lock(thread);
	
	if (thread->wait_queue == wq) {
		remqueue(&wq->wq_queue, (queue_entry_t)thread);
		thread->wait_queue = WAIT_QUEUE_NULL;
		thread->wait_event = NO_EVENT;
		thread->at_safe_point = FALSE;
		wait_queue_unlock(wq);
		return KERN_SUCCESS;
	} else {
		wait_queue_unlock(wq);
		return KERN_NOT_WAITING; /* anymore */
	}
}