# A Pool-based Memory Management

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
Magic magic;
//pointer to the next BlockHeader, nullptr if tail
//Number of Free Blocks / Used Blocks
Size managedBlocks;
//Whether this Header is Free or Used
bool isFree;
//pointer to the next physical block header
//pointer to the previous physical block header
//pointer to first physical block header
BlockHeaderData() : magic(MAGIC), nextFreeBlock(nullptr), previousFreeBlock(nullptr), managedBlocks(0), nextPhysicalBlock(nullptr), previousPhysicalBlock(nullptr), isFree(false) {}
};

//Padding to ensure BlockHeader is always the next multiple of BlkSz blocks large
};

private:
static constexpr Magic MAGIC = 0xDEADBEEF;
Size allocatedBlockCount;
Size allocatedBytesCount;
const std::unique_ptr<Block> allocatedBlocks;
void initialize() {
std::memset(allocatedBlocks.get(), 0, allocatedBytesCount);
// Place initial BlockHeader at the beginning of all blocks
}

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

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

Log("Coalescing BlockHeader at " << left << " & " << right )
//accumulate free blocks + now obsolete header data
left->data.managedBlocks += right->data.managedBlocks;
//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)
//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
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

//Now try to coalesce with the next and previous physical block
}
}

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

• Welcome to code review, if you have some unit tests for this class and posted them then we can give you a better review. At the moment we have to guess how it is used. Jul 12, 2020 at 12:56
• You should find a unique magic number 0xDEADBEEF is used in lots of situations. Especially common for debuggers. en.wikipedia.org/wiki/Hexspeak See the notable magic numbers and pick one NOT in the list. Jul 13, 2020 at 17:44
• That's some pretty dense code. You could make it easier to use by adding some vertical white space and logically grouping things together. Then replacing the bad comments with a "WHY" description comment. Self documenting code is your friend. Jul 13, 2020 at 17:52
• Your malloc constructs an instance of T. But your free accepts a void*. Who is responsible for calling the destructor of the object? The user or the library? Either accept a T* and call the destructor, or only return a void* from malloc and leave object construction to the caller.
– Rish
Jul 13, 2020 at 18:42

## 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!)


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

• Thanks for the anwer! Can you tell me why no destructor leaks memory? I am using a unique_ptr for the allocated memory. Shouldnt that make sure no leak occurs? Jul 18, 2020 at 4:15
• @Raildex Sorry missed that. No leak. Jul 18, 2020 at 14:46