Custom bounded memory pool allocator

Question

Recently I put together a custom fixed size (bounded) memory pool for my job system implementation to support its internal memory management. Since it will be accessed by different threads I want to make sure that the allocation and deallocation itself is atomic. However, I 'm not sure how to test it to make sure it's actually working. Also, it must support memory alignemnts as well to avoid false acquisition, with also avoiding locks and minimize waits.

These were my main criteria, however, I'd like to go further, and support growth in pool size or support objects (call ctor and dtor), etc.

This was my first quick and dirty attempt to implement this, and meeting my criteria.

#include <cstddef>
#include <atomic>

#include <cstdint>
#include <cassert>
#include <cstdlib>

namespace JobSystem
{
  class MemoryPoolAllocator
  {
  public:
    MemoryPoolAllocator(size_t elementSize, size_t numElements, size_t alignment = 16);

    MemoryPoolAllocator(const MemoryPoolAllocator & alloc) = delete;
    MemoryPoolAllocator & operator=(const MemoryPoolAllocator & rhs) = delete;
    MemoryPoolAllocator(MemoryPoolAllocator && alloc) = delete;
    MemoryPoolAllocator & operator=(MemoryPoolAllocator && rhs) = delete;

    ~MemoryPoolAllocator();

    void * Allocate() noexcept;
    void Deallocate(void * pBlock) noexcept;
    size_t ElementSize() const { return mElementSize; }
    size_t Capacity() const { return mPoolSize; }

  private:
    bool AllocatePool(size_t elementSize, size_t numElements, size_t alignment);
    void ReleasePool();

    size_t mPoolSize = 0;
    size_t mElementSize = 0;
    size_t mAlignment = 0;

    void * mMemory = nullptr;
    std::atomic<void **> mHead;
  };

} // namespace JobSystem


JobSystem::MemoryPoolAllocator::MemoryPoolAllocator(const std::size_t elementSize, const std::size_t numElements, std::size_t alignment)
{
  mHead.store(nullptr);
  const bool result = AllocatePool(elementSize, numElements, alignment);
  assert(result);
}

JobSystem::MemoryPoolAllocator::~MemoryPoolAllocator() { ReleasePool(); }

bool JobSystem::MemoryPoolAllocator::AllocatePool(const std::size_t elementSize, const std::size_t numElements, const std::size_t alignment)
{
  assert(mMemory == nullptr);

  mElementSize = elementSize;
  mAlignment = alignment;

  assert(mElementSize >= sizeof(void *));
  assert(mElementSize % mAlignment == 0);
  assert((mAlignment & (mAlignment - 1)) == 0);

  mPoolSize = (mElementSize * numElements) + alignment;
  mMemory = aligned_alloc(mAlignment, mElementSize * numElements);
  if (mMemory == nullptr) return false;

  void ** freeMemoryList = static_cast<void **>(mMemory);
  mHead.store(freeMemoryList);
  const auto endAddress = reinterpret_cast<uintptr_t>(freeMemoryList) + (elementSize * numElements);

  for (size_t element = 0; element < numElements; ++element) {
    const auto currAddress = reinterpret_cast<uintptr_t>(freeMemoryList) + element * mElementSize;
    const auto nextAddress = currAddress + mElementSize;
    void ** currMemory = reinterpret_cast<void **>(currAddress);
    if (nextAddress >= endAddress) { // last chunk
      *currMemory = nullptr;
    } else {
      *currMemory = reinterpret_cast<void *>(nextAddress);
    }
  }
  return true;
}

void * JobSystem::MemoryPoolAllocator::Allocate() noexcept
{
  assert(mMemory);
  void ** pHead = mHead.load(std::memory_order_relaxed);
  if (pHead != nullptr) {
    void * pBlock = reinterpret_cast<void *>(pHead);
    void ** pNext = static_cast<void **>(*pHead);
    mHead.compare_exchange_weak(pHead, pNext); 

    return pBlock;
  }

  return nullptr;
}

void JobSystem::MemoryPoolAllocator::Deallocate(void * pBlock) noexcept
{
  if (pBlock == nullptr) { return; }

  assert(mMemory);

  void ** pHead = mHead.load(std::memory_order_relaxed);

  if (pHead == nullptr) { 
    void ** pPrev = reinterpret_cast<void **>(pBlock);
    *pPrev = nullptr;
    mHead.compare_exchange_weak(pHead, pPrev); 
  } else {
    void ** ppReturnedBlock = pHead;
    void ** pPrev = reinterpret_cast<void **>(pBlock);
    *pHead = reinterpret_cast<void *>(ppReturnedBlock);
    mHead.compare_exchange_weak(pHead, pPrev); 
  }
}

void JobSystem::MemoryPoolAllocator::ReleasePool()
{
  std::free(mMemory);
  mMemory = mHead = nullptr;
}

Answer 1

Really cool idea for allocator, but style is awful

---

1) Comments/documentation

Memory stuff is perhaps the most complicated part of processes to understand. Please, don't leave your successors just idly looking at this code in terror, not knowing what follows what.

While function names are good, reasoning behind execution flow is hard to guess from first read.

2) throw vs noexcept

As allocators are part of that fringe between C and C++ API, it is extremely important to decide straight away on what side of the debate you are.

If you support "no exceptions" side, you must:
1) noexcept-qualify every function, and
2) return indication of error to the caller in all cases when that happens.

Your AllocatePool function returns bool indicating failure, but your constructor doesn't do anything to show it to caller
The moment it happens in production, caller will have absolutely no idea why nothing works

