WebSVN – HelenOS-historic – Diff – /kernel/trunk/generic/src/synch/rwlock.c


/*
 * Copyright (C) 2001-2004 Jakub Jermar
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * - Redistributions of source code must retain the above copyright
 *   notice, this list of conditions and the following disclaimer.
 * - Redistributions in binary form must reproduce the above copyright
 *   notice, this list of conditions and the following disclaimer in the
 *   documentation and/or other materials provided with the distribution.
 * - The name of the author may not be used to endorse or promote products
 *   derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
 
/**
 * @file    rwlock.c
 * @brief   Reader/Writer locks.
 *
 * A reader/writer lock can be held by multiple readers at a time.
 * Or it can be exclusively held by a sole writer at a time.
 *
 
 
 * These locks are not recursive.
 * Because technique called direct hand-off is used, neither readers
 * nor writers will suffer starvation.
 *
 * If there is a writer followed by a reader waiting for the rwlock
 * and the writer times out, all leading readers are automatically woken up
 * and allowed in.
 */
 
/*
 * NOTE ON rwlock_holder_type
 * This field is set on an attempt to acquire the exclusive mutex
 * to the respective value depending whether the caller is a reader
 * or a writer. The field is examined only if the thread had been
 * previously blocked on the exclusive mutex. Thus it is save
 * to store the rwlock type in the thread structure, because
 * each thread can block on only one rwlock at a time.
 */
 
#include <synch/rwlock.h>
#include <synch/spinlock.h>
#include <synch/mutex.h>
#include <synch/waitq.h>
#include <synch/synch.h>
#include <adt/list.h>
#include <typedefs.h>
#include <arch/asm.h>
#include <arch.h>
#include <proc/thread.h>
#include <panic.h>
 
#define ALLOW_ALL       0
#define ALLOW_READERS_ONLY  1
 
static void let_others_in(rwlock_t *rwl, int readers_only);
static void release_spinlock(void *arg);
 
/** Initialize reader/writer lock
 *
 * Initialize reader/writer lock.
 *
 * @param rwl Reader/Writer lock.
 */
void rwlock_initialize(rwlock_t *rwl) {
    spinlock_initialize(&rwl->lock, "rwlock_t");
    mutex_initialize(&rwl->exclusive);
    rwl->readers_in = 0;
}
 
/** Acquire reader/writer lock for reading
 *
 * Acquire reader/writer lock for reading.
 * Timeout and willingness to block may be specified.
 *
 * @param rwl Reader/Writer lock.
 * @param usec Timeout in microseconds.
 * @param trylock Switches between blocking and non-blocking mode.
 *
 * For exact description of possible combinations of
 * @usec and @trylock, see comment for waitq_sleep_timeout().
 *
 * @return See comment for waitq_sleep_timeout().
 */
int _rwlock_write_lock_timeout(rwlock_t *rwl, __u32 usec, int trylock)
{
    ipl_t ipl;
    int rc;
   
    ipl = interrupts_disable();
    spinlock_lock(&THREAD->lock);
    THREAD->rwlock_holder_type = RWLOCK_WRITER;
    spinlock_unlock(&THREAD->lock);
    interrupts_restore(ipl);
 
    /*
     * Writers take the easy part.
     * They just need to acquire the exclusive mutex.
     */
    rc = _mutex_lock_timeout(&rwl->exclusive, usec, trylock);
    if (SYNCH_FAILED(rc)) {
 
        /*
         * Lock operation timed out.
         * The state of rwl is UNKNOWN at this point.
         * No claims about its holder can be made.
         */
         
        ipl = interrupts_disable();
        spinlock_lock(&rwl->lock);
        /*
         * Now when rwl is locked, we can inspect it again.
         * If it is held by some readers already, we can let
         * readers from the head of the wait queue in.
         */
        if (rwl->readers_in)
            let_others_in(rwl, ALLOW_READERS_ONLY);
        spinlock_unlock(&rwl->lock);
        interrupts_restore(ipl);
    }
   
    return rc;
}
 
