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). I was doing all sorts of allocations and looking at the returned pointer. What I found was that the only the two low bits were always the same (obviously because malloc has to return aligned data). All other bits could be different depending on the size of the requested allocation. I think they were also depended on the thread that was requesting the allocation, but I'm not sure on this point. So, other than the 2 lower bits, you can't assume you can use any more. And 2 bits seems kinda low for an ABA tag.
all 32 bit platforms that i know of are using the full 32bit as address space (the lower two bits are 0 because of 32bit alignment) ... on 64bit platforms it is quite different ... ppc64, ia64 and x86_64 all use just a part of the full address space (iirc 48 bit for x86_64) ... the rest should be usable as aba prevention tag.
1. You're missing write barrier after a call to alloc_node(). Rational: alloc_node sets the "next" pointer of the newly allocated node to NULL. That is a store to shared memory. Setting next pointer to NULL has to be observable to other threads BEFORE they observe the inserted node. If you don't insert a write barrier, it is possible for other threads to see the new element in the list before element's next pointer is initialized with NULL.
i was assuming, that cas issues a full memory barrier (at least my cas implementation does), so i don't think, this would be an issue.
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.
the c++0x atomic library handles it explicitly ... compare_exchange has takes the behavior as argument ...
i am currently porting the data structures to the boost.atomic proposal, which provides better language support to specify the memory order constraints. the code is available from a separate branch of my repository. i would be curious, if you could have a look at that implementation as well.
Definitely. How can I get to your latest code?
the code can be found in my git repository [1], branch lockfree-atomic ... unfortunately, i am stuck with the fifo implementation, which is currently broken, although i cannot see why :/ thnx, tim [1] http://tim.klingt.org/git?p=boost_lockfree.git -- tim@klingt.org http://tim.klingt.org Relying on the government to protect your privacy is like asking a peeping tom to install your window blinds. John Perry Barlow