lib/libkse/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$
  33  */
  34 #include <stdlib.h>
  35 #include <errno.h>
  36 #include <string.h>
  37 #include <sys/param.h>
  38 #include <sys/queue.h>
  39 #ifdef _THREAD_SAFE
  40 #include <pthread.h>
  41 #include "pthread_private.h"
  42
  43 #if defined(_PTHREADS_INVARIANTS)
  44 #define _MUTEX_INIT_LINK(m)             do {            \
  45         (m)->m_qe.tqe_prev = NULL;                      \
  46         (m)->m_qe.tqe_next = NULL;                      \
  47 } while (0)
  48 #define _MUTEX_ASSERT_IS_OWNED(m)       do {            \
  49         if ((m)->m_qe.tqe_prev == NULL)                 \
  50                 PANIC("mutex is not on list");          \
  51 } while (0)
  52 #define _MUTEX_ASSERT_NOT_OWNED(m)      do {            \
  53         if (((m)->m_qe.tqe_prev != NULL) ||             \
  54             ((m)->m_qe.tqe_next != NULL))               \
  55                 PANIC("mutex is on list");              \
  56 } while (0)
  57 #else
  58 #define _MUTEX_INIT_LINK(m)
  59 #define _MUTEX_ASSERT_IS_OWNED(m)
  60 #define _MUTEX_ASSERT_NOT_OWNED(m)
  61 #endif
  62
  63 /*
  64  * Prototypes
  65  */
  66 static inline int       mutex_self_trylock(pthread_mutex_t);
  67 static inline int       mutex_self_lock(pthread_mutex_t);
  68 static inline int       mutex_unlock_common(pthread_mutex_t *, int);
  69 static void             mutex_priority_adjust(pthread_mutex_t);
  70 static void             mutex_rescan_owned (pthread_t, pthread_mutex_t);
  71 static inline pthread_t mutex_queue_deq(pthread_mutex_t);
  72 static inline void      mutex_queue_remove(pthread_mutex_t, pthread_t);
  73 static inline void      mutex_queue_enq(pthread_mutex_t, pthread_t);
  74
  75
  76 static spinlock_t static_init_lock = _SPINLOCK_INITIALIZER;
  77
  78 /* Reinitialize a mutex to defaults. */
  79 int
  80 _mutex_reinit(pthread_mutex_t * mutex)
  81 {
  82         int ret = 0;
  83
  84         if (mutex == NULL)
  85                 ret = EINVAL;
  86         else if (*mutex == NULL)
  87                 ret = pthread_mutex_init(mutex, NULL);
  88         else {
  89                 /*
  90                  * Initialize the mutex structure:
  91                  */
  92                 (*mutex)->m_type = PTHREAD_MUTEX_DEFAULT;
  93                 (*mutex)->m_protocol = PTHREAD_PRIO_NONE;
  94                 TAILQ_INIT(&(*mutex)->m_queue);
  95                 (*mutex)->m_owner = NULL;
  96                 (*mutex)->m_data.m_count = 0;
  97                 (*mutex)->m_flags = MUTEX_FLAGS_INITED;
  98                 (*mutex)->m_refcount = 0;
  99                 (*mutex)->m_prio = 0;
 100                 (*mutex)->m_saved_prio = 0;
 101                 _MUTEX_INIT_LINK(*mutex);
 102                 memset(&(*mutex)->lock, 0, sizeof((*mutex)->lock));
 103         }
 104         return (ret);
 105 }
 106
 107 int
 108 pthread_mutex_init(pthread_mutex_t * mutex,
 109                    const pthread_mutexattr_t * mutex_attr)
 110 {
 111         enum pthread_mutextype  type;
 112         int             protocol;
 113         int             ceiling;
 114         pthread_mutex_t pmutex;
 115         int             ret = 0;
 116
 117         if (mutex == NULL)
 118                 ret = EINVAL;
 119
 120         /* Check if default mutex attributes: */
 121         else if (mutex_attr == NULL || *mutex_attr == NULL) {
 122                 /* Default to a (error checking) POSIX mutex: */
 123                 type = PTHREAD_MUTEX_ERRORCHECK;
 124                 protocol = PTHREAD_PRIO_NONE;
 125                 ceiling = PTHREAD_MAX_PRIORITY;
 126         }
 127
 128         /* Check mutex type: */
 129         else if (((*mutex_attr)->m_type < PTHREAD_MUTEX_ERRORCHECK) ||
 130             ((*mutex_attr)->m_type >= MUTEX_TYPE_MAX))
 131                 /* Return an invalid argument error: */
 132                 ret = EINVAL;
 133
 134         /* Check mutex protocol: */
 135         else if (((*mutex_attr)->m_protocol < PTHREAD_PRIO_NONE) ||
 136             ((*mutex_attr)->m_protocol > PTHREAD_MUTEX_RECURSIVE))
 137                 /* Return an invalid argument error: */
 138                 ret = EINVAL;
 139
 140         else {
 141                 /* Use the requested mutex type and protocol: */
 142                 type = (*mutex_attr)->m_type;
 143                 protocol = (*mutex_attr)->m_protocol;
 144                 ceiling = (*mutex_attr)->m_ceiling;
 145         }
 146
 147         /* Check no errors so far: */
 148         if (ret == 0) {
 149                 if ((pmutex = (pthread_mutex_t)
 150                     malloc(sizeof(struct pthread_mutex))) == NULL)
 151                         ret = ENOMEM;
 152                 else {
 153                         /* Reset the mutex flags: */
 154                         pmutex->m_flags = 0;
 155
 156                         /* Process according to mutex type: */
 157                         switch (type) {
 158                         /* case PTHREAD_MUTEX_DEFAULT: */
 159                         case PTHREAD_MUTEX_ERRORCHECK:
 160                         case PTHREAD_MUTEX_NORMAL:
 161                                 /* Nothing to do here. */
 162                                 break;
 163
 164                         /* Single UNIX Spec 2 recursive mutex: */
 165                         case PTHREAD_MUTEX_RECURSIVE:
 166                                 /* Reset the mutex count: */
 167                                 pmutex->m_data.m_count = 0;
 168                                 break;
 169
 170                         /* Trap invalid mutex types: */
 171                         default:
 172                                 /* Return an invalid argument error: */
 173                                 ret = EINVAL;
 174                                 break;
 175                         }
 176                         if (ret == 0) {
 177                                 /* Initialise the rest of the mutex: */
 178                                 TAILQ_INIT(&pmutex->m_queue);
 179                                 pmutex->m_flags |= MUTEX_FLAGS_INITED;
 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 = 0;
 188                                 pmutex->m_saved_prio = 0;
 189                                 _MUTEX_INIT_LINK(pmutex);
 190                                 memset(&pmutex->lock, 0, sizeof(pmutex->lock));
 191                                 *mutex = pmutex;
 192                         } else {
 193                                 free(pmutex);
 194                                 *mutex = NULL;
 195                         }
 196                 }
 197         }
 198         /* Return the completion status: */
 199         return(ret);
 200 }
 201
 202 int
 203 pthread_mutex_destroy(pthread_mutex_t * mutex)
 204 {
 205         int ret = 0;
 206
 207         if (mutex == NULL || *mutex == NULL)
 208                 ret = EINVAL;
 209         else {
 210                 /* Lock the mutex structure: */
 211                 _SPINLOCK(&(*mutex)->lock);
 212
 213                 /*
 214                  * Check to see if this mutex is in use:
 215                  */
 216                 if (((*mutex)->m_owner != NULL) ||
 217                     (TAILQ_FIRST(&(*mutex)->m_queue) != NULL) ||
 218                     ((*mutex)->m_refcount != 0)) {
 219                         ret = EBUSY;
 220
 221                         /* Unlock the mutex structure: */
 222                         _SPINUNLOCK(&(*mutex)->lock);
 223                 }
 224                 else {
 225                         /*
 226                          * Free the memory allocated for the mutex
 227                          * structure:
 228                          */
 229                         _MUTEX_ASSERT_NOT_OWNED(*mutex);
 230                         free(*mutex);
 231
 232                         /*
 233                          * Leave the caller's pointer NULL now that
 234                          * the mutex has been destroyed:
 235                          */
 236                         *mutex = NULL;
 237                 }
 238         }
 239
 240         /* Return the completion status: */
 241         return (ret);
 242 }
 243
 244 static int
 245 init_static (pthread_mutex_t *mutex)
 246 {
 247         int ret;
 248
 249         _SPINLOCK(&static_init_lock);
 250
 251         if (*mutex == NULL)
 252                 ret = pthread_mutex_init(mutex, NULL);
 253         else
 254                 ret = 0;
 255
 256         _SPINUNLOCK(&static_init_lock);
 257
 258         return(ret);
 259 }
 260
 261 int
 262 pthread_mutex_trylock(pthread_mutex_t * mutex)
 263 {
 264         int             ret = 0;
 265
 266         if (mutex == NULL)
 267                 ret = EINVAL;
 268
 269         /*
 270          * If the mutex is statically initialized, perform the dynamic
 271          * initialization:
 272          */
 273         else if (*mutex != NULL || (ret = init_static(mutex)) == 0) {
 274                 /*
 275                  * Defer signals to protect the scheduling queues from
 276                  * access by the signal handler:
 277                  */
 278                 _thread_kern_sig_defer();
 279
 280                 /* Lock the mutex structure: */
 281                 _SPINLOCK(&(*mutex)->lock);
 282
 283                 /*
 284                  * If the mutex was statically allocated, properly
 285                  * initialize the tail queue.
 286                  */
 287                 if (((*mutex)->m_flags & MUTEX_FLAGS_INITED) == 0) {
 288                         TAILQ_INIT(&(*mutex)->m_queue);
 289                         _MUTEX_INIT_LINK(*mutex);
 290                         (*mutex)->m_flags |= MUTEX_FLAGS_INITED;
 291                 }
 292
 293                 /* Process according to mutex type: */
 294                 switch ((*mutex)->m_protocol) {
 295                 /* Default POSIX mutex: */
 296                 case PTHREAD_PRIO_NONE:
 297                         /* Check if this mutex is not locked: */
 298                         if ((*mutex)->m_owner == NULL) {
 299                                 /* Lock the mutex for the running thread: */
 300                                 (*mutex)->m_owner = _thread_run;
 301
 302                                 /* Add to the list of owned mutexes: */
 303                                 _MUTEX_ASSERT_NOT_OWNED(*mutex);
 304                                 TAILQ_INSERT_TAIL(&_thread_run->mutexq,
 305                                     (*mutex), m_qe);
 306                         } else if ((*mutex)->m_owner == _thread_run)
 307                                 ret = mutex_self_trylock(*mutex);
 308                         else
 309                                 /* Return a busy error: */
 310                                 ret = EBUSY;
 311                         break;
 312
 313                 /* POSIX priority inheritence mutex: */
 314                 case PTHREAD_PRIO_INHERIT:
 315                         /* Check if this mutex is not locked: */
 316                         if ((*mutex)->m_owner == NULL) {
 317                                 /* Lock the mutex for the running thread: */
 318                                 (*mutex)->m_owner = _thread_run;
 319
 320                                 /* Track number of priority mutexes owned: */
 321                                 _thread_run->priority_mutex_count++;
 322
 323                                 /*
 324                                  * The mutex takes on the attributes of the
 325                                  * running thread when there are no waiters.
 326                                  */
 327                                 (*mutex)->m_prio = _thread_run->active_priority;
 328                                 (*mutex)->m_saved_prio =
 329                                     _thread_run->inherited_priority;
 330
 331                                 /* Add to the list of owned mutexes: */
 332                                 _MUTEX_ASSERT_NOT_OWNED(*mutex);
 333                                 TAILQ_INSERT_TAIL(&_thread_run->mutexq,
 334                                     (*mutex), m_qe);
 335                         } else if ((*mutex)->m_owner == _thread_run)
 336                                 ret = mutex_self_trylock(*mutex);
 337                         else
 338                                 /* Return a busy error: */
 339                                 ret = EBUSY;
 340                         break;
 341
 342                 /* POSIX priority protection mutex: */
 343                 case PTHREAD_PRIO_PROTECT:
 344                         /* Check for a priority ceiling violation: */
 345                         if (_thread_run->active_priority > (*mutex)->m_prio)
 346                                 ret = EINVAL;
 347
 348                         /* Check if this mutex is not locked: */
 349                         else if ((*mutex)->m_owner == NULL) {
 350                                 /* Lock the mutex for the running thread: */
 351                                 (*mutex)->m_owner = _thread_run;
 352
 353                                 /* Track number of priority mutexes owned: */
 354                                 _thread_run->priority_mutex_count++;
 355
 356                                 /*
 357                                  * The running thread inherits the ceiling
 358                                  * priority of the mutex and executes at that
 359                                  * priority.
 360                                  */
 361                                 _thread_run->active_priority = (*mutex)->m_prio;
 362                                 (*mutex)->m_saved_prio =
 363                                     _thread_run->inherited_priority;
 364                                 _thread_run->inherited_priority =
 365                                     (*mutex)->m_prio;
 366
 367                                 /* Add to the list of owned mutexes: */
 368                                 _MUTEX_ASSERT_NOT_OWNED(*mutex);
 369                                 TAILQ_INSERT_TAIL(&_thread_run->mutexq,
 370                                     (*mutex), m_qe);
 371                         } else if ((*mutex)->m_owner == _thread_run)
 372                                 ret = mutex_self_trylock(*mutex);
 373                         else
 374                                 /* Return a busy error: */
 375                                 ret = EBUSY;
 376                         break;
 377
 378                 /* Trap invalid mutex types: */
 379                 default:
 380                         /* Return an invalid argument error: */
 381                         ret = EINVAL;
 382                         break;
 383                 }
 384
 385                 /* Unlock the mutex structure: */
 386                 _SPINUNLOCK(&(*mutex)->lock);
 387
 388                 /*
 389                  * Undefer and handle pending signals, yielding if
 390                  * necessary:
 391                  */
 392                 _thread_kern_sig_undefer();
 393         }
 394
 395         /* Return the completion status: */
 396         return (ret);
 397 }
 398
 399 int
 400 pthread_mutex_lock(pthread_mutex_t * mutex)
 401 {
 402         int             ret = 0;
 403
 404         if (mutex == NULL)
 405                 ret = EINVAL;
 406
 407         /*
 408          * If the mutex is statically initialized, perform the dynamic
 409          * initialization:
 410          */
 411         else if (*mutex != NULL || (ret = init_static(mutex)) == 0) {
 412                 /*
 413                  * Defer signals to protect the scheduling queues from
 414                  * access by the signal handler:
 415                  */
 416                 _thread_kern_sig_defer();
 417
 418                 /* Lock the mutex structure: */
 419                 _SPINLOCK(&(*mutex)->lock);
 420
 421                 /*
 422                  * If the mutex was statically allocated, properly
 423                  * initialize the tail queue.
 424                  */
 425                 if (((*mutex)->m_flags & MUTEX_FLAGS_INITED) == 0) {
 426                         TAILQ_INIT(&(*mutex)->m_queue);
 427                         (*mutex)->m_flags |= MUTEX_FLAGS_INITED;
 428                         _MUTEX_INIT_LINK(*mutex);
 429                 }
 430
 431                 /* Process according to mutex type: */
 432                 switch ((*mutex)->m_protocol) {
 433                 /* Default POSIX mutex: */
 434                 case PTHREAD_PRIO_NONE:
 435                         if ((*mutex)->m_owner == NULL) {
 436                                 /* Lock the mutex for this thread: */
 437                                 (*mutex)->m_owner = _thread_run;
 438
 439                                 /* Add to the list of owned mutexes: */
 440                                 _MUTEX_ASSERT_NOT_OWNED(*mutex);
 441                                 TAILQ_INSERT_TAIL(&_thread_run->mutexq,
 442                                     (*mutex), m_qe);
 443
 444                         } else if ((*mutex)->m_owner == _thread_run)
 445                                 ret = mutex_self_lock(*mutex);
 446                         else {
 447                                 /*
 448                                  * Join the queue of threads waiting to lock
 449                                  * the mutex:
 450                                  */
 451                                 mutex_queue_enq(*mutex, _thread_run);
 452
 453                                 /*
 454                                  * Keep a pointer to the mutex this thread
 455                                  * is waiting on:
 456                                  */
 457                                 _thread_run->data.mutex = *mutex;
 458
 459                                 /*
 460                                  * Unlock the mutex structure and schedule the
 461                                  * next thread:
 462                                  */
 463                                 _thread_kern_sched_state_unlock(PS_MUTEX_WAIT,
 464                                     &(*mutex)->lock, __FILE__, __LINE__);
 465
 466                                 /* Lock the mutex structure again: */
 467                                 _SPINLOCK(&(*mutex)->lock);
 468                         }
 469                         break;
 470
 471                 /* POSIX priority inheritence mutex: */
 472                 case PTHREAD_PRIO_INHERIT:
 473                         /* Check if this mutex is not locked: */
 474                         if ((*mutex)->m_owner == NULL) {
 475                                 /* Lock the mutex for this thread: */
 476                                 (*mutex)->m_owner = _thread_run;
 477
 478                                 /* Track number of priority mutexes owned: */
 479                                 _thread_run->priority_mutex_count++;
 480
 481                                 /*
 482                                  * The mutex takes on attributes of the
 483                                  * running thread when there are no waiters.
 484                                  */
 485                                 (*mutex)->m_prio = _thread_run->active_priority;
 486                                 (*mutex)->m_saved_prio =
 487                                     _thread_run->inherited_priority;
 488                                 _thread_run->inherited_priority =
 489                                     (*mutex)->m_prio;
 490
 491                                 /* Add to the list of owned mutexes: */
 492                                 _MUTEX_ASSERT_NOT_OWNED(*mutex);
 493                                 TAILQ_INSERT_TAIL(&_thread_run->mutexq,
 494                                     (*mutex), m_qe);
 495
 496                         } else if ((*mutex)->m_owner == _thread_run)
 497                                 ret = mutex_self_lock(*mutex);
 498                         else {
 499                                 /*
 500                                  * Join the queue of threads waiting to lock
 501                                  * the mutex:
 502                                  */
 503                                 mutex_queue_enq(*mutex, _thread_run);
 504
 505                                 /*
 506                                  * Keep a pointer to the mutex this thread
 507                                  * is waiting on:
 508                                  */
 509                                 _thread_run->data.mutex = *mutex;
 510
 511                                 if (_thread_run->active_priority >
 512                                     (*mutex)->m_prio)
 513                                         /* Adjust priorities: */
 514                                         mutex_priority_adjust(*mutex);
 515
 516                                 /*
 517                                  * Unlock the mutex structure and schedule the
 518                                  * next thread:
 519                                  */
 520                                 _thread_kern_sched_state_unlock(PS_MUTEX_WAIT,
 521                                     &(*mutex)->lock, __FILE__, __LINE__);
 522
 523                                 /* Lock the mutex structure again: */
 524                                 _SPINLOCK(&(*mutex)->lock);
 525                         }
 526                         break;
 527
 528                 /* POSIX priority protection mutex: */
 529                 case PTHREAD_PRIO_PROTECT:
 530                         /* Check for a priority ceiling violation: */
 531                         if (_thread_run->active_priority > (*mutex)->m_prio)
 532                                 ret = EINVAL;
 533
 534                         /* Check if this mutex is not locked: */
 535                         else if ((*mutex)->m_owner == NULL) {
 536                                 /*
 537                                  * Lock the mutex for the running
 538                                  * thread:
 539                                  */
 540                                 (*mutex)->m_owner = _thread_run;
 541
 542                                 /* Track number of priority mutexes owned: */
 543                                 _thread_run->priority_mutex_count++;
 544
 545                                 /*
 546                                  * The running thread inherits the ceiling
 547                                  * priority of the mutex and executes at that
 548                                  * priority:
 549                                  */
 550                                 _thread_run->active_priority = (*mutex)->m_prio;
 551                                 (*mutex)->m_saved_prio =
 552                                     _thread_run->inherited_priority;
 553                                 _thread_run->inherited_priority =
 554                                     (*mutex)->m_prio;
 555
 556                                 /* Add to the list of owned mutexes: */
 557                                 _MUTEX_ASSERT_NOT_OWNED(*mutex);
 558                                 TAILQ_INSERT_TAIL(&_thread_run->mutexq,
 559                                     (*mutex), m_qe);
 560                         } else if ((*mutex)->m_owner == _thread_run)
 561                                 ret = mutex_self_lock(*mutex);
 562                         else {
 563                                 /*
 564                                  * Join the queue of threads waiting to lock
 565                                  * the mutex:
 566                                  */
 567                                 mutex_queue_enq(*mutex, _thread_run);
 568
 569                                 /*
 570                                  * Keep a pointer to the mutex this thread
 571                                  * is waiting on:
 572                                  */
 573                                 _thread_run->data.mutex = *mutex;
 574
 575                                 /* Clear any previous error: */
 576                                 _thread_run->error = 0;
 577
 578                                 /*
 579                                  * Unlock the mutex structure and schedule the
 580                                  * next thread:
 581                                  */
 582                                 _thread_kern_sched_state_unlock(PS_MUTEX_WAIT,
 583                                     &(*mutex)->lock, __FILE__, __LINE__);
 584
 585                                 /* Lock the mutex structure again: */
 586                                 _SPINLOCK(&(*mutex)->lock);
 587
 588                                 /*
 589                                  * The threads priority may have changed while
 590                                  * waiting for the mutex causing a ceiling
 591                                  * violation.
 592                                  */
 593                                 ret = _thread_run->error;
 594                                 _thread_run->error = 0;
 595                         }
 596                         break;
 597
 598                 /* Trap invalid mutex types: */
 599                 default:
 600                         /* Return an invalid argument error: */
 601                         ret = EINVAL;
 602                         break;
 603                 }
 604
 605                 /* Unlock the mutex structure: */
 606                 _SPINUNLOCK(&(*mutex)->lock);
 607
 608                 /*
 609                  * Undefer and handle pending signals, yielding if
 610                  * necessary:
 611                  */
 612                 _thread_kern_sig_undefer();
 613         }
 614
 615         /* Return the completion status: */
 616         return (ret);
 617 }
 618
 619 int
 620 pthread_mutex_unlock(pthread_mutex_t * mutex)
 621 {
 622         return (mutex_unlock_common(mutex, /* add reference */ 0));
 623 }
 624
 625 int
 626 _mutex_cv_unlock(pthread_mutex_t * mutex)
 627 {
 628         return (mutex_unlock_common(mutex, /* add reference */ 1));
 629 }
 630
 631 int
 632 _mutex_cv_lock(pthread_mutex_t * mutex)
 633 {
 634         int ret;
 635         if ((ret = pthread_mutex_lock(mutex)) == 0)
 636                 (*mutex)->m_refcount--;
 637         return (ret);
 638 }
 639
 640 static inline int
 641 mutex_self_trylock(pthread_mutex_t mutex)
 642 {
 643         int ret = 0;
 644
 645         switch (mutex->m_type) {
 646
 647         /* case PTHREAD_MUTEX_DEFAULT: */
 648         case PTHREAD_MUTEX_ERRORCHECK:
 649         case PTHREAD_MUTEX_NORMAL:
 650                 /*
 651                  * POSIX specifies that mutexes should return EDEADLK if a
 652                  * recursive lock is detected.
 653                  */
 654                 ret = EBUSY;
 655                 break;
 656
 657         case PTHREAD_MUTEX_RECURSIVE:
 658                 /* Increment the lock count: */
 659                 mutex->m_data.m_count++;
 660                 break;
 661
 662         default:
 663                 /* Trap invalid mutex types; */
 664                 ret = EINVAL;
 665         }
 666
 667         return(ret);
 668 }
 669
 670 static inline int
 671 mutex_self_lock(pthread_mutex_t mutex)
 672 {
 673         int ret = 0;
 674
 675         switch (mutex->m_type) {
 676         /* case PTHREAD_MUTEX_DEFAULT: */
 677         case PTHREAD_MUTEX_ERRORCHECK:
 678                 /*
 679                  * POSIX specifies that mutexes should return EDEADLK if a
 680                  * recursive lock is detected.
 681                  */
 682                 ret = EDEADLK;
 683                 break;
 684
 685         case PTHREAD_MUTEX_NORMAL:
 686                 /*
 687                  * What SS2 define as a 'normal' mutex.  Intentionally
 688                  * deadlock on attempts to get a lock you already own.
 689                  */
 690                 _thread_kern_sched_state_unlock(PS_DEADLOCK,
 691                     &mutex->lock, __FILE__, __LINE__);
 692                 break;
 693
 694         case PTHREAD_MUTEX_RECURSIVE:
 695                 /* Increment the lock count: */
 696                 mutex->m_data.m_count++;
 697                 break;
 698
 699         default:
 700                 /* Trap invalid mutex types; */
 701                 ret = EINVAL;
 702         }
 703
 704         return(ret);
 705 }
 706
 707 static inline int
 708 mutex_unlock_common(pthread_mutex_t * mutex, int add_reference)
 709 {
 710         int ret = 0;
 711
 712         if (mutex == NULL || *mutex == NULL) {
 713                 ret = EINVAL;
 714         } else {
 715                 /*
 716                  * Defer signals to protect the scheduling queues from
 717                  * access by the signal handler:
 718                  */
 719                 _thread_kern_sig_defer();
 720
 721                 /* Lock the mutex structure: */
 722                 _SPINLOCK(&(*mutex)->lock);
 723
 724                 /* Process according to mutex type: */
 725                 switch ((*mutex)->m_protocol) {
 726                 /* Default POSIX mutex: */
 727                 case PTHREAD_PRIO_NONE:
 728                         /*
 729                          * Check if the running thread is not the owner of the
 730                          * mutex:
 731                          */
 732                         if ((*mutex)->m_owner != _thread_run) {
 733                                 /*
 734                                  * Return an invalid argument error for no
 735                                  * owner and a permission error otherwise:
 736                                  */
 737                                 ret = (*mutex)->m_owner == NULL ? EINVAL : EPERM;
 738                         }
 739                         else if (((*mutex)->m_type == PTHREAD_MUTEX_RECURSIVE) &&
 740                             ((*mutex)->m_data.m_count > 1)) {
 741                                 /* Decrement the count: */
 742                                 (*mutex)->m_data.m_count--;
 743                         } else {
 744                                 /*
 745                                  * Clear the count in case this is recursive
 746                                  * mutex.
 747                                  */
 748                                 (*mutex)->m_data.m_count = 0;
 749
 750                                 /* Remove the mutex from the threads queue. */
 751                                 _MUTEX_ASSERT_IS_OWNED(*mutex);
 752                                 TAILQ_REMOVE(&(*mutex)->m_owner->mutexq,
 753                                     (*mutex), m_qe);
 754                                 _MUTEX_INIT_LINK(*mutex);
 755
 756                                 /*
 757                                  * Get the next thread from the queue of
 758                                  * threads waiting on the mutex:
 759                                  */
 760                                 if (((*mutex)->m_owner =
 761                                     mutex_queue_deq(*mutex)) != NULL) {
 762                                         /*
 763                                          * Allow the new owner of the mutex to
 764                                          * run:
 765                                          */
 766                                         PTHREAD_NEW_STATE((*mutex)->m_owner,
 767                                             PS_RUNNING);
 768
 769                                         /*
 770                                          * Add the mutex to the threads list of
 771                                          * owned mutexes:
 772                                          */
 773                                         TAILQ_INSERT_TAIL(&(*mutex)->m_owner->mutexq,
 774                                             (*mutex), m_qe);
 775
 776                                         /*
 777                                          * The owner is no longer waiting for
 778                                          * this mutex:
 779                                          */
 780                                         (*mutex)->m_owner->data.mutex = NULL;
 781                                 }
 782                         }
 783                         break;
 784
 785                 /* POSIX priority inheritence mutex: */
 786                 case PTHREAD_PRIO_INHERIT:
 787                         /*
 788                          * Check if the running thread is not the owner of the
 789                          * mutex:
 790                          */
 791                         if ((*mutex)->m_owner != _thread_run) {
 792                                 /*
 793                                  * Return an invalid argument error for no
 794                                  * owner and a permission error otherwise:
 795                                  */
 796                                 ret = (*mutex)->m_owner == NULL ? EINVAL : EPERM;
 797                         }
 798                         else if (((*mutex)->m_type == PTHREAD_MUTEX_RECURSIVE) &&
 799                             ((*mutex)->m_data.m_count > 1)) {
 800                                 /* Decrement the count: */
 801                                 (*mutex)->m_data.m_count--;
 802                         } else {
 803                                 /*
 804                                  * Clear the count in case this is recursive
 805                                  * mutex.
 806                                  */
 807                                 (*mutex)->m_data.m_count = 0;
 808
 809                                 /*
 810                                  * Restore the threads inherited priority and
 811                                  * recompute the active priority (being careful
 812                                  * not to override changes in the threads base
 813                                  * priority subsequent to locking the mutex).
 814                                  */
 815                                 _thread_run->inherited_priority =
 816                                         (*mutex)->m_saved_prio;
 817                                 _thread_run->active_priority =
 818                                     MAX(_thread_run->inherited_priority,
 819                                     _thread_run->base_priority);
 820
 821                                 /*
 822                                  * This thread now owns one less priority mutex.
 823                                  */
 824                                 _thread_run->priority_mutex_count--;
 825
 826                                 /* Remove the mutex from the threads queue. */
 827                                 _MUTEX_ASSERT_IS_OWNED(*mutex);
 828                                 TAILQ_REMOVE(&(*mutex)->m_owner->mutexq,
 829                                     (*mutex), m_qe);
 830                                 _MUTEX_INIT_LINK(*mutex);
 831
 832                                 /*
 833                                  * Get the next thread from the queue of threads
 834                                  * waiting on the mutex:
 835                                  */
 836                                 if (((*mutex)->m_owner =
 837                                     mutex_queue_deq(*mutex)) == NULL)
 838                                         /* This mutex has no priority. */
 839                                         (*mutex)->m_prio = 0;
 840                                 else {
 841                                         /*
 842                                          * Track number of priority mutexes owned:
 843                                          */
 844                                         (*mutex)->m_owner->priority_mutex_count++;
 845
 846                                         /*
 847                                          * Add the mutex to the threads list
 848                                          * of owned mutexes:
 849                                          */
 850                                         TAILQ_INSERT_TAIL(&(*mutex)->m_owner->mutexq,
 851                                             (*mutex), m_qe);
 852
 853                                         /*
 854                                          * The owner is no longer waiting for
 855                                          * this mutex:
 856                                          */
 857                                         (*mutex)->m_owner->data.mutex = NULL;
 858
 859                                         /*
 860                                          * Set the priority of the mutex.  Since
 861                                          * our waiting threads are in descending
 862                                          * priority order, the priority of the
 863                                          * mutex becomes the active priority of
 864                                          * the thread we just dequeued.
 865                                          */
 866                                         (*mutex)->m_prio =
 867                                             (*mutex)->m_owner->active_priority;
 868
 869                                         /*
 870                                          * Save the owning threads inherited
 871                                          * priority:
 872                                          */
 873                                         (*mutex)->m_saved_prio =
 874                                                 (*mutex)->m_owner->inherited_priority;
 875
 876                                         /*
 877                                          * The owning threads inherited priority
 878                                          * now becomes his active priority (the
 879                                          * priority of the mutex).
 880                                          */
 881                                         (*mutex)->m_owner->inherited_priority =
 882                                                 (*mutex)->m_prio;
 883
 884                                         /*
 885                                          * Allow the new owner of the mutex to
 886                                          * run:
 887                                          */
 888                                         PTHREAD_NEW_STATE((*mutex)->m_owner,
 889                                             PS_RUNNING);
 890                                 }
 891                         }
 892                         break;
 893
 894                 /* POSIX priority ceiling mutex: */
 895                 case PTHREAD_PRIO_PROTECT:
 896                         /*
 897                          * Check if the running thread is not the owner of the
 898                          * mutex:
 899                          */
 900                         if ((*mutex)->m_owner != _thread_run) {
 901                                 /*
 902                                  * Return an invalid argument error for no
 903                                  * owner and a permission error otherwise:
 904                                  */
 905                                 ret = (*mutex)->m_owner == NULL ? EINVAL : EPERM;
 906                         }
 907                         else if (((*mutex)->m_type == PTHREAD_MUTEX_RECURSIVE) &&
 908                             ((*mutex)->m_data.m_count > 1)) {
 909                                 /* Decrement the count: */
 910                                 (*mutex)->m_data.m_count--;
 911                         } else {
 912                                 /*
 913                                  * Clear the count in case this is recursive
 914                                  * mutex.
 915                                  */
 916                                 (*mutex)->m_data.m_count = 0;
 917
 918                                 /*
 919                                  * Restore the threads inherited priority and
 920                                  * recompute the active priority (being careful
 921                                  * not to override changes in the threads base
 922                                  * priority subsequent to locking the mutex).
 923                                  */
 924                                 _thread_run->inherited_priority =
 925                                         (*mutex)->m_saved_prio;
 926                                 _thread_run->active_priority =
 927                                     MAX(_thread_run->inherited_priority,
 928                                     _thread_run->base_priority);
 929
 930                                 /*
 931                                  * This thread now owns one less priority mutex.
 932                                  */
 933                                 _thread_run->priority_mutex_count--;
 934
 935                                 /* Remove the mutex from the threads queue. */
 936                                 _MUTEX_ASSERT_IS_OWNED(*mutex);
 937                                 TAILQ_REMOVE(&(*mutex)->m_owner->mutexq,
 938                                     (*mutex), m_qe);
 939                                 _MUTEX_INIT_LINK(*mutex);
 940
 941                                 /*
 942                                  * Enter a loop to find a waiting thread whose
 943                                  * active priority will not cause a ceiling
 944                                  * violation:
 945                                  */
 946                                 while ((((*mutex)->m_owner =
 947                                     mutex_queue_deq(*mutex)) != NULL) &&
 948                                     ((*mutex)->m_owner->active_priority >
 949                                      (*mutex)->m_prio)) {
 950                                         /*
 951                                          * Either the mutex ceiling priority
 952                                          * been lowered and/or this threads
 953                                          * priority has been raised subsequent
 954                                          * to this thread being queued on the
 955                                          * waiting list.
 956                                          */
 957                                         (*mutex)->m_owner->error = EINVAL;
 958                                         PTHREAD_NEW_STATE((*mutex)->m_owner,
 959                                             PS_RUNNING);
 960                                         /*
 961                                          * The thread is no longer waiting for
 962                                          * this mutex:
 963                                          */
 964                                         (*mutex)->m_owner->data.mutex = NULL;
 965                                 }
 966
 967                                 /* Check for a new owner: */
 968                                 if ((*mutex)->m_owner != NULL) {
 969                                         /*
 970                                          * Track number of priority mutexes owned:
 971                                          */
 972                                         (*mutex)->m_owner->priority_mutex_count++;
 973
 974                                         /*
 975                                          * Add the mutex to the threads list
 976                                          * of owned mutexes:
 977                                          */
 978                                         TAILQ_INSERT_TAIL(&(*mutex)->m_owner->mutexq,
 979                                             (*mutex), m_qe);
 980
 981                                         /*
 982                                          * The owner is no longer waiting for
 983                                          * this mutex:
 984                                          */
 985                                         (*mutex)->m_owner->data.mutex = NULL;
 986
 987                                         /*
 988                                          * Save the owning threads inherited
 989                                          * priority:
 990                                          */
 991                                         (*mutex)->m_saved_prio =
 992                                                 (*mutex)->m_owner->inherited_priority;
 993
 994                                         /*
 995                                          * The owning thread inherits the
 996                                          * ceiling priority of the mutex and
 997                                          * executes at that priority:
 998                                          */
 999                                         (*mutex)->m_owner->inherited_priority =
1000                                             (*mutex)->m_prio;
1001                                         (*mutex)->m_owner->active_priority =
1002                                             (*mutex)->m_prio;
1003
1004                                         /*
1005                                          * Allow the new owner of the mutex to
1006                                          * run:
1007                                          */
1008                                         PTHREAD_NEW_STATE((*mutex)->m_owner,
1009                                             PS_RUNNING);
1010                                 }
1011                         }
1012                         break;
1013
1014                 /* Trap invalid mutex types: */
1015                 default:
1016                         /* Return an invalid argument error: */
1017                         ret = EINVAL;
1018                         break;
1019                 }
1020
1021                 if ((ret == 0) && (add_reference != 0)) {
1022                         /* Increment the reference count: */
1023                         (*mutex)->m_refcount++;
1024                 }
1025
1026                 /* Unlock the mutex structure: */
1027                 _SPINUNLOCK(&(*mutex)->lock);
1028
1029                 /*
1030                  * Undefer and handle pending signals, yielding if
1031                  * necessary:
1032                  */
1033                 _thread_kern_sig_undefer();
1034         }
1035
1036         /* Return the completion status: */
1037         return (ret);
1038 }
1039
1040
1041 /*
1042  * This function is called when a change in base priority occurs for
1043  * a thread that is holding or waiting for a priority protection or
1044  * inheritence mutex.  A change in a threads base priority can effect
1045  * changes to active priorities of other threads and to the ordering
1046  * of mutex locking by waiting threads.
1047  *
1048  * This must be called while thread scheduling is deferred.
1049  */
1050 void
1051 _mutex_notify_priochange(pthread_t pthread)
1052 {
1053         /* Adjust the priorites of any owned priority mutexes: */
1054         if (pthread->priority_mutex_count > 0) {
1055                 /*
1056                  * Rescan the mutexes owned by this thread and correct
1057                  * their priorities to account for this threads change
1058                  * in priority.  This has the side effect of changing
1059                  * the threads active priority.
1060                  */
1061                 mutex_rescan_owned(pthread, /* rescan all owned */ NULL);
1062         }
1063
1064         /*
1065          * If this thread is waiting on a priority inheritence mutex,
1066          * check for priority adjustments.  A change in priority can
1067          * also effect a ceiling violation(*) for a thread waiting on
1068          * a priority protection mutex; we don't perform the check here
1069          * as it is done in pthread_mutex_unlock.
1070          *
1071          * (*) It should be noted that a priority change to a thread
1072          *     _after_ taking and owning a priority ceiling mutex
1073          *     does not affect ownership of that mutex; the ceiling
1074          *     priority is only checked before mutex ownership occurs.
1075          */
1076         if (pthread->state == PS_MUTEX_WAIT) {
1077                 /* Lock the mutex structure: */
1078                 _SPINLOCK(&pthread->data.mutex->lock);
1079
1080                 /*
1081                  * Check to make sure this thread is still in the same state
1082                  * (the spinlock above can yield the CPU to another thread):
1083                  */
1084                 if (pthread->state == PS_MUTEX_WAIT) {
1085                         /*
1086                          * Remove and reinsert this thread into the list of
1087                          * waiting threads to preserve decreasing priority
1088                          * order.
1089                          */
1090                         mutex_queue_remove(pthread->data.mutex, pthread);
1091                         mutex_queue_enq(pthread->data.mutex, pthread);
1092
1093                         if (pthread->data.mutex->m_protocol ==
1094                              PTHREAD_PRIO_INHERIT) {
1095                                 /* Adjust priorities: */
1096                                 mutex_priority_adjust(pthread->data.mutex);
1097                         }
1098                 }
1099
1100                 /* Unlock the mutex structure: */
1101                 _SPINUNLOCK(&pthread->data.mutex->lock);
1102         }
1103 }
1104
1105 /*
1106  * Called when a new thread is added to the mutex waiting queue or
1107  * when a threads priority changes that is already in the mutex
1108  * waiting queue.
1109  */
1110 static void
1111 mutex_priority_adjust(pthread_mutex_t mutex)
1112 {
1113         pthread_t       pthread_next, pthread = mutex->m_owner;
1114         int             temp_prio;
1115         pthread_mutex_t m = mutex;
1116
1117         /*
1118          * Calculate the mutex priority as the maximum of the highest
1119          * active priority of any waiting threads and the owning threads
1120          * active priority(*).
1121          *
1122          * (*) Because the owning threads current active priority may
1123          *     reflect priority inherited from this mutex (and the mutex
1124          *     priority may have changed) we must recalculate the active
1125          *     priority based on the threads saved inherited priority
1126          *     and its base priority.
1127          */
1128         pthread_next = TAILQ_FIRST(&m->m_queue);  /* should never be NULL */
1129         temp_prio = MAX(pthread_next->active_priority,
1130             MAX(m->m_saved_prio, pthread->base_priority));
1131
1132         /* See if this mutex really needs adjusting: */
1133         if (temp_prio == m->m_prio)
1134                 /* No need to propagate the priority: */
1135                 return;
1136
1137         /* Set new priority of the mutex: */
1138         m->m_prio = temp_prio;
1139
1140         while (m != NULL) {
1141                 /*
1142                  * Save the threads priority before rescanning the
1143                  * owned mutexes:
1144                  */
1145                 temp_prio = pthread->active_priority;
1146
1147                 /*
1148                  * Fix the priorities for all the mutexes this thread has
1149                  * locked since taking this mutex.  This also has a
1150                  * potential side-effect of changing the threads priority.
1151                  */
1152                 mutex_rescan_owned(pthread, m);
1153
1154                 /*
1155                  * If the thread is currently waiting on a mutex, check
1156                  * to see if the threads new priority has affected the
1157                  * priority of the mutex.
1158                  */
1159                 if ((temp_prio != pthread->active_priority) &&
1160                     (pthread->state == PS_MUTEX_WAIT) &&
1161                     (pthread->data.mutex->m_protocol == PTHREAD_PRIO_INHERIT)) {
1162                         /* Grab the mutex this thread is waiting on: */
1163                         m = pthread->data.mutex;
1164
1165                         /*
1166                          * The priority for this thread has changed.  Remove
1167                          * and reinsert this thread into the list of waiting
1168                          * threads to preserve decreasing priority order.
1169                          */
1170                         mutex_queue_remove(m, pthread);
1171                         mutex_queue_enq(m, pthread);
1172
1173                         /* Grab the waiting thread with highest priority: */
1174                         pthread_next = TAILQ_FIRST(&m->m_queue);
1175
1176                         /*
1177                          * Calculate the mutex priority as the maximum of the
1178                          * highest active priority of any waiting threads and
1179                          * the owning threads active priority.
1180                          */
1181                         temp_prio = MAX(pthread_next->active_priority,
1182                             MAX(m->m_saved_prio, m->m_owner->base_priority));
1183
1184                         if (temp_prio != m->m_prio) {
1185                                 /*
1186                                  * The priority needs to be propagated to the
1187                                  * mutex this thread is waiting on and up to
1188                                  * the owner of that mutex.
1189                                  */
1190                                 m->m_prio = temp_prio;
1191                                 pthread = m->m_owner;
1192                         }
1193                         else
1194                                 /* We're done: */
1195                                 m = NULL;
1196
1197                 }
1198                 else
1199                         /* We're done: */
1200                         m = NULL;
1201         }
1202 }
1203
1204 static void
1205 mutex_rescan_owned (pthread_t pthread, pthread_mutex_t mutex)
1206 {
1207         int             active_prio, inherited_prio;
1208         pthread_mutex_t m;
1209         pthread_t       pthread_next;
1210
1211         /*
1212          * Start walking the mutexes the thread has taken since
1213          * taking this mutex.
1214          */
1215         if (mutex == NULL) {
1216                 /*
1217                  * A null mutex means start at the beginning of the owned
1218                  * mutex list.
1219                  */
1220                 m = TAILQ_FIRST(&pthread->mutexq);
1221
1222                 /* There is no inherited priority yet. */
1223                 inherited_prio = 0;
1224         }
1225         else {
1226                 /*
1227                  * The caller wants to start after a specific mutex.  It
1228                  * is assumed that this mutex is a priority inheritence
1229                  * mutex and that its priority has been correctly
1230                  * calculated.
1231                  */
1232                 m = TAILQ_NEXT(mutex, m_qe);
1233
1234                 /* Start inheriting priority from the specified mutex. */
1235                 inherited_prio = mutex->m_prio;
1236         }
1237         active_prio = MAX(inherited_prio, pthread->base_priority);
1238
1239         while (m != NULL) {
1240                 /*
1241                  * We only want to deal with priority inheritence
1242                  * mutexes.  This might be optimized by only placing
1243                  * priority inheritence mutexes into the owned mutex
1244                  * list, but it may prove to be useful having all
1245                  * owned mutexes in this list.  Consider a thread
1246                  * exiting while holding mutexes...
1247                  */
1248                 if (m->m_protocol == PTHREAD_PRIO_INHERIT) {
1249                         /*
1250                          * Fix the owners saved (inherited) priority to
1251                          * reflect the priority of the previous mutex.
1252                          */
1253                         m->m_saved_prio = inherited_prio;
1254
1255                         if ((pthread_next = TAILQ_FIRST(&m->m_queue)) != NULL)
1256                                 /* Recalculate the priority of the mutex: */
1257                                 m->m_prio = MAX(active_prio,
1258                                      pthread_next->active_priority);
1259                         else
1260                                 m->m_prio = active_prio;
1261
1262                         /* Recalculate new inherited and active priorities: */
1263                         inherited_prio = m->m_prio;
1264                         active_prio = MAX(m->m_prio, pthread->base_priority);
1265                 }
1266
1267                 /* Advance to the next mutex owned by this thread: */
1268                 m = TAILQ_NEXT(m, m_qe);
1269         }
1270
1271         /*
1272          * Fix the threads inherited priority and recalculate its
1273          * active priority.
1274          */
1275         pthread->inherited_priority = inherited_prio;
1276         active_prio = MAX(inherited_prio, pthread->base_priority);
1277
1278         if (active_prio != pthread->active_priority) {
1279                 /*
1280                  * If this thread is in the priority queue, it must be
1281                  * removed and reinserted for its new priority.
1282                  */
1283                 if (pthread->flags & PTHREAD_FLAGS_IN_PRIOQ) {
1284                         /*
1285                          * Remove the thread from the priority queue
1286                          * before changing its priority:
1287                          */
1288                         PTHREAD_PRIOQ_REMOVE(pthread);
1289
1290                         /*
1291                          * POSIX states that if the priority is being
1292                          * lowered, the thread must be inserted at the
1293                          * head of the queue for its priority if it owns
1294                          * any priority protection or inheritence mutexes.
1295                          */
1296                         if ((active_prio < pthread->active_priority) &&
1297                             (pthread->priority_mutex_count > 0)) {
1298                                 /* Set the new active priority. */
1299                                 pthread->active_priority = active_prio;
1300
1301                                 PTHREAD_PRIOQ_INSERT_HEAD(pthread);
1302                         }
1303                         else {
1304                                 /* Set the new active priority. */
1305                                 pthread->active_priority = active_prio;
1306
1307                                 PTHREAD_PRIOQ_INSERT_TAIL(pthread);
1308                         }
1309                 }
1310                 else {
1311                         /* Set the new active priority. */
1312                         pthread->active_priority = active_prio;
1313                 }
1314         }
1315 }
1316
1317 /*
1318  * Dequeue a waiting thread from the head of a mutex queue in descending
1319  * priority order.
1320  */
1321 static inline pthread_t
1322 mutex_queue_deq(pthread_mutex_t mutex)
1323 {
1324         pthread_t pthread;
1325
1326         if ((pthread = TAILQ_FIRST(&mutex->m_queue)) != NULL)
1327                 TAILQ_REMOVE(&mutex->m_queue, pthread, qe);
1328
1329         return(pthread);
1330 }
1331
1332 /*
1333  * Remove a waiting thread from a mutex queue in descending priority order.
1334  */
1335 static inline void
1336 mutex_queue_remove(pthread_mutex_t mutex, pthread_t pthread)
1337 {
1338         TAILQ_REMOVE(&mutex->m_queue, pthread, qe);
1339 }
1340
1341 /*
1342  * Enqueue a waiting thread to a queue in descending priority order.
1343  */
1344 static inline void
1345 mutex_queue_enq(pthread_mutex_t mutex, pthread_t pthread)
1346 {
1347         pthread_t tid = TAILQ_LAST(&mutex->m_queue, mutex_head);
1348
1349         /*
1350          * For the common case of all threads having equal priority,
1351          * we perform a quick check against the priority of the thread
1352          * at the tail of the queue.
1353          */
1354         if ((tid == NULL) || (pthread->active_priority <= tid->active_priority))
1355                 TAILQ_INSERT_TAIL(&mutex->m_queue, pthread, qe);
1356         else {
1357                 tid = TAILQ_FIRST(&mutex->m_queue);
1358                 while (pthread->active_priority <= tid->active_priority)
1359                         tid = TAILQ_NEXT(tid, qe);
1360                 TAILQ_INSERT_BEFORE(tid, pthread, qe);
1361         }
1362 }
1363
1364 #endif