kernel/os/sleepq.c

   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, Version 1.0 only
   6  * (the "License").  You may not use this file except in compliance
   7  * with the License.
   8  *
   9  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
  10  * or http://www.opensolaris.org/os/licensing.
  11  * See the License for the specific language governing permissions
  12  * and limitations under the License.
  13  *
  14  * When distributing Covered Code, include this CDDL HEADER in each
  15  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
  16  * If applicable, add the following below this CDDL HEADER, with the
  17  * fields enclosed by brackets "[]" replaced with your own identifying
  18  * information: Portions Copyright [yyyy] [name of copyright owner]
  19  *
  20  * CDDL HEADER END
  21  */
  22 /*
  23  * Copyright 2004 Sun Microsystems, Inc.  All rights reserved.
  24  * Use is subject to license terms.
  25  */
  26
  27 #pragma ident   "%Z%%M% %I%     %E% SMI"
  28
  29 #include <sys/param.h>
  30 #include <sys/systm.h>
  31 #include <sys/thread.h>
  32 #include <sys/proc.h>
  33 #include <sys/debug.h>
  34 #include <sys/cpuvar.h>
  35 #include <sys/sleepq.h>
  36 #include <sys/sdt.h>
  37
  38 /*
  39  * Operations on sleepq_t structures.
  40  *
  41  * A sleep queue is a singly linked NULL-terminated list with doubly
  42  * linked circular sublists.  The singly linked list is in descending
  43  * priority order and FIFO for threads of the same priority.  It links
  44  * through the t_link field of the thread structure.  The doubly linked
  45  * sublists link threads of the same priority.  They use the t_priforw
  46  * and t_priback fields of the thread structure.
  47  *
  48  * Graphically (with priorities in parens):
  49  *
  50  *         ________________           _______                   _______
  51  *        /                \         /       \                 /       \
  52  *        |                |         |       |                 |       |
  53  *        v                v         v       v                 v       v
  54  *     t1(60)-->t2(60)-->t3(60)-->t4(50)-->t5(50)-->t6(30)-->t7(0)-->t8(0)
  55  *        ^      ^  ^      ^         ^       ^       ^  ^      ^       ^
  56  *        |      |  |      |         |       |       |  |      |       |
  57  *        \______/  \______/         \_______/       \__/      \_______/
  58  *
  59  * There are three interesting operations on a sleepq list: inserting
  60  * a thread into the proper position according to priority; removing a
  61  * thread given a pointer to it; and walking the list, possibly
  62  * removing threads along the way.  This design allows all three
  63  * operations to be performed efficiently and easily.
  64  *
  65  * To insert a thread, traverse the list looking for the sublist of
  66  * the same priority as the thread (or one of a lower priority,
  67  * meaning there are no other threads in the list of the same
  68  * priority).  This can be done without touching all threads in the
  69  * list by following the links between the first threads in each
  70  * sublist.  Given a thread t that is the head of a sublist (the first
  71  * thread of that priority found when following the t_link pointers),
  72  * t->t_priback->t_link points to the head of the next sublist.  It's
  73  * important to do this since a sleepq may contain thousands of
  74  * threads.
  75  *
  76  * Removing a thread from the list is also efficient.  First, the
  77  * t_sleepq field contains a pointer to the sleepq on which a thread
  78  * is waiting (or NULL if it's not on a sleepq).  This is used to
  79  * determine if the given thread is on the given sleepq without
  80  * searching the list.  Assuming it is, if it's not the head of a
  81  * sublist, just remove it from the sublist and use the t_priback
  82  * pointer to find the thread that points to it with t_link.  If it is
  83  * the head of a sublist, search for it by walking the sublist heads,
  84  * similar to searching for a given priority level when inserting a
  85  * thread.
  86  *
  87  * To walk the list, simply follow the t_link pointers.  Removing
  88  * threads along the way can be done easily if the code maintains a
  89  * pointer to the t_link field that pointed to the thread being
  90  * removed.
  91  */
  92
  93 sleepq_head_t sleepq_head[NSLEEPQ];
  94
  95 /*
  96  * Common code to unlink a thread from the queue.  tpp is a pointer to
  97  * the t_link pointer that points to tp.
  98  */
  99 void
 100 sleepq_unlink(kthread_t **tpp, kthread_t *tp)
 101 {
 102         ASSERT(*tpp == tp);
 103         ASSERT(tp->t_sleepq != NULL);
 104
 105         /* remove it from the t_link list */
 106         *tpp = tp->t_link;
 107
 108         /*
 109          * Take it off the priority sublist if there's more than one
 110          * thread there.
 111          */
 112         if (tp->t_priforw != tp) {
 113                 tp->t_priback->t_priforw = tp->t_priforw;
 114                 tp->t_priforw->t_priback = tp->t_priback;
 115         }
 116
 117         /* Clear out the link junk */
 118         tp->t_link = NULL;
 119         tp->t_sleepq = NULL;
 120         tp->t_priforw = NULL;
 121         tp->t_priback = NULL;
 122 }
 123
 124 /*
 125  * Insert thread t into sleep queue spq in dispatch priority order.
 126  * For lwp_rwlock_t queueing, we must queue writers ahead of readers
 127  * of the same priority.  We do this by making writers appear to have
 128  * a half point higher priority for purposes of priority comparisions.
 129  */
 130 #define CMP_PRIO(t)     ((DISP_PRIO(t) << 1) + (t)->t_writer)
 131 void
 132 sleepq_insert(sleepq_t *spq, kthread_t *t)
 133 {
 134         kthread_t       *next_tp;
 135         kthread_t       *last_tp;
 136         kthread_t       **tpp;
 137         pri_t           tpri, next_pri, last_pri = -1;
 138
 139         ASSERT(THREAD_LOCK_HELD(t));    /* holding the lock on the sleepq */
 140         ASSERT(t->t_sleepq == NULL);    /* not already on a sleep queue */
 141
 142         tpri = CMP_PRIO(t);
 143         tpp = &spq->sq_first;
 144         while ((next_tp = *tpp) != NULL) {
 145                 next_pri = CMP_PRIO(next_tp);
 146                 if (tpri > next_pri)
 147                         break;
 148                 last_tp = next_tp->t_priback;
 149                 last_pri = next_pri;
 150                 tpp = &last_tp->t_link;
 151         }
 152         *tpp = t;
 153         t->t_link = next_tp;
 154         if (last_pri == tpri) {
 155                 /* last_tp points to the last thread of this priority */
 156                 t->t_priback = last_tp;
 157                 t->t_priforw = last_tp->t_priforw;
 158                 last_tp->t_priforw->t_priback = t;
 159                 last_tp->t_priforw = t;
 160         } else {
 161                 t->t_priback = t->t_priforw = t;
 162         }
 163         t->t_sleepq = spq;
 164 }
 165
 166
 167 /*
 168  * Yank a particular thread out of sleep queue and wake it up.
 169  */
 170 void
 171 sleepq_unsleep(kthread_t *t)
 172 {
 173         ASSERT(THREAD_LOCK_HELD(t));    /* thread locked via sleepq */
 174
 175         /* remove it from queue */
 176         sleepq_dequeue(t);
 177
 178         /* wake it up */
 179         t->t_sobj_ops = NULL;
 180         t->t_wchan = NULL;
 181         t->t_wchan0 = NULL;
 182         ASSERT(t->t_state == TS_SLEEP);
 183         /*
 184          * Change thread to transition state without
 185          * dropping the sleep queue lock.
 186          */
 187         THREAD_TRANSITION_NOLOCK(t);
 188 }
 189
 190 /*
 191  * Yank a particular thread out of sleep queue but don't wake it up.
 192  */
 193 void
 194 sleepq_dequeue(kthread_t *t)
 195 {
 196         kthread_t       *nt;
 197         kthread_t       **ptl;
 198
 199         ASSERT(THREAD_LOCK_HELD(t));    /* thread locked via sleepq */
 200         ASSERT(t->t_sleepq != NULL);
 201
 202         ptl = &t->t_priback->t_link;
 203         /*
 204          * Is it the head of a priority sublist?  If so, need to walk
 205          * the priorities to find the t_link pointer that points to it.
 206          */
 207         if (*ptl != t) {
 208                 /*
 209                  * Find the right priority level.
 210                  */
 211                 ptl = &t->t_sleepq->sq_first;
 212                 while ((nt = *ptl) != t)
 213                         ptl = &nt->t_priback->t_link;
 214         }
 215         sleepq_unlink(ptl, t);
 216 }
 217
 218 kthread_t *
 219 sleepq_wakeone_chan(sleepq_t *spq, void *chan)
 220 {
 221         kthread_t       *tp;
 222         kthread_t       **tpp;
 223
 224         tpp = &spq->sq_first;
 225         while ((tp = *tpp) != NULL) {
 226                 if (tp->t_wchan == chan) {
 227                         ASSERT(tp->t_wchan0 == NULL);
 228                         sleepq_unlink(tpp, tp);
 229                         DTRACE_SCHED1(wakeup, kthread_t *, tp);
 230                         tp->t_wchan = NULL;
 231                         tp->t_sobj_ops = NULL;
 232                         /*
 233                          * Let the target thread know it was cv_signal()ed.
 234                          * This assumes that cv_signal() is the only
 235                          * caller of sleepq_wakeone_chan().  If this
 236                          * becomes false, this code must be revised.
 237                          */
 238                         tp->t_schedflag |= TS_SIGNALLED;
 239                         ASSERT(tp->t_state == TS_SLEEP);
 240                         CL_WAKEUP(tp);
 241                         thread_unlock_high(tp);         /* drop runq lock */
 242                         return (tp);
 243                 }
 244                 tpp = &tp->t_link;
 245         }
 246         return (NULL);
 247 }
 248
 249 void
 250 sleepq_wakeall_chan(sleepq_t *spq, void *chan)
 251 {
 252         kthread_t       *tp;
 253         kthread_t       **tpp;
 254
 255         tpp = &spq->sq_first;
 256         while ((tp = *tpp) != NULL) {
 257                 if (tp->t_wchan == chan) {
 258                         ASSERT(tp->t_wchan0 == NULL);
 259                         sleepq_unlink(tpp, tp);
 260                         DTRACE_SCHED1(wakeup, kthread_t *, tp);
 261                         tp->t_wchan = NULL;
 262                         tp->t_sobj_ops = NULL;
 263                         ASSERT(tp->t_state == TS_SLEEP);
 264                         CL_WAKEUP(tp);
 265                         thread_unlock_high(tp);         /* drop runq lock */
 266                         continue;
 267                 }
 268                 tpp = &tp->t_link;
 269         }
 270 }