Revert "GH-108362: Incremental Cycle GC (GH-116206)"

This reverts commit 1530932.
python · Yhg1s · Sep 30, 2024 · Sep 29, 2024 · Sep 29, 2024 · Sep 29, 2024
commit d15eace1d6165a63810dd9cca7ec502a43a699f5
diff --git a/Doc/whatsnew/3.13.rst b/Doc/whatsnew/3.13.rst
@@ -908,6 +908,7 @@ fractions
  (Contributed by Mark Dickinson in :gh:`111320`.)


+<<<<<<< HEAD
 gc
 --

@@ -938,6 +939,31 @@ may not work exactly as intended, but it is very unlikely to be harmful.
 All other code will work just fine.


+||||||| 15309329b65 (GH-108362: Incremental Cycle GC (GH-116206))
+gc
+--
+
+* The cyclic garbage collector is now incremental, which changes the meanings
+  of the results of :meth:`gc.get_threshold` and :meth:`gc.get_threshold` as
+  well as :meth:`gc.get_count` and :meth:`gc.get_stats`.
+* :meth:`gc.get_threshold` returns a three-tuple for backwards compatibility,
+  the first value is the threshold for young collections, as before, the second
+  value determines the rate at which the old collection is scanned; the
+  default is 10 and higher values mean that the old collection is scanned more slowly.
+  The third value is meangless and is always zero.
+* :meth:`gc.set_threshold` ignores any items after the second.
+* :meth:`gc.get_count` and :meth:`gc.get_stats`.
+  These functions return the same format of results as before.
+  The only difference is that instead of the results refering to
+  the young, aging and old generations, the results refer to the
+  young generation and the aging and collecting spaces of the old generation.
+
+In summary, code that attempted to manipulate the behavior of the cycle GC may
+not work exactly as intended, but it is very unlikely to harmful.
+All other code will work just fine.
+
+=======
+>>>>>>> parent of 15309329b65 (GH-108362: Incremental Cycle GC (GH-116206))
 glob
 ----


