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. --- 13 unchanged lines hidden (view full) --- 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: head/sys/kern/subr_witness.c 74912 2001-03-28 09:03:24Z jhb $ |
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 --- 12 unchanged lines hidden (view full) --- 57 */ 58 59#include "opt_ddb.h" 60#include "opt_witness.h" 61 62#include <sys/param.h> 63#include <sys/bus.h> 64#include <sys/kernel.h> |
65#include <sys/ktr.h> 66#include <sys/lock.h> |
67#include <sys/malloc.h> |
68#include <sys/mutex.h> |
69#include <sys/proc.h> 70#include <sys/sysctl.h> 71#include <sys/systm.h> |
72 |
73#include <ddb/ddb.h> 74 |
75#define WITNESS_COUNT 200 76#define WITNESS_CHILDCOUNT (WITNESS_COUNT * 4) |
77/* |
78 * XXX: This is somewhat bogus, as we assume here that at most 1024 processes 79 * will hold LOCK_NCHILDREN * 2 locks. We handle failure ok, and we should 80 * probably be safe for the most part, but it's still a SWAG. |
81 */ |
82#define LOCK_CHILDCOUNT (MAXCPU + 1024) * 2 |
83 |
84#define WITNESS_NCHILDREN 6 |
85 |
86struct witness_child_list_entry; |
87 |
88struct witness { 89 const char *w_name; 90 struct lock_class *w_class; 91 STAILQ_ENTRY(witness) w_list; /* List of all witnesses. */ 92 STAILQ_ENTRY(witness) w_typelist; /* Witnesses of a type. */ 93 struct witness_child_list_entry *w_children; /* Great evilness... */ 94 const char *w_file; 95 int w_line; 96 u_int w_level; 97 u_int w_refcount; 98 u_char w_Giant_squawked:1; 99 u_char w_other_squawked:1; 100 u_char w_same_squawked:1; 101}; |
102 |
103struct witness_child_list_entry { 104 struct witness_child_list_entry *wcl_next; 105 struct witness *wcl_children[WITNESS_NCHILDREN]; 106 u_int wcl_count; 107}; |
108 |
109STAILQ_HEAD(witness_list, witness); |
110 |
111struct witness_blessed { 112 const char *b_lock1; 113 const char *b_lock2; 114}; |
115 |
116struct witness_order_list_entry { 117 const char *w_name; 118 struct lock_class *w_class; 119}; |
120 |
121static struct witness *enroll(const char *description, 122 struct lock_class *lock_class); 123static int itismychild(struct witness *parent, struct witness *child); 124static void removechild(struct witness *parent, struct witness *child); 125static int isitmychild(struct witness *parent, struct witness *child); 126static int isitmydescendant(struct witness *parent, struct witness *child); 127static int dup_ok(struct witness *); 128static int blessed(struct witness *, struct witness *); 129static void witness_display_list(void(*prnt)(const char *fmt, ...), 130 struct witness_list *list); 131static void witness_displaydescendants(void(*)(const char *fmt, ...), 132 struct witness *); 133static void witness_leveldescendents(struct witness *parent, int level); 134static void witness_levelall(void); 135static struct witness *witness_get(void); 136static void witness_free(struct witness *m); 137static struct witness_child_list_entry *witness_child_get(void); 138static void witness_child_free(struct witness_child_list_entry *wcl); 139static struct lock_list_entry *witness_lock_list_get(void); 140static void witness_lock_list_free(struct lock_list_entry *lle); 141static void witness_display(void(*)(const char *fmt, ...)); |
142 |
143MALLOC_DEFINE(M_WITNESS, "witness", "witness structure"); |
144 |
145static int witness_watch; 146TUNABLE_INT_DECL("debug.witness_watch", 1, witness_watch); 147SYSCTL_INT(_debug, OID_AUTO, witness_watch, CTLFLAG_RD, &witness_watch, 0, ""); |
148 |
149#ifdef DDB |
150/* |
151 * When DDB is enabled and witness_ddb is set to 1, it will cause the system to 152 * drop into kdebug() when: 153 * - a lock heirarchy violation occurs 154 * - locks are held when going to sleep. 155 */ 156int witness_ddb; 157#ifdef WITNESS_DDB 158TUNABLE_INT_DECL("debug.witness_ddb", 1, witness_ddb); --- 7 unchanged lines hidden (view full) --- 166#ifdef WITNESS_SKIPSPIN 167TUNABLE_INT_DECL("debug.witness_skipspin", 1, witness_skipspin); 168#else 169TUNABLE_INT_DECL("debug.witness_skipspin", 0, witness_skipspin); 170#endif 171SYSCTL_INT(_debug, OID_AUTO, witness_skipspin, CTLFLAG_RD, &witness_skipspin, 0, 172 ""); 173 |
174static struct mtx w_mtx; 175static struct witness_list w_free = STAILQ_HEAD_INITIALIZER(w_free); 176static struct witness_list w_all = STAILQ_HEAD_INITIALIZER(w_all); 177static struct witness_list w_spin = STAILQ_HEAD_INITIALIZER(w_spin); 178static struct witness_list w_sleep = STAILQ_HEAD_INITIALIZER(w_sleep); 179static struct witness_child_list_entry *w_child_free = NULL; 180static struct lock_list_entry *w_lock_list_free = NULL; 181static int witness_dead; /* fatal error, probably no memory */ |
182 |
183static struct witness w_data[WITNESS_COUNT]; 184static struct witness_child_list_entry w_childdata[WITNESS_CHILDCOUNT]; 185static struct lock_list_entry w_locklistdata[LOCK_CHILDCOUNT]; |
186 |
187static struct witness_order_list_entry order_lists[] = { 188 { "Giant", &lock_class_mtx_sleep }, 189 { "proctree", &lock_class_sx }, 190 { "allproc", &lock_class_sx }, 191 { "process lock", &lock_class_mtx_sleep }, 192 { "uidinfo hash", &lock_class_mtx_sleep }, 193 { "uidinfo struct", &lock_class_mtx_sleep }, 194 { NULL, NULL }, |
195#if defined(__i386__) && defined (SMP) |
196 { "com", &lock_class_mtx_spin }, |
197#endif |
198 { "sio", &lock_class_mtx_spin }, |
199#ifdef __i386__ |
200 { "cy", &lock_class_mtx_spin }, |
201#endif |
202 { "ng_node", &lock_class_mtx_spin }, 203 { "ng_worklist", &lock_class_mtx_spin }, 204 { "ithread table lock", &lock_class_mtx_spin }, 205 { "ithread list lock", &lock_class_mtx_spin }, 206 { "sched lock", &lock_class_mtx_spin }, |
207#ifdef __i386__ |
208 { "clk", &lock_class_mtx_spin }, |
209#endif |
210 { "callout", &lock_class_mtx_spin }, |
211 /* 212 * leaf locks 213 */ 214#ifdef SMP 215#ifdef __i386__ |
216 { "ap boot", &lock_class_mtx_spin }, 217 { "imen", &lock_class_mtx_spin }, |
218#endif |
219 { "smp rendezvous", &lock_class_mtx_spin }, |
220#endif |
221 { NULL, NULL }, 222 { NULL, NULL } |
223}; 224 |
225static const char *dup_list[] = { |
226 "process lock", 227 NULL 228}; 229 |
230/* 231 * Pairs of locks which have been blessed 232 * Don't complain about order problems with blessed locks 233 */ 234static struct witness_blessed blessed_list[] = { 235}; 236static int blessed_count = 237 sizeof(blessed_list) / sizeof(struct witness_blessed); 238 |
239/* 240 * List of all locks in the system. 241 */ 242STAILQ_HEAD(, lock_object) all_locks = STAILQ_HEAD_INITIALIZER(all_locks); |
243 |
244static struct mtx all_mtx = { 245 { &lock_class_mtx_sleep, /* mtx_object.lo_class */ 246 "All locks list", /* mtx_object.lo_name */ 247 NULL, /* mtx_object.lo_file */ 248 0, /* mtx_object.lo_line */ 249 LO_INITIALIZED, /* mtx_object.lo_flags */ 250 { NULL }, /* mtx_object.lo_list */ 251 NULL }, /* mtx_object.lo_witness */ 252 MTX_UNOWNED, 0, /* mtx_lock, mtx_recurse */ 253 0, /* mtx_savecrit */ 254 TAILQ_HEAD_INITIALIZER(all_mtx.mtx_blocked), 255 { NULL, NULL } /* mtx_contested */ 256}; 257 258/* 259 * This global is set to 0 once it becomes safe to use the witness code. 260 */ 261static int witness_cold = 1; 262 263/* 264 * Global variables for book keeping. 265 */ 266static int lock_cur_cnt; 267static int lock_max_cnt; 268 269/* 270 * The WITNESS-enabled diagnostic code. 271 */ |
272static void |
273witness_initialize(void *dummy __unused) |
274{ |
275 struct lock_object *lock; 276 struct witness_order_list_entry *order; 277 struct witness *w, *w1; 278 int i; 279 280 /* 281 * We have to release Giant before initializing its witness 282 * structure so that WITNESS doesn't get confused. 283 */ 284 mtx_unlock(&Giant); 285 mtx_assert(&Giant, MA_NOTOWNED); 286 287 STAILQ_INSERT_HEAD(&all_locks, &all_mtx.mtx_object, lo_list); 288 mtx_init(&w_mtx, "witness lock", MTX_SPIN | MTX_QUIET | MTX_NOWITNESS); 289 for (i = 0; i < WITNESS_COUNT; i++) 290 witness_free(&w_data[i]); 291 for (i = 0; i < WITNESS_CHILDCOUNT; i++) 292 witness_child_free(&w_childdata[i]); 293 for (i = 0; i < LOCK_CHILDCOUNT; i++) 294 witness_lock_list_free(&w_locklistdata[i]); 295 296 /* First add in all the specified order lists. */ 297 for (order = order_lists; order->w_name != NULL; order++) { 298 w = enroll(order->w_name, order->w_class); 299 w->w_file = "order list"; 300 for (order++; order->w_name != NULL; order++) { 301 w1 = enroll(order->w_name, order->w_class); 302 w1->w_file = "order list"; 303 itismychild(w, w1); 304 w = w1; |
305 } 306 } |
307 |
308 /* Iterate through all locks and add them to witness. */ 309 mtx_lock(&all_mtx); 310 STAILQ_FOREACH(lock, &all_locks, lo_list) { 311 if (lock->lo_flags & LO_WITNESS) 312 lock->lo_witness = enroll(lock->lo_name, 313 lock->lo_class); 314 else 315 lock->lo_witness = NULL; 316 } 317 mtx_unlock(&all_mtx); 318 319 /* Mark the witness code as being ready for use. */ 320 atomic_store_rel_int(&witness_cold, 0); 321 322 mtx_lock(&Giant); |
323} |
324SYSINIT(witness_init, SI_SUB_WITNESS, SI_ORDER_FIRST, witness_initialize, NULL) |
325 |
326void 327witness_init(struct lock_object *lock) 328{ 329 struct lock_class *class; 330 331 class = lock->lo_class; 332 if (lock->lo_flags & LO_INITIALIZED) 333 panic("%s: lock (%s) %s is already initialized!\n", __func__, 334 class->lc_name, lock->lo_name); 335 336 if ((lock->lo_flags & LO_RECURSABLE) != 0 && 337 (class->lc_flags & LC_RECURSABLE) == 0) 338 panic("%s: lock (%s) %s can not be recursable!\n", __func__, 339 class->lc_name, lock->lo_name); 340 341 if ((lock->lo_flags & LO_SLEEPABLE) != 0 && 342 (class->lc_flags & LC_SLEEPABLE) == 0) 343 panic("%s: lock (%s) %s can not be sleepable!\n", __func__, 344 class->lc_name, lock->lo_name); 345 346 mtx_lock(&all_mtx); 347 STAILQ_INSERT_TAIL(&all_locks, lock, lo_list); 348 lock->lo_flags |= LO_INITIALIZED; 349 lock_cur_cnt++; 350 if (lock_cur_cnt > lock_max_cnt) 351 lock_max_cnt = lock_cur_cnt; 352 mtx_unlock(&all_mtx); 353 if (!witness_cold && !witness_dead && 354 (lock->lo_flags & LO_WITNESS) != 0) 355 lock->lo_witness = enroll(lock->lo_name, class); 356 else 357 lock->lo_witness = NULL; 358} 359 360void 361witness_destroy(struct lock_object *lock) 362{ 363 364 if (witness_cold) 365 panic("lock (%s) %s destroyed while witness_cold", 366 lock->lo_class->lc_name, lock->lo_name); 367 368 if ((lock->lo_flags & LO_INITIALIZED) == 0) 369 panic("%s: lock (%s) %s is not initialized!\n", __func__, 370 lock->lo_class->lc_name, lock->lo_name); 371 372 if (lock->lo_flags & LO_LOCKED) 373 panic("lock (%s) %s destroyed while held", 374 lock->lo_class->lc_name, lock->lo_name); 375 376 mtx_lock(&all_mtx); 377 lock_cur_cnt--; 378 STAILQ_REMOVE(&all_locks, lock, lock_object, lo_list); 379 lock->lo_flags &= LO_INITIALIZED; 380 mtx_unlock(&all_mtx); 381} 382 |
383static void |
384witness_display_list(void(*prnt)(const char *fmt, ...), 385 struct witness_list *list) |
386{ 387 struct witness *w, *w1; |
388 int found; |
389 |
390 STAILQ_FOREACH(w, list, w_typelist) { 391 if (w->w_file == NULL) |
392 continue; |
393 found = 0; 394 STAILQ_FOREACH(w1, list, w_typelist) { 395 if (isitmychild(w1, w)) { 396 found++; |
397 break; |
398 } |
399 } |
400 if (found) |
401 continue; 402 /* 403 * This lock has no anscestors, display its descendants. 404 */ 405 witness_displaydescendants(prnt, w); 406 } |
407} |
408 |
409static void 410witness_display(void(*prnt)(const char *fmt, ...)) 411{ 412 struct witness *w; 413 414 KASSERT(!witness_cold, ("%s: witness_cold\n", __func__)); 415 witness_levelall(); 416 |
417 /* |
418 * First, handle sleep mutexes which have been acquired at least 419 * once. 420 */ 421 prnt("Sleep locks:\n"); 422 witness_display_list(prnt, &w_sleep); 423 424 /* |
425 * Now do spin mutexes which have been acquired at least once. 426 */ |
427 prnt("\nSpin locks:\n"); 428 witness_display_list(prnt, &w_spin); |
429 430 /* 431 * Finally, any mutexes which have not been acquired yet. 432 */ |
433 prnt("\nLocks which were never acquired:\n"); 434 STAILQ_FOREACH(w, &w_all, w_list) { |
435 if (w->w_file != NULL) 436 continue; |
437 prnt("%s\n", w->w_name); |
438 } 439} 440 441void |
442witness_lock(struct lock_object *lock, int flags, const char *file, int line) |
443{ |
444 struct lock_list_entry **lock_list, *lle; 445 struct lock_object *lock1, *lock2; 446 struct lock_class *class; |
447 struct witness *w, *w1; |
448 struct proc *p; |
449 int i, j; |
450#ifdef DDB 451 int go_into_ddb = 0; 452#endif /* DDB */ 453 |
454 if (witness_cold || witness_dead || lock->lo_witness == NULL || 455 panicstr) |
456 return; |
457 w = lock->lo_witness; 458 class = lock->lo_class; |
459 p = curproc; 460 |
461 if ((lock->lo_flags & LO_LOCKED) == 0) 462 panic("%s: lock (%s) %s is not locked @ %s:%d", __func__, 463 class->lc_name, lock->lo_name, file, line); |
464 |
465 if ((lock->lo_flags & LO_RECURSED) != 0) { 466 if ((lock->lo_flags & LO_RECURSABLE) == 0) 467 panic( 468 "%s: recursed on non-recursive lock (%s) %s @ %s:%d", 469 __func__, class->lc_name, lock->lo_name, file, 470 line); |
471 return; 472 } |
473 474 lock_list = PCPU_PTR(spinlocks); 475 if (class->lc_flags & LC_SLEEPLOCK) { 476 if (*lock_list != NULL) 477 panic("blockable sleep lock (%s) %s @ %s:%d", 478 class->lc_name, lock->lo_name, file, line); 479 lock_list = &p->p_sleeplocks; 480 } 481 482 if (flags & LOP_TRYLOCK) |
483 goto out; |
484 |
485 /* |
486 * Is this the first lock acquired? If so, then no order checking 487 * is needed. |
488 */ |
489 if (*lock_list == NULL) |
490 goto out; 491 |
492 /* 493 * Check for duplicate locks of the same type. Note that we only 494 * have to check for this on the last lock we just acquired. Any 495 * other cases will be caught as lock order violations. 496 */ 497 lock1 = (*lock_list)->ll_children[(*lock_list)->ll_count - 1]; 498 w1 = lock1->lo_witness; 499 if (w1 == w) { |
500 if (w->w_same_squawked || dup_ok(w)) 501 goto out; 502 w->w_same_squawked = 1; 503 printf("acquring duplicate lock of same type: \"%s\"\n", |
504 lock->lo_name); |
505 printf(" 1st @ %s:%d\n", w->w_file, w->w_line); 506 printf(" 2nd @ %s:%d\n", file, line); 507#ifdef DDB 508 go_into_ddb = 1; 509#endif /* DDB */ 510 goto out; 511 } 512 MPASS(!mtx_owned(&w_mtx)); |
513 mtx_lock_spin(&w_mtx); |
514 /* 515 * If we have a known higher number just say ok 516 */ 517 if (witness_watch > 1 && w->w_level > w1->w_level) { |
518 mtx_unlock_spin(&w_mtx); |
519 goto out; 520 } |
521 if (isitmydescendant(w1, w)) { 522 mtx_unlock_spin(&w_mtx); |
523 goto out; 524 } |
525 for (j = 0, lle = *lock_list; lle != NULL; lle = lle->ll_next) { 526 for (i = lle->ll_count - 1; i >= 0; i--, j++) { |
527 |
528 MPASS(j < WITNESS_COUNT); 529 lock1 = lle->ll_children[i]; 530 w1 = lock1->lo_witness; 531 532 /* 533 * If this lock doesn't undergo witness checking, 534 * then skip it. 535 */ 536 if (w1 == NULL) { 537 KASSERT((lock1->lo_flags & LO_WITNESS) == 0, 538 ("lock missing witness structure")); 539 continue; 540 } 541 if (!isitmydescendant(w, w1)) 542 continue; 543 /* 544 * We have a lock order violation, check to see if it 545 * is allowed or has already been yelled about. 546 */ 547 mtx_unlock_spin(&w_mtx); |
548 if (blessed(w, w1)) 549 goto out; |
550 if (lock1 == &Giant.mtx_object) { |
551 if (w1->w_Giant_squawked) 552 goto out; 553 else 554 w1->w_Giant_squawked = 1; 555 } else { 556 if (w1->w_other_squawked) 557 goto out; 558 else 559 w1->w_other_squawked = 1; 560 } |
561 /* 562 * Ok, yell about it. 563 */ |
564 printf("lock order reversal\n"); |
565 /* 566 * Try to locate an earlier lock with 567 * witness w in our list. 568 */ 569 do { 570 lock2 = lle->ll_children[i]; 571 MPASS(lock2 != NULL); 572 if (lock2->lo_witness == w) 573 break; 574 i--; 575 if (i == 0 && lle->ll_next != NULL) { 576 lle = lle->ll_next; 577 i = lle->ll_count - 1; 578 MPASS(i != 0); 579 } 580 } while (i >= 0); 581 if (i < 0) 582 /* 583 * We are very likely bogus in this case. 584 */ 585 printf(" 1st %s last acquired @ %s:%d\n", 586 w->w_name, w->w_file, w->w_line); 587 else 588 printf(" 1st %p %s @ %s:%d\n", lock2, 589 lock2->lo_name, lock2->lo_file, 590 lock2->lo_line); |
591 printf(" 2nd %p %s @ %s:%d\n", |
592 lock1, lock1->lo_name, lock1->lo_file, 593 lock1->lo_line); |
594 printf(" 3rd %p %s @ %s:%d\n", |
595 lock, lock->lo_name, file, line); |
596#ifdef DDB 597 go_into_ddb = 1; 598#endif /* DDB */ 599 goto out; 600 } 601 } |
602 lock1 = (*lock_list)->ll_children[(*lock_list)->ll_count - 1]; 603 if (!itismychild(lock1->lo_witness, w)) 604 mtx_unlock_spin(&w_mtx); |
605 606out: 607#ifdef DDB 608 if (witness_ddb && go_into_ddb) 609 Debugger("witness_enter"); 610#endif /* DDB */ 611 w->w_file = file; 612 w->w_line = line; |
613 lock->lo_line = line; 614 lock->lo_file = file; 615 616 lle = *lock_list; 617 if (lle == NULL || lle->ll_count == LOCK_CHILDCOUNT) { 618 *lock_list = witness_lock_list_get(); 619 if (*lock_list == NULL) |
620 return; |
621 (*lock_list)->ll_next = lle; 622 lle = *lock_list; |
623 } |
624 lle->ll_children[lle->ll_count++] = lock; |
625} 626 627void |
628witness_unlock(struct lock_object *lock, int flags, const char *file, int line) |
629{ |
630 struct lock_list_entry **lock_list, *lle; 631 struct lock_class *class; |
632 struct proc *p; |
633 int i, j; |
634 |
635 if (witness_cold || witness_dead || lock->lo_witness == NULL || 636 panicstr) |
637 return; |
638 p = curproc; |
639 class = lock->lo_class; |
640 |
641 if (lock->lo_flags & LO_RECURSED) { 642 if ((lock->lo_flags & LO_LOCKED) == 0) 643 panic("%s: recursed lock (%s) %s is not locked @ %s:%d", 644 __func__, class->lc_name, lock->lo_name, file, 645 line); |
646 return; 647 } |
648 |
649 /* 650 * We don't need to protect this PCPU_GET() here against preemption 651 * because if we hold any spinlocks then we are already protected, 652 * and if we don't we will get NULL if we hold no spinlocks even if 653 * we switch CPU's while reading it. 654 */ 655 if (class->lc_flags & LC_SLEEPLOCK) { 656 if ((flags & LOP_NOSWITCH) == 0 && PCPU_GET(spinlocks) != NULL) 657 panic("switchable sleep unlock (%s) %s @ %s:%d", 658 class->lc_name, lock->lo_name, file, line); 659 lock_list = &p->p_sleeplocks; 660 } else 661 lock_list = PCPU_PTR(spinlocks); |
662 |
663 for (; *lock_list != NULL; lock_list = &(*lock_list)->ll_next) 664 for (i = 0; i < (*lock_list)->ll_count; i++) 665 if ((*lock_list)->ll_children[i] == lock) { 666 (*lock_list)->ll_count--; 667 for (j = i; j < (*lock_list)->ll_count; j++) 668 (*lock_list)->ll_children[j] = 669 (*lock_list)->ll_children[j + 1]; 670 if ((*lock_list)->ll_count == 0) { 671 lle = *lock_list; 672 *lock_list = lle->ll_next; 673 witness_lock_list_free(lle); 674 } 675 return; 676 } |
677} 678 |
679/* 680 * Warn if any held locks are not sleepable. Note that Giant and the lock 681 * passed in are both special cases since they are both released during the 682 * sleep process and aren't actually held while the process is asleep. 683 */ |
684int |
685witness_sleep(int check_only, struct lock_object *lock, const char *file, 686 int line) |
687{ |
688 struct lock_list_entry **lock_list, *lle; 689 struct lock_object *lock1; |
690 struct proc *p; |
691 critical_t savecrit; 692 int i, n; |
693 |
694 if (witness_dead || panicstr) 695 return (0); 696 KASSERT(!witness_cold, ("%s: witness_cold\n", __func__)); 697 n = 0; 698 /* 699 * Preemption bad because we need PCPU_PTR(spinlocks) to not change. 700 */ 701 savecrit = critical_enter(); |
702 p = curproc; |
703 lock_list = &p->p_sleeplocks; 704again: 705 for (lle = *lock_list; lle != NULL; lle = lle->ll_next) 706 for (i = lle->ll_count - 1; i >= 0; i--) { 707 lock1 = lle->ll_children[i]; 708 if (lock1 == lock || lock1 == &Giant.mtx_object || 709 (lock1->lo_flags & LO_SLEEPABLE)) 710 continue; 711 n++; 712 printf("%s:%d: %s with \"%s\" locked from %s:%d\n", 713 file, line, check_only ? "could sleep" : "sleeping", 714 lock1->lo_name, lock1->lo_file, lock1->lo_line); 715 } 716 if (lock_list == &p->p_sleeplocks) { 717 lock_list = PCPU_PTR(spinlocks); 718 goto again; |
719 } 720#ifdef DDB 721 if (witness_ddb && n) 722 Debugger("witness_sleep"); 723#endif /* DDB */ |
724 critical_exit(savecrit); |
725 return (n); 726} 727 728static struct witness * |
729enroll(const char *description, struct lock_class *lock_class) |
730{ |
731 struct witness *w; |
732 733 if (!witness_watch) 734 return (NULL); |
735 |
736 if ((lock_class->lc_flags & LC_SPINLOCK) && witness_skipspin) |
737 return (NULL); |
738 mtx_lock_spin(&w_mtx); 739 STAILQ_FOREACH(w, &w_all, w_list) { 740 if (strcmp(description, w->w_name) == 0) { 741 mtx_unlock_spin(&w_mtx); 742 if (lock_class != w->w_class) 743 panic( 744 "lock (%s) %s does not match earlier (%s) lock", 745 description, lock_class->lc_name, 746 w->w_class->lc_name); |
747 return (w); 748 } 749 } |
750 /* 751 * This isn't quite right, as witness_cold is still 0 while we 752 * enroll all the locks initialized before witness_initialize(). 753 */ 754 if ((lock_class->lc_flags & LC_SPINLOCK) && !witness_cold) 755 panic("spin lock %s not in order list", description); |
756 if ((w = witness_get()) == NULL) 757 return (NULL); |
758 w->w_name = description; 759 w->w_class = lock_class; 760 STAILQ_INSERT_HEAD(&w_all, w, w_list); 761 if (lock_class->lc_flags & LC_SPINLOCK) 762 STAILQ_INSERT_HEAD(&w_spin, w, w_typelist); 763 else if (lock_class->lc_flags & LC_SLEEPLOCK) 764 STAILQ_INSERT_HEAD(&w_sleep, w, w_typelist); 765 else 766 panic("lock class %s is not sleep or spin", 767 lock_class->lc_name); 768 mtx_unlock_spin(&w_mtx); |
769 770 return (w); 771} 772 773static int 774itismychild(struct witness *parent, struct witness *child) 775{ 776 static int recursed; |
777 struct witness_child_list_entry **wcl; 778 struct witness_list *list; |
779 |
780 MPASS(child != NULL && parent != NULL); 781 if ((parent->w_class->lc_flags & (LC_SLEEPLOCK | LC_SPINLOCK)) != 782 (child->w_class->lc_flags & (LC_SLEEPLOCK | LC_SPINLOCK))) 783 panic( 784 "%s: parent (%s) and child (%s) are not the same lock type", 785 __func__, parent->w_class->lc_name, 786 child->w_class->lc_name); 787 |
788 /* 789 * Insert "child" after "parent" 790 */ |
791 wcl = &parent->w_children; 792 while (*wcl != NULL && (*wcl)->wcl_count == WITNESS_NCHILDREN) 793 wcl = &(*wcl)->wcl_next; |
794 |
795 if (*wcl == NULL) { 796 *wcl = witness_child_get(); 797 if (*wcl == NULL) |
798 return (1); |
799 } |
800 801 (*wcl)->wcl_children[(*wcl)->wcl_count++] = child; 802 |
803 /* |
804 * Now prune whole tree. We look for cases where a lock is now 805 * both a descendant and a direct child of a given lock. In that 806 * case, we want to remove the direct child link from the tree. |
807 */ 808 if (recursed) 809 return (0); 810 recursed = 1; |
811 if (parent->w_class->lc_flags & LC_SLEEPLOCK) 812 list = &w_sleep; 813 else 814 list = &w_spin; 815 STAILQ_FOREACH(child, list, w_typelist) { 816 STAILQ_FOREACH(parent, list, w_typelist) { |
817 if (!isitmychild(parent, child)) 818 continue; 819 removechild(parent, child); 820 if (isitmydescendant(parent, child)) 821 continue; 822 itismychild(parent, child); 823 } 824 } 825 recursed = 0; 826 witness_levelall(); 827 return (0); 828} 829 830static void 831removechild(struct witness *parent, struct witness *child) 832{ |
833 struct witness_child_list_entry **wcl, *wcl1; |
834 int i; 835 |
836 for (wcl = &parent->w_children; *wcl != NULL; wcl = &(*wcl)->wcl_next) 837 for (i = 0; i < (*wcl)->wcl_count; i++) 838 if ((*wcl)->wcl_children[i] == child) |
839 goto found; 840 return; 841found: |
842 (*wcl)->wcl_count--; 843 if ((*wcl)->wcl_count > i) 844 (*wcl)->wcl_children[i] = 845 (*wcl)->wcl_children[(*wcl)->wcl_count]; 846 MPASS((*wcl)->wcl_children[i] != NULL); |
847 |
848 if ((*wcl)->wcl_count != 0) |
849 return; 850 |
851 wcl1 = *wcl; 852 *wcl = wcl1->wcl_next; 853 witness_child_free(wcl1); |
854} 855 856static int 857isitmychild(struct witness *parent, struct witness *child) 858{ |
859 struct witness_child_list_entry *wcl; |
860 int i; 861 |
862 for (wcl = parent->w_children; wcl != NULL; wcl = wcl->wcl_next) { 863 for (i = 0; i < wcl->wcl_count; i++) { 864 if (wcl->wcl_children[i] == child) |
865 return (1); 866 } 867 } 868 return (0); 869} 870 871static int 872isitmydescendant(struct witness *parent, struct witness *child) 873{ |
874 struct witness_child_list_entry *wcl; 875 int i, j; |
876 |
877 if (isitmychild(parent, child)) 878 return (1); 879 j = 0; 880 for (wcl = parent->w_children; wcl != NULL; wcl = wcl->wcl_next) { |
881 MPASS(j < 1000); |
882 for (i = 0; i < wcl->wcl_count; i++) { 883 if (isitmydescendant(wcl->wcl_children[i], child)) |
884 return (1); 885 } |
886 j++; |
887 } 888 return (0); 889} 890 891void 892witness_levelall (void) 893{ |
894 struct witness_list *list; |
895 struct witness *w, *w1; 896 |
897 /* 898 * First clear all levels. 899 */ 900 STAILQ_FOREACH(w, &w_all, w_list) { 901 w->w_level = 0; 902 } 903 904 /* 905 * Look for locks with no parent and level all their descendants. 906 */ 907 STAILQ_FOREACH(w, &w_all, w_list) { 908 /* 909 * This is just an optimization, technically we could get 910 * away just walking the all list each time. 911 */ 912 if (w->w_class->lc_flags & LC_SLEEPLOCK) 913 list = &w_sleep; 914 else 915 list = &w_spin; 916 STAILQ_FOREACH(w1, list, w_typelist) { |
917 if (isitmychild(w1, w)) |
918 goto skip; |
919 } |
920 witness_leveldescendents(w, 0); |
921 skip: |
922 } 923} 924 925static void 926witness_leveldescendents(struct witness *parent, int level) 927{ |
928 struct witness_child_list_entry *wcl; |
929 int i; |
930 931 if (parent->w_level < level) 932 parent->w_level = level; 933 level++; |
934 for (wcl = parent->w_children; wcl != NULL; wcl = wcl->wcl_next) 935 for (i = 0; i < wcl->wcl_count; i++) 936 witness_leveldescendents(wcl->wcl_children[i], level); |
937} 938 939static void 940witness_displaydescendants(void(*prnt)(const char *fmt, ...), 941 struct witness *parent) 942{ |
943 struct witness_child_list_entry *wcl; 944 int i, level; |
945 |
946 level = parent->w_level; |
947 |
948 prnt("%-2d", level); |
949 for (i = 0; i < level; i++) 950 prnt(" "); |
951 prnt("%s", parent->w_name); |
952 if (parent->w_file != NULL) 953 prnt(" -- last acquired @ %s:%d\n", parent->w_file, 954 parent->w_line); 955 |
956 for (wcl = parent->w_children; wcl != NULL; wcl = wcl->wcl_next) 957 for (i = 0; i < wcl->wcl_count; i++) 958 witness_displaydescendants(prnt, 959 wcl->wcl_children[i]); 960} |
961 962static int 963dup_ok(struct witness *w) 964{ |
965 const char **dup; |
966 |
967 for (dup = dup_list; *dup != NULL; dup++) 968 if (strcmp(w->w_name, *dup) == 0) |
969 return (1); 970 return (0); 971} 972 973static int 974blessed(struct witness *w1, struct witness *w2) 975{ 976 int i; 977 struct witness_blessed *b; 978 979 for (i = 0; i < blessed_count; i++) { 980 b = &blessed_list[i]; |
981 if (strcmp(w1->w_name, b->b_lock1) == 0) { 982 if (strcmp(w2->w_name, b->b_lock2) == 0) |
983 return (1); 984 continue; 985 } |
986 if (strcmp(w1->w_name, b->b_lock2) == 0) 987 if (strcmp(w2->w_name, b->b_lock1) == 0) |
988 return (1); 989 } 990 return (0); 991} 992 993static struct witness * |
994witness_get(void) |
995{ 996 struct witness *w; 997 |
998 if (STAILQ_EMPTY(&w_free)) { |
999 witness_dead = 1; |
1000 mtx_unlock_spin(&w_mtx); 1001 printf("%s: witness exhausted\n", __func__); |
1002 return (NULL); 1003 } |
1004 w = STAILQ_FIRST(&w_free); 1005 STAILQ_REMOVE_HEAD(&w_free, w_list); |
1006 bzero(w, sizeof(*w)); 1007 return (w); 1008} 1009 1010static void 1011witness_free(struct witness *w) 1012{ |
1013 1014 STAILQ_INSERT_HEAD(&w_free, w, w_list); |
1015} 1016 |
1017static struct witness_child_list_entry * 1018witness_child_get(void) |
1019{ |
1020 struct witness_child_list_entry *wcl; |
1021 |
1022 wcl = w_child_free; 1023 if (wcl == NULL) { 1024 witness_dead = 1; 1025 mtx_unlock_spin(&w_mtx); 1026 printf("%s: witness exhausted\n", __func__); 1027 return (NULL); |
1028 } |
1029 w_child_free = wcl->wcl_next; 1030 bzero(wcl, sizeof(*wcl)); 1031 return (wcl); 1032} |
1033 |
1034static void 1035witness_child_free(struct witness_child_list_entry *wcl) 1036{ 1037 1038 wcl->wcl_next = w_child_free; 1039 w_child_free = wcl; |
1040} 1041 |
1042static struct lock_list_entry * 1043witness_lock_list_get(void) 1044{ 1045 struct lock_list_entry *lle; |
1046 |
1047 mtx_lock_spin(&w_mtx); 1048 lle = w_lock_list_free; 1049 if (lle == NULL) { 1050 witness_dead = 1; 1051 mtx_unlock_spin(&w_mtx); 1052 printf("%s: witness exhausted\n", __func__); 1053 return (NULL); 1054 } 1055 w_lock_list_free = lle->ll_next; 1056 mtx_unlock_spin(&w_mtx); 1057 bzero(lle, sizeof(*lle)); 1058 return (lle); 1059} 1060 1061static void 1062witness_lock_list_free(struct lock_list_entry *lle) |
1063{ 1064 |
1065 mtx_lock_spin(&w_mtx); 1066 lle->ll_next = w_lock_list_free; 1067 w_lock_list_free = lle; 1068 mtx_unlock_spin(&w_mtx); |
1069} 1070 |
1071/* 1072 * Calling this on p != curproc is bad unless we are in ddb. 1073 */ 1074int 1075witness_list(struct proc *p) |
1076{ |
1077 struct lock_list_entry **lock_list, *lle; 1078 struct lock_object *lock; 1079 critical_t savecrit; 1080 int i, nheld; |
1081 |
1082 KASSERT(p == curproc || db_active, 1083 ("%s: p != curproc and we aren't in the debugger", __func__)); 1084 KASSERT(!witness_cold, ("%s: witness_cold", __func__)); 1085 nheld = 0; 1086 /* 1087 * Preemption bad because we need PCPU_PTR(spinlocks) to not change. 1088 */ 1089 savecrit = critical_enter(); 1090 lock_list = &p->p_sleeplocks; 1091again: 1092 for (lle = *lock_list; lle != NULL; lle = lle->ll_next) 1093 for (i = lle->ll_count - 1; i >= 0; i--) { 1094 lock = lle->ll_children[i]; 1095 printf("\t(%s) %s (%p) locked at %s:%d\n", 1096 lock->lo_class->lc_name, lock->lo_name, lock, 1097 lock->lo_file, lock->lo_line); 1098 nheld++; 1099 } 1100 /* 1101 * We only handle spinlocks if p == curproc. This is somewhat broken 1102 * if p is currently executing on some other CPU and holds spin locks 1103 * as we won't display those locks. 1104 */ 1105 if (lock_list == &p->p_sleeplocks && p == curproc) { 1106 lock_list = PCPU_PTR(spinlocks); 1107 goto again; 1108 } 1109 critical_exit(savecrit); 1110 1111 return (nheld); |
1112} |
1113 1114void |
1115witness_save(struct lock_object *lock, const char **filep, int *linep) |
1116{ 1117 |
1118 KASSERT(!witness_cold, ("%s: witness_cold\n", __func__)); 1119 if (lock->lo_witness == NULL) |
1120 return; 1121 |
1122 *filep = lock->lo_file; 1123 *linep = lock->lo_line; |
1124} 1125 1126void |
1127witness_restore(struct lock_object *lock, const char *file, int line) |
1128{ 1129 |
1130 KASSERT(!witness_cold, ("%s: witness_cold\n", __func__)); 1131 if (lock->lo_witness == NULL) |
1132 return; 1133 |
1134 lock->lo_witness->w_file = file; 1135 lock->lo_witness->w_line = line; 1136 lock->lo_file = file; 1137 lock->lo_line = line; |
1138} 1139 |
1140#ifdef DDB 1141 1142DB_SHOW_COMMAND(mutexes, db_witness_list) 1143{ 1144 1145 witness_list(curproc); 1146} 1147 1148DB_SHOW_COMMAND(witness, db_witness_display) 1149{ 1150 1151 witness_display(db_printf); 1152} 1153#endif |