// Cyclic garbage collector implementation for free-threaded build.

#include "Python.h"

#include "pycore_brc.h" // struct _brc_thread_state

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

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

#include "pycore_frame.h" // FRAME_CLEARED

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

#include "pycore_genobject.h" // _PyGen_GetGeneratorFromFrame()

#include "pycore_initconfig.h" // _PyStatus_NO_MEMORY()

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

#include "pycore_interpframe.h" // _PyFrame_GetLocalsArray()

#include "pycore_list.h" // _PyList_GetItemRef()

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

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

#include "pycore_tstate.h" // _PyThreadStateImpl

#include "pycore_tuple.h" // _PyTuple_MaybeUntrack()

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

#include "pydtrace.h"

// enable the "mark alive" pass of GC

#define GC_ENABLE_MARK_ALIVE 1

// if true, enable the use of "prefetch" CPU instructions

#define GC_ENABLE_PREFETCH_INSTRUCTIONS 1

// include additional roots in "mark alive" pass

#define GC_MARK_ALIVE_EXTRA_ROOTS 1

// include Python stacks as set of known roots

#define GC_MARK_ALIVE_STACKS 1

#ifdef Py_GIL_DISABLED

typedef struct _gc_runtime_state GCState;

#ifdef Py_DEBUG

# define GC_DEBUG

#endif

// Each thread buffers the count of allocated objects in a thread-local

// variable up to +/- this amount to reduce the overhead of updating

// the global count.

#define LOCAL_ALLOC_COUNT_THRESHOLD 512

// Automatically choose the generation that needs collecting.

#define GENERATION_AUTO (-1)

// A linked list of objects using the `ob_tid` field as the next pointer.

// The linked list pointers are distinct from any real thread ids, because the

// thread ids returned by _Py_ThreadId() are also pointers to distinct objects.

// No thread will confuse its own id with a linked list pointer.

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

};

// Per-collection state

struct collection_state {

struct visitor_args base;

PyInterpreterState *interp;

GCState *gcstate;

_PyGC_Reason reason;

// GH-129236: If we see an active frame without a valid stack pointer,

// we can't collect objects with deferred references because we may not

// see all references.

int skip_deferred_objects;

Py_ssize_t collected;

Py_ssize_t uncollectable;

Py_ssize_t candidates;

Py_ssize_t long_lived_total;

struct worklist unreachable;

struct worklist legacy_finalizers;

struct worklist wrcb_to_call;

struct worklist objs_to_decref;

};

// iterate over a worklist

#define WORKSTACK_FOR_EACH(stack, op) \

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

// iterate over a worklist with support for removing the current object

#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);

}

#endif

static inline void

gc_clear_alive(PyObject *op)

{

gc_clear_bit(op, _PyGC_BITS_ALIVE);

}

// Initialize the `ob_tid` field to zero if the object is not already

// initialized as unreachable.

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);

#endif

// 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_IsNullOrInt(*ref) && !PyStackRef_RefcountOnObject(*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);

}

}

// Given a mimalloc memory block return the PyObject stored in it or NULL if

// the block is not allocated or the object is not tracked or is immortal.

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;

}

// As above but returns untracked and frozen objects as well.

static PyObject *

op_from_block_all_gc(void *block, void *arg)

{

struct visitor_args *a = arg;

if (block == NULL) {

return NULL;

}

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

assert(PyObject_IS_GC(op));

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;

}

// Visits all GC objects in the interpreter's heaps.

// NOTE: It is not safe to allocate or free any mimalloc managed memory while

// this function is running.

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)

{

if (!PyStackRef_IsNullOrInt(stackref) && !PyStackRef_RefcountOnObject(stackref)) {

PyObject *obj = PyStackRef_AsPyObjectBorrow(stackref);

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

gc_add_refs(obj, 1);

}

}

}

// Add 1 to the gc_refs for every deferred reference on each thread's stack.

static void

gc_visit_thread_stacks(PyInterpreterState *interp, struct collection_state *state)

{

_Py_FOR_EACH_TSTATE_BEGIN(interp, p) {

_PyCStackRef *c_ref = ((_PyThreadStateImpl *)p)->c_stack_refs;

while (c_ref != NULL) {

gc_visit_stackref(c_ref->ref);

c_ref = c_ref->next;

}

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

if (f->owner >= FRAME_OWNED_BY_INTERPRETER) {

continue;

}

_PyStackRef *top = f->stackpointer;

if (top == NULL) {

// GH-129236: The stackpointer may be NULL in cases where

// the GC is run during a PyStackRef_CLOSE() call. Skip this

// frame and don't collect objects with deferred references.

state->skip_deferred_objects = 1;

continue;

}

gc_visit_stackref(f->f_executable);

while (top != f->localsplus) {

--top;

gc_visit_stackref(*top);

}

}

}

