#include "Python.h"

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

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

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

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

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

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

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

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

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

#include "pydtrace.h"

#ifndef Py_GIL_DISABLED

typedef struct _gc_runtime_state GCState;

#ifdef Py_DEBUG

# define GC_DEBUG

#define GC_NEXT _PyGCHead_NEXT

#define GC_PREV _PyGCHead_PREV

#define PREV_MASK_COLLECTING _PyGC_PREV_MASK_COLLECTING

#define NEXT_MASK_UNREACHABLE 2

#define AS_GC(op) _Py_AS_GC(op)

#define FROM_GC(gc) _Py_FROM_GC(gc)

#define GENERATION_AUTO (-1)

static inline int

gc_is_collecting(PyGC_Head *g)

{

return (g->_gc_prev & PREV_MASK_COLLECTING) != 0;

}

static inline void

gc_clear_collecting(PyGC_Head *g)

{

g->_gc_prev &= ~PREV_MASK_COLLECTING;

}

static inline Py_ssize_t

gc_get_refs(PyGC_Head *g)

{

return (Py_ssize_t)(g->_gc_prev >> _PyGC_PREV_SHIFT);

}

static inline void

gc_set_refs(PyGC_Head *g, Py_ssize_t refs)

{

g->_gc_prev = (g->_gc_prev & ~_PyGC_PREV_MASK)

| ((uintptr_t)(refs) << _PyGC_PREV_SHIFT);

}

static inline void

gc_reset_refs(PyGC_Head *g, Py_ssize_t refs)

{

g->_gc_prev = (g->_gc_prev & _PyGC_PREV_MASK_FINALIZED)

| PREV_MASK_COLLECTING

| ((uintptr_t)(refs) << _PyGC_PREV_SHIFT);

}

static inline void

gc_decref(PyGC_Head *g)

{

_PyObject_ASSERT_WITH_MSG(FROM_GC(g),

gc_get_refs(g) > 0,

"refcount is too small");

g->_gc_prev -= 1 << _PyGC_PREV_SHIFT;

}

static inline int

gc_old_space(PyGC_Head *g)

{

return g->_gc_next & _PyGC_NEXT_MASK_OLD_SPACE_1;

}

static inline int

other_space(int space)

{

assert(space == 0 || space == 1);

return space ^ _PyGC_NEXT_MASK_OLD_SPACE_1;

}

static inline void

gc_flip_old_space(PyGC_Head *g)

{

g->_gc_next ^= _PyGC_NEXT_MASK_OLD_SPACE_1;

}

static inline void

gc_set_old_space(PyGC_Head *g, int space)

{

assert(space == 0 || space == _PyGC_NEXT_MASK_OLD_SPACE_1);

g->_gc_next &= ~_PyGC_NEXT_MASK_OLD_SPACE_1;

g->_gc_next |= space;

}

static PyGC_Head *

GEN_HEAD(GCState *gcstate, int n)

{

assert((gcstate->visited_space & (~1)) == 0);

switch(n) {

case 0:

return &gcstate->young.head;

case 1:

return &gcstate->old[gcstate->visited_space].head;

case 2:

return &gcstate->old[gcstate->visited_space^1].head;

default:

Py_UNREACHABLE();

}

}

static GCState *

get_gc_state(void)

{

PyInterpreterState *interp = _PyInterpreterState_GET();

return &interp->gc;

}

_PyGC_InitState(GCState *gcstate)

{

#define INIT_HEAD(GEN) \

do { \

GEN.head._gc_next = (uintptr_t)&GEN.head; \

GEN.head._gc_prev = (uintptr_t)&GEN.head; \

} while (0)

assert(gcstate->young.count == 0);

assert(gcstate->old[0].count == 0);

assert(gcstate->old[1].count == 0);

INIT_HEAD(gcstate->young);

INIT_HEAD(gcstate->old[0]);

INIT_HEAD(gcstate->old[1]);

INIT_HEAD(gcstate->permanent_generation);

#undef INIT_HEAD

}

