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 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, __u32 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, __u32 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);
}
 

Rev 1248	Rev 1502
1	/*	1	/*
2	* Copyright (C) 2001-2004 Jakub Jermar	2	* Copyright (C) 2001-2004 Jakub Jermar
3	* All rights reserved.	3	* All rights reserved.
4	*	4	*
5	* Redistribution and use in source and binary forms, with or without	5	* Redistribution and use in source and binary forms, with or without
6	* modification, are permitted provided that the following conditions	6	* modification, are permitted provided that the following conditions
7	* are met:	7	* are met:
8	*	8	*
9	* - Redistributions of source code must retain the above copyright	9	* - Redistributions of source code must retain the above copyright
10	* notice, this list of conditions and the following disclaimer.	10	* notice, this list of conditions and the following disclaimer.
11	* - Redistributions in binary form must reproduce the above copyright	11	* - Redistributions in binary form must reproduce the above copyright
12	* notice, this list of conditions and the following disclaimer in the	12	* notice, this list of conditions and the following disclaimer in the
13	* documentation and/or other materials provided with the distribution.	13	* documentation and/or other materials provided with the distribution.
14	* - The name of the author may not be used to endorse or promote products	14	* - The name of the author may not be used to endorse or promote products
15	* derived from this software without specific prior written permission.	15	* derived from this software without specific prior written permission.
16	*	16	*
17	* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR	17	* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18	* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES	18	* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19	* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.	19	* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20	* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,	20	* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21	* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT	21	* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22	* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,	22	* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23	* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY	23	* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24	* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT	24	* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25	* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF	25	* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26	* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.	26	* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27	*/	27	*/
28		28
29	/**	29	/**
30	* @file rwlock.c	30	* @file rwlock.c
31	* @brief Reader/Writer locks.	31	* @brief Reader/Writer locks.
32	*	32	*
33	* A reader/writer lock can be held by multiple readers at a time.	33	* A reader/writer lock can be held by multiple readers at a time.
34	* Or it can be exclusively held by a sole writer at a time.	34	* Or it can be exclusively held by a sole writer at a time.
35	*	35	*
36	* These locks are not recursive.	36	* These locks are not recursive.
37	* Because technique called direct hand-off is used, neither readers	37	* Because technique called direct hand-off is used, neither readers
38	* nor writers will suffer starvation.	38	* nor writers will suffer starvation.
39	*	39	*
40	* If there is a writer followed by a reader waiting for the rwlock	40	* If there is a writer followed by a reader waiting for the rwlock
41	* and the writer times out, all leading readers are automatically woken up	41	* and the writer times out, all leading readers are automatically woken up
42	* and allowed in.	42	* and allowed in.
43	*/	43	*/
44		44
45	/*	45	/*
46	* NOTE ON rwlock_holder_type	46	* NOTE ON rwlock_holder_type
47	* This field is set on an attempt to acquire the exclusive mutex	47	* This field is set on an attempt to acquire the exclusive mutex
48	* to the respective value depending whether the caller is a reader	48	* to the respective value depending whether the caller is a reader
49	* or a writer. The field is examined only if the thread had been	49	* or a writer. The field is examined only if the thread had been
50	* previously blocked on the exclusive mutex. Thus it is save	50	* previously blocked on the exclusive mutex. Thus it is save
51	* to store the rwlock type in the thread structure, because	51	* to store the rwlock type in the thread structure, because
52	* each thread can block on only one rwlock at a time.	52	* each thread can block on only one rwlock at a time.
53	*/	53	*/
54		54
55	#include <synch/rwlock.h>	55	#include <synch/rwlock.h>
56	#include <synch/spinlock.h>	56	#include <synch/spinlock.h>
57	#include <synch/mutex.h>	57	#include <synch/mutex.h>
58	#include <synch/waitq.h>	58	#include <synch/waitq.h>
59	#include <synch/synch.h>	59	#include <synch/synch.h>
60	#include <adt/list.h>	60	#include <adt/list.h>
61	#include <typedefs.h>	61	#include <typedefs.h>
62	#include <arch/asm.h>	62	#include <arch/asm.h>
63	#include <arch.h>	63	#include <arch.h>
64	#include <proc/thread.h>	64	#include <proc/thread.h>
65	#include <panic.h>	65	#include <panic.h>
66		66
67	#define ALLOW_ALL 0	67	#define ALLOW_ALL 0
68	#define ALLOW_READERS_ONLY 1	68	#define ALLOW_READERS_ONLY 1
69		69
70	static void let_others_in(rwlock_t *rwl, int readers_only);	70	static void let_others_in(rwlock_t *rwl, int readers_only);
71	static void release_spinlock(void *arg);	71	static void release_spinlock(void *arg);
72		72
73	/** Initialize reader/writer lock	73	/** Initialize reader/writer lock
74	*	74	*
75	* Initialize reader/writer lock.	75	* Initialize reader/writer lock.
76	*	76	*
77	* @param rwl Reader/Writer lock.	77	* @param rwl Reader/Writer lock.
78	*/	78	*/
79	void rwlock_initialize(rwlock_t *rwl) {	79	void rwlock_initialize(rwlock_t *rwl) {
80	spinlock_initialize(&rwl->lock, "rwlock_t");	80	spinlock_initialize(&rwl->lock, "rwlock_t");
81	mutex_initialize(&rwl->exclusive);	81	mutex_initialize(&rwl->exclusive);
82	rwl->readers_in = 0;	82	rwl->readers_in = 0;
83	}	83	}
84		84
85	/** Acquire reader/writer lock for reading	85	/** Acquire reader/writer lock for reading
86	*	86	*
87	* Acquire reader/writer lock for reading.	87	* Acquire reader/writer lock for reading.
88	* Timeout and willingness to block may be specified.	88	* Timeout and willingness to block may be specified.
89	*	89	*
90	* @param rwl Reader/Writer lock.	90	* @param rwl Reader/Writer lock.
91	* @param usec Timeout in microseconds.	91	* @param usec Timeout in microseconds.
92	* @param trylock Switches between blocking and non-blocking mode.	92	* @param flags Specify mode of operation.
93	*	93	*
94	* For exact description of possible combinations of	94	* For exact description of possible combinations of
95	* @usec and @trylock, see comment for waitq_sleep_timeout().	95	* usec and flags, see comment for waitq_sleep_timeout().
96	*	96	*
97	* @return See comment for waitq_sleep_timeout().	97	* @return See comment for waitq_sleep_timeout().
98	*/	98	*/
99	int _rwlock_write_lock_timeout(rwlock_t *rwl, __u32 usec, int trylock)	99	int _rwlock_write_lock_timeout(rwlock_t *rwl, __u32 usec, int flags)
100	{	100	{
101	ipl_t ipl;	101	ipl_t ipl;
102	int rc;	102	int rc;
103		103
104	ipl = interrupts_disable();	104	ipl = interrupts_disable();
105	spinlock_lock(&THREAD->lock);	105	spinlock_lock(&THREAD->lock);
106	THREAD->rwlock_holder_type = RWLOCK_WRITER;	106	THREAD->rwlock_holder_type = RWLOCK_WRITER;
107	spinlock_unlock(&THREAD->lock);	107	spinlock_unlock(&THREAD->lock);
108	interrupts_restore(ipl);	108	interrupts_restore(ipl);
109		109
110	/*	110	/*
111	* Writers take the easy part.	111	* Writers take the easy part.
112	* They just need to acquire the exclusive mutex.	112	* They just need to acquire the exclusive mutex.
113	*/	113	*/
114	rc = _mutex_lock_timeout(&rwl->exclusive, usec, trylock);	114	rc = _mutex_lock_timeout(&rwl->exclusive, usec, flags);
115	if (SYNCH_FAILED(rc)) {	115	if (SYNCH_FAILED(rc)) {
116		116
117	/*	117	/*
118	* Lock operation timed out.	118	* Lock operation timed out or was interrupted.
119	* The state of rwl is UNKNOWN at this point.	119	* The state of rwl is UNKNOWN at this point.
120	* No claims about its holder can be made.	120	* No claims about its holder can be made.
121	*/	121	*/
122		122
123	ipl = interrupts_disable();	123	ipl = interrupts_disable();
124	spinlock_lock(&rwl->lock);	124	spinlock_lock(&rwl->lock);
125	/*	125	/*
126	* Now when rwl is locked, we can inspect it again.	126	* Now when rwl is locked, we can inspect it again.
127	* If it is held by some readers already, we can let	127	* If it is held by some readers already, we can let
128	* readers from the head of the wait queue in.	128	* readers from the head of the wait queue in.
129	*/	129	*/
130	if (rwl->readers_in)	130	if (rwl->readers_in)
131	let_others_in(rwl, ALLOW_READERS_ONLY);	131	let_others_in(rwl, ALLOW_READERS_ONLY);
132	spinlock_unlock(&rwl->lock);	132	spinlock_unlock(&rwl->lock);
133	interrupts_restore(ipl);	133	interrupts_restore(ipl);
134	}	134	}
135		135
136	return rc;	136	return rc;
137	}	137	}
138		138
139	/** Acquire reader/writer lock for writing	139	/** Acquire reader/writer lock for writing
140	*	140	*
141	* Acquire reader/writer lock for writing.	141	* Acquire reader/writer lock for writing.
142	* Timeout and willingness to block may be specified.	142	* Timeout and willingness to block may be specified.
143	*	143	*
144	* @param rwl Reader/Writer lock.	144	* @param rwl Reader/Writer lock.
145	* @param usec Timeout in microseconds.	145	* @param usec Timeout in microseconds.
146	* @param trylock Switches between blocking and non-blocking mode.	146	* @param flags Select mode of operation.
147	*	147	*
148	* For exact description of possible combinations of	148	* For exact description of possible combinations of
149	* usec and trylock, see comment for waitq_sleep_timeout().	149	* usec and flags, see comment for waitq_sleep_timeout().
150	*	150	*
151	* @return See comment for waitq_sleep_timeout().	151	* @return See comment for waitq_sleep_timeout().
152	*/	152	*/
153	int _rwlock_read_lock_timeout(rwlock_t *rwl, __u32 usec, int trylock)	153	int _rwlock_read_lock_timeout(rwlock_t *rwl, __u32 usec, int flags)
154	{	154	{
155	int rc;	155	int rc;
156	ipl_t ipl;	156	ipl_t ipl;
157		157
158	ipl = interrupts_disable();	158	ipl = interrupts_disable();
159	spinlock_lock(&THREAD->lock);	159	spinlock_lock(&THREAD->lock);
160	THREAD->rwlock_holder_type = RWLOCK_READER;	160	THREAD->rwlock_holder_type = RWLOCK_READER;
161	spinlock_unlock(&THREAD->lock);	161	spinlock_unlock(&THREAD->lock);
162		162
163	spinlock_lock(&rwl->lock);	163	spinlock_lock(&rwl->lock);
164		164
165	/*	165	/*
166	* Find out whether we can get what we want without blocking.	166	* Find out whether we can get what we want without blocking.
167	*/	167	*/
168	rc = mutex_trylock(&rwl->exclusive);	168	rc = mutex_trylock(&rwl->exclusive);
169	if (SYNCH_FAILED(rc)) {	169	if (SYNCH_FAILED(rc)) {
170		170
171	/*	171	/*
172	* 'exclusive' mutex is being held by someone else.	172	* 'exclusive' mutex is being held by someone else.
173	* If the holder is a reader and there is no one	173	* If the holder is a reader and there is no one
174	* else waiting for it, we can enter the critical	174	* else waiting for it, we can enter the critical
175	* section.	175	* section.
176	*/	176	*/
177		177
178	if (rwl->readers_in) {	178	if (rwl->readers_in) {
179	spinlock_lock(&rwl->exclusive.sem.wq.lock);	179	spinlock_lock(&rwl->exclusive.sem.wq.lock);
180	if (list_empty(&rwl->exclusive.sem.wq.head)) {	180	if (list_empty(&rwl->exclusive.sem.wq.head)) {
181	/*	181	/*
182	* We can enter.	182	* We can enter.
183	*/	183	*/
184	spinlock_unlock(&rwl->exclusive.sem.wq.lock);	184	spinlock_unlock(&rwl->exclusive.sem.wq.lock);
185	goto shortcut;	185	goto shortcut;
186	}	186	}
187	spinlock_unlock(&rwl->exclusive.sem.wq.lock);	187	spinlock_unlock(&rwl->exclusive.sem.wq.lock);
188	}	188	}
189		189
190	/*	190	/*
191	* In order to prevent a race condition when a reader	191	* In order to prevent a race condition when a reader
192	* could block another reader at the head of the waitq,	192	* could block another reader at the head of the waitq,
193	* we register a function to unlock rwl->lock	193	* we register a function to unlock rwl->lock
194	* after this thread is put asleep.	194	* after this thread is put asleep.
195	*/	195	*/
196	#ifdef CONFIG_SMP	196	#ifdef CONFIG_SMP
197	thread_register_call_me(release_spinlock, &rwl->lock);	197	thread_register_call_me(release_spinlock, &rwl->lock);
198	#else	198	#else
199	thread_register_call_me(release_spinlock, NULL);	199	thread_register_call_me(release_spinlock, NULL);
200	#endif	200	#endif
201		201
202	rc = _mutex_lock_timeout(&rwl->exclusive, usec, trylock);	202	rc = _mutex_lock_timeout(&rwl->exclusive, usec, flags);
203	switch (rc) {	203	switch (rc) {
204	case ESYNCH_WOULD_BLOCK:	204	case ESYNCH_WOULD_BLOCK:
205	/*	205	/*
206	* release_spinlock() wasn't called	206	* release_spinlock() wasn't called
207	*/	207	*/
208	thread_register_call_me(NULL, NULL);	208	thread_register_call_me(NULL, NULL);
209	spinlock_unlock(&rwl->lock);	209	spinlock_unlock(&rwl->lock);
210	case ESYNCH_TIMEOUT:	210	case ESYNCH_TIMEOUT:
-		211	case ESYNCH_INTERRUPTED:
211	/*	212	/*
212	* The sleep timeouted.	213	* The sleep timed out.
213	* We just restore interrupt priority level.	214	* We just restore interrupt priority level.
214	*/	215	*/
215	case ESYNCH_OK_BLOCKED:	216	case ESYNCH_OK_BLOCKED:
216	/*	217	/*
217	* We were woken with rwl->readers_in already incremented.	218	* We were woken with rwl->readers_in already incremented.
218	* Note that this arrangement avoids race condition between	219	* Note that this arrangement avoids race condition between
219	* two concurrent readers. (Race is avoided if 'exclusive' is	220	* two concurrent readers. (Race is avoided if 'exclusive' is
220	* locked at the same time as 'readers_in' is incremented.	221	* locked at the same time as 'readers_in' is incremented.
221	* Same time means both events happen atomically when	222	* Same time means both events happen atomically when
222	* rwl->lock is held.)	223	* rwl->lock is held.)
223	*/	224	*/
224	interrupts_restore(ipl);	225	interrupts_restore(ipl);
225	break;	226	break;
226	case ESYNCH_OK_ATOMIC:	227	case ESYNCH_OK_ATOMIC:
227	panic("_mutex_lock_timeout()==ESYNCH_OK_ATOMIC\n");	228	panic("_mutex_lock_timeout()==ESYNCH_OK_ATOMIC\n");
228	break;	229	break;
229	default:	230	default:
230	panic("invalid ESYNCH\n");	231	panic("invalid ESYNCH\n");
231	break;	232	break;
232	}	233	}
233	return rc;	234	return rc;
234	}	235	}
235		236
236	shortcut:	237	shortcut:
237		238
238	/*	239	/*
239	* We can increment readers_in only if we didn't go to sleep.	240	* We can increment readers_in only if we didn't go to sleep.
240	* For sleepers, rwlock_let_others_in() will do the job.	241	* For sleepers, rwlock_let_others_in() will do the job.
241	*/	242	*/
242	rwl->readers_in++;	243	rwl->readers_in++;
243		244
244	spinlock_unlock(&rwl->lock);	245	spinlock_unlock(&rwl->lock);
245	interrupts_restore(ipl);	246	interrupts_restore(ipl);
246		247
247	return ESYNCH_OK_ATOMIC;	248	return ESYNCH_OK_ATOMIC;
248	}	249	}
249		250
250	/** Release reader/writer lock held by writer	251	/** Release reader/writer lock held by writer
251	*	252	*
252	* Release reader/writer lock held by writer.	253	* Release reader/writer lock held by writer.
253	* Handoff reader/writer lock ownership directly	254	* Handoff reader/writer lock ownership directly
254	* to waiting readers or a writer.	255	* to waiting readers or a writer.
255	*	256	*
256	* @param rwl Reader/Writer lock.	257	* @param rwl Reader/Writer lock.
257	*/	258	*/
258	void rwlock_write_unlock(rwlock_t *rwl)	259	void rwlock_write_unlock(rwlock_t *rwl)
259	{	260	{
260	ipl_t ipl;	261	ipl_t ipl;
261		262
262	ipl = interrupts_disable();	263	ipl = interrupts_disable();
263	spinlock_lock(&rwl->lock);	264	spinlock_lock(&rwl->lock);
264	let_others_in(rwl, ALLOW_ALL);	265	let_others_in(rwl, ALLOW_ALL);
265	spinlock_unlock(&rwl->lock);	266	spinlock_unlock(&rwl->lock);
266	interrupts_restore(ipl);	267	interrupts_restore(ipl);
267		268
268	}	269	}
269		270
270	/** Release reader/writer lock held by reader	271	/** Release reader/writer lock held by reader
271	*	272	*
272	* Release reader/writer lock held by reader.	273	* Release reader/writer lock held by reader.
273	* Handoff reader/writer lock ownership directly	274	* Handoff reader/writer lock ownership directly
274	* to a waiting writer or don't do anything if more	275	* to a waiting writer or don't do anything if more
275	* readers poses the lock.	276	* readers poses the lock.
276	*	277	*
277	* @param rwl Reader/Writer lock.	278	* @param rwl Reader/Writer lock.
278	*/	279	*/
279	void rwlock_read_unlock(rwlock_t *rwl)	280	void rwlock_read_unlock(rwlock_t *rwl)
280	{	281	{
281	ipl_t ipl;	282	ipl_t ipl;
282		283
283	ipl = interrupts_disable();	284	ipl = interrupts_disable();
284	spinlock_lock(&rwl->lock);	285	spinlock_lock(&rwl->lock);
285	if (!--rwl->readers_in)	286	if (!--rwl->readers_in)
286	let_others_in(rwl, ALLOW_ALL);	287	let_others_in(rwl, ALLOW_ALL);
287	spinlock_unlock(&rwl->lock);	288	spinlock_unlock(&rwl->lock);
288	interrupts_restore(ipl);	289	interrupts_restore(ipl);
289	}	290	}
290		291
291		292
292	/** Direct handoff of reader/writer lock ownership.	293	/** Direct handoff of reader/writer lock ownership.
293	*	294	*
294	* Direct handoff of reader/writer lock ownership	295	* Direct handoff of reader/writer lock ownership
295	* to waiting readers or a writer.	296	* to waiting readers or a writer.
296	*	297	*
297	* Must be called with rwl->lock locked.	298	* Must be called with rwl->lock locked.
298	* Must be called with interrupts_disable()'d.	299	* Must be called with interrupts_disable()'d.
299	*	300	*
300	* @param rwl Reader/Writer lock.	301	* @param rwl Reader/Writer lock.
301	* @param readers_only See the description below.	302	* @param readers_only See the description below.
302	*	303	*
303	* If readers_only is false: (unlock scenario)	304	* If readers_only is false: (unlock scenario)
304	* Let the first sleeper on 'exclusive' mutex in, no matter	305	* Let the first sleeper on 'exclusive' mutex in, no matter
305	* whether it is a reader or a writer. If there are more leading	306	* whether it is a reader or a writer. If there are more leading
306	* readers in line, let each of them in.	307	* readers in line, let each of them in.
307	*	308	*
308	* Otherwise: (timeout scenario)	309	* Otherwise: (timeout scenario)
309	* Let all leading readers in.	310	* Let all leading readers in.
310	*/	311	*/
311	void let_others_in(rwlock_t *rwl, int readers_only)	312	void let_others_in(rwlock_t *rwl, int readers_only)
312	{	313	{
313	rwlock_type_t type = RWLOCK_NONE;	314	rwlock_type_t type = RWLOCK_NONE;
314	thread_t *t = NULL;	315	thread_t *t = NULL;
315	bool one_more = true;	316	bool one_more = true;
316		317
317	spinlock_lock(&rwl->exclusive.sem.wq.lock);	318	spinlock_lock(&rwl->exclusive.sem.wq.lock);
318		319
319	if (!list_empty(&rwl->exclusive.sem.wq.head))	320	if (!list_empty(&rwl->exclusive.sem.wq.head))
320	t = list_get_instance(rwl->exclusive.sem.wq.head.next, thread_t, wq_link);	321	t = list_get_instance(rwl->exclusive.sem.wq.head.next, thread_t, wq_link);
321	do {	322	do {
322	if (t) {	323	if (t) {
323	spinlock_lock(&t->lock);	324	spinlock_lock(&t->lock);
324	type = t->rwlock_holder_type;	325	type = t->rwlock_holder_type;
325	spinlock_unlock(&t->lock);	326	spinlock_unlock(&t->lock);
326	}	327	}
327		328
328	/*	329	/*
329	* If readers_only is true, we wake all leading readers	330	* If readers_only is true, we wake all leading readers
330	* if and only if rwl is locked by another reader.	331	* if and only if rwl is locked by another reader.
331	* Assumption: readers_only ==> rwl->readers_in	332	* Assumption: readers_only ==> rwl->readers_in
332	*/	333	*/
333	if (readers_only && (type != RWLOCK_READER))	334	if (readers_only && (type != RWLOCK_READER))
334	break;	335	break;
335		336
336		337
337	if (type == RWLOCK_READER) {	338	if (type == RWLOCK_READER) {
338	/*	339	/*
339	* Waking up a reader.	340	* Waking up a reader.
340	* We are responsible for incrementing rwl->readers_in for it.	341	* We are responsible for incrementing rwl->readers_in for it.
341	*/	342	*/
342	rwl->readers_in++;	343	rwl->readers_in++;
343	}	344	}
344		345
345	/*	346	/*
346	* Only the last iteration through this loop can increment	347	* Only the last iteration through this loop can increment
347	* rwl->exclusive.sem.wq.missed_wakeup's. All preceeding	348	* rwl->exclusive.sem.wq.missed_wakeup's. All preceeding
348	* iterations will wake up a thread.	349	* iterations will wake up a thread.
349	*/	350	*/
350	/* We call the internal version of waitq_wakeup, which	351	/* We call the internal version of waitq_wakeup, which
351	* relies on the fact that the waitq is already locked.	352	* relies on the fact that the waitq is already locked.
352	*/	353	*/
353	_waitq_wakeup_unsafe(&rwl->exclusive.sem.wq, WAKEUP_FIRST);	354	_waitq_wakeup_unsafe(&rwl->exclusive.sem.wq, WAKEUP_FIRST);
354		355
355	t = NULL;	356	t = NULL;
356	if (!list_empty(&rwl->exclusive.sem.wq.head)) {	357	if (!list_empty(&rwl->exclusive.sem.wq.head)) {
357	t = list_get_instance(rwl->exclusive.sem.wq.head.next, thread_t, wq_link);	358	t = list_get_instance(rwl->exclusive.sem.wq.head.next, thread_t, wq_link);
358	if (t) {	359	if (t) {
359	spinlock_lock(&t->lock);	360	spinlock_lock(&t->lock);
360	if (t->rwlock_holder_type != RWLOCK_READER)	361	if (t->rwlock_holder_type != RWLOCK_READER)
361	one_more = false;	362	one_more = false;
362	spinlock_unlock(&t->lock);	363	spinlock_unlock(&t->lock);
363	}	364	}
364	}	365	}
365	} while ((type == RWLOCK_READER) && t && one_more);	366	} while ((type == RWLOCK_READER) && t && one_more);
366		367
367	spinlock_unlock(&rwl->exclusive.sem.wq.lock);	368	spinlock_unlock(&rwl->exclusive.sem.wq.lock);
368	}	369	}
369		370
370	/** Release spinlock callback	371	/** Release spinlock callback
371	*	372	*
372	* This is a callback function invoked from the scheduler.	373	* This is a callback function invoked from the scheduler.
373	* The callback is registered in _rwlock_read_lock_timeout().	374	* The callback is registered in _rwlock_read_lock_timeout().
374	*	375	*
375	* @param arg Spinlock.	376	* @param arg Spinlock.
376	*/	377	*/
377	void release_spinlock(void *arg)	378	void release_spinlock(void *arg)
378	{	379	{
379	spinlock_unlock((spinlock_t *) arg);	380	spinlock_unlock((spinlock_t *) arg);
380	}	381	}
381		382

Subversion Repositories HelenOS-historic

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