#include "Python.h"

#include "pycore_brc.h" // struct _brc_thread_state

#include "pycore_ceval.h" // _Py_set_eval_breaker_bit()

#include "pycore_context.h"

#include "pycore_dict.h" // _PyInlineValuesSize()

#include "pycore_freelist.h" // _PyObject_ClearFreeLists()

#include "pycore_initconfig.h"

#include "pycore_interp.h" // PyInterpreterState.gc

#include "pycore_object.h"

#include "pycore_object_alloc.h" // _PyObject_MallocWithType()

#include "pycore_object_stack.h"

#include "pycore_pyerrors.h"

#include "pycore_pystate.h" // _PyThreadState_GET()

#include "pycore_tstate.h" // _PyThreadStateImpl

#include "pycore_weakref.h" // _PyWeakref_ClearRef()

#include "pydtrace.h"

#include "pycore_uniqueid.h" // _PyObject_MergeThreadLocalRefcounts()

#define GC_ENABLE_MARK_ALIVE 1

#define GC_MARK_ALIVE_EXTRA_ROOTS 1

#define GC_MARK_ALIVE_STACKS 1

#ifdef Py_GIL_DISABLED

typedef struct _gc_runtime_state GCState;

#ifdef Py_DEBUG

# define GC_DEBUG

#define LOCAL_ALLOC_COUNT_THRESHOLD 512

#define GENERATION_AUTO (-1)

struct worklist {

uintptr_t head;

};

struct worklist_iter {

uintptr_t *ptr; // pointer to current object

uintptr_t *next; // next value of ptr

};

struct visitor_args {

size_t offset; // offset of PyObject from start of block

};

struct collection_state {

};

#define WORKSTACK_FOR_EACH(stack, op) \

for ((op) = (PyObject *)(stack)->head; (op) != NULL; (op) = (PyObject *)(op)->ob_tid)

#define WORKSTACK_FOR_EACH_ITER(stack, iter, op) \

for (worklist_iter_init((iter), &(stack)->head), (op) = (PyObject *)(*(iter)->ptr); \

(op) != NULL; \

worklist_iter_init((iter), (iter)->next), (op) = (PyObject *)(*(iter)->ptr))

static void

worklist_push(struct worklist *worklist, PyObject *op)

{

assert(op->ob_tid == 0);

op->ob_tid = worklist->head;

worklist->head = (uintptr_t)op;

}

static PyObject *

worklist_pop(struct worklist *worklist)

{

PyObject *op = (PyObject *)worklist->head;

if (op != NULL) {

worklist->head = op->ob_tid;

_Py_atomic_store_uintptr_relaxed(&op->ob_tid, 0);

}

return op;

}

static void

worklist_iter_init(struct worklist_iter *iter, uintptr_t *next)

{

iter->ptr = next;

PyObject *op = (PyObject *)*(iter->ptr);

if (op) {

iter->next = &op->ob_tid;

}

}

static void

worklist_remove(struct worklist_iter *iter)

{

PyObject *op = (PyObject *)*(iter->ptr);

*(iter->ptr) = op->ob_tid;

op->ob_tid = 0;

iter->next = iter->ptr;

}

static inline int

gc_has_bit(PyObject *op, uint8_t bit)

{

return (op->ob_gc_bits & bit) != 0;

}

static inline void

gc_set_bit(PyObject *op, uint8_t bit)

{

op->ob_gc_bits |= bit;

}

static inline void

gc_clear_bit(PyObject *op, uint8_t bit)

{

op->ob_gc_bits &= ~bit;

}

static inline int

gc_is_frozen(PyObject *op)

{

return gc_has_bit(op, _PyGC_BITS_FROZEN);

}

static inline int

gc_is_unreachable(PyObject *op)

{

return gc_has_bit(op, _PyGC_BITS_UNREACHABLE);

}

static inline void

gc_set_unreachable(PyObject *op)

{

gc_set_bit(op, _PyGC_BITS_UNREACHABLE);

}

static inline void

gc_clear_unreachable(PyObject *op)

{

gc_clear_bit(op, _PyGC_BITS_UNREACHABLE);

}

static inline int

gc_is_alive(PyObject *op)

{

return gc_has_bit(op, _PyGC_BITS_ALIVE);

}