/** Acquire reader/writer lock for writing
 *
 * Acquire reader/writer lock for writing.
 * Timeout and willingness to block may be specified.
 *
 * @param rwl Reader/Writer lock.
 * @param usec Timeout in microseconds.
 * @param trylock Switches between blocking and non-blocking mode.
 *
 * For exact description of possible combinations of
 * usec and trylock, see comment for waitq_sleep_timeout().
 *
 * @return See comment for waitq_sleep_timeout().
 */
int _rwlock_read_lock_timeout(rwlock_t *rwl, __u32 usec, int trylock)
{
    int rc;
    ipl_t ipl;
   
    ipl = interrupts_disable();
    spinlock_lock(&THREAD->lock);
    THREAD->rwlock_holder_type = RWLOCK_READER;
    spinlock_unlock(&THREAD->lock);
 
    spinlock_lock(&rwl->lock);
 
    /*
     * Find out whether we can get what we want without blocking.
     */
    rc = mutex_trylock(&rwl->exclusive);
    if (SYNCH_FAILED(rc)) {
 
        /*
         * 'exclusive' mutex is being held by someone else.
         * If the holder is a reader and there is no one
         * else waiting for it, we can enter the critical
         * section.
         */
 
        if (rwl->readers_in) {
            spinlock_lock(&rwl->exclusive.sem.wq.lock);
            if (list_empty(&rwl->exclusive.sem.wq.head)) {
                /*
                 * We can enter.
                 */
                spinlock_unlock(&rwl->exclusive.sem.wq.lock);
                goto shortcut;
            }
            spinlock_unlock(&rwl->exclusive.sem.wq.lock);
        }
 
        /*
         * In order to prevent a race condition when a reader
         * could block another reader at the head of the waitq,
         * we register a function to unlock rwl->lock
         * after this thread is put asleep.
         */
        #ifdef CONFIG_SMP
        thread_register_call_me(release_spinlock, &rwl->lock);
        #else
        thread_register_call_me(release_spinlock, NULL);
        #endif
                 
        rc = _mutex_lock_timeout(&rwl->exclusive, usec, trylock);
        switch (rc) {
            case ESYNCH_WOULD_BLOCK:
                /*
                 * release_spinlock() wasn't called
                 */
                thread_register_call_me(NULL, NULL);
                spinlock_unlock(&rwl->lock);
            case ESYNCH_TIMEOUT:
                /*
                 * The sleep timeouted.
                 * We just restore interrupt priority level.
                 */
            case ESYNCH_OK_BLOCKED:    
                /*
                 * We were woken with rwl->readers_in already incremented.
                 * Note that this arrangement avoids race condition between
                 * two concurrent readers. (Race is avoided if 'exclusive' is
                 * locked at the same time as 'readers_in' is incremented.
                 * Same time means both events happen atomically when
                 * rwl->lock is held.)
                 */
                interrupts_restore(ipl);
                break;
            case ESYNCH_OK_ATOMIC:
                panic("_mutex_lock_timeout()==ESYNCH_OK_ATOMIC\n");
                break;
            default:
                panic("invalid ESYNCH\n");
                break;
        }
        return rc;
    }
 
shortcut:
 
    /*
     * We can increment readers_in only if we didn't go to sleep.
     * For sleepers, rwlock_let_others_in() will do the job.
     */
    rwl->readers_in++;
   
    spinlock_unlock(&rwl->lock);
    interrupts_restore(ipl);
 
    return ESYNCH_OK_ATOMIC;
}
 
/** Release reader/writer lock held by writer
 *
 * Release reader/writer lock held by writer.
 * Handoff reader/writer lock ownership directly
 * to waiting readers or a writer.
 *
 * @param rwl Reader/Writer lock.
 */
