CAS and Reference Counting Revisited

A while ago I suggested that we can't use atomic compare and swap (CAS) and reference counting together to update an arbitrary data structure because we can't atomically dereference the pointer and increase our reference count at the same time. The problem is that there is an instant while we are 'off the end' of the pointer that we haven't increased our reference count; an updater would have no idea that throwing out the copy of the data we are using is a poor idea.

Here's possible work-around: use the low bit of the pointer we want to CAS as a "lock" bit and spin. The algorithm would go something like this:

read begin:
while(1){ // this spins if someone else is trying to
ret = ptr // read-begin.
if(ptr, ptr | 1)) break
}
atomic_inc(&ptr->ref_count);
CAS(ptr, ptr & ~1);
return ret

read_end(data)
if atomic_dec(&data->ref_count)==0)
delete data

update:
while(1)
old = read_begin // take a ref count because we are copying from data
create new copy from old
if CAS(old,new){
assert(atomic_dec(&old->ref_count) > 0);
read_end(old) // two decs,
break
} else {
read_end(old) // we failed to swap, retry.*
delete new }

The idea here is that we can enforce spinning for a short time on other readers while we read the pointer to our block of data by always CASing in the low bit. (This assumes that memory is at least 2-byte aligned, which is an acceptable design assumption on pretty much all modern machines.) Thus we are holding a spin lock while we get our reference count registered.

This code assumes that the data we are protecting has a baseline reference count of one - thus once an updater has replaced it, the updater removes this 'baseline' count, and the last reader to stop counting it (and an updater is a reader) releases it.

One reason why I only come back to RCU-style algorithms every few months is that (at least for this one) there's no way to block to ensure that the old copy of the data has been fully released. Knowing that your update is "fully committed" to all thread contexts is an important property that this algorithm does not have.