Неблокирующая поточно-ориентированная реализация пула памяти - PullRequest
Новая
       55

Неблокирующая поточно-ориентированная реализация пула памяти

6 голосов
/ 19 ноября 2010

Мне был нужен простой неблокирующий пул памяти статического размера. Я не нашел такого в сети. Так что всем, кому нужно такое решение. Это бесплатно ... работает только на Win32.

С уважением,

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

И 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;
}

Ответы [ 2 ]

9 голосов
/ 19 ноября 2010

Проблема этого подхода в том, что в 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. Первоначальный поток прерывается (или на другом процессоре) серией malloc и free, поэтому A используется некоторое время и освобождается последним.
  4. Новое состояние списка: Root = A, A->next = ZZZ, ...
  5. Исходная нить просыпается и выполняет cmpxchg и успешно, потому что Root == r == A и, таким образом, устанавливает Root = ecx = B
  6. Теперь ваш список поврежден.

Вы можете решить эту проблему, если у вас есть двойное слово cmpxchg, например cmpxchg8b. Вы просто добавляете серийный номер рядом с заголовком списка, чтобы, если сравнение не удалось, вас прервали, как в (3) выше. Сторона free может использовать узкую версию, если каждый malloc обменивает указатель и увеличивает серийный номер.

3 голосов
/ 26 ноября 2010

Спасибо за любые комментарии. Этот может использоваться с WinXP и новее. Упомянутая выше реализация может все еще использоваться с архитектурой PowerPC (если у вас есть правильная реализация CompareAndSwap, см. "http://publib.boulder.ibm.com/infocenter/aix/v6r1/topic/com.ibm.aix.aixassem/doc/alangref/stwcx.htm").

С уважением,

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);
    }
};
...