_Py_FOR_EACH_TSTATE_END(interp);

}

// Untrack objects that can never create reference cycles.

// Return true if the object was untracked.

static bool

gc_maybe_untrack(PyObject *op)

{

if (_PyObject_HasDeferredRefcount(op)) {

// deferred refcounting only works if the object is tracked

return false;

}

// 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

// prefetch buffer and stack //////////////////////////////////

// The buffer is a circular FIFO queue of PyObject pointers. We take

// care to not dereference these pointers until they are taken out of

// the buffer. A prefetch CPU instruction is issued when a pointer is

// put into the buffer. If all is working as expected, there will be

// enough time between the enqueue and dequeue so that the needed memory

// for the object, most importantly ob_gc_bits and ob_type words, will

// already be in the CPU cache.

#define BUFFER_SIZE 256

#define BUFFER_HI 16

#define BUFFER_LO 8

#define BUFFER_MASK (BUFFER_SIZE - 1)

// the buffer size must be an exact power of two

static_assert(BUFFER_SIZE > 0 && !(BUFFER_SIZE & BUFFER_MASK),

"Invalid BUFFER_SIZE, must be power of 2");

// the code below assumes these relationships are true

static_assert(BUFFER_HI < BUFFER_SIZE &&

BUFFER_LO < BUFFER_HI &&

BUFFER_LO > 0,

"Invalid prefetch buffer level settings.");

// Prefetch intructions will fetch the line of data from memory that

// contains the byte specified with the source operand to a location in

// the cache hierarchy specified by a locality hint. The instruction

// is only a hint and the CPU is free to ignore it. Instructions and

// behaviour are CPU specific but the definitions of locality hints

// below are mostly consistent.

//

// * T0 (temporal data) prefetch data into all levels of the cache hierarchy.

//

// * T1 (temporal data with respect to first level cache) prefetch data into

// level 2 cache and higher.

//

// * T2 (temporal data with respect to second level cache) prefetch data into

// level 3 cache and higher, or an implementation-specific choice.

//

// * NTA (non-temporal data with respect to all cache levels) prefetch data into

// non-temporal cache structure and into a location close to the processor,

// minimizing cache pollution.

#if defined(__GNUC__) || defined(__clang__)

#define PREFETCH_T0(ptr) __builtin_prefetch(ptr, 0, 3)

#define PREFETCH_T1(ptr) __builtin_prefetch(ptr, 0, 2)

#define PREFETCH_T2(ptr) __builtin_prefetch(ptr, 0, 1)

#define PREFETCH_NTA(ptr) __builtin_prefetch(ptr, 0, 0)

#elif defined(_MSC_VER) && (defined(_M_X64) || defined(_M_I86)) && !defined(_M_ARM64EC)

#include <mmintrin.h>

#define PREFETCH_T0(ptr) _mm_prefetch((const char*)(ptr), _MM_HINT_T0)

#define PREFETCH_T1(ptr) _mm_prefetch((const char*)(ptr), _MM_HINT_T1)

#define PREFETCH_T2(ptr) _mm_prefetch((const char*)(ptr), _MM_HINT_T2)

#define PREFETCH_NTA(ptr) _mm_prefetch((const char*)(ptr), _MM_HINT_NTA)

#elif defined (__aarch64__)

#define PREFETCH_T0(ptr) \

do { __asm__ __volatile__("prfm pldl1keep, %0" ::"Q"(*(ptr))); } while (0)

#define PREFETCH_T1(ptr) \

do { __asm__ __volatile__("prfm pldl2keep, %0" ::"Q"(*(ptr))); } while (0)

#define PREFETCH_T2(ptr) \

do { __asm__ __volatile__("prfm pldl3keep, %0" ::"Q"(*(ptr))); } while (0)

#define PREFETCH_NTA(ptr) \

do { __asm__ __volatile__("prfm pldl1strm, %0" ::"Q"(*(ptr))); } while (0)

#else

#define PREFETCH_T0(ptr) do { (void)(ptr); } while (0) /* disabled */

#define PREFETCH_T1(ptr) do { (void)(ptr); } while (0) /* disabled */

#define PREFETCH_T2(ptr) do { (void)(ptr); } while (0) /* disabled */

#define PREFETCH_NTA(ptr) do { (void)(ptr); } while (0) /* disabled */

#endif

#ifdef GC_ENABLE_PREFETCH_INSTRUCTIONS

#define prefetch(ptr) PREFETCH_T1(ptr)

#else

#define prefetch(ptr)

#endif

// a contigous sequence of PyObject pointers, can contain NULLs

typedef struct {

PyObject **start;

PyObject **end;

} gc_span_t;

typedef struct {

Py_ssize_t size;

Py_ssize_t capacity;

gc_span_t *stack;

} gc_span_stack_t;

typedef struct {

unsigned int in;

unsigned int out;

_PyObjectStack stack;

gc_span_stack_t spans;

PyObject *buffer[BUFFER_SIZE];

bool use_prefetch;

} gc_mark_args_t;

// Returns number of entries in buffer

static inline unsigned int

gc_mark_buffer_len(gc_mark_args_t *args)

{

return args->in - args->out;

}

// Returns number of free entry slots in buffer

#ifndef NDEBUG

static inline unsigned int

gc_mark_buffer_avail(gc_mark_args_t *args)

{

return BUFFER_SIZE - gc_mark_buffer_len(args);

}

#endif

static inline bool

gc_mark_buffer_is_empty(gc_mark_args_t *args)

{

return args->in == args->out;

}

static inline bool

gc_mark_buffer_is_full(gc_mark_args_t *args)

{

return gc_mark_buffer_len(args) == BUFFER_SIZE;

}

static inline PyObject *

gc_mark_buffer_pop(gc_mark_args_t *args)

{

assert(!gc_mark_buffer_is_empty(args));

PyObject *op = args->buffer[args->out & BUFFER_MASK];

args->out++;

return op;

}

// Called when there is space in the buffer for the object. Issue the

// prefetch instruction and add it to the end of the buffer.

static inline void

gc_mark_buffer_push(PyObject *op, gc_mark_args_t *args)

{

assert(!gc_mark_buffer_is_full(args));

prefetch(op);

args->buffer[args->in & BUFFER_MASK] = op;

args->in++;

}

// Called when we run out of space in the buffer or if the prefetching

// is disabled. The object will be pushed on the gc_mark_args.stack.

static int

gc_mark_stack_push(_PyObjectStack *ms, PyObject *op)

{

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

return -1;

}

return 0;

}

static int

gc_mark_span_push(gc_span_stack_t *ss, PyObject **start, PyObject **end)

{

if (start == end) {

return 0;

}

if (ss->size >= ss->capacity) {

if (ss->capacity == 0) {

ss->capacity = 256;

}

else {

ss->capacity *= 2;

}

gc_span_t *new_stack = (gc_span_t *)PyMem_Realloc(ss->stack, ss->capacity * sizeof(gc_span_t));

if (new_stack == NULL) {

return -1;

}

ss->stack = new_stack;

}

assert(end > start);

ss->stack[ss->size].start = start;

ss->stack[ss->size].end = end;

ss->size++;

return 0;

}

static int

gc_mark_enqueue_no_buffer(PyObject *op, gc_mark_args_t *args)

{

if (op == NULL) {

return 0;

}

if (!gc_has_bit(op, _PyGC_BITS_TRACKED)) {

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(&args->stack, op) < 0) {

return -1;

}

return 0;

}

static inline int

gc_mark_enqueue_no_buffer_visitproc(PyObject *op, void *args)

{

return gc_mark_enqueue_no_buffer(op, (gc_mark_args_t *)args);

}

static int

gc_mark_enqueue_buffer(PyObject *op, gc_mark_args_t *args)

{

assert(op != NULL);

if (!gc_mark_buffer_is_full(args)) {

gc_mark_buffer_push(op, args);

return 0;

}

else {

return gc_mark_stack_push(&args->stack, op);

}

}

static inline int

gc_mark_enqueue_buffer_visitproc(PyObject *op, void *args)

{

return gc_mark_enqueue_buffer(op, (gc_mark_args_t *)args);

}

// Called when we find an object that needs to be marked alive (either from a

// root or from calling tp_traverse).

static int

gc_mark_enqueue(PyObject *op, gc_mark_args_t *args)

{

if (args->use_prefetch) {

return gc_mark_enqueue_buffer(op, args);

}

else {

return gc_mark_enqueue_no_buffer(op, args);

}

}

// Called when we have a contigous sequence of PyObject pointers, either

// a tuple or list object. This will add the items to the buffer if there

