text: /*
   * 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;
  }
  