The Design and Implementation of the FreeBSD Operating System, Second Edition
Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]

FreeBSD/Linux Kernel Cross Reference
sys/kern/subr_turnstile.c

Version: -  FREEBSD  -  FREEBSD-12-STABLE  -  FREEBSD-12-0  -  FREEBSD-11-STABLE  -  FREEBSD-11-2  -  FREEBSD-11-1  -  FREEBSD-11-0  -  FREEBSD-10-STABLE  -  FREEBSD-10-4  -  FREEBSD-10-3  -  FREEBSD-10-2  -  FREEBSD-10-1  -  FREEBSD-10-0  -  FREEBSD-9-STABLE  -  FREEBSD-9-3  -  FREEBSD-9-2  -  FREEBSD-9-1  -  FREEBSD-9-0  -  FREEBSD-8-STABLE  -  FREEBSD-8-4  -  FREEBSD-8-3  -  FREEBSD-8-2  -  FREEBSD-8-1  -  FREEBSD-8-0  -  FREEBSD-7-STABLE  -  FREEBSD-7-4  -  FREEBSD-7-3  -  FREEBSD-7-2  -  FREEBSD-7-1  -  FREEBSD-7-0  -  FREEBSD-6-STABLE  -  FREEBSD-6-4  -  FREEBSD-6-3  -  FREEBSD-6-2  -  FREEBSD-6-1  -  FREEBSD-6-0  -  FREEBSD-5-STABLE  -  FREEBSD-5-5  -  FREEBSD-5-4  -  FREEBSD-5-3  -  FREEBSD-5-2  -  FREEBSD-5-1  -  FREEBSD-5-0  -  FREEBSD-4-STABLE  -  FREEBSD-3-STABLE  -  FREEBSD22  -  linux-2.6  -  linux-2.4.22  -  MK83  -  MK84  -  PLAN9  -  DFBSD  -  NETBSD  -  NETBSD5  -  NETBSD4  -  NETBSD3  -  NETBSD20  -  OPENBSD  -  xnu-517  -  xnu-792  -  xnu-792.6.70  -  xnu-1228  -  xnu-1456.1.26  -  xnu-1699.24.8  -  xnu-2050.18.24  -  OPENSOLARIS  -  minix-3-1-1 
SearchContext: -  none  -  3  -  10 

    1 /*-
    2  * Copyright (c) 1998 Berkeley Software Design, Inc. All rights reserved.
    3  *
    4  * Redistribution and use in source and binary forms, with or without
    5  * modification, are permitted provided that the following conditions
    6  * are met:
    7  * 1. Redistributions of source code must retain the above copyright
    8  *    notice, this list of conditions and the following disclaimer.
    9  * 2. Redistributions in binary form must reproduce the above copyright
   10  *    notice, this list of conditions and the following disclaimer in the
   11  *    documentation and/or other materials provided with the distribution.
   12  * 3. Berkeley Software Design Inc's name may not be used to endorse or
   13  *    promote products derived from this software without specific prior
   14  *    written permission.
   15  *
   16  * THIS SOFTWARE IS PROVIDED BY BERKELEY SOFTWARE DESIGN INC ``AS IS'' AND
   17  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
   18  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
   19  * ARE DISCLAIMED.  IN NO EVENT SHALL BERKELEY SOFTWARE DESIGN INC BE LIABLE
   20  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
   21  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
   22  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
   23  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
   24  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
   25  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
   26  * SUCH DAMAGE.
   27  *
   28  *      from BSDI $Id: mutex_witness.c,v 1.1.2.20 2000/04/27 03:10:27 cp Exp $
   29  *      and BSDI $Id: synch_machdep.c,v 2.3.2.39 2000/04/27 03:10:25 cp Exp $
   30  */
   31 
   32 /*
   33  * Implementation of turnstiles used to hold queue of threads blocked on
   34  * non-sleepable locks.  Sleepable locks use condition variables to
   35  * implement their queues.  Turnstiles differ from a sleep queue in that
   36  * turnstile queue's are assigned to a lock held by an owning thread.  Thus,
   37  * when one thread is enqueued onto a turnstile, it can lend its priority
   38  * to the owning thread.
   39  *
   40  * We wish to avoid bloating locks with an embedded turnstile and we do not
   41  * want to use back-pointers in the locks for the same reason.  Thus, we
   42  * use a similar approach to that of Solaris 7 as described in Solaris
   43  * Internals by Jim Mauro and Richard McDougall.  Turnstiles are looked up
   44  * in a hash table based on the address of the lock.  Each entry in the
   45  * hash table is a linked-lists of turnstiles and is called a turnstile
   46  * chain.  Each chain contains a spin mutex that protects all of the
   47  * turnstiles in the chain.
   48  *
   49  * Each time a thread is created, a turnstile is allocated from a UMA zone
   50  * and attached to that thread.  When a thread blocks on a lock, if it is the
   51  * first thread to block, it lends its turnstile to the lock.  If the lock
   52  * already has a turnstile, then it gives its turnstile to the lock's
   53  * turnstile's free list.  When a thread is woken up, it takes a turnstile from
   54  * the free list if there are any other waiters.  If it is the only thread
   55  * blocked on the lock, then it reclaims the turnstile associated with the lock
   56  * and removes it from the hash table.
   57  */
   58 
   59 #include <sys/cdefs.h>
   60 __FBSDID("$FreeBSD: stable/10/sys/kern/subr_turnstile.c 296728 2016-03-12 17:17:34Z kib $");
   61 
   62 #include "opt_ddb.h"
   63 #include "opt_kdtrace.h"
   64 #include "opt_turnstile_profiling.h"
   65 #include "opt_sched.h"
   66 
   67 #include <sys/param.h>
   68 #include <sys/systm.h>
   69 #include <sys/kdb.h>
   70 #include <sys/kernel.h>
   71 #include <sys/ktr.h>
   72 #include <sys/lock.h>
   73 #include <sys/mutex.h>
   74 #include <sys/proc.h>
   75 #include <sys/queue.h>
   76 #include <sys/sched.h>
   77 #include <sys/sdt.h>
   78 #include <sys/sysctl.h>
   79 #include <sys/turnstile.h>
   80 
   81 #include <vm/uma.h>
   82 
   83 #ifdef DDB
   84 #include <ddb/ddb.h>
   85 #include <sys/lockmgr.h>
   86 #include <sys/sx.h>
   87 #endif
   88 
   89 /*
   90  * Constants for the hash table of turnstile chains.  TC_SHIFT is a magic
   91  * number chosen because the sleep queue's use the same value for the
   92  * shift.  Basically, we ignore the lower 8 bits of the address.
   93  * TC_TABLESIZE must be a power of two for TC_MASK to work properly.
   94  */
   95 #define TC_TABLESIZE    128                     /* Must be power of 2. */
   96 #define TC_MASK         (TC_TABLESIZE - 1)
   97 #define TC_SHIFT        8
   98 #define TC_HASH(lock)   (((uintptr_t)(lock) >> TC_SHIFT) & TC_MASK)
   99 #define TC_LOOKUP(lock) &turnstile_chains[TC_HASH(lock)]
  100 
  101 /*
  102  * There are three different lists of turnstiles as follows.  The list
  103  * connected by ts_link entries is a per-thread list of all the turnstiles
  104  * attached to locks that we own.  This is used to fixup our priority when
  105  * a lock is released.  The other two lists use the ts_hash entries.  The
  106  * first of these two is the turnstile chain list that a turnstile is on
  107  * when it is attached to a lock.  The second list to use ts_hash is the
  108  * free list hung off of a turnstile that is attached to a lock.
  109  *
  110  * Each turnstile contains three lists of threads.  The two ts_blocked lists
  111  * are linked list of threads blocked on the turnstile's lock.  One list is
  112  * for exclusive waiters, and the other is for shared waiters.  The
  113  * ts_pending list is a linked list of threads previously awakened by
  114  * turnstile_signal() or turnstile_wait() that are waiting to be put on
  115  * the run queue.
  116  *
  117  * Locking key:
  118  *  c - turnstile chain lock
  119  *  q - td_contested lock
  120  */
  121 struct turnstile {
  122         struct mtx ts_lock;                     /* Spin lock for self. */
  123         struct threadqueue ts_blocked[2];       /* (c + q) Blocked threads. */
  124         struct threadqueue ts_pending;          /* (c) Pending threads. */
  125         LIST_ENTRY(turnstile) ts_hash;          /* (c) Chain and free list. */
  126         LIST_ENTRY(turnstile) ts_link;          /* (q) Contested locks. */
  127         LIST_HEAD(, turnstile) ts_free;         /* (c) Free turnstiles. */
  128         struct lock_object *ts_lockobj;         /* (c) Lock we reference. */
  129         struct thread *ts_owner;                /* (c + q) Who owns the lock. */
  130 };
  131 
  132 struct turnstile_chain {
  133         LIST_HEAD(, turnstile) tc_turnstiles;   /* List of turnstiles. */
  134         struct mtx tc_lock;                     /* Spin lock for this chain. */
  135 #ifdef TURNSTILE_PROFILING
  136         u_int   tc_depth;                       /* Length of tc_queues. */
  137         u_int   tc_max_depth;                   /* Max length of tc_queues. */
  138 #endif
  139 };
  140 
  141 #ifdef TURNSTILE_PROFILING
  142 u_int turnstile_max_depth;
  143 static SYSCTL_NODE(_debug, OID_AUTO, turnstile, CTLFLAG_RD, 0,
  144     "turnstile profiling");
  145 static SYSCTL_NODE(_debug_turnstile, OID_AUTO, chains, CTLFLAG_RD, 0,
  146     "turnstile chain stats");
  147 SYSCTL_UINT(_debug_turnstile, OID_AUTO, max_depth, CTLFLAG_RD,
  148     &turnstile_max_depth, 0, "maximum depth achieved of a single chain");
  149 #endif
  150 static struct mtx td_contested_lock;
  151 static struct turnstile_chain turnstile_chains[TC_TABLESIZE];
  152 static uma_zone_t turnstile_zone;
  153 
  154 /*
  155  * Prototypes for non-exported routines.
  156  */
  157 static void     init_turnstile0(void *dummy);
  158 #ifdef TURNSTILE_PROFILING
  159 static void     init_turnstile_profiling(void *arg);
  160 #endif
  161 static void     propagate_priority(struct thread *td);
  162 static int      turnstile_adjust_thread(struct turnstile *ts,
  163                     struct thread *td);
  164 static struct thread *turnstile_first_waiter(struct turnstile *ts);
  165 static void     turnstile_setowner(struct turnstile *ts, struct thread *owner);
  166 #ifdef INVARIANTS
  167 static void     turnstile_dtor(void *mem, int size, void *arg);
  168 #endif
  169 static int      turnstile_init(void *mem, int size, int flags);
  170 static void     turnstile_fini(void *mem, int size);
  171 
  172 SDT_PROVIDER_DECLARE(sched);
  173 SDT_PROBE_DEFINE(sched, , , sleep);
  174 SDT_PROBE_DEFINE2(sched, , , wakeup, "struct thread *", 
  175     "struct proc *");
  176 
  177 /*
  178  * Walks the chain of turnstiles and their owners to propagate the priority
  179  * of the thread being blocked to all the threads holding locks that have to
  180  * release their locks before this thread can run again.
  181  */
  182 static void
  183 propagate_priority(struct thread *td)
  184 {
  185         struct turnstile *ts;
  186         int pri;
  187 
  188         THREAD_LOCK_ASSERT(td, MA_OWNED);
  189         pri = td->td_priority;
  190         ts = td->td_blocked;
  191         THREAD_LOCKPTR_ASSERT(td, &ts->ts_lock);
  192         /*
  193          * 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  */
  289 static int
  290 turnstile_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  */
  359 void
  360 init_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
  375 static void
  376 init_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 }
  395 SYSINIT(turnstile_profiling, SI_SUB_LOCK, SI_ORDER_ANY,
  396     init_turnstile_profiling, NULL);
  397 #endif
  398 
  399 static void
  400 init_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 }
  413 SYSINIT(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  */
  419 void
  420 turnstile_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  */
  454 static void
  455 turnstile_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  */
  474 static void
  475 turnstile_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  */
  489 static int
  490 turnstile_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 
  504 static void
  505 turnstile_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  */
  516 struct turnstile *
  517 turnstile_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  */
  526 void
  527 turnstile_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  */
  536 void
  537 turnstile_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 
  545 struct turnstile *
  546 turnstile_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 
  568 void
  569 turnstile_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  */
  589 struct turnstile *
  590 turnstile_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  */
  608 void
  609 turnstile_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  */
  621 static struct thread *
  622 turnstile_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  */
  637 void
  638 turnstile_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  */
  674 void
  675 turnstile_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  */
  764 int
  765 turnstile_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  */
  815 void
  816 turnstile_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  */
  865 void
  866 turnstile_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  */
  950 void
  951 turnstile_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  */
  997 struct thread *
  998 turnstile_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  */
 1012 int
 1013 turnstile_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
 1025 static void
 1026 print_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 
 1033 static void
 1034 print_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 
 1048 DB_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;
 1080 found:
 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  */
 1099 static void
 1100 print_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 
 1147 DB_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 
 1160 DB_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 }
 1178 DB_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  */
 1184 static void
 1185 print_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 
 1231 DB_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 
 1244 static void     print_waiters(struct turnstile *ts, int indent);
 1245         
 1246 static void
 1247 print_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 
 1261 static void
 1262 print_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 
 1284 DB_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

Cache object: b60ce79073ab6c9cb5933b06dab17f9f


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]


This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.