The Cycle Collector

The problem

Consider two objects that reference each other:

a = Node(); b = Node()
a.peer = b
b.peer = a
del a, b        # both refcounts are still 1, from each other

Nothing outside can reach them, but neither count reaches zero, so neither deallocator ever runs. Pure reference counting leaks every cycle. Since cycles arise constantly in real programs — parent/child links, caches, closures capturing themselves, an exception traceback referring to the frame that holds the exception — CPython adds a second mechanism.

How CPython finds unreachable cycles

The collector maintains lists of tracked objects — only objects of types that opt in. To find garbage it uses a subtraction trick rather than a mark-from-roots walk:

1. Copy each tracked object's refcount into a scratch field (gc_refs).
2. Ask every tracked object to enumerate the objects it references, and for each reference that points at another tracked object, decrement that object's gc_refs.
3. After this pass, gc_refs counts only references from outside the candidate set. Any object left with gc_refs > 0 is reachable from outside.
4. Mark those reachable, propagate reachability to everything they point at, and whatever remains at zero is unreachable garbage — a cycle with no external owner.
5. Break the cycles by asking each garbage object to drop its references, at which point ordinary reference counting finishes the job.

Step 2 is tp_traverse. Step 5 is tp_clear. Those two functions are the entire contract, and if your type gets them wrong the collector either leaks or frees live memory.

The collector is generational: newly created tracked objects go in generation 0, survivors are promoted to 1 and then 2, and younger generations are scanned far more often. That is why a collection can fire at an arbitrary allocation, which matters below.

Does my type need this?

Ask one question: can an instance of my type hold a reference to an object that could, through any chain, refer back to my instance?

• A type whose only object field is a str you created yourself: no. Strings cannot refer back.
• A type that stores an arbitrary PyObject * handed in by the caller: yes, always. The caller can pass a list containing your instance.
• A type that stores a Python callback: yes. Closures capture things.
• A type that holds only doubles and a FILE *: no.
• Any heap type at all: effectively yes, because every instance references its type, which references the module, which references the type. That cycle exists whether you like it or not, which is why PyType_FromModuleAndSpec in practice goes with Py_TPFLAGS_HAVE_GC.

If in doubt, opt in. The cost is a small header on each instance and a traversal function; the cost of not opting in is a silent, unfixable leak that only shows up in long-running processes.

Implementing the contract

Three things go together and none may be omitted: the flag, tp_traverse, and (in practice) tp_clear.

typedef struct {
    PyObject_HEAD
    PyObject *payload;    /* arbitrary object from the caller */
    PyObject *callback;   /* arbitrary callable */
    long      counter;    /* plain C, never traversed */
} NodeObject;

static int
Node_traverse(PyObject *op, visitproc visit, void *arg)
{
    NodeObject *self = (NodeObject *)op;
    Py_VISIT(Py_TYPE(self));     /* required for heap types, 3.9+ */
    Py_VISIT(self->payload);
    Py_VISIT(self->callback);
    return 0;
}

static int
Node_clear(PyObject *op)
{
    NodeObject *self = (NodeObject *)op;
    Py_CLEAR(self->payload);
    Py_CLEAR(self->callback);
    return 0;
}

static void
Node_dealloc(PyObject *op)
{
    PyTypeObject *tp = Py_TYPE(op);
    PyObject_GC_UnTrack(op);     /* 1. stop the collector seeing us */
    (void)Node_clear(op);        /* 2. drop object references       */
    tp->tp_free(op);             /* 3. release the memory           */
    Py_DECREF(tp);               /* 4. heap types only              */
}

The canonical shape. Deviating from this order causes crashes, not leaks.

Py_VISIT(x) expands to roughly: if x is not NULL, call visit(x, arg), and if that returns nonzero, return it immediately. It handles the NULL check and the early return so you cannot forget them. Always use it rather than calling visit by hand.

The rules for tp_traverse

• Visit every PyObject * your instance owns a reference to. Miss one and the collector will conclude a live object is garbage, and free it. This is the bug that produces impossible crashes.
• Visit nothing you do not own. Reporting a borrowed reference makes the collector undercount external references and leak. Do not visit Py_None — it is immortal, but more importantly you do not own it.
• Visit Py_TYPE(self) for heap types (Python 3.9+). Static types are immortal and must not be visited.
• Do not allocate, do not run Python code, do not acquire locks, do not raise. tp_traverse runs in the middle of a collection with the object graph in a half-analysed state. It must be a pure enumeration.
• Tolerate half-built objects. The generic allocator starts tracking an instance as soon as tp_alloc returns, so a collection can call your tp_traverse after tp_new but before tp_init has filled anything in. Py_VISIT's NULL check is what makes this safe — which is why tp_new must leave fields at NULL rather than uninitialized garbage.

