c++ - Basic spin-lock mutex implementation ordering

Question

There is a popular spin-lock mutex version which is spreaded across the Internet and which one might encounter in the Anthony Williams book(C++ Concurrency in Action). Here it is:

class SpinLock
{
    std::atomic_flag locked;
public:
    SpinLock() :
        locked{ATOMIC_FLAG_INIT}
    {
    }
    void lock() 
    {
        while(locked.test_and_set(std::memory_order_acquire));
    }
    void unlock() 
    {
        locked.clear(std::memory_order_release);
    }
};

The thing I do not understand is why everybody uses std::memory_order_acquire for the test_and_set which is an RMW operation. Why is it not std::memory_acq_rel? Suppose we have 2 threads simultaneously trying to acquire a lock:

T1: test_and_set -> ret false
T2: test_and_set -> ret false

The situation should be possible since we have 2 acquire operations which don't form any sync with relationship between each other. Yes, after we have unlocked the mutex we have a release operation which heads a subsequent release sequence and life becomes colorful and everyone is happy. But why is it safe before the release sequence is headed?

Since many people mention exactly that implementation I suppose it should work correctly. So what am I missing?

UPDATE 1:

I perfectly understand that the operation is atomic, that operations between lock and unlock can't go out of the critical section. This is not a problem. The problem is that I don't see how the code above prevents 2 mutexes coming into the critical section simultaneously. To prevent it from happening there should be happens before relationship between 2 locks. Could someone show me, using the C++ standard notions, that the code is perfectly safe?

UPDATE 2:

Ok, we are close to the correct answer, I believe. I've found the following in the standard:

[atomics.order] clause 11

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.

And on this major note I could happily close the question but I still have my doubts. What about in the modification order part? Standard is pretty clear about it:

[intro.multithread] clause 8

All modifications to a particular atomic object M occur in some particular total order, called the modification order of M . If A and B are modifications of an atomic object M and A happens before(as defined below) B, then A shall precede B in the modification order of M , which is defined below.

So according to that clause for an RMW operation to have the latest written value, the latest write operation should happen before the reading part or RMW operation. Which is not the case in the question. Right?

UPDATE 3:

I more and more think that the code for a spin lock is broken. Here is my reasoning. C++ specify 3 types of operations:

• Acquire, release, acquire-release - these are sync ops.
• Relaxed - these are no sync ops
• RMW - these are operations with "special" characteristic

Let's start with RMW and find out what so special about them. First, they are a valuable asset in forming release sequence, second they have a special clause([atomics.order] clause 11) cited above. Nothing else special I found.

Acquire/release are sync ops and release sync with acquire so forming a happens before relationship. Relaxed operations are just plain atomics and don't participate in the modification order at all.

What we have in our code? We have an RMW operation which uses acquire memory semantics so whenever first unlock(release) is reached it serves 2 roles:

1. It forms a sync with relationship with the previous release
2. It participates in the release sequence. But that's all true only after the first unlock has finished.

Before that, if we have 2+ threads which are simultaneously running our lock code then we can enter pass the lock simultaneously since 2 acquire operations don't form any kind of relationship. They are as unordered as relaxed operations would. Since they are unordered we can't use any special clauses about RMW operations since there is no happens before relationship and hence no modification order for the locked flag.

So either my logic is flawed or code is broken. Please, whoever knows the truth - comment on this.

Answer 1

I think what you're missing is that test_and_set is atomic, period. There is no memory ordering setting that makes this operation not atomic. If all we needed was an atomic test and set, we could specify any memory ordering.

However, in this case, we need more than just an atomic "test and set" operation. We need to ensure that memory operations we performed after we confirmed that the lock was ours to take aren't re-ordered to before we observed the mutex to be unlocked. (Because those operations won't be atomic operations.)

Consider:

1. Some reads of data not protected by the mutex.
2. Some writes to data not protected by the mutex.
3. We try to lock the mutex.
4. We see the mutex as locked and fail to lock it.
5. We see the mutex as unlocked and atomically lock it.
6. Some reads of data protected by the mutex.
7. Some writes to data protected by the mutex.

What is the one thing that must not happen? It's that the reads and writes in step 6 and 7 somehow get re-ordered to before step 5, stepping on another thread accessing shared data under protection of the mutex.

The test_and_set operation is already atomic, so steps 4 and 5 are inherently safe. And steps 1 and 2 can't modify protected data (because they occur before we even try to lock) so there's no harm in re-ordering them around our lock operation.

But steps 6 and 7 -- those must not be re-ordered to prior to us observing that the lock was unlocked so that we could atomically lock it. That would be a catastrophe.

The definition of memory_order_acquire: "A load operation with this memory order performs the acquire operation on the affected memory location: no memory accesses in the current thread can be reordered before this load."

Exactly what we need.