lib0042.html

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

<span style="background-color:d9d9d9">}/*end printState---------------------------------------------*/</span>
</pre>
</div>
<a></a>
</div>
<a></a>
</div>
<div class="section">
<h3 class="sect3-title">
<a name="562"></a><a name="ch05lev2sec3"></a>Tests</h3>
<p class="first-para">I performed two different tests against this memory manager. A debug test was performed to make sure that the manager was doing what it was supposed to do. If you modify my source code, I would suggest running the debug test again to validate your changes. Once I was sure that the memory manager was operational, I turned off debugging features and ran a performance test.</p>
<p class="para">The debug test was performed by executing the code in the <span class="fixed">debugTest()</span> function defined in the <span class="fixed">driver.cpp</span> source file. I keep things fairly simple, but at the same time, I take a good, hard look at what is going on. If you decide to run a debug test, you will want to make sure that the <span class="fixed">DEBUG_xxx</span> macros in <span class="fixed">mallocV4.cpp</span> are turned on. You will also want to comment out the <span class="fixed">PerformanceTestDriver()</span> function call in <span class="fixed">main()</span>.</p>
<p class="para">The following output was generated by the debug build of the memory manager:</p>
<div class="informalexample">
<pre class="literallayout">
RefCountMemoryManager::RefCountMemoryManager(270)
RefCountMemoryManager::allocate(8)
RefCountMemoryManager::split(): split=YES<a name="563"></a><a name="IDX-300"></a>
0) [P=0][addr=16][Ct=1][Sz=8][N=40]
1) [P=16][addr=40][FREE][Sz=230][N=0]
RefCountMemoryManager::allocate(12)
RefCountMemoryManager::split(): split=YES
0) [P=0][addr=16][Ct=l][Sz=8][N=40]
1) [P=16][addr=40][Ct=l][Sz=12][N=68]
2) [P=40][addr=68][FREE][Sz=202][N=0]
RefCountMemoryManager::allocate(33)
RefCountMemoryManager::split(): split=YES
0) [P=0][addr=16][Ct=1][Sz=8][N=40]
1) [P=16][addr=40][Ct=1][Sz=12][N=68]
2) [P=40][addr=68][Ct=1][Sz=33][N=117]
3) [P=68][addr=117][FREE][Sz=153][N=0]
RefCountMemoryManager::allocate(1)
RefCountMemoryManager::split(): split=YES
0) [P=0][addr=16][Ct=1][Sz=8][N=40]
1) [P=16][addr=40][Ct=1][Sz=12][N=68]
2) [P=40][addr=68][Ct=1][Sz=33][N=117]
3) [P=68][addr=117][Ct=1][Sz=1][N=134]
4) [P=117][addr=134][FREE][Sz=136][N=0]
RefCountMemoryManager::allocate(122)
RefCountMemoryManager::split(): split=NO
0) [P=0][addr=16][Ct=1][Sz=8][N=40]
1) [P=16][addr=40][Ct=1][Sz=12][N=68]
2) [P=40][addr=68][Ct=1][Sz=33][N=117]
3) [P=68][addr=117][Ct=1][Sz=1][N=134]
4) [P=117][addr=134][Ct=1][Sz=136][N=0]
RefCountMemoryManager::allocate(50)
0) [P=0][addr=16][Ct=1][Sz=8][N=40]
1) [P=16][addr=40][Ct=1][Sz=12][N=68]
2) [P=40][addr=68][Ct=1][Sz=33][N=117]
3) [P=68][addr=117][Ct=1][Sz=1][N=134]
4) [P=117][addr=134][Ct=1][Sz=136][N=0]
ptr[5]==NULL!
copying ptr[0]
RefCountMemoryManager::checkAddress(5439516)
RefCountMemoryManager::inc(): address resolves to index 16
RefCountMemoryManager::inc(): incrementing ram[16] to 2
copying ptr[1]
RefCountMemoryManager::checkAddress(5439540)
RefCountMemoryManager::inc(): address resolves to index 40
RefCountMemoryManager::inc(): incrementing ram[40] to 2
copying ptr1
RefCountMemoryManager::checkAddress(5439516)
RefCountMemoryManager::inc(): address resolves to index 16
RefCountMemoryManager::inc(): incrementing ram[16] to 3
overwriting ptr1 with ptr3
RefCountMemoryManager::checkAddress(5439516)
RefCountMemoryManager::dec(): address resolves to index 16
RefCountMemoryManager::dec(): decrementing ram[16] to 2
RefCountMemoryManager::checkAddress(5439540)<a name="564"></a><a name="IDX-301"></a>
RefCountMemoryManager::inc(): address resolves to index 40
RefCountMemoryManager::inc(): incrementing ram[40] to 3
leaving scope
RefCountMemoryManager::checkAddress(5439516)
RefCountMemoryManager::dec(): address resolves to index 16
RefCountMemoryManager::dec(): decrementing ram[16] to 1
RefCountMemoryManager::checkAddress(5439540)
RefCountMemoryManager::dec(): address resolves to index 40
RefCountMemoryManager::dec(): decrementing ram[40] to 2
RefCountMemoryManager::checkAddress(5439568)
RefCountMemoryManager::dec(): address resolves to index 68
RefCountMemoryManager::dec(): decrementing ram[68] to 0
RefCountMemoryManager::dec(): releasing ram[68]
0) [P=0][addr=16][Ct=1][Sz=8][N=40]
1) [P=16][addr=40][Ct=2][Sz=12][N=68]
2) [P=40][addr=68][FREE][Sz=33][N=117]
3) [P=68][addr=117][Ct=1][Sz=1][N=134]
4) [P=117][addr=134][Ct=1][Sz=136][N=0]
RefCountMemoryManager::checkAddress(5439617)
RefCountMemoryManager::dec(): address resolves to index 117
RefCountMemoryManager::dec(): decrementing ram[117] to 0
RefCountMemoryManager::dec(): releasing ram[117]
RefCountMemoryManager::merge():merging to PREV
0) [P=0][addr=16][Ct=1][Sz=8][N=40]
1) [P=16][addr=40][Ct=2][Sz=12][N=68]
2) [P=40][addr=68][FREE][Sz=50][N=134]
3) [P=68][addr=134][Ct=1][Sz=136][N=0]
RefCountMemoryManager::checkAddress(5439634)
RefCountMemoryManager::dec(): address resolves to index 134
RefCountMemoryManager::dec(): decrementing ram[134] to 0
RefCountMemoryManager::dec(): releasing ram[134]
RefCountMemoryManager::merge():merging to PREV
0) [P=0][addr=16][Ct=1][Sz=8][N=40]
1) [P=16][addr=40][Ct=2][Sz=12][N=68]
2) [P=40][addr=68][FREE][Sz=202][N=0]
RefCountMemoryManager::checkAddress(): cannot release NULL
pointer
RefCountMemoryManager::checkAddress(5439516)
RefCountMemoryManager::dec(): address resolves to index 16
RefCountMemoryManager::dec(): decrementing ram[16] to 0
RefCountMemoryManager::dec(): releasing ram[16]
0) [P=0][addr=16][FREE][Sz=8][N=40]
1) [P=16][addr=40][Ct=2][Sz=12][N=68]
2) [P=40][addr=68][FREE][Sz=202][N=0]
RefCountMemoryManager::checkAddress(5439540)
RefCountMemoryManager::dec(): address resolves to index 40
RefCountMemoryManager::dec(): decrementing ram[40] to 1
RefCountMemoryManager::checkAddress(5439540)
RefCountMemoryManager::dec(): address resolves to index 40
RefCountMemoryManager::dec(): decrementing ram[40] to 0
RefCountMemoryManager::dec(): releasing ram[40]<a name="565"></a><a name="IDX-302"></a>
RefCountMemoryManager::merge():merging with both sides
0) [P=0][addr=16][FREE][Sz=254][N=0]
RefCountMemoryManager::~RefCountMemoryManager()free ram[270]
</pre>
</div>
<p class="para">The performance test was conducted by commenting out <span class="fixed">debugTest()</span> and the debug macros in mallocV4.cpp, and then enabling the <span class="fixed">PerformanceTestDriver()</span> function. The results of the performance run were, well, surprising:</p>
<div class="informalexample">
<pre class="literallayout">
PerformanceTest::runTest(): time whistle blown
PerformanceTest::runTest(): race has ended
msecs=30
</pre>
</div>
<p class="last-para">Not bad.</p>
<a></a>
</div>
<div class="section">
<h3 class="sect3-title">
<a name="566"></a><a name="ch05lev2sec4"></a>Trade-Offs</h3>
<p class="first-para">The reference counting approach to garbage collection is convenient because it offers a type of collection that is <i class="emphasis">incremental,</i> which is to say that the bookkeeping needed to reclaim garbage is done in short, bite-sized bursts. This allows the memory manager to do its jobs without introducing a significant time delay into the program's critical path. Some garbage collectors wait to do everything at once so that users may experience a noticeable pause while a program runs.</p>
<p class="para">While the reference counting approach is fast, it also suffers from some serious problems. For example, reference counting garbage collectors cannot reclaim objects that reference each other. This is known as a <i class="emphasis">cycle</i> (see <a class="internaljump" href="#ch05fig04">Figure 5.4</a>).</p>
<div class="figure">
<a name="567"></a><a name="ch05fig04"></a><span class="figuremediaobject"><a href="images/fig330%5F01%5F0%2Ejpg" NAME="IMG_84" target="_parent"><img src="images/fig330_01.jpg" height="139" 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.4</span></span>
</div>
<p class="para">Let us assume that we have two heap-allocated variables, A and B, which reference one another. For example:</p>
<div class="informalexample">
<pre class="literallayout">
<span style="background-color:d9d9d9">#include&lt;stdlib.h&gt;</span>
<span style="background-color:d9d9d9">#include&lt;stdio.h&gt;</span><a name="568"></a><a name="IDX-303"></a>

