/* This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

/*
 * JS Atomics pseudo-module.
 *
 * See chapter 24.4 "The Atomics Object" and chapter 27 "Memory Model" in
 * ECMAScript 2021 for the full specification.
 */

#include "builtin/AtomicsObject.h"

#include "mozilla/Atomics.h"
#include "mozilla/DebugOnly.h"
#include "mozilla/FloatingPoint.h"
#include "mozilla/Maybe.h"
#include "mozilla/ScopeExit.h"

#include "builtin/Number.h"
#include "builtin/Promise.h"
#include "jit/AtomicOperations.h"
#include "jit/InlinableNatives.h"
#include "js/Class.h"
#include "js/friend/ErrorMessages.h"  // js::GetErrorMessage, JSMSG_*
#include "js/PropertySpec.h"
#include "js/Result.h"
#include "js/WaitCallbacks.h"
#include "vm/GlobalObject.h"
#include "vm/HelperThreads.h"                 // AutoLockHelperThreadState
#include "vm/OffThreadPromiseRuntimeState.h"  // OffthreadPromiseTask
#include "vm/TypedArrayObject.h"

#include "vm/Compartment-inl.h"
#include "vm/JSObject-inl.h"
#include "vm/Realm-inl.h"

using namespace js;

static bool ReportBadArrayType(JSContext* cx) {
  JS_ReportErrorNumberASCII(cx, GetErrorMessage, nullptr,
                            JSMSG_ATOMICS_BAD_ARRAY);
  return false;
}

static bool ReportDetachedArrayBuffer(JSContext* cx) {
  JS_ReportErrorNumberASCII(cx, GetErrorMessage, nullptr,
                            JSMSG_TYPED_ARRAY_DETACHED);
  return false;
}

static bool ReportImmutableBuffer(JSContext* cx) {
  JS_ReportErrorNumberASCII(cx, GetErrorMessage, nullptr,
                            JSMSG_ARRAYBUFFER_IMMUTABLE);
  return false;
}

static bool ReportResizedArrayBuffer(JSContext* cx) {
  JS_ReportErrorNumberASCII(cx, GetErrorMessage, nullptr,
                            JSMSG_TYPED_ARRAY_RESIZED_BOUNDS);
  return false;
}

static bool ReportOutOfRange(JSContext* cx) {
  // Use JSMSG_BAD_INDEX here, it is what ToIndex uses for some cases that it
  // reports directly.
  JS_ReportErrorNumberASCII(cx, GetErrorMessage, nullptr, JSMSG_BAD_INDEX);
  return false;
}

enum class AccessMode { Read, Write };

// ES2026 draft rev affcec07523a45d40fb668689c07657412e772ac
// Plus: https://tc39.es/proposal-immutable-arraybuffer/
// 25.4.3.1 ValidateIntegerTypedArray ( typedArray, waitable )
static bool ValidateIntegerTypedArray(
    JSContext* cx, HandleValue typedArray, bool waitable, AccessMode accessMode,
    MutableHandle<TypedArrayObject*> unwrappedTypedArray) {
  // Steps 1-2.
  auto* unwrapped = UnwrapAndTypeCheckValue<TypedArrayObject>(
      cx, typedArray, [cx]() { ReportBadArrayType(cx); });
  if (!unwrapped) {
    return false;
  }

  if (unwrapped->hasDetachedBuffer()) {
    return ReportDetachedArrayBuffer(cx);
  }

  if (accessMode == AccessMode::Write &&
      unwrapped->is<ImmutableTypedArrayObject>()) {
    return ReportImmutableBuffer(cx);
  }

  // Steps 3-4.
  if (waitable) {
    switch (unwrapped->type()) {
      case Scalar::Int32:
      case Scalar::BigInt64:
        break;
      default:
        return ReportBadArrayType(cx);
    }
  } else {
    switch (unwrapped->type()) {
      case Scalar::Int8:
      case Scalar::Uint8:
      case Scalar::Int16:
      case Scalar::Uint16:
      case Scalar::Int32:
      case Scalar::Uint32:
      case Scalar::BigInt64:
      case Scalar::BigUint64:
        break;
      default:
        return ReportBadArrayType(cx);
    }
  }

  // Step 5 (modified to return the TypedArray).
  unwrappedTypedArray.set(unwrapped);
  return true;
}

// ES2021 draft rev bd868f20b8c574ad6689fba014b62a1dba819e56
// 24.4.1.2 ValidateAtomicAccess ( typedArray, requestIndex )
static bool ValidateAtomicAccess(JSContext* cx,
                                 Handle<TypedArrayObject*> typedArray,
                                 HandleValue requestIndex, size_t* index) {
  MOZ_ASSERT(!typedArray->hasDetachedBuffer());

  // Steps 1-2.
  mozilla::Maybe<size_t> length = typedArray->length();
  if (!length) {
    // ValidateIntegerTypedArray doesn't check for out-of-bounds in our
    // implementation, so we have to handle this case here.
    return ReportResizedArrayBuffer(cx);
  }

  // Steps 3-4.
  uint64_t accessIndex;
  if (!ToIndex(cx, requestIndex, &accessIndex)) {
    return false;
  }

  // Step 5.
  if (accessIndex >= *length) {
    return ReportOutOfRange(cx);
  }

  // Steps 6-9.
  *index = size_t(accessIndex);
  return true;
}

template <typename T>
struct ArrayOps {
  using Type = T;

  static JS::Result<T> convertValue(JSContext* cx, HandleValue v) {
    int32_t n;
    if (!ToInt32(cx, v, &n)) {
      return cx->alreadyReportedError();
    }
    return static_cast<T>(n);
  }

  static JS::Result<T> convertValue(JSContext* cx, HandleValue v,
                                    MutableHandleValue result) {
    double d;
    if (!ToInteger(cx, v, &d)) {
      return cx->alreadyReportedError();
    }
    result.setNumber(d);
    return static_cast<T>(JS::ToInt32(d));
  }

  static JS::Result<> storeResult(JSContext* cx, T v,
                                  MutableHandleValue result) {
    result.setInt32(v);
    return Ok();
  }
};

template <>
JS::Result<> ArrayOps<uint32_t>::storeResult(JSContext* cx, uint32_t v,
                                             MutableHandleValue result) {
  // Always double typed so that the JITs can assume the types are stable.
  result.setDouble(v);
  return Ok();
}

template <>
struct ArrayOps<int64_t> {
  using Type = int64_t;

  static JS::Result<int64_t> convertValue(JSContext* cx, HandleValue v) {
    BigInt* bi = ToBigInt(cx, v);
    if (!bi) {
      return cx->alreadyReportedError();
    }
    return BigInt::toInt64(bi);
  }

  static JS::Result<int64_t> convertValue(JSContext* cx, HandleValue v,
                                          MutableHandleValue result) {
    BigInt* bi = ToBigInt(cx, v);
    if (!bi) {
      return cx->alreadyReportedError();
    }
    result.setBigInt(bi);
    return BigInt::toInt64(bi);
  }

  static JS::Result<> storeResult(JSContext* cx, int64_t v,
                                  MutableHandleValue result) {
    BigInt* bi = BigInt::createFromInt64(cx, v);
    if (!bi) {
      return cx->alreadyReportedError();
    }
    result.setBigInt(bi);
    return Ok();
  }
};

template <>
struct ArrayOps<uint64_t> {
  using Type = uint64_t;

  static JS::Result<uint64_t> convertValue(JSContext* cx, HandleValue v) {
    BigInt* bi = ToBigInt(cx, v);
    if (!bi) {
      return cx->alreadyReportedError();
    }
    return BigInt::toUint64(bi);
  }

  static JS::Result<uint64_t> convertValue(JSContext* cx, HandleValue v,
                                           MutableHandleValue result) {
    BigInt* bi = ToBigInt(cx, v);
    if (!bi) {
      return cx->alreadyReportedError();
    }
    result.setBigInt(bi);
    return BigInt::toUint64(bi);
  }

  static JS::Result<> storeResult(JSContext* cx, uint64_t v,
                                  MutableHandleValue result) {
    BigInt* bi = BigInt::createFromUint64(cx, v);
    if (!bi) {
      return cx->alreadyReportedError();
    }
    result.setBigInt(bi);
    return Ok();
  }
};

