Re: [boost] [lockfree::fifo] Review

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 
news:hgfqaj$k90$1_at_ger.gmane.org...
> "Helge Bahmann" <hcb_at_[hidden]> wrote in message 
> news:alpine.DEB.1.10.0912101115460.456_at_m65s28.vlinux.de...
>> 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:
>>>>
>>>> http://www.chaoticmind.net/~hcb/projects/boost.atomic/stack.hpp
>>>
>>> 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:

http://groups.google.com/group/comp.programming.threads/browse_frm/thread/a53f24de178b419f

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

http://webpages.charter.net/appcore/misc/pc_sample_h_v1.html

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:

http://www.chaoticmind.net/~hcb/projects/boost.atomic/stack.hpp

you do it like:
__________________________________________________________________
 bool pop(T &data) throw()
 {
  enter_crit();
  node * n=stack.pop();
  if (n) {
   data=n->data;
   expired.push(n);
  }
  leave_crit();
  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);
    }

    m_proxy.release(c);

    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...

;^(...