A Pool-based Memory Management

Question

I wrote a memory management class that is supposed to be used in a game. I decided to use "Blocks" as an in-code representation. It is written in MSVC++ and is currently not meant for portability. I am actually not really experienced in C++ - I just wanted to "try it out".
The pool is not meant to grow - it is initialized once and can be reset (for example on Level load). The BlockHeader is both an explicit and implicit free list. It contains the next/previous free and the next/previous physical Block. Here is an outdated image of how the internal representation is :

#pragma once
#include <stdint.h>
#include <memory>
#include <iostream>
#include "Game/debug/assert.h"
#include "Game/debug/log.h"
#include <type_traits>
namespace T5M::Memory {
    //Block Size suggestions
    enum class BlockSize : size_t {
        Minimal = 4,
        Tiny = 8,
        Small = 16,
        Medium = 32,
        Big = 64,
        Huge = 128,
    };

    //A multi purpose Memory pool
    template<unsigned BlkSz>
    class Pool {
        static_assert(BlkSz > 0 && (BlkSz & (BlkSz - 1)) == 0,"Block Size needs to be PoT!");
        using Size = size_t;
        using Byte = uint8_t;
        using Magic = uint32_t;
        //Returns the number of Blocks needed for the number of Bytes
        static constexpr Size getBlockCount(Size bytes) {
            return (bytes + (static_cast<Size>(BlkSz) - 1)) / static_cast<Size>(BlkSz);
        }
        //Block representation

        struct Block {
            Byte data[static_cast<Size>(BlkSz)];
        };
        // Block Header Data. Contains either Data about Free Blocks in the case of Free
        // Or Number of Blocks that were allocated in the case of Used
        union BlockHeader;
        struct BlockHeaderData {
            Magic magic;
            //pointer to the next BlockHeader, nullptr if tail
            BlockHeader* nextFreeBlock;
            //pointer to the previous BlockHeader, nullptr if head
            BlockHeader* previousFreeBlock;
            //Number of Free Blocks / Used Blocks
            Size managedBlocks;
            //Whether this Header is Free or Used
            bool isFree;
            //pointer to the next physical block header
            BlockHeader* nextPhysicalBlock;
            //pointer to the previous physical block header
            BlockHeader* previousPhysicalBlock;
            //pointer to first physical block header
            BlockHeaderData() : magic(MAGIC), nextFreeBlock(nullptr), previousFreeBlock(nullptr), managedBlocks(0), nextPhysicalBlock(nullptr), previousPhysicalBlock(nullptr), isFree(false) {}
        };
        union BlockHeader {

            BlockHeaderData data;
            //Padding to ensure BlockHeader is always the next multiple of BlkSz blocks large
            Block padding[getBlockCount(sizeof(BlockHeaderData))];
            BlockHeader() : data(BlockHeaderData()) {};
        };

    private:
        static constexpr Magic MAGIC = 0xDEADBEEF;
        Size allocatedBlockCount;
        Size allocatedBytesCount;
        const std::unique_ptr<Block> allocatedBlocks;
        BlockHeader* head;
        BlockHeader* firstPhysicalBlock;
        void initialize() {
            std::memset(allocatedBlocks.get(), 0, allocatedBytesCount);
            // Place initial BlockHeader at the beginning of all blocks
            head = new(allocatedBlocks.get())BlockHeader();
            head->data.nextFreeBlock = nullptr;
            head->data.managedBlocks = allocatedBlockCount - getHeaderBlockCount();
            head->data.previousFreeBlock = nullptr;
            head->data.nextPhysicalBlock = nullptr;
            head->data.previousPhysicalBlock = nullptr;
            this->firstPhysicalBlock = head;
        }


