Add DTrace probes

Modules/gcmodule.c

 /*
 
   Reference Cycle Garbage Collection
   ==================================
 
   Neil Schemenauer <nas@arctrix.com>
 
   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
+
+  The following mailing list threads provide a historical perspective on
+  the design of this module.  Note that a fair amount of refinement has
+  occurred since those discussions.
+
+  http://mail.python.org/pipermail/python-dev/2000-March/002385.html
+  http://mail.python.org/pipermail/python-dev/2000-March/002434.html
+  http://mail.python.org/pipermail/python-dev/2000-March/002497.html
 
   For a highlevel view of the collection process, read the collect
   function.
 
 */
 
 #include "Python.h"
 #include "frameobject.h"        /* for PyFrame_ClearFreeList */
 
 #ifdef WITH_DTRACE
@@ skipping 32 matching lines @@
 
 /* true if we are currently running the collector */
 static int collecting = 0;
 
 /* list of uncollectable objects */
 static PyObject *garbage = NULL;
 
 /* Python string to use if unhandled exception occurs */
 static PyObject *gc_str = NULL;
 
-/* Python string used to look for __del__ attribute. */
-static PyObject *delstr = NULL;
-
-/* This is the number of objects who survived the last full collection. It
+/* a list of callbacks to be invoked when collection is performed */
+static PyObject *callbacks = NULL;
+
+/* This is the number of objects that survived the last full collection. It
    approximates the number of long lived objects tracked by the GC.
 
    (by "full collection", we mean a collection of the oldest generation).
 */
 static Py_ssize_t long_lived_total = 0;
 
-/* This is the number of objects who survived all "non-full" collections,
+/* This is the number of objects that survived all "non-full" collections,
    and are awaiting to undergo a full collection for the first time.
 
 */
 static Py_ssize_t long_lived_pending = 0;
 
 /*
    NOTE: about the counting of long-lived objects.
 
    To limit the cost of garbage collection, there are two strategies;
      - make each collection faster, e.g. by scanning fewer objects
@@ skipping 20 matching lines @@
    Using the above ratio, instead, yields amortized linear performance in
    the total number of objects (the effect of which can be summarized
    thusly: "each full garbage collection is more and more costly as the
    number of objects grows, but we do fewer and fewer of them").
 
    This heuristic was suggested by Martin von Löwis on python-dev in
    June 2008. His original analysis and proposal can be found at:
     http://mail.python.org/pipermail/python-dev/2008-June/080579.html
 */
 
