gcmodule.c

python s60 1.4.5版本的源代码

/* Portions Copyright (c) 2005 Nokia Corporation */
/*

  Reference Cycle Garbage Collection
  ==================================

  Neil Schemenauer <[e-mail]>

  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"

#ifdef WITH_CYCLE_GC

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

#ifdef SYMBIAN
typedef struct {
  PyGC_Head generation0;
  PyGC_Head f_generation1;
  PyGC_Head f_generation2;
  int f_generation;
  int f_enabled;
  int f_threshold0;
  int f_threshold1;
  int f_threshold2;
  int f_allocated;
  int f_collecting;
  int f_debug;
  PyObject *f_garbage;
  PyObject *f_gc_str;
  PyObject *has_finalizer_delstr;
  long collect_generations_collections0;
  long collect_generations_collections1;
} GcGlobals;

#define GC_GLOBALS ((GcGlobals*)(PYTHON_GLOBALS->gc_globals))

static void init_gc_globals()
{
  /* Memory gets freed when the memory pool is destroyed */
  GcGlobals *gb = PyMem_Malloc(sizeof(GcGlobals));
  gb->generation0.gc.gc_next = &(gb->generation0);
  gb->generation0.gc.gc_prev = &(gb->generation0);
  gb->generation0.gc.gc_refs = 0;
  gb->f_generation1.gc.gc_next = &(gb->f_generation1);
  gb->f_generation1.gc.gc_prev = &(gb->f_generation1);
  gb->f_generation1.gc.gc_refs = 0;
  gb->f_generation2.gc.gc_next = &(gb->f_generation2);
  gb->f_generation2.gc.gc_prev = &(gb->f_generation2);
  gb->f_generation2.gc.gc_refs = 0;
  gb->f_generation = 0;
  gb->f_enabled = 0;
  gb->f_threshold0 = 700;
  gb->f_threshold1 = 10;
  gb->f_threshold2 = 10;
  gb->f_allocated = 0;
  gb->f_collecting = 0;
  gb->f_debug = 0;
  gb->f_garbage = NULL;
  gb->f_gc_str = NULL;
  gb->has_finalizer_delstr = NULL;
  gb->collect_generations_collections0 = 0;
  gb->collect_generations_collections1 = 0;
  PYTHON_GLOBALS->gc_globals = gb;
}
#endif

/*** Global GC state ***/

/* linked lists of container objects */
#ifndef SYMBIAN
PyGC_Head _PyGC_generation0 = {{&_PyGC_generation0, &_PyGC_generation0, 0}};
static PyGC_Head generation1 = {{&generation1, &generation1, 0}};
static PyGC_Head generation2 = {{&generation2, &generation2, 0}};
static int generation = 0; /* current generation being collected */
#else
#define generation1 (GC_GLOBALS->f_generation1)
#define generation2 (GC_GLOBALS->f_generation2)
#define generation (GC_GLOBALS->f_generation)
#endif
/* collection frequencies, XXX tune these */
#ifndef SYMBIAN
static int enabled = 1; /* automatic collection enabled? */
static int threshold0 = 700; /* net new containers before collection */
static int threshold1 = 10;  /* generation0 collections before collecting 1 */
static int threshold2 = 10;  /* generation1 collections before collecting 2 */
#else
#define enabled (GC_GLOBALS->f_enabled)
#define threshold0 (GC_GLOBALS->f_threshold0)
#define threshold1 (GC_GLOBALS->f_threshold1)
#define threshold2 (GC_GLOBALS->f_threshold2)
#endif

/* net new objects allocated since last collection */
#ifndef SYMBIAN
static int allocated;
#else
#define allocated (GC_GLOBALS->f_allocated)
#endif

/* true if we are currently running the collector */
#ifndef SYMBIAN
static int collecting;
#else
#define collecting (GC_GLOBALS->f_collecting)
#endif

/* 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
#ifndef SYMBIAN
static int debug;
#else
#define debug (GC_GLOBALS->f_debug)
#endif

/* When a collection begins, gc_refs is set to ob_refcnt for, and only for,
 * the objects in the generation being collected, called the "young"
 * generation at that point.  As collection proceeds, when it's determined
 * that one of these can't be collected (e.g., because it's reachable from
 * outside, or has a __del__ method), the object is moved out of young, and
 * gc_refs is set to a negative value.  The latter is so we can distinguish
 * collection candidates from non-candidates just by looking at the object.
 */
/* Special gc_refs value, although any negative value means "moved". */
#define GC_MOVED  -123

/* True iff an object is still a candidate for collection. */
#define STILL_A_CANDIDATE(o) ((AS_GC(o))->gc.gc_refs >= 0)

/* list of uncollectable objects */
#ifndef SYMBIAN
static PyObject *garbage;
#else
#define garbage (GC_GLOBALS->f_garbage)
#endif

