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