1 /* $NetBSD: kern_sleepq.c,v 1.33 2008/06/17 09:11:25 ad Exp $ */ 2 3 /*- 4 * Copyright (c) 2006, 2007, 2008 The NetBSD Foundation, Inc. 5 * All rights reserved. 6 * 7 * This code is derived from software contributed to The NetBSD Foundation 8 * by Andrew Doran. 9 * 10 * Redistribution and use in source and binary forms, with or without 11 * modification, are permitted provided that the following conditions 12 * are met: 13 * 1. Redistributions of source code must retain the above copyright 14 * notice, this list of conditions and the following disclaimer. 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in the 17 * documentation and/or other materials provided with the distribution. 18 * 19 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS 20 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 21 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 22 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS 23 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 24 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 25 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 26 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 27 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 28 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 29 * POSSIBILITY OF SUCH DAMAGE. 30 */ 31 32 /* 33 * Sleep queue implementation, used by turnstiles and general sleep/wakeup 34 * interfaces. 35 */ 36 37 #include <sys/cdefs.h> 38 __KERNEL_RCSID(0, "$NetBSD: kern_sleepq.c,v 1.33 2008/06/17 09:11:25 ad Exp $"); 39 40 #include <sys/param.h> 41 #include <sys/kernel.h> 42 #include <sys/cpu.h> 43 #include <sys/pool.h> 44 #include <sys/proc.h> 45 #include <sys/resourcevar.h> 46 #include <sys/sched.h> 47 #include <sys/systm.h> 48 #include <sys/sleepq.h> 49 #include <sys/ktrace.h> 50 51 #include <uvm/uvm_extern.h> 52 53 int sleepq_sigtoerror(lwp_t *, int); 54 55 /* General purpose sleep table, used by ltsleep() and condition variables. */ 56 sleeptab_t sleeptab; 57 58 /* 59 * sleeptab_init: 60 * 61 * Initialize a sleep table. 62 */ 63 void 64 sleeptab_init(sleeptab_t *st) 65 { 66 sleepq_t *sq; 67 int i; 68 69 for (i = 0; i < SLEEPTAB_HASH_SIZE; i++) { 70 sq = &st->st_queues[i].st_queue; 71 mutex_init(&st->st_queues[i].st_mutex, MUTEX_DEFAULT, 72 IPL_SCHED); 73 sleepq_init(sq); 74 } 75 } 76 77 /* 78 * sleepq_init: 79 * 80 * Prepare a sleep queue for use. 81 */ 82 void 83 sleepq_init(sleepq_t *sq) 84 { 85 86 TAILQ_INIT(sq); 87 } 88 89 /* 90 * sleepq_remove: 91 * 92 * Remove an LWP from a sleep queue and wake it up. Return non-zero if 93 * the LWP is swapped out; if so the caller needs to awaken the swapper 94 * to bring the LWP into memory. 95 */ 96 int 97 sleepq_remove(sleepq_t *sq, lwp_t *l) 98 { 99 struct schedstate_percpu *spc; 100 struct cpu_info *ci; 101 102 KASSERT(lwp_locked(l, NULL)); 103 104 TAILQ_REMOVE(sq, l, l_sleepchain); 105 l->l_syncobj = &sched_syncobj; 106 l->l_wchan = NULL; 107 l->l_sleepq = NULL; 108 l->l_flag &= ~LW_SINTR; 109 110 ci = l->l_cpu; 111 spc = &ci->ci_schedstate; 112 113 /* 114 * If not sleeping, the LWP must have been suspended. Let whoever 115 * holds it stopped set it running again. 116 */ 117 if (l->l_stat != LSSLEEP) { 118 KASSERT(l->l_stat == LSSTOP || l->l_stat == LSSUSPENDED); 119 lwp_setlock(l, spc->spc_lwplock); 120 return 0; 121 } 122 123 /* 124 * If the LWP is still on the CPU, mark it as LSONPROC. It may be 125 * about to call mi_switch(), in which case it will yield. 126 */ 127 if ((l->l_pflag & LP_RUNNING) != 0) { 128 l->l_stat = LSONPROC; 129 l->l_slptime = 0; 130 lwp_setlock(l, spc->spc_lwplock); 131 return 0; 132 } 133 134 /* Update sleep time delta, call the wake-up handler of scheduler */ 135 l->l_slpticksum += (hardclock_ticks - l->l_slpticks); 136 sched_wakeup(l); 137 138 /* Look for a CPU to wake up */ 139 l->l_cpu = sched_takecpu(l); 140 ci = l->l_cpu; 141 spc = &ci->ci_schedstate; 142 143 /* 144 * Set it running. 145 */ 146 spc_lock(ci); 147 lwp_setlock(l, spc->spc_mutex); 148 sched_setrunnable(l); 149 l->l_stat = LSRUN; 150 l->l_slptime = 0; 151 if ((l->l_flag & LW_INMEM) != 0) { 152 sched_enqueue(l, false); 153 spc_unlock(ci); 154 return 0; 155 } 156 spc_unlock(ci); 157 return 1; 158 } 159 160 /* 161 * sleepq_insert: 162 * 163 * Insert an LWP into the sleep queue, optionally sorting by priority. 164 */ 165 inline void 166 sleepq_insert(sleepq_t *sq, lwp_t *l, syncobj_t *sobj) 167 { 168 lwp_t *l2; 169 const int pri = lwp_eprio(l); 170 171 if ((sobj->sobj_flag & SOBJ_SLEEPQ_SORTED) != 0) { 172 TAILQ_FOREACH(l2, sq, l_sleepchain) { 173 if (lwp_eprio(l2) < pri) { 174 TAILQ_INSERT_BEFORE(l2, l, l_sleepchain); 175 return; 176 } 177 } 178 } 179 180 if ((sobj->sobj_flag & SOBJ_SLEEPQ_LIFO) != 0) 181 TAILQ_INSERT_HEAD(sq, l, l_sleepchain); 182 else 183 TAILQ_INSERT_TAIL(sq, l, l_sleepchain); 184 } 185 186 /* 187 * sleepq_enqueue: 188 * 189 * Enter an LWP into the sleep queue and prepare for sleep. The sleep 190 * queue must already be locked, and any interlock (such as the kernel 191 * lock) must have be released (see sleeptab_lookup(), sleepq_enter()). 192 */ 193 void 194 sleepq_enqueue(sleepq_t *sq, wchan_t wchan, const char *wmesg, syncobj_t *sobj) 195 { 196 lwp_t *l = curlwp; 197 198 KASSERT(lwp_locked(l, NULL)); 199 KASSERT(l->l_stat == LSONPROC); 200 KASSERT(l->l_wchan == NULL && l->l_sleepq == NULL); 201 202 l->l_syncobj = sobj; 203 l->l_wchan = wchan; 204 l->l_sleepq = sq; 205 l->l_wmesg = wmesg; 206 l->l_slptime = 0; 207 l->l_stat = LSSLEEP; 208 l->l_sleeperr = 0; 209 210 sleepq_insert(sq, l, sobj); 211 212 /* Save the time when thread has slept */ 213 l->l_slpticks = hardclock_ticks; 214 sched_slept(l); 215 } 216 217 /* 218 * sleepq_block: 219 * 220 * After any intermediate step such as releasing an interlock, switch. 221 * sleepq_block() may return early under exceptional conditions, for 222 * example if the LWP's containing process is exiting. 223 */ 224 int 225 sleepq_block(int timo, bool catch) 226 { 227 int error = 0, sig; 228 struct proc *p; 229 lwp_t *l = curlwp; 230 bool early = false; 231 232 ktrcsw(1, 0); 233 234 /* 235 * If sleeping interruptably, check for pending signals, exits or 236 * core dump events. 237 */ 238 if (catch) { 239 l->l_flag |= LW_SINTR; 240 if ((l->l_flag & (LW_CANCELLED|LW_WEXIT|LW_WCORE)) != 0) { 241 l->l_flag &= ~LW_CANCELLED; 242 error = EINTR; 243 early = true; 244 } else if ((l->l_flag & LW_PENDSIG) != 0 && sigispending(l, 0)) 245 early = true; 246 } 247 248 if (early) { 249 /* lwp_unsleep() will release the lock */ 250 lwp_unsleep(l, true); 251 } else { 252 if (timo) 253 callout_schedule(&l->l_timeout_ch, timo); 254 mi_switch(l); 255 256 /* The LWP and sleep queue are now unlocked. */ 257 if (timo) { 258 /* 259 * Even if the callout appears to have fired, we need to 260 * stop it in order to synchronise with other CPUs. 261 */ 262 if (callout_halt(&l->l_timeout_ch, NULL)) 263 error = EWOULDBLOCK; 264 } 265 } 266 267 if (catch && error == 0) { 268 p = l->l_proc; 269 if ((l->l_flag & (LW_CANCELLED | LW_WEXIT | LW_WCORE)) != 0) 270 error = EINTR; 271 else if ((l->l_flag & LW_PENDSIG) != 0) { 272 /* 273 * Acquiring p_lock may cause us to recurse 274 * through the sleep path and back into this 275 * routine, but is safe because LWPs sleeping 276 * on locks are non-interruptable. We will 277 * not recurse again. 278 */ 279 mutex_enter(p->p_lock); 280 if ((sig = issignal(l)) != 0) 281 error = sleepq_sigtoerror(l, sig); 282 mutex_exit(p->p_lock); 283 } 284 } 285 286 ktrcsw(0, 0); 287 if (__predict_false(l->l_biglocks != 0)) { 288 KERNEL_LOCK(l->l_biglocks, NULL); 289 } 290 return error; 291 } 292 293 /* 294 * sleepq_wake: 295 * 296 * Wake zero or more LWPs blocked on a single wait channel. 297 */ 298 lwp_t * 299 sleepq_wake(sleepq_t *sq, wchan_t wchan, u_int expected, kmutex_t *mp) 300 { 301 lwp_t *l, *next; 302 int swapin = 0; 303 304 KASSERT(mutex_owned(mp)); 305 306 for (l = TAILQ_FIRST(sq); l != NULL; l = next) { 307 KASSERT(l->l_sleepq == sq); 308 KASSERT(l->l_mutex == mp); 309 next = TAILQ_NEXT(l, l_sleepchain); 310 if (l->l_wchan != wchan) 311 continue; 312 swapin |= sleepq_remove(sq, l); 313 if (--expected == 0) 314 break; 315 } 316 317 mutex_spin_exit(mp); 318 319 /* 320 * If there are newly awakend threads that need to be swapped in, 321 * then kick the swapper into action. 322 */ 323 if (swapin) 324 uvm_kick_scheduler(); 325 326 return l; 327 } 328 329 /* 330 * sleepq_unsleep: 331 * 332 * Remove an LWP from its sleep queue and set it runnable again. 333 * sleepq_unsleep() is called with the LWP's mutex held, and will 334 * always release it. 335 */ 336 u_int 337 sleepq_unsleep(lwp_t *l, bool cleanup) 338 { 339 sleepq_t *sq = l->l_sleepq; 340 kmutex_t *mp = l->l_mutex; 341 int swapin; 342 343 KASSERT(lwp_locked(l, mp)); 344 KASSERT(l->l_wchan != NULL); 345 346 swapin = sleepq_remove(sq, l); 347 348 if (cleanup) { 349 mutex_spin_exit(mp); 350 if (swapin) 351 uvm_kick_scheduler(); 352 } 353 354 return swapin; 355 } 356 357 /* 358 * sleepq_timeout: 359 * 360 * Entered via the callout(9) subsystem to time out an LWP that is on a 361 * sleep queue. 362 */ 363 void 364 sleepq_timeout(void *arg) 365 { 366 lwp_t *l = arg; 367 368 /* 369 * Lock the LWP. Assuming it's still on the sleep queue, its 370 * current mutex will also be the sleep queue mutex. 371 */ 372 lwp_lock(l); 373 374 if (l->l_wchan == NULL) { 375 /* Somebody beat us to it. */ 376 lwp_unlock(l); 377 return; 378 } 379 380 lwp_unsleep(l, true); 381 } 382 383 /* 384 * sleepq_sigtoerror: 385 * 386 * Given a signal number, interpret and return an error code. 387 */ 388 int 389 sleepq_sigtoerror(lwp_t *l, int sig) 390 { 391 struct proc *p = l->l_proc; 392 int error; 393 394 KASSERT(mutex_owned(p->p_lock)); 395 396 /* 397 * If this sleep was canceled, don't let the syscall restart. 398 */ 399 if ((SIGACTION(p, sig).sa_flags & SA_RESTART) == 0) 400 error = EINTR; 401 else 402 error = ERESTART; 403 404 return error; 405 } 406 407 /* 408 * sleepq_abort: 409 * 410 * After a panic or during autoconfiguration, lower the interrupt 411 * priority level to give pending interrupts a chance to run, and 412 * then return. Called if sleepq_dontsleep() returns non-zero, and 413 * always returns zero. 414 */ 415 int 416 sleepq_abort(kmutex_t *mtx, int unlock) 417 { 418 extern int safepri; 419 int s; 420 421 s = splhigh(); 422 splx(safepri); 423 splx(s); 424 if (mtx != NULL && unlock != 0) 425 mutex_exit(mtx); 426 427 return 0; 428 } 429 430 /* 431 * sleepq_changepri: 432 * 433 * Adjust the priority of an LWP residing on a sleepq. This method 434 * will only alter the user priority; the effective priority is 435 * assumed to have been fixed at the time of insertion into the queue. 436 */ 437 void 438 sleepq_changepri(lwp_t *l, pri_t pri) 439 { 440 sleepq_t *sq = l->l_sleepq; 441 pri_t opri; 442 443 KASSERT(lwp_locked(l, NULL)); 444 445 opri = lwp_eprio(l); 446 l->l_priority = pri; 447 448 if (lwp_eprio(l) == opri) { 449 return; 450 } 451 if ((l->l_syncobj->sobj_flag & SOBJ_SLEEPQ_SORTED) == 0) { 452 return; 453 } 454 455 /* 456 * Don't let the sleep queue become empty, even briefly. 457 * cv_signal() and cv_broadcast() inspect it without the 458 * sleep queue lock held and need to see a non-empty queue 459 * head if there are waiters. 460 */ 461 if (TAILQ_FIRST(sq) == l && TAILQ_NEXT(l, l_sleepchain) == NULL) { 462 return; 463 } 464 TAILQ_REMOVE(sq, l, l_sleepchain); 465 sleepq_insert(sq, l, l->l_syncobj); 466 } 467 468 void 469 sleepq_lendpri(lwp_t *l, pri_t pri) 470 { 471 sleepq_t *sq = l->l_sleepq; 472 pri_t opri; 473 474 KASSERT(lwp_locked(l, NULL)); 475 476 opri = lwp_eprio(l); 477 l->l_inheritedprio = pri; 478 479 if (lwp_eprio(l) == opri) { 480 return; 481 } 482 if ((l->l_syncobj->sobj_flag & SOBJ_SLEEPQ_SORTED) == 0) { 483 return; 484 } 485 486 /* 487 * Don't let the sleep queue become empty, even briefly. 488 * cv_signal() and cv_broadcast() inspect it without the 489 * sleep queue lock held and need to see a non-empty queue 490 * head if there are waiters. 491 */ 492 if (TAILQ_FIRST(sq) == l && TAILQ_NEXT(l, l_sleepchain) == NULL) { 493 return; 494 } 495 TAILQ_REMOVE(sq, l, l_sleepchain); 496 sleepq_insert(sq, l, l->l_syncobj); 497 } 498