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_witness.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) 2008 Isilon Systems, Inc.
    3  * Copyright (c) 2008 Ilya Maykov <ivmaykov@gmail.com>
    4  * Copyright (c) 1998 Berkeley Software Design, Inc.
    5  * All rights reserved.
    6  *
    7  * Redistribution and use in source and binary forms, with or without
    8  * modification, are permitted provided that the following conditions
    9  * are met:
   10  * 1. Redistributions of source code must retain the above copyright
   11  *    notice, this list of conditions and the following disclaimer.
   12  * 2. Redistributions in binary form must reproduce the above copyright
   13  *    notice, this list of conditions and the following disclaimer in the
   14  *    documentation and/or other materials provided with the distribution.
   15  * 3. Berkeley Software Design Inc's name may not be used to endorse or
   16  *    promote products derived from this software without specific prior
   17  *    written permission.
   18  *
   19  * THIS SOFTWARE IS PROVIDED BY BERKELEY SOFTWARE DESIGN INC ``AS IS'' AND
   20  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
   21  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
   22  * ARE DISCLAIMED.  IN NO EVENT SHALL BERKELEY SOFTWARE DESIGN INC BE LIABLE
   23  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
   24  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
   25  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
   26  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
   27  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
   28  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
   29  * SUCH DAMAGE.
   30  *
   31  *      from BSDI $Id: mutex_witness.c,v 1.1.2.20 2000/04/27 03:10:27 cp Exp $
   32  *      and BSDI $Id: synch_machdep.c,v 2.3.2.39 2000/04/27 03:10:25 cp Exp $
   33  */
   34 
   35 /*
   36  * Implementation of the `witness' lock verifier.  Originally implemented for
   37  * mutexes in BSD/OS.  Extended to handle generic lock objects and lock
   38  * classes in FreeBSD.
   39  */
   40 
   41 /*
   42  *      Main Entry: witness
   43  *      Pronunciation: 'wit-n&s
   44  *      Function: noun
   45  *      Etymology: Middle English witnesse, from Old English witnes knowledge,
   46  *          testimony, witness, from 2wit
   47  *      Date: before 12th century
   48  *      1 : attestation of a fact or event : TESTIMONY
   49  *      2 : one that gives evidence; specifically : one who testifies in
   50  *          a cause or before a judicial tribunal
   51  *      3 : one asked to be present at a transaction so as to be able to
   52  *          testify to its having taken place
   53  *      4 : one who has personal knowledge of something
   54  *      5 a : something serving as evidence or proof : SIGN
   55  *        b : public affirmation by word or example of usually
   56  *            religious faith or conviction <the heroic witness to divine
   57  *            life -- Pilot>
   58  *      6 capitalized : a member of the Jehovah's Witnesses 
   59  */
   60 
   61 /*
   62  * Special rules concerning Giant and lock orders:
   63  *
   64  * 1) Giant must be acquired before any other mutexes.  Stated another way,
   65  *    no other mutex may be held when Giant is acquired.
   66  *
   67  * 2) Giant must be released when blocking on a sleepable lock.
   68  *
   69  * This rule is less obvious, but is a result of Giant providing the same
   70  * semantics as spl().  Basically, when a thread sleeps, it must release
   71  * Giant.  When a thread blocks on a sleepable lock, it sleeps.  Hence rule
   72  * 2).
   73  *
   74  * 3) Giant may be acquired before or after sleepable locks.
   75  *
   76  * This rule is also not quite as obvious.  Giant may be acquired after
   77  * a sleepable lock because it is a non-sleepable lock and non-sleepable
   78  * locks may always be acquired while holding a sleepable lock.  The second
   79  * case, Giant before a sleepable lock, follows from rule 2) above.  Suppose
   80  * you have two threads T1 and T2 and a sleepable lock X.  Suppose that T1
   81  * acquires X and blocks on Giant.  Then suppose that T2 acquires Giant and
   82  * blocks on X.  When T2 blocks on X, T2 will release Giant allowing T1 to
   83  * execute.  Thus, acquiring Giant both before and after a sleepable lock
   84  * will not result in a lock order reversal.
   85  */
   86 
   87 #include <sys/cdefs.h>
   88 __FBSDID("$FreeBSD: releng/11.0/sys/kern/subr_witness.c 298819 2016-04-29 22:15:33Z pfg $");
   89 
   90 #include "opt_ddb.h"
   91 #include "opt_hwpmc_hooks.h"
   92 #include "opt_stack.h"
   93 #include "opt_witness.h"
   94 
   95 #include <sys/param.h>
   96 #include <sys/bus.h>
   97 #include <sys/kdb.h>
   98 #include <sys/kernel.h>
   99 #include <sys/ktr.h>
  100 #include <sys/lock.h>
  101 #include <sys/malloc.h>
  102 #include <sys/mutex.h>
  103 #include <sys/priv.h>
  104 #include <sys/proc.h>
  105 #include <sys/sbuf.h>
  106 #include <sys/sched.h>
  107 #include <sys/stack.h>
  108 #include <sys/sysctl.h>
  109 #include <sys/syslog.h>
  110 #include <sys/systm.h>
  111 
  112 #ifdef DDB
  113 #include <ddb/ddb.h>
  114 #endif
  115 
  116 #include <machine/stdarg.h>
  117 
  118 #if !defined(DDB) && !defined(STACK)
  119 #error "DDB or STACK options are required for WITNESS"
  120 #endif
  121 
  122 /* Note that these traces do not work with KTR_ALQ. */
  123 #if 0
  124 #define KTR_WITNESS     KTR_SUBSYS
  125 #else
  126 #define KTR_WITNESS     0
  127 #endif
  128 
  129 #define LI_RECURSEMASK  0x0000ffff      /* Recursion depth of lock instance. */
  130 #define LI_EXCLUSIVE    0x00010000      /* Exclusive lock instance. */
  131 #define LI_NORELEASE    0x00020000      /* Lock not allowed to be released. */
  132 
  133 /* Define this to check for blessed mutexes */
  134 #undef BLESSING
  135 
  136 #ifndef WITNESS_COUNT
  137 #define WITNESS_COUNT           1536
  138 #endif
  139 #define WITNESS_HASH_SIZE       251     /* Prime, gives load factor < 2 */
  140 #define WITNESS_PENDLIST        (1024 + MAXCPU)
  141 
  142 /* Allocate 256 KB of stack data space */
  143 #define WITNESS_LO_DATA_COUNT   2048
  144 
  145 /* Prime, gives load factor of ~2 at full load */
  146 #define WITNESS_LO_HASH_SIZE    1021
  147 
  148 /*
  149  * XXX: This is somewhat bogus, as we assume here that at most 2048 threads
  150  * will hold LOCK_NCHILDREN locks.  We handle failure ok, and we should
  151  * probably be safe for the most part, but it's still a SWAG.
  152  */
  153 #define LOCK_NCHILDREN  5
  154 #define LOCK_CHILDCOUNT 2048
  155 
  156 #define MAX_W_NAME      64
  157 
  158 #define FULLGRAPH_SBUF_SIZE     512
  159 
  160 /*
  161  * These flags go in the witness relationship matrix and describe the
  162  * relationship between any two struct witness objects.
  163  */
  164 #define WITNESS_UNRELATED        0x00    /* No lock order relation. */
  165 #define WITNESS_PARENT           0x01    /* Parent, aka direct ancestor. */
  166 #define WITNESS_ANCESTOR         0x02    /* Direct or indirect ancestor. */
  167 #define WITNESS_CHILD            0x04    /* Child, aka direct descendant. */
  168 #define WITNESS_DESCENDANT       0x08    /* Direct or indirect descendant. */
  169 #define WITNESS_ANCESTOR_MASK    (WITNESS_PARENT | WITNESS_ANCESTOR)
  170 #define WITNESS_DESCENDANT_MASK  (WITNESS_CHILD | WITNESS_DESCENDANT)
  171 #define WITNESS_RELATED_MASK                                            \
  172         (WITNESS_ANCESTOR_MASK | WITNESS_DESCENDANT_MASK)
  173 #define WITNESS_REVERSAL         0x10    /* A lock order reversal has been
  174                                           * observed. */
  175 #define WITNESS_RESERVED1        0x20    /* Unused flag, reserved. */
  176 #define WITNESS_RESERVED2        0x40    /* Unused flag, reserved. */
  177 #define WITNESS_LOCK_ORDER_KNOWN 0x80    /* This lock order is known. */
  178 
  179 /* Descendant to ancestor flags */
  180 #define WITNESS_DTOA(x) (((x) & WITNESS_RELATED_MASK) >> 2)
  181 
  182 /* Ancestor to descendant flags */
  183 #define WITNESS_ATOD(x) (((x) & WITNESS_RELATED_MASK) << 2)
  184 
  185 #define WITNESS_INDEX_ASSERT(i)                                         \
  186         MPASS((i) > 0 && (i) <= w_max_used_index && (i) < witness_count)
  187 
  188 static MALLOC_DEFINE(M_WITNESS, "Witness", "Witness");
  189 
  190 /*
  191  * Lock instances.  A lock instance is the data associated with a lock while
  192  * it is held by witness.  For example, a lock instance will hold the
  193  * recursion count of a lock.  Lock instances are held in lists.  Spin locks
  194  * are held in a per-cpu list while sleep locks are held in per-thread list.
  195  */
  196 struct lock_instance {
  197         struct lock_object      *li_lock;
  198         const char              *li_file;
  199         int                     li_line;
  200         u_int                   li_flags;
  201 };
  202 
  203 /*
  204  * A simple list type used to build the list of locks held by a thread
  205  * or CPU.  We can't simply embed the list in struct lock_object since a
  206  * lock may be held by more than one thread if it is a shared lock.  Locks
  207  * are added to the head of the list, so we fill up each list entry from
  208  * "the back" logically.  To ease some of the arithmetic, we actually fill
  209  * in each list entry the normal way (children[0] then children[1], etc.) but
  210  * when we traverse the list we read children[count-1] as the first entry
  211  * down to children[0] as the final entry.
  212  */
  213 struct lock_list_entry {
  214         struct lock_list_entry  *ll_next;
  215         struct lock_instance    ll_children[LOCK_NCHILDREN];
  216         u_int                   ll_count;
  217 };
  218 
  219 /*
  220  * The main witness structure. One of these per named lock type in the system
  221  * (for example, "vnode interlock").
  222  */
  223 struct witness {
  224         char                    w_name[MAX_W_NAME];
  225         uint32_t                w_index;  /* Index in the relationship matrix */
  226         struct lock_class       *w_class;
  227         STAILQ_ENTRY(witness)   w_list;         /* List of all witnesses. */
  228         STAILQ_ENTRY(witness)   w_typelist;     /* Witnesses of a type. */
  229         struct witness          *w_hash_next; /* Linked list in hash buckets. */
  230         const char              *w_file; /* File where last acquired */
  231         uint32_t                w_line; /* Line where last acquired */
  232         uint32_t                w_refcount;
  233         uint16_t                w_num_ancestors; /* direct/indirect
  234                                                   * ancestor count */
  235         uint16_t                w_num_descendants; /* direct/indirect
  236                                                     * descendant count */
  237         int16_t                 w_ddb_level;
  238         unsigned                w_displayed:1;
  239         unsigned                w_reversed:1;
  240 };
  241 
  242 STAILQ_HEAD(witness_list, witness);
  243 
  244 /*
  245  * The witness hash table. Keys are witness names (const char *), elements are
  246  * witness objects (struct witness *).
  247  */
  248 struct witness_hash {
  249         struct witness  *wh_array[WITNESS_HASH_SIZE];
  250         uint32_t        wh_size;
  251         uint32_t        wh_count;
  252 };
  253 
  254 /*
  255  * Key type for the lock order data hash table.
  256  */
  257 struct witness_lock_order_key {
  258         uint16_t        from;
  259         uint16_t        to;
  260 };
  261 
  262 struct witness_lock_order_data {
  263         struct stack                    wlod_stack;
  264         struct witness_lock_order_key   wlod_key;
  265         struct witness_lock_order_data  *wlod_next;
  266 };
  267 
  268 /*
  269  * The witness lock order data hash table. Keys are witness index tuples
  270  * (struct witness_lock_order_key), elements are lock order data objects
  271  * (struct witness_lock_order_data). 
  272  */
  273 struct witness_lock_order_hash {
  274         struct witness_lock_order_data  *wloh_array[WITNESS_LO_HASH_SIZE];
  275         u_int   wloh_size;
  276         u_int   wloh_count;
  277 };
  278 
  279 #ifdef BLESSING
  280 struct witness_blessed {
  281         const char      *b_lock1;
  282         const char      *b_lock2;
  283 };
  284 #endif
  285 
  286 struct witness_pendhelp {
  287         const char              *wh_type;
  288         struct lock_object      *wh_lock;
  289 };
  290 
  291 struct witness_order_list_entry {
  292         const char              *w_name;
  293         struct lock_class       *w_class;
  294 };
  295 
  296 /*
  297  * Returns 0 if one of the locks is a spin lock and the other is not.
  298  * Returns 1 otherwise.
  299  */
  300 static __inline int
  301 witness_lock_type_equal(struct witness *w1, struct witness *w2)
  302 {
  303 
  304         return ((w1->w_class->lc_flags & (LC_SLEEPLOCK | LC_SPINLOCK)) ==
  305                 (w2->w_class->lc_flags & (LC_SLEEPLOCK | LC_SPINLOCK)));
  306 }
  307 
  308 static __inline int
  309 witness_lock_order_key_equal(const struct witness_lock_order_key *a,
  310     const struct witness_lock_order_key *b)
  311 {
  312 
  313         return (a->from == b->from && a->to == b->to);
  314 }
  315 
  316 static int      _isitmyx(struct witness *w1, struct witness *w2, int rmask,
  317                     const char *fname);
  318 static void     adopt(struct witness *parent, struct witness *child);
  319 #ifdef BLESSING
  320 static int      blessed(struct witness *, struct witness *);
  321 #endif
  322 static void     depart(struct witness *w);
  323 static struct witness   *enroll(const char *description,
  324                             struct lock_class *lock_class);
  325 static struct lock_instance     *find_instance(struct lock_list_entry *list,
  326                                     const struct lock_object *lock);
  327 static int      isitmychild(struct witness *parent, struct witness *child);
  328 static int      isitmydescendant(struct witness *parent, struct witness *child);
  329 static void     itismychild(struct witness *parent, struct witness *child);
  330 static int      sysctl_debug_witness_badstacks(SYSCTL_HANDLER_ARGS);
  331 static int      sysctl_debug_witness_watch(SYSCTL_HANDLER_ARGS);
  332 static int      sysctl_debug_witness_fullgraph(SYSCTL_HANDLER_ARGS);
  333 static int      sysctl_debug_witness_channel(SYSCTL_HANDLER_ARGS);
  334 static void     witness_add_fullgraph(struct sbuf *sb, struct witness *parent);
  335 #ifdef DDB
  336 static void     witness_ddb_compute_levels(void);
  337 static void     witness_ddb_display(int(*)(const char *fmt, ...));
  338 static void     witness_ddb_display_descendants(int(*)(const char *fmt, ...),
  339                     struct witness *, int indent);
  340 static void     witness_ddb_display_list(int(*prnt)(const char *fmt, ...),
  341                     struct witness_list *list);
  342 static void     witness_ddb_level_descendants(struct witness *parent, int l);
  343 static void     witness_ddb_list(struct thread *td);
  344 #endif
  345 static void     witness_debugger(int cond, const char *msg);
  346 static void     witness_free(struct witness *m);
  347 static struct witness   *witness_get(void);
  348 static uint32_t witness_hash_djb2(const uint8_t *key, uint32_t size);
  349 static struct witness   *witness_hash_get(const char *key);
  350 static void     witness_hash_put(struct witness *w);
  351 static void     witness_init_hash_tables(void);
  352 static void     witness_increment_graph_generation(void);
  353 static void     witness_lock_list_free(struct lock_list_entry *lle);
  354 static struct lock_list_entry   *witness_lock_list_get(void);
  355 static int      witness_lock_order_add(struct witness *parent,
  356                     struct witness *child);
  357 static int      witness_lock_order_check(struct witness *parent,
  358                     struct witness *child);
  359 static struct witness_lock_order_data   *witness_lock_order_get(
  360                                             struct witness *parent,
  361                                             struct witness *child);
  362 static void     witness_list_lock(struct lock_instance *instance,
  363                     int (*prnt)(const char *fmt, ...));
  364 static int      witness_output(const char *fmt, ...) __printflike(1, 2);
  365 static int      witness_voutput(const char *fmt, va_list ap) __printflike(1, 0);
  366 static void     witness_setflag(struct lock_object *lock, int flag, int set);
  367 
  368 static SYSCTL_NODE(_debug, OID_AUTO, witness, CTLFLAG_RW, NULL,
  369     "Witness Locking");
  370 
  371 /*
  372  * If set to 0, lock order checking is disabled.  If set to -1,
  373  * witness is completely disabled.  Otherwise witness performs full
  374  * lock order checking for all locks.  At runtime, lock order checking
  375  * may be toggled.  However, witness cannot be reenabled once it is
  376  * completely disabled.
  377  */
  378 static int witness_watch = 1;
  379 SYSCTL_PROC(_debug_witness, OID_AUTO, watch, CTLFLAG_RWTUN | CTLTYPE_INT, NULL, 0,
  380     sysctl_debug_witness_watch, "I", "witness is watching lock operations");
  381 
  382 #ifdef KDB
  383 /*
  384  * When KDB is enabled and witness_kdb is 1, it will cause the system
  385  * to drop into kdebug() when:
  386  *      - a lock hierarchy violation occurs
  387  *      - locks are held when going to sleep.
  388  */
  389 #ifdef WITNESS_KDB
  390 int     witness_kdb = 1;
  391 #else
  392 int     witness_kdb = 0;
  393 #endif
  394 SYSCTL_INT(_debug_witness, OID_AUTO, kdb, CTLFLAG_RWTUN, &witness_kdb, 0, "");
  395 #endif /* KDB */
  396 
  397 #if defined(DDB) || defined(KDB)
  398 /*
  399  * When DDB or KDB is enabled and witness_trace is 1, it will cause the system
  400  * to print a stack trace:
  401  *      - a lock hierarchy violation occurs
  402  *      - locks are held when going to sleep.
  403  */
  404 int     witness_trace = 1;
  405 SYSCTL_INT(_debug_witness, OID_AUTO, trace, CTLFLAG_RWTUN, &witness_trace, 0, "");
  406 #endif /* DDB || KDB */
  407 
  408 #ifdef WITNESS_SKIPSPIN
  409 int     witness_skipspin = 1;
  410 #else
  411 int     witness_skipspin = 0;
  412 #endif
  413 SYSCTL_INT(_debug_witness, OID_AUTO, skipspin, CTLFLAG_RDTUN, &witness_skipspin, 0, "");
  414 
  415 int badstack_sbuf_size;
  416 
  417 int witness_count = WITNESS_COUNT;
  418 SYSCTL_INT(_debug_witness, OID_AUTO, witness_count, CTLFLAG_RDTUN, 
  419     &witness_count, 0, "");
  420 
  421 /*
  422  * Output channel for witness messages.  By default we print to the console.
  423  */
  424 enum witness_channel {
  425         WITNESS_CONSOLE,
  426         WITNESS_LOG,
  427         WITNESS_NONE,
  428 };
  429 
  430 static enum witness_channel witness_channel = WITNESS_CONSOLE;
  431 SYSCTL_PROC(_debug_witness, OID_AUTO, output_channel, CTLTYPE_STRING |
  432     CTLFLAG_RWTUN, NULL, 0, sysctl_debug_witness_channel, "A",
  433     "Output channel for warnings");
  434 
  435 /*
  436  * Call this to print out the relations between locks.
  437  */
  438 SYSCTL_PROC(_debug_witness, OID_AUTO, fullgraph, CTLTYPE_STRING | CTLFLAG_RD,
  439     NULL, 0, sysctl_debug_witness_fullgraph, "A", "Show locks relation graphs");
  440 
  441 /*
  442  * Call this to print out the witness faulty stacks.
  443  */
  444 SYSCTL_PROC(_debug_witness, OID_AUTO, badstacks, CTLTYPE_STRING | CTLFLAG_RD,
  445     NULL, 0, sysctl_debug_witness_badstacks, "A", "Show bad witness stacks");
  446 
  447 static struct mtx w_mtx;
  448 
  449 /* w_list */
  450 static struct witness_list w_free = STAILQ_HEAD_INITIALIZER(w_free);
  451 static struct witness_list w_all = STAILQ_HEAD_INITIALIZER(w_all);
  452 
  453 /* w_typelist */
  454 static struct witness_list w_spin = STAILQ_HEAD_INITIALIZER(w_spin);
  455 static struct witness_list w_sleep = STAILQ_HEAD_INITIALIZER(w_sleep);
  456 
  457 /* lock list */
  458 static struct lock_list_entry *w_lock_list_free = NULL;
  459 static struct witness_pendhelp pending_locks[WITNESS_PENDLIST];
  460 static u_int pending_cnt;
  461 
  462 static int w_free_cnt, w_spin_cnt, w_sleep_cnt;
  463 SYSCTL_INT(_debug_witness, OID_AUTO, free_cnt, CTLFLAG_RD, &w_free_cnt, 0, "");
  464 SYSCTL_INT(_debug_witness, OID_AUTO, spin_cnt, CTLFLAG_RD, &w_spin_cnt, 0, "");
  465 SYSCTL_INT(_debug_witness, OID_AUTO, sleep_cnt, CTLFLAG_RD, &w_sleep_cnt, 0,
  466     "");
  467 
  468 static struct witness *w_data;
  469 static uint8_t **w_rmatrix;
  470 static struct lock_list_entry w_locklistdata[LOCK_CHILDCOUNT];
  471 static struct witness_hash w_hash;      /* The witness hash table. */
  472 
  473 /* The lock order data hash */
  474 static struct witness_lock_order_data w_lodata[WITNESS_LO_DATA_COUNT];
  475 static struct witness_lock_order_data *w_lofree = NULL;
  476 static struct witness_lock_order_hash w_lohash;
  477 static int w_max_used_index = 0;
  478 static unsigned int w_generation = 0;
  479 static const char w_notrunning[] = "Witness not running\n";
  480 static const char w_stillcold[] = "Witness is still cold\n";
  481 
  482 
  483 static struct witness_order_list_entry order_lists[] = {
  484         /*
  485          * sx locks
  486          */
  487         { "proctree", &lock_class_sx },
  488         { "allproc", &lock_class_sx },
  489         { "allprison", &lock_class_sx },
  490         { NULL, NULL },
  491         /*
  492          * Various mutexes
  493          */
  494         { "Giant", &lock_class_mtx_sleep },
  495         { "pipe mutex", &lock_class_mtx_sleep },
  496         { "sigio lock", &lock_class_mtx_sleep },
  497         { "process group", &lock_class_mtx_sleep },
  498         { "process lock", &lock_class_mtx_sleep },
  499         { "session", &lock_class_mtx_sleep },
  500         { "uidinfo hash", &lock_class_rw },
  501 #ifdef  HWPMC_HOOKS
  502         { "pmc-sleep", &lock_class_mtx_sleep },
  503 #endif
  504         { "time lock", &lock_class_mtx_sleep },
  505         { NULL, NULL },
  506         /*
  507          * umtx
  508          */
  509         { "umtx lock", &lock_class_mtx_sleep },
  510         { NULL, NULL },
  511         /*
  512          * Sockets
  513          */
  514         { "accept", &lock_class_mtx_sleep },
  515         { "so_snd", &lock_class_mtx_sleep },
  516         { "so_rcv", &lock_class_mtx_sleep },
  517         { "sellck", &lock_class_mtx_sleep },
  518         { NULL, NULL },
  519         /*
  520          * Routing
  521          */
  522         { "so_rcv", &lock_class_mtx_sleep },
  523         { "radix node head", &lock_class_rw },
  524         { "rtentry", &lock_class_mtx_sleep },
  525         { "ifaddr", &lock_class_mtx_sleep },
  526         { NULL, NULL },
  527         /*
  528          * IPv4 multicast:
  529          * protocol locks before interface locks, after UDP locks.
  530          */
  531         { "udpinp", &lock_class_rw },
  532         { "in_multi_mtx", &lock_class_mtx_sleep },
  533         { "igmp_mtx", &lock_class_mtx_sleep },
  534         { "if_addr_lock", &lock_class_rw },
  535         { NULL, NULL },
  536         /*
  537          * IPv6 multicast:
  538          * protocol locks before interface locks, after UDP locks.
  539          */
  540         { "udpinp", &lock_class_rw },
  541         { "in6_multi_mtx", &lock_class_mtx_sleep },
  542         { "mld_mtx", &lock_class_mtx_sleep },
  543         { "if_addr_lock", &lock_class_rw },
  544         { NULL, NULL },
  545         /*
  546          * UNIX Domain Sockets
  547          */
  548         { "unp_link_rwlock", &lock_class_rw },
  549         { "unp_list_lock", &lock_class_mtx_sleep },
  550         { "unp", &lock_class_mtx_sleep },
  551         { "so_snd", &lock_class_mtx_sleep },
  552         { NULL, NULL },
  553         /*
  554          * UDP/IP
  555          */
  556         { "udp", &lock_class_rw },
  557         { "udpinp", &lock_class_rw },
  558         { "so_snd", &lock_class_mtx_sleep },
  559         { NULL, NULL },
  560         /*
  561          * TCP/IP
  562          */
  563         { "tcp", &lock_class_rw },
  564         { "tcpinp", &lock_class_rw },
  565         { "so_snd", &lock_class_mtx_sleep },
  566         { NULL, NULL },
  567         /*
  568          * BPF
  569          */
  570         { "bpf global lock", &lock_class_mtx_sleep },
  571         { "bpf interface lock", &lock_class_rw },
  572         { "bpf cdev lock", &lock_class_mtx_sleep },
  573         { NULL, NULL },
  574         /*
  575          * NFS server
  576          */
  577         { "nfsd_mtx", &lock_class_mtx_sleep },
  578         { "so_snd", &lock_class_mtx_sleep },
  579         { NULL, NULL },
  580 
  581         /*
  582          * IEEE 802.11
  583          */
  584         { "802.11 com lock", &lock_class_mtx_sleep},
  585         { NULL, NULL },
  586         /*
  587          * Network drivers
  588          */
  589         { "network driver", &lock_class_mtx_sleep},
  590         { NULL, NULL },
  591 
  592         /*
  593          * Netgraph
  594          */
  595         { "ng_node", &lock_class_mtx_sleep },
  596         { "ng_worklist", &lock_class_mtx_sleep },
  597         { NULL, NULL },
  598         /*
  599          * CDEV
  600          */
  601         { "vm map (system)", &lock_class_mtx_sleep },
  602         { "vm page queue", &lock_class_mtx_sleep },
  603         { "vnode interlock", &lock_class_mtx_sleep },
  604         { "cdev", &lock_class_mtx_sleep },
  605         { NULL, NULL },
  606         /*
  607          * VM
  608          */
  609         { "vm map (user)", &lock_class_sx },
  610         { "vm object", &lock_class_rw },
  611         { "vm page", &lock_class_mtx_sleep },
  612         { "vm page queue", &lock_class_mtx_sleep },
  613         { "pmap pv global", &lock_class_rw },
  614         { "pmap", &lock_class_mtx_sleep },
  615         { "pmap pv list", &lock_class_rw },
  616         { "vm page free queue", &lock_class_mtx_sleep },
  617         { NULL, NULL },
  618         /*
  619          * kqueue/VFS interaction
  620          */
  621         { "kqueue", &lock_class_mtx_sleep },
  622         { "struct mount mtx", &lock_class_mtx_sleep },
  623         { "vnode interlock", &lock_class_mtx_sleep },
  624         { NULL, NULL },
  625         /*
  626          * ZFS locking
  627          */
  628         { "dn->dn_mtx", &lock_class_sx },
  629         { "dr->dt.di.dr_mtx", &lock_class_sx },
  630         { "db->db_mtx", &lock_class_sx },
  631         { NULL, NULL },
  632         /*
  633          * spin locks
  634          */
  635 #ifdef SMP
  636         { "ap boot", &lock_class_mtx_spin },
  637 #endif
  638         { "rm.mutex_mtx", &lock_class_mtx_spin },
  639         { "sio", &lock_class_mtx_spin },
  640         { "scrlock", &lock_class_mtx_spin },
  641 #ifdef __i386__
  642         { "cy", &lock_class_mtx_spin },
  643 #endif
  644 #ifdef __sparc64__
  645         { "pcib_mtx", &lock_class_mtx_spin },
  646         { "rtc_mtx", &lock_class_mtx_spin },
  647 #endif
  648         { "scc_hwmtx", &lock_class_mtx_spin },
  649         { "uart_hwmtx", &lock_class_mtx_spin },
  650         { "fast_taskqueue", &lock_class_mtx_spin },
  651         { "intr table", &lock_class_mtx_spin },
  652 #ifdef  HWPMC_HOOKS
  653         { "pmc-per-proc", &lock_class_mtx_spin },
  654 #endif
  655         { "process slock", &lock_class_mtx_spin },
  656         { "sleepq chain", &lock_class_mtx_spin },
  657         { "rm_spinlock", &lock_class_mtx_spin },
  658         { "turnstile chain", &lock_class_mtx_spin },
  659         { "turnstile lock", &lock_class_mtx_spin },
  660         { "sched lock", &lock_class_mtx_spin },
  661         { "td_contested", &lock_class_mtx_spin },
  662         { "callout", &lock_class_mtx_spin },
  663         { "entropy harvest mutex", &lock_class_mtx_spin },
  664         { "syscons video lock", &lock_class_mtx_spin },
  665 #ifdef SMP
  666         { "smp rendezvous", &lock_class_mtx_spin },
  667 #endif
  668 #ifdef __powerpc__
  669         { "tlb0", &lock_class_mtx_spin },
  670 #endif
  671         /*
  672          * leaf locks
  673          */
  674         { "intrcnt", &lock_class_mtx_spin },
  675         { "icu", &lock_class_mtx_spin },
  676 #if defined(SMP) && defined(__sparc64__)
  677         { "ipi", &lock_class_mtx_spin },
  678 #endif
  679 #ifdef __i386__
  680         { "allpmaps", &lock_class_mtx_spin },
  681         { "descriptor tables", &lock_class_mtx_spin },
  682 #endif
  683         { "clk", &lock_class_mtx_spin },
  684         { "cpuset", &lock_class_mtx_spin },
  685         { "mprof lock", &lock_class_mtx_spin },
  686         { "zombie lock", &lock_class_mtx_spin },
  687         { "ALD Queue", &lock_class_mtx_spin },
  688 #if defined(__i386__) || defined(__amd64__)
  689         { "pcicfg", &lock_class_mtx_spin },
  690         { "NDIS thread lock", &lock_class_mtx_spin },
  691 #endif
  692         { "tw_osl_io_lock", &lock_class_mtx_spin },
  693         { "tw_osl_q_lock", &lock_class_mtx_spin },
  694         { "tw_cl_io_lock", &lock_class_mtx_spin },
  695         { "tw_cl_intr_lock", &lock_class_mtx_spin },
  696         { "tw_cl_gen_lock", &lock_class_mtx_spin },
  697 #ifdef  HWPMC_HOOKS
  698         { "pmc-leaf", &lock_class_mtx_spin },
  699 #endif
  700         { "blocked lock", &lock_class_mtx_spin },
  701         { NULL, NULL },
  702         { NULL, NULL }
  703 };
  704 
  705 #ifdef BLESSING
  706 /*
  707  * Pairs of locks which have been blessed
  708  * Don't complain about order problems with blessed locks
  709  */
  710 static struct witness_blessed blessed_list[] = {
  711 };
  712 #endif
  713 
  714 /*
  715  * This global is set to 0 once it becomes safe to use the witness code.
  716  */
  717 static int witness_cold = 1;
  718 
  719 /*
  720  * This global is set to 1 once the static lock orders have been enrolled
  721  * so that a warning can be issued for any spin locks enrolled later.
  722  */
  723 static int witness_spin_warn = 0;
  724 
  725 /* Trim useless garbage from filenames. */
  726 static const char *
  727 fixup_filename(const char *file)
  728 {
  729 
  730         if (file == NULL)
  731                 return (NULL);
  732         while (strncmp(file, "../", 3) == 0)
  733                 file += 3;
  734         return (file);
  735 }
  736 
  737 /*
  738  * The WITNESS-enabled diagnostic code.  Note that the witness code does
  739  * assume that the early boot is single-threaded at least until after this
  740  * routine is completed.
  741  */
  742 static void
  743 witness_initialize(void *dummy __unused)
  744 {
  745         struct lock_object *lock;
  746         struct witness_order_list_entry *order;
  747         struct witness *w, *w1;
  748         int i;
  749 
  750         w_data = malloc(sizeof (struct witness) * witness_count, M_WITNESS,
  751             M_WAITOK | M_ZERO);
  752 
  753         w_rmatrix = malloc(sizeof(*w_rmatrix) * (witness_count + 1),
  754             M_WITNESS, M_WAITOK | M_ZERO);
  755 
  756         for (i = 0; i < witness_count + 1; i++) {
  757                 w_rmatrix[i] = malloc(sizeof(*w_rmatrix[i]) *
  758                     (witness_count + 1), M_WITNESS, M_WAITOK | M_ZERO);
  759         }
  760         badstack_sbuf_size = witness_count * 256;
  761 
  762         /*
  763          * We have to release Giant before initializing its witness
  764          * structure so that WITNESS doesn't get confused.
  765          */
  766         mtx_unlock(&Giant);
  767         mtx_assert(&Giant, MA_NOTOWNED);
  768 
  769         CTR1(KTR_WITNESS, "%s: initializing witness", __func__);
  770         mtx_init(&w_mtx, "witness lock", NULL, MTX_SPIN | MTX_QUIET |
  771             MTX_NOWITNESS | MTX_NOPROFILE);
  772         for (i = witness_count - 1; i >= 0; i--) {
  773                 w = &w_data[i];
  774                 memset(w, 0, sizeof(*w));
  775                 w_data[i].w_index = i;  /* Witness index never changes. */
  776                 witness_free(w);
  777         }
  778         KASSERT(STAILQ_FIRST(&w_free)->w_index == 0,
  779             ("%s: Invalid list of free witness objects", __func__));
  780 
  781         /* Witness with index 0 is not used to aid in debugging. */
  782         STAILQ_REMOVE_HEAD(&w_free, w_list);
  783         w_free_cnt--;
  784 
  785         for (i = 0; i < witness_count; i++) {
  786                 memset(w_rmatrix[i], 0, sizeof(*w_rmatrix[i]) * 
  787                     (witness_count + 1));
  788         }
  789 
  790         for (i = 0; i < LOCK_CHILDCOUNT; i++)
  791                 witness_lock_list_free(&w_locklistdata[i]);
  792         witness_init_hash_tables();
  793 
  794         /* First add in all the specified order lists. */
  795         for (order = order_lists; order->w_name != NULL; order++) {
  796                 w = enroll(order->w_name, order->w_class);
  797                 if (w == NULL)
  798                         continue;
  799                 w->w_file = "order list";
  800                 for (order++; order->w_name != NULL; order++) {
  801                         w1 = enroll(order->w_name, order->w_class);
  802                         if (w1 == NULL)
  803                                 continue;
  804                         w1->w_file = "order list";
  805                         itismychild(w, w1);
  806                         w = w1;
  807                 }
  808         }
  809         witness_spin_warn = 1;
  810 
  811         /* Iterate through all locks and add them to witness. */
  812         for (i = 0; pending_locks[i].wh_lock != NULL; i++) {
  813                 lock = pending_locks[i].wh_lock;
  814                 KASSERT(lock->lo_flags & LO_WITNESS,
  815                     ("%s: lock %s is on pending list but not LO_WITNESS",
  816                     __func__, lock->lo_name));
  817                 lock->lo_witness = enroll(pending_locks[i].wh_type,
  818                     LOCK_CLASS(lock));
  819         }
  820 
  821         /* Mark the witness code as being ready for use. */
  822         witness_cold = 0;
  823 
  824         mtx_lock(&Giant);
  825 }
  826 SYSINIT(witness_init, SI_SUB_WITNESS, SI_ORDER_FIRST, witness_initialize,
  827     NULL);
  828 
  829 void
  830 witness_init(struct lock_object *lock, const char *type)
  831 {
  832         struct lock_class *class;
  833 
  834         /* Various sanity checks. */
  835         class = LOCK_CLASS(lock);
  836         if ((lock->lo_flags & LO_RECURSABLE) != 0 &&
  837             (class->lc_flags & LC_RECURSABLE) == 0)
  838                 kassert_panic("%s: lock (%s) %s can not be recursable",
  839                     __func__, class->lc_name, lock->lo_name);
  840         if ((lock->lo_flags & LO_SLEEPABLE) != 0 &&
  841             (class->lc_flags & LC_SLEEPABLE) == 0)
  842                 kassert_panic("%s: lock (%s) %s can not be sleepable",
  843                     __func__, class->lc_name, lock->lo_name);
  844         if ((lock->lo_flags & LO_UPGRADABLE) != 0 &&
  845             (class->lc_flags & LC_UPGRADABLE) == 0)
  846                 kassert_panic("%s: lock (%s) %s can not be upgradable",
  847                     __func__, class->lc_name, lock->lo_name);
  848 
  849         /*
  850          * If we shouldn't watch this lock, then just clear lo_witness.
  851          * Otherwise, if witness_cold is set, then it is too early to
  852          * enroll this lock, so defer it to witness_initialize() by adding
  853          * it to the pending_locks list.  If it is not too early, then enroll
  854          * the lock now.
  855          */
  856         if (witness_watch < 1 || panicstr != NULL ||
  857             (lock->lo_flags & LO_WITNESS) == 0)
  858                 lock->lo_witness = NULL;
  859         else if (witness_cold) {
  860                 pending_locks[pending_cnt].wh_lock = lock;
  861                 pending_locks[pending_cnt++].wh_type = type;
  862                 if (pending_cnt > WITNESS_PENDLIST)
  863                         panic("%s: pending locks list is too small, "
  864                             "increase WITNESS_PENDLIST\n",
  865                             __func__);
  866         } else
  867                 lock->lo_witness = enroll(type, class);
  868 }
  869 
  870 void
  871 witness_destroy(struct lock_object *lock)
  872 {
  873         struct lock_class *class;
  874         struct witness *w;
  875 
  876         class = LOCK_CLASS(lock);
  877 
  878         if (witness_cold)
  879                 panic("lock (%s) %s destroyed while witness_cold",
  880                     class->lc_name, lock->lo_name);
  881 
  882         /* XXX: need to verify that no one holds the lock */
  883         if ((lock->lo_flags & LO_WITNESS) == 0 || lock->lo_witness == NULL)
  884                 return;
  885         w = lock->lo_witness;
  886 
  887         mtx_lock_spin(&w_mtx);
  888         MPASS(w->w_refcount > 0);
  889         w->w_refcount--;
  890 
  891         if (w->w_refcount == 0)
  892                 depart(w);
  893         mtx_unlock_spin(&w_mtx);
  894 }
  895 
  896 #ifdef DDB
  897 static void
  898 witness_ddb_compute_levels(void)
  899 {
  900         struct witness *w;
  901 
  902         /*
  903          * First clear all levels.
  904          */
  905         STAILQ_FOREACH(w, &w_all, w_list)
  906                 w->w_ddb_level = -1;
  907 
  908         /*
  909          * Look for locks with no parents and level all their descendants.
  910          */
  911         STAILQ_FOREACH(w, &w_all, w_list) {
  912 
  913                 /* If the witness has ancestors (is not a root), skip it. */
  914                 if (w->w_num_ancestors > 0)
  915                         continue;
  916                 witness_ddb_level_descendants(w, 0);
  917         }
  918 }
  919 
  920 static void
  921 witness_ddb_level_descendants(struct witness *w, int l)
  922 {
  923         int i;
  924 
  925         if (w->w_ddb_level >= l)
  926                 return;
  927 
  928         w->w_ddb_level = l;
  929         l++;
  930 
  931         for (i = 1; i <= w_max_used_index; i++) {
  932                 if (w_rmatrix[w->w_index][i] & WITNESS_PARENT)
  933                         witness_ddb_level_descendants(&w_data[i], l);
  934         }
  935 }
  936 
  937 static void
  938 witness_ddb_display_descendants(int(*prnt)(const char *fmt, ...),
  939     struct witness *w, int indent)
  940 {
  941         int i;
  942 
  943         for (i = 0; i < indent; i++)
  944                 prnt(" ");
  945         prnt("%s (type: %s, depth: %d, active refs: %d)",
  946              w->w_name, w->w_class->lc_name,
  947              w->w_ddb_level, w->w_refcount);
  948         if (w->w_displayed) {
  949                 prnt(" -- (already displayed)\n");
  950                 return;
  951         }
  952         w->w_displayed = 1;
  953         if (w->w_file != NULL && w->w_line != 0)
  954                 prnt(" -- last acquired @ %s:%d\n", fixup_filename(w->w_file),
  955                     w->w_line);
  956         else
  957                 prnt(" -- never acquired\n");
  958         indent++;
  959         WITNESS_INDEX_ASSERT(w->w_index);
  960         for (i = 1; i <= w_max_used_index; i++) {
  961                 if (db_pager_quit)
  962                         return;
  963                 if (w_rmatrix[w->w_index][i] & WITNESS_PARENT)
  964                         witness_ddb_display_descendants(prnt, &w_data[i],
  965                             indent);
  966         }
  967 }
  968 
  969 static void
  970 witness_ddb_display_list(int(*prnt)(const char *fmt, ...),
  971     struct witness_list *list)
  972 {
  973         struct witness *w;
  974 
  975         STAILQ_FOREACH(w, list, w_typelist) {
  976                 if (w->w_file == NULL || w->w_ddb_level > 0)
  977                         continue;
  978 
  979                 /* This lock has no anscestors - display its descendants. */
  980                 witness_ddb_display_descendants(prnt, w, 0);
  981                 if (db_pager_quit)
  982                         return;
  983         }
  984 }
  985         
  986 static void
  987 witness_ddb_display(int(*prnt)(const char *fmt, ...))
  988 {
  989         struct witness *w;
  990 
  991         KASSERT(witness_cold == 0, ("%s: witness_cold", __func__));
  992         witness_ddb_compute_levels();
  993 
  994         /* Clear all the displayed flags. */
  995         STAILQ_FOREACH(w, &w_all, w_list)
  996                 w->w_displayed = 0;
  997 
  998         /*
  999          * First, handle sleep locks which have been acquired at least
 1000          * once.
 1001          */
 1002         prnt("Sleep locks:\n");
 1003         witness_ddb_display_list(prnt, &w_sleep);
 1004         if (db_pager_quit)
 1005                 return;
 1006         
 1007         /*
 1008          * Now do spin locks which have been acquired at least once.
 1009          */
 1010         prnt("\nSpin locks:\n");
 1011         witness_ddb_display_list(prnt, &w_spin);
 1012         if (db_pager_quit)
 1013                 return;
 1014         
 1015         /*
 1016          * Finally, any locks which have not been acquired yet.
 1017          */
 1018         prnt("\nLocks which were never acquired:\n");
 1019         STAILQ_FOREACH(w, &w_all, w_list) {
 1020                 if (w->w_file != NULL || w->w_refcount == 0)
 1021                         continue;
 1022                 prnt("%s (type: %s, depth: %d)\n", w->w_name,
 1023                     w->w_class->lc_name, w->w_ddb_level);
 1024                 if (db_pager_quit)
 1025                         return;
 1026         }
 1027 }
 1028 #endif /* DDB */
 1029 
 1030 int
 1031 witness_defineorder(struct lock_object *lock1, struct lock_object *lock2)
 1032 {
 1033 
 1034         if (witness_watch == -1 || panicstr != NULL)
 1035                 return (0);
 1036 
 1037         /* Require locks that witness knows about. */
 1038         if (lock1 == NULL || lock1->lo_witness == NULL || lock2 == NULL ||
 1039             lock2->lo_witness == NULL)
 1040                 return (EINVAL);
 1041 
 1042         mtx_assert(&w_mtx, MA_NOTOWNED);
 1043         mtx_lock_spin(&w_mtx);
 1044 
 1045         /*
 1046          * If we already have either an explicit or implied lock order that
 1047          * is the other way around, then return an error.
 1048          */
 1049         if (witness_watch &&
 1050             isitmydescendant(lock2->lo_witness, lock1->lo_witness)) {
 1051                 mtx_unlock_spin(&w_mtx);
 1052                 return (EDOOFUS);
 1053         }
 1054         
 1055         /* Try to add the new order. */
 1056         CTR3(KTR_WITNESS, "%s: adding %s as a child of %s", __func__,
 1057             lock2->lo_witness->w_name, lock1->lo_witness->w_name);
 1058         itismychild(lock1->lo_witness, lock2->lo_witness);
 1059         mtx_unlock_spin(&w_mtx);
 1060         return (0);
 1061 }
 1062 
 1063 void
 1064 witness_checkorder(struct lock_object *lock, int flags, const char *file,
 1065     int line, struct lock_object *interlock)
 1066 {
 1067         struct lock_list_entry *lock_list, *lle;
 1068         struct lock_instance *lock1, *lock2, *plock;
 1069         struct lock_class *class, *iclass;
 1070         struct witness *w, *w1;
 1071         struct thread *td;
 1072         int i, j;
 1073 
 1074         if (witness_cold || witness_watch < 1 || lock->lo_witness == NULL ||
 1075             panicstr != NULL)
 1076                 return;
 1077 
 1078         w = lock->lo_witness;
 1079         class = LOCK_CLASS(lock);
 1080         td = curthread;
 1081 
 1082         if (class->lc_flags & LC_SLEEPLOCK) {
 1083 
 1084                 /*
 1085                  * Since spin locks include a critical section, this check
 1086                  * implicitly enforces a lock order of all sleep locks before
 1087                  * all spin locks.
 1088                  */
 1089                 if (td->td_critnest != 0 && !kdb_active)
 1090                         kassert_panic("acquiring blockable sleep lock with "
 1091                             "spinlock or critical section held (%s) %s @ %s:%d",
 1092                             class->lc_name, lock->lo_name,
 1093                             fixup_filename(file), line);
 1094 
 1095                 /*
 1096                  * If this is the first lock acquired then just return as
 1097                  * no order checking is needed.
 1098                  */
 1099                 lock_list = td->td_sleeplocks;
 1100                 if (lock_list == NULL || lock_list->ll_count == 0)
 1101                         return;
 1102         } else {
 1103 
 1104                 /*
 1105                  * If this is the first lock, just return as no order
 1106                  * checking is needed.  Avoid problems with thread
 1107                  * migration pinning the thread while checking if
 1108                  * spinlocks are held.  If at least one spinlock is held
 1109                  * the thread is in a safe path and it is allowed to
 1110                  * unpin it.
 1111                  */
 1112                 sched_pin();
 1113                 lock_list = PCPU_GET(spinlocks);
 1114                 if (lock_list == NULL || lock_list->ll_count == 0) {
 1115                         sched_unpin();
 1116                         return;
 1117                 }
 1118                 sched_unpin();
 1119         }
 1120 
 1121         /*
 1122          * Check to see if we are recursing on a lock we already own.  If
 1123          * so, make sure that we don't mismatch exclusive and shared lock
 1124          * acquires.
 1125          */
 1126         lock1 = find_instance(lock_list, lock);
 1127         if (lock1 != NULL) {
 1128                 if ((lock1->li_flags & LI_EXCLUSIVE) != 0 &&
 1129                     (flags & LOP_EXCLUSIVE) == 0) {
 1130                         witness_output("shared lock of (%s) %s @ %s:%d\n",
 1131                             class->lc_name, lock->lo_name,
 1132                             fixup_filename(file), line);
 1133                         witness_output("while exclusively locked from %s:%d\n",
 1134                             fixup_filename(lock1->li_file), lock1->li_line);
 1135                         kassert_panic("excl->share");
 1136                 }
 1137                 if ((lock1->li_flags & LI_EXCLUSIVE) == 0 &&
 1138                     (flags & LOP_EXCLUSIVE) != 0) {
 1139                         witness_output("exclusive lock of (%s) %s @ %s:%d\n",
 1140                             class->lc_name, lock->lo_name,
 1141                             fixup_filename(file), line);
 1142                         witness_output("while share locked from %s:%d\n",
 1143                             fixup_filename(lock1->li_file), lock1->li_line);
 1144                         kassert_panic("share->excl");
 1145                 }
 1146                 return;
 1147         }
 1148 
 1149         /* Warn if the interlock is not locked exactly once. */
 1150         if (interlock != NULL) {
 1151                 iclass = LOCK_CLASS(interlock);
 1152                 lock1 = find_instance(lock_list, interlock);
 1153                 if (lock1 == NULL)
 1154                         kassert_panic("interlock (%s) %s not locked @ %s:%d",
 1155                             iclass->lc_name, interlock->lo_name,
 1156                             fixup_filename(file), line);
 1157                 else if ((lock1->li_flags & LI_RECURSEMASK) != 0)
 1158                         kassert_panic("interlock (%s) %s recursed @ %s:%d",
 1159                             iclass->lc_name, interlock->lo_name,
 1160                             fixup_filename(file), line);
 1161         }
 1162 
 1163         /*
 1164          * Find the previously acquired lock, but ignore interlocks.
 1165          */
 1166         plock = &lock_list->ll_children[lock_list->ll_count - 1];
 1167         if (interlock != NULL && plock->li_lock == interlock) {
 1168                 if (lock_list->ll_count > 1)
 1169                         plock =
 1170                             &lock_list->ll_children[lock_list->ll_count - 2];
 1171                 else {
 1172                         lle = lock_list->ll_next;
 1173 
 1174                         /*
 1175                          * The interlock is the only lock we hold, so
 1176                          * simply return.
 1177                          */
 1178                         if (lle == NULL)
 1179                                 return;
 1180                         plock = &lle->ll_children[lle->ll_count - 1];
 1181                 }
 1182         }
 1183         
 1184         /*
 1185          * Try to perform most checks without a lock.  If this succeeds we
 1186          * can skip acquiring the lock and return success.  Otherwise we redo
 1187          * the check with the lock held to handle races with concurrent updates.
 1188          */
 1189         w1 = plock->li_lock->lo_witness;
 1190         if (witness_lock_order_check(w1, w))
 1191                 return;
 1192 
 1193         mtx_lock_spin(&w_mtx);
 1194         if (witness_lock_order_check(w1, w)) {
 1195                 mtx_unlock_spin(&w_mtx);
 1196                 return;
 1197         }
 1198         witness_lock_order_add(w1, w);
 1199 
 1200         /*
 1201          * Check for duplicate locks of the same type.  Note that we only
 1202          * have to check for this on the last lock we just acquired.  Any
 1203          * other cases will be caught as lock order violations.
 1204          */
 1205         if (w1 == w) {
 1206                 i = w->w_index;
 1207                 if (!(lock->lo_flags & LO_DUPOK) && !(flags & LOP_DUPOK) &&
 1208                     !(w_rmatrix[i][i] & WITNESS_REVERSAL)) {
 1209                     w_rmatrix[i][i] |= WITNESS_REVERSAL;
 1210                         w->w_reversed = 1;
 1211                         mtx_unlock_spin(&w_mtx);
 1212                         witness_output(
 1213                             "acquiring duplicate lock of same type: \"%s\"\n", 
 1214                             w->w_name);
 1215                         witness_output(" 1st %s @ %s:%d\n", plock->li_lock->lo_name,
 1216                             fixup_filename(plock->li_file), plock->li_line);
 1217                         witness_output(" 2nd %s @ %s:%d\n", lock->lo_name,
 1218                             fixup_filename(file), line);
 1219                         witness_debugger(1, __func__);
 1220                 } else
 1221                         mtx_unlock_spin(&w_mtx);
 1222                 return;
 1223         }
 1224         mtx_assert(&w_mtx, MA_OWNED);
 1225 
 1226         /*
 1227          * If we know that the lock we are acquiring comes after
 1228          * the lock we most recently acquired in the lock order tree,
 1229          * then there is no need for any further checks.
 1230          */
 1231         if (isitmychild(w1, w))
 1232                 goto out;
 1233 
 1234         for (j = 0, lle = lock_list; lle != NULL; lle = lle->ll_next) {
 1235                 for (i = lle->ll_count - 1; i >= 0; i--, j++) {
 1236 
 1237                         MPASS(j < LOCK_CHILDCOUNT * LOCK_NCHILDREN);
 1238                         lock1 = &lle->ll_children[i];
 1239 
 1240                         /*
 1241                          * Ignore the interlock.
 1242                          */
 1243                         if (interlock == lock1->li_lock)
 1244                                 continue;
 1245 
 1246                         /*
 1247                          * If this lock doesn't undergo witness checking,
 1248                          * then skip it.
 1249                          */
 1250                         w1 = lock1->li_lock->lo_witness;
 1251                         if (w1 == NULL) {
 1252                                 KASSERT((lock1->li_lock->lo_flags & LO_WITNESS) == 0,
 1253                                     ("lock missing witness structure"));
 1254                                 continue;
 1255                         }
 1256 
 1257                         /*
 1258                          * If we are locking Giant and this is a sleepable
 1259                          * lock, then skip it.
 1260                          */
 1261                         if ((lock1->li_lock->lo_flags & LO_SLEEPABLE) != 0 &&
 1262                             lock == &Giant.lock_object)
 1263                                 continue;
 1264 
 1265                         /*
 1266                          * If we are locking a sleepable lock and this lock
 1267                          * is Giant, then skip it.
 1268                          */
 1269                         if ((lock->lo_flags & LO_SLEEPABLE) != 0 &&
 1270                             lock1->li_lock == &Giant.lock_object)
 1271                                 continue;
 1272 
 1273                         /*
 1274                          * If we are locking a sleepable lock and this lock
 1275                          * isn't sleepable, we want to treat it as a lock
 1276                          * order violation to enfore a general lock order of
 1277                          * sleepable locks before non-sleepable locks.
 1278                          */
 1279                         if (((lock->lo_flags & LO_SLEEPABLE) != 0 &&
 1280                             (lock1->li_lock->lo_flags & LO_SLEEPABLE) == 0))
 1281                                 goto reversal;
 1282 
 1283                         /*
 1284                          * If we are locking Giant and this is a non-sleepable
 1285                          * lock, then treat it as a reversal.
 1286                          */
 1287                         if ((lock1->li_lock->lo_flags & LO_SLEEPABLE) == 0 &&
 1288                             lock == &Giant.lock_object)
 1289                                 goto reversal;
 1290 
 1291                         /*
 1292                          * Check the lock order hierarchy for a reveresal.
 1293                          */
 1294                         if (!isitmydescendant(w, w1))
 1295                                 continue;
 1296                 reversal:
 1297 
 1298                         /*
 1299                          * We have a lock order violation, check to see if it
 1300                          * is allowed or has already been yelled about.
 1301                          */
 1302 #ifdef BLESSING
 1303 
 1304                         /*
 1305                          * If the lock order is blessed, just bail.  We don't
 1306                          * look for other lock order violations though, which
 1307                          * may be a bug.
 1308                          */
 1309                         if (blessed(w, w1))
 1310                                 goto out;
 1311 #endif
 1312 
 1313                         /* Bail if this violation is known */
 1314                         if (w_rmatrix[w1->w_index][w->w_index] & WITNESS_REVERSAL)
 1315                                 goto out;
 1316 
 1317                         /* Record this as a violation */
 1318                         w_rmatrix[w1->w_index][w->w_index] |= WITNESS_REVERSAL;
 1319                         w_rmatrix[w->w_index][w1->w_index] |= WITNESS_REVERSAL;
 1320                         w->w_reversed = w1->w_reversed = 1;
 1321                         witness_increment_graph_generation();
 1322                         mtx_unlock_spin(&w_mtx);
 1323 
 1324 #ifdef WITNESS_NO_VNODE
 1325                         /*
 1326                          * There are known LORs between VNODE locks. They are
 1327                          * not an indication of a bug. VNODE locks are flagged
 1328                          * as such (LO_IS_VNODE) and we don't yell if the LOR
 1329                          * is between 2 VNODE locks.
 1330                          */
 1331                         if ((lock->lo_flags & LO_IS_VNODE) != 0 &&
 1332                             (lock1->li_lock->lo_flags & LO_IS_VNODE) != 0)
 1333                                 return;
 1334 #endif
 1335 
 1336                         /*
 1337                          * Ok, yell about it.
 1338                          */
 1339                         if (((lock->lo_flags & LO_SLEEPABLE) != 0 &&
 1340                             (lock1->li_lock->lo_flags & LO_SLEEPABLE) == 0))
 1341                                 witness_output(
 1342                 "lock order reversal: (sleepable after non-sleepable)\n");
 1343                         else if ((lock1->li_lock->lo_flags & LO_SLEEPABLE) == 0
 1344                             && lock == &Giant.lock_object)
 1345                                 witness_output(
 1346                 "lock order reversal: (Giant after non-sleepable)\n");
 1347                         else
 1348                                 witness_output("lock order reversal:\n");
 1349 
 1350                         /*
 1351                          * Try to locate an earlier lock with
 1352                          * witness w in our list.
 1353                          */
 1354                         do {
 1355                                 lock2 = &lle->ll_children[i];
 1356                                 MPASS(lock2->li_lock != NULL);
 1357                                 if (lock2->li_lock->lo_witness == w)
 1358                                         break;
 1359                                 if (i == 0 && lle->ll_next != NULL) {
 1360                                         lle = lle->ll_next;
 1361                                         i = lle->ll_count - 1;
 1362                                         MPASS(i >= 0 && i < LOCK_NCHILDREN);
 1363                                 } else
 1364                                         i--;
 1365                         } while (i >= 0);
 1366                         if (i < 0) {
 1367                                 witness_output(" 1st %p %s (%s) @ %s:%d\n",
 1368                                     lock1->li_lock, lock1->li_lock->lo_name,
 1369                                     w1->w_name, fixup_filename(lock1->li_file),
 1370                                     lock1->li_line);
 1371                                 witness_output(" 2nd %p %s (%s) @ %s:%d\n", lock,
 1372                                     lock->lo_name, w->w_name,
 1373                                     fixup_filename(file), line);
 1374                         } else {
 1375                                 witness_output(" 1st %p %s (%s) @ %s:%d\n",
 1376                                     lock2->li_lock, lock2->li_lock->lo_name,
 1377                                     lock2->li_lock->lo_witness->w_name,
 1378                                     fixup_filename(lock2->li_file),
 1379                                     lock2->li_line);
 1380                                 witness_output(" 2nd %p %s (%s) @ %s:%d\n",
 1381                                     lock1->li_lock, lock1->li_lock->lo_name,
 1382                                     w1->w_name, fixup_filename(lock1->li_file),
 1383                                     lock1->li_line);
 1384                                 witness_output(" 3rd %p %s (%s) @ %s:%d\n", lock,
 1385                                     lock->lo_name, w->w_name,
 1386                                     fixup_filename(file), line);
 1387                         }
 1388                         witness_debugger(1, __func__);
 1389                         return;
 1390                 }
 1391         }
 1392 
 1393         /*
 1394          * If requested, build a new lock order.  However, don't build a new
 1395          * relationship between a sleepable lock and Giant if it is in the
 1396          * wrong direction.  The correct lock order is that sleepable locks
 1397          * always come before Giant.
 1398          */
 1399         if (flags & LOP_NEWORDER &&
 1400             !(plock->li_lock == &Giant.lock_object &&
 1401             (lock->lo_flags & LO_SLEEPABLE) != 0)) {
 1402                 CTR3(KTR_WITNESS, "%s: adding %s as a child of %s", __func__,
 1403                     w->w_name, plock->li_lock->lo_witness->w_name);
 1404                 itismychild(plock->li_lock->lo_witness, w);
 1405         }
 1406 out:
 1407         mtx_unlock_spin(&w_mtx);
 1408 }
 1409 
 1410 void
 1411 witness_lock(struct lock_object *lock, int flags, const char *file, int line)
 1412 {
 1413         struct lock_list_entry **lock_list, *lle;
 1414         struct lock_instance *instance;
 1415         struct witness *w;
 1416         struct thread *td;
 1417 
 1418         if (witness_cold || witness_watch == -1 || lock->lo_witness == NULL ||
 1419             panicstr != NULL)
 1420                 return;
 1421         w = lock->lo_witness;
 1422         td = curthread;
 1423 
 1424         /* Determine lock list for this lock. */
 1425         if (LOCK_CLASS(lock)->lc_flags & LC_SLEEPLOCK)
 1426                 lock_list = &td->td_sleeplocks;
 1427         else
 1428                 lock_list = PCPU_PTR(spinlocks);
 1429 
 1430         /* Check to see if we are recursing on a lock we already own. */
 1431         instance = find_instance(*lock_list, lock);
 1432         if (instance != NULL) {
 1433                 instance->li_flags++;
 1434                 CTR4(KTR_WITNESS, "%s: pid %d recursed on %s r=%d", __func__,
 1435                     td->td_proc->p_pid, lock->lo_name,
 1436                     instance->li_flags & LI_RECURSEMASK);
 1437                 instance->li_file = file;
 1438                 instance->li_line = line;
 1439                 return;
 1440         }
 1441 
 1442         /* Update per-witness last file and line acquire. */
 1443         w->w_file = file;
 1444         w->w_line = line;
 1445 
 1446         /* Find the next open lock instance in the list and fill it. */
 1447         lle = *lock_list;
 1448         if (lle == NULL || lle->ll_count == LOCK_NCHILDREN) {
 1449                 lle = witness_lock_list_get();
 1450                 if (lle == NULL)
 1451                         return;
 1452                 lle->ll_next = *lock_list;
 1453                 CTR3(KTR_WITNESS, "%s: pid %d added lle %p", __func__,
 1454                     td->td_proc->p_pid, lle);
 1455                 *lock_list = lle;
 1456         }
 1457         instance = &lle->ll_children[lle->ll_count++];
 1458         instance->li_lock = lock;
 1459         instance->li_line = line;
 1460         instance->li_file = file;
 1461         if ((flags & LOP_EXCLUSIVE) != 0)
 1462                 instance->li_flags = LI_EXCLUSIVE;
 1463         else
 1464                 instance->li_flags = 0;
 1465         CTR4(KTR_WITNESS, "%s: pid %d added %s as lle[%d]", __func__,
 1466             td->td_proc->p_pid, lock->lo_name, lle->ll_count - 1);
 1467 }
 1468 
 1469 void
 1470 witness_upgrade(struct lock_object *lock, int flags, const char *file, int line)
 1471 {
 1472         struct lock_instance *instance;
 1473         struct lock_class *class;
 1474 
 1475         KASSERT(witness_cold == 0, ("%s: witness_cold", __func__));
 1476         if (lock->lo_witness == NULL || witness_watch == -1 || panicstr != NULL)
 1477                 return;
 1478         class = LOCK_CLASS(lock);
 1479         if (witness_watch) {
 1480                 if ((lock->lo_flags & LO_UPGRADABLE) == 0)
 1481                         kassert_panic(
 1482                             "upgrade of non-upgradable lock (%s) %s @ %s:%d",
 1483                             class->lc_name, lock->lo_name,
 1484                             fixup_filename(file), line);
 1485                 if ((class->lc_flags & LC_SLEEPLOCK) == 0)
 1486                         kassert_panic(
 1487                             "upgrade of non-sleep lock (%s) %s @ %s:%d",
 1488                             class->lc_name, lock->lo_name,
 1489                             fixup_filename(file), line);
 1490         }
 1491         instance = find_instance(curthread->td_sleeplocks, lock);
 1492         if (instance == NULL) {
 1493                 kassert_panic("upgrade of unlocked lock (%s) %s @ %s:%d",
 1494                     class->lc_name, lock->lo_name,
 1495                     fixup_filename(file), line);
 1496                 return;
 1497         }
 1498         if (witness_watch) {
 1499                 if ((instance->li_flags & LI_EXCLUSIVE) != 0)
 1500                         kassert_panic(
 1501                             "upgrade of exclusive lock (%s) %s @ %s:%d",
 1502                             class->lc_name, lock->lo_name,
 1503                             fixup_filename(file), line);
 1504                 if ((instance->li_flags & LI_RECURSEMASK) != 0)
 1505                         kassert_panic(
 1506                             "upgrade of recursed lock (%s) %s r=%d @ %s:%d",
 1507                             class->lc_name, lock->lo_name,
 1508                             instance->li_flags & LI_RECURSEMASK,
 1509                             fixup_filename(file), line);
 1510         }
 1511         instance->li_flags |= LI_EXCLUSIVE;
 1512 }
 1513 
 1514 void
 1515 witness_downgrade(struct lock_object *lock, int flags, const char *file,
 1516     int line)
 1517 {
 1518         struct lock_instance *instance;
 1519         struct lock_class *class;
 1520 
 1521         KASSERT(witness_cold == 0, ("%s: witness_cold", __func__));
 1522         if (lock->lo_witness == NULL || witness_watch == -1 || panicstr != NULL)
 1523                 return;
 1524         class = LOCK_CLASS(lock);
 1525         if (witness_watch) {
 1526                 if ((lock->lo_flags & LO_UPGRADABLE) == 0)
 1527                         kassert_panic(
 1528                             "downgrade of non-upgradable lock (%s) %s @ %s:%d",
 1529                             class->lc_name, lock->lo_name,
 1530                             fixup_filename(file), line);
 1531                 if ((class->lc_flags & LC_SLEEPLOCK) == 0)
 1532                         kassert_panic(
 1533                             "downgrade of non-sleep lock (%s) %s @ %s:%d",
 1534                             class->lc_name, lock->lo_name,
 1535                             fixup_filename(file), line);
 1536         }
 1537         instance = find_instance(curthread->td_sleeplocks, lock);
 1538         if (instance == NULL) {
 1539                 kassert_panic("downgrade of unlocked lock (%s) %s @ %s:%d",
 1540                     class->lc_name, lock->lo_name,
 1541                     fixup_filename(file), line);
 1542                 return;
 1543         }
 1544         if (witness_watch) {
 1545                 if ((instance->li_flags & LI_EXCLUSIVE) == 0)
 1546                         kassert_panic(
 1547                             "downgrade of shared lock (%s) %s @ %s:%d",
 1548                             class->lc_name, lock->lo_name,
 1549                             fixup_filename(file), line);
 1550                 if ((instance->li_flags & LI_RECURSEMASK) != 0)
 1551                         kassert_panic(
 1552                             "downgrade of recursed lock (%s) %s r=%d @ %s:%d",
 1553                             class->lc_name, lock->lo_name,
 1554                             instance->li_flags & LI_RECURSEMASK,
 1555                             fixup_filename(file), line);
 1556         }
 1557         instance->li_flags &= ~LI_EXCLUSIVE;
 1558 }
 1559 
 1560 void
 1561 witness_unlock(struct lock_object *lock, int flags, const char *file, int line)
 1562 {
 1563         struct lock_list_entry **lock_list, *lle;
 1564         struct lock_instance *instance;
 1565         struct lock_class *class;
 1566         struct thread *td;
 1567         register_t s;
 1568         int i, j;
 1569 
 1570         if (witness_cold || lock->lo_witness == NULL || panicstr != NULL)
 1571                 return;
 1572         td = curthread;
 1573         class = LOCK_CLASS(lock);
 1574 
 1575         /* Find lock instance associated with this lock. */
 1576         if (class->lc_flags & LC_SLEEPLOCK)
 1577                 lock_list = &td->td_sleeplocks;
 1578         else
 1579                 lock_list = PCPU_PTR(spinlocks);
 1580         lle = *lock_list;
 1581         for (; *lock_list != NULL; lock_list = &(*lock_list)->ll_next)
 1582                 for (i = 0; i < (*lock_list)->ll_count; i++) {
 1583                         instance = &(*lock_list)->ll_children[i];
 1584                         if (instance->li_lock == lock)
 1585                                 goto found;
 1586                 }
 1587 
 1588         /*
 1589          * When disabling WITNESS through witness_watch we could end up in
 1590          * having registered locks in the td_sleeplocks queue.
 1591          * We have to make sure we flush these queues, so just search for
 1592          * eventual register locks and remove them.
 1593          */
 1594         if (witness_watch > 0) {
 1595                 kassert_panic("lock (%s) %s not locked @ %s:%d", class->lc_name,
 1596                     lock->lo_name, fixup_filename(file), line);
 1597                 return;
 1598         } else {
 1599                 return;
 1600         }
 1601 found:
 1602 
 1603         /* First, check for shared/exclusive mismatches. */
 1604         if ((instance->li_flags & LI_EXCLUSIVE) != 0 && witness_watch > 0 &&
 1605             (flags & LOP_EXCLUSIVE) == 0) {
 1606                 witness_output("shared unlock of (%s) %s @ %s:%d\n",
 1607                     class->lc_name, lock->lo_name, fixup_filename(file), line);
 1608                 witness_output("while exclusively locked from %s:%d\n",
 1609                     fixup_filename(instance->li_file), instance->li_line);
 1610                 kassert_panic("excl->ushare");
 1611         }
 1612         if ((instance->li_flags & LI_EXCLUSIVE) == 0 && witness_watch > 0 &&
 1613             (flags & LOP_EXCLUSIVE) != 0) {
 1614                 witness_output("exclusive unlock of (%s) %s @ %s:%d\n",
 1615                     class->lc_name, lock->lo_name, fixup_filename(file), line);
 1616                 witness_output("while share locked from %s:%d\n",
 1617                     fixup_filename(instance->li_file),
 1618                     instance->li_line);
 1619                 kassert_panic("share->uexcl");
 1620         }
 1621         /* If we are recursed, unrecurse. */
 1622         if ((instance->li_flags & LI_RECURSEMASK) > 0) {
 1623                 CTR4(KTR_WITNESS, "%s: pid %d unrecursed on %s r=%d", __func__,
 1624                     td->td_proc->p_pid, instance->li_lock->lo_name,
 1625                     instance->li_flags);
 1626                 instance->li_flags--;
 1627                 return;
 1628         }
 1629         /* The lock is now being dropped, check for NORELEASE flag */
 1630         if ((instance->li_flags & LI_NORELEASE) != 0 && witness_watch > 0) {
 1631                 witness_output("forbidden unlock of (%s) %s @ %s:%d\n",
 1632                     class->lc_name, lock->lo_name, fixup_filename(file), line);
 1633                 kassert_panic("lock marked norelease");
 1634         }
 1635 
 1636         /* Otherwise, remove this item from the list. */
 1637         s = intr_disable();
 1638         CTR4(KTR_WITNESS, "%s: pid %d removed %s from lle[%d]", __func__,
 1639             td->td_proc->p_pid, instance->li_lock->lo_name,
 1640             (*lock_list)->ll_count - 1);
 1641         for (j = i; j < (*lock_list)->ll_count - 1; j++)
 1642                 (*lock_list)->ll_children[j] =
 1643                     (*lock_list)->ll_children[j + 1];
 1644         (*lock_list)->ll_count--;
 1645         intr_restore(s);
 1646 
 1647         /*
 1648          * In order to reduce contention on w_mtx, we want to keep always an
 1649          * head object into lists so that frequent allocation from the 
 1650          * free witness pool (and subsequent locking) is avoided.
 1651          * In order to maintain the current code simple, when the head
 1652          * object is totally unloaded it means also that we do not have
 1653          * further objects in the list, so the list ownership needs to be
 1654          * hand over to another object if the current head needs to be freed.
 1655          */
 1656         if ((*lock_list)->ll_count == 0) {
 1657                 if (*lock_list == lle) {
 1658                         if (lle->ll_next == NULL)
 1659                                 return;
 1660                 } else
 1661                         lle = *lock_list;
 1662                 *lock_list = lle->ll_next;
 1663                 CTR3(KTR_WITNESS, "%s: pid %d removed lle %p", __func__,
 1664                     td->td_proc->p_pid, lle);
 1665                 witness_lock_list_free(lle);
 1666         }
 1667 }
 1668 
 1669 void
 1670 witness_thread_exit(struct thread *td)
 1671 {
 1672         struct lock_list_entry *lle;
 1673         int i, n;
 1674 
 1675         lle = td->td_sleeplocks;
 1676         if (lle == NULL || panicstr != NULL)
 1677                 return;
 1678         if (lle->ll_count != 0) {
 1679                 for (n = 0; lle != NULL; lle = lle->ll_next)
 1680                         for (i = lle->ll_count - 1; i >= 0; i--) {
 1681                                 if (n == 0)
 1682                                         witness_output(
 1683                     "Thread %p exiting with the following locks held:\n", td);
 1684                                 n++;
 1685                                 witness_list_lock(&lle->ll_children[i],
 1686                                     witness_output);
 1687                                 
 1688                         }
 1689                 kassert_panic(
 1690                     "Thread %p cannot exit while holding sleeplocks\n", td);
 1691         }
 1692         witness_lock_list_free(lle);
 1693 }
 1694 
 1695 /*
 1696  * Warn if any locks other than 'lock' are held.  Flags can be passed in to
 1697  * exempt Giant and sleepable locks from the checks as well.  If any
 1698  * non-exempt locks are held, then a supplied message is printed to the
 1699  * output channel along with a list of the offending locks.  If indicated in the
 1700  * flags then a failure results in a panic as well.
 1701  */
 1702 int
 1703 witness_warn(int flags, struct lock_object *lock, const char *fmt, ...)
 1704 {
 1705         struct lock_list_entry *lock_list, *lle;
 1706         struct lock_instance *lock1;
 1707         struct thread *td;
 1708         va_list ap;
 1709         int i, n;
 1710 
 1711         if (witness_cold || witness_watch < 1 || panicstr != NULL)
 1712                 return (0);
 1713         n = 0;
 1714         td = curthread;
 1715         for (lle = td->td_sleeplocks; lle != NULL; lle = lle->ll_next)
 1716                 for (i = lle->ll_count - 1; i >= 0; i--) {
 1717                         lock1 = &lle->ll_children[i];
 1718                         if (lock1->li_lock == lock)
 1719                                 continue;
 1720                         if (flags & WARN_GIANTOK &&
 1721                             lock1->li_lock == &Giant.lock_object)
 1722                                 continue;
 1723                         if (flags & WARN_SLEEPOK &&
 1724                             (lock1->li_lock->lo_flags & LO_SLEEPABLE) != 0)
 1725                                 continue;
 1726                         if (n == 0) {
 1727                                 va_start(ap, fmt);
 1728                                 witness_voutput(fmt, ap);
 1729                                 va_end(ap);
 1730                                 witness_output(
 1731                                     " with the following %slocks held:\n",
 1732                                     (flags & WARN_SLEEPOK) != 0 ?
 1733                                     "non-sleepable " : "");
 1734                         }
 1735                         n++;
 1736                         witness_list_lock(lock1, witness_output);
 1737                 }
 1738 
 1739         /*
 1740          * Pin the thread in order to avoid problems with thread migration.
 1741          * Once that all verifies are passed about spinlocks ownership,
 1742          * the thread is in a safe path and it can be unpinned.
 1743          */
 1744         sched_pin();
 1745         lock_list = PCPU_GET(spinlocks);
 1746         if (lock_list != NULL && lock_list->ll_count != 0) {
 1747                 sched_unpin();
 1748 
 1749                 /*
 1750                  * We should only have one spinlock and as long as
 1751                  * the flags cannot match for this locks class,
 1752                  * check if the first spinlock is the one curthread
 1753                  * should hold.
 1754                  */
 1755                 lock1 = &lock_list->ll_children[lock_list->ll_count - 1];
 1756                 if (lock_list->ll_count == 1 && lock_list->ll_next == NULL &&
 1757                     lock1->li_lock == lock && n == 0)
 1758                         return (0);
 1759 
 1760                 va_start(ap, fmt);
 1761                 witness_voutput(fmt, ap);
 1762                 va_end(ap);
 1763                 witness_output(" with the following %slocks held:\n",
 1764                     (flags & WARN_SLEEPOK) != 0 ?  "non-sleepable " : "");
 1765                 n += witness_list_locks(&lock_list, witness_output);
 1766         } else
 1767                 sched_unpin();
 1768         if (flags & WARN_PANIC && n)
 1769                 kassert_panic("%s", __func__);
 1770         else
 1771                 witness_debugger(n, __func__);
 1772         return (n);
 1773 }
 1774 
 1775 const char *
 1776 witness_file(struct lock_object *lock)
 1777 {
 1778         struct witness *w;
 1779 
 1780         if (witness_cold || witness_watch < 1 || lock->lo_witness == NULL)
 1781                 return ("?");
 1782         w = lock->lo_witness;
 1783         return (w->w_file);
 1784 }
 1785 
 1786 int
 1787 witness_line(struct lock_object *lock)
 1788 {
 1789         struct witness *w;
 1790 
 1791         if (witness_cold || witness_watch < 1 || lock->lo_witness == NULL)
 1792                 return (0);
 1793         w = lock->lo_witness;
 1794         return (w->w_line);
 1795 }
 1796 
 1797 static struct witness *
 1798 enroll(const char *description, struct lock_class *lock_class)
 1799 {
 1800         struct witness *w;
 1801         struct witness_list *typelist;
 1802 
 1803         MPASS(description != NULL);
 1804 
 1805         if (witness_watch == -1 || panicstr != NULL)
 1806                 return (NULL);
 1807         if ((lock_class->lc_flags & LC_SPINLOCK)) {
 1808                 if (witness_skipspin)
 1809                         return (NULL);
 1810                 else
 1811                         typelist = &w_spin;
 1812         } else if ((lock_class->lc_flags & LC_SLEEPLOCK)) {
 1813                 typelist = &w_sleep;
 1814         } else {
 1815                 kassert_panic("lock class %s is not sleep or spin",
 1816                     lock_class->lc_name);
 1817                 return (NULL);
 1818         }
 1819 
 1820         mtx_lock_spin(&w_mtx);
 1821         w = witness_hash_get(description);
 1822         if (w)
 1823                 goto found;
 1824         if ((w = witness_get()) == NULL)
 1825                 return (NULL);
 1826         MPASS(strlen(description) < MAX_W_NAME);
 1827         strcpy(w->w_name, description);
 1828         w->w_class = lock_class;
 1829         w->w_refcount = 1;
 1830         STAILQ_INSERT_HEAD(&w_all, w, w_list);
 1831         if (lock_class->lc_flags & LC_SPINLOCK) {
 1832                 STAILQ_INSERT_HEAD(&w_spin, w, w_typelist);
 1833                 w_spin_cnt++;
 1834         } else if (lock_class->lc_flags & LC_SLEEPLOCK) {
 1835                 STAILQ_INSERT_HEAD(&w_sleep, w, w_typelist);
 1836                 w_sleep_cnt++;
 1837         }
 1838 
 1839         /* Insert new witness into the hash */
 1840         witness_hash_put(w);
 1841         witness_increment_graph_generation();
 1842         mtx_unlock_spin(&w_mtx);
 1843         return (w);
 1844 found:
 1845         w->w_refcount++;
 1846         mtx_unlock_spin(&w_mtx);
 1847         if (lock_class != w->w_class)
 1848                 kassert_panic(
 1849                         "lock (%s) %s does not match earlier (%s) lock",
 1850                         description, lock_class->lc_name,
 1851                         w->w_class->lc_name);
 1852         return (w);
 1853 }
 1854 
 1855 static void
 1856 depart(struct witness *w)
 1857 {
 1858         struct witness_list *list;
 1859 
 1860         MPASS(w->w_refcount == 0);
 1861         if (w->w_class->lc_flags & LC_SLEEPLOCK) {
 1862                 list = &w_sleep;
 1863                 w_sleep_cnt--;
 1864         } else {
 1865                 list = &w_spin;
 1866                 w_spin_cnt--;
 1867         }
 1868         /*
 1869          * Set file to NULL as it may point into a loadable module.
 1870          */
 1871         w->w_file = NULL;
 1872         w->w_line = 0;
 1873         witness_increment_graph_generation();
 1874 }
 1875 
 1876 
 1877 static void
 1878 adopt(struct witness *parent, struct witness *child)
 1879 {
 1880         int pi, ci, i, j;
 1881 
 1882         if (witness_cold == 0)
 1883                 mtx_assert(&w_mtx, MA_OWNED);
 1884 
 1885         /* If the relationship is already known, there's no work to be done. */
 1886         if (isitmychild(parent, child))
 1887                 return;
 1888 
 1889         /* When the structure of the graph changes, bump up the generation. */
 1890         witness_increment_graph_generation();
 1891 
 1892         /*
 1893          * The hard part ... create the direct relationship, then propagate all
 1894          * indirect relationships.
 1895          */
 1896         pi = parent->w_index;
 1897         ci = child->w_index;
 1898         WITNESS_INDEX_ASSERT(pi);
 1899         WITNESS_INDEX_ASSERT(ci);
 1900         MPASS(pi != ci);
 1901         w_rmatrix[pi][ci] |= WITNESS_PARENT;
 1902         w_rmatrix[ci][pi] |= WITNESS_CHILD;
 1903 
 1904         /*
 1905          * If parent was not already an ancestor of child,
 1906          * then we increment the descendant and ancestor counters.
 1907          */
 1908         if ((w_rmatrix[pi][ci] & WITNESS_ANCESTOR) == 0) {
 1909                 parent->w_num_descendants++;
 1910                 child->w_num_ancestors++;
 1911         }
 1912 
 1913         /* 
 1914          * Find each ancestor of 'pi'. Note that 'pi' itself is counted as 
 1915          * an ancestor of 'pi' during this loop.
 1916          */
 1917         for (i = 1; i <= w_max_used_index; i++) {
 1918                 if ((w_rmatrix[i][pi] & WITNESS_ANCESTOR_MASK) == 0 && 
 1919                     (i != pi))
 1920                         continue;
 1921 
 1922                 /* Find each descendant of 'i' and mark it as a descendant. */
 1923                 for (j = 1; j <= w_max_used_index; j++) {
 1924 
 1925                         /* 
 1926                          * Skip children that are already marked as
 1927                          * descendants of 'i'.
 1928                          */
 1929                         if (w_rmatrix[i][j] & WITNESS_ANCESTOR_MASK)
 1930                                 continue;
 1931 
 1932                         /*
 1933                          * We are only interested in descendants of 'ci'. Note
 1934                          * that 'ci' itself is counted as a descendant of 'ci'.
 1935                          */
 1936                         if ((w_rmatrix[ci][j] & WITNESS_ANCESTOR_MASK) == 0 && 
 1937                             (j != ci))
 1938                                 continue;
 1939                         w_rmatrix[i][j] |= WITNESS_ANCESTOR;
 1940                         w_rmatrix[j][i] |= WITNESS_DESCENDANT;
 1941                         w_data[i].w_num_descendants++;
 1942                         w_data[j].w_num_ancestors++;
 1943 
 1944                         /* 
 1945                          * Make sure we aren't marking a node as both an
 1946                          * ancestor and descendant. We should have caught 
 1947                          * this as a lock order reversal earlier.
 1948                          */
 1949                         if ((w_rmatrix[i][j] & WITNESS_ANCESTOR_MASK) &&
 1950                             (w_rmatrix[i][j] & WITNESS_DESCENDANT_MASK)) {
 1951                                 printf("witness rmatrix paradox! [%d][%d]=%d "
 1952                                     "both ancestor and descendant\n",
 1953                                     i, j, w_rmatrix[i][j]); 
 1954                                 kdb_backtrace();
 1955                                 printf("Witness disabled.\n");
 1956                                 witness_watch = -1;
 1957                         }
 1958                         if ((w_rmatrix[j][i] & WITNESS_ANCESTOR_MASK) &&
 1959                             (w_rmatrix[j][i] & WITNESS_DESCENDANT_MASK)) {
 1960                                 printf("witness rmatrix paradox! [%d][%d]=%d "
 1961                                     "both ancestor and descendant\n",
 1962                                     j, i, w_rmatrix[j][i]); 
 1963                                 kdb_backtrace();
 1964                                 printf("Witness disabled.\n");
 1965                                 witness_watch = -1;
 1966                         }
 1967                 }
 1968         }
 1969 }
 1970 
 1971 static void
 1972 itismychild(struct witness *parent, struct witness *child)
 1973 {
 1974         int unlocked;
 1975 
 1976         MPASS(child != NULL && parent != NULL);
 1977         if (witness_cold == 0)
 1978                 mtx_assert(&w_mtx, MA_OWNED);
 1979 
 1980         if (!witness_lock_type_equal(parent, child)) {
 1981                 if (witness_cold == 0) {
 1982                         unlocked = 1;
 1983                         mtx_unlock_spin(&w_mtx);
 1984                 } else {
 1985                         unlocked = 0;
 1986                 }
 1987                 kassert_panic(
 1988                     "%s: parent \"%s\" (%s) and child \"%s\" (%s) are not "
 1989                     "the same lock type", __func__, parent->w_name,
 1990                     parent->w_class->lc_name, child->w_name,
 1991                     child->w_class->lc_name);
 1992                 if (unlocked)
 1993                         mtx_lock_spin(&w_mtx);
 1994         }
 1995         adopt(parent, child);
 1996 }
 1997 
 1998 /*
 1999  * Generic code for the isitmy*() functions. The rmask parameter is the
 2000  * expected relationship of w1 to w2.
 2001  */
 2002 static int
 2003 _isitmyx(struct witness *w1, struct witness *w2, int rmask, const char *fname)
 2004 {
 2005         unsigned char r1, r2;
 2006         int i1, i2;
 2007 
 2008         i1 = w1->w_index;
 2009         i2 = w2->w_index;
 2010         WITNESS_INDEX_ASSERT(i1);
 2011         WITNESS_INDEX_ASSERT(i2);
 2012         r1 = w_rmatrix[i1][i2] & WITNESS_RELATED_MASK;
 2013         r2 = w_rmatrix[i2][i1] & WITNESS_RELATED_MASK;
 2014 
 2015         /* The flags on one better be the inverse of the flags on the other */
 2016         if (!((WITNESS_ATOD(r1) == r2 && WITNESS_DTOA(r2) == r1) ||
 2017             (WITNESS_DTOA(r1) == r2 && WITNESS_ATOD(r2) == r1))) {
 2018                 /* Don't squawk if we're potentially racing with an update. */
 2019                 if (!mtx_owned(&w_mtx))
 2020                         return (0);
 2021                 printf("%s: rmatrix mismatch between %s (index %d) and %s "
 2022                     "(index %d): w_rmatrix[%d][%d] == %hhx but "
 2023                     "w_rmatrix[%d][%d] == %hhx\n",
 2024                     fname, w1->w_name, i1, w2->w_name, i2, i1, i2, r1,
 2025                     i2, i1, r2);
 2026                 kdb_backtrace();
 2027                 printf("Witness disabled.\n");
 2028                 witness_watch = -1;
 2029         }
 2030         return (r1 & rmask);
 2031 }
 2032 
 2033 /*
 2034  * Checks if @child is a direct child of @parent.
 2035  */
 2036 static int
 2037 isitmychild(struct witness *parent, struct witness *child)
 2038 {
 2039 
 2040         return (_isitmyx(parent, child, WITNESS_PARENT, __func__));
 2041 }
 2042 
 2043 /*
 2044  * Checks if @descendant is a direct or inderect descendant of @ancestor.
 2045  */
 2046 static int
 2047 isitmydescendant(struct witness *ancestor, struct witness *descendant)
 2048 {
 2049 
 2050         return (_isitmyx(ancestor, descendant, WITNESS_ANCESTOR_MASK,
 2051             __func__));
 2052 }
 2053 
 2054 #ifdef BLESSING
 2055 static int
 2056 blessed(struct witness *w1, struct witness *w2)
 2057 {
 2058         int i;
 2059         struct witness_blessed *b;
 2060 
 2061         for (i = 0; i < nitems(blessed_list); i++) {
 2062                 b = &blessed_list[i];
 2063                 if (strcmp(w1->w_name, b->b_lock1) == 0) {
 2064                         if (strcmp(w2->w_name, b->b_lock2) == 0)
 2065                                 return (1);
 2066                         continue;
 2067                 }
 2068                 if (strcmp(w1->w_name, b->b_lock2) == 0)
 2069                         if (strcmp(w2->w_name, b->b_lock1) == 0)
 2070                                 return (1);
 2071         }
 2072         return (0);
 2073 }
 2074 #endif
 2075 
 2076 static struct witness *
 2077 witness_get(void)
 2078 {
 2079         struct witness *w;
 2080         int index;
 2081 
 2082         if (witness_cold == 0)
 2083                 mtx_assert(&w_mtx, MA_OWNED);
 2084 
 2085         if (witness_watch == -1) {
 2086                 mtx_unlock_spin(&w_mtx);
 2087                 return (NULL);
 2088         }
 2089         if (STAILQ_EMPTY(&w_free)) {
 2090                 witness_watch = -1;
 2091                 mtx_unlock_spin(&w_mtx);
 2092                 printf("WITNESS: unable to allocate a new witness object\n");
 2093                 return (NULL);
 2094         }
 2095         w = STAILQ_FIRST(&w_free);
 2096         STAILQ_REMOVE_HEAD(&w_free, w_list);
 2097         w_free_cnt--;
 2098         index = w->w_index;
 2099         MPASS(index > 0 && index == w_max_used_index+1 &&
 2100             index < witness_count);
 2101         bzero(w, sizeof(*w));
 2102         w->w_index = index;
 2103         if (index > w_max_used_index)
 2104                 w_max_used_index = index;
 2105         return (w);
 2106 }
 2107 
 2108 static void
 2109 witness_free(struct witness *w)
 2110 {
 2111 
 2112         STAILQ_INSERT_HEAD(&w_free, w, w_list);
 2113         w_free_cnt++;
 2114 }
 2115 
 2116 static struct lock_list_entry *
 2117 witness_lock_list_get(void)
 2118 {
 2119         struct lock_list_entry *lle;
 2120 
 2121         if (witness_watch == -1)
 2122                 return (NULL);
 2123         mtx_lock_spin(&w_mtx);
 2124         lle = w_lock_list_free;
 2125         if (lle == NULL) {
 2126                 witness_watch = -1;
 2127                 mtx_unlock_spin(&w_mtx);
 2128                 printf("%s: witness exhausted\n", __func__);
 2129                 return (NULL);
 2130         }
 2131         w_lock_list_free = lle->ll_next;
 2132         mtx_unlock_spin(&w_mtx);
 2133         bzero(lle, sizeof(*lle));
 2134         return (lle);
 2135 }
 2136                 
 2137 static void
 2138 witness_lock_list_free(struct lock_list_entry *lle)
 2139 {
 2140 
 2141         mtx_lock_spin(&w_mtx);
 2142         lle->ll_next = w_lock_list_free;
 2143         w_lock_list_free = lle;
 2144         mtx_unlock_spin(&w_mtx);
 2145 }
 2146 
 2147 static struct lock_instance *
 2148 find_instance(struct lock_list_entry *list, const struct lock_object *lock)
 2149 {
 2150         struct lock_list_entry *lle;
 2151         struct lock_instance *instance;
 2152         int i;
 2153 
 2154         for (lle = list; lle != NULL; lle = lle->ll_next)
 2155                 for (i = lle->ll_count - 1; i >= 0; i--) {
 2156                         instance = &lle->ll_children[i];
 2157                         if (instance->li_lock == lock)
 2158                                 return (instance);
 2159                 }
 2160         return (NULL);
 2161 }
 2162 
 2163 static void
 2164 witness_list_lock(struct lock_instance *instance,
 2165     int (*prnt)(const char *fmt, ...))
 2166 {
 2167         struct lock_object *lock;
 2168 
 2169         lock = instance->li_lock;
 2170         prnt("%s %s %s", (instance->li_flags & LI_EXCLUSIVE) != 0 ?
 2171             "exclusive" : "shared", LOCK_CLASS(lock)->lc_name, lock->lo_name);
 2172         if (lock->lo_witness->w_name != lock->lo_name)
 2173                 prnt(" (%s)", lock->lo_witness->w_name);
 2174         prnt(" r = %d (%p) locked @ %s:%d\n",
 2175             instance->li_flags & LI_RECURSEMASK, lock,
 2176             fixup_filename(instance->li_file), instance->li_line);
 2177 }
 2178 
 2179 static int
 2180 witness_output(const char *fmt, ...)
 2181 {
 2182         va_list ap;
 2183         int ret;
 2184 
 2185         va_start(ap, fmt);
 2186         ret = witness_voutput(fmt, ap);
 2187         va_end(ap);
 2188         return (ret);
 2189 }
 2190 
 2191 static int
 2192 witness_voutput(const char *fmt, va_list ap)
 2193 {
 2194         int ret;
 2195 
 2196         ret = 0;
 2197         switch (witness_channel) {
 2198         case WITNESS_CONSOLE:
 2199                 ret = vprintf(fmt, ap);
 2200                 break;
 2201         case WITNESS_LOG:
 2202                 vlog(LOG_NOTICE, fmt, ap);
 2203                 break;
 2204         case WITNESS_NONE:
 2205                 break;
 2206         }
 2207         return (ret);
 2208 }
 2209 
 2210 #ifdef DDB
 2211 static int
 2212 witness_thread_has_locks(struct thread *td)
 2213 {
 2214 
 2215         if (td->td_sleeplocks == NULL)
 2216                 return (0);
 2217         return (td->td_sleeplocks->ll_count != 0);
 2218 }
 2219 
 2220 static int
 2221 witness_proc_has_locks(struct proc *p)
 2222 {
 2223         struct thread *td;
 2224 
 2225         FOREACH_THREAD_IN_PROC(p, td) {
 2226                 if (witness_thread_has_locks(td))
 2227                         return (1);
 2228         }
 2229         return (0);
 2230 }
 2231 #endif
 2232 
 2233 int
 2234 witness_list_locks(struct lock_list_entry **lock_list,
 2235     int (*prnt)(const char *fmt, ...))
 2236 {
 2237         struct lock_list_entry *lle;
 2238         int i, nheld;
 2239 
 2240         nheld = 0;
 2241         for (lle = *lock_list; lle != NULL; lle = lle->ll_next)
 2242                 for (i = lle->ll_count - 1; i >= 0; i--) {
 2243                         witness_list_lock(&lle->ll_children[i], prnt);
 2244                         nheld++;
 2245                 }
 2246         return (nheld);
 2247 }
 2248 
 2249 /*
 2250  * This is a bit risky at best.  We call this function when we have timed
 2251  * out acquiring a spin lock, and we assume that the other CPU is stuck
 2252  * with this lock held.  So, we go groveling around in the other CPU's
 2253  * per-cpu data to try to find the lock instance for this spin lock to
 2254  * see when it was last acquired.
 2255  */
 2256 void
 2257 witness_display_spinlock(struct lock_object *lock, struct thread *owner,
 2258     int (*prnt)(const char *fmt, ...))
 2259 {
 2260         struct lock_instance *instance;
 2261         struct pcpu *pc;
 2262 
 2263         if (owner->td_critnest == 0 || owner->td_oncpu == NOCPU)
 2264                 return;
 2265         pc = pcpu_find(owner->td_oncpu);
 2266         instance = find_instance(pc->pc_spinlocks, lock);
 2267         if (instance != NULL)
 2268                 witness_list_lock(instance, prnt);
 2269 }
 2270 
 2271 void
 2272 witness_save(struct lock_object *lock, const char **filep, int *linep)
 2273 {
 2274         struct lock_list_entry *lock_list;
 2275         struct lock_instance *instance;
 2276         struct lock_class *class;
 2277 
 2278         /*
 2279          * This function is used independently in locking code to deal with
 2280          * Giant, SCHEDULER_STOPPED() check can be removed here after Giant
 2281          * is gone.
 2282          */
 2283         if (SCHEDULER_STOPPED())
 2284                 return;
 2285         KASSERT(witness_cold == 0, ("%s: witness_cold", __func__));
 2286         if (lock->lo_witness == NULL || witness_watch == -1 || panicstr != NULL)
 2287                 return;
 2288         class = LOCK_CLASS(lock);
 2289         if (class->lc_flags & LC_SLEEPLOCK)
 2290                 lock_list = curthread->td_sleeplocks;
 2291         else {
 2292                 if (witness_skipspin)
 2293                         return;
 2294                 lock_list = PCPU_GET(spinlocks);
 2295         }
 2296         instance = find_instance(lock_list, lock);
 2297         if (instance == NULL) {
 2298                 kassert_panic("%s: lock (%s) %s not locked", __func__,
 2299                     class->lc_name, lock->lo_name);
 2300                 return;
 2301         }
 2302         *filep = instance->li_file;
 2303         *linep = instance->li_line;
 2304 }
 2305 
 2306 void
 2307 witness_restore(struct lock_object *lock, const char *file, int line)
 2308 {
 2309         struct lock_list_entry *lock_list;
 2310         struct lock_instance *instance;
 2311         struct lock_class *class;
 2312 
 2313         /*
 2314          * This function is used independently in locking code to deal with
 2315          * Giant, SCHEDULER_STOPPED() check can be removed here after Giant
 2316          * is gone.
 2317          */
 2318         if (SCHEDULER_STOPPED())
 2319                 return;
 2320         KASSERT(witness_cold == 0, ("%s: witness_cold", __func__));
 2321         if (lock->lo_witness == NULL || witness_watch == -1 || panicstr != NULL)
 2322                 return;
 2323         class = LOCK_CLASS(lock);
 2324         if (class->lc_flags & LC_SLEEPLOCK)
 2325                 lock_list = curthread->td_sleeplocks;
 2326         else {
 2327                 if (witness_skipspin)
 2328                         return;
 2329                 lock_list = PCPU_GET(spinlocks);
 2330         }
 2331         instance = find_instance(lock_list, lock);
 2332         if (instance == NULL)
 2333                 kassert_panic("%s: lock (%s) %s not locked", __func__,
 2334                     class->lc_name, lock->lo_name);
 2335         lock->lo_witness->w_file = file;
 2336         lock->lo_witness->w_line = line;
 2337         if (instance == NULL)
 2338                 return;
 2339         instance->li_file = file;
 2340         instance->li_line = line;
 2341 }
 2342 
 2343 void
 2344 witness_assert(const struct lock_object *lock, int flags, const char *file,
 2345     int line)
 2346 {
 2347 #ifdef INVARIANT_SUPPORT
 2348         struct lock_instance *instance;
 2349         struct lock_class *class;
 2350 
 2351         if (lock->lo_witness == NULL || witness_watch < 1 || panicstr != NULL)
 2352                 return;
 2353         class = LOCK_CLASS(lock);
 2354         if ((class->lc_flags & LC_SLEEPLOCK) != 0)
 2355                 instance = find_instance(curthread->td_sleeplocks, lock);
 2356         else if ((class->lc_flags & LC_SPINLOCK) != 0)
 2357                 instance = find_instance(PCPU_GET(spinlocks), lock);
 2358         else {
 2359                 kassert_panic("Lock (%s) %s is not sleep or spin!",
 2360                     class->lc_name, lock->lo_name);
 2361                 return;
 2362         }
 2363         switch (flags) {
 2364         case LA_UNLOCKED:
 2365                 if (instance != NULL)
 2366                         kassert_panic("Lock (%s) %s locked @ %s:%d.",
 2367                             class->lc_name, lock->lo_name,
 2368                             fixup_filename(file), line);
 2369                 break;
 2370         case LA_LOCKED:
 2371         case LA_LOCKED | LA_RECURSED:
 2372         case LA_LOCKED | LA_NOTRECURSED:
 2373         case LA_SLOCKED:
 2374         case LA_SLOCKED | LA_RECURSED:
 2375         case LA_SLOCKED | LA_NOTRECURSED:
 2376         case LA_XLOCKED:
 2377         case LA_XLOCKED | LA_RECURSED:
 2378         case LA_XLOCKED | LA_NOTRECURSED:
 2379                 if (instance == NULL) {
 2380                         kassert_panic("Lock (%s) %s not locked @ %s:%d.",
 2381                             class->lc_name, lock->lo_name,
 2382                             fixup_filename(file), line);
 2383                         break;
 2384                 }
 2385                 if ((flags & LA_XLOCKED) != 0 &&
 2386                     (instance->li_flags & LI_EXCLUSIVE) == 0)
 2387                         kassert_panic(
 2388                             "Lock (%s) %s not exclusively locked @ %s:%d.",
 2389                             class->lc_name, lock->lo_name,
 2390                             fixup_filename(file), line);
 2391                 if ((flags & LA_SLOCKED) != 0 &&
 2392                     (instance->li_flags & LI_EXCLUSIVE) != 0)
 2393                         kassert_panic(
 2394                             "Lock (%s) %s exclusively locked @ %s:%d.",
 2395                             class->lc_name, lock->lo_name,
 2396                             fixup_filename(file), line);
 2397                 if ((flags & LA_RECURSED) != 0 &&
 2398                     (instance->li_flags & LI_RECURSEMASK) == 0)
 2399                         kassert_panic("Lock (%s) %s not recursed @ %s:%d.",
 2400                             class->lc_name, lock->lo_name,
 2401                             fixup_filename(file), line);
 2402                 if ((flags & LA_NOTRECURSED) != 0 &&
 2403                     (instance->li_flags & LI_RECURSEMASK) != 0)
 2404                         kassert_panic("Lock (%s) %s recursed @ %s:%d.",
 2405                             class->lc_name, lock->lo_name,
 2406                             fixup_filename(file), line);
 2407                 break;
 2408         default:
 2409                 kassert_panic("Invalid lock assertion at %s:%d.",
 2410                     fixup_filename(file), line);
 2411 
 2412         }
 2413 #endif  /* INVARIANT_SUPPORT */
 2414 }
 2415 
 2416 static void
 2417 witness_setflag(struct lock_object *lock, int flag, int set)
 2418 {
 2419         struct lock_list_entry *lock_list;
 2420         struct lock_instance *instance;
 2421         struct lock_class *class;
 2422 
 2423         if (lock->lo_witness == NULL || witness_watch == -1 || panicstr != NULL)
 2424                 return;
 2425         class = LOCK_CLASS(lock);
 2426         if (class->lc_flags & LC_SLEEPLOCK)
 2427                 lock_list = curthread->td_sleeplocks;
 2428         else {
 2429                 if (witness_skipspin)
 2430                         return;
 2431                 lock_list = PCPU_GET(spinlocks);
 2432         }
 2433         instance = find_instance(lock_list, lock);
 2434         if (instance == NULL) {
 2435                 kassert_panic("%s: lock (%s) %s not locked", __func__,
 2436                     class->lc_name, lock->lo_name);
 2437                 return;
 2438         }
 2439 
 2440         if (set)
 2441                 instance->li_flags |= flag;
 2442         else
 2443                 instance->li_flags &= ~flag;
 2444 }
 2445 
 2446 void
 2447 witness_norelease(struct lock_object *lock)
 2448 {
 2449 
 2450         witness_setflag(lock, LI_NORELEASE, 1);
 2451 }
 2452 
 2453 void
 2454 witness_releaseok(struct lock_object *lock)
 2455 {
 2456 
 2457         witness_setflag(lock, LI_NORELEASE, 0);
 2458 }
 2459 
 2460 #ifdef DDB
 2461 static void
 2462 witness_ddb_list(struct thread *td)
 2463 {
 2464 
 2465         KASSERT(witness_cold == 0, ("%s: witness_cold", __func__));
 2466         KASSERT(kdb_active, ("%s: not in the debugger", __func__));
 2467 
 2468         if (witness_watch < 1)
 2469                 return;
 2470 
 2471         witness_list_locks(&td->td_sleeplocks, db_printf);
 2472 
 2473         /*
 2474          * We only handle spinlocks if td == curthread.  This is somewhat broken
 2475          * if td is currently executing on some other CPU and holds spin locks
 2476          * as we won't display those locks.  If we had a MI way of getting
 2477          * the per-cpu data for a given cpu then we could use
 2478          * td->td_oncpu to get the list of spinlocks for this thread
 2479          * and "fix" this.
 2480          *
 2481          * That still wouldn't really fix this unless we locked the scheduler
 2482          * lock or stopped the other CPU to make sure it wasn't changing the
 2483          * list out from under us.  It is probably best to just not try to
 2484          * handle threads on other CPU's for now.
 2485          */
 2486         if (td == curthread && PCPU_GET(spinlocks) != NULL)
 2487                 witness_list_locks(PCPU_PTR(spinlocks), db_printf);
 2488 }
 2489 
 2490 DB_SHOW_COMMAND(locks, db_witness_list)
 2491 {
 2492         struct thread *td;
 2493 
 2494         if (have_addr)
 2495                 td = db_lookup_thread(addr, true);
 2496         else
 2497                 td = kdb_thread;
 2498         witness_ddb_list(td);
 2499 }
 2500 
 2501 DB_SHOW_ALL_COMMAND(locks, db_witness_list_all)
 2502 {
 2503         struct thread *td;
 2504         struct proc *p;
 2505 
 2506         /*
 2507          * It would be nice to list only threads and processes that actually
 2508          * held sleep locks, but that information is currently not exported
 2509          * by WITNESS.
 2510          */
 2511         FOREACH_PROC_IN_SYSTEM(p) {
 2512                 if (!witness_proc_has_locks(p))
 2513                         continue;
 2514                 FOREACH_THREAD_IN_PROC(p, td) {
 2515                         if (!witness_thread_has_locks(td))
 2516                                 continue;
 2517                         db_printf("Process %d (%s) thread %p (%d)\n", p->p_pid,
 2518                             p->p_comm, td, td->td_tid);
 2519                         witness_ddb_list(td);
 2520                         if (db_pager_quit)
 2521                                 return;
 2522                 }
 2523         }
 2524 }
 2525 DB_SHOW_ALIAS(alllocks, db_witness_list_all)
 2526 
 2527 DB_SHOW_COMMAND(witness, db_witness_display)
 2528 {
 2529 
 2530         witness_ddb_display(db_printf);
 2531 }
 2532 #endif
 2533 
 2534 static int
 2535 sysctl_debug_witness_badstacks(SYSCTL_HANDLER_ARGS)
 2536 {
 2537         struct witness_lock_order_data *data1, *data2, *tmp_data1, *tmp_data2;
 2538         struct witness *tmp_w1, *tmp_w2, *w1, *w2;
 2539         struct sbuf *sb;
 2540         u_int w_rmatrix1, w_rmatrix2;
 2541         int error, generation, i, j;
 2542 
 2543         tmp_data1 = NULL;
 2544         tmp_data2 = NULL;
 2545         tmp_w1 = NULL;
 2546         tmp_w2 = NULL;
 2547         if (witness_watch < 1) {
 2548                 error = SYSCTL_OUT(req, w_notrunning, sizeof(w_notrunning));
 2549                 return (error);
 2550         }
 2551         if (witness_cold) {
 2552                 error = SYSCTL_OUT(req, w_stillcold, sizeof(w_stillcold));
 2553                 return (error);
 2554         }
 2555         error = 0;
 2556         sb = sbuf_new(NULL, NULL, badstack_sbuf_size, SBUF_AUTOEXTEND);
 2557         if (sb == NULL)
 2558                 return (ENOMEM);
 2559 
 2560         /* Allocate and init temporary storage space. */
 2561         tmp_w1 = malloc(sizeof(struct witness), M_TEMP, M_WAITOK | M_ZERO);
 2562         tmp_w2 = malloc(sizeof(struct witness), M_TEMP, M_WAITOK | M_ZERO);
 2563         tmp_data1 = malloc(sizeof(struct witness_lock_order_data), M_TEMP, 
 2564             M_WAITOK | M_ZERO);
 2565         tmp_data2 = malloc(sizeof(struct witness_lock_order_data), M_TEMP, 
 2566             M_WAITOK | M_ZERO);
 2567         stack_zero(&tmp_data1->wlod_stack);
 2568         stack_zero(&tmp_data2->wlod_stack);
 2569 
 2570 restart:
 2571         mtx_lock_spin(&w_mtx);
 2572         generation = w_generation;
 2573         mtx_unlock_spin(&w_mtx);
 2574         sbuf_printf(sb, "Number of known direct relationships is %d\n",
 2575             w_lohash.wloh_count);
 2576         for (i = 1; i < w_max_used_index; i++) {
 2577                 mtx_lock_spin(&w_mtx);
 2578                 if (generation != w_generation) {
 2579                         mtx_unlock_spin(&w_mtx);
 2580 
 2581                         /* The graph has changed, try again. */
 2582                         req->oldidx = 0;
 2583                         sbuf_clear(sb);
 2584                         goto restart;
 2585                 }
 2586 
 2587                 w1 = &w_data[i];
 2588                 if (w1->w_reversed == 0) {
 2589                         mtx_unlock_spin(&w_mtx);
 2590                         continue;
 2591                 }
 2592 
 2593                 /* Copy w1 locally so we can release the spin lock. */
 2594                 *tmp_w1 = *w1;
 2595                 mtx_unlock_spin(&w_mtx);
 2596 
 2597                 if (tmp_w1->w_reversed == 0)
 2598                         continue;
 2599                 for (j = 1; j < w_max_used_index; j++) {
 2600                         if ((w_rmatrix[i][j] & WITNESS_REVERSAL) == 0 || i > j)
 2601                                 continue;
 2602 
 2603                         mtx_lock_spin(&w_mtx);
 2604                         if (generation != w_generation) {
 2605                                 mtx_unlock_spin(&w_mtx);
 2606 
 2607                                 /* The graph has changed, try again. */
 2608                                 req->oldidx = 0;
 2609                                 sbuf_clear(sb);
 2610                                 goto restart;
 2611                         }
 2612 
 2613                         w2 = &w_data[j];
 2614                         data1 = witness_lock_order_get(w1, w2);
 2615                         data2 = witness_lock_order_get(w2, w1);
 2616 
 2617                         /*
 2618                          * Copy information locally so we can release the
 2619                          * spin lock.
 2620                          */
 2621                         *tmp_w2 = *w2;
 2622                         w_rmatrix1 = (unsigned int)w_rmatrix[i][j];
 2623                         w_rmatrix2 = (unsigned int)w_rmatrix[j][i];
 2624 
 2625                         if (data1) {
 2626                                 stack_zero(&tmp_data1->wlod_stack);
 2627                                 stack_copy(&data1->wlod_stack,
 2628                                     &tmp_data1->wlod_stack);
 2629                         }
 2630                         if (data2 && data2 != data1) {
 2631                                 stack_zero(&tmp_data2->wlod_stack);
 2632                                 stack_copy(&data2->wlod_stack,
 2633                                     &tmp_data2->wlod_stack);
 2634                         }
 2635                         mtx_unlock_spin(&w_mtx);
 2636 
 2637                         sbuf_printf(sb,
 2638             "\nLock order reversal between \"%s\"(%s) and \"%s\"(%s)!\n",
 2639                             tmp_w1->w_name, tmp_w1->w_class->lc_name, 
 2640                             tmp_w2->w_name, tmp_w2->w_class->lc_name);
 2641                         if (data1) {
 2642                                 sbuf_printf(sb,
 2643                         "Lock order \"%s\"(%s) -> \"%s\"(%s) first seen at:\n",
 2644                                     tmp_w1->w_name, tmp_w1->w_class->lc_name, 
 2645                                     tmp_w2->w_name, tmp_w2->w_class->lc_name);
 2646                                 stack_sbuf_print(sb, &tmp_data1->wlod_stack);
 2647                                 sbuf_printf(sb, "\n");
 2648                         }
 2649                         if (data2 && data2 != data1) {
 2650                                 sbuf_printf(sb,
 2651                         "Lock order \"%s\"(%s) -> \"%s\"(%s) first seen at:\n",
 2652                                     tmp_w2->w_name, tmp_w2->w_class->lc_name, 
 2653                                     tmp_w1->w_name, tmp_w1->w_class->lc_name);
 2654                                 stack_sbuf_print(sb, &tmp_data2->wlod_stack);
 2655                                 sbuf_printf(sb, "\n");
 2656                         }
 2657                 }
 2658         }
 2659         mtx_lock_spin(&w_mtx);
 2660         if (generation != w_generation) {
 2661                 mtx_unlock_spin(&w_mtx);
 2662 
 2663                 /*
 2664                  * The graph changed while we were printing stack data,
 2665                  * try again.
 2666                  */
 2667                 req->oldidx = 0;
 2668                 sbuf_clear(sb);
 2669                 goto restart;
 2670         }
 2671         mtx_unlock_spin(&w_mtx);
 2672 
 2673         /* Free temporary storage space. */
 2674         free(tmp_data1, M_TEMP);
 2675         free(tmp_data2, M_TEMP);
 2676         free(tmp_w1, M_TEMP);
 2677         free(tmp_w2, M_TEMP);
 2678 
 2679         sbuf_finish(sb);
 2680         error = SYSCTL_OUT(req, sbuf_data(sb), sbuf_len(sb) + 1);
 2681         sbuf_delete(sb);
 2682 
 2683         return (error);
 2684 }
 2685 
 2686 static int
 2687 sysctl_debug_witness_channel(SYSCTL_HANDLER_ARGS)
 2688 {
 2689         static const struct {
 2690                 enum witness_channel channel;
 2691                 const char *name;
 2692         } channels[] = {
 2693                 { WITNESS_CONSOLE, "console" },
 2694                 { WITNESS_LOG, "log" },
 2695                 { WITNESS_NONE, "none" },
 2696         };
 2697         char buf[16];
 2698         u_int i;
 2699         int error;
 2700 
 2701         buf[0] = '\0';
 2702         for (i = 0; i < nitems(channels); i++)
 2703                 if (witness_channel == channels[i].channel) {
 2704                         snprintf(buf, sizeof(buf), "%s", channels[i].name);
 2705                         break;
 2706                 }
 2707 
 2708         error = sysctl_handle_string(oidp, buf, sizeof(buf), req);
 2709         if (error != 0 || req->newptr == NULL)
 2710                 return (error);
 2711 
 2712         error = EINVAL;
 2713         for (i = 0; i < nitems(channels); i++)
 2714                 if (strcmp(channels[i].name, buf) == 0) {
 2715                         witness_channel = channels[i].channel;
 2716                         error = 0;
 2717                         break;
 2718                 }
 2719         return (error);
 2720 }
 2721 
 2722 static int
 2723 sysctl_debug_witness_fullgraph(SYSCTL_HANDLER_ARGS)
 2724 {
 2725         struct witness *w;
 2726         struct sbuf *sb;
 2727         int error;
 2728 
 2729         if (witness_watch < 1) {
 2730                 error = SYSCTL_OUT(req, w_notrunning, sizeof(w_notrunning));
 2731                 return (error);
 2732         }
 2733         if (witness_cold) {
 2734                 error = SYSCTL_OUT(req, w_stillcold, sizeof(w_stillcold));
 2735                 return (error);
 2736         }
 2737         error = 0;
 2738 
 2739         error = sysctl_wire_old_buffer(req, 0);
 2740         if (error != 0)
 2741                 return (error);
 2742         sb = sbuf_new_for_sysctl(NULL, NULL, FULLGRAPH_SBUF_SIZE, req);
 2743         if (sb == NULL)
 2744                 return (ENOMEM);
 2745         sbuf_printf(sb, "\n");
 2746 
 2747         mtx_lock_spin(&w_mtx);
 2748         STAILQ_FOREACH(w, &w_all, w_list)
 2749                 w->w_displayed = 0;
 2750         STAILQ_FOREACH(w, &w_all, w_list)
 2751                 witness_add_fullgraph(sb, w);
 2752         mtx_unlock_spin(&w_mtx);
 2753 
 2754         /*
 2755          * Close the sbuf and return to userland.
 2756          */
 2757         error = sbuf_finish(sb);
 2758         sbuf_delete(sb);
 2759 
 2760         return (error);
 2761 }
 2762 
 2763 static int
 2764 sysctl_debug_witness_watch(SYSCTL_HANDLER_ARGS)
 2765 {
 2766         int error, value;
 2767 
 2768         value = witness_watch;
 2769         error = sysctl_handle_int(oidp, &value, 0, req);
 2770         if (error != 0 || req->newptr == NULL)
 2771                 return (error);
 2772         if (value > 1 || value < -1 ||
 2773             (witness_watch == -1 && value != witness_watch))
 2774                 return (EINVAL);
 2775         witness_watch = value;
 2776         return (0);
 2777 }
 2778 
 2779 static void
 2780 witness_add_fullgraph(struct sbuf *sb, struct witness *w)
 2781 {
 2782         int i;
 2783 
 2784         if (w->w_displayed != 0 || (w->w_file == NULL && w->w_line == 0))
 2785                 return;
 2786         w->w_displayed = 1;
 2787 
 2788         WITNESS_INDEX_ASSERT(w->w_index);
 2789         for (i = 1; i <= w_max_used_index; i++) {
 2790                 if (w_rmatrix[w->w_index][i] & WITNESS_PARENT) {
 2791                         sbuf_printf(sb, "\"%s\",\"%s\"\n", w->w_name,
 2792                             w_data[i].w_name);
 2793                         witness_add_fullgraph(sb, &w_data[i]);
 2794                 }
 2795         }
 2796 }
 2797 
 2798 /*
 2799  * A simple hash function. Takes a key pointer and a key size. If size == 0,
 2800  * interprets the key as a string and reads until the null
 2801  * terminator. Otherwise, reads the first size bytes. Returns an unsigned 32-bit
 2802  * hash value computed from the key.
 2803  */
 2804 static uint32_t
 2805 witness_hash_djb2(const uint8_t *key, uint32_t size)
 2806 {
 2807         unsigned int hash = 5381;
 2808         int i;
 2809 
 2810         /* hash = hash * 33 + key[i] */
 2811         if (size)
 2812                 for (i = 0; i < size; i++)
 2813                         hash = ((hash << 5) + hash) + (unsigned int)key[i];
 2814         else
 2815                 for (i = 0; key[i] != 0; i++)
 2816                         hash = ((hash << 5) + hash) + (unsigned int)key[i];
 2817 
 2818         return (hash);
 2819 }
 2820 
 2821 
 2822 /*
 2823  * Initializes the two witness hash tables. Called exactly once from
 2824  * witness_initialize().
 2825  */
 2826 static void
 2827 witness_init_hash_tables(void)
 2828 {
 2829         int i;
 2830 
 2831         MPASS(witness_cold);
 2832 
 2833         /* Initialize the hash tables. */
 2834         for (i = 0; i < WITNESS_HASH_SIZE; i++)
 2835                 w_hash.wh_array[i] = NULL;
 2836 
 2837         w_hash.wh_size = WITNESS_HASH_SIZE;
 2838         w_hash.wh_count = 0;
 2839 
 2840         /* Initialize the lock order data hash. */
 2841         w_lofree = NULL;
 2842         for (i = 0; i < WITNESS_LO_DATA_COUNT; i++) {
 2843                 memset(&w_lodata[i], 0, sizeof(w_lodata[i]));
 2844                 w_lodata[i].wlod_next = w_lofree;
 2845                 w_lofree = &w_lodata[i];
 2846         }
 2847         w_lohash.wloh_size = WITNESS_LO_HASH_SIZE;
 2848         w_lohash.wloh_count = 0;
 2849         for (i = 0; i < WITNESS_LO_HASH_SIZE; i++)
 2850                 w_lohash.wloh_array[i] = NULL;
 2851 }
 2852 
 2853 static struct witness *
 2854 witness_hash_get(const char *key)
 2855 {
 2856         struct witness *w;
 2857         uint32_t hash;
 2858         
 2859         MPASS(key != NULL);
 2860         if (witness_cold == 0)
 2861                 mtx_assert(&w_mtx, MA_OWNED);
 2862         hash = witness_hash_djb2(key, 0) % w_hash.wh_size;
 2863         w = w_hash.wh_array[hash];
 2864         while (w != NULL) {
 2865                 if (strcmp(w->w_name, key) == 0)
 2866                         goto out;
 2867                 w = w->w_hash_next;
 2868         }
 2869 
 2870 out:
 2871         return (w);
 2872 }
 2873 
 2874 static void
 2875 witness_hash_put(struct witness *w)
 2876 {
 2877         uint32_t hash;
 2878 
 2879         MPASS(w != NULL);
 2880         MPASS(w->w_name != NULL);
 2881         if (witness_cold == 0)
 2882                 mtx_assert(&w_mtx, MA_OWNED);
 2883         KASSERT(witness_hash_get(w->w_name) == NULL,
 2884             ("%s: trying to add a hash entry that already exists!", __func__));
 2885         KASSERT(w->w_hash_next == NULL,
 2886             ("%s: w->w_hash_next != NULL", __func__));
 2887 
 2888         hash = witness_hash_djb2(w->w_name, 0) % w_hash.wh_size;
 2889         w->w_hash_next = w_hash.wh_array[hash];
 2890         w_hash.wh_array[hash] = w;
 2891         w_hash.wh_count++;
 2892 }
 2893 
 2894 
 2895 static struct witness_lock_order_data *
 2896 witness_lock_order_get(struct witness *parent, struct witness *child)
 2897 {
 2898         struct witness_lock_order_data *data = NULL;
 2899         struct witness_lock_order_key key;
 2900         unsigned int hash;
 2901 
 2902         MPASS(parent != NULL && child != NULL);
 2903         key.from = parent->w_index;
 2904         key.to = child->w_index;
 2905         WITNESS_INDEX_ASSERT(key.from);
 2906         WITNESS_INDEX_ASSERT(key.to);
 2907         if ((w_rmatrix[parent->w_index][child->w_index]
 2908             & WITNESS_LOCK_ORDER_KNOWN) == 0)
 2909                 goto out;
 2910 
 2911         hash = witness_hash_djb2((const char*)&key,
 2912             sizeof(key)) % w_lohash.wloh_size;
 2913         data = w_lohash.wloh_array[hash];
 2914         while (data != NULL) {
 2915                 if (witness_lock_order_key_equal(&data->wlod_key, &key))
 2916                         break;
 2917                 data = data->wlod_next;
 2918         }
 2919 
 2920 out:
 2921         return (data);
 2922 }
 2923 
 2924 /*
 2925  * Verify that parent and child have a known relationship, are not the same,
 2926  * and child is actually a child of parent.  This is done without w_mtx
 2927  * to avoid contention in the common case.
 2928  */
 2929 static int
 2930 witness_lock_order_check(struct witness *parent, struct witness *child)
 2931 {
 2932 
 2933         if (parent != child &&
 2934             w_rmatrix[parent->w_index][child->w_index]
 2935             & WITNESS_LOCK_ORDER_KNOWN &&
 2936             isitmychild(parent, child))
 2937                 return (1);
 2938 
 2939         return (0);
 2940 }
 2941 
 2942 static int
 2943 witness_lock_order_add(struct witness *parent, struct witness *child)
 2944 {
 2945         struct witness_lock_order_data *data = NULL;
 2946         struct witness_lock_order_key key;
 2947         unsigned int hash;
 2948         
 2949         MPASS(parent != NULL && child != NULL);
 2950         key.from = parent->w_index;
 2951         key.to = child->w_index;
 2952         WITNESS_INDEX_ASSERT(key.from);
 2953         WITNESS_INDEX_ASSERT(key.to);
 2954         if (w_rmatrix[parent->w_index][child->w_index]
 2955             & WITNESS_LOCK_ORDER_KNOWN)
 2956                 return (1);
 2957 
 2958         hash = witness_hash_djb2((const char*)&key,
 2959             sizeof(key)) % w_lohash.wloh_size;
 2960         w_rmatrix[parent->w_index][child->w_index] |= WITNESS_LOCK_ORDER_KNOWN;
 2961         data = w_lofree;
 2962         if (data == NULL)
 2963                 return (0);
 2964         w_lofree = data->wlod_next;
 2965         data->wlod_next = w_lohash.wloh_array[hash];
 2966         data->wlod_key = key;
 2967         w_lohash.wloh_array[hash] = data;
 2968         w_lohash.wloh_count++;
 2969         stack_zero(&data->wlod_stack);
 2970         stack_save(&data->wlod_stack);
 2971         return (1);
 2972 }
 2973 
 2974 /* Call this whenever the structure of the witness graph changes. */
 2975 static void
 2976 witness_increment_graph_generation(void)
 2977 {
 2978 
 2979         if (witness_cold == 0)
 2980                 mtx_assert(&w_mtx, MA_OWNED);
 2981         w_generation++;
 2982 }
 2983 
 2984 static int
 2985 witness_output_drain(void *arg __unused, const char *data, int len)
 2986 {
 2987 
 2988         witness_output("%.*s", len, data);
 2989         return (len);
 2990 }
 2991 
 2992 static void
 2993 witness_debugger(int cond, const char *msg)
 2994 {
 2995         char buf[32];
 2996         struct sbuf sb;
 2997         struct stack st;
 2998 
 2999         if (!cond)
 3000                 return;
 3001 
 3002         if (witness_trace) {
 3003                 sbuf_new(&sb, buf, sizeof(buf), SBUF_FIXEDLEN);
 3004                 sbuf_set_drain(&sb, witness_output_drain, NULL);
 3005 
 3006                 stack_zero(&st);
 3007                 stack_save(&st);
 3008                 witness_output("stack backtrace:\n");
 3009                 stack_sbuf_print_ddb(&sb, &st);
 3010 
 3011                 sbuf_finish(&sb);
 3012         }
 3013 
 3014 #ifdef KDB
 3015         if (witness_kdb)
 3016                 kdb_enter(KDB_WHY_WITNESS, msg);
 3017 #endif
 3018 }

Cache object: a196faf3f9b7aec288f938fc5b490bfe


[ 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.