Atomic swap in C

Question

I think I'm missing something obvious here. I have code like this:

int *a = <some_address>;
int *b = <another_address>;

// ...

// desired atomic swap of addresses a and b here
int *tmp = a;
a = b; b = tmp;

I want to do this atomically. I've been looking at __c11_atomic_exchange and on OSX the OSAtomic methods, but nothing seems to perform a straight swap atomically. They can all write a value into 1 of the 2 variables atomically, but never both.

Any ideas?

Answer 1

It depends a bit on your architecture, what is effectively and efficiently possible. In any case you would need that the two pointers that you want to swap be adjacent in memory, the easiest that you have them as some like

typedef struct pair { void *a[2]; } pair;

Then you can, if you have a full C11 compiler use _Atomic(pair) as an atomic type to swap the contents of such a pair: first load the actual pair in a temporary, construct a new one with the two values swapped, do a compare-exchange to store the new value and iterate if necessary:

inline
void pair_swap(_Atomic(pair) *myPair) {
  pair actual = { 0 };
  pair future = { 0 };

  while (!atomic_compare_exchange_weak(myPair, &actual, future)) {
      future.a[0] = actual.a[1];
      future.a[1] = actual.a[0];
  }
}

Depending on your architecture this might be realized with a lock free primitive operation or not. Modern 64 bit architectures usually have 128bit atomics, there this could result in just some 128 bit assembler instructions.

But this would depend a lot on the quality of the implementation of atomics on your platform. P99 would provide you with an implementation that implements the "functionlike" part of atomic operations, and that supports 128 bit swap, when detected; on my machine (64 bit Intel linux) this effectively compiles into a lock cmpxchg16b instruction.

Relevant documentation:

1. https://en.cppreference.com/w/c/language/atomic
2. https://en.cppreference.com/w/c/thread
3. https://en.cppreference.com/w/c/atomic/atomic_exchange
4. https://en.cppreference.com/w/c/atomic/atomic_compare_exchange

Answer 2

You should use a mutex.

Or, if you don't want your thread to go to sleep if the mutex isn't immediately available, you can improve efficiency by using a spin lock, since the number of times the spin lock has to spin is frequently so small that it is faster to spin than to put a thread to sleep and have a whole context switch.

C11 has a whole suite of atomic types and functions which allow you to easily implement your own spin lock to accomplish this.

Keep in mind, however, that a basic spin lock must not be used on a bare metal (no operating system) single core (processor) system, as it will result in deadlock if the main context takes the lock and then while the lock is still taken, an ISR fires and tries to take the lock. The ISR will block indefinitely.

To avoid this, more-complicated locking mechanisms must be used, such as a spin lock with a timeout, an ISR which auto-reschedules itself for a slightly later time if the lock is taken, automatic yielding, etc.

Quick answer:

Here is what we will be building up to:

int *a = &some_int1;
int *b = &some_int2;
spinlock_t spinlock = SPINLOCK_UNLOCKED;

// swap `a` and `b`
atomic_swap_int_ptr(&spinlock, &a, &b);

Here are the details:

For a basic spin lock (mutex) on a multi-core system, which is where spin locks are best, however, try this:

Basic spin lock implementation in C11 using _Atomic types

#include <stdbool.h>
#include <stdatomic.h>


#define SPINLOCK_UNLOCKED 0
#define SPINLOCK_LOCKED   1

typedef volatile atomic_bool spinlock_t;

// This is how you'd create a new spinlock to use in the functions below.
// spinlock_t spinlock = SPINLOCK_UNLOCKED;

/// \brief  Set the spin lock to `SPINLOCK_LOCKED`, and return the previous 
///  state of the `spinlock` object.
/// \details    If the previous state was `SPINLOCK_LOCKED`, you can know that
///  the lock was already taken, and you do NOT now own the lock. If the
///  previous state was `SPINLOCK_UNLOCKED`, however, then you have now locked
///  the lock and own the lock.
bool atomic_test_and_set(spinlock_t* spinlock)
{
    bool spinlock_val_old = atomic_exchange(spinlock, SPINLOCK_LOCKED);
    return spinlock_val_old;
}

/// Spin (loop) until you take the spin lock.
void spinlock_lock(spinlock_t* spinlock)
{
    // Spin lock: loop forever until we get the lock; we know the lock was
    // successfully obtained after exiting this while loop because the
    // atomic_test_and_set() function locks the lock and returns the previous
    // lock value. If the previous lock value was SPINLOCK_LOCKED then the lock
    // was **already** locked by another thread or process. Once the previous
    // lock value was SPINLOCK_UNLOCKED, however, then it indicates the lock
    // was **not** locked before we locked it, but now it **is** locked because
    // we locked it, indicating we own the lock.
    while (atomic_test_and_set(spinlock) == SPINLOCK_LOCKED) {};
}

/// Release the spin lock.
void spinlock_unlock(spinlock_t* spinlock)
{
    *spinlock = SPINLOCK_UNLOCKED;
}

Now, you can use the spin lock, for your example, in your multi-core system like this:

/// Atomically swap two pointers to int (`int *`). 
/// NB: this does NOT swap their contents, meaning: the integers they point to.
/// Rather, it swaps the pointers (addresses) themselves.
void atomic_swap_int_ptr(spinlock_t * spinlock, int ** ptr1, int ** ptr2)
{
    spinlock_lock(spinlock)
    // critical, atomic section start

    int * temp = *ptr1;
    *ptr1 = *ptr2;
    *ptr2 = temp;
    
    // critical, atomic section end
    spinlock_unlock(spinlock)
}


// Demo to perform an address swap

int *a = &some_int1;
int *b = &some_int2;
spinlock_t spinlock = SPINLOCK_UNLOCKED;

// swap `a` and `b`
atomic_swap_int_ptr(&spinlock, &a, &b);  // <=========== final answer

References

1. https://en.wikipedia.org/wiki/Test-and-set#Pseudo-C_implementation_of_a_spin_lock
2. C11 Concurrency support library and atomic_bool and other types: https://en.cppreference.com/w/c/thread
3. C11 atomic_exchange() function: https://en.cppreference.com/w/c/atomic/atomic_exchange

Other links

1. Note that you could use C11's struct atomic_flag as well, and its corresponding atomic_flag_test_and_set() function, instead of creating your own atomic_test_and_set() function using atomic_exchange(), like I did above.
2. _Atomic types in C11: https://en.cppreference.com/w/c/language/atomic
3. C++11 Implementation of Spinlock using header <atomic>

TODO

1. This implementation would need to be modified to add safety anti-deadlock mechanisms such as automatic deferral, timeout, and retry, to prevent deadlock on single core and bare-metal systems. See my notes here: Add basic mutex (lock) and spin lock implementations in C11, C++11, AVR, and STM32 and here: What are the various ways to disable and re-enable interrupts in STM32 microcontrollers in order to implement atomic access guards?