Subversion Repositories HelenOS

Rev

Rev 3191 | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
1 jermar 1
/*
2071 jermar 2
 * Copyright (c) 2001-2004 Jakub Jermar
1 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
 
1757 jermar 29
/** @addtogroup sync
1702 cejka 30
 * @{
31
 */
32
 
1248 jermar 33
/**
1702 cejka 34
 * @file
1248 jermar 35
 * @brief   Reader/Writer locks.
557 jermar 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.
1248 jermar 39
 *
1 jermar 40
 * These locks are not recursive.
1757 jermar 41
 * Because a technique called direct hand-off is used and because
42
 * waiting takes place in a single wait queue, neither readers
1248 jermar 43
 * nor writers will suffer starvation.
1 jermar 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>
385 jermar 64
#include <synch/synch.h>
788 jermar 65
#include <adt/list.h>
1 jermar 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
 
74
static void let_others_in(rwlock_t *rwl, int readers_only);
75
static void release_spinlock(void *arg);
76
 
385 jermar 77
/** Initialize reader/writer lock
78
 *
79
 * Initialize reader/writer lock.
80
 *
81
 * @param rwl Reader/Writer lock.
82
 */
1 jermar 83
void rwlock_initialize(rwlock_t *rwl) {
557 jermar 84
    spinlock_initialize(&rwl->lock, "rwlock_t");
3191 svoboda 85
    mutex_initialize(&rwl->exclusive, MUTEX_PASSIVE);
1 jermar 86
    rwl->readers_in = 0;
87
}
88
 
385 jermar 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.
1502 jermar 96
 * @param flags Specify mode of operation.
385 jermar 97
 *
98
 * For exact description of possible combinations of
1502 jermar 99
 * usec and flags, see comment for waitq_sleep_timeout().
385 jermar 100
 *
101
 * @return See comment for waitq_sleep_timeout().
102
 */
1780 jermar 103
int _rwlock_write_lock_timeout(rwlock_t *rwl, uint32_t usec, int flags)
1 jermar 104
{
413 jermar 105
    ipl_t ipl;
1 jermar 106
    int rc;
107
 
413 jermar 108
    ipl = interrupts_disable();
15 jermar 109
    spinlock_lock(&THREAD->lock);
110
    THREAD->rwlock_holder_type = RWLOCK_WRITER;
111
    spinlock_unlock(&THREAD->lock);
413 jermar 112
    interrupts_restore(ipl);
1 jermar 113
 
114
    /*
115
     * Writers take the easy part.
116
     * They just need to acquire the exclusive mutex.
117
     */
1502 jermar 118
    rc = _mutex_lock_timeout(&rwl->exclusive, usec, flags);
1 jermar 119
    if (SYNCH_FAILED(rc)) {
120
 
121
        /*
1502 jermar 122
         * Lock operation timed out or was interrupted.
1 jermar 123
         * The state of rwl is UNKNOWN at this point.
124
         * No claims about its holder can be made.
125
         */
126
 
413 jermar 127
        ipl = interrupts_disable();
1 jermar 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);
413 jermar 137
        interrupts_restore(ipl);
1 jermar 138
    }
139
 
140
    return rc;
141
}
142
 
385 jermar 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.
1502 jermar 150
 * @param flags Select mode of operation.
385 jermar 151
 *
152
 * For exact description of possible combinations of
1502 jermar 153
 * usec and flags, see comment for waitq_sleep_timeout().
385 jermar 154
 *
155
 * @return See comment for waitq_sleep_timeout().
156
 */
