sys/kern/subr_witness.c

   1 /*-
   2  * Copyright (c) 1998 Berkeley Software Design, Inc. All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   7  * 1. Redistributions of source code must retain the above copyright
   8  *    notice, this list of conditions and the following disclaimer.
   9  * 2. Redistributions in binary form must reproduce the above copyright
  10  *    notice, this list of conditions and the following disclaimer in the
  11  *    documentation and/or other materials provided with the distribution.
  12  * 3. Berkeley Software Design Inc's name may not be used to endorse or
  13  *    promote products derived from this software without specific prior
  14  *    written permission.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY BERKELEY SOFTWARE DESIGN INC ``AS IS'' AND
  17  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  18  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  19  * ARE DISCLAIMED.  IN NO EVENT SHALL BERKELEY SOFTWARE DESIGN INC BE LIABLE
  20  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  21  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  22  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  23  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  24  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  25  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  26  * SUCH DAMAGE.
  27  *
  28  *      from BSDI $Id: mutex_witness.c,v 1.1.2.20 2000/04/27 03:10:27 cp Exp $
  29  *      and BSDI $Id: synch_machdep.c,v 2.3.2.39 2000/04/27 03:10:25 cp Exp $
  30  * $FreeBSD$
  31  */
  32
  33 /*
  34  * Implementation of the `witness' lock verifier.  Originally implemented for
  35  * mutexes in BSD/OS.  Extended to handle generic lock objects and lock
  36  * classes in FreeBSD.
  37  */
  38
  39 /*
  40  *      Main Entry: witness
  41  *      Pronunciation: 'wit-n&s
  42  *      Function: noun
  43  *      Etymology: Middle English witnesse, from Old English witnes knowledge,
  44  *          testimony, witness, from 2wit
  45  *      Date: before 12th century
  46  *      1 : attestation of a fact or event : TESTIMONY
  47  *      2 : one that gives evidence; specifically : one who testifies in
  48  *          a cause or before a judicial tribunal
  49  *      3 : one asked to be present at a transaction so as to be able to
  50  *          testify to its having taken place
  51  *      4 : one who has personal knowledge of something
  52  *      5 a : something serving as evidence or proof : SIGN
  53  *        b : public affirmation by word or example of usually
  54  *            religious faith or conviction <the heroic witness to divine
  55  *            life -- Pilot>
  56  *      6 capitalized : a member of the Jehovah's Witnesses
  57  */
  58
  59 #include "opt_ddb.h"
  60 #include "opt_witness.h"
  61
  62 #include <sys/param.h>
  63 #include <sys/bus.h>
  64 #include <sys/kernel.h>
  65 #include <sys/ktr.h>
  66 #include <sys/lock.h>
  67 #include <sys/malloc.h>
  68 #include <sys/mutex.h>
  69 #include <sys/proc.h>
  70 #include <sys/sysctl.h>
  71 #include <sys/systm.h>
  72
  73 #include <ddb/ddb.h>
  74
  75 #define WITNESS_COUNT 200
  76 #define WITNESS_CHILDCOUNT (WITNESS_COUNT * 4)
  77 /*
  78  * XXX: This is somewhat bogus, as we assume here that at most 1024 threads
  79  * will hold LOCK_NCHILDREN * 2 locks.  We handle failure ok, and we should
  80  * probably be safe for the most part, but it's still a SWAG.
  81  */
  82 #define LOCK_CHILDCOUNT (MAXCPU + 1024) * 2
  83
  84 #define WITNESS_NCHILDREN 6
  85
  86 struct witness_child_list_entry;
  87
  88 struct witness {
  89         const   char *w_name;
  90         struct  lock_class *w_class;
  91         STAILQ_ENTRY(witness) w_list;           /* List of all witnesses. */
  92         STAILQ_ENTRY(witness) w_typelist;       /* Witnesses of a type. */
  93         struct  witness_child_list_entry *w_children;   /* Great evilness... */
  94         const   char *w_file;
  95         int     w_line;
  96         u_int   w_level;
  97         u_int   w_refcount;
  98         u_char  w_Giant_squawked:1;
  99         u_char  w_other_squawked:1;
 100         u_char  w_same_squawked:1;
 101 };
 102
 103 struct witness_child_list_entry {
 104         struct  witness_child_list_entry *wcl_next;
 105         struct  witness *wcl_children[WITNESS_NCHILDREN];
 106         u_int   wcl_count;
 107 };
 108
 109 STAILQ_HEAD(witness_list, witness);
 110
 111 struct witness_blessed {
 112         const   char *b_lock1;
 113         const   char *b_lock2;
 114 };
 115
 116 struct witness_order_list_entry {
 117         const   char *w_name;
 118         struct  lock_class *w_class;
 119 };
 120
 121 static struct   witness *enroll(const char *description,
 122                                 struct lock_class *lock_class);
 123 static int      itismychild(struct witness *parent, struct witness *child);
 124 static void     removechild(struct witness *parent, struct witness *child);
 125 static int      isitmychild(struct witness *parent, struct witness *child);
 126 static int      isitmydescendant(struct witness *parent, struct witness *child);
 127 static int      blessed(struct witness *, struct witness *);
 128 static void     witness_display_list(void(*prnt)(const char *fmt, ...),
 129                                      struct witness_list *list);
 130 static void     witness_displaydescendants(void(*)(const char *fmt, ...),
 131                                            struct witness *);
 132 static void     witness_leveldescendents(struct witness *parent, int level);
 133 static void     witness_levelall(void);
 134 static struct   witness *witness_get(void);
 135 static void     witness_free(struct witness *m);
 136 static struct   witness_child_list_entry *witness_child_get(void);
 137 static void     witness_child_free(struct witness_child_list_entry *wcl);
 138 static struct   lock_list_entry *witness_lock_list_get(void);
 139 static void     witness_lock_list_free(struct lock_list_entry *lle);
 140 static void     witness_display(void(*)(const char *fmt, ...));
 141 static struct   lock_instance *find_instance(struct lock_list_entry *lock_list,
 142                                              struct lock_object *lock);
 143
 144 MALLOC_DEFINE(M_WITNESS, "witness", "witness structure");
 145
 146 static int witness_watch = 1;
 147 TUNABLE_INT("debug.witness_watch", &witness_watch);
 148 SYSCTL_INT(_debug, OID_AUTO, witness_watch, CTLFLAG_RD, &witness_watch, 0, "");
 149
 150 #ifdef DDB
 151 /*
 152  * When DDB is enabled and witness_ddb is set to 1, it will cause the system to
 153  * drop into kdebug() when:
 154  *      - a lock heirarchy violation occurs
 155  *      - locks are held when going to sleep.
 156  */
 157 #ifdef WITNESS_DDB
 158 int     witness_ddb = 1;
 159 #else
 160 int     witness_ddb = 0;
 161 #endif
 162 TUNABLE_INT("debug.witness_ddb", &witness_ddb);
 163 SYSCTL_INT(_debug, OID_AUTO, witness_ddb, CTLFLAG_RW, &witness_ddb, 0, "");
 164 #endif /* DDB */
 165
 166 #ifdef WITNESS_SKIPSPIN
 167 int     witness_skipspin = 1;
 168 #else
 169 int     witness_skipspin = 0;
 170 #endif
 171 TUNABLE_INT("debug.witness_skipspin", &witness_skipspin);
 172 SYSCTL_INT(_debug, OID_AUTO, witness_skipspin, CTLFLAG_RD, &witness_skipspin, 0,
 173     "");
 174
 175 static struct mtx w_mtx;
 176 static struct witness_list w_free = STAILQ_HEAD_INITIALIZER(w_free);
 177 static struct witness_list w_all = STAILQ_HEAD_INITIALIZER(w_all);
 178 static struct witness_list w_spin = STAILQ_HEAD_INITIALIZER(w_spin);
 179 static struct witness_list w_sleep = STAILQ_HEAD_INITIALIZER(w_sleep);
 180 static struct witness_child_list_entry *w_child_free = NULL;
 181 static struct lock_list_entry *w_lock_list_free = NULL;
 182 static int witness_dead;        /* fatal error, probably no memory */
 183
 184 static struct witness w_data[WITNESS_COUNT];
 185 static struct witness_child_list_entry w_childdata[WITNESS_CHILDCOUNT];
 186 static struct lock_list_entry w_locklistdata[LOCK_CHILDCOUNT];
 187
 188 static struct witness_order_list_entry order_lists[] = {
 189         { "Giant", &lock_class_mtx_sleep },
 190         { "proctree", &lock_class_sx },
 191         { "allproc", &lock_class_sx },
 192         { "process group", &lock_class_mtx_sleep },
 193         { "process lock", &lock_class_mtx_sleep },
 194         { "session", &lock_class_mtx_sleep },
 195         { "uidinfo hash", &lock_class_mtx_sleep },
 196         { "uidinfo struct", &lock_class_mtx_sleep },
 197         { NULL, NULL },
 198         /*
 199          * spin locks
 200          */
 201 #ifdef SMP
 202         { "ap boot", &lock_class_mtx_spin },
 203 #ifdef __i386__
 204         { "com", &lock_class_mtx_spin },
 205 #endif
 206 #endif
 207         { "sio", &lock_class_mtx_spin },
 208 #ifdef __i386__
 209         { "cy", &lock_class_mtx_spin },
 210 #endif
 211         { "ng_node", &lock_class_mtx_spin },
 212         { "ng_worklist", &lock_class_mtx_spin },
 213         { "ithread table lock", &lock_class_mtx_spin },
 214         { "sched lock", &lock_class_mtx_spin },
 215         { "callout", &lock_class_mtx_spin },
 216         /*
 217          * leaf locks
 218          */
 219         { "allpmaps", &lock_class_mtx_spin },
 220         { "vm page buckets mutex", &lock_class_mtx_spin },
 221         { "icu", &lock_class_mtx_spin },
 222 #ifdef SMP
 223         { "smp rendezvous", &lock_class_mtx_spin },
 224 #endif
 225         { "clk", &lock_class_mtx_spin },
 226         { "mutex profiling lock", &lock_class_mtx_spin },
 227         { NULL, NULL },
 228         { NULL, NULL }
 229 };
 230
 231 /*
 232  * Pairs of locks which have been blessed
 233  * Don't complain about order problems with blessed locks
 234  */
 235 static struct witness_blessed blessed_list[] = {
 236 };
 237 static int blessed_count =
 238         sizeof(blessed_list) / sizeof(struct witness_blessed);
 239
 240 /*
 241  * List of all locks in the system.
 242  */
 243 STAILQ_HEAD(, lock_object) all_locks = STAILQ_HEAD_INITIALIZER(all_locks);
 244
 245 static struct mtx all_mtx = {
 246         { &lock_class_mtx_sleep,        /* mtx_object.lo_class */
 247           "All locks list",             /* mtx_object.lo_name */
 248           "All locks list",             /* mtx_object.lo_type */
 249           LO_INITIALIZED,               /* mtx_object.lo_flags */
 250           { NULL },                     /* mtx_object.lo_list */
 251           NULL },                       /* mtx_object.lo_witness */
 252         MTX_UNOWNED, 0,                 /* mtx_lock, mtx_recurse */
 253         TAILQ_HEAD_INITIALIZER(all_mtx.mtx_blocked),
 254         { NULL, NULL }                  /* mtx_contested */
 255 };
 256
 257 /*
 258  * This global is set to 0 once it becomes safe to use the witness code.
 259  */
 260 static int witness_cold = 1;
 261
 262 /*
 263  * Global variables for book keeping.
 264  */
 265 static int lock_cur_cnt;
 266 static int lock_max_cnt;
 267
 268 /*
 269  * The WITNESS-enabled diagnostic code.
 270  */
 271 static void
 272 witness_initialize(void *dummy __unused)
 273 {
 274         struct lock_object *lock;
 275         struct witness_order_list_entry *order;
 276         struct witness *w, *w1;
 277         int i;
 278
 279         /*
 280          * We have to release Giant before initializing its witness
 281          * structure so that WITNESS doesn't get confused.
 282          */
 283         mtx_unlock(&Giant);
 284         mtx_assert(&Giant, MA_NOTOWNED);
 285
 286         CTR1(KTR_WITNESS, "%s: initializing witness", __func__);
 287         STAILQ_INSERT_HEAD(&all_locks, &all_mtx.mtx_object, lo_list);
 288         mtx_init(&w_mtx, "witness lock", NULL, MTX_SPIN | MTX_QUIET |
 289             MTX_NOWITNESS);
 290         for (i = 0; i < WITNESS_COUNT; i++)
 291                 witness_free(&w_data[i]);
 292         for (i = 0; i < WITNESS_CHILDCOUNT; i++)
 293                 witness_child_free(&w_childdata[i]);
 294         for (i = 0; i < LOCK_CHILDCOUNT; i++)
 295                 witness_lock_list_free(&w_locklistdata[i]);
 296
 297         /* First add in all the specified order lists. */
 298         for (order = order_lists; order->w_name != NULL; order++) {
 299                 w = enroll(order->w_name, order->w_class);
 300                 if (w == NULL)
 301                         continue;
 302                 w->w_file = "order list";
 303                 for (order++; order->w_name != NULL; order++) {
 304                         w1 = enroll(order->w_name, order->w_class);
 305                         if (w1 == NULL)
 306                                 continue;
 307                         w1->w_file = "order list";
 308                         itismychild(w, w1);
 309                         w = w1;
 310                 }
 311         }
 312
 313         /* Iterate through all locks and add them to witness. */
 314         mtx_lock(&all_mtx);
 315         STAILQ_FOREACH(lock, &all_locks, lo_list) {
 316                 if (lock->lo_flags & LO_WITNESS)
 317                         lock->lo_witness = enroll(lock->lo_type,
 318                             lock->lo_class);
 319                 else
 320                         lock->lo_witness = NULL;
 321         }
 322         mtx_unlock(&all_mtx);
 323
 324         /* Mark the witness code as being ready for use. */
 325         atomic_store_rel_int(&witness_cold, 0);
 326
 327         mtx_lock(&Giant);
 328 }
 329 SYSINIT(witness_init, SI_SUB_WITNESS, SI_ORDER_FIRST, witness_initialize, NULL)
 330
 331 void
 332 witness_init(struct lock_object *lock)
 333 {
 334         struct lock_class *class;
 335
 336         class = lock->lo_class;
 337         if (lock->lo_flags & LO_INITIALIZED)
 338                 panic("%s: lock (%s) %s is already initialized", __func__,
 339                     class->lc_name, lock->lo_name);
 340         if ((lock->lo_flags & LO_RECURSABLE) != 0 &&
 341             (class->lc_flags & LC_RECURSABLE) == 0)
 342                 panic("%s: lock (%s) %s can not be recursable", __func__,
 343                     class->lc_name, lock->lo_name);
 344         if ((lock->lo_flags & LO_SLEEPABLE) != 0 &&
 345             (class->lc_flags & LC_SLEEPABLE) == 0)
 346                 panic("%s: lock (%s) %s can not be sleepable", __func__,
 347                     class->lc_name, lock->lo_name);
 348         if ((lock->lo_flags & LO_UPGRADABLE) != 0 &&
 349             (class->lc_flags & LC_UPGRADABLE) == 0)
 350                 panic("%s: lock (%s) %s can not be upgradable", __func__,
 351                     class->lc_name, lock->lo_name);
 352
 353         mtx_lock(&all_mtx);
 354         STAILQ_INSERT_TAIL(&all_locks, lock, lo_list);
 355         lock->lo_flags |= LO_INITIALIZED;
 356         lock_cur_cnt++;
 357         if (lock_cur_cnt > lock_max_cnt)
 358                 lock_max_cnt = lock_cur_cnt;
 359         mtx_unlock(&all_mtx);
 360         if (!witness_cold && !witness_dead && panicstr == NULL &&
 361             (lock->lo_flags & LO_WITNESS) != 0)
 362                 lock->lo_witness = enroll(lock->lo_type, class);
 363         else
 364                 lock->lo_witness = NULL;
 365 }
 366
 367 void
 368 witness_destroy(struct lock_object *lock)
 369 {
 370         struct witness *w;
 371
 372         if (witness_cold)
 373                 panic("lock (%s) %s destroyed while witness_cold",
 374                     lock->lo_class->lc_name, lock->lo_name);
 375         if ((lock->lo_flags & LO_INITIALIZED) == 0)
 376                 panic("%s: lock (%s) %s is not initialized", __func__,
 377                     lock->lo_class->lc_name, lock->lo_name);
 378
 379         /* XXX: need to verify that no one holds the lock */
 380         w = lock->lo_witness;
 381         if (w != NULL) {
 382                 mtx_lock_spin(&w_mtx);
 383                 w->w_refcount--;
 384                 if (w->w_refcount == 0) {
 385                         CTR2(KTR_WITNESS,
 386                             "%s: marking witness %s as dead", __func__, w->w_name);
 387                         w->w_name = "(dead)";
 388                         w->w_file = "(dead)";
 389                         w->w_line = 0;
 390                 }
 391                 mtx_unlock_spin(&w_mtx);
 392         }
 393
 394         mtx_lock(&all_mtx);
 395         lock_cur_cnt--;
 396         STAILQ_REMOVE(&all_locks, lock, lock_object, lo_list);
 397         lock->lo_flags &= ~LO_INITIALIZED;
 398         mtx_unlock(&all_mtx);
 399 }
 400
 401 static void
 402 witness_display_list(void(*prnt)(const char *fmt, ...),
 403                      struct witness_list *list)
 404 {
 405         struct witness *w, *w1;
 406         int found;
 407
 408         STAILQ_FOREACH(w, list, w_typelist) {
 409                 if (w->w_file == NULL)
 410                         continue;
 411                 found = 0;
 412                 STAILQ_FOREACH(w1, list, w_typelist) {
 413                         if (isitmychild(w1, w)) {
 414                                 found++;
 415                                 break;
 416                         }
 417                 }
 418                 if (found)
 419                         continue;
 420                 /*
 421                  * This lock has no anscestors, display its descendants.
 422                  */
 423                 witness_displaydescendants(prnt, w);
 424         }
 425 }
 426
 427 static void
 428 witness_display(void(*prnt)(const char *fmt, ...))
 429 {
 430         struct witness *w;
 431
 432         KASSERT(!witness_cold, ("%s: witness_cold", __func__));
 433         witness_levelall();
 434
 435         /*
 436          * First, handle sleep locks which have been acquired at least
 437          * once.
 438          */
 439         prnt("Sleep locks:\n");
 440         witness_display_list(prnt, &w_sleep);
 441
 442         /*
 443          * Now do spin locks which have been acquired at least once.
 444          */
 445         prnt("\nSpin locks:\n");
 446         witness_display_list(prnt, &w_spin);
 447
 448         /*
 449          * Finally, any locks which have not been acquired yet.
 450          */
 451         prnt("\nLocks which were never acquired:\n");
 452         STAILQ_FOREACH(w, &w_all, w_list) {
 453                 if (w->w_file != NULL)
 454                         continue;
 455                 prnt("%s\n", w->w_name);
 456         }
 457 }
 458
 459 void
 460 witness_lock(struct lock_object *lock, int flags, const char *file, int line)
 461 {
 462         struct lock_list_entry **lock_list, *lle;
 463         struct lock_instance *lock1, *lock2;
 464         struct lock_class *class;
 465         struct witness *w, *w1;
 466         struct thread *td;
 467         int i, j;
 468 #ifdef DDB
 469         int go_into_ddb = 0;
 470 #endif /* DDB */
 471
 472         if (witness_cold || witness_dead || lock->lo_witness == NULL ||
 473             panicstr != NULL)
 474                 return;
 475         w = lock->lo_witness;
 476         class = lock->lo_class;
 477         td = curthread;
 478
 479         if (class->lc_flags & LC_SLEEPLOCK) {
 480                 /*
 481                  * Since spin locks include a critical section, this check
 482                  * impliclty enforces a lock order of all sleep locks before
 483                  * all spin locks.
 484                  */
 485                 if (td->td_critnest != 0 && (flags & LOP_TRYLOCK) == 0)
 486                         panic("blockable sleep lock (%s) %s @ %s:%d",
 487                             class->lc_name, lock->lo_name, file, line);
 488                 lock_list = &td->td_sleeplocks;
 489         } else
 490                 lock_list = PCPU_PTR(spinlocks);
 491
 492         /*
 493          * Try locks do not block if they fail to acquire the lock, thus
 494          * there is no danger of deadlocks or of switching while holding a
 495          * spin lock if we acquire a lock via a try operation.
 496          */
 497         if (flags & LOP_TRYLOCK)
 498                 goto out;
 499
 500         /*
 501          * Is this the first lock acquired?  If so, then no order checking
 502          * is needed.
 503          */
 504         if (*lock_list == NULL)
 505                 goto out;
 506
 507         /*
 508          * Check to see if we are recursing on a lock we already own.
 509          */
 510         lock1 = find_instance(*lock_list, lock);
 511         if (lock1 != NULL) {
 512                 if ((lock1->li_flags & LI_EXCLUSIVE) != 0 &&
 513                     (flags & LOP_EXCLUSIVE) == 0) {
 514                         printf("shared lock of (%s) %s @ %s:%d\n",
 515                             class->lc_name, lock->lo_name, file, line);
 516                         printf("while exclusively locked from %s:%d\n",
 517                             lock1->li_file, lock1->li_line);
 518                         panic("share->excl");
 519                 }
 520                 if ((lock1->li_flags & LI_EXCLUSIVE) == 0 &&
 521                     (flags & LOP_EXCLUSIVE) != 0) {
 522                         printf("exclusive lock of (%s) %s @ %s:%d\n",
 523                             class->lc_name, lock->lo_name, file, line);
 524                         printf("while share locked from %s:%d\n",
 525                             lock1->li_file, lock1->li_line);
 526                         panic("excl->share");
 527                 }
 528                 lock1->li_flags++;
 529                 if ((lock->lo_flags & LO_RECURSABLE) == 0) {
 530                         printf(
 531                         "recursed on non-recursive lock (%s) %s @ %s:%d\n",
 532                             class->lc_name, lock->lo_name, file, line);
 533                         printf("first acquired @ %s:%d\n", lock1->li_file,
 534                             lock1->li_line);
 535                         panic("recurse");
 536                 }
 537                 CTR4(KTR_WITNESS, "%s: pid %d recursed on %s r=%d", __func__,
 538                     td->td_proc->p_pid, lock->lo_name,
 539                     lock1->li_flags & LI_RECURSEMASK);
 540                 lock1->li_file = file;
 541                 lock1->li_line = line;
 542                 return;
 543         }
 544
 545         /*
 546          * Check for duplicate locks of the same type.  Note that we only
 547          * have to check for this on the last lock we just acquired.  Any
 548          * other cases will be caught as lock order violations.
 549          */
 550         lock1 = &(*lock_list)->ll_children[(*lock_list)->ll_count - 1];
 551         w1 = lock1->li_lock->lo_witness;
 552         if (w1 == w) {
 553                 if (w->w_same_squawked || (lock->lo_flags & LO_DUPOK))
 554                         goto out;
 555                 w->w_same_squawked = 1;
 556                 printf("acquiring duplicate lock of same type: \"%s\"\n",
 557                         lock->lo_type);
 558                 printf(" 1st %s @ %s:%d\n", lock1->li_lock->lo_name,
 559                     lock1->li_file, lock1->li_line);
 560                 printf(" 2nd %s @ %s:%d\n", lock->lo_name, file, line);
 561 #ifdef DDB
 562                 go_into_ddb = 1;
 563 #endif /* DDB */
 564                 goto out;
 565         }
 566         MPASS(!mtx_owned(&w_mtx));
 567         mtx_lock_spin(&w_mtx);
 568         /*
 569          * If we have a known higher number just say ok
 570          */
 571         if (witness_watch > 1 && w->w_level > w1->w_level) {
 572                 mtx_unlock_spin(&w_mtx);
 573                 goto out;
 574         }
 575         if (isitmydescendant(w1, w)) {
 576                 mtx_unlock_spin(&w_mtx);
 577                 goto out;
 578         }
 579         for (j = 0, lle = *lock_list; lle != NULL; lle = lle->ll_next) {
 580                 for (i = lle->ll_count - 1; i >= 0; i--, j++) {
 581
 582                         MPASS(j < WITNESS_COUNT);
 583                         lock1 = &lle->ll_children[i];
 584                         w1 = lock1->li_lock->lo_witness;
 585
 586                         /*
 587                          * If this lock doesn't undergo witness checking,
 588                          * then skip it.
 589                          */
 590                         if (w1 == NULL) {
 591                                 KASSERT((lock1->li_lock->lo_flags & LO_WITNESS) == 0,
 592                                     ("lock missing witness structure"));
 593                                 continue;
 594                         }
 595                         /*
 596                          * If we are locking Giant and we slept with this
 597                          * lock, then skip it.
 598                          */
 599                         if ((lock1->li_flags & LI_SLEPT) != 0 &&
 600                             lock == &Giant.mtx_object)
 601                                 continue;
 602                         /*
 603                          * If we are locking a sleepable lock and this lock
 604                          * isn't sleepable and isn't Giant, we want to treat
 605                          * it as a lock order violation to enfore a general
 606                          * lock order of sleepable locks before non-sleepable
 607                          * locks.  Thus, we only bother checking the lock
 608                          * order hierarchy if we pass the initial test.
 609                          */
 610                         if (!((lock->lo_flags & LO_SLEEPABLE) != 0 &&
 611                             ((lock1->li_lock->lo_flags & LO_SLEEPABLE) == 0 &&
 612                             lock1->li_lock != &Giant.mtx_object)) &&
 613                             !isitmydescendant(w, w1))
 614                                 continue;
 615                         /*
 616                          * We have a lock order violation, check to see if it
 617                          * is allowed or has already been yelled about.
 618                          */
 619                         mtx_unlock_spin(&w_mtx);
 620                         if (blessed(w, w1))
 621                                 goto out;
 622                         if (lock1->li_lock == &Giant.mtx_object) {
 623                                 if (w1->w_Giant_squawked)
 624                                         goto out;
 625                                 else
 626                                         w1->w_Giant_squawked = 1;
 627                         } else {
 628                                 if (w1->w_other_squawked)
 629                                         goto out;
 630                                 else
 631                                         w1->w_other_squawked = 1;
 632                         }
 633                         /*
 634                          * Ok, yell about it.
 635                          */
 636                         printf("lock order reversal\n");
 637                         /*
 638                          * Try to locate an earlier lock with
 639                          * witness w in our list.
 640                          */
 641                         do {
 642                                 lock2 = &lle->ll_children[i];
 643                                 MPASS(lock2->li_lock != NULL);
 644                                 if (lock2->li_lock->lo_witness == w)
 645                                         break;
 646                                 i--;
 647                                 if (i == 0 && lle->ll_next != NULL) {
 648                                         lle = lle->ll_next;
 649                                         i = lle->ll_count - 1;
 650                                         MPASS(i != 0);
 651                                 }
 652                         } while (i >= 0);
 653                         if (i < 0) {
 654                                 printf(" 1st %p %s (%s) @ %s:%d\n",
 655                                     lock1->li_lock, lock1->li_lock->lo_name,
 656                                     lock1->li_lock->lo_type, lock1->li_file,
 657                                     lock1->li_line);
 658                                 printf(" 2nd %p %s (%s) @ %s:%d\n", lock,
 659                                     lock->lo_name, lock->lo_type, file, line);
 660                         } else {
 661                                 printf(" 1st %p %s (%s) @ %s:%d\n",
 662                                     lock2->li_lock, lock2->li_lock->lo_name,
 663                                     lock2->li_lock->lo_type, lock2->li_file,
 664                                     lock2->li_line);
 665                                 printf(" 2nd %p %s (%s) @ %s:%d\n",
 666                                     lock1->li_lock, lock1->li_lock->lo_name,
 667                                     lock1->li_lock->lo_type, lock1->li_file,
 668                                     lock1->li_line);
 669                                 printf(" 3rd %p %s (%s) @ %s:%d\n", lock,
 670                                     lock->lo_name, lock->lo_type, file, line);
 671                         }
 672 #ifdef DDB
 673                         go_into_ddb = 1;
 674 #endif /* DDB */
 675                         goto out;
 676                 }
 677         }
 678         lock1 = &(*lock_list)->ll_children[(*lock_list)->ll_count - 1];
 679         /*
 680          * Don't build a new relationship if we are locking Giant just
 681          * after waking up and the previous lock in the list was acquired
 682          * prior to blocking.
 683          */
 684         if (lock == &Giant.mtx_object && (lock1->li_flags & LI_SLEPT) != 0)
 685                 mtx_unlock_spin(&w_mtx);
 686         else {
 687                 CTR3(KTR_WITNESS, "%s: adding %s as a child of %s", __func__,
 688                     lock->lo_type, lock1->li_lock->lo_type);
 689                 if (!itismychild(lock1->li_lock->lo_witness, w))
 690                         mtx_unlock_spin(&w_mtx);
 691         }
 692
 693 out:
 694 #ifdef DDB
 695         if (witness_ddb && go_into_ddb)
 696                 Debugger(__func__);
 697 #endif /* DDB */
 698         w->w_file = file;
 699         w->w_line = line;
 700
 701         lle = *lock_list;
 702         if (lle == NULL || lle->ll_count == LOCK_NCHILDREN) {
 703                 lle = witness_lock_list_get();
 704                 if (lle == NULL)
 705                         return;
 706                 lle->ll_next = *lock_list;
 707                 CTR3(KTR_WITNESS, "%s: pid %d added lle %p", __func__,
 708                     td->td_proc->p_pid, lle);
 709                 *lock_list = lle;
 710         }
 711         lock1 = &lle->ll_children[lle->ll_count++];
 712         lock1->li_lock = lock;
 713         lock1->li_line = line;
 714         lock1->li_file = file;
 715         if ((flags & LOP_EXCLUSIVE) != 0)
 716                 lock1->li_flags = LI_EXCLUSIVE;
 717         else
 718                 lock1->li_flags = 0;
 719         CTR4(KTR_WITNESS, "%s: pid %d added %s as lle[%d]", __func__,
 720             td->td_proc->p_pid, lock->lo_name, lle->ll_count - 1);
 721 }
 722
 723 void
 724 witness_upgrade(struct lock_object *lock, int flags, const char *file, int line)
 725 {
 726         struct lock_instance *instance;
 727         struct lock_class *class;
 728
 729         KASSERT(!witness_cold, ("%s: witness_cold", __func__));
 730         if (lock->lo_witness == NULL || witness_dead || panicstr != NULL)
 731                 return;
 732         class = lock->lo_class;
 733         if ((lock->lo_flags & LO_UPGRADABLE) == 0)
 734                 panic("upgrade of non-upgradable lock (%s) %s @ %s:%d",
 735                     class->lc_name, lock->lo_name, file, line);
 736         if ((flags & LOP_TRYLOCK) == 0)
 737                 panic("non-try upgrade of lock (%s) %s @ %s:%d", class->lc_name,
 738                     lock->lo_name, file, line);
 739         if ((lock->lo_class->lc_flags & LC_SLEEPLOCK) == 0)
 740                 panic("upgrade of non-sleep lock (%s) %s @ %s:%d",
 741                     class->lc_name, lock->lo_name, file, line);
 742         instance = find_instance(curthread->td_sleeplocks, lock);
 743         if (instance == NULL)
 744                 panic("upgrade of unlocked lock (%s) %s @ %s:%d",
 745                     class->lc_name, lock->lo_name, file, line);
 746         if ((instance->li_flags & LI_EXCLUSIVE) != 0)
 747                 panic("upgrade of exclusive lock (%s) %s @ %s:%d",
 748                     class->lc_name, lock->lo_name, file, line);
 749         if ((instance->li_flags & LI_RECURSEMASK) != 0)
 750                 panic("upgrade of recursed lock (%s) %s r=%d @ %s:%d",
 751                     class->lc_name, lock->lo_name,
 752                     instance->li_flags & LI_RECURSEMASK, file, line);
 753         instance->li_flags |= LI_EXCLUSIVE;
 754 }
 755
 756 void
 757 witness_downgrade(struct lock_object *lock, int flags, const char *file,
 758     int line)
 759 {
 760         struct lock_instance *instance;
 761         struct lock_class *class;
 762
 763         KASSERT(!witness_cold, ("%s: witness_cold", __func__));
 764         if (lock->lo_witness == NULL || witness_dead || panicstr != NULL)
 765                 return;
 766         class = lock->lo_class;
 767         if ((lock->lo_flags & LO_UPGRADABLE) == 0)
 768                 panic("downgrade of non-upgradable lock (%s) %s @ %s:%d",
 769                     class->lc_name, lock->lo_name, file, line);
 770         if ((lock->lo_class->lc_flags & LC_SLEEPLOCK) == 0)
 771                 panic("downgrade of non-sleep lock (%s) %s @ %s:%d",
 772                     class->lc_name, lock->lo_name, file, line);
 773         instance = find_instance(curthread->td_sleeplocks, lock);
 774         if (instance == NULL)
 775                 panic("downgrade of unlocked lock (%s) %s @ %s:%d",
 776                     class->lc_name, lock->lo_name, file, line);
 777         if ((instance->li_flags & LI_EXCLUSIVE) == 0)
 778                 panic("downgrade of shared lock (%s) %s @ %s:%d",
 779                     class->lc_name, lock->lo_name, file, line);
 780         if ((instance->li_flags & LI_RECURSEMASK) != 0)
 781                 panic("downgrade of recursed lock (%s) %s r=%d @ %s:%d",
 782                     class->lc_name, lock->lo_name,
 783                     instance->li_flags & LI_RECURSEMASK, file, line);
 784         instance->li_flags &= ~LI_EXCLUSIVE;
 785 }
 786
 787 void
 788 witness_unlock(struct lock_object *lock, int flags, const char *file, int line)
 789 {
 790         struct lock_list_entry **lock_list, *lle;
 791         struct lock_instance *instance;
 792         struct lock_class *class;
 793         struct thread *td;
 794         register_t s;
 795         int i, j;
 796
 797         if (witness_cold || witness_dead || lock->lo_witness == NULL ||
 798             panicstr != NULL)
 799                 return;
 800         td = curthread;
 801         class = lock->lo_class;
 802         if (class->lc_flags & LC_SLEEPLOCK)
 803                 lock_list = &td->td_sleeplocks;
 804         else
 805                 lock_list = PCPU_PTR(spinlocks);
 806         for (; *lock_list != NULL; lock_list = &(*lock_list)->ll_next)
 807                 for (i = 0; i < (*lock_list)->ll_count; i++) {
 808                         instance = &(*lock_list)->ll_children[i];
 809                         if (instance->li_lock == lock) {
 810                                 if ((instance->li_flags & LI_EXCLUSIVE) != 0 &&
 811                                     (flags & LOP_EXCLUSIVE) == 0) {
 812                                         printf(
 813                                         "shared unlock of (%s) %s @ %s:%d\n",
 814                                             class->lc_name, lock->lo_name,
 815                                             file, line);
 816                                         printf(
 817                                         "while exclusively locked from %s:%d\n",
 818                                             instance->li_file,
 819                                             instance->li_line);
 820                                         panic("excl->ushare");
 821                                 }
 822                                 if ((instance->li_flags & LI_EXCLUSIVE) == 0 &&
 823                                     (flags & LOP_EXCLUSIVE) != 0) {
 824                                         printf(
 825                                         "exclusive unlock of (%s) %s @ %s:%d\n",
 826                                             class->lc_name, lock->lo_name,
 827                                             file, line);
 828                                         printf(
 829                                         "while share locked from %s:%d\n",
 830                                             instance->li_file,
 831                                             instance->li_line);
 832                                         panic("share->uexcl");
 833                                 }
 834                                 /* If we are recursed, unrecurse. */
 835                                 if ((instance->li_flags & LI_RECURSEMASK) > 0) {
 836                                         CTR4(KTR_WITNESS,
 837                                     "%s: pid %d unrecursed on %s r=%d", __func__,
 838                                             td->td_proc->p_pid,
 839                                             instance->li_lock->lo_name,
 840                                             instance->li_flags);
 841                                         instance->li_flags--;
 842                                         return;
 843                                 }
 844                                 s = intr_disable();
 845                                 CTR4(KTR_WITNESS,
 846                                     "%s: pid %d removed %s from lle[%d]", __func__,
 847                                     td->td_proc->p_pid,
 848                                     instance->li_lock->lo_name,
 849                                     (*lock_list)->ll_count - 1);
 850                                 (*lock_list)->ll_count--;
 851                                 for (j = i; j < (*lock_list)->ll_count; j++)
 852                                         (*lock_list)->ll_children[j] =
 853                                             (*lock_list)->ll_children[j + 1];
 854                                 intr_restore(s);
 855                                 if ((*lock_list)->ll_count == 0) {
 856                                         lle = *lock_list;
 857                                         *lock_list = lle->ll_next;
 858                                         CTR3(KTR_WITNESS,
 859                                             "%s: pid %d removed lle %p", __func__,
 860                                             td->td_proc->p_pid, lle);
 861                                         witness_lock_list_free(lle);
 862                                 }
 863                                 return;
 864                         }
 865                 }
 866         panic("lock (%s) %s not locked @ %s:%d", class->lc_name, lock->lo_name,
 867             file, line);
 868 }
 869
 870 /*
 871  * Warn if any held locks are not sleepable.  Note that Giant and the lock
 872  * passed in are both special cases since they are both released during the
 873  * sleep process and aren't actually held while the thread is asleep.
 874  */
 875 int
 876 witness_sleep(int check_only, struct lock_object *lock, const char *file,
 877               int line)
 878 {
 879         struct lock_list_entry **lock_list, *lle;
 880         struct lock_instance *lock1;
 881         struct thread *td;
 882         int i, n;
 883
 884         if (witness_dead || panicstr != NULL)
 885                 return (0);
 886         KASSERT(!witness_cold, ("%s: witness_cold", __func__));
 887         n = 0;
 888         /*
 889          * Preemption bad because we need PCPU_PTR(spinlocks) to not change.
 890          */
 891         critical_enter();
 892         td = curthread;
 893         lock_list = &td->td_sleeplocks;
 894 again:
 895         for (lle = *lock_list; lle != NULL; lle = lle->ll_next)
 896                 for (i = lle->ll_count - 1; i >= 0; i--) {
 897                         lock1 = &lle->ll_children[i];
 898                         if (lock1->li_lock == lock ||
 899                             lock1->li_lock == &Giant.mtx_object)
 900                                 continue;
 901                         if ((lock1->li_lock->lo_flags & LO_SLEEPABLE) != 0) {
 902                                 if (check_only == 0) {
 903                                         CTR3(KTR_WITNESS,
 904                                     "pid %d: sleeping with lock (%s) %s held",
 905                                             td->td_proc->p_pid,
 906                                             lock1->li_lock->lo_class->lc_name,
 907                                             lock1->li_lock->lo_name);
 908                                         lock1->li_flags |= LI_SLEPT;
 909                                 }
 910                                 continue;
 911                         }
 912                         n++;
 913                         printf("%s:%d: %s with \"%s\" locked from %s:%d\n",
 914                             file, line, check_only ? "could sleep" : "sleeping",
 915                             lock1->li_lock->lo_name, lock1->li_file,
 916                             lock1->li_line);
 917                 }
 918         if (lock_list == &td->td_sleeplocks) {
 919                 lock_list = PCPU_PTR(spinlocks);
 920                 goto again;
 921         }
 922 #ifdef DDB
 923         if (witness_ddb && n)
 924                 Debugger(__func__);
 925 #endif /* DDB */
 926         critical_exit();
 927         return (n);
 928 }
 929
 930 static struct witness *
 931 enroll(const char *description, struct lock_class *lock_class)
 932 {
 933         struct witness *w;
 934
 935         if (!witness_watch || witness_dead || panicstr != NULL)
 936                 return (NULL);
 937         if ((lock_class->lc_flags & LC_SPINLOCK) && witness_skipspin)
 938                 return (NULL);
 939         mtx_lock_spin(&w_mtx);
 940         STAILQ_FOREACH(w, &w_all, w_list) {
 941                 if (strcmp(description, w->w_name) == 0) {
 942                         w->w_refcount++;
 943                         mtx_unlock_spin(&w_mtx);
 944                         if (lock_class != w->w_class)
 945                                 panic(
 946                                 "lock (%s) %s does not match earlier (%s) lock",
 947                                     description, lock_class->lc_name,
 948                                     w->w_class->lc_name);
 949                         return (w);
 950                 }
 951         }
 952         /*
 953          * This isn't quite right, as witness_cold is still 0 while we
 954          * enroll all the locks initialized before witness_initialize().
 955          */
 956         if ((lock_class->lc_flags & LC_SPINLOCK) && !witness_cold) {
 957                 mtx_unlock_spin(&w_mtx);
 958                 panic("spin lock %s not in order list", description);
 959         }
 960         if ((w = witness_get()) == NULL)
 961                 return (NULL);
 962         w->w_name = description;
 963         w->w_class = lock_class;
 964         w->w_refcount = 1;
 965         STAILQ_INSERT_HEAD(&w_all, w, w_list);
 966         if (lock_class->lc_flags & LC_SPINLOCK)
 967                 STAILQ_INSERT_HEAD(&w_spin, w, w_typelist);
 968         else if (lock_class->lc_flags & LC_SLEEPLOCK)
 969                 STAILQ_INSERT_HEAD(&w_sleep, w, w_typelist);
 970         else {
 971                 mtx_unlock_spin(&w_mtx);
 972                 panic("lock class %s is not sleep or spin",
 973                     lock_class->lc_name);
 974         }
 975         mtx_unlock_spin(&w_mtx);
 976         return (w);
 977 }
 978
 979 static int
 980 itismychild(struct witness *parent, struct witness *child)
 981 {
 982         static int recursed;
 983         struct witness_child_list_entry **wcl;
 984         struct witness_list *list;
 985
 986         MPASS(child != NULL && parent != NULL);
 987         if ((parent->w_class->lc_flags & (LC_SLEEPLOCK | LC_SPINLOCK)) !=
 988             (child->w_class->lc_flags & (LC_SLEEPLOCK | LC_SPINLOCK)))
 989                 panic(
 990                 "%s: parent (%s) and child (%s) are not the same lock type",
 991                     __func__, parent->w_class->lc_name,
 992                     child->w_class->lc_name);
 993
 994         /*
 995          * Insert "child" after "parent"
 996          */
 997         wcl = &parent->w_children;
 998         while (*wcl != NULL && (*wcl)->wcl_count == WITNESS_NCHILDREN)
 999                 wcl = &(*wcl)->wcl_next;
1000         if (*wcl == NULL) {
1001                 *wcl = witness_child_get();
1002                 if (*wcl == NULL)
1003                         return (1);
1004         }
1005         (*wcl)->wcl_children[(*wcl)->wcl_count++] = child;
1006
1007         /*
1008          * Now prune whole tree.  We look for cases where a lock is now
1009          * both a descendant and a direct child of a given lock.  In that
1010          * case, we want to remove the direct child link from the tree.
1011          */
1012         if (recursed)
1013                 return (0);
1014         recursed = 1;
1015         if (parent->w_class->lc_flags & LC_SLEEPLOCK)
1016                 list = &w_sleep;
1017         else
1018                 list = &w_spin;
1019         STAILQ_FOREACH(child, list, w_typelist) {
1020                 STAILQ_FOREACH(parent, list, w_typelist) {
1021                         if (!isitmychild(parent, child))
1022                                 continue;
1023                         removechild(parent, child);
1024                         if (isitmydescendant(parent, child))
1025                                 continue;
1026                         itismychild(parent, child);
1027                 }
1028         }
1029         recursed = 0;
1030         witness_levelall();
1031         return (0);
1032 }
1033
1034 static void
1035 removechild(struct witness *parent, struct witness *child)
1036 {
1037         struct witness_child_list_entry **wcl, *wcl1;
1038         int i;
1039
1040         for (wcl = &parent->w_children; *wcl != NULL; wcl = &(*wcl)->wcl_next)
1041                 for (i = 0; i < (*wcl)->wcl_count; i++)
1042                         if ((*wcl)->wcl_children[i] == child)
1043                                 goto found;
1044         return;
1045 found:
1046         (*wcl)->wcl_count--;
1047         if ((*wcl)->wcl_count > i)
1048                 (*wcl)->wcl_children[i] =
1049                     (*wcl)->wcl_children[(*wcl)->wcl_count];
1050         MPASS((*wcl)->wcl_children[i] != NULL);
1051         if ((*wcl)->wcl_count != 0)
1052                 return;
1053         wcl1 = *wcl;
1054         *wcl = wcl1->wcl_next;
1055         witness_child_free(wcl1);
1056 }
1057
1058 static int
1059 isitmychild(struct witness *parent, struct witness *child)
1060 {
1061         struct witness_child_list_entry *wcl;
1062         int i;
1063
1064         for (wcl = parent->w_children; wcl != NULL; wcl = wcl->wcl_next) {
1065                 for (i = 0; i < wcl->wcl_count; i++) {
1066                         if (wcl->wcl_children[i] == child)
1067                                 return (1);
1068                 }
1069         }
1070         return (0);
1071 }
1072
1073 static int
1074 isitmydescendant(struct witness *parent, struct witness *child)
1075 {
1076         struct witness_child_list_entry *wcl;
1077         int i, j;
1078
1079         if (isitmychild(parent, child))
1080                 return (1);
1081         j = 0;
1082         for (wcl = parent->w_children; wcl != NULL; wcl = wcl->wcl_next) {
1083                 MPASS(j < 1000);
1084                 for (i = 0; i < wcl->wcl_count; i++) {
1085                         if (isitmydescendant(wcl->wcl_children[i], child))
1086                                 return (1);
1087                 }
1088                 j++;
1089         }
1090         return (0);
1091 }
1092
1093 void
1094 witness_levelall (void)
1095 {
1096         struct witness_list *list;
1097         struct witness *w, *w1;
1098
1099         /*
1100          * First clear all levels.
1101          */
1102         STAILQ_FOREACH(w, &w_all, w_list) {
1103                 w->w_level = 0;
1104         }
1105
1106         /*
1107          * Look for locks with no parent and level all their descendants.
1108          */
1109         STAILQ_FOREACH(w, &w_all, w_list) {
1110                 /*
1111                  * This is just an optimization, technically we could get
1112                  * away just walking the all list each time.
1113                  */
1114                 if (w->w_class->lc_flags & LC_SLEEPLOCK)
1115                         list = &w_sleep;
1116                 else
1117                         list = &w_spin;
1118                 STAILQ_FOREACH(w1, list, w_typelist) {
1119                         if (isitmychild(w1, w))
1120                                 goto skip;
1121                 }
1122                 witness_leveldescendents(w, 0);
1123         skip:
1124                 ;       /* silence GCC 3.x */
1125         }
1126 }
1127
1128 static void
1129 witness_leveldescendents(struct witness *parent, int level)
1130 {
1131         struct witness_child_list_entry *wcl;
1132         int i;
1133
1134         if (parent->w_level < level)
1135                 parent->w_level = level;
1136         level++;
1137         for (wcl = parent->w_children; wcl != NULL; wcl = wcl->wcl_next)
1138                 for (i = 0; i < wcl->wcl_count; i++)
1139                         witness_leveldescendents(wcl->wcl_children[i], level);
1140 }
1141
1142 static void
1143 witness_displaydescendants(void(*prnt)(const char *fmt, ...),
1144                            struct witness *parent)
1145 {
1146         struct witness_child_list_entry *wcl;
1147         int i, level;
1148
1149         level = parent->w_level;
1150         prnt("%-2d", level);
1151         for (i = 0; i < level; i++)
1152                 prnt(" ");
1153         prnt("%s", parent->w_name);
1154         if (parent->w_file != NULL)
1155                 prnt(" -- last acquired @ %s:%d\n", parent->w_file,
1156                     parent->w_line);
1157         for (wcl = parent->w_children; wcl != NULL; wcl = wcl->wcl_next)
1158                 for (i = 0; i < wcl->wcl_count; i++)
1159                             witness_displaydescendants(prnt,
1160                                 wcl->wcl_children[i]);
1161 }
1162
1163 static int
1164 blessed(struct witness *w1, struct witness *w2)
1165 {
1166         int i;
1167         struct witness_blessed *b;
1168
1169         for (i = 0; i < blessed_count; i++) {
1170                 b = &blessed_list[i];
1171                 if (strcmp(w1->w_name, b->b_lock1) == 0) {
1172                         if (strcmp(w2->w_name, b->b_lock2) == 0)
1173                                 return (1);
1174                         continue;
1175                 }
1176                 if (strcmp(w1->w_name, b->b_lock2) == 0)
1177                         if (strcmp(w2->w_name, b->b_lock1) == 0)
1178                                 return (1);
1179         }
1180         return (0);
1181 }
1182
1183 static struct witness *
1184 witness_get(void)
1185 {
1186         struct witness *w;
1187
1188         if (witness_dead) {
1189                 mtx_unlock_spin(&w_mtx);
1190                 return (NULL);
1191         }
1192         if (STAILQ_EMPTY(&w_free)) {
1193                 witness_dead = 1;
1194                 mtx_unlock_spin(&w_mtx);
1195                 printf("%s: witness exhausted\n", __func__);
1196                 return (NULL);
1197         }
1198         w = STAILQ_FIRST(&w_free);
1199         STAILQ_REMOVE_HEAD(&w_free, w_list);
1200         bzero(w, sizeof(*w));
1201         return (w);
1202 }
1203
1204 static void
1205 witness_free(struct witness *w)
1206 {
1207
1208         STAILQ_INSERT_HEAD(&w_free, w, w_list);
1209 }
1210
1211 static struct witness_child_list_entry *
1212 witness_child_get(void)
1213 {
1214         struct witness_child_list_entry *wcl;
1215
1216         if (witness_dead) {
1217                 mtx_unlock_spin(&w_mtx);
1218                 return (NULL);
1219         }
1220         wcl = w_child_free;
1221         if (wcl == NULL) {
1222                 witness_dead = 1;
1223                 mtx_unlock_spin(&w_mtx);
1224                 printf("%s: witness exhausted\n", __func__);
1225                 return (NULL);
1226         }
1227         w_child_free = wcl->wcl_next;
1228         bzero(wcl, sizeof(*wcl));
1229         return (wcl);
1230 }
1231
1232 static void
1233 witness_child_free(struct witness_child_list_entry *wcl)
1234 {
1235
1236         wcl->wcl_next = w_child_free;
1237         w_child_free = wcl;
1238 }
1239
1240 static struct lock_list_entry *
1241 witness_lock_list_get(void)
1242 {
1243         struct lock_list_entry *lle;
1244
1245         if (witness_dead)
1246                 return (NULL);
1247         mtx_lock_spin(&w_mtx);
1248         lle = w_lock_list_free;
1249         if (lle == NULL) {
1250                 witness_dead = 1;
1251                 mtx_unlock_spin(&w_mtx);
1252                 printf("%s: witness exhausted\n", __func__);
1253                 return (NULL);
1254         }
1255         w_lock_list_free = lle->ll_next;
1256         mtx_unlock_spin(&w_mtx);
1257         bzero(lle, sizeof(*lle));
1258         return (lle);
1259 }
1260
1261 static void
1262 witness_lock_list_free(struct lock_list_entry *lle)
1263 {
1264
1265         mtx_lock_spin(&w_mtx);
1266         lle->ll_next = w_lock_list_free;
1267         w_lock_list_free = lle;
1268         mtx_unlock_spin(&w_mtx);
1269 }
1270
1271 static struct lock_instance *
1272 find_instance(struct lock_list_entry *lock_list, struct lock_object *lock)
1273 {
1274         struct lock_list_entry *lle;
1275         struct lock_instance *instance;
1276         int i;
1277
1278         for (lle = lock_list; lle != NULL; lle = lle->ll_next)
1279                 for (i = lle->ll_count - 1; i >= 0; i--) {
1280                         instance = &lle->ll_children[i];
1281                         if (instance->li_lock == lock)
1282                                 return (instance);
1283                 }
1284         return (NULL);
1285 }
1286
1287 int
1288 witness_list_locks(struct lock_list_entry **lock_list)
1289 {
1290         struct lock_list_entry *lle;
1291         struct lock_instance *instance;
1292         struct lock_object *lock;
1293         int i, nheld;
1294
1295         nheld = 0;
1296         for (lle = *lock_list; lle != NULL; lle = lle->ll_next)
1297                 for (i = lle->ll_count - 1; i >= 0; i--) {
1298                         instance = &lle->ll_children[i];
1299                         lock = instance->li_lock;
1300                         printf("%s %s %s",
1301                             (instance->li_flags & LI_EXCLUSIVE) != 0 ?
1302                             "exclusive" : "shared",
1303                             lock->lo_class->lc_name, lock->lo_name);
1304                         if (lock->lo_type != lock->lo_name)
1305                                 printf(" (%s)", lock->lo_type);
1306                         printf(" r = %d (%p) locked @ %s:%d\n",
1307                             instance->li_flags & LI_RECURSEMASK, lock,
1308                             instance->li_file, instance->li_line);
1309                         nheld++;
1310                 }
1311         return (nheld);
1312 }
1313
1314 /*
1315  * Calling this on td != curthread is bad unless we are in ddb.
1316  */
1317 int
1318 witness_list(struct thread *td)
1319 {
1320         int nheld;
1321
1322         KASSERT(!witness_cold, ("%s: witness_cold", __func__));
1323 #ifdef DDB
1324         KASSERT(td == curthread || db_active,
1325             ("%s: td != curthread and we aren't in the debugger", __func__));
1326         if (!db_active && witness_dead)
1327                 return (0);
1328 #else
1329         KASSERT(td == curthread, ("%s: p != curthread", __func__));
1330         if (witness_dead)
1331                 return (0);
1332 #endif
1333         nheld = witness_list_locks(&td->td_sleeplocks);
1334
1335         /*
1336          * We only handle spinlocks if td == curthread.  This is somewhat broken
1337          * if td is currently executing on some other CPU and holds spin locks
1338          * as we won't display those locks.  If we had a MI way of getting
1339          * the per-cpu data for a given cpu then we could use
1340          * td->td_kse->ke_oncpu to get the list of spinlocks for this thread
1341          * and "fix" this.
1342          *
1343          * That still wouldn't really fix this unless we locked sched_lock
1344          * or stopped the other CPU to make sure it wasn't changing the list
1345          * out from under us.  It is probably best to just not try to handle
1346          * threads on other CPU's for now.
1347          */
1348         if (td == curthread) {
1349                 /*
1350                  * Preemption bad because we need PCPU_PTR(spinlocks) to not
1351                  * change.
1352                  */
1353                 critical_enter();
1354                 nheld += witness_list_locks(PCPU_PTR(spinlocks));
1355                 critical_exit();
1356         }
1357         return (nheld);
1358 }
1359
1360 void
1361 witness_save(struct lock_object *lock, const char **filep, int *linep)
1362 {
1363         struct lock_instance *instance;
1364
1365         KASSERT(!witness_cold, ("%s: witness_cold", __func__));
1366         if (lock->lo_witness == NULL || witness_dead || panicstr != NULL)
1367                 return;
1368         if ((lock->lo_class->lc_flags & LC_SLEEPLOCK) == 0)
1369                 panic("%s: lock (%s) %s is not a sleep lock", __func__,
1370                     lock->lo_class->lc_name, lock->lo_name);
1371         instance = find_instance(curthread->td_sleeplocks, lock);
1372         if (instance == NULL)
1373                 panic("%s: lock (%s) %s not locked", __func__,
1374                     lock->lo_class->lc_name, lock->lo_name);
1375         *filep = instance->li_file;
1376         *linep = instance->li_line;
1377 }
1378
1379 void
1380 witness_restore(struct lock_object *lock, const char *file, int line)
1381 {
1382         struct lock_instance *instance;
1383
1384         KASSERT(!witness_cold, ("%s: witness_cold", __func__));
1385         if (lock->lo_witness == NULL || witness_dead || panicstr != NULL)
1386                 return;
1387         if ((lock->lo_class->lc_flags & LC_SLEEPLOCK) == 0)
1388                 panic("%s: lock (%s) %s is not a sleep lock", __func__,
1389                     lock->lo_class->lc_name, lock->lo_name);
1390         instance = find_instance(curthread->td_sleeplocks, lock);
1391         if (instance == NULL)
1392                 panic("%s: lock (%s) %s not locked", __func__,
1393                     lock->lo_class->lc_name, lock->lo_name);
1394         lock->lo_witness->w_file = file;
1395         lock->lo_witness->w_line = line;
1396         instance->li_file = file;
1397         instance->li_line = line;
1398 }
1399
1400 void
1401 witness_assert(struct lock_object *lock, int flags, const char *file, int line)
1402 {
1403 #ifdef INVARIANT_SUPPORT
1404         struct lock_instance *instance;
1405
1406         if (lock->lo_witness == NULL || witness_dead || panicstr != NULL)
1407                 return;
1408         if ((lock->lo_class->lc_flags & LC_SLEEPLOCK) != 0)
1409                 instance = find_instance(curthread->td_sleeplocks, lock);
1410         else if ((lock->lo_class->lc_flags & LC_SPINLOCK) != 0)
1411                 instance = find_instance(PCPU_GET(spinlocks), lock);
1412         else {
1413                 panic("Lock (%s) %s is not sleep or spin!",
1414                     lock->lo_class->lc_name, lock->lo_name);
1415                 return;
1416         }
1417         switch (flags) {
1418         case LA_UNLOCKED:
1419                 if (instance != NULL)
1420                         panic("Lock (%s) %s locked @ %s:%d.",
1421                             lock->lo_class->lc_name, lock->lo_name, file, line);
1422                 break;
1423         case LA_LOCKED:
1424         case LA_LOCKED | LA_RECURSED:
1425         case LA_LOCKED | LA_NOTRECURSED:
1426         case LA_SLOCKED:
1427         case LA_SLOCKED | LA_RECURSED:
1428         case LA_SLOCKED | LA_NOTRECURSED:
1429         case LA_XLOCKED:
1430         case LA_XLOCKED | LA_RECURSED:
1431         case LA_XLOCKED | LA_NOTRECURSED:
1432                 if (instance == NULL) {
1433                         panic("Lock (%s) %s not locked @ %s:%d.",
1434                             lock->lo_class->lc_name, lock->lo_name, file, line);
1435                         break;
1436                 }
1437                 if ((flags & LA_XLOCKED) != 0 &&
1438                     (instance->li_flags & LI_EXCLUSIVE) == 0)
1439                         panic("Lock (%s) %s not exclusively locked @ %s:%d.",
1440                             lock->lo_class->lc_name, lock->lo_name, file, line);
1441                 if ((flags & LA_SLOCKED) != 0 &&
1442                     (instance->li_flags & LI_EXCLUSIVE) != 0)
1443                         panic("Lock (%s) %s exclusively locked @ %s:%d.",
1444                             lock->lo_class->lc_name, lock->lo_name, file, line);
1445                 if ((flags & LA_RECURSED) != 0 &&
1446                     (instance->li_flags & LI_RECURSEMASK) == 0)
1447                         panic("Lock (%s) %s not recursed @ %s:%d.",
1448                             lock->lo_class->lc_name, lock->lo_name, file, line);
1449                 if ((flags & LA_NOTRECURSED) != 0 &&
1450                     (instance->li_flags & LI_RECURSEMASK) != 0)
1451                         panic("Lock (%s) %s recursed @ %s:%d.",
1452                             lock->lo_class->lc_name, lock->lo_name, file, line);
1453                 break;
1454         default:
1455                 panic("Invalid lock assertion at %s:%d.", file, line);
1456
1457         }
1458 #endif  /* INVARIANT_SUPPORT */
1459 }
1460
1461 #ifdef DDB
1462
1463 DB_SHOW_COMMAND(locks, db_witness_list)
1464 {
1465         struct thread *td;
1466         pid_t pid;
1467         struct proc *p;
1468
1469         if (have_addr) {
1470                 pid = (addr % 16) + ((addr >> 4) % 16) * 10 +
1471                     ((addr >> 8) % 16) * 100 + ((addr >> 12) % 16) * 1000 +
1472                     ((addr >> 16) % 16) * 10000;
1473                 /* sx_slock(&allproc_lock); */
1474                 FOREACH_PROC_IN_SYSTEM(p) {
1475                         if (p->p_pid == pid)
1476                                 break;
1477                 }
1478                 /* sx_sunlock(&allproc_lock); */
1479                 if (p == NULL) {
1480                         db_printf("pid %d not found\n", pid);
1481                         return;
1482                 }
1483                 FOREACH_THREAD_IN_PROC(p, td) {
1484                         witness_list(td);
1485                 }
1486         } else {
1487                 td = curthread;
1488                 witness_list(td);
1489         }
1490 }
1491
1492 DB_SHOW_COMMAND(witness, db_witness_display)
1493 {
1494
1495         witness_display(db_printf);
1496 }
1497 #endif