[BACK]Return to kern_mutex.c CVS log [TXT][DIR] Up to [cvs.NetBSD.org] / src / sys / kern

Annotation of src/sys/kern/kern_mutex.c, Revision 1.6

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

CVSweb <webmaster@jp.NetBSD.org>