Annotation of src/sys/kern/kern_mutex.c, Revision 1.51
1.51 ! rmind 1: /* $NetBSD: kern_mutex.c,v 1.50 2011/03/20 23:19:16 rmind Exp $ */
1.2 ad 2:
3: /*-
1.30 ad 4: * Copyright (c) 2002, 2006, 2007, 2008 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.51 ! rmind 43: __KERNEL_RCSID(0, "$NetBSD: kern_mutex.c,v 1.50 2011/03/20 23:19:16 rmind 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.2 ad 57:
58: #include <dev/lockstat.h>
59:
1.28 ad 60: #include <machine/lock.h>
61:
1.44 wrstuden 62: #include "opt_sa.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.40 ad 79: (uintptr_t)__builtin_return_address(0), false, false)
1.2 ad 80: #define MUTEX_LOCKED(mtx) \
1.42 ad 81: LOCKDEBUG_LOCKED(MUTEX_DEBUG_P(mtx), (mtx), NULL, \
1.2 ad 82: (uintptr_t)__builtin_return_address(0), 0)
83: #define MUTEX_UNLOCKED(mtx) \
1.23 yamt 84: LOCKDEBUG_UNLOCKED(MUTEX_DEBUG_P(mtx), (mtx), \
1.2 ad 85: (uintptr_t)__builtin_return_address(0), 0)
86: #define MUTEX_ABORT(mtx, msg) \
1.17 ad 87: mutex_abort(mtx, __func__, msg)
1.2 ad 88:
89: #if defined(LOCKDEBUG)
90:
91: #define MUTEX_DASSERT(mtx, cond) \
92: do { \
93: if (!(cond)) \
94: MUTEX_ABORT(mtx, "assertion failed: " #cond); \
95: } while (/* CONSTCOND */ 0);
96:
97: #else /* LOCKDEBUG */
98:
99: #define MUTEX_DASSERT(mtx, cond) /* nothing */
100:
101: #endif /* LOCKDEBUG */
102:
103: #if defined(DIAGNOSTIC)
104:
105: #define MUTEX_ASSERT(mtx, cond) \
106: do { \
107: if (!(cond)) \
108: MUTEX_ABORT(mtx, "assertion failed: " #cond); \
109: } while (/* CONSTCOND */ 0)
110:
111: #else /* DIAGNOSTIC */
112:
113: #define MUTEX_ASSERT(mtx, cond) /* nothing */
114:
115: #endif /* DIAGNOSTIC */
116:
117: /*
118: * Spin mutex SPL save / restore.
119: */
120:
121: #define MUTEX_SPIN_SPLRAISE(mtx) \
122: do { \
1.36 ad 123: struct cpu_info *x__ci; \
1.2 ad 124: int x__cnt, s; \
1.36 ad 125: s = splraiseipl(mtx->mtx_ipl); \
126: x__ci = curcpu(); \
1.2 ad 127: x__cnt = x__ci->ci_mtx_count--; \
1.37 ad 128: __insn_barrier(); \
1.51 ! rmind 129: if (x__cnt == 0) \
1.2 ad 130: x__ci->ci_mtx_oldspl = (s); \
131: } while (/* CONSTCOND */ 0)
132:
133: #define MUTEX_SPIN_SPLRESTORE(mtx) \
134: do { \
135: struct cpu_info *x__ci = curcpu(); \
136: int s = x__ci->ci_mtx_oldspl; \
137: __insn_barrier(); \
1.51 ! rmind 138: if (++(x__ci->ci_mtx_count) == 0) \
1.2 ad 139: splx(s); \
140: } while (/* CONSTCOND */ 0)
141:
142: /*
143: * For architectures that provide 'simple' mutexes: they provide a
144: * CAS function that is either MP-safe, or does not need to be MP
145: * safe. Adaptive mutexes on these architectures do not require an
146: * additional interlock.
147: */
148:
149: #ifdef __HAVE_SIMPLE_MUTEXES
150:
151: #define MUTEX_OWNER(owner) \
152: (owner & MUTEX_THREAD)
153: #define MUTEX_HAS_WAITERS(mtx) \
154: (((int)(mtx)->mtx_owner & MUTEX_BIT_WAITERS) != 0)
155:
1.23 yamt 156: #define MUTEX_INITIALIZE_ADAPTIVE(mtx, dodebug) \
1.49 skrll 157: if (!dodebug) \
158: (mtx)->mtx_owner |= MUTEX_BIT_NODEBUG; \
1.2 ad 159: do { \
160: } while (/* CONSTCOND */ 0);
161:
1.23 yamt 162: #define MUTEX_INITIALIZE_SPIN(mtx, dodebug, ipl) \
1.2 ad 163: do { \
164: (mtx)->mtx_owner = MUTEX_BIT_SPIN; \
1.49 skrll 165: if (!dodebug) \
166: (mtx)->mtx_owner |= MUTEX_BIT_NODEBUG; \
1.2 ad 167: (mtx)->mtx_ipl = makeiplcookie((ipl)); \
168: __cpu_simple_lock_init(&(mtx)->mtx_lock); \
169: } while (/* CONSTCOND */ 0)
170:
171: #define MUTEX_DESTROY(mtx) \
172: do { \
173: (mtx)->mtx_owner = MUTEX_THREAD; \
174: } while (/* CONSTCOND */ 0);
175:
176: #define MUTEX_SPIN_P(mtx) \
177: (((mtx)->mtx_owner & MUTEX_BIT_SPIN) != 0)
178: #define MUTEX_ADAPTIVE_P(mtx) \
179: (((mtx)->mtx_owner & MUTEX_BIT_SPIN) == 0)
180:
1.49 skrll 181: #define MUTEX_DEBUG_P(mtx) (((mtx)->mtx_owner & MUTEX_BIT_NODEBUG) == 0)
1.23 yamt 182: #if defined(LOCKDEBUG)
1.49 skrll 183: #define MUTEX_OWNED(owner) (((owner) & ~MUTEX_BIT_NODEBUG) != 0)
184: #define MUTEX_INHERITDEBUG(new, old) (new) |= (old) & MUTEX_BIT_NODEBUG
1.23 yamt 185: #else /* defined(LOCKDEBUG) */
186: #define MUTEX_OWNED(owner) ((owner) != 0)
187: #define MUTEX_INHERITDEBUG(new, old) /* nothing */
188: #endif /* defined(LOCKDEBUG) */
1.2 ad 189:
190: static inline int
191: MUTEX_ACQUIRE(kmutex_t *mtx, uintptr_t curthread)
192: {
193: int rv;
1.23 yamt 194: uintptr_t old = 0;
195: uintptr_t new = curthread;
196:
197: MUTEX_INHERITDEBUG(old, mtx->mtx_owner);
198: MUTEX_INHERITDEBUG(new, old);
199: rv = MUTEX_CAS(&mtx->mtx_owner, old, new);
1.7 itohy 200: MUTEX_RECEIVE(mtx);
1.2 ad 201: return rv;
202: }
203:
204: static inline int
205: MUTEX_SET_WAITERS(kmutex_t *mtx, uintptr_t owner)
206: {
207: int rv;
208: rv = MUTEX_CAS(&mtx->mtx_owner, owner, owner | MUTEX_BIT_WAITERS);
1.7 itohy 209: MUTEX_RECEIVE(mtx);
1.2 ad 210: return rv;
211: }
212:
213: static inline void
214: MUTEX_RELEASE(kmutex_t *mtx)
215: {
1.23 yamt 216: uintptr_t new;
217:
1.7 itohy 218: MUTEX_GIVE(mtx);
1.23 yamt 219: new = 0;
220: MUTEX_INHERITDEBUG(new, mtx->mtx_owner);
221: mtx->mtx_owner = new;
1.2 ad 222: }
1.4 ad 223:
224: static inline void
225: MUTEX_CLEAR_WAITERS(kmutex_t *mtx)
226: {
227: /* nothing */
228: }
1.2 ad 229: #endif /* __HAVE_SIMPLE_MUTEXES */
230:
231: /*
232: * Patch in stubs via strong alias where they are not available.
233: */
234:
235: #if defined(LOCKDEBUG)
236: #undef __HAVE_MUTEX_STUBS
237: #undef __HAVE_SPIN_MUTEX_STUBS
238: #endif
239:
240: #ifndef __HAVE_MUTEX_STUBS
1.8 itohy 241: __strong_alias(mutex_enter,mutex_vector_enter);
242: __strong_alias(mutex_exit,mutex_vector_exit);
1.2 ad 243: #endif
244:
245: #ifndef __HAVE_SPIN_MUTEX_STUBS
1.8 itohy 246: __strong_alias(mutex_spin_enter,mutex_vector_enter);
247: __strong_alias(mutex_spin_exit,mutex_vector_exit);
1.2 ad 248: #endif
249:
1.50 rmind 250: static void mutex_abort(kmutex_t *, const char *, const char *);
251: static void mutex_dump(volatile void *);
1.2 ad 252:
253: lockops_t mutex_spin_lockops = {
254: "Mutex",
1.42 ad 255: LOCKOPS_SPIN,
1.2 ad 256: mutex_dump
257: };
258:
259: lockops_t mutex_adaptive_lockops = {
260: "Mutex",
1.42 ad 261: LOCKOPS_SLEEP,
1.2 ad 262: mutex_dump
263: };
264:
1.5 yamt 265: syncobj_t mutex_syncobj = {
266: SOBJ_SLEEPQ_SORTED,
267: turnstile_unsleep,
268: turnstile_changepri,
269: sleepq_lendpri,
1.27 ad 270: (void *)mutex_owner,
1.5 yamt 271: };
272:
1.2 ad 273: /*
274: * mutex_dump:
275: *
276: * Dump the contents of a mutex structure.
277: */
278: void
279: mutex_dump(volatile void *cookie)
280: {
281: volatile kmutex_t *mtx = cookie;
282:
283: printf_nolog("owner field : %#018lx wait/spin: %16d/%d\n",
284: (long)MUTEX_OWNER(mtx->mtx_owner), MUTEX_HAS_WAITERS(mtx),
285: MUTEX_SPIN_P(mtx));
286: }
287:
288: /*
289: * mutex_abort:
290: *
1.3 ad 291: * Dump information about an error and panic the system. This
292: * generates a lot of machine code in the DIAGNOSTIC case, so
293: * we ask the compiler to not inline it.
1.2 ad 294: */
1.43 ad 295: void __noinline
1.2 ad 296: mutex_abort(kmutex_t *mtx, const char *func, const char *msg)
297: {
298:
1.23 yamt 299: LOCKDEBUG_ABORT(mtx, (MUTEX_SPIN_P(mtx) ?
1.3 ad 300: &mutex_spin_lockops : &mutex_adaptive_lockops), func, msg);
1.2 ad 301: }
302:
303: /*
304: * mutex_init:
305: *
306: * Initialize a mutex for use. Note that adaptive mutexes are in
307: * essence spin mutexes that can sleep to avoid deadlock and wasting
308: * CPU time. We can't easily provide a type of mutex that always
309: * sleeps - see comments in mutex_vector_enter() about releasing
310: * mutexes unlocked.
311: */
312: void
313: mutex_init(kmutex_t *mtx, kmutex_type_t type, int ipl)
314: {
1.23 yamt 315: bool dodebug;
1.2 ad 316:
317: memset(mtx, 0, sizeof(*mtx));
318:
1.15 ad 319: switch (type) {
320: case MUTEX_ADAPTIVE:
321: KASSERT(ipl == IPL_NONE);
322: break;
1.22 ad 323: case MUTEX_DEFAULT:
1.15 ad 324: case MUTEX_DRIVER:
1.26 ad 325: if (ipl == IPL_NONE || ipl == IPL_SOFTCLOCK ||
326: ipl == IPL_SOFTBIO || ipl == IPL_SOFTNET ||
327: ipl == IPL_SOFTSERIAL) {
1.22 ad 328: type = MUTEX_ADAPTIVE;
1.26 ad 329: } else {
1.22 ad 330: type = MUTEX_SPIN;
331: }
1.15 ad 332: break;
333: default:
334: break;
335: }
1.2 ad 336:
337: switch (type) {
1.11 ad 338: case MUTEX_NODEBUG:
1.23 yamt 339: dodebug = LOCKDEBUG_ALLOC(mtx, NULL,
1.19 ad 340: (uintptr_t)__builtin_return_address(0));
1.23 yamt 341: MUTEX_INITIALIZE_SPIN(mtx, dodebug, ipl);
1.11 ad 342: break;
1.2 ad 343: case MUTEX_ADAPTIVE:
1.23 yamt 344: dodebug = LOCKDEBUG_ALLOC(mtx, &mutex_adaptive_lockops,
1.19 ad 345: (uintptr_t)__builtin_return_address(0));
1.23 yamt 346: MUTEX_INITIALIZE_ADAPTIVE(mtx, dodebug);
1.2 ad 347: break;
348: case MUTEX_SPIN:
1.23 yamt 349: dodebug = LOCKDEBUG_ALLOC(mtx, &mutex_spin_lockops,
1.19 ad 350: (uintptr_t)__builtin_return_address(0));
1.23 yamt 351: MUTEX_INITIALIZE_SPIN(mtx, dodebug, ipl);
1.2 ad 352: break;
353: default:
354: panic("mutex_init: impossible type");
355: break;
356: }
357: }
358:
359: /*
360: * mutex_destroy:
361: *
362: * Tear down a mutex.
363: */
364: void
365: mutex_destroy(kmutex_t *mtx)
366: {
367:
368: if (MUTEX_ADAPTIVE_P(mtx)) {
369: MUTEX_ASSERT(mtx, !MUTEX_OWNED(mtx->mtx_owner) &&
370: !MUTEX_HAS_WAITERS(mtx));
371: } else {
1.16 skrll 372: MUTEX_ASSERT(mtx, !__SIMPLELOCK_LOCKED_P(&mtx->mtx_lock));
1.2 ad 373: }
374:
1.23 yamt 375: LOCKDEBUG_FREE(MUTEX_DEBUG_P(mtx), mtx);
1.2 ad 376: MUTEX_DESTROY(mtx);
377: }
378:
1.50 rmind 379: #ifdef MULTIPROCESSOR
1.2 ad 380: /*
1.50 rmind 381: * mutex_oncpu:
1.2 ad 382: *
383: * Return true if an adaptive mutex owner is running on a CPU in the
384: * system. If the target is waiting on the kernel big lock, then we
1.15 ad 385: * must release it. This is necessary to avoid deadlock.
1.2 ad 386: */
1.50 rmind 387: static bool
388: mutex_oncpu(uintptr_t owner)
1.2 ad 389: {
390: struct cpu_info *ci;
1.50 rmind 391: lwp_t *l;
1.2 ad 392:
1.50 rmind 393: KASSERT(kpreempt_disabled());
394:
395: if (!MUTEX_OWNED(owner)) {
396: return false;
397: }
1.2 ad 398:
1.50 rmind 399: /*
400: * See lwp_dtor() why dereference of the LWP pointer is safe.
401: * We must have kernel preemption disabled for that.
402: */
403: l = (lwp_t *)MUTEX_OWNER(owner);
404: ci = l->l_cpu;
1.2 ad 405:
1.50 rmind 406: if (ci && ci->ci_curlwp == l) {
407: /* Target is running; do we need to block? */
408: return (ci->ci_biglock_wanted != l);
409: }
1.15 ad 410:
1.50 rmind 411: /* Not running. It may be safe to block now. */
412: return false;
1.2 ad 413: }
1.15 ad 414: #endif /* MULTIPROCESSOR */
1.2 ad 415:
416: /*
417: * mutex_vector_enter:
418: *
1.45 rmind 419: * Support routine for mutex_enter() that must handle all cases. In
1.2 ad 420: * the LOCKDEBUG case, mutex_enter() is always aliased here, even if
421: * fast-path stubs are available. If an mutex_spin_enter() stub is
422: * not available, then it is also aliased directly here.
423: */
424: void
425: mutex_vector_enter(kmutex_t *mtx)
426: {
427: uintptr_t owner, curthread;
428: turnstile_t *ts;
429: #ifdef MULTIPROCESSOR
430: u_int count;
431: #endif
1.44 wrstuden 432: #ifdef KERN_SA
433: int f;
434: #endif
1.2 ad 435: LOCKSTAT_COUNTER(spincnt);
436: LOCKSTAT_COUNTER(slpcnt);
437: LOCKSTAT_TIMER(spintime);
438: LOCKSTAT_TIMER(slptime);
439: LOCKSTAT_FLAG(lsflag);
440:
441: /*
442: * Handle spin mutexes.
443: */
444: if (MUTEX_SPIN_P(mtx)) {
445: #if defined(LOCKDEBUG) && defined(MULTIPROCESSOR)
446: u_int spins = 0;
447: #endif
448: MUTEX_SPIN_SPLRAISE(mtx);
449: MUTEX_WANTLOCK(mtx);
450: #ifdef FULL
451: if (__cpu_simple_lock_try(&mtx->mtx_lock)) {
452: MUTEX_LOCKED(mtx);
453: return;
454: }
455: #if !defined(MULTIPROCESSOR)
456: MUTEX_ABORT(mtx, "locking against myself");
457: #else /* !MULTIPROCESSOR */
458:
459: LOCKSTAT_ENTER(lsflag);
460: LOCKSTAT_START_TIMER(lsflag, spintime);
461: count = SPINLOCK_BACKOFF_MIN;
462:
463: /*
464: * Spin testing the lock word and do exponential backoff
465: * to reduce cache line ping-ponging between CPUs.
466: */
467: do {
468: if (panicstr != NULL)
469: break;
1.16 skrll 470: while (__SIMPLELOCK_LOCKED_P(&mtx->mtx_lock)) {
1.2 ad 471: SPINLOCK_BACKOFF(count);
472: #ifdef LOCKDEBUG
473: if (SPINLOCK_SPINOUT(spins))
474: MUTEX_ABORT(mtx, "spinout");
475: #endif /* LOCKDEBUG */
476: }
477: } while (!__cpu_simple_lock_try(&mtx->mtx_lock));
478:
479: if (count != SPINLOCK_BACKOFF_MIN) {
480: LOCKSTAT_STOP_TIMER(lsflag, spintime);
481: LOCKSTAT_EVENT(lsflag, mtx,
482: LB_SPIN_MUTEX | LB_SPIN, 1, spintime);
483: }
484: LOCKSTAT_EXIT(lsflag);
485: #endif /* !MULTIPROCESSOR */
486: #endif /* FULL */
487: MUTEX_LOCKED(mtx);
488: return;
489: }
490:
491: curthread = (uintptr_t)curlwp;
492:
493: MUTEX_DASSERT(mtx, MUTEX_ADAPTIVE_P(mtx));
494: MUTEX_ASSERT(mtx, curthread != 0);
495: MUTEX_WANTLOCK(mtx);
496:
497: if (panicstr == NULL) {
498: LOCKDEBUG_BARRIER(&kernel_lock, 1);
499: }
500:
501: LOCKSTAT_ENTER(lsflag);
502:
503: /*
504: * Adaptive mutex; spin trying to acquire the mutex. If we
505: * determine that the owner is not running on a processor,
506: * then we stop spinning, and sleep instead.
507: */
1.50 rmind 508: KPREEMPT_DISABLE(curlwp);
1.34 ad 509: for (owner = mtx->mtx_owner;;) {
1.2 ad 510: if (!MUTEX_OWNED(owner)) {
511: /*
512: * Mutex owner clear could mean two things:
513: *
514: * * The mutex has been released.
515: * * The owner field hasn't been set yet.
516: *
517: * Try to acquire it again. If that fails,
518: * we'll just loop again.
519: */
520: if (MUTEX_ACQUIRE(mtx, curthread))
521: break;
1.34 ad 522: owner = mtx->mtx_owner;
1.2 ad 523: continue;
524: }
1.50 rmind 525: if (__predict_false(panicstr != NULL)) {
526: kpreempt_enable();
1.2 ad 527: return;
1.50 rmind 528: }
529: if (__predict_false(MUTEX_OWNER(owner) == curthread)) {
1.2 ad 530: MUTEX_ABORT(mtx, "locking against myself");
1.50 rmind 531: }
1.2 ad 532: #ifdef MULTIPROCESSOR
533: /*
534: * Check to see if the owner is running on a processor.
535: * If so, then we should just spin, as the owner will
536: * likely release the lock very soon.
537: */
1.50 rmind 538: if (mutex_oncpu(owner)) {
1.2 ad 539: LOCKSTAT_START_TIMER(lsflag, spintime);
540: count = SPINLOCK_BACKOFF_MIN;
1.50 rmind 541: do {
542: kpreempt_enable();
1.34 ad 543: SPINLOCK_BACKOFF(count);
1.50 rmind 544: kpreempt_disable();
1.2 ad 545: owner = mtx->mtx_owner;
1.50 rmind 546: } while (mutex_oncpu(owner));
1.2 ad 547: LOCKSTAT_STOP_TIMER(lsflag, spintime);
548: LOCKSTAT_COUNT(spincnt, 1);
549: if (!MUTEX_OWNED(owner))
550: continue;
551: }
552: #endif
553:
554: ts = turnstile_lookup(mtx);
555:
556: /*
557: * Once we have the turnstile chain interlock, mark the
558: * mutex has having waiters. If that fails, spin again:
559: * chances are that the mutex has been released.
560: */
561: if (!MUTEX_SET_WAITERS(mtx, owner)) {
562: turnstile_exit(mtx);
1.34 ad 563: owner = mtx->mtx_owner;
1.2 ad 564: continue;
565: }
566:
567: #ifdef MULTIPROCESSOR
568: /*
569: * mutex_exit() is permitted to release the mutex without
570: * any interlocking instructions, and the following can
571: * occur as a result:
572: *
573: * CPU 1: MUTEX_SET_WAITERS() CPU2: mutex_exit()
574: * ---------------------------- ----------------------------
575: * .. acquire cache line
576: * .. test for waiters
577: * acquire cache line <- lose cache line
578: * lock cache line ..
579: * verify mutex is held ..
580: * set waiters ..
581: * unlock cache line ..
582: * lose cache line -> acquire cache line
583: * .. clear lock word, waiters
584: * return success
585: *
1.50 rmind 586: * There is another race that can occur: a third CPU could
1.2 ad 587: * acquire the mutex as soon as it is released. Since
588: * adaptive mutexes are primarily spin mutexes, this is not
589: * something that we need to worry about too much. What we
590: * do need to ensure is that the waiters bit gets set.
591: *
592: * To allow the unlocked release, we need to make some
593: * assumptions here:
594: *
595: * o Release is the only non-atomic/unlocked operation
596: * that can be performed on the mutex. (It must still
597: * be atomic on the local CPU, e.g. in case interrupted
598: * or preempted).
599: *
600: * o At any given time, MUTEX_SET_WAITERS() can only ever
1.21 pooka 601: * be in progress on one CPU in the system - guaranteed
1.2 ad 602: * by the turnstile chain lock.
603: *
604: * o No other operations other than MUTEX_SET_WAITERS()
605: * and release can modify a mutex with a non-zero
606: * owner field.
607: *
608: * o The result of a successful MUTEX_SET_WAITERS() call
609: * is an unbuffered write that is immediately visible
610: * to all other processors in the system.
611: *
612: * o If the holding LWP switches away, it posts a store
613: * fence before changing curlwp, ensuring that any
614: * overwrite of the mutex waiters flag by mutex_exit()
615: * completes before the modification of curlwp becomes
616: * visible to this CPU.
617: *
1.14 yamt 618: * o mi_switch() posts a store fence before setting curlwp
1.2 ad 619: * and before resuming execution of an LWP.
620: *
621: * o _kernel_lock() posts a store fence before setting
622: * curcpu()->ci_biglock_wanted, and after clearing it.
623: * This ensures that any overwrite of the mutex waiters
624: * flag by mutex_exit() completes before the modification
625: * of ci_biglock_wanted becomes visible.
626: *
627: * We now post a read memory barrier (after setting the
628: * waiters field) and check the lock holder's status again.
629: * Some of the possible outcomes (not an exhaustive list):
630: *
1.50 rmind 631: * 1. The on-CPU check returns true: the holding LWP is
1.2 ad 632: * running again. The lock may be released soon and
633: * we should spin. Importantly, we can't trust the
634: * value of the waiters flag.
635: *
1.50 rmind 636: * 2. The on-CPU check returns false: the holding LWP is
1.39 yamt 637: * not running. We now have the opportunity to check
1.2 ad 638: * if mutex_exit() has blatted the modifications made
639: * by MUTEX_SET_WAITERS().
640: *
1.50 rmind 641: * 3. The on-CPU check returns false: the holding LWP may
1.2 ad 642: * or may not be running. It has context switched at
643: * some point during our check. Again, we have the
644: * chance to see if the waiters bit is still set or
645: * has been overwritten.
646: *
1.50 rmind 647: * 4. The on-CPU check returns false: the holding LWP is
1.2 ad 648: * running on a CPU, but wants the big lock. It's OK
649: * to check the waiters field in this case.
650: *
651: * 5. The has-waiters check fails: the mutex has been
652: * released, the waiters flag cleared and another LWP
653: * now owns the mutex.
654: *
655: * 6. The has-waiters check fails: the mutex has been
656: * released.
657: *
658: * If the waiters bit is not set it's unsafe to go asleep,
659: * as we might never be awoken.
660: */
1.50 rmind 661: if ((membar_consumer(), mutex_oncpu(owner)) ||
1.24 ad 662: (membar_consumer(), !MUTEX_HAS_WAITERS(mtx))) {
1.2 ad 663: turnstile_exit(mtx);
1.34 ad 664: owner = mtx->mtx_owner;
1.2 ad 665: continue;
666: }
667: #endif /* MULTIPROCESSOR */
668:
1.44 wrstuden 669: #ifdef KERN_SA
670: /*
671: * Sleeping for a mutex should not generate an upcall.
672: * So set LP_SA_NOBLOCK to indicate this.
673: * f indicates if we should clear LP_SA_NOBLOCK when done.
674: */
675: f = ~curlwp->l_pflag & LP_SA_NOBLOCK;
676: curlwp->l_pflag |= LP_SA_NOBLOCK;
677: #endif /* KERN_SA */
678:
1.2 ad 679: LOCKSTAT_START_TIMER(lsflag, slptime);
680:
1.5 yamt 681: turnstile_block(ts, TS_WRITER_Q, mtx, &mutex_syncobj);
1.2 ad 682:
683: LOCKSTAT_STOP_TIMER(lsflag, slptime);
684: LOCKSTAT_COUNT(slpcnt, 1);
1.34 ad 685:
1.44 wrstuden 686: #ifdef KERN_SA
687: curlwp->l_pflag ^= f;
688: #endif /* KERN_SA */
689:
1.34 ad 690: owner = mtx->mtx_owner;
1.2 ad 691: }
1.50 rmind 692: KPREEMPT_ENABLE(curlwp);
1.2 ad 693:
694: LOCKSTAT_EVENT(lsflag, mtx, LB_ADAPTIVE_MUTEX | LB_SLEEP1,
695: slpcnt, slptime);
696: LOCKSTAT_EVENT(lsflag, mtx, LB_ADAPTIVE_MUTEX | LB_SPIN,
697: spincnt, spintime);
698: LOCKSTAT_EXIT(lsflag);
699:
700: MUTEX_DASSERT(mtx, MUTEX_OWNER(mtx->mtx_owner) == curthread);
701: MUTEX_LOCKED(mtx);
702: }
703:
704: /*
705: * mutex_vector_exit:
706: *
707: * Support routine for mutex_exit() that handles all cases.
708: */
709: void
710: mutex_vector_exit(kmutex_t *mtx)
711: {
712: turnstile_t *ts;
713: uintptr_t curthread;
714:
715: if (MUTEX_SPIN_P(mtx)) {
716: #ifdef FULL
1.33 ad 717: if (__predict_false(!__SIMPLELOCK_LOCKED_P(&mtx->mtx_lock))) {
718: if (panicstr != NULL)
719: return;
1.2 ad 720: MUTEX_ABORT(mtx, "exiting unheld spin mutex");
1.33 ad 721: }
1.2 ad 722: MUTEX_UNLOCKED(mtx);
723: __cpu_simple_unlock(&mtx->mtx_lock);
724: #endif
725: MUTEX_SPIN_SPLRESTORE(mtx);
726: return;
727: }
728:
1.11 ad 729: if (__predict_false((uintptr_t)panicstr | cold)) {
1.2 ad 730: MUTEX_UNLOCKED(mtx);
731: MUTEX_RELEASE(mtx);
732: return;
733: }
734:
735: curthread = (uintptr_t)curlwp;
736: MUTEX_DASSERT(mtx, curthread != 0);
737: MUTEX_ASSERT(mtx, MUTEX_OWNER(mtx->mtx_owner) == curthread);
738: MUTEX_UNLOCKED(mtx);
739:
1.15 ad 740: #ifdef LOCKDEBUG
741: /*
742: * Avoid having to take the turnstile chain lock every time
743: * around. Raise the priority level to splhigh() in order
744: * to disable preemption and so make the following atomic.
745: */
746: {
747: int s = splhigh();
748: if (!MUTEX_HAS_WAITERS(mtx)) {
749: MUTEX_RELEASE(mtx);
750: splx(s);
751: return;
752: }
753: splx(s);
754: }
755: #endif
756:
1.2 ad 757: /*
758: * Get this lock's turnstile. This gets the interlock on
759: * the sleep queue. Once we have that, we can clear the
760: * lock. If there was no turnstile for the lock, there
761: * were no waiters remaining.
762: */
763: ts = turnstile_lookup(mtx);
764:
765: if (ts == NULL) {
766: MUTEX_RELEASE(mtx);
767: turnstile_exit(mtx);
768: } else {
769: MUTEX_RELEASE(mtx);
770: turnstile_wakeup(ts, TS_WRITER_Q,
771: TS_WAITERS(ts, TS_WRITER_Q), NULL);
772: }
773: }
774:
1.4 ad 775: #ifndef __HAVE_SIMPLE_MUTEXES
776: /*
777: * mutex_wakeup:
778: *
779: * Support routine for mutex_exit() that wakes up all waiters.
780: * We assume that the mutex has been released, but it need not
781: * be.
782: */
783: void
784: mutex_wakeup(kmutex_t *mtx)
785: {
786: turnstile_t *ts;
787:
788: ts = turnstile_lookup(mtx);
789: if (ts == NULL) {
790: turnstile_exit(mtx);
791: return;
792: }
793: MUTEX_CLEAR_WAITERS(mtx);
794: turnstile_wakeup(ts, TS_WRITER_Q, TS_WAITERS(ts, TS_WRITER_Q), NULL);
795: }
796: #endif /* !__HAVE_SIMPLE_MUTEXES */
797:
1.2 ad 798: /*
799: * mutex_owned:
800: *
1.3 ad 801: * Return true if the current LWP (adaptive) or CPU (spin)
802: * holds the mutex.
1.2 ad 803: */
804: int
805: mutex_owned(kmutex_t *mtx)
806: {
807:
1.35 ad 808: if (mtx == NULL)
809: return 0;
1.2 ad 810: if (MUTEX_ADAPTIVE_P(mtx))
811: return MUTEX_OWNER(mtx->mtx_owner) == (uintptr_t)curlwp;
812: #ifdef FULL
1.16 skrll 813: return __SIMPLELOCK_LOCKED_P(&mtx->mtx_lock);
1.2 ad 814: #else
815: return 1;
816: #endif
817: }
818:
819: /*
820: * mutex_owner:
821: *
1.6 ad 822: * Return the current owner of an adaptive mutex. Used for
823: * priority inheritance.
1.2 ad 824: */
1.27 ad 825: lwp_t *
826: mutex_owner(kmutex_t *mtx)
1.2 ad 827: {
828:
829: MUTEX_ASSERT(mtx, MUTEX_ADAPTIVE_P(mtx));
830: return (struct lwp *)MUTEX_OWNER(mtx->mtx_owner);
831: }
832:
833: /*
834: * mutex_tryenter:
835: *
836: * Try to acquire the mutex; return non-zero if we did.
837: */
838: int
839: mutex_tryenter(kmutex_t *mtx)
840: {
841: uintptr_t curthread;
842:
843: /*
844: * Handle spin mutexes.
845: */
846: if (MUTEX_SPIN_P(mtx)) {
847: MUTEX_SPIN_SPLRAISE(mtx);
848: #ifdef FULL
849: if (__cpu_simple_lock_try(&mtx->mtx_lock)) {
1.4 ad 850: MUTEX_WANTLOCK(mtx);
1.2 ad 851: MUTEX_LOCKED(mtx);
852: return 1;
853: }
854: MUTEX_SPIN_SPLRESTORE(mtx);
855: #else
1.4 ad 856: MUTEX_WANTLOCK(mtx);
1.2 ad 857: MUTEX_LOCKED(mtx);
858: return 1;
859: #endif
860: } else {
861: curthread = (uintptr_t)curlwp;
862: MUTEX_ASSERT(mtx, curthread != 0);
863: if (MUTEX_ACQUIRE(mtx, curthread)) {
1.4 ad 864: MUTEX_WANTLOCK(mtx);
1.2 ad 865: MUTEX_LOCKED(mtx);
866: MUTEX_DASSERT(mtx,
867: MUTEX_OWNER(mtx->mtx_owner) == curthread);
868: return 1;
869: }
870: }
871:
872: return 0;
873: }
874:
875: #if defined(__HAVE_SPIN_MUTEX_STUBS) || defined(FULL)
876: /*
877: * mutex_spin_retry:
878: *
879: * Support routine for mutex_spin_enter(). Assumes that the caller
880: * has already raised the SPL, and adjusted counters.
881: */
882: void
883: mutex_spin_retry(kmutex_t *mtx)
884: {
885: #ifdef MULTIPROCESSOR
886: u_int count;
887: LOCKSTAT_TIMER(spintime);
888: LOCKSTAT_FLAG(lsflag);
889: #ifdef LOCKDEBUG
890: u_int spins = 0;
891: #endif /* LOCKDEBUG */
892:
893: MUTEX_WANTLOCK(mtx);
894:
895: LOCKSTAT_ENTER(lsflag);
896: LOCKSTAT_START_TIMER(lsflag, spintime);
897: count = SPINLOCK_BACKOFF_MIN;
898:
899: /*
900: * Spin testing the lock word and do exponential backoff
901: * to reduce cache line ping-ponging between CPUs.
902: */
903: do {
904: if (panicstr != NULL)
905: break;
1.16 skrll 906: while (__SIMPLELOCK_LOCKED_P(&mtx->mtx_lock)) {
1.2 ad 907: SPINLOCK_BACKOFF(count);
908: #ifdef LOCKDEBUG
909: if (SPINLOCK_SPINOUT(spins))
910: MUTEX_ABORT(mtx, "spinout");
911: #endif /* LOCKDEBUG */
912: }
913: } while (!__cpu_simple_lock_try(&mtx->mtx_lock));
914:
915: LOCKSTAT_STOP_TIMER(lsflag, spintime);
916: LOCKSTAT_EVENT(lsflag, mtx, LB_SPIN_MUTEX | LB_SPIN, 1, spintime);
917: LOCKSTAT_EXIT(lsflag);
918:
919: MUTEX_LOCKED(mtx);
920: #else /* MULTIPROCESSOR */
921: MUTEX_ABORT(mtx, "locking against myself");
922: #endif /* MULTIPROCESSOR */
923: }
924: #endif /* defined(__HAVE_SPIN_MUTEX_STUBS) || defined(FULL) */
CVSweb <webmaster@jp.NetBSD.org>
![[BACK]](/icons/back.gif){kind=icon}
Return to kern_mutex.c CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [cvs.NetBSD.org] / src / sys / kern