/* vmem.h
*
* (c) 1999 Microsoft Corporation. All rights reserved.
* Portions (c) 1999 ActiveState Tool Corp, http://www.ActiveState.com/
*
* You may distribute under the terms of either the GNU General Public
* License or the Artistic License, as specified in the README file.
*
* Options:
*
* Defining _USE_MSVCRT_MEM_ALLOC will cause all memory allocations
* to be forwarded to MSVCRT.DLL. Defining _USE_LINKED_LIST as well will
* track all allocations in a doubly linked list, so that the host can
* free all memory allocated when it goes away.
* If _USE_MSVCRT_MEM_ALLOC is not defined then Knuth's boundary tag algorithm
* is used; defining _USE_BUDDY_BLOCKS will use Knuth's algorithm R
* (Buddy system reservation)
*
*/
#ifndef ___VMEM_H_INC___
#define ___VMEM_H_INC___
#define _USE_MSVCRT_MEM_ALLOC
#define _USE_LINKED_LIST
// #define _USE_BUDDY_BLOCKS
// #define _DEBUG_MEM
#ifdef _DEBUG_MEM
#define ASSERT(f) if(!(f)) DebugBreak();
inline void MEMODS(char *str)
{
OutputDebugString(str);
OutputDebugString("\n");
}
inline void MEMODSlx(char *str, long x)
{
char szBuffer[512];
sprintf(szBuffer, "%s %lx\n", str, x);
OutputDebugString(szBuffer);
}
#define WALKHEAP() WalkHeap(0)
#define WALKHEAPTRACE() WalkHeap(1)
#else
#define ASSERT(f)
#define MEMODS(x)
#define MEMODSlx(x, y)
#define WALKHEAP()
#define WALKHEAPTRACE()
#endif
#ifdef _USE_MSVCRT_MEM_ALLOC
#ifndef _USE_LINKED_LIST
// #define _USE_LINKED_LIST
#endif
/*
* Pass all memory requests throught to msvcrt.dll
* optionaly track by using a doubly linked header
*/
typedef void (*LPFREE)(void *block);
typedef void* (*LPMALLOC)(size_t size);
typedef void* (*LPREALLOC)(void *block, size_t size);
#ifdef _USE_LINKED_LIST
class VMem;
typedef struct _MemoryBlockHeader* PMEMORY_BLOCK_HEADER;
typedef struct _MemoryBlockHeader {
PMEMORY_BLOCK_HEADER pNext;
PMEMORY_BLOCK_HEADER pPrev;
VMem *owner;
} MEMORY_BLOCK_HEADER, *PMEMORY_BLOCK_HEADER;
#endif
class VMem
{
public:
VMem();
~VMem();
virtual void* Malloc(size_t size);
virtual void* Realloc(void* pMem, size_t size);
virtual void Free(void* pMem);
virtual void GetLock(void);
virtual void FreeLock(void);
virtual int IsLocked(void);
virtual long Release(void);
virtual long AddRef(void);
inline BOOL CreateOk(void)
{
return TRUE;
};
protected:
#ifdef _USE_LINKED_LIST
void LinkBlock(PMEMORY_BLOCK_HEADER ptr)
{
PMEMORY_BLOCK_HEADER next = m_Dummy.pNext;
m_Dummy.pNext = ptr;
ptr->pPrev = &m_Dummy;
ptr->pNext = next;
ptr->owner = this;
next->pPrev = ptr;
}
void UnlinkBlock(PMEMORY_BLOCK_HEADER ptr)
{
PMEMORY_BLOCK_HEADER next = ptr->pNext;
PMEMORY_BLOCK_HEADER prev = ptr->pPrev;
prev->pNext = next;
next->pPrev = prev;
}
MEMORY_BLOCK_HEADER m_Dummy;
#endif
long m_lRefCount; // number of current users
CRITICAL_SECTION m_cs; // access lock
HINSTANCE m_hLib;
LPFREE m_pfree;
LPMALLOC m_pmalloc;
LPREALLOC m_prealloc;
};
VMem::VMem()
{
m_lRefCount = 1;
InitializeCriticalSection(&m_cs);
#ifdef _USE_LINKED_LIST
m_Dummy.pNext = m_Dummy.pPrev = &m_Dummy;
m_Dummy.owner = this;
#endif
m_hLib = LoadLibrary("msvcrt.dll");
if (m_hLib) {
m_pfree = (LPFREE)GetProcAddress(m_hLib, "free");
m_pmalloc = (LPMALLOC)GetProcAddress(m_hLib, "malloc");
m_prealloc = (LPREALLOC)GetProcAddress(m_hLib, "realloc");
}
}
VMem::~VMem(void)
{
#ifdef _USE_LINKED_LIST
while (m_Dummy.pNext != &m_Dummy) {
Free(m_Dummy.pNext+1);
}
#endif
if (m_hLib)
FreeLibrary(m_hLib);
DeleteCriticalSection(&m_cs);
}
void* VMem::Malloc(size_t size)
{
#ifdef _USE_LINKED_LIST
GetLock();
PMEMORY_BLOCK_HEADER ptr = (PMEMORY_BLOCK_HEADER)m_pmalloc(size+sizeof(MEMORY_BLOCK_HEADER));
LinkBlock(ptr);
FreeLock();
return (ptr+1);
#else
return m_pmalloc(size);
#endif
}
void* VMem::Realloc(void* pMem, size_t size)
{
#ifdef _USE_LINKED_LIST
if (!pMem)
return Malloc(size);
if (!size) {
Free(pMem);
return NULL;
}
GetLock();
PMEMORY_BLOCK_HEADER ptr = (PMEMORY_BLOCK_HEADER)(((char*)pMem)-sizeof(MEMORY_BLOCK_HEADER));
UnlinkBlock(ptr);
ptr = (PMEMORY_BLOCK_HEADER)m_prealloc(ptr, size+sizeof(MEMORY_BLOCK_HEADER));
LinkBlock(ptr);
FreeLock();
return (ptr+1);
#else
return m_prealloc(pMem, size);
#endif
}
void VMem::Free(void* pMem)
{
#ifdef _USE_LINKED_LIST
if (pMem) {
PMEMORY_BLOCK_HEADER ptr = (PMEMORY_BLOCK_HEADER)(((char*)pMem)-sizeof(MEMORY_BLOCK_HEADER));
if (ptr->owner != this) {
if (ptr->owner) {
#if 1
dTHX;
int *nowhere = NULL;
Perl_warn(aTHX_ "Free to wrong pool %p not %p",this,ptr->owner);
*nowhere = 0;
#else
ptr->owner->Free(pMem);
#endif
}
return;
}
GetLock();
UnlinkBlock(ptr);
ptr->owner = NULL;
m_pfree(ptr);
FreeLock();
}
#else
m_pfree(pMem);
#endif
}
void VMem::GetLock(void)
{
EnterCriticalSection(&m_cs);
}
void VMem::FreeLock(void)
{
LeaveCriticalSection(&m_cs);
}
int VMem::IsLocked(void)
{
#if 0
/* XXX TryEnterCriticalSection() is not available in some versions
* of Windows 95. Since this code is not used anywhere yet, we
* skirt the issue for now. */
BOOL bAccessed = TryEnterCriticalSection(&m_cs);
if(bAccessed) {
LeaveCriticalSection(&m_cs);
}
return !bAccessed;
#else
ASSERT(0); /* alarm bells for when somebody calls this */
return 0;
#endif
}
long VMem::Release(void)
{
long lCount = InterlockedDecrement(&m_lRefCount);
if(!lCount)
delete this;
return lCount;
}
long VMem::AddRef(void)
{
long lCount = InterlockedIncrement(&m_lRefCount);
return lCount;
}
#else /* _USE_MSVCRT_MEM_ALLOC */
/*
* Knuth's boundary tag algorithm Vol #1, Page 440.
*
* Each block in the heap has tag words before and after it,
* TAG
* block
* TAG
* The size is stored in these tags as a long word, and includes the 8 bytes
* of overhead that the boundary tags consume. Blocks are allocated on long
* word boundaries, so the size is always multiples of long words. When the
* block is allocated, bit 0, (the tag bit), of the size is set to 1. When
* a block is freed, it is merged with adjacent free blocks, and the tag bit
* is set to 0.
*
* A linked list is used to manage the free list. The first two long words of
* the block contain double links. These links are only valid when the block
* is freed, therefore space needs to be reserved for them. Thus, the minimum
* block size (not counting the tags) is 8 bytes.
*
* Since memory allocation may occur on a single threaded, explict locks are not
* provided.
*
*/
const long lAllocStart = 0x00020000; /* start at 128K */
const long minBlockSize = sizeof(void*)*2;
const long sizeofTag = sizeof(long);
const long blockOverhead = sizeofTag*2;
const long minAllocSize = minBlockSize+blockOverhead;
#ifdef _USE_BUDDY_BLOCKS
const long lSmallBlockSize = 1024;
const size_t nListEntries = ((lSmallBlockSize-minAllocSize)/sizeof(long));
inline size_t CalcEntry(size_t size)
{
ASSERT((size&(sizeof(long)-1)) == 0);
return ((size - minAllocSize) / sizeof(long));
}
#endif
typedef BYTE* PBLOCK; /* pointer to a memory block */
/*
* Macros for accessing hidden fields in a memory block:
*
* SIZE size of this block (tag bit 0 is 1 if block is allocated)
* PSIZE size of previous physical block
*/
#define SIZE(block) (*(ULONG*)(((PBLOCK)(block))-sizeofTag))
#define PSIZE(block) (*(ULONG*)(((PBLOCK)(block))-(blockOverhead)))
inline void SetTags(PBLOCK block, long size)
{
SIZE(block) = size;
PSIZE(block+(size&~1)) = size;
}
/*
* Free list pointers
* PREV pointer to previous block
* NEXT pointer to next block
*/
#define PREV(block) (*(PBLOCK*)(block))
#define NEXT(block) (*(PBLOCK*)((block)+sizeof(PBLOCK)))
inline void SetLink(PBLOCK block, PBLOCK prev, PBLOCK next)
{
PREV(block) = prev;
NEXT(block) = next;
}
inline void Unlink(PBLOCK p)
{
PBLOCK next = NEXT(p);
PBLOCK prev = PREV(p);
NEXT(prev) = next;
PREV(next) = prev;
}
#ifndef _USE_BUDDY_BLOCKS
inline void AddToFreeList(PBLOCK block, PBLOCK pInList)
{
PBLOCK next = NEXT(pInList);
NEXT(pInList) = block;
SetLink(block, pInList, next);
PREV(next) = block;
}
#endif
/* Macro for rounding up to the next sizeof(long) */
#define ROUND_UP(n) (((ULONG)(n)+sizeof(long)-1)&~(sizeof(long)-1))
#define ROUND_UP64K(n) (((ULONG)(n)+0x10000-1)&~(0x10000-1))
#define ROUND_DOWN(n) ((ULONG)(n)&~(sizeof(long)-1))
/*
* HeapRec - a list of all non-contiguous heap areas
*
* Each record in this array contains information about a non-contiguous heap area.
*/
const int maxHeaps = 32; /* 64 was overkill */
const long lAllocMax = 0x80000000; /* max size of allocation */
#ifdef _USE_BUDDY_BLOCKS
typedef struct _FreeListEntry
{
BYTE Dummy[minAllocSize]; // dummy free block
} FREE_LIST_ENTRY, *PFREE_LIST_ENTRY;
#endif
#ifndef _USE_BUDDY_BLOCKS
#define USE_BIGBLOCK_ALLOC
#endif
/*
* performance tuning
* Use VirtualAlloc() for blocks bigger than nMaxHeapAllocSize since
* Windows 95/98/Me have heap managers that are designed for memory
* blocks smaller than four megabytes.
*/
#ifdef USE_BIGBLOCK_ALLOC
const int nMaxHeapAllocSize = (1024*512); /* don't allocate anything larger than this from the heap */
#endif
typedef struct _HeapRec
{
PBLOCK base; /* base of heap area */
ULONG len; /* size of heap area */
#ifdef USE_BIGBLOCK_ALLOC
BOOL bBigBlock; /* was allocate using VirtualAlloc */
#endif
} HeapRec;
class VMem
{
public:
VMem();
~VMem();
virtual void* Malloc(size_t size);
virtual void* Realloc(void* pMem, size_t size);
virtual void Free(void* pMem);
virtual void GetLock(void);
virtual void FreeLock(void);
virtual int IsLocked(void);
virtual long Release(void);
virtual long AddRef(void);
inline BOOL CreateOk(void)
{
#ifdef _USE_BUDDY_BLOCKS
return TRUE;
#else
return m_hHeap != NULL;
#endif
};
void ReInit(void);
protected:
void Init(void);
int Getmem(size_t size);
int HeapAdd(void* ptr, size_t size
#ifdef USE_BIGBLOCK_ALLOC
, BOOL bBigBlock
#endif
);
void* Expand(void* block, size_t size);
#ifdef _USE_BUDDY_BLOCKS
inline PBLOCK GetFreeListLink(int index)
{
if (index >= nListEntries)
index = nListEntries-1;
return &m_FreeList[index].Dummy[sizeofTag];
}
inline PBLOCK GetOverSizeFreeList(void)
{
return &m_FreeList[nListEntries-1].Dummy[sizeofTag];
}
inline PBLOCK GetEOLFreeList(void)
{
return &m_FreeList[nListEntries].Dummy[sizeofTag];
}
void AddToFreeList(PBLOCK block, size_t size)
{
PBLOCK pFreeList = GetFreeListLink(CalcEntry(size));
PBLOCK next = NEXT(pFreeList);
NEXT(pFreeList) = block;
SetLink(block, pFreeList, next);
PREV(next) = block;
}
#endif
inline size_t CalcAllocSize(size_t size)
{
/*
* Adjust the real size of the block to be a multiple of sizeof(long), and add
* the overhead for the boundary tags. Disallow negative or zero sizes.
*/
return (size < minBlockSize) ? minAllocSize : (size_t)ROUND_UP(size) + blockOverhead;
}
#ifdef _USE_BUDDY_BLOCKS
FREE_LIST_ENTRY m_FreeList[nListEntries+1]; // free list with dummy end of list entry as well
#else
HANDLE m_hHeap; // memory heap for this script
char m_FreeDummy[minAllocSize]; // dummy free block
PBLOCK m_pFreeList; // pointer to first block on free list
#endif
PBLOCK m_pRover; // roving pointer into the free list
HeapRec m_heaps[maxHeaps]; // list of all non-contiguous heap areas
int m_nHeaps; // no. of heaps in m_heaps
long m_lAllocSize; // current alloc size
long m_lRefCount; // number of current users
CRITICAL_SECTION m_cs; // access lock
#ifdef _DEBUG_MEM
void WalkHeap(int complete);
void MemoryUsageMessage(char *str, long x, long y, int c);
FILE* m_pLog;
#endif
};
VMem::VMem()
{
m_lRefCount = 1;
#ifndef _USE_BUDDY_BLOCKS
BOOL bRet = (NULL != (m_hHeap = HeapCreate(HEAP_NO_SERIALIZE,
lAllocStart, /* initial size of heap */
0))); /* no upper limit on size of heap */
ASSERT(bRet);
#endif
InitializeCriticalSection(&m_cs);
#ifdef _DEBUG_MEM
m_pLog = 0;
#endif
Init();
}
VMem::~VMem(void)
{
#ifndef _USE_BUDDY_BLOCKS
ASSERT(HeapValidate(m_hHeap, HEAP_NO_SERIALIZE, NULL));
#endif
WALKHEAPTRACE();
DeleteCriticalSection(&m_cs);
#ifdef _USE_BUDDY_BLOCKS
for(int index = 0; index < m_nHeaps; ++index) {
VirtualFree(m_heaps[index].base, 0, MEM_RELEASE);
}
#else /* !_USE_BUDDY_BLOCKS */
#ifdef USE_BIGBLOCK_ALLOC
for(int index = 0; index < m_nHeaps; ++index) {
if (m_heaps[index].bBigBlock) {
VirtualFree(m_heaps[index].base, 0, MEM_RELEASE);
}
}
#endif
BOOL bRet = HeapDestroy(m_hHeap);
ASSERT(bRet);
#endif /* _USE_BUDDY_BLOCKS */
}
void VMem::ReInit(void)
{
for(int index = 0; index < m_nHeaps; ++index) {
#ifdef _USE_BUDDY_BLOCKS
VirtualFree(m_heaps[index].base, 0, MEM_RELEASE);
#else
#ifdef USE_BIGBLOCK_ALLOC
if (m_heaps[index].bBigBlock) {
VirtualFree(m_heaps[index].base, 0, MEM_RELEASE);
}
else
#endif
HeapFree(m_hHeap, HEAP_NO_SERIALIZE, m_heaps[index].base);
#endif /* _USE_BUDDY_BLOCKS */
}
Init();
}
void VMem::Init(void)
{
#ifdef _USE_BUDDY_BLOCKS
PBLOCK pFreeList;
/*
* Initialize the free list by placing a dummy zero-length block on it.
* Set the end of list marker.
* Set the number of non-contiguous heaps to zero.
* Set the next allocation size.
*/
for (int index = 0; index < nListEntries; ++index) {
pFreeList = GetFreeListLink(index);
SIZE(pFreeList) = PSIZE(pFreeList+minAllocSize) = 0;
PREV(pFreeList) = NEXT(pFreeList) = pFreeList;
}
pFreeList = GetEOLFreeList();
SIZE(pFreeList) = PSIZE(pFreeList+minAllocSize) = 0;
PREV(pFreeList) = NEXT(pFreeList) = NULL;
m_pRover = GetOverSizeFreeList();
#else
/*
* Initialize the free list by placing a dummy zero-length block on it.
* Set the number of non-contiguous heaps to zero.
*/
m_pFreeList = m_pRover = (PBLOCK)(&m_FreeDummy[sizeofTag]);
PSIZE(m_pFreeList+minAllocSize) = SIZE(m_pFreeList) = 0;
PREV(m_pFreeList) = NEXT(m_pFreeList) = m_pFreeList;
#endif
m_nHeaps = 0;
m_lAllocSize = lAllocStart;
}
void* VMem::Malloc(size_t size)
{
WALKHEAP();
PBLOCK ptr;
size_t lsize, rem;
/*
* Disallow negative or zero sizes.
*/
size_t realsize = CalcAllocSize(size);
if((int)realsize < minAllocSize || size == 0)
return NULL;
#ifdef _USE_BUDDY_BLOCKS
/*
* Check the free list of small blocks if this is free use it
* Otherwise check the rover if it has no blocks then
* Scan the free list entries use the first free block
* split the block if needed, stop at end of list marker
*/
{
int index = CalcEntry(realsize);
if (index < nListEntries-1) {
ptr = GetFreeListLink(index);
lsize = SIZE(ptr);
if (lsize >= realsize) {
rem = lsize - realsize;
if(rem < minAllocSize) {
/* Unlink the block from the free list. */
Unlink(ptr);
}
else {
/*
* split the block
* The remainder is big enough to split off into a new block.
* Use the end of the block, resize the beginning of the block
* no need to change the free list.
*/
SetTags(ptr, rem);
ptr += SIZE(ptr);
lsize = realsize;
}
SetTags(ptr, lsize | 1);
return ptr;
}
ptr = m_pRover;
lsize = SIZE(ptr);
if (lsize >= realsize) {
rem = lsize - realsize;
if(rem < minAllocSize) {
/* Unlink the block from the free list. */
Unlink(ptr);
}
else {
/*
* split the block
* The remainder is big enough to split off into a new block.
* Use the end of the block, resize the beginning of the block
* no need to change the free list.
*/
SetTags(ptr, rem);
ptr += SIZE(ptr);
lsize = realsize;
}
SetTags(ptr, lsize | 1);
return ptr;
}
ptr = GetFreeListLink(index+1);
while (NEXT(ptr)) {
lsize = SIZE(ptr);
if (lsize >= realsize) {
size_t rem = lsize - realsize;
if(rem < minAllocSize) {
/* Unlink the block from the free list. */
Unlink(ptr);
}
else {
/*
* split the block
* The remainder is big enough to split off into a new block.
* Use the end of the block, resize the beginning of the block
* no need to change the free list.
*/
SetTags(ptr, rem);
ptr += SIZE(ptr);
lsize = realsize;
}
SetTags(ptr, lsize | 1);
return ptr;
}
ptr += sizeof(FREE_LIST_ENTRY);
}
}
}
#endif
/*
* Start searching the free list at the rover. If we arrive back at rover without
* finding anything, allocate some memory from the heap and try again.
*/
ptr = m_pRover; /* start searching at rover */
int loops = 2; /* allow two times through the loop */
for(;;) {
lsize = SIZE(ptr);
ASSERT((lsize&1)==0);
/* is block big enough? */
if(lsize >= realsize) {
/* if the remainder is too small, don't bother splitting the block. */
rem = lsize - realsize;
if(rem < minAllocSize) {
if(m_pRover == ptr)
m_pRover = NEXT(ptr);
/* Unlink the block from the free list. */
Unlink(ptr);
}
else {
/*
* split the block
* The remainder is big enough to split off into a new block.
* Use the end of the block, resize the beginning of the block
* no need to change the free list.
*/
SetTags(ptr, rem);
ptr += SIZE(ptr);
lsize = realsize;
}
/* Set the boundary tags to mark it as allocated. */
SetTags(ptr, lsize | 1);
return ((void *)ptr);
}
/*
* This block was unsuitable. If we've gone through this list once already without
* finding anything, allocate some new memory from the heap and try again.
*/
ptr = NEXT(ptr);
if(ptr == m_pRover) {
if(!(loops-- && Getmem(realsize))) {
return NULL;
}
ptr = m_pRover;
}
}
}
void* VMem::Realloc(void* block, size_t size)
{
WALKHEAP();
/* if size is zero, free the block. */
if(size == 0) {
Free(block);
return (NULL);
}
/* if block pointer is NULL, do a Malloc(). */
if(block == NULL)
return Malloc(size);
/*
* Grow or shrink the block in place.
* if the block grows then the next block will be used if free
*/
if(Expand(block, size) != NULL)
return block;
size_t realsize = CalcAllocSize(size);
if((int)realsize < minAllocSize)
return NULL;
/*
* see if the previous block is free, and is it big enough to cover the new size
* if merged with the current block.
*/
PBLOCK ptr = (PBLOCK)block;
size_t cursize = SIZE(ptr) & ~1;
size_t psize = PSIZE(ptr);
if((psize&1) == 0 && (psize + cursize) >= realsize) {
PBLOCK prev = ptr - psize;
if(m_pRover == prev)
m_pRover = NEXT(prev);
/* Unlink the next block from the free list. */
Unlink(prev);
/* Copy contents of old block to new location, make it the current block. */
memmove(prev, ptr, cursize);
cursize += psize; /* combine sizes */
ptr = prev;
size_t rem = cursize - realsize;
if(rem >= minAllocSize) {
/*
* The remainder is big enough to be a new block. Set boundary
* tags for the resized block and the new block.
*/
prev = ptr + realsize;
/*
* add the new block to the free list.
* next block cannot be free
*/
SetTags(prev, rem);
#ifdef _USE_BUDDY_BLOCKS
AddToFreeList(prev, rem);
#else
AddToFreeList(prev, m_pFreeList);
#endif
cursize = realsize;
}
/* Set the boundary tags to mark it as allocated. */
SetTags(ptr, cursize | 1);
return ((void *)ptr);
}
/* Allocate a new block, copy the old to the new, and free the old. */
if((ptr = (PBLOCK)Malloc(size)) != NULL) {
memmove(ptr, block, cursize-blockOverhead);
Free(block);
}
return ((void *)ptr);
}
void VMem::Free(void* p)
{
WALKHEAP();
/* Ignore null pointer. */
if(p == NULL)
return;
PBLOCK ptr = (PBLOCK)p;
/* Check for attempt to free a block that's already free. */
size_t size = SIZE(ptr);
if((size&1) == 0) {
MEMODSlx("Attempt to free previously freed block", (long)p);
return;
}
size &= ~1; /* remove allocated tag */
/* if previous block is free, add this block to it. */
#ifndef _USE_BUDDY_BLOCKS
int linked = FALSE;
#endif
size_t psize = PSIZE(ptr);
if((psize&1) == 0) {
ptr -= psize; /* point to previous block */
size += psize; /* merge the sizes of the two blocks */
#ifdef _USE_BUDDY_BLOCKS
Unlink(ptr);
#else
linked = TRUE; /* it's already on the free list */
#endif
}
/* if the next physical block is free, merge it with this block. */
PBLOCK next = ptr + size; /* point to next physical block */
size_t nsize = SIZE(next);
if((nsize&1) == 0) {
/* block is free move rover if needed */
if(m_pRover == next)
m_pRover = NEXT(next);
/* unlink the next block from the free list. */
Unlink(next);
/* merge the sizes of this block and the next block. */
size += nsize;
}
/* Set the boundary tags for the block; */
SetTags(ptr, size);
/* Link the block to the head of the free list. */
#ifdef _USE_BUDDY_BLOCKS
AddToFreeList(ptr, size);
#else
if(!linked) {
AddToFreeList(ptr, m_pFreeList);
}
#endif
}
void VMem::GetLock(void)
{
EnterCriticalSection(&m_cs);
}
void VMem::FreeLock(void)
{
LeaveCriticalSection(&m_cs);
}
int VMem::IsLocked(void)
{
#if 0
/* XXX TryEnterCriticalSection() is not available in some versions
* of Windows 95. Since this code is not used anywhere yet, we
* skirt the issue for now. */
BOOL bAccessed = TryEnterCriticalSection(&m_cs);
if(bAccessed) {
LeaveCriticalSection(&m_cs);
}
return !bAccessed;
#else
ASSERT(0); /* alarm bells for when somebody calls this */
return 0;
#endif
}
long VMem::Release(void)
{
long lCount = InterlockedDecrement(&m_lRefCount);
if(!lCount)
delete this;
return lCount;
}
long VMem::AddRef(void)
{
long lCount = InterlockedIncrement(&m_lRefCount);
return lCount;
}
int VMem::Getmem(size_t requestSize)
{ /* returns -1 is successful 0 if not */
#ifdef USE_BIGBLOCK_ALLOC
BOOL bBigBlock;
#endif
void *ptr;
/* Round up size to next multiple of 64K. */
size_t size = (size_t)ROUND_UP64K(requestSize);
/*
* if the size requested is smaller than our current allocation size
* adjust up
*/
if(size < (unsigned long)m_lAllocSize)
size = m_lAllocSize;
/* Update the size to allocate on the next request */
if(m_lAllocSize != lAllocMax)
m_lAllocSize <<= 2;
#ifndef _USE_BUDDY_BLOCKS
if(m_nHeaps != 0
#ifdef USE_BIGBLOCK_ALLOC
&& !m_heaps[m_nHeaps-1].bBigBlock
#endif
) {
/* Expand the last allocated heap */
ptr = HeapReAlloc(m_hHeap, HEAP_REALLOC_IN_PLACE_ONLY|HEAP_NO_SERIALIZE,
m_heaps[m_nHeaps-1].base,
m_heaps[m_nHeaps-1].len + size);
if(ptr != 0) {
HeapAdd(((char*)ptr) + m_heaps[m_nHeaps-1].len, size
#ifdef USE_BIGBLOCK_ALLOC
, FALSE
#endif
);
return -1;
}
}
#endif /* _USE_BUDDY_BLOCKS */
/*
* if we didn't expand a block to cover the requested size
* allocate a new Heap
* the size of this block must include the additional dummy tags at either end
* the above ROUND_UP64K may not have added any memory to include this.
*/
if(size == requestSize)
size = (size_t)ROUND_UP64K(requestSize+(blockOverhead));
Restart:
#ifdef _USE_BUDDY_BLOCKS
ptr = VirtualAlloc(NULL, size, MEM_COMMIT, PAGE_READWRITE);
#else
#ifdef USE_BIGBLOCK_ALLOC
bBigBlock = FALSE;
if (size >= nMaxHeapAllocSize) {
bBigBlock = TRUE;
ptr = VirtualAlloc(NULL, size, MEM_COMMIT, PAGE_READWRITE);
}
else
#endif
ptr = HeapAlloc(m_hHeap, HEAP_NO_SERIALIZE, size);
#endif /* _USE_BUDDY_BLOCKS */
if (!ptr) {
/* try to allocate a smaller chunk */
size >>= 1;
if(size > requestSize)
goto Restart;
}
if(ptr == 0) {
MEMODSlx("HeapAlloc failed on size!!!", size);
return 0;
}
#ifdef _USE_BUDDY_BLOCKS
if (HeapAdd(ptr, size)) {
VirtualFree(ptr, 0, MEM_RELEASE);
return 0;
}
#else
#ifdef USE_BIGBLOCK_ALLOC
if (HeapAdd(ptr, size, bBigBlock)) {
if (bBigBlock) {
VirtualFree(ptr, 0, MEM_RELEASE);
}
}
#else
HeapAdd(ptr, size);
#endif
#endif /* _USE_BUDDY_BLOCKS */
return -1;
}
int VMem::HeapAdd(void* p, size_t size
#ifdef USE_BIGBLOCK_ALLOC
, BOOL bBigBlock
#endif
)
{ /* if the block can be succesfully added to the heap, returns 0; otherwise -1. */
int index;
/* Check size, then round size down to next long word boundary. */
if(size < minAllocSize)
return -1;
size = (size_t)ROUND_DOWN(size);
PBLOCK ptr = (PBLOCK)p;
#ifdef USE_BIGBLOCK_ALLOC
if (!bBigBlock) {
#endif
/*
* Search for another heap area that's contiguous with the bottom of this new area.
* (It should be extremely unusual to find one that's contiguous with the top).
*/
for(index = 0; index < m_nHeaps; ++index) {
if(ptr == m_heaps[index].base + (int)m_heaps[index].len) {
/*
* The new block is contiguous with a previously allocated heap area. Add its
* length to that of the previous heap. Merge it with the the dummy end-of-heap
* area marker of the previous heap.
*/
m_heaps[index].len += size;
break;
}
}
#ifdef USE_BIGBLOCK_ALLOC
}
else {
index = m_nHeaps;
}
#endif
if(index == m_nHeaps) {
/* The new block is not contiguous, or is BigBlock. Add it to the heap list. */
if(m_nHeaps == maxHeaps) {
return -1; /* too many non-contiguous heaps */
}
m_heaps[m_nHeaps].base = ptr;
m_heaps[m_nHeaps].len = size;
#ifdef USE_BIGBLOCK_ALLOC
m_heaps[m_nHeaps].bBigBlock = bBigBlock;
#endif
m_nHeaps++;
/*
* Reserve the first LONG in the block for the ending boundary tag of a dummy
* block at the start of the heap area.
*/
size -= blockOverhead;
ptr += blockOverhead;
PSIZE(ptr) = 1; /* mark the dummy previous block as allocated */
}
/*
* Convert the heap to one large block. Set up its boundary tags, and those of
* marker block after it. The marker block before the heap will already have
* been set up if this heap is not contiguous with the end of another heap.
*/
SetTags(ptr, size | 1);
PBLOCK next = ptr + size; /* point to dummy end block */
SIZE(next) = 1; /* mark the dummy end block as allocated */
/*
* Link the block to the start of the free list by calling free().
* This will merge the block with any adjacent free blocks.
*/
Free(ptr);
return 0;
}
void* VMem::Expand(void* block, size_t size)
{
/*
* Disallow negative or zero sizes.
*/
size_t realsize = CalcAllocSize(size);
if((int)realsize < minAllocSize || size == 0)
return NULL;
PBLOCK ptr = (PBLOCK)block;
/* if the current size is the same as requested, do nothing. */
size_t cursize = SIZE(ptr) & ~1;
if(cursize == realsize) {
return block;
}
/* if the block is being shrunk, convert the remainder of the block into a new free block. */
if(realsize <= cursize) {
size_t nextsize = cursize - realsize; /* size of new remainder block */
if(nextsize >= minAllocSize) {
/*
* Split the block
* Set boundary tags for the resized block and the new block.
*/
SetTags(ptr, realsize | 1);
ptr += realsize;
/*
* add the new block to the free list.
* call Free to merge this block with next block if free
*/
SetTags(ptr, nextsize | 1);
Free(ptr);
}
return block;
}
PBLOCK next = ptr + cursize;
size_t nextsize = SIZE(next);
/* Check the next block for consistency.*/
if((nextsize&1) == 0 && (nextsize + cursize) >= realsize) {
/*
* The next block is free and big enough. Add the part that's needed
* to our block, and split the remainder off into a new block.
*/
if(m_pRover == next)
m_pRover = NEXT(next);
/* Unlink the next block from the free list. */
Unlink(next);
cursize += nextsize; /* combine sizes */
size_t rem = cursize - realsize; /* size of remainder */
if(rem >= minAllocSize) {
/*
* The remainder is big enough to be a new block.
* Set boundary tags for the resized block and the new block.
*/
next = ptr + realsize;
/*
* add the new block to the free list.
* next block cannot be free
*/
SetTags(next, rem);
#ifdef _USE_BUDDY_BLOCKS
AddToFreeList(next, rem);
#else
AddToFreeList(next, m_pFreeList);
#endif
cursize = realsize;
}
/* Set the boundary tags to mark it as allocated. */
SetTags(ptr, cursize | 1);
return ((void *)ptr);
}
return NULL;
}
#ifdef _DEBUG_MEM
#define LOG_FILENAME ".\\MemLog.txt"
void VMem::MemoryUsageMessage(char *str, long x, long y, int c)
{
char szBuffer[512];
if(str) {
if(!m_pLog)
m_pLog = fopen(LOG_FILENAME, "w");
sprintf(szBuffer, str, x, y, c);
fputs(szBuffer, m_pLog);
}
else {
if(m_pLog) {
fflush(m_pLog);
fclose(m_pLog);
m_pLog = 0;
}
}
}
void VMem::WalkHeap(int complete)
{
if(complete) {
MemoryUsageMessage(NULL, 0, 0, 0);
size_t total = 0;
for(int i = 0; i < m_nHeaps; ++i) {
total += m_heaps[i].len;
}
MemoryUsageMessage("VMem heaps used %d. Total memory %08x\n", m_nHeaps, total, 0);
/* Walk all the heaps - verify structures */
for(int index = 0; index < m_nHeaps; ++index) {
PBLOCK ptr = m_heaps[index].base;
size_t size = m_heaps[index].len;
#ifndef _USE_BUDDY_BLOCKS
#ifdef USE_BIGBLOCK_ALLOC
if (!m_heaps[m_nHeaps].bBigBlock)
#endif
ASSERT(HeapValidate(m_hHeap, HEAP_NO_SERIALIZE, ptr));
#endif
/* set over reserved header block */
size -= blockOverhead;
ptr += blockOverhead;
PBLOCK pLast = ptr + size;
ASSERT(PSIZE(ptr) == 1); /* dummy previous block is allocated */
ASSERT(SIZE(pLast) == 1); /* dummy next block is allocated */
while(ptr < pLast) {
ASSERT(ptr > m_heaps[index].base);
size_t cursize = SIZE(ptr) & ~1;
ASSERT((PSIZE(ptr+cursize) & ~1) == cursize);
MemoryUsageMessage("Memory Block %08x: Size %08x %c\n", (long)ptr, cursize, (SIZE(ptr)&1) ? 'x' : ' ');
if(!(SIZE(ptr)&1)) {
/* this block is on the free list */
PBLOCK tmp = NEXT(ptr);
while(tmp != ptr) {
ASSERT((SIZE(tmp)&1)==0);
if(tmp == m_pFreeList)
break;
ASSERT(NEXT(tmp));
tmp = NEXT(tmp);
}
if(tmp == ptr) {
MemoryUsageMessage("Memory Block %08x: Size %08x free but not in free list\n", (long)ptr, cursize, 0);
}
}
ptr += cursize;
}
}
MemoryUsageMessage(NULL, 0, 0, 0);
}
}
#endif /* _DEBUG_MEM */
#endif /* _USE_MSVCRT_MEM_ALLOC */
#endif /* ___VMEM_H_INC___ */
|
