8322 nl: misleading-indentation

[unleashed/tickless.git] / usr / src / 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);
}