58. Garbage collection: mark and sweep

A heap that only grows

Since chapter 50, every object the VM allocates goes onto one list, the object list. Nothing ever comes off it. Run this:

let s = "";
for (let i = 0; i < 100000; i = i + 1) {
  s = s + "x";
}

Each pass makes a new, longer string. After the next pass, nothing can reach the old one. But the object list still links it, so the heap keeps every string the program ever built.

You may wonder why this matters, since the VM is written in JavaScript and JavaScript has a garbage collector. The catch is that V8 frees an object only when nothing refers to it, and the object list refers to everything. Only the VM knows which objects Drip code can still use. So the VM needs its own collector, over its own heap.

Reachable from the roots

Drip code can only reach an object by starting from something it holds directly: a value on the stack, a global, a closure that is running. Those are the roots. Anything reachable from them, through fields, upvalues, constants and so on, might be used again. Anything else can’t be, ever, so it is safe to free. Here are the VM’s roots:

markRoots(mark) {
  for (let i = 0; i < this.sp; i++) {
    mark(this.stack[i]);
  }
  for (const f of this.frames) {
    mark(f.closure);
  }
  for (let u = this.openUpvalues; u;
       u = u.nextOpen) mark(u);
  this.globals.forEach((k, v) => {
    mark(k);
    mark(v);
  });
  mark(this.initString);
}

The stack holds locals and temporaries. Each frame’s closure is running, so its constants must stay. Open upvalues sit on the VM’s own list, which later captures reuse, so they must stay valid even if no closure holds them any more. Globals are reachable by name. initString is the interned "init", kept for chapter 59. The heap adds two more: the functions the compiler is still building, which no VM structure points at yet, and a small extraRoots stack for values that are briefly reachable from nowhere.

Marking: white, grey, black

Marking an object sets its isMarked flag. But an object’s own references must be marked too, and theirs, and so on. Doing that by recursion would follow a long linked list a hundred thousand calls deep and overflow the host stack (chapter 9). So the collector keeps an explicit stack of objects still to trace:

markObject(o) {
  if (!o || o.isMarked) return;
  o.isMarked = true;
  this.gray.push(o); // reached, not traced
}

Then it drains that stack. “Blackening” an object marks everything it refers to, and what that is depends on its type:

blacken(o) {
  switch (o.type) {
    case 'string': case 'native':
      return;
    case 'upvalue':
      this.markValue(o.closed);
      return;
    case 'closure':
      this.markObject(o.fn);
      for (const u of o.upvalues)
        this.markObject(u);
      return;
    case 'instance':
      this.markObject(o.klass);
      this.markTable(o.fields);
      return;
    // function, class, bound: the same idea
  }
}

Step through a collection:

collect() {
  vm.markRoots(markValue);
  while (gray.length)
    blacken(gray.pop());
  strings.removeWhite();
  sweep();
}

The early return in markObject does two jobs: nothing is traced twice, and a cycle can’t send marking round forever.

Sweeping, and a weak table

Sweeping walks the object list once. Marked objects stay and are reset to white for next time. Unmarked ones are unlinked:

let prev = null;
let o = this.objects;
while (o) {
  if (o.isMarked) {
    o.isMarked = false;
    prev = o;
    o = o.next;
  } else {
    const dead = o;
    o = o.next;
    if (prev) prev.next = o;
    else this.objects = o;
    this.bytesAllocated -= SIZE[dead.type];
  }
}

Once unlinked, nothing in the VM refers to the dead object, and V8’s own collector can reclaim the memory.

One table needs care: the interning table of chapter 52. It refers to every string, so if it were a root, no string would ever die. And if it kept entries for strings that sweep frees, copyString could hand out a dead string. So the table is weak: between marking and sweeping, strings.removeWhite() deletes every entry whose string is unmarked.

When to collect, and catching mistakes

Collecting costs time, so the VM doesn’t do it on every allocation. It counts rough object sizes in bytesAllocated and collects when that passes nextGC. After each collection, nextGC becomes twice what survived (at least 1 MiB). A program with a large live heap therefore collects less often, instead of re-marking the same big heap over and over.

Bugs like that hide, because collections are rare. So the heap has a stress mode that collects on every allocation. In JavaScript, a freed object doesn’t actually vanish while something still refers to it, so the heap also poisons freed objects: it deletes their fields and makes reading type throw use after free. The test suite runs corpus programs under stress mode, so a missing root fails loudly. Poisoning is debug-only, and chapter 60 shows why.

Your turn

function collect(heap, roots) {
  const gray = [];
  // 1. mark the roots (grey)
  // 2. trace until gray is empty
  // 3. sweep: keep marked, reset
  return heap;
}

function removeWhite(table) {
  // delete entries whose string
  // was not marked
}

What you learned

• Garbage collection frees objects nothing can reach. The VM needs its own, because its object list keeps every object alive as far as V8 can tell.
• The roots are the stack, frames’ closures, open upvalues, globals, the init string and the compiler’s functions.
• Tri-colour marking: white, grey (on the grey stack), black. An explicit stack avoids deep recursion, and the mark check stops cycles.
• Mark-sweep: mark from the roots, then sweep the object list and unlink white objects. The string table is weak.
• Collections run when allocation passes nextGC. Stress mode and poisoning turn a missing root into an immediate error.