[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.34

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

CVSweb <webmaster@jp.NetBSD.org>