/*
 * Copyright (C) 2010 The Android Open Source Project
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *  * Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 *  * Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in
 *    the documentation and/or other materials provided with the
 *    distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
 * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */

#include <errno.h>
#include <stdatomic.h>
#include <string.h>

#include "pthread_internal.h"
#include "private/bionic_futex.h"
#include "private/bionic_lock.h"
#include "private/bionic_time_conversions.h"

/* Technical note:
 *
 * Possible states of a read/write lock:
 *
 *  - no readers and no writer (unlocked)
 *  - one or more readers sharing the lock at the same time (read-locked)
 *  - one writer holding the lock (write-lock)
 *
 * Additionally:
 *  - trying to get the write-lock while there are any readers blocks
 *  - trying to get the read-lock while there is a writer blocks
 *  - a single thread can acquire the lock multiple times in read mode
 *
 *  - Posix states that behavior is undefined (may deadlock) if a thread tries
 *    to acquire the lock
 *      - in write mode while already holding the lock (whether in read or write mode)
 *      - in read mode while already holding the lock in write mode.
 *  - This implementation will return EDEADLK in "write after write" and "read after
 *    write" cases and will deadlock in write after read case.
 *
 */

// A rwlockattr is implemented as a 32-bit integer which has following fields:
//  bits    name              description
//   1     rwlock_kind       have rwlock preference like PTHREAD_RWLOCK_PREFER_READER_NP.
//   0      process_shared    set to 1 if the rwlock is shared between processes.

#define RWLOCKATTR_PSHARED_SHIFT 0
#define RWLOCKATTR_KIND_SHIFT    1

#define RWLOCKATTR_PSHARED_MASK  1
#define RWLOCKATTR_KIND_MASK     2
#define RWLOCKATTR_RESERVED_MASK (~3)

static inline __always_inline __always_inline bool __rwlockattr_getpshared(const pthread_rwlockattr_t* attr) {
  return (*attr & RWLOCKATTR_PSHARED_MASK) >> RWLOCKATTR_PSHARED_SHIFT;
}

static inline __always_inline __always_inline void __rwlockattr_setpshared(pthread_rwlockattr_t* attr, int pshared) {
  *attr = (*attr & ~RWLOCKATTR_PSHARED_MASK) | (pshared << RWLOCKATTR_PSHARED_SHIFT);
}

static inline __always_inline int __rwlockattr_getkind(const pthread_rwlockattr_t* attr) {
  return (*attr & RWLOCKATTR_KIND_MASK) >> RWLOCKATTR_KIND_SHIFT;
}

static inline __always_inline void __rwlockattr_setkind(pthread_rwlockattr_t* attr, int kind) {
  *attr = (*attr & ~RWLOCKATTR_KIND_MASK) | (kind << RWLOCKATTR_KIND_SHIFT);
}


int pthread_rwlockattr_init(pthread_rwlockattr_t* attr) {
  *attr = 0;
  return 0;
}

int pthread_rwlockattr_destroy(pthread_rwlockattr_t* attr) {
  *attr = -1;
  return 0;
}

int pthread_rwlockattr_getpshared(const pthread_rwlockattr_t* attr, int* pshared) {
  if (__rwlockattr_getpshared(attr)) {
    *pshared = PTHREAD_PROCESS_SHARED;
  } else {
    *pshared = PTHREAD_PROCESS_PRIVATE;
  }
  return 0;
}

int pthread_rwlockattr_setpshared(pthread_rwlockattr_t* attr, int pshared) {
  switch (pshared) {
    case PTHREAD_PROCESS_PRIVATE:
      __rwlockattr_setpshared(attr, 0);
      return 0;
    case PTHREAD_PROCESS_SHARED:
      __rwlockattr_setpshared(attr, 1);
      return 0;
    default:
      return EINVAL;
  }
}

int pthread_rwlockattr_getkind_np(const pthread_rwlockattr_t* attr, int* pref) {
  *pref = __rwlockattr_getkind(attr);
  return 0;
}

