GrowableSharedArrayBuffer.prototype.grow maybe not handling races correctly

[marjakh]

Example: T1 and T2 both have GSABs which share the same backing memory, current length 10.

T1 does:
gsab.grow(20);

T2 does:
gsab.grow(40);

Looks like this could happen:
T1 executes steps 1 - 5 of GrowableSharedArrayBuffer.prototype.grow. (Now we're past the point of throwing because the buffer would shrink.)

T2 executes GrowableSharedArrayBuffer.prototype.grow; 40 is written in the memory as the new byte length.

T2 goes on and does other stuff with the GSAB.

T1 executes the rest of GrowableSharedArrayBuffer.prototype.grow. 20 is written in the memory as the new byte length.

-> From T2's point of view, the buffer has now shrunk.

Potential fix:

Structure the spec like the implementation is structured: read currentByteLength in a loop, and each iteration of the loop does the "throw if shrinking" check.

(Btw, reading currentByteLength seems to be missing from the spec too.)

[conrad-watt]

Yes, the way this is currently done in the Wasm spec at the operational level is

1. non-deterministically pick a value to represent the current length
2. if current+growth > max, or if some other OOM occurs non-deterministically, the growth fails and no event is emitted (max is known thread-locally)
3. otherwise, emit an RMW event reading the current length and writing current+growth

The axiomatic part of the semantics ensures that all the RMWs are totally ordered, so no growths are "lost". I think this is similar in spirit to our previous discussion about the specification of Atomics.compareExchange here.

EDIT: my original comment stated that an SC read of the length is emitted if the growth fails, but our current spec is actually weaker than this, since we don't observably distinguish between non-deterministic OOM errors and growth-over-max errors.

EDIT2: also, if I'm reading the JS spec correctly, there needs to be a data write of 0s to the new memory, so that subsequent reads have initial values they can take.

[syg]

Another great catch @marjakh. Thanks for the info on the wasm side too, @conrad-watt.

1. non-deterministically pick a value to represent the current length

This is how it works in the JS spec and this spec draft as well. I think the bug is that in step 9 of https://tc39.es/proposal-resizablearraybuffer/#sec-growablesharedarraybuffer.prototype.grow I do use a != check instead of < check for newByteLength < currentByteLength, and the OOM check should probably be checked down there. The right fix is to use an RMW as originally suggested.

In any case I don't think a loop is needed.

EDIT2: also, if I'm reading the JS spec correctly, there needs to be a data write of 0s to the new memory, so that subsequent reads have initial values they can take.

Good catch, this is right.

[conrad-watt]

@syg in the spec you linked, line 8 appears to be performing an SC read of the buffer length, while line 9.c performs a separate SC write. If the read and write are not performed as a single RMW, it's possible to "lose" growths (i.e. two concurrent growths read the same value, and both race to write back their "new length"). I think this is what @marjakh is describing.

[syg]

Ah duh, absolutely right on the need for RMW.

[syg]

EDIT2: also, if I'm reading the JS spec correctly, there needs to be a data write of 0s to the new memory, so that subsequent reads have initial values they can take.

From the spec's perspective, this isn't necessary because the spec fiction is that a shared data block of size maxLength is allocated up front, and since a SAB can never shrink, any new memory is already zeroed.

In implementations, I'm actually not too sure how this should be done. Does it basically require zero-fill-on-demand pages? You can't speculatively zero bytes ahead of time, in case while you're doing that another grow of a smaller increment succeeds, and you end up clobbering new writes. You can't zero after atomically updating the length, because that might race with reads. How does Wasm deal with this?

[conrad-watt]

From the spec's perspective, this isn't necessary because the spec fiction is that a shared data block of size maxLength is allocated up front, and since a SAB can never shrink, any new memory is already zeroed.

Ah I see, that works!

In implementations, I'm actually not too sure how this should be done. Does it basically require zero-fill-on-demand pages? You can't speculatively zero bytes ahead of time, in case while you're doing that another grow of a smaller increment succeeds, and you end up clobbering new writes. You can't zero after atomically updating the length, because that might race with reads. How does Wasm deal with this?

My understanding is that because engines pretty much all implement shared memories in place, all of the zeroed pages are allocated upfront, and some bounds-checking implementation (either explicit checks or trap handler) controls which pages are accessible without provoking OOB errors at the Wasm level. So the formal model you sketched above actually corresponds pretty closely to reality.

[codehag]

cc @jandem