OpenSolaris_b135/uts/common/os/waitq.c
/*
* CDDL HEADER START
*
* The contents of this file are subject to the terms of the
* Common Development and Distribution License (the "License").
* You may not use this file except in compliance with the License.
*
* You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
* or http://www.opensolaris.org/os/licensing.
* See the License for the specific language governing permissions
* and limitations under the License.
*
* When distributing Covered Code, include this CDDL HEADER in each
* file and include the License file at usr/src/OPENSOLARIS.LICENSE.
* If applicable, add the following below this CDDL HEADER, with the
* fields enclosed by brackets "[]" replaced with your own identifying
* information: Portions Copyright [yyyy] [name of copyright owner]
*
* CDDL HEADER END
*/
/*
* Copyright 2008 Sun Microsystems, Inc. All rights reserved.
* Use is subject to license terms.
*/
#include <sys/param.h>
#include <sys/systm.h>
#include <sys/thread.h>
#include <sys/class.h>
#include <sys/debug.h>
#include <sys/cpuvar.h>
#include <sys/waitq.h>
#include <sys/cmn_err.h>
#include <sys/time.h>
#include <sys/dtrace.h>
#include <sys/sdt.h>
#include <sys/zone.h>
/*
* Wait queue implementation.
*/
void
waitq_init(waitq_t *wq)
{
DISP_LOCK_INIT(&wq->wq_lock);
wq->wq_first = NULL;
wq->wq_count = 0;
wq->wq_blocked = B_TRUE;
}
void
waitq_fini(waitq_t *wq)
{
ASSERT(wq->wq_count == 0);
ASSERT(wq->wq_first == NULL);
ASSERT(wq->wq_blocked == B_TRUE);
ASSERT(!DISP_LOCK_HELD(&wq->wq_lock));
DISP_LOCK_DESTROY(&wq->wq_lock);
}
/*
* Operations on waitq_t structures.
*
* A wait queue is a singly linked NULL-terminated list with doubly
* linked circular sublists. The singly linked list is in descending
* priority order and FIFO for threads of the same priority. It links
* through the t_link field of the thread structure. The doubly linked
* sublists link threads of the same priority. They use the t_priforw
* and t_priback fields of the thread structure.
*
* Graphically (with priorities in parens):
*
* ________________ _______ _______
* / \ / \ / \
* | | | | | |
* v v v v v v
* t1(60)-->t2(60)-->t3(60)-->t4(50)-->t5(50)-->t6(30)-->t7(0)-->t8(0)
* ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
* | | | | | | | | | |
* \______/ \______/ \_______/ \__/ \_______/
*
* There are three interesting operations on a waitq list: inserting
* a thread into the proper position according to priority; removing a
* thread given a pointer to it; and walking the list, possibly
* removing threads along the way. This design allows all three
* operations to be performed efficiently and easily.
*
* To insert a thread, traverse the list looking for the sublist of
* the same priority as the thread (or one of a lower priority,
* meaning there are no other threads in the list of the same
* priority). This can be done without touching all threads in the
* list by following the links between the first threads in each
* sublist. Given a thread t that is the head of a sublist (the first
* thread of that priority found when following the t_link pointers),
* t->t_priback->t_link points to the head of the next sublist. It's
* important to do this since a waitq may contain thousands of
* threads.
*
* Removing a thread from the list is also efficient. First, the
* t_waitq field contains a pointer to the waitq on which a thread
* is waiting (or NULL if it's not on a waitq). This is used to
* determine if the given thread is on the given waitq without
* searching the list. Assuming it is, if it's not the head of a
* sublist, just remove it from the sublist and use the t_priback
* pointer to find the thread that points to it with t_link. If it is
* the head of a sublist, search for it by walking the sublist heads,
* similar to searching for a given priority level when inserting a
* thread.
*
* To walk the list, simply follow the t_link pointers. Removing
* threads along the way can be done easily if the code maintains a
* pointer to the t_link field that pointed to the thread being
* removed.
*/
static void
waitq_link(waitq_t *wq, kthread_t *t)
{
kthread_t *next_tp;
kthread_t *last_tp;
kthread_t **tpp;
pri_t tpri, next_pri, last_pri = -1;
ASSERT(DISP_LOCK_HELD(&wq->wq_lock));
tpri = DISP_PRIO(t);
tpp = &wq->wq_first;
while ((next_tp = *tpp) != NULL) {
next_pri = DISP_PRIO(next_tp);
if (tpri > next_pri)
break;
last_tp = next_tp->t_priback;
last_pri = next_pri;
tpp = &last_tp->t_link;
}
*tpp = t;
t->t_link = next_tp;
if (last_pri == tpri) {
/* last_tp points to the last thread of this priority */
t->t_priback = last_tp;
t->t_priforw = last_tp->t_priforw;
last_tp->t_priforw->t_priback = t;
last_tp->t_priforw = t;
} else {
t->t_priback = t->t_priforw = t;
}
wq->wq_count++;
t->t_waitq = wq;
}
static void
waitq_unlink(waitq_t *wq, kthread_t *t)
{
kthread_t *nt;
kthread_t **ptl;
ASSERT(THREAD_LOCK_HELD(t));
ASSERT(DISP_LOCK_HELD(&wq->wq_lock));
ASSERT(t->t_waitq == wq);
ptl = &t->t_priback->t_link;
/*
* Is it the head of a priority sublist? If so, need to walk
* the priorities to find the t_link pointer that points to it.
*/
if (*ptl != t) {
/*
* Find the right priority level.
*/
ptl = &t->t_waitq->wq_first;
while ((nt = *ptl) != t)
ptl = &nt->t_priback->t_link;
}
/*
* Remove thread from the t_link list.
*/
*ptl = t->t_link;
/*
* Take it off the priority sublist if there's more than one
* thread there.
*/
if (t->t_priforw != t) {
t->t_priback->t_priforw = t->t_priforw;
t->t_priforw->t_priback = t->t_priback;
}
t->t_link = NULL;
wq->wq_count--;
t->t_waitq = NULL;
t->t_priforw = NULL;
t->t_priback = NULL;
}
/*
* Put specified thread to specified wait queue without dropping thread's lock.
* Returns 1 if thread was successfully placed on project's wait queue, or
* 0 if wait queue is blocked.
*/
int
waitq_enqueue(waitq_t *wq, kthread_t *t)
{
ASSERT(THREAD_LOCK_HELD(t));
ASSERT(t->t_sleepq == NULL);
ASSERT(t->t_waitq == NULL);
ASSERT(t->t_link == NULL);
disp_lock_enter_high(&wq->wq_lock);
/*
* Can't enqueue anything on a blocked wait queue
*/
if (wq->wq_blocked) {
disp_lock_exit_high(&wq->wq_lock);
return (0);
}
/*
* Mark the time when thread is placed on wait queue. The microstate
* accounting code uses this timestamp to determine wait times.
*/
t->t_waitrq = gethrtime_unscaled();
/*
* Mark thread as not swappable. If necessary, it will get
* swapped out when it returns to the userland.
*/
t->t_schedflag |= TS_DONT_SWAP;
DTRACE_SCHED1(cpucaps__sleep, kthread_t *, t);
waitq_link(wq, t);
THREAD_WAIT(t, &wq->wq_lock);
return (1);
}
/*
* Change thread's priority while on the wait queue.
* Dequeue and equeue it again so that it gets placed in the right place.
*/
void
waitq_change_pri(kthread_t *t, pri_t new_pri)
{
waitq_t *wq = t->t_waitq;
ASSERT(THREAD_LOCK_HELD(t));
ASSERT(ISWAITING(t));
ASSERT(wq != NULL);
waitq_unlink(wq, t);
t->t_pri = new_pri;
waitq_link(wq, t);
}
static void
waitq_dequeue(waitq_t *wq, kthread_t *t)
{
ASSERT(THREAD_LOCK_HELD(t));
ASSERT(t->t_waitq == wq);
ASSERT(ISWAITING(t));
waitq_unlink(wq, t);
DTRACE_SCHED1(cpucaps__wakeup, kthread_t *, t);
/*
* Change thread to transition state and drop the wait queue lock. The
* thread will remain locked since its t_lockp points to the
* transition_lock.
*/
THREAD_TRANSITION(t);
}
/*
* Return True iff there are any threads on the specified wait queue.
* The check is done **without holding any locks**.
*/
boolean_t
waitq_isempty(waitq_t *wq)
{
return (wq->wq_count == 0);
}
/*
* Take thread off its wait queue and make it runnable.
* Returns with thread lock held.
*/
void
waitq_setrun(kthread_t *t)
{
waitq_t *wq = t->t_waitq;
ASSERT(THREAD_LOCK_HELD(t));
ASSERT(ISWAITING(t));
if (wq == NULL)
panic("waitq_setrun: thread %p is not on waitq", (void *)t);
waitq_dequeue(wq, t);
CL_SETRUN(t);
}
/*
* Take the first thread off the wait queue and return pointer to it.
*/
static kthread_t *
waitq_takeone(waitq_t *wq)
{
kthread_t *t;
disp_lock_enter(&wq->wq_lock);
/*
* waitq_dequeue drops wait queue lock but leaves the CPU at high PIL.
*/
if ((t = wq->wq_first) != NULL)
waitq_dequeue(wq, wq->wq_first);
else
disp_lock_exit(&wq->wq_lock);
return (t);
}
/*
* Take the first thread off the wait queue and make it runnable.
* Return the pointer to the thread or NULL if waitq is empty
*/
static kthread_t *
waitq_runfirst(waitq_t *wq)
{
kthread_t *t;
t = waitq_takeone(wq);
if (t != NULL) {
/*
* t should have transition lock held.
* CL_SETRUN() will replace it with dispq lock and keep it held.
* thread_unlock() will drop dispq lock and restore PIL.
*/
ASSERT(THREAD_LOCK_HELD(t));
CL_SETRUN(t);
thread_unlock(t);
}
return (t);
}
/*
* Take the first thread off the wait queue and make it runnable.
*/
void
waitq_runone(waitq_t *wq)
{
(void) waitq_runfirst(wq);
}
/*
* Take all threads off the wait queue and make them runnable.
*/
static void
waitq_runall(waitq_t *wq)
{
while (waitq_runfirst(wq) != NULL)
;
}
/*
* Prevent any new threads from entering wait queue and make all threads
* currently on the wait queue runnable. After waitq_block() completion, no
* threads should ever appear on the wait queue untill it is unblocked.
*/
void
waitq_block(waitq_t *wq)
{
ASSERT(!wq->wq_blocked);
disp_lock_enter(&wq->wq_lock);
wq->wq_blocked = B_TRUE;
disp_lock_exit(&wq->wq_lock);
waitq_runall(wq);
ASSERT(waitq_isempty(wq));
}
/*
* Allow threads to be placed on the wait queue.
*/
void
waitq_unblock(waitq_t *wq)
{
disp_lock_enter(&wq->wq_lock);
ASSERT(waitq_isempty(wq));
ASSERT(wq->wq_blocked);
wq->wq_blocked = B_FALSE;
disp_lock_exit(&wq->wq_lock);
}