int pthread_rwlockattr_setkind_np(pthread_rwlockattr_t* attr, int pref) {
  switch (pref) {
    case PTHREAD_RWLOCK_PREFER_READER_NP:   // Fall through.
    case PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP:
      __rwlockattr_setkind(attr, pref);
      return 0;
    default:
      return EINVAL;
  }
}

// A rwlock state is implemented as a 32-bit integer which has following rules:
//  bits      name                              description
//   31      owned_by_writer_flag              set to 1 if the lock is owned by a writer now.
//  30-2     reader_count                      the count of readers holding the lock.
//   1       have_pending_writers              set to 1 if having pending writers.
//   0       have_pending_readers              set to 1 if having pending readers.

#define STATE_HAVE_PENDING_READERS_SHIFT    0
#define STATE_HAVE_PENDING_WRITERS_SHIFT    1
#define STATE_READER_COUNT_SHIFT            2
#define STATE_OWNED_BY_WRITER_SHIFT        31

#define STATE_HAVE_PENDING_READERS_FLAG     (1 << STATE_HAVE_PENDING_READERS_SHIFT)
#define STATE_HAVE_PENDING_WRITERS_FLAG     (1 << STATE_HAVE_PENDING_WRITERS_SHIFT)
#define STATE_READER_COUNT_CHANGE_STEP  (1 << STATE_READER_COUNT_SHIFT)
#define STATE_OWNED_BY_WRITER_FLAG      (1 << STATE_OWNED_BY_WRITER_SHIFT)

#define STATE_HAVE_PENDING_READERS_OR_WRITERS_FLAG \
          (STATE_HAVE_PENDING_READERS_FLAG | STATE_HAVE_PENDING_WRITERS_FLAG)

struct pthread_rwlock_internal_t {
  atomic_int state;
  atomic_int writer_tid;

  bool pshared;
  bool writer_nonrecursive_preferred;
  uint16_t __pad;

// When a reader thread plans to suspend on the rwlock, it will add STATE_HAVE_PENDING_READERS_FLAG
// in state, increase pending_reader_count, and wait on pending_reader_wakeup_serial. After woken
// up, the reader thread decreases pending_reader_count, and the last pending reader thread should
// remove STATE_HAVE_PENDING_READERS_FLAG in state. A pending writer thread works in a similar way,
// except that it uses flag and members for writer threads.

  Lock pending_lock;  // All pending members below are protected by pending_lock.
  uint32_t pending_reader_count;  // Count of pending reader threads.
  uint32_t pending_writer_count;  // Count of pending writer threads.
  uint32_t pending_reader_wakeup_serial;  // Pending reader threads wait on this address by futex_wait.
  uint32_t pending_writer_wakeup_serial;  // Pending writer threads wait on this address by futex_wait.

#if defined(__LP64__)
  char __reserved[20];
#else
  char __reserved[4];
#endif
};

static inline __always_inline bool __state_owned_by_writer(int state) {
  return state < 0;
}

static inline __always_inline bool __state_owned_by_readers(int state) {
  // If state >= 0, the owned_by_writer_flag is not set.
  // And if state >= STATE_READER_COUNT_CHANGE_STEP, the reader_count field is not empty.
  return state >= STATE_READER_COUNT_CHANGE_STEP;
}

static inline __always_inline bool __state_owned_by_readers_or_writer(int state) {
  return state < 0 || state >= STATE_READER_COUNT_CHANGE_STEP;
}

static inline __always_inline int __state_add_writer_flag(int state) {
  return state | STATE_OWNED_BY_WRITER_FLAG;
}

static inline __always_inline bool __state_is_last_reader(int state) {
  return (state >> STATE_READER_COUNT_SHIFT) == 1;
}

static inline __always_inline bool __state_have_pending_writers(int state) {
  return state & STATE_HAVE_PENDING_WRITERS_FLAG;
}

static inline __always_inline bool __state_have_pending_readers_or_writers(int state) {
  return state & STATE_HAVE_PENDING_READERS_OR_WRITERS_FLAG;
}

static_assert(sizeof(pthread_rwlock_t) == sizeof(pthread_rwlock_internal_t),
              "pthread_rwlock_t should actually be pthread_rwlock_internal_t in implementation.");

