1 /*- 2 * Copyright (c) 2004 John Baldwin <jhb@FreeBSD.org> 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions 7 * are met: 8 * 1. Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * 2. Redistributions in binary form must reproduce the above copyright 11 * notice, this list of conditions and the following disclaimer in the 12 * documentation and/or other materials provided with the distribution. 13 * 3. Neither the name of the author nor the names of any co-contributors 14 * may be used to endorse or promote products derived from this software 15 * without specific prior written permission. 16 * 17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 18 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 20 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 21 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 22 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 23 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 24 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 25 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 26 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 27 * SUCH DAMAGE. 28 */ 29 30 /* 31 * Implementation of sleep queues used to hold queue of threads blocked on 32 * a wait channel. Sleep queues different from turnstiles in that wait 33 * channels are not owned by anyone, so there is no priority propagation. 34 * Sleep queues can also provide a timeout and can also be interrupted by 35 * signals. That said, there are several similarities between the turnstile 36 * and sleep queue implementations. (Note: turnstiles were implemented 37 * first.) For example, both use a hash table of the same size where each 38 * bucket is referred to as a "chain" that contains both a spin lock and 39 * a linked list of queues. An individual queue is located by using a hash 40 * to pick a chain, locking the chain, and then walking the chain searching 41 * for the queue. This means that a wait channel object does not need to 42 * embed it's queue head just as locks do not embed their turnstile queue 43 * head. Threads also carry around a sleep queue that they lend to the 44 * wait channel when blocking. Just as in turnstiles, the queue includes 45 * a free list of the sleep queues of other threads blocked on the same 46 * wait channel in the case of multiple waiters. 47 * 48 * Some additional functionality provided by sleep queues include the 49 * ability to set a timeout. The timeout is managed using a per-thread 50 * callout that resumes a thread if it is asleep. A thread may also 51 * catch signals while it is asleep (aka an interruptible sleep). The 52 * signal code uses sleepq_abort() to interrupt a sleeping thread. Finally, 53 * sleep queues also provide some extra assertions. One is not allowed to 54 * mix the sleep/wakeup and cv APIs for a given wait channel. Also, one 55 * must consistently use the same lock to synchronize with a wait channel, 56 * though this check is currently only a warning for sleep/wakeup due to 57 * pre-existing abuse of that API. The same lock must also be held when 58 * awakening threads, though that is currently only enforced for condition 59 * variables. 60 */ 61 62 #include <sys/cdefs.h> 63 __FBSDID("$FreeBSD$"); 64 65 #include "opt_sleepqueue_profiling.h" 66 #include "opt_ddb.h" 67 #include "opt_sched.h" 68 69 #include <sys/param.h> 70 #include <sys/systm.h> 71 #include <sys/lock.h> 72 #include <sys/kernel.h> 73 #include <sys/ktr.h> 74 #include <sys/mutex.h> 75 #include <sys/proc.h> 76 #include <sys/sched.h> 77 #include <sys/signalvar.h> 78 #include <sys/sleepqueue.h> 79 #include <sys/sysctl.h> 80 81 #include <vm/uma.h> 82 83 #ifdef DDB 84 #include <ddb/ddb.h> 85 #endif 86 87 /* 88 * Constants for the hash table of sleep queue chains. These constants are 89 * the same ones that 4BSD (and possibly earlier versions of BSD) used. 90 * Basically, we ignore the lower 8 bits of the address since most wait 91 * channel pointers are aligned and only look at the next 7 bits for the 92 * hash. SC_TABLESIZE must be a power of two for SC_MASK to work properly. 93 */ 94 #define SC_TABLESIZE 128 /* Must be power of 2. */ 95 #define SC_MASK (SC_TABLESIZE - 1) 96 #define SC_SHIFT 8 97 #define SC_HASH(wc) (((uintptr_t)(wc) >> SC_SHIFT) & SC_MASK) 98 #define SC_LOOKUP(wc) &sleepq_chains[SC_HASH(wc)] 99 #define NR_SLEEPQS 2 100 /* 101 * There two different lists of sleep queues. Both lists are connected 102 * via the sq_hash entries. The first list is the sleep queue chain list 103 * that a sleep queue is on when it is attached to a wait channel. The 104 * second list is the free list hung off of a sleep queue that is attached 105 * to a wait channel. 106 * 107 * Each sleep queue also contains the wait channel it is attached to, the 108 * list of threads blocked on that wait channel, flags specific to the 109 * wait channel, and the lock used to synchronize with a wait channel. 110 * The flags are used to catch mismatches between the various consumers 111 * of the sleep queue API (e.g. sleep/wakeup and condition variables). 112 * The lock pointer is only used when invariants are enabled for various 113 * debugging checks. 114 * 115 * Locking key: 116 * c - sleep queue chain lock 117 */ 118 struct sleepqueue { 119 TAILQ_HEAD(, thread) sq_blocked[NR_SLEEPQS]; /* (c) Blocked threads. */ 120 LIST_ENTRY(sleepqueue) sq_hash; /* (c) Chain and free list. */ 121 LIST_HEAD(, sleepqueue) sq_free; /* (c) Free queues. */ 122 void *sq_wchan; /* (c) Wait channel. */ 123 #ifdef INVARIANTS 124 int sq_type; /* (c) Queue type. */ 125 struct lock_object *sq_lock; /* (c) Associated lock. */ 126 #endif 127 }; 128 129 struct sleepqueue_chain { 130 LIST_HEAD(, sleepqueue) sc_queues; /* List of sleep queues. */ 131 struct mtx sc_lock; /* Spin lock for this chain. */ 132 #ifdef SLEEPQUEUE_PROFILING 133 u_int sc_depth; /* Length of sc_queues. */ 134 u_int sc_max_depth; /* Max length of sc_queues. */ 135 #endif 136 }; 137 138 #ifdef SLEEPQUEUE_PROFILING 139 u_int sleepq_max_depth; 140 SYSCTL_NODE(_debug, OID_AUTO, sleepq, CTLFLAG_RD, 0, "sleepq profiling"); 141 SYSCTL_NODE(_debug_sleepq, OID_AUTO, chains, CTLFLAG_RD, 0, 142 "sleepq chain stats"); 143 SYSCTL_UINT(_debug_sleepq, OID_AUTO, max_depth, CTLFLAG_RD, &sleepq_max_depth, 144 0, "maxmimum depth achieved of a single chain"); 145 #endif 146 static struct sleepqueue_chain sleepq_chains[SC_TABLESIZE]; 147 static uma_zone_t sleepq_zone; 148 149 /* 150 * Prototypes for non-exported routines. 151 */ 152 static int sleepq_catch_signals(void *wchan); 153 static int sleepq_check_signals(void); 154 static int sleepq_check_timeout(void); 155 #ifdef INVARIANTS 156 static void sleepq_dtor(void *mem, int size, void *arg); 157 #endif 158 static int sleepq_init(void *mem, int size, int flags); 159 static void sleepq_resume_thread(struct sleepqueue *sq, struct thread *td, 160 int pri); 161 static void sleepq_switch(void *wchan); 162 static void sleepq_timeout(void *arg); 163 164 /* 165 * Early initialization of sleep queues that is called from the sleepinit() 166 * SYSINIT. 167 */ 168 void 169 init_sleepqueues(void) 170 { 171 #ifdef SLEEPQUEUE_PROFILING 172 struct sysctl_oid *chain_oid; 173 char chain_name[10]; 174 #endif 175 int i; 176 177 for (i = 0; i < SC_TABLESIZE; i++) { 178 LIST_INIT(&sleepq_chains[i].sc_queues); 179 mtx_init(&sleepq_chains[i].sc_lock, "sleepq chain", NULL, 180 MTX_SPIN | MTX_RECURSE); 181 #ifdef SLEEPQUEUE_PROFILING 182 snprintf(chain_name, sizeof(chain_name), "%d", i); 183 chain_oid = SYSCTL_ADD_NODE(NULL, 184 SYSCTL_STATIC_CHILDREN(_debug_sleepq_chains), OID_AUTO, 185 chain_name, CTLFLAG_RD, NULL, "sleepq chain stats"); 186 SYSCTL_ADD_UINT(NULL, SYSCTL_CHILDREN(chain_oid), OID_AUTO, 187 "depth", CTLFLAG_RD, &sleepq_chains[i].sc_depth, 0, NULL); 188 SYSCTL_ADD_UINT(NULL, SYSCTL_CHILDREN(chain_oid), OID_AUTO, 189 "max_depth", CTLFLAG_RD, &sleepq_chains[i].sc_max_depth, 0, 190 NULL); 191 #endif 192 } 193 sleepq_zone = uma_zcreate("SLEEPQUEUE", sizeof(struct sleepqueue), 194 #ifdef INVARIANTS 195 NULL, sleepq_dtor, sleepq_init, NULL, UMA_ALIGN_CACHE, 0); 196 #else 197 NULL, NULL, sleepq_init, NULL, UMA_ALIGN_CACHE, 0); 198 #endif 199 200 thread0.td_sleepqueue = sleepq_alloc(); 201 } 202 203 /* 204 * Get a sleep queue for a new thread. 205 */ 206 struct sleepqueue * 207 sleepq_alloc(void) 208 { 209 210 return (uma_zalloc(sleepq_zone, M_WAITOK)); 211 } 212 213 /* 214 * Free a sleep queue when a thread is destroyed. 215 */ 216 void 217 sleepq_free(struct sleepqueue *sq) 218 { 219 220 uma_zfree(sleepq_zone, sq); 221 } 222 223 /* 224 * Lock the sleep queue chain associated with the specified wait channel. 225 */ 226 void 227 sleepq_lock(void *wchan) 228 { 229 struct sleepqueue_chain *sc; 230 231 sc = SC_LOOKUP(wchan); 232 mtx_lock_spin(&sc->sc_lock); 233 } 234 235 /* 236 * Look up the sleep queue associated with a given wait channel in the hash 237 * table locking the associated sleep queue chain. If no queue is found in 238 * the table, NULL is returned. 239 */ 240 struct sleepqueue * 241 sleepq_lookup(void *wchan) 242 { 243 struct sleepqueue_chain *sc; 244 struct sleepqueue *sq; 245 246 KASSERT(wchan != NULL, ("%s: invalid NULL wait channel", __func__)); 247 sc = SC_LOOKUP(wchan); 248 mtx_assert(&sc->sc_lock, MA_OWNED); 249 LIST_FOREACH(sq, &sc->sc_queues, sq_hash) 250 if (sq->sq_wchan == wchan) 251 return (sq); 252 return (NULL); 253 } 254 255 /* 256 * Unlock the sleep queue chain associated with a given wait channel. 257 */ 258 void 259 sleepq_release(void *wchan) 260 { 261 struct sleepqueue_chain *sc; 262 263 sc = SC_LOOKUP(wchan); 264 mtx_unlock_spin(&sc->sc_lock); 265 } 266 267 /* 268 * Places the current thread on the sleep queue for the specified wait 269 * channel. If INVARIANTS is enabled, then it associates the passed in 270 * lock with the sleepq to make sure it is held when that sleep queue is 271 * woken up. 272 */ 273 void 274 sleepq_add(void *wchan, struct lock_object *lock, const char *wmesg, int flags, 275 int queue) 276 { 277 struct sleepqueue_chain *sc; 278 struct sleepqueue *sq; 279 struct thread *td; 280 281 td = curthread; 282 sc = SC_LOOKUP(wchan); 283 mtx_assert(&sc->sc_lock, MA_OWNED); 284 MPASS(td->td_sleepqueue != NULL); 285 MPASS(wchan != NULL); 286 MPASS((queue >= 0) && (queue < NR_SLEEPQS)); 287 288 /* If this thread is not allowed to sleep, die a horrible death. */ 289 KASSERT(!(td->td_pflags & TDP_NOSLEEPING), 290 ("Trying sleep, but thread marked as sleeping prohibited")); 291 292 /* Look up the sleep queue associated with the wait channel 'wchan'. */ 293 sq = sleepq_lookup(wchan); 294 295 /* 296 * If the wait channel does not already have a sleep queue, use 297 * this thread's sleep queue. Otherwise, insert the current thread 298 * into the sleep queue already in use by this wait channel. 299 */ 300 if (sq == NULL) { 301 #ifdef INVARIANTS 302 int i; 303 304 sq = td->td_sleepqueue; 305 for (i = 0; i < NR_SLEEPQS; i++) 306 KASSERT(TAILQ_EMPTY(&sq->sq_blocked[i]), 307 ("thread's sleep queue %d is not empty", i)); 308 KASSERT(LIST_EMPTY(&sq->sq_free), 309 ("thread's sleep queue has a non-empty free list")); 310 KASSERT(sq->sq_wchan == NULL, ("stale sq_wchan pointer")); 311 sq->sq_lock = lock; 312 sq->sq_type = flags & SLEEPQ_TYPE; 313 #endif 314 #ifdef SLEEPQUEUE_PROFILING 315 sc->sc_depth++; 316 if (sc->sc_depth > sc->sc_max_depth) { 317 sc->sc_max_depth = sc->sc_depth; 318 if (sc->sc_max_depth > sleepq_max_depth) 319 sleepq_max_depth = sc->sc_max_depth; 320 } 321 #endif 322 sq = td->td_sleepqueue; 323 LIST_INSERT_HEAD(&sc->sc_queues, sq, sq_hash); 324 sq->sq_wchan = wchan; 325 } else { 326 MPASS(wchan == sq->sq_wchan); 327 MPASS(lock == sq->sq_lock); 328 MPASS((flags & SLEEPQ_TYPE) == sq->sq_type); 329 LIST_INSERT_HEAD(&sq->sq_free, td->td_sleepqueue, sq_hash); 330 } 331 thread_lock(td); 332 TAILQ_INSERT_TAIL(&sq->sq_blocked[queue], td, td_slpq); 333 td->td_sleepqueue = NULL; 334 td->td_sqqueue = queue; 335 td->td_wchan = wchan; 336 td->td_wmesg = wmesg; 337 if (flags & SLEEPQ_INTERRUPTIBLE) { 338 td->td_flags |= TDF_SINTR; 339 td->td_flags &= ~TDF_SLEEPABORT; 340 } 341 thread_unlock(td); 342 } 343 344 /* 345 * Sets a timeout that will remove the current thread from the specified 346 * sleep queue after timo ticks if the thread has not already been awakened. 347 */ 348 void 349 sleepq_set_timeout(void *wchan, int timo) 350 { 351 struct sleepqueue_chain *sc; 352 struct thread *td; 353 354 td = curthread; 355 sc = SC_LOOKUP(wchan); 356 mtx_assert(&sc->sc_lock, MA_OWNED); 357 MPASS(TD_ON_SLEEPQ(td)); 358 MPASS(td->td_sleepqueue == NULL); 359 MPASS(wchan != NULL); 360 callout_reset(&td->td_slpcallout, timo, sleepq_timeout, td); 361 } 362 363 /* 364 * Marks the pending sleep of the current thread as interruptible and 365 * makes an initial check for pending signals before putting a thread 366 * to sleep. Enters and exits with the thread lock held. Thread lock 367 * may have transitioned from the sleepq lock to a run lock. 368 */ 369 static int 370 sleepq_catch_signals(void *wchan) 371 { 372 struct sleepqueue_chain *sc; 373 struct sleepqueue *sq; 374 struct thread *td; 375 struct proc *p; 376 struct sigacts *ps; 377 int sig, ret; 378 379 td = curthread; 380 p = curproc; 381 sc = SC_LOOKUP(wchan); 382 mtx_assert(&sc->sc_lock, MA_OWNED); 383 MPASS(wchan != NULL); 384 CTR3(KTR_PROC, "sleepq catching signals: thread %p (pid %ld, %s)", 385 (void *)td, (long)p->p_pid, td->td_name); 386 387 mtx_unlock_spin(&sc->sc_lock); 388 389 /* See if there are any pending signals for this thread. */ 390 PROC_LOCK(p); 391 ps = p->p_sigacts; 392 mtx_lock(&ps->ps_mtx); 393 sig = cursig(td); 394 if (sig == 0) { 395 mtx_unlock(&ps->ps_mtx); 396 ret = thread_suspend_check(1); 397 MPASS(ret == 0 || ret == EINTR || ret == ERESTART); 398 } else { 399 if (SIGISMEMBER(ps->ps_sigintr, sig)) 400 ret = EINTR; 401 else 402 ret = ERESTART; 403 mtx_unlock(&ps->ps_mtx); 404 } 405 /* 406 * Lock sleepq chain before unlocking proc 407 * without this, we could lose a race. 408 */ 409 mtx_lock_spin(&sc->sc_lock); 410 PROC_UNLOCK(p); 411 thread_lock(td); 412 if (ret == 0) { 413 if (!(td->td_flags & TDF_INTERRUPT)) { 414 sleepq_switch(wchan); 415 return (0); 416 } 417 /* KSE threads tried unblocking us. */ 418 ret = td->td_intrval; 419 MPASS(ret == EINTR || ret == ERESTART || ret == EWOULDBLOCK); 420 } 421 /* 422 * There were pending signals and this thread is still 423 * on the sleep queue, remove it from the sleep queue. 424 */ 425 if (TD_ON_SLEEPQ(td)) { 426 sq = sleepq_lookup(wchan); 427 sleepq_resume_thread(sq, td, -1); 428 } 429 mtx_unlock_spin(&sc->sc_lock); 430 MPASS(td->td_lock != &sc->sc_lock); 431 return (ret); 432 } 433 434 /* 435 * Switches to another thread if we are still asleep on a sleep queue. 436 * Returns with thread lock. 437 */ 438 static void 439 sleepq_switch(void *wchan) 440 { 441 struct sleepqueue_chain *sc; 442 struct sleepqueue *sq; 443 struct thread *td; 444 445 td = curthread; 446 sc = SC_LOOKUP(wchan); 447 mtx_assert(&sc->sc_lock, MA_OWNED); 448 THREAD_LOCK_ASSERT(td, MA_OWNED); 449 450 /* 451 * If we have a sleep queue, then we've already been woken up, so 452 * just return. 453 */ 454 if (td->td_sleepqueue != NULL) { 455 mtx_unlock_spin(&sc->sc_lock); 456 return; 457 } 458 459 /* 460 * If TDF_TIMEOUT is set, then our sleep has been timed out 461 * already but we are still on the sleep queue, so dequeue the 462 * thread and return. 463 */ 464 if (td->td_flags & TDF_TIMEOUT) { 465 MPASS(TD_ON_SLEEPQ(td)); 466 sq = sleepq_lookup(wchan); 467 sleepq_resume_thread(sq, td, -1); 468 mtx_unlock_spin(&sc->sc_lock); 469 return; 470 } 471 472 thread_lock_set(td, &sc->sc_lock); 473 474 MPASS(td->td_sleepqueue == NULL); 475 sched_sleep(td); 476 TD_SET_SLEEPING(td); 477 SCHED_STAT_INC(switch_sleepq); 478 mi_switch(SW_VOL, NULL); 479 KASSERT(TD_IS_RUNNING(td), ("running but not TDS_RUNNING")); 480 CTR3(KTR_PROC, "sleepq resume: thread %p (pid %ld, %s)", 481 (void *)td, (long)td->td_proc->p_pid, (void *)td->td_name); 482 } 483 484 /* 485 * Check to see if we timed out. 486 */ 487 static int 488 sleepq_check_timeout(void) 489 { 490 struct thread *td; 491 492 td = curthread; 493 THREAD_LOCK_ASSERT(td, MA_OWNED); 494 495 /* 496 * If TDF_TIMEOUT is set, we timed out. 497 */ 498 if (td->td_flags & TDF_TIMEOUT) { 499 td->td_flags &= ~TDF_TIMEOUT; 500 return (EWOULDBLOCK); 501 } 502 503 /* 504 * If TDF_TIMOFAIL is set, the timeout ran after we had 505 * already been woken up. 506 */ 507 if (td->td_flags & TDF_TIMOFAIL) 508 td->td_flags &= ~TDF_TIMOFAIL; 509 510 /* 511 * If callout_stop() fails, then the timeout is running on 512 * another CPU, so synchronize with it to avoid having it 513 * accidentally wake up a subsequent sleep. 514 */ 515 else if (callout_stop(&td->td_slpcallout) == 0) { 516 td->td_flags |= TDF_TIMEOUT; 517 TD_SET_SLEEPING(td); 518 SCHED_STAT_INC(switch_sleepqtimo); 519 mi_switch(SW_INVOL, NULL); 520 } 521 return (0); 522 } 523 524 /* 525 * Check to see if we were awoken by a signal. 526 */ 527 static int 528 sleepq_check_signals(void) 529 { 530 struct thread *td; 531 532 td = curthread; 533 THREAD_LOCK_ASSERT(td, MA_OWNED); 534 535 /* We are no longer in an interruptible sleep. */ 536 if (td->td_flags & TDF_SINTR) 537 td->td_flags &= ~TDF_SINTR; 538 539 if (td->td_flags & TDF_SLEEPABORT) { 540 td->td_flags &= ~TDF_SLEEPABORT; 541 return (td->td_intrval); 542 } 543 544 if (td->td_flags & TDF_INTERRUPT) 545 return (td->td_intrval); 546 547 return (0); 548 } 549 550 /* 551 * Block the current thread until it is awakened from its sleep queue. 552 */ 553 void 554 sleepq_wait(void *wchan) 555 { 556 struct thread *td; 557 558 td = curthread; 559 MPASS(!(td->td_flags & TDF_SINTR)); 560 thread_lock(td); 561 sleepq_switch(wchan); 562 thread_unlock(td); 563 } 564 565 /* 566 * Block the current thread until it is awakened from its sleep queue 567 * or it is interrupted by a signal. 568 */ 569 int 570 sleepq_wait_sig(void *wchan) 571 { 572 int rcatch; 573 int rval; 574 575 rcatch = sleepq_catch_signals(wchan); 576 rval = sleepq_check_signals(); 577 thread_unlock(curthread); 578 if (rcatch) 579 return (rcatch); 580 return (rval); 581 } 582 583 /* 584 * Block the current thread until it is awakened from its sleep queue 585 * or it times out while waiting. 586 */ 587 int 588 sleepq_timedwait(void *wchan) 589 { 590 struct thread *td; 591 int rval; 592 593 td = curthread; 594 MPASS(!(td->td_flags & TDF_SINTR)); 595 thread_lock(td); 596 sleepq_switch(wchan); 597 rval = sleepq_check_timeout(); 598 thread_unlock(td); 599 600 return (rval); 601 } 602 603 /* 604 * Block the current thread until it is awakened from its sleep queue, 605 * it is interrupted by a signal, or it times out waiting to be awakened. 606 */ 607 int 608 sleepq_timedwait_sig(void *wchan) 609 { 610 int rcatch, rvalt, rvals; 611 612 rcatch = sleepq_catch_signals(wchan); 613 rvalt = sleepq_check_timeout(); 614 rvals = sleepq_check_signals(); 615 thread_unlock(curthread); 616 if (rcatch) 617 return (rcatch); 618 if (rvals) 619 return (rvals); 620 return (rvalt); 621 } 622 623 /* 624 * Removes a thread from a sleep queue and makes it 625 * runnable. 626 */ 627 static void 628 sleepq_resume_thread(struct sleepqueue *sq, struct thread *td, int pri) 629 { 630 struct sleepqueue_chain *sc; 631 632 MPASS(td != NULL); 633 MPASS(sq->sq_wchan != NULL); 634 MPASS(td->td_wchan == sq->sq_wchan); 635 MPASS(td->td_sqqueue < NR_SLEEPQS && td->td_sqqueue >= 0); 636 THREAD_LOCK_ASSERT(td, MA_OWNED); 637 sc = SC_LOOKUP(sq->sq_wchan); 638 mtx_assert(&sc->sc_lock, MA_OWNED); 639 640 /* Remove the thread from the queue. */ 641 TAILQ_REMOVE(&sq->sq_blocked[td->td_sqqueue], td, td_slpq); 642 643 /* 644 * Get a sleep queue for this thread. If this is the last waiter, 645 * use the queue itself and take it out of the chain, otherwise, 646 * remove a queue from the free list. 647 */ 648 if (LIST_EMPTY(&sq->sq_free)) { 649 td->td_sleepqueue = sq; 650 #ifdef INVARIANTS 651 sq->sq_wchan = NULL; 652 #endif 653 #ifdef SLEEPQUEUE_PROFILING 654 sc->sc_depth--; 655 #endif 656 } else 657 td->td_sleepqueue = LIST_FIRST(&sq->sq_free); 658 LIST_REMOVE(td->td_sleepqueue, sq_hash); 659 660 td->td_wmesg = NULL; 661 td->td_wchan = NULL; 662 td->td_flags &= ~TDF_SINTR; 663 664 /* 665 * Note that thread td might not be sleeping if it is running 666 * sleepq_catch_signals() on another CPU or is blocked on 667 * its proc lock to check signals. It doesn't hurt to clear 668 * the sleeping flag if it isn't set though, so we just always 669 * do it. However, we can't assert that it is set. 670 */ 671 CTR3(KTR_PROC, "sleepq_wakeup: thread %p (pid %ld, %s)", 672 (void *)td, (long)td->td_proc->p_pid, td->td_name); 673 TD_CLR_SLEEPING(td); 674 675 /* Adjust priority if requested. */ 676 MPASS(pri == -1 || (pri >= PRI_MIN && pri <= PRI_MAX)); 677 if (pri != -1 && td->td_priority > pri) 678 sched_prio(td, pri); 679 setrunnable(td); 680 } 681 682 #ifdef INVARIANTS 683 /* 684 * UMA zone item deallocator. 685 */ 686 static void 687 sleepq_dtor(void *mem, int size, void *arg) 688 { 689 struct sleepqueue *sq; 690 int i; 691 692 sq = mem; 693 for (i = 0; i < NR_SLEEPQS; i++) 694 MPASS(TAILQ_EMPTY(&sq->sq_blocked[i])); 695 } 696 #endif 697 698 /* 699 * UMA zone item initializer. 700 */ 701 static int 702 sleepq_init(void *mem, int size, int flags) 703 { 704 struct sleepqueue *sq; 705 int i; 706 707 bzero(mem, size); 708 sq = mem; 709 for (i = 0; i < NR_SLEEPQS; i++) 710 TAILQ_INIT(&sq->sq_blocked[i]); 711 LIST_INIT(&sq->sq_free); 712 return (0); 713 } 714 715 /* 716 * Find the highest priority thread sleeping on a wait channel and resume it. 717 */ 718 void 719 sleepq_signal(void *wchan, int flags, int pri, int queue) 720 { 721 struct sleepqueue *sq; 722 struct thread *td, *besttd; 723 724 CTR2(KTR_PROC, "sleepq_signal(%p, %d)", wchan, flags); 725 KASSERT(wchan != NULL, ("%s: invalid NULL wait channel", __func__)); 726 MPASS((queue >= 0) && (queue < NR_SLEEPQS)); 727 sq = sleepq_lookup(wchan); 728 if (sq == NULL) 729 return; 730 KASSERT(sq->sq_type == (flags & SLEEPQ_TYPE), 731 ("%s: mismatch between sleep/wakeup and cv_*", __func__)); 732 733 /* 734 * Find the highest priority thread on the queue. If there is a 735 * tie, use the thread that first appears in the queue as it has 736 * been sleeping the longest since threads are always added to 737 * the tail of sleep queues. 738 */ 739 besttd = NULL; 740 TAILQ_FOREACH(td, &sq->sq_blocked[queue], td_slpq) { 741 if (besttd == NULL || td->td_priority < besttd->td_priority) 742 besttd = td; 743 } 744 MPASS(besttd != NULL); 745 thread_lock(besttd); 746 sleepq_resume_thread(sq, besttd, pri); 747 thread_unlock(besttd); 748 } 749 750 /* 751 * Resume all threads sleeping on a specified wait channel. 752 */ 753 void 754 sleepq_broadcast(void *wchan, int flags, int pri, int queue) 755 { 756 struct sleepqueue *sq; 757 struct thread *td; 758 759 CTR2(KTR_PROC, "sleepq_broadcast(%p, %d)", wchan, flags); 760 KASSERT(wchan != NULL, ("%s: invalid NULL wait channel", __func__)); 761 MPASS((queue >= 0) && (queue < NR_SLEEPQS)); 762 sq = sleepq_lookup(wchan); 763 if (sq == NULL) { 764 sleepq_release(wchan); 765 return; 766 } 767 KASSERT(sq->sq_type == (flags & SLEEPQ_TYPE), 768 ("%s: mismatch between sleep/wakeup and cv_*", __func__)); 769 770 /* Resume all blocked threads on the sleep queue. */ 771 while (!TAILQ_EMPTY(&sq->sq_blocked[queue])) { 772 td = TAILQ_FIRST(&sq->sq_blocked[queue]); 773 thread_lock(td); 774 sleepq_resume_thread(sq, td, pri); 775 thread_unlock(td); 776 } 777 sleepq_release(wchan); 778 } 779 780 /* 781 * Time sleeping threads out. When the timeout expires, the thread is 782 * removed from the sleep queue and made runnable if it is still asleep. 783 */ 784 static void 785 sleepq_timeout(void *arg) 786 { 787 struct sleepqueue_chain *sc; 788 struct sleepqueue *sq; 789 struct thread *td; 790 void *wchan; 791 792 td = arg; 793 CTR3(KTR_PROC, "sleepq_timeout: thread %p (pid %ld, %s)", 794 (void *)td, (long)td->td_proc->p_pid, (void *)td->td_name); 795 796 /* 797 * First, see if the thread is asleep and get the wait channel if 798 * it is. 799 */ 800 thread_lock(td); 801 if (TD_IS_SLEEPING(td) && TD_ON_SLEEPQ(td)) { 802 wchan = td->td_wchan; 803 sc = SC_LOOKUP(wchan); 804 THREAD_LOCKPTR_ASSERT(td, &sc->sc_lock); 805 sq = sleepq_lookup(wchan); 806 MPASS(sq != NULL); 807 td->td_flags |= TDF_TIMEOUT; 808 sleepq_resume_thread(sq, td, -1); 809 thread_unlock(td); 810 return; 811 } 812 813 /* 814 * If the thread is on the SLEEPQ but isn't sleeping yet, it 815 * can either be on another CPU in between sleepq_add() and 816 * one of the sleepq_*wait*() routines or it can be in 817 * sleepq_catch_signals(). 818 */ 819 if (TD_ON_SLEEPQ(td)) { 820 td->td_flags |= TDF_TIMEOUT; 821 thread_unlock(td); 822 return; 823 } 824 825 /* 826 * Now check for the edge cases. First, if TDF_TIMEOUT is set, 827 * then the other thread has already yielded to us, so clear 828 * the flag and resume it. If TDF_TIMEOUT is not set, then the 829 * we know that the other thread is not on a sleep queue, but it 830 * hasn't resumed execution yet. In that case, set TDF_TIMOFAIL 831 * to let it know that the timeout has already run and doesn't 832 * need to be canceled. 833 */ 834 if (td->td_flags & TDF_TIMEOUT) { 835 MPASS(TD_IS_SLEEPING(td)); 836 td->td_flags &= ~TDF_TIMEOUT; 837 TD_CLR_SLEEPING(td); 838 setrunnable(td); 839 } else 840 td->td_flags |= TDF_TIMOFAIL; 841 thread_unlock(td); 842 } 843 844 /* 845 * Resumes a specific thread from the sleep queue associated with a specific 846 * wait channel if it is on that queue. 847 */ 848 void 849 sleepq_remove(struct thread *td, void *wchan) 850 { 851 struct sleepqueue *sq; 852 853 /* 854 * Look up the sleep queue for this wait channel, then re-check 855 * that the thread is asleep on that channel, if it is not, then 856 * bail. 857 */ 858 MPASS(wchan != NULL); 859 sleepq_lock(wchan); 860 sq = sleepq_lookup(wchan); 861 /* 862 * We can not lock the thread here as it may be sleeping on a 863 * different sleepq. However, holding the sleepq lock for this 864 * wchan can guarantee that we do not miss a wakeup for this 865 * channel. The asserts below will catch any false positives. 866 */ 867 if (!TD_ON_SLEEPQ(td) || td->td_wchan != wchan) { 868 sleepq_release(wchan); 869 return; 870 } 871 /* Thread is asleep on sleep queue sq, so wake it up. */ 872 thread_lock(td); 873 MPASS(sq != NULL); 874 MPASS(td->td_wchan == wchan); 875 sleepq_resume_thread(sq, td, -1); 876 thread_unlock(td); 877 sleepq_release(wchan); 878 } 879 880 /* 881 * Abort a thread as if an interrupt had occurred. Only abort 882 * interruptible waits (unfortunately it isn't safe to abort others). 883 */ 884 void 885 sleepq_abort(struct thread *td, int intrval) 886 { 887 struct sleepqueue *sq; 888 void *wchan; 889 890 THREAD_LOCK_ASSERT(td, MA_OWNED); 891 MPASS(TD_ON_SLEEPQ(td)); 892 MPASS(td->td_flags & TDF_SINTR); 893 MPASS(intrval == EINTR || intrval == ERESTART); 894 895 /* 896 * If the TDF_TIMEOUT flag is set, just leave. A 897 * timeout is scheduled anyhow. 898 */ 899 if (td->td_flags & TDF_TIMEOUT) 900 return; 901 902 CTR3(KTR_PROC, "sleepq_abort: thread %p (pid %ld, %s)", 903 (void *)td, (long)td->td_proc->p_pid, (void *)td->td_name); 904 td->td_intrval = intrval; 905 td->td_flags |= TDF_SLEEPABORT; 906 /* 907 * If the thread has not slept yet it will find the signal in 908 * sleepq_catch_signals() and call sleepq_resume_thread. Otherwise 909 * we have to do it here. 910 */ 911 if (!TD_IS_SLEEPING(td)) 912 return; 913 wchan = td->td_wchan; 914 MPASS(wchan != NULL); 915 sq = sleepq_lookup(wchan); 916 MPASS(sq != NULL); 917 918 /* Thread is asleep on sleep queue sq, so wake it up. */ 919 sleepq_resume_thread(sq, td, -1); 920 } 921 922 #ifdef DDB 923 DB_SHOW_COMMAND(sleepq, db_show_sleepqueue) 924 { 925 struct sleepqueue_chain *sc; 926 struct sleepqueue *sq; 927 #ifdef INVARIANTS 928 struct lock_object *lock; 929 #endif 930 struct thread *td; 931 void *wchan; 932 int i; 933 934 if (!have_addr) 935 return; 936 937 /* 938 * First, see if there is an active sleep queue for the wait channel 939 * indicated by the address. 940 */ 941 wchan = (void *)addr; 942 sc = SC_LOOKUP(wchan); 943 LIST_FOREACH(sq, &sc->sc_queues, sq_hash) 944 if (sq->sq_wchan == wchan) 945 goto found; 946 947 /* 948 * Second, see if there is an active sleep queue at the address 949 * indicated. 950 */ 951 for (i = 0; i < SC_TABLESIZE; i++) 952 LIST_FOREACH(sq, &sleepq_chains[i].sc_queues, sq_hash) { 953 if (sq == (struct sleepqueue *)addr) 954 goto found; 955 } 956 957 db_printf("Unable to locate a sleep queue via %p\n", (void *)addr); 958 return; 959 found: 960 db_printf("Wait channel: %p\n", sq->sq_wchan); 961 #ifdef INVARIANTS 962 db_printf("Queue type: %d\n", sq->sq_type); 963 if (sq->sq_lock) { 964 lock = sq->sq_lock; 965 db_printf("Associated Interlock: %p - (%s) %s\n", lock, 966 LOCK_CLASS(lock)->lc_name, lock->lo_name); 967 } 968 #endif 969 db_printf("Blocked threads:\n"); 970 for (i = 0; i < NR_SLEEPQS; i++) { 971 db_printf("\nQueue[%d]:\n", i); 972 if (TAILQ_EMPTY(&sq->sq_blocked[i])) 973 db_printf("\tempty\n"); 974 else 975 TAILQ_FOREACH(td, &sq->sq_blocked[0], 976 td_slpq) { 977 db_printf("\t%p (tid %d, pid %d, \"%s\")\n", td, 978 td->td_tid, td->td_proc->p_pid, 979 td->td_name[i] != '\0' ? td->td_name : 980 td->td_name); 981 } 982 } 983 } 984 985 /* Alias 'show sleepqueue' to 'show sleepq'. */ 986 DB_SET(sleepqueue, db_show_sleepqueue, db_show_cmd_set, 0, NULL); 987 #endif 988