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