// Copyright 2015 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef V8_EXECUTION_FUTEX_EMULATION_H_
#define V8_EXECUTION_FUTEX_EMULATION_H_

#include <stdint.h>

#include "include/v8-persistent-handle.h"
#include "src/base/atomicops.h"
#include "src/base/macros.h"
#include "src/base/platform/condition-variable.h"
#include "src/base/platform/time.h"
#include "src/tasks/cancelable-task.h"
#include "src/utils/allocation.h"

// Support for emulating futexes, a low-level synchronization primitive. They
// are natively supported by Linux, but must be emulated for other platforms.
// This library emulates them on all platforms using mutexes and condition
// variables for consistency.
//
// This is used by the Futex API defined in the SharedArrayBuffer draft spec,
// found here: https://github.com/tc39/ecmascript_sharedmem

namespace v8 {

class Promise;

namespace base {
class TimeDelta;
}  // namespace base

namespace internal {

class BackingStore;
class FutexWaitList;
#if V8_ENABLE_WEBASSEMBLY
class FutexManagedObjectWaitList;
template <class CppType>
class Managed;
#endif

class Isolate;
class JSArrayBuffer;
class JSPromise;
class NoGarbageCollectionMutexGuard;

class FutexWaitListNode {
 public:
  // Create a sync FutexWaitListNode.
  FutexWaitListNode() = default;

  // Create an async FutexWaitListNode.
  FutexWaitListNode(std::weak_ptr<BackingStore> backing_store,
                    void* wait_location,
                    DirectHandle<JSPromise> promise_capability,
                    Isolate* isolate);

  // Disallow copying nodes.
  FutexWaitListNode(const FutexWaitListNode&) = delete;
  FutexWaitListNode& operator=(const FutexWaitListNode&) = delete;

  void NotifyWake();

  bool IsAsync() const { return async_state_ != nullptr; }
  bool IsWaiting() const { return waiting_.load(std::memory_order_relaxed); }
  bool IsInSyncWait() const { return in_sync_wait_; }
  void SetInSyncWait(bool v) { in_sync_wait_ = v; }

  // Returns false if the cancelling failed, true otherwise.
  bool CancelTimeoutTask();

 private:
  friend class FutexEmulation;
  friend class FutexWaitList;
#if V8_ENABLE_WEBASSEMBLY
  friend class FutexManagedObjectWaitList;
#endif

  // Async wait requires substantially more information than synchronous wait.
  // Hence store that additional information in a heap-allocated struct to make
  // it more obvious that this will only be needed for the async case.
  struct AsyncState {
    AsyncState(Isolate* isolate, std::shared_ptr<TaskRunner> task_runner,
               std::weak_ptr<BackingStore> backing_store,
               v8::Global<v8::Promise> promise,
               v8::Global<v8::Context> native_context)
        : isolate_for_async_waiters(isolate),
          task_runner(std::move(task_runner)),
          backing_store(std::move(backing_store)),
          promise(std::move(promise)),
          native_context(std::move(native_context)) {
      DCHECK(this->promise.IsWeak());
      DCHECK(this->native_context.IsWeak());
    }

    ~AsyncState() {
      // Assert that the timeout task was cancelled.
      DCHECK_EQ(CancelableTaskManager::kInvalidTaskId, timeout_task_id);
    }

    Isolate* const isolate_for_async_waiters;
    std::shared_ptr<TaskRunner> const task_runner;

    // The backing store on which we are waiting might die in an async wait.
    // We keep a weak_ptr to verify during a wake operation that the original
    // backing store is still mapped to that address.
    std::weak_ptr<BackingStore> const backing_store;

    // Weak Global handle. Must not be synchronously resolved by a non-owner
    // Isolate.
    v8::Global<v8::Promise> const promise;

    // Weak Global handle.
    v8::Global<v8::Context> const native_context;

    // If timeout_time_ is base::TimeTicks(), this async waiter doesn't have a
    // timeout or has already been notified. Values other than base::TimeTicks()
    // are used for async waiters with an active timeout.
    base::TimeTicks timeout_time;

    // The task ID of the timeout task.
    CancelableTaskManager::Id timeout_task_id =
        CancelableTaskManager::kInvalidTaskId;

    // True if the node is ready to be deleted (has to happen on the main
    // thread).
    bool waiting_for_main_thread_cleanup = false;
  };

