lib0027.html

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

<li class="listitem">
<p class="first-para">Push function arguments onto the stack.</p>
</li>
<li class="listitem">
<p class="first-para">Push the return address onto the stack.</p>
</li>
<li class="listitem">
<p class="first-para">Jump to the location of the procedure.</p>
</li>
</ol>
<p class="para">Using Intel's <span class="fixed">CALL</span> instruction will typically take care of the last two steps automatically. The function being invoked must also take a few steps to ensure that it can access the parameters passed to it and create local storage:</p>
<ol class="orderedlist">
<li class="first-listitem">
<p class="first-para">Push <span class="fixed">EBP</span> on to the stack (to save its value).</p>
</li>
<li class="listitem">
<p class="first-para">Copy the current <span class="fixed">ESP</span> value into <span class="fixed">EBP</span>.</p>
</li>
<li class="listitem">
<p class="first-para">Decrement <span class="fixed">ESP</span> to allocate local storage.</p>
</li>
<li class="listitem">
<p class="first-para">Execute the function's instructions.</p>
</li>
</ol>
<p class="para">The code that performs these four steps is known as the invoked function's <i class="emphasis">prologue.</i>
</p>
<p class="para">The result of all this stack manipulation is that we end up with a stack arrangement similar to that displayed in <a class="internaljump" href="#ch03fig08">Figure 3.8</a>.</p>
<div class="figure">
<a name="316"></a><a name="ch03fig08"></a><span class="figuremediaobject"><img src="images/fig167_01.jpg" height="280" width="334" alt="" border="0"></span>
<br style="line-height: 1">
<span class="figure-title"><span class="figure-titlelabel">Figure 3.8</span></span>
</div>
<p class="para">The region of the stack used to store a function's parameters and local storage is referred to as the <i class="emphasis">activation record</i> because every time a procedure is activated (i.e., invoked), this information must be specified. An activation record is also known as a <i class="emphasis">stack frame.</i>
</p>
<a name="317"></a><a name="IDX-139"></a>
<p class="para">The stack region displayed in <a class="internaljump" href="#ch03fig08">Figure 3.8</a> is an example of an activation record.</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">On Intel machines, the <span class="fixed">EBP</span> register is pushed on the stack so that it can serve as a reference point. <span class="fixed">EBP</span> is known as the <i class="emphasis">stack frame pointer,</i> and it is used so that elements in the activation record can be referenced via indirect addressing (i.e., <span class="fixed">MOV AX</span>, <span class="fixed">[EBP+5]</span>).</p>
</td>
</tr>
</table>
<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 arrangement of elements in the activation record does not necessarily have to follow the conventions that I adhere to in this section. Different languages and compilers will use different ordering for items in the activation record.</p>
</td>
</tr>
</table>
<p class="para">When the function has done its thing and is ready to return, it must perform the following stack maintenance steps:</p>
<ol class="orderedlist">
<li class="first-listitem">
<p class="first-para">Reclaim local storage.</p>
</li>
<li class="listitem">
<p class="first-para">Pop <span class="fixed">EBP</span> off the stack.</p>
</li>
<li class="listitem">
<p class="first-para">Pop the return address off the stack.</p>
</li>
<li class="listitem">
<p class="first-para">Jump to the return address.</p>
</li>
</ol>
<p class="para">The Intel <span class="fixed">RET</span> instruction will usually take care of the last two steps.</p>
<p class="para">The code that performs the previous four steps is known as the invoked function's <i class="emphasis">epilogue.</i>
</p>
<p class="para">Once the invoked function has returned, the invoking function will need to take the following steps to get its hands on the return value and clean up the stack:</p>
<ol class="orderedlist">
<li class="first-listitem">
<p class="first-para">Pop the function arguments off the stack.</p>
</li>
<li class="listitem">
<p class="first-para">Pop the return value off the stack.</p>
</li>
<li class="listitem">
<p class="first-para">Pop the saved program state off the stack.</p>
</li>
</ol>
<a name="318"></a><a name="IDX-140"></a>
<p class="para">Another way to handle the arguments is to simply increment the stack pointer. We really have no use for the function arguments once the invoked function has returned, so this is a cleaner and more efficient way to reclaim the corresponding stack space.</p>
<p class="para">This whole process can be seen in terms of four compound steps:</p>
<ol class="orderedlist">
<li class="first-listitem">
<p class="first-para">Invoking function sets up stack</p>
</li>
<li class="listitem">
<p class="first-para">Function invoked sets up EBP and local storage (prologue) -----called function executes-----</p>
</li>
<li class="listitem">
<p class="first-para">Function invoked frees local storage and restores EBP (epilogue)</p>
</li>
<li class="listitem">
<p class="first-para">Invoking function extracts return value and cleans up stack</p>
</li>
</ol>
<p class="para">Here is a simple example to illustrate all of the previous points. Consider the following C code:</p>
<div class="informalexample">
<pre class="literallayout">
<span style="background-color:d9d9d9">/* ---stkfram.c--- */</span>

<span style="background-color:d9d9d9">unsigned char array[] = {1,2,3,4,5};</span>

<span style="background-color:d9d9d9">unsigned short sigma(unsigned char *cptr,int n)</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">int i;</span>
    <span style="background-color:d9d9d9">int sum;</span>
    <span style="background-color:d9d9d9">sum= 0;</span>
    <span style="background-color:d9d9d9">for(i=0;i&lt;n;i++){ sum = sum+ cptr[i]; }</span>
    <span style="background-color:d9d9d9">return(sum);</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">int retval;</span>
    <span style="background-color:d9d9d9">retval = sigma(array,5);</span>
    <span style="background-color:d9d9d9">return;</span>
