[RFC] [BZ 14417] Document condvar synchronization

[Torvald Riegel]

I've been reviewing condvar synchronization.  Attached is a patch that
documents this, covering interactions of wait and signal.  I have yet to
finish reviewing broadcasts and cancellation.  Please have a look and
let me know whether this is adequate documentation (scope,
verbosity, ...).  I tried to find a middle ground between preciseness
and brevity.  Given that several people (including myself) looked for a
while at 14417 without seeing the fault, I think it can't hurt to have
rather lengthy documentation for the condvar implementation.

We (Siddhesh Poyarekar and I) have been investigating 14417, and we
think we have found the fault.  The problem is that the non-PI aware
condvar implementation does not need to handle spurious wake-up (see the
comments in my patch).  By spurious wake-up, I mean futex_wait returning
-EAGAIN because the futex value changed concurrently, for example.

However, with PI and when futex_wait_requeue_pi is used, we have to
because this syscall will acquire the mutex unless it returns due to a
spurious wake-up.  Thus, we don't need to handle this specially for the
core concurrent algorithm also used for non-PI condvars, but we have to
ensure that (1) we release the mutex if it has been acquired by the
syscall but we did not consume the signal, or (2) acquire the mutex if
we have consumed the signal but after a spurious wake-up.  The latter
will not ensure PI, but we believe this is still a reasonable
(intermediate) fix.  (There is more work left to be done anyway until
condvars are fully PI-aware, see BZ 11588.)

Siddhesh has been working on a patch that fixes the PI-supporting code
and will send it soon I believe.

I'd also appreciate feedback on the ABA issue that I mention in the
comments.


Torvald
-------------- next part --------------
commit 8e5d8b4bf7c429fb42f6af45ea8c3033303aceac
Author: Torvald Riegel <triegel@redhat.com>
Date:   Mon Sep 17 13:35:41 2012 +0200

    Add explanation of condvar synchronization.

diff --git a/nptl/pthread_cond_wait.c b/nptl/pthread_cond_wait.c
index 35505d9..db31c14 100644
--- a/nptl/pthread_cond_wait.c
+++ b/nptl/pthread_cond_wait.c
@@ -90,6 +90,89 @@ __condvar_cleanup (void *arg)
 }
 
 
+/* Overview of condvar synchronization (just considering wait/signal):
+
+   As shared state, we have three counters and a futex that waiting threads
+   use to wait until waken.  __total_seq counts the number of waiting threads
+   that have started waiting at some point in time, including those that have
+   been already wakened.  __wakeup_seq counts the number of times that a
+   signaling thread wakened waiting threads (if any existed previously and
+   incremented __total_seq so that it was larger than __wakeup_seq).
+   __woken_seq counts the number of waiters that have actually woken up due
+   to being signaled.
+
+   The following types of critical sections (CS) are executed by waiting
+   (W1-W3) and signaling threads (S1):
+
+   W1:
+     pthread_mutex_unlock(mutex);
+     __total_seq++;
+     __futex++;
+     seq = val = __wakeup_seq;
+     f = __futex;
+
+   W2:
+     val = __wakeup_seq;
+     assert(val == seq || val == __woken_seq);
+     f == __futex;
+
+   W3:
+     v == __wakeup_seq;
+     assert( val != seq && val != __woken_seq);
+     __woken_seq++;
+
+   S1:
+     if (__total_seq > __wakeup_seq)
+       __futex++;
+       __wakeup_seq++;
+       futex_wake(&__futex);
+
+   Those CSs all use __lock and thus execute mutually exclusive.  Waiting
+   threads block using a futex_wait (FW) call on __futex.  Thus we can get
+   the following execution sequence:
+     W1, FW, (W2, FW)*, W3
+   FW is not atomic wrt. W1-W3 or S1 (but FW is atomic wrt. S1's futex_wake
+   call).  However, FW will only  block if __futex has the same value as
+   observed in the preceding W1 or W2 CS; therefore, we only block if a W1,FW
+   or W2,FW pair was not interrupted by another W1 or S1.  This is important
+   to avoid blocking based on false/stale information.  For example, if S1
+   would not  increment __futex, then we would get a lost wake-up in
+   W1, S1, FW, block forever.  Instead, if FW does not block due to __futex
+   being changed concurrently, then it will either retry (W2) or finish (W3).
+   We retry waiting whenever no signal has happened yet after we started
+   waiting (val == seq) or when other waiting threads have consumed the
+   signals (val == woken_seq).
+
+   POSIX requires that if a waiting thread A's W1 happens before S1, A will
+   be considered as being "blocked" on the condvar by S1.  However, it does
+   not require that only those threads whose W1 happens before S1 are
+   considered to be blocked by S1; if S1 happens before W1 of thread B, B can
+   still be considered as blocked.  S1 will then waken one of the threads
+   being blocked.  Informally, executing S1 behaves like an asynchronous
+   signal: It will be consumed eventually at some time during or after S1,
+   and by one of the threads blocked on the condvar at that time (without any
+   fairness guarantees).  Bug #13165 discusses this in more detail.
+
+   In turn, this allows the implementation to not have to distinguish between
+   real and spurious wake-ups for FW, nor to have to maintain classes of
+   waiting threads based on which S1 the respective W1s happened before.  If
+   a signal is available (which can be determined based on the three shared
+   counters), the first waiting thread able to wake-up (spuriously or
+   otherwise) and acquire __lock will simply consume the signal.
+   Example execution (A, and B are waiting threads, A:W1 happens-before S1
+   happens-before A:W2): A:W1, A:FW, S1, B:W1, B:FW, B:FW returns (spurious),
+   B:W3, A:FW returns (real), A:W2.  B:FW can return spuriously due to a
+   third waiting thread executing W1 between B:W1 and B:FW, for example.
+
+   FIXME: When __futex overflows, this can create an ABA issue for FW,
+   potentially leading to a lost wake-up.  However, this only happens if the
+   thread is suspended between W1/W2 and FW and during this time, other
+   threads make UINT_MAX calls pthread_cond_wait or pthread_cond_signal.
+   Then, this thread will not wake-up until the next spurious or real wake-up
+   on __futex.  Alternatively,  32 pthread_cond_broadcast calls and one call
+   to either pthread_cond_wait or pthread_cond_signal can also trigger this
+   ABA issue.  */
+
 int
 __pthread_cond_wait (cond, mutex)
      pthread_cond_t *cond;
