Preliminary Review Request (2): boost-memory
What is new? 1. Lock-free free list (workarounds ABA problem). 2. Provide both region allocators (boost::auto_alloc, boost::scoped_alloc) and general-purpose allocators (boost::gc_alloc). 3. Notes: To fit for C++ exception semantics (See the example named "testExceptionSemantics"), I updated the specification of GC Allocator. Highlights: 1. Allocating memory is very fast. 2. No memory leaks. No need to delete objects manually. Or forgetting to delete objects is allowed. Thanks: * Steven Watanabe * Scott McMurray * Tim * Diduck, Lance To gain the source code, you can: 1. Svn checkout http://winx.googlecode.com/svn/tags/boost-memory-0.2.00/. 2. Svn checkout http://svn.boost.org/svn/boost/sandbox/memory/. --- What is boost-memory? It provides allocators named "GC Allocator". Note "GC Allocator" isn't GC. GC Allocator is different from STL Allocator. The following is minimum specification for GC Allocator: typedef void (*DestructorType)(void* data); concept GCAllocator { // Allocate memory without given a cleanup function void* allocate(size_t cb); // Allocate unmanaged memory with a cleanup function void* unmanaged_alloc(size_t cb, DestructorType fn); // Commit unmanaged memory to be managed. void* manage(void* p, destructor_t fn); // Deprecated: allocate memory with a cleanup function void* allocate(size_t cb, DestructorType fn) { return manage(unmanaged_alloc(cb, fn), fn); } // Cleanup and deallocate all allocated memory by this GC Allocator void clear(); // Swap two GCAllocator instances void swap(GCAllocator& o); }; For more information about GC Allocator, refer to http://www.codeproject.com/KB/cpp/gc-allocator.aspx
See http://cpp.winxgui.com/boost-memory-0-2-00 On Fri, May 16, 2008 at 5:33 PM, shiwei xu <xushiweizh@gmail.com> wrote:
What is new?
1. Lock-free free list (workarounds ABA problem). 2. Provide both region allocators (boost::auto_alloc, boost::scoped_alloc) and general-purpose allocators (boost::gc_alloc). 3. Notes: To fit for C++ exception semantics (See the example named "testExceptionSemantics"), I updated the specification of GC Allocator.
Highlights:
1. Allocating memory is very fast. 2. No memory leaks. No need to delete objects manually. Or forgetting to delete objects is allowed.
Thanks:
* Steven Watanabe * Scott McMurray * Tim * Diduck, Lance
To gain the source code, you can:
1. Svn checkout http://winx.googlecode.com/svn/tags/boost-memory-0.2.00/. 2. Svn checkout http://svn.boost.org/svn/boost/sandbox/memory/.
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 ... 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... cheers, tim -- tim@klingt.org http://tim.klingt.org Which is more musical, a truck passing by a factory or a truck passing by a music school? John Cage
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
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
participants (2)
-
shiwei xu -
Tim Blechmann