libc: Fix sem_post() implementation to wake up all waiting threads.

This also allows us to optimize the case where we increment an
uncontended semaphore (no need to call futex_wake() then).

Change-Id: Iad48efe8551dc66dc89d3e3f18c001e5a6c1939f

3 files changed, 180 insertions, 48 deletions

diff --git a/libc/bionic/semaphore.c b/libc/bionic/semaphore.c
index 0a6cab4..96819ae 100644
--- a/libc/bionic/semaphore.c
+++ b/libc/bionic/semaphore.c
@@ -32,15 +32,60 @@
 #include <time.h>
 #include <bionic_atomic_inline.h>
 #include <bionic_futex.h>
+#include <limits.h>
 
-/* Use the lower 31-bits for the counter, and the high bit for
- * the shared flag.
+/* In this implementation, a semaphore contains a
+ * 31-bit signed value and a 1-bit 'shared' flag
+ * (for process-sharing purpose).
+ *
+ * We use the value -1 to indicate contention on the
+ * semaphore, 0 or more to indicate uncontended state,
+ * any value lower than -2 is invalid at runtime.
+ *
+ * State diagram:
+ *
+ * post(1)  ==> 2
+ * post(0)  ==> 1
+ * post(-1) ==> 1, then wake all waiters
+ *
+ * wait(2)  ==> 1
+ * wait(1)  ==> 0
+ * wait(0)  ==> -1 then wait for a wake up + loop
+ * wait(-1) ==> -1 then wait for a wake up + loop
+ *
+ */
+
+/* Use the upper 31-bits for the counter, and the lower one
+ * for the shared flag.
  */
-#define SEM_VALUE_MASK  0x7fffffff
-#define SEM_SHARED_MASK 0x80000000
+#define SEMCOUNT_SHARED_MASK      0x00000001
+#define SEMCOUNT_VALUE_MASK       0xfffffffe
+#define SEMCOUNT_VALUE_SHIFT      1
+
+/* Maximum unsigned value that can be stored in the semaphore.
+ * One bit is used for the shared flag, another one for the
+ * sign bit, leaving us with only 30 bits.
+ */
+#define SEM_MAX_VALUE             0x3fffffff
+
+/* convert a value into the corresponding sem->count bit pattern */
+#define SEMCOUNT_FROM_VALUE(val)    (((val) << SEMCOUNT_VALUE_SHIFT) & SEMCOUNT_VALUE_MASK)
+
+/* convert a sem->count bit pattern into the corresponding signed value */
+#define SEMCOUNT_TO_VALUE(sval)  ((int)(sval) >> SEMCOUNT_VALUE_SHIFT)
+
+/* the value +1 as a sem->count bit-pattern. */
+#define SEMCOUNT_ONE              SEMCOUNT_FROM_VALUE(1)
+
+/* the value -1 as a sem->count bit-pattern. */
+#define SEMCOUNT_MINUS_ONE        SEMCOUNT_FROM_VALUE(-1)
+
+#define SEMCOUNT_DECREMENT(sval)    (((sval) - (1U << SEMCOUNT_VALUE_SHIFT)) & SEMCOUNT_VALUE_MASK)
+#define SEMCOUNT_INCREMENT(sval)    (((sval) + (1U << SEMCOUNT_VALUE_SHIFT)) & SEMCOUNT_VALUE_MASK)
+
+/* return the shared bitflag from a semaphore */
+#define SEM_GET_SHARED(sem)       ((sem)->count & SEMCOUNT_SHARED_MASK)
 
-#define SEM_GET_SHARED(sem)  ((sem)->count & SEM_SHARED_MASK)
-#define SEM_GET_VALUE(sem)   ((sem)->count & SEM_VALUE_MASK)
 
 int sem_init(sem_t *sem, int pshared, unsigned int value)
 {
@@ -50,14 +95,14 @@ int sem_init(sem_t *sem, int pshared, unsigned int value)
     }
 
     /* ensure that 'value' can be stored in the semaphore */
-    if ((value & SEM_VALUE_MASK) != value) {
+    if (value > SEM_MAX_VALUE) {
         errno = EINVAL;
         return -1;
     }
 
-    sem->count = value;
+    sem->count = SEMCOUNT_FROM_VALUE(value);
     if (pshared != 0)
-        sem->count |= SEM_SHARED_MASK;
+        sem->count |= SEMCOUNT_SHARED_MASK;
 
     return 0;
 }
