Fixed-Size Memory Pool with alignment

Question

After taking a break and reviewing the comments on my first attempt at creating a fixed-size memory pool, this is my second attempt.

The memory pool should allocate each block correctly aligned in memory, so that when I call placement new on the returned memory, it isn't misaligned. This is my main goal with this implementation.

The pool is implemented as a free-list, with each block looking something like this in memory:

 -------------------------------------------
 | Next Block Index | Padding | Object Data |
 -------------------------------------------

Here's my .h

#include <cstdint>
class FixedSizeMemoryPool
{
public:
 FixedSizeMemoryPool(const uint32_t objectSize, const uint32_t nObjects);
 ~FixedSizeMemoryPool();
 FixedSizeMemoryPool(const FixedSizeMemoryPool&)=delete;
 FixedSizeMemoryPool&operator=(const FixedSizeMemoryPool&)=delete;
 FixedSizeMemoryPool(FixedSizeMemoryPool&&)=delete;
 FixedSizeMemoryPool&operator=(FixedSizeMemoryPool&&)=delete;
 uint8_t* Alloc();
 void Free(void* data);
 const uint32_t GetCapacity() const;
 const uint32_t GetFreeBlockCount() const;
private:
 const uint32_t GetIndex(void* data) const;
 const uint32_t CalculatePadding(const uint32_t objectSize) const;
 uint32_t m_nFreeBlocks;
 uint32_t m_Capacity;
 uint32_t m_BlockSize;
 uint32_t m_PaddingSize;
 uint32_t m_NextFreeBlock;
 uint8_t* m_pData;
};

And the .cpp:

 FixedSizeMemoryPool::FixedSizeMemoryPool(const uint32_t objectSize,
 const uint32_t nObjects)
 : m_pData(nullptr), m_BlockSize(0), m_PaddingSize(0),
 m_Capacity(nObjects), m_nFreeBlocks(nObjects), m_NextFreeBlock(0)
{
 const uint32_t headerSize = sizeof(uint32_t);
 const uint32_t totalObjectSize = headerSize + objectSize;
 m_PaddingSize = CalculatePadding(totalObjectSize);
 m_BlockSize = totalObjectSize + m_PaddingSize;
 m_pData = new uint8_t[m_BlockSize * nObjects];
 //Set up the next free block
 for(unsigned int i = 0; i < nObjects; ++i)
 {
 uint8_t* hPtr = m_pData + (i * m_BlockSize);
 *((uint32_t*)hPtr) = i + 1;
 }
}
FixedSizeMemoryPool::~FixedSizeMemoryPool()
{
 delete[] m_pData;
}
uint8_t *FixedSizeMemoryPool::Alloc()
{
 if(m_NextFreeBlock == m_Capacity)
 {
 return nullptr;
 }
 uint8_t* ptr = m_pData + (m_NextFreeBlock * m_BlockSize);
 m_NextFreeBlock = *((uint32_t*)ptr);
 ptr += sizeof(uint32_t);
 ptr += m_PaddingSize;
 --m_nFreeBlocks;
 return ptr;
}
void FixedSizeMemoryPool::Free(void* data)
{
 uint8_t* pData = (uint8_t*)data - m_PaddingSize - sizeof(uint32_t);
 *((uint32_t*)pData) = m_NextFreeBlock;
 m_NextFreeBlock = GetIndex(data);
 ++m_nFreeBlocks;
}
const uint32_t FixedSizeMemoryPool::GetIndex(void *data) const
{
 return ((uint8_t*)data - m_pData) / m_BlockSize;
}
const uint32_t FixedSizeMemoryPool::CalculatePadding(
 const uint32_t objectSize) const
{
 //Check the object size is a power of 2
 if((objectSize & (objectSize - 1)) != 0)
 {
 //Get next highest power of 2
 uint32_t paddingSize = 0;
 paddingSize = objectSize - 1;
 paddingSize |= m_PaddingSize >> 1;
 paddingSize |= m_PaddingSize >> 2;
 paddingSize |= m_PaddingSize >> 4;
 paddingSize |= m_PaddingSize >> 8;
 paddingSize |= m_PaddingSize >> 16;
 ++paddingSize ;
 paddingSize = paddingSize - objectSize;
 return paddingSize;
 }
 return 0;
}
const uint32_t FixedSizeMemoryPool::GetCapacity() const
{
 return m_Capacity; 
}
const uint32_t FixedSizeMemoryPool::GetFreeBlockCount() const
{
 return m_nFreeBlocks;
}