<span style="background-color:d9d9d9">void function()</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">void **A;    //points to value storing an address</span>
    <span style="background-color:d9d9d9">void **B;</span>

    <span style="background-color:d9d9d9">//create 2 blocks in heap that can store addresses</span>

    <span style="background-color:d9d9d9">A = (void*)malloc(sizeof(void*));</span>
    <span style="background-color:d9d9d9">B = (void*)malloc(sizeof(void*));</span>

    <span style="background-color:d9d9d9">// A's reference count = 1</span>
    <span style="background-color:d9d9d9">// B's reference count = 1</span>

    <span style="background-color:d9d9d9">(*A) = B;    //set A's heap value to the address of B</span>
    <span style="background-color:d9d9d9">(*B) = A;    //set B's heap value to the address of A</span>

    <span style="background-color:d9d9d9">// A's reference count = 2</span>
    <span style="background-color:d9d9d9">// B's reference count = 2</span>

    <span style="background-color:d9d9d9">printf("address A=%p\t",A);</span>
    <span style="background-color:d9d9d9">printf("value in A=%p\n\n",*A);</span>

    <span style="background-color:d9d9d9">printf("address B=%p\t",B);</span>
    <span style="background-color:d9d9d9">printf("value in B=%p\n",*B);</span>

    <span style="background-color:d9d9d9">//decrement A's reference count to 1 ( A goes out of scope )</span>
    <span style="background-color:d9d9d9">//decrement B's reference count to 1 ( B goes out of scope )</span>

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

