Re: [boost] [lock-free] CDS -yet another lock-free library

Subject: Re: [boost] [lock-free] CDS -yet another lock-free library
From: Khiszinsky, Maxim (Maxim.Khiszinsky_at_[hidden])
Date: 2010-03-30 07:25:06

Cory Nelson wrote:

>> Comparing only the tag means that there is global counter incremented atomically. As a result a contention on this global counter may be encountered...

> You should be able to use the exact same algos, but compare only the
> tag.  No global counter needed.

I'm not understanding  :-(

Formally:
Lets P is the set of all tagged pointer of our application.
To resolve ABA-problem with cmp8xchg16 the following condition must be true:
for each {p, q} from P: p.tag != q.tag

p is struct {
   atomic64_t tag ;
   void *     ptr ; 
};

Then, when we change tagged pointer p we must change its tag. How? Simply increment ++p.tag?.. In this case the condition may be violated...
Another question: how the p.tag should be initialized.

It seems, a global counter C appears: 
p.tag = atomic_inc( &C ) ;

The global counter keeps the condition as true.

Maybe, my reasoning is not true and you known best solution. 

Regards, Max