_PyGC_Init(PyInterpreterState *interp)

{

GCState *gcstate = &interp->gc;

gcstate->garbage = PyList_New(0);

if (gcstate->garbage == NULL) {

return _PyStatus_NO_MEMORY();

}

gcstate->callbacks = PyList_New(0);

if (gcstate->callbacks == NULL) {

return _PyStatus_NO_MEMORY();

}

gcstate->heap_size = 0;

return _PyStatus_OK();

}

static inline void

gc_list_init(PyGC_Head *list)

{

// List header must not have flags.

// We can assign pointer by simple cast.

list->_gc_prev = (uintptr_t)list;

list->_gc_next = (uintptr_t)list;

}

static inline int

gc_list_is_empty(PyGC_Head *list)

{

return (list->_gc_next == (uintptr_t)list);

}

static inline void

gc_list_append(PyGC_Head *node, PyGC_Head *list)

{

assert((list->_gc_prev & ~_PyGC_PREV_MASK) == 0);

PyGC_Head *last = (PyGC_Head *)list->_gc_prev;

// last <-> node

_PyGCHead_SET_PREV(node, last);

_PyGCHead_SET_NEXT(last, node);

// node <-> list

_PyGCHead_SET_NEXT(node, list);

list->_gc_prev = (uintptr_t)node;

}

static inline void

gc_list_remove(PyGC_Head *node)

{

PyGC_Head *prev = GC_PREV(node);

PyGC_Head *next = GC_NEXT(node);

_PyGCHead_SET_NEXT(prev, next);

_PyGCHead_SET_PREV(next, prev);

node->_gc_next = 0; /* object is not currently tracked */

}

static void

gc_list_move(PyGC_Head *node, PyGC_Head *list)

{

/* Unlink from current list. */

PyGC_Head *from_prev = GC_PREV(node);

PyGC_Head *from_next = GC_NEXT(node);

_PyGCHead_SET_NEXT(from_prev, from_next);

_PyGCHead_SET_PREV(from_next, from_prev);

/* Relink at end of new list. */

// list must not have flags. So we can skip macros.

PyGC_Head *to_prev = (PyGC_Head*)list->_gc_prev;

_PyGCHead_SET_PREV(node, to_prev);

_PyGCHead_SET_NEXT(to_prev, node);

list->_gc_prev = (uintptr_t)node;

_PyGCHead_SET_NEXT(node, list);

}

static void

gc_list_merge(PyGC_Head *from, PyGC_Head *to)

{

assert(from != to);

if (!gc_list_is_empty(from)) {

PyGC_Head *to_tail = GC_PREV(to);

PyGC_Head *from_head = GC_NEXT(from);

PyGC_Head *from_tail = GC_PREV(from);

assert(from_head != from);

assert(from_tail != from);

assert(gc_list_is_empty(to) ||

gc_old_space(to_tail) == gc_old_space(from_tail));

_PyGCHead_SET_NEXT(to_tail, from_head);

_PyGCHead_SET_PREV(from_head, to_tail);

_PyGCHead_SET_NEXT(from_tail, to);

_PyGCHead_SET_PREV(to, from_tail);

}

gc_list_init(from);

}

static Py_ssize_t

gc_list_size(PyGC_Head *list)

{

PyGC_Head *gc;

Py_ssize_t n = 0;

for (gc = GC_NEXT(list); gc != list; gc = GC_NEXT(gc)) {

n++;

}

return n;

}

static inline void

gc_list_clear_collecting(PyGC_Head *collectable)

{

PyGC_Head *gc;

for (gc = GC_NEXT(collectable); gc != collectable; gc = GC_NEXT(gc)) {

gc_clear_collecting(gc);

}

}

static int

append_objects(PyObject *py_list, PyGC_Head *gc_list)

