Cheney's Copying Garbage Collector

This is THE garbage collection algorithm. Nearly every garbage collector out there uses some derivation of this algorithm.

Steps

Split the heap into two semispaces (halves), the from space and the to space.
Allocate memory in the "from space"
When "from space" is full:
1. Compact from the "from" space to the "to" space
2. Swap the from/to space

[!implementation]
Suppose we have 3 constants, heapStart, heapEnd, and heapMiddle.

def init = {
    heapPtr = heapStart
    fromSpaceEnd = heapMiddle

    def allocate(wanted) = {
        if (heapPtr + wanted > fromSpaceEnd) {
            gc()
        }

        val ret = heapPointer
        
        heapPointer = heapPointer + wanted
        ret
    }
}

gc:

Scan stack to copy blocks that have pointers from stack
Scan "to" space to copy blocks that have pointers from "to" space
Once a block has been copied, set the size to negative. That way you can still get the size, but you don't re-copy a block.

We will use these functions to manipulate our heap:

def size(block) = deref(block)
def next(block) = deref(block + 4)
def setSize(block, size) = assignToAddr(block, size)
def setNext(block, next) = assignToAddr(block + 4, next)

def fwdAddr(addr) = deref(addr + 4)
def setFwdAddr(addr, nextAddr) = assignToAddr(a + 4, nextAddr)

def gc() = {
    val toSpaceStart = if fromSpaceEnd == heapMiddle then heapMiddle else heapStart
    var free = toSpaceStart // Like the heap pointer
    var scan = dynamicLink // dynamic link of GC, top of stack after GC

    while (scan < memSize) {
        forwardPtrs(scan)
        scan = scan + size(scan)
    }

    // Now we must find the blocks that any reachable blocks reference
    scan = toSpaceStart
    
    while (scan < free) {
        forwardPlus(scan)
        scan = scan + size(scan)
    }
    fromSpaceEnd = toSpaceStart + semiSpaceSize
    heapPointer = free

    def forwardPtrs(add: Int) = {
        for (offset <- offset in block that holds a pointer) {
            val newAddr = copy(deref(block + offset))

            assignToAddr(addr + offset, newAddr)
        }
    }

    def copy(addr: Int): Int = {
        if (addr is in fromSpace) {
            if (size(addr) > 0) { // Not yet copied
                copyChunk(free, addr)
                setFwdAddr(addr, free) // Leave forwarding address
                setSize(addr, 0 - size(addr)) // Once a block has been copied, mark it negative
                free = free + size(free)
            }
            
            forwardingAddr(addr) // return forwarding address
        } else {
            addr
        }
    }
}