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