+/*
+   NOTE: about untracking of mutable objects.
+   
+   Certain types of container cannot participate in a reference cycle, and
+   so do not need to be tracked by the garbage collector. Untracking these
+   objects reduces the cost of garbage collections. However, determining
+   which objects may be untracked is not free, and the costs must be
+   weighed against the benefits for garbage collection.
+
+   There are two possible strategies for when to untrack a container:
+
+   i) When the container is created.
+   ii) When the container is examined by the garbage collector.
+
+   Tuples containing only immutable objects (integers, strings etc, and
+   recursively, tuples of immutable objects) do not need to be tracked.
+   The interpreter creates a large number of tuples, many of which will
+   not survive until garbage collection. It is therefore not worthwhile
+   to untrack eligible tuples at creation time.
+
+   Instead, all tuples except the empty tuple are tracked when created. 
+   During garbage collection it is determined whether any surviving tuples 
+   can be untracked. A tuple can be untracked if all of its contents are 
+   already not tracked. Tuples are examined for untracking in all garbage 
+   collection cycles. It may take more than one cycle to untrack a tuple.
+
+   Dictionaries containing only immutable objects also do not need to be
+   tracked. Dictionaries are untracked when created. If a tracked item is
+   inserted into a dictionary (either as a key or value), the dictionary
+   becomes tracked. During a full garbage collection (all generations),
+   the collector will untrack any dictionaries whose contents are not
+   tracked.
+
+   The module provides the python function is_tracked(obj), which returns
+   the CURRENT tracking status of the object. Subsequent garbage
+   collections may change the tracking status of the object.
+   
+   Untracking of certain containers was introduced in issue #4688, and 
+   the algorithm was refined in response to issue #14775.
+*/
 
 /* 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
 static int debug;
 static PyObject *tmod = NULL;
 
 /*--------------------------------------------------------------------------
 gc_refs values.
 
 Between collections, every gc'ed object has one of two gc_refs values:
 
 GC_UNTRACKED
@@ skipping 293 matching lines @@
             traverseproc traverse = Py_TYPE(op)->tp_traverse;
             assert(gc->gc.gc_refs > 0);
             gc->gc.gc_refs = GC_REACHABLE;
             (void) traverse(op,
                             (visitproc)visit_reachable,
                             (void *)young);
             next = gc->gc.gc_next;
             if (PyTuple_CheckExact(op)) {
                 _PyTuple_MaybeUntrack(op);
             }
-            else if (PyDict_CheckExact(op)) {
-                _PyDict_MaybeUntrack(op);
-            }
         }
         else {
             /* This *may* be unreachable.  To make progress,
              * assume it is.  gc isn't directly reachable from
              * any object we've already traversed, but may be
              * reachable from an object we haven't gotten to yet.
              * visit_reachable will eventually move gc back into
              * young if that's so, and we'll see it again.
              */
             next = gc->gc.gc_next;
             gc_list_move(gc, unreachable);
             gc->gc.gc_refs = GC_TENTATIVELY_UNREACHABLE;
         }
         gc = next;
     }
 }
 
-/* Return true if object has a finalization method.
- * CAUTION:  An instance of an old-style class has to be checked for a
- *__del__ method, and earlier versions of this used to call PyObject_HasAttr,
- * which in turn could call the class's __getattr__ hook (if any).  That
- * could invoke arbitrary Python code, mutating the object graph in arbitrary
- * ways, and that was the source of some excruciatingly subtle bugs.
- */
+/* Try to untrack all currently tracked dictionaries */
+static void
+untrack_dicts(PyGC_Head *head)
+{
+    PyGC_Head *next, *gc = head->gc.gc_next;
+    while (gc != head) {
+        PyObject *op = FROM_GC(gc);
+        next = gc->gc.gc_next;
+        if (PyDict_CheckExact(op))
+            _PyDict_MaybeUntrack(op);
+        gc = next;
+    }
+}
+
+/* Return true if object has a finalization method. */
 static int
 has_finalizer(PyObject *op)
 {
-    if (PyInstance_Check(op)) {
-        assert(delstr != NULL);
-        return _PyInstance_Lookup(op, delstr) != NULL;
-    }
-    else if (PyType_HasFeature(op->ob_type, Py_TPFLAGS_HEAPTYPE))
-        return op->ob_type->tp_del != NULL;
-    else if (PyGen_CheckExact(op))
+    if (PyGen_CheckExact(op))
         return PyGen_NeedsFinalizing((PyGenObject *)op);
     else
-        return 0;
+        return op->ob_type->tp_del != NULL;
 }
 
 /* Move the objects in unreachable with __del__ methods into `finalizers`.
  * Objects moved into `finalizers` have gc_refs set to GC_REACHABLE; the
  * objects remaining in unreachable are left at GC_TENTATIVELY_UNREACHABLE.
  */
 static void
 move_finalizers(PyGC_Head *unreachable, PyGC_Head *finalizers)
 {
     PyGC_Head *gc;
@@ skipping 193 matching lines @@
             gc_list_move(gc, old);
         }
         else
             ++num_freed;
     }
 
     return num_freed;
 }
 
 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, Py_TYPE(op)->tp_name, op);
