Bugs in futex(2) example - fix for deadlock/busy-waiting and output

Bugs in futex(2) example - fix for deadlock/busy-waiting and output

[Georg Sauthoff]

Hello,

I've noticed that the example in the current
http://man7.org/linux/man-pages/man2/futex.2.html page has 2 issues:

1) The quoted output mismatches the actual output, i.e. the parent/child
order is reversed.

Man page output:

    $ ./futex_demo
    Parent (18534) 0
    Child  (18535) 0
    Parent (18534) 1
    Child  (18535) 1
    [..]

Actual output:

    Child  (21215) 0
    Parent (21214) 0
    Child  (21215) 1
    Parent (21214) 1
    [..]

Fix:

--- futex_demo.c.orig	2019-10-14 19:36:23.292238650 +0200
+++ futex_demo.c	2019-10-14 19:36:58.599464636 +0200
@@ -108,8 +108,8 @@
     futex1 = &iaddr[0];
     futex2 = &iaddr[1];
 
-    *futex1 = 0;        /* State: unavailable */
-    *futex2 = 1;        /* State: available */
+    *futex1 = 1;        /* State: unavailable */
+    *futex2 = 0;        /* State: available */
 
     /* Create a child process that inherits the shared anonymous
	mapping */

Note that this also fixes the comments.

2) As is, the fwait() either busy-waits or waits forever:

    static void
    fwait(int *futexp)
    {
	int s;
	while (1) {

	    /* Is the futex available? */
	    const int zero = 0;
	    if (atomic_compare_exchange_strong(futexp, &zero, 1))
		break;      /* Yes */

	    /* Futex is not available; wait */

	    s = futex(futexp, FUTEX_WAIT, 0, NULL, NULL, 0);

            // XXX => because 3rd arg (val) is 0 and not 1 this call
            //        likely return s==-1 and sets errno==EAGAIN
            //        (in our context)

	    if (s == -1 && errno != EAGAIN)
		errExit("futex-FUTEX_WAIT");
	}
    }

See also:

    $ strace -o log -f ./futex_demo
    $ grep 'futex.*'EAGAIN log -c
    17

The number varies, of course.

Depending on the scheduling, this also may lead to a deadlock - most easily
reproducible when running it multiple times under strace, e.g.:

    $ strace -o log -f ./futex_demo
    Parent (21488) 0
    Child  (21489) 0
    ^C
    $ 

Reason: There is a race between atomic_compare_exchange_strong() and
futex(.., FUTEX_WAIT, ..) where the first observes the futex value as 1
but the second as 0.


Fix: set val argument of futex() to 1, i.e. the same value that failed to be
set atomically:


--- futex_demo.c.orig	2019-10-14 19:36:23.292238650 +0200
+++ futex_demo.c	2019-10-14 19:49:02.696404149 +0200
@@ -60,7 +60,7 @@
 
         /* Futex is not available; wait */
 
-        s = futex(futexp, FUTEX_WAIT, 0, NULL, NULL, 0);
+        s = futex(futexp, FUTEX_WAIT, 1, NULL, NULL, 0);
         if (s == -1 && errno != EAGAIN)
             errExit("futex-FUTEX_WAIT");
     }

With that: no deadlocks and:

	$strace -o log -f ./futex_demo
	$ grep 'futex.*'EAGAIN log -c
	0


Best regards
Georg
-- 
Hofstadter's Law: "It always takes longer than you think it will
take, even when you take into account Hofstadter's Law"

Re: Bugs in futex(2) example - fix for deadlock/busy-waiting and output

[Georg Sauthoff]

On Mon, Oct 14, 2019 at 08:10:43PM +0200, Georg Sauthoff wrote:

Hello,

> I've noticed that the example in the current
> http://man7.org/linux/man-pages/man2/futex.2.html page has 2 issues:
[output,deadlock]

meanwhile, I've updated some more outdated comments and fixed const
correctness issues.

Example:

    -        const int zero = 0;
    -        if (atomic_compare_exchange_strong(futexp, &zero, 1))
    -            break;      /* Yes */
    +        int expected = 0;
    +        if (atomic_compare_exchange_strong(futexp, &expected, 1))
    +            break;

Since atomic_compare_exchange_strong() overwrites the expected value if
it doesn't match, declaring it as const yields undefined behavior.

Also, a reader unfamilar with atomic_compare_exchange() might wrongly
deduce that it doesn't modify its second argument.

You can find the complete modified example online:
https://gist.github.com/gsauthof/6eb6c648e483005191c37f86e759906e

And inline the updated patch:

--- futex_demo.c.orig	2019-10-14 19:36:23.292238650 +0200
+++ futex_demo.c	2019-10-20 10:13:32.268350668 +0200
@@ -36,38 +36,46 @@
 }
 
 /* Acquire the futex pointed to by 'futexp': wait for its value to
-   become 1, and then set the value to 0. */
+   become 0, and then set the value to 1. */
 
 static void
 fwait(int *futexp)
 {
     int s;
 
-    /* atomic_compare_exchange_strong(ptr, oldval, newval)
-       atomically performs the equivalent of:
+    /* atomic_compare_exchange_strong atomically performs
+       the equivalent of:
 
-           if (*ptr == *oldval)
-               *ptr = newval;
+       bool cmpexch(int *val, int *exp, int newval)
+       {
+           if (*val == *exp) {
+               *val = newval;
+               return true;
+           } else {
+               *exp = *val;
+               return false;
+           }
+       }
 
-       It returns true if the test yielded true and *ptr was updated. */
+       */
 
     while (1) {
 
         /* Is the futex available? */
-        const int zero = 0;
-        if (atomic_compare_exchange_strong(futexp, &zero, 1))
-            break;      /* Yes */
+        int expected = 0;
+        if (atomic_compare_exchange_strong(futexp, &expected, 1))
+            break;
 
         /* Futex is not available; wait */
 
-        s = futex(futexp, FUTEX_WAIT, 0, NULL, NULL, 0);
+        s = futex(futexp, FUTEX_WAIT, 1, NULL, NULL, 0);
         if (s == -1 && errno != EAGAIN)
             errExit("futex-FUTEX_WAIT");
     }
 }
 
 /* Release the futex pointed to by 'futexp': if the futex currently
-   has the value 0, set its value to 1 and the wake any futex waiters,
+   has the value 1, set its value to 0 and the wake any futex waiters,
    so that if the peer is blocked in fpost(), it can proceed. */
 
 static void
@@ -77,8 +85,8 @@
 
     /* atomic_compare_exchange_strong() was described in comments above */
 
-    const int one = 1;
-    if (atomic_compare_exchange_strong(futexp, &one, 0)) {
+    int expected = 1;
+    if (atomic_compare_exchange_strong(futexp, &expected, 0)) {
         s = futex(futexp, FUTEX_WAKE, 1, NULL, NULL, 0);
         if (s  == -1)
             errExit("futex-FUTEX_WAKE");
@@ -108,8 +116,8 @@
     futex1 = &iaddr[0];
     futex2 = &iaddr[1];
 
-    *futex1 = 0;        /* State: unavailable */
-    *futex2 = 1;        /* State: available */
+    *futex1 = 1;        /* State: unavailable */
+    *futex2 = 0;        /* State: available */
 
     /* Create a child process that inherits the shared anonymous
        mapping */


Best regards
Georg