New pthread_barrier algorithm to fulfill barrier destruction requirements.

The previous barrier implementation did not fulfill the POSIX requirements
for when a barrier can be destroyed.  Specifically, it was possible that
threads that haven't noticed yet that their round is complete still access
the barrier's memory, and that those accesses can happen after the barrier
has been legally destroyed.
The new algorithm does not have this issue, and it avoids using a lock
internally.

1 files changed, 186 insertions, 43 deletions

diff --git a/nptl/pthread_barrier_wait.c b/nptl/pthread_barrier_wait.c
index c9c37e187c..eabb5099d3 100644
--- a/nptl/pthread_barrier_wait.c
+++ b/nptl/pthread_barrier_wait.c
@@ -18,63 +18,206 @@
 
 #include <errno.h>
 #include <sysdep.h>
-#include <lowlevellock.h>
 #include <futex-internal.h>
 #include <pthreadP.h>
 
 
-/* Wait on barrier.  */
+/* Wait on the barrier.
+
+   In each round, we wait for a fixed number of threads to enter the barrier
+   (COUNT).  Once that has happened, exactly these threads are allowed to
+   leave the barrier.  Note that POSIX does not require that only COUNT
+   threads can attempt to block using the barrier concurrently.
+
+   We count the number of threads that have entered (IN).  Each thread
+   increments IN when entering, thus getting a position in the sequence of
+   threads that are or have been waiting (starting with 1, so the position
+   is the number of threads that have entered so far including the current
+   thread).
+   CURRENT_ROUND designates the most recent thread whose round has been
+   detected as complete.  When a thread detects that enough threads have
+   entered to make a round complete, it finishes this round by effectively
+   adding COUNT to CURRENT_ROUND atomically.  Threads that believe that their
+   round is not complete yet wait until CURRENT_ROUND is not smaller than
+   their position anymore.
+
+   A barrier can be destroyed as soon as no threads are blocked on the
+   barrier.  This is already the case if just one thread from the last round
+   has stopped waiting and returned to the caller; the assumption is that
+   all threads from the round are unblocked atomically, even though they may
+   return at different times from the respective calls to
+   pthread_barrier_wait).  Thus, a valid call to pthread_barrier_destroy can
+   be concurrent with other threads still figuring out that their round has
+   been completed.  Therefore, threads need to confirm that they have left
+   the barrier by incrementing OUT, and pthread_barrier_destroy needs to wait
+   until OUT equals IN.
+
+   To avoid an ABA issue for futex_wait on CURRENT_ROUND and for archs with
+   32b-only atomics, we additionally reset the barrier when IN reaches
+   a threshold to avoid overflow.  We assume that the total number of threads
+   is less than UINT_MAX/2, and set the threshold accordingly so that we can
+   use a simple atomic_fetch_add on IN instead of a CAS when entering.  The
+   threshold is always set to the end of a round, so all threads that have
+   entered are either pre-reset threads or post-reset threads (i.e., have a
+   position larger than the threshold).
+   Pre-reset threads just run the algorithm explained above.  Post-reset
+   threads wait until IN is reset to a pre-threshold value.
+   When the last pre-reset thread leaves the barrier (i.e., OUT equals the
+   threshold), it resets the barrier to its initial state.  Other (post-reset)
+   threads wait for the reset to have finished by waiting until IN is less
+   than the threshold and then restart by trying to enter the barrier again.
+
+   We reuse the reset mechanism in pthread_barrier_destroy to get notified
+   when all threads have left the barrier: We trigger an artificial reset and
+   wait for the last pre-reset thread to finish reset, thus notifying the
+   thread that is about to destroy the barrier.
+
+   Blocking using futexes is straightforward: pre-reset threads wait for
+   completion of their round using CURRENT_ROUND as futex word, and post-reset
+   threads and pthread_barrier_destroy use IN as futex word.
+
+   Further notes:
+   * It is not simple to let some of the post-reset threads help with the
+     reset because of the ABA issues that arise; therefore, we simply make
+     the last thread to leave responsible for the reset.
+   * POSIX leaves it unspecified whether a signal handler running in a thread
+     that has been unblocked (because its round is complete) can stall all
+     other threads and prevent them from returning from the barrier.  In this
+     implementation, other threads will return.  However,
+     pthread_barrier_destroy will of course wait for the signal handler thread
+     to confirm that it left the barrier.
+
+   TODO We should add spinning with back-off.  Once we do that, we could also
+   try to avoid the futex_wake syscall when a round is detected as finished.
+   If we do not spin, it is quite likely that at least some other threads will
+   have called futex_wait already.  */
 int
 __pthread_barrier_wait (pthread_barrier_t *barrier)
 {
-  struct pthread_barrier *ibarrier = (struct pthread_barrier *) barrier;
-  int result = 0;
-  int lll_private = ibarrier->private ^ FUTEX_PRIVATE_FLAG;
-  int futex_private = (lll_private == LLL_PRIVATE
-		       ? FUTEX_PRIVATE : FUTEX_SHARED);
-
-  /* Make sure we are alone.  */
-  lll_lock (ibarrier->lock, lll_private);
-
-  /* One more arrival.  */
-  --ibarrier->left;
-
-  /* Are these all?  */
-  if (ibarrier->left == 0)
+  struct pthread_barrier *bar = (struct pthread_barrier *) barrier;
+
+  /* How many threads entered so far, including ourself.  */
+  unsigned int i;
+
+ reset_restart:
+  /* Try to enter the barrier.  We need acquire MO to (1) ensure that if we
+     observe that our round can be completed (see below for our attempt to do
+     so), all pre-barrier-entry effects of all threads in our round happen
+     before us completing the round, and (2) to make our use of the barrier
+     happen after a potential reset.  We need release MO to make sure that our
+     pre-barrier-entry effects happen before threads in this round leaving the
+     barrier.  */
+  i = atomic_fetch_add_acq_rel (&bar->in, 1) + 1;
+  /* These loads are after the fetch_add so that we're less likely to first
+     pull in the cache line as shared.  */
+  unsigned int count = bar->count;
+  /* This is the number of threads that can enter before we need to reset.
+     Always at the end of a round.  */
+  unsigned int max_in_before_reset = BARRIER_IN_THRESHOLD
+				   - BARRIER_IN_THRESHOLD % count;
+
+  if (i > max_in_before_reset)
     {
-      /* Yes. Increment the event counter to avoid invalid wake-ups and
-	 tell the current waiters that it is their turn.  */
-      ++ibarrier->curr_event;
-
-      /* Wake up everybody.  */
-      futex_wake (&ibarrier->curr_event, INT_MAX, futex_private);
-
-      /* This is the thread which finished the serialization.  */
-      result = PTHREAD_BARRIER_SERIAL_THREAD;
+      /* We're in a reset round.  Just wait for a reset to finish; do not
+	 help finishing previous rounds because this could happen
+	 concurrently with a reset.  */
+      while (i > max_in_before_reset)
+	{
+	  futex_wait_simple (&bar->in, i, bar->shared);
+	  /* Relaxed MO is fine here because we just need an indication for
+	     when we should retry to enter (which will use acquire MO, see
+	     above).  */
+	  i = atomic_load_relaxed (&bar->in);
+	}
+      goto reset_restart;
     }
-  else
-    {
-      /* The number of the event we are waiting for.  The barrier's event
-	 number must be bumped before we continue.  */
-      unsigned int event = ibarrier->curr_event;
 
-      /* Before suspending, make the barrier available to others.  */
-      lll_unlock (ibarrier->lock, lll_private);
+  /* Look at the current round.  At this point, we are just interested in
+     whether we can complete rounds, based on the information we obtained
+     through our acquire-MO load of IN.  Nonetheless, if we notice that
+     our round has been completed using this load, we use the acquire-MO
+     fence below to make sure that all pre-barrier-entry effects of all
+     threads in our round happen before us leaving the barrier.  Therefore,
+     relaxed MO is sufficient.  */
+  unsigned cr = atomic_load_relaxed (&bar->current_round);
+
+  /* Try to finish previous rounds and/or the current round.  We simply
+     consider just our position here and do not try to do the work of threads
+     that entered more recently.  */
+  while (cr + count <= i)
+    {
+      /* Calculate the new current round based on how many threads entered.
+	 NEWCR must be larger than CR because CR+COUNT ends a round.  */
+      unsigned int newcr = i - i % count;
+      /* Try to complete previous and/or the current round.  We need release
+	 MO to propagate the happens-before that we observed through reading
+	 with acquire MO from IN to other threads.  If the CAS fails, it
+	 is like the relaxed-MO load of CURRENT_ROUND above.  */
+      if (atomic_compare_exchange_weak_release (&bar->current_round, &cr,
+						newcr))
+	{
+	  /* Update CR with the modification we just did.  */
+	  cr = newcr;
+	  /* Wake threads belonging to the rounds we just finished.  We may
+	     wake more threads than necessary if more than COUNT threads try
+	     to block concurrently on the barrier, but this is not a typical
+	     use of barriers.
+	     Note that we can still access SHARED because we haven't yet
+	     confirmed to have left the barrier.  */
+	  futex_wake (&bar->current_round, INT_MAX, bar->shared);
+	  /* We did as much as we could based on our position.  If we advanced
+	     the current round to a round sufficient for us, do not wait for
+	     that to happen and skip the acquire fence (we already
+	     synchronize-with all other threads in our round through the
+	     initial acquire MO fetch_add of IN.  */
+	  if (i <= cr)
+	    goto ready_to_leave;
+	  else
+	    break;
+	}
+    }
 
-      /* Wait for the event counter of the barrier to change.  */
-      do
-	futex_wait_simple (&ibarrier->curr_event, event, futex_private);
-      while (event == ibarrier->curr_event);
+  /* Wait until the current round is more recent than the round we are in.  */
+  while (i > cr)
+    {
+      /* Wait for the current round to finish.  */
+      futex_wait_simple (&bar->current_round, cr, bar->shared);
+      /* See the fence below.  */
+      cr = atomic_load_relaxed (&bar->current_round);
     }
 
-  /* Make sure the init_count is stored locally or in a register.  */
-  unsigned int init_count = ibarrier->init_count;
+  /* Our round finished.  Use the acquire MO fence to synchronize-with the
+     thread that finished the round, either through the initial load of
+     CURRENT_ROUND above or a failed CAS in the loop above.  */
+  atomic_thread_fence_acquire ();
+
+  /* Now signal that we left.  */
+  unsigned int o;
+ ready_to_leave:
+  /* We need release MO here so that our use of the barrier happens before
+     reset or memory reuse after pthread_barrier_destroy.  */
+  o = atomic_fetch_add_release (&bar->out, 1) + 1;
+  if (o == max_in_before_reset)
+    {
+      /* Perform a reset if we are the last pre-reset thread leaving.   All
+	 other threads accessing the barrier are post-reset threads and are
+	 incrementing or spinning on IN.  Thus, resetting IN as the last step
+	 of reset ensures that the reset is not concurrent with actual use of
+	 the barrier.  We need the acquire MO fence so that the reset happens
+	 after use of the barrier by all earlier pre-reset threads.  */
+      atomic_thread_fence_acquire ();
+      atomic_store_relaxed (&bar->current_round, 0);
+      atomic_store_relaxed (&bar->out, 0);
+      /* When destroying the barrier, we wait for a reset to happen.  Thus,
+	 we must load SHARED now so that this happens before the barrier is
+	 destroyed.  */
+      int shared = bar->shared;
+      atomic_store_release (&bar->in, 0);
+      futex_wake (&bar->in, INT_MAX, shared);
 
-  /* If this was the last woken thread, unlock.  */
-  if (atomic_increment_val (&ibarrier->left) == init_count)
-    /* We are done.  */
-    lll_unlock (ibarrier->lock, lll_private);
+    }
 
-  return result;
+  /* Return a special value for exactly one thread per round.  */
+  return i % count == 0 ?  PTHREAD_BARRIER_SERIAL_THREAD : 0;
 }
 weak_alias (__pthread_barrier_wait, pthread_barrier_wait)