10384fff8SJason Evans /*- 20384fff8SJason Evans * Copyright (c) 1998 Berkeley Software Design, Inc. All rights reserved. 30384fff8SJason Evans * 40384fff8SJason Evans * Redistribution and use in source and binary forms, with or without 50384fff8SJason Evans * modification, are permitted provided that the following conditions 60384fff8SJason Evans * are met: 70384fff8SJason Evans * 1. Redistributions of source code must retain the above copyright 80384fff8SJason Evans * notice, this list of conditions and the following disclaimer. 90384fff8SJason Evans * 2. Redistributions in binary form must reproduce the above copyright 100384fff8SJason Evans * notice, this list of conditions and the following disclaimer in the 110384fff8SJason Evans * documentation and/or other materials provided with the distribution. 120384fff8SJason Evans * 3. Berkeley Software Design Inc's name may not be used to endorse or 130384fff8SJason Evans * promote products derived from this software without specific prior 140384fff8SJason Evans * written permission. 150384fff8SJason Evans * 160384fff8SJason Evans * THIS SOFTWARE IS PROVIDED BY BERKELEY SOFTWARE DESIGN INC ``AS IS'' AND 170384fff8SJason Evans * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 180384fff8SJason Evans * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 190384fff8SJason Evans * ARE DISCLAIMED. IN NO EVENT SHALL BERKELEY SOFTWARE DESIGN INC BE LIABLE 200384fff8SJason Evans * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 210384fff8SJason Evans * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 220384fff8SJason Evans * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 230384fff8SJason Evans * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 240384fff8SJason Evans * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 250384fff8SJason Evans * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 260384fff8SJason Evans * SUCH DAMAGE. 270384fff8SJason Evans * 280384fff8SJason Evans * from BSDI $Id: mutex_witness.c,v 1.1.2.20 2000/04/27 03:10:27 cp Exp $ 2936412d79SJohn Baldwin * and BSDI $Id: synch_machdep.c,v 2.3.2.39 2000/04/27 03:10:25 cp Exp $ 300384fff8SJason Evans * $FreeBSD$ 310384fff8SJason Evans */ 320384fff8SJason Evans 330384fff8SJason Evans /* 349ed346baSBosko Milekic * Machine independent bits of mutex implementation and implementation of 359ed346baSBosko Milekic * `witness' structure & related debugging routines. 369ed346baSBosko Milekic */ 379ed346baSBosko Milekic 389ed346baSBosko Milekic /* 390384fff8SJason Evans * Main Entry: witness 400384fff8SJason Evans * Pronunciation: 'wit-n&s 410384fff8SJason Evans * Function: noun 420384fff8SJason Evans * Etymology: Middle English witnesse, from Old English witnes knowledge, 430384fff8SJason Evans * testimony, witness, from 2wit 440384fff8SJason Evans * Date: before 12th century 450384fff8SJason Evans * 1 : attestation of a fact or event : TESTIMONY 460384fff8SJason Evans * 2 : one that gives evidence; specifically : one who testifies in 470384fff8SJason Evans * a cause or before a judicial tribunal 480384fff8SJason Evans * 3 : one asked to be present at a transaction so as to be able to 490384fff8SJason Evans * testify to its having taken place 500384fff8SJason Evans * 4 : one who has personal knowledge of something 510384fff8SJason Evans * 5 a : something serving as evidence or proof : SIGN 520384fff8SJason Evans * b : public affirmation by word or example of usually 530384fff8SJason Evans * religious faith or conviction <the heroic witness to divine 540384fff8SJason Evans * life -- Pilot> 550384fff8SJason Evans * 6 capitalized : a member of the Jehovah's Witnesses 560384fff8SJason Evans */ 570384fff8SJason Evans 589c36c934SJohn Baldwin #include "opt_ddb.h" 59a5a96a19SJohn Baldwin 600384fff8SJason Evans #include <sys/param.h> 6136412d79SJohn Baldwin #include <sys/bus.h> 6236412d79SJohn Baldwin #include <sys/kernel.h> 6319284646SJohn Baldwin #include <sys/lock.h> 64fb919e4dSMark Murray #include <sys/malloc.h> 6519284646SJohn Baldwin #include <sys/mutex.h> 660384fff8SJason Evans #include <sys/proc.h> 67c4f7a187SJohn Baldwin #include <sys/resourcevar.h> 68a5a96a19SJohn Baldwin #include <sys/sysctl.h> 690384fff8SJason Evans #include <sys/systm.h> 7036412d79SJohn Baldwin #include <sys/vmmeter.h> 710384fff8SJason Evans #include <sys/ktr.h> 720384fff8SJason Evans 7336412d79SJohn Baldwin #include <machine/atomic.h> 7436412d79SJohn Baldwin #include <machine/bus.h> 7536412d79SJohn Baldwin #include <machine/clock.h> 760384fff8SJason Evans #include <machine/cpu.h> 7736412d79SJohn Baldwin 789c36c934SJohn Baldwin #include <ddb/ddb.h> 799c36c934SJohn Baldwin 8036412d79SJohn Baldwin #include <vm/vm.h> 8136412d79SJohn Baldwin #include <vm/vm_extern.h> 8236412d79SJohn Baldwin 830cde2e34SJason Evans /* 849ed346baSBosko Milekic * Internal utility macros. 850cde2e34SJason Evans */ 869ed346baSBosko Milekic #define mtx_unowned(m) ((m)->mtx_lock == MTX_UNOWNED) 870cde2e34SJason Evans 889ed346baSBosko Milekic #define mtx_owner(m) (mtx_unowned((m)) ? NULL \ 89b40ce416SJulian Elischer : (struct thread *)((m)->mtx_lock & MTX_FLAGMASK)) 909ed346baSBosko Milekic 91b40ce416SJulian Elischer #define SET_PRIO(td, pri) (td)->td_ksegrp->kg_pri.pri_level = (pri) 920cde2e34SJason Evans 930cde2e34SJason Evans /* 9419284646SJohn Baldwin * Lock classes for sleep and spin mutexes. 950cde2e34SJason Evans */ 9619284646SJohn Baldwin struct lock_class lock_class_mtx_sleep = { 9719284646SJohn Baldwin "sleep mutex", 9819284646SJohn Baldwin LC_SLEEPLOCK | LC_RECURSABLE 9919284646SJohn Baldwin }; 10019284646SJohn Baldwin struct lock_class lock_class_mtx_spin = { 10119284646SJohn Baldwin "spin mutex", 10219284646SJohn Baldwin LC_SPINLOCK | LC_RECURSABLE 1038484de75SJohn Baldwin }; 1048484de75SJohn Baldwin 1059ed346baSBosko Milekic /* 1069ed346baSBosko Milekic * Prototypes for non-exported routines. 1079ed346baSBosko Milekic */ 108b40ce416SJulian Elischer static void propagate_priority(struct thread *); 10936412d79SJohn Baldwin 11036412d79SJohn Baldwin static void 111b40ce416SJulian Elischer propagate_priority(struct thread *td) 11236412d79SJohn Baldwin { 113b40ce416SJulian Elischer struct ksegrp *kg = td->td_ksegrp; 114b40ce416SJulian Elischer int pri = kg->kg_pri.pri_level; 115b40ce416SJulian Elischer struct mtx *m = td->td_blocked; 11636412d79SJohn Baldwin 1171bd0eefbSJohn Baldwin mtx_assert(&sched_lock, MA_OWNED); 11836412d79SJohn Baldwin for (;;) { 119b40ce416SJulian Elischer struct thread *td1; 12036412d79SJohn Baldwin 121b40ce416SJulian Elischer td = mtx_owner(m); 12236412d79SJohn Baldwin 123b40ce416SJulian Elischer if (td == NULL) { 12436412d79SJohn Baldwin /* 12536412d79SJohn Baldwin * This really isn't quite right. Really 126b40ce416SJulian Elischer * ought to bump priority of thread that 12736412d79SJohn Baldwin * next acquires the mutex. 12836412d79SJohn Baldwin */ 12936412d79SJohn Baldwin MPASS(m->mtx_lock == MTX_CONTESTED); 13036412d79SJohn Baldwin return; 13136412d79SJohn Baldwin } 132a44f918bSJohn Baldwin kg = td->td_ksegrp; 1339ed346baSBosko Milekic 134b40ce416SJulian Elischer MPASS(td->td_proc->p_magic == P_MAGIC); 135b40ce416SJulian Elischer KASSERT(td->td_proc->p_stat != SSLEEP, ("sleeping thread owns a mutex")); 136b40ce416SJulian Elischer if (kg->kg_pri.pri_level <= pri) /* lower is higher priority */ 13736412d79SJohn Baldwin return; 1381bd0eefbSJohn Baldwin 1391bd0eefbSJohn Baldwin /* 140b40ce416SJulian Elischer * Bump this thread's priority. 1411bd0eefbSJohn Baldwin */ 142b40ce416SJulian Elischer SET_PRIO(td, pri); 1431bd0eefbSJohn Baldwin 14436412d79SJohn Baldwin /* 14536412d79SJohn Baldwin * If lock holder is actually running, just bump priority. 14636412d79SJohn Baldwin */ 147b40ce416SJulian Elischer /* XXXKSE this test is not sufficient */ 148b40ce416SJulian Elischer if (td->td_kse && (td->td_kse->ke_oncpu != NOCPU)) { 149b40ce416SJulian Elischer MPASS(td->td_proc->p_stat == SRUN 150b40ce416SJulian Elischer || td->td_proc->p_stat == SZOMB 151b40ce416SJulian Elischer || td->td_proc->p_stat == SSTOP); 15236412d79SJohn Baldwin return; 15336412d79SJohn Baldwin } 154d5a08a60SJake Burkholder 1551b43703bSJohn Baldwin #ifndef SMP 1561b43703bSJohn Baldwin /* 157b40ce416SJulian Elischer * For UP, we check to see if td is curthread (this shouldn't 1581b43703bSJohn Baldwin * ever happen however as it would mean we are in a deadlock.) 1591b43703bSJohn Baldwin */ 160b40ce416SJulian Elischer KASSERT(td != curthread, ("Deadlock detected")); 1611b43703bSJohn Baldwin #endif 1621b43703bSJohn Baldwin 16336412d79SJohn Baldwin /* 164b40ce416SJulian Elischer * If on run queue move to new run queue, and quit. 165b40ce416SJulian Elischer * XXXKSE this gets a lot more complicated under threads 166b40ce416SJulian Elischer * but try anyhow. 16736412d79SJohn Baldwin */ 168b40ce416SJulian Elischer if (td->td_proc->p_stat == SRUN) { 169b40ce416SJulian Elischer MPASS(td->td_blocked == NULL); 170b40ce416SJulian Elischer remrunqueue(td); 171b40ce416SJulian Elischer setrunqueue(td); 17236412d79SJohn Baldwin return; 17336412d79SJohn Baldwin } 17436412d79SJohn Baldwin 17536412d79SJohn Baldwin /* 1761bd0eefbSJohn Baldwin * If we aren't blocked on a mutex, we should be. 17736412d79SJohn Baldwin */ 178b40ce416SJulian Elischer KASSERT(td->td_proc->p_stat == SMTX, ( 1791bd0eefbSJohn Baldwin "process %d(%s):%d holds %s but isn't blocked on a mutex\n", 180b40ce416SJulian Elischer td->td_proc->p_pid, td->td_proc->p_comm, td->td_proc->p_stat, 18119284646SJohn Baldwin m->mtx_object.lo_name)); 18236412d79SJohn Baldwin 18336412d79SJohn Baldwin /* 184b40ce416SJulian Elischer * Pick up the mutex that td is blocked on. 18536412d79SJohn Baldwin */ 186b40ce416SJulian Elischer m = td->td_blocked; 18736412d79SJohn Baldwin MPASS(m != NULL); 18836412d79SJohn Baldwin 18936412d79SJohn Baldwin /* 190b40ce416SJulian Elischer * Check if the thread needs to be moved up on 19136412d79SJohn Baldwin * the blocked chain 19236412d79SJohn Baldwin */ 193b40ce416SJulian Elischer if (td == TAILQ_FIRST(&m->mtx_blocked)) { 1941bd0eefbSJohn Baldwin continue; 1951bd0eefbSJohn Baldwin } 1969ed346baSBosko Milekic 197b40ce416SJulian Elischer td1 = TAILQ_PREV(td, threadqueue, td_blkq); 198b40ce416SJulian Elischer if (td1->td_ksegrp->kg_pri.pri_level <= pri) { 19936412d79SJohn Baldwin continue; 20036412d79SJohn Baldwin } 20136412d79SJohn Baldwin 20236412d79SJohn Baldwin /* 203b40ce416SJulian Elischer * Remove thread from blocked chain and determine where 204b40ce416SJulian Elischer * it should be moved up to. Since we know that td1 has 205b40ce416SJulian Elischer * a lower priority than td, we know that at least one 206b40ce416SJulian Elischer * thread in the chain has a lower priority and that 207b40ce416SJulian Elischer * td1 will thus not be NULL after the loop. 20836412d79SJohn Baldwin */ 209b40ce416SJulian Elischer TAILQ_REMOVE(&m->mtx_blocked, td, td_blkq); 210b40ce416SJulian Elischer TAILQ_FOREACH(td1, &m->mtx_blocked, td_blkq) { 211b40ce416SJulian Elischer MPASS(td1->td_proc->p_magic == P_MAGIC); 212b40ce416SJulian Elischer if (td1->td_ksegrp->kg_pri.pri_level > pri) 21336412d79SJohn Baldwin break; 21436412d79SJohn Baldwin } 2159ed346baSBosko Milekic 216b40ce416SJulian Elischer MPASS(td1 != NULL); 217b40ce416SJulian Elischer TAILQ_INSERT_BEFORE(td1, td, td_blkq); 21836412d79SJohn Baldwin CTR4(KTR_LOCK, 2198484de75SJohn Baldwin "propagate_priority: p %p moved before %p on [%p] %s", 220b40ce416SJulian Elischer td, td1, m, m->mtx_object.lo_name); 22136412d79SJohn Baldwin } 22236412d79SJohn Baldwin } 22336412d79SJohn Baldwin 2240cde2e34SJason Evans /* 2256283b7d0SJohn Baldwin * Function versions of the inlined __mtx_* macros. These are used by 2266283b7d0SJohn Baldwin * modules and can also be called from assembly language if needed. 2276283b7d0SJohn Baldwin */ 2286283b7d0SJohn Baldwin void 2296283b7d0SJohn Baldwin _mtx_lock_flags(struct mtx *m, int opts, const char *file, int line) 2306283b7d0SJohn Baldwin { 2316283b7d0SJohn Baldwin 232dde96c99SJohn Baldwin MPASS(curthread != NULL); 233dde96c99SJohn Baldwin KASSERT((opts & MTX_NOSWITCH) == 0, 234dde96c99SJohn Baldwin ("MTX_NOSWITCH used at %s:%d", file, line)); 235dde96c99SJohn Baldwin _get_sleep_lock(m, curthread, opts, file, line); 236dde96c99SJohn Baldwin LOCK_LOG_LOCK("LOCK", &m->mtx_object, opts, m->mtx_recurse, file, 237dde96c99SJohn Baldwin line); 238dde96c99SJohn Baldwin WITNESS_LOCK(&m->mtx_object, opts | LOP_EXCLUSIVE, file, line); 2396283b7d0SJohn Baldwin } 2406283b7d0SJohn Baldwin 2416283b7d0SJohn Baldwin void 2426283b7d0SJohn Baldwin _mtx_unlock_flags(struct mtx *m, int opts, const char *file, int line) 2436283b7d0SJohn Baldwin { 2446283b7d0SJohn Baldwin 245dde96c99SJohn Baldwin MPASS(curthread != NULL); 24621377ce0SJohn Baldwin mtx_assert(m, MA_OWNED); 247dde96c99SJohn Baldwin WITNESS_UNLOCK(&m->mtx_object, opts | LOP_EXCLUSIVE, file, line); 248dde96c99SJohn Baldwin LOCK_LOG_LOCK("UNLOCK", &m->mtx_object, opts, m->mtx_recurse, file, 249dde96c99SJohn Baldwin line); 250dde96c99SJohn Baldwin _rel_sleep_lock(m, curthread, opts, file, line); 2516283b7d0SJohn Baldwin } 2526283b7d0SJohn Baldwin 2536283b7d0SJohn Baldwin void 2546283b7d0SJohn Baldwin _mtx_lock_spin_flags(struct mtx *m, int opts, const char *file, int line) 2556283b7d0SJohn Baldwin { 2566283b7d0SJohn Baldwin 257dde96c99SJohn Baldwin MPASS(curthread != NULL); 258dde96c99SJohn Baldwin _get_spin_lock(m, curthread, opts, file, line); 259dde96c99SJohn Baldwin LOCK_LOG_LOCK("LOCK", &m->mtx_object, opts, m->mtx_recurse, file, 260dde96c99SJohn Baldwin line); 261dde96c99SJohn Baldwin WITNESS_LOCK(&m->mtx_object, opts | LOP_EXCLUSIVE, file, line); 2626283b7d0SJohn Baldwin } 2636283b7d0SJohn Baldwin 2646283b7d0SJohn Baldwin void 2656283b7d0SJohn Baldwin _mtx_unlock_spin_flags(struct mtx *m, int opts, const char *file, int line) 2666283b7d0SJohn Baldwin { 2676283b7d0SJohn Baldwin 268dde96c99SJohn Baldwin MPASS(curthread != NULL); 26921377ce0SJohn Baldwin mtx_assert(m, MA_OWNED); 270dde96c99SJohn Baldwin WITNESS_UNLOCK(&m->mtx_object, opts | LOP_EXCLUSIVE, file, line); 271dde96c99SJohn Baldwin LOCK_LOG_LOCK("UNLOCK", &m->mtx_object, opts, m->mtx_recurse, file, 272dde96c99SJohn Baldwin line); 273dde96c99SJohn Baldwin _rel_spin_lock(m); 2746283b7d0SJohn Baldwin } 2756283b7d0SJohn Baldwin 2766283b7d0SJohn Baldwin /* 2779ed346baSBosko Milekic * The important part of mtx_trylock{,_flags}() 2789ed346baSBosko Milekic * Tries to acquire lock `m.' We do NOT handle recursion here; we assume that 2799ed346baSBosko Milekic * if we're called, it's because we know we don't already own this lock. 2800cde2e34SJason Evans */ 2810cde2e34SJason Evans int 2829ed346baSBosko Milekic _mtx_trylock(struct mtx *m, int opts, const char *file, int line) 2830cde2e34SJason Evans { 2840cde2e34SJason Evans int rval; 2850cde2e34SJason Evans 286b40ce416SJulian Elischer MPASS(curthread != NULL); 2879ed346baSBosko Milekic 2889ed346baSBosko Milekic /* 2899ed346baSBosko Milekic * _mtx_trylock does not accept MTX_NOSWITCH option. 2909ed346baSBosko Milekic */ 2915746a1d8SBosko Milekic KASSERT((opts & MTX_NOSWITCH) == 0, 2925746a1d8SBosko Milekic ("mtx_trylock() called with invalid option flag(s) %d", opts)); 2939ed346baSBosko Milekic 294b40ce416SJulian Elischer rval = _obtain_lock(m, curthread); 2959ed346baSBosko Milekic 29619284646SJohn Baldwin LOCK_LOG_TRY("LOCK", &m->mtx_object, opts, rval, file, line); 29719284646SJohn Baldwin if (rval) { 2989ed346baSBosko Milekic /* 2999ed346baSBosko Milekic * We do not handle recursion in _mtx_trylock; see the 3009ed346baSBosko Milekic * note at the top of the routine. 3019ed346baSBosko Milekic */ 3025746a1d8SBosko Milekic KASSERT(!mtx_recursed(m), 3035746a1d8SBosko Milekic ("mtx_trylock() called on a recursed mutex")); 3042d96f0b1SJohn Baldwin WITNESS_LOCK(&m->mtx_object, opts | LOP_EXCLUSIVE | LOP_TRYLOCK, 3052d96f0b1SJohn Baldwin file, line); 3060cde2e34SJason Evans } 3079ed346baSBosko Milekic 30819284646SJohn Baldwin return (rval); 3090cde2e34SJason Evans } 3100cde2e34SJason Evans 3110cde2e34SJason Evans /* 3129ed346baSBosko Milekic * _mtx_lock_sleep: the tougher part of acquiring an MTX_DEF lock. 3139ed346baSBosko Milekic * 3149ed346baSBosko Milekic * We call this if the lock is either contested (i.e. we need to go to 3159ed346baSBosko Milekic * sleep waiting for it), or if we need to recurse on it. 3160cde2e34SJason Evans */ 3170cde2e34SJason Evans void 3189ed346baSBosko Milekic _mtx_lock_sleep(struct mtx *m, int opts, const char *file, int line) 31936412d79SJohn Baldwin { 320b40ce416SJulian Elischer struct thread *td = curthread; 321b40ce416SJulian Elischer struct ksegrp *kg = td->td_ksegrp; 32236412d79SJohn Baldwin 323b40ce416SJulian Elischer if ((m->mtx_lock & MTX_FLAGMASK) == (uintptr_t)td) { 32436412d79SJohn Baldwin m->mtx_recurse++; 32508812b39SBosko Milekic atomic_set_ptr(&m->mtx_lock, MTX_RECURSED); 32619284646SJohn Baldwin if (LOCK_LOG_TEST(&m->mtx_object, opts)) 3275746a1d8SBosko Milekic CTR1(KTR_LOCK, "_mtx_lock_sleep: %p recursing", m); 32836412d79SJohn Baldwin return; 32936412d79SJohn Baldwin } 3309ed346baSBosko Milekic 33119284646SJohn Baldwin if (LOCK_LOG_TEST(&m->mtx_object, opts)) 33215ec816aSJohn Baldwin CTR4(KTR_LOCK, 33315ec816aSJohn Baldwin "_mtx_lock_sleep: %s contested (lock=%p) at %s:%d", 33419284646SJohn Baldwin m->mtx_object.lo_name, (void *)m->mtx_lock, file, line); 3351bd0eefbSJohn Baldwin 336b40ce416SJulian Elischer while (!_obtain_lock(m, td)) { 337f5271ebcSJohn Baldwin uintptr_t v; 338b40ce416SJulian Elischer struct thread *td1; 33936412d79SJohn Baldwin 3409ed346baSBosko Milekic mtx_lock_spin(&sched_lock); 34136412d79SJohn Baldwin /* 3429ed346baSBosko Milekic * Check if the lock has been released while spinning for 3439ed346baSBosko Milekic * the sched_lock. 34436412d79SJohn Baldwin */ 34536412d79SJohn Baldwin if ((v = m->mtx_lock) == MTX_UNOWNED) { 3469ed346baSBosko Milekic mtx_unlock_spin(&sched_lock); 34736412d79SJohn Baldwin continue; 34836412d79SJohn Baldwin } 3499ed346baSBosko Milekic 35036412d79SJohn Baldwin /* 3519ed346baSBosko Milekic * The mutex was marked contested on release. This means that 352b40ce416SJulian Elischer * there are threads blocked on it. 35336412d79SJohn Baldwin */ 35436412d79SJohn Baldwin if (v == MTX_CONTESTED) { 355b40ce416SJulian Elischer td1 = TAILQ_FIRST(&m->mtx_blocked); 356b40ce416SJulian Elischer MPASS(td1 != NULL); 357b40ce416SJulian Elischer m->mtx_lock = (uintptr_t)td | MTX_CONTESTED; 3589ed346baSBosko Milekic 359b40ce416SJulian Elischer if (td1->td_ksegrp->kg_pri.pri_level < kg->kg_pri.pri_level) 360b40ce416SJulian Elischer SET_PRIO(td, td1->td_ksegrp->kg_pri.pri_level); 3619ed346baSBosko Milekic mtx_unlock_spin(&sched_lock); 36236412d79SJohn Baldwin return; 36336412d79SJohn Baldwin } 3649ed346baSBosko Milekic 36536412d79SJohn Baldwin /* 3669ed346baSBosko Milekic * If the mutex isn't already contested and a failure occurs 3679ed346baSBosko Milekic * setting the contested bit, the mutex was either released 3689ed346baSBosko Milekic * or the state of the MTX_RECURSED bit changed. 36936412d79SJohn Baldwin */ 37036412d79SJohn Baldwin if ((v & MTX_CONTESTED) == 0 && 37136412d79SJohn Baldwin !atomic_cmpset_ptr(&m->mtx_lock, (void *)v, 37236412d79SJohn Baldwin (void *)(v | MTX_CONTESTED))) { 3739ed346baSBosko Milekic mtx_unlock_spin(&sched_lock); 37436412d79SJohn Baldwin continue; 37536412d79SJohn Baldwin } 37636412d79SJohn Baldwin 3779ed346baSBosko Milekic /* 3789ed346baSBosko Milekic * We deffinately must sleep for this lock. 3799ed346baSBosko Milekic */ 38036412d79SJohn Baldwin mtx_assert(m, MA_NOTOWNED); 38136412d79SJohn Baldwin 38236412d79SJohn Baldwin #ifdef notyet 38336412d79SJohn Baldwin /* 3849ed346baSBosko Milekic * If we're borrowing an interrupted thread's VM context, we 3859ed346baSBosko Milekic * must clean up before going to sleep. 38636412d79SJohn Baldwin */ 387b40ce416SJulian Elischer if (td->td_ithd != NULL) { 388b40ce416SJulian Elischer struct ithd *it = td->td_ithd; 38936412d79SJohn Baldwin 39036412d79SJohn Baldwin if (it->it_interrupted) { 39119284646SJohn Baldwin if (LOCK_LOG_TEST(&m->mtx_object, opts)) 39236412d79SJohn Baldwin CTR2(KTR_LOCK, 39315ec816aSJohn Baldwin "_mtx_lock_sleep: %p interrupted %p", 39436412d79SJohn Baldwin it, it->it_interrupted); 39536412d79SJohn Baldwin intr_thd_fixup(it); 39636412d79SJohn Baldwin } 39736412d79SJohn Baldwin } 39836412d79SJohn Baldwin #endif 39936412d79SJohn Baldwin 4009ed346baSBosko Milekic /* 4019ed346baSBosko Milekic * Put us on the list of threads blocked on this mutex. 4029ed346baSBosko Milekic */ 40336412d79SJohn Baldwin if (TAILQ_EMPTY(&m->mtx_blocked)) { 404b40ce416SJulian Elischer td1 = (struct thread *)(m->mtx_lock & MTX_FLAGMASK); 405b40ce416SJulian Elischer LIST_INSERT_HEAD(&td1->td_contested, m, mtx_contested); 406b40ce416SJulian Elischer TAILQ_INSERT_TAIL(&m->mtx_blocked, td, td_blkq); 40736412d79SJohn Baldwin } else { 408b40ce416SJulian Elischer TAILQ_FOREACH(td1, &m->mtx_blocked, td_blkq) 409b40ce416SJulian Elischer if (td1->td_ksegrp->kg_pri.pri_level > kg->kg_pri.pri_level) 41036412d79SJohn Baldwin break; 411b40ce416SJulian Elischer if (td1) 412b40ce416SJulian Elischer TAILQ_INSERT_BEFORE(td1, td, td_blkq); 41336412d79SJohn Baldwin else 414b40ce416SJulian Elischer TAILQ_INSERT_TAIL(&m->mtx_blocked, td, td_blkq); 41536412d79SJohn Baldwin } 41636412d79SJohn Baldwin 4179ed346baSBosko Milekic /* 4189ed346baSBosko Milekic * Save who we're blocked on. 4199ed346baSBosko Milekic */ 420b40ce416SJulian Elischer td->td_blocked = m; 421b40ce416SJulian Elischer td->td_mtxname = m->mtx_object.lo_name; 422b40ce416SJulian Elischer td->td_proc->p_stat = SMTX; 423b40ce416SJulian Elischer propagate_priority(td); 4249ed346baSBosko Milekic 42519284646SJohn Baldwin if (LOCK_LOG_TEST(&m->mtx_object, opts)) 426562e4ffeSJohn Baldwin CTR3(KTR_LOCK, 427b40ce416SJulian Elischer "_mtx_lock_sleep: p %p blocked on [%p] %s", td, m, 42819284646SJohn Baldwin m->mtx_object.lo_name); 4299ed346baSBosko Milekic 430b40ce416SJulian Elischer td->td_proc->p_stats->p_ru.ru_nvcsw++; 43120cdcc5bSJohn Baldwin mi_switch(); 4329ed346baSBosko Milekic 43319284646SJohn Baldwin if (LOCK_LOG_TEST(&m->mtx_object, opts)) 43436412d79SJohn Baldwin CTR3(KTR_LOCK, 4359ed346baSBosko Milekic "_mtx_lock_sleep: p %p free from blocked on [%p] %s", 436b40ce416SJulian Elischer td, m, m->mtx_object.lo_name); 4379ed346baSBosko Milekic 4389ed346baSBosko Milekic mtx_unlock_spin(&sched_lock); 43936412d79SJohn Baldwin } 4409ed346baSBosko Milekic 44136412d79SJohn Baldwin return; 4429ed346baSBosko Milekic } 4439ed346baSBosko Milekic 4449ed346baSBosko Milekic /* 4459ed346baSBosko Milekic * _mtx_lock_spin: the tougher part of acquiring an MTX_SPIN lock. 4469ed346baSBosko Milekic * 4479ed346baSBosko Milekic * This is only called if we need to actually spin for the lock. Recursion 4489ed346baSBosko Milekic * is handled inline. 4499ed346baSBosko Milekic */ 4509ed346baSBosko Milekic void 4516283b7d0SJohn Baldwin _mtx_lock_spin(struct mtx *m, int opts, critical_t mtx_crit, const char *file, 4529ed346baSBosko Milekic int line) 45336412d79SJohn Baldwin { 45436412d79SJohn Baldwin int i = 0; 45536412d79SJohn Baldwin 45619284646SJohn Baldwin if (LOCK_LOG_TEST(&m->mtx_object, opts)) 4575746a1d8SBosko Milekic CTR1(KTR_LOCK, "_mtx_lock_spin: %p spinning", m); 4589ed346baSBosko Milekic 45936412d79SJohn Baldwin for (;;) { 460b40ce416SJulian Elischer if (_obtain_lock(m, curthread)) 46136412d79SJohn Baldwin break; 4629ed346baSBosko Milekic 4637141f2adSJohn Baldwin /* Give interrupts a chance while we spin. */ 4647141f2adSJohn Baldwin critical_exit(mtx_crit); 46536412d79SJohn Baldwin while (m->mtx_lock != MTX_UNOWNED) { 46636412d79SJohn Baldwin if (i++ < 1000000) 46736412d79SJohn Baldwin continue; 46836412d79SJohn Baldwin if (i++ < 6000000) 46936412d79SJohn Baldwin DELAY(1); 47036412d79SJohn Baldwin #ifdef DDB 47136412d79SJohn Baldwin else if (!db_active) 47236412d79SJohn Baldwin #else 47336412d79SJohn Baldwin else 47436412d79SJohn Baldwin #endif 4759ed346baSBosko Milekic panic("spin lock %s held by %p for > 5 seconds", 47619284646SJohn Baldwin m->mtx_object.lo_name, (void *)m->mtx_lock); 47736412d79SJohn Baldwin } 4787141f2adSJohn Baldwin mtx_crit = critical_enter(); 47936412d79SJohn Baldwin } 48036412d79SJohn Baldwin 4816283b7d0SJohn Baldwin m->mtx_savecrit = mtx_crit; 48219284646SJohn Baldwin if (LOCK_LOG_TEST(&m->mtx_object, opts)) 4839ed346baSBosko Milekic CTR1(KTR_LOCK, "_mtx_lock_spin: %p spin done", m); 4849ed346baSBosko Milekic 48536412d79SJohn Baldwin return; 48636412d79SJohn Baldwin } 48736412d79SJohn Baldwin 4889ed346baSBosko Milekic /* 4899ed346baSBosko Milekic * _mtx_unlock_sleep: the tougher part of releasing an MTX_DEF lock. 4909ed346baSBosko Milekic * 4919ed346baSBosko Milekic * We are only called here if the lock is recursed or contested (i.e. we 4929ed346baSBosko Milekic * need to wake up a blocked thread). 4939ed346baSBosko Milekic */ 49436412d79SJohn Baldwin void 4959ed346baSBosko Milekic _mtx_unlock_sleep(struct mtx *m, int opts, const char *file, int line) 49636412d79SJohn Baldwin { 497b40ce416SJulian Elischer struct thread *td, *td1; 49836412d79SJohn Baldwin struct mtx *m1; 49936412d79SJohn Baldwin int pri; 500b40ce416SJulian Elischer struct ksegrp *kg; 50136412d79SJohn Baldwin 502b40ce416SJulian Elischer td = curthread; 503b40ce416SJulian Elischer kg = td->td_ksegrp; 5049ed346baSBosko Milekic 50508812b39SBosko Milekic if (mtx_recursed(m)) { 50636412d79SJohn Baldwin if (--(m->mtx_recurse) == 0) 50708812b39SBosko Milekic atomic_clear_ptr(&m->mtx_lock, MTX_RECURSED); 50819284646SJohn Baldwin if (LOCK_LOG_TEST(&m->mtx_object, opts)) 5099ed346baSBosko Milekic CTR1(KTR_LOCK, "_mtx_unlock_sleep: %p unrecurse", m); 51036412d79SJohn Baldwin return; 51136412d79SJohn Baldwin } 5129ed346baSBosko Milekic 5139ed346baSBosko Milekic mtx_lock_spin(&sched_lock); 51419284646SJohn Baldwin if (LOCK_LOG_TEST(&m->mtx_object, opts)) 5159ed346baSBosko Milekic CTR1(KTR_LOCK, "_mtx_unlock_sleep: %p contested", m); 5169ed346baSBosko Milekic 517b40ce416SJulian Elischer td1 = TAILQ_FIRST(&m->mtx_blocked); 518b40ce416SJulian Elischer MPASS(td->td_proc->p_magic == P_MAGIC); 519b40ce416SJulian Elischer MPASS(td1->td_proc->p_magic == P_MAGIC); 5209ed346baSBosko Milekic 521b40ce416SJulian Elischer TAILQ_REMOVE(&m->mtx_blocked, td1, td_blkq); 5229ed346baSBosko Milekic 52336412d79SJohn Baldwin if (TAILQ_EMPTY(&m->mtx_blocked)) { 52436412d79SJohn Baldwin LIST_REMOVE(m, mtx_contested); 52536412d79SJohn Baldwin _release_lock_quick(m); 52619284646SJohn Baldwin if (LOCK_LOG_TEST(&m->mtx_object, opts)) 5279ed346baSBosko Milekic CTR1(KTR_LOCK, "_mtx_unlock_sleep: %p not held", m); 52836412d79SJohn Baldwin } else 5299ed346baSBosko Milekic atomic_store_rel_ptr(&m->mtx_lock, (void *)MTX_CONTESTED); 5309ed346baSBosko Milekic 531d5a08a60SJake Burkholder pri = PRI_MAX; 532b40ce416SJulian Elischer LIST_FOREACH(m1, &td->td_contested, mtx_contested) { 533b40ce416SJulian Elischer int cp = TAILQ_FIRST(&m1->mtx_blocked)->td_ksegrp->kg_pri.pri_level; 53436412d79SJohn Baldwin if (cp < pri) 53536412d79SJohn Baldwin pri = cp; 53636412d79SJohn Baldwin } 5379ed346baSBosko Milekic 538b40ce416SJulian Elischer if (pri > kg->kg_pri.pri_native) 539b40ce416SJulian Elischer pri = kg->kg_pri.pri_native; 540b40ce416SJulian Elischer SET_PRIO(td, pri); 5419ed346baSBosko Milekic 54219284646SJohn Baldwin if (LOCK_LOG_TEST(&m->mtx_object, opts)) 5439ed346baSBosko Milekic CTR2(KTR_LOCK, "_mtx_unlock_sleep: %p contested setrunqueue %p", 544b40ce416SJulian Elischer m, td1); 5459ed346baSBosko Milekic 546b40ce416SJulian Elischer td1->td_blocked = NULL; 547b40ce416SJulian Elischer td1->td_proc->p_stat = SRUN; 548b40ce416SJulian Elischer setrunqueue(td1); 5499ed346baSBosko Milekic 550b40ce416SJulian Elischer if ((opts & MTX_NOSWITCH) == 0 && td1->td_ksegrp->kg_pri.pri_level < pri) { 55136412d79SJohn Baldwin #ifdef notyet 552b40ce416SJulian Elischer if (td->td_ithd != NULL) { 553b40ce416SJulian Elischer struct ithd *it = td->td_ithd; 55436412d79SJohn Baldwin 55536412d79SJohn Baldwin if (it->it_interrupted) { 55619284646SJohn Baldwin if (LOCK_LOG_TEST(&m->mtx_object, opts)) 55736412d79SJohn Baldwin CTR2(KTR_LOCK, 55815ec816aSJohn Baldwin "_mtx_unlock_sleep: %p interrupted %p", 55936412d79SJohn Baldwin it, it->it_interrupted); 56036412d79SJohn Baldwin intr_thd_fixup(it); 56136412d79SJohn Baldwin } 56236412d79SJohn Baldwin } 56336412d79SJohn Baldwin #endif 564b40ce416SJulian Elischer setrunqueue(td); 56519284646SJohn Baldwin if (LOCK_LOG_TEST(&m->mtx_object, opts)) 566562e4ffeSJohn Baldwin CTR2(KTR_LOCK, 5679ed346baSBosko Milekic "_mtx_unlock_sleep: %p switching out lock=%p", m, 5689ed346baSBosko Milekic (void *)m->mtx_lock); 5699ed346baSBosko Milekic 570b40ce416SJulian Elischer td->td_proc->p_stats->p_ru.ru_nivcsw++; 57136412d79SJohn Baldwin mi_switch(); 57219284646SJohn Baldwin if (LOCK_LOG_TEST(&m->mtx_object, opts)) 5739ed346baSBosko Milekic CTR2(KTR_LOCK, "_mtx_unlock_sleep: %p resuming lock=%p", 57431271627SJohn Baldwin m, (void *)m->mtx_lock); 57536412d79SJohn Baldwin } 57636412d79SJohn Baldwin 5779ed346baSBosko Milekic mtx_unlock_spin(&sched_lock); 5789ed346baSBosko Milekic 5799ed346baSBosko Milekic return; 5809ed346baSBosko Milekic } 5819ed346baSBosko Milekic 5829ed346baSBosko Milekic /* 5839ed346baSBosko Milekic * All the unlocking of MTX_SPIN locks is done inline. 5849ed346baSBosko Milekic * See the _rel_spin_lock() macro for the details. 5859ed346baSBosko Milekic */ 5869ed346baSBosko Milekic 5879ed346baSBosko Milekic /* 58815ec816aSJohn Baldwin * The backing function for the INVARIANTS-enabled mtx_assert() 5899ed346baSBosko Milekic */ 5901103f3b0SJohn Baldwin #ifdef INVARIANT_SUPPORT 5910cde2e34SJason Evans void 59256771ca7SJason Evans _mtx_assert(struct mtx *m, int what, const char *file, int line) 5930cde2e34SJason Evans { 5945cb0fbe4SJohn Baldwin 5955cb0fbe4SJohn Baldwin if (panicstr != NULL) 5965cb0fbe4SJohn Baldwin return; 597a10f4966SJake Burkholder switch (what) { 5980cde2e34SJason Evans case MA_OWNED: 5990cde2e34SJason Evans case MA_OWNED | MA_RECURSED: 6000cde2e34SJason Evans case MA_OWNED | MA_NOTRECURSED: 601a10f4966SJake Burkholder if (!mtx_owned(m)) 6020cde2e34SJason Evans panic("mutex %s not owned at %s:%d", 60319284646SJohn Baldwin m->mtx_object.lo_name, file, line); 604a10f4966SJake Burkholder if (mtx_recursed(m)) { 605a10f4966SJake Burkholder if ((what & MA_NOTRECURSED) != 0) 6060cde2e34SJason Evans panic("mutex %s recursed at %s:%d", 60719284646SJohn Baldwin m->mtx_object.lo_name, file, line); 608a10f4966SJake Burkholder } else if ((what & MA_RECURSED) != 0) { 6090cde2e34SJason Evans panic("mutex %s unrecursed at %s:%d", 61019284646SJohn Baldwin m->mtx_object.lo_name, file, line); 6110cde2e34SJason Evans } 6120cde2e34SJason Evans break; 6130cde2e34SJason Evans case MA_NOTOWNED: 614a10f4966SJake Burkholder if (mtx_owned(m)) 6150cde2e34SJason Evans panic("mutex %s owned at %s:%d", 61619284646SJohn Baldwin m->mtx_object.lo_name, file, line); 6170cde2e34SJason Evans break; 6180cde2e34SJason Evans default: 61956771ca7SJason Evans panic("unknown mtx_assert at %s:%d", file, line); 6200cde2e34SJason Evans } 6210cde2e34SJason Evans } 6220cde2e34SJason Evans #endif 6230cde2e34SJason Evans 6249ed346baSBosko Milekic /* 6259ed346baSBosko Milekic * The MUTEX_DEBUG-enabled mtx_validate() 62619284646SJohn Baldwin * 62719284646SJohn Baldwin * Most of these checks have been moved off into the LO_INITIALIZED flag 62819284646SJohn Baldwin * maintained by the witness code. 6299ed346baSBosko Milekic */ 63036412d79SJohn Baldwin #ifdef MUTEX_DEBUG 63136412d79SJohn Baldwin 63219284646SJohn Baldwin void mtx_validate __P((struct mtx *)); 63336412d79SJohn Baldwin 63419284646SJohn Baldwin void 63519284646SJohn Baldwin mtx_validate(struct mtx *m) 63636412d79SJohn Baldwin { 63736412d79SJohn Baldwin 63836412d79SJohn Baldwin /* 63936412d79SJohn Baldwin * XXX - When kernacc() is fixed on the alpha to handle K0_SEG memory properly 64036412d79SJohn Baldwin * we can re-enable the kernacc() checks. 64136412d79SJohn Baldwin */ 64236412d79SJohn Baldwin #ifndef __alpha__ 64376dcbd6fSBosko Milekic /* 64476dcbd6fSBosko Milekic * Can't call kernacc() from early init386(), especially when 64576dcbd6fSBosko Milekic * initializing Giant mutex, because some stuff in kernacc() 64676dcbd6fSBosko Milekic * requires Giant itself. 64776dcbd6fSBosko Milekic */ 648ab07087eSBosko Milekic if (!cold) 649ab07087eSBosko Milekic if (!kernacc((caddr_t)m, sizeof(m), 650ab07087eSBosko Milekic VM_PROT_READ | VM_PROT_WRITE)) 65119284646SJohn Baldwin panic("Can't read and write to mutex %p", m); 65236412d79SJohn Baldwin #endif 65336412d79SJohn Baldwin } 65436412d79SJohn Baldwin #endif 65536412d79SJohn Baldwin 6569ed346baSBosko Milekic /* 6579ed346baSBosko Milekic * Mutex initialization routine; initialize lock `m' of type contained in 6589ed346baSBosko Milekic * `opts' with options contained in `opts' and description `description.' 6599ed346baSBosko Milekic */ 66036412d79SJohn Baldwin void 6619ed346baSBosko Milekic mtx_init(struct mtx *m, const char *description, int opts) 66236412d79SJohn Baldwin { 66319284646SJohn Baldwin struct lock_object *lock; 6649ed346baSBosko Milekic 66519284646SJohn Baldwin MPASS((opts & ~(MTX_SPIN | MTX_QUIET | MTX_RECURSE | 66619284646SJohn Baldwin MTX_SLEEPABLE | MTX_NOWITNESS)) == 0); 6679ed346baSBosko Milekic 66836412d79SJohn Baldwin #ifdef MUTEX_DEBUG 6699ed346baSBosko Milekic /* Diagnostic and error correction */ 67019284646SJohn Baldwin mtx_validate(m); 6716936206eSJohn Baldwin #endif 67236412d79SJohn Baldwin 67319284646SJohn Baldwin bzero(m, sizeof(*m)); 67419284646SJohn Baldwin lock = &m->mtx_object; 67519284646SJohn Baldwin if (opts & MTX_SPIN) 67619284646SJohn Baldwin lock->lo_class = &lock_class_mtx_spin; 67719284646SJohn Baldwin else 67819284646SJohn Baldwin lock->lo_class = &lock_class_mtx_sleep; 67919284646SJohn Baldwin lock->lo_name = description; 68019284646SJohn Baldwin if (opts & MTX_QUIET) 68119284646SJohn Baldwin lock->lo_flags = LO_QUIET; 68219284646SJohn Baldwin if (opts & MTX_RECURSE) 68319284646SJohn Baldwin lock->lo_flags |= LO_RECURSABLE; 68419284646SJohn Baldwin if (opts & MTX_SLEEPABLE) 68519284646SJohn Baldwin lock->lo_flags |= LO_SLEEPABLE; 68619284646SJohn Baldwin if ((opts & MTX_NOWITNESS) == 0) 68719284646SJohn Baldwin lock->lo_flags |= LO_WITNESS; 68819284646SJohn Baldwin 68919284646SJohn Baldwin m->mtx_lock = MTX_UNOWNED; 69036412d79SJohn Baldwin TAILQ_INIT(&m->mtx_blocked); 6919ed346baSBosko Milekic 69219284646SJohn Baldwin LOCK_LOG_INIT(lock, opts); 693d1c1b841SJason Evans 69419284646SJohn Baldwin WITNESS_INIT(lock); 69536412d79SJohn Baldwin } 69636412d79SJohn Baldwin 6979ed346baSBosko Milekic /* 69819284646SJohn Baldwin * Remove lock `m' from all_mtx queue. We don't allow MTX_QUIET to be 69919284646SJohn Baldwin * passed in as a flag here because if the corresponding mtx_init() was 70019284646SJohn Baldwin * called with MTX_QUIET set, then it will already be set in the mutex's 70119284646SJohn Baldwin * flags. 7029ed346baSBosko Milekic */ 70336412d79SJohn Baldwin void 70436412d79SJohn Baldwin mtx_destroy(struct mtx *m) 70536412d79SJohn Baldwin { 70636412d79SJohn Baldwin 70719284646SJohn Baldwin LOCK_LOG_DESTROY(&m->mtx_object, 0); 7089ed346baSBosko Milekic 70919284646SJohn Baldwin if (!mtx_owned(m)) 71019284646SJohn Baldwin MPASS(mtx_unowned(m)); 71119284646SJohn Baldwin else { 71208812b39SBosko Milekic MPASS((m->mtx_lock & (MTX_RECURSED|MTX_CONTESTED)) == 0); 7139ed346baSBosko Milekic 71419284646SJohn Baldwin /* Tell witness this isn't locked to make it happy. */ 7152d96f0b1SJohn Baldwin WITNESS_UNLOCK(&m->mtx_object, LOP_EXCLUSIVE | LOP_NOSWITCH, 7162d96f0b1SJohn Baldwin __FILE__, __LINE__); 71736412d79SJohn Baldwin } 7180384fff8SJason Evans 71919284646SJohn Baldwin WITNESS_DESTROY(&m->mtx_object); 7200384fff8SJason Evans } 721