Subj : Re: A question about atomic_ptr
To   : comp.programming.threads
From : Peter Dimov
Date : Sun Apr 17 2005 07:19 pm

Chris Thomasson wrote:
> Yup, just noticed that. DWCAS would work. However, I am currently
> fiddling around with logic like this:

[...]

I think that there is a race, but it doesn't really matter. In the absence 
of atomic double-wide stores, it is impossible to make it lock-free (by the 
canonical definition of lock-free). That's because if you have

struct { void *p1, *p2 };

where p1 and p2 need to be in sync, when the writer changes p1 and gets 
preempted before changing p2, no other thread can make progress. It's 
basically a rw(spin)lock.

I think that the only lock-free solution is to introduce a level of 
indirection and hold the struct by a single pointer (and then use 64 bit CAS 
on a 32-bit "virtual pointer" and a 32-bit contention count or something 
like that).

.