1 /*
2 * Copyright (C) 2008 The Android Open Source Project
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 * * Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * * Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in
12 * the documentation and/or other materials provided with the
13 * distribution.
14 *
15 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
16 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
17 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
18 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
19 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
20 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
21 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
22 * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
23 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
24 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
25 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
26 * SUCH DAMAGE.
27 */
28 #include <semaphore.h>
29 #include <errno.h>
30 #include <sys/time.h>
31 #include <time.h>
32 #include <limits.h>
33
34 #include "private/bionic_atomic_inline.h"
35 #include "private/bionic_futex.h"
36
37 /* In this implementation, a semaphore contains a
38 * 31-bit signed value and a 1-bit 'shared' flag
39 * (for process-sharing purpose).
40 *
41 * We use the value -1 to indicate contention on the
42 * semaphore, 0 or more to indicate uncontended state,
43 * any value lower than -2 is invalid at runtime.
44 *
45 * State diagram:
46 *
47 * post(1) ==> 2
48 * post(0) ==> 1
49 * post(-1) ==> 1, then wake all waiters
50 *
51 * wait(2) ==> 1
52 * wait(1) ==> 0
53 * wait(0) ==> -1 then wait for a wake up + loop
54 * wait(-1) ==> -1 then wait for a wake up + loop
55 *
56 */
57
58 /* Use the upper 31-bits for the counter, and the lower one
59 * for the shared flag.
60 */
61 #define SEMCOUNT_SHARED_MASK 0x00000001
62 #define SEMCOUNT_VALUE_MASK 0xfffffffe
63 #define SEMCOUNT_VALUE_SHIFT 1
64
65 /* Maximum unsigned value that can be stored in the semaphore.
66 * One bit is used for the shared flag, another one for the
67 * sign bit, leaving us with only 30 bits.
68 */
69 #define SEM_MAX_VALUE 0x3fffffff
70
71 /* convert a value into the corresponding sem->count bit pattern */
72 #define SEMCOUNT_FROM_VALUE(val) (((val) << SEMCOUNT_VALUE_SHIFT) & SEMCOUNT_VALUE_MASK)
73
74 /* convert a sem->count bit pattern into the corresponding signed value */
75 #define SEMCOUNT_TO_VALUE(sval) ((int)(sval) >> SEMCOUNT_VALUE_SHIFT)
76
77 /* the value +1 as a sem->count bit-pattern. */
78 #define SEMCOUNT_ONE SEMCOUNT_FROM_VALUE(1)
79
80 /* the value -1 as a sem->count bit-pattern. */
81 #define SEMCOUNT_MINUS_ONE SEMCOUNT_FROM_VALUE(-1)
82
83 #define SEMCOUNT_DECREMENT(sval) (((sval) - (1U << SEMCOUNT_VALUE_SHIFT)) & SEMCOUNT_VALUE_MASK)
84 #define SEMCOUNT_INCREMENT(sval) (((sval) + (1U << SEMCOUNT_VALUE_SHIFT)) & SEMCOUNT_VALUE_MASK)
85
86 /* return the shared bitflag from a semaphore */
87 #define SEM_GET_SHARED(sem) ((sem)->count & SEMCOUNT_SHARED_MASK)
88
89
sem_init(sem_t * sem,int pshared,unsigned int value)90 int sem_init(sem_t *sem, int pshared, unsigned int value)
91 {
92 if (sem == NULL) {
93 errno = EINVAL;
94 return -1;
95 }
96
97 /* ensure that 'value' can be stored in the semaphore */
98 if (value > SEM_MAX_VALUE) {
99 errno = EINVAL;
100 return -1;
101 }
102
103 sem->count = SEMCOUNT_FROM_VALUE(value);
104 if (pshared != 0)
105 sem->count |= SEMCOUNT_SHARED_MASK;
106
107 return 0;
108 }
109
110
sem_destroy(sem_t * sem)111 int sem_destroy(sem_t *sem)
112 {
113 int count;
114
115 if (sem == NULL) {
116 errno = EINVAL;
117 return -1;
118 }
119 count = SEMCOUNT_TO_VALUE(sem->count);
120 if (count < 0) {
121 errno = EBUSY;
122 return -1;
123 }
124 sem->count = 0;
125 return 0;
126 }
127
128
sem_open(const char * name __unused,int oflag __unused,...)129 sem_t *sem_open(const char *name __unused, int oflag __unused, ...)
130 {
131 errno = ENOSYS;
132 return SEM_FAILED;
133 }
134
135
sem_close(sem_t * sem)136 int sem_close(sem_t *sem)
137 {
138 if (sem == NULL) {
139 errno = EINVAL;
140 return -1;
141 }
142 errno = ENOSYS;
143 return -1;
144 }
145
146
sem_unlink(const char * name __unused)147 int sem_unlink(const char* name __unused)
148 {
149 errno = ENOSYS;
150 return -1;
151 }
152
153
154 /* Decrement a semaphore's value atomically,
155 * and return the old one. As a special case,
156 * this returns immediately if the value is
157 * negative (i.e. -1)
158 */
159 static int
__sem_dec(volatile unsigned int * pvalue)160 __sem_dec(volatile unsigned int *pvalue)
161 {
162 unsigned int shared = (*pvalue & SEMCOUNT_SHARED_MASK);
163 unsigned int old, new;
164 int ret;
165
166 do {
167 old = (*pvalue & SEMCOUNT_VALUE_MASK);
168 ret = SEMCOUNT_TO_VALUE(old);
169 if (ret < 0)
170 break;
171
172 new = SEMCOUNT_DECREMENT(old);
173 }
174 while (__bionic_cmpxchg((int)(old|shared),
175 (int)(new|shared),
176 (volatile int *)pvalue) != 0);
177 return ret;
178 }
179
180 /* Same as __sem_dec, but will not touch anything if the
181 * value is already negative *or* 0. Returns the old value.
182 */
183 static int
__sem_trydec(volatile unsigned int * pvalue)184 __sem_trydec(volatile unsigned int *pvalue)
185 {
186 unsigned int shared = (*pvalue & SEMCOUNT_SHARED_MASK);
187 unsigned int old, new;
188 int ret;
189
190 do {
191 old = (*pvalue & SEMCOUNT_VALUE_MASK);
192 ret = SEMCOUNT_TO_VALUE(old);
193 if (ret <= 0)
194 break;
195
196 new = SEMCOUNT_DECREMENT(old);
197 }
198 while (__bionic_cmpxchg((int)(old|shared),
199 (int)(new|shared),
200 (volatile int *)pvalue) != 0);
201
202 return ret;
203 }
204
205
206 /* "Increment" the value of a semaphore atomically and
207 * return its old value. Note that this implements
208 * the special case of "incrementing" any negative
209 * value to +1 directly.
210 *
211 * NOTE: The value will _not_ wrap above SEM_VALUE_MAX
212 */
213 static int
__sem_inc(volatile unsigned int * pvalue)214 __sem_inc(volatile unsigned int *pvalue)
215 {
216 unsigned int shared = (*pvalue & SEMCOUNT_SHARED_MASK);
217 unsigned int old, new;
218 int ret;
219
220 do {
221 old = (*pvalue & SEMCOUNT_VALUE_MASK);
222 ret = SEMCOUNT_TO_VALUE(old);
223
224 /* Can't go higher than SEM_MAX_VALUE */
225 if (ret == SEM_MAX_VALUE)
226 break;
227
228 /* If the counter is negative, go directly to +1,
229 * otherwise just increment */
230 if (ret < 0)
231 new = SEMCOUNT_ONE;
232 else
233 new = SEMCOUNT_INCREMENT(old);
234 }
235 while ( __bionic_cmpxchg((int)(old|shared),
236 (int)(new|shared),
237 (volatile int*)pvalue) != 0);
238
239 return ret;
240 }
241
242 /* lock a semaphore */
sem_wait(sem_t * sem)243 int sem_wait(sem_t *sem)
244 {
245 unsigned shared;
246
247 if (sem == NULL) {
248 errno = EINVAL;
249 return -1;
250 }
251
252 shared = SEM_GET_SHARED(sem);
253
254 for (;;) {
255 if (__sem_dec(&sem->count) > 0)
256 break;
257
258 __futex_wait_ex(&sem->count, shared, shared|SEMCOUNT_MINUS_ONE, NULL);
259 }
260 ANDROID_MEMBAR_FULL();
261 return 0;
262 }
263
sem_timedwait(sem_t * sem,const struct timespec * abs_timeout)264 int sem_timedwait(sem_t *sem, const struct timespec *abs_timeout)
265 {
266 unsigned int shared;
267
268 if (sem == NULL) {
269 errno = EINVAL;
270 return -1;
271 }
272
273 /* POSIX says we need to try to decrement the semaphore
274 * before checking the timeout value. Note that if the
275 * value is currently 0, __sem_trydec() does nothing.
276 */
277 if (__sem_trydec(&sem->count) > 0) {
278 ANDROID_MEMBAR_FULL();
279 return 0;
280 }
281
282 /* Check it as per Posix */
283 if (abs_timeout == NULL ||
284 abs_timeout->tv_sec < 0 ||
285 abs_timeout->tv_nsec < 0 ||
286 abs_timeout->tv_nsec >= 1000000000)
287 {
288 errno = EINVAL;
289 return -1;
290 }
291
292 shared = SEM_GET_SHARED(sem);
293
294 for (;;) {
295 struct timespec ts;
296 int ret;
297
298 /* Posix mandates CLOCK_REALTIME here */
299 clock_gettime( CLOCK_REALTIME, &ts );
300 ts.tv_sec = abs_timeout->tv_sec - ts.tv_sec;
301 ts.tv_nsec = abs_timeout->tv_nsec - ts.tv_nsec;
302 if (ts.tv_nsec < 0) {
303 ts.tv_nsec += 1000000000;
304 ts.tv_sec -= 1;
305 }
306
307 if (ts.tv_sec < 0 || ts.tv_nsec < 0) {
308 errno = ETIMEDOUT;
309 return -1;
310 }
311
312 /* Try to grab the semaphore. If the value was 0, this
313 * will also change it to -1 */
314 if (__sem_dec(&sem->count) > 0) {
315 ANDROID_MEMBAR_FULL();
316 break;
317 }
318
319 /* Contention detected. wait for a wakeup event */
320 ret = __futex_wait_ex(&sem->count, shared, shared|SEMCOUNT_MINUS_ONE, &ts);
321
322 /* return in case of timeout or interrupt */
323 if (ret == -ETIMEDOUT || ret == -EINTR) {
324 errno = -ret;
325 return -1;
326 }
327 }
328 return 0;
329 }
330
331 /* Unlock a semaphore */
sem_post(sem_t * sem)332 int sem_post(sem_t *sem)
333 {
334 unsigned int shared;
335 int old;
336
337 if (sem == NULL)
338 return EINVAL;
339
340 shared = SEM_GET_SHARED(sem);
341
342 ANDROID_MEMBAR_FULL();
343 old = __sem_inc(&sem->count);
344 if (old < 0) {
345 /* contention on the semaphore, wake up all waiters */
346 __futex_wake_ex(&sem->count, shared, INT_MAX);
347 }
348 else if (old == SEM_MAX_VALUE) {
349 /* overflow detected */
350 errno = EOVERFLOW;
351 return -1;
352 }
353
354 return 0;
355 }
356
sem_trywait(sem_t * sem)357 int sem_trywait(sem_t *sem)
358 {
359 if (sem == NULL) {
360 errno = EINVAL;
361 return -1;
362 }
363
364 if (__sem_trydec(&sem->count) > 0) {
365 ANDROID_MEMBAR_FULL();
366 return 0;
367 } else {
368 errno = EAGAIN;
369 return -1;
370 }
371 }
372
373 /* Note that Posix requires that sem_getvalue() returns, in
374 * case of contention, the negative of the number of waiting
375 * threads.
376 *
377 * However, code that depends on this negative value to be
378 * meaningful is most probably racy. The GLibc sem_getvalue()
379 * only returns the semaphore value, which is 0, in case of
380 * contention, so we will mimick this behaviour here instead
381 * for better compatibility.
382 */
sem_getvalue(sem_t * sem,int * sval)383 int sem_getvalue(sem_t *sem, int *sval)
384 {
385 int val;
386
387 if (sem == NULL || sval == NULL) {
388 errno = EINVAL;
389 return -1;
390 }
391
392 val = SEMCOUNT_TO_VALUE(sem->count);
393 if (val < 0)
394 val = 0;
395
396 *sval = val;
397 return 0;
398 }
399