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 the compiler's MSVCR*.DLL. Defining _USE_LINKED_LIST as
13 * well will 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 through to the compiler's msvcr*.dll.
69 * Optionaly track by using a doubly linked header.
72 #ifdef _USE_LINKED_LIST
74 typedef struct _MemoryBlockHeader* PMEMORY_BLOCK_HEADER;
75 typedef struct _MemoryBlockHeader {
76 PMEMORY_BLOCK_HEADER pNext;
77 PMEMORY_BLOCK_HEADER pPrev;
79 } MEMORY_BLOCK_HEADER, *PMEMORY_BLOCK_HEADER;
87 void* Malloc(size_t size);
88 void* Realloc(void* pMem, size_t size);
89 void Free(void* pMem);
96 inline BOOL CreateOk(void)
102 #ifdef _USE_LINKED_LIST
103 void LinkBlock(PMEMORY_BLOCK_HEADER ptr)
105 PMEMORY_BLOCK_HEADER next = m_Dummy.pNext;
107 ptr->pPrev = &m_Dummy;
112 void UnlinkBlock(PMEMORY_BLOCK_HEADER ptr)
114 PMEMORY_BLOCK_HEADER next = ptr->pNext;
115 PMEMORY_BLOCK_HEADER prev = ptr->pPrev;
120 MEMORY_BLOCK_HEADER m_Dummy;
121 CRITICAL_SECTION m_cs; // access lock
124 long m_lRefCount; // number of current users
130 #ifdef _USE_LINKED_LIST
131 InitializeCriticalSection(&m_cs);
132 m_Dummy.pNext = m_Dummy.pPrev = &m_Dummy;
133 m_Dummy.owner = this;
139 #ifdef _USE_LINKED_LIST
140 while (m_Dummy.pNext != &m_Dummy) {
141 Free(m_Dummy.pNext+1);
143 DeleteCriticalSection(&m_cs);
147 void* VMem::Malloc(size_t size)
149 #ifdef _USE_LINKED_LIST
151 PMEMORY_BLOCK_HEADER ptr = (PMEMORY_BLOCK_HEADER)malloc(size+sizeof(MEMORY_BLOCK_HEADER));
164 void* VMem::Realloc(void* pMem, size_t size)
166 #ifdef _USE_LINKED_LIST
176 PMEMORY_BLOCK_HEADER ptr = (PMEMORY_BLOCK_HEADER)(((char*)pMem)-sizeof(MEMORY_BLOCK_HEADER));
178 ptr = (PMEMORY_BLOCK_HEADER)realloc(ptr, size+sizeof(MEMORY_BLOCK_HEADER));
188 return realloc(pMem, size);
192 void VMem::Free(void* pMem)
194 #ifdef _USE_LINKED_LIST
196 PMEMORY_BLOCK_HEADER ptr = (PMEMORY_BLOCK_HEADER)(((char*)pMem)-sizeof(MEMORY_BLOCK_HEADER));
197 if (ptr->owner != this) {
201 Perl_warn_nocontext("Free to wrong pool %p not %p",this,ptr->owner);
202 *nowhere = 0; /* this segfault is deliberate,
203 so you can see the stack trace */
205 ptr->owner->Free(pMem);
216 #else /*_USE_LINKED_LIST*/
221 void VMem::GetLock(void)
223 #ifdef _USE_LINKED_LIST
224 EnterCriticalSection(&m_cs);
228 void VMem::FreeLock(void)
230 #ifdef _USE_LINKED_LIST
231 LeaveCriticalSection(&m_cs);
235 int VMem::IsLocked(void)
238 /* XXX TryEnterCriticalSection() is not available in some versions
239 * of Windows 95. Since this code is not used anywhere yet, we
240 * skirt the issue for now. */
241 BOOL bAccessed = TryEnterCriticalSection(&m_cs);
243 LeaveCriticalSection(&m_cs);
247 ASSERT(0); /* alarm bells for when somebody calls this */
252 long VMem::Release(void)
254 long lCount = InterlockedDecrement(&m_lRefCount);
260 long VMem::AddRef(void)
262 long lCount = InterlockedIncrement(&m_lRefCount);
266 #else /* _USE_MSVCRT_MEM_ALLOC */
269 * Knuth's boundary tag algorithm Vol #1, Page 440.
271 * Each block in the heap has tag words before and after it,
275 * The size is stored in these tags as a long word, and includes the 8 bytes
276 * of overhead that the boundary tags consume. Blocks are allocated on long
277 * word boundaries, so the size is always multiples of long words. When the
278 * block is allocated, bit 0, (the tag bit), of the size is set to 1. When
279 * a block is freed, it is merged with adjacent free blocks, and the tag bit
282 * A linked list is used to manage the free list. The first two long words of
283 * the block contain double links. These links are only valid when the block
284 * is freed, therefore space needs to be reserved for them. Thus, the minimum
285 * block size (not counting the tags) is 8 bytes.
287 * Since memory allocation may occur on a single threaded, explict locks are not
292 const long lAllocStart = 0x00020000; /* start at 128K */
293 const long minBlockSize = sizeof(void*)*2;
294 const long sizeofTag = sizeof(long);
295 const long blockOverhead = sizeofTag*2;
296 const long minAllocSize = minBlockSize+blockOverhead;
297 #ifdef _USE_BUDDY_BLOCKS
298 const long lSmallBlockSize = 1024;
299 const size_t nListEntries = ((lSmallBlockSize-minAllocSize)/sizeof(long));
301 inline size_t CalcEntry(size_t size)
303 ASSERT((size&(sizeof(long)-1)) == 0);
304 return ((size - minAllocSize) / sizeof(long));
308 typedef BYTE* PBLOCK; /* pointer to a memory block */
311 * Macros for accessing hidden fields in a memory block:
313 * SIZE size of this block (tag bit 0 is 1 if block is allocated)
314 * PSIZE size of previous physical block
317 #define SIZE(block) (*(ULONG*)(((PBLOCK)(block))-sizeofTag))
318 #define PSIZE(block) (*(ULONG*)(((PBLOCK)(block))-(blockOverhead)))
319 inline void SetTags(PBLOCK block, long size)
322 PSIZE(block+(size&~1)) = size;
327 * PREV pointer to previous block
328 * NEXT pointer to next block
331 #define PREV(block) (*(PBLOCK*)(block))
332 #define NEXT(block) (*(PBLOCK*)((block)+sizeof(PBLOCK)))
333 inline void SetLink(PBLOCK block, PBLOCK prev, PBLOCK next)
338 inline void Unlink(PBLOCK p)
340 PBLOCK next = NEXT(p);
341 PBLOCK prev = PREV(p);
345 #ifndef _USE_BUDDY_BLOCKS
346 inline void AddToFreeList(PBLOCK block, PBLOCK pInList)
348 PBLOCK next = NEXT(pInList);
349 NEXT(pInList) = block;
350 SetLink(block, pInList, next);
355 /* Macro for rounding up to the next sizeof(long) */
356 #define ROUND_UP(n) (((ULONG)(n)+sizeof(long)-1)&~(sizeof(long)-1))
357 #define ROUND_UP64K(n) (((ULONG)(n)+0x10000-1)&~(0x10000-1))
358 #define ROUND_DOWN(n) ((ULONG)(n)&~(sizeof(long)-1))
361 * HeapRec - a list of all non-contiguous heap areas
363 * Each record in this array contains information about a non-contiguous heap area.
366 const int maxHeaps = 32; /* 64 was overkill */
367 const long lAllocMax = 0x80000000; /* max size of allocation */
369 #ifdef _USE_BUDDY_BLOCKS
370 typedef struct _FreeListEntry
372 BYTE Dummy[minAllocSize]; // dummy free block
373 } FREE_LIST_ENTRY, *PFREE_LIST_ENTRY;
376 #ifndef _USE_BUDDY_BLOCKS
377 #define USE_BIGBLOCK_ALLOC
381 * Use VirtualAlloc() for blocks bigger than nMaxHeapAllocSize since
382 * Windows 95/98/Me have heap managers that are designed for memory
383 * blocks smaller than four megabytes.
386 #ifdef USE_BIGBLOCK_ALLOC
387 const int nMaxHeapAllocSize = (1024*512); /* don't allocate anything larger than this from the heap */
390 typedef struct _HeapRec
392 PBLOCK base; /* base of heap area */
393 ULONG len; /* size of heap area */
394 #ifdef USE_BIGBLOCK_ALLOC
395 BOOL bBigBlock; /* was allocate using VirtualAlloc */
404 void* Malloc(size_t size);
405 void* Realloc(void* pMem, size_t size);
406 void Free(void* pMem);
413 inline BOOL CreateOk(void)
415 #ifdef _USE_BUDDY_BLOCKS
418 return m_hHeap != NULL;
426 int Getmem(size_t size);
428 int HeapAdd(void* ptr, size_t size
429 #ifdef USE_BIGBLOCK_ALLOC
434 void* Expand(void* block, size_t size);
436 #ifdef _USE_BUDDY_BLOCKS
437 inline PBLOCK GetFreeListLink(int index)
439 if (index >= nListEntries)
440 index = nListEntries-1;
441 return &m_FreeList[index].Dummy[sizeofTag];
443 inline PBLOCK GetOverSizeFreeList(void)
445 return &m_FreeList[nListEntries-1].Dummy[sizeofTag];
447 inline PBLOCK GetEOLFreeList(void)
449 return &m_FreeList[nListEntries].Dummy[sizeofTag];
452 void AddToFreeList(PBLOCK block, size_t size)
454 PBLOCK pFreeList = GetFreeListLink(CalcEntry(size));
455 PBLOCK next = NEXT(pFreeList);
456 NEXT(pFreeList) = block;
457 SetLink(block, pFreeList, next);
461 inline size_t CalcAllocSize(size_t size)
464 * Adjust the real size of the block to be a multiple of sizeof(long), and add
465 * the overhead for the boundary tags. Disallow negative or zero sizes.
467 return (size < minBlockSize) ? minAllocSize : (size_t)ROUND_UP(size) + blockOverhead;
470 #ifdef _USE_BUDDY_BLOCKS
471 FREE_LIST_ENTRY m_FreeList[nListEntries+1]; // free list with dummy end of list entry as well
473 HANDLE m_hHeap; // memory heap for this script
474 char m_FreeDummy[minAllocSize]; // dummy free block
475 PBLOCK m_pFreeList; // pointer to first block on free list
477 PBLOCK m_pRover; // roving pointer into the free list
478 HeapRec m_heaps[maxHeaps]; // list of all non-contiguous heap areas
479 int m_nHeaps; // no. of heaps in m_heaps
480 long m_lAllocSize; // current alloc size
481 long m_lRefCount; // number of current users
482 CRITICAL_SECTION m_cs; // access lock
485 void WalkHeap(int complete);
486 void MemoryUsageMessage(char *str, long x, long y, int c);
494 #ifndef _USE_BUDDY_BLOCKS
495 BOOL bRet = (NULL != (m_hHeap = HeapCreate(HEAP_NO_SERIALIZE,
496 lAllocStart, /* initial size of heap */
497 0))); /* no upper limit on size of heap */
501 InitializeCriticalSection(&m_cs);
511 #ifndef _USE_BUDDY_BLOCKS
512 ASSERT(HeapValidate(m_hHeap, HEAP_NO_SERIALIZE, NULL));
516 DeleteCriticalSection(&m_cs);
517 #ifdef _USE_BUDDY_BLOCKS
518 for(int index = 0; index < m_nHeaps; ++index) {
519 VirtualFree(m_heaps[index].base, 0, MEM_RELEASE);
521 #else /* !_USE_BUDDY_BLOCKS */
522 #ifdef USE_BIGBLOCK_ALLOC
523 for(int index = 0; index < m_nHeaps; ++index) {
524 if (m_heaps[index].bBigBlock) {
525 VirtualFree(m_heaps[index].base, 0, MEM_RELEASE);
529 BOOL bRet = HeapDestroy(m_hHeap);
531 #endif /* _USE_BUDDY_BLOCKS */
534 void VMem::ReInit(void)
536 for(int index = 0; index < m_nHeaps; ++index) {
537 #ifdef _USE_BUDDY_BLOCKS
538 VirtualFree(m_heaps[index].base, 0, MEM_RELEASE);
540 #ifdef USE_BIGBLOCK_ALLOC
541 if (m_heaps[index].bBigBlock) {
542 VirtualFree(m_heaps[index].base, 0, MEM_RELEASE);
546 HeapFree(m_hHeap, HEAP_NO_SERIALIZE, m_heaps[index].base);
547 #endif /* _USE_BUDDY_BLOCKS */
553 void VMem::Init(void)
555 #ifdef _USE_BUDDY_BLOCKS
558 * Initialize the free list by placing a dummy zero-length block on it.
559 * Set the end of list marker.
560 * Set the number of non-contiguous heaps to zero.
561 * Set the next allocation size.
563 for (int index = 0; index < nListEntries; ++index) {
564 pFreeList = GetFreeListLink(index);
565 SIZE(pFreeList) = PSIZE(pFreeList+minAllocSize) = 0;
566 PREV(pFreeList) = NEXT(pFreeList) = pFreeList;
568 pFreeList = GetEOLFreeList();
569 SIZE(pFreeList) = PSIZE(pFreeList+minAllocSize) = 0;
570 PREV(pFreeList) = NEXT(pFreeList) = NULL;
571 m_pRover = GetOverSizeFreeList();
574 * Initialize the free list by placing a dummy zero-length block on it.
575 * Set the number of non-contiguous heaps to zero.
577 m_pFreeList = m_pRover = (PBLOCK)(&m_FreeDummy[sizeofTag]);
578 PSIZE(m_pFreeList+minAllocSize) = SIZE(m_pFreeList) = 0;
579 PREV(m_pFreeList) = NEXT(m_pFreeList) = m_pFreeList;
583 m_lAllocSize = lAllocStart;
586 void* VMem::Malloc(size_t size)
593 * Disallow negative or zero sizes.
595 size_t realsize = CalcAllocSize(size);
596 if((int)realsize < minAllocSize || size == 0)
599 #ifdef _USE_BUDDY_BLOCKS
601 * Check the free list of small blocks if this is free use it
602 * Otherwise check the rover if it has no blocks then
603 * Scan the free list entries use the first free block
604 * split the block if needed, stop at end of list marker
607 int index = CalcEntry(realsize);
608 if (index < nListEntries-1) {
609 ptr = GetFreeListLink(index);
611 if (lsize >= realsize) {
612 rem = lsize - realsize;
613 if(rem < minAllocSize) {
614 /* Unlink the block from the free list. */
620 * The remainder is big enough to split off into a new block.
621 * Use the end of the block, resize the beginning of the block
622 * no need to change the free list.
628 SetTags(ptr, lsize | 1);
633 if (lsize >= realsize) {
634 rem = lsize - realsize;
635 if(rem < minAllocSize) {
636 /* Unlink the block from the free list. */
642 * The remainder is big enough to split off into a new block.
643 * Use the end of the block, resize the beginning of the block
644 * no need to change the free list.
650 SetTags(ptr, lsize | 1);
653 ptr = GetFreeListLink(index+1);
656 if (lsize >= realsize) {
657 size_t rem = lsize - realsize;
658 if(rem < minAllocSize) {
659 /* Unlink the block from the free list. */
665 * The remainder is big enough to split off into a new block.
666 * Use the end of the block, resize the beginning of the block
667 * no need to change the free list.
673 SetTags(ptr, lsize | 1);
676 ptr += sizeof(FREE_LIST_ENTRY);
683 * Start searching the free list at the rover. If we arrive back at rover without
684 * finding anything, allocate some memory from the heap and try again.
686 ptr = m_pRover; /* start searching at rover */
687 int loops = 2; /* allow two times through the loop */
690 ASSERT((lsize&1)==0);
691 /* is block big enough? */
692 if(lsize >= realsize) {
693 /* if the remainder is too small, don't bother splitting the block. */
694 rem = lsize - realsize;
695 if(rem < minAllocSize) {
697 m_pRover = NEXT(ptr);
699 /* Unlink the block from the free list. */
705 * The remainder is big enough to split off into a new block.
706 * Use the end of the block, resize the beginning of the block
707 * no need to change the free list.
713 /* Set the boundary tags to mark it as allocated. */
714 SetTags(ptr, lsize | 1);
715 return ((void *)ptr);
719 * This block was unsuitable. If we've gone through this list once already without
720 * finding anything, allocate some new memory from the heap and try again.
723 if(ptr == m_pRover) {
724 if(!(loops-- && Getmem(realsize))) {
732 void* VMem::Realloc(void* block, size_t size)
736 /* if size is zero, free the block. */
742 /* if block pointer is NULL, do a Malloc(). */
747 * Grow or shrink the block in place.
748 * if the block grows then the next block will be used if free
750 if(Expand(block, size) != NULL)
753 size_t realsize = CalcAllocSize(size);
754 if((int)realsize < minAllocSize)
758 * see if the previous block is free, and is it big enough to cover the new size
759 * if merged with the current block.
761 PBLOCK ptr = (PBLOCK)block;
762 size_t cursize = SIZE(ptr) & ~1;
763 size_t psize = PSIZE(ptr);
764 if((psize&1) == 0 && (psize + cursize) >= realsize) {
765 PBLOCK prev = ptr - psize;
767 m_pRover = NEXT(prev);
769 /* Unlink the next block from the free list. */
772 /* Copy contents of old block to new location, make it the current block. */
773 memmove(prev, ptr, cursize);
774 cursize += psize; /* combine sizes */
777 size_t rem = cursize - realsize;
778 if(rem >= minAllocSize) {
780 * The remainder is big enough to be a new block. Set boundary
781 * tags for the resized block and the new block.
783 prev = ptr + realsize;
785 * add the new block to the free list.
786 * next block cannot be free
789 #ifdef _USE_BUDDY_BLOCKS
790 AddToFreeList(prev, rem);
792 AddToFreeList(prev, m_pFreeList);
796 /* Set the boundary tags to mark it as allocated. */
797 SetTags(ptr, cursize | 1);
798 return ((void *)ptr);
801 /* Allocate a new block, copy the old to the new, and free the old. */
802 if((ptr = (PBLOCK)Malloc(size)) != NULL) {
803 memmove(ptr, block, cursize-blockOverhead);
806 return ((void *)ptr);
809 void VMem::Free(void* p)
813 /* Ignore null pointer. */
817 PBLOCK ptr = (PBLOCK)p;
819 /* Check for attempt to free a block that's already free. */
820 size_t size = SIZE(ptr);
822 MEMODSlx("Attempt to free previously freed block", (long)p);
825 size &= ~1; /* remove allocated tag */
827 /* if previous block is free, add this block to it. */
828 #ifndef _USE_BUDDY_BLOCKS
831 size_t psize = PSIZE(ptr);
833 ptr -= psize; /* point to previous block */
834 size += psize; /* merge the sizes of the two blocks */
835 #ifdef _USE_BUDDY_BLOCKS
838 linked = TRUE; /* it's already on the free list */
842 /* if the next physical block is free, merge it with this block. */
843 PBLOCK next = ptr + size; /* point to next physical block */
844 size_t nsize = SIZE(next);
846 /* block is free move rover if needed */
848 m_pRover = NEXT(next);
850 /* unlink the next block from the free list. */
853 /* merge the sizes of this block and the next block. */
857 /* Set the boundary tags for the block; */
860 /* Link the block to the head of the free list. */
861 #ifdef _USE_BUDDY_BLOCKS
862 AddToFreeList(ptr, size);
865 AddToFreeList(ptr, m_pFreeList);
870 void VMem::GetLock(void)
872 EnterCriticalSection(&m_cs);
875 void VMem::FreeLock(void)
877 LeaveCriticalSection(&m_cs);
880 int VMem::IsLocked(void)
883 /* XXX TryEnterCriticalSection() is not available in some versions
884 * of Windows 95. Since this code is not used anywhere yet, we
885 * skirt the issue for now. */
886 BOOL bAccessed = TryEnterCriticalSection(&m_cs);
888 LeaveCriticalSection(&m_cs);
892 ASSERT(0); /* alarm bells for when somebody calls this */
898 long VMem::Release(void)
900 long lCount = InterlockedDecrement(&m_lRefCount);
906 long VMem::AddRef(void)
908 long lCount = InterlockedIncrement(&m_lRefCount);
913 int VMem::Getmem(size_t requestSize)
914 { /* returns -1 is successful 0 if not */
915 #ifdef USE_BIGBLOCK_ALLOC
920 /* Round up size to next multiple of 64K. */
921 size_t size = (size_t)ROUND_UP64K(requestSize);
924 * if the size requested is smaller than our current allocation size
927 if(size < (unsigned long)m_lAllocSize)
930 /* Update the size to allocate on the next request */
931 if(m_lAllocSize != lAllocMax)
934 #ifndef _USE_BUDDY_BLOCKS
936 #ifdef USE_BIGBLOCK_ALLOC
937 && !m_heaps[m_nHeaps-1].bBigBlock
940 /* Expand the last allocated heap */
941 ptr = HeapReAlloc(m_hHeap, HEAP_REALLOC_IN_PLACE_ONLY|HEAP_NO_SERIALIZE,
942 m_heaps[m_nHeaps-1].base,
943 m_heaps[m_nHeaps-1].len + size);
945 HeapAdd(((char*)ptr) + m_heaps[m_nHeaps-1].len, size
946 #ifdef USE_BIGBLOCK_ALLOC
953 #endif /* _USE_BUDDY_BLOCKS */
956 * if we didn't expand a block to cover the requested size
957 * allocate a new Heap
958 * the size of this block must include the additional dummy tags at either end
959 * the above ROUND_UP64K may not have added any memory to include this.
961 if(size == requestSize)
962 size = (size_t)ROUND_UP64K(requestSize+(blockOverhead));
965 #ifdef _USE_BUDDY_BLOCKS
966 ptr = VirtualAlloc(NULL, size, MEM_COMMIT, PAGE_READWRITE);
968 #ifdef USE_BIGBLOCK_ALLOC
970 if (size >= nMaxHeapAllocSize) {
972 ptr = VirtualAlloc(NULL, size, MEM_COMMIT, PAGE_READWRITE);
976 ptr = HeapAlloc(m_hHeap, HEAP_NO_SERIALIZE, size);
977 #endif /* _USE_BUDDY_BLOCKS */
980 /* try to allocate a smaller chunk */
982 if(size > requestSize)
987 MEMODSlx("HeapAlloc failed on size!!!", size);
991 #ifdef _USE_BUDDY_BLOCKS
992 if (HeapAdd(ptr, size)) {
993 VirtualFree(ptr, 0, MEM_RELEASE);
997 #ifdef USE_BIGBLOCK_ALLOC
998 if (HeapAdd(ptr, size, bBigBlock)) {
1000 VirtualFree(ptr, 0, MEM_RELEASE);
1006 #endif /* _USE_BUDDY_BLOCKS */
1010 int VMem::HeapAdd(void* p, size_t size
1011 #ifdef USE_BIGBLOCK_ALLOC
1015 { /* if the block can be succesfully added to the heap, returns 0; otherwise -1. */
1018 /* Check size, then round size down to next long word boundary. */
1019 if(size < minAllocSize)
1022 size = (size_t)ROUND_DOWN(size);
1023 PBLOCK ptr = (PBLOCK)p;
1025 #ifdef USE_BIGBLOCK_ALLOC
1029 * Search for another heap area that's contiguous with the bottom of this new area.
1030 * (It should be extremely unusual to find one that's contiguous with the top).
1032 for(index = 0; index < m_nHeaps; ++index) {
1033 if(ptr == m_heaps[index].base + (int)m_heaps[index].len) {
1035 * The new block is contiguous with a previously allocated heap area. Add its
1036 * length to that of the previous heap. Merge it with the dummy end-of-heap
1037 * area marker of the previous heap.
1039 m_heaps[index].len += size;
1043 #ifdef USE_BIGBLOCK_ALLOC
1050 if(index == m_nHeaps) {
1051 /* The new block is not contiguous, or is BigBlock. Add it to the heap list. */
1052 if(m_nHeaps == maxHeaps) {
1053 return -1; /* too many non-contiguous heaps */
1055 m_heaps[m_nHeaps].base = ptr;
1056 m_heaps[m_nHeaps].len = size;
1057 #ifdef USE_BIGBLOCK_ALLOC
1058 m_heaps[m_nHeaps].bBigBlock = bBigBlock;
1063 * Reserve the first LONG in the block for the ending boundary tag of a dummy
1064 * block at the start of the heap area.
1066 size -= blockOverhead;
1067 ptr += blockOverhead;
1068 PSIZE(ptr) = 1; /* mark the dummy previous block as allocated */
1072 * Convert the heap to one large block. Set up its boundary tags, and those of
1073 * marker block after it. The marker block before the heap will already have
1074 * been set up if this heap is not contiguous with the end of another heap.
1076 SetTags(ptr, size | 1);
1077 PBLOCK next = ptr + size; /* point to dummy end block */
1078 SIZE(next) = 1; /* mark the dummy end block as allocated */
1081 * Link the block to the start of the free list by calling free().
1082 * This will merge the block with any adjacent free blocks.
1089 void* VMem::Expand(void* block, size_t size)
1092 * Disallow negative or zero sizes.
1094 size_t realsize = CalcAllocSize(size);
1095 if((int)realsize < minAllocSize || size == 0)
1098 PBLOCK ptr = (PBLOCK)block;
1100 /* if the current size is the same as requested, do nothing. */
1101 size_t cursize = SIZE(ptr) & ~1;
1102 if(cursize == realsize) {
1106 /* if the block is being shrunk, convert the remainder of the block into a new free block. */
1107 if(realsize <= cursize) {
1108 size_t nextsize = cursize - realsize; /* size of new remainder block */
1109 if(nextsize >= minAllocSize) {
1112 * Set boundary tags for the resized block and the new block.
1114 SetTags(ptr, realsize | 1);
1118 * add the new block to the free list.
1119 * call Free to merge this block with next block if free
1121 SetTags(ptr, nextsize | 1);
1128 PBLOCK next = ptr + cursize;
1129 size_t nextsize = SIZE(next);
1131 /* Check the next block for consistency.*/
1132 if((nextsize&1) == 0 && (nextsize + cursize) >= realsize) {
1134 * The next block is free and big enough. Add the part that's needed
1135 * to our block, and split the remainder off into a new block.
1137 if(m_pRover == next)
1138 m_pRover = NEXT(next);
1140 /* Unlink the next block from the free list. */
1142 cursize += nextsize; /* combine sizes */
1144 size_t rem = cursize - realsize; /* size of remainder */
1145 if(rem >= minAllocSize) {
1147 * The remainder is big enough to be a new block.
1148 * Set boundary tags for the resized block and the new block.
1150 next = ptr + realsize;
1152 * add the new block to the free list.
1153 * next block cannot be free
1156 #ifdef _USE_BUDDY_BLOCKS
1157 AddToFreeList(next, rem);
1159 AddToFreeList(next, m_pFreeList);
1163 /* Set the boundary tags to mark it as allocated. */
1164 SetTags(ptr, cursize | 1);
1165 return ((void *)ptr);
1171 #define LOG_FILENAME ".\\MemLog.txt"
1173 void VMem::MemoryUsageMessage(char *str, long x, long y, int c)
1178 m_pLog = fopen(LOG_FILENAME, "w");
1179 sprintf(szBuffer, str, x, y, c);
1180 fputs(szBuffer, m_pLog);
1191 void VMem::WalkHeap(int complete)
1194 MemoryUsageMessage(NULL, 0, 0, 0);
1196 for(int i = 0; i < m_nHeaps; ++i) {
1197 total += m_heaps[i].len;
1199 MemoryUsageMessage("VMem heaps used %d. Total memory %08x\n", m_nHeaps, total, 0);
1201 /* Walk all the heaps - verify structures */
1202 for(int index = 0; index < m_nHeaps; ++index) {
1203 PBLOCK ptr = m_heaps[index].base;
1204 size_t size = m_heaps[index].len;
1205 #ifndef _USE_BUDDY_BLOCKS
1206 #ifdef USE_BIGBLOCK_ALLOC
1207 if (!m_heaps[m_nHeaps].bBigBlock)
1209 ASSERT(HeapValidate(m_hHeap, HEAP_NO_SERIALIZE, ptr));
1212 /* set over reserved header block */
1213 size -= blockOverhead;
1214 ptr += blockOverhead;
1215 PBLOCK pLast = ptr + size;
1216 ASSERT(PSIZE(ptr) == 1); /* dummy previous block is allocated */
1217 ASSERT(SIZE(pLast) == 1); /* dummy next block is allocated */
1218 while(ptr < pLast) {
1219 ASSERT(ptr > m_heaps[index].base);
1220 size_t cursize = SIZE(ptr) & ~1;
1221 ASSERT((PSIZE(ptr+cursize) & ~1) == cursize);
1222 MemoryUsageMessage("Memory Block %08x: Size %08x %c\n", (long)ptr, cursize, (SIZE(ptr)&1) ? 'x' : ' ');
1223 if(!(SIZE(ptr)&1)) {
1224 /* this block is on the free list */
1225 PBLOCK tmp = NEXT(ptr);
1227 ASSERT((SIZE(tmp)&1)==0);
1228 if(tmp == m_pFreeList)
1234 MemoryUsageMessage("Memory Block %08x: Size %08x free but not in free list\n", (long)ptr, cursize, 0);
1240 MemoryUsageMessage(NULL, 0, 0, 0);
1243 #endif /* _DEBUG_MEM */
1245 #endif /* _USE_MSVCRT_MEM_ALLOC */
1247 #endif /* ___VMEM_H_INC___ */