memory ordering with atomic_flag spin lock

Question

I am trying to get familiar with the new memory ordering concepts of c++11 and believed I actully had a quite good grasp on them, until I stumbled upon this implementation of a spin lock:

#include <atomic>

namespace JayZ
{
    namespace Tools
    {
        class SpinLock
        {
        private:
            std::atomic_flag spin_lock;
        public:
            inline SpinLock( void ) : atomic_flag( ATOMIC_FLAG_INIT ) {}

            inline void lock( void )
            {
                while( spin_lock.test_and_set( std::memory_order_acquire ) )
                    ;
            }

            inline void unlock( void )
            {
                lock.clear( std::memory_order_release );
            }
        };
    }
}

It is e.g. equivalently mentioned at http://en.cppreference.com/w/cpp/atomic/atomic_flag
and also in the book "Concurrency in Action". I also found it someplace here at SO.

But I just don't understand why it would work!
Imagine thread 1 calls lock() and test_and_set() returns 0 as the old value --> thread 1 has acquired the lock.
But then thread 2 comes along and tries the same. Now since there has occurred no "store synchronization" (release,seq_cst_acq_rel) thread 1's store to spin_lock should be of type relaxed.
But from this follows that it cannot imao be synchronized with thread 2's read of spin_lock. This should make it possible for thread 2 to read the value 0 from spin_lock and thus acquire the lock as well.
Where is my mistake?

Answer 1

Your mistake is in forgetting that spin_lock is an atomic_flag and thus test_and_set is an atomic operation. The memory_order_acquire and memory_order_release is needed to prevent reads from migrating to before the lock operation or writes from migrating to after the unlock. The lock itself is protected by atomicity which always includes visibility.

Answer 2

For a given atomic variable, there is a "modification order" for it. Once thread 1 test_and_sets the value from 0 to 1, it is impossible for thread 2 to see a 0.

Memory order affects how all other memory addresses are 'synced.' If one thread modifies an atomic variable with a memory-order_release, then any thread that reads the same variable with memory_order_acquire "sees" every memory change the first thread made before it released.

The acquire and release is not about the atomic. It's about making sure every thread that successfully locks the spinlock "sees" the changes of every thread that locked it before.

The modification order is the key to making the algorithm lockfree. Both thread 1 and thread 2 are trying to do a test_and_set on the same variable, so by the rules, one modification "happens before" the other. Because the test_and_set that "happens before" the other gets to "progress," at least one thread must always make progress. This is the definition of lockfree

Answer 3

test_and_set operations on atomic flags are specified to be read-modify-write operations which have special characteristics, one of which is:

Atomic read-modify-write operations shall always read the last value (in the modification order) written before the write associated with the read-modify-write operation. [n3337 § 29.3/12]

This is also why fetch_add, for example, works whereas simple load operations are not required to read the latest value in the modification order.