diff --git a/Include/internal/pycore_gc.h b/Include/internal/pycore_gc.h
@@ -142,14 +142,11 @@ static inline void _PyObject_GC_SET_SHARED_INLINE(PyObject *op) {

 /* Bit flags for _gc_prev */
 /* Bit 0 is set when tp_finalize is called */
-#define _PyGC_PREV_MASK_FINALIZED  1
+#define _PyGC_PREV_MASK_FINALIZED  (1)
 /* Bit 1 is set when the object is in generation which is GCed currently. */
-#define _PyGC_PREV_MASK_COLLECTING 2
-
-/* Bit 0 is set if the object belongs to old space 1 */
-#define _PyGC_NEXT_MASK_OLD_SPACE_1    1
-
-#define _PyGC_PREV_SHIFT           2
+#define _PyGC_PREV_MASK_COLLECTING (2)
+/* The (N-2) most significant bits contain the real address. */
+#define _PyGC_PREV_SHIFT           (2)
 #define _PyGC_PREV_MASK            (((uintptr_t) -1) << _PyGC_PREV_SHIFT)

 /* set for debugging information */
@@ -175,21 +172,18 @@ typedef enum {
 // Lowest bit of _gc_next is used for flags only in GC.
 // But it is always 0 for normal code.
 static inline PyGC_Head* _PyGCHead_NEXT(PyGC_Head *gc) {
-    uintptr_t next = gc->_gc_next & _PyGC_PREV_MASK;
+    uintptr_t next = gc->_gc_next;
    return (PyGC_Head*)next;
 }
 static inline void _PyGCHead_SET_NEXT(PyGC_Head *gc, PyGC_Head *next) {
-    uintptr_t unext = (uintptr_t)next;
-    assert((unext & ~_PyGC_PREV_MASK) == 0);
-    gc->_gc_next = (gc->_gc_next & ~_PyGC_PREV_MASK) | unext;
+    gc->_gc_next = (uintptr_t)next;
 }

 // Lowest two bits of _gc_prev is used for _PyGC_PREV_MASK_* flags.
 static inline PyGC_Head* _PyGCHead_PREV(PyGC_Head *gc) {
    uintptr_t prev = (gc->_gc_prev & _PyGC_PREV_MASK);
    return (PyGC_Head*)prev;
 }
-
 static inline void _PyGCHead_SET_PREV(PyGC_Head *gc, PyGC_Head *prev) {
    uintptr_t uprev = (uintptr_t)prev;
    assert((uprev & ~_PyGC_PREV_MASK) == 0);
@@ -275,13 +269,6 @@ struct gc_generation {
                  generations */
 };

-struct gc_collection_stats {
-    /* number of collected objects */
-    Py_ssize_t collected;
-    /* total number of uncollectable objects (put into gc.garbage) */
-    Py_ssize_t uncollectable;
-};
-
 /* Running stats per generation */
 struct gc_generation_stats {
    /* total number of collections */
@@ -303,8 +290,8 @@ struct _gc_runtime_state {
    int enabled;
    int debug;
    /* linked lists of container objects */
-    struct gc_generation young;
-    struct gc_generation old[2];
+    struct gc_generation generations[NUM_GENERATIONS];
+    PyGC_Head *generation0;
    /* a permanent generation which won't be collected */
    struct gc_generation permanent_generation;
    struct gc_generation_stats generation_stats[NUM_GENERATIONS];
@@ -315,11 +302,7 @@ struct _gc_runtime_state {
    /* a list of callbacks to be invoked when collection is performed */
    PyObject *callbacks;

-    Py_ssize_t work_to_do;
-    /* Which of the old spaces is the visited space */
-    int visited_space;
-
-#ifdef Py_GIL_DISABLED
+#ifndef Py_GIL_DISABLED
    /* This is the number of objects that survived the last full
       collection. It approximates the number of long lived objects
       tracked by the GC.
@@ -352,7 +335,8 @@ struct _gc_thread_state {

 extern void _PyGC_InitState(struct _gc_runtime_state *);

-extern Py_ssize_t _PyGC_Collect(PyThreadState *tstate, int generation, _PyGC_Reason reason);
+extern Py_ssize_t _PyGC_Collect(PyThreadState *tstate, int generation,
+                                _PyGC_Reason reason);
 extern void _PyGC_CollectNoFail(PyThreadState *tstate);

 /* Freeze objects tracked by the GC and ignore them in future collections. */
@@ -362,7 +346,7 @@ extern void _PyGC_Unfreeze(PyInterpreterState *interp);
 /* Number of frozen objects */
 extern Py_ssize_t _PyGC_GetFreezeCount(PyInterpreterState *interp);

-extern PyObject *_PyGC_GetObjects(PyInterpreterState *interp, Py_ssize_t generation);
+extern PyObject *_PyGC_GetObjects(PyInterpreterState *interp, int generation);
 extern PyObject *_PyGC_GetReferrers(PyInterpreterState *interp, PyObject *objs);

 // Functions to clear types free lists

diff --git a/Include/internal/pycore_object.h b/Include/internal/pycore_object.h
@@ -353,12 +353,11 @@ static inline void _PyObject_GC_TRACK(
                          filename, lineno, __func__);

    PyInterpreterState *interp = _PyInterpreterState_GET();
-    PyGC_Head *generation0 = &interp->gc.young.head;
+    PyGC_Head *generation0 = interp->gc.generation0;
    PyGC_Head *last = (PyGC_Head*)(generation0->_gc_prev);
    _PyGCHead_SET_NEXT(last, gc);
    _PyGCHead_SET_PREV(gc, last);
    _PyGCHead_SET_NEXT(gc, generation0);
-    assert((gc->_gc_next & _PyGC_NEXT_MASK_OLD_SPACE_1) == 0);
    generation0->_gc_prev = (uintptr_t)gc;
 #endif
 }

@@ -228,12 +228,12 @@ extern PyTypeObject _PyExc_MemoryError;
        }, \
        .gc = { \
            .enabled = 1, \
-            .young = { .threshold = 2000, }, \
-            .old = { \
+            .generations = { \
+                /* .head is set in _PyGC_InitState(). */ \
+                { .threshold = 2000, }, \
+                { .threshold = 10, }, \
                { .threshold = 10, }, \
-                { .threshold = 0, }, \
            }, \
-            .work_to_do = -5000, \
        }, \
        .qsbr = { \
            .wr_seq = QSBR_INITIAL, \

diff --git a/Lib/test/test_gc.py b/Lib/test/test_gc.py
@@ -392,11 +392,19 @@ def test_collect_generations(self):
        # each call to collect(N)
        x = []
        gc.collect(0)
-        # x is now in the old gen
+        # x is now in gen 1
        a, b, c = gc.get_count()
-        # We don't check a since its exact values depends on
+        gc.collect(1)
+        # x is now in gen 2
+        d, e, f = gc.get_count()
+        gc.collect(2)
+        # x is now in gen 3
+        g, h, i = gc.get_count()
+        # We don't check a, d, g since their exact values depends on
        # internal implementation details of the interpreter.
        self.assertEqual((b, c), (1, 0))
+        self.assertEqual((e, f), (0, 1))
+        self.assertEqual((h, i), (0, 0))

    def test_trashcan(self):
        class Ouch:
@@ -851,6 +859,16 @@ def test_get_objects_generations(self):
        self.assertFalse(
                any(l is element for element in gc.get_objects(generation=2))
        )
+        gc.collect(generation=1)
+        self.assertFalse(
+                any(l is element for element in gc.get_objects(generation=0))
+        )
+        self.assertFalse(
+                any(l is element for element in  gc.get_objects(generation=1))
+        )
+        self.assertTrue(
+                any(l is element for element in gc.get_objects(generation=2))
+        )
        gc.collect(generation=2)
        self.assertFalse(
                any(l is element for element in gc.get_objects(generation=0))
@@ -1088,69 +1106,6 @@ def test_get_referents_on_capsule(self):
        gc.get_referents(tracked_capsule)


-
-class IncrementalGCTests(unittest.TestCase):
-
-    def setUp(self):
-        # Reenable GC as it is disabled module-wide
-        gc.enable()
-
-    def tearDown(self):
-        gc.disable()
-
-    @requires_gil_enabled("Free threading does not support incremental GC")
-    # Use small increments to emulate longer running process in a shorter time
-    @gc_threshold(200, 10)
-    def test_incremental_gc_handles_fast_cycle_creation(self):
-
-        class LinkedList:
-
-            #Use slots to reduce number of implicit objects
-            __slots__ = "next", "prev", "surprise"
-
-            def __init__(self, next=None, prev=None):
-                self.next = next
-                if next is not None:
-                    next.prev = self
-                self.prev = prev
-                if prev is not None:
-                    prev.next = self
-
-        def make_ll(depth):
-            head = LinkedList()
-            for i in range(depth):
-                head = LinkedList(head, head.prev)
-            return head
-
-        head = make_ll(10000)
-        count = 10000
-
-        # We expect the counts to go negative eventually
-        # as there will some objects we aren't counting,
-        # e.g. the gc stats dicts. The test merely checks
-        # that the counts don't grow.
-
-        enabled = gc.isenabled()
-        gc.enable()
-        olds = []
-        for i in range(1000):
-            newhead = make_ll(200)
-            count += 200
-            newhead.surprise = head
-            olds.append(newhead)
-            if len(olds) == 50:
-                stats = gc.get_stats()
-                young = stats[0]
-                incremental = stats[1]
-                old = stats[2]
-                collected = young['collected'] + incremental['collected'] + old['collected']
-                live = count - collected
-                self.assertLess(live, 25000)
-                del olds[:]
-        if not enabled:
-            gc.disable()
-
-
 class GCCallbackTests(unittest.TestCase):
    def setUp(self):
        # Save gc state and disable it.

@@ -158,12 +158,17 @@
 {
    GCState *gcstate = get_gc_state();

-    gcstate->young.threshold = threshold0;
+    gcstate->generations[0].threshold = threshold0;
    if (group_right_1) {
-        gcstate->old[0].threshold = threshold1;
+        gcstate->generations[1].threshold = threshold1;
    }
    if (group_right_2) {
-        gcstate->old[1].threshold = threshold2;
+        gcstate->generations[2].threshold = threshold2;
+
+        /* generations higher than 2 get the same threshold */
+        for (int i = 3; i < NUM_GENERATIONS; i++) {
+            gcstate->generations[i].threshold = gcstate->generations[2].threshold;
+        }
    }
    Py_RETURN_NONE;
 }
@@ -180,9 +185,9 @@
 {
    GCState *gcstate = get_gc_state();
    return Py_BuildValue("(iii)",
-                         gcstate->young.threshold,
-                         gcstate->old[0].threshold,
-                         0);
+                         gcstate->generations[0].threshold,
+                         gcstate->generations[1].threshold,
+                         gcstate->generations[2].threshold);
 }

 /*[clinic input]
@@ -202,14 +207,14 @@
    struct _gc_thread_state *gc = &tstate->gc;

    // Flush the local allocation count to the global count
-    _Py_atomic_add_int(&gcstate->young.count, (int)gc->alloc_count);
+    _Py_atomic_add_int(&gcstate->generations[0].count, (int)gc->alloc_count);
    gc->alloc_count = 0;
 #endif

    return Py_BuildValue("(iii)",
-                         gcstate->young.count,
-                         gcstate->old[gcstate->visited_space].count,
-                         gcstate->old[gcstate->visited_space^1].count);
+                         gcstate->generations[0].count,
+                         gcstate->generations[1].count,
+                         gcstate->generations[2].count);
 }

 /*[clinic input]
@@ -326,7 +331,7 @@
    }

    PyInterpreterState *interp = _PyInterpreterState_GET();
    return _PyGC_GetObjects(interp, generation);
 }

 /*[clinic input]