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