lib0043.html

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

<span style="background-color:d9d9d9">class MarkSweepMemoryManager</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">private:</span>
    <span style="background-color:d9d9d9">HANDLE handle;</span>
    <span style="background-color:d9d9d9">U1 *ram;        //pointer to memory storage</span>
    <span style="background-color:d9d9d9">U4 size;        //nbytes in storage</span>
    <span style="background-color:d9d9d9">U1 ticks;       //used to trigger collection</span>
    <span style="background-color:d9d9d9">U1 period;      //# ticks before collect</span>

    <span style="background-color:d9d9d9">void split(U4 addr,U4 nbytes);</span>

    <span style="background-color:d9d9d9">void trace();</span>
    <span style="background-color:d9d9d9">void mark();</span>
    <span style="background-color:d9d9d9">void traverseStack();</span><a name="588"></a><a name="IDX-314"></a>
    <span style="background-color:d9d9d9">void traverseHeap();</span>
    <span style="background-color:d9d9d9">void traverseMemory(U1 *addr,U4 nbytes);</span>
    <span style="background-color:d9d9d9">int checkAddress(void *addr);</span>
    <span style="background-color:d9d9d9">void sweep();</span>

    <span style="background-color:d9d9d9">void release(U4 index);</span>
    <span style="background-color:d9d9d9">void merge(U4 prev,U4 current,U4 next);</span>

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

    <span style="background-color:d9d9d9">MarkSweepMemoryManager(U4 nbytes,U1 maxticks);</span>
    <span style="background-color:d9d9d9">~MarkSweepMemoryManager();</span>

    <span style="background-color:d9d9d9">void*allocate(U4 nbytes);</span>
    <span style="background-color:d9d9d9">void forceCollection();</span>
    <span style="background-color:d9d9d9">void printState();</span>
<span style="background-color:d9d9d9">};</span>

<span style="background-color:d9d9d9">MarkSweepMemoryManager::MarkSweepMemoryManager(U4 nbytes,U1</span>
         <span style="background-color:d9d9d9">maxticks)</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">handle = GetProcessHeap();</span>
    <span style="background-color:d9d9d9">if(handle==NULL)</span>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">printf("MarkSweepMemoryManager::");</span>
        <span style="background-color:d9d9d9">printf("MarkSweepMemoryManager():");</span>
        <span style="background-color:d9d9d9">printf ("invalid handle\n");</span>
        <span style="background-color:d9d9d9">exit (1);</span>
    <span style="background-color:d9d9d9">}</span>

    <span style="background-color:d9d9d9">ram = (U1*)HeapAlloc(handle,HEAP_ZERO_MEMORY,nbytes);</span>

    <span style="background-color:d9d9d9">//for portability, you could use:</span>
    <span style="background-color:d9d9d9">//ram = (unsigned char*)malloc(nbytes);</span>

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

    <span style="background-color:d9d9d9">if(size&lt;=SZ_HEADER)</span>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">printf("MarkSweepMemoryManager::");</span>
        <span style="background-color:d9d9d9">printf("MarkSweepMemoryManager():");</span>
        <span style="background-color:d9d9d9">printf("not enough memory fed to constructor\n");</span>
        <span style="background-color:d9d9d9">exit (1);</span>
    <span style="background-color:d9d9d9">}</span>

    <span style="background-color:d9d9d9">PREV(START)=0;</span>
    <span style="background-color:d9d9d9">NEXT(START)=0;</span>
    <span style="background-color:d9d9d9">STATE(START)=FREE;</span>
    <span style="background-color:d9d9d9">SIZE(START)=size-SZ_HEADER;</span>

    <span style="background-color:d9d9d9">MSG0("MarkSweepMemoryManager::");</span><a name="589"></a><a name="IDX-315"></a>
    <span style="background-color:d9d9d9">MSG1("MarkSweepMemoryManager(): ram[%lu], ",nbytes);</span>

    <span style="background-color:d9d9d9">ticks = 0;</span>
    <span style="background-color:d9d9d9">period = maxticks;</span>

    <span style="background-color:d9d9d9">MSG1("ticks=%u, ",ticks);</span>
    <span style="background-color:d9d9d9">MSG1("period=%u\n",period);</span>

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

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

<span style="background-color:d9d9d9">MarkSweepMemoryManager::~MarkSweepMemoryManager()</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">if(HeapFree(handle,HEAP_NO_SERIALIZE,ram)==0)</span>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">printf("MarkSweepMemoryManager::");</span>
        <span style="background-color:d9d9d9">printf("~MarkSweepMemoryManager():");</span>
        <span style="background-color:d9d9d9">printf("could not free heap storage\n");</span>
        <span style="background-color:d9d9d9">return;</span>
    <span style="background-color:d9d9d9">}</span>

    <span style="background-color:d9d9d9">//for portability, you could use:</span>
    <span style="background-color:d9d9d9">//free(ram);</span>

    <span style="background-color:d9d9d9">MSG0("MarkSweepMemoryManager::");</span>
    <span style="background-color:d9d9d9">MSG0("~MarkSweepMemoryManager()");</span>
    <span style="background-color:d9d9d9">MSG1("free ram[%lu]\n",size);</span>
    <span style="background-color:d9d9d9">return;</span>

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