// For binary compatibility with old version of pthread_rwlock_t, we can't use more strict
// alignment than 4-byte alignment.
static_assert(alignof(pthread_rwlock_t) == 4,
             "pthread_rwlock_t should fulfill the alignment requirement of pthread_rwlock_internal_t.");

static inline __always_inline pthread_rwlock_internal_t* __get_internal_rwlock(pthread_rwlock_t* rwlock_interface) {
  return reinterpret_cast<pthread_rwlock_internal_t*>(rwlock_interface);
}

int pthread_rwlock_init(pthread_rwlock_t* rwlock_interface, const pthread_rwlockattr_t* attr) {
  pthread_rwlock_internal_t* rwlock = __get_internal_rwlock(rwlock_interface);

  memset(rwlock, 0, sizeof(pthread_rwlock_internal_t));

  if (__predict_false(attr != NULL)) {
    rwlock->pshared = __rwlockattr_getpshared(attr);
    int kind = __rwlockattr_getkind(attr);
    switch (kind) {
      case PTHREAD_RWLOCK_PREFER_READER_NP:
        rwlock->writer_nonrecursive_preferred = false;
        break;
      case PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP:
        rwlock->writer_nonrecursive_preferred = true;
        break;
      default:
        return EINVAL;
    }
    if ((*attr & RWLOCKATTR_RESERVED_MASK) != 0) {
      return EINVAL;
    }
  }

  atomic_init(&rwlock->state, 0);
  rwlock->pending_lock.init(rwlock->pshared);
  return 0;
}

int pthread_rwlock_destroy(pthread_rwlock_t* rwlock_interface) {
  pthread_rwlock_internal_t* rwlock = __get_internal_rwlock(rwlock_interface);

  if (atomic_load_explicit(&rwlock->state, memory_order_relaxed) != 0) {
    return EBUSY;
  }
  return 0;
}

static inline __always_inline bool __can_acquire_read_lock(int old_state,
                                                             bool writer_nonrecursive_preferred) {
  // If writer is preferred with nonrecursive reader, we prevent further readers from acquiring
  // the lock when there are writers waiting for the lock.
  bool cannot_apply = __state_owned_by_writer(old_state) ||
                      (writer_nonrecursive_preferred && __state_have_pending_writers(old_state));
  return !cannot_apply;
}

static inline __always_inline int __pthread_rwlock_tryrdlock(pthread_rwlock_internal_t* rwlock) {
  int old_state = atomic_load_explicit(&rwlock->state, memory_order_relaxed);

  while (__predict_true(__can_acquire_read_lock(old_state, rwlock->writer_nonrecursive_preferred))) {

    int new_state = old_state + STATE_READER_COUNT_CHANGE_STEP;
    if (__predict_false(!__state_owned_by_readers(new_state))) { // Happens when reader count overflows.
      return EAGAIN;
    }
    if (__predict_true(atomic_compare_exchange_weak_explicit(&rwlock->state, &old_state, new_state,
                                              memory_order_acquire, memory_order_relaxed))) {
      return 0;
    }
  }
  return EBUSY;
}

