Annotation of prex-old/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.
! 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