I finished my memory management prototype last night, but I'm worried that my whole strategy is not efficient.
I will illustrate what my idea was.
I use one big piece of memory like this:
[ ........................lots of MB............................ ]
Every piece of memory has a header, which looks as follows:
struct MemBlock
{
void* loPtr; /**< Low pointer of the available memory without header */
void* hiPtr; /**< High pointer of available memory */
MemBlock* next, *prev; /**< Links of the list */
unsigned int size; /**< Size of the memory (without header */
char taken; /**< Marks if block is ready to be used */
};
Every block of memory that is taken receives this header. It is in essence a double linked list.
A block looks as follows:
[ HEADER | ..... memory to be used by application .... ]
After a few allocs the big memory block looks as follows:
[hhh| ...... ][hhh| ..........][hhh| ... ] etc etc
where "hhh" is a header
I have my doubts about this whole idea of using headers. Every header is 28 bytes. With a bit of bad luck and many small objects I have more header data than actual usable data.
On the other hand, this is fast. This is all pointer work. No new objects that need to be pushed down a list, no ordening of lists. Looping through the whole list is fast too.
What are your opinions about this? Would it be better to adapt to a seperate list for header information?
Here's the current source code. I have tested it with the basic functionality to see if allocating and freeing works. It seems to, but a real thorough test still remains to be done.
#ifndef MEMORYMANAGER_H
#define MEMORYMANAGER_H
#include <vector>
using std::vector;
#include <assert.h>
#include <stdio.h>
#define MEM_ALLOC_SIZE 1024*1024*100 // megabytes
/*
comment these defines to disable functionality
*/
//#define MEM_TRACK_ALLOCS 1 /**< Keeps track of allocations */
//#define MEM_REG_ALLOCS 1 /**< Registers all allocations to file */
#define MEM_CHECK_BOUNDS /**< Check the bounds of a block */
/*
END
comment these defines to disable functionality
*/
#define MEM_BOUNDS_SIZE 8
#define MEM_BOUNDS_VALUE 0xDEADBEEF
#define MEM_FNAME_SIZE 256
struct MemBlock
{
#if defined MEM_TRACK_ALLOCS | MEM_REG_ALLOCS // guard with defines to save memory
char file[MEM_FNAME_SIZE];
int line;
#endif
void* loPtr; /**< */
void* hiPtr; /**< */
MemBlock* next, *prev;
unsigned int size; /**< */
char taken;
};
struct MemLog
{
};
class MemoryManager
{
public:
MemoryManager()
{
}
~MemoryManager()
{
}
static void init()
{
heap = (char*)malloc(MEM_ALLOC_SIZE);
if (heap == NULL)
{
assert( "COULD NOT ALLOCATE MEMORY" && false );
}
MemBlock* b = (MemBlock*)heap; // move to first...
memset(heap,0x00,sizeof(MemBlock));
b->loPtr = (void*)&heap[sizeof(MemBlock)];
b->hiPtr = (void*)&heap[MEM_ALLOC_SIZE - 1 - sizeof(MemBlock)];
b->size = MEM_ALLOC_SIZE - sizeof(MemBlock);
b->next = 0;
b->prev = 0;
b->taken = 0;
}
static void clean()
{
if (heap)
free(heap);
}
static void* MMmalloc(int size)
{
MemBlock* b = (MemBlock*)heap;
MemBlock* n;
while (b)
{
if (b->taken == 0 && (b->size - sizeof(MemBlock)) > size)
/*
This is tricky thinking. If a new block should fit in this free block, then a new header should be added
The size of the header should be deducted from the total available size.
*/
{
n = (MemBlock*)&((char*)b->loPtr)[size]; // move the n-pointer (n stands for new) to the end of the block
// <->[b->next]
// <->[n]<->[b->next]
n->prev = b;
n->next = b->next;
b->next = n;
if (n->next)
n->next->prev = n;
// [bbb|b.lo ...................... b.hi]
// [bbb|b.lo ... b.hi][nnn|n.lo ... n.hi]
n->loPtr = &((char*)n)[sizeof(MemBlock)];
n->hiPtr = b->hiPtr;
b->hiPtr = &((char*)b->loPtr)[size-1];
n->size = b->size - size - sizeof(MemBlock);
b->size = size;
n->taken = 0;
b->taken = 1;
return b->loPtr;
}
else if (b->taken == 0 && b->size >= size)
/*
The block would not fit, but perhaps this is because the size of the header was just atad too much.
Well, instead we just keep the header and put the data in this block.
*/
{
b->taken = 1;
return b->loPtr;
}
b = b->next;
}
return NULL;
}
static void* MMmalloc(int size, char* file, int line)
{
return MMmalloc(size);
}
static void MMfree(void* address)
{
MemBlock* b = (MemBlock*)heap;
int returnFlag = 0;
while (b)
{
if (address == b->loPtr)
{
b->taken = 0;
//[aaa| ... ][xxx| ...... ][bbb| ... ][yyy| ......]
//[aaa| ... ][xxx| ................. ][yyy| ......]
if (b->prev != NULL)
{
if (b->prev->taken == 0) // only xxx is free
{
b->prev->next = b->next;
b->prev->hiPtr = b->hiPtr;
if (b->next)
b->next->prev = b->prev;
b->prev->size += b->size + sizeof(MemBlock);
b=b->prev; // Adjustment: if the following statement is true, then b should point to the new header, not the old one.
returnFlag = 1;
}
}
//[xxx| ...... ][bbb| ... ][yyy| ......][zzz| ...... ]
//[xxx| ...... ][bbb| ................ ][zzz| ...... ]
if (b->next != NULL)
{
if (b->next->taken == 0) // only yyy is free
{
b->size += b->next->size + sizeof(MemBlock);
b->hiPtr = b->next->hiPtr;
b->next = b->next->next;
if (b->next)
b->next->prev = b;
returnFlag = 1;
}
}
if (returnFlag)
return;
}
b = b->next;
}
}
static void writeMap(char* filename)
{
FILE* file;
char line [ 256 ];
int i;
int linesize;
int maxlinesize = 100;
if (!filename)
return;
file = fopen(filename, "w");
if (!file)
return;
MemBlock* b = (MemBlock*)heap;
sprintf(line, "MEMORY MAP\n---------------------\nSize: %i bytes (%x hex)\nHeader Size: %i (%x hex)\n---------------------\n",MEM_ALLOC_SIZE, MEM_ALLOC_SIZE, sizeof(MemBlock), sizeof(MemBlock));
fputs(line, file);
i=0;
while (b)
{
sprintf(line, "[ %i (%i) | %x ... (size %i b) %x ]\n", i, b->taken, b->loPtr, b->size, b->hiPtr);
b = b->next;
i++;
fputs(line, file);
}
}
private:
static char* heap;
// static vector<MemBlock*> freeBlocks;
// static vector<MemBlock*> takenBlocks;
// static vector<MemBlock> blocks;
// static vector<MemBlock> dead;
// static vector<MemLog> log;
// static int opCount;
// static int missCount;
// static int algoCount;
};
inline void* __cdecl operator new(size_t nSize, char* lpszFileName, int nLine)
{
return MemoryManager::MMmalloc(nSize, lpszFileName, nLine);
}
inline void __cdecl operator delete(void* mem)
{
MemoryManager::MMfree(mem);
}
#define new _MEM_DEBUG_NEW_
#define delete _MEM_DEBUG_DELETE_
#ifndef __FILE__
#define __FILE__ "No __FILE__ define known"
#endif
#ifndef __LINE__
#define __LINE__ -1
#endif
#define _MEM_DEBUG_NEW_ new(__FILE__,__LINE__)
#define _MEM_DEBUG_DELETE_ delete
#if defined MEM_TRACK_ALLOCS || MEM_REG_ALLOCS // Only give filename and line if debugging
#define malloc(size) MemoryManager::MMmalloc(size, __FILE__, __LINE__);
#else
#define malloc(size) MemoryManager::MMmalloc(size);
#endif
#define free(addr) MemoryManager::MMfree(addr)
#endif