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
(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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk