Boost logo

Boost :

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


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk