Changeset 710c1e9 in mainline

Timestamp:

2018-07-13T16:54:22Z (6 years ago)

Author:

Jiří Zárevúcky <jiri.zarevucky@…>

Branches:

lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export

Children:

868d75c

Parents:

e3787a0

git-author:

Jiří Zárevúcky <jiri.zarevucky@…> (2018-07-01 17:23:12)

git-committer:

Jiří Zárevúcky <jiri.zarevucky@…> (2018-07-13 16:54:22)

Message:

More robust non-blocking futex down.

File:

• uspace/lib/c/include/futex.h (modified) (5 diffs)

uspace/lib/c/include/futex.h

@@ -86 +86 @@
 #endif
 
-/** Try to down the futex.
- *
- * @param futex Futex.
- *
- * @return true if the futex was acquired.
- * @return false if the futex was not acquired.
- *
- */
-static inline bool futex_trydown(futex_t *futex)
-{
-        return cas(&futex->val, 1, 0);
-}
-
 /** Down the futex with timeout, composably.
  *
@@ -115 +102 @@
  *
  */
-static inline errno_t futex_down_composable(futex_t *futex, struct timeval *expires)
+static inline errno_t futex_down_composable(futex_t *futex, const struct timeval *expires)
 {
         // TODO: Add tests for this.
 
-        /* No timeout by default. */
-        suseconds_t timeout = 0;
-
-        if (expires) {
-                struct timeval tv;
-                getuptime(&tv);
-                if (tv_gteq(&tv, expires)) {
+        if ((atomic_signed_t) atomic_predec(&futex->val) >= 0)
+                return EOK;
+
+        suseconds_t timeout;
+
+        if (!expires) {
+                /* No timeout. */
+                timeout = 0;
+        } else {
+                if (expires->tv_sec == 0) {
                         /* We can't just return ETIMEOUT. That wouldn't be composable. */
                         timeout = 1;
                 } else {
-                        timeout = tv_sub_diff(expires, &tv);
+                        struct timeval tv;
+                        getuptime(&tv);
+                        timeout = tv_gteq(&tv, expires) ? 1 :
+                            tv_sub_diff(expires, &tv);
                 }
 
@@ -135 +128 @@
         }
 
-        if ((atomic_signed_t) atomic_predec(&futex->val) < 0)
-                return (errno_t) __SYSCALL2(SYS_FUTEX_SLEEP, (sysarg_t) &futex->val.count, (sysarg_t) timeout);
-
-        return EOK;
+        return __SYSCALL2(SYS_FUTEX_SLEEP, (sysarg_t) &futex->val.count, (sysarg_t) timeout);
 }
 
@@ -153 +143 @@
 {
         if ((atomic_signed_t) atomic_postinc(&futex->val) < 0)
-                return (errno_t) __SYSCALL1(SYS_FUTEX_WAKEUP, (sysarg_t) &futex->val.count);
+                return __SYSCALL1(SYS_FUTEX_WAKEUP, (sysarg_t) &futex->val.count);
 
         return EOK;
 }
 
-static inline errno_t futex_down_timeout(futex_t *futex, struct timeval *expires)
-{
+static inline errno_t futex_down_timeout(futex_t *futex, const struct timeval *expires)
+{
+        if (expires && expires->tv_sec == 0 && expires->tv_usec == 0) {
+                /* Nonblocking down. */
+
+                /*
+                 * Try good old CAS a few times.
+                 * Not too much though, we don't want to bloat the caller.
+                 */
+                for (int i = 0; i < 2; i++) {
+                        atomic_signed_t old = atomic_get(&futex->val);
+                        if (old <= 0)
+                                return ETIMEOUT;
+
+                        if (cas(&futex->val, old, old - 1))
+                                return EOK;
+                }
+
+                // TODO: builtin atomics with relaxed ordering can make this
+                //       faster.
+
+                /*
+                 * If we don't succeed with CAS, we can't just return failure
+                 * because that would lead to spurious failures where
+                 * futex_down_timeout returns ETIMEOUT despite there being
+                 * available tokens. That could break some algorithms.
+                 * We also don't want to loop on CAS indefinitely, because
+                 * that would make the semaphore not wait-free, even when all
+                 * atomic operations and the underlying base semaphore are all
+                 * wait-free.
+                 * Instead, we fall back to regular down_timeout(), with
+                 * an already expired deadline. That way we delegate all these
+                 * concerns to the base semaphore.
+                 */
+        }
+
         /*
          * This combination of a "composable" sleep followed by futex_up() on
@@ -171 +195 @@
 }
 
+/** Try to down the futex.
+ *
+ * @param futex Futex.
+ *
+ * @return true if the futex was acquired.
+ * @return false if the futex was not acquired.
+ *
+ */
+static inline bool futex_trydown(futex_t *futex)
+{
+        /*
+         * down_timeout with an already expired deadline should behave like
+         * trydown.
+         */
+        struct timeval tv = { .tv_sec = 0, .tv_usec = 0 };
+        return futex_down_timeout(futex, &tv) == EOK;
+}
+
 /** Down the futex.
  *