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