#ifdef GC_ENABLE_MARK_ALIVE

static inline void

gc_set_alive(PyObject *op)

{

gc_set_bit(op, _PyGC_BITS_ALIVE);

}

static inline void

gc_clear_alive(PyObject *op)

{

gc_clear_bit(op, _PyGC_BITS_ALIVE);

}

static void

gc_maybe_init_refs(PyObject *op)

{

if (!gc_is_unreachable(op)) {

assert(!gc_is_alive(op));

gc_set_unreachable(op);

op->ob_tid = 0;

}

}

static inline Py_ssize_t

gc_get_refs(PyObject *op)

{

return (Py_ssize_t)op->ob_tid;

}

static inline void

gc_add_refs(PyObject *op, Py_ssize_t refs)

{

assert(_PyObject_GC_IS_TRACKED(op));

op->ob_tid += refs;

}

static inline void

gc_decref(PyObject *op)

{

op->ob_tid -= 1;

}

static Py_ssize_t

merge_refcount(PyObject *op, Py_ssize_t extra)

{

assert(_PyInterpreterState_GET()->stoptheworld.world_stopped);

Py_ssize_t refcount = Py_REFCNT(op);

refcount += extra;

#ifdef Py_REF_DEBUG

_Py_AddRefTotal(_PyThreadState_GET(), extra);

// No atomics necessary; all other threads in this interpreter are paused.

op->ob_tid = 0;

op->ob_ref_local = 0;

op->ob_ref_shared = _Py_REF_SHARED(refcount, _Py_REF_MERGED);

return refcount;

}

static void

frame_disable_deferred_refcounting(_PyInterpreterFrame *frame)

{

// Convert locals, variables, and the executable object to strong

// references from (possibly) deferred references.

assert(frame->stackpointer != NULL);

assert(frame->owner == FRAME_OWNED_BY_FRAME_OBJECT ||

frame->owner == FRAME_OWNED_BY_GENERATOR);

frame->f_executable = PyStackRef_AsStrongReference(frame->f_executable);

if (frame->owner == FRAME_OWNED_BY_GENERATOR) {

PyGenObject *gen = _PyGen_GetGeneratorFromFrame(frame);

if (gen->gi_frame_state == FRAME_CLEARED) {

// gh-124068: if the generator is cleared, then most fields other

// than f_executable are not valid.

return;

}

}

frame->f_funcobj = PyStackRef_AsStrongReference(frame->f_funcobj);

for (_PyStackRef *ref = frame->localsplus; ref < frame->stackpointer; ref++) {

if (!PyStackRef_IsNull(*ref) && PyStackRef_IsDeferred(*ref)) {

*ref = PyStackRef_AsStrongReference(*ref);

}

}

}

static void

disable_deferred_refcounting(PyObject *op)

{

if (_PyObject_HasDeferredRefcount(op)) {

op->ob_gc_bits &= ~_PyGC_BITS_DEFERRED;

op->ob_ref_shared -= _Py_REF_SHARED(_Py_REF_DEFERRED, 0);

merge_refcount(op, 0);

// Heap types and code objects also use per-thread refcounting, which

// should also be disabled when we turn off deferred refcounting.

_PyObject_DisablePerThreadRefcounting(op);

}

// Generators and frame objects may contain deferred references to other

// objects. If the pointed-to objects are part of cyclic trash, we may

// have disabled deferred refcounting on them and need to ensure that we

// use strong references, in case the generator or frame object is

// resurrected by a finalizer.

if (PyGen_CheckExact(op) || PyCoro_CheckExact(op) || PyAsyncGen_CheckExact(op)) {

frame_disable_deferred_refcounting(&((PyGenObject *)op)->gi_iframe);

}

else if (PyFrame_Check(op)) {

frame_disable_deferred_refcounting(((PyFrameObject *)op)->f_frame);

}

}

static void

gc_restore_tid(PyObject *op)

{

assert(_PyInterpreterState_GET()->stoptheworld.world_stopped);

mi_segment_t *segment = _mi_ptr_segment(op);

if (_Py_REF_IS_MERGED(op->ob_ref_shared)) {

op->ob_tid = 0;

}

else {

// NOTE: may change ob_tid if the object was re-initialized by

// a different thread or its segment was abandoned and reclaimed.

// The segment thread id might be zero, in which case we should

// ensure the refcounts are now merged.

op->ob_tid = segment->thread_id;

if (op->ob_tid == 0) {

merge_refcount(op, 0);

}

}

}

