/* Copyright (C) 2003-2018 Free Software Foundation, Inc.

   This file is part of the GNU C Library.

   Contributed by Martin Schwidefsky <schwidefsky@de.ibm.com>, 2003.

   The GNU C Library is free software; you can redistribute it and/or

   modify it under the terms of the GNU Lesser General Public

   License as published by the Free Software Foundation; either

   version 2.1 of the License, or (at your option) any later version.

   The GNU C Library is distributed in the hope that it will be useful,

   but WITHOUT ANY WARRANTY; without even the implied warranty of

   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.	 See the GNU

   Lesser General Public License for more details.

   You should have received a copy of the GNU Lesser General Public

   License along with the GNU C Library; if not, see

   <http://www.gnu.org/licenses/>.  */

#include <errno.h>

#include <sysdep.h>

#include <futex-internal.h>

#include <pthreadP.h>

/* 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 *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)

    {

      /* 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;

    }

  /* 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 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);

    }

  /* 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);

    }

  /* 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)