1 /* Linuxthreads - a simple clone()-based implementation of Posix */
2 /* threads for Linux. */
3 /* Copyright (C) 1996 Xavier Leroy (Xavier.Leroy@inria.fr) */
5 /* This program is free software; you can redistribute it and/or */
6 /* modify it under the terms of the GNU Library General Public License */
7 /* as published by the Free Software Foundation; either version 2 */
8 /* of the License, or (at your option) any later version. */
10 /* This program is distributed in the hope that it will be useful, */
11 /* but WITHOUT ANY WARRANTY; without even the implied warranty of */
12 /* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the */
13 /* GNU Library General Public License for more details. */
15 /* Semaphores a la POSIX 1003.1b */
18 #include "semaphore.h"
19 #include "internals.h"
23 #if !defined HAS_COMPARE_AND_SWAP && !defined TEST_FOR_COMPARE_AND_SWAP
24 /* If we have no atomic compare and swap, fake it using an extra spinlock. */
27 static inline int sem_compare_and_swap(sem_t *sem, long oldval, long newval)
30 acquire(&sem->sem_spinlock);
31 ret = (sem->sem_status == oldval);
32 if (ret) sem->sem_status = newval;
33 release(&sem->sem_spinlock);
37 #elif defined TEST_FOR_COMPARE_AND_SWAP
40 static int has_compare_and_swap = -1; /* to be determined at run-time */
42 static inline int sem_compare_and_swap(sem_t *sem, long oldval, long newval)
46 if (has_compare_and_swap == 1)
47 return __compare_and_swap(&sem->sem_status, oldval, newval);
49 acquire(&sem->sem_spinlock);
50 ret = (sem->sem_status == oldval);
51 if (ret) sem->sem_status = newval;
52 release(&sem->sem_spinlock);
57 /* But if we do have an atomic compare and swap, use it! */
59 static inline int sem_compare_and_swap(sem_t *sem, long oldval, long newval)
61 return __compare_and_swap(&sem->sem_status, oldval, newval);
67 /* The state of a semaphore is represented by a long int encoding
68 either the semaphore count if >= 0 and no thread is waiting on it,
69 or the head of the list of threads waiting for the semaphore.
70 To distinguish the two cases, we encode the semaphore count N
71 as 2N+1, so that it has the lowest bit set.
73 A sequence of sem_wait operations on a semaphore initialized to N
74 result in the following successive states:
75 2N+1, 2N-1, ..., 3, 1, &first_waiting_thread, &second_waiting_thread, ...
78 static void sem_restart_list(pthread_descr waiting);
80 int sem_init(sem_t *sem, int pshared, unsigned int value)
82 if ((long)value > SEM_VALUE_MAX) {
90 #ifdef TEST_FOR_COMPARE_AND_SWAP
91 if (has_compare_and_swap == -1) {
92 has_compare_and_swap = compare_and_swap_is_available();
95 #if !defined HAS_COMPARE_AND_SWAP || defined TEST_FOR_COMPARE_AND_SWAP
96 sem->sem_spinlock = 0;
98 sem->sem_status = ((long)value << 1) + 1;
102 int sem_wait(sem_t * sem)
104 long oldstatus, newstatus;
105 volatile pthread_descr self = thread_self();
110 oldstatus = sem->sem_status;
111 if ((oldstatus & 1) && (oldstatus != 1))
112 newstatus = oldstatus - 2;
114 newstatus = (long) self;
115 self->p_nextwaiting = (pthread_descr) oldstatus;
118 while (! sem_compare_and_swap(sem, oldstatus, newstatus));
120 /* We got the semaphore. */
122 /* Wait for sem_post or cancellation */
123 suspend_with_cancellation(self);
124 /* This is a cancellation point */
125 if (self->p_canceled && self->p_cancelstate == PTHREAD_CANCEL_ENABLE) {
126 /* Remove ourselves from the waiting list if we're still on it */
127 /* First check if we're at the head of the list. */
129 oldstatus = sem->sem_status;
130 if (oldstatus != (long) self) break;
131 newstatus = (long) self->p_nextwaiting;
133 while (! sem_compare_and_swap(sem, oldstatus, newstatus));
134 /* Now, check if we're somewhere in the list.
135 There's a race condition with sem_post here, but it does not matter:
136 the net result is that at the time pthread_exit is called,
137 self is no longer reachable from sem->sem_status. */
138 if (oldstatus != (long) self && (oldstatus & 1) == 0) {
139 for (th = &(((pthread_descr) oldstatus)->p_nextwaiting);
140 *th != NULL && *th != (pthread_descr) 1;
141 th = &((*th)->p_nextwaiting)) {
143 *th = self->p_nextwaiting;
148 pthread_exit(PTHREAD_CANCELED);
153 int sem_trywait(sem_t * sem)
155 long oldstatus, newstatus;
158 oldstatus = sem->sem_status;
159 if ((oldstatus & 1) == 0 || (oldstatus == 1)) {
163 newstatus = oldstatus - 2;
165 while (! sem_compare_and_swap(sem, oldstatus, newstatus));
169 int sem_post(sem_t * sem)
171 long oldstatus, newstatus;
174 oldstatus = sem->sem_status;
175 if ((oldstatus & 1) == 0)
178 if (oldstatus >= SEM_VALUE_MAX) {
183 newstatus = oldstatus + 2;
186 while (! sem_compare_and_swap(sem, oldstatus, newstatus));
187 if ((oldstatus & 1) == 0)
188 sem_restart_list((pthread_descr) oldstatus);
192 int sem_getvalue(sem_t * sem, int * sval)
194 long status = sem->sem_status;
196 *sval = (int)((unsigned long) status >> 1);
202 int sem_destroy(sem_t * sem)
204 if ((sem->sem_status & 1) == 0) {
211 /* Auxiliary function for restarting all threads on a waiting list,
212 in priority order. */
214 static void sem_restart_list(pthread_descr waiting)
216 pthread_descr th, towake, *p;
218 /* Sort list of waiting threads by decreasing priority (insertion sort) */
220 while (waiting != (pthread_descr) 1) {
222 waiting = waiting->p_nextwaiting;
224 while (*p != NULL && th->p_priority < (*p)->p_priority)
225 p = &((*p)->p_nextwaiting);
226 th->p_nextwaiting = *p;
229 /* Wake up threads in priority order */
230 while (towake != NULL) {
232 towake = towake->p_nextwaiting;
233 th->p_nextwaiting = NULL;