On Mon, Apr 28, 2008 at 3:26 PM, <Lance.Diduck@ubs.com> 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