1 /*

     2 

     3   Reference Cycle Garbage Collection

     4   ==================================

     5 

     6   Neil Schemenauer <nas@arctrix.com>

     7 

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

     9   Eric Tiedemann, and various others.

    10 

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

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

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

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

    15 

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

    17   function.

    18 

    19 */

    20 

    21 #include "Python.h"

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

    23 

    24 /* Get an object's GC head */

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

    26 

    27 /* Get the object given the GC head */

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

    29 

    30 /*** Global GC state ***/

    31 

    32 struct gc_generation {

    33 	PyGC_Head head;

    34 	int threshold; /* collection threshold */

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

    36 		      generations */

    37 };

    38 

    39 #define NUM_GENERATIONS 3

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

    41 

    42 /* linked lists of container objects */

    43 static struct gc_generation generations[NUM_GENERATIONS] = {

    44 	/* PyGC_Head,				threshold,	count */

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

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

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

    48 };

    49 

    50 PyGC_Head *_PyGC_generation0 = GEN_HEAD(0);

    51 

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

    53 

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

    55 static int collecting = 0;

    56 

    57 /* list of uncollectable objects */

    58 static PyObject *garbage = NULL;

    59 

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

    61 static PyObject *gc_str = NULL;

    62 

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

    64 static PyObject *delstr = NULL;

    65 

    66 /* set for debugging information */

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

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

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

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

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

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

    73 #define DEBUG_LEAK		DEBUG_COLLECTABLE | \

    74 				DEBUG_UNCOLLECTABLE | \

    75 				DEBUG_INSTANCES | \

    76 				DEBUG_OBJECTS | \

    77 				DEBUG_SAVEALL

    78 static int debug;

    79 static PyObject *tmod = NULL;

    80 

    81 /*--------------------------------------------------------------------------

    82 gc_refs values.

    83 

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

    85 

    86 GC_UNTRACKED

    87     The initial state; objects returned by PyObject_GC_Malloc are in this

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

    89     tp_traverse slot must not be called.

    90 

    91 GC_REACHABLE

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

    93     call.  An object transitions to GC_REACHABLE when PyObject_GC_Track

    94     is called.

    95 

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

    97 

    98 >= 0

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

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

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

   102     times an object is referenced directly from outside the generation

   103     being collected.

   104     gc_refs remains >= 0 throughout these steps.

   105 

   106 GC_TENTATIVELY_UNREACHABLE

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

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

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

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

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

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

   113     transition back to GC_REACHABLE.

   114 

   115     Only objects with GC_TENTATIVELY_UNREACHABLE still set are candidates

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

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

   118 ----------------------------------------------------------------------------

   119 */

   120 #define GC_UNTRACKED			_PyGC_REFS_UNTRACKED

   121 #define GC_REACHABLE			_PyGC_REFS_REACHABLE

   122 #define GC_TENTATIVELY_UNREACHABLE	_PyGC_REFS_TENTATIVELY_UNREACHABLE

   123 

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

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

   126 #define IS_TENTATIVELY_UNREACHABLE(o) ( \

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

   128 

   129 /*** list functions ***/

   130 

   131 static void

   132 gc_list_init(PyGC_Head *list)

   133 {

   134 	list->gc.gc_prev = list;

   135 	list->gc.gc_next = list;

   136 }

   137 

   138 static int

   139 gc_list_is_empty(PyGC_Head *list)

   140 {

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

   142 }

   143 

   144 #if 0

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

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

   147 static void

   148 gc_list_append(PyGC_Head *node, PyGC_Head *list)

   149 {

   150 	node->gc.gc_next = list;

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

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

   153 	list->gc.gc_prev = node;

   154 }

   155 #endif

   156 

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

   158 static void

   159 gc_list_remove(PyGC_Head *node)

   160 {

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

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

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

   164 }

   165 

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

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

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

   169  */

   170 static void

   171 gc_list_move(PyGC_Head *node, PyGC_Head *list)

   172 {

   173 	PyGC_Head *new_prev;

   174 	PyGC_Head *current_prev = node->gc.gc_prev;

   175 	PyGC_Head *current_next = node->gc.gc_next;

   176 	/* Unlink from current list. */

   177 	current_prev->gc.gc_next = current_next;

   178 	current_next->gc.gc_prev = current_prev;

   179 	/* Relink at end of new list. */

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

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

   182 	node->gc.gc_next = list;

   183 }

   184 

   185 /* append list `from` onto list `to`; `from` becomes an empty list */

   186 static void

   187 gc_list_merge(PyGC_Head *from, PyGC_Head *to)

   188 {

   189 	PyGC_Head *tail;

   190 	assert(from != to);

   191 	if (!gc_list_is_empty(from)) {

   192 		tail = to->gc.gc_prev;

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

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

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

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

   197 	}

   198 	gc_list_init(from);

   199 }

   200 

   201 static Py_ssize_t

   202 gc_list_size(PyGC_Head *list)

   203 {

   204 	PyGC_Head *gc;

   205 	Py_ssize_t n = 0;

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

   207 		n++;

   208 	}

   209 	return n;

   210 }

   211 

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

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

   214  */

   215 static int

   216 append_objects(PyObject *py_list, PyGC_Head *gc_list)

   217 {

   218 	PyGC_Head *gc;

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

   220 		PyObject *op = FROM_GC(gc);

   221 		if (op != py_list) {

   222 			if (PyList_Append(py_list, op)) {

   223 				return -1; /* exception */

   224 			}

   225 		}

   226 	}

   227 	return 0;

   228 }

   229 

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

   231 

   232 

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

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

   235  * containers.

   236  */

   237 static void

   238 update_refs(PyGC_Head *containers)

   239 {

   240 	PyGC_Head *gc = containers->gc.gc_next;

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

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

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

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

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

   246 		 * deallocated immediately at that time.

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

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

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

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

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

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

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

   254 		 * a mysterious segfault, when _Py_ForgetReference tried

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

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

   257 		 * double deallocation occurred, which leads to corruption

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

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

   260 		 * check instead of an assert?

   261 		 */

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

   263 	}

   264 }

   265 

   266 /* A traversal callback for subtract_refs. */

   267 static int

   268 visit_decref(PyObject *op, void *data)

   269 {

   270         assert(op != NULL);

   271 	if (PyObject_IS_GC(op)) {

   272 		PyGC_Head *gc = AS_GC(op);

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

   274 		 * generation being collected, which can be recognized

   275 		 * because only they have positive gc_refs.

   276 		 */

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

   278 		if (gc->gc.gc_refs > 0)

   279 			gc->gc.gc_refs--;

   280 	}

   281 	return 0;

   282 }

   283 

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

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

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

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

   288  */

   289 static void

   290 subtract_refs(PyGC_Head *containers)

   291 {

   292 	traverseproc traverse;

   293 	PyGC_Head *gc = containers->gc.gc_next;

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

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

   296 		(void) traverse(FROM_GC(gc),

   297 			       (visitproc)visit_decref,

   298 			       NULL);

   299 	}

   300 }

   301 

   302 /* A traversal callback for move_unreachable. */

   303 static int

   304 visit_reachable(PyObject *op, PyGC_Head *reachable)

   305 {

   306 	if (PyObject_IS_GC(op)) {

   307 		PyGC_Head *gc = AS_GC(op);

   308 		const Py_ssize_t gc_refs = gc->gc.gc_refs;

   309 

   310 		if (gc_refs == 0) {

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

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

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

   314 			 * reachable.

   315 			 */

   316 			gc->gc.gc_refs = 1;

   317 		}

   318 		else if (gc_refs == GC_TENTATIVELY_UNREACHABLE) {

   319 			/* This had gc_refs = 0 when move_unreachable got

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

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

   322 			 * and move_unreachable will eventually get to it

   323 			 * again.

   324 			 */

   325 			gc_list_move(gc, reachable);

   326 			gc->gc.gc_refs = 1;

   327 		}

   328 		/* Else there's nothing to do.

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

   330 		 * list, and move_unreachable will eventually get to it.

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

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

   333 		 * already dealt with it.

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

   335 		 */

   336 		 else {

   337 		 	assert(gc_refs > 0

   338 		 	       || gc_refs == GC_REACHABLE

   339 		 	       || gc_refs == GC_UNTRACKED);

   340 		 }

   341 	}

   342 	return 0;

   343 }

   344 

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

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

   347  * unreachable have gc_refs = GC_TENTATIVELY_UNREACHABLE.  All tracked

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

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

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

   351  * not.

   352  */

   353 static void

   354 move_unreachable(PyGC_Head *young, PyGC_Head *unreachable)

   355 {

   356 	PyGC_Head *gc = young->gc.gc_next;

   357 

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

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

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

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

   362 	 * and have gc_refs = GC_TENTATIVELY_UNREACHABLE.  All objects to the

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

   364 	 * or to the right have been scanned yet.

   365 	 */

   366 

   367 	while (gc != young) {

   368 		PyGC_Head *next;

   369 

   370 		if (gc->gc.gc_refs) {

   371                         /* gc is definitely reachable from outside the

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

   373                          * its pointers to find any other objects that may

   374                          * be directly reachable from it.  Note that the

   375                          * call to tp_traverse may append objects to young,

   376                          * so we have to wait until it returns to determine

   377                          * the next object to visit.

   378                          */

   379                         PyObject *op = FROM_GC(gc);

   380                         traverseproc traverse = Py_TYPE(op)->tp_traverse;

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

   382                         gc->gc.gc_refs = GC_REACHABLE;

   383                         (void) traverse(op,

   384                                         (visitproc)visit_reachable,

   385                                         (void *)young);

   386                         next = gc->gc.gc_next;

   387 		}

   388 		else {

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

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

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

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

   393 			 * visit_reachable will eventually move gc back into

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

   395 			 */

   396 			next = gc->gc.gc_next;

   397 			gc_list_move(gc, unreachable);

   398 			gc->gc.gc_refs = GC_TENTATIVELY_UNREACHABLE;

   399 		}

   400 		gc = next;

   401 	}

   402 }

   403 

   404 /* Return true if object has a finalization method.

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

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

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

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

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

   410  */

   411 static int

   412 has_finalizer(PyObject *op)

   413 {

   414 	if (PyInstance_Check(op)) {

   415 		assert(delstr != NULL);

   416 		return _PyInstance_Lookup(op, delstr) != NULL;

   417 	}

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

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

   420 	else if (PyGen_CheckExact(op))

   421 		return PyGen_NeedsFinalizing((PyGenObject *)op);

   422 	else

   423 		return 0;

   424 }

   425 

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

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

   428  * objects remaining in unreachable are left at GC_TENTATIVELY_UNREACHABLE.

   429  */

   430 static void

   431 move_finalizers(PyGC_Head *unreachable, PyGC_Head *finalizers)

   432 {

   433 	PyGC_Head *gc;

   434 	PyGC_Head *next;

   435 

   436 	/* March over unreachable.  Move objects with finalizers into

   437 	 * `finalizers`.

   438 	 */

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

   440 		PyObject *op = FROM_GC(gc);

   441 

   442 		assert(IS_TENTATIVELY_UNREACHABLE(op));

   443 		next = gc->gc.gc_next;

   444 

   445 		if (has_finalizer(op)) {

   446 			gc_list_move(gc, finalizers);

   447 			gc->gc.gc_refs = GC_REACHABLE;

   448 		}

   449 	}

   450 }

   451 

   452 /* A traversal callback for move_finalizer_reachable. */

   453 static int

   454 visit_move(PyObject *op, PyGC_Head *tolist)

   455 {

   456 	if (PyObject_IS_GC(op)) {

   457 		if (IS_TENTATIVELY_UNREACHABLE(op)) {

   458 			PyGC_Head *gc = AS_GC(op);

   459 			gc_list_move(gc, tolist);

   460 			gc->gc.gc_refs = GC_REACHABLE;

   461 		}

   462 	}

   463 	return 0;

   464 }

   465 

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

   467  * into finalizers set.

   468  */

   469 static void

   470 move_finalizer_reachable(PyGC_Head *finalizers)

   471 {

   472 	traverseproc traverse;

   473 	PyGC_Head *gc = finalizers->gc.gc_next;

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

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

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

   477 		(void) traverse(FROM_GC(gc),

   478 				(visitproc)visit_move,

   479 				(void *)finalizers);

   480 	}

   481 }

   482 

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

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

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

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

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

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

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

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

   491  * unreachable are left at GC_TENTATIVELY_UNREACHABLE.  When this returns,

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

   493  */

   494 static int

   495 handle_weakrefs(PyGC_Head *unreachable, PyGC_Head *old)

   496 {

   497 	PyGC_Head *gc;

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

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

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

   501 	PyGC_Head *next;

   502 	int num_freed = 0;

   503 

   504 	gc_list_init(&wrcb_to_call);

   505 

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

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

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

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

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

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

   512 	 * pass completes.

   513 	 */

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

   515 		PyWeakReference **wrlist;

   516 

   517 		op = FROM_GC(gc);

   518 		assert(IS_TENTATIVELY_UNREACHABLE(op));

   519 		next = gc->gc.gc_next;

   520 

   521 		if (! PyType_SUPPORTS_WEAKREFS(Py_TYPE(op)))

   522 			continue;

   523 

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

   525 		wrlist = (PyWeakReference **)

   526 			     		PyObject_GET_WEAKREFS_LISTPTR(op);

   527 

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

   529 		 * all the weakrefs, and move the weakrefs with callbacks

   530 		 * that must be called into wrcb_to_call.

   531 		 */

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

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

   534 

   535 			/* _PyWeakref_ClearRef clears the weakref but leaves

   536 			 * the callback pointer intact.  Obscure:  it also

   537 			 * changes *wrlist.

   538 			 */

   539 			assert(wr->wr_object == op);

   540 			_PyWeakref_ClearRef(wr);

   541 			assert(wr->wr_object == Py_None);

   542 			if (wr->wr_callback == NULL)

   543 				continue;	/* no callback */

   544 

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

   546 	 * `wr`, which has a callback.  Should the callback be invoked?  If wr

   547 	 * is also trash, no:

   548 	 *

   549 	 * 1. There's no need to call it.  The object and the weakref are

   550 	 *    both going away, so it's legitimate to pretend the weakref is

   551 	 *    going away first.  The user has to ensure a weakref outlives its

   552 	 *    referent if they want a guarantee that the wr callback will get

   553 	 *    invoked.

   554 	 *

   555 	 * 2. It may be catastrophic to call it.  If the callback is also in

   556 	 *    cyclic trash (CT), then although the CT is unreachable from

   557 	 *    outside the current generation, CT may be reachable from the

   558 	 *    callback.  Then the callback could resurrect insane objects.

   559 	 *

   560 	 * Since the callback is never needed and may be unsafe in this case,

   561 	 * wr is simply left in the unreachable set.  Note that because we

   562 	 * already called _PyWeakref_ClearRef(wr), its callback will never

   563 	 * trigger.

   564 	 *

   565 	 * OTOH, if wr isn't part of CT, we should invoke the callback:  the

   566 	 * weakref outlived the trash.  Note that since wr isn't CT in this

   567 	 * case, its callback can't be CT either -- wr acted as an external

   568 	 * root to this generation, and therefore its callback did too.  So

   569 	 * nothing in CT is reachable from the callback either, so it's hard

   570 	 * to imagine how calling it later could create a problem for us.  wr

   571 	 * is moved to wrcb_to_call in this case.

   572 	 */

   573 	 		if (IS_TENTATIVELY_UNREACHABLE(wr))

   574 	 			continue;

   575 			assert(IS_REACHABLE(wr));

   576 

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

   578 			 * before we can process it again.

   579 			 */

   580 			Py_INCREF(wr);

   581 

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

   583 			wrasgc = AS_GC(wr);

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

   585 			                           next isn't, so they can't

   586 			                           be the same */

   587 			gc_list_move(wrasgc, &wrcb_to_call);

   588 		}

   589 	}

   590 

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

   592 	 * because they can't reference unreachable objects.

   593 	 */

   594 	while (! gc_list_is_empty(&wrcb_to_call)) {

   595 		PyObject *temp;

   596 		PyObject *callback;

   597 

   598 		gc = wrcb_to_call.gc.gc_next;

   599 		op = FROM_GC(gc);

   600 		assert(IS_REACHABLE(op));

   601 		assert(PyWeakref_Check(op));

   602 		wr = (PyWeakReference *)op;

   603 		callback = wr->wr_callback;

   604 		assert(callback != NULL);

   605 

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

   607 		temp = PyObject_CallFunctionObjArgs(callback, wr, NULL);

   608 		if (temp == NULL)

   609 			PyErr_WriteUnraisable(callback);

   610 		else

   611 			Py_DECREF(temp);

   612 

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

   614 		 * op's refcount hits 0 (which it may or may not do right now),

   615 		 * op's tp_dealloc will decref op->wr_callback too.  Note

   616 		 * that the refcount probably will hit 0 now, and because this

   617 		 * weakref was reachable to begin with, gc didn't already

   618 		 * add it to its count of freed objects.  Example:  a reachable

   619 		 * weak value dict maps some key to this reachable weakref.

   620 		 * The callback removes this key->weakref mapping from the

   621 		 * dict, leaving no other references to the weakref (excepting

   622 		 * ours).

   623 		 */

   624 		Py_DECREF(op);

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

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

   627 			gc_list_move(gc, old);

   628 		}

   629 		else

   630 			++num_freed;

   631 	}

   632 

   633 	return num_freed;

   634 }

   635 

   636 static void

   637 debug_instance(char *msg, PyInstanceObject *inst)

   638 {

   639 	char *cname;

   640 	/* simple version of instance_repr */

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

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

   643 		cname = PyString_AsString(classname);

   644 	else

   645 		cname = "?";

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

   647 			  msg, cname, inst);

   648 }

   649 

   650 static void

   651 debug_cycle(char *msg, PyObject *op)

   652 {

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

   654 		debug_instance(msg, (PyInstanceObject *)op);

   655 	}

   656 	else if (debug & DEBUG_OBJECTS) {

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

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

   659 	}

   660 }

   661 

   662 /* Handle uncollectable garbage (cycles with finalizers, and stuff reachable

   663  * only from such cycles).

   664  * If DEBUG_SAVEALL, all objects in finalizers are appended to the module

   665  * garbage list (a Python list), else only the objects in finalizers with

   666  * __del__ methods are appended to garbage.  All objects in finalizers are

   667  * merged into the old list regardless.

   668  * Returns 0 if all OK, <0 on error (out of memory to grow the garbage list).

   669  * The finalizers list is made empty on a successful return.

   670  */

   671 static int

   672 handle_finalizers(PyGC_Head *finalizers, PyGC_Head *old)

   673 {

   674 	PyGC_Head *gc = finalizers->gc.gc_next;

   675 

   676 	if (garbage == NULL) {

   677 		garbage = PyList_New(0);

   678 		if (garbage == NULL)

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

   680 	}

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

   682 		PyObject *op = FROM_GC(gc);

   683 

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

   685 			if (PyList_Append(garbage, op) < 0)

   686 				return -1;

   687 		}

   688 	}

   689 

   690 	gc_list_merge(finalizers, old);

   691 	return 0;

   692 }

   693 

   694 /* Break reference cycles by clearing the containers involved.	This is

   695  * tricky business as the lists can be changing and we don't know which

   696  * objects may be freed.  It is possible I screwed something up here.

   697  */

   698 static void

   699 delete_garbage(PyGC_Head *collectable, PyGC_Head *old)

   700 {

   701 	inquiry clear;

   702 

   703 	while (!gc_list_is_empty(collectable)) {

   704 		PyGC_Head *gc = collectable->gc.gc_next;

   705 		PyObject *op = FROM_GC(gc);

   706 

   707 		assert(IS_TENTATIVELY_UNREACHABLE(op));

   708 		if (debug & DEBUG_SAVEALL) {

   709 			PyList_Append(garbage, op);

   710 		}

   711 		else {

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

   713 				Py_INCREF(op);

   714 				clear(op);

   715 				Py_DECREF(op);

   716 			}

   717 		}

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

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

   720 			gc_list_move(gc, old);

   721 			gc->gc.gc_refs = GC_REACHABLE;

   722 		}

   723 	}

   724 }

   725 

   726 /* Clear all free lists

   727  * All free lists are cleared during the collection of the highest generation.

   728  * Allocated items in the free list may keep a pymalloc arena occupied.

   729  * Clearing the free lists may give back memory to the OS earlier.

   730  */

   731 static void

   732 clear_freelists(void)

   733 {

   734 	(void)PyMethod_ClearFreeList();

   735 	(void)PyFrame_ClearFreeList();

   736 	(void)PyCFunction_ClearFreeList();

   737 	(void)PyTuple_ClearFreeList();

   738 	(void)PyUnicode_ClearFreeList();

   739 	(void)PyInt_ClearFreeList();

   740 	(void)PyFloat_ClearFreeList();

   741 }

   742 

   743 /* This is the main function.  Read this to understand how the

   744  * collection process works. */

   745 static Py_ssize_t

   746 collect(int generation)

   747 {

   748 	int i;

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

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

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

   752 	PyGC_Head *old; /* next older generation */

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

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

   755 	PyGC_Head *gc;

   756 	double t1 = 0.0;

   757 

   758 	if (delstr == NULL) {

   759 		delstr = PyString_InternFromString("__del__");

   760 		if (delstr == NULL)

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

   762 	}

   763 

   764 	if (debug & DEBUG_STATS) {

   765 		if (tmod != NULL) {

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

   767 			if (f == NULL) {

   768 				PyErr_Clear();

   769 			}

   770 			else {

   771 				t1 = PyFloat_AsDouble(f);

   772 				Py_DECREF(f);

   773 			}

   774 		}

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

   776 				  generation);

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

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

   779 			PySys_WriteStderr(" %" PY_FORMAT_SIZE_T "d",

   780 					  gc_list_size(GEN_HEAD(i)));

   781 		PySys_WriteStderr("\n");

   782 	}

   783 

   784 	/* update collection and allocation counters */

   785 	if (generation+1 < NUM_GENERATIONS)

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

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

   788 		generations[i].count = 0;

   789 

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

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

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

   793 	}

   794 

   795 	/* handy references */

   796 	young = GEN_HEAD(generation);

   797 	if (generation < NUM_GENERATIONS-1)

   798 		old = GEN_HEAD(generation+1);

   799 	else

   800 		old = young;

   801 

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

   803 	 * container set are reachable from outside the set (i.e., have a

   804 	 * refcount greater than 0 when all the references within the

   805 	 * set are taken into account).

   806 	 */

   807 	update_refs(young);

   808 	subtract_refs(young);

   809 

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

   811 	 * everything else (in young) to unreachable.

   812 	 * NOTE:  This used to move the reachable objects into a reachable

   813 	 * set instead.  But most things usually turn out to be reachable,

   814 	 * so it's more efficient to move the unreachable things.

   815 	 */

   816 	gc_list_init(&unreachable);

   817 	move_unreachable(young, &unreachable);

   818 

   819 	/* Move reachable objects to next generation. */

   820 	if (young != old)

   821 		gc_list_merge(young, old);

   822 

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

   824 	 * finalizers can't safely be deleted.  Python programmers should take

   825 	 * care not to create such things.  For Python, finalizers means

   826 	 * instance objects with __del__ methods.  Weakrefs with callbacks

   827 	 * can also call arbitrary Python code but they will be dealt with by

   828 	 * handle_weakrefs().

   829  	 */

   830 	gc_list_init(&finalizers);

   831 	move_finalizers(&unreachable, &finalizers);

   832 	/* finalizers contains the unreachable objects with a finalizer;

   833 	 * unreachable objects reachable *from* those are also uncollectable,

   834 	 * and we move those into the finalizers list too.

   835 	 */

   836 	move_finalizer_reachable(&finalizers);

   837 

   838 	/* Collect statistics on collectable objects found and print

   839 	 * debugging information.

   840 	 */

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

   842 			gc = gc->gc.gc_next) {

   843 		m++;

   844 		if (debug & DEBUG_COLLECTABLE) {

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

   846 		}

   847 		if (tmod != NULL && (debug & DEBUG_STATS)) {

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

   849 			if (f == NULL) {

   850 				PyErr_Clear();

   851 			}

   852 			else {

   853 				t1 = PyFloat_AsDouble(f)-t1;

   854 				Py_DECREF(f);

   855 				PySys_WriteStderr("gc: %.4fs elapsed.\n", t1);

   856 			}

   857 		}

   858 	}

   859 

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

   861 	m += handle_weakrefs(&unreachable, old);

   862 

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

   864 	 * the reference cycles to be broken.  It may also cause some objects

   865 	 * in finalizers to be freed.

   866 	 */

   867 	delete_garbage(&unreachable, old);

   868 

   869 	/* Collect statistics on uncollectable objects found and print

   870 	 * debugging information. */

   871 	for (gc = finalizers.gc.gc_next;

   872 	     gc != &finalizers;

   873 	     gc = gc->gc.gc_next) {

   874 		n++;

   875 		if (debug & DEBUG_UNCOLLECTABLE)

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

   877 	}

   878 	if (debug & DEBUG_STATS) {

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

   880 			PySys_WriteStderr("gc: done.\n");

   881 		else

   882 			PySys_WriteStderr(

   883 			    "gc: done, "

   884 			    "%" PY_FORMAT_SIZE_T "d unreachable, "

   885 			    "%" PY_FORMAT_SIZE_T "d uncollectable.\n",

   886 			    n+m, n);

   887 	}

   888 

   889 	/* Append instances in the uncollectable set to a Python

   890 	 * reachable list of garbage.  The programmer has to deal with

   891 	 * this if they insist on creating this type of structure.

   892 	 */

   893 	(void)handle_finalizers(&finalizers, old);

   894 

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

   896 	 * generation */

   897 	if (generation == NUM_GENERATIONS-1) {

   898 		clear_freelists();

   899 	}

   900 

   901 	if (PyErr_Occurred()) {

   902 		if (gc_str == NULL)

   903 			gc_str = PyString_FromString("garbage collection");

   904 		PyErr_WriteUnraisable(gc_str);

   905 		Py_FatalError("unexpected exception during garbage collection");

   906 	}

   907 	return n+m;

   908 }

   909 

   910 static Py_ssize_t

   911 collect_generations(void)

   912 {

   913 	int i;

   914 	Py_ssize_t n = 0;

   915 

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

   917 	 * exceeds the threshold.  Objects in the that generation and

   918 	 * generations younger than it will be collected. */

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

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

   921 			n = collect(i);

   922 			break;

   923 		}

   924 	}

   925 	return n;

   926 }

   927 

   928 PyDoc_STRVAR(gc_enable__doc__,

   929 "enable() -> None\n"

   930 "\n"

   931 "Enable automatic garbage collection.\n");

   932 

   933 static PyObject *

   934 gc_enable(PyObject *self, PyObject *noargs)

   935 {

   936 	enabled = 1;

   937 	Py_INCREF(Py_None);

   938 	return Py_None;

   939 }

   940 

   941 PyDoc_STRVAR(gc_disable__doc__,

   942 "disable() -> None\n"

   943 "\n"

   944 "Disable automatic garbage collection.\n");

   945 

   946 static PyObject *

   947 gc_disable(PyObject *self, PyObject *noargs)

   948 {

   949 	enabled = 0;

   950 	Py_INCREF(Py_None);

   951 	return Py_None;

   952 }

   953 

   954 PyDoc_STRVAR(gc_isenabled__doc__,

   955 "isenabled() -> status\n"

   956 "\n"

   957 "Returns true if automatic garbage collection is enabled.\n");

   958 

   959 static PyObject *

   960 gc_isenabled(PyObject *self, PyObject *noargs)

   961 {

   962 	return PyBool_FromLong((long)enabled);

   963 }

   964 

   965 PyDoc_STRVAR(gc_collect__doc__,

   966 "collect([generation]) -> n\n"

   967 "\n"

   968 "With no arguments, run a full collection.  The optional argument\n"

   969 "may be an integer specifying which generation to collect.  A ValueError\n"

   970 "is raised if the generation number is invalid.\n\n"

   971 "The number of unreachable objects is returned.\n");

   972 

   973 static PyObject *

   974 gc_collect(PyObject *self, PyObject *args, PyObject *kws)

   975 {

   976 	static char *keywords[] = {"generation", NULL};

   977 	int genarg = NUM_GENERATIONS - 1;

   978 	Py_ssize_t n;

   979 

   980 	if (!PyArg_ParseTupleAndKeywords(args, kws, "|i", keywords, &genarg))

   981 		return NULL;

   982 

   983 	else if (genarg < 0 || genarg >= NUM_GENERATIONS) {

   984 		PyErr_SetString(PyExc_ValueError, "invalid generation");

   985 		return NULL;

   986 	}

   987 

   988 	if (collecting)

   989 		n = 0; /* already collecting, don't do anything */

   990 	else {

   991 		collecting = 1;

   992 		n = collect(genarg);

   993 		collecting = 0;

   994 	}

   995 

   996 	return PyInt_FromSsize_t(n);

   997 }

   998 

   999 PyDoc_STRVAR(gc_set_debug__doc__,

  1000 "set_debug(flags) -> None\n"

  1001 "\n"

  1002 "Set the garbage collection debugging flags. Debugging information is\n"

  1003 "written to sys.stderr.\n"

  1004 "\n"

  1005 "flags is an integer and can have the following bits turned on:\n"

  1006 "\n"

  1007 "  DEBUG_STATS - Print statistics during collection.\n"

  1008 "  DEBUG_COLLECTABLE - Print collectable objects found.\n"

  1009 "  DEBUG_UNCOLLECTABLE - Print unreachable but uncollectable objects found.\n"

  1010 "  DEBUG_INSTANCES - Print instance objects.\n"

  1011 "  DEBUG_OBJECTS - Print objects other than instances.\n"

  1012 "  DEBUG_SAVEALL - Save objects to gc.garbage rather than freeing them.\n"

  1013 "  DEBUG_LEAK - Debug leaking programs (everything but STATS).\n");

  1014 

  1015 static PyObject *

  1016 gc_set_debug(PyObject *self, PyObject *args)

  1017 {

  1018 	if (!PyArg_ParseTuple(args, "i:set_debug", &debug))

  1019 		return NULL;

  1020 

  1021 	Py_INCREF(Py_None);

  1022 	return Py_None;

  1023 }

  1024 

  1025 PyDoc_STRVAR(gc_get_debug__doc__,

  1026 "get_debug() -> flags\n"

  1027 "\n"

  1028 "Get the garbage collection debugging flags.\n");

  1029 

  1030 static PyObject *

  1031 gc_get_debug(PyObject *self, PyObject *noargs)

  1032 {

  1033 	return Py_BuildValue("i", debug);

  1034 }

  1035 

  1036 PyDoc_STRVAR(gc_set_thresh__doc__,

  1037 "set_threshold(threshold0, [threshold1, threshold2]) -> None\n"

  1038 "\n"

  1039 "Sets the collection thresholds.  Setting threshold0 to zero disables\n"

  1040 "collection.\n");

  1041 

  1042 static PyObject *

  1043 gc_set_thresh(PyObject *self, PyObject *args)

  1044 {

  1045 	int i;

  1046 	if (!PyArg_ParseTuple(args, "i|ii:set_threshold",

  1047 			      &generations[0].threshold,

  1048 			      &generations[1].threshold,

  1049 			      &generations[2].threshold))

  1050 		return NULL;

  1051 	for (i = 2; i < NUM_GENERATIONS; i++) {

  1052  		/* generations higher than 2 get the same threshold */

  1053 		generations[i].threshold = generations[2].threshold;

  1054 	}

  1055 

  1056 	Py_INCREF(Py_None);

  1057 	return Py_None;

  1058 }

  1059 

  1060 PyDoc_STRVAR(gc_get_thresh__doc__,

  1061 "get_threshold() -> (threshold0, threshold1, threshold2)\n"

  1062 "\n"

  1063 "Return the current collection thresholds\n");

  1064 

  1065 static PyObject *

  1066 gc_get_thresh(PyObject *self, PyObject *noargs)

  1067 {

  1068 	return Py_BuildValue("(iii)",

  1069 			     generations[0].threshold,

  1070 			     generations[1].threshold,

  1071 			     generations[2].threshold);

  1072 }

  1073 

  1074 PyDoc_STRVAR(gc_get_count__doc__,

  1075 "get_count() -> (count0, count1, count2)\n"

  1076 "\n"

  1077 "Return the current collection counts\n");

  1078 

  1079 static PyObject *

  1080 gc_get_count(PyObject *self, PyObject *noargs)

  1081 {

  1082 	return Py_BuildValue("(iii)",

  1083 			     generations[0].count,

  1084 			     generations[1].count,

  1085 			     generations[2].count);

  1086 }

  1087 

  1088 static int

  1089 referrersvisit(PyObject* obj, PyObject *objs)

  1090 {

  1091 	Py_ssize_t i;

  1092 	for (i = 0; i < PyTuple_GET_SIZE(objs); i++)

  1093 		if (PyTuple_GET_ITEM(objs, i) == obj)

  1094 			return 1;

  1095 	return 0;

  1096 }

  1097 

  1098 static int

  1099 gc_referrers_for(PyObject *objs, PyGC_Head *list, PyObject *resultlist)

  1100 {

  1101 	PyGC_Head *gc;

  1102 	PyObject *obj;

  1103 	traverseproc traverse;

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

  1105 		obj = FROM_GC(gc);

  1106 		traverse = Py_TYPE(obj)->tp_traverse;

  1107 		if (obj == objs || obj == resultlist)

  1108 			continue;

  1109 		if (traverse(obj, (visitproc)referrersvisit, objs)) {

  1110 			if (PyList_Append(resultlist, obj) < 0)

  1111 				return 0; /* error */

  1112 		}

  1113 	}

  1114 	return 1; /* no error */

  1115 }

  1116 

  1117 PyDoc_STRVAR(gc_get_referrers__doc__,

  1118 "get_referrers(*objs) -> list\n\

  1119 Return the list of objects that directly refer to any of objs.");

  1120 

  1121 static PyObject *

  1122 gc_get_referrers(PyObject *self, PyObject *args)

  1123 {

  1124 	int i;

  1125 	PyObject *result = PyList_New(0);

  1126 	if (!result) return NULL;

  1127 

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

  1129 		if (!(gc_referrers_for(args, GEN_HEAD(i), result))) {

  1130 			Py_DECREF(result);

  1131 			return NULL;

  1132 		}

  1133 	}

  1134 	return result;

  1135 }