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 #endif /* DDB */
 820
 821 static void
 822 witness_addgraph(struct sbuf *sb, struct witness *parent)
 823 {
 824         struct witness_child_list_entry *wcl;
 825         int i;
 826
 827         if (parent->w_displayed != 0 || parent->w_refcount == 0 ||
 828             parent->w_file == NULL)
 829                 return;
 830
 831         parent->w_displayed = 1;
 832         for (wcl = parent->w_children; wcl != NULL; wcl = wcl->wcl_next)
 833                 for (i = 0; i < wcl->wcl_count; i++) {
 834                         sbuf_printf(sb, "\"%s\",\"%s\"\n", parent->w_name,
 835                             wcl->wcl_children[i]->w_name);
 836                         witness_addgraph(sb, wcl->wcl_children[i]);
 837                 }
 838 }
 839
 840 #ifdef DDB
 841 static void
 842 witness_display(void(*prnt)(const char *fmt, ...))
 843 {
 844         struct witness *w;
 845
 846         KASSERT(!witness_cold, ("%s: witness_cold", __func__));
 847         witness_levelall();
 848
 849         /* Clear all the displayed flags. */
 850         STAILQ_FOREACH(w, &w_all, w_list) {
 851                 w->w_displayed = 0;
 852         }
 853
 854         /*
 855          * First, handle sleep locks which have been acquired at least
 856          * once.
 857          */
 858         prnt("Sleep locks:\n");
 859         witness_display_list(prnt, &w_sleep);
 860
 861         /*
 862          * Now do spin locks which have been acquired at least once.
 863          */
 864         prnt("\nSpin locks:\n");
 865         witness_display_list(prnt, &w_spin);
 866
 867         /*
 868          * Finally, any locks which have not been acquired yet.
 869          */
 870         prnt("\nLocks which were never acquired:\n");
 871         STAILQ_FOREACH(w, &w_all, w_list) {
 872                 if (w->w_file != NULL || w->w_refcount == 0)
 873                         continue;
 874                 prnt("%s\n", w->w_name);
 875         }
 876 }
 877 #endif /* DDB */
 878
 879 /* Trim useless garbage from filenames. */
 880 static const char *
 881 fixup_filename(const char *file)
 882 {
 883
 884         if (file == NULL)
 885                 return (NULL);
 886         while (strncmp(file, "../", 3) == 0)
 887                 file += 3;
 888         return (file);
 889 }
 890
 891 int
 892 witness_defineorder(struct lock_object *lock1, struct lock_object *lock2)
 893 {
 894
 895         if (witness_watch == 0 || panicstr != NULL)
 896                 return (0);
 897
 898         /* Require locks that witness knows about. */
 899         if (lock1 == NULL || lock1->lo_witness == NULL || lock2 == NULL ||
 900             lock2->lo_witness == NULL)
 901                 return (EINVAL);
 902
 903         MPASS(!mtx_owned(&w_mtx));
 904         mtx_lock_spin(&w_mtx);
 905
 906         /*
 907          * If we already have either an explicit or implied lock order that
 908          * is the other way around, then return an error.
 909          */
 910         if (isitmydescendant(lock2->lo_witness, lock1->lo_witness)) {
 911                 mtx_unlock_spin(&w_mtx);
 912                 return (EDOOFUS);
 913         }
 914
 915         /* Try to add the new order. */
 916         CTR3(KTR_WITNESS, "%s: adding %s as a child of %s", __func__,
 917             lock2->lo_witness->w_name, lock1->lo_witness->w_name);
 918         if (!itismychild(lock1->lo_witness, lock2->lo_witness))
 919                 return (ENOMEM);
 920         mtx_unlock_spin(&w_mtx);
 921         return (0);
 922 }
 923
 924 void
 925 witness_checkorder(struct lock_object *lock, int flags, const char *file,
 926     int line)
 927 {
 928         struct lock_list_entry **lock_list, *lle;
 929         struct lock_instance *lock1, *lock2;
 930         struct lock_class *class;
 931         struct witness *w, *w1;
 932         struct thread *td;
 933         int i, j;
 934
 935         if (witness_cold || witness_watch == 0 || lock->lo_witness == NULL ||
 936             panicstr != NULL)
 937                 return;
 938
 939         /*
 940          * Try locks do not block if they fail to acquire the lock, thus
 941          * there is no danger of deadlocks or of switching while holding a
 942          * spin lock if we acquire a lock via a try operation.  This
 943          * function shouldn't even be called for try locks, so panic if
 944          * that happens.
 945          */
 946         if (flags & LOP_TRYLOCK)
 947                 panic("%s should not be called for try lock operations",
 948                     __func__);
 949
 950         w = lock->lo_witness;
 951         class = LOCK_CLASS(lock);
 952         td = curthread;
 953         file = fixup_filename(file);
 954
 955         if (class->lc_flags & LC_SLEEPLOCK) {
 956                 /*
 957                  * Since spin locks include a critical section, this check
 958                  * implicitly enforces a lock order of all sleep locks before
 959                  * all spin locks.
 960                  */
 961                 if (td->td_critnest != 0 && !kdb_active)
 962                         panic("blockable sleep lock (%s) %s @ %s:%d",
 963                             class->lc_name, lock->lo_name, file, line);
 964
 965                 /*
 966                  * If this is the first lock acquired then just return as
 967                  * no order checking is needed.
 968                  */
 969                 if (td->td_sleeplocks == NULL)
 970                         return;
 971                 lock_list = &td->td_sleeplocks;
 972         } else {
 973                 /*
 974                  * If this is the first lock, just return as no order
 975                  * checking is needed.  We check this in both if clauses
 976                  * here as unifying the check would require us to use a
 977                  * critical section to ensure we don't migrate while doing
 978                  * the check.  Note that if this is not the first lock, we
 979                  * are already in a critical section and are safe for the
 980                  * rest of the check.
 981                  */
 982                 if (PCPU_GET(spinlocks) == NULL)
 983                         return;
 984                 lock_list = PCPU_PTR(spinlocks);
 985         }
 986
 987         /*
 988          * Check to see if we are recursing on a lock we already own.  If
 989          * so, make sure that we don't mismatch exclusive and shared lock
 990          * acquires.
 991          */
 992         lock1 = find_instance(*lock_list, lock);
 993         if (lock1 != NULL) {
 994                 if ((lock1->li_flags & LI_EXCLUSIVE) != 0 &&
 995                     (flags & LOP_EXCLUSIVE) == 0) {
 996                         printf("shared lock of (%s) %s @ %s:%d\n",
 997                             class->lc_name, lock->lo_name, file, line);
 998                         printf("while exclusively locked from %s:%d\n",
 999                             lock1->li_file, lock1->li_line);
1000                         panic("share->excl");
1001                 }
1002                 if ((lock1->li_flags & LI_EXCLUSIVE) == 0 &&
1003                     (flags & LOP_EXCLUSIVE) != 0) {
1004                         printf("exclusive lock of (%s) %s @ %s:%d\n",
1005                             class->lc_name, lock->lo_name, file, line);
1006                         printf("while share locked from %s:%d\n",
1007                             lock1->li_file, lock1->li_line);
1008                         panic("excl->share");
1009                 }
1010                 return;
1011         }
1012
1013         /*
1014          * Check for duplicate locks of the same type.  Note that we only
1015          * have to check for this on the last lock we just acquired.  Any
1016          * other cases will be caught as lock order violations.
1017          */
1018         lock1 = &(*lock_list)->ll_children[(*lock_list)->ll_count - 1];
1019         w1 = lock1->li_lock->lo_witness;
1020         if (w1 == w) {
1021                 if (w->w_same_squawked || (lock->lo_flags & LO_DUPOK) ||
1022                     (flags & LOP_DUPOK))
1023                         return;
1024                 w->w_same_squawked = 1;
1025                 printf("acquiring duplicate lock of same type: \"%s\"\n",
1026                         w->w_name);
1027                 printf(" 1st %s @ %s:%d\n", lock1->li_lock->lo_name,
1028                     lock1->li_file, lock1->li_line);
1029                 printf(" 2nd %s @ %s:%d\n", lock->lo_name, file, line);
1030 #ifdef KDB
1031                 goto debugger;
1032 #else
1033                 return;
1034 #endif
1035         }
1036         MPASS(!mtx_owned(&w_mtx));
1037         mtx_lock_spin(&w_mtx);
1038         /*
1039          * If we know that the the lock we are acquiring comes after
1040          * the lock we most recently acquired in the lock order tree,
1041          * then there is no need for any further checks.
1042          */
1043         if (isitmychild(w1, w)) {
1044                 mtx_unlock_spin(&w_mtx);
1045                 return;
1046         }
1047         for (j = 0, lle = *lock_list; lle != NULL; lle = lle->ll_next) {
1048                 for (i = lle->ll_count - 1; i >= 0; i--, j++) {
1049
1050                         MPASS(j < WITNESS_COUNT);
1051                         lock1 = &lle->ll_children[i];
1052                         w1 = lock1->li_lock->lo_witness;
1053
1054                         /*
1055                          * If this lock doesn't undergo witness checking,
1056                          * then skip it.
1057                          */
1058                         if (w1 == NULL) {
1059                                 KASSERT((lock1->li_lock->lo_flags & LO_WITNESS) == 0,
1060                                     ("lock missing witness structure"));
1061                                 continue;
1062                         }
1063                         /*
1064                          * If we are locking Giant and this is a sleepable
1065                          * lock, then skip it.
1066                          */
1067                         if ((lock1->li_lock->lo_flags & LO_SLEEPABLE) != 0 &&
1068                             lock == &Giant.lock_object)
1069                                 continue;
1070                         /*
1071                          * If we are locking a sleepable lock and this lock
1072                          * is Giant, then skip it.
1073                          */
1074                         if ((lock->lo_flags & LO_SLEEPABLE) != 0 &&
1075                             lock1->li_lock == &Giant.lock_object)
1076                                 continue;
1077                         /*
1078                          * If we are locking a sleepable lock and this lock
1079                          * isn't sleepable, we want to treat it as a lock
1080                          * order violation to enfore a general lock order of
1081                          * sleepable locks before non-sleepable locks.
1082                          */
1083                         if (((lock->lo_flags & LO_SLEEPABLE) != 0 &&
1084                             (lock1->li_lock->lo_flags & LO_SLEEPABLE) == 0))
1085                                 goto reversal;
1086                         /*
1087                          * If we are locking Giant and this is a non-sleepable
1088                          * lock, then treat it as a reversal.
1089                          */
1090                         if ((lock1->li_lock->lo_flags & LO_SLEEPABLE) == 0 &&
1091                             lock == &Giant.lock_object)
1092                                 goto reversal;
1093                         /*
1094                          * Check the lock order hierarchy for a reveresal.
1095                          */
1096                         if (!isitmydescendant(w, w1))
1097                                 continue;
1098                 reversal:
1099                         /*
1100                          * We have a lock order violation, check to see if it
1101                          * is allowed or has already been yelled about.
1102                          */
1103                         mtx_unlock_spin(&w_mtx);
1104 #ifdef BLESSING
1105                         /*
1106                          * If the lock order is blessed, just bail.  We don't
1107                          * look for other lock order violations though, which
1108                          * may be a bug.
1109                          */
1110                         if (blessed(w, w1))
1111                                 return;
1112 #endif
1113                         if (lock1->li_lock == &Giant.lock_object) {
1114                                 if (w1->w_Giant_squawked)
1115                                         return;
1116                                 else
1117                                         w1->w_Giant_squawked = 1;
1118                         } else {
1119                                 if (w1->w_other_squawked)
1120                                         return;
1121                                 else
1122                                         w1->w_other_squawked = 1;
1123                         }
1124                         /*
1125                          * Ok, yell about it.
1126                          */
1127                         if (((lock->lo_flags & LO_SLEEPABLE) != 0 &&
1128                             (lock1->li_lock->lo_flags & LO_SLEEPABLE) == 0))
1129                                 printf(
1130                 "lock order reversal: (sleepable after non-sleepable)\n");
1131                         else if ((lock1->li_lock->lo_flags & LO_SLEEPABLE) == 0
1132                             && lock == &Giant.lock_object)
1133                                 printf(
1134                 "lock order reversal: (Giant after non-sleepable)\n");
1135                         else
1136                                 printf("lock order reversal:\n");
1137                         /*
1138                          * Try to locate an earlier lock with
1139                          * witness w in our list.
1140                          */
1141                         do {
1142                                 lock2 = &lle->ll_children[i];
1143                                 MPASS(lock2->li_lock != NULL);
1144                                 if (lock2->li_lock->lo_witness == w)
1145                                         break;
1146                                 if (i == 0 && lle->ll_next != NULL) {
1147                                         lle = lle->ll_next;
1148                                         i = lle->ll_count - 1;
1149                                         MPASS(i >= 0 && i < LOCK_NCHILDREN);
1150                                 } else
1151                                         i--;
1152                         } while (i >= 0);
1153                         if (i < 0) {
1154                                 printf(" 1st %p %s (%s) @ %s:%d\n",
1155                                     lock1->li_lock, lock1->li_lock->lo_name,
1156                                     w1->w_name, lock1->li_file, lock1->li_line);
1157                                 printf(" 2nd %p %s (%s) @ %s:%d\n", lock,
1158                                     lock->lo_name, w->w_name, file, line);
1159                         } else {
1160                                 printf(" 1st %p %s (%s) @ %s:%d\n",
1161                                     lock2->li_lock, lock2->li_lock->lo_name,
1162                                     lock2->li_lock->lo_witness->w_name,
1163                                     lock2->li_file, lock2->li_line);
1164                                 printf(" 2nd %p %s (%s) @ %s:%d\n",
1165                                     lock1->li_lock, lock1->li_lock->lo_name,
1166                                     w1->w_name, lock1->li_file, lock1->li_line);
1167                                 printf(" 3rd %p %s (%s) @ %s:%d\n", lock,
1168                                     lock->lo_name, w->w_name, file, line);
1169                         }
1170 #ifdef KDB
1171                         goto debugger;
1172 #else
1173                         return;
1174 #endif
1175                 }
1176         }
1177         lock1 = &(*lock_list)->ll_children[(*lock_list)->ll_count - 1];
1178         /*
1179          * If requested, build a new lock order.  However, don't build a new
1180          * relationship between a sleepable lock and Giant if it is in the
1181          * wrong direction.  The correct lock order is that sleepable locks
1182          * always come before Giant.
1183          */
1184         if (flags & LOP_NEWORDER &&
1185             !(lock1->li_lock == &Giant.lock_object &&
1186             (lock->lo_flags & LO_SLEEPABLE) != 0)) {
1187                 CTR3(KTR_WITNESS, "%s: adding %s as a child of %s", __func__,
1188                     w->w_name, lock1->li_lock->lo_witness->w_name);
1189                 if (!itismychild(lock1->li_lock->lo_witness, w))
1190                         /* Witness is dead. */
1191                         return;
1192         }
1193         mtx_unlock_spin(&w_mtx);
1194         return;
1195
1196 #ifdef KDB
1197 debugger:
1198         if (witness_trace)
1199                 kdb_backtrace();
1200         if (witness_kdb)
1201                 kdb_enter(KDB_WHY_WITNESS, __func__);
1202 #endif
1203 }
1204
1205 void
1206 witness_lock(struct lock_object *lock, int flags, const char *file, int line)
1207 {
1208         struct lock_list_entry **lock_list, *lle;
1209         struct lock_instance *instance;
1210         struct witness *w;
1211         struct thread *td;
1212
1213         if (witness_cold || witness_watch == 0 || lock->lo_witness == NULL ||
1214             panicstr != NULL)
1215                 return;
1216         w = lock->lo_witness;
1217         td = curthread;
1218         file = fixup_filename(file);
1219
1220         /* Determine lock list for this lock. */
1221         if (LOCK_CLASS(lock)->lc_flags & LC_SLEEPLOCK)
1222                 lock_list = &td->td_sleeplocks;
1223         else
1224                 lock_list = PCPU_PTR(spinlocks);
1225
1226         /* Check to see if we are recursing on a lock we already own. */
1227         instance = find_instance(*lock_list, lock);
1228         if (instance != NULL) {
1229                 instance->li_flags++;
1230                 CTR4(KTR_WITNESS, "%s: pid %d recursed on %s r=%d", __func__,
1231                     td->td_proc->p_pid, lock->lo_name,
1232                     instance->li_flags & LI_RECURSEMASK);
1233                 instance->li_file = file;
1234                 instance->li_line = line;
1235                 return;
1236         }
1237
1238         /* Update per-witness last file and line acquire. */
1239         w->w_file = file;
1240         w->w_line = line;
1241
1242         /* Find the next open lock instance in the list and fill it. */
1243         lle = *lock_list;
1244         if (lle == NULL || lle->ll_count == LOCK_NCHILDREN) {
1245                 lle = witness_lock_list_get();
1246                 if (lle == NULL)
1247                         return;
1248                 lle->ll_next = *lock_list;
1249                 CTR3(KTR_WITNESS, "%s: pid %d added lle %p", __func__,
1250                     td->td_proc->p_pid, lle);
1251                 *lock_list = lle;
1252         }
1253         instance = &lle->ll_children[lle->ll_count++];
1254         instance->li_lock = lock;
1255         instance->li_line = line;
1256         instance->li_file = file;
1257         if ((flags & LOP_EXCLUSIVE) != 0)
1258                 instance->li_flags = LI_EXCLUSIVE;
1259         else
1260                 instance->li_flags = 0;
1261         CTR4(KTR_WITNESS, "%s: pid %d added %s as lle[%d]", __func__,
1262             td->td_proc->p_pid, lock->lo_name, lle->ll_count - 1);
1263 }
1264
1265 void
1266 witness_upgrade(struct lock_object *lock, int flags, const char *file, int line)
1267 {
1268         struct lock_instance *instance;
1269         struct lock_class *class;
1270
1271         KASSERT(!witness_cold, ("%s: witness_cold", __func__));
1272         if (lock->lo_witness == NULL || witness_watch == 0 || panicstr != NULL)
1273                 return;
1274         class = LOCK_CLASS(lock);
1275         file = fixup_filename(file);
1276         if ((lock->lo_flags & LO_UPGRADABLE) == 0)
1277                 panic("upgrade of non-upgradable lock (%s) %s @ %s:%d",
1278                     class->lc_name, lock->lo_name, file, line);
1279         if ((class->lc_flags & LC_SLEEPLOCK) == 0)
1280                 panic("upgrade of non-sleep lock (%s) %s @ %s:%d",
1281                     class->lc_name, lock->lo_name, file, line);
1282         instance = find_instance(curthread->td_sleeplocks, lock);
1283         if (instance == NULL)
1284                 panic("upgrade of unlocked lock (%s) %s @ %s:%d",
1285                     class->lc_name, lock->lo_name, file, line);
1286         if ((instance->li_flags & LI_EXCLUSIVE) != 0)
1287                 panic("upgrade of exclusive lock (%s) %s @ %s:%d",
1288                     class->lc_name, lock->lo_name, file, line);
1289         if ((instance->li_flags & LI_RECURSEMASK) != 0)
1290                 panic("upgrade of recursed lock (%s) %s r=%d @ %s:%d",
1291                     class->lc_name, lock->lo_name,
1292                     instance->li_flags & LI_RECURSEMASK, file, line);
1293         instance->li_flags |= LI_EXCLUSIVE;
1294 }
1295
1296 void
1297 witness_downgrade(struct lock_object *lock, int flags, const char *file,
1298     int line)
1299 {
1300         struct lock_instance *instance;
1301         struct lock_class *class;
1302
1303         KASSERT(!witness_cold, ("%s: witness_cold", __func__));
1304         if (lock->lo_witness == NULL || witness_watch == 0 || panicstr != NULL)
1305                 return;
1306         class = LOCK_CLASS(lock);
1307         file = fixup_filename(file);
1308         if ((lock->lo_flags & LO_UPGRADABLE) == 0)
1309                 panic("downgrade of non-upgradable lock (%s) %s @ %s:%d",
1310                     class->lc_name, lock->lo_name, file, line);
1311         if ((class->lc_flags & LC_SLEEPLOCK) == 0)
1312                 panic("downgrade of non-sleep lock (%s) %s @ %s:%d",
1313                     class->lc_name, lock->lo_name, file, line);
1314         instance = find_instance(curthread->td_sleeplocks, lock);
1315         if (instance == NULL)
1316                 panic("downgrade of unlocked lock (%s) %s @ %s:%d",
1317                     class->lc_name, lock->lo_name, file, line);
1318         if ((instance->li_flags & LI_EXCLUSIVE) == 0)
1319                 panic("downgrade of shared lock (%s) %s @ %s:%d",
1320                     class->lc_name, lock->lo_name, file, line);
1321         if ((instance->li_flags & LI_RECURSEMASK) != 0)
1322                 panic("downgrade of recursed lock (%s) %s r=%d @ %s:%d",
1323                     class->lc_name, lock->lo_name,
1324                     instance->li_flags & LI_RECURSEMASK, file, line);
1325         instance->li_flags &= ~LI_EXCLUSIVE;
1326 }
1327
1328 void
1329 witness_unlock(struct lock_object *lock, int flags, const char *file, int line)
1330 {
1331         struct lock_list_entry **lock_list, *lle;
1332         struct lock_instance *instance;
1333         struct lock_class *class;
1334         struct thread *td;
1335         register_t s;
1336         int i, j;
1337
1338         if (witness_cold || witness_watch == 0 || lock->lo_witness == NULL ||
1339             panicstr != NULL)
1340                 return;
1341         td = curthread;
1342         class = LOCK_CLASS(lock);
1343         file = fixup_filename(file);
1344
1345         /* Find lock instance associated with this lock. */
1346         if (class->lc_flags & LC_SLEEPLOCK)
1347                 lock_list = &td->td_sleeplocks;
1348         else
1349                 lock_list = PCPU_PTR(spinlocks);
1350         for (; *lock_list != NULL; lock_list = &(*lock_list)->ll_next)
1351                 for (i = 0; i < (*lock_list)->ll_count; i++) {
1352                         instance = &(*lock_list)->ll_children[i];
1353                         if (instance->li_lock == lock)
1354                                 goto found;
1355                 }
1356         panic("lock (%s) %s not locked @ %s:%d", class->lc_name, lock->lo_name,
1357             file, line);
1358 found:
1359
1360         /* First, check for shared/exclusive mismatches. */
1361         if ((instance->li_flags & LI_EXCLUSIVE) != 0 &&
1362             (flags & LOP_EXCLUSIVE) == 0) {
1363                 printf("shared unlock of (%s) %s @ %s:%d\n", class->lc_name,
1364                     lock->lo_name, file, line);
1365                 printf("while exclusively locked from %s:%d\n",
1366                     instance->li_file, instance->li_line);
1367                 panic("excl->ushare");
1368         }
1369         if ((instance->li_flags & LI_EXCLUSIVE) == 0 &&
1370             (flags & LOP_EXCLUSIVE) != 0) {
1371                 printf("exclusive unlock of (%s) %s @ %s:%d\n", class->lc_name,
1372                     lock->lo_name, file, line);
1373                 printf("while share locked from %s:%d\n", instance->li_file,
1374                     instance->li_line);
1375                 panic("share->uexcl");
1376         }
1377
1378         /* If we are recursed, unrecurse. */
1379         if ((instance->li_flags & LI_RECURSEMASK) > 0) {
1380                 CTR4(KTR_WITNESS, "%s: pid %d unrecursed on %s r=%d", __func__,
1381                     td->td_proc->p_pid, instance->li_lock->lo_name,
1382                     instance->li_flags);
1383                 instance->li_flags--;
1384                 return;
1385         }
1386
1387         /* Otherwise, remove this item from the list. */
1388         s = intr_disable();
1389         CTR4(KTR_WITNESS, "%s: pid %d removed %s from lle[%d]", __func__,
1390             td->td_proc->p_pid, instance->li_lock->lo_name,
1391             (*lock_list)->ll_count - 1);
1392         for (j = i; j < (*lock_list)->ll_count - 1; j++)
1393                 (*lock_list)->ll_children[j] =
1394                     (*lock_list)->ll_children[j + 1];
1395         (*lock_list)->ll_count--;
1396         intr_restore(s);
1397
1398         /* If this lock list entry is now empty, free it. */
1399         if ((*lock_list)->ll_count == 0) {
1400                 lle = *lock_list;
1401                 *lock_list = lle->ll_next;
1402                 CTR3(KTR_WITNESS, "%s: pid %d removed lle %p", __func__,
1403                     td->td_proc->p_pid, lle);
1404                 witness_lock_list_free(lle);
1405         }
1406 }
1407
1408 /*
1409  * Warn if any locks other than 'lock' are held.  Flags can be passed in to
1410  * exempt Giant and sleepable locks from the checks as well.  If any
1411  * non-exempt locks are held, then a supplied message is printed to the
1412  * console along with a list of the offending locks.  If indicated in the
1413  * flags then a failure results in a panic as well.
1414  */
1415 int
1416 witness_warn(int flags, struct lock_object *lock, const char *fmt, ...)
1417 {
1418         struct lock_list_entry *lle;
1419         struct lock_instance *lock1;
1420         struct thread *td;
1421         va_list ap;
1422         int i, n;
1423
1424         if (witness_cold || witness_watch == 0 || panicstr != NULL)
1425                 return (0);
1426         n = 0;
1427         td = curthread;
1428         for (lle = td->td_sleeplocks; lle != NULL; lle = lle->ll_next)
1429                 for (i = lle->ll_count - 1; i >= 0; i--) {
1430                         lock1 = &lle->ll_children[i];
1431                         if (lock1->li_lock == lock)
1432                                 continue;
1433                         if (flags & WARN_GIANTOK &&
1434                             lock1->li_lock == &Giant.lock_object)
1435                                 continue;
1436                         if (flags & WARN_SLEEPOK &&
1437                             (lock1->li_lock->lo_flags & LO_SLEEPABLE) != 0)
1438                                 continue;
1439                         if (n == 0) {
1440                                 va_start(ap, fmt);
1441                                 vprintf(fmt, ap);
1442                                 va_end(ap);
1443                                 printf(" with the following");
1444                                 if (flags & WARN_SLEEPOK)
1445                                         printf(" non-sleepable");
1446                                 printf(" locks held:\n");
1447                         }
1448                         n++;
1449                         witness_list_lock(lock1);
1450                 }
1451         if (PCPU_GET(spinlocks) != NULL) {
1452                 /*
1453                  * Since we already hold a spinlock preemption is
1454                  * already blocked.
1455                  */
1456                 if (n == 0) {
1457                         va_start(ap, fmt);
1458                         vprintf(fmt, ap);
1459                         va_end(ap);
1460                         printf(" with the following");
1461                         if (flags & WARN_SLEEPOK)
1462                                 printf(" non-sleepable");
1463                         printf(" locks held:\n");
1464                 }
1465                 n += witness_list_locks(PCPU_PTR(spinlocks));
1466         }
1467         if (flags & WARN_PANIC && n)
1468                 panic("witness_warn");
1469 #ifdef KDB
1470         else if (witness_kdb && n)
1471                 kdb_enter(KDB_WHY_WITNESS, __func__);
1472         else if (witness_trace && n)
1473                 kdb_backtrace();
1474 #endif
1475         return (n);
1476 }
1477
1478 const char *
1479 witness_file(struct lock_object *lock)
1480 {
1481         struct witness *w;
1482
1483         if (witness_cold || witness_watch == 0 || lock->lo_witness == NULL)
1484                 return ("?");
1485         w = lock->lo_witness;
1486         return (w->w_file);
1487 }
1488
1489 int
1490 witness_line(struct lock_object *lock)
1491 {
1492         struct witness *w;
1493
1494         if (witness_cold || witness_watch == 0 || lock->lo_witness == NULL)
1495                 return (0);
1496         w = lock->lo_witness;
1497         return (w->w_line);
1498 }
1499
1500 static struct witness *
1501 enroll(const char *description, struct lock_class *lock_class)
1502 {
1503         struct witness *w;
1504
1505         if (witness_watch == 0 || panicstr != NULL)
1506                 return (NULL);
1507         if ((lock_class->lc_flags & LC_SPINLOCK) && witness_skipspin)
1508                 return (NULL);
1509         mtx_lock_spin(&w_mtx);
1510         STAILQ_FOREACH(w, &w_all, w_list) {
1511                 if (w->w_name == description || (w->w_refcount > 0 &&
1512                     strcmp(description, w->w_name) == 0)) {
1513                         w->w_refcount++;
1514                         mtx_unlock_spin(&w_mtx);
1515                         if (lock_class != w->w_class)
1516                                 panic(
1517                                 "lock (%s) %s does not match earlier (%s) lock",
1518                                     description, lock_class->lc_name,
1519                                     w->w_class->lc_name);
1520                         return (w);
1521                 }
1522         }
1523         if ((w = witness_get()) == NULL) {
1524                 printf("WITNESS: unable to allocate a new witness object\n");
1525                 goto out;
1526         }
1527         w->w_name = description;
1528         w->w_class = lock_class;
1529         w->w_refcount = 1;
1530         STAILQ_INSERT_HEAD(&w_all, w, w_list);
1531         if (lock_class->lc_flags & LC_SPINLOCK) {
1532                 STAILQ_INSERT_HEAD(&w_spin, w, w_typelist);
1533                 w_spin_cnt++;
1534         } else if (lock_class->lc_flags & LC_SLEEPLOCK) {
1535                 STAILQ_INSERT_HEAD(&w_sleep, w, w_typelist);
1536                 w_sleep_cnt++;
1537         } else {
1538                 mtx_unlock_spin(&w_mtx);
1539                 panic("lock class %s is not sleep or spin",
1540                     lock_class->lc_name);
1541         }
1542         mtx_unlock_spin(&w_mtx);
1543 out:
1544         /*
1545          * We issue a warning for any spin locks not defined in the static
1546          * order list as a way to discourage their use (folks should really
1547          * be using non-spin mutexes most of the time).  However, several
1548          * 3rd part device drivers use spin locks because that is all they
1549          * have available on Windows and Linux and they think that normal
1550          * mutexes are insufficient.
1551          */
1552         if ((lock_class->lc_flags & LC_SPINLOCK) && witness_spin_warn)
1553                 printf("WITNESS: spin lock %s not in order list\n",
1554                     description);
1555         return (w);
1556 }
1557
1558 /* Don't let the door bang you on the way out... */
1559 static void
1560 depart(struct witness *w)
1561 {
1562         struct witness_child_list_entry *wcl, *nwcl;
1563         struct witness_list *list;
1564         struct witness *parent;
1565
1566         MPASS(w->w_refcount == 0);
1567         if (w->w_class->lc_flags & LC_SLEEPLOCK) {
1568                 list = &w_sleep;
1569                 w_sleep_cnt--;
1570         } else {
1571                 list = &w_spin;
1572                 w_spin_cnt--;
1573         }
1574         /*
1575          * First, we run through the entire tree looking for any
1576          * witnesses that the outgoing witness is a child of.  For
1577          * each parent that we find, we reparent all the direct
1578          * children of the outgoing witness to its parent.
1579          */
1580         STAILQ_FOREACH(parent, list, w_typelist) {
1581                 if (!isitmychild(parent, w))
1582                         continue;
1583                 removechild(parent, w);
1584         }
1585
1586         /*
1587          * Now we go through and free up the child list of the
1588          * outgoing witness.
1589          */
1590         for (wcl = w->w_children; wcl != NULL; wcl = nwcl) {
1591                 nwcl = wcl->wcl_next;
1592                 w_child_cnt--;
1593                 witness_child_free(wcl);
1594         }
1595
1596         /*
1597          * Detach from various lists and free.
1598          */
1599         STAILQ_REMOVE(list, w, witness, w_typelist);
1600         STAILQ_REMOVE(&w_all, w, witness, w_list);
1601         witness_free(w);
1602 }
1603
1604 /*
1605  * Add "child" as a direct child of "parent".  Returns false if
1606  * we fail due to out of memory.
1607  */
1608 static int
1609 insertchild(struct witness *parent, struct witness *child)
1610 {
1611         struct witness_child_list_entry **wcl;
1612
1613         MPASS(child != NULL && parent != NULL);
1614
1615         /*
1616          * Insert "child" after "parent"
1617          */
1618         wcl = &parent->w_children;
1619         while (*wcl != NULL && (*wcl)->wcl_count == WITNESS_NCHILDREN)
1620                 wcl = &(*wcl)->wcl_next;
1621         if (*wcl == NULL) {
1622                 *wcl = witness_child_get();
1623                 if (*wcl == NULL)
1624                         return (0);
1625                 w_child_cnt++;
1626         }
1627         (*wcl)->wcl_children[(*wcl)->wcl_count++] = child;
1628
1629         return (1);
1630 }
1631
1632
1633 static int
1634 itismychild(struct witness *parent, struct witness *child)
1635 {
1636
1637         MPASS(child != NULL && parent != NULL);
1638         if ((parent->w_class->lc_flags & (LC_SLEEPLOCK | LC_SPINLOCK)) !=
1639             (child->w_class->lc_flags & (LC_SLEEPLOCK | LC_SPINLOCK)))
1640                 panic(
1641                 "%s: parent (%s) and child (%s) are not the same lock type",
1642                     __func__, parent->w_class->lc_name,
1643                     child->w_class->lc_name);
1644
1645         return (insertchild(parent, child));
1646 }
1647
1648 static void
1649 removechild(struct witness *parent, struct witness *child)
1650 {
1651         struct witness_child_list_entry **wcl, *wcl1;
1652         int i;
1653
1654         for (wcl = &parent->w_children; *wcl != NULL; wcl = &(*wcl)->wcl_next)
1655                 for (i = 0; i < (*wcl)->wcl_count; i++)
1656                         if ((*wcl)->wcl_children[i] == child)
1657                                 goto found;
1658         return;
1659 found:
1660         (*wcl)->wcl_count--;
1661         if ((*wcl)->wcl_count > i)
1662                 (*wcl)->wcl_children[i] =
1663                     (*wcl)->wcl_children[(*wcl)->wcl_count];
1664         MPASS((*wcl)->wcl_children[i] != NULL);
1665         if ((*wcl)->wcl_count != 0)
1666                 return;
1667         wcl1 = *wcl;
1668         *wcl = wcl1->wcl_next;
1669         w_child_cnt--;
1670         witness_child_free(wcl1);
1671 }
1672
1673 static int
1674 isitmychild(struct witness *parent, struct witness *child)
1675 {
1676         struct witness_child_list_entry *wcl;
1677         int i;
1678
1679         for (wcl = parent->w_children; wcl != NULL; wcl = wcl->wcl_next) {
1680                 for (i = 0; i < wcl->wcl_count; i++) {
1681                         if (wcl->wcl_children[i] == child)
1682                                 return (1);
1683                 }
1684         }
1685         return (0);
1686 }
1687
1688 static int
1689 isitmydescendant(struct witness *parent, struct witness *child)
1690 {
1691         struct witness_child_list_entry *wcl;
1692         int i, j;
1693
1694         if (isitmychild(parent, child))
1695                 return (1);
1696         j = 0;
1697         for (wcl = parent->w_children; wcl != NULL; wcl = wcl->wcl_next) {
1698                 MPASS(j < 1000);
1699                 for (i = 0; i < wcl->wcl_count; i++) {
1700                         if (isitmydescendant(wcl->wcl_children[i], child))
1701                                 return (1);
1702                 }
1703                 j++;
1704         }
1705         return (0);
1706 }
1707
1708 #ifdef BLESSING
1709 static int
1710 blessed(struct witness *w1, struct witness *w2)
1711 {
1712         int i;
1713         struct witness_blessed *b;
1714
1715         for (i = 0; i < blessed_count; i++) {
1716                 b = &blessed_list[i];
1717                 if (strcmp(w1->w_name, b->b_lock1) == 0) {
1718                         if (strcmp(w2->w_name, b->b_lock2) == 0)
1719                                 return (1);
1720                         continue;
1721                 }
1722                 if (strcmp(w1->w_name, b->b_lock2) == 0)
1723                         if (strcmp(w2->w_name, b->b_lock1) == 0)
1724                                 return (1);
1725         }
1726         return (0);
1727 }
1728 #endif
1729
1730 static struct witness *
1731 witness_get(void)
1732 {
1733         struct witness *w;
1734
1735         if (witness_watch == 0) {
1736                 mtx_unlock_spin(&w_mtx);
1737                 return (NULL);
1738         }
1739         if (STAILQ_EMPTY(&w_free)) {
1740                 witness_watch = 0;
1741                 mtx_unlock_spin(&w_mtx);
1742                 printf("%s: witness exhausted\n", __func__);
1743                 return (NULL);
1744         }
1745         w = STAILQ_FIRST(&w_free);
1746         STAILQ_REMOVE_HEAD(&w_free, w_list);
1747         w_free_cnt--;
1748         bzero(w, sizeof(*w));
1749         return (w);
1750 }
1751
1752 static void
1753 witness_free(struct witness *w)
1754 {
1755
1756         STAILQ_INSERT_HEAD(&w_free, w, w_list);
1757         w_free_cnt++;
1758 }
1759
1760 static struct witness_child_list_entry *
1761 witness_child_get(void)
1762 {
1763         struct witness_child_list_entry *wcl;
1764
1765         if (witness_watch == 0) {
1766                 mtx_unlock_spin(&w_mtx);
1767                 return (NULL);
1768         }
1769         wcl = w_child_free;
1770         if (wcl == NULL) {
1771                 witness_watch = 0;
1772                 mtx_unlock_spin(&w_mtx);
1773                 printf("%s: witness exhausted\n", __func__);
1774                 return (NULL);
1775         }
1776         w_child_free = wcl->wcl_next;
1777         w_child_free_cnt--;
1778         bzero(wcl, sizeof(*wcl));
1779         return (wcl);
1780 }
1781
1782 static void
1783 witness_child_free(struct witness_child_list_entry *wcl)
1784 {
1785
1786         wcl->wcl_next = w_child_free;
1787         w_child_free = wcl;
1788         w_child_free_cnt++;
1789 }
1790
1791 static struct lock_list_entry *
1792 witness_lock_list_get(void)
1793 {
1794         struct lock_list_entry *lle;
1795
1796         if (witness_watch == 0)
1797                 return (NULL);
1798         mtx_lock_spin(&w_mtx);
1799         lle = w_lock_list_free;
1800         if (lle == NULL) {
1801                 witness_watch = 0;
1802                 mtx_unlock_spin(&w_mtx);
1803                 printf("%s: witness exhausted\n", __func__);
1804                 return (NULL);
1805         }
1806         w_lock_list_free = lle->ll_next;
1807         mtx_unlock_spin(&w_mtx);
1808         bzero(lle, sizeof(*lle));
1809         return (lle);
1810 }
1811
1812 static void
1813 witness_lock_list_free(struct lock_list_entry *lle)
1814 {
1815
1816         mtx_lock_spin(&w_mtx);
1817         lle->ll_next = w_lock_list_free;
1818         w_lock_list_free = lle;
1819         mtx_unlock_spin(&w_mtx);
1820 }
1821
1822 static struct lock_instance *
1823 find_instance(struct lock_list_entry *lock_list, struct lock_object *lock)
1824 {
1825         struct lock_list_entry *lle;
1826         struct lock_instance *instance;
1827         int i;
1828
1829         for (lle = lock_list; lle != NULL; lle = lle->ll_next)
1830                 for (i = lle->ll_count - 1; i >= 0; i--) {
1831                         instance = &lle->ll_children[i];
1832                         if (instance->li_lock == lock)
1833                                 return (instance);
1834                 }
1835         return (NULL);
1836 }
1837
1838 static void
1839 witness_list_lock(struct lock_instance *instance)
1840 {
1841         struct lock_object *lock;
1842
1843         lock = instance->li_lock;
1844         printf("%s %s %s", (instance->li_flags & LI_EXCLUSIVE) != 0 ?
1845             "exclusive" : "shared", LOCK_CLASS(lock)->lc_name, lock->lo_name);
1846         if (lock->lo_witness->w_name != lock->lo_name)
1847                 printf(" (%s)", lock->lo_witness->w_name);
1848         printf(" r = %d (%p) locked @ %s:%d\n",
1849             instance->li_flags & LI_RECURSEMASK, lock, instance->li_file,
1850             instance->li_line);
1851 }
1852
1853 #ifdef DDB
1854 static int
1855 witness_thread_has_locks(struct thread *td)
1856 {
1857
1858         return (td->td_sleeplocks != NULL);
1859 }
1860
1861 static int
1862 witness_proc_has_locks(struct proc *p)
1863 {
1864         struct thread *td;
1865
1866         FOREACH_THREAD_IN_PROC(p, td) {
1867                 if (witness_thread_has_locks(td))
1868                         return (1);
1869         }
1870         return (0);
1871 }
1872 #endif
1873
1874 int
1875 witness_list_locks(struct lock_list_entry **lock_list)
1876 {
1877         struct lock_list_entry *lle;
1878         int i, nheld;
1879
1880         nheld = 0;
1881         for (lle = *lock_list; lle != NULL; lle = lle->ll_next)
1882                 for (i = lle->ll_count - 1; i >= 0; i--) {
1883                         witness_list_lock(&lle->ll_children[i]);
1884                         nheld++;
1885                 }
1886         return (nheld);
1887 }
1888
1889 /*
1890  * This is a bit risky at best.  We call this function when we have timed
1891  * out acquiring a spin lock, and we assume that the other CPU is stuck
1892  * with this lock held.  So, we go groveling around in the other CPU's
1893  * per-cpu data to try to find the lock instance for this spin lock to
1894  * see when it was last acquired.
1895  */
1896 void
1897 witness_display_spinlock(struct lock_object *lock, struct thread *owner)
1898 {
1899         struct lock_instance *instance;
1900         struct pcpu *pc;
1901
1902         if (owner->td_critnest == 0 || owner->td_oncpu == NOCPU)
1903                 return;
1904         pc = pcpu_find(owner->td_oncpu);
1905         instance = find_instance(pc->pc_spinlocks, lock);
1906         if (instance != NULL)
1907                 witness_list_lock(instance);
1908 }
1909
1910 void
1911 witness_save(struct lock_object *lock, const char **filep, int *linep)
1912 {
1913         struct lock_list_entry *lock_list;
1914         struct lock_instance *instance;
1915         struct lock_class *class;
1916
1917         KASSERT(!witness_cold, ("%s: witness_cold", __func__));
1918         if (lock->lo_witness == NULL || witness_watch == 0 || panicstr != NULL)
1919                 return;
1920         class = LOCK_CLASS(lock);
1921         if (class->lc_flags & LC_SLEEPLOCK)
1922                 lock_list = curthread->td_sleeplocks;
1923         else {
1924                 if (witness_skipspin)
1925                         return;
1926                 lock_list = PCPU_GET(spinlocks);
1927         }
1928         instance = find_instance(lock_list, lock);
1929         if (instance == NULL)
1930                 panic("%s: lock (%s) %s not locked", __func__,
1931                     class->lc_name, lock->lo_name);
1932         *filep = instance->li_file;
1933         *linep = instance->li_line;
1934 }
1935
1936 void
1937 witness_restore(struct lock_object *lock, const char *file, int line)
1938 {
1939         struct lock_list_entry *lock_list;
1940         struct lock_instance *instance;
1941         struct lock_class *class;
1942
1943         KASSERT(!witness_cold, ("%s: witness_cold", __func__));
1944         if (lock->lo_witness == NULL || witness_watch == 0 || panicstr != NULL)
1945                 return;
1946         class = LOCK_CLASS(lock);
1947         if (class->lc_flags & LC_SLEEPLOCK)
1948                 lock_list = curthread->td_sleeplocks;
1949         else {
1950                 if (witness_skipspin)
1951                         return;
1952                 lock_list = PCPU_GET(spinlocks);
1953         }
1954         instance = find_instance(lock_list, lock);
1955         if (instance == NULL)
1956                 panic("%s: lock (%s) %s not locked", __func__,
1957                     class->lc_name, lock->lo_name);
1958         lock->lo_witness->w_file = file;
1959         lock->lo_witness->w_line = line;
1960         instance->li_file = file;
1961         instance->li_line = line;
1962 }
1963
1964 void
1965 witness_assert(struct lock_object *lock, int flags, const char *file, int line)
1966 {
1967 #ifdef INVARIANT_SUPPORT
1968         struct lock_instance *instance;
1969         struct lock_class *class;
1970
1971         if (lock->lo_witness == NULL || witness_watch == 0 || panicstr != NULL)
1972                 return;
1973         class = LOCK_CLASS(lock);
1974         if ((class->lc_flags & LC_SLEEPLOCK) != 0)
1975                 instance = find_instance(curthread->td_sleeplocks, lock);
1976         else if ((class->lc_flags & LC_SPINLOCK) != 0)
1977                 instance = find_instance(PCPU_GET(spinlocks), lock);
1978         else {
1979                 panic("Lock (%s) %s is not sleep or spin!",
1980                     class->lc_name, lock->lo_name);
1981         }
1982         file = fixup_filename(file);
1983         switch (flags) {
1984         case LA_UNLOCKED:
1985                 if (instance != NULL)
1986                         panic("Lock (%s) %s locked @ %s:%d.",
1987                             class->lc_name, lock->lo_name, file, line);
1988                 break;
1989         case LA_LOCKED:
1990         case LA_LOCKED | LA_RECURSED:
1991         case LA_LOCKED | LA_NOTRECURSED:
1992         case LA_SLOCKED:
1993         case LA_SLOCKED | LA_RECURSED:
1994         case LA_SLOCKED | LA_NOTRECURSED:
1995         case LA_XLOCKED:
1996         case LA_XLOCKED | LA_RECURSED:
1997         case LA_XLOCKED | LA_NOTRECURSED:
1998                 if (instance == NULL) {
1999                         panic("Lock (%s) %s not locked @ %s:%d.",
2000                             class->lc_name, lock->lo_name, file, line);
2001                         break;
2002                 }
2003                 if ((flags & LA_XLOCKED) != 0 &&
2004                     (instance->li_flags & LI_EXCLUSIVE) == 0)
2005                         panic("Lock (%s) %s not exclusively locked @ %s:%d.",
2006                             class->lc_name, lock->lo_name, file, line);
2007                 if ((flags & LA_SLOCKED) != 0 &&
2008                     (instance->li_flags & LI_EXCLUSIVE) != 0)
2009                         panic("Lock (%s) %s exclusively locked @ %s:%d.",
2010                             class->lc_name, lock->lo_name, file, line);
2011                 if ((flags & LA_RECURSED) != 0 &&
2012                     (instance->li_flags & LI_RECURSEMASK) == 0)
2013                         panic("Lock (%s) %s not recursed @ %s:%d.",
2014                             class->lc_name, lock->lo_name, file, line);
2015                 if ((flags & LA_NOTRECURSED) != 0 &&
2016                     (instance->li_flags & LI_RECURSEMASK) != 0)
2017                         panic("Lock (%s) %s recursed @ %s:%d.",
2018                             class->lc_name, lock->lo_name, file, line);
2019                 break;
2020         default:
2021                 panic("Invalid lock assertion at %s:%d.", file, line);
2022
2023         }
2024 #endif  /* INVARIANT_SUPPORT */
2025 }
2026
2027 #ifdef DDB
2028 static void
2029 witness_list(struct thread *td)
2030 {
2031
2032         KASSERT(!witness_cold, ("%s: witness_cold", __func__));
2033         KASSERT(kdb_active, ("%s: not in the debugger", __func__));
2034
2035         if (witness_watch == 0)
2036                 return;
2037
2038         witness_list_locks(&td->td_sleeplocks);
2039
2040         /*
2041          * We only handle spinlocks if td == curthread.  This is somewhat broken
2042          * if td is currently executing on some other CPU and holds spin locks
2043          * as we won't display those locks.  If we had a MI way of getting
2044          * the per-cpu data for a given cpu then we could use
2045          * td->td_oncpu to get the list of spinlocks for this thread
2046          * and "fix" this.
2047          *
2048          * That still wouldn't really fix this unless we locked the scheduler
2049          * lock or stopped the other CPU to make sure it wasn't changing the
2050          * list out from under us.  It is probably best to just not try to
2051          * handle threads on other CPU's for now.
2052          */
2053         if (td == curthread && PCPU_GET(spinlocks) != NULL)
2054                 witness_list_locks(PCPU_PTR(spinlocks));
2055 }
2056
2057 DB_SHOW_COMMAND(locks, db_witness_list)
2058 {
2059         struct thread *td;
2060
2061         if (have_addr)
2062                 td = db_lookup_thread(addr, TRUE);
2063         else
2064                 td = kdb_thread;
2065         witness_list(td);
2066 }
2067
2068 DB_SHOW_COMMAND(alllocks, db_witness_list_all)
2069 {
2070         struct thread *td;
2071         struct proc *p;
2072
2073         /*
2074          * It would be nice to list only threads and processes that actually
2075          * held sleep locks, but that information is currently not exported
2076          * by WITNESS.
2077          */
2078         FOREACH_PROC_IN_SYSTEM(p) {
2079                 if (!witness_proc_has_locks(p))
2080                         continue;
2081                 FOREACH_THREAD_IN_PROC(p, td) {
2082                         if (!witness_thread_has_locks(td))
2083                                 continue;
2084                         db_printf("Process %d (%s) thread %p (%d)\n", p->p_pid,
2085                             td->td_name, td, td->td_tid);
2086                         witness_list(td);
2087                 }
2088         }
2089 }
2090
2091 DB_SHOW_COMMAND(witness, db_witness_display)
2092 {
2093
2094         witness_display(db_printf);
2095 }
2096 #endif