/*   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" /* 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_SAVEALLstatic 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 voidgc_list_init(PyGC_Head *list){	list->gc.gc_prev = list;	list->gc.gc_next = list;} static intgc_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 voidgc_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 voidgc_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 voidgc_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 voidgc_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_tgc_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 intappend_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 voidupdate_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 = FROM_GC(gc)->ob_refcnt;		/* 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 intvisit_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 voidsubtract_refs(PyGC_Head *containers){	traverseproc traverse;	PyGC_Head *gc = containers->gc.gc_next;	for (; gc != containers; gc=gc->gc.gc_next) {		traverse = FROM_GC(gc)->ob_type->tp_traverse;		(void) traverse(FROM_GC(gc),			       (visitproc)visit_decref,			       NULL);	}} /* A traversal callback for move_unreachable. */static intvisit_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 voidmove_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 = op->ob_type->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 inthas_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 voidmove_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 intvisit_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 voidmove_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 = FROM_GC(gc)->ob_type->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 inthandle_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;

Lines 1–500 of 1390. Load more