/***********************************************************************
* Memory.c:
* Copyright (c) 2001, Eidatsu Interactive, Inc.
* All Rights Reserved
* Version: 0.0.0-1
*
* Revision History:
* *
*
* Notes:
* * This is a total rewrite of the previous memory manager featured
* on flipcode's COTD. The previous memory manager had a few
* dormant bugs that would cause corruption of the memory heap,
* and, only in some *rare* cases, a crash. Obviously, these bugs
* were hard to track down. Other than bug fixes, this total
* rewrite features MUCH MUCH MUCH cleaner and more easy-to-read
* code. Yay!
*
* * This code contains calls to functions and macros in our run-time
* library. These functions are not included, but their purpose
* should be pretty clear, and not need any further documentation.
*
* * Oh, and unlike the previous version, this version of the dyn
* memory allocator is now thread-safe.
*
* * ALL of the following functions are heavily dependant on machine
* size and architecture. Word-size is expected to be 32 bits.
**********************************************************************/
/***********************************************************************
* Function Declarations
**********************************************************************/
private void* _Alloc ( uword );
private void _Free ( void* );
export void* MemAlloc ( uword );
export void* MemReAlloc ( void*, uword );
export void MemFree ( void* );
public word _MemInitialize ( void );
public void _MemShutdown ( void );
/* Not included. */
export void MemCopy ( void*, const void*, uword );
export void MemMove ( void*, const void*, uword );
export void MemFill ( void*, uword, uint8 );
/***********************************************************************
* Global Variables
**********************************************************************/
private Mutex_t gMemMutex;
private DWORD gPageSize;
private uword *gFirstSuperBlock;
private uword *gEndOfLastSuperBlock;
private uword *gLastUsedBlock;
/***********************************************************************
* Function Macros
**********************************************************************/
#define MemArrayAlloc( size, count ) \
MemAlloc( (size) * (count) )
#define MemArrayReAlloc( ptr, size, count ) \
MemReAlloc( ptr, (size) * (count) )
#define MemZero( ptr, count ) \
MemFill( ptr, count, 0x00 )
/***********************************************************************
* Functions
**********************************************************************/
/* Block Header:
* ----------------
* | Block Size |E|F|
* ----------------
*
* Block Size: The offset to the next block header.
* E: Flag is set if this is the last block.
* F: Flag is set if this block is full (allocated).
*
* Superblock:
* --------------
* | Prev Pointer |
* --------------
* | Block Header | ---> E=0 F=1
* --------------
* | DATA |
* --------------
* | .... |
* --------------
* | DATA |
* --------------
* | Block Header | ---> E=1 F=0
* --------------
* | EMPTY |
* --------------
* | .... |
* --------------
* | EMPTY |
* --------------
* | Next Pointer |
* --------------
*
* Prev Pointer: Pointer to the previous superblock.
* Next Pointer: Pointer to the next superblock.
*
* The superblocks are kept in a circular linked list. If
* there is only one superblock, then both it's "next" and "prev"
* pointers point to the first byte in the superblock (which,
* coincidentally, is the "prev" pointer).
*/
private
void*
_Alloc
( uword Size )
{
uword *tmpblk;
uword NewSupBlockSize, tmpi;
/* We round the requested size up to the nearest multiple of eight
* bytes, and then add a four byte buffer. We also set tmpblk to
* gLastUsedBlock, as is required for the next block of code. */
Size = ((Size + 7) & 0xFFFFFFF8) + 4;
tmpblk = gLastUsedBlock;
/* We now do a search through the entire heap to see if there is
* a block of the right size available. */
do
{
/* If we find an unused block of the appropriate size, then
* we break out of this loop to the BlockFound label below. */
if ( (*tmpblk & 0x1) == 0 )
if ( (((*tmpblk >> 2) - 1) << 2) > Size )
goto BlockFound;
/* Otherwise we advance to the next block header. If the
* block we are currently looking at is the last in the
* superblock (the end bit is set), then we must advance
* one more time to the first block in the next
* superblock. */
tmpi = *tmpblk;
tmpblk = tmpblk + (tmpi >> 2);
if ( (tmpi & 0x2) != 0 )
tmpblk = (uword*)( *tmpblk + sizeof(uword) );
}
while ( tmpblk != gLastUsedBlock );
/* A block of the appropriate size was not found. We must
* therefore request another chunk of memory from the
* operating system. The new chunk of memory must be large
* enough to hold the requested memory, two pointers, and
* a block header, and must be a multiple of gPageSize.
*
* In the following calculation we assume that gPageSize is
* a power of 2. */
NewSupBlockSize = (Size + 3 * sizeof(uword) + gPageSize - 1) &
~(gPageSize - 1);
tmpblk = VirtualAlloc( NULL, NewSupBlockSize,
MEM_RESERVE | MEM_COMMIT,
PAGE_READWRITE );
if ( tmpblk == NULL )
return NULL;
/* Set the Prev pointer. */
*tmpblk = *gFirstSuperBlock;
/* Insert this new superblock into the heap as the last
* superblock. */
*gFirstSuperBlock = (uword) tmpblk;
*gEndOfLastSuperBlock = (uword) tmpblk;
gEndOfLastSuperBlock = tmpblk + (NewSupBlockSize >> 2) - 1;
/* Now set the Next pointer, which gEndOfLastSuperBlock
* now points to. */
*gEndOfLastSuperBlock = (uword) gFirstSuperBlock;
/* Before we move on to allocate the new block, we set up
* a default block the size of the newly allocated space,
* and set tmpblk equal to it's header. */
++tmpblk;
*tmpblk = (NewSupBlockSize - 2 * sizeof(uword)) | 0x2;
BlockFound:
/* If the block we found is too big, we split it. The cut-off
* limit of 24 is arbitrary. I have absolutly no idea what an
* optimal cut-off limit in real life situations would be. 24
* just sounded good.
*
* If we split, then we set gLastUsedBlock to the value of the
* second (free) block, otherwise we set it to the value of the
* block being used. */
if
( ((*tmpblk & 0xFFFFFFFC) - sizeof(uword) - Size) > 24 )
{
gLastUsedBlock = tmpblk + 1 + (Size >> 2);
*gLastUsedBlock = *tmpblk - Size - sizeof(uword);
*tmpblk = (Size + sizeof(uword)) | 0x1;
}
else
{
*tmpblk = *tmpblk | 0x1;
gLastUsedBlock = tmpblk;
}
return tmpblk + 1;
}
private
void
_Free
( void *Ptr )
{
uword *BlockToBeFreed, *BlockItr, *SupBlockFreedFrom;
uword tmpi;
/* The value passed to this function should be a pointer
* to the first byte of memory that was allocated - the
* same value that was returned from _Alloc(). To get
* the header of the block we're freeing, we simply move
* back one uword. */
BlockToBeFreed = ((uword*) Ptr) - 1;
/* We clear the "full" bit in the block header. */
*BlockToBeFreed = *BlockToBeFreed ^ 0x1;
/* Finding the next block after the one being freed is
* easy. */
if
( (*BlockToBeFreed & 0x2) != 0 )
{
/* We use BlockItr as a temporary. */
BlockItr = BlockToBeFreed + (*BlockToBeFreed >> 2);
/* If the next block is empty, we merge it and the
* block now being freed. */
if ( (*BlockItr & 0x1) == 0 )
*BlockToBeFreed += *BlockItr;
}
/* Now we find the previous block to the one being freed.
* This is a little more time consuming, as we need to
* advance all the way to the next superblock, use the
* Prev pointer to get back to the beginning of the
* superblock we're in, and then advance to the block
* right before the block we're freeing. */
BlockItr = BlockToBeFreed;
do
{
tmpi = *BlockItr;
BlockItr += tmpi >> 2;
}
while ( (tmpi & 0x2) != 0 );
SupBlockFreedFrom = **((uword***) BlockItr);
BlockItr = SupBlockFreedFrom + 1;
if
( BlockItr != BlockToBeFreed )
{
while ( BlockItr + (*BlockItr >> 2) != BlockToBeFreed )
BlockItr += (*BlockItr >> 2);
/* If the previous block is empty, we merge it and the
* block being freed. */
if
( (*BlockItr & 0x1) == 0 )
{
*BlockItr += *BlockToBeFreed;
BlockToBeFreed = BlockItr;
}
}
/* We set gLastBlockUsed to the value of BlockToBeFreed.
* That way the next call to _Alloc() will begin its search
* for free memory with an empty block, hopefully saving
* time in the long run. */
gLastUsedBlock = BlockToBeFreed;
/* Now we test to see if the superblock is empty, and if
* it is, then we request the operating system to free
* it. */
if
( (*(SupBlockFreedFrom + 1) & 0x2) != 0 )
{
/* We do not deallocate the superblock if it is the
* superblock pointed to by gFirstSuperBlock - that way
* we can be assured that there will always be at least
* one superblock in memory. */
if
( SupBlockFreedFrom != gFirstSuperBlock )
{
/* Before we free the superblock we must first remove it
* from the global list of superblocks. */
/* First we advance BlockItr to the Prev pointer in the
* next superblock, taking advantage of the fact that we
* know this superblock to contain only one unused block. */
BlockItr = SupBlockFreedFrom + 1;
BlockItr += *BlockItr >> 2;
BlockItr = *((uword**) BlockItr);
/* And then set this Prev pointer to the value of the Prev
* pointer in the superblock being freed. */
*BlockItr = *SupBlockFreedFrom;
/* In order to save on the number of variables we have,
* we use BlockToBeFreed as a temporary. */
BlockToBeFreed = BlockItr;
/* Now we set BlockItr to the beginning of the previous
* superblock, and advance until we reach the Next pointer
* at the end of the superblock. */
BlockItr = *((uword**) SupBlockFreedFrom) + 1;
do
{
tmpi = *BlockItr;
BlockItr += tmpi >> 2;
}
while ( (tmpi & 0x2) == 0 );
/* Now we set the Next pointer in the previous superblock to
* the address of the superblock after the one being freed.
* BlockToBeFreed, in this case, is just a temporary
* containing a pointer to the next superblock. */
*BlockItr = (uword) BlockToBeFreed;
VirtualFree( SupBlockFreedFrom, 0, MEM_DECOMMIT | MEM_RELEASE );
/* Finally, we must choose another value for gLastBlockUsed,
* since we just deallocated the memory it pointed to. We
* simply play it safe and point it at the only block we
* know to be in existance - the first one. */
gLastUsedBlock = gFirstSuperBlock + 1;
}
}
return;
}
export
void*
MemAlloc
( uword Size )
{
void *Mem;
MutexLock( &gMemMutex );
Mem = _Alloc( Size );
MutexUnLock( &gMemMutex );
return Mem;
}
export
void*
MemReAlloc
( void *OldMemory, uword NewSize )
{
void *NewMemory;
uword OldSize;
MutexLock( &gMemMutex );
do
{
if
( NULL == OldMemory )
{
/* If OldMemory is NULL, then the user is simply requesting
* that NewSize bytes be allocated. */
NewMemory = _Alloc( NewSize );
break;
}
else if ( NewSize == 0 )
{
/* If NewSize is zero, then the user is requesting that
* OldMemory be freed. */
_Free( OldMemory );
break;
}
else
{
/* Otherwise the user is requesting that the memory block
* pointed to by OldMemory be either increased or decreased
* to NewSize bytes. */
OldSize = ((*(((uword*) OldMemory) - 1) >> 2) + 1) << 2;
if
( NewSize > OldSize )
{
NewMemory = _Alloc( NewSize );
if ( NewMemory == NULL )
break;
MemCopy( NewMemory, OldMemory, OldSize );
MemFree( OldMemory );
break;
}
}
}
while ( 0 );
MutexUnLock( &gMemMutex );
return NewMemory;
}
export
void
MemFree
( void *Ptr )
{
MutexLock( &gMemMutex );
_Free( Ptr );
MutexUnLock( &gMemMutex );
return;
}
public
word
_MemInitialize
( void )
{
SYSTEM_INFO SystInfo;
MutexCreate( &gMemMutex );
GetSystemInfo( &SystInfo );
gPageSize = SystInfo.dwPageSize;
if ( gPageSize <= 0 )
return -1; /* FIXME: need error code */
gFirstSuperBlock = VirtualAlloc( NULL, gPageSize,
MEM_COMMIT | MEM_RESERVE,
PAGE_READWRITE );
if ( gFirstSuperBlock == NULL )
return -1; /* FIXME: need error code */
gLastUsedBlock = gFirstSuperBlock + 1;
gEndOfLastSuperBlock = (uword*)(((byte*) gFirstSuperBlock) +
gPageSize - sizeof(uword));
*gFirstSuperBlock = (uword) gFirstSuperBlock;
*gEndOfLastSuperBlock = (uword) gFirstSuperBlock;
*gLastUsedBlock = (gPageSize - sizeof(uword) * 2) | 0x2;
return 0;
}
public
void
_MemShutdown
( void )
{
/* No heap cleanup routines provided, as they are usually not
* needed (the operating system deallocates all memory when
* the application exits). This would, however, be a good
* place to call routines that browse the heap and print
* memory information to a log file, as any allocated
* memory present when this function is called may safely
* be considered a memory leak. */
MutexDestroy( &gMemMutex );
return;
}
/***********************************************************************
* The End
**********************************************************************/
|
