Last Ray of Hope

The final entry for my Athena: Memory Management (Part 1 and Part 2), this entry will cover my code for merging unallocated blocks into a single block and splitting memory blocks into smaller blocks.

For merging unallocated blocks, I iterate through each unallocated block, and if the next block is not out of memory pool range and is unallocated, then the current memory header has its size and the size of its header added to it. By continuing after this, we repeat the same process for the merged block incase there is more free memory after it.

//
//
void MemoryHeap::MergeFreeBlocks()
{
unsigned char * pCurrentMemory = static_cast<unsigned char *>( m_memoryPool );

for( unsigned int byteIdx = 0; byteIdx < kMemoryPoolSize; )
{
BasicMemoryHeader * pCurrentHeader = reinterpret_cast<BasicMemoryHeader *>( &pCurrentMemory[byteIdx] );

if( pCurrentHeader->usage == kBlockUsage_UnAllocated )
{
const unsigned int kNextHeaderOffset = byteIdx + sizeof( BasicMemoryHeader ) + pCurrentHeader;
BasicMemoryHeader * pNextHeader = reinterpret_cast<BasicMemoryHeader *>( &pCurrentMemory[kNextHeaderOffset] );

if( kNextHeaderOffset < kMemoryPoolSize && pNextHeader->usage == kBlockUsage_UnAllocated )
{
pCurrentHeader->size += sizeof( BasicMemoryHeader ) + pNextHeader->size;
continue;
}
}

byteIdx += sizeof( BasicMemoryHeader ) + pCurrentHeader->size;
}
}

When splitting a memory block, first I check to see if there is enough space left over from what I’m allocating for a new header and 16 bytes worth of memory. The 16 bytes is arbitrary, any value is acceptable as long as it is greater than 0. If there isn’t enough space left over, the function exits without splitting the memory block.

However if there is, the next memory header is setup using the space that is left over after subtracting the new memory header size and the space required for the original memory block. The original memory block size is then set to the require memory block size.

//
//
void MemoryHeap::SplitMemoryBlock( BasicMemoryHeader * inBlockHeader, const unsigned int inSize )
{
const unsigned int kRequiredForSplit = sizeof( BasicMemoryHeader ) + 16;

//
// Don't Split if it is the correct size
if( inBlockHeader->size < ( inSize + kRequiredForSplit ) )
{
return;
}

//
// Setup New Header from Split
unsigned char * nextHeaderPointer = reinterpret_cast<unsigned char *>( inBlockHeader ) + sizeof( BasicMemoryHeader ) + inSize;
BasicMemoryHeader * nextHeader = reinterpret_cast<BasicMemoryHeader *>( nextHeaderPointer );
nextHeader->size = inBlockHeader->size - inSize - sizeof( BasicMemoryHeader );
nextHeader->usage = kBlockUsage_UnAllocated;

//
// Set old header size to input size
inBlockHeader->size = inSize;
}

Finally for when I run out of memory, I output a message to the debug console window, cause an assertion, and if the code attempts to continue, it will cause the application to exit immediately with a code 1.

//
//
void MemoryHeap::OutOfMemory() const
{
printf( "Memory Heap has run out of memory.\n" );
assert( 0 );
exit( 1 );
}

Well thats my basic memory heap for the moment. It still has lots of work since it isn’t perfect, one flaw with this memory heap is that it doesn’t support aligned allocations and reallocation.

Following on from my previous entry, Athena: Memory Manager (Part 1), this will show my code for allocation and freeing of memory.

//
//
void * MemoryHeap::Allocate( const unsigned int inSize )
{
//
//
unsigned char * pCurrentMemory = static_cast<unsigned char *>( m_memoryPool );

for( unsigned int byteIdx = 0; byteIdx < kMemoryPoolSize; )
{
//
//
BasicMemoryHeader * pCurrentHeader = reinterpret_cast<BasicMemoryHeader *>( &pCurrentMemory[byteIdx] );

if( pCurrentHeader->usage == kBlockUsage_UnAllocated && pCurrentHeader->size >= inSize )
{
//
//
SplitMemoryBlock( pCurrentHeader, inSize );

//
//
pCurrentHeader->usage = kBlockUsage_Allocated;
return pCurrentMemory + sizeof( BasicMemoryHeader );
}

byteIdx += sizeof( BasicMemoryHeader ) + pCurrentHeader->size;
}

//
// No adequate memory block found, must be out of memory.
OutOfMemory();
return 0;
}

