⭐ 欢迎来到虫虫下载站！ | 📦 资源下载 📁 资源专辑 ℹ️ 关于我们
⭐ 虫虫下载站
📤 上传资源

📄 lib0042.html

📁 Memory Management—Algorithms and implementation in C/C++ Introduction Chapter 1 - Memory Manag
💻 HTML
📖 第 1 页 / 共 5 页
字号:
🔍
12345 
<html>
<META http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
<title>malloc() Version 4: Reference Counting</title>
<link rel="STYLESHEET" type="text/css" href="images/xpolecat.css">
<link rel="STYLESHEET" type="text/css" href="images/ie.content.books24x7.css">
</head>
<body >
<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 Section"></a>
<a href="LiB0043.html"><img src="images/next.gif" width="41" height="15" border="0" align="absmiddle" alt="Next Section"></a>
</div></td></tr>
</table>

<div class="chapter">
<a name="ch05"></a>
<div class="section">
<h2 class="first-section-title"><a name="539"></a><a name="ch05lev1sec2"></a><span class="fixed">malloc()</span> Version 4: Reference Counting</h2><a name="540"></a><a name="IDX-283"></a>
<div class="section">
<h3 class="sect3-title">
<a name="541"></a><a name="ch05lev2sec1"></a>Theory</h3>
<p class="first-para">The reference count approach keeps track of the number of pointers that hold the address of a given block of memory. The reference count of a block of memory is incremented every time that its address is assigned or copied to another pointer. The reference count of a memory block is decremented when a pointer holding its address is overwritten, goes out of scope, or is recycled. When the reference count reaches a value of zero, the corresponding memory is reclaimed.</p>
<p class="para">Consider the following short program:</p>
<div class="informalexample">
<pre class="literallayout">
<span style="background-color:d9d9d9">#include&lt;stdlib.h&gt;</span>

<span style="background-color:d9d9d9">void main()</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">char *cptr1;</span>
    <span style="background-color:d9d9d9">char *cptr2;</span>
    <span style="background-color:d9d9d9">char *cptr3;</span>

    <span style="background-color:d9d9d9">cptr1 = (char*)malloc(16);  //increment memory_block_1</span>

    <span style="background-color:d9d9d9">cptr2 = cptr1;              //increment memory_block_1</span>

    <span style="background-color:d9d9d9">cptr3 = (char*)malloc(16);  //increment memory_block_2</span>

    <span style="background-color:d9d9d9">cptr2 = cptr3;    //increment memory_block_2,</span>
                      <span style="background-color:d9d9d9">//decrement memory_block_1</span>

    <span style="background-color:d9d9d9">//decrement memory_block_2 (cptr3 out of scope)</span>
    <span style="background-color:d9d9d9">//decrement memory_block_2 (cptr2 out of scope)</span>
    <span style="background-color:d9d9d9">//decrement memory_block_1 (cptr1 out of scope)</span>

    <span style="background-color:d9d9d9">return;</span>
