Statistics
| Branch: | Revision:

scoutos / prex-0.9.0 / sys / sync / mutex.c @ 03e9c04a

History | View | Annotate | Download (11.2 KB)

1
/*-
2
 * Copyright (c) 2005-2007, Kohsuke Ohtani
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
 * 1. Redistributions of source code must retain the above copyright
9
 *    notice, this list of conditions and the following disclaimer.
10
 * 2. Redistributions in binary form must reproduce the above copyright
11
 *    notice, this list of conditions and the following disclaimer in the
12
 *    documentation and/or other materials provided with the distribution.
13
 * 3. Neither the name of the author nor the names of any co-contributors
14
 *    may be used to endorse or promote products derived from this software
15
 *    without specific prior written permission.
16
 *
17
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
18
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
21
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
27
 * SUCH DAMAGE.
28
 */
29

    
30
/*
31
 * mutex.c - mutual exclusion service.
32
 */
33

    
34
/*
35
 * A mutex is used to protect un-sharable resources. A thread can use
36
 * mutex_lock() to ensure that global resource is not accessed by
37
 * other thread. The mutex is effective only the threads belonging to
38
 * the same task.
39
 *
40
 * Prex will change the thread priority to prevent priority inversion.
41
 *
42
 * <Priority inheritance>
43
 *   The priority is changed at the following conditions.
44
 *
45
 *   1. When the current thread can not lock the mutex and its
46
 *      mutex holder has lower priority than current thread, the
47
 *      priority of mutex holder is boosted to same priority with
48
 *      current thread.  If this mutex holder is waiting for another
49
 *      mutex, such related mutexes are also processed.
50
 *
51
 *   2. When the current thread unlocks the mutex and its priority
52
 *      has already been inherited, the current priority is reset.
53
 *      In this time, the current priority is changed to the highest
54
 *      priority among the threads waiting for the mutexes locked by
55
 *      current thread.
56
 *
57
 *   3. When the thread priority is changed by user request, the
58
 *      inherited thread's priority is changed.
59
 *
60
 * <Limitation>
61
 *
62
 *   1. If the priority is changed by user request, the priority
63
 *      recomputation is done only when the new priority is higher
64
 *      than old priority. The inherited priority is reset to base
65
 *      priority when the mutex is unlocked.
66
 *
67
 *   2. Even if thread is killed with mutex waiting, the related
68
 *      priority is not adjusted.
69
 */
70

    
71
#include <kernel.h>
72
#include <event.h>
73
#include <sched.h>
74
#include <kmem.h>
75
#include <thread.h>
76
#include <task.h>
77
#include <sync.h>
78

    
79
/* forward declarations */
80
static int        mutex_valid(mutex_t);
81
static int        mutex_copyin(mutex_t *, mutex_t *);
82
static int        prio_inherit(thread_t);
83
static void        prio_uninherit(thread_t);
84

    
85
/*
86
 * Initialize a mutex.
87
 *
88
 * If an initialized mutex is reinitialized, undefined
89
 * behavior results. Technically, we can not detect such
90
 * error condition here because we can not touch the passed
91
 * object in kernel.
92
 */
93
int
94
mutex_init(mutex_t *mp)
95
{
96
        task_t self = curtask;
97
        mutex_t m;
98

    
99
        if (self->nsyncs >= MAXSYNCS)
100
                return EAGAIN;
101

    
102
        if ((m = kmem_alloc(sizeof(struct mutex))) == NULL)
103
                return ENOMEM;
104

    
105
        event_init(&m->event, "mutex");
106
        m->owner = self;
107
        m->holder = NULL;
108
        m->priority = MINPRI;
109

    
110
        if (copyout(&m, mp, sizeof(m))) {
111
                kmem_free(m);
112
                return EFAULT;
113
        }
114

    
115
        sched_lock();
116
        list_insert(&self->mutexes, &m->task_link);
117
        self->nsyncs++;
118
        sched_unlock();
119
        return 0;
120
}
121

    
122
/*
123
 * Internal version of mutex_destroy.
124
 */
125
static void
126
mutex_deallocate(mutex_t m)
127
{
128

    
129
        m->owner->nsyncs--;
130
        list_remove(&m->task_link);
131
        kmem_free(m);
132
}
133

    
134
/*
135
 * Destroy the specified mutex.
136
 * The mutex must be unlock state, otherwise it fails with EBUSY.
137
 */
138
int
139
mutex_destroy(mutex_t *mp)
140
{
141
        mutex_t m;
142

    
143
        sched_lock();
144
        if (copyin(mp, &m, sizeof(mp))) {
145
                sched_unlock();
146
                return EFAULT;
147
        }
148
        if (!mutex_valid(m)) {
149
                sched_unlock();
150
                return EINVAL;
151
        }
152
        if (m->holder || event_waiting(&m->event)) {
153
                sched_unlock();
154
                return EBUSY;
155
        }
156
        mutex_deallocate(m);
157
        sched_unlock();
158
        return 0;
159
}
160

    
161
/*
162
 * Clean up for task termination.
163
 */
164
void
165
mutex_cleanup(task_t task)
166
{
167
        mutex_t m;
168

    
169
        while (!list_empty(&task->mutexes)) {
170
                m = list_entry(list_first(&task->mutexes),
171
                               struct mutex, task_link);
172
                mutex_deallocate(m);
173
        }
174
}
175

    
176
/*
177
 * Lock a mutex.
178
 *
179
 * A current thread is blocked if the mutex has already been
180
 * locked. If current thread receives any exception while
181
 * waiting mutex, this routine returns with EINTR in order to
182
 * invoke exception handler. But, POSIX thread assumes this
183
 * function does NOT return with EINTR.  So, system call stub
184
 * routine in library must call this again if it gets EINTR.
185
 */
186
int
187
mutex_lock(mutex_t *mp)
188
{
189
        mutex_t m;
190
        int error, rc;
191

    
192
        sched_lock();
193
        if ((error = mutex_copyin(mp, &m)) != 0) {
194
                sched_unlock();
195
                return error;
196
        }
197

    
198
        if (m->holder == curthread) {
199
                /*
200
                 * Recursive lock
201
                 */
202
                m->locks++;
203
                ASSERT(m->locks != 0);
204
        } else {
205
                /*
206
                 * Check whether a target mutex is locked.
207
                 * If the mutex is not locked, this routine
208
                 * returns immediately.
209
                 */
210
                if (m->holder == NULL)
211
                        m->priority = curthread->priority;
212
                else {
213
                        /*
214
                         * Wait for a mutex.
215
                         */
216
                        curthread->mutex_waiting = m;
217
                        if ((error = prio_inherit(curthread)) != 0) {
218
                                curthread->mutex_waiting = NULL;
219
                                sched_unlock();
220
                                return error;
221
                        }
222
                        rc = sched_sleep(&m->event);
223
                        curthread->mutex_waiting = NULL;
224
                        if (rc == SLP_INTR) {
225
                                sched_unlock();
226
                                return EINTR;
227
                        }
228
                }
229
                m->locks = 1;
230
                m->holder = curthread;
231
                list_insert(&curthread->mutexes, &m->link);
232
        }
233
        sched_unlock();
234
        return 0;
235
}
236

    
237
/*
238
 * Try to lock a mutex without blocking.
239
 */
240
int
241
mutex_trylock(mutex_t *mp)
242
{
243
        mutex_t m;
244
        int error;
245

    
246
        sched_lock();
247
        if ((error = mutex_copyin(mp, &m)) != 0) {
248
                sched_unlock();
249
                return error;
250
        }
251

    
252
        if (m->holder == curthread) {
253
                m->locks++;
254
                ASSERT(m->locks != 0);
255
        } else {
256
                if (m->holder != NULL)
257
                        error = EBUSY;
258
                else {
259
                        m->locks = 1;
260
                        m->holder = curthread;
261
                        list_insert(&curthread->mutexes, &m->link);
262
                }
263
        }
264
        sched_unlock();
265
        return error;
266
}
267

    
268
/*
269
 * Unlock a mutex.
270
 * Caller must be a current mutex holder.
271
 */
272
int
273
mutex_unlock(mutex_t *mp)
274
{
275
        mutex_t m;
276
        int error;
277

    
278
        sched_lock();
279
        if ((error = mutex_copyin(mp, &m)) != 0) {
280
                sched_unlock();
281
                return error;
282
        }
283

    
284
        if (m->holder != curthread || m->locks <= 0) {
285
                sched_unlock();
286
                return EPERM;
287
        }
288
        if (--m->locks == 0) {
289
                list_remove(&m->link);
290
                prio_uninherit(curthread);
291
                /*
292
                 * Change the mutex holder, and make the next
293
                 * holder runnable if it exists.
294
                 */
295
                m->holder = sched_wakeone(&m->event);
296
                if (m->holder)
297
                        m->holder->mutex_waiting = NULL;
298

    
299
                m->priority = m->holder ? m->holder->priority : MINPRI;
300
        }
301
        sched_unlock();
302
        return 0;
303
}
304

    
305
/*
306
 * Cancel mutex operations.
307
 *
308
 * This is called with scheduling locked when thread is
309
 * terminated. If a thread is terminated with mutex hold, all
310
 * waiting threads keeps waiting forever. So, all mutex locked by
311
 * terminated thread must be unlocked. Even if the terminated
312
 * thread is waiting some mutex, the inherited priority of other
313
 * mutex holder is not adjusted.
314
 */
