atomic swap with CAS (using gcc sync builtins)

Question

Can the compare-and-swap function be used to swap variables atomically? I'm using C/C++ via gcc on x86_64 RedHat Linux, specifically the __sync builtins. Example:

   int x = 0, y = 1; 
   y = __sync_val_compare_and_swap(&x, x, y);

I think this boils down to whether x can change between &x and x; for instance, if &x constitutes an operation, it might be possible for x to change between &x and x in the arguments. I want to assume that the comparison implicit above will always be true; my question is whether I can. Obviously there's the bool version of CAS, but then I can't get the old x to write into y.

A more useful example might be inserting or removing from the head of a linked list (gcc claims to support pointer types, so assume that's what elem and head are):

   elem->next = __sync_val_compare_and_swap(&head, head, elem); //always inserts?
   elem = __sync_val_compare_and_swap(&head, head, elem->next); //always removes?

Reference: http://gcc.gnu.org/onlinedocs/gcc/Atomic-Builtins.html

Answer 1

Nope. The CAS instruction on x86 takes a value from a register, and compares/writes it against a value in memory.

In order to atomically swap two variables, it'd have to work with two memory operands.

As for whether x can change between &x and x? Yes, of course it can.

Even without the &, it could change.

Even in a function such as Foo(x, x), you could get two different values of x, since in order to call the function, the compiler has to:

• take the value of x, and store it in the first parameter's position, according to the calling convention
• take the value of x, and store it in the second parameter's position, according to the calling convention

between those two operations, another thread could easily modify the value of x.

Answer 2

It seems like you're looking for the interlocked-exchange primitive, not the interlocked-compare-exchange. That will unconditionally atomically swap the holding register with the target memory location.

However, you still have a problem with race conditions between assignments to y. Sometimes y is a local, in which case this will be safe, but if both x and y are shared you have a major problem and will need a lock to resolve it.

Answer 3

The operation might not actually store the new value into the destination because of a race with another thread that changes the value at the same moment you're trying to. The CAS primitive doesn't guarantee that the write occurs - only that the write occurs if the value is already what's expected. The primitive can't know what the correct behavior is if the value isn't what is expected, so nothing happens in that case - you need to fix up the problem by checking the return value to see if the operation worked.

So, your example:

elem->next = __sync_val_compare_and_swap(&head, head, elem); //always inserts?

won't necessarily insert the new element. If another thread inserts an element at the same moment, there's a race condition that might cause this thread's call to __sync_val_compare_and_swap() to not update head (but neither this thread's or the other thread's element is lost yet if you handle it correctly).

But, there's another problem with that line of code - even if head did get updated, there's a brief moment of time where head points to the inserted element, but that element's next pointer hasn't been updated to point to the previous head of the list. If another thread swoops in during that moment and tries to walk the list, bad things happen.

To correctly update the list change that line of code to something like:

whatever_t* prev_head = NULL;
do {
    elem->next = head;  // set up `elem->head` so the list will still be linked 
                        // correctly the instant the element is inserted
    prev_head = __sync_val_compare_and_swap(&head, elem->next, elem);
} while (prev_head != elem->next);

Or use the bool variant, which I think is a bit more convenient:

do {
    elem->next = head;  // set up `elem->head` so the list will still be linked 
                        // correctly the instant the element is inserted
} while (!__sync_bool_compare_and_swap(&head, elem->next, elem));

It's kind of ugly, and I hope I got it right (it's easy to get tripped up in the details of thread-safe code). It should be wrapped in an insert_element() function (or even better, use an appropriate library).

Addressing the ABA problem:

I don't think the ABA problem is relevant to this "add an element to the head of a list" code. Let's say that a thread wants to add object X to the list and when it executes elem->next = head, head has value A1.

Then before the __sync_val_compare_and_swap() is executed, another set of threads comes along and:

• removes A1 from the list, making head point to B
• does whatever with object A1 and frees it
• allocates another object, A2 that happens to to be at the same address as A1 was
• adds A2 to the list so that head now points to A2

Since A1 and A2 have the same identifier/address, this is an instance of the ABA problem.

However, it doesn't matter in this case since the thread adding object X doesn't care that the head points to a different object than it started out with - all it cares about is that when X is queued:

• the list is consistent,
• no objects on the list have been lost, and
• no objects other than X have been added to the list (by this thread)