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