Re: [boost] boost.lockfree proposal

From: Cory Nelson (phrosty_at_[hidden])
Date: 2008-04-28 19:32:21

On Mon, Apr 28, 2008 at 3:26 PM,  <Lance.Diduck_at_[hidden]> wrote:
>  >I want intrusive versions of stack/queue.  The freelist could also be
>  made to use the stack.
>  In my design I did make the free list allocator use the stack. The stack
>  assumes that its nodes are intrusive style.
>  However, I have never seen published an intrusive queue. The Micheal
>  Scott queue relies on dummy nodes, where the last node dequed serves as
>  the new dummy node, the previous one being freed. This makes it
>  difficult (or impossible) to make the nodes intrusive.

Indeed.  I have an intrusive version that is made mainly to organize
the code, it would not make much sense to use elsewhere.

>  >A simple freelist allocator that grabs blocks in pages would be
>  fantastic in a lot of cases.
>  The one I have does this. The drawback is that it make pointer
>  compression difficult. Compression is a good way to solve many ABA
>  problems on architectures where CAS2 is not available.
>  A compressing allocator/pointer pair would be required for any hope of
>  portability. Of course, noncompressing version should be available for
>  platofrm that could support it (such as Intel)

Yes, I actually combine the pointer and an ABA counter into one 64-bit
value for legacy AMD systems that don't support CAS2.  I have only
tested this on Windows - I have no idea how other OSes lay out their
memory.  This also introduces the idea of "preparing" a pointer for
CAS, though the algorithm code can still be generic enough for all
archs.

http://svn.int64.org/svnroot/int64/snips/lockfree/tagged_ptr.x64.hpp
http://svn.int64.org/svnroot/int64/snips/lockfree/basic_iqueue.hpp

(caveat, the code in that dir is actually outdated, I never got around
to finishing it.  would need some work to get good.)

> >The algo works inefficiently on IA64 because it copies the pointer when
>  IA64 only needs to copy the ABA counter >(it has cmp8xchg16b).
>  I have not seen an algorithm published that makes use of cmp8xchg16b.
>  Most algs I have seen want to swap both the pointer and the count, and
>  not just the pointer if the count is different.
>

The idea is that you compare just the counter, then exchange the whole
thing.  As far as I know there is no cmpxchg16b on IA64, so you have
to do it this way or not at all.

-- 
Cory Nelson