lib0043.html

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

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

<span style="background-color:d9d9d9">}/*end forceCollection----------------------------------------*/</span>

<span style="background-color:d9d9d9">void MarkSweepMemoryManager::trace()</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">MSG0("MarkSweepMemoryManager::");</span>
    <span style="background-color:d9d9d9">MSG0 ("trace(): initiating mark-sweep\n");</span>
    <span style="background-color:d9d9d9">mark();</span><a name="592"></a><a name="IDX-318"></a>
    <span style="background-color:d9d9d9">sweep();</span>
    <span style="background-color:d9d9d9">return;</span>

<span style="background-color:d9d9d9">}/*end trace --------------------------------------------------*/</span>

<span style="background-color:d9d9d9">void MarkSweepMemoryManager::mark()</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">U4 i;</span>
    <span style="background-color:d9d9d9">U4 current;</span>

    <span style="background-color:d9d9d9">//set all OCCUPIED blocks to TESTING</span>

    <span style="background-color:d9d9d9">i=0;</span>
    <span style="background-color:d9d9d9">current=START;</span>

    <span style="background-color:d9d9d9">while(NEXT(current)!=0)</span>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">if(STATE(current)==OCCUPIED)</span>
        <span style="background-color:d9d9d9">{</span>
            <span style="background-color:d9d9d9">STATE(current)=TESTING;</span>
        <span style="background-color:d9d9d9">}</span>
        <span style="background-color:d9d9d9">current = NEXT(current);</span>
        <span style="background-color:d9d9d9">i++;</span>
    <span style="background-color:d9d9d9">}</span>

    <span style="background-color:d9d9d9">if(STATE(current)==OCCUPIED)</span>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">STATE(current)=TESTING;</span>
    <span style="background-color:d9d9d9">}</span>

<span style="background-color:d9d9d9">#ifdef  DEBUG_MS_MEM_MGR</span>
    <span style="background-color:d9d9d9">MSG0("MarkSweepMemoryManager::");</span>
    <span style="background-color:d9d9d9">MSG0("mark(): toggle OCCUPIED to TESTING\n");</span>
    <span style="background-color:d9d9d9">printState();</span>
<span style="background-color:d9d9d9">#endif</span>

    <span style="background-color:d9d9d9">//traverse the stack and heap</span>
    <span style="background-color:d9d9d9">//if find address to TESTING block, set to OCCUPIED</span>

    <span style="background-color:d9d9d9">MSG0("MarkSweepMemoryManager::");</span>
    <span style="background-color:d9d9d9">MSG0("mark(): initiating stack and heap traversals\n");</span>
    <span style="background-color:d9d9d9">traverseStack();</span>
    <span style="background-color:d9d9d9">traverseHeap();</span>
    <span style="background-color:d9d9d9">return;</span>

<span style="background-color:d9d9d9">}/*end mark --------------------------------------------------*/</span>

<span style="background-color:d9d9d9">void MarkSweepMemoryManager::traverseStack()</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">U4 currentAddr;</span><a name="593"></a><a name="IDX-319"></a>
    <span style="background-color:d9d9d9">_asm{ MOV currentAddr,ESP };</span>

    <span style="background-color:d9d9d9">MSG0("MarkSweepMemoryManager::traverseStack():");</span>
    <span style="background-color:d9d9d9">MSG1("EBP=%p\t",stackFrameBase);</span>
    <span style="background-color:d9d9d9">MSG1("ESP=%p\n",currentAddr);</span>

    <span style="background-color:d9d9d9">//basically traverse stack from current pointer to base</span>
     <span style="background-color:d9d9d9">(Lo-&gt;Hi)</span>


<span style="background-color:d9d9d9">traverseMemory((U1*)currentAddr,(stackFrameBase-currentAddr));</span>
    <span style="background-color:d9d9d9">return;</span>

<span style="background-color:d9d9d9">}/*end traverseStack------------------------------------------*/</span>

<span style="background-color:d9d9d9">void MarkSweepMemoryManager::traverseHeap()</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">MSG0("MarkSweepMemoryManager::traverseHeap(): looking at</span>
          <span style="background-color:d9d9d9">heap\n");</span>
    <span style="background-color:d9d9d9">traverseMemory(ram,size);</span>
    <span style="background-color:d9d9d9">return;</span>

<span style="background-color:d9d9d9">}/*end traverseHeap-------------------------------------------*/</span>

<span style="background-color:d9d9d9">void MarkSweepMemoryManager::traverseMemory(U1 *addr,U4 nbytes)</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">U4 i;</span>
    <span style="background-color:d9d9d9">U4 start,end;</span>
    <span style="background-color:d9d9d9">U4 *iptr;</span>

    <span style="background-color:d9d9d9">start = (U4)addr;</span>
    <span style="background-color:d9d9d9">end   = start + nbytes -1;</span>

    <span style="background-color:d9d9d9">MSG0("MarkSweepMemoryManager::traverseMemory(): ");</span>
    <span style="background-color:d9d9d9">MSG1("[start=%lx,",start);</span>
    <span style="background-color:d9d9d9">MSG1(" end=%lx]\n",end);</span>

    <span style="background-color:d9d9d9">//address = 4 bytes, so stop 4 bytes from end</span>

    <span style="background-color:d9d9d9">for(i=start;i&lt;=end-3;i++)</span>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">//point to integer value at memory address i</span>
        <span style="background-color:d9d9d9">iptr = (U4*)i;</span>

        <span style="background-color:d9d9d9">//check integer value to see if it is a heap address</span>
        <span style="background-color:d9d9d9">if( checkAddress((void *)(*iptr))==TRUE)</span>
        <span style="background-color:d9d9d9">{</span>
            <span style="background-color:d9d9d9">MSG0("MarkSweepMemoryManager::traverseMemory(): ");</span>
            <span style="background-color:d9d9d9">MSG1("value source address=%p\n",iptr);</span>
        <span style="background-color:d9d9d9">}</span>
    <span style="background-color:d9d9d9">}</span><a name="594"></a><a name="IDX-320"></a>
    <span style="background-color:d9d9d9">return;</span>

