/*

  Reference Cycle Garbage Collection

  ==================================

  Neil Schemenauer <nas@arctrix.com>

  Based on a post on the python-dev list.  Ideas from Guido van Rossum,

  Eric Tiedemann, and various others.

  http://www.arctrix.com/nas/python/gc/

  http://www.python.org/pipermail/python-dev/2000-March/003869.html

  http://www.python.org/pipermail/python-dev/2000-March/004010.html

  http://www.python.org/pipermail/python-dev/2000-March/004022.html

  For a highlevel view of the collection process, read the collect

  function.

*/

#include "Python.h"

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

/* Get an object's GC head */

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

/* Get the object given the GC head */

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

/*** Global GC state ***/

struct gc_generation {

	PyGC_Head head;

	int threshold; /* collection threshold */

	int count; /* count of allocations or collections of younger

		      generations */

};

#define NUM_GENERATIONS 3

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

/* linked lists of container objects */

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

/* true if we are currently running the collector */

static int collecting = 0;

/* list of uncollectable objects */

static PyObject *garbage = NULL;

/* Python string to use if unhandled exception occurs */

static PyObject *gc_str = NULL;

/* Python string used to look for __del__ attribute. */

static PyObject *delstr = NULL;

/* set for debugging information */

#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 | \

				DEBUG_UNCOLLECTABLE | \

				DEBUG_INSTANCES | \

				DEBUG_OBJECTS | \

				DEBUG_SAVEALL

static int debug;

static PyObject *tmod = NULL;

/*--------------------------------------------------------------------------

gc_refs values.

Between collections, every gc'ed object has one of two gc_refs values:

GC_UNTRACKED

    The initial state; objects returned by PyObject_GC_Malloc are in this

    state.  The object doesn't live in any generation list, and its

    tp_traverse slot must not be called.

GC_REACHABLE

    The object lives in some generation list, and its tp_traverse is safe to

    call.  An object transitions to GC_REACHABLE when PyObject_GC_Track

    is called.

During a collection, gc_refs can temporarily take on other states:

>= 0

    At the start of a collection, update_refs() copies the true refcount

    to gc_refs, for each object in the generation being collected.

    subtract_refs() then adjusts gc_refs so that it equals the number of

    times an object is referenced directly from outside the generation

    being collected.

    gc_refs remains >= 0 throughout these steps.

GC_TENTATIVELY_UNREACHABLE

    move_unreachable() then moves objects not reachable (whether directly or

    indirectly) from outside the generation into an "unreachable" set.

    Objects that are found to be reachable have gc_refs set to GC_REACHABLE

    again.  Objects that are found to be unreachable have gc_refs set to

    GC_TENTATIVELY_UNREACHABLE.  It's "tentatively" because the pass doing

    this can't be sure until it ends, and GC_TENTATIVELY_UNREACHABLE may

    transition back to GC_REACHABLE.

    Only objects with GC_TENTATIVELY_UNREACHABLE still set are candidates

    for collection.  If it's decided not to collect such an object (e.g.,

    it has a __del__ method), its gc_refs is restored to GC_REACHABLE again.

----------------------------------------------------------------------------

*/

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

/*** list functions ***/

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

/* This became unused after gc_list_move() was introduced. */

/* Append `node` to `list`. */

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;

}

#endif

/* Remove `node` from the gc list it's currently in. */

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

}

/* Move `node` from the gc list it's currently in (which is not explicitly

 * named here) to the end of `list`.  This is semantically the same as

 * gc_list_remove(node) followed by gc_list_append(node, list).

 */

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;

}

/* append list `from` onto list `to`; `from` becomes an empty 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;

}

/* Append objects in a GC list to a Python list.

 * Return 0 if all OK, < 0 if error (out of memory for list).

 */

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;

}

/*** end of list stuff ***/

/* Set all gc_refs = ob_refcnt.  After this, gc_refs is > 0 for all objects

 * in containers, and is GC_REACHABLE for all tracked gc objects not in

 * containers.

 */

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

		 * of 0:  if something decref'ed to 0, it should have been

		 * deallocated immediately at that time.

		 * Possible cause (if the assert triggers):  a tp_dealloc

		 * routine left a gc-aware object tracked during its teardown

		 * phase, and did something-- or allowed something to happen --

		 * that called back into Python.  gc can trigger then, and may

		 * see the still-tracked dying object.  Before this assert

		 * was added, such mistakes went on to allow gc to try to

		 * delete the object again.  In a debug build, that caused

		 * a mysterious segfault, when _Py_ForgetReference tried

		 * to remove the object from the doubly-linked list of all

		 * objects a second time.  In a release build, an actual

		 * double deallocation occurred, which leads to corruption

		 * of the allocator's internal bookkeeping pointers.  That's

		 * so serious that maybe this should be a release-build

		 * check instead of an assert?

		 */

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

	}

}

/* A traversal callback for subtract_refs. */

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

		 * generation being collected, which can be recognized

		 * because only they have positive gc_refs.

		 */

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

		if (gc->gc.gc_refs > 0)

			gc->gc.gc_refs--;

	}

	return 0;

}

/* Subtract internal references from gc_refs.  After this, gc_refs is >= 0

 * for all objects in containers, and is GC_REACHABLE for all tracked gc

 * objects not in containers.  The ones with gc_refs > 0 are directly

 * reachable from outside containers, and so can't be collected.

 */

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

	}

}