<span style="background-color:d9d9d9">/*</span>
<span style="background-color:d9d9d9">U4 nbytes    -    number of bytes required</span>
<span style="background-color:d9d9d9">returns address of first byte of memory region allocated</span>
<span style="background-color:d9d9d9">( or NULL if cannot allocate a large enough block )</span>
<span style="background-color:d9d9d9">*/</span>

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

    <span style="background-color:d9d9d9">MSG0("MarkSweepMemoryManager::");</span>
    <span style="background-color:d9d9d9">MSG1("allocate(%lu)\n", nbytes);</span>

    <span style="background-color:d9d9d9">if(nbytes==0)</span>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">MSG0("MarkSweepMemoryManager::");</span>
        <span style="background-color:d9d9d9">MSG0("allocate(): zero bytes requested\n");</span>
        <span style="background-color:d9d9d9">return(NULL);</span>
    <span style="background-color:d9d9d9">}</span><a name="590"></a><a name="IDX-316"></a>

    <span style="background-color:d9d9d9">//before we start, garbage collect if the time has arrived</span>

    <span style="background-color:d9d9d9">ticks++;</span>
    <span style="background-color:d9d9d9">MSG0("MarkSweepMemoryManager::");</span>
    <span style="background-color:d9d9d9">MSG1("allocate(): gc check -&gt; [ticks,period]=[%u,",ticks);</span>
    <span style="background-color:d9d9d9">MSG1("%u]\n",period);</span>
    <span style="background-color:d9d9d9">if(ticks==period)</span>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">trace();</span>
        <span style="background-color:d9d9d9">ticks=0;</span>
    <span style="background-color:d9d9d9">}</span>

    <span style="background-color:d9d9d9">//traverse the linked list, starting with first element</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((SIZE(current)&gt;=nbytes)&amp;&amp;(STATE(current)==FREE))</span>
        <span style="background-color:d9d9d9">{</span>
            <span style="background-color:d9d9d9">split(current,nbytes);</span>
            <span style="background-color:d9d9d9">return((void*)&amp;ram[current]);</span>
        <span style="background-color:d9d9d9">}</span>
        <span style="background-color:d9d9d9">current = NEXT(current);</span>
    <span style="background-color:d9d9d9">}</span>

    <span style="background-color:d9d9d9">//handle the last block ( which has NEXT(current)=0 )</span>

    <span style="background-color:d9d9d9">if((SIZE(current)&gt;=nbytes)&amp;&amp;(STATE(current)==FREE))</span>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">split(current,nbytes);</span>
        <span style="background-color:d9d9d9">return((void*)&amp;ram[current]);</span>
    <span style="background-color:d9d9d9">}</span>

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

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

<span style="background-color:d9d9d9">/*</span>
<span style="background-color:d9d9d9">breaks [free] region into [alloc] [free] pair, if possible</span>
<span style="background-color:d9d9d9">*/</span>

<span style="background-color:d9d9d9">void MarkSweepMemoryManager::split(U4 addr, U4 nbytes)</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">/*</span>
    <span style="background-color:d9d9d9">want payload to have enough room for</span>
    <span style="background-color:d9d9d9">nbytes = size of request</span>
    <span style="background-color:d9d9d9">SZ_HEADER = header for new region</span>
    <span style="background-color:d9d9d9">SZ_HEADER = payload for new region (arbitrary 13 bytes)</span>
    <span style="background-color:d9d9d9">*/</span><a name="591"></a><a name="IDX-317"></a>
    <span style="background-color:d9d9d9">if(SIZE(addr)&gt;= nbytes+SZ_HEADER+SZ_HEADER)</span>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">U4 oldnext;</span>
        <span style="background-color:d9d9d9">U4 oldprev;</span>
        <span style="background-color:d9d9d9">U4 oldsize;</span>

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

        <span style="background-color:d9d9d9">MSG0("MarkSweepMemoryManager::");</span>
        <span style="background-color:d9d9d9">MSG0("split(): split=YES\n");</span>

        <span style="background-color:d9d9d9">oldnext=NEXT(addr);</span>
        <span style="background-color:d9d9d9">oldprev=PREV(addr);</span>
        <span style="background-color:d9d9d9">oldsize=SIZE(addr);</span>

        <span style="background-color:d9d9d9">newaddr = addr + nbytes + SZ_HEADER;</span>

        <span style="background-color:d9d9d9">NEXT(addr)=newaddr;</span>
        <span style="background-color:d9d9d9">PREV(addr)=oldprev;</span>
        <span style="background-color:d9d9d9">STATE(addr)=OCCUPIED;</span>
        <span style="background-color:d9d9d9">SIZE(addr)=nbytes;</span>

        <span style="background-color:d9d9d9">NEXT(newaddr)=oldnext;</span>
        <span style="background-color:d9d9d9">PREV(newaddr)=addr;</span>
        <span style="background-color:d9d9d9">STATE(newaddr)=FREE;</span>
        <span style="background-color:d9d9d9">SIZE(newaddr)=oldsize-nbytes-SZ_HEADER;</span>
    <span style="background-color:d9d9d9">}</span>
    <span style="background-color:d9d9d9">else</span>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">MSG0("MarkSweepMemoryManager::");</span>
        <span style="background-color:d9d9d9">MSG0("split(): split=NO\n");</span>
        <span style="background-color:d9d9d9">STATE(addr)=OCCUPIED;</span>
    <span style="background-color:d9d9d9">}</span>
    <span style="background-color:d9d9d9">return;</span>

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

<span style="background-color:d9d9d9">void MarkSweepMemoryManager::forceCollection()</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">MSG0("MarkSweepMemoryManager::");</span>
    <span style="background-color:d9d9d9">MSG0("forceCollection(): forcing collection\n");</span>