// ES2021 draft rev bd868f20b8c574ad6689fba014b62a1dba819e56
// 24.4.1.11 AtomicReadModifyWrite ( typedArray, index, value, op ), steps 1-2.
// 24.4.1.12 AtomicLoad ( typedArray, index ), steps 1-2.
// 24.4.4 Atomics.compareExchange ( typedArray, index, ... ), steps 1-2.
// 24.4.9 Atomics.store ( typedArray, index, value ), steps 1-2.
template <typename Op>
static bool AtomicAccess(JSContext* cx, HandleValue obj, HandleValue index,
                         AccessMode accessMode, Op op) {
  // Step 1.
  Rooted<TypedArrayObject*> unwrappedTypedArray(cx);
  if (!ValidateIntegerTypedArray(cx, obj, false, accessMode,
                                 &unwrappedTypedArray)) {
    return false;
  }

  // Step 2.
  size_t intIndex;
  if (!ValidateAtomicAccess(cx, unwrappedTypedArray, index, &intIndex)) {
    return false;
  }

  switch (unwrappedTypedArray->type()) {
    case Scalar::Int8:
      return op(ArrayOps<int8_t>{}, unwrappedTypedArray, intIndex);
    case Scalar::Uint8:
      return op(ArrayOps<uint8_t>{}, unwrappedTypedArray, intIndex);
    case Scalar::Int16:
      return op(ArrayOps<int16_t>{}, unwrappedTypedArray, intIndex);
    case Scalar::Uint16:
      return op(ArrayOps<uint16_t>{}, unwrappedTypedArray, intIndex);
    case Scalar::Int32:
      return op(ArrayOps<int32_t>{}, unwrappedTypedArray, intIndex);
    case Scalar::Uint32:
      return op(ArrayOps<uint32_t>{}, unwrappedTypedArray, intIndex);
    case Scalar::BigInt64:
      return op(ArrayOps<int64_t>{}, unwrappedTypedArray, intIndex);
    case Scalar::BigUint64:
      return op(ArrayOps<uint64_t>{}, unwrappedTypedArray, intIndex);
    case Scalar::Float16:
    case Scalar::Float32:
    case Scalar::Float64:
    case Scalar::Uint8Clamped:
    case Scalar::MaxTypedArrayViewType:
    case Scalar::Int64:
    case Scalar::Simd128:
      break;
  }
  MOZ_CRASH("Unsupported TypedArray type");
}

template <typename T>
static SharedMem<T*> TypedArrayData(JSContext* cx, TypedArrayObject* typedArray,
                                    size_t index) {
  // RevalidateAtomicAccess, steps 1-3.
  mozilla::Maybe<size_t> length = typedArray->length();

  // RevalidateAtomicAccess, step 4.
  if (!length) {
    ReportDetachedArrayBuffer(cx);
    return {};
  }

  // RevalidateAtomicAccess, step 5.
  if (index >= *length) {
    ReportOutOfRange(cx);
    return {};
  }

  SharedMem<void*> typedArrayData = typedArray->dataPointerEither();
  return typedArrayData.cast<T*>() + index;
}

// ES2021 draft rev bd868f20b8c574ad6689fba014b62a1dba819e56
// 24.4.4 Atomics.compareExchange ( typedArray, index, expectedValue,
//                                  replacementValue )
static bool atomics_compareExchange(JSContext* cx, unsigned argc, Value* vp) {
  CallArgs args = CallArgsFromVp(argc, vp);
  HandleValue typedArray = args.get(0);
  HandleValue index = args.get(1);

  return AtomicAccess(
      cx, typedArray, index, AccessMode::Write,
      [cx, &args](auto ops, Handle<TypedArrayObject*> unwrappedTypedArray,
                  size_t index) {
        using T = typename decltype(ops)::Type;

        HandleValue expectedValue = args.get(2);
        HandleValue replacementValue = args.get(3);

        T oldval;
        JS_TRY_VAR_OR_RETURN_FALSE(cx, oldval,
                                   ops.convertValue(cx, expectedValue));

        T newval;
        JS_TRY_VAR_OR_RETURN_FALSE(cx, newval,
                                   ops.convertValue(cx, replacementValue));

        SharedMem<T*> addr = TypedArrayData<T>(cx, unwrappedTypedArray, index);
        if (!addr) {
          return false;
        }

        oldval =
            jit::AtomicOperations::compareExchangeSeqCst(addr, oldval, newval);

        JS_TRY_OR_RETURN_FALSE(cx, ops.storeResult(cx, oldval, args.rval()));
        return true;
      });
}

// ES2021 draft rev bd868f20b8c574ad6689fba014b62a1dba819e56
// 24.4.7 Atomics.load ( typedArray, index )
static bool atomics_load(JSContext* cx, unsigned argc, Value* vp) {
  CallArgs args = CallArgsFromVp(argc, vp);
  HandleValue typedArray = args.get(0);
  HandleValue index = args.get(1);

  return AtomicAccess(
      cx, typedArray, index, AccessMode::Read,
      [cx, &args](auto ops, Handle<TypedArrayObject*> unwrappedTypedArray,
                  size_t index) {
        using T = typename decltype(ops)::Type;

        SharedMem<T*> addr = TypedArrayData<T>(cx, unwrappedTypedArray, index);
        if (!addr) {
          return false;
        }

        T v = jit::AtomicOperations::loadSeqCst(addr);

        JS_TRY_OR_RETURN_FALSE(cx, ops.storeResult(cx, v, args.rval()));
        return true;
      });
}

// ES2021 draft rev bd868f20b8c574ad6689fba014b62a1dba819e56
// 24.4.9 Atomics.store ( typedArray, index, value )
static bool atomics_store(JSContext* cx, unsigned argc, Value* vp) {
  CallArgs args = CallArgsFromVp(argc, vp);
  HandleValue typedArray = args.get(0);
  HandleValue index = args.get(1);

  return AtomicAccess(
      cx, typedArray, index, AccessMode::Write,
      [cx, &args](auto ops, Handle<TypedArrayObject*> unwrappedTypedArray,
                  size_t index) {
        using T = typename decltype(ops)::Type;

        HandleValue value = args.get(2);

        T v;
        JS_TRY_VAR_OR_RETURN_FALSE(cx, v,
                                   ops.convertValue(cx, value, args.rval()));

        SharedMem<T*> addr = TypedArrayData<T>(cx, unwrappedTypedArray, index);
        if (!addr) {
          return false;
        }

        jit::AtomicOperations::storeSeqCst(addr, v);
        return true;
      });
}

// ES2021 draft rev bd868f20b8c574ad6689fba014b62a1dba819e56
// 24.4.1.11 AtomicReadModifyWrite ( typedArray, index, value, op )
template <typename AtomicOp>
static bool AtomicReadModifyWrite(JSContext* cx, const CallArgs& args,
                                  AtomicOp op) {
  HandleValue typedArray = args.get(0);
  HandleValue index = args.get(1);

  return AtomicAccess(
      cx, typedArray, index, AccessMode::Write,
      [cx, &args, op](auto ops, Handle<TypedArrayObject*> unwrappedTypedArray,
                      size_t index) {
        using T = typename decltype(ops)::Type;

        HandleValue value = args.get(2);

        T v;
        JS_TRY_VAR_OR_RETURN_FALSE(cx, v, ops.convertValue(cx, value));

        SharedMem<T*> addr = TypedArrayData<T>(cx, unwrappedTypedArray, index);
        if (!addr) {
          return false;
        }

        v = op(addr, v);

        JS_TRY_OR_RETURN_FALSE(cx, ops.storeResult(cx, v, args.rval()));
        return true;
      });
}

// ES2021 draft rev bd868f20b8c574ad6689fba014b62a1dba819e56
// 24.4.5 Atomics.exchange ( typedArray, index, value )
static bool atomics_exchange(JSContext* cx, unsigned argc, Value* vp) {
  CallArgs args = CallArgsFromVp(argc, vp);

  return AtomicReadModifyWrite(cx, args, [](auto addr, auto val) {
    return jit::AtomicOperations::exchangeSeqCst(addr, val);
  });
}

// ES2021 draft rev bd868f20b8c574ad6689fba014b62a1dba819e56
// 24.4.2 Atomics.add ( typedArray, index, value )
static bool atomics_add(JSContext* cx, unsigned argc, Value* vp) {
  CallArgs args = CallArgsFromVp(argc, vp);

  return AtomicReadModifyWrite(cx, args, [](auto addr, auto val) {
    return jit::AtomicOperations::fetchAddSeqCst(addr, val);
  });
}

// ES2021 draft rev bd868f20b8c574ad6689fba014b62a1dba819e56
// 24.4.10 Atomics.sub ( typedArray, index, value )
static bool atomics_sub(JSContext* cx, unsigned argc, Value* vp) {
  CallArgs args = CallArgsFromVp(argc, vp);

  return AtomicReadModifyWrite(cx, args, [](auto addr, auto val) {
    return jit::AtomicOperations::fetchSubSeqCst(addr, val);
  });
}

// ES2021 draft rev bd868f20b8c574ad6689fba014b62a1dba819e56
// 24.4.3 Atomics.and ( typedArray, index, value )
static bool atomics_and(JSContext* cx, unsigned argc, Value* vp) {
  CallArgs args = CallArgsFromVp(argc, vp);

  return AtomicReadModifyWrite(cx, args, [](auto addr, auto val) {
    return jit::AtomicOperations::fetchAndSeqCst(addr, val);
  });
}

// ES2021 draft rev bd868f20b8c574ad6689fba014b62a1dba819e56
// 24.4.8 Atomics.or ( typedArray, index, value )
static bool atomics_or(JSContext* cx, unsigned argc, Value* vp) {
  CallArgs args = CallArgsFromVp(argc, vp);

  return AtomicReadModifyWrite(cx, args, [](auto addr, auto val) {
    return jit::AtomicOperations::fetchOrSeqCst(addr, val);
  });
}