/* Python string to use if unhandled exception occurs */
#ifndef SYMBIAN
static PyObject *gc_str;
#else
#define gc_str (GC_GLOBALS->f_gc_str)
#endif

/*** list functions ***/

static void
gc_list_init(PyGC_Head *list)
{
	list->gc.gc_prev = list;
	list->gc.gc_next = 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;
}

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 *from, PyGC_Head *to)
{
	if (from->gc.gc_next == from) {
		/* empty from list */
		gc_list_init(to);
	}
	else {
		to->gc.gc_next = from->gc.gc_next;
		to->gc.gc_next->gc.gc_prev = to;
		to->gc.gc_prev = from->gc.gc_prev;
		to->gc.gc_prev->gc.gc_next = to;
	}
	gc_list_init(from);
}

/* append a list onto another list, from becomes an empty list */
static void
gc_list_merge(PyGC_Head *from, PyGC_Head *to)
{
	PyGC_Head *tail;
	if (from->gc.gc_next != 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 long
gc_list_size(PyGC_Head *list)
{
	PyGC_Head *gc;
	long n = 0;
	for (gc = list->gc.gc_next; gc != list; gc = gc->gc.gc_next) {
		n++;
	}
	return n;
}

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



/* Set all gc_refs = ob_refcnt.  After this, STILL_A_CANDIDATE(o) is true
 * for all objects in containers, and false for all tracked gc objects not
 * in containers (although see the comment in visit_decref).
 */
static void
update_refs(PyGC_Head *containers)
{
	PyGC_Head *gc = containers->gc.gc_next;
	for (; gc != containers; gc=gc->gc.gc_next) {
		gc->gc.gc_refs = FROM_GC(gc)->ob_refcnt;
	}
}

static int
visit_decref(PyObject *op, void *data)
{
        /* There's no point to decrementing gc_refs unless
         * STILL_A_CANDIDATE(op) is true.  It would take extra cycles to
         * check that, though.  If STILL_A_CANDIDATE(op) is false,
         * decrementing gc_refs almost always makes it "even more negative",
         * so doesn't change that STILL_A_CANDIDATE is false, and no harm is
         * done.  However, it's possible that, after many collections, this
         * could underflow gc_refs in a long-lived old object.  In that case,
         * visit_move() may move the old object back to the generation
         * getting collected.  That would be a waste of time, but wouldn't
         * cause an error.
         */
	if (op && PyObject_IS_GC(op)) {
		PyGC_Head *gc = AS_GC(op);
		if (gc->gc.gc_next != NULL)
			AS_GC(op)->gc.gc_refs--;
	}
	return 0;
}

/* Subtract internal references from gc_refs */
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 = FROM_GC(gc)->ob_type->tp_traverse;
		(void) traverse(FROM_GC(gc),
			       (visitproc)visit_decref,
			       NULL);
	}
}

/* Move objects with gc_refs > 0 to roots list.  They can't be collected. */
static void
move_roots(PyGC_Head *containers, PyGC_Head *roots)
{
	PyGC_Head *next;
	PyGC_Head *gc = containers->gc.gc_next;
	while (gc != containers) {
		next = gc->gc.gc_next;
		if (gc->gc.gc_refs > 0) {
			gc_list_remove(gc);
			gc_list_append(gc, roots);
			gc->gc.gc_refs = GC_MOVED;
		}
		gc = next;
	}
}

static int
visit_move(PyObject *op, PyGC_Head *tolist)
{
	if (PyObject_IS_GC(op)) {
		PyGC_Head *gc = AS_GC(op);
		if (gc->gc.gc_next != NULL && STILL_A_CANDIDATE(op)) {
			gc_list_remove(gc);
			gc_list_append(gc, tolist);
			gc->gc.gc_refs = GC_MOVED;
		}
	}
	return 0;
}

/* Move candidates referenced from reachable to reachable set (they're no
 * longer candidates).
 */
static void
move_root_reachable(PyGC_Head *reachable)
{
	traverseproc traverse;
	PyGC_Head *gc = reachable->gc.gc_next;
	for (; gc != reachable; gc=gc->gc.gc_next) {
		/* careful, reachable list is growing here */
		PyObject *op = FROM_GC(gc);
		traverse = op->ob_type->tp_traverse;
		(void) traverse(op,
			       (visitproc)visit_move,
			       (void *)reachable);
	}
}

/* return true if object has a finalization method */
static int
has_finalizer(PyObject *op)
{
#ifndef SYMBIAN
	static PyObject *delstr = NULL;
#else
#define delstr (GC_GLOBALS->has_finalizer_delstr)
#endif
	if (delstr == NULL) {
		delstr = PyString_InternFromString("__del__");
		if (delstr == NULL)
			Py_FatalError("PyGC: can't initialize __del__ string");
	}
	return (PyInstance_Check(op) ||
	        PyType_HasFeature(op->ob_type, Py_TPFLAGS_HEAPTYPE))
	       && PyObject_HasAttr(op, delstr);
}