1780 jermar 157
int _rwlock_read_lock_timeout(rwlock_t *rwl, uint32_t usec, int flags)
1 jermar 158
{
159
    int rc;
413 jermar 160
    ipl_t ipl;
1 jermar 161
 
413 jermar 162
    ipl = interrupts_disable();
15 jermar 163
    spinlock_lock(&THREAD->lock);
164
    THREAD->rwlock_holder_type = RWLOCK_READER;
165
    spinlock_unlock(&THREAD->lock);
1 jermar 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
         */
623 jermar 200
        #ifdef CONFIG_SMP
1 jermar 201
        thread_register_call_me(release_spinlock, &rwl->lock);
623 jermar 202
        #else
203
        thread_register_call_me(release_spinlock, NULL);
204
        #endif
1 jermar 205
 
1502 jermar 206
        rc = _mutex_lock_timeout(&rwl->exclusive, usec, flags);
1 jermar 207
        switch (rc) {
1888 jermar 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
            /*
2087 jermar 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.)
1888 jermar 230
             */
231
            interrupts_restore(ipl);
232
            break;
233
        case ESYNCH_OK_ATOMIC:
4339 svoboda 234
            panic("_mutex_lock_timeout() == ESYNCH_OK_ATOMIC.");
1888 jermar 235
            break;
236
        default:
4339 svoboda 237
            panic("Invalid ESYNCH.");
1888 jermar 238
            break;
1 jermar 239
        }
240
        return rc;
241
    }
242
 
243
shortcut:
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);
413 jermar 252
    interrupts_restore(ipl);
1 jermar 253
 
254
    return ESYNCH_OK_ATOMIC;
255
}
256
 
385 jermar 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
 */
1 jermar 265
void rwlock_write_unlock(rwlock_t *rwl)
266
{
413 jermar 267
    ipl_t ipl;
1 jermar 268
 
413 jermar 269
    ipl = interrupts_disable();
1 jermar 270
    spinlock_lock(&rwl->lock);
271
    let_others_in(rwl, ALLOW_ALL);
272
    spinlock_unlock(&rwl->lock);
413 jermar 273
    interrupts_restore(ipl);
1 jermar 274
 
275
}
276
 
385 jermar 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
 */
1 jermar 286
void rwlock_read_unlock(rwlock_t *rwl)
287
{
413 jermar 288
    ipl_t ipl;
1 jermar 289
 
413 jermar 290
    ipl = interrupts_disable();
1 jermar 291
    spinlock_lock(&rwl->lock);
292
    if (!--rwl->readers_in)
293
        let_others_in(rwl, ALLOW_ALL);
294
    spinlock_unlock(&rwl->lock);
413 jermar 295
    interrupts_restore(ipl);
1 jermar 296
}
297
 
298
 
557 jermar 299
/** Direct handoff of reader/writer lock ownership.
385 jermar 300
 *
301
 * Direct handoff of reader/writer lock ownership
302
 * to waiting readers or a writer.
303
 *
1 jermar 304
 * Must be called with rwl->lock locked.
413 jermar 305
 * Must be called with interrupts_disable()'d.
385 jermar 306
 *
307
 * @param rwl Reader/Writer lock.
308
 * @param readers_only See the description below.
309
 *
1 jermar 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
 */
318
void let_others_in(rwlock_t *rwl, int readers_only)
319
{
320
    rwlock_type_t type = RWLOCK_NONE;
321
    thread_t *t = NULL;
557 jermar 322
    bool one_more = true;
1 jermar 323
 
324
    spinlock_lock(&rwl->exclusive.sem.wq.lock);
325
 
326
    if (!list_empty(&rwl->exclusive.sem.wq.head))
2087 jermar 327
        t = list_get_instance(rwl->exclusive.sem.wq.head.next, thread_t,
328
            wq_link);
1 jermar 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.
2087 jermar 348
             * We are responsible for incrementing rwl->readers_in
349
             * for it.
1 jermar 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)) {
2087 jermar 366
            t = list_get_instance(rwl->exclusive.sem.wq.head.next,
367
                thread_t, wq_link);
1 jermar 368
            if (t) {
369
                spinlock_lock(&t->lock);
370
                if (t->rwlock_holder_type != RWLOCK_READER)
557 jermar 371
                    one_more = false;
1 jermar 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
 
385 jermar 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
 */
1 jermar 387
void release_spinlock(void *arg)
388
{
389
    spinlock_unlock((spinlock_t *) arg);
390
}
1702 cejka 391
 
1757 jermar 392
/** @}
1702 cejka 393
 */