315
void
316
mutex_cancel(thread_t t)
317
{
318
        list_t head;
319
        mutex_t m;
320
        thread_t holder;
321

    
322
        /*
323
         * Purge all mutexes held by the thread.
324
         */
325
        head = &t->mutexes;
326
        while (!list_empty(head)) {
327
                /*
328
                 * Release locked mutex.
329
                 */
330
                m = list_entry(list_first(head), struct mutex, link);
331
                m->locks = 0;
332
                list_remove(&m->link);
333

    
334
                /*
335
                 * Change the mutex holder if other thread
336
                 * is waiting for it.
337
                 */
338
                holder = sched_wakeone(&m->event);
339
                if (holder) {
340
                        holder->mutex_waiting = NULL;
341
                        m->locks = 1;
342
                        list_insert(&holder->mutexes, &m->link);
343
                }
344
                m->holder = holder;
345
        }
346
}
347

    
348
/*
349
 * This is called with scheduling locked before thread priority
350
 * is changed.
351
 */
352
void
353
mutex_setpri(thread_t t, int pri)
354
{
355

    
356
        if (t->mutex_waiting && pri < t->priority)
357
                prio_inherit(t);
358
}
359

    
360
/*
361
 * Check if the specified mutex is valid.
362
 */
363
static int
364
mutex_valid(mutex_t m)
365
{
366
        mutex_t tmp;
367
        list_t head, n;
368

    
369
        head = &curtask->mutexes;
370
        for (n = list_first(head); n != head; n = list_next(n)) {
371
                tmp = list_entry(n, struct mutex, task_link);
372
                if (tmp == m)
373
                        return 1;
374
        }
375
        return 0;
376
}
377

    
378
/*
379
 * Copy mutex from user space.
380
 * If it is not initialized, create new mutex.
381
 */
382
static int
383
mutex_copyin(mutex_t *ump, mutex_t *kmp)
384
{
385
        mutex_t m;
386
        int error;
387

    
388
        if (copyin(ump, &m, sizeof(ump)))
389
                return EFAULT;
390

    
391
        if (m == MUTEX_INITIALIZER) {
392
                /*
393
                 * Allocate new mutex, and retreive its id
394
                 * from the user space.
395
                 */
396
                if ((error = mutex_init(ump)) != 0)
397
                        return error;
398
                copyin(ump, &m, sizeof(ump));
399
        } else {
400
                if (!mutex_valid(m))
401
                        return EINVAL;
402
        }
403
        *kmp = m;
404
        return 0;
405
}
406

    
407
/*
408
 * Inherit priority.
409
 *
410
 * To prevent priority inversion, we must ensure the higher
411
 * priority thread does not wait other lower priority thread. So,
412
 * raise the priority of mutex holder which blocks the "waiter"
413
 * thread. If such mutex holder is also waiting for other mutex,
414
 * that mutex is also processed. Returns EDEALK if it finds
415
 * deadlock condition.
416
 */
417
static int
418
prio_inherit(thread_t waiter)
419
{
420
        mutex_t m = waiter->mutex_waiting;
421
        thread_t holder;
422
        int count = 0;
423

    
424
        do {
425
                holder = m->holder;
426
                /*
427
                 * If the holder of relative mutex has already
428
                 * been waiting for the "waiter" thread, it
429
                 * causes a deadlock.
430
                 */
431
                if (holder == waiter) {
432
                        DPRINTF(("Deadlock! mutex=%lx holder=%lx waiter=%lx\n",
433
                                 (long)m, (long)holder, (long)waiter));
434
                        return EDEADLK;
435
                }
436
                /*
437
                 * If the priority of the mutex holder is lower
438
                 * than "waiter" thread's, we rise the mutex
439
                 * holder's priority.
440
                 */
441
                if (holder->priority > waiter->priority) {
442
                        sched_setpri(holder, holder->basepri, waiter->priority);
443
                        m->priority = waiter->priority;
444
                }
445
                /*
446
                 * If the mutex holder is waiting for another
447
                 * mutex, that mutex is also processed.
448
                 */
449
                m = (mutex_t)holder->mutex_waiting;
450

    
451
                /* Fail safe... */
452
                ASSERT(count < MAXINHERIT);
453
                if (count >= MAXINHERIT)
454
                        break;
455

    
456
        } while (m != NULL);
457
        return 0;
458
}
459

    
460
/*
461
 * Un-inherit priority
462
 *
463
 * The priority of specified thread is reset to the base
464
 * priority.  If specified thread locks other mutex and higher
465
 * priority thread is waiting for it, the priority is kept to
466
 * that level.
467
 */
468
static void
469
prio_uninherit(thread_t t)
470
{
471
        int maxpri;
472
        list_t head, n;
473
        mutex_t m;
474

    
475
        /* Check if the priority is inherited. */
476
        if (t->priority == t->basepri)
477
                return;
478

    
479
        maxpri = t->basepri;
480

    
481
        /*
482
         * Find the highest priority thread that is waiting
483
         * for the thread. This is done by checking all mutexes
484
         * that the thread locks.
485
         */
486
        head = &t->mutexes;
487
        for (n = list_first(head); n != head; n = list_next(n)) {
488
                m = list_entry(n, struct mutex, link);
489
                if (m->priority < maxpri)
490
                        maxpri = m->priority;
491
        }
492

    
493
        sched_setpri(t, t->basepri, maxpri);
494
}