void rwlock_write_unlock(rwlock_t *rwl)
{
    ipl_t ipl;
   
    ipl = interrupts_disable();
    spinlock_lock(&rwl->lock);
    let_others_in(rwl, ALLOW_ALL);
    spinlock_unlock(&rwl->lock);
    interrupts_restore(ipl);
   
}
 
/** Release reader/writer lock held by reader
 *
 * Release reader/writer lock held by reader.
 * Handoff reader/writer lock ownership directly
 * to a waiting writer or don't do anything if more
 * readers poses the lock.
 *
 * @param rwl Reader/Writer lock.
 */
void rwlock_read_unlock(rwlock_t *rwl)
{
    ipl_t ipl;
 
    ipl = interrupts_disable();
    spinlock_lock(&rwl->lock);
    if (!--rwl->readers_in)
        let_others_in(rwl, ALLOW_ALL);
    spinlock_unlock(&rwl->lock);
    interrupts_restore(ipl);
}
 
 
/** Direct handoff of reader/writer lock ownership.
 *
 * Direct handoff of reader/writer lock ownership
 * to waiting readers or a writer.
 *
 * Must be called with rwl->lock locked.
 * Must be called with interrupts_disable()'d.
 *
 * @param rwl Reader/Writer lock.
 * @param readers_only See the description below.
 *
 * If readers_only is false: (unlock scenario)
 * Let the first sleeper on 'exclusive' mutex in, no matter
 * whether it is a reader or a writer. If there are more leading
 * readers in line, let each of them in.
 *
 * Otherwise: (timeout scenario)
 * Let all leading readers in.
 */
void let_others_in(rwlock_t *rwl, int readers_only)
{
    rwlock_type_t type = RWLOCK_NONE;
    thread_t *t = NULL;
    bool one_more = true;
   
    spinlock_lock(&rwl->exclusive.sem.wq.lock);
 
    if (!list_empty(&rwl->exclusive.sem.wq.head))
        t = list_get_instance(rwl->exclusive.sem.wq.head.next, thread_t, wq_link);
    do {
        if (t) {
            spinlock_lock(&t->lock);
            type = t->rwlock_holder_type;
            spinlock_unlock(&t->lock);         
        }
   
        /*
         * If readers_only is true, we wake all leading readers
         * if and only if rwl is locked by another reader.
         * Assumption: readers_only ==> rwl->readers_in
         */
        if (readers_only && (type != RWLOCK_READER))
            break;
 
 
        if (type == RWLOCK_READER) {
            /*
             * Waking up a reader.
             * We are responsible for incrementing rwl->readers_in for it.
             */
             rwl->readers_in++;
        }
 
        /*
         * Only the last iteration through this loop can increment
         * rwl->exclusive.sem.wq.missed_wakeup's. All preceeding
         * iterations will wake up a thread.
         */
        /* We call the internal version of waitq_wakeup, which
         * relies on the fact that the waitq is already locked.
         */
        _waitq_wakeup_unsafe(&rwl->exclusive.sem.wq, WAKEUP_FIRST);
       
        t = NULL;
        if (!list_empty(&rwl->exclusive.sem.wq.head)) {
            t = list_get_instance(rwl->exclusive.sem.wq.head.next, thread_t, wq_link);
            if (t) {
                spinlock_lock(&t->lock);
                if (t->rwlock_holder_type != RWLOCK_READER)
                    one_more = false;
                spinlock_unlock(&t->lock); 
            }
        }
    } while ((type == RWLOCK_READER) && t && one_more);
 
    spinlock_unlock(&rwl->exclusive.sem.wq.lock);
}
 
/** Release spinlock callback
 *
 * This is a callback function invoked from the scheduler.
 * The callback is registered in _rwlock_read_lock_timeout().
 *
 * @param arg Spinlock.
 */
void release_spinlock(void *arg)
{
    spinlock_unlock((spinlock_t *) arg);
}
 
Subversion Repositories HelenOS-historic

(root)/kernel/trunk/generic/src/synch/rwlock.c – Rev 1229 → 1248