@@ -65,11 +110,14 @@ int sem_init(sem_t *sem, int pshared, unsigned int value)
 
 int sem_destroy(sem_t *sem)
 {
+    int count;
+
     if (sem == NULL) {
         errno = EINVAL;
         return -1;
     }
-    if ((sem->count & SEM_VALUE_MASK) == 0) {
+    count = SEMCOUNT_TO_VALUE(sem->count);
+    if (count < 0) {
         errno = EBUSY;
         return -1;
     }
@@ -106,41 +154,92 @@ int sem_unlink(const char * name)
 }
 
 
-/* Return 0 if a semaphore's value is 0
- * Otherwise, decrement the value and return the old value.
+/* Decrement a semaphore's value atomically,
+ * and return the old one. As a special case,
+ * this returns immediately if the value is
+ * negative (i.e. -1)
+ */
+static int
+__sem_dec(volatile unsigned int *pvalue)
+{
+    unsigned int shared = (*pvalue & SEMCOUNT_SHARED_MASK);
+    unsigned int old, new;
+    int          ret;
+
+    do {
+        old = (*pvalue & SEMCOUNT_VALUE_MASK);
+        ret = SEMCOUNT_TO_VALUE(old);
+        if (ret < 0)
+            break;
+
+        new = SEMCOUNT_DECREMENT(old);
+    }
+    while (__atomic_cmpxchg((int)(old|shared),
+                            (int)(new|shared),
+                            (volatile int *)pvalue) != 0);
+    return ret;
+}
+
+/* Same as __sem_dec, but will not touch anything if the
+ * value is already negative *or* 0. Returns the old value.
  */
 static int
-__sem_dec_if_positive(volatile unsigned int *pvalue)
+__sem_trydec(volatile unsigned int *pvalue)
 {
-    unsigned int  shared = (*pvalue & SEM_SHARED_MASK);
-    unsigned int  old;
+    unsigned int shared = (*pvalue & SEMCOUNT_SHARED_MASK);
+    unsigned int old, new;
+    int          ret;
 
     do {
-        old = (*pvalue & SEM_VALUE_MASK);
+        old = (*pvalue & SEMCOUNT_VALUE_MASK);
+        ret = SEMCOUNT_TO_VALUE(old);
+        if (ret <= 0)
+            break;
+
+        new = SEMCOUNT_DECREMENT(old);
     }
-    while ( old != 0 &&
-            __atomic_cmpxchg((int)(old|shared),
-                             (int)((old-1)|shared),
-                             (volatile int*)pvalue) != 0 );
+    while (__atomic_cmpxchg((int)(old|shared),
+                            (int)(new|shared),
+                            (volatile int *)pvalue) != 0);
 
-    return old;
+    return ret;
 }
 
-/* Increment the value of a semaphore atomically.
- * NOTE: the value will wrap above SEM_VALUE_MASK
+
+/* "Increment" the value of a semaphore atomically and
+ * return its old value. Note that this implements
+ * the special case of "incrementing" any negative
+ * value to +1 directly.
+ *
+ * NOTE: The value will _not_ wrap above SEM_VALUE_MAX
  */
 static int
 __sem_inc(volatile unsigned int *pvalue)
 {
-    unsigned int  shared = (*pvalue & SEM_SHARED_MASK);
-    unsigned int  old;
+    unsigned int  shared = (*pvalue & SEMCOUNT_SHARED_MASK);
+    unsigned int  old, new;
+    int           ret;
 
     do {
-        old = (*pvalue & SEM_VALUE_MASK);
-    } while ( __atomic_cmpxchg((int)(old|shared),
-                               (int)(((old+1)&SEM_VALUE_MASK)|shared),
-                               (volatile int*)pvalue) != 0);
-    return old;
+        old = (*pvalue & SEMCOUNT_VALUE_MASK);
+        ret = SEMCOUNT_TO_VALUE(old);
+
+        /* Can't go higher than SEM_MAX_VALUE */
+        if (ret == SEM_MAX_VALUE)
+            break;
+
+        /* If the counter is negative, go directly to +1,
+         * otherwise just increment */
+        if (ret < 0)
+            new = SEMCOUNT_ONE;
+        else
+            new = SEMCOUNT_INCREMENT(old);
+    }
+    while ( __atomic_cmpxchg((int)(old|shared),
+                             (int)(new|shared),
+                             (volatile int*)pvalue) != 0);
+
+    return ret;
 }
 
 /* lock a semaphore */
@@ -156,10 +255,10 @@ int sem_wait(sem_t *sem)
     shared = SEM_GET_SHARED(sem);
 
     for (;;) {
-        if (__sem_dec_if_positive(&sem->count))
+        if (__sem_dec(&sem->count) > 0)
             break;
 
-        __futex_wait_ex(&sem->count, shared, shared, NULL);
+        __futex_wait_ex(&sem->count, shared, shared|SEMCOUNT_MINUS_ONE, NULL);
     }
     ANDROID_MEMBAR_FULL();
     return 0;
