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

Subject: Re: [boost] [lockfree::fifo] Review
From: Anthony Williams (anthony.ajw_at_[hidden])
Date: 2009-12-09 16:45:10

Helge Bahmann <hcb_at_[hidden]> writes:

> On Tue, 8 Dec 2009, Andy Venikov wrote:
>>>> Third, and the biggest limitation, is the algorithm's assumption
>>>> that you can store a pointer to an element plus an ABA tag in a
>>>> contiguous memory space that can be passed to a CAS instruction. I
>>>> believe not all platforms provide a DCAS instruction, that's why
>>>> you're trying to work around this issue by using "packed
>>>> pointers", i.e. storing the ABA tag in the part of the pointer
>>>> that presumably is never used. The problem with that, however, is
>>>> that some libc implementations of malloc/free do use all the bits
>>>> in the pointer for their own needs, so you can't assume that you
>>>> can meddle with them.
>>>
>>> puh, can you elaborate on this? i haven't been aware of any use of the
>>> unused address space bits.
>>
>>
>> Yes. Recently I did an experiment on 32 bit 2.6 linux using SUSE 9.1
>> and libc that came with it. (libc version was 2.3.3-97).
>
> 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.

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

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.

> Using correct ordering constraints is unfortunately tricky -- use "too
> strong" ones, and performance will look ridiculous compared to
> locking. Use "took weak" ones, and your implementation will spuriously
> fail in ways that are nearly impossible to diagnose.

Totally agreed.

Anthony
-- 
Author of C++ Concurrency in Action     http://www.stdthread.co.uk/book/
just::thread C++0x thread library             http://www.stdthread.co.uk
Just Software Solutions Ltd       http://www.justsoftwaresolutions.co.uk
15 Carrallack Mews, St Just, Cornwall, TR19 7UL, UK. Company No. 5478976