subr_turnstile.c revision 69879
1829SN/A/*- 27424SN/A * Copyright (c) 1998 Berkeley Software Design, Inc. All rights reserved. 3829SN/A * 4829SN/A * Redistribution and use in source and binary forms, with or without 5829SN/A * modification, are permitted provided that the following conditions 6829SN/A * are met: 72362SN/A * 1. Redistributions of source code must retain the above copyright 8829SN/A * notice, this list of conditions and the following disclaimer. 92362SN/A * 2. Redistributions in binary form must reproduce the above copyright 10829SN/A * notice, this list of conditions and the following disclaimer in the 11829SN/A * documentation and/or other materials provided with the distribution. 12829SN/A * 3. Berkeley Software Design Inc's name may not be used to endorse or 13829SN/A * promote products derived from this software without specific prior 14829SN/A * written permission. 15829SN/A * 16829SN/A * THIS SOFTWARE IS PROVIDED BY BERKELEY SOFTWARE DESIGN INC ``AS IS'' AND 17829SN/A * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 18829SN/A * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 19829SN/A * ARE DISCLAIMED. IN NO EVENT SHALL BERKELEY SOFTWARE DESIGN INC BE LIABLE 20829SN/A * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 212362SN/A * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 222362SN/A * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 232362SN/A * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 24829SN/A * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 2515409Sserb * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 26829SN/A * SUCH DAMAGE. 27829SN/A * 28829SN/A * from BSDI $Id: mutex_witness.c,v 1.1.2.20 2000/04/27 03:10:27 cp Exp $ 29829SN/A * and BSDI $Id: synch_machdep.c,v 2.3.2.39 2000/04/27 03:10:25 cp Exp $ 30829SN/A * $FreeBSD: head/sys/kern/subr_turnstile.c 69879 2000-12-12 00:37:18Z jhb $ 31829SN/A */ 32829SN/A 33829SN/A/* 34829SN/A * Main Entry: witness 35829SN/A * Pronunciation: 'wit-n&s 36829SN/A * Function: noun 37829SN/A * Etymology: Middle English witnesse, from Old English witnes knowledge, 38829SN/A * testimony, witness, from 2wit 397424SN/A * Date: before 12th century 40829SN/A * 1 : attestation of a fact or event : TESTIMONY 4112839Sprr * 2 : one that gives evidence; specifically : one who testifies in 42829SN/A * a cause or before a judicial tribunal 43829SN/A * 3 : one asked to be present at a transaction so as to be able to 44829SN/A * testify to its having taken place 45829SN/A * 4 : one who has personal knowledge of something 46829SN/A * 5 a : something serving as evidence or proof : SIGN 47829SN/A * b : public affirmation by word or example of usually 48829SN/A * religious faith or conviction <the heroic witness to divine 49829SN/A * life -- Pilot> 50829SN/A * 6 capitalized : a member of the Jehovah's Witnesses 51829SN/A */ 52829SN/A 53829SN/A#include "opt_ddb.h" 54829SN/A#include "opt_witness.h" 55829SN/A 56829SN/A/* 57829SN/A * Cause non-inlined mtx_*() to be compiled. 58829SN/A * Must be defined early because other system headers may include mutex.h. 59829SN/A */ 60829SN/A#define _KERN_MUTEX_C_ 61829SN/A 62829SN/A#include <sys/param.h> 63829SN/A#include <sys/bus.h> 64829SN/A#include <sys/kernel.h> 65829SN/A#include <sys/malloc.h> 66829SN/A#include <sys/proc.h> 67829SN/A#include <sys/sysctl.h> 68829SN/A#include <sys/systm.h> 69829SN/A#include <sys/vmmeter.h> 70829SN/A#include <sys/ktr.h> 71829SN/A 72829SN/A#include <machine/atomic.h> 73829SN/A#include <machine/bus.h> 74829SN/A#include <machine/clock.h> 75829SN/A#include <machine/cpu.h> 76829SN/A 77829SN/A#include <ddb/ddb.h> 78829SN/A 79829SN/A#include <vm/vm.h> 80829SN/A#include <vm/vm_extern.h> 81829SN/A 82829SN/A#include <sys/mutex.h> 83829SN/A 84829SN/A/* 85829SN/A * Machine independent bits of the mutex implementation 86829SN/A */ 87829SN/A/* All mutexes in system (used for debug/panic) */ 88829SN/A#ifdef WITNESS 89829SN/Astatic struct mtx_debug all_mtx_debug = { NULL, {NULL, NULL}, NULL, 0, 90829SN/A "All mutexes queue head" }; 91829SN/Astatic struct mtx all_mtx = { MTX_UNOWNED, 0, 0, &all_mtx_debug, 92829SN/A TAILQ_HEAD_INITIALIZER(all_mtx.mtx_blocked), 93829SN/A { NULL, NULL }, &all_mtx, &all_mtx }; 94829SN/A#else /* WITNESS */ 95829SN/Astatic struct mtx all_mtx = { MTX_UNOWNED, 0, 0, "All mutexes queue head", 96829SN/A TAILQ_HEAD_INITIALIZER(all_mtx.mtx_blocked), 97829SN/A { NULL, NULL }, &all_mtx, &all_mtx }; 98829SN/A#endif /* WITNESS */ 99829SN/A 100829SN/Astatic int mtx_cur_cnt; 101829SN/Astatic int mtx_max_cnt; 102829SN/A 103829SN/Avoid _mtx_enter_giant_def(void); 104829SN/Avoid _mtx_exit_giant_def(void); 105829SN/Astatic void propagate_priority(struct proc *); 106829SN/A 107829SN/A#define mtx_unowned(m) ((m)->mtx_lock == MTX_UNOWNED) 108829SN/A#define mtx_owner(m) (mtx_unowned(m) ? NULL \ 109829SN/A : (struct proc *)((m)->mtx_lock & MTX_FLAGMASK)) 110829SN/A 111829SN/A#define RETIP(x) *(((uintptr_t *)(&x)) - 1) 112829SN/A#define SET_PRIO(p, pri) (p)->p_priority = (pri) 113829SN/A 114829SN/A/* 115829SN/A * XXX Temporary, for use from assembly language 116829SN/A */ 117829SN/A 118829SN/Avoid 119829SN/A_mtx_enter_giant_def(void) 120829SN/A{ 121829SN/A 122829SN/A mtx_enter(&Giant, MTX_DEF); 123829SN/A} 124829SN/A 125829SN/Avoid 126829SN/A_mtx_exit_giant_def(void) 127829SN/A{ 128829SN/A 129829SN/A mtx_exit(&Giant, MTX_DEF); 130829SN/A} 131829SN/A 132829SN/Astatic void 133829SN/Apropagate_priority(struct proc *p) 134829SN/A{ 135829SN/A int pri = p->p_priority; 136829SN/A struct mtx *m = p->p_blocked; 137829SN/A 138829SN/A mtx_assert(&sched_lock, MA_OWNED); 139829SN/A for (;;) { 140829SN/A struct proc *p1; 141829SN/A 142829SN/A p = mtx_owner(m); 143829SN/A 144829SN/A if (p == NULL) { 145829SN/A /* 146829SN/A * This really isn't quite right. Really 147829SN/A * ought to bump priority of process that 148829SN/A * next acquires the mutex. 149829SN/A */ 150829SN/A MPASS(m->mtx_lock == MTX_CONTESTED); 151829SN/A return; 152829SN/A } 153829SN/A MPASS(p->p_magic == P_MAGIC); 154829SN/A KASSERT(p->p_stat != SSLEEP, ("sleeping process owns a mutex")); 155829SN/A if (p->p_priority <= pri) 156829SN/A return; 157829SN/A 158829SN/A /* 159829SN/A * Bump this process' priority. 160829SN/A */ 161829SN/A SET_PRIO(p, pri); 162829SN/A 163829SN/A /* 164829SN/A * If lock holder is actually running, just bump priority. 165829SN/A */ 166829SN/A#ifdef SMP 167829SN/A /* 168829SN/A * For SMP, we can check the p_oncpu field to see if we are 169829SN/A * running. 170829SN/A */ 171829SN/A if (p->p_oncpu != 0xff) { 172829SN/A MPASS(p->p_stat == SRUN || p->p_stat == SZOMB); 173829SN/A return; 174829SN/A } 175829SN/A#else 176829SN/A /* 177829SN/A * For UP, we check to see if p is curproc (this shouldn't 178829SN/A * ever happen however as it would mean we are in a deadlock.) 179829SN/A */ 180829SN/A if (p == curproc) { 181829SN/A panic("Deadlock detected"); 182829SN/A return; 183829SN/A } 184829SN/A#endif 185829SN/A /* 186829SN/A * If on run queue move to new run queue, and 187829SN/A * quit. 188829SN/A */ 189829SN/A if (p->p_stat == SRUN) { 190829SN/A printf("XXX: moving process %d(%s) to a new run queue\n", 191829SN/A p->p_pid, p->p_comm); 192829SN/A MPASS(p->p_blocked == NULL); 193829SN/A remrunqueue(p); 194829SN/A setrunqueue(p); 195829SN/A return; 196829SN/A } 197829SN/A 198829SN/A /* 199829SN/A * If we aren't blocked on a mutex, we should be. 200829SN/A */ 201829SN/A KASSERT(p->p_stat == SMTX, ( 202829SN/A "process %d(%s):%d holds %s but isn't blocked on a mutex\n", 203829SN/A p->p_pid, p->p_comm, p->p_stat, 204829SN/A m->mtx_description)); 205829SN/A 206829SN/A /* 207829SN/A * Pick up the mutex that p is blocked on. 208829SN/A */ 209829SN/A m = p->p_blocked; 210829SN/A MPASS(m != NULL); 211829SN/A 212829SN/A printf("XXX: process %d(%s) is blocked on %s\n", p->p_pid, 213829SN/A p->p_comm, m->mtx_description); 214829SN/A /* 215829SN/A * Check if the proc needs to be moved up on 216829SN/A * the blocked chain 217829SN/A */ 218829SN/A if (p == TAILQ_FIRST(&m->mtx_blocked)) { 219829SN/A printf("XXX: process at head of run queue\n"); 220829SN/A continue; 221829SN/A } 222829SN/A p1 = TAILQ_PREV(p, rq, p_procq); 223829SN/A if (p1->p_priority <= pri) { 224829SN/A printf( 225829SN/A "XXX: previous process %d(%s) has higher priority\n", 226829SN/A p->p_pid, p->p_comm); 227829SN/A continue; 228829SN/A } 229829SN/A 230829SN/A /* 231829SN/A * Remove proc from blocked chain and determine where 232829SN/A * it should be moved up to. Since we know that p1 has 233829SN/A * a lower priority than p, we know that at least one 234829SN/A * process in the chain has a lower priority and that 235829SN/A * p1 will thus not be NULL after the loop. 236829SN/A */ 237829SN/A TAILQ_REMOVE(&m->mtx_blocked, p, p_procq); 238829SN/A TAILQ_FOREACH(p1, &m->mtx_blocked, p_procq) { 239829SN/A MPASS(p1->p_magic == P_MAGIC); 240829SN/A if (p1->p_priority > pri) 241829SN/A break; 242829SN/A } 243829SN/A MPASS(p1 != NULL); 244829SN/A TAILQ_INSERT_BEFORE(p1, p, p_procq); 245829SN/A CTR4(KTR_LOCK, 246829SN/A "propagate_priority: p 0x%p moved before 0x%p on [0x%p] %s", 247829SN/A p, p1, m, m->mtx_description); 248829SN/A } 249829SN/A} 250829SN/A 251829SN/Avoid 252829SN/Amtx_enter_hard(struct mtx *m, int type, int saveintr) 253829SN/A{ 254829SN/A struct proc *p = CURPROC; 255829SN/A 256829SN/A KASSERT(p != NULL, ("curproc is NULL in mutex")); 257829SN/A 258829SN/A switch (type) { 259829SN/A case MTX_DEF: 260829SN/A if ((m->mtx_lock & MTX_FLAGMASK) == (uintptr_t)p) { 261829SN/A m->mtx_recurse++; 262829SN/A atomic_set_ptr(&m->mtx_lock, MTX_RECURSE); 263829SN/A CTR1(KTR_LOCK, "mtx_enter: 0x%p recurse", m); 264829SN/A return; 265829SN/A } 266829SN/A CTR3(KTR_LOCK, "mtx_enter: 0x%p contested (lock=%p) [0x%p]", 267829SN/A m, (void *)m->mtx_lock, (void *)RETIP(m)); 268829SN/A 269829SN/A /* 270829SN/A * Save our priority. Even though p_nativepri is protected 271829SN/A * by sched_lock, we don't obtain it here as it can be 272829SN/A * expensive. Since this is the only place p_nativepri is 273829SN/A * set, and since two CPUs will not be executing the same 274829SN/A * process concurrently, we know that no other CPU is going 275829SN/A * to be messing with this. Also, p_nativepri is only read 276829SN/A * when we are blocked on a mutex, so that can't be happening 277829SN/A * right now either. 278829SN/A */ 279829SN/A p->p_nativepri = p->p_priority; 280829SN/A while (!_obtain_lock(m, p)) { 281829SN/A uintptr_t v; 282829SN/A struct proc *p1; 283829SN/A 284829SN/A mtx_enter(&sched_lock, MTX_SPIN | MTX_RLIKELY); 285829SN/A /* 286829SN/A * check if the lock has been released while 287829SN/A * waiting for the schedlock. 288829SN/A */ 289829SN/A if ((v = m->mtx_lock) == MTX_UNOWNED) { 290829SN/A mtx_exit(&sched_lock, MTX_SPIN); 291829SN/A continue; 292829SN/A } 293829SN/A /* 294829SN/A * The mutex was marked contested on release. This 295829SN/A * means that there are processes blocked on it. 296829SN/A */ 297829SN/A if (v == MTX_CONTESTED) { 298829SN/A p1 = TAILQ_FIRST(&m->mtx_blocked); 299829SN/A KASSERT(p1 != NULL, ("contested mutex has no contesters")); 300829SN/A KASSERT(p != NULL, ("curproc is NULL for contested mutex")); 301829SN/A m->mtx_lock = (uintptr_t)p | MTX_CONTESTED; 302829SN/A if (p1->p_priority < p->p_priority) { 303829SN/A SET_PRIO(p, p1->p_priority); 304829SN/A } 305829SN/A mtx_exit(&sched_lock, MTX_SPIN); 306829SN/A return; 307829SN/A } 308829SN/A /* 309829SN/A * If the mutex isn't already contested and 310829SN/A * a failure occurs setting the contested bit the 311829SN/A * mutex was either release or the 312829SN/A * state of the RECURSION bit changed. 313829SN/A */ 314829SN/A if ((v & MTX_CONTESTED) == 0 && 315829SN/A !atomic_cmpset_ptr(&m->mtx_lock, (void *)v, 316829SN/A (void *)(v | MTX_CONTESTED))) { 317829SN/A mtx_exit(&sched_lock, MTX_SPIN); 318829SN/A continue; 319829SN/A } 320829SN/A 321829SN/A /* We definitely have to sleep for this lock */ 322829SN/A mtx_assert(m, MA_NOTOWNED); 323829SN/A 324829SN/A#ifdef notyet 325829SN/A /* 326829SN/A * If we're borrowing an interrupted thread's VM 327829SN/A * context must clean up before going to sleep. 328829SN/A */ 329829SN/A if (p->p_flag & (P_ITHD | P_SITHD)) { 330829SN/A ithd_t *it = (ithd_t *)p; 331829SN/A 332829SN/A if (it->it_interrupted) { 333829SN/A CTR2(KTR_LOCK, 334829SN/A "mtx_enter: 0x%x interrupted 0x%x", 335829SN/A it, it->it_interrupted); 336829SN/A intr_thd_fixup(it); 337829SN/A } 338829SN/A } 339829SN/A#endif 340829SN/A 341829SN/A /* Put us on the list of procs blocked on this mutex */ 342829SN/A if (TAILQ_EMPTY(&m->mtx_blocked)) { 343829SN/A p1 = (struct proc *)(m->mtx_lock & 344829SN/A MTX_FLAGMASK); 345829SN/A LIST_INSERT_HEAD(&p1->p_contested, m, 346829SN/A mtx_contested); 347829SN/A TAILQ_INSERT_TAIL(&m->mtx_blocked, p, p_procq); 348829SN/A } else { 349829SN/A TAILQ_FOREACH(p1, &m->mtx_blocked, p_procq) 350829SN/A if (p1->p_priority > p->p_priority) 351829SN/A break; 352829SN/A if (p1) 353829SN/A TAILQ_INSERT_BEFORE(p1, p, p_procq); 354829SN/A else 355829SN/A TAILQ_INSERT_TAIL(&m->mtx_blocked, p, 356829SN/A p_procq); 357829SN/A } 358829SN/A 359829SN/A p->p_blocked = m; /* Who we're blocked on */ 360829SN/A p->p_mtxname = m->mtx_description; 361829SN/A p->p_stat = SMTX; 362829SN/A#if 0 363829SN/A propagate_priority(p); 364829SN/A#endif 365829SN/A CTR3(KTR_LOCK, "mtx_enter: p 0x%p blocked on [0x%p] %s", 366829SN/A p, m, m->mtx_description); 367829SN/A mi_switch(); 368829SN/A CTR3(KTR_LOCK, 369829SN/A "mtx_enter: p 0x%p free from blocked on [0x%p] %s", 370829SN/A p, m, m->mtx_description); 371829SN/A mtx_exit(&sched_lock, MTX_SPIN); 372829SN/A } 373829SN/A return; 374829SN/A case MTX_SPIN: 375829SN/A case MTX_SPIN | MTX_FIRST: 376829SN/A case MTX_SPIN | MTX_TOPHALF: 377829SN/A { 378829SN/A int i = 0; 379829SN/A 380829SN/A if (m->mtx_lock == (uintptr_t)p) { 381829SN/A m->mtx_recurse++; 382829SN/A return; 383829SN/A } 384829SN/A CTR1(KTR_LOCK, "mtx_enter: %p spinning", m); 385829SN/A for (;;) { 386829SN/A if (_obtain_lock(m, p)) 387829SN/A break; 388829SN/A while (m->mtx_lock != MTX_UNOWNED) { 389829SN/A if (i++ < 1000000) 390829SN/A continue; 391829SN/A if (i++ < 6000000) 392829SN/A DELAY (1); 393829SN/A#ifdef DDB 394829SN/A else if (!db_active) 395829SN/A#else 396829SN/A else 397829SN/A#endif 398829SN/A panic( 399829SN/A "spin lock %s held by 0x%p for > 5 seconds", 400829SN/A m->mtx_description, 401829SN/A (void *)m->mtx_lock); 402829SN/A } 403829SN/A } 404829SN/A 405829SN/A#ifdef MUTEX_DEBUG 406829SN/A if (type != MTX_SPIN) 407829SN/A m->mtx_saveintr = 0xbeefface; 408829SN/A else 409829SN/A#endif 410829SN/A m->mtx_saveintr = saveintr; 411829SN/A CTR1(KTR_LOCK, "mtx_enter: 0x%p spin done", m); 412829SN/A return; 413829SN/A } 414829SN/A } 415829SN/A} 416829SN/A 417829SN/Avoid 418829SN/Amtx_exit_hard(struct mtx *m, int type) 419829SN/A{ 420829SN/A struct proc *p, *p1; 421829SN/A struct mtx *m1; 422829SN/A int pri; 423829SN/A 424829SN/A p = CURPROC; 425829SN/A switch (type) { 426829SN/A case MTX_DEF: 427829SN/A case MTX_DEF | MTX_NOSWITCH: 428829SN/A if (m->mtx_recurse != 0) { 429829SN/A if (--(m->mtx_recurse) == 0) 430829SN/A atomic_clear_ptr(&m->mtx_lock, MTX_RECURSE); 431829SN/A CTR1(KTR_LOCK, "mtx_exit: 0x%p unrecurse", m); 432829SN/A return; 433829SN/A } 434829SN/A mtx_enter(&sched_lock, MTX_SPIN); 435829SN/A CTR1(KTR_LOCK, "mtx_exit: 0x%p contested", m); 436829SN/A p1 = TAILQ_FIRST(&m->mtx_blocked); 437829SN/A MPASS(p->p_magic == P_MAGIC); 438829SN/A MPASS(p1->p_magic == P_MAGIC); 439829SN/A TAILQ_REMOVE(&m->mtx_blocked, p1, p_procq); 440829SN/A if (TAILQ_EMPTY(&m->mtx_blocked)) { 441829SN/A LIST_REMOVE(m, mtx_contested); 442829SN/A _release_lock_quick(m); 443829SN/A CTR1(KTR_LOCK, "mtx_exit: 0x%p not held", m); 444829SN/A } else 445829SN/A atomic_store_rel_ptr(&m->mtx_lock, 446829SN/A (void *)MTX_CONTESTED); 447829SN/A pri = MAXPRI; 448829SN/A LIST_FOREACH(m1, &p->p_contested, mtx_contested) { 449829SN/A int cp = TAILQ_FIRST(&m1->mtx_blocked)->p_priority; 450829SN/A if (cp < pri) 451829SN/A pri = cp; 452829SN/A } 453829SN/A if (pri > p->p_nativepri) 454829SN/A pri = p->p_nativepri; 455829SN/A SET_PRIO(p, pri); 456829SN/A CTR2(KTR_LOCK, "mtx_exit: 0x%p contested setrunqueue 0x%p", 457829SN/A m, p1); 458829SN/A p1->p_blocked = NULL; 459829SN/A p1->p_mtxname = NULL; 460829SN/A p1->p_stat = SRUN; 461829SN/A setrunqueue(p1); 462829SN/A if ((type & MTX_NOSWITCH) == 0 && p1->p_priority < pri) { 463829SN/A#ifdef notyet 464829SN/A if (p->p_flag & (P_ITHD | P_SITHD)) { 465829SN/A ithd_t *it = (ithd_t *)p; 466829SN/A 467829SN/A if (it->it_interrupted) { 468829SN/A CTR2(KTR_LOCK, 469829SN/A "mtx_exit: 0x%x interruped 0x%x", 470829SN/A it, it->it_interrupted); 471829SN/A intr_thd_fixup(it); 472829SN/A } 473829SN/A } 474829SN/A#endif 475829SN/A setrunqueue(p); 476829SN/A CTR2(KTR_LOCK, "mtx_exit: 0x%p switching out lock=0x%p", 477829SN/A m, (void *)m->mtx_lock); 478829SN/A mi_switch(); 479829SN/A CTR2(KTR_LOCK, "mtx_exit: 0x%p resuming lock=0x%p", 480829SN/A m, (void *)m->mtx_lock); 481829SN/A } 482829SN/A mtx_exit(&sched_lock, MTX_SPIN); 483829SN/A break; 484829SN/A case MTX_SPIN: 485829SN/A case MTX_SPIN | MTX_FIRST: 486829SN/A if (m->mtx_recurse != 0) { 487829SN/A m->mtx_recurse--; 488829SN/A return; 489829SN/A } 490829SN/A MPASS(mtx_owned(m)); 491829SN/A _release_lock_quick(m); 492829SN/A if (type & MTX_FIRST) 493829SN/A enable_intr(); /* XXX is this kosher? */ 494829SN/A else { 495829SN/A MPASS(m->mtx_saveintr != 0xbeefface); 496829SN/A restore_intr(m->mtx_saveintr); 497829SN/A } 498829SN/A break; 499829SN/A case MTX_SPIN | MTX_TOPHALF: 500829SN/A if (m->mtx_recurse != 0) { 501829SN/A m->mtx_recurse--; 502829SN/A return; 503829SN/A } 504829SN/A MPASS(mtx_owned(m)); 505829SN/A _release_lock_quick(m); 506829SN/A break; 507829SN/A default: 508829SN/A panic("mtx_exit_hard: unsupported type 0x%x\n", type); 509829SN/A } 510829SN/A} 511829SN/A 512829SN/A#define MV_DESTROY 0 /* validate before destory */ 513829SN/A#define MV_INIT 1 /* validate before init */ 514829SN/A 515829SN/A#ifdef MUTEX_DEBUG 516829SN/A 517829SN/Aint mtx_validate __P((struct mtx *, int)); 518829SN/A 519829SN/Aint 520829SN/Amtx_validate(struct mtx *m, int when) 521829SN/A{ 522829SN/A struct mtx *mp; 523829SN/A int i; 524829SN/A int retval = 0; 525829SN/A 526829SN/A if (m == &all_mtx || cold) 527829SN/A return 0; 528829SN/A 529829SN/A mtx_enter(&all_mtx, MTX_DEF); 530829SN/A/* 531829SN/A * XXX - When kernacc() is fixed on the alpha to handle K0_SEG memory properly 532829SN/A * we can re-enable the kernacc() checks. 533829SN/A */ 534829SN/A#ifndef __alpha__ 535829SN/A MPASS(kernacc((caddr_t)all_mtx.mtx_next, sizeof(uintptr_t), 536829SN/A VM_PROT_READ) == 1); 537829SN/A#endif 538829SN/A MPASS(all_mtx.mtx_next->mtx_prev == &all_mtx); 539829SN/A for (i = 0, mp = all_mtx.mtx_next; mp != &all_mtx; mp = mp->mtx_next) { 540829SN/A#ifndef __alpha__ 541829SN/A if (kernacc((caddr_t)mp->mtx_next, sizeof(uintptr_t), 542829SN/A VM_PROT_READ) != 1) { 543829SN/A panic("mtx_validate: mp=%p mp->mtx_next=%p", 544829SN/A mp, mp->mtx_next); 545829SN/A } 546829SN/A#endif 547829SN/A i++; 548829SN/A if (i > mtx_cur_cnt) { 549829SN/A panic("mtx_validate: too many in chain, known=%d\n", 550829SN/A mtx_cur_cnt); 551829SN/A } 552829SN/A } 553829SN/A MPASS(i == mtx_cur_cnt); 554829SN/A switch (when) { 555829SN/A case MV_DESTROY: 556829SN/A for (mp = all_mtx.mtx_next; mp != &all_mtx; mp = mp->mtx_next) 557829SN/A if (mp == m) 558829SN/A break; 559829SN/A MPASS(mp == m); 560829SN/A break; 561829SN/A case MV_INIT: 562829SN/A for (mp = all_mtx.mtx_next; mp != &all_mtx; mp = mp->mtx_next) 563829SN/A if (mp == m) { 564829SN/A /* 565829SN/A * Not good. This mutex already exists. 566829SN/A */ 567829SN/A printf("re-initing existing mutex %s\n", 568829SN/A m->mtx_description); 569829SN/A MPASS(m->mtx_lock == MTX_UNOWNED); 570829SN/A retval = 1; 571829SN/A } 572829SN/A } 573829SN/A mtx_exit(&all_mtx, MTX_DEF); 574829SN/A return (retval); 575829SN/A} 576829SN/A#endif 577829SN/A 578829SN/Avoid 579829SN/Amtx_init(struct mtx *m, const char *t, int flag) 580829SN/A{ 581829SN/A#ifdef WITNESS 582829SN/A struct mtx_debug *debug; 583829SN/A#endif 584829SN/A 585829SN/A CTR2(KTR_LOCK, "mtx_init 0x%p (%s)", m, t); 586829SN/A#ifdef MUTEX_DEBUG 587829SN/A if (mtx_validate(m, MV_INIT)) /* diagnostic and error correction */ 588829SN/A return; 589829SN/A#endif 590829SN/A#ifdef WITNESS 591829SN/A if (flag & MTX_COLD) 592829SN/A debug = m->mtx_debug; 593829SN/A else 594829SN/A debug = NULL; 595829SN/A if (debug == NULL) { 596829SN/A#ifdef DIAGNOSTIC 597829SN/A if(cold && bootverbose) 598829SN/A printf("malloc'ing mtx_debug while cold for %s\n", t); 599829SN/A#endif 600829SN/A 601829SN/A /* XXX - should not use DEVBUF */ 602829SN/A debug = malloc(sizeof(struct mtx_debug), M_DEVBUF, 603829SN/A M_NOWAIT | M_ZERO); 604829SN/A MPASS(debug != NULL); 605829SN/A } 606829SN/A#endif 607829SN/A bzero((void *)m, sizeof *m); 608829SN/A TAILQ_INIT(&m->mtx_blocked); 609829SN/A#ifdef WITNESS 610829SN/A m->mtx_debug = debug; 611829SN/A#endif 612829SN/A m->mtx_description = t; 613829SN/A m->mtx_lock = MTX_UNOWNED; 614829SN/A /* Put on all mutex queue */ 615829SN/A mtx_enter(&all_mtx, MTX_DEF); 616829SN/A m->mtx_next = &all_mtx; 617829SN/A m->mtx_prev = all_mtx.mtx_prev; 618829SN/A m->mtx_prev->mtx_next = m; 619829SN/A all_mtx.mtx_prev = m; 620829SN/A if (++mtx_cur_cnt > mtx_max_cnt) 621829SN/A mtx_max_cnt = mtx_cur_cnt; 622829SN/A mtx_exit(&all_mtx, MTX_DEF); 623829SN/A witness_init(m, flag); 624829SN/A} 625829SN/A 626829SN/Avoid 627829SN/Amtx_destroy(struct mtx *m) 628829SN/A{ 629829SN/A 630829SN/A CTR2(KTR_LOCK, "mtx_destroy 0x%p (%s)", m, m->mtx_description); 631829SN/A#ifdef MUTEX_DEBUG 632829SN/A if (m->mtx_next == NULL) 633829SN/A panic("mtx_destroy: %p (%s) already destroyed", 634829SN/A m, m->mtx_description); 635829SN/A 636829SN/A if (!mtx_owned(m)) { 637829SN/A MPASS(m->mtx_lock == MTX_UNOWNED); 638829SN/A } else { 639829SN/A MPASS((m->mtx_lock & (MTX_RECURSE|MTX_CONTESTED)) == 0); 640829SN/A } 641829SN/A mtx_validate(m, MV_DESTROY); /* diagnostic */ 642829SN/A#endif 643829SN/A 644829SN/A#ifdef WITNESS 645829SN/A if (m->mtx_witness) 646829SN/A witness_destroy(m); 647829SN/A#endif /* WITNESS */ 648829SN/A 649829SN/A /* Remove from the all mutex queue */ 650829SN/A mtx_enter(&all_mtx, MTX_DEF); 651829SN/A m->mtx_next->mtx_prev = m->mtx_prev; 652829SN/A m->mtx_prev->mtx_next = m->mtx_next; 653829SN/A#ifdef MUTEX_DEBUG 654829SN/A m->mtx_next = m->mtx_prev = NULL; 655829SN/A#endif 656829SN/A#ifdef WITNESS 657829SN/A free(m->mtx_debug, M_DEVBUF); 658829SN/A m->mtx_debug = NULL; 659829SN/A#endif 660829SN/A mtx_cur_cnt--; 661829SN/A mtx_exit(&all_mtx, MTX_DEF); 662829SN/A} 663829SN/A 664829SN/A/* 665829SN/A * The non-inlined versions of the mtx_*() functions are always built (above), 666829SN/A * but the witness code depends on the WITNESS kernel option being specified. 667829SN/A */ 668829SN/A#ifdef WITNESS 669829SN/A 670829SN/A#define WITNESS_COUNT 200 671829SN/A#define WITNESS_NCHILDREN 2 672829SN/A 673829SN/Aint witness_watch = 1; 674829SN/A 675829SN/Astruct witness { 676829SN/A struct witness *w_next; 677829SN/A const char *w_description; 678829SN/A const char *w_file; 679829SN/A int w_line; 680829SN/A struct witness *w_morechildren; 681829SN/A u_char w_childcnt; 682829SN/A u_char w_Giant_squawked:1; 683829SN/A u_char w_other_squawked:1; 684829SN/A u_char w_same_squawked:1; 685829SN/A u_char w_sleep:1; 686829SN/A u_char w_spin:1; /* this is a spin mutex */ 687829SN/A u_int w_level; 688829SN/A struct witness *w_children[WITNESS_NCHILDREN]; 689829SN/A}; 690829SN/A 691829SN/Astruct witness_blessed { 692829SN/A char *b_lock1; 693829SN/A char *b_lock2; 694829SN/A}; 695829SN/A 696829SN/A#ifdef DDB 697829SN/A/* 698829SN/A * When DDB is enabled and witness_ddb is set to 1, it will cause the system to 699829SN/A * drop into kdebug() when: 700829SN/A * - a lock heirarchy violation occurs 701829SN/A * - locks are held when going to sleep. 702829SN/A */ 703829SN/A#ifdef WITNESS_DDB 704829SN/Aint witness_ddb = 1; 705829SN/A#else 706829SN/Aint witness_ddb = 0; 707829SN/A#endif 708829SN/ASYSCTL_INT(_debug, OID_AUTO, witness_ddb, CTLFLAG_RW, &witness_ddb, 0, ""); 709829SN/A#endif /* DDB */ 710829SN/A 711829SN/A#ifdef WITNESS_SKIPSPIN 712829SN/Aint witness_skipspin = 1; 713829SN/A#else 714829SN/Aint witness_skipspin = 0; 715829SN/A#endif 716829SN/ASYSCTL_INT(_debug, OID_AUTO, witness_skipspin, CTLFLAG_RD, &witness_skipspin, 0, 717829SN/A ""); 718829SN/A 719829SN/AMUTEX_DECLARE(static,w_mtx); 720829SN/Astatic struct witness *w_free; 721829SN/Astatic struct witness *w_all; 722829SN/Astatic int w_inited; 723829SN/Astatic int witness_dead; /* fatal error, probably no memory */ 724829SN/A 725829SN/Astatic struct witness w_data[WITNESS_COUNT]; 726829SN/A 727829SN/Astatic struct witness *enroll __P((const char *description, int flag)); 728829SN/Astatic int itismychild __P((struct witness *parent, struct witness *child)); 729829SN/Astatic void removechild __P((struct witness *parent, struct witness *child)); 730829SN/Astatic int isitmychild __P((struct witness *parent, struct witness *child)); 731829SN/Astatic int isitmydescendant __P((struct witness *parent, struct witness *child)); 732829SN/Astatic int dup_ok __P((struct witness *)); 733829SN/Astatic int blessed __P((struct witness *, struct witness *)); 734829SN/Astatic void witness_displaydescendants 735829SN/A __P((void(*)(const char *fmt, ...), struct witness *)); 736829SN/Astatic void witness_leveldescendents __P((struct witness *parent, int level)); 737829SN/Astatic void witness_levelall __P((void)); 738829SN/Astatic struct witness * witness_get __P((void)); 739829SN/Astatic void witness_free __P((struct witness *m)); 740829SN/A 741829SN/A 742829SN/Astatic char *ignore_list[] = { 743829SN/A "witness lock", 744829SN/A NULL 745829SN/A}; 746829SN/A 747829SN/Astatic char *spin_order_list[] = { 748829SN/A "sio", 749829SN/A "sched lock", 750829SN/A#ifdef __i386__ 751829SN/A "clk", 752829SN/A#endif 753829SN/A "callout", 754829SN/A /* 755829SN/A * leaf locks 756829SN/A */ 757829SN/A NULL 758829SN/A}; 759829SN/A 760829SN/Astatic char *order_list[] = { 761829SN/A "uidinfo hash", "uidinfo struct", NULL, 762829SN/A NULL 763829SN/A}; 764829SN/A 765829SN/Astatic char *dup_list[] = { 766829SN/A NULL 767829SN/A}; 768829SN/A 769829SN/Astatic char *sleep_list[] = { 770829SN/A "Giant", 771829SN/A NULL 772829SN/A}; 773829SN/A 774829SN/A/* 775829SN/A * Pairs of locks which have been blessed 776829SN/A * Don't complain about order problems with blessed locks 777829SN/A */ 778829SN/Astatic struct witness_blessed blessed_list[] = { 779829SN/A}; 780829SN/Astatic int blessed_count = sizeof(blessed_list) / sizeof(struct witness_blessed); 781829SN/A 782829SN/Avoid 783829SN/Awitness_init(struct mtx *m, int flag) 784829SN/A{ 785829SN/A m->mtx_witness = enroll(m->mtx_description, flag); 786829SN/A} 787829SN/A 788829SN/Avoid 789829SN/Awitness_destroy(struct mtx *m) 790829SN/A{ 791829SN/A struct mtx *m1; 792829SN/A struct proc *p; 793829SN/A p = CURPROC; 794829SN/A for ((m1 = LIST_FIRST(&p->p_heldmtx)); m1 != NULL; 795829SN/A m1 = LIST_NEXT(m1, mtx_held)) { 796829SN/A if (m1 == m) { 797829SN/A LIST_REMOVE(m, mtx_held); 798829SN/A break; 799829SN/A } 800829SN/A } 801829SN/A return; 802829SN/A 803829SN/A} 804829SN/A 805829SN/Avoid 806829SN/Awitness_enter(struct mtx *m, int flags, const char *file, int line) 807829SN/A{ 808829SN/A struct witness *w, *w1; 809829SN/A struct mtx *m1; 810829SN/A struct proc *p; 811829SN/A int i; 812829SN/A#ifdef DDB 813829SN/A int go_into_ddb = 0; 814829SN/A#endif /* DDB */ 815829SN/A 816829SN/A w = m->mtx_witness; 817829SN/A p = CURPROC; 818829SN/A 819829SN/A if (flags & MTX_SPIN) { 820829SN/A if (!w->w_spin) 821829SN/A panic("mutex_enter: MTX_SPIN on MTX_DEF mutex %s @" 822829SN/A " %s:%d", m->mtx_description, file, line); 823829SN/A if (m->mtx_recurse != 0) 824829SN/A return; 825829SN/A mtx_enter(&w_mtx, MTX_SPIN); 826829SN/A i = witness_spin_check; 827829SN/A if (i != 0 && w->w_level < i) { 828829SN/A mtx_exit(&w_mtx, MTX_SPIN); 829829SN/A panic("mutex_enter(%s:%x, MTX_SPIN) out of order @" 830829SN/A " %s:%d already holding %s:%x", 831829SN/A m->mtx_description, w->w_level, file, line, 832829SN/A spin_order_list[ffs(i)-1], i); 833829SN/A } 834829SN/A PCPU_SET(witness_spin_check, i | w->w_level); 835829SN/A mtx_exit(&w_mtx, MTX_SPIN); 836829SN/A w->w_file = file; 837829SN/A w->w_line = line; 838829SN/A m->mtx_line = line; 839829SN/A m->mtx_file = file; 840829SN/A return; 841829SN/A } 842829SN/A if (w->w_spin) 843829SN/A panic("mutex_enter: MTX_DEF on MTX_SPIN mutex %s @ %s:%d", 844829SN/A m->mtx_description, file, line); 845829SN/A 846829SN/A if (m->mtx_recurse != 0) 847829SN/A return; 848829SN/A if (witness_dead) 849829SN/A goto out; 850829SN/A if (cold || panicstr) 851829SN/A goto out; 852829SN/A 853829SN/A if (!mtx_legal2block()) 854829SN/A panic("blockable mtx_enter() of %s when not legal @ %s:%d", 855829SN/A m->mtx_description, file, line); 856829SN/A /* 857829SN/A * Is this the first mutex acquired 858829SN/A */ 859829SN/A if ((m1 = LIST_FIRST(&p->p_heldmtx)) == NULL) 860829SN/A goto out; 861829SN/A 862829SN/A if ((w1 = m1->mtx_witness) == w) { 863829SN/A if (w->w_same_squawked || dup_ok(w)) 864829SN/A goto out; 865829SN/A w->w_same_squawked = 1; 866829SN/A printf("acquring duplicate lock of same type: \"%s\"\n", 867829SN/A m->mtx_description); 868829SN/A printf(" 1st @ %s:%d\n", w->w_file, w->w_line); 869829SN/A printf(" 2nd @ %s:%d\n", file, line); 870829SN/A#ifdef DDB 871829SN/A go_into_ddb = 1; 872829SN/A#endif /* DDB */ 873829SN/A goto out; 874829SN/A } 875829SN/A MPASS(!mtx_owned(&w_mtx)); 876829SN/A mtx_enter(&w_mtx, MTX_SPIN); 877829SN/A /* 878829SN/A * If we have a known higher number just say ok 879829SN/A */ 880829SN/A if (witness_watch > 1 && w->w_level > w1->w_level) { 881829SN/A mtx_exit(&w_mtx, MTX_SPIN); 882829SN/A goto out; 883829SN/A } 884829SN/A if (isitmydescendant(m1->mtx_witness, w)) { 885829SN/A mtx_exit(&w_mtx, MTX_SPIN); 886829SN/A goto out; 887829SN/A } 888829SN/A for (i = 0; m1 != NULL; m1 = LIST_NEXT(m1, mtx_held), i++) { 889829SN/A 890829SN/A MPASS(i < 200); 891829SN/A w1 = m1->mtx_witness; 892829SN/A if (isitmydescendant(w, w1)) { 893829SN/A mtx_exit(&w_mtx, MTX_SPIN); 894829SN/A if (blessed(w, w1)) 895829SN/A goto out; 896829SN/A if (m1 == &Giant) { 897829SN/A if (w1->w_Giant_squawked) 898829SN/A goto out; 899829SN/A else 900829SN/A w1->w_Giant_squawked = 1; 901829SN/A } else { 902829SN/A if (w1->w_other_squawked) 903829SN/A goto out; 904829SN/A else 905829SN/A w1->w_other_squawked = 1; 906829SN/A } 907829SN/A printf("lock order reversal\n"); 908829SN/A printf(" 1st %s last acquired @ %s:%d\n", 909829SN/A w->w_description, w->w_file, w->w_line); 910829SN/A printf(" 2nd %p %s @ %s:%d\n", 911829SN/A m1, w1->w_description, w1->w_file, w1->w_line); 912829SN/A printf(" 3rd %p %s @ %s:%d\n", 913829SN/A m, w->w_description, file, line); 914829SN/A#ifdef DDB 915829SN/A go_into_ddb = 1; 916829SN/A#endif /* DDB */ 917829SN/A goto out; 918829SN/A } 919829SN/A } 920829SN/A m1 = LIST_FIRST(&p->p_heldmtx); 921829SN/A if (!itismychild(m1->mtx_witness, w)) 922829SN/A mtx_exit(&w_mtx, MTX_SPIN); 923829SN/A 924829SN/Aout: 925829SN/A#ifdef DDB 926829SN/A if (witness_ddb && go_into_ddb) 927829SN/A Debugger("witness_enter"); 928829SN/A#endif /* DDB */ 929829SN/A w->w_file = file; 930829SN/A w->w_line = line; 931829SN/A m->mtx_line = line; 932829SN/A m->mtx_file = file; 933829SN/A 934829SN/A /* 935829SN/A * If this pays off it likely means that a mutex being witnessed 936829SN/A * is acquired in hardclock. Put it in the ignore list. It is 937829SN/A * likely not the mutex this assert fails on. 938829SN/A */ 939829SN/A MPASS(m->mtx_held.le_prev == NULL); 940829SN/A LIST_INSERT_HEAD(&p->p_heldmtx, (struct mtx*)m, mtx_held); 941829SN/A} 942829SN/A 943829SN/Avoid 944829SN/Awitness_exit(struct mtx *m, int flags, const char *file, int line) 945829SN/A{ 946829SN/A struct witness *w; 947829SN/A 948829SN/A w = m->mtx_witness; 949829SN/A 950829SN/A if (flags & MTX_SPIN) { 951829SN/A if (!w->w_spin) 952829SN/A panic("mutex_exit: MTX_SPIN on MTX_DEF mutex %s @" 953829SN/A " %s:%d", m->mtx_description, file, line); 954829SN/A if (m->mtx_recurse != 0) 955829SN/A return; 956829SN/A mtx_enter(&w_mtx, MTX_SPIN); 957829SN/A PCPU_SET(witness_spin_check, witness_spin_check & ~w->w_level); 958829SN/A mtx_exit(&w_mtx, MTX_SPIN); 959829SN/A return; 960829SN/A } 961829SN/A if (w->w_spin) 962829SN/A panic("mutex_exit: MTX_DEF on MTX_SPIN mutex %s @ %s:%d", 963829SN/A m->mtx_description, file, line); 964829SN/A 965829SN/A if (m->mtx_recurse != 0) 966829SN/A return; 967829SN/A 968829SN/A if ((flags & MTX_NOSWITCH) == 0 && !mtx_legal2block() && !cold) 969829SN/A panic("switchable mtx_exit() of %s when not legal @ %s:%d", 970829SN/A m->mtx_description, file, line); 971829SN/A LIST_REMOVE(m, mtx_held); 972829SN/A m->mtx_held.le_prev = NULL; 973829SN/A} 974829SN/A 975829SN/Avoid 976829SN/Awitness_try_enter(struct mtx *m, int flags, const char *file, int line) 977829SN/A{ 978829SN/A struct proc *p; 979829SN/A struct witness *w = m->mtx_witness; 980829SN/A 981829SN/A if (flags & MTX_SPIN) { 982829SN/A if (!w->w_spin) 983829SN/A panic("mutex_try_enter: " 984829SN/A "MTX_SPIN on MTX_DEF mutex %s @ %s:%d", 985829SN/A m->mtx_description, file, line); 986829SN/A if (m->mtx_recurse != 0) 987829SN/A return; 988829SN/A mtx_enter(&w_mtx, MTX_SPIN); 989829SN/A PCPU_SET(witness_spin_check, witness_spin_check | w->w_level); 990829SN/A mtx_exit(&w_mtx, MTX_SPIN); 991829SN/A w->w_file = file; 992829SN/A w->w_line = line; 993829SN/A m->mtx_line = line; 994829SN/A m->mtx_file = file; 995829SN/A return; 996829SN/A } 997829SN/A 998829SN/A if (w->w_spin) 999829SN/A panic("mutex_try_enter: MTX_DEF on MTX_SPIN mutex %s @ %s:%d", 1000829SN/A m->mtx_description, file, line); 1001829SN/A 1002829SN/A if (m->mtx_recurse != 0) 1003829SN/A return; 1004829SN/A 1005829SN/A w->w_file = file; 1006829SN/A w->w_line = line; 1007829SN/A m->mtx_line = line; 1008829SN/A m->mtx_file = file; 1009829SN/A p = CURPROC; 1010829SN/A MPASS(m->mtx_held.le_prev == NULL); 1011829SN/A LIST_INSERT_HEAD(&p->p_heldmtx, (struct mtx*)m, mtx_held); 1012829SN/A} 1013829SN/A 1014829SN/Avoid 1015829SN/Awitness_display(void(*prnt)(const char *fmt, ...)) 1016829SN/A{ 1017829SN/A struct witness *w, *w1; 1018829SN/A 1019829SN/A witness_levelall(); 1020829SN/A 1021829SN/A for (w = w_all; w; w = w->w_next) { 1022829SN/A if (w->w_file == NULL) 1023829SN/A continue; 1024829SN/A for (w1 = w_all; w1; w1 = w1->w_next) { 1025829SN/A if (isitmychild(w1, w)) 1026829SN/A break; 1027829SN/A } 1028829SN/A if (w1 != NULL) 1029829SN/A continue; 1030829SN/A /* 1031829SN/A * This lock has no anscestors, display its descendants. 1032829SN/A */ 1033829SN/A witness_displaydescendants(prnt, w); 1034829SN/A } 1035829SN/A prnt("\nMutex which were never acquired\n"); 1036829SN/A for (w = w_all; w; w = w->w_next) { 1037829SN/A if (w->w_file != NULL) 1038829SN/A continue; 1039829SN/A prnt("%s\n", w->w_description); 1040829SN/A } 1041829SN/A} 1042829SN/A 1043829SN/Aint 1044829SN/Awitness_sleep(int check_only, struct mtx *mtx, const char *file, int line) 1045829SN/A{ 1046829SN/A struct mtx *m; 1047829SN/A struct proc *p; 1048829SN/A char **sleep; 1049829SN/A int n = 0; 1050829SN/A 1051829SN/A p = CURPROC; 1052829SN/A for ((m = LIST_FIRST(&p->p_heldmtx)); m != NULL; 1053829SN/A m = LIST_NEXT(m, mtx_held)) { 1054829SN/A if (m == mtx) 1055829SN/A continue; 1056829SN/A for (sleep = sleep_list; *sleep!= NULL; sleep++) 1057829SN/A if (strcmp(m->mtx_description, *sleep) == 0) 1058829SN/A goto next; 1059829SN/A printf("%s:%d: %s with \"%s\" locked from %s:%d\n", 1060829SN/A file, line, check_only ? "could sleep" : "sleeping", 1061829SN/A m->mtx_description, 1062829SN/A m->mtx_witness->w_file, m->mtx_witness->w_line); 1063829SN/A n++; 1064829SN/A next: 1065829SN/A } 1066829SN/A#ifdef DDB 1067829SN/A if (witness_ddb && n) 1068829SN/A Debugger("witness_sleep"); 1069829SN/A#endif /* DDB */ 1070829SN/A return (n); 1071829SN/A} 1072829SN/A 1073829SN/Astatic struct witness * 1074829SN/Aenroll(const char *description, int flag) 1075829SN/A{ 1076829SN/A int i; 1077829SN/A struct witness *w, *w1; 1078829SN/A char **ignore; 1079829SN/A char **order; 1080829SN/A 1081829SN/A if (!witness_watch) 1082829SN/A return (NULL); 1083829SN/A for (ignore = ignore_list; *ignore != NULL; ignore++) 1084829SN/A if (strcmp(description, *ignore) == 0) 1085829SN/A return (NULL); 1086829SN/A 1087829SN/A if (w_inited == 0) { 1088829SN/A mtx_init(&w_mtx, "witness lock", MTX_COLD | MTX_SPIN); 1089829SN/A for (i = 0; i < WITNESS_COUNT; i++) { 1090829SN/A w = &w_data[i]; 1091829SN/A witness_free(w); 1092829SN/A } 1093829SN/A w_inited = 1; 1094829SN/A for (order = order_list; *order != NULL; order++) { 1095829SN/A w = enroll(*order, MTX_DEF); 1096829SN/A w->w_file = "order list"; 1097829SN/A for (order++; *order != NULL; order++) { 1098829SN/A w1 = enroll(*order, MTX_DEF); 1099829SN/A w1->w_file = "order list"; 1100829SN/A itismychild(w, w1); 1101829SN/A w = w1; 1102829SN/A } 1103829SN/A } 1104829SN/A } 1105829SN/A if ((flag & MTX_SPIN) && witness_skipspin) 1106829SN/A return (NULL); 1107829SN/A mtx_enter(&w_mtx, MTX_SPIN); 1108829SN/A for (w = w_all; w; w = w->w_next) { 1109829SN/A if (strcmp(description, w->w_description) == 0) { 1110829SN/A mtx_exit(&w_mtx, MTX_SPIN); 1111829SN/A return (w); 1112829SN/A } 1113829SN/A } 1114829SN/A if ((w = witness_get()) == NULL) 1115829SN/A return (NULL); 1116829SN/A w->w_next = w_all; 1117829SN/A w_all = w; 1118829SN/A w->w_description = description; 1119829SN/A mtx_exit(&w_mtx, MTX_SPIN); 1120829SN/A if (flag & MTX_SPIN) { 1121829SN/A w->w_spin = 1; 1122829SN/A 1123829SN/A i = 1; 1124829SN/A for (order = spin_order_list; *order != NULL; order++) { 1125829SN/A if (strcmp(description, *order) == 0) 1126829SN/A break; 1127829SN/A i <<= 1; 1128829SN/A } 1129829SN/A if (*order == NULL) 1130829SN/A panic("spin lock %s not in order list", description); 1131829SN/A w->w_level = i; 1132829SN/A } 1133829SN/A return (w); 1134829SN/A} 1135829SN/A 1136829SN/Astatic int 1137829SN/Aitismychild(struct witness *parent, struct witness *child) 1138829SN/A{ 1139829SN/A static int recursed; 1140829SN/A 1141829SN/A /* 1142829SN/A * Insert "child" after "parent" 1143829SN/A */ 1144829SN/A while (parent->w_morechildren) 1145829SN/A parent = parent->w_morechildren; 1146829SN/A 1147829SN/A if (parent->w_childcnt == WITNESS_NCHILDREN) { 1148829SN/A if ((parent->w_morechildren = witness_get()) == NULL) 1149829SN/A return (1); 1150829SN/A parent = parent->w_morechildren; 1151829SN/A } 1152829SN/A MPASS(child != NULL); 1153829SN/A parent->w_children[parent->w_childcnt++] = child; 1154829SN/A /* 1155829SN/A * now prune whole tree 1156829SN/A */ 1157829SN/A if (recursed) 1158829SN/A return (0); 1159829SN/A recursed = 1; 1160829SN/A for (child = w_all; child != NULL; child = child->w_next) { 1161829SN/A for (parent = w_all; parent != NULL; 1162829SN/A parent = parent->w_next) { 1163829SN/A if (!isitmychild(parent, child)) 1164829SN/A continue; 1165829SN/A removechild(parent, child); 1166829SN/A if (isitmydescendant(parent, child)) 1167829SN/A continue; 1168829SN/A itismychild(parent, child); 1169829SN/A } 1170829SN/A } 1171829SN/A recursed = 0; 1172829SN/A witness_levelall(); 1173829SN/A return (0); 1174829SN/A} 1175829SN/A 1176829SN/Astatic void 1177829SN/Aremovechild(struct witness *parent, struct witness *child) 1178829SN/A{ 1179829SN/A struct witness *w, *w1; 1180829SN/A int i; 1181829SN/A 1182829SN/A for (w = parent; w != NULL; w = w->w_morechildren) 1183829SN/A for (i = 0; i < w->w_childcnt; i++) 1184829SN/A if (w->w_children[i] == child) 1185829SN/A goto found; 1186829SN/A return; 1187829SN/Afound: 1188829SN/A for (w1 = w; w1->w_morechildren != NULL; w1 = w1->w_morechildren) 1189829SN/A continue; 1190829SN/A w->w_children[i] = w1->w_children[--w1->w_childcnt]; 1191829SN/A MPASS(w->w_children[i] != NULL); 1192829SN/A 1193829SN/A if (w1->w_childcnt != 0) 1194829SN/A return; 1195829SN/A 1196829SN/A if (w1 == parent) 1197829SN/A return; 1198829SN/A for (w = parent; w->w_morechildren != w1; w = w->w_morechildren) 1199829SN/A continue; 1200829SN/A w->w_morechildren = 0; 1201829SN/A witness_free(w1); 1202829SN/A} 1203829SN/A 1204829SN/Astatic int 1205829SN/Aisitmychild(struct witness *parent, struct witness *child) 1206829SN/A{ 1207829SN/A struct witness *w; 1208829SN/A int i; 1209829SN/A 1210829SN/A for (w = parent; w != NULL; w = w->w_morechildren) { 1211829SN/A for (i = 0; i < w->w_childcnt; i++) { 1212829SN/A if (w->w_children[i] == child) 1213829SN/A return (1); 1214829SN/A } 1215829SN/A } 1216829SN/A return (0); 1217829SN/A} 1218829SN/A 1219829SN/Astatic int 1220829SN/Aisitmydescendant(struct witness *parent, struct witness *child) 1221829SN/A{ 1222829SN/A struct witness *w; 1223829SN/A int i; 1224829SN/A int j; 1225829SN/A 1226829SN/A for (j = 0, w = parent; w != NULL; w = w->w_morechildren, j++) { 1227829SN/A MPASS(j < 1000); 1228829SN/A for (i = 0; i < w->w_childcnt; i++) { 1229829SN/A if (w->w_children[i] == child) 1230829SN/A return (1); 1231829SN/A } 1232829SN/A for (i = 0; i < w->w_childcnt; i++) { 1233829SN/A if (isitmydescendant(w->w_children[i], child)) 1234829SN/A return (1); 1235829SN/A } 1236829SN/A } 1237829SN/A return (0); 1238829SN/A} 1239829SN/A 1240829SN/Avoid 1241829SN/Awitness_levelall (void) 1242829SN/A{ 1243829SN/A struct witness *w, *w1; 1244829SN/A 1245829SN/A for (w = w_all; w; w = w->w_next) 1246829SN/A if (!w->w_spin) 1247829SN/A w->w_level = 0; 1248829SN/A for (w = w_all; w; w = w->w_next) { 1249829SN/A if (w->w_spin) 1250829SN/A continue; 1251829SN/A for (w1 = w_all; w1; w1 = w1->w_next) { 1252829SN/A if (isitmychild(w1, w)) 1253829SN/A break; 1254829SN/A } 1255829SN/A if (w1 != NULL) 1256829SN/A continue; 1257829SN/A witness_leveldescendents(w, 0); 1258829SN/A } 1259829SN/A} 1260829SN/A 1261829SN/Astatic void 1262829SN/Awitness_leveldescendents(struct witness *parent, int level) 1263829SN/A{ 1264829SN/A int i; 1265829SN/A struct witness *w; 1266829SN/A 1267829SN/A if (parent->w_level < level) 1268829SN/A parent->w_level = level; 1269829SN/A level++; 1270829SN/A for (w = parent; w != NULL; w = w->w_morechildren) 1271829SN/A for (i = 0; i < w->w_childcnt; i++) 1272829SN/A witness_leveldescendents(w->w_children[i], level); 1273829SN/A} 1274829SN/A 1275829SN/Astatic void 1276829SN/Awitness_displaydescendants(void(*prnt)(const char *fmt, ...), 1277829SN/A struct witness *parent) 1278829SN/A{ 1279829SN/A struct witness *w; 1280829SN/A int i; 1281829SN/A int level = parent->w_level; 1282829SN/A 1283829SN/A prnt("%d", level); 1284829SN/A if (level < 10) 1285829SN/A prnt(" "); 1286829SN/A for (i = 0; i < level; i++) 1287829SN/A prnt(" "); 1288829SN/A prnt("%s", parent->w_description); 1289829SN/A if (parent->w_file != NULL) { 1290829SN/A prnt(" -- last acquired @ %s", parent->w_file); 1291829SN/A#ifndef W_USE_WHERE 1292829SN/A prnt(":%d", parent->w_line); 1293829SN/A#endif 1294829SN/A prnt("\n"); 1295829SN/A } 1296829SN/A 1297829SN/A for (w = parent; w != NULL; w = w->w_morechildren) 1298829SN/A for (i = 0; i < w->w_childcnt; i++) 1299829SN/A witness_displaydescendants(prnt, w->w_children[i]); 1300829SN/A } 1301829SN/A 1302829SN/Astatic int 1303829SN/Adup_ok(struct witness *w) 1304829SN/A{ 1305829SN/A char **dup; 1306829SN/A 1307829SN/A for (dup = dup_list; *dup!= NULL; dup++) 1308829SN/A if (strcmp(w->w_description, *dup) == 0) 1309829SN/A return (1); 1310829SN/A return (0); 1311829SN/A} 1312829SN/A 1313829SN/Astatic int 1314829SN/Ablessed(struct witness *w1, struct witness *w2) 1315829SN/A{ 1316829SN/A int i; 1317829SN/A struct witness_blessed *b; 1318829SN/A 1319829SN/A for (i = 0; i < blessed_count; i++) { 1320829SN/A b = &blessed_list[i]; 1321829SN/A if (strcmp(w1->w_description, b->b_lock1) == 0) { 1322829SN/A if (strcmp(w2->w_description, b->b_lock2) == 0) 1323829SN/A return (1); 1324829SN/A continue; 1325829SN/A } 1326829SN/A if (strcmp(w1->w_description, b->b_lock2) == 0) 1327829SN/A if (strcmp(w2->w_description, b->b_lock1) == 0) 1328829SN/A return (1); 1329829SN/A } 1330829SN/A return (0); 1331829SN/A} 1332829SN/A 1333829SN/Astatic struct witness * 1334829SN/Awitness_get() 1335829SN/A{ 1336829SN/A struct witness *w; 1337829SN/A 1338829SN/A if ((w = w_free) == NULL) { 1339829SN/A witness_dead = 1; 1340829SN/A mtx_exit(&w_mtx, MTX_SPIN); 1341829SN/A printf("witness exhausted\n"); 1342829SN/A return (NULL); 1343829SN/A } 1344829SN/A w_free = w->w_next; 1345829SN/A bzero(w, sizeof(*w)); 1346829SN/A return (w); 1347829SN/A} 1348829SN/A 1349829SN/Astatic void 1350829SN/Awitness_free(struct witness *w) 1351829SN/A{ 1352829SN/A w->w_next = w_free; 1353829SN/A w_free = w; 1354829SN/A} 1355829SN/A 1356829SN/Avoid 1357829SN/Awitness_list(struct proc *p) 1358829SN/A{ 1359829SN/A struct mtx *m; 1360829SN/A 1361829SN/A for ((m = LIST_FIRST(&p->p_heldmtx)); m != NULL; 1362829SN/A m = LIST_NEXT(m, mtx_held)) { 1363829SN/A printf("\t\"%s\" (%p) locked at %s:%d\n", 1364829SN/A m->mtx_description, m, 1365829SN/A m->mtx_witness->w_file, m->mtx_witness->w_line); 1366829SN/A } 1367829SN/A} 1368829SN/A 1369829SN/Avoid 1370829SN/Awitness_save(struct mtx *m, const char **filep, int *linep) 1371829SN/A{ 1372829SN/A *filep = m->mtx_witness->w_file; 1373829SN/A *linep = m->mtx_witness->w_line; 1374829SN/A} 1375829SN/A 1376829SN/Avoid 1377829SN/Awitness_restore(struct mtx *m, const char *file, int line) 1378829SN/A{ 1379829SN/A m->mtx_witness->w_file = file; 1380829SN/A m->mtx_witness->w_line = line; 1381829SN/A} 1382829SN/A 1383829SN/A#endif /* WITNESS */ 1384829SN/A