This is a live mirror of the Perl 5 development currently hosted at https://github.com/perl/perl5
[PATCH: perl@11564] introducing perlivp
[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  *
10  * Knuth's boundary tag algorithm Vol #1, Page 440.
11  *
12  * Each block in the heap has tag words before and after it,
13  *  TAG
14  *  block
15  *  TAG
16  * The size is stored in these tags as a long word, and includes the 8 bytes
17  * of overhead that the boundary tags consume.  Blocks are allocated on long
18  * word boundaries, so the size is always multiples of long words.  When the
19  * block is allocated, bit 0, (the tag bit), of the size is set to 1.  When 
20  * a block is freed, it is merged with adjacent free blocks, and the tag bit
21  * is set to 0.
22  *
23  * A linked list is used to manage the free list. The first two long words of
24  * the block contain double links.  These links are only valid when the block
25  * is freed, therefore space needs to be reserved for them.  Thus, the minimum
26  * block size (not counting the tags) is 8 bytes.
27  *
28  * Since memory allocation may occur on a single threaded, explict locks are
29  * provided.
30  * 
31  */
32
33 #ifndef ___VMEM_H_INC___
34 #define ___VMEM_H_INC___
35
36 const long lAllocStart = 0x00010000; /* start at 64K */
37 const long minBlockSize = sizeof(void*)*2;
38 const long sizeofTag = sizeof(long);
39 const long blockOverhead = sizeofTag*2;
40 const long minAllocSize = minBlockSize+blockOverhead;
41
42 typedef BYTE* PBLOCK;   /* pointer to a memory block */
43
44 /*
45  * Macros for accessing hidden fields in a memory block:
46  *
47  * SIZE     size of this block (tag bit 0 is 1 if block is allocated)
48  * PSIZE    size of previous physical block
49  */
50
51 #define SIZE(block)     (*(ULONG*)(((PBLOCK)(block))-sizeofTag))
52 #define PSIZE(block)    (*(ULONG*)(((PBLOCK)(block))-(sizeofTag*2)))
53 inline void SetTags(PBLOCK block, long size)
54 {
55     SIZE(block) = size;
56     PSIZE(block+(size&~1)) = size;
57 }
58
59 /*
60  * Free list pointers
61  * PREV pointer to previous block
62  * NEXT pointer to next block
63  */
64
65 #define PREV(block)     (*(PBLOCK*)(block))
66 #define NEXT(block)     (*(PBLOCK*)((block)+sizeof(PBLOCK)))
67 inline void SetLink(PBLOCK block, PBLOCK prev, PBLOCK next)
68 {
69     PREV(block) = prev;
70     NEXT(block) = next;
71 }
72 inline void Unlink(PBLOCK p)
73 {
74     PBLOCK next = NEXT(p);
75     PBLOCK prev = PREV(p);
76     NEXT(prev) = next;
77     PREV(next) = prev;
78 }
79 inline void AddToFreeList(PBLOCK block, PBLOCK pInList)
80 {
81     PBLOCK next = NEXT(pInList);
82     NEXT(pInList) = block;
83     SetLink(block, pInList, next);
84     PREV(next) = block;
85 }
86
87
88 /* Macro for rounding up to the next sizeof(long) */
89 #define ROUND_UP(n)     (((ULONG)(n)+sizeof(long)-1)&~(sizeof(long)-1))
90 #define ROUND_UP64K(n)  (((ULONG)(n)+0x10000-1)&~(0x10000-1))
91 #define ROUND_DOWN(n)   ((ULONG)(n)&~(sizeof(long)-1))
92
93 /*
94  * HeapRec - a list of all non-contiguous heap areas
95  *
96  * Each record in this array contains information about a non-contiguous heap area.
97  */
98
99 const int maxHeaps = 64;
100 const long lAllocMax   = 0x80000000; /* max size of allocation */
101
102 typedef struct _HeapRec
103 {
104     PBLOCK      base;   /* base of heap area */
105     ULONG       len;    /* size of heap area */
106 } HeapRec;
107
108
109 class VMem
110 {
111 public:
112     VMem();
113     ~VMem();
114     virtual void* Malloc(size_t size);
115     virtual void* Realloc(void* pMem, size_t size);
116     virtual void Free(void* pMem);
117     virtual void GetLock(void);
118     virtual void FreeLock(void);
119     virtual int IsLocked(void);
120     virtual long Release(void);
121     virtual long AddRef(void);
122
123     inline BOOL CreateOk(void)
124     {
125         return m_hHeap != NULL;
126     };
127
128     void ReInit(void);
129
130 protected:
131     void Init(void);
132     int Getmem(size_t size);
133     int HeapAdd(void* ptr, size_t size);
134     void* Expand(void* block, size_t size);
135     void WalkHeap(void);
136
137     HANDLE              m_hHeap;                    // memory heap for this script
138     char                m_FreeDummy[minAllocSize];  // dummy free block
139     PBLOCK              m_pFreeList;                // pointer to first block on free list
140     PBLOCK              m_pRover;                   // roving pointer into the free list
141     HeapRec             m_heaps[maxHeaps];          // list of all non-contiguous heap areas 
142     int                 m_nHeaps;                   // no. of heaps in m_heaps 
143     long                m_lAllocSize;               // current alloc size
144     long                m_lRefCount;                // number of current users
145     CRITICAL_SECTION    m_cs;                       // access lock
146 };
147
148 // #define _DEBUG_MEM
149 #ifdef _DEBUG_MEM
150 #define ASSERT(f) if(!(f)) DebugBreak();
151
152 inline void MEMODS(char *str)
153 {
154     OutputDebugString(str);
155     OutputDebugString("\n");
156 }
157
158 inline void MEMODSlx(char *str, long x)
159 {
160     char szBuffer[512]; 
161     sprintf(szBuffer, "%s %lx\n", str, x);
162     OutputDebugString(szBuffer);
163 }
164
165 #define WALKHEAP() WalkHeap()
166 #define WALKHEAPTRACE() m_pRover = NULL; WalkHeap()
167
168 #else
169
170 #define ASSERT(f)
171 #define MEMODS(x)
172 #define MEMODSlx(x, y)
173 #define WALKHEAP()
174 #define WALKHEAPTRACE()
175
176 #endif
177
178
179 VMem::VMem()
180 {
181     m_lRefCount = 1;
182     BOOL bRet = (NULL != (m_hHeap = HeapCreate(HEAP_NO_SERIALIZE,
183                                 lAllocStart,    /* initial size of heap */
184                                 0)));           /* no upper limit on size of heap */
185     ASSERT(bRet);
186
187     InitializeCriticalSection(&m_cs);
188
189     Init();
190 }
191
192 VMem::~VMem(void)
193 {
194     ASSERT(HeapValidate(m_hHeap, HEAP_NO_SERIALIZE, NULL));
195     WALKHEAPTRACE();
196     DeleteCriticalSection(&m_cs);
197     BOOL bRet = HeapDestroy(m_hHeap);
198     ASSERT(bRet);
199 }
200
201 void VMem::ReInit(void)
202 {
203     for(int index = 0; index < m_nHeaps; ++index)
204         HeapFree(m_hHeap, HEAP_NO_SERIALIZE, m_heaps[index].base);
205
206     Init();
207 }
208
209 void VMem::Init(void)
210 {   /*
211      * Initialize the free list by placing a dummy zero-length block on it.
212      * Set the number of non-contiguous heaps to zero.
213      */
214     m_pFreeList = m_pRover = (PBLOCK)(&m_FreeDummy[minBlockSize]);
215     PSIZE(m_pFreeList) = SIZE(m_pFreeList) = 0;
216     PREV(m_pFreeList) = NEXT(m_pFreeList) = m_pFreeList;
217
218     m_nHeaps = 0;
219     m_lAllocSize = lAllocStart;
220 }
221
222 void* VMem::Malloc(size_t size)
223 {
224     WALKHEAP();
225
226     /*
227      * Adjust the real size of the block to be a multiple of sizeof(long), and add
228      * the overhead for the boundary tags.  Disallow negative or zero sizes.
229      */
230     size_t realsize = (size < blockOverhead) ? minAllocSize : (size_t)ROUND_UP(size) + minBlockSize;
231     if((int)realsize < minAllocSize || size == 0)
232         return NULL;
233
234     /*
235      * Start searching the free list at the rover.  If we arrive back at rover without
236      * finding anything, allocate some memory from the heap and try again.
237      */
238     PBLOCK ptr = m_pRover;      /* start searching at rover */
239     int loops = 2;              /* allow two times through the loop  */
240     for(;;) {
241         size_t lsize = SIZE(ptr);
242         ASSERT((lsize&1)==0);
243         /* is block big enough? */
244         if(lsize >= realsize) { 
245             /* if the remainder is too small, don't bother splitting the block. */
246             size_t rem = lsize - realsize;
247             if(rem < minAllocSize) {
248                 if(m_pRover == ptr)
249                     m_pRover = NEXT(ptr);
250
251                 /* Unlink the block from the free list. */
252                 Unlink(ptr);
253             }
254             else {
255                 /*
256                  * split the block
257                  * The remainder is big enough to split off into a new block.
258                  * Use the end of the block, resize the beginning of the block
259                  * no need to change the free list.
260                  */
261                 SetTags(ptr, rem);
262                 ptr += SIZE(ptr);
263                 lsize = realsize;
264             }
265             /* Set the boundary tags to mark it as allocated. */
266             SetTags(ptr, lsize | 1);
267             return ((void *)ptr);
268         }
269
270         /*
271          * This block was unsuitable.  If we've gone through this list once already without
272          * finding anything, allocate some new memory from the heap and try again.
273          */
274         ptr = NEXT(ptr);
275         if(ptr == m_pRover) {
276             if(!(loops-- && Getmem(realsize))) {
277                 return NULL;
278             }
279             ptr = m_pRover;
280         }
281     }
282 }
283
284 void* VMem::Realloc(void* block, size_t size)
285 {
286     WALKHEAP();
287
288     /* if size is zero, free the block. */
289     if(size == 0) {
290         Free(block);
291         return (NULL);
292     }
293
294     /* if block pointer is NULL, do a Malloc(). */
295     if(block == NULL)
296         return Malloc(size);
297
298     /*
299      * Grow or shrink the block in place.
300      * if the block grows then the next block will be used if free
301      */
302     if(Expand(block, size) != NULL)
303         return block;
304
305     /*
306      * adjust the real size of the block to be a multiple of sizeof(long), and add the
307      * overhead for the boundary tags.  Disallow negative or zero sizes.
308      */
309     size_t realsize = (size < blockOverhead) ? minAllocSize : (size_t)ROUND_UP(size) + minBlockSize;
310     if((int)realsize < minAllocSize)
311         return NULL;
312
313     /*
314      * see if the previous block is free, and is it big enough to cover the new size
315      * if merged with the current block.
316      */
317     PBLOCK ptr = (PBLOCK)block;
318     size_t cursize = SIZE(ptr) & ~1;
319     size_t psize = PSIZE(ptr);
320     if((psize&1) == 0 && (psize + cursize) >= realsize) {
321         PBLOCK prev = ptr - psize;
322         if(m_pRover == prev)
323             m_pRover = NEXT(prev);
324
325         /* Unlink the next block from the free list. */
326         Unlink(prev);
327
328         /* Copy contents of old block to new location, make it the current block. */
329         memmove(prev, ptr, cursize);
330         cursize += psize;       /* combine sizes */
331         ptr = prev;
332
333         size_t rem = cursize - realsize;
334         if(rem >= minAllocSize) {
335             /*
336              * The remainder is big enough to be a new block.  Set boundary
337              * tags for the resized block and the new block.
338              */
339             prev = ptr + realsize;
340             /*
341              * add the new block to the free list.
342              * next block cannot be free
343              */
344             SetTags(prev, rem);
345             AddToFreeList(prev, m_pFreeList);
346             cursize = realsize;
347         }
348         /* Set the boundary tags to mark it as allocated. */
349         SetTags(ptr, cursize | 1);
350         return ((void *)ptr);
351     }
352
353     /* Allocate a new block, copy the old to the new, and free the old. */
354     if((ptr = (PBLOCK)Malloc(size)) != NULL) {
355         memmove(ptr, block, cursize-minBlockSize);
356         Free(block);
357     }
358     return ((void *)ptr);
359 }
360
361 void VMem::Free(void* p)
362 {
363     WALKHEAP();
364
365     /* Ignore null pointer. */
366     if(p == NULL)
367         return;
368
369     PBLOCK ptr = (PBLOCK)p;
370
371     /* Check for attempt to free a block that's already free. */
372     size_t size = SIZE(ptr);
373     if((size&1) == 0) {
374         MEMODSlx("Attempt to free previously freed block", (long)p);
375         return;
376     }
377     size &= ~1; /* remove allocated tag */
378
379     /* if previous block is free, add this block to it. */
380     int linked = FALSE;
381     size_t psize = PSIZE(ptr);
382     if((psize&1) == 0) {
383         ptr -= psize;   /* point to previous block */
384         size += psize;  /* merge the sizes of the two blocks */
385         linked = TRUE;  /* it's already on the free list */
386     }
387
388     /* if the next physical block is free, merge it with this block. */
389     PBLOCK next = ptr + size;   /* point to next physical block */
390     size_t nsize = SIZE(next);
391     if((nsize&1) == 0) {
392         /* block is free move rover if needed */
393         if(m_pRover == next)
394             m_pRover = NEXT(next);
395
396         /* unlink the next block from the free list. */
397         Unlink(next);
398
399         /* merge the sizes of this block and the next block. */
400         size += nsize;
401     }
402
403     /* Set the boundary tags for the block; */
404     SetTags(ptr, size);
405
406     /* Link the block to the head of the free list. */
407     if(!linked) {
408         AddToFreeList(ptr, m_pFreeList);
409     }
410 }
411
412 void VMem::GetLock(void)
413 {
414     EnterCriticalSection(&m_cs);
415 }
416
417 void VMem::FreeLock(void)
418 {
419     LeaveCriticalSection(&m_cs);
420 }
421
422 int VMem::IsLocked(void)
423 {
424 #if 0
425     /* XXX TryEnterCriticalSection() is not available in some versions
426      * of Windows 95.  Since this code is not used anywhere yet, we 
427      * skirt the issue for now. */
428     BOOL bAccessed = TryEnterCriticalSection(&m_cs);
429     if(bAccessed) {
430         LeaveCriticalSection(&m_cs);
431     }
432     return !bAccessed;
433 #else
434     ASSERT(0);  /* alarm bells for when somebody calls this */
435     return 0;
436 #endif
437 }
438
439
440 long VMem::Release(void)
441 {
442     long lCount = InterlockedDecrement(&m_lRefCount);
443     if(!lCount)
444         delete this;
445     return lCount;
446 }
447
448 long VMem::AddRef(void)
449 {
450     long lCount = InterlockedIncrement(&m_lRefCount);
451     return lCount;
452 }
453
454
455 int VMem::Getmem(size_t requestSize)
456 {   /* returns -1 is successful 0 if not */
457     void *ptr;
458
459     /* Round up size to next multiple of 64K. */
460     size_t size = (size_t)ROUND_UP64K(requestSize);
461     
462     /*
463      * if the size requested is smaller than our current allocation size
464      * adjust up
465      */
466     if(size < (unsigned long)m_lAllocSize)
467         size = m_lAllocSize;
468
469     /* Update the size to allocate on the next request */
470     if(m_lAllocSize != lAllocMax)
471         m_lAllocSize <<= 1;
472
473     if(m_nHeaps != 0) {
474         /* Expand the last allocated heap */
475         ptr = HeapReAlloc(m_hHeap, HEAP_REALLOC_IN_PLACE_ONLY|HEAP_ZERO_MEMORY|HEAP_NO_SERIALIZE,
476                 m_heaps[m_nHeaps-1].base,
477                 m_heaps[m_nHeaps-1].len + size);
478         if(ptr != 0) {
479             HeapAdd(((char*)ptr) + m_heaps[m_nHeaps-1].len, size);
480             return -1;
481         }
482     }
483
484     /*
485      * if we didn't expand a block to cover the requested size
486      * allocate a new Heap
487      * the size of this block must include the additional dummy tags at either end
488      * the above ROUND_UP64K may not have added any memory to include this.
489      */
490     if(size == requestSize)
491         size = (size_t)ROUND_UP64K(requestSize+(sizeofTag*2));
492
493     ptr = HeapAlloc(m_hHeap, HEAP_ZERO_MEMORY|HEAP_NO_SERIALIZE, size);
494     if(ptr == 0) {
495         MEMODSlx("HeapAlloc failed on size!!!", size);
496         return 0;
497     }
498
499     HeapAdd(ptr, size);
500     return -1;
501 }
502
503 int VMem::HeapAdd(void *p, size_t size)
504 {   /* if the block can be succesfully added to the heap, returns 0; otherwise -1. */
505     int index;
506
507     /* Check size, then round size down to next long word boundary. */
508     if(size < minAllocSize)
509         return -1;
510
511     size = (size_t)ROUND_DOWN(size);
512     PBLOCK ptr = (PBLOCK)p;
513
514     /*
515      * Search for another heap area that's contiguous with the bottom of this new area.
516      * (It should be extremely unusual to find one that's contiguous with the top).
517      */
518     for(index = 0; index < m_nHeaps; ++index) {
519         if(ptr == m_heaps[index].base + (int)m_heaps[index].len) {
520             /*
521              * The new block is contiguous with a previously allocated heap area.  Add its
522              * length to that of the previous heap.  Merge it with the the dummy end-of-heap
523              * area marker of the previous heap.
524              */
525             m_heaps[index].len += size;
526             break;
527         }
528     }
529
530     if(index == m_nHeaps) {
531         /* The new block is not contiguous.  Add it to the heap list. */
532         if(m_nHeaps == maxHeaps) {
533             return -1;  /* too many non-contiguous heaps */
534         }
535         m_heaps[m_nHeaps].base = ptr;
536         m_heaps[m_nHeaps].len = size;
537         m_nHeaps++;
538
539         /*
540          * Reserve the first LONG in the block for the ending boundary tag of a dummy
541          * block at the start of the heap area.
542          */
543         size -= minBlockSize;
544         ptr += minBlockSize;
545         PSIZE(ptr) = 1; /* mark the dummy previous block as allocated */
546     }
547
548     /*
549      * Convert the heap to one large block.  Set up its boundary tags, and those of
550      * marker block after it.  The marker block before the heap will already have
551      * been set up if this heap is not contiguous with the end of another heap.
552      */
553     SetTags(ptr, size | 1);
554     PBLOCK next = ptr + size;   /* point to dummy end block */
555     SIZE(next) = 1;     /* mark the dummy end block as allocated */
556
557     /*
558      * Link the block to the start of the free list by calling free().
559      * This will merge the block with any adjacent free blocks.
560      */
561     Free(ptr);
562     return 0;
563 }
564
565
566 void* VMem::Expand(void* block, size_t size)
567 {
568     /*
569      * Adjust the size of the block to be a multiple of sizeof(long), and add the
570      * overhead for the boundary tags.  Disallow negative or zero sizes.
571      */
572     size_t realsize = (size < blockOverhead) ? minAllocSize : (size_t)ROUND_UP(size) + minBlockSize;
573     if((int)realsize < minAllocSize || size == 0)
574         return NULL;
575
576     PBLOCK ptr = (PBLOCK)block; 
577
578     /* if the current size is the same as requested, do nothing. */
579     size_t cursize = SIZE(ptr) & ~1;
580     if(cursize == realsize) {
581         return block;
582     }
583
584     /* if the block is being shrunk, convert the remainder of the block into a new free block. */
585     if(realsize <= cursize) {
586         size_t nextsize = cursize - realsize;   /* size of new remainder block */
587         if(nextsize >= minAllocSize) {
588             /*
589              * Split the block
590              * Set boundary tags for the resized block and the new block.
591              */
592             SetTags(ptr, realsize | 1);
593             ptr += realsize;
594
595             /*
596              * add the new block to the free list.
597              * call Free to merge this block with next block if free
598              */
599             SetTags(ptr, nextsize | 1);
600             Free(ptr);
601         }
602
603         return block;
604     }
605
606     PBLOCK next = ptr + cursize;
607     size_t nextsize = SIZE(next);
608
609     /* Check the next block for consistency.*/
610     if((nextsize&1) == 0 && (nextsize + cursize) >= realsize) {
611         /*
612          * The next block is free and big enough.  Add the part that's needed
613          * to our block, and split the remainder off into a new block.
614          */
615         if(m_pRover == next)
616             m_pRover = NEXT(next);
617
618         /* Unlink the next block from the free list. */
619         Unlink(next);
620         cursize += nextsize;    /* combine sizes */
621
622         size_t rem = cursize - realsize;        /* size of remainder */
623         if(rem >= minAllocSize) {
624             /*
625              * The remainder is big enough to be a new block.
626              * Set boundary tags for the resized block and the new block.
627              */
628             next = ptr + realsize;
629             /*
630              * add the new block to the free list.
631              * next block cannot be free
632              */
633             SetTags(next, rem);
634             AddToFreeList(next, m_pFreeList);
635             cursize = realsize;
636         }
637         /* Set the boundary tags to mark it as allocated. */
638         SetTags(ptr, cursize | 1);
639         return ((void *)ptr);
640     }
641     return NULL;
642 }
643
644 #ifdef _DEBUG_MEM
645 #define LOG_FILENAME "P:\\Apps\\Perl\\Result.txt"
646
647 void MemoryUsageMessage(char *str, long x, long y, int c)
648 {
649     static FILE* fp = NULL;
650     char szBuffer[512];
651     if(str) {
652         if(!fp)
653             fp = fopen(LOG_FILENAME, "w");
654         sprintf(szBuffer, str, x, y, c);
655         fputs(szBuffer, fp);
656     }
657     else {
658         fflush(fp);
659         fclose(fp);
660     }
661 }
662
663 void VMem::WalkHeap(void)
664 {
665     if(!m_pRover) {
666         MemoryUsageMessage("VMem heaps used %d\n", m_nHeaps, 0, 0);
667     }
668
669     /* Walk all the heaps - verify structures */
670     for(int index = 0; index < m_nHeaps; ++index) {
671         PBLOCK ptr = m_heaps[index].base;
672         size_t size = m_heaps[index].len;
673         ASSERT(HeapValidate(m_hHeap, HEAP_NO_SERIALIZE, p));
674
675         /* set over reserved header block */
676         size -= minBlockSize;
677         ptr += minBlockSize;
678         PBLOCK pLast = ptr + size;
679         ASSERT(PSIZE(ptr) == 1); /* dummy previous block is allocated */
680         ASSERT(SIZE(pLast) == 1); /* dummy next block is allocated */
681         while(ptr < pLast) {
682             ASSERT(ptr > m_heaps[index].base);
683             size_t cursize = SIZE(ptr) & ~1;
684             ASSERT((PSIZE(ptr+cursize) & ~1) == cursize);
685             if(!m_pRover) {
686                 MemoryUsageMessage("Memory Block %08x: Size %08x %c\n", (long)ptr, cursize, (SIZE(p)&1) ? 'x' : ' ');
687             }
688             if(!(SIZE(ptr)&1)) {
689                 /* this block is on the free list */
690                 PBLOCK tmp = NEXT(ptr);
691                 while(tmp != ptr) {
692                     ASSERT((SIZE(tmp)&1)==0);
693                     if(tmp == m_pFreeList)
694                         break;
695                     ASSERT(NEXT(tmp));
696                     tmp = NEXT(tmp);
697                 }
698                 if(tmp == ptr) {
699                     MemoryUsageMessage("Memory Block %08x: Size %08x free but not in free list\n", (long)ptr, cursize, 0);
700                 }
701             }
702             ptr += cursize;
703         }
704     }
705     if(!m_pRover) {
706         MemoryUsageMessage(NULL, 0, 0, 0);
707     }
708 }
709 #endif
710
711 #endif  /* ___VMEM_H_INC___ */