Backout revision 1.5, the pthread->error was used as internal
[dragonfly.git] / 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.6 2005/05/07 07:39:14 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 }