The Cyclic GC Algorithm & Tri-Color Marking

How does CPython determine that a group of cyclic objects is completely unreachable from the running program without scanning the entire memory space of the operating system?

The cyclic garbage collector achieves this by isolating internal container-to-container references from true external references, executing a deterministic graph subtraction algorithm.

Marking AbstractionGraph Algorithm

Tri-Color

Categorizes objects into Black (reachable), Grey (to visit), and White (unreachable candidates).

1. The 4-Stage Cycle Detection Algorithm#

When a generation $S$ is selected for collection, CPython executes the following deterministic procedure:

Architecture Diagram

Rendering diagram...

Mathematical Formalization#

Let $S$ represent the set of container objects in the target generation:

Step 1: Copy Reference Counters

Initialize a candidate counter gc_refs for every container in $S$ , isolating GC state from live refcounts:

\forall o \in S, \quad \text{gc\_refs}(o) \leftarrow o.\text{ob\_refcnt}

Step 2: Subtract Internal References

Iterate over every container $o \in S$ . For each child pointer $child$ referenced by $o$ (discovered via the type's tp_traverse function):

\text{if } child \in S \implies \text{gc\_refs}(child) \leftarrow \text{gc\_refs}(child) - 1

After scanning all candidates in $S$ , any container whose gc_refs remains greater than zero must have at least one external reference pointing to it from outside the candidate generation!

Step 3: Isolate Reachable Roots & Restore Graph

Containers with $\text{gc\_refs}(o) > 0$ form the Reachable Root Set. CPython marks them Black and transitively traverses all objects reachable from them, restoring their gc_refs and promoting them to Black as well.

Step 4: Sweep Unreachable White Objects

Any objects that still have $\text{gc\_refs}(o) == 0$ cannot be reached from any root variable. They are confirmed isolated cyclic garbage! CPython untracks them, calls tp_clear() to break their cyclic links, and deallocates their memory via tp_dealloc().

2. Tri-Color Marking Conceptual Model#

CPython conceptually structures graph reachability using the Tri-Color Marking abstraction:

Color	Meaning	State Invariant
Black	Reachable & Processed	Confirmed reachable from active root variables; all its child references have been fully inspected. Kept in RAM.
Grey	Reachable & Pending	Visited during traversal; queued for child pointer inspection.
White	Unreachable Candidate	Not visited from any root variable. At the end of the sweep, all remaining White objects are destroyed.

Architecture Diagram

Rendering diagram...

3. The `tp_traverse` & `tp_clear` Type Slots#

Every container class supporting garbage collection must implement two dedicated C function slots:

1. The Traversal Slot: `tp_traverse`

Visits all child PyObject* references held by the instance, invoking a visitor function callback (visitproc) on each child:

1
2
3
4
5
static int custom_traverse(CustomObject *self, visitproc visit, void *arg) {
    Py_VISIT(self->first_child);
    Py_VISIT(self->second_child);
    return 0;
}

2. The Clearing Slot: `tp_clear`

Breaks cyclic references by setting child pointers to NULL and calling Py_DECREF:

1
2
3
4
5
static int custom_clear(CustomObject *self) {
    Py_CLEAR(self->first_child);
    Py_CLEAR(self->second_child);
    return 0;
}

4. Finalization & PEP 442 (Safe `del`)#

In early versions of Python (prior to 3.4), if two objects in an unreachable cycle defined custom __del__ finalizers, Python could not determine which finalizer to run first without risking reading a destroyed partner.

Consequently, Python would abandon the cycle in gc.garbage, creating an uncollectable memory leak!

PEP 442 (Python 3.4+) resolved this problem completely:

When an unreachable cycle is discovered, CPython first executes all tp_finalize (__del__) methods on the objects while the entire cycle is still intact in memory.
Once all finalizers have finished, CPython proceeds to tp_clear and deallocates the cycle safely.

5. Concept Verification#

Test your understanding of the cyclic GC algorithm:

Concept check

How does CPython identify which containers belong to an unreachable cycle during a GC sweep?