lib0043.html

Memory Management—Algorithms and implementation in C/C++ Introduction Chapter 1 - Memory Manag

    <span style="background-color:d9d9d9">forceCollection();</span>

    <span style="background-color:d9d9d9">closeMemMgr();</span>
    <span style="background-color:d9d9d9">return;</span>

<span style="background-color:d9d9d9">}/*end debugTest----------------------------------------------*/</span>

<span style="background-color:d9d9d9">void main()</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">//need this for mark-sweep</span>
    <span style="background-color:d9d9d9">getTOS();</span>

    <span style="background-color:d9d9d9">//for the debug test, should activate debug macros in</span>
      <span style="background-color:d9d9d9">mallocVx.cpp</span>
    <span style="background-color:d9d9d9">//debugTest();</span>

    <span style="background-color:d9d9d9">//for the performance test, should comment out debug macros</span>
    <span style="background-color:d9d9d9">PerformanceTestDriver();</span>
    <span style="background-color:d9d9d9">return;</span>

<span style="background-color:d9d9d9">}/*end main --------------------------------------------------*/</span>
</pre>
</div>
<p class="para">You might notice a weird-looking function called <span class="fixed">getTOS()</span>, which is invoked in <span class="fixed">main()</span>. This is the first statement in <span class="fixed">main()</span>, and it resolves to a macro defined in <span class="fixed">memmgr.cpp</span>. This macro, which stands for get Top Of the Stack, obtains the value of <span class="fixed">EBP</span> register so that my code knows where to stop its scan of the stack while looking for pointers. The <span class="fixed">main()</span> function, like other C functions, has a prologue that sets up the <span class="fixed">EBP</span> register as a stack frame pointer.</p>
<div class="informalexample">
<pre class="literallayout">
_main PROC NEAR
      push ebp
      mov  ebp, esp
</pre>
</div>
<p class="last-para">By saving the value of <span class="fixed">EBP</span> as soon as <span class="fixed">main()</span> begins, I ensure that I can scan as much of the stack as legally possible.</p>
<a></a>
</div>
<div class="section">
<h4 class="sect4-title">mallocV5.cpp</h4>
<p class="first-para">Because we are now in the domain of automatic memory management, I disabled the <span class="fixed">newFree()</span> function that has traditionally been defined in this file. The <span class="fixed">newMalloc()</span> function is still operational, albeit using a different underlying object. If you wish to perform a debug/diagnostic test, you will need to activate the <span class="fixed">DEBUG_XXX</span> macros.</p>
<p class="para">You also might want to keep in mind that I have included a <span class="fixed">forceCollection()</span> wrapper function that allows you to invoke the garbage collector.</p>
<a name="583"></a><a name="IDX-310"></a>
<div class="informalexample">
<pre class="literallayout">
<span style="background-color:d9d9d9">#include&lt;stdio.h&gt;</span>
<span style="background-color:d9d9d9">#include&lt;stdlib.h&gt;</span>
<span style="background-color:d9d9d9">#include&lt;windows.h&gt;</span>

<span style="background-color:d9d9d9">//#define DEBUG_MS_MEM_MGR</span>
<span style="background-color:d9d9d9">//#define DEBUG_MALLOCV5</span>

<span style="background-color:d9d9d9">#include&lt;memmgr.cpp&gt;</span>

<span style="background-color:d9d9d9">/*</span>
<span style="background-color:d9d9d9">wrapper functions</span>
<span style="background-color:d9d9d9">*/</span>

<span style="background-color:d9d9d9">MarkSweepMemoryManager *mmptr;</span>

<span style="background-color:d9d9d9">void initMemMgr(unsigned long totalbytes,unsigned char period)</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">mmptr = new MarkSweepMemoryManager(totalbytes,period);</span>
<span style="background-color:d9d9d9">}</span>

<span style="background-color:d9d9d9">void closeMemMgr()</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">delete(mmptr);</span>
<span style="background-color:d9d9d9">}</span>

<span style="background-color:d9d9d9">void *newMalloc(unsigned long size)</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">void *ptr = (*mmptr).allocate(size);</span>

<span style="background-color:d9d9d9">#ifdef DEBUG_MALLOCV5</span>
    <span style="background-color:d9d9d9">(*mmptr) .printState();</span>
<span style="background-color:d9d9d9">#endif</span>

    <span style="background-color:d9d9d9">return(ptr);</span>
<span style="background-color:d9d9d9">}</span>

<span style="background-color:d9d9d9">void forceCollection()</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">(*mmptr) .forceCollection();</span>
    <span style="background-color:d9d9d9">return;</span>
<span style="background-color:d9d9d9">}</span>

<span style="background-color:d9d9d9">void newFree(void *ptr)</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">printf("newFree(): cannot free %p\n",ptr);</span>
    <span style="background-color:d9d9d9">printf("newFree(): not implemented, using garbage</span>
            <span style="background-color:d9d9d9">collector\n");</span>
    <span style="background-color:d9d9d9">return;</span>
<span style="background-color:d9d9d9">}</span><a name="584"></a><a name="IDX-311"></a>
</pre>
</div>
<a></a>
</div>
<div class="section">
<h4 class="sect4-title">perform.cpp</h4>
<p class="first-para">The <span class="fixed">PerformanceTest</span> class defined in this file has not been modified very much. The only thing that changed was the implementation of the <span class="fixed">runTest()</span> member function. Specifically, I had to remove the calls to <span class="fixed">newFree()</span>, which are no longer valid. I also replaced the array of <span class="fixed">void*addr []</span> pointers with a single <span class="fixed">addr</span> pointer so that I could overwrite its contents and produce garbage.</p>
<div class="informalexample">
<pre class="literallayout">
<span style="background-color:d9d9d9">unsigned long PerformanceTest::runTest()</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">unsigned long *allocs;</span>
    <span style="background-color:d9d9d9">unsigned long i;</span>
    <span style="background-color:d9d9d9">unsigned long ticks1,ticks2;</span>

    <span style="background-color:d9d9d9">void *addr;</span>

    <span style="background-color:d9d9d9">/*create stream of allocation values*/</span>

    <span style="background-color:d9d9d9">allocs = (unsigned long *)malloc(sizeof(long)*nAllocations);</span>
    <span style="background-color:d9d9d9">if(allocs==NULL)</span>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">printf("could not allocate malloc() request stream\n");</span>
        <span style="background-color:d9d9d9">exit (1);</span>
    <span style="background-color:d9d9d9">}</span>

    <span style="background-color:d9d9d9">getAllocArray(allocs);</span>

    <span style="background-color:d9d9d9">/*start timer and do some work*/</span>

    <span style="background-color:d9d9d9">initMemMgr(1024*1024,200);</span>

    <span style="background-color:d9d9d9">printf("PerformanceTest::runTest(): time whistle blown\n");</span>

    <span style="background-color:d9d9d9">ticks1 = GetTickCount();</span>

    <span style="background-color:d9d9d9">for(i=0;i&lt;nAllocations;i++)</span>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">addr = (char *)newMalloc(allocs[i]);</span>
        <span style="background-color:d9d9d9">if(addr==NULL)</span>
        <span style="background-color:d9d9d9">{</span>
            <span style="background-color:d9d9d9">printf("mallco()=addr[%lu]=%lu failed\n",i,addr);</span>
            <span style="background-color:d9d9d9">exit(1);</span>
        <span style="background-color:d9d9d9">}</span>
    <span style="background-color:d9d9d9">}</span>

    <span style="background-color:d9d9d9">forceCollection();</span>

    <span style="background-color:d9d9d9">ticks2 = GetTickCount();</span><a name="585"></a><a name="IDX-312"></a>

    <span style="background-color:d9d9d9">printf("PerformanceTest::runTest(): race has ended\n");</span>

    <span style="background-color:d9d9d9">closeMemMgr();</span>

    <span style="background-color:d9d9d9">free(allocs);</span>

    <span style="background-color:d9d9d9">return(ticks2-ticks1);</span>

