lib0028.html

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

</tr>
<tr valign="top">
<td class="td" align="left">
<p class="table-para">restaurant customer</p>
</td><td class="td" align="left">
<p class="table-para">
<span class="unicode">&harr;</span>
</p>
</td><td class="td" align="left">
<p class="table-para">waiter</p>
</td><td class="td" align="left">
<p class="table-para">
<span class="unicode">&harr;</span>
</p>
</td><td class="td" align="left">
<p class="table-para">cook</p>
</td>
</tr>
</tbody>
</table>
</div>
<a name="342"></a><a name="IDX-155"></a>
<p class="para">The C programming language's standard library is a classic example of this tactic. Let's look at a somewhat forced implementation of the <span class="fixed">putchar ()</span> function to see how library functions build upon system functions. To begin with, most standard library implementations define <span class="fixed">putchar ()</span> in terms of its more general sibling, <span class="fixed">putc ()</span>, which writes a character to a given output stream. In the case of <span class="fixed">putchar ()</span>, the output stream is fixed as standard output (<span class="fixed">stdout</span>).</p>
<div class="informalexample">
<pre class="literallayout">
#define putchar(c) putc(c,stdout)
</pre>
</div>
<p class="para">Thus, to understand <span class="fixed">putchar ()</span>, we must dissect <span class="fixed">putc ()</span>:</p>
<div class="informalexample">
<pre class="literallayout">
int putc(int ch, FILE *stream)
{
    int ret;
    ret = write(stream,&amp;ch,1);
    if(ret!=1){ return(EOF); }else{ return(c); }
}
</pre>
</div>
<p class="para">The <span class="fixed">putc()</span> function, in turn, wraps a system call called <span class="fixed">write ()</span>. A recurring theme that you will notice is the tendency of functions with specific duties to invoke more general and primitive routines.</p>
<div class="informalexample">
<pre class="literallayout">
/*
stream = output stream to write to
buffer = buffer of bytes to write to stream
nbytes = number of bytes to write
returns: number of bytes written to stream
*/

