Prex Home / Browse Source - Prex Version: 0.9.0

root/sys/sync/mutex.c

DEFINITIONS

1. mutex_init
2. mutex_deallocate
3. mutex_destroy
4. mutex_cleanup
5. mutex_lock
6. mutex_trylock
7. mutex_unlock
8. mutex_cancel
9. mutex_setpri
10. mutex_valid
11. mutex_copyin
12. prio_inherit
13. prio_uninherit

   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  */
  30 /*
  31  * mutex.c - mutual exclusion service.
  32  */
  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  */
  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>
  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);
  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
mutex_init(mutex_t *mp)
  95 {
task_t self = curtask;
mutex_t m;
  99         if (self->nsyncs >= MAXSYNCS)
 100                 return EAGAIN;
 102         if ((m = kmem_alloc(sizeof(struct mutex))) == NULL)
 103                 return ENOMEM;
event_init(&m->event, "mutex");
m->owner = self;
m->holder = NULL;
m->priority = MINPRI;
 110         if (copyout(&m, mp, sizeof(m))) {
kmem_free(m);
 112                 return EFAULT;
 113         }
sched_lock();
list_insert(&self->mutexes, &m->task_link);
self->nsyncs++;
sched_unlock();
 119         return 0;
 120 }
 122 /*
 123  * Internal version of mutex_destroy.
 124  */
 125 static void
mutex_deallocate(mutex_t m)
 127 {
m->owner->nsyncs--;
list_remove(&m->task_link);
kmem_free(m);
 132 }
 134 /*
 135  * Destroy the specified mutex.
 136  * The mutex must be unlock state, otherwise it fails with EBUSY.
 137  */
 138 int
mutex_destroy(mutex_t *mp)
 140 {
mutex_t m;
sched_lock();
 144         if (copyin(mp, &m, sizeof(mp))) {
sched_unlock();
 146                 return EFAULT;
 147         }
 148         if (!mutex_valid(m)) {
sched_unlock();
 150                 return EINVAL;
 151         }
 152         if (m->holder || event_waiting(&m->event)) {
sched_unlock();
 154                 return EBUSY;
 155         }
mutex_deallocate(m);
sched_unlock();
 158         return 0;
 159 }
 161 /*
 162  * Clean up for task termination.
 163  */
 164 void
mutex_cleanup(task_t task)
 166 {
mutex_t m;
 169         while (!list_empty(&task->mutexes)) {
m = list_entry(list_first(&task->mutexes),
 171                                struct mutex, task_link);
mutex_deallocate(m);
 173         }
 174 }
 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
mutex_lock(mutex_t *mp)
 188 {
mutex_t m;
 190         int error, rc;
sched_lock();
 193         if ((error = mutex_copyin(mp, &m)) != 0) {
sched_unlock();
 195                 return error;
 196         }
 198         if (m->holder == curthread) {
 199                 /*
 200                  * Recursive lock
 201                  */
m->locks++;
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)
m->priority = curthread->priority;
 212                 else {
 213                         /*
 214                          * Wait for a mutex.
 215                          */
curthread->mutex_waiting = m;
 217                         if ((error = prio_inherit(curthread)) != 0) {
curthread->mutex_waiting = NULL;
sched_unlock();
 220                                 return error;
 221                         }
rc = sched_sleep(&m->event);
curthread->mutex_waiting = NULL;
 224                         if (rc == SLP_INTR) {
sched_unlock();
 226                                 return EINTR;
 227                         }
 228                 }
m->locks = 1;
m->holder = curthread;
list_insert(&curthread->mutexes, &m->link);
 232         }
sched_unlock();
 234         return 0;
 235 }
 237 /*
 238  * Try to lock a mutex without blocking.
 239  */
 240 int
mutex_trylock(mutex_t *mp)
 242 {
mutex_t m;
 244         int error;
sched_lock();
 247         if ((error = mutex_copyin(mp, &m)) != 0) {
sched_unlock();
 249                 return error;
 250         }
 252         if (m->holder == curthread) {
m->locks++;
ASSERT(m->locks != 0);
 255         } else {
 256                 if (m->holder != NULL)
error = EBUSY;
 258                 else {
m->locks = 1;
m->holder = curthread;
list_insert(&curthread->mutexes, &m->link);
 262                 }
 263         }
sched_unlock();
 265         return error;
 266 }
 268 /*
 269  * Unlock a mutex.
 270  * Caller must be a current mutex holder.
 271  */
 272 int
