subr_sleepqueue.c revision 177132
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: head/sys/kern/subr_sleepqueue.c 177132 2008-03-13 00:46:12Z jeff $"); 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 */ 118struct 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 129struct 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 139u_int sleepq_max_depth; 140SYSCTL_NODE(_debug, OID_AUTO, sleepq, CTLFLAG_RD, 0, "sleepq profiling"); 141SYSCTL_NODE(_debug_sleepq, OID_AUTO, chains, CTLFLAG_RD, 0, 142 "sleepq chain stats"); 143SYSCTL_UINT(_debug_sleepq, OID_AUTO, max_depth, CTLFLAG_RD, &sleepq_max_depth, 144 0, "maxmimum depth achieved of a single chain"); 145#endif 146static struct sleepqueue_chain sleepq_chains[SC_TABLESIZE]; 147static uma_zone_t sleepq_zone; 148 149/* 150 * Prototypes for non-exported routines. 151 */ 152static int sleepq_catch_signals(void *wchan, int pri); 153static int sleepq_check_signals(void); 154static int sleepq_check_timeout(void); 155#ifdef INVARIANTS 156static void sleepq_dtor(void *mem, int size, void *arg); 157#endif 158static int sleepq_init(void *mem, int size, int flags); 159static void sleepq_resume_thread(struct sleepqueue *sq, struct thread *td, 160 int pri); 161static void sleepq_switch(void *wchan, int pri); 162static void sleepq_timeout(void *arg); 163 164/* 165 * Early initialization of sleep queues that is called from the sleepinit() 166 * SYSINIT. 167 */ 168void 169init_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 */ 206struct sleepqueue * 207sleepq_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 */ 216void 217sleepq_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 */ 226void 227sleepq_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 */ 240struct sleepqueue * 241sleepq_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 */ 258void 259sleepq_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 */ 273void 274sleepq_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 */ 348void 349sleepq_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 */ 369static int 370sleepq_catch_signals(void *wchan, int pri) 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 the per-process spinlock prior to dropping the PROC_LOCK 407 * to avoid a signal delivery race. PROC_LOCK, PROC_SLOCK, and 408 * thread_lock() are currently held in tdsignal(). 409 */ 410 PROC_SLOCK(p); 411 mtx_lock_spin(&sc->sc_lock); 412 PROC_UNLOCK(p); 413 thread_lock(td); 414 PROC_SUNLOCK(p); 415 if (ret == 0) { 416 sleepq_switch(wchan, pri); 417 return (0); 418 } 419 /* 420 * There were pending signals and this thread is still 421 * on the sleep queue, remove it from the sleep queue. 422 */ 423 if (TD_ON_SLEEPQ(td)) { 424 sq = sleepq_lookup(wchan); 425 sleepq_resume_thread(sq, td, 0); 426 } 427 mtx_unlock_spin(&sc->sc_lock); 428 MPASS(td->td_lock != &sc->sc_lock); 429 return (ret); 430} 431 432/* 433 * Switches to another thread if we are still asleep on a sleep queue. 434 * Returns with thread lock. 435 */ 436static void 437sleepq_switch(void *wchan, int pri) 438{ 439 struct sleepqueue_chain *sc; 440 struct sleepqueue *sq; 441 struct thread *td; 442 443 td = curthread; 444 sc = SC_LOOKUP(wchan); 445 mtx_assert(&sc->sc_lock, MA_OWNED); 446 THREAD_LOCK_ASSERT(td, MA_OWNED); 447 448 /* 449 * If we have a sleep queue, then we've already been woken up, so 450 * just return. 451 */ 452 if (td->td_sleepqueue != NULL) { 453 mtx_unlock_spin(&sc->sc_lock); 454 return; 455 } 456 457 /* 458 * If TDF_TIMEOUT is set, then our sleep has been timed out 459 * already but we are still on the sleep queue, so dequeue the 460 * thread and return. 461 */ 462 if (td->td_flags & TDF_TIMEOUT) { 463 MPASS(TD_ON_SLEEPQ(td)); 464 sq = sleepq_lookup(wchan); 465 sleepq_resume_thread(sq, td, 0); 466 mtx_unlock_spin(&sc->sc_lock); 467 return; 468 } 469 470 MPASS(td->td_sleepqueue == NULL); 471 sched_sleep(td, pri); 472 thread_lock_set(td, &sc->sc_lock); 473 TD_SET_SLEEPING(td); 474 SCHED_STAT_INC(switch_sleepq); 475 mi_switch(SW_VOL, NULL); 476 KASSERT(TD_IS_RUNNING(td), ("running but not TDS_RUNNING")); 477 CTR3(KTR_PROC, "sleepq resume: thread %p (pid %ld, %s)", 478 (void *)td, (long)td->td_proc->p_pid, (void *)td->td_name); 479} 480 481/* 482 * Check to see if we timed out. 483 */ 484static int 485sleepq_check_timeout(void) 486{ 487 struct thread *td; 488 489 td = curthread; 490 THREAD_LOCK_ASSERT(td, MA_OWNED); 491 492 /* 493 * If TDF_TIMEOUT is set, we timed out. 494 */ 495 if (td->td_flags & TDF_TIMEOUT) { 496 td->td_flags &= ~TDF_TIMEOUT; 497 return (EWOULDBLOCK); 498 } 499 500 /* 501 * If TDF_TIMOFAIL is set, the timeout ran after we had 502 * already been woken up. 503 */ 504 if (td->td_flags & TDF_TIMOFAIL) 505 td->td_flags &= ~TDF_TIMOFAIL; 506 507 /* 508 * If callout_stop() fails, then the timeout is running on 509 * another CPU, so synchronize with it to avoid having it 510 * accidentally wake up a subsequent sleep. 511 */ 512 else if (callout_stop(&td->td_slpcallout) == 0) { 513 td->td_flags |= TDF_TIMEOUT; 514 TD_SET_SLEEPING(td); 515 SCHED_STAT_INC(switch_sleepqtimo); 516 mi_switch(SW_INVOL, NULL); 517 } 518 return (0); 519} 520 521/* 522 * Check to see if we were awoken by a signal. 523 */ 524static int 525sleepq_check_signals(void) 526{ 527 struct thread *td; 528 529 td = curthread; 530 THREAD_LOCK_ASSERT(td, MA_OWNED); 531 532 /* We are no longer in an interruptible sleep. */ 533 if (td->td_flags & TDF_SINTR) 534 td->td_flags &= ~TDF_SINTR; 535 536 if (td->td_flags & TDF_SLEEPABORT) { 537 td->td_flags &= ~TDF_SLEEPABORT; 538 return (td->td_intrval); 539 } 540 541 return (0); 542} 543 544/* 545 * Block the current thread until it is awakened from its sleep queue. 546 */ 547void 548sleepq_wait(void *wchan, int pri) 549{ 550 struct thread *td; 551 552 td = curthread; 553 MPASS(!(td->td_flags & TDF_SINTR)); 554 thread_lock(td); 555 sleepq_switch(wchan, pri); 556 thread_unlock(td); 557} 558 559/* 560 * Block the current thread until it is awakened from its sleep queue 561 * or it is interrupted by a signal. 562 */ 563int 564sleepq_wait_sig(void *wchan, int pri) 565{ 566 int rcatch; 567 int rval; 568 569 rcatch = sleepq_catch_signals(wchan, pri); 570 rval = sleepq_check_signals(); 571 thread_unlock(curthread); 572 if (rcatch) 573 return (rcatch); 574 return (rval); 575} 576 577/* 578 * Block the current thread until it is awakened from its sleep queue 579 * or it times out while waiting. 580 */ 581int 582sleepq_timedwait(void *wchan, int pri) 583{ 584 struct thread *td; 585 int rval; 586 587 td = curthread; 588 MPASS(!(td->td_flags & TDF_SINTR)); 589 thread_lock(td); 590 sleepq_switch(wchan, pri); 591 rval = sleepq_check_timeout(); 592 thread_unlock(td); 593 594 return (rval); 595} 596 597/* 598 * Block the current thread until it is awakened from its sleep queue, 599 * it is interrupted by a signal, or it times out waiting to be awakened. 600 */ 601int 602sleepq_timedwait_sig(void *wchan, int pri) 603{ 604 int rcatch, rvalt, rvals; 605 606 rcatch = sleepq_catch_signals(wchan, pri); 607 rvalt = sleepq_check_timeout(); 608 rvals = sleepq_check_signals(); 609 thread_unlock(curthread); 610 if (rcatch) 611 return (rcatch); 612 if (rvals) 613 return (rvals); 614 return (rvalt); 615} 616 617/* 618 * Removes a thread from a sleep queue and makes it 619 * runnable. 620 */ 621static void 622sleepq_resume_thread(struct sleepqueue *sq, struct thread *td, int pri) 623{ 624 struct sleepqueue_chain *sc; 625 626 MPASS(td != NULL); 627 MPASS(sq->sq_wchan != NULL); 628 MPASS(td->td_wchan == sq->sq_wchan); 629 MPASS(td->td_sqqueue < NR_SLEEPQS && td->td_sqqueue >= 0); 630 THREAD_LOCK_ASSERT(td, MA_OWNED); 631 sc = SC_LOOKUP(sq->sq_wchan); 632 mtx_assert(&sc->sc_lock, MA_OWNED); 633 634 /* Remove the thread from the queue. */ 635 TAILQ_REMOVE(&sq->sq_blocked[td->td_sqqueue], td, td_slpq); 636 637 /* 638 * Get a sleep queue for this thread. If this is the last waiter, 639 * use the queue itself and take it out of the chain, otherwise, 640 * remove a queue from the free list. 641 */ 642 if (LIST_EMPTY(&sq->sq_free)) { 643 td->td_sleepqueue = sq; 644#ifdef INVARIANTS 645 sq->sq_wchan = NULL; 646#endif 647#ifdef SLEEPQUEUE_PROFILING 648 sc->sc_depth--; 649#endif 650 } else 651 td->td_sleepqueue = LIST_FIRST(&sq->sq_free); 652 LIST_REMOVE(td->td_sleepqueue, sq_hash); 653 654 td->td_wmesg = NULL; 655 td->td_wchan = NULL; 656 td->td_flags &= ~TDF_SINTR; 657 658 /* 659 * Note that thread td might not be sleeping if it is running 660 * sleepq_catch_signals() on another CPU or is blocked on 661 * its proc lock to check signals. It doesn't hurt to clear 662 * the sleeping flag if it isn't set though, so we just always 663 * do it. However, we can't assert that it is set. 664 */ 665 CTR3(KTR_PROC, "sleepq_wakeup: thread %p (pid %ld, %s)", 666 (void *)td, (long)td->td_proc->p_pid, td->td_name); 667 TD_CLR_SLEEPING(td); 668 669 /* Adjust priority if requested. */ 670 MPASS(pri == 0 || (pri >= PRI_MIN && pri <= PRI_MAX)); 671 if (pri != 0 && td->td_priority > pri) 672 sched_prio(td, pri); 673 setrunnable(td); 674} 675 676#ifdef INVARIANTS 677/* 678 * UMA zone item deallocator. 679 */ 680static void 681sleepq_dtor(void *mem, int size, void *arg) 682{ 683 struct sleepqueue *sq; 684 int i; 685 686 sq = mem; 687 for (i = 0; i < NR_SLEEPQS; i++) 688 MPASS(TAILQ_EMPTY(&sq->sq_blocked[i])); 689} 690#endif 691 692/* 693 * UMA zone item initializer. 694 */ 695static int 696sleepq_init(void *mem, int size, int flags) 697{ 698 struct sleepqueue *sq; 699 int i; 700 701 bzero(mem, size); 702 sq = mem; 703 for (i = 0; i < NR_SLEEPQS; i++) 704 TAILQ_INIT(&sq->sq_blocked[i]); 705 LIST_INIT(&sq->sq_free); 706 return (0); 707} 708 709/* 710 * Find the highest priority thread sleeping on a wait channel and resume it. 711 */ 712void 713sleepq_signal(void *wchan, int flags, int pri, int queue) 714{ 715 struct sleepqueue *sq; 716 struct thread *td, *besttd; 717 718 CTR2(KTR_PROC, "sleepq_signal(%p, %d)", wchan, flags); 719 KASSERT(wchan != NULL, ("%s: invalid NULL wait channel", __func__)); 720 MPASS((queue >= 0) && (queue < NR_SLEEPQS)); 721 sq = sleepq_lookup(wchan); 722 if (sq == NULL) 723 return; 724 KASSERT(sq->sq_type == (flags & SLEEPQ_TYPE), 725 ("%s: mismatch between sleep/wakeup and cv_*", __func__)); 726 727 /* 728 * Find the highest priority thread on the queue. If there is a 729 * tie, use the thread that first appears in the queue as it has 730 * been sleeping the longest since threads are always added to 731 * the tail of sleep queues. 732 */ 733 besttd = NULL; 734 TAILQ_FOREACH(td, &sq->sq_blocked[queue], td_slpq) { 735 if (besttd == NULL || td->td_priority < besttd->td_priority) 736 besttd = td; 737 } 738 MPASS(besttd != NULL); 739 thread_lock(besttd); 740 sleepq_resume_thread(sq, besttd, pri); 741 thread_unlock(besttd); 742} 743 744/* 745 * Resume all threads sleeping on a specified wait channel. 746 */ 747void 748sleepq_broadcast(void *wchan, int flags, int pri, int queue) 749{ 750 struct sleepqueue *sq; 751 struct thread *td; 752 753 CTR2(KTR_PROC, "sleepq_broadcast(%p, %d)", wchan, flags); 754 KASSERT(wchan != NULL, ("%s: invalid NULL wait channel", __func__)); 755 MPASS((queue >= 0) && (queue < NR_SLEEPQS)); 756 sq = sleepq_lookup(wchan); 757 if (sq == NULL) 758 return; 759 KASSERT(sq->sq_type == (flags & SLEEPQ_TYPE), 760 ("%s: mismatch between sleep/wakeup and cv_*", __func__)); 761 762 /* Resume all blocked threads on the sleep queue. */ 763 while (!TAILQ_EMPTY(&sq->sq_blocked[queue])) { 764 td = TAILQ_FIRST(&sq->sq_blocked[queue]); 765 thread_lock(td); 766 sleepq_resume_thread(sq, td, pri); 767 thread_unlock(td); 768 } 769} 770 771/* 772 * Time sleeping threads out. When the timeout expires, the thread is 773 * removed from the sleep queue and made runnable if it is still asleep. 774 */ 775static void 776sleepq_timeout(void *arg) 777{ 778 struct sleepqueue_chain *sc; 779 struct sleepqueue *sq; 780 struct thread *td; 781 void *wchan; 782 783 td = arg; 784 CTR3(KTR_PROC, "sleepq_timeout: thread %p (pid %ld, %s)", 785 (void *)td, (long)td->td_proc->p_pid, (void *)td->td_name); 786 787 /* 788 * First, see if the thread is asleep and get the wait channel if 789 * it is. 790 */ 791 thread_lock(td); 792 if (TD_IS_SLEEPING(td) && TD_ON_SLEEPQ(td)) { 793 wchan = td->td_wchan; 794 sc = SC_LOOKUP(wchan); 795 THREAD_LOCKPTR_ASSERT(td, &sc->sc_lock); 796 sq = sleepq_lookup(wchan); 797 MPASS(sq != NULL); 798 td->td_flags |= TDF_TIMEOUT; 799 sleepq_resume_thread(sq, td, 0); 800 thread_unlock(td); 801 return; 802 } 803 804 /* 805 * If the thread is on the SLEEPQ but isn't sleeping yet, it 806 * can either be on another CPU in between sleepq_add() and 807 * one of the sleepq_*wait*() routines or it can be in 808 * sleepq_catch_signals(). 809 */ 810 if (TD_ON_SLEEPQ(td)) { 811 td->td_flags |= TDF_TIMEOUT; 812 thread_unlock(td); 813 return; 814 } 815 816 /* 817 * Now check for the edge cases. First, if TDF_TIMEOUT is set, 818 * then the other thread has already yielded to us, so clear 819 * the flag and resume it. If TDF_TIMEOUT is not set, then the 820 * we know that the other thread is not on a sleep queue, but it 821 * hasn't resumed execution yet. In that case, set TDF_TIMOFAIL 822 * to let it know that the timeout has already run and doesn't 823 * need to be canceled. 824 */ 825 if (td->td_flags & TDF_TIMEOUT) { 826 MPASS(TD_IS_SLEEPING(td)); 827 td->td_flags &= ~TDF_TIMEOUT; 828 TD_CLR_SLEEPING(td); 829 setrunnable(td); 830 } else 831 td->td_flags |= TDF_TIMOFAIL; 832 thread_unlock(td); 833} 834 835/* 836 * Resumes a specific thread from the sleep queue associated with a specific 837 * wait channel if it is on that queue. 838 */ 839void 840sleepq_remove(struct thread *td, void *wchan) 841{ 842 struct sleepqueue *sq; 843 844 /* 845 * Look up the sleep queue for this wait channel, then re-check 846 * that the thread is asleep on that channel, if it is not, then 847 * bail. 848 */ 849 MPASS(wchan != NULL); 850 sleepq_lock(wchan); 851 sq = sleepq_lookup(wchan); 852 /* 853 * We can not lock the thread here as it may be sleeping on a 854 * different sleepq. However, holding the sleepq lock for this 855 * wchan can guarantee that we do not miss a wakeup for this 856 * channel. The asserts below will catch any false positives. 857 */ 858 if (!TD_ON_SLEEPQ(td) || td->td_wchan != wchan) { 859 sleepq_release(wchan); 860 return; 861 } 862 /* Thread is asleep on sleep queue sq, so wake it up. */ 863 thread_lock(td); 864 MPASS(sq != NULL); 865 MPASS(td->td_wchan == wchan); 866 sleepq_resume_thread(sq, td, 0); 867 thread_unlock(td); 868 sleepq_release(wchan); 869} 870 871/* 872 * Abort a thread as if an interrupt had occurred. Only abort 873 * interruptible waits (unfortunately it isn't safe to abort others). 874 */ 875void 876sleepq_abort(struct thread *td, int intrval) 877{ 878 struct sleepqueue *sq; 879 void *wchan; 880 881 THREAD_LOCK_ASSERT(td, MA_OWNED); 882 MPASS(TD_ON_SLEEPQ(td)); 883 MPASS(td->td_flags & TDF_SINTR); 884 MPASS(intrval == EINTR || intrval == ERESTART); 885 886 /* 887 * If the TDF_TIMEOUT flag is set, just leave. A 888 * timeout is scheduled anyhow. 889 */ 890 if (td->td_flags & TDF_TIMEOUT) 891 return; 892 893 CTR3(KTR_PROC, "sleepq_abort: thread %p (pid %ld, %s)", 894 (void *)td, (long)td->td_proc->p_pid, (void *)td->td_name); 895 td->td_intrval = intrval; 896 td->td_flags |= TDF_SLEEPABORT; 897 /* 898 * If the thread has not slept yet it will find the signal in 899 * sleepq_catch_signals() and call sleepq_resume_thread. Otherwise 900 * we have to do it here. 901 */ 902 if (!TD_IS_SLEEPING(td)) 903 return; 904 wchan = td->td_wchan; 905 MPASS(wchan != NULL); 906 sq = sleepq_lookup(wchan); 907 MPASS(sq != NULL); 908 909 /* Thread is asleep on sleep queue sq, so wake it up. */ 910 sleepq_resume_thread(sq, td, 0); 911} 912 913#ifdef DDB 914DB_SHOW_COMMAND(sleepq, db_show_sleepqueue) 915{ 916 struct sleepqueue_chain *sc; 917 struct sleepqueue *sq; 918#ifdef INVARIANTS 919 struct lock_object *lock; 920#endif 921 struct thread *td; 922 void *wchan; 923 int i; 924 925 if (!have_addr) 926 return; 927 928 /* 929 * First, see if there is an active sleep queue for the wait channel 930 * indicated by the address. 931 */ 932 wchan = (void *)addr; 933 sc = SC_LOOKUP(wchan); 934 LIST_FOREACH(sq, &sc->sc_queues, sq_hash) 935 if (sq->sq_wchan == wchan) 936 goto found; 937 938 /* 939 * Second, see if there is an active sleep queue at the address 940 * indicated. 941 */ 942 for (i = 0; i < SC_TABLESIZE; i++) 943 LIST_FOREACH(sq, &sleepq_chains[i].sc_queues, sq_hash) { 944 if (sq == (struct sleepqueue *)addr) 945 goto found; 946 } 947 948 db_printf("Unable to locate a sleep queue via %p\n", (void *)addr); 949 return; 950found: 951 db_printf("Wait channel: %p\n", sq->sq_wchan); 952#ifdef INVARIANTS 953 db_printf("Queue type: %d\n", sq->sq_type); 954 if (sq->sq_lock) { 955 lock = sq->sq_lock; 956 db_printf("Associated Interlock: %p - (%s) %s\n", lock, 957 LOCK_CLASS(lock)->lc_name, lock->lo_name); 958 } 959#endif 960 db_printf("Blocked threads:\n"); 961 for (i = 0; i < NR_SLEEPQS; i++) { 962 db_printf("\nQueue[%d]:\n", i); 963 if (TAILQ_EMPTY(&sq->sq_blocked[i])) 964 db_printf("\tempty\n"); 965 else 966 TAILQ_FOREACH(td, &sq->sq_blocked[0], 967 td_slpq) { 968 db_printf("\t%p (tid %d, pid %d, \"%s\")\n", td, 969 td->td_tid, td->td_proc->p_pid, 970 td->td_name[i] != '\0' ? td->td_name : 971 td->td_name); 972 } 973 } 974} 975 976/* Alias 'show sleepqueue' to 'show sleepq'. */ 977DB_SET(sleepqueue, db_show_sleepqueue, db_show_cmd_set, 0, NULL); 978#endif 979