3288. atomic<T>::notify_one is unimplementable

Section: 32.5.6 [atomics.wait] Status: New Submitter: Anthony Williams Opened: 2019-09-11 Last modified: 2020-09-06

Priority: 2

View other active issues in [atomics.wait].

View all other issues in [atomics.wait].

View all issues with New status.

Discussion:

I am concerned by the wording around atomic<T>::wait()/atomic<T>::notify_one().

32.5.6 [atomics.wait] p4 requires that the thread that calls wait() observed a value X prior to the value Y which results from a store that happens-before the notify in order to be eligible to be unlocked.

I am not sure how to implement that.

atomic<int> a = 0;

T1: int ra=a, read 0
T1: a.wait(0)
T2: a=42
T3: int ra=a, read 42
T3: a.wait(42)
T2: a.notify_one()

The wording requires that T1 is eligible to be unlocked, but not T3, as there is not a write after the value read by T3 that happens-before the notify.

However, both T1 and T3 are waiting, so T3 may be woken by the OS. Waking T3 is allowed (wait() says it may wake spuriously), but waking T1 is currently required as it is the only thread "eligible to be unblocked".

This requires notify_one() to wake all waiters, which defeats the purpose.

I suspect we need to change 32.5.6 [atomics.wait] p4.

How about:

"A call to an atomic waiting operation W on an atomic object M is eligible to be unlocked by a call to an atomic notifying operation N on M if

• N does not happen-before W

• There are no side effects X and Y in the modification order of M such that N happens-before X, X precedes Y in the modification order of M and an atomic operation that observes the effects of Y happens-before W.

"

This would allow T3 to be woken in the preceding example, but prevent it being woken in the following case:

T1: int ra=a, read 0
T1: a.wait(0)
T2: a=42
T2: a.notify_one()
T2: a=69
T3: int ra=a, read 69
T3: a.wait(69)

[2020-07-17; Priority set to 2 in telecon]

Proposed resolution:

This wording is relative to N4830.

1. Modify 32.5.6 [atomics.wait] as indicated:

   -4- A call to an atomic waiting operation W on an atomic object M is eligible to be unblocked by a call to an atomic notifying operation N on M if there exist side effects X and Y on M such that:

   1. (4.1) — N does not happen before Wthe atomic waiting operation has blocked after observing the result of X,

   2. (4.2) — There are no side effects X andprecedes Y in the modification order of M, andsuch that N happens before X, X precedes Y in the modification order of M and an atomic operation that observes the effects of Y happens before W.

   3. (4.3) — Y happens before the call to the atomic notifying operation.