static void

gc_restore_refs(PyObject *op)

{

if (gc_is_unreachable(op)) {

assert(!gc_is_alive(op));

gc_restore_tid(op);

gc_clear_unreachable(op);

}

else {

gc_clear_alive(op);

}

}

static PyObject *

op_from_block(void *block, void *arg, bool include_frozen)

{

struct visitor_args *a = arg;

if (block == NULL) {

return NULL;

}

PyObject *op = (PyObject *)((char*)block + a->offset);

assert(PyObject_IS_GC(op));

if (!_PyObject_GC_IS_TRACKED(op)) {

return NULL;

}

if (!include_frozen && gc_is_frozen(op)) {

return NULL;

}

return op;

}

static int

gc_visit_heaps_lock_held(PyInterpreterState *interp, mi_block_visit_fun *visitor,

struct visitor_args *arg)

{

// Offset of PyObject header from start of memory block.

Py_ssize_t offset_base = 0;

if (_PyMem_DebugEnabled()) {

// The debug allocator adds two words at the beginning of each block.

offset_base += 2 * sizeof(size_t);

}

// Objects with Py_TPFLAGS_PREHEADER have two extra fields

Py_ssize_t offset_pre = offset_base + 2 * sizeof(PyObject*);

// visit each thread's heaps for GC objects

_Py_FOR_EACH_TSTATE_UNLOCKED(interp, p) {

struct _mimalloc_thread_state *m = &((_PyThreadStateImpl *)p)->mimalloc;

if (!_Py_atomic_load_int(&m->initialized)) {

// The thread may not have called tstate_mimalloc_bind() yet.

continue;

}

arg->offset = offset_base;

if (!mi_heap_visit_blocks(&m->heaps[_Py_MIMALLOC_HEAP_GC], true,

visitor, arg)) {

return -1;

}

arg->offset = offset_pre;

if (!mi_heap_visit_blocks(&m->heaps[_Py_MIMALLOC_HEAP_GC_PRE], true,

visitor, arg)) {

return -1;

}

}

// visit blocks in the per-interpreter abandoned pool (from dead threads)

mi_abandoned_pool_t *pool = &interp->mimalloc.abandoned_pool;

arg->offset = offset_base;

if (!_mi_abandoned_pool_visit_blocks(pool, _Py_MIMALLOC_HEAP_GC, true,

visitor, arg)) {

return -1;

}

arg->offset = offset_pre;

if (!_mi_abandoned_pool_visit_blocks(pool, _Py_MIMALLOC_HEAP_GC_PRE, true,

visitor, arg)) {

return -1;

}

return 0;

}

static int

gc_visit_heaps(PyInterpreterState *interp, mi_block_visit_fun *visitor,

struct visitor_args *arg)

{

// Other threads in the interpreter must be paused so that we can safely

// traverse their heaps.

assert(interp->stoptheworld.world_stopped);

int err;

HEAD_LOCK(&_PyRuntime);

err = gc_visit_heaps_lock_held(interp, visitor, arg);

HEAD_UNLOCK(&_PyRuntime);

return err;

}

static inline void

gc_visit_stackref(_PyStackRef stackref)

{

// Note: we MUST check that it is deferred before checking the rest.

// Otherwise we might read into invalid memory due to non-deferred references

// being dead already.

if (PyStackRef_IsDeferred(stackref) && !PyStackRef_IsNull(stackref)) {

PyObject *obj = PyStackRef_AsPyObjectBorrow(stackref);

if (_PyObject_GC_IS_TRACKED(obj) && !gc_is_frozen(obj)) {

gc_add_refs(obj, 1);

}

}

}

static void

gc_visit_thread_stacks(PyInterpreterState *interp)