-    }
+    PySys_FormatStderr("gc: %s <%s %p>\n",
+                       msg, Py_TYPE(op)->tp_name, op);
 }
 
 /* Handle uncollectable garbage (cycles with finalizers, and stuff reachable
  * only from such cycles).
  * If DEBUG_SAVEALL, all objects in finalizers are appended to the module
  * garbage list (a Python list), else only the objects in finalizers with
  * __del__ methods are appended to garbage.  All objects in finalizers are
  * merged into the old list regardless.
  * Returns 0 if all OK, <0 on error (out of memory to grow the garbage list).
  * The finalizers list is made empty on a successful return.
@@ skipping 58 matching lines @@
  * Allocated items in the free list may keep a pymalloc arena occupied.
  * Clearing the free lists may give back memory to the OS earlier.
  */
 static void
 clear_freelists(void)
 {
     (void)PyMethod_ClearFreeList();
     (void)PyFrame_ClearFreeList();
     (void)PyCFunction_ClearFreeList();
     (void)PyTuple_ClearFreeList();
-#ifdef Py_USING_UNICODE
     (void)PyUnicode_ClearFreeList();
-#endif
-    (void)PyInt_ClearFreeList();
     (void)PyFloat_ClearFreeList();
+    (void)PyList_ClearFreeList();
+    (void)PyDict_ClearFreeList();
+    (void)PySet_ClearFreeList();
 }
 
 static double
 get_time(void)
 {
     double result = 0;
     if (tmod != NULL) {
-        PyObject *f = PyObject_CallMethod(tmod, "time", NULL);
+        _Py_IDENTIFIER(time);
+
+        PyObject *f = _PyObject_CallMethodId(tmod, &PyId_time, NULL);
         if (f == NULL) {
             PyErr_Clear();
         }
         else {
             if (PyFloat_Check(f))
                 result = PyFloat_AsDouble(f);
             Py_DECREF(f);
         }
     }
     return result;
 }
 
 /* This is the main function.  Read this to understand how the
  * collection process works. */
 static Py_ssize_t
 #ifdef WITH_DTRACE
 collect2
 #else
 collect
 #endif
-(int generation)
+(int generation, Py_ssize_t *n_collected, Py_ssize_t *n_uncollectable)
 {
     int i;
     Py_ssize_t m = 0; /* # objects collected */
     Py_ssize_t n = 0; /* # unreachable objects that couldn't be collected */
     PyGC_Head *young; /* the generation we are examining */
     PyGC_Head *old; /* next older generation */
     PyGC_Head unreachable; /* non-problematic unreachable trash */
     PyGC_Head finalizers;  /* objects with, & reachable from, __del__ */
     PyGC_Head *gc;
     double t1 = 0.0;
 
-    if (delstr == NULL) {
-        delstr = PyString_InternFromString("__del__");
-        if (delstr == NULL)
-            Py_FatalError("gc couldn't allocate \"__del__\"");
-    }
-
     if (debug & DEBUG_STATS) {
         PySys_WriteStderr("gc: collecting generation %d...\n",
                           generation);
         PySys_WriteStderr("gc: objects in each generation:");
         for (i = 0; i < NUM_GENERATIONS; i++)
             PySys_WriteStderr(" %" PY_FORMAT_SIZE_T "d",
                               gc_list_size(GEN_HEAD(i)));
         t1 = get_time();
         PySys_WriteStderr("\n");
     }
@@ skipping 34 matching lines @@
     move_unreachable(young, &unreachable);
 
     /* Move reachable objects to next generation. */
     if (young != old) {
         if (generation == NUM_GENERATIONS - 2) {
             long_lived_pending += gc_list_size(young);
         }
         gc_list_merge(young, old);
     }
     else {
+        /* We only untrack dicts in full collections, to avoid quadratic
+           dict build-up. See issue #14775. */
+        untrack_dicts(young);
         long_lived_pending = 0;
         long_lived_total = gc_list_size(young);
     }
 
     /* All objects in unreachable are trash, but objects reachable from
      * finalizers can't safely be deleted.  Python programmers should take
      * care not to create such things.  For Python, finalizers means
      * instance objects with __del__ methods.  Weakrefs with callbacks
      * can also call arbitrary Python code but they will be dealt with by
      * handle_weakrefs().
@@ skipping 58 matching lines @@
     (void)handle_finalizers(&finalizers, old);
 
     /* Clear free list only during the collection of the highest
      * generation */
     if (generation == NUM_GENERATIONS-1) {
         clear_freelists();
     }
 
     if (PyErr_Occurred()) {
         if (gc_str == NULL)
-            gc_str = PyString_FromString("garbage collection");
+            gc_str = PyUnicode_FromString("garbage collection");
         PyErr_WriteUnraisable(gc_str);
         Py_FatalError("unexpected exception during garbage collection");
     }
+
+    if (n_collected)
+        *n_collected = m;
+    if (n_uncollectable)
+        *n_uncollectable = n;
     return n+m;
 }
 
 #ifdef WITH_DTRACE
 static void
 dtrace_gc_start(int collection)
 {
     PYTHON_GC_START(collection);
 
     /*
@@ skipping 13 matching lines @@
     /*
      * Currently a USDT tail-call will not receive the correct arguments.
      * Disable the tail call here.
      */
 #if defined(__sparc)
     asm("nop");
 #endif
 }
 
 static Py_ssize_t
