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

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 sme 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).