#include "Python.h"

#include "frameobject.h" /* for PyFrame_ClearFreeList */

#define AS_GC(o) ((PyGC_Head *)(o)-1)

#define FROM_GC(g) ((PyObject *)(((PyGC_Head *)g)+1))

struct gc_generation {

};

#define NUM_GENERATIONS 3

#define GEN_HEAD(n) (&generations[n].head)

static struct gc_generation generations[NUM_GENERATIONS] = {

/* PyGC_Head, threshold, count */

{{{GEN_HEAD(0), GEN_HEAD(0), 0}}, 700, 0},

{{{GEN_HEAD(1), GEN_HEAD(1), 0}}, 10, 0},

{{{GEN_HEAD(2), GEN_HEAD(2), 0}}, 10, 0},

};

PyGC_Head *_PyGC_generation0 = GEN_HEAD(0);

static int enabled = 1; /* automatic collection enabled? */

static int collecting = 0;

static PyObject *garbage = NULL;

static PyObject *gc_str = NULL;

static PyObject *delstr = NULL;

static Py_ssize_t long_lived_total = 0;

static Py_ssize_t long_lived_pending = 0;

#define DEBUG_STATS (1<<0) /* print collection statistics */

#define DEBUG_COLLECTABLE (1<<1) /* print collectable objects */

#define DEBUG_UNCOLLECTABLE (1<<2) /* print uncollectable objects */

#define DEBUG_INSTANCES (1<<3) /* print instances */

#define DEBUG_OBJECTS (1<<4) /* print other objects */

#define DEBUG_SAVEALL (1<<5) /* save all garbage in gc.garbage */

#define DEBUG_LEAK DEBUG_COLLECTABLE | \

static int debug;

static PyObject *tmod = NULL;

#define GC_UNTRACKED _PyGC_REFS_UNTRACKED

#define GC_REACHABLE _PyGC_REFS_REACHABLE

#define GC_TENTATIVELY_UNREACHABLE _PyGC_REFS_TENTATIVELY_UNREACHABLE

#define IS_TRACKED(o) ((AS_GC(o))->gc.gc_refs != GC_UNTRACKED)

#define IS_REACHABLE(o) ((AS_GC(o))->gc.gc_refs == GC_REACHABLE)

#define IS_TENTATIVELY_UNREACHABLE(o) ( \

(AS_GC(o))->gc.gc_refs == GC_TENTATIVELY_UNREACHABLE)

static void

gc_list_init(PyGC_Head *list)

{

list->gc.gc_prev = list;

list->gc.gc_next = list;

}

static int

gc_list_is_empty(PyGC_Head *list)

{

return (list->gc.gc_next == list);

}

#if 0

static void

gc_list_append(PyGC_Head *node, PyGC_Head *list)

{

node->gc.gc_next = list;

node->gc.gc_prev = list->gc.gc_prev;

node->gc.gc_prev->gc.gc_next = node;

list->gc.gc_prev = node;

}

static void

gc_list_remove(PyGC_Head *node)

{

node->gc.gc_prev->gc.gc_next = node->gc.gc_next;

node->gc.gc_next->gc.gc_prev = node->gc.gc_prev;

node->gc.gc_next = NULL; /* object is not currently tracked */

}

static void

gc_list_move(PyGC_Head *node, PyGC_Head *list)

{

PyGC_Head *new_prev;

PyGC_Head *current_prev = node->gc.gc_prev;

PyGC_Head *current_next = node->gc.gc_next;

/* Unlink from current list. */

current_prev->gc.gc_next = current_next;

current_next->gc.gc_prev = current_prev;

/* Relink at end of new list. */

new_prev = node->gc.gc_prev = list->gc.gc_prev;

new_prev->gc.gc_next = list->gc.gc_prev = node;

node->gc.gc_next = list;

}

static void

gc_list_merge(PyGC_Head *from, PyGC_Head *to)

{

PyGC_Head *tail;

assert(from != to);

if (!gc_list_is_empty(from)) {

tail = to->gc.gc_prev;

tail->gc.gc_next = from->gc.gc_next;

tail->gc.gc_next->gc.gc_prev = tail;

to->gc.gc_prev = from->gc.gc_prev;

to->gc.gc_prev->gc.gc_next = to;

}

gc_list_init(from);

}

static Py_ssize_t

gc_list_size(PyGC_Head *list)

{

PyGC_Head *gc;

Py_ssize_t n = 0;

for (gc = list->gc.gc_next; gc != list; gc = gc->gc.gc_next) {

n++;

}

return n;

}

static int

append_objects(PyObject *py_list, PyGC_Head *gc_list)

{

PyGC_Head *gc;

for (gc = gc_list->gc.gc_next; gc != gc_list; gc = gc->gc.gc_next) {

PyObject *op = FROM_GC(gc);

if (op != py_list) {

if (PyList_Append(py_list, op)) {

return -1; /* exception */

}

}

}

return 0;

}

static void

update_refs(PyGC_Head *containers)

{

PyGC_Head *gc = containers->gc.gc_next;

for (; gc != containers; gc = gc->gc.gc_next) {

assert(gc->gc.gc_refs == GC_REACHABLE);

gc->gc.gc_refs = Py_REFCNT(FROM_GC(gc));

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

assert(gc->gc.gc_refs != 0);

}

}

static int

visit_decref(PyObject *op, void *data)

{

assert(op != NULL);

if (PyObject_IS_GC(op)) {

PyGC_Head *gc = AS_GC(op);

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

assert(gc->gc.gc_refs != 0); /* else refcount was too small */

if (gc->gc.gc_refs > 0)

gc->gc.gc_refs--;

}

return 0;

}

static void

subtract_refs(PyGC_Head *containers)

{

traverseproc traverse;

PyGC_Head *gc = containers->gc.gc_next;

for (; gc != containers; gc=gc->gc.gc_next) {

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

(void) traverse(FROM_GC(gc),

(visitproc)visit_decref,

NULL);

}

}

static int

visit_reachable(PyObject *op, PyGC_Head *reachable)

