source: mainline/kernel/generic/src/synch/rwlock.c@ 8ccd2ea

lfn serial ticket/834-toolchain-update topic/msim-upgrade topic/simplify-dev-export
Last change on this file since 8ccd2ea was b3f8fb7, checked in by Martin Decky <martin@…>, 18 years ago

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