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