/* A traversal callback for move_unreachable. */

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

			 * the traversal hasn't yet gotten to it.  All

			 * we need to do is tell move_unreachable that it's

			 * reachable.

			 */

			gc->gc.gc_refs = 1;

		}

		else if (gc_refs == GC_TENTATIVELY_UNREACHABLE) {

			/* This had gc_refs = 0 when move_unreachable got

			 * to it, but turns out it's reachable after all.

			 * Move it back to move_unreachable's 'young' list,

			 * and move_unreachable will eventually get to it

			 * again.

			 */

			gc_list_move(gc, reachable);

			gc->gc.gc_refs = 1;

		}

		/* Else there's nothing to do.

		 * If gc_refs > 0, it must be in move_unreachable's 'young'

		 * list, and move_unreachable will eventually get to it.

		 * If gc_refs == GC_REACHABLE, it's either in some other

		 * generation so we don't care about it, or move_unreachable

		 * already dealt with it.

		 * If gc_refs == GC_UNTRACKED, it must be ignored.

		 */

		 else {

		 	assert(gc_refs > 0

		 	       || gc_refs == GC_REACHABLE

		 	       || gc_refs == GC_UNTRACKED);

		 }

	}

	return 0;

}

/* Move the unreachable objects from young to unreachable.  After this,

 * all objects in young have gc_refs = GC_REACHABLE, and all objects in

 * unreachable have gc_refs = GC_TENTATIVELY_UNREACHABLE.  All tracked

 * gc objects not in young or unreachable still have gc_refs = GC_REACHABLE.

 * All objects in young after this are directly or indirectly reachable

 * from outside the original young; and all objects in unreachable are

 * not.

 */

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

	 * = GC_REACHABLE, and are indeed reachable (directly or indirectly)

	 * from outside the young list as it was at entry.  All other objects

	 * from the original young "to the left" of us are in unreachable now,

	 * and have gc_refs = GC_TENTATIVELY_UNREACHABLE.  All objects to the

	 * left of us in 'young' now have been scanned, and no objects here

	 * or to the right have been scanned yet.

	 */

	while (gc != young) {

		PyGC_Head *next;

		if (gc->gc.gc_refs) {

                        /* gc is definitely reachable from outside the

                         * original 'young'.  Mark it as such, and traverse

                         * its pointers to find any other objects that may

                         * be directly reachable from it.  Note that the

                         * call to tp_traverse may append objects to young,

                         * so we have to wait until it returns to determine

                         * the next object to visit.

                         */

                        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,

			 * assume it is.  gc isn't directly reachable from

			 * any object we've already traversed, but may be

			 * reachable from an object we haven't gotten to yet.

			 * visit_reachable will eventually move gc back into

			 * young if that's so, and we'll see it again.

			 */

			next = gc->gc.gc_next;

			gc_list_move(gc, unreachable);

			gc->gc.gc_refs = GC_TENTATIVELY_UNREACHABLE;

		}

		gc = next;

	}

}

/* Return true if object has a finalization method.

 * CAUTION:  An instance of an old-style class has to be checked for a

 *__del__ method, and earlier versions of this used to call PyObject_HasAttr,

 * which in turn could call the class's __getattr__ hook (if any).  That

 * could invoke arbitrary Python code, mutating the object graph in arbitrary

 * ways, and that was the source of some excruciatingly subtle bugs.

 */

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;

}

/* Move the objects in unreachable with __del__ methods into `finalizers`.

 * Objects moved into `finalizers` have gc_refs set to GC_REACHABLE; the

 * objects remaining in unreachable are left at GC_TENTATIVELY_UNREACHABLE.

 */

static void

move_finalizers(PyGC_Head *unreachable, PyGC_Head *finalizers)

{

	PyGC_Head *gc;

	PyGC_Head *next;

	/* March over unreachable.  Move objects with finalizers into

	 * `finalizers`.

	 */

	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;

		}

	}

}

/* A traversal callback for move_finalizer_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;

}

/* Move objects that are reachable from finalizers, from the unreachable set

 * into finalizers set.

 */

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

	}

}

/* Clear all weakrefs to unreachable objects, and if such a weakref has a

 * callback, invoke it if necessary.  Note that it's possible for such

 * weakrefs to be outside the unreachable set -- indeed, those are precisely

 * the weakrefs whose callbacks must be invoked.  See gc_weakref.txt for

 * overview & some details.  Some weakrefs with callbacks may be reclaimed

 * directly by this routine; the number reclaimed is the return value.  Other

 * weakrefs with callbacks may be moved into the `old` generation.  Objects

 * moved into `old` have gc_refs set to GC_REACHABLE; the objects remaining in

 * unreachable are left at GC_TENTATIVELY_UNREACHABLE.  When this returns,

 * no object in `unreachable` is weakly referenced anymore.

 */

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

	 * also has a callback, move it into `wrcb_to_call` if the callback

	 * needs to be invoked.  Note that we cannot invoke any callbacks until

	 * all weakrefs to unreachable objects are cleared, lest the callback

	 * resurrect an unreachable object via a still-active weakref.  We

	 * make another pass over wrcb_to_call, invoking callbacks, after this

	 * pass completes.

	 */

	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