X-Git-Url: https://git.saurik.com/apple/xnu.git/blobdiff_plain/c18c124eaa464aaaa5549e99e5a70fc9cbb50944..3e170ce000f1506b7b5d2c5c7faec85ceabb573d:/osfmk/kern/wait_queue.c diff --git a/osfmk/kern/wait_queue.c b/osfmk/kern/wait_queue.c deleted file mode 100644 index 1c998771b..000000000 --- a/osfmk/kern/wait_queue.c +++ /dev/null @@ -1,2172 +0,0 @@ -/* - * Copyright (c) 2000-2009 Apple 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@ - */ -/* - * @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 -#include -#include -#include -#include -#include -#include -#include - -#include -#include - -/* forward declarations */ -static boolean_t wait_queue_member_locked( - wait_queue_t wq, - wait_queue_set_t wq_set); - -static void wait_queues_init(void); - -#define WAIT_QUEUE_MAX thread_max -#define WAIT_QUEUE_SET_MAX task_max * 3 -#define WAIT_QUEUE_LINK_MAX PORT_MAX / 2 + (WAIT_QUEUE_MAX * WAIT_QUEUE_SET_MAX) / 64 - -static zone_t _wait_queue_link_zone; -static zone_t _wait_queue_set_zone; -static zone_t _wait_queue_zone; - -/* see rdar://6737748&5561610; we need an unshadowed - * definition of a WaitQueueLink for debugging, - * but it needs to be used somewhere to wind up in - * the dSYM file. */ -volatile WaitQueueLink *unused_except_for_debugging; - - -/* - * Waiting protocols and implementation: - * - * Each thread may be waiting for exactly one event; this event - * is set using assert_wait(). That thread may be awakened either - * by performing a thread_wakeup_prim() on its event, - * or by directly waking that thread up with clear_wait(). - * - * The implementation of wait events uses a hash table. Each - * bucket is queue of threads having the same hash function - * value; the chain for the queue (linked list) is the run queue - * field. [It is not possible to be waiting and runnable at the - * same time.] - * - * Locks on both the thread and on the hash buckets govern the - * wait event field and the queue chain field. Because wakeup - * operations only have the event as an argument, the event hash - * bucket must be locked before any thread. - * - * Scheduling operations may also occur at interrupt level; therefore, - * interrupts below splsched() must be prevented when holding - * thread or hash bucket locks. - * - * The wait event hash table declarations are as follows: - */ - -struct wait_queue boot_wait_queue[1]; -__private_extern__ struct wait_queue *wait_queues = &boot_wait_queue[0]; -__private_extern__ uint32_t num_wait_queues = 1; - -#define P2ROUNDUP(x, align) (-(-((uint32_t)(x)) & -(align))) -#define ROUNDDOWN(x,y) (((x)/(y))*(y)) - -static uint32_t -compute_wait_hash_size(void) -{ - uint32_t hsize, queues; - - if (PE_parse_boot_argn("wqsize", &hsize, sizeof(hsize))) - return (hsize); - - queues = thread_max / 11; - hsize = P2ROUNDUP(queues * sizeof(struct wait_queue), PAGE_SIZE); - - return hsize; -} - -static void -wait_queues_init(void) -{ - uint32_t i, whsize, qsz; - kern_return_t kret; - - /* - * Determine the amount of memory we're willing to reserve for - * the waitqueue hash table - */ - whsize = compute_wait_hash_size(); - - /* Determine the number of waitqueues we can fit. */ - qsz = sizeof (struct wait_queue); - whsize = ROUNDDOWN(whsize, qsz); - num_wait_queues = whsize / qsz; - - /* - * The hash algorithm requires that this be a power of 2, so we - * just mask off all the low-order bits. - */ - for (i = 0; i < 31; i++) { - uint32_t bit = (1 << i); - if ((num_wait_queues & bit) == num_wait_queues) - break; - num_wait_queues &= ~bit; - } - assert(num_wait_queues > 0); - - /* Now determine how much memory we really need. */ - whsize = P2ROUNDUP(num_wait_queues * qsz, PAGE_SIZE); - - kret = kernel_memory_allocate(kernel_map, (vm_offset_t *) &wait_queues, - whsize, 0, KMA_KOBJECT|KMA_NOPAGEWAIT); - - if (kret != KERN_SUCCESS || wait_queues == NULL) - panic("kernel_memory_allocate() failed to allocate wait queues, error: %d, whsize: 0x%x", kret, whsize); - - for (i = 0; i < num_wait_queues; i++) { - wait_queue_init(&wait_queues[i], SYNC_POLICY_FIFO); - } -} - -void -wait_queue_bootstrap(void) -{ - wait_queues_init(); - _wait_queue_zone = zinit(sizeof(struct wait_queue), - WAIT_QUEUE_MAX * sizeof(struct wait_queue), - sizeof(struct wait_queue), - "wait queues"); - zone_change(_wait_queue_zone, Z_NOENCRYPT, TRUE); - - _wait_queue_set_zone = zinit(sizeof(struct wait_queue_set), - WAIT_QUEUE_SET_MAX * sizeof(struct wait_queue_set), - sizeof(struct wait_queue_set), - "wait queue sets"); - zone_change(_wait_queue_set_zone, Z_NOENCRYPT, TRUE); - - _wait_queue_link_zone = zinit(sizeof(struct _wait_queue_link), - WAIT_QUEUE_LINK_MAX * sizeof(struct _wait_queue_link), - sizeof(struct _wait_queue_link), - "wait queue links"); - zone_change(_wait_queue_link_zone, Z_NOENCRYPT, TRUE); -} - -/* - * Routine: wait_queue_init - * Purpose: - * Initialize a previously allocated wait queue. - * Returns: - * KERN_SUCCESS - The wait_queue_t was initialized - * KERN_INVALID_ARGUMENT - The policy parameter was invalid - */ -kern_return_t -wait_queue_init( - wait_queue_t wq, - int policy) -{ - /* only FIFO and LIFO for now */ - if ((policy & SYNC_POLICY_FIXED_PRIORITY) != 0) - return KERN_INVALID_ARGUMENT; - - wq->wq_fifo = ((policy & SYNC_POLICY_REVERSED) == 0); - wq->wq_type = _WAIT_QUEUE_inited; - wq->wq_eventmask = 0; - queue_init(&wq->wq_queue); - hw_lock_init(&wq->wq_interlock); - return KERN_SUCCESS; -} - -/* - * 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; - kern_return_t ret; - - wq = (wait_queue_t) zalloc(_wait_queue_zone); - if (wq != WAIT_QUEUE_NULL) { - ret = wait_queue_init(wq, policy); - if (ret != KERN_SUCCESS) { - zfree(_wait_queue_zone, wq); - wq = WAIT_QUEUE_NULL; - } - } - return wq; -} - -/* - * Routine: wait_queue_free - * Purpose: - * Free an allocated wait queue. - * Conditions: - * May block. - */ -kern_return_t -wait_queue_free( - wait_queue_t wq) -{ - if (!wait_queue_is_queue(wq)) - return KERN_INVALID_ARGUMENT; - if (!queue_empty(&wq->wq_queue)) - return KERN_FAILURE; - zfree(_wait_queue_zone, wq); - return KERN_SUCCESS; -} - -/* - * Routine: wait_queue_set_init - * Purpose: - * Initialize a previously allocated wait queue set. - * Returns: - * KERN_SUCCESS - The wait_queue_set_t was initialized - * KERN_INVALID_ARGUMENT - The policy parameter was invalid - */ -kern_return_t -wait_queue_set_init( - wait_queue_set_t wqset, - int policy) -{ - kern_return_t ret; - - ret = wait_queue_init(&wqset->wqs_wait_queue, policy); - if (ret != KERN_SUCCESS) - return ret; - - wqset->wqs_wait_queue.wq_type = _WAIT_QUEUE_SET_inited; - if (policy & SYNC_POLICY_PREPOST) - wqset->wqs_wait_queue.wq_prepost = TRUE; - else - wqset->wqs_wait_queue.wq_prepost = FALSE; - queue_init(&wqset->wqs_setlinks); - queue_init(&wqset->wqs_preposts); - return KERN_SUCCESS; -} - - -kern_return_t -wait_queue_sub_init( - wait_queue_set_t wqset, - int policy) -{ - return wait_queue_set_init(wqset, policy); -} - -kern_return_t -wait_queue_sub_clearrefs( - wait_queue_set_t wq_set) -{ - wait_queue_link_t wql; - queue_t q; - spl_t s; - - if (!wait_queue_is_set(wq_set)) - return KERN_INVALID_ARGUMENT; - - s = splsched(); - wqs_lock(wq_set); - q = &wq_set->wqs_preposts; - while (!queue_empty(q)) { - queue_remove_first(q, wql, wait_queue_link_t, wql_preposts); - assert(!wql_is_preposted(wql)); - } - wqs_unlock(wq_set); - splx(s); - return KERN_SUCCESS; -} - -/* - * Routine: wait_queue_set_alloc - * Purpose: - * Allocate and initialize a wait queue set for - * use outside of the mach part of the kernel. - * Conditions: - * May block. - * Returns: - * The allocated and initialized wait queue set - * WAIT_QUEUE_SET_NULL if there is a resource shortage - */ -wait_queue_set_t -wait_queue_set_alloc( - int policy) -{ - wait_queue_set_t wq_set; - - wq_set = (wait_queue_set_t) zalloc(_wait_queue_set_zone); - if (wq_set != WAIT_QUEUE_SET_NULL) { - kern_return_t ret; - - ret = wait_queue_set_init(wq_set, policy); - if (ret != KERN_SUCCESS) { - zfree(_wait_queue_set_zone, wq_set); - wq_set = WAIT_QUEUE_SET_NULL; - } - } - return wq_set; -} - -/* - * Routine: wait_queue_set_free - * Purpose: - * Free an allocated wait queue set - * Conditions: - * May block. - */ -kern_return_t -wait_queue_set_free( - wait_queue_set_t wq_set) -{ - if (!wait_queue_is_set(wq_set)) - return KERN_INVALID_ARGUMENT; - - if (!queue_empty(&wq_set->wqs_wait_queue.wq_queue)) - return KERN_FAILURE; - - zfree(_wait_queue_set_zone, wq_set); - return KERN_SUCCESS; -} - - -/* - * - * Routine: wait_queue_set_size - * Routine: wait_queue_link_size - * Purpose: - * Return the size of opaque wait queue structures - */ -unsigned int wait_queue_set_size(void) { return sizeof(WaitQueueSet); } -unsigned int wait_queue_link_size(void) { return sizeof(WaitQueueLink); } - -/* declare a unique type for wait queue link structures */ -static unsigned int _wait_queue_link; -static unsigned int _wait_queue_link_noalloc; -static unsigned int _wait_queue_unlinked; - -#define WAIT_QUEUE_LINK ((void *)&_wait_queue_link) -#define WAIT_QUEUE_LINK_NOALLOC ((void *)&_wait_queue_link_noalloc) -#define WAIT_QUEUE_UNLINKED ((void *)&_wait_queue_unlinked) - -#define WAIT_QUEUE_ELEMENT_CHECK(wq, wqe) \ - WQASSERT(((wqe)->wqe_queue == (wq) && \ - queue_next(queue_prev((queue_t) (wqe))) == (queue_t)(wqe)), \ - "wait queue element list corruption: wq=%#x, wqe=%#x", \ - (wq), (wqe)) - -#define WQSPREV(wqs, wql) ((wait_queue_link_t)queue_prev( \ - ((&(wqs)->wqs_setlinks == (queue_t)(wql)) ? \ - (queue_t)(wql) : &(wql)->wql_setlinks))) - -#define WQSNEXT(wqs, wql) ((wait_queue_link_t)queue_next( \ - ((&(wqs)->wqs_setlinks == (queue_t)(wql)) ? \ - (queue_t)(wql) : &(wql)->wql_setlinks))) - -#define WAIT_QUEUE_SET_LINK_CHECK(wqs, wql) \ - WQASSERT(((((wql)->wql_type == WAIT_QUEUE_LINK) || \ - ((wql)->wql_type == WAIT_QUEUE_LINK_NOALLOC)) && \ - ((wql)->wql_setqueue == (wqs)) && \ - (((wql)->wql_queue->wq_type == _WAIT_QUEUE_inited) || \ - ((wql)->wql_queue->wq_type == _WAIT_QUEUE_SET_inited)) && \ - (WQSNEXT((wqs), WQSPREV((wqs),(wql))) == (wql))), \ - "wait queue set links corruption: wqs=%#x, wql=%#x", \ - (wqs), (wql)) - -#if defined(_WAIT_QUEUE_DEBUG_) - -#define WQASSERT(e, s, p0, p1) ((e) ? 0 : panic(s, p0, p1)) - -#define WAIT_QUEUE_CHECK(wq) \ -MACRO_BEGIN \ - queue_t q2 = &(wq)->wq_queue; \ - wait_queue_element_t wqe2 = (wait_queue_element_t) queue_first(q2); \ - while (!queue_end(q2, (queue_entry_t)wqe2)) { \ - WAIT_QUEUE_ELEMENT_CHECK((wq), wqe2); \ - wqe2 = (wait_queue_element_t) queue_next((queue_t) wqe2); \ - } \ -MACRO_END - -#define WAIT_QUEUE_SET_CHECK(wqs) \ -MACRO_BEGIN \ - queue_t q2 = &(wqs)->wqs_setlinks; \ - wait_queue_link_t wql2 = (wait_queue_link_t) queue_first(q2); \ - while (!queue_end(q2, (queue_entry_t)wql2)) { \ - WAIT_QUEUE_SET_LINK_CHECK((wqs), wql2); \ - wql2 = (wait_queue_link_t) wql2->wql_setlinks.next; \ - } \ -MACRO_END - -#else /* !_WAIT_QUEUE_DEBUG_ */ - -#define WQASSERT(e, s, p0, p1) assert(e) - -#define WAIT_QUEUE_CHECK(wq) -#define WAIT_QUEUE_SET_CHECK(wqs) - -#endif /* !_WAIT_QUEUE_DEBUG_ */ - -/* - * Routine: wait_queue_global - * Purpose: - * Indicate if this wait queue is a global wait queue or not. - */ -static boolean_t -wait_queue_global( - wait_queue_t wq) -{ - if ((wq >= wait_queues) && (wq <= (wait_queues + num_wait_queues))) { - return TRUE; - } - return FALSE; -} - - -/* - * Routine: wait_queue_member_locked - * Purpose: - * Indicate if this set queue is a member of the queue - * Conditions: - * The wait queue is locked - * The set queue is just that, a set queue - */ -static boolean_t -wait_queue_member_locked( - wait_queue_t wq, - wait_queue_set_t wq_set) -{ - wait_queue_element_t wq_element; - queue_t q; - - assert(wait_queue_held(wq)); - assert(wait_queue_is_set(wq_set)); - - q = &wq->wq_queue; - - wq_element = (wait_queue_element_t) queue_first(q); - while (!queue_end(q, (queue_entry_t)wq_element)) { - WAIT_QUEUE_ELEMENT_CHECK(wq, wq_element); - if ((wq_element->wqe_type == WAIT_QUEUE_LINK) || - (wq_element->wqe_type == WAIT_QUEUE_LINK_NOALLOC)) { - wait_queue_link_t wql = (wait_queue_link_t)wq_element; - - if (wql->wql_setqueue == wq_set) - return TRUE; - } - wq_element = (wait_queue_element_t) - queue_next((queue_t) wq_element); - } - return FALSE; -} - - -/* - * Routine: wait_queue_member - * Purpose: - * Indicate if this set queue is a member of the queue - * Conditions: - * The set queue is just that, a set queue - */ -boolean_t -wait_queue_member( - wait_queue_t wq, - wait_queue_set_t wq_set) -{ - boolean_t ret; - spl_t s; - - if (!wait_queue_is_set(wq_set)) - return FALSE; - - s = splsched(); - wait_queue_lock(wq); - ret = wait_queue_member_locked(wq, wq_set); - wait_queue_unlock(wq); - splx(s); - - return ret; -} - - -/* - * Routine: wait_queue_link_internal - * Purpose: - * Insert a set wait queue into a wait queue. This - * requires us to link the two together using a wait_queue_link - * structure that was provided. - * Conditions: - * The wait queue being inserted must be inited as a set queue - * The wait_queue_link structure must already be properly typed - */ -static -kern_return_t -wait_queue_link_internal( - wait_queue_t wq, - wait_queue_set_t wq_set, - wait_queue_link_t wql) -{ - wait_queue_element_t wq_element; - queue_t q; - spl_t s; - - if (!wait_queue_is_valid(wq) || !wait_queue_is_set(wq_set)) - return KERN_INVALID_ARGUMENT; - - /* - * There are probably fewer threads and sets associated with - * the wait queue than there are wait queues associated with - * the set. So let's validate it that way. - */ - 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)) { - WAIT_QUEUE_ELEMENT_CHECK(wq, wq_element); - if ((wq_element->wqe_type == WAIT_QUEUE_LINK || - wq_element->wqe_type == WAIT_QUEUE_LINK_NOALLOC) && - ((wait_queue_link_t)wq_element)->wql_setqueue == wq_set) { - wait_queue_unlock(wq); - splx(s); - return KERN_ALREADY_IN_SET; - } - wq_element = (wait_queue_element_t) - queue_next((queue_t) wq_element); - } - - /* - * Not already a member, so we can add it. - */ - wqs_lock(wq_set); - - WAIT_QUEUE_SET_CHECK(wq_set); - - assert(wql->wql_type == WAIT_QUEUE_LINK || - wql->wql_type == WAIT_QUEUE_LINK_NOALLOC); - - wql->wql_queue = wq; - wql_clear_prepost(wql); - queue_enter(&wq->wq_queue, wql, wait_queue_link_t, wql_links); - wql->wql_setqueue = wq_set; - queue_enter(&wq_set->wqs_setlinks, wql, wait_queue_link_t, wql_setlinks); - - wqs_unlock(wq_set); - wait_queue_unlock(wq); - splx(s); - - return KERN_SUCCESS; -} - -/* - * Routine: wait_queue_link_noalloc - * Purpose: - * Insert a set 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 set queue - */ -kern_return_t -wait_queue_link_noalloc( - wait_queue_t wq, - wait_queue_set_t wq_set, - wait_queue_link_t wql) -{ - wql->wql_type = WAIT_QUEUE_LINK_NOALLOC; - return wait_queue_link_internal(wq, wq_set, wql); -} - -/* - * Routine: wait_queue_link - * Purpose: - * Insert a set 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 set queue - */ -kern_return_t -wait_queue_link( - wait_queue_t wq, - wait_queue_set_t wq_set) -{ - wait_queue_link_t wql; - kern_return_t ret; - - wql = (wait_queue_link_t) zalloc(_wait_queue_link_zone); - if (wql == WAIT_QUEUE_LINK_NULL) - return KERN_RESOURCE_SHORTAGE; - - wql->wql_type = WAIT_QUEUE_LINK; - ret = wait_queue_link_internal(wq, wq_set, wql); - if (ret != KERN_SUCCESS) - zfree(_wait_queue_link_zone, wql); - - return ret; -} - -wait_queue_link_t -wait_queue_link_allocate(void) -{ - wait_queue_link_t wql; - - wql = zalloc(_wait_queue_link_zone); /* Can't fail */ - bzero(wql, sizeof(*wql)); - wql->wql_type = WAIT_QUEUE_UNLINKED; - - return wql; -} - -kern_return_t -wait_queue_link_free(wait_queue_link_t wql) -{ - zfree(_wait_queue_link_zone, wql); - return KERN_SUCCESS; -} - - -/* - * Routine: wait_queue_unlink_locked - * Purpose: - * Undo the linkage between a wait queue and a set. - */ -static void -wait_queue_unlink_locked( - wait_queue_t wq, - wait_queue_set_t wq_set, - wait_queue_link_t wql) -{ - assert(wait_queue_held(wq)); - assert(wait_queue_held(&wq_set->wqs_wait_queue)); - - wql->wql_queue = WAIT_QUEUE_NULL; - queue_remove(&wq->wq_queue, wql, wait_queue_link_t, wql_links); - wql->wql_setqueue = WAIT_QUEUE_SET_NULL; - queue_remove(&wq_set->wqs_setlinks, wql, wait_queue_link_t, wql_setlinks); - if (wql_is_preposted(wql)) { - queue_t ppq = &wq_set->wqs_preposts; - queue_remove(ppq, wql, wait_queue_link_t, wql_preposts); - } - wql->wql_type = WAIT_QUEUE_UNLINKED; - - WAIT_QUEUE_CHECK(wq); - WAIT_QUEUE_SET_CHECK(wq_set); -} - -/* - * Routine: wait_queue_unlink_nofree - * Purpose: - * Remove the linkage between a wait queue and a set, - * returning the linkage structure to the caller to - * free later. - * Conditions: - * The wait queue being must be a member set queue - */ -kern_return_t -wait_queue_unlink_nofree( - wait_queue_t wq, - wait_queue_set_t wq_set, - wait_queue_link_t *wqlp) -{ - wait_queue_element_t wq_element; - wait_queue_link_t wql; - queue_t q; - spl_t s; - - if (!wait_queue_is_valid(wq) || !wait_queue_is_set(wq_set)) { - return KERN_INVALID_ARGUMENT; - } - 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)) { - WAIT_QUEUE_ELEMENT_CHECK(wq, wq_element); - if (wq_element->wqe_type == WAIT_QUEUE_LINK || - wq_element->wqe_type == WAIT_QUEUE_LINK_NOALLOC) { - - wql = (wait_queue_link_t)wq_element; - - if (wql->wql_setqueue == wq_set) { - - wqs_lock(wq_set); - wait_queue_unlink_locked(wq, wq_set, wql); - wqs_unlock(wq_set); - wait_queue_unlock(wq); - splx(s); - *wqlp = wql; - return KERN_SUCCESS; - } - } - wq_element = (wait_queue_element_t) - queue_next((queue_t) wq_element); - } - wait_queue_unlock(wq); - splx(s); - return KERN_NOT_IN_SET; -} - -/* - * Routine: wait_queue_unlink - * Purpose: - * Remove the linkage between a wait queue and a set, - * freeing the linkage structure. - * Conditions: - * The wait queue being must be a member set queue - */ -kern_return_t -wait_queue_unlink( - wait_queue_t wq, - wait_queue_set_t wq_set) -{ - wait_queue_element_t wq_element; - wait_queue_link_t wql; - queue_t q; - spl_t s; - - if (!wait_queue_is_valid(wq) || !wait_queue_is_set(wq_set)) { - return KERN_INVALID_ARGUMENT; - } - 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)) { - WAIT_QUEUE_ELEMENT_CHECK(wq, wq_element); - if (wq_element->wqe_type == WAIT_QUEUE_LINK || - wq_element->wqe_type == WAIT_QUEUE_LINK_NOALLOC) { - - wql = (wait_queue_link_t)wq_element; - - if (wql->wql_setqueue == wq_set) { - boolean_t alloced; - - alloced = (wql->wql_type == WAIT_QUEUE_LINK); - wqs_lock(wq_set); - wait_queue_unlink_locked(wq, wq_set, wql); - wqs_unlock(wq_set); - wait_queue_unlock(wq); - splx(s); - if (alloced) - zfree(_wait_queue_link_zone, wql); - return KERN_SUCCESS; - } - } - wq_element = (wait_queue_element_t) - queue_next((queue_t) wq_element); - } - wait_queue_unlock(wq); - splx(s); - return KERN_NOT_IN_SET; -} - -/* - * Routine: wait_queue_unlink_all_nofree_locked - * Purpose: - * Remove the linkage between a wait queue and all its sets. - * All the linkage structures are returned to the caller for - * later freeing. - * Conditions: - * Wait queue locked. - */ - -static void -wait_queue_unlink_all_nofree_locked( - wait_queue_t wq, - queue_t links) -{ - wait_queue_element_t wq_element; - wait_queue_element_t wq_next_element; - wait_queue_set_t wq_set; - wait_queue_link_t wql; - 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)) { - - WAIT_QUEUE_ELEMENT_CHECK(wq, wq_element); - wq_next_element = (wait_queue_element_t) - queue_next((queue_t) wq_element); - - if (wq_element->wqe_type == WAIT_QUEUE_LINK || - wq_element->wqe_type == WAIT_QUEUE_LINK_NOALLOC) { - wql = (wait_queue_link_t)wq_element; - wq_set = wql->wql_setqueue; - wqs_lock(wq_set); - wait_queue_unlink_locked(wq, wq_set, wql); - wqs_unlock(wq_set); - enqueue(links, &wql->wql_links); - } - wq_element = wq_next_element; - } -} - -/* - * Routine: wait_queue_unlink_all_nofree - * Purpose: - * Remove the linkage between a wait queue and all its sets. - * All the linkage structures are returned to the caller for - * later freeing. - * Conditions: - * Nothing of interest locked. - */ - -kern_return_t -wait_queue_unlink_all_nofree( - wait_queue_t wq, - queue_t links) -{ - spl_t s; - - if (!wait_queue_is_valid(wq)) { - return KERN_INVALID_ARGUMENT; - } - - s = splsched(); - wait_queue_lock(wq); - wait_queue_unlink_all_nofree_locked(wq, links); - wait_queue_unlock(wq); - splx(s); - - return(KERN_SUCCESS); -} - -/* - * Routine: wait_queue_unlink_all_locked - * Purpose: - * Remove the linkage between a locked wait queue and all its - * sets and enqueue the allocated ones onto the links queue - * provided. - * Conditions: - * Wait queue locked. - */ -static void -wait_queue_unlink_all_locked( - wait_queue_t wq, - queue_t links) -{ - wait_queue_element_t wq_element; - wait_queue_element_t wq_next_element; - wait_queue_set_t wq_set; - wait_queue_link_t wql; - 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)) { - boolean_t alloced; - - WAIT_QUEUE_ELEMENT_CHECK(wq, wq_element); - wq_next_element = (wait_queue_element_t) - queue_next((queue_t) wq_element); - - alloced = (wq_element->wqe_type == WAIT_QUEUE_LINK); - if (alloced || wq_element->wqe_type == WAIT_QUEUE_LINK_NOALLOC) { - wql = (wait_queue_link_t)wq_element; - wq_set = wql->wql_setqueue; - wqs_lock(wq_set); - wait_queue_unlink_locked(wq, wq_set, wql); - wqs_unlock(wq_set); - if (alloced) - enqueue(links, &wql->wql_links); - } - wq_element = wq_next_element; - } - -} - - -/* - * Routine: wait_queue_unlink_all - * Purpose: - * Remove the linkage between a wait queue and all its sets. - * All the linkage structures that were allocated internally - * are freed. The others are the caller's responsibility. - * Conditions: - * Nothing of interest locked. - */ - -kern_return_t -wait_queue_unlink_all( - wait_queue_t wq) -{ - wait_queue_link_t wql; - queue_head_t links_queue_head; - queue_t links = &links_queue_head; - spl_t s; - - if (!wait_queue_is_valid(wq)) { - return KERN_INVALID_ARGUMENT; - } - - queue_init(links); - - s = splsched(); - wait_queue_lock(wq); - wait_queue_unlink_all_locked(wq, links); - wait_queue_unlock(wq); - splx(s); - - while(!queue_empty(links)) { - wql = (wait_queue_link_t) dequeue(links); - zfree(_wait_queue_link_zone, wql); - } - - return(KERN_SUCCESS); -} - -/* legacy interface naming */ -kern_return_t -wait_subqueue_unlink_all( - wait_queue_set_t wq_set) -{ - return wait_queue_set_unlink_all(wq_set); -} - - -/* - * Routine: wait_queue_set_unlink_all_nofree - * Purpose: - * Remove the linkage between a set wait queue and all its - * member wait queues and all the sets it may be a member of. - * The links structures are returned for later freeing by the - * caller. - * Conditions: - * The wait queue must be a set - */ -kern_return_t -wait_queue_set_unlink_all_nofree( - wait_queue_set_t wq_set, - queue_t links) -{ - wait_queue_link_t wql; - wait_queue_t wq; - queue_t q; - spl_t s; - - if (!wait_queue_is_set(wq_set)) { - return KERN_INVALID_ARGUMENT; - } - -retry: - s = splsched(); - wqs_lock(wq_set); - - /* remove the wait queues that are members of our set */ - q = &wq_set->wqs_setlinks; - - wql = (wait_queue_link_t)queue_first(q); - while (!queue_end(q, (queue_entry_t)wql)) { - WAIT_QUEUE_SET_LINK_CHECK(wq_set, wql); - wq = wql->wql_queue; - if (wait_queue_lock_try(wq)) { - wait_queue_unlink_locked(wq, wq_set, wql); - wait_queue_unlock(wq); - enqueue(links, &wql->wql_links); - wql = (wait_queue_link_t)queue_first(q); - } else { - wqs_unlock(wq_set); - splx(s); - delay(1); - goto retry; - } - } - - /* remove this set from sets it belongs to */ - wait_queue_unlink_all_nofree_locked(&wq_set->wqs_wait_queue, links); - - wqs_unlock(wq_set); - splx(s); - - return(KERN_SUCCESS); -} - -/* - * Routine: wait_queue_set_unlink_all - * Purpose: - * Remove the linkage between a set wait queue and all its - * member wait queues and all the sets it may be members of. - * The link structures are freed for those links which were - * dynamically allocated. - * Conditions: - * The wait queue must be a set - */ -kern_return_t -wait_queue_set_unlink_all( - wait_queue_set_t wq_set) -{ - wait_queue_link_t wql; - wait_queue_t wq; - queue_t q; - queue_head_t links_queue_head; - queue_t links = &links_queue_head; - spl_t s; - - if (!wait_queue_is_set(wq_set)) { - return KERN_INVALID_ARGUMENT; - } - - queue_init(links); - -retry: - s = splsched(); - wqs_lock(wq_set); - - /* remove the wait queues that are members of our set */ - q = &wq_set->wqs_setlinks; - - wql = (wait_queue_link_t)queue_first(q); - while (!queue_end(q, (queue_entry_t)wql)) { - WAIT_QUEUE_SET_LINK_CHECK(wq_set, wql); - wq = wql->wql_queue; - if (wait_queue_lock_try(wq)) { - boolean_t alloced; - - alloced = (wql->wql_type == WAIT_QUEUE_LINK); - wait_queue_unlink_locked(wq, wq_set, wql); - wait_queue_unlock(wq); - if (alloced) - enqueue(links, &wql->wql_links); - wql = (wait_queue_link_t)queue_first(q); - } else { - wqs_unlock(wq_set); - splx(s); - delay(1); - goto retry; - } - } - - - /* remove this set from sets it belongs to */ - wait_queue_unlink_all_locked(&wq_set->wqs_wait_queue, links); - - wqs_unlock(wq_set); - splx(s); - - while (!queue_empty (links)) { - wql = (wait_queue_link_t) dequeue(links); - zfree(_wait_queue_link_zone, wql); - } - return(KERN_SUCCESS); -} - -kern_return_t -wait_queue_set_unlink_one( - wait_queue_set_t wq_set, - wait_queue_link_t wql) -{ - wait_queue_t wq; - spl_t s; - - assert(wait_queue_is_set(wq_set)); - -retry: - s = splsched(); - wqs_lock(wq_set); - - WAIT_QUEUE_SET_CHECK(wq_set); - - /* Already unlinked, e.g. by selclearthread() */ - if (wql->wql_type == WAIT_QUEUE_UNLINKED) { - goto out; - } - - WAIT_QUEUE_SET_LINK_CHECK(wq_set, wql); - - /* On a wait queue, and we hold set queue lock ... */ - wq = wql->wql_queue; - if (wait_queue_lock_try(wq)) { - wait_queue_unlink_locked(wq, wq_set, wql); - wait_queue_unlock(wq); - } else { - wqs_unlock(wq_set); - splx(s); - delay(1); - goto retry; - } - -out: - wqs_unlock(wq_set); - splx(s); - - return KERN_SUCCESS; -} - -/* - * Routine: wait_queue_assert_wait64_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. - * The waiting thread is assumed locked. - * - */ -__private_extern__ wait_result_t -wait_queue_assert_wait64_locked( - wait_queue_t wq, - event64_t event, - wait_interrupt_t interruptible, - wait_timeout_urgency_t urgency, - uint64_t deadline, - uint64_t leeway, - thread_t thread) -{ - wait_result_t wait_result; - boolean_t realtime; - - if (!wait_queue_assert_possible(thread)) - panic("wait_queue_assert_wait64_locked"); - - if (wq->wq_type == _WAIT_QUEUE_SET_inited) { - wait_queue_set_t wqs = (wait_queue_set_t)wq; - - if (event == NO_EVENT64 && wqs_is_preposted(wqs)) - return (thread->wait_result = THREAD_AWAKENED); - } - - /* - * Realtime threads get priority for wait queue placements. - * This allows wait_queue_wakeup_one to prefer a waiting - * realtime thread, similar in principle to performing - * a wait_queue_wakeup_all and allowing scheduler prioritization - * to run the realtime thread, but without causing the - * lock contention of that scenario. - */ - realtime = (thread->sched_pri >= BASEPRI_REALTIME); - - /* - * 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. - */ - wait_result = thread_mark_wait_locked(thread, interruptible); - if (wait_result == THREAD_WAITING) { - if (!wq->wq_fifo - || (thread->options & TH_OPT_VMPRIV) - || realtime) - 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; - - if (deadline != 0) { - - if (!timer_call_enter_with_leeway(&thread->wait_timer, NULL, - deadline, leeway, urgency, FALSE)) - thread->wait_timer_active++; - thread->wait_timer_is_set = TRUE; - } - if (wait_queue_global(wq)) { - wq->wq_eventmask = wq->wq_eventmask | CAST_TO_EVENT_MASK(event); - } - - } - return(wait_result); -} - -/* - * 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. - */ -wait_result_t -wait_queue_assert_wait( - wait_queue_t wq, - event_t event, - wait_interrupt_t interruptible, - uint64_t deadline) -{ - spl_t s; - wait_result_t ret; - thread_t thread = current_thread(); - - /* If it is an invalid wait queue, you can't wait on it */ - if (!wait_queue_is_valid(wq)) - return (thread->wait_result = THREAD_RESTART); - - s = splsched(); - wait_queue_lock(wq); - thread_lock(thread); - ret = wait_queue_assert_wait64_locked(wq, CAST_DOWN(event64_t,event), - interruptible, - TIMEOUT_URGENCY_SYS_NORMAL, - deadline, 0, - thread); - thread_unlock(thread); - wait_queue_unlock(wq); - splx(s); - return(ret); -} - -/* - * Routine: wait_queue_assert_wait_with_leeway - * Purpose: - * Insert the current thread into the supplied wait queue - * waiting for a particular event to be posted to that queue. - * Deadline values are specified with urgency and leeway. - * - * Conditions: - * nothing of interest locked. - */ -wait_result_t -wait_queue_assert_wait_with_leeway( - wait_queue_t wq, - event_t event, - wait_interrupt_t interruptible, - wait_timeout_urgency_t urgency, - uint64_t deadline, - uint64_t leeway) -{ - spl_t s; - wait_result_t ret; - thread_t thread = current_thread(); - - /* If it is an invalid wait queue, you can't wait on it */ - if (!wait_queue_is_valid(wq)) - return (thread->wait_result = THREAD_RESTART); - - s = splsched(); - wait_queue_lock(wq); - thread_lock(thread); - ret = wait_queue_assert_wait64_locked(wq, CAST_DOWN(event64_t,event), - interruptible, - urgency, deadline, leeway, - thread); - thread_unlock(thread); - wait_queue_unlock(wq); - splx(s); - return(ret); -} - -/* - * Routine: wait_queue_assert_wait64 - * 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. - */ -wait_result_t -wait_queue_assert_wait64( - wait_queue_t wq, - event64_t event, - wait_interrupt_t interruptible, - uint64_t deadline) -{ - spl_t s; - wait_result_t ret; - thread_t thread = current_thread(); - - /* If it is an invalid wait queue, you cant wait on it */ - if (!wait_queue_is_valid(wq)) - return (thread->wait_result = THREAD_RESTART); - - s = splsched(); - wait_queue_lock(wq); - thread_lock(thread); - ret = wait_queue_assert_wait64_locked(wq, event, interruptible, - TIMEOUT_URGENCY_SYS_NORMAL, - deadline, 0, - thread); - thread_unlock(thread); - wait_queue_unlock(wq); - splx(s); - return(ret); -} - -/* - * Routine: wait_queue_assert_wait64_with_leeway - * Purpose: - * Insert the current thread into the supplied wait queue - * waiting for a particular event to be posted to that queue. - * Deadline values are specified with urgency and leeway. - * Conditions: - * nothing of interest locked. - */ -wait_result_t -wait_queue_assert_wait64_with_leeway( - wait_queue_t wq, - event64_t event, - wait_interrupt_t interruptible, - wait_timeout_urgency_t urgency, - uint64_t deadline, - uint64_t leeway) -{ - spl_t s; - wait_result_t ret; - thread_t thread = current_thread(); - - /* If it is an invalid wait queue, you cant wait on it */ - if (!wait_queue_is_valid(wq)) - return (thread->wait_result = THREAD_RESTART); - - s = splsched(); - wait_queue_lock(wq); - thread_lock(thread); - ret = wait_queue_assert_wait64_locked(wq, event, interruptible, - urgency, deadline, leeway, - thread); - thread_unlock(thread); - wait_queue_unlock(wq); - splx(s); - return(ret); -} - -/* - * Routine: _wait_queue_select64_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 - */ -static void -_wait_queue_select64_all( - wait_queue_t wq, - event64_t event, - queue_t wake_queue) -{ - wait_queue_element_t wq_element; - wait_queue_element_t wqe_next; - unsigned long eventmask = 0; - boolean_t is_queue_global = FALSE; - queue_t q; - - is_queue_global = wait_queue_global(wq); - if (is_queue_global) { - eventmask = CAST_TO_EVENT_MASK(event); - if ((wq->wq_eventmask & eventmask) != eventmask) { - return; - } - eventmask = 0; - } - q = &wq->wq_queue; - - wq_element = (wait_queue_element_t) queue_first(q); - while (!queue_end(q, (queue_entry_t)wq_element)) { - WAIT_QUEUE_ELEMENT_CHECK(wq, 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_type == WAIT_QUEUE_LINK || - wq_element->wqe_type == WAIT_QUEUE_LINK_NOALLOC) { - wait_queue_link_t wql = (wait_queue_link_t)wq_element; - wait_queue_set_t set_queue = wql->wql_setqueue; - - /* - * We have to check the set wait queue. If it is marked - * as pre-post, and it is the "generic event" then mark - * it pre-posted now (if not already). - */ - wqs_lock(set_queue); - if (event == NO_EVENT64 && set_queue->wqs_prepost && !wql_is_preposted(wql)) { - queue_t ppq = &set_queue->wqs_preposts; - queue_enter(ppq, wql, wait_queue_link_t, wql_preposts); - } - if (! wait_queue_empty(&set_queue->wqs_wait_queue)) - _wait_queue_select64_all(&set_queue->wqs_wait_queue, event, wake_queue); - wqs_unlock(set_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)(void *)wq_element; - - if (t->wait_event == event) { - thread_lock(t); - remqueue((queue_entry_t) t); - enqueue (wake_queue, (queue_entry_t) t); - t->wait_queue = WAIT_QUEUE_NULL; - t->wait_event = NO_EVENT64; - t->at_safe_point = FALSE; - /* returned locked */ - } else { - if (is_queue_global) { - eventmask = eventmask | - CAST_TO_EVENT_MASK(t->wait_event); - } - } - } - wq_element = wqe_next; - } - /* Update event mask if global wait queue */ - if (is_queue_global) { - wq->wq_eventmask = eventmask; - } - -} - -/* - * Routine: wait_queue_wakeup64_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 pair - */ -__private_extern__ kern_return_t -wait_queue_wakeup64_all_locked( - wait_queue_t wq, - event64_t event, - wait_result_t result, - boolean_t unlock) -{ - queue_head_t wake_queue_head; - queue_t q = &wake_queue_head; - kern_return_t res; - -// assert(wait_queue_held(wq)); -// if(!wq->wq_interlock.lock_data) { /* (BRINGUP */ -// panic("wait_queue_wakeup64_all_locked: lock not held on %p\n", wq); /* (BRINGUP) */ -// } - - 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_select64_all(wq, event, q); - if (unlock) - wait_queue_unlock(wq); - - /* - * For each thread, set it running. - */ - res = KERN_NOT_WAITING; - while (!queue_empty (q)) { - thread_t thread = (thread_t)(void *) dequeue(q); - res = thread_go(thread, result); - assert(res == KERN_SUCCESS); - thread_unlock(thread); - } - return res; -} - - -/* - * 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 pair - */ -kern_return_t -wait_queue_wakeup_all( - wait_queue_t wq, - event_t event, - wait_result_t result) -{ - kern_return_t ret; - spl_t s; - - if (!wait_queue_is_valid(wq)) { - return KERN_INVALID_ARGUMENT; - } - - s = splsched(); - wait_queue_lock(wq); -// if(!wq->wq_interlock.lock_data) { /* (BRINGUP */ -// panic("wait_queue_wakeup_all: we did not get the lock on %p\n", wq); /* (BRINGUP) */ -// } - ret = wait_queue_wakeup64_all_locked( - wq, CAST_DOWN(event64_t,event), - result, TRUE); - /* lock released */ - splx(s); - return ret; -} - -/* - * Routine: wait_queue_wakeup64_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 pair - */ -kern_return_t -wait_queue_wakeup64_all( - wait_queue_t wq, - event64_t event, - wait_result_t result) -{ - kern_return_t ret; - spl_t s; - - if (!wait_queue_is_valid(wq)) { - return KERN_INVALID_ARGUMENT; - } - - s = splsched(); - wait_queue_lock(wq); - ret = wait_queue_wakeup64_all_locked(wq, event, result, TRUE); - /* lock released */ - splx(s); - return ret; -} - -/* - * Routine: _wait_queue_select64_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/LIFO. - */ -static thread_t -_wait_queue_select64_one( - wait_queue_t wq, - event64_t event) -{ - wait_queue_element_t wq_element; - wait_queue_element_t wqe_next; - thread_t t = THREAD_NULL; - thread_t fifo_thread = THREAD_NULL; - boolean_t is_queue_fifo = TRUE; - boolean_t is_queue_global = FALSE; - boolean_t thread_imp_donor = FALSE; - boolean_t realtime = FALSE; - unsigned long eventmask = 0; - queue_t q; - - if (wait_queue_global(wq)) { - eventmask = CAST_TO_EVENT_MASK(event); - if ((wq->wq_eventmask & eventmask) != eventmask) { - return THREAD_NULL; - } - eventmask = 0; - is_queue_global = TRUE; -#if IMPORTANCE_INHERITANCE - is_queue_fifo = FALSE; -#endif /* IMPORTANCE_INHERITANCE */ - } - - q = &wq->wq_queue; - - wq_element = (wait_queue_element_t) queue_first(q); - while (!queue_end(q, (queue_entry_t)wq_element)) { - WAIT_QUEUE_ELEMENT_CHECK(wq, 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_type == WAIT_QUEUE_LINK || - wq_element->wqe_type == WAIT_QUEUE_LINK_NOALLOC) { - wait_queue_link_t wql = (wait_queue_link_t)wq_element; - wait_queue_set_t set_queue = wql->wql_setqueue; - - /* - * We have to check the set wait queue. If the set - * supports pre-posting, it isn't already preposted, - * and we didn't find a thread in the set, then mark it. - * - * If we later find a thread, there may be a spurious - * pre-post here on this set. The wait side has to check - * for that either pre- or post-wait. - */ - wqs_lock(set_queue); - if (! wait_queue_empty(&set_queue->wqs_wait_queue)) { - t = _wait_queue_select64_one(&set_queue->wqs_wait_queue, event); - } - if (t != THREAD_NULL) { - wqs_unlock(set_queue); - return t; - } - if (event == NO_EVENT64 && set_queue->wqs_prepost && !wql_is_preposted(wql)) { - queue_t ppq = &set_queue->wqs_preposts; - queue_enter(ppq, wql, wait_queue_link_t, wql_preposts); - } - wqs_unlock(set_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. - */ - t = (thread_t)(void *)wq_element; - if (t->wait_event == event) { - if (fifo_thread == THREAD_NULL) { - fifo_thread = t; - } -#if IMPORTANCE_INHERITANCE - /* - * Checking imp donor bit does not need thread lock or - * or task lock since we have the wait queue lock and - * thread can not be removed from it without acquiring - * wait queue lock. The imp donor bit may change - * once we read its value, but it is ok to wake - * a thread while someone drops importance assertion - * on the that thread. - */ - thread_imp_donor = task_is_importance_donor(t->task); -#endif /* IMPORTANCE_INHERITANCE */ - realtime = (t->sched_pri >= BASEPRI_REALTIME); - if (is_queue_fifo || thread_imp_donor || realtime || - (t->options & TH_OPT_VMPRIV)) { - thread_lock(t); - remqueue((queue_entry_t) t); - t->wait_queue = WAIT_QUEUE_NULL; - t->wait_event = NO_EVENT64; - t->at_safe_point = FALSE; - return t; /* still locked */ - } - } - if (is_queue_global) { - eventmask = eventmask | CAST_TO_EVENT_MASK(t->wait_event); - } - t = THREAD_NULL; - } - wq_element = wqe_next; - } - - if (is_queue_global) { - wq->wq_eventmask = eventmask; - } -#if IMPORTANCE_INHERITANCE - if (fifo_thread != THREAD_NULL) { - thread_lock(fifo_thread); - remqueue((queue_entry_t) fifo_thread); - fifo_thread->wait_queue = WAIT_QUEUE_NULL; - fifo_thread->wait_event = NO_EVENT64; - fifo_thread->at_safe_point = FALSE; - return fifo_thread; /* still locked */ - } -#endif /* IMPORTANCE_INHERITANCE */ - return THREAD_NULL; -} - - -/* - * Routine: wait_queue_pull_thread_locked - * Purpose: - * Pull a thread off its 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((queue_entry_t)thread ); - thread->wait_queue = WAIT_QUEUE_NULL; - thread->wait_event = NO_EVENT64; - thread->at_safe_point = FALSE; - if (unlock) - wait_queue_unlock(waitq); -} - - -/* - * Routine: wait_queue_select64_thread - * Purpose: - * Look for a thread and remove it from the queues, if - * (and only if) the thread is waiting on the supplied - * 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) - */ -static kern_return_t -_wait_queue_select64_thread( - wait_queue_t wq, - event64_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; - - thread_lock(thread); - - if ((thread->wait_queue == wq) && (thread->wait_event == event)) { - remqueue((queue_entry_t) thread); - thread->at_safe_point = FALSE; - thread->wait_event = NO_EVENT64; - 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 sets. 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)) { - WAIT_QUEUE_ELEMENT_CHECK(wq, wq_element); - wqe_next = (wait_queue_element_t) - queue_next((queue_t) wq_element); - - if (wq_element->wqe_type == WAIT_QUEUE_LINK || - wq_element->wqe_type == WAIT_QUEUE_LINK_NOALLOC) { - wait_queue_link_t wql = (wait_queue_link_t)wq_element; - wait_queue_set_t set_queue = wql->wql_setqueue; - - wqs_lock(set_queue); - if (! wait_queue_empty(&set_queue->wqs_wait_queue)) { - res = _wait_queue_select64_thread(&set_queue->wqs_wait_queue, - event, - thread); - } - wqs_unlock(set_queue); - if (res == KERN_SUCCESS) - return KERN_SUCCESS; - } - wq_element = wqe_next; - } - return res; -} - - -/* - * Routine: wait_queue_wakeup64_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 - */ -__private_extern__ thread_t -wait_queue_wakeup64_identity_locked( - wait_queue_t wq, - event64_t event, - wait_result_t result, - boolean_t unlock) -{ - kern_return_t res; - thread_t thread; - - assert(wait_queue_held(wq)); - - thread = _wait_queue_select64_one(wq, event); - if (unlock) - wait_queue_unlock(wq); - - if (thread) { - res = thread_go(thread, result); - assert(res == KERN_SUCCESS); - } - return thread; /* still locked if not NULL */ -} - - -/* - * Routine: wait_queue_wakeup64_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 pair - */ -__private_extern__ kern_return_t -wait_queue_wakeup64_one_locked( - wait_queue_t wq, - event64_t event, - wait_result_t result, - boolean_t unlock) -{ - thread_t thread; - - assert(wait_queue_held(wq)); - - thread = _wait_queue_select64_one(wq, event); - if (unlock) - wait_queue_unlock(wq); - - if (thread) { - kern_return_t res; - - res = thread_go(thread, result); - assert(res == KERN_SUCCESS); - thread_unlock(thread); - return res; - } - - 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 pair - */ -kern_return_t -wait_queue_wakeup_one( - wait_queue_t wq, - event_t event, - wait_result_t result, - int priority) -{ - thread_t thread; - spl_t s; - - if (!wait_queue_is_valid(wq)) { - return KERN_INVALID_ARGUMENT; - } - - s = splsched(); - wait_queue_lock(wq); - thread = _wait_queue_select64_one(wq, CAST_DOWN(event64_t,event)); - wait_queue_unlock(wq); - - if (thread) { - kern_return_t res; - - if (thread->sched_pri < priority) { - if (priority <= MAXPRI) { - set_sched_pri(thread, priority); - - thread->was_promoted_on_wakeup = 1; - thread->sched_flags |= TH_SFLAG_PROMOTED; - } - } - res = thread_go(thread, result); - assert(res == KERN_SUCCESS); - thread_unlock(thread); - splx(s); - return res; - } - - splx(s); - return KERN_NOT_WAITING; -} - -/* - * Routine: wait_queue_wakeup64_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 pair - */ -kern_return_t -wait_queue_wakeup64_one( - wait_queue_t wq, - event64_t event, - wait_result_t result) -{ - thread_t thread; - spl_t s; - - if (!wait_queue_is_valid(wq)) { - return KERN_INVALID_ARGUMENT; - } - s = splsched(); - wait_queue_lock(wq); - thread = _wait_queue_select64_one(wq, event); - wait_queue_unlock(wq); - - if (thread) { - kern_return_t res; - - res = thread_go(thread, result); - assert(res == KERN_SUCCESS); - thread_unlock(thread); - splx(s); - return res; - } - - splx(s); - return KERN_NOT_WAITING; -} - - -/* - * Routine: wait_queue_wakeup64_thread_locked - * Purpose: - * Wakeup the particular thread that was specified if and only - * it was in this wait queue (or one of it's set 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 - */ -__private_extern__ kern_return_t -wait_queue_wakeup64_thread_locked( - wait_queue_t wq, - event64_t event, - thread_t thread, - wait_result_t 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_select64_thread(wq, event, thread); - if (unlock) - wait_queue_unlock(wq); - - if (res != KERN_SUCCESS) - return KERN_NOT_WAITING; - - res = thread_go(thread, result); - assert(res == KERN_SUCCESS); - thread_unlock(thread); - return res; -} - -/* - * 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 set 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, - wait_result_t result) -{ - kern_return_t res; - spl_t s; - - if (!wait_queue_is_valid(wq)) { - return KERN_INVALID_ARGUMENT; - } - - s = splsched(); - wait_queue_lock(wq); - res = _wait_queue_select64_thread(wq, CAST_DOWN(event64_t,event), thread); - wait_queue_unlock(wq); - - if (res == KERN_SUCCESS) { - res = thread_go(thread, result); - assert(res == KERN_SUCCESS); - thread_unlock(thread); - splx(s); - return res; - } - splx(s); - return KERN_NOT_WAITING; -} - -/* - * Routine: wait_queue_wakeup64_thread - * Purpose: - * Wakeup the particular thread that was specified if and only - * it was in this wait queue (or one of it's set's 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: - * 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_wakeup64_thread( - wait_queue_t wq, - event64_t event, - thread_t thread, - wait_result_t result) -{ - kern_return_t res; - spl_t s; - - if (!wait_queue_is_valid(wq)) { - return KERN_INVALID_ARGUMENT; - } - - s = splsched(); - wait_queue_lock(wq); - res = _wait_queue_select64_thread(wq, event, thread); - wait_queue_unlock(wq); - - if (res == KERN_SUCCESS) { - res = thread_go(thread, result); - assert(res == KERN_SUCCESS); - - thread_unlock(thread); - splx(s); - return res; - } - splx(s); - return KERN_NOT_WAITING; -}