path: root/nptl/pthread_cond_common.c

/* pthread_cond_common -- shared code for condition variable.
   Copyright (C) 2016-2023 Free Software Foundation, Inc.
   This file is part of the GNU C Library.

   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
   <https://www.gnu.org/licenses/>.  */

#include <atomic.h>
#include <atomic_wide_counter.h>
#include <stdint.h>
#include <pthread.h>

/* We need 3 least-significant bits on __wrefs for something else.
   This also matches __atomic_wide_counter requirements: The highest
   value we add is __PTHREAD_COND_MAX_GROUP_SIZE << 2 to __g1_start
   (the two extra bits are for the lock in the two LSBs of
   __g1_start).  */
#define __PTHREAD_COND_MAX_GROUP_SIZE ((unsigned) 1 << 29)

static inline uint64_t
__condvar_load_wseq_relaxed (pthread_cond_t *cond)
{
  return __atomic_wide_counter_load_relaxed (&cond->__data.__wseq);
}

static inline uint64_t
__condvar_fetch_add_wseq_acquire (pthread_cond_t *cond, unsigned int val)
{
  return __atomic_wide_counter_fetch_add_acquire (&cond->__data.__wseq, val);
}

static inline uint64_t
__condvar_load_g1_start_relaxed (pthread_cond_t *cond)
{
  return __atomic_wide_counter_load_relaxed (&cond->__data.__g1_start);
}

static inline void
__condvar_add_g1_start_relaxed (pthread_cond_t *cond, unsigned int val)
{
  __atomic_wide_counter_add_relaxed (&cond->__data.__g1_start, val);
}

#if __HAVE_64B_ATOMICS == 1

static inline uint64_t
__condvar_fetch_xor_wseq_release (pthread_cond_t *cond, unsigned int val)
{
  return atomic_fetch_xor_release (&cond->__data.__wseq.__value64, val);
}

#else /* !__HAVE_64B_ATOMICS */

/* The xor operation needs to be an atomic read-modify-write.  The write
   itself is not an issue as it affects just the lower-order half but not bits
   used in the add operation.  To make the full fetch-and-xor atomic, we
   exploit that concurrently, the value can increase by at most 1<<31 (*): The
   xor operation is only called while having acquired the lock, so not more
   than __PTHREAD_COND_MAX_GROUP_SIZE waiters can enter concurrently and thus
   increment __wseq.  Therefore, if the xor operation observes a value of
   __wseq, then the value it applies the modification to later on can be
   derived.  */

static uint64_t __attribute__ ((unused))
__condvar_fetch_xor_wseq_release (pthread_cond_t *cond, unsigned int val)
{
  /* First, get the current value.  See __atomic_wide_counter_load_relaxed.  */
  unsigned int h, l, h2;
  do
    {
      h = atomic_load_acquire (&cond->__data.__wseq.__value32.__high);
      l = atomic_load_acquire (&cond->__data.__wseq.__value32.__low);
      h2 = atomic_load_relaxed (&cond->__data.__wseq.__value32.__high);
    }
  while (h != h2);
  if (((l >> 31) > 0) && ((h >> 31) == 0))
    h++;
  h &= ~((unsigned int) 1 << 31);
  l &= ~((unsigned int) 1 << 31);

  /* Now modify.  Due to the coherence rules, the prior load will read a value
     earlier in modification order than the following fetch-xor.
     This uses release MO to make the full operation have release semantics
     (all other operations access the lower-order half).  */
  unsigned int l2
    = (atomic_fetch_xor_release (&cond->__data.__wseq.__value32.__low, val)
       & ~((unsigned int) 1 << 31));
  if (l2 < l)
    /* The lower-order half overflowed in the meantime.  This happened exactly
       once due to the limit on concurrent waiters (see above).  */
    h++;
  return ((uint64_t) h << 31) + l2;
}

#endif /* !__HAVE_64B_ATOMICS */

/* The lock that signalers use.  See pthread_cond_wait_common for uses.
   The lock is our normal three-state lock: not acquired (0) / acquired (1) /
   acquired-with-futex_wake-request (2).  However, we need to preserve the
   other bits in the unsigned int used for the lock, and therefore it is a
   little more complex.  */
static void __attribute__ ((unused))
__condvar_acquire_lock (pthread_cond_t *cond, int private)
{
  unsigned int s = atomic_load_relaxed (&cond->__data.__g1_orig_size);
  while ((s & 3) == 0)
    {
      if (atomic_compare_exchange_weak_acquire (&cond->__data.__g1_orig_size,
	  &s, s | 1))
	return;
      /* TODO Spinning and back-off.  */
    }
  /* We can't change from not acquired to acquired, so try to change to
     acquired-with-futex-wake-request and do a futex wait if we cannot change
     from not acquired.  */
  while (1)
    {
      while ((s & 3) != 2)
	{
	  if (atomic_compare_exchange_weak_acquire
	      (&cond->__data.__g1_orig_size, &s, (s & ~(unsigned int) 3) | 2))
	    {
	      if ((s & 3) == 0)
		return;
	      break;
	    }
	  /* TODO Back off.  */
	}
      futex_wait_simple (&cond->__data.__g1_orig_size,
	  (s & ~(unsigned int) 3) | 2, private);
      /* Reload so we see a recent value.  */
      s = atomic_load_relaxed (&cond->__data.__g1_orig_size);
    }
}

/* See __condvar_acquire_lock.  */
static void __attribute__ ((unused))
__condvar_release_lock (pthread_cond_t *cond, int private)
{
  if ((atomic_fetch_and_release (&cond->__data.__g1_orig_size,
				 ~(unsigned int) 3) & 3)
      == 2)
    futex_wake (&cond->__data.__g1_orig_size, 1, private);
}

/* Only use this when having acquired the lock.  */
static unsigned int __attribute__ ((unused))
__condvar_get_orig_size (pthread_cond_t *cond)
{
  return atomic_load_relaxed (&cond->__data.__g1_orig_size) >> 2;
}

/* Only use this when having acquired the lock.  */
static void __attribute__ ((unused))
__condvar_set_orig_size