Annotation of prex/sys/sync/mutex.c, Revision 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. 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.
! 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 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.
! 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 */
! 83: static int prio_inherit(thread_t th);
! 84: static void prio_uninherit(thread_t th);
! 85:
! 86: /*
! 87: * Initialize a mutex.
! 88: *
! 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.
! 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;
! 128: goto out;
! 129: }
! 130: if (!mutex_valid(m)) {
! 131: err = EINVAL;
! 132: goto out;
! 133: }
! 134: if (m->owner || event_waiting(&m->event)) {
! 135: err = EBUSY;
! 136: goto out;
! 137: }
! 138:
! 139: m->magic = 0;
! 140: kmem_free(m);
! 141: out:
! 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: /*
! 162: * Allocate new mutex, and retreive its id
! 163: * from the user space.
! 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: *
! 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 *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: */
! 200: m->locks++;
! 201: ASSERT(m->locks != 0);
! 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: }
! 226: m->locks = 1;
! 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)
! 248: m->locks++;
! 249: else {
! 250: if (m->owner != NULL)
! 251: err = EBUSY;
! 252: else {
! 253: m->locks = 1;
! 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;
! 276: if (m->owner != cur_thread || m->locks <= 0) {
! 277: err = EPERM;
! 278: goto out;
! 279: }
! 280: if (--m->locks == 0) {
! 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: *
! 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.
! 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);
! 325: m->locks = 0;
! 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;
! 334: m->locks = 1;
! 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: *
! 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.
! 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) {
! 377: DPRINTF(("Deadlock! mutex=%x owner=%x waiter=%x\n",
! 378: m, owner, waiter));
! 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) {
! 387: sched_setprio(owner, owner->baseprio, waiter->prio);
! 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: *
! 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.
! 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. */
! 421: if (th->prio == th->baseprio)
! 422: return;
! 423:
! 424: top_prio = th->baseprio;
! 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: }
! 436: sched_setprio(th, th->baseprio, top_prio);
! 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 / sys / sync