// ES2021 draft rev bd868f20b8c574ad6689fba014b62a1dba819e56
// 24.4.13 Atomics.xor ( typedArray, index, value )
static bool atomics_xor(JSContext* cx, unsigned argc, Value* vp) {
  CallArgs args = CallArgsFromVp(argc, vp);

  return AtomicReadModifyWrite(cx, args, [](auto addr, auto val) {
    return jit::AtomicOperations::fetchXorSeqCst(addr, val);
  });
}

// ES2021 draft rev bd868f20b8c574ad6689fba014b62a1dba819e56
// 24.4.6 Atomics.isLockFree ( size )
static bool atomics_isLockFree(JSContext* cx, unsigned argc, Value* vp) {
  CallArgs args = CallArgsFromVp(argc, vp);
  HandleValue v = args.get(0);

  // Step 1.
  int32_t size;
  if (v.isInt32()) {
    size = v.toInt32();
  } else {
    double dsize;
    if (!ToInteger(cx, v, &dsize)) {
      return false;
    }

    // Step 7 (non-integer case only).
    if (!mozilla::NumberEqualsInt32(dsize, &size)) {
      args.rval().setBoolean(false);
      return true;
    }
  }

  // Steps 2-7.
  args.rval().setBoolean(jit::AtomicOperations::isLockfreeJS(size));
  return true;
}

namespace js {

/*
 * [SMDOC] Atomics.wait, Atomics.waitAsync, and Atomics.notify
 *
 * `wait`, `waitAsync`, and `notify` are provided as low-level primitives for
 * thread synchronization. The primary use case is to take code that looks like
 * this:
 *
 *     const ValueIndex = 0;
 *     const FlagIndex = 1;
 *
 *     THREAD A:
 *       // Write a value.
 *       Atomics.store(sharedBuffer, ValueIndex, value);
 *       // Update a flag to indicate that the value was written.
 *       Atomics.store(sharedBuffer, FlagIndex, 1);
 *
 *     THREAD B:
 *       // Busy-wait for the flag to be updated.
 *       while (Atomics.load(sharedBuffer, FlagIndex) == 0) {}
 *       // Load the value.
 *       let value = Atomics.load(sharedBuffer, ValueIndex);
 *
 * ...and replace the busy-wait:
 *
 *     THREAD A':
 *       // Write the value and update the flag.
 *       Atomics.store(sharedBuffer, ValueIndex, value);
 *       Atomics.store(sharedBuffer, FlagIndex, 1);
 *       // Notify that the flag has been written.
 *       Atomics.notify(sharedBuffer, FlagIndex);
 *
 *     THREAD B':
 *       // Wait until the flag is notified.
 *       // If it's already non-zero, no wait occurs.
 *       Atomics.wait(sharedBuffer, FlagIndex, 0);
 *       // Load the value.
 *       let value = Atomics.load(sharedBuffer, ValueIndex);
 *
 * `wait` puts the calling thread to sleep until it is notified (or an optional
 * timeout expires). This can't be used on the main thread.
 *
 * `waitAsync` instead creates a Promise which will be resolved when the
 * position is notified (or an optional timeout expires).
 *
 * When `wait` or `waitAsync` is called, a waiter is created and registered with
 * the SharedArrayBuffer. Waiter instances for a SharedArrayRawBuffer are
 * connected in a circular doubly-linked list, containing both sync and async
 * waiters. Sync waiters are stack allocated in the stack frame of the waiting
 * thread. Async waiters are heap-allocated. The `waiters` field of the
 * SharedArrayRawBuffer is a dedicated list head node for the list. Waiters are
 * awoken in a first-in-first-out order. The `next` field of the list head node
 * points to the highest priority waiter. The `prev` field points to the lowest
 * priority waiter. This list is traversed when `notify` is called to find the
 * waiters that should be woken up.
 *
 * Synchronous waits are implemented using a per-context condition variable. See
 * FutexThread::wait.
 *
 * Asynchronous waits are more complicated, particularly with respect to
 * timeouts. In addition to the AsyncFutexWaiter that is added to the list of
 * waiters, we also create:
 *
 *   1. A Promise object to return to the caller. The promise will be resolved
 *      when the waiter is notified or times out.
 *   2. A WaitAsyncNotifyTask (derived from OffThreadPromiseTask) wrapping that
 *      promise. `notify` can be called from any thread, but the promise must be
 *      resolved on the thread that owns it. To resolve the promise, we dispatch
 *      the task to enqueue a promise resolution task in the target's event
 *      loop. The notify task is stored in the AsyncFutexWaiter.
 *   3. If there is a non-zero timeout, a WaitAsyncTimeoutTask (derived from
 *      JS::Dispatchable) containing a pointer to the async waiter. We dispatch
 *      this task to the embedding's event loop, with a delay. When the timeout
 *      expires and the task runs, if the promise has not yet been resolved, we
 *      resolve it with "timed-out".
 *
 * `waitAsync` Lifetimes
 * ---------------------
 *           ┌─────┐
 *           │ SAB │
 *           └─────┘
 *        ┌────► ◄────┐ bi-directional linked list
 *        │           │
 *        ▼           ▼
 *      *waiter      *waiter
 *        ▲           ▲
 *        │           │
 *        └───► *  ◄──┘
 *              │
 *      ┌───────▼────────┐
 *      │AsyncFutexWaiter│ ◄───────────┐
 *      └────────────────┘             │
 *              │                      │
 *              │ borrow               │ borrow
 *              ▼                      ▼
 *      ┌────────────────────┐       ┌───────────────────┐
 *      │WaitAsyncTimeoutTask│       │WaitAsyncNotifyTask│ ◄─────┐
 *      └────────────────────┘       └───┬───────────────┘       │
 *              ▲                        │             ▲         │
 *              │                        │             │         │ (transferred)
 *              │ own                    ▼             │         │ own
 *     ┌────────────────────────────┐ ┌─────────────┐  │ ┌─────────────────────┐
 *     │DelayedJSDispatchableHandler│ │PromiseObject│  │ │JSDispatchableHandler│
 *     └────────────────────────────┘ └─────────────┘  │ └─────────────────────┘
 *              ▲                        ▲             │
 *     ┌────────┼────────────────────────┼──────┐      │
 *     │ ┌──────┴───────┐           ┌────┴────┐ │      │ own (initialized)
 *     │ │TimeoutManager│           │JSContext┼─┼──────┘
 *     │ └──────────────┘           └─────────┘ │   Cancellable List
 *     │                                        │
 *     │     Runtime (MainThread or Worker)     │
 *     └────────────────────────────────────────┘
 *
 *
 * The data representing an async wait is divided between the JSContext in which
 * it was created and the SharedArrayBuffer being waited on. There are three
 * potential components:
 *
 * A) The AsyncFutexWaiter itself (shared by the SharedArrayRawBuffer,
 *    WaitAsyncNotifyTask, and WaitAsyncTimeoutTask if it exists). It
 *    will be cleaned up manually.
 * B) The corresponding WaitAsyncNotifyTask (owned by the JS::Context). It
 *    destroys itself on run.
 * C) The WaitAsyncTimeoutTask (owned by the embedding's job queue). It
 *    destroys itself on run.
 *
 * WaitAsyncNotifyTask and WaitAsyncTimeoutTask (if it exists) delete
 * themselves. When either task is run or destroyed, they also trigger the
 * destruction and unlinking of the AsyncFutexWaiter. There are
 * four scenarios:
 *
 * 1. A call to `Atomics.notify` notifies the waiter (atomics_notify_impl)
 *    from another thread.
 *    A) The async waiter is removed from the list.
 *    B) The notify task is removed from OffThreadPromiseRuntimeState's
 *       cancelable list and is dispatched to resolve the promise with "ok".
 *       The task then destroys itself.
 *    C) The WaitAsyncTimeoutTask is disabled. It will fire and do nothing.
 *       See AsyncFutexWaiter::maybeClearTimeout in atomics_notify_impl.
 *    D) The async waiter is destroyed.
 *
 * 2. A call to `Atomics.notify` notifies the waiter (atomics_notify_impl)
 *    from the same thread.
 *    A) The async waiter is removed from the list.
 *    B) The notify task is cancelled. The promise is extracted and resolved
 *        directly.
 *    C) The WaitAsyncTimeoutTask is disabled. It will fire and do nothing.
 *       See AsyncFutexWaiter::maybeClearTimeout in atomics_notify_impl.
 *    D) The async waiter is destroyed.
 *
 * 3. The timeout expires without notification (WaitAsyncTimeoutTask::run)
 *    A) The async waiter is removed from the list.
 *    B) The notify task is dispatched to resolve the promise with "timed-out"
 *       and destroys itself..
 *    C) The timeout task is running and will be destroyed when it's done.
 *    D) The async waiter is destroyed.
 *
 * 4. The context is destroyed (OffThreadPromiseRuntimeState::shutdown):
 *    A) The async waiter is removed and destroyed by
 *       WaitAsyncNotifyTask::prepareForCancel.
 *    B) The notify task is cancelled and destroyed by
 *       OffThreadPromiseRuntimeState::shutdown.
 *    C) The WaitAsyncTimeoutTask is disabled.
 *       See AsyncFutexWaiter::maybeClearTimeout in prepareForCancel.
 *
 * 5. The SharedArrayBuffer is collected by the GC (~FutexWaiterListHead)
 *    A) Async waiters without timeouts can no longer resolve. They are removed.
 *    B) If no timeout task exists, the notify task is dispatched and
 *       destroys itself, without resolving the promise.
 *    C) If there is an enqueued timeout, the waiter can still be resolved.
 *       In this case it will not be destroyed until it times out.
 *
 * The UniquePtr can be thought of as a "runnable handle" that gives exclusive
 * access to executing a runnable by a given owner. The runnable will still
 * delete itself (via js_delete, see OffThreadPromiseRuntimeState.cpp
 * implementation of OffThreadPromiseTask::run). If somehow the UniquePtr is not
 * passed to embedding code that will run the code, the task is released from
 * the pointer. We then use the list of raw pointers in
 * OffThreadPromiseRuntimeState's cancellable and dead lists are used to
 * identify which were never dispatched, and which failed to dispatch, and clear
 * them when the engine has an opportunity to do so (i.e. shutdown).
 */

class WaitAsyncNotifyTask;
class WaitAsyncTimeoutTask;

class AutoLockFutexAPI {
  // We have to wrap this in a Maybe because of the way loading
  // mozilla::Atomic pointers works.
  mozilla::Maybe<js::UniqueLock<js::Mutex>> unique_;

