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 |
} |