semaphore.c revision 95d3cd0b85724d3702cfb71942f9aa0a5ee27c74 
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
90int 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
111int 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
129sem_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
139int 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
150int sem_unlink(const char* name __unused)
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 */
162static int
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 (__bionic_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 */
186static int
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 (__bionic_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 */
216static int
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 ( __bionic_cmpxchg((int)(old|shared),
239                             (int)(new|shared),
240                             (volatile int*)pvalue) != 0);
241
242    return ret;
243}
244
245/* lock a semaphore */
246int 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
267int sem_timedwait(sem_t *sem, const struct timespec *abs_timeout)
268{
269    unsigned int shared;
270
271    if (sem == NULL) {
272        errno = EINVAL;
273        return -1;
274    }
275
276    /* POSIX says we need to try to decrement the semaphore
277     * before checking the timeout value. Note that if the
278     * value is currently 0, __sem_trydec() does nothing.
279     */
280    if (__sem_trydec(&sem->count) > 0) {
281        ANDROID_MEMBAR_FULL();
282        return 0;
283    }
284
285    /* Check it as per Posix */
286    if (abs_timeout == NULL    ||
287        abs_timeout->tv_sec < 0 ||
288        abs_timeout->tv_nsec < 0 ||
289        abs_timeout->tv_nsec >= 1000000000)
290    {
291        errno = EINVAL;
292        return -1;
293    }
294
295    shared = SEM_GET_SHARED(sem);
296
297    for (;;) {
298        struct timespec ts;
299        int             ret;
300
301        /* Posix mandates CLOCK_REALTIME here */
302        clock_gettime( CLOCK_REALTIME, &ts );
303        ts.tv_sec  = abs_timeout->tv_sec - ts.tv_sec;
304        ts.tv_nsec = abs_timeout->tv_nsec - ts.tv_nsec;
305        if (ts.tv_nsec < 0) {
306            ts.tv_nsec += 1000000000;
307            ts.tv_sec  -= 1;
308        }
309
310        if (ts.tv_sec < 0 || ts.tv_nsec < 0) {
311            errno = ETIMEDOUT;
312            return -1;
313        }
314
315        /* Try to grab the semaphore. If the value was 0, this
316         * will also change it to -1 */
317        if (__sem_dec(&sem->count) > 0) {
318            ANDROID_MEMBAR_FULL();
319            break;
320        }
321
322        /* Contention detected. wait for a wakeup event */
323        ret = __futex_wait_ex(&sem->count, shared, shared|SEMCOUNT_MINUS_ONE, &ts);
324
325        /* return in case of timeout or interrupt */
326        if (ret == -ETIMEDOUT || ret == -EINTR) {
327            errno = -ret;
328            return -1;
329        }
330    }
331    return 0;
332}
333
334/* Unlock a semaphore */
335int sem_post(sem_t *sem)
336{
337    unsigned int shared;
338    int          old;
339
340    if (sem == NULL)
341        return EINVAL;
342
343    shared = SEM_GET_SHARED(sem);
344
345    ANDROID_MEMBAR_FULL();
346    old = __sem_inc(&sem->count);
347    if (old < 0) {
348        /* contention on the semaphore, wake up all waiters */
349        __futex_wake_ex(&sem->count, shared, INT_MAX);
350    }
351    else if (old == SEM_MAX_VALUE) {
352        /* overflow detected */
353        errno = EOVERFLOW;
354        return -1;
355    }
356
357    return 0;
358}
359
360int  sem_trywait(sem_t *sem)
361{
362    if (sem == NULL) {
363        errno = EINVAL;
364        return -1;
365    }
366
367    if (__sem_trydec(&sem->count) > 0) {
368        ANDROID_MEMBAR_FULL();
369        return 0;
370    } else {
371        errno = EAGAIN;
372        return -1;
373    }
374}
375
376/* Note that Posix requires that sem_getvalue() returns, in
377 * case of contention, the negative of the number of waiting
378 * threads.
379 *
380 * However, code that depends on this negative value to be
381 * meaningful is most probably racy. The GLibc sem_getvalue()
382 * only returns the semaphore value, which is 0, in case of
383 * contention, so we will mimick this behaviour here instead
384 * for better compatibility.
385 */
386int  sem_getvalue(sem_t *sem, int *sval)
387{
388    int  val;
389
390    if (sem == NULL || sval == NULL) {
391        errno = EINVAL;
392        return -1;
393    }
394
395    val = SEMCOUNT_TO_VALUE(sem->count);
396    if (val < 0)
397        val = 0;
398
399    *sval = val;
400    return 0;
401}
402