 public:
  AutoLockFutexAPI() {
    js::Mutex* lock = FutexThread::lock_;
    unique_.emplace(*lock);
  }

  ~AutoLockFutexAPI() { unique_.reset(); }

  js::UniqueLock<js::Mutex>& unique() { return *unique_; }
};

// Represents one waiter. This is the abstract base class for SyncFutexWaiter
// and AsyncFutexWaiter.
class FutexWaiter : public FutexWaiterListNode {
 protected:
  FutexWaiter(JSContext* cx, size_t offset, FutexWaiterKind kind)
      : FutexWaiterListNode(kind), offset_(offset), cx_(cx) {}

  size_t offset_;  // Element index within the SharedArrayBuffer
  JSContext* cx_;  // The thread that called `wait` or `waitAsync`.

 public:
  bool isSync() const { return kind_ == FutexWaiterKind::Sync; }
  SyncFutexWaiter* asSync() {
    MOZ_ASSERT(isSync());
    return reinterpret_cast<SyncFutexWaiter*>(this);
  }

  bool isAsync() const { return kind_ == FutexWaiterKind::Async; }
  AsyncFutexWaiter* asAsync() {
    MOZ_ASSERT(isAsync());
    return reinterpret_cast<AsyncFutexWaiter*>(this);
  }
  size_t offset() const { return offset_; }
  JSContext* cx() { return cx_; }
};

// Represents a worker blocked while calling |Atomics.wait|.
// Instances of js::SyncFutexWaiter are stack-allocated and linked
// onto the waiter list across a call to FutexThread::wait().
// When this waiter is notified, the worker will resume execution.
class MOZ_STACK_CLASS SyncFutexWaiter : public FutexWaiter {
 public:
  SyncFutexWaiter(JSContext* cx, size_t offset)
      : FutexWaiter(cx, offset, FutexWaiterKind::Sync) {}
};

// Represents a waiter asynchronously waiting after calling |Atomics.waitAsync|.
// Instances of js::AsyncFutexWaiter are heap-allocated.
// When this waiter is notified, the promise it holds will be resolved.
class AsyncFutexWaiter : public FutexWaiter {
 public:
  AsyncFutexWaiter(JSContext* cx, size_t offset)
      : FutexWaiter(cx, offset, FutexWaiterKind::Async) {}

  // NOTE: AsyncFutexWaiter is deleted only by UniquePtr<AsyncFutexWaiter>,
  //       and thus the destructor is not virtual.
  ~AsyncFutexWaiter();

  WaitAsyncNotifyTask* notifyTask() { return notifyTask_; }

  void setNotifyTask(WaitAsyncNotifyTask* task) {
    MOZ_ASSERT(!notifyTask_);
    notifyTask_ = task;
  }

  void resetNotifyTask() { notifyTask_ = nullptr; }

  void setTimeoutTask(WaitAsyncTimeoutTask* task) {
    MOZ_ASSERT(!timeoutTask_);
    timeoutTask_ = task;
  }

  void resetTimeoutTask() { timeoutTask_ = nullptr; }

  bool hasTimeout() const { return !!timeoutTask_; }
  WaitAsyncTimeoutTask* timeoutTask() const { return timeoutTask_; }

  void maybeClearTimeout(AutoLockFutexAPI& lock);

 private:
  // Both of these pointers are borrowed pointers. The notifyTask is owned by
  // the runtime's cancellable list, while the timeout task (if it exists) is
  // owned by the embedding's timeout manager.
  //
  // Set by setNotifyTask immediately after construction, and reset by
  // resetNotifyTask when the notify task is getting deleted.
  // WaitAsyncNotifyTask is responsible for calling resetNotifyTask
  WaitAsyncNotifyTask* notifyTask_ = nullptr;

  // Set by setTimeoutTask immediately after construction, and reset by
  // resetTimeoutTask when the timeout task is getting deleted.
  // WaitAsyncTimeoutTask is responsible for calling resetTimeoutTask
  WaitAsyncTimeoutTask* timeoutTask_ = nullptr;
};

// When an async waiter from a different context is notified, this
// task is queued to resolve the promise on the thread to which it
// belongs.
//
// WaitAsyncNotifyTask (derived from OffThreadPromiseTask) is wrapping that
// promise. `Atomics.notify` can be called from any thread, but the promise must
// be resolved on the thread that owns it. To resolve the promise, we dispatch
// the task to enqueue a promise resolution task in the target's event
// loop.
//
// See [SMDOC] Atomics.wait for more details.
class WaitAsyncNotifyTask : public OffThreadPromiseTask {
 public:
  enum class Result { Ok, TimedOut, Dead };

 private:
  Result result_ = Result::Ok;

  // A back-edge to the waiter so that it can be cleaned up when the
  // Notify Task is dispatched and destroyed.
  //
  // Set by setWaiter immediately after construction, and reset by resetWaiter
  // when the waiter is getting deleted.  AsyncFutexWaiter is responsible for
  // calling resetWaiter.
  AsyncFutexWaiter* waiter_ = nullptr;

 public:
  WaitAsyncNotifyTask(JSContext* cx, Handle<PromiseObject*> promise)
      : OffThreadPromiseTask(cx, promise) {}

  ~WaitAsyncNotifyTask() override {
    if (waiter_) {
      waiter_->resetNotifyTask();
    }
  }

  void setWaiter(AsyncFutexWaiter* waiter) {
    MOZ_ASSERT(!waiter_);
    waiter_ = waiter;
  }
  void resetWaiter() { waiter_ = nullptr; }

  void setResult(Result result, AutoLockFutexAPI& lock) { result_ = result; }

  bool resolve(JSContext* cx, Handle<PromiseObject*> promise) override {
    RootedValue resultMsg(cx);
    switch (result_) {
      case Result::Ok:
        resultMsg = StringValue(cx->names().ok);
        break;
      case Result::TimedOut:
        resultMsg = StringValue(cx->names().timed_out_);
        break;
      case Result::Dead:
        // The underlying SharedArrayBuffer is no longer reachable, and no
        // timeout is associated with this waiter. The promise will never
        // resolve. There's nothing to do here.
        return true;
    }
    return PromiseObject::resolve(cx, promise, resultMsg);
  }

  void prepareForCancel() override;
};

// WaitAsyncNotifyTask (derived from OffThreadPromiseTask) is wrapping that
// promise. `notify` can be called from any thread, but the promise must be
// resolved on the thread that owns it. To resolve the promise, we dispatch
// the task to enqueue a promise resolution task in the target's event
// loop.
//
// See [SMDOC] Atomics.wait for more details.
class WaitAsyncTimeoutTask : public JS::Dispatchable {
  // Set by the constructor, and reset by resetWaiter when the waiter is getting
  // deleted. AsyncFutexWaiter is responsible for calling resetWaiter.
  AsyncFutexWaiter* waiter_;

 public:
  explicit WaitAsyncTimeoutTask(AsyncFutexWaiter* waiter) : waiter_(waiter) {
    MOZ_ASSERT(waiter_);
  }
  ~WaitAsyncTimeoutTask() {
    if (waiter_) {
      waiter_->resetTimeoutTask();
    }
  }

  void resetWaiter() { waiter_ = nullptr; }

  void clear(AutoLockFutexAPI&) {
    if (waiter_) {
      waiter_->resetTimeoutTask();
    }
    waiter_ = nullptr;
  }
  bool cleared(AutoLockFutexAPI&) { return !waiter_; }

