1507112 - Limit number of waiters for atomics.wait and notify to 2^32-1

Status: NEW

(Core :: JavaScript: WebAssembly, task, P3)

Description

[Lars T Hansen [:lth]]

On Nov 13 the CG meeting decided to adjust the semantics of atomics.wait and atomics.notify (née atomics.wake) in a backward-compatible manner, so that (a) the argument to notify is interpreted as an unsigned maximum number of waiters to notify and (b) there is an implementation limit on the number of waiters allowed on a given location so that we don't have to deal with what it means to wake "all" if the argument to notify doesn't go that high.  ISTR the limit is 2^32-1 but we'll figure that out eventually.  Anyway what happens is that if wait would create a situation where there would be too many waiters then we get to trap.  Being an implementation limit the trap is not part of the formal semantics, I think, which is why this is supposedly an improvement over the current situation where there's an explicit trap case in atomics.notify.

The limit will have to be shared by the JS implementation.  This was agreed among the implementers present; no agreement is required by TC39, probably.

I'm fairly sure it's not urgent to fix this, as our current implementation behaves as the new specification requires until we implement Atomics.asyncWait on the JS side.

Comment 1

[Lars T Hansen [:lth]]

https://github.com/WebAssembly/threads/pull/110

Comment 2

[Lars T Hansen [:lth]]

Note, this is not P5 because P5 means "won't really do this" but it doesn't block anything really.

Comment 3

[Ryan Hunt [:rhunt]]

Per [1] we're supposed to trap if the number of waiters is >= 2^32. I think the reason for this is because the wasm instructions are 32-bit unsigned and cannot express waking up more waiters than 2^32-1. This was not an issue before waitAsync because the number of waiters would be bound by the number of threads. Now with waitAsync, this case can actually happen.

[1] https://github.com/WebAssembly/threads/blob/main/proposals/threads/Overview.md#wait

Comment 4

[Yury Delendik (:yury)]

Need a second opinion on this matter from the JS team:

1. JS and Wasm share the same code here, so adding a limit in Wasm will affect JS in some way
2. I cannot find the similar constraint in JS world, e.g. at https://tc39.es/ecma262/#sec-dowait or https://tc39.es/ecma262/#sec-addwaiter -- I guess it is not an issue for instructions/operations reason
3. The current implementation and data structure is not capable to to maintain even a small fraction of 2^32 -- it is linked list.
4. Looks like Atomics.waitAsync is implemented, make this bug an urgent matter (based on the description)

Do we need to change the linked list data structure to something like a hashmap or b-tree?

Comment 5

[Iain Ireland [:iain]]

With regards to Atomics.waitAsync, and whether it makes this urgent: my understanding is that prior to Atomics.waitAsync the maximum number of waiters was bounded by the number of threads, which was never going to get anywhere close to 2^32, and now it's instead bound by the number of Promise objects we can allocate, which ... let's be honest, is also not going to get anywhere close to 2^32. A single PromiseObject is ... 56 bytes? (Shape pointer, slots pointer, elements pointer, and four slots.) So 2^32 promises is more than 200 GB of memory even before you start considering resolution functions and so on. That's going to hit other implementation limits first.

(Note also that the order in which waiters are inserted matters for the purposes of waking up the right ones, so a hashmap probably wouldn't work.)

Comment 6

[Yury Delendik (:yury)]

let's be honest, is also not going to get anywhere close to 2^32... That's going to hit other implementation limits first.

I thought along that line too. What will be right way to proceed here though? will closing this issue as WONTFIX be enough, or we want to add some asserts

the order in which waiters are inserted matters for the purposes of waking up the right ones

atomics_notify_impl just has a loop that just filters out based on byteOffset != waiter->offset(), so I was thinking hashmap + list, which may allow us to count waiters per location

Comment 7

[Iain Ireland [:iain]]

Note that we currently do some Clever Tricks involving the doubly linked list (it's possible for a timeout to resolve a waiter even after the associated SAB has been freed). I would hold off on modifying the data structures until we get some concrete evidence that perf is an issue.

In terms of the right way to proceed: if there's somewhere convenient to add a release-assert, that would be reasonable. I guess we don't necessarily have O(1) access to the number of waiters, though.