atomic operation implementation

Question

i am using atomic operation provided by SunOs in <sys/atomic.h> , which is
void *atomic_cas_ptr(volatile void *target, void *cmp, void *newval);

now to make is usable, i have to check whether old value returned by this function and passed by callee function cmp are same, if they are then operation is successful.
but i have certain doubt: as this function returns a void pointer to the old value let's call it void *old and i'm passing void *cmp, then i need to compare these two old and cmp, so how i am going to compare these two ? and if while comparing *old got changed then what i am going to do ?
in essence what i want to do is to warp this function, inside another function which takes these three arguments and return either true or false, which indicate success or failure.
about the CAS, i read that it's misnomer to call it lockfree operation, since it eventually takes lock at hardware ( lock at bus ), It's right correct ? that's why the CAS is costly operation .

Answer 1

Possibly the function declaration confused you. This function does not return a pointer to the old value (of what?), but the old value from the memory pointed by target (which should really be a pointer to void*, i.e. void* volatile * target).

Usually if a CAS primitive returns an old value rather than a bool, you check CAS success with something like this:

void* atomic_ptr; // global atomically modified pointer

void* oldval, newval, comparand; // local variables
/* ... */
oldval = atomic_cas_ptr( (void*)&atomic_ptr, /* note that address is taken */
                          comparand, newval );
if( oldval == comparand ) {
    // success
} else {
    // failure
}

So when you compare old_val and comparand, you work with local variables that do not change concurrently (while global atomic_ptr might be changed again), and you compare pointer values without dereferencing.

The function you want should be like this:

bool my_atomic_cas_ptr(volatile void* target, void* comparand, void* newval)
{
    return (comparand == atomic_cas_ptr(target, comparand, newval));
}

Note that since in some algorithms the old value (the one before CAS) should be known, it's better to have a CAS primitive returning the old value rather than a bool, as you can easily build the latter from the former while the opposite is more complex and inefficient (see the following code that tries to obtain the correct old value out of a MacOS CAS primitive that returns a bool).

void* CAS(void* volatile* target, void* comparand, void* newval)
{
    while( !OSAtomicCompareAndSwapPtr(comparand, newval, target) ) {
        void* snapshot = *target;
        if( snapshot!=comparand ) return snapshot;
    }
    return comparand;
}

As for CAS locking memory bus, it depends on hardware. It was true for old x86 processors, but in modern x86 systems it's different. First, there is no central bus; it was replaced by AMD's HyperTransport and Intel's QuickPath Interconnect. Second, in recent CPU generations locked instructions are not all serialized (see some data showing that locked instructions on different memory addresses do not interfere). And finally, in the commonly accepted definition lock freedom is the guarantee of system-wide progress, not absence of serializing synchronization.