How CPython Trashcan Prevents Stack Overflows

In CPython, deleting deeply nested data structures can trigger a chain reaction of recursive deallocations that exhausts the operating system's call stack, leading to a segmentation fault. To eliminate this vulnerability, CPython implements a defensive system known as the "trashcan" mechanism. By intercepting deeply nested deallocation calls, deferring object destruction, and flattening the recursive cleanup process into an iterative loop, the trashcan guarantees that deeply nested collections can be freed safely without causing C-level stack overflows.

The Problem: Recursive Deallocation

CPython relies primarily on reference counting for memory management. When an object's reference count drops to zero, its type-specific deallocator (tp_dealloc) is executed immediately.

For container types—such as lists, tuples, or dictionaries—the tp_dealloc function must decrement the reference count of every item it holds:

1. Object \(A\) reaches a reference count of zero, triggering its tp_dealloc.
2. Object \(A\)'s deallocator calls Py_DECREF() on child object \(B\).
3. If \(B\)'s reference count drops to zero, \(B\)'s tp_dealloc is immediately invoked on the same C stack.
4. \(B\) calls Py_DECREF() on child object \(C\), and the chain continues.

Consider a singly nested list chain constructed as x = []; for _ in range(1000000): x = [x]. Deleting x requires unwinding one million nested lists. Because each tp_dealloc call allocates a new C stack frame, this pattern rapidly exceeds the execution stack limits of the host operating system, terminating the Python process abruptly with a segmentation fault.

How the Trashcan Mechanism Works

The trashcan mechanism solves this problem by enforcing a maximum recursion depth for deallocation routines at the C level. It is exposed to container implementations via the macros Py_TRASHCAN_BEGIN and Py_TRASHCAN_END.

1. Tracking Nesting Depth

The CPython interpreter state maintains a counter tracking the current nesting depth of active deallocators (trash_delete_nesting). Each time a container begins deallocating its contents within a Py_TRASHCAN_BEGIN block, CPython checks this counter against a hardcoded threshold (historically defined as PyTrash_UNWIND_LEVEL, typically set to 54).

2. Deferring Destruction

If the nesting depth is below the threshold, the object deallocates normally, incrementing the nesting depth while its children are processed.

Once the nesting depth reaches the threshold limit:

• The current object is not immediately traversed or freed.
• Instead, the object is added to a singly linked list of deferred objects (trash_delete_later) stored on the thread state.
• The object's internal pointers are temporarily reused to maintain this linked list, avoiding additional memory allocation.
• The tp_dealloc call immediately returns, unwinding the C stack frame rather than proceeding deeper into the hierarchy.

3. Iterative Processing

When the stack unwinds back to the original caller that entered the Py_TRASHCAN_BEGIN block at depth zero:

• The Py_TRASHCAN_END macro detects that the base deallocation level has been reached and that deferred objects are waiting in the trash_delete_later queue.
• The mechanism enters an iterative while loop that pops deferred objects from the queue one at a time and executes their deallocators with the nesting counter reset to 1.
• If processing those queued objects generates further deep cascades exceeding the limit, they are simply queued back into trash_delete_later.

Summary

By using a fixed recursion threshold and a deferred queue, the trashcan converts an unbounded recursive destruction tree into a bounded, iterative release loop. This ensures that object destruction in Python remains memory-efficient and protected from low-level C stack exhaustion, regardless of how deeply nested the objects are.