sys/kern/subr_witness.c

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