On Mon, 18 Jul 2022, Andrey Semashev via Std-Discussion wrote:

> On 7/18/22 17:48, Nate Eldredge via Std-Discussion wrote:

>> Suppose that `b.wait(false)` starts while the value of `b` is still
>> `false`, and so it blocks.  When `b.notify_one()` executes, the main
>> thread will unblock and test the value of `b`.  However, I cannot find
>> anything to clearly imply that the store of `true` to `b` will be
>> visible by then.  If the main thread loads the old value `false`, it
>> will block again, and potentially never wake up (unless there is a
>> spurious unblock).
>
> What you're saying is only possible if notify_one is observed before the
> store by the main thread. And that is not possible as the store is
> sequenced-before the notify. Consequently, the store happens-before the
> notify:
>
> http://eel.is/c++draft/intro.multithread#intro.races-10

I agree that the store happens-before notify_one() by sequencing, but I
don't see how that helps by itself. What we need is for the store in thr1
to happen-before the load inside b.wait() in the main thread. Since these
are in separate threads, sequencing alone cannot get us that relation.

By my reading of [data.races p7-12], if we disregard consume operations,
the only way to get a happens-before between two evaluations in different
threads is to have a synchronizes-with somewhere in the chain. The
example program doesn't have any synchronizes-with relations that I can
find, so I don't see how we can ever establish the thr1 store to
happen-before the main thread load.

In general, the fact that one operation happens-before another does not
imply that those operations will be observed in the same order by another
thread. For instance, when a thread does two relaxed stores in sequence,
the one certainly happens-before the other, but they can be observed out
of order by loads in another thread. Indeed, that is precisely the
problem with the "perverse" implementation I suggested. If Thread 1 does

b.store(true, std::memory_order_relaxed);
__counter.fetch_add(1, std::memory_order_relaxed);

and Thread 2 does

while (__counter.load(std::memory_order_relaxed) == 0) {
   // spin
}
res = b.load(std::memory_order_relaxed);

then it's certainly correct to say that b.store() happens-before
__counter.fetch_add(). But res can end up with the value false, because
it is not the case that b.store() happens-before b.load().

> Synchronizes-with is a different relation that describes memory ordering
> wrt. other objects than the atomic. Notifying operations don't do that
> and don't need to do that because the preceding store does that. I.e. it
> is the store that may synchronize-with the load performed by the waiting
> operation.

Well, I think it's analogous to the way that `std::thread t(fn)`
synchronizes-with the start of the evaluation of `fn` in the new thread
(http://eel.is/c++draft/thread.thread.constr#6). That is how, when we do
something like

std::atomic<int> x;
void fn() {
     std::cout << x.load(std::memory_order_relaxed) << std::endl;
}
int main() {
     x.store(42, std::memory_order_relaxed);
     std::thread t(fn);
     t.join();
}

we are guaranteed to have the value 42 printed. x.store happens-before
the thread constructor (sequencing), which happens-before the start of
fn() (synchronizes-with), which happens-before x.load() (sequencing), and
so by WR coherency the value 42 must be loaded.

I think that notify/wait needs something similar to guarantee the desired
deadlock-free behavior, and I don't see it in the current standard. There
is nothing to play the role of the synchronizes-with step.

-- 
Nate Eldredge
nate_at_[hidden]