-collect(int collection)
+collect(int collection, Py_ssize_t *n_collected, Py_ssize_t *n_uncollectable)
 {
     Py_ssize_t value;
 
     if (PYTHON_GC_START_ENABLED())
         dtrace_gc_start(collection);
-    value = collect2(collection);
+    value = collect2(collection, n_collected, n_uncollectable);
     if (PYTHON_GC_DONE_ENABLED())
         dtrace_gc_done(value);
     return value;
 }
 #endif /* WITH_DTRACE */
+
+/* Invoke progress callbacks to notify clients that garbage collection
+ * is starting or stopping
+ */
+static void
+invoke_gc_callback(const char *phase, int generation,
+                   Py_ssize_t collected, Py_ssize_t uncollectable)
+{
+    Py_ssize_t i;
+    PyObject *info = NULL;
+
+    /* we may get called very early */
+    if (callbacks == NULL)
+        return;
+    /* The local variable cannot be rebound, check it for sanity */
+    assert(callbacks != NULL && PyList_CheckExact(callbacks));
+    if (PyList_GET_SIZE(callbacks) != 0) {
+        info = Py_BuildValue("{sisnsn}",
+            "generation", generation,
+            "collected", collected,
+            "uncollectable", uncollectable);
+        if (info == NULL) {
+            PyErr_WriteUnraisable(NULL);
+            return;
+        }
+    }
+    for (i=0; i<PyList_GET_SIZE(callbacks); i++) {
+        PyObject *r, *cb = PyList_GET_ITEM(callbacks, i);
+        Py_INCREF(cb); /* make sure cb doesn't go away */
+        r = PyObject_CallFunction(cb, "sO", phase, info);
+        Py_XDECREF(r);
+        if (r == NULL)
+            PyErr_WriteUnraisable(cb);
+        Py_DECREF(cb);
+    }
+    Py_XDECREF(info);
+}
+
+/* Perform garbage collection of a generation and invoke
+ * progress callbacks.
+ */
+static Py_ssize_t
+collect_with_callback(int generation)
+{
+    Py_ssize_t result, collected, uncollectable;
+    invoke_gc_callback("start", generation, 0, 0);
+    result = collect(generation, &collected, &uncollectable);
+    invoke_gc_callback("stop", generation, collected, uncollectable);
+    return result;
+}
 
 static Py_ssize_t
 collect_generations(void)
 {
     int i;
     Py_ssize_t n = 0;
 
     /* Find the oldest generation (highest numbered) where the count
      * exceeds the threshold.  Objects in the that generation and
      * generations younger than it will be collected. */
     for (i = NUM_GENERATIONS-1; i >= 0; i--) {
         if (generations[i].count > generations[i].threshold) {
             /* Avoid quadratic performance degradation in number
                of tracked objects. See comments at the beginning
                of this file, and issue #4074.
             */
             if (i == NUM_GENERATIONS - 1
                 && long_lived_pending < long_lived_total / 4)
                 continue;
-            n = collect(i);
+            n = collect_with_callback(i);
             break;
         }
     }
     return n;
 }
 
 PyDoc_STRVAR(gc_enable__doc__,
 "enable() -> None\n"
 "\n"
 "Enable automatic garbage collection.\n");