{

PyGC_Head *gc;

for (gc = GC_NEXT(gc_list); gc != gc_list; gc = GC_NEXT(gc)) {

PyObject *op = FROM_GC(gc);

if (op != py_list) {

if (PyList_Append(py_list, op)) {

return -1; /* exception */

}

}

}

return 0;

}

enum flagstates {collecting_clear_unreachable_clear,

collecting_clear_unreachable_set,

collecting_set_unreachable_clear,

collecting_set_unreachable_set};

#ifdef GC_DEBUG

static void

validate_list(PyGC_Head *head, enum flagstates flags)

{

assert((head->_gc_prev & ~_PyGC_PREV_MASK) == 0);

assert((head->_gc_next & ~_PyGC_PREV_MASK) == 0);

uintptr_t prev_value = 0, next_value = 0;

switch (flags) {

case collecting_clear_unreachable_clear:

break;

case collecting_set_unreachable_clear:

prev_value = PREV_MASK_COLLECTING;

break;

case collecting_clear_unreachable_set:

next_value = NEXT_MASK_UNREACHABLE;

break;

case collecting_set_unreachable_set:

prev_value = PREV_MASK_COLLECTING;

next_value = NEXT_MASK_UNREACHABLE;

break;

default:

assert(! "bad internal flags argument");

}

PyGC_Head *prev = head;

PyGC_Head *gc = GC_NEXT(head);

while (gc != head) {

PyGC_Head *trueprev = GC_PREV(gc);

PyGC_Head *truenext = GC_NEXT(gc);

assert(truenext != NULL);

assert(trueprev == prev);

assert((gc->_gc_prev & PREV_MASK_COLLECTING) == prev_value);

assert((gc->_gc_next & NEXT_MASK_UNREACHABLE) == next_value);

prev = gc;

gc = truenext;

}

assert(prev == GC_PREV(head));

}

#define validate_list(x, y) do{}while(0)

#ifdef GC_EXTRA_DEBUG

static void

gc_list_validate_space(PyGC_Head *head, int space) {

PyGC_Head *gc = GC_NEXT(head);

while (gc != head) {

assert(gc_old_space(gc) == space);

gc = GC_NEXT(gc);

}

}

static void

validate_spaces(GCState *gcstate)

{

int visited = gcstate->visited_space;

int not_visited = other_space(visited);

gc_list_validate_space(&gcstate->young.head, not_visited);

for (int space = 0; space < 2; space++) {

gc_list_validate_space(&gcstate->old[space].head, space);

}

gc_list_validate_space(&gcstate->permanent_generation.head, visited);

}

static void

validate_consistent_old_space(PyGC_Head *head)

{

PyGC_Head *gc = GC_NEXT(head);

if (gc == head) {

return;

}

int old_space = gc_old_space(gc);

while (gc != head) {

PyGC_Head *truenext = GC_NEXT(gc);

assert(truenext != NULL);

assert(gc_old_space(gc) == old_space);

gc = truenext;

}

}

#define validate_spaces(g) do{}while(0)

#define validate_consistent_old_space(l) do{}while(0)

#define gc_list_validate_space(l, s) do{}while(0)

static Py_ssize_t

update_refs(PyGC_Head *containers)

{

PyGC_Head *next;

PyGC_Head *gc = GC_NEXT(containers);

Py_ssize_t candidates = 0;

while (gc != containers) {

next = GC_NEXT(gc);

PyObject *op = FROM_GC(gc);

if (_Py_IsImmortal(op)) {

assert(!_Py_IsStaticImmortal(op));

_PyObject_GC_UNTRACK(op);

gc = next;

continue;

}

gc_reset_refs(gc, Py_REFCNT(op));

/* Python's cyclic gc should never see an incoming refcount

_PyObject_ASSERT(op, gc_get_refs(gc) != 0);

gc = next;

candidates++;

}

return candidates;

}

struct visit_decref_context {

PyObject *parent;

struct gc_generation_stats *stats;

};

static int

visit_decref(PyObject *op, void *arg)

{

OBJECT_STAT_INC(object_visits);

struct visit_decref_context *ctx = (struct visit_decref_context *)arg;

ctx->stats->object_visits += 1;

_PyObject_ASSERT(ctx->parent, !_PyObject_IsFreed(op));

if (_PyObject_IS_GC(op)) {

PyGC_Head *gc = AS_GC(op);

/* We're only interested in gc_refs for objects in the

if (gc_is_collecting(gc)) {

gc_decref(gc);

}

}

return 0;

}

_PyGC_VisitStackRef(_PyStackRef *ref, visitproc visit, void *arg)

{

// This is a bit tricky! We want to ignore stackrefs with embedded

// refcounts when computing the incoming references, but otherwise treat

// them like normal.

assert(!PyStackRef_IsTaggedInt(*ref));

if (!PyStackRef_RefcountOnObject(*ref) && (visit == visit_decref)) {

return 0;

}

Py_VISIT(PyStackRef_AsPyObjectBorrow(*ref));

return 0;

}

_PyGC_VisitFrameStack(_PyInterpreterFrame *frame, visitproc visit, void *arg)

{

_PyStackRef *ref = _PyFrame_GetLocalsArray(frame);

/* locals and stack */

for (; ref < frame->stackpointer; ref++) {

if (!PyStackRef_IsTaggedInt(*ref)) {

_Py_VISIT_STACKREF(*ref);

}

}

return 0;

}

static void

subtract_refs(PyGC_Head *containers, struct gc_generation_stats *stats)

{

traverseproc traverse;

PyGC_Head *gc = GC_NEXT(containers);

for (; gc != containers; gc = GC_NEXT(gc)) {

PyObject *op = FROM_GC(gc);

traverse = Py_TYPE(op)->tp_traverse;

struct visit_decref_context ctx = {

.parent = op,

.stats = stats

};

(void) traverse(op,

visit_decref,

&ctx);

}

}

struct visit_reachable_context {

PyGC_Head *head;

struct gc_generation_stats *stats;

};

static int

visit_reachable(PyObject *op, void *arg)

{

struct visit_reachable_context *ctx = (struct visit_reachable_context *)arg;

ctx->stats->object_visits += 1;

PyGC_Head *reachable = ctx->head;

OBJECT_STAT_INC(object_visits);

if (!_PyObject_IS_GC(op)) {

return 0;

}

PyGC_Head *gc = AS_GC(op);

const Py_ssize_t gc_refs = gc_get_refs(gc);

// Ignore objects in other generation.

// This also skips objects "to the left" of the current position in

// move_unreachable's scan of the 'young' list - they've already been

// traversed, and no longer have the PREV_MASK_COLLECTING flag.

if (! gc_is_collecting(gc)) {

return 0;

}

// It would be a logic error elsewhere if the collecting flag were set on

// an untracked object.

_PyObject_ASSERT(op, gc->_gc_next != 0);

if (gc->_gc_next & NEXT_MASK_UNREACHABLE) {

/* This had gc_refs = 0 when move_unreachable got

// Manually unlink gc from unreachable list because the list functions

// don't work right in the presence of NEXT_MASK_UNREACHABLE flags.

PyGC_Head *prev = GC_PREV(gc);

PyGC_Head *next = GC_NEXT(gc);

_PyObject_ASSERT(FROM_GC(prev),

prev->_gc_next & NEXT_MASK_UNREACHABLE);

_PyObject_ASSERT(FROM_GC(next),

next->_gc_next & NEXT_MASK_UNREACHABLE);

prev->_gc_next = gc->_gc_next; // copy flag bits

gc->_gc_next &= ~NEXT_MASK_UNREACHABLE;

_PyGCHead_SET_PREV(next, prev);

gc_list_append(gc, reachable);

gc_set_refs(gc, 1);

}

else if (gc_refs == 0) {

/* This is in move_unreachable's 'young' list, but

gc_set_refs(gc, 1);

}

/* Else there's nothing to do.

else {

_PyObject_ASSERT_WITH_MSG(op, gc_refs > 0, "refcount is too small");

}

return 0;

}

static void

move_unreachable(PyGC_Head *young, PyGC_Head *unreachable, struct gc_generation_stats *stats)

{

// previous elem in the young list, used for restore gc_prev.

PyGC_Head *prev = young;

PyGC_Head *gc = GC_NEXT(young);

/* Invariants: all objects "to the left" of us in young are reachable

struct visit_reachable_context ctx = {

.head = young,

.stats = stats

};

validate_consistent_old_space(young);

/* Record which old space we are in, and set NEXT_MASK_UNREACHABLE bit for convenience */

uintptr_t flags = NEXT_MASK_UNREACHABLE | (gc->_gc_next & _PyGC_NEXT_MASK_OLD_SPACE_1);

while (gc != young) {

if (gc_get_refs(gc)) {

/* gc is definitely reachable from outside the

PyObject *op = FROM_GC(gc);

traverseproc traverse = Py_TYPE(op)->tp_traverse;

_PyObject_ASSERT_WITH_MSG(op, gc_get_refs(gc) > 0,

"refcount is too small");

// NOTE: visit_reachable may change gc->_gc_next when

// young->_gc_prev == gc. Don't do gc = GC_NEXT(gc) before!

(void) traverse(op,

visit_reachable,

&ctx);

// relink gc_prev to prev element.

_PyGCHead_SET_PREV(gc, prev);

// gc is not COLLECTING state after here.

gc_clear_collecting(gc);

prev = gc;

}

else {

/* This *may* be unreachable. To make progress,

// Move gc to unreachable.

// No need to gc->next->prev = prev because it is single linked.

prev->_gc_next = gc->_gc_next;

// We can't use gc_list_append() here because we use

// NEXT_MASK_UNREACHABLE here.

PyGC_Head *last = GC_PREV(unreachable);

// NOTE: Since all objects in unreachable set has

// NEXT_MASK_UNREACHABLE flag, we set it unconditionally.

// But this may pollute the unreachable list head's 'next' pointer

// too. That's semantically senseless but expedient here - the

// damage is repaired when this function ends.

last->_gc_next = flags | (uintptr_t)gc;

_PyGCHead_SET_PREV(gc, last);

gc->_gc_next = flags | (uintptr_t)unreachable;

unreachable->_gc_prev = (uintptr_t)gc;

}

gc = _PyGCHead_NEXT(prev);

}

// young->_gc_prev must be last element remained in the list.

young->_gc_prev = (uintptr_t)prev;

young->_gc_next &= _PyGC_PREV_MASK;

// don't let the pollution of the list head's next pointer leak

unreachable->_gc_next &= _PyGC_PREV_MASK;

}

static void

untrack_tuples(PyGC_Head *head)

{

PyGC_Head *gc = GC_NEXT(head);

while (gc != head) {

PyObject *op = FROM_GC(gc);

PyGC_Head *next = GC_NEXT(gc);

if (PyTuple_CheckExact(op)) {

_PyTuple_MaybeUntrack(op);

}

gc = next;

}

}

static int

has_legacy_finalizer(PyObject *op)

{

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

}

static void

move_legacy_finalizers(PyGC_Head *unreachable, PyGC_Head *finalizers)

{

PyGC_Head *gc, *next;

_PyObject_ASSERT(

FROM_GC(unreachable),

(unreachable->_gc_next & NEXT_MASK_UNREACHABLE) == 0);

/* March over unreachable. Move objects with finalizers into

for (gc = GC_NEXT(unreachable); gc != unreachable; gc = next) {

PyObject *op = FROM_GC(gc);

_PyObject_ASSERT(op, gc->_gc_next & NEXT_MASK_UNREACHABLE);

next = GC_NEXT(gc);

gc->_gc_next &= ~NEXT_MASK_UNREACHABLE;

if (has_legacy_finalizer(op)) {

gc_clear_collecting(gc);

gc_list_move(gc, finalizers);

}

}

}

static inline void

clear_unreachable_mask(PyGC_Head *unreachable)

{

/* Check that the list head does not have the unreachable bit set */

_PyObject_ASSERT(

FROM_GC(unreachable),

((uintptr_t)unreachable & NEXT_MASK_UNREACHABLE) == 0);

_PyObject_ASSERT(

FROM_GC(unreachable),

(unreachable->_gc_next & NEXT_MASK_UNREACHABLE) == 0);

PyGC_Head *gc, *next;

for (gc = GC_NEXT(unreachable); gc != unreachable; gc = next) {

_PyObject_ASSERT((PyObject*)FROM_GC(gc), gc->_gc_next & NEXT_MASK_UNREACHABLE);

next = GC_NEXT(gc);

gc->_gc_next &= ~NEXT_MASK_UNREACHABLE;

}

validate_list(unreachable, collecting_set_unreachable_clear);

}

static int

visit_move(PyObject *op, void *arg)

{

struct visit_reachable_context *ctx = (struct visit_reachable_context *)arg;

PyGC_Head *tolist = ctx->head;

ctx->stats->object_visits += 1;

OBJECT_STAT_INC(object_visits);

if (_PyObject_IS_GC(op)) {

PyGC_Head *gc = AS_GC(op);

if (gc_is_collecting(gc)) {

gc_list_move(gc, tolist);

gc_clear_collecting(gc);

}

}

return 0;

}

static void

move_legacy_finalizer_reachable(PyGC_Head *finalizers, struct gc_generation_stats *stats)

{

struct visit_reachable_context ctx = {

.head = finalizers,

.stats = stats

};

traverseproc traverse;

PyGC_Head *gc = GC_NEXT(finalizers);

for (; gc != finalizers; gc = GC_NEXT(gc)) {

/* Note that the finalizers list may grow during this. */

traverse = Py_TYPE(FROM_GC(gc))->tp_traverse;

(void) traverse(FROM_GC(gc),

visit_move,

&ctx);

}

}

static int

handle_weakref_callbacks(PyGC_Head *unreachable, PyGC_Head *old)

{

PyGC_Head *gc;

PyGC_Head wrcb_to_call; /* weakrefs with callbacks to call */

PyGC_Head *next;

int num_freed = 0;

gc_list_init(&wrcb_to_call);

/* Find all weakrefs with callbacks and move into `wrcb_to_call` if the

for (gc = GC_NEXT(unreachable); gc != unreachable; gc = next) {

PyWeakReference **wrlist;

PyObject *op = FROM_GC(gc);

next = GC_NEXT(gc);

if (! _PyType_SUPPORTS_WEAKREFS(Py_TYPE(op))) {

continue;

}

/* It supports weakrefs. Does it have any?

wrlist = _PyObject_GET_WEAKREFS_LISTPTR_FROM_OFFSET(op);

/* `op` may have some weakrefs. March over the list and move the

PyWeakReference *next_wr;

for (PyWeakReference *wr = *wrlist; wr != NULL; wr = next_wr) {

// Get the next list element to get iterator progress if we omit

// clearing of the weakref (because _PyWeakref_ClearRef changes

// next pointer in the wrlist).

next_wr = wr->wr_next;

if (wr->wr_callback == NULL) {

/* no callback */

continue;

}

// Clear the weakref. See the comments above this function for

// reasons why we need to clear weakrefs that have callbacks.

// Note that _PyWeakref_ClearRef clears the weakref but leaves the

// callback pointer intact. Obscure: it also changes *wrlist.

_PyObject_ASSERT((PyObject *)wr, wr->wr_object == op);

_PyWeakref_ClearRef(wr);

_PyObject_ASSERT((PyObject *)wr, wr->wr_object == Py_None);

/* Headache time. `op` is going away, and is weakly referenced by