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 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 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 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 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 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 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 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 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 */ 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 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 */ 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 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 */ 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