Stage 2 Draft / June 26, 2019

Atomics.waitAsync

We provide a new API, Atomics.waitAsync, that an agent can use to wait on a shared memory location (to later be awoken by some agent calling Atomics.notify on that location) without waiting synchronously (ie, without blocking). Notably this API is useful in agents whose [[CanBlock]] attribute is false, such as the main thread of a web browser document, but the API is not restricted to such agents.

The API is promise-based. Very high performance is not a requirement, but good performance is desirable.

1Semantics

To support Atomics.waitAsync, the WaiterList semantic object is split into two semantic objects.

A ClusterWaiterList is a semantic object that contains an ordered List of agent signifiers of agents that are waiting on a location (block, i) in shared memory; block is a Shared Data Block and i a byte offset into the memory of block. This list is agent-independent and, like the current WaiterList semantic object, is shared by all agents in an agent cluster.

An AsyncWaitList is a List of Records that have a PromiseCapability Record and an alarm id. Each Record encapsulates the result of a call to Atomics.waitAsync, and null denotes a call to Atomics.wait. This list is per-agent.

Additionally, Agent Records tracks whether the agent is currently blocked.

Conceptually, agents that call either Atomics.wait or Atomics.waitAsync are appended to ClusterWaiterList. If the call was to Atomics.wait, the agent is marked as blocked. If the call was to Atomics.waitAsync, the result PromiseCapability Record is appended to that agent's AsyncWaitList.

This enables two design goals:

  1. Waiting agents are notified in FIFO order for fairness.
  2. Asynchronous waits in one agent are notified in FIFO order, while synchronous waits are notified before any asynchronous wait. This is because resolving the Promise result of a call to Atomics.waitAsync does no meaningful computation if the agent is in a blocking wait.

Agent Record is modified as follows.

Table 1: Agent Record Fields
Field Name Value Meaning
[[LittleEndian]] Boolean The default value computed for the isLittleEndian parameter when it is needed by the algorithms GetValueFromBuffer and SetValueInBuffer. The choice is implementation-dependent and should be the alternative that is most efficient for the implementation. Once the value has been observed it cannot change.
[[CanBlock]] Boolean Determines whether the agent can block or not.
[[Blocked]] Boolean Determines if the agent is blocked by Atomics.wait. If [[CanBlock]] is false, this value is always false.
[[Signifier]] Any globally-unique value Uniquely identifies the agent within its agent cluster.
[[IsLockFree1]] Boolean true if atomic operations on one-byte values are lock-free, false otherwise.
[[IsLockFree2]] Boolean true if atomic operations on two-byte values are lock-free, false otherwise.
[[CandidateExecution]] A candidate execution Record See the memory model.
[[AsyncWaitList]] An AsyncWaitList A List of Records denoting calls to Atomics.waitAsync.

1.1HostResolveInAgent ( W, promiseCapability, resolution)

This is a new section.

HostResolveInAgent is an implementation-defined abstract operation that takes three arguments, an agent signifier W, a PromiseCapability Record promiseCapability, and a value resolution. The host's responsibility is to resolve the promiseCapability in the agent signified by W with resolution in finite time. The host may delay resolving the promiseCapability in W, e.g. for resource management reasons, but the promise must eventually be resolved.

1.2GetClusterWaiterList ( block, i )

A ClusterWaiterList is a semantic object that contains an ordered list of agent signifiers of those agents that are waiting on a location (block, i) in shared memory; block is a Shared Data Block and i a byte offset into the memory of block.

There can be multiple entries in a ClusterWaiterList with the same agent signifier.

The ClusterWaiterList has an attached alarm set, a set of truthy values. This set is manipulated only when the agent manipulating it is in the critical section for the ClusterWaiterList.

The agent cluster has a store of ClusterWaiterList objects; the store is indexed by (block, i). WaiterLists are agent-independent: a lookup in the store of ClusterWaiterLists by (block, i) will result in the same ClusterWaiterList object in any agent in the agent cluster.

Operations on a ClusterWaiterList -- adding and removing waiting agents, traversing the list of agents, suspending and notifying agents on the list, adding and removing alarms -- may only be performed by agents that have entered the ClusterWaiterList's critical section.