Unlike the memory allocation function, the free function just takes the pointer we are passing in and subtracts the size of the header from it. Since the actual block of memory is offset by the header size from the header, by going backwards we can get instant access to the header.

//
//
void MemoryHeap::Free( void * inPointer )
{
//
//
unsigned char * memoryBlockOffset = static_cast<unsigned char *>( inPointer );

//
//
BasicMemoryHeader * pBlockHeader = reinterpret_cast<BasicMemoryHeader *>( memoryBlockOffset - sizeof( BasicMemoryHeader ) );
pBlockHeader->usage = kBlockUsage_UnAllocated;

//
//
MergeFreeBlocks();
}

Thats all for now, the next entry will finish off my basic memory heap class.

After reading Object-Orientated Game Development, I came up with some ideas for managing memory pools. Basically it works like this, after first allocating a pool of memory of size X, the first header size is subtracted from this.

So a basic memory header would be the following code. It stores the size of the memory block following it and whether that memory block has been allocated. The size of this memory header is 8 bytes, 4 bytes for the size and 4 bytes for the usage. I will probably expand this later by adding memory guards, and maybe a pointer to the next free block to improve lookup times.

#ifndef BASICMEMORYHEADER_H_INCLUDED
#define BASICMEMORYHEADER_H_INCLUDED

//
//
enum BlockUsage
{
kBlockUsage_UnAllocated,
kBlockUsage_Allocated
};

//
//
struct BasicMemoryHeader
{
BasicMemoryHeader()
:
usage( kBlockUsage_UnAllocated ),
size( 0 )
{
}

BlockUsage usage;
unsigned int size;
}

#endif

Now for the heap object, it will contain my pool of memory. If I use 100,008 bytes, after the first 8 bytes of our pool are used for the first header, I will have 100,000 bytes available for allocation. I have the two main functions, ‘Alloc()‘ for allocating memory, and ‘Free()‘ for releasing allocated memory.

My other three functions are used when allocating and freeing memory. After I have freed a memory block, I’ll make a call to ‘MergeFreeBlocks()’, which will iterate through all memory blocks and merge two blocks together that are next to each other in memory.

When allocating memory, when I find a suitably sized memory block, I’ll make a call to ‘SplitMemoryBlock()‘, passing to it the memory block I found, and the amount of blocks I need allocated from it, if there is more than enough memory, at the end of my allocation size, a new memory header with the remainder of memory, while the original will be updated to my usage request.

If when allocating there is not enough memory, I’ll make a call to ‘OutOfMemory()‘.

#ifndef MEMORYHEAP_H_INCLUDED
#define MEMORYHEAP_H_INCLUDED

//
//
#include "BasicMemoryHeader.h"

//
//
class MemoryHeap
{
//
// Attributes
private:
const unsigned int kMemoryPoolSize;
void * m_memoryPool = 0;

//
// Functions
public:
//
//
MemoryHeap();

//
//
~MemoryHeap();

//
//
void * Allocate( const unsigned int inSize );

//
//
void Free( void * inPointer );

private:
//
//
void MergeFreeBlocks();

//
//
void SplitMemoryBlock( BasicMemoryHeader * inBlockHeader, const unsigned int inUsageSize );

//
//
void OutOfMemory() const;
}

#endif

This is my basic setup for memory heap after it has been created and destroyed.

I wanted to check to see if any memory hasn’t been deallocated when the destructor is called, so I iterate through all memory blocks to checked to see if they are allocated. If they are allocated, I make an assert happen.

//
//
#include "MemoryHeap.h"

//
//
MemoryHeap::MemoryHeap()
:
kMemoryPoolSize( 100008 )
{
//
// Allocated Memory Pool
m_memoryPool = malloc( kMemoryPoolSize );

//
// Setup First Memory Header
BasicMemoryHeader * firstMemoryHeader = static_cast<BasicMemoryHeader *>( m_memoryPool );
firstMemoryHeader.size = kMemoryPoolSize - sizeof( BasicMemoryHeader );
}

