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