[PATCH] Update to new generic semaphore algorithm v2

[Andreas Schwab]

On Jan 13 2015, Torvald Riegel wrote:

> +/* Slow path that blocks.  */
> +static int
> +__attribute__ ((noinline))
> +__new_sem_wait_slow (struct new_sem *sem, const struct timespec *abstime)
> +{
> +  int err = 0;
> +
> +#if __HAVE_64B_ATOMICS
> +  /* Add a waiter.  Relaxed MO is sufficient because we can rely on the
> +     ordering provided by the RMW operations we use.  */
> +  unsigned long d = atomic_fetch_add_relaxed (&sem->data,
> +      1UL << SEM_NWAITERS_SHIFT);
> +
> +  pthread_cleanup_push (__sem_wait_cleanup, sem);
> +
> +  /* Wait for a token to be available.  Retry until we can grab one.  */
> +  for (;;)
> +    {
> +      /* If there is no token available, sleep until there is.  */
> +      if ((d & SEM_VALUE_MASK) == 0)
> +	{
> +	  err = do_futex_wait (sem, abstime);
> +	  /* A futex return value of 0 or EAGAIN is due to a real or spurious
> +	     wake-up, or due to a change in the number of tokens.  We retry in
> +	     these cases.
> +	     If we timed out, forward this to the caller.
> +	     EINTR could be either due to being interrupted by a signal, or
> +	     due to a spurious wake-up.  Thus, we cannot distinguish between
> +	     both, and are not allowed to return EINTR to the caller but have
> +	     to retry; this is because we may not have been interrupted by a
> +	     signal.  However, if we assume that only signals cause a futex
> +	     return of EINTR, we forward EINTR to the caller.
> +
> +	     Retrying on EINTR is technically always allowed because to
> +	     reliably interrupt sem_wait with a signal, the signal handler
> +	     must call sem_post (which is AS-Safe).  In executions where the
> +	     signal handler does not do that, the implementation can correctly
> +	     claim that sem_wait hadn't actually started to execute yet, and
> +	     thus the signal never actually interrupted sem_wait.  We make no
> +	     timing guarantees, so the program can never observe that sem_wait
> +	     actually did start to execute.  Thus, in a correct program, we
> +	     can expect a signal that wanted to interrupt the sem_wait to have
> +	     provided a token, and can just try to grab this token if
> +	     futex_wait returns EINTR.  */
> +	  if (err == ETIMEDOUT ||
> +	      (err == EINTR && sem_assume_only_signals_cause_futex_EINTR))
> +	    {
> +	      __set_errno (err);
> +	      err = -1;
> +	      /* Stop being registered as a waiter.  */
> +	      atomic_fetch_add_relaxed (&sem->data,
> +		  -(1UL << SEM_NWAITERS_SHIFT));
> +	      break;
> +	    }
> +	  /* Relaxed MO is sufficient; see below.  */
> +	  d = atomic_load_relaxed (&sem->data);
> +	}
> +      else
> +	{
> +	  /* Try to grab both a token and stop being a waiter.  We need
> +	     acquire MO so this synchronizes with all token providers (i.e.,
> +	     the RMW operation we read from or all those before it in
> +	     modification order; also see sem_post).  On the failure path,
> +	     relaxed MO is sufficient because we only eventually need the
> +	     up-to-date value; the futex_wait or the CAS perform the real
> +	     work.  */
> +	  if (atomic_compare_exchange_weak_acquire (&sem->data,
> +	      &d, d - 1 - (1UL << SEM_NWAITERS_SHIFT)))

Doesn't that underflow the nwaiters field if there was a token
available on entry?  In that case the value of d is the semaphore data
_before_ incrementing the nwaiters field as fetched at the start of the
function.  I think the initial load should look like this:

+  unsigned long d = atomic_fetch_add_relaxed (&sem->data,
+      1UL << SEM_NWAITERS_SHIFT) + (1UL << SEM_NWAITERS_SHIFT);

-- 
Andreas Schwab, SUSE Labs, schwab@suse.de
GPG Key fingerprint = 0196 BAD8 1CE9 1970 F4BE  1748 E4D4 88E3 0EEA B9D7
"And now for something completely different."