{

if (PyObject_IS_GC(op)) {

PyGC_Head *gc = AS_GC(op);

const Py_ssize_t gc_refs = gc->gc.gc_refs;

if (gc_refs == 0) {

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

gc->gc.gc_refs = 1;

}

else if (gc_refs == GC_TENTATIVELY_UNREACHABLE) {

/* This had gc_refs = 0 when move_unreachable got

gc_list_move(gc, reachable);

gc->gc.gc_refs = 1;

}

/* Else there's nothing to do.

else {

assert(gc_refs > 0

|| gc_refs == GC_REACHABLE

|| gc_refs == GC_UNTRACKED);

}

}

return 0;

}

static void

move_unreachable(PyGC_Head *young, PyGC_Head *unreachable)

{

PyGC_Head *gc = young->gc.gc_next;

/* Invariants: all objects "to the left" of us in young have gc_refs

while (gc != young) {

PyGC_Head *next;

if (gc->gc.gc_refs) {

/* gc is definitely reachable from outside the

PyObject *op = FROM_GC(gc);

traverseproc traverse = Py_TYPE(op)->tp_traverse;

assert(gc->gc.gc_refs > 0);

gc->gc.gc_refs = GC_REACHABLE;

(void) traverse(op,

(visitproc)visit_reachable,

(void *)young);

next = gc->gc.gc_next;

}

else {

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

next = gc->gc.gc_next;

gc_list_move(gc, unreachable);

gc->gc.gc_refs = GC_TENTATIVELY_UNREACHABLE;

}

gc = next;

}

}

static int

has_finalizer(PyObject *op)

{

if (PyInstance_Check(op)) {

assert(delstr != NULL);

return _PyInstance_Lookup(op, delstr) != NULL;

}

else if (PyType_HasFeature(op->ob_type, Py_TPFLAGS_HEAPTYPE))

return op->ob_type->tp_del != NULL;

else if (PyGen_CheckExact(op))

return PyGen_NeedsFinalizing((PyGenObject *)op);

else

return 0;

}

static void

move_finalizers(PyGC_Head *unreachable, PyGC_Head *finalizers)

{

PyGC_Head *gc;

PyGC_Head *next;

/* March over unreachable. Move objects with finalizers into

for (gc = unreachable->gc.gc_next; gc != unreachable; gc = next) {

PyObject *op = FROM_GC(gc);

assert(IS_TENTATIVELY_UNREACHABLE(op));

next = gc->gc.gc_next;

if (has_finalizer(op)) {

gc_list_move(gc, finalizers);

gc->gc.gc_refs = GC_REACHABLE;

}

}

}

static int

visit_move(PyObject *op, PyGC_Head *tolist)

{

if (PyObject_IS_GC(op)) {

if (IS_TENTATIVELY_UNREACHABLE(op)) {

PyGC_Head *gc = AS_GC(op);

gc_list_move(gc, tolist);

gc->gc.gc_refs = GC_REACHABLE;

}

}

return 0;

}

static void

move_finalizer_reachable(PyGC_Head *finalizers)

{

traverseproc traverse;

PyGC_Head *gc = finalizers->gc.gc_next;

for (; gc != finalizers; gc = gc->gc.gc_next) {

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

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

(void) traverse(FROM_GC(gc),

(visitproc)visit_move,

(void *)finalizers);

}

}

static int

handle_weakrefs(PyGC_Head *unreachable, PyGC_Head *old)

{

PyGC_Head *gc;

PyObject *op; /* generally FROM_GC(gc) */

PyWeakReference *wr; /* generally a cast of op */

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

PyGC_Head *next;

int num_freed = 0;

gc_list_init(&wrcb_to_call);

/* Clear all weakrefs to the objects in unreachable. If such a weakref

for (gc = unreachable->gc.gc_next; gc != unreachable; gc = next) {

PyWeakReference **wrlist;

op = FROM_GC(gc);

assert(IS_TENTATIVELY_UNREACHABLE(op));

next = gc->gc.gc_next;

if (! PyType_SUPPORTS_WEAKREFS(Py_TYPE(op)))

continue;

/* It supports weakrefs. Does it have any? */

wrlist = (PyWeakReference **)

PyObject_GET_WEAKREFS_LISTPTR(op);

/* `op` may have some weakrefs. March over the list, clear

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

PyGC_Head *wrasgc; /* AS_GC(wr) */

/* _PyWeakref_ClearRef clears the weakref but leaves

assert(wr->wr_object == op);

_PyWeakref_ClearRef(wr);

assert(wr->wr_object == Py_None);

if (wr->wr_callback == NULL)

continue; /* no callback */

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

if (IS_TENTATIVELY_UNREACHABLE(wr))

continue;

assert(IS_REACHABLE(wr));

/* Create a new reference so that wr can't go away

Py_INCREF(wr);

/* Move wr to wrcb_to_call, for the next pass. */

wrasgc = AS_GC(wr);

assert(wrasgc != next); /* wrasgc is reachable, but

gc_list_move(wrasgc, &wrcb_to_call);

}

}

/* Invoke the callbacks we decided to honor. It's safe to invoke them

while (! gc_list_is_empty(&wrcb_to_call)) {

PyObject *temp;

PyObject *callback;

gc = wrcb_to_call.gc.gc_next;

op = FROM_GC(gc);

assert(IS_REACHABLE(op));

assert(PyWeakref_Check(op));

wr = (PyWeakReference *)op;

callback = wr->wr_callback;

assert(callback != NULL);

/* copy-paste of weakrefobject.c's handle_callback() */

temp = PyObject_CallFunctionObjArgs(callback, wr, NULL);

if (temp == NULL)

PyErr_WriteUnraisable(callback);

else

Py_DECREF(temp);

/* Give up the reference we created in the first pass. When

Py_DECREF(op);

if (wrcb_to_call.gc.gc_next == gc) {

/* object is still alive -- move it */

gc_list_move(gc, old);

}

else

++num_freed;

}

return num_freed;

}