int write(FILE *stream, void *buffer, int nbytes)
{
    struct call_struct;
    call_struct.type = FILE_SYSTEM;
    call_struct.subtype = BUFF_OUTPUT;
    call_struct.param1 = (long)stream;
    call_struct.param2 = (long)buffer;
    call_struct.param3 = nbytes;

    asm
    {
        MOV ECX,USER_LIBRARY
        LEA EAX,call_struct
        INT SYSTEM_GATE
    }
}
</pre>
</div>
<p class="para">Notice how the <span class="fixed">write ()</span> function is actually a front man for a more general system call gate called <span class="fixed">SYSTEM_GATE</span>.</p>
<a name="343"></a><a name="IDX-156"></a>
<a></a>
</div>
<div class="section">
<h3 class="sect3-title">
<a name="344"></a><a name="ch03lev2sec5"></a>The Heap</h3>
<p class="first-para">The heap is just a region of bytes. It is a portion of an application's address space that has been set aside for run-time memory requests. As mentioned previously, the general nature of possible memory requests forces the code that manages the heap to have to deal with a number of possible contingencies. The heap manager cannot handle every type of request equally well, and concessions have to be made. As a result of this, heap management is beset by three potential pitfalls:</p>
<ul class="itemizedlist">
<li class="first-listitem">
<p class="first-para">Internal fragmentation</p>
</li>
<li class="listitem">
<p class="first-para">External fragmentation</p>
</li>
<li class="listitem">
<p class="first-para">Location-based latency</p>
</li>
</ul>
<p class="para">
<i class="emphasis">Internal fragmentation</i> occurs when memory is wasted because a request for memory resulted in the allocation of a block of memory that was much too big, relative to the request size. For example, let's say you request 128 bytes of storage and the run-time system gives you a block of 512 bytes. Most of the memory you've been allocated will never be used. Management schemes that allocate fixed-sized memory blocks can run into this problem.</p>
<p class="para">
<i class="emphasis">External fragmentation</i> occurs when a series of memory requests leaves several free blocks of available memory, none of which are large enough to service a typical request.</p>
<p class="para">Latency problems can occur if two data values are stored far apart from one another in memory. The farther apart two values are in memory, the longer it takes for the processor to perform operations that involve those values. In an extreme case, one value may be so far away that it gets paged-out to disk and requires a disk I/O operation to bring it back into the ball game.</p>
<p class="para">Latency problems can also occur because of complexity. If an algorithm takes extensive measures to ensure that internal and external fragmentation are both minimized, the improvement in memory utilization will be offset by the additional execution time necessary to perform the requisite accounting.</p>
<p class="para">Depending on the allocation technique used by the heap management code, it will suffer from one or more of these problems. Rarely can you have your cake and eat it too.</p>
<p class="para">
<a class="internaljump" href="#ch03fig13">Figure 3.13</a> displays these three pitfalls.</p>
<div class="figure">
<a name="345"></a><a name="ch03fig13"></a><span class="figuremediaobject"><a href="images/fig185%5F01%5F0%2Ejpg" NAME="IMG_62" target="_parent"><img src="images/fig185_01.jpg" height="191" width="229" alt="Click To expand" border="0"></a></span>
<br style="line-height: 1">
<span class="figure-title"><span class="figure-titlelabel">Figure 3.13</span></span>
</div>
<p class="para">In the end, what makes the heap an interesting problem is not the heap itself, but the algorithms used to manage it. There are two different approaches to managing heap memory: manual memory management and automatic memory management.</p>
<a name="346"></a><a name="IDX-157"></a>
<p class="para">In the next two sections, I will examine both of these techniques and offer examples of how they are used in practice.</p>
<div class="section">
<h4 class="sect4-title">Manual Memory Management</h4>
<p class="first-para">
<i class="emphasis">Manual memory management,</i> also known as <i class="emphasis">explicit memory management,</i> requires the programmer to explicitly allocate and recycle heap storage. This is performed through function calls like <span class="fixed">malloc()</span> and <span class="fixed">free()</span>. Explicit memory management shifts responsibility onto the shoulders of the developer with regard to keeping track of allocated memory.</p>
<p class="para">The result of this is that the algorithms implemented by the run-time systems are simpler and involve less bookkeeping. This is both a blessing and a curse. Explicit memory management allows programs to be smaller because the compiler does not have to emit any extra instructions or data to handle garbage collection. In addition, explicit memory management also gives the programmer a better idea of what is actually going on behind the curtain.</p>
<p class="para">The curse of this extra complexity is that it can lead to mistakes (this is an understatement).</p>
<p class="para">If a dynamically allocated variable leaves its scope before being recycled, the memory cannot be recycled and the program will gradually drain away memory until the computer halts. This is known as a <i class="emphasis">memory leak,</i> and is an insidious problem to try to correct (the author is a voice of experience in this matter). In <a href="LiB0019.html#131" target="_parent" class="chapterjump">Chapter 2</a> we encountered a program that created a memory leak during the discussion of siege warfare.</p>
<a name="347"></a><a name="IDX-158"></a>
<p class="para">If a dynamically allocated variable is recycled before it goes out of scope, the variable will become an invalid reference and can potentially crash the program (or produce incorrect results, which is even worse). The invalid reference in this kind of situation is known as a <i class="emphasis">dangling pointer.</i>
</p>
<p class="last-para">Memory leaks and dangling pointers are the bugaboos of every C programmer's working hours. Trying to find these problems by inspection alone can entail many frustrating debugging sessions. Fortunately, there are specialized tools that can be used to track down memory leaks. These tools tend to be platform specific, so it is hard to recommend a universal solution. The Boehm-Demers-Weiser (BDW) conservative garbage collector, described later, can be used as a memory leak detector on several platforms.</p>
<a></a>
</div>
<div class="section">
<h4 class="sect4-title">Example: C Standard Library Calls</h4>
<p class="first-para">The ANSI C standard library, whose prototypes are spelled out in <span class="fixed">stdlib.h</span>, supports manual memory management through a series of four functions:</p>
<div class="informalexample">
<pre class="literallayout">
    void *calloc(size_t num, size_t size);
    void free(void *);
    void malloc(size_t);
    void *realloc(void *block, size_t size);
