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

From: shiwei xu (xushiweizh_at_[hidden])
Date: 2008-05-17 05:24:05

> > 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/freelist.hpp
>

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