How CPython's Garbage Collector Works

CPython manages memory with two cooperating mechanisms: reference counting for the common case, and a cyclic garbage collector for the cases reference counting cannot handle. This article traces both through the CPython 3.15 source, with C-level examples you can build yourself.

Reference counting

Every Python object carries a reference count (ob_refcnt). When a new reference is created the count goes up; when a reference goes away it goes down. When it reaches zero the object is deallocated immediately, and its references are decremented in turn:

>>> import sys
>>> x = object()
>>> sys.getrefcount(x)   # 2: x and the argument
2
>>> y = x
>>> sys.getrefcount(x)
3
>>> del y
>>> sys.getrefcount(x)
2

The implementation lives in Objects/object.c. Py_INCREF and Py_DECREF are the public macros; Py_DECREF calls _Py_Dealloc (and thus tp_dealloc) when the count hits zero:

// Objects/object.c
void
_Py_Dealloc(PyObject *op)
{
    destructor dealloc = Py_TYPE(op)->tp_dealloc;
    ...
    (*dealloc)(op);
}

Reference counting is deterministic and prompt, but it cannot reclaim reference cycles:

>>> container = []
>>> container.append(container)
>>> del container   # refcount never reaches 0

container holds a reference to itself, so deleting our variable leaves the count at 1. That is what the cyclic collector exists to clean up.

The cyclic collector

The collector only deals with container objects – things that can hold references to other objects (lists, dicts, class instances, …). Atomic objects like ints and strings never form cycles on their own.

The implementation is in Python/gc.c. The algorithm, at a high level:

Start from a set of candidate objects (a generation).
Compute, for each candidate, how many references it receives from other candidates. Store that in a temporary gc_ref field.
Any candidate with gc_ref == 0 after this step is not referenced from outside the candidate set – it is tentatively unreachable.
Re-scan: objects reachable from a gc_ref > 0 object are moved back to the reachable list.
What remains in the unreachable list is truly garbage.

The trick is that the real reference count is never touched. The collector copies it into gc_ref (in the _gc_prev field of PyGC_Head) and works on the copy. The original ob_refcnt is restored afterwards.

Memory layout

In the default (GIL) build, every GC-tracked object has a PyGC_Head prepended to it:

                  +------------------+  <- PyGC_Head
                  |   _gc_next       |
                  +------------------+
                  |   _gc_prev       |
object ---------> +------------------+
                  |   ob_refcnt      |
                  +------------------+
                  |   *ob_type       |
                  +------------------+
                  |       ...        |

The object pointer still points at ob_refcnt, so normal code is unaffected. The collector reaches the head with ((PyGC_Head *)obj) - 1, exposed as the AS_GC macro in Python/gc.c.

The two head fields are “fat pointers”: their low bits are reused as flags (PREV_MASK_COLLECTING, _PyGC_PREV_MASK_FINALIZED, NEXT_MASK_UNREACHABLE), and during collection _gc_prev is reused to store gc_ref.

In the free-threaded build there is no PyGC_Head; the equivalent state lives in ob_gc_bits and the collector scans the whole heap via mimalloc instead of using generations.

A cycle in action

>>> import gc
>>> class Link:
...     def __init__(self, next_link=None):
...         self.next_link = next_link
...
>>> a = Link()
>>> b = Link(a)
>>> a.next_link = b          # cycle: a -> b -> a
>>> del a, b                 # unreachable, but refcounts stay at 1
>>> gc.collect()
4                            # 2 Link objects + 2 __dict__ dicts

Generations

To keep collections cheap, the default build splits tracked objects into three generations. New objects start in generation 0; survivors are promoted. Collections happen when allocation/deallocation counters cross thresholds:

>>> import gc
>>> gc.get_threshold()
(2000, 10, 10)

Generation 0 is collected when allocations minus deallocations exceed threshold0 (2000).
Generation 1 is collected when generation 0 has been collected threshold1 (10) times since generation 1 last was.
Generation 2 (full collection) uses an additional ratio check (long_lived_pending / long_lived_total > 25%) so that building a large set of long-lived objects does not trigger O(n^2) full collections.

The free-threaded build is non-generational: every collection scans the entire heap.

>>> gc.collect(0)            # collect only generation 0
>>> gc.get_objects(generation=1)

Finalizers and destruction

Once the unreachable set is known, destruction proceeds carefully:

Weak references with callbacks are handled (callbacks enqueued for reachable weakrefs; ignored when both sides are unreachable).
Objects with a legacy tp_del slot go to gc.garbage.
tp_finalize is called and the object is marked finalized.
Resurrected objects are re-scanned.
Weak references still pointing at unreachable objects are cleared.
tp_clear breaks every internal link, dropping refcounts to 0 and freeing the objects.

