perldelta for a8e0c1fd5ade
[perl.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 #ifndef UNDER_CE
25 #define _USE_MSVCRT_MEM_ALLOC
26 #endif
27 #define _USE_LINKED_LIST
28
29 // #define _USE_BUDDY_BLOCKS
30
31 // #define _DEBUG_MEM
32 #ifdef _DEBUG_MEM
33 #define ASSERT(f) if(!(f)) DebugBreak();
34
35 inline void MEMODS(char *str)
36 {
37     OutputDebugString(str);
38     OutputDebugString("\n");
39 }
40
41 inline void MEMODSlx(char *str, long x)
42 {
43     char szBuffer[512]; 
44     sprintf(szBuffer, "%s %lx\n", str, x);
45     OutputDebugString(szBuffer);
46 }
47
48 #define WALKHEAP() WalkHeap(0)
49 #define WALKHEAPTRACE() WalkHeap(1)
50
51 #else
52
53 #define ASSERT(f)
54 #define MEMODS(x)
55 #define MEMODSlx(x, y)
56 #define WALKHEAP()
57 #define WALKHEAPTRACE()
58
59 #endif
60
61 #ifdef _USE_MSVCRT_MEM_ALLOC
62
63 #ifndef _USE_LINKED_LIST
64 // #define _USE_LINKED_LIST
65 #endif
66
67 /* 
68  * Pass all memory requests through to the compiler's msvcr*.dll.
69  * Optionaly track by using a doubly linked header.
70  */
71
72 #ifdef _USE_LINKED_LIST
73 class VMem;
74 typedef struct _MemoryBlockHeader* PMEMORY_BLOCK_HEADER;
75 typedef struct _MemoryBlockHeader {
76     PMEMORY_BLOCK_HEADER    pNext;
77     PMEMORY_BLOCK_HEADER    pPrev;
78     VMem *owner;
79 } MEMORY_BLOCK_HEADER, *PMEMORY_BLOCK_HEADER;
80 #endif
81
82 class VMem
83 {
84 public:
85     VMem();
86     ~VMem();
87     void* Malloc(size_t size);
88     void* Realloc(void* pMem, size_t size);
89     void Free(void* pMem);
90     void GetLock(void);
91     void FreeLock(void);
92     int IsLocked(void);
93     long Release(void);
94     long AddRef(void);
95
96     inline BOOL CreateOk(void)
97     {
98         return TRUE;
99     };
100
101 protected:
102 #ifdef _USE_LINKED_LIST
103     void LinkBlock(PMEMORY_BLOCK_HEADER ptr)
104     {
105         PMEMORY_BLOCK_HEADER next = m_Dummy.pNext;
106         m_Dummy.pNext = ptr;
107         ptr->pPrev = &m_Dummy;
108         ptr->pNext = next;
109         ptr->owner = this;
110         next->pPrev = ptr;
111     }
112     void UnlinkBlock(PMEMORY_BLOCK_HEADER ptr)
113     {
114         PMEMORY_BLOCK_HEADER next = ptr->pNext;
115         PMEMORY_BLOCK_HEADER prev = ptr->pPrev;
116         prev->pNext = next;
117         next->pPrev = prev;
118     }
119
120     MEMORY_BLOCK_HEADER m_Dummy;
121     CRITICAL_SECTION    m_cs;           // access lock
122 #endif
123
124     long                m_lRefCount;    // number of current users
125 };
126
127 VMem::VMem()
128 {
129     m_lRefCount = 1;
130 #ifdef _USE_LINKED_LIST
131     InitializeCriticalSection(&m_cs);
132     m_Dummy.pNext = m_Dummy.pPrev =  &m_Dummy;
133     m_Dummy.owner = this;
134 #endif
135 }
136
137 VMem::~VMem(void)
138 {
139 #ifdef _USE_LINKED_LIST
140     while (m_Dummy.pNext != &m_Dummy) {
141         Free(m_Dummy.pNext+1);
142     }
143     DeleteCriticalSection(&m_cs);
144 #endif
145 }
146
147 void* VMem::Malloc(size_t size)
148 {
149 #ifdef _USE_LINKED_LIST
150     GetLock();
151     PMEMORY_BLOCK_HEADER ptr = (PMEMORY_BLOCK_HEADER)malloc(size+sizeof(MEMORY_BLOCK_HEADER));
152     if (!ptr) {
153         FreeLock();
154         return NULL;
155     }
156     LinkBlock(ptr);
157     FreeLock();
158     return (ptr+1);
159 #else
160     return malloc(size);
161 #endif
162 }
163
164 void* VMem::Realloc(void* pMem, size_t size)
165 {
166 #ifdef _USE_LINKED_LIST
167     if (!pMem)
168         return Malloc(size);
169
170     if (!size) {
171         Free(pMem);
172         return NULL;
173     }
174
175     GetLock();
176     PMEMORY_BLOCK_HEADER ptr = (PMEMORY_BLOCK_HEADER)(((char*)pMem)-sizeof(MEMORY_BLOCK_HEADER));
177     UnlinkBlock(ptr);
178     ptr = (PMEMORY_BLOCK_HEADER)realloc(ptr, size+sizeof(MEMORY_BLOCK_HEADER));
179     if (!ptr) {
180         FreeLock();
181         return NULL;
182     }
183     LinkBlock(ptr);
184     FreeLock();
185
186     return (ptr+1);
187 #else
188     return realloc(pMem, size);
189 #endif
190 }
191
192 void VMem::Free(void* pMem)
193 {
194 #ifdef _USE_LINKED_LIST
195     if (pMem) {
196         PMEMORY_BLOCK_HEADER ptr = (PMEMORY_BLOCK_HEADER)(((char*)pMem)-sizeof(MEMORY_BLOCK_HEADER));
197         if (ptr->owner != this) {
198             if (ptr->owner) {
199 #if 1
200                 int *nowhere = NULL;
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 */
204 #else
205                 ptr->owner->Free(pMem); 
206 #endif
207             }
208             return;
209         }
210         GetLock();
211         UnlinkBlock(ptr);
212         ptr->owner = NULL;
213         free(ptr);
214         FreeLock();
215     }
216 #else /*_USE_LINKED_LIST*/
217     free(pMem);
218 #endif
219 }
220
221 void VMem::GetLock(void)
222 {
223 #ifdef _USE_LINKED_LIST
224     EnterCriticalSection(&m_cs);
225 #endif
226 }
227
228 void VMem::FreeLock(void)
229 {
230 #ifdef _USE_LINKED_LIST
231     LeaveCriticalSection(&m_cs);
232 #endif
233 }
234
235 int VMem::IsLocked(void)
236 {
237 #if 0
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);
242     if(bAccessed) {
243         LeaveCriticalSection(&m_cs);
244     }
245     return !bAccessed;
246 #else
247     ASSERT(0);  /* alarm bells for when somebody calls this */
248     return 0;
249 #endif
250 }
251
252 long VMem::Release(void)
253 {
254     long lCount = InterlockedDecrement(&m_lRefCount);
255     if(!lCount)
256         delete this;
257     return lCount;
258 }
259
260 long VMem::AddRef(void)
261 {
262     long lCount = InterlockedIncrement(&m_lRefCount);
263     return lCount;
264 }
265
266 #else   /* _USE_MSVCRT_MEM_ALLOC */
267
268 /*
269  * Knuth's boundary tag algorithm Vol #1, Page 440.
270  *
271  * Each block in the heap has tag words before and after it,
272  *  TAG
273  *  block
274  *  TAG
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
280  * is set to 0.
281  *
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.
286  *
287  * Since memory allocation may occur on a single threaded, explicit locks are not
288  * provided.
289  * 
290  */
291
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));
300
301 inline size_t CalcEntry(size_t size)
302 {
303     ASSERT((size&(sizeof(long)-1)) == 0);
304     return ((size - minAllocSize) / sizeof(long));
305 }
306 #endif
307
308 typedef BYTE* PBLOCK;   /* pointer to a memory block */
309
310 /*
311  * Macros for accessing hidden fields in a memory block:
312  *
313  * SIZE     size of this block (tag bit 0 is 1 if block is allocated)
314  * PSIZE    size of previous physical block
315  */
316
317 #define SIZE(block)     (*(ULONG*)(((PBLOCK)(block))-sizeofTag))
318 #define PSIZE(block)    (*(ULONG*)(((PBLOCK)(block))-(blockOverhead)))
319 inline void SetTags(PBLOCK block, long size)
320 {
321     SIZE(block) = size;
322     PSIZE(block+(size&~1)) = size;
323 }
324
325 /*
326  * Free list pointers
327  * PREV pointer to previous block
328  * NEXT pointer to next block
329  */
330
331 #define PREV(block)     (*(PBLOCK*)(block))
332 #define NEXT(block)     (*(PBLOCK*)((block)+sizeof(PBLOCK)))
333 inline void SetLink(PBLOCK block, PBLOCK prev, PBLOCK next)
334 {
335     PREV(block) = prev;
336     NEXT(block) = next;
337 }
338 inline void Unlink(PBLOCK p)
339 {
340     PBLOCK next = NEXT(p);
341     PBLOCK prev = PREV(p);
342     NEXT(prev) = next;
343     PREV(next) = prev;
344 }
345 #ifndef _USE_BUDDY_BLOCKS
346 inline void AddToFreeList(PBLOCK block, PBLOCK pInList)
347 {
348     PBLOCK next = NEXT(pInList);
349     NEXT(pInList) = block;
350     SetLink(block, pInList, next);
351     PREV(next) = block;
352 }
353 #endif
354
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))
359
360 /*
361  * HeapRec - a list of all non-contiguous heap areas
362  *
363  * Each record in this array contains information about a non-contiguous heap area.
364  */
365
366 const int maxHeaps = 32; /* 64 was overkill */
367 const long lAllocMax   = 0x80000000; /* max size of allocation */
368
369 #ifdef _USE_BUDDY_BLOCKS
370 typedef struct _FreeListEntry
371 {
372     BYTE    Dummy[minAllocSize];        // dummy free block
373 } FREE_LIST_ENTRY, *PFREE_LIST_ENTRY;
374 #endif
375
376 #ifndef _USE_BUDDY_BLOCKS
377 #define USE_BIGBLOCK_ALLOC
378 #endif
379 /*
380  * performance tuning
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.
384  */
385
386 #ifdef USE_BIGBLOCK_ALLOC
387 const int nMaxHeapAllocSize = (1024*512);  /* don't allocate anything larger than this from the heap */
388 #endif
389
390 typedef struct _HeapRec
391 {
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 */
396 #endif
397 } HeapRec;
398
399 class VMem
400 {
401 public:
402     VMem();
403     ~VMem();
404     void* Malloc(size_t size);
405     void* Realloc(void* pMem, size_t size);
406     void Free(void* pMem);
407     void GetLock(void);
408     void FreeLock(void);
409     int IsLocked(void);
410     long Release(void);
411     long AddRef(void);
412
413     inline BOOL CreateOk(void)
414     {
415 #ifdef _USE_BUDDY_BLOCKS
416         return TRUE;
417 #else
418         return m_hHeap != NULL;
419 #endif
420     };
421
422     void ReInit(void);
423
424 protected:
425     void Init(void);
426     int Getmem(size_t size);
427
428     int HeapAdd(void* ptr, size_t size
429 #ifdef USE_BIGBLOCK_ALLOC
430         , BOOL bBigBlock
431 #endif
432     );
433
434     void* Expand(void* block, size_t size);
435
436 #ifdef _USE_BUDDY_BLOCKS
437     inline PBLOCK GetFreeListLink(int index)
438     {
439         if (index >= nListEntries)
440             index = nListEntries-1;
441         return &m_FreeList[index].Dummy[sizeofTag];
442     }
443     inline PBLOCK GetOverSizeFreeList(void)
444     {
445         return &m_FreeList[nListEntries-1].Dummy[sizeofTag];
446     }
447     inline PBLOCK GetEOLFreeList(void)
448     {
449         return &m_FreeList[nListEntries].Dummy[sizeofTag];
450     }
451
452     void AddToFreeList(PBLOCK block, size_t size)
453     {
454         PBLOCK pFreeList = GetFreeListLink(CalcEntry(size));
455         PBLOCK next = NEXT(pFreeList);
456         NEXT(pFreeList) = block;
457         SetLink(block, pFreeList, next);
458         PREV(next) = block;
459     }
460 #endif
461     inline size_t CalcAllocSize(size_t size)
462     {
463         /*
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.
466          */
467         return (size < minBlockSize) ? minAllocSize : (size_t)ROUND_UP(size) + blockOverhead;
468     }
469
470 #ifdef _USE_BUDDY_BLOCKS
471     FREE_LIST_ENTRY     m_FreeList[nListEntries+1];     // free list with dummy end of list entry as well
472 #else
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
476 #endif
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
483
484 #ifdef _DEBUG_MEM
485     void WalkHeap(int complete);
486     void MemoryUsageMessage(char *str, long x, long y, int c);
487     FILE*               m_pLog;
488 #endif
489 };
490
491 VMem::VMem()
492 {
493     m_lRefCount = 1;
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 */
498     ASSERT(bRet);
499 #endif
500
501     InitializeCriticalSection(&m_cs);
502 #ifdef _DEBUG_MEM
503     m_pLog = 0;
504 #endif
505
506     Init();
507 }
508
509 VMem::~VMem(void)
510 {
511 #ifndef _USE_BUDDY_BLOCKS
512     ASSERT(HeapValidate(m_hHeap, HEAP_NO_SERIALIZE, NULL));
513 #endif
514     WALKHEAPTRACE();
515
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);
520     }
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);
526         }
527     }
528 #endif
529     BOOL bRet = HeapDestroy(m_hHeap);
530     ASSERT(bRet);
531 #endif /* _USE_BUDDY_BLOCKS */
532 }
533
534 void VMem::ReInit(void)
535 {
536     for(int index = 0; index < m_nHeaps; ++index) {
537 #ifdef _USE_BUDDY_BLOCKS
538         VirtualFree(m_heaps[index].base, 0, MEM_RELEASE);
539 #else
540 #ifdef USE_BIGBLOCK_ALLOC
541         if (m_heaps[index].bBigBlock) {
542             VirtualFree(m_heaps[index].base, 0, MEM_RELEASE);
543         }
544         else
545 #endif
546             HeapFree(m_hHeap, HEAP_NO_SERIALIZE, m_heaps[index].base);
547 #endif /* _USE_BUDDY_BLOCKS */
548     }
549
550     Init();
551 }
552
553 void VMem::Init(void)
554 {
555 #ifdef _USE_BUDDY_BLOCKS
556     PBLOCK pFreeList;
557     /*
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.
562      */
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;
567     }
568     pFreeList = GetEOLFreeList();
569     SIZE(pFreeList) = PSIZE(pFreeList+minAllocSize) = 0;
570     PREV(pFreeList) = NEXT(pFreeList) = NULL;
571     m_pRover = GetOverSizeFreeList();
572 #else
573     /*
574      * Initialize the free list by placing a dummy zero-length block on it.
575      * Set the number of non-contiguous heaps to zero.
576      */
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;
580 #endif
581
582     m_nHeaps = 0;
583     m_lAllocSize = lAllocStart;
584 }
585
586 void* VMem::Malloc(size_t size)
587 {
588     WALKHEAP();
589
590     PBLOCK ptr;
591     size_t lsize, rem;
592     /*
593      * Disallow negative or zero sizes.
594      */
595     size_t realsize = CalcAllocSize(size);
596     if((int)realsize < minAllocSize || size == 0)
597         return NULL;
598
599 #ifdef _USE_BUDDY_BLOCKS
600     /*
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
605      */
606     {
607         int index = CalcEntry(realsize);
608         if (index < nListEntries-1) {
609             ptr = GetFreeListLink(index);
610             lsize = SIZE(ptr);
611             if (lsize >= realsize) {
612                 rem = lsize - realsize;
613                 if(rem < minAllocSize) {
614                     /* Unlink the block from the free list. */
615                     Unlink(ptr);
616                 }
617                 else {
618                     /*
619                      * split the block
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.
623                      */
624                     SetTags(ptr, rem);
625                     ptr += SIZE(ptr);
626                     lsize = realsize;
627                 }
628                 SetTags(ptr, lsize | 1);
629                 return ptr;
630             }
631             ptr = m_pRover;
632             lsize = SIZE(ptr);
633             if (lsize >= realsize) {
634                 rem = lsize - realsize;
635                 if(rem < minAllocSize) {
636                     /* Unlink the block from the free list. */
637                     Unlink(ptr);
638                 }
639                 else {
640                     /*
641                      * split the block
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.
645                      */
646                     SetTags(ptr, rem);
647                     ptr += SIZE(ptr);
648                     lsize = realsize;
649                 }
650                 SetTags(ptr, lsize | 1);
651                 return ptr;
652             }
653             ptr = GetFreeListLink(index+1);
654             while (NEXT(ptr)) {
655                 lsize = SIZE(ptr);
656                 if (lsize >= realsize) {
657                     size_t rem = lsize - realsize;
658                     if(rem < minAllocSize) {
659                         /* Unlink the block from the free list. */
660                         Unlink(ptr);
661                     }
662                     else {
663                         /*
664                          * split the block
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.
668                          */
669                         SetTags(ptr, rem);
670                         ptr += SIZE(ptr);
671                         lsize = realsize;
672                     }
673                     SetTags(ptr, lsize | 1);
674                     return ptr;
675                 }
676                 ptr += sizeof(FREE_LIST_ENTRY);
677             }
678         }
679     }
680 #endif
681
682     /*
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.
685      */
686     ptr = m_pRover;     /* start searching at rover */
687     int loops = 2;      /* allow two times through the loop  */
688     for(;;) {
689         lsize = SIZE(ptr);
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) {
696                 if(m_pRover == ptr)
697                     m_pRover = NEXT(ptr);
698
699                 /* Unlink the block from the free list. */
700                 Unlink(ptr);
701             }
702             else {
703                 /*
704                  * split the block
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.
708                  */
709                 SetTags(ptr, rem);
710                 ptr += SIZE(ptr);
711                 lsize = realsize;
712             }
713             /* Set the boundary tags to mark it as allocated. */
714             SetTags(ptr, lsize | 1);
715             return ((void *)ptr);
716         }
717
718         /*
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.
721          */
722         ptr = NEXT(ptr);
723         if(ptr == m_pRover) {
724             if(!(loops-- && Getmem(realsize))) {
725                 return NULL;
726             }
727             ptr = m_pRover;
728         }
729     }
730 }
731
732 void* VMem::Realloc(void* block, size_t size)
733 {
734     WALKHEAP();
735
736     /* if size is zero, free the block. */
737     if(size == 0) {
738         Free(block);
739         return (NULL);
740     }
741
742     /* if block pointer is NULL, do a Malloc(). */
743     if(block == NULL)
744         return Malloc(size);
745
746     /*
747      * Grow or shrink the block in place.
748      * if the block grows then the next block will be used if free
749      */
750     if(Expand(block, size) != NULL)
751         return block;
752
753     size_t realsize = CalcAllocSize(size);
754     if((int)realsize < minAllocSize)
755         return NULL;
756
757     /*
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.
760      */
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;
766         if(m_pRover == prev)
767             m_pRover = NEXT(prev);
768
769         /* Unlink the next block from the free list. */
770         Unlink(prev);
771
772         /* Copy contents of old block to new location, make it the current block. */
773         memmove(prev, ptr, cursize);
774         cursize += psize;       /* combine sizes */
775         ptr = prev;
776
777         size_t rem = cursize - realsize;
778         if(rem >= minAllocSize) {
779             /*
780              * The remainder is big enough to be a new block.  Set boundary
781              * tags for the resized block and the new block.
782              */
783             prev = ptr + realsize;
784             /*
785              * add the new block to the free list.
786              * next block cannot be free
787              */
788             SetTags(prev, rem);
789 #ifdef _USE_BUDDY_BLOCKS
790             AddToFreeList(prev, rem);
791 #else
792             AddToFreeList(prev, m_pFreeList);
793 #endif
794             cursize = realsize;
795         }
796         /* Set the boundary tags to mark it as allocated. */
797         SetTags(ptr, cursize | 1);
798         return ((void *)ptr);
799     }
800
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);
804         Free(block);
805     }
806     return ((void *)ptr);
807 }
808
809 void VMem::Free(void* p)
810 {
811     WALKHEAP();
812
813     /* Ignore null pointer. */
814     if(p == NULL)
815         return;
816
817     PBLOCK ptr = (PBLOCK)p;
818
819     /* Check for attempt to free a block that's already free. */
820     size_t size = SIZE(ptr);
821     if((size&1) == 0) {
822         MEMODSlx("Attempt to free previously freed block", (long)p);
823         return;
824     }
825     size &= ~1; /* remove allocated tag */
826
827     /* if previous block is free, add this block to it. */
828 #ifndef _USE_BUDDY_BLOCKS
829     int linked = FALSE;
830 #endif
831     size_t psize = PSIZE(ptr);
832     if((psize&1) == 0) {
833         ptr -= psize;   /* point to previous block */
834         size += psize;  /* merge the sizes of the two blocks */
835 #ifdef _USE_BUDDY_BLOCKS
836         Unlink(ptr);
837 #else
838         linked = TRUE;  /* it's already on the free list */
839 #endif
840     }
841
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);
845     if((nsize&1) == 0) {
846         /* block is free move rover if needed */
847         if(m_pRover == next)
848             m_pRover = NEXT(next);
849
850         /* unlink the next block from the free list. */
851         Unlink(next);
852
853         /* merge the sizes of this block and the next block. */
854         size += nsize;
855     }
856
857     /* Set the boundary tags for the block; */
858     SetTags(ptr, size);
859
860     /* Link the block to the head of the free list. */
861 #ifdef _USE_BUDDY_BLOCKS
862         AddToFreeList(ptr, size);
863 #else
864     if(!linked) {
865         AddToFreeList(ptr, m_pFreeList);
866     }
867 #endif
868 }
869
870 void VMem::GetLock(void)
871 {
872     EnterCriticalSection(&m_cs);
873 }
874
875 void VMem::FreeLock(void)
876 {
877     LeaveCriticalSection(&m_cs);
878 }
879
880 int VMem::IsLocked(void)
881 {
882 #if 0
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);
887     if(bAccessed) {
888         LeaveCriticalSection(&m_cs);
889     }
890     return !bAccessed;
891 #else
892     ASSERT(0);  /* alarm bells for when somebody calls this */
893     return 0;
894 #endif
895 }
896
897
898 long VMem::Release(void)
899 {
900     long lCount = InterlockedDecrement(&m_lRefCount);
901     if(!lCount)
902         delete this;
903     return lCount;
904 }
905
906 long VMem::AddRef(void)
907 {
908     long lCount = InterlockedIncrement(&m_lRefCount);
909     return lCount;
910 }
911
912
913 int VMem::Getmem(size_t requestSize)
914 {   /* returns -1 is successful 0 if not */
915 #ifdef USE_BIGBLOCK_ALLOC
916     BOOL bBigBlock;
917 #endif
918     void *ptr;
919
920     /* Round up size to next multiple of 64K. */
921     size_t size = (size_t)ROUND_UP64K(requestSize);
922
923     /*
924      * if the size requested is smaller than our current allocation size
925      * adjust up
926      */
927     if(size < (unsigned long)m_lAllocSize)
928         size = m_lAllocSize;
929
930     /* Update the size to allocate on the next request */
931     if(m_lAllocSize != lAllocMax)
932         m_lAllocSize <<= 2;
933
934 #ifndef _USE_BUDDY_BLOCKS
935     if(m_nHeaps != 0
936 #ifdef USE_BIGBLOCK_ALLOC
937         && !m_heaps[m_nHeaps-1].bBigBlock
938 #endif
939                     ) {
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);
944         if(ptr != 0) {
945             HeapAdd(((char*)ptr) + m_heaps[m_nHeaps-1].len, size
946 #ifdef USE_BIGBLOCK_ALLOC
947                 , FALSE
948 #endif
949                 );
950             return -1;
951         }
952     }
953 #endif /* _USE_BUDDY_BLOCKS */
954
955     /*
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.
960      */
961     if(size == requestSize)
962         size = (size_t)ROUND_UP64K(requestSize+(blockOverhead));
963
964 Restart:
965 #ifdef _USE_BUDDY_BLOCKS
966     ptr = VirtualAlloc(NULL, size, MEM_COMMIT, PAGE_READWRITE);
967 #else
968 #ifdef USE_BIGBLOCK_ALLOC
969     bBigBlock = FALSE;
970     if (size >= nMaxHeapAllocSize) {
971         bBigBlock = TRUE;
972         ptr = VirtualAlloc(NULL, size, MEM_COMMIT, PAGE_READWRITE);
973     }
974     else
975 #endif
976     ptr = HeapAlloc(m_hHeap, HEAP_NO_SERIALIZE, size);
977 #endif /* _USE_BUDDY_BLOCKS */
978
979     if (!ptr) {
980         /* try to allocate a smaller chunk */
981         size >>= 1;
982         if(size > requestSize)
983             goto Restart;
984     }
985
986     if(ptr == 0) {
987         MEMODSlx("HeapAlloc failed on size!!!", size);
988         return 0;
989     }
990
991 #ifdef _USE_BUDDY_BLOCKS
992     if (HeapAdd(ptr, size)) {
993         VirtualFree(ptr, 0, MEM_RELEASE);
994         return 0;
995     }
996 #else
997 #ifdef USE_BIGBLOCK_ALLOC
998     if (HeapAdd(ptr, size, bBigBlock)) {
999         if (bBigBlock) {
1000             VirtualFree(ptr, 0, MEM_RELEASE);
1001         }
1002     }
1003 #else
1004     HeapAdd(ptr, size);
1005 #endif
1006 #endif /* _USE_BUDDY_BLOCKS */
1007     return -1;
1008 }
1009
1010 int VMem::HeapAdd(void* p, size_t size
1011 #ifdef USE_BIGBLOCK_ALLOC
1012     , BOOL bBigBlock
1013 #endif
1014     )
1015 {   /* if the block can be successfully added to the heap, returns 0; otherwise -1. */
1016     int index;
1017
1018     /* Check size, then round size down to next long word boundary. */
1019     if(size < minAllocSize)
1020         return -1;
1021
1022     size = (size_t)ROUND_DOWN(size);
1023     PBLOCK ptr = (PBLOCK)p;
1024
1025 #ifdef USE_BIGBLOCK_ALLOC
1026     if (!bBigBlock) {
1027 #endif
1028         /*
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).
1031          */
1032         for(index = 0; index < m_nHeaps; ++index) {
1033             if(ptr == m_heaps[index].base + (int)m_heaps[index].len) {
1034                 /*
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.
1038                  */
1039                 m_heaps[index].len += size;
1040                 break;
1041             }
1042         }
1043 #ifdef USE_BIGBLOCK_ALLOC
1044     }
1045     else {
1046         index = m_nHeaps;
1047     }
1048 #endif
1049
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 */
1054         }
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;
1059 #endif
1060         m_nHeaps++;
1061
1062         /*
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.
1065          */
1066         size -= blockOverhead;
1067         ptr += blockOverhead;
1068         PSIZE(ptr) = 1; /* mark the dummy previous block as allocated */
1069     }
1070
1071     /*
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.
1075      */
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 */
1079
1080     /*
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.
1083      */
1084     Free(ptr);
1085     return 0;
1086 }
1087
1088
1089 void* VMem::Expand(void* block, size_t size)
1090 {
1091     /*
1092      * Disallow negative or zero sizes.
1093      */
1094     size_t realsize = CalcAllocSize(size);
1095     if((int)realsize < minAllocSize || size == 0)
1096         return NULL;
1097
1098     PBLOCK ptr = (PBLOCK)block; 
1099
1100     /* if the current size is the same as requested, do nothing. */
1101     size_t cursize = SIZE(ptr) & ~1;
1102     if(cursize == realsize) {
1103         return block;
1104     }
1105
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) {
1110             /*
1111              * Split the block
1112              * Set boundary tags for the resized block and the new block.
1113              */
1114             SetTags(ptr, realsize | 1);
1115             ptr += realsize;
1116
1117             /*
1118              * add the new block to the free list.
1119              * call Free to merge this block with next block if free
1120              */
1121             SetTags(ptr, nextsize | 1);
1122             Free(ptr);
1123         }
1124
1125         return block;
1126     }
1127
1128     PBLOCK next = ptr + cursize;
1129     size_t nextsize = SIZE(next);
1130
1131     /* Check the next block for consistency.*/
1132     if((nextsize&1) == 0 && (nextsize + cursize) >= realsize) {
1133         /*
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.
1136          */
1137         if(m_pRover == next)
1138             m_pRover = NEXT(next);
1139
1140         /* Unlink the next block from the free list. */
1141         Unlink(next);
1142         cursize += nextsize;    /* combine sizes */
1143
1144         size_t rem = cursize - realsize;        /* size of remainder */
1145         if(rem >= minAllocSize) {
1146             /*
1147              * The remainder is big enough to be a new block.
1148              * Set boundary tags for the resized block and the new block.
1149              */
1150             next = ptr + realsize;
1151             /*
1152              * add the new block to the free list.
1153              * next block cannot be free
1154              */
1155             SetTags(next, rem);
1156 #ifdef _USE_BUDDY_BLOCKS
1157             AddToFreeList(next, rem);
1158 #else
1159             AddToFreeList(next, m_pFreeList);
1160 #endif
1161             cursize = realsize;
1162         }
1163         /* Set the boundary tags to mark it as allocated. */
1164         SetTags(ptr, cursize | 1);
1165         return ((void *)ptr);
1166     }
1167     return NULL;
1168 }
1169
1170 #ifdef _DEBUG_MEM
1171 #define LOG_FILENAME ".\\MemLog.txt"
1172
1173 void VMem::MemoryUsageMessage(char *str, long x, long y, int c)
1174 {
1175     char szBuffer[512];
1176     if(str) {
1177         if(!m_pLog)
1178             m_pLog = fopen(LOG_FILENAME, "w");
1179         sprintf(szBuffer, str, x, y, c);
1180         fputs(szBuffer, m_pLog);
1181     }
1182     else {
1183         if(m_pLog) {
1184             fflush(m_pLog);
1185             fclose(m_pLog);
1186             m_pLog = 0;
1187         }
1188     }
1189 }
1190
1191 void VMem::WalkHeap(int complete)
1192 {
1193     if(complete) {
1194         MemoryUsageMessage(NULL, 0, 0, 0);
1195         size_t total = 0;
1196         for(int i = 0; i < m_nHeaps; ++i) {
1197             total += m_heaps[i].len;
1198         }
1199         MemoryUsageMessage("VMem heaps used %d. Total memory %08x\n", m_nHeaps, total, 0);
1200
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)
1208 #endif
1209                 ASSERT(HeapValidate(m_hHeap, HEAP_NO_SERIALIZE, ptr));
1210 #endif
1211
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);
1226                     while(tmp != ptr) {
1227                         ASSERT((SIZE(tmp)&1)==0);
1228                         if(tmp == m_pFreeList)
1229                             break;
1230                         ASSERT(NEXT(tmp));
1231                         tmp = NEXT(tmp);
1232                     }
1233                     if(tmp == ptr) {
1234                         MemoryUsageMessage("Memory Block %08x: Size %08x free but not in free list\n", (long)ptr, cursize, 0);
1235                     }
1236                 }
1237                 ptr += cursize;
1238             }
1239         }
1240         MemoryUsageMessage(NULL, 0, 0, 0);
1241     }
1242 }
1243 #endif  /* _DEBUG_MEM */
1244
1245 #endif  /* _USE_MSVCRT_MEM_ALLOC */
1246
1247 #endif  /* ___VMEM_H_INC___ */