lib0029.html

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

<span style="background-color:d9d9d9">begin</span>
    <span style="background-color:d9d9d9">index:=10;</span>
    <span style="background-color:d9d9d9">iptr:=new(intPointer);</span>
    <span style="background-color:d9d9d9">iptr^:=0;</span>
    <span style="background-color:d9d9d9">for index:= 1 to size do</span>
    <span style="background-color:d9d9d9">begin</span>
        <span style="background-color:d9d9d9">iptr^:= iptr^ + factorial(index);</span>
        <span style="background-color:d9d9d9">writeln('factorial(',index,')= ',factorial</span>
               <span style="background-color:d9d9d9">(index))</span>
    <span style="background-color:d9d9d9">end;</span>
    <span style="background-color:d9d9d9">writeln('iptr^=',iptr^);</span>
    <span style="background-color:d9d9d9">dispose(iptr)</span>
<span style="background-color:d9d9d9">end.</span>
</pre>
</div>
<p class="para">If you run this program, the following output will be sent to the console:</p>
<div class="informalexample">
<pre class="literallayout">
factorial(1)= 1
factorial(2)= 2
factorial(3)= 6
factorial(4)= 24
factorial(5)= 120
factorial(6)= 720
iptr^=873
</pre>
</div>
<p class="para">The <span class="fixed">factorial()</span> function is recursive, which proves that Pascal implements activation records on the stack. I also manually allocate an integer off the heap and store its address in the variable <span class="fixed">iptr^</span> to show how Pascal's manual memory management scheme works.</p>
<p class="last-para">Pascal's variety of memory management facilities and its easy-to-read structured format place it above COBOL 85 and F77 on the scale of sophistication. However, Pascal is not a language that you would use to construct production software. The organization of heavily nested routines in Pascal source code does not lend itself to constructing large-scale applications. This is why I decided to present Pascal before my discussion of C and Java. Pascal may possess memory management bells and whistles, but it is not a prime-time language.</p>
<table class="BlueLine" border="0" cellspacing="0" cellpadding="0" width="100%">
<tr>
<td bgcolor="000080" class="bluecell"><font size="2" face="Arial" color="010100"><b><img src="_.gif" width="1" height="2" alt="End example" border="0"></b></font></td>
</tr>
</table>
<table class="BlankSpace" border="0" cellspacing="0" cellpadding="0" width="100%">
<tr>
<td height="16"></td>
</tr>
</table>
</div>
</div>
<a name="382"></a><a name="IDX-184"></a>
<div class="example">
<span class="example-title"><span class="example-titlelabel">Case Study: </span>C</span><a name="383"></a><a></a>
<div class="formalbody">
<table class="BlueLine" border="0" cellspacing="0" cellpadding="0" width="100%">
<tr>
<td bgcolor="000080" class="bluecell"><font size="2" face="Arial" color="010100"><b><img src="_.gif" width="1" height="2" alt="Start example" border="0"></b></font></td>
</tr>
</table>
<p class="first-para">The C programming language is the Swiss army knife of programming languages. It is compact, versatile, and you can do darn near everything with it. Perhaps this is why every operating system being sold today has been written mostly in C. Part of C's utility is based on the language's provision for low-level operations like bit-wise manipulation and inline assembly code. C also possesses a syntax that allows memory addresses to be symbolically manipulated in a number of intricate ways. Furthermore, the fairly simple function-based granularity of scope is a straightforward alternative to Pascal's tendency toward heavy procedure nesting.</p>
<p class="para">
<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">In a sense, C can be viewed as a nifty macro language for assembly code. C elevates you far enough from assembly code that you don't have to worry about maintaining stack frames or keeping track of offset addresses. You are given enough programming amenities that you don't feel like you are being forced to sleep on the floor. However, C doesn't really take you any higher than a few floors above the basement. You can still hop down and tinker with the rusty old furnace, if you so desire.</p>
</td>
</tr>
</table>
</p>
<p class="para">
<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">If you are interested in the history of C, I offer a brief synopsis in the "<a href="LiB0008.html#39" target="_parent" class="chapterjump">Prerequisites</a>" section of this book's introduction. For those of you who want the short version, a guy at Bell Labs named Ken Thompson wrote an operating system named Unics in assembly code back in the late 1960s. He discovered that porting assembly code is no fun, so he hacked a language called BCPL into a new language that he called B. Soon afterward, two of Ken's friends at Bell Labs (Dennis Ritchie and Brian Kernighan) got mixed up in Ken's project, and C was born. They rewrote Unics in C, Bell Labs trademarked the resulting product as UNIX, and the rest is history.</p>
</td>
</tr>
</table>
</p>
<p class="para">The C language can use all of the high-level memory constructs mentioned in this chapter. C supports global data, local variables, recursion, and dynamic memory allocation. In other words, C can make ample use of data sections, the stack, and the heap. As you saw earlier, there are even tools like the BDW garbage collector, that can be plugged into C as a set of library functions.</p>
<p class="para">Throughout the chapter, we have used C to illustrate different high-level services. Now we have the opportunity to bring everything together and look at all the services in a single example. Consider the following code:</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;string.h&gt;</span><a name="384"></a><a name="IDX-185"></a>
<span style="background-color:d9d9d9">#define ERR_STK_SZ  64</span>
<span style="background-color:d9d9d9">#define ERR_STR_SZ    128</span>

<span style="background-color:d9d9d9">#define ERR_LVL_WARN    0</span>
<span style="background-color:d9d9d9">#define ERR_LVL_ERROR    1</span>
<span style="background-color:d9d9d9">#define ERR_LVL_FATAL    2</span>

<span style="background-color:d9d9d9">struct ErrData</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">char *info;</span>
    <span style="background-color:d9d9d9">unsigned char level;</span>
