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