Trashcan cleanup: Now that cyclic gc is always there, the trashcan

mechanism is no longer evil:  it no longer plays dangerous games with
the type pointer or refcounts, and objects in extension modules can play
along too without needing to edit the core first.

Rewrote all the comments to explain this, and (I hope) give clear
guidance to extension authors who do want to play along.  Documented
all the functions.  Added more asserts (it may no longer be evil, but
it's still dangerous <0.9 wink>).  Rearranged the generated code to
make it clearer, and to tolerate either the presence or absence of a
semicolon after the macros.  Rewrote _PyTrash_destroy_chain() to call
tp_dealloc directly; it was doing a Py_DECREF again, and that has all
sorts of obscure distorting effects in non-release builds (Py_DECREF
was already called on the object!).  Removed Christian's little "embedded
change log" comments -- that's what checkin messages are for, and since
it was impossible to correlate the comments with the code that changed,
I found them merely distracting.

3 files changed, 96 insertions, 100 deletions

diff --git a/Include/object.h b/Include/object.h
index 7bb1eac..a0997f2 100644
--- a/Include/object.h
+++ b/Include/object.h
@@ -76,7 +76,7 @@ whose size is determined when the object is allocated.
 #define PyObject_VAR_HEAD \
 	PyObject_HEAD \
 	int ob_size; /* Number of items in variable part */
- 
+
 typedef struct _object {
 	PyObject_HEAD
 } PyObject;
@@ -197,7 +197,7 @@ typedef struct {
 	getsegcountproc bf_getsegcount;
 	getcharbufferproc bf_getcharbuffer;
 } PyBufferProcs;
-	
+
 
 typedef void (*freefunc)(void *);
 typedef void (*destructor)(PyObject *);
@@ -222,18 +222,18 @@ typedef struct _typeobject {
 	PyObject_VAR_HEAD
 	char *tp_name; /* For printing, in format "<module>.<name>" */
 	int tp_basicsize, tp_itemsize; /* For allocation */
-	
+
 	/* Methods to implement standard operations */
-	
+
 	destructor tp_dealloc;
 	printfunc tp_print;
 	getattrfunc tp_getattr;
 	setattrfunc tp_setattr;
 	cmpfunc tp_compare;
 	reprfunc tp_repr;
-	
+
 	/* Method suites for standard classes */
-	
+
 	PyNumberMethods *tp_as_number;
 	PySequenceMethods *tp_as_sequence;
 	PyMappingMethods *tp_as_mapping;
@@ -248,7 +248,7 @@ typedef struct _typeobject {
 
 	/* Functions to access object as input/output buffer */
 	PyBufferProcs *tp_as_buffer;
-	
+
 	/* Flags to define presence of optional/expanded features */
 	long tp_flags;
 
@@ -257,7 +257,7 @@ typedef struct _typeobject {
 	/* Assigned meaning in release 2.0 */
 	/* call function for all accessible objects */
 	traverseproc tp_traverse;
-	
+
 	/* delete references to contained objects */
 	inquiry tp_clear;
 
@@ -654,58 +654,61 @@ it carefully, it may save lots of calls to Py_INCREF() and Py_DECREF() at
 times.
 */
 
-/*
-  trashcan
-  CT 2k0130
-  non-recursively destroy nested objects
-
-  CT 2k0223
-  redefinition for better locality and less overhead.
-
-  Objects that want to be recursion safe need to use
-  the macro's 
-		Py_TRASHCAN_SAFE_BEGIN(name)
-  and
-		Py_TRASHCAN_SAFE_END(name)
-  surrounding their actual deallocation code.
-
-  It would be nice to do this using the thread state.
-  Also, we could do an exact stack measure then.
-  Unfortunately, deallocations also take place when
-  the thread state is undefined.
-
-  CT 2k0422 complete rewrite.
-  There is no need to allocate new objects.
-  Everything is done vialob_refcnt and ob_type now.
-  Adding support for free-threading should be easy, too.
-*/
 
-#define PyTrash_UNWIND_LEVEL 50
+/* Trashcan mechanism, thanks to Christian Tismer.
 
-#define Py_TRASHCAN_SAFE_BEGIN(op) \
-	{ \
-		++_PyTrash_delete_nesting; \
-		if (_PyTrash_delete_nesting < PyTrash_UNWIND_LEVEL) { \
+When deallocating a container object, it's possible to trigger an unbounded
+chain of deallocations, as each Py_DECREF in turn drops the refcount on "the
+next" object in the chain to 0.  This can easily lead to stack faults, and
+especially in threads (which typically have less stack space to work with).
 
-#define Py_TRASHCAN_SAFE_END(op) \
-		;} \
-		else \
-			_PyTrash_deposit_object((PyObject*)op);\
-		--_PyTrash_delete_nesting; \
-		if (_PyTrash_delete_later && _PyTrash_delete_nesting <= 0) \
-			_PyTrash_destroy_chain(); \
-	} \
+A container object that participates in cyclic gc can avoid this by
+bracketing the body of its tp_dealloc function with a pair of macros:
+
+static void
+mytype_dealloc(mytype *p)
+{
+        ... declarations go here ...
+
+ 	PyObject_GC_UnTrack(p);	   // must untrack first
+	Py_TRASHCAN_SAFE_BEGIN(p)
+	... The body of the deallocator goes here, including all calls ...
+	... to Py_DECREF on contained objects.                         ...
+	Py_TRASHCAN_SAFE_END(p)
+}
+
+How it works:  The BEGIN macro increments a call-depth counter.  So long
+as this counter is small, the body of the deallocator is run directly without
+further ado.  But if the counter gets large, it instead adds p to a list of
+objects to be deallocated later, skips the body of the deallocator, and
+resumes execution after the END macro.  The tp_dealloc routine then returns
+without deallocating anything (and so unbounded call-stack depth is avoided).
+
+When the call stack finishes unwinding again, code generated by the END macro
+notices this, and calls another routine to deallocate all the objects that
+may have been added to the list of deferred deallocations.  In effect, a
+chain of N deallocations is broken into N / PyTrash_UNWIND_LEVEL pieces,
+with the call stack never exceeding a depth of PyTrash_UNWIND_LEVEL.
+*/
 
 extern DL_IMPORT(void) _PyTrash_deposit_object(PyObject*);
 extern DL_IMPORT(void) _PyTrash_destroy_chain(void);
-
 extern DL_IMPORT(int) _PyTrash_delete_nesting;
 extern DL_IMPORT(PyObject *) _PyTrash_delete_later;
 
-/* swap the "xx" to check the speed loss */
+#define PyTrash_UNWIND_LEVEL 50
 
-#define xxPy_TRASHCAN_SAFE_BEGIN(op) 
-#define xxPy_TRASHCAN_SAFE_END(op) ;
+#define Py_TRASHCAN_SAFE_BEGIN(op) \
+	if (_PyTrash_delete_nesting < PyTrash_UNWIND_LEVEL) { \
+		++_PyTrash_delete_nesting;
+		/* The body of the deallocator is here. */
+#define Py_TRASHCAN_SAFE_END(op) \
+		--_PyTrash_delete_nesting; \
+		if (_PyTrash_delete_later && _PyTrash_delete_nesting <= 0) \
+			_PyTrash_destroy_chain(); \
+	} \
+	else \
+		_PyTrash_deposit_object((PyObject*)op);
 
 #ifdef __cplusplus
 }
diff --git a/Modules/gcmodule.c b/Modules/gcmodule.c
index 5685101..e0c7631 100644
--- a/Modules/gcmodule.c
+++ b/Modules/gcmodule.c
@@ -963,6 +963,9 @@ _PyObject_GC_Track(PyObject *op)
 void
 PyObject_GC_UnTrack(void *op)
 {
+	/* Obscure:  the Py_TRASHCAN mechanism requires that we be able to
+	 * call PyObject_GC_UnTrack twice on an object.
+	 */
 	if (IS_TRACKED(op))
 		_PyObject_GC_UNTRACK(op);
 }
diff --git a/Objects/object.c b/Objects/object.c
index 8d670c9..6a77e88 100644
--- a/Objects/object.c
+++ b/Objects/object.c
@@ -192,7 +192,7 @@ PyObject_Print(PyObject *op, FILE *fp, int flags)
 }
 
 /* For debugging convenience.  See Misc/gdbinit for some useful gdb hooks */
-void _PyObject_Dump(PyObject* op) 
+void _PyObject_Dump(PyObject* op)
 {
 	if (op == NULL)
 		fprintf(stderr, "NULL\n");
@@ -256,7 +256,7 @@ PyObject *
 PyObject_Str(PyObject *v)
 {
 	PyObject *res;
-	
+
 	if (v == NULL)
 		return PyString_FromString("<NULL>");
 	if (PyString_CheckExact(v)) {
@@ -295,7 +295,7 @@ PyObject *
 PyObject_Unicode(PyObject *v)
 {
 	PyObject *res;
-	
+
 	if (v == NULL)
 		res = PyString_FromString("<NULL>");
 	if (PyUnicode_CheckExact(v)) {
@@ -699,9 +699,9 @@ get_inprogress_dict(void)
 	if (tstate_dict == NULL) {
 		PyErr_BadInternalCall();
 		return NULL;
-	} 
+	}
 
-	inprogress = PyDict_GetItem(tstate_dict, key); 
+	inprogress = PyDict_GetItem(tstate_dict, key);
 	if (inprogress == NULL) {
 		inprogress = PyDict_New();
 		if (inprogress == NULL)
@@ -848,7 +848,7 @@ convert_3way_to_object(int op, int c)
 	Py_INCREF(result);
 	return result;
 }
-	
+
 /* We want a rich comparison but don't have one.  Try a 3-way cmp instead.
    Return
    NULL      if error
@@ -1063,13 +1063,13 @@ _Py_HashPointer(void *p)
 	/* convert to a Python long and hash that */
 	PyObject* longobj;
 	long x;
-	
+
 	if ((longobj = PyLong_FromVoidPtr(p)) == NULL) {
 		x = -1;
 		goto finally;
 	}
 	x = PyObject_Hash(longobj);
-	
+
 finally:
 	Py_XDECREF(longobj);
 	return x;
@@ -1195,7 +1195,7 @@ PyObject_SetAttr(PyObject *v, PyObject *name, PyObject *value)
 			if (name == NULL)
 				return -1;
 		}
-		else 
+		else
 #endif
 		{
 			PyErr_SetString(PyExc_TypeError,
@@ -1285,7 +1285,7 @@ PyObject_GenericGetAttr(PyObject *obj, PyObject *name)
 			if (name == NULL)
 				return NULL;
 		}
-		else 
+		else
 #endif
 		{
 			PyErr_SetString(PyExc_TypeError,
@@ -1361,7 +1361,7 @@ PyObject_GenericSetAttr(PyObject *obj, PyObject *name, PyObject *value)
 			if (name == NULL)
 				return -1;
 		}
-		else 
+		else
 #endif
 		{
 			PyErr_SetString(PyExc_TypeError,
@@ -1450,7 +1450,7 @@ PyObject_IsTrue(PyObject *v)
 	return (res > 0) ? 1 : res;
 }
 
-/* equivalent of 'not v' 
+/* equivalent of 'not v'
    Return -1 if an error occurred */
 
 int
@@ -1758,7 +1758,7 @@ none_repr(PyObject *op)
 
 /* ARGUSED */
 static void
-none_dealloc(PyObject* ignore) 
+none_dealloc(PyObject* ignore)
 {
 	/* This should never get called, but we also don't want to SEGV if
 	 * we accidently decref None out of existance.
@@ -2042,62 +2042,52 @@ Py_ReprLeave(PyObject *obj)
 	}
 }
 
-/*
-  trashcan
-  CT 2k0130
-  non-recursively destroy nested objects
-
-  CT 2k0223
-  everything is now done in a macro.
-
-  CT 2k0305
-  modified to use functions, after Tim Peter's suggestion.
-
-  CT 2k0309
-  modified to restore a possible error.
-
-  CT 2k0325
-  added better safe than sorry check for threadstate
-
-  CT 2k0422
-  complete rewrite. We now build a chain via ob_type
-  and save the limited number of types in ob_refcnt.
-  This is perfect since we don't need any memory.
-  A patch for free-threading would need just a lock.
-*/
-
-#define Py_TRASHCAN_TUPLE       1
-#define Py_TRASHCAN_LIST        2
-#define Py_TRASHCAN_DICT        3
-#define Py_TRASHCAN_FRAME       4
-#define Py_TRASHCAN_TRACEBACK   5
-/* extend here if other objects want protection */
+/* Trashcan support. */
 
+/* Current call-stack depth of tp_dealloc calls. */
 int _PyTrash_delete_nesting = 0;
 
-PyObject * _PyTrash_delete_later = NULL;
+/* List of objects that still need to be cleaned up, singly linked via their
+ * gc headers' gc_prev pointers.
+ */
+PyObject *_PyTrash_delete_later = NULL;
 
+/* Add op to the _PyTrash_delete_later list.  Called when the current
+ * call-stack depth gets large.  op must be a currently untracked gc'ed
+ * object, with refcount 0.  Py_DECREF must already have been called on it.
+ */
 void
 _PyTrash_deposit_object(PyObject *op)
 {
-	assert (_Py_AS_GC(op)->gc.gc_next == NULL);
+	assert(PyObject_IS_GC(op));
+	assert(_Py_AS_GC(op)->gc.gc_refs == _PyGC_REFS_UNTRACKED);
+	assert(op->ob_refcnt == 0);
 	_Py_AS_GC(op)->gc.gc_prev = (PyGC_Head *)_PyTrash_delete_later;
 	_PyTrash_delete_later = op;
 }
 
+/* Dealloccate all the objects in the _PyTrash_delete_later list.  Called when
+ * the call-stack unwinds again.
+ */
 void
 _PyTrash_destroy_chain(void)
 {
 	while (_PyTrash_delete_later) {
-		PyObject *shredder = _PyTrash_delete_later;
+		PyObject *op = _PyTrash_delete_later;
+		destructor dealloc = op->ob_type->tp_dealloc;
 
 		_PyTrash_delete_later =
-			(PyObject*) _Py_AS_GC(shredder)->gc.gc_prev;
-
-		_Py_NewReference(shredder);
+			(PyObject*) _Py_AS_GC(op)->gc.gc_prev;
 
+		/* Call the deallocator directly.  This used to try to
+		 * fool Py_DECREF into calling it indirectly, but
+		 * Py_DECREF was already called on this object, and in
+		 * assorted non-release builds calling Py_DECREF again ends
+		 * up distorting allocation statistics.
+		 */
+		assert(op->ob_refcnt == 0);
 		++_PyTrash_delete_nesting;
-		Py_DECREF(shredder);
+		(*dealloc)(op);
 		--_PyTrash_delete_nesting;
 	}
 }