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!). 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
Fourth, on platforms where CAS is implemented using LL/SC (such as PowerPC and MIPS), it is possible to livelock. The problem with LL/SC on most platforms is that the write granulum for marking LL's address as "dirty" isn't just the memory pointed to by LL, but the whole cache line where the memory resides. On these platforms it is important to make sure that each "node" of the queue is located on a separate cache line.
just to make this clear... there are two types of "live-lock"s with ll/sc: a) one thread accessing memory between ll/sc b) two threads racing in a tight loop on ll/sc, continually aborting the other's operation If ll/sc is encapsulated in CAS, than a) is impossible There is nothing you can do about b) without changing the CAS implementation -- and there is generally no reason to even attempt that: With a window of usually two-three instructions between ll/sc, the rate of failure (i.e. repetition required due to interference) is surprisingly low even with two threads racing in tight ll/sc loops. Moving things to separate cache lines is a useful optimization (even without ll/sc), but nothing that is required.
You know, it's an interesting question whether CAS really implies a memory barrier or not. Obviously, you've implemented it that way, but I think it not need be that way. I think there's really no "standard" on CAS so we need to go with what is commonly accepted. It may be another question that would be good to ask at c.p.t If someone can answer this question, please chime in.
There are valid uses for CAS with and without various types of barriers. See the explicit memory_order specification in my atomic operations library. 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. Best regards, Helge