• Harald Scheirich: It's always helpful for reviewers to see your class being used, including testcode or just a simple use case would would be great
• Toby Speight: Why use uint32_t (presumably intended to be std::uint32_t, though that's not a given) for the object size and count, instead of std::size_t? Is there a good reason to limit objects to be less than 4GB, or to hold more than 4 billion of them?

Answer 1

first of all you hold Next Block Index in allocated block. but you not use it . Next Block Index (which is implicit pointer to next free block) used only in free block. as result you not need Next Block Index and Padding in allocated block. the Object Data must begin at begin of block. this give serious optimization by memory size and simplify code.

also instead index (implicit pointer) better use explicit pointer to next free block (or 0 if no more free blocks). this yet more simplify code.

next your code is not thread safe and not design to allocate/free in concurrent from multiple threads. however this is very easy can be implemented.

finally CalculatePadding simply wrong. impossible calculate align of object by it size. different objects with same size, can have different align.

first we need implement structure describes an entry in a block linked list:

struct LE 
{
 LE* next;
 static void Push(LE* head, LE* entry)
 {
 LE *_next = head->next, *next;
 for( ; ; _next = next)
 {
 entry->next = _next;
 next = (LE*)InterlockedCompareExchangePointerRelease(
 (void**)&head->next, entry, _next);
 if (next == _next)
 {
 return;
 }
 }
 }
 static LE* Pop(LE* head)
 {
 LE* _entry = head->next, *entry;
 for ( ;_entry;_entry = entry)
 {
 entry = (LE*)InterlockedCompareExchangePointerAcquire(
 (void**)&head->next, _entry->next, _entry);
 if (entry == _entry)
 {
 return entry;
 }
 }
 return 0;
 }
};

we put this LE at begin of every free block. this will pointer to next free block (or 0 if this is the last free block). instead of index. with this we can allocate block by LE::Pop and free block by LE::Push.

#define DEBUG_CHECK 1
class FixedSizeMemoryPool
{
 LE m_head;
 void* m_buf;
 void (__stdcall * m_Free)(void*);
#if DEBUG_CHECK
 ULONG m_count;
#endif
public:
 FixedSizeMemoryPool() { m_buf = 0; }
 ~FixedSizeMemoryPool();
 void* Alloc()
 {
 return LE::Pop(&m_head);
 }
 void Free(void* data)
 {
 LE::Push(&m_head, reinterpret_cast<LE*>(data));
 }
 bool Create(ULONG objectSize, ULONG nObjects, 
 void* (__stdcall* XxxAllocate)(ULONG), 
 void (__stdcall * XxxFree)(void*));
};
FixedSizeMemoryPool::~FixedSizeMemoryPool()
{
 if (m_buf) 
 {
#if DEBUG_CHECK
 ULONG count = m_count;
 if (LE* next = m_head.next)
 {
 do 
 {
 --count;
 } while (next = next->next);
 }
 if (count)
 {
 __debugbreak();
 }
#endif
 m_Free(m_buf);
 }
}
bool FixedSizeMemoryPool::Create(ULONG objectSize, ULONG nObjects, 
 void* (__stdcall* XxxAllocate)(ULONG),
 void (__stdcall * XxxFree)(void*))
{
 if (!objectSize || !nObjects || objectSize > MAXLONG)
 {
 return false;
 }
 if (objectSize < sizeof(LE))
 {
 // we need space for LE in block
 objectSize = sizeof(LE);
 }
 // must be aligned how minimum as LE
 objectSize = (objectSize + alignof(LE) - 1) & ~(alignof(LE) - 1);
 ULONGLONG size = (ULONGLONG)objectSize * (ULONGLONG)nObjects;
 if (size > MAXULONG)
 {
 return false;
 }
 union {
 void* buf;
 char* pb;
 LE* entry;
 };
 if (buf = XxxAllocate((ULONG)size))
 {
#if DEBUG_CHECK
 m_count = nObjects;
#endif
 m_buf = buf;
 m_Free = XxxFree;
 LE* next = 0;
 do 
 {
 entry->next = next, next = entry;
 } while (pb += objectSize, --nObjects);
 m_head.next = next;
 return true;
 }
 return false;
}

note that client of FixedSizeMemoryPool must provide itself routines for allocate/free block of memory, where pool will be implemented. this give ability implement different memory types. also if objects(pool blocks) require special align (more than default allocation align), user implement this in allocate routine. say if we not need extended alignment for object, we can use

void* __stdcall XxxAlocate(ULONG s)
{
 return new char[s];
}
void __stdcall XxxFree(void* data)
{
 delete [] data;
}

if we need extended alignment - say want 64byte align for blocks in pool:

void* __stdcall XxxAlocate(ULONG s)
{
 return _aligned_malloc(s, 64);
}
void __stdcall XxxFree(void* data)
{
 _aligned_free(data);
}

and of course size of object (block) must be multiple of object(block) align