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