WebSVN – HelenOS – Diff – /trunk/kernel/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.
 */
 
 
/*
 * Reader/Writer locks
 */
 
/*
 * These locks are not recursive.
 * 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 <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);
    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)
{
    pri_t pri;
    int rc;
   
    pri = cpu_priority_high();
    spinlock_lock(&THREAD->lock);
    THREAD->rwlock_holder_type = RWLOCK_WRITER;
    spinlock_unlock(&THREAD->lock);
    cpu_priority_restore(pri);
 
    /*
     * 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.
         */
         
        pri = cpu_priority_high();
        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);
        cpu_priority_restore(pri);
    }
   
    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;
    pri_t pri;
   
    pri = cpu_priority_high();
    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.
         */
        thread_register_call_me(release_spinlock, &rwl->lock);
                 
        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 the cpu priority.
                 */
            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.)
                 */
                cpu_priority_restore(pri);
                break;
            case ESYNCH_OK_ATOMIC:
                panic("_mutex_lock_timeout()==ESYNCH_OK_ATOMIC");
                break;
            dafault:
                panic("invalid ESYNCH");
                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);
    cpu_priority_restore(pri);
 
    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)
{
    pri_t pri;
   
    pri = cpu_priority_high();
    spinlock_lock(&rwl->lock);
    let_others_in(rwl, ALLOW_ALL);
    spinlock_unlock(&rwl->lock);
    cpu_priority_restore(pri);
   
}
 
