js-atomics-synchronization.h

Go to the documentation of this file.

// Copyright 2022 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_OBJECTS_JS_ATOMICS_SYNCHRONIZATION_H_
#define V8_OBJECTS_JS_ATOMICS_SYNCHRONIZATION_H_
 
#include <atomic>
 
#include "src/base/platform/time.h"
#include "src/execution/thread-id.h"
#include "src/objects/contexts.h"
#include "src/objects/js-objects.h"
#include "src/objects/js-struct.h"
#include "src/objects/struct.h"
 
// Has to be the last include (doesn't have include guards):
#include "src/objects/object-macros.h"
 
namespace v8 {
namespace internal {
 
#include "torque-generated/src/objects/js-atomics-synchronization-tq.inc"
 
namespace detail {
class WaiterQueueLockGuard;
class WaiterQueueNode;
template <typename T>
class AsyncWaiterQueueNode;
}  // namespace detail
 
using detail::WaiterQueueLockGuard;
using detail::WaiterQueueNode;
using LockAsyncWaiterQueueNode = detail::AsyncWaiterQueueNode<JSAtomicsMutex>;
using WaitAsyncWaiterQueueNode =
    detail::AsyncWaiterQueueNode<JSAtomicsCondition>;
 
// JSSynchronizationPrimitive is the base class for JSAtomicsMutex and
// JSAtomicsCondition. It contains a 32-bit state field and a pointer to a
// waiter queue head, used to manage the queue of waiting threads for both: the
// mutex and the condition variable.
 
class JSSynchronizationPrimitive
    : public TorqueGeneratedJSSynchronizationPrimitive<
          JSSynchronizationPrimitive, AlwaysSharedSpaceJSObject> {
 public:
  // Synchronization only store raw data as state.
  static constexpr int kEndOfTaggedFieldsOffset = JSObject::kHeaderSize;
  class BodyDescriptor;
 
  static void IsolateDeinit(Isolate* isolate);
  Tagged<Object> NumWaitersForTesting(Isolate* requester);
 
  TQ_OBJECT_CONSTRUCTORS(JSSynchronizationPrimitive)
  inline void SetNullWaiterQueueHead();
 
 protected:
  using StateT = uint32_t;
 
  // The `HasWaitersField` bitfield has the following properties:
  // - It isn't a lock bit, meaning that if this bit is 1,
  //   that doesn't imply that some thread has exclusive write access to the
  //   lock state.
  // - It is a metadata bit that's only written with the queue lock bit held.
  // - It is set iff the external pointer is non-null.
  // - It can be read without holding any lock bit.
  // - It allows for fast and threadsafe checking if there is a waiter,
  //   as dereferencing the waiter queue should be done only when the
  //   `IsWaiterQueueLockedField` bit is set.
  using HasWaitersField = base::BitField<bool, 0, 1>;
 
  // The `IsWaiterQueueLockedField` bitfield protects the waiter queue head from
  // concurrent modification. It is set through as CAS operation in a spinlock.
  using IsWaiterQueueLockedField = HasWaitersField::Next<bool, 1>;
 
  template <class T, int size>
  using NextBitField = IsWaiterQueueLockedField::Next<T, size>;
 
  inline std::atomic<StateT>* AtomicStatePtr();
  inline WaiterQueueNode* DestructivelyGetWaiterQueueHead(Isolate* requester);
 
  // Store the waiter queue head in the synchronization primitive. If the head
  // is not null, the returned state has the kHasWaitersBit set.
  // In case of pointer compression, the waiter queue head is encoded as an
  // `ExternalPointerHandle`.
  inline StateT SetWaiterQueueHead(Isolate* requester,
                                   WaiterQueueNode* waiter_head,
                                   StateT new_state);
 
  // Set the new state without modifying bits outside the waiter queue mask.
  static void SetWaiterQueueStateOnly(std::atomic<StateT>* state,
                                      StateT new_state);
 
  static bool TryLockWaiterQueueExplicit(std::atomic<StateT>* state,
                                         StateT& expected);
 
  using TorqueGeneratedJSSynchronizationPrimitive<
      JSSynchronizationPrimitive, AlwaysSharedSpaceJSObject>::state;
  using TorqueGeneratedJSSynchronizationPrimitive<
      JSSynchronizationPrimitive, AlwaysSharedSpaceJSObject>::set_state;
  using DequeueMatcher = std::function<bool(WaiterQueueNode*)>;
 
  static constexpr StateT kEmptyState = 0;
  static constexpr StateT kWaiterQueueMask =
      base::BitFieldUnion<HasWaitersField, IsWaiterQueueLockedField>::kMask;
 
 private:
  friend class WaiterQueueLockGuard;
 
#if V8_COMPRESS_POINTERS
  // When pointer compression is enabled, the pointer to the waiter queue head
  // is stored in the external pointer table and the object itself only contains
  // a 32-bit external pointer handles.
  inline ExternalPointerHandle* waiter_queue_head_handle_location() const;
#else
  inline WaiterQueueNode** waiter_queue_head_location() const;
#endif
  // Remove the matching async waiter queue nodes from the locked and unlocked
  // async waiter lists in the isolate.
  static void CleanupAsyncWaiterLists(Isolate* isolate, DequeueMatcher matcher);
};
 
// A non-recursive mutex that is exposed to JS.
//
// It has the following properties:
//   - Slim: 12-16 bytes. Lock state is 4 bytes, waiter queue head is 4 bytes
//     when V8_COMPRESS_POINTERS, and sizeof(void*) otherwise. Owner thread is
//     an additional 4 bytes.
//   - Fast when uncontended: a single weak CAS.
//   - Possibly unfair under contention.
//   - Moving GC safe. It uses an index into the shared Isolate's external
//     pointer table to store a queue of sleeping threads.
//   - Parks the main thread LocalHeap when the thread is blocked on acquiring
//     the lock. Unparks the main thread LocalHeap when unblocked. This means
//     that the lock can only be used with main thread isolates (including
//     workers) but not with helper threads that have their own LocalHeap.
//
// This mutex manages its own queue of waiting threads under contention, i.e.
// it implements a futex in userland. The algorithm is inspired by WebKit's
// ParkingLot.
//
// The state variable encodes the locking state as a single word: 0bLQW.
// - W: Whether there are waiter threads in the queue.
// - Q: Whether the waiter queue is locked.
// - L: Whether the lock itself is locked.
 
// The locking algorithm is as follows:
//  1. Fast Path. Unlocked+Uncontended(0b000) -> Locked+Uncontended(0b100).
//  2. Otherwise, slow path.
//    a. Attempt to acquire the L bit (set current state | 0b100) on the state
//       using a CAS spin loop bounded to some number of iterations.
//    b. If L bit cannot be acquired, park the current thread:
//     i.   Acquire the Q bit (set current state | 0b010) in a spinlock.
//     ii.  Destructively get the waiter queue head.
//     iii. Enqueue this thread's WaiterQueueNode to the tail of the list
//          pointed to by the head, possibly creating a new list.
//     iv.  Release the Q bit and set the W bit
//          (set (current state | 0b001) & ~0b010 in a single CAS operation).
//     iv.  Put the thread to sleep.
//     v.   Upon wake up, go to i.
 
// The unlocking algorithm is as follows:
//  1. Fast Path. Locked+Uncontended(0b100) -> Unlocked+Uncontended(0b000).
//  2. Otherwise, slow path.
//    a. Acquire the Q bit (set current state | 0b010) in a spinlock.
//    b. Destructively get the waiter queue head.
//    c. If the head is not null, dequeue the head.
//    d. Store the new waiter queue head (possibly null).
//    f. If the list is empty, clear the W bit (set current state & ~0b001).
//    g. Release the Q bit and clear the L bit (set current state & ~0b100).
//       (The W and Q bits must be set in a single CAS operation).
//    h. If the list was not empty, notify the dequeued head.
class JSAtomicsMutex
    : public TorqueGeneratedJSAtomicsMutex<JSAtomicsMutex,
                                           JSSynchronizationPrimitive> {
 public:
  using AsyncWaiterNodeType = LockAsyncWaiterQueueNode;
  // A non-copyable wrapper class that provides an RAII-style mechanism for
  // owning the `JSAtomicsMutex`.
  class V8_NODISCARD LockGuardBase {
   public:
    LockGuardBase(const LockGuardBase&) = delete;
    LockGuardBase& operator=(const LockGuardBase&) = delete;
    inline ~LockGuardBase();
    bool locked() const { return locked_; }
 
   protected:
    inline LockGuardBase(Isolate* isolate, DirectHandle<JSAtomicsMutex> mutex,
                         bool locked);
 
   private:
    Isolate* isolate_;
    DirectHandle<JSAtomicsMutex> mutex_;
    bool locked_;
  };
 
  // The mutex is attempted to be locked via `Lock` when a `LockGuard`
  // object is created, the lock will be acquired unless the timeout is reached.
  // If the mutex was acquired, then it is released when the `LockGuard` object
  // is destructed.
  class V8_NODISCARD LockGuard final : public LockGuardBase {
   public:
    inline LockGuard(Isolate* isolate, DirectHandle<JSAtomicsMutex> mutex,
                     std::optional<base::TimeDelta> timeout = std::nullopt);
  };
 
  // The mutex is attempted to be locked via `TryLock` when a `TryLockGuard`
  // object is created. If the mutex was acquired, then it is released when the
  // `TryLockGuard` object is destructed.
  class V8_NODISCARD TryLockGuard final : public LockGuardBase {
   public:
    inline TryLockGuard(Isolate* isolate, DirectHandle<JSAtomicsMutex> mutex);
  };
 
  DECL_PRINTER(JSAtomicsMutex)
  EXPORT_DECL_VERIFIER(JSAtomicsMutex)
 
  static DirectHandle<JSObject> CreateResultObject(Isolate* isolate,
                                                   DirectHandle<Object> value,
                                                   bool success);
 
  // Lock the mutex, blocking if it's currently owned by another thread.
  // Returns false if the lock times out, true otherwise.
  static inline bool Lock(
      Isolate* requester, DirectHandle<JSAtomicsMutex> mutex,
      std::optional<base::TimeDelta> timeout = std::nullopt);
 
  V8_WARN_UNUSED_RESULT inline bool TryLock();
 
  // Try to lock the mutex, if it's currently owned by another thread, creates
  // a LockAsyncWaiterQueueNode and enqueue it in the mutex's waiter queue.
  // The `internal_locked_promise` is resolved when the node is notified.
  // Returns true if the lock was acquired, false otherwise.
  static bool LockAsync(Isolate* requester, DirectHandle<JSAtomicsMutex> mutex,
                        Handle<JSPromise> internal_locked_promise,
                        MaybeHandle<JSPromise> unlocked_promise,
                        AsyncWaiterNodeType** waiter_node,
                        std::optional<base::TimeDelta> timeout = std::nullopt);
 
  // A wrapper for LockAsync called when an asyncWait call returns control
  // to the lockAsync callback. It calls `LockAsync` without setting all the
  // logic to run the callback, since the callback is already running.
  static DirectHandle<JSPromise> LockAsyncWrapperForWait(
      Isolate* requester, DirectHandle<JSAtomicsMutex> mutex);
 
  // Try to take the lock and set up the promise logic to asynchronously run
  // the callback under the lock. Always returns a promise that settles when the
  // promise is unlocked or times out.
  static MaybeDirectHandle<JSPromise> LockOrEnqueuePromise(
      Isolate* isolate, DirectHandle<JSAtomicsMutex> mutex,
      DirectHandle<Object> callback, std::optional<base::TimeDelta> timeout);
 
  // Try to take the lock or requeue an existing node.
  static bool LockOrEnqueueAsyncNode(Isolate* isolate,
                                     DirectHandle<JSAtomicsMutex> mutex,
                                     LockAsyncWaiterQueueNode* node);
  static void HandleAsyncNotify(LockAsyncWaiterQueueNode* node);
  static void HandleAsyncTimeout(LockAsyncWaiterQueueNode* node);
 
  inline void Unlock(Isolate* requester);
 
  inline bool IsHeld();
  inline bool IsCurrentThreadOwner();
 
  void UnlockAsyncLockedMutex(
      Isolate* requester, DirectHandle<Foreign> async_locked_waiter_wrapper);
 
  static void CleanupMatchingAsyncWaiters(Isolate* isolate,
                                          WaiterQueueNode* node,
                                          DequeueMatcher matcher);
 
  // The context slots for the artificial context created for the resolve and
  // reject handlers in charge of unlocking the mutex after the callback passed
  // to Atomics.Mutex.lockAsync is executed.
  enum {
    // The context slot for the js mutex that is locked asynchronously.
    kMutexAsyncContextSlot = Context::MIN_CONTEXT_SLOTS,
    // The context slot for the js exposed promise returned by the call to
    // Atomics.Mutex.lockAsync, it should be resolved or rejected after the
    // mutex is released.
    kUnlockedPromiseAsyncContextSlot,
    // The isolate keeps track of WaiterQueueNodes for each mutex locked
    // asynchronously, this is so that the lock can be released in case worker
    // termination. The kAsyncLockedWaiterAsyncContextSlot slot is used to store
    // a Foreign wrapping around an ExternalPointerHandle (or raw
    // pointer when pointer compression is disabled) pointing to the
    // WaiterQueueNode so that it can be removed from the list when the lock is
    // released through the usual path.
    kAsyncLockedWaiterAsyncContextSlot,
    kAsyncContextLength
  };
 
  TQ_OBJECT_CONSTRUCTORS(JSAtomicsMutex)
 
 private:
  friend class Factory;
 
  // There are 3 state bits: whether there are waiter threads in the queue,
  // whether the waiter queue is locked (both inherited from the base class),
  // and whether the lock itself is locked (IsLockedField).
  using IsLockedField = JSSynchronizationPrimitive::NextBitField<bool, 1>;
 
  static constexpr StateT kUnlockedUncontended = kEmptyState;
  static constexpr StateT kLockedUncontended = IsLockedField::encode(true);
 
  inline void SetCurrentThreadAsOwner();
  inline void ClearOwnerThread();
 
  inline std::atomic<int32_t>* AtomicOwnerThreadIdPtr();
 
  V8_EXPORT_PRIVATE static bool LockSlowPath(
      Isolate* requester, DirectHandle<JSAtomicsMutex> mutex,
      std::atomic<StateT>* state, std::optional<base::TimeDelta> timeout);
  static bool LockAsyncSlowPath(Isolate* isolate,
                                DirectHandle<JSAtomicsMutex> mutex,
                                std::atomic<StateT>* state,
                                Handle<JSPromise> internal_locked_promise,
                                MaybeHandle<JSPromise> unlocked_promise,
                                AsyncWaiterNodeType** waiter_node,
                                std::optional<base::TimeDelta> timeout);
 
  V8_EXPORT_PRIVATE void UnlockSlowPath(Isolate* requester,
                                        std::atomic<StateT>* state);
 
  // Returns true if the JS mutex was taken and false otherwise.
  bool LockJSMutexOrDequeueTimedOutWaiter(Isolate* requester,
                                          std::atomic<StateT>* state,
                                          WaiterQueueNode* timed_out_waiter);
 
  static bool TryLockExplicit(std::atomic<StateT>* state, StateT& expected);
  // Returns nullopt if the JS mutex is acquired, otherwise return an optional
  // with a `WaiterQueueLockGuard` object.
  static std::optional<WaiterQueueLockGuard> LockWaiterQueueOrJSMutex(
      std::atomic<StateT>* state, StateT& current_state);
  V8_EXPORT_PRIVATE static bool MutexTryLock(Isolate* requester,
                                             DirectHandle<JSAtomicsMutex> mutex,
                                             std::atomic<StateT>* state);
  V8_INLINE static bool BackoffTryLock(Isolate* requester,
                                       DirectHandle<JSAtomicsMutex> mutex,
                                       std::atomic<StateT>* state);
  static bool DequeueTimedOutAsyncWaiter(Isolate* requester,
                                         DirectHandle<JSAtomicsMutex> mutex,
                                         std::atomic<StateT>* state,
                                         WaiterQueueNode* timed_out_waiter);
 
  V8_EXPORT_PRIVATE static bool MaybeEnqueueNode(
      Isolate* requester, DirectHandle<JSAtomicsMutex> mutex,
      std::atomic<StateT>* state, WaiterQueueNode* this_waiter);
 
  template <typename LockSlowPathWrapper,
            typename = std::enable_if<std::is_invocable_r_v<
                bool, LockSlowPathWrapper, std::atomic<StateT>*>>>
  static inline bool LockImpl(Isolate* requester,
                              DirectHandle<JSAtomicsMutex> mutex,
                              std::optional<base::TimeDelta> timeout,
                              LockSlowPathWrapper slow_path_wrapper);
 
  using TorqueGeneratedJSAtomicsMutex<
      JSAtomicsMutex, JSSynchronizationPrimitive>::owner_thread_id;
  using TorqueGeneratedJSAtomicsMutex<
      JSAtomicsMutex, JSSynchronizationPrimitive>::set_owner_thread_id;
};
 
// A condition variable that is exposed to JS.
//
// It has the following properties:
//   - Slim: 8-12 bytes. Lock state is 4 bytes, waiter queue head is 4 bytes
//     when V8_COMPRESS_POINTERS, and sizeof(void*) otherwise.
//   - Moving GC safe. It uses an index into the shared Isolate's external
//     pointer table to store a queue of sleeping threads.
//   - Parks the main thread LocalHeap when waiting. Unparks the main thread
//     LocalHeap after waking up.
//
// This condition variable manages its own queue of waiting threads, like
// JSAtomicsMutex. The algorithm is inspired by WebKit's ParkingLot.
//
// The state variable encodes the locking state as a single word: 0bQW.
// - W: Whether there are waiter threads in the queue.
// - Q: Whether the waiter queue is locked.
//
// The waiting algorithm is as follows:
// 1. Acquire the Q bit (set current state | 0b010) in a spinlock.
// 2. Destructively get the waiter queue head.
// 3. Enqueue this thread's WaiterQueueNode to the tail of the list pointed to
//    by the head, possibly creating a new list.
// 4. Release the Q bit and set the W bit (set (current state | 0b001) & ~0b010
//    in a single CAS operation).
// 5. Put the thread to sleep.
//
// The notification algorithm is as follows:
// 1. Acquire the Q bit (set current state | 0b010) in a spinlock.
// 2. Destructively get the waiter queue head.
// 3. If the head is not null, dequeue the head.
// 4. Store the new waiter queue head (possibly null).
// 5. If the list is empty, clear the W bit (set current state & ~0b001).
// 6. Release the Q bit (set current state & ~0b010).
//    (The W and Q bits must be set in a single CAS operation).
// 7. If the list was not empty, notify the dequeued head.
 
class JSAtomicsCondition
    : public TorqueGeneratedJSAtomicsCondition<JSAtomicsCondition,
                                               JSSynchronizationPrimitive> {
 public:
  using AsyncWaiterNodeType = WaitAsyncWaiterQueueNode;
  DECL_PRINTER(JSAtomicsCondition)
  EXPORT_DECL_VERIFIER(JSAtomicsCondition)
 
  V8_EXPORT_PRIVATE static bool WaitFor(Isolate* requester,
                                        DirectHandle<JSAtomicsCondition> cv,
                                        DirectHandle<JSAtomicsMutex> mutex,
                                        std::optional<base::TimeDelta> timeout);
 
  V8_EXPORT_PRIVATE static MaybeDirectHandle<JSReceiver> WaitAsync(
      Isolate* requester, DirectHandle<JSAtomicsCondition> cv,
      DirectHandle<JSAtomicsMutex> mutex,
      std::optional<base::TimeDelta> timeout);
 
  static void HandleAsyncNotify(WaitAsyncWaiterQueueNode* node);
  static void HandleAsyncTimeout(WaitAsyncWaiterQueueNode* node);
 
  static constexpr uint32_t kAllWaiters = UINT32_MAX;
 
  // Notify {count} waiters. Returns the number of waiters woken up.
  static V8_EXPORT_PRIVATE uint32_t Notify(Isolate* requester,
                                           DirectHandle<JSAtomicsCondition> cv,
                                           uint32_t count);
 
  static void CleanupMatchingAsyncWaiters(Isolate* isolate,
                                          WaiterQueueNode* node,
                                          DequeueMatcher matcher);
 
  enum {
    kMutexAsyncContextSlot = Context::MIN_CONTEXT_SLOTS,
    kConditionVariableAsyncContextSlot,
    kAsyncContextLength
  };
 
  TQ_OBJECT_CONSTRUCTORS(JSAtomicsCondition)
 
 private:
  friend class Factory;
 
  static void QueueWaiter(Isolate* requester,
                          DirectHandle<JSAtomicsCondition> cv,
                          WaiterQueueNode* waiter);
 
  using DequeueAction = std::function<uint32_t(WaiterQueueNode**)>;
  static uint32_t DequeueExplicit(Isolate* requester,
                                  DirectHandle<JSAtomicsCondition> cv,
                                  std::atomic<StateT>* state,
                                  const DequeueAction& dequeue_action);
};
 
}  // namespace internal
}  // namespace v8
 
#include "src/objects/object-macros-undef.h"
 
#endif  // V8_OBJECTS_JS_ATOMICS_SYNCHRONIZATION_H_