  void run(JSContext*, MaybeShuttingDown maybeshuttingdown) final;
  void transferToRuntime() final;
};

AsyncFutexWaiter::~AsyncFutexWaiter() {
  if (notifyTask_) {
    notifyTask_->resetWaiter();
  }
  if (timeoutTask_) {
    timeoutTask_->resetWaiter();
  }
}

}  // namespace js

// https://tc39.es/ecma262/#sec-addwaiter
static void AddWaiter(SharedArrayRawBuffer* sarb, FutexWaiter* node,
                      AutoLockFutexAPI&) {
  FutexWaiterListNode* listHead = sarb->waiters();

  // Step 3: Append waiterRecord to WL.[[Waiters]].
  node->setNext(listHead);
  node->setPrev(listHead->prev());
  listHead->prev()->setNext(node);
  listHead->setPrev(node);
}

// https://tc39.es/ecma262/#sec-removewaiter
static void RemoveWaiterImpl(FutexWaiterListNode* node, AutoLockFutexAPI&) {
  if (!node->prev()) {
    MOZ_ASSERT(!node->next());
    return;
  }

  node->prev()->setNext(node->next());
  node->next()->setPrev(node->prev());

  node->setNext(nullptr);
  node->setPrev(nullptr);
}

// Sync waiters are stack allocated and can simply be removed from the list.
static void RemoveSyncWaiter(SyncFutexWaiter* waiter, AutoLockFutexAPI& lock) {
  RemoveWaiterImpl(waiter, lock);
}

// Async waiters are heap allocated. After removing the waiter, the caller
// is responsible for freeing it. Return the waiter to help enforce this.
[[nodiscard]] AsyncFutexWaiter* RemoveAsyncWaiter(AsyncFutexWaiter* waiter,
                                                  AutoLockFutexAPI& lock) {
  RemoveWaiterImpl(waiter, lock);
  return waiter;
}

FutexWaiterListHead::~FutexWaiterListHead() {
  // Cleanup steps from 5. in SMDOC for Atomics.waitAsync
  // When a SharedArrayRawBuffer is no longer reachable, the contents of its
  // waiters list can no longer be notified. However, they can still resolve if
  // they have an associated timeout. When the list head goes away, we walk
  // through the remaining waiters and clean up the ones that don't have
  // timeouts. We leave the remaining waiters in a free-floating linked list;
  // they will remove themselves as the timeouts fire or the associated runtime
  // shuts down.
  AutoLockHelperThreadState helperLock;
  AutoLockFutexAPI lock;

  FutexWaiterListNode* iter = next();
  while (iter && iter != this) {
    // All remaining FutexWaiters must be async. A sync waiter can only exist if
    // a thread is waiting, and that thread must have a reference to the shared
    // array buffer it's waiting on, so that buffer can't be freed.

    FutexWaiterListNode* next = iter->next();
    AsyncFutexWaiter* removedWaiter =
        RemoveAsyncWaiter(iter->toWaiter()->asAsync(), lock);
    iter = next;

    if (removedWaiter->hasTimeout() &&
        !removedWaiter->timeoutTask()->cleared(lock)) {
      // If a timeout task exists,  allow it to clean up the notify task when it
      // runs. See the comment in WaitAsyncTimeoutTask::run() or the the SMDOC
      // in this file.
      continue;
    }
    // In the case that a timeout task does not exist, the two live raw
    // pointers at this point are WaitAsyncNotifyTask and the
    // AsyncFutexWaiter. We can clean them up here as there is no way to
    // notify them without the SAB or without waiting for the shutdown of the
    // JS::Context. In order to do this, we store the removed waiter in a
    // unique ptr, so that it is cleared after this function, and dispatch and
    // destroy the notify task.
    UniquePtr<AsyncFutexWaiter> ownedWaiter(removedWaiter);
    WaitAsyncNotifyTask* task = ownedWaiter->notifyTask();
    task->setResult(WaitAsyncNotifyTask::Result::Dead, lock);
    task->removeFromCancellableListAndDispatch(helperLock);
  }

  RemoveWaiterImpl(this, lock);
}

// Creates an object to use as the return value of Atomics.waitAsync.
static PlainObject* CreateAsyncResultObject(JSContext* cx, bool async,
                                            HandleValue promiseOrString) {
  Rooted<PlainObject*> resultObject(cx, NewPlainObject(cx));
  if (!resultObject) {
    return nullptr;
  }

  RootedValue isAsync(cx, BooleanValue(async));
  if (!NativeDefineDataProperty(cx, resultObject, cx->names().async, isAsync,
                                JSPROP_ENUMERATE)) {
    return nullptr;
  }

  MOZ_ASSERT_IF(!async, promiseOrString.isString());
  MOZ_ASSERT_IF(async, promiseOrString.isObject() &&
                           promiseOrString.toObject().is<PromiseObject>());
  if (!NativeDefineDataProperty(cx, resultObject, cx->names().value,
                                promiseOrString, JSPROP_ENUMERATE)) {
    return nullptr;
  }

  return resultObject;
}

void WaitAsyncNotifyTask::prepareForCancel() {
  AutoLockFutexAPI lock;
  UniquePtr<AsyncFutexWaiter> waiter(RemoveAsyncWaiter(waiter_, lock));
  waiter->maybeClearTimeout(lock);
}

void WaitAsyncTimeoutTask::run(JSContext* cx,
                               MaybeShuttingDown maybeShuttingDown) {
  AutoLockHelperThreadState helperLock;
  AutoLockFutexAPI lock;

  // If the waiter was notified while this task was enqueued, do nothing.
  if (cleared(lock)) {
    js_delete(this);
    return;
  }

  // Cleanup steps from 3. and 5. lifecycle in SMDOC for Atomics.waitAsync
  // Take ownership of the async waiter, so that it will be freed
  // when we return.
  UniquePtr<AsyncFutexWaiter> asyncWaiter(RemoveAsyncWaiter(waiter_, lock));
  asyncWaiter->resetTimeoutTask();

  // Dispatch a task to resolve the promise with value "timed-out".
  WaitAsyncNotifyTask* task = asyncWaiter->notifyTask();
  task->setResult(WaitAsyncNotifyTask::Result::TimedOut, lock);
  task->removeFromCancellableListAndDispatch(helperLock);
  js_delete(this);
}

void WaitAsyncTimeoutTask::transferToRuntime() {
  // Clear and delete. Clearing this task will result in the cancellable
  // notify task being cleaned up on shutdown, as it can no longer be triggered.
  // In as sense, the task "transfered" for cleanup is the notify task.
  {
    AutoLockFutexAPI lock;
    clear(lock);
  }
  // As we are not managing any state, the runtime is not tracking this task,
  // and we have nothing to run, we can delete.
  js_delete(this);
}

void AsyncFutexWaiter::maybeClearTimeout(AutoLockFutexAPI& lock) {
  if (timeoutTask_) {
    timeoutTask_->clear(lock);
    timeoutTask_ = nullptr;
  }
}

// DoWait Steps 17-31
// https://tc39.es/ecma262/#sec-dowait
template <typename T>
static FutexThread::WaitResult AtomicsWaitAsyncCriticalSection(
    JSContext* cx, SharedArrayRawBuffer* sarb, size_t byteOffset, T value,
    const mozilla::Maybe<mozilla::TimeDuration>& timeout,
    Handle<PromiseObject*> promise) {
  // Step 17: Enter critical section.
  // We need to initialize an OffThreadPromiseTask inside this critical section.
  // To avoid deadlock, we claim the helper thread lock first.
  AutoLockHelperThreadState helperThreadLock;

  UniquePtr<WaitAsyncTimeoutTask> timeoutTask;
  {
    AutoLockFutexAPI futexLock;

    // Steps 18-20:
    SharedMem<T*> addr =
        sarb->dataPointerShared().cast<T*>() + (byteOffset / sizeof(T));
    if (jit::AtomicOperations::loadSafeWhenRacy(addr) != value) {
      return FutexThread::WaitResult::NotEqual;
    }

    // Step 21
    bool hasTimeout = timeout.isSome();
    if (hasTimeout && timeout.value().IsZero()) {
      return FutexThread::WaitResult::TimedOut;
    }

    // Steps 22-30
    // To handle potential failures, we split this up into two phases:
    // First, we allocate everything: the notify task, the waiter, and
    // (if necessary) the timeout task. The allocations are managed
    // using unique pointers, which will free them on failure. This
    // phase has no external side-effects.

    // Second, we transfer ownership of the allocations to the right places:
    // the waiter owns the notify task, the shared array buffer owns the waiter,
    // and the event loop owns the timeout task. This phase is infallible.
    auto notifyTask = js::MakeUnique<WaitAsyncNotifyTask>(cx, promise);
    if (!notifyTask) {
      JS_ReportOutOfMemory(cx);
      return FutexThread::WaitResult::Error;
    }
    auto waiter = js::MakeUnique<AsyncFutexWaiter>(cx, byteOffset);
    if (!waiter) {
      JS_ReportOutOfMemory(cx);
      return FutexThread::WaitResult::Error;
    }

    notifyTask->setWaiter(waiter.get());
    waiter->setNotifyTask(notifyTask.get());

    if (hasTimeout) {
      timeoutTask = js::MakeUnique<WaitAsyncTimeoutTask>(waiter.get());
      if (!timeoutTask) {
        JS_ReportOutOfMemory(cx);
        return FutexThread::WaitResult::Error;
      }
      waiter->setTimeoutTask(timeoutTask.get());
    }

    // This is the last fallible operation. If it fails, all allocations
    // will be freed. init has no side-effects if it fails.
    if (!js::OffThreadPromiseTask::InitCancellable(cx, helperThreadLock,
                                                   std::move(notifyTask))) {
      return FutexThread::WaitResult::Error;
    }

    // Below this point, everything is infallible.
    AddWaiter(sarb, waiter.release(), futexLock);
  }  // End of futexLock critical section

  // We dispatch the task after leaving the critical section to avoid
  // potential deadlock if the dispatch callback has internal locking.
  // See bug 1980271.
  if (timeoutTask) {
    OffThreadPromiseRuntimeState& state =
        cx->runtime()->offThreadPromiseState.ref();
    // We are not tracking the dispatch of the timeout task using the
    // OffThreadPromiseRuntimeState, so we ignore the return value. If this
    // fails, the embeddings should call transferToRuntime on timeoutTask
    // which will clear itself, and set the notify task to be cleaned on
    // shutdown.
    (void)state.delayedDispatchToEventLoop(std::move(timeoutTask),
                                           timeout.value().ToMilliseconds());
  }

  // Step 31: Leave critical section.
  return FutexThread::WaitResult::OK;
}

