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