Atomic operations are the basis for dealing with contention between asynchronously executing code.  In theory atomic operations are fairly easy; in practice their application is very difficult. Traditionally locks, semaphores, and mutexs are implemented with some sort of underlying atomic operation, such as test-and-set-lock.

The most common operations are atomic_increment (and decrement), and atomic_compare_and_swap.  Many algorithms are written using these.  Unfortunately the better form of atomics that uses lock line reservations and conditional updates is rarely available.  I'll go into why they are better in a bit.

So why is it so hard to get things right?  For starters hardware varies widely, with cache lines of differing sizes and levels and instructions sets that expose more or less bytes that can be handled atomically.  It gets much worse one you start to consider optimizing C/C++ compilers that will often reorder instructions and elide copies in ways that will surprise you and break your code, and adding volatile everywhere will cause them to produce horribly inefficient code. Ultimately though, we humans are just not that good at thinking through all that interactions that are happening, and how they can go wrong.

So lets say you a machine where sizeof(void*) is 4 (i.e. a 32-bit machine), and you have bool atomic_compare_and_swap_ptr(volatile intptr_t *address, intptr_t const& compare_to, intptr_t const& swap_with) that works.  What can you do with it? Lets try and build a stack.  (We'll fail, but how we fail is important.)

This results in the a-b-a problem.  Lets say our stack looks like this "abc"  (i.e. "a" is on top followed by "b" then "c") and we've got two threads accessing the stack.  Now thread 0 comes along and starts a pop operation but gets suspended at [1] in the code above; r points to "a" with a next of "b".  Now thread 1 comes along and pops off "a" and "b" and pushes "a" back on, now with a next of "c". Eventually thread 0 wakes up and the atomic_compare_and_swap_ptr is made, and succeeds in swapping the top with "b", which is completely wrong.  Because thread 1 restored the top pointer to the same value it was when thread 0 was suspended thread 0 didn't see the change to the next pointer.

(Note: writing atomic_compare_and_swap_ptr(s, (uintptr_t)*r, (uintptr_t)(*s)->next) doesn't fix the problem.  It just moves it to having to suspend thread 0 during setting up the function call, after the third parameter is resolved and before the dispatch occurs.)

(Also note: The loops don't yield, and as far as I know there is no portable way to yield.  You'll likely have to yield at some point though (perhaps in the caller), since if you don't a consumer thread spinning on stack_pop waiting for a producer thread to stack_push could completely block out the producer thread if your priorities are set wrong and you operating system doesn't eventually give time to lower priority threads; say like on a PS3.)

So can we avoid the a-b-a problem?  Unfortunately not with atomic_compare_and_swap_ptr (at least if we want to keep using pointers directly).  We need either larger atomics, or lock line reservation with conditional update.

With larger atomics we can version the pointer and increment the version on every operation.  That way the push will see the pointer as the same ("a"), but with a different version and so will fail.  The version is often called a tag.  The major draw back up this approach is that many systems don't support atomics larger than pointer size.  There is also a small chance of wrap around, but that's very unlikely in real world usage unless you specifically contrive a case for it.  (Then again, some of the things hackers have done to break systems are very similar.)

Ideally we'd have lock line reservation with conditional update (GetLLAR/PutLLC if you're familiar with the PS3-SPU) everywhere rather than just on a small number of platforms.  Atomics are generally implemented using something like them under the hood anyways.  Basically each cache line has a reservation marker indicated which core last asked for a reservation.  Any writes to the cache line clear it, even if the data written is identical to what was already there.  The conditional update checks the reservation marker matches the core updating it before writing to the cache line and only writes if it is still held.  During a thread switch the core has to clear outstanding reservations so only a limited number of cache lines can be reserved at a time.  In practice you should only ever rely on getting one reservation.

The major reason I prefer cache line reservations is it better reflects what really happens and doesn't limit use to 32, 64, or 128 bit atomics when the cache lines are 512 or 1024 bits in size.  Since the smallest amount of real memory that can be updated is a cache line and inter cpu synchronization happens at a cache line level all atomic updates actually happen at the cache line granularity anyways, so why not expose it.

For now we'll have to live with versioning pointers on system that allow larger than pointer sized atomics and avoid using pointer indexing on system with pointer sized atomics.  (Basically artificially reducing pointer space by using an index into an array and adding a version into the bits freed up.)

Now at first you'll be tempted to use a union to overlay an integer type over the pointer and version, do not do this.  All access to atomics in the heap must go through a type marked as volatile, and making a union volatile is a nightmare.  The compiler dependent treatment of the volatile keyword is going to cause us enough grief before we're done.

To start with we'll need a pointer + version pair that most compilers will do-the-right-thing with.  That basically means it has to be an integer type, not an aggregate, since most compiles will place integer types in a register whenever possible.  This presents a problem on 64bit machines since there is no standard 128 bit integer type.  That means we'll have to use macros for manipulating the type so we can use compiler and sdk specific code for manipulating the MSB and LSB parts of the integer and clearing it to zero.


We can now build an atomic stack class (or free functions if your a C fan):

I use FORCE_INLINE on push and pop. It is likely that the atomic_stack will be used as the basis for a more complicated data access pattern that will expose a few functions that use push and pop; so the code bloat won't be significant. It is unfortunate that C++ doesn't allow for the inlining to be specified at the call site and so we have to inline by default and rely on the user deciding to wrap the calls in a non-inlined function or method to reduce code bloat if they intend to call the push and pop methods from many places in their code. If you do use push and pop from several call sites you should consider not inlining them to reduce code bloat.

We only bump the version in pop since an item in the stack should never be re-added to the stack.  You might also notice that we're added a compiler read-write barrier before the compare and swap call.  That ensures the store to the next pointer of the item doesn't get reordered to after the compare and swap call.  (Some compilers don't provide this, or don't honor it properly, for example the XBox360 compiler requires additional volatiles to get the order correct that also generate unnecessary load-hit-stores and cost performance.)

I use a clear method rather than having the constructor (ctor) do the initialization. I aim to have my classes be valid when initialized to all zeros so my allocator can efficiently zero out the memory so often the clear call goes unused.

At this point some of you are probably wondering how we're going to test this.  One major problem with developing any program is that what we write and what the compiler generates are different things.  I've already alluded to this by adding in macro that we need to replace with a compiler specific directive to prevent reordering of stores. Different compilers and architectures present different optimization techniques and many of them assume a singled threaded program.  Reordering of loads and stores is just one problem.

Take this code for instance:

The call to f(&i) will likely be assembled into something like this:
That is to say no call will be made (it'll be inlined), and all of the temporary variables will be elided.  If the machine is capable of acting on memory directly it may even boil down to a single instruction that increments the value in memory rather than a function call.

Now, if we consider the impact this has on our atomics code above you can see why barriers alone are not enough:
can easily turn into:
instead of:
That is the compiler might assume it can read the value from memory twice and get the same result.  (Hence we mark the memory as volatile to indicate to the compiler that the memory can be changed by operations not executing in the current thread.) I've actually had a compiler generate code like this.

Now, given that we can't completely control the assembly code generated by the compiler we've got some issues with testing our atomic_stack class. Any tests we write will have to be executed by a real machine and it is very possible the compiler for that machine will produce code that works, even if we've made an error, while a compiler for another machine would produce code that would break because of our error. Also the window for a race can be as small as a single instruction interleaving between two threads that occurs so rarely (one in billions) it doesn't occur often enough to show up regularly in our tests. There is really no way to test this code to a one hundred percent level of confidence using standard testing practices. Each machine we're going to use this code on is going to require us to decompile and analyze the assembly produced so we can be sure it works. Worse yet if we want to continue to be one hundred percent sure the code is working we'll have to do this every time the compiler changes to produce different assembly output as new optimizations are added. (Yes, we could build an emulator and simulate every conceivable instruction interleaves between several threads, but that not exactly a standard testing practice and still leaves us with having to test each machine and compiler combination anyways.) This is a really good argument for having this kind of algorithm be a built in feature of a language rather than something each user should develop.

To go further at this point we need to pick a machine and see what we get.  I'm going to use Visual Studio Express 2008 on a 32bit intel machine.

To start with we'll need the defines and platform includes:
That gets our atomic_stack code compiling.

A small test:
Confirms functionality and tests multiple threads pushing and poping from a stack.

Now lets look under the hood and check up on the compiler. First make sure your building the above test in Release. Now place a break point somewhere in main and run it in the debugger. Right click and pick "Go To Disassembly".

The first two pushes turn into (without the annotations to the left which I've added):
Oddly it generates different code for the two calls, but both are correct as we can see the next pointer is updated before the cmpxchg happens and that top_ is read only once to get both the original and new values.

Now lets look at the first Pop:
Holy crap. The compiler sure spit out a lot of code for pop, and the _allmul call looks really fishy.

Turns out the this particular compilers is turning the atomic_set math into a 64bit multiply, and fiddling with the optimization settings doesn't help. We can write atomic_set differently in this case to avoid the problem:

This improves the code generation, atomic_push becomes:
It is still doing a needless, and potentially harmful, cdq on the pointer to the data to be pushed. If the memory management system returns a pointer with the high bit set our versioning will fail since the cqd will fill edx with all ones and the subsequent or of the version and the saved edx value from the stack will result in the version being all ones. This could lead to an A-B-A failure that would be very hard to track down.

Using a union we can avoid the sign extension:

Now push becomes:
Which is exactly what we want.

And pop becomes:
Which is also exactly what we want.  Note that I said we'd avoid using union originally, and the only reason we get away with it here is that atomic_set is only used on the temporary and not the value in the heap.

If we hadn't checked up on the compiler we'd have a much slower and more inefficient (in both code space and execution time) program, and potentially an incorrect version of the code with a difficult to track down bug that our unit test failed to find. By analyzing the assembly code produced we can be confidant the code will work for the platform we're targeting.