subr_turnstile.c revision 71360
1139749Simp/*- 2578Srgrimes * Copyright (c) 1998 Berkeley Software Design, Inc. All rights reserved. 3578Srgrimes * 41197Srgrimes * Redistribution and use in source and binary forms, with or without 56604Sache * modification, are permitted provided that the following conditions 61197Srgrimes * are met: 71197Srgrimes * 1. Redistributions of source code must retain the above copyright 81197Srgrimes * notice, this list of conditions and the following disclaimer. 91197Srgrimes * 2. Redistributions in binary form must reproduce the above copyright 10578Srgrimes * notice, this list of conditions and the following disclaimer in the 11578Srgrimes * documentation and/or other materials provided with the distribution. 12578Srgrimes * 3. Berkeley Software Design Inc's name may not be used to endorse or 13578Srgrimes * promote products derived from this software without specific prior 14578Srgrimes * written permission. 15578Srgrimes * 16578Srgrimes * THIS SOFTWARE IS PROVIDED BY BERKELEY SOFTWARE DESIGN INC ``AS IS'' AND 17578Srgrimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 18578Srgrimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 19578Srgrimes * ARE DISCLAIMED. IN NO EVENT SHALL BERKELEY SOFTWARE DESIGN INC BE LIABLE 20578Srgrimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 21578Srgrimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 22578Srgrimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 231197Srgrimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 24578Srgrimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 25578Srgrimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 26578Srgrimes * SUCH DAMAGE. 27578Srgrimes * 28578Srgrimes * from BSDI $Id: mutex_witness.c,v 1.1.2.20 2000/04/27 03:10:27 cp Exp $ 29578Srgrimes * and BSDI $Id: synch_machdep.c,v 2.3.2.39 2000/04/27 03:10:25 cp Exp $ 30578Srgrimes * $FreeBSD: head/sys/kern/subr_turnstile.c 71360 2001-01-22 05:56:55Z jasone $ 31578Srgrimes */ 32578Srgrimes 33578Srgrimes/* 34578Srgrimes * Main Entry: witness 35578Srgrimes * Pronunciation: 'wit-n&s 36578Srgrimes * Function: noun 37578Srgrimes * Etymology: Middle English witnesse, from Old English witnes knowledge, 38578Srgrimes * testimony, witness, from 2wit 39578Srgrimes * Date: before 12th century 40578Srgrimes * 1 : attestation of a fact or event : TESTIMONY 41578Srgrimes * 2 : one that gives evidence; specifically : one who testifies in 42578Srgrimes * a cause or before a judicial tribunal 43578Srgrimes * 3 : one asked to be present at a transaction so as to be able to 44119418Sobrien * testify to its having taken place 45119418Sobrien * 4 : one who has personal knowledge of something 46119418Sobrien * 5 a : something serving as evidence or proof : SIGN 4716322Sgpalmer * b : public affirmation by word or example of usually 48578Srgrimes * religious faith or conviction <the heroic witness to divine 492056Swollman * life -- Pilot> 502056Swollman * 6 capitalized : a member of the Jehovah's Witnesses 5161011Speter */ 522056Swollman 5324131Sbde#include "opt_ddb.h" 5460041Sphk#include "opt_witness.h" 552056Swollman 56104545Smdodd/* 5761011Speter * Cause non-inlined mtx_*() to be compiled. 583816Swollman * Must be defined early because other system headers may include mutex.h. 59104445Smdodd */ 60104445Smdodd#define _KERN_MUTEX_C_ 61104445Smdodd 627430Sbde#include <sys/param.h> 63104445Smdodd#include <sys/bus.h> 64104445Smdodd#include <sys/kernel.h> 65104445Smdodd#include <sys/malloc.h> 66104445Smdodd#include <sys/proc.h> 67578Srgrimes#include <sys/sysctl.h> 68115477Sphk#include <sys/systm.h> 698375Srgrimes#include <sys/vmmeter.h> 70104445Smdodd#include <sys/ktr.h> 71104445Smdodd 72104445Smdodd#include <machine/atomic.h> 738375Srgrimes#include <machine/bus.h> 748375Srgrimes#include <machine/clock.h> 758375Srgrimes#include <machine/cpu.h> 76578Srgrimes 772395Sache#include <ddb/ddb.h> 78578Srgrimes 79578Srgrimes#include <vm/vm.h> 8014654Sache#include <vm/vm_extern.h> 8114654Sache 8214654Sache#include <sys/mutex.h> 8314654Sache 8414654Sache/* 8514654Sache * Machine independent bits of the mutex implementation 8614654Sache */ 8714654Sache 8814654Sache#ifdef WITNESS 89578Srgrimesstruct mtx_debug { 90578Srgrimes struct witness *mtxd_witness; 91578Srgrimes LIST_ENTRY(mtx) mtxd_held; 92578Srgrimes const char *mtxd_file; 93578Srgrimes int mtxd_line; 94578Srgrimes const char *mtxd_description; 95578Srgrimes}; 961241Sjkh 971241Sjkh#define mtx_description mtx_union.mtxu_debug->mtxd_description 981241Sjkh#define mtx_held mtx_union.mtxu_debug->mtxd_held 991241Sjkh#define mtx_file mtx_union.mtxu_debug->mtxd_file 1001241Sjkh#define mtx_line mtx_union.mtxu_debug->mtxd_line 1011237Sjkh#define mtx_witness mtx_union.mtxu_debug->mtxd_witness 1022477Sache#else /* WITNESS */ 1032477Sache#define mtx_description mtx_union.mtxu_description 1044480Sache#endif /* WITNESS */ 1054480Sache 1064480Sache/* 10713874Sache * Assembly macros 10813874Sache *------------------------------------------------------------------------------ 10913874Sache */ 1104480Sache 111578Srgrimes#define _V(x) __STRING(x) 112578Srgrimes 113578Srgrimes/* 114578Srgrimes * Default, unoptimized mutex micro-operations 115578Srgrimes */ 116578Srgrimes 117578Srgrimes#ifndef _obtain_lock 118578Srgrimes/* Actually obtain mtx_lock */ 119104445Smdodd#define _obtain_lock(mp, tid) \ 12011872Sphk atomic_cmpset_acq_ptr(&(mp)->mtx_lock, (void *)MTX_UNOWNED, (tid)) 121104445Smdodd#endif 12211872Sphk 123104445Smdodd#ifndef _release_lock 124104445Smdodd/* Actually release mtx_lock */ 125104445Smdodd#define _release_lock(mp, tid) \ 126104445Smdodd atomic_cmpset_rel_ptr(&(mp)->mtx_lock, (tid), (void *)MTX_UNOWNED) 127104445Smdodd#endif 128104445Smdodd 129104445Smdodd#ifndef _release_lock_quick 130104445Smdodd/* Actually release mtx_lock quickly assuming that we own it */ 131104445Smdodd#define _release_lock_quick(mp) \ 132104445Smdodd atomic_store_rel_ptr(&(mp)->mtx_lock, (void *)MTX_UNOWNED) 133104445Smdodd#endif 134104445Smdodd 135104445Smdodd#ifndef _getlock_sleep 136104445Smdodd/* Get a sleep lock, deal with recursion inline. */ 137141031Ssobomax#define _getlock_sleep(mp, tid, type) do { \ 138141031Ssobomax if (!_obtain_lock(mp, tid)) { \ 139104445Smdodd if (((mp)->mtx_lock & MTX_FLAGMASK) != ((uintptr_t)(tid)))\ 140104445Smdodd mtx_enter_hard(mp, (type) & MTX_HARDOPTS, 0); \ 141104445Smdodd else { \ 14231016Sphk atomic_set_ptr(&(mp)->mtx_lock, MTX_RECURSED); \ 143104445Smdodd (mp)->mtx_recurse++; \ 14431016Sphk } \ 145104445Smdodd } \ 146104445Smdodd} while (0) 147104445Smdodd#endif 148104445Smdodd 149104445Smdodd#ifndef _getlock_spin_block 150104445Smdodd/* Get a spin lock, handle recursion inline (as the less common case) */ 151104445Smdodd#define _getlock_spin_block(mp, tid, type) do { \ 152104445Smdodd u_int _mtx_intr = save_intr(); \ 153104445Smdodd disable_intr(); \ 154104445Smdodd if (!_obtain_lock(mp, tid)) \ 155104445Smdodd mtx_enter_hard(mp, (type) & MTX_HARDOPTS, _mtx_intr); \ 156130585Sphk else \ 157578Srgrimes (mp)->mtx_saveintr = _mtx_intr; \ 158104445Smdodd} while (0) 159104445Smdodd#endif 160104445Smdodd 161104445Smdodd#ifndef _getlock_norecurse 162578Srgrimes/* 16337389Sjulian * Get a lock without any recursion handling. Calls the hard enter function if 164126080Sphk * we can't get it inline. 165111815Sphk */ 166111815Sphk#define _getlock_norecurse(mp, tid, type) do { \ 167111815Sphk if (!_obtain_lock(mp, tid)) \ 168111815Sphk mtx_enter_hard((mp), (type) & MTX_HARDOPTS, 0); \ 169111815Sphk} while (0) 170111815Sphk#endif 171126080Sphk 17247625Sphk#ifndef _exitlock_norecurse 17337389Sjulian/* 174578Srgrimes * Release a sleep lock assuming we haven't recursed on it, recursion is handled 175578Srgrimes * in the hard function. 176578Srgrimes */ 1776604Sache#define _exitlock_norecurse(mp, tid, type) do { \ 1786604Sache if (!_release_lock(mp, tid)) \ 1796604Sache mtx_exit_hard((mp), (type) & MTX_HARDOPTS); \ 1806604Sache} while (0) 181578Srgrimes#endif 1822477Sache 1832477Sache#ifndef _exitlock 184578Srgrimes/* 185578Srgrimes * Release a sleep lock when its likely we recursed (the code to 1862477Sache * deal with simple recursion is inline). 18710069Sjoerg */ 188578Srgrimes#define _exitlock(mp, tid, type) do { \ 189104445Smdodd if (!_release_lock(mp, tid)) { \ 190104445Smdodd if ((mp)->mtx_lock & MTX_RECURSED) { \ 191578Srgrimes if (--((mp)->mtx_recurse) == 0) \ 192104445Smdodd atomic_clear_ptr(&(mp)->mtx_lock, \ 1938876Srgrimes MTX_RECURSED); \ 194104445Smdodd } else { \ 195104445Smdodd mtx_exit_hard((mp), (type) & MTX_HARDOPTS); \ 196106490Smdodd } \ 197104445Smdodd } \ 198106490Smdodd} while (0) 199578Srgrimes#endif 200578Srgrimes 201578Srgrimes#ifndef _exitlock_spin 202104445Smdodd/* Release a spin lock (with possible recursion). */ 203578Srgrimes#define _exitlock_spin(mp) do { \ 2044480Sache if (!mtx_recursed((mp))) { \ 205104545Smdodd int _mtx_intr = (mp)->mtx_saveintr; \ 206104445Smdodd \ 207104445Smdodd _release_lock_quick(mp); \ 208104545Smdodd restore_intr(_mtx_intr); \ 209104445Smdodd } else { \ 210106490Smdodd (mp)->mtx_recurse--; \ 211578Srgrimes } \ 212578Srgrimes} while (0) 213104441Smdodd#endif 214130585Sphk 215578Srgrimes#ifdef WITNESS 216104445Smdoddstatic void witness_init(struct mtx *, int flag); 217104545Smdoddstatic void witness_destroy(struct mtx *); 2188876Srgrimesstatic void witness_display(void(*)(const char *fmt, ...)); 219104445Smdodd 2208876Srgrimes/* All mutexes in system (used for debug/panic) */ 221578Srgrimesstatic struct mtx_debug all_mtx_debug = { NULL, {NULL, NULL}, NULL, 0, 222106490Smdodd "All mutexes queue head" }; 223106490Smdoddstatic struct mtx all_mtx = { MTX_UNOWNED, 0, 0, 0, {&all_mtx_debug}, 224578Srgrimes TAILQ_HEAD_INITIALIZER(all_mtx.mtx_blocked), 225578Srgrimes { NULL, NULL }, &all_mtx, &all_mtx }; 226106490Smdodd/* 227106490Smdodd * Set to 0 once mutexes have been fully initialized so that witness code can be 228578Srgrimes * safely executed. 229104445Smdodd */ 230106490Smdoddstatic int witness_cold = 1; 231578Srgrimes#else /* WITNESS */ 232106490Smdodd/* All mutexes in system (used for debug/panic) */ 233106490Smdoddstatic struct mtx all_mtx = { MTX_UNOWNED, 0, 0, 0, {"All mutexes queue head"}, 2346604Sache TAILQ_HEAD_INITIALIZER(all_mtx.mtx_blocked), 235106490Smdodd { NULL, NULL }, &all_mtx, &all_mtx }; 236104445Smdodd 237106490Smdodd/* 2386604Sache * flag++ is slezoid way of shutting up unused parameter warning 2396604Sache * in mtx_init() 2406604Sache */ 2416604Sache#define witness_init(m, flag) flag++ 242106490Smdodd#define witness_destroy(m) 243104445Smdodd#define witness_try_enter(m, t, f, l) 244106490Smdodd#endif /* WITNESS */ 2452477Sache 246106490Smdoddstatic int mtx_cur_cnt; 247104445Smdoddstatic int mtx_max_cnt; 248106490Smdodd 2492477Sachestatic void propagate_priority(struct proc *); 250106490Smdoddstatic void mtx_enter_hard(struct mtx *, int type, int saveintr); 251104445Smdoddstatic void mtx_exit_hard(struct mtx *, int type); 252106490Smdodd 2536604Sache#define mtx_unowned(m) ((m)->mtx_lock == MTX_UNOWNED) 254578Srgrimes#define mtx_owner(m) (mtx_unowned(m) ? NULL \ 255111731Sphk : (struct proc *)((m)->mtx_lock & MTX_FLAGMASK)) 256104445Smdodd 257106490Smdodd#define RETIP(x) *(((uintptr_t *)(&x)) - 1) 258104545Smdodd#define SET_PRIO(p, pri) (p)->p_priority = (pri) 259578Srgrimes 260106490Smdoddstatic void 261106490Smdoddpropagate_priority(struct proc *p) 262106490Smdodd{ 263578Srgrimes int pri = p->p_priority; 264104545Smdodd struct mtx *m = p->p_blocked; 265106490Smdodd 266106490Smdodd mtx_assert(&sched_lock, MA_OWNED); 26751111Sjulian for (;;) { 268106490Smdodd struct proc *p1; 269578Srgrimes 270578Srgrimes p = mtx_owner(m); 271104441Smdodd 272130585Sphk if (p == NULL) { 273578Srgrimes /* 274104445Smdodd * This really isn't quite right. Really 2758876Srgrimes * ought to bump priority of process that 276104445Smdodd * next acquires the mutex. 2778876Srgrimes */ 278106490Smdodd MPASS(m->mtx_lock == MTX_CONTESTED); 279106490Smdodd return; 280578Srgrimes } 281104445Smdodd MPASS(p->p_magic == P_MAGIC); 282106490Smdodd KASSERT(p->p_stat != SSLEEP, ("sleeping process owns a mutex")); 283106490Smdodd if (p->p_priority <= pri) 284578Srgrimes return; 285106490Smdodd 286578Srgrimes /* 287578Srgrimes * Bump this process' priority. 288104441Smdodd */ 28959249Sphk SET_PRIO(p, pri); 290578Srgrimes 291104445Smdodd /* 2928876Srgrimes * If lock holder is actually running, just bump priority. 293104445Smdodd */ 294578Srgrimes#ifdef SMP 295578Srgrimes /* 296106490Smdodd * For SMP, we can check the p_oncpu field to see if we are 297104545Smdodd * running. 29859249Sphk */ 299578Srgrimes if (p->p_oncpu != 0xff) { 300578Srgrimes MPASS(p->p_stat == SRUN || p->p_stat == SZOMB); 301578Srgrimes return; 302578Srgrimes } 30359249Sphk#else 30459249Sphk /* 305578Srgrimes * For UP, we check to see if p is curproc (this shouldn't 306578Srgrimes * ever happen however as it would mean we are in a deadlock.) 3078876Srgrimes */ 308578Srgrimes if (p == curproc) { 30959249Sphk panic("Deadlock detected"); 310578Srgrimes return; 3118876Srgrimes } 312106490Smdodd#endif 313104545Smdodd /* 314104545Smdodd * If on run queue move to new run queue, and 315578Srgrimes * quit. 3168876Srgrimes */ 317104545Smdodd if (p->p_stat == SRUN) { 318104545Smdodd printf("XXX: moving process %d(%s) to a new run queue\n", 319578Srgrimes p->p_pid, p->p_comm); 320112946Sphk MPASS(p->p_blocked == NULL); 3218876Srgrimes remrunqueue(p); 322578Srgrimes setrunqueue(p); 323104445Smdodd return; 324578Srgrimes } 325578Srgrimes 326578Srgrimes /* 32759249Sphk * If we aren't blocked on a mutex, we should be. 328578Srgrimes */ 32959249Sphk KASSERT(p->p_stat == SMTX, ( 330578Srgrimes "process %d(%s):%d holds %s but isn't blocked on a mutex\n", 331578Srgrimes p->p_pid, p->p_comm, p->p_stat, 332578Srgrimes m->mtx_description)); 333578Srgrimes 334104441Smdodd /* 335104445Smdodd * Pick up the mutex that p is blocked on. 336578Srgrimes */ 33759249Sphk m = p->p_blocked; 3388876Srgrimes MPASS(m != NULL); 339106490Smdodd 340578Srgrimes printf("XXX: process %d(%s) is blocked on %s\n", p->p_pid, 3412477Sache p->p_comm, m->mtx_description); 342578Srgrimes /* 343137045Sphk * Check if the proc needs to be moved up on 34415574Sphk * the blocked chain 345578Srgrimes */ 346578Srgrimes if (p == TAILQ_FIRST(&m->mtx_blocked)) { 347106490Smdodd printf("XXX: process at head of run queue\n"); 348578Srgrimes continue; 349578Srgrimes } 350578Srgrimes p1 = TAILQ_PREV(p, rq, p_procq); 351578Srgrimes if (p1->p_priority <= pri) { 352578Srgrimes printf( 353106490Smdodd "XXX: previous process %d(%s) has higher priority\n", 354106490Smdodd p->p_pid, p->p_comm); 355578Srgrimes continue; 356106490Smdodd } 357578Srgrimes 358578Srgrimes /* 359578Srgrimes * Remove proc from blocked chain and determine where 360104441Smdodd * it should be moved up to. Since we know that p1 has 361130585Sphk * a lower priority than p, we know that at least one 362578Srgrimes * process in the chain has a lower priority and that 363104445Smdodd * p1 will thus not be NULL after the loop. 364104545Smdodd */ 3658876Srgrimes TAILQ_REMOVE(&m->mtx_blocked, p, p_procq); 366104445Smdodd TAILQ_FOREACH(p1, &m->mtx_blocked, p_procq) { 367578Srgrimes MPASS(p1->p_magic == P_MAGIC); 368104445Smdodd if (p1->p_priority > pri) 369106490Smdodd break; 37037618Sbde } 371578Srgrimes MPASS(p1 != NULL); 372578Srgrimes TAILQ_INSERT_BEFORE(p1, p, p_procq); 37314285Sache CTR4(KTR_LOCK, 37414285Sache "propagate_priority: p 0x%p moved before 0x%p on [0x%p] %s", 37514285Sache p, p1, m, m->mtx_description); 37614285Sache } 37714285Sache} 37814285Sache 37914285Sache/* 38014285Sache * Get lock 'm', the macro handles the easy (and most common cases) and leaves 381106490Smdodd * the slow stuff to the mtx_enter_hard() function. 38214285Sache * 383104445Smdodd * Note: since type is usually a constant much of this code is optimized out. 38414285Sache */ 385106490Smdoddvoid 386106490Smdodd_mtx_enter(struct mtx *mtxp, int type, const char *file, int line) 38714285Sache{ 388106490Smdodd struct mtx *mpp = mtxp; 389106490Smdodd 39014285Sache /* bits only valid on mtx_exit() */ 391104445Smdodd MPASS4(((type) & (MTX_NORECURSE | MTX_NOSWITCH)) == 0, 39214285Sache STR_mtx_bad_type, file, line); 393104445Smdodd 39414285Sache if ((type) & MTX_SPIN) { 395104445Smdodd /* 39614285Sache * Easy cases of spin locks: 397104445Smdodd * 39814285Sache * 1) We already own the lock and will simply recurse on it (if 39914285Sache * RLIKELY) 400106490Smdodd * 401106490Smdodd * 2) The lock is free, we just get it 402106490Smdodd */ 40314285Sache if ((type) & MTX_RLIKELY) { 404106490Smdodd /* 405104445Smdodd * Check for recursion, if we already have this 406106490Smdodd * lock we just bump the recursion count. 40714285Sache */ 40814285Sache if (mpp->mtx_lock == (uintptr_t)CURTHD) { 40914285Sache mpp->mtx_recurse++; 410106490Smdodd goto done; 411106490Smdodd } 412111731Sphk } 41314285Sache 414106490Smdodd if (((type) & MTX_TOPHALF) == 0) { 415106490Smdodd /* 416106490Smdodd * If an interrupt thread uses this we must block 417104445Smdodd * interrupts here. 418106490Smdodd */ 419106490Smdodd if ((type) & MTX_FIRST) { 42014285Sache ASS_IEN; 42114285Sache disable_intr(); 42214285Sache _getlock_norecurse(mpp, CURTHD, 423104545Smdodd (type) & MTX_HARDOPTS); 424106490Smdodd } else { 425104545Smdodd _getlock_spin_block(mpp, CURTHD, 426104545Smdodd (type) & MTX_HARDOPTS); 427106490Smdodd } 428104545Smdodd } else 429104545Smdodd _getlock_norecurse(mpp, CURTHD, (type) & MTX_HARDOPTS); 430578Srgrimes } else { 431104445Smdodd /* Sleep locks */ 432578Srgrimes if ((type) & MTX_RLIKELY) 433104445Smdodd _getlock_sleep(mpp, CURTHD, (type) & MTX_HARDOPTS); 4342477Sache else 435104445Smdodd _getlock_norecurse(mpp, CURTHD, (type) & MTX_HARDOPTS); 436141031Ssobomax } 437141031Ssobomaxdone: 438578Srgrimes WITNESS_ENTER(mpp, type, file, line); 439141031Ssobomax if (((type) & MTX_QUIET) == 0) 440578Srgrimes CTR5(KTR_LOCK, STR_mtx_enter_fmt, 441104445Smdodd mpp->mtx_description, mpp, mpp->mtx_recurse, file, line); 442578Srgrimes 443104445Smdodd} 444578Srgrimes 445104445Smdodd/* 446578Srgrimes * Attempt to get MTX_DEF lock, return non-zero if lock acquired. 447104445Smdodd * 448578Srgrimes * XXX DOES NOT HANDLE RECURSION 449104445Smdodd */ 450106490Smdoddint 451106490Smdodd_mtx_try_enter(struct mtx *mtxp, int type, const char *file, int line) 452578Srgrimes{ 453104445Smdodd struct mtx *const mpp = mtxp; 454578Srgrimes int rval; 455106490Smdodd 456578Srgrimes rval = _obtain_lock(mpp, CURTHD); 457578Srgrimes#ifdef WITNESS 458578Srgrimes if (rval && mpp->mtx_witness != NULL) { 459578Srgrimes MPASS(mpp->mtx_recurse == 0); 460104441Smdodd witness_try_enter(mpp, type, file, line); 461130585Sphk } 462578Srgrimes#endif /* WITNESS */ 463104445Smdodd if (((type) & MTX_QUIET) == 0) 464578Srgrimes CTR5(KTR_LOCK, STR_mtx_try_enter_fmt, 465578Srgrimes mpp->mtx_description, mpp, rval, file, line); 466104445Smdodd 467104445Smdodd return rval; 468104445Smdodd} 469106490Smdodd 470106490Smdodd/* 471106490Smdodd * Release lock m. 472106490Smdodd */ 473578Srgrimesvoid 474106490Smdodd_mtx_exit(struct mtx *mtxp, int type, const char *file, int line) 475578Srgrimes{ 476578Srgrimes struct mtx *const mpp = mtxp; 477578Srgrimes 478578Srgrimes MPASS4(mtx_owned(mpp), STR_mtx_owned, file, line); 479578Srgrimes WITNESS_EXIT(mpp, type, file, line); 480578Srgrimes if (((type) & MTX_QUIET) == 0) 481578Srgrimes CTR5(KTR_LOCK, STR_mtx_exit_fmt, 4821197Srgrimes mpp->mtx_description, mpp, mpp->mtx_recurse, file, line); 4831197Srgrimes if ((type) & MTX_SPIN) { 484578Srgrimes if ((type) & MTX_NORECURSE) { 485578Srgrimes int mtx_intr = mpp->mtx_saveintr; 486578Srgrimes 487578Srgrimes MPASS4(mpp->mtx_recurse == 0, STR_mtx_recurse, 4881197Srgrimes file, line); 4891197Srgrimes _release_lock_quick(mpp); 490578Srgrimes if (((type) & MTX_TOPHALF) == 0) { 491578Srgrimes if ((type) & MTX_FIRST) { 492578Srgrimes ASS_IDIS; 493578Srgrimes enable_intr(); 49411872Sphk } else 4951197Srgrimes restore_intr(mtx_intr); 496104445Smdodd } 497578Srgrimes } else { 498104445Smdodd if (((type & MTX_TOPHALF) == 0) && 499578Srgrimes (type & MTX_FIRST)) { 50011872Sphk ASS_IDIS; 501578Srgrimes ASS_SIEN(mpp); 5021197Srgrimes } 5031197Srgrimes _exitlock_spin(mpp); 504104445Smdodd } 5051197Srgrimes } else { 5061197Srgrimes /* Handle sleep locks */ 5071197Srgrimes if ((type) & MTX_RLIKELY) 5081197Srgrimes _exitlock(mpp, CURTHD, (type) & MTX_HARDOPTS); 509104445Smdodd else { 510106490Smdodd _exitlock_norecurse(mpp, CURTHD, 5111197Srgrimes (type) & MTX_HARDOPTS); 51213598Sjoerg } 513104445Smdodd } 514106490Smdodd} 5151197Srgrimes 5161197Srgrimesvoid 517978Sjkhmtx_enter_hard(struct mtx *m, int type, int saveintr) 518578Srgrimes{ 519104445Smdodd struct proc *p = CURPROC; 520104445Smdodd 521578Srgrimes KASSERT(p != NULL, ("curproc is NULL in mutex")); 5221197Srgrimes 5231197Srgrimes switch (type) { 524578Srgrimes case MTX_DEF: 525104445Smdodd if ((m->mtx_lock & MTX_FLAGMASK) == (uintptr_t)p) { 526578Srgrimes m->mtx_recurse++; 527578Srgrimes atomic_set_ptr(&m->mtx_lock, MTX_RECURSED); 528578Srgrimes if ((type & MTX_QUIET) == 0) 529104445Smdodd CTR1(KTR_LOCK, "mtx_enter: 0x%p recurse", m); 530578Srgrimes return; 531104445Smdodd } 532578Srgrimes if ((type & MTX_QUIET) == 0) 533578Srgrimes CTR3(KTR_LOCK, 534578Srgrimes "mtx_enter: 0x%p contested (lock=%p) [0x%p]", 535104445Smdodd m, (void *)m->mtx_lock, (void *)RETIP(m)); 536578Srgrimes 5371197Srgrimes /* 5381197Srgrimes * Save our priority. Even though p_nativepri is protected 5391197Srgrimes * by sched_lock, we don't obtain it here as it can be 5401197Srgrimes * expensive. Since this is the only place p_nativepri is 5412477Sache * set, and since two CPUs will not be executing the same 542104445Smdodd * process concurrently, we know that no other CPU is going 543578Srgrimes * to be messing with this. Also, p_nativepri is only read 5441197Srgrimes * when we are blocked on a mutex, so that can't be happening 545104445Smdodd * right now either. 546104445Smdodd */ 547104445Smdodd p->p_nativepri = p->p_priority; 5481197Srgrimes while (!_obtain_lock(m, p)) { 549104445Smdodd uintptr_t v; 5501197Srgrimes struct proc *p1; 551104445Smdodd 552104445Smdodd mtx_enter(&sched_lock, MTX_SPIN | MTX_RLIKELY); 553104445Smdodd /* 5541197Srgrimes * check if the lock has been released while 5555178Sache * waiting for the schedlock. 556104445Smdodd */ 5575226Sache if ((v = m->mtx_lock) == MTX_UNOWNED) { 558104445Smdodd mtx_exit(&sched_lock, MTX_SPIN); 559104445Smdodd continue; 5601197Srgrimes } 561104445Smdodd /* 5624480Sache * The mutex was marked contested on release. This 5634480Sache * means that there are processes blocked on it. 56413874Sache */ 565104445Smdodd if (v == MTX_CONTESTED) { 566104445Smdodd p1 = TAILQ_FIRST(&m->mtx_blocked); 56713874Sache KASSERT(p1 != NULL, ("contested mutex has no contesters")); 568104445Smdodd KASSERT(p != NULL, ("curproc is NULL for contested mutex")); 569104445Smdodd m->mtx_lock = (uintptr_t)p | MTX_CONTESTED; 5704480Sache if (p1->p_priority < p->p_priority) { 571104445Smdodd SET_PRIO(p, p1->p_priority); 572104445Smdodd } 5734480Sache mtx_exit(&sched_lock, MTX_SPIN); 5744480Sache return; 5754480Sache } 576104445Smdodd /* 577104445Smdodd * If the mutex isn't already contested and 5784480Sache * a failure occurs setting the contested bit the 5794480Sache * mutex was either release or the 580104445Smdodd * state of the RECURSION bit changed. 581104445Smdodd */ 582104445Smdodd if ((v & MTX_CONTESTED) == 0 && 5834480Sache !atomic_cmpset_ptr(&m->mtx_lock, (void *)v, 5844480Sache (void *)(v | MTX_CONTESTED))) { 585104445Smdodd mtx_exit(&sched_lock, MTX_SPIN); 586104445Smdodd continue; 5874480Sache } 5884480Sache 5895226Sache /* We definitely have to sleep for this lock */ 590104445Smdodd mtx_assert(m, MA_NOTOWNED); 591104445Smdodd 592104445Smdodd#ifdef notyet 593104445Smdodd /* 594106490Smdodd * If we're borrowing an interrupted thread's VM 595578Srgrimes * context must clean up before going to sleep. 596578Srgrimes */ 597978Sjkh if (p->p_flag & (P_ITHD | P_SITHD)) { 5981197Srgrimes ithd_t *it = (ithd_t *)p; 599104445Smdodd 600578Srgrimes if (it->it_interrupted) { 601578Srgrimes if ((type & MTX_QUIET) == 0) 602578Srgrimes CTR2(KTR_LOCK, 6035226Sache "mtx_enter: 0x%x interrupted 0x%x", 6042477Sache it, it->it_interrupted); 605104445Smdodd intr_thd_fixup(it); 606106490Smdodd } 6072477Sache } 608578Srgrimes#endif 609106490Smdodd 610578Srgrimes /* Put us on the list of procs blocked on this mutex */ 611578Srgrimes if (TAILQ_EMPTY(&m->mtx_blocked)) { 6121197Srgrimes p1 = (struct proc *)(m->mtx_lock & 613104445Smdodd MTX_FLAGMASK); 614578Srgrimes LIST_INSERT_HEAD(&p1->p_contested, m, 615578Srgrimes mtx_contested); 616578Srgrimes TAILQ_INSERT_TAIL(&m->mtx_blocked, p, p_procq); 617104445Smdodd } else { 618104445Smdodd TAILQ_FOREACH(p1, &m->mtx_blocked, p_procq) 619106490Smdodd if (p1->p_priority > p->p_priority) 620578Srgrimes break; 621578Srgrimes if (p1) 622578Srgrimes TAILQ_INSERT_BEFORE(p1, p, p_procq); 623106490Smdodd else 624578Srgrimes TAILQ_INSERT_TAIL(&m->mtx_blocked, p, 625578Srgrimes p_procq); 6261197Srgrimes } 627104445Smdodd 628578Srgrimes p->p_blocked = m; /* Who we're blocked on */ 629578Srgrimes p->p_mtxname = m->mtx_description; 630578Srgrimes p->p_stat = SMTX; 631578Srgrimes#if 0 632578Srgrimes propagate_priority(p); 633104445Smdodd#endif 634104445Smdodd if ((type & MTX_QUIET) == 0) 6356604Sache CTR3(KTR_LOCK, 636106490Smdodd "mtx_enter: p 0x%p blocked on [0x%p] %s", 637106490Smdodd p, m, m->mtx_description); 6386604Sache mi_switch(); 639578Srgrimes if ((type & MTX_QUIET) == 0) 640106490Smdodd CTR3(KTR_LOCK, 641578Srgrimes "mtx_enter: p 0x%p free from blocked on [0x%p] %s", 642104445Smdodd p, m, m->mtx_description); 643106490Smdodd mtx_exit(&sched_lock, MTX_SPIN); 644106490Smdodd } 645578Srgrimes return; 646578Srgrimes case MTX_SPIN: 6472477Sache case MTX_SPIN | MTX_FIRST: 648104445Smdodd case MTX_SPIN | MTX_TOPHALF: 649578Srgrimes { 650104445Smdodd int i = 0; 651578Srgrimes 652106490Smdodd if (m->mtx_lock == (uintptr_t)p) { 653106490Smdodd m->mtx_recurse++; 6548375Srgrimes return; 655104445Smdodd } 656106490Smdodd if ((type & MTX_QUIET) == 0) 657578Srgrimes CTR1(KTR_LOCK, "mtx_enter: %p spinning", m); 658578Srgrimes for (;;) { 659106490Smdodd if (_obtain_lock(m, p)) 660106490Smdodd break; 661106490Smdodd while (m->mtx_lock != MTX_UNOWNED) { 662106490Smdodd if (i++ < 1000000) 663106490Smdodd continue; 664578Srgrimes if (i++ < 6000000) 665578Srgrimes DELAY (1); 6661197Srgrimes#ifdef DDB 667104445Smdodd else if (!db_active) 668578Srgrimes#else 669578Srgrimes else 6708876Srgrimes#endif 671578Srgrimes panic( 672578Srgrimes "spin lock %s held by 0x%p for > 5 seconds", 673104445Smdodd m->mtx_description, 674104445Smdodd (void *)m->mtx_lock); 675106490Smdodd } 676578Srgrimes } 677578Srgrimes 678578Srgrimes#ifdef MUTEX_DEBUG 679106490Smdodd if (type != MTX_SPIN) 680578Srgrimes m->mtx_saveintr = 0xbeefface; 681578Srgrimes else 6821197Srgrimes#endif 683104445Smdodd m->mtx_saveintr = saveintr; 684578Srgrimes if ((type & MTX_QUIET) == 0) 6852477Sache CTR1(KTR_LOCK, "mtx_enter: 0x%p spin done", m); 6868876Srgrimes return; 6872477Sache } 688578Srgrimes } 689104445Smdodd} 690104445Smdodd 691578Srgrimesvoid 692578Srgrimesmtx_exit_hard(struct mtx *m, int type) 6932477Sache{ 694104445Smdodd struct proc *p, *p1; 695106490Smdodd struct mtx *m1; 6962477Sache int pri; 697578Srgrimes 698104445Smdodd p = CURPROC; 699106490Smdodd switch (type) { 700578Srgrimes case MTX_DEF: 7012477Sache case MTX_DEF | MTX_NOSWITCH: 702106490Smdodd if (mtx_recursed(m)) { 703578Srgrimes if (--(m->mtx_recurse) == 0) 704578Srgrimes atomic_clear_ptr(&m->mtx_lock, MTX_RECURSED); 7051197Srgrimes if ((type & MTX_QUIET) == 0) 7061197Srgrimes CTR1(KTR_LOCK, "mtx_exit: 0x%p unrecurse", m); 707578Srgrimes return; 708578Srgrimes } 709578Srgrimes mtx_enter(&sched_lock, MTX_SPIN); 71013770Sache if ((type & MTX_QUIET) == 0) 71113770Sache CTR1(KTR_LOCK, "mtx_exit: 0x%p contested", m); 71213770Sache p1 = TAILQ_FIRST(&m->mtx_blocked); 71313770Sache MPASS(p->p_magic == P_MAGIC); 714578Srgrimes MPASS(p1->p_magic == P_MAGIC); 715578Srgrimes TAILQ_REMOVE(&m->mtx_blocked, p1, p_procq); 7161197Srgrimes if (TAILQ_EMPTY(&m->mtx_blocked)) { 71713770Sache LIST_REMOVE(m, mtx_contested); 718578Srgrimes _release_lock_quick(m); 71913770Sache if ((type & MTX_QUIET) == 0) 72013770Sache CTR1(KTR_LOCK, "mtx_exit: 0x%p not held", m); 721578Srgrimes } else 722578Srgrimes atomic_store_rel_ptr(&m->mtx_lock, 7231197Srgrimes (void *)MTX_CONTESTED); 724104445Smdodd pri = MAXPRI; 725578Srgrimes LIST_FOREACH(m1, &p->p_contested, mtx_contested) { 726578Srgrimes int cp = TAILQ_FIRST(&m1->mtx_blocked)->p_priority; 727578Srgrimes if (cp < pri) 728106490Smdodd pri = cp; 729578Srgrimes } 7302477Sache if (pri > p->p_nativepri) 7312477Sache pri = p->p_nativepri; 732578Srgrimes SET_PRIO(p, pri); 733104445Smdodd if ((type & MTX_QUIET) == 0) 734106490Smdodd CTR2(KTR_LOCK, 735578Srgrimes "mtx_exit: 0x%p contested setrunqueue 0x%p", m, p1); 736578Srgrimes p1->p_blocked = NULL; 737106490Smdodd p1->p_mtxname = NULL; 738104445Smdodd p1->p_stat = SRUN; 739106490Smdodd setrunqueue(p1); 740578Srgrimes if ((type & MTX_NOSWITCH) == 0 && p1->p_priority < pri) { 741578Srgrimes#ifdef notyet 742106490Smdodd if (p->p_flag & (P_ITHD | P_SITHD)) { 743106490Smdodd ithd_t *it = (ithd_t *)p; 7446604Sache 745106490Smdodd if (it->it_interrupted) { 746106490Smdodd if ((type & MTX_QUIET) == 0) 747578Srgrimes CTR2(KTR_LOCK, 748578Srgrimes "mtx_exit: 0x%x interruped 0x%x", 749106490Smdodd it, it->it_interrupted); 750578Srgrimes intr_thd_fixup(it); 751578Srgrimes } 752578Srgrimes } 753578Srgrimes#endif 754578Srgrimes setrunqueue(p); 755578Srgrimes if ((type & MTX_QUIET) == 0) 756578Srgrimes CTR2(KTR_LOCK, 757578Srgrimes "mtx_exit: 0x%p switching out lock=0x%p", 7581197Srgrimes m, (void *)m->mtx_lock); 75925056Sbde mi_switch(); 76025056Sbde if ((type & MTX_QUIET) == 0) 761104445Smdodd CTR2(KTR_LOCK, 762104445Smdodd "mtx_exit: 0x%p resuming lock=0x%p", 763104445Smdodd m, (void *)m->mtx_lock); 764104445Smdodd } 765104445Smdodd mtx_exit(&sched_lock, MTX_SPIN); 76625056Sbde break; 76725056Sbde case MTX_SPIN: 76825056Sbde case MTX_SPIN | MTX_FIRST: 769104445Smdodd if (mtx_recursed(m)) { 770578Srgrimes m->mtx_recurse--; 771104445Smdodd return; 772104445Smdodd } 773104445Smdodd MPASS(mtx_owned(m)); 774578Srgrimes _release_lock_quick(m); 775104445Smdodd if (type & MTX_FIRST) 776578Srgrimes enable_intr(); /* XXX is this kosher? */ 777578Srgrimes else { 778104445Smdodd MPASS(m->mtx_saveintr != 0xbeefface); 779104445Smdodd restore_intr(m->mtx_saveintr); 780104445Smdodd } 781578Srgrimes break; 782578Srgrimes case MTX_SPIN | MTX_TOPHALF: 783578Srgrimes if (mtx_recursed(m)) { 784104445Smdodd m->mtx_recurse--; 785578Srgrimes return; 786578Srgrimes } 7876604Sache MPASS(mtx_owned(m)); 788578Srgrimes _release_lock_quick(m); 789104445Smdodd break; 790578Srgrimes default: 791104445Smdodd panic("mtx_exit_hard: unsupported type 0x%x\n", type); 792104445Smdodd } 793578Srgrimes} 794578Srgrimes 795104445Smdodd#ifdef INVARIANTS 796104445Smdoddvoid 797578Srgrimes_mtx_assert(struct mtx *m, int what, const char *file, int line) 798104445Smdodd{ 799104445Smdodd switch ((what)) { 800104445Smdodd case MA_OWNED: 801578Srgrimes case MA_OWNED | MA_RECURSED: 802578Srgrimes case MA_OWNED | MA_NOTRECURSED: 803106490Smdodd if (!mtx_owned((m))) 804106490Smdodd panic("mutex %s not owned at %s:%d", 8056028Sache (m)->mtx_description, file, line); 806104445Smdodd if (mtx_recursed((m))) { 8072477Sache if (((what) & MA_NOTRECURSED) != 0) 8081197Srgrimes panic("mutex %s recursed at %s:%d", 8098375Srgrimes (m)->mtx_description, file, line); 810578Srgrimes } else if (((what) & MA_RECURSED) != 0) { 811106490Smdodd panic("mutex %s unrecursed at %s:%d", 812104445Smdodd (m)->mtx_description, file, line); 813578Srgrimes } 814578Srgrimes break; 8156604Sache case MA_NOTOWNED: 8166028Sache if (mtx_owned((m))) 817578Srgrimes panic("mutex %s owned at %s:%d", 818106490Smdodd (m)->mtx_description, file, line); 8194389Sache break; 820578Srgrimes default: 821578Srgrimes panic("unknown mtx_assert at %s:%d", file, line); 8224389Sache } 823106490Smdodd} 824578Srgrimes#endif 825578Srgrimes 826106490Smdodd#define MV_DESTROY 0 /* validate before destory */ 8272477Sache#define MV_INIT 1 /* validate before init */ 8282477Sache 829578Srgrimes#ifdef MUTEX_DEBUG 8302477Sache 831106490Smdoddint mtx_validate __P((struct mtx *, int)); 8322477Sache 833104445Smdoddint 834104445Smdoddmtx_validate(struct mtx *m, int when) 8352477Sache{ 836104445Smdodd struct mtx *mp; 837104445Smdodd int i; 838578Srgrimes int retval = 0; 839578Srgrimes 840104445Smdodd#ifdef WITNESS 841578Srgrimes if (witness_cold) 842578Srgrimes return 0; 843578Srgrimes#endif 844578Srgrimes if (m == &all_mtx || cold) 845104445Smdodd return 0; 846104445Smdodd 847578Srgrimes mtx_enter(&all_mtx, MTX_DEF); 848104445Smdodd/* 849578Srgrimes * XXX - When kernacc() is fixed on the alpha to handle K0_SEG memory properly 850578Srgrimes * we can re-enable the kernacc() checks. 851104445Smdodd */ 852104445Smdodd#ifndef __alpha__ 853104445Smdodd MPASS(kernacc((caddr_t)all_mtx.mtx_next, sizeof(uintptr_t), 854578Srgrimes VM_PROT_READ) == 1); 855578Srgrimes#endif 856106490Smdodd MPASS(all_mtx.mtx_next->mtx_prev == &all_mtx); 857106490Smdodd for (i = 0, mp = all_mtx.mtx_next; mp != &all_mtx; mp = mp->mtx_next) { 858106490Smdodd#ifndef __alpha__ 8596028Sache if (kernacc((caddr_t)mp->mtx_next, sizeof(uintptr_t), 8606028Sache VM_PROT_READ) != 1) { 861104445Smdodd panic("mtx_validate: mp=%p mp->mtx_next=%p", 8622477Sache mp, mp->mtx_next); 863106490Smdodd } 8641197Srgrimes#endif 8658375Srgrimes i++; 8662477Sache if (i > mtx_cur_cnt) { 867578Srgrimes panic("mtx_validate: too many in chain, known=%d\n", 86859249Sphk mtx_cur_cnt); 869578Srgrimes } 870578Srgrimes } 871578Srgrimes MPASS(i == mtx_cur_cnt); 872121212Sphk switch (when) { 873578Srgrimes case MV_DESTROY: 8748456Srgrimes for (mp = all_mtx.mtx_next; mp != &all_mtx; mp = mp->mtx_next) 8758375Srgrimes if (mp == m) 876578Srgrimes break; 877578Srgrimes MPASS(mp == m); 878578Srgrimes break; 8796028Sache case MV_INIT: 880578Srgrimes for (mp = all_mtx.mtx_next; mp != &all_mtx; mp = mp->mtx_next) 881106719Smdodd if (mp == m) { 882106490Smdodd /* 883104445Smdodd * Not good. This mutex already exists. 884104445Smdodd */ 885104445Smdodd printf("re-initing existing mutex %s\n", 886104445Smdodd m->mtx_description); 887104445Smdodd MPASS(m->mtx_lock == MTX_UNOWNED); 888104445Smdodd retval = 1; 889106719Smdodd } 8902477Sache } 8912762Sache mtx_exit(&all_mtx, MTX_DEF); 8922762Sache return (retval); 893104445Smdodd} 8945226Sache#endif 8952762Sache 8962762Sachevoid 8972762Sachemtx_init(struct mtx *m, const char *t, int flag) 8982762Sache{ 899578Srgrimes if ((flag & MTX_QUIET) == 0) 900104445Smdodd CTR2(KTR_LOCK, "mtx_init 0x%p (%s)", m, t); 901104445Smdodd#ifdef MUTEX_DEBUG 902578Srgrimes if (mtx_validate(m, MV_INIT)) /* diagnostic and error correction */ 903578Srgrimes return; 904104445Smdodd#endif 905104445Smdodd 906578Srgrimes bzero((void *)m, sizeof *m); 907104445Smdodd TAILQ_INIT(&m->mtx_blocked); 9085226Sache#ifdef WITNESS 9091197Srgrimes if (!witness_cold) { 9108375Srgrimes /* XXX - should not use DEVBUF */ 9112762Sache m->mtx_union.mtxu_debug = malloc(sizeof(struct mtx_debug), 912578Srgrimes M_DEVBUF, M_NOWAIT | M_ZERO); 91359249Sphk MPASS(m->mtx_union.mtxu_debug != NULL); 9142477Sache 915104445Smdodd m->mtx_description = t; 916578Srgrimes } else { 917104445Smdodd /* 918104445Smdodd * Save a pointer to the description so that witness_fixup() 919578Srgrimes * can properly initialize this mutex later on. 920104445Smdodd */ 9212477Sache m->mtx_union.mtxu_description = t; 9225226Sache } 923104445Smdodd#else 924104445Smdodd m->mtx_description = t; 925104445Smdodd#endif 926104445Smdodd 9272477Sache m->mtx_flags = flag; 9282477Sache m->mtx_lock = MTX_UNOWNED; 929578Srgrimes /* Put on all mutex queue */ 930578Srgrimes mtx_enter(&all_mtx, MTX_DEF); 931578Srgrimes m->mtx_next = &all_mtx; 932578Srgrimes m->mtx_prev = all_mtx.mtx_prev; 933578Srgrimes m->mtx_prev->mtx_next = m; 934578Srgrimes all_mtx.mtx_prev = m; 93559249Sphk if (++mtx_cur_cnt > mtx_max_cnt) 936578Srgrimes mtx_max_cnt = mtx_cur_cnt; 937578Srgrimes mtx_exit(&all_mtx, MTX_DEF); 938106490Smdodd#ifdef WITNESS 939104445Smdodd if (!witness_cold) 940578Srgrimes witness_init(m, flag); 941578Srgrimes#endif 9425226Sache} 943106490Smdodd 944106490Smdoddvoid 9456028Sachemtx_destroy(struct mtx *m) 946104445Smdodd{ 9472477Sache 9482477Sache#ifdef WITNESS 949104445Smdodd KASSERT(!witness_cold, ("%s: Cannot destroy while still cold\n", 950104445Smdodd __FUNCTION__)); 951578Srgrimes#endif 952578Srgrimes CTR2(KTR_LOCK, "mtx_destroy 0x%p (%s)", m, m->mtx_description); 953104445Smdodd#ifdef MUTEX_DEBUG 954578Srgrimes if (m->mtx_next == NULL) 955578Srgrimes panic("mtx_destroy: %p (%s) already destroyed", 956578Srgrimes m, m->mtx_description); 957578Srgrimes 958578Srgrimes if (!mtx_owned(m)) { 959578Srgrimes MPASS(m->mtx_lock == MTX_UNOWNED); 960104445Smdodd } else { 961578Srgrimes MPASS((m->mtx_lock & (MTX_RECURSED|MTX_CONTESTED)) == 0); 962578Srgrimes } 963578Srgrimes mtx_validate(m, MV_DESTROY); /* diagnostic */ 9642477Sache#endif 965578Srgrimes 96659249Sphk#ifdef WITNESS 96759249Sphk if (m->mtx_witness) 968578Srgrimes witness_destroy(m); 9692477Sache#endif /* WITNESS */ 970106490Smdodd 971104445Smdodd /* Remove from the all mutex queue */ 972578Srgrimes mtx_enter(&all_mtx, MTX_DEF); 973578Srgrimes m->mtx_next->mtx_prev = m->mtx_prev; 9742477Sache m->mtx_prev->mtx_next = m->mtx_next; 975104445Smdodd#ifdef MUTEX_DEBUG 9762477Sache m->mtx_next = m->mtx_prev = NULL; 9772477Sache#endif 978578Srgrimes#ifdef WITNESS 979104445Smdodd free(m->mtx_union.mtxu_debug, M_DEVBUF); 980104445Smdodd m->mtx_union.mtxu_debug = NULL; 981578Srgrimes#endif 982104445Smdodd mtx_cur_cnt--; 983104445Smdodd mtx_exit(&all_mtx, MTX_DEF); 984106490Smdodd} 985106490Smdodd 986578Srgrimesstatic void 987578Srgrimeswitness_fixup(void *dummy __unused) 988578Srgrimes{ 989578Srgrimes#ifdef WITNESS 990578Srgrimes struct mtx *mp; 9911197Srgrimes const char *description; 992104445Smdodd 9932477Sache /* Iterate through all mutexes and finish up mutex initialization. */ 9942477Sache for (mp = all_mtx.mtx_next; mp != &all_mtx; mp = mp->mtx_next) { 995104445Smdodd description = mp->mtx_union.mtxu_description; 996104445Smdodd 997104445Smdodd /* XXX - should not use DEVBUF */ 998106490Smdodd mp->mtx_union.mtxu_debug = malloc(sizeof(struct mtx_debug), 999106490Smdodd M_DEVBUF, M_NOWAIT | M_ZERO); 10006604Sache MPASS(mp->mtx_union.mtxu_debug != NULL); 10016604Sache 10026604Sache mp->mtx_description = description; 1003104445Smdodd 10046604Sache witness_init(mp, mp->mtx_flags); 10056604Sache } 10066604Sache 1007104445Smdodd /* Mark the witness code as being ready for use. */ 1008106490Smdodd atomic_store_rel_int(&witness_cold, 0); 1009106490Smdodd#endif 1010104445Smdodd} 10116604SacheSYSINIT(wtnsfxup, SI_SUB_MUTEX, SI_ORDER_FIRST, witness_fixup, NULL) 1012104445Smdodd 1013106490Smdodd/* 10146604Sache * The non-inlined versions of the mtx_*() functions are always built (above), 1015104445Smdodd * but the witness code depends on the WITNESS kernel option being specified. 1016106490Smdodd */ 1017106490Smdodd#ifdef WITNESS 10186604Sache 10196604Sache#define WITNESS_COUNT 200 1020106490Smdodd#define WITNESS_NCHILDREN 2 10216604Sache 1022106490Smdoddint witness_watch = 1; 10236604Sache 10246604Sachestruct witness { 10256604Sache struct witness *w_next; 1026104445Smdodd const char *w_description; 10276604Sache const char *w_file; 1028104445Smdodd int w_line; 10296604Sache struct witness *w_morechildren; 1030104445Smdodd u_char w_childcnt; 1031106490Smdodd u_char w_Giant_squawked:1; 1032106490Smdodd u_char w_other_squawked:1; 1033106490Smdodd u_char w_same_squawked:1; 1034104445Smdodd u_char w_sleep:1; /* MTX_DEF type mutex. */ 1035106490Smdodd u_char w_spin:1; /* MTX_SPIN type mutex. */ 1036104445Smdodd u_char w_recurse:1; /* MTX_RECURSE mutex option. */ 1037104445Smdodd u_int w_level; 1038106490Smdodd struct witness *w_children[WITNESS_NCHILDREN]; 1039106490Smdodd}; 10402477Sache 10412477Sachestruct witness_blessed { 10422477Sache char *b_lock1; 1043104445Smdodd char *b_lock2; 104413866Sache}; 104513866Sache 1046104445Smdodd#ifdef DDB 1047106490Smdodd/* 1048106490Smdodd * When DDB is enabled and witness_ddb is set to 1, it will cause the system to 1049104445Smdodd * drop into kdebug() when: 1050106490Smdodd * - a lock heirarchy violation occurs 105113866Sache * - locks are held when going to sleep. 105213866Sache */ 105313866Sache#ifdef WITNESS_DDB 1054104445Smdoddint witness_ddb = 1; 10552477Sache#else 10562477Sacheint witness_ddb = 0; 1057104445Smdodd#endif 1058106490SmdoddSYSCTL_INT(_debug, OID_AUTO, witness_ddb, CTLFLAG_RW, &witness_ddb, 0, ""); 1059106490Smdodd#endif /* DDB */ 1060106490Smdodd 10612477Sache#ifdef WITNESS_SKIPSPIN 10622477Sacheint witness_skipspin = 1; 10632477Sache#else 1064104445Smdoddint witness_skipspin = 0; 10652477Sache#endif 10662477SacheSYSCTL_INT(_debug, OID_AUTO, witness_skipspin, CTLFLAG_RD, &witness_skipspin, 0, 1067106490Smdodd ""); 1068106490Smdodd 1069106490Smdoddstatic struct mtx w_mtx; 1070106490Smdoddstatic struct witness *w_free; 10712477Sachestatic struct witness *w_all; 10722477Sachestatic int w_inited; 10732477Sachestatic int witness_dead; /* fatal error, probably no memory */ 1074104445Smdodd 1075578Srgrimesstatic struct witness w_data[WITNESS_COUNT]; 10762477Sache 1077578Srgrimesstatic struct witness *enroll __P((const char *description, int flag)); 1078106490Smdoddstatic int itismychild __P((struct witness *parent, struct witness *child)); 1079106490Smdoddstatic void removechild __P((struct witness *parent, struct witness *child)); 1080106490Smdoddstatic int isitmychild __P((struct witness *parent, struct witness *child)); 1081104445Smdoddstatic int isitmydescendant __P((struct witness *parent, struct witness *child)); 1082578Srgrimesstatic int dup_ok __P((struct witness *)); 1083578Srgrimesstatic int blessed __P((struct witness *, struct witness *)); 1084106490Smdoddstatic void witness_displaydescendants 1085104445Smdodd __P((void(*)(const char *fmt, ...), struct witness *)); 1086104445Smdoddstatic void witness_leveldescendents __P((struct witness *parent, int level)); 1087104445Smdoddstatic void witness_levelall __P((void)); 1088106490Smdoddstatic struct witness * witness_get __P((void)); 1089106490Smdoddstatic void witness_free __P((struct witness *m)); 10902477Sache 10912477Sache 1092104445Smdoddstatic char *ignore_list[] = { 10932477Sache "witness lock", 10942477Sache NULL 1095578Srgrimes}; 1096578Srgrimes 1097106490Smdoddstatic char *spin_order_list[] = { 1098578Srgrimes "sio", 1099578Srgrimes "sched lock", 11001197Srgrimes#ifdef __i386__ 1101104445Smdodd "clk", 1102578Srgrimes#endif 11032477Sache "callout", 1104578Srgrimes /* 1105104445Smdodd * leaf locks 1106106490Smdodd */ 1107578Srgrimes NULL 1108106490Smdodd}; 1109106490Smdodd 111013874Sachestatic char *order_list[] = { 111113874Sache "uidinfo hash", "uidinfo struct", NULL, 111213874Sache NULL 1113578Srgrimes}; 1114106490Smdodd 1115578Srgrimesstatic char *dup_list[] = { 1116578Srgrimes NULL 11171197Srgrimes}; 1118104445Smdodd 1119578Srgrimesstatic char *sleep_list[] = { 1120578Srgrimes "Giant", 1121578Srgrimes NULL 1122578Srgrimes}; 1123578Srgrimes 1124578Srgrimes/* 1125106490Smdodd * Pairs of locks which have been blessed 1126106490Smdodd * Don't complain about order problems with blessed locks 1127578Srgrimes */ 1128106490Smdoddstatic struct witness_blessed blessed_list[] = { 1129104445Smdodd}; 1130578Srgrimesstatic int blessed_count = sizeof(blessed_list) / sizeof(struct witness_blessed); 1131104445Smdodd 1132106490Smdoddstatic void 1133578Srgrimeswitness_init(struct mtx *m, int flag) 1134104445Smdodd{ 1135106490Smdodd m->mtx_witness = enroll(m->mtx_description, flag); 11366665Sache} 1137104445Smdodd 1138106490Smdoddstatic void 1139578Srgrimeswitness_destroy(struct mtx *m) 1140106490Smdodd{ 1141104445Smdodd struct mtx *m1; 11422477Sache struct proc *p; 1143578Srgrimes p = CURPROC; 1144106490Smdodd for ((m1 = LIST_FIRST(&p->p_heldmtx)); m1 != NULL; 1145578Srgrimes m1 = LIST_NEXT(m1, mtx_held)) { 11466612Sache if (m1 == m) { 1147578Srgrimes LIST_REMOVE(m, mtx_held); 1148104445Smdodd break; 1149578Srgrimes } 11502477Sache } 1151106490Smdodd return; 1152106490Smdodd 1153578Srgrimes} 1154578Srgrimes 11551197Srgrimesstatic void 1156578Srgrimeswitness_display(void(*prnt)(const char *fmt, ...)) 1157578Srgrimes{ 1158104445Smdodd struct witness *w, *w1; 1159106490Smdodd 1160578Srgrimes KASSERT(!witness_cold, ("%s: witness_cold\n", __FUNCTION__)); 11612477Sache witness_levelall(); 1162106490Smdodd 1163578Srgrimes for (w = w_all; w; w = w->w_next) { 1164578Srgrimes if (w->w_file == NULL) 1165578Srgrimes continue; 1166106490Smdodd for (w1 = w_all; w1; w1 = w1->w_next) { 1167106490Smdodd if (isitmychild(w1, w)) 1168106490Smdodd break; 1169106490Smdodd } 1170106490Smdodd if (w1 != NULL) 1171106490Smdodd continue; 1172106490Smdodd /* 1173578Srgrimes * This lock has no anscestors, display its descendants. 1174106490Smdodd */ 11752477Sache witness_displaydescendants(prnt, w); 11762477Sache } 1177104445Smdodd prnt("\nMutex which were never acquired\n"); 1178104445Smdodd for (w = w_all; w; w = w->w_next) { 1179106490Smdodd if (w->w_file != NULL) 1180106490Smdodd continue; 1181106490Smdodd prnt("%s\n", w->w_description); 1182106490Smdodd } 1183106490Smdodd} 11842477Sache 11852477Sachevoid 1186106490Smdoddwitness_enter(struct mtx *m, int flags, const char *file, int line) 1187578Srgrimes{ 1188106490Smdodd struct witness *w, *w1; 1189578Srgrimes struct mtx *m1; 1190578Srgrimes struct proc *p; 119131016Sphk int i; 11921197Srgrimes#ifdef DDB 1193104445Smdodd int go_into_ddb = 0; 119425460Sjoerg#endif /* DDB */ 119525460Sjoerg 119625460Sjoerg if (witness_cold || m->mtx_witness == NULL || panicstr) 119725460Sjoerg return; 119825460Sjoerg w = m->mtx_witness; 119925460Sjoerg p = CURPROC; 1200106490Smdodd 120125460Sjoerg if (flags & MTX_SPIN) { 120225460Sjoerg if (!(w->w_spin)) 1203104445Smdodd panic("mutex_enter: MTX_SPIN on MTX_DEF mutex %s @" 1204106490Smdodd " %s:%d", m->mtx_description, file, line); 120525460Sjoerg if (mtx_recursed(m)) { 120625460Sjoerg if (!(w->w_recurse)) 120725460Sjoerg panic("mutex_enter: recursion on non-recursive" 120825460Sjoerg " mutex %s @ %s:%d", m->mtx_description, 120925460Sjoerg file, line); 121025460Sjoerg return; 121125460Sjoerg } 121225460Sjoerg mtx_enter(&w_mtx, MTX_SPIN | MTX_QUIET); 1213106490Smdodd i = PCPU_GET(witness_spin_check); 121425460Sjoerg if (i != 0 && w->w_level < i) { 121525460Sjoerg mtx_exit(&w_mtx, MTX_SPIN | MTX_QUIET); 1216104445Smdodd panic("mutex_enter(%s:%x, MTX_SPIN) out of order @" 1217106490Smdodd " %s:%d already holding %s:%x", 121825460Sjoerg m->mtx_description, w->w_level, file, line, 121925460Sjoerg spin_order_list[ffs(i)-1], i); 1220106490Smdodd } 1221106490Smdodd PCPU_SET(witness_spin_check, i | w->w_level); 122225460Sjoerg mtx_exit(&w_mtx, MTX_SPIN | MTX_QUIET); 1223106490Smdodd w->w_file = file; 1224106490Smdodd w->w_line = line; 122525460Sjoerg m->mtx_line = line; 1226106490Smdodd m->mtx_file = file; 1227106490Smdodd return; 122825460Sjoerg } 122925460Sjoerg if (w->w_spin) 123025460Sjoerg panic("mutex_enter: MTX_DEF on MTX_SPIN mutex %s @ %s:%d", 1231106490Smdodd m->mtx_description, file, line); 1232106490Smdodd 1233106490Smdodd if (mtx_recursed(m)) { 123425460Sjoerg if (!(w->w_recurse)) 123525460Sjoerg panic("mutex_enter: recursion on non-recursive" 1236106490Smdodd " mutex %s @ %s:%d", m->mtx_description, 123725460Sjoerg file, line); 123825460Sjoerg return; 1239106490Smdodd } 124025460Sjoerg if (witness_dead) 124131016Sphk goto out; 124225460Sjoerg if (cold) 124325460Sjoerg goto out; 1244104445Smdodd 1245578Srgrimes if (!mtx_legal2block()) 12462477Sache panic("blockable mtx_enter() of %s when not legal @ %s:%d", 1247578Srgrimes m->mtx_description, file, line); 124813743Sache /* 1249578Srgrimes * Is this the first mutex acquired 125013743Sache */ 125113743Sache if ((m1 = LIST_FIRST(&p->p_heldmtx)) == NULL) 125246571Speter goto out; 125346571Speter 12542477Sache if ((w1 = m1->mtx_witness) == w) { 1255106490Smdodd if (w->w_same_squawked || dup_ok(w)) 1256578Srgrimes goto out; 1257578Srgrimes w->w_same_squawked = 1; 1258104445Smdodd printf("acquring duplicate lock of same type: \"%s\"\n", 1259106490Smdodd m->mtx_description); 1260578Srgrimes printf(" 1st @ %s:%d\n", w->w_file, w->w_line); 126113732Sache printf(" 2nd @ %s:%d\n", file, line); 126213732Sache#ifdef DDB 126313732Sache go_into_ddb = 1; 126413732Sache#endif /* DDB */ 126513732Sache goto out; 126613732Sache } 126713732Sache MPASS(!mtx_owned(&w_mtx)); 1268106490Smdodd mtx_enter(&w_mtx, MTX_SPIN | MTX_QUIET); 126913732Sache /* 127013743Sache * If we have a known higher number just say ok 127113743Sache */ 127213743Sache if (witness_watch > 1 && w->w_level > w1->w_level) { 127313743Sache mtx_exit(&w_mtx, MTX_SPIN | MTX_QUIET); 127413743Sache goto out; 1275106490Smdodd } 127613743Sache if (isitmydescendant(m1->mtx_witness, w)) { 127713732Sache mtx_exit(&w_mtx, MTX_SPIN | MTX_QUIET); 1278104445Smdodd goto out; 1279106490Smdodd } 128013732Sache for (i = 0; m1 != NULL; m1 = LIST_NEXT(m1, mtx_held), i++) { 128113732Sache 128213732Sache MPASS(i < 200); 1283106490Smdodd w1 = m1->mtx_witness; 128413732Sache if (isitmydescendant(w, w1)) { 1285106490Smdodd mtx_exit(&w_mtx, MTX_SPIN | MTX_QUIET); 1286106490Smdodd if (blessed(w, w1)) 128713732Sache goto out; 1288106490Smdodd if (m1 == &Giant) { 1289106490Smdodd if (w1->w_Giant_squawked) 129013732Sache goto out; 129113732Sache else 129213732Sache w1->w_Giant_squawked = 1; 1293106490Smdodd } else { 1294106490Smdodd if (w1->w_other_squawked) 1295106490Smdodd goto out; 129613732Sache else 129713732Sache w1->w_other_squawked = 1; 1298106490Smdodd } 129913732Sache printf("lock order reversal\n"); 13002477Sache printf(" 1st %s last acquired @ %s:%d\n", 13012477Sache w->w_description, w->w_file, w->w_line); 130213732Sache printf(" 2nd %p %s @ %s:%d\n", 1303578Srgrimes m1, w1->w_description, w1->w_file, w1->w_line); 1304578Srgrimes printf(" 3rd %p %s @ %s:%d\n", 1305578Srgrimes m, w->w_description, file, line); 130613732Sache#ifdef DDB 1307578Srgrimes go_into_ddb = 1; 1308578Srgrimes#endif /* DDB */ 13091197Srgrimes goto out; 1310104445Smdodd } 1311578Srgrimes } 1312578Srgrimes m1 = LIST_FIRST(&p->p_heldmtx); 13136604Sache if (!itismychild(m1->mtx_witness, w)) 1314106490Smdodd mtx_exit(&w_mtx, MTX_SPIN | MTX_QUIET); 1315106490Smdodd 1316106490Smdoddout: 1317106490Smdodd#ifdef DDB 1318104445Smdodd if (witness_ddb && go_into_ddb) 1319104445Smdodd Debugger("witness_enter"); 1320106490Smdodd#endif /* DDB */ 1321106490Smdodd w->w_file = file; 13226604Sache w->w_line = line; 1323106490Smdodd m->mtx_line = line; 1324104445Smdodd m->mtx_file = file; 1325106490Smdodd 1326106490Smdodd /* 1327106490Smdodd * If this pays off it likely means that a mutex being witnessed 1328578Srgrimes * is acquired in hardclock. Put it in the ignore list. It is 1329578Srgrimes * likely not the mutex this assert fails on. 13301197Srgrimes */ 1331104445Smdodd MPASS(m->mtx_held.le_prev == NULL); 1332578Srgrimes LIST_INSERT_HEAD(&p->p_heldmtx, (struct mtx*)m, mtx_held); 1333578Srgrimes} 1334104445Smdodd 1335106490Smdoddvoid 1336104445Smdoddwitness_try_enter(struct mtx *m, int flags, const char *file, int line) 1337106490Smdodd{ 1338106490Smdodd struct proc *p; 1339104445Smdodd struct witness *w = m->mtx_witness; 1340104445Smdodd 1341104445Smdodd if (witness_cold) 1342104445Smdodd return; 1343104445Smdodd if (panicstr) 1344104445Smdodd return; 1345104445Smdodd if (flags & MTX_SPIN) { 1346104445Smdodd if (!(w->w_spin)) 1347104445Smdodd panic("mutex_try_enter: " 1348104445Smdodd "MTX_SPIN on MTX_DEF mutex %s @ %s:%d", 1349104445Smdodd m->mtx_description, file, line); 13501197Srgrimes if (mtx_recursed(m)) { 1351106490Smdodd if (!(w->w_recurse)) 1352578Srgrimes panic("mutex_try_enter: recursion on" 1353578Srgrimes " non-recursive mutex %s @ %s:%d", 13541197Srgrimes m->mtx_description, file, line); 1355141031Ssobomax return; 1356578Srgrimes } 1357578Srgrimes mtx_enter(&w_mtx, MTX_SPIN | MTX_QUIET); 1358578Srgrimes PCPU_SET(witness_spin_check, 135913770Sache PCPU_GET(witness_spin_check) | w->w_level); 1360578Srgrimes mtx_exit(&w_mtx, MTX_SPIN | MTX_QUIET); 1361106490Smdodd w->w_file = file; 1362104445Smdodd w->w_line = line; 1363104445Smdodd m->mtx_line = line; 1364104445Smdodd m->mtx_file = file; 13652477Sache return; 1366104445Smdodd } 1367104445Smdodd 1368106490Smdodd if (w->w_spin) 13692477Sache panic("mutex_try_enter: MTX_DEF on MTX_SPIN mutex %s @ %s:%d", 1370104445Smdodd m->mtx_description, file, line); 1371104445Smdodd 1372106490Smdodd if (mtx_recursed(m)) { 13732477Sache if (!(w->w_recurse)) 1374104445Smdodd panic("mutex_try_enter: recursion on non-recursive" 1375106490Smdodd " mutex %s @ %s:%d", m->mtx_description, file, 13762477Sache line); 1377104445Smdodd return; 1378106490Smdodd } 1379578Srgrimes w->w_file = file; 1380106490Smdodd w->w_line = line; 1381104445Smdodd m->mtx_line = line; 138213886Sache m->mtx_file = file; 1383104445Smdodd p = CURPROC; 138413886Sache MPASS(m->mtx_held.le_prev == NULL); 138513886Sache LIST_INSERT_HEAD(&p->p_heldmtx, (struct mtx*)m, mtx_held); 138613886Sache} 138713732Sache 138813886Sachevoid 138913886Sachewitness_exit(struct mtx *m, int flags, const char *file, int line) 139013886Sache{ 139113886Sache struct witness *w; 139213886Sache 139313886Sache if (witness_cold || m->mtx_witness == NULL || panicstr) 1394104445Smdodd return; 139513886Sache w = m->mtx_witness; 139613886Sache 139713886Sache if (flags & MTX_SPIN) { 139813886Sache if (!(w->w_spin)) 139913886Sache panic("mutex_exit: MTX_SPIN on MTX_DEF mutex %s @" 140013886Sache " %s:%d", m->mtx_description, file, line); 140113886Sache if (mtx_recursed(m)) { 140213886Sache if (!(w->w_recurse)) 140313886Sache panic("mutex_exit: recursion on non-recursive" 140413886Sache " mutex %s @ %s:%d", m->mtx_description, 140513886Sache file, line); 140613886Sache return; 140713886Sache } 140813886Sache mtx_enter(&w_mtx, MTX_SPIN | MTX_QUIET); 140913886Sache PCPU_SET(witness_spin_check, 141013886Sache PCPU_GET(witness_spin_check) & ~w->w_level); 141113886Sache mtx_exit(&w_mtx, MTX_SPIN | MTX_QUIET); 141213886Sache return; 141313886Sache } 141413886Sache if (w->w_spin) 141513886Sache panic("mutex_exit: MTX_DEF on MTX_SPIN mutex %s @ %s:%d", 141613886Sache m->mtx_description, file, line); 141713886Sache 141813732Sache if (mtx_recursed(m)) { 14196665Sache if (!(w->w_recurse)) 1420578Srgrimes panic("mutex_exit: recursion on non-recursive" 1421141031Ssobomax " mutex %s @ %s:%d", m->mtx_description, 1422141031Ssobomax file, line); 1423141031Ssobomax return; 1424141061Smaxim } 1425578Srgrimes 1426578Srgrimes if ((flags & MTX_NOSWITCH) == 0 && !mtx_legal2block() && !cold) 14271197Srgrimes panic("switchable mtx_exit() of %s when not legal @ %s:%d", 1428104445Smdodd m->mtx_description, file, line); 14292477Sache LIST_REMOVE(m, mtx_held); 14302477Sache m->mtx_held.le_prev = NULL; 14312477Sache} 1432106490Smdodd 1433104445Smdoddint 143413833Sachewitness_sleep(int check_only, struct mtx *mtx, const char *file, int line) 143513833Sache{ 143613833Sache struct mtx *m; 143713833Sache struct proc *p; 143813833Sache char **sleep; 143913833Sache int n = 0; 1440106490Smdodd 1441106490Smdodd KASSERT(!witness_cold, ("%s: witness_cold\n", __FUNCTION__)); 1442106490Smdodd p = CURPROC; 1443106490Smdodd for ((m = LIST_FIRST(&p->p_heldmtx)); m != NULL; 144413833Sache m = LIST_NEXT(m, mtx_held)) { 144513833Sache if (m == mtx) 144613833Sache continue; 144713833Sache for (sleep = sleep_list; *sleep!= NULL; sleep++) 144813833Sache if (strcmp(m->mtx_description, *sleep) == 0) 144913833Sache goto next; 145013833Sache printf("%s:%d: %s with \"%s\" locked from %s:%d\n", 145113833Sache file, line, check_only ? "could sleep" : "sleeping", 1452104445Smdodd m->mtx_description, 1453106490Smdodd m->mtx_witness->w_file, m->mtx_witness->w_line); 14542477Sache n++; 1455104445Smdodd next: 14562477Sache } 14572477Sache#ifdef DDB 14582477Sache if (witness_ddb && n) 1459104445Smdodd Debugger("witness_sleep"); 1460578Srgrimes#endif /* DDB */ 1461578Srgrimes return (n); 1462578Srgrimes} 1463578Srgrimes 14644390Sachestatic struct witness * 1465578Srgrimesenroll(const char *description, int flag) 1466104445Smdodd{ 1467106490Smdodd int i; 1468578Srgrimes struct witness *w, *w1; 1469106490Smdodd char **ignore; 1470104445Smdodd char **order; 14712477Sache 14722477Sache if (!witness_watch) 1473106490Smdodd return (NULL); 1474106490Smdodd for (ignore = ignore_list; *ignore != NULL; ignore++) 14752477Sache if (strcmp(description, *ignore) == 0) 1476106490Smdodd return (NULL); 1477106490Smdodd 1478106490Smdodd if (w_inited == 0) { 1479578Srgrimes mtx_init(&w_mtx, "witness lock", MTX_SPIN); 14804390Sache for (i = 0; i < WITNESS_COUNT; i++) { 1481106490Smdodd w = &w_data[i]; 1482106490Smdodd witness_free(w); 14834390Sache } 1484578Srgrimes w_inited = 1; 1485104445Smdodd for (order = order_list; *order != NULL; order++) { 1486106490Smdodd w = enroll(*order, MTX_DEF); 148713833Sache w->w_file = "order list"; 1488104445Smdodd for (order++; *order != NULL; order++) { 1489578Srgrimes w1 = enroll(*order, MTX_DEF); 1490578Srgrimes w1->w_file = "order list"; 14911197Srgrimes itismychild(w, w1); 1492104445Smdodd w = w1; 149313833Sache } 149413833Sache } 149513833Sache } 1496106490Smdodd if ((flag & MTX_SPIN) && witness_skipspin) 1497104445Smdodd return (NULL); 1498104445Smdodd mtx_enter(&w_mtx, MTX_SPIN | MTX_QUIET); 149913833Sache for (w = w_all; w; w = w->w_next) { 1500106490Smdodd if (strcmp(description, w->w_description) == 0) { 150113833Sache mtx_exit(&w_mtx, MTX_SPIN | MTX_QUIET); 1502106490Smdodd return (w); 1503106490Smdodd } 150413833Sache } 150513833Sache if ((w = witness_get()) == NULL) 150613833Sache return (NULL); 150713833Sache w->w_next = w_all; 1508104445Smdodd w_all = w; 1509106490Smdodd w->w_description = description; 151013833Sache mtx_exit(&w_mtx, MTX_SPIN | MTX_QUIET); 1511104445Smdodd if (flag & MTX_SPIN) { 151213833Sache w->w_spin = 1; 151313833Sache 151413833Sache i = 1; 1515104445Smdodd for (order = spin_order_list; *order != NULL; order++) { 1516578Srgrimes if (strcmp(description, *order) == 0) 15172477Sache break; 1518578Srgrimes i <<= 1; 1519106490Smdodd } 15201197Srgrimes if (*order == NULL) 15212477Sache panic("spin lock %s not in order list", description); 1522106719Smdodd w->w_level = i; 1523104445Smdodd } else 1524104445Smdodd w->w_sleep = 1; 1525104445Smdodd 1526104445Smdodd if (flag & MTX_RECURSE) 1527104445Smdodd w->w_recurse = 1; 1528104445Smdodd 1529104445Smdodd return (w); 1530106719Smdodd} 15312477Sache 1532104445Smdoddstatic int 15332477Sacheitismychild(struct witness *parent, struct witness *child) 15342477Sache{ 15352477Sache static int recursed; 15362477Sache 15372477Sache /* 1538578Srgrimes * Insert "child" after "parent" 1539578Srgrimes */ 15402477Sache while (parent->w_morechildren) 1541104445Smdodd parent = parent->w_morechildren; 1542106490Smdodd 15431197Srgrimes if (parent->w_childcnt == WITNESS_NCHILDREN) { 1544106490Smdodd if ((parent->w_morechildren = witness_get()) == NULL) 1545104445Smdodd return (1); 1546104445Smdodd parent = parent->w_morechildren; 15472477Sache } 1548106490Smdodd MPASS(child != NULL); 1549106490Smdodd parent->w_children[parent->w_childcnt++] = child; 1550106490Smdodd /* 1551578Srgrimes * now prune whole tree 1552578Srgrimes */ 15531197Srgrimes if (recursed) 1554104445Smdodd return (0); 1555578Srgrimes recursed = 1; 1556578Srgrimes for (child = w_all; child != NULL; child = child->w_next) { 1557578Srgrimes for (parent = w_all; parent != NULL; 1558578Srgrimes parent = parent->w_next) { 1559578Srgrimes if (!isitmychild(parent, child)) 1560106490Smdodd continue; 1561106490Smdodd removechild(parent, child); 1562106490Smdodd if (isitmydescendant(parent, child)) 1563104445Smdodd continue; 1564104445Smdodd itismychild(parent, child); 1565106490Smdodd } 1566106490Smdodd } 1567578Srgrimes recursed = 0; 1568578Srgrimes witness_levelall(); 1569578Srgrimes return (0); 1570104445Smdodd} 1571106490Smdodd 1572578Srgrimesstatic void 1573578Srgrimesremovechild(struct witness *parent, struct witness *child) 1574106490Smdodd{ 1575106490Smdodd struct witness *w, *w1; 1576106490Smdodd int i; 1577578Srgrimes 1578578Srgrimes for (w = parent; w != NULL; w = w->w_morechildren) 1579104445Smdodd for (i = 0; i < w->w_childcnt; i++) 1580106490Smdodd if (w->w_children[i] == child) 1581578Srgrimes goto found; 1582578Srgrimes return; 1583106490Smdoddfound: 1584106490Smdodd for (w1 = w; w1->w_morechildren != NULL; w1 = w1->w_morechildren) 1585578Srgrimes continue; 1586578Srgrimes w->w_children[i] = w1->w_children[--w1->w_childcnt]; 15871197Srgrimes MPASS(w->w_children[i] != NULL); 1588104445Smdodd 1589578Srgrimes if (w1->w_childcnt != 0) 1590578Srgrimes return; 1591106490Smdodd 1592106490Smdodd if (w1 == parent) 1593106490Smdodd return; 1594578Srgrimes for (w = parent; w->w_morechildren != w1; w = w->w_morechildren) 1595 continue; 1596 w->w_morechildren = 0; 1597 witness_free(w1); 1598} 1599 1600static int 1601isitmychild(struct witness *parent, struct witness *child) 1602{ 1603 struct witness *w; 1604 int i; 1605 1606 for (w = parent; w != NULL; w = w->w_morechildren) { 1607 for (i = 0; i < w->w_childcnt; i++) { 1608 if (w->w_children[i] == child) 1609 return (1); 1610 } 1611 } 1612 return (0); 1613} 1614 1615static int 1616isitmydescendant(struct witness *parent, struct witness *child) 1617{ 1618 struct witness *w; 1619 int i; 1620 int j; 1621 1622 for (j = 0, w = parent; w != NULL; w = w->w_morechildren, j++) { 1623 MPASS(j < 1000); 1624 for (i = 0; i < w->w_childcnt; i++) { 1625 if (w->w_children[i] == child) 1626 return (1); 1627 } 1628 for (i = 0; i < w->w_childcnt; i++) { 1629 if (isitmydescendant(w->w_children[i], child)) 1630 return (1); 1631 } 1632 } 1633 return (0); 1634} 1635 1636void 1637witness_levelall (void) 1638{ 1639 struct witness *w, *w1; 1640 1641 for (w = w_all; w; w = w->w_next) 1642 if (!(w->w_spin)) 1643 w->w_level = 0; 1644 for (w = w_all; w; w = w->w_next) { 1645 if (w->w_spin) 1646 continue; 1647 for (w1 = w_all; w1; w1 = w1->w_next) { 1648 if (isitmychild(w1, w)) 1649 break; 1650 } 1651 if (w1 != NULL) 1652 continue; 1653 witness_leveldescendents(w, 0); 1654 } 1655} 1656 1657static void 1658witness_leveldescendents(struct witness *parent, int level) 1659{ 1660 int i; 1661 struct witness *w; 1662 1663 if (parent->w_level < level) 1664 parent->w_level = level; 1665 level++; 1666 for (w = parent; w != NULL; w = w->w_morechildren) 1667 for (i = 0; i < w->w_childcnt; i++) 1668 witness_leveldescendents(w->w_children[i], level); 1669} 1670 1671static void 1672witness_displaydescendants(void(*prnt)(const char *fmt, ...), 1673 struct witness *parent) 1674{ 1675 struct witness *w; 1676 int i; 1677 int level = parent->w_level; 1678 1679 prnt("%d", level); 1680 if (level < 10) 1681 prnt(" "); 1682 for (i = 0; i < level; i++) 1683 prnt(" "); 1684 prnt("%s", parent->w_description); 1685 if (parent->w_file != NULL) { 1686 prnt(" -- last acquired @ %s", parent->w_file); 1687#ifndef W_USE_WHERE 1688 prnt(":%d", parent->w_line); 1689#endif 1690 prnt("\n"); 1691 } 1692 1693 for (w = parent; w != NULL; w = w->w_morechildren) 1694 for (i = 0; i < w->w_childcnt; i++) 1695 witness_displaydescendants(prnt, w->w_children[i]); 1696 } 1697 1698static int 1699dup_ok(struct witness *w) 1700{ 1701 char **dup; 1702 1703 for (dup = dup_list; *dup!= NULL; dup++) 1704 if (strcmp(w->w_description, *dup) == 0) 1705 return (1); 1706 return (0); 1707} 1708 1709static int 1710blessed(struct witness *w1, struct witness *w2) 1711{ 1712 int i; 1713 struct witness_blessed *b; 1714 1715 for (i = 0; i < blessed_count; i++) { 1716 b = &blessed_list[i]; 1717 if (strcmp(w1->w_description, b->b_lock1) == 0) { 1718 if (strcmp(w2->w_description, b->b_lock2) == 0) 1719 return (1); 1720 continue; 1721 } 1722 if (strcmp(w1->w_description, b->b_lock2) == 0) 1723 if (strcmp(w2->w_description, b->b_lock1) == 0) 1724 return (1); 1725 } 1726 return (0); 1727} 1728 1729static struct witness * 1730witness_get() 1731{ 1732 struct witness *w; 1733 1734 if ((w = w_free) == NULL) { 1735 witness_dead = 1; 1736 mtx_exit(&w_mtx, MTX_SPIN | MTX_QUIET); 1737 printf("witness exhausted\n"); 1738 return (NULL); 1739 } 1740 w_free = w->w_next; 1741 bzero(w, sizeof(*w)); 1742 return (w); 1743} 1744 1745static void 1746witness_free(struct witness *w) 1747{ 1748 w->w_next = w_free; 1749 w_free = w; 1750} 1751 1752int 1753witness_list(struct proc *p) 1754{ 1755 struct mtx *m; 1756 int nheld; 1757 1758 KASSERT(!witness_cold, ("%s: witness_cold\n", __FUNCTION__)); 1759 nheld = 0; 1760 for ((m = LIST_FIRST(&p->p_heldmtx)); m != NULL; 1761 m = LIST_NEXT(m, mtx_held)) { 1762 printf("\t\"%s\" (%p) locked at %s:%d\n", 1763 m->mtx_description, m, 1764 m->mtx_witness->w_file, m->mtx_witness->w_line); 1765 nheld++; 1766 } 1767 1768 return (nheld); 1769} 1770 1771void 1772witness_save(struct mtx *m, const char **filep, int *linep) 1773{ 1774 1775 KASSERT(!witness_cold, ("%s: witness_cold\n", __FUNCTION__)); 1776 if (m->mtx_witness == NULL) 1777 return; 1778 1779 *filep = m->mtx_witness->w_file; 1780 *linep = m->mtx_witness->w_line; 1781} 1782 1783void 1784witness_restore(struct mtx *m, const char *file, int line) 1785{ 1786 1787 KASSERT(!witness_cold, ("%s: witness_cold\n", __FUNCTION__)); 1788 if (m->mtx_witness == NULL) 1789 return; 1790 1791 m->mtx_witness->w_file = file; 1792 m->mtx_witness->w_line = line; 1793} 1794 1795#endif /* WITNESS */ 1796