lib0042.html

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

    <span style="background-color:d9d9d9">ptr2 = ptr1;</span>
    <span style="background-color:d9d9d9">(*mmptr).inc(ptr1);       //compiler insert</span>

    <span style="background-color:d9d9d9">//overwritting</span>

    <span style="background-color:d9d9d9">printf("overwriting ptr1 with ptr3\n");</span>
    <span style="background-color:d9d9d9">(*mmptr).dec(ptr2);       //compiler insert</span>
    <span style="background-color:d9d9d9">ptr2 = ptr3;</span>
    <span style="background-color:d9d9d9">(*mmptr).inc(ptr3);       //compiler insert</span>

    <span style="background-color:d9d9d9">//locals going out of scope, need to decrement</span>

    <span style="background-color:d9d9d9">printf("leaving scope\n");</span>
    <span style="background-color:d9d9d9">for(i=0; i&lt;6;i++)</span>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">(*mmptr).dec(ptr[i]);  //compiler insert</span>
    <span style="background-color:d9d9d9">}</span>
    <span style="background-color:d9d9d9">(*mmptr).dec(ptr1);        //compiler insert</span>
    <span style="background-color:d9d9d9">(*mmptr).dec(ptr2);        //compiler insert</span>
    <span style="background-color:d9d9d9">(*mmptr).dec(ptr3);        //compiler insert</span>

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

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

<span style="background-color:d9d9d9">void main()</span>
<span style="background-color:d9d9d9">{</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><a name="548"></a><a name="IDX-287"></a>
    <span style="background-color:d9d9d9">PerformanceTestDriver();</span>
    <span style="background-color:d9d9d9">return;</span>

<span style="background-color:d9d9d9">}/*end main-&mdash;--&mdash;---&mdash;--&mdash;--&mdash;--&mdash;--&mdash;--&mdash;--&mdash;--&mdash;--&mdash;--&mdash;----------*/</span>
</pre>
</div>
<a></a>
</div>
<div class="section">
<h4 class="sect4-title">mallocV4.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>
<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_RC_MEM_MGR</span>
<span style="background-color:d9d9d9">//#define DEBUG_MALLOCV4</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">RefCountMemoryManager *mmptr;</span>

<span style="background-color:d9d9d9">void initMemMgr(unsigned long totalbytes)</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">mmptr = new RefCountMemoryManager(totalbytes);</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_MALLOCV4</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><a name="549"></a><a name="IDX-288"></a>

<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>
</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, and add in the <span class="fixed">dec()</span> invocations that the compiler should normally emit.</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">char **addr;    /*pointer to an array of pointers*/</span>

    <span style="background-color:d9d9d9">/*create array of address holders to stockpile malloc()</span>
     <span style="background-color:d9d9d9">returns*/</span>

    <span style="background-color:d9d9d9">addr = (char **)malloc(sizeof(char *)*nAllocations);</span>
    <span style="background-color:d9d9d9">if(addr==NULL)</span>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">printf("could not allocate address repository\n");</span>
        <span style="background-color:d9d9d9">exit (1);</span>
    <span style="background-color:d9d9d9">}</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);</span><a name="550"></a><a name="IDX-289"></a>

    <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">//printf("%lu\n",allocs[i]);</span>
        <span style="background-color:d9d9d9">addr[i] = (char *)newMalloc(allocs[i]);</span>
        <span style="background-color:d9d9d9">if(addr[i]==NULL)</span>
        <span style="background-color:d9d9d9">{</span>
            <span style="background-color:d9d9d9">printf("mallco()=addr[%lu]=%lu failed\n",i,addr[i]);</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">//array goes out of scope</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">(*mmptr).dec(addr[i]);</span>
    <span style="background-color:d9d9d9">}</span>

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

    <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(addr);</span>
    <span style="background-color:d9d9d9">free(allocs);</span>

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

<span style="background-color:d9d9d9">}/*end runTest--&mdash;---&mdash;--&mdash;--&mdash;--&mdash;--&mdash;--&mdash;--&mdash;--&mdash;--&mdash;--&mdash;--------------*/</span>
</pre>
</div>
<a></a>
</div>
<div class="section">
<h4 class="sect4-title">memmgr.cpp</h4>
<p class="first-para">The <span class="fixed">RefCountMemoryManager</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="#ch05fig03">Figure 5.3</a> (on the following page).</p>
<div class="figure">
<a name="551"></a><a name="ch05fig03"></a><span class="figuremediaobject"><a href="images/fig318%5F01%5F0%2Ejpg" NAME="IMG_83" target="_parent"><img src="images/fig318_01.jpg" height="186" width="257" alt="Click To expand" border="0"></a></span>
<br style="line-height: 1">
<span class="figure-title"><span class="figure-titlelabel">Figure 5.3</span></span>
</div>
<p class="para">Most of the action happens as a result of the <span class="fixed">allocate()</span> or <span class="fixed">dec()</span> functions being called. Both the <span class="fixed">inc()</span> and <span class="fixed">dec()</span> functions perform a series of sanity checks before they modify the heap block list. The <span class="fixed">inc()</span> function increments the reference count of a memory block, and the <span class="fixed">dec()</span> function decrements the reference count of a memory block. As you can see from <a class="internaljump" href="#ch05fig03">Figure 5.3</a>, the <span class="fixed">release ()</span> function has been made subservient to the <span class="fixed">dec()</span> function.</p>
<a name="552"></a><a name="IDX-290"></a>
<div class="informalexample">
<pre class="literallayout">
<span style="background-color:d9d9d9">#ifdef DEBUG_RC_MEM_MGR</span>
<span style="background-color:d9d9d9">#define MSGO(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>
<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  11||12  15||16 .. n|</span>
                <span style="background-color:d9d9d9">[PREV][NEXT][COUNT][ SIZE ][payload]</span>
                  <span style="background-color:d9d9d9">U4    U4    U4    U4       ?</span>

    <span style="background-color:d9d9d9">byte allocated/freed is address of first byte of payload</span>
    <span style="background-color:d9d9d9">header = 16 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-16])))</span>
<span style="background-color:d9d9d9">#define NEXT(i)        (*((U4*)(&amp;ram[i-12])))</span>
<span style="background-color:d9d9d9">#define COUNT(i)       (*((U1*)(&amp;ram[i-8])))  /*# references*/</span>
<span style="background-color:d9d9d9">#define SIZE(i)        (*((U4*)(&amp;ram[i-4])))</span>
<span style="background-color:d9d9d9">#define FREE       0    /*free blocks have COUNT=0*/</span><a name="553"></a><a name="IDX-291"></a>
<span style="background-color:d9d9d9">#define START        16    /*address of first payload*/</span>
<span style="background-color:d9d9d9">#define SZ_HEADER    16</span>