Heap Memory Manager: Custom malloc/free and new/delete in C++

This project implements my own “malloc()/free()” and “new/delete” on top of a block of heap memory. It includes two kinds of memory allocators.

Code: HeapMemoryManager on GitHub (C++, Visual Studio project, Windows only). main.cpp contains a unit test that exercises the whole memory system. The project was the final exam of a game engine course; the test in main.cpp came with the assignment, the allocators are mine.

General memory allocator

It allocates memory of any size for the caller (HeapManager.h / HeapManager.cpp):

• Use two singly linked lists to manage allocated and unallocated memory blocks.
• Suballocate from the end of the heap memory.
• Subtract needed size (i_size) from the end of the heap memory to get enough memory for the caller.
• Round the address down to the requested alignment.
• The memory from the aligned address to the end of the block is handed to the caller.
• Create a new MemoryBlock for the caller’s memory.
• A collection function walks the free list and merges adjacent free blocks into one larger block.

Fixed size memory allocator

It allocates small blocks of a fixed size for the caller (FixedSizeAllocator.h / FixedSizeAllocator.cpp, BitArray.h / BitArray.cpp):

• Benefits:
  • Doesn’t require a fit search when making an allocation of that size.
  • No internal fragmentation.
  • Reduces per-allocation overhead.
  • In real game development, most memory allocations have a small fixed size.
• Use BitArray (with bitwise operator) to manage allocated and unallocated memory blocks (one bit per block: 1 = in use, 0 = free).
• Use the compiler intrinsics _BitScanForward() and _BitScanForward64() to find the first set or clear bit, which locates the block to hand out or to check.

Putting the two together

MemorySystem.h / MemorySystem.cpp sets everything up on one block of heap memory: three fixed-size allocators (16-byte, 32-byte and 96-byte blocks, 100 / 200 / 400 of them) sit at the front, and the heap manager takes everything behind them. The replaced malloc() and operator new route each request by size: up to 16, 32 or 96 bytes goes to the matching fixed-size allocator, anything larger to the heap manager with 4-byte alignment. free() and operator delete try the fixed-size allocators first (each one can tell whether an address is one of its blocks and whether that block is in use) and fall back to the heap manager. On shutdown every allocator checks that nothing is still outstanding.