    public:
        Pool(Size numBlocks) : allocatedBlockCount(numBlocks), allocatedBytesCount(sizeof(Block)* numBlocks) , allocatedBlocks(new Block[numBlocks]) {
            initialize();
            Log("Pool Init: Initialized Pool with " << numBlocks << " Blocks")
            Log("Pool Init: Free Blocks :" << head->data.managedBlocks)
        }
    private:
        constexpr Size getHeaderBlockCount() const {
            return getBlockCount(sizeof(BlockHeader));
        };

        //try coalescing with the next block in the list
        void tryCoalesce(BlockHeader* origin) {
            BlockHeader* left = origin->data.previousPhysicalBlock;
            BlockHeader* right = origin->data.nextPhysicalBlock;
            if (right != nullptr && right->data.isFree)
                coalesce(origin, right);
            if (left != nullptr && left->data.isFree)
                coalesce(left, origin);
        }

        void coalesce(BlockHeader* left, BlockHeader* right) {
            Log("Coalescing BlockHeader at " << left << " & " << right )
            //accumulate free blocks + now obsolete header data
            left->data.managedBlocks += right->data.managedBlocks;
            left->data.managedBlocks += getHeaderBlockCount();
            //relink so left points to right->next
            left->data.nextFreeBlock = right->data.nextFreeBlock;
            left->data.nextPhysicalBlock = right->data.nextPhysicalBlock;

            //relink so right->next->previous points to left
            if (right->data.nextFreeBlock != nullptr) {
                right->data.nextFreeBlock->data.previousFreeBlock = left;
            }
        }
    public:
        template <typename T,typename ... Args>
        [[nodiscard]]T* malloc(Size count = 1,Args&&...args) noexcept {
            //Forbid allocation of size 0
            if (count < 1) return nullptr;
            //assertm(count >= 1,"Allocation Size must be greater than 0!");
            // calculate the amount of blocks we want
            Size requestedBlocks = getBlockCount(sizeof(T) * count);
            Log("Malloc: Requested Blocks for " << typeid(T).name() << " x " << count << ": " << requestedBlocks)
            BlockHeader* currentNode = head;
            //Make sure we have enough space for one Block Header and one free Block!
            while (currentNode != nullptr && currentNode->data.managedBlocks < requestedBlocks+getHeaderBlockCount()) {
                assertm(currentNode->data.magic == MAGIC, "Pool is corrupt");
                currentNode = currentNode->data.nextFreeBlock;
            }
            //We could not find a block of suitable size
            assertm(currentNode != nullptr, "Pool is full");
            //Free Blocks are directly behind BlockHeader
            Block* blockToReturn = reinterpret_cast<Block*>(currentNode + 1);
            Log("Malloc: Return block at " << blockToReturn)
            //The current node will be removed from Free List, so keep the number of Blocks that will be deallocated for later!
            Size numFreeBlocksAfterSplit = currentNode->data.managedBlocks - ((getHeaderBlockCount()));
            currentNode->data.managedBlocks = requestedBlocks;
            currentNode->data.isFree = false;
            Block* splitBlock = blockToReturn + requestedBlocks + 1;
            //Place a new BlockHeader right after the Requested Block
            BlockHeader* newHead = new(splitBlock)BlockHeader();
            Log("Malloc: New Head at " << newHead)
            newHead->data.previousPhysicalBlock = currentNode;
            newHead->data.nextPhysicalBlock = currentNode->data.nextPhysicalBlock;
            currentNode->data.nextPhysicalBlock = newHead;
            newHead->data.isFree = true;
            head = newHead;
            head->data.nextFreeBlock = currentNode->data.nextFreeBlock;
            head->data.managedBlocks = numFreeBlocksAfterSplit;
            Log("Malloc: New Free Blocks : " << numFreeBlocksAfterSplit)
            return new(blockToReturn)T(std::forward<Args>(args)...);

        }
        void free(void* ptr) {
            assertm((ptr >= allocatedBlocks.get() && ptr < (allocatedBlocks.get() + allocatedBlockCount)), "memory must be in Pool range!");
            //Go to the point infront of the pointer to free, where an old header was before
            BlockHeader* blockHead = (reinterpret_cast<BlockHeader*>(ptr)) - 1;
            if (blockHead->data.magic == MAGIC) {
                Log("Free: BlockHeader at " << blockHead )
                BlockHeader* oldHead = head;
                BlockHeader* newHead = blockHead;
                head = newHead;
                head->data.isFree = true;
                head->data.nextFreeBlock = oldHead;
                oldHead->data.previousFreeBlock = head;

                //Now try to coalesce with the next and previous physical block
                tryCoalesce(blockHead);
                tryCoalesce(oldHead);
            }
        }