/* Move all objects with finalizers (instances with __del__) */
static void
move_finalizers(PyGC_Head *unreachable, PyGC_Head *finalizers)
{
	PyGC_Head *next;
	PyGC_Head *gc = unreachable->gc.gc_next;
	for (; gc != unreachable; gc=next) {
		PyObject *op = FROM_GC(gc);
		next = gc->gc.gc_next;
		if (has_finalizer(op)) {
			gc_list_remove(gc);
			gc_list_append(gc, finalizers);
			gc->gc.gc_refs = GC_MOVED;
		}
	}
}

/* Move objects referenced from roots to roots */
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) {
		/* careful, finalizers list is growing here */
		traverse = FROM_GC(gc)->ob_type->tp_traverse;
		(void) traverse(FROM_GC(gc),
			       (visitproc)visit_move,
			       (void *)finalizers);
	}
}

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, op->ob_type->tp_name, op);
	}
}

/* Handle uncollectable garbage (cycles with finalizers). */
static void
handle_finalizers(PyGC_Head *finalizers, PyGC_Head *old)
{
	PyGC_Head *gc;
	if (garbage == NULL) {
		garbage = PyList_New(0);
	}
	for (gc = finalizers->gc.gc_next; gc != finalizers;
			gc = finalizers->gc.gc_next) {
		PyObject *op = FROM_GC(gc);
		if ((debug & DEBUG_SAVEALL) || has_finalizer(op)) {
			/* If SAVEALL is not set then just append objects with
			 * finalizers to the list of garbage.  All objects in
			 * the finalizers list are reachable from those
			 * objects. */
			PyList_Append(garbage, op);
		}
		/* object is now reachable again */
		assert(!STILL_A_CANDIDATE(op));
		gc_list_remove(gc);
		gc_list_append(gc, old);
	}
}

/* Break reference cycles by clearing the containers involved.	This is
 * tricky business as the lists can be changing and we don't know which
 * objects may be freed.  It is possible I screwed something up here. */
static void
delete_garbage(PyGC_Head *unreachable, PyGC_Head *old)
{
	inquiry clear;

	while (unreachable->gc.gc_next != unreachable) {
		PyGC_Head *gc = unreachable->gc.gc_next;
		PyObject *op = FROM_GC(gc);

		assert(STILL_A_CANDIDATE(op));
		if (debug & DEBUG_SAVEALL) {
			PyList_Append(garbage, op);
		}
		else {
			if ((clear = op->ob_type->tp_clear) != NULL) {
				Py_INCREF(op);
				clear((PyObject *)op);
				Py_DECREF(op);
			}
		}
		if (unreachable->gc.gc_next == gc) {
			/* object is still alive, move it, it may die later */
			gc_list_remove(gc);
			gc_list_append(gc, old);
			gc->gc.gc_refs = GC_MOVED;
		}
	}
}

/* This is the main function.  Read this to understand how the
 * collection process works. */
static long
collect(PyGC_Head *young, PyGC_Head *old)
{
	long n = 0;
	long m = 0;
	PyGC_Head reachable;
	PyGC_Head unreachable;
	PyGC_Head finalizers;
	PyGC_Head *gc;

	if (debug & DEBUG_STATS) {
		PySys_WriteStderr(
			"gc: collecting generation %d...\n"
			"gc: objects in each generation: %ld %ld %ld\n",
			generation,
			gc_list_size(&_PyGC_generation0),
			gc_list_size(&generation1),
			gc_list_size(&generation2));
	}

	/* Using ob_refcnt and gc_refs, calculate which objects in the
	 * container set are reachable from outside the set (ie. have a
	 * refcount greater than 0 when all the references within the
	 * set are taken into account */
	update_refs(young);
	subtract_refs(young);

	/* Move everything reachable from outside the set into the
	 * reachable set (ie. gc_refs > 0).  Next, move everything
	 * reachable from objects in the reachable set. */
	gc_list_init(&reachable);
	move_roots(young, &reachable);
	move_root_reachable(&reachable);

	/* move unreachable objects to a temporary list, new objects can be
	 * allocated after this point */
	gc_list_init(&unreachable);
	gc_list_move(young, &unreachable);

	/* move reachable objects to next generation */
	gc_list_merge(&reachable, old);

	/* Move objects reachable from finalizers, we can't safely delete
	 * them.  Python programmers should take care not to create such
	 * things.  For Python finalizers means instance objects with
	 * __del__ methods. */
	gc_list_init(&finalizers);
	move_finalizers(&unreachable, &finalizers);
	move_finalizer_reachable(&finalizers);

	/* Collect statistics on collectable objects found and print
	 * debugging information. */
	for (gc = unreachable.gc.gc_next; gc != &unreachable;
			gc = gc->gc.gc_next) {
		m++;
		if (debug & DEBUG_COLLECTABLE) {