thread safe longjmp functions.
[kopensolaris-gnu/glibc.git] / linuxthreads / semaphore.c
1 /* Linuxthreads - a simple clone()-based implementation of Posix        */
2 /* threads for Linux.                                                   */
3 /* Copyright (C) 1996 Xavier Leroy (Xavier.Leroy@inria.fr)              */
4 /*                                                                      */
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.               */
9 /*                                                                      */
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.                 */
14
15 /* Semaphores a la POSIX 1003.1b */
16
17 #include "pthread.h"
18 #include "semaphore.h"
19 #include "internals.h"
20 #include "restart.h"
21
22
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.  */
25
26 #include "spinlock.h"
27 static inline int sem_compare_and_swap(sem_t *sem, long oldval, long newval)
28 {
29   int ret;
30   acquire(&sem->sem_spinlock);
31   ret = (sem->sem_status == oldval);
32   if (ret) sem->sem_status = newval;
33   release(&sem->sem_spinlock);
34   return ret;
35 }
36
37 #elif defined TEST_FOR_COMPARE_AND_SWAP
38
39 #include "spinlock.h"
40 static int has_compare_and_swap = -1; /* to be determined at run-time */
41
42 static inline int sem_compare_and_swap(sem_t *sem, long oldval, long newval)
43 {
44   int ret;
45
46   if (has_compare_and_swap == 1)
47     return __compare_and_swap(&sem->sem_status, oldval, newval);
48
49   acquire(&sem->sem_spinlock);
50   ret = (sem->sem_status == oldval);
51   if (ret) sem->sem_status = newval;
52   release(&sem->sem_spinlock);
53   return ret;
54 }
55
56 #else
57 /* But if we do have an atomic compare and swap, use it!  */
58
59 static inline int sem_compare_and_swap(sem_t *sem, long oldval, long newval)
60 {
61   return __compare_and_swap(&sem->sem_status, oldval, newval);
62 }
63
64 #endif
65
66
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.
72
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, ...
76 */
77
78 static void sem_restart_list(pthread_descr waiting);
79
80 int sem_init(sem_t *sem, int pshared, unsigned int value)
81 {
82   if ((long)value > SEM_VALUE_MAX) {
83     errno = EINVAL;
84     return -1;
85   }
86   if (pshared) {
87     errno = ENOSYS;
88     return -1;
89   }
90 #ifdef TEST_FOR_COMPARE_AND_SWAP
91   if (has_compare_and_swap == -1) {
92     has_compare_and_swap = compare_and_swap_is_available();
93   }
94 #endif
95 #if !defined HAS_COMPARE_AND_SWAP || defined TEST_FOR_COMPARE_AND_SWAP
96   sem->sem_spinlock = 0;
97 #endif
98   sem->sem_status = ((long)value << 1) + 1;
99   return 0;
100 }
101
102 int sem_wait(sem_t * sem)
103 {
104   long oldstatus, newstatus;
105   volatile pthread_descr self = thread_self();
106   pthread_descr * th;
107
108   while (1) {
109     do {
110       oldstatus = sem->sem_status;
111       if ((oldstatus & 1) && (oldstatus != 1))
112         newstatus = oldstatus - 2;
113       else {
114         newstatus = (long) self;
115         self->p_nextwaiting = (pthread_descr) oldstatus;
116       }
117     }
118     while (! sem_compare_and_swap(sem, oldstatus, newstatus));
119     if (newstatus & 1)
120       /* We got the semaphore. */
121       return 0;
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. */
128       do {
129         oldstatus = sem->sem_status;
130         if (oldstatus != (long) self) break;
131         newstatus = (long) self->p_nextwaiting;
132       }
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)) {
142           if (*th == self) {
143             *th = self->p_nextwaiting;
144             break;
145           }
146         }
147       }
148       pthread_exit(PTHREAD_CANCELED);
149     }
150   }
151 }
152
153 int sem_trywait(sem_t * sem)
154 {
155   long oldstatus, newstatus;
156
157   do {
158     oldstatus = sem->sem_status;
159     if ((oldstatus & 1) == 0 || (oldstatus == 1)) {
160       errno = EAGAIN;
161       return -1;
162     }
163     newstatus = oldstatus - 2;
164   }
165   while (! sem_compare_and_swap(sem, oldstatus, newstatus));
166   return 0;
167 }
168
169 int sem_post(sem_t * sem)
170 {
171   long oldstatus, newstatus;
172
173   do {
174     oldstatus = sem->sem_status;
175     if ((oldstatus & 1) == 0)
176       newstatus = 3;
177     else {
178       if (oldstatus >= SEM_VALUE_MAX) {
179         /* Overflow */
180         errno = ERANGE;
181         return -1;
182       }
183       newstatus = oldstatus + 2;
184     }
185   }
186   while (! sem_compare_and_swap(sem, oldstatus, newstatus));
187   if ((oldstatus & 1) == 0)
188     sem_restart_list((pthread_descr) oldstatus);
189   return 0;
190 }
191
192 int sem_getvalue(sem_t * sem, int * sval)
193 {
194   long status = sem->sem_status;
195   if (status & 1)
196     *sval = (int)((unsigned long) status >> 1);
197   else
198     *sval = 0;
199   return 0;
200 }
201
202 int sem_destroy(sem_t * sem)
203 {
204   if ((sem->sem_status & 1) == 0) {
205     errno = EBUSY;
206     return -1;
207   }
208   return 0;
209 }
210
211 /* Auxiliary function for restarting all threads on a waiting list,
212    in priority order. */
213
214 static void sem_restart_list(pthread_descr waiting)
215 {
216   pthread_descr th, towake, *p;
217
218   /* Sort list of waiting threads by decreasing priority (insertion sort) */
219   towake = NULL;
220   while (waiting != (pthread_descr) 1) {
221     th = waiting;
222     waiting = waiting->p_nextwaiting;
223     p = &towake;
224     while (*p != NULL && th->p_priority < (*p)->p_priority)
225       p = &((*p)->p_nextwaiting);
226     th->p_nextwaiting = *p;
227     *p = th;
228   }
229   /* Wake up threads in priority order */
230   while (towake != NULL) {
231     th = towake;
232     towake = towake->p_nextwaiting;
233     th->p_nextwaiting = NULL;
234     restart(th);
235   }
236 }