Non-blocking streaming implementation of the memory pool

Question

I need a simple non-blocking memory pool the size of a static block. I did not find this on the Internet. So everyone who needs such a solution. This free ... only works with Win32.

Yours faithfully,

Friedrich

#ifndef MEMPOOL_HPP_INCLUDED #define MEMPOOL_HPP_INCLUDED #include "atomic.hpp" #include "static_assert.hpp" #pragma warning( push ) #pragma warning( disable : 4311 ) // warning C4311: 'Typumwandlung' /// @brief Block-free memory-pool implemenation /// @tparam T Object-type to be saved within the memory-pool. /// @tparam S Capacy of the memory-pool. template <typename T, int S> class MemoryPool { private: STATIC_ASSERT(sizeof(int) == sizeof(void*), "Well, ..."); public: /// @brief Object-type saved within the pool. typedef T TYPE; enum { /// @brief Capacy of the memory-pool. SIZE = S }; private: /// @brief Chunks, that holds the memory struct Chunk { /// @brief Single-linked list. Chunk* Next; /// @brief The value /// We do not call the default constructor this way. char Value[sizeof(TYPE)]; }; /// @brief The root object. Chunk* Root; /// @brief The pool Chunk Pool[SIZE]; private: // do not allow copying MemoryPool(const MemoryPool&); MemoryPool& operator=(const MemoryPool&); void free(Chunk* c) { c->Next = Root; while(!CompareAndSwap((int*)&Root, (int)c->Next, (int)c)) { c->Next = Root; } } public: /// Default constructor /// Creates an empty memory-pool. /// Invalidates all the memory. MemoryPool() : Root(0) { for(int i = 0; i < SIZE; i++) { MemoryPool::free(&Pool[i]); } } /// @brief Frees a chunk of memory, that was allocated by MemoryPool::malloc /// @param _Chunk A chunk of memory, that was allocated by MemoryPool::malloc /// This function will not call the destructor. /// Thread-safe, non-blocking void free(T* _Chunk) { if(!_Chunk) return; Chunk* c = (Chunk*)((int)(_Chunk) - sizeof(Chunk*)); if(c < &Pool[0] || c > &Pool[SIZE - 1]) return; MemoryPool::free(c); } /// @brief Returns a pointer to a chunk of memory /// @return 0 on a memory shortage /// @return A pointer to a chunk of memory /// This function will not call the constructor. /// Thread-safe, non-blocking T* malloc() { Chunk* r = Root; if(!r) return 0; while(!CompareAndSwap((int*)&Root, (int)r, (int)r->Next)) { r = Root; if(!r) return 0; } return &(r->Value); } }; #pragma warning( pop ) #endif // MEMPOOL_HPP_INCLUDED 

And CompareAndSwap

 /// @brief Atomic compare and set /// Atomically compare the value stored at *p with cmpval and if the /// two values are equal, update the value of *p with newval. Returns /// zero if the compare failed, nonzero otherwise. /// @param p Pointer to the target /// @param cmpval Value as we excpect it /// @param newval New value static inline int CompareAndSwap(volatile int *_ptr, int _old, int _new) { __asm { mov eax, [_old] // place the value of _old to EAX mov ecx, [_new] // place the value of _new to ECX mov edx, [_ptr] // place the pointer of _ptr to EDX lock cmpxchg [edx], ecx // cmpxchg old (EAX) and *ptr ([EDX]) } return 1; } 

Answer 1

The problem with this approach is that in malloc there is a race condition:

 while(!CompareAndSwap((int*)&Root, (int)r, (int)r->Next)) 

Consider the following sequence of operations:

• Initially, Root = A, A->next = B, ...
• One thread reads r = Root , so r = A and (in register) it reads ecx = r->Next = B
• The original thread is unloaded (or on another CPU) a series of malloc and free occurs, so A used for a while and freed last.
• The state of the new list Root = A, A->next = ZZZ, ...
• The original thread wakes up and makes cmpxchg and succeeds because Root == r == A and thus sets Root = ecx = B
• Now your list is corrupted.

You can solve this problem if you have a double word cmpxchg , for example cmpxchg8b . You simply include the serial number next to the list heading so that if the comparison fails, if you are interrupted, as in (3) above. The free side can use the narrow version if each malloc swaps the pointer and increments the serial number.

Answer 2

Thanks for any comments. This can be used with WinXP and newer. The above implementation can still be used with the PowerPC architecture (if you have the correct CompareAndSwap implementation, see "http://publib.boulder.ibm.com/infocenter/aix/v6r1/topic/com.ibm.aix. Aixassem / doc / alangref / stwcx.htm ").

Yours faithfully,

Friedrich

 /// @brief Lock-free memory-pool implementation /// @tparam T Type stored within the memory-pool /// @tparam S Number of elements stored in the memory-pool. template <typename T, int S> class MemoryPool { public: /// @brief Type stored within the memory-pool. typedef T TYPE; enum { /// @brief Number of enrties in the memory-pool. SIZE = S }; private: // we need to align the memory-pool-chunks. #pragma pack(push, MEMORY_ALLOCATION_ALIGNMENT) /// @brief The memory-chunk used by the memory-pool. template <typename TYPE> struct MemoryChunk { /// @brief Next entry in the single-linked list. SLIST_ENTRY Next; /// @brief The value stored within the memory-pool. /// Do not call the constructor char Value[sizeof(TYPE)]; }; typedef MemoryChunk<TYPE> CHUNK_TYPE; #pragma pack(pop, MEMORY_ALLOCATION_ALIGNMENT) /// @brief Head of the single-linked list. SLIST_HEADER Head; /// @brief The pool itself CHUNK_TYPE Pool[SIZE]; // no copying is supported MemoryPool& operator=(const MemoryPool&); MemoryPool(const MemoryPool&); public: /// @brief Constructs the memory-pool. MemoryPool() { InitializeSListHead(&Head); for(int i = 0; i < SIZE; i++) { InterlockedPushEntrySList(&Head, &Pool[i].Next); } } /// @brief Free the memory-pool. ~MemoryPool() { InterlockedFlushSList(&Head); } /// @brief Allocates a memory chunk /// @return 0 if none is free /// @return Pointer to a free memory chunk (the constructor is not called!) TYPE* Allocate() { CHUNK_TYPE* c = reinterpret_cast<CHUNK_TYPE*>(InterlockedPopEntrySList(&Head)); if(c) return reinterpret_cast<TYPE*>(&c->Value[0]); else return 0; } /// @brief Deallocates a memory chunk (the destructor is not called) /// @param c Point to the memory-chunk allocated by us. void Deallocate(void* c) { if(c < static_cast<void*>(&Pool[0]) || c > static_cast<void*>(&Pool[SIZE])) return; // was not allocated by us char* p = static_cast<char*>(c); p -= sizeof(SLIST_ENTRY); CHUNK_TYPE* t = reinterpret_cast<CHUNK_TYPE*>(p); InterlockedPushEntrySList(&Head, &t->Next); } };