subr_turnstile.c revision 246923
165557Sjasone/*- 265557Sjasone * Copyright (c) 1998 Berkeley Software Design, Inc. All rights reserved. 365557Sjasone * 465557Sjasone * Redistribution and use in source and binary forms, with or without 565557Sjasone * modification, are permitted provided that the following conditions 665557Sjasone * are met: 765557Sjasone * 1. Redistributions of source code must retain the above copyright 865557Sjasone * notice, this list of conditions and the following disclaimer. 965557Sjasone * 2. Redistributions in binary form must reproduce the above copyright 1065557Sjasone * notice, this list of conditions and the following disclaimer in the 1165557Sjasone * documentation and/or other materials provided with the distribution. 1265557Sjasone * 3. Berkeley Software Design Inc's name may not be used to endorse or 1365557Sjasone * promote products derived from this software without specific prior 1465557Sjasone * written permission. 1565557Sjasone * 1665557Sjasone * THIS SOFTWARE IS PROVIDED BY BERKELEY SOFTWARE DESIGN INC ``AS IS'' AND 1765557Sjasone * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 1865557Sjasone * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 1965557Sjasone * ARE DISCLAIMED. IN NO EVENT SHALL BERKELEY SOFTWARE DESIGN INC BE LIABLE 2065557Sjasone * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 2165557Sjasone * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 2265557Sjasone * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 2365557Sjasone * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 2465557Sjasone * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 2565557Sjasone * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 2665557Sjasone * SUCH DAMAGE. 2765557Sjasone * 2865557Sjasone * from BSDI $Id: mutex_witness.c,v 1.1.2.20 2000/04/27 03:10:27 cp Exp $ 2967352Sjhb * and BSDI $Id: synch_machdep.c,v 2.3.2.39 2000/04/27 03:10:25 cp Exp $ 3065557Sjasone */ 3165557Sjasone 3265557Sjasone/* 33122514Sjhb * Implementation of turnstiles used to hold queue of threads blocked on 34122514Sjhb * non-sleepable locks. Sleepable locks use condition variables to 35122514Sjhb * implement their queues. Turnstiles differ from a sleep queue in that 36122514Sjhb * turnstile queue's are assigned to a lock held by an owning thread. Thus, 37122514Sjhb * when one thread is enqueued onto a turnstile, it can lend its priority 38122514Sjhb * to the owning thread. 39122514Sjhb * 40122514Sjhb * We wish to avoid bloating locks with an embedded turnstile and we do not 41122514Sjhb * want to use back-pointers in the locks for the same reason. Thus, we 42122514Sjhb * use a similar approach to that of Solaris 7 as described in Solaris 43122514Sjhb * Internals by Jim Mauro and Richard McDougall. Turnstiles are looked up 44122514Sjhb * in a hash table based on the address of the lock. Each entry in the 45122514Sjhb * hash table is a linked-lists of turnstiles and is called a turnstile 46122514Sjhb * chain. Each chain contains a spin mutex that protects all of the 47122514Sjhb * turnstiles in the chain. 48122514Sjhb * 49169666Sjeff * Each time a thread is created, a turnstile is allocated from a UMA zone 50169666Sjeff * and attached to that thread. When a thread blocks on a lock, if it is the 51169666Sjeff * first thread to block, it lends its turnstile to the lock. If the lock 52169666Sjeff * already has a turnstile, then it gives its turnstile to the lock's 53169666Sjeff * turnstile's free list. When a thread is woken up, it takes a turnstile from 54169666Sjeff * the free list if there are any other waiters. If it is the only thread 55169666Sjeff * blocked on the lock, then it reclaims the turnstile associated with the lock 56169666Sjeff * and removes it from the hash table. 5772200Sbmilekic */ 5872200Sbmilekic 59116182Sobrien#include <sys/cdefs.h> 60116182Sobrien__FBSDID("$FreeBSD: head/sys/kern/subr_turnstile.c 246923 2013-02-17 21:37:32Z pjd $"); 61116182Sobrien 62154937Sjhb#include "opt_ddb.h" 63235459Srstone#include "opt_kdtrace.h" 64154937Sjhb#include "opt_turnstile_profiling.h" 65170640Sjeff#include "opt_sched.h" 66154937Sjhb 6765557Sjasone#include <sys/param.h> 6893609Sdes#include <sys/systm.h> 69234280Smarius#include <sys/kdb.h> 7067352Sjhb#include <sys/kernel.h> 7193609Sdes#include <sys/ktr.h> 7276166Smarkm#include <sys/lock.h> 7374912Sjhb#include <sys/mutex.h> 7465557Sjasone#include <sys/proc.h> 75122514Sjhb#include <sys/queue.h> 76131259Sjhb#include <sys/sched.h> 77235459Srstone#include <sys/sdt.h> 78131259Sjhb#include <sys/sysctl.h> 79122514Sjhb#include <sys/turnstile.h> 8065557Sjasone 81169666Sjeff#include <vm/uma.h> 82169666Sjeff 83154937Sjhb#ifdef DDB 84154937Sjhb#include <ddb/ddb.h> 85161337Sjhb#include <sys/lockmgr.h> 86161337Sjhb#include <sys/sx.h> 87154937Sjhb#endif 88154937Sjhb 8965557Sjasone/* 90122514Sjhb * Constants for the hash table of turnstile chains. TC_SHIFT is a magic 91122514Sjhb * number chosen because the sleep queue's use the same value for the 92122514Sjhb * shift. Basically, we ignore the lower 8 bits of the address. 93122514Sjhb * TC_TABLESIZE must be a power of two for TC_MASK to work properly. 9471352Sjasone */ 95122514Sjhb#define TC_TABLESIZE 128 /* Must be power of 2. */ 96122514Sjhb#define TC_MASK (TC_TABLESIZE - 1) 97122514Sjhb#define TC_SHIFT 8 98122514Sjhb#define TC_HASH(lock) (((uintptr_t)(lock) >> TC_SHIFT) & TC_MASK) 99122514Sjhb#define TC_LOOKUP(lock) &turnstile_chains[TC_HASH(lock)] 10071352Sjasone 10171352Sjasone/* 102122514Sjhb * There are three different lists of turnstiles as follows. The list 103122514Sjhb * connected by ts_link entries is a per-thread list of all the turnstiles 104122514Sjhb * attached to locks that we own. This is used to fixup our priority when 105122514Sjhb * a lock is released. The other two lists use the ts_hash entries. The 106126317Sjhb * first of these two is the turnstile chain list that a turnstile is on 107126317Sjhb * when it is attached to a lock. The second list to use ts_hash is the 108126317Sjhb * free list hung off of a turnstile that is attached to a lock. 109122514Sjhb * 110154937Sjhb * Each turnstile contains three lists of threads. The two ts_blocked lists 111154937Sjhb * are linked list of threads blocked on the turnstile's lock. One list is 112154937Sjhb * for exclusive waiters, and the other is for shared waiters. The 113126884Sjhb * ts_pending list is a linked list of threads previously awakened by 114122514Sjhb * turnstile_signal() or turnstile_wait() that are waiting to be put on 115122514Sjhb * the run queue. 116122514Sjhb * 117122514Sjhb * Locking key: 118122514Sjhb * c - turnstile chain lock 119122514Sjhb * q - td_contested lock 12071352Sjasone */ 121122514Sjhbstruct turnstile { 122170295Sjeff struct mtx ts_lock; /* Spin lock for self. */ 123154937Sjhb struct threadqueue ts_blocked[2]; /* (c + q) Blocked threads. */ 124154937Sjhb struct threadqueue ts_pending; /* (c) Pending threads. */ 125122514Sjhb LIST_ENTRY(turnstile) ts_hash; /* (c) Chain and free list. */ 126122514Sjhb LIST_ENTRY(turnstile) ts_link; /* (q) Contested locks. */ 127122514Sjhb LIST_HEAD(, turnstile) ts_free; /* (c) Free turnstiles. */ 128122514Sjhb struct lock_object *ts_lockobj; /* (c) Lock we reference. */ 129122590Sjhb struct thread *ts_owner; /* (c + q) Who owns the lock. */ 13074912Sjhb}; 131122514Sjhb 132122514Sjhbstruct turnstile_chain { 133122514Sjhb LIST_HEAD(, turnstile) tc_turnstiles; /* List of turnstiles. */ 134122514Sjhb struct mtx tc_lock; /* Spin lock for this chain. */ 135131259Sjhb#ifdef TURNSTILE_PROFILING 136131259Sjhb u_int tc_depth; /* Length of tc_queues. */ 137131259Sjhb u_int tc_max_depth; /* Max length of tc_queues. */ 138131259Sjhb#endif 13974912Sjhb}; 14071352Sjasone 141131259Sjhb#ifdef TURNSTILE_PROFILING 142131259Sjhbu_int turnstile_max_depth; 143227309Sedstatic SYSCTL_NODE(_debug, OID_AUTO, turnstile, CTLFLAG_RD, 0, 144227309Sed "turnstile profiling"); 145227309Sedstatic SYSCTL_NODE(_debug_turnstile, OID_AUTO, chains, CTLFLAG_RD, 0, 146131259Sjhb "turnstile chain stats"); 147131259SjhbSYSCTL_UINT(_debug_turnstile, OID_AUTO, max_depth, CTLFLAG_RD, 148234303Sdavide &turnstile_max_depth, 0, "maximum depth achieved of a single chain"); 149131259Sjhb#endif 150122514Sjhbstatic struct mtx td_contested_lock; 151122514Sjhbstatic struct turnstile_chain turnstile_chains[TC_TABLESIZE]; 152169666Sjeffstatic uma_zone_t turnstile_zone; 15393702Sjhb 15493702Sjhb/* 15572200Sbmilekic * Prototypes for non-exported routines. 15672200Sbmilekic */ 157122514Sjhbstatic void init_turnstile0(void *dummy); 158131263Sjhb#ifdef TURNSTILE_PROFILING 159131263Sjhbstatic void init_turnstile_profiling(void *arg); 160131263Sjhb#endif 161139453Sjhbstatic void propagate_priority(struct thread *td); 162139453Sjhbstatic int turnstile_adjust_thread(struct turnstile *ts, 163139453Sjhb struct thread *td); 164154937Sjhbstatic struct thread *turnstile_first_waiter(struct turnstile *ts); 165122514Sjhbstatic void turnstile_setowner(struct turnstile *ts, struct thread *owner); 166169666Sjeff#ifdef INVARIANTS 167169666Sjeffstatic void turnstile_dtor(void *mem, int size, void *arg); 168169666Sjeff#endif 169169666Sjeffstatic int turnstile_init(void *mem, int size, int flags); 170170295Sjeffstatic void turnstile_fini(void *mem, int size); 17167352Sjhb 172235459SrstoneSDT_PROVIDER_DECLARE(sched); 173235459SrstoneSDT_PROBE_DEFINE(sched, , , sleep, sleep); 174235459SrstoneSDT_PROBE_DEFINE2(sched, , , wakeup, wakeup, "struct thread *", 175235459Srstone "struct proc *"); 176235459Srstone 177122514Sjhb/* 178122514Sjhb * Walks the chain of turnstiles and their owners to propagate the priority 179122514Sjhb * of the thread being blocked to all the threads holding locks that have to 180122514Sjhb * release their locks before this thread can run again. 181122514Sjhb */ 18267352Sjhbstatic void 18383366Sjulianpropagate_priority(struct thread *td) 18467352Sjhb{ 185122514Sjhb struct turnstile *ts; 186122514Sjhb int pri; 18767352Sjhb 188170295Sjeff THREAD_LOCK_ASSERT(td, MA_OWNED); 189122514Sjhb pri = td->td_priority; 190122514Sjhb ts = td->td_blocked; 191176078Sjeff THREAD_LOCKPTR_ASSERT(td, &ts->ts_lock); 192170295Sjeff /* 193170295Sjeff * Grab a recursive lock on this turnstile chain so it stays locked 194170295Sjeff * for the whole operation. The caller expects us to return with 195170295Sjeff * the original lock held. We only ever lock down the chain so 196170295Sjeff * the lock order is constant. 197170295Sjeff */ 198170295Sjeff mtx_lock_spin(&ts->ts_lock); 19967352Sjhb for (;;) { 200122514Sjhb td = ts->ts_owner; 20167352Sjhb 20283366Sjulian if (td == NULL) { 20367352Sjhb /* 204154937Sjhb * This might be a read lock with no owner. There's 205154937Sjhb * not much we can do, so just bail. 20667352Sjhb */ 207170295Sjeff mtx_unlock_spin(&ts->ts_lock); 20867352Sjhb return; 20967352Sjhb } 21072200Sbmilekic 211170295Sjeff thread_lock_flags(td, MTX_DUPOK); 212170295Sjeff mtx_unlock_spin(&ts->ts_lock); 21399072Sjulian MPASS(td->td_proc != NULL); 21483366Sjulian MPASS(td->td_proc->p_magic == P_MAGIC); 215122514Sjhb 216122514Sjhb /* 217157275Sjhb * If the thread is asleep, then we are probably about 218246923Spjd * to deadlock. To make debugging this easier, show 219246923Spjd * backtrace of misbehaving thread and panic to not 220246923Spjd * leave the kernel deadlocked. 221122514Sjhb */ 222157275Sjhb if (TD_IS_SLEEPING(td)) { 223157275Sjhb printf( 224157275Sjhb "Sleeping thread (tid %d, pid %d) owns a non-sleepable lock\n", 225157275Sjhb td->td_tid, td->td_proc->p_pid); 226234190Sjhb kdb_backtrace_thread(td); 227157275Sjhb panic("sleeping thread"); 228157275Sjhb } 229122514Sjhb 230122514Sjhb /* 231122514Sjhb * If this thread already has higher priority than the 232122514Sjhb * thread that is being blocked, we are finished. 233122514Sjhb */ 234170295Sjeff if (td->td_priority <= pri) { 235170295Sjeff thread_unlock(td); 23667352Sjhb return; 237170295Sjeff } 23869376Sjhb 23969376Sjhb /* 240139453Sjhb * Bump this thread's priority. 24167352Sjhb */ 242139453Sjhb sched_lend_prio(td, pri); 243139453Sjhb 244139453Sjhb /* 245139453Sjhb * If lock holder is actually running or on the run queue 246139453Sjhb * then we are done. 247139453Sjhb */ 248139453Sjhb if (TD_IS_RUNNING(td) || TD_ON_RUNQ(td)) { 249139453Sjhb MPASS(td->td_blocked == NULL); 250170295Sjeff thread_unlock(td); 25167352Sjhb return; 25267352Sjhb } 25372376Sjake 25473912Sjhb#ifndef SMP 25567352Sjhb /* 25683366Sjulian * For UP, we check to see if td is curthread (this shouldn't 25773912Sjhb * ever happen however as it would mean we are in a deadlock.) 25873912Sjhb */ 25983366Sjulian KASSERT(td != curthread, ("Deadlock detected")); 26073912Sjhb#endif 26173912Sjhb 26273912Sjhb /* 263122514Sjhb * If we aren't blocked on a lock, we should be. 26467352Sjhb */ 265104387Sjhb KASSERT(TD_ON_LOCK(td), ( 266139453Sjhb "thread %d(%s):%d holds %s but isn't blocked on a lock\n", 267173600Sjulian td->td_tid, td->td_name, td->td_state, 268122514Sjhb ts->ts_lockobj->lo_name)); 26967352Sjhb 27067352Sjhb /* 271122514Sjhb * Pick up the lock that td is blocked on. 27267352Sjhb */ 273122514Sjhb ts = td->td_blocked; 274122514Sjhb MPASS(ts != NULL); 275176078Sjeff THREAD_LOCKPTR_ASSERT(td, &ts->ts_lock); 276139453Sjhb /* Resort td on the list if needed. */ 277139453Sjhb if (!turnstile_adjust_thread(ts, td)) { 278170295Sjeff mtx_unlock_spin(&ts->ts_lock); 279122590Sjhb return; 280122590Sjhb } 281170295Sjeff /* The thread lock is released as ts lock above. */ 282139453Sjhb } 283139453Sjhb} 284122590Sjhb 285139453Sjhb/* 286139453Sjhb * Adjust the thread's position on a turnstile after its priority has been 287139453Sjhb * changed. 288139453Sjhb */ 289139453Sjhbstatic int 290139453Sjhbturnstile_adjust_thread(struct turnstile *ts, struct thread *td) 291139453Sjhb{ 292139453Sjhb struct thread *td1, *td2; 293154937Sjhb int queue; 29472200Sbmilekic 295170295Sjeff THREAD_LOCK_ASSERT(td, MA_OWNED); 296139453Sjhb MPASS(TD_ON_LOCK(td)); 29767352Sjhb 298139453Sjhb /* 299139453Sjhb * This thread may not be blocked on this turnstile anymore 300139453Sjhb * but instead might already be woken up on another CPU 301170295Sjeff * that is waiting on the thread lock in turnstile_unpend() to 302139453Sjhb * finish waking this thread up. We can detect this case 303139453Sjhb * by checking to see if this thread has been given a 304139453Sjhb * turnstile by either turnstile_signal() or 305139453Sjhb * turnstile_broadcast(). In this case, treat the thread as 306139453Sjhb * if it was already running. 307139453Sjhb */ 308139453Sjhb if (td->td_turnstile != NULL) 309139453Sjhb return (0); 310139453Sjhb 311139453Sjhb /* 312139453Sjhb * Check if the thread needs to be moved on the blocked chain. 313139453Sjhb * It needs to be moved if either its priority is lower than 314139453Sjhb * the previous thread or higher than the next thread. 315139453Sjhb */ 316176078Sjeff THREAD_LOCKPTR_ASSERT(td, &ts->ts_lock); 317139453Sjhb td1 = TAILQ_PREV(td, threadqueue, td_lockq); 318139453Sjhb td2 = TAILQ_NEXT(td, td_lockq); 319139453Sjhb if ((td1 != NULL && td->td_priority < td1->td_priority) || 320139453Sjhb (td2 != NULL && td->td_priority > td2->td_priority)) { 321139453Sjhb 32267352Sjhb /* 32383366Sjulian * Remove thread from blocked chain and determine where 324139453Sjhb * it should be moved to. 32567352Sjhb */ 326154937Sjhb queue = td->td_tsqueue; 327154937Sjhb MPASS(queue == TS_EXCLUSIVE_QUEUE || queue == TS_SHARED_QUEUE); 328122514Sjhb mtx_lock_spin(&td_contested_lock); 329154937Sjhb TAILQ_REMOVE(&ts->ts_blocked[queue], td, td_lockq); 330154937Sjhb TAILQ_FOREACH(td1, &ts->ts_blocked[queue], td_lockq) { 33183366Sjulian MPASS(td1->td_proc->p_magic == P_MAGIC); 332139453Sjhb if (td1->td_priority > td->td_priority) 33367352Sjhb break; 33467352Sjhb } 33572200Sbmilekic 336139453Sjhb if (td1 == NULL) 337154937Sjhb TAILQ_INSERT_TAIL(&ts->ts_blocked[queue], td, td_lockq); 338139453Sjhb else 339139453Sjhb TAILQ_INSERT_BEFORE(td1, td, td_lockq); 340122514Sjhb mtx_unlock_spin(&td_contested_lock); 341139453Sjhb if (td1 == NULL) 342139453Sjhb CTR3(KTR_LOCK, 343139453Sjhb "turnstile_adjust_thread: td %d put at tail on [%p] %s", 344139453Sjhb td->td_tid, ts->ts_lockobj, ts->ts_lockobj->lo_name); 345139453Sjhb else 346139453Sjhb CTR4(KTR_LOCK, 347139453Sjhb "turnstile_adjust_thread: td %d moved before %d on [%p] %s", 348139453Sjhb td->td_tid, td1->td_tid, ts->ts_lockobj, 349139453Sjhb ts->ts_lockobj->lo_name); 35067352Sjhb } 351139453Sjhb return (1); 35267352Sjhb} 35367352Sjhb 35471352Sjasone/* 355122514Sjhb * Early initialization of turnstiles. This is not done via a SYSINIT() 356122514Sjhb * since this needs to be initialized very early when mutexes are first 357122514Sjhb * initialized. 35893609Sdes */ 359122514Sjhbvoid 360122514Sjhbinit_turnstiles(void) 36193667Sdes{ 362122514Sjhb int i; 36393667Sdes 364122514Sjhb for (i = 0; i < TC_TABLESIZE; i++) { 365122514Sjhb LIST_INIT(&turnstile_chains[i].tc_turnstiles); 366122514Sjhb mtx_init(&turnstile_chains[i].tc_lock, "turnstile chain", 367122514Sjhb NULL, MTX_SPIN); 368131263Sjhb } 369131263Sjhb mtx_init(&td_contested_lock, "td_contested", NULL, MTX_SPIN); 370154482Sjhb LIST_INIT(&thread0.td_contested); 371131263Sjhb thread0.td_turnstile = NULL; 372131263Sjhb} 373131263Sjhb 374131259Sjhb#ifdef TURNSTILE_PROFILING 375131263Sjhbstatic void 376131263Sjhbinit_turnstile_profiling(void *arg) 377131263Sjhb{ 378131263Sjhb struct sysctl_oid *chain_oid; 379131263Sjhb char chain_name[10]; 380131263Sjhb int i; 381131263Sjhb 382131263Sjhb for (i = 0; i < TC_TABLESIZE; i++) { 383131259Sjhb snprintf(chain_name, sizeof(chain_name), "%d", i); 384131259Sjhb chain_oid = SYSCTL_ADD_NODE(NULL, 385131259Sjhb SYSCTL_STATIC_CHILDREN(_debug_turnstile_chains), OID_AUTO, 386131259Sjhb chain_name, CTLFLAG_RD, NULL, "turnstile chain stats"); 387131259Sjhb SYSCTL_ADD_UINT(NULL, SYSCTL_CHILDREN(chain_oid), OID_AUTO, 388131259Sjhb "depth", CTLFLAG_RD, &turnstile_chains[i].tc_depth, 0, 389131259Sjhb NULL); 390131259Sjhb SYSCTL_ADD_UINT(NULL, SYSCTL_CHILDREN(chain_oid), OID_AUTO, 391131259Sjhb "max_depth", CTLFLAG_RD, &turnstile_chains[i].tc_max_depth, 392131259Sjhb 0, NULL); 393122514Sjhb } 39493667Sdes} 395131263SjhbSYSINIT(turnstile_profiling, SI_SUB_LOCK, SI_ORDER_ANY, 396131263Sjhb init_turnstile_profiling, NULL); 397131263Sjhb#endif 39893667Sdes 399122514Sjhbstatic void 400122514Sjhbinit_turnstile0(void *dummy) 40193609Sdes{ 40293609Sdes 403169666Sjeff turnstile_zone = uma_zcreate("TURNSTILE", sizeof(struct turnstile), 404182879Sjhb NULL, 405169666Sjeff#ifdef INVARIANTS 406182879Sjhb turnstile_dtor, 407169666Sjeff#else 408182879Sjhb NULL, 409169666Sjeff#endif 410182879Sjhb turnstile_init, turnstile_fini, UMA_ALIGN_CACHE, UMA_ZONE_NOFREE); 411122514Sjhb thread0.td_turnstile = turnstile_alloc(); 41293609Sdes} 413122514SjhbSYSINIT(turnstile0, SI_SUB_LOCK, SI_ORDER_ANY, init_turnstile0, NULL); 41493609Sdes 41593609Sdes/* 416139453Sjhb * Update a thread on the turnstile list after it's priority has been changed. 417139453Sjhb * The old priority is passed in as an argument. 418139453Sjhb */ 419139453Sjhbvoid 420139453Sjhbturnstile_adjust(struct thread *td, u_char oldpri) 421139453Sjhb{ 422139453Sjhb struct turnstile *ts; 423139453Sjhb 424139453Sjhb MPASS(TD_ON_LOCK(td)); 425139453Sjhb 426139453Sjhb /* 427139453Sjhb * Pick up the lock that td is blocked on. 428139453Sjhb */ 429139453Sjhb ts = td->td_blocked; 430139453Sjhb MPASS(ts != NULL); 431176078Sjeff THREAD_LOCKPTR_ASSERT(td, &ts->ts_lock); 432170295Sjeff mtx_assert(&ts->ts_lock, MA_OWNED); 433139453Sjhb 434139453Sjhb /* Resort the turnstile on the list. */ 435170295Sjeff if (!turnstile_adjust_thread(ts, td)) 436139453Sjhb return; 437139453Sjhb /* 438139453Sjhb * If our priority was lowered and we are at the head of the 439139453Sjhb * turnstile, then propagate our new priority up the chain. 440139453Sjhb * Note that we currently don't try to revoke lent priorities 441139453Sjhb * when our priority goes up. 442139453Sjhb */ 443154937Sjhb MPASS(td->td_tsqueue == TS_EXCLUSIVE_QUEUE || 444154937Sjhb td->td_tsqueue == TS_SHARED_QUEUE); 445154937Sjhb if (td == TAILQ_FIRST(&ts->ts_blocked[td->td_tsqueue]) && 446154937Sjhb td->td_priority < oldpri) { 447139453Sjhb propagate_priority(td); 448170295Sjeff } 449139453Sjhb} 450139453Sjhb 451139453Sjhb/* 452122514Sjhb * Set the owner of the lock this turnstile is attached to. 45374900Sjhb */ 454122514Sjhbstatic void 455122514Sjhbturnstile_setowner(struct turnstile *ts, struct thread *owner) 45674900Sjhb{ 45774900Sjhb 458122514Sjhb mtx_assert(&td_contested_lock, MA_OWNED); 459154937Sjhb MPASS(ts->ts_owner == NULL); 460154937Sjhb 461154937Sjhb /* A shared lock might not have an owner. */ 462154937Sjhb if (owner == NULL) 463154937Sjhb return; 464154937Sjhb 465122514Sjhb MPASS(owner->td_proc->p_magic == P_MAGIC); 466122514Sjhb ts->ts_owner = owner; 467122514Sjhb LIST_INSERT_HEAD(&owner->td_contested, ts, ts_link); 46874900Sjhb} 46974900Sjhb 470169666Sjeff#ifdef INVARIANTS 471122514Sjhb/* 472169666Sjeff * UMA zone item deallocator. 473122514Sjhb */ 474169666Sjeffstatic void 475169666Sjeffturnstile_dtor(void *mem, int size, void *arg) 47674900Sjhb{ 477122514Sjhb struct turnstile *ts; 47874900Sjhb 479169666Sjeff ts = mem; 480169666Sjeff MPASS(TAILQ_EMPTY(&ts->ts_blocked[TS_EXCLUSIVE_QUEUE])); 481169666Sjeff MPASS(TAILQ_EMPTY(&ts->ts_blocked[TS_SHARED_QUEUE])); 482169666Sjeff MPASS(TAILQ_EMPTY(&ts->ts_pending)); 483169666Sjeff} 484169666Sjeff#endif 485169666Sjeff 486169666Sjeff/* 487169666Sjeff * UMA zone item initializer. 488169666Sjeff */ 489169666Sjeffstatic int 490169666Sjeffturnstile_init(void *mem, int size, int flags) 491169666Sjeff{ 492169666Sjeff struct turnstile *ts; 493169666Sjeff 494169666Sjeff bzero(mem, size); 495169666Sjeff ts = mem; 496154937Sjhb TAILQ_INIT(&ts->ts_blocked[TS_EXCLUSIVE_QUEUE]); 497154937Sjhb TAILQ_INIT(&ts->ts_blocked[TS_SHARED_QUEUE]); 498122514Sjhb TAILQ_INIT(&ts->ts_pending); 499122514Sjhb LIST_INIT(&ts->ts_free); 500170295Sjeff mtx_init(&ts->ts_lock, "turnstile lock", NULL, MTX_SPIN | MTX_RECURSE); 501169666Sjeff return (0); 50274900Sjhb} 50374900Sjhb 504170295Sjeffstatic void 505170295Sjeffturnstile_fini(void *mem, int size) 506170295Sjeff{ 507170295Sjeff struct turnstile *ts; 508170295Sjeff 509170295Sjeff ts = mem; 510170295Sjeff mtx_destroy(&ts->ts_lock); 511170295Sjeff} 512170295Sjeff 513122514Sjhb/* 514169666Sjeff * Get a turnstile for a new thread. 515169666Sjeff */ 516169666Sjeffstruct turnstile * 517169666Sjeffturnstile_alloc(void) 518169666Sjeff{ 519169666Sjeff 520169666Sjeff return (uma_zalloc(turnstile_zone, M_WAITOK)); 521169666Sjeff} 522169666Sjeff 523169666Sjeff/* 524122514Sjhb * Free a turnstile when a thread is destroyed. 525122514Sjhb */ 52674900Sjhbvoid 527122514Sjhbturnstile_free(struct turnstile *ts) 52874900Sjhb{ 52974900Sjhb 530169666Sjeff uma_zfree(turnstile_zone, ts); 53174900Sjhb} 53274900Sjhb 53374900Sjhb/* 534136445Sjhb * Lock the turnstile chain associated with the specified lock. 535136445Sjhb */ 536136445Sjhbvoid 537170295Sjeffturnstile_chain_lock(struct lock_object *lock) 538136445Sjhb{ 539136445Sjhb struct turnstile_chain *tc; 540136445Sjhb 541136445Sjhb tc = TC_LOOKUP(lock); 542136445Sjhb mtx_lock_spin(&tc->tc_lock); 543136445Sjhb} 544136445Sjhb 545170295Sjeffstruct turnstile * 546170295Sjeffturnstile_trywait(struct lock_object *lock) 547170295Sjeff{ 548170295Sjeff struct turnstile_chain *tc; 549170295Sjeff struct turnstile *ts; 550170295Sjeff 551170295Sjeff tc = TC_LOOKUP(lock); 552170295Sjeff mtx_lock_spin(&tc->tc_lock); 553170295Sjeff LIST_FOREACH(ts, &tc->tc_turnstiles, ts_hash) 554170295Sjeff if (ts->ts_lockobj == lock) { 555170295Sjeff mtx_lock_spin(&ts->ts_lock); 556170295Sjeff return (ts); 557170295Sjeff } 558170295Sjeff 559170295Sjeff ts = curthread->td_turnstile; 560170295Sjeff MPASS(ts != NULL); 561170295Sjeff mtx_lock_spin(&ts->ts_lock); 562170295Sjeff KASSERT(ts->ts_lockobj == NULL, ("stale ts_lockobj pointer")); 563170295Sjeff ts->ts_lockobj = lock; 564170295Sjeff 565170295Sjeff return (ts); 566170295Sjeff} 567170295Sjeff 568170295Sjeffvoid 569170295Sjeffturnstile_cancel(struct turnstile *ts) 570170295Sjeff{ 571170295Sjeff struct turnstile_chain *tc; 572170295Sjeff struct lock_object *lock; 573170295Sjeff 574170295Sjeff mtx_assert(&ts->ts_lock, MA_OWNED); 575170295Sjeff 576170295Sjeff mtx_unlock_spin(&ts->ts_lock); 577170295Sjeff lock = ts->ts_lockobj; 578170295Sjeff if (ts == curthread->td_turnstile) 579170295Sjeff ts->ts_lockobj = NULL; 580170295Sjeff tc = TC_LOOKUP(lock); 581170295Sjeff mtx_unlock_spin(&tc->tc_lock); 582170295Sjeff} 583170295Sjeff 584136445Sjhb/* 585122514Sjhb * Look up the turnstile for a lock in the hash table locking the associated 586136445Sjhb * turnstile chain along the way. If no turnstile is found in the hash 587136445Sjhb * table, NULL is returned. 58871352Sjasone */ 589122514Sjhbstruct turnstile * 590122514Sjhbturnstile_lookup(struct lock_object *lock) 59171352Sjasone{ 592122514Sjhb struct turnstile_chain *tc; 593122514Sjhb struct turnstile *ts; 59471352Sjasone 595122514Sjhb tc = TC_LOOKUP(lock); 596136445Sjhb mtx_assert(&tc->tc_lock, MA_OWNED); 597122514Sjhb LIST_FOREACH(ts, &tc->tc_turnstiles, ts_hash) 598170295Sjeff if (ts->ts_lockobj == lock) { 599170295Sjeff mtx_lock_spin(&ts->ts_lock); 600122514Sjhb return (ts); 601170295Sjeff } 602122514Sjhb return (NULL); 60371352Sjasone} 60471352Sjasone 60571352Sjasone/* 606122514Sjhb * Unlock the turnstile chain associated with a given lock. 60771352Sjasone */ 60872200Sbmilekicvoid 609170295Sjeffturnstile_chain_unlock(struct lock_object *lock) 61071352Sjasone{ 611122514Sjhb struct turnstile_chain *tc; 61271352Sjasone 613122514Sjhb tc = TC_LOOKUP(lock); 614122514Sjhb mtx_unlock_spin(&tc->tc_lock); 61572200Sbmilekic} 61672200Sbmilekic 61772200Sbmilekic/* 618154937Sjhb * Return a pointer to the thread waiting on this turnstile with the 619154937Sjhb * most important priority or NULL if the turnstile has no waiters. 620154937Sjhb */ 621154937Sjhbstatic struct thread * 622154937Sjhbturnstile_first_waiter(struct turnstile *ts) 623154937Sjhb{ 624154937Sjhb struct thread *std, *xtd; 625154937Sjhb 626154937Sjhb std = TAILQ_FIRST(&ts->ts_blocked[TS_SHARED_QUEUE]); 627154937Sjhb xtd = TAILQ_FIRST(&ts->ts_blocked[TS_EXCLUSIVE_QUEUE]); 628154937Sjhb if (xtd == NULL || (std != NULL && std->td_priority < xtd->td_priority)) 629154937Sjhb return (std); 630154937Sjhb return (xtd); 631154937Sjhb} 632154937Sjhb 633154937Sjhb/* 634122514Sjhb * Take ownership of a turnstile and adjust the priority of the new 635122514Sjhb * owner appropriately. 63672200Sbmilekic */ 63772200Sbmilekicvoid 638170295Sjeffturnstile_claim(struct turnstile *ts) 63972200Sbmilekic{ 640170295Sjeff struct thread *td, *owner; 641122514Sjhb struct turnstile_chain *tc; 64272200Sbmilekic 643170295Sjeff mtx_assert(&ts->ts_lock, MA_OWNED); 644170295Sjeff MPASS(ts != curthread->td_turnstile); 64572200Sbmilekic 646122514Sjhb owner = curthread; 647122514Sjhb mtx_lock_spin(&td_contested_lock); 648122514Sjhb turnstile_setowner(ts, owner); 649122514Sjhb mtx_unlock_spin(&td_contested_lock); 65072200Sbmilekic 651154937Sjhb td = turnstile_first_waiter(ts); 652122514Sjhb MPASS(td != NULL); 653122514Sjhb MPASS(td->td_proc->p_magic == P_MAGIC); 654176078Sjeff THREAD_LOCKPTR_ASSERT(td, &ts->ts_lock); 65572200Sbmilekic 656122514Sjhb /* 657122514Sjhb * Update the priority of the new owner if needed. 658122514Sjhb */ 659170295Sjeff thread_lock(owner); 660122514Sjhb if (td->td_priority < owner->td_priority) 661139453Sjhb sched_lend_prio(owner, td->td_priority); 662170295Sjeff thread_unlock(owner); 663170295Sjeff tc = TC_LOOKUP(ts->ts_lockobj); 664170295Sjeff mtx_unlock_spin(&ts->ts_lock); 665170295Sjeff mtx_unlock_spin(&tc->tc_lock); 66667352Sjhb} 66767352Sjhb 66872200Sbmilekic/* 669136445Sjhb * Block the current thread on the turnstile assicated with 'lock'. This 670136445Sjhb * function will context switch and not return until this thread has been 671136445Sjhb * woken back up. This function must be called with the appropriate 672136445Sjhb * turnstile chain locked and will return with it unlocked. 67372200Sbmilekic */ 67467352Sjhbvoid 675170295Sjeffturnstile_wait(struct turnstile *ts, struct thread *owner, int queue) 67667352Sjhb{ 677122514Sjhb struct turnstile_chain *tc; 67883366Sjulian struct thread *td, *td1; 679170295Sjeff struct lock_object *lock; 68067352Sjhb 68183366Sjulian td = curthread; 682170295Sjeff mtx_assert(&ts->ts_lock, MA_OWNED); 683154937Sjhb if (owner) 684154937Sjhb MPASS(owner->td_proc->p_magic == P_MAGIC); 685154937Sjhb MPASS(queue == TS_SHARED_QUEUE || queue == TS_EXCLUSIVE_QUEUE); 68672200Sbmilekic 687136445Sjhb /* 688136445Sjhb * If the lock does not already have a turnstile, use this thread's 689136445Sjhb * turnstile. Otherwise insert the current thread into the 690136445Sjhb * turnstile already in use by this lock. 691136445Sjhb */ 692170295Sjeff tc = TC_LOOKUP(ts->ts_lockobj); 693218272Sjhb mtx_assert(&tc->tc_lock, MA_OWNED); 694170295Sjeff if (ts == td->td_turnstile) { 695131259Sjhb#ifdef TURNSTILE_PROFILING 696131259Sjhb tc->tc_depth++; 697131259Sjhb if (tc->tc_depth > tc->tc_max_depth) { 698131259Sjhb tc->tc_max_depth = tc->tc_depth; 699131259Sjhb if (tc->tc_max_depth > turnstile_max_depth) 700131259Sjhb turnstile_max_depth = tc->tc_max_depth; 701131259Sjhb } 702131259Sjhb#endif 703122514Sjhb LIST_INSERT_HEAD(&tc->tc_turnstiles, ts, ts_hash); 704122514Sjhb KASSERT(TAILQ_EMPTY(&ts->ts_pending), 705122514Sjhb ("thread's turnstile has pending threads")); 706154937Sjhb KASSERT(TAILQ_EMPTY(&ts->ts_blocked[TS_EXCLUSIVE_QUEUE]), 707154937Sjhb ("thread's turnstile has exclusive waiters")); 708154937Sjhb KASSERT(TAILQ_EMPTY(&ts->ts_blocked[TS_SHARED_QUEUE]), 709154937Sjhb ("thread's turnstile has shared waiters")); 710122514Sjhb KASSERT(LIST_EMPTY(&ts->ts_free), 711122514Sjhb ("thread's turnstile has a non-empty free list")); 712170295Sjeff MPASS(ts->ts_lockobj != NULL); 713122514Sjhb mtx_lock_spin(&td_contested_lock); 714154937Sjhb TAILQ_INSERT_TAIL(&ts->ts_blocked[queue], td, td_lockq); 715122514Sjhb turnstile_setowner(ts, owner); 716122514Sjhb mtx_unlock_spin(&td_contested_lock); 717122514Sjhb } else { 718154937Sjhb TAILQ_FOREACH(td1, &ts->ts_blocked[queue], td_lockq) 719122514Sjhb if (td1->td_priority > td->td_priority) 720122514Sjhb break; 721122514Sjhb mtx_lock_spin(&td_contested_lock); 722122514Sjhb if (td1 != NULL) 723122514Sjhb TAILQ_INSERT_BEFORE(td1, td, td_lockq); 724122514Sjhb else 725154937Sjhb TAILQ_INSERT_TAIL(&ts->ts_blocked[queue], td, td_lockq); 726154937Sjhb MPASS(owner == ts->ts_owner); 727122514Sjhb mtx_unlock_spin(&td_contested_lock); 728122514Sjhb MPASS(td->td_turnstile != NULL); 729122514Sjhb LIST_INSERT_HEAD(&ts->ts_free, td->td_turnstile, ts_hash); 73072200Sbmilekic } 731170295Sjeff thread_lock(td); 732170295Sjeff thread_lock_set(td, &ts->ts_lock); 733122514Sjhb td->td_turnstile = NULL; 73472200Sbmilekic 735122514Sjhb /* Save who we are blocked on and switch. */ 736170295Sjeff lock = ts->ts_lockobj; 737154937Sjhb td->td_tsqueue = queue; 738122514Sjhb td->td_blocked = ts; 739122514Sjhb td->td_lockname = lock->lo_name; 740201879Sattilio td->td_blktick = ticks; 741122514Sjhb TD_SET_LOCK(td); 742170295Sjeff mtx_unlock_spin(&tc->tc_lock); 743122514Sjhb propagate_priority(td); 74472200Sbmilekic 745122514Sjhb if (LOCK_LOG_TEST(lock, 0)) 746139453Sjhb CTR4(KTR_LOCK, "%s: td %d blocked on [%p] %s", __func__, 747139453Sjhb td->td_tid, lock, lock->lo_name); 74872200Sbmilekic 749235459Srstone SDT_PROBE0(sched, , , sleep); 750235459Srstone 751176078Sjeff THREAD_LOCKPTR_ASSERT(td, &ts->ts_lock); 752178272Sjeff mi_switch(SW_VOL | SWT_TURNSTILE, NULL); 75372200Sbmilekic 754122514Sjhb if (LOCK_LOG_TEST(lock, 0)) 755139453Sjhb CTR4(KTR_LOCK, "%s: td %d free from blocked on [%p] %s", 756139453Sjhb __func__, td->td_tid, lock, lock->lo_name); 757170295Sjeff thread_unlock(td); 75867352Sjhb} 75967352Sjhb 76072200Sbmilekic/* 761122514Sjhb * Pick the highest priority thread on this turnstile and put it on the 762122514Sjhb * pending list. This must be called with the turnstile chain locked. 76372200Sbmilekic */ 764122514Sjhbint 765154937Sjhbturnstile_signal(struct turnstile *ts, int queue) 76671352Sjasone{ 767122514Sjhb struct turnstile_chain *tc; 768122514Sjhb struct thread *td; 769122514Sjhb int empty; 77080748Sjhb 771122514Sjhb MPASS(ts != NULL); 772170295Sjeff mtx_assert(&ts->ts_lock, MA_OWNED); 773122514Sjhb MPASS(curthread->td_proc->p_magic == P_MAGIC); 774176017Sjeff MPASS(ts->ts_owner == curthread || ts->ts_owner == NULL); 775154937Sjhb MPASS(queue == TS_SHARED_QUEUE || queue == TS_EXCLUSIVE_QUEUE); 77671352Sjasone 777122514Sjhb /* 778122514Sjhb * Pick the highest priority thread blocked on this lock and 779122514Sjhb * move it to the pending list. 780122514Sjhb */ 781154937Sjhb td = TAILQ_FIRST(&ts->ts_blocked[queue]); 782122514Sjhb MPASS(td->td_proc->p_magic == P_MAGIC); 783122514Sjhb mtx_lock_spin(&td_contested_lock); 784154937Sjhb TAILQ_REMOVE(&ts->ts_blocked[queue], td, td_lockq); 785122514Sjhb mtx_unlock_spin(&td_contested_lock); 786122514Sjhb TAILQ_INSERT_TAIL(&ts->ts_pending, td, td_lockq); 78767352Sjhb 78882304Sbmilekic /* 789122514Sjhb * If the turnstile is now empty, remove it from its chain and 790122514Sjhb * give it to the about-to-be-woken thread. Otherwise take a 791122514Sjhb * turnstile from the free list and give it to the thread. 792105782Sdes */ 793154937Sjhb empty = TAILQ_EMPTY(&ts->ts_blocked[TS_EXCLUSIVE_QUEUE]) && 794154937Sjhb TAILQ_EMPTY(&ts->ts_blocked[TS_SHARED_QUEUE]); 795131259Sjhb if (empty) { 796170295Sjeff tc = TC_LOOKUP(ts->ts_lockobj); 797170295Sjeff mtx_assert(&tc->tc_lock, MA_OWNED); 798122514Sjhb MPASS(LIST_EMPTY(&ts->ts_free)); 799131259Sjhb#ifdef TURNSTILE_PROFILING 800131259Sjhb tc->tc_depth--; 801131259Sjhb#endif 802131259Sjhb } else 803122514Sjhb ts = LIST_FIRST(&ts->ts_free); 804123363Sjhb MPASS(ts != NULL); 805122514Sjhb LIST_REMOVE(ts, ts_hash); 806122514Sjhb td->td_turnstile = ts; 807122514Sjhb 808122514Sjhb return (empty); 80967352Sjhb} 810122514Sjhb 81172200Sbmilekic/* 812122514Sjhb * Put all blocked threads on the pending list. This must be called with 813122514Sjhb * the turnstile chain locked. 81493672Sarr */ 81593672Sarrvoid 816154937Sjhbturnstile_broadcast(struct turnstile *ts, int queue) 81793672Sarr{ 818122514Sjhb struct turnstile_chain *tc; 819122514Sjhb struct turnstile *ts1; 820122514Sjhb struct thread *td; 82193672Sarr 822122514Sjhb MPASS(ts != NULL); 823170295Sjeff mtx_assert(&ts->ts_lock, MA_OWNED); 824122514Sjhb MPASS(curthread->td_proc->p_magic == P_MAGIC); 825176017Sjeff MPASS(ts->ts_owner == curthread || ts->ts_owner == NULL); 826170295Sjeff /* 827170295Sjeff * We must have the chain locked so that we can remove the empty 828170295Sjeff * turnstile from the hash queue. 829170295Sjeff */ 830122514Sjhb tc = TC_LOOKUP(ts->ts_lockobj); 831122514Sjhb mtx_assert(&tc->tc_lock, MA_OWNED); 832154937Sjhb MPASS(queue == TS_SHARED_QUEUE || queue == TS_EXCLUSIVE_QUEUE); 833122514Sjhb 834122514Sjhb /* 835122514Sjhb * Transfer the blocked list to the pending list. 836122514Sjhb */ 837122514Sjhb mtx_lock_spin(&td_contested_lock); 838154937Sjhb TAILQ_CONCAT(&ts->ts_pending, &ts->ts_blocked[queue], td_lockq); 839122514Sjhb mtx_unlock_spin(&td_contested_lock); 840122514Sjhb 841122514Sjhb /* 842122514Sjhb * Give a turnstile to each thread. The last thread gets 843154937Sjhb * this turnstile if the turnstile is empty. 844122514Sjhb */ 845122514Sjhb TAILQ_FOREACH(td, &ts->ts_pending, td_lockq) { 846122514Sjhb if (LIST_EMPTY(&ts->ts_free)) { 847122514Sjhb MPASS(TAILQ_NEXT(td, td_lockq) == NULL); 848122514Sjhb ts1 = ts; 849131259Sjhb#ifdef TURNSTILE_PROFILING 850131259Sjhb tc->tc_depth--; 851131259Sjhb#endif 852122514Sjhb } else 853122514Sjhb ts1 = LIST_FIRST(&ts->ts_free); 854123363Sjhb MPASS(ts1 != NULL); 855122514Sjhb LIST_REMOVE(ts1, ts_hash); 856122514Sjhb td->td_turnstile = ts1; 857122514Sjhb } 85893672Sarr} 859122590Sjhb 86093672Sarr/* 861122514Sjhb * Wakeup all threads on the pending list and adjust the priority of the 862122514Sjhb * current thread appropriately. This must be called with the turnstile 863122514Sjhb * chain locked. 864105782Sdes */ 86567352Sjhbvoid 866154937Sjhbturnstile_unpend(struct turnstile *ts, int owner_type) 86767352Sjhb{ 868122514Sjhb TAILQ_HEAD( ,thread) pending_threads; 869170295Sjeff struct turnstile *nts; 870122514Sjhb struct thread *td; 871139453Sjhb u_char cp, pri; 87272200Sbmilekic 873122514Sjhb MPASS(ts != NULL); 874170295Sjeff mtx_assert(&ts->ts_lock, MA_OWNED); 875176017Sjeff MPASS(ts->ts_owner == curthread || ts->ts_owner == NULL); 876122514Sjhb MPASS(!TAILQ_EMPTY(&ts->ts_pending)); 87772200Sbmilekic 878122514Sjhb /* 879122514Sjhb * Move the list of pending threads out of the turnstile and 880122514Sjhb * into a local variable. 881122514Sjhb */ 882122514Sjhb TAILQ_INIT(&pending_threads); 883122514Sjhb TAILQ_CONCAT(&pending_threads, &ts->ts_pending, td_lockq); 884122514Sjhb#ifdef INVARIANTS 885154937Sjhb if (TAILQ_EMPTY(&ts->ts_blocked[TS_EXCLUSIVE_QUEUE]) && 886154937Sjhb TAILQ_EMPTY(&ts->ts_blocked[TS_SHARED_QUEUE])) 887122514Sjhb ts->ts_lockobj = NULL; 88869429Sjhb#endif 889122514Sjhb /* 890170295Sjeff * Adjust the priority of curthread based on other contested 891170295Sjeff * locks it owns. Don't lower the priority below the base 892170295Sjeff * priority however. 893170295Sjeff */ 894170295Sjeff td = curthread; 895170295Sjeff pri = PRI_MAX; 896170295Sjeff thread_lock(td); 897170295Sjeff mtx_lock_spin(&td_contested_lock); 898170295Sjeff /* 899122514Sjhb * Remove the turnstile from this thread's list of contested locks 900122514Sjhb * since this thread doesn't own it anymore. New threads will 901122514Sjhb * not be blocking on the turnstile until it is claimed by a new 902154937Sjhb * owner. There might not be a current owner if this is a shared 903154937Sjhb * lock. 904122514Sjhb */ 905154937Sjhb if (ts->ts_owner != NULL) { 906154937Sjhb ts->ts_owner = NULL; 907154937Sjhb LIST_REMOVE(ts, ts_link); 908154937Sjhb } 909170295Sjeff LIST_FOREACH(nts, &td->td_contested, ts_link) { 910170295Sjeff cp = turnstile_first_waiter(nts)->td_priority; 911122514Sjhb if (cp < pri) 912122514Sjhb pri = cp; 913122514Sjhb } 914122514Sjhb mtx_unlock_spin(&td_contested_lock); 915139453Sjhb sched_unlend_prio(td, pri); 916170295Sjeff thread_unlock(td); 917122514Sjhb /* 918122514Sjhb * Wake up all the pending threads. If a thread is not blocked 919122514Sjhb * on a lock, then it is currently executing on another CPU in 920123364Sjhb * turnstile_wait() or sitting on a run queue waiting to resume 921123364Sjhb * in turnstile_wait(). Set a flag to force it to try to acquire 922122514Sjhb * the lock again instead of blocking. 923122514Sjhb */ 924122514Sjhb while (!TAILQ_EMPTY(&pending_threads)) { 925122514Sjhb td = TAILQ_FIRST(&pending_threads); 926122514Sjhb TAILQ_REMOVE(&pending_threads, td, td_lockq); 927235459Srstone SDT_PROBE2(sched, , , wakeup, td, td->td_proc); 928170295Sjeff thread_lock(td); 929176078Sjeff THREAD_LOCKPTR_ASSERT(td, &ts->ts_lock); 930122514Sjhb MPASS(td->td_proc->p_magic == P_MAGIC); 931170295Sjeff MPASS(TD_ON_LOCK(td)); 932170295Sjeff TD_CLR_LOCK(td); 933170295Sjeff MPASS(TD_CAN_RUN(td)); 934170295Sjeff td->td_blocked = NULL; 935170295Sjeff td->td_lockname = NULL; 936201879Sattilio td->td_blktick = 0; 937154937Sjhb#ifdef INVARIANTS 938170295Sjeff td->td_tsqueue = 0xff; 939154937Sjhb#endif 940170295Sjeff sched_add(td, SRQ_BORING); 941170295Sjeff thread_unlock(td); 942122514Sjhb } 943170295Sjeff mtx_unlock_spin(&ts->ts_lock); 94467352Sjhb} 94567352Sjhb 94672200Sbmilekic/* 947157844Sjhb * Give up ownership of a turnstile. This must be called with the 948157844Sjhb * turnstile chain locked. 949157844Sjhb */ 950157844Sjhbvoid 951157844Sjhbturnstile_disown(struct turnstile *ts) 952157844Sjhb{ 953157844Sjhb struct thread *td; 954157844Sjhb u_char cp, pri; 955157844Sjhb 956157844Sjhb MPASS(ts != NULL); 957170295Sjeff mtx_assert(&ts->ts_lock, MA_OWNED); 958157844Sjhb MPASS(ts->ts_owner == curthread); 959157844Sjhb MPASS(TAILQ_EMPTY(&ts->ts_pending)); 960157844Sjhb MPASS(!TAILQ_EMPTY(&ts->ts_blocked[TS_EXCLUSIVE_QUEUE]) || 961157844Sjhb !TAILQ_EMPTY(&ts->ts_blocked[TS_SHARED_QUEUE])); 962157844Sjhb 963157844Sjhb /* 964157844Sjhb * Remove the turnstile from this thread's list of contested locks 965157844Sjhb * since this thread doesn't own it anymore. New threads will 966157844Sjhb * not be blocking on the turnstile until it is claimed by a new 967157844Sjhb * owner. 968157844Sjhb */ 969157844Sjhb mtx_lock_spin(&td_contested_lock); 970157844Sjhb ts->ts_owner = NULL; 971157844Sjhb LIST_REMOVE(ts, ts_link); 972157844Sjhb mtx_unlock_spin(&td_contested_lock); 973157844Sjhb 974157844Sjhb /* 975157844Sjhb * Adjust the priority of curthread based on other contested 976157844Sjhb * locks it owns. Don't lower the priority below the base 977157844Sjhb * priority however. 978157844Sjhb */ 979157844Sjhb td = curthread; 980157844Sjhb pri = PRI_MAX; 981170295Sjeff thread_lock(td); 982170295Sjeff mtx_unlock_spin(&ts->ts_lock); 983157844Sjhb mtx_lock_spin(&td_contested_lock); 984157844Sjhb LIST_FOREACH(ts, &td->td_contested, ts_link) { 985157844Sjhb cp = turnstile_first_waiter(ts)->td_priority; 986157844Sjhb if (cp < pri) 987157844Sjhb pri = cp; 988157844Sjhb } 989157844Sjhb mtx_unlock_spin(&td_contested_lock); 990157844Sjhb sched_unlend_prio(td, pri); 991170295Sjeff thread_unlock(td); 992157844Sjhb} 993157844Sjhb 994157844Sjhb/* 995122514Sjhb * Return the first thread in a turnstile. 99672200Sbmilekic */ 997122514Sjhbstruct thread * 998154937Sjhbturnstile_head(struct turnstile *ts, int queue) 99967352Sjhb{ 1000122514Sjhb#ifdef INVARIANTS 100167352Sjhb 1002122514Sjhb MPASS(ts != NULL); 1003154937Sjhb MPASS(queue == TS_SHARED_QUEUE || queue == TS_EXCLUSIVE_QUEUE); 1004170295Sjeff mtx_assert(&ts->ts_lock, MA_OWNED); 1005122514Sjhb#endif 1006154937Sjhb return (TAILQ_FIRST(&ts->ts_blocked[queue])); 100771320Sjasone} 1008154937Sjhb 1009157844Sjhb/* 1010157844Sjhb * Returns true if a sub-queue of a turnstile is empty. 1011157844Sjhb */ 1012157844Sjhbint 1013157844Sjhbturnstile_empty(struct turnstile *ts, int queue) 1014157844Sjhb{ 1015157844Sjhb#ifdef INVARIANTS 1016157844Sjhb 1017157844Sjhb MPASS(ts != NULL); 1018157844Sjhb MPASS(queue == TS_SHARED_QUEUE || queue == TS_EXCLUSIVE_QUEUE); 1019170295Sjeff mtx_assert(&ts->ts_lock, MA_OWNED); 1020157844Sjhb#endif 1021157844Sjhb return (TAILQ_EMPTY(&ts->ts_blocked[queue])); 1022157844Sjhb} 1023157844Sjhb 1024154937Sjhb#ifdef DDB 1025154937Sjhbstatic void 1026154937Sjhbprint_thread(struct thread *td, const char *prefix) 1027154937Sjhb{ 1028154937Sjhb 1029154937Sjhb db_printf("%s%p (tid %d, pid %d, \"%s\")\n", prefix, td, td->td_tid, 1030157952Sjhb td->td_proc->p_pid, td->td_name[0] != '\0' ? td->td_name : 1031173600Sjulian td->td_name); 1032154937Sjhb} 1033154937Sjhb 1034154937Sjhbstatic void 1035154937Sjhbprint_queue(struct threadqueue *queue, const char *header, const char *prefix) 1036154937Sjhb{ 1037154937Sjhb struct thread *td; 1038154937Sjhb 1039154937Sjhb db_printf("%s:\n", header); 1040154937Sjhb if (TAILQ_EMPTY(queue)) { 1041154937Sjhb db_printf("%sempty\n", prefix); 1042154937Sjhb return; 1043154937Sjhb } 1044154937Sjhb TAILQ_FOREACH(td, queue, td_lockq) { 1045154937Sjhb print_thread(td, prefix); 1046154937Sjhb } 1047154937Sjhb} 1048154937Sjhb 1049154937SjhbDB_SHOW_COMMAND(turnstile, db_show_turnstile) 1050154937Sjhb{ 1051154937Sjhb struct turnstile_chain *tc; 1052154937Sjhb struct turnstile *ts; 1053154937Sjhb struct lock_object *lock; 1054154937Sjhb int i; 1055154937Sjhb 1056154937Sjhb if (!have_addr) 1057154937Sjhb return; 1058154937Sjhb 1059154937Sjhb /* 1060154937Sjhb * First, see if there is an active turnstile for the lock indicated 1061154937Sjhb * by the address. 1062154937Sjhb */ 1063154937Sjhb lock = (struct lock_object *)addr; 1064154937Sjhb tc = TC_LOOKUP(lock); 1065154937Sjhb LIST_FOREACH(ts, &tc->tc_turnstiles, ts_hash) 1066154937Sjhb if (ts->ts_lockobj == lock) 1067154937Sjhb goto found; 1068154937Sjhb 1069154937Sjhb /* 1070154937Sjhb * Second, see if there is an active turnstile at the address 1071154937Sjhb * indicated. 1072154937Sjhb */ 1073154937Sjhb for (i = 0; i < TC_TABLESIZE; i++) 1074154937Sjhb LIST_FOREACH(ts, &turnstile_chains[i].tc_turnstiles, ts_hash) { 1075154937Sjhb if (ts == (struct turnstile *)addr) 1076154937Sjhb goto found; 1077154937Sjhb } 1078154937Sjhb 1079154937Sjhb db_printf("Unable to locate a turnstile via %p\n", (void *)addr); 1080154937Sjhb return; 1081154937Sjhbfound: 1082154937Sjhb lock = ts->ts_lockobj; 1083154937Sjhb db_printf("Lock: %p - (%s) %s\n", lock, LOCK_CLASS(lock)->lc_name, 1084154937Sjhb lock->lo_name); 1085154937Sjhb if (ts->ts_owner) 1086154937Sjhb print_thread(ts->ts_owner, "Lock Owner: "); 1087154937Sjhb else 1088154937Sjhb db_printf("Lock Owner: none\n"); 1089154937Sjhb print_queue(&ts->ts_blocked[TS_SHARED_QUEUE], "Shared Waiters", "\t"); 1090154937Sjhb print_queue(&ts->ts_blocked[TS_EXCLUSIVE_QUEUE], "Exclusive Waiters", 1091154937Sjhb "\t"); 1092154937Sjhb print_queue(&ts->ts_pending, "Pending Threads", "\t"); 1093154937Sjhb 1094154937Sjhb} 1095158031Sjhb 1096161324Sjhb/* 1097161324Sjhb * Show all the threads a particular thread is waiting on based on 1098161324Sjhb * non-sleepable and non-spin locks. 1099161324Sjhb */ 1100158031Sjhbstatic void 1101161324Sjhbprint_lockchain(struct thread *td, const char *prefix) 1102158031Sjhb{ 1103158031Sjhb struct lock_object *lock; 1104158031Sjhb struct lock_class *class; 1105158031Sjhb struct turnstile *ts; 1106158031Sjhb 1107158031Sjhb /* 1108158031Sjhb * Follow the chain. We keep walking as long as the thread is 1109158031Sjhb * blocked on a turnstile that has an owner. 1110158031Sjhb */ 1111160313Sjhb while (!db_pager_quit) { 1112158031Sjhb db_printf("%sthread %d (pid %d, %s) ", prefix, td->td_tid, 1113158031Sjhb td->td_proc->p_pid, td->td_name[0] != '\0' ? td->td_name : 1114173600Sjulian td->td_name); 1115158031Sjhb switch (td->td_state) { 1116158031Sjhb case TDS_INACTIVE: 1117158031Sjhb db_printf("is inactive\n"); 1118158031Sjhb return; 1119158031Sjhb case TDS_CAN_RUN: 1120158031Sjhb db_printf("can run\n"); 1121158031Sjhb return; 1122158031Sjhb case TDS_RUNQ: 1123158031Sjhb db_printf("is on a run queue\n"); 1124158031Sjhb return; 1125158031Sjhb case TDS_RUNNING: 1126158031Sjhb db_printf("running on CPU %d\n", td->td_oncpu); 1127158031Sjhb return; 1128158031Sjhb case TDS_INHIBITED: 1129158031Sjhb if (TD_ON_LOCK(td)) { 1130158031Sjhb ts = td->td_blocked; 1131158031Sjhb lock = ts->ts_lockobj; 1132158031Sjhb class = LOCK_CLASS(lock); 1133158031Sjhb db_printf("blocked on lock %p (%s) \"%s\"\n", 1134158031Sjhb lock, class->lc_name, lock->lo_name); 1135158031Sjhb if (ts->ts_owner == NULL) 1136158031Sjhb return; 1137158031Sjhb td = ts->ts_owner; 1138158031Sjhb break; 1139158031Sjhb } 1140158031Sjhb db_printf("inhibited\n"); 1141158031Sjhb return; 1142158031Sjhb default: 1143158031Sjhb db_printf("??? (%#x)\n", td->td_state); 1144158031Sjhb return; 1145158031Sjhb } 1146158031Sjhb } 1147158031Sjhb} 1148158031Sjhb 1149161324SjhbDB_SHOW_COMMAND(lockchain, db_show_lockchain) 1150158031Sjhb{ 1151158031Sjhb struct thread *td; 1152158031Sjhb 1153158031Sjhb /* Figure out which thread to start with. */ 1154158031Sjhb if (have_addr) 1155158031Sjhb td = db_lookup_thread(addr, TRUE); 1156158031Sjhb else 1157158031Sjhb td = kdb_thread; 1158158031Sjhb 1159161324Sjhb print_lockchain(td, ""); 1160158031Sjhb} 1161158031Sjhb 1162183054SsamDB_SHOW_ALL_COMMAND(chains, db_show_allchains) 1163158031Sjhb{ 1164158031Sjhb struct thread *td; 1165158031Sjhb struct proc *p; 1166158031Sjhb int i; 1167158031Sjhb 1168158031Sjhb i = 1; 1169166073Sdelphij FOREACH_PROC_IN_SYSTEM(p) { 1170158031Sjhb FOREACH_THREAD_IN_PROC(p, td) { 1171158031Sjhb if (TD_ON_LOCK(td) && LIST_EMPTY(&td->td_contested)) { 1172158031Sjhb db_printf("chain %d:\n", i++); 1173161324Sjhb print_lockchain(td, " "); 1174158031Sjhb } 1175160313Sjhb if (db_pager_quit) 1176160313Sjhb return; 1177158031Sjhb } 1178158031Sjhb } 1179158031Sjhb} 1180183054SsamDB_SHOW_ALIAS(allchains, db_show_allchains) 1181158031Sjhb 1182161337Sjhb/* 1183161337Sjhb * Show all the threads a particular thread is waiting on based on 1184161337Sjhb * sleepable locks. 1185161337Sjhb */ 1186161337Sjhbstatic void 1187161337Sjhbprint_sleepchain(struct thread *td, const char *prefix) 1188161337Sjhb{ 1189161337Sjhb struct thread *owner; 1190161337Sjhb 1191161337Sjhb /* 1192161337Sjhb * Follow the chain. We keep walking as long as the thread is 1193161337Sjhb * blocked on a sleep lock that has an owner. 1194161337Sjhb */ 1195161337Sjhb while (!db_pager_quit) { 1196161337Sjhb db_printf("%sthread %d (pid %d, %s) ", prefix, td->td_tid, 1197161337Sjhb td->td_proc->p_pid, td->td_name[0] != '\0' ? td->td_name : 1198173600Sjulian td->td_name); 1199161337Sjhb switch (td->td_state) { 1200161337Sjhb case TDS_INACTIVE: 1201161337Sjhb db_printf("is inactive\n"); 1202161337Sjhb return; 1203161337Sjhb case TDS_CAN_RUN: 1204161337Sjhb db_printf("can run\n"); 1205161337Sjhb return; 1206161337Sjhb case TDS_RUNQ: 1207161337Sjhb db_printf("is on a run queue\n"); 1208161337Sjhb return; 1209161337Sjhb case TDS_RUNNING: 1210161337Sjhb db_printf("running on CPU %d\n", td->td_oncpu); 1211161337Sjhb return; 1212161337Sjhb case TDS_INHIBITED: 1213161337Sjhb if (TD_ON_SLEEPQ(td)) { 1214161337Sjhb if (lockmgr_chain(td, &owner) || 1215161337Sjhb sx_chain(td, &owner)) { 1216161337Sjhb if (owner == NULL) 1217161337Sjhb return; 1218161337Sjhb td = owner; 1219161337Sjhb break; 1220161337Sjhb } 1221161337Sjhb db_printf("sleeping on %p \"%s\"\n", 1222161337Sjhb td->td_wchan, td->td_wmesg); 1223161337Sjhb return; 1224161337Sjhb } 1225161337Sjhb db_printf("inhibited\n"); 1226161337Sjhb return; 1227161337Sjhb default: 1228161337Sjhb db_printf("??? (%#x)\n", td->td_state); 1229161337Sjhb return; 1230161337Sjhb } 1231161337Sjhb } 1232161337Sjhb} 1233161337Sjhb 1234161337SjhbDB_SHOW_COMMAND(sleepchain, db_show_sleepchain) 1235161337Sjhb{ 1236161337Sjhb struct thread *td; 1237161337Sjhb 1238161337Sjhb /* Figure out which thread to start with. */ 1239161337Sjhb if (have_addr) 1240161337Sjhb td = db_lookup_thread(addr, TRUE); 1241161337Sjhb else 1242161337Sjhb td = kdb_thread; 1243161337Sjhb 1244161337Sjhb print_sleepchain(td, ""); 1245161337Sjhb} 1246161337Sjhb 1247158031Sjhbstatic void print_waiters(struct turnstile *ts, int indent); 1248158031Sjhb 1249158031Sjhbstatic void 1250158031Sjhbprint_waiter(struct thread *td, int indent) 1251158031Sjhb{ 1252158031Sjhb struct turnstile *ts; 1253158031Sjhb int i; 1254158031Sjhb 1255160313Sjhb if (db_pager_quit) 1256160313Sjhb return; 1257158031Sjhb for (i = 0; i < indent; i++) 1258158031Sjhb db_printf(" "); 1259158031Sjhb print_thread(td, "thread "); 1260158031Sjhb LIST_FOREACH(ts, &td->td_contested, ts_link) 1261158031Sjhb print_waiters(ts, indent + 1); 1262158031Sjhb} 1263158031Sjhb 1264158031Sjhbstatic void 1265158031Sjhbprint_waiters(struct turnstile *ts, int indent) 1266158031Sjhb{ 1267158031Sjhb struct lock_object *lock; 1268158031Sjhb struct lock_class *class; 1269158031Sjhb struct thread *td; 1270158031Sjhb int i; 1271158031Sjhb 1272160313Sjhb if (db_pager_quit) 1273160313Sjhb return; 1274158031Sjhb lock = ts->ts_lockobj; 1275158031Sjhb class = LOCK_CLASS(lock); 1276158031Sjhb for (i = 0; i < indent; i++) 1277158031Sjhb db_printf(" "); 1278158031Sjhb db_printf("lock %p (%s) \"%s\"\n", lock, class->lc_name, lock->lo_name); 1279158031Sjhb TAILQ_FOREACH(td, &ts->ts_blocked[TS_EXCLUSIVE_QUEUE], td_lockq) 1280158031Sjhb print_waiter(td, indent + 1); 1281158031Sjhb TAILQ_FOREACH(td, &ts->ts_blocked[TS_SHARED_QUEUE], td_lockq) 1282158031Sjhb print_waiter(td, indent + 1); 1283158031Sjhb TAILQ_FOREACH(td, &ts->ts_pending, td_lockq) 1284158031Sjhb print_waiter(td, indent + 1); 1285158031Sjhb} 1286158031Sjhb 1287161324SjhbDB_SHOW_COMMAND(locktree, db_show_locktree) 1288158031Sjhb{ 1289158031Sjhb struct lock_object *lock; 1290158031Sjhb struct lock_class *class; 1291158031Sjhb struct turnstile_chain *tc; 1292158031Sjhb struct turnstile *ts; 1293158031Sjhb 1294158031Sjhb if (!have_addr) 1295158031Sjhb return; 1296158031Sjhb lock = (struct lock_object *)addr; 1297158031Sjhb tc = TC_LOOKUP(lock); 1298158031Sjhb LIST_FOREACH(ts, &tc->tc_turnstiles, ts_hash) 1299158031Sjhb if (ts->ts_lockobj == lock) 1300158031Sjhb break; 1301158031Sjhb if (ts == NULL) { 1302158031Sjhb class = LOCK_CLASS(lock); 1303158031Sjhb db_printf("lock %p (%s) \"%s\"\n", lock, class->lc_name, 1304158031Sjhb lock->lo_name); 1305158031Sjhb } else 1306158031Sjhb print_waiters(ts, 0); 1307158031Sjhb} 1308154937Sjhb#endif 1309