  base::ConditionVariable cond_;
  // prev_ and next_ are protected by `GetWaitList()::mutex()`.
  FutexWaitListNode* prev_ = nullptr;
  FutexWaitListNode* next_ = nullptr;

  // The memory location the FutexWaitListNode is waiting on. Equals
  // backing_store_->buffer_start() + wait_addr at FutexWaitListNode creation
  // time. This address is used find the node in the per-location list, or to
  // remove it.
  // Note that during an async wait the BackingStore might get deleted while
  // this node is alive.
  void* wait_location_ = nullptr;

  // waiting_ is std::atomic<bool> to allow safe relaxed reads outside mutex
  // locks.
  std::atomic<bool> waiting_{false};
  bool interrupted_ = false;
  // in_sync_wait_ tracks whether the isolate thread is executing inside a
  // WaitSync scope. Modified exclusively by the isolate thread itself.
  bool in_sync_wait_ = false;

  // State used for an async wait; nullptr on sync waits.
  const std::unique_ptr<AsyncState> async_state_;
};

#if V8_ENABLE_WEBASSEMBLY
class FutexManagedObjectWaitList {
 public:
  static constexpr internal::ExternalPointerTag kManagedTag =
      internal::kWasmFutexManagedObjectWaitListTag;

  FutexManagedObjectWaitList() = default;
  FutexManagedObjectWaitList(const FutexWaitList&) = delete;
  FutexManagedObjectWaitList& operator=(const FutexWaitList&) = delete;

  void AddNode(FutexWaitListNode* node) {
    if (head_ == nullptr) {
      DCHECK_EQ(tail_, nullptr);
      head_ = tail_ = node;
    } else {
      DCHECK_NOT_NULL(tail_);
      tail_->next_ = node;
      node->prev_ = tail_;
      node->next_ = nullptr;
      tail_ = node;
    }
  }

  void RemoveNode(FutexWaitListNode* node) {
    DCHECK(NodeIsOnList(node, head_));
    if (node->prev_) {
      node->prev_->next_ = node->next_;
    } else {
      DCHECK_EQ(node, head_);
      head_ = node->next_;
    }
    if (node->next_) {
      node->next_->prev_ = node->prev_;
    } else {
      DCHECK_EQ(node, tail_);
      tail_ = node->prev_;
    }
    node->prev_ = node->next_ = nullptr;
  }

 private:
  friend class FutexEmulation;

  bool NodeIsOnList(FutexWaitListNode* node, FutexWaitListNode* head) {
    for (FutexWaitListNode* n = head; n; n = n->next_) {
      if (n == node) return true;
    }
    return false;
  }

  FutexWaitListNode* head_ = nullptr;
  FutexWaitListNode* tail_ = nullptr;
};
#endif  // V8_ENABLE_WEBASSEMBLY

class FutexEmulation : public AllStatic {
 public:
  enum WaitMode { kSync = 0, kAsync };
  enum class CallType { kIsNotWasm = 0, kIsWasm };

  // Pass to Wake() to wake all waiters.
  static const uint32_t kWakeAll = UINT32_MAX;

  // Check that array_buffer[addr] == value, and return "not-equal" if not. If
  // they are equal, block execution on |isolate|'s thread until woken via
  // |Wake|, or when the time given in |rel_timeout_ms| elapses. Note that
  // |rel_timeout_ms| can be Infinity.
  // If woken, return "ok", otherwise return "timed-out". The initial check and
  // the decision to wait happen atomically.
  static Tagged<Object> WaitJs32(Isolate* isolate, WaitMode mode,
                                 DirectHandle<JSArrayBuffer> array_buffer,
                                 size_t addr, int32_t value,
                                 double rel_timeout_ms);

  // An version of WaitJs32 for int64_t values.
  static Tagged<Object> WaitJs64(Isolate* isolate, WaitMode mode,
                                 DirectHandle<JSArrayBuffer> array_buffer,
                                 size_t addr, int64_t value,
                                 double rel_timeout_ms);

  // Same as WaitJs above except it returns 0 (ok), 1 (not equal) and 2 (timed
  // out) as expected by Wasm.
  V8_EXPORT_PRIVATE static Tagged<Object> WaitWasm32(
      Isolate* isolate, BackingStore* backing_store, size_t addr, int32_t value,
      int64_t rel_timeout_ns);

