Subversion Repositories HelenOS-historic

Rev

Rev 625 | Rev 1248 | Go to most recent revision | Details | Compare with Previous | Last modification | View Log | RSS feed

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