static void

debug_instance(char *msg, PyInstanceObject *inst)

{

char *cname;

/* simple version of instance_repr */

PyObject *classname = inst->in_class->cl_name;

if (classname != NULL && PyString_Check(classname))

cname = PyString_AsString(classname);

else

cname = "?";

PySys_WriteStderr("gc: %.100s <%.100s instance at %p>\n",

msg, cname, inst);

}

static void

debug_cycle(char *msg, PyObject *op)

{

if ((debug & DEBUG_INSTANCES) && PyInstance_Check(op)) {

debug_instance(msg, (PyInstanceObject *)op);

}

else if (debug & DEBUG_OBJECTS) {

PySys_WriteStderr("gc: %.100s <%.100s %p>\n",

msg, Py_TYPE(op)->tp_name, op);

}

}

static int

handle_finalizers(PyGC_Head *finalizers, PyGC_Head *old)

{

PyGC_Head *gc = finalizers->gc.gc_next;

if (garbage == NULL) {

garbage = PyList_New(0);

if (garbage == NULL)

Py_FatalError("gc couldn't create gc.garbage list");

}

for (; gc != finalizers; gc = gc->gc.gc_next) {

PyObject *op = FROM_GC(gc);

if ((debug & DEBUG_SAVEALL) || has_finalizer(op)) {

if (PyList_Append(garbage, op) < 0)

return -1;

}

}

gc_list_merge(finalizers, old);

return 0;

}

static void

delete_garbage(PyGC_Head *collectable, PyGC_Head *old)

{

inquiry clear;

while (!gc_list_is_empty(collectable)) {

PyGC_Head *gc = collectable->gc.gc_next;

PyObject *op = FROM_GC(gc);

assert(IS_TENTATIVELY_UNREACHABLE(op));

if (debug & DEBUG_SAVEALL) {

PyList_Append(garbage, op);

}

else {

if ((clear = Py_TYPE(op)->tp_clear) != NULL) {

Py_INCREF(op);

clear(op);

Py_DECREF(op);

}

}

if (collectable->gc.gc_next == gc) {

/* object is still alive, move it, it may die later */

gc_list_move(gc, old);

gc->gc.gc_refs = GC_REACHABLE;

}

}

}

static void

clear_freelists(void)

{

(void)PyMethod_ClearFreeList();

(void)PyFrame_ClearFreeList();

(void)PyCFunction_ClearFreeList();

(void)PyTuple_ClearFreeList();

#ifdef Py_USING_UNICODE

(void)PyUnicode_ClearFreeList();

(void)PyInt_ClearFreeList();

(void)PyFloat_ClearFreeList();

}

static double

get_time(void)

{

double result = 0;

if (tmod != NULL) {

PyObject *f = PyObject_CallMethod(tmod, "time", NULL);

if (f == NULL) {

PyErr_Clear();

}

else {

if (PyFloat_Check(f))

result = PyFloat_AsDouble(f);

Py_DECREF(f);

}

}

return result;

}

static Py_ssize_t

collect(int generation)