<span style="background-color:d9d9d9">}/*end traverseMemory-----------------------------------------*/</span>

<span style="background-color:d9d9d9">int MarkSweepMemoryManager::checkAddress(void *addr)</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">U4 index;</span>

    <span style="background-color:d9d9d9">if(addr==NULL){ return(FALSE); }</span>

    <span style="background-color:d9d9d9">//check to see if address is out of heap bounds</span>

    <span style="background-color:d9d9d9">if( (addr&gt;= (void*)&amp;ram[size]) || (addr&lt; (void*)&amp;ram[0]) )</span>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">return (FALSE);</span>
    <span style="background-color:d9d9d9">}</span>

    <span style="background-color:d9d9d9">//translate addr into index</span>

    <span style="background-color:d9d9d9">index = (U4)( ((U1*)addr) - &amp;ram[0] );</span>

    <span style="background-color:d9d9d9">//now check index to see if reference an actual block</span>
    <span style="background-color:d9d9d9">//a header always occupies first SZ_HEADER bytes of storage</span>

    <span style="background-color:d9d9d9">if(index&lt;SZ_HEADER){ return(FALSE); }</span>

    <span style="background-color:d9d9d9">//more sanity checks</span>

    <span style="background-color:d9d9d9">if((STATE(index)!=TESTING) || //region if free</span>
       <span style="background-color:d9d9d9">(PREV(index)&gt;=index)    || //previous element not previous</span>
       <span style="background-color:d9d9d9">(NEXT(index)&gt;=size)     || //next is beyond the end</span>
       <span style="background-color:d9d9d9">(SIZE(index)&gt;=size)     || //size of region greater</span>
                                  <span style="background-color:d9d9d9">//than whole</span>
       <span style="background-color:d9d9d9">(SIZE(index)==0))          //no size at all</span>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">MSG0("MarkSweepMemoryManager::checkAddress():");</span>
        <span style="background-color:d9d9d9">MSG1("failed sanity chk (already found) addr=%p ",addr);</span>
        <span style="background-color:d9d9d9">return(FALSE);</span>
    <span style="background-color:d9d9d9">}</span>

    <span style="background-color:d9d9d9">MSG0("MarkSweepMemoryManager::checkAddress():");</span>
    <span style="background-color:d9d9d9">MSG1("live memory block at addr=%p ",addr);</span>
    <span style="background-color:d9d9d9">MSG1("index=%lu\n",index);</span>

    <span style="background-color:d9d9d9">STATE(index)=OCCUPIED;</span>

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

<span style="background-color:d9d9d9">}/*end checkAddress-------------------------------------------*/</span><a name="595"></a><a name="IDX-321"></a>

<span style="background-color:d9d9d9">void MarkSweepMemoryManager::sweep()</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">U4 i;</span>
    <span style="background-color:d9d9d9">U4 current;</span>

    <span style="background-color:d9d9d9">MSG0("MarkSweepMemoryManager::");</span>
    <span style="background-color:d9d9d9">MSG0("sweep(): link sweep intiated\n");</span>

    <span style="background-color:d9d9d9">//recycle all the TESTING blocks</span>

    <span style="background-color:d9d9d9">i=0;</span>
    <span style="background-color:d9d9d9">current=START;</span>

    <span style="background-color:d9d9d9">while(NEXT(current)!=0)</span>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">if(STATE(current)==TESTING)</span>
        <span style="background-color:d9d9d9">{</span>
            <span style="background-color:d9d9d9">MSG0("MarkSweepMemoryManager::");</span>
            <span style="background-color:d9d9d9">MSG1("sweep(): garbage found at index=%lu\n",</span>
                  <span style="background-color:d9d9d9">current);</span>
            <span style="background-color:d9d9d9">release(current);</span>
        <span style="background-color:d9d9d9">}</span>
        <span style="background-color:d9d9d9">current = NEXT(current);</span>
        <span style="background-color:d9d9d9">i++;</span>
    <span style="background-color:d9d9d9">}</span>

    <span style="background-color:d9d9d9">if(STATE(current)==TESTING)</span>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">MSG0("MarkSweepMemoryManager::");</span>
        <span style="background-color:d9d9d9">MSG1("sweep(): garbage found at index=%lu\n",current);</span>
        <span style="background-color:d9d9d9">release(current);</span>
    <span style="background-color:d9d9d9">}</span>

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

<span style="background-color:d9d9d9">}/*end sweep -------------------------------------------------*/</span>

<span style="background-color:d9d9d9">void MarkSweepMemoryManager::release(U4 index)</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">//a header always occupies first 13 bytes of storage</span>

    <span style="background-color:d9d9d9">if(index&lt;SZ_HEADER)</span>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">MSG0("MarkSweepMemoryManager::");</span>
        <span style="background-color:d9d9d9">MSG0("release(): address in first 13 bytes\n");</span>
        <span style="background-color:d9d9d9">return;</span>