@@ -103,7 +186,7 @@ __pthread_cond_wait (cond, mutex)
 
   LIBC_PROBE (cond_wait, 2, cond, mutex);
 
-  /* Make sure we are alone.  */
+  /* Make sure we are alone.  Start of CS W1.  */
   lll_lock (cond->__data.__lock, pshared);
 
   /* Now we can release the mutex.  */
@@ -120,7 +203,7 @@ __pthread_cond_wait (cond, mutex)
   cond->__data.__nwaiters += 1 << COND_NWAITERS_SHIFT;
 
   /* Remember the mutex we are using here.  If there is already a
-     different address store this is a bad user bug.  Do not store
+     different address stored, this is a bad user bug.  Do not store
      anything for pshared condvars.  */
   if (cond->__data.__mutex != (void *) ~0l)
     cond->__data.__mutex = mutex;
@@ -129,7 +212,7 @@ __pthread_cond_wait (cond, mutex)
   cbuffer.cond = cond;
   cbuffer.mutex = mutex;
 
-  /* Before we block we enable cancellation.  Therefore we have to
+  /* Before we block, we enable cancellation.  Therefore, we have to
      install a cancellation handler.  */
   __pthread_cleanup_push (&buffer, __condvar_cleanup, &cbuffer);
 
@@ -151,20 +234,22 @@ __pthread_cond_wait (cond, mutex)
       /* Enable asynchronous cancellation.  Required by the standard.  */
       cbuffer.oldtype = __pthread_enable_asynccancel ();
 
-      /* Wait until woken by signal or broadcast.  */
+      /* Wait until woken by signal or broadcast.  We do not need to
+	 handle spurious wake-ups specially.  */
       lll_futex_wait (&cond->__data.__futex, futex_val, pshared);
 
       /* Disable asynchronous cancellation.  */
       __pthread_disable_asynccancel (cbuffer.oldtype);
 
-      /* We are going to look at shared data again, so get the lock.  */
+      /* We are going to look at shared data again, so get the lock.  Start
+         of CS W2 or W3.  */
       lll_lock (cond->__data.__lock, pshared);
 
       /* If a broadcast happened, we are done.  */
       if (cbuffer.bc_seq != cond->__data.__broadcast_seq)
 	goto bc_out;
 
-      /* Check whether we are eligible for wakeup.  */
+      /* Check whether we are eligible for wake-up.  */
       val = cond->__data.__wakeup_seq;
     }
   while (val == seq || cond->__data.__woken_seq == val);
@@ -176,7 +261,7 @@ __pthread_cond_wait (cond, mutex)
 
   cond->__data.__nwaiters -= 1 << COND_NWAITERS_SHIFT;
 
-  /* If pthread_cond_destroy was called on this varaible already,
+  /* If pthread_cond_destroy was called on this variable already,
      notify the pthread_cond_destroy caller all waiters have left
      and it can be successfully destroyed.  */
   if (cond->__data.__total_seq == -1ULL