The abstract operation GetClusterWaiterList takes two arguments, a Shared Data Block block and a nonnegative integer i. It performs the following steps:

  1. Assert: block is a Shared Data Block.
  2. Assert: i and i + 3 are valid byte offsets within the memory of block.
  3. Assert: i is divisible by 4.
  4. Return the ClusterWaiterList that is referenced by the pair (block, i).

1.3Alarm Functions

This is a new section.

An alarm function is an anonymous built-in function that has [[WaiterList]], [[Waiter]], [[Kind]], and [[Result]] internal slots.

When an alarm function is called with no arguments, the following steps are taken:

  1. Let F be the active function object.
  2. Assert: F has a [[WaiterList]] internal slot whose value is a ClusterWaiterList.
  3. Assert: F has a [[Waiter]] internal slot whose value is an agent signifier.
  4. Assert: F has a [[Kind]] internal slot whose value is a String.
  5. Let WL be F.[[WaiterList]].
  6. Let W be F.[[Waiter]].
  7. Let AR be the Agent Record whose [[Signifier]] field is W.
  8. If F.[[Kind]] is "sync", then
    1. Set F.[[Result]].[[Value]] to the String "timed-out".
  9. Perform EnterCriticalSection(WL).
  10. Perform RemoveWaiter(WL, W).
  11. If F.[[Result]] is "async", then
    1. Let asyncRecord be F.[[Result]].
    2. Assert: asyncRecord is in AR.[[AsyncWaitList]].
    3. Remove asyncRecord from AR.[[AsyncWaitList]].
  12. Perform NotifyWaiter(WL, W, asyncRecord, "timed-out").
  13. Perform LeaveCriticalSection(WL).

Change this function not to take a timeout argument. Timeouts are now handled in the caller. (Not intended as a normative change.)

1.4Suspend ( WL, W, timeout )

The abstract operation Suspend takes threetwo arguments, a ClusterWaiterList WL,and an agent signifier W, and a nonnegative, non-NaN Number timeout. It performs the following steps:

  1. Assert: The calling agent is in the critical section for WL.
  2. Assert: W is equal to AgentSignifier().
  3. Assert: W is on the list of waiters in WL.
  4. Assert: AgentCanSuspend() is true.
  5. Perform LeaveCriticalSection(WL) and suspend W for up to timeout milliseconds, performing the combined operation in such a way that a notification that arrives after the critical section is exited but before the suspension takes effect is not lost. W can notify either because the timeout expired or because it wasbe notified explicitly by another agent calling NotifyWaiter(WL, W, ...), and not for any other reasons at all.
  6. Perform EnterCriticalSection(WL).
  7. Set the [[Blocked]] field of Agent Record whose [[Signifier]] field is W to true.
  8. If W was notified explicitly by another agent calling NotifyWaiter(WL, W), return true.
  9. Return false.

1.5NotifyWaiter ( WL, W, value )

The abstract operation NotifyWaiter takes twothree arguments, a ClusterWaiterList WL and, an agent signifier W, and a String value. It performs the following steps:

  1. Assert: The calling agent is in the critical section for WL.
  2. Assert: W is on the list of waiters in WL.
  3. Assert: value is either the String "ok" or the String "timed-out".
  4. Let AR be the Agent Record whose [[Signifier]] field is W.
  5. Let execution be the [[CandidateExecution]] field of the surrounding agent's Agent Record.
  6. Let eventsRecord be the Agent Events Record in execution.[[EventsRecords]] whose [[AgentSignifier]] is AgentSignifier().
  7. Let agentSynchronizesWith be eventsRecord.[[AgentSynchronizesWith]].
  8. Let notifierEventList be eventsRecord.[[EventList]].
  9. Let waiterEventList be the [[EventList]] field of the element in execution.[[EventsRecords]] whose [[AgentSignifier]] is W.
  10. Let notifyEvent and waitEvent be new Synchronize events.
  11. Append notifyEvent to notifierEventList.
  12. Append waitEvent to waiterEventList.
  13. Append (notifyEvent, waitEvent) to agentSynchronizesWith.
  14. Notify the agent W.If AR.[[Blocked]] is true, then
    1. Set AR.[[Blocked]] to false.
    2. Notify the agent W.
  15. Else,
    1. Assert: AR.[[AsyncWaitList]] is not an empty List.
    2. Let asyncRecord be the first element of AR.[[AsyncWaitList]].
    3. Remove the first element of AR.[[AsyncWaitList]].
    4. Perform HostResolveInAgent(W, asyncRecord.[[PromiseCapability]], value)
    5. NOTE: An agent must not access another agent's promise capability in any capacity beyond passing it to the host.
    6. If asyncRecord.[[Alarm]] is truthy, then
      1. Perform CancelAlarm(WL, asyncRecord.[[Alarm]]).
Note

The embedding may delay notifying W, e.g. for resource management reasons, but W must eventually be notified in order to guarantee forward progress.

1.6AddAlarm( WL, alarmFn, timeout )

This is a new abstract operation.

The abstract operation AddAlarm takes three arguments, a ClusterWaiterList WL, a thunk alarmFn, and a nonnegative finite number timeout. It performs the following steps:

  1. Assert: The calling agent is in the critical section for WL.
  2. Let alarm be a truthy value that is not in WL's alarm set.
  3. Add alarm to WL's alarm set.
  4. After timeout milliseconds has passed, perform the following actions concurrently:
    1. Perform EnterCriticalSection(WL).
    2. If CancelAlarm(WL, alarm) is true, then
      1. Perform ! Call(alarmFn, undefined, « »).
    3. Perform LeaveCriticalSection(WL).
    4. NOTE: alarmFn is now dead.
  5. Return alarm.

1.7CancelAlarm( WL, alarm )

This is a new abstraction operation.

The abstract operation CancelAlarm takes two arguments, a ClusterWaiterList WL, and a truthy value alarm. It performs the following steps:

  1. Assert: The calling agent is in the critical section for WL.
  2. Assert: alarm is a truthy value.
  3. If alarm is in WL's alarm set, then
    1. Remove alarm from WL's alarm set.
    2. Return true.
    3. NOTE: No alarm that subsequently triggers for alarm (in the concurrent thread referenced in AddAlarm) will have any effect. If not called from AddAlarm, the thunk associated with alarm is now dead and can be reclaimed; any scheduled timeout associated with alarm can be canceled.
  4. Else return false.

1.8Atomics.wait ( typedArray, index, value, timeout )

Atomics.wait puts the calling agent in a wait queue and puts it to sleep until it is notified or the sleep times out. The following steps are taken:

  1. Let buffer be ? ValidateSharedIntegerTypedArray(typedArray, true).
  2. Let i be ? ValidateAtomicAccess(typedArray, index).
  3. Let v be ? ToInt32(value).
  4. Let q be ? ToNumber(timeout).
  5. If q is NaN, let t be +∞, else let t be max(q, 0).
  6. Let B be AgentCanSuspend().
  7. If B is false, throw a TypeError exception.
  8. Let block be buffer.[[ArrayBufferData]].
  9. Let offset be typedArray.[[ByteOffset]].
  10. Let indexedPosition be (i × 4) + offset.
  11. Let WL be GetClusterWaiterList(block, indexedPosition).
  12. Perform EnterCriticalSection(WL).
  13. Let w be ! AtomicLoad(typedArray, i).
  14. If v is not equal to w, then
    1. Perform LeaveCriticalSection(WL).
    2. Return the String "not-equal".
  15. Let W be AgentSignifier().
  16. Perform AddWaiter(WL, W).
  17. Let notified be Suspend(WL, W, t).
  18. If notified is true, then
    1. Assert: W is not on the list of waiters in WL.
  19. Else,
    1. Perform RemoveWaiter(WL, W).
  20. Let syncResult be a new Record { [[Value]]: "ok" }.
  21. Let alarm be false.
  22. If t is finite, then
    1. Let stepsAlarm be the algorithm steps defined in Alarm Functions (1.3).
    2. Let alarmFn be CreateBuiltinFunction(stepsAlarm, « [[WaiterList]], [[Waiter]], [[Kind]], [[Result]] »).
    3. Set alarmFn.[[WaiterList]] to WL.
    4. Set alarmFn.[[Waiter]] to W.
    5. Set alarmFn.[[Kind]] to the String "sync".
    6. Set alarmFn.[[Result]] to syncResult.
    7. Set alarm to AddAlarm(WL, alarmFn, t).
  23. Perform AddWaiter(WL, W).
  24. Perform Suspend(WL, W).
  25. If syncResult.[[Value]] is "ok" and alarm is a truthy value, then
    1. Perform CancelAlarm(WL, alarm).
  26. Perform LeaveCriticalSection(WL).
  27. If notified is true, return the String "ok".
  28. Return the String "timed-out"syncResult.[[Value]].

