#pragma once
#include "MemoryException.h"
#include "MemoryStructs.h"
namespace Combustion
{
struct Heap_Impl;
class Heap
{
public:
/* Creates a Heap that manages the provided memory
pMemory: pointer to the memory to manage
size: size of pMemory
Optional Params (used for more verbose debugging data):
line: line number of the call to create the heap
filename:filename of the line with the call to create the heap
tag: an integer representing a 4 character string to mark the memory
throws MemoryException for failures
*/
Heap(void* pMemory, size_t size, int line = 0, char* filename = 0, int tag = 0);
/* Destroys the Heap
Note: Does not call delete on the pMemory provided during the Heaps construction
*/
~Heap();
/* Allocates at least the amount of memory specified of the given type
and returns a typed pointer
size: Amount of memory requested
Optional Params (used for more verbose debugging data):
line: line number of the call to allocate memory
filename:filename of the line with the call to allocate memory
tag: an integer representing a 4 character string to allocate memory
throws MemoryException for failures
*/
template<typename T>
T* Alloc(size_t size, int line = 0, char* filename = 0, int tag = 0)
{ return reinterpret_cast<T*>( Alloc(size, line, filename, tag) ); }
/*
Frees the memory allocated at the specified pointer
pMemory: A pointer to the beginning of a block of memory allocated by the heap
Optional Params (used for more verbose debugging data):
line: line number of the call to free memory
filename:filename of the line with the call to free memory
throws MemoryException for failures
*/
void Free(void* pMemory, int line = 0, char* filename = 0);
/*
Creates a new Heap inside the memory allocated for the Heap
size: Minimum requested size of the new Heap
Optional Params (used for more verbose debugging data):
line: line number of the call to create the heap
filename:filename of the line with the call to create the heap
throws MemoryException for failures
*/
Heap* SubHeap(size_t size, int line = 0, char* filename = 0);
/*
Frees the SubHeap pointed to by the provided pointer
heap: Pointer to the Heap to free
Optional Params (used for more verbose debugging data):
line: line number of the call to free the heap
filename:filename of the line with the call to free the heap
throws MemoryException for failures
*/
void FreeSubHeap(Heap* heap, int line = 0, char* filename = 0);
/* Merges block with sourrounding free blocks of memory. If pMemory==0,
entire heap is coalesced */
void Coalesce(void *pMemory = 0);
/* Checks all guard blocks in heap for changes. Returns true if Heap is
valid, false otherwise */
bool Validate();
/* Returns size of all free memory if checkFree = true. Otherwise returns
size of allocated memory */
size_t TotalMemory(bool checkFree);
/* Returns size of largest free block in the Heap */
size_t LargestFreeBlock();
/* Checks if the block is allocated by the Heap and checks if the block is corrupted*/
bool IsInvalid(void *pMemory);
/* Returns 0-1 value for fragmentation ratio. 0=no fragmentation 1=max fragmentation */
float ExternalFragmentation();
/* Returns 0-1 value for fragmentation ratio. 0=no fragmentation 1=max fragmentation */
float InternalFragmentation();
/* Returns the largest amount of memory ever stored in allocated blocks at once */
int GetMaxMemoryUsage();
/* prints recorded statistics for the heap */
void PrintHeapStatistics();
//=====================================================================
// Helper Debug Functions
//=====================================================================
/* Returns the number of unfreed blocks */
int NumLeaks();
/* Prints the allocation number, file, line, and tag (if provided) of any
unallocated memory */
void PrintLeaks();
/* Returns oldest allocated block in debug. returns 0 in release */
void* OldestBlock();
/* Prints the number of bytes stored in blocks marked by the given tag */
size_t GetUsageFromTag(int tag);
private:
void* Alloc(size_t size, int line = 0, char* filename = 0, int tag = 0);
Heap_Impl* heap;
};
}
#include "Heap.h"
#include "Heap_Impl.cpp"
#include <cassert>
#include <memory>
#include <iostream>
using namespace std;
namespace Combustion
{
int g_NextAllocNum = 1;
int GetAllocationNumber() { return g_NextAllocNum++; }
Heap::Heap(void* pMemory, size_t size, int line /* = 0*/, char* filename /* = 0*/,
int tag /* = 0*/)
{
if(!pMemory) throw MemoryException("Heap Initialized With Null Data", line, filename);
if(size < sizeof(Heap)) throw MemoryException("Heap Size Too Small", line, filename);
heap = new(pMemory) Heap_Impl(size);
#ifdef _DEBUG
heap->allocNum = GetAllocationNumber();
#endif
}
Heap::~Heap()
{
heap->~Heap_Impl();
}
#define FIND_SUITABLE_FREE while(current != 0) { \
if(!current->isAllocated && current->size >= correctSize) break;\
current = current->nextBlock; }
void* Heap::Alloc(size_t size, int line /* = 0*/, char* filename /* = 0*/,
int tag /* = 0*/)
{
size_t correctSize = size + GUARD_SIZE;//BLOCK_HEADER_AND_GUARD;
//First-fit allocation (for speed)
MemoryHeader* current = (MemoryHeader*) (reinterpret_cast<char*>(heap) +
sizeof(Heap_Impl));
FIND_SUITABLE_FREE
if(!current)
{
Coalesce(); //if no suitable block found, coalesce to try to find one
FIND_SUITABLE_FREE //try again
if(!current) throw MemoryException("Out of Memory", line, filename);
}
heap->Split(current, size); //if no split is needed, none is made
#ifdef _DEBUG
heap->stats.numAllocs++;
current->allocNum = GetAllocationNumber();
current->lineNum = line;
current->file = filename;
current->tag = tag;
#endif
return reinterpret_cast<void*>( (reinterpret_cast<char*>(current) +
sizeof(MemoryHeader)) );
}
Heap* Heap::SubHeap(size_t size, int line /* = 0*/, char* filename /* = 0*/)
{
//allocate enough room for everything HeapObj Heap_Impl MemoryHeader size
size_t correctSize = sizeof(Heap) + sizeof(Heap_Impl) + sizeof(MemoryHeader) + size;
Heap* subheap = reinterpret_cast<Heap*>( Alloc(correctSize, line, filename) );
void* subheapData = reinterpret_cast<void*>( reinterpret_cast<char*>(subheap) +
sizeof(Heap) );
subheap = new(subheap) Heap(subheapData, size, line, filename);
return subheap;
}
void Heap::FreeSubHeap(Heap* subheap, int line /*= 0*/, char* filename /*= 0*/)
{
subheap->~Heap(); //delete subeap
Free(subheap, line, filename); //free data in outer heap
}
void Heap::Free(void* pMemory, int line /*= 0*/, char* filename /*= 0*/)
{
if(!pMemory) throw MemoryException("Null Pointer", line, filename);
if(IsInvalid(pMemory)) throw MemoryException("Invalid Pointer in Free",
line, filename);
MemoryHeader* memHeader = (MemoryHeader*) (reinterpret_cast<char*>(pMemory) -
sizeof(MemoryHeader));
if(!memHeader->isAllocated) throw MemoryException("Double Free", line, filename);
memHeader->isAllocated = false;
memHeader->guardData = _MAGIC;
int* endGuard = (int*) (reinterpret_cast<char*>(pMemory) + memHeader->size);
*endGuard = _MAGIC;
//the guard block now counts towards the block size
memHeader->size += GUARD_SIZE;
#ifdef _DEBUG
heap->stats.numDeallocs++;
#endif
heap->numAllocatedBlocks--;
heap->currUsage -= memHeader->size;
}
void Heap::Coalesce(void *pMemory)
{
if(pMemory)
{//only coalesce immediately surrounding blocks
MemoryHeader* memHeader = (MemoryHeader*) (reinterpret_cast<char*>(pMemory) -
sizeof(MemoryHeader));
//walk left until a non-free block is hit
MemoryHeader* start = memHeader;
while(start->prevBlock != 0 && !start->prevBlock->isAllocated)
start = start->prevBlock;
//march right, coalescing until a non-free block is hit
while(start->nextBlock != 0 && !start->nextBlock->isAllocated)
heap->MergeWithNextBlock(start);
}
else
{//coalesce all free blocks in the heap...
MemoryHeader* memHeader = (MemoryHeader*) (reinterpret_cast<char*>(heap) +
sizeof(Heap_Impl));
while(memHeader != 0)
{
if(!memHeader->isAllocated && memHeader->nextBlock != 0 &&
!memHeader->nextBlock->isAllocated)
heap->MergeWithNextBlock(memHeader); //merge, but don't move memHeader
else
memHeader = memHeader->nextBlock; //don't merge, but move memHeader
}
}
}
size_t Heap::TotalMemory(bool checkFree)
{
//Walk through the memory and count the size of the free blocks
MemoryHeader* current = (MemoryHeader*)(reinterpret_cast<char*>(heap) +
sizeof(Heap_Impl));
size_t totalFreeMem = 0;
while(current != 0)
{
if( (checkFree && !current->isAllocated) ||
(!checkFree && current->isAllocated) )
totalFreeMem += current->size;
current = current->nextBlock;
}
return totalFreeMem;
}
size_t Heap::LargestFreeBlock()
{
//Walk through the memory and find the biggest free
MemoryHeader* current = (MemoryHeader*)(reinterpret_cast<char*>(heap) +
sizeof(Heap_Impl));
size_t largestFree = 0;
while(current != 0)
{
if(!current->isAllocated && current->size > largestFree)
largestFree = current->size;
current = current->nextBlock;
}
return largestFree;
}
void* Heap::OldestBlock()
{
#ifndef _DEBUG
return 0;
#else
//Walk through the memory and find the earliest allocation
MemoryHeader* current = (MemoryHeader*)(reinterpret_cast<char*>(heap) +
sizeof(Heap_Impl));
size_t oldest = INT_MAX;
void* pOldest = 0;
while(current != 0)
{
if(current->isAllocated && current->allocNum < oldest)
{
oldest = current->allocNum;
pOldest = reinterpret_cast<void*>( reinterpret_cast<char*>(current) +
sizeof(MemoryHeader));
}
current = current->nextBlock;
}
return pOldest;
#endif
}
bool Heap::Validate()
{
//walk entire heap, checking each block
MemoryHeader* memHeader = reinterpret_cast<MemoryHeader*>(
(reinterpret_cast<char*>(heap) + sizeof(Heap_Impl)) );
while(memHeader != 0)
{
if(memHeader->guardData != _MAGIC)
return false;
if(memHeader->isAllocated)
{
int* endGuard = (int*)(reinterpret_cast<char*>(memHeader) +
sizeof(MemoryHeader) + memHeader->size);
if(*endGuard != memHeader->guardData)
return false;
}
memHeader = memHeader->nextBlock;
}
return true;
}
bool Heap::IsInvalid(void* pMemory)
{
if(pMemory == 0) return true;
//check if the address is in the range of the heap
void* start = reinterpret_cast<void*>(heap);
void* end = (void*) (reinterpret_cast<char*>(heap) +
sizeof(Heap_Impl) + heap->size);
if(pMemory <= start || pMemory >= end)
return true;
MemoryHeader* memHeader = (MemoryHeader*) (reinterpret_cast<char*>(pMemory) -
sizeof(MemoryHeader));
//check to make sure the pointer was allocated
if(!memHeader->isAllocated)
return true;
//check the guard blocks
if(memHeader->guardData != _MAGIC)
return true;
if(memHeader->isAllocated)
{
int* endGuard = (int*)(reinterpret_cast<char*>(pMemory) +
memHeader->size);
if(*endGuard != memHeader->guardData)
return true;
}
return false;
}
void Heap::PrintHeapStatistics()
{
cout << "===================================\n";
#ifdef _DEBUG
cout << "Number of Allocations: " << heap->stats.numAllocs << endl;
cout << "Number of Deallocations: " << heap->stats.numDeallocs << endl;
#endif
cout << "Number of Blocks: " << heap->numTotalBlocks << endl;
cout << "Number of Alloced: " << heap->numAllocatedBlocks << endl;
cout << "Number of Free: " << heap->numTotalBlocks - heap->numAllocatedBlocks << endl;
cout << "===================================\n" << endl;
}
float Heap::ExternalFragmentation()
{
int totalFreeBlocks = heap->numTotalBlocks - heap->numAllocatedBlocks;
return 1.0f - (LargestFreeBlock() / totalFreeBlocks);
}
float Heap::InternalFragmentation()
{
return float(heap->numTotalBlocks * sizeof(MemoryHeader)) /
float(heap->size);
}
size_t Heap::GetUsageFromTag(int tag)
{
#ifdef _DEBUG
//Walk through the memory and count the size of the free blocks
MemoryHeader* current = (MemoryHeader*)(reinterpret_cast<char*>(heap) +
sizeof(Heap_Impl));
size_t totalUsed = 0;
while(current != 0)
{
if(current->isAllocated && current->tag == tag)
totalUsed += current->size;
current = current->nextBlock;
}
return totalUsed;
#else
return 0;
#endif
}
int Heap::NumLeaks()
{
#ifdef _DEBUG
return heap->stats.numAllocs - heap->stats.numDeallocs;
#else
return false;
#endif
}
void Heap::PrintLeaks()
{
#ifdef _DEBUG
//walk entire heap, checking each block
MemoryHeader* memHeader = reinterpret_cast<MemoryHeader*>(
(reinterpret_cast<char*>(heap) + sizeof(Heap_Impl)) );
while(memHeader != 0)
{
if(memHeader->isAllocated)
{
cout << "Leak in file " << memHeader->file << " on line " <<
memHeader->lineNum << ".\n";
cout << "Allocation number: " << memHeader->allocNum << ".\n";
if(memHeader->tag != 0)
{
char tag[4];
memcpy(tag, &(memHeader->tag), 4);
cout << "Tagged As: ";
for(int i = 3; i >= 0; --i) //tag is backwards, so print in reverse
cout << tag[i];
cout <<"\n\n";
}
}
memHeader = memHeader->nextBlock;
}
#endif
}
int Heap::GetMaxMemoryUsage()
{
return heap->maxUsage;
}
}
#include "MemoryException.h"
#include "MemoryStructs.h"
#include <cassert>
namespace Combustion
{
const int _MAGIC = 0xBAADF00D;
#define GUARD_SIZE 4
#define TRUE_MIN_BLOCK_SIZE sizeof(MemoryHeader) + GUARD_SIZE + 4
#define BLOCK_HEADER_AND_GUARD sizeof(MemoryHeader) + GUARD_SIZE
struct MemoryHeader
{
#ifdef _DEBUG
unsigned int allocNum; //number of alloc (used to report unfreed memory)
int lineNum; //line that called Alloc
int tag; //block tag information
char* file; //file of line that called Alloc
#endif
size_t size; //size of data in the block (not incl. guard block/header size)
bool isAllocated; //marks whether block is free or allocated
MemoryHeader* prevBlock;//pointer to prev block in heap
MemoryHeader* nextBlock;//pointer to next block in heap
int guardData; //contains begining guard block data
MemoryHeader(size_t memsize, int guard, bool isalloced, int memoryTag = 0)
: size(memsize), isAllocated(isalloced), prevBlock(0), nextBlock(0),
guardData(guard)
{
#ifdef _DEBUG
tag = memoryTag;
#endif
}
};
struct Heap_Impl
{
size_t size; //size of the entire heap
int currUsage; //current amount allocated
int maxUsage; //largest amount allocated
int numAllocatedBlocks; //number of currently allocated blocks
int numTotalBlocks; //number of all blocks (free and allocated)
#ifdef _DEBUG
unsigned int allocNum;//allocation number
HeapStats stats; //struct that holds debugging stats about heap usage
#endif
/*
Constructs the Heap Header and creates a free block spanning all memory
not taken up by the Heap Header
*/
Heap_Impl(size_t heapSize, int line = 0, char* filename = 0)
: size(heapSize - sizeof(Heap_Impl)), numAllocatedBlocks(0),
numTotalBlocks(1), currUsage(0), maxUsage(0)
{
size_t minSize = sizeof(Heap_Impl) + sizeof(MemoryHeader);
if(heapSize < minSize) throw MemoryException("Out of Memory", line, filename);
//Create Header for a free block
MemoryHeader* pFirstFree = (MemoryHeader*) (reinterpret_cast<char*>(this) +
sizeof(Heap_Impl));
pFirstFree = new(pFirstFree) MemoryHeader( heapSize - minSize, 0xBAADF00D, false );
#ifdef _DEBUG
pFirstFree->lineNum = line;
pFirstFree->file = filename;
stats = HeapStats();
#endif
}
/* Attempts to split a free block to make an allocated block of minSize and a free
block for the remaining data.
In the case where the resulting free block is too small to hold a header, the block
is not split, and the allocated block is given the remainder.
Allocated blocks are marked at the end with a guard block marker
*/
void Split(void* pHeader, size_t minSize)
{
MemoryHeader* memHeader = reinterpret_cast<MemoryHeader*>(pHeader);
assert(memHeader->size >= minSize);
assert(memHeader->isAllocated == false);
//Check if there is enough leftover to justify split
if(memHeader->size > TRUE_MIN_BLOCK_SIZE)
{ //can split
size_t originalSize = sizeof(MemoryHeader) + memHeader->size;
//create first header
memHeader->isAllocated = true;
memHeader->size = minSize;
//write magic marker at end
int* ptr = reinterpret_cast<int*>( (reinterpret_cast<char*>(memHeader) +
sizeof(MemoryHeader) + memHeader->size) );
*ptr = _MAGIC;
numAllocatedBlocks++;
numTotalBlocks++;
//create second header
MemoryHeader* freeHeader = reinterpret_cast<MemoryHeader*>(
(reinterpret_cast<char*>(memHeader) + sizeof(MemoryHeader) +
memHeader->size + GUARD_SIZE) );
int freeBlockSize = originalSize - (sizeof(MemoryHeader) * 2 + GUARD_SIZE +
memHeader->size);
freeHeader = new(freeHeader) MemoryHeader(freeBlockSize, _MAGIC, false);
//repair pointers
freeHeader->prevBlock = memHeader;
freeHeader->nextBlock = memHeader->nextBlock;
memHeader->nextBlock = freeHeader;
}
else
{ //can't split, return entire block
memHeader->isAllocated = true;
int* ptr = (int*) (reinterpret_cast<char*>(memHeader) + sizeof(MemoryHeader) +
memHeader->size);
*ptr = _MAGIC;
numAllocatedBlocks++;
}
currUsage += memHeader->size;
if(currUsage > maxUsage)
maxUsage = currUsage;
}
/*
Coalesces the block pointed to by pHeader with the block on its right
*/
void MergeWithNextBlock(void* pHeader)
{
MemoryHeader* currHeader = reinterpret_cast<MemoryHeader*>(pHeader);
MemoryHeader* nextHeader = currHeader->nextBlock;
size_t newSize = currHeader->size + sizeof(MemoryHeader) + nextHeader->size;
nextHeader->guardData = _MAGIC;
//clear the endGuard
if(nextHeader->isAllocated)
{
int* endGuard = (int*) (reinterpret_cast<char*>(nextHeader) +
sizeof(MemoryHeader) + nextHeader->size);
*endGuard = _MAGIC;
newSize += GUARD_SIZE;
}
currHeader->isAllocated = false;
currHeader->size = newSize;
currHeader->nextBlock = nextHeader->nextBlock;
//fix the pointer of the next block
if(nextHeader->nextBlock != 0)
nextHeader->nextBlock->prevBlock = currHeader;
//clear nextHeader's pointers for better debugging
nextHeader->nextBlock = 0;
nextHeader->prevBlock = 0;
numTotalBlocks--;
}
};
}
#pragma once
#include <exception>
#include <string>
namespace Combustion
{
/*
Thrown by MemoryManager when a problem is encountered
Functions allow the user to request the amount of information
they would like to display
errorMessage: details the exact problem encountered
linenumber: the line of the instruction which triggered the exception
filename: the filename of the line which triggered the exception
*/
class MemoryException : public std::exception
{
public:
MemoryException(const char* msg, int linenumber, char* filename)
: errorMessage(msg), line(linenumber), file(filename)
{}
/* Returns the message describing the exception */
virtual const char* what() { return errorMessage; }
/* Returns the line number that triggered the exception */
virtual int GetLine() { return line; }
/* Returns the file of the line number that triggered the exception */
virtual char* GetFile() { return file; }
private:
const char* errorMessage;
int line;
char* file;
};
}