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