This is the top
[bottom]
- Yada Yada Yada
/******************************************************************************/
/*!
\file ObjectAllocator.cpp
\author Alejandro Hitti
\par email: alejandro.hitti\@digipen.edu
\par DigiPen login: alejandro.hitti
\par Course: CS280
\par Assignment #1
\date 01/23/2014
\brief
This is the implementation file of a simple memory manager, which includes
three types of header blocks, padding and debug checks. It also contains
the OAException class and 4 structs: OAStats, OAConfig, GenericObject and
MemBlockInfo. http://alejandrohitti.com
Functions include:
- Constructor
- Destructor
- Allocate
- Free
- DumpMemoryInUse
- ValidatePages
- FreeEmptyPages
- SetDebugState
- GetFreeList
- GetPageList
- GetConfig
- GetStats
*/
/******************************************************************************/
#include "ObjectAllocator.h"
#include <cstring> // memset
/******************************************************************************/
/*!
\brief
Creates the ObjectManager per the specified values
Throws an exception if the construction fails. (Memory allocation problem)
\param ObjectSize
Size of the actual data for each block
\param config
Config struct specifying all the characteristics of the Object Allocator
*/
/******************************************************************************/
ObjectAllocator::ObjectAllocator(size_t ObjectSize, const OAConfig& config) throw(OAException)
: mFreeList(NULL), mPageList(NULL), mConfig(config)
{
// Initializes all variables for stats and config
initialize(ObjectSize);
// Allocates the first page
MakePage();
}
/******************************************************************************/
/*!
\brief
Destroys the ObjectManager (never throws)
*/
/******************************************************************************/
ObjectAllocator::~ObjectAllocator() throw()
{
GenericObject* temp;
// While there are pages allocated
while (mPageList)
{
// Pop Front of PageList
temp = mPageList->Next;
delete [] reinterpret_cast<char*>(mPageList);
mPageList = temp;
}
}
/******************************************************************************/
/*!
\brief
Take an object from the free list and give it to the client (simulates new)
Throws an exception if the object can't be allocated. (Memory allocation problem)
\param label
Character pointer to the user defined data for External HB
\return
Pointer to the allocated memory block
*/
/******************************************************************************/
void *ObjectAllocator::Allocate(const char *label) throw(OAException)
{
// Wrapper around new
if (mConfig.UseCPPMemManager_)
{
char* newObject;
try
{
newObject = new char[mStats.ObjectSize_];
}
catch (std::bad_alloc)
{
throw OAException(OAException::E_NO_MEMORY, "System out of memory.");
}
// Update stats
++mStats.Allocations_;
++mStats.ObjectsInUse_;
--mStats.FreeObjects_;
// Check for most number of objects
if (mStats.ObjectsInUse_ > mStats.MostObjects_)
mStats.MostObjects_ = mStats.ObjectsInUse_;
return reinterpret_cast<void*>(newObject);
}
// If all pages are full
if (mFreeList == NULL && mStats.PagesInUse_ < mConfig.MaxPages_)
MakePage();
// Reached max number of pages
else if (mFreeList == NULL && mStats.PagesInUse_ >= mConfig.MaxPages_)
throw OAException(OAException::E_NO_PAGES, "No more pages can be allocated. Max number of pages reached.");
// Give the first element of the FreeList to the user
GenericObject* newObject = mFreeList;
mFreeList = mFreeList->Next; // Move ahead on the list
std::memset(newObject, ALLOCATED_PATTERN, mStats.ObjectSize_);
// Update stats
++mStats.Allocations_;
++mStats.ObjectsInUse_;
--mStats.FreeObjects_;
// Check for most number of objects
if (mStats.ObjectsInUse_ > mStats.MostObjects_)
mStats.MostObjects_ = mStats.ObjectsInUse_;
// Update Header Blocks
char *header = reinterpret_cast<char*>(newObject) -
(mConfig.PadBytes_ + mConfig.HBlockInfo_.size_);
// Every time you see pointer arithmetic from here on, it's jumping over
// the previously updated variable
switch (mConfig.HBlockInfo_.type_)
{
case OAConfig::hbNone :
break;
case OAConfig::hbBasic :
(*reinterpret_cast<int*>(header)) = mStats.Allocations_; // Set number of allocs
header += sizeof(int);
*header |= 1; // Turn last bit to 1
break;
case OAConfig::hbExtended :
header += mConfig.HBlockInfo_.additional_;
++(*reinterpret_cast<short*>(header)); // Increase number of uses
header += sizeof(short);
(*reinterpret_cast<int*>(header)) = mStats.Allocations_; // Set number of allocs
header += sizeof(int);
*header |= 1; // Turn last bit to 1
break;
case OAConfig::hbExternal :
MemBlockInfo** mem = reinterpret_cast<MemBlockInfo**>(header);
*mem = new MemBlockInfo();
(*mem)->alloc_num = mStats.Allocations_; // Set number of allocs
(*mem)->in_use = true; // Set in use flag
if (label) // If user provided a label
{
(*mem)->label = new char[strlen(label) + 1]; // Dynamically allocate it
strcpy((*mem)->label, label);
}
else
(*mem)->label = NULL;
break;
}
return newObject;
}
/******************************************************************************/
/*!
\brief
Returns an object to the free list for the client (simulates delete)
Throws an exception if the the object can't be freed. (Invalid object)
\param Object
Pointer to the object to free
*/
/******************************************************************************/
void ObjectAllocator::Free(void *Object) throw(OAException)
{
// Wrapper around delete
if (mConfig.UseCPPMemManager_)
{
// Update stats
++mStats.FreeObjects_;
++mStats.Deallocations_;
--mStats.ObjectsInUse_;
delete [] reinterpret_cast<char*>(Object);
return;
}
// Checks for OutOfBounds and DoubleFree
if (mConfig.DebugOn_)
DebugExceptions(Object);
// Check for corruption
if (CheckCorruption(Object))
throw OAException(OAException::E_CORRUPTED_BLOCK, "Memory block is corrupted.");
// Put the new block in the front of the FreeList
GenericObject *temp = reinterpret_cast<GenericObject*>(Object);
// Set the free pattern
if (mConfig.DebugOn_)
std::memset(temp, FREED_PATTERN, mStats.ObjectSize_);
temp->Next = mFreeList;
mFreeList = temp;
// Update stats
++mStats.FreeObjects_;
++mStats.Deallocations_;
--mStats.ObjectsInUse_;
// Update Header Blocks
char *header = reinterpret_cast<char*>(Object) -
(mConfig.PadBytes_ + mConfig.HBlockInfo_.size_);
// Every time you see pointer arithmetic from here on, it's jumping over
// the previously updated variable
switch (mConfig.HBlockInfo_.type_)
{
case OAConfig::hbNone :
break;
case OAConfig::hbBasic :
(*reinterpret_cast<int*>(header)) = 0; // Number of allocations
header += sizeof(unsigned);
*header &= 0; // In use flag to false
break;
case OAConfig::hbExtended :
header += mConfig.HBlockInfo_.additional_; // User defined memory
header += sizeof(short);
(*reinterpret_cast<int*>(header)) = 0; // Number of allocations
header += sizeof(int);
*header &= 0; // In use flag to false
break;
case OAConfig::hbExternal :
MemBlockInfo** mem = reinterpret_cast<MemBlockInfo**>(header);
(*mem)->alloc_num = 0; // Number of allocations
(*mem)->in_use = false; // In use flag to false
if ((*mem)->label) // Check if label was dynamically allocated
delete [] (*mem)->label; // Delete it
delete (*mem); // Delete the external header block
*mem = NULL;
break;
}
}
/******************************************************************************/
/*!
\brief
Calls the callback fn for each block still in use
\param fn
Function pointer to the function that will be called if there is a memory
block that is still in use
\return
Number of blocks still in use when freeing the OA
*/
/******************************************************************************/
unsigned ObjectAllocator::DumpMemoryInUse(DUMPCALLBACK fn) const
{
GenericObject *pagePointer = mPageList;
unsigned inUse = 0;
// Checks every page
while(pagePointer)
{
// Checks every object in a page
for (unsigned i = 0; i < mConfig.ObjectsPerPage_; ++i)
{
char *pos = reinterpret_cast<char*>(pagePointer) + mOffset + i * mSkipSize; // Position
if (CheckInUse(pos)) // If the mem block is in use
{
fn(pos, mStats.ObjectSize_); // Callback function
++inUse;
}
}
pagePointer = pagePointer->Next;
}
return inUse;
}
/******************************************************************************/
/*!
\brief
Calls the callback fn for each block that is potentially corrupted
\param fn
Function pointer to the function that will be called if there is memory
corruption in a memory block
\return
Number of corruptions found. Returns 0 if debug is off or if padding is 0
*/
/******************************************************************************/
unsigned ObjectAllocator::ValidatePages(VALIDATECALLBACK fn) const
{
// Return if debug is off or if the padding size is zero
if (!mConfig.DebugOn_ || (mConfig.PadBytes_ == 0))
return 0;
GenericObject *pagePointer = mPageList;
unsigned corruptions = 0;
// Checks every page
while(pagePointer)
{
// Checks every object in a page
for (unsigned i = 0; i < mConfig.ObjectsPerPage_; ++i)
{
char *pos = reinterpret_cast<char*>(pagePointer) + mOffset + i * mSkipSize; // Position
if (CheckCorruption(reinterpret_cast<void*>(pos))) // If the mem block is corrupted
{
fn(pos, mStats.ObjectSize_); // Callback function
++corruptions;
}
}
pagePointer = pagePointer->Next;
}
return corruptions;
}
/******************************************************************************/
/*!
\brief
Frees all empty pages (extra credit)
\return
Number of pages freed.
*/
/******************************************************************************/
unsigned ObjectAllocator::FreeEmptyPages(void)
{
// Pointers to walk the pagelist and freelist
GenericObject *pagePointer = mPageList;
GenericObject *prevPage = NULL;
GenericObject *listPointer;
GenericObject *nextNode;
GenericObject *prevList = mFreeList;
GenericObject *head = pagePointer;
// Counter of pages freed
unsigned pagesFreed = 0;
// Walks pages
while(pagePointer)
{
bool isEmpty = true; // Initial value
char *pos = (reinterpret_cast<char*>(pagePointer) + mOffset); // Position/object
// Walks each object in a page
for (unsigned i = 0; i < mConfig.ObjectsPerPage_; ++i)
{
// If one object is in use, the page isn't empty
if (CheckInUse(reinterpret_cast<void*>(pos)))
{
isEmpty = false;
break;
}
// Prevents past-one check
if (i != mConfig.ObjectsPerPage_ - 1)
pos += mSkipSize;
}
// If the current page is empty
if (isEmpty)
{
// Update stats
mStats.FreeObjects_ -= mConfig.ObjectsPerPage_;
--mStats.PagesInUse_;
++pagesFreed;
// Update the freelist pointer
listPointer = mFreeList;
// Remove items from the freelist that are in the empty page
// While inside the empty page
while (listPointer > pagePointer &&
(reinterpret_cast<char*>(listPointer) < (reinterpret_cast<char*>(pagePointer) + mStats.PageSize_)))
{
listPointer = listPointer->Next;
prevList = listPointer;
}
while (listPointer)
{
nextNode = listPointer->Next;
while (nextNode > pagePointer &&
(reinterpret_cast<char*>(nextNode) < (reinterpret_cast<char*>(pagePointer) + mStats.PageSize_)))
nextNode = nextNode->Next;
listPointer->Next = nextNode;
listPointer = listPointer->Next;
}
// Set new head for the freelist
mFreeList = prevList;
// Delete the page if it's the first one
if (prevPage == NULL)
{
// Rearrange pointers
GenericObject* temp = pagePointer->Next;
delete [] reinterpret_cast<char*>(pagePointer);
pagePointer = temp;
head = pagePointer;
mPageList = head;
}
// Not the first page
else
{
// Rearrange pointers
prevPage->Next = pagePointer->Next;
delete [] reinterpret_cast<char*>(pagePointer);
pagePointer = prevPage->Next;
mPageList = head;
}
}
else
{
prevPage = pagePointer;
pagePointer = pagePointer->Next;
}
}
return pagesFreed;
}
/******************************************************************************/
/*!
\brief
Returns true if FreeEmptyPages and alignments are implemented
\return
True or False
*/
/******************************************************************************/
bool ObjectAllocator::ImplementedExtraCredit(void)
{
return false;
}
/******************************************************************************/
/*!
\brief
Testing/Debugging/Statistic methods
\param State
Changes the state of the DebugOn flag.
true=enable, false=disable
*/
/******************************************************************************/
void ObjectAllocator::SetDebugState(bool State)
{
mConfig.DebugOn_ = State;
}
/******************************************************************************/
/*!
\brief
Returns a pointer to the internal free list
\return
Pointer to the free list
*/
/******************************************************************************/
const void *ObjectAllocator::GetFreeList(void) const
{
return mFreeList;
}
/******************************************************************************/
/*!
\brief
Returns a pointer to the internal page list
\return
Pointer to the page list
*/
/******************************************************************************/
const void *ObjectAllocator::GetPageList(void) const
{
return mPageList;
}
/******************************************************************************/
/*!
\brief
Returns the configuration parameters
\return
Configuration struct
*/
/******************************************************************************/
OAConfig ObjectAllocator::GetConfig(void) const
{
return mConfig;
}
/******************************************************************************/
/*!
\brief
Returns the statistics for the allocator
\return
Stats struct
*/
/******************************************************************************/
OAStats ObjectAllocator::GetStats(void) const
{
return mStats;
}
/******************************************************************************/
/*!
\brief
Helper Function.
Creates a page, adds it to the page list and divides it into blocks that
are also added to the free list.
*/
/******************************************************************************/
void ObjectAllocator::MakePage() throw (OAException)
{
char *heap;
// Dynamically allocate the page
try
{
heap = new char[mStats.PageSize_];
}
catch (std::bad_alloc)
{
throw OAException(OAException::E_NO_MEMORY, "System out of memory.");
}
// Set all bytes to AA
if (mConfig.DebugOn_)
std::memset(heap, UNALLOCATED_PATTERN, mStats.PageSize_);
// Push Front of PageList
GenericObject* temp = mPageList;
mPageList = reinterpret_cast<GenericObject*>(heap);
mPageList->Next = temp;
// Left Alignment
if (mConfig.DebugOn_)
std::memset(heap + sizeof(void*), ALIGN_PATTERN, mConfig.LeftAlignSize_);
// Creates a linked list from the allocated block of memory
for (unsigned i = 0; i < mConfig.ObjectsPerPage_; ++i)
{
char *pos = heap + mOffset + i * mSkipSize; // Position
// Push front of FreeList
temp = mFreeList;
mFreeList = reinterpret_cast<GenericObject*>(pos);
mFreeList->Next = temp;
if (mConfig.DebugOn_)
{
// Padding
std::memset(pos - mConfig.PadBytes_, PAD_PATTERN, mConfig.PadBytes_);
std::memset(pos + mStats.ObjectSize_, PAD_PATTERN, mConfig.PadBytes_);
// Header Block
std::memset(pos - mConfig.PadBytes_ - mConfig.HBlockInfo_.size_, 0, mConfig.HBlockInfo_.size_);
// Inter Alignment
if (i < mConfig.ObjectsPerPage_ - 1)
std::memset(pos + mConfig.PadBytes_ + mStats.ObjectSize_, ALIGN_PATTERN, mConfig.InterAlignSize_);
}
}
// Update Stats
++mStats.PagesInUse_;
mStats.FreeObjects_ = mConfig.ObjectsPerPage_;
}
/******************************************************************************/
/*!
\brief
Helper Function.
Runs the checks for double free and out of bounds and throws exceptions
if required.
\param Object
Pointer to the object to check.
*/
/******************************************************************************/
void ObjectAllocator::DebugExceptions(void *Object) throw (OAException)
{
GenericObject* temp = mPageList;
GenericObject* tObject = reinterpret_cast<GenericObject*>(Object);
// Walk the PageList
while (temp)
{
// If the object is out of bounds of the current page
if (tObject < temp || tObject > (temp + mStats.PageSize_))
{
// If this is the last page, throw
if (!temp->Next)
throw OAException(OAException::E_BAD_BOUNDARY, "The block of memory provided is out of bounds.");
// If there are more pages, keep walking the PageList
else
temp = temp->Next;
}
// Inside of page bounds
else
{
// Calculates the distance from the start of the page minus the PageList Pointer
long int dist = reinterpret_cast<char*>(Object) -
reinterpret_cast<char*>(temp) - mOffset;
// If distance if positive and the distance mod the size of the object
if ((dist % mSkipSize) == 0)
break;
else
throw OAException(OAException::E_BAD_BOUNDARY, "The block of memory provided is not a valid one.");
}
}
// Check for Double free (optimized)
if (*(reinterpret_cast<char*>(Object) + sizeof(void*)) == static_cast<char>(FREED_PATTERN))
throw OAException(OAException::E_MULTIPLE_FREE, "This block of memory is already freed.");
//// Checks for Double free (Walks the whole FreeList)
//temp = mFreeList;
//while (temp)
//{
// if (reinterpret_cast<GenericObject*>(Object) == temp)
// throw OAException(OAException::E_MULTIPLE_FREE, "This block of memory is already freed.");
// temp = temp->Next;
//}
}
/******************************************************************************/
/*!
\brief
Helper Function.
Checks if the memory block at the given address is corrupter by checking
the pad bytes.
\param Object
Pointer to the object to check.
\return
True if block is corurpted
False if it is not corrupted
*/
/******************************************************************************/
bool ObjectAllocator::CheckCorruption(void* Object) const
{
// Check all padbytes
for (unsigned i = 0; i < mConfig.PadBytes_; ++i)
{
// If padbytes where modified, return true
if (*(reinterpret_cast<char*>(Object) - i - sizeof(char)) != static_cast<char>(PAD_PATTERN) ||
(*(reinterpret_cast<char*>(Object) + mStats.ObjectSize_ + i)) != static_cast<char>(PAD_PATTERN))
return true;
}
return false;
}
/******************************************************************************/
/*!
\brief
Helper Function.
Checks if the memory block at the given address is in use. Different
checks get run depending on the type of header block being used.
\param Object
Pointer to the object to check.
\return
True if block is in use
False if it is not in use
*/
/******************************************************************************/
bool ObjectAllocator::CheckInUse(void *Object) const
{
unsigned type = mConfig.HBlockInfo_.type_;
// If header is basic or extended, you check the "in use" flag
if (type == OAConfig::hbBasic ||
type == OAConfig::hbExtended)
{
if (*(reinterpret_cast<char*>(Object) - sizeof(char) - mConfig.PadBytes_) == 1)
return true;
else
return false;
}
// If header is external, check if the MemBlockInfo struct exists
else if (type == OAConfig::hbExternal)
{
char *temp = reinterpret_cast<char*>(Object) - mConfig.HBlockInfo_.size_ - mConfig.PadBytes_;
MemBlockInfo** mem = reinterpret_cast<MemBlockInfo**>(temp);
if ((*mem))
return true;
else
return false;
}
// If no header blocks are being used
else
{
GenericObject* listPointer = mFreeList;
// Walk the free list
while (listPointer)
{
// And compare it to the object. Return true if the object is on the free list
if (listPointer == Object)
return true;
listPointer = listPointer->Next;
}
// False otherwise
return false;
}
}
/******************************************************************************/
/*!
\brief
Helper Function.
Initializes all the varibales for mConfig and mStats at the creation of
the Object Allocator
\param ObjectSize
Size of the objects to be allocated
*/
/******************************************************************************/
void ObjectAllocator::Initialize(size_t ObjectSize)
{
// Set values for Stats variables
mStats.ObjectSize_ = ObjectSize;
// Initialize to Zero
mStats.Allocations_ = 0;
mStats.Deallocations_ = 0;
mStats.FreeObjects_ = 0;
mStats.MostObjects_ = 0;
mStats.ObjectsInUse_ = 0;
mStats.PagesInUse_ = 0;
// Calculate skip size
mSkipSize = mStats.ObjectSize_ + // Objects
2 * mConfig.PadBytes_ + // Padding
mConfig.HBlockInfo_.size_; // Header Block
// Initial mOffset
mOffset = sizeof(void*) + // PageList Pointer
mConfig.PadBytes_ + // Padding
mConfig.HBlockInfo_.size_; // Header Block
if (mConfig.Alignment_ > 1)
{
// Alignment
mConfig.LeftAlignSize_ = static_cast<unsigned>(mConfig.Alignment_ - (mOffset % mConfig.Alignment_));
mConfig.InterAlignSize_ = static_cast<unsigned>(mConfig.Alignment_ - (mSkipSize % mConfig.Alignment_));
// Update offsets
mOffset += mConfig.LeftAlignSize_;
mSkipSize += mConfig.InterAlignSize_;
}
// Update Page size
mStats.PageSize_ = sizeof(void*) + // PageList pointer
mConfig.LeftAlignSize_ - // Initial Alignment
mConfig.InterAlignSize_ + // Minus the last alignment (not set)
mConfig.ObjectsPerPage_ * // This multiplies everything below
(mStats.ObjectSize_ + // Objects
(mConfig.PadBytes_ * 2) + // Padding(x2) (before and after)
mConfig.HBlockInfo_.size_ + // Header Blocks
mConfig.InterAlignSize_ ); // Inter Alignment
}
[top]
Alejandro Hitti 