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);
}