<span style="background-color:d9d9d9">};</span>

<span style="background-color:d9d9d9">struct ErrData *stack[ERR_STK_SZ];</span>
<span style="background-color:d9d9d9">int SP;</span>
<span style="background-color:d9d9d9">char *ErrLvl[]={"WARN","ERROR", "FATAL"};</span>

<span style="background-color:d9d9d9">void bldErr();</span>
<span style="background-color:d9d9d9">void checkStack();</span>

<span style="background-color:d9d9d9">int main()</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">SP=0;</span>
    <span style="background-color:d9d9d9">bldErr();</span>
    <span style="background-color:d9d9d9">checkStack();</span>
    <span style="background-color:d9d9d9">return(0);</span>
<span style="background-color:d9d9d9">}/*end main*/</span>

<span style="background-color:d9d9d9">void bldErr()</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">stack[SP]=(struct ErrData*)malloc(sizeof(struct</span>
             <span style="background-color:d9d9d9">ErrData));</span>
    <span style="background-color:d9d9d9">(*stack[SP]).info = malloc(ERR_STR_SZ);</span>
    <span style="background-color:d9d9d9">(*stack[SP]).level = ERR_LVL_ERROR;</span>
    <span style="background-color:d9d9d9">strncpy((*stack[SP]).info,"testing",ERR_STR_SZ-1);</span>
    <span style="background-color:d9d9d9">SP++;</span>
    <span style="background-color:d9d9d9">return;</span>
<span style="background-color:d9d9d9">}/*end bldError*/</span>

<span style="background-color:d9d9d9">void checkStack()</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">int i;</span>
    <span style="background-color:d9d9d9">for(i=0;i&lt;SP;i++)</span>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">printf("%s\n",(*stack[i]).info);</span>
        <span style="background-color:d9d9d9">printf("%s\n",ErrLvl[(*stack[i]).level]);</span>
    <span style="background-color:d9d9d9">}</span>
    <span style="background-color:d9d9d9">return;</span>
<span style="background-color:d9d9d9">}/*end checkstack*/</span><a name="385"></a><a name="IDX-186"></a>
</pre>
</div>
<p class="para">When this program is executed, the following output will be produced:</p>
<div class="informalexample">
<pre class="literallayout">
testing
ERROR
</pre>
</div>
<p class="para">The previous code implements a basic error stack. As errors occur, they are popped onto the stack and the stack pointer is incremented. In this example, I run through the full gamut of memory usage. There is global data (i.e., <span class="fixed">stack [ ]</span>), heap allocation via <span class="fixed">malloc ()</span>, and the stack is used to provide storage for function activation records.</p>
<p class="para">To get a better idea of how this code is realized at the machine level, let's look at an assembly code listing. Don't be concerned if you can't immediately "see" everything that is going on. I will dissect this code shortly and point out the important things. When I am done, you can come back and take a better look. For now, just skim the following assembly code:</p>
<div class="informalexample">
<pre class="literallayout">
<span style="background-color:d9d9d9">.386P</span>
<span style="background-color:d9d9d9">.model  FLAT</span>
<span style="background-color:d9d9d9">PUBLIC  _ErrLvl</span>
<span style="background-color:d9d9d9">_DATA   SEGMENT</span>
<span style="background-color:d9d9d9">COMM    _stack:DWORD:040H</span>
<span style="background-color:d9d9d9">COMM    _SP:DWORD</span>
<span style="background-color:d9d9d9">_ErrLvl   DD    FLAT:$SG336</span>
    <span style="background-color:d9d9d9">DD    FLAT:$SG337</span>
    <span style="background-color:d9d9d9">DD    FLAT:$SG338</span>
<span style="background-color:d9d9d9">$SG336    DB    'WARN', 00H</span>
    <span style="background-color:d9d9d9">ORG $+3</span>
<span style="background-color:d9d9d9">$SG337    DB    'ERROR', 00H</span>
    <span style="background-color:d9d9d9">ORG $+2</span>
<span style="background-color:d9d9d9">$SG338    DB    'FATAL', 00H</span>
<span style="background-color:d9d9d9">_DATA   ENDS</span>
<span style="background-color:d9d9d9">PUBLIC  _bldErr</span>
<span style="background-color:d9d9d9">PUBLIC  _checkStack</span>
<span style="background-color:d9d9d9">PUBLIC  _main</span>
<span style="background-color:d9d9d9">_TEXT   SEGMENT</span>
<span style="background-color:d9d9d9">_main   PROC NEAR</span>
        <span style="background-color:d9d9d9">push ebp</span>
        <span style="background-color:d9d9d9">mov ebp, esp</span>
        <span style="background-color:d9d9d9">mov DWORD PTR _SP, 0</span>
        <span style="background-color:d9d9d9">call _bldErr</span>
        <span style="background-color:d9d9d9">call _checkStack</span>
        <span style="background-color:d9d9d9">xor  eax, eax</span>
        <span style="background-color:d9d9d9">pop  ebp</span>
        <span style="background-color:d9d9d9">ret  0</span>
<span style="background-color:d9d9d9">_main   ENDP</span>
<span style="background-color:d9d9d9">_TEXT   ENDS</span><a name="386"></a><a name="IDX-187"></a>
<span style="background-color:d9d9d9">EXTRN   _malloc:NEAR</span>
<span style="background-color:d9d9d9">EXTRN   _strncpy:NEAR</span>
<span style="background-color:d9d9d9">_DATA   SEGMENT</span>
    <span style="background-color:d9d9d9">ORG $+2</span>
<span style="background-color:d9d9d9">$SG344  DB    'testing', 00H</span>
<span style="background-color:d9d9d9">_DATA   ENDS</span>
<span style="background