<span style="background-color:d9d9d9">}</span>
</pre>
</div>
<p class="para">If we look at a listing file, we can see how activation records are utilized in practice:</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 _array</span>
<span style="background-color:d9d9d9">_DATA  SEGMENT</span>
<span style="background-color:d9d9d9">_array DB   01H</span>
       <span style="background-color:d9d9d9">DB   02H</span>
       <span style="background-color:d9d9d9">DB   03H</span>
       <span style="background-color:d9d9d9">DB   04H</span>
       <span style="background-color:d9d9d9">DB   05H</span>
<span style="background-color:d9d9d9">_DATA  ENDS</span>
<span style="background-color:d9d9d9">PUBLIC _sigma</span><a name="319"></a><a name="IDX-141"></a>
<span style="background-color:d9d9d9">_TEXT  SEGMENT</span>
<span style="background-color:d9d9d9">_cptr$ = 8</span>
<span style="background-color:d9d9d9">_n$ = 12</span>
<span style="background-color:d9d9d9">_i$ = -8</span>
<span style="background-color:d9d9d9">_sum$ = -4</span>
<span style="background-color:d9d9d9">_sigma    PROC NEAR</span>
<span style="background-color:d9d9d9">; 7    : {</span>

       <span style="background-color:d9d9d9">push  ebp</span>
       <span style="background-color:d9d9d9">mov   ebp, esp</span>
       <span style="background-color:d9d9d9">sub   esp, 8</span>

<span style="background-color:d9d9d9">; 8    :     int i;</span>
<span style="background-color:d9d9d9">; 9    :     int sum;</span>
<span style="background-color:d9d9d9">; 10   :</span>
<span style="background-color:d9d9d9">; 11   :     sum= 0;</span>

       <span style="background-color:d9d9d9">mov   DWORD PTR _sum$[ebp], 0</span>

<span style="background-color:d9d9d9">; 12   :     for(i=0;i&lt;n;i++){ sum = sum+ cptr[i]; }</span>

       <span style="background-color:d9d9d9">mov   DWORD PTR _i$[ebp], 0</span>
       <span style="background-color:d9d9d9">jmp   SHORT $L31</span>
<span style="background-color:d9d9d9">$L32:</span>
       <span style="background-color:d9d9d9">mov   eax, DWORD PTR _i$[ebp]</span>
       <span style="background-color:d9d9d9">add   eax, 1</span>
       <span style="background-color:d9d9d9">mov   DWORD PTR _i$[ebp], eax</span>
<span style="background-color:d9d9d9">$L31:</span>
       <span style="background-color:d9d9d9">mov   ecx, DWORD PTR _i$[ebp]</span>
       <span style="background-color:d9d9d9">cmp   ecx, DWORD PTR _n$[ebp]</span>
       <span style="background-color:d9d9d9">jge   SHORT $L33</span>
       <span style="background-color:d9d9d9">mov   edx, DWORD PTR _cptr$[ebp]</span>
       <span style="background-color:d9d9d9">add   edx, DWORD PTR _i$[ebp]</span>
       <span style="background-color:d9d9d9">xor   eax, eax</span>
       <span style="background-color:d9d9d9">mov   al, BYTE PTR [edx]</span>
       <span style="background-color:d9d9d9">mov   ecx, DWORD PTR _sum$[ebp]</span>
       <span style="background-color:d9d9d9">add   ecx, eax</span>
       <span style="background-color:d9d9d9">mov   DWORD PTR _sum$[ebp], ecx</span>
       <span style="background-color:d9d9d9">jmp   SHORT $L32</span>
<span style="background-color:d9d9d9">$L33:</span>

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

       <span style="background-color:d9d9d9">mov   ax, WORD PTR _sum$[ebp]</span>

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

       <span style="background-color:d9d9d9">mov   esp, ebp</span>
       <span style="background-color:d9d9d9">pop   ebp</span>
       <span style="background-color:d9d9d9">ret   0</span>
<span style="background-color:d9d9d9">_sigma ENDP</span><a name="320"></a><a name="IDX-142"></a>
<span style="background-color:d9d9d9">_TEXT  ENDS</span>
<span style="background-color:d9d9d9">PUBLIC _main</span>
<span style="background-color:d9d9d9">_TEXT  SEGMENT</span>
<span style="background-color:d9d9d9">_retval$ = -4</span>
<span style="background-color:d9d9d9">_main  PROC NEAR</span>

<span style="background-color:d9d9d9">; 17   : {</span>

       <span style="background-color:d9d9d9">push   ebp</span>
       <span style="background-color:d9d9d9">mov    ebp, esp</span>
       <span style="background-color:d9d9d9">push   ecx</span>

<span style="background-color:d9d9d9">; 18   :      int retval;</span>
<span style="background-color:d9d9d9">; 19   :</span>
<span style="background-color:d9d9d9">; 20   :      retval = sigma(array,5);</span>

       <span style="background-color:d9d9d9">push   5</span>
       <span style="background-color:d9d9d9">push   OFFSET FLAT:_array</span>
       <span style="background-color:d9d9d9">call   _sigma</span>
       <span style="background-color:d9d9d9">add    esp, 8</span>
       <span style="background-color:d9d9d9">and    eax, 65535                ; 0000ffffH</span>
       <span style="background-color:d9d9d9">mov    DWORD PTR _retval$[ebp], eax</span>

<span style="background-color:d9d9d9">; 21   :</span>
<span style="background-color:d9d9d9">; 22   :      //printf("retval=%d\n",retval);</span>
<span style="background-color:d9d9d9">; 23   :      return;</span>
<span style="background-color:d9d9d9">; 24   : }</span>

       <span style="background-color:d9d9d9">mov    esp, ebp</span>
       <span style="background-color:d9d9d9">pop    ebp</span>
       <span style="background-color:d9d9d9">ret    0</span>