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