0,0 → 1,393 |
/* |
* 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. |
*/ |
|
/** @addtogroup sync |
* @{ |
*/ |
|
/** |
* @file |
* @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 a technique called direct hand-off is used and because |
* waiting takes place in a single wait queue, 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 <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 flags Specify mode of operation. |
* |
* For exact description of possible combinations of |
* usec and flags, see comment for waitq_sleep_timeout(). |
* |
* @return See comment for waitq_sleep_timeout(). |
*/ |
int _rwlock_write_lock_timeout(rwlock_t *rwl, uint32_t usec, int flags) |
{ |
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, flags); |
if (SYNCH_FAILED(rc)) { |
|
/* |
* Lock operation timed out or was interrupted. |
* 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 flags Select mode of operation. |
* |
* For exact description of possible combinations of |
* usec and flags, see comment for waitq_sleep_timeout(). |
* |
* @return See comment for waitq_sleep_timeout(). |
*/ |
int _rwlock_read_lock_timeout(rwlock_t *rwl, uint32_t usec, int flags) |
{ |
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, flags); |
switch (rc) { |
case ESYNCH_WOULD_BLOCK: |
/* |
* release_spinlock() wasn't called |
*/ |
thread_register_call_me(NULL, NULL); |
spinlock_unlock(&rwl->lock); |
case ESYNCH_TIMEOUT: |
case ESYNCH_INTERRUPTED: |
/* |
* The sleep timed out. |
* 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); |
} |
|
/** @} |
*/ |