home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / mslang / vm / src / alloc.c next >
Encoding:
C/C++ Source or Header  |  1993-12-15  |  12.9 KB  |  451 lines
  1. /***
  2. *alloc.c - Allocate memory routines
  3. *
  4. *       Copyright (c) 1989-1992, Microsoft Corporation.  All rights reserved.
  5. *
  6. *******************************************************************************/
  7.  
  8. #include <version.h>
  9. #include <vmassert.h>
  10. #include <stdlib.h>
  11. #include <string.h>
  12. #include <vmm.h>
  13. #include <vmbm.h>
  14.  
  15. VPVOID pascal near __VpAllocAtEnd(unsigned);
  16. VPVOID near pascal __VpAllocInFree(unsigned);
  17.  
  18. // global variables to manage
  19. GVMBM   _gvmbm = {cbMaxFreeSize};
  20.  
  21.  
  22. /*** HbkVmAllocate
  23. *
  24. * Purpose:  Allocate in vm cb bytes of memory
  25. *
  26. * Input:
  27. *   cb      The minimum number of bytes to allocate. Zero length allocations
  28. *               are allowed.
  29. *
  30. * Output:
  31. *  Returns:
  32. *           An HBK representing the virtual memory allocated. NULL
  33. *           if an error.
  34. *
  35. * Exceptions:
  36. *
  37. * Notes:
  38. *
  39. *     Allocated                Free                      Page
  40. *       Block                    Block                    Block
  41. *
  42. *    FEDCBA9876543210        FEDCBA9876543210        FEDCBA9876543210
  43. *   +----------------+      +----------------+      +----------------+
  44. *   |                |      |                |      |                |
  45. *   |                |      |   Free         |      |                |
  46. *   |   Allocated    |      |      Space     |      |   Allocated    |
  47. *   |     Space      |      |                |E     |     Pages      |
  48. *   |                |      +----------------+      |                |
  49. *   |                |      |  Free Next     |      |                |
  50. *   |                |      |    VM Ptr      |A     |                |
  51. *   |                |      +----------------+      |                |
  52. *   |                |      |   Free Back    |      |                |
  53. *   |                |6     |    VM Ptr      |6     |                |6
  54. *   +----------------+      +----------------+      +----------------+
  55. *   |   cbBack     |C|4     |     cbBack   |C|4     |       0        |4
  56. *   +----------------+      +----------------+      +----------------+
  57. *   |RRRRRR00| cLock |2     |RRRRRR01| cLock |2     |RRRRRR10| cLock |2
  58. *   +----------------+      +----------------+      +----------------+
  59. *   |   cbSize     |C|0     |   cbSize     |C|0     |     cPage      |0
  60. *   +----------------+      +----------------+      +----------------+
  61. *
  62. *
  63. *   Where:
  64. *       cbSize:         The nbr of bytes to the end of the block
  65. *       cbBack          The nbr of bytes of the previous block
  66. *       C:              The next/back block is adjacent.
  67. *       Back VM Ptr:    The VM Pointer to the previously allocated block.
  68. *       Free Next:      The VM pointer to the next free block.
  69. *       Free Back:      The VM pointer to the previouse free block.
  70. *
  71. *   What is known:
  72. *
  73. *   1)  Any free block is at least HDF is size. If not, it is merged
  74. *           in with the previous allocation.
  75. *
  76. *   2)  sizeof(HDF) >= sizeof(HDB) >= sizeof(HDP)
  77. *
  78. *   3)  cbBack is zero if the previous block is not adjacent.
  79. *
  80. *************************************************************************/
  81. HBK VMFUNC __HbkVmAllocate(
  82. unsigned long cb
  83. ) {
  84.    unsigned long cbT;
  85.  
  86.    VPVOID       vp = vpNil;
  87.    PHDP phdb;
  88.  
  89.    if (!_fVmInit)
  90.       return NULL;
  91.  
  92.    if( cb > cbMaxAlloc )
  93.       return(NULL);
  94.  
  95.    // round the size to an int boundary
  96.    cb = ((cb + sizeof(int) - 1) / sizeof(int)) * sizeof(int);
  97.  
  98.    // determine the actual size to allocate, must be big enough for a free
  99.    cbT = max(cb + sizeof(HDB), sizeof(HDF));
  100.  
  101.    // If the allocation is big, or the allocation is close to a page
  102.    // size, then put it in as pages and not in the allocation list
  103.    if( (cbT > cbBig  ||  cbT == cbVmPage  ||
  104.       (cbVmPage - (cbT % cbVmPage)) < cbClose)    &&
  105.       (vp = __VpVmAllocateCb(cb + sizeof(HDB)))               )
  106.    {
  107.  
  108.       // load the first page
  109.       phdb = __PVmLoadVp(vp, TRUE);
  110.  
  111.       // initialize the page stuff
  112.       _fmemset( phdb, 0, sizeof(HDB) );
  113.       phdb->cPage       = (unsigned short) ((cb + sizeof(HDB) + cbVmPage - 1) / cbVmPage);
  114.       phdb->fByPage     = TRUE;
  115.    }
  116.  
  117.    // if we know we have an item in the list see if it is big enough
  118.    else if(cbT <= cbBig  &&
  119.          !(_gvmbm.cFree  &&  (vp = __VpAllocInFree((unsigned) cbT))) )
  120.       vp = __VpAllocAtEnd( (unsigned) cbT );
  121.  
  122.  
  123.    // check the free list
  124. #ifdef VMDEBUG
  125.    {
  126.       HBK       hbk, hbkBackHdf;
  127.       PHDF      phdf;
  128.  
  129.       hbk = _gvmbm.hbkFreeStart;
  130.       hbkBackHdf = NULL;
  131.       while( hbk )
  132.       {
  133.      phdf = __PVmLoadVp( (VPVOID) hbk, FALSE );
  134.      Assert( phdf != NULL );
  135.      Assert( phdf->fFree == TRUE );
  136.      Assert( phdf->hbkBackHdf == hbkBackHdf );
  137.      hbkBackHdf = hbk;
  138.      hbk = phdf->hbkNextHdf;
  139.       }
  140.    }
  141. #endif
  142.  
  143.    return((HBK) vp);
  144. }
  145.  
  146. /*** VpAllocAtEnd
  147. *
  148. * Purpose:  Allocate cb bytes at the end of the allocate chain
  149. *
  150. * Input:
  151. *   cb      The minimum number of bytes to allocate. This count MUST
  152. *               include the bytes for the header too.
  153. *
  154. * Output:
  155. *  Returns:
  156. *           A a vp to the block allocated
  157. *
  158. * Exceptions:
  159. *
  160. * Notes:
  161. *
  162. *   It is known that no current free pages are big enough because then
  163. *       were checked already
  164. *
  165. *   All sizes are rounded up to a word.
  166. *   If there is extra space in the current page, it is marked as free.
  167. *   If the extra space is not big enough to contain an HDF, then the
  168. *       space is included as part of the allocation.
  169. *
  170. *************************************************************************/
  171. VPVOID pascal near __VpAllocAtEnd(
  172. unsigned cb
  173. ) {
  174. VPVOID      vp = vpNil, vpFree;
  175. SZBK        szbk;
  176. HBK         hbkBack = _gvmbm.hbkLastBlock;
  177. PHDF        phdf;
  178. PHDB        phdb;
  179. unsigned    cbAllocSize;
  180.  
  181. // the size must include the HDB, so it better be >=.
  182. Assert( cb >= sizeof(HDF) );
  183. _fmemset( &szbk, 0, sizeof(SZBK) );
  184.  
  185. // go ahead and allocate the needed pages
  186. // realize that one few pages may be needed if the VMs are adjacent.
  187. if( (vp = __VpVmAllocateCb(cb + sizeof(HDB))) ) {
  188.  
  189.     cbAllocSize = (unsigned) (((cb + (unsigned long) cbVmPage - 1) / cbVmPage) * cbVmPage);
  190.  
  191.     // see if a free block needs to be made
  192.     if( cbAllocSize >= cb + sizeof(HDF) ) {
  193.  
  194.     // get the free pointer
  195.     vpFree = vp + cb;
  196.  
  197.     // make the free header
  198.     phdf = __PVmLoadVp(vpFree, TRUE);
  199.     _fmemset(phdf, 0, sizeof(HDF));
  200.     phdf->fFree             = TRUE;
  201.     phdf->cbSize            = CbMakeSize(cbAllocSize - cb, 0);
  202.     phdf->szbkBack.cbSize   = CbMakeSize(cb, 1);
  203.  
  204.     // add to the free list, and update the last block pointer
  205.     __VmFreeLinkEnd( (HBK) vpFree, cbAllocSize - cb );
  206.     _gvmbm.hbkLastBlock  = (HBK) vpFree;
  207.     }
  208.  
  209.     else {
  210.     vpFree = vpNil;
  211.     cb = cbAllocSize;
  212.     _gvmbm.hbkLastBlock = (HBK) vp;
  213.     }
  214.  
  215.     // the vp pointer points to the start of the block, initalize it
  216.     phdb = __PVmLoadVp(vp, TRUE);
  217.  
  218.     // initialize the new allocated block
  219.     _fmemset( phdb, 0, sizeof(HDB) );
  220.     phdb->cbSize = CbMakeSize(cb,0);
  221.     phdb->szbkBack = szbk;
  222.     phdb->fAdjacent = (vpFree != vpNil);
  223.  
  224.     }
  225.  
  226. // return the VM pointer
  227. return(vp);
  228. }
  229.  
  230. /*** VpAllocInFree
  231. *
  232. * Purpose:  Allocate cb bytes in the free list
  233. *
  234. * Input:
  235. *   cb      The minimum number of bytes to allocate. This count MUST
  236. *               include the bytes for the header too.
  237. *
  238. * Output:
  239. *  Returns:
  240. *           A a vp to the block allocated
  241. *
  242. * Exceptions:
  243. *
  244. * Notes:
  245. *
  246. *   All sizes are rounded up to a word.
  247. *   If there is extra space in the block, it is marked as free.
  248. *   If the extra space is not big enough to contain an HDF within the
  249. *   same page, then the space is included as part of the allocation.
  250. *
  251. *************************************************************************/
  252. VPVOID near pascal __VpAllocInFree(
  253. unsigned cb
  254. ) {
  255.  
  256. unsigned    cbMaxFree = 0;
  257. VPVOID      vp  = vpNil, vpFree;
  258. PHDF        phdf;
  259. PHDB        phdb;
  260. HBK         hbk;
  261. unsigned    cbFree;
  262. HDF         hdf;
  263.  
  264. Assert( cb >= sizeof(HDF) );
  265.  
  266. // If we are to search the free list
  267. if( _gvmbm.cFree  &&  _gvmbm.cbMaxFree >= cb ) {
  268.  
  269.     hbk = _gvmbm.hbkFreeLast;
  270.  
  271.     // look until we find a page
  272.     while( hbk ) {
  273.  
  274.     phdf = __PVmLoadVp((VPVOID) hbk, FALSE);
  275.     Assert( phdf->fFree == TRUE );
  276.  
  277.     // is it big enough?
  278.     if( CbGetSize(phdf->cbSize) >= cb ) {
  279.  
  280.         vp = (VPVOID) hbk;
  281.  
  282.         // see if we are going to corrupt the max free size
  283.         // information that we have. If we found the big one
  284.         // then we don't know what the max is. Set it to the
  285.         // absolute max so we search the list again.
  286.         cbFree      = CbGetSize(phdf->cbSize);
  287.         if( _gvmbm.cbMaxFree == cbFree)
  288.         _gvmbm.cbMaxFree = cbMaxFreeSize;
  289.  
  290.         // save the original state
  291.         hdf = *phdf;
  292.  
  293.         break;
  294.         }
  295.  
  296.     cbMaxFree = max(cbMaxFree, CbGetSize(phdf->cbSize));
  297.     hbk = phdf->hbkBackHdf;
  298.     }
  299.  
  300.     // if we didn't find a vp, then we searched the whole
  301.     // free list and we know the max size
  302.     if( !vp ) {
  303.     Assert( cbMaxFree <= _gvmbm.cbMaxFree );
  304.     _gvmbm.cbMaxFree = cbMaxFree;
  305.     }
  306.     }
  307.  
  308. // only if we found a free block big enough
  309. // we also know the page is loaded and pointed to by phdf
  310. if( vp ) {
  311.  
  312.     _gvmbm.cFree--;
  313.  
  314.     // if no room for the free block
  315.     if( (cbFree - cb) < sizeof(HDF) ) {
  316.     cb = cbFree;
  317.     cbFree = 0;
  318.     vpFree = vpNil;
  319.     }
  320.  
  321.     // see if we can get the allocated block on one page by choosing the
  322.     // top half of the free area rather than the bottom.
  323.     else if( vp != ((VPVOID) _gvmbm.hbkLastBlock)    &&
  324.          VpVmPageVp(vp + cbFree - cb)         ==
  325.          VpVmPageVp(vp + cbFree - 1)          ) {
  326.     vpFree = vp;
  327.     vp = vp + cbFree - cb;
  328.     cbFree -= cb;
  329.     }
  330.  
  331.     // if the free header is on one page, set the free mark
  332.     else if( VpVmPageVp(vp + cb) ==
  333.          VpVmPageVp(vp + cb + sizeof(HDF) - 1) ) {
  334.     vpFree = vp + cb;
  335.     cbFree -= cb;
  336.     }
  337.  
  338.     // see if we can move the free up some
  339.     else if( (VpVmPageVp(vp + cb) + (unsigned long) cbVmPage + sizeof(HDF))  <=
  340.          (vp + cbFree) ) {
  341.     vpFree = VpVmPageVp(vp + cb) + (unsigned long) cbVmPage;
  342.     cb += cbEndPage((unsigned)vp + cb);
  343.     cbFree -= cb;
  344.     }
  345.  
  346.     // page breaks are against us, we have to keep the block as is
  347.     else {
  348.     cb = cbFree;
  349.     cbFree = 0;
  350.     vpFree = vpNil;
  351.     }
  352.  
  353.     // since we found a free block, _gvmbm.hbkLastBlock can't be NULL
  354.     // But if either vp or vpFree == _gvmbm.hbkLastBlock, then the
  355.     // other pointer( vpFree or vp respectively) must be the new end.
  356.     Assert( _gvmbm.hbkLastBlock != NULL );
  357.     if( vpFree  &&  vp == (VPVOID) _gvmbm.hbkLastBlock )
  358.     _gvmbm.hbkLastBlock = (HBK) vpFree;
  359.     else if( vpFree == (VPVOID) _gvmbm.hbkLastBlock )
  360.     _gvmbm.hbkLastBlock = (HBK) vp;
  361.  
  362.     // do the free page first, this way the allocated page will be
  363.     // loaded on return
  364.     if( cbFree ) {
  365.  
  366.     phdf = __PVmLoadVp(vpFree, TRUE);
  367.  
  368.     _fmemset(phdf, 0, sizeof(HDF) );
  369.     phdf->cbSize        = CbMakeSize(cbFree, FALSE);
  370.     phdf->fFree         = TRUE;
  371.  
  372.     // I know that if the free is on the bottom, then the free block
  373.     // is still in the free list. Also it is known that the allocated
  374.     // block is adjacent to the free (doesn't have to be in the
  375.     // same page thougth, just adjacent vm).
  376.     if(vpFree < vp) {
  377.         phdf->szbkBack      = hdf.szbkBack;
  378.         phdf->fAdjacent     = TRUE;
  379.         phdf->hbkBackHdf    = hdf.hbkBackHdf;
  380.         phdf->hbkNextHdf    = hdf.hbkNextHdf;
  381.         _gvmbm.cFree++;
  382.  
  383.         // fixup the next block to have the free size
  384.         if(hdf.fAdjacent) {
  385.         phdb = __PVmLoadVp((vp + cb), TRUE);
  386.         phdb->szbkBack.cbSize   = CbMakeSize(cb, TRUE);
  387.         }
  388.         }
  389.  
  390.     // if vp < vpFree, then we know the old vp pointer contains
  391.     // the linkage to the free list
  392.     else {
  393.         phdf->szbkBack.cbSize   = CbMakeSize(cb, TRUE);
  394.         phdf->fAdjacent         = hdf.fAdjacent;
  395.  
  396.         __VmFreeLinkIn((HBK) vpFree, cbFree,
  397.                    hdf.hbkBackHdf, hdf.hbkNextHdf);
  398.  
  399.         // fixup the next block to have the free size
  400.         if(hdf.fAdjacent) {
  401.         phdb = __PVmLoadVp((vpFree + cbFree), TRUE);
  402.         phdb->szbkBack.cbSize   = CbMakeSize(cbFree, TRUE);
  403.         }
  404.         }
  405.     }
  406.  
  407.     // the free entry no longer exists so fix up the linkage
  408.     else
  409.         __VmFreeLink(hdf.hbkBackHdf, hdf.hbkNextHdf);
  410.  
  411.     // now fix up the vp
  412.     phdb = __PVmLoadVp(vp, TRUE);
  413.     _fmemset(phdb, 0, sizeof(HDB));
  414.     phdb->cbSize = CbMakeSize(cb, hdf.fAdjacent);
  415.  
  416.     // if the vp is in the lower spot.
  417.     if( !vpFree  ||  vp < vpFree ) {
  418.  
  419.     phdb->szbkBack   = hdf.szbkBack;
  420.     phdb->fAdjacent  = ((vpFree != vpNil) || hdf.fAdjacent);
  421.     }
  422.  
  423.     // the vp is in the upper page, only need the back pointer
  424.     else
  425.     phdb->szbkBack.cbSize    = CbMakeSize(cbFree, TRUE);
  426.     }
  427.  
  428. return(vp);
  429. }
  430.  
  431. /*** VmInitialize
  432. *
  433. * Purpose:
  434. *
  435. * Input:
  436. *
  437. * Output:
  438. *  Returns:
  439. *
  440. * Exceptions:
  441. *
  442. * Notes:
  443. *
  444. *
  445. *************************************************************************/
  446. int VMFUNC __VmInitialize( unsigned cVmParaMin, unsigned cParaVmDosMax, unsigned bitSwapArea ) {
  447. _fmemset(&_gvmbm, 0, sizeof(GVMBM));
  448. _gvmbm.cbMaxFree = cbMaxFreeSize;
  449. return(__FVmInitialize(cVmParaMin, cParaVmDosMax, bitSwapArea));
  450. };
  451.