Also many architectures with builtin fetch-and-add bundle it with an implicit memory barrier (that includes x86).
On x86, stores are always ordered anyways, so fetch-and-add doesn't need to do any implicit memory barrier.
It is true that on x86 all stores and loads have the correct implicit barriers, but you still get a store-load (including its cycle cost) with lock xadd whether you want it or not.
Think about this:
assign(value)
{
root.ref = value;
}
needs to be expanded out into: assign(value)
{
if (value)
inc_ref(value)
tmp = value
atomic_swap(&root.ref, &tmp)
if (tmp && dec_ref(tmp) == 0)
free(tmp)
}
If you don't use an atomic swap, you race with other threads trying to assign to the same location. You can't decrement the destination before incrementing the source because they could be equal. You can't make the logic conditional on equality because it races.You have a harder time with this:
a.b.c = value
You need to inc-ref each step in the chain, keeping them in temporaries, to ensure they don't get dec-refed out from underneath you on another thread.Keyword is atomic. Fetch-and-add returns you the previous value atomically.
-------
Edit:
This (below) is obviously a buggy reference counting algorithm.
-------
In freeing (decrementing reference count) thread A, if it was 1 before (returned value) and A added -1, the object can be freed.
Because the operation is atomic, only one of two things can happen:
1) Another reference adding thread B increments it before A decreases it. So A doesn't see 1, thus won't free the object.
2) B increments it after A decremented it. So B gets zero and knows the object is invalid. (Edit: Oops, a bug: after B increments refcount, when thread C tries to do same, it would get 1 and conclude the object is valid!)
If B is allowed to allocate the object again (invalid state, refcount == 0), careful synchronization needs to be done remove any races with A's deallocation.
Memory barrier (and atomic operations) don't have anything to do with it.
[1] visibly at least. HTM complicates things a bit of course.
All you need is an atomic fetch-and-add (like x86 XADD opcode). Many architectures provide that as a primitive. On those that don't, you have to compose it out of other atomic primitives.