非阻塞線程安全內存池實現

Question

我需要一個簡單的非阻塞靜態塊大小的內存池。我在網上找不到這樣的內容。所以每個人都需要這樣的解決方案。這個是免費的...只適用於Win32。

最好的問候，

弗里德里希

#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 

而且比較並交換

/// @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

這種方法的問題是，有在malloc競爭條件：

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

考慮操作的順序如下：

1. 最初Root = A, A->next = B, ...
2. 一個線程讀取r = Root所以r = A和（到寄存器中）讀取ecx = r->Next = B
3. 初始線程被搶佔（或，在另一CPU）的一系列malloc和free發生，使A被用了一段時間，最後被釋放。
4. 新列表狀態Root = A, A->next = ZZZ, ...
5. 原來的線程醒來並做cmpxchg和成功，因爲Root == r == A，從而將Root = ecx = B
6. 現在你的列表已損壞。

如果您有雙字cmpxchg，例如cmpxchg8b，則可以解決此問題。您只需在列表頭旁邊包含一個序列號，以便在上面（3）中如果您中斷比較就會失敗。 free方可以使用窄版，只要每個malloc都交換指針和遞增序號。

Answer 2

謝謝你的任何意見。這個可以用於WinXP和更新的版本。前面提到的實現可能仍然可以與PowerPC體系結構一起使用（如果您有適當的CompareAndSwap實現，請參閱「http://publib.boulder.ibm.com/infocenter/aix/v6r1/topic/com.ibm.aix」。 aixassem/DOC/alangref/stwcx.htm「）。

最好的問候，

弗里德里希

/// @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); 
    } 
};