sys/kern/kern_mutex.c

   1 /*-
   2  * Copyright (c) 1998 Berkeley Software Design, Inc. All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   7  * 1. Redistributions of source code must retain the above copyright
   8  *    notice, this list of conditions and the following disclaimer.
   9  * 2. Redistributions in binary form must reproduce the above copyright
  10  *    notice, this list of conditions and the following disclaimer in the
  11  *    documentation and/or other materials provided with the distribution.
  12  * 3. Berkeley Software Design Inc's name may not be used to endorse or
  13  *    promote products derived from this software without specific prior
  14  *    written permission.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY BERKELEY SOFTWARE DESIGN INC ``AS IS'' AND
  17  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  18  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  19  * ARE DISCLAIMED.  IN NO EVENT SHALL BERKELEY SOFTWARE DESIGN INC BE LIABLE
  20  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  21  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  22  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  23  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  24  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  25  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  26  * SUCH DAMAGE.
  27  *
  28  *      from BSDI $Id: mutex_witness.c,v 1.1.2.20 2000/04/27 03:10:27 cp Exp $
  29  * $FreeBSD$
  30  */
  31
  32 /*
  33  *      Main Entry: witness
  34  *      Pronunciation: 'wit-n&s
  35  *      Function: noun
  36  *      Etymology: Middle English witnesse, from Old English witnes knowledge,
  37  *          testimony, witness, from 2wit
  38  *      Date: before 12th century
  39  *      1 : attestation of a fact or event : TESTIMONY
  40  *      2 : one that gives evidence; specifically : one who testifies in
  41  *          a cause or before a judicial tribunal
  42  *      3 : one asked to be present at a transaction so as to be able to
  43  *          testify to its having taken place
  44  *      4 : one who has personal knowledge of something
  45  *      5 a : something serving as evidence or proof : SIGN
  46  *        b : public affirmation by word or example of usually
  47  *            religious faith or conviction <the heroic witness to divine
  48  *            life -- Pilot>
  49  *      6 capitalized : a member of the Jehovah's Witnesses
  50  */
  51
  52 #include <sys/param.h>
  53 #include <sys/proc.h>
  54 #include <sys/systm.h>
  55 #include <sys/ktr.h>
  56
  57 #include <machine/cpu.h>
  58 #define _KERN_MUTEX_C_          /* Cause non-inlined mtx_*() to be compiled. */
  59 #include <machine/mutex.h>
  60
  61 /*
  62  * The non-inlined versions of the mtx_*() functions are always built (above),
  63  * but the witness code depends on the SMP_DEBUG and WITNESS kernel options
  64  * being specified.
  65  */
  66 #if (defined(SMP_DEBUG) && defined(WITNESS))
  67
  68 #define WITNESS_COUNT 200
  69 #define WITNESS_NCHILDREN 2
  70
  71 #ifndef WITNESS
  72 #define WITNESS         0       /* default off */
  73 #endif
  74
  75 #ifndef SMP
  76 extern int witness_spin_check;
  77 #endif
  78
  79 int witness_watch;
  80
  81 typedef struct witness {
  82         struct witness  *w_next;
  83         char            *w_description;
  84         char            *w_file;
  85         int              w_line;
  86         struct witness  *w_morechildren;
  87         u_char           w_childcnt;
  88         u_char           w_Giant_squawked:1;
  89         u_char           w_other_squawked:1;
  90         u_char           w_same_squawked:1;
  91         u_char           w_sleep:1;
  92         u_char           w_spin:1;      /* this is a spin mutex */
  93         u_int            w_level;
  94         struct witness  *w_children[WITNESS_NCHILDREN];
  95 } witness_t;
  96
  97 typedef struct witness_blessed {
  98         char    *b_lock1;
  99         char    *b_lock2;
 100 } witness_blessed_t;
 101
 102 #ifdef KDEBUG
 103 /*
 104  * When WITNESS_KDEBUG is set to 1, it will cause the system to
 105  * drop into kdebug() when:
 106  *      - a lock heirarchy violation occurs
 107  *      - locks are held when going to sleep.
 108  */
 109 #ifndef WITNESS_KDEBUG
 110 #define WITNESS_KDEBUG 0
 111 #endif
 112 int     witness_kdebug = WITNESS_KDEBUG;
 113 #endif /* KDEBUG */
 114
 115 #ifndef WITNESS_SKIPSPIN
 116 #define WITNESS_SKIPSPIN 0
 117 #endif
 118 int     witness_skipspin = WITNESS_SKIPSPIN;
 119
 120
 121 static mtx_t     w_mtx;
 122 static witness_t *w_free;
 123 static witness_t *w_all;
 124 static int       w_inited;
 125 static int       witness_dead;  /* fatal error, probably no memory */
 126
 127 static witness_t w_data[WITNESS_COUNT];
 128
 129 static witness_t *enroll __P((char *description, int flag));
 130 static int itismychild __P((witness_t *parent, witness_t *child));
 131 static void removechild __P((witness_t *parent, witness_t *child));
 132 static int isitmychild __P((witness_t *parent, witness_t *child));
 133 static int isitmydescendant __P((witness_t *parent, witness_t *child));
 134 static int dup_ok __P((witness_t *));
 135 static int blessed __P((witness_t *, witness_t *));
 136 static void witness_displaydescendants
 137     __P((void(*)(const char *fmt, ...), witness_t *));
 138 static void witness_leveldescendents __P((witness_t *parent, int level));
 139 static void witness_levelall __P((void));
 140 static witness_t * witness_get __P((void));
 141 static void witness_free __P((witness_t *m));
 142
 143
 144 static char *ignore_list[] = {
 145         "witness lock",
 146         "Kdebug",               /* breaks rules and may or may not work */
 147         "Page Alias",           /* sparc only, witness lock won't block intr */
 148         NULL
 149 };
 150
 151 static char *spin_order_list[] = {
 152         "sched lock",
 153         "log mtx",
 154         "zslock",       /* sparc only above log, this one is a real hack */
 155         "time lock",    /* above callout */
 156         "callout mtx",  /* above wayout */
 157         /*
 158          * leaf locks
 159          */
 160         "wayout mtx",
 161         "kernel_pmap",  /* sparc only, logically equal "pmap" below */
 162         "pmap",         /* sparc only */
 163         NULL
 164 };
 165
 166 static char *order_list[] = {
 167         "tcb", "inp", "so_snd", "so_rcv", "Giant lock", NULL,
 168         "udb", "inp", NULL,
 169         "unp head", "unp", "so_snd", NULL,
 170         "de0", "Giant lock", NULL,
 171         "ifnet", "Giant lock", NULL,
 172         "fifo", "so_snd", NULL,
 173         "hme0", "Giant lock", NULL,
 174         "esp0", "Giant lock", NULL,
 175         "hfa0", "Giant lock", NULL,
 176         "so_rcv", "atm_global", NULL,
 177         "so_snd", "atm_global", NULL,
 178         "NFS", "Giant lock", NULL,
 179         NULL
 180 };
 181
 182 static char *dup_list[] = {
 183         "inp",
 184         "process group",
 185         "session",
 186         "unp",
 187         "rtentry",
 188         "rawcb",
 189         NULL
 190 };
 191
 192 static 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  */
 201 static witness_blessed_t blessed_list[] = {
 202 };
 203 static int blessed_count = sizeof (blessed_list) / sizeof (witness_blessed_t);
 204
 205 void
 206 witness_init(mtx_t *m, int flag)
 207 {
 208         m->mtx_witness = enroll(m->mtx_description, flag);
 209 }
 210
 211 void
 212 witness_destroy(mtx_t *m)
 213 {
 214         mtx_t *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
 228 void
 229 witness_enter(mtx_t *m, int flags,  char *file, int line)
 230 {
 231         witness_t *w, *w1;
 232         mtx_t *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 @ %s:%d",
 245                             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 @ %s:%d"
 253                             " 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
 282         if ((w1 = m1->mtx_witness) == w) {
 283                 if (w->w_same_squawked || dup_ok(w))
 284                         goto out;
 285                 w->w_same_squawked = 1;
 286                 printf("acquring duplicate lock of same type: \"%s\"\n",
 287                         m->mtx_description);
 288                 printf(" 1st @ %s:%d\n", w->w_file, w->w_line);
 289                 printf(" 2nd @ %s:%d\n", file, line);
 290 #ifdef KDEBUG
 291                 go_into_kdebug = 1;
 292 #endif /* KDEBUG */
 293                 goto out;
 294         }
 295         MPASS(!mtx_owned(&w_mtx));
 296         mtx_enter(&w_mtx, MTX_SPIN);
 297         /*
 298          * If we have a known higher number just say ok
 299          */
 300         if (witness_watch > 1 && w->w_level > w1->w_level) {
 301                 mtx_exit(&w_mtx, MTX_SPIN);
 302                 goto out;
 303         }
 304         if (isitmydescendant(m1->mtx_witness, w)) {
 305                 mtx_exit(&w_mtx, MTX_SPIN);
 306                 goto out;
 307         }
 308         for (i = 0; m1 != NULL; m1 = LIST_NEXT(m1, mtx_held), i++) {
 309
 310                 ASS(i < 200);
 311                 w1 = m1->mtx_witness;
 312                 if (isitmydescendant(w, w1)) {
 313                         mtx_exit(&w_mtx, MTX_SPIN);
 314                         if (blessed(w, w1))
 315                                 goto out;
 316                         if (m1 == &Giant) {
 317                                 if (w1->w_Giant_squawked)
 318                                         goto out;
 319                                 else
 320                                         w1->w_Giant_squawked = 1;
 321                         } else {
 322                                 if (w1->w_other_squawked)
 323                                         goto out;
 324                                 else
 325                                         w1->w_other_squawked = 1;
 326                         }
 327                         printf("lock order reversal\n");
 328                         printf(" 1st %s last acquired @ %s:%d\n",
 329                             w->w_description, w->w_file, w->w_line);
 330                         printf(" 2nd %p %s @ %s:%d\n",
 331                             m1, w1->w_description, w1->w_file, w1->w_line);
 332                         printf(" 3rd %p %s @ %s:%d\n",
 333                             m, w->w_description, file, line);
 334 #ifdef KDEBUG
 335                         go_into_kdebug = 1;
 336 #endif /* KDEBUG */
 337                         goto out;
 338                 }
 339         }
 340         m1 = LIST_FIRST(&p->p_heldmtx);
 341         if (!itismychild(m1->mtx_witness, w))
 342                 mtx_exit(&w_mtx, MTX_SPIN);
 343
 344 out:
 345 #ifdef KDEBUG
 346         if (witness_kdebug && go_into_kdebug)
 347                 kdebug();
 348 #endif /* KDEBUG */
 349         w->w_file = file;
 350         w->w_line = line;
 351         m->mtx_line = line;
 352         m->mtx_file = file;
 353
 354         /*
 355          * If this pays off it likely means that a mutex  being witnessed
 356          * is acquired in hardclock. Put it in the ignore list. It is
 357          * likely not the mutex this assert fails on.
 358          */
 359         ASS(m->mtx_held.le_prev == NULL);
 360         LIST_INSERT_HEAD(&p->p_heldmtx, (struct mtx*)m, mtx_held);
 361 }
 362
 363 void
 364 witness_exit(mtx_t *m, int flags, char *file, int line)
 365 {
 366         witness_t *w;
 367
 368         w = m->mtx_witness;
 369
 370         if (flags & MTX_SPIN) {
 371                 if (!w->w_spin)
 372                         panic("mutex_exit: MTX_SPIN on MTX_DEF mutex %s @ %s:%d",
 373                             m->mtx_description, file, line);
 374                 if (m->mtx_recurse != 0)
 375                         return;
 376                 mtx_enter(&w_mtx, MTX_SPIN);
 377                 PCPU_SET(witness_spin_check, witness_spin_check & ~w->w_level);
 378                 mtx_exit(&w_mtx, MTX_SPIN);
 379                 return;
 380         }
 381         if (w->w_spin)
 382                 panic("mutex_exit: MTX_DEF on MTX_SPIN mutex %s @ %s:%d",
 383                     m->mtx_description, file, line);
 384
 385         if (m->mtx_recurse != 0)
 386                 return;
 387
 388         if ((flags & MTX_NOSWITCH) == 0 && !mtx_legal2block() && !cold)
 389                 panic("switchable mtx_exit() of %s when not legal @ %s:%d",
 390                             m->mtx_description, file, line);
 391         LIST_REMOVE(m, mtx_held);
 392         m->mtx_held.le_prev = NULL;
 393 }
 394
 395 void
 396 witness_try_enter(mtx_t *m, int flags, char *file, int line)
 397 {
 398         struct proc *p;
 399         witness_t *w = m->mtx_witness;
 400
 401
 402         if (flags & MTX_SPIN) {
 403                 if (!w->w_spin)
 404                         panic("mutex_try_enter: "
 405                             "MTX_SPIN on MTX_DEF mutex %s @ %s:%d",
 406                             m->mtx_description, file, line);
 407                 if (m->mtx_recurse != 0)
 408                         return;
 409                 mtx_enter(&w_mtx, MTX_SPIN);
 410                 PCPU_SET(witness_spin_check, witness_spin_check | w->w_level);
 411                 mtx_exit(&w_mtx, MTX_SPIN);
 412                 return;
 413         }
 414
 415         if (w->w_spin)
 416                 panic("mutex_try_enter: MTX_DEF on MTX_SPIN mutex %s @ %s:%d",
 417                     m->mtx_description, file, line);
 418
 419         if (m->mtx_recurse != 0)
 420                 return;
 421
 422         w->w_file = file;
 423         w->w_line = line;
 424         m->mtx_line = line;
 425         m->mtx_file = file;
 426         p = CURPROC;
 427         ASS(m->mtx_held.le_prev == NULL);
 428         LIST_INSERT_HEAD(&p->p_heldmtx, (struct mtx*)m, mtx_held);
 429 }
 430
 431 void
 432 witness_display(void(*prnt)(const char *fmt, ...))
 433 {
 434         witness_t *w, *w1;
 435
 436         witness_levelall();
 437
 438         for (w = w_all; w; w = w->w_next) {
 439                 if (w->w_file == NULL)
 440                         continue;
 441                 for (w1 = w_all; w1; w1 = w1->w_next) {
 442                         if (isitmychild(w1, w))
 443                                 break;
 444                 }
 445                 if (w1 != NULL)
 446                         continue;
 447                 /*
 448                  * This lock has no anscestors, display its descendants.
 449                  */
 450                 witness_displaydescendants(prnt, w);
 451         }
 452         prnt("\nMutex which were never acquired\n");
 453         for (w = w_all; w; w = w->w_next) {
 454                 if (w->w_file != NULL)
 455                         continue;
 456                 prnt("%s\n", w->w_description);
 457         }
 458 }
 459
 460 int
 461 witness_sleep(int check_only, mtx_t *mtx, char *file, int line)
 462 {
 463         mtx_t *m;
 464         struct proc *p;
 465         char **sleep;
 466         int n = 0;
 467
 468         p = CURPROC;
 469         for ((m = LIST_FIRST(&p->p_heldmtx)); m != NULL;
 470             m = LIST_NEXT(m, mtx_held)) {
 471                 if (m == mtx)
 472                         continue;
 473                 for (sleep = sleep_list; *sleep!= NULL; sleep++)
 474                         if (strcmp(m->mtx_description, *sleep) == 0)
 475                                 goto next;
 476                 printf("%s:%d: %s with \"%s\" locked from %s:%d\n",
 477                         file, line, check_only ? "could sleep" : "sleeping",
 478                         m->mtx_description,
 479                         m->mtx_witness->w_file, m->mtx_witness->w_line);
 480                 n++;
 481         next:
 482         }
 483 #ifdef KDEBUG
 484         if (witness_kdebug && n)
 485                 kdebug();
 486 #endif /* KDEBUG */
 487         return (n);
 488 }
 489
 490 static witness_t *
 491 enroll(char *description, int flag)
 492 {
 493         int i;
 494         witness_t *w, *w1;
 495         char **ignore;
 496         char **order;
 497
 498         if (!witness_watch)
 499                 return (NULL);
 500         for (ignore = ignore_list; *ignore != NULL; ignore++)
 501                 if (strcmp(description, *ignore) == 0)
 502                         return (NULL);
 503
 504         if (w_inited == 0) {
 505                 mtx_init(&w_mtx, "witness lock", MTX_DEF);
 506                 for (i = 0; i < WITNESS_COUNT; i++) {
 507                         w = &w_data[i];
 508                         witness_free(w);
 509                 }
 510                 w_inited = 1;
 511                 for (order = order_list; *order != NULL; order++) {
 512                         w = enroll(*order, MTX_DEF);
 513                         w->w_file = "order list";
 514                         for (order++; *order != NULL; order++) {
 515                                 w1 = enroll(*order, MTX_DEF);
 516                                 w1->w_file = "order list";
 517                                 itismychild(w, w1);
 518                                 w = w1;
 519                         }
 520                 }
 521         }
 522         if ((flag & MTX_SPIN) && witness_skipspin)
 523                 return (NULL);
 524         mtx_enter(&w_mtx, MTX_SPIN);
 525         for (w = w_all; w; w = w->w_next) {
 526                 if (strcmp(description, w->w_description) == 0) {
 527                         mtx_exit(&w_mtx, MTX_SPIN);
 528                         return (w);
 529                 }
 530         }
 531         if ((w = witness_get()) == NULL)
 532                 return (NULL);
 533         w->w_next = w_all;
 534         w_all = w;
 535         w->w_description = description;
 536         mtx_exit(&w_mtx, MTX_SPIN);
 537         if (flag & MTX_SPIN) {
 538                 w->w_spin = 1;
 539
 540                 i = 1;
 541                 for (order = spin_order_list; *order != NULL; order++) {
 542                         if (strcmp(description, *order) == 0)
 543                                 break;
 544                         i <<= 1;
 545                 }
 546                 if (*order == NULL)
 547                         panic("spin lock %s not in order list", description);
 548                 w->w_level = i;
 549         }
 550         return (w);
 551 }
 552
 553 static int
 554 itismychild(witness_t *parent, witness_t *child)
 555 {
 556         static int recursed;
 557
 558         /*
 559          * Insert "child" after "parent"
 560          */
 561         while (parent->w_morechildren)
 562                 parent = parent->w_morechildren;
 563
 564         if (parent->w_childcnt == WITNESS_NCHILDREN) {
 565                 if ((parent->w_morechildren = witness_get()) == NULL)
 566                         return (1);
 567                 parent = parent->w_morechildren;
 568         }
 569         ASS(child != NULL);
 570         parent->w_children[parent->w_childcnt++] = child;
 571         /*
 572          * now prune whole tree
 573          */
 574         if (recursed)
 575                 return (0);
 576         recursed = 1;
 577         for (child = w_all; child != NULL; child = child->w_next) {
 578                 for (parent = w_all; parent != NULL;
 579                     parent = parent->w_next) {
 580                         if (!isitmychild(parent, child))
 581                                 continue;
 582                         removechild(parent, child);
 583                         if (isitmydescendant(parent, child))
 584                                 continue;
 585                         itismychild(parent, child);
 586                 }
 587         }
 588         recursed = 0;
 589         witness_levelall();
 590         return (0);
 591 }
 592
 593 static void
 594 removechild(witness_t *parent, witness_t *child)
 595 {
 596         witness_t *w, *w1;
 597         int i;
 598
 599         for (w = parent; w != NULL; w = w->w_morechildren)
 600                 for (i = 0; i < w->w_childcnt; i++)
 601                         if (w->w_children[i] == child)
 602                                 goto found;
 603         return;
 604 found:
 605         for (w1 = w; w1->w_morechildren != NULL; w1 = w1->w_morechildren)
 606                 continue;
 607         w->w_children[i] = w1->w_children[--w1->w_childcnt];
 608         ASS(w->w_children[i] != NULL);
 609
 610         if (w1->w_childcnt != 0)
 611                 return;
 612
 613         if (w1 == parent)
 614                 return;
 615         for (w = parent; w->w_morechildren != w1; w = w->w_morechildren)
 616                 continue;
 617         w->w_morechildren = 0;
 618         witness_free(w1);
 619 }
 620
 621 static int
 622 isitmychild(witness_t *parent, witness_t *child)
 623 {
 624         witness_t *w;
 625         int i;
 626
 627         for (w = parent; w != NULL; w = w->w_morechildren) {
 628                 for (i = 0; i < w->w_childcnt; i++) {
 629                         if (w->w_children[i] == child)
 630                                 return (1);
 631                 }
 632         }
 633         return (0);
 634 }
 635
 636 static int
 637 isitmydescendant(witness_t *parent, witness_t *child)
 638 {
 639         witness_t *w;
 640         int i;
 641         int j;
 642
 643         for (j = 0, w = parent; w != NULL; w = w->w_morechildren, j++) {
 644                 ASS(j < 1000);
 645                 for (i = 0; i < w->w_childcnt; i++) {
 646                         if (w->w_children[i] == child)
 647                                 return (1);
 648                 }
 649                 for (i = 0; i < w->w_childcnt; i++) {
 650                         if (isitmydescendant(w->w_children[i], child))
 651                                 return (1);
 652                 }
 653         }
 654         return (0);
 655 }
 656
 657 void
 658 witness_levelall (void)
 659 {
 660         witness_t *w, *w1;
 661
 662         for (w = w_all; w; w = w->w_next)
 663                 if (!w->w_spin)
 664                         w->w_level = 0;
 665         for (w = w_all; w; w = w->w_next) {
 666                 if (w->w_spin)
 667                         continue;
 668                 for (w1 = w_all; w1; w1 = w1->w_next) {
 669                         if (isitmychild(w1, w))
 670                                 break;
 671                 }
 672                 if (w1 != NULL)
 673                         continue;
 674                 witness_leveldescendents(w, 0);
 675         }
 676 }
 677
 678 static void
 679 witness_leveldescendents(witness_t *parent, int level)
 680 {
 681         int i;
 682         witness_t *w;
 683
 684         if (parent->w_level < level)
 685                 parent->w_level = level;
 686         level++;
 687         for (w = parent; w != NULL; w = w->w_morechildren)
 688                 for (i = 0; i < w->w_childcnt; i++)
 689                         witness_leveldescendents(w->w_children[i], level);
 690 }
 691
 692 static void
 693 witness_displaydescendants(void(*prnt)(const char *fmt, ...), witness_t *parent)
 694 {
 695         witness_t *w;
 696         int i;
 697         int level = parent->w_level;
 698
 699         prnt("%d", level);
 700         if (level < 10)
 701                 prnt(" ");
 702         for (i = 0; i < level; i++)
 703                 prnt(" ");
 704         prnt("%s", parent->w_description);
 705         if (parent->w_file != NULL) {
 706                 prnt(" -- last acquired @ %s", parent->w_file);
 707 #ifndef W_USE_WHERE
 708                 prnt(":%d", parent->w_line);
 709 #endif
 710                 prnt("\n");
 711         }
 712
 713         for (w = parent; w != NULL; w = w->w_morechildren)
 714                 for (i = 0; i < w->w_childcnt; i++)
 715                             witness_displaydescendants(prnt, w->w_children[i]);
 716     }
 717
 718 static int
 719 dup_ok(witness_t *w)
 720 {
 721         char **dup;
 722
 723         for (dup = dup_list; *dup!= NULL; dup++)
 724                 if (strcmp(w->w_description, *dup) == 0)
 725                         return (1);
 726         return (0);
 727 }
 728
 729 static int
 730 blessed(witness_t *w1, witness_t *w2)
 731 {
 732         int i;
 733         witness_blessed_t *b;
 734
 735         for (i = 0; i < blessed_count; i++) {
 736                 b = &blessed_list[i];
 737                 if (strcmp(w1->w_description, b->b_lock1) == 0) {
 738                         if (strcmp(w2->w_description, b->b_lock2) == 0)
 739                                 return (1);
 740                         continue;
 741                 }
 742                 if (strcmp(w1->w_description, b->b_lock2) == 0)
 743                         if (strcmp(w2->w_description, b->b_lock1) == 0)
 744                                 return (1);
 745         }
 746         return (0);
 747 }
 748
 749 static witness_t *
 750 witness_get()
 751 {
 752         witness_t *w;
 753
 754         if ((w = w_free) == NULL) {
 755                 witness_dead = 1;
 756                 mtx_exit(&w_mtx, MTX_SPIN);
 757                 printf("witness exhausted\n");
 758                 return (NULL);
 759         }
 760         w_free = w->w_next;
 761         bzero(w, sizeof (*w));
 762         return (w);
 763 }
 764
 765 static void
 766 witness_free(witness_t *w)
 767 {
 768         w->w_next = w_free;
 769         w_free = w;
 770 }
 771
 772 void
 773 witness_list(struct proc *p)
 774 {
 775         mtx_t *m;
 776
 777         for ((m = LIST_FIRST(&p->p_heldmtx)); m != NULL;
 778             m = LIST_NEXT(m, mtx_held)) {
 779                 printf("\t\"%s\" (%p) locked at %s:%d\n",
 780                     m->mtx_description, m,
 781                     m->mtx_witness->w_file, m->mtx_witness->w_line);
 782         }
 783 }
 784
 785 void
 786 witness_save(mtx_t *m, char **filep, int *linep)
 787 {
 788         *filep = m->mtx_witness->w_file;
 789         *linep = m->mtx_witness->w_line;
 790 }
 791
 792 void
 793 witness_restore(mtx_t *m, char *file, int line)
 794 {
 795         m->mtx_witness->w_file = file;
 796         m->mtx_witness->w_line = line;
 797 }
 798
 799 #endif  /* (defined(SMP_DEBUG) && defined(WITNESS)) */