Memory System
Preface
I have spent a lot of time on this. I know nothing about this kind of stuff before. Also, I’m not that familiar with the C++ programming pattern. For PA2, the teacher’s code include a “singleton pattern” which confuse me a lot at the beginning. After I read the book and look for the website, I learnt that this is a very common design pattern, which help creating a global single object, I think I should take some time to learn something about that.
I have no idea how to deal with everything at the beginning, but some of my class mates finish their homework very fast, which makes me under pressure. I check my classmate Weixing An’s code, and under how the whole system working. I write my code referenced his code at first, and finally finished non-fixed block part for this assignment.
Two weeks later, after the midterm, I finally got some time to re-work on this Memory System. I read the book Memory Allocation Chapter of “Game Engine Architecture”, which helps me understand why we need to do this and how to adjust alignment. This time, I delete all my previous code, and write it from blank. I finally finished the normal and fixed block, which, I think, should follow the design better than others students. This assignment helps me a lot on the understanding of memory stuff.
Why we need memory system for game engine
malloc & new is slow
It’s a general-purpose facility, need to handle a lots of management.
In most operate system, call malloc and free must context-switch from user mode into kernel mode.
Count the usage of the memory
We need to count the current usage memory, allocation times, and peak memory usage for debugging and improving performance.
Deal with memory fragmentation
We can improve the problem of fragmentation, like design the memory as a stack or pool.
Memory System Design
Tracking Block class
Store the information for each block. Include 4 pointer for two double links.
Heap class
Store the information for each heap. Include 2 pointer for Heap links.
HeapInfo
The structure in the Heap class storing the heap block information.
Mem class
Store the whole memory system information.
Store the head pointers point to Heap list head and Tracking Block list head.
MemInfo
The structure in the Mem class storing the memory system information.
Overload new & delete
To use our memory system, it means, we create our object into the memory where the tracking block is, and use tracking block to manage them.
So we need to overload original new and delete to offer these function.
Out new function should return the pointer that points to the raw memory in the tracking block.
Alignment
Data should be stored in alignment. The return pointer of the new operator should be aligned.
To adjust the data to be aligned, we should put an extra padding in each block’s tracking block.
And, when delete, we need a return pointer to get the Tracking block. We can store it in the 4 bytes just upon the raw memory.
Implement
Singleton Pattern
Only one Mem object is created in the whole system. We use a singleton pattern to design it.
Code Example
// create a singleton
class Mem
{
private:
// Prevent default constructor, copy constructor, assignment operator from being called externally
Mem(){};
Mem( const Mem &in ){};
Mem &operator = (const Mem &in){};
~Mem(){};
// Magical internal function (singleton Keeper)
static Mem *privGetInstance( void );
};
// Magical internal function (singleton Keeper)
Mem* Mem::privGetInstance( void )
{
static Mem mSingleton;
return &mSingleton;
}
Windows Heap API
Get the memory from system memory.
HeapCreate
Creates a private heap object, return a win handle
HeapAlloc
Allocates a block of memory from a heap. The allocated memory is not movable.
new(pointer)object
“new” an object at the pointer’s memory location. Help us put the Heap head object in to the heap’s real memory location.
New & delete
There are two way to new and delete the system.
Normal Block
Call new
Get the needed size of allocation
Allocate the size + tracking block + padding
Put the tracking block into the memory
Link the linked list
Fixed Block
Allocate all heap when we create the heap
We should decide how large per block is before new
Create all the tracking block in the heap
Link all free block
When new, get the first node in the free memory linked list, unlink the node.
Return the aligned address.
When delete, relink the block in to the free list.
Linked list
Heap linked list
List links all heaps.
Heap tracking block linked list
Inside heap tracking block list.
Global tracking block linked list
A global linked list to track every allocation.
Notice:
When we destroy a Heap, we need to first remove all the tracking block, so the global list will not mess.
Need to rework
Here are something that I haven’t deal well when I do the assignment.
Need to rework when I have time.
All two kind of heap has a fixed size, how the deal with the issue, if I allocate more memory than it could offer.
The alignment might cost too many memories, need to make it better.
Jin Han
February 22, 2013
