Lock-free C++11 example using Load-link/store-conditional to prevent ABA?

Question

When writing lock-free code using the Compare-and-Swap (CAS) technique there is a problem called the ABA problem:

http://en.wikipedia.org/wiki/ABA_problem

whereby comparing just on the value "A" is problematic because a write could still have occurred between the two observations. I read on and found this solution:

http://en.wikipedia.org/wiki/LL/SC

In computer science, load-link and store-conditional (LL/SC) are a pair of instructions used in multithreading to achieve synchronization. Load-link returns the current value of a memory location, while a subsequent store-conditional to the same memory location will store a new value only if no updates have occurred to that location since the load-link. Together, this implements a lock-free atomic read-modify-write operation.

How would a typical C++ lock-free CAS technique be modified to use the above solution? Would somebody be able to show a small example?

I don't mind whether its C++11/x86, x86-64 Linux-specific (preferably no Win32 answers).

Answer 1

LL/SC are instructions implemented by some architectures (e.g. SPARC) to form the foundation of higher level atomic operations. In x86 you have the LOCK prefix instead to accomplish a similar goal.

To avoid the ABA problem on x86 with LOCK you have to provide your own protection against intervening stores. One way to do this is to store a generation number (just an increasing integer) adjacent to the memory in question. Each updater does an atomic compare/exchange wide enough to encompass both the data and the serial number. The update only succeeds if it finds the right data and the right number. At the same time, it updates the number so that other threads see the change.

You'll note that x86 has always (?) offered a CMPXCHG instruction that is twice as wide as a machine word (see CMPXCHG8B and later CMPXCGH16B) which can be used for this purpose.