<span style="background-color:d9d9d9">}/*end runTest------------------------------------------------*/</span>
</pre>
</div>
<a></a>
</div>
<div class="section">
<h4 class="sect4-title">memmgr.cpp</h4>
<p class="first-para">The <span class="fixed">MarkSweepMemoryManager</span> class defined in this file is basically an extended version of the <span class="fixed">SequentialFitMemoryManager</span>. To give you an idea of how this class operates, I have enumerated the possible paths of execution for this class in <a class="internaljump" href="#ch05fig09">Figure 5.9</a>.</p>
<div class="figure">
<a name="586"></a><a name="ch05fig09"></a><span class="figuremediaobject"><a href="images/fig340%5F01%5F0%2Ejpg" NAME="IMG_89" target="_parent"><img src="images/fig340_01.jpg" height="225" width="350" alt="Click To expand" border="0"></a></span>
<br style="line-height: 1">
<span class="figure-title"><span class="figure-titlelabel">Figure 5.9</span></span>
</div>
<p class="para">Most of what happens is performed as a result of invoking the <span class="fixed">allocate()</span> function. Normally, <span class="fixed">allocate()</span> will reserve storage and split free blocks. However, if the <span class="fixed">ticks</span> variable has hit its <span class="fixed">period</span> value, the garbage collector will kick into action via the <span class="fixed">trace()</span> function.</p>
<div class="informalexample">
<pre class="literallayout">
<span style="background-color:d9d9d9">#ifdef  DEBUG_MS_MEM_MGR</span>
<span style="background-color:d9d9d9">#define MSG0(arg);        printf(arg);</span>
<span style="background-color:d9d9d9">#define MSG1(arg1,arg2);  printf(arg1,arg2);</span>
<span style="background-color:d9d9d9">#else</span>
<span style="background-color:d9d9d9">#define MSG0(arg);</span>
<span style="background-color:d9d9d9">#define MSG1(arg1,arg2);</span><a name="587"></a><a name="IDX-313"></a>
<span style="background-color:d9d9d9">#endif</span>

<span style="background-color:d9d9d9">#define U1 unsigned char</span>
<span style="background-color:d9d9d9">#define U4 unsigned long</span>

<span style="background-color:d9d9d9">/*</span>
    <span style="background-color:d9d9d9">list element format</span>
                <span style="background-color:d9d9d9">|0  3||4  7||  8  ||9 12||13 .. n|</span>
                <span style="background-color:d9d9d9">[PREV][NEXT][STATE][SIZE][payload]</span>
                  <span style="background-color:d9d9d9">U4    U4    U1    U4     ?</span>

    <span style="background-color:d9d9d9">byte allocated/freed is address of first byte of payload</span>
    <span style="background-color:d9d9d9">header = 13 bytes</span>

    <span style="background-color:d9d9d9">byte[0] is occupied by header data, so is always used, thus</span>
            <span style="background-color:d9d9d9">first link has prev=0 ( 0 indicates not used )</span>
            <span style="background-color:d9d9d9">last link has next=0</span>
<span style="background-color:d9d9d9">*/</span>

<span style="background-color:d9d9d9">#define PREV(i)        (*((U4*)(&amp;ram[i-13])))</span>
<span style="background-color:d9d9d9">#define NEXT(i)        (*((U4*)(&amp;ram[i-9])))</span>
<span style="background-color:d9d9d9">#define STATE(i)       (*((U1*)(&amp;ram[i-5])))</span>
<span style="background-color:d9d9d9">/*FREE,OCCUPIED,TESTING*/</span>
<span style="background-color:d9d9d9">#define SIZE(i)        (*((U4*)(&amp;ram[i-4])))</span>

<span style="background-color:d9d9d9">#define FREE                0</span>
<span style="background-color:d9d9d9">#define OCCUPIED            1</span>
<span style="background-color:d9d9d9">#define TESTING             2</span>
<span style="background-color:d9d9d9">char *stateStr[3]={"FREE","OCCUPIED","TESTING"};</span>

<span style="background-color:d9d9d9">#define START        13    /*address of first payload*/</span>
<span style="background-color:d9d9d9">#define SZ_HEADER    13</span>

<span style="background-color:d9d9d9">U4 stackFrameBase;</span>

<span style="background-color:d9d9d9">#define getTOS()   _asm{ MOV stackFrameBase, EBP}</span>