{

int i;

Py_ssize_t m = 0; /* # objects collected */

Py_ssize_t n = 0; /* # unreachable objects that couldn't be collected */

PyGC_Head *young; /* the generation we are examining */

PyGC_Head *old; /* next older generation */

PyGC_Head unreachable; /* non-problematic unreachable trash */

PyGC_Head finalizers; /* objects with, & reachable from, __del__ */

PyGC_Head *gc;

double t1 = 0.0;

if (delstr == NULL) {

delstr = PyString_InternFromString("__del__");

if (delstr == NULL)

Py_FatalError("gc couldn't allocate \"__del__\"");

}

if (debug & DEBUG_STATS) {

t1 = get_time();

PySys_WriteStderr("gc: collecting generation %d...\n",

generation);

PySys_WriteStderr("gc: objects in each generation:");

for (i = 0; i < NUM_GENERATIONS; i++)

PySys_WriteStderr(" %" PY_FORMAT_SIZE_T "d",

gc_list_size(GEN_HEAD(i)));

PySys_WriteStderr("\n");

}

/* update collection and allocation counters */

if (generation+1 < NUM_GENERATIONS)

generations[generation+1].count += 1;

for (i = 0; i <= generation; i++)

generations[i].count = 0;

/* merge younger generations with one we are currently collecting */

for (i = 0; i < generation; i++) {

gc_list_merge(GEN_HEAD(i), GEN_HEAD(generation));

}

/* handy references */

young = GEN_HEAD(generation);

if (generation < NUM_GENERATIONS-1)

old = GEN_HEAD(generation+1);

else

old = young;

/* Using ob_refcnt and gc_refs, calculate which objects in the

update_refs(young);

subtract_refs(young);

/* Leave everything reachable from outside young in young, and move

gc_list_init(&unreachable);

move_unreachable(young, &unreachable);

/* Move reachable objects to next generation. */

if (young != old) {

if (generation == NUM_GENERATIONS - 2) {

long_lived_pending += gc_list_size(young);

}

gc_list_merge(young, old);

}

else {

long_lived_pending = 0;

long_lived_total = gc_list_size(young);

}

/* All objects in unreachable are trash, but objects reachable from

gc_list_init(&finalizers);

move_finalizers(&unreachable, &finalizers);

/* finalizers contains the unreachable objects with a finalizer;

move_finalizer_reachable(&finalizers);

/* Collect statistics on collectable objects found and print

for (gc = unreachable.gc.gc_next; gc != &unreachable;

gc = gc->gc.gc_next) {

m++;

if (debug & DEBUG_COLLECTABLE) {

debug_cycle("collectable", FROM_GC(gc));

}

}

/* Clear weakrefs and invoke callbacks as necessary. */

m += handle_weakrefs(&unreachable, old);

/* Call tp_clear on objects in the unreachable set. This will cause

delete_garbage(&unreachable, old);

/* Collect statistics on uncollectable objects found and print

for (gc = finalizers.gc.gc_next;

gc != &finalizers;

gc = gc->gc.gc_next) {

n++;

if (debug & DEBUG_UNCOLLECTABLE)

debug_cycle("uncollectable", FROM_GC(gc));

}

if (debug & DEBUG_STATS) {

double t2 = get_time();

if (m == 0 && n == 0)

PySys_WriteStderr("gc: done");

else

PySys_WriteStderr(

"gc: done, "

"%" PY_FORMAT_SIZE_T "d unreachable, "

"%" PY_FORMAT_SIZE_T "d uncollectable",

n+m, n);

if (t1 && t2) {

PySys_WriteStderr(", %.4fs elapsed", t2-t1);

}

PySys_WriteStderr(".\n");

}

/* Append instances in the uncollectable set to a Python

(void)handle_finalizers(&finalizers, old);

/* Clear free list only during the collection of the higest

if (generation == NUM_GENERATIONS-1) {

clear_freelists();

}

if (PyErr_Occurred()) {

if (gc_str == NULL)

gc_str = PyString_FromString("garbage collection");

PyErr_WriteUnraisable(gc_str);

Py_FatalError("unexpected exception during garbage collection");

}

return n+m;

}

static Py_ssize_t

collect_generations(void)

{

int i;

Py_ssize_t n = 0;

/* Find the oldest generation (higest numbered) where the count

for (i = NUM_GENERATIONS-1; i >= 0; i--) {

if (generations[i].count > generations[i].threshold) {

/* Avoid quadratic performance degradation in number

if (i == NUM_GENERATIONS - 1

&& long_lived_pending < long_lived_total / 4)

continue;

n = collect(i);

break;

}

}

return n;

}

PyDoc_STRVAR(gc_enable__doc__,

"Enable automatic garbage collection.\n");