#include <errno.h>
#include <lib/sync/internal/mutex-internal.h>
#include <lib/sync/mutex.h>
#include <lib/zircon-internal/unique-backtrace.h>
#include <stdalign.h>
#include <threads.h>

#include "futex_impl.h"
#include "libc.h"
#include "threads_impl.h"

// The storage used by the _c_lock member of a cnd_t is actually treated like a
// sync_mutex_t under the hood.  This allows users of a cnd_t to be able to
// allocate one without needing to know anything about the sync_mutex_t
// implementation detail.  We need to be careful, however, to make certain that
// storage requirements don't change in a way which might lead to a mismatch.
//
// So; assert that the storage size and alignment of the _c_lock member are
// compatible with those needed by a sync_mutex_t instance.
static_assert(sizeof(((cnd_t*)0)->_c_lock) >= sizeof(sync_mutex_t),
              "cnd_t::_c_lock storage must be large enough to hold a sync_mutex_t instance");
static_assert(((alignof(cnd_t) + offsetof(cnd_t, _c_lock)) % alignof(sync_mutex_t)) == 0,
              "cnd_t::_c_lock storage must have compatible alignment with a sync_mutex_t instance");

struct waiter {
  struct waiter *prev, *next;
  atomic_int state;
  atomic_int barrier;
  atomic_int* notify;
};

enum {
  WAITING,
  LEAVING,
};

int cnd_timedwait(cnd_t* restrict c, mtx_t* restrict mutex,
                  const struct timespec* restrict ts) __TA_NO_THREAD_SAFETY_ANALYSIS {
  sync_mutex_t* m = (sync_mutex_t*)mutex;
  int e, clock = c->_c_clock, oldstate;

  if (ts && ts->tv_nsec >= 1000000000UL)
    return thrd_error;

  sync_mutex_lock((sync_mutex_t*)(&c->_c_lock));

  int seq = 2;
  struct waiter node = {
      .barrier = ATOMIC_VAR_INIT(seq),
      .state = ATOMIC_VAR_INIT(WAITING),
  };
  atomic_int* fut = &node.barrier;
  /* Add our waiter node onto the condvar's list.  We add the node to the
   * head of the list, but this is logically the end of the queue. */
  node.next = c->_c_head;
  c->_c_head = &node;
  if (!c->_c_tail)
    c->_c_tail = &node;
  else
    node.next->prev = &node;

  sync_mutex_unlock((sync_mutex_t*)(&c->_c_lock));
  sync_mutex_unlock(m);

  /* Wait to be signaled.  There are multiple ways this loop could exit:
   *  1) After being woken by __private_cond_signal().
   *  2) After being woken by sync_mutex_unlock(), after we were
   *     requeued from the condvar's futex to the mutex's futex (by
   *     cnd_timedwait() in another thread).
   *  3) After a timeout.
   *  4) On Linux, interrupted by an asynchronous signal.  This does
   *     not apply on Zircon. */
  do
    e = __timedwait(fut, seq, clock, ts);
  while (*fut == seq && !e);

  oldstate = a_cas_shim(&node.state, WAITING, LEAVING);

  if (oldstate == WAITING) {
    /* The wait timed out.  So far, this thread was not signaled by
     * cnd_signal()/cnd_broadcast() -- this thread was able to move
     * state.node out of the WAITING state before any
     * __private_cond_signal() call could do that.
     *
     * This thread must therefore remove the waiter node from the
     * list itself. */

    /* Access to cv object is valid because this waiter was not
     * yet signaled and a new signal/broadcast cannot return
     * after seeing a LEAVING waiter without getting notified
     * via the futex notify below. */

    sync_mutex_lock((sync_mutex_t*)(&c->_c_lock));

    /* Remove our waiter node from the list. */
    if (c->_c_head == &node)
      c->_c_head = node.next;
    else if (node.prev)
      node.prev->next = node.next;
    if (c->_c_tail == &node)
      c->_c_tail = node.prev;
    else if (node.next)
      node.next->prev = node.prev;

    sync_mutex_unlock((sync_mutex_t*)(&c->_c_lock));

    /* It is possible that __private_cond_signal() saw our waiter node
     * after we set node.state to LEAVING but before we removed the
     * node from the list.  If so, it will have set node.notify and
     * will be waiting on it, and we need to wake it up.
     *
     * This is rather complex.  An alternative would be to eliminate
     * the node.state field and always claim _c_lock if we could have
     * got a timeout.  However, that presumably has higher overhead
     * (since it contends _c_lock and involves more atomic ops). */
    if (node.notify) {
      if (atomic_fetch_add(node.notify, -1) == 1)
        _zx_futex_wake(node.notify, 1);
    }
  } else {
    /* Lock barrier first to control wake order. */
    lock(&node.barrier);
  }

  /* We must leave the mutex in the "locked with waiters" state here.
   * There are two reasons for that:
   *  1) If we do the unlock_requeue() below, a condvar waiter will be
   *     requeued to the mutex's futex.  We need to ensure that it will
   *     be signaled by sync_mutex_unlock() in future.
   *  2) If the current thread was woken via an unlock_requeue() +
   *     sync_mutex_unlock(), there *might* be another thread waiting for
   *     the mutex after us in the queue.  We need to ensure that it
   *     will be signaled by sync_mutex_unlock() in future. */
  sync_mutex_lock_with_waiter(m);

  /* By this point, our part of the waiter list cannot change further.
   * It has been unlinked from the condvar by __private_cond_signal().
   * It consists only of waiters that were woken explicitly by
   * cnd_signal()/cnd_broadcast().  Any timed-out waiters would have
   * removed themselves from the list before __private_cond_signal()
   * signaled the first node.barrier in our list.
   *
   * It is therefore safe now to read node.next and node.prev without
   * holding _c_lock. */

  if (oldstate != WAITING && node.prev) {
    /* Unlock the barrier that's holding back the next waiter, and
     * requeue it to the mutex so that it will be woken when the
     * mutex is unlocked. */
    zx_futex_storage_t mutex_val =
        __atomic_load_n((zx_futex_storage_t*)&m->futex, __ATOMIC_ACQUIRE);
    unlock_requeue(&node.prev->barrier, &m->futex, libsync_mutex_make_owner_from_state(mutex_val));
  }

  switch (e) {
    case 0:
      return 0;
    case EINVAL:
      return thrd_error;
    case ETIMEDOUT:
      return thrd_timedout;
    default:
      // No other error values are permissible from __timedwait_cp();
      CRASH_WITH_UNIQUE_BACKTRACE();
  }
}