{

_Py_FOR_EACH_TSTATE_BEGIN(interp, p) {

for (_PyInterpreterFrame *f = p->current_frame; f != NULL; f = f->previous) {

PyObject *executable = PyStackRef_AsPyObjectBorrow(f->f_executable);

if (executable == NULL || !PyCode_Check(executable)) {

continue;

}

PyCodeObject *co = (PyCodeObject *)executable;

int max_stack = co->co_nlocalsplus + co->co_stacksize;

gc_visit_stackref(f->f_executable);

for (int i = 0; i < max_stack; i++) {

gc_visit_stackref(f->localsplus[i]);

}

}

}

_Py_FOR_EACH_TSTATE_END(interp);

}

static bool

gc_maybe_untrack(PyObject *op)

{

// Currently we only check for tuples containing only non-GC objects. In

// theory we could check other immutable objects that contain references

// to non-GC objects.

if (PyTuple_CheckExact(op)) {

_PyTuple_MaybeUntrack(op);

if (!_PyObject_GC_IS_TRACKED(op)) {

return true;

}

}

return false;

}

#ifdef GC_ENABLE_MARK_ALIVE

static int

mark_alive_stack_push(PyObject *op, _PyObjectStack *stack)

{

if (op == NULL) {

return 0;

}

if (!_PyObject_GC_IS_TRACKED(op)) {

return 0;

}

if (gc_is_alive(op)) {

return 0; // already visited this object

}

if (gc_maybe_untrack(op)) {

return 0; // was untracked, don't visit it

}

// Need to call tp_traverse on this object. Add to stack and mark it

// alive so we don't traverse it a second time.

gc_set_alive(op);

if (_PyObjectStack_Push(stack, op) < 0) {

return -1;

}

return 0;

}

static bool

gc_clear_alive_bits(const mi_heap_t *heap, const mi_heap_area_t *area,

void *block, size_t block_size, void *args)

{

PyObject *op = op_from_block(block, args, false);

if (op == NULL) {

return true;

}

if (gc_is_alive(op)) {

gc_clear_alive(op);

}

return true;

}

static void

gc_abort_mark_alive(PyInterpreterState *interp,

struct collection_state *state,

_PyObjectStack *stack)

{

// We failed to allocate memory for "stack" while doing the "mark

// alive" phase. In that case, free the object stack and make sure

// that no objects have the alive bit set.

_PyObjectStack_Clear(stack);

gc_visit_heaps(interp, &gc_clear_alive_bits, &state->base);

}

#ifdef GC_MARK_ALIVE_STACKS

static int

gc_visit_stackref_mark_alive(_PyObjectStack *stack, _PyStackRef stackref)

{

// Note: we MUST check that it is deferred before checking the rest.

// Otherwise we might read into invalid memory due to non-deferred references

// being dead already.

if (PyStackRef_IsDeferred(stackref) && !PyStackRef_IsNull(stackref)) {

PyObject *op = PyStackRef_AsPyObjectBorrow(stackref);

if (mark_alive_stack_push(op, stack) < 0) {

return -1;

}

}

return 0;

}

static int

gc_visit_thread_stacks_mark_alive(PyInterpreterState *interp, _PyObjectStack *stack)

{

_Py_FOR_EACH_TSTATE_BEGIN(interp, p) {

for (_PyInterpreterFrame *f = p->current_frame; f != NULL; f = f->previous) {

PyObject *executable = PyStackRef_AsPyObjectBorrow(f->f_executable);

if (executable == NULL || !PyCode_Check(executable)) {

continue;

}

PyCodeObject *co = (PyCodeObject *)executable;

int max_stack = co->co_nlocalsplus + co->co_stacksize;

if (gc_visit_stackref_mark_alive(stack, f->f_executable) < 0) {

return -1;

}

for (int i = 0; i < max_stack; i++) {

if (gc_visit_stackref_mark_alive(stack, f->localsplus[i]) < 0) {

return -1;

}

}

}

}

_Py_FOR_EACH_TSTATE_END(interp);

return 0;

}

#endif // GC_MARK_ALIVE_STACKS

#endif // GC_ENABLE_MARK_ALIVE

static void

queue_untracked_obj_decref(PyObject *op, struct collection_state *state)

