LCOV - code coverage report
Current view: | top level - Modules - gcmodule.c (source / functions) |  |  | Hit | Total | Coverage
Test: | CPython 3.12 LCOV report [commit 5e6661bce9] |  | Lines: | 460 | 759 | 60.6 %
Date: | 2023-03-20 08:15:36 |  | Functions: | 56 | 89 | 62.9 %
|  |  | Branches: | 150 | 342 | 43.9 %

               Branch data     Line data    Source code
           1                 :            : /*
           2                 :            :
           3                 :            :   Reference Cycle Garbage Collection
           4                 :            :   ==================================
           5                 :            :
           6                 :            :   Neil Schemenauer <nas@arctrix.com>
           7                 :            :
           8                 :            :   Based on a post on the python-dev list.  Ideas from Guido van Rossum,
           9                 :            :   Eric Tiedemann, and various others.
          10                 :            :
          11                 :            :   http://www.arctrix.com/nas/python/gc/
          12                 :            :
          13                 :            :   The following mailing list threads provide a historical perspective on
          14                 :            :   the design of this module.  Note that a fair amount of refinement has
          15                 :            :   occurred since those discussions.
          16                 :            :
          17                 :            :   http://mail.python.org/pipermail/python-dev/2000-March/002385.html
          18                 :            :   http://mail.python.org/pipermail/python-dev/2000-March/002434.html
          19                 :            :   http://mail.python.org/pipermail/python-dev/2000-March/002497.html
          20                 :            :
          21                 :            :   For a highlevel view of the collection process, read the collect
          22                 :            :   function.
          23                 :            :
          24                 :            : */
          25                 :            :
          26                 :            : #include "Python.h"
          27                 :            : #include "pycore_context.h"
          28                 :            : #include "pycore_initconfig.h"
          29                 :            : #include "pycore_interp.h"      // PyInterpreterState.gc
          30                 :            : #include "pycore_object.h"
          31                 :            : #include "pycore_pyerrors.h"
          32                 :            : #include "pycore_pystate.h"     // _PyThreadState_GET()
          33                 :            : #include "pydtrace.h"
          34                 :            :
          35                 :            : typedef struct _gc_runtime_state GCState;
          36                 :            :
          37                 :            : /*[clinic input]
          38                 :            : module gc
          39                 :            : [clinic start generated code]*/
          40                 :            : /*[clinic end generated code: output=da39a3ee5e6b4b0d input=b5c9690ecc842d79]*/
          41                 :            :
          42                 :            :
          43                 :            : #ifdef Py_DEBUG
          44                 :            : #  define GC_DEBUG
          45                 :            : #endif
          46                 :            :
          47                 :            : #define GC_NEXT _PyGCHead_NEXT
          48                 :            : #define GC_PREV _PyGCHead_PREV
          49                 :            :
          50                 :            : // update_refs() set this bit for all objects in current generation.
          51                 :            : // subtract_refs() and move_unreachable() uses this to distinguish
          52                 :            : // visited object is in GCing or not.
          53                 :            : //
          54                 :            : // move_unreachable() removes this flag from reachable objects.
          55                 :            : // Only unreachable objects have this flag.
          56                 :            : //
          57                 :            : // No objects in interpreter have this flag after GC ends.
          58                 :            : #define PREV_MASK_COLLECTING   _PyGC_PREV_MASK_COLLECTING
          59                 :            :
          60                 :            : // Lowest bit of _gc_next is used for UNREACHABLE flag.
          61                 :            : //
          62                 :            : // This flag represents the object is in unreachable list in move_unreachable()
          63                 :            : //
          64                 :            : // Although this flag is used only in move_unreachable(), move_unreachable()
          65                 :            : // doesn't clear this flag to skip unnecessary iteration.
          66                 :            : // move_legacy_finalizers() removes this flag instead.
          67                 :            : // Between them, unreachable list is not normal list and we can not use
          68                 :            : // most gc_list_* functions for it.
          69                 :            : #define NEXT_MASK_UNREACHABLE  (1)
          70                 :            :
          71                 :            : /* Get an object's GC head */
          72                 :            : #define AS_GC(o) ((PyGC_Head *)(((char *)(o))-sizeof(PyGC_Head)))
          73                 :            :
          74                 :            : /* Get the object given the GC head */
          75                 :            : #define FROM_GC(g) ((PyObject *)(((char *)(g))+sizeof(PyGC_Head)))
          76                 :            :
          77                 :            : static inline int
          78                 :    6028829 : gc_is_collecting(PyGC_Head *g)
          79                 :            : {
          80                 :    6028829 :     return (g->_gc_prev & PREV_MASK_COLLECTING) != 0;
          81                 :            : }
          82                 :            :
          83                 :            : static inline void
          84                 :    1463100 : gc_clear_collecting(PyGC_Head *g)
          85                 :            : {
          86                 :    1463100 :     g->_gc_prev &= ~PREV_MASK_COLLECTING;
          87                 :    1463100 : }
          88                 :            :
          89                 :            : static inline Py_ssize_t
          90                 :    4869431 : gc_get_refs(PyGC_Head *g)
          91                 :            : {
          92                 :    4869431 :     return (Py_ssize_t)(g->_gc_prev >> _PyGC_PREV_SHIFT);
          93                 :            : }
          94                 :            :
          95                 :            : static inline void
          96                 :    1220763 : gc_set_refs(PyGC_Head *g, Py_ssize_t refs)
          97                 :            : {
          98                 :    1220763 :     g->_gc_prev = (g->_gc_prev & ~_PyGC_PREV_MASK)
          99                 :    1220763 :         | ((uintptr_t)(refs) << _PyGC_PREV_SHIFT);
         100                 :    1220763 : }
         101                 :            :
         102                 :            : static inline void
         103                 :    1539696 : gc_reset_refs(PyGC_Head *g, Py_ssize_t refs)
         104                 :            : {
         105                 :    1539696 :     g->_gc_prev = (g->_gc_prev & _PyGC_PREV_MASK_FINALIZED)
         106                 :            :         | PREV_MASK_COLLECTING
         107                 :    1539696 :         | ((uintptr_t)(refs) << _PyGC_PREV_SHIFT);
         108                 :    1539696 : }
         109                 :            :
         110                 :            : static inline void
         111                 :    2143854 : gc_decref(PyGC_Head *g)
         112                 :            : {
         113                 :            :     _PyObject_ASSERT_WITH_MSG(FROM_GC(g),
         114                 :            :                               gc_get_refs(g) > 0,
         115                 :            :                               "refcount is too small");
         116                 :    2143854 :     g->_gc_prev -= 1 << _PyGC_PREV_SHIFT;
         117                 :    2143854 : }
         118                 :            :
         119                 :            : /* set for debugging information */
         120                 :            : #define DEBUG_STATS             (1<<0) /* print collection statistics */
         121                 :            : #define DEBUG_COLLECTABLE       (1<<1) /* print collectable objects */
         122                 :            : #define DEBUG_UNCOLLECTABLE     (1<<2) /* print uncollectable objects */
         123                 :            : #define DEBUG_SAVEALL           (1<<5) /* save all garbage in gc.garbage */
         124                 :            : #define DEBUG_LEAK              DEBUG_COLLECTABLE | \
         125                 :            :                 DEBUG_UNCOLLECTABLE | \
         126                 :            :                 DEBUG_SAVEALL
         127                 :            :
         128                 :            : #define GEN_HEAD(gcstate, n) (&(gcstate)->generations[n].head)
         129                 :            :
         130                 :            :
         131                 :            : static GCState *
         132                 :    8977914 : get_gc_state(void)
         133                 :            : {
         134                 :    8977914 :     PyInterpreterState *interp = _PyInterpreterState_GET();
         135                 :    8977914 :     return &interp->gc;
         136                 :            : }
         137                 :            :
         138                 :            :
         139                 :            : void
         140                 :         29 : _PyGC_InitState(GCState *gcstate)
         141                 :            : {
         142                 :            : #define INIT_HEAD(GEN) \
         143                 :            :     do { \
         144                 :            :         GEN.head._gc_next = (uintptr_t)&GEN.head; \
         145                 :            :         GEN.head._gc_prev = (uintptr_t)&GEN.head; \
         146                 :            :     } while (0)
         147                 :            :
         148         [ +  + ]:        116 :     for (int i = 0; i < NUM_GENERATIONS; i++) {
         149                 :            :         assert(gcstate->generations[i].count == 0);
         150                 :         87 :         INIT_HEAD(gcstate->generations[i]);
         151                 :            :     };
         152                 :         29 :     gcstate->generation0 = GEN_HEAD(gcstate, 0);
         153                 :         29 :     INIT_HEAD(gcstate->permanent_generation);
         154                 :            :
         155                 :            : #undef INIT_HEAD
         156                 :         29 : }
         157                 :            :
         158                 :            :
         159                 :            : PyStatus
         160                 :         29 : _PyGC_Init(PyInterpreterState *interp)
         161                 :            : {
         162                 :         29 :     GCState *gcstate = &interp->gc;
         163                 :            :
         164                 :         29 :     gcstate->garbage = PyList_New(0);
         165         [ -  + ]:         29 :     if (gcstate->garbage == NULL) {
         166                 :          0 :         return _PyStatus_NO_MEMORY();
         167                 :            :     }
         168                 :            :
         169                 :         29 :     gcstate->callbacks = PyList_New(0);
         170         [ -  + ]:         29 :     if (gcstate->callbacks == NULL) {
         171                 :          0 :         return _PyStatus_NO_MEMORY();
         172                 :            :     }
         173                 :            :
         174                 :         29 :     return _PyStatus_OK();
         175                 :            : }
         176                 :            :
         177                 :            :
         178                 :            : /*
         179                 :            : _gc_prev values
         180                 :            : ---------------
         181                 :            :
         182                 :            : Between collections, _gc_prev is used for doubly linked list.
         183                 :            :
         184                 :            : Lowest two bits of _gc_prev are used for flags.
         185                 :            : PREV_MASK_COLLECTING is used only while collecting and cleared before GC ends
         186                 :            : or _PyObject_GC_UNTRACK() is called.
         187                 :            :
         188                 :            : During a collection, _gc_prev is temporary used for gc_refs, and the gc list
         189                 :            : is singly linked until _gc_prev is restored.
         190                 :            :
         191                 :            : gc_refs
         192                 :            :     At the start of a collection, update_refs() copies the true refcount
         193                 :            :     to gc_refs, for each object in the generation being collected.
         194                 :            :     subtract_refs() then adjusts gc_refs so that it equals the number of
         195                 :            :     times an object is referenced directly from outside the generation
         196                 :            :     being collected.
         197                 :            :
         198                 :            : PREV_MASK_COLLECTING
         199                 :            :     Objects in generation being collected are marked PREV_MASK_COLLECTING in
         200                 :            :     update_refs().
         201                 :            :
         202                 :            :
         203                 :            : _gc_next values
         204                 :            : ---------------
         205                 :            :
         206                 :            : _gc_next takes these values:
         207                 :            :
         208                 :            :
         209                 :            :     The object is not tracked
         210                 :            :
         211                 :            : != 0
         212                 :            :     Pointer to the next object in the GC list.
         213                 :            :     Additionally, lowest bit is used temporary for
         214                 :            :     NEXT_MASK_UNREACHABLE flag described below.
         215                 :            :
         216                 :            : NEXT_MASK_UNREACHABLE
         217                 :            :     move_unreachable() then moves objects not reachable (whether directly or
         218                 :            :     indirectly) from outside the generation into an "unreachable" set and
         219                 :            :     set this flag.
         220                 :            :
         221                 :            :     Objects that are found to be reachable have gc_refs set to 1.
         222                 :            :     When this flag is set for the reachable object, the object must be in
         223                 :            :     "unreachable" set.
         224                 :            :     The flag is unset and the object is moved back to "reachable" set.
         225                 :            :
         226                 :            :     move_legacy_finalizers() will remove this flag from "unreachable" set.
         227                 :            : */
         228                 :            :
         229                 :            : /*** list functions ***/
         230                 :            :
         231                 :            : static inline void
         232                 :       3595 : gc_list_init(PyGC_Head *list)
         233                 :            : {
         234                 :            :     // List header must not have flags.
         235                 :            :     // We can assign pointer by simple cast.
         236                 :       3595 :     list->_gc_prev = (uintptr_t)list;
         237                 :       3595 :     list->_gc_next = (uintptr_t)list;
         238                 :       3595 : }
         239                 :            :
         240                 :            : static inline int
         241                 :      94729 : gc_list_is_empty(PyGC_Head *list)
         242                 :            : {
         243                 :      94729 :     return (list->_gc_next == (uintptr_t)list);
         244                 :            : }
         245                 :            :
         246                 :            : /* Append `node` to `list`. */
         247                 :            : static inline void
         248                 :     513682 : gc_list_append(PyGC_Head *node, PyGC_Head *list)
         249                 :            : {
         250                 :     513682 :     PyGC_Head *last = (PyGC_Head *)list->_gc_prev;
         251                 :            :
         252                 :            :     // last <-> node
         253                 :     513682 :     _PyGCHead_SET_PREV(node, last);
         254                 :     513682 :     _PyGCHead_SET_NEXT(last, node);
         255                 :            :
         256                 :            :     // node <-> list
         257                 :     513682 :     _PyGCHead_SET_NEXT(node, list);
         258                 :     513682 :     list->_gc_prev = (uintptr_t)node;
         259                 :     513682 : }
         260                 :            :
         261                 :            : /* Remove `node` from the gc list it's currently in. */
         262                 :            : static inline void
         263                 :          0 : gc_list_remove(PyGC_Head *node)
         264                 :            : {
         265                 :          0 :     PyGC_Head *prev = GC_PREV(node);
         266                 :          0 :     PyGC_Head *next = GC_NEXT(node);
         267                 :            :
         268                 :          0 :     _PyGCHead_SET_NEXT(prev, next);
         269                 :          0 :     _PyGCHead_SET_PREV(next, prev);
         270                 :            :
         271                 :          0 :     node->_gc_next = 0; /* object is not currently tracked */
         272                 :          0 : }
         273                 :            :
         274                 :            : /* Move `node` from the gc list it's currently in (which is not explicitly
         275                 :            :  * named here) to the end of `list`.  This is semantically the same as
         276                 :            :  * gc_list_remove(node) followed by gc_list_append(node, list).
         277                 :            :  */
         278                 :            : static void
         279                 :      85975 : gc_list_move(PyGC_Head *node, PyGC_Head *list)
         280                 :            : {
         281                 :            :     /* Unlink from current list. */
         282                 :      85975 :     PyGC_Head *from_prev = GC_PREV(node);
         283                 :      85975 :     PyGC_Head *from_next = GC_NEXT(node);
         284                 :      85975 :     _PyGCHead_SET_NEXT(from_prev, from_next);
         285                 :      85975 :     _PyGCHead_SET_PREV(from_next, from_prev);
         286                 :            :
         287                 :            :     /* Relink at end of new list. */
         288                 :            :     // list must not have flags.  So we can skip macros.
         289                 :      85975 :     PyGC_Head *to_prev = (PyGC_Head*)list->_gc_prev;
         290                 :      85975 :     _PyGCHead_SET_PREV(node, to_prev);
         291                 :      85975 :     _PyGCHead_SET_NEXT(to_prev, node);
         292                 :      85975 :     list->_gc_prev = (uintptr_t)node;
         293                 :      85975 :     _PyGCHead_SET_NEXT(node, list);
         294                 :      85975 : }
         295                 :            :
         296                 :            : /* append list `from` onto list `to`; `from` becomes an empty list */
         297                 :            : static void
         298                 :       1665 : gc_list_merge(PyGC_Head *from, PyGC_Head *to)
         299                 :            : {
         300                 :            :     assert(from != to);
         301         [ +  + ]:       1665 :     if (!gc_list_is_empty(from)) {
         302                 :        481 :         PyGC_Head *to_tail = GC_PREV(to);
         303                 :        481 :         PyGC_Head *from_head = GC_NEXT(from);
         304                 :        481 :         PyGC_Head *from_tail = GC_PREV(from);
         305                 :            :         assert(from_head != from);
         306                 :            :         assert(from_tail != from);
         307                 :            :
         308                 :        481 :         _PyGCHead_SET_NEXT(to_tail, from_head);
         309                 :        481 :         _PyGCHead_SET_PREV(from_head, to_tail);
         310                 :            :
         311                 :        481 :         _PyGCHead_SET_NEXT(from_tail, to);
         312                 :        481 :         _PyGCHead_SET_PREV(to, from_tail);
         313                 :            :     }
         314                 :       1665 :     gc_list_init(from);
         315                 :       1665 : }
         316                 :            :
         317                 :            : static Py_ssize_t
         318                 :        507 : gc_list_size(PyGC_Head *list)
         319                 :            : {
         320                 :            :     PyGC_Head *gc;
         321                 :        507 :     Py_ssize_t n = 0;
         322         [ +  + ]:     840950 :     for (gc = GC_NEXT(list); gc != list; gc = GC_NEXT(gc)) {
         323                 :     840443 :         n++;
         324                 :            :     }
         325                 :        507 :     return n;
         326                 :            : }
         327                 :            :
         328                 :            : /* Walk the list and mark all objects as non-collecting */
         329                 :            : static inline void
         330                 :        386 : gc_list_clear_collecting(PyGC_Head *collectable)
         331                 :            : {
         332                 :            :     PyGC_Head *gc;
         333         [ +  + ]:      81668 :     for (gc = GC_NEXT(collectable); gc != collectable; gc = GC_NEXT(gc)) {
         334                 :      81282 :         gc_clear_collecting(gc);
         335                 :            :     }
         336                 :        386 : }
         337                 :            :
         338                 :            : /* Append objects in a GC list to a Python list.
         339                 :            :  * Return 0 if all OK, < 0 if error (out of memory for list)
         340                 :            :  */
         341                 :            : static int
         342                 :          0 : append_objects(PyObject *py_list, PyGC_Head *gc_list)
         343                 :            : {
         344                 :            :     PyGC_Head *gc;
         345         [ #  # ]:          0 :     for (gc = GC_NEXT(gc_list); gc != gc_list; gc = GC_NEXT(gc)) {
         346                 :          0 :         PyObject *op = FROM_GC(gc);
         347         [ #  # ]:          0 :         if (op != py_list) {
         348         [ #  # ]:          0 :             if (PyList_Append(py_list, op)) {
         349                 :          0 :                 return -1; /* exception */
         350                 :            :             }
         351                 :            :         }
         352                 :            :     }
         353                 :          0 :     return 0;
         354                 :            : }
         355                 :            :
         356                 :            : // Constants for validate_list's flags argument.
         357                 :            : enum flagstates {collecting_clear_unreachable_clear,
         358                 :            :                  collecting_clear_unreachable_set,
         359                 :            :                  collecting_set_unreachable_clear,
         360                 :            :                  collecting_set_unreachable_set};
         361                 :            :
         362                 :            : #ifdef GC_DEBUG
         363                 :            : // validate_list checks list consistency.  And it works as document
         364                 :            : // describing when flags are expected to be set / unset.
         365                 :            : // `head` must be a doubly-linked gc list, although it's fine (expected!) if
         366                 :            : // the prev and next pointers are "polluted" with flags.
         367                 :            : // What's checked:
         368                 :            : // - The `head` pointers are not polluted.
         369                 :            : // - The objects' PREV_MASK_COLLECTING and NEXT_MASK_UNREACHABLE flags are all
         370                 :            : //   `set or clear, as specified by the 'flags' argument.
         371                 :            : // - The prev and next pointers are mutually consistent.
         372                 :            : static void
         373                 :            : validate_list(PyGC_Head *head, enum flagstates flags)
         374                 :            : {
         375                 :            :     assert((head->_gc_prev & PREV_MASK_COLLECTING) == 0);
         376                 :            :     assert((head->_gc_next & NEXT_MASK_UNREACHABLE) == 0);
         377                 :            :     uintptr_t prev_value = 0, next_value = 0;
         378                 :            :     switch (flags) {
         379                 :            :         case collecting_clear_unreachable_clear:
         380                 :            :             break;
         381                 :            :         case collecting_set_unreachable_clear:
         382                 :            :             prev_value = PREV_MASK_COLLECTING;
         383                 :            :             break;
         384                 :            :         case collecting_clear_unreachable_set:
         385                 :            :             next_value = NEXT_MASK_UNREACHABLE;
         386                 :            :             break;
         387                 :            :         case collecting_set_unreachable_set:
         388                 :            :             prev_value = PREV_MASK_COLLECTING;
         389                 :            :             next_value = NEXT_MASK_UNREACHABLE;
         390                 :            :             break;
         391                 :            :         default:
         392                 :            :             assert(! "bad internal flags argument");
         393                 :            :     }
         394                 :            :     PyGC_Head *prev = head;
         395                 :            :     PyGC_Head *gc = GC_NEXT(head);
         396                 :            :     while (gc != head) {
         397                 :            :         PyGC_Head *trueprev = GC_PREV(gc);
         398                 :            :         PyGC_Head *truenext = (PyGC_Head *)(gc->_gc_next  & ~NEXT_MASK_UNREACHABLE);
         399                 :            :         assert(truenext != NULL);
         400                 :            :         assert(trueprev == prev);
         401                 :            :         assert((gc->_gc_prev & PREV_MASK_COLLECTING) == prev_value);
         402                 :            :         assert((gc->_gc_next & NEXT_MASK_UNREACHABLE) == next_value);
         403                 :            :         prev = gc;
         404                 :            :         gc = truenext;
         405                 :            :     }
         406                 :            :     assert(prev == GC_PREV(head));
         407                 :            : }
         408                 :            : #else
         409                 :            : #define validate_list(x, y) do{}while(0)
         410                 :            : #endif
         411                 :            :
         412                 :            : /*** end of list stuff ***/
         413                 :            :
         414                 :            :
         415                 :            : /* Set all gc_refs = ob_refcnt.  After this, gc_refs is > 0 and
         416                 :            :  * PREV_MASK_COLLECTING bit is set for all objects in containers.
         417                 :            :  */
         418                 :            : static void
         419                 :        772 : update_refs(PyGC_Head *containers)
         420                 :            : {
         421                 :        772 :     PyGC_Head *gc = GC_NEXT(containers);
         422         [ +  + ]:    1540468 :     for (; gc != containers; gc = GC_NEXT(gc)) {
         423                 :    1539696 :         gc_reset_refs(gc, Py_REFCNT(FROM_GC(gc)));
         424                 :            :         /* Python's cyclic gc should never see an incoming refcount
         425                 :            :          * of 0:  if something decref'ed to 0, it should have been
         426                 :            :          * deallocated immediately at that time.
         427                 :            :          * Possible cause (if the assert triggers):  a tp_dealloc
         428                 :            :          * routine left a gc-aware object tracked during its teardown
         429                 :            :          * phase, and did something-- or allowed something to happen --
         430                 :            :          * that called back into Python.  gc can trigger then, and may
         431                 :            :          * see the still-tracked dying object.  Before this assert
         432                 :            :          * was added, such mistakes went on to allow gc to try to
         433                 :            :          * delete the object again.  In a debug build, that caused
         434                 :            :          * a mysterious segfault, when _Py_ForgetReference tried
         435                 :            :          * to remove the object from the doubly-linked list of all
         436                 :            :          * objects a second time.  In a release build, an actual
         437                 :            :          * double deallocation occurred, which leads to corruption
         438                 :            :          * of the allocator's internal bookkeeping pointers.  That's
         439                 :            :          * so serious that maybe this should be a release-build
         440                 :            :          * check instead of an assert?
         441                 :            :          */
         442                 :            :         _PyObject_ASSERT(FROM_GC(gc), gc_get_refs(gc) != 0);
         443                 :            :     }
         444                 :        772 : }
         445                 :            :
         446                 :            : /* A traversal callback for subtract_refs. */
         447                 :            : static int
         448                 :    5808645 : visit_decref(PyObject *op, void *parent)
         449                 :            : {
         450                 :            :     _PyObject_ASSERT(_PyObject_CAST(parent), !_PyObject_IsFreed(op));
         451                 :            :
         452         [ +  + ]:    5808645 :     if (_PyObject_IS_GC(op)) {
         453                 :    3212763 :         PyGC_Head *gc = AS_GC(op);
         454                 :            :         /* We're only interested in gc_refs for objects in the
         455                 :            :          * generation being collected, which can be recognized
         456                 :            :          * because only they have positive gc_refs.
         457                 :            :          */
         458         [ +  + ]:    3212763 :         if (gc_is_collecting(gc)) {
         459                 :    2143854 :             gc_decref(gc);
         460                 :            :         }
         461                 :            :     }
         462                 :    5808645 :     return 0;
         463                 :            : }
         464                 :            :
         465                 :            : /* Subtract internal references from gc_refs.  After this, gc_refs is >= 0
         466                 :            :  * for all objects in containers, and is GC_REACHABLE for all tracked gc
         467                 :            :  * objects not in containers.  The ones with gc_refs > 0 are directly
         468                 :            :  * reachable from outside containers, and so can't be collected.
         469                 :            :  */
         470                 :            : static void
         471                 :        772 : subtract_refs(PyGC_Head *containers)
         472                 :            : {
         473                 :            :     traverseproc traverse;
         474                 :        772 :     PyGC_Head *gc = GC_NEXT(containers);
         475         [ +  + ]:    1540468 :     for (; gc != containers; gc = GC_NEXT(gc)) {
         476                 :    1539696 :         PyObject *op = FROM_GC(gc);
         477                 :    1539696 :         traverse = Py_TYPE(op)->tp_traverse;
         478                 :    1539696 :         (void) traverse(op,
         479                 :            :                         (visitproc)visit_decref,
         480                 :            :                         op);
         481                 :            :     }
         482                 :        772 : }
         483                 :            :
         484                 :            : /* A traversal callback for move_unreachable. */
         485                 :            : static int
         486                 :    4997751 : visit_reachable(PyObject *op, PyGC_Head *reachable)
         487                 :            : {
         488         [ +  + ]:    4997751 :     if (!_PyObject_IS_GC(op)) {
         489                 :    2181698 :         return 0;
         490                 :            :     }
         491                 :            :
         492                 :    2816053 :     PyGC_Head *gc = AS_GC(op);
         493                 :    2816053 :     const Py_ssize_t gc_refs = gc_get_refs(gc);
         494                 :            :
         495                 :            :     // Ignore objects in other generation.
         496                 :            :     // This also skips objects "to the left" of the current position in
         497                 :            :     // move_unreachable's scan of the 'young' list - they've already been
         498                 :            :     // traversed, and no longer have the PREV_MASK_COLLECTING flag.
         499         [ +  + ]:    2816053 :     if (! gc_is_collecting(gc)) {
         500                 :    1542068 :         return 0;
         501                 :            :     }
         502                 :            :     // It would be a logic error elsewhere if the collecting flag were set on
         503                 :            :     // an untracked object.
         504                 :            :     assert(gc->_gc_next != 0);
         505                 :            :
         506         [ +  + ]:    1273985 :     if (gc->_gc_next & NEXT_MASK_UNREACHABLE) {
         507                 :            :         /* This had gc_refs = 0 when move_unreachable got
         508                 :            :          * to it, but turns out it's reachable after all.
         509                 :            :          * Move it back to move_unreachable's 'young' list,
         510                 :            :          * and move_unreachable will eventually get to it
         511                 :            :          * again.
         512                 :            :          */
         513                 :            :         // Manually unlink gc from unreachable list because the list functions
         514                 :            :         // don't work right in the presence of NEXT_MASK_UNREACHABLE flags.
         515                 :     513682 :         PyGC_Head *prev = GC_PREV(gc);
         516                 :     513682 :         PyGC_Head *next = (PyGC_Head*)(gc->_gc_next & ~NEXT_MASK_UNREACHABLE);
         517                 :            :         _PyObject_ASSERT(FROM_GC(prev),
         518                 :            :                          prev->_gc_next & NEXT_MASK_UNREACHABLE);
         519                 :            :         _PyObject_ASSERT(FROM_GC(next),
         520                 :            :                          next->_gc_next & NEXT_MASK_UNREACHABLE);
         521                 :     513682 :         prev->_gc_next = gc->_gc_next;  // copy NEXT_MASK_UNREACHABLE
         522                 :     513682 :         _PyGCHead_SET_PREV(next, prev);
         523                 :            :
         524                 :     513682 :         gc_list_append(gc, reachable);
         525                 :     513682 :         gc_set_refs(gc, 1);
         526                 :            :     }
         527         [ +  + ]:     760303 :     else if (gc_refs == 0) {
         528                 :            :         /* This is in move_unreachable's 'young' list, but
         529                 :            :          * the traversal hasn't yet gotten to it.  All
         530                 :            :          * we need to do is tell move_unreachable that it's
         531                 :            :          * reachable.
         532                 :            :          */
         533                 :     707081 :         gc_set_refs(gc, 1);
         534                 :            :     }
         535                 :            :     /* Else there's nothing to do.
         536                 :            :      * If gc_refs > 0, it must be in move_unreachable's 'young'
         537                 :            :      * list, and move_unreachable will eventually get to it.
         538                 :            :      */
         539                 :            :     else {
         540                 :            :         _PyObject_ASSERT_WITH_MSG(op, gc_refs > 0, "refcount is too small");
         541                 :            :     }
         542                 :    1273985 :     return 0;
         543                 :            : }
         544                 :            :
         545                 :            : /* Move the unreachable objects from young to unreachable.  After this,
         546                 :            :  * all objects in young don't have PREV_MASK_COLLECTING flag and
         547                 :            :  * unreachable have the flag.
         548                 :            :  * All objects in young after this are directly or indirectly reachable
         549                 :            :  * from outside the original young; and all objects in unreachable are
         550                 :            :  * not.
         551                 :            :  *
         552                 :            :  * This function restores _gc_prev pointer.  young and unreachable are
         553                 :            :  * doubly linked list after this function.
         554                 :            :  * But _gc_next in unreachable list has NEXT_MASK_UNREACHABLE flag.
         555                 :            :  * So we can not gc_list_* functions for unreachable until we remove the flag.
         556                 :            :  */
         557                 :            : static void
         558                 :        772 : move_unreachable(PyGC_Head *young, PyGC_Head *unreachable)
         559                 :            : {
         560                 :            :     // previous elem in the young list, used for restore gc_prev.
         561                 :        772 :     PyGC_Head *prev = young;
         562                 :        772 :     PyGC_Head *gc = GC_NEXT(young);
         563                 :            :
         564                 :            :     /* Invariants:  all objects "to the left" of us in young are reachable
         565                 :            :      * (directly or indirectly) from outside the young list as it was at entry.
         566                 :            :      *
         567                 :            :      * All other objects from the original young "to the left" of us are in
         568                 :            :      * unreachable now, and have NEXT_MASK_UNREACHABLE.  All objects to the
         569                 :            :      * left of us in 'young' now have been scanned, and no objects here
         570                 :            :      * or to the right have been scanned yet.
         571                 :            :      */
         572                 :            :
         573         [ +  + ]:    2054150 :     while (gc != young) {
         574         [ +  + ]:    2053378 :         if (gc_get_refs(gc)) {
         575                 :            :             /* gc is definitely reachable from outside the
         576                 :            :              * original 'young'.  Mark it as such, and traverse
         577                 :            :              * its pointers to find any other objects that may
         578                 :            :              * be directly reachable from it.  Note that the
         579                 :            :              * call to tp_traverse may append objects to young,
         580                 :            :              * so we have to wait until it returns to determine
         581                 :            :              * the next object to visit.
         582                 :            :              */
         583                 :    1377132 :             PyObject *op = FROM_GC(gc);
         584                 :    1377132 :             traverseproc traverse = Py_TYPE(op)->tp_traverse;
         585                 :            :             _PyObject_ASSERT_WITH_MSG(op, gc_get_refs(gc) > 0,
         586                 :            :                                       "refcount is too small");
         587                 :            :             // NOTE: visit_reachable may change gc->_gc_next when
         588                 :            :             // young->_gc_prev == gc.  Don't do gc = GC_NEXT(gc) before!
         589                 :    1377132 :             (void) traverse(op,
         590                 :            :                     (visitproc)visit_reachable,
         591                 :            :                     (void *)young);
         592                 :            :             // relink gc_prev to prev element.
         593                 :    1377132 :             _PyGCHead_SET_PREV(gc, prev);
         594                 :            :             // gc is not COLLECTING state after here.
         595                 :    1377132 :             gc_clear_collecting(gc);
         596                 :    1377132 :             prev = gc;
         597                 :            :         }
         598                 :            :         else {
         599                 :            :             /* This *may* be unreachable.  To make progress,
         600                 :            :              * assume it is.  gc isn't directly reachable from
         601                 :            :              * any object we've already traversed, but may be
         602                 :            :              * reachable from an object we haven't gotten to yet.
         603                 :            :              * visit_reachable will eventually move gc back into
         604                 :            :              * young if that's so, and we'll see it again.
         605                 :            :              */
         606                 :            :             // Move gc to unreachable.
         607                 :            :             // No need to gc->next->prev = prev because it is single linked.
         608                 :     676246 :             prev->_gc_next = gc->_gc_next;
         609                 :            :
         610                 :            :             // We can't use gc_list_append() here because we use
         611                 :            :             // NEXT_MASK_UNREACHABLE here.
         612                 :     676246 :             PyGC_Head *last = GC_PREV(unreachable);
         613                 :            :             // NOTE: Since all objects in unreachable set has
         614                 :            :             // NEXT_MASK_UNREACHABLE flag, we set it unconditionally.
         615                 :            :             // But this may pollute the unreachable list head's 'next' pointer
         616                 :            :             // too. That's semantically senseless but expedient here - the
         617                 :            :             // damage is repaired when this function ends.
         618                 :     676246 :             last->_gc_next = (NEXT_MASK_UNREACHABLE | (uintptr_t)gc);
         619                 :     676246 :             _PyGCHead_SET_PREV(gc, last);
         620                 :     676246 :             gc->_gc_next = (NEXT_MASK_UNREACHABLE | (uintptr_t)unreachable);
         621                 :     676246 :             unreachable->_gc_prev = (uintptr_t)gc;
         622                 :            :         }
         623                 :    2053378 :         gc = (PyGC_Head*)prev->_gc_next;
         624                 :            :     }
         625                 :            :     // young->_gc_prev must be last element remained in the list.
         626                 :        772 :     young->_gc_prev = (uintptr_t)prev;
         627                 :            :     // don't let the pollution of the list head's next pointer leak
         628                 :        772 :     unreachable->_gc_next &= ~NEXT_MASK_UNREACHABLE;
         629                 :        772 : }
         630                 :            :
         631                 :            : static void
         632                 :        386 : untrack_tuples(PyGC_Head *head)
         633                 :            : {
         634                 :        386 :     PyGC_Head *next, *gc = GC_NEXT(head);
         635         [ +  + ]:    1377518 :     while (gc != head) {
         636                 :    1377132 :         PyObject *op = FROM_GC(gc);
         637                 :    1377132 :         next = GC_NEXT(gc);
         638         [ +  + ]:    1377132 :         if (PyTuple_CheckExact(op)) {
         639                 :     170129 :             _PyTuple_MaybeUntrack(op);
         640                 :            :         }
         641                 :    1377132 :         gc = next;
         642                 :            :     }
         643                 :        386 : }
         644                 :            :
         645                 :            : /* Try to untrack all currently tracked dictionaries */
         646                 :            : static void
         647                 :        112 : untrack_dicts(PyGC_Head *head)
         648                 :            : {
         649                 :        112 :     PyGC_Head *next, *gc = GC_NEXT(head);
         650         [ +  + ]:     647645 :     while (gc != head) {
         651                 :     647533 :         PyObject *op = FROM_GC(gc);
         652                 :     647533 :         next = GC_NEXT(gc);
         653         [ +  + ]:     647533 :         if (PyDict_CheckExact(op)) {
         654                 :      61845 :             _PyDict_MaybeUntrack(op);
         655                 :            :         }
         656                 :     647533 :         gc = next;
         657                 :            :     }
         658                 :        112 : }
         659                 :            :
         660                 :            : /* Return true if object has a pre-PEP 442 finalization method. */
         661                 :            : static int
         662                 :      81282 : has_legacy_finalizer(PyObject *op)
         663                 :            : {
         664                 :      81282 :     return Py_TYPE(op)->tp_del != NULL;
         665                 :            : }
         666                 :            :
         667                 :            : /* Move the objects in unreachable with tp_del slots into `finalizers`.
         668                 :            :  *
         669                 :            :  * This function also removes NEXT_MASK_UNREACHABLE flag
         670                 :            :  * from _gc_next in unreachable.
         671                 :            :  */
         672                 :            : static void
         673                 :        386 : move_legacy_finalizers(PyGC_Head *unreachable, PyGC_Head *finalizers)
         674                 :            : {
         675                 :            :     PyGC_Head *gc, *next;
         676                 :            :     assert((unreachable->_gc_next & NEXT_MASK_UNREACHABLE) == 0);
         677                 :            :
         678                 :            :     /* March over unreachable.  Move objects with finalizers into
         679                 :            :      * `finalizers`.
         680                 :            :      */
         681         [ +  + ]:      81668 :     for (gc = GC_NEXT(unreachable); gc != unreachable; gc = next) {
         682                 :      81282 :         PyObject *op = FROM_GC(gc);
         683                 :            :
         684                 :            :         _PyObject_ASSERT(op, gc->_gc_next & NEXT_MASK_UNREACHABLE);
         685                 :      81282 :         gc->_gc_next &= ~NEXT_MASK_UNREACHABLE;
         686                 :      81282 :         next = (PyGC_Head*)gc->_gc_next;
         687                 :            :
         688         [ -  + ]:      81282 :         if (has_legacy_finalizer(op)) {
         689                 :          0 :             gc_clear_collecting(gc);
         690                 :          0 :             gc_list_move(gc, finalizers);
         691                 :            :         }
         692                 :            :     }
         693                 :        386 : }
         694                 :            :
         695                 :            : static inline void
         696                 :        386 : clear_unreachable_mask(PyGC_Head *unreachable)
         697                 :            : {
         698                 :            :     /* Check that the list head does not have the unreachable bit set */
         699                 :            :     assert(((uintptr_t)unreachable & NEXT_MASK_UNREACHABLE) == 0);
         700                 :            :
         701                 :            :     PyGC_Head *gc, *next;
         702                 :            :     assert((unreachable->_gc_next & NEXT_MASK_UNREACHABLE) == 0);
         703         [ +  + ]:      81668 :     for (gc = GC_NEXT(unreachable); gc != unreachable; gc = next) {
         704                 :            :         _PyObject_ASSERT((PyObject*)FROM_GC(gc), gc->_gc_next & NEXT_MASK_UNREACHABLE);
         705                 :      81282 :         gc->_gc_next &= ~NEXT_MASK_UNREACHABLE;
         706                 :      81282 :         next = (PyGC_Head*)gc->_gc_next;
         707                 :            :     }
         708                 :            :     validate_list(unreachable, collecting_set_unreachable_clear);
         709                 :        386 : }
         710                 :            :
         711                 :            : /* A traversal callback for move_legacy_finalizer_reachable. */
         712                 :            : static int
         713                 :          0 : visit_move(PyObject *op, PyGC_Head *tolist)
         714                 :            : {
         715         [ #  # ]:          0 :     if (_PyObject_IS_GC(op)) {
         716                 :          0 :         PyGC_Head *gc = AS_GC(op);
         717         [ #  # ]:          0 :         if (gc_is_collecting(gc)) {
         718                 :          0 :             gc_list_move(gc, tolist);
         719                 :          0 :             gc_clear_collecting(gc);
         720                 :            :         }
         721                 :            :     }
         722                 :          0 :     return 0;
         723                 :            : }
         724                 :            :
         725                 :            : /* Move objects that are reachable from finalizers, from the unreachable set
         726                 :            :  * into finalizers set.
         727                 :            :  */
         728                 :            : static void
         729                 :        386 : move_legacy_finalizer_reachable(PyGC_Head *finalizers)
         730                 :            : {
         731                 :            :     traverseproc traverse;
         732                 :        386 :     PyGC_Head *gc = GC_NEXT(finalizers);
         733         [ -  + ]:        386 :     for (; gc != finalizers; gc = GC_NEXT(gc)) {
         734                 :            :         /* Note that the finalizers list may grow during this. */
         735                 :          0 :         traverse = Py_TYPE(FROM_GC(gc))->tp_traverse;
         736                 :          0 :         (void) traverse(FROM_GC(gc),
         737                 :            :                         (visitproc)visit_move,
         738                 :            :                         (void *)finalizers);
         739                 :            :     }
         740                 :        386 : }
         741                 :            :
         742                 :            : /* Clear all weakrefs to unreachable objects, and if such a weakref has a
         743                 :            :  * callback, invoke it if necessary.  Note that it's possible for such
         744                 :            :  * weakrefs to be outside the unreachable set -- indeed, those are precisely
         745                 :            :  * the weakrefs whose callbacks must be invoked.  See gc_weakref.txt for
         746                 :            :  * overview & some details.  Some weakrefs with callbacks may be reclaimed
         747                 :            :  * directly by this routine; the number reclaimed is the return value.  Other
         748                 :            :  * weakrefs with callbacks may be moved into the `old` generation.  Objects
         749                 :            :  * moved into `old` have gc_refs set to GC_REACHABLE; the objects remaining in
         750                 :            :  * unreachable are left at GC_TENTATIVELY_UNREACHABLE.  When this returns,
         751                 :            :  * no object in `unreachable` is weakly referenced anymore.
         752                 :            :  */
         753                 :            : static int
         754                 :        386 : handle_weakrefs(PyGC_Head *unreachable, PyGC_Head *old)
         755                 :            : {
         756                 :            :     PyGC_Head *gc;
         757                 :            :     PyObject *op;               /* generally FROM_GC(gc) */
         758                 :            :     PyWeakReference *wr;        /* generally a cast of op */
         759                 :            :     PyGC_Head wrcb_to_call;     /* weakrefs with callbacks to call */
         760                 :            :     PyGC_Head *next;
         761                 :        386 :     int num_freed = 0;
         762                 :            :
         763                 :        386 :     gc_list_init(&wrcb_to_call);
         764                 :            :
         765                 :            :     /* Clear all weakrefs to the objects in unreachable.  If such a weakref
         766                 :            :      * also has a callback, move it into `wrcb_to_call` if the callback
         767                 :            :      * needs to be invoked.  Note that we cannot invoke any callbacks until
         768                 :            :      * all weakrefs to unreachable objects are cleared, lest the callback
         769                 :            :      * resurrect an unreachable object via a still-active weakref.  We
         770                 :            :      * make another pass over wrcb_to_call, invoking callbacks, after this
         771                 :            :      * pass completes.
         772                 :            :      */
         773         [ +  + ]:      81668 :     for (gc = GC_NEXT(unreachable); gc != unreachable; gc = next) {
         774                 :            :         PyWeakReference **wrlist;
         775                 :            :
         776                 :      81282 :         op = FROM_GC(gc);
         777                 :      81282 :         next = GC_NEXT(gc);
         778                 :            :
         779   [ +  +  +  -  :      81282 :         if (PyWeakref_Check(op)) {
                       -  + ]
         780                 :            :             /* A weakref inside the unreachable set must be cleared.  If we
         781                 :            :              * allow its callback to execute inside delete_garbage(), it
         782                 :            :              * could expose objects that have tp_clear already called on
         783                 :            :              * them.  Or, it could resurrect unreachable objects.  One way
         784                 :            :              * this can happen is if some container objects do not implement
         785                 :            :              * tp_traverse.  Then, wr_object can be outside the unreachable
         786                 :            :              * set but can be deallocated as a result of breaking the
         787                 :            :              * reference cycle.  If we don't clear the weakref, the callback
         788                 :            :              * will run and potentially cause a crash.  See bpo-38006 for
         789                 :            :              * one example.
         790                 :            :              */
         791                 :       2004 :             _PyWeakref_ClearRef((PyWeakReference *)op);
         792                 :            :         }
         793                 :            :
         794         [ +  + ]:      81282 :         if (! _PyType_SUPPORTS_WEAKREFS(Py_TYPE(op)))
         795                 :      44163 :             continue;
         796                 :            :
         797                 :            :         /* It supports weakrefs.  Does it have any?
         798                 :            :          *
         799                 :            :          * This is never triggered for static types so we can avoid the
         800                 :            :          * (slightly) more costly _PyObject_GET_WEAKREFS_LISTPTR().
         801                 :            :          */
         802                 :      37119 :         wrlist = _PyObject_GET_WEAKREFS_LISTPTR_FROM_OFFSET(op);
         803                 :            :
         804                 :            :         /* `op` may have some weakrefs.  March over the list, clear
         805                 :            :          * all the weakrefs, and move the weakrefs with callbacks
         806                 :            :          * that must be called into wrcb_to_call.
         807                 :            :          */
         808         [ +  + ]:      45356 :         for (wr = *wrlist; wr != NULL; wr = *wrlist) {
         809                 :            :             PyGC_Head *wrasgc;                  /* AS_GC(wr) */
         810                 :            :
         811                 :            :             /* _PyWeakref_ClearRef clears the weakref but leaves
         812                 :            :              * the callback pointer intact.  Obscure:  it also
         813                 :            :              * changes *wrlist.
         814                 :            :              */
         815                 :            :             _PyObject_ASSERT((PyObject *)wr, wr->wr_object == op);
         816                 :       8237 :             _PyWeakref_ClearRef(wr);
         817                 :            :             _PyObject_ASSERT((PyObject *)wr, wr->wr_object == Py_None);
         818         [ +  + ]:       8237 :             if (wr->wr_callback == NULL) {
         819                 :            :                 /* no callback */
         820                 :       8224 :                 continue;
         821                 :            :             }
         822                 :            :
         823                 :            :             /* Headache time.  `op` is going away, and is weakly referenced by
         824                 :            :              * `wr`, which has a callback.  Should the callback be invoked?  If wr
         825                 :            :              * is also trash, no:
         826                 :            :              *
         827                 :            :              * 1. There's no need to call it.  The object and the weakref are
         828                 :            :              *    both going away, so it's legitimate to pretend the weakref is
         829                 :            :              *    going away first.  The user has to ensure a weakref outlives its
         830                 :            :              *    referent if they want a guarantee that the wr callback will get
         831                 :            :              *    invoked.
         832                 :            :              *
         833                 :            :              * 2. It may be catastrophic to call it.  If the callback is also in
         834                 :            :              *    cyclic trash (CT), then although the CT is unreachable from
         835                 :            :              *    outside the current generation, CT may be reachable from the
         836                 :            :              *    callback.  Then the callback could resurrect insane objects.
         837                 :            :              *
         838                 :            :              * Since the callback is never needed and may be unsafe in this case,
         839                 :            :              * wr is simply left in the unreachable set.  Note that because we
         840                 :            :              * already called _PyWeakref_ClearRef(wr), its callback will never
         841                 :            :              * trigger.
         842                 :            :              *
         843                 :            :              * OTOH, if wr isn't part of CT, we should invoke the callback:  the
         844                 :            :              * weakref outlived the trash.  Note that since wr isn't CT in this
         845                 :            :              * case, its callback can't be CT either -- wr acted as an external
         846                 :            :              * root to this generation, and therefore its callback did too.  So
         847                 :            :              * nothing in CT is reachable from the callback either, so it's hard
         848                 :            :              * to imagine how calling it later could create a problem for us.  wr
         849                 :            :              * is moved to wrcb_to_call in this case.
         850                 :            :              */
         851         [ +  + ]:         13 :             if (gc_is_collecting(AS_GC(wr))) {
         852                 :            :                 /* it should already have been cleared above */
         853                 :            :                 assert(wr->wr_object == Py_None);
         854                 :          6 :                 continue;
         855                 :            :             }
         856                 :            :
         857                 :            :             /* Create a new reference so that wr can't go away
         858                 :            :              * before we can process it again.
         859                 :            :              */
         860                 :          7 :             Py_INCREF(wr);
         861                 :            :
         862                 :            :             /* Move wr to wrcb_to_call, for the next pass. */
         863                 :          7 :             wrasgc = AS_GC(wr);
         864                 :            :             assert(wrasgc != next); /* wrasgc is reachable, but
         865                 :            :                                        next isn't, so they can't
         866                 :            :                                        be the same */
         867                 :          7 :             gc_list_move(wrasgc, &wrcb_to_call);
         868                 :            :         }
         869                 :            :     }
         870                 :            :
         871                 :            :     /* Invoke the callbacks we decided to honor.  It's safe to invoke them
         872                 :            :      * because they can't reference unreachable objects.
         873                 :            :      */
         874         [ +  + ]:        393 :     while (! gc_list_is_empty(&wrcb_to_call)) {
         875                 :            :         PyObject *temp;
         876                 :            :         PyObject *callback;
         877                 :            :
         878                 :          7 :         gc = (PyGC_Head*)wrcb_to_call._gc_next;
         879                 :          7 :         op = FROM_GC(gc);
         880                 :            :         _PyObject_ASSERT(op, PyWeakref_Check(op));
         881                 :          7 :         wr = (PyWeakReference *)op;
         882                 :          7 :         callback = wr->wr_callback;
         883                 :            :         _PyObject_ASSERT(op, callback != NULL);
         884                 :            :
         885                 :            :         /* copy-paste of weakrefobject.c's handle_callback() */
         886                 :          7 :         temp = PyObject_CallOneArg(callback, (PyObject *)wr);
         887         [ -  + ]:          7 :         if (temp == NULL)
         888                 :          0 :             PyErr_WriteUnraisable(callback);
         889                 :            :         else
         890                 :          7 :             Py_DECREF(temp);
         891                 :            :
         892                 :            :         /* Give up the reference we created in the first pass.  When
         893                 :            :          * op's refcount hits 0 (which it may or may not do right now),
         894                 :            :          * op's tp_dealloc will decref op->wr_callback too.  Note
         895                 :            :          * that the refcount probably will hit 0 now, and because this
         896                 :            :          * weakref was reachable to begin with, gc didn't already
         897                 :            :          * add it to its count of freed objects.  Example:  a reachable
         898                 :            :          * weak value dict maps some key to this reachable weakref.
         899                 :            :          * The callback removes this key->weakref mapping from the
         900                 :            :          * dict, leaving no other references to the weakref (excepting
         901                 :            :          * ours).
         902                 :            :          */
         903                 :          7 :         Py_DECREF(op);
         904         [ -  + ]:          7 :         if (wrcb_to_call._gc_next == (uintptr_t)gc) {
         905                 :            :             /* object is still alive -- move it */
         906                 :          0 :             gc_list_move(gc, old);
         907                 :            :         }
         908                 :            :         else {
         909                 :          7 :             ++num_freed;
         910                 :            :         }
         911                 :            :     }
         912                 :            :
         913                 :        386 :     return num_freed;
         914                 :            : }
         915                 :            :
         916                 :            : static void
         917                 :          0 : debug_cycle(const char *msg, PyObject *op)
         918                 :            : {
         919                 :          0 :     PySys_FormatStderr("gc: %s <%s %p>\n",
         920                 :          0 :                        msg, Py_TYPE(op)->tp_name, op);
         921                 :          0 : }
         922                 :            :
         923                 :            : /* Handle uncollectable garbage (cycles with tp_del slots, and stuff reachable
         924                 :            :  * only from such cycles).
         925                 :            :  * If DEBUG_SAVEALL, all objects in finalizers are appended to the module
         926                 :            :  * garbage list (a Python list), else only the objects in finalizers with
         927                 :            :  * __del__ methods are appended to garbage.  All objects in finalizers are
         928                 :            :  * merged into the old list regardless.
         929                 :            :  */
         930                 :            : static void
         931                 :        386 : handle_legacy_finalizers(PyThreadState *tstate,
         932                 :            :                          GCState *gcstate,
         933                 :            :                          PyGC_Head *finalizers, PyGC_Head *old)
         934                 :            : {
         935                 :            :     assert(!_PyErr_Occurred(tstate));
         936                 :            :     assert(gcstate->garbage != NULL);
         937                 :            :
         938                 :        386 :     PyGC_Head *gc = GC_NEXT(finalizers);
         939         [ -  + ]:        386 :     for (; gc != finalizers; gc = GC_NEXT(gc)) {
         940                 :          0 :         PyObject *op = FROM_GC(gc);
         941                 :            :
         942   [ #  #  #  # ]:          0 :         if ((gcstate->debug & DEBUG_SAVEALL) || has_legacy_finalizer(op)) {
         943         [ #  # ]:          0 :             if (PyList_Append(gcstate->garbage, op) < 0) {
         944                 :          0 :                 _PyErr_Clear(tstate);
         945                 :          0 :                 break;
         946                 :            :             }
         947                 :            :         }
         948                 :            :     }
         949                 :            :
         950                 :        386 :     gc_list_merge(finalizers, old);
         951                 :        386 : }
         952                 :            :
         953                 :            : /* Run first-time finalizers (if any) on all the objects in collectable.
         954                 :            :  * Note that this may remove some (or even all) of the objects from the
         955                 :            :  * list, due to refcounts falling to 0.
         956                 :            :  */
         957                 :            : static void
         958                 :        386 : finalize_garbage(PyThreadState *tstate, PyGC_Head *collectable)
         959                 :            : {
         960                 :            :     destructor finalize;
         961                 :            :     PyGC_Head seen;
         962                 :            :
         963                 :            :     /* While we're going through the loop, `finalize(op)` may cause op, or
         964                 :            :      * other objects, to be reclaimed via refcounts falling to zero.  So
         965                 :            :      * there's little we can rely on about the structure of the input
         966                 :            :      * `collectable` list across iterations.  For safety, we always take the
         967                 :            :      * first object in that list and move it to a temporary `seen` list.
         968                 :            :      * If objects vanish from the `collectable` and `seen` lists we don't
         969                 :            :      * care.
         970                 :            :      */
         971                 :        386 :     gc_list_init(&seen);
         972                 :            :
         973         [ +  + ]:      81668 :     while (!gc_list_is_empty(collectable)) {
         974                 :      81282 :         PyGC_Head *gc = GC_NEXT(collectable);
         975                 :      81282 :         PyObject *op = FROM_GC(gc);
         976                 :      81282 :         gc_list_move(gc, &seen);
         977         [ +  - ]:      81282 :         if (!_PyGCHead_FINALIZED(gc) &&
         978         [ +  + ]:      81282 :                 (finalize = Py_TYPE(op)->tp_finalize) != NULL) {
         979                 :         12 :             _PyGCHead_SET_FINALIZED(gc);
         980                 :         12 :             Py_INCREF(op);
         981                 :         12 :             finalize(op);
         982                 :            :             assert(!_PyErr_Occurred(tstate));
         983                 :         12 :             Py_DECREF(op);
         984                 :            :         }
         985                 :            :     }
         986                 :        386 :     gc_list_merge(&seen, collectable);
         987                 :        386 : }
         988                 :            :
         989                 :            : /* Break reference cycles by clearing the containers involved.  This is
         990                 :            :  * tricky business as the lists can be changing and we don't know which
         991                 :            :  * objects may be freed.  It is possible I screwed something up here.
         992                 :            :  */
         993                 :            : static void
         994                 :        386 : delete_garbage(PyThreadState *tstate, GCState *gcstate,
         995                 :            :                PyGC_Head *collectable, PyGC_Head *old)
         996                 :            : {
         997                 :            :     assert(!_PyErr_Occurred(tstate));
         998                 :            :
         999         [ +  + ]:      11003 :     while (!gc_list_is_empty(collectable)) {
        1000                 :      10617 :         PyGC_Head *gc = GC_NEXT(collectable);
        1001                 :      10617 :         PyObject *op = FROM_GC(gc);
        1002                 :            :
        1003                 :            :         _PyObject_ASSERT_WITH_MSG(op, Py_REFCNT(op) > 0,
        1004                 :            :                                   "refcount is too small");
        1005                 :            :
        1006         [ -  + ]:      10617 :         if (gcstate->debug & DEBUG_SAVEALL) {
        1007                 :            :             assert(gcstate->garbage != NULL);
        1008         [ #  # ]:          0 :             if (PyList_Append(gcstate->garbage, op) < 0) {
        1009                 :          0 :                 _PyErr_Clear(tstate);
        1010                 :            :             }
        1011                 :            :         }
        1012                 :            :         else {
        1013                 :            :             inquiry clear;
        1014         [ +  + ]:      10617 :             if ((clear = Py_TYPE(op)->tp_clear) != NULL) {
        1015                 :       9902 :                 Py_INCREF(op);
        1016                 :       9902 :                 (void) clear(op);
        1017         [ -  + ]:       9902 :                 if (_PyErr_Occurred(tstate)) {
        1018                 :          0 :                     _PyErr_WriteUnraisableMsg("in tp_clear of",
        1019                 :          0 :                                               (PyObject*)Py_TYPE(op));
        1020                 :            :                 }
        1021                 :       9902 :                 Py_DECREF(op);
        1022                 :            :             }
        1023                 :            :         }
        1024         [ +  + ]:      10617 :         if (GC_NEXT(collectable) == gc) {
        1025                 :            :             /* object is still alive, move it, it may die later */
        1026                 :       4686 :             gc_clear_collecting(gc);
        1027                 :       4686 :             gc_list_move(gc, old);
        1028                 :            :         }
        1029                 :            :     }
        1030                 :        386 : }
        1031                 :            :
        1032                 :            : /* Clear all free lists
        1033                 :            :  * All free lists are cleared during the collection of the highest generation.
        1034                 :            :  * Allocated items in the free list may keep a pymalloc arena occupied.
        1035                 :            :  * Clearing the free lists may give back memory to the OS earlier.
        1036                 :            :  */
        1037                 :            : static void
        1038                 :        112 : clear_freelists(PyInterpreterState *interp)
        1039                 :            : {
        1040                 :        112 :     _PyTuple_ClearFreeList(interp);
        1041                 :        112 :     _PyFloat_ClearFreeList(interp);
        1042                 :        112 :     _PyList_ClearFreeList(interp);
        1043                 :        112 :     _PyDict_ClearFreeList(interp);
        1044                 :        112 :     _PyAsyncGen_ClearFreeLists(interp);
        1045                 :        112 :     _PyContext_ClearFreeList(interp);
        1046                 :        112 : }
        1047                 :            :
        1048                 :            : // Show stats for objects in each generations
        1049                 :            : static void
        1050                 :          0 : show_stats_each_generations(GCState *gcstate)
        1051                 :            : {
        1052                 :            :     char buf[100];
        1053                 :          0 :     size_t pos = 0;
        1054                 :            :
        1055   [ #  #  #  # ]:          0 :     for (int i = 0; i < NUM_GENERATIONS && pos < sizeof(buf); i++) {
        1056                 :          0 :         pos += PyOS_snprintf(buf+pos, sizeof(buf)-pos,
        1057                 :            :                              " %zd",
        1058                 :            :                              gc_list_size(GEN_HEAD(gcstate, i)));
        1059                 :            :     }
        1060                 :            :
        1061                 :          0 :     PySys_FormatStderr(
        1062                 :            :         "gc: objects in each generation:%s\n"
        1063                 :            :         "gc: objects in permanent generation: %zd\n",
        1064                 :            :         buf, gc_list_size(&gcstate->permanent_generation.head));
        1065                 :          0 : }
        1066                 :            :
        1067                 :            : /* Deduce which objects among "base" are unreachable from outside the list
        1068                 :            :    and move them to 'unreachable'. The process consist in the following steps:
        1069                 :            :
        1070                 :            : 1. Copy all reference counts to a different field (gc_prev is used to hold
        1071                 :            :    this copy to save memory).
        1072                 :            : 2. Traverse all objects in "base" and visit all referred objects using
        1073                 :            :    "tp_traverse" and for every visited object, subtract 1 to the reference
        1074                 :            :    count (the one that we copied in the previous step). After this step, all
        1075                 :            :    objects that can be reached directly from outside must have strictly positive
        1076                 :            :    reference count, while all unreachable objects must have a count of exactly 0.
        1077                 :            : 3. Identify all unreachable objects (the ones with 0 reference count) and move
        1078                 :            :    them to the "unreachable" list. This step also needs to move back to "base" all
        1079                 :            :    objects that were initially marked as unreachable but are referred transitively
        1080                 :            :    by the reachable objects (the ones with strictly positive reference count).
        1081                 :            :
        1082                 :            : Contracts:
        1083                 :            :
        1084                 :            :     * The "base" has to be a valid list with no mask set.
        1085                 :            :
        1086                 :            :     * The "unreachable" list must be uninitialized (this function calls
        1087                 :            :       gc_list_init over 'unreachable').
        1088                 :            :
        1089                 :            : IMPORTANT: This function leaves 'unreachable' with the NEXT_MASK_UNREACHABLE
        1090                 :            : flag set but it does not clear it to skip unnecessary iteration. Before the
        1091                 :            : flag is cleared (for example, by using 'clear_unreachable_mask' function or
        1092                 :            : by a call to 'move_legacy_finalizers'), the 'unreachable' list is not a normal
        1093                 :            : list and we can not use most gc_list_* functions for it. */
        1094                 :            : static inline void
        1095                 :        772 : deduce_unreachable(PyGC_Head *base, PyGC_Head *unreachable) {
        1096                 :            :     validate_list(base, collecting_clear_unreachable_clear);
        1097                 :            :     /* Using ob_refcnt and gc_refs, calculate which objects in the
        1098                 :            :      * container set are reachable from outside the set (i.e., have a
        1099                 :            :      * refcount greater than 0 when all the references within the
        1100                 :            :      * set are taken into account).
        1101                 :            :      */
        1102                 :        772 :     update_refs(base);  // gc_prev is used for gc_refs
        1103                 :        772 :     subtract_refs(base);
        1104                 :            :
        1105                 :            :     /* Leave everything reachable from outside base in base, and move
        1106                 :            :      * everything else (in base) to unreachable.
        1107                 :            :      *
        1108                 :            :      * NOTE:  This used to move the reachable objects into a reachable
        1109                 :            :      * set instead.  But most things usually turn out to be reachable,
        1110                 :            :      * so it's more efficient to move the unreachable things.  It "sounds slick"
        1111                 :            :      * to move the unreachable objects, until you think about it - the reason it
        1112                 :            :      * pays isn't actually obvious.
        1113                 :            :      *
        1114                 :            :      * Suppose we create objects A, B, C in that order.  They appear in the young
        1115                 :            :      * generation in the same order.  If B points to A, and C to B, and C is
        1116                 :            :      * reachable from outside, then the adjusted refcounts will be 0, 0, and 1
        1117                 :            :      * respectively.
        1118                 :            :      *
        1119                 :            :      * When move_unreachable finds A, A is moved to the unreachable list.  The
        1120                 :            :      * same for B when it's first encountered.  Then C is traversed, B is moved
        1121                 :            :      * _back_ to the reachable list.  B is eventually traversed, and then A is
        1122                 :            :      * moved back to the reachable list.
        1123                 :            :      *
        1124                 :            :      * So instead of not moving at all, the reachable objects B and A are moved
        1125                 :            :      * twice each.  Why is this a win?  A straightforward algorithm to move the
        1126                 :            :      * reachable objects instead would move A, B, and C once each.
        1127                 :            :      *
        1128                 :            :      * The key is that this dance leaves the objects in order C, B, A - it's
        1129                 :            :      * reversed from the original order.  On all _subsequent_ scans, none of
        1130                 :            :      * them will move.  Since most objects aren't in cycles, this can save an
        1131                 :            :      * unbounded number of moves across an unbounded number of later collections.
        1132                 :            :      * It can cost more only the first time the chain is scanned.
        1133                 :            :      *
        1134                 :            :      * Drawback:  move_unreachable is also used to find out what's still trash
        1135                 :            :      * after finalizers may resurrect objects.  In _that_ case most unreachable
        1136                 :            :      * objects will remain unreachable, so it would be more efficient to move
        1137                 :            :      * the reachable objects instead.  But this is a one-time cost, probably not
        1138                 :            :      * worth complicating the code to speed just a little.
        1139                 :            :      */
        1140                 :        772 :     gc_list_init(unreachable);
        1141                 :        772 :     move_unreachable(base, unreachable);  // gc_prev is pointer again
        1142                 :            :     validate_list(base, collecting_clear_unreachable_clear);
        1143                 :            :     validate_list(unreachable, collecting_set_unreachable_set);
        1144                 :        772 : }
        1145                 :            :
        1146                 :            : /* Handle objects that may have resurrected after a call to 'finalize_garbage', moving
        1147                 :            :    them to 'old_generation' and placing the rest on 'still_unreachable'.
        1148                 :            :
        1149                 :            :    Contracts:
        1150                 :            :        * After this function 'unreachable' must not be used anymore and 'still_unreachable'
        1151                 :            :          will contain the objects that did not resurrect.
        1152                 :            :
        1153                 :            :        * The "still_unreachable" list must be uninitialized (this function calls
        1154                 :            :          gc_list_init over 'still_unreachable').
        1155                 :            :
        1156                 :            : IMPORTANT: After a call to this function, the 'still_unreachable' set will have the
        1157                 :            : PREV_MARK_COLLECTING set, but the objects in this set are going to be removed so
        1158                 :            : we can skip the expense of clearing the flag to avoid extra iteration. */
        1159                 :            : static inline void
        1160                 :        386 : handle_resurrected_objects(PyGC_Head *unreachable, PyGC_Head* still_unreachable,
        1161                 :            :                            PyGC_Head *old_generation)
        1162                 :            : {
        1163                 :            :     // Remove the PREV_MASK_COLLECTING from unreachable
        1164                 :            :     // to prepare it for a new call to 'deduce_unreachable'
        1165                 :        386 :     gc_list_clear_collecting(unreachable);
        1166                 :            :
        1167                 :            :     // After the call to deduce_unreachable, the 'still_unreachable' set will
        1168                 :            :     // have the PREV_MARK_COLLECTING set, but the objects are going to be
        1169                 :            :     // removed so we can skip the expense of clearing the flag.
        1170                 :        386 :     PyGC_Head* resurrected = unreachable;
        1171                 :        386 :     deduce_unreachable(resurrected, still_unreachable);
        1172                 :        386 :     clear_unreachable_mask(still_unreachable);
        1173                 :            :
        1174                 :            :     // Move the resurrected objects to the old generation for future collection.
        1175                 :        386 :     gc_list_merge(resurrected, old_generation);
        1176                 :        386 : }
        1177                 :            :
        1178                 :            : /* This is the main function.  Read this to understand how the
        1179                 :            :  * collection process works. */
        1180                 :            : static Py_ssize_t
        1181                 :        386 : gc_collect_main(PyThreadState *tstate, int generation,
        1182                 :            :                 Py_ssize_t *n_collected, Py_ssize_t *n_uncollectable,
        1183                 :            :                 int nofail)
        1184                 :            : {
        1185                 :            :     int i;
        1186                 :        386 :     Py_ssize_t m = 0; /* # objects collected */
        1187                 :        386 :     Py_ssize_t n = 0; /* # unreachable objects that couldn't be collected */
        1188                 :            :     PyGC_Head *young; /* the generation we are examining */
        1189                 :            :     PyGC_Head *old; /* next older generation */
        1190                 :            :     PyGC_Head unreachable; /* non-problematic unreachable trash */
        1191                 :            :     PyGC_Head finalizers;  /* objects with, & reachable from, __del__ */
        1192                 :            :     PyGC_Head *gc;
        1193                 :        386 :     _PyTime_t t1 = 0;   /* initialize to prevent a compiler warning */
        1194                 :        386 :     GCState *gcstate = &tstate->interp->gc;
        1195                 :            :
        1196                 :            :     // gc_collect_main() must not be called before _PyGC_Init
        1197                 :            :     // or after _PyGC_Fini()
        1198                 :            :     assert(gcstate->garbage != NULL);
        1199                 :            :     assert(!_PyErr_Occurred(tstate));
        1200                 :            :
        1201         [ -  + ]:        386 :     if (gcstate->debug & DEBUG_STATS) {
        1202                 :          0 :         PySys_WriteStderr("gc: collecting generation %d...\n", generation);
        1203                 :          0 :         show_stats_each_generations(gcstate);
        1204                 :          0 :         t1 = _PyTime_GetPerfCounter();
        1205                 :            :     }
        1206                 :            :
        1207         [ -  + ]:        386 :     if (PyDTrace_GC_START_ENABLED())
        1208                 :          0 :         PyDTrace_GC_START(generation);
        1209                 :            :
        1210                 :            :     /* update collection and allocation counters */
        1211         [ +  + ]:        386 :     if (generation+1 < NUM_GENERATIONS)
        1212                 :        274 :         gcstate->generations[generation+1].count += 1;
        1213         [ +  + ]:       1005 :     for (i = 0; i <= generation; i++)
        1214                 :        619 :         gcstate->generations[i].count = 0;
        1215                 :            :
        1216                 :            :     /* merge younger generations with one we are currently collecting */
        1217         [ +  + ]:        619 :     for (i = 0; i < generation; i++) {
        1218                 :        233 :         gc_list_merge(GEN_HEAD(gcstate, i), GEN_HEAD(gcstate, generation));
        1219                 :            :     }
        1220                 :            :
        1221                 :            :     /* handy references */
        1222                 :        386 :     young = GEN_HEAD(gcstate, generation);
        1223         [ +  + ]:        386 :     if (generation < NUM_GENERATIONS-1)
        1224                 :        274 :         old = GEN_HEAD(gcstate, generation+1);
        1225                 :            :     else
        1226                 :        112 :         old = young;
        1227                 :            :     validate_list(old, collecting_clear_unreachable_clear);
        1228                 :            :
        1229                 :        386 :     deduce_unreachable(young, &unreachable);
        1230                 :            :
        1231                 :        386 :     untrack_tuples(young);
        1232                 :            :     /* Move reachable objects to next generation. */
        1233         [ +  + ]:        386 :     if (young != old) {
        1234         [ +  + ]:        274 :         if (generation == NUM_GENERATIONS - 2) {
        1235                 :          9 :             gcstate->long_lived_pending += gc_list_size(young);
        1236                 :            :         }
        1237                 :        274 :         gc_list_merge(young, old);
        1238                 :            :     }
        1239                 :            :     else {
        1240                 :            :         /* We only un-track dicts in full collections, to avoid quadratic
        1241                 :            :            dict build-up. See issue #14775. */
        1242                 :        112 :         untrack_dicts(young);
        1243                 :        112 :         gcstate->long_lived_pending = 0;
        1244                 :        112 :         gcstate->long_lived_total = gc_list_size(young);
        1245                 :            :     }
        1246                 :            :
        1247                 :            :     /* All objects in unreachable are trash, but objects reachable from
        1248                 :            :      * legacy finalizers (e.g. tp_del) can't safely be deleted.
        1249                 :            :      */
        1250                 :        386 :     gc_list_init(&finalizers);
        1251                 :            :     // NEXT_MASK_UNREACHABLE is cleared here.
        1252                 :            :     // After move_legacy_finalizers(), unreachable is normal list.
        1253                 :        386 :     move_legacy_finalizers(&unreachable, &finalizers);
        1254                 :            :     /* finalizers contains the unreachable objects with a legacy finalizer;
        1255                 :            :      * unreachable objects reachable *from* those are also uncollectable,
        1256                 :            :      * and we move those into the finalizers list too.
        1257                 :            :      */
        1258                 :        386 :     move_legacy_finalizer_reachable(&finalizers);
        1259                 :            :
        1260                 :            :     validate_list(&finalizers, collecting_clear_unreachable_clear);
        1261                 :            :     validate_list(&unreachable, collecting_set_unreachable_clear);
        1262                 :            :
        1263                 :            :     /* Print debugging information. */
        1264         [ -  + ]:        386 :     if (gcstate->debug & DEBUG_COLLECTABLE) {
        1265         [ #  # ]:          0 :         for (gc = GC_NEXT(&unreachable); gc != &unreachable; gc = GC_NEXT(gc)) {
        1266                 :          0 :             debug_cycle("collectable", FROM_GC(gc));
        1267                 :            :         }
        1268                 :            :     }
        1269                 :            :
        1270                 :            :     /* Clear weakrefs and invoke callbacks as necessary. */
        1271                 :        386 :     m += handle_weakrefs(&unreachable, old);
        1272                 :            :
        1273                 :            :     validate_list(old, collecting_clear_unreachable_clear);
        1274                 :            :     validate_list(&unreachable, collecting_set_unreachable_clear);
        1275                 :            :
        1276                 :            :     /* Call tp_finalize on objects which have one. */
        1277                 :        386 :     finalize_garbage(tstate, &unreachable);
        1278                 :            :
        1279                 :            :     /* Handle any objects that may have resurrected after the call
        1280                 :            :      * to 'finalize_garbage' and continue the collection with the
        1281                 :            :      * objects that are still unreachable */
        1282                 :            :     PyGC_Head final_unreachable;
        1283                 :        386 :     handle_resurrected_objects(&unreachable, &final_unreachable, old);
        1284                 :            :
        1285                 :            :     /* Call tp_clear on objects in the final_unreachable set.  This will cause
        1286                 :            :     * the reference cycles to be broken.  It may also cause some objects
        1287                 :            :     * in finalizers to be freed.
        1288                 :            :     */
        1289                 :        386 :     m += gc_list_size(&final_unreachable);
        1290                 :        386 :     delete_garbage(tstate, gcstate, &final_unreachable, old);
        1291                 :            :
        1292                 :            :     /* Collect statistics on uncollectable objects found and print
        1293                 :            :      * debugging information. */
        1294         [ -  + ]:        386 :     for (gc = GC_NEXT(&finalizers); gc != &finalizers; gc = GC_NEXT(gc)) {
        1295                 :          0 :         n++;
        1296         [ #  # ]:          0 :         if (gcstate->debug & DEBUG_UNCOLLECTABLE)
        1297                 :          0 :             debug_cycle("uncollectable", FROM_GC(gc));
        1298                 :            :     }
        1299         [ -  + ]:        386 :     if (gcstate->debug & DEBUG_STATS) {
        1300                 :          0 :         double d = _PyTime_AsSecondsDouble(_PyTime_GetPerfCounter() - t1);
        1301                 :          0 :         PySys_WriteStderr(
        1302                 :            :             "gc: done, %zd unreachable, %zd uncollectable, %.4fs elapsed\n",
        1303                 :            :             n+m, n, d);
        1304                 :            :     }
        1305                 :            :
        1306                 :            :     /* Append instances in the uncollectable set to a Python
        1307                 :            :      * reachable list of garbage.  The programmer has to deal with
        1308                 :            :      * this if they insist on creating this type of structure.
        1309                 :            :      */
        1310                 :        386 :     handle_legacy_finalizers(tstate, gcstate, &finalizers, old);
        1311                 :            :     validate_list(old, collecting_clear_unreachable_clear);
        1312                 :            :
        1313                 :            :     /* Clear free list only during the collection of the highest
        1314                 :            :      * generation */
        1315         [ +  + ]:        386 :     if (generation == NUM_GENERATIONS-1) {
        1316                 :        112 :         clear_freelists(tstate->interp);
        1317                 :            :     }
        1318                 :            :
        1319         [ -  + ]:        386 :     if (_PyErr_Occurred(tstate)) {
        1320         [ #  # ]:          0 :         if (nofail) {
        1321                 :          0 :             _PyErr_Clear(tstate);
        1322                 :            :         }
        1323                 :            :         else {
        1324                 :          0 :             _PyErr_WriteUnraisableMsg("in garbage collection", NULL);
        1325                 :            :         }
        1326                 :            :     }
        1327                 :            :
        1328                 :            :     /* Update stats */
        1329         [ +  + ]:        386 :     if (n_collected) {
        1330                 :        311 :         *n_collected = m;
        1331                 :            :     }
        1332         [ +  + ]:        386 :     if (n_uncollectable) {
        1333                 :        311 :         *n_uncollectable = n;
        1334                 :            :     }
        1335                 :            :
        1336                 :        386 :     struct gc_generation_stats *stats = &gcstate->generation_stats[generation];
        1337                 :        386 :     stats->collections++;
        1338                 :        386 :     stats->collected += m;
        1339                 :        386 :     stats->uncollectable += n;
        1340                 :            :
        1341         [ -  + ]:        386 :     if (PyDTrace_GC_DONE_ENABLED()) {
        1342                 :          0 :         PyDTrace_GC_DONE(n + m);
        1343                 :            :     }
        1344                 :            :
        1345                 :            :     assert(!_PyErr_Occurred(tstate));
        1346                 :        386 :     return n + m;
        1347                 :            : }
        1348                 :            :
        1349                 :            : /* Invoke progress callbacks to notify clients that garbage collection
        1350                 :            :  * is starting or stopping
        1351                 :            :  */
        1352                 :            : static void
        1353                 :        622 : invoke_gc_callback(PyThreadState *tstate, const char *phase,
        1354                 :            :                    int generation, Py_ssize_t collected,
        1355                 :            :                    Py_ssize_t uncollectable)
        1356                 :            : {
        1357                 :            :     assert(!_PyErr_Occurred(tstate));
        1358                 :            :
        1359                 :            :     /* we may get called very early */
        1360                 :        622 :     GCState *gcstate = &tstate->interp->gc;
        1361         [ -  + ]:        622 :     if (gcstate->callbacks == NULL) {
        1362                 :          0 :         return;
        1363                 :            :     }
        1364                 :            :
        1365                 :            :     /* The local variable cannot be rebound, check it for sanity */
        1366                 :            :     assert(PyList_CheckExact(gcstate->callbacks));
        1367                 :        622 :     PyObject *info = NULL;
        1368         [ -  + ]:        622 :     if (PyList_GET_SIZE(gcstate->callbacks) != 0) {
        1369                 :          0 :         info = Py_BuildValue("{sisnsn}",
        1370                 :            :             "generation", generation,
        1371                 :            :             "collected", collected,
        1372                 :            :             "uncollectable", uncollectable);
        1373         [ #  # ]:          0 :         if (info == NULL) {
        1374                 :          0 :             PyErr_WriteUnraisable(NULL);
        1375                 :          0 :             return;
        1376                 :            :         }
        1377                 :            :     }
        1378         [ -  + ]:        622 :     for (Py_ssize_t i=0; i<PyList_GET_SIZE(gcstate->callbacks); i++) {
        1379                 :          0 :         PyObject *r, *cb = PyList_GET_ITEM(gcstate->callbacks, i);
        1380                 :          0 :         Py_INCREF(cb); /* make sure cb doesn't go away */
        1381                 :          0 :         r = PyObject_CallFunction(cb, "sO", phase, info);
        1382         [ #  # ]:          0 :         if (r == NULL) {
        1383                 :          0 :             PyErr_WriteUnraisable(cb);
        1384                 :            :         }
        1385                 :            :         else {
        1386                 :          0 :             Py_DECREF(r);
        1387                 :            :         }
        1388                 :          0 :         Py_DECREF(cb);
        1389                 :            :     }
        1390                 :        622 :     Py_XDECREF(info);
        1391                 :            :     assert(!_PyErr_Occurred(tstate));
        1392                 :            : }
        1393                 :            :
        1394                 :            : /* Perform garbage collection of a generation and invoke
        1395                 :            :  * progress callbacks.
        1396                 :            :  */
        1397                 :            : static Py_ssize_t
        1398                 :        311 : gc_collect_with_callback(PyThreadState *tstate, int generation)
        1399                 :            : {
        1400                 :            :     assert(!_PyErr_Occurred(tstate));
        1401                 :            :     Py_ssize_t result, collected, uncollectable;
        1402                 :        311 :     invoke_gc_callback(tstate, "start", generation, 0, 0);
        1403                 :        311 :     result = gc_collect_main(tstate, generation, &collected, &uncollectable, 0);
        1404                 :        311 :     invoke_gc_callback(tstate, "stop", generation, collected, uncollectable);
        1405                 :            :     assert(!_PyErr_Occurred(tstate));
        1406                 :        311 :     return result;
        1407                 :            : }
        1408                 :            :
        1409                 :            : static Py_ssize_t
        1410                 :        298 : gc_collect_generations(PyThreadState *tstate)
        1411                 :            : {
        1412                 :        298 :     GCState *gcstate = &tstate->interp->gc;
        1413                 :            :     /* Find the oldest generation (highest numbered) where the count
        1414                 :            :      * exceeds the threshold.  Objects in the that generation and
        1415                 :            :      * generations younger than it will be collected. */
        1416                 :        298 :     Py_ssize_t n = 0;
        1417         [ +  + ]:        909 :     for (int i = NUM_GENERATIONS-1; i >= 0; i--) {
        1418         [ +  + ]:        885 :         if (gcstate->generations[i].count > gcstate->generations[i].threshold) {
        1419                 :            :             /* Avoid quadratic performance degradation in number
        1420                 :            :                of tracked objects (see also issue #4074):
        1421                 :            :
        1422                 :            :                To limit the cost of garbage collection, there are two strategies;
        1423                 :            :                  - make each collection faster, e.g. by scanning fewer objects
        1424                 :            :                  - do less collections
        1425                 :            :                This heuristic is about the latter strategy.
        1426                 :            :
        1427                 :            :                In addition to the various configurable thresholds, we only trigger a
        1428                 :            :                full collection if the ratio
        1429                 :            :
        1430                 :            :                 long_lived_pending / long_lived_total
        1431                 :            :
        1432                 :            :                is above a given value (hardwired to 25%).
        1433                 :            :
        1434                 :            :                The reason is that, while "non-full" collections (i.e., collections of
        1435                 :            :                the young and middle generations) will always examine roughly the same
        1436                 :            :                number of objects -- determined by the aforementioned thresholds --,
        1437                 :            :                the cost of a full collection is proportional to the total number of
        1438                 :            :                long-lived objects, which is virtually unbounded.
        1439                 :            :
        1440                 :            :                Indeed, it has been remarked that doing a full collection every
        1441                 :            :                <constant number> of object creations entails a dramatic performance
        1442                 :            :                degradation in workloads which consist in creating and storing lots of
        1443                 :            :                long-lived objects (e.g. building a large list of GC-tracked objects would
        1444                 :            :                show quadratic performance, instead of linear as expected: see issue #4074).
        1445                 :            :
        1446                 :            :                Using the above ratio, instead, yields amortized linear performance in
        1447                 :            :                the total number of objects (the effect of which can be summarized
        1448                 :            :                thusly: "each full garbage collection is more and more costly as the
        1449                 :            :                number of objects grows, but we do fewer and fewer of them").
        1450                 :            :
        1451                 :            :                This heuristic was suggested by Martin von Löwis on python-dev in
        1452                 :            :                June 2008. His original analysis and proposal can be found at:
        1453                 :            :                http://mail.python.org/pipermail/python-dev/2008-June/080579.html
        1454                 :            :             */
        1455         [ -  + ]:        274 :             if (i == NUM_GENERATIONS - 1
        1456         [ #  # ]:          0 :                 && gcstate->long_lived_pending < gcstate->long_lived_total / 4)
        1457                 :          0 :                 continue;
        1458                 :        274 :             n = gc_collect_with_callback(tstate, i);
        1459                 :        274 :             break;
        1460                 :            :         }
        1461                 :            :     }
        1462                 :        298 :     return n;
        1463                 :            : }
        1464                 :            :
        1465                 :            : #include "clinic/gcmodule.c.h"
        1466                 :            :
        1467                 :            : /*[clinic input]
        1468                 :            : gc.enable
        1469                 :            :
        1470                 :            : Enable automatic garbage collection.
        1471                 :            : [clinic start generated code]*/
        1472                 :            :
        1473                 :            : static PyObject *
        1474                 :          0 : gc_enable_impl(PyObject *module)
        1475                 :            : /*[clinic end generated code: output=45a427e9dce9155c input=81ac4940ca579707]*/
        1476                 :            : {
        1477                 :          0 :     PyGC_Enable();
        1478                 :          0 :     Py_RETURN_NONE;
        1479                 :            : }
        1480                 :            :
        1481                 :            : /*[clinic input]
        1482                 :            : gc.disable
        1483                 :            :
        1484                 :            : Disable automatic garbage collection.
        1485                 :            : [clinic start generated code]*/
        1486                 :            :
        1487                 :            : static PyObject *
        1488                 :          0 : gc_disable_impl(PyObject *module)
        1489                 :            : /*[clinic end generated code: output=97d1030f7aa9d279 input=8c2e5a14e800d83b]*/
        1490                 :            : {
        1491                 :          0 :     PyGC_Disable();
        1492                 :          0 :     Py_RETURN_NONE;
        1493                 :            : }
        1494                 :            :
        1495                 :            : /*[clinic input]
        1496                 :            : gc.isenabled -> bool
        1497                 :            :
        1498                 :            : Returns true if automatic garbage collection is enabled.
        1499                 :            : [clinic start generated code]*/
        1500                 :            :
        1501                 :            : static int
        1502                 :          0 : gc_isenabled_impl(PyObject *module)
        1503                 :            : /*[clinic end generated code: output=1874298331c49130 input=30005e0422373b31]*/
        1504                 :            : {
        1505                 :          0 :     return PyGC_IsEnabled();
        1506                 :            : }
        1507                 :            :
        1508                 :            : /*[clinic input]
        1509                 :            : gc.collect -> Py_ssize_t
        1510                 :            :
        1511                 :            :     generation: int(c_default="NUM_GENERATIONS - 1") = 2
        1512                 :            :
        1513                 :            : Run the garbage collector.
        1514                 :            :
        1515                 :            : With no arguments, run a full collection.  The optional argument
        1516                 :            : may be an integer specifying which generation to collect.  A ValueError
        1517                 :            : is raised if the generation number is invalid.
        1518                 :            :
        1519                 :            : The number of unreachable objects is returned.
        1520                 :            : [clinic start generated code]*/
        1521                 :            :
        1522                 :            : static Py_ssize_t
        1523                 :         12 : gc_collect_impl(PyObject *module, int generation)
        1524                 :            : /*[clinic end generated code: output=b697e633043233c7 input=40720128b682d879]*/
        1525                 :            : {
        1526                 :         12 :     PyThreadState *tstate = _PyThreadState_GET();
        1527                 :            :
        1528   [ +  -  -  + ]:         12 :     if (generation < 0 || generation >= NUM_GENERATIONS) {
        1529                 :          0 :         _PyErr_SetString(tstate, PyExc_ValueError, "invalid generation");
        1530                 :          0 :         return -1;
        1531                 :            :     }
        1532                 :            :
        1533                 :         12 :     GCState *gcstate = &tstate->interp->gc;
        1534                 :            :     Py_ssize_t n;
        1535         [ -  + ]:         12 :     if (gcstate->collecting) {
        1536                 :            :         /* already collecting, don't do anything */
        1537                 :          0 :         n = 0;
        1538                 :            :     }
        1539                 :            :     else {
        1540                 :         12 :         gcstate->collecting = 1;
        1541                 :         12 :         n = gc_collect_with_callback(tstate, generation);
        1542                 :         12 :         gcstate->collecting = 0;
        1543                 :            :     }
        1544                 :         12 :     return n;
        1545                 :            : }
        1546                 :            :
        1547                 :            : /*[clinic input]
        1548                 :            : gc.set_debug
        1549                 :            :
        1550                 :            :     flags: int
        1551                 :            :         An integer that can have the following bits turned on:
        1552                 :            :           DEBUG_STATS - Print statistics during collection.
        1553                 :            :           DEBUG_COLLECTABLE - Print collectable objects found.
        1554                 :            :           DEBUG_UNCOLLECTABLE - Print unreachable but uncollectable objects
        1555                 :            :             found.
        1556                 :            :           DEBUG_SAVEALL - Save objects to gc.garbage rather than freeing them.
        1557                 :            :           DEBUG_LEAK - Debug leaking programs (everything but STATS).
        1558                 :            :     /
        1559                 :            :
        1560                 :            : Set the garbage collection debugging flags.
        1561                 :            :
        1562                 :            : Debugging information is written to sys.stderr.
        1563                 :            : [clinic start generated code]*/
        1564                 :            :
        1565                 :            : static PyObject *
        1566                 :          0 : gc_set_debug_impl(PyObject *module, int flags)
        1567                 :            : /*[clinic end generated code: output=7c8366575486b228 input=5e5ce15e84fbed15]*/
        1568                 :            : {
        1569                 :          0 :     GCState *gcstate = get_gc_state();
        1570                 :          0 :     gcstate->debug = flags;
        1571                 :          0 :     Py_RETURN_NONE;
        1572                 :            : }
        1573                 :            :
        1574                 :            : /*[clinic input]
        1575                 :            : gc.get_debug -> int
        1576                 :            :
        1577                 :            : Get the garbage collection debugging flags.
        1578                 :            : [clinic start generated code]*/
        1579                 :            :
        1580                 :            : static int
        1581                 :          0 : gc_get_debug_impl(PyObject *module)
        1582                 :            : /*[clinic end generated code: output=91242f3506cd1e50 input=91a101e1c3b98366]*/
        1583                 :            : {
        1584                 :          0 :     GCState *gcstate = get_gc_state();
        1585                 :          0 :     return gcstate->debug;
        1586                 :            : }
        1587                 :            :
        1588                 :            : PyDoc_STRVAR(gc_set_thresh__doc__,
        1589                 :            : "set_threshold(threshold0, [threshold1, threshold2]) -> None\n"
        1590                 :            : "\n"
        1591                 :            : "Sets the collection thresholds.  Setting threshold0 to zero disables\n"
        1592                 :            : "collection.\n");
        1593                 :            :
        1594                 :            : static PyObject *
        1595                 :          0 : gc_set_threshold(PyObject *self, PyObject *args)
        1596                 :            : {
        1597                 :          0 :     GCState *gcstate = get_gc_state();
        1598         [ #  # ]:          0 :     if (!PyArg_ParseTuple(args, "i|ii:set_threshold",
        1599                 :            :                           &gcstate->generations[0].threshold,
        1600                 :            :                           &gcstate->generations[1].threshold,
        1601                 :            :                           &gcstate->generations[2].threshold))
        1602                 :          0 :         return NULL;
        1603         [ #  # ]:          0 :     for (int i = 3; i < NUM_GENERATIONS; i++) {
        1604                 :            :         /* generations higher than 2 get the same threshold */
        1605                 :          0 :         gcstate->generations[i].threshold = gcstate->generations[2].threshold;
        1606                 :            :     }
        1607                 :          0 :     Py_RETURN_NONE;
        1608                 :            : }
        1609                 :            :
        1610                 :            : /*[clinic input]
        1611                 :            : gc.get_threshold
        1612                 :            :
        1613                 :            : Return the current collection thresholds.
        1614                 :            : [clinic start generated code]*/
        1615                 :            :
        1616                 :            : static PyObject *
        1617                 :          0 : gc_get_threshold_impl(PyObject *module)
        1618                 :            : /*[clinic end generated code: output=7902bc9f41ecbbd8 input=286d79918034d6e6]*/
        1619                 :            : {
        1620                 :          0 :     GCState *gcstate = get_gc_state();
        1621                 :          0 :     return Py_BuildValue("(iii)",
        1622                 :            :                          gcstate->generations[0].threshold,
        1623                 :            :                          gcstate->generations[1].threshold,
        1624                 :            :                          gcstate->generations[2].threshold);
        1625                 :            : }
        1626                 :            :
        1627                 :            : /*[clinic input]
        1628                 :            : gc.get_count
        1629                 :            :
        1630                 :            : Return a three-tuple of the current collection counts.
        1631                 :            : [clinic start generated code]*/
        1632                 :            :
        1633                 :            : static PyObject *
        1634                 :          0 : gc_get_count_impl(PyObject *module)
        1635                 :            : /*[clinic end generated code: output=354012e67b16398f input=a392794a08251751]*/
        1636                 :            : {
        1637                 :          0 :     GCState *gcstate = get_gc_state();
        1638                 :          0 :     return Py_BuildValue("(iii)",
        1639                 :            :                          gcstate->generations[0].count,
        1640                 :            :                          gcstate->generations[1].count,
        1641                 :            :                          gcstate->generations[2].count);
        1642                 :            : }
        1643                 :            :
        1644                 :            : static int
        1645                 :          0 : referrersvisit(PyObject* obj, PyObject *objs)
        1646                 :            : {
        1647                 :            :     Py_ssize_t i;
        1648         [ #  # ]:          0 :     for (i = 0; i < PyTuple_GET_SIZE(objs); i++)
        1649         [ #  # ]:          0 :         if (PyTuple_GET_ITEM(objs, i) == obj)
        1650                 :          0 :             return 1;
        1651                 :          0 :     return 0;
        1652                 :            : }
        1653                 :            :
        1654                 :            : static int
        1655                 :          0 : gc_referrers_for(PyObject *objs, PyGC_Head *list, PyObject *resultlist)
        1656                 :            : {
        1657                 :            :     PyGC_Head *gc;
        1658                 :            :     PyObject *obj;
        1659                 :            :     traverseproc traverse;
        1660         [ #  # ]:          0 :     for (gc = GC_NEXT(list); gc != list; gc = GC_NEXT(gc)) {
        1661                 :          0 :         obj = FROM_GC(gc);
        1662                 :          0 :         traverse = Py_TYPE(obj)->tp_traverse;
        1663   [ #  #  #  # ]:          0 :         if (obj == objs || obj == resultlist)
        1664                 :          0 :             continue;
        1665         [ #  # ]:          0 :         if (traverse(obj, (visitproc)referrersvisit, objs)) {
        1666         [ #  # ]:          0 :             if (PyList_Append(resultlist, obj) < 0)
        1667                 :          0 :                 return 0; /* error */
        1668                 :            :         }
        1669                 :            :     }
        1670                 :          0 :     return 1; /* no error */
        1671                 :            : }
        1672                 :            :
        1673                 :            : PyDoc_STRVAR(gc_get_referrers__doc__,
        1674                 :            : "get_referrers(*objs) -> list\n\
        1675                 :            : Return the list of objects that directly refer to any of objs.");
        1676                 :            :
        1677                 :            : static PyObject *
        1678                 :          0 : gc_get_referrers(PyObject *self, PyObject *args)
        1679                 :            : {
        1680         [ #  # ]:          0 :     if (PySys_Audit("gc.get_referrers", "(O)", args) < 0) {
        1681                 :          0 :         return NULL;
        1682                 :            :     }
        1683                 :            :
        1684                 :          0 :     PyObject *result = PyList_New(0);
        1685         [ #  # ]:          0 :     if (!result) {
        1686                 :          0 :         return NULL;
        1687                 :            :     }
        1688                 :            :
        1689                 :          0 :     GCState *gcstate = get_gc_state();
        1690         [ #  # ]:          0 :     for (int i = 0; i < NUM_GENERATIONS; i++) {
        1691         [ #  # ]:          0 :         if (!(gc_referrers_for(args, GEN_HEAD(gcstate, i), result))) {
        1692                 :          0 :             Py_DECREF(result);
        1693                 :          0 :             return NULL;
        1694                 :            :         }
        1695                 :            :     }
        1696                 :          0 :     return result;
        1697                 :            : }
        1698                 :            :
        1699                 :            : /* Append obj to list; return true if error (out of memory), false if OK. */
        1700                 :            : static int
        1701                 :          0 : referentsvisit(PyObject *obj, PyObject *list)
        1702                 :            : {
        1703                 :          0 :     return PyList_Append(list, obj) < 0;
        1704                 :            : }
        1705                 :            :
        1706                 :            : PyDoc_STRVAR(gc_get_referents__doc__,
        1707                 :            : "get_referents(*objs) -> list\n\
        1708                 :            : Return the list of objects that are directly referred to by objs.");
        1709                 :            :
        1710                 :            : static PyObject *
        1711                 :          0 : gc_get_referents(PyObject *self, PyObject *args)
        1712                 :            : {
        1713                 :            :     Py_ssize_t i;
        1714         [ #  # ]:          0 :     if (PySys_Audit("gc.get_referents", "(O)", args) < 0) {
        1715                 :          0 :         return NULL;
        1716                 :            :     }
        1717                 :          0 :     PyObject *result = PyList_New(0);
        1718                 :            :
        1719         [ #  # ]:          0 :     if (result == NULL)
        1720                 :          0 :         return NULL;
        1721                 :            :
        1722         [ #  # ]:          0 :     for (i = 0; i < PyTuple_GET_SIZE(args); i++) {
        1723                 :            :         traverseproc traverse;
        1724                 :          0 :         PyObject *obj = PyTuple_GET_ITEM(args, i);
        1725                 :            :
        1726         [ #  # ]:          0 :         if (!_PyObject_IS_GC(obj))
        1727                 :          0 :             continue;
        1728                 :          0 :         traverse = Py_TYPE(obj)->tp_traverse;
        1729         [ #  # ]:          0 :         if (! traverse)
        1730                 :          0 :             continue;
        1731         [ #  # ]:          0 :         if (traverse(obj, (visitproc)referentsvisit, result)) {
        1732                 :          0 :             Py_DECREF(result);
        1733                 :          0 :             return NULL;
        1734                 :            :         }
        1735                 :            :     }
        1736                 :          0 :     return result;
        1737                 :            : }
        1738                 :            :
        1739                 :            : /*[clinic input]
        1740                 :            : gc.get_objects
        1741                 :            :     generation: Py_ssize_t(accept={int, NoneType}, c_default="-1") = None
        1742                 :            :         Generation to extract the objects from.
        1743                 :            :
        1744                 :            : Return a list of objects tracked by the collector (excluding the list returned).
        1745                 :            :
        1746                 :            : If generation is not None, return only the objects tracked by the collector
        1747                 :            : that are in that generation.
        1748                 :            : [clinic start generated code]*/
        1749                 :            :
        1750                 :            : static PyObject *
        1751                 :          0 : gc_get_objects_impl(PyObject *module, Py_ssize_t generation)
        1752                 :            : /*[clinic end generated code: output=48b35fea4ba6cb0e input=ef7da9df9806754c]*/
        1753                 :            : {
        1754                 :          0 :     PyThreadState *tstate = _PyThreadState_GET();
        1755                 :            :     int i;
        1756                 :            :     PyObject* result;
        1757                 :          0 :     GCState *gcstate = &tstate->interp->gc;
        1758                 :            :
        1759         [ #  # ]:          0 :     if (PySys_Audit("gc.get_objects", "n", generation) < 0) {
        1760                 :          0 :         return NULL;
        1761                 :            :     }
        1762                 :            :
        1763                 :          0 :     result = PyList_New(0);
        1764         [ #  # ]:          0 :     if (result == NULL) {
        1765                 :          0 :         return NULL;
        1766                 :            :     }
        1767                 :            :
        1768                 :            :     /* If generation is passed, we extract only that generation */
        1769         [ #  # ]:          0 :     if (generation != -1) {
        1770         [ #  # ]:          0 :         if (generation >= NUM_GENERATIONS) {
        1771                 :          0 :             _PyErr_Format(tstate, PyExc_ValueError,
        1772                 :            :                           "generation parameter must be less than the number of "
        1773                 :            :                           "available generations (%i)",
        1774                 :            :                            NUM_GENERATIONS);
        1775                 :          0 :             goto error;
        1776                 :            :         }
        1777                 :            :
        1778         [ #  # ]:          0 :         if (generation < 0) {
        1779                 :          0 :             _PyErr_SetString(tstate, PyExc_ValueError,
        1780                 :            :                              "generation parameter cannot be negative");
        1781                 :          0 :             goto error;
        1782                 :            :         }
        1783                 :            :
        1784         [ #  # ]:          0 :         if (append_objects(result, GEN_HEAD(gcstate, generation))) {
        1785                 :          0 :             goto error;
        1786                 :            :         }
        1787                 :            :
        1788                 :          0 :         return result;
        1789                 :            :     }
        1790                 :            :
        1791                 :            :     /* If generation is not passed or None, get all objects from all generations */
        1792         [ #  # ]:          0 :     for (i = 0; i < NUM_GENERATIONS; i++) {
        1793         [ #  # ]:          0 :         if (append_objects(result, GEN_HEAD(gcstate, i))) {
        1794                 :          0 :             goto error;
        1795                 :            :         }
        1796                 :            :     }
        1797                 :          0 :     return result;
        1798                 :            :
        1799                 :          0 : error:
        1800                 :          0 :     Py_DECREF(result);
        1801                 :          0 :     return NULL;
        1802                 :            : }
        1803                 :            :
        1804                 :            : /*[clinic input]
        1805                 :            : gc.get_stats
        1806                 :            :
        1807                 :            : Return a list of dictionaries containing per-generation statistics.
        1808                 :            : [clinic start generated code]*/
        1809                 :            :
        1810                 :            : static PyObject *
        1811                 :          0 : gc_get_stats_impl(PyObject *module)
        1812                 :            : /*[clinic end generated code: output=a8ab1d8a5d26f3ab input=1ef4ed9d17b1a470]*/
        1813                 :            : {
        1814                 :            :     int i;
        1815                 :            :     struct gc_generation_stats stats[NUM_GENERATIONS], *st;
        1816                 :            :
        1817                 :            :     /* To get consistent values despite allocations while constructing
        1818                 :            :        the result list, we use a snapshot of the running stats. */
        1819                 :          0 :     GCState *gcstate = get_gc_state();
        1820         [ #  # ]:          0 :     for (i = 0; i < NUM_GENERATIONS; i++) {
        1821                 :          0 :         stats[i] = gcstate->generation_stats[i];
        1822                 :            :     }
        1823                 :            :
        1824                 :          0 :     PyObject *result = PyList_New(0);
        1825         [ #  # ]:          0 :     if (result == NULL)
        1826                 :          0 :         return NULL;
        1827                 :            :
        1828         [ #  # ]:          0 :     for (i = 0; i < NUM_GENERATIONS; i++) {
        1829                 :            :         PyObject *dict;
        1830                 :          0 :         st = &stats[i];
        1831                 :          0 :         dict = Py_BuildValue("{snsnsn}",
        1832                 :            :                              "collections", st->collections,
        1833                 :            :                              "collected", st->collected,
        1834                 :            :                              "uncollectable", st->uncollectable
        1835                 :            :                             );
        1836         [ #  # ]:          0 :         if (dict == NULL)
        1837                 :          0 :             goto error;
        1838         [ #  # ]:          0 :         if (PyList_Append(result, dict)) {
        1839                 :          0 :             Py_DECREF(dict);
        1840                 :          0 :             goto error;
        1841                 :            :         }
        1842                 :          0 :         Py_DECREF(dict);
        1843                 :            :     }
        1844                 :          0 :     return result;
        1845                 :            :
        1846                 :          0 : error:
        1847                 :          0 :     Py_XDECREF(result);
        1848                 :          0 :     return NULL;
        1849                 :            : }
        1850                 :            :
        1851                 :            :
        1852                 :            : /*[clinic input]
        1853                 :            : gc.is_tracked
        1854                 :            :
        1855                 :            :     obj: object
        1856                 :            :     /
        1857                 :            :
        1858                 :            : Returns true if the object is tracked by the garbage collector.
        1859                 :            :
        1860                 :            : Simple atomic objects will return false.
        1861                 :            : [clinic start generated code]*/
        1862                 :            :
        1863                 :            : static PyObject *
        1864                 :          0 : gc_is_tracked(PyObject *module, PyObject *obj)
        1865                 :            : /*[clinic end generated code: output=14f0103423b28e31 input=d83057f170ea2723]*/
        1866                 :            : {
        1867                 :            :     PyObject *result;
        1868                 :            :
        1869   [ #  #  #  # ]:          0 :     if (_PyObject_IS_GC(obj) && _PyObject_GC_IS_TRACKED(obj))
        1870                 :          0 :         result = Py_True;
        1871                 :            :     else
        1872                 :          0 :         result = Py_False;
        1873                 :          0 :     return Py_NewRef(result);
        1874                 :            : }
        1875                 :            :
        1876                 :            : /*[clinic input]
        1877                 :            : gc.is_finalized
        1878                 :            :
        1879                 :            :     obj: object
        1880                 :            :     /
        1881                 :            :
        1882                 :            : Returns true if the object has been already finalized by the GC.
        1883                 :            : [clinic start generated code]*/
        1884                 :            :
        1885                 :            : static PyObject *
        1886                 :          0 : gc_is_finalized(PyObject *module, PyObject *obj)
        1887                 :            : /*[clinic end generated code: output=e1516ac119a918ed input=201d0c58f69ae390]*/
        1888                 :            : {
        1889   [ #  #  #  # ]:          0 :     if (_PyObject_IS_GC(obj) && _PyGCHead_FINALIZED(AS_GC(obj))) {
        1890                 :          0 :          Py_RETURN_TRUE;
        1891                 :            :     }
        1892                 :          0 :     Py_RETURN_FALSE;
        1893                 :            : }
        1894                 :            :
        1895                 :            : /*[clinic input]
        1896                 :            : gc.freeze
        1897                 :            :
        1898                 :            : Freeze all current tracked objects and ignore them for future collections.
        1899                 :            :
        1900                 :            : This can be used before a POSIX fork() call to make the gc copy-on-write friendly.
        1901                 :            : Note: collection before a POSIX fork() call may free pages for future allocation
        1902                 :            : which can cause copy-on-write.
        1903                 :            : [clinic start generated code]*/
        1904                 :            :
        1905                 :            : static PyObject *
        1906                 :          0 : gc_freeze_impl(PyObject *module)
        1907                 :            : /*[clinic end generated code: output=502159d9cdc4c139 input=b602b16ac5febbe5]*/
        1908                 :            : {
        1909                 :          0 :     GCState *gcstate = get_gc_state();
        1910         [ #  # ]:          0 :     for (int i = 0; i < NUM_GENERATIONS; ++i) {
        1911                 :          0 :         gc_list_merge(GEN_HEAD(gcstate, i), &gcstate->permanent_generation.head);
        1912                 :          0 :         gcstate->generations[i].count = 0;
        1913                 :            :     }
        1914                 :          0 :     Py_RETURN_NONE;
        1915                 :            : }
        1916                 :            :
        1917                 :            : /*[clinic input]
        1918                 :            : gc.unfreeze
        1919                 :            :
        1920                 :            : Unfreeze all objects in the permanent generation.
        1921                 :            :
        1922                 :            : Put all objects in the permanent generation back into oldest generation.
        1923                 :            : [clinic start generated code]*/
        1924                 :            :
        1925                 :            : static PyObject *
        1926                 :          0 : gc_unfreeze_impl(PyObject *module)
        1927                 :            : /*[clinic end generated code: output=1c15f2043b25e169 input=2dd52b170f4cef6c]*/
        1928                 :            : {
        1929                 :          0 :     GCState *gcstate = get_gc_state();
        1930                 :          0 :     gc_list_merge(&gcstate->permanent_generation.head,
        1931                 :            :                   GEN_HEAD(gcstate, NUM_GENERATIONS-1));
        1932                 :          0 :     Py_RETURN_NONE;
        1933                 :            : }
        1934                 :            :
        1935                 :            : /*[clinic input]
        1936                 :            : gc.get_freeze_count -> Py_ssize_t
        1937                 :            :
        1938                 :            : Return the number of objects in the permanent generation.
        1939                 :            : [clinic start generated code]*/
        1940                 :            :
        1941                 :            : static Py_ssize_t
        1942                 :          0 : gc_get_freeze_count_impl(PyObject *module)
        1943                 :            : /*[clinic end generated code: output=61cbd9f43aa032e1 input=45ffbc65cfe2a6ed]*/
        1944                 :            : {
        1945                 :          0 :     GCState *gcstate = get_gc_state();
        1946                 :          0 :     return gc_list_size(&gcstate->permanent_generation.head);
        1947                 :            : }
        1948                 :            :
        1949                 :            :
        1950                 :            : PyDoc_STRVAR(gc__doc__,
        1951                 :            : "This module provides access to the garbage collector for reference cycles.\n"
        1952                 :            : "\n"
        1953                 :            : "enable() -- Enable automatic garbage collection.\n"
        1954                 :            : "disable() -- Disable automatic garbage collection.\n"
        1955                 :            : "isenabled() -- Returns true if automatic collection is enabled.\n"
        1956                 :            : "collect() -- Do a full collection right now.\n"
        1957                 :            : "get_count() -- Return the current collection counts.\n"
        1958                 :            : "get_stats() -- Return list of dictionaries containing per-generation stats.\n"
        1959                 :            : "set_debug() -- Set debugging flags.\n"
        1960                 :            : "get_debug() -- Get debugging flags.\n"
        1961                 :            : "set_threshold() -- Set the collection thresholds.\n"
        1962                 :            : "get_threshold() -- Return the current the collection thresholds.\n"
        1963                 :            : "get_objects() -- Return a list of all objects tracked by the collector.\n"
        1964                 :            : "is_tracked() -- Returns true if a given object is tracked.\n"
        1965                 :            : "is_finalized() -- Returns true if a given object has been already finalized.\n"
        1966                 :            : "get_referrers() -- Return the list of objects that refer to an object.\n"
        1967                 :            : "get_referents() -- Return the list of objects that an object refers to.\n"
        1968                 :            : "freeze() -- Freeze all tracked objects and ignore them for future collections.\n"
        1969                 :            : "unfreeze() -- Unfreeze all objects in the permanent generation.\n"
        1970                 :            : "get_freeze_count() -- Return the number of objects in the permanent generation.\n");
        1971                 :            :
        1972                 :            : static PyMethodDef GcMethods[] = {
        1973                 :            :     GC_ENABLE_METHODDEF
        1974                 :            :     GC_DISABLE_METHODDEF
        1975                 :            :     GC_ISENABLED_METHODDEF
        1976                 :            :     GC_SET_DEBUG_METHODDEF
        1977                 :            :     GC_GET_DEBUG_METHODDEF
        1978                 :            :     GC_GET_COUNT_METHODDEF
        1979                 :            :     {"set_threshold",  gc_set_threshold, METH_VARARGS, gc_set_thresh__doc__},
        1980                 :            :     GC_GET_THRESHOLD_METHODDEF
        1981                 :            :     GC_COLLECT_METHODDEF
        1982                 :            :     GC_GET_OBJECTS_METHODDEF
        1983                 :            :     GC_GET_STATS_METHODDEF
        1984                 :            :     GC_IS_TRACKED_METHODDEF
        1985                 :            :     GC_IS_FINALIZED_METHODDEF
        1986                 :            :     {"get_referrers",  gc_get_referrers, METH_VARARGS,
        1987                 :            :         gc_get_referrers__doc__},
        1988                 :            :     {"get_referents",  gc_get_referents, METH_VARARGS,
        1989                 :            :         gc_get_referents__doc__},
        1990                 :            :     GC_FREEZE_METHODDEF
        1991                 :            :     GC_UNFREEZE_METHODDEF
        1992                 :            :     GC_GET_FREEZE_COUNT_METHODDEF
        1993                 :            :     {NULL,      NULL}           /* Sentinel */
        1994                 :            : };
        1995                 :            :
        1996                 :            : static int
        1997                 :          2 : gcmodule_exec(PyObject *module)
        1998                 :            : {
        1999                 :          2 :     GCState *gcstate = get_gc_state();
        2000                 :            :
        2001                 :            :     /* garbage and callbacks are initialized by _PyGC_Init() early in
        2002                 :            :      * interpreter lifecycle. */
        2003                 :            :     assert(gcstate->garbage != NULL);
        2004         [ -  + ]:          2 :     if (PyModule_AddObjectRef(module, "garbage", gcstate->garbage) < 0) {
        2005                 :          0 :         return -1;
        2006                 :            :     }
        2007                 :            :     assert(gcstate->callbacks != NULL);
        2008         [ -  + ]:          2 :     if (PyModule_AddObjectRef(module, "callbacks", gcstate->callbacks) < 0) {
        2009                 :          0 :         return -1;
        2010                 :            :     }
        2011                 :            :
        2012                 :            : #define ADD_INT(NAME) if (PyModule_AddIntConstant(module, #NAME, NAME) < 0) { return -1; }
        2013         [ -  + ]:          2 :     ADD_INT(DEBUG_STATS);
        2014         [ -  + ]:          2 :     ADD_INT(DEBUG_COLLECTABLE);
        2015         [ -  + ]:          2 :     ADD_INT(DEBUG_UNCOLLECTABLE);
        2016         [ -  + ]:          2 :     ADD_INT(DEBUG_SAVEALL);
        2017         [ -  + ]:          2 :     ADD_INT(DEBUG_LEAK);
        2018                 :            : #undef ADD_INT
        2019                 :          2 :     return 0;
        2020                 :            : }
        2021                 :            :
        2022                 :            : static PyModuleDef_Slot gcmodule_slots[] = {
        2023                 :            :     {Py_mod_exec, gcmodule_exec},
        2024                 :            :     {0, NULL}
        2025                 :            : };
        2026                 :            :
        2027                 :            : static struct PyModuleDef gcmodule = {
        2028                 :            :     PyModuleDef_HEAD_INIT,
        2029                 :            :     .m_name = "gc",
        2030                 :            :     .m_doc = gc__doc__,
        2031                 :            :     .m_size = 0,  // per interpreter state, see: get_gc_state()
        2032                 :            :     .m_methods = GcMethods,
        2033                 :            :     .m_slots = gcmodule_slots
        2034                 :            : };
        2035                 :            :
        2036                 :            : PyMODINIT_FUNC
        2037                 :          2 : PyInit_gc(void)
        2038                 :            : {
        2039                 :          2 :     return PyModuleDef_Init(&gcmodule);
        2040                 :            : }
        2041                 :            :
        2042                 :            : /* C API for controlling the state of the garbage collector */
        2043                 :            : int
        2044                 :          0 : PyGC_Enable(void)
        2045                 :            : {
        2046                 :          0 :     GCState *gcstate = get_gc_state();
        2047                 :          0 :     int old_state = gcstate->enabled;
        2048                 :          0 :     gcstate->enabled = 1;
        2049                 :          0 :     return old_state;
        2050                 :            : }
        2051                 :            :
        2052                 :            : int
        2053                 :          0 : PyGC_Disable(void)
        2054                 :            : {
        2055                 :          0 :     GCState *gcstate = get_gc_state();
        2056                 :          0 :     int old_state = gcstate->enabled;
        2057                 :          0 :     gcstate->enabled = 0;
        2058                 :          0 :     return old_state;
        2059                 :            : }
        2060                 :            :
        2061                 :            : int
        2062                 :          0 : PyGC_IsEnabled(void)
        2063                 :            : {
        2064                 :          0 :     GCState *gcstate = get_gc_state();
        2065                 :          0 :     return gcstate->enabled;
        2066                 :            : }
        2067                 :            :
        2068                 :            : /* Public API to invoke gc.collect() from C */
        2069                 :            : Py_ssize_t
        2070                 :         25 : PyGC_Collect(void)
        2071                 :            : {
        2072                 :         25 :     PyThreadState *tstate = _PyThreadState_GET();
        2073                 :         25 :     GCState *gcstate = &tstate->interp->gc;
        2074                 :            :
        2075         [ -  + ]:         25 :     if (!gcstate->enabled) {
        2076                 :          0 :         return 0;
        2077                 :            :     }
        2078                 :            :
        2079                 :            :     Py_ssize_t n;
        2080         [ -  + ]:         25 :     if (gcstate->collecting) {
        2081                 :            :         /* already collecting, don't do anything */
        2082                 :          0 :         n = 0;
        2083                 :            :     }
        2084                 :            :     else {
        2085                 :         25 :         gcstate->collecting = 1;
        2086                 :         25 :         PyObject *exc = _PyErr_GetRaisedException(tstate);
        2087                 :         25 :         n = gc_collect_with_callback(tstate, NUM_GENERATIONS - 1);
        2088                 :         25 :         _PyErr_SetRaisedException(tstate, exc);
        2089                 :         25 :         gcstate->collecting = 0;
        2090                 :            :     }
        2091                 :            :
        2092                 :         25 :     return n;
        2093                 :            : }
        2094                 :            :
        2095                 :            : Py_ssize_t
        2096                 :         75 : _PyGC_CollectNoFail(PyThreadState *tstate)
        2097                 :            : {
        2098                 :            :     /* Ideally, this function is only called on interpreter shutdown,
        2099                 :            :        and therefore not recursively.  Unfortunately, when there are daemon
        2100                 :            :        threads, a daemon thread can start a cyclic garbage collection
        2101                 :            :        during interpreter shutdown (and then never finish it).
        2102                 :            :        See http://bugs.python.org/issue8713#msg195178 for an example.
        2103                 :            :        */
        2104                 :         75 :     GCState *gcstate = &tstate->interp->gc;
        2105         [ -  + ]:         75 :     if (gcstate->collecting) {
        2106                 :          0 :         return 0;
        2107                 :            :     }
        2108                 :            :
        2109                 :            :     Py_ssize_t n;
        2110                 :         75 :     gcstate->collecting = 1;
        2111                 :         75 :     n = gc_collect_main(tstate, NUM_GENERATIONS - 1, NULL, NULL, 1);
        2112                 :         75 :     gcstate->collecting = 0;
        2113                 :         75 :     return n;
        2114                 :            : }
        2115                 :            :
        2116                 :            : void
        2117                 :         25 : _PyGC_DumpShutdownStats(PyInterpreterState *interp)
        2118                 :            : {
        2119                 :         25 :     GCState *gcstate = &interp->gc;
        2120         [ +  - ]:         25 :     if (!(gcstate->debug & DEBUG_SAVEALL)
        2121   [ +  -  -  + ]:         25 :         && gcstate->garbage != NULL && PyList_GET_SIZE(gcstate->garbage) > 0) {
        2122                 :            :         const char *message;
        2123         [ #  # ]:          0 :         if (gcstate->debug & DEBUG_UNCOLLECTABLE)
        2124                 :          0 :             message = "gc: %zd uncollectable objects at " \
        2125                 :            :                 "shutdown";
        2126                 :            :         else
        2127                 :          0 :             message = "gc: %zd uncollectable objects at " \
        2128                 :            :                 "shutdown; use gc.set_debug(gc.DEBUG_UNCOLLECTABLE) to list them";
        2129                 :            :         /* PyErr_WarnFormat does too many things and we are at shutdown,
        2130                 :            :            the warnings module's dependencies (e.g. linecache) may be gone
        2131                 :            :            already. */
        2132         [ #  # ]:          0 :         if (PyErr_WarnExplicitFormat(PyExc_ResourceWarning, "gc", 0,
        2133                 :            :                                      "gc", NULL, message,
        2134                 :            :                                      PyList_GET_SIZE(gcstate->garbage)))
        2135                 :          0 :             PyErr_WriteUnraisable(NULL);
        2136         [ #  # ]:          0 :         if (gcstate->debug & DEBUG_UNCOLLECTABLE) {
        2137                 :          0 :             PyObject *repr = NULL, *bytes = NULL;
        2138                 :          0 :             repr = PyObject_Repr(gcstate->garbage);
        2139   [ #  #  #  # ]:          0 :             if (!repr || !(bytes = PyUnicode_EncodeFSDefault(repr)))
        2140                 :          0 :                 PyErr_WriteUnraisable(gcstate->garbage);
        2141                 :            :             else {
        2142                 :          0 :                 PySys_WriteStderr(
        2143                 :            :                     "      %s\n",
        2144                 :            :                     PyBytes_AS_STRING(bytes)
        2145                 :            :                     );
        2146                 :            :             }
        2147                 :          0 :             Py_XDECREF(repr);
        2148                 :          0 :             Py_XDECREF(bytes);
        2149                 :            :         }
        2150                 :            :     }
        2151                 :         25 : }
        2152                 :            :
        2153                 :            :
        2154                 :            : static void
        2155                 :          0 : gc_fini_untrack(PyGC_Head *list)
        2156                 :            : {
        2157                 :            :     PyGC_Head *gc;
        2158         [ #  # ]:          0 :     for (gc = GC_NEXT(list); gc != list; gc = GC_NEXT(list)) {
        2159                 :          0 :         PyObject *op = FROM_GC(gc);
        2160                 :          0 :         _PyObject_GC_UNTRACK(op);
        2161                 :            :         // gh-92036: If a deallocator function expect the object to be tracked
        2162                 :            :         // by the GC (ex: func_dealloc()), it can crash if called on an object
        2163                 :            :         // which is no longer tracked by the GC. Leak one strong reference on
        2164                 :            :         // purpose so the object is never deleted and its deallocator is not
        2165                 :            :         // called.
        2166                 :          0 :         Py_INCREF(op);
        2167                 :            :     }
        2168                 :          0 : }
        2169                 :            :
        2170                 :            :
        2171                 :            : void
        2172                 :         25 : _PyGC_Fini(PyInterpreterState *interp)
        2173                 :            : {
        2174                 :         25 :     GCState *gcstate = &interp->gc;
        2175         [ +  - ]:         25 :     Py_CLEAR(gcstate->garbage);
        2176         [ +  - ]:         25 :     Py_CLEAR(gcstate->callbacks);
        2177                 :            :
        2178         [ -  + ]:         25 :     if (!_Py_IsMainInterpreter(interp)) {
        2179                 :            :         // bpo-46070: Explicitly untrack all objects currently tracked by the
        2180                 :            :         // GC. Otherwise, if an object is used later by another interpreter,
        2181                 :            :         // calling PyObject_GC_UnTrack() on the object crashs if the previous
        2182                 :            :         // or the next object of the PyGC_Head structure became a dangling
        2183                 :            :         // pointer.
        2184         [ #  # ]:          0 :         for (int i = 0; i < NUM_GENERATIONS; i++) {
        2185                 :          0 :             PyGC_Head *gen = GEN_HEAD(gcstate, i);
        2186                 :          0 :             gc_fini_untrack(gen);
        2187                 :            :         }
        2188                 :            :     }
        2189                 :         25 : }
        2190                 :            :
        2191                 :            : /* for debugging */
        2192                 :            : void
        2193                 :          0 : _PyGC_Dump(PyGC_Head *g)
        2194                 :            : {
        2195                 :          0 :     _PyObject_Dump(FROM_GC(g));
        2196                 :          0 : }
        2197                 :            :
        2198                 :            :
        2199                 :            : #ifdef Py_DEBUG
        2200                 :            : static int
        2201                 :            : visit_validate(PyObject *op, void *parent_raw)
        2202                 :            : {
        2203                 :            :     PyObject *parent = _PyObject_CAST(parent_raw);
        2204                 :            :     if (_PyObject_IsFreed(op)) {
        2205                 :            :         _PyObject_ASSERT_FAILED_MSG(parent,
        2206                 :            :                                     "PyObject_GC_Track() object is not valid");
        2207                 :            :     }
        2208                 :            :     return 0;
        2209                 :            : }
        2210                 :            : #endif
        2211                 :            :
        2212                 :            :
        2213                 :            : /* extension modules might be compiled with GC support so these
        2214                 :            :    functions must always be available */
        2215                 :            :
        2216                 :            : void
        2217                 :    1572233 : PyObject_GC_Track(void *op_raw)
        2218                 :            : {
        2219                 :    1572233 :     PyObject *op = _PyObject_CAST(op_raw);
        2220         [ -  + ]:    1572233 :     if (_PyObject_GC_IS_TRACKED(op)) {
        2221                 :          0 :         _PyObject_ASSERT_FAILED_MSG(op,
        2222                 :            :                                     "object already tracked "
        2223                 :            :                                     "by the garbage collector");
        2224                 :            :     }
        2225                 :    1572233 :     _PyObject_GC_TRACK(op);
        2226                 :            :
        2227                 :            : #ifdef Py_DEBUG
        2228                 :            :     /* Check that the object is valid: validate objects traversed
        2229                 :            :        by tp_traverse() */
        2230                 :            :     traverseproc traverse = Py_TYPE(op)->tp_traverse;
        2231                 :            :     (void)traverse(op, visit_validate, op);
        2232                 :            : #endif
        2233                 :    1572233 : }
        2234                 :            :
        2235                 :            : void
        2236                 :    9406814 : PyObject_GC_UnTrack(void *op_raw)
        2237                 :            : {
        2238                 :    9406814 :     PyObject *op = _PyObject_CAST(op_raw);
        2239                 :            :     /* Obscure:  the Py_TRASHCAN mechanism requires that we be able to
        2240                 :            :      * call PyObject_GC_UnTrack twice on an object.
        2241                 :            :      */
        2242         [ +  + ]:    9406814 :     if (_PyObject_GC_IS_TRACKED(op)) {
        2243                 :    8594260 :         _PyObject_GC_UNTRACK(op);
        2244                 :            :     }
        2245                 :    9406814 : }
        2246                 :            :
        2247                 :            : int
        2248                 :    7502158 : PyObject_IS_GC(PyObject *obj)
        2249                 :            : {
        2250                 :    7502158 :     return _PyObject_IS_GC(obj);
        2251                 :            : }
        2252                 :            :
        2253                 :            : void
        2254                 :     945489 : _Py_ScheduleGC(PyInterpreterState *interp)
        2255                 :            : {
        2256                 :     945489 :     GCState *gcstate = &interp->gc;
        2257         [ -  + ]:     945489 :     if (gcstate->collecting == 1) {
        2258                 :          0 :         return;
        2259                 :            :     }
        2260                 :     945489 :     struct _ceval_state *ceval = &interp->ceval;
        2261         [ +  + ]:     945489 :     if (!_Py_atomic_load_relaxed(&ceval->gc_scheduled)) {
        2262                 :        302 :         _Py_atomic_store_relaxed(&ceval->gc_scheduled, 1);
        2263                 :        302 :         _Py_atomic_store_relaxed(&ceval->eval_breaker, 1);
        2264                 :            :     }
        2265                 :            : }
        2266                 :            :
        2267                 :            : void
        2268                 :    8996350 : _PyObject_GC_Link(PyObject *op)
        2269                 :            : {
        2270                 :    8996350 :     PyGC_Head *g = AS_GC(op);
        2271                 :            :     assert(((uintptr_t)g & (sizeof(uintptr_t)-1)) == 0);  // g must be correctly aligned
        2272                 :            :
        2273                 :    8996350 :     PyThreadState *tstate = _PyThreadState_GET();
        2274                 :    8996350 :     GCState *gcstate = &tstate->interp->gc;
        2275                 :    8996350 :     g->_gc_next = 0;
        2276                 :    8996350 :     g->_gc_prev = 0;
        2277                 :    8996350 :     gcstate->generations[0].count++; /* number of allocated GC objects */
        2278         [ +  + ]:    8996350 :     if (gcstate->generations[0].count > gcstate->generations[0].threshold &&
        2279         [ +  - ]:     945489 :         gcstate->enabled &&
        2280         [ +  - ]:     945489 :         gcstate->generations[0].threshold &&
        2281   [ +  -  +  - ]:    1890978 :         !gcstate->collecting &&
        2282                 :     945489 :         !_PyErr_Occurred(tstate))
        2283                 :            :     {
        2284                 :     945489 :         _Py_ScheduleGC(tstate->interp);
        2285                 :            :     }
        2286                 :    8996350 : }
        2287                 :            :
        2288                 :            : void
        2289                 :        298 : _Py_RunGC(PyThreadState *tstate)
        2290                 :            : {
        2291                 :        298 :     GCState *gcstate = &tstate->interp->gc;
        2292                 :        298 :     gcstate->collecting = 1;
        2293                 :        298 :     gc_collect_generations(tstate);
        2294                 :        298 :     gcstate->collecting = 0;
        2295                 :        298 : }
        2296                 :            :
        2297                 :            : static PyObject *
        2298                 :    7577793 : gc_alloc(size_t basicsize, size_t presize)
        2299                 :            : {
        2300                 :    7577793 :     PyThreadState *tstate = _PyThreadState_GET();
        2301         [ -  + ]:    7577793 :     if (basicsize > PY_SSIZE_T_MAX - presize) {
        2302                 :          0 :         return _PyErr_NoMemory(tstate);
        2303                 :            :     }
        2304                 :    7577793 :     size_t size = presize + basicsize;
        2305                 :    7577793 :     char *mem = PyObject_Malloc(size);
        2306         [ -  + ]:    7577793 :     if (mem == NULL) {
        2307                 :          0 :         return _PyErr_NoMemory(tstate);
        2308                 :            :     }
        2309                 :    7577793 :     ((PyObject **)mem)[0] = NULL;
        2310                 :    7577793 :     ((PyObject **)mem)[1] = NULL;
        2311                 :    7577793 :     PyObject *op = (PyObject *)(mem + presize);
        2312                 :    7577793 :     _PyObject_GC_Link(op);
        2313                 :    7577793 :     return op;
        2314                 :            : }
        2315                 :            :
        2316                 :            : PyObject *
        2317                 :    7219180 : _PyObject_GC_New(PyTypeObject *tp)
        2318                 :            : {
        2319                 :    7219180 :     size_t presize = _PyType_PreHeaderSize(tp);
        2320                 :    7219180 :     PyObject *op = gc_alloc(_PyObject_SIZE(tp), presize);
        2321         [ -  + ]:    7219180 :     if (op == NULL) {
        2322                 :          0 :         return NULL;
        2323                 :            :     }
        2324                 :    7219180 :     _PyObject_Init(op, tp);
        2325                 :    7219180 :     return op;
        2326                 :            : }
        2327                 :            :
        2328                 :            : PyVarObject *
        2329                 :     358613 : _PyObject_GC_NewVar(PyTypeObject *tp, Py_ssize_t nitems)
        2330                 :            : {
        2331                 :            :     PyVarObject *op;
        2332                 :            :
        2333         [ -  + ]:     358613 :     if (nitems < 0) {
        2334                 :          0 :         PyErr_BadInternalCall();
        2335                 :          0 :         return NULL;
        2336                 :            :     }
        2337                 :     358613 :     size_t presize = _PyType_PreHeaderSize(tp);
        2338                 :     358613 :     size_t size = _PyObject_VAR_SIZE(tp, nitems);
        2339                 :     358613 :     op = (PyVarObject *)gc_alloc(size, presize);
        2340         [ -  + ]:     358613 :     if (op == NULL) {
        2341                 :          0 :         return NULL;
        2342                 :            :     }
        2343                 :     358613 :     _PyObject_InitVar(op, tp, nitems);
        2344                 :     358613 :     return op;
        2345                 :            : }
        2346                 :            :
        2347                 :            : PyVarObject *
        2348                 :       2822 : _PyObject_GC_Resize(PyVarObject *op, Py_ssize_t nitems)
        2349                 :            : {
        2350                 :       2822 :     const size_t basicsize = _PyObject_VAR_SIZE(Py_TYPE(op), nitems);
        2351                 :            :     _PyObject_ASSERT((PyObject *)op, !_PyObject_GC_IS_TRACKED(op));
        2352         [ -  + ]:       2822 :     if (basicsize > (size_t)PY_SSIZE_T_MAX - sizeof(PyGC_Head)) {
        2353                 :          0 :         return (PyVarObject *)PyErr_NoMemory();
        2354                 :            :     }
        2355                 :            :
        2356                 :       2822 :     PyGC_Head *g = AS_GC(op);
        2357                 :       2822 :     g = (PyGC_Head *)PyObject_Realloc(g,  sizeof(PyGC_Head) + basicsize);
        2358         [ -  + ]:       2822 :     if (g == NULL)
        2359                 :          0 :         return (PyVarObject *)PyErr_NoMemory();
        2360                 :       2822 :     op = (PyVarObject *) FROM_GC(g);
        2361                 :       2822 :     Py_SET_SIZE(op, nitems);
        2362                 :       2822 :     return op;
        2363                 :            : }
        2364                 :            :
        2365                 :            : void
        2366                 :    8977912 : PyObject_GC_Del(void *op)
        2367                 :            : {
        2368                 :    8977912 :     size_t presize = _PyType_PreHeaderSize(((PyObject *)op)->ob_type);
        2369                 :    8977912 :     PyGC_Head *g = AS_GC(op);
        2370         [ -  + ]:    8977912 :     if (_PyObject_GC_IS_TRACKED(op)) {
        2371                 :            : #ifdef Py_DEBUG
        2372                 :            :         if (PyErr_WarnExplicitFormat(PyExc_ResourceWarning, "gc", 0,
        2373                 :            :                                      "gc", NULL, "Object of type %s is not untracked before destruction",
        2374                 :            :                                      ((PyObject*)op)->ob_type->tp_name)) {
        2375                 :            :             PyErr_WriteUnraisable(NULL);
        2376                 :            :         }
        2377                 :            : #endif
        2378                 :          0 :         gc_list_remove(g);
        2379                 :            :     }
        2380                 :    8977912 :     GCState *gcstate = get_gc_state();
        2381         [ +  + ]:    8977912 :     if (gcstate->generations[0].count > 0) {
        2382                 :    7892674 :         gcstate->generations[0].count--;
        2383                 :            :     }
        2384                 :    8977912 :     PyObject_Free(((char *)op)-presize);
        2385                 :    8977912 : }
        2386                 :            :
        2387                 :            : int
        2388                 :          0 : PyObject_GC_IsTracked(PyObject* obj)
        2389                 :            : {
        2390   [ #  #  #  # ]:          0 :     if (_PyObject_IS_GC(obj) && _PyObject_GC_IS_TRACKED(obj)) {
        2391                 :          0 :         return 1;
        2392                 :            :     }
        2393                 :          0 :     return 0;
        2394                 :            : }
        2395                 :            :
        2396                 :            : int
        2397                 :          0 : PyObject_GC_IsFinalized(PyObject *obj)
        2398                 :            : {
        2399   [ #  #  #  # ]:          0 :     if (_PyObject_IS_GC(obj) && _PyGCHead_FINALIZED(AS_GC(obj))) {
        2400                 :          0 :          return 1;
        2401                 :            :     }
        2402                 :          0 :     return 0;
        2403                 :            : }
        2404                 :            :
        2405                 :            : void
        2406                 :          0 : PyUnstable_GC_VisitObjects(gcvisitobjects_t callback, void *arg)
        2407                 :            : {
        2408                 :            :     size_t i;
        2409                 :          0 :     GCState *gcstate = get_gc_state();
        2410                 :          0 :     int origenstate = gcstate->enabled;
        2411                 :          0 :     gcstate->enabled = 0;
        2412         [ #  # ]:          0 :     for (i = 0; i < NUM_GENERATIONS; i++) {
        2413                 :            :         PyGC_Head *gc_list, *gc;
        2414                 :          0 :         gc_list = GEN_HEAD(gcstate, i);
        2415         [ #  # ]:          0 :         for (gc = GC_NEXT(gc_list); gc != gc_list; gc = GC_NEXT(gc)) {
        2416                 :          0 :             PyObject *op = FROM_GC(gc);
        2417                 :          0 :             Py_INCREF(op);
        2418                 :          0 :             int res = callback(op, arg);
        2419                 :          0 :             Py_DECREF(op);
        2420         [ #  # ]:          0 :             if (!res) {
        2421                 :          0 :                 goto done;
        2422                 :            :             }
        2423                 :            :         }
        2424                 :            :     }
        2425                 :          0 : done:
        2426                 :          0 :     gcstate->enabled = origenstate;
        2427                 :          0 : }

Generated by: LCOV version 1.14