Zero entries were skipped, fix from Adrian Goalby
[p5sagit/p5-mst-13.2.git] / win32 / vmem.h
CommitLineData
7766f137 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
36const long lAllocStart = 0x00010000; /* start at 64K */
37const long minBlockSize = sizeof(void*)*2;
38const long sizeofTag = sizeof(long);
39const long blockOverhead = sizeofTag*2;
40const long minAllocSize = minBlockSize+blockOverhead;
41
42typedef 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)))
53inline 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)))
67inline void SetLink(PBLOCK block, PBLOCK prev, PBLOCK next)
68{
69 PREV(block) = prev;
70 NEXT(block) = next;
71}
72inline void Unlink(PBLOCK p)
73{
74 PBLOCK next = NEXT(p);
75 PBLOCK prev = PREV(p);
76 NEXT(prev) = next;
77 PREV(next) = prev;
78}
79inline 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
99const int maxHeaps = 64;
100const long lAllocMax = 0x80000000; /* max size of allocation */
101
102typedef struct _HeapRec
103{
104 PBLOCK base; /* base of heap area */
105 ULONG len; /* size of heap area */
106} HeapRec;
107
108
109class VMem
110{
111public:
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
130protected:
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
152inline void MEMODS(char *str)
153{
154 OutputDebugString(str);
155 OutputDebugString("\n");
156}
157
158inline 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
179VMem::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
192VMem::~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
201void 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
209void 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
222void* 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
284void* 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
361void 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
412void VMem::GetLock(void)
413{
414 EnterCriticalSection(&m_cs);
415}
416
417void VMem::FreeLock(void)
418{
419 LeaveCriticalSection(&m_cs);
420}
421
422int VMem::IsLocked(void)
423{
90430aa1 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. */
7766f137 428 BOOL bAccessed = TryEnterCriticalSection(&m_cs);
429 if(bAccessed) {
430 LeaveCriticalSection(&m_cs);
431 }
432 return !bAccessed;
90430aa1 433#else
434 ASSERT(0); /* alarm bells for when somebody calls this */
435 return 0;
436#endif
7766f137 437}
438
439
440long VMem::Release(void)
441{
442 long lCount = InterlockedDecrement(&m_lRefCount);
443 if(!lCount)
444 delete this;
445 return lCount;
446}
447
448long VMem::AddRef(void)
449{
450 long lCount = InterlockedIncrement(&m_lRefCount);
451 return lCount;
452}
453
454
455int 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
503int 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
566void* 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
647void 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
663void 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___ */