static int __pthread_rwlock_timedrdlock(pthread_rwlock_internal_t* rwlock,
                                        const timespec* abs_timeout_or_null) {

  if (atomic_load_explicit(&rwlock->writer_tid, memory_order_relaxed) == __get_thread()->tid) {
    return EDEADLK;
  }

  while (true) {
    int ret = __pthread_rwlock_tryrdlock(rwlock);
    if (ret == 0 || ret == EAGAIN) {
      return ret;
    }

    int old_state = atomic_load_explicit(&rwlock->state, memory_order_relaxed);
    if (__can_acquire_read_lock(old_state, rwlock->writer_nonrecursive_preferred)) {
      continue;
    }

    timespec ts;
    timespec* rel_timeout = NULL;

    if (abs_timeout_or_null != NULL) {
      rel_timeout = &ts;
      if (!timespec_from_absolute_timespec(*rel_timeout, *abs_timeout_or_null, CLOCK_REALTIME)) {
        return ETIMEDOUT;
      }
    }

    rwlock->pending_lock.lock();
    rwlock->pending_reader_count++;

    // We rely on the fact that all atomic exchange operations on the same object (here it is
    // rwlock->state) always appear to occur in a single total order. If the pending flag is added
    // before unlocking, the unlocking thread will wakeup the waiter. Otherwise, we will see the
    // state is unlocked and will not wait anymore.
    old_state = atomic_fetch_or_explicit(&rwlock->state, STATE_HAVE_PENDING_READERS_FLAG,
                                         memory_order_relaxed);

    int old_serial = rwlock->pending_reader_wakeup_serial;
    rwlock->pending_lock.unlock();

    int futex_ret = 0;
    if (!__can_acquire_read_lock(old_state, rwlock->writer_nonrecursive_preferred)) {
      futex_ret = __futex_wait_ex(&rwlock->pending_reader_wakeup_serial, rwlock->pshared,
                                  old_serial, rel_timeout);
    }

    rwlock->pending_lock.lock();
    rwlock->pending_reader_count--;
    if (rwlock->pending_reader_count == 0) {
      atomic_fetch_and_explicit(&rwlock->state, ~STATE_HAVE_PENDING_READERS_FLAG,
                                memory_order_relaxed);
    }
    rwlock->pending_lock.unlock();

    if (futex_ret == -ETIMEDOUT) {
      return ETIMEDOUT;
    }
  }
}

static inline __always_inline bool __can_acquire_write_lock(int old_state) {
  return !__state_owned_by_readers_or_writer(old_state);
}

static inline __always_inline int __pthread_rwlock_trywrlock(pthread_rwlock_internal_t* rwlock) {
  int old_state = atomic_load_explicit(&rwlock->state, memory_order_relaxed);

  while (__predict_true(__can_acquire_write_lock(old_state))) {
    if (__predict_true(atomic_compare_exchange_weak_explicit(&rwlock->state, &old_state,
          __state_add_writer_flag(old_state), memory_order_acquire, memory_order_relaxed))) {

      atomic_store_explicit(&rwlock->writer_tid, __get_thread()->tid, memory_order_relaxed);
      return 0;
    }
  }
  return EBUSY;
}

static int __pthread_rwlock_timedwrlock(pthread_rwlock_internal_t* rwlock,
                                        const timespec* abs_timeout_or_null) {

  if (atomic_load_explicit(&rwlock->writer_tid, memory_order_relaxed) == __get_thread()->tid) {
    return EDEADLK;
  }
  while (true) {
    int ret = __pthread_rwlock_trywrlock(rwlock);
    if (ret == 0) {
      return ret;
    }

    int old_state = atomic_load_explicit(&rwlock->state, memory_order_relaxed);
    if (__can_acquire_write_lock(old_state)) {
      continue;
    }

    timespec ts;
    timespec* rel_timeout = NULL;

    if (abs_timeout_or_null != NULL) {
      rel_timeout = &ts;
      if (!timespec_from_absolute_timespec(*rel_timeout, *abs_timeout_or_null, CLOCK_REALTIME)) {
        return ETIMEDOUT;
      }
    }

    rwlock->pending_lock.lock();
    rwlock->pending_writer_count++;

    old_state = atomic_fetch_or_explicit(&rwlock->state, STATE_HAVE_PENDING_WRITERS_FLAG,
                                         memory_order_relaxed);

    int old_serial = rwlock->pending_writer_wakeup_serial;
    rwlock->pending_lock.unlock();

    int futex_ret = 0;
    if (!__can_acquire_write_lock(old_state)) {
      futex_ret = __futex_wait_ex(&rwlock->pending_writer_wakeup_serial, rwlock->pshared,
                                  old_serial, rel_timeout);
    }

    rwlock->pending_lock.lock();
    rwlock->pending_writer_count--;
    if (rwlock->pending_writer_count == 0) {
      atomic_fetch_and_explicit(&rwlock->state, ~STATE_HAVE_PENDING_WRITERS_FLAG,
                                memory_order_relaxed);
    }
    rwlock->pending_lock.unlock();

    if (futex_ret == -ETIMEDOUT) {
      return ETIMEDOUT;
    }
  }
}

