How to implement double-word compare and swap in C/Linux?

Question

I was reading the paper "Simple, fast, and practical non-blocking and blocking concurrent queue algorithms" and I realized that that they assume that the computer implements the following pseudo-code atomically:

CAS(Q->Tail,tail,<next.ptr,next.count+1>)

Where Q->Tail and tail are a pointer and an instance of a struct containing a pointer and a counter.

I know that gcc provides a couple of build-ins for single word compare and swap in c. However, is it possible to implement a non-blocking atomic double-word compare and swap from a single compare and swap in c (using Linux)? Is this the right approach to implement the pseudo-code of the referenced paper?

Answer 1

I don't know of any CAS operations that work on two distinct memory locations. However, it's possible the paper is using a struct for the pointer and counter as a workaround to treat both fields as a larger type, and therefore, change both atomically.

Assuming you have a struct of two fields, a pointer and a counter: pointer size of 4 bytes, counter size of 4 bytes; properly aligned without padding to a struct size of 8 bytes. Assuming you also have a CAS operation that handles values of 8 bytes (such as a pointer to a 64-bit integer). You can prepare the struct values separately, and use the CAS operation on the struct as a whole to change two values at once.

Answer 2

Gcc also provides built-ins for double-word CAS, you can use __sync_bool_compare_and_swap, if sizeof(*Q->Tail) == sizeof(tail) == sizeof(third_arg) == 8. So everything works fine if you can increment "next.count" before performing CAS.