// is space for them all otherwise push a new "span" on the span stack. Using

// spans has the advantage of not creating a deep _PyObjectStack stack when

// dealing with long sequences. Those sequences will be processed in smaller

// chunks by the gc_prime_from_spans() function.

static int

gc_mark_enqueue_span(PyObject **item, Py_ssize_t size, gc_mark_args_t *args)

{

Py_ssize_t used = gc_mark_buffer_len(args);

Py_ssize_t free = BUFFER_SIZE - used;

if (free >= size) {

for (Py_ssize_t i = 0; i < size; i++) {

PyObject *op = item[i];

if (op == NULL) {

continue;

}

gc_mark_buffer_push(op, args);

}

}

else {

assert(size > 0);

PyObject **end = &item[size];

if (gc_mark_span_push(&args->spans, item, end) < 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 int

gc_mark_traverse_list(PyObject *self, void *args)

{

PyListObject *list = (PyListObject *)self;

if (list->ob_item == NULL) {

return 0;

}

if (gc_mark_enqueue_span(list->ob_item, PyList_GET_SIZE(list), args) < 0) {

return -1;

}

return 0;

}

static int

gc_mark_traverse_tuple(PyObject *self, void *args)

{

_PyTuple_MaybeUntrack(self);

if (!gc_has_bit(self, _PyGC_BITS_TRACKED)) {

gc_clear_alive(self);

return 0;

}

PyTupleObject *tuple = _PyTuple_CAST(self);

if (gc_mark_enqueue_span(tuple->ob_item, Py_SIZE(tuple), args) < 0) {

return -1;

}

return 0;

}

static void

gc_abort_mark_alive(PyInterpreterState *interp,

struct collection_state *state,

gc_mark_args_t *args)

{

// We failed to allocate memory while doing the "mark alive" phase.

// In that case, free the memory used for marking state and make

// sure that no objects have the alive bit set.

_PyObjectStack_Clear(&args->stack);

if (args->spans.stack != NULL) {

PyMem_Free(args->spans.stack);

}

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

}

#ifdef GC_MARK_ALIVE_STACKS

static int

gc_visit_stackref_mark_alive(gc_mark_args_t *args, _PyStackRef stackref)

{

if (!PyStackRef_IsNullOrInt(stackref)) {

PyObject *op = PyStackRef_AsPyObjectBorrow(stackref);

if (gc_mark_enqueue(op, args) < 0) {

return -1;

}

}

return 0;

}

static int

gc_visit_thread_stacks_mark_alive(PyInterpreterState *interp, gc_mark_args_t *args)

{

int err = 0;

_Py_FOR_EACH_TSTATE_BEGIN(interp, p) {

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

if (f->owner >= FRAME_OWNED_BY_INTERPRETER) {

continue;

}

if (f->stackpointer == NULL) {

// GH-129236: The stackpointer may be NULL in cases where

// the GC is run during a PyStackRef_CLOSE() call. Skip this

// frame for now.

continue;

}

_PyStackRef *top = f->stackpointer;

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

err = -1;

goto exit;

}

while (top != f->localsplus) {

--top;

if (gc_visit_stackref_mark_alive(args, *top) < 0) {

err = -1;

goto exit;

}

}

}

}

exit:

_Py_FOR_EACH_TSTATE_END(interp);

return err;

}

#endif // GC_MARK_ALIVE_STACKS

#endif // GC_ENABLE_MARK_ALIVE

static void

queue_untracked_obj_decref(PyObject *op, struct collection_state *state)

{

assert(Py_REFCNT(op) == 0);

// gh-142975: We have to treat frozen objects as untracked in this function

// or else they might be picked up in a future collection, which breaks the

// assumption that all incoming objects have a non-zero reference count.

if (!_PyObject_GC_IS_TRACKED(op) || gc_is_frozen(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());

#endif

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);

}

// Subtract an incoming reference from the computed "gc_refs" refcount.

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;

}

// Compute the number of external references to objects in the heap

// by subtracting internal references from the refcount. The difference is

// computed in the ob_tid field (we restore it later).

static bool

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

void *block, size_t block_size, void *args)

{

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

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

if (op == NULL) {

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;

}

// Marked objects count as candidates, immortals don't:

state->candidates++;

if (gc_is_alive(op)) {

return true;

}

Py_ssize_t refcount = Py_REFCNT(op);

if (_PyObject_HasDeferredRefcount(op)) {

refcount -= _Py_REF_DEFERRED;

}

_PyObject_ASSERT(op, refcount >= 0);