(memory model, wait/notify) Atomics.wait/notify non-SC behaviour, what is expected?

[conrad-watt]

Currently, as specified, it's possible for Atomics.wait/notify to interact in a non-sequentially-consistent way.

Thread 1	Thread 2
(a): Atomics.wait(tA, 0, 0)	(b): Atomics.store(tA, 0, 1)
	(c): var x = Atomics.notify(tA, 0, 1)

Given the following program, it's permitted to have the (operational) interleaving (b) -> (c) -> (a), but for the Atomics.wait of (a) to nevertheless read 0, therefore missing both the store and the notify, and getting stuck.

Is this intended? This feature doesn't seem to be formally specified in any other language, so there's no real "prior art". The closest analogy might be the C/C++11 try_lock operation, which is surprisingly weak. However this isn't a perfect match, and conceptually it seems like Atomics.* operations are expected to act in a reasonably sequential way.

[lars-t-hansen]

Were you thinking that there ought to be a rule that notify makes preceding writes visible in some way? That may have been implied / intended by the use of a critical section inside notify in the spec, but it's just as likely that I / we never thought about it.

[ljharb]

cc @syg

[jaag5678]

@lars-t-hansen Isn’t this the sort of situation that is avoided by enforcing a synchronize-with order as specified in the specs?

To quote from specs:

“For each pair (R, W) in execution.[[ReadsFrom]], (W, R) is in execution.[[SynchronizesWith]] if R.[[Order]] is "SeqCst", W.[[Order]] is "SeqCst", and R and W have equal ranges.“

[jaag5678]

@lars-t-hansen Or is it something enforced by the sequentially consistent atomics? Meaning the atomic store is visible immediately to all other agents?

[syg]

@conrad-watt What is meant by operational interleaving here?

[syg]

