#include <kern/kern_types.h>
#include <kern/simple_lock.h>
#include <kern/zalloc.h>
#include <kern/queue.h>
#include <kern/spl.h>
#include <mach/sync_policy.h>
#include <kern/mach_param.h>
#include <kern/sched_prim.h>
#include <kern/wait_queue.h>
#include <vm/vm_kern.h>
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;
volatile WaitQueueLink *unused_except_for_debugging;
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;
whsize = compute_wait_hash_size();
qsz = sizeof (struct wait_queue);
whsize = ROUNDDOWN(whsize, qsz);
num_wait_queues = whsize / qsz;
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);
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);
}
kern_return_t
wait_queue_init(
wait_queue_t wq,
int policy)
{
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;
}
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;
}
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;
}
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;
}
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;
}
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;
}
unsigned int wait_queue_set_size(void) { return sizeof(WaitQueueSet); }
unsigned int wait_queue_link_size(void) { return sizeof(WaitQueueLink); }
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
#define WQASSERT(e, s, p0, p1) assert(e)
#define WAIT_QUEUE_CHECK(wq)
#define WAIT_QUEUE_SET_CHECK(wqs)
#endif
static boolean_t
wait_queue_global(
wait_queue_t wq)
{
if ((wq >= wait_queues) && (wq <= (wait_queues + num_wait_queues))) {
return TRUE;
}
return FALSE;
}
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;
}
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;
}
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;
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);
}
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;
}
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);
}
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);
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;
}
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);
}
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;
}
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;
}
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;
}
}
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);
}
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;
}
}
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);
}
kern_return_t
wait_subqueue_unlink_all(
wait_queue_set_t wq_set)
{
return wait_queue_set_unlink_all(wq_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);
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;
}
}
wait_queue_unlink_all_nofree_locked(&wq_set->wqs_wait_queue, links);
wqs_unlock(wq_set);
splx(s);
return(KERN_SUCCESS);
}
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);
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;
}
}
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);
if (wql->wql_type == WAIT_QUEUE_UNLINKED) {
goto out;
}
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);
} else {
wqs_unlock(wq_set);
splx(s);
delay(1);
goto retry;
}
out:
wqs_unlock(wq_set);
splx(s);
return KERN_SUCCESS;
}
__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_AWAKENED);
}
realtime = (thread->sched_pri >= BASEPRI_REALTIME);
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);
}
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 (!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);
}
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 (!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);
}
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 (!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);
}
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 (!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);
}
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);
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 (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 {
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;
} else {
if (is_queue_global) {
eventmask = eventmask |
CAST_TO_EVENT_MASK(t->wait_event);
}
}
}
wq_element = wqe_next;
}
if (is_queue_global) {
wq->wq_eventmask = eventmask;
}
}
__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;
queue_init(q);
_wait_queue_select64_all(wq, event, q);
if (unlock)
wait_queue_unlock(wq);
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;
}
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);
ret = wait_queue_wakeup64_all_locked(
wq, CAST_DOWN(event64_t,event),
result, TRUE);
splx(s);
return ret;
}
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);
splx(s);
return ret;
}
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
}
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);
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)) {
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 {
t = (thread_t)(void *)wq_element;
if (t->wait_event == event) {
if (fifo_thread == THREAD_NULL) {
fifo_thread = t;
}
#if IMPORTANCE_INHERITANCE
thread_imp_donor = task_is_importance_donor(t->task);
#endif
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;
}
}
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;
}
#endif
return THREAD_NULL;
}
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);
}
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;
return KERN_SUCCESS;
}
thread_unlock(thread);
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;
}
__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;
}
__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;
}
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;
}
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;
}
__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));
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;
}
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;
}
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;
}