//
//
MemoryHeap::~MemoryHeap()
{
const unsigned char * pCurrentMemory = static_cast<unsigned char *>( m_memoryPool );

//
//
for( unsigned int byteIdx = 0; byteIdx < kMemoryPoolSize; )
{
const BasicMemoryHeader * pCurrentHeader = reinterpret_cast<BasicMemoryHeader *>( &pCurrentMemory[byteIdx] );
assert( pCurrentHeader->usage == kBlockUsage_UnAllocated );
byteIdx += sizeof( BasicMemoryHeader ) + pCurrentHeader->size;
}

//
//
free( m_memoryPool );
}

I don’t want to get this blog entry clogged up with code, so I’ll post the allocation and free code in the next entry, and the merge / split code in the entry after.

With my job near starting (This Monday), I’ve decided my PC needs a bit of an upgrade, been nearly a year since I last added something to it.

A lot of things I already have such as a great 2ms 3000:1 monitor, and G7 carbon fibre edition mouse.

So after a while of browsing the web, checking bandwidths of DDR3 over DDR2, and seeing what I could build on the Dell website, I starting playing around with ideas on the Scan website, looking for some amazing parts.

The end result in my opinion, is a Behemoth of a machine, and I was holding back to keep the cost low (Imagine 3x SLi).

Heres what I have got:

Motherboard: Asus Striker II Extreme

CPU: Intel Core 2 Quad Extreme QX9770

Memory: 4GB (2×2GB) CorsairTwinX XMS3 Dominator DDR3

GPU (2x): 1GB EVGA 9800 GX2

HDD (2x): 1TB Samsung (32MB Cache)

Sound Card: Creative Soundblaster X-Fi Platinum Fatal1ty Champion

This all comes to a grand total of $2600.97. Just under a grand less than what Dell would have charged for a similar machine. The two HDD I will be putting in Raid 0 Striped.

Originally I was going to get a PhysX card, but as a friend pointed out to me, the latest nVidia drivers allow a 9 series card to be used for physics calculations.

Needless to say, unless I get out of a loan, its gonna be a gradual buildup til I can afford such a machine.

I’ve been seeing a lot of code recently with empty statements. An empty statement is something in code that does something useless whilst doing now. You’re probably wondering how can you do something useful whilst doing nothing, well take this example code into consideration.

#define FREE_MEMORY( x ) free( (x) ); x = 0

It is a macro to free memory and nullify the pointer associated with it. Now when trying to implement it in code.

void main()
{
void * p = 0;

// Okay
FREE_MEMORY( p );

// Okay
if( p )
FREE_MEMORY( p );

// Okay
if( p )
p = 0;
else
FREE_MEMORY( p );

// Bad Syntax
if( p )
FREE_MEMORY( p );
else
p = 0;
}

As you can see, it is all okay until the if-else statement where the FREE_MEMORY() macro comes after. The reason why this fails is that if-else statement only allows one statement after the if and else, scope brackets ({}) are required for more.

So we add scope brackets to the macro.

#define FREE_MEMORY( x ) { free( (x) ); x = 0; }

Now if this macro is treated like another other function and an end statement (;) is used with it, then the if-else will fail again. The reason why this time is because when it is expanded, we have an end statement where there shouldn’t be one.

void main()
{
if( p )
{
free( (p) );
(p) = 0;
}; // End Statement causes syntax error
else
p = 0;
}

So the one way around this is to implement something with scope that is postfixed with an end statement, and does nothing.. a do-while.

#define FREE_MEMORY( x ) do { free( (x) ); x = 0; } while( 0 )

Now when we use it, everything works as it should do when expanded.

void main()
{
if( p )
do
{
free( (p) );
(p) = 0;
} while( 0 );
else
p = 0;
}

The do-while is a scoped statement, and since it’s continuation argument is set to 0 (false), it will exit when finished.

A few days ago I posted about a wonderous operator I had just found out about, known as Placement New. However after playing around with it a bit, I came by a slight problem with it.

To understand it, lets look at the class below.

#ifndef TEST_H_INCLUDED
#define TEST_H_INCLUDED

// --- [ includes ] -------------------------------------------
//
#include <stdlib.h>

