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