// DoWait steps 12-35
// https://tc39.es/ecma262/#sec-dowait
// This implements the mode=ASYNC case.
template <typename T>
static PlainObject* AtomicsWaitAsync(
    JSContext* cx, SharedArrayRawBuffer* sarb, size_t byteOffset, T value,
    const mozilla::Maybe<mozilla::TimeDuration>& timeout) {
  // Step 16a.
  Rooted<PromiseObject*> promiseObject(
      cx, CreatePromiseObjectWithoutResolutionFunctions(cx));
  if (!promiseObject) {
    return nullptr;
  }

  // Steps 17-31
  switch (AtomicsWaitAsyncCriticalSection(cx, sarb, byteOffset, value, timeout,
                                          promiseObject)) {
    case FutexThread::WaitResult::NotEqual: {
      // Steps 16b, 20c-e
      RootedValue msg(cx, StringValue(cx->names().not_equal_));
      return CreateAsyncResultObject(cx, false, msg);
    }
    case FutexThread::WaitResult::TimedOut: {
      // Steps 16b, 21c-e
      RootedValue msg(cx, StringValue(cx->names().timed_out_));
      return CreateAsyncResultObject(cx, false, msg);
    }
    case FutexThread::WaitResult::Error:
      return nullptr;
    case FutexThread::WaitResult::OK:
      break;
  }

  // Steps 15b, 33-35
  RootedValue objectValue(cx, ObjectValue(*promiseObject));
  return CreateAsyncResultObject(cx, true, objectValue);
}

// DoWait steps 12-32
// https://tc39.es/ecma262/#sec-dowait
// This implements the mode=SYNC case.
template <typename T>
static FutexThread::WaitResult AtomicsWait(
    JSContext* cx, SharedArrayRawBuffer* sarb, size_t byteOffset, T value,
    const mozilla::Maybe<mozilla::TimeDuration>& timeout) {
  // Validation and other guards should ensure that this does not happen.
  MOZ_ASSERT(sarb, "wait is only applicable to shared memory");

  SharedMem<T*> addr =
      sarb->dataPointerShared().cast<T*>() + (byteOffset / sizeof(T));

  // Steps 17 and 31 (through destructor).
  // This lock also protects the "waiters" field on SharedArrayRawBuffer,
  // and it provides the necessary memory fence.
  AutoLockFutexAPI lock;

  // Steps 18-20.
  if (jit::AtomicOperations::loadSafeWhenRacy(addr) != value) {
    return FutexThread::WaitResult::NotEqual;
  }

  // Steps 14, 22-27
  SyncFutexWaiter w(cx, byteOffset);

  // Steps 28-29
  AddWaiter(sarb, &w, lock);
  FutexThread::WaitResult retval = cx->fx.wait(cx, lock.unique(), timeout);
  RemoveSyncWaiter(&w, lock);

  // Step 32
  return retval;
}

FutexThread::WaitResult js::atomics_wait_impl(
    JSContext* cx, SharedArrayRawBuffer* sarb, size_t byteOffset, int32_t value,
    const mozilla::Maybe<mozilla::TimeDuration>& timeout) {
  return AtomicsWait(cx, sarb, byteOffset, value, timeout);
}

FutexThread::WaitResult js::atomics_wait_impl(
    JSContext* cx, SharedArrayRawBuffer* sarb, size_t byteOffset, int64_t value,
    const mozilla::Maybe<mozilla::TimeDuration>& timeout) {
  return AtomicsWait(cx, sarb, byteOffset, value, timeout);
}

PlainObject* js::atomics_wait_async_impl(
    JSContext* cx, SharedArrayRawBuffer* sarb, size_t byteOffset, int32_t value,
    const mozilla::Maybe<mozilla::TimeDuration>& timeout) {
  return AtomicsWaitAsync(cx, sarb, byteOffset, value, timeout);
}

PlainObject* js::atomics_wait_async_impl(
    JSContext* cx, SharedArrayRawBuffer* sarb, size_t byteOffset, int64_t value,
    const mozilla::Maybe<mozilla::TimeDuration>& timeout) {
  return AtomicsWaitAsync(cx, sarb, byteOffset, value, timeout);
}

// https://tc39.es/ecma262/#sec-dowait
// DoWait ( mode, typedArray, index, value, timeout ), steps 8-35.
template <typename T>
static bool DoAtomicsWait(JSContext* cx, bool isAsync,
                          Handle<TypedArrayObject*> unwrappedTypedArray,
                          size_t index, T value, HandleValue timeoutv,
                          MutableHandleValue r) {
  mozilla::Maybe<mozilla::TimeDuration> timeout;
  if (!timeoutv.isUndefined()) {
    // Step 8.
    double timeout_ms;
    if (!ToNumber(cx, timeoutv, &timeout_ms)) {
      return false;
    }

    // Step 9.
    if (!std::isnan(timeout_ms)) {
      if (timeout_ms < 0) {
        timeout = mozilla::Some(mozilla::TimeDuration::FromSeconds(0.0));
      } else if (!std::isinf(timeout_ms)) {
        timeout =
            mozilla::Some(mozilla::TimeDuration::FromMilliseconds(timeout_ms));
      }
    }
  }

  // Step 10.
  if (!isAsync && !cx->fx.canWait()) {
    JS_ReportErrorNumberASCII(cx, GetErrorMessage, nullptr,
                              JSMSG_ATOMICS_WAIT_NOT_ALLOWED);
    return false;
  }

  // Step 11.
  Rooted<SharedArrayBufferObject*> unwrappedSab(
      cx, unwrappedTypedArray->bufferShared());

  // Step 12
  mozilla::Maybe<size_t> offset = unwrappedTypedArray->byteOffset();
  MOZ_ASSERT(
      offset,
      "offset can't become invalid because shared buffers can only grow");

  // Step 13.
  // The computation will not overflow because range checks have been
  // performed.
  size_t byteIndexInBuffer = index * sizeof(T) + *offset;

  // Steps 14-35.
  if (isAsync) {
    PlainObject* resultObject = atomics_wait_async_impl(
        cx, unwrappedSab->rawBufferObject(), byteIndexInBuffer, value, timeout);
    if (!resultObject) {
      return false;
    }
    r.setObject(*resultObject);
    return true;
  }

  switch (atomics_wait_impl(cx, unwrappedSab->rawBufferObject(),
                            byteIndexInBuffer, value, timeout)) {
    case FutexThread::WaitResult::NotEqual:
      r.setString(cx->names().not_equal_);
      return true;
    case FutexThread::WaitResult::OK:
      r.setString(cx->names().ok);
      return true;
    case FutexThread::WaitResult::TimedOut:
      r.setString(cx->names().timed_out_);
      return true;
    case FutexThread::WaitResult::Error:
      return false;
    default:
      MOZ_CRASH("Should not happen");
  }
}