<span style="background-color:d9d9d9">}</span>
</pre>
</div>
<p class="para">Each reference increment and decrement has been marked with a comment to give you an idea of what would need to be done behind the scenes.</p>
<p class="para">The one line:</p>
<div class="informalexample">
<pre class="literallayout">
cptr2 = cptr3;
</pre>
</div>
<p class="para">increments the reference count to <span class="fixed">memory_block_2</span> because its address is being copied into <span class="fixed">cptr2</span>. On the other hand, the reference count to <span class="fixed">memory_block_1</span> is decremented because its address in <span class="fixed">cptr2</span> is being overwritten.</p>
<a name="542"></a><a name="IDX-284"></a>
<p class="para">Reference counting is a technique that requires the cooperation of the compiler. Specifically, the compiler will need to recognize when it is necessary to increment or decrement a reference count and emit special code to do the job. For example, normally, the native code generated for:</p>
<div class="informalexample">
<pre class="literallayout">
cptr2 = cptr1;
</pre>
</div>
<p class="para">would resemble something like:</p>
<div class="informalexample">
<pre class="literallayout">
mov    eax, DWORD PTR _cptr1$[ebp]
mov    DWORD PTR _cptr2$[ebp], eax
</pre>
</div>
<p class="para">However, because the reference count to <span class="fixed">memory_block_1</span> needs to be maintained, the compiler will need to generate something like:</p>
<div class="informalexample">
<pre class="literallayout">
mov    eax, DWORD PTR _cptr1$[ebp]
mov    DWORD PTR _cptr2$[ebp], eax
mov    ecx, DWORD PTR _cptr1$[ebp]
push   ecx
call   _increment
add    esp, 4
</pre>
</div>
<p class="para">Likewise, when a pointer goes out of scope or is overwritten, the compiler will need to emit something that looks like:</p>
<div class="informalexample">
<pre class="literallayout">
mov    ecx, DWORD PTR _cptr3$[ebp]
push   ecx
call   _decrement
add    esp, 4
</pre>
</div>
<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 alternative to emitting extra instructions to perform the reference counting is to use an interpreter, or virtual machine, which can keep pointer tallies without help from the compiler.</p>
</td>
</tr>
</table>
<a></a>
</div>
<div class="section">
<h3 class="sect3-title">
<a name="543"></a><a name="ch05lev2sec2"></a>Implementation</h3>
<p class="first-para">I decided to implement a reference counting garbage collector by modifying the sequential fit implementation in <a href="LiB0032.html#418" target="_parent" class="chapterjump">Chapter 4</a>. As with the sequential fit approach, memory is arranged as a series of blocks where each block is prefixed by a 16-byte header (see <a class="internaljump" href="#ch05fig02">Figure 5.2</a>).</p>
<div class="figure">
<a name="544"></a><a name="ch05fig02"></a><span class="figuremediaobject"><a href="images/fig312%5F01%5F0%2Ejpg" NAME="IMG_82" target="_parent"><img src="images/fig312_01.jpg" height="77" 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.2</span></span>
</div>
<a name="545"></a><a name="IDX-285"></a>
<p class="para">The <span class="fixed">STATE</span> field, which was a byte in the sequential fit implementation, has been replaced by a 32-bit field called <span class="fixed">COUNT</span>. This <span class="fixed">COUNT</span> field keeps track of the number of references to a block of memory.</p>
<p class="para">My implementation of the reference counting memory manager required four files:</p>
<a name="546"></a><a name="ch05table01"></a>
<table class="table" border="1">
<caption class="table-title">
<span class="table-title"><span class="table-titlelabel">Table 5.1</span></span>
</caption>
<thead>
<tr valign="top">
<th class="th" scope="col" align="left">
<p class="table-para">
<b class="bold">File</b>
</p>
</th><th class="th" scope="col" align="left">
<p class="table-para">
<b class="bold">Use</b>
</p>
</th>
</tr>
</thead>
<tbody>
<tr valign="top">
<td class="td" align="left">
<p class="table-para">
<span class="fixed">driver.cpp</span>
</p>
</td><td class="td" align="left">
<p class="table-para">contains <span class="fixed">main()</span>, is the scene of the crime</p>
</td>
</tr>
<tr valign="top">
<td class="td" align="left">
<p class="table-para">
<span class="fixed">mallocV4.cpp</span>
</p>
</td><td class="td" align="left">
<p class="table-para">
<span class="fixed">newMalloc(), newFree()</span> wrappers (4th version)</p>
</td>
</tr>
<tr valign="top">
<td class="td" align="left">
<p class="table-para">
<span class="fixed">perform.cpp</span>
</p>
</td><td class="td" align="left">
<p class="table-para">implements the <span class="fixed">PerformanceTest</span> class</p>
</td>
</tr>
<tr valign="top">
<td class="td" align="left">
<p class="table-para">
<span class="fixed">memmgr.cpp</span>
</p>
</td><td class="td" align="left">
<p class="table-para">implements the <span class="fixed">RefCountMemoryManager</span> class</p>
</td>
</tr>
</tbody>
</table>
<div class="section">
<h4 class="sect4-title">driver.cpp</h4>
<p class="first-para">This file contains the <span class="fixed">main()</span> entry point. You can build my implementation to execute a diagnostic test or a performance test. To build the diagnostic version, you will need to comment out the <span class="fixed">PerformanceTestDriver()</span> invocation and uncomment the <span class="fixed">debugTest()</span> invocation. You will also need to activate the <span class="fixed">DEBUG_XXX</span> macros in the <span class="fixed">mallocV4.cpp</span> file.</p>
<p class="para">Because the compiler that I used has not been engineered to emit the extra instructions needed to support reference counting, I had to manually insert the code. Throughout <span class="fixed">debugTest()</span>, I added <span class="fixed">inc()</span> and <span class="fixed">dec()</span> function calls. I also added comments indicating that these calls should have been generated by the compiler.</p>
<div class="informalexample">
<pre class="literallayout">
<span style="background-color:d9d9d9">#include&lt;mallocV4.cpp&gt;</span>
<span style="background-color:d9d9d9">#include&lt;perform.cpp&gt;</span>

<span style="background-color:d9d9d9">/*</span>
<span style="background-color:d9d9d9">not using a modified compiler, so will need to insert</span>
<span style="background-color:d9d9d9">reference counting code manually</span>
<span style="background-color:d9d9d9">*/</span>

<span style="background-color:d9d9d9">void debugTest()</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">void *ptr[6];</span>
    <span style="background-color:d9d9d9">void *ptr1;</span>
    <span style="background-color:d9d9d9">void *ptr2;</span>
    <span style="background-color:d9d9d9">void *ptr3;</span>

    <span style="background-color:d9d9d9">unsigned long allocs[6]={8,12,33,1,122,50};</span>
    <span style="background-color:d9d9d9">int i;</span>

    <span style="background-color:d9d9d9">initMemMgr(270);</span><a name="547"></a><a name="IDX-286"></a>
    <span style="background-color:d9d9d9">for(i=0;i&lt;6;i++)</span>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">ptr[i] = newMalloc(allocs[i]);</span>
        <span style="background-color:d9d9d9">if(ptr[i]==NULL){ printf("ptr[%lu]==NULL!\n",i); }</span>
    <span style="background-color:d9d9d9">}</span>

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

    <span style="background-color:d9d9d9">printf("copying ptr[0]\n");</span>
    <span style="background-color:d9d9d9">ptr1 = ptr[0];</span>
    <span style="background-color:d9d9d9">(*mmptr).inc(ptr[0]);     //compiler insert</span>

    <span style="background-color:d9d9d9">printf("copying ptr[1]\n");</span>
    <span style="background-color:d9d9d9">ptr3 = ptr[1];</span>
    <span style="background-color:d9d9d9">(*mmptr).inc(ptr[1]);     //compiler insert</span>

    <span style="background-color:d9d9d9">printf("copying ptr1\n");</span>
12345

⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -