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 } 271