1 /*
   2  * CDDL HEADER START
   3  *
   4  * The contents of this file are subject to the terms of the
   5  * Common Development and Distribution License (the "License").
   6  * You may not use this file except in compliance with the License.
   7  *
   8  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
   9  * or http://www.opensolaris.org/os/licensing.
  10  * See the License for the specific language governing permissions
  11  * and limitations under the License.
  12  *
  13  * When distributing Covered Code, include this CDDL HEADER in each
  14  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
  15  * If applicable, add the following below this CDDL HEADER, with the
  16  * fields enclosed by brackets "[]" replaced with your own identifying
  17  * information: Portions Copyright [yyyy] [name of copyright owner]
  18  *
  19  * CDDL HEADER END
  20  */
  21 /*
  22  * Copyright 2008 Sun Microsystems, Inc.  All rights reserved.
  23  * Use is subject to license terms.
  24  */
  25 
  26 #include <sys/param.h>
  27 #include <sys/systm.h>
  28 #include <sys/thread.h>
  29 #include <sys/class.h>
  30 #include <sys/debug.h>
  31 #include <sys/cpuvar.h>
  32 #include <sys/waitq.h>
  33 #include <sys/cmn_err.h>
  34 #include <sys/time.h>
  35 #include <sys/dtrace.h>
  36 #include <sys/sdt.h>
  37 #include <sys/zone.h>
  38 
  39 /*
  40  * Wait queue implementation.
  41  */
  42 
  43 void
  44 waitq_init(waitq_t *wq)
  45 {
  46         DISP_LOCK_INIT(&wq->wq_lock);
  47         wq->wq_first = NULL;
  48         wq->wq_count = 0;
  49         wq->wq_blocked = B_TRUE;
  50 }
  51 
  52 void
  53 waitq_fini(waitq_t *wq)
  54 {
  55         ASSERT(wq->wq_count == 0);
  56         ASSERT(wq->wq_first == NULL);
  57         ASSERT(wq->wq_blocked == B_TRUE);
  58         ASSERT(!DISP_LOCK_HELD(&wq->wq_lock));
  59 
  60         DISP_LOCK_DESTROY(&wq->wq_lock);
  61 }
  62 
  63 /*
  64  * Operations on waitq_t structures.
  65  *
  66  * A wait queue is a singly linked NULL-terminated list with doubly
  67  * linked circular sublists.  The singly linked list is in descending
  68  * priority order and FIFO for threads of the same priority.  It links
  69  * through the t_link field of the thread structure.  The doubly linked
  70  * sublists link threads of the same priority.  They use the t_priforw
  71  * and t_priback fields of the thread structure.
  72  *
  73  * Graphically (with priorities in parens):
  74  *
  75  *         ________________           _______                   _______
  76  *        /                \         /       \                 /       \
  77  *        |                |         |       |                 |       |
  78  *        v                v         v       v                 v       v
  79  *     t1(60)-->t2(60)-->t3(60)-->t4(50)-->t5(50)-->t6(30)-->t7(0)-->t8(0)
  80  *        ^      ^  ^      ^         ^       ^       ^  ^      ^       ^
  81  *        |      |  |      |         |       |       |  |      |       |
  82  *        \______/  \______/         \_______/       \__/      \_______/
  83  *
  84  * There are three interesting operations on a waitq list: inserting
  85  * a thread into the proper position according to priority; removing a
  86  * thread given a pointer to it; and walking the list, possibly
  87  * removing threads along the way.  This design allows all three
  88  * operations to be performed efficiently and easily.
  89  *
  90  * To insert a thread, traverse the list looking for the sublist of
  91  * the same priority as the thread (or one of a lower priority,
  92  * meaning there are no other threads in the list of the same
  93  * priority).  This can be done without touching all threads in the
  94  * list by following the links between the first threads in each
  95  * sublist.  Given a thread t that is the head of a sublist (the first
  96  * thread of that priority found when following the t_link pointers),
  97  * t->t_priback->t_link points to the head of the next sublist.  It's
  98  * important to do this since a waitq may contain thousands of
  99  * threads.
 100  *
 101  * Removing a thread from the list is also efficient.  First, the
 102  * t_waitq field contains a pointer to the waitq on which a thread
 103  * is waiting (or NULL if it's not on a waitq).  This is used to
 104  * determine if the given thread is on the given waitq without
 105  * searching the list.  Assuming it is, if it's not the head of a
 106  * sublist, just remove it from the sublist and use the t_priback
 107  * pointer to find the thread that points to it with t_link.  If it is
 108  * the head of a sublist, search for it by walking the sublist heads,
 109  * similar to searching for a given priority level when inserting a
 110  * thread.
 111  *
 112  * To walk the list, simply follow the t_link pointers.  Removing
 113  * threads along the way can be done easily if the code maintains a
 114  * pointer to the t_link field that pointed to the thread being
 115  * removed.
 116  */
 117 
 118 static void
 119 waitq_link(waitq_t *wq, kthread_t *t)
 120 {
 121         kthread_t *next_tp;
 122         kthread_t *last_tp;
 123         kthread_t **tpp;
 124         pri_t tpri, next_pri, last_pri = -1;
 125 
 126         ASSERT(DISP_LOCK_HELD(&wq->wq_lock));
 127 
 128         tpri = DISP_PRIO(t);
 129         tpp = &wq->wq_first;
 130         while ((next_tp = *tpp) != NULL) {
 131                 next_pri = DISP_PRIO(next_tp);
 132                 if (tpri > next_pri)
 133                         break;
 134                 last_tp = next_tp->t_priback;
 135                 last_pri = next_pri;
 136                 tpp = &last_tp->t_link;
 137         }
 138         *tpp = t;
 139         t->t_link = next_tp;
 140         if (last_pri == tpri) {
 141                 /* last_tp points to the last thread of this priority */
 142                 t->t_priback = last_tp;
 143                 t->t_priforw = last_tp->t_priforw;
 144                 last_tp->t_priforw->t_priback = t;
 145                 last_tp->t_priforw = t;
 146         } else {
 147                 t->t_priback = t->t_priforw = t;
 148         }
 149         wq->wq_count++;
 150         t->t_waitq = wq;
 151 }
 152 
 153 static void
 154 waitq_unlink(waitq_t *wq, kthread_t *t)
 155 {
 156         kthread_t *nt;
 157         kthread_t **ptl;
 158 
 159         ASSERT(THREAD_LOCK_HELD(t));
 160         ASSERT(DISP_LOCK_HELD(&wq->wq_lock));
 161         ASSERT(t->t_waitq == wq);
 162 
 163         ptl = &t->t_priback->t_link;
 164         /*
 165          * Is it the head of a priority sublist?  If so, need to walk
 166          * the priorities to find the t_link pointer that points to it.
 167          */
 168         if (*ptl != t) {
 169                 /*
 170                  * Find the right priority level.
 171                  */
 172                 ptl = &t->t_waitq->wq_first;
 173                 while ((nt = *ptl) != t)
 174                         ptl = &nt->t_priback->t_link;
 175         }
 176         /*
 177          * Remove thread from the t_link list.
 178          */
 179         *ptl = t->t_link;
 180 
 181         /*
 182          * Take it off the priority sublist if there's more than one
 183          * thread there.
 184          */
 185         if (t->t_priforw != t) {
 186                 t->t_priback->t_priforw = t->t_priforw;
 187                 t->t_priforw->t_priback = t->t_priback;
 188         }
 189         t->t_link = NULL;
 190 
 191         wq->wq_count--;
 192         t->t_waitq = NULL;
 193         t->t_priforw = NULL;
 194         t->t_priback = NULL;
 195 }
 196 
 197 /*
 198  * Put specified thread to specified wait queue without dropping thread's lock.
 199  * Returns 1 if thread was successfully placed on project's wait queue, or
 200  * 0 if wait queue is blocked.
 201  */
 202 int
 203 waitq_enqueue(waitq_t *wq, kthread_t *t)
 204 {
 205         ASSERT(THREAD_LOCK_HELD(t));
 206         ASSERT(t->t_sleepq == NULL);
 207         ASSERT(t->t_waitq == NULL);
 208         ASSERT(t->t_link == NULL);
 209 
 210         disp_lock_enter_high(&wq->wq_lock);
 211 
 212         /*
 213          * Can't enqueue anything on a blocked wait queue
 214          */
 215         if (wq->wq_blocked) {
 216                 disp_lock_exit_high(&wq->wq_lock);
 217                 return (0);
 218         }
 219 
 220         /*
 221          * Mark the time when thread is placed on wait queue. The microstate
 222          * accounting code uses this timestamp to determine wait times.
 223          */
 224         t->t_waitrq = gethrtime_unscaled();
 225 
 226         DTRACE_SCHED1(cpucaps__sleep, kthread_t *, t);
 227         waitq_link(wq, t);
 228 
 229         THREAD_WAIT(t, &wq->wq_lock);
 230         return (1);
 231 }
 232 
 233 /*
 234  * Change thread's priority while on the wait queue.
 235  * Dequeue and equeue it again so that it gets placed in the right place.
 236  */
 237 void
 238 waitq_change_pri(kthread_t *t, pri_t new_pri)
 239 {
 240         waitq_t *wq = t->t_waitq;
 241 
 242         ASSERT(THREAD_LOCK_HELD(t));
 243         ASSERT(ISWAITING(t));
 244         ASSERT(wq != NULL);
 245 
 246         waitq_unlink(wq, t);
 247         t->t_pri = new_pri;
 248         waitq_link(wq, t);
 249 }
 250 
 251 static void
 252 waitq_dequeue(waitq_t *wq, kthread_t *t)
 253 {
 254         ASSERT(THREAD_LOCK_HELD(t));
 255         ASSERT(t->t_waitq == wq);
 256         ASSERT(ISWAITING(t));
 257 
 258         waitq_unlink(wq, t);
 259         DTRACE_SCHED1(cpucaps__wakeup, kthread_t *, t);
 260 
 261         /*
 262          * Change thread to transition state and drop the wait queue lock. The
 263          * thread will remain locked since its t_lockp points to the
 264          * transition_lock.
 265          */
 266         THREAD_TRANSITION(t);
 267 }
 268 
 269 /*
 270  * Return True iff there are any threads on the specified wait queue.
 271  * The check is done **without holding any locks**.
 272  */
 273 boolean_t
 274 waitq_isempty(waitq_t *wq)
 275 {
 276         return (wq->wq_count == 0);
 277 }
 278 
 279 /*
 280  * Take thread off its wait queue and make it runnable.
 281  * Returns with thread lock held.
 282  */
 283 void
 284 waitq_setrun(kthread_t *t)
 285 {
 286         waitq_t *wq = t->t_waitq;
 287 
 288         ASSERT(THREAD_LOCK_HELD(t));
 289 
 290         ASSERT(ISWAITING(t));
 291         if (wq == NULL)
 292                 panic("waitq_setrun: thread %p is not on waitq", (void *)t);
 293         waitq_dequeue(wq, t);
 294         CL_SETRUN(t);
 295 }
 296 
 297 /*
 298  * Take the first thread off the wait queue and return pointer to it.
 299  */
 300 static kthread_t *
 301 waitq_takeone(waitq_t *wq)
 302 {
 303         kthread_t *t;
 304 
 305         disp_lock_enter(&wq->wq_lock);
 306         /*
 307          * waitq_dequeue drops wait queue lock but leaves the CPU at high PIL.
 308          */
 309         if ((t = wq->wq_first) != NULL)
 310                 waitq_dequeue(wq, wq->wq_first);
 311         else
 312                 disp_lock_exit(&wq->wq_lock);
 313         return (t);
 314 }
 315 
 316 /*
 317  * Take the first thread off the wait queue and make it runnable.
 318  * Return the pointer to the thread or NULL if waitq is empty
 319  */
 320 static kthread_t *
 321 waitq_runfirst(waitq_t *wq)
 322 {
 323         kthread_t *t;
 324 
 325         t = waitq_takeone(wq);
 326         if (t != NULL) {
 327                 /*
 328                  * t should have transition lock held.
 329                  * CL_SETRUN() will replace it with dispq lock and keep it held.
 330                  * thread_unlock() will drop dispq lock and restore PIL.
 331                  */
 332                 ASSERT(THREAD_LOCK_HELD(t));
 333                 CL_SETRUN(t);
 334                 thread_unlock(t);
 335         }
 336         return (t);
 337 }
 338 
 339 /*
 340  * Take the first thread off the wait queue and make it runnable.
 341  */
 342 void
 343 waitq_runone(waitq_t *wq)
 344 {
 345         (void) waitq_runfirst(wq);
 346 }
 347 
 348 /*
 349  * Take all threads off the wait queue and make them runnable.
 350  */
 351 static void
 352 waitq_runall(waitq_t *wq)
 353 {
 354         while (waitq_runfirst(wq) != NULL)
 355                 ;
 356 }
 357 
 358 /*
 359  * Prevent any new threads from entering wait queue and make all threads
 360  * currently on the wait queue runnable. After waitq_block() completion, no
 361  * threads should ever appear on the wait queue untill it is unblocked.
 362  */
 363 void
 364 waitq_block(waitq_t *wq)
 365 {
 366         ASSERT(!wq->wq_blocked);
 367         disp_lock_enter(&wq->wq_lock);
 368         wq->wq_blocked = B_TRUE;
 369         disp_lock_exit(&wq->wq_lock);
 370         waitq_runall(wq);
 371         ASSERT(waitq_isempty(wq));
 372 }
 373 
 374 /*
 375  * Allow threads to be placed on the wait queue.
 376  */
 377 void
 378 waitq_unblock(waitq_t *wq)
 379 {
 380         disp_lock_enter(&wq->wq_lock);
 381 
 382         ASSERT(waitq_isempty(wq));
 383         ASSERT(wq->wq_blocked);
 384 
 385         wq->wq_blocked = B_FALSE;
 386 
 387         disp_lock_exit(&wq->wq_lock);
 388 }