subr_turnstile.c revision 65856
1178596Sraj/*- 2178596Sraj * Copyright (c) 1998 Berkeley Software Design, Inc. All rights reserved. 3178596Sraj * 4178596Sraj * Redistribution and use in source and binary forms, with or without 5178596Sraj * modification, are permitted provided that the following conditions 6178596Sraj * are met: 7178596Sraj * 1. Redistributions of source code must retain the above copyright 8178596Sraj * notice, this list of conditions and the following disclaimer. 9178596Sraj * 2. Redistributions in binary form must reproduce the above copyright 10178596Sraj * notice, this list of conditions and the following disclaimer in the 11178596Sraj * documentation and/or other materials provided with the distribution. 12178596Sraj * 3. Berkeley Software Design Inc's name may not be used to endorse or 13178596Sraj * promote products derived from this software without specific prior 14178596Sraj * written permission. 15178596Sraj * 16178596Sraj * THIS SOFTWARE IS PROVIDED BY BERKELEY SOFTWARE DESIGN INC ``AS IS'' AND 17178596Sraj * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 18178596Sraj * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 19178596Sraj * ARE DISCLAIMED. IN NO EVENT SHALL BERKELEY SOFTWARE DESIGN INC BE LIABLE 20178596Sraj * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 21178596Sraj * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 22178596Sraj * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 23178596Sraj * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 24178596Sraj * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 25178596Sraj * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 26178596Sraj * SUCH DAMAGE. 27178596Sraj * 28178596Sraj * from BSDI $Id: mutex_witness.c,v 1.1.2.20 2000/04/27 03:10:27 cp Exp $ 29178596Sraj * $FreeBSD: head/sys/kern/subr_turnstile.c 65856 2000-09-14 20:15:16Z jhb $ 30178596Sraj */ 31178596Sraj 32209908Sraj/* 33209908Sraj * Main Entry: witness 34209908Sraj * Pronunciation: 'wit-n&s 35178596Sraj * Function: noun 36178597Sraj * Etymology: Middle English witnesse, from Old English witnes knowledge, 37178597Sraj * testimony, witness, from 2wit 38178597Sraj * Date: before 12th century 39178596Sraj * 1 : attestation of a fact or event : TESTIMONY 40178596Sraj * 2 : one that gives evidence; specifically : one who testifies in 41178596Sraj * a cause or before a judicial tribunal 42178596Sraj * 3 : one asked to be present at a transaction so as to be able to 43186227Sraj * testify to its having taken place 44178597Sraj * 4 : one who has personal knowledge of something 45178596Sraj * 5 a : something serving as evidence or proof : SIGN 46178596Sraj * b : public affirmation by word or example of usually 47178596Sraj * religious faith or conviction <the heroic witness to divine 48178596Sraj * life -- Pilot> 49186227Sraj * 6 capitalized : a member of the Jehovah's Witnesses 50186227Sraj */ 51186227Sraj 52186227Sraj#include <sys/param.h> 53186227Sraj#include <sys/proc.h> 54186227Sraj#include <sys/systm.h> 55186227Sraj#include <sys/ktr.h> 56186227Sraj 57178596Sraj#include <machine/cpu.h> 58186227Sraj#define _KERN_MUTEX_C_ /* Cause non-inlined mtx_*() to be compiled. */ 59178596Sraj#include <machine/mutex.h> 60186227Sraj 61178596Sraj/* 62186227Sraj * The non-inlined versions of the mtx_*() functions are always built (above), 63186227Sraj * but the witness code depends on the SMP_DEBUG and WITNESS kernel options 64186227Sraj * being specified. 65186227Sraj */ 66189757Sraj#if (defined(SMP_DEBUG) && defined(WITNESS)) 67186288Sraj 68186288Sraj#define WITNESS_COUNT 200 69186288Sraj#define WITNESS_NCHILDREN 2 70186288Sraj 71186288Sraj#ifndef WITNESS 72186288Sraj#define WITNESS 0 /* default off */ 73186288Sraj#endif 74189757Sraj 75189757Sraj#ifndef SMP 76186288Srajextern int witness_spin_check; 77186288Sraj#endif 78186288Sraj 79186288Srajint witness_watch; 80186288Sraj 81186288Srajstruct witness { 82186288Sraj struct witness *w_next; 83186288Sraj char *w_description; 84186288Sraj const char *w_file; 85186288Sraj int w_line; 86186288Sraj struct witness *w_morechildren; 87186288Sraj u_char w_childcnt; 88186288Sraj u_char w_Giant_squawked:1; 89186288Sraj u_char w_other_squawked:1; 90186288Sraj u_char w_same_squawked:1; 91186288Sraj u_char w_sleep:1; 92186288Sraj u_char w_spin:1; /* this is a spin mutex */ 93186288Sraj u_int w_level; 94186288Sraj struct witness *w_children[WITNESS_NCHILDREN]; 95186288Sraj}; 96186288Sraj 97186288Srajstruct witness_blessed { 98186288Sraj char *b_lock1; 99186288Sraj char *b_lock2; 100186288Sraj}; 101186288Sraj 102186288Sraj#ifdef KDEBUG 103186288Sraj/* 104186288Sraj * When WITNESS_KDEBUG is set to 1, it will cause the system to 105186288Sraj * drop into kdebug() when: 106186288Sraj * - a lock heirarchy violation occurs 107186288Sraj * - locks are held when going to sleep. 108186288Sraj */ 109186288Sraj#ifndef WITNESS_KDEBUG 110186288Sraj#define WITNESS_KDEBUG 0 111186288Sraj#endif 112186288Srajint witness_kdebug = WITNESS_KDEBUG; 113186288Sraj#endif /* KDEBUG */ 114186288Sraj 115186288Sraj#ifndef WITNESS_SKIPSPIN 116186288Sraj#define WITNESS_SKIPSPIN 0 117186288Sraj#endif 118186288Srajint witness_skipspin = WITNESS_SKIPSPIN; 119186288Sraj 120186288Sraj 121186288Srajstatic struct mtx w_mtx; 122186288Srajstatic struct witness *w_free; 123186288Srajstatic struct witness *w_all; 124186288Srajstatic int w_inited; 125186288Srajstatic int witness_dead; /* fatal error, probably no memory */ 126186288Sraj 127186288Srajstatic struct witness w_data[WITNESS_COUNT]; 128186288Sraj 129186288Srajstatic struct witness *enroll __P((char *description, int flag)); 130186288Srajstatic int itismychild __P((struct witness *parent, struct witness *child)); 131186288Srajstatic void removechild __P((struct witness *parent, struct witness *child)); 132186288Srajstatic int isitmychild __P((struct witness *parent, struct witness *child)); 133186288Srajstatic int isitmydescendant __P((struct witness *parent, struct witness *child)); 134209908Srajstatic int dup_ok __P((struct witness *)); 135209908Srajstatic int blessed __P((struct witness *, struct witness *)); 136209908Srajstatic void witness_displaydescendants 137209908Sraj __P((void(*)(const char *fmt, ...), struct witness *)); 138209908Srajstatic void witness_leveldescendents __P((struct witness *parent, int level)); 139209908Srajstatic void witness_levelall __P((void)); 140209908Srajstatic struct witness * witness_get __P((void)); 141209908Srajstatic void witness_free __P((struct witness *m)); 142209908Sraj 143209908Sraj 144209908Srajstatic char *ignore_list[] = { 145209908Sraj "witness lock", 146209908Sraj "Kdebug", /* breaks rules and may or may not work */ 147209908Sraj "Page Alias", /* sparc only, witness lock won't block intr */ 148209908Sraj NULL 149209908Sraj}; 150209908Sraj 151209908Srajstatic char *spin_order_list[] = { 152209908Sraj "sched lock", 153209908Sraj "log mtx", 154209908Sraj "zslock", /* sparc only above log, this one is a real hack */ 155209908Sraj "time lock", /* above callout */ 156209908Sraj "callout mtx", /* above wayout */ 157209908Sraj /* 158209908Sraj * leaf locks 159209908Sraj */ 160209908Sraj "wayout mtx", 161209908Sraj "kernel_pmap", /* sparc only, logically equal "pmap" below */ 162209908Sraj "pmap", /* sparc only */ 163209908Sraj NULL 164209908Sraj}; 165209908Sraj 166209908Srajstatic char *order_list[] = { 167186227Sraj "tcb", "inp", "so_snd", "so_rcv", "Giant lock", NULL, 168186227Sraj "udb", "inp", NULL, 169186227Sraj "unp head", "unp", "so_snd", NULL, 170186227Sraj "de0", "Giant lock", NULL, 171186227Sraj "ifnet", "Giant lock", NULL, 172189757Sraj "fifo", "so_snd", NULL, 173189757Sraj "hme0", "Giant lock", NULL, 174178597Sraj "esp0", "Giant lock", NULL, 175186227Sraj "hfa0", "Giant lock", NULL, 176178597Sraj "so_rcv", "atm_global", NULL, 177178597Sraj "so_snd", "atm_global", NULL, 178178597Sraj "NFS", "Giant lock", NULL, 179186227Sraj NULL 180178596Sraj}; 181178597Sraj 182178597Srajstatic char *dup_list[] = { 183178596Sraj "inp", 184178597Sraj "process group", 185186227Sraj "session", 186186227Sraj "unp", 187178597Sraj "rtentry", 188178597Sraj "rawcb", 189178596Sraj NULL 190178596Sraj}; 191178596Sraj 192static char *sleep_list[] = { 193 "Giant lock", 194 NULL 195}; 196 197/* 198 * Pairs of locks which have been blessed 199 * Don't complain about order problems with blessed locks 200 */ 201static struct witness_blessed blessed_list[] = { 202}; 203static int blessed_count = sizeof(blessed_list) / sizeof(struct witness_blessed); 204 205void 206witness_init(struct mtx *m, int flag) 207{ 208 m->mtx_witness = enroll(m->mtx_description, flag); 209} 210 211void 212witness_destroy(struct mtx *m) 213{ 214 struct mtx *m1; 215 struct proc *p; 216 p = CURPROC; 217 for ((m1 = LIST_FIRST(&p->p_heldmtx)); m1 != NULL; 218 m1 = LIST_NEXT(m1, mtx_held)) { 219 if (m1 == m) { 220 LIST_REMOVE(m, mtx_held); 221 break; 222 } 223 } 224 return; 225 226} 227 228void 229witness_enter(struct mtx *m, int flags, const char *file, int line) 230{ 231 struct witness *w, *w1; 232 struct mtx *m1; 233 struct proc *p; 234 int i; 235#ifdef KDEBUG 236 int go_into_kdebug = 0; 237#endif /* KDEBUG */ 238 239 w = m->mtx_witness; 240 p = CURPROC; 241 242 if (flags & MTX_SPIN) { 243 if (!w->w_spin) 244 panic("mutex_enter: MTX_SPIN on MTX_DEF mutex %s @" 245 " %s:%d", m->mtx_description, file, line); 246 if (m->mtx_recurse != 0) 247 return; 248 mtx_enter(&w_mtx, MTX_SPIN); 249 i = witness_spin_check; 250 if (i != 0 && w->w_level < i) { 251 mtx_exit(&w_mtx, MTX_SPIN); 252 panic("mutex_enter(%s:%x, MTX_SPIN) out of order @" 253 " %s:%d already holding %s:%x", 254 m->mtx_description, w->w_level, file, line, 255 spin_order_list[ffs(i)-1], i); 256 } 257 PCPU_SET(witness_spin_check, i | w->w_level); 258 mtx_exit(&w_mtx, MTX_SPIN); 259 return; 260 } 261 if (w->w_spin) 262 panic("mutex_enter: MTX_DEF on MTX_SPIN mutex %s @ %s:%d", 263 m->mtx_description, file, line); 264 265 if (m->mtx_recurse != 0) 266 return; 267 if (witness_dead) 268 goto out; 269 if (cold) 270 goto out; 271 272 if (!mtx_legal2block()) 273 panic("blockable mtx_enter() of %s when not legal @ %s:%d", 274 m->mtx_description, file, line); 275 /* 276 * Is this the first mutex acquired 277 */ 278 if ((m1 = LIST_FIRST(&p->p_heldmtx)) == NULL) 279 goto out; 280 281 if ((w1 = m1->mtx_witness) == w) { 282 if (w->w_same_squawked || dup_ok(w)) 283 goto out; 284 w->w_same_squawked = 1; 285 printf("acquring duplicate lock of same type: \"%s\"\n", 286 m->mtx_description); 287 printf(" 1st @ %s:%d\n", w->w_file, w->w_line); 288 printf(" 2nd @ %s:%d\n", file, line); 289#ifdef KDEBUG 290 go_into_kdebug = 1; 291#endif /* KDEBUG */ 292 goto out; 293 } 294 MPASS(!mtx_owned(&w_mtx)); 295 mtx_enter(&w_mtx, MTX_SPIN); 296 /* 297 * If we have a known higher number just say ok 298 */ 299 if (witness_watch > 1 && w->w_level > w1->w_level) { 300 mtx_exit(&w_mtx, MTX_SPIN); 301 goto out; 302 } 303 if (isitmydescendant(m1->mtx_witness, w)) { 304 mtx_exit(&w_mtx, MTX_SPIN); 305 goto out; 306 } 307 for (i = 0; m1 != NULL; m1 = LIST_NEXT(m1, mtx_held), i++) { 308 309 ASS(i < 200); 310 w1 = m1->mtx_witness; 311 if (isitmydescendant(w, w1)) { 312 mtx_exit(&w_mtx, MTX_SPIN); 313 if (blessed(w, w1)) 314 goto out; 315 if (m1 == &Giant) { 316 if (w1->w_Giant_squawked) 317 goto out; 318 else 319 w1->w_Giant_squawked = 1; 320 } else { 321 if (w1->w_other_squawked) 322 goto out; 323 else 324 w1->w_other_squawked = 1; 325 } 326 printf("lock order reversal\n"); 327 printf(" 1st %s last acquired @ %s:%d\n", 328 w->w_description, w->w_file, w->w_line); 329 printf(" 2nd %p %s @ %s:%d\n", 330 m1, w1->w_description, w1->w_file, w1->w_line); 331 printf(" 3rd %p %s @ %s:%d\n", 332 m, w->w_description, file, line); 333#ifdef KDEBUG 334 go_into_kdebug = 1; 335#endif /* KDEBUG */ 336 goto out; 337 } 338 } 339 m1 = LIST_FIRST(&p->p_heldmtx); 340 if (!itismychild(m1->mtx_witness, w)) 341 mtx_exit(&w_mtx, MTX_SPIN); 342 343out: 344#ifdef KDEBUG 345 if (witness_kdebug && go_into_kdebug) 346 kdebug(); 347#endif /* KDEBUG */ 348 w->w_file = file; 349 w->w_line = line; 350 m->mtx_line = line; 351 m->mtx_file = file; 352 353 /* 354 * If this pays off it likely means that a mutex being witnessed 355 * is acquired in hardclock. Put it in the ignore list. It is 356 * likely not the mutex this assert fails on. 357 */ 358 ASS(m->mtx_held.le_prev == NULL); 359 LIST_INSERT_HEAD(&p->p_heldmtx, (struct mtx*)m, mtx_held); 360} 361 362void 363witness_exit(struct mtx *m, int flags, const char *file, int line) 364{ 365 struct witness *w; 366 367 w = m->mtx_witness; 368 369 if (flags & MTX_SPIN) { 370 if (!w->w_spin) 371 panic("mutex_exit: MTX_SPIN on MTX_DEF mutex %s @" 372 " %s:%d", m->mtx_description, file, line); 373 if (m->mtx_recurse != 0) 374 return; 375 mtx_enter(&w_mtx, MTX_SPIN); 376 PCPU_SET(witness_spin_check, witness_spin_check & ~w->w_level); 377 mtx_exit(&w_mtx, MTX_SPIN); 378 return; 379 } 380 if (w->w_spin) 381 panic("mutex_exit: MTX_DEF on MTX_SPIN mutex %s @ %s:%d", 382 m->mtx_description, file, line); 383 384 if (m->mtx_recurse != 0) 385 return; 386 387 if ((flags & MTX_NOSWITCH) == 0 && !mtx_legal2block() && !cold) 388 panic("switchable mtx_exit() of %s when not legal @ %s:%d", 389 m->mtx_description, file, line); 390 LIST_REMOVE(m, mtx_held); 391 m->mtx_held.le_prev = NULL; 392} 393 394void 395witness_try_enter(struct mtx *m, int flags, const char *file, int line) 396{ 397 struct proc *p; 398 struct witness *w = m->mtx_witness; 399 400 if (flags & MTX_SPIN) { 401 if (!w->w_spin) 402 panic("mutex_try_enter: " 403 "MTX_SPIN on MTX_DEF mutex %s @ %s:%d", 404 m->mtx_description, file, line); 405 if (m->mtx_recurse != 0) 406 return; 407 mtx_enter(&w_mtx, MTX_SPIN); 408 PCPU_SET(witness_spin_check, witness_spin_check | w->w_level); 409 mtx_exit(&w_mtx, MTX_SPIN); 410 return; 411 } 412 413 if (w->w_spin) 414 panic("mutex_try_enter: MTX_DEF on MTX_SPIN mutex %s @ %s:%d", 415 m->mtx_description, file, line); 416 417 if (m->mtx_recurse != 0) 418 return; 419 420 w->w_file = file; 421 w->w_line = line; 422 m->mtx_line = line; 423 m->mtx_file = file; 424 p = CURPROC; 425 ASS(m->mtx_held.le_prev == NULL); 426 LIST_INSERT_HEAD(&p->p_heldmtx, (struct mtx*)m, mtx_held); 427} 428 429void 430witness_display(void(*prnt)(const char *fmt, ...)) 431{ 432 struct witness *w, *w1; 433 434 witness_levelall(); 435 436 for (w = w_all; w; w = w->w_next) { 437 if (w->w_file == NULL) 438 continue; 439 for (w1 = w_all; w1; w1 = w1->w_next) { 440 if (isitmychild(w1, w)) 441 break; 442 } 443 if (w1 != NULL) 444 continue; 445 /* 446 * This lock has no anscestors, display its descendants. 447 */ 448 witness_displaydescendants(prnt, w); 449 } 450 prnt("\nMutex which were never acquired\n"); 451 for (w = w_all; w; w = w->w_next) { 452 if (w->w_file != NULL) 453 continue; 454 prnt("%s\n", w->w_description); 455 } 456} 457 458int 459witness_sleep(int check_only, struct mtx *mtx, const char *file, int line) 460{ 461 struct mtx *m; 462 struct proc *p; 463 char **sleep; 464 int n = 0; 465 466 p = CURPROC; 467 for ((m = LIST_FIRST(&p->p_heldmtx)); m != NULL; 468 m = LIST_NEXT(m, mtx_held)) { 469 if (m == mtx) 470 continue; 471 for (sleep = sleep_list; *sleep!= NULL; sleep++) 472 if (strcmp(m->mtx_description, *sleep) == 0) 473 goto next; 474 printf("%s:%d: %s with \"%s\" locked from %s:%d\n", 475 file, line, check_only ? "could sleep" : "sleeping", 476 m->mtx_description, 477 m->mtx_witness->w_file, m->mtx_witness->w_line); 478 n++; 479 next: 480 } 481#ifdef KDEBUG 482 if (witness_kdebug && n) 483 kdebug(); 484#endif /* KDEBUG */ 485 return (n); 486} 487 488static struct witness * 489enroll(char *description, int flag) 490{ 491 int i; 492 struct witness *w, *w1; 493 char **ignore; 494 char **order; 495 496 if (!witness_watch) 497 return (NULL); 498 for (ignore = ignore_list; *ignore != NULL; ignore++) 499 if (strcmp(description, *ignore) == 0) 500 return (NULL); 501 502 if (w_inited == 0) { 503 mtx_init(&w_mtx, "witness lock", MTX_DEF); 504 for (i = 0; i < WITNESS_COUNT; i++) { 505 w = &w_data[i]; 506 witness_free(w); 507 } 508 w_inited = 1; 509 for (order = order_list; *order != NULL; order++) { 510 w = enroll(*order, MTX_DEF); 511 w->w_file = "order list"; 512 for (order++; *order != NULL; order++) { 513 w1 = enroll(*order, MTX_DEF); 514 w1->w_file = "order list"; 515 itismychild(w, w1); 516 w = w1; 517 } 518 } 519 } 520 if ((flag & MTX_SPIN) && witness_skipspin) 521 return (NULL); 522 mtx_enter(&w_mtx, MTX_SPIN); 523 for (w = w_all; w; w = w->w_next) { 524 if (strcmp(description, w->w_description) == 0) { 525 mtx_exit(&w_mtx, MTX_SPIN); 526 return (w); 527 } 528 } 529 if ((w = witness_get()) == NULL) 530 return (NULL); 531 w->w_next = w_all; 532 w_all = w; 533 w->w_description = description; 534 mtx_exit(&w_mtx, MTX_SPIN); 535 if (flag & MTX_SPIN) { 536 w->w_spin = 1; 537 538 i = 1; 539 for (order = spin_order_list; *order != NULL; order++) { 540 if (strcmp(description, *order) == 0) 541 break; 542 i <<= 1; 543 } 544 if (*order == NULL) 545 panic("spin lock %s not in order list", description); 546 w->w_level = i; 547 } 548 return (w); 549} 550 551static int 552itismychild(struct witness *parent, struct witness *child) 553{ 554 static int recursed; 555 556 /* 557 * Insert "child" after "parent" 558 */ 559 while (parent->w_morechildren) 560 parent = parent->w_morechildren; 561 562 if (parent->w_childcnt == WITNESS_NCHILDREN) { 563 if ((parent->w_morechildren = witness_get()) == NULL) 564 return (1); 565 parent = parent->w_morechildren; 566 } 567 ASS(child != NULL); 568 parent->w_children[parent->w_childcnt++] = child; 569 /* 570 * now prune whole tree 571 */ 572 if (recursed) 573 return (0); 574 recursed = 1; 575 for (child = w_all; child != NULL; child = child->w_next) { 576 for (parent = w_all; parent != NULL; 577 parent = parent->w_next) { 578 if (!isitmychild(parent, child)) 579 continue; 580 removechild(parent, child); 581 if (isitmydescendant(parent, child)) 582 continue; 583 itismychild(parent, child); 584 } 585 } 586 recursed = 0; 587 witness_levelall(); 588 return (0); 589} 590 591static void 592removechild(struct witness *parent, struct witness *child) 593{ 594 struct witness *w, *w1; 595 int i; 596 597 for (w = parent; w != NULL; w = w->w_morechildren) 598 for (i = 0; i < w->w_childcnt; i++) 599 if (w->w_children[i] == child) 600 goto found; 601 return; 602found: 603 for (w1 = w; w1->w_morechildren != NULL; w1 = w1->w_morechildren) 604 continue; 605 w->w_children[i] = w1->w_children[--w1->w_childcnt]; 606 ASS(w->w_children[i] != NULL); 607 608 if (w1->w_childcnt != 0) 609 return; 610 611 if (w1 == parent) 612 return; 613 for (w = parent; w->w_morechildren != w1; w = w->w_morechildren) 614 continue; 615 w->w_morechildren = 0; 616 witness_free(w1); 617} 618 619static int 620isitmychild(struct witness *parent, struct witness *child) 621{ 622 struct witness *w; 623 int i; 624 625 for (w = parent; w != NULL; w = w->w_morechildren) { 626 for (i = 0; i < w->w_childcnt; i++) { 627 if (w->w_children[i] == child) 628 return (1); 629 } 630 } 631 return (0); 632} 633 634static int 635isitmydescendant(struct witness *parent, struct witness *child) 636{ 637 struct witness *w; 638 int i; 639 int j; 640 641 for (j = 0, w = parent; w != NULL; w = w->w_morechildren, j++) { 642 ASS(j < 1000); 643 for (i = 0; i < w->w_childcnt; i++) { 644 if (w->w_children[i] == child) 645 return (1); 646 } 647 for (i = 0; i < w->w_childcnt; i++) { 648 if (isitmydescendant(w->w_children[i], child)) 649 return (1); 650 } 651 } 652 return (0); 653} 654 655void 656witness_levelall (void) 657{ 658 struct witness *w, *w1; 659 660 for (w = w_all; w; w = w->w_next) 661 if (!w->w_spin) 662 w->w_level = 0; 663 for (w = w_all; w; w = w->w_next) { 664 if (w->w_spin) 665 continue; 666 for (w1 = w_all; w1; w1 = w1->w_next) { 667 if (isitmychild(w1, w)) 668 break; 669 } 670 if (w1 != NULL) 671 continue; 672 witness_leveldescendents(w, 0); 673 } 674} 675 676static void 677witness_leveldescendents(struct witness *parent, int level) 678{ 679 int i; 680 struct witness *w; 681 682 if (parent->w_level < level) 683 parent->w_level = level; 684 level++; 685 for (w = parent; w != NULL; w = w->w_morechildren) 686 for (i = 0; i < w->w_childcnt; i++) 687 witness_leveldescendents(w->w_children[i], level); 688} 689 690static void 691witness_displaydescendants(void(*prnt)(const char *fmt, ...), 692 struct witness *parent) 693{ 694 struct witness *w; 695 int i; 696 int level = parent->w_level; 697 698 prnt("%d", level); 699 if (level < 10) 700 prnt(" "); 701 for (i = 0; i < level; i++) 702 prnt(" "); 703 prnt("%s", parent->w_description); 704 if (parent->w_file != NULL) { 705 prnt(" -- last acquired @ %s", parent->w_file); 706#ifndef W_USE_WHERE 707 prnt(":%d", parent->w_line); 708#endif 709 prnt("\n"); 710 } 711 712 for (w = parent; w != NULL; w = w->w_morechildren) 713 for (i = 0; i < w->w_childcnt; i++) 714 witness_displaydescendants(prnt, w->w_children[i]); 715 } 716 717static int 718dup_ok(struct witness *w) 719{ 720 char **dup; 721 722 for (dup = dup_list; *dup!= NULL; dup++) 723 if (strcmp(w->w_description, *dup) == 0) 724 return (1); 725 return (0); 726} 727 728static int 729blessed(struct witness *w1, struct witness *w2) 730{ 731 int i; 732 struct witness_blessed *b; 733 734 for (i = 0; i < blessed_count; i++) { 735 b = &blessed_list[i]; 736 if (strcmp(w1->w_description, b->b_lock1) == 0) { 737 if (strcmp(w2->w_description, b->b_lock2) == 0) 738 return (1); 739 continue; 740 } 741 if (strcmp(w1->w_description, b->b_lock2) == 0) 742 if (strcmp(w2->w_description, b->b_lock1) == 0) 743 return (1); 744 } 745 return (0); 746} 747 748static struct witness * 749witness_get() 750{ 751 struct witness *w; 752 753 if ((w = w_free) == NULL) { 754 witness_dead = 1; 755 mtx_exit(&w_mtx, MTX_SPIN); 756 printf("witness exhausted\n"); 757 return (NULL); 758 } 759 w_free = w->w_next; 760 bzero(w, sizeof(*w)); 761 return (w); 762} 763 764static void 765witness_free(struct witness *w) 766{ 767 w->w_next = w_free; 768 w_free = w; 769} 770 771void 772witness_list(struct proc *p) 773{ 774 struct mtx *m; 775 776 for ((m = LIST_FIRST(&p->p_heldmtx)); m != NULL; 777 m = LIST_NEXT(m, mtx_held)) { 778 printf("\t\"%s\" (%p) locked at %s:%d\n", 779 m->mtx_description, m, 780 m->mtx_witness->w_file, m->mtx_witness->w_line); 781 } 782} 783 784void 785witness_save(struct mtx *m, const char **filep, int *linep) 786{ 787 *filep = m->mtx_witness->w_file; 788 *linep = m->mtx_witness->w_line; 789} 790 791void 792witness_restore(struct mtx *m, const char *file, int line) 793{ 794 m->mtx_witness->w_file = file; 795 m->mtx_witness->w_line = line; 796} 797 798#endif /* (defined(SMP_DEBUG) && defined(WITNESS)) */ 799