@@ skipping 50 matching lines @@
 
     else if (genarg < 0 || genarg >= NUM_GENERATIONS) {
         PyErr_SetString(PyExc_ValueError, "invalid generation");
         return NULL;
     }
 
     if (collecting)
         n = 0; /* already collecting, don't do anything */
     else {
         collecting = 1;
-        n = collect(genarg);
+        n = collect_with_callback(genarg);
         collecting = 0;
     }
 
-    return PyInt_FromSsize_t(n);
+    return PyLong_FromSsize_t(n);
 }
 
 PyDoc_STRVAR(gc_set_debug__doc__,
 "set_debug(flags) -> None\n"
 "\n"
 "Set the garbage collection debugging flags. Debugging information is\n"
 "written to sys.stderr.\n"
 "\n"
 "flags is an integer and can have the following bits turned on:\n"
 "\n"
 "  DEBUG_STATS - Print statistics during collection.\n"
 "  DEBUG_COLLECTABLE - Print collectable objects found.\n"
 "  DEBUG_UNCOLLECTABLE - Print unreachable but uncollectable objects found.\n"
-"  DEBUG_INSTANCES - Print instance objects.\n"
-"  DEBUG_OBJECTS - Print objects other than instances.\n"
 "  DEBUG_SAVEALL - Save objects to gc.garbage rather than freeing them.\n"
 "  DEBUG_LEAK - Debug leaking programs (everything but STATS).\n");
 
 static PyObject *
 gc_set_debug(PyObject *self, PyObject *args)
 {
     if (!PyArg_ParseTuple(args, "i:set_debug", &debug))
         return NULL;
 
     Py_INCREF(Py_None);
@@ skipping 224 matching lines @@
         METH_VARARGS | METH_KEYWORDS,           gc_collect__doc__},
     {"get_objects",    gc_get_objects,METH_NOARGS,  gc_get_objects__doc__},
     {"is_tracked",     gc_is_tracked, METH_O,       gc_is_tracked__doc__},
     {"get_referrers",  gc_get_referrers, METH_VARARGS,
         gc_get_referrers__doc__},
     {"get_referents",  gc_get_referents, METH_VARARGS,
         gc_get_referents__doc__},
     {NULL,      NULL}           /* Sentinel */
 };
 
+static struct PyModuleDef gcmodule = {
+    PyModuleDef_HEAD_INIT,
+    "gc",              /* m_name */
+    gc__doc__,         /* m_doc */
+    -1,                /* m_size */
+    GcMethods,         /* m_methods */
+    NULL,              /* m_reload */
+    NULL,              /* m_traverse */
+    NULL,              /* m_clear */
+    NULL               /* m_free */
+};
+
 PyMODINIT_FUNC