tp_clear is what makes cycle collection actually reclaim memory: it severs the references so ordinary refcounting can finish the job.

Writing a GC-tracked C extension

A type that can participate in cycles must:

set Py_TPFLAGS_HAVE_GC in tp_flags,
implement tp_traverse (visit every referenced object with Py_VISIT),
implement tp_clear (drop references with Py_CLEAR),
allocate with PyObject_GC_New and free with PyObject_GC_Del,
track/untrack with PyObject_GC_Track / PyObject_GC_UnTrack.

Here is a minimal node type holding a list of children and a name:

#include <Python.h>

typedef struct {
    PyObject_HEAD
    PyObject *children;   /* list of child nodes */
    PyObject *name;
} Node;

static int
Node_traverse(PyObject *self, visitproc visit, void *arg)
{
    Node *n = (Node *)self;
    Py_VISIT(n->children);
    Py_VISIT(n->name);
    return 0;
}

static int
Node_clear(PyObject *self)
{
    Node *n = (Node *)self;
    Py_CLEAR(n->children);
    Py_CLEAR(n->name);
    return 0;
}

static void
Node_dealloc(PyObject *self)
{
    PyObject_GC_UnTrack(self);
    Node_clear(self);
    Py_TYPE(self)->tp_free(self);
}

static PyObject *
Node_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
{
    Node *self = (Node *)PyObject_GC_New(Node, type);
    if (self == NULL)
        return NULL;
    self->children = PyList_New(0);
    if (self->children == NULL) {
        Py_DECREF(self);
        return NULL;
    }
    self->name = NULL;
    PyObject_GC_Track(self);
    return (PyObject *)self;
}

static PyTypeObject NodeType = {
    PyVarObject_HEAD_INIT(NULL, 0)
    .tp_name = "gc_demo.Node",
    .tp_basicsize = sizeof(Node),
    .tp_dealloc = Node_dealloc,
    .tp_traverse = Node_traverse,
    .tp_clear = Node_clear,
    .tp_flags = Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,
    .tp_new = Node_new,
};

static struct PyModuleDef module = {
    PyModuleDef_HEAD_INIT,
    .m_name = "gc_demo",
    .m_size = -1,
};

PyMODINIT_FUNC
PyInit_gc_demo(void)
{
    if (PyType_Ready(&NodeType) < 0)
        return NULL;
    PyObject *m = PyModule_Create(&module);
    if (m == NULL)
        return NULL;
    Py_INCREF(&NodeType);
    if (PyModule_AddObject(m, "Node", (PyObject *)&NodeType) < 0) {
        Py_DECREF(&NodeType);
        Py_DECREF(m);
        return NULL;
    }
    return m;
}

Build it with the interpreter’s own flags (frame pointers and all) so it stays consistent with the ABI:

python3-config --extension-suffix   # -> .cpython-315-x86_64-linux-gnu.so
gcc $(python3-config --cflags) -shared -fPIC gc_demo.c \
    -o gc_demo$(python3-config --extension-suffix)

Then a cycle through the C type is collected exactly like a Python one:

>>> import gc, gc_demo
>>> a = gc_demo.Node()
>>> b = gc_demo.Node()
>>> a.children.append(b)
>>> b.children.append(a)
>>> del a, b
>>> gc.collect()
4

Key invariants to remember

Py_VISIT (used in tp_traverse) must visit every owned reference, including ones that may be NULL (it handles NULL safely).
Py_CLEAR must be used instead of Py_DECREF + assignment in tp_clear and tp_dealloc, because it sets the field to NULL before dropping the reference – preventing re-entrancy if the destructor triggers Python code.
Always call PyObject_GC_UnTrack before tp_clear in tp_dealloc. Clearing a tracked object’s fields while it is still in a GC list corrupts the list.
Objects allocated with PyObject_GC_New must be freed with PyObject_GC_Del, never free or PyObject_Free.

Tracking status

Not every container is tracked. Tuples of immutable objects, for example, are tracked at creation but may be untracked during collection if all their contents are untracked. You can query the current status:

>>> import gc
>>> gc.is_tracked([])
True
>>> gc.is_tracked(())
False
>>> gc.is_tracked({})
True
>>> gc.is_tracked({"a": 1})
True

Debugging

gc.set_debug enables detailed output during collection:

import gc
gc.set_debug(gc.DEBUG_STATS | gc.DEBUG_COLLECTABLE)
gc.collect()

DEBUG_SAVEALL keeps collected objects in gc.garbage instead of freeing them, which is invaluable when tracking down a leak.

Free-threaded builds

In free-threaded CPython there are no generations and no PyGC_Head. The collector pauses all other threads, marks objects reachable from roots as alive, then scans the whole heap through mimalloc. The basic cycle algorithm is the same; only the bookkeeping differs.