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 __unused, int oflag __unused, ...) 130{ 131 errno = ENOSYS; 132 return SEM_FAILED; 133} 134 135 136int 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 147int 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 */ 159static int 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 */ 183static int 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 */ 213static int 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 */ 243int 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 264int 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 */ 332int 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 357int 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 */ 383int 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