3 * (c) 1999 Microsoft Corporation. All rights reserved.
4 * Portions (c) 1999 ActiveState Tool Corp, http://www.ActiveState.com/
6 * You may distribute under the terms of either the GNU General Public
7 * License or the Artistic License, as specified in the README file.
11 * Defining _USE_MSVCRT_MEM_ALLOC will cause all memory allocations
12 * to be forwarded to MSVCRT.DLL. Defining _USE_LINKED_LIST as well will
13 * track all allocations in a doubly linked list, so that the host can
14 * free all memory allocated when it goes away.
15 * If _USE_MSVCRT_MEM_ALLOC is not defined then Knuth's boundary tag algorithm
16 * is used; defining _USE_BUDDY_BLOCKS will use Knuth's algorithm R
17 * (Buddy system reservation)
21 #ifndef ___VMEM_H_INC___
22 #define ___VMEM_H_INC___
25 #define _USE_MSVCRT_MEM_ALLOC
27 #define _USE_LINKED_LIST
29 // #define _USE_BUDDY_BLOCKS
33 #define ASSERT(f) if(!(f)) DebugBreak();
35 inline void MEMODS(char *str)
37 OutputDebugString(str);
38 OutputDebugString("\n");
41 inline void MEMODSlx(char *str, long x)
44 sprintf(szBuffer, "%s %lx\n", str, x);
45 OutputDebugString(szBuffer);
48 #define WALKHEAP() WalkHeap(0)
49 #define WALKHEAPTRACE() WalkHeap(1)
55 #define MEMODSlx(x, y)
57 #define WALKHEAPTRACE()
61 #ifdef _USE_MSVCRT_MEM_ALLOC
63 #ifndef _USE_LINKED_LIST
64 // #define _USE_LINKED_LIST
68 * Pass all memory requests throught to msvcrt.dll
69 * optionaly track by using a doubly linked header
72 typedef void (*LPFREE)(void *block);
73 typedef void* (*LPMALLOC)(size_t size);
74 typedef void* (*LPREALLOC)(void *block, size_t size);
75 #ifdef _USE_LINKED_LIST
77 typedef struct _MemoryBlockHeader* PMEMORY_BLOCK_HEADER;
78 typedef struct _MemoryBlockHeader {
79 PMEMORY_BLOCK_HEADER pNext;
80 PMEMORY_BLOCK_HEADER pPrev;
82 } MEMORY_BLOCK_HEADER, *PMEMORY_BLOCK_HEADER;
90 virtual void* Malloc(size_t size);
91 virtual void* Realloc(void* pMem, size_t size);
92 virtual void Free(void* pMem);
93 virtual void GetLock(void);
94 virtual void FreeLock(void);
95 virtual int IsLocked(void);
96 virtual long Release(void);
97 virtual long AddRef(void);
99 inline BOOL CreateOk(void)
105 #ifdef _USE_LINKED_LIST
106 void LinkBlock(PMEMORY_BLOCK_HEADER ptr)
108 PMEMORY_BLOCK_HEADER next = m_Dummy.pNext;
110 ptr->pPrev = &m_Dummy;
115 void UnlinkBlock(PMEMORY_BLOCK_HEADER ptr)
117 PMEMORY_BLOCK_HEADER next = ptr->pNext;
118 PMEMORY_BLOCK_HEADER prev = ptr->pPrev;
123 MEMORY_BLOCK_HEADER m_Dummy;
126 long m_lRefCount; // number of current users
127 CRITICAL_SECTION m_cs; // access lock
131 LPREALLOC m_prealloc;
137 InitializeCriticalSection(&m_cs);
138 #ifdef _USE_LINKED_LIST
139 m_Dummy.pNext = m_Dummy.pPrev = &m_Dummy;
140 m_Dummy.owner = this;
142 m_hLib = LoadLibrary("msvcrt.dll");
144 m_pfree = (LPFREE)GetProcAddress(m_hLib, "free");
145 m_pmalloc = (LPMALLOC)GetProcAddress(m_hLib, "malloc");
146 m_prealloc = (LPREALLOC)GetProcAddress(m_hLib, "realloc");
152 #ifdef _USE_LINKED_LIST
153 while (m_Dummy.pNext != &m_Dummy) {
154 Free(m_Dummy.pNext+1);
159 DeleteCriticalSection(&m_cs);
162 void* VMem::Malloc(size_t size)
164 #ifdef _USE_LINKED_LIST
166 PMEMORY_BLOCK_HEADER ptr = (PMEMORY_BLOCK_HEADER)m_pmalloc(size+sizeof(MEMORY_BLOCK_HEADER));
171 return m_pmalloc(size);
175 void* VMem::Realloc(void* pMem, size_t size)
177 #ifdef _USE_LINKED_LIST
187 PMEMORY_BLOCK_HEADER ptr = (PMEMORY_BLOCK_HEADER)(((char*)pMem)-sizeof(MEMORY_BLOCK_HEADER));
189 ptr = (PMEMORY_BLOCK_HEADER)m_prealloc(ptr, size+sizeof(MEMORY_BLOCK_HEADER));
195 return m_prealloc(pMem, size);
199 void VMem::Free(void* pMem)
201 #ifdef _USE_LINKED_LIST
203 PMEMORY_BLOCK_HEADER ptr = (PMEMORY_BLOCK_HEADER)(((char*)pMem)-sizeof(MEMORY_BLOCK_HEADER));
204 if (ptr->owner != this) {
209 Perl_warn(aTHX_ "Free to wrong pool %p not %p",this,ptr->owner);
212 ptr->owner->Free(pMem);
228 void VMem::GetLock(void)
230 EnterCriticalSection(&m_cs);
233 void VMem::FreeLock(void)
235 LeaveCriticalSection(&m_cs);
238 int VMem::IsLocked(void)
241 /* XXX TryEnterCriticalSection() is not available in some versions
242 * of Windows 95. Since this code is not used anywhere yet, we
243 * skirt the issue for now. */
244 BOOL bAccessed = TryEnterCriticalSection(&m_cs);
246 LeaveCriticalSection(&m_cs);
250 ASSERT(0); /* alarm bells for when somebody calls this */
255 long VMem::Release(void)
257 long lCount = InterlockedDecrement(&m_lRefCount);
263 long VMem::AddRef(void)
265 long lCount = InterlockedIncrement(&m_lRefCount);
269 #else /* _USE_MSVCRT_MEM_ALLOC */
272 * Knuth's boundary tag algorithm Vol #1, Page 440.
274 * Each block in the heap has tag words before and after it,
278 * The size is stored in these tags as a long word, and includes the 8 bytes
279 * of overhead that the boundary tags consume. Blocks are allocated on long
280 * word boundaries, so the size is always multiples of long words. When the
281 * block is allocated, bit 0, (the tag bit), of the size is set to 1. When
282 * a block is freed, it is merged with adjacent free blocks, and the tag bit
285 * A linked list is used to manage the free list. The first two long words of
286 * the block contain double links. These links are only valid when the block
287 * is freed, therefore space needs to be reserved for them. Thus, the minimum
288 * block size (not counting the tags) is 8 bytes.
290 * Since memory allocation may occur on a single threaded, explict locks are not
295 const long lAllocStart = 0x00020000; /* start at 128K */
296 const long minBlockSize = sizeof(void*)*2;
297 const long sizeofTag = sizeof(long);
298 const long blockOverhead = sizeofTag*2;
299 const long minAllocSize = minBlockSize+blockOverhead;
300 #ifdef _USE_BUDDY_BLOCKS
301 const long lSmallBlockSize = 1024;
302 const size_t nListEntries = ((lSmallBlockSize-minAllocSize)/sizeof(long));
304 inline size_t CalcEntry(size_t size)
306 ASSERT((size&(sizeof(long)-1)) == 0);
307 return ((size - minAllocSize) / sizeof(long));
311 typedef BYTE* PBLOCK; /* pointer to a memory block */
314 * Macros for accessing hidden fields in a memory block:
316 * SIZE size of this block (tag bit 0 is 1 if block is allocated)
317 * PSIZE size of previous physical block
320 #define SIZE(block) (*(ULONG*)(((PBLOCK)(block))-sizeofTag))
321 #define PSIZE(block) (*(ULONG*)(((PBLOCK)(block))-(blockOverhead)))
322 inline void SetTags(PBLOCK block, long size)
325 PSIZE(block+(size&~1)) = size;
330 * PREV pointer to previous block
331 * NEXT pointer to next block
334 #define PREV(block) (*(PBLOCK*)(block))
335 #define NEXT(block) (*(PBLOCK*)((block)+sizeof(PBLOCK)))
336 inline void SetLink(PBLOCK block, PBLOCK prev, PBLOCK next)
341 inline void Unlink(PBLOCK p)
343 PBLOCK next = NEXT(p);
344 PBLOCK prev = PREV(p);
348 #ifndef _USE_BUDDY_BLOCKS
349 inline void AddToFreeList(PBLOCK block, PBLOCK pInList)
351 PBLOCK next = NEXT(pInList);
352 NEXT(pInList) = block;
353 SetLink(block, pInList, next);
358 /* Macro for rounding up to the next sizeof(long) */
359 #define ROUND_UP(n) (((ULONG)(n)+sizeof(long)-1)&~(sizeof(long)-1))
360 #define ROUND_UP64K(n) (((ULONG)(n)+0x10000-1)&~(0x10000-1))
361 #define ROUND_DOWN(n) ((ULONG)(n)&~(sizeof(long)-1))
364 * HeapRec - a list of all non-contiguous heap areas
366 * Each record in this array contains information about a non-contiguous heap area.
369 const int maxHeaps = 32; /* 64 was overkill */
370 const long lAllocMax = 0x80000000; /* max size of allocation */
372 #ifdef _USE_BUDDY_BLOCKS
373 typedef struct _FreeListEntry
375 BYTE Dummy[minAllocSize]; // dummy free block
376 } FREE_LIST_ENTRY, *PFREE_LIST_ENTRY;
379 #ifndef _USE_BUDDY_BLOCKS
380 #define USE_BIGBLOCK_ALLOC
384 * Use VirtualAlloc() for blocks bigger than nMaxHeapAllocSize since
385 * Windows 95/98/Me have heap managers that are designed for memory
386 * blocks smaller than four megabytes.
389 #ifdef USE_BIGBLOCK_ALLOC
390 const int nMaxHeapAllocSize = (1024*512); /* don't allocate anything larger than this from the heap */
393 typedef struct _HeapRec
395 PBLOCK base; /* base of heap area */
396 ULONG len; /* size of heap area */
397 #ifdef USE_BIGBLOCK_ALLOC
398 BOOL bBigBlock; /* was allocate using VirtualAlloc */
407 virtual void* Malloc(size_t size);
408 virtual void* Realloc(void* pMem, size_t size);
409 virtual void Free(void* pMem);
410 virtual void GetLock(void);
411 virtual void FreeLock(void);
412 virtual int IsLocked(void);
413 virtual long Release(void);
414 virtual long AddRef(void);
416 inline BOOL CreateOk(void)
418 #ifdef _USE_BUDDY_BLOCKS
421 return m_hHeap != NULL;
429 int Getmem(size_t size);
431 int HeapAdd(void* ptr, size_t size
432 #ifdef USE_BIGBLOCK_ALLOC
437 void* Expand(void* block, size_t size);
439 #ifdef _USE_BUDDY_BLOCKS
440 inline PBLOCK GetFreeListLink(int index)
442 if (index >= nListEntries)
443 index = nListEntries-1;
444 return &m_FreeList[index].Dummy[sizeofTag];
446 inline PBLOCK GetOverSizeFreeList(void)
448 return &m_FreeList[nListEntries-1].Dummy[sizeofTag];
450 inline PBLOCK GetEOLFreeList(void)
452 return &m_FreeList[nListEntries].Dummy[sizeofTag];
455 void AddToFreeList(PBLOCK block, size_t size)
457 PBLOCK pFreeList = GetFreeListLink(CalcEntry(size));
458 PBLOCK next = NEXT(pFreeList);
459 NEXT(pFreeList) = block;
460 SetLink(block, pFreeList, next);
464 inline size_t CalcAllocSize(size_t size)
467 * Adjust the real size of the block to be a multiple of sizeof(long), and add
468 * the overhead for the boundary tags. Disallow negative or zero sizes.
470 return (size < minBlockSize) ? minAllocSize : (size_t)ROUND_UP(size) + blockOverhead;
473 #ifdef _USE_BUDDY_BLOCKS
474 FREE_LIST_ENTRY m_FreeList[nListEntries+1]; // free list with dummy end of list entry as well
476 HANDLE m_hHeap; // memory heap for this script
477 char m_FreeDummy[minAllocSize]; // dummy free block
478 PBLOCK m_pFreeList; // pointer to first block on free list
480 PBLOCK m_pRover; // roving pointer into the free list
481 HeapRec m_heaps[maxHeaps]; // list of all non-contiguous heap areas
482 int m_nHeaps; // no. of heaps in m_heaps
483 long m_lAllocSize; // current alloc size
484 long m_lRefCount; // number of current users
485 CRITICAL_SECTION m_cs; // access lock
488 void WalkHeap(int complete);
489 void MemoryUsageMessage(char *str, long x, long y, int c);
497 #ifndef _USE_BUDDY_BLOCKS
498 BOOL bRet = (NULL != (m_hHeap = HeapCreate(HEAP_NO_SERIALIZE,
499 lAllocStart, /* initial size of heap */
500 0))); /* no upper limit on size of heap */
504 InitializeCriticalSection(&m_cs);
514 #ifndef _USE_BUDDY_BLOCKS
515 ASSERT(HeapValidate(m_hHeap, HEAP_NO_SERIALIZE, NULL));
519 DeleteCriticalSection(&m_cs);
520 #ifdef _USE_BUDDY_BLOCKS
521 for(int index = 0; index < m_nHeaps; ++index) {
522 VirtualFree(m_heaps[index].base, 0, MEM_RELEASE);
524 #else /* !_USE_BUDDY_BLOCKS */
525 #ifdef USE_BIGBLOCK_ALLOC
526 for(int index = 0; index < m_nHeaps; ++index) {
527 if (m_heaps[index].bBigBlock) {
528 VirtualFree(m_heaps[index].base, 0, MEM_RELEASE);
532 BOOL bRet = HeapDestroy(m_hHeap);
534 #endif /* _USE_BUDDY_BLOCKS */
537 void VMem::ReInit(void)
539 for(int index = 0; index < m_nHeaps; ++index) {
540 #ifdef _USE_BUDDY_BLOCKS
541 VirtualFree(m_heaps[index].base, 0, MEM_RELEASE);
543 #ifdef USE_BIGBLOCK_ALLOC
544 if (m_heaps[index].bBigBlock) {
545 VirtualFree(m_heaps[index].base, 0, MEM_RELEASE);
549 HeapFree(m_hHeap, HEAP_NO_SERIALIZE, m_heaps[index].base);
550 #endif /* _USE_BUDDY_BLOCKS */
556 void VMem::Init(void)
558 #ifdef _USE_BUDDY_BLOCKS
561 * Initialize the free list by placing a dummy zero-length block on it.
562 * Set the end of list marker.
563 * Set the number of non-contiguous heaps to zero.
564 * Set the next allocation size.
566 for (int index = 0; index < nListEntries; ++index) {
567 pFreeList = GetFreeListLink(index);
568 SIZE(pFreeList) = PSIZE(pFreeList+minAllocSize) = 0;
569 PREV(pFreeList) = NEXT(pFreeList) = pFreeList;
571 pFreeList = GetEOLFreeList();
572 SIZE(pFreeList) = PSIZE(pFreeList+minAllocSize) = 0;
573 PREV(pFreeList) = NEXT(pFreeList) = NULL;
574 m_pRover = GetOverSizeFreeList();
577 * Initialize the free list by placing a dummy zero-length block on it.
578 * Set the number of non-contiguous heaps to zero.
580 m_pFreeList = m_pRover = (PBLOCK)(&m_FreeDummy[sizeofTag]);
581 PSIZE(m_pFreeList+minAllocSize) = SIZE(m_pFreeList) = 0;
582 PREV(m_pFreeList) = NEXT(m_pFreeList) = m_pFreeList;
586 m_lAllocSize = lAllocStart;
589 void* VMem::Malloc(size_t size)
596 * Disallow negative or zero sizes.
598 size_t realsize = CalcAllocSize(size);
599 if((int)realsize < minAllocSize || size == 0)
602 #ifdef _USE_BUDDY_BLOCKS
604 * Check the free list of small blocks if this is free use it
605 * Otherwise check the rover if it has no blocks then
606 * Scan the free list entries use the first free block
607 * split the block if needed, stop at end of list marker
610 int index = CalcEntry(realsize);
611 if (index < nListEntries-1) {
612 ptr = GetFreeListLink(index);
614 if (lsize >= realsize) {
615 rem = lsize - realsize;
616 if(rem < minAllocSize) {
617 /* Unlink the block from the free list. */
623 * The remainder is big enough to split off into a new block.
624 * Use the end of the block, resize the beginning of the block
625 * no need to change the free list.
631 SetTags(ptr, lsize | 1);
636 if (lsize >= realsize) {
637 rem = lsize - realsize;
638 if(rem < minAllocSize) {
639 /* Unlink the block from the free list. */
645 * The remainder is big enough to split off into a new block.
646 * Use the end of the block, resize the beginning of the block
647 * no need to change the free list.
653 SetTags(ptr, lsize | 1);
656 ptr = GetFreeListLink(index+1);
659 if (lsize >= realsize) {
660 size_t rem = lsize - realsize;
661 if(rem < minAllocSize) {
662 /* Unlink the block from the free list. */
668 * The remainder is big enough to split off into a new block.
669 * Use the end of the block, resize the beginning of the block
670 * no need to change the free list.
676 SetTags(ptr, lsize | 1);
679 ptr += sizeof(FREE_LIST_ENTRY);
686 * Start searching the free list at the rover. If we arrive back at rover without
687 * finding anything, allocate some memory from the heap and try again.
689 ptr = m_pRover; /* start searching at rover */
690 int loops = 2; /* allow two times through the loop */
693 ASSERT((lsize&1)==0);
694 /* is block big enough? */
695 if(lsize >= realsize) {
696 /* if the remainder is too small, don't bother splitting the block. */
697 rem = lsize - realsize;
698 if(rem < minAllocSize) {
700 m_pRover = NEXT(ptr);
702 /* Unlink the block from the free list. */
708 * The remainder is big enough to split off into a new block.
709 * Use the end of the block, resize the beginning of the block
710 * no need to change the free list.
716 /* Set the boundary tags to mark it as allocated. */
717 SetTags(ptr, lsize | 1);
718 return ((void *)ptr);
722 * This block was unsuitable. If we've gone through this list once already without
723 * finding anything, allocate some new memory from the heap and try again.
726 if(ptr == m_pRover) {
727 if(!(loops-- && Getmem(realsize))) {
735 void* VMem::Realloc(void* block, size_t size)
739 /* if size is zero, free the block. */
745 /* if block pointer is NULL, do a Malloc(). */
750 * Grow or shrink the block in place.
751 * if the block grows then the next block will be used if free
753 if(Expand(block, size) != NULL)
756 size_t realsize = CalcAllocSize(size);
757 if((int)realsize < minAllocSize)
761 * see if the previous block is free, and is it big enough to cover the new size
762 * if merged with the current block.
764 PBLOCK ptr = (PBLOCK)block;
765 size_t cursize = SIZE(ptr) & ~1;
766 size_t psize = PSIZE(ptr);
767 if((psize&1) == 0 && (psize + cursize) >= realsize) {
768 PBLOCK prev = ptr - psize;
770 m_pRover = NEXT(prev);
772 /* Unlink the next block from the free list. */
775 /* Copy contents of old block to new location, make it the current block. */
776 memmove(prev, ptr, cursize);
777 cursize += psize; /* combine sizes */
780 size_t rem = cursize - realsize;
781 if(rem >= minAllocSize) {
783 * The remainder is big enough to be a new block. Set boundary
784 * tags for the resized block and the new block.
786 prev = ptr + realsize;
788 * add the new block to the free list.
789 * next block cannot be free
792 #ifdef _USE_BUDDY_BLOCKS
793 AddToFreeList(prev, rem);
795 AddToFreeList(prev, m_pFreeList);
799 /* Set the boundary tags to mark it as allocated. */
800 SetTags(ptr, cursize | 1);
801 return ((void *)ptr);
804 /* Allocate a new block, copy the old to the new, and free the old. */
805 if((ptr = (PBLOCK)Malloc(size)) != NULL) {
806 memmove(ptr, block, cursize-blockOverhead);
809 return ((void *)ptr);
812 void VMem::Free(void* p)
816 /* Ignore null pointer. */
820 PBLOCK ptr = (PBLOCK)p;
822 /* Check for attempt to free a block that's already free. */
823 size_t size = SIZE(ptr);
825 MEMODSlx("Attempt to free previously freed block", (long)p);
828 size &= ~1; /* remove allocated tag */
830 /* if previous block is free, add this block to it. */
831 #ifndef _USE_BUDDY_BLOCKS
834 size_t psize = PSIZE(ptr);
836 ptr -= psize; /* point to previous block */
837 size += psize; /* merge the sizes of the two blocks */
838 #ifdef _USE_BUDDY_BLOCKS
841 linked = TRUE; /* it's already on the free list */
845 /* if the next physical block is free, merge it with this block. */
846 PBLOCK next = ptr + size; /* point to next physical block */
847 size_t nsize = SIZE(next);
849 /* block is free move rover if needed */
851 m_pRover = NEXT(next);
853 /* unlink the next block from the free list. */
856 /* merge the sizes of this block and the next block. */
860 /* Set the boundary tags for the block; */
863 /* Link the block to the head of the free list. */
864 #ifdef _USE_BUDDY_BLOCKS
865 AddToFreeList(ptr, size);
868 AddToFreeList(ptr, m_pFreeList);
873 void VMem::GetLock(void)
875 EnterCriticalSection(&m_cs);
878 void VMem::FreeLock(void)
880 LeaveCriticalSection(&m_cs);
883 int VMem::IsLocked(void)
886 /* XXX TryEnterCriticalSection() is not available in some versions
887 * of Windows 95. Since this code is not used anywhere yet, we
888 * skirt the issue for now. */
889 BOOL bAccessed = TryEnterCriticalSection(&m_cs);
891 LeaveCriticalSection(&m_cs);
895 ASSERT(0); /* alarm bells for when somebody calls this */
901 long VMem::Release(void)
903 long lCount = InterlockedDecrement(&m_lRefCount);
909 long VMem::AddRef(void)
911 long lCount = InterlockedIncrement(&m_lRefCount);
916 int VMem::Getmem(size_t requestSize)
917 { /* returns -1 is successful 0 if not */
918 #ifdef USE_BIGBLOCK_ALLOC
923 /* Round up size to next multiple of 64K. */
924 size_t size = (size_t)ROUND_UP64K(requestSize);
927 * if the size requested is smaller than our current allocation size
930 if(size < (unsigned long)m_lAllocSize)
933 /* Update the size to allocate on the next request */
934 if(m_lAllocSize != lAllocMax)
937 #ifndef _USE_BUDDY_BLOCKS
939 #ifdef USE_BIGBLOCK_ALLOC
940 && !m_heaps[m_nHeaps-1].bBigBlock
943 /* Expand the last allocated heap */
944 ptr = HeapReAlloc(m_hHeap, HEAP_REALLOC_IN_PLACE_ONLY|HEAP_NO_SERIALIZE,
945 m_heaps[m_nHeaps-1].base,
946 m_heaps[m_nHeaps-1].len + size);
948 HeapAdd(((char*)ptr) + m_heaps[m_nHeaps-1].len, size
949 #ifdef USE_BIGBLOCK_ALLOC
956 #endif /* _USE_BUDDY_BLOCKS */
959 * if we didn't expand a block to cover the requested size
960 * allocate a new Heap
961 * the size of this block must include the additional dummy tags at either end
962 * the above ROUND_UP64K may not have added any memory to include this.
964 if(size == requestSize)
965 size = (size_t)ROUND_UP64K(requestSize+(blockOverhead));
968 #ifdef _USE_BUDDY_BLOCKS
969 ptr = VirtualAlloc(NULL, size, MEM_COMMIT, PAGE_READWRITE);
971 #ifdef USE_BIGBLOCK_ALLOC
973 if (size >= nMaxHeapAllocSize) {
975 ptr = VirtualAlloc(NULL, size, MEM_COMMIT, PAGE_READWRITE);
979 ptr = HeapAlloc(m_hHeap, HEAP_NO_SERIALIZE, size);
980 #endif /* _USE_BUDDY_BLOCKS */
983 /* try to allocate a smaller chunk */
985 if(size > requestSize)
990 MEMODSlx("HeapAlloc failed on size!!!", size);
994 #ifdef _USE_BUDDY_BLOCKS
995 if (HeapAdd(ptr, size)) {
996 VirtualFree(ptr, 0, MEM_RELEASE);
1000 #ifdef USE_BIGBLOCK_ALLOC
1001 if (HeapAdd(ptr, size, bBigBlock)) {
1003 VirtualFree(ptr, 0, MEM_RELEASE);
1009 #endif /* _USE_BUDDY_BLOCKS */
1013 int VMem::HeapAdd(void* p, size_t size
1014 #ifdef USE_BIGBLOCK_ALLOC
1018 { /* if the block can be succesfully added to the heap, returns 0; otherwise -1. */
1021 /* Check size, then round size down to next long word boundary. */
1022 if(size < minAllocSize)
1025 size = (size_t)ROUND_DOWN(size);
1026 PBLOCK ptr = (PBLOCK)p;
1028 #ifdef USE_BIGBLOCK_ALLOC
1032 * Search for another heap area that's contiguous with the bottom of this new area.
1033 * (It should be extremely unusual to find one that's contiguous with the top).
1035 for(index = 0; index < m_nHeaps; ++index) {
1036 if(ptr == m_heaps[index].base + (int)m_heaps[index].len) {
1038 * The new block is contiguous with a previously allocated heap area. Add its
1039 * length to that of the previous heap. Merge it with the dummy end-of-heap
1040 * area marker of the previous heap.
1042 m_heaps[index].len += size;
1046 #ifdef USE_BIGBLOCK_ALLOC
1053 if(index == m_nHeaps) {
1054 /* The new block is not contiguous, or is BigBlock. Add it to the heap list. */
1055 if(m_nHeaps == maxHeaps) {
1056 return -1; /* too many non-contiguous heaps */
1058 m_heaps[m_nHeaps].base = ptr;
1059 m_heaps[m_nHeaps].len = size;
1060 #ifdef USE_BIGBLOCK_ALLOC
1061 m_heaps[m_nHeaps].bBigBlock = bBigBlock;
1066 * Reserve the first LONG in the block for the ending boundary tag of a dummy
1067 * block at the start of the heap area.
1069 size -= blockOverhead;
1070 ptr += blockOverhead;
1071 PSIZE(ptr) = 1; /* mark the dummy previous block as allocated */
1075 * Convert the heap to one large block. Set up its boundary tags, and those of
1076 * marker block after it. The marker block before the heap will already have
1077 * been set up if this heap is not contiguous with the end of another heap.
1079 SetTags(ptr, size | 1);
1080 PBLOCK next = ptr + size; /* point to dummy end block */
1081 SIZE(next) = 1; /* mark the dummy end block as allocated */
1084 * Link the block to the start of the free list by calling free().
1085 * This will merge the block with any adjacent free blocks.
1092 void* VMem::Expand(void* block, size_t size)
1095 * Disallow negative or zero sizes.
1097 size_t realsize = CalcAllocSize(size);
1098 if((int)realsize < minAllocSize || size == 0)
1101 PBLOCK ptr = (PBLOCK)block;
1103 /* if the current size is the same as requested, do nothing. */
1104 size_t cursize = SIZE(ptr) & ~1;
1105 if(cursize == realsize) {
1109 /* if the block is being shrunk, convert the remainder of the block into a new free block. */
1110 if(realsize <= cursize) {
1111 size_t nextsize = cursize - realsize; /* size of new remainder block */
1112 if(nextsize >= minAllocSize) {
1115 * Set boundary tags for the resized block and the new block.
1117 SetTags(ptr, realsize | 1);
1121 * add the new block to the free list.
1122 * call Free to merge this block with next block if free
1124 SetTags(ptr, nextsize | 1);
1131 PBLOCK next = ptr + cursize;
1132 size_t nextsize = SIZE(next);
1134 /* Check the next block for consistency.*/
1135 if((nextsize&1) == 0 && (nextsize + cursize) >= realsize) {
1137 * The next block is free and big enough. Add the part that's needed
1138 * to our block, and split the remainder off into a new block.
1140 if(m_pRover == next)
1141 m_pRover = NEXT(next);
1143 /* Unlink the next block from the free list. */
1145 cursize += nextsize; /* combine sizes */
1147 size_t rem = cursize - realsize; /* size of remainder */
1148 if(rem >= minAllocSize) {
1150 * The remainder is big enough to be a new block.
1151 * Set boundary tags for the resized block and the new block.
1153 next = ptr + realsize;
1155 * add the new block to the free list.
1156 * next block cannot be free
1159 #ifdef _USE_BUDDY_BLOCKS
1160 AddToFreeList(next, rem);
1162 AddToFreeList(next, m_pFreeList);
1166 /* Set the boundary tags to mark it as allocated. */
1167 SetTags(ptr, cursize | 1);
1168 return ((void *)ptr);
1174 #define LOG_FILENAME ".\\MemLog.txt"
1176 void VMem::MemoryUsageMessage(char *str, long x, long y, int c)
1181 m_pLog = fopen(LOG_FILENAME, "w");
1182 sprintf(szBuffer, str, x, y, c);
1183 fputs(szBuffer, m_pLog);
1194 void VMem::WalkHeap(int complete)
1197 MemoryUsageMessage(NULL, 0, 0, 0);
1199 for(int i = 0; i < m_nHeaps; ++i) {
1200 total += m_heaps[i].len;
1202 MemoryUsageMessage("VMem heaps used %d. Total memory %08x\n", m_nHeaps, total, 0);
1204 /* Walk all the heaps - verify structures */
1205 for(int index = 0; index < m_nHeaps; ++index) {
1206 PBLOCK ptr = m_heaps[index].base;
1207 size_t size = m_heaps[index].len;
1208 #ifndef _USE_BUDDY_BLOCKS
1209 #ifdef USE_BIGBLOCK_ALLOC
1210 if (!m_heaps[m_nHeaps].bBigBlock)
1212 ASSERT(HeapValidate(m_hHeap, HEAP_NO_SERIALIZE, ptr));
1215 /* set over reserved header block */
1216 size -= blockOverhead;
1217 ptr += blockOverhead;
1218 PBLOCK pLast = ptr + size;
1219 ASSERT(PSIZE(ptr) == 1); /* dummy previous block is allocated */
1220 ASSERT(SIZE(pLast) == 1); /* dummy next block is allocated */
1221 while(ptr < pLast) {
1222 ASSERT(ptr > m_heaps[index].base);
1223 size_t cursize = SIZE(ptr) & ~1;
1224 ASSERT((PSIZE(ptr+cursize) & ~1) == cursize);
1225 MemoryUsageMessage("Memory Block %08x: Size %08x %c\n", (long)ptr, cursize, (SIZE(ptr)&1) ? 'x' : ' ');
1226 if(!(SIZE(ptr)&1)) {
1227 /* this block is on the free list */
1228 PBLOCK tmp = NEXT(ptr);
1230 ASSERT((SIZE(tmp)&1)==0);
1231 if(tmp == m_pFreeList)
1237 MemoryUsageMessage("Memory Block %08x: Size %08x free but not in free list\n", (long)ptr, cursize, 0);
1243 MemoryUsageMessage(NULL, 0, 0, 0);
1246 #endif /* _DEBUG_MEM */
1248 #endif /* _USE_MSVCRT_MEM_ALLOC */
1250 #endif /* ___VMEM_H_INC___ */