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 /* 227 * Mark thread as not swappable. If necessary, it will get 228 * swapped out when it returns to the userland. 229 */ 230 t->t_schedflag |= TS_DONT_SWAP; 231 DTRACE_SCHED1(cpucaps__sleep, kthread_t *, t); 232 waitq_link(wq, t); 233 234 THREAD_WAIT(t, &wq->wq_lock); 235 return (1); 236 } 237 238 /* 239 * Change thread's priority while on the wait queue. 240 * Dequeue and equeue it again so that it gets placed in the right place. 241 */ 242 void 243 waitq_change_pri(kthread_t *t, pri_t new_pri) 244 { 245 waitq_t *wq = t->t_waitq; 246 247 ASSERT(THREAD_LOCK_HELD(t)); 248 ASSERT(ISWAITING(t)); 249 ASSERT(wq != NULL); 250 251 waitq_unlink(wq, t); 252 t->t_pri = new_pri; 253 waitq_link(wq, t); 254 } 255 256 static void 257 waitq_dequeue(waitq_t *wq, kthread_t *t) 258 { 259 ASSERT(THREAD_LOCK_HELD(t)); 260 ASSERT(t->t_waitq == wq); 261 ASSERT(ISWAITING(t)); 262 263 waitq_unlink(wq, t); 264 DTRACE_SCHED1(cpucaps__wakeup, kthread_t *, t); 265 266 /* 267 * Change thread to transition state and drop the wait queue lock. The 268 * thread will remain locked since its t_lockp points to the 269 * transition_lock. 270 */ 271 THREAD_TRANSITION(t); 272 } 273 274 /* 275 * Return True iff there are any threads on the specified wait queue. 276 * The check is done **without holding any locks**. 277 */ 278 boolean_t 279 waitq_isempty(waitq_t *wq) 280 { 281 return (wq->wq_count == 0); 282 } 283 284 /* 285 * Take thread off its wait queue and make it runnable. 286 * Returns with thread lock held. 287 */ 288 void 289 waitq_setrun(kthread_t *t) 290 { 291 waitq_t *wq = t->t_waitq; 292 293 ASSERT(THREAD_LOCK_HELD(t)); 294 295 ASSERT(ISWAITING(t)); 296 if (wq == NULL) 297 panic("waitq_setrun: thread %p is not on waitq", (void *)t); 298 waitq_dequeue(wq, t); 299 CL_SETRUN(t); 300 } 301 302 /* 303 * Take the first thread off the wait queue and return pointer to it. 304 */ 305 static kthread_t * 306 waitq_takeone(waitq_t *wq) 307 { 308 kthread_t *t; 309 310 disp_lock_enter(&wq->wq_lock); 311 /* 312 * waitq_dequeue drops wait queue lock but leaves the CPU at high PIL. 313 */ 314 if ((t = wq->wq_first) != NULL) 315 waitq_dequeue(wq, wq->wq_first); 316 else 317 disp_lock_exit(&wq->wq_lock); 318 return (t); 319 } 320 321 /* 322 * Take the first thread off the wait queue and make it runnable. 323 * Return the pointer to the thread or NULL if waitq is empty 324 */ 325 static kthread_t * 326 waitq_runfirst(waitq_t *wq) 327 { 328 kthread_t *t; 329 330 t = waitq_takeone(wq); 331 if (t != NULL) { 332 /* 333 * t should have transition lock held. 334 * CL_SETRUN() will replace it with dispq lock and keep it held. 335 * thread_unlock() will drop dispq lock and restore PIL. 336 */ 337 ASSERT(THREAD_LOCK_HELD(t)); 338 CL_SETRUN(t); 339 thread_unlock(t); 340 } 341 return (t); 342 } 343 344 /* 345 * Take the first thread off the wait queue and make it runnable. 346 */ 347 void 348 waitq_runone(waitq_t *wq) 349 { 350 (void) waitq_runfirst(wq); 351 } 352 353 /* 354 * Take all threads off the wait queue and make them runnable. 355 */ 356 static void 357 waitq_runall(waitq_t *wq) 358 { 359 while (waitq_runfirst(wq) != NULL) 360 ; 361 } 362 363 /* 364 * Prevent any new threads from entering wait queue and make all threads 365 * currently on the wait queue runnable. After waitq_block() completion, no 366 * threads should ever appear on the wait queue untill it is unblocked. 367 */ 368 void 369 waitq_block(waitq_t *wq) 370 { 371 ASSERT(!wq->wq_blocked); 372 disp_lock_enter(&wq->wq_lock); 373 wq->wq_blocked = B_TRUE; 374 disp_lock_exit(&wq->wq_lock); 375 waitq_runall(wq); 376 ASSERT(waitq_isempty(wq)); 377 } 378 379 /* 380 * Allow threads to be placed on the wait queue. 381 */ 382 void 383 waitq_unblock(waitq_t *wq) 384 { 385 disp_lock_enter(&wq->wq_lock); 386 387 ASSERT(waitq_isempty(wq)); 388 ASSERT(wq->wq_blocked); 389 390 wq->wq_blocked = B_FALSE; 391 392 disp_lock_exit(&wq->wq_lock); 393 } 394