Atomic swap function using gcc atomic builtins

Question

Is this a correct implementation for a generic atomic swap function? I'm looking for a C++03-compatible solution on GCC.

template<typename T>
void atomic_swap(T & a, T & b) {
    static_assert(sizeof(T) <= sizeof(void*), "Maximum size type exceeded.");
    T * ptr = &a;
    b =__sync_lock_test_and_set(ptr, b);
    __sync_lock_release(&ptr);
}

If not, what should I do to fix it?

Also: is the __sync_lock_release always necessary? When searching through other codebases I found that this is often not called. Without the release call my code looks like this:

template<typename T>
void atomic_swap(T & a, T & b) {
    static_assert(sizeof(T) <= sizeof(void*), "Maximum size type exceeded.");
    b = __sync_lock_test_and_set(&a, b);
}

PS: Atomic swap in GNU C++ is a similar question but it doesn't answer my question because the provided answer requires C++11's std::atomic and it has signature Data *swap_data(Data *new_data) which doesn't seem to make sense at all for a swap function. (It actually swaps the provided argument with a global variable that was defined before the function.)

@BenVoigt That post doesn't give a clear answer. And it swaps the argument with a global variable. — StackedCrooked, Jan 27 '12 at 22:09

Jason · Accepted Answer · 2012-01-27T23:41:25.083

Keep in mind this version of swap is not a fully atomic operation. While the value of b will be atomically copied into a, the value of a may copy over another modification to the value of b by another thread. In other words the assignment to b is not atomic with respect to other threads. Thus you could end up with a situation where a == 1, and b == 2, and after the gcc built-in, you end up with a == 2 and the value of 1 being returned, but now another thread has changed the value of b to 3, and you write over that value in b with the value of 1. So while you may have "technically" swapped the values, you didn't do it atomically ... another thread touched the value of b in-between the return from the gcc atomic built-in, and the assignment of that return value to b. Looked at from the assembly stand-point, you have something like the following:

lea RAX, qword ptr [RDI]  // T * ptr = &a;
mov RCX, qword ptr [RSI]  // copy out the value referenced by b into a register
xchg [RAX], RCX           // __sync_lock_test_and_set(&a, b)
mov qword ptr [RSI], RCX  // place the exchange value back into b (not atomic!!)

To be honest, you can't do a lock-free atomic swap of two separate memory locations without a hardware operation like a DCAS or a weak load-linked/store-conditional, or possibly using some other method like transactional memory (which itself tends to use fine-grained locking).

Secondly, as your function is written right now, if you want your atomic operation to have both acquire and release semantics, then yes, you're going to have to either place in the __sync_lock_release, or you're going to have to add a full memory barrier through __sync_synchronize. Otherwise it will only have acquire semantics on the __sync_lock_test_and_set. Still though, it does not atomically swap two separate memory locations with each other ...

I understand that the write to `b` makes it a non-atomic operation and thus not thread-safe. However, I don't see a way to make it safe. Does this mean that a lockless swap of pointer types is not really possible? — StackedCrooked, Jan 27 '12 at 22:31
Pretty much, unless again, the hardware supports something like a DCAS, or a load-linked/store conditional operation that is fairly weak so that it fails if there is any access to memory, or at least memory access on a cache-line, and the two values you're swapping are on the same cache-line — Jason, Jan 27 '12 at 22:43

Atomic swap function using gcc atomic builtins

1 Answers1