I'm learning memory management for about 2 days now and I'm trying to create my own memory management for my game engine.
First I start with heap allocation.
If someone has some time to check if I'm doing OK please have a look at the code below.
But now that I have a Heap Allocator. How should I continue?
I heard something about pools and I've read a little bit about them but still don't have a clue what they should do.
Also, how can I make my HeapAllocator multi-thread safe?
I assume some of my heaps will give errors when I use multithreads?
Thanks in advance!
Kind regards,
Jonathan
This is the code I have at the moment:
///////////////////////////////////////////////////////////////////////////
// HeapAllocator.h
// Date: 21/09/2012
// Copyrights Bollaert Jonathan
///////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////
#ifndef HEAP_ALLOCATOR_H
#define HEAP_ALLOCATOR_H
#pragma once
#include "Types.h"
#include "Assert.h"
#include <iostream>
using namespace std;
template<typename T> CINLINE
T Align(T nData, size_t nAlign)
{
// More information: http://en.wikipedia.org/wiki/Data_structure_alignment
ASSERT((nAlign & (nAlign - 1)) == 0);
size_t size = ((size_t)nData + (nAlign - 1)) & ~(nAlign - 1);
return T(size);
}
namespace C2D1HeapAlloc
{
///////////////////////////////////////////////
// Heap System Allocator
///////////////////////////////////////////////
class HeapSysAllocator
{
public:
static CVOID* SysAlloc(size_t size) {
cout << "HeapSysAllocator has allocated a heap with size: " << size << " bytes." << endl;
return malloc(size);
}
static CVOID SysDealloc(void* ptr) {
cout << "HeapSysAllocator has deallocated a heap." << endl;
free(ptr);
}
};
///////////////////////////////////////////////
// Memory Usage
///////////////////////////////////////////////
struct MemoryUsage
{
size_t m_MemAllocated, m_MemUsed;
MemoryUsage(size_t nAlloc = 0, size_t nUsed = 0)
:m_MemAllocated(nAlloc), m_MemUsed(nUsed)
{
Validate();
}
CINLINE CVOID Validate() {
ASSERT(m_MemUsed <= m_MemAllocated);
}
CINLINE CVOID ClearMemory(){
m_MemAllocated = m_MemUsed = 0;
}
CINLINE const size_t GetMemoryFree() const {
return m_MemAllocated - m_MemUsed;
}
CINLINE const size_t GetMemoryAllocated() const {
return m_MemAllocated;
}
CINLINE const size_t GetMemoryUsed() const {
return m_MemUsed;
}
};
///////////////////////////////////////////////
// Round up to next multiple of nAlign.
///////////////////////////////////////////////
CINLINE const size_t RoundUpTo(size_t nSize, size_t nAlign)
{
ASSERT(nAlign > 0);
nSize += nAlign - 1;
return nSize - nSize % nAlign;
}
///////////////////////////////////////////////
// Heap Allocator
///////////////////////////////////////////////
template<CBOOL bMultiPage = true, typename SysAl = HeapSysAllocator>
class HeapAllocator: private SysAl
{
public:
enum {DefaultAlignment = sizeof(void*)}; // 4 bytes
enum {DefaultPageSize = 0x1000}; // 4 Kb
HeapAllocator(size_t nPageSize = DefaultPageSize)
:m_PageSize(nPageSize ? nPageSize : DefaultPageSize)
,m_PageList(nullptr)
{
cout << "HeapAllocator is being constructed on the stack with size: " << sizeof(*this) << " bytes." << endl;
}
~HeapAllocator()
{
cout << "HeapAllocator is being deallocated." << endl;
Clear();
}
////////////////////////////
// Raw memory allocation
////////////////////////////
void* Allocate(size_t nSize, size_t nAlign = DefaultAlignment)
{
for(;;)
{
cout << "Attempting to find a heap..." << endl;
// Try allocating from head page first
if(m_PageList)
{
cout << "Heap has been found." << endl;
cout << "Attempting to allocate: " << nSize << " bytes." << endl;
if(void* ptr = m_PageList->Allocate(nSize, nAlign)) {
m_Memory.m_MemUsed += nSize;
return ptr;
}
if(m_PageList->m_pNext && m_PageList->m_pNext->GetMemoryFree() > m_PageList->GetMemoryFree())
{
SortPage(m_PageList);
Validate();
if(void* ptr = m_PageList->Allocate(nSize, nAlign)) {
m_Memory.m_MemUsed += nSize;
return ptr;
}
}
cout << "Allocating requested memory FAILED." << endl;
if(!bMultiPage)
return 0;
cout << "Heap can not store the required size." << endl;
}
else
{
cout << "No heap has been found!" << endl;
}
// Allocate the new page of the required size.
int nAllocSize = sizeof(PageNode) + nAlign - 1 + RoundUpTo(nSize, m_PageSize);
cout << "Attempting to allocate a heap..." << endl;
void* pAlloc = this->SysAlloc(nAllocSize);
PageNode* pPageNode = new(pAlloc) PageNode(nAllocSize);
// Insert at head of list
pPageNode->m_pNext = m_PageList;
m_PageList = pPageNode;
m_Memory.m_MemAllocated += nAllocSize;
Validate();
}
}
CVOID Deallocate(void* ptr, size_t nSize)
{
cout << "Attempting to deallocate memory..." << endl;
ASSERT(CheckPtr(ptr));
ASSERT(m_Memory.m_MemUsed >= nSize);
m_Memory.m_MemUsed -= nSize;
cout << "A memory with size: " << nSize << " bytes has been deallocated." << endl;
}
////////////////////////////
// Maintenance
////////////////////////////
CINLINE const MemoryUsage GetTotalMemory() const {
m_Memory;
}
struct PageNodeHandle {};
PageNodeHandle* RemovePages() {
// Remove the pages from the object.
PageNodeHandle* pPageNode;
Validate();
pPageNode = m_PageList;
m_PageList = 0;
m_Memory.ClearMemory();
return pPageNode;
}
CVOID FreeMemory(PageNodeHandle* handle)
{
PageNode* pPageNode = static_cast<PageNode*>(handle);
// Loop through all the pages, freeing the memory.
while(pPageNode != nullptr)
{
// Read the "next" pointer before deleting.
PageNode* pNext = pPageNode->m_pNext;
// Delete the current page
this->SysDealloc(pPageNode);
// Mode to the next page in the list
pPageNode = pNext;
}
}
CVOID Clear()
{
PageNodeHandle* pPageNode;
Validate();
// Remove the pages from the object.
pPageNode = RemovePages();
// Loop through all the pages, freeing the memory.
FreeMemory(pPageNode);
}
CVOID Reset()
{
Validate();
size_t nPrevSize = ~0;
for(PageNode** ppPage = &m_PageList; *ppPage; )
{
(*ppPage)->Reset();
if((*ppPage)->GetMemoryAlloc() > nPrevSize) {
// Move page to sorted location near beginning.
SortPage(*ppPage);
// ppPage is now next page, so continue loop.
continue;
}
nPrevSize = (*ppPage)->GetMemoryAlloc();
ppPage = &(*ppPage)->pNext;
}
m_Memory.m_MemUsed = 0;
Validate();
}
CBOOL CheckPtr(void* ptr) const
{
if(!ptr)
return true;
for(PageNode* pNode = m_PageList; pNode; pNode = pNode->m_pNext) {
if(pNode->CheckPtr(ptr))
return true;
}
return false;
}
CVOID Validate()
{
MemoryUsage MemCheck;
for(PageNode* pPage = m_PageList; pPage; pPage = pPage->m_pNext) {
pPage->Validate();
if(pPage != m_PageList && pPage->m_pNext)
ASSERT(pPage->GetMemoryFree() >= pPage->m_pNext->GetMemoryFree());
MemCheck.m_MemAllocated += pPage->GetMemoryAllocated();
MemCheck.m_MemUsed += pPage->GetMemoryUsed();
}
ASSERT(MemCheck.m_MemAllocated == m_Memory.m_MemAllocated);
ASSERT(MemCheck.m_MemUsed >= m_Memory.m_MemUsed);
}
protected:
struct PageNode : PageNodeHandle
{
PageNode* m_pNext;
char* m_pEndAlloc;
char* m_pEndUsed;
CINLINE char* StartUsed() const {
return (char*)(this+1);
}
PageNode(size_t nAlloc) {
m_pNext = nullptr;
m_pEndAlloc = (char*)this + nAlloc;
m_pEndUsed = StartUsed();
}
void* Allocate(size_t nSize, size_t nAlign) {
// Align current mem
char* pNew = Align(m_pEndUsed, nAlign);
if(pNew + nSize > m_pEndAlloc)
return 0;
m_pEndUsed = pNew + nSize;
cout << "Memory has been allocated with size: " << nSize << " bytes." << endl;
return pNew;
}
CINLINE CVOID Reset() {
m_pEndUsed = StartUsed();
}
CINLINE const size_t GetMemoryAllocated() const {
return m_pEndAlloc - (char*)this;
}
CINLINE const size_t GetMemoryUsed() const {
return m_pEndUsed - StartUsed();
}
CINLINE const size_t GetMemoryFree() const {
return m_pEndAlloc - m_pEndUsed;
}
CINLINE CVOID Validate() const {
ASSERT(m_pEndAlloc >= (char*)this);
ASSERT(m_pEndUsed >= StartUsed() && m_pEndUsed <= m_pEndAlloc);
}
CINLINE CBOOL CheckPtr(void* ptr) const {
return (char*)ptr >= StartUsed() && (char*)ptr < m_pEndUsed;
}
};
CVOID SortPage(PageNode* rpPage) {
// Unlink rpPage.
PageNode* pPage = rpPage;
rpPage = pPage->m_pNext;
// Insert into list based on free memory.
PageNode** ppBefore = &m_PageList;
while (*ppBefore && (*ppBefore)->GetMemoryFree() > pPage->GetMemoryFree())
ppBefore = &(*ppBefore)->m_pNext;
// Link before rpList.
pPage->m_pNext = *ppBefore;
*ppBefore = pPage;
}
private:
MemoryUsage m_Memory; // Track memory allocated and used
const size_t m_PageSize; // Pages allocated at this size
PageNode* m_PageList; // All allocated pages
};
}
#endif // HEAP_ALLOCATOR_H
Some of you may think "I have seen this kind of code before...."
Well got all the code from all of these:
- CryEngine open source SDK
- Standard Library C++ ~by Sutter
- Internet: http://www.cantrip.org/wave12.html
http://www.bogotobogo.com/cplusplus/memoryallocation.php
http://www.codeguru.com/cpp/cpp/cpp_mfc/stl/article.php/c4079/Allocators-STL.htm