Re: [boost] Preliminary Review Request (2): boost-memory

From: Tim Blechmann (tim_at_[hidden])
Date: 2008-05-17 08:09:41

> 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_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