Boost logo

Boost :

Subject: Re: [boost] [lockfree::fifo] Review
From: Chris M. Thomasson (cristom_at_[hidden])
Date: 2010-01-15 21:15:44

"Chris M. Thomasson" <cristom_at_[hidden]> wrote in message
> "Helge Bahmann" <hcb_at_[hidden]> wrote in message
>> On Wed, 9 Dec 2009, Anthony Williams wrote:
>>>> So far I have not yet met any 64-bit platform that provides 64 bits of
>>>> (user-space!) address space (the same cannot be said of 32-bit
>>>> platforms), so I would say that any use of spare bits on 64 bit is
>>>> safe (for user-space!).
>>> As Chris also noted, I would be wary of using them for ABA checking
>>> though: it's easy to overflow a 16-bit counter quite quickly, and that's
>>> all you've got even if the OS only uses 48 of your 64 bits for address
>>> space.
>> This concern is certainly valid for basically any algorithm that uses
>> "generation counters" or similar constructs for disambiguation (it could
>> be argued that even 32 bits may not be enough). Using spare bits at all
>> should however be considered a valid technique.
>>>> FWIW there are other ways to avoid ABA than tagging pointers, and
>>>> without DCAS on 32-bit, see e.g. this sample implementation of a
>>>> lock-free stack:
>>> Yup. Incidentally, you don't even need to count the nodes in push,
>>> provided you're careful when reclaiming nodes in pop.
>> hm, I'm not sure what you mean, I don't think I am counting anything but
>> the number of threads in the critical section?
>>> The downside of this technique is that if the traffic is too heavy then
>>> the ref count never reaches zero, so the nodes can never be reclaimed.
>> Right, and although I would argue that such a highly contended hotspot is
>> a design flaw in itself,
> You have created a proxy garbage collector that reminds me of one I did a
> long time ago which also suffered from this exact same problem.

FWIW Helge, here is a new proxy garbage collector algorithm of mine that I
am currently experimenting with:

is basically a simplified version of the following lock-free algorithm:

The new algorihtm is a *wait-free solution to the ABA problem and memory
reclamation issues in general wrt non-blocking algorithms. The usage pattern
is basically identical to you're collector wrt the following code:

you do it like:
 bool pop(T &data) throw()
  node * n=stack.pop();
  if (n) {
  return n!=0;

The equivalent code for my collector would be:
bool pop(T& data) throw()
    proxy_type::collector& c = m_proxy.acquire();

    node* n = m_stack.pop();

    if (n)
        data = n->m_data;

        m_proxy.collect(c, n);


    return (n != NULL);


The algorithm is wait-free in practice on systems with native fetch-and-add
and swap instructions like x86-32/64. If the architecture forces you to
implement fetch-and-add with a damn LL/SC or CAS loop, well, then it's not
really wait-free now is it? No, I am afraid it's lock-free, or whatever
semantics the LL/SC is which could even be obstruction-free. Sad...


Boost list run by bdawes at, gregod at, cpdaniel at, john at