1.9Atomics.waitAsync ( typedArray, index, value, timeout )

This is a new method.

Atomics.waitAsync returns a Promise that is resolved when the calling agent is notified or the sleep times out. The following steps are taken:

  1. Let buffer be ? ValidateSharedIntegerTypedArray(typedArray, true).
  2. Let i be ? ValidateAtomicAccess(typedArray, index).
  3. Let v be ? ToInt32(value).
  4. Let q be ? ToNumber(timeout).
  5. If q is NaN, let t be +∞, else let t be max(q, 0).
  6. Let B be AgentCanSuspend().
  7. If B is false, throw a TypeError exception.
  8. Let block be buffer.[[ArrayBufferData]].
  9. Let offset be typedArray.[[ByteOffset]].
  10. Let indexedPosition be (i × 4) + offset.
  11. Let WL be GetClusterWaiterList(block, indexedPosition).
  12. Let promiseCapability be ! NewPromiseCapability(%Promise%).
  13. Perform EnterCriticalSection(WL).
  14. Let w be ! AtomicLoad(typedArray, i).
  15. If v is not equal to w, then
    1. Perform LeaveCriticalSection(WL).
    2. Perform ! Call(capability.[[Resolve]], undefined, « "not-equal" »).
    3. Return promiseCapability.[[Promise]].
  16. Let W be AgentSignifier().
  17. Let AR be the Agent Record whose [[Signifier]] field is W.
  18. Let alarm be false.
  19. Let asyncRecord be { [[PromiseCapability]]: promiseCapability, [[Alarm]]: alarm }.
  20. Let t is finite, then
    1. Let stepsAlarm be the algorithm steps defined in Alarm Functions (1.3).
    2. Let alarmFn be CreateBuiltinFunction(stepsAlarm, « [[WaiterList]], [[Waiter]], [[Kind]], [[Result]] »).
    3. Set alarmFn.[[WaiterList]] to WL.
    4. Set alarmFn.[[Waiter]] to W.
    5. Set alarmFn.[[Kind]] to the String "async".
    6. Set alarmFn.[[Result]] to asyncRecord.
    7. Set alarm to AddAlarm(WL, alarmFn, t).
    8. Set asyncRecord.[[Alarm]] to alarm.
  21. Perform AddWaiter(WL, W).
  22. Append asyncRecord as the last element of the AR.[[AsyncWaitList]].
  23. Perform LeaveCriticalSection(WL).
  24. Return promiseCapability.[[Promise]].

1.10Atomics.notify ( typedArray, index, count )

Atomics.notify notifies some agents that are sleeping in the wait queue. The following steps are taken:

  1. Let buffer be ? ValidateSharedIntegerTypedArray(typedArray, true).
  2. Let i be ? ValidateAtomicAccess(typedArray, index).
  3. If count is undefined, let c be +∞.
  4. Else,
    1. Let intCount be ? ToInteger(count).
    2. Let c be max(intCount, 0).
  5. Let block be buffer.[[ArrayBufferData]].
  6. Let offset be typedArray.[[ByteOffset]].
  7. Let indexedPosition be (i × 4) + offset.
  8. Let WL be GetClusterWaiterList(block, indexedPosition).
  9. Let n be 0.
  10. Perform EnterCriticalSection(WL).
  11. Let S be RemoveWaiters(WL, c).
  12. Repeat, while S is not an empty List,
    1. Let W be the first agent in S.
    2. Remove W from the front of S.
    3. Perform NotifyWaiter(WL, W, "ok").
    4. Add 1 to n.
  13. Perform LeaveCriticalSection(WL).
  14. Return n.