int pthread_rwlock_rdlock(pthread_rwlock_t* rwlock_interface) {
  pthread_rwlock_internal_t* rwlock = __get_internal_rwlock(rwlock_interface);
  // Avoid slowing down fast path of rdlock.
  if (__predict_true(__pthread_rwlock_tryrdlock(rwlock) == 0)) {
    return 0;
  }
  return __pthread_rwlock_timedrdlock(rwlock, NULL);
}

int pthread_rwlock_timedrdlock(pthread_rwlock_t* rwlock_interface, const timespec* abs_timeout) {
  pthread_rwlock_internal_t* rwlock = __get_internal_rwlock(rwlock_interface);

  return __pthread_rwlock_timedrdlock(rwlock, abs_timeout);
}

int pthread_rwlock_tryrdlock(pthread_rwlock_t* rwlock_interface) {
  return __pthread_rwlock_tryrdlock(__get_internal_rwlock(rwlock_interface));
}

int pthread_rwlock_wrlock(pthread_rwlock_t* rwlock_interface) {
  pthread_rwlock_internal_t* rwlock = __get_internal_rwlock(rwlock_interface);
  // Avoid slowing down fast path of wrlock.
  if (__predict_true(__pthread_rwlock_trywrlock(rwlock) == 0)) {
    return 0;
  }
  return __pthread_rwlock_timedwrlock(rwlock, NULL);
}

int pthread_rwlock_timedwrlock(pthread_rwlock_t* rwlock_interface, const timespec* abs_timeout) {
  pthread_rwlock_internal_t* rwlock = __get_internal_rwlock(rwlock_interface);

  return __pthread_rwlock_timedwrlock(rwlock, abs_timeout);
}

int pthread_rwlock_trywrlock(pthread_rwlock_t* rwlock_interface) {
  return __pthread_rwlock_trywrlock(__get_internal_rwlock(rwlock_interface));
}

int pthread_rwlock_unlock(pthread_rwlock_t* rwlock_interface) {
  pthread_rwlock_internal_t* rwlock = __get_internal_rwlock(rwlock_interface);

  int old_state = atomic_load_explicit(&rwlock->state, memory_order_relaxed);
  if (__state_owned_by_writer(old_state)) {
    if (atomic_load_explicit(&rwlock->writer_tid, memory_order_relaxed) != __get_thread()->tid) {
      return EPERM;
    }
    atomic_store_explicit(&rwlock->writer_tid, 0, memory_order_relaxed);
    old_state = atomic_fetch_and_explicit(&rwlock->state, ~STATE_OWNED_BY_WRITER_FLAG,
                                          memory_order_release);
    if (!__state_have_pending_readers_or_writers(old_state)) {
      return 0;
    }

  } else if (__state_owned_by_readers(old_state)) {
    old_state = atomic_fetch_sub_explicit(&rwlock->state, STATE_READER_COUNT_CHANGE_STEP,
                                          memory_order_release);
    if (!__state_is_last_reader(old_state) || !__state_have_pending_readers_or_writers(old_state)) {
      return 0;
    }

  } else {
    return EPERM;
  }

  // Wake up pending readers or writers.
  rwlock->pending_lock.lock();
  if (rwlock->pending_writer_count != 0) {
    rwlock->pending_writer_wakeup_serial++;
    rwlock->pending_lock.unlock();

    __futex_wake_ex(&rwlock->pending_writer_wakeup_serial, rwlock->pshared, 1);

  } else if (rwlock->pending_reader_count != 0) {
    rwlock->pending_reader_wakeup_serial++;
    rwlock->pending_lock.unlock();

    __futex_wake_ex(&rwlock->pending_reader_wakeup_serial, rwlock->pshared, INT_MAX);

  } else {
    // It happens when waiters are woken up by timeout.
    rwlock->pending_lock.unlock();
  }
  return 0;
}