If you support "yes exceptions" side, you must:
1) use RAII
2) throw the moment error happens

So, I suggest instead of

if (mMemory == nullptr) return false;

just use

if (mMemory == nullptr) throw /*bad-alloc exception?*/;

As a reminder:
the noexcept side will allow everyone to use this allocator (and I'd prefer that if it's going to be left as memory-only), while
throw side will allow you to accept throwing constructors when your plans to support objects will happen

You might want to leave this as noexcept memory-only allocator as internal static member for exception-based object allocator built on top.

3) reinterpret_cast, uintptr_t

reinterpret_cast is an easy "code smell" - if you're using it, you understood something wrong.

In this case, you're misusing uintptr_t - in AllocatePool function:

const auto endAddress = reinterpret_cast<uintptr_t>(freeMemoryList) + (elementSize * numElements);

elementSize is about size in bytes, while it is quite possible that reinterpret_cast<uintptr_t>(freeMemoryList) will be address number in bits.

You should use static_cast<byte*> to increment in bytes.

And in other instances, it should be just changed to static_cast

4) Bad names

Bad names are the main problem both for debugging and for maintaining.

Currently, you have good names for input variables: mPoolSize, mElementSize, mAlignment. (and even then you need to add somewhere that last 2 are in bytes)
But everything else does not represent what it is:
- mMemory is address of a Pool, not "just memory". indicate that
- mHead is address of Head of available memory. indicate that
- in Allocate you use pHead, pBlock, pNext - instead of explaining what those variables do, you're using hungarian notation to show type that we already see right beside them

5) Small stuff

mPoolSize = (mElementSize * numElements) + alignment;
mMemory = aligned_alloc(mAlignment, mElementSize * numElements);

You allocate your pool, but you set your poolSize to be a bit bigger?

AllocatePool(const std::size_t elementSize, const std::size_t numElements, const std::size_t alignment)
  mElementSize = elementSize;
  mAlignment = alignment;

You push parameters from constructor into pool allocating function, which just takes parameters and puts them into member variables...
Have you never heard about member initializer list ?
This will even allow you to make variables constant and public (instead of private and with Getter).

In Deallocate:

Deallocate(void* pBlock)
...
void ** pHead = mHead.load(std::memory_order_relaxed);
...
else {
    void ** ppReturnedBlock = pHead;
    void ** pPrev = reinterpret_cast<void **>(pBlock);
    *pHead = reinterpret_cast<void *>(ppReturnedBlock);
    mHead.compare_exchange_weak(pHead, pPrev);

From what I deduced about the design, it is returning block that should be pointing to old Head, not the other way around

And FOR THE SAKE OF READABILITY, please add return; into your void-returning functions...

6) Trying to be clever is dumb. Part 1: memory_order

memory_order is a bag of worms. Simplest rule is to never use anything other than seq_cst with rare acq_rel. If you use it, if it appears in code, you must explain and prove EXTREMELY well that it is ok to not use default maximum synchronization.

Currently, you use memory_order_relaxed for allocation and deallocation. That pretty much means that state of atomic variable does not represent any process that uses non-atomic variables.
Do you already recognize why it is bad for memory allocator?

In short, right now it is possible for optimizer to reorder allocate->do_smth_with_ptr->deallocate into allocate->deallocare->do_wtevr with another thread (or even same one!) allocating same address.

And all that will be not only runtime, but build-time dependent!

And worst part? Even with all that cleverness, at best you'll get no benefits, because hardware vendors already more or less switched to seq_cst where it matters.

7) Trying to be clever is dumb. Part 2: compare_exchange_weak vs compare_exchange_strong

You must know instruments that you're using.

Both compare_exchange variants guarantee that they return true only if they succeeded. Strong one guarantees that if it returns false then change to atomic [made by another thread] has definitely happened. Weak one exchanges that guarantee for ability to work faster on certain architectures.

By default prefer Strong version as it will always do what it explains.

Right now you just use them as if you're always right and they will always succeed... Which reminds me:

8) Allocate can give same slot infinite amount of times. Deallocate can drop infinite amount of slots

You don't use return of compare_exchange.
You don't loop over compare_exchange.

In Allocate:

void ** pHead = mHead.load(); //million threads acquire same Head at the same time
if (pHead != nullptr) {
    void * pBlock = reinterpret_cast<void *>(pHead); //million threads compute same address
    void ** pNext = static_cast<void **>(*pHead);
    mHead.compare_exchange_strong(pHead, pNext); //one thread writes new Head, million-minus-one threads fail

    return pBlock; //million threads return with same address

in Deallocate:

Deallocate( void* pBlock) //million threads come in with their blocks

void ** pHead = mHead.load();//million threads get same Head at the same time

if (pHead == nullptr) { 
  void ** pPrev = reinterpret_cast<void **>(pBlock);
  *pPrev = nullptr; //million threads change their slots to point to nullptr
  mHead.compare_exchange_strong(pHead, pPrev); //one thread pushes its slot. million-minus-one threads fail
  return; //million threads return to caller, leaving their slots behind

9) Is there any need to be dynamic?

As I'm looking at this code, I don't see anything (other than use-case) that can stop this code from being a template on ElementSize and, optionally, on numElements.
Also I don't see that big of a bonus in performance as long as you dynamically allocate with malloc on heap, instead of compile-time-known size on stack (although you do get some bonus due to locality).

Just making a class with std::array<std::allocated_storage<ElementSize>, numElements> would give quite a speed up.

---

So far you have a lot to fix. But idea is cool and I guess it can work.