This is a live mirror of the Perl 5 development currently hosted at https://github.com/perl/perl5
Bump Data::Dumper version
[perl5.git] / win32 / vmem.h
1 /* vmem.h
2  *
3  * (c) 1999 Microsoft Corporation. All rights reserved. 
4  * Portions (c) 1999 ActiveState Tool Corp, http://www.ActiveState.com/
5  *
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.
8  *
9  * Options:
10  *
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)
18  *
19  */
20
21 #ifndef ___VMEM_H_INC___
22 #define ___VMEM_H_INC___
23
24 #define _USE_MSVCRT_MEM_ALLOC
25 #define _USE_LINKED_LIST
26
27 // #define _USE_BUDDY_BLOCKS
28
29 // #define _DEBUG_MEM
30 #ifdef _DEBUG_MEM
31 #define ASSERT(f) if(!(f)) DebugBreak();
32
33 inline void MEMODS(char *str)
34 {
35     OutputDebugString(str);
36     OutputDebugString("\n");
37 }
38
39 inline void MEMODSlx(char *str, long x)
40 {
41     char szBuffer[512]; 
42     sprintf(szBuffer, "%s %lx\n", str, x);
43     OutputDebugString(szBuffer);
44 }
45
46 #define WALKHEAP() WalkHeap(0)
47 #define WALKHEAPTRACE() WalkHeap(1)
48
49 #else
50
51 #define ASSERT(f)
52 #define MEMODS(x)
53 #define MEMODSlx(x, y)
54 #define WALKHEAP()
55 #define WALKHEAPTRACE()
56
57 #endif
58
59 #ifdef _USE_MSVCRT_MEM_ALLOC
60
61 #ifndef _USE_LINKED_LIST
62 // #define _USE_LINKED_LIST
63 #endif
64
65 /* 
66  * Pass all memory requests through to the compiler's msvcr*.dll.
67  * Optionaly track by using a doubly linked header.
68  */
69
70 #ifdef _USE_LINKED_LIST
71 class VMem;
72 typedef struct _MemoryBlockHeader* PMEMORY_BLOCK_HEADER;
73 typedef struct _MemoryBlockHeader {
74     PMEMORY_BLOCK_HEADER    pNext;
75     PMEMORY_BLOCK_HEADER    pPrev;
76     VMem *owner;
77 } MEMORY_BLOCK_HEADER, *PMEMORY_BLOCK_HEADER;
78 #endif
79
80 class VMem
81 {
82 public:
83     VMem();
84     ~VMem();
85     void* Malloc(size_t size);
86     void* Realloc(void* pMem, size_t size);
87     void Free(void* pMem);
88     void GetLock(void);
89     void FreeLock(void);
90     int IsLocked(void);
91     long Release(void);
92     long AddRef(void);
93
94     inline BOOL CreateOk(void)
95     {
96         return TRUE;
97     };
98
99 protected:
100 #ifdef _USE_LINKED_LIST
101     void LinkBlock(PMEMORY_BLOCK_HEADER ptr)
102     {
103         PMEMORY_BLOCK_HEADER next = m_Dummy.pNext;
104         m_Dummy.pNext = ptr;
105         ptr->pPrev = &m_Dummy;
106         ptr->pNext = next;
107         ptr->owner = this;
108         next->pPrev = ptr;
109     }
110     void UnlinkBlock(PMEMORY_BLOCK_HEADER ptr)
111     {
112         PMEMORY_BLOCK_HEADER next = ptr->pNext;
113         PMEMORY_BLOCK_HEADER prev = ptr->pPrev;
114         prev->pNext = next;
115         next->pPrev = prev;
116     }
117
118     MEMORY_BLOCK_HEADER m_Dummy;
119     CRITICAL_SECTION    m_cs;           // access lock
120 #endif
121
122     long                m_lRefCount;    // number of current users
123 };
124
125 VMem::VMem()
126 {
127     m_lRefCount = 1;
128 #ifdef _USE_LINKED_LIST
129     InitializeCriticalSection(&m_cs);
130     m_Dummy.pNext = m_Dummy.pPrev =  &m_Dummy;
131     m_Dummy.owner = this;
132 #endif
133 }
134
135 VMem::~VMem(void)
136 {
137 #ifdef _USE_LINKED_LIST
138     while (m_Dummy.pNext != &m_Dummy) {
139         Free(m_Dummy.pNext+1);
140     }
141     DeleteCriticalSection(&m_cs);
142 #endif
143 }
144
145 void* VMem::Malloc(size_t size)
146 {
147 #ifdef _USE_LINKED_LIST
148     GetLock();
149     PMEMORY_BLOCK_HEADER ptr = (PMEMORY_BLOCK_HEADER)malloc(size+sizeof(MEMORY_BLOCK_HEADER));
150     if (!ptr) {
151         FreeLock();
152         return NULL;
153     }
154     LinkBlock(ptr);
155     FreeLock();
156     return (ptr+1);
157 #else
158     return malloc(size);
159 #endif
160 }
161
162 void* VMem::Realloc(void* pMem, size_t size)
163 {
164 #ifdef _USE_LINKED_LIST
165     if (!pMem)
166         return Malloc(size);
167
168     if (!size) {
169         Free(pMem);
170         return NULL;
171     }
172
173     GetLock();
174     PMEMORY_BLOCK_HEADER ptr = (PMEMORY_BLOCK_HEADER)(((char*)pMem)-sizeof(MEMORY_BLOCK_HEADER));
175     UnlinkBlock(ptr);
176     ptr = (PMEMORY_BLOCK_HEADER)realloc(ptr, size+sizeof(MEMORY_BLOCK_HEADER));
177     if (!ptr) {
178         FreeLock();
179         return NULL;
180     }
181     LinkBlock(ptr);
182     FreeLock();
183
184     return (ptr+1);
185 #else
186     return realloc(pMem, size);
187 #endif
188 }
189
190 void VMem::Free(void* pMem)
191 {
192 #ifdef _USE_LINKED_LIST
193     if (pMem) {
194         PMEMORY_BLOCK_HEADER ptr = (PMEMORY_BLOCK_HEADER)(((char*)pMem)-sizeof(MEMORY_BLOCK_HEADER));
195         if (ptr->owner != this) {
196             if (ptr->owner) {
197 #if 1
198                 int *nowhere = NULL;
199                 Perl_warn_nocontext("Free to wrong pool %p not %p",this,ptr->owner);
200                 *nowhere = 0; /* this segfault is deliberate, 
201                                  so you can see the stack trace */
202 #else
203                 ptr->owner->Free(pMem); 
204 #endif
205             }
206             return;
207         }
208         GetLock();
209         UnlinkBlock(ptr);
210         ptr->owner = NULL;
211         free(ptr);
212         FreeLock();
213     }
214 #else /*_USE_LINKED_LIST*/
215     free(pMem);
216 #endif
217 }
218
219 void VMem::GetLock(void)
220 {
221 #ifdef _USE_LINKED_LIST
222     EnterCriticalSection(&m_cs);
223 #endif
224 }
225
226 void VMem::FreeLock(void)
227 {
228 #ifdef _USE_LINKED_LIST
229     LeaveCriticalSection(&m_cs);
230 #endif
231 }
232
233 int VMem::IsLocked(void)
234 {
235 #if 0
236     /* XXX TryEnterCriticalSection() is not available in some versions
237      * of Windows 95.  Since this code is not used anywhere yet, we 
238      * skirt the issue for now. */
239     BOOL bAccessed = TryEnterCriticalSection(&m_cs);
240     if(bAccessed) {
241         LeaveCriticalSection(&m_cs);
242     }
243     return !bAccessed;
244 #else
245     ASSERT(0);  /* alarm bells for when somebody calls this */
246     return 0;
247 #endif
248 }
249
250 long VMem::Release(void)
251 {
252     long lCount = InterlockedDecrement(&m_lRefCount);
253     if(!lCount)
254         delete this;
255     return lCount;
256 }
257
258 long VMem::AddRef(void)
259 {
260     long lCount = InterlockedIncrement(&m_lRefCount);
261     return lCount;
262 }
263
264 #else   /* _USE_MSVCRT_MEM_ALLOC */
265
266 /*
267  * Knuth's boundary tag algorithm Vol #1, Page 440.
268  *
269  * Each block in the heap has tag words before and after it,
270  *  TAG
271  *  block
272  *  TAG
273  * The size is stored in these tags as a long word, and includes the 8 bytes
274  * of overhead that the boundary tags consume.  Blocks are allocated on long
275  * word boundaries, so the size is always multiples of long words.  When the
276  * block is allocated, bit 0, (the tag bit), of the size is set to 1.  When 
277  * a block is freed, it is merged with adjacent free blocks, and the tag bit
278  * is set to 0.
279  *
280  * A linked list is used to manage the free list. The first two long words of
281  * the block contain double links.  These links are only valid when the block
282  * is freed, therefore space needs to be reserved for them.  Thus, the minimum
283  * block size (not counting the tags) is 8 bytes.
284  *
285  * Since memory allocation may occur on a single threaded, explicit locks are not
286  * provided.
287  * 
288  */
289
290 const long lAllocStart = 0x00020000; /* start at 128K */
291 const long minBlockSize = sizeof(void*)*2;
292 const long sizeofTag = sizeof(long);
293 const long blockOverhead = sizeofTag*2;
294 const long minAllocSize = minBlockSize+blockOverhead;
295 #ifdef _USE_BUDDY_BLOCKS
296 const long lSmallBlockSize = 1024;
297 const size_t nListEntries = ((lSmallBlockSize-minAllocSize)/sizeof(long));
298
299 inline size_t CalcEntry(size_t size)
300 {
301     ASSERT((size&(sizeof(long)-1)) == 0);
302     return ((size - minAllocSize) / sizeof(long));
303 }
304 #endif
305
306 typedef BYTE* PBLOCK;   /* pointer to a memory block */
307
308 /*
309  * Macros for accessing hidden fields in a memory block:
310  *
311  * SIZE     size of this block (tag bit 0 is 1 if block is allocated)
312  * PSIZE    size of previous physical block
313  */
314
315 #define SIZE(block)     (*(ULONG*)(((PBLOCK)(block))-sizeofTag))
316 #define PSIZE(block)    (*(ULONG*)(((PBLOCK)(block))-(blockOverhead)))
317 inline void SetTags(PBLOCK block, long size)
318 {
319     SIZE(block) = size;
320     PSIZE(block+(size&~1)) = size;
321 }
322
323 /*
324  * Free list pointers
325  * PREV pointer to previous block
326  * NEXT pointer to next block
327  */
328
329 #define PREV(block)     (*(PBLOCK*)(block))
330 #define NEXT(block)     (*(PBLOCK*)((block)+sizeof(PBLOCK)))
331 inline void SetLink(PBLOCK block, PBLOCK prev, PBLOCK next)
332 {
333     PREV(block) = prev;
334     NEXT(block) = next;
335 }
336 inline void Unlink(PBLOCK p)
337 {
338     PBLOCK next = NEXT(p);
339     PBLOCK prev = PREV(p);
340     NEXT(prev) = next;
341     PREV(next) = prev;
342 }
343 #ifndef _USE_BUDDY_BLOCKS
344 inline void AddToFreeList(PBLOCK block, PBLOCK pInList)
345 {
346     PBLOCK next = NEXT(pInList);
347     NEXT(pInList) = block;
348     SetLink(block, pInList, next);
349     PREV(next) = block;
350 }
351 #endif
352
353 /* Macro for rounding up to the next sizeof(long) */
354 #define ROUND_UP(n)     (((ULONG)(n)+sizeof(long)-1)&~(sizeof(long)-1))
355 #define ROUND_UP64K(n)  (((ULONG)(n)+0x10000-1)&~(0x10000-1))
356 #define ROUND_DOWN(n)   ((ULONG)(n)&~(sizeof(long)-1))
357
358 /*
359  * HeapRec - a list of all non-contiguous heap areas
360  *
361  * Each record in this array contains information about a non-contiguous heap area.
362  */
363
364 const int maxHeaps = 32; /* 64 was overkill */
365 const long lAllocMax   = 0x80000000; /* max size of allocation */
366
367 #ifdef _USE_BUDDY_BLOCKS
368 typedef struct _FreeListEntry
369 {
370     BYTE    Dummy[minAllocSize];        // dummy free block
371 } FREE_LIST_ENTRY, *PFREE_LIST_ENTRY;
372 #endif
373
374 #ifndef _USE_BUDDY_BLOCKS
375 #define USE_BIGBLOCK_ALLOC
376 #endif
377 /*
378  * performance tuning
379  * Use VirtualAlloc() for blocks bigger than nMaxHeapAllocSize since
380  * Windows 95/98/Me have heap managers that are designed for memory 
381  * blocks smaller than four megabytes.
382  */
383
384 #ifdef USE_BIGBLOCK_ALLOC
385 const int nMaxHeapAllocSize = (1024*512);  /* don't allocate anything larger than this from the heap */
386 #endif
387
388 typedef struct _HeapRec
389 {
390     PBLOCK      base;   /* base of heap area */
391     ULONG       len;    /* size of heap area */
392 #ifdef USE_BIGBLOCK_ALLOC
393     BOOL        bBigBlock;  /* was allocate using VirtualAlloc */
394 #endif
395 } HeapRec;
396
397 class VMem
398 {
399 public:
400     VMem();
401     ~VMem();
402     void* Malloc(size_t size);
403     void* Realloc(void* pMem, size_t size);
404     void Free(void* pMem);
405     void GetLock(void);
406     void FreeLock(void);
407     int IsLocked(void);
408     long Release(void);
409     long AddRef(void);
410
411     inline BOOL CreateOk(void)
412     {
413 #ifdef _USE_BUDDY_BLOCKS
414         return TRUE;
415 #else
416         return m_hHeap != NULL;
417 #endif
418     };
419
420     void ReInit(void);
421
422 protected:
423     void Init(void);
424     int Getmem(size_t size);
425
426     int HeapAdd(void* ptr, size_t size
427 #ifdef USE_BIGBLOCK_ALLOC
428         , BOOL bBigBlock
429 #endif
430     );
431
432     void* Expand(void* block, size_t size);
433
434 #ifdef _USE_BUDDY_BLOCKS
435     inline PBLOCK GetFreeListLink(int index)
436     {
437         if (index >= nListEntries)
438             index = nListEntries-1;
439         return &m_FreeList[index].Dummy[sizeofTag];
440     }
441     inline PBLOCK GetOverSizeFreeList(void)
442     {
443         return &m_FreeList[nListEntries-1].Dummy[sizeofTag];
444     }
445     inline PBLOCK GetEOLFreeList(void)
446     {
447         return &m_FreeList[nListEntries].Dummy[sizeofTag];
448     }
449
450     void AddToFreeList(PBLOCK block, size_t size)
451     {
452         PBLOCK pFreeList = GetFreeListLink(CalcEntry(size));
453         PBLOCK next = NEXT(pFreeList);
454         NEXT(pFreeList) = block;
455         SetLink(block, pFreeList, next);
456         PREV(next) = block;
457     }
458 #endif
459     inline size_t CalcAllocSize(size_t size)
460     {
461         /*
462          * Adjust the real size of the block to be a multiple of sizeof(long), and add
463          * the overhead for the boundary tags.  Disallow negative or zero sizes.
464          */
465         return (size < minBlockSize) ? minAllocSize : (size_t)ROUND_UP(size) + blockOverhead;
466     }
467
468 #ifdef _USE_BUDDY_BLOCKS
469     FREE_LIST_ENTRY     m_FreeList[nListEntries+1];     // free list with dummy end of list entry as well
470 #else
471     HANDLE              m_hHeap;                    // memory heap for this script
472     char                m_FreeDummy[minAllocSize];  // dummy free block
473     PBLOCK              m_pFreeList;                // pointer to first block on free list
474 #endif
475     PBLOCK              m_pRover;                   // roving pointer into the free list
476     HeapRec             m_heaps[maxHeaps];          // list of all non-contiguous heap areas 
477     int                 m_nHeaps;                   // no. of heaps in m_heaps 
478     long                m_lAllocSize;               // current alloc size
479     long                m_lRefCount;                // number of current users
480     CRITICAL_SECTION    m_cs;                       // access lock
481
482 #ifdef _DEBUG_MEM
483     void WalkHeap(int complete);
484     void MemoryUsageMessage(char *str, long x, long y, int c);
485     FILE*               m_pLog;
486 #endif
487 };
488
489 VMem::VMem()
490 {
491     m_lRefCount = 1;
492 #ifndef _USE_BUDDY_BLOCKS
493     BOOL bRet = (NULL != (m_hHeap = HeapCreate(HEAP_NO_SERIALIZE,
494                                 lAllocStart,    /* initial size of heap */
495                                 0)));           /* no upper limit on size of heap */
496     ASSERT(bRet);
497 #endif
498
499     InitializeCriticalSection(&m_cs);
500 #ifdef _DEBUG_MEM
501     m_pLog = 0;
502 #endif
503
504     Init();
505 }
506
507 VMem::~VMem(void)
508 {
509 #ifndef _USE_BUDDY_BLOCKS
510     ASSERT(HeapValidate(m_hHeap, HEAP_NO_SERIALIZE, NULL));
511 #endif
512     WALKHEAPTRACE();
513
514     DeleteCriticalSection(&m_cs);
515 #ifdef _USE_BUDDY_BLOCKS
516     for(int index = 0; index < m_nHeaps; ++index) {
517         VirtualFree(m_heaps[index].base, 0, MEM_RELEASE);
518     }
519 #else /* !_USE_BUDDY_BLOCKS */
520 #ifdef USE_BIGBLOCK_ALLOC
521     for(int index = 0; index < m_nHeaps; ++index) {
522         if (m_heaps[index].bBigBlock) {
523             VirtualFree(m_heaps[index].base, 0, MEM_RELEASE);
524         }
525     }
526 #endif
527     BOOL bRet = HeapDestroy(m_hHeap);
528     ASSERT(bRet);
529 #endif /* _USE_BUDDY_BLOCKS */
530 }
531
532 void VMem::ReInit(void)
533 {
534     for(int index = 0; index < m_nHeaps; ++index) {
535 #ifdef _USE_BUDDY_BLOCKS
536         VirtualFree(m_heaps[index].base, 0, MEM_RELEASE);
537 #else
538 #ifdef USE_BIGBLOCK_ALLOC
539         if (m_heaps[index].bBigBlock) {
540             VirtualFree(m_heaps[index].base, 0, MEM_RELEASE);
541         }
542         else
543 #endif
544             HeapFree(m_hHeap, HEAP_NO_SERIALIZE, m_heaps[index].base);
545 #endif /* _USE_BUDDY_BLOCKS */
546     }
547
548     Init();
549 }
550
551 void VMem::Init(void)
552 {
553 #ifdef _USE_BUDDY_BLOCKS
554     PBLOCK pFreeList;
555     /*
556      * Initialize the free list by placing a dummy zero-length block on it.
557      * Set the end of list marker.
558      * Set the number of non-contiguous heaps to zero.
559      * Set the next allocation size.
560      */
561     for (int index = 0; index < nListEntries; ++index) {
562         pFreeList = GetFreeListLink(index);
563         SIZE(pFreeList) = PSIZE(pFreeList+minAllocSize) = 0;
564         PREV(pFreeList) = NEXT(pFreeList) = pFreeList;
565     }
566     pFreeList = GetEOLFreeList();
567     SIZE(pFreeList) = PSIZE(pFreeList+minAllocSize) = 0;
568     PREV(pFreeList) = NEXT(pFreeList) = NULL;
569     m_pRover = GetOverSizeFreeList();
570 #else
571     /*
572      * Initialize the free list by placing a dummy zero-length block on it.
573      * Set the number of non-contiguous heaps to zero.
574      */
575     m_pFreeList = m_pRover = (PBLOCK)(&m_FreeDummy[sizeofTag]);
576     PSIZE(m_pFreeList+minAllocSize) = SIZE(m_pFreeList) = 0;
577     PREV(m_pFreeList) = NEXT(m_pFreeList) = m_pFreeList;
578 #endif
579
580     m_nHeaps = 0;
581     m_lAllocSize = lAllocStart;
582 }
583
584 void* VMem::Malloc(size_t size)
585 {
586     WALKHEAP();
587
588     PBLOCK ptr;
589     size_t lsize, rem;
590     /*
591      * Disallow negative or zero sizes.
592      */
593     size_t realsize = CalcAllocSize(size);
594     if((int)realsize < minAllocSize || size == 0)
595         return NULL;
596
597 #ifdef _USE_BUDDY_BLOCKS
598     /*
599      * Check the free list of small blocks if this is free use it
600      * Otherwise check the rover if it has no blocks then
601      * Scan the free list entries use the first free block
602      * split the block if needed, stop at end of list marker
603      */
604     {
605         int index = CalcEntry(realsize);
606         if (index < nListEntries-1) {
607             ptr = GetFreeListLink(index);
608             lsize = SIZE(ptr);
609             if (lsize >= realsize) {
610                 rem = lsize - realsize;
611                 if(rem < minAllocSize) {
612                     /* Unlink the block from the free list. */
613                     Unlink(ptr);
614                 }
615                 else {
616                     /*
617                      * split the block
618                      * The remainder is big enough to split off into a new block.
619                      * Use the end of the block, resize the beginning of the block
620                      * no need to change the free list.
621                      */
622                     SetTags(ptr, rem);
623                     ptr += SIZE(ptr);
624                     lsize = realsize;
625                 }
626                 SetTags(ptr, lsize | 1);
627                 return ptr;
628             }
629             ptr = m_pRover;
630             lsize = SIZE(ptr);
631             if (lsize >= realsize) {
632                 rem = lsize - realsize;
633                 if(rem < minAllocSize) {
634                     /* Unlink the block from the free list. */
635                     Unlink(ptr);
636                 }
637                 else {
638                     /*
639                      * split the block
640                      * The remainder is big enough to split off into a new block.
641                      * Use the end of the block, resize the beginning of the block
642                      * no need to change the free list.
643                      */
644                     SetTags(ptr, rem);
645                     ptr += SIZE(ptr);
646                     lsize = realsize;
647                 }
648                 SetTags(ptr, lsize | 1);
649                 return ptr;
650             }
651             ptr = GetFreeListLink(index+1);
652             while (NEXT(ptr)) {
653                 lsize = SIZE(ptr);
654                 if (lsize >= realsize) {
655                     size_t rem = lsize - realsize;
656                     if(rem < minAllocSize) {
657                         /* Unlink the block from the free list. */
658                         Unlink(ptr);
659                     }
660                     else {
661                         /*
662                          * split the block
663                          * The remainder is big enough to split off into a new block.
664                          * Use the end of the block, resize the beginning of the block
665                          * no need to change the free list.
666                          */
667                         SetTags(ptr, rem);
668                         ptr += SIZE(ptr);
669                         lsize = realsize;
670                     }
671                     SetTags(ptr, lsize | 1);
672                     return ptr;
673                 }
674                 ptr += sizeof(FREE_LIST_ENTRY);
675             }
676         }
677     }
678 #endif
679
680     /*
681      * Start searching the free list at the rover.  If we arrive back at rover without
682      * finding anything, allocate some memory from the heap and try again.
683      */
684     ptr = m_pRover;     /* start searching at rover */
685     int loops = 2;      /* allow two times through the loop  */
686     for(;;) {
687         lsize = SIZE(ptr);
688         ASSERT((lsize&1)==0);
689         /* is block big enough? */
690         if(lsize >= realsize) { 
691             /* if the remainder is too small, don't bother splitting the block. */
692             rem = lsize - realsize;
693             if(rem < minAllocSize) {
694                 if(m_pRover == ptr)
695                     m_pRover = NEXT(ptr);
696
697                 /* Unlink the block from the free list. */
698                 Unlink(ptr);
699             }
700             else {
701                 /*
702                  * split the block
703                  * The remainder is big enough to split off into a new block.
704                  * Use the end of the block, resize the beginning of the block
705                  * no need to change the free list.
706                  */
707                 SetTags(ptr, rem);
708                 ptr += SIZE(ptr);
709                 lsize = realsize;
710             }
711             /* Set the boundary tags to mark it as allocated. */
712             SetTags(ptr, lsize | 1);
713             return ((void *)ptr);
714         }
715
716         /*
717          * This block was unsuitable.  If we've gone through this list once already without
718          * finding anything, allocate some new memory from the heap and try again.
719          */
720         ptr = NEXT(ptr);
721         if(ptr == m_pRover) {
722             if(!(loops-- && Getmem(realsize))) {
723                 return NULL;
724             }
725             ptr = m_pRover;
726         }
727     }
728 }
729
730 void* VMem::Realloc(void* block, size_t size)
731 {
732     WALKHEAP();
733
734     /* if size is zero, free the block. */
735     if(size == 0) {
736         Free(block);
737         return (NULL);
738     }
739
740     /* if block pointer is NULL, do a Malloc(). */
741     if(block == NULL)
742         return Malloc(size);
743
744     /*
745      * Grow or shrink the block in place.
746      * if the block grows then the next block will be used if free
747      */
748     if(Expand(block, size) != NULL)
749         return block;
750
751     size_t realsize = CalcAllocSize(size);
752     if((int)realsize < minAllocSize)
753         return NULL;
754
755     /*
756      * see if the previous block is free, and is it big enough to cover the new size
757      * if merged with the current block.
758      */
759     PBLOCK ptr = (PBLOCK)block;
760     size_t cursize = SIZE(ptr) & ~1;
761     size_t psize = PSIZE(ptr);
762     if((psize&1) == 0 && (psize + cursize) >= realsize) {
763         PBLOCK prev = ptr - psize;
764         if(m_pRover == prev)
765             m_pRover = NEXT(prev);
766
767         /* Unlink the next block from the free list. */
768         Unlink(prev);
769
770         /* Copy contents of old block to new location, make it the current block. */
771         memmove(prev, ptr, cursize);
772         cursize += psize;       /* combine sizes */
773         ptr = prev;
774
775         size_t rem = cursize - realsize;
776         if(rem >= minAllocSize) {
777             /*
778              * The remainder is big enough to be a new block.  Set boundary
779              * tags for the resized block and the new block.
780              */
781             prev = ptr + realsize;
782             /*
783              * add the new block to the free list.
784              * next block cannot be free
785              */
786             SetTags(prev, rem);
787 #ifdef _USE_BUDDY_BLOCKS
788             AddToFreeList(prev, rem);
789 #else
790             AddToFreeList(prev, m_pFreeList);
791 #endif
792             cursize = realsize;
793         }
794         /* Set the boundary tags to mark it as allocated. */
795         SetTags(ptr, cursize | 1);
796         return ((void *)ptr);
797     }
798
799     /* Allocate a new block, copy the old to the new, and free the old. */
800     if((ptr = (PBLOCK)Malloc(size)) != NULL) {
801         memmove(ptr, block, cursize-blockOverhead);
802         Free(block);
803     }
804     return ((void *)ptr);
805 }
806
807 void VMem::Free(void* p)
808 {
809     WALKHEAP();
810
811     /* Ignore null pointer. */
812     if(p == NULL)
813         return;
814
815     PBLOCK ptr = (PBLOCK)p;
816
817     /* Check for attempt to free a block that's already free. */
818     size_t size = SIZE(ptr);
819     if((size&1) == 0) {
820         MEMODSlx("Attempt to free previously freed block", (long)p);
821         return;
822     }
823     size &= ~1; /* remove allocated tag */
824
825     /* if previous block is free, add this block to it. */
826 #ifndef _USE_BUDDY_BLOCKS
827     int linked = FALSE;
828 #endif
829     size_t psize = PSIZE(ptr);
830     if((psize&1) == 0) {
831         ptr -= psize;   /* point to previous block */
832         size += psize;  /* merge the sizes of the two blocks */
833 #ifdef _USE_BUDDY_BLOCKS
834         Unlink(ptr);
835 #else
836         linked = TRUE;  /* it's already on the free list */
837 #endif
838     }
839
840     /* if the next physical block is free, merge it with this block. */
841     PBLOCK next = ptr + size;   /* point to next physical block */
842     size_t nsize = SIZE(next);
843     if((nsize&1) == 0) {
844         /* block is free move rover if needed */
845         if(m_pRover == next)
846             m_pRover = NEXT(next);
847
848         /* unlink the next block from the free list. */
849         Unlink(next);
850
851         /* merge the sizes of this block and the next block. */
852         size += nsize;
853     }
854
855     /* Set the boundary tags for the block; */
856     SetTags(ptr, size);
857
858     /* Link the block to the head of the free list. */
859 #ifdef _USE_BUDDY_BLOCKS
860         AddToFreeList(ptr, size);
861 #else
862     if(!linked) {
863         AddToFreeList(ptr, m_pFreeList);
864     }
865 #endif
866 }
867
868 void VMem::GetLock(void)
869 {
870     EnterCriticalSection(&m_cs);
871 }
872
873 void VMem::FreeLock(void)
874 {
875     LeaveCriticalSection(&m_cs);
876 }
877
878 int VMem::IsLocked(void)
879 {
880 #if 0
881     /* XXX TryEnterCriticalSection() is not available in some versions
882      * of Windows 95.  Since this code is not used anywhere yet, we 
883      * skirt the issue for now. */
884     BOOL bAccessed = TryEnterCriticalSection(&m_cs);
885     if(bAccessed) {
886         LeaveCriticalSection(&m_cs);
887     }
888     return !bAccessed;
889 #else
890     ASSERT(0);  /* alarm bells for when somebody calls this */
891     return 0;
892 #endif
893 }
894
895
896 long VMem::Release(void)
897 {
898     long lCount = InterlockedDecrement(&m_lRefCount);
899     if(!lCount)
900         delete this;
901     return lCount;
902 }
903
904 long VMem::AddRef(void)
905 {
906     long lCount = InterlockedIncrement(&m_lRefCount);
907     return lCount;
908 }
909
910
911 int VMem::Getmem(size_t requestSize)
912 {   /* returns -1 is successful 0 if not */
913 #ifdef USE_BIGBLOCK_ALLOC
914     BOOL bBigBlock;
915 #endif
916     void *ptr;
917
918     /* Round up size to next multiple of 64K. */
919     size_t size = (size_t)ROUND_UP64K(requestSize);
920
921     /*
922      * if the size requested is smaller than our current allocation size
923      * adjust up
924      */
925     if(size < (unsigned long)m_lAllocSize)
926         size = m_lAllocSize;
927
928     /* Update the size to allocate on the next request */
929     if(m_lAllocSize != lAllocMax)
930         m_lAllocSize <<= 2;
931
932 #ifndef _USE_BUDDY_BLOCKS
933     if(m_nHeaps != 0
934 #ifdef USE_BIGBLOCK_ALLOC
935         && !m_heaps[m_nHeaps-1].bBigBlock
936 #endif
937                     ) {
938         /* Expand the last allocated heap */
939         ptr = HeapReAlloc(m_hHeap, HEAP_REALLOC_IN_PLACE_ONLY|HEAP_NO_SERIALIZE,
940                 m_heaps[m_nHeaps-1].base,
941                 m_heaps[m_nHeaps-1].len + size);
942         if(ptr != 0) {
943             HeapAdd(((char*)ptr) + m_heaps[m_nHeaps-1].len, size
944 #ifdef USE_BIGBLOCK_ALLOC
945                 , FALSE
946 #endif
947                 );
948             return -1;
949         }
950     }
951 #endif /* _USE_BUDDY_BLOCKS */
952
953     /*
954      * if we didn't expand a block to cover the requested size
955      * allocate a new Heap
956      * the size of this block must include the additional dummy tags at either end
957      * the above ROUND_UP64K may not have added any memory to include this.
958      */
959     if(size == requestSize)
960         size = (size_t)ROUND_UP64K(requestSize+(blockOverhead));
961
962 Restart:
963 #ifdef _USE_BUDDY_BLOCKS
964     ptr = VirtualAlloc(NULL, size, MEM_COMMIT, PAGE_READWRITE);
965 #else
966 #ifdef USE_BIGBLOCK_ALLOC
967     bBigBlock = FALSE;
968     if (size >= nMaxHeapAllocSize) {
969         bBigBlock = TRUE;
970         ptr = VirtualAlloc(NULL, size, MEM_COMMIT, PAGE_READWRITE);
971     }
972     else
973 #endif
974     ptr = HeapAlloc(m_hHeap, HEAP_NO_SERIALIZE, size);
975 #endif /* _USE_BUDDY_BLOCKS */
976
977     if (!ptr) {
978         /* try to allocate a smaller chunk */
979         size >>= 1;
980         if(size > requestSize)
981             goto Restart;
982     }
983
984     if(ptr == 0) {
985         MEMODSlx("HeapAlloc failed on size!!!", size);
986         return 0;
987     }
988
989 #ifdef _USE_BUDDY_BLOCKS
990     if (HeapAdd(ptr, size)) {
991         VirtualFree(ptr, 0, MEM_RELEASE);
992         return 0;
993     }
994 #else
995 #ifdef USE_BIGBLOCK_ALLOC
996     if (HeapAdd(ptr, size, bBigBlock)) {
997         if (bBigBlock) {
998             VirtualFree(ptr, 0, MEM_RELEASE);
999         }
1000     }
1001 #else
1002     HeapAdd(ptr, size);
1003 #endif
1004 #endif /* _USE_BUDDY_BLOCKS */
1005     return -1;
1006 }
1007
1008 int VMem::HeapAdd(void* p, size_t size
1009 #ifdef USE_BIGBLOCK_ALLOC
1010     , BOOL bBigBlock
1011 #endif
1012     )
1013 {   /* if the block can be successfully added to the heap, returns 0; otherwise -1. */
1014     int index;
1015
1016     /* Check size, then round size down to next long word boundary. */
1017     if(size < minAllocSize)
1018         return -1;
1019
1020     size = (size_t)ROUND_DOWN(size);
1021     PBLOCK ptr = (PBLOCK)p;
1022
1023 #ifdef USE_BIGBLOCK_ALLOC
1024     if (!bBigBlock) {
1025 #endif
1026         /*
1027          * Search for another heap area that's contiguous with the bottom of this new area.
1028          * (It should be extremely unusual to find one that's contiguous with the top).
1029          */
1030         for(index = 0; index < m_nHeaps; ++index) {
1031             if(ptr == m_heaps[index].base + (int)m_heaps[index].len) {
1032                 /*
1033                  * The new block is contiguous with a previously allocated heap area.  Add its
1034                  * length to that of the previous heap.  Merge it with the dummy end-of-heap
1035                  * area marker of the previous heap.
1036                  */
1037                 m_heaps[index].len += size;
1038                 break;
1039             }
1040         }
1041 #ifdef USE_BIGBLOCK_ALLOC
1042     }
1043     else {
1044         index = m_nHeaps;
1045     }
1046 #endif
1047
1048     if(index == m_nHeaps) {
1049         /* The new block is not contiguous, or is BigBlock.  Add it to the heap list. */
1050         if(m_nHeaps == maxHeaps) {
1051             return -1;  /* too many non-contiguous heaps */
1052         }
1053         m_heaps[m_nHeaps].base = ptr;
1054         m_heaps[m_nHeaps].len = size;
1055 #ifdef USE_BIGBLOCK_ALLOC
1056         m_heaps[m_nHeaps].bBigBlock = bBigBlock;
1057 #endif
1058         m_nHeaps++;
1059
1060         /*
1061          * Reserve the first LONG in the block for the ending boundary tag of a dummy
1062          * block at the start of the heap area.
1063          */
1064         size -= blockOverhead;
1065         ptr += blockOverhead;
1066         PSIZE(ptr) = 1; /* mark the dummy previous block as allocated */
1067     }
1068
1069     /*
1070      * Convert the heap to one large block.  Set up its boundary tags, and those of
1071      * marker block after it.  The marker block before the heap will already have
1072      * been set up if this heap is not contiguous with the end of another heap.
1073      */
1074     SetTags(ptr, size | 1);
1075     PBLOCK next = ptr + size;   /* point to dummy end block */
1076     SIZE(next) = 1;     /* mark the dummy end block as allocated */
1077
1078     /*
1079      * Link the block to the start of the free list by calling free().
1080      * This will merge the block with any adjacent free blocks.
1081      */
1082     Free(ptr);
1083     return 0;
1084 }
1085
1086
1087 void* VMem::Expand(void* block, size_t size)
1088 {
1089     /*
1090      * Disallow negative or zero sizes.
1091      */
1092     size_t realsize = CalcAllocSize(size);
1093     if((int)realsize < minAllocSize || size == 0)
1094         return NULL;
1095
1096     PBLOCK ptr = (PBLOCK)block; 
1097
1098     /* if the current size is the same as requested, do nothing. */
1099     size_t cursize = SIZE(ptr) & ~1;
1100     if(cursize == realsize) {
1101         return block;
1102     }
1103
1104     /* if the block is being shrunk, convert the remainder of the block into a new free block. */
1105     if(realsize <= cursize) {
1106         size_t nextsize = cursize - realsize;   /* size of new remainder block */
1107         if(nextsize >= minAllocSize) {
1108             /*
1109              * Split the block
1110              * Set boundary tags for the resized block and the new block.
1111              */
1112             SetTags(ptr, realsize | 1);
1113             ptr += realsize;
1114
1115             /*
1116              * add the new block to the free list.
1117              * call Free to merge this block with next block if free
1118              */
1119             SetTags(ptr, nextsize | 1);
1120             Free(ptr);
1121         }
1122
1123         return block;
1124     }
1125
1126     PBLOCK next = ptr + cursize;
1127     size_t nextsize = SIZE(next);
1128
1129     /* Check the next block for consistency.*/
1130     if((nextsize&1) == 0 && (nextsize + cursize) >= realsize) {
1131         /*
1132          * The next block is free and big enough.  Add the part that's needed
1133          * to our block, and split the remainder off into a new block.
1134          */
1135         if(m_pRover == next)
1136             m_pRover = NEXT(next);
1137
1138         /* Unlink the next block from the free list. */
1139         Unlink(next);
1140         cursize += nextsize;    /* combine sizes */
1141
1142         size_t rem = cursize - realsize;        /* size of remainder */
1143         if(rem >= minAllocSize) {
1144             /*
1145              * The remainder is big enough to be a new block.
1146              * Set boundary tags for the resized block and the new block.
1147              */
1148             next = ptr + realsize;
1149             /*
1150              * add the new block to the free list.
1151              * next block cannot be free
1152              */
1153             SetTags(next, rem);
1154 #ifdef _USE_BUDDY_BLOCKS
1155             AddToFreeList(next, rem);
1156 #else
1157             AddToFreeList(next, m_pFreeList);
1158 #endif
1159             cursize = realsize;
1160         }
1161         /* Set the boundary tags to mark it as allocated. */
1162         SetTags(ptr, cursize | 1);
1163         return ((void *)ptr);
1164     }
1165     return NULL;
1166 }
1167
1168 #ifdef _DEBUG_MEM
1169 #define LOG_FILENAME ".\\MemLog.txt"
1170
1171 void VMem::MemoryUsageMessage(char *str, long x, long y, int c)
1172 {
1173     char szBuffer[512];
1174     if(str) {
1175         if(!m_pLog)
1176             m_pLog = fopen(LOG_FILENAME, "w");
1177         sprintf(szBuffer, str, x, y, c);
1178         fputs(szBuffer, m_pLog);
1179     }
1180     else {
1181         if(m_pLog) {
1182             fflush(m_pLog);
1183             fclose(m_pLog);
1184             m_pLog = 0;
1185         }
1186     }
1187 }
1188
1189 void VMem::WalkHeap(int complete)
1190 {
1191     if(complete) {
1192         MemoryUsageMessage(NULL, 0, 0, 0);
1193         size_t total = 0;
1194         for(int i = 0; i < m_nHeaps; ++i) {
1195             total += m_heaps[i].len;
1196         }
1197         MemoryUsageMessage("VMem heaps used %d. Total memory %08x\n", m_nHeaps, total, 0);
1198
1199         /* Walk all the heaps - verify structures */
1200         for(int index = 0; index < m_nHeaps; ++index) {
1201             PBLOCK ptr = m_heaps[index].base;
1202             size_t size = m_heaps[index].len;
1203 #ifndef _USE_BUDDY_BLOCKS
1204 #ifdef USE_BIGBLOCK_ALLOC
1205             if (!m_heaps[m_nHeaps].bBigBlock)
1206 #endif
1207                 ASSERT(HeapValidate(m_hHeap, HEAP_NO_SERIALIZE, ptr));
1208 #endif
1209
1210             /* set over reserved header block */
1211             size -= blockOverhead;
1212             ptr += blockOverhead;
1213             PBLOCK pLast = ptr + size;
1214             ASSERT(PSIZE(ptr) == 1); /* dummy previous block is allocated */
1215             ASSERT(SIZE(pLast) == 1); /* dummy next block is allocated */
1216             while(ptr < pLast) {
1217                 ASSERT(ptr > m_heaps[index].base);
1218                 size_t cursize = SIZE(ptr) & ~1;
1219                 ASSERT((PSIZE(ptr+cursize) & ~1) == cursize);
1220                 MemoryUsageMessage("Memory Block %08x: Size %08x %c\n", (long)ptr, cursize, (SIZE(ptr)&1) ? 'x' : ' ');
1221                 if(!(SIZE(ptr)&1)) {
1222                     /* this block is on the free list */
1223                     PBLOCK tmp = NEXT(ptr);
1224                     while(tmp != ptr) {
1225                         ASSERT((SIZE(tmp)&1)==0);
1226                         if(tmp == m_pFreeList)
1227                             break;
1228                         ASSERT(NEXT(tmp));
1229                         tmp = NEXT(tmp);
1230                     }
1231                     if(tmp == ptr) {
1232                         MemoryUsageMessage("Memory Block %08x: Size %08x free but not in free list\n", (long)ptr, cursize, 0);
1233                     }
1234                 }
1235                 ptr += cursize;
1236             }
1237         }
1238         MemoryUsageMessage(NULL, 0, 0, 0);
1239     }
1240 }
1241 #endif  /* _DEBUG_MEM */
1242
1243 #endif  /* _USE_MSVCRT_MEM_ALLOC */
1244
1245 #endif  /* ___VMEM_H_INC___ */