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