subr_witness.c revision 73114
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: head/sys/kern/subr_witness.c 73114 2001-02-26 23:27:35Z jake $ 31 */ 32 33/* 34 * Machine independent bits of mutex implementation and implementation of 35 * `witness' structure & related debugging routines. 36 */ 37 38/* 39 * Main Entry: witness 40 * Pronunciation: 'wit-n&s 41 * Function: noun 42 * Etymology: Middle English witnesse, from Old English witnes knowledge, 43 * testimony, witness, from 2wit 44 * Date: before 12th century 45 * 1 : attestation of a fact or event : TESTIMONY 46 * 2 : one that gives evidence; specifically : one who testifies in 47 * a cause or before a judicial tribunal 48 * 3 : one asked to be present at a transaction so as to be able to 49 * testify to its having taken place 50 * 4 : one who has personal knowledge of something 51 * 5 a : something serving as evidence or proof : SIGN 52 * b : public affirmation by word or example of usually 53 * religious faith or conviction <the heroic witness to divine 54 * life -- Pilot> 55 * 6 capitalized : a member of the Jehovah's Witnesses 56 */ 57 58#include "opt_ddb.h" 59#include "opt_witness.h" 60 61#include <sys/param.h> 62#include <sys/bus.h> 63#include <sys/kernel.h> 64#include <sys/malloc.h> 65#include <sys/proc.h> 66#include <sys/sysctl.h> 67#include <sys/systm.h> 68#include <sys/vmmeter.h> 69#include <sys/ktr.h> 70 71#include <machine/atomic.h> 72#include <machine/bus.h> 73#include <machine/clock.h> 74#include <machine/cpu.h> 75 76#include <ddb/ddb.h> 77 78#include <vm/vm.h> 79#include <vm/vm_extern.h> 80 81#include <sys/mutex.h> 82 83/* 84 * The WITNESS-enabled mutex debug structure. 85 */ 86#ifdef WITNESS 87struct mtx_debug { 88 struct witness *mtxd_witness; 89 LIST_ENTRY(mtx) mtxd_held; 90 const char *mtxd_file; 91 int mtxd_line; 92}; 93 94#define mtx_held mtx_debug->mtxd_held 95#define mtx_file mtx_debug->mtxd_file 96#define mtx_line mtx_debug->mtxd_line 97#define mtx_witness mtx_debug->mtxd_witness 98#endif /* WITNESS */ 99 100/* 101 * Internal utility macros. 102 */ 103#define mtx_unowned(m) ((m)->mtx_lock == MTX_UNOWNED) 104 105#define mtx_owner(m) (mtx_unowned((m)) ? NULL \ 106 : (struct proc *)((m)->mtx_lock & MTX_FLAGMASK)) 107 108#define SET_PRIO(p, pri) (p)->p_pri.pri_level = (pri) 109 110/* 111 * Early WITNESS-enabled declarations. 112 */ 113#ifdef WITNESS 114 115/* 116 * Internal WITNESS routines which must be prototyped early. 117 * 118 * XXX: When/if witness code is cleaned up, it would be wise to place all 119 * witness prototyping early in this file. 120 */ 121static void witness_init(struct mtx *, int flag); 122static void witness_destroy(struct mtx *); 123static void witness_display(void(*)(const char *fmt, ...)); 124 125MALLOC_DEFINE(M_WITNESS, "witness", "witness mtx_debug structure"); 126 127/* All mutexes in system (used for debug/panic) */ 128static struct mtx_debug all_mtx_debug = { NULL, {NULL, NULL}, NULL, 0 }; 129 130/* 131 * This global is set to 0 once it becomes safe to use the witness code. 132 */ 133static int witness_cold = 1; 134 135#else /* WITNESS */ 136 137/* XXX XXX XXX 138 * flag++ is sleazoid way of shuting up warning 139 */ 140#define witness_init(m, flag) flag++ 141#define witness_destroy(m) 142#define witness_try_enter(m, t, f, l) 143#endif /* WITNESS */ 144 145/* 146 * All mutex locks in system are kept on the all_mtx list. 147 */ 148static struct mtx all_mtx = { MTX_UNOWNED, 0, 0, 0, "All mutexes queue head", 149 TAILQ_HEAD_INITIALIZER(all_mtx.mtx_blocked), 150 { NULL, NULL }, &all_mtx, &all_mtx, 151#ifdef WITNESS 152 &all_mtx_debug 153#else 154 NULL 155#endif 156 }; 157 158/* 159 * Global variables for book keeping. 160 */ 161static int mtx_cur_cnt; 162static int mtx_max_cnt; 163 164/* 165 * Couple of strings for KTR_LOCK tracing in order to avoid duplicates. 166 */ 167char STR_mtx_lock_slp[] = "GOT (sleep) %s [%p] r=%d at %s:%d"; 168char STR_mtx_unlock_slp[] = "REL (sleep) %s [%p] r=%d at %s:%d"; 169char STR_mtx_lock_spn[] = "GOT (spin) %s [%p] r=%d at %s:%d"; 170char STR_mtx_unlock_spn[] = "REL (spin) %s [%p] r=%d at %s:%d"; 171 172/* 173 * Prototypes for non-exported routines. 174 * 175 * NOTE: Prototypes for witness routines are placed at the bottom of the file. 176 */ 177static void propagate_priority(struct proc *); 178 179static void 180propagate_priority(struct proc *p) 181{ 182 int pri = p->p_pri.pri_level; 183 struct mtx *m = p->p_blocked; 184 185 mtx_assert(&sched_lock, MA_OWNED); 186 for (;;) { 187 struct proc *p1; 188 189 p = mtx_owner(m); 190 191 if (p == NULL) { 192 /* 193 * This really isn't quite right. Really 194 * ought to bump priority of process that 195 * next acquires the mutex. 196 */ 197 MPASS(m->mtx_lock == MTX_CONTESTED); 198 return; 199 } 200 201 MPASS(p->p_magic == P_MAGIC); 202 KASSERT(p->p_stat != SSLEEP, ("sleeping process owns a mutex")); 203 if (p->p_pri.pri_level <= pri) 204 return; 205 206 /* 207 * Bump this process' priority. 208 */ 209 SET_PRIO(p, pri); 210 211 /* 212 * If lock holder is actually running, just bump priority. 213 */ 214 if (p->p_oncpu != NOCPU) { 215 MPASS(p->p_stat == SRUN || p->p_stat == SZOMB); 216 return; 217 } 218 219 /* 220 * If on run queue move to new run queue, and 221 * quit. 222 */ 223 if (p->p_stat == SRUN) { 224 MPASS(p->p_blocked == NULL); 225 remrunqueue(p); 226 setrunqueue(p); 227 return; 228 } 229 230 /* 231 * If we aren't blocked on a mutex, we should be. 232 */ 233 KASSERT(p->p_stat == SMTX, ( 234 "process %d(%s):%d holds %s but isn't blocked on a mutex\n", 235 p->p_pid, p->p_comm, p->p_stat, 236 m->mtx_description)); 237 238 /* 239 * Pick up the mutex that p is blocked on. 240 */ 241 m = p->p_blocked; 242 MPASS(m != NULL); 243 244 /* 245 * Check if the proc needs to be moved up on 246 * the blocked chain 247 */ 248 if (p == TAILQ_FIRST(&m->mtx_blocked)) { 249 continue; 250 } 251 252 p1 = TAILQ_PREV(p, procqueue, p_procq); 253 if (p1->p_pri.pri_level <= pri) { 254 continue; 255 } 256 257 /* 258 * Remove proc from blocked chain and determine where 259 * it should be moved up to. Since we know that p1 has 260 * a lower priority than p, we know that at least one 261 * process in the chain has a lower priority and that 262 * p1 will thus not be NULL after the loop. 263 */ 264 TAILQ_REMOVE(&m->mtx_blocked, p, p_procq); 265 TAILQ_FOREACH(p1, &m->mtx_blocked, p_procq) { 266 MPASS(p1->p_magic == P_MAGIC); 267 if (p1->p_pri.pri_level > pri) 268 break; 269 } 270 271 MPASS(p1 != NULL); 272 TAILQ_INSERT_BEFORE(p1, p, p_procq); 273 CTR4(KTR_LOCK, 274 "propagate_priority: p %p moved before %p on [%p] %s", 275 p, p1, m, m->mtx_description); 276 } 277} 278 279/* 280 * The important part of mtx_trylock{,_flags}() 281 * Tries to acquire lock `m.' We do NOT handle recursion here; we assume that 282 * if we're called, it's because we know we don't already own this lock. 283 */ 284int 285_mtx_trylock(struct mtx *m, int opts, const char *file, int line) 286{ 287 int rval; 288 289 MPASS(curproc != NULL); 290 291 /* 292 * _mtx_trylock does not accept MTX_NOSWITCH option. 293 */ 294 KASSERT((opts & MTX_NOSWITCH) == 0, 295 ("mtx_trylock() called with invalid option flag(s) %d", opts)); 296 297 rval = _obtain_lock(m, curproc); 298 299#ifdef WITNESS 300 if (rval && m->mtx_witness != NULL) { 301 /* 302 * We do not handle recursion in _mtx_trylock; see the 303 * note at the top of the routine. 304 */ 305 KASSERT(!mtx_recursed(m), 306 ("mtx_trylock() called on a recursed mutex")); 307 witness_try_enter(m, (opts | m->mtx_flags), file, line); 308 } 309#endif /* WITNESS */ 310 311 if ((opts & MTX_QUIET) == 0) 312 CTR5(KTR_LOCK, "TRY_LOCK %s [%p] result=%d at %s:%d", 313 m->mtx_description, m, rval, file, line); 314 315 return rval; 316} 317 318/* 319 * _mtx_lock_sleep: the tougher part of acquiring an MTX_DEF lock. 320 * 321 * We call this if the lock is either contested (i.e. we need to go to 322 * sleep waiting for it), or if we need to recurse on it. 323 */ 324void 325_mtx_lock_sleep(struct mtx *m, int opts, const char *file, int line) 326{ 327 struct proc *p = curproc; 328 329 if ((m->mtx_lock & MTX_FLAGMASK) == (uintptr_t)p) { 330 m->mtx_recurse++; 331 atomic_set_ptr(&m->mtx_lock, MTX_RECURSED); 332 if ((opts & MTX_QUIET) == 0) 333 CTR1(KTR_LOCK, "_mtx_lock_sleep: %p recursing", m); 334 return; 335 } 336 337 if ((opts & MTX_QUIET) == 0) 338 CTR4(KTR_LOCK, 339 "_mtx_lock_sleep: %s contested (lock=%p) at %s:%d", 340 m->mtx_description, (void *)m->mtx_lock, file, line); 341 342 while (!_obtain_lock(m, p)) { 343 uintptr_t v; 344 struct proc *p1; 345 346 mtx_lock_spin(&sched_lock); 347 /* 348 * Check if the lock has been released while spinning for 349 * the sched_lock. 350 */ 351 if ((v = m->mtx_lock) == MTX_UNOWNED) { 352 mtx_unlock_spin(&sched_lock); 353 continue; 354 } 355 356 /* 357 * The mutex was marked contested on release. This means that 358 * there are processes blocked on it. 359 */ 360 if (v == MTX_CONTESTED) { 361 p1 = TAILQ_FIRST(&m->mtx_blocked); 362 MPASS(p1 != NULL); 363 m->mtx_lock = (uintptr_t)p | MTX_CONTESTED; 364 365 if (p1->p_pri.pri_level < p->p_pri.pri_level) 366 SET_PRIO(p, p1->p_pri.pri_level); 367 mtx_unlock_spin(&sched_lock); 368 return; 369 } 370 371 /* 372 * If the mutex isn't already contested and a failure occurs 373 * setting the contested bit, the mutex was either released 374 * or the state of the MTX_RECURSED bit changed. 375 */ 376 if ((v & MTX_CONTESTED) == 0 && 377 !atomic_cmpset_ptr(&m->mtx_lock, (void *)v, 378 (void *)(v | MTX_CONTESTED))) { 379 mtx_unlock_spin(&sched_lock); 380 continue; 381 } 382 383 /* 384 * We deffinately must sleep for this lock. 385 */ 386 mtx_assert(m, MA_NOTOWNED); 387 388#ifdef notyet 389 /* 390 * If we're borrowing an interrupted thread's VM context, we 391 * must clean up before going to sleep. 392 */ 393 if (p->p_ithd != NULL) { 394 struct ithd *it = p->p_ithd; 395 396 if (it->it_interrupted) { 397 if ((opts & MTX_QUIET) == 0) 398 CTR2(KTR_LOCK, 399 "_mtx_lock_sleep: %p interrupted %p", 400 it, it->it_interrupted); 401 intr_thd_fixup(it); 402 } 403 } 404#endif 405 406 /* 407 * Put us on the list of threads blocked on this mutex. 408 */ 409 if (TAILQ_EMPTY(&m->mtx_blocked)) { 410 p1 = (struct proc *)(m->mtx_lock & MTX_FLAGMASK); 411 LIST_INSERT_HEAD(&p1->p_contested, m, mtx_contested); 412 TAILQ_INSERT_TAIL(&m->mtx_blocked, p, p_procq); 413 } else { 414 TAILQ_FOREACH(p1, &m->mtx_blocked, p_procq) 415 if (p1->p_pri.pri_level > p->p_pri.pri_level) 416 break; 417 if (p1) 418 TAILQ_INSERT_BEFORE(p1, p, p_procq); 419 else 420 TAILQ_INSERT_TAIL(&m->mtx_blocked, p, p_procq); 421 } 422 423 /* 424 * Save who we're blocked on. 425 */ 426 p->p_blocked = m; 427 p->p_mtxname = m->mtx_description; 428 p->p_stat = SMTX; 429 if (p->p_pri.pri_native == PRI_MAX) 430 p->p_pri.pri_native = p->p_pri.pri_level; 431 propagate_priority(p); 432 433 if ((opts & MTX_QUIET) == 0) 434 CTR3(KTR_LOCK, 435 "_mtx_lock_sleep: p %p blocked on [%p] %s", p, m, 436 m->mtx_description); 437 438 mi_switch(); 439 440 if ((opts & MTX_QUIET) == 0) 441 CTR3(KTR_LOCK, 442 "_mtx_lock_sleep: p %p free from blocked on [%p] %s", 443 p, m, m->mtx_description); 444 445 mtx_unlock_spin(&sched_lock); 446 } 447 448 return; 449} 450 451/* 452 * _mtx_lock_spin: the tougher part of acquiring an MTX_SPIN lock. 453 * 454 * This is only called if we need to actually spin for the lock. Recursion 455 * is handled inline. 456 */ 457void 458_mtx_lock_spin(struct mtx *m, int opts, u_int mtx_intr, const char *file, 459 int line) 460{ 461 int i = 0; 462 463 if ((opts & MTX_QUIET) == 0) 464 CTR1(KTR_LOCK, "_mtx_lock_spin: %p spinning", m); 465 466 for (;;) { 467 if (_obtain_lock(m, curproc)) 468 break; 469 470 while (m->mtx_lock != MTX_UNOWNED) { 471 if (i++ < 1000000) 472 continue; 473 if (i++ < 6000000) 474 DELAY(1); 475#ifdef DDB 476 else if (!db_active) 477#else 478 else 479#endif 480 panic("spin lock %s held by %p for > 5 seconds", 481 m->mtx_description, (void *)m->mtx_lock); 482 } 483 } 484 485 m->mtx_saveintr = mtx_intr; 486 if ((opts & MTX_QUIET) == 0) 487 CTR1(KTR_LOCK, "_mtx_lock_spin: %p spin done", m); 488 489 return; 490} 491 492/* 493 * _mtx_unlock_sleep: the tougher part of releasing an MTX_DEF lock. 494 * 495 * We are only called here if the lock is recursed or contested (i.e. we 496 * need to wake up a blocked thread). 497 */ 498void 499_mtx_unlock_sleep(struct mtx *m, int opts, const char *file, int line) 500{ 501 struct proc *p, *p1; 502 struct mtx *m1; 503 int pri; 504 505 p = curproc; 506 MPASS4(mtx_owned(m), "mtx_owned(mpp)", file, line); 507 508 if (mtx_recursed(m)) { 509 if (--(m->mtx_recurse) == 0) 510 atomic_clear_ptr(&m->mtx_lock, MTX_RECURSED); 511 if ((opts & MTX_QUIET) == 0) 512 CTR1(KTR_LOCK, "_mtx_unlock_sleep: %p unrecurse", m); 513 return; 514 } 515 516 mtx_lock_spin(&sched_lock); 517 if ((opts & MTX_QUIET) == 0) 518 CTR1(KTR_LOCK, "_mtx_unlock_sleep: %p contested", m); 519 520 p1 = TAILQ_FIRST(&m->mtx_blocked); 521 MPASS(p->p_magic == P_MAGIC); 522 MPASS(p1->p_magic == P_MAGIC); 523 524 TAILQ_REMOVE(&m->mtx_blocked, p1, p_procq); 525 526 if (TAILQ_EMPTY(&m->mtx_blocked)) { 527 LIST_REMOVE(m, mtx_contested); 528 _release_lock_quick(m); 529 if ((opts & MTX_QUIET) == 0) 530 CTR1(KTR_LOCK, "_mtx_unlock_sleep: %p not held", m); 531 } else 532 atomic_store_rel_ptr(&m->mtx_lock, (void *)MTX_CONTESTED); 533 534 pri = PRI_MAX; 535 LIST_FOREACH(m1, &p->p_contested, mtx_contested) { 536 int cp = TAILQ_FIRST(&m1->mtx_blocked)->p_pri.pri_level; 537 if (cp < pri) 538 pri = cp; 539 } 540 541 if (pri > p->p_pri.pri_native) 542 pri = p->p_pri.pri_native; 543 SET_PRIO(p, pri); 544 545 if ((opts & MTX_QUIET) == 0) 546 CTR2(KTR_LOCK, "_mtx_unlock_sleep: %p contested setrunqueue %p", 547 m, p1); 548 549 p1->p_blocked = NULL; 550 p1->p_stat = SRUN; 551 setrunqueue(p1); 552 553 if ((opts & MTX_NOSWITCH) == 0 && p1->p_pri.pri_level < pri) { 554#ifdef notyet 555 if (p->p_ithd != NULL) { 556 struct ithd *it = p->p_ithd; 557 558 if (it->it_interrupted) { 559 if ((opts & MTX_QUIET) == 0) 560 CTR2(KTR_LOCK, 561 "_mtx_unlock_sleep: %p interrupted %p", 562 it, it->it_interrupted); 563 intr_thd_fixup(it); 564 } 565 } 566#endif 567 setrunqueue(p); 568 if ((opts & MTX_QUIET) == 0) 569 CTR2(KTR_LOCK, 570 "_mtx_unlock_sleep: %p switching out lock=%p", m, 571 (void *)m->mtx_lock); 572 573 mi_switch(); 574 if ((opts & MTX_QUIET) == 0) 575 CTR2(KTR_LOCK, "_mtx_unlock_sleep: %p resuming lock=%p", 576 m, (void *)m->mtx_lock); 577 } 578 579 mtx_unlock_spin(&sched_lock); 580 581 return; 582} 583 584/* 585 * All the unlocking of MTX_SPIN locks is done inline. 586 * See the _rel_spin_lock() macro for the details. 587 */ 588 589/* 590 * The backing function for the INVARIANTS-enabled mtx_assert() 591 */ 592#ifdef INVARIANT_SUPPORT 593void 594_mtx_assert(struct mtx *m, int what, const char *file, int line) 595{ 596 switch (what) { 597 case MA_OWNED: 598 case MA_OWNED | MA_RECURSED: 599 case MA_OWNED | MA_NOTRECURSED: 600 if (!mtx_owned(m)) 601 panic("mutex %s not owned at %s:%d", 602 m->mtx_description, file, line); 603 if (mtx_recursed(m)) { 604 if ((what & MA_NOTRECURSED) != 0) 605 panic("mutex %s recursed at %s:%d", 606 m->mtx_description, file, line); 607 } else if ((what & MA_RECURSED) != 0) { 608 panic("mutex %s unrecursed at %s:%d", 609 m->mtx_description, file, line); 610 } 611 break; 612 case MA_NOTOWNED: 613 if (mtx_owned(m)) 614 panic("mutex %s owned at %s:%d", 615 m->mtx_description, file, line); 616 break; 617 default: 618 panic("unknown mtx_assert at %s:%d", file, line); 619 } 620} 621#endif 622 623/* 624 * The MUTEX_DEBUG-enabled mtx_validate() 625 */ 626#define MV_DESTROY 0 /* validate before destory */ 627#define MV_INIT 1 /* validate before init */ 628 629#ifdef MUTEX_DEBUG 630 631int mtx_validate __P((struct mtx *, int)); 632 633int 634mtx_validate(struct mtx *m, int when) 635{ 636 struct mtx *mp; 637 int i; 638 int retval = 0; 639 640#ifdef WITNESS 641 if (witness_cold) 642 return 0; 643#endif 644 if (m == &all_mtx || cold) 645 return 0; 646 647 mtx_lock(&all_mtx); 648/* 649 * XXX - When kernacc() is fixed on the alpha to handle K0_SEG memory properly 650 * we can re-enable the kernacc() checks. 651 */ 652#ifndef __alpha__ 653 MPASS(kernacc((caddr_t)all_mtx.mtx_next, sizeof(uintptr_t), 654 VM_PROT_READ) == 1); 655#endif 656 MPASS(all_mtx.mtx_next->mtx_prev == &all_mtx); 657 for (i = 0, mp = all_mtx.mtx_next; mp != &all_mtx; mp = mp->mtx_next) { 658#ifndef __alpha__ 659 if (kernacc((caddr_t)mp->mtx_next, sizeof(uintptr_t), 660 VM_PROT_READ) != 1) { 661 panic("mtx_validate: mp=%p mp->mtx_next=%p", 662 mp, mp->mtx_next); 663 } 664#endif 665 i++; 666 if (i > mtx_cur_cnt) { 667 panic("mtx_validate: too many in chain, known=%d\n", 668 mtx_cur_cnt); 669 } 670 } 671 MPASS(i == mtx_cur_cnt); 672 switch (when) { 673 case MV_DESTROY: 674 for (mp = all_mtx.mtx_next; mp != &all_mtx; mp = mp->mtx_next) 675 if (mp == m) 676 break; 677 MPASS(mp == m); 678 break; 679 case MV_INIT: 680 for (mp = all_mtx.mtx_next; mp != &all_mtx; mp = mp->mtx_next) 681 if (mp == m) { 682 /* 683 * Not good. This mutex already exists. 684 */ 685 printf("re-initing existing mutex %s\n", 686 m->mtx_description); 687 MPASS(m->mtx_lock == MTX_UNOWNED); 688 retval = 1; 689 } 690 } 691 mtx_unlock(&all_mtx); 692 return (retval); 693} 694#endif 695 696/* 697 * Mutex initialization routine; initialize lock `m' of type contained in 698 * `opts' with options contained in `opts' and description `description.' 699 * Place on "all_mtx" queue. 700 */ 701void 702mtx_init(struct mtx *m, const char *description, int opts) 703{ 704 705 if ((opts & MTX_QUIET) == 0) 706 CTR2(KTR_LOCK, "mtx_init %p (%s)", m, description); 707 708#ifdef MUTEX_DEBUG 709 /* Diagnostic and error correction */ 710 if (mtx_validate(m, MV_INIT)) 711 return; 712#endif 713 714 bzero((void *)m, sizeof *m); 715 TAILQ_INIT(&m->mtx_blocked); 716 717#ifdef WITNESS 718 if (!witness_cold) { 719 m->mtx_debug = malloc(sizeof(struct mtx_debug), 720 M_WITNESS, M_NOWAIT | M_ZERO); 721 MPASS(m->mtx_debug != NULL); 722 } 723#endif 724 725 m->mtx_description = description; 726 m->mtx_flags = opts; 727 m->mtx_lock = MTX_UNOWNED; 728 729 /* Put on all mutex queue */ 730 mtx_lock(&all_mtx); 731 m->mtx_next = &all_mtx; 732 m->mtx_prev = all_mtx.mtx_prev; 733 m->mtx_prev->mtx_next = m; 734 all_mtx.mtx_prev = m; 735 if (++mtx_cur_cnt > mtx_max_cnt) 736 mtx_max_cnt = mtx_cur_cnt; 737 mtx_unlock(&all_mtx); 738 739#ifdef WITNESS 740 if (!witness_cold) 741 witness_init(m, opts); 742#endif 743} 744 745/* 746 * Remove lock `m' from all_mtx queue. 747 */ 748void 749mtx_destroy(struct mtx *m) 750{ 751 752#ifdef WITNESS 753 KASSERT(!witness_cold, ("%s: Cannot destroy while still cold\n", 754 __FUNCTION__)); 755#endif 756 757 CTR2(KTR_LOCK, "mtx_destroy %p (%s)", m, m->mtx_description); 758 759#ifdef MUTEX_DEBUG 760 if (m->mtx_next == NULL) 761 panic("mtx_destroy: %p (%s) already destroyed", 762 m, m->mtx_description); 763 764 if (!mtx_owned(m)) { 765 MPASS(m->mtx_lock == MTX_UNOWNED); 766 } else { 767 MPASS((m->mtx_lock & (MTX_RECURSED|MTX_CONTESTED)) == 0); 768 } 769 770 /* diagnostic */ 771 mtx_validate(m, MV_DESTROY); 772#endif 773 774#ifdef WITNESS 775 if (m->mtx_witness) 776 witness_destroy(m); 777#endif /* WITNESS */ 778 779 /* Remove from the all mutex queue */ 780 mtx_lock(&all_mtx); 781 m->mtx_next->mtx_prev = m->mtx_prev; 782 m->mtx_prev->mtx_next = m->mtx_next; 783 784#ifdef MUTEX_DEBUG 785 m->mtx_next = m->mtx_prev = NULL; 786#endif 787 788#ifdef WITNESS 789 free(m->mtx_debug, M_WITNESS); 790 m->mtx_debug = NULL; 791#endif 792 793 mtx_cur_cnt--; 794 mtx_unlock(&all_mtx); 795} 796 797 798/* 799 * The WITNESS-enabled diagnostic code. 800 */ 801#ifdef WITNESS 802static void 803witness_fixup(void *dummy __unused) 804{ 805 struct mtx *mp; 806 807 /* 808 * We have to release Giant before initializing its witness 809 * structure so that WITNESS doesn't get confused. 810 */ 811 mtx_unlock(&Giant); 812 mtx_assert(&Giant, MA_NOTOWNED); 813 814 mtx_lock(&all_mtx); 815 816 /* Iterate through all mutexes and finish up mutex initialization. */ 817 for (mp = all_mtx.mtx_next; mp != &all_mtx; mp = mp->mtx_next) { 818 819 mp->mtx_debug = malloc(sizeof(struct mtx_debug), 820 M_WITNESS, M_NOWAIT | M_ZERO); 821 MPASS(mp->mtx_debug != NULL); 822 823 witness_init(mp, mp->mtx_flags); 824 } 825 mtx_unlock(&all_mtx); 826 827 /* Mark the witness code as being ready for use. */ 828 atomic_store_rel_int(&witness_cold, 0); 829 830 mtx_lock(&Giant); 831} 832SYSINIT(wtnsfxup, SI_SUB_MUTEX, SI_ORDER_FIRST, witness_fixup, NULL) 833 834#define WITNESS_COUNT 200 835#define WITNESS_NCHILDREN 2 836 837int witness_watch = 1; 838 839struct witness { 840 struct witness *w_next; 841 const char *w_description; 842 const char *w_file; 843 int w_line; 844 struct witness *w_morechildren; 845 u_char w_childcnt; 846 u_char w_Giant_squawked:1; 847 u_char w_other_squawked:1; 848 u_char w_same_squawked:1; 849 u_char w_spin:1; /* MTX_SPIN type mutex. */ 850 u_int w_level; 851 struct witness *w_children[WITNESS_NCHILDREN]; 852}; 853 854struct witness_blessed { 855 char *b_lock1; 856 char *b_lock2; 857}; 858 859#ifdef DDB 860/* 861 * When DDB is enabled and witness_ddb is set to 1, it will cause the system to 862 * drop into kdebug() when: 863 * - a lock heirarchy violation occurs 864 * - locks are held when going to sleep. 865 */ 866int witness_ddb; 867#ifdef WITNESS_DDB 868TUNABLE_INT_DECL("debug.witness_ddb", 1, witness_ddb); 869#else 870TUNABLE_INT_DECL("debug.witness_ddb", 0, witness_ddb); 871#endif 872SYSCTL_INT(_debug, OID_AUTO, witness_ddb, CTLFLAG_RW, &witness_ddb, 0, ""); 873#endif /* DDB */ 874 875int witness_skipspin; 876#ifdef WITNESS_SKIPSPIN 877TUNABLE_INT_DECL("debug.witness_skipspin", 1, witness_skipspin); 878#else 879TUNABLE_INT_DECL("debug.witness_skipspin", 0, witness_skipspin); 880#endif 881SYSCTL_INT(_debug, OID_AUTO, witness_skipspin, CTLFLAG_RD, &witness_skipspin, 0, 882 ""); 883 884/* 885 * Witness-enabled globals 886 */ 887static struct mtx w_mtx; 888static struct witness *w_free; 889static struct witness *w_all; 890static int w_inited; 891static int witness_dead; /* fatal error, probably no memory */ 892 893static struct witness w_data[WITNESS_COUNT]; 894 895/* 896 * Internal witness routine prototypes 897 */ 898static struct witness *enroll(const char *description, int flag); 899static int itismychild(struct witness *parent, struct witness *child); 900static void removechild(struct witness *parent, struct witness *child); 901static int isitmychild(struct witness *parent, struct witness *child); 902static int isitmydescendant(struct witness *parent, struct witness *child); 903static int dup_ok(struct witness *); 904static int blessed(struct witness *, struct witness *); 905static void 906 witness_displaydescendants(void(*)(const char *fmt, ...), struct witness *); 907static void witness_leveldescendents(struct witness *parent, int level); 908static void witness_levelall(void); 909static struct witness * witness_get(void); 910static void witness_free(struct witness *m); 911 912static char *ignore_list[] = { 913 "witness lock", 914 NULL 915}; 916 917static char *spin_order_list[] = { 918#if defined(__i386__) && defined (SMP) 919 "com", 920#endif 921 "sio", 922#ifdef __i386__ 923 "cy", 924#endif 925 "ithread table lock", 926 "ithread list lock", 927 "sched lock", 928#ifdef __i386__ 929 "clk", 930#endif 931 "callout", 932 /* 933 * leaf locks 934 */ 935 "ng_node", 936 "ng_worklist", 937#ifdef SMP 938#ifdef __i386__ 939 "ap boot", 940 "imen", 941#endif 942 "smp rendezvous", 943#endif 944 NULL 945}; 946 947static char *order_list[] = { 948 "Giant", "proctree", "allproc", "process lock", "uidinfo hash", 949 "uidinfo struct", NULL, 950 NULL 951}; 952 953static char *dup_list[] = { 954 NULL 955}; 956 957static char *sleep_list[] = { 958 "Giant", 959 NULL 960}; 961 962/* 963 * Pairs of locks which have been blessed 964 * Don't complain about order problems with blessed locks 965 */ 966static struct witness_blessed blessed_list[] = { 967}; 968static int blessed_count = 969 sizeof(blessed_list) / sizeof(struct witness_blessed); 970 971static void 972witness_init(struct mtx *m, int flag) 973{ 974 m->mtx_witness = enroll(m->mtx_description, flag); 975} 976 977static void 978witness_destroy(struct mtx *m) 979{ 980 struct mtx *m1; 981 struct proc *p; 982 p = curproc; 983 LIST_FOREACH(m1, &p->p_heldmtx, mtx_held) { 984 if (m1 == m) { 985 LIST_REMOVE(m, mtx_held); 986 break; 987 } 988 } 989 return; 990 991} 992 993static void 994witness_display(void(*prnt)(const char *fmt, ...)) 995{ 996 struct witness *w, *w1; 997 int level, found; 998 999 KASSERT(!witness_cold, ("%s: witness_cold\n", __FUNCTION__)); 1000 witness_levelall(); 1001 1002 /* 1003 * First, handle sleep mutexes which have been acquired at least 1004 * once. 1005 */ 1006 prnt("Sleep mutexes:\n"); 1007 for (w = w_all; w; w = w->w_next) { 1008 if (w->w_file == NULL || w->w_spin) 1009 continue; 1010 for (w1 = w_all; w1; w1 = w1->w_next) { 1011 if (isitmychild(w1, w)) 1012 break; 1013 } 1014 if (w1 != NULL) 1015 continue; 1016 /* 1017 * This lock has no anscestors, display its descendants. 1018 */ 1019 witness_displaydescendants(prnt, w); 1020 } 1021 1022 /* 1023 * Now do spin mutexes which have been acquired at least once. 1024 */ 1025 prnt("\nSpin mutexes:\n"); 1026 level = 0; 1027 while (level < sizeof(spin_order_list) / sizeof(char *)) { 1028 found = 0; 1029 for (w = w_all; w; w = w->w_next) { 1030 if (w->w_file == NULL || !w->w_spin) 1031 continue; 1032 if (w->w_level == 1 << level) { 1033 witness_displaydescendants(prnt, w); 1034 level++; 1035 found = 1; 1036 } 1037 } 1038 if (found == 0) 1039 level++; 1040 } 1041 1042 /* 1043 * Finally, any mutexes which have not been acquired yet. 1044 */ 1045 prnt("\nMutexes which were never acquired:\n"); 1046 for (w = w_all; w; w = w->w_next) { 1047 if (w->w_file != NULL) 1048 continue; 1049 prnt("%s\n", w->w_description); 1050 } 1051} 1052 1053void 1054witness_enter(struct mtx *m, int flags, const char *file, int line) 1055{ 1056 struct witness *w, *w1; 1057 struct mtx *m1; 1058 struct proc *p; 1059 int i; 1060#ifdef DDB 1061 int go_into_ddb = 0; 1062#endif /* DDB */ 1063 1064 if (witness_cold || m->mtx_witness == NULL || panicstr) 1065 return; 1066 w = m->mtx_witness; 1067 p = curproc; 1068 1069 if (flags & MTX_SPIN) { 1070 if ((m->mtx_flags & MTX_SPIN) == 0) 1071 panic("mutex_enter: MTX_SPIN on MTX_DEF mutex %s @" 1072 " %s:%d", m->mtx_description, file, line); 1073 if (mtx_recursed(m)) { 1074 if ((m->mtx_flags & MTX_RECURSE) == 0) 1075 panic("mutex_enter: recursion on non-recursive" 1076 " mutex %s @ %s:%d", m->mtx_description, 1077 file, line); 1078 return; 1079 } 1080 mtx_lock_spin_flags(&w_mtx, MTX_QUIET); 1081 i = PCPU_GET(witness_spin_check); 1082 if (i != 0 && w->w_level < i) { 1083 mtx_unlock_spin_flags(&w_mtx, MTX_QUIET); 1084 panic("mutex_enter(%s:%x, MTX_SPIN) out of order @" 1085 " %s:%d already holding %s:%x", 1086 m->mtx_description, w->w_level, file, line, 1087 spin_order_list[ffs(i)-1], i); 1088 } 1089 PCPU_SET(witness_spin_check, i | w->w_level); 1090 mtx_unlock_spin_flags(&w_mtx, MTX_QUIET); 1091 w->w_file = file; 1092 w->w_line = line; 1093 m->mtx_line = line; 1094 m->mtx_file = file; 1095 return; 1096 } 1097 if ((m->mtx_flags & MTX_SPIN) != 0) 1098 panic("mutex_enter: MTX_DEF on MTX_SPIN mutex %s @ %s:%d", 1099 m->mtx_description, file, line); 1100 1101 if (mtx_recursed(m)) { 1102 if ((m->mtx_flags & MTX_RECURSE) == 0) 1103 panic("mutex_enter: recursion on non-recursive" 1104 " mutex %s @ %s:%d", m->mtx_description, 1105 file, line); 1106 return; 1107 } 1108 if (witness_dead) 1109 goto out; 1110 if (cold) 1111 goto out; 1112 1113 if (!mtx_legal2block()) 1114 panic("blockable mtx_lock() of %s when not legal @ %s:%d", 1115 m->mtx_description, file, line); 1116 /* 1117 * Is this the first mutex acquired 1118 */ 1119 if ((m1 = LIST_FIRST(&p->p_heldmtx)) == NULL) 1120 goto out; 1121 1122 if ((w1 = m1->mtx_witness) == w) { 1123 if (w->w_same_squawked || dup_ok(w)) 1124 goto out; 1125 w->w_same_squawked = 1; 1126 printf("acquring duplicate lock of same type: \"%s\"\n", 1127 m->mtx_description); 1128 printf(" 1st @ %s:%d\n", w->w_file, w->w_line); 1129 printf(" 2nd @ %s:%d\n", file, line); 1130#ifdef DDB 1131 go_into_ddb = 1; 1132#endif /* DDB */ 1133 goto out; 1134 } 1135 MPASS(!mtx_owned(&w_mtx)); 1136 mtx_lock_spin_flags(&w_mtx, MTX_QUIET); 1137 /* 1138 * If we have a known higher number just say ok 1139 */ 1140 if (witness_watch > 1 && w->w_level > w1->w_level) { 1141 mtx_unlock_spin_flags(&w_mtx, MTX_QUIET); 1142 goto out; 1143 } 1144 if (isitmydescendant(m1->mtx_witness, w)) { 1145 mtx_unlock_spin_flags(&w_mtx, MTX_QUIET); 1146 goto out; 1147 } 1148 for (i = 0; m1 != NULL; m1 = LIST_NEXT(m1, mtx_held), i++) { 1149 1150 MPASS(i < 200); 1151 w1 = m1->mtx_witness; 1152 if (isitmydescendant(w, w1)) { 1153 mtx_unlock_spin_flags(&w_mtx, MTX_QUIET); 1154 if (blessed(w, w1)) 1155 goto out; 1156 if (m1 == &Giant) { 1157 if (w1->w_Giant_squawked) 1158 goto out; 1159 else 1160 w1->w_Giant_squawked = 1; 1161 } else { 1162 if (w1->w_other_squawked) 1163 goto out; 1164 else 1165 w1->w_other_squawked = 1; 1166 } 1167 printf("lock order reversal\n"); 1168 printf(" 1st %s last acquired @ %s:%d\n", 1169 w->w_description, w->w_file, w->w_line); 1170 printf(" 2nd %p %s @ %s:%d\n", 1171 m1, w1->w_description, w1->w_file, w1->w_line); 1172 printf(" 3rd %p %s @ %s:%d\n", 1173 m, w->w_description, file, line); 1174#ifdef DDB 1175 go_into_ddb = 1; 1176#endif /* DDB */ 1177 goto out; 1178 } 1179 } 1180 m1 = LIST_FIRST(&p->p_heldmtx); 1181 if (!itismychild(m1->mtx_witness, w)) 1182 mtx_unlock_spin_flags(&w_mtx, MTX_QUIET); 1183 1184out: 1185#ifdef DDB 1186 if (witness_ddb && go_into_ddb) 1187 Debugger("witness_enter"); 1188#endif /* DDB */ 1189 w->w_file = file; 1190 w->w_line = line; 1191 m->mtx_line = line; 1192 m->mtx_file = file; 1193 1194 /* 1195 * If this pays off it likely means that a mutex being witnessed 1196 * is acquired in hardclock. Put it in the ignore list. It is 1197 * likely not the mutex this assert fails on. 1198 */ 1199 MPASS(m->mtx_held.le_prev == NULL); 1200 LIST_INSERT_HEAD(&p->p_heldmtx, (struct mtx*)m, mtx_held); 1201} 1202 1203void 1204witness_try_enter(struct mtx *m, int flags, const char *file, int line) 1205{ 1206 struct proc *p; 1207 struct witness *w = m->mtx_witness; 1208 1209 if (witness_cold) 1210 return; 1211 if (panicstr) 1212 return; 1213 if (flags & MTX_SPIN) { 1214 if ((m->mtx_flags & MTX_SPIN) == 0) 1215 panic("mutex_try_enter: " 1216 "MTX_SPIN on MTX_DEF mutex %s @ %s:%d", 1217 m->mtx_description, file, line); 1218 if (mtx_recursed(m)) { 1219 if ((m->mtx_flags & MTX_RECURSE) == 0) 1220 panic("mutex_try_enter: recursion on" 1221 " non-recursive mutex %s @ %s:%d", 1222 m->mtx_description, file, line); 1223 return; 1224 } 1225 mtx_lock_spin_flags(&w_mtx, MTX_QUIET); 1226 PCPU_SET(witness_spin_check, 1227 PCPU_GET(witness_spin_check) | w->w_level); 1228 mtx_unlock_spin_flags(&w_mtx, MTX_QUIET); 1229 w->w_file = file; 1230 w->w_line = line; 1231 m->mtx_line = line; 1232 m->mtx_file = file; 1233 return; 1234 } 1235 1236 if ((m->mtx_flags & MTX_SPIN) != 0) 1237 panic("mutex_try_enter: MTX_DEF on MTX_SPIN mutex %s @ %s:%d", 1238 m->mtx_description, file, line); 1239 1240 if (mtx_recursed(m)) { 1241 if ((m->mtx_flags & MTX_RECURSE) == 0) 1242 panic("mutex_try_enter: recursion on non-recursive" 1243 " mutex %s @ %s:%d", m->mtx_description, file, 1244 line); 1245 return; 1246 } 1247 w->w_file = file; 1248 w->w_line = line; 1249 m->mtx_line = line; 1250 m->mtx_file = file; 1251 p = curproc; 1252 MPASS(m->mtx_held.le_prev == NULL); 1253 LIST_INSERT_HEAD(&p->p_heldmtx, (struct mtx*)m, mtx_held); 1254} 1255 1256void 1257witness_exit(struct mtx *m, int flags, const char *file, int line) 1258{ 1259 struct witness *w; 1260 1261 if (witness_cold || m->mtx_witness == NULL || panicstr) 1262 return; 1263 w = m->mtx_witness; 1264 1265 if (flags & MTX_SPIN) { 1266 if ((m->mtx_flags & MTX_SPIN) == 0) 1267 panic("mutex_exit: MTX_SPIN on MTX_DEF mutex %s @" 1268 " %s:%d", m->mtx_description, file, line); 1269 if (mtx_recursed(m)) { 1270 if ((m->mtx_flags & MTX_RECURSE) == 0) 1271 panic("mutex_exit: recursion on non-recursive" 1272 " mutex %s @ %s:%d", m->mtx_description, 1273 file, line); 1274 return; 1275 } 1276 mtx_lock_spin_flags(&w_mtx, MTX_QUIET); 1277 PCPU_SET(witness_spin_check, 1278 PCPU_GET(witness_spin_check) & ~w->w_level); 1279 mtx_unlock_spin_flags(&w_mtx, MTX_QUIET); 1280 return; 1281 } 1282 if ((m->mtx_flags & MTX_SPIN) != 0) 1283 panic("mutex_exit: MTX_DEF on MTX_SPIN mutex %s @ %s:%d", 1284 m->mtx_description, file, line); 1285 1286 if (mtx_recursed(m)) { 1287 if ((m->mtx_flags & MTX_RECURSE) == 0) 1288 panic("mutex_exit: recursion on non-recursive" 1289 " mutex %s @ %s:%d", m->mtx_description, 1290 file, line); 1291 return; 1292 } 1293 1294 if ((flags & MTX_NOSWITCH) == 0 && !mtx_legal2block() && !cold) 1295 panic("switchable mtx_unlock() of %s when not legal @ %s:%d", 1296 m->mtx_description, file, line); 1297 LIST_REMOVE(m, mtx_held); 1298 m->mtx_held.le_prev = NULL; 1299} 1300 1301int 1302witness_sleep(int check_only, struct mtx *mtx, const char *file, int line) 1303{ 1304 struct mtx *m; 1305 struct proc *p; 1306 char **sleep; 1307 int n = 0; 1308 1309 KASSERT(!witness_cold, ("%s: witness_cold\n", __FUNCTION__)); 1310 p = curproc; 1311 LIST_FOREACH(m, &p->p_heldmtx, mtx_held) { 1312 if (m == mtx) 1313 continue; 1314 for (sleep = sleep_list; *sleep!= NULL; sleep++) 1315 if (strcmp(m->mtx_description, *sleep) == 0) 1316 goto next; 1317 if (n == 0) 1318 printf("Whee!\n"); 1319 printf("%s:%d: %s with \"%s\" locked from %s:%d\n", 1320 file, line, check_only ? "could sleep" : "sleeping", 1321 m->mtx_description, 1322 m->mtx_witness->w_file, m->mtx_witness->w_line); 1323 n++; 1324 next: 1325 } 1326#ifdef DDB 1327 if (witness_ddb && n) 1328 Debugger("witness_sleep"); 1329#endif /* DDB */ 1330 return (n); 1331} 1332 1333static struct witness * 1334enroll(const char *description, int flag) 1335{ 1336 int i; 1337 struct witness *w, *w1; 1338 char **ignore; 1339 char **order; 1340 1341 if (!witness_watch) 1342 return (NULL); 1343 for (ignore = ignore_list; *ignore != NULL; ignore++) 1344 if (strcmp(description, *ignore) == 0) 1345 return (NULL); 1346 1347 if (w_inited == 0) { 1348 mtx_init(&w_mtx, "witness lock", MTX_SPIN); 1349 for (i = 0; i < WITNESS_COUNT; i++) { 1350 w = &w_data[i]; 1351 witness_free(w); 1352 } 1353 w_inited = 1; 1354 for (order = order_list; *order != NULL; order++) { 1355 w = enroll(*order, MTX_DEF); 1356 w->w_file = "order list"; 1357 for (order++; *order != NULL; order++) { 1358 w1 = enroll(*order, MTX_DEF); 1359 w1->w_file = "order list"; 1360 itismychild(w, w1); 1361 w = w1; 1362 } 1363 } 1364 } 1365 if ((flag & MTX_SPIN) && witness_skipspin) 1366 return (NULL); 1367 mtx_lock_spin_flags(&w_mtx, MTX_QUIET); 1368 for (w = w_all; w; w = w->w_next) { 1369 if (strcmp(description, w->w_description) == 0) { 1370 mtx_unlock_spin_flags(&w_mtx, MTX_QUIET); 1371 return (w); 1372 } 1373 } 1374 if ((w = witness_get()) == NULL) 1375 return (NULL); 1376 w->w_next = w_all; 1377 w_all = w; 1378 w->w_description = description; 1379 mtx_unlock_spin_flags(&w_mtx, MTX_QUIET); 1380 if (flag & MTX_SPIN) { 1381 w->w_spin = 1; 1382 1383 i = 1; 1384 for (order = spin_order_list; *order != NULL; order++) { 1385 if (strcmp(description, *order) == 0) 1386 break; 1387 i <<= 1; 1388 } 1389 if (*order == NULL) 1390 panic("spin lock %s not in order list", description); 1391 w->w_level = i; 1392 } 1393 1394 return (w); 1395} 1396 1397static int 1398itismychild(struct witness *parent, struct witness *child) 1399{ 1400 static int recursed; 1401 1402 /* 1403 * Insert "child" after "parent" 1404 */ 1405 while (parent->w_morechildren) 1406 parent = parent->w_morechildren; 1407 1408 if (parent->w_childcnt == WITNESS_NCHILDREN) { 1409 if ((parent->w_morechildren = witness_get()) == NULL) 1410 return (1); 1411 parent = parent->w_morechildren; 1412 } 1413 MPASS(child != NULL); 1414 parent->w_children[parent->w_childcnt++] = child; 1415 /* 1416 * now prune whole tree 1417 */ 1418 if (recursed) 1419 return (0); 1420 recursed = 1; 1421 for (child = w_all; child != NULL; child = child->w_next) { 1422 for (parent = w_all; parent != NULL; 1423 parent = parent->w_next) { 1424 if (!isitmychild(parent, child)) 1425 continue; 1426 removechild(parent, child); 1427 if (isitmydescendant(parent, child)) 1428 continue; 1429 itismychild(parent, child); 1430 } 1431 } 1432 recursed = 0; 1433 witness_levelall(); 1434 return (0); 1435} 1436 1437static void 1438removechild(struct witness *parent, struct witness *child) 1439{ 1440 struct witness *w, *w1; 1441 int i; 1442 1443 for (w = parent; w != NULL; w = w->w_morechildren) 1444 for (i = 0; i < w->w_childcnt; i++) 1445 if (w->w_children[i] == child) 1446 goto found; 1447 return; 1448found: 1449 for (w1 = w; w1->w_morechildren != NULL; w1 = w1->w_morechildren) 1450 continue; 1451 w->w_children[i] = w1->w_children[--w1->w_childcnt]; 1452 MPASS(w->w_children[i] != NULL); 1453 1454 if (w1->w_childcnt != 0) 1455 return; 1456 1457 if (w1 == parent) 1458 return; 1459 for (w = parent; w->w_morechildren != w1; w = w->w_morechildren) 1460 continue; 1461 w->w_morechildren = 0; 1462 witness_free(w1); 1463} 1464 1465static int 1466isitmychild(struct witness *parent, struct witness *child) 1467{ 1468 struct witness *w; 1469 int i; 1470 1471 for (w = parent; w != NULL; w = w->w_morechildren) { 1472 for (i = 0; i < w->w_childcnt; i++) { 1473 if (w->w_children[i] == child) 1474 return (1); 1475 } 1476 } 1477 return (0); 1478} 1479 1480static int 1481isitmydescendant(struct witness *parent, struct witness *child) 1482{ 1483 struct witness *w; 1484 int i; 1485 int j; 1486 1487 for (j = 0, w = parent; w != NULL; w = w->w_morechildren, j++) { 1488 MPASS(j < 1000); 1489 for (i = 0; i < w->w_childcnt; i++) { 1490 if (w->w_children[i] == child) 1491 return (1); 1492 } 1493 for (i = 0; i < w->w_childcnt; i++) { 1494 if (isitmydescendant(w->w_children[i], child)) 1495 return (1); 1496 } 1497 } 1498 return (0); 1499} 1500 1501void 1502witness_levelall (void) 1503{ 1504 struct witness *w, *w1; 1505 1506 for (w = w_all; w; w = w->w_next) 1507 if (!(w->w_spin)) 1508 w->w_level = 0; 1509 for (w = w_all; w; w = w->w_next) { 1510 if (w->w_spin) 1511 continue; 1512 for (w1 = w_all; w1; w1 = w1->w_next) { 1513 if (isitmychild(w1, w)) 1514 break; 1515 } 1516 if (w1 != NULL) 1517 continue; 1518 witness_leveldescendents(w, 0); 1519 } 1520} 1521 1522static void 1523witness_leveldescendents(struct witness *parent, int level) 1524{ 1525 int i; 1526 struct witness *w; 1527 1528 if (parent->w_level < level) 1529 parent->w_level = level; 1530 level++; 1531 for (w = parent; w != NULL; w = w->w_morechildren) 1532 for (i = 0; i < w->w_childcnt; i++) 1533 witness_leveldescendents(w->w_children[i], level); 1534} 1535 1536static void 1537witness_displaydescendants(void(*prnt)(const char *fmt, ...), 1538 struct witness *parent) 1539{ 1540 struct witness *w; 1541 int i; 1542 int level; 1543 1544 level = parent->w_spin ? ffs(parent->w_level) : parent->w_level; 1545 1546 prnt("%d", level); 1547 if (level < 10) 1548 prnt(" "); 1549 for (i = 0; i < level; i++) 1550 prnt(" "); 1551 prnt("%s", parent->w_description); 1552 if (parent->w_file != NULL) 1553 prnt(" -- last acquired @ %s:%d\n", parent->w_file, 1554 parent->w_line); 1555 1556 for (w = parent; w != NULL; w = w->w_morechildren) 1557 for (i = 0; i < w->w_childcnt; i++) 1558 witness_displaydescendants(prnt, w->w_children[i]); 1559 } 1560 1561static int 1562dup_ok(struct witness *w) 1563{ 1564 char **dup; 1565 1566 for (dup = dup_list; *dup!= NULL; dup++) 1567 if (strcmp(w->w_description, *dup) == 0) 1568 return (1); 1569 return (0); 1570} 1571 1572static int 1573blessed(struct witness *w1, struct witness *w2) 1574{ 1575 int i; 1576 struct witness_blessed *b; 1577 1578 for (i = 0; i < blessed_count; i++) { 1579 b = &blessed_list[i]; 1580 if (strcmp(w1->w_description, b->b_lock1) == 0) { 1581 if (strcmp(w2->w_description, b->b_lock2) == 0) 1582 return (1); 1583 continue; 1584 } 1585 if (strcmp(w1->w_description, b->b_lock2) == 0) 1586 if (strcmp(w2->w_description, b->b_lock1) == 0) 1587 return (1); 1588 } 1589 return (0); 1590} 1591 1592static struct witness * 1593witness_get() 1594{ 1595 struct witness *w; 1596 1597 if ((w = w_free) == NULL) { 1598 witness_dead = 1; 1599 mtx_unlock_spin_flags(&w_mtx, MTX_QUIET); 1600 printf("witness exhausted\n"); 1601 return (NULL); 1602 } 1603 w_free = w->w_next; 1604 bzero(w, sizeof(*w)); 1605 return (w); 1606} 1607 1608static void 1609witness_free(struct witness *w) 1610{ 1611 w->w_next = w_free; 1612 w_free = w; 1613} 1614 1615int 1616witness_list(struct proc *p) 1617{ 1618 struct mtx *m; 1619 int nheld; 1620 1621 KASSERT(!witness_cold, ("%s: witness_cold\n", __FUNCTION__)); 1622 nheld = 0; 1623 LIST_FOREACH(m, &p->p_heldmtx, mtx_held) { 1624 printf("\t\"%s\" (%p) locked at %s:%d\n", 1625 m->mtx_description, m, 1626 m->mtx_witness->w_file, m->mtx_witness->w_line); 1627 nheld++; 1628 } 1629 1630 return (nheld); 1631} 1632 1633#ifdef DDB 1634 1635DB_SHOW_COMMAND(mutexes, db_witness_list) 1636{ 1637 1638 witness_list(curproc); 1639} 1640 1641DB_SHOW_COMMAND(witness, db_witness_display) 1642{ 1643 1644 witness_display(db_printf); 1645} 1646#endif 1647 1648void 1649witness_save(struct mtx *m, const char **filep, int *linep) 1650{ 1651 1652 KASSERT(!witness_cold, ("%s: witness_cold\n", __FUNCTION__)); 1653 if (m->mtx_witness == NULL) 1654 return; 1655 1656 *filep = m->mtx_witness->w_file; 1657 *linep = m->mtx_witness->w_line; 1658} 1659 1660void 1661witness_restore(struct mtx *m, const char *file, int line) 1662{ 1663 1664 KASSERT(!witness_cold, ("%s: witness_cold\n", __FUNCTION__)); 1665 if (m->mtx_witness == NULL) 1666 return; 1667 1668 m->mtx_witness->w_file = file; 1669 m->mtx_witness->w_line = line; 1670} 1671 1672#endif /* WITNESS */ 1673