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