{

if (!_PyObject_GC_IS_TRACKED(op)) {

// GC objects with zero refcount are handled subsequently by the

// GC as if they were cyclic trash, but we have to handle dead

// non-GC objects here. Add one to the refcount so that we can

// decref and deallocate the object once we start the world again.

op->ob_ref_shared += (1 << _Py_REF_SHARED_SHIFT);

#ifdef Py_REF_DEBUG

_Py_IncRefTotal(_PyThreadState_GET());

worklist_push(&state->objs_to_decref, op);

}

}

static void

merge_queued_objects(_PyThreadStateImpl *tstate, struct collection_state *state)

{

struct _brc_thread_state *brc = &tstate->brc;

_PyObjectStack_Merge(&brc->local_objects_to_merge, &brc->objects_to_merge);

PyObject *op;

while ((op = _PyObjectStack_Pop(&brc->local_objects_to_merge)) != NULL) {

// Subtract one when merging because the queue had a reference.

Py_ssize_t refcount = merge_refcount(op, -1);

if (refcount == 0) {

queue_untracked_obj_decref(op, state);

}

}

}

static void

queue_freed_object(PyObject *obj, void *arg)

{

queue_untracked_obj_decref(obj, arg);

}

static void

process_delayed_frees(PyInterpreterState *interp, struct collection_state *state)

{

// While we are in a "stop the world" pause, we can observe the latest

// write sequence by advancing the write sequence immediately.

_Py_qsbr_advance(&interp->qsbr);

_PyThreadStateImpl *current_tstate = (_PyThreadStateImpl *)_PyThreadState_GET();

_Py_qsbr_quiescent_state(current_tstate->qsbr);

// Merge the queues from other threads into our own queue so that we can

// process all of the pending delayed free requests at once.

_Py_FOR_EACH_TSTATE_BEGIN(interp, p) {

_PyThreadStateImpl *other = (_PyThreadStateImpl *)p;

if (other != current_tstate) {

llist_concat(&current_tstate->mem_free_queue, &other->mem_free_queue);

}

}

_Py_FOR_EACH_TSTATE_END(interp);

_PyMem_ProcessDelayedNoDealloc((PyThreadState *)current_tstate, queue_freed_object, state);

}

static int

visit_decref(PyObject *op, void *arg)

{

if (_PyObject_GC_IS_TRACKED(op)

&& !_Py_IsImmortal(op)

&& !gc_is_frozen(op)

&& !gc_is_alive(op))

{

// If update_refs hasn't reached this object yet, mark it

// as (tentatively) unreachable and initialize ob_tid to zero.

gc_maybe_init_refs(op);

gc_decref(op);

}

return 0;

}

static bool

update_refs(const mi_heap_t *heap, const mi_heap_area_t *area,

void *block, size_t block_size, void *args)

{

PyObject *op = op_from_block(block, args, false);

if (op == NULL) {

return true;

}

if (gc_is_alive(op)) {

return true;

}

// Exclude immortal objects from garbage collection

if (_Py_IsImmortal(op)) {

op->ob_tid = 0;

_PyObject_GC_UNTRACK(op);

gc_clear_unreachable(op);

return true;

}

Py_ssize_t refcount = Py_REFCNT(op);

if (_PyObject_HasDeferredRefcount(op)) {

refcount -= _Py_REF_DEFERRED;

}

_PyObject_ASSERT(op, refcount >= 0);

if (refcount > 0 && !_PyObject_HasDeferredRefcount(op)) {

if (gc_maybe_untrack(op)) {

gc_restore_refs(op);

return true;

}

}

// We repurpose ob_tid to compute "gc_refs", the number of external

// references to the object (i.e., from outside the GC heaps). This means

// that ob_tid is no longer a valid thread id until it is restored by

// scan_heap_visitor(). Until then, we cannot use the standard reference

// counting functions or allow other threads to run Python code.

gc_maybe_init_refs(op);

// Add the actual refcount to ob_tid.

gc_add_refs(op, refcount);

// Subtract internal references from ob_tid. Objects with ob_tid > 0

// are directly reachable from outside containers, and so can't be

// collected.

Py_TYPE(op)->tp_traverse(op, visit_decref, NULL);

return true;

}

static int

visit_clear_unreachable(PyObject *op, _PyObjectStack *stack)

{

if (gc_is_unreachable(op)) {

_PyObject_ASSERT(op, _PyObject_GC_IS_TRACKED(op));

gc_clear_unreachable(op);

return _PyObjectStack_Push(stack, op);

}

return 0;

}

