subr_witness.c revision 73205
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 73205 2001-02-28 02:53:44Z 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 propagate_priority(p); 430 431 if ((opts & MTX_QUIET) == 0) 432 CTR3(KTR_LOCK, 433 "_mtx_lock_sleep: p %p blocked on [%p] %s", p, m, 434 m->mtx_description); 435 436 mi_switch(); 437 438 if ((opts & MTX_QUIET) == 0) 439 CTR3(KTR_LOCK, 440 "_mtx_lock_sleep: p %p free from blocked on [%p] %s", 441 p, m, m->mtx_description); 442 443 mtx_unlock_spin(&sched_lock); 444 } 445 446 return; 447} 448 449/* 450 * _mtx_lock_spin: the tougher part of acquiring an MTX_SPIN lock. 451 * 452 * This is only called if we need to actually spin for the lock. Recursion 453 * is handled inline. 454 */ 455void 456_mtx_lock_spin(struct mtx *m, int opts, u_int mtx_intr, const char *file, 457 int line) 458{ 459 int i = 0; 460 461 if ((opts & MTX_QUIET) == 0) 462 CTR1(KTR_LOCK, "_mtx_lock_spin: %p spinning", m); 463 464 for (;;) { 465 if (_obtain_lock(m, curproc)) 466 break; 467 468 while (m->mtx_lock != MTX_UNOWNED) { 469 if (i++ < 1000000) 470 continue; 471 if (i++ < 6000000) 472 DELAY(1); 473#ifdef DDB 474 else if (!db_active) 475#else 476 else 477#endif 478 panic("spin lock %s held by %p for > 5 seconds", 479 m->mtx_description, (void *)m->mtx_lock); 480 } 481 } 482 483 m->mtx_saveintr = mtx_intr; 484 if ((opts & MTX_QUIET) == 0) 485 CTR1(KTR_LOCK, "_mtx_lock_spin: %p spin done", m); 486 487 return; 488} 489 490/* 491 * _mtx_unlock_sleep: the tougher part of releasing an MTX_DEF lock. 492 * 493 * We are only called here if the lock is recursed or contested (i.e. we 494 * need to wake up a blocked thread). 495 */ 496void 497_mtx_unlock_sleep(struct mtx *m, int opts, const char *file, int line) 498{ 499 struct proc *p, *p1; 500 struct mtx *m1; 501 int pri; 502 503 p = curproc; 504 MPASS4(mtx_owned(m), "mtx_owned(mpp)", file, line); 505 506 if (mtx_recursed(m)) { 507 if (--(m->mtx_recurse) == 0) 508 atomic_clear_ptr(&m->mtx_lock, MTX_RECURSED); 509 if ((opts & MTX_QUIET) == 0) 510 CTR1(KTR_LOCK, "_mtx_unlock_sleep: %p unrecurse", m); 511 return; 512 } 513 514 mtx_lock_spin(&sched_lock); 515 if ((opts & MTX_QUIET) == 0) 516 CTR1(KTR_LOCK, "_mtx_unlock_sleep: %p contested", m); 517 518 p1 = TAILQ_FIRST(&m->mtx_blocked); 519 MPASS(p->p_magic == P_MAGIC); 520 MPASS(p1->p_magic == P_MAGIC); 521 522 TAILQ_REMOVE(&m->mtx_blocked, p1, p_procq); 523 524 if (TAILQ_EMPTY(&m->mtx_blocked)) { 525 LIST_REMOVE(m, mtx_contested); 526 _release_lock_quick(m); 527 if ((opts & MTX_QUIET) == 0) 528 CTR1(KTR_LOCK, "_mtx_unlock_sleep: %p not held", m); 529 } else 530 atomic_store_rel_ptr(&m->mtx_lock, (void *)MTX_CONTESTED); 531 532 pri = PRI_MAX; 533 LIST_FOREACH(m1, &p->p_contested, mtx_contested) { 534 int cp = TAILQ_FIRST(&m1->mtx_blocked)->p_pri.pri_level; 535 if (cp < pri) 536 pri = cp; 537 } 538 539 if (pri > p->p_pri.pri_native) 540 pri = p->p_pri.pri_native; 541 SET_PRIO(p, pri); 542 543 if ((opts & MTX_QUIET) == 0) 544 CTR2(KTR_LOCK, "_mtx_unlock_sleep: %p contested setrunqueue %p", 545 m, p1); 546 547 p1->p_blocked = NULL; 548 p1->p_stat = SRUN; 549 setrunqueue(p1); 550 551 if ((opts & MTX_NOSWITCH) == 0 && p1->p_pri.pri_level < pri) { 552#ifdef notyet 553 if (p->p_ithd != NULL) { 554 struct ithd *it = p->p_ithd; 555 556 if (it->it_interrupted) { 557 if ((opts & MTX_QUIET) == 0) 558 CTR2(KTR_LOCK, 559 "_mtx_unlock_sleep: %p interrupted %p", 560 it, it->it_interrupted); 561 intr_thd_fixup(it); 562 } 563 } 564#endif 565 setrunqueue(p); 566 if ((opts & MTX_QUIET) == 0) 567 CTR2(KTR_LOCK, 568 "_mtx_unlock_sleep: %p switching out lock=%p", m, 569 (void *)m->mtx_lock); 570 571 mi_switch(); 572 if ((opts & MTX_QUIET) == 0) 573 CTR2(KTR_LOCK, "_mtx_unlock_sleep: %p resuming lock=%p", 574 m, (void *)m->mtx_lock); 575 } 576 577 mtx_unlock_spin(&sched_lock); 578 579 return; 580} 581 582/* 583 * All the unlocking of MTX_SPIN locks is done inline. 584 * See the _rel_spin_lock() macro for the details. 585 */ 586 587/* 588 * The backing function for the INVARIANTS-enabled mtx_assert() 589 */ 590#ifdef INVARIANT_SUPPORT 591void 592_mtx_assert(struct mtx *m, int what, const char *file, int line) 593{ 594 switch (what) { 595 case MA_OWNED: 596 case MA_OWNED | MA_RECURSED: 597 case MA_OWNED | MA_NOTRECURSED: 598 if (!mtx_owned(m)) 599 panic("mutex %s not owned at %s:%d", 600 m->mtx_description, file, line); 601 if (mtx_recursed(m)) { 602 if ((what & MA_NOTRECURSED) != 0) 603 panic("mutex %s recursed at %s:%d", 604 m->mtx_description, file, line); 605 } else if ((what & MA_RECURSED) != 0) { 606 panic("mutex %s unrecursed at %s:%d", 607 m->mtx_description, file, line); 608 } 609 break; 610 case MA_NOTOWNED: 611 if (mtx_owned(m)) 612 panic("mutex %s owned at %s:%d", 613 m->mtx_description, file, line); 614 break; 615 default: 616 panic("unknown mtx_assert at %s:%d", file, line); 617 } 618} 619#endif 620 621/* 622 * The MUTEX_DEBUG-enabled mtx_validate() 623 */ 624#define MV_DESTROY 0 /* validate before destory */ 625#define MV_INIT 1 /* validate before init */ 626 627#ifdef MUTEX_DEBUG 628 629int mtx_validate __P((struct mtx *, int)); 630 631int 632mtx_validate(struct mtx *m, int when) 633{ 634 struct mtx *mp; 635 int i; 636 int retval = 0; 637 638#ifdef WITNESS 639 if (witness_cold) 640 return 0; 641#endif 642 if (m == &all_mtx || cold) 643 return 0; 644 645 mtx_lock(&all_mtx); 646/* 647 * XXX - When kernacc() is fixed on the alpha to handle K0_SEG memory properly 648 * we can re-enable the kernacc() checks. 649 */ 650#ifndef __alpha__ 651 MPASS(kernacc((caddr_t)all_mtx.mtx_next, sizeof(uintptr_t), 652 VM_PROT_READ) == 1); 653#endif 654 MPASS(all_mtx.mtx_next->mtx_prev == &all_mtx); 655 for (i = 0, mp = all_mtx.mtx_next; mp != &all_mtx; mp = mp->mtx_next) { 656#ifndef __alpha__ 657 if (kernacc((caddr_t)mp->mtx_next, sizeof(uintptr_t), 658 VM_PROT_READ) != 1) { 659 panic("mtx_validate: mp=%p mp->mtx_next=%p", 660 mp, mp->mtx_next); 661 } 662#endif 663 i++; 664 if (i > mtx_cur_cnt) { 665 panic("mtx_validate: too many in chain, known=%d\n", 666 mtx_cur_cnt); 667 } 668 } 669 MPASS(i == mtx_cur_cnt); 670 switch (when) { 671 case MV_DESTROY: 672 for (mp = all_mtx.mtx_next; mp != &all_mtx; mp = mp->mtx_next) 673 if (mp == m) 674 break; 675 MPASS(mp == m); 676 break; 677 case MV_INIT: 678 for (mp = all_mtx.mtx_next; mp != &all_mtx; mp = mp->mtx_next) 679 if (mp == m) { 680 /* 681 * Not good. This mutex already exists. 682 */ 683 printf("re-initing existing mutex %s\n", 684 m->mtx_description); 685 MPASS(m->mtx_lock == MTX_UNOWNED); 686 retval = 1; 687 } 688 } 689 mtx_unlock(&all_mtx); 690 return (retval); 691} 692#endif 693 694/* 695 * Mutex initialization routine; initialize lock `m' of type contained in 696 * `opts' with options contained in `opts' and description `description.' 697 * Place on "all_mtx" queue. 698 */ 699void 700mtx_init(struct mtx *m, const char *description, int opts) 701{ 702 703 if ((opts & MTX_QUIET) == 0) 704 CTR2(KTR_LOCK, "mtx_init %p (%s)", m, description); 705 706#ifdef MUTEX_DEBUG 707 /* Diagnostic and error correction */ 708 if (mtx_validate(m, MV_INIT)) 709 return; 710#endif 711 712 bzero((void *)m, sizeof *m); 713 TAILQ_INIT(&m->mtx_blocked); 714 715#ifdef WITNESS 716 if (!witness_cold) { 717 m->mtx_debug = malloc(sizeof(struct mtx_debug), 718 M_WITNESS, M_NOWAIT | M_ZERO); 719 MPASS(m->mtx_debug != NULL); 720 } 721#endif 722 723 m->mtx_description = description; 724 m->mtx_flags = opts; 725 m->mtx_lock = MTX_UNOWNED; 726 727 /* Put on all mutex queue */ 728 mtx_lock(&all_mtx); 729 m->mtx_next = &all_mtx; 730 m->mtx_prev = all_mtx.mtx_prev; 731 m->mtx_prev->mtx_next = m; 732 all_mtx.mtx_prev = m; 733 if (++mtx_cur_cnt > mtx_max_cnt) 734 mtx_max_cnt = mtx_cur_cnt; 735 mtx_unlock(&all_mtx); 736 737#ifdef WITNESS 738 if (!witness_cold) 739 witness_init(m, opts); 740#endif 741} 742 743/* 744 * Remove lock `m' from all_mtx queue. 745 */ 746void 747mtx_destroy(struct mtx *m) 748{ 749 750#ifdef WITNESS 751 KASSERT(!witness_cold, ("%s: Cannot destroy while still cold\n", 752 __FUNCTION__)); 753#endif 754 755 CTR2(KTR_LOCK, "mtx_destroy %p (%s)", m, m->mtx_description); 756 757#ifdef MUTEX_DEBUG 758 if (m->mtx_next == NULL) 759 panic("mtx_destroy: %p (%s) already destroyed", 760 m, m->mtx_description); 761 762 if (!mtx_owned(m)) { 763 MPASS(m->mtx_lock == MTX_UNOWNED); 764 } else { 765 MPASS((m->mtx_lock & (MTX_RECURSED|MTX_CONTESTED)) == 0); 766 } 767 768 /* diagnostic */ 769 mtx_validate(m, MV_DESTROY); 770#endif 771 772#ifdef WITNESS 773 if (m->mtx_witness) 774 witness_destroy(m); 775#endif /* WITNESS */ 776 777 /* Remove from the all mutex queue */ 778 mtx_lock(&all_mtx); 779 m->mtx_next->mtx_prev = m->mtx_prev; 780 m->mtx_prev->mtx_next = m->mtx_next; 781 782#ifdef MUTEX_DEBUG 783 m->mtx_next = m->mtx_prev = NULL; 784#endif 785 786#ifdef WITNESS 787 free(m->mtx_debug, M_WITNESS); 788 m->mtx_debug = NULL; 789#endif 790 791 mtx_cur_cnt--; 792 mtx_unlock(&all_mtx); 793} 794 795 796/* 797 * The WITNESS-enabled diagnostic code. 798 */ 799#ifdef WITNESS 800static void 801witness_fixup(void *dummy __unused) 802{ 803 struct mtx *mp; 804 805 /* 806 * We have to release Giant before initializing its witness 807 * structure so that WITNESS doesn't get confused. 808 */ 809 mtx_unlock(&Giant); 810 mtx_assert(&Giant, MA_NOTOWNED); 811 812 mtx_lock(&all_mtx); 813 814 /* Iterate through all mutexes and finish up mutex initialization. */ 815 for (mp = all_mtx.mtx_next; mp != &all_mtx; mp = mp->mtx_next) { 816 817 mp->mtx_debug = malloc(sizeof(struct mtx_debug), 818 M_WITNESS, M_NOWAIT | M_ZERO); 819 MPASS(mp->mtx_debug != NULL); 820 821 witness_init(mp, mp->mtx_flags); 822 } 823 mtx_unlock(&all_mtx); 824 825 /* Mark the witness code as being ready for use. */ 826 atomic_store_rel_int(&witness_cold, 0); 827 828 mtx_lock(&Giant); 829} 830SYSINIT(wtnsfxup, SI_SUB_MUTEX, SI_ORDER_FIRST, witness_fixup, NULL) 831 832#define WITNESS_COUNT 200 833#define WITNESS_NCHILDREN 2 834 835int witness_watch = 1; 836 837struct witness { 838 struct witness *w_next; 839 const char *w_description; 840 const char *w_file; 841 int w_line; 842 struct witness *w_morechildren; 843 u_char w_childcnt; 844 u_char w_Giant_squawked:1; 845 u_char w_other_squawked:1; 846 u_char w_same_squawked:1; 847 u_char w_spin:1; /* MTX_SPIN type mutex. */ 848 u_int w_level; 849 struct witness *w_children[WITNESS_NCHILDREN]; 850}; 851 852struct witness_blessed { 853 char *b_lock1; 854 char *b_lock2; 855}; 856 857#ifdef DDB 858/* 859 * When DDB is enabled and witness_ddb is set to 1, it will cause the system to 860 * drop into kdebug() when: 861 * - a lock heirarchy violation occurs 862 * - locks are held when going to sleep. 863 */ 864int witness_ddb; 865#ifdef WITNESS_DDB 866TUNABLE_INT_DECL("debug.witness_ddb", 1, witness_ddb); 867#else 868TUNABLE_INT_DECL("debug.witness_ddb", 0, witness_ddb); 869#endif 870SYSCTL_INT(_debug, OID_AUTO, witness_ddb, CTLFLAG_RW, &witness_ddb, 0, ""); 871#endif /* DDB */ 872 873int witness_skipspin; 874#ifdef WITNESS_SKIPSPIN 875TUNABLE_INT_DECL("debug.witness_skipspin", 1, witness_skipspin); 876#else 877TUNABLE_INT_DECL("debug.witness_skipspin", 0, witness_skipspin); 878#endif 879SYSCTL_INT(_debug, OID_AUTO, witness_skipspin, CTLFLAG_RD, &witness_skipspin, 0, 880 ""); 881 882/* 883 * Witness-enabled globals 884 */ 885static struct mtx w_mtx; 886static struct witness *w_free; 887static struct witness *w_all; 888static int w_inited; 889static int witness_dead; /* fatal error, probably no memory */ 890 891static struct witness w_data[WITNESS_COUNT]; 892 893/* 894 * Internal witness routine prototypes 895 */ 896static struct witness *enroll(const char *description, int flag); 897static int itismychild(struct witness *parent, struct witness *child); 898static void removechild(struct witness *parent, struct witness *child); 899static int isitmychild(struct witness *parent, struct witness *child); 900static int isitmydescendant(struct witness *parent, struct witness *child); 901static int dup_ok(struct witness *); 902static int blessed(struct witness *, struct witness *); 903static void 904 witness_displaydescendants(void(*)(const char *fmt, ...), struct witness *); 905static void witness_leveldescendents(struct witness *parent, int level); 906static void witness_levelall(void); 907static struct witness * witness_get(void); 908static void witness_free(struct witness *m); 909 910static char *ignore_list[] = { 911 "witness lock", 912 NULL 913}; 914 915static char *spin_order_list[] = { 916#if defined(__i386__) && defined (SMP) 917 "com", 918#endif 919 "sio", 920#ifdef __i386__ 921 "cy", 922#endif 923 "ithread table lock", 924 "ithread list lock", 925 "sched lock", 926#ifdef __i386__ 927 "clk", 928#endif 929 "callout", 930 /* 931 * leaf locks 932 */ 933 "ng_node", 934 "ng_worklist", 935#ifdef SMP 936#ifdef __i386__ 937 "ap boot", 938 "imen", 939#endif 940 "smp rendezvous", 941#endif 942 NULL 943}; 944 945static char *order_list[] = { 946 "Giant", "proctree", "allproc", "process lock", "uidinfo hash", 947 "uidinfo struct", NULL, 948 NULL 949}; 950 951static char *dup_list[] = { 952 NULL 953}; 954 955static char *sleep_list[] = { 956 "Giant", 957 NULL 958}; 959 960/* 961 * Pairs of locks which have been blessed 962 * Don't complain about order problems with blessed locks 963 */ 964static struct witness_blessed blessed_list[] = { 965}; 966static int blessed_count = 967 sizeof(blessed_list) / sizeof(struct witness_blessed); 968 969static void 970witness_init(struct mtx *m, int flag) 971{ 972 m->mtx_witness = enroll(m->mtx_description, flag); 973} 974 975static void 976witness_destroy(struct mtx *m) 977{ 978 struct mtx *m1; 979 struct proc *p; 980 p = curproc; 981 LIST_FOREACH(m1, &p->p_heldmtx, mtx_held) { 982 if (m1 == m) { 983 LIST_REMOVE(m, mtx_held); 984 break; 985 } 986 } 987 return; 988 989} 990 991static void 992witness_display(void(*prnt)(const char *fmt, ...)) 993{ 994 struct witness *w, *w1; 995 int level, found; 996 997 KASSERT(!witness_cold, ("%s: witness_cold\n", __FUNCTION__)); 998 witness_levelall(); 999 1000 /* 1001 * First, handle sleep mutexes which have been acquired at least 1002 * once. 1003 */ 1004 prnt("Sleep mutexes:\n"); 1005 for (w = w_all; w; w = w->w_next) { 1006 if (w->w_file == NULL || w->w_spin) 1007 continue; 1008 for (w1 = w_all; w1; w1 = w1->w_next) { 1009 if (isitmychild(w1, w)) 1010 break; 1011 } 1012 if (w1 != NULL) 1013 continue; 1014 /* 1015 * This lock has no anscestors, display its descendants. 1016 */ 1017 witness_displaydescendants(prnt, w); 1018 } 1019 1020 /* 1021 * Now do spin mutexes which have been acquired at least once. 1022 */ 1023 prnt("\nSpin mutexes:\n"); 1024 level = 0; 1025 while (level < sizeof(spin_order_list) / sizeof(char *)) { 1026 found = 0; 1027 for (w = w_all; w; w = w->w_next) { 1028 if (w->w_file == NULL || !w->w_spin) 1029 continue; 1030 if (w->w_level == 1 << level) { 1031 witness_displaydescendants(prnt, w); 1032 level++; 1033 found = 1; 1034 } 1035 } 1036 if (found == 0) 1037 level++; 1038 } 1039 1040 /* 1041 * Finally, any mutexes which have not been acquired yet. 1042 */ 1043 prnt("\nMutexes which were never acquired:\n"); 1044 for (w = w_all; w; w = w->w_next) { 1045 if (w->w_file != NULL) 1046 continue; 1047 prnt("%s\n", w->w_description); 1048 } 1049} 1050 1051void 1052witness_enter(struct mtx *m, int flags, const char *file, int line) 1053{ 1054 struct witness *w, *w1; 1055 struct mtx *m1; 1056 struct proc *p; 1057 int i; 1058#ifdef DDB 1059 int go_into_ddb = 0; 1060#endif /* DDB */ 1061 1062 if (witness_cold || m->mtx_witness == NULL || panicstr) 1063 return; 1064 w = m->mtx_witness; 1065 p = curproc; 1066 1067 if (flags & MTX_SPIN) { 1068 if ((m->mtx_flags & MTX_SPIN) == 0) 1069 panic("mutex_enter: MTX_SPIN on MTX_DEF mutex %s @" 1070 " %s:%d", m->mtx_description, file, line); 1071 if (mtx_recursed(m)) { 1072 if ((m->mtx_flags & MTX_RECURSE) == 0) 1073 panic("mutex_enter: recursion on non-recursive" 1074 " mutex %s @ %s:%d", m->mtx_description, 1075 file, line); 1076 return; 1077 } 1078 mtx_lock_spin_flags(&w_mtx, MTX_QUIET); 1079 i = PCPU_GET(witness_spin_check); 1080 if (i != 0 && w->w_level < i) { 1081 mtx_unlock_spin_flags(&w_mtx, MTX_QUIET); 1082 panic("mutex_enter(%s:%x, MTX_SPIN) out of order @" 1083 " %s:%d already holding %s:%x", 1084 m->mtx_description, w->w_level, file, line, 1085 spin_order_list[ffs(i)-1], i); 1086 } 1087 PCPU_SET(witness_spin_check, i | w->w_level); 1088 mtx_unlock_spin_flags(&w_mtx, MTX_QUIET); 1089 w->w_file = file; 1090 w->w_line = line; 1091 m->mtx_line = line; 1092 m->mtx_file = file; 1093 return; 1094 } 1095 if ((m->mtx_flags & MTX_SPIN) != 0) 1096 panic("mutex_enter: MTX_DEF on MTX_SPIN mutex %s @ %s:%d", 1097 m->mtx_description, file, line); 1098 1099 if (mtx_recursed(m)) { 1100 if ((m->mtx_flags & MTX_RECURSE) == 0) 1101 panic("mutex_enter: recursion on non-recursive" 1102 " mutex %s @ %s:%d", m->mtx_description, 1103 file, line); 1104 return; 1105 } 1106 if (witness_dead) 1107 goto out; 1108 if (cold) 1109 goto out; 1110 1111 if (!mtx_legal2block()) 1112 panic("blockable mtx_lock() of %s when not legal @ %s:%d", 1113 m->mtx_description, file, line); 1114 /* 1115 * Is this the first mutex acquired 1116 */ 1117 if ((m1 = LIST_FIRST(&p->p_heldmtx)) == NULL) 1118 goto out; 1119 1120 if ((w1 = m1->mtx_witness) == w) { 1121 if (w->w_same_squawked || dup_ok(w)) 1122 goto out; 1123 w->w_same_squawked = 1; 1124 printf("acquring duplicate lock of same type: \"%s\"\n", 1125 m->mtx_description); 1126 printf(" 1st @ %s:%d\n", w->w_file, w->w_line); 1127 printf(" 2nd @ %s:%d\n", file, line); 1128#ifdef DDB 1129 go_into_ddb = 1; 1130#endif /* DDB */ 1131 goto out; 1132 } 1133 MPASS(!mtx_owned(&w_mtx)); 1134 mtx_lock_spin_flags(&w_mtx, MTX_QUIET); 1135 /* 1136 * If we have a known higher number just say ok 1137 */ 1138 if (witness_watch > 1 && w->w_level > w1->w_level) { 1139 mtx_unlock_spin_flags(&w_mtx, MTX_QUIET); 1140 goto out; 1141 } 1142 if (isitmydescendant(m1->mtx_witness, w)) { 1143 mtx_unlock_spin_flags(&w_mtx, MTX_QUIET); 1144 goto out; 1145 } 1146 for (i = 0; m1 != NULL; m1 = LIST_NEXT(m1, mtx_held), i++) { 1147 1148 MPASS(i < 200); 1149 w1 = m1->mtx_witness; 1150 if (isitmydescendant(w, w1)) { 1151 mtx_unlock_spin_flags(&w_mtx, MTX_QUIET); 1152 if (blessed(w, w1)) 1153 goto out; 1154 if (m1 == &Giant) { 1155 if (w1->w_Giant_squawked) 1156 goto out; 1157 else 1158 w1->w_Giant_squawked = 1; 1159 } else { 1160 if (w1->w_other_squawked) 1161 goto out; 1162 else 1163 w1->w_other_squawked = 1; 1164 } 1165 printf("lock order reversal\n"); 1166 printf(" 1st %s last acquired @ %s:%d\n", 1167 w->w_description, w->w_file, w->w_line); 1168 printf(" 2nd %p %s @ %s:%d\n", 1169 m1, w1->w_description, w1->w_file, w1->w_line); 1170 printf(" 3rd %p %s @ %s:%d\n", 1171 m, w->w_description, file, line); 1172#ifdef DDB 1173 go_into_ddb = 1; 1174#endif /* DDB */ 1175 goto out; 1176 } 1177 } 1178 m1 = LIST_FIRST(&p->p_heldmtx); 1179 if (!itismychild(m1->mtx_witness, w)) 1180 mtx_unlock_spin_flags(&w_mtx, MTX_QUIET); 1181 1182out: 1183#ifdef DDB 1184 if (witness_ddb && go_into_ddb) 1185 Debugger("witness_enter"); 1186#endif /* DDB */ 1187 w->w_file = file; 1188 w->w_line = line; 1189 m->mtx_line = line; 1190 m->mtx_file = file; 1191 1192 /* 1193 * If this pays off it likely means that a mutex being witnessed 1194 * is acquired in hardclock. Put it in the ignore list. It is 1195 * likely not the mutex this assert fails on. 1196 */ 1197 MPASS(m->mtx_held.le_prev == NULL); 1198 LIST_INSERT_HEAD(&p->p_heldmtx, (struct mtx*)m, mtx_held); 1199} 1200 1201void 1202witness_try_enter(struct mtx *m, int flags, const char *file, int line) 1203{ 1204 struct proc *p; 1205 struct witness *w = m->mtx_witness; 1206 1207 if (witness_cold) 1208 return; 1209 if (panicstr) 1210 return; 1211 if (flags & MTX_SPIN) { 1212 if ((m->mtx_flags & MTX_SPIN) == 0) 1213 panic("mutex_try_enter: " 1214 "MTX_SPIN on MTX_DEF mutex %s @ %s:%d", 1215 m->mtx_description, file, line); 1216 if (mtx_recursed(m)) { 1217 if ((m->mtx_flags & MTX_RECURSE) == 0) 1218 panic("mutex_try_enter: recursion on" 1219 " non-recursive mutex %s @ %s:%d", 1220 m->mtx_description, file, line); 1221 return; 1222 } 1223 mtx_lock_spin_flags(&w_mtx, MTX_QUIET); 1224 PCPU_SET(witness_spin_check, 1225 PCPU_GET(witness_spin_check) | w->w_level); 1226 mtx_unlock_spin_flags(&w_mtx, MTX_QUIET); 1227 w->w_file = file; 1228 w->w_line = line; 1229 m->mtx_line = line; 1230 m->mtx_file = file; 1231 return; 1232 } 1233 1234 if ((m->mtx_flags & MTX_SPIN) != 0) 1235 panic("mutex_try_enter: MTX_DEF on MTX_SPIN mutex %s @ %s:%d", 1236 m->mtx_description, file, line); 1237 1238 if (mtx_recursed(m)) { 1239 if ((m->mtx_flags & MTX_RECURSE) == 0) 1240 panic("mutex_try_enter: recursion on non-recursive" 1241 " mutex %s @ %s:%d", m->mtx_description, file, 1242 line); 1243 return; 1244 } 1245 w->w_file = file; 1246 w->w_line = line; 1247 m->mtx_line = line; 1248 m->mtx_file = file; 1249 p = curproc; 1250 MPASS(m->mtx_held.le_prev == NULL); 1251 LIST_INSERT_HEAD(&p->p_heldmtx, (struct mtx*)m, mtx_held); 1252} 1253 1254void 1255witness_exit(struct mtx *m, int flags, const char *file, int line) 1256{ 1257 struct witness *w; 1258 1259 if (witness_cold || m->mtx_witness == NULL || panicstr) 1260 return; 1261 w = m->mtx_witness; 1262 1263 if (flags & MTX_SPIN) { 1264 if ((m->mtx_flags & MTX_SPIN) == 0) 1265 panic("mutex_exit: MTX_SPIN on MTX_DEF mutex %s @" 1266 " %s:%d", m->mtx_description, file, line); 1267 if (mtx_recursed(m)) { 1268 if ((m->mtx_flags & MTX_RECURSE) == 0) 1269 panic("mutex_exit: recursion on non-recursive" 1270 " mutex %s @ %s:%d", m->mtx_description, 1271 file, line); 1272 return; 1273 } 1274 mtx_lock_spin_flags(&w_mtx, MTX_QUIET); 1275 PCPU_SET(witness_spin_check, 1276 PCPU_GET(witness_spin_check) & ~w->w_level); 1277 mtx_unlock_spin_flags(&w_mtx, MTX_QUIET); 1278 return; 1279 } 1280 if ((m->mtx_flags & MTX_SPIN) != 0) 1281 panic("mutex_exit: MTX_DEF on MTX_SPIN mutex %s @ %s:%d", 1282 m->mtx_description, file, line); 1283 1284 if (mtx_recursed(m)) { 1285 if ((m->mtx_flags & MTX_RECURSE) == 0) 1286 panic("mutex_exit: recursion on non-recursive" 1287 " mutex %s @ %s:%d", m->mtx_description, 1288 file, line); 1289 return; 1290 } 1291 1292 if ((flags & MTX_NOSWITCH) == 0 && !mtx_legal2block() && !cold) 1293 panic("switchable mtx_unlock() of %s when not legal @ %s:%d", 1294 m->mtx_description, file, line); 1295 LIST_REMOVE(m, mtx_held); 1296 m->mtx_held.le_prev = NULL; 1297} 1298 1299int 1300witness_sleep(int check_only, struct mtx *mtx, const char *file, int line) 1301{ 1302 struct mtx *m; 1303 struct proc *p; 1304 char **sleep; 1305 int n = 0; 1306 1307 KASSERT(!witness_cold, ("%s: witness_cold\n", __FUNCTION__)); 1308 p = curproc; 1309 LIST_FOREACH(m, &p->p_heldmtx, mtx_held) { 1310 if (m == mtx) 1311 continue; 1312 for (sleep = sleep_list; *sleep!= NULL; sleep++) 1313 if (strcmp(m->mtx_description, *sleep) == 0) 1314 goto next; 1315 if (n == 0) 1316 printf("Whee!\n"); 1317 printf("%s:%d: %s with \"%s\" locked from %s:%d\n", 1318 file, line, check_only ? "could sleep" : "sleeping", 1319 m->mtx_description, 1320 m->mtx_witness->w_file, m->mtx_witness->w_line); 1321 n++; 1322 next: 1323 } 1324#ifdef DDB 1325 if (witness_ddb && n) 1326 Debugger("witness_sleep"); 1327#endif /* DDB */ 1328 return (n); 1329} 1330 1331static struct witness * 1332enroll(const char *description, int flag) 1333{ 1334 int i; 1335 struct witness *w, *w1; 1336 char **ignore; 1337 char **order; 1338 1339 if (!witness_watch) 1340 return (NULL); 1341 for (ignore = ignore_list; *ignore != NULL; ignore++) 1342 if (strcmp(description, *ignore) == 0) 1343 return (NULL); 1344 1345 if (w_inited == 0) { 1346 mtx_init(&w_mtx, "witness lock", MTX_SPIN); 1347 for (i = 0; i < WITNESS_COUNT; i++) { 1348 w = &w_data[i]; 1349 witness_free(w); 1350 } 1351 w_inited = 1; 1352 for (order = order_list; *order != NULL; order++) { 1353 w = enroll(*order, MTX_DEF); 1354 w->w_file = "order list"; 1355 for (order++; *order != NULL; order++) { 1356 w1 = enroll(*order, MTX_DEF); 1357 w1->w_file = "order list"; 1358 itismychild(w, w1); 1359 w = w1; 1360 } 1361 } 1362 } 1363 if ((flag & MTX_SPIN) && witness_skipspin) 1364 return (NULL); 1365 mtx_lock_spin_flags(&w_mtx, MTX_QUIET); 1366 for (w = w_all; w; w = w->w_next) { 1367 if (strcmp(description, w->w_description) == 0) { 1368 mtx_unlock_spin_flags(&w_mtx, MTX_QUIET); 1369 return (w); 1370 } 1371 } 1372 if ((w = witness_get()) == NULL) 1373 return (NULL); 1374 w->w_next = w_all; 1375 w_all = w; 1376 w->w_description = description; 1377 mtx_unlock_spin_flags(&w_mtx, MTX_QUIET); 1378 if (flag & MTX_SPIN) { 1379 w->w_spin = 1; 1380 1381 i = 1; 1382 for (order = spin_order_list; *order != NULL; order++) { 1383 if (strcmp(description, *order) == 0) 1384 break; 1385 i <<= 1; 1386 } 1387 if (*order == NULL) 1388 panic("spin lock %s not in order list", description); 1389 w->w_level = i; 1390 } 1391 1392 return (w); 1393} 1394 1395static int 1396itismychild(struct witness *parent, struct witness *child) 1397{ 1398 static int recursed; 1399 1400 /* 1401 * Insert "child" after "parent" 1402 */ 1403 while (parent->w_morechildren) 1404 parent = parent->w_morechildren; 1405 1406 if (parent->w_childcnt == WITNESS_NCHILDREN) { 1407 if ((parent->w_morechildren = witness_get()) == NULL) 1408 return (1); 1409 parent = parent->w_morechildren; 1410 } 1411 MPASS(child != NULL); 1412 parent->w_children[parent->w_childcnt++] = child; 1413 /* 1414 * now prune whole tree 1415 */ 1416 if (recursed) 1417 return (0); 1418 recursed = 1; 1419 for (child = w_all; child != NULL; child = child->w_next) { 1420 for (parent = w_all; parent != NULL; 1421 parent = parent->w_next) { 1422 if (!isitmychild(parent, child)) 1423 continue; 1424 removechild(parent, child); 1425 if (isitmydescendant(parent, child)) 1426 continue; 1427 itismychild(parent, child); 1428 } 1429 } 1430 recursed = 0; 1431 witness_levelall(); 1432 return (0); 1433} 1434 1435static void 1436removechild(struct witness *parent, struct witness *child) 1437{ 1438 struct witness *w, *w1; 1439 int i; 1440 1441 for (w = parent; w != NULL; w = w->w_morechildren) 1442 for (i = 0; i < w->w_childcnt; i++) 1443 if (w->w_children[i] == child) 1444 goto found; 1445 return; 1446found: 1447 for (w1 = w; w1->w_morechildren != NULL; w1 = w1->w_morechildren) 1448 continue; 1449 w->w_children[i] = w1->w_children[--w1->w_childcnt]; 1450 MPASS(w->w_children[i] != NULL); 1451 1452 if (w1->w_childcnt != 0) 1453 return; 1454 1455 if (w1 == parent) 1456 return; 1457 for (w = parent; w->w_morechildren != w1; w = w->w_morechildren) 1458 continue; 1459 w->w_morechildren = 0; 1460 witness_free(w1); 1461} 1462 1463static int 1464isitmychild(struct witness *parent, struct witness *child) 1465{ 1466 struct witness *w; 1467 int i; 1468 1469 for (w = parent; w != NULL; w = w->w_morechildren) { 1470 for (i = 0; i < w->w_childcnt; i++) { 1471 if (w->w_children[i] == child) 1472 return (1); 1473 } 1474 } 1475 return (0); 1476} 1477 1478static int 1479isitmydescendant(struct witness *parent, struct witness *child) 1480{ 1481 struct witness *w; 1482 int i; 1483 int j; 1484 1485 for (j = 0, w = parent; w != NULL; w = w->w_morechildren, j++) { 1486 MPASS(j < 1000); 1487 for (i = 0; i < w->w_childcnt; i++) { 1488 if (w->w_children[i] == child) 1489 return (1); 1490 } 1491 for (i = 0; i < w->w_childcnt; i++) { 1492 if (isitmydescendant(w->w_children[i], child)) 1493 return (1); 1494 } 1495 } 1496 return (0); 1497} 1498 1499void 1500witness_levelall (void) 1501{ 1502 struct witness *w, *w1; 1503 1504 for (w = w_all; w; w = w->w_next) 1505 if (!(w->w_spin)) 1506 w->w_level = 0; 1507 for (w = w_all; w; w = w->w_next) { 1508 if (w->w_spin) 1509 continue; 1510 for (w1 = w_all; w1; w1 = w1->w_next) { 1511 if (isitmychild(w1, w)) 1512 break; 1513 } 1514 if (w1 != NULL) 1515 continue; 1516 witness_leveldescendents(w, 0); 1517 } 1518} 1519 1520static void 1521witness_leveldescendents(struct witness *parent, int level) 1522{ 1523 int i; 1524 struct witness *w; 1525 1526 if (parent->w_level < level) 1527 parent->w_level = level; 1528 level++; 1529 for (w = parent; w != NULL; w = w->w_morechildren) 1530 for (i = 0; i < w->w_childcnt; i++) 1531 witness_leveldescendents(w->w_children[i], level); 1532} 1533 1534static void 1535witness_displaydescendants(void(*prnt)(const char *fmt, ...), 1536 struct witness *parent) 1537{ 1538 struct witness *w; 1539 int i; 1540 int level; 1541 1542 level = parent->w_spin ? ffs(parent->w_level) : parent->w_level; 1543 1544 prnt("%d", level); 1545 if (level < 10) 1546 prnt(" "); 1547 for (i = 0; i < level; i++) 1548 prnt(" "); 1549 prnt("%s", parent->w_description); 1550 if (parent->w_file != NULL) 1551 prnt(" -- last acquired @ %s:%d\n", parent->w_file, 1552 parent->w_line); 1553 1554 for (w = parent; w != NULL; w = w->w_morechildren) 1555 for (i = 0; i < w->w_childcnt; i++) 1556 witness_displaydescendants(prnt, w->w_children[i]); 1557 } 1558 1559static int 1560dup_ok(struct witness *w) 1561{ 1562 char **dup; 1563 1564 for (dup = dup_list; *dup!= NULL; dup++) 1565 if (strcmp(w->w_description, *dup) == 0) 1566 return (1); 1567 return (0); 1568} 1569 1570static int 1571blessed(struct witness *w1, struct witness *w2) 1572{ 1573 int i; 1574 struct witness_blessed *b; 1575 1576 for (i = 0; i < blessed_count; i++) { 1577 b = &blessed_list[i]; 1578 if (strcmp(w1->w_description, b->b_lock1) == 0) { 1579 if (strcmp(w2->w_description, b->b_lock2) == 0) 1580 return (1); 1581 continue; 1582 } 1583 if (strcmp(w1->w_description, b->b_lock2) == 0) 1584 if (strcmp(w2->w_description, b->b_lock1) == 0) 1585 return (1); 1586 } 1587 return (0); 1588} 1589 1590static struct witness * 1591witness_get() 1592{ 1593 struct witness *w; 1594 1595 if ((w = w_free) == NULL) { 1596 witness_dead = 1; 1597 mtx_unlock_spin_flags(&w_mtx, MTX_QUIET); 1598 printf("witness exhausted\n"); 1599 return (NULL); 1600 } 1601 w_free = w->w_next; 1602 bzero(w, sizeof(*w)); 1603 return (w); 1604} 1605 1606static void 1607witness_free(struct witness *w) 1608{ 1609 w->w_next = w_free; 1610 w_free = w; 1611} 1612 1613int 1614witness_list(struct proc *p) 1615{ 1616 struct mtx *m; 1617 int nheld; 1618 1619 KASSERT(!witness_cold, ("%s: witness_cold\n", __FUNCTION__)); 1620 nheld = 0; 1621 LIST_FOREACH(m, &p->p_heldmtx, mtx_held) { 1622 printf("\t\"%s\" (%p) locked at %s:%d\n", 1623 m->mtx_description, m, 1624 m->mtx_witness->w_file, m->mtx_witness->w_line); 1625 nheld++; 1626 } 1627 1628 return (nheld); 1629} 1630 1631#ifdef DDB 1632 1633DB_SHOW_COMMAND(mutexes, db_witness_list) 1634{ 1635 1636 witness_list(curproc); 1637} 1638 1639DB_SHOW_COMMAND(witness, db_witness_display) 1640{ 1641 1642 witness_display(db_printf); 1643} 1644#endif 1645 1646void 1647witness_save(struct mtx *m, const char **filep, int *linep) 1648{ 1649 1650 KASSERT(!witness_cold, ("%s: witness_cold\n", __FUNCTION__)); 1651 if (m->mtx_witness == NULL) 1652 return; 1653 1654 *filep = m->mtx_witness->w_file; 1655 *linep = m->mtx_witness->w_line; 1656} 1657 1658void 1659witness_restore(struct mtx *m, const char *file, int line) 1660{ 1661 1662 KASSERT(!witness_cold, ("%s: witness_cold\n", __FUNCTION__)); 1663 if (m->mtx_witness == NULL) 1664 return; 1665 1666 m->mtx_witness->w_file = file; 1667 m->mtx_witness->w_line = line; 1668} 1669 1670#endif /* WITNESS */ 1671