  // Same as Wait32 above except it checks for an int64_t value in the
  // array_buffer.
  V8_EXPORT_PRIVATE static Tagged<Object> WaitWasm64(
      Isolate* isolate, BackingStore* backing_store, size_t addr, int64_t value,
      int64_t rel_timeout_ns);

#if V8_ENABLE_WEBASSEMBLY
  template <typename T>
    requires(std::is_same_v<T, int32_t> || std::is_same_v<T, int64_t> ||
             std::is_same_v<T, Tagged<Object>>)
  V8_EXPORT_PRIVATE static Tagged<Object> WaitWasmManagedObject(
      Isolate* isolate, Tagged<HeapObject> object, int32_t offset,
      Tagged<Managed<FutexManagedObjectWaitList>> waitqueue, T expected_value,
      int64_t rel_timeout_ns);
#endif

  // Wake |num_waiters_to_wake| threads that are waiting on the given |addr|.
  // |num_waiters_to_wake| can be kWakeAll, in which case all waiters are
  // woken. The rest of the waiters will continue to wait. The return value is
  // the number of woken waiters.
  // Variant 1: Compute the wait address from the |array_buffer| and |addr|.
  V8_EXPORT_PRIVATE static int Wake(Tagged<JSArrayBuffer> array_buffer,
                                    size_t addr, uint32_t num_waiters_to_wake);
  // Variant 2: Pass raw |addr| (used for WebAssembly atomic.notify).
  static int Wake(void* addr, uint32_t num_waiters_to_wake);
#if V8_ENABLE_WEBASSEMBLY
  // Variant 3: Pass a waitqueue (used for WebAssembly waitqueue.notify).
  static int Wake(Address raw_waitqueue, uint32_t num_waiters_to_wake);
#endif

  // Called before |isolate| dies. Removes async waiters owned by |isolate|.
  static void IsolateDeinit(Isolate* isolate);

  // Return the number of threads or async waiters waiting on |addr|. Should
  // only be used for testing.
  static int NumWaitersForTesting(Tagged<JSArrayBuffer> array_buffer,
                                  size_t addr);

  // Return the number of async waiters which were waiting for |addr| and are
  // now waiting for the Promises to be resolved. Should only be used for
  // testing.
  static int NumUnresolvedAsyncPromisesForTesting(
      Tagged<JSArrayBuffer> array_buffer, size_t addr);

 private:
  friend class FutexWaitListNode;
  friend class ResolveAsyncWaiterPromisesTask;
  friend class AsyncWaiterTimeoutTask;

  template <typename T>
  static Tagged<Object> Wait(Isolate* isolate, WaitMode mode,
                             DirectHandle<JSArrayBuffer> array_buffer,
                             size_t addr, T value, double rel_timeout_ms,
                             CallType call_type);

  template <typename T>
  static Tagged<Object> WaitSync(Isolate* isolate, void* wait_location, T value,
                                 bool use_timeout, int64_t rel_timeout_ns,
                                 CallType call_type);

  template <typename T>
  static Tagged<Object> WaitAsync(Isolate* isolate,
                                  DirectHandle<JSArrayBuffer> array_buffer,
                                  size_t addr, T value, bool use_timeout,
                                  int64_t rel_timeout_ns, CallType call_type);

  template <typename WaitList, typename T>
  static DirectHandle<Object> WaitSyncImpl(
      Isolate* isolate, WaitList* wait_list, FutexWaitListNode* node,
      NoGarbageCollectionMutexGuard& lock_guard, bool use_timeout,
      base::TimeTicks timeout_time, T value, T loaded_value,
      std::optional<void*> wait_location);

  // Resolve the Promises of the async waiters which belong to |isolate|.
  static void ResolveAsyncWaiterPromises(Isolate* isolate);

  static void ResolveAsyncWaiterPromise(FutexWaitListNode* node);

  static void HandleAsyncWaiterTimeout(FutexWaitListNode* node);

  static void NotifyAsyncWaiter(FutexWaitListNode* node);

  // Remove the node's Promise from the NativeContext's Promise set.
  static void CleanupAsyncWaiterPromise(FutexWaitListNode* node);
};
}  // namespace internal
}  // namespace v8

#endif  // V8_EXECUTION_FUTEX_EMULATION_H_