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 <sys/atomics.h>
32 #include <time.h>
33 #include <bionic_atomic_inline.h>
34 #include <bionic_futex.h>
35 #include <limits.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,int oflag,...)129 sem_t *sem_open(const char *name, int oflag, ...)
130 {
131 name=name;
132 oflag=oflag;
133
134 errno = ENOSYS;
135 return SEM_FAILED;
136 }
137
138
sem_close(sem_t * sem)139 int sem_close(sem_t *sem)
140 {
141 if (sem == NULL) {
142 errno = EINVAL;
143 return -1;
144 }
145 errno = ENOSYS;
146 return -1;
147 }
148
149
sem_unlink(const char * name)150 int sem_unlink(const char * name)
151 {
152 errno = ENOSYS;
153 return -1;
154 }
155
156
157 /* Decrement a semaphore's value atomically,
158 * and return the old one. As a special case,
159 * this returns immediately if the value is
160 * negative (i.e. -1)
161 */
162 static int
__sem_dec(volatile unsigned int * pvalue)163 __sem_dec(volatile unsigned int *pvalue)
164 {
165 unsigned int shared = (*pvalue & SEMCOUNT_SHARED_MASK);
166 unsigned int old, new;
167 int ret;
168
169 do {
170 old = (*pvalue & SEMCOUNT_VALUE_MASK);
171 ret = SEMCOUNT_TO_VALUE(old);
172 if (ret < 0)
173 break;
174
175 new = SEMCOUNT_DECREMENT(old);
176 }
177 while (__atomic_cmpxchg((int)(old|shared),
178 (int)(new|shared),
179 (volatile int *)pvalue) != 0);
180 return ret;
181 }
182
183 /* Same as __sem_dec, but will not touch anything if the
184 * value is already negative *or* 0. Returns the old value.
185 */
186 static int
__sem_trydec(volatile unsigned int * pvalue)187 __sem_trydec(volatile unsigned int *pvalue)
188 {
189 unsigned int shared = (*pvalue & SEMCOUNT_SHARED_MASK);
190 unsigned int old, new;
191 int ret;
192
193 do {
194 old = (*pvalue & SEMCOUNT_VALUE_MASK);
195 ret = SEMCOUNT_TO_VALUE(old);
196 if (ret <= 0)
197 break;
198
199 new = SEMCOUNT_DECREMENT(old);
200 }
201 while (__atomic_cmpxchg((int)(old|shared),
202 (int)(new|shared),
203 (volatile int *)pvalue) != 0);
204
205 return ret;
206 }
207
208
209 /* "Increment" the value of a semaphore atomically and
210 * return its old value. Note that this implements
211 * the special case of "incrementing" any negative
212 * value to +1 directly.
213 *
214 * NOTE: The value will _not_ wrap above SEM_VALUE_MAX
215 */
216 static int
__sem_inc(volatile unsigned int * pvalue)217 __sem_inc(volatile unsigned int *pvalue)
218 {
219 unsigned int shared = (*pvalue & SEMCOUNT_SHARED_MASK);
220 unsigned int old, new;
221 int ret;
222
223 do {
224 old = (*pvalue & SEMCOUNT_VALUE_MASK);
225 ret = SEMCOUNT_TO_VALUE(old);
226
227 /* Can't go higher than SEM_MAX_VALUE */
228 if (ret == SEM_MAX_VALUE)
229 break;
230
231 /* If the counter is negative, go directly to +1,
232 * otherwise just increment */
233 if (ret < 0)
234 new = SEMCOUNT_ONE;
235 else
236 new = SEMCOUNT_INCREMENT(old);
237 }
238 while ( __atomic_cmpxchg((int)(old|shared),
239 (int)(new|shared),
240 (volatile int*)pvalue) != 0);
241
242 return ret;
243 }
244
245 /* lock a semaphore */
sem_wait(sem_t * sem)246 int sem_wait(sem_t *sem)
247 {
248 unsigned shared;
249
250 if (sem == NULL) {
251 errno = EINVAL;
252 return -1;
253 }
254
255 shared = SEM_GET_SHARED(sem);
256
257 for (;;) {
258 if (__sem_dec(&sem->count) > 0)
259 break;
260
261 __futex_wait_ex(&sem->count, shared, shared|SEMCOUNT_MINUS_ONE, NULL);
262 }
263 ANDROID_MEMBAR_FULL();
264 return 0;
265 }
266
sem_timedwait(sem_t * sem,const struct timespec * abs_timeout)267 int sem_timedwait(sem_t *sem, const struct timespec *abs_timeout)
268 {
269 int ret;
270 unsigned int shared;
271
272 if (sem == NULL) {
273 errno = EINVAL;
274 return -1;
275 }
276
277 /* POSIX says we need to try to decrement the semaphore
278 * before checking the timeout value. Note that if the
279 * value is currently 0, __sem_trydec() does nothing.
280 */
281 if (__sem_trydec(&sem->count) > 0) {
282 ANDROID_MEMBAR_FULL();
283 return 0;
284 }
285
286 /* Check it as per Posix */
287 if (abs_timeout == NULL ||
288 abs_timeout->tv_sec < 0 ||
289 abs_timeout->tv_nsec < 0 ||
290 abs_timeout->tv_nsec >= 1000000000)
291 {
292 errno = EINVAL;
293 return -1;
294 }
295
296 shared = SEM_GET_SHARED(sem);
297
298 for (;;) {
299 struct timespec ts;
300 int ret;
301
302 /* Posix mandates CLOCK_REALTIME here */
303 clock_gettime( CLOCK_REALTIME, &ts );
304 ts.tv_sec = abs_timeout->tv_sec - ts.tv_sec;
305 ts.tv_nsec = abs_timeout->tv_nsec - ts.tv_nsec;
306 if (ts.tv_nsec < 0) {
307 ts.tv_nsec += 1000000000;
308 ts.tv_sec -= 1;
309 }
310
311 if (ts.tv_sec < 0 || ts.tv_nsec < 0) {
312 errno = ETIMEDOUT;
313 return -1;
314 }
315
316 /* Try to grab the semaphore. If the value was 0, this
317 * will also change it to -1 */
318 if (__sem_dec(&sem->count) > 0) {
319 ANDROID_MEMBAR_FULL();
320 break;
321 }
322
323 /* Contention detected. wait for a wakeup event */
324 ret = __futex_wait_ex(&sem->count, shared, shared|SEMCOUNT_MINUS_ONE, &ts);
325
326 /* return in case of timeout or interrupt */
327 if (ret == -ETIMEDOUT || ret == -EINTR) {
328 errno = -ret;
329 return -1;
330 }
331 }
332 return 0;
333 }
334
335 /* Unlock a semaphore */
sem_post(sem_t * sem)336 int sem_post(sem_t *sem)
337 {
338 unsigned int shared;
339 int old;
340
341 if (sem == NULL)
342 return EINVAL;
343
344 shared = SEM_GET_SHARED(sem);
345
346 ANDROID_MEMBAR_FULL();
347 old = __sem_inc(&sem->count);
348 if (old < 0) {
349 /* contention on the semaphore, wake up all waiters */
350 __futex_wake_ex(&sem->count, shared, INT_MAX);
351 }
352 else if (old == SEM_MAX_VALUE) {
353 /* overflow detected */
354 errno = EOVERFLOW;
355 return -1;
356 }
357
358 return 0;
359 }
360
sem_trywait(sem_t * sem)361 int sem_trywait(sem_t *sem)
362 {
363 if (sem == NULL) {
364 errno = EINVAL;
365 return -1;
366 }
367
368 if (__sem_trydec(&sem->count) > 0) {
369 ANDROID_MEMBAR_FULL();
370 return 0;
371 } else {
372 errno = EAGAIN;
373 return -1;
374 }
375 }
376
377 /* Note that Posix requires that sem_getvalue() returns, in
378 * case of contention, the negative of the number of waiting
379 * threads.
380 *
381 * However, code that depends on this negative value to be
382 * meaningful is most probably racy. The GLibc sem_getvalue()
383 * only returns the semaphore value, which is 0, in case of
384 * contention, so we will mimick this behaviour here instead
385 * for better compatibility.
386 */
sem_getvalue(sem_t * sem,int * sval)387 int sem_getvalue(sem_t *sem, int *sval)
388 {
389 int val;
390
391 if (sem == NULL || sval == NULL) {
392 errno = EINVAL;
393 return -1;
394 }
395
396 val = SEMCOUNT_TO_VALUE(sem->count);
397 if (val < 0)
398 val = 0;
399
400 *sval = val;
401 return 0;
402 }
403