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