Re: [patch] futex.7: Semantics section: Race condition in locking semantics description

["Michael Kerrisk (man-pages)" <mtk.manpages@gmail.com>]

Hello Marion.

On 12/2/20 7:07 PM, Sudvarg, Marion wrote:
> Hello Michael,
> 
> I apologize if you're receiving this email a second time. I
> accidentally kept HTML formatting enabled the first time I sent it,
> causing it to be rejected as spam.
> 
> I am teaching the Operating Systems Organization course at Washington
> University in St. Louis, and to supplement a series of lectures on
> locking and synchronization, I assigned students to read the futex(7)
> manual page. One student, Alex Baker <mailto:alexbaker@wustl.edu>,
> pointed out a race condition in the description of how to "down" a
> futex, i.e. wait for or acquire a lock, under the Semantics section.
> Say we have two threads, T0 and T1, which execute as follows:
> 
> 1. T0 acquires the lock, decrements the futex to 0
> 2. T1 switches in, attempts to acquire the lock, decrements the futex
> to -1
> 3. T0 switches in, completes its critical section
> 4. T0 unlocks the lock, increments the futex to 0
> 5. Because the futex is 0, T0 assumes threads are waiting on the
> futex, but no threads have yet called FUTEX_WAIT
> 6. T0 sets the futex to 1
> 7. T0 uses the FUTEX_WAKE operation
> 8. T1 switches in, and believing it should still wait for the futex,
> it sets the futex to -1
> 9. T1 now uses the FUTEX_WAIT operation
> 
> Because, in step 8, T1 has set the futex to -1, its call to
> FUTEX_WAIT in 9 will succeed, as the futex holds the expected value
> in the call (-1). But since T0 has already completed its execution
> and has called FUTEX_WAKE, T1 may never be woken.
> 
> The fwait and fpost (i.e. lock and release, or down and up) functions
> in the Examples section on the futex(2) page seem to be race free,
> but use atomic compare exchange functions, instead of the atomic
> increment and decrement semantics described in futex(7).
> 
> I've attached a patch for the futex(7) man page, which modifies the
> Semantics section to describe a correct, race-free use of a futex for
> lock acquisition using atomic increment and decrement operations.
> I've also added a code sample to help illustrate this. I hope the
> addition of the code sample does not, in your opinion, add
> unnecessary length to this manual page, given that the futex(2) page
> is already so thorough.
> 
> I have copied Bert Hubert, whom I believe to be the original author
> of the futex(7) man page.

I have a question: what Linux distro are you using/did you make
this patch from? The code example that your patch is using is _not_
in the upstream page that is part of man-pages.

Regarding your comments on the race above, I find the text of
the manual page a bit unclear, so I'm not sure what kind of
fix should be made. Maybe we are lucky and Bert has a long memory
and replies to this thread.

Thanks,

Michael
 
=====

diff --git a/man7/futex.7 b/man7/futex.7
index 22f610646..f59725b61 100644
--- a/man7/futex.7
+++ b/man7/futex.7
@@ -72,19 +72,11 @@ operation.
 Waiting on a futex, to "down" it, is the reverse operation.
 Atomically decrement the counter and check if it changed to 0,
 in which case the operation is done and the futex was uncontended.
-In all other circumstances, the process should
-request that the kernel wait for another process to up the futex.
+In all other circumstances, the process should set the counter to \-1
+and request that the kernel wait for another process to up the futex.
 This is done using the
 .B FUTEX_WAIT
-operation,
-which is provided the return value of the atomic decrement operation.
-In the event that another process has modified the value of the futex
-between the atomic decrement and the
-.B FUTEX_WAIT
-operation, this guarantees that the
-.B FUTEX_WAIT
-fails, and the process may try again to "down" the futex.
-.SS 
+operation.
 .PP
 The
 .BR futex (2)
@@ -113,166 +105,6 @@ below.
 This man page illustrates the most common use of the
 .BR futex (2)
 primitives; it is by no means the only one.
