diff options
Diffstat (limited to 'usr/src/uts/common/os/waitq.c')
| -rw-r--r-- | usr/src/uts/common/os/waitq.c | 386 |
1 files changed, 386 insertions, 0 deletions
diff --git a/usr/src/uts/common/os/waitq.c b/usr/src/uts/common/os/waitq.c new file mode 100644 index 0000000000..802d7afdc4 --- /dev/null +++ b/usr/src/uts/common/os/waitq.c @@ -0,0 +1,386 @@ +/* + * 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 2007 Sun Microsystems, Inc. All rights reserved. + * Use is subject to license terms. + */ + +#pragma ident "%Z%%M% %I% %E% SMI" + +#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 without dropping + * the wait queue lock. + */ + THREAD_TRANSITION_NOLOCK(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", t); + waitq_dequeue(wq, t); + + disp_lock_exit_high(&wq->wq_lock); + 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); + if ((t = wq->wq_first) != NULL) + waitq_dequeue(wq, wq->wq_first); + 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) { + CL_SETRUN(t); + thread_unlock(t); /* drops dispq lock */ + } + 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); +} |