js-atomics-synchronization.h | Explore in Territory

// 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

WaiterQueueLockGuard;
WaiterQueueNode;
LockAsyncWaiterQueueNode;
WaitAsyncWaiterQueueNode;

// 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> { … };

// 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> { … };

// 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> { … };

}  // namespace internal
}  // namespace v8

#include "src/objects/object-macros-undef.h"

#endif  // V8_OBJECTS_JS_ATOMICS_SYNCHRONIZATION_H_
chromium/v8/src/objects/js-atomics-synchronization.h
