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

Subversion Repositories HelenOS-historic

(root)/kernel/trunk/generic/src/synch/rwlock.c – Rev 552 → 557