I'm guessing @conrad-watt doesn't mean memory-order because IIUC this is prohibited by memory-order. (If you assume a memory-order of (b) -> (c) -> (a) and (a) reads-from the init event writing 0, then the init event synchronizes-with (a), and SC atomics prohibits (b) from being memory-order after the init, which contradicts the assumption. Perhaps I missed something, Conrad's better at this than I am!)

Maybe you mean "the implementation happened to evaluate (b), (c), then (a)". I kinda take your point there. Like @lars-t-hansen noted, it is weird that Atomics.notify has no "force" in the memory model except when it synchronizes-with some Atomics.wait.

At the same time, this is almost a philosophical question. There isn't a notion of "operational interleaving" across agents beyond memory-order, is there? Is it equally odd to folks that (a') in the following modified example can read 0, with some out-of-band observation that the implementation evaluated (b), (c), then (a')?

Thread 1	Thread 2
(a'): Atomics.load(tA, 0)	(b): Atomics.store(tA, 0, 1)
	(c): var x = Atomics.notify(tA, 0, 1)

I'm amenable to giving notify some fence-like force, but I'm not sure what that actually means yet. What's the difference between doing that and saying memory-order is the allowed operational interleavings?

[conrad-watt]

Currently the wait queue implies a de-facto operational interleaving, because it's a synchronized data structure accessed by multiple threads. The interleaving on the wait queue is observable, as seen in my example above, where it must have been (c) -> (a) in order for (a) to get stuck (per the spec, which explicitly enforces this). However, currently this order is not required to be consistent with the memory-order, so you can justify the stuck execution by arbitrarily picking the memory-order (a) -> (b), even though this is inconsistent with what's observable from the wait queue. This is the cause of the behaviour I described.

Looking more closely at the spec, I agree with @lars-t-hansen that Enter/LeaveCriticalSection seem intended to enforce an ordering. In Java, entering a critical section synchronizes with all previous exits. But the JavaScript memory model currently doesn't have this built in.

So again, we have a weak fix and a strong fix possible. The weak fix is to make the critical section interleaving imply memory-order. The strong fix is to make the critical section interleaving imply synchronizes-with. Both would fix my previous example, but they can be distinguished with the following.

Thread 1	Thread 2	Thread 3
(a): Atomics.store(tA, 0, 1)	(c): tA[1] = 1	(f): tA[2] = 1
(b): var x = Atomics.notify(tA, 0, 2)	(d): Atomics.wait(tA, 0, 0)	(g): Atomics.wait(tA, 0, 0)
	(e): var y = tA[2]	(h): var z = tA[1]

Consider the interleaving on the wait queue where (b) wakes both (d) and (g) (i.e., x=2). In the strong fix, it is guaranteed that y=1, z=1. In the weak fix, y=0, z=0 is allowed.

As I said, Java specifies the strong fix, and it would also be my preference if we can get away with it. Implementations doing some optimisation like busy-waiting for a period would need to make sure there are the right barriers in place.

The strong fix would also subsume the previous alteration we made wrt a waker synchronizing-with its wakee, which is certainly necessary either way.

---

@jaag5678 the section you've quoted shows why the ordering is currently not there. You currently only get synchronization by having a successful reading or notifying pair. The "missed" notification of my example currently implies no ordering in the memory model.

[lars-t-hansen]

IMO: Certainly for JS the strong fix seems appropriate - it reduces surprises and it should be affordable. I tend to feel the same way about wasm, so that shouldn't stand in the way either.

The thing about fences for fast-path busy-waiting may be worth calling out in an implementation note around about the critical section abstractions (24.4.1.4, 24.4.1.5).

[conrad-watt]

There's actually a much better example that distinguishes the strong vs weak fixes.

Thread 1	Thread 2
(a): Atomics.wait(tA, 0, 0)	(b): ta[0] = 1
	(c): var x = Atomics.notify(tA, 0, 1)

This is just my original example with (b)'s store changed to a non-atomic.

The weak fix guarantees that my original example terminates, but still allows this weakened variant to get stuck.

The strong fix guarantees that both variants will terminate. Personally I think this makes my weak fix look much less reasonable.

[jaag5678]

@conrad-watt @lars-t-hansen I was of the understanding that Atomics mimic the Sequentially Consistent type of events. In that sense I assumed that a sequentially consistent action is immediately visible to all agents and maintains an intra-agent memory coherence. However, the example mentioned by you earlier clearly shows that Atomics do not show that behavior. (the atomic store is not visible immediately)

As a student and researcher I want to know where my misunderstanding lies. Is it in my understanding of the specs of Sequentially consistent atomics or is it the implementation of Atomics.

[conrad-watt]

I assumed that a sequentially consistent action is immediately visible to all agents and maintains an intra-agent memory coherence.

You've described a high-level intuition about a property which arguably should be true of the memory model. Your misunderstanding is of the specification, since the memory model does not provide this property currently, although we will hopefully be able to fix that.

The only way to discover issues like this is to carefully read the specification, and try to match your intuition about what the model should do with what the rules actually say the model does. If you're interested in relaxed memory, I'd encourage you to get in touch with me by email (on my profile).

[syg]

Currently the wait queue implies a de-facto operational interleaving, because it's a synchronized data structure accessed by multiple threads.

Ah ha, okay, then this is very much a practical question, thanks for setting me right here. I strongly agree that the strong fix is the better alternative here.

The "missed" notification of my example currently implies no ordering in the memory model.

This succinctly captures the problem. This bug is the other half of the one @conrad-watt found in #1127: all kinds of astonishments are caused by failing to capture wait/notify pairs as synchronizes-with. #1127 fixed it for the wait/notify pairs that happened to have woken up, and we need a similar fix for wait/notify pairs that happened to have not woken up.

[ljharb]

Seems like perhaps a needs consensus PR is in order? It’d be great to get it on the next meeting’s agenda if so.

[syg]

@ljharb Sure. While the semantics should be uncontroversial, it'd be good to get some implementation clarification:

• V8 uses SRWLOCK on Windows and pthread_mutex_t on lock the waiter list, and so should already be synchronizing on wait/notify.
• SpiderMonkey seems to do some kind of relaxed busy-waiting on macOS. @lars-t-hansen would this spec change require implementation changes?
• JSC maps wait/notify onto its ParkingLot abstraction. @kmiller68 are parking lot lock/unlocks already synchronizing? I would imagine so.

[lars-t-hansen]

@syg, thanks for asking. Some man pages say the macOS spinlock functions synchronize properly: https://developer.apple.com/library/archive/documentation/System/Conceptual/ManPages_iPhoneOS/man3/OSSpinLockUnlock.3.html. Other pages say these functions are deprecated. I'll take it up with The Proper Authorities.

[kmiller68]

To clarify, "synchronizes-with" is equivalent to acquire/release where every thread agrees on the state of writes before the atomic and reads after? And "memory-order" is equivalent to a release/consume on the atomic variable where every thread only agree on the state of the atomic in question (and any dependencies)? Sorry, I've forgotten the exact meaning of the terminology and I want to make sure I'm on the same page...

@syg Yeah, our ParkingLot uses a std::atomic::load with the sequentially consistent ordering flag. If I understand correctly, this should be stronger than the expectations of this proposal.

@lars-t-hansen Looking at the source of OSSpinLockLock/Unlock it looks like (TM; no promises) it's using acquire/release semantics so I think it should be sufficient for the strong proposal.

[conrad-watt]

To clarify, "synchronizes-with" is equivalent to acquire/release where every thread agrees on the state of writes before the atomic and reads after? And "memory-order" is equivalent to a release/consume on the atomic variable where every thread only agree on the state of the atomic in question (and any dependencies)? Sorry, I've forgotten the exact meaning of the terminology and I want to make sure I'm on the same page...

Yes, synchronizes-with is like acquire/release.

memory-order is more like JS's version of C++'s sc ordering. So the weak fix is saying that the sc ordering of atomics has to be consistent with the (implied) order of "wait queue accesses", but doesn't constrain non-atomics. The strong fix also implies this.

[lars-t-hansen]

Firefox uses pthread locks on macOS for our mutexes, but with a little busy-waiting to improve performance. But judging from the code we should be fine with a spec change, no code changes needed.