lib/libthread_xu/thread/thr_mutex.c

   1 /*
   2  * Copyright (c) 1995 John Birrell <jb@cimlogic.com.au>.
   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. All advertising materials mentioning features or use of this software
  14  *    must display the following acknowledgement:
  15  *      This product includes software developed by John Birrell.
  16  * 4. Neither the name of the author nor the names of any co-contributors
  17  *    may be used to endorse or promote products derived from this software
  18  *    without specific prior written permission.
  19  *
  20  * THIS SOFTWARE IS PROVIDED BY JOHN BIRRELL AND CONTRIBUTORS ``AS IS'' AND
  21  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  22  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  23  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  24  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  25  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  26  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  27  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  28  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  29  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  30  * SUCH DAMAGE.
  31  *
  32  * $FreeBSD: src/lib/libpthread/thread/thr_mutex.c,v 1.46 2004/10/31 05:03:50 green Exp $
  33  * $DragonFly: src/lib/libthread_xu/thread/thr_mutex.c,v 1.4 2005/04/05 23:04:22 davidxu Exp $
  34  */
  35
  36 #include <machine/tls.h>
  37
  38 #include <stdlib.h>
  39 #include <errno.h>
  40 #include <string.h>
  41 #include <sys/param.h>
  42 #include <sys/queue.h>
  43 #include <pthread.h>
  44 #include "thr_private.h"
  45
  46 #if defined(_PTHREADS_INVARIANTS)
  47 #define MUTEX_INIT_LINK(m)              do {            \
  48         (m)->m_qe.tqe_prev = NULL;                      \
  49         (m)->m_qe.tqe_next = NULL;                      \
  50 } while (0)
  51 #define MUTEX_ASSERT_IS_OWNED(m)        do {            \
  52         if ((m)->m_qe.tqe_prev == NULL)                 \
  53                 PANIC("mutex is not on list");          \
  54 } while (0)
  55 #define MUTEX_ASSERT_NOT_OWNED(m)       do {            \
  56         if (((m)->m_qe.tqe_prev != NULL) ||             \
  57             ((m)->m_qe.tqe_next != NULL))               \
  58                 PANIC("mutex is on list");              \
  59 } while (0)
  60 #define THR_ASSERT_NOT_IN_SYNCQ(thr)    do {            \
  61         THR_ASSERT(((thr)->sflags & THR_FLAGS_IN_SYNCQ) == 0, \
  62             "thread in syncq when it shouldn't be.");   \
  63 } while (0);
  64 #else
  65 #define MUTEX_INIT_LINK(m)
  66 #define MUTEX_ASSERT_IS_OWNED(m)
  67 #define MUTEX_ASSERT_NOT_OWNED(m)
  68 #define THR_ASSERT_NOT_IN_SYNCQ(thr)
  69 #endif
  70
  71 #define THR_IN_MUTEXQ(thr)      (((thr)->sflags & THR_FLAGS_IN_SYNCQ) != 0)
  72 #define MUTEX_DESTROY(m) do {           \
  73         free(m);                        \
  74 } while (0)
  75
  76
  77 /*
  78  * Prototypes
  79  */
  80 static long             mutex_handoff(struct pthread *, struct pthread_mutex *);
  81 static int              mutex_self_trylock(struct pthread *, pthread_mutex_t);
  82 static int              mutex_self_lock(struct pthread *, pthread_mutex_t,
  83                                 const struct timespec *abstime);
  84 static int              mutex_unlock_common(pthread_mutex_t *, int);
  85 static void             mutex_priority_adjust(struct pthread *, pthread_mutex_t);
  86 static void             mutex_rescan_owned (struct pthread *, struct pthread *,
  87                             struct pthread_mutex *);
  88 #if 0
  89 static pthread_t        mutex_queue_deq(pthread_mutex_t);
  90 #endif
  91 static void             mutex_queue_remove(pthread_mutex_t, pthread_t);
  92 static void             mutex_queue_enq(pthread_mutex_t, pthread_t);
  93
  94 __weak_reference(__pthread_mutex_init, pthread_mutex_init);
  95 __weak_reference(__pthread_mutex_lock, pthread_mutex_lock);
  96 __weak_reference(__pthread_mutex_timedlock, pthread_mutex_timedlock);
  97 __weak_reference(__pthread_mutex_trylock, pthread_mutex_trylock);
  98
  99 /* Single underscore versions provided for libc internal usage: */
 100 /* No difference between libc and application usage of these: */
 101 __weak_reference(_pthread_mutex_destroy, pthread_mutex_destroy);
 102 __weak_reference(_pthread_mutex_unlock, pthread_mutex_unlock);
 103
 104 static int
 105 mutex_init(pthread_mutex_t *mutex,
 106     const pthread_mutexattr_t *mutex_attr, int private)
 107 {
 108         struct pthread_mutex *pmutex;
 109         enum pthread_mutextype type;
 110         int             protocol;
 111         int             ceiling;
 112         int             flags;
 113         int             ret = 0;
 114
 115         /* Check if default mutex attributes: */
 116         if (mutex_attr == NULL || *mutex_attr == NULL) {
 117                 /* Default to a (error checking) POSIX mutex: */
 118                 type = PTHREAD_MUTEX_ERRORCHECK;
 119                 protocol = PTHREAD_PRIO_NONE;
 120                 ceiling = THR_MAX_PRIORITY;
 121                 flags = 0;
 122         }
 123
 124         /* Check mutex type: */
 125         else if (((*mutex_attr)->m_type < PTHREAD_MUTEX_ERRORCHECK) ||
 126             ((*mutex_attr)->m_type >= MUTEX_TYPE_MAX))
 127                 /* Return an invalid argument error: */
 128                 ret = EINVAL;
 129
 130         /* Check mutex protocol: */
 131         else if (((*mutex_attr)->m_protocol < PTHREAD_PRIO_NONE) ||
 132             ((*mutex_attr)->m_protocol > PTHREAD_PRIO_PROTECT))
 133                 /* Return an invalid argument error: */
 134                 ret = EINVAL;
 135
 136         else {
 137                 /* Use the requested mutex type and protocol: */
 138                 type = (*mutex_attr)->m_type;
 139                 protocol = (*mutex_attr)->m_protocol;
 140                 ceiling = (*mutex_attr)->m_ceiling;
 141                 flags = (*mutex_attr)->m_flags;
 142         }
 143
 144         /* Check no errors so far: */
 145         if (ret == 0) {
 146                 if ((pmutex = (pthread_mutex_t)
 147                     malloc(sizeof(struct pthread_mutex))) == NULL) {
 148                         ret = ENOMEM;
 149                 } else {
 150                         _thr_umtx_init(&pmutex->m_lock);
 151                         /* Set the mutex flags: */
 152                         pmutex->m_flags = flags;
 153
 154                         /* Process according to mutex type: */
 155                         switch (type) {
 156                         /* case PTHREAD_MUTEX_DEFAULT: */
 157                         case PTHREAD_MUTEX_ERRORCHECK:
 158                         case PTHREAD_MUTEX_NORMAL:
 159                                 /* Nothing to do here. */
 160                                 break;
 161
 162                         /* Single UNIX Spec 2 recursive mutex: */
 163                         case PTHREAD_MUTEX_RECURSIVE:
 164                                 /* Reset the mutex count: */
 165                                 pmutex->m_count = 0;
 166                                 break;
 167
 168                         /* Trap invalid mutex types: */
 169                         default:
 170                                 /* Return an invalid argument error: */
 171                                 ret = EINVAL;
 172                                 break;
 173                         }
 174                         if (ret == 0) {
 175                                 /* Initialise the rest of the mutex: */
 176                                 TAILQ_INIT(&pmutex->m_queue);
 177                                 pmutex->m_flags |= MUTEX_FLAGS_INITED;
 178                                 if (private)
 179                                         pmutex->m_flags |= MUTEX_FLAGS_PRIVATE;
 180                                 pmutex->m_owner = NULL;
 181                                 pmutex->m_type = type;
 182                                 pmutex->m_protocol = protocol;
 183                                 pmutex->m_refcount = 0;
 184                                 if (protocol == PTHREAD_PRIO_PROTECT)
 185                                         pmutex->m_prio = ceiling;
 186                                 else
 187                                         pmutex->m_prio = -1;
 188                                 pmutex->m_saved_prio = 0;
 189                                 MUTEX_INIT_LINK(pmutex);
 190                                 *mutex = pmutex;
 191                         } else {
 192                                 /* Free the mutex lock structure: */
 193                                 MUTEX_DESTROY(pmutex);
 194                                 *mutex = NULL;
 195                         }
 196                 }
 197         }
 198         /* Return the completion status: */
 199         return (ret);
 200 }
 201
 202 static int
 203 init_static(struct pthread *thread, pthread_mutex_t *mutex)
 204 {
 205         int ret;
 206
 207         THR_LOCK_ACQUIRE(thread, &_mutex_static_lock);
 208
 209         if (*mutex == NULL)
 210                 ret = mutex_init(mutex, NULL, 0);
 211         else
 212                 ret = 0;
 213
 214         THR_LOCK_RELEASE(thread, &_mutex_static_lock);
 215
 216         return (ret);
 217 }
 218
 219 static int
 220 init_static_private(struct pthread *thread, pthread_mutex_t *mutex)
 221 {
 222         int ret;
 223
 224         THR_LOCK_ACQUIRE(thread, &_mutex_static_lock);
 225
 226         if (*mutex == NULL)
 227                 ret = mutex_init(mutex, NULL, 1);
 228         else
 229                 ret = 0;
 230
 231         THR_LOCK_RELEASE(thread, &_mutex_static_lock);
 232
 233         return (ret);
 234 }
 235
 236 int
 237 _pthread_mutex_init(pthread_mutex_t *mutex,
 238     const pthread_mutexattr_t *mutex_attr)
 239 {
 240         return mutex_init(mutex, mutex_attr, 1);
 241 }
 242
 243 int
 244 __pthread_mutex_init(pthread_mutex_t *mutex,
 245     const pthread_mutexattr_t *mutex_attr)
 246 {
 247         return mutex_init(mutex, mutex_attr, 0);
 248 }
 249
 250 int
 251 _mutex_reinit(pthread_mutex_t *mutex)
 252 {
 253         _thr_umtx_init(&(*mutex)->m_lock);
 254         TAILQ_INIT(&(*mutex)->m_queue);
 255         MUTEX_INIT_LINK(*mutex);
 256         (*mutex)->m_owner = NULL;
 257         (*mutex)->m_count = 0;
 258         (*mutex)->m_refcount = 0;
 259         (*mutex)->m_prio = 0;
 260         (*mutex)->m_saved_prio = 0;
 261         return (0);
 262 }
 263
 264 void
 265 _mutex_fork(struct pthread *curthread)
 266 {
 267         struct pthread_mutex *m;
 268
 269         TAILQ_FOREACH(m, &curthread->mutexq, m_qe)
 270                 m->m_lock = UMTX_LOCKED;
 271
 272         /* Clear contender for priority mutexes */
 273         TAILQ_FOREACH(m, &curthread->pri_mutexq, m_qe) {
 274                 /* clear another thread locked us */
 275                 _thr_umtx_init(&m->m_lock);
 276                 TAILQ_INIT(&m->m_queue);
 277         }
 278 }
 279
 280 int
 281 _pthread_mutex_destroy(pthread_mutex_t *mutex)
 282 {
 283         struct pthread *curthread = tls_get_curthread();
 284         pthread_mutex_t m;
 285         int ret = 0;
 286
 287         if (mutex == NULL || *mutex == NULL)
 288                 ret = EINVAL;
 289         else {
 290                 /*
 291                  * Try to lock the mutex structure, we only need to
 292                  * try once, if failed, the mutex is in used.
 293                  */
 294                 ret = THR_UMTX_TRYLOCK(curthread, &(*mutex)->m_lock);
 295                 if (ret)
 296                         return (ret);
 297
 298                 /*
 299                  * Check mutex other fields to see if this mutex is
 300                  * in use. Mostly for prority mutex types, or there
 301                  * are condition variables referencing it.
 302                  */
 303                 if (((*mutex)->m_owner != NULL) ||
 304                     (TAILQ_FIRST(&(*mutex)->m_queue) != NULL) ||
 305                     ((*mutex)->m_refcount != 0)) {
 306                         THR_UMTX_UNLOCK(curthread, &(*mutex)->m_lock);
 307                         ret = EBUSY;
 308                 } else {
 309                         /*
 310                          * Save a pointer to the mutex so it can be free'd
 311                          * and set the caller's pointer to NULL:
 312                          */
 313                         m = *mutex;
 314                         *mutex = NULL;
 315
 316                         /* Unlock the mutex structure: */
 317                         _thr_umtx_unlock(&m->m_lock, curthread->tid);
 318
 319                         /*
 320                          * Free the memory allocated for the mutex
 321                          * structure:
 322                          */
 323                         MUTEX_ASSERT_NOT_OWNED(m);
 324                         MUTEX_DESTROY(m);
 325                 }
 326         }
 327
 328         /* Return the completion status: */
 329         return (ret);
 330 }
 331
 332 static int
 333 mutex_trylock_common(struct pthread *curthread, pthread_mutex_t *mutex)
 334 {
 335         int ret = 0;
 336
 337         THR_ASSERT((mutex != NULL) && (*mutex != NULL),
 338             "Uninitialized mutex in mutex_trylock_common");
 339
 340         /* Short cut for simple mutex. */
 341         if ((*mutex)->m_protocol == PTHREAD_PRIO_NONE) {
 342                 ret = THR_UMTX_TRYLOCK(curthread, &(*mutex)->m_lock);
 343                 if (ret == 0) {
 344                         (*mutex)->m_owner = curthread;
 345                         /* Add to the list of owned mutexes: */
 346                         MUTEX_ASSERT_NOT_OWNED(*mutex);
 347                         TAILQ_INSERT_TAIL(&curthread->mutexq,
 348                             (*mutex), m_qe);
 349                 } else if ((*mutex)->m_owner == curthread) {
 350                         ret = mutex_self_trylock(curthread, *mutex);
 351                 } /* else {} */
 352
 353                 return (ret);
 354         }
 355
 356         /* Code for priority mutex */
 357
 358         /* Lock the mutex structure: */
 359         THR_LOCK_ACQUIRE(curthread, &(*mutex)->m_lock);
 360
 361         /*
 362          * If the mutex was statically allocated, properly
 363          * initialize the tail queue.
 364          */
 365         if (((*mutex)->m_flags & MUTEX_FLAGS_INITED) == 0) {
 366                 TAILQ_INIT(&(*mutex)->m_queue);
 367                 MUTEX_INIT_LINK(*mutex);
 368                 (*mutex)->m_flags |= MUTEX_FLAGS_INITED;
 369         }
 370
 371         /* Process according to mutex type: */
 372         switch ((*mutex)->m_protocol) {
 373         /* POSIX priority inheritence mutex: */
 374         case PTHREAD_PRIO_INHERIT:
 375                 /* Check if this mutex is not locked: */
 376                 if ((*mutex)->m_owner == NULL) {
 377                         /* Lock the mutex for the running thread: */
 378                         (*mutex)->m_owner = curthread;
 379
 380                         THR_LOCK(curthread);
 381                         /* Track number of priority mutexes owned: */
 382                         curthread->priority_mutex_count++;
 383
 384                         /*
 385                          * The mutex takes on the attributes of the
 386                          * running thread when there are no waiters.
 387                          */
 388                         (*mutex)->m_prio = curthread->active_priority;
 389                         (*mutex)->m_saved_prio =
 390                             curthread->inherited_priority;
 391                         curthread->inherited_priority = (*mutex)->m_prio;
 392                         THR_UNLOCK(curthread);
 393
 394                         /* Add to the list of owned mutexes: */
 395                         MUTEX_ASSERT_NOT_OWNED(*mutex);
 396                         TAILQ_INSERT_TAIL(&curthread->pri_mutexq,
 397                             (*mutex), m_qe);
 398                 } else if ((*mutex)->m_owner == curthread)
 399                         ret = mutex_self_trylock(curthread, *mutex);
 400                 else
 401                         /* Return a busy error: */
 402                         ret = EBUSY;
 403                 break;
 404
 405         /* POSIX priority protection mutex: */
 406         case PTHREAD_PRIO_PROTECT:
 407                 /* Check for a priority ceiling violation: */
 408                 if (curthread->active_priority > (*mutex)->m_prio)
 409                         ret = EINVAL;
 410
 411                 /* Check if this mutex is not locked: */
 412                 else if ((*mutex)->m_owner == NULL) {
 413                         /* Lock the mutex for the running thread: */
 414                         (*mutex)->m_owner = curthread;
 415
 416                         THR_LOCK(curthread);
 417                         /* Track number of priority mutexes owned: */
 418                         curthread->priority_mutex_count++;
 419
 420                         /*
 421                          * The running thread inherits the ceiling
 422                          * priority of the mutex and executes at that
 423                          * priority.
 424                          */
 425                         curthread->active_priority = (*mutex)->m_prio;
 426                         (*mutex)->m_saved_prio =
 427                             curthread->inherited_priority;
 428                         curthread->inherited_priority =
 429                             (*mutex)->m_prio;
 430                         THR_UNLOCK(curthread);
 431                         /* Add to the list of owned mutexes: */
 432                         MUTEX_ASSERT_NOT_OWNED(*mutex);
 433                         TAILQ_INSERT_TAIL(&curthread->pri_mutexq,
 434                             (*mutex), m_qe);
 435                 } else if ((*mutex)->m_owner == curthread)
 436                         ret = mutex_self_trylock(curthread, *mutex);
 437                 else
 438                         /* Return a busy error: */
 439                         ret = EBUSY;
 440                 break;
 441
 442         /* Trap invalid mutex types: */
 443         default:
 444                 /* Return an invalid argument error: */
 445                 ret = EINVAL;
 446                 break;
 447         }
 448
 449         /* Unlock the mutex structure: */
 450         THR_LOCK_RELEASE(curthread, &(*mutex)->m_lock);
 451
 452         /* Return the completion status: */
 453         return (ret);
 454 }
 455
 456 int
 457 __pthread_mutex_trylock(pthread_mutex_t *mutex)
 458 {
 459         struct pthread *curthread = tls_get_curthread();
 460         int ret = 0;
 461
 462         /*
 463          * If the mutex is statically initialized, perform the dynamic
 464          * initialization:
 465          */
 466         if ((*mutex != NULL) ||
 467             ((ret = init_static(curthread, mutex)) == 0))
 468                 ret = mutex_trylock_common(curthread, mutex);
 469
 470         return (ret);
 471 }
 472
 473 int
 474 _pthread_mutex_trylock(pthread_mutex_t *mutex)
 475 {
 476         struct pthread  *curthread = tls_get_curthread();
 477         int     ret = 0;
 478
 479         /*
 480          * If the mutex is statically initialized, perform the dynamic
 481          * initialization marking the mutex private (delete safe):
 482          */
 483         if ((*mutex != NULL) ||
 484             ((ret = init_static_private(curthread, mutex)) == 0))
 485                 ret = mutex_trylock_common(curthread, mutex);
 486
 487         return (ret);
 488 }
 489
 490 static int
 491 mutex_lock_common(struct pthread *curthread, pthread_mutex_t *m,
 492         const struct timespec * abstime)
 493 {
 494         struct  timespec ts, ts2;
 495         long    cycle;
 496         int     ret = 0;
 497
 498         THR_ASSERT((m != NULL) && (*m != NULL),
 499             "Uninitialized mutex in mutex_lock_common");
 500
 501         if (abstime != NULL && (abstime->tv_sec < 0 || abstime->tv_nsec < 0 ||
 502             abstime->tv_nsec >= 1000000000))
 503                 return (EINVAL);
 504
 505         /* Short cut for simple mutex. */
 506
 507         if ((*m)->m_protocol == PTHREAD_PRIO_NONE) {
 508                 /* Default POSIX mutex: */
 509                 ret = THR_UMTX_TRYLOCK(curthread, &(*m)->m_lock);
 510                 if (ret == 0) {
 511                         (*m)->m_owner = curthread;
 512                         /* Add to the list of owned mutexes: */
 513                         MUTEX_ASSERT_NOT_OWNED(*m);
 514                         TAILQ_INSERT_TAIL(&curthread->mutexq,
 515                             (*m), m_qe);
 516                 } else if ((*m)->m_owner == curthread) {
 517                         ret = mutex_self_lock(curthread, *m, abstime);
 518                 } else {
 519                         if (abstime == NULL) {
 520                                 THR_UMTX_LOCK(curthread, &(*m)->m_lock);
 521                                 ret = 0;
 522                         } else {
 523                                 clock_gettime(CLOCK_REALTIME, &ts);
 524                                 TIMESPEC_SUB(&ts2, abstime, &ts);
 525                                 ret = THR_UMTX_TIMEDLOCK(curthread,
 526                                         &(*m)->m_lock, &ts2);
 527                                 /*
 528                                  * Timed out wait is not restarted if
 529                                  * it was interrupted, not worth to do it.
 530                                  */
 531                                 if (ret == EINTR)
 532                                         ret = ETIMEDOUT;
 533                         }
 534                         if (ret == 0) {
 535                                 (*m)->m_owner = curthread;
 536                                 /* Add to the list of owned mutexes: */
 537                                 MUTEX_ASSERT_NOT_OWNED(*m);
 538                                 TAILQ_INSERT_TAIL(&curthread->mutexq,
 539                                     (*m), m_qe);
 540                         }
 541                 }
 542                 return (ret);
 543         }
 544
 545         /* Code for priority mutex */
 546
 547         /*
 548          * Enter a loop waiting to become the mutex owner.  We need a
 549          * loop in case the waiting thread is interrupted by a signal
 550          * to execute a signal handler.  It is not (currently) possible
 551          * to remain in the waiting queue while running a handler.
 552          * Instead, the thread is interrupted and backed out of the
 553          * waiting queue prior to executing the signal handler.
 554          */
 555         do {
 556                 /* Lock the mutex structure: */
 557                 THR_LOCK_ACQUIRE(curthread, &(*m)->m_lock);
 558
 559                 /*
 560                  * If the mutex was statically allocated, properly
 561                  * initialize the tail queue.
 562                  */
 563                 if (((*m)->m_flags & MUTEX_FLAGS_INITED) == 0) {
 564                         TAILQ_INIT(&(*m)->m_queue);
 565                         (*m)->m_flags |= MUTEX_FLAGS_INITED;
 566                         MUTEX_INIT_LINK(*m);
 567                 }
 568
 569                 /* Process according to mutex type: */
 570                 switch ((*m)->m_protocol) {
 571                 /* POSIX priority inheritence mutex: */
 572                 case PTHREAD_PRIO_INHERIT:
 573                         /* Check if this mutex is not locked: */
 574                         if ((*m)->m_owner == NULL) {
 575                                 /* Lock the mutex for this thread: */
 576                                 (*m)->m_owner = curthread;
 577
 578                                 THR_LOCK(curthread);
 579                                 /* Track number of priority mutexes owned: */
 580                                 curthread->priority_mutex_count++;
 581
 582                                 /*
 583                                  * The mutex takes on attributes of the
 584                                  * running thread when there are no waiters.
 585                                  * Make sure the thread's scheduling lock is
 586                                  * held while priorities are adjusted.
 587                                  */
 588                                 (*m)->m_prio = curthread->active_priority;
 589                                 (*m)->m_saved_prio =
 590                                     curthread->inherited_priority;
 591                                 curthread->inherited_priority = (*m)->m_prio;
 592                                 THR_UNLOCK(curthread);
 593
 594                                 /* Add to the list of owned mutexes: */
 595                                 MUTEX_ASSERT_NOT_OWNED(*m);
 596                                 TAILQ_INSERT_TAIL(&curthread->pri_mutexq,
 597                                     (*m), m_qe);
 598
 599                                 /* Unlock the mutex structure: */
 600                                 THR_LOCK_RELEASE(curthread, &(*m)->m_lock);
 601                         } else if ((*m)->m_owner == curthread) {
 602                                 ret = mutex_self_lock(curthread, *m, abstime);
 603
 604                                 /* Unlock the mutex structure: */
 605                                 THR_LOCK_RELEASE(curthread, &(*m)->m_lock);
 606                         } else {
 607                                 /*
 608                                  * Join the queue of threads waiting to lock
 609                                  * the mutex and save a pointer to the mutex.
 610                                  */
 611                                 mutex_queue_enq(*m, curthread);
 612                                 curthread->data.mutex = *m;
 613
 614                                 if (curthread->active_priority > (*m)->m_prio)
 615                                         /* Adjust priorities: */
 616                                         mutex_priority_adjust(curthread, *m);
 617
 618                                 THR_LOCK(curthread);
 619                                 cycle = curthread->cycle;
 620                                 THR_UNLOCK(curthread);
 621
 622                                 /* Unlock the mutex structure: */
 623                                 THR_LOCK_RELEASE(curthread, &(*m)->m_lock);
 624
 625                                 clock_gettime(CLOCK_REALTIME, &ts);
 626                                 TIMESPEC_SUB(&ts2, abstime, &ts);
 627                                 ret = _thr_umtx_wait(&curthread->cycle, cycle,
 628                                          &ts2, CLOCK_REALTIME);
 629                                 if (ret == EINTR)
 630                                         ret = 0;
 631
 632                                 if (THR_IN_MUTEXQ(curthread)) {
 633                                         THR_LOCK_ACQUIRE(curthread, &(*m)->m_lock);
 634                                         mutex_queue_remove(*m, curthread);
 635                                         THR_LOCK_RELEASE(curthread, &(*m)->m_lock);
 636                                 }
 637                                 /*
 638                                  * Only clear these after assuring the
 639                                  * thread is dequeued.
 640                                  */
 641                                 curthread->data.mutex = NULL;
 642                         }
 643                         break;
 644
 645                 /* POSIX priority protection mutex: */
 646                 case PTHREAD_PRIO_PROTECT:
 647                         /* Check for a priority ceiling violation: */
 648                         if (curthread->active_priority > (*m)->m_prio) {
 649                                 /* Unlock the mutex structure: */
 650                                 THR_LOCK_RELEASE(curthread, &(*m)->m_lock);
 651                                 ret = EINVAL;
 652                         }
 653                         /* Check if this mutex is not locked: */
 654                         else if ((*m)->m_owner == NULL) {
 655                                 /*
 656                                  * Lock the mutex for the running
 657                                  * thread:
 658                                  */
 659                                 (*m)->m_owner = curthread;
 660
 661                                 THR_LOCK(curthread);
 662                                 /* Track number of priority mutexes owned: */
 663                                 curthread->priority_mutex_count++;
 664
 665                                 /*
 666                                  * The running thread inherits the ceiling
 667                                  * priority of the mutex and executes at that
 668                                  * priority.  Make sure the thread's
 669                                  * scheduling lock is held while priorities
 670                                  * are adjusted.
 671                                  */
 672                                 curthread->active_priority = (*m)->m_prio;
 673                                 (*m)->m_saved_prio =
 674                                     curthread->inherited_priority;
 675                                 curthread->inherited_priority = (*m)->m_prio;
 676                                 THR_UNLOCK(curthread);
 677
 678                                 /* Add to the list of owned mutexes: */
 679                                 MUTEX_ASSERT_NOT_OWNED(*m);
 680                                 TAILQ_INSERT_TAIL(&curthread->pri_mutexq,
 681                                     (*m), m_qe);
 682
 683                                 /* Unlock the mutex structure: */
 684                                 THR_LOCK_RELEASE(curthread, &(*m)->m_lock);
 685                         } else if ((*m)->m_owner == curthread) {
 686                                 ret = mutex_self_lock(curthread, *m, abstime);
 687
 688                                 /* Unlock the mutex structure: */
 689                                 THR_LOCK_RELEASE(curthread, &(*m)->m_lock);
 690                         } else {
 691                                 /*
 692                                  * Join the queue of threads waiting to lock
 693                                  * the mutex and save a pointer to the mutex.
 694                                  */
 695                                 mutex_queue_enq(*m, curthread);
 696                                 curthread->data.mutex = *m;
 697
 698                                 /* Clear any previous error: */
 699                                 curthread->error = 0;
 700
 701                                 THR_LOCK(curthread);
 702                                 cycle = curthread->cycle;
 703                                 THR_UNLOCK(curthread);
 704
 705                                 /* Unlock the mutex structure: */
 706                                 THR_LOCK_RELEASE(curthread, &(*m)->m_lock);
 707
 708                                 clock_gettime(CLOCK_REALTIME, &ts);
 709                                 TIMESPEC_SUB(&ts2, abstime, &ts);
 710                                 ret = _thr_umtx_wait(&curthread->cycle, cycle,
 711                                         &ts2, CLOCK_REALTIME);
 712                                 if (ret == EINTR)
 713                                         ret = 0;
 714
 715                                 curthread->data.mutex = NULL;
 716                                 if (THR_IN_MUTEXQ(curthread)) {
 717                                         THR_LOCK_ACQUIRE(curthread, &(*m)->m_lock);
 718                                         mutex_queue_remove(*m, curthread);
 719                                         THR_LOCK_RELEASE(curthread, &(*m)->m_lock);
 720                                 }
 721                                 /*
 722                                  * Only clear these after assuring the
 723                                  * thread is dequeued.
 724                                  */
 725                                 curthread->data.mutex = NULL;
 726
 727                                 /*
 728                                  * The threads priority may have changed while
 729                                  * waiting for the mutex causing a ceiling
 730                                  * violation.
 731                                  */
 732                                 ret = curthread->error;
 733                                 curthread->error = 0;
 734                         }
 735                         break;
 736
 737                 /* Trap invalid mutex types: */
 738                 default:
 739                         /* Unlock the mutex structure: */
 740                         THR_LOCK_RELEASE(curthread, &(*m)->m_lock);
 741
 742                         /* Return an invalid argument error: */
 743                         ret = EINVAL;
 744                         break;
 745                 }
 746
 747         } while (((*m)->m_owner != curthread) && (ret == 0));
 748
 749         /* Return the completion status: */
 750         return (ret);
 751 }
 752
 753 int
 754 __pthread_mutex_lock(pthread_mutex_t *m)
 755 {
 756         struct pthread *curthread;
 757         int     ret = 0;
 758
 759         _thr_check_init();
 760
 761         curthread = tls_get_curthread();
 762
 763         /*
 764          * If the mutex is statically initialized, perform the dynamic
 765          * initialization:
 766          */
 767         if ((*m != NULL) || ((ret = init_static(curthread, m)) == 0))
 768                 ret = mutex_lock_common(curthread, m, NULL);
 769
 770         return (ret);
 771 }
 772
 773 int
 774 _pthread_mutex_lock(pthread_mutex_t *m)
 775 {
 776         struct pthread *curthread;
 777         int     ret = 0;
 778
 779         _thr_check_init();
 780
 781         curthread = tls_get_curthread();
 782
 783         /*
 784          * If the mutex is statically initialized, perform the dynamic
 785          * initialization marking it private (delete safe):
 786          */
 787         if ((*m != NULL) ||
 788             ((ret = init_static_private(curthread, m)) == 0))
 789                 ret = mutex_lock_common(curthread, m, NULL);
 790
 791         return (ret);
 792 }
 793
 794 int
 795 __pthread_mutex_timedlock(pthread_mutex_t *m,
 796         const struct timespec *abs_timeout)
 797 {
 798         struct pthread *curthread;
 799         int     ret = 0;
 800
 801         _thr_check_init();
 802
 803         curthread = tls_get_curthread();
 804
 805         /*
 806          * If the mutex is statically initialized, perform the dynamic
 807          * initialization:
 808          */
 809         if ((*m != NULL) || ((ret = init_static(curthread, m)) == 0))
 810                 ret = mutex_lock_common(curthread, m, abs_timeout);
 811
 812         return (ret);
 813 }
 814
 815 int
 816 _pthread_mutex_timedlock(pthread_mutex_t *m,
 817         const struct timespec *abs_timeout)
 818 {
 819         struct pthread *curthread;
 820         int     ret = 0;
 821
 822         _thr_check_init();
 823
 824         curthread = tls_get_curthread();
 825
 826         /*
 827          * If the mutex is statically initialized, perform the dynamic
 828          * initialization marking it private (delete safe):
 829          */
 830         if ((*m != NULL) ||
 831             ((ret = init_static_private(curthread, m)) == 0))
 832                 ret = mutex_lock_common(curthread, m, abs_timeout);
 833
 834         return (ret);
 835 }
 836
 837 int
 838 _pthread_mutex_unlock(pthread_mutex_t *m)
 839 {
 840         return (mutex_unlock_common(m, /* add reference */ 0));
 841 }
 842
 843 int
 844 _mutex_cv_unlock(pthread_mutex_t *m)
 845 {
 846         return (mutex_unlock_common(m, /* add reference */ 1));
 847 }
 848
 849 int
 850 _mutex_cv_lock(pthread_mutex_t *m)
 851 {
 852         struct  pthread *curthread;
 853         int     ret;
 854
 855         curthread = tls_get_curthread();
 856         if ((ret = _pthread_mutex_lock(m)) == 0)
 857                 (*m)->m_refcount--;
 858         return (ret);
 859 }
 860
 861 static int
 862 mutex_self_trylock(struct pthread *curthread, pthread_mutex_t m)
 863 {
 864         int     ret;
 865
 866         switch (m->m_type) {
 867         /* case PTHREAD_MUTEX_DEFAULT: */
 868         case PTHREAD_MUTEX_ERRORCHECK:
 869         case PTHREAD_MUTEX_NORMAL:
 870                 ret = EBUSY;
 871                 break;
 872
 873         case PTHREAD_MUTEX_RECURSIVE:
 874                 /* Increment the lock count: */
 875                 if (m->m_count + 1 > 0) {
 876                         m->m_count++;
 877                         ret = 0;
 878                 } else
 879                         ret = EAGAIN;
 880                 break;
 881
 882         default:
 883                 /* Trap invalid mutex types; */
 884                 ret = EINVAL;
 885         }
 886
 887         return (ret);
 888 }
 889
 890 static int
 891 mutex_self_lock(struct pthread *curthread, pthread_mutex_t m,
 892         const struct timespec *abstime)
 893 {
 894         struct timespec ts1, ts2;
 895         int ret;
 896
 897         switch (m->m_type) {
 898         /* case PTHREAD_MUTEX_DEFAULT: */
 899         case PTHREAD_MUTEX_ERRORCHECK:
 900                 if (abstime) {
 901                         clock_gettime(CLOCK_REALTIME, &ts1);
 902                         TIMESPEC_SUB(&ts2, abstime, &ts1);
 903                         __sys_nanosleep(&ts2, NULL);
 904                         ret = ETIMEDOUT;
 905                 } else {
 906                         /*
 907                          * POSIX specifies that mutexes should return
 908                          * EDEADLK if a recursive lock is detected.
 909                          */
 910                         ret = EDEADLK;
 911                 }
 912                 break;
 913
 914         case PTHREAD_MUTEX_NORMAL:
 915                 /*
 916                  * What SS2 define as a 'normal' mutex.  Intentionally
 917                  * deadlock on attempts to get a lock you already own.
 918                  */
 919                 ret = 0;
 920                 if (m->m_protocol != PTHREAD_PRIO_NONE) {
 921                         /* Unlock the mutex structure: */
 922                         THR_LOCK_RELEASE(curthread, &m->m_lock);
 923                 }
 924                 if (abstime) {
 925                         clock_gettime(CLOCK_REALTIME, &ts1);
 926                         TIMESPEC_SUB(&ts2, abstime, &ts1);
 927                         __sys_nanosleep(&ts2, NULL);
 928                         ret = ETIMEDOUT;
 929                 } else {
 930                         ts1.tv_sec = 30;
 931                         ts1.tv_nsec = 0;
 932                         for (;;)
 933                                 __sys_nanosleep(&ts1, NULL);
 934                 }
 935                 break;
 936
 937         case PTHREAD_MUTEX_RECURSIVE:
 938                 /* Increment the lock count: */
 939                 if (m->m_count + 1 > 0) {
 940                         m->m_count++;
 941                         ret = 0;
 942                 } else
 943                         ret = EAGAIN;
 944                 break;
 945
 946         default:
 947                 /* Trap invalid mutex types; */
 948                 ret = EINVAL;
 949         }
 950
 951         return (ret);
 952 }
 953
 954 static int
 955 mutex_unlock_common(pthread_mutex_t *m, int add_reference)
 956 {
 957         struct pthread *curthread = tls_get_curthread();
 958         long tid = -1;
 959         int ret = 0;
 960
 961         if (m == NULL || *m == NULL)
 962                 ret = EINVAL;
 963         else {
 964                 /* Short cut for simple mutex. */
 965
 966                 if ((*m)->m_protocol == PTHREAD_PRIO_NONE) {
 967                         /*
 968                          * Check if the running thread is not the owner of the
 969                          * mutex:
 970                          */
 971                         if (__predict_false((*m)->m_owner != curthread)) {
 972                                 ret = EPERM;
 973                         } else if (__predict_false(
 974                                   (*m)->m_type == PTHREAD_MUTEX_RECURSIVE &&
 975                                   (*m)->m_count > 0)) {
 976                                 /* Decrement the count: */
 977                                 (*m)->m_count--;
 978                                 if (add_reference)
 979                                         (*m)->m_refcount++;
 980                         } else {
 981                                 /*
 982                                  * Clear the count in case this is a recursive
 983                                  * mutex.
 984                                  */
 985                                 (*m)->m_count = 0;
 986                                 (*m)->m_owner = NULL;
 987                                 /* Remove the mutex from the threads queue. */
 988                                 MUTEX_ASSERT_IS_OWNED(*m);
 989                                 TAILQ_REMOVE(&curthread->mutexq, (*m), m_qe);
 990                                 MUTEX_INIT_LINK(*m);
 991                                 if (add_reference)
 992                                         (*m)->m_refcount++;
 993                                 /*
 994                                  * Hand off the mutex to the next waiting
 995                                  * thread.
 996                                  */
 997                                 _thr_umtx_unlock(&(*m)->m_lock, curthread->tid);
 998                         }
 999                         return (ret);
1000                 }
1001
1002                 /* Code for priority mutex */
1003
1004                 /* Lock the mutex structure: */
1005                 THR_LOCK_ACQUIRE(curthread, &(*m)->m_lock);
1006
1007                 /* Process according to mutex type: */
1008                 switch ((*m)->m_protocol) {
1009                 /* POSIX priority inheritence mutex: */
1010                 case PTHREAD_PRIO_INHERIT:
1011                         /*
1012                          * Check if the running thread is not the owner of the
1013                          * mutex:
1014                          */
1015                         if ((*m)->m_owner != curthread)
1016                                 ret = EPERM;
1017                         else if (((*m)->m_type == PTHREAD_MUTEX_RECURSIVE) &&
1018                             ((*m)->m_count > 0))
1019                                 /* Decrement the count: */
1020                                 (*m)->m_count--;
1021                         else {
1022                                 /*
1023                                  * Clear the count in case this is recursive
1024                                  * mutex.
1025                                  */
1026                                 (*m)->m_count = 0;
1027
1028                                 /*
1029                                  * Restore the threads inherited priority and
1030                                  * recompute the active priority (being careful
1031                                  * not to override changes in the threads base
1032                                  * priority subsequent to locking the mutex).
1033                                  */
1034                                 THR_LOCK(curthread);
1035                                 curthread->inherited_priority =
1036                                         (*m)->m_saved_prio;
1037                                 curthread->active_priority =
1038                                     MAX(curthread->inherited_priority,
1039                                     curthread->base_priority);
1040
1041                                 /*
1042                                  * This thread now owns one less priority mutex.
1043                                  */
1044                                 curthread->priority_mutex_count--;
1045                                 THR_UNLOCK(curthread);
1046
1047                                 /* Remove the mutex from the threads queue. */
1048                                 MUTEX_ASSERT_IS_OWNED(*m);
1049                                 TAILQ_REMOVE(&(*m)->m_owner->pri_mutexq,
1050                                     (*m), m_qe);
1051                                 MUTEX_INIT_LINK(*m);
1052
1053                                 /*
1054                                  * Hand off the mutex to the next waiting
1055                                  * thread:
1056                                  */
1057                                 tid = mutex_handoff(curthread, *m);
1058                         }
1059                         break;
1060
1061                 /* POSIX priority ceiling mutex: */
1062                 case PTHREAD_PRIO_PROTECT:
1063                         /*
1064                          * Check if the running thread is not the owner of the
1065                          * mutex:
1066                          */
1067                         if ((*m)->m_owner != curthread)
1068                                 ret = EPERM;
1069                         else if (((*m)->m_type == PTHREAD_MUTEX_RECURSIVE) &&
1070                             ((*m)->m_count > 0))
1071                                 /* Decrement the count: */
1072                                 (*m)->m_count--;
1073                         else {
1074                                 /*
1075                                  * Clear the count in case this is a recursive
1076                                  * mutex.
1077                                  */
1078                                 (*m)->m_count = 0;
1079
1080                                 /*
1081                                  * Restore the threads inherited priority and
1082                                  * recompute the active priority (being careful
1083                                  * not to override changes in the threads base
1084                                  * priority subsequent to locking the mutex).
1085                                  */
1086                                 THR_LOCK(curthread);
1087                                 curthread->inherited_priority =
1088                                         (*m)->m_saved_prio;
1089                                 curthread->active_priority =
1090                                     MAX(curthread->inherited_priority,
1091                                     curthread->base_priority);
1092
1093                                 /*
1094                                  * This thread now owns one less priority mutex.
1095                                  */
1096                                 curthread->priority_mutex_count--;
1097                                 THR_UNLOCK(curthread);
1098
1099                                 /* Remove the mutex from the threads queue. */
1100                                 MUTEX_ASSERT_IS_OWNED(*m);
1101                                 TAILQ_REMOVE(&(*m)->m_owner->pri_mutexq,
1102                                     (*m), m_qe);
1103                                 MUTEX_INIT_LINK(*m);
1104
1105                                 /*
1106                                  * Hand off the mutex to the next waiting
1107                                  * thread:
1108                                  */
1109                                 tid = mutex_handoff(curthread, *m);
1110                         }
1111                         break;
1112
1113                 /* Trap invalid mutex types: */
1114                 default:
1115                         /* Return an invalid argument error: */
1116                         ret = EINVAL;
1117                         break;
1118                 }
1119
1120                 if ((ret == 0) && (add_reference != 0))
1121                         /* Increment the reference count: */
1122                         (*m)->m_refcount++;
1123
1124                 /* Unlock the mutex structure: */
1125                 THR_LOCK_RELEASE(curthread, &(*m)->m_lock);
1126         }
1127
1128         /* Return the completion status: */
1129         return (ret);
1130 }
1131
1132
1133 /*
1134  * This function is called when a change in base priority occurs for
1135  * a thread that is holding or waiting for a priority protection or
1136  * inheritence mutex.  A change in a threads base priority can effect
1137  * changes to active priorities of other threads and to the ordering
1138  * of mutex locking by waiting threads.
1139  *
1140  * This must be called without the target thread's scheduling lock held.
1141  */
1142 void
1143 _mutex_notify_priochange(struct pthread *curthread, struct pthread *pthread,
1144     int propagate_prio)
1145 {
1146         struct pthread_mutex *m;
1147
1148         /* Adjust the priorites of any owned priority mutexes: */
1149         if (pthread->priority_mutex_count > 0) {
1150                 /*
1151                  * Rescan the mutexes owned by this thread and correct
1152                  * their priorities to account for this threads change
1153                  * in priority.  This has the side effect of changing
1154                  * the threads active priority.
1155                  *
1156                  * Be sure to lock the first mutex in the list of owned
1157                  * mutexes.  This acts as a barrier against another
1158                  * simultaneous call to change the threads priority
1159                  * and from the owning thread releasing the mutex.
1160                  */
1161                 m = TAILQ_FIRST(&pthread->pri_mutexq);
1162                 if (m != NULL) {
1163                         THR_LOCK_ACQUIRE(curthread, &m->m_lock);
1164                         /*
1165                          * Make sure the thread still owns the lock.
1166                          */
1167                         if (m == TAILQ_FIRST(&pthread->pri_mutexq))
1168                                 mutex_rescan_owned(curthread, pthread,
1169                                     /* rescan all owned */ NULL);
1170                         THR_LOCK_RELEASE(curthread, &m->m_lock);
1171                 }
1172         }
1173
1174         /*
1175          * If this thread is waiting on a priority inheritence mutex,
1176          * check for priority adjustments.  A change in priority can
1177          * also cause a ceiling violation(*) for a thread waiting on
1178          * a priority protection mutex; we don't perform the check here
1179          * as it is done in pthread_mutex_unlock.
1180          *
1181          * (*) It should be noted that a priority change to a thread
1182          *     _after_ taking and owning a priority ceiling mutex
1183          *     does not affect ownership of that mutex; the ceiling
1184          *     priority is only checked before mutex ownership occurs.
1185          */
1186         if (propagate_prio != 0) {
1187                 /*
1188                  * Lock the thread's scheduling queue.  This is a bit
1189                  * convoluted; the "in synchronization queue flag" can
1190                  * only be cleared with both the thread's scheduling and
1191                  * mutex locks held.  The thread's pointer to the wanted
1192                  * mutex is guaranteed to be valid during this time.
1193                  */
1194                 THR_THREAD_LOCK(curthread, pthread);
1195
1196                 if (((pthread->sflags & THR_FLAGS_IN_SYNCQ) == 0) ||
1197                     ((m = pthread->data.mutex) == NULL))
1198                         THR_THREAD_UNLOCK(curthread, pthread);
1199                 else {
1200                         /*
1201                          * This thread is currently waiting on a mutex; unlock
1202                          * the scheduling queue lock and lock the mutex.  We
1203                          * can't hold both at the same time because the locking
1204                          * order could cause a deadlock.
1205                          */
1206                         THR_THREAD_UNLOCK(curthread, pthread);
1207                         THR_LOCK_ACQUIRE(curthread, &m->m_lock);
1208
1209                         /*
1210                          * Check to make sure this thread is still in the
1211                          * same state (the lock above can yield the CPU to
1212                          * another thread or the thread may be running on
1213                          * another CPU).
1214                          */
1215                         if (((pthread->sflags & THR_FLAGS_IN_SYNCQ) != 0) &&
1216                             (pthread->data.mutex == m)) {
1217                                 /*
1218                                  * Remove and reinsert this thread into
1219                                  * the list of waiting threads to preserve
1220                                  * decreasing priority order.
1221                                  */
1222                                 mutex_queue_remove(m, pthread);
1223                                 mutex_queue_enq(m, pthread);
1224
1225                                 if (m->m_protocol == PTHREAD_PRIO_INHERIT)
1226                                         /* Adjust priorities: */
1227                                         mutex_priority_adjust(curthread, m);
1228                         }
1229
1230                         /* Unlock the mutex structure: */
1231                         THR_LOCK_RELEASE(curthread, &m->m_lock);
1232                 }
1233         }
1234 }
1235
1236 /*
1237  * Called when a new thread is added to the mutex waiting queue or
1238  * when a threads priority changes that is already in the mutex
1239  * waiting queue.
1240  *
1241  * This must be called with the mutex locked by the current thread.
1242  */
1243 static void
1244 mutex_priority_adjust(struct pthread *curthread, pthread_mutex_t mutex)
1245 {
1246         pthread_mutex_t m = mutex;
1247         struct pthread  *pthread_next, *pthread = mutex->m_owner;
1248         int             done, temp_prio;
1249
1250         /*
1251          * Calculate the mutex priority as the maximum of the highest
1252          * active priority of any waiting threads and the owning threads
1253          * active priority(*).
1254          *
1255          * (*) Because the owning threads current active priority may
1256          *     reflect priority inherited from this mutex (and the mutex
1257          *     priority may have changed) we must recalculate the active
1258          *     priority based on the threads saved inherited priority
1259          *     and its base priority.
1260          */
1261         pthread_next = TAILQ_FIRST(&m->m_queue);  /* should never be NULL */
1262         temp_prio = MAX(pthread_next->active_priority,
1263             MAX(m->m_saved_prio, pthread->base_priority));
1264
1265         /* See if this mutex really needs adjusting: */
1266         if (temp_prio == m->m_prio)
1267                 /* No need to propagate the priority: */
1268                 return;
1269
1270         /* Set new priority of the mutex: */
1271         m->m_prio = temp_prio;
1272
1273         /*
1274          * Don't unlock the mutex passed in as an argument.  It is
1275          * expected to be locked and unlocked by the caller.
1276          */
1277         done = 1;
1278         do {
1279                 /*
1280                  * Save the threads priority before rescanning the
1281                  * owned mutexes:
1282                  */
1283                 temp_prio = pthread->active_priority;
1284
1285                 /*
1286                  * Fix the priorities for all mutexes held by the owning
1287                  * thread since taking this mutex.  This also has a
1288                  * potential side-effect of changing the threads priority.
1289                  *
1290                  * At this point the mutex is locked by the current thread.
1291                  * The owning thread can't release the mutex until it is
1292                  * unlocked, so we should be able to safely walk its list
1293                  * of owned mutexes.
1294                  */
1295                 mutex_rescan_owned(curthread, pthread, m);
1296
1297                 /*
1298                  * If this isn't the first time through the loop,
1299                  * the current mutex needs to be unlocked.
1300                  */
1301                 if (done == 0)
1302                         THR_LOCK_RELEASE(curthread, &m->m_lock);
1303
1304                 /* Assume we're done unless told otherwise: */
1305                 done = 1;
1306
1307                 /*
1308                  * If the thread is currently waiting on a mutex, check
1309                  * to see if the threads new priority has affected the
1310                  * priority of the mutex.
1311                  */
1312                 if ((temp_prio != pthread->active_priority) &&
1313                     ((pthread->sflags & THR_FLAGS_IN_SYNCQ) != 0) &&
1314                     ((m = pthread->data.mutex) != NULL) &&
1315                     (m->m_protocol == PTHREAD_PRIO_INHERIT)) {
1316                         /* Lock the mutex structure: */
1317                         THR_LOCK_ACQUIRE(curthread, &m->m_lock);
1318
1319                         /*
1320                          * Make sure the thread is still waiting on the
1321                          * mutex:
1322                          */
1323                         if (((pthread->sflags & THR_FLAGS_IN_SYNCQ) != 0) &&
1324                             (m == pthread->data.mutex)) {
1325                                 /*
1326                                  * The priority for this thread has changed.
1327                                  * Remove and reinsert this thread into the
1328                                  * list of waiting threads to preserve
1329                                  * decreasing priority order.
1330                                  */
1331                                 mutex_queue_remove(m, pthread);
1332                                 mutex_queue_enq(m, pthread);
1333
1334                                 /*
1335                                  * Grab the waiting thread with highest
1336                                  * priority:
1337                                  */
1338                                 pthread_next = TAILQ_FIRST(&m->m_queue);
1339
1340                                 /*
1341                                  * Calculate the mutex priority as the maximum
1342                                  * of the highest active priority of any
1343                                  * waiting threads and the owning threads
1344                                  * active priority.
1345                                  */
1346                                 temp_prio = MAX(pthread_next->active_priority,
1347                                     MAX(m->m_saved_prio,
1348                                     m->m_owner->base_priority));
1349
1350                                 if (temp_prio != m->m_prio) {
1351                                         /*
1352                                          * The priority needs to be propagated
1353                                          * to the mutex this thread is waiting
1354                                          * on and up to the owner of that mutex.
1355                                          */
1356                                         m->m_prio = temp_prio;
1357                                         pthread = m->m_owner;
1358
1359                                         /* We're not done yet: */
1360                                         done = 0;
1361                                 }
1362                         }
1363                         /* Only release the mutex if we're done: */
1364                         if (done != 0)
1365                                 THR_LOCK_RELEASE(curthread, &m->m_lock);
1366                 }
1367         } while (done == 0);
1368 }
1369
1370 static void
1371 mutex_rescan_owned(struct pthread *curthread, struct pthread *pthread,
1372     struct pthread_mutex *mutex)
1373 {
1374         struct pthread_mutex    *m;
1375         struct pthread          *pthread_next;
1376         int                     active_prio, inherited_prio;
1377
1378         /*
1379          * Start walking the mutexes the thread has taken since
1380          * taking this mutex.
1381          */
1382         if (mutex == NULL) {
1383                 /*
1384                  * A null mutex means start at the beginning of the owned
1385                  * mutex list.
1386                  */
1387                 m = TAILQ_FIRST(&pthread->pri_mutexq);
1388
1389                 /* There is no inherited priority yet. */
1390                 inherited_prio = 0;
1391         } else {
1392                 /*
1393                  * The caller wants to start after a specific mutex.  It
1394                  * is assumed that this mutex is a priority inheritence
1395                  * mutex and that its priority has been correctly
1396                  * calculated.
1397                  */
1398                 m = TAILQ_NEXT(mutex, m_qe);
1399
1400                 /* Start inheriting priority from the specified mutex. */
1401                 inherited_prio = mutex->m_prio;
1402         }
1403         active_prio = MAX(inherited_prio, pthread->base_priority);
1404
1405         for (; m != NULL; m = TAILQ_NEXT(m, m_qe)) {
1406                 /*
1407                  * We only want to deal with priority inheritence
1408                  * mutexes.  This might be optimized by only placing
1409                  * priority inheritence mutexes into the owned mutex
1410                  * list, but it may prove to be useful having all
1411                  * owned mutexes in this list.  Consider a thread
1412                  * exiting while holding mutexes...
1413                  */
1414                 if (m->m_protocol == PTHREAD_PRIO_INHERIT) {
1415                         /*
1416                          * Fix the owners saved (inherited) priority to
1417                          * reflect the priority of the previous mutex.
1418                          */
1419                         m->m_saved_prio = inherited_prio;
1420
1421                         if ((pthread_next = TAILQ_FIRST(&m->m_queue)) != NULL)
1422                                 /* Recalculate the priority of the mutex: */
1423                                 m->m_prio = MAX(active_prio,
1424                                      pthread_next->active_priority);
1425                         else
1426                                 m->m_prio = active_prio;
1427
1428                         /* Recalculate new inherited and active priorities: */
1429                         inherited_prio = m->m_prio;
1430                         active_prio = MAX(m->m_prio, pthread->base_priority);
1431                 }
1432         }
1433
1434         /*
1435          * Fix the threads inherited priority and recalculate its
1436          * active priority.
1437          */
1438         pthread->inherited_priority = inherited_prio;
1439         active_prio = MAX(inherited_prio, pthread->base_priority);
1440
1441         if (active_prio != pthread->active_priority) {
1442                 /* Lock the thread's scheduling queue: */
1443                 THR_THREAD_LOCK(curthread, pthread);
1444
1445                 /* if ((pthread->flags & THR_FLAGS_IN_RUNQ) == 0) */
1446                 if (1) {
1447                         /*
1448                          * This thread is not in a run queue.  Just set
1449                          * its active priority.
1450                          */
1451                         pthread->active_priority = active_prio;
1452                 }
1453                 else {
1454                         /*
1455                          * This thread is in a run queue.  Remove it from
1456                          * the queue before changing its priority:
1457                          */
1458                         /* THR_RUNQ_REMOVE(pthread);*/
1459                         /*
1460                          * POSIX states that if the priority is being
1461                          * lowered, the thread must be inserted at the
1462                          * head of the queue for its priority if it owns
1463                          * any priority protection or inheritence mutexes.
1464                          */
1465                         if ((active_prio < pthread->active_priority) &&
1466                             (pthread->priority_mutex_count > 0)) {
1467                                 /* Set the new active priority. */
1468                                 pthread->active_priority = active_prio;
1469                                 /* THR_RUNQ_INSERT_HEAD(pthread); */
1470                         } else {
1471                                 /* Set the new active priority. */
1472                                 pthread->active_priority = active_prio;
1473                                 /* THR_RUNQ_INSERT_TAIL(pthread);*/
1474                         }
1475                 }
1476                 THR_THREAD_UNLOCK(curthread, pthread);
1477         }
1478 }
1479
1480 void
1481 _mutex_unlock_private(pthread_t pthread)
1482 {
1483         struct pthread_mutex    *m, *m_next;
1484
1485         for (m = TAILQ_FIRST(&pthread->pri_mutexq); m != NULL; m = m_next) {
1486                 m_next = TAILQ_NEXT(m, m_qe);
1487                 if ((m->m_flags & MUTEX_FLAGS_PRIVATE) != 0)
1488                         pthread_mutex_unlock(&m);
1489         }
1490 }
1491
1492 /*
1493  * Dequeue a waiting thread from the head of a mutex queue in descending
1494  * priority order.
1495  *
1496  * In order to properly dequeue a thread from the mutex queue and
1497  * make it runnable without the possibility of errant wakeups, it
1498  * is necessary to lock the thread's scheduling queue while also
1499  * holding the mutex lock.
1500  */
1501 static long
1502 mutex_handoff(struct pthread *curthread, struct pthread_mutex *mutex)
1503 {
1504         struct pthread *pthread;
1505         long tid = -1;
1506
1507         /* Keep dequeueing until we find a valid thread: */
1508         mutex->m_owner = NULL;
1509         pthread = TAILQ_FIRST(&mutex->m_queue);
1510         while (pthread != NULL) {
1511                 /* Take the thread's scheduling lock: */
1512                 THR_THREAD_LOCK(curthread, pthread);
1513
1514                 /* Remove the thread from the mutex queue: */
1515                 TAILQ_REMOVE(&mutex->m_queue, pthread, sqe);
1516                 pthread->sflags &= ~THR_FLAGS_IN_SYNCQ;
1517
1518                 /*
1519                  * Only exit the loop if the thread hasn't been
1520                  * cancelled.
1521                  */
1522                 switch (mutex->m_protocol) {
1523                 case PTHREAD_PRIO_NONE:
1524                         /*
1525                          * Assign the new owner and add the mutex to the
1526                          * thread's list of owned mutexes.
1527                          */
1528                         mutex->m_owner = pthread;
1529                         TAILQ_INSERT_TAIL(&pthread->pri_mutexq, mutex, m_qe);
1530                         break;
1531
1532                 case PTHREAD_PRIO_INHERIT:
1533                         /*
1534                          * Assign the new owner and add the mutex to the
1535                          * thread's list of owned mutexes.
1536                          */
1537                         mutex->m_owner = pthread;
1538                         TAILQ_INSERT_TAIL(&pthread->pri_mutexq, mutex, m_qe);
1539
1540                         /* Track number of priority mutexes owned: */
1541                         pthread->priority_mutex_count++;
1542
1543                         /*
1544                          * Set the priority of the mutex.  Since our waiting
1545                          * threads are in descending priority order, the
1546                          * priority of the mutex becomes the active priority
1547                          * of the thread we just dequeued.
1548                          */
1549                         mutex->m_prio = pthread->active_priority;
1550
1551                         /* Save the owning threads inherited priority: */
1552                         mutex->m_saved_prio = pthread->inherited_priority;
1553
1554                         /*
1555                          * The owning threads inherited priority now becomes
1556                          * his active priority (the priority of the mutex).
1557                          */
1558                         pthread->inherited_priority = mutex->m_prio;
1559                         break;
1560
1561                 case PTHREAD_PRIO_PROTECT:
1562                         if (pthread->active_priority > mutex->m_prio) {
1563                                 /*
1564                                  * Either the mutex ceiling priority has
1565                                  * been lowered and/or this threads priority
1566                                  * has been raised subsequent to the thread
1567                                  * being queued on the waiting list.
1568                                  */
1569                                 pthread->error = EINVAL;
1570                         }
1571                         else {
1572                                 /*
1573                                  * Assign the new owner and add the mutex
1574                                  * to the thread's list of owned mutexes.
1575                                  */
1576                                 mutex->m_owner = pthread;
1577                                 TAILQ_INSERT_TAIL(&pthread->pri_mutexq,
1578                                     mutex, m_qe);
1579
1580                                 /* Track number of priority mutexes owned: */
1581                                 pthread->priority_mutex_count++;
1582
1583                                 /*
1584                                  * Save the owning threads inherited
1585                                  * priority:
1586                                  */
1587                                 mutex->m_saved_prio =
1588                                     pthread->inherited_priority;
1589
1590                                 /*
1591                                  * The owning thread inherits the ceiling
1592                                  * priority of the mutex and executes at
1593                                  * that priority:
1594                                  */
1595                                 pthread->inherited_priority = mutex->m_prio;
1596                                 pthread->active_priority = mutex->m_prio;
1597
1598                         }
1599                         break;
1600                 }
1601
1602                 /* Make the thread runnable and unlock the scheduling queue: */
1603                 pthread->cycle++;
1604                 _thr_umtx_wake(&pthread->cycle, 1);
1605
1606                 THR_THREAD_UNLOCK(curthread, pthread);
1607                 if (mutex->m_owner == pthread)
1608                         /* We're done; a valid owner was found. */
1609                         break;
1610                 else
1611                         /* Get the next thread from the waiting queue: */
1612                         pthread = TAILQ_NEXT(pthread, sqe);
1613         }
1614
1615         if ((pthread == NULL) && (mutex->m_protocol == PTHREAD_PRIO_INHERIT))
1616                 /* This mutex has no priority: */
1617                 mutex->m_prio = 0;
1618         return (tid);
1619 }
1620
1621 #if 0
1622 /*
1623  * Dequeue a waiting thread from the head of a mutex queue in descending
1624  * priority order.
1625  */
1626 static pthread_t
1627 mutex_queue_deq(struct pthread_mutex *mutex)
1628 {
1629         pthread_t pthread;
1630
1631         while ((pthread = TAILQ_FIRST(&mutex->m_queue)) != NULL) {
1632                 TAILQ_REMOVE(&mutex->m_queue, pthread, sqe);
1633                 pthread->sflags &= ~THR_FLAGS_IN_SYNCQ;
1634         }
1635
1636         return (pthread);
1637 }
1638 #endif
1639
1640 /*
1641  * Remove a waiting thread from a mutex queue in descending priority order.
1642  */
1643 static void
1644 mutex_queue_remove(pthread_mutex_t mutex, pthread_t pthread)
1645 {
1646         if ((pthread->sflags & THR_FLAGS_IN_SYNCQ) != 0) {
1647                 TAILQ_REMOVE(&mutex->m_queue, pthread, sqe);
1648                 pthread->sflags &= ~THR_FLAGS_IN_SYNCQ;
1649         }
1650 }
1651
1652 /*
1653  * Enqueue a waiting thread to a queue in descending priority order.
1654  */
1655 static void
1656 mutex_queue_enq(pthread_mutex_t mutex, pthread_t pthread)
1657 {
1658         pthread_t tid = TAILQ_LAST(&mutex->m_queue, mutex_head);
1659
1660         THR_ASSERT_NOT_IN_SYNCQ(pthread);
1661         /*
1662          * For the common case of all threads having equal priority,
1663          * we perform a quick check against the priority of the thread
1664          * at the tail of the queue.
1665          */
1666         if ((tid == NULL) || (pthread->active_priority <= tid->active_priority))
1667                 TAILQ_INSERT_TAIL(&mutex->m_queue, pthread, sqe);
1668         else {
1669                 tid = TAILQ_FIRST(&mutex->m_queue);
1670                 while (pthread->active_priority <= tid->active_priority)
1671                         tid = TAILQ_NEXT(tid, sqe);
1672                 TAILQ_INSERT_BEFORE(tid, pthread, sqe);
1673         }
1674         pthread->sflags |= THR_FLAGS_IN_SYNCQ;
1675 }