5 ms·

Nope, std::memory_order_acquire is perfectly fine here. Just because an atomic operation involves a store doesn't necessarily mean you always need/want to synch

Nope, std::memory_order_acquire is perfectly fine here. Just because an atomic operation involves a store doesn't necessarily mean you always need/want to synchronize with that store. In this case, we only need to make sure that subsequent code is not reordered before the atomic load, hence the aquire semantics.

tialaramex 5y ago
Thanks, I guess? I spent a whole lot of time staring at this, and I was eventually able to convince myself that you're correct, there isn't any way for this to actually go wrong. In the case where you're storing a different value than was already there, you just took the lock and even in relaxed ordering that is in fact an atomic operation, nobody else has the lock. In every other case who cares if you release, you didn't change anything anyway. The unlock() will release, and so anybody who subsequently acquires the lock will see the changes made under the lock. Even after convincing myself this analysis is correct, I'm still scared that it's wrong, anyway. After all my previous analysis was wrong :/
- atq2119 5y ago
  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...
  - spacechild1 5y ago
    > 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).
    - atq2119 5y ago
      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.
      - spacechild1 5y ago
        "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.
        atq2119 5y ago
        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.
- spacechild1 5y ago
  Your reasoning is correct. Also, if it makes you sleep better :-), here's the boost implementation of a spinlock: https://github.com/boostorg/sync/blob/dfdf317f63d26fb40c703b8d2dc6bbf99c5ca1db/include/boost/sync/detail/mutexes/spin_mutex.hpp#L69 https://github.com/boostorg/sync/blob/dfdf317f63d26fb40c703b... It has been written by an expert in lockfree programming (Tim Blechmann)
  - albertzeyer 5y ago
    I wonder, there was this change/fix: https://github.com/boostorg/sync/commit/1b5aaa4a0b7ef4fad2a46336a201081740e1c624#diff-3808384c88a5623a406c6b8073b76294dba88f784b17da9e3316d75295fcde6a https://github.com/boostorg/sync/commit/1b5aaa4a0b7ef4fad2a4...
    - spacechild1 5y ago
      The title "Corrected memory order in some cases" is a bit misleading because the original code was correct. The commit just relaxes some unnecessarily strict memory orderings (to improve performance on platforms with weak memory models). BTW, the spinlock implementation is not affected.

tialaramex 5y ago

Thanks, I guess? I spent a whole lot of time staring at this, and I was eventually able to convince myself that you're correct, there isn't any way for this to actually go wrong. In the case where you're storing a different value than was already there, you just took the lock and even in relaxed ordering that is in fact an atomic operation, nobody else has the lock. In every other case who cares if you release, you didn't change anything anyway. The unlock() will release, and so anybody who subsequently acquires the lock will see the changes made under the lock. Even after convincing myself this analysis is correct, I'm still scared that it's wrong, anyway. After all my previous analysis was wrong :/

atq2119 5y ago
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...
- spacechild1 5y ago
  > 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).
  - atq2119 5y ago
    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.
    - spacechild1 5y ago
      "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.
      - atq2119 5y ago
        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.
spacechild1 5y ago
Your reasoning is correct. Also, if it makes you sleep better :-), here's the boost implementation of a spinlock: https://github.com/boostorg/sync/blob/dfdf317f63d26fb40c703b8d2dc6bbf99c5ca1db/include/boost/sync/detail/mutexes/spin_mutex.hpp#L69 https://github.com/boostorg/sync/blob/dfdf317f63d26fb40c703b... It has been written by an expert in lockfree programming (Tim Blechmann)
- albertzeyer 5y ago
  I wonder, there was this change/fix: https://github.com/boostorg/sync/commit/1b5aaa4a0b7ef4fad2a46336a201081740e1c624#diff-3808384c88a5623a406c6b8073b76294dba88f784b17da9e3316d75295fcde6a https://github.com/boostorg/sync/commit/1b5aaa4a0b7ef4fad2a4...
  - spacechild1 5y ago
    The title "Corrected memory order in some cases" is a bit misleading because the original code was correct. The commit just relaxes some unnecessarily strict memory orderings (to improve performance on platforms with weak memory models). BTW, the spinlock implementation is not affected.