Issue #21435: Segfault in gc with cyclic trash

Changed the iteration logic in finalize_garbage() to tolerate objects vanishing
from the list as a side effect of executing a finalizer.

3 files changed, 62 insertions, 11 deletions

diff --git a/Lib/test/test_gc.py b/Lib/test/test_gc.py
index 7eb104a6b58..c0be53795f0 100644
--- a/Lib/test/test_gc.py
+++ b/Lib/test/test_gc.py
@@ -580,6 +580,38 @@ class GCTests(unittest.TestCase):
             # would be damaged, with an empty __dict__.
             self.assertEqual(x, None)
 
+    def test_bug21435(self):
+        # This is a poor test - its only virtue is that it happened to
+        # segfault on Tim's Windows box before the patch for 21435 was
+        # applied.  That's a nasty bug relying on specific pieces of cyclic
+        # trash appearing in exactly the right order in finalize_garbage()'s
+        # input list.
+        # But there's no reliable way to force that order from Python code,
+        # so over time chances are good this test won't really be testing much
+        # of anything anymore.  Still, if it blows up, there's _some_
+        # problem ;-)
+        gc.collect()
+
+        class A:
+            pass
+
+        class B:
+            def __init__(self, x):
+                self.x = x
+
+            def __del__(self):
+                self.attr = None
+
+        def do_work():
+            a = A()
+            b = B(A())
+
+            a.attr = b
+            b.attr = a
+
+        do_work()
+        gc.collect() # this blows up (bad C pointer) when it fails
+
     @cpython_only
     def test_garbage_at_shutdown(self):
         import subprocess
diff --git a/Misc/NEWS b/Misc/NEWS
index 29634fcf407..d0d9012ffba 100644
--- a/Misc/NEWS
+++ b/Misc/NEWS
@@ -7,6 +7,13 @@ What's New in Python 3.4.1?
 
 Release date: TBA
 
+Core and Builtins
+-----------------
+
+- Issue #21435: In rare cases, when running finalizers on objects in cyclic
+  trash a bad pointer dereference could occur due to a subtle flaw in
+  internal iteration logic.
+
 Library
 -------
 
diff --git a/Modules/gcmodule.c b/Modules/gcmodule.c
index 6281a7c3433..9bb3666e1ad 100644
--- a/Modules/gcmodule.c
+++ b/Modules/gcmodule.c
@@ -776,28 +776,40 @@ handle_legacy_finalizers(PyGC_Head *finalizers, PyGC_Head *old)
     return 0;
 }
 
+/* Run first-time finalizers (if any) on all the objects in collectable.
+ * Note that this may remove some (or even all) of the objects from the
+ * list, due to refcounts falling to 0.
+ */
 static void
-finalize_garbage(PyGC_Head *collectable, PyGC_Head *old)
+finalize_garbage(PyGC_Head *collectable)
 {
     destructor finalize;
-    PyGC_Head *gc = collectable->gc.gc_next;
+    PyGC_Head seen;
+
+    /* While we're going through the loop, `finalize(op)` may cause op, or
+     * other objects, to be reclaimed via refcounts falling to zero.  So
+     * there's little we can rely on about the structure of the input
+     * `collectable` list across iterations.  For safety, we always take the
+     * first object in that list and move it to a temporary `seen` list.
+     * If objects vanish from the `collectable` and `seen` lists we don't
+     * care.
+     */
+    gc_list_init(&seen);
 
-    for (; gc != collectable; gc = gc->gc.gc_next) {
+    while (!gc_list_is_empty(collectable)) {
+        PyGC_Head *gc = collectable->gc.gc_next;
         PyObject *op = FROM_GC(gc);
-
+        gc_list_move(gc, &seen);
         if (!_PyGCHead_FINALIZED(gc) &&
-            PyType_HasFeature(Py_TYPE(op), Py_TPFLAGS_HAVE_FINALIZE) &&
-            (finalize = Py_TYPE(op)->tp_finalize) != NULL) {
+                PyType_HasFeature(Py_TYPE(op), Py_TPFLAGS_HAVE_FINALIZE) &&
+                (finalize = Py_TYPE(op)->tp_finalize) != NULL) {
             _PyGCHead_SET_FINALIZED(gc, 1);
             Py_INCREF(op);
             finalize(op);
-            if (Py_REFCNT(op) == 1) {
-                /* op will be destroyed */
-                gc = gc->gc.gc_prev;
-            }
             Py_DECREF(op);
         }
     }
+    gc_list_merge(&seen, collectable);
 }
 
 /* Walk the collectable list and check that they are really unreachable
@@ -1006,7 +1018,7 @@ collect(int generation, Py_ssize_t *n_collected, Py_ssize_t *n_uncollectable,
     m += handle_weakrefs(&unreachable, old);
 
     /* Call tp_finalize on objects which have one. */
-    finalize_garbage(&unreachable, old);
+    finalize_garbage(&unreachable);
 
     if (check_garbage(&unreachable)) {
         revive_garbage(&unreachable);