From: Tim Blechmann (tim_at_[hidden])
Date: 2008-05-17 08:09:41
> Suppose we write the following code:
> Type vOld = m_p;
> Type vTag = m_p;
> atomic if (m_p == vOld && m_p == vTag) then set m_p = vNew,
> m_p = vTag+1.
> Let's image the following executing order:
> 1. p1: vOld1 = m_p;
> 2. p2: vOld2 = m_p;
> 3. p2: vTag2 = m_p; // = Tag
> 4. p2: atomic if (m_p == vOld2 && m_p == Tag) then set m_p =
> vNew2, m_p = Tag+1
> 5. p1: vTag1 = m_p; // = Tag+1
> 6. p1: atomic if (m_p == vOld1 && m_p == Tag+1) then set m_p =
> vNew1, m_p = 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
> 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
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 ...
-- tim_at_[hidden] http://tim.klingt.org The price an artist pays for doing what he wants is that he has to do it. William S. Burroughs
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk