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