// https://tc39.es/ecma262/#sec-dowait
// DoWait ( mode, typedArray, index, value, timeout )
static bool DoWait(JSContext* cx, bool isAsync, HandleValue objv,
                   HandleValue index, HandleValue valv, HandleValue timeoutv,
                   MutableHandleValue r) {
  // Steps 1-2.
  Rooted<TypedArrayObject*> unwrappedTypedArray(cx);
  if (!ValidateIntegerTypedArray(cx, objv, true, AccessMode::Read,
                                 &unwrappedTypedArray)) {
    return false;
  }
  MOZ_ASSERT(unwrappedTypedArray->type() == Scalar::Int32 ||
             unwrappedTypedArray->type() == Scalar::BigInt64);

  // Step 3
  if (!unwrappedTypedArray->isSharedMemory()) {
    return ReportBadArrayType(cx);
  }

  // Step 4.
  size_t intIndex;
  if (!ValidateAtomicAccess(cx, unwrappedTypedArray, index, &intIndex)) {
    return false;
  }

  // Step 5
  if (unwrappedTypedArray->type() == Scalar::Int32) {
    // Step 7.
    int32_t value;
    if (!ToInt32(cx, valv, &value)) {
      return false;
    }

    // Steps 8-35.
    return DoAtomicsWait(cx, isAsync, unwrappedTypedArray, intIndex, value,
                         timeoutv, r);
  }

  MOZ_ASSERT(unwrappedTypedArray->type() == Scalar::BigInt64);

  // Step 6.
  RootedBigInt value(cx, ToBigInt(cx, valv));
  if (!value) {
    return false;
  }

  // Steps 8-35.
  return DoAtomicsWait(cx, isAsync, unwrappedTypedArray, intIndex,
                       BigInt::toInt64(value), timeoutv, r);
}

// 24.4.11 Atomics.wait ( typedArray, index, value, timeout )
// https://tc39.es/ecma262/#sec-atomics.wait
static bool atomics_wait(JSContext* cx, unsigned argc, Value* vp) {
  CallArgs args = CallArgsFromVp(argc, vp);
  HandleValue objv = args.get(0);
  HandleValue index = args.get(1);
  HandleValue valv = args.get(2);
  HandleValue timeoutv = args.get(3);
  MutableHandleValue r = args.rval();

  return DoWait(cx, /*isAsync = */ false, objv, index, valv, timeoutv, r);
}

// Atomics.waitAsync ( typedArray, index, value, timeout )
// https://tc39.es/ecma262/#sec-atomics.waitasync
static bool atomics_wait_async(JSContext* cx, unsigned argc, Value* vp) {
  CallArgs args = CallArgsFromVp(argc, vp);
  HandleValue objv = args.get(0);
  HandleValue index = args.get(1);
  HandleValue valv = args.get(2);
  HandleValue timeoutv = args.get(3);
  MutableHandleValue r = args.rval();

  return DoWait(cx, /*isAsync = */ true, objv, index, valv, timeoutv, r);
}

// Atomics.notify ( typedArray, index, count ), steps 8-13.
// https://tc39.es/ecma262/#sec-atomics.notify
bool js::atomics_notify_impl(JSContext* cx, SharedArrayRawBuffer* sarb,
                             size_t byteOffset, int64_t count, int64_t* woken) {
  MOZ_ASSERT(woken);

  // Validation should ensure this does not happen.
  MOZ_ASSERT(sarb, "notify is only applicable to shared memory");

  // Step 8
  *woken = 0;

  Rooted<GCVector<PromiseObject*>> promisesToResolve(
      cx, GCVector<PromiseObject*>(cx));
  {
    // Steps 9, 12 (through destructor).
    AutoLockHelperThreadState helperLock;
    AutoLockFutexAPI lock;
    // Steps 10-11
    FutexWaiterListNode* waiterListHead = sarb->waiters();
    FutexWaiterListNode* iter = waiterListHead->next();
    while (count && iter != waiterListHead) {
      FutexWaiter* waiter = iter->toWaiter();
      iter = iter->next();
      if (byteOffset != waiter->offset()) {
        continue;
      }
      if (waiter->isSync()) {
        // For sync waits, the context to notify is currently sleeping.
        // We notify that context (unless it's already been notified by
        // another thread).
        if (!waiter->cx()->fx.isWaiting()) {
          continue;
        }
        waiter->cx()->fx.notify(FutexThread::NotifyExplicit);
      } else {
        // For async waits, we resolve a promise.

        // Steps to clean up case 1. and 2. in SMDOC for Atomics.waitAsync
        // Take ownership of the async waiter, so that it will be
        // freed at the end of this block.
        UniquePtr<AsyncFutexWaiter> asyncWaiter(
            RemoveAsyncWaiter(waiter->asAsync(), lock));
        asyncWaiter->maybeClearTimeout(lock);
        // If we are notifying a waiter that was created by the current
        // context, we resolve the promise directly instead of dispatching
        // a task to the event loop.
        OffThreadPromiseTask* task = asyncWaiter->notifyTask();
        if (waiter->cx() == cx) {
          // Add the promise to a list to resolve as soon as we've left the
          // critical section.
          PromiseObject* promise =
              OffThreadPromiseTask::ExtractAndForget(task, helperLock);
          if (!promisesToResolve.append(promise)) {
            return false;
          }
        } else {
          // Dispatch a task to resolve the promise with value "ok".
          task->removeFromCancellableListAndDispatch(helperLock);
        }
      }
      // Overflow will be a problem only in two cases:
      // (1) 128-bit systems with substantially more than 2^64 bytes of
      //     memory per process, and a very lightweight
      //     Atomics.waitAsync().  Obviously a future problem.
      // (2) Bugs.
      MOZ_RELEASE_ASSERT(*woken < INT64_MAX);
      (*woken)++;
      if (count > 0) {
        --count;
      }
    }
  }

  // Step 10 (reordered)
  // We resolve same-thread promises after we've left the critical section to
  // avoid mutex ordering problems.
  RootedValue resultMsg(cx, StringValue(cx->names().ok));
  for (uint32_t i = 0; i < promisesToResolve.length(); i++) {
    AutoRealm ar(cx, promisesToResolve[i]);
    if (!PromiseObject::resolve(cx, promisesToResolve[i], resultMsg)) {
      MOZ_ASSERT(cx->isThrowingOutOfMemory() || cx->isThrowingOverRecursed());
      return false;
    }
  }

  // Step 13.
  return true;
}

// ES2021 draft rev bd868f20b8c574ad6689fba014b62a1dba819e56
// 24.4.12 Atomics.notify ( typedArray, index, count )
static bool atomics_notify(JSContext* cx, unsigned argc, Value* vp) {
  CallArgs args = CallArgsFromVp(argc, vp);
  HandleValue objv = args.get(0);
  HandleValue index = args.get(1);
  HandleValue countv = args.get(2);
  MutableHandleValue r = args.rval();

  // Step 1.
  Rooted<TypedArrayObject*> unwrappedTypedArray(cx);
  if (!ValidateIntegerTypedArray(cx, objv, true, AccessMode::Read,
                                 &unwrappedTypedArray)) {
    return false;
  }
  MOZ_ASSERT(unwrappedTypedArray->type() == Scalar::Int32 ||
             unwrappedTypedArray->type() == Scalar::BigInt64);

  // Step 2.
  size_t intIndex;
  if (!ValidateAtomicAccess(cx, unwrappedTypedArray, index, &intIndex)) {
    return false;
  }

  // Steps 3-4.
  int64_t count;
  if (countv.isUndefined()) {
    count = -1;
  } else {
    double dcount;
    if (!ToInteger(cx, countv, &dcount)) {
      return false;
    }
    if (dcount < 0.0) {
      dcount = 0.0;
    }
    count = dcount < double(1ULL << 63) ? int64_t(dcount) : -1;
  }

  // https://github.com/tc39/ecma262/pull/1908
  if (!unwrappedTypedArray->isSharedMemory()) {
    r.setInt32(0);
    return true;
  }

  // Step 5.
  Rooted<SharedArrayBufferObject*> unwrappedSab(
      cx, unwrappedTypedArray->bufferShared());

  // Step 6.
  mozilla::Maybe<size_t> offset = unwrappedTypedArray->byteOffset();
  MOZ_ASSERT(
      offset,
      "offset can't become invalid because shared buffers can only grow");

  // Steps 7-9.
  // The computation will not overflow because range checks have been
  // performed.
  size_t elementSize = Scalar::byteSize(unwrappedTypedArray->type());
  size_t indexedPosition = intIndex * elementSize + *offset;

  // Steps 10-16.

  int64_t woken = 0;
  if (!atomics_notify_impl(cx, unwrappedSab->rawBufferObject(), indexedPosition,
                           count, &woken)) {
    return false;
  }

  r.setNumber(double(woken));

  return true;
}

/**
 * Atomics.pause ( [ N ] )
 *
 * https://tc39.es/proposal-atomics-microwait/
 */
static bool atomics_pause(JSContext* cx, unsigned argc, Value* vp) {
  CallArgs args = CallArgsFromVp(argc, vp);

  // Step 1.
  if (args.hasDefined(0)) {
    if (!args[0].isNumber() || !IsInteger(args[0].toNumber())) {
      JS_ReportErrorNumberASCII(cx, GetErrorMessage, nullptr,
                                JSMSG_ATOMICS_PAUSE_BAD_COUNT);
      return false;
    }
  }

  // Step 2.
  //
  // We ignore the iteration count when not inlining this operation.
  jit::AtomicOperations::pause();

  // Step 3.
  args.rval().setUndefined();
  return true;
}

/* static */
bool js::FutexThread::initialize() {
  MOZ_ASSERT(!lock_);
  lock_ = js_new<js::Mutex>(mutexid::FutexThread);
  return lock_ != nullptr;
}

