[SOLVED] Atomic swap in C

Atomic swap in C

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?

Solution

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: