Return to lock.c CVS log

Up to [GnuMach] / OSKit-Mach / kern

Annotation of OSKit-Mach/kern/lock.c, revision 1.1

1.1     ! root        1: /*
        !             2:  * Mach Operating System
        !             3:  * Copyright (c) 1991,1990,1989,1988,1987 Carnegie Mellon University.
        !             4:  * Copyright (c) 1993,1994 The University of Utah and
        !             5:  * the Computer Systems Laboratory (CSL).
        !             6:  * All rights reserved.
        !             7:  *
        !             8:  * Permission to use, copy, modify and distribute this software and its
        !             9:  * documentation is hereby granted, provided that both the copyright
        !            10:  * notice and this permission notice appear in all copies of the
        !            11:  * software, derivative works or modified versions, and any portions
        !            12:  * thereof, and that both notices appear in supporting documentation.
        !            13:  *
        !            14:  * CARNEGIE MELLON, THE UNIVERSITY OF UTAH AND CSL ALLOW FREE USE OF
        !            15:  * THIS SOFTWARE IN ITS "AS IS" CONDITION, AND DISCLAIM ANY LIABILITY
        !            16:  * OF ANY KIND FOR ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF
        !            17:  * THIS SOFTWARE.
        !            18:  *
        !            19:  * Carnegie Mellon requests users of this software to return to
        !            20:  *
        !            21:  *  Software Distribution Coordinator  or  [email protected]
        !            22:  *  School of Computer Science
        !            23:  *  Carnegie Mellon University
        !            24:  *  Pittsburgh PA 15213-3890
        !            25:  *
        !            26:  * any improvements or extensions that they make and grant Carnegie Mellon
        !            27:  * the rights to redistribute these changes.
        !            28:  */
        !            29: /*
        !            30:  *     File:   kern/lock.c
        !            31:  *     Author: Avadis Tevanian, Jr., Michael Wayne Young
        !            32:  *     Date:   1985
        !            33:  *
        !            34:  *     Locking primitives implementation
        !            35:  */
        !            36: 
        !            37: #include <cpus.h>
        !            38: #include <mach_kdb.h>
        !            39: 
        !            40: #include <kern/lock.h>
        !            41: #include <kern/thread.h>
        !            42: #include <kern/sched_prim.h>
        !            43: #if    MACH_KDB
        !            44: #include <machine/db_machdep.h>
        !            45: #include <ddb/db_sym.h>
        !            46: #endif
        !            47: 
        !            48: 
        !            49: #if    NCPUS > 1
        !            50: 
        !            51: /*
        !            52:  *     Module:         lock
        !            53:  *     Function:
        !            54:  *             Provide reader/writer sychronization.
        !            55:  *     Implementation:
        !            56:  *             Simple interlock on a bit.  Readers first interlock,
        !            57:  *             increment the reader count, then let go.  Writers hold
        !            58:  *             the interlock (thus preventing further readers), and
        !            59:  *             wait for already-accepted readers to go away.
        !            60:  */
        !            61: 
        !            62: /*
        !            63:  *     The simple-lock routines are the primitives out of which
        !            64:  *     the lock package is built.  The implementation is left
        !            65:  *     to the machine-dependent code.
        !            66:  */
        !            67: 
        !            68: #ifdef notdef
        !            69: /*
        !            70:  *     A sample implementation of simple locks.
        !            71:  *     assumes:
        !            72:  *             boolean_t test_and_set(boolean_t *)
        !            73:  *                     indivisibly sets the boolean to TRUE
        !            74:  *                     and returns its old value
        !            75:  *             and that setting a boolean to FALSE is indivisible.
        !            76:  */
        !            77: /*
        !            78:  *     simple_lock_init initializes a simple lock.  A simple lock
        !            79:  *     may only be used for exclusive locks.
        !            80:  */
        !            81: 
        !            82: void simple_lock_init(simple_lock_t l)
        !            83: {
        !            84:        *(boolean_t *)l = FALSE;
        !            85: }
        !            86: 
        !            87: void simple_lock(simple_lock_t l)
        !            88: {
        !            89:        while (test_and_set((boolean_t *)l))
        !            90:                continue;
        !            91: }
        !            92: 
        !            93: void simple_unlock(simple_lock_t l)
        !            94: {
        !            95:        *(boolean_t *)l = FALSE;
        !            96: }
        !            97: 
        !            98: boolean_t simple_lock_try(simple_lock_t l)
        !            99: {
        !           100:        return (!test_and_set((boolean_t *)l));
        !           101: }
        !           102: #endif /* notdef */
        !           103: #endif /* NCPUS > 1 */
        !           104: 
        !           105: #if    NCPUS > 1
        !           106: int lock_wait_time = 100;
        !           107: #else  /* NCPUS > 1 */
        !           108: 
        !           109:        /*
        !           110:         *      It is silly to spin on a uni-processor as if we
        !           111:         *      thought something magical would happen to the
        !           112:         *      want_write bit while we are executing.
        !           113:         */
        !           114: int lock_wait_time = 0;
        !           115: #endif /* NCPUS > 1 */
        !           116: 
        !           117: #if    MACH_SLOCKS && NCPUS == 1
        !           118: /*
        !           119:  *     This code does not protect simple_locks_taken and simple_locks_info.
        !           120:  *     It works despite the fact that interrupt code does use simple locks.
        !           121:  *     This is because interrupts use locks in a stack-like manner.
        !           122:  *     Each interrupt releases all the locks it acquires, so the data
        !           123:  *     structures end up in the same state after the interrupt as before.
        !           124:  *     The only precaution necessary is that simple_locks_taken be
        !           125:  *     incremented first and decremented last, so that interrupt handlers
        !           126:  *     don't over-write active slots in simple_locks_info.
        !           127:  */
        !           128: 
        !           129: unsigned int simple_locks_taken = 0;
        !           130: 
        !           131: #define        NSLINFO 1000            /* maximum number of locks held */
        !           132: 
        !           133: struct simple_locks_info {
        !           134:        simple_lock_t l;
        !           135:        unsigned int ra;
        !           136: } simple_locks_info[NSLINFO];
        !           137: 
        !           138: void check_simple_locks(void)
        !           139: {
        !           140:        assert(simple_locks_taken == 0);
        !           141: }
        !           142: 
        !           143: /* Need simple lock sanity checking code if simple locks are being
        !           144:    compiled in, and we are compiling for a uniprocessor. */
        !           145: 
        !           146: void simple_lock_init(
        !           147:        simple_lock_t l)
        !           148: {
        !           149:        l->lock_data = 0;
        !           150: }
        !           151: 
        !           152: void simple_lock(
        !           153:        simple_lock_t l)
        !           154: {
        !           155:        struct simple_locks_info *info;
        !           156: 
        !           157:        assert(l->lock_data == 0);
        !           158: 
        !           159:        l->lock_data = 1;
        !           160: 
        !           161:        info = &simple_locks_info[simple_locks_taken++];
        !           162:        info->l = l;
        !           163:        /* XXX we want our return address, if possible */
        !           164: #ifdef i386
        !           165:        info->ra = *((unsigned int *)&l - 1);
        !           166: #endif /* i386 */
        !           167: }
        !           168: 
        !           169: boolean_t simple_lock_try(
        !           170:        simple_lock_t l)
        !           171: {
        !           172:        struct simple_locks_info *info;
        !           173: 
        !           174:        if (l->lock_data != 0)
        !           175:                return FALSE;
        !           176: 
        !           177:        l->lock_data = 1;
        !           178: 
        !           179:        info = &simple_locks_info[simple_locks_taken++];
        !           180:        info->l = l;
        !           181:        /* XXX we want our return address, if possible */
        !           182: #ifdef i386
        !           183:        info->ra = *((unsigned int *)&l - 1);
        !           184: #endif /* i386 */
        !           185: 
        !           186:        return TRUE;
        !           187: }
        !           188: 
        !           189: void simple_unlock(
        !           190:        simple_lock_t l)
        !           191: {
        !           192:        assert(l->lock_data != 0);
        !           193: 
        !           194:        l->lock_data = 0;
        !           195: 
        !           196:        if (simple_locks_info[simple_locks_taken-1].l != l) {
        !           197:                unsigned int i = simple_locks_taken;
        !           198: 
        !           199:                /* out-of-order unlocking */
        !           200: 
        !           201:                do
        !           202:                        if (i == 0)
        !           203:                                panic("simple_unlock");
        !           204:                while (simple_locks_info[--i].l != l);
        !           205: 
        !           206:                simple_locks_info[i] = simple_locks_info[simple_locks_taken-1];
        !           207:        }
        !           208:        simple_locks_taken--;
        !           209: }
        !           210: 
        !           211: #endif /* MACH_SLOCKS && NCPUS == 1 */
        !           212: 
        !           213: /*
        !           214:  *     Routine:        lock_init
        !           215:  *     Function:
        !           216:  *             Initialize a lock; required before use.
        !           217:  *             Note that clients declare the "struct lock"
        !           218:  *             variables and then initialize them, rather
        !           219:  *             than getting a new one from this module.
        !           220:  */
        !           221: void lock_init(
        !           222:        lock_t          l,
        !           223:        boolean_t       can_sleep)
        !           224: {
        !           225:        bzero((char *)l, sizeof(lock_data_t));
        !           226:        simple_lock_init(&l->interlock);
        !           227:        l->want_write = FALSE;
        !           228:        l->want_upgrade = FALSE;
        !           229:        l->read_count = 0;
        !           230:        l->can_sleep = can_sleep;
        !           231:        l->thread = (struct thread *)-1;        /* XXX */
        !           232:        l->recursion_depth = 0;
        !           233: }
        !           234: 
        !           235: void lock_sleepable(
        !           236:        lock_t          l,
        !           237:        boolean_t       can_sleep)
        !           238: {
        !           239:        simple_lock(&l->interlock);
        !           240:        l->can_sleep = can_sleep;
        !           241:        simple_unlock(&l->interlock);
        !           242: }
        !           243: 
        !           244: 
        !           245: /*
        !           246:  *     Sleep locks.  These use the same data structure and algorithm
        !           247:  *     as the spin locks, but the process sleeps while it is waiting
        !           248:  *     for the lock.  These work on uniprocessor systems.
        !           249:  */
        !           250: 
        !           251: void lock_write(
        !           252:        register lock_t l)
        !           253: {
        !           254:        register int    i;
        !           255: 
        !           256:        check_simple_locks();
        !           257:        simple_lock(&l->interlock);
        !           258: 
        !           259:        if (l->thread == current_thread()) {
        !           260:                /*
        !           261:                 *      Recursive lock.
        !           262:                 */
        !           263:                l->recursion_depth++;
        !           264:                simple_unlock(&l->interlock);
        !           265:                return;
        !           266:        }
        !           267: 
        !           268:        /*
        !           269:         *      Try to acquire the want_write bit.
        !           270:         */
        !           271:        while (l->want_write) {
        !           272:                if ((i = lock_wait_time) > 0) {
        !           273:                        simple_unlock(&l->interlock);
        !           274:                        while (--i > 0 && l->want_write)
        !           275:                                continue;
        !           276:                        simple_lock(&l->interlock);
        !           277:                }
        !           278: 
        !           279:                if (l->can_sleep && l->want_write) {
        !           280:                        l->waiting = TRUE;
        !           281:                        thread_sleep(l,
        !           282:                                simple_lock_addr(l->interlock), FALSE);
        !           283:                        simple_lock(&l->interlock);
        !           284:                }
        !           285:        }
        !           286:        l->want_write = TRUE;
        !           287: 
        !           288:        /* Wait for readers (and upgrades) to finish */
        !           289: 
        !           290:        while ((l->read_count != 0) || l->want_upgrade) {
        !           291:                if ((i = lock_wait_time) > 0) {
        !           292:                        simple_unlock(&l->interlock);
        !           293:                        while (--i > 0 && (l->read_count != 0 ||
        !           294:                                        l->want_upgrade))
        !           295:                                continue;
        !           296:                        simple_lock(&l->interlock);
        !           297:                }
        !           298: 
        !           299:                if (l->can_sleep && (l->read_count != 0 || l->want_upgrade)) {
        !           300:                        l->waiting = TRUE;
        !           301:                        thread_sleep(l,
        !           302:                                simple_lock_addr(l->interlock), FALSE);
        !           303:                        simple_lock(&l->interlock);
        !           304:                }
        !           305:        }
        !           306:        simple_unlock(&l->interlock);
        !           307: }
        !           308: 
        !           309: void lock_done(
        !           310:        register lock_t l)
        !           311: {
        !           312:        simple_lock(&l->interlock);
        !           313: 
        !           314:        if (l->read_count != 0)
        !           315:                l->read_count--;
        !           316:        else
        !           317:        if (l->recursion_depth != 0)
        !           318:                l->recursion_depth--;
        !           319:        else
        !           320:        if (l->want_upgrade)
        !           321:                l->want_upgrade = FALSE;
        !           322:        else
        !           323:                l->want_write = FALSE;
        !           324: 
        !           325:        /*
        !           326:         *      There is no reason to wakeup a waiting thread
        !           327:         *      if the read-count is non-zero.  Consider:
        !           328:         *              we must be dropping a read lock
        !           329:         *              threads are waiting only if one wants a write lock
        !           330:         *              if there are still readers, they can't proceed
        !           331:         */
        !           332: 
        !           333:        if (l->waiting && (l->read_count == 0)) {
        !           334:                l->waiting = FALSE;
        !           335:                thread_wakeup(l);
        !           336:        }
        !           337: 
        !           338:        simple_unlock(&l->interlock);
        !           339: }
        !           340: 
        !           341: void lock_read(
        !           342:        register lock_t l)
        !           343: {
        !           344:        register int    i;
        !           345: 
        !           346:        check_simple_locks();
        !           347:        simple_lock(&l->interlock);
        !           348: 
        !           349:        if (l->thread == current_thread()) {
        !           350:                /*
        !           351:                 *      Recursive lock.
        !           352:                 */
        !           353:                l->read_count++;
        !           354:                simple_unlock(&l->interlock);
        !           355:                return;
        !           356:        }
        !           357: 
        !           358:        while (l->want_write || l->want_upgrade) {
        !           359:                if ((i = lock_wait_time) > 0) {
        !           360:                        simple_unlock(&l->interlock);
        !           361:                        while (--i > 0 && (l->want_write || l->want_upgrade))
        !           362:                                continue;
        !           363:                        simple_lock(&l->interlock);
        !           364:                }
        !           365: 
        !           366:                if (l->can_sleep && (l->want_write || l->want_upgrade)) {
        !           367:                        l->waiting = TRUE;
        !           368:                        thread_sleep(l,
        !           369:                                simple_lock_addr(l->interlock), FALSE);
        !           370:                        simple_lock(&l->interlock);
        !           371:                }
        !           372:        }
        !           373: 
        !           374:        l->read_count++;
        !           375:        simple_unlock(&l->interlock);
        !           376: }
        !           377: 
        !           378: /*
        !           379:  *     Routine:        lock_read_to_write
        !           380:  *     Function:
        !           381:  *             Improves a read-only lock to one with
        !           382:  *             write permission.  If another reader has
        !           383:  *             already requested an upgrade to a write lock,
        !           384:  *             no lock is held upon return.
        !           385:  *
        !           386:  *             Returns TRUE if the upgrade *failed*.
        !           387:  */
        !           388: boolean_t lock_read_to_write(
        !           389:        register lock_t l)
        !           390: {
        !           391:        register int    i;
        !           392: 
        !           393:        check_simple_locks();
        !           394:        simple_lock(&l->interlock);
        !           395: 
        !           396:        l->read_count--;
        !           397: 
        !           398:        if (l->thread == current_thread()) {
        !           399:                /*
        !           400:                 *      Recursive lock.
        !           401:                 */
        !           402:                l->recursion_depth++;
        !           403:                simple_unlock(&l->interlock);
        !           404:                return(FALSE);
        !           405:        }
        !           406: 
        !           407:        if (l->want_upgrade) {
        !           408:                /*
        !           409:                 *      Someone else has requested upgrade.
        !           410:                 *      Since we've released a read lock, wake
        !           411:                 *      him up.
        !           412:                 */
        !           413:                if (l->waiting && (l->read_count == 0)) {
        !           414:                        l->waiting = FALSE;
        !           415:                        thread_wakeup(l);
        !           416:                }
        !           417: 
        !           418:                simple_unlock(&l->interlock);
        !           419:                return TRUE;
        !           420:        }
        !           421: 
        !           422:        l->want_upgrade = TRUE;
        !           423: 
        !           424:        while (l->read_count != 0) {
        !           425:                if ((i = lock_wait_time) > 0) {
        !           426:                        simple_unlock(&l->interlock);
        !           427:                        while (--i > 0 && l->read_count != 0)
        !           428:                                continue;
        !           429:                        simple_lock(&l->interlock);
        !           430:                }
        !           431: 
        !           432:                if (l->can_sleep && l->read_count != 0) {
        !           433:                        l->waiting = TRUE;
        !           434:                        thread_sleep(l,
        !           435:                                simple_lock_addr(l->interlock), FALSE);
        !           436:                        simple_lock(&l->interlock);
        !           437:                }
        !           438:        }
        !           439: 
        !           440:        simple_unlock(&l->interlock);
        !           441:        return FALSE;
        !           442: }
        !           443: 
        !           444: void lock_write_to_read(
        !           445:        register lock_t l)
        !           446: {
        !           447:        simple_lock(&l->interlock);
        !           448: 
        !           449:        l->read_count++;
        !           450:        if (l->recursion_depth != 0)
        !           451:                l->recursion_depth--;
        !           452:        else
        !           453:        if (l->want_upgrade)
        !           454:                l->want_upgrade = FALSE;
        !           455:        else
        !           456:                l->want_write = FALSE;
        !           457: 
        !           458:        if (l->waiting) {
        !           459:                l->waiting = FALSE;
        !           460:                thread_wakeup(l);
        !           461:        }
        !           462: 
        !           463:        simple_unlock(&l->interlock);
        !           464: }
        !           465: 
        !           466: 
        !           467: /*
        !           468:  *     Routine:        lock_try_write
        !           469:  *     Function:
        !           470:  *             Tries to get a write lock.
        !           471:  *
        !           472:  *             Returns FALSE if the lock is not held on return.
        !           473:  */
        !           474: 
        !           475: boolean_t lock_try_write(
        !           476:        register lock_t l)
        !           477: {
        !           478:        simple_lock(&l->interlock);
        !           479: 
        !           480:        if (l->thread == current_thread()) {
        !           481:                /*
        !           482:                 *      Recursive lock
        !           483:                 */
        !           484:                l->recursion_depth++;
        !           485:                simple_unlock(&l->interlock);
        !           486:                return TRUE;
        !           487:        }
        !           488: 
        !           489:        if (l->want_write || l->want_upgrade || l->read_count) {
        !           490:                /*
        !           491:                 *      Can't get lock.
        !           492:                 */
        !           493:                simple_unlock(&l->interlock);
        !           494:                return FALSE;
        !           495:        }
        !           496: 
        !           497:        /*
        !           498:         *      Have lock.
        !           499:         */
        !           500: 
        !           501:        l->want_write = TRUE;
        !           502:        simple_unlock(&l->interlock);
        !           503:        return TRUE;
        !           504: }
        !           505: 
        !           506: /*
        !           507:  *     Routine:        lock_try_read
        !           508:  *     Function:
        !           509:  *             Tries to get a read lock.
        !           510:  *
        !           511:  *             Returns FALSE if the lock is not held on return.
        !           512:  */
        !           513: 
        !           514: boolean_t lock_try_read(
        !           515:        register lock_t l)
        !           516: {
        !           517:        simple_lock(&l->interlock);
        !           518: 
        !           519:        if (l->thread == current_thread()) {
        !           520:                /*
        !           521:                 *      Recursive lock
        !           522:                 */
        !           523:                l->read_count++;
        !           524:                simple_unlock(&l->interlock);
        !           525:                return TRUE;
        !           526:        }
        !           527: 
        !           528:        if (l->want_write || l->want_upgrade) {
        !           529:                simple_unlock(&l->interlock);
        !           530:                return FALSE;
        !           531:        }
        !           532: 
        !           533:        l->read_count++;
        !           534:        simple_unlock(&l->interlock);
        !           535:        return TRUE;
        !           536: }
        !           537: 
        !           538: /*
        !           539:  *     Routine:        lock_try_read_to_write
        !           540:  *     Function:
        !           541:  *             Improves a read-only lock to one with
        !           542:  *             write permission.  If another reader has
        !           543:  *             already requested an upgrade to a write lock,
        !           544:  *             the read lock is still held upon return.
        !           545:  *
        !           546:  *             Returns FALSE if the upgrade *failed*.
        !           547:  */
        !           548: boolean_t lock_try_read_to_write(
        !           549:        register lock_t l)
        !           550: {
        !           551:        check_simple_locks();
        !           552:        simple_lock(&l->interlock);
        !           553: 
        !           554:        if (l->thread == current_thread()) {
        !           555:                /*
        !           556:                 *      Recursive lock
        !           557:                 */
        !           558:                l->read_count--;
        !           559:                l->recursion_depth++;
        !           560:                simple_unlock(&l->interlock);
        !           561:                return TRUE;
        !           562:        }
        !           563: 
        !           564:        if (l->want_upgrade) {
        !           565:                simple_unlock(&l->interlock);
        !           566:                return FALSE;
        !           567:        }
        !           568:        l->want_upgrade = TRUE;
        !           569:        l->read_count--;
        !           570: 
        !           571:        while (l->read_count != 0) {
        !           572:                l->waiting = TRUE;
        !           573:                thread_sleep(l,
        !           574:                        simple_lock_addr(l->interlock), FALSE);
        !           575:                simple_lock(&l->interlock);
        !           576:        }
        !           577: 
        !           578:        simple_unlock(&l->interlock);
        !           579:        return TRUE;
        !           580: }
        !           581: 
        !           582: /*
        !           583:  *     Allow a process that has a lock for write to acquire it
        !           584:  *     recursively (for read, write, or update).
        !           585:  */
        !           586: void lock_set_recursive(
        !           587:        lock_t          l)
        !           588: {
        !           589:        simple_lock(&l->interlock);
        !           590:        if (!l->want_write) {
        !           591:                panic("lock_set_recursive: don't have write lock");
        !           592:        }
        !           593:        l->thread = current_thread();
        !           594:        simple_unlock(&l->interlock);
        !           595: }
        !           596: 
        !           597: /*
        !           598:  *     Prevent a lock from being re-acquired.
        !           599:  */
        !           600: void lock_clear_recursive(
        !           601:        lock_t          l)
        !           602: {
        !           603:        simple_lock(&l->interlock);
        !           604:        if (l->thread != current_thread()) {
        !           605:                panic("lock_clear_recursive: wrong thread");
        !           606:        }
        !           607:        if (l->recursion_depth == 0)
        !           608:                l->thread = (struct thread *)-1;        /* XXX */
        !           609:        simple_unlock(&l->interlock);
        !           610: }
        !           611: 
        !           612: #if    MACH_KDB
        !           613: #if    MACH_SLOCKS && NCPUS == 1
        !           614: void db_show_all_slocks(void)
        !           615: {
        !           616:        int i;
        !           617:        struct simple_locks_info *info;
        !           618:        simple_lock_t l;
        !           619: 
        !           620:        for (i = 0; i < simple_locks_taken; i++) {
        !           621:                info = &simple_locks_info[i];
        !           622:                db_printf("%d: ", i);
        !           623:                db_printsym(info->l, DB_STGY_ANY);
        !           624: #if i386
        !           625:                db_printf(" locked by ");
        !           626:                db_printsym(info->ra, DB_STGY_PROC);
        !           627: #endif
        !           628:                db_printf("\n");
        !           629:        }
        !           630: }
        !           631: #else  /* MACH_SLOCKS && NCPUS == 1 */
        !           632: void db_show_all_slocks(void)
        !           633: {
        !           634:        db_printf("simple lock info not available\n");
        !           635: }
        !           636: #endif /* MACH_SLOCKS && NCPUS == 1 */
        !           637: #endif /* MACH_KDB */

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.