/** 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)
{
    pri_t pri;
 
    pri = cpu_priority_high();
    spinlock_lock(&rwl->lock);
    if (!--rwl->readers_in)
        let_others_in(rwl, ALLOW_ALL);
    spinlock_unlock(&rwl->lock);
    cpu_priority_restore(pri);
}
 
 
/** Direct handoff
 *
 * Direct handoff of reader/writer lock ownership
 * to waiting readers or a writer.
 *
 * Must be called with rwl->lock locked.
 * Must be called with cpu_priority_high'ed.
 *
 * @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;
    int one_more = 1;
   
    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 = 0;
                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 153	Rev 385
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	/*	30	/*
31	* Reader/Writer locks	31	* Reader/Writer locks
32	*/	32	*/
33		33
34	/*	34	/*
35	* These locks are not recursive.	35	* These locks are not recursive.
36	* Neither readers nor writers will suffer starvation.	36	* Neither readers nor writers will suffer starvation.
37	*	37	*
38	* If there is a writer followed by a reader waiting for the rwlock	38	* If there is a writer followed by a reader waiting for the rwlock
39	* and the writer times out, all leading readers are automatically woken up	39	* and the writer times out, all leading readers are automatically woken up
40	* and allowed in.	40	* and allowed in.
41	*/	41	*/
42		42
43	/*	43	/*
44	* NOTE ON rwlock_holder_type	44	* NOTE ON rwlock_holder_type
45	* This field is set on an attempt to acquire the exclusive mutex	45	* This field is set on an attempt to acquire the exclusive mutex
46	* to the respective value depending whether the caller is a reader	46	* to the respective value depending whether the caller is a reader
47	* or a writer. The field is examined only if the thread had been	47	* or a writer. The field is examined only if the thread had been
48	* previously blocked on the exclusive mutex. Thus it is save	48	* previously blocked on the exclusive mutex. Thus it is save
49	* to store the rwlock type in the thread structure, because	49	* to store the rwlock type in the thread structure, because
50	* each thread can block on only one rwlock at a time.	50	* each thread can block on only one rwlock at a time.
51	*/	51	*/
52		52
53	#include <synch/synch.h>	-
54	#include <synch/rwlock.h>	53	#include <synch/rwlock.h>
55	#include <synch/spinlock.h>	54	#include <synch/spinlock.h>
56	#include <synch/mutex.h>	55	#include <synch/mutex.h>
57	#include <synch/waitq.h>	56	#include <synch/waitq.h>
58		-
-		57	#include <synch/synch.h>
59	#include <list.h>	58	#include <list.h>
60	#include <typedefs.h>	59	#include <typedefs.h>
61	#include <arch/asm.h>	60	#include <arch/asm.h>
62	#include <arch.h>	61	#include <arch.h>
63	#include <proc/thread.h>	62	#include <proc/thread.h>
64	#include <panic.h>	63	#include <panic.h>
65		64
66	#define ALLOW_ALL 0	65	#define ALLOW_ALL 0
67	#define ALLOW_READERS_ONLY 1	66	#define ALLOW_READERS_ONLY 1
68		67
69	static void let_others_in(rwlock_t *rwl, int readers_only);	68	static void let_others_in(rwlock_t *rwl, int readers_only);
70	static void release_spinlock(void *arg);	69	static void release_spinlock(void *arg);
71		70
-		71	/** Initialize reader/writer lock
-		72	*
-		73	* Initialize reader/writer lock.
-		74	*
-		75	* @param rwl Reader/Writer lock.
-		76	*/
72	void rwlock_initialize(rwlock_t *rwl) {	77	void rwlock_initialize(rwlock_t *rwl) {
73	spinlock_initialize(&rwl->lock);	78	spinlock_initialize(&rwl->lock);
74	mutex_initialize(&rwl->exclusive);	79	mutex_initialize(&rwl->exclusive);
75	rwl->readers_in = 0;	80	rwl->readers_in = 0;
76	}	81	}
77		82
-		83	/** Acquire reader/writer lock for reading
-		84	*
-		85	* Acquire reader/writer lock for reading.
-		86	* Timeout and willingness to block may be specified.
-		87	*
-		88	* @param rwl Reader/Writer lock.
-		89	* @param usec Timeout in microseconds.
-		90	* @param trylock Switches between blocking and non-blocking mode.
-		91	*
-		92	* For exact description of possible combinations of
-		93	* 'usec' and 'trylock', see comment for waitq_sleep_timeout().
-		94	*
-		95	* @return See comment for waitq_sleep_timeout().
-		96	*/
78	int _rwlock_write_lock_timeout(rwlock_t *rwl, __u32 usec, int trylock)	97	int _rwlock_write_lock_timeout(rwlock_t *rwl, __u32 usec, int trylock)
79	{	98	{
80	pri_t pri;	99	pri_t pri;
81	int rc;	100	int rc;
82		101
83	pri = cpu_priority_high();	102	pri = cpu_priority_high();
84	spinlock_lock(&THREAD->lock);	103	spinlock_lock(&THREAD->lock);
85	THREAD->rwlock_holder_type = RWLOCK_WRITER;	104	THREAD->rwlock_holder_type = RWLOCK_WRITER;
86	spinlock_unlock(&THREAD->lock);	105	spinlock_unlock(&THREAD->lock);
87	cpu_priority_restore(pri);	106	cpu_priority_restore(pri);
88		107
89	/*	108	/*
90	* Writers take the easy part.	109	* Writers take the easy part.
91	* They just need to acquire the exclusive mutex.	110	* They just need to acquire the exclusive mutex.
92	*/	111	*/
93	rc = _mutex_lock_timeout(&rwl->exclusive, usec, trylock);	112	rc = _mutex_lock_timeout(&rwl->exclusive, usec, trylock);
94	if (SYNCH_FAILED(rc)) {	113	if (SYNCH_FAILED(rc)) {
95		114
96	/*	115	/*
97	* Lock operation timed out.	116	* Lock operation timed out.
98	* The state of rwl is UNKNOWN at this point.	117	* The state of rwl is UNKNOWN at this point.
99	* No claims about its holder can be made.	118	* No claims about its holder can be made.
100	*/	119	*/
101		120
102	pri = cpu_priority_high();	121	pri = cpu_priority_high();
103	spinlock_lock(&rwl->lock);	122	spinlock_lock(&rwl->lock);
104	/*	123	/*
105	* Now when rwl is locked, we can inspect it again.	124	* Now when rwl is locked, we can inspect it again.
106	* If it is held by some readers already, we can let	125	* If it is held by some readers already, we can let
107	* readers from the head of the wait queue in.	126	* readers from the head of the wait queue in.
108	*/	127	*/
109	if (rwl->readers_in)	128	if (rwl->readers_in)
110	let_others_in(rwl, ALLOW_READERS_ONLY);	129	let_others_in(rwl, ALLOW_READERS_ONLY);
111	spinlock_unlock(&rwl->lock);	130	spinlock_unlock(&rwl->lock);
112	cpu_priority_restore(pri);	131	cpu_priority_restore(pri);
113	}	132	}
114		133
115	return rc;	134	return rc;
116	}	135	}
117		136
-		137	/** Acquire reader/writer lock for writing
-		138	*
-		139	* Acquire reader/writer lock for writing.
-		140	* Timeout and willingness to block may be specified.
-		141	*
-		142	* @param rwl Reader/Writer lock.
-		143	* @param usec Timeout in microseconds.
-		144	* @param trylock Switches between blocking and non-blocking mode.
-		145	*
-		146	* For exact description of possible combinations of
-		147	* 'usec' and 'trylock', see comment for waitq_sleep_timeout().
-		148	*
-		149	* @return See comment for waitq_sleep_timeout().
-		150	*/
118	int _rwlock_read_lock_timeout(rwlock_t *rwl, __u32 usec, int trylock)	151	int _rwlock_read_lock_timeout(rwlock_t *rwl, __u32 usec, int trylock)
119	{	152	{
120	int rc;	153	int rc;
121	pri_t pri;	154	pri_t pri;
122		155
123	pri = cpu_priority_high();	156	pri = cpu_priority_high();
124	spinlock_lock(&THREAD->lock);	157	spinlock_lock(&THREAD->lock);
125	THREAD->rwlock_holder_type = RWLOCK_READER;	158	THREAD->rwlock_holder_type = RWLOCK_READER;
126	spinlock_unlock(&THREAD->lock);	159	spinlock_unlock(&THREAD->lock);
127		160
128	spinlock_lock(&rwl->lock);	161	spinlock_lock(&rwl->lock);
129		162
130	/*	163	/*
131	* Find out whether we can get what we want without blocking.	164	* Find out whether we can get what we want without blocking.
132	*/	165	*/
133	rc = mutex_trylock(&rwl->exclusive);	166	rc = mutex_trylock(&rwl->exclusive);
134	if (SYNCH_FAILED(rc)) {	167	if (SYNCH_FAILED(rc)) {
135		168
136	/*	169	/*
137	* 'exclusive' mutex is being held by someone else.	170	* 'exclusive' mutex is being held by someone else.
138	* If the holder is a reader and there is no one	171	* If the holder is a reader and there is no one
139	* else waiting for it, we can enter the critical	172	* else waiting for it, we can enter the critical
140	* section.	173	* section.
141	*/	174	*/
142		175
143	if (rwl->readers_in) {	176	if (rwl->readers_in) {
144	spinlock_lock(&rwl->exclusive.sem.wq.lock);	177	spinlock_lock(&rwl->exclusive.sem.wq.lock);
145	if (list_empty(&rwl->exclusive.sem.wq.head)) {	178	if (list_empty(&rwl->exclusive.sem.wq.head)) {
146	/*	179	/*
147	* We can enter.	180	* We can enter.
148	*/	181	*/
149	spinlock_unlock(&rwl->exclusive.sem.wq.lock);	182	spinlock_unlock(&rwl->exclusive.sem.wq.lock);
150	goto shortcut;	183	goto shortcut;
151	}	184	}
152	spinlock_unlock(&rwl->exclusive.sem.wq.lock);	185	spinlock_unlock(&rwl->exclusive.sem.wq.lock);
153	}	186	}
154		187
155	/*	188	/*
156	* In order to prevent a race condition when a reader	189	* In order to prevent a race condition when a reader
157	* could block another reader at the head of the waitq,	190	* could block another reader at the head of the waitq,
158	* we register a function to unlock rwl->lock	191	* we register a function to unlock rwl->lock
159	* after this thread is put asleep.	192	* after this thread is put asleep.
160	*/	193	*/
161	thread_register_call_me(release_spinlock, &rwl->lock);	194	thread_register_call_me(release_spinlock, &rwl->lock);
162		195
163	rc = _mutex_lock_timeout(&rwl->exclusive, usec, trylock);	196	rc = _mutex_lock_timeout(&rwl->exclusive, usec, trylock);
164	switch (rc) {	197	switch (rc) {
165	case ESYNCH_WOULD_BLOCK:	198	case ESYNCH_WOULD_BLOCK:
166	/*	199	/*
167	* release_spinlock() wasn't called	200	* release_spinlock() wasn't called
168	*/	201	*/
169	thread_register_call_me(NULL, NULL);	202	thread_register_call_me(NULL, NULL);
170	spinlock_unlock(&rwl->lock);	203	spinlock_unlock(&rwl->lock);
171	case ESYNCH_TIMEOUT:	204	case ESYNCH_TIMEOUT:
172	/*	205	/*
173	* The sleep timeouted.	206	* The sleep timeouted.
174	* We just restore the cpu priority.	207	* We just restore the cpu priority.
175	*/	208	*/
176	case ESYNCH_OK_BLOCKED:	209	case ESYNCH_OK_BLOCKED:
177	/*	210	/*
178	* We were woken with rwl->readers_in already incremented.	211	* We were woken with rwl->readers_in already incremented.
179	* Note that this arrangement avoids race condition between	212	* Note that this arrangement avoids race condition between
180	* two concurrent readers. (Race is avoided if 'exclusive' is	213	* two concurrent readers. (Race is avoided if 'exclusive' is
181	* locked at the same time as 'readers_in' is incremented.	214	* locked at the same time as 'readers_in' is incremented.
182	* Same time means both events happen atomically when	215	* Same time means both events happen atomically when
183	* rwl->lock is held.)	216	* rwl->lock is held.)
184	*/	217	*/
185	cpu_priority_restore(pri);	218	cpu_priority_restore(pri);
186	break;	219	break;
187	case ESYNCH_OK_ATOMIC:	220	case ESYNCH_OK_ATOMIC:
188	panic("_mutex_lock_timeout()==ESYNCH_OK_ATOMIC");	221	panic("_mutex_lock_timeout()==ESYNCH_OK_ATOMIC");
189	break;	222	break;
190	dafault:	223	dafault:
191	panic("invalid ESYNCH");	224	panic("invalid ESYNCH");
192	break;	225	break;
193	}	226	}
194	return rc;	227	return rc;
195	}	228	}
196		229
197	shortcut:	230	shortcut:
198		231
199	/*	232	/*
200	* We can increment readers_in only if we didn't go to sleep.	233	* We can increment readers_in only if we didn't go to sleep.
201	* For sleepers, rwlock_let_others_in() will do the job.	234	* For sleepers, rwlock_let_others_in() will do the job.
202	*/	235	*/
203	rwl->readers_in++;	236	rwl->readers_in++;
204		237
205	spinlock_unlock(&rwl->lock);	238	spinlock_unlock(&rwl->lock);
206	cpu_priority_restore(pri);	239	cpu_priority_restore(pri);
207		240
208	return ESYNCH_OK_ATOMIC;	241	return ESYNCH_OK_ATOMIC;
209	}	242	}
210		243
-		244	/** Release reader/writer lock held by writer
-		245	*
-		246	* Release reader/writer lock held by writer.
-		247	* Handoff reader/writer lock ownership directly
-		248	* to waiting readers or a writer.
-		249	*
-		250	* @param rwl Reader/Writer lock.
-		251	*/
211	void rwlock_write_unlock(rwlock_t *rwl)	252	void rwlock_write_unlock(rwlock_t *rwl)
212	{	253	{
213	pri_t pri;	254	pri_t pri;
214		255
215	pri = cpu_priority_high();	256	pri = cpu_priority_high();
216	spinlock_lock(&rwl->lock);	257	spinlock_lock(&rwl->lock);
217	let_others_in(rwl, ALLOW_ALL);	258	let_others_in(rwl, ALLOW_ALL);
218	spinlock_unlock(&rwl->lock);	259	spinlock_unlock(&rwl->lock);
219	cpu_priority_restore(pri);	260	cpu_priority_restore(pri);
220		261
221	}	262	}
222		263
-		264	/** Release reader/writer lock held by reader
-		265	*
-		266	* Release reader/writer lock held by reader.
-		267	* Handoff reader/writer lock ownership directly
-		268	* to a waiting writer or don't do anything if more
-		269	* readers poses the lock.
-		270	*
-		271	* @param rwl Reader/Writer lock.
-		272	*/
223	void rwlock_read_unlock(rwlock_t *rwl)	273	void rwlock_read_unlock(rwlock_t *rwl)
224	{	274	{
225	pri_t pri;	275	pri_t pri;
226		276
227	pri = cpu_priority_high();	277	pri = cpu_priority_high();
228	spinlock_lock(&rwl->lock);	278	spinlock_lock(&rwl->lock);
229	if (!--rwl->readers_in)	279	if (!--rwl->readers_in)
230	let_others_in(rwl, ALLOW_ALL);	280	let_others_in(rwl, ALLOW_ALL);
231	spinlock_unlock(&rwl->lock);	281	spinlock_unlock(&rwl->lock);
232	cpu_priority_restore(pri);	282	cpu_priority_restore(pri);
233	}	283	}
234		284
235		285
-		286	/** Direct handoff
236	/*	287	*
-		288	* Direct handoff of reader/writer lock ownership
-		289	* to waiting readers or a writer.
-		290	*
237	* Must be called with rwl->lock locked.	291	* Must be called with rwl->lock locked.
238	* Must be called with cpu_priority_high'ed.	292	* Must be called with cpu_priority_high'ed.
239	*/	293	*
-		294	* @param rwl Reader/Writer lock.
-		295	* @param readers_only See the description below.
240	/*	296	*
241	* If readers_only is false: (unlock scenario)	297	* If readers_only is false: (unlock scenario)
242	* Let the first sleeper on 'exclusive' mutex in, no matter	298	* Let the first sleeper on 'exclusive' mutex in, no matter
243	* whether it is a reader or a writer. If there are more leading	299	* whether it is a reader or a writer. If there are more leading
244	* readers in line, let each of them in.	300	* readers in line, let each of them in.
245	*	301	*
246	* Otherwise: (timeout scenario)	302	* Otherwise: (timeout scenario)
247	* Let all leading readers in.	303	* Let all leading readers in.
248	*/	304	*/
249	void let_others_in(rwlock_t *rwl, int readers_only)	305	void let_others_in(rwlock_t *rwl, int readers_only)
250	{	306	{
251	rwlock_type_t type = RWLOCK_NONE;	307	rwlock_type_t type = RWLOCK_NONE;
252	thread_t *t = NULL;	308	thread_t *t = NULL;
253	int one_more = 1;	309	int one_more = 1;
254		310
255	spinlock_lock(&rwl->exclusive.sem.wq.lock);	311	spinlock_lock(&rwl->exclusive.sem.wq.lock);
256		312
257	if (!list_empty(&rwl->exclusive.sem.wq.head))	313	if (!list_empty(&rwl->exclusive.sem.wq.head))
258	t = list_get_instance(rwl->exclusive.sem.wq.head.next, thread_t, wq_link);	314	t = list_get_instance(rwl->exclusive.sem.wq.head.next, thread_t, wq_link);
259	do {	315	do {
260	if (t) {	316	if (t) {
261	spinlock_lock(&t->lock);	317	spinlock_lock(&t->lock);
262	type = t->rwlock_holder_type;	318	type = t->rwlock_holder_type;
263	spinlock_unlock(&t->lock);	319	spinlock_unlock(&t->lock);
264	}	320	}
265		321
266	/*	322	/*
267	* If readers_only is true, we wake all leading readers	323	* If readers_only is true, we wake all leading readers
268	* if and only if rwl is locked by another reader.	324	* if and only if rwl is locked by another reader.
269	* Assumption: readers_only ==> rwl->readers_in	325	* Assumption: readers_only ==> rwl->readers_in
270	*/	326	*/
271	if (readers_only && (type != RWLOCK_READER))	327	if (readers_only && (type != RWLOCK_READER))
272	break;	328	break;
273		329
274		330
275	if (type == RWLOCK_READER) {	331	if (type == RWLOCK_READER) {
276	/*	332	/*
277	* Waking up a reader.	333	* Waking up a reader.
278	* We are responsible for incrementing rwl->readers_in for it.	334	* We are responsible for incrementing rwl->readers_in for it.
279	*/	335	*/
280	rwl->readers_in++;	336	rwl->readers_in++;
281	}	337	}
282		338
283	/*	339	/*
284	* Only the last iteration through this loop can increment	340	* Only the last iteration through this loop can increment
285	* rwl->exclusive.sem.wq.missed_wakeup's. All preceeding	341	* rwl->exclusive.sem.wq.missed_wakeup's. All preceeding
286	* iterations will wake up a thread.	342	* iterations will wake up a thread.
287	*/	343	*/
288	/* We call the internal version of waitq_wakeup, which	344	/* We call the internal version of waitq_wakeup, which
289	* relies on the fact that the waitq is already locked.	345	* relies on the fact that the waitq is already locked.
290	*/	346	*/
291	_waitq_wakeup_unsafe(&rwl->exclusive.sem.wq, WAKEUP_FIRST);	347	_waitq_wakeup_unsafe(&rwl->exclusive.sem.wq, WAKEUP_FIRST);
292		348
293	t = NULL;	349	t = NULL;
294	if (!list_empty(&rwl->exclusive.sem.wq.head)) {	350	if (!list_empty(&rwl->exclusive.sem.wq.head)) {
295	t = list_get_instance(rwl->exclusive.sem.wq.head.next, thread_t, wq_link);	351	t = list_get_instance(rwl->exclusive.sem.wq.head.next, thread_t, wq_link);
296	if (t) {	352	if (t) {
297	spinlock_lock(&t->lock);	353	spinlock_lock(&t->lock);
298	if (t->rwlock_holder_type != RWLOCK_READER)	354	if (t->rwlock_holder_type != RWLOCK_READER)
299	one_more = 0;	355	one_more = 0;
300	spinlock_unlock(&t->lock);	356	spinlock_unlock(&t->lock);
301	}	357	}
302	}	358	}
303	} while ((type == RWLOCK_READER) && t && one_more);	359	} while ((type == RWLOCK_READER) && t && one_more);
304		360
305	spinlock_unlock(&rwl->exclusive.sem.wq.lock);	361	spinlock_unlock(&rwl->exclusive.sem.wq.lock);
306	}	362	}
307		363
-		364	/** Release spinlock callback
-		365	*
-		366	* This is a callback function invoked from the scheduler.
-		367	* The callback is registered in _rwlock_read_lock_timeout().
-		368	*
-		369	* @param arg Spinlock.
-		370	*/
308	void release_spinlock(void *arg)	371	void release_spinlock(void *arg)
309	{	372	{
310	spinlock_unlock((spinlock_t *) arg);	373	spinlock_unlock((spinlock_t *) arg);
311	}	374	}
312		375

Subversion Repositories HelenOS

(root)/trunk/kernel/generic/src/synch/rwlock.c @ 2071 – Rev 153 → 385