static int

mark_reachable(PyObject *op)

{

_PyObjectStack stack = { NULL };

do {

traverseproc traverse = Py_TYPE(op)->tp_traverse;

if (traverse(op, (visitproc)&visit_clear_unreachable, &stack) < 0) {

_PyObjectStack_Clear(&stack);

return -1;

}

op = _PyObjectStack_Pop(&stack);

} while (op != NULL);

return 0;

}

#ifdef GC_DEBUG

static bool

validate_alive_bits(const mi_heap_t *heap, const mi_heap_area_t *area,

void *block, size_t block_size, void *args)

{

PyObject *op = op_from_block(block, args, false);

if (op == NULL) {

return true;

}

_PyObject_ASSERT_WITH_MSG(op, !gc_is_alive(op),

"object should not be marked as alive yet");

return true;

}

static bool

validate_refcounts(const mi_heap_t *heap, const mi_heap_area_t *area,

void *block, size_t block_size, void *args)

{

PyObject *op = op_from_block(block, args, false);

if (op == NULL) {

return true;

}

_PyObject_ASSERT_WITH_MSG(op, !gc_is_unreachable(op),

"object should not be marked as unreachable yet");

if (_Py_REF_IS_MERGED(op->ob_ref_shared)) {

_PyObject_ASSERT_WITH_MSG(op, op->ob_tid == 0,

"merged objects should have ob_tid == 0");

}

else if (!_Py_IsImmortal(op)) {

_PyObject_ASSERT_WITH_MSG(op, op->ob_tid != 0,

"unmerged objects should have ob_tid != 0");

}

return true;

}

static bool

validate_gc_objects(const mi_heap_t *heap, const mi_heap_area_t *area,

void *block, size_t block_size, void *args)

{

PyObject *op = op_from_block(block, args, false);

if (op == NULL) {

return true;

}

if (gc_is_alive(op)) {

_PyObject_ASSERT(op, !gc_is_unreachable(op));

return true;

}

_PyObject_ASSERT(op, gc_is_unreachable(op));

_PyObject_ASSERT_WITH_MSG(op, gc_get_refs(op) >= 0,

"refcount is too small");

return true;

}

static bool

mark_heap_visitor(const mi_heap_t *heap, const mi_heap_area_t *area,

void *block, size_t block_size, void *args)

{

PyObject *op = op_from_block(block, args, false);

if (op == NULL) {

return true;

}

if (gc_is_alive(op)) {

return true;

}

_PyObject_ASSERT_WITH_MSG(op, gc_get_refs(op) >= 0,

"refcount is too small");

if (gc_is_unreachable(op) && gc_get_refs(op) != 0) {

// Object is reachable but currently marked as unreachable.

// Mark it as reachable and traverse its pointers to find

// any other object that may be directly reachable from it.

gc_clear_unreachable(op);

// Transitively mark reachable objects by clearing the unreachable flag.

if (mark_reachable(op) < 0) {

return false;

}

}

return true;

}

static bool

restore_refs(const mi_heap_t *heap, const mi_heap_area_t *area,

void *block, size_t block_size, void *args)

{

PyObject *op = op_from_block(block, args, false);

if (op == NULL) {

return true;

}

gc_restore_tid(op);

gc_clear_unreachable(op);

gc_clear_alive(op);

return true;

}

static int

has_legacy_finalizer(PyObject *op)

{

return Py_TYPE(op)->tp_del != NULL;

}

static bool

scan_heap_visitor(const mi_heap_t *heap, const mi_heap_area_t *area,

void *block, size_t block_size, void *args)

{

PyObject *op = op_from_block(block, args, false);

if (op == NULL) {

return true;

}

struct collection_state *state = (struct collection_state *)args;

if (gc_is_unreachable(op)) {

// Disable deferred refcounting for unreachable objects so that they

// are collected immediately after finalization.

disable_deferred_refcounting(op);

// Merge and add one to the refcount to prevent deallocation while we

// are holding on to it in a worklist.

merge_refcount(op, 1);

if (has_legacy_finalizer(op)) {

// would be unreachable, but has legacy finalizer

gc_clear_unreachable(op);

worklist_push(&state->legacy_finalizers, op);

}

else {

worklist_push(&state->unreachable, op);

}

return true;

}

if (state->reason == _Py_GC_REASON_SHUTDOWN) {

// Disable deferred refcounting for reachable objects as well during

// interpreter shutdown. This ensures that these objects are collected

// immediately when their last reference is removed.

disable_deferred_refcounting(op);

}

// object is reachable, restore `ob_tid`; we're done with these objects

gc_restore_tid(op);

gc_clear_alive(op);

state->long_lived_total++;

return true;

}