</pre>
</div>
<p class="para">The <span class="fixed">calloc()</span> function allocates an array of <span class="fixed">num</span> elements, each element being <span class="fixed">size</span> bytes long, and initializes everything to zero. The <span class="fixed">free ()</span> function releases an allocated block of memory. The <span class="fixed">malloc()</span> function allocates <span class="fixed">size</span> number of bytes from the heap. The <span class="fixed">realloc()</span> function changes the <span class="fixed">size</span> of an allocated block of memory. As you can see, there are very few amenities. Calls to <span class="fixed">calloc()</span> and <span class="fixed">realloc()</span> typically end up indirectly calling <span class="fixed">malloc()</span>. So most of the behind-the-scenes work is actually done by <span class="fixed">malloc()</span> and <span class="fixed">free()</span>.</p>
<div class="informalexample">
<pre class="literallayout">
void *calloc(size_t num, size_t size)
{
   void ptr;
   size_t nbytes;
   nbytes = num*size;
   ptr = malloc(nbytes);
   if(ptr!=NULL){ memset(ptr, 0x0,nbytes); }
   return ptr;
}

void *realloc(void *ptr, size_t size)
{
      unsigned char *cptr;<a name="348"></a><a name="IDX-159"></a>
      int oldsize;
      if (ptr == NULL){ return malloc(size); }
      oldsize = sizeMem(ptr);
      if (size &lt;= oldsize){ return ptr; }
      cptr = (char *)malloc(size);
      memcpy(cptr, ptr, oldsize);
      free(ptr);
      return cptr;
}
</pre>
</div>
<p class="para">The implementation of <span class="fixed">malloc ()</span> and <span class="fixed">free ()</span> varies greatly from one distribution to the next, so it is a little harder for me to offer reference implementations. The <span class="fixed">malloc ()</span> and <span class="fixed">free ()</span> functions on UNIX platforms are front men for the <span class="fixed">brk ()</span> system call. Its prototype usually resembles something like this:</p>
<div class="informalexample">
<pre class="literallayout">
       int brk(void *end_heap);
</pre>
</div>
<p class="para">The <span class="fixed">brk ()</span> system call is responsible for modifying the size of a program's heap by either increasing or decreasing its end point. The <span class="fixed">end_heap</span> value can be changed as long as it does not infringe on other sections of the application.</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 POSIX standard does not include <span class="fixed">brk ()</span> on the grounds that it dictates a certain underlying memory model implementation. On most flavors of UNIX, however, you will find the <span class="fixed">brk ()</span> system call. If you are interested in looking at an implementation of <span class="fixed">brk ()</span>, I would recommend taking a look at the one that accompanies Linux. It is located in the <span class="fixed">/usr/src/linux/mm/mmap.c</span> file.</p>
</td>
</tr>
</table>
<p class="para">Now that you are familiar with C's manual memory allocation functions, I can demonstrate how dangling pointers occur and what happens when they do. Consider the following example:</p>
<div class="informalexample">
<pre class="literallayout">
<span style="background-color:d9d9d9">/* --dangleptr.c-- */</span>

<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">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">cptr1 = malloc(10);</span>
    <span style="background-color:d9d9d9">printf("address=%p\n",cptr1);</span>

    <span style="background-color:d9d9d9">cptr1[0]='a'; cptr1[1]='b'; cptr1[2]=0;</span>
    <span style="background-color:d9d9d9">printf("cptr1=%s\n",cptr1);</span>