Lesson 14 · The mark phase - Build a Garbage Collector

The mark phase

The mark phase is the trace, colored. Today you build it - grey the roots, then repeatedly take a gray object, grey its white children, and blacken it - until every reachable object is black.

The goal

Blacken exactly the reachable objects by draining a gray worklist from the roots.

Start here - the target

TO DO

Scenario: Marking blackens the reachable set and leaves garbage white

Givenr = 0 rooted with r.field0 = a (a = 1), a.field0 = b (b = 2), and an unreachable object u = 3

WhenMark() runs from a fully white heap

Thenobjects 0, 1, 2 are Black and object 3 is still White

Andthe set of black objects equals the reachable set - no reachable object is left gray or white

Background

The mark phase is the reachable-set trace from the last chapter, expressed in colors. Start by greying every root - they are reachable by definition and their children are not yet scanned. Then drain a worklist of gray objects: pop one, look at each child, and grey any child that is still white (newly discovered); once its children are all greyed, paint the object black. Repeat until no gray remains.

Greying a child only if it is white is what makes this terminate and handle sharing and cycles for free - an object already gray or black is not re-added, exactly like the seen guard before. When the worklist empties, black is the reachable set and white is the garbage: every live object the roots can reach is black, and everything the trace never touched is still white. That white-versus-black split is the entire decision the sweep will act on next. The gray color is transient - it only exists while the phase runs.

Make it work

func (h *Heap) Mark() {
  var gray []Ref
  for _, r := range h.Roots() { h.SetColor(r, Gray); gray = append(gray, r) }
  for len(gray) > 0 {
    r := gray[len(gray)-1]; gray = gray[:len(gray)-1] // pop
    for _, c := range h.Children(r) {
      if h.Color(c) == White { h.SetColor(c, Gray); gray = append(gray, c) }
    }
    h.SetColor(r, Black)
  }
}

CheckpointDONE

The mark phase blackens exactly the reachable objects. Commit and stop here.