root / prex-0.9.0 / sys / sync / mutex.c @ 03e9c04a
History | View | Annotate | Download (11.2 KB)
1 | 03e9c04a | Brad Neuman | /*-
|
---|---|---|---|
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 | } |