The rules for tp_clear

• Drop references with Py_CLEAR, never plain Py_DECREF. Clearing can re-enter your object, and the field must be NULL before the decref.
• It must be idempotent — callable twice with no ill effect — because it is called both by the collector and by your own deallocator.
• Afterwards the object must still be usable, in the sense of not crashing. Methods may legitimately raise on a cleared object, but they must not dereference NULL. Adding NULL checks to your methods is the price of GC support.
• Do not release non-Python resources here (files, sockets, malloc'd buffers). tp_clear exists to break cycles; those belong in tp_dealloc or tp_finalize.

Allocation and tracking

If your tp_new allocates the normal way — type->tp_alloc(type, 0), which resolves to PyType_GenericAlloc — then for a HAVE_GC type the object is allocated with a GC header and tracked immediately. You do not call PyObject_GC_Track yourself.

You only need the lower-level API if you are managing memory by hand:

Finalization: tp_finalize versus tp_dealloc

These are different events and conflating them causes real bugs.

tp_dealloc

Runs when the refcount reaches zero. Its job is to free memory. By the time it runs the object is already doomed; it must not make the object reachable again.

tp_finalize — the C slot behind __del__

Runs before deallocation, while the object is still fully valid, and is guaranteed to run at most once per object. It is where user-visible cleanup belongs: closing files, cancelling timers, emitting a ResourceWarning.

PEP 442 introduced tp_finalize precisely so that objects in cycles could still be finalized safely. Before it, CPython refused to collect cycles containing objects with __del__, and they piled up in gc.garbage. Today they are collected: the collector calls tp_finalize on every object in the garbage cycle first, then clears them.

If you implement tp_finalize, the standard shape is:

static void
Node_finalize(PyObject *self)
{
    /* Finalizers can run with an exception in flight. Save and restore it,
       or you will clobber the caller's exception state (Lesson 05). */
    PyObject *exc = PyErr_GetRaisedException();

    ... close resources, call back into Python if you must ...

    PyErr_SetRaisedException(exc);
}

And register it with Py_tp_finalize. Because a finalizer runs while the object is alive, it can technically store self somewhere and resurrect it; CPython handles that correctly, but it is a sharp edge to avoid.

Module state has the same obligations

A module's per-module state (Lesson 08) is memory attached to the module object, and if it holds PyObject * fields the module itself needs m_traverse, m_clear and m_free in its PyModuleDef, written exactly like tp_traverse/tp_clear. A module that caches type objects and forgets m_traverse produces an uncollectable module — the classic "my extension leaks on reimport" bug.

Observing the collector

import gc

gc.collect()                      # returns the number of unreachable objects found
gc.get_count()                    # allocations since last collection, per generation
gc.get_threshold()                # (700, 10, 10) by default
gc.freeze()                       # move everything to a permanent generation

gc.set_debug(gc.DEBUG_LEAK)       # verbose: report everything found unreachable
gc.get_referrers(obj)             # who points at obj  -- invaluable for leak hunting
gc.get_referents(obj)             # what obj points at -- this is tp_traverse, exposed

import gc

class Node:
    __slots__ = ("peer",)
    def __init__(self): self.peer = None

gc.collect()
a, b = Node(), Node()
a.peer, b.peer = b, a
del a, b
print("cycle objects collected:", gc.collect())   # expect 2

# Now watch the generational behaviour.
gc.set_debug(gc.DEBUG_STATS)
for _ in range(2000):
    x, y = Node(), Node(); x.peer, y.peer = y, x
gc.set_debug(0)

# And inspect a real extension type's traversal:
print(gc.get_referents({"k": [1, 2]}))
print(gc.is_tracked(1), gc.is_tracked([]), gc.is_tracked((1, 2)), gc.is_tracked(("a",)))

Further reading

• Supporting Cyclic Garbage Collection. The contract, the API, and the exact deallocation order.
• CPython Developer's Guide — Garbage Collector Design. The clearest available explanation of the reference-subtraction algorithm and generations.
• PEP 442 — Safe Object Finalization. Why tp_finalize exists and how resurrection is handled.
• The gc module. In particular get_referents, get_referrers and the debug flags.