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.
hm, afaiu the CAS in (4) and (6) are the linearization points of the stack/fifo algorithms ... anyway, if you need ordered memory access, you should add a memory barrier ...
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;
check the stl_allocator_freelist branch of my git repository ;)
BTW, I don't know why free list don't need any ABA prevention. And in your freelist implementation I think that
please forget, what i wrote ... this version of the freelist requires ABA prevention ... there is a hazard-ptr based implementation of a freelist, which is not aba-prone, though ... cheers, tim -- tim@klingt.org http://tim.klingt.org The price an artist pays for doing what he wants is that he has to do it. William S. Burroughs