-.SH EXAMPLES
-The program below demonstrates the use of futexes in a program where
-threads use a futex to synchronize access to a critical section,
-which increments a global integer variable
-.IR nloops
-(a command-line argument that defaults to 100000 if omitted)
-times.
-After the parallel section,
-the program prints the value of the global variable.
-Upon running this program we see output such as the following:
-.PP
-.in +4n
-.EX
-$ \fB./futex_demo\fP
-Ran with 2 threads
-Each thread incremented global_int 1000000 times
-Final value of global_int: 2000000
-.EE
-.in
-.SS Program source
-\&
-.EX
-/* futex_demo.c
-
-    Usage: futex_demo [nloops]
-                    (Default: 100000)
-
-    Demonstrate the use of futexes in a program where multiple threads
-    use a futex to synchronize access to a global integer variable, which
-    is initialized to 0. The two threads each increment the variable
-    \(aqnloops\(aq times, and employ a synchronization protocol that
-    ensures only one thread can access the global variable at a time.
-
-    We use OpenMP for thread parallelism;
-    therefore, this program must be compiled with the \-fopenmp flag,
-    e.g.:
-
-    gcc futex_demo.c \-o futex_demo \-fopenmp
-
-#define _GNU_SOURCE
-#include <stdio.h>
-#include <errno.h>
-#include <stdatomic.h>
-#include <stdint.h>
-#include <stdlib.h>
-#include <unistd.h>
-#include <sys/syscall.h>
-#include <linux/futex.h>
-#include <omp.h>
-
-#define errExit(msg)    do { perror(msg); exit(EXIT_FAILURE); \e
-                        } while (0)
-
-#define NUM_THREADS 2
-#define LOCKED 0
-#define UNLOCKED 1
-
-static int global_int = 0;
-static uint32_t lock = UNLOCKED;
-
-static int
-futex(uint32_t *uaddr, int futex_op, uint32_t val,
-      const struct timespec *timeout, uint32_t *uaddr2, uint32_t val3)
-{
-    return syscall(SYS_futex, uaddr, futex_op, val,
-                   timeout, uaddr2, val3);
-}
-
-/*  Increments the global integer variable nloops times.
-    Without locking, a race condition may occur. */
-
-static void
-critical_section(int nloops)
-{
-    for (int i = 0; i < nloops; i++) {
-        global_int++;
-    }
-}
-
-
-/*  Attempt to lock the futex pointed to by \(aqfutexp\(aq:
-    The futex value is decremented by 1.
-    If the futex value is now LOCKED,
-    the lock was successfully acquired.
-    Otherwise, wait for the lock to be released. */
-
-static void
-flock(uint32_t * futexp)
-{
-    int s;
-    int futex_val;
-
-    /* Attempt to acquire the lock */
-    while ( (futex_val = __atomic_sub_fetch(futexp, 1, __ATOMIC_ACQ_REL)) < LOCKED ) {
-
-        /* If the lock is not available, wait */
-
-        s = futex(futexp, FUTEX_WAIT, futex_val, NULL, NULL, 0);
-        if (s == \-1 && errno != EAGAIN)
-            errExit("futex\-FUTEX_WAIT");
-    }
-}
-
-/*  Unlock the futex pointed to by \(aqfutexp\(aq:
-    The futex value is incremented by 1.
-    
-    If the futex value is now UNLOCKED,
-    no threads are waiting for the lock.
-    Otherwise, another thread is waiting,
-    so set the value to UNLOCKED and wake. */
-
-static void
-funlock(uint32_t * futexp)
-{
-    int s;
-
-    /* Are any threads waiting for the lock? */
-    if (__atomic_add_fetch(futexp, 1, __ATOMIC_ACQ_REL) != UNLOCKED) {
-
-        /* If so, unlock and notify */
-        __atomic_store_n(futexp, UNLOCKED, __ATOMIC_RELEASE);
-        s = futex(futexp, FUTEX_WAKE, 1, NULL, NULL, 0);
-        if (s  == \-1)
-            errExit("futex\-FUTEX_WAKE");
-    }
-}
-
-int
-main(int argc, char *argv[])
-{
-    int nloops;
-    int n_threads;
-
-    nloops = (argc > 1) ? atoi(argv[1]) : 100000;
-
-    //Begin OpenMP parallel section
-    omp_set_num_threads(NUM_THREADS);
-    #pragma omp parallel
-    {
-
-        //Retrieve the actual number of threads
-        if (omp_get_thread_num() == 0) {
-            n_threads = omp_get_num_threads();
-        }
-
-        //Lock and run the critical section
-        flock(&lock);
-        critical_section(nloops);
-        funlock(&lock);
-
-    }
-    
-    printf("Ran with %d threads\n", n_threads);
-    printf("Each thread incremented global_int %d times\n", nloops);
-    printf("Final value of global_int: %d\n", global_int);
-
-    exit(EXIT_SUCCESS);
-}
-
-.EE
 .\" .SH AUTHORS
 .\" .PP
 .\" Futexes were designed and worked on by Hubertus Franke
-- 
Michael Kerrisk
Linux man-pages maintainer; http://www.kernel.org/doc/man-pages/
Linux/UNIX System Programming Training: http://man7.org/training/