1. Lock-free free list (workarounds ABA problem).
i didn't read all the code, but in tagged_ptr::set you write:
Type vTag = m_p[1]; // NOTE: getting 'tag' before getting 'data'! Type vOld = m_p[0];
... i am not sure, whether it is necessary to get tag before data, but if you need to do that, you have to add a memory barrier, otherwise compiler or cpu may reorder the memory access ...
Suppose we write the following code: Type vOld = m_p[0]; Type vTag = m_p[1]; ... atomic if (m_p[0] == vOld && m_p[1] == vTag) then set m_p[0] = vNew, m_p[1] = vTag+1. Let's image the following executing order: 1. p1: vOld1 = m_p[0]; 2. p2: vOld2 = m_p[0]; 3. p2: vTag2 = m_p[1]; // = Tag ... 4. p2: atomic if (m_p[0] == vOld2 && m_p[1] == Tag) then set m_p[0] = vNew2, m_p[1] = Tag+1 5. p1: vTag1 = m_p[1]; // = Tag+1 ... 6. p1: atomic if (m_p[0] == vOld1 && m_p[1] == Tag+1) then set m_p[0] = vNew1, m_p[1] = Tag+2 Clearly, if vNew2 == vOld1, then it is another ABA problem. So, we should read Tag before reading Data. btw, if you are using the stack just as free list, i don't think you need
any aba prevention ... also, what about grabbing the code from my freelist implementation?
http://tim.klingt.org/git?p=boost_lockfree.git;a=blob;f=boost/lockfree/freel...
I wrote lock-free codes for the first time. So I didn't use your implementation for exercises. :) And your freelist implementation don't fit for me. I need a customizable freelist to specify Alloc implementation. It seems like this: template <typename T, typename Alloc, std::size_t max_size = 64> class freelist; BTW, I don't know why free list don't need any ABA prevention. And in your freelist implementation I think that struct freelist_node { tagged_ptr<struct freelist_node> next; }; can be: struct freelist_node { freelist_node* next; }; Here we don't need a tagged_ptr. Best Regards, Shiwei Xu