Annotation of src/sys/kern/kern_mutex.c, Revision 1.82
1.82 ! ad 1: /* $NetBSD: kern_mutex.c,v 1.81 2019/12/09 21:05:23 ad Exp $ */
1.2 ad 2:
3: /*-
1.81 ad 4: * Copyright (c) 2002, 2006, 2007, 2008, 2019 The NetBSD Foundation, Inc.
1.2 ad 5: * All rights reserved.
6: *
7: * This code is derived from software contributed to The NetBSD Foundation
8: * by Jason R. Thorpe and Andrew Doran.
9: *
10: * Redistribution and use in source and binary forms, with or without
11: * modification, are permitted provided that the following conditions
12: * are met:
13: * 1. Redistributions of source code must retain the above copyright
14: * notice, this list of conditions and the following disclaimer.
15: * 2. Redistributions in binary form must reproduce the above copyright
16: * notice, this list of conditions and the following disclaimer in the
17: * documentation and/or other materials provided with the distribution.
18: *
19: * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
20: * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
21: * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22: * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
23: * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
24: * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
25: * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
26: * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
27: * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
28: * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
29: * POSSIBILITY OF SUCH DAMAGE.
30: */
31:
32: /*
33: * Kernel mutex implementation, modeled after those found in Solaris,
34: * a description of which can be found in:
35: *
36: * Solaris Internals: Core Kernel Architecture, Jim Mauro and
37: * Richard McDougall.
38: */
39:
40: #define __MUTEX_PRIVATE
41:
42: #include <sys/cdefs.h>
1.82 ! ad 43: __KERNEL_RCSID(0, "$NetBSD: kern_mutex.c,v 1.81 2019/12/09 21:05:23 ad Exp $");
1.2 ad 44:
45: #include <sys/param.h>
1.46 pooka 46: #include <sys/atomic.h>
1.2 ad 47: #include <sys/proc.h>
48: #include <sys/mutex.h>
49: #include <sys/sched.h>
50: #include <sys/sleepq.h>
51: #include <sys/systm.h>
52: #include <sys/lockdebug.h>
53: #include <sys/kernel.h>
1.24 ad 54: #include <sys/intr.h>
1.29 xtraeme 55: #include <sys/lock.h>
1.50 rmind 56: #include <sys/types.h>
1.72 ozaki-r 57: #include <sys/cpu.h>
1.74 ozaki-r 58: #include <sys/pserialize.h>
1.2 ad 59:
60: #include <dev/lockstat.h>
61:
1.28 ad 62: #include <machine/lock.h>
63:
1.2 ad 64: /*
65: * When not running a debug kernel, spin mutexes are not much
66: * more than an splraiseipl() and splx() pair.
67: */
68:
69: #if defined(DIAGNOSTIC) || defined(MULTIPROCESSOR) || defined(LOCKDEBUG)
70: #define FULL
71: #endif
72:
73: /*
74: * Debugging support.
75: */
76:
77: #define MUTEX_WANTLOCK(mtx) \
1.23 yamt 78: LOCKDEBUG_WANTLOCK(MUTEX_DEBUG_P(mtx), (mtx), \
1.54 mlelstv 79: (uintptr_t)__builtin_return_address(0), 0)
1.65 pgoyette 80: #define MUTEX_TESTLOCK(mtx) \
81: LOCKDEBUG_WANTLOCK(MUTEX_DEBUG_P(mtx), (mtx), \
82: (uintptr_t)__builtin_return_address(0), -1)
1.2 ad 83: #define MUTEX_LOCKED(mtx) \
1.42 ad 84: LOCKDEBUG_LOCKED(MUTEX_DEBUG_P(mtx), (mtx), NULL, \
1.2 ad 85: (uintptr_t)__builtin_return_address(0), 0)
86: #define MUTEX_UNLOCKED(mtx) \
1.23 yamt 87: LOCKDEBUG_UNLOCKED(MUTEX_DEBUG_P(mtx), (mtx), \
1.2 ad 88: (uintptr_t)__builtin_return_address(0), 0)
89: #define MUTEX_ABORT(mtx, msg) \
1.64 christos 90: mutex_abort(__func__, __LINE__, mtx, msg)
1.2 ad 91:
92: #if defined(LOCKDEBUG)
93:
94: #define MUTEX_DASSERT(mtx, cond) \
95: do { \
1.75 ozaki-r 96: if (__predict_false(!(cond))) \
1.2 ad 97: MUTEX_ABORT(mtx, "assertion failed: " #cond); \
1.76 skrll 98: } while (/* CONSTCOND */ 0)
1.2 ad 99:
100: #else /* LOCKDEBUG */
101:
102: #define MUTEX_DASSERT(mtx, cond) /* nothing */
103:
104: #endif /* LOCKDEBUG */
105:
106: #if defined(DIAGNOSTIC)
107:
108: #define MUTEX_ASSERT(mtx, cond) \
109: do { \
1.75 ozaki-r 110: if (__predict_false(!(cond))) \
1.2 ad 111: MUTEX_ABORT(mtx, "assertion failed: " #cond); \
112: } while (/* CONSTCOND */ 0)
113:
114: #else /* DIAGNOSTIC */
115:
116: #define MUTEX_ASSERT(mtx, cond) /* nothing */
117:
118: #endif /* DIAGNOSTIC */
119:
120: /*
1.60 matt 121: * Some architectures can't use __cpu_simple_lock as is so allow a way
122: * for them to use an alternate definition.
123: */
124: #ifndef MUTEX_SPINBIT_LOCK_INIT
125: #define MUTEX_SPINBIT_LOCK_INIT(mtx) __cpu_simple_lock_init(&(mtx)->mtx_lock)
126: #endif
127: #ifndef MUTEX_SPINBIT_LOCKED_P
128: #define MUTEX_SPINBIT_LOCKED_P(mtx) __SIMPLELOCK_LOCKED_P(&(mtx)->mtx_lock)
129: #endif
130: #ifndef MUTEX_SPINBIT_LOCK_TRY
131: #define MUTEX_SPINBIT_LOCK_TRY(mtx) __cpu_simple_lock_try(&(mtx)->mtx_lock)
132: #endif
133: #ifndef MUTEX_SPINBIT_LOCK_UNLOCK
134: #define MUTEX_SPINBIT_LOCK_UNLOCK(mtx) __cpu_simple_unlock(&(mtx)->mtx_lock)
135: #endif
136:
137: #ifndef MUTEX_INITIALIZE_SPIN_IPL
138: #define MUTEX_INITIALIZE_SPIN_IPL(mtx, ipl) \
139: ((mtx)->mtx_ipl = makeiplcookie((ipl)))
140: #endif
141:
142: /*
1.2 ad 143: * Spin mutex SPL save / restore.
144: */
145:
146: #define MUTEX_SPIN_SPLRAISE(mtx) \
147: do { \
1.36 ad 148: struct cpu_info *x__ci; \
1.2 ad 149: int x__cnt, s; \
1.60 matt 150: s = splraiseipl(MUTEX_SPIN_IPL(mtx)); \
1.36 ad 151: x__ci = curcpu(); \
1.2 ad 152: x__cnt = x__ci->ci_mtx_count--; \
1.37 ad 153: __insn_barrier(); \
1.51 rmind 154: if (x__cnt == 0) \
1.2 ad 155: x__ci->ci_mtx_oldspl = (s); \
156: } while (/* CONSTCOND */ 0)
157:
158: #define MUTEX_SPIN_SPLRESTORE(mtx) \
159: do { \
160: struct cpu_info *x__ci = curcpu(); \
161: int s = x__ci->ci_mtx_oldspl; \
162: __insn_barrier(); \
1.51 rmind 163: if (++(x__ci->ci_mtx_count) == 0) \
1.2 ad 164: splx(s); \
165: } while (/* CONSTCOND */ 0)
166:
167: /*
1.80 ad 168: * Memory barriers.
169: */
170: #ifdef __HAVE_ATOMIC_AS_MEMBAR
171: #define MUTEX_MEMBAR_ENTER()
172: #define MUTEX_MEMBAR_EXIT()
173: #else
174: #define MUTEX_MEMBAR_ENTER() membar_enter()
175: #define MUTEX_MEMBAR_EXIT() membar_exit()
176: #endif
177:
178: /*
1.2 ad 179: * For architectures that provide 'simple' mutexes: they provide a
180: * CAS function that is either MP-safe, or does not need to be MP
181: * safe. Adaptive mutexes on these architectures do not require an
182: * additional interlock.
183: */
184:
185: #ifdef __HAVE_SIMPLE_MUTEXES
186:
187: #define MUTEX_OWNER(owner) \
188: (owner & MUTEX_THREAD)
189: #define MUTEX_HAS_WAITERS(mtx) \
190: (((int)(mtx)->mtx_owner & MUTEX_BIT_WAITERS) != 0)
191:
1.23 yamt 192: #define MUTEX_INITIALIZE_ADAPTIVE(mtx, dodebug) \
1.76 skrll 193: do { \
1.49 skrll 194: if (!dodebug) \
195: (mtx)->mtx_owner |= MUTEX_BIT_NODEBUG; \
1.76 skrll 196: } while (/* CONSTCOND */ 0)
1.2 ad 197:
1.23 yamt 198: #define MUTEX_INITIALIZE_SPIN(mtx, dodebug, ipl) \
1.2 ad 199: do { \
200: (mtx)->mtx_owner = MUTEX_BIT_SPIN; \
1.49 skrll 201: if (!dodebug) \
202: (mtx)->mtx_owner |= MUTEX_BIT_NODEBUG; \
1.60 matt 203: MUTEX_INITIALIZE_SPIN_IPL((mtx), (ipl)); \
204: MUTEX_SPINBIT_LOCK_INIT((mtx)); \
1.2 ad 205: } while (/* CONSTCOND */ 0)
206:
207: #define MUTEX_DESTROY(mtx) \
208: do { \
209: (mtx)->mtx_owner = MUTEX_THREAD; \
1.76 skrll 210: } while (/* CONSTCOND */ 0)
1.2 ad 211:
212: #define MUTEX_SPIN_P(mtx) \
213: (((mtx)->mtx_owner & MUTEX_BIT_SPIN) != 0)
214: #define MUTEX_ADAPTIVE_P(mtx) \
215: (((mtx)->mtx_owner & MUTEX_BIT_SPIN) == 0)
216:
1.49 skrll 217: #define MUTEX_DEBUG_P(mtx) (((mtx)->mtx_owner & MUTEX_BIT_NODEBUG) == 0)
1.23 yamt 218: #if defined(LOCKDEBUG)
1.49 skrll 219: #define MUTEX_OWNED(owner) (((owner) & ~MUTEX_BIT_NODEBUG) != 0)
1.59 matt 220: #define MUTEX_INHERITDEBUG(n, o) (n) |= (o) & MUTEX_BIT_NODEBUG
1.23 yamt 221: #else /* defined(LOCKDEBUG) */
222: #define MUTEX_OWNED(owner) ((owner) != 0)
1.59 matt 223: #define MUTEX_INHERITDEBUG(n, o) /* nothing */
1.23 yamt 224: #endif /* defined(LOCKDEBUG) */
1.2 ad 225:
226: static inline int
227: MUTEX_ACQUIRE(kmutex_t *mtx, uintptr_t curthread)
228: {
229: int rv;
1.59 matt 230: uintptr_t oldown = 0;
231: uintptr_t newown = curthread;
1.23 yamt 232:
1.59 matt 233: MUTEX_INHERITDEBUG(oldown, mtx->mtx_owner);
234: MUTEX_INHERITDEBUG(newown, oldown);
235: rv = MUTEX_CAS(&mtx->mtx_owner, oldown, newown);
1.80 ad 236: MUTEX_MEMBAR_ENTER();
1.2 ad 237: return rv;
238: }
239:
240: static inline int
241: MUTEX_SET_WAITERS(kmutex_t *mtx, uintptr_t owner)
242: {
243: int rv;
244: rv = MUTEX_CAS(&mtx->mtx_owner, owner, owner | MUTEX_BIT_WAITERS);
1.80 ad 245: MUTEX_MEMBAR_ENTER();
1.2 ad 246: return rv;
247: }
248:
249: static inline void
250: MUTEX_RELEASE(kmutex_t *mtx)
251: {
1.59 matt 252: uintptr_t newown;
1.23 yamt 253:
1.80 ad 254: MUTEX_MEMBAR_EXIT();
1.59 matt 255: newown = 0;
256: MUTEX_INHERITDEBUG(newown, mtx->mtx_owner);
257: mtx->mtx_owner = newown;
1.2 ad 258: }
259: #endif /* __HAVE_SIMPLE_MUTEXES */
260:
261: /*
262: * Patch in stubs via strong alias where they are not available.
263: */
264:
265: #if defined(LOCKDEBUG)
266: #undef __HAVE_MUTEX_STUBS
267: #undef __HAVE_SPIN_MUTEX_STUBS
268: #endif
269:
270: #ifndef __HAVE_MUTEX_STUBS
1.8 itohy 271: __strong_alias(mutex_enter,mutex_vector_enter);
272: __strong_alias(mutex_exit,mutex_vector_exit);
1.2 ad 273: #endif
274:
275: #ifndef __HAVE_SPIN_MUTEX_STUBS
1.8 itohy 276: __strong_alias(mutex_spin_enter,mutex_vector_enter);
277: __strong_alias(mutex_spin_exit,mutex_vector_exit);
1.2 ad 278: #endif
279:
1.67 christos 280: static void mutex_abort(const char *, size_t, const kmutex_t *,
281: const char *);
1.79 ozaki-r 282: static void mutex_dump(const volatile void *, lockop_printer_t);
1.2 ad 283:
284: lockops_t mutex_spin_lockops = {
1.68 ozaki-r 285: .lo_name = "Mutex",
286: .lo_type = LOCKOPS_SPIN,
287: .lo_dump = mutex_dump,
1.2 ad 288: };
289:
290: lockops_t mutex_adaptive_lockops = {
1.68 ozaki-r 291: .lo_name = "Mutex",
292: .lo_type = LOCKOPS_SLEEP,
293: .lo_dump = mutex_dump,
1.2 ad 294: };
295:
1.5 yamt 296: syncobj_t mutex_syncobj = {
1.70 ozaki-r 297: .sobj_flag = SOBJ_SLEEPQ_SORTED,
298: .sobj_unsleep = turnstile_unsleep,
299: .sobj_changepri = turnstile_changepri,
300: .sobj_lendpri = sleepq_lendpri,
301: .sobj_owner = (void *)mutex_owner,
1.5 yamt 302: };
303:
1.2 ad 304: /*
305: * mutex_dump:
306: *
307: * Dump the contents of a mutex structure.
308: */
1.78 ozaki-r 309: static void
1.79 ozaki-r 310: mutex_dump(const volatile void *cookie, lockop_printer_t pr)
1.2 ad 311: {
1.67 christos 312: const volatile kmutex_t *mtx = cookie;
1.2 ad 313:
1.79 ozaki-r 314: pr("owner field : %#018lx wait/spin: %16d/%d\n",
1.2 ad 315: (long)MUTEX_OWNER(mtx->mtx_owner), MUTEX_HAS_WAITERS(mtx),
316: MUTEX_SPIN_P(mtx));
317: }
318:
319: /*
320: * mutex_abort:
321: *
1.3 ad 322: * Dump information about an error and panic the system. This
323: * generates a lot of machine code in the DIAGNOSTIC case, so
324: * we ask the compiler to not inline it.
1.2 ad 325: */
1.78 ozaki-r 326: static void __noinline
1.67 christos 327: mutex_abort(const char *func, size_t line, const kmutex_t *mtx, const char *msg)
1.2 ad 328: {
329:
1.64 christos 330: LOCKDEBUG_ABORT(func, line, mtx, (MUTEX_SPIN_P(mtx) ?
331: &mutex_spin_lockops : &mutex_adaptive_lockops), msg);
1.2 ad 332: }
333:
334: /*
335: * mutex_init:
336: *
337: * Initialize a mutex for use. Note that adaptive mutexes are in
338: * essence spin mutexes that can sleep to avoid deadlock and wasting
339: * CPU time. We can't easily provide a type of mutex that always
340: * sleeps - see comments in mutex_vector_enter() about releasing
341: * mutexes unlocked.
342: */
1.71 ozaki-r 343: void _mutex_init(kmutex_t *, kmutex_type_t, int, uintptr_t);
1.2 ad 344: void
1.71 ozaki-r 345: _mutex_init(kmutex_t *mtx, kmutex_type_t type, int ipl,
346: uintptr_t return_address)
1.2 ad 347: {
1.81 ad 348: lockops_t *lockops __unused;
1.23 yamt 349: bool dodebug;
1.2 ad 350:
351: memset(mtx, 0, sizeof(*mtx));
352:
1.81 ad 353: if (ipl == IPL_NONE || ipl == IPL_SOFTCLOCK ||
354: ipl == IPL_SOFTBIO || ipl == IPL_SOFTNET ||
355: ipl == IPL_SOFTSERIAL) {
356: lockops = (type == MUTEX_NODEBUG ?
357: NULL : &mutex_adaptive_lockops);
358: dodebug = LOCKDEBUG_ALLOC(mtx, lockops, return_address);
1.23 yamt 359: MUTEX_INITIALIZE_ADAPTIVE(mtx, dodebug);
1.81 ad 360: } else {
361: lockops = (type == MUTEX_NODEBUG ?
362: NULL : &mutex_spin_lockops);
363: dodebug = LOCKDEBUG_ALLOC(mtx, lockops, return_address);
1.23 yamt 364: MUTEX_INITIALIZE_SPIN(mtx, dodebug, ipl);
1.2 ad 365: }
366: }
367:
1.71 ozaki-r 368: void
369: mutex_init(kmutex_t *mtx, kmutex_type_t type, int ipl)
370: {
371:
372: _mutex_init(mtx, type, ipl, (uintptr_t)__builtin_return_address(0));
373: }
374:
1.2 ad 375: /*
376: * mutex_destroy:
377: *
378: * Tear down a mutex.
379: */
380: void
381: mutex_destroy(kmutex_t *mtx)
382: {
383:
384: if (MUTEX_ADAPTIVE_P(mtx)) {
385: MUTEX_ASSERT(mtx, !MUTEX_OWNED(mtx->mtx_owner) &&
386: !MUTEX_HAS_WAITERS(mtx));
387: } else {
1.60 matt 388: MUTEX_ASSERT(mtx, !MUTEX_SPINBIT_LOCKED_P(mtx));
1.2 ad 389: }
390:
1.23 yamt 391: LOCKDEBUG_FREE(MUTEX_DEBUG_P(mtx), mtx);
1.2 ad 392: MUTEX_DESTROY(mtx);
393: }
394:
1.50 rmind 395: #ifdef MULTIPROCESSOR
1.2 ad 396: /*
1.50 rmind 397: * mutex_oncpu:
1.2 ad 398: *
399: * Return true if an adaptive mutex owner is running on a CPU in the
400: * system. If the target is waiting on the kernel big lock, then we
1.15 ad 401: * must release it. This is necessary to avoid deadlock.
1.2 ad 402: */
1.50 rmind 403: static bool
404: mutex_oncpu(uintptr_t owner)
1.2 ad 405: {
406: struct cpu_info *ci;
1.50 rmind 407: lwp_t *l;
1.2 ad 408:
1.50 rmind 409: KASSERT(kpreempt_disabled());
410:
411: if (!MUTEX_OWNED(owner)) {
412: return false;
413: }
1.2 ad 414:
1.50 rmind 415: /*
416: * See lwp_dtor() why dereference of the LWP pointer is safe.
417: * We must have kernel preemption disabled for that.
418: */
419: l = (lwp_t *)MUTEX_OWNER(owner);
420: ci = l->l_cpu;
1.2 ad 421:
1.50 rmind 422: if (ci && ci->ci_curlwp == l) {
423: /* Target is running; do we need to block? */
424: return (ci->ci_biglock_wanted != l);
425: }
1.15 ad 426:
1.50 rmind 427: /* Not running. It may be safe to block now. */
428: return false;
1.2 ad 429: }
1.15 ad 430: #endif /* MULTIPROCESSOR */
1.2 ad 431:
432: /*
433: * mutex_vector_enter:
434: *
1.45 rmind 435: * Support routine for mutex_enter() that must handle all cases. In
1.2 ad 436: * the LOCKDEBUG case, mutex_enter() is always aliased here, even if
1.62 prlw1 437: * fast-path stubs are available. If a mutex_spin_enter() stub is
1.2 ad 438: * not available, then it is also aliased directly here.
439: */
440: void
441: mutex_vector_enter(kmutex_t *mtx)
442: {
443: uintptr_t owner, curthread;
444: turnstile_t *ts;
445: #ifdef MULTIPROCESSOR
446: u_int count;
447: #endif
448: LOCKSTAT_COUNTER(spincnt);
449: LOCKSTAT_COUNTER(slpcnt);
450: LOCKSTAT_TIMER(spintime);
451: LOCKSTAT_TIMER(slptime);
452: LOCKSTAT_FLAG(lsflag);
453:
454: /*
455: * Handle spin mutexes.
456: */
457: if (MUTEX_SPIN_P(mtx)) {
458: #if defined(LOCKDEBUG) && defined(MULTIPROCESSOR)
459: u_int spins = 0;
460: #endif
461: MUTEX_SPIN_SPLRAISE(mtx);
462: MUTEX_WANTLOCK(mtx);
463: #ifdef FULL
1.60 matt 464: if (MUTEX_SPINBIT_LOCK_TRY(mtx)) {
1.2 ad 465: MUTEX_LOCKED(mtx);
466: return;
467: }
468: #if !defined(MULTIPROCESSOR)
469: MUTEX_ABORT(mtx, "locking against myself");
470: #else /* !MULTIPROCESSOR */
471:
472: LOCKSTAT_ENTER(lsflag);
473: LOCKSTAT_START_TIMER(lsflag, spintime);
474: count = SPINLOCK_BACKOFF_MIN;
475:
476: /*
477: * Spin testing the lock word and do exponential backoff
478: * to reduce cache line ping-ponging between CPUs.
479: */
480: do {
1.60 matt 481: while (MUTEX_SPINBIT_LOCKED_P(mtx)) {
1.63 msaitoh 482: SPINLOCK_BACKOFF(count);
1.2 ad 483: #ifdef LOCKDEBUG
484: if (SPINLOCK_SPINOUT(spins))
485: MUTEX_ABORT(mtx, "spinout");
486: #endif /* LOCKDEBUG */
487: }
1.60 matt 488: } while (!MUTEX_SPINBIT_LOCK_TRY(mtx));
1.2 ad 489:
490: if (count != SPINLOCK_BACKOFF_MIN) {
491: LOCKSTAT_STOP_TIMER(lsflag, spintime);
492: LOCKSTAT_EVENT(lsflag, mtx,
493: LB_SPIN_MUTEX | LB_SPIN, 1, spintime);
494: }
495: LOCKSTAT_EXIT(lsflag);
496: #endif /* !MULTIPROCESSOR */
497: #endif /* FULL */
498: MUTEX_LOCKED(mtx);
499: return;
500: }
501:
502: curthread = (uintptr_t)curlwp;
503:
504: MUTEX_DASSERT(mtx, MUTEX_ADAPTIVE_P(mtx));
505: MUTEX_ASSERT(mtx, curthread != 0);
1.72 ozaki-r 506: MUTEX_ASSERT(mtx, !cpu_intr_p());
1.2 ad 507: MUTEX_WANTLOCK(mtx);
508:
509: if (panicstr == NULL) {
1.77 ozaki-r 510: KDASSERT(pserialize_not_in_read_section());
1.2 ad 511: LOCKDEBUG_BARRIER(&kernel_lock, 1);
512: }
513:
514: LOCKSTAT_ENTER(lsflag);
515:
516: /*
517: * Adaptive mutex; spin trying to acquire the mutex. If we
518: * determine that the owner is not running on a processor,
519: * then we stop spinning, and sleep instead.
520: */
1.50 rmind 521: KPREEMPT_DISABLE(curlwp);
1.34 ad 522: for (owner = mtx->mtx_owner;;) {
1.2 ad 523: if (!MUTEX_OWNED(owner)) {
524: /*
525: * Mutex owner clear could mean two things:
526: *
527: * * The mutex has been released.
528: * * The owner field hasn't been set yet.
529: *
530: * Try to acquire it again. If that fails,
531: * we'll just loop again.
532: */
533: if (MUTEX_ACQUIRE(mtx, curthread))
534: break;
1.34 ad 535: owner = mtx->mtx_owner;
1.2 ad 536: continue;
537: }
1.50 rmind 538: if (__predict_false(MUTEX_OWNER(owner) == curthread)) {
1.2 ad 539: MUTEX_ABORT(mtx, "locking against myself");
1.50 rmind 540: }
1.2 ad 541: #ifdef MULTIPROCESSOR
542: /*
543: * Check to see if the owner is running on a processor.
544: * If so, then we should just spin, as the owner will
545: * likely release the lock very soon.
546: */
1.50 rmind 547: if (mutex_oncpu(owner)) {
1.2 ad 548: LOCKSTAT_START_TIMER(lsflag, spintime);
549: count = SPINLOCK_BACKOFF_MIN;
1.50 rmind 550: do {
1.53 rmind 551: KPREEMPT_ENABLE(curlwp);
1.34 ad 552: SPINLOCK_BACKOFF(count);
1.53 rmind 553: KPREEMPT_DISABLE(curlwp);
1.2 ad 554: owner = mtx->mtx_owner;
1.50 rmind 555: } while (mutex_oncpu(owner));
1.2 ad 556: LOCKSTAT_STOP_TIMER(lsflag, spintime);
557: LOCKSTAT_COUNT(spincnt, 1);
558: if (!MUTEX_OWNED(owner))
559: continue;
560: }
561: #endif
562:
563: ts = turnstile_lookup(mtx);
564:
565: /*
566: * Once we have the turnstile chain interlock, mark the
1.69 skrll 567: * mutex as having waiters. If that fails, spin again:
1.2 ad 568: * chances are that the mutex has been released.
569: */
570: if (!MUTEX_SET_WAITERS(mtx, owner)) {
571: turnstile_exit(mtx);
1.34 ad 572: owner = mtx->mtx_owner;
1.2 ad 573: continue;
574: }
575:
576: #ifdef MULTIPROCESSOR
577: /*
578: * mutex_exit() is permitted to release the mutex without
579: * any interlocking instructions, and the following can
580: * occur as a result:
581: *
582: * CPU 1: MUTEX_SET_WAITERS() CPU2: mutex_exit()
583: * ---------------------------- ----------------------------
584: * .. acquire cache line
585: * .. test for waiters
586: * acquire cache line <- lose cache line
587: * lock cache line ..
588: * verify mutex is held ..
589: * set waiters ..
590: * unlock cache line ..
591: * lose cache line -> acquire cache line
592: * .. clear lock word, waiters
593: * return success
594: *
1.50 rmind 595: * There is another race that can occur: a third CPU could
1.2 ad 596: * acquire the mutex as soon as it is released. Since
597: * adaptive mutexes are primarily spin mutexes, this is not
598: * something that we need to worry about too much. What we
599: * do need to ensure is that the waiters bit gets set.
600: *
601: * To allow the unlocked release, we need to make some
602: * assumptions here:
603: *
604: * o Release is the only non-atomic/unlocked operation
605: * that can be performed on the mutex. (It must still
606: * be atomic on the local CPU, e.g. in case interrupted
607: * or preempted).
608: *
609: * o At any given time, MUTEX_SET_WAITERS() can only ever
1.21 pooka 610: * be in progress on one CPU in the system - guaranteed
1.2 ad 611: * by the turnstile chain lock.
612: *
613: * o No other operations other than MUTEX_SET_WAITERS()
614: * and release can modify a mutex with a non-zero
615: * owner field.
616: *
617: * o The result of a successful MUTEX_SET_WAITERS() call
618: * is an unbuffered write that is immediately visible
619: * to all other processors in the system.
620: *
621: * o If the holding LWP switches away, it posts a store
622: * fence before changing curlwp, ensuring that any
623: * overwrite of the mutex waiters flag by mutex_exit()
624: * completes before the modification of curlwp becomes
625: * visible to this CPU.
626: *
1.14 yamt 627: * o mi_switch() posts a store fence before setting curlwp
1.2 ad 628: * and before resuming execution of an LWP.
629: *
630: * o _kernel_lock() posts a store fence before setting
631: * curcpu()->ci_biglock_wanted, and after clearing it.
632: * This ensures that any overwrite of the mutex waiters
633: * flag by mutex_exit() completes before the modification
634: * of ci_biglock_wanted becomes visible.
635: *
636: * We now post a read memory barrier (after setting the
637: * waiters field) and check the lock holder's status again.
638: * Some of the possible outcomes (not an exhaustive list):
639: *
1.50 rmind 640: * 1. The on-CPU check returns true: the holding LWP is
1.2 ad 641: * running again. The lock may be released soon and
642: * we should spin. Importantly, we can't trust the
643: * value of the waiters flag.
644: *
1.50 rmind 645: * 2. The on-CPU check returns false: the holding LWP is
1.39 yamt 646: * not running. We now have the opportunity to check
1.2 ad 647: * if mutex_exit() has blatted the modifications made
648: * by MUTEX_SET_WAITERS().
649: *
1.50 rmind 650: * 3. The on-CPU check returns false: the holding LWP may
1.2 ad 651: * or may not be running. It has context switched at
652: * some point during our check. Again, we have the
653: * chance to see if the waiters bit is still set or
654: * has been overwritten.
655: *
1.50 rmind 656: * 4. The on-CPU check returns false: the holding LWP is
1.2 ad 657: * running on a CPU, but wants the big lock. It's OK
658: * to check the waiters field in this case.
659: *
660: * 5. The has-waiters check fails: the mutex has been
661: * released, the waiters flag cleared and another LWP
662: * now owns the mutex.
663: *
664: * 6. The has-waiters check fails: the mutex has been
665: * released.
666: *
667: * If the waiters bit is not set it's unsafe to go asleep,
668: * as we might never be awoken.
669: */
1.50 rmind 670: if ((membar_consumer(), mutex_oncpu(owner)) ||
1.24 ad 671: (membar_consumer(), !MUTEX_HAS_WAITERS(mtx))) {
1.2 ad 672: turnstile_exit(mtx);
1.34 ad 673: owner = mtx->mtx_owner;
1.2 ad 674: continue;
675: }
676: #endif /* MULTIPROCESSOR */
677:
678: LOCKSTAT_START_TIMER(lsflag, slptime);
679:
1.5 yamt 680: turnstile_block(ts, TS_WRITER_Q, mtx, &mutex_syncobj);
1.2 ad 681:
682: LOCKSTAT_STOP_TIMER(lsflag, slptime);
683: LOCKSTAT_COUNT(slpcnt, 1);
1.34 ad 684:
685: owner = mtx->mtx_owner;
1.2 ad 686: }
1.50 rmind 687: KPREEMPT_ENABLE(curlwp);
1.2 ad 688:
689: LOCKSTAT_EVENT(lsflag, mtx, LB_ADAPTIVE_MUTEX | LB_SLEEP1,
690: slpcnt, slptime);
691: LOCKSTAT_EVENT(lsflag, mtx, LB_ADAPTIVE_MUTEX | LB_SPIN,
692: spincnt, spintime);
693: LOCKSTAT_EXIT(lsflag);
694:
695: MUTEX_DASSERT(mtx, MUTEX_OWNER(mtx->mtx_owner) == curthread);
696: MUTEX_LOCKED(mtx);
697: }
698:
699: /*
700: * mutex_vector_exit:
701: *
702: * Support routine for mutex_exit() that handles all cases.
703: */
704: void
705: mutex_vector_exit(kmutex_t *mtx)
706: {
707: turnstile_t *ts;
708: uintptr_t curthread;
709:
710: if (MUTEX_SPIN_P(mtx)) {
711: #ifdef FULL
1.60 matt 712: if (__predict_false(!MUTEX_SPINBIT_LOCKED_P(mtx))) {
1.2 ad 713: MUTEX_ABORT(mtx, "exiting unheld spin mutex");
1.33 ad 714: }
1.2 ad 715: MUTEX_UNLOCKED(mtx);
1.60 matt 716: MUTEX_SPINBIT_LOCK_UNLOCK(mtx);
1.2 ad 717: #endif
718: MUTEX_SPIN_SPLRESTORE(mtx);
719: return;
720: }
721:
722: curthread = (uintptr_t)curlwp;
723: MUTEX_DASSERT(mtx, curthread != 0);
724: MUTEX_ASSERT(mtx, MUTEX_OWNER(mtx->mtx_owner) == curthread);
725: MUTEX_UNLOCKED(mtx);
1.58 mrg 726: #if !defined(LOCKDEBUG)
727: __USE(curthread);
728: #endif
1.2 ad 729:
1.15 ad 730: #ifdef LOCKDEBUG
731: /*
732: * Avoid having to take the turnstile chain lock every time
733: * around. Raise the priority level to splhigh() in order
734: * to disable preemption and so make the following atomic.
735: */
736: {
737: int s = splhigh();
738: if (!MUTEX_HAS_WAITERS(mtx)) {
739: MUTEX_RELEASE(mtx);
740: splx(s);
741: return;
742: }
743: splx(s);
744: }
745: #endif
746:
1.2 ad 747: /*
748: * Get this lock's turnstile. This gets the interlock on
749: * the sleep queue. Once we have that, we can clear the
750: * lock. If there was no turnstile for the lock, there
751: * were no waiters remaining.
752: */
753: ts = turnstile_lookup(mtx);
754:
755: if (ts == NULL) {
756: MUTEX_RELEASE(mtx);
757: turnstile_exit(mtx);
758: } else {
759: MUTEX_RELEASE(mtx);
760: turnstile_wakeup(ts, TS_WRITER_Q,
761: TS_WAITERS(ts, TS_WRITER_Q), NULL);
762: }
763: }
764:
1.4 ad 765: #ifndef __HAVE_SIMPLE_MUTEXES
766: /*
767: * mutex_wakeup:
768: *
769: * Support routine for mutex_exit() that wakes up all waiters.
770: * We assume that the mutex has been released, but it need not
771: * be.
772: */
773: void
774: mutex_wakeup(kmutex_t *mtx)
775: {
776: turnstile_t *ts;
777:
778: ts = turnstile_lookup(mtx);
779: if (ts == NULL) {
780: turnstile_exit(mtx);
781: return;
782: }
783: MUTEX_CLEAR_WAITERS(mtx);
784: turnstile_wakeup(ts, TS_WRITER_Q, TS_WAITERS(ts, TS_WRITER_Q), NULL);
785: }
786: #endif /* !__HAVE_SIMPLE_MUTEXES */
787:
1.2 ad 788: /*
789: * mutex_owned:
790: *
1.3 ad 791: * Return true if the current LWP (adaptive) or CPU (spin)
792: * holds the mutex.
1.2 ad 793: */
794: int
1.66 christos 795: mutex_owned(const kmutex_t *mtx)
1.2 ad 796: {
797:
1.35 ad 798: if (mtx == NULL)
799: return 0;
1.2 ad 800: if (MUTEX_ADAPTIVE_P(mtx))
801: return MUTEX_OWNER(mtx->mtx_owner) == (uintptr_t)curlwp;
802: #ifdef FULL
1.60 matt 803: return MUTEX_SPINBIT_LOCKED_P(mtx);
1.2 ad 804: #else
805: return 1;
806: #endif
807: }
808:
809: /*
810: * mutex_owner:
811: *
1.6 ad 812: * Return the current owner of an adaptive mutex. Used for
813: * priority inheritance.
1.2 ad 814: */
1.27 ad 815: lwp_t *
1.66 christos 816: mutex_owner(const kmutex_t *mtx)
1.2 ad 817: {
818:
819: MUTEX_ASSERT(mtx, MUTEX_ADAPTIVE_P(mtx));
820: return (struct lwp *)MUTEX_OWNER(mtx->mtx_owner);
821: }
822:
823: /*
1.81 ad 824: * mutex_owner_running:
825: *
1.82 ! ad 826: * Return true if an adaptive mutex is unheld, or held and the owner is
! 827: * running on a CPU. For the pagedaemon.
1.81 ad 828: */
829: bool
830: mutex_owner_running(const kmutex_t *mtx)
831: {
1.82 ! ad 832: #ifdef MULTIPROCESSOR
! 833: uintptr_t owner;
1.81 ad 834: bool rv;
835:
836: MUTEX_ASSERT(mtx, MUTEX_ADAPTIVE_P(mtx));
837: kpreempt_disable();
1.82 ! ad 838: owner = mtx->mtx_owner;
! 839: rv = (MUTEX_OWNED(owner) && mutex_oncpu(MUTEX_OWNER(owner));
1.81 ad 840: kpreempt_enable();
841: return rv;
1.82 ! ad 842: #else
! 843: return mutex_owner(mtx) == curlwp;
! 844: #endif
1.81 ad 845: }
846:
847: /*
1.65 pgoyette 848: * mutex_ownable:
849: *
850: * When compiled with DEBUG and LOCKDEBUG defined, ensure that
851: * the mutex is available. We cannot use !mutex_owned() since
852: * that won't work correctly for spin mutexes.
853: */
854: int
1.66 christos 855: mutex_ownable(const kmutex_t *mtx)
1.65 pgoyette 856: {
857:
858: #ifdef LOCKDEBUG
859: MUTEX_TESTLOCK(mtx);
860: #endif
861: return 1;
862: }
863:
864: /*
1.2 ad 865: * mutex_tryenter:
866: *
867: * Try to acquire the mutex; return non-zero if we did.
868: */
869: int
870: mutex_tryenter(kmutex_t *mtx)
871: {
872: uintptr_t curthread;
873:
874: /*
875: * Handle spin mutexes.
876: */
877: if (MUTEX_SPIN_P(mtx)) {
878: MUTEX_SPIN_SPLRAISE(mtx);
879: #ifdef FULL
1.60 matt 880: if (MUTEX_SPINBIT_LOCK_TRY(mtx)) {
1.4 ad 881: MUTEX_WANTLOCK(mtx);
1.2 ad 882: MUTEX_LOCKED(mtx);
883: return 1;
884: }
885: MUTEX_SPIN_SPLRESTORE(mtx);
886: #else
1.4 ad 887: MUTEX_WANTLOCK(mtx);
1.2 ad 888: MUTEX_LOCKED(mtx);
889: return 1;
890: #endif
891: } else {
892: curthread = (uintptr_t)curlwp;
893: MUTEX_ASSERT(mtx, curthread != 0);
894: if (MUTEX_ACQUIRE(mtx, curthread)) {
1.4 ad 895: MUTEX_WANTLOCK(mtx);
1.2 ad 896: MUTEX_LOCKED(mtx);
897: MUTEX_DASSERT(mtx,
898: MUTEX_OWNER(mtx->mtx_owner) == curthread);
899: return 1;
900: }
901: }
902:
903: return 0;
904: }
905:
906: #if defined(__HAVE_SPIN_MUTEX_STUBS) || defined(FULL)
907: /*
908: * mutex_spin_retry:
909: *
910: * Support routine for mutex_spin_enter(). Assumes that the caller
911: * has already raised the SPL, and adjusted counters.
912: */
913: void
914: mutex_spin_retry(kmutex_t *mtx)
915: {
916: #ifdef MULTIPROCESSOR
917: u_int count;
918: LOCKSTAT_TIMER(spintime);
919: LOCKSTAT_FLAG(lsflag);
920: #ifdef LOCKDEBUG
921: u_int spins = 0;
922: #endif /* LOCKDEBUG */
923:
924: MUTEX_WANTLOCK(mtx);
925:
926: LOCKSTAT_ENTER(lsflag);
927: LOCKSTAT_START_TIMER(lsflag, spintime);
928: count = SPINLOCK_BACKOFF_MIN;
929:
930: /*
931: * Spin testing the lock word and do exponential backoff
932: * to reduce cache line ping-ponging between CPUs.
933: */
934: do {
1.60 matt 935: while (MUTEX_SPINBIT_LOCKED_P(mtx)) {
1.63 msaitoh 936: SPINLOCK_BACKOFF(count);
1.2 ad 937: #ifdef LOCKDEBUG
938: if (SPINLOCK_SPINOUT(spins))
939: MUTEX_ABORT(mtx, "spinout");
940: #endif /* LOCKDEBUG */
941: }
1.60 matt 942: } while (!MUTEX_SPINBIT_LOCK_TRY(mtx));
1.2 ad 943:
944: LOCKSTAT_STOP_TIMER(lsflag, spintime);
945: LOCKSTAT_EVENT(lsflag, mtx, LB_SPIN_MUTEX | LB_SPIN, 1, spintime);
946: LOCKSTAT_EXIT(lsflag);
947:
948: MUTEX_LOCKED(mtx);
949: #else /* MULTIPROCESSOR */
950: MUTEX_ABORT(mtx, "locking against myself");
951: #endif /* MULTIPROCESSOR */
952: }
953: #endif /* defined(__HAVE_SPIN_MUTEX_STUBS) || defined(FULL) */
CVSweb <webmaster@jp.NetBSD.org>