GC Handbook - Chapter 1: Introduction

Terminology and Notation

For Ruby, this probably means that VALUE is a granule, RVALUE is a cell, and it may be allocated as various types of object (RString, RClass etc) which would be the Objects.


Mutator roots

This is different to the set of root objects. It is

a finite set of mutator roots, representing pointers held in storage that is directly accessible to the mutator without going through other objects

Root objects are all objects in the heap that are directly accessible from these mutator roots.

In practice, this is normally global state, thread local storage (such as execution stacks), that contains pointers to things on the heap.


Pointers(N) = { a | a = &N[i]; ∀i: 0 ≤ i < |N| where N[i] is a pointer}

For an Object N: The set of pointer fields of N is all the addresses to fields that are part of the array, where the contents of the field is a pointer.

Basically: references are all the fields of an object that are pointers to other things.


An object is live if the mutator will access it in the future. This is an undecidable problem.

A GC is only correct if it never reclaims live objects.

We approximate liveness using pointer reachability. an object N is reachable from an object M if N can be reached by following a chain of pointers from a field of M

reachable = {N ∈ Nodes | (∃r ∈ Roots : r ⟶ N) ∨ (∃M ∈ reachable: M ⟶ N)}

The set of all Reachable objects in Nodes such that there exists a reference from a root node that points to it, or there exists another object in the reachable set that points to it.