mutex_unlock(mutex_t *mp)
 274 {
mutex_t m;
 276         int error;
sched_lock();
 279         if ((error = mutex_copyin(mp, &m)) != 0) {
sched_unlock();
 281                 return error;
 282         }
 284         if (m->holder != curthread || m->locks <= 0) {
sched_unlock();
 286                 return EPERM;
 287         }
 288         if (--m->locks == 0) {
list_remove(&m->link);
prio_uninherit(curthread);
 291                 /*
 292                  * Change the mutex holder, and make the next
 293                  * holder runnable if it exists.
 294                  */
m->holder = sched_wakeone(&m->event);
 296                 if (m->holder)
m->holder->mutex_waiting = NULL;
m->priority = m->holder ? m->holder->priority : MINPRI;
 300         }
sched_unlock();
 302         return 0;
 303 }
 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
mutex_cancel(thread_t t)
 317 {
list_t head;
mutex_t m;
thread_t holder;
 322         /*
 323          * Purge all mutexes held by the thread.
 324          */
head = &t->mutexes;
 326         while (!list_empty(head)) {
 327                 /*
 328                  * Release locked mutex.
 329                  */
m = list_entry(list_first(head), struct mutex, link);
m->locks = 0;
list_remove(&m->link);
 334                 /*
 335                  * Change the mutex holder if other thread
 336                  * is waiting for it.
 337                  */
holder = sched_wakeone(&m->event);
 339                 if (holder) {
holder->mutex_waiting = NULL;
m->locks = 1;
list_insert(&holder->mutexes, &m->link);
 343                 }
m->holder = holder;
 345         }
 346 }
 348 /*
 349  * This is called with scheduling locked before thread priority
 350  * is changed.
 351  */
 352 void
mutex_setpri(thread_t t, int pri)
 354 {
 356         if (t->mutex_waiting && pri < t->priority)
prio_inherit(t);
 358 }
 360 /*
 361  * Check if the specified mutex is valid.
 362  */
 363 static int
mutex_valid(mutex_t m)
 365 {
mutex_t tmp;
list_t head, n;
head = &curtask->mutexes;
 370         for (n = list_first(head); n != head; n = list_next(n)) {
tmp = list_entry(n, struct mutex, task_link);
 372                 if (tmp == m)
 373                         return 1;
 374         }
 375         return 0;
 376 }
 378 /*
 379  * Copy mutex from user space.
 380  * If it is not initialized, create new mutex.
 381  */
 382 static int
mutex_copyin(mutex_t *ump, mutex_t *kmp)
 384 {
mutex_t m;
 386         int error;
 388         if (copyin(ump, &m, sizeof(ump)))
 389                 return EFAULT;
 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;
copyin(ump, &m, sizeof(ump));
 399         } else {
 400                 if (!mutex_valid(m))
 401                         return EINVAL;
 402         }
 403         *kmp = m;
 404         return 0;
 405 }
 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
prio_inherit(thread_t waiter)
 419 {
mutex_t m = waiter->mutex_waiting;
thread_t holder;
 422         int count = 0;
 424         do {
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) {
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) {
sched_setpri(holder, holder->basepri, waiter->priority);
m->priority = waiter->priority;
 444                 }
 445                 /*
 446                  * If the mutex holder is waiting for another
 447                  * mutex, that mutex is also processed.
 448                  */
m = (mutex_t)holder->mutex_waiting;
 451                 /* Fail safe... */
ASSERT(count < MAXINHERIT);
 453                 if (count >= MAXINHERIT)
 454                         break;
 456         } while (m != NULL);
 457         return 0;
 458 }
 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
prio_uninherit(thread_t t)
 470 {
 471         int maxpri;
list_t head, n;
mutex_t m;
 475         /* Check if the priority is inherited. */
 476         if (t->priority == t->basepri)
 477                 return;
maxpri = t->basepri;
 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          */
head = &t->mutexes;
 487         for (n = list_first(head); n != head; n = list_next(n)) {
m = list_entry(n, struct mutex, link);
 489                 if (m->priority < maxpri)
maxpri = m->priority;
 491         }
sched_setpri(t, t->basepri, maxpri);
 494 }