// --- [ class ] ----------------------------------------------
//
class Test
{
// Attributes
//
private:
void * m_pData;

// Functions
//
public:
Test()
{
m_pData = malloc( 100 );
}

~Test()
{
free( m_pData );
}
};

#endif

A very basic class, in it’s constructor it allocates 100 bytes of memory and then frees that 100 bytes in its destructor, so no memory leak as long as the destructor is called. Now lets see this in action with placement new.

// --- [ includes ] -------------------------------------------
//
#include "Test.h"
#include <new>

// --- [ prototypes ] -----------------------------------------
//
template<class T>
void CallDestructor( T* inObject );

template<class T>
void CallDestructor( T** inObject );

// --- [ entry point ] ----------------------------------------
//
void main()
{
char buffer[2048];

// Case 1: Single New
{
// Create Class
Test * pClass = new ( buffer ) Test();

// Call class destructor
CallDestructor( pClass );
}

// Case 2: Single New Array of Pointers
{
// Create Pointer List
Test ** pClassList = new ( buffer ) Test*[10];

// Call destructor
CallDestructor( pClassList );
}
}

// --- [ functions ] ------------------------------------------
//
template<class T>
void CallDestructor( T* inObject )
{
inObject->~T();
}

template<class T>
void CallDestructor( T** inObject )
{
// Do nothing
}

Those both work fine, however the problem arises when you allocate an array of objects as below.

// --- [ includes ] -------------------------------------------
//
#include "Test.h"
#include <new>

// --- [ prototypes ] -----------------------------------------
//
template<class T>
void CallDestructor( T* inObject );

template<class T>
void CallDestructor( T** inObject );

// --- [ entry point ] ----------------------------------------
//
int main()
{
char buffer[2048];

// Case 1: Single New
{
// Create Class
Test * pClass = new ( buffer ) Test();

// Call class destructor
CallDestructor( pClass );
}

// Case 2: Single New Array of Pointers
{
// Create Pointer List
Test ** pClassList = new ( buffer ) Test*[10];

// Call destructor
CallDestructor( pClassList );
}

// Case 3: Multiple Object New in Array
{
// Create Array of Objects
Test * pClassArray = new ( buffer ) Test[10];

// Call destructor
CallDestructor( pClassArray );
}

return 0;
}

// --- [ functions ] ------------------------------------------
//
template<class T>
void CallDestructor( T* inObject )
{
inObject->~T();
}

template<class T>
void CallDestructor( T** inObject )
{
// Do nothing
}

If you debug through this code you’ll notice that case 1 and 2 still work, however when you get to case 3, the destructor is only called once, since it cannot tell the difference between an array and a single class that was allocated with new.

I can only think of three ways around this at the moment.

1. Store the Number of Objects in this array and manually iterate through free them
2. Override the placement new operator with my own that adds a header to the memory block that stores the number of elements so it can be retrieved to iterate through.
3. Override the default delete operator, this way the delete operator can be used as you normally would to free objects created with new.

The last option seems to the best one, however overriding both default delete operators would mean I’d need my own memory management system, and override the default new operators as well.

Best get to work on that…

I recently discovered two operators that expand on new and delete. They are known as the placement operators. Basically they allow you to allocate memory to preallocated memory, rather than calling new and delete for every object (reducing segfaults).

// --- [ includes ] -------------------------------------------
//
#include <iostream>
#include <new>

// --- [ class ] ----------------------------------------------
//
class Test
{
// Attributes
//
private:
int m_value;

// Functions
//
public:
//
//
Test()
:
m_value( 20 )
{
}

// Set Value
//
void SetValue( const int inValue )
{
m_value = inValue;
}

// Get Value
//
int GetValue() const
{
return m_value;
}
};

// --- [ entry point ] ----------------------------------------
//
void main()
{
// 2096 Bytes of Data
//
char buffer[2096];

// Allocate Memory from Buffer and call constructor
//
Test * pClass = new (buffer) Test();

// Get Value set in Constructor
//
std::cout << "Value: " << pClass->GetValue() << std::endl;

// Call Destructor
//
pClass->~Test();
}

I have to admit, there are quite a few good uses for this, I’ll probably play around with it for the next few days, see if I can find problems that may occur from using it.