/* static */
void js::FutexThread::destroy() {
  if (lock_) {
    js::Mutex* lock = lock_;
    js_delete(lock);
    lock_ = nullptr;
  }
}

/* static */
void js::FutexThread::lock() {
  // Load the atomic pointer.
  js::Mutex* lock = lock_;

  lock->lock();
}

/* static */ mozilla::Atomic<js::Mutex*, mozilla::SequentiallyConsistent>
    FutexThread::lock_;

/* static */
void js::FutexThread::unlock() {
  // Load the atomic pointer.
  js::Mutex* lock = lock_;

  lock->unlock();
}

js::FutexThread::FutexThread()
    : cond_(nullptr), state_(Idle), canWait_(false) {}

bool js::FutexThread::initInstance() {
  MOZ_ASSERT(lock_);
  cond_ = js_new<js::ConditionVariable>();
  return cond_ != nullptr;
}

void js::FutexThread::destroyInstance() {
  if (cond_) {
    js_delete(cond_);
  }
}

bool js::FutexThread::isWaiting() {
  // When a worker is awoken for an interrupt it goes into state
  // WaitingNotifiedForInterrupt for a short time before it actually
  // wakes up and goes into WaitingInterrupted.  In those states the
  // worker is still waiting, and if an explicit notify arrives the
  // worker transitions to Woken.  See further comments in
  // FutexThread::wait().
  return state_ == Waiting || state_ == WaitingInterrupted ||
         state_ == WaitingNotifiedForInterrupt;
}

FutexThread::WaitResult js::FutexThread::wait(
    JSContext* cx, js::UniqueLock<js::Mutex>& locked,
    const mozilla::Maybe<mozilla::TimeDuration>& timeout) {
  MOZ_ASSERT(&cx->fx == this);
  MOZ_ASSERT(cx->fx.canWait());
  MOZ_ASSERT(state_ == Idle || state_ == WaitingInterrupted);

  // Disallow waiting when a runtime is processing an interrupt.
  // See explanation below.

  if (state_ == WaitingInterrupted) {
    UnlockGuard unlock(locked);
    JS_ReportErrorNumberASCII(cx, GetErrorMessage, nullptr,
                              JSMSG_ATOMICS_WAIT_NOT_ALLOWED);
    return WaitResult::Error;
  }

  // Go back to Idle after returning.
  auto onFinish = mozilla::MakeScopeExit([&] { state_ = Idle; });

  const bool isTimed = timeout.isSome();

  auto finalEnd = timeout.map([](const mozilla::TimeDuration& timeout) {
    return mozilla::TimeStamp::Now() + timeout;
  });

  // 4000s is about the longest timeout slice that is guaranteed to
  // work cross-platform.
  auto maxSlice = mozilla::TimeDuration::FromSeconds(4000.0);

  for (;;) {
    // If we are doing a timed wait, calculate the end time for this wait
    // slice.
    auto sliceEnd = finalEnd.map([&](mozilla::TimeStamp& finalEnd) {
      auto sliceEnd = mozilla::TimeStamp::Now() + maxSlice;
      if (finalEnd < sliceEnd) {
        sliceEnd = finalEnd;
      }
      return sliceEnd;
    });

    state_ = Waiting;

    MOZ_ASSERT((cx->runtime()->beforeWaitCallback == nullptr) ==
               (cx->runtime()->afterWaitCallback == nullptr));
    mozilla::DebugOnly<bool> callbacksPresent =
        cx->runtime()->beforeWaitCallback != nullptr;

    void* cookie = nullptr;
    uint8_t clientMemory[JS::WAIT_CALLBACK_CLIENT_MAXMEM];
    if (cx->runtime()->beforeWaitCallback) {
      cookie = (*cx->runtime()->beforeWaitCallback)(clientMemory);
    }

    if (isTimed) {
      (void)cond_->wait_until(locked, *sliceEnd);
    } else {
      cond_->wait(locked);
    }

    MOZ_ASSERT((cx->runtime()->afterWaitCallback != nullptr) ==
               callbacksPresent);
    if (cx->runtime()->afterWaitCallback) {
      (*cx->runtime()->afterWaitCallback)(cookie);
    }

    switch (state_) {
      case FutexThread::Waiting:
        // Timeout or spurious wakeup.
        if (isTimed) {
          auto now = mozilla::TimeStamp::Now();
          if (now >= *finalEnd) {
            return WaitResult::TimedOut;
          }
        }
        break;

      case FutexThread::Woken:
        return WaitResult::OK;

      case FutexThread::WaitingNotifiedForInterrupt:
        // The interrupt handler may reenter the engine.  In that case
        // there are two complications:
        //
        // - The waiting thread is not actually waiting on the
        //   condition variable so we have to record that it
        //   should be woken when the interrupt handler returns.
        //   To that end, we flag the thread as interrupted around
        //   the interrupt and check state_ when the interrupt
        //   handler returns.  A notify() call that reaches the
        //   runtime during the interrupt sets state_ to Woken.
        //
        // - It is in principle possible for wait() to be
        //   reentered on the same thread/runtime and waiting on the
        //   same location and to yet again be interrupted and enter
        //   the interrupt handler.  In this case, it is important
        //   that when another agent notifies waiters, all waiters using
        //   the same runtime on the same location are woken in LIFO
        //   order; FIFO may be the required order, but FIFO would
        //   fail to wake up the innermost call.  Interrupts are
        //   outside any spec anyway.  Also, several such suspended
        //   waiters may be woken at a time.
        //
        //   For the time being we disallow waiting from within code
        //   that runs from within an interrupt handler; this may
        //   occasionally (very rarely) be surprising but is
        //   expedient.  Other solutions exist, see bug #1131943.  The
        //   code that performs the check is above, at the head of
        //   this function.

        state_ = WaitingInterrupted;
        {
          UnlockGuard unlock(locked);
          if (!cx->handleInterrupt()) {
            return WaitResult::Error;
          }
        }
        if (state_ == Woken) {
          return WaitResult::OK;
        }
        break;

      default:
        MOZ_CRASH("Bad FutexState in wait()");
    }
  }
}

void js::FutexThread::notify(NotifyReason reason) {
  MOZ_ASSERT(isWaiting());

  if ((state_ == WaitingInterrupted || state_ == WaitingNotifiedForInterrupt) &&
      reason == NotifyExplicit) {
    state_ = Woken;
    return;
  }
  switch (reason) {
    case NotifyExplicit:
      state_ = Woken;
      break;
    case NotifyForJSInterrupt:
      if (state_ == WaitingNotifiedForInterrupt) {
        return;
      }
      state_ = WaitingNotifiedForInterrupt;
      break;
    default:
      MOZ_CRASH("bad NotifyReason in FutexThread::notify()");
  }
  cond_->notify_all();
}

const JSFunctionSpec AtomicsMethods[] = {
    JS_INLINABLE_FN("compareExchange", atomics_compareExchange, 4, 0,
                    AtomicsCompareExchange),
    JS_INLINABLE_FN("load", atomics_load, 2, 0, AtomicsLoad),
    JS_INLINABLE_FN("store", atomics_store, 3, 0, AtomicsStore),
    JS_INLINABLE_FN("exchange", atomics_exchange, 3, 0, AtomicsExchange),
    JS_INLINABLE_FN("add", atomics_add, 3, 0, AtomicsAdd),
    JS_INLINABLE_FN("sub", atomics_sub, 3, 0, AtomicsSub),
    JS_INLINABLE_FN("and", atomics_and, 3, 0, AtomicsAnd),
    JS_INLINABLE_FN("or", atomics_or, 3, 0, AtomicsOr),
    JS_INLINABLE_FN("xor", atomics_xor, 3, 0, AtomicsXor),
    JS_INLINABLE_FN("isLockFree", atomics_isLockFree, 1, 0, AtomicsIsLockFree),
    JS_FN("wait", atomics_wait, 4, 0),
    JS_FN("waitAsync", atomics_wait_async, 4, 0),
    JS_FN("notify", atomics_notify, 3, 0),
    JS_FN("wake", atomics_notify, 3, 0),  // Legacy name
    JS_INLINABLE_FN("pause", atomics_pause, 0, 0, AtomicsPause),
    JS_FS_END,
};

static const JSPropertySpec AtomicsProperties[] = {
    JS_STRING_SYM_PS(toStringTag, "Atomics", JSPROP_READONLY),
    JS_PS_END,
};

static JSObject* CreateAtomicsObject(JSContext* cx, JSProtoKey key) {
  RootedObject proto(cx, &cx->global()->getObjectPrototype());
  return NewObjectWithGivenProto(cx, &AtomicsObject::class_, proto,
                                 {.newKind = TenuredObject});
}

static const ClassSpec AtomicsClassSpec = {
    CreateAtomicsObject,
    nullptr,
    AtomicsMethods,
    AtomicsProperties,
};

const JSClass AtomicsObject::class_ = {
    "Atomics",
    JSCLASS_HAS_CACHED_PROTO(JSProto_Atomics),
    JS_NULL_CLASS_OPS,
    &AtomicsClassSpec,
};