1 /* $NetBSD: kern_sleepq.c,v 1.46 2012/02/19 21:06:54 rmind Exp $ */ 2 3 /*- 4 * Copyright (c) 2006, 2007, 2008, 2009 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.46 2012/02/19 21:06:54 rmind 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 static int sleepq_sigtoerror(lwp_t *, int); 52 53 /* General purpose sleep table, used by mtsleep() and condition variables. */ 54 sleeptab_t sleeptab __cacheline_aligned; 55 56 /* 57 * sleeptab_init: 58 * 59 * Initialize a sleep table. 60 */ 61 void 62 sleeptab_init(sleeptab_t *st) 63 { 64 sleepq_t *sq; 65 int i; 66 67 for (i = 0; i < SLEEPTAB_HASH_SIZE; i++) { 68 sq = &st->st_queues[i].st_queue; 69 st->st_queues[i].st_mutex = 70 mutex_obj_alloc(MUTEX_DEFAULT, IPL_SCHED); 71 sleepq_init(sq); 72 } 73 } 74 75 /* 76 * sleepq_init: 77 * 78 * Prepare a sleep queue for use. 79 */ 80 void 81 sleepq_init(sleepq_t *sq) 82 { 83 84 TAILQ_INIT(sq); 85 } 86 87 /* 88 * sleepq_remove: 89 * 90 * Remove an LWP from a sleep queue and wake it up. 91 */ 92 void 93 sleepq_remove(sleepq_t *sq, lwp_t *l) 94 { 95 struct schedstate_percpu *spc; 96 struct cpu_info *ci; 97 98 KASSERT(lwp_locked(l, NULL)); 99 100 TAILQ_REMOVE(sq, l, l_sleepchain); 101 l->l_syncobj = &sched_syncobj; 102 l->l_wchan = NULL; 103 l->l_sleepq = NULL; 104 l->l_flag &= ~LW_SINTR; 105 106 ci = l->l_cpu; 107 spc = &ci->ci_schedstate; 108 109 /* 110 * If not sleeping, the LWP must have been suspended. Let whoever 111 * holds it stopped set it running again. 112 */ 113 if (l->l_stat != LSSLEEP) { 114 KASSERT(l->l_stat == LSSTOP || l->l_stat == LSSUSPENDED); 115 lwp_setlock(l, spc->spc_lwplock); 116 return; 117 } 118 119 /* 120 * If the LWP is still on the CPU, mark it as LSONPROC. It may be 121 * about to call mi_switch(), in which case it will yield. 122 */ 123 if ((l->l_pflag & LP_RUNNING) != 0) { 124 l->l_stat = LSONPROC; 125 l->l_slptime = 0; 126 lwp_setlock(l, spc->spc_lwplock); 127 return; 128 } 129 130 /* Update sleep time delta, call the wake-up handler of scheduler */ 131 l->l_slpticksum += (hardclock_ticks - l->l_slpticks); 132 sched_wakeup(l); 133 134 /* Look for a CPU to wake up */ 135 l->l_cpu = sched_takecpu(l); 136 ci = l->l_cpu; 137 spc = &ci->ci_schedstate; 138 139 /* 140 * Set it running. 141 */ 142 spc_lock(ci); 143 lwp_setlock(l, spc->spc_mutex); 144 sched_setrunnable(l); 145 l->l_stat = LSRUN; 146 l->l_slptime = 0; 147 sched_enqueue(l, false); 148 spc_unlock(ci); 149 } 150 151 /* 152 * sleepq_insert: 153 * 154 * Insert an LWP into the sleep queue, optionally sorting by priority. 155 */ 156 static void 157 sleepq_insert(sleepq_t *sq, lwp_t *l, syncobj_t *sobj) 158 { 159 160 if ((sobj->sobj_flag & SOBJ_SLEEPQ_SORTED) != 0) { 161 lwp_t *l2; 162 const int pri = lwp_eprio(l); 163 164 TAILQ_FOREACH(l2, sq, l_sleepchain) { 165 if (lwp_eprio(l2) < pri) { 166 TAILQ_INSERT_BEFORE(l2, l, l_sleepchain); 167 return; 168 } 169 } 170 } 171 172 if ((sobj->sobj_flag & SOBJ_SLEEPQ_LIFO) != 0) 173 TAILQ_INSERT_HEAD(sq, l, l_sleepchain); 174 else 175 TAILQ_INSERT_TAIL(sq, l, l_sleepchain); 176 } 177 178 /* 179 * sleepq_enqueue: 180 * 181 * Enter an LWP into the sleep queue and prepare for sleep. The sleep 182 * queue must already be locked, and any interlock (such as the kernel 183 * lock) must have be released (see sleeptab_lookup(), sleepq_enter()). 184 */ 185 void 186 sleepq_enqueue(sleepq_t *sq, wchan_t wchan, const char *wmesg, syncobj_t *sobj) 187 { 188 lwp_t *l = curlwp; 189 190 KASSERT(lwp_locked(l, NULL)); 191 KASSERT(l->l_stat == LSONPROC); 192 KASSERT(l->l_wchan == NULL && l->l_sleepq == NULL); 193 194 l->l_syncobj = sobj; 195 l->l_wchan = wchan; 196 l->l_sleepq = sq; 197 l->l_wmesg = wmesg; 198 l->l_slptime = 0; 199 l->l_stat = LSSLEEP; 200 l->l_sleeperr = 0; 201 202 sleepq_insert(sq, l, sobj); 203 204 /* Save the time when thread has slept */ 205 l->l_slpticks = hardclock_ticks; 206 sched_slept(l); 207 } 208 209 /* 210 * sleepq_block: 211 * 212 * After any intermediate step such as releasing an interlock, switch. 213 * sleepq_block() may return early under exceptional conditions, for 214 * example if the LWP's containing process is exiting. 215 */ 216 int 217 sleepq_block(int timo, bool catch) 218 { 219 int error = 0, sig; 220 struct proc *p; 221 lwp_t *l = curlwp; 222 bool early = false; 223 int biglocks = l->l_biglocks; 224 225 ktrcsw(1, 0); 226 227 /* 228 * If sleeping interruptably, check for pending signals, exits or 229 * core dump events. 230 */ 231 if (catch) { 232 l->l_flag |= LW_SINTR; 233 if ((l->l_flag & (LW_CANCELLED|LW_WEXIT|LW_WCORE)) != 0) { 234 l->l_flag &= ~LW_CANCELLED; 235 error = EINTR; 236 early = true; 237 } else if ((l->l_flag & LW_PENDSIG) != 0 && sigispending(l, 0)) 238 early = true; 239 } 240 241 if (early) { 242 /* lwp_unsleep() will release the lock */ 243 lwp_unsleep(l, true); 244 } else { 245 if (timo) { 246 callout_schedule(&l->l_timeout_ch, timo); 247 } 248 mi_switch(l); 249 250 /* The LWP and sleep queue are now unlocked. */ 251 if (timo) { 252 /* 253 * Even if the callout appears to have fired, we need to 254 * stop it in order to synchronise with other CPUs. 255 */ 256 if (callout_halt(&l->l_timeout_ch, NULL)) 257 error = EWOULDBLOCK; 258 } 259 } 260 261 if (catch && error == 0) { 262 p = l->l_proc; 263 if ((l->l_flag & (LW_CANCELLED | LW_WEXIT | LW_WCORE)) != 0) 264 error = EINTR; 265 else if ((l->l_flag & LW_PENDSIG) != 0) { 266 /* 267 * Acquiring p_lock may cause us to recurse 268 * through the sleep path and back into this 269 * routine, but is safe because LWPs sleeping 270 * on locks are non-interruptable. We will 271 * not recurse again. 272 */ 273 mutex_enter(p->p_lock); 274 if (((sig = sigispending(l, 0)) != 0 && 275 (sigprop[sig] & SA_STOP) == 0) || 276 (sig = issignal(l)) != 0) 277 error = sleepq_sigtoerror(l, sig); 278 mutex_exit(p->p_lock); 279 } 280 } 281 282 ktrcsw(0, 0); 283 if (__predict_false(biglocks != 0)) { 284 KERNEL_LOCK(biglocks, NULL); 285 } 286 return error; 287 } 288 289 /* 290 * sleepq_wake: 291 * 292 * Wake zero or more LWPs blocked on a single wait channel. 293 */ 294 lwp_t * 295 sleepq_wake(sleepq_t *sq, wchan_t wchan, u_int expected, kmutex_t *mp) 296 { 297 lwp_t *l, *next; 298 299 KASSERT(mutex_owned(mp)); 300 301 for (l = TAILQ_FIRST(sq); l != NULL; l = next) { 302 KASSERT(l->l_sleepq == sq); 303 KASSERT(l->l_mutex == mp); 304 next = TAILQ_NEXT(l, l_sleepchain); 305 if (l->l_wchan != wchan) 306 continue; 307 sleepq_remove(sq, l); 308 if (--expected == 0) 309 break; 310 } 311 312 mutex_spin_exit(mp); 313 return l; 314 } 315 316 /* 317 * sleepq_unsleep: 318 * 319 * Remove an LWP from its sleep queue and set it runnable again. 320 * sleepq_unsleep() is called with the LWP's mutex held, and will 321 * always release it. 322 */ 323 void 324 sleepq_unsleep(lwp_t *l, bool cleanup) 325 { 326 sleepq_t *sq = l->l_sleepq; 327 kmutex_t *mp = l->l_mutex; 328 329 KASSERT(lwp_locked(l, mp)); 330 KASSERT(l->l_wchan != NULL); 331 332 sleepq_remove(sq, l); 333 if (cleanup) { 334 mutex_spin_exit(mp); 335 } 336 } 337 338 /* 339 * sleepq_timeout: 340 * 341 * Entered via the callout(9) subsystem to time out an LWP that is on a 342 * sleep queue. 343 */ 344 void 345 sleepq_timeout(void *arg) 346 { 347 lwp_t *l = arg; 348 349 /* 350 * Lock the LWP. Assuming it's still on the sleep queue, its 351 * current mutex will also be the sleep queue mutex. 352 */ 353 lwp_lock(l); 354 355 if (l->l_wchan == NULL) { 356 /* Somebody beat us to it. */ 357 lwp_unlock(l); 358 return; 359 } 360 361 lwp_unsleep(l, true); 362 } 363 364 /* 365 * sleepq_sigtoerror: 366 * 367 * Given a signal number, interpret and return an error code. 368 */ 369 static int 370 sleepq_sigtoerror(lwp_t *l, int sig) 371 { 372 struct proc *p = l->l_proc; 373 int error; 374 375 KASSERT(mutex_owned(p->p_lock)); 376 377 /* 378 * If this sleep was canceled, don't let the syscall restart. 379 */ 380 if ((SIGACTION(p, sig).sa_flags & SA_RESTART) == 0) 381 error = EINTR; 382 else 383 error = ERESTART; 384 385 return error; 386 } 387 388 /* 389 * sleepq_abort: 390 * 391 * After a panic or during autoconfiguration, lower the interrupt 392 * priority level to give pending interrupts a chance to run, and 393 * then return. Called if sleepq_dontsleep() returns non-zero, and 394 * always returns zero. 395 */ 396 int 397 sleepq_abort(kmutex_t *mtx, int unlock) 398 { 399 extern int safepri; 400 int s; 401 402 s = splhigh(); 403 splx(safepri); 404 splx(s); 405 if (mtx != NULL && unlock != 0) 406 mutex_exit(mtx); 407 408 return 0; 409 } 410 411 /* 412 * sleepq_reinsert: 413 * 414 * Move the possition of the lwp in the sleep queue after a possible 415 * change of the lwp's effective priority. 416 */ 417 static void 418 sleepq_reinsert(sleepq_t *sq, lwp_t *l) 419 { 420 421 KASSERT(l->l_sleepq == sq); 422 if ((l->l_syncobj->sobj_flag & SOBJ_SLEEPQ_SORTED) == 0) { 423 return; 424 } 425 426 /* 427 * Don't let the sleep queue become empty, even briefly. 428 * cv_signal() and cv_broadcast() inspect it without the 429 * sleep queue lock held and need to see a non-empty queue 430 * head if there are waiters. 431 */ 432 if (TAILQ_FIRST(sq) == l && TAILQ_NEXT(l, l_sleepchain) == NULL) { 433 return; 434 } 435 TAILQ_REMOVE(sq, l, l_sleepchain); 436 sleepq_insert(sq, l, l->l_syncobj); 437 } 438 439 /* 440 * sleepq_changepri: 441 * 442 * Adjust the priority of an LWP residing on a sleepq. 443 */ 444 void 445 sleepq_changepri(lwp_t *l, pri_t pri) 446 { 447 sleepq_t *sq = l->l_sleepq; 448 449 KASSERT(lwp_locked(l, NULL)); 450 451 l->l_priority = pri; 452 sleepq_reinsert(sq, l); 453 } 454 455 /* 456 * sleepq_changepri: 457 * 458 * Adjust the lended priority of an LWP residing on a sleepq. 459 */ 460 void 461 sleepq_lendpri(lwp_t *l, pri_t pri) 462 { 463 sleepq_t *sq = l->l_sleepq; 464 465 KASSERT(lwp_locked(l, NULL)); 466 467 l->l_inheritedprio = pri; 468 sleepq_reinsert(sq, l); 469 } 470