        void reset() {
            initialize();
        }
    };
}

content of assert.h:

#pragma once
#include <cassert>
#ifndef assertm
#define assertm(exp, msg) assert(((void)msg, exp))
#endif

content of log.h:

#pragma once
#if _DEBUG
#include <iostream>
#include <ostream>
#ifndef Log
#define Log(x) std::cout << x << std::endl;
#endif
#else 
#define Log(x)
#endif

Answer 1

Observation

There is no destructor (so this simply leaks memory when it is done).

The fact that it leaks is probably a blessing as it does not obey the rule of three/five. So copying or assigning this object is probably not going to work the way you want it (though it is hard to tell what that is since you don't document it). Either implement these methods or delete them.

Overall I find the code overall dense to read. Please add some vertical white space and group things logically. I also hate the useless comments. Comments should not explain the code (the code explains the code with good use of variable/function names). If you do this you have to deal with comment written over time. Good comments explain WHY.

        //pointer to the previous physical block header  (Are you sure this is necessary!)
        BlockHeader* previousPhysicalBlock;

Would love to see some unit tests that validate that the state is correct after usage. This is something you definitely want to test a lot before use.

Code Review

This is a bit screwy:

#if _DEBUG
#include <iostream>
#include <ostream>

#ifndef Log
#define Log(x) std::cout << x << std::endl;
#endif

#else               // Notice this else belongs to the top _DEBUG
                    // Notice that if _DEBUG is defined you test
                    // for the existence of Log but not here!
#define Log(x)
#endif

---

This looks like a bug.

        BlockHeader* currentNode = head;
        while (currentNode != nullptr && currentNode->data.managedBlocks < requestedBlocks+getHeaderBlockCount()) {

What happens when the head is not part of the "Free" block chain. You probably need one more statement:

 BlockHeader* currentNode = head;
 if (!currentNode->isFree) {
     currentNode = currentNode->nextFreeBlock;
 }

I would move those two lines into its own self documenting function.

 BlockHeader* getHeadOfFreeList()
 {
         ....
 }

---

This looks like another bug:

   void coalesce(BlockHeader* left, BlockHeader* right) {

        ....
        //relink so right->next->previous points to left
        if (right->data.nextFreeBlock != nullptr) {
            right->data.nextFreeBlock->data.previousFreeBlock = left;
        }
  }

You just coalesced blocks. Does that not mean that the physical block does not exist any more? You removed the physical block from this blocks chain. Why are you not removing if from the next blocks chain. Your physical chains are no longer consistent in both directions.

---

The pointer arithmetic gets overly complicated hard for me to follow at this point. So I will assume it is wrong until you have unit tests to prove it is correct.

---

The design is a bit simplistic. You only have a physical list and a free list.

Most designs for pools I see is a list of sizes. With each size being a list of free chunks. So when a chunk is freed you add it to a list of chunks of that size. When an allocation is done you try and re-use already chunked memory of the correct size only splitting of unused memory if chunks of the correct size are not available.

This reduces the amount of searching you have to do (you don't traverse the whole list looking for free chunks that are not available).

You can optimize splitting. If there is no free are left try splitting a chunk that is twice the size into two chunks of a useful size (leaves you with less small bits lying around that are unusable, which reduces collation calls).