#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;
}
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;
}
void
wait_queue_free(
wait_queue_t wq)
{
assert(queue_empty(&wq->wq_queue));
kfree((vm_offset_t)wq, sizeof(struct wait_queue));
}
void
wait_queue_lock(
wait_queue_t wq)
{
#ifdef __ppc__
vm_offset_t pc;
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
}
boolean_t
wait_queue_lock_try(
wait_queue_t wq)
{
return hw_lock_try(&wq->wq_interlock);
}
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;
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;
}
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;
}
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;
}
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;
}
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");
}
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);
}
return(KERN_FAILURE);
}
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);
}
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);
}
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;
}
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);
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);
}
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);
splx(s);
return(ret);
}
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);
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 (sub_queue->wq_isprepost) {
wait_queue_sub_t wqs = (wait_queue_sub_t)sub_queue;
wqs->wqs_refcount++;
}
if (! wait_queue_empty(sub_queue))
_wait_queue_select_all(sub_queue, event, wake_queue);
wait_queue_unlock(sub_queue);
} else {
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;
}
}
wq_element = wqe_next;
}
}
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);
_wait_queue_select_all(wq, event, q);
if (unlock)
wait_queue_unlock(wq);
while (!queue_empty (q)) {
thread_t thread = (thread_t) dequeue(q);
thread_go_locked(thread, result);
thread_unlock(thread);
ret = KERN_SUCCESS;
}
return ret;
}
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);
splx(s);
return ret;
}
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);
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)) {
t = _wait_queue_select_one(sub_queue, event);
}
wait_queue_unlock(sub_queue);
if (t != THREAD_NULL)
return t;
} else {
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;
}
}
wq_element = wqe_next;
}
return THREAD_NULL;
}
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);
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)) {
wait_queue_peek_locked(sub_queue, event, tp, wqp);
}
if (*tp != THREAD_NULL)
return;
wait_queue_unlock(sub_queue);
} else {
thread_t t = (thread_t)wq_element;
if (t->wait_event == event) {
thread_lock(t);
*tp = t;
*wqp = wq;
return;
}
}
wq_element = wqe_next;
}
}
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);
}
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;
return KERN_SUCCESS;
}
thread_unlock(thread);
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;
}
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;
}
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;
}
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;
}
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));
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;
}
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;
}
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;
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;
}
}