144743Smarkm/*- 244743Smarkm * Copyright (c) 1998 Berkeley Software Design, Inc. All rights reserved. 344743Smarkm * 444743Smarkm * Redistribution and use in source and binary forms, with or without 544743Smarkm * modification, are permitted provided that the following conditions 644743Smarkm * are met: 744743Smarkm * 1. Redistributions of source code must retain the above copyright 844743Smarkm * notice, this list of conditions and the following disclaimer. 944743Smarkm * 2. Redistributions in binary form must reproduce the above copyright 1044743Smarkm * notice, this list of conditions and the following disclaimer in the 1144743Smarkm * documentation and/or other materials provided with the distribution. 1244743Smarkm * 3. Berkeley Software Design Inc's name may not be used to endorse or 1344743Smarkm * promote products derived from this software without specific prior 1444743Smarkm * written permission. 1544743Smarkm * 1644743Smarkm * THIS SOFTWARE IS PROVIDED BY BERKELEY SOFTWARE DESIGN INC ``AS IS'' AND 1744743Smarkm * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 1844743Smarkm * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 1944743Smarkm * ARE DISCLAIMED. IN NO EVENT SHALL BERKELEY SOFTWARE DESIGN INC BE LIABLE 2044743Smarkm * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 2144743Smarkm * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 2244743Smarkm * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 2344743Smarkm * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 2444743Smarkm * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 2544743Smarkm * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 2644743Smarkm * SUCH DAMAGE. 2744743Smarkm * 2844743Smarkm * from BSDI $Id: mutex_witness.c,v 1.1.2.20 2000/04/27 03:10:27 cp Exp $ 2944743Smarkm * and BSDI $Id: synch_machdep.c,v 2.3.2.39 2000/04/27 03:10:25 cp Exp $ 3044743Smarkm */ 3144743Smarkm 3244743Smarkm/* 3344743Smarkm * Implementation of turnstiles used to hold queue of threads blocked on 3444743Smarkm * non-sleepable locks. Sleepable locks use condition variables to 3544743Smarkm * implement their queues. Turnstiles differ from a sleep queue in that 3644743Smarkm * turnstile queue's are assigned to a lock held by an owning thread. Thus, 3744743Smarkm * when one thread is enqueued onto a turnstile, it can lend its priority 3844743Smarkm * to the owning thread. 3944743Smarkm * 4044743Smarkm * We wish to avoid bloating locks with an embedded turnstile and we do not 4144743Smarkm * want to use back-pointers in the locks for the same reason. Thus, we 4244743Smarkm * use a similar approach to that of Solaris 7 as described in Solaris 4344743Smarkm * Internals by Jim Mauro and Richard McDougall. Turnstiles are looked up 4444743Smarkm * in a hash table based on the address of the lock. Each entry in the 4544743Smarkm * hash table is a linked-lists of turnstiles and is called a turnstile 4644743Smarkm * chain. Each chain contains a spin mutex that protects all of the 4744743Smarkm * turnstiles in the chain. 4844743Smarkm * 4944743Smarkm * Each time a thread is created, a turnstile is allocated from a UMA zone 5044743Smarkm * and attached to that thread. When a thread blocks on a lock, if it is the 5144743Smarkm * first thread to block, it lends its turnstile to the lock. If the lock 5244743Smarkm * already has a turnstile, then it gives its turnstile to the lock's 5344743Smarkm * turnstile's free list. When a thread is woken up, it takes a turnstile from 5444743Smarkm * the free list if there are any other waiters. If it is the only thread 5544743Smarkm * blocked on the lock, then it reclaims the turnstile associated with the lock 5644743Smarkm * and removes it from the hash table. 5744743Smarkm */ 5844743Smarkm 5944743Smarkm#include <sys/cdefs.h> 6044743Smarkm__FBSDID("$FreeBSD$"); 6144743Smarkm 6244743Smarkm#include "opt_ddb.h" 6344743Smarkm#include "opt_kdtrace.h" 6444743Smarkm#include "opt_turnstile_profiling.h" 6544743Smarkm#include "opt_sched.h" 6644743Smarkm 6744743Smarkm#include <sys/param.h> 6844743Smarkm#include <sys/systm.h> 6944743Smarkm#include <sys/kdb.h> 7044743Smarkm#include <sys/kernel.h> 7144743Smarkm#include <sys/ktr.h> 7244743Smarkm#include <sys/lock.h> 7344743Smarkm#include <sys/mutex.h> 7444743Smarkm#include <sys/proc.h> 7544743Smarkm#include <sys/queue.h> 7644743Smarkm#include <sys/sched.h> 7744743Smarkm#include <sys/sdt.h> 7844743Smarkm#include <sys/sysctl.h> 7944743Smarkm#include <sys/turnstile.h> 8044743Smarkm 8144743Smarkm#include <vm/uma.h> 8244743Smarkm 8344743Smarkm#ifdef DDB 8444743Smarkm#include <ddb/ddb.h> 8544743Smarkm#include <sys/lockmgr.h> 8644743Smarkm#include <sys/sx.h> 8744743Smarkm#endif 8844743Smarkm 8944743Smarkm/* 9044743Smarkm * Constants for the hash table of turnstile chains. TC_SHIFT is a magic 9144743Smarkm * number chosen because the sleep queue's use the same value for the 9244743Smarkm * shift. Basically, we ignore the lower 8 bits of the address. 9344743Smarkm * TC_TABLESIZE must be a power of two for TC_MASK to work properly. 9444743Smarkm */ 9544743Smarkm#define TC_TABLESIZE 128 /* Must be power of 2. */ 9644743Smarkm#define TC_MASK (TC_TABLESIZE - 1) 9744743Smarkm#define TC_SHIFT 8 9844743Smarkm#define TC_HASH(lock) (((uintptr_t)(lock) >> TC_SHIFT) & TC_MASK) 9944743Smarkm#define TC_LOOKUP(lock) &turnstile_chains[TC_HASH(lock)] 10044743Smarkm 10144743Smarkm/* 10244743Smarkm * There are three different lists of turnstiles as follows. The list 10344743Smarkm * connected by ts_link entries is a per-thread list of all the turnstiles 10444743Smarkm * attached to locks that we own. This is used to fixup our priority when 10544743Smarkm * a lock is released. The other two lists use the ts_hash entries. The 10644743Smarkm * first of these two is the turnstile chain list that a turnstile is on 10744743Smarkm * when it is attached to a lock. The second list to use ts_hash is the 10844743Smarkm * free list hung off of a turnstile that is attached to a lock. 10944743Smarkm * 11044743Smarkm * Each turnstile contains three lists of threads. The two ts_blocked lists 11144743Smarkm * are linked list of threads blocked on the turnstile's lock. One list is 11244743Smarkm * for exclusive waiters, and the other is for shared waiters. The 11344743Smarkm * ts_pending list is a linked list of threads previously awakened by 11444743Smarkm * turnstile_signal() or turnstile_wait() that are waiting to be put on 11544743Smarkm * the run queue. 11644743Smarkm * 11744743Smarkm * Locking key: 11844743Smarkm * c - turnstile chain lock 11944743Smarkm * q - td_contested lock 12044743Smarkm */ 12144743Smarkmstruct turnstile { 12244743Smarkm struct mtx ts_lock; /* Spin lock for self. */ 12344743Smarkm struct threadqueue ts_blocked[2]; /* (c + q) Blocked threads. */ 12444743Smarkm struct threadqueue ts_pending; /* (c) Pending threads. */ 12544743Smarkm LIST_ENTRY(turnstile) ts_hash; /* (c) Chain and free list. */ 12644743Smarkm LIST_ENTRY(turnstile) ts_link; /* (q) Contested locks. */ 12744743Smarkm LIST_HEAD(, turnstile) ts_free; /* (c) Free turnstiles. */ 12844743Smarkm struct lock_object *ts_lockobj; /* (c) Lock we reference. */ 12944743Smarkm struct thread *ts_owner; /* (c + q) Who owns the lock. */ 13044743Smarkm}; 13144743Smarkm 13244743Smarkmstruct turnstile_chain { 13344743Smarkm LIST_HEAD(, turnstile) tc_turnstiles; /* List of turnstiles. */ 13444743Smarkm struct mtx tc_lock; /* Spin lock for this chain. */ 13544743Smarkm#ifdef TURNSTILE_PROFILING 13644743Smarkm u_int tc_depth; /* Length of tc_queues. */ 13744743Smarkm u_int tc_max_depth; /* Max length of tc_queues. */ 13844743Smarkm#endif 13944743Smarkm}; 14044743Smarkm 14144743Smarkm#ifdef TURNSTILE_PROFILING 14244743Smarkmu_int turnstile_max_depth; 14344743Smarkmstatic SYSCTL_NODE(_debug, OID_AUTO, turnstile, CTLFLAG_RD, 0, 14444743Smarkm "turnstile profiling"); 14544743Smarkmstatic SYSCTL_NODE(_debug_turnstile, OID_AUTO, chains, CTLFLAG_RD, 0, 14644743Smarkm "turnstile chain stats"); 14744743SmarkmSYSCTL_UINT(_debug_turnstile, OID_AUTO, max_depth, CTLFLAG_RD, 14844743Smarkm &turnstile_max_depth, 0, "maximum depth achieved of a single chain"); 14944743Smarkm#endif 15044743Smarkmstatic struct mtx td_contested_lock; 15144743Smarkmstatic struct turnstile_chain turnstile_chains[TC_TABLESIZE]; 15244743Smarkmstatic uma_zone_t turnstile_zone; 15344743Smarkm 15444743Smarkm/* 15544743Smarkm * Prototypes for non-exported routines. 15644743Smarkm */ 15744743Smarkmstatic void init_turnstile0(void *dummy); 15844743Smarkm#ifdef TURNSTILE_PROFILING 15944743Smarkmstatic void init_turnstile_profiling(void *arg); 16044743Smarkm#endif 16144743Smarkmstatic void propagate_priority(struct thread *td); 16244743Smarkmstatic int turnstile_adjust_thread(struct turnstile *ts, 16344743Smarkm struct thread *td); 16444743Smarkmstatic struct thread *turnstile_first_waiter(struct turnstile *ts); 16544743Smarkmstatic void turnstile_setowner(struct turnstile *ts, struct thread *owner); 16644743Smarkm#ifdef INVARIANTS 16744743Smarkmstatic void turnstile_dtor(void *mem, int size, void *arg); 16844743Smarkm#endif 16944743Smarkmstatic int turnstile_init(void *mem, int size, int flags); 17044743Smarkmstatic void turnstile_fini(void *mem, int size); 17144743Smarkm 17244743SmarkmSDT_PROVIDER_DECLARE(sched); 17344743SmarkmSDT_PROBE_DEFINE(sched, , , sleep); 17444743SmarkmSDT_PROBE_DEFINE2(sched, , , wakeup, "struct thread *", 17544743Smarkm "struct proc *"); 17644743Smarkm 17744743Smarkm/* 17844743Smarkm * Walks the chain of turnstiles and their owners to propagate the priority 17944743Smarkm * of the thread being blocked to all the threads holding locks that have to 18044743Smarkm * release their locks before this thread can run again. 18144743Smarkm */ 18244743Smarkmstatic void 18344743Smarkmpropagate_priority(struct thread *td) 18444743Smarkm{ 18544743Smarkm struct turnstile *ts; 18644743Smarkm int pri; 18744743Smarkm 18844743Smarkm THREAD_LOCK_ASSERT(td, MA_OWNED); 18944743Smarkm pri = td->td_priority; 19044743Smarkm ts = td->td_blocked; 19144743Smarkm THREAD_LOCKPTR_ASSERT(td, &ts->ts_lock); 19244743Smarkm /* 19344743Smarkm * Grab a recursive lock on this turnstile chain so it stays locked 194 * for the whole operation. The caller expects us to return with 195 * the original lock held. We only ever lock down the chain so 196 * the lock order is constant. 197 */ 198 mtx_lock_spin(&ts->ts_lock); 199 for (;;) { 200 td = ts->ts_owner; 201 202 if (td == NULL) { 203 /* 204 * This might be a read lock with no owner. There's 205 * not much we can do, so just bail. 206 */ 207 mtx_unlock_spin(&ts->ts_lock); 208 return; 209 } 210 211 thread_lock_flags(td, MTX_DUPOK); 212 mtx_unlock_spin(&ts->ts_lock); 213 MPASS(td->td_proc != NULL); 214 MPASS(td->td_proc->p_magic == P_MAGIC); 215 216 /* 217 * If the thread is asleep, then we are probably about 218 * to deadlock. To make debugging this easier, show 219 * backtrace of misbehaving thread and panic to not 220 * leave the kernel deadlocked. 221 */ 222 if (TD_IS_SLEEPING(td)) { 223 printf( 224 "Sleeping thread (tid %d, pid %d) owns a non-sleepable lock\n", 225 td->td_tid, td->td_proc->p_pid); 226 kdb_backtrace_thread(td); 227 panic("sleeping thread"); 228 } 229 230 /* 231 * If this thread already has higher priority than the 232 * thread that is being blocked, we are finished. 233 */ 234 if (td->td_priority <= pri) { 235 thread_unlock(td); 236 return; 237 } 238 239 /* 240 * Bump this thread's priority. 241 */ 242 sched_lend_prio(td, pri); 243 244 /* 245 * If lock holder is actually running or on the run queue 246 * then we are done. 247 */ 248 if (TD_IS_RUNNING(td) || TD_ON_RUNQ(td)) { 249 MPASS(td->td_blocked == NULL); 250 thread_unlock(td); 251 return; 252 } 253 254#ifndef SMP 255 /* 256 * For UP, we check to see if td is curthread (this shouldn't 257 * ever happen however as it would mean we are in a deadlock.) 258 */ 259 KASSERT(td != curthread, ("Deadlock detected")); 260#endif 261 262 /* 263 * If we aren't blocked on a lock, we should be. 264 */ 265 KASSERT(TD_ON_LOCK(td), ( 266 "thread %d(%s):%d holds %s but isn't blocked on a lock\n", 267 td->td_tid, td->td_name, td->td_state, 268 ts->ts_lockobj->lo_name)); 269 270 /* 271 * Pick up the lock that td is blocked on. 272 */ 273 ts = td->td_blocked; 274 MPASS(ts != NULL); 275 THREAD_LOCKPTR_ASSERT(td, &ts->ts_lock); 276 /* Resort td on the list if needed. */ 277 if (!turnstile_adjust_thread(ts, td)) { 278 mtx_unlock_spin(&ts->ts_lock); 279 return; 280 } 281 /* The thread lock is released as ts lock above. */ 282 } 283} 284 285/* 286 * Adjust the thread's position on a turnstile after its priority has been 287 * changed. 288 */ 289static int 290turnstile_adjust_thread(struct turnstile *ts, struct thread *td) 291{ 292 struct thread *td1, *td2; 293 int queue; 294 295 THREAD_LOCK_ASSERT(td, MA_OWNED); 296 MPASS(TD_ON_LOCK(td)); 297 298 /* 299 * This thread may not be blocked on this turnstile anymore 300 * but instead might already be woken up on another CPU 301 * that is waiting on the thread lock in turnstile_unpend() to 302 * finish waking this thread up. We can detect this case 303 * by checking to see if this thread has been given a 304 * turnstile by either turnstile_signal() or 305 * turnstile_broadcast(). In this case, treat the thread as 306 * if it was already running. 307 */ 308 if (td->td_turnstile != NULL) 309 return (0); 310 311 /* 312 * Check if the thread needs to be moved on the blocked chain. 313 * It needs to be moved if either its priority is lower than 314 * the previous thread or higher than the next thread. 315 */ 316 THREAD_LOCKPTR_ASSERT(td, &ts->ts_lock); 317 td1 = TAILQ_PREV(td, threadqueue, td_lockq); 318 td2 = TAILQ_NEXT(td, td_lockq); 319 if ((td1 != NULL && td->td_priority < td1->td_priority) || 320 (td2 != NULL && td->td_priority > td2->td_priority)) { 321 322 /* 323 * Remove thread from blocked chain and determine where 324 * it should be moved to. 325 */ 326 queue = td->td_tsqueue; 327 MPASS(queue == TS_EXCLUSIVE_QUEUE || queue == TS_SHARED_QUEUE); 328 mtx_lock_spin(&td_contested_lock); 329 TAILQ_REMOVE(&ts->ts_blocked[queue], td, td_lockq); 330 TAILQ_FOREACH(td1, &ts->ts_blocked[queue], td_lockq) { 331 MPASS(td1->td_proc->p_magic == P_MAGIC); 332 if (td1->td_priority > td->td_priority) 333 break; 334 } 335 336 if (td1 == NULL) 337 TAILQ_INSERT_TAIL(&ts->ts_blocked[queue], td, td_lockq); 338 else 339 TAILQ_INSERT_BEFORE(td1, td, td_lockq); 340 mtx_unlock_spin(&td_contested_lock); 341 if (td1 == NULL) 342 CTR3(KTR_LOCK, 343 "turnstile_adjust_thread: td %d put at tail on [%p] %s", 344 td->td_tid, ts->ts_lockobj, ts->ts_lockobj->lo_name); 345 else 346 CTR4(KTR_LOCK, 347 "turnstile_adjust_thread: td %d moved before %d on [%p] %s", 348 td->td_tid, td1->td_tid, ts->ts_lockobj, 349 ts->ts_lockobj->lo_name); 350 } 351 return (1); 352} 353 354/* 355 * Early initialization of turnstiles. This is not done via a SYSINIT() 356 * since this needs to be initialized very early when mutexes are first 357 * initialized. 358 */ 359void 360init_turnstiles(void) 361{ 362 int i; 363 364 for (i = 0; i < TC_TABLESIZE; i++) { 365 LIST_INIT(&turnstile_chains[i].tc_turnstiles); 366 mtx_init(&turnstile_chains[i].tc_lock, "turnstile chain", 367 NULL, MTX_SPIN); 368 } 369 mtx_init(&td_contested_lock, "td_contested", NULL, MTX_SPIN); 370 LIST_INIT(&thread0.td_contested); 371 thread0.td_turnstile = NULL; 372} 373 374#ifdef TURNSTILE_PROFILING 375static void 376init_turnstile_profiling(void *arg) 377{ 378 struct sysctl_oid *chain_oid; 379 char chain_name[10]; 380 int i; 381 382 for (i = 0; i < TC_TABLESIZE; i++) { 383 snprintf(chain_name, sizeof(chain_name), "%d", i); 384 chain_oid = SYSCTL_ADD_NODE(NULL, 385 SYSCTL_STATIC_CHILDREN(_debug_turnstile_chains), OID_AUTO, 386 chain_name, CTLFLAG_RD, NULL, "turnstile chain stats"); 387 SYSCTL_ADD_UINT(NULL, SYSCTL_CHILDREN(chain_oid), OID_AUTO, 388 "depth", CTLFLAG_RD, &turnstile_chains[i].tc_depth, 0, 389 NULL); 390 SYSCTL_ADD_UINT(NULL, SYSCTL_CHILDREN(chain_oid), OID_AUTO, 391 "max_depth", CTLFLAG_RD, &turnstile_chains[i].tc_max_depth, 392 0, NULL); 393 } 394} 395SYSINIT(turnstile_profiling, SI_SUB_LOCK, SI_ORDER_ANY, 396 init_turnstile_profiling, NULL); 397#endif 398 399static void 400init_turnstile0(void *dummy) 401{ 402 403 turnstile_zone = uma_zcreate("TURNSTILE", sizeof(struct turnstile), 404 NULL, 405#ifdef INVARIANTS 406 turnstile_dtor, 407#else 408 NULL, 409#endif 410 turnstile_init, turnstile_fini, UMA_ALIGN_CACHE, UMA_ZONE_NOFREE); 411 thread0.td_turnstile = turnstile_alloc(); 412} 413SYSINIT(turnstile0, SI_SUB_LOCK, SI_ORDER_ANY, init_turnstile0, NULL); 414 415/* 416 * Update a thread on the turnstile list after it's priority has been changed. 417 * The old priority is passed in as an argument. 418 */ 419void 420turnstile_adjust(struct thread *td, u_char oldpri) 421{ 422 struct turnstile *ts; 423 424 MPASS(TD_ON_LOCK(td)); 425 426 /* 427 * Pick up the lock that td is blocked on. 428 */ 429 ts = td->td_blocked; 430 MPASS(ts != NULL); 431 THREAD_LOCKPTR_ASSERT(td, &ts->ts_lock); 432 mtx_assert(&ts->ts_lock, MA_OWNED); 433 434 /* Resort the turnstile on the list. */ 435 if (!turnstile_adjust_thread(ts, td)) 436 return; 437 /* 438 * If our priority was lowered and we are at the head of the 439 * turnstile, then propagate our new priority up the chain. 440 * Note that we currently don't try to revoke lent priorities 441 * when our priority goes up. 442 */ 443 MPASS(td->td_tsqueue == TS_EXCLUSIVE_QUEUE || 444 td->td_tsqueue == TS_SHARED_QUEUE); 445 if (td == TAILQ_FIRST(&ts->ts_blocked[td->td_tsqueue]) && 446 td->td_priority < oldpri) { 447 propagate_priority(td); 448 } 449} 450 451/* 452 * Set the owner of the lock this turnstile is attached to. 453 */ 454static void 455turnstile_setowner(struct turnstile *ts, struct thread *owner) 456{ 457 458 mtx_assert(&td_contested_lock, MA_OWNED); 459 MPASS(ts->ts_owner == NULL); 460 461 /* A shared lock might not have an owner. */ 462 if (owner == NULL) 463 return; 464 465 MPASS(owner->td_proc->p_magic == P_MAGIC); 466 ts->ts_owner = owner; 467 LIST_INSERT_HEAD(&owner->td_contested, ts, ts_link); 468} 469 470#ifdef INVARIANTS 471/* 472 * UMA zone item deallocator. 473 */ 474static void 475turnstile_dtor(void *mem, int size, void *arg) 476{ 477 struct turnstile *ts; 478 479 ts = mem; 480 MPASS(TAILQ_EMPTY(&ts->ts_blocked[TS_EXCLUSIVE_QUEUE])); 481 MPASS(TAILQ_EMPTY(&ts->ts_blocked[TS_SHARED_QUEUE])); 482 MPASS(TAILQ_EMPTY(&ts->ts_pending)); 483} 484#endif 485 486/* 487 * UMA zone item initializer. 488 */ 489static int 490turnstile_init(void *mem, int size, int flags) 491{ 492 struct turnstile *ts; 493 494 bzero(mem, size); 495 ts = mem; 496 TAILQ_INIT(&ts->ts_blocked[TS_EXCLUSIVE_QUEUE]); 497 TAILQ_INIT(&ts->ts_blocked[TS_SHARED_QUEUE]); 498 TAILQ_INIT(&ts->ts_pending); 499 LIST_INIT(&ts->ts_free); 500 mtx_init(&ts->ts_lock, "turnstile lock", NULL, MTX_SPIN | MTX_RECURSE); 501 return (0); 502} 503 504static void 505turnstile_fini(void *mem, int size) 506{ 507 struct turnstile *ts; 508 509 ts = mem; 510 mtx_destroy(&ts->ts_lock); 511} 512 513/* 514 * Get a turnstile for a new thread. 515 */ 516struct turnstile * 517turnstile_alloc(void) 518{ 519 520 return (uma_zalloc(turnstile_zone, M_WAITOK)); 521} 522 523/* 524 * Free a turnstile when a thread is destroyed. 525 */ 526void 527turnstile_free(struct turnstile *ts) 528{ 529 530 uma_zfree(turnstile_zone, ts); 531} 532 533/* 534 * Lock the turnstile chain associated with the specified lock. 535 */ 536void 537turnstile_chain_lock(struct lock_object *lock) 538{ 539 struct turnstile_chain *tc; 540 541 tc = TC_LOOKUP(lock); 542 mtx_lock_spin(&tc->tc_lock); 543} 544 545struct turnstile * 546turnstile_trywait(struct lock_object *lock) 547{ 548 struct turnstile_chain *tc; 549 struct turnstile *ts; 550 551 tc = TC_LOOKUP(lock); 552 mtx_lock_spin(&tc->tc_lock); 553 LIST_FOREACH(ts, &tc->tc_turnstiles, ts_hash) 554 if (ts->ts_lockobj == lock) { 555 mtx_lock_spin(&ts->ts_lock); 556 return (ts); 557 } 558 559 ts = curthread->td_turnstile; 560 MPASS(ts != NULL); 561 mtx_lock_spin(&ts->ts_lock); 562 KASSERT(ts->ts_lockobj == NULL, ("stale ts_lockobj pointer")); 563 ts->ts_lockobj = lock; 564 565 return (ts); 566} 567 568void 569turnstile_cancel(struct turnstile *ts) 570{ 571 struct turnstile_chain *tc; 572 struct lock_object *lock; 573 574 mtx_assert(&ts->ts_lock, MA_OWNED); 575 576 mtx_unlock_spin(&ts->ts_lock); 577 lock = ts->ts_lockobj; 578 if (ts == curthread->td_turnstile) 579 ts->ts_lockobj = NULL; 580 tc = TC_LOOKUP(lock); 581 mtx_unlock_spin(&tc->tc_lock); 582} 583 584/* 585 * Look up the turnstile for a lock in the hash table locking the associated 586 * turnstile chain along the way. If no turnstile is found in the hash 587 * table, NULL is returned. 588 */ 589struct turnstile * 590turnstile_lookup(struct lock_object *lock) 591{ 592 struct turnstile_chain *tc; 593 struct turnstile *ts; 594 595 tc = TC_LOOKUP(lock); 596 mtx_assert(&tc->tc_lock, MA_OWNED); 597 LIST_FOREACH(ts, &tc->tc_turnstiles, ts_hash) 598 if (ts->ts_lockobj == lock) { 599 mtx_lock_spin(&ts->ts_lock); 600 return (ts); 601 } 602 return (NULL); 603} 604 605/* 606 * Unlock the turnstile chain associated with a given lock. 607 */ 608void 609turnstile_chain_unlock(struct lock_object *lock) 610{ 611 struct turnstile_chain *tc; 612 613 tc = TC_LOOKUP(lock); 614 mtx_unlock_spin(&tc->tc_lock); 615} 616 617/* 618 * Return a pointer to the thread waiting on this turnstile with the 619 * most important priority or NULL if the turnstile has no waiters. 620 */ 621static struct thread * 622turnstile_first_waiter(struct turnstile *ts) 623{ 624 struct thread *std, *xtd; 625 626 std = TAILQ_FIRST(&ts->ts_blocked[TS_SHARED_QUEUE]); 627 xtd = TAILQ_FIRST(&ts->ts_blocked[TS_EXCLUSIVE_QUEUE]); 628 if (xtd == NULL || (std != NULL && std->td_priority < xtd->td_priority)) 629 return (std); 630 return (xtd); 631} 632 633/* 634 * Take ownership of a turnstile and adjust the priority of the new 635 * owner appropriately. 636 */ 637void 638turnstile_claim(struct turnstile *ts) 639{ 640 struct thread *td, *owner; 641 struct turnstile_chain *tc; 642 643 mtx_assert(&ts->ts_lock, MA_OWNED); 644 MPASS(ts != curthread->td_turnstile); 645 646 owner = curthread; 647 mtx_lock_spin(&td_contested_lock); 648 turnstile_setowner(ts, owner); 649 mtx_unlock_spin(&td_contested_lock); 650 651 td = turnstile_first_waiter(ts); 652 MPASS(td != NULL); 653 MPASS(td->td_proc->p_magic == P_MAGIC); 654 THREAD_LOCKPTR_ASSERT(td, &ts->ts_lock); 655 656 /* 657 * Update the priority of the new owner if needed. 658 */ 659 thread_lock(owner); 660 if (td->td_priority < owner->td_priority) 661 sched_lend_prio(owner, td->td_priority); 662 thread_unlock(owner); 663 tc = TC_LOOKUP(ts->ts_lockobj); 664 mtx_unlock_spin(&ts->ts_lock); 665 mtx_unlock_spin(&tc->tc_lock); 666} 667 668/* 669 * Block the current thread on the turnstile assicated with 'lock'. This 670 * function will context switch and not return until this thread has been 671 * woken back up. This function must be called with the appropriate 672 * turnstile chain locked and will return with it unlocked. 673 */ 674void 675turnstile_wait(struct turnstile *ts, struct thread *owner, int queue) 676{ 677 struct turnstile_chain *tc; 678 struct thread *td, *td1; 679 struct lock_object *lock; 680 681 td = curthread; 682 mtx_assert(&ts->ts_lock, MA_OWNED); 683 if (owner) 684 MPASS(owner->td_proc->p_magic == P_MAGIC); 685 MPASS(queue == TS_SHARED_QUEUE || queue == TS_EXCLUSIVE_QUEUE); 686 687 /* 688 * If the lock does not already have a turnstile, use this thread's 689 * turnstile. Otherwise insert the current thread into the 690 * turnstile already in use by this lock. 691 */ 692 tc = TC_LOOKUP(ts->ts_lockobj); 693 mtx_assert(&tc->tc_lock, MA_OWNED); 694 if (ts == td->td_turnstile) { 695#ifdef TURNSTILE_PROFILING 696 tc->tc_depth++; 697 if (tc->tc_depth > tc->tc_max_depth) { 698 tc->tc_max_depth = tc->tc_depth; 699 if (tc->tc_max_depth > turnstile_max_depth) 700 turnstile_max_depth = tc->tc_max_depth; 701 } 702#endif 703 LIST_INSERT_HEAD(&tc->tc_turnstiles, ts, ts_hash); 704 KASSERT(TAILQ_EMPTY(&ts->ts_pending), 705 ("thread's turnstile has pending threads")); 706 KASSERT(TAILQ_EMPTY(&ts->ts_blocked[TS_EXCLUSIVE_QUEUE]), 707 ("thread's turnstile has exclusive waiters")); 708 KASSERT(TAILQ_EMPTY(&ts->ts_blocked[TS_SHARED_QUEUE]), 709 ("thread's turnstile has shared waiters")); 710 KASSERT(LIST_EMPTY(&ts->ts_free), 711 ("thread's turnstile has a non-empty free list")); 712 MPASS(ts->ts_lockobj != NULL); 713 mtx_lock_spin(&td_contested_lock); 714 TAILQ_INSERT_TAIL(&ts->ts_blocked[queue], td, td_lockq); 715 turnstile_setowner(ts, owner); 716 mtx_unlock_spin(&td_contested_lock); 717 } else { 718 TAILQ_FOREACH(td1, &ts->ts_blocked[queue], td_lockq) 719 if (td1->td_priority > td->td_priority) 720 break; 721 mtx_lock_spin(&td_contested_lock); 722 if (td1 != NULL) 723 TAILQ_INSERT_BEFORE(td1, td, td_lockq); 724 else 725 TAILQ_INSERT_TAIL(&ts->ts_blocked[queue], td, td_lockq); 726 MPASS(owner == ts->ts_owner); 727 mtx_unlock_spin(&td_contested_lock); 728 MPASS(td->td_turnstile != NULL); 729 LIST_INSERT_HEAD(&ts->ts_free, td->td_turnstile, ts_hash); 730 } 731 thread_lock(td); 732 thread_lock_set(td, &ts->ts_lock); 733 td->td_turnstile = NULL; 734 735 /* Save who we are blocked on and switch. */ 736 lock = ts->ts_lockobj; 737 td->td_tsqueue = queue; 738 td->td_blocked = ts; 739 td->td_lockname = lock->lo_name; 740 td->td_blktick = ticks; 741 TD_SET_LOCK(td); 742 mtx_unlock_spin(&tc->tc_lock); 743 propagate_priority(td); 744 745 if (LOCK_LOG_TEST(lock, 0)) 746 CTR4(KTR_LOCK, "%s: td %d blocked on [%p] %s", __func__, 747 td->td_tid, lock, lock->lo_name); 748 749 SDT_PROBE0(sched, , , sleep); 750 751 THREAD_LOCKPTR_ASSERT(td, &ts->ts_lock); 752 mi_switch(SW_VOL | SWT_TURNSTILE, NULL); 753 754 if (LOCK_LOG_TEST(lock, 0)) 755 CTR4(KTR_LOCK, "%s: td %d free from blocked on [%p] %s", 756 __func__, td->td_tid, lock, lock->lo_name); 757 thread_unlock(td); 758} 759 760/* 761 * Pick the highest priority thread on this turnstile and put it on the 762 * pending list. This must be called with the turnstile chain locked. 763 */ 764int 765turnstile_signal(struct turnstile *ts, int queue) 766{ 767 struct turnstile_chain *tc; 768 struct thread *td; 769 int empty; 770 771 MPASS(ts != NULL); 772 mtx_assert(&ts->ts_lock, MA_OWNED); 773 MPASS(curthread->td_proc->p_magic == P_MAGIC); 774 MPASS(ts->ts_owner == curthread || ts->ts_owner == NULL); 775 MPASS(queue == TS_SHARED_QUEUE || queue == TS_EXCLUSIVE_QUEUE); 776 777 /* 778 * Pick the highest priority thread blocked on this lock and 779 * move it to the pending list. 780 */ 781 td = TAILQ_FIRST(&ts->ts_blocked[queue]); 782 MPASS(td->td_proc->p_magic == P_MAGIC); 783 mtx_lock_spin(&td_contested_lock); 784 TAILQ_REMOVE(&ts->ts_blocked[queue], td, td_lockq); 785 mtx_unlock_spin(&td_contested_lock); 786 TAILQ_INSERT_TAIL(&ts->ts_pending, td, td_lockq); 787 788 /* 789 * If the turnstile is now empty, remove it from its chain and 790 * give it to the about-to-be-woken thread. Otherwise take a 791 * turnstile from the free list and give it to the thread. 792 */ 793 empty = TAILQ_EMPTY(&ts->ts_blocked[TS_EXCLUSIVE_QUEUE]) && 794 TAILQ_EMPTY(&ts->ts_blocked[TS_SHARED_QUEUE]); 795 if (empty) { 796 tc = TC_LOOKUP(ts->ts_lockobj); 797 mtx_assert(&tc->tc_lock, MA_OWNED); 798 MPASS(LIST_EMPTY(&ts->ts_free)); 799#ifdef TURNSTILE_PROFILING 800 tc->tc_depth--; 801#endif 802 } else 803 ts = LIST_FIRST(&ts->ts_free); 804 MPASS(ts != NULL); 805 LIST_REMOVE(ts, ts_hash); 806 td->td_turnstile = ts; 807 808 return (empty); 809} 810 811/* 812 * Put all blocked threads on the pending list. This must be called with 813 * the turnstile chain locked. 814 */ 815void 816turnstile_broadcast(struct turnstile *ts, int queue) 817{ 818 struct turnstile_chain *tc; 819 struct turnstile *ts1; 820 struct thread *td; 821 822 MPASS(ts != NULL); 823 mtx_assert(&ts->ts_lock, MA_OWNED); 824 MPASS(curthread->td_proc->p_magic == P_MAGIC); 825 MPASS(ts->ts_owner == curthread || ts->ts_owner == NULL); 826 /* 827 * We must have the chain locked so that we can remove the empty 828 * turnstile from the hash queue. 829 */ 830 tc = TC_LOOKUP(ts->ts_lockobj); 831 mtx_assert(&tc->tc_lock, MA_OWNED); 832 MPASS(queue == TS_SHARED_QUEUE || queue == TS_EXCLUSIVE_QUEUE); 833 834 /* 835 * Transfer the blocked list to the pending list. 836 */ 837 mtx_lock_spin(&td_contested_lock); 838 TAILQ_CONCAT(&ts->ts_pending, &ts->ts_blocked[queue], td_lockq); 839 mtx_unlock_spin(&td_contested_lock); 840 841 /* 842 * Give a turnstile to each thread. The last thread gets 843 * this turnstile if the turnstile is empty. 844 */ 845 TAILQ_FOREACH(td, &ts->ts_pending, td_lockq) { 846 if (LIST_EMPTY(&ts->ts_free)) { 847 MPASS(TAILQ_NEXT(td, td_lockq) == NULL); 848 ts1 = ts; 849#ifdef TURNSTILE_PROFILING 850 tc->tc_depth--; 851#endif 852 } else 853 ts1 = LIST_FIRST(&ts->ts_free); 854 MPASS(ts1 != NULL); 855 LIST_REMOVE(ts1, ts_hash); 856 td->td_turnstile = ts1; 857 } 858} 859 860/* 861 * Wakeup all threads on the pending list and adjust the priority of the 862 * current thread appropriately. This must be called with the turnstile 863 * chain locked. 864 */ 865void 866turnstile_unpend(struct turnstile *ts, int owner_type) 867{ 868 TAILQ_HEAD( ,thread) pending_threads; 869 struct turnstile *nts; 870 struct thread *td; 871 u_char cp, pri; 872 873 MPASS(ts != NULL); 874 mtx_assert(&ts->ts_lock, MA_OWNED); 875 MPASS(ts->ts_owner == curthread || ts->ts_owner == NULL); 876 MPASS(!TAILQ_EMPTY(&ts->ts_pending)); 877 878 /* 879 * Move the list of pending threads out of the turnstile and 880 * into a local variable. 881 */ 882 TAILQ_INIT(&pending_threads); 883 TAILQ_CONCAT(&pending_threads, &ts->ts_pending, td_lockq); 884#ifdef INVARIANTS 885 if (TAILQ_EMPTY(&ts->ts_blocked[TS_EXCLUSIVE_QUEUE]) && 886 TAILQ_EMPTY(&ts->ts_blocked[TS_SHARED_QUEUE])) 887 ts->ts_lockobj = NULL; 888#endif 889 /* 890 * Adjust the priority of curthread based on other contested 891 * locks it owns. Don't lower the priority below the base 892 * priority however. 893 */ 894 td = curthread; 895 pri = PRI_MAX; 896 thread_lock(td); 897 mtx_lock_spin(&td_contested_lock); 898 /* 899 * Remove the turnstile from this thread's list of contested locks 900 * since this thread doesn't own it anymore. New threads will 901 * not be blocking on the turnstile until it is claimed by a new 902 * owner. There might not be a current owner if this is a shared 903 * lock. 904 */ 905 if (ts->ts_owner != NULL) { 906 ts->ts_owner = NULL; 907 LIST_REMOVE(ts, ts_link); 908 } 909 LIST_FOREACH(nts, &td->td_contested, ts_link) { 910 cp = turnstile_first_waiter(nts)->td_priority; 911 if (cp < pri) 912 pri = cp; 913 } 914 mtx_unlock_spin(&td_contested_lock); 915 sched_unlend_prio(td, pri); 916 thread_unlock(td); 917 /* 918 * Wake up all the pending threads. If a thread is not blocked 919 * on a lock, then it is currently executing on another CPU in 920 * turnstile_wait() or sitting on a run queue waiting to resume 921 * in turnstile_wait(). Set a flag to force it to try to acquire 922 * the lock again instead of blocking. 923 */ 924 while (!TAILQ_EMPTY(&pending_threads)) { 925 td = TAILQ_FIRST(&pending_threads); 926 TAILQ_REMOVE(&pending_threads, td, td_lockq); 927 SDT_PROBE2(sched, , , wakeup, td, td->td_proc); 928 thread_lock(td); 929 THREAD_LOCKPTR_ASSERT(td, &ts->ts_lock); 930 MPASS(td->td_proc->p_magic == P_MAGIC); 931 MPASS(TD_ON_LOCK(td)); 932 TD_CLR_LOCK(td); 933 MPASS(TD_CAN_RUN(td)); 934 td->td_blocked = NULL; 935 td->td_lockname = NULL; 936 td->td_blktick = 0; 937#ifdef INVARIANTS 938 td->td_tsqueue = 0xff; 939#endif 940 sched_add(td, SRQ_BORING); 941 thread_unlock(td); 942 } 943 mtx_unlock_spin(&ts->ts_lock); 944} 945 946/* 947 * Give up ownership of a turnstile. This must be called with the 948 * turnstile chain locked. 949 */ 950void 951turnstile_disown(struct turnstile *ts) 952{ 953 struct thread *td; 954 u_char cp, pri; 955 956 MPASS(ts != NULL); 957 mtx_assert(&ts->ts_lock, MA_OWNED); 958 MPASS(ts->ts_owner == curthread); 959 MPASS(TAILQ_EMPTY(&ts->ts_pending)); 960 MPASS(!TAILQ_EMPTY(&ts->ts_blocked[TS_EXCLUSIVE_QUEUE]) || 961 !TAILQ_EMPTY(&ts->ts_blocked[TS_SHARED_QUEUE])); 962 963 /* 964 * Remove the turnstile from this thread's list of contested locks 965 * since this thread doesn't own it anymore. New threads will 966 * not be blocking on the turnstile until it is claimed by a new 967 * owner. 968 */ 969 mtx_lock_spin(&td_contested_lock); 970 ts->ts_owner = NULL; 971 LIST_REMOVE(ts, ts_link); 972 mtx_unlock_spin(&td_contested_lock); 973 974 /* 975 * Adjust the priority of curthread based on other contested 976 * locks it owns. Don't lower the priority below the base 977 * priority however. 978 */ 979 td = curthread; 980 pri = PRI_MAX; 981 thread_lock(td); 982 mtx_unlock_spin(&ts->ts_lock); 983 mtx_lock_spin(&td_contested_lock); 984 LIST_FOREACH(ts, &td->td_contested, ts_link) { 985 cp = turnstile_first_waiter(ts)->td_priority; 986 if (cp < pri) 987 pri = cp; 988 } 989 mtx_unlock_spin(&td_contested_lock); 990 sched_unlend_prio(td, pri); 991 thread_unlock(td); 992} 993 994/* 995 * Return the first thread in a turnstile. 996 */ 997struct thread * 998turnstile_head(struct turnstile *ts, int queue) 999{ 1000#ifdef INVARIANTS 1001 1002 MPASS(ts != NULL); 1003 MPASS(queue == TS_SHARED_QUEUE || queue == TS_EXCLUSIVE_QUEUE); 1004 mtx_assert(&ts->ts_lock, MA_OWNED); 1005#endif 1006 return (TAILQ_FIRST(&ts->ts_blocked[queue])); 1007} 1008 1009/* 1010 * Returns true if a sub-queue of a turnstile is empty. 1011 */ 1012int 1013turnstile_empty(struct turnstile *ts, int queue) 1014{ 1015#ifdef INVARIANTS 1016 1017 MPASS(ts != NULL); 1018 MPASS(queue == TS_SHARED_QUEUE || queue == TS_EXCLUSIVE_QUEUE); 1019 mtx_assert(&ts->ts_lock, MA_OWNED); 1020#endif 1021 return (TAILQ_EMPTY(&ts->ts_blocked[queue])); 1022} 1023 1024#ifdef DDB 1025static void 1026print_thread(struct thread *td, const char *prefix) 1027{ 1028 1029 db_printf("%s%p (tid %d, pid %d, \"%s\")\n", prefix, td, td->td_tid, 1030 td->td_proc->p_pid, td->td_name); 1031} 1032 1033static void 1034print_queue(struct threadqueue *queue, const char *header, const char *prefix) 1035{ 1036 struct thread *td; 1037 1038 db_printf("%s:\n", header); 1039 if (TAILQ_EMPTY(queue)) { 1040 db_printf("%sempty\n", prefix); 1041 return; 1042 } 1043 TAILQ_FOREACH(td, queue, td_lockq) { 1044 print_thread(td, prefix); 1045 } 1046} 1047 1048DB_SHOW_COMMAND(turnstile, db_show_turnstile) 1049{ 1050 struct turnstile_chain *tc; 1051 struct turnstile *ts; 1052 struct lock_object *lock; 1053 int i; 1054 1055 if (!have_addr) 1056 return; 1057 1058 /* 1059 * First, see if there is an active turnstile for the lock indicated 1060 * by the address. 1061 */ 1062 lock = (struct lock_object *)addr; 1063 tc = TC_LOOKUP(lock); 1064 LIST_FOREACH(ts, &tc->tc_turnstiles, ts_hash) 1065 if (ts->ts_lockobj == lock) 1066 goto found; 1067 1068 /* 1069 * Second, see if there is an active turnstile at the address 1070 * indicated. 1071 */ 1072 for (i = 0; i < TC_TABLESIZE; i++) 1073 LIST_FOREACH(ts, &turnstile_chains[i].tc_turnstiles, ts_hash) { 1074 if (ts == (struct turnstile *)addr) 1075 goto found; 1076 } 1077 1078 db_printf("Unable to locate a turnstile via %p\n", (void *)addr); 1079 return; 1080found: 1081 lock = ts->ts_lockobj; 1082 db_printf("Lock: %p - (%s) %s\n", lock, LOCK_CLASS(lock)->lc_name, 1083 lock->lo_name); 1084 if (ts->ts_owner) 1085 print_thread(ts->ts_owner, "Lock Owner: "); 1086 else 1087 db_printf("Lock Owner: none\n"); 1088 print_queue(&ts->ts_blocked[TS_SHARED_QUEUE], "Shared Waiters", "\t"); 1089 print_queue(&ts->ts_blocked[TS_EXCLUSIVE_QUEUE], "Exclusive Waiters", 1090 "\t"); 1091 print_queue(&ts->ts_pending, "Pending Threads", "\t"); 1092 1093} 1094 1095/* 1096 * Show all the threads a particular thread is waiting on based on 1097 * non-sleepable and non-spin locks. 1098 */ 1099static void 1100print_lockchain(struct thread *td, const char *prefix) 1101{ 1102 struct lock_object *lock; 1103 struct lock_class *class; 1104 struct turnstile *ts; 1105 1106 /* 1107 * Follow the chain. We keep walking as long as the thread is 1108 * blocked on a turnstile that has an owner. 1109 */ 1110 while (!db_pager_quit) { 1111 db_printf("%sthread %d (pid %d, %s) ", prefix, td->td_tid, 1112 td->td_proc->p_pid, td->td_name); 1113 switch (td->td_state) { 1114 case TDS_INACTIVE: 1115 db_printf("is inactive\n"); 1116 return; 1117 case TDS_CAN_RUN: 1118 db_printf("can run\n"); 1119 return; 1120 case TDS_RUNQ: 1121 db_printf("is on a run queue\n"); 1122 return; 1123 case TDS_RUNNING: 1124 db_printf("running on CPU %d\n", td->td_oncpu); 1125 return; 1126 case TDS_INHIBITED: 1127 if (TD_ON_LOCK(td)) { 1128 ts = td->td_blocked; 1129 lock = ts->ts_lockobj; 1130 class = LOCK_CLASS(lock); 1131 db_printf("blocked on lock %p (%s) \"%s\"\n", 1132 lock, class->lc_name, lock->lo_name); 1133 if (ts->ts_owner == NULL) 1134 return; 1135 td = ts->ts_owner; 1136 break; 1137 } 1138 db_printf("inhibited\n"); 1139 return; 1140 default: 1141 db_printf("??? (%#x)\n", td->td_state); 1142 return; 1143 } 1144 } 1145} 1146 1147DB_SHOW_COMMAND(lockchain, db_show_lockchain) 1148{ 1149 struct thread *td; 1150 1151 /* Figure out which thread to start with. */ 1152 if (have_addr) 1153 td = db_lookup_thread(addr, TRUE); 1154 else 1155 td = kdb_thread; 1156 1157 print_lockchain(td, ""); 1158} 1159 1160DB_SHOW_ALL_COMMAND(chains, db_show_allchains) 1161{ 1162 struct thread *td; 1163 struct proc *p; 1164 int i; 1165 1166 i = 1; 1167 FOREACH_PROC_IN_SYSTEM(p) { 1168 FOREACH_THREAD_IN_PROC(p, td) { 1169 if (TD_ON_LOCK(td) && LIST_EMPTY(&td->td_contested)) { 1170 db_printf("chain %d:\n", i++); 1171 print_lockchain(td, " "); 1172 } 1173 if (db_pager_quit) 1174 return; 1175 } 1176 } 1177} 1178DB_SHOW_ALIAS(allchains, db_show_allchains) 1179 1180/* 1181 * Show all the threads a particular thread is waiting on based on 1182 * sleepable locks. 1183 */ 1184static void 1185print_sleepchain(struct thread *td, const char *prefix) 1186{ 1187 struct thread *owner; 1188 1189 /* 1190 * Follow the chain. We keep walking as long as the thread is 1191 * blocked on a sleep lock that has an owner. 1192 */ 1193 while (!db_pager_quit) { 1194 db_printf("%sthread %d (pid %d, %s) ", prefix, td->td_tid, 1195 td->td_proc->p_pid, td->td_name); 1196 switch (td->td_state) { 1197 case TDS_INACTIVE: 1198 db_printf("is inactive\n"); 1199 return; 1200 case TDS_CAN_RUN: 1201 db_printf("can run\n"); 1202 return; 1203 case TDS_RUNQ: 1204 db_printf("is on a run queue\n"); 1205 return; 1206 case TDS_RUNNING: 1207 db_printf("running on CPU %d\n", td->td_oncpu); 1208 return; 1209 case TDS_INHIBITED: 1210 if (TD_ON_SLEEPQ(td)) { 1211 if (lockmgr_chain(td, &owner) || 1212 sx_chain(td, &owner)) { 1213 if (owner == NULL) 1214 return; 1215 td = owner; 1216 break; 1217 } 1218 db_printf("sleeping on %p \"%s\"\n", 1219 td->td_wchan, td->td_wmesg); 1220 return; 1221 } 1222 db_printf("inhibited\n"); 1223 return; 1224 default: 1225 db_printf("??? (%#x)\n", td->td_state); 1226 return; 1227 } 1228 } 1229} 1230 1231DB_SHOW_COMMAND(sleepchain, db_show_sleepchain) 1232{ 1233 struct thread *td; 1234 1235 /* Figure out which thread to start with. */ 1236 if (have_addr) 1237 td = db_lookup_thread(addr, TRUE); 1238 else 1239 td = kdb_thread; 1240 1241 print_sleepchain(td, ""); 1242} 1243 1244static void print_waiters(struct turnstile *ts, int indent); 1245 1246static void 1247print_waiter(struct thread *td, int indent) 1248{ 1249 struct turnstile *ts; 1250 int i; 1251 1252 if (db_pager_quit) 1253 return; 1254 for (i = 0; i < indent; i++) 1255 db_printf(" "); 1256 print_thread(td, "thread "); 1257 LIST_FOREACH(ts, &td->td_contested, ts_link) 1258 print_waiters(ts, indent + 1); 1259} 1260 1261static void 1262print_waiters(struct turnstile *ts, int indent) 1263{ 1264 struct lock_object *lock; 1265 struct lock_class *class; 1266 struct thread *td; 1267 int i; 1268 1269 if (db_pager_quit) 1270 return; 1271 lock = ts->ts_lockobj; 1272 class = LOCK_CLASS(lock); 1273 for (i = 0; i < indent; i++) 1274 db_printf(" "); 1275 db_printf("lock %p (%s) \"%s\"\n", lock, class->lc_name, lock->lo_name); 1276 TAILQ_FOREACH(td, &ts->ts_blocked[TS_EXCLUSIVE_QUEUE], td_lockq) 1277 print_waiter(td, indent + 1); 1278 TAILQ_FOREACH(td, &ts->ts_blocked[TS_SHARED_QUEUE], td_lockq) 1279 print_waiter(td, indent + 1); 1280 TAILQ_FOREACH(td, &ts->ts_pending, td_lockq) 1281 print_waiter(td, indent + 1); 1282} 1283 1284DB_SHOW_COMMAND(locktree, db_show_locktree) 1285{ 1286 struct lock_object *lock; 1287 struct lock_class *class; 1288 struct turnstile_chain *tc; 1289 struct turnstile *ts; 1290 1291 if (!have_addr) 1292 return; 1293 lock = (struct lock_object *)addr; 1294 tc = TC_LOOKUP(lock); 1295 LIST_FOREACH(ts, &tc->tc_turnstiles, ts_hash) 1296 if (ts->ts_lockobj == lock) 1297 break; 1298 if (ts == NULL) { 1299 class = LOCK_CLASS(lock); 1300 db_printf("lock %p (%s) \"%s\"\n", lock, class->lc_name, 1301 lock->lo_name); 1302 } else 1303 print_waiters(ts, 0); 1304} 1305#endif 1306