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 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) 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 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 */ 336int 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 361int 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 */ 387int 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