win32/vmem.h

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