<span style="background-color:d9d9d9">void main()</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">function();</span>
    <span style="background-color:d9d9d9">return;</span>
<span style="background-color:d9d9d9">}</span>
</pre>
</div>
<p class="para">If the variable A goes out of scope, its heap storage will still not be reclaimed. This is because B still references it so that its reference count is 1. The same holds true for B. Because of the pointer tomfoolery performed, and because of the nature of reference counting, neither of these blocks of memory will ever have their storage reclaimed because their reference counts will never be able to reach zero.</p>
<table border="0" cellspacing="0" cellpadding="0" class="note">
<tr>
<td valign="top" class="admon-check"></td><td valign="top" class="admon-title">Note&nbsp;</td><td valign="top" class="admon-body">
<p class="first-para">The ugly truth is that the inability to handle cyclic references is what allows reference counting schemes to develop memory leaks. This is one reason why most run-time systems, like the Java virtual machine, avoid reference counting garbage collection.</p>
</td>
</tr>
</table>
<a name="569"></a><a name="IDX-304"></a>
<p class="para">Another problem with reference counting schemes is that functions with a lot of local variables can cause the memory manager to perform an excessive amount of reference count incrementing and decrementing.</p>
<p class="para">One solution is to use <i class="emphasis">deferred reference counting,</i> where the memory manager does not include local variables when it maintains reference counts. The problem with this is that you cannot be sure if a memory block can be reclaimed when its reference count is zero. This is because there might still be one or more local variables referencing the memory block. If you reclaim too early, you will end up with a bunch of dangling pointers! This is why most memory managers that implement deferred reference counting will use it in conjunction with a tracing algorithm that can survey the stack for local variable pointers.</p>
<p class="last-para">Another reference counting technique is to use a <span class="fixed">COUNT</span> field that is a single bit in size. This is known as <i class="emphasis">1-bit reference counting.</i> The gist of this technique is that the number of references to a block of memory is always zero, one, or many. So the 1-bit <span class="fixed">COUNT</span> field will be zero or one. When it is one, there may be one or more references. In many cases, there is only a single reference and garbage collection is very quick. However, there also may be many references, which is why the 1-bit reference counting technique is usually used with another tracing garbage collector.</p>
<a></a>
</div>
<a></a>
</div>
</div>
</div>
</div>
<table width="100%" border="0" cellspacing="0" cellpadding="0">
<td><div STYLE="MARGIN-LEFT: 0.15in;">
<a href="toc.html"><img src="images/teamlib.gif" width="62" height="15" border="0" align="absmiddle"  alt="Team LiB"></a></div></td>
<td valign="top" class="v2" align="right"><div STYLE="MARGIN-RIGHT: 0.15in"><a href="LiB0041.html"><img src="images/previous.gif" width="62" height="15" border="0" align="absmiddle" alt="Previous S