@@ -176,13 +275,15 @@ int sem_timedwait(sem_t *sem, const struct timespec *abs_timeout)
     }
 
     /* POSIX says we need to try to decrement the semaphore
-     * before checking the timeout value */
-    if (__sem_dec_if_positive(&sem->count)) {
+     * before checking the timeout value. Note that if the
+     * value is currently 0, __sem_trydec() does nothing.
+     */
+    if (__sem_trydec(&sem->count) > 0) {
         ANDROID_MEMBAR_FULL();
         return 0;
     }
 
-    /* check it as per Posix */
+    /* Check it as per Posix */
     if (abs_timeout == NULL    ||
         abs_timeout->tv_sec < 0 ||
         abs_timeout->tv_nsec < 0 ||
@@ -212,26 +313,30 @@ int sem_timedwait(sem_t *sem, const struct timespec *abs_timeout)
             return -1;
         }
 
-        ret = __futex_wait_ex(&sem->count, shared, shared, &ts);
+        /* Try to grab the semaphore. If the value was 0, this
+         * will also change it to -1 */
+        if (__sem_dec(&sem->count) > 0) {
+            ANDROID_MEMBAR_FULL();
+            break;
+        }
+
+        /* Contention detected. wait for a wakeup event */
+        ret = __futex_wait_ex(&sem->count, shared, shared|SEMCOUNT_MINUS_ONE, &ts);
 
         /* return in case of timeout or interrupt */
         if (ret == -ETIMEDOUT || ret == -EINTR) {
             errno = -ret;
             return -1;
         }
-
-        if (__sem_dec_if_positive(&sem->count)) {
-            ANDROID_MEMBAR_FULL();
-            break;
-        }
     }
     return 0;
 }
 
-/* unlock a semaphore */
+/* Unlock a semaphore */
 int sem_post(sem_t *sem)
 {
     unsigned int shared;
+    int          old;
 
     if (sem == NULL)
         return EINVAL;
@@ -239,8 +344,16 @@ int sem_post(sem_t *sem)
     shared = SEM_GET_SHARED(sem);
 
     ANDROID_MEMBAR_FULL();
-    if (__sem_inc(&sem->count) >= 0)
-        __futex_wake_ex(&sem->count, shared, 1);
+    old = __sem_inc(&sem->count);
+    if (old < 0) {
+        /* contention on the semaphore, wake up all waiters */
+        __futex_wake_ex(&sem->count, shared, INT_MAX);
+    }
+    else if (old == SEM_MAX_VALUE) {
+        /* overflow detected */
+        errno = EOVERFLOW;
+        return -1;
+    }
 
     return 0;
 }
@@ -252,7 +365,7 @@ int  sem_trywait(sem_t *sem)
         return -1;
     }
 
-    if (__sem_dec_if_positive(&sem->count) > 0) {
+    if (__sem_trydec(&sem->count) > 0) {
         ANDROID_MEMBAR_FULL();
         return 0;
     } else {
@@ -261,13 +374,29 @@ int  sem_trywait(sem_t *sem)
     }
 }
 
+/* Note that Posix requires that sem_getvalue() returns, in
+ * case of contention, the negative of the number of waiting
+ * threads.
+ *
+ * However, code that depends on this negative value to be
+ * meaningful is most probably racy. The GLibc sem_getvalue()
+ * only returns the semaphore value, which is 0, in case of
+ * contention, so we will mimick this behaviour here instead
+ * for better compatibility.
+ */
 int  sem_getvalue(sem_t *sem, int *sval)
 {
+    int  val;
+
     if (sem == NULL || sval == NULL) {
         errno = EINVAL;
         return -1;
     }
 
-    *sval = SEM_GET_VALUE(sem);
+    val = SEMCOUNT_TO_VALUE(sem->count);
+    if (val < 0)
+        val = 0;
+
+    *sval = val;
     return 0;
 }
diff --git a/libc/docs/CHANGES.TXT b/libc/docs/CHANGES.TXT
index 5a7a1ac..9389f7a 100644
--- a/libc/docs/CHANGES.TXT
+++ b/libc/docs/CHANGES.TXT
@@ -10,6 +10,10 @@ Differences between current and Android 2.2:
 - <semaphore.h>: Use private futexes for semaphore implementation,
   unless your set 'pshared' to non-0 when calling sem_init().
 
+  Also fixed a bug in sem_post() to make it wake up all waiting
+  threads, instead of one. As a consequence, the maximum semaphore
+  value is now reduced to 0x3fffffff.
+
 - <math.h>: Added sincos(), sincosf() and sincosl() (GLibc compatibility).
 
 - <sys/sysinfo.h>: Added missing sysinfo() system call implementation
@@ -59,7 +63,6 @@ Differences between current and Android 2.2:
 
 - <sys/select.h>: add missing declaration for pselect()
 
-- 
 
 -------------------------------------------------------------------------------
 Differences between Android 2.2. and Android 2.1:
diff --git a/libc/unistd/sysconf.c b/libc/unistd/sysconf.c
index 27b113c..9377802 100644
--- a/libc/unistd/sysconf.c
+++ b/libc/unistd/sysconf.c
@@ -44,7 +44,7 @@
 #define  SYSTEM_MQ_OPEN_MAX     8
 #define  SYSTEM_MQ_PRIO_MAX     32768
 #define  SYSTEM_SEM_NSEMS_MAX   256
-#define  SYSTEM_SEM_VALUE_MAX   (2147483647)
+#define  SYSTEM_SEM_VALUE_MAX   0x3fffffff  /* see bionic/semaphore.c */
 #define  SYSTEM_SIGQUEUE_MAX    32
 #define  SYSTEM_TIMER_MAX       32
 #define  SYSTEM_LOGIN_NAME_MAX  256