Annotation of prex-old/sys/sync/mutex.c, Revision 1.1.1.1.2.1
1.1 nbrk 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: /*
1.1.1.1.2.1! nbrk 35: * A mutex is used to protect un-sharable resources. A thread
! 36: * can use mutex_lock() to ensure that global resource is not
! 37: * accessed by other thread. The mutex is effective only the
! 38: * threads belonging to the same task.
1.1 nbrk 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: *
1.1.1.1.2.1! nbrk 45: * 1. When the current thread can not lock the mutex and its
! 46: * mutex owner has lower priority than current thread, the
! 47: * priority of mutex owner is boosted to same priority with
! 48: * current thread. If this mutex owner is waiting for another
! 49: * mutex, such related mutexes are also processed.
1.1 nbrk 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: /* max mutex count to inherit priority */
80: #define MAXINHERIT 10
81:
82: /* forward declarations */
1.1.1.1.2.1! nbrk 83: static int prio_inherit(thread_t th);
! 84: static void prio_uninherit(thread_t th);
1.1 nbrk 85:
86: /*
87: * Initialize a mutex.
88: *
1.1.1.1.2.1! nbrk 89: * If an initialized mutex is reinitialized, undefined
! 90: * behavior results. Technically, we can not detect such
! 91: * error condition here because we can not touch the passed
! 92: * object in kernel.
1.1 nbrk 93: */
94: int
95: mutex_init(mutex_t *mtx)
96: {
97: mutex_t m;
98:
99: if ((m = kmem_alloc(sizeof(struct mutex))) == NULL)
100: return ENOMEM;
101:
102: event_init(&m->event, "mutex");
103: m->task = cur_task();
104: m->owner = NULL;
105: m->prio = MIN_PRIO;
106: m->magic = MUTEX_MAGIC;
107:
108: if (umem_copyout(&m, mtx, sizeof(mutex_t))) {
109: kmem_free(m);
110: return EFAULT;
111: }
112: return 0;
113: }
114:
115: /*
116: * Destroy the specified mutex.
117: * The mutex must be unlock state, otherwise it fails with EBUSY.
118: */
119: int
120: mutex_destroy(mutex_t *mtx)
121: {
122: mutex_t m;
123: int err = 0;
124:
125: sched_lock();
126: if (umem_copyin(mtx, &m, sizeof(mutex_t))) {
127: err = EFAULT;
1.1.1.1.2.1! nbrk 128: goto out;
! 129: }
! 130: if (!mutex_valid(m)) {
1.1 nbrk 131: err = EINVAL;
1.1.1.1.2.1! nbrk 132: goto out;
! 133: }
! 134: if (m->owner || event_waiting(&m->event)) {
1.1 nbrk 135: err = EBUSY;
1.1.1.1.2.1! nbrk 136: goto out;
1.1 nbrk 137: }
1.1.1.1.2.1! nbrk 138:
! 139: m->magic = 0;
! 140: kmem_free(m);
! 141: out:
1.1 nbrk 142: sched_unlock();
143: ASSERT(err == 0);
144: return err;
145: }
146:
147: /*
148: * Copy mutex from user space.
149: * If it is not initialized, create new mutex.
150: */
151: static int
152: mutex_copyin(mutex_t *umtx, mutex_t *kmtx)
153: {
154: mutex_t m;
155: int err;
156:
157: if (umem_copyin(umtx, &m, sizeof(mutex_t)))
158: return EFAULT;
159:
160: if (m == MUTEX_INITIALIZER) {
161: /*
1.1.1.1.2.1! nbrk 162: * Allocate new mutex, and retreive its id
! 163: * from the user space.
1.1 nbrk 164: */
165: if ((err = mutex_init(umtx)))
166: return err;
167: umem_copyin(umtx, &m, sizeof(mutex_t));
168: } else {
169: if (!mutex_valid(m))
170: return EINVAL;
171: }
172: *kmtx = m;
173: return 0;
174: }
175:
176: /*
177: * Lock a mutex.
178: *
1.1.1.1.2.1! nbrk 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.
1.1 nbrk 185: */
186: int
187: mutex_lock(mutex_t *mtx)
188: {
189: mutex_t m;
190: int rc, err;
191:
192: sched_lock();
193: if ((err = mutex_copyin(mtx, &m)))
194: goto out;
195:
196: if (m->owner == cur_thread) {
197: /*
198: * Recursive lock
199: */
1.1.1.1.2.1! nbrk 200: m->locks++;
! 201: ASSERT(m->locks != 0);
1.1 nbrk 202: } else {
203: /*
204: * Check whether a target mutex is locked.
205: * If the mutex is not locked, this routine
206: * returns immediately.
207: */
208: if (m->owner == NULL)
209: m->prio = cur_thread->prio;
210: else {
211: /*
212: * Wait for a mutex.
213: */
214: cur_thread->wait_mutex = m;
215: if ((err = prio_inherit(cur_thread))) {
216: cur_thread->wait_mutex = NULL;
217: goto out;
218: }
219: rc = sched_sleep(&m->event);
220: cur_thread->wait_mutex = NULL;
221: if (rc == SLP_INTR) {
222: err = EINTR;
223: goto out;
224: }
225: }
1.1.1.1.2.1! nbrk 226: m->locks = 1;
1.1 nbrk 227: }
228: m->owner = cur_thread;
229: list_insert(&cur_thread->mutexes, &m->link);
230: out:
231: sched_unlock();
232: return err;
233: }
234:
235: /*
236: * Try to lock a mutex without blocking.
237: */
238: int
239: mutex_trylock(mutex_t *mtx)
240: {
241: mutex_t m;
242: int err;
243:
244: sched_lock();
245: if ((err = mutex_copyin(mtx, &m)))
246: goto out;
247: if (m->owner == cur_thread)
1.1.1.1.2.1! nbrk 248: m->locks++;
1.1 nbrk 249: else {
250: if (m->owner != NULL)
251: err = EBUSY;
252: else {
1.1.1.1.2.1! nbrk 253: m->locks = 1;
1.1 nbrk 254: m->owner = cur_thread;
255: list_insert(&cur_thread->mutexes, &m->link);
256: }
257: }
258: out:
259: sched_unlock();
260: return err;
261: }
262:
263: /*
264: * Unlock a mutex.
265: * Caller must be a current mutex owner.
266: */
267: int
268: mutex_unlock(mutex_t *mtx)
269: {
270: mutex_t m;
271: int err;
272:
273: sched_lock();
274: if ((err = mutex_copyin(mtx, &m)))
275: goto out;
1.1.1.1.2.1! nbrk 276: if (m->owner != cur_thread || m->locks <= 0) {
1.1 nbrk 277: err = EPERM;
278: goto out;
279: }
1.1.1.1.2.1! nbrk 280: if (--m->locks == 0) {
1.1 nbrk 281: list_remove(&m->link);
282: prio_uninherit(cur_thread);
283: /*
284: * Change the mutex owner, and make the next
285: * owner runnable if it exists.
286: */
287: m->owner = sched_wakeone(&m->event);
288: if (m->owner)
289: m->owner->wait_mutex = NULL;
290:
291: m->prio = m->owner ? m->owner->prio : MIN_PRIO;
292: }
293: out:
294: sched_unlock();
295: ASSERT(err == 0);
296: return err;
297: }
298:
299: /*
300: * Clean up mutex.
301: *
1.1.1.1.2.1! nbrk 302: * This is called with scheduling locked when thread is
! 303: * terminated. If a thread is terminated with mutex hold, all
! 304: * waiting threads keeps waiting forever. So, all mutex locked by
! 305: * terminated thread must be unlocked. Even if the terminated
! 306: * thread is waiting some mutex, the inherited priority of other
! 307: * mutex owner is not adjusted.
1.1 nbrk 308: */
309: void
310: mutex_cleanup(thread_t th)
311: {
312: list_t head;
313: mutex_t m;
314: thread_t owner;
315:
316: /*
317: * Purge all mutexes held by the thread.
318: */
319: head = &th->mutexes;
320: while (!list_empty(head)) {
321: /*
322: * Release locked mutex.
323: */
324: m = list_entry(list_first(head), struct mutex, link);
1.1.1.1.2.1! nbrk 325: m->locks = 0;
1.1 nbrk 326: list_remove(&m->link);
327: /*
328: * Change the mutex owner if other thread
329: * is waiting for it.
330: */
331: owner = sched_wakeone(&m->event);
332: if (owner) {
333: owner->wait_mutex = NULL;
1.1.1.1.2.1! nbrk 334: m->locks = 1;
1.1 nbrk 335: list_insert(&owner->mutexes, &m->link);
336: }
337: m->owner = owner;
338: }
339: }
340:
341: /*
342: * This is called with scheduling locked before thread priority
343: * is changed.
344: */
345: void
346: mutex_setprio(thread_t th, int prio)
347: {
348: if (th->wait_mutex && prio < th->prio)
349: prio_inherit(th);
350: }
351:
352: /*
353: * Inherit priority.
354: *
1.1.1.1.2.1! nbrk 355: * To prevent priority inversion, we must ensure the higher
! 356: * priority thread does not wait other lower priority thread. So,
! 357: * raise the priority of mutex owner which blocks the "waiter"
! 358: * thread. If such mutex owner is also waiting for other mutex,
! 359: * that mutex is also processed. Returns EDEALK if it finds
! 360: * deadlock condition.
1.1 nbrk 361: */
362: static int
363: prio_inherit(thread_t waiter)
364: {
365: mutex_t m = waiter->wait_mutex;
366: thread_t owner;
367: int count = 0;
368:
369: do {
370: owner = m->owner;
371: /*
372: * If the owner of relative mutex has already
373: * been waiting for the "waiter" thread, it
374: * causes a deadlock.
375: */
376: if (owner == waiter) {
1.1.1.1.2.1! nbrk 377: DPRINTF(("Deadlock! mutex=%x owner=%x waiter=%x\n",
! 378: m, owner, waiter));
1.1 nbrk 379: return EDEADLK;
380: }
381: /*
382: * If the priority of the mutex owner is lower
383: * than "waiter" thread's, we rise the mutex
384: * owner's priority.
385: */
386: if (owner->prio > waiter->prio) {
1.1.1.1.2.1! nbrk 387: sched_setprio(owner, owner->baseprio, waiter->prio);
1.1 nbrk 388: m->prio = waiter->prio;
389: }
390: /*
391: * If the mutex owner is waiting for another
392: * mutex, that mutex is also processed.
393: */
394: m = (mutex_t)owner->wait_mutex;
395:
396: /* Fail safe... */
397: ASSERT(count < MAXINHERIT);
398: if (count >= MAXINHERIT)
399: break;
400:
401: } while (m != NULL);
402: return 0;
403: }
404:
405: /*
406: * Un-inherit priority
407: *
1.1.1.1.2.1! nbrk 408: * The priority of specified thread is reset to the base
! 409: * priority. If specified thread locks other mutex and higher
! 410: * priority thread is waiting for it, the priority is kept to
! 411: * that level.
1.1 nbrk 412: */
413: static void
414: prio_uninherit(thread_t th)
415: {
416: int top_prio;
417: list_t head, n;
418: mutex_t m;
419:
420: /* Check if the priority is inherited. */
1.1.1.1.2.1! nbrk 421: if (th->prio == th->baseprio)
1.1 nbrk 422: return;
423:
1.1.1.1.2.1! nbrk 424: top_prio = th->baseprio;
1.1 nbrk 425: /*
426: * Find the highest priority thread that is waiting
427: * for the thread. This is done by checking all mutexes
428: * that the thread locks.
429: */
430: head = &th->mutexes;
431: for (n = list_first(head); n != head; n = list_next(n)) {
432: m = list_entry(n, struct mutex, link);
433: if (m->prio < top_prio)
434: top_prio = m->prio;
435: }
1.1.1.1.2.1! nbrk 436: sched_setprio(th, th->baseprio, top_prio);
1.1 nbrk 437: }
CVSweb
![[BACK]](/icons/back.gif){kind=icon}
Return to mutex.c CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [local] / prex-old / sys / sync