sys/kern/subr_witness.c

   1 /*-
   2  * Copyright (c) 1998 Berkeley Software Design, Inc. All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   7  * 1. Redistributions of source code must retain the above copyright
   8  *    notice, this list of conditions and the following disclaimer.
   9  * 2. Redistributions in binary form must reproduce the above copyright
  10  *    notice, this list of conditions and the following disclaimer in the
  11  *    documentation and/or other materials provided with the distribution.
  12  * 3. Berkeley Software Design Inc's name may not be used to endorse or
  13  *    promote products derived from this software without specific prior
  14  *    written permission.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY BERKELEY SOFTWARE DESIGN INC ``AS IS'' AND
  17  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  18  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  19  * ARE DISCLAIMED.  IN NO EVENT SHALL BERKELEY SOFTWARE DESIGN INC BE LIABLE
  20  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  21  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  22  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  23  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  24  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  25  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  26  * SUCH DAMAGE.
  27  *
  28  *      from BSDI $Id: mutex_witness.c,v 1.1.2.20 2000/04/27 03:10:27 cp Exp $
  29  *      and BSDI $Id: synch_machdep.c,v 2.3.2.39 2000/04/27 03:10:25 cp Exp $
  30  */
  31
  32 /*
  33  * Implementation of the `witness' lock verifier.  Originally implemented for
  34  * mutexes in BSD/OS.  Extended to handle generic lock objects and lock
  35  * classes in FreeBSD.
  36  */
  37
  38 /*
  39  *      Main Entry: witness
  40  *      Pronunciation: 'wit-n&s
  41  *      Function: noun
  42  *      Etymology: Middle English witnesse, from Old English witnes knowledge,
  43  *          testimony, witness, from 2wit
  44  *      Date: before 12th century
  45  *      1 : attestation of a fact or event : TESTIMONY
  46  *      2 : one that gives evidence; specifically : one who testifies in
  47  *          a cause or before a judicial tribunal
  48  *      3 : one asked to be present at a transaction so as to be able to
  49  *          testify to its having taken place
  50  *      4 : one who has personal knowledge of something
  51  *      5 a : something serving as evidence or proof : SIGN
  52  *        b : public affirmation by word or example of usually
  53  *            religious faith or conviction <the heroic witness to divine
  54  *            life -- Pilot>
  55  *      6 capitalized : a member of the Jehovah's Witnesses
  56  */
  57
  58 /*
  59  * Special rules concerning Giant and lock orders:
  60  *
  61  * 1) Giant must be acquired before any other mutexes.  Stated another way,
  62  *    no other mutex may be held when Giant is acquired.
  63  *
  64  * 2) Giant must be released when blocking on a sleepable lock.
  65  *
  66  * This rule is less obvious, but is a result of Giant providing the same
  67  * semantics as spl().  Basically, when a thread sleeps, it must release
  68  * Giant.  When a thread blocks on a sleepable lock, it sleeps.  Hence rule
  69  * 2).
  70  *
  71  * 3) Giant may be acquired before or after sleepable locks.
  72  *
  73  * This rule is also not quite as obvious.  Giant may be acquired after
  74  * a sleepable lock because it is a non-sleepable lock and non-sleepable
  75  * locks may always be acquired while holding a sleepable lock.  The second
  76  * case, Giant before a sleepable lock, follows from rule 2) above.  Suppose
  77  * you have two threads T1 and T2 and a sleepable lock X.  Suppose that T1
  78  * acquires X and blocks on Giant.  Then suppose that T2 acquires Giant and
  79  * blocks on X.  When T2 blocks on X, T2 will release Giant allowing T1 to
  80  * execute.  Thus, acquiring Giant both before and after a sleepable lock
  81  * will not result in a lock order reversal.
  82  */
  83
  84 #include <sys/cdefs.h>
  85 __FBSDID("$FreeBSD$");
  86
  87 #include "opt_ddb.h"
  88 #include "opt_hwpmc_hooks.h"
  89 #include "opt_witness.h"
  90
  91 #include <sys/param.h>
  92 #include <sys/bus.h>
  93 #include <sys/kdb.h>
  94 #include <sys/kernel.h>
  95 #include <sys/ktr.h>
  96 #include <sys/lock.h>
  97 #include <sys/malloc.h>
  98 #include <sys/mutex.h>
  99 #include <sys/priv.h>
 100 #include <sys/proc.h>
 101 #include <sys/sbuf.h>
 102 #include <sys/sysctl.h>
 103 #include <sys/systm.h>
 104
 105 #include <ddb/ddb.h>
 106
 107 #include <machine/stdarg.h>
 108
 109 /* Note that these traces do not work with KTR_ALQ. */
 110 #if 0
 111 #define KTR_WITNESS     KTR_SUBSYS
 112 #else
 113 #define KTR_WITNESS     0
 114 #endif
 115
 116 #define LI_RECURSEMASK  0x0000ffff      /* Recursion depth of lock instance. */
 117 #define LI_EXCLUSIVE    0x00010000      /* Exclusive lock instance. */
 118
 119 /* Define this to check for blessed mutexes */
 120 #undef BLESSING
 121
 122 #define WITNESS_COUNT 1024
 123 #define WITNESS_CHILDCOUNT (WITNESS_COUNT * 4)
 124 #define WITNESS_SBUFSIZE        32768
 125 #define WITNESS_PENDLIST        512
 126 /*
 127  * XXX: This is somewhat bogus, as we assume here that at most 1024 threads
 128  * will hold LOCK_NCHILDREN * 2 locks.  We handle failure ok, and we should
 129  * probably be safe for the most part, but it's still a SWAG.
 130  */
 131 #define LOCK_CHILDCOUNT (MAXCPU + 1024) * 2
 132
 133 #define WITNESS_NCHILDREN 6
 134
 135 #define LOCK_NCHILDREN  3
 136
 137 struct witness_child_list_entry;
 138
 139 /*
 140  * Lock instances.  A lock instance is the data associated with a lock while
 141  * it is held by witness.  For example, a lock instance will hold the
 142  * recursion count of a lock.  Lock instances are held in lists.  Spin locks
 143  * are held in a per-cpu list while sleep locks are held in per-thread list.
 144  */
 145 struct lock_instance {
 146         struct lock_object *li_lock;
 147         const char      *li_file;
 148         int             li_line;
 149         u_int           li_flags;       /* Recursion count and LI_* flags. */
 150 };
 151
 152 /*
 153  * A simple list type used to build the list of locks held by a thread
 154  * or CPU.  We can't simply embed the list in struct lock_object since a
 155  * lock may be held by more than one thread if it is a shared lock.  Locks
 156  * are added to the head of the list, so we fill up each list entry from
 157  * "the back" logically.  To ease some of the arithmetic, we actually fill
 158  * in each list entry the normal way (children[0] then children[1], etc.) but
 159  * when we traverse the list we read children[count-1] as the first entry
 160  * down to children[0] as the final entry.
 161  */
 162 struct lock_list_entry {
 163         struct lock_list_entry  *ll_next;
 164         struct lock_instance    ll_children[LOCK_NCHILDREN];
 165         u_int                   ll_count;
 166 };
 167
 168 struct witness {
 169         const   char *w_name;
 170         struct  lock_class *w_class;
 171         STAILQ_ENTRY(witness) w_list;           /* List of all witnesses. */
 172         STAILQ_ENTRY(witness) w_typelist;       /* Witnesses of a type. */
 173         struct  witness_child_list_entry *w_children;   /* Great evilness... */
 174         const   char *w_file;
 175         int     w_line;
 176         u_int   w_level;
 177         u_int   w_refcount;
 178         u_char  w_Giant_squawked:1;
 179         u_char  w_other_squawked:1;
 180         u_char  w_same_squawked:1;
 181         u_char  w_displayed:1;
 182 };
 183
 184 struct witness_child_list_entry {
 185         struct  witness_child_list_entry *wcl_next;
 186         struct  witness *wcl_children[WITNESS_NCHILDREN];
 187         u_int   wcl_count;
 188 };
 189
 190 STAILQ_HEAD(witness_list, witness);
 191
 192 #ifdef BLESSING
 193 struct witness_blessed {
 194         const   char *b_lock1;
 195         const   char *b_lock2;
 196 };
 197 #endif
 198
 199 struct witness_order_list_entry {
 200         const   char *w_name;
 201         struct  lock_class *w_class;
 202 };
 203
 204 struct witness_pendhelp {
 205         const char              *wh_type;
 206         struct lock_object      *wh_lock;
 207 };
 208
 209 #ifdef BLESSING
 210 static int      blessed(struct witness *, struct witness *);
 211 #endif
 212 static void     depart(struct witness *w);
 213 static struct   witness *enroll(const char *description,
 214                                 struct lock_class *lock_class);
 215 static int      insertchild(struct witness *parent, struct witness *child);
 216 static int      isitmychild(struct witness *parent, struct witness *child);
 217 static int      isitmydescendant(struct witness *parent, struct witness *child);
 218 static int      itismychild(struct witness *parent, struct witness *child);
 219 static void     removechild(struct witness *parent, struct witness *child);
 220 static int      sysctl_debug_witness_watch(SYSCTL_HANDLER_ARGS);
 221 static int      sysctl_debug_witness_graphs(SYSCTL_HANDLER_ARGS);
 222 static const char *fixup_filename(const char *file);
 223 static void     witness_addgraph(struct sbuf *sb, struct witness *parent);
 224 static struct   witness *witness_get(void);
 225 static void     witness_free(struct witness *m);
 226 static struct   witness_child_list_entry *witness_child_get(void);
 227 static void     witness_child_free(struct witness_child_list_entry *wcl);
 228 static struct   lock_list_entry *witness_lock_list_get(void);
 229 static void     witness_lock_list_free(struct lock_list_entry *lle);
 230 static struct   lock_instance *find_instance(struct lock_list_entry *lock_list,
 231                                              struct lock_object *lock);
 232 static void     witness_list_lock(struct lock_instance *instance);
 233 #ifdef DDB
 234 static void     witness_leveldescendents(struct witness *parent, int level);
 235 static void     witness_levelall(void);
 236 static void     witness_displaydescendants(void(*)(const char *fmt, ...),
 237                                            struct witness *, int indent);
 238 static void     witness_display_list(void(*prnt)(const char *fmt, ...),
 239                                      struct witness_list *list);
 240 static void     witness_display(void(*)(const char *fmt, ...));
 241 static void     witness_list(struct thread *td);
 242 #endif
 243
 244 SYSCTL_NODE(_debug, OID_AUTO, witness, CTLFLAG_RW, 0, "Witness Locking");
 245
 246 /*
 247  * If set to 0, witness is disabled.  If set to a non-zero value, witness
 248  * performs full lock order checking for all locks.  At runtime, this
 249  * value may be set to 0 to turn off witness.  witness is not allowed be
 250  * turned on once it is turned off, however.
 251  */
 252 static int witness_watch = 1;
 253 TUNABLE_INT("debug.witness.watch", &witness_watch);
 254 SYSCTL_PROC(_debug_witness, OID_AUTO, watch, CTLFLAG_RW | CTLTYPE_INT, NULL, 0,
 255     sysctl_debug_witness_watch, "I", "witness is watching lock operations");
 256 SYSCTL_PROC(_debug_witness, OID_AUTO, graphs, CTLTYPE_STRING | CTLFLAG_RD,
 257     NULL, 0, sysctl_debug_witness_graphs, "A", "Show locks relation graphs");
 258
 259 #ifdef KDB
 260 /*
 261  * When KDB is enabled and witness_kdb is set to 1, it will cause the system
 262  * to drop into kdebug() when:
 263  *      - a lock hierarchy violation occurs
 264  *      - locks are held when going to sleep.
 265  */
 266 #ifdef WITNESS_KDB
 267 int     witness_kdb = 1;
 268 #else
 269 int     witness_kdb = 0;
 270 #endif
 271 TUNABLE_INT("debug.witness.kdb", &witness_kdb);
 272 SYSCTL_INT(_debug_witness, OID_AUTO, kdb, CTLFLAG_RW, &witness_kdb, 0, "");
 273
 274 /*
 275  * When KDB is enabled and witness_trace is set to 1, it will cause the system
 276  * to print a stack trace:
 277  *      - a lock hierarchy violation occurs
 278  *      - locks are held when going to sleep.
 279  */
 280 int     witness_trace = 1;
 281 TUNABLE_INT("debug.witness.trace", &witness_trace);
 282 SYSCTL_INT(_debug_witness, OID_AUTO, trace, CTLFLAG_RW, &witness_trace, 0, "");
 283 #endif /* KDB */
 284
 285 #ifdef WITNESS_SKIPSPIN
 286 int     witness_skipspin = 1;
 287 #else
 288 int     witness_skipspin = 0;
 289 #endif
 290 TUNABLE_INT("debug.witness.skipspin", &witness_skipspin);
 291 SYSCTL_INT(_debug_witness, OID_AUTO, skipspin, CTLFLAG_RDTUN,
 292     &witness_skipspin, 0, "");
 293
 294 static struct mtx w_mtx;
 295 static struct witness_list w_free = STAILQ_HEAD_INITIALIZER(w_free);
 296 static struct witness_list w_all = STAILQ_HEAD_INITIALIZER(w_all);
 297 static struct witness_list w_spin = STAILQ_HEAD_INITIALIZER(w_spin);
 298 static struct witness_list w_sleep = STAILQ_HEAD_INITIALIZER(w_sleep);
 299 static struct witness_child_list_entry *w_child_free = NULL;
 300 static struct lock_list_entry *w_lock_list_free = NULL;
 301 static struct witness_pendhelp pending_locks[WITNESS_PENDLIST];
 302 static u_int pending_cnt;
 303
 304 static int w_free_cnt, w_spin_cnt, w_sleep_cnt, w_child_free_cnt, w_child_cnt;
 305 SYSCTL_INT(_debug_witness, OID_AUTO, free_cnt, CTLFLAG_RD, &w_free_cnt, 0, "");
 306 SYSCTL_INT(_debug_witness, OID_AUTO, spin_cnt, CTLFLAG_RD, &w_spin_cnt, 0, "");
 307 SYSCTL_INT(_debug_witness, OID_AUTO, sleep_cnt, CTLFLAG_RD, &w_sleep_cnt, 0,
 308     "");
 309 SYSCTL_INT(_debug_witness, OID_AUTO, child_free_cnt, CTLFLAG_RD,
 310     &w_child_free_cnt, 0, "");
 311 SYSCTL_INT(_debug_witness, OID_AUTO, child_cnt, CTLFLAG_RD, &w_child_cnt, 0,
 312     "");
 313
 314 static struct witness w_data[WITNESS_COUNT];
 315 static struct witness_child_list_entry w_childdata[WITNESS_CHILDCOUNT];
 316 static struct lock_list_entry w_locklistdata[LOCK_CHILDCOUNT];
 317
 318 static struct witness_order_list_entry order_lists[] = {
 319         /*
 320          * sx locks
 321          */
 322         { "proctree", &lock_class_sx },
 323         { "allproc", &lock_class_sx },
 324         { "allprison", &lock_class_sx },
 325         { NULL, NULL },
 326         /*
 327          * Various mutexes
 328          */
 329         { "Giant", &lock_class_mtx_sleep },
 330         { "pipe mutex", &lock_class_mtx_sleep },
 331         { "sigio lock", &lock_class_mtx_sleep },
 332         { "process group", &lock_class_mtx_sleep },
 333         { "process lock", &lock_class_mtx_sleep },
 334         { "session", &lock_class_mtx_sleep },
 335         { "uidinfo hash", &lock_class_rw },
 336 #ifdef  HWPMC_HOOKS
 337         { "pmc-sleep", &lock_class_mtx_sleep },
 338 #endif
 339         { NULL, NULL },
 340         /*
 341          * Sockets
 342          */
 343         { "accept", &lock_class_mtx_sleep },
 344         { "so_snd", &lock_class_mtx_sleep },
 345         { "so_rcv", &lock_class_mtx_sleep },
 346         { "sellck", &lock_class_mtx_sleep },
 347         { NULL, NULL },
 348         /*
 349          * Routing
 350          */
 351         { "so_rcv", &lock_class_mtx_sleep },
 352         { "radix node head", &lock_class_mtx_sleep },
 353         { "rtentry", &lock_class_mtx_sleep },
 354         { "ifaddr", &lock_class_mtx_sleep },
 355         { NULL, NULL },
 356         /*
 357          * Multicast - protocol locks before interface locks, after UDP locks.
 358          */
 359         { "udpinp", &lock_class_rw },
 360         { "in_multi_mtx", &lock_class_mtx_sleep },
 361         { "igmp_mtx", &lock_class_mtx_sleep },
 362         { "if_addr_mtx", &lock_class_mtx_sleep },
 363         { NULL, NULL },
 364         /*
 365          * UNIX Domain Sockets
 366          */
 367         { "unp", &lock_class_mtx_sleep },
 368         { "so_snd", &lock_class_mtx_sleep },
 369         { NULL, NULL },
 370         /*
 371          * UDP/IP
 372          */
 373         { "udp", &lock_class_rw },
 374         { "udpinp", &lock_class_rw },
 375         { "so_snd", &lock_class_mtx_sleep },
 376         { NULL, NULL },
 377         /*
 378          * TCP/IP
 379          */
 380         { "tcp", &lock_class_rw },
 381         { "tcpinp", &lock_class_rw },
 382         { "so_snd", &lock_class_mtx_sleep },
 383         { NULL, NULL },
 384         /*
 385          * SLIP
 386          */
 387         { "slip_mtx", &lock_class_mtx_sleep },
 388         { "slip sc_mtx", &lock_class_mtx_sleep },
 389         { NULL, NULL },
 390         /*
 391          * netatalk
 392          */
 393         { "ddp_list_mtx", &lock_class_mtx_sleep },
 394         { "ddp_mtx", &lock_class_mtx_sleep },
 395         { NULL, NULL },
 396         /*
 397          * BPF
 398          */
 399         { "bpf global lock", &lock_class_mtx_sleep },
 400         { "bpf interface lock", &lock_class_mtx_sleep },
 401         { "bpf cdev lock", &lock_class_mtx_sleep },
 402         { NULL, NULL },
 403         /*
 404          * NFS server
 405          */
 406         { "nfsd_mtx", &lock_class_mtx_sleep },
 407         { "so_snd", &lock_class_mtx_sleep },
 408         { NULL, NULL },
 409
 410         /*
 411          * IEEE 802.11
 412          */
 413         { "802.11 com lock", &lock_class_mtx_sleep},
 414         { NULL, NULL },
 415         /*
 416          * Network drivers
 417          */
 418         { "network driver", &lock_class_mtx_sleep},
 419         { NULL, NULL },
 420
 421         /*
 422          * Netgraph
 423          */
 424         { "ng_node", &lock_class_mtx_sleep },
 425         { "ng_worklist", &lock_class_mtx_sleep },
 426         { NULL, NULL },
 427         /*
 428          * CDEV
 429          */
 430         { "system map", &lock_class_mtx_sleep },
 431         { "vm page queue mutex", &lock_class_mtx_sleep },
 432         { "vnode interlock", &lock_class_mtx_sleep },
 433         { "cdev", &lock_class_mtx_sleep },
 434         { NULL, NULL },
 435         /*
 436          * kqueue/VFS interaction
 437          */
 438         { "kqueue", &lock_class_mtx_sleep },
 439         { "struct mount mtx", &lock_class_mtx_sleep },
 440         { "vnode interlock", &lock_class_mtx_sleep },
 441         { NULL, NULL },
 442         /*
 443          * spin locks
 444          */
 445 #ifdef SMP
 446         { "ap boot", &lock_class_mtx_spin },
 447 #endif
 448         { "rm.mutex_mtx", &lock_class_mtx_spin },
 449         { "sio", &lock_class_mtx_spin },
 450         { "scrlock", &lock_class_mtx_spin },
 451 #ifdef __i386__
 452         { "cy", &lock_class_mtx_spin },
 453 #endif
 454 #ifdef __sparc64__
 455         { "pcib_mtx", &lock_class_mtx_spin },
 456         { "rtc_mtx", &lock_class_mtx_spin },
 457 #endif
 458         { "scc_hwmtx", &lock_class_mtx_spin },
 459         { "uart_hwmtx", &lock_class_mtx_spin },
 460         { "fast_taskqueue", &lock_class_mtx_spin },
 461         { "intr table", &lock_class_mtx_spin },
 462 #ifdef  HWPMC_HOOKS
 463         { "pmc-per-proc", &lock_class_mtx_spin },
 464 #endif
 465         { "process slock", &lock_class_mtx_spin },
 466         { "sleepq chain", &lock_class_mtx_spin },
 467         { "umtx lock", &lock_class_mtx_spin },
 468         { "rm_spinlock", &lock_class_mtx_spin },
 469         { "turnstile chain", &lock_class_mtx_spin },
 470         { "turnstile lock", &lock_class_mtx_spin },
 471         { "sched lock", &lock_class_mtx_spin },
 472         { "td_contested", &lock_class_mtx_spin },
 473         { "callout", &lock_class_mtx_spin },
 474         { "entropy harvest mutex", &lock_class_mtx_spin },
 475         { "syscons video lock", &lock_class_mtx_spin },
 476         { "time lock", &lock_class_mtx_spin },
 477 #ifdef SMP
 478         { "smp rendezvous", &lock_class_mtx_spin },
 479 #endif
 480 #ifdef __powerpc__
 481         { "tlb0", &lock_class_mtx_spin },
 482 #endif
 483         /*
 484          * leaf locks
 485          */
 486         { "intrcnt", &lock_class_mtx_spin },
 487         { "icu", &lock_class_mtx_spin },
 488 #if defined(SMP) && defined(__sparc64__)
 489         { "ipi", &lock_class_mtx_spin },
 490 #endif
 491 #ifdef __i386__
 492         { "allpmaps", &lock_class_mtx_spin },
 493         { "descriptor tables", &lock_class_mtx_spin },
 494 #endif
 495         { "clk", &lock_class_mtx_spin },
 496         { "cpuset", &lock_class_mtx_spin },
 497         { "mprof lock", &lock_class_mtx_spin },
 498         { "zombie lock", &lock_class_mtx_spin },
 499         { "ALD Queue", &lock_class_mtx_spin },
 500 #ifdef __ia64__
 501         { "MCA spin lock", &lock_class_mtx_spin },
 502 #endif
 503 #if defined(__i386__) || defined(__amd64__)
 504         { "pcicfg", &lock_class_mtx_spin },
 505         { "NDIS thread lock", &lock_class_mtx_spin },
 506 #endif
 507         { "tw_osl_io_lock", &lock_class_mtx_spin },
 508         { "tw_osl_q_lock", &lock_class_mtx_spin },
 509         { "tw_cl_io_lock", &lock_class_mtx_spin },
 510         { "tw_cl_intr_lock", &lock_class_mtx_spin },
 511         { "tw_cl_gen_lock", &lock_class_mtx_spin },
 512 #ifdef  HWPMC_HOOKS
 513         { "pmc-leaf", &lock_class_mtx_spin },
 514 #endif
 515         { "blocked lock", &lock_class_mtx_spin },
 516         { NULL, NULL },
 517         { NULL, NULL }
 518 };
 519
 520 #ifdef BLESSING
 521 /*
 522  * Pairs of locks which have been blessed
 523  * Don't complain about order problems with blessed locks
 524  */
 525 static struct witness_blessed blessed_list[] = {
 526 };
 527 static int blessed_count =
 528         sizeof(blessed_list) / sizeof(struct witness_blessed);
 529 #endif
 530
 531 /*
 532  * This global is set to 0 once it becomes safe to use the witness code.
 533  */
 534 static int witness_cold = 1;
 535
 536 /*
 537  * This global is set to 1 once the static lock orders have been enrolled
 538  * so that a warning can be issued for any spin locks enrolled later.
 539  */
 540 static int witness_spin_warn = 0;
 541
 542 /*
 543  * The WITNESS-enabled diagnostic code.  Note that the witness code does
 544  * assume that the early boot is single-threaded at least until after this
 545  * routine is completed.
 546  */
 547 static void
 548 witness_initialize(void *dummy __unused)
 549 {
 550         struct lock_object *lock;
 551         struct witness_order_list_entry *order;
 552         struct witness *w, *w1;
 553         int i;
 554
 555         /*
 556          * We have to release Giant before initializing its witness
 557          * structure so that WITNESS doesn't get confused.
 558          */
 559         mtx_unlock(&Giant);
 560         mtx_assert(&Giant, MA_NOTOWNED);
 561
 562         CTR1(KTR_WITNESS, "%s: initializing witness", __func__);
 563         mtx_init(&w_mtx, "witness lock", NULL, MTX_SPIN | MTX_QUIET |
 564             MTX_NOWITNESS | MTX_NOPROFILE);
 565         for (i = 0; i < WITNESS_COUNT; i++)
 566                 witness_free(&w_data[i]);
 567         for (i = 0; i < WITNESS_CHILDCOUNT; i++)
 568                 witness_child_free(&w_childdata[i]);
 569         for (i = 0; i < LOCK_CHILDCOUNT; i++)
 570                 witness_lock_list_free(&w_locklistdata[i]);
 571
 572         /* First add in all the specified order lists. */
 573         for (order = order_lists; order->w_name != NULL; order++) {
 574                 w = enroll(order->w_name, order->w_class);
 575                 if (w == NULL)
 576                         continue;
 577                 w->w_file = "order list";
 578                 for (order++; order->w_name != NULL; order++) {
 579                         w1 = enroll(order->w_name, order->w_class);
 580                         if (w1 == NULL)
 581                                 continue;
 582                         w1->w_file = "order list";
 583                         if (!itismychild(w, w1))
 584                                 panic("Not enough memory for static orders!");
 585                         w = w1;
 586                 }
 587         }
 588         witness_spin_warn = 1;
 589
 590         /* Iterate through all locks and add them to witness. */
 591         for (i = 0; pending_locks[i].wh_lock != NULL; i++) {
 592                 lock = pending_locks[i].wh_lock;
 593                 KASSERT(lock->lo_flags & LO_WITNESS,
 594                     ("%s: lock %s is on pending list but not LO_WITNESS",
 595                     __func__, lock->lo_name));
 596                 lock->lo_witness = enroll(pending_locks[i].wh_type,
 597                     LOCK_CLASS(lock));
 598         }
 599
 600         /* Mark the witness code as being ready for use. */
 601         witness_cold = 0;
 602
 603         mtx_lock(&Giant);
 604 }
 605 SYSINIT(witness_init, SI_SUB_WITNESS, SI_ORDER_FIRST, witness_initialize,
 606     NULL);
 607
 608 static int
 609 sysctl_debug_witness_watch(SYSCTL_HANDLER_ARGS)
 610 {
 611         int error, value;
 612
 613         value = witness_watch;
 614         error = sysctl_handle_int(oidp, &value, 0, req);
 615         if (error != 0 || req->newptr == NULL)
 616                 return (error);
 617         if (value == witness_watch)
 618                 return (0);
 619         if (value != 0)
 620                 return (EINVAL);
 621         witness_watch = 0;
 622         return (0);
 623 }
 624
 625 static int
 626 sysctl_debug_witness_graphs(SYSCTL_HANDLER_ARGS)
 627 {
 628         struct witness *w;
 629         struct sbuf *sb;
 630         int error;
 631
 632         KASSERT(witness_cold == 0, ("%s: witness is still cold", __func__));
 633
 634         sb = sbuf_new(NULL, NULL, WITNESS_SBUFSIZE, SBUF_FIXEDLEN);
 635         if (sb == NULL)
 636                 return (ENOMEM);
 637
 638         mtx_lock_spin(&w_mtx);
 639         STAILQ_FOREACH(w, &w_all, w_list)
 640                 w->w_displayed = 0;
 641         STAILQ_FOREACH(w, &w_all, w_list)
 642                 witness_addgraph(sb, w);
 643         mtx_unlock_spin(&w_mtx);
 644
 645         if (sbuf_overflowed(sb)) {
 646                 sbuf_delete(sb);
 647                 panic("%s: sbuf overflowed, bump the static buffer size\n",
 648                     __func__);
 649         }
 650
 651         sbuf_finish(sb);
 652         error = SYSCTL_OUT(req, sbuf_data(sb), sbuf_len(sb) + 1);
 653         sbuf_delete(sb);
 654
 655         return (error);
 656 }
 657
 658 void
 659 witness_init(struct lock_object *lock, const char *type)
 660 {
 661         struct lock_class *class;
 662
 663         /* Various sanity checks. */
 664         class = LOCK_CLASS(lock);
 665         if ((lock->lo_flags & LO_RECURSABLE) != 0 &&
 666             (class->lc_flags & LC_RECURSABLE) == 0)
 667                 panic("%s: lock (%s) %s can not be recursable", __func__,
 668                     class->lc_name, lock->lo_name);
 669         if ((lock->lo_flags & LO_SLEEPABLE) != 0 &&
 670             (class->lc_flags & LC_SLEEPABLE) == 0)
 671                 panic("%s: lock (%s) %s can not be sleepable", __func__,
 672                     class->lc_name, lock->lo_name);
 673         if ((lock->lo_flags & LO_UPGRADABLE) != 0 &&
 674             (class->lc_flags & LC_UPGRADABLE) == 0)
 675                 panic("%s: lock (%s) %s can not be upgradable", __func__,
 676                     class->lc_name, lock->lo_name);
 677
 678         /*
 679          * If we shouldn't watch this lock, then just clear lo_witness.
 680          * Otherwise, if witness_cold is set, then it is too early to
 681          * enroll this lock, so defer it to witness_initialize() by adding
 682          * it to the pending_locks list.  If it is not too early, then enroll
 683          * the lock now.
 684          */
 685         if (witness_watch == 0 || panicstr != NULL ||
 686             (lock->lo_flags & LO_WITNESS) == 0)
 687                 lock->lo_witness = NULL;
 688         else if (witness_cold) {
 689                 pending_locks[pending_cnt].wh_lock = lock;
 690                 pending_locks[pending_cnt++].wh_type = type;
 691                 if (pending_cnt > WITNESS_PENDLIST)
 692                         panic("%s: pending locks list is too small, bump it\n",
 693                             __func__);
 694         } else
 695                 lock->lo_witness = enroll(type, class);
 696 }
 697
 698 void
 699 witness_destroy(struct lock_object *lock)
 700 {
 701         struct lock_class *class;
 702         struct witness *w;
 703
 704         class = LOCK_CLASS(lock);
 705         if (witness_cold)
 706                 panic("lock (%s) %s destroyed while witness_cold",
 707                     class->lc_name, lock->lo_name);
 708
 709         /* XXX: need to verify that no one holds the lock */
 710         if ((lock->lo_flags & LO_WITNESS) && lock->lo_witness != NULL) {
 711                 w = lock->lo_witness;
 712                 mtx_lock_spin(&w_mtx);
 713                 MPASS(w->w_refcount > 0);
 714                 w->w_refcount--;
 715
 716                 if (w->w_refcount == 0)
 717                         depart(w);
 718                 mtx_unlock_spin(&w_mtx);
 719         }
 720 }
 721
 722 #ifdef DDB
 723 static void
 724 witness_levelall (void)
 725 {
 726         struct witness_list *list;
 727         struct witness *w, *w1;
 728
 729         /*
 730          * First clear all levels.
 731          */
 732         STAILQ_FOREACH(w, &w_all, w_list) {
 733                 w->w_level = 0;
 734         }
 735
 736         /*
 737          * Look for locks with no parent and level all their descendants.
 738          */
 739         STAILQ_FOREACH(w, &w_all, w_list) {
 740                 /*
 741                  * This is just an optimization, technically we could get
 742                  * away just walking the all list each time.
 743                  */
 744                 if (w->w_class->lc_flags & LC_SLEEPLOCK)
 745                         list = &w_sleep;
 746                 else
 747                         list = &w_spin;
 748                 STAILQ_FOREACH(w1, list, w_typelist) {
 749                         if (isitmychild(w1, w))
 750                                 goto skip;
 751                 }
 752                 witness_leveldescendents(w, 0);
 753         skip:
 754                 ;       /* silence GCC 3.x */
 755         }
 756 }
 757
 758 static void
 759 witness_leveldescendents(struct witness *parent, int level)
 760 {
 761         struct witness_child_list_entry *wcl;
 762         int i;
 763
 764         if (parent->w_level < level)
 765                 parent->w_level = level;
 766         level++;
 767         for (wcl = parent->w_children; wcl != NULL; wcl = wcl->wcl_next)
 768                 for (i = 0; i < wcl->wcl_count; i++)
 769                         witness_leveldescendents(wcl->wcl_children[i], level);
 770 }
 771
 772 static void
 773 witness_displaydescendants(void(*prnt)(const char *fmt, ...),
 774                            struct witness *parent, int indent)
 775 {
 776         struct witness_child_list_entry *wcl;
 777         int i, level;
 778
 779         level = parent->w_level;
 780         prnt("%-2d", level);
 781         for (i = 0; i < indent; i++)
 782                 prnt(" ");
 783         if (parent->w_refcount > 0)
 784                 prnt("%s", parent->w_name);
 785         else
 786                 prnt("(dead)");
 787         if (parent->w_displayed) {
 788                 prnt(" -- (already displayed)\n");
 789                 return;
 790         }
 791         parent->w_displayed = 1;
 792         if (parent->w_refcount > 0) {
 793                 if (parent->w_file != NULL)
 794                         prnt(" -- last acquired @ %s:%d", parent->w_file,
 795                             parent->w_line);
 796         }
 797         prnt("\n");
 798         for (wcl = parent->w_children; wcl != NULL; wcl = wcl->wcl_next)
 799                 for (i = 0; i < wcl->wcl_count; i++)
 800                             witness_displaydescendants(prnt,
 801                                 wcl->wcl_children[i], indent + 1);
 802 }
 803
 804 static void
 805 witness_display_list(void(*prnt)(const char *fmt, ...),
 806                      struct witness_list *list)
 807 {
 808         struct witness *w;
 809
 810         STAILQ_FOREACH(w, list, w_typelist) {
 811                 if (w->w_file == NULL || w->w_level > 0)
 812                         continue;
 813                 /*
 814                  * This lock has no anscestors, display its descendants.
 815                  */
 816                 witness_displaydescendants(prnt, w, 0);
 817         }
 818 }
 819
 820 static void
 821 witness_addgraph(struct sbuf *sb, struct witness *parent)
 822 {
 823         struct witness_child_list_entry *wcl;
 824         int i;
 825
 826         if (parent->w_displayed != 0 || parent->w_refcount == 0 ||
 827             parent->w_file == NULL)
 828                 return;
 829
 830         parent->w_displayed = 1;
 831         for (wcl = parent->w_children; wcl != NULL; wcl = wcl->wcl_next)
 832                 for (i = 0; i < wcl->wcl_count; i++) {
 833                         sbuf_printf(sb, "\"%s\",\"%s\"\n", parent->w_name,
 834                             wcl->wcl_children[i]->w_name);
 835                         witness_addgraph(sb, wcl->wcl_children[i]);
 836                 }
 837 }
 838
 839 static void
 840 witness_display(void(*prnt)(const char *fmt, ...))
 841 {
 842         struct witness *w;
 843
 844         KASSERT(!witness_cold, ("%s: witness_cold", __func__));
 845         witness_levelall();
 846
 847         /* Clear all the displayed flags. */
 848         STAILQ_FOREACH(w, &w_all, w_list) {
 849                 w->w_displayed = 0;
 850         }
 851
 852         /*
 853          * First, handle sleep locks which have been acquired at least
 854          * once.
 855          */
 856         prnt("Sleep locks:\n");
 857         witness_display_list(prnt, &w_sleep);
 858
 859         /*
 860          * Now do spin locks which have been acquired at least once.
 861          */
 862         prnt("\nSpin locks:\n");
 863         witness_display_list(prnt, &w_spin);
 864
 865         /*
 866          * Finally, any locks which have not been acquired yet.
 867          */
 868         prnt("\nLocks which were never acquired:\n");
 869         STAILQ_FOREACH(w, &w_all, w_list) {
 870                 if (w->w_file != NULL || w->w_refcount == 0)
 871                         continue;
 872                 prnt("%s\n", w->w_name);
 873         }
 874 }
 875 #endif /* DDB */
 876
 877 /* Trim useless garbage from filenames. */
 878 static const char *
 879 fixup_filename(const char *file)
 880 {
 881
 882         if (file == NULL)
 883                 return (NULL);
 884         while (strncmp(file, "../", 3) == 0)
 885                 file += 3;
 886         return (file);
 887 }
 888
 889 int
 890 witness_defineorder(struct lock_object *lock1, struct lock_object *lock2)
 891 {
 892
 893         if (witness_watch == 0 || panicstr != NULL)
 894                 return (0);
 895
 896         /* Require locks that witness knows about. */
 897         if (lock1 == NULL || lock1->lo_witness == NULL || lock2 == NULL ||
 898             lock2->lo_witness == NULL)
 899                 return (EINVAL);
 900
 901         MPASS(!mtx_owned(&w_mtx));
 902         mtx_lock_spin(&w_mtx);
 903
 904         /*
 905          * If we already have either an explicit or implied lock order that
 906          * is the other way around, then return an error.
 907          */
 908         if (isitmydescendant(lock2->lo_witness, lock1->lo_witness)) {
 909                 mtx_unlock_spin(&w_mtx);
 910                 return (EDOOFUS);
 911         }
 912
 913         /* Try to add the new order. */
 914         CTR3(KTR_WITNESS, "%s: adding %s as a child of %s", __func__,
 915             lock2->lo_witness->w_name, lock1->lo_witness->w_name);
 916         if (!itismychild(lock1->lo_witness, lock2->lo_witness))
 917                 return (ENOMEM);
 918         mtx_unlock_spin(&w_mtx);
 919         return (0);
 920 }
 921
 922 void
 923 witness_checkorder(struct lock_object *lock, int flags, const char *file,
 924     int line)
 925 {
 926         struct lock_list_entry **lock_list, *lle;
 927         struct lock_instance *lock1, *lock2;
 928         struct lock_class *class;
 929         struct witness *w, *w1;
 930         struct thread *td;
 931         int i, j;
 932
 933         if (witness_cold || witness_watch == 0 || lock->lo_witness == NULL ||
 934             panicstr != NULL)
 935                 return;
 936
 937         /*
 938          * Try locks do not block if they fail to acquire the lock, thus
 939          * there is no danger of deadlocks or of switching while holding a
 940          * spin lock if we acquire a lock via a try operation.  This
 941          * function shouldn't even be called for try locks, so panic if
 942          * that happens.
 943          */
 944         if (flags & LOP_TRYLOCK)
 945                 panic("%s should not be called for try lock operations",
 946                     __func__);
 947
 948         w = lock->lo_witness;
 949         class = LOCK_CLASS(lock);
 950         td = curthread;
 951         file = fixup_filename(file);
 952
 953         if (class->lc_flags & LC_SLEEPLOCK) {
 954                 /*
 955                  * Since spin locks include a critical section, this check
 956                  * implicitly enforces a lock order of all sleep locks before
 957                  * all spin locks.
 958                  */
 959                 if (td->td_critnest != 0 && !kdb_active)
 960                         panic("blockable sleep lock (%s) %s @ %s:%d",
 961                             class->lc_name, lock->lo_name, file, line);
 962
 963                 /*
 964                  * If this is the first lock acquired then just return as
 965                  * no order checking is needed.
 966                  */
 967                 if (td->td_sleeplocks == NULL)
 968                         return;
 969                 lock_list = &td->td_sleeplocks;
 970         } else {
 971                 /*
 972                  * If this is the first lock, just return as no order
 973                  * checking is needed.  We check this in both if clauses
 974                  * here as unifying the check would require us to use a
 975                  * critical section to ensure we don't migrate while doing
 976                  * the check.  Note that if this is not the first lock, we
 977                  * are already in a critical section and are safe for the
 978                  * rest of the check.
 979                  */
 980                 if (PCPU_GET(spinlocks) == NULL)
 981                         return;
 982                 lock_list = PCPU_PTR(spinlocks);
 983         }
 984
 985         /*
 986          * Check to see if we are recursing on a lock we already own.  If
 987          * so, make sure that we don't mismatch exclusive and shared lock
 988          * acquires.
 989          */
 990         lock1 = find_instance(*lock_list, lock);
 991         if (lock1 != NULL) {
 992                 if ((lock1->li_flags & LI_EXCLUSIVE) != 0 &&
 993                     (flags & LOP_EXCLUSIVE) == 0) {
 994                         printf("shared lock of (%s) %s @ %s:%d\n",
 995                             class->lc_name, lock->lo_name, file, line);
 996                         printf("while exclusively locked from %s:%d\n",
 997                             lock1->li_file, lock1->li_line);
 998                         panic("share->excl");
 999                 }
1000                 if ((lock1->li_flags & LI_EXCLUSIVE) == 0 &&
1001                     (flags & LOP_EXCLUSIVE) != 0) {
1002                         printf("exclusive lock of (%s) %s @ %s:%d\n",
1003                             class->lc_name, lock->lo_name, file, line);
1004                         printf("while share locked from %s:%d\n",
1005                             lock1->li_file, lock1->li_line);
1006                         panic("excl->share");
1007                 }
1008                 return;
1009         }
1010
1011         /*
1012          * Check for duplicate locks of the same type.  Note that we only
1013          * have to check for this on the last lock we just acquired.  Any
1014          * other cases will be caught as lock order violations.
1015          */
1016         lock1 = &(*lock_list)->ll_children[(*lock_list)->ll_count - 1];
1017         w1 = lock1->li_lock->lo_witness;
1018         if (w1 == w) {
1019                 if (w->w_same_squawked || (lock->lo_flags & LO_DUPOK) ||
1020                     (flags & LOP_DUPOK))
1021                         return;
1022                 w->w_same_squawked = 1;
1023                 printf("acquiring duplicate lock of same type: \"%s\"\n",
1024                         w->w_name);
1025                 printf(" 1st %s @ %s:%d\n", lock1->li_lock->lo_name,
1026                     lock1->li_file, lock1->li_line);
1027                 printf(" 2nd %s @ %s:%d\n", lock->lo_name, file, line);
1028 #ifdef KDB
1029                 goto debugger;
1030 #else
1031                 return;
1032 #endif
1033         }
1034         MPASS(!mtx_owned(&w_mtx));
1035         mtx_lock_spin(&w_mtx);
1036         /*
1037          * If we know that the the lock we are acquiring comes after
1038          * the lock we most recently acquired in the lock order tree,
1039          * then there is no need for any further checks.
1040          */
1041         if (isitmychild(w1, w)) {
1042                 mtx_unlock_spin(&w_mtx);
1043                 return;
1044         }
1045         for (j = 0, lle = *lock_list; lle != NULL; lle = lle->ll_next) {
1046                 for (i = lle->ll_count - 1; i >= 0; i--, j++) {
1047
1048                         MPASS(j < WITNESS_COUNT);
1049                         lock1 = &lle->ll_children[i];
1050                         w1 = lock1->li_lock->lo_witness;
1051
1052                         /*
1053                          * If this lock doesn't undergo witness checking,
1054                          * then skip it.
1055                          */
1056                         if (w1 == NULL) {
1057                                 KASSERT((lock1->li_lock->lo_flags & LO_WITNESS) == 0,
1058                                     ("lock missing witness structure"));
1059                                 continue;
1060                         }
1061                         /*
1062                          * If we are locking Giant and this is a sleepable
1063                          * lock, then skip it.
1064                          */
1065                         if ((lock1->li_lock->lo_flags & LO_SLEEPABLE) != 0 &&
1066                             lock == &Giant.lock_object)
1067                                 continue;
1068                         /*
1069                          * If we are locking a sleepable lock and this lock
1070                          * is Giant, then skip it.
1071                          */
1072                         if ((lock->lo_flags & LO_SLEEPABLE) != 0 &&
1073                             lock1->li_lock == &Giant.lock_object)
1074                                 continue;
1075                         /*
1076                          * If we are locking a sleepable lock and this lock
1077                          * isn't sleepable, we want to treat it as a lock
1078                          * order violation to enfore a general lock order of
1079                          * sleepable locks before non-sleepable locks.
1080                          */
1081                         if (((lock->lo_flags & LO_SLEEPABLE) != 0 &&
1082                             (lock1->li_lock->lo_flags & LO_SLEEPABLE) == 0))
1083                                 goto reversal;
1084                         /*
1085                          * If we are locking Giant and this is a non-sleepable
1086                          * lock, then treat it as a reversal.
1087                          */
1088                         if ((lock1->li_lock->lo_flags & LO_SLEEPABLE) == 0 &&
1089                             lock == &Giant.lock_object)
1090                                 goto reversal;
1091                         /*
1092                          * Check the lock order hierarchy for a reveresal.
1093                          */
1094                         if (!isitmydescendant(w, w1))
1095                                 continue;
1096                 reversal:
1097                         /*
1098                          * We have a lock order violation, check to see if it
1099                          * is allowed or has already been yelled about.
1100                          */
1101                         mtx_unlock_spin(&w_mtx);
1102 #ifdef BLESSING
1103                         /*
1104                          * If the lock order is blessed, just bail.  We don't
1105                          * look for other lock order violations though, which
1106                          * may be a bug.
1107                          */
1108                         if (blessed(w, w1))
1109                                 return;
1110 #endif
1111                         if (lock1->li_lock == &Giant.lock_object) {
1112                                 if (w1->w_Giant_squawked)
1113                                         return;
1114                                 else
1115                                         w1->w_Giant_squawked = 1;
1116                         } else {
1117                                 if (w1->w_other_squawked)
1118                                         return;
1119                                 else
1120                                         w1->w_other_squawked = 1;
1121                         }
1122                         /*
1123                          * Ok, yell about it.
1124                          */
1125                         if (((lock->lo_flags & LO_SLEEPABLE) != 0 &&
1126                             (lock1->li_lock->lo_flags & LO_SLEEPABLE) == 0))
1127                                 printf(
1128                 "lock order reversal: (sleepable after non-sleepable)\n");
1129                         else if ((lock1->li_lock->lo_flags & LO_SLEEPABLE) == 0
1130                             && lock == &Giant.lock_object)
1131                                 printf(
1132                 "lock order reversal: (Giant after non-sleepable)\n");
1133                         else
1134                                 printf("lock order reversal:\n");
1135                         /*
1136                          * Try to locate an earlier lock with
1137                          * witness w in our list.
1138                          */
1139                         do {
1140                                 lock2 = &lle->ll_children[i];
1141                                 MPASS(lock2->li_lock != NULL);
1142                                 if (lock2->li_lock->lo_witness == w)
1143                                         break;
1144                                 if (i == 0 && lle->ll_next != NULL) {
1145                                         lle = lle->ll_next;
1146                                         i = lle->ll_count - 1;
1147                                         MPASS(i >= 0 && i < LOCK_NCHILDREN);
1148                                 } else
1149                                         i--;
1150                         } while (i >= 0);
1151                         if (i < 0) {
1152                                 printf(" 1st %p %s (%s) @ %s:%d\n",
1153                                     lock1->li_lock, lock1->li_lock->lo_name,
1154                                     w1->w_name, lock1->li_file, lock1->li_line);
1155                                 printf(" 2nd %p %s (%s) @ %s:%d\n", lock,
1156                                     lock->lo_name, w->w_name, file, line);
1157                         } else {
1158                                 printf(" 1st %p %s (%s) @ %s:%d\n",
1159                                     lock2->li_lock, lock2->li_lock->lo_name,
1160                                     lock2->li_lock->lo_witness->w_name,
1161                                     lock2->li_file, lock2->li_line);
1162                                 printf(" 2nd %p %s (%s) @ %s:%d\n",
1163                                     lock1->li_lock, lock1->li_lock->lo_name,
1164                                     w1->w_name, lock1->li_file, lock1->li_line);
1165                                 printf(" 3rd %p %s (%s) @ %s:%d\n", lock,
1166                                     lock->lo_name, w->w_name, file, line);
1167                         }
1168 #ifdef KDB
1169                         goto debugger;
1170 #else
1171                         return;
1172 #endif
1173                 }
1174         }
1175         lock1 = &(*lock_list)->ll_children[(*lock_list)->ll_count - 1];
1176         /*
1177          * If requested, build a new lock order.  However, don't build a new
1178          * relationship between a sleepable lock and Giant if it is in the
1179          * wrong direction.  The correct lock order is that sleepable locks
1180          * always come before Giant.
1181          */
1182         if (flags & LOP_NEWORDER &&
1183             !(lock1->li_lock == &Giant.lock_object &&
1184             (lock->lo_flags & LO_SLEEPABLE) != 0)) {
1185                 CTR3(KTR_WITNESS, "%s: adding %s as a child of %s", __func__,
1186                     w->w_name, lock1->li_lock->lo_witness->w_name);
1187                 if (!itismychild(lock1->li_lock->lo_witness, w))
1188                         /* Witness is dead. */
1189                         return;
1190         }
1191         mtx_unlock_spin(&w_mtx);
1192         return;
1193
1194 #ifdef KDB
1195 debugger:
1196         if (witness_trace)
1197                 kdb_backtrace();
1198         if (witness_kdb)
1199                 kdb_enter(KDB_WHY_WITNESS, __func__);
1200 #endif
1201 }
1202
1203 void
1204 witness_lock(struct lock_object *lock, int flags, const char *file, int line)
1205 {
1206         struct lock_list_entry **lock_list, *lle;
1207         struct lock_instance *instance;
1208         struct witness *w;
1209         struct thread *td;
1210
1211         if (witness_cold || witness_watch == 0 || lock->lo_witness == NULL ||
1212             panicstr != NULL)
1213                 return;
1214         w = lock->lo_witness;
1215         td = curthread;
1216         file = fixup_filename(file);
1217
1218         /* Determine lock list for this lock. */
1219         if (LOCK_CLASS(lock)->lc_flags & LC_SLEEPLOCK)
1220                 lock_list = &td->td_sleeplocks;
1221         else
1222                 lock_list = PCPU_PTR(spinlocks);
1223
1224         /* Check to see if we are recursing on a lock we already own. */
1225         instance = find_instance(*lock_list, lock);
1226         if (instance != NULL) {
1227                 instance->li_flags++;
1228                 CTR4(KTR_WITNESS, "%s: pid %d recursed on %s r=%d", __func__,
1229                     td->td_proc->p_pid, lock->lo_name,
1230                     instance->li_flags & LI_RECURSEMASK);
1231                 instance->li_file = file;
1232                 instance->li_line = line;
1233                 return;
1234         }
1235
1236         /* Update per-witness last file and line acquire. */
1237         w->w_file = file;
1238         w->w_line = line;
1239
1240         /* Find the next open lock instance in the list and fill it. */
1241         lle = *lock_list;
1242         if (lle == NULL || lle->ll_count == LOCK_NCHILDREN) {
1243                 lle = witness_lock_list_get();
1244                 if (lle == NULL)
1245                         return;
1246                 lle->ll_next = *lock_list;
1247                 CTR3(KTR_WITNESS, "%s: pid %d added lle %p", __func__,
1248                     td->td_proc->p_pid, lle);
1249                 *lock_list = lle;
1250         }
1251         instance = &lle->ll_children[lle->ll_count++];
1252         instance->li_lock = lock;
1253         instance->li_line = line;
1254         instance->li_file = file;
1255         if ((flags & LOP_EXCLUSIVE) != 0)
1256                 instance->li_flags = LI_EXCLUSIVE;
1257         else
1258                 instance->li_flags = 0;
1259         CTR4(KTR_WITNESS, "%s: pid %d added %s as lle[%d]", __func__,
1260             td->td_proc->p_pid, lock->lo_name, lle->ll_count - 1);
1261 }
1262
1263 void
1264 witness_upgrade(struct lock_object *lock, int flags, const char *file, int line)
1265 {
1266         struct lock_instance *instance;
1267         struct lock_class *class;
1268
1269         KASSERT(!witness_cold, ("%s: witness_cold", __func__));
1270         if (lock->lo_witness == NULL || witness_watch == 0 || panicstr != NULL)
1271                 return;
1272         class = LOCK_CLASS(lock);
1273         file = fixup_filename(file);
1274         if ((lock->lo_flags & LO_UPGRADABLE) == 0)
1275                 panic("upgrade of non-upgradable lock (%s) %s @ %s:%d",
1276                     class->lc_name, lock->lo_name, file, line);
1277         if ((class->lc_flags & LC_SLEEPLOCK) == 0)
1278                 panic("upgrade of non-sleep lock (%s) %s @ %s:%d",
1279                     class->lc_name, lock->lo_name, file, line);
1280         instance = find_instance(curthread->td_sleeplocks, lock);
1281         if (instance == NULL)
1282                 panic("upgrade of unlocked lock (%s) %s @ %s:%d",
1283                     class->lc_name, lock->lo_name, file, line);
1284         if ((instance->li_flags & LI_EXCLUSIVE) != 0)
1285                 panic("upgrade of exclusive lock (%s) %s @ %s:%d",
1286                     class->lc_name, lock->lo_name, file, line);
1287         if ((instance->li_flags & LI_RECURSEMASK) != 0)
1288                 panic("upgrade of recursed lock (%s) %s r=%d @ %s:%d",
1289                     class->lc_name, lock->lo_name,
1290                     instance->li_flags & LI_RECURSEMASK, file, line);
1291         instance->li_flags |= LI_EXCLUSIVE;
1292 }
1293
1294 void
1295 witness_downgrade(struct lock_object *lock, int flags, const char *file,
1296     int line)
1297 {
1298         struct lock_instance *instance;
1299         struct lock_class *class;
1300
1301         KASSERT(!witness_cold, ("%s: witness_cold", __func__));
1302         if (lock->lo_witness == NULL || witness_watch == 0 || panicstr != NULL)
1303                 return;
1304         class = LOCK_CLASS(lock);
1305         file = fixup_filename(file);
1306         if ((lock->lo_flags & LO_UPGRADABLE) == 0)
1307                 panic("downgrade of non-upgradable lock (%s) %s @ %s:%d",
1308                     class->lc_name, lock->lo_name, file, line);
1309         if ((class->lc_flags & LC_SLEEPLOCK) == 0)
1310                 panic("downgrade of non-sleep lock (%s) %s @ %s:%d",
1311                     class->lc_name, lock->lo_name, file, line);
1312         instance = find_instance(curthread->td_sleeplocks, lock);
1313         if (instance == NULL)
1314                 panic("downgrade of unlocked lock (%s) %s @ %s:%d",
1315                     class->lc_name, lock->lo_name, file, line);
1316         if ((instance->li_flags & LI_EXCLUSIVE) == 0)
1317                 panic("downgrade of shared lock (%s) %s @ %s:%d",
1318                     class->lc_name, lock->lo_name, file, line);
1319         if ((instance->li_flags & LI_RECURSEMASK) != 0)
1320                 panic("downgrade of recursed lock (%s) %s r=%d @ %s:%d",
1321                     class->lc_name, lock->lo_name,
1322                     instance->li_flags & LI_RECURSEMASK, file, line);
1323         instance->li_flags &= ~LI_EXCLUSIVE;
1324 }
1325
1326 void
1327 witness_unlock(struct lock_object *lock, int flags, const char *file, int line)
1328 {
1329         struct lock_list_entry **lock_list, *lle;
1330         struct lock_instance *instance;
1331         struct lock_class *class;
1332         struct thread *td;
1333         register_t s;
1334         int i, j;
1335
1336         if (witness_cold || witness_watch == 0 || lock->lo_witness == NULL ||
1337             panicstr != NULL)
1338                 return;
1339         td = curthread;
1340         class = LOCK_CLASS(lock);
1341         file = fixup_filename(file);
1342
1343         /* Find lock instance associated with this lock. */
1344         if (class->lc_flags & LC_SLEEPLOCK)
1345                 lock_list = &td->td_sleeplocks;
1346         else
1347                 lock_list = PCPU_PTR(spinlocks);
1348         for (; *lock_list != NULL; lock_list = &(*lock_list)->ll_next)
1349                 for (i = 0; i < (*lock_list)->ll_count; i++) {
1350                         instance = &(*lock_list)->ll_children[i];
1351                         if (instance->li_lock == lock)
1352                                 goto found;
1353                 }
1354         panic("lock (%s) %s not locked @ %s:%d", class->lc_name, lock->lo_name,
1355             file, line);
1356 found:
1357
1358         /* First, check for shared/exclusive mismatches. */
1359         if ((instance->li_flags & LI_EXCLUSIVE) != 0 &&
1360             (flags & LOP_EXCLUSIVE) == 0) {
1361                 printf("shared unlock of (%s) %s @ %s:%d\n", class->lc_name,
1362                     lock->lo_name, file, line);
1363                 printf("while exclusively locked from %s:%d\n",
1364                     instance->li_file, instance->li_line);
1365                 panic("excl->ushare");
1366         }
1367         if ((instance->li_flags & LI_EXCLUSIVE) == 0 &&
1368             (flags & LOP_EXCLUSIVE) != 0) {
1369                 printf("exclusive unlock of (%s) %s @ %s:%d\n", class->lc_name,
1370                     lock->lo_name, file, line);
1371                 printf("while share locked from %s:%d\n", instance->li_file,
1372                     instance->li_line);
1373                 panic("share->uexcl");
1374         }
1375
1376         /* If we are recursed, unrecurse. */
1377         if ((instance->li_flags & LI_RECURSEMASK) > 0) {
1378                 CTR4(KTR_WITNESS, "%s: pid %d unrecursed on %s r=%d", __func__,
1379                     td->td_proc->p_pid, instance->li_lock->lo_name,
1380                     instance->li_flags);
1381                 instance->li_flags--;
1382                 return;
1383         }
1384
1385         /* Otherwise, remove this item from the list. */
1386         s = intr_disable();
1387         CTR4(KTR_WITNESS, "%s: pid %d removed %s from lle[%d]", __func__,
1388             td->td_proc->p_pid, instance->li_lock->lo_name,
1389             (*lock_list)->ll_count - 1);
1390         for (j = i; j < (*lock_list)->ll_count - 1; j++)
1391                 (*lock_list)->ll_children[j] =
1392                     (*lock_list)->ll_children[j + 1];
1393         (*lock_list)->ll_count--;
1394         intr_restore(s);
1395
1396         /* If this lock list entry is now empty, free it. */
1397         if ((*lock_list)->ll_count == 0) {
1398                 lle = *lock_list;
1399                 *lock_list = lle->ll_next;
1400                 CTR3(KTR_WITNESS, "%s: pid %d removed lle %p", __func__,
1401                     td->td_proc->p_pid, lle);
1402                 witness_lock_list_free(lle);
1403         }
1404 }
1405
1406 /*
1407  * Warn if any locks other than 'lock' are held.  Flags can be passed in to
1408  * exempt Giant and sleepable locks from the checks as well.  If any
1409  * non-exempt locks are held, then a supplied message is printed to the
1410  * console along with a list of the offending locks.  If indicated in the
1411  * flags then a failure results in a panic as well.
1412  */
1413 int
1414 witness_warn(int flags, struct lock_object *lock, const char *fmt, ...)
1415 {
1416         struct lock_list_entry *lle;
1417         struct lock_instance *lock1;
1418         struct thread *td;
1419         va_list ap;
1420         int i, n;
1421
1422         if (witness_cold || witness_watch == 0 || panicstr != NULL)
1423                 return (0);
1424         n = 0;
1425         td = curthread;
1426         for (lle = td->td_sleeplocks; lle != NULL; lle = lle->ll_next)
1427                 for (i = lle->ll_count - 1; i >= 0; i--) {
1428                         lock1 = &lle->ll_children[i];
1429                         if (lock1->li_lock == lock)
1430                                 continue;
1431                         if (flags & WARN_GIANTOK &&
1432                             lock1->li_lock == &Giant.lock_object)
1433                                 continue;
1434                         if (flags & WARN_SLEEPOK &&
1435                             (lock1->li_lock->lo_flags & LO_SLEEPABLE) != 0)
1436                                 continue;
1437                         if (n == 0) {
1438                                 va_start(ap, fmt);
1439                                 vprintf(fmt, ap);
1440                                 va_end(ap);
1441                                 printf(" with the following");
1442                                 if (flags & WARN_SLEEPOK)
1443                                         printf(" non-sleepable");
1444                                 printf(" locks held:\n");
1445                         }
1446                         n++;
1447                         witness_list_lock(lock1);
1448                 }
1449         if (PCPU_GET(spinlocks) != NULL) {
1450                 /*
1451                  * Since we already hold a spinlock preemption is
1452                  * already blocked.
1453                  */
1454                 if (n == 0) {
1455                         va_start(ap, fmt);
1456                         vprintf(fmt, ap);
1457                         va_end(ap);
1458                         printf(" with the following");
1459                         if (flags & WARN_SLEEPOK)
1460                                 printf(" non-sleepable");
1461                         printf(" locks held:\n");
1462                 }
1463                 n += witness_list_locks(PCPU_PTR(spinlocks));
1464         }
1465         if (flags & WARN_PANIC && n)
1466                 panic("witness_warn");
1467 #ifdef KDB
1468         else if (witness_kdb && n)
1469                 kdb_enter(KDB_WHY_WITNESS, __func__);
1470         else if (witness_trace && n)
1471                 kdb_backtrace();
1472 #endif
1473         return (n);
1474 }
1475
1476 const char *
1477 witness_file(struct lock_object *lock)
1478 {
1479         struct witness *w;
1480
1481         if (witness_cold || witness_watch == 0 || lock->lo_witness == NULL)
1482                 return ("?");
1483         w = lock->lo_witness;
1484         return (w->w_file);
1485 }
1486
1487 int
1488 witness_line(struct lock_object *lock)
1489 {
1490         struct witness *w;
1491
1492         if (witness_cold || witness_watch == 0 || lock->lo_witness == NULL)
1493                 return (0);
1494         w = lock->lo_witness;
1495         return (w->w_line);
1496 }
1497
1498 static struct witness *
1499 enroll(const char *description, struct lock_class *lock_class)
1500 {
1501         struct witness *w;
1502
1503         if (witness_watch == 0 || panicstr != NULL)
1504                 return (NULL);
1505         if ((lock_class->lc_flags & LC_SPINLOCK) && witness_skipspin)
1506                 return (NULL);
1507         mtx_lock_spin(&w_mtx);
1508         STAILQ_FOREACH(w, &w_all, w_list) {
1509                 if (w->w_name == description || (w->w_refcount > 0 &&
1510                     strcmp(description, w->w_name) == 0)) {
1511                         w->w_refcount++;
1512                         mtx_unlock_spin(&w_mtx);
1513                         if (lock_class != w->w_class)
1514                                 panic(
1515                                 "lock (%s) %s does not match earlier (%s) lock",
1516                                     description, lock_class->lc_name,
1517                                     w->w_class->lc_name);
1518                         return (w);
1519                 }
1520         }
1521         if ((w = witness_get()) == NULL) {
1522                 printf("WITNESS: unable to allocate a new witness object\n");
1523                 goto out;
1524         }
1525         w->w_name = description;
1526         w->w_class = lock_class;
1527         w->w_refcount = 1;
1528         STAILQ_INSERT_HEAD(&w_all, w, w_list);
1529         if (lock_class->lc_flags & LC_SPINLOCK) {
1530                 STAILQ_INSERT_HEAD(&w_spin, w, w_typelist);
1531                 w_spin_cnt++;
1532         } else if (lock_class->lc_flags & LC_SLEEPLOCK) {
1533                 STAILQ_INSERT_HEAD(&w_sleep, w, w_typelist);
1534                 w_sleep_cnt++;
1535         } else {
1536                 mtx_unlock_spin(&w_mtx);
1537                 panic("lock class %s is not sleep or spin",
1538                     lock_class->lc_name);
1539         }
1540         mtx_unlock_spin(&w_mtx);
1541 out:
1542         /*
1543          * We issue a warning for any spin locks not defined in the static
1544          * order list as a way to discourage their use (folks should really
1545          * be using non-spin mutexes most of the time).  However, several
1546          * 3rd part device drivers use spin locks because that is all they
1547          * have available on Windows and Linux and they think that normal
1548          * mutexes are insufficient.
1549          */
1550         if ((lock_class->lc_flags & LC_SPINLOCK) && witness_spin_warn)
1551                 printf("WITNESS: spin lock %s not in order list\n",
1552                     description);
1553         return (w);
1554 }
1555
1556 /* Don't let the door bang you on the way out... */
1557 static void
1558 depart(struct witness *w)
1559 {
1560         struct witness_child_list_entry *wcl, *nwcl;
1561         struct witness_list *list;
1562         struct witness *parent;
1563
1564         MPASS(w->w_refcount == 0);
1565         if (w->w_class->lc_flags & LC_SLEEPLOCK) {
1566                 list = &w_sleep;
1567                 w_sleep_cnt--;
1568         } else {
1569                 list = &w_spin;
1570                 w_spin_cnt--;
1571         }
1572         /*
1573          * First, we run through the entire tree looking for any
1574          * witnesses that the outgoing witness is a child of.  For
1575          * each parent that we find, we reparent all the direct
1576          * children of the outgoing witness to its parent.
1577          */
1578         STAILQ_FOREACH(parent, list, w_typelist) {
1579                 if (!isitmychild(parent, w))
1580                         continue;
1581                 removechild(parent, w);
1582         }
1583
1584         /*
1585          * Now we go through and free up the child list of the
1586          * outgoing witness.
1587          */
1588         for (wcl = w->w_children; wcl != NULL; wcl = nwcl) {
1589                 nwcl = wcl->wcl_next;
1590                 w_child_cnt--;
1591                 witness_child_free(wcl);
1592         }
1593
1594         /*
1595          * Detach from various lists and free.
1596          */
1597         STAILQ_REMOVE(list, w, witness, w_typelist);
1598         STAILQ_REMOVE(&w_all, w, witness, w_list);
1599         witness_free(w);
1600 }
1601
1602 /*
1603  * Add "child" as a direct child of "parent".  Returns false if
1604  * we fail due to out of memory.
1605  */
1606 static int
1607 insertchild(struct witness *parent, struct witness *child)
1608 {
1609         struct witness_child_list_entry **wcl;
1610
1611         MPASS(child != NULL && parent != NULL);
1612
1613         /*
1614          * Insert "child" after "parent"
1615          */
1616         wcl = &parent->w_children;
1617         while (*wcl != NULL && (*wcl)->wcl_count == WITNESS_NCHILDREN)
1618                 wcl = &(*wcl)->wcl_next;
1619         if (*wcl == NULL) {
1620                 *wcl = witness_child_get();
1621                 if (*wcl == NULL)
1622                         return (0);
1623                 w_child_cnt++;
1624         }
1625         (*wcl)->wcl_children[(*wcl)->wcl_count++] = child;
1626
1627         return (1);
1628 }
1629
1630
1631 static int
1632 itismychild(struct witness *parent, struct witness *child)
1633 {
1634
1635         MPASS(child != NULL && parent != NULL);
1636         if ((parent->w_class->lc_flags & (LC_SLEEPLOCK | LC_SPINLOCK)) !=
1637             (child->w_class->lc_flags & (LC_SLEEPLOCK | LC_SPINLOCK)))
1638                 panic(
1639                 "%s: parent (%s) and child (%s) are not the same lock type",
1640                     __func__, parent->w_class->lc_name,
1641                     child->w_class->lc_name);
1642
1643         return (insertchild(parent, child));
1644 }
1645
1646 static void
1647 removechild(struct witness *parent, struct witness *child)
1648 {
1649         struct witness_child_list_entry **wcl, *wcl1;
1650         int i;
1651
1652         for (wcl = &parent->w_children; *wcl != NULL; wcl = &(*wcl)->wcl_next)
1653                 for (i = 0; i < (*wcl)->wcl_count; i++)
1654                         if ((*wcl)->wcl_children[i] == child)
1655                                 goto found;
1656         return;
1657 found:
1658         (*wcl)->wcl_count--;
1659         if ((*wcl)->wcl_count > i)
1660                 (*wcl)->wcl_children[i] =
1661                     (*wcl)->wcl_children[(*wcl)->wcl_count];
1662         MPASS((*wcl)->wcl_children[i] != NULL);
1663         if ((*wcl)->wcl_count != 0)
1664                 return;
1665         wcl1 = *wcl;
1666         *wcl = wcl1->wcl_next;
1667         w_child_cnt--;
1668         witness_child_free(wcl1);
1669 }
1670
1671 static int
1672 isitmychild(struct witness *parent, struct witness *child)
1673 {
1674         struct witness_child_list_entry *wcl;
1675         int i;
1676
1677         for (wcl = parent->w_children; wcl != NULL; wcl = wcl->wcl_next) {
1678                 for (i = 0; i < wcl->wcl_count; i++) {
1679                         if (wcl->wcl_children[i] == child)
1680                                 return (1);
1681                 }
1682         }
1683         return (0);
1684 }
1685
1686 static int
1687 isitmydescendant(struct witness *parent, struct witness *child)
1688 {
1689         struct witness_child_list_entry *wcl;
1690         int i, j;
1691
1692         if (isitmychild(parent, child))
1693                 return (1);
1694         j = 0;
1695         for (wcl = parent->w_children; wcl != NULL; wcl = wcl->wcl_next) {
1696                 MPASS(j < 1000);
1697                 for (i = 0; i < wcl->wcl_count; i++) {
1698                         if (isitmydescendant(wcl->wcl_children[i], child))
1699                                 return (1);
1700                 }
1701                 j++;
1702         }
1703         return (0);
1704 }
1705
1706 #ifdef BLESSING
1707 static int
1708 blessed(struct witness *w1, struct witness *w2)
1709 {
1710         int i;
1711         struct witness_blessed *b;
1712
1713         for (i = 0; i < blessed_count; i++) {
1714                 b = &blessed_list[i];
1715                 if (strcmp(w1->w_name, b->b_lock1) == 0) {
1716                         if (strcmp(w2->w_name, b->b_lock2) == 0)
1717                                 return (1);
1718                         continue;
1719                 }
1720                 if (strcmp(w1->w_name, b->b_lock2) == 0)
1721                         if (strcmp(w2->w_name, b->b_lock1) == 0)
1722                                 return (1);
1723         }
1724         return (0);
1725 }
1726 #endif
1727
1728 static struct witness *
1729 witness_get(void)
1730 {
1731         struct witness *w;
1732
1733         if (witness_watch == 0) {
1734                 mtx_unlock_spin(&w_mtx);
1735                 return (NULL);
1736         }
1737         if (STAILQ_EMPTY(&w_free)) {
1738                 witness_watch = 0;
1739                 mtx_unlock_spin(&w_mtx);
1740                 printf("%s: witness exhausted\n", __func__);
1741                 return (NULL);
1742         }
1743         w = STAILQ_FIRST(&w_free);
1744         STAILQ_REMOVE_HEAD(&w_free, w_list);
1745         w_free_cnt--;
1746         bzero(w, sizeof(*w));
1747         return (w);
1748 }
1749
1750 static void
1751 witness_free(struct witness *w)
1752 {
1753
1754         STAILQ_INSERT_HEAD(&w_free, w, w_list);
1755         w_free_cnt++;
1756 }
1757
1758 static struct witness_child_list_entry *
1759 witness_child_get(void)
1760 {
1761         struct witness_child_list_entry *wcl;
1762
1763         if (witness_watch == 0) {
1764                 mtx_unlock_spin(&w_mtx);
1765                 return (NULL);
1766         }
1767         wcl = w_child_free;
1768         if (wcl == NULL) {
1769                 witness_watch = 0;
1770                 mtx_unlock_spin(&w_mtx);
1771                 printf("%s: witness exhausted\n", __func__);
1772                 return (NULL);
1773         }
1774         w_child_free = wcl->wcl_next;
1775         w_child_free_cnt--;
1776         bzero(wcl, sizeof(*wcl));
1777         return (wcl);
1778 }
1779
1780 static void
1781 witness_child_free(struct witness_child_list_entry *wcl)
1782 {
1783
1784         wcl->wcl_next = w_child_free;
1785         w_child_free = wcl;
1786         w_child_free_cnt++;
1787 }
1788
1789 static struct lock_list_entry *
1790 witness_lock_list_get(void)
1791 {
1792         struct lock_list_entry *lle;
1793
1794         if (witness_watch == 0)
1795                 return (NULL);
1796         mtx_lock_spin(&w_mtx);
1797         lle = w_lock_list_free;
1798         if (lle == NULL) {
1799                 witness_watch = 0;
1800                 mtx_unlock_spin(&w_mtx);
1801                 printf("%s: witness exhausted\n", __func__);
1802                 return (NULL);
1803         }
1804         w_lock_list_free = lle->ll_next;
1805         mtx_unlock_spin(&w_mtx);
1806         bzero(lle, sizeof(*lle));
1807         return (lle);
1808 }
1809
1810 static void
1811 witness_lock_list_free(struct lock_list_entry *lle)
1812 {
1813
1814         mtx_lock_spin(&w_mtx);
1815         lle->ll_next = w_lock_list_free;
1816         w_lock_list_free = lle;
1817         mtx_unlock_spin(&w_mtx);
1818 }
1819
1820 static struct lock_instance *
1821 find_instance(struct lock_list_entry *lock_list, struct lock_object *lock)
1822 {
1823         struct lock_list_entry *lle;
1824         struct lock_instance *instance;
1825         int i;
1826
1827         for (lle = lock_list; lle != NULL; lle = lle->ll_next)
1828                 for (i = lle->ll_count - 1; i >= 0; i--) {
1829                         instance = &lle->ll_children[i];
1830                         if (instance->li_lock == lock)
1831                                 return (instance);
1832                 }
1833         return (NULL);
1834 }
1835
1836 static void
1837 witness_list_lock(struct lock_instance *instance)
1838 {
1839         struct lock_object *lock;
1840
1841         lock = instance->li_lock;
1842         printf("%s %s %s", (instance->li_flags & LI_EXCLUSIVE) != 0 ?
1843             "exclusive" : "shared", LOCK_CLASS(lock)->lc_name, lock->lo_name);
1844         if (lock->lo_witness->w_name != lock->lo_name)
1845                 printf(" (%s)", lock->lo_witness->w_name);
1846         printf(" r = %d (%p) locked @ %s:%d\n",
1847             instance->li_flags & LI_RECURSEMASK, lock, instance->li_file,
1848             instance->li_line);
1849 }
1850
1851 #ifdef DDB
1852 static int
1853 witness_thread_has_locks(struct thread *td)
1854 {
1855
1856         return (td->td_sleeplocks != NULL);
1857 }
1858
1859 static int
1860 witness_proc_has_locks(struct proc *p)
1861 {
1862         struct thread *td;
1863
1864         FOREACH_THREAD_IN_PROC(p, td) {
1865                 if (witness_thread_has_locks(td))
1866                         return (1);
1867         }
1868         return (0);
1869 }
1870 #endif
1871
1872 int
1873 witness_list_locks(struct lock_list_entry **lock_list)
1874 {
1875         struct lock_list_entry *lle;
1876         int i, nheld;
1877
1878         nheld = 0;
1879         for (lle = *lock_list; lle != NULL; lle = lle->ll_next)
1880                 for (i = lle->ll_count - 1; i >= 0; i--) {
1881                         witness_list_lock(&lle->ll_children[i]);
1882                         nheld++;
1883                 }
1884         return (nheld);
1885 }
1886
1887 /*
1888  * This is a bit risky at best.  We call this function when we have timed
1889  * out acquiring a spin lock, and we assume that the other CPU is stuck
1890  * with this lock held.  So, we go groveling around in the other CPU's
1891  * per-cpu data to try to find the lock instance for this spin lock to
1892  * see when it was last acquired.
1893  */
1894 void
1895 witness_display_spinlock(struct lock_object *lock, struct thread *owner)
1896 {
1897         struct lock_instance *instance;
1898         struct pcpu *pc;
1899
1900         if (owner->td_critnest == 0 || owner->td_oncpu == NOCPU)
1901                 return;
1902         pc = pcpu_find(owner->td_oncpu);
1903         instance = find_instance(pc->pc_spinlocks, lock);
1904         if (instance != NULL)
1905                 witness_list_lock(instance);
1906 }
1907
1908 void
1909 witness_save(struct lock_object *lock, const char **filep, int *linep)
1910 {
1911         struct lock_list_entry *lock_list;
1912         struct lock_instance *instance;
1913         struct lock_class *class;
1914
1915         KASSERT(!witness_cold, ("%s: witness_cold", __func__));
1916         if (lock->lo_witness == NULL || witness_watch == 0 || panicstr != NULL)
1917                 return;
1918         class = LOCK_CLASS(lock);
1919         if (class->lc_flags & LC_SLEEPLOCK)
1920                 lock_list = curthread->td_sleeplocks;
1921         else {
1922                 if (witness_skipspin)
1923                         return;
1924                 lock_list = PCPU_GET(spinlocks);
1925         }
1926         instance = find_instance(lock_list, lock);
1927         if (instance == NULL)
1928                 panic("%s: lock (%s) %s not locked", __func__,
1929                     class->lc_name, lock->lo_name);
1930         *filep = instance->li_file;
1931         *linep = instance->li_line;
1932 }
1933
1934 void
1935 witness_restore(struct lock_object *lock, const char *file, int line)
1936 {
1937         struct lock_list_entry *lock_list;
1938         struct lock_instance *instance;
1939         struct lock_class *class;
1940
1941         KASSERT(!witness_cold, ("%s: witness_cold", __func__));
1942         if (lock->lo_witness == NULL || witness_watch == 0 || panicstr != NULL)
1943                 return;
1944         class = LOCK_CLASS(lock);
1945         if (class->lc_flags & LC_SLEEPLOCK)
1946                 lock_list = curthread->td_sleeplocks;
1947         else {
1948                 if (witness_skipspin)
1949                         return;
1950                 lock_list = PCPU_GET(spinlocks);
1951         }
1952         instance = find_instance(lock_list, lock);
1953         if (instance == NULL)
1954                 panic("%s: lock (%s) %s not locked", __func__,
1955                     class->lc_name, lock->lo_name);
1956         lock->lo_witness->w_file = file;
1957         lock->lo_witness->w_line = line;
1958         instance->li_file = file;
1959         instance->li_line = line;
1960 }
1961
1962 void
1963 witness_assert(struct lock_object *lock, int flags, const char *file, int line)
1964 {
1965 #ifdef INVARIANT_SUPPORT
1966         struct lock_instance *instance;
1967         struct lock_class *class;
1968
1969         if (lock->lo_witness == NULL || witness_watch == 0 || panicstr != NULL)
1970                 return;
1971         class = LOCK_CLASS(lock);
1972         if ((class->lc_flags & LC_SLEEPLOCK) != 0)
1973                 instance = find_instance(curthread->td_sleeplocks, lock);
1974         else if ((class->lc_flags & LC_SPINLOCK) != 0)
1975                 instance = find_instance(PCPU_GET(spinlocks), lock);
1976         else {
1977                 panic("Lock (%s) %s is not sleep or spin!",
1978                     class->lc_name, lock->lo_name);
1979         }
1980         file = fixup_filename(file);
1981         switch (flags) {
1982         case LA_UNLOCKED:
1983                 if (instance != NULL)
1984                         panic("Lock (%s) %s locked @ %s:%d.",
1985                             class->lc_name, lock->lo_name, file, line);
1986                 break;
1987         case LA_LOCKED:
1988         case LA_LOCKED | LA_RECURSED:
1989         case LA_LOCKED | LA_NOTRECURSED:
1990         case LA_SLOCKED:
1991         case LA_SLOCKED | LA_RECURSED:
1992         case LA_SLOCKED | LA_NOTRECURSED:
1993         case LA_XLOCKED:
1994         case LA_XLOCKED | LA_RECURSED:
1995         case LA_XLOCKED | LA_NOTRECURSED:
1996                 if (instance == NULL) {
1997                         panic("Lock (%s) %s not locked @ %s:%d.",
1998                             class->lc_name, lock->lo_name, file, line);
1999                         break;
2000                 }
2001                 if ((flags & LA_XLOCKED) != 0 &&
2002                     (instance->li_flags & LI_EXCLUSIVE) == 0)
2003                         panic("Lock (%s) %s not exclusively locked @ %s:%d.",
2004                             class->lc_name, lock->lo_name, file, line);
2005                 if ((flags & LA_SLOCKED) != 0 &&
2006                     (instance->li_flags & LI_EXCLUSIVE) != 0)
2007                         panic("Lock (%s) %s exclusively locked @ %s:%d.",
2008                             class->lc_name, lock->lo_name, file, line);
2009                 if ((flags & LA_RECURSED) != 0 &&
2010                     (instance->li_flags & LI_RECURSEMASK) == 0)
2011                         panic("Lock (%s) %s not recursed @ %s:%d.",
2012                             class->lc_name, lock->lo_name, file, line);
2013                 if ((flags & LA_NOTRECURSED) != 0 &&
2014                     (instance->li_flags & LI_RECURSEMASK) != 0)
2015                         panic("Lock (%s) %s recursed @ %s:%d.",
2016                             class->lc_name, lock->lo_name, file, line);
2017                 break;
2018         default:
2019                 panic("Invalid lock assertion at %s:%d.", file, line);
2020
2021         }
2022 #endif  /* INVARIANT_SUPPORT */
2023 }
2024
2025 #ifdef DDB
2026 static void
2027 witness_list(struct thread *td)
2028 {
2029
2030         KASSERT(!witness_cold, ("%s: witness_cold", __func__));
2031         KASSERT(kdb_active, ("%s: not in the debugger", __func__));
2032
2033         if (witness_watch == 0)
2034                 return;
2035
2036         witness_list_locks(&td->td_sleeplocks);
2037
2038         /*
2039          * We only handle spinlocks if td == curthread.  This is somewhat broken
2040          * if td is currently executing on some other CPU and holds spin locks
2041          * as we won't display those locks.  If we had a MI way of getting
2042          * the per-cpu data for a given cpu then we could use
2043          * td->td_oncpu to get the list of spinlocks for this thread
2044          * and "fix" this.
2045          *
2046          * That still wouldn't really fix this unless we locked the scheduler
2047          * lock or stopped the other CPU to make sure it wasn't changing the
2048          * list out from under us.  It is probably best to just not try to
2049          * handle threads on other CPU's for now.
2050          */
2051         if (td == curthread && PCPU_GET(spinlocks) != NULL)
2052                 witness_list_locks(PCPU_PTR(spinlocks));
2053 }
2054
2055 DB_SHOW_COMMAND(locks, db_witness_list)
2056 {
2057         struct thread *td;
2058
2059         if (have_addr)
2060                 td = db_lookup_thread(addr, TRUE);
2061         else
2062                 td = kdb_thread;
2063         witness_list(td);
2064 }
2065
2066 DB_SHOW_COMMAND(alllocks, db_witness_list_all)
2067 {
2068         struct thread *td;
2069         struct proc *p;
2070
2071         /*
2072          * It would be nice to list only threads and processes that actually
2073          * held sleep locks, but that information is currently not exported
2074          * by WITNESS.
2075          */
2076         FOREACH_PROC_IN_SYSTEM(p) {
2077                 if (!witness_proc_has_locks(p))
2078                         continue;
2079                 FOREACH_THREAD_IN_PROC(p, td) {
2080                         if (!witness_thread_has_locks(td))
2081                                 continue;
2082                         db_printf("Process %d (%s) thread %p (%d)\n", p->p_pid,
2083                             td->td_name, td, td->td_tid);
2084                         witness_list(td);
2085                 }
2086         }
2087 }
2088
2089 DB_SHOW_COMMAND(witness, db_witness_display)
2090 {
2091
2092         witness_display(db_printf);
2093 }
2094 #endif