-initgc(void)
+PyInit_gc(void)
 {
     PyObject *m;
 
-    m = Py_InitModule4("gc",
-                          GcMethods,
-                          gc__doc__,
-                          NULL,
-                          PYTHON_API_VERSION);
+    m = PyModule_Create(&gcmodule);
+
     if (m == NULL)
-        return;
+        return NULL;
 
     if (garbage == NULL) {
         garbage = PyList_New(0);
         if (garbage == NULL)
-            return;
+            return NULL;
     }
     Py_INCREF(garbage);
     if (PyModule_AddObject(m, "garbage", garbage) < 0)
-        return;
+        return NULL;
+
+    if (callbacks == NULL) {
+        callbacks = PyList_New(0);
+        if (callbacks == NULL)
+            return NULL;
+    }
+    Py_INCREF(callbacks);
+    if (PyModule_AddObject(m, "callbacks", callbacks) < 0)
+        return NULL;
 
     /* Importing can't be done in collect() because collect()
      * can be called via PyGC_Collect() in Py_Finalize().
      * This wouldn't be a problem, except that <initialized> is
      * reset to 0 before calling collect which trips up
      * the import and triggers an assertion.
      */
     if (tmod == NULL) {
         tmod = PyImport_ImportModuleNoBlock("time");
         if (tmod == NULL)
             PyErr_Clear();
     }
 
-#define ADD_INT(NAME) if (PyModule_AddIntConstant(m, #NAME, NAME) < 0) return
+#define ADD_INT(NAME) if (PyModule_AddIntConstant(m, #NAME, NAME) < 0) return NULL
     ADD_INT(DEBUG_STATS);
     ADD_INT(DEBUG_COLLECTABLE);
     ADD_INT(DEBUG_UNCOLLECTABLE);
-    ADD_INT(DEBUG_INSTANCES);
-    ADD_INT(DEBUG_OBJECTS);
     ADD_INT(DEBUG_SAVEALL);
     ADD_INT(DEBUG_LEAK);
 #undef ADD_INT
+    return m;
 }
 
 /* API to invoke gc.collect() from C */
 Py_ssize_t
 PyGC_Collect(void)
 {
     Py_ssize_t n;
 
     if (collecting)
         n = 0; /* already collecting, don't do anything */
     else {
         collecting = 1;
-        n = collect(NUM_GENERATIONS - 1);
+        n = collect_with_callback(NUM_GENERATIONS - 1);
         collecting = 0;
     }
 
     return n;
+}
+
+void
+_PyGC_Fini(void)
+{
+    if (!(debug & DEBUG_SAVEALL)
+        && garbage != NULL && PyList_GET_SIZE(garbage) > 0) {
+        char *message;
+        if (debug & DEBUG_UNCOLLECTABLE)
+            message = "gc: %zd uncollectable objects at " \
+                "shutdown";
+        else
+            message = "gc: %zd uncollectable objects at " \
+                "shutdown; use gc.set_debug(gc.DEBUG_UNCOLLECTABLE) to list them";
+        if (PyErr_WarnFormat(PyExc_ResourceWarning, 0, message,
+                             PyList_GET_SIZE(garbage)) < 0)
+            PyErr_WriteUnraisable(NULL);
+        if (debug & DEBUG_UNCOLLECTABLE) {
+            PyObject *repr = NULL, *bytes = NULL;
+            repr = PyObject_Repr(garbage);
+            if (!repr || !(bytes = PyUnicode_EncodeFSDefault(repr)))
+                PyErr_WriteUnraisable(garbage);
+            else {
+                PySys_WriteStderr(
+                    "    %s\n",
+                    PyBytes_AS_STRING(bytes)
+                    );
+            }
+            Py_XDECREF(repr);
+            Py_XDECREF(bytes);
+        }
+    }
+    Py_CLEAR(callbacks);
 }
 
 /* for debugging */
 void
 _PyGC_Dump(PyGC_Head *g)
 {
     _PyObject_Dump(FROM_GC(g));
 }
 
 /* extension modules might be compiled with GC support so these
@@ skipping 98 matching lines @@
 PyObject_GC_Del(void *op)
 {
     PyGC_Head *g = AS_GC(op);
     if (IS_TRACKED(op))
         gc_list_remove(g);
     if (generations[0].count > 0) {
         generations[0].count--;
     }
     PyObject_FREE(g);
 }
-
-/* for binary compatibility with 2.2 */
-#undef _PyObject_GC_Del
-void
-_PyObject_GC_Del(PyObject *op)
-{
-    PyObject_GC_Del(op);
-}