Subversion Repositories HelenOS

Rev

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