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