static int

move_legacy_finalizer_reachable(struct collection_state *state);

#ifdef GC_ENABLE_MARK_ALIVE

static int

propagate_alive_bits(_PyObjectStack *stack)

{

for (;;) {

PyObject *op = _PyObjectStack_Pop(stack);

if (op == NULL) {

break;

}

assert(_PyObject_GC_IS_TRACKED(op));

assert(gc_is_alive(op));

traverseproc traverse = Py_TYPE(op)->tp_traverse;

if (traverse(op, (visitproc)&mark_alive_stack_push, stack) < 0) {

return -1;

}

}

return 0;

}

static int

mark_alive_from_roots(PyInterpreterState *interp,

struct collection_state *state)

{

#ifdef GC_DEBUG

// Check that all objects don't have alive bit set

gc_visit_heaps(interp, &validate_alive_bits, &state->base);

_PyObjectStack stack = { NULL };

#define STACK_PUSH(op) \

if (mark_alive_stack_push(op, &stack) < 0) { \

gc_abort_mark_alive(interp, state, &stack); \

return -1; \

}

STACK_PUSH(interp->sysdict);

#ifdef GC_MARK_ALIVE_EXTRA_ROOTS

STACK_PUSH(interp->builtins);

STACK_PUSH(interp->dict);

struct types_state *types = &interp->types;

for (int i = 0; i < _Py_MAX_MANAGED_STATIC_BUILTIN_TYPES; i++) {

STACK_PUSH(types->builtins.initialized[i].tp_dict);

STACK_PUSH(types->builtins.initialized[i].tp_subclasses);

}

for (int i = 0; i < _Py_MAX_MANAGED_STATIC_EXT_TYPES; i++) {

STACK_PUSH(types->for_extensions.initialized[i].tp_dict);

STACK_PUSH(types->for_extensions.initialized[i].tp_subclasses);

}

#ifdef GC_MARK_ALIVE_STACKS

if (gc_visit_thread_stacks_mark_alive(interp, &stack) < 0) {

gc_abort_mark_alive(interp, state, &stack);

return -1;

}

#undef STACK_PUSH

// Use tp_traverse to find everything reachable from roots.

if (propagate_alive_bits(&stack) < 0) {

gc_abort_mark_alive(interp, state, &stack);

return -1;

}

return 0;

}

#endif // GC_ENABLE_MARK_ALIVE

static int

deduce_unreachable_heap(PyInterpreterState *interp,

struct collection_state *state)

{

#ifdef GC_DEBUG

// Check that all objects are marked as unreachable and that the computed

// reference count difference (stored in `ob_tid`) is non-negative.

gc_visit_heaps(interp, &validate_refcounts, &state->base);

// Identify objects that are directly reachable from outside the GC heap

// by computing the difference between the refcount and the number of

// incoming references.

gc_visit_heaps(interp, &update_refs, &state->base);

#ifdef GC_DEBUG

// Check that all objects are marked as unreachable and that the computed

// reference count difference (stored in `ob_tid`) is non-negative.

gc_visit_heaps(interp, &validate_gc_objects, &state->base);

// Visit the thread stacks to account for any deferred references.

gc_visit_thread_stacks(interp);

// Transitively mark reachable objects by clearing the

// _PyGC_BITS_UNREACHABLE flag.

if (gc_visit_heaps(interp, &mark_heap_visitor, &state->base) < 0) {

// On out-of-memory, restore the refcounts and bail out.

gc_visit_heaps(interp, &restore_refs, &state->base);

return -1;

}

// Identify remaining unreachable objects and push them onto a stack.

// Restores ob_tid for reachable objects.

gc_visit_heaps(interp, &scan_heap_visitor, &state->base);