Hacker News Reader

Comment by atq2119 | Hacker News Reader

This stuff is so subtle.

It's not actually clear to me right now what part of the memory model would prevent the release store of an earlier unlock from being moved past the acquire load of a later lock.

Except that you wouldn't move it past a single acquire load, you'd potentially move it past an infinite number of acquire loads, and maybe then you run into formal language about forward progress?

There are similarly fun questions around hoisting an acquire load out of an otherwise empty loop...

View on HN

> what part of the memory model would prevent the release store of an earlier unlock from being moved past the acquire load of a later lock.

Are you talking about different locks? In that case, yes, reordering can happen.

If it's about the same lock, then this can't happen because it would change the semantics of the code (you can't aquire the lock without releasing it first).

That reordering would be bad even with different locks because it can introduce deadlocks, as somebody has pointed out.

There must be some formal semantics reason which forbids it, and I think the reason boils down to the lock not being a single acquire load but instead a loop of acquire loads.

Unlock followed by lock is a store that is followed by a potentially infinite loop. If you move the store past the loop, and the loop happens to be or becomes infinite, then the effect of the store will never become visible, and that is an incorrect program transform because it'd be as-if you simply erased the store.

So you can probably move the store past any finite number of loads, but not past a potentially infinite loop.

Yes this re-ordering can cause a deadlock. But it's not an allowed optimization to change a non-deadlocking program into a potentially deadlocking program, so this reordering can not happen. (http://eel.is/c++draft/intro.multithread#intro.progress-7)

You can still get this deadlock if you actually write the code like that: lock1.lock(); lock2.unlock();

"aquire" means that the compiler can't move any reads/writes up before the load. "release" means that it can't move any reads/writes down after the store.

The compiler can move a release store of variable A past an aquire load of variable B because it violates neither constraints.

The opposite is not true: it can't move an aquire load of variable A past a release store of variable B because it violates both contraints.

For a lock, aquire/release semantics are sufficient because its only job is to protect some shared piece of data, it doesn't care about other locks.

> reordering would be bad even with different locks because it can introduce deadlocks, as somebody has pointed out.

Do you have an example of such a deadlock? Maybe it's best to work with some actual code.

Example:

Thread 1 does A.lock, A.unlock, B.lock, B.unlock

Thread 2 does B.lock, B.unlock, A.lock, A.unlock

That's fine, but swap the middle pair of unlock followed by lock on both threads and you have a standard deadlock based on different lock nestings.

And to reiterate from my previous comment, I do think that transform is or should be forbidden. That's not for synchronization reasons per se, but because the transform can change the set of externally visible side effects of the code. This argument requires that a store with release semantics is considered to be an externally visible side effect. That makes intuitive sense to me, though I don't remember what e.g. the C++ standard actually says about that.

Although pure aquire-release semantics would allow such reordering, it also didn't feel quite right to me, either. Fortunately, someone asked the exact same question on Stack Overflow and got a good answer: https://stackoverflow.com/a/61300584

Looks like you've been on the right track with regard to possible infinite loops.

Isn't this case discussed at the end of the article?

> C++ committee member Tony Van Eerd commented on reddit that with std::memory_order_acquire and two locks a and b; calls to a.unlock(); b.lock() and lock() for different locks could be reordered to b.lock(); a.unlock(); and introduce a potential deadlock. I don’t think that’s true. Reading section 6.9.2.1 Data races (paragraph 9) of the C++ standard] no loads or stores can bed moved into or out from between a load-acquire and store-release pair.

> http://eel.is/c++draft/intro.races#9

It's true that the compiler can't move reads/write out from between a load-acquire and store-release pair, but in my understanding it can certainly move reads/writes into the pair. Or can someone point me to the exact section of the standard where this is prohibited?

I think my stack overflow link above gives a more satisfying explanation on why the example can't deadlock.

I now think it's actually this part of the standard that prevents it: http://eel.is/c++draft/intro.multithread#intro.progress-7

Basically a compiler can not optimize a non-deadlocking program into a potentially deadlocking one.

Yes, it's the same example, but the answer appears to be subtly different. Acquire and release are only "one-way barriers". Consider the link in the sibling comment by spacechild1.

Reply on news.ycombinator.com