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.
10 * Knuth's boundary tag algorithm Vol #1, Page 440.
12 * Each block in the heap has tag words before and after it,
16 * The size is stored in these tags as a long word, and includes the 8 bytes
17 * of overhead that the boundary tags consume. Blocks are allocated on long
18 * word boundaries, so the size is always multiples of long words. When the
19 * block is allocated, bit 0, (the tag bit), of the size is set to 1. When
20 * a block is freed, it is merged with adjacent free blocks, and the tag bit
23 * A linked list is used to manage the free list. The first two long words of
24 * the block contain double links. These links are only valid when the block
25 * is freed, therefore space needs to be reserved for them. Thus, the minimum
26 * block size (not counting the tags) is 8 bytes.
28 * Since memory allocation may occur on a single threaded, explict locks are
33 #ifndef ___VMEM_H_INC___
34 #define ___VMEM_H_INC___
36 const long lAllocStart = 0x00010000; /* start at 64K */
37 const long minBlockSize = sizeof(void*)*2;
38 const long sizeofTag = sizeof(long);
39 const long blockOverhead = sizeofTag*2;
40 const long minAllocSize = minBlockSize+blockOverhead;
42 typedef BYTE* PBLOCK; /* pointer to a memory block */
45 * Macros for accessing hidden fields in a memory block:
47 * SIZE size of this block (tag bit 0 is 1 if block is allocated)
48 * PSIZE size of previous physical block
51 #define SIZE(block) (*(ULONG*)(((PBLOCK)(block))-sizeofTag))
52 #define PSIZE(block) (*(ULONG*)(((PBLOCK)(block))-(sizeofTag*2)))
53 inline void SetTags(PBLOCK block, long size)
56 PSIZE(block+(size&~1)) = size;
61 * PREV pointer to previous block
62 * NEXT pointer to next block
65 #define PREV(block) (*(PBLOCK*)(block))
66 #define NEXT(block) (*(PBLOCK*)((block)+sizeof(PBLOCK)))
67 inline void SetLink(PBLOCK block, PBLOCK prev, PBLOCK next)
72 inline void Unlink(PBLOCK p)
74 PBLOCK next = NEXT(p);
75 PBLOCK prev = PREV(p);
79 inline void AddToFreeList(PBLOCK block, PBLOCK pInList)
81 PBLOCK next = NEXT(pInList);
82 NEXT(pInList) = block;
83 SetLink(block, pInList, next);
88 /* Macro for rounding up to the next sizeof(long) */
89 #define ROUND_UP(n) (((ULONG)(n)+sizeof(long)-1)&~(sizeof(long)-1))
90 #define ROUND_UP64K(n) (((ULONG)(n)+0x10000-1)&~(0x10000-1))
91 #define ROUND_DOWN(n) ((ULONG)(n)&~(sizeof(long)-1))
94 * HeapRec - a list of all non-contiguous heap areas
96 * Each record in this array contains information about a non-contiguous heap area.
99 const int maxHeaps = 64;
100 const long lAllocMax = 0x80000000; /* max size of allocation */
102 typedef struct _HeapRec
104 PBLOCK base; /* base of heap area */
105 ULONG len; /* size of heap area */
114 virtual void* Malloc(size_t size);
115 virtual void* Realloc(void* pMem, size_t size);
116 virtual void Free(void* pMem);
117 virtual void GetLock(void);
118 virtual void FreeLock(void);
119 virtual int IsLocked(void);
120 virtual long Release(void);
121 virtual long AddRef(void);
123 inline BOOL CreateOk(void)
125 return m_hHeap != NULL;
132 int Getmem(size_t size);
133 int HeapAdd(void* ptr, size_t size);
134 void* Expand(void* block, size_t size);
137 HANDLE m_hHeap; // memory heap for this script
138 char m_FreeDummy[minAllocSize]; // dummy free block
139 PBLOCK m_pFreeList; // pointer to first block on free list
140 PBLOCK m_pRover; // roving pointer into the free list
141 HeapRec m_heaps[maxHeaps]; // list of all non-contiguous heap areas
142 int m_nHeaps; // no. of heaps in m_heaps
143 long m_lAllocSize; // current alloc size
144 long m_lRefCount; // number of current users
145 CRITICAL_SECTION m_cs; // access lock
151 // #define _DEBUG_MEM
153 #define ASSERT(f) if(!(f)) DebugBreak();
155 inline void MEMODS(char *str)
157 OutputDebugString(str);
158 OutputDebugString("\n");
161 inline void MEMODSlx(char *str, long x)
164 sprintf(szBuffer, "%s %lx\n", str, x);
165 OutputDebugString(szBuffer);
168 #define WALKHEAP() WalkHeap()
169 #define WALKHEAPTRACE() m_pRover = NULL; WalkHeap()
175 #define MEMODSlx(x, y)
177 #define WALKHEAPTRACE()
185 BOOL bRet = (NULL != (m_hHeap = HeapCreate(HEAP_NO_SERIALIZE,
186 lAllocStart, /* initial size of heap */
187 0))); /* no upper limit on size of heap */
190 InitializeCriticalSection(&m_cs);
200 ASSERT(HeapValidate(m_hHeap, HEAP_NO_SERIALIZE, NULL));
203 MemoryUsageMessage(NULL, 0, 0, 0);
205 DeleteCriticalSection(&m_cs);
206 BOOL bRet = HeapDestroy(m_hHeap);
210 void VMem::ReInit(void)
212 for(int index = 0; index < m_nHeaps; ++index)
213 HeapFree(m_hHeap, HEAP_NO_SERIALIZE, m_heaps[index].base);
218 void VMem::Init(void)
220 * Initialize the free list by placing a dummy zero-length block on it.
221 * Set the number of non-contiguous heaps to zero.
223 m_pFreeList = m_pRover = (PBLOCK)(&m_FreeDummy[minBlockSize]);
224 PSIZE(m_pFreeList) = SIZE(m_pFreeList) = 0;
225 PREV(m_pFreeList) = NEXT(m_pFreeList) = m_pFreeList;
228 m_lAllocSize = lAllocStart;
231 void* VMem::Malloc(size_t size)
236 * Adjust the real size of the block to be a multiple of sizeof(long), and add
237 * the overhead for the boundary tags. Disallow negative or zero sizes.
239 size_t realsize = (size < blockOverhead) ? minAllocSize : (size_t)ROUND_UP(size) + minBlockSize;
240 if((int)realsize < minAllocSize || size == 0)
244 * Start searching the free list at the rover. If we arrive back at rover without
245 * finding anything, allocate some memory from the heap and try again.
247 PBLOCK ptr = m_pRover; /* start searching at rover */
248 int loops = 2; /* allow two times through the loop */
250 size_t lsize = SIZE(ptr);
251 ASSERT((lsize&1)==0);
252 /* is block big enough? */
253 if(lsize >= realsize) {
254 /* if the remainder is too small, don't bother splitting the block. */
255 size_t rem = lsize - realsize;
256 if(rem < minAllocSize) {
258 m_pRover = NEXT(ptr);
260 /* Unlink the block from the free list. */
266 * The remainder is big enough to split off into a new block.
267 * Use the end of the block, resize the beginning of the block
268 * no need to change the free list.
274 /* Set the boundary tags to mark it as allocated. */
275 SetTags(ptr, lsize | 1);
276 return ((void *)ptr);
280 * This block was unsuitable. If we've gone through this list once already without
281 * finding anything, allocate some new memory from the heap and try again.
284 if(ptr == m_pRover) {
285 if(!(loops-- && Getmem(realsize))) {
293 void* VMem::Realloc(void* block, size_t size)
297 /* if size is zero, free the block. */
303 /* if block pointer is NULL, do a Malloc(). */
308 * Grow or shrink the block in place.
309 * if the block grows then the next block will be used if free
311 if(Expand(block, size) != NULL)
315 * adjust the real size of the block to be a multiple of sizeof(long), and add the
316 * overhead for the boundary tags. Disallow negative or zero sizes.
318 size_t realsize = (size < blockOverhead) ? minAllocSize : (size_t)ROUND_UP(size) + minBlockSize;
319 if((int)realsize < minAllocSize)
323 * see if the previous block is free, and is it big enough to cover the new size
324 * if merged with the current block.
326 PBLOCK ptr = (PBLOCK)block;
327 size_t cursize = SIZE(ptr) & ~1;
328 size_t psize = PSIZE(ptr);
329 if((psize&1) == 0 && (psize + cursize) >= realsize) {
330 PBLOCK prev = ptr - psize;
332 m_pRover = NEXT(prev);
334 /* Unlink the next block from the free list. */
337 /* Copy contents of old block to new location, make it the current block. */
338 memmove(prev, ptr, cursize);
339 cursize += psize; /* combine sizes */
342 size_t rem = cursize - realsize;
343 if(rem >= minAllocSize) {
345 * The remainder is big enough to be a new block. Set boundary
346 * tags for the resized block and the new block.
348 prev = ptr + realsize;
350 * add the new block to the free list.
351 * next block cannot be free
354 AddToFreeList(prev, m_pFreeList);
357 /* Set the boundary tags to mark it as allocated. */
358 SetTags(ptr, cursize | 1);
359 return ((void *)ptr);
362 /* Allocate a new block, copy the old to the new, and free the old. */
363 if((ptr = (PBLOCK)Malloc(size)) != NULL) {
364 memmove(ptr, block, cursize-minBlockSize);
367 return ((void *)ptr);
370 void VMem::Free(void* p)
374 /* Ignore null pointer. */
378 PBLOCK ptr = (PBLOCK)p;
380 /* Check for attempt to free a block that's already free. */
381 size_t size = SIZE(ptr);
383 MEMODSlx("Attempt to free previously freed block", (long)p);
386 size &= ~1; /* remove allocated tag */
388 /* if previous block is free, add this block to it. */
390 size_t psize = PSIZE(ptr);
392 ptr -= psize; /* point to previous block */
393 size += psize; /* merge the sizes of the two blocks */
394 linked = TRUE; /* it's already on the free list */
397 /* if the next physical block is free, merge it with this block. */
398 PBLOCK next = ptr + size; /* point to next physical block */
399 size_t nsize = SIZE(next);
401 /* block is free move rover if needed */
403 m_pRover = NEXT(next);
405 /* unlink the next block from the free list. */
408 /* merge the sizes of this block and the next block. */
412 /* Set the boundary tags for the block; */
415 /* Link the block to the head of the free list. */
417 AddToFreeList(ptr, m_pFreeList);
421 void VMem::GetLock(void)
423 EnterCriticalSection(&m_cs);
426 void VMem::FreeLock(void)
428 LeaveCriticalSection(&m_cs);
431 int VMem::IsLocked(void)
434 /* XXX TryEnterCriticalSection() is not available in some versions
435 * of Windows 95. Since this code is not used anywhere yet, we
436 * skirt the issue for now. */
437 BOOL bAccessed = TryEnterCriticalSection(&m_cs);
439 LeaveCriticalSection(&m_cs);
443 ASSERT(0); /* alarm bells for when somebody calls this */
449 long VMem::Release(void)
451 long lCount = InterlockedDecrement(&m_lRefCount);
457 long VMem::AddRef(void)
459 long lCount = InterlockedIncrement(&m_lRefCount);
464 int VMem::Getmem(size_t requestSize)
465 { /* returns -1 is successful 0 if not */
468 /* Round up size to next multiple of 64K. */
469 size_t size = (size_t)ROUND_UP64K(requestSize);
472 * if the size requested is smaller than our current allocation size
475 if(size < (unsigned long)m_lAllocSize)
478 /* Update the size to allocate on the next request */
479 if(m_lAllocSize != lAllocMax)
483 /* Expand the last allocated heap */
484 ptr = HeapReAlloc(m_hHeap, HEAP_REALLOC_IN_PLACE_ONLY|HEAP_ZERO_MEMORY|HEAP_NO_SERIALIZE,
485 m_heaps[m_nHeaps-1].base,
486 m_heaps[m_nHeaps-1].len + size);
488 HeapAdd(((char*)ptr) + m_heaps[m_nHeaps-1].len, size);
494 * if we didn't expand a block to cover the requested size
495 * allocate a new Heap
496 * the size of this block must include the additional dummy tags at either end
497 * the above ROUND_UP64K may not have added any memory to include this.
499 if(size == requestSize)
500 size = (size_t)ROUND_UP64K(requestSize+(sizeofTag*2));
502 ptr = HeapAlloc(m_hHeap, HEAP_ZERO_MEMORY|HEAP_NO_SERIALIZE, size);
504 MEMODSlx("HeapAlloc failed on size!!!", size);
512 int VMem::HeapAdd(void *p, size_t size)
513 { /* if the block can be succesfully added to the heap, returns 0; otherwise -1. */
516 /* Check size, then round size down to next long word boundary. */
517 if(size < minAllocSize)
520 size = (size_t)ROUND_DOWN(size);
521 PBLOCK ptr = (PBLOCK)p;
524 * Search for another heap area that's contiguous with the bottom of this new area.
525 * (It should be extremely unusual to find one that's contiguous with the top).
527 for(index = 0; index < m_nHeaps; ++index) {
528 if(ptr == m_heaps[index].base + (int)m_heaps[index].len) {
530 * The new block is contiguous with a previously allocated heap area. Add its
531 * length to that of the previous heap. Merge it with the the dummy end-of-heap
532 * area marker of the previous heap.
534 m_heaps[index].len += size;
539 if(index == m_nHeaps) {
540 /* The new block is not contiguous. Add it to the heap list. */
541 if(m_nHeaps == maxHeaps) {
542 return -1; /* too many non-contiguous heaps */
544 m_heaps[m_nHeaps].base = ptr;
545 m_heaps[m_nHeaps].len = size;
549 * Reserve the first LONG in the block for the ending boundary tag of a dummy
550 * block at the start of the heap area.
552 size -= minBlockSize;
554 PSIZE(ptr) = 1; /* mark the dummy previous block as allocated */
558 * Convert the heap to one large block. Set up its boundary tags, and those of
559 * marker block after it. The marker block before the heap will already have
560 * been set up if this heap is not contiguous with the end of another heap.
562 SetTags(ptr, size | 1);
563 PBLOCK next = ptr + size; /* point to dummy end block */
564 SIZE(next) = 1; /* mark the dummy end block as allocated */
567 * Link the block to the start of the free list by calling free().
568 * This will merge the block with any adjacent free blocks.
575 void* VMem::Expand(void* block, size_t size)
578 * Adjust the size of the block to be a multiple of sizeof(long), and add the
579 * overhead for the boundary tags. Disallow negative or zero sizes.
581 size_t realsize = (size < blockOverhead) ? minAllocSize : (size_t)ROUND_UP(size) + minBlockSize;
582 if((int)realsize < minAllocSize || size == 0)
585 PBLOCK ptr = (PBLOCK)block;
587 /* if the current size is the same as requested, do nothing. */
588 size_t cursize = SIZE(ptr) & ~1;
589 if(cursize == realsize) {
593 /* if the block is being shrunk, convert the remainder of the block into a new free block. */
594 if(realsize <= cursize) {
595 size_t nextsize = cursize - realsize; /* size of new remainder block */
596 if(nextsize >= minAllocSize) {
599 * Set boundary tags for the resized block and the new block.
601 SetTags(ptr, realsize | 1);
605 * add the new block to the free list.
606 * call Free to merge this block with next block if free
608 SetTags(ptr, nextsize | 1);
615 PBLOCK next = ptr + cursize;
616 size_t nextsize = SIZE(next);
618 /* Check the next block for consistency.*/
619 if((nextsize&1) == 0 && (nextsize + cursize) >= realsize) {
621 * The next block is free and big enough. Add the part that's needed
622 * to our block, and split the remainder off into a new block.
625 m_pRover = NEXT(next);
627 /* Unlink the next block from the free list. */
629 cursize += nextsize; /* combine sizes */
631 size_t rem = cursize - realsize; /* size of remainder */
632 if(rem >= minAllocSize) {
634 * The remainder is big enough to be a new block.
635 * Set boundary tags for the resized block and the new block.
637 next = ptr + realsize;
639 * add the new block to the free list.
640 * next block cannot be free
643 AddToFreeList(next, m_pFreeList);
646 /* Set the boundary tags to mark it as allocated. */
647 SetTags(ptr, cursize | 1);
648 return ((void *)ptr);
654 #define LOG_FILENAME ".\\MemLog.txt"
656 void MemoryUsageMessage(char *str, long x, long y, int c)
661 m_pLog = fopen(LOG_FILENAME, "w");
662 sprintf(szBuffer, str, x, y, c);
663 fputs(szBuffer, m_pLog);
672 void VMem::WalkHeap(void)
675 MemoryUsageMessage("VMem heaps used %d\n", m_nHeaps, 0, 0);
678 /* Walk all the heaps - verify structures */
679 for(int index = 0; index < m_nHeaps; ++index) {
680 PBLOCK ptr = m_heaps[index].base;
681 size_t size = m_heaps[index].len;
682 ASSERT(HeapValidate(m_hHeap, HEAP_NO_SERIALIZE, p));
684 /* set over reserved header block */
685 size -= minBlockSize;
687 PBLOCK pLast = ptr + size;
688 ASSERT(PSIZE(ptr) == 1); /* dummy previous block is allocated */
689 ASSERT(SIZE(pLast) == 1); /* dummy next block is allocated */
691 ASSERT(ptr > m_heaps[index].base);
692 size_t cursize = SIZE(ptr) & ~1;
693 ASSERT((PSIZE(ptr+cursize) & ~1) == cursize);
695 MemoryUsageMessage("Memory Block %08x: Size %08x %c\n", (long)ptr, cursize, (SIZE(p)&1) ? 'x' : ' ');
698 /* this block is on the free list */
699 PBLOCK tmp = NEXT(ptr);
701 ASSERT((SIZE(tmp)&1)==0);
702 if(tmp == m_pFreeList)
708 MemoryUsageMessage("Memory Block %08x: Size %08x free but not in free list\n", (long)ptr, cursize, 0);
715 MemoryUsageMessage(NULL, 0, 0, 0);
720 #endif /* ___VMEM_H_INC___ */