Python-2.7.3/Modules/gcmodule.c

No issues found

   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   http://www.python.org/pipermail/python-dev/2000-March/003869.html
  13   http://www.python.org/pipermail/python-dev/2000-March/004010.html
  14   http://www.python.org/pipermail/python-dev/2000-March/004022.html
  15 
  16   For a highlevel view of the collection process, read the collect
  17   function.
  18 
  19 */
  20 
  21 #include "Python.h"
  22 #include "frameobject.h"        /* for PyFrame_ClearFreeList */
  23 
  24 /* Get an object's GC head */
  25 #define AS_GC(o) ((PyGC_Head *)(o)-1)
  26 
  27 /* Get the object given the GC head */
  28 #define FROM_GC(g) ((PyObject *)(((PyGC_Head *)g)+1))
  29 
  30 /*** Global GC state ***/
  31 
  32 struct gc_generation {
  33     PyGC_Head head;
  34     int threshold; /* collection threshold */
  35     int count; /* count of allocations or collections of younger
  36                   generations */
  37 };
  38 
  39 #define NUM_GENERATIONS 3
  40 #define GEN_HEAD(n) (&generations[n].head)
  41 
  42 /* linked lists of container objects */
  43 static struct gc_generation generations[NUM_GENERATIONS] = {
  44     /* PyGC_Head,                               threshold,      count */
  45     {{{GEN_HEAD(0), GEN_HEAD(0), 0}},           700,            0},
  46     {{{GEN_HEAD(1), GEN_HEAD(1), 0}},           10,             0},
  47     {{{GEN_HEAD(2), GEN_HEAD(2), 0}},           10,             0},
  48 };
  49 
  50 PyGC_Head *_PyGC_generation0 = GEN_HEAD(0);
  51 
  52 static int enabled = 1; /* automatic collection enabled? */
  53 
  54 /* true if we are currently running the collector */
  55 static int collecting = 0;
  56 
  57 /* list of uncollectable objects */
  58 static PyObject *garbage = NULL;
  59 
  60 /* Python string to use if unhandled exception occurs */
  61 static PyObject *gc_str = NULL;
  62 
  63 /* Python string used to look for __del__ attribute. */
  64 static PyObject *delstr = NULL;
  65 
  66 /* This is the number of objects who survived the last full collection. It
  67    approximates the number of long lived objects tracked by the GC.
  68 
  69    (by "full collection", we mean a collection of the oldest generation).
  70 */
  71 static Py_ssize_t long_lived_total = 0;
  72 
  73 /* This is the number of objects who survived all "non-full" collections,
  74    and are awaiting to undergo a full collection for the first time.
  75 
  76 */
  77 static Py_ssize_t long_lived_pending = 0;
  78 
  79 /*
  80    NOTE: about the counting of long-lived objects.
  81 
  82    To limit the cost of garbage collection, there are two strategies;
  83      - make each collection faster, e.g. by scanning fewer objects
  84      - do less collections
  85    This heuristic is about the latter strategy.
  86 
  87    In addition to the various configurable thresholds, we only trigger a
  88    full collection if the ratio
  89     long_lived_pending / long_lived_total
  90    is above a given value (hardwired to 25%).
  91 
  92    The reason is that, while "non-full" collections (i.e., collections of
  93    the young and middle generations) will always examine roughly the same
  94    number of objects -- determined by the aforementioned thresholds --,
  95    the cost of a full collection is proportional to the total number of
  96    long-lived objects, which is virtually unbounded.
  97 
  98    Indeed, it has been remarked that doing a full collection every
  99    <constant number> of object creations entails a dramatic performance
 100    degradation in workloads which consist in creating and storing lots of
 101    long-lived objects (e.g. building a large list of GC-tracked objects would
 102    show quadratic performance, instead of linear as expected: see issue #4074).
 103 
 104    Using the above ratio, instead, yields amortized linear performance in
 105    the total number of objects (the effect of which can be summarized
 106    thusly: "each full garbage collection is more and more costly as the
 107    number of objects grows, but we do fewer and fewer of them").
 108 
 109    This heuristic was suggested by Martin von Lรถwis on python-dev in
 110    June 2008. His original analysis and proposal can be found at:
 111     http://mail.python.org/pipermail/python-dev/2008-June/080579.html
 112 */
 113 
 114 
 115 /* set for debugging information */
 116 #define DEBUG_STATS             (1<<0) /* print collection statistics */
 117 #define DEBUG_COLLECTABLE       (1<<1) /* print collectable objects */
 118 #define DEBUG_UNCOLLECTABLE     (1<<2) /* print uncollectable objects */
 119 #define DEBUG_INSTANCES         (1<<3) /* print instances */
 120 #define DEBUG_OBJECTS           (1<<4) /* print other objects */
 121 #define DEBUG_SAVEALL           (1<<5) /* save all garbage in gc.garbage */
 122 #define DEBUG_LEAK              DEBUG_COLLECTABLE | \
 123                 DEBUG_UNCOLLECTABLE | \
 124                 DEBUG_INSTANCES | \
 125                 DEBUG_OBJECTS | \
 126                 DEBUG_SAVEALL
 127 static int debug;
 128 static PyObject *tmod = NULL;
 129 
 130 /*--------------------------------------------------------------------------
 131 gc_refs values.
 132 
 133 Between collections, every gc'ed object has one of two gc_refs values:
 134 
 135 GC_UNTRACKED
 136     The initial state; objects returned by PyObject_GC_Malloc are in this
 137     state.  The object doesn't live in any generation list, and its
 138     tp_traverse slot must not be called.
 139 
 140 GC_REACHABLE
 141     The object lives in some generation list, and its tp_traverse is safe to
 142     call.  An object transitions to GC_REACHABLE when PyObject_GC_Track
 143     is called.
 144 
 145 During a collection, gc_refs can temporarily take on other states:
 146 
 147 >= 0
 148     At the start of a collection, update_refs() copies the true refcount
 149     to gc_refs, for each object in the generation being collected.
 150     subtract_refs() then adjusts gc_refs so that it equals the number of
 151     times an object is referenced directly from outside the generation
 152     being collected.
 153     gc_refs remains >= 0 throughout these steps.
 154 
 155 GC_TENTATIVELY_UNREACHABLE
 156     move_unreachable() then moves objects not reachable (whether directly or
 157     indirectly) from outside the generation into an "unreachable" set.
 158     Objects that are found to be reachable have gc_refs set to GC_REACHABLE
 159     again.  Objects that are found to be unreachable have gc_refs set to
 160     GC_TENTATIVELY_UNREACHABLE.  It's "tentatively" because the pass doing
 161     this can't be sure until it ends, and GC_TENTATIVELY_UNREACHABLE may
 162     transition back to GC_REACHABLE.
 163 
 164     Only objects with GC_TENTATIVELY_UNREACHABLE still set are candidates
 165     for collection.  If it's decided not to collect such an object (e.g.,
 166     it has a __del__ method), its gc_refs is restored to GC_REACHABLE again.
 167 ----------------------------------------------------------------------------
 168 */
 169 #define GC_UNTRACKED                    _PyGC_REFS_UNTRACKED
 170 #define GC_REACHABLE                    _PyGC_REFS_REACHABLE
 171 #define GC_TENTATIVELY_UNREACHABLE      _PyGC_REFS_TENTATIVELY_UNREACHABLE
 172 
 173 #define IS_TRACKED(o) ((AS_GC(o))->gc.gc_refs != GC_UNTRACKED)
 174 #define IS_REACHABLE(o) ((AS_GC(o))->gc.gc_refs == GC_REACHABLE)
 175 #define IS_TENTATIVELY_UNREACHABLE(o) ( \
 176     (AS_GC(o))->gc.gc_refs == GC_TENTATIVELY_UNREACHABLE)
 177 
 178 /*** list functions ***/
 179 
 180 static void
 181 gc_list_init(PyGC_Head *list)
 182 {
 183     list->gc.gc_prev = list;
 184     list->gc.gc_next = list;
 185 }
 186 
 187 static int
 188 gc_list_is_empty(PyGC_Head *list)
 189 {
 190     return (list->gc.gc_next == list);
 191 }
 192 
 193 #if 0
 194 /* This became unused after gc_list_move() was introduced. */
 195 /* Append `node` to `list`. */
 196 static void
 197 gc_list_append(PyGC_Head *node, PyGC_Head *list)
 198 {
 199     node->gc.gc_next = list;
 200     node->gc.gc_prev = list->gc.gc_prev;
 201     node->gc.gc_prev->gc.gc_next = node;
 202     list->gc.gc_prev = node;
 203 }
 204 #endif
 205 
 206 /* Remove `node` from the gc list it's currently in. */
 207 static void
 208 gc_list_remove(PyGC_Head *node)
 209 {
 210     node->gc.gc_prev->gc.gc_next = node->gc.gc_next;
 211     node->gc.gc_next->gc.gc_prev = node->gc.gc_prev;
 212     node->gc.gc_next = NULL; /* object is not currently tracked */
 213 }
 214 
 215 /* Move `node` from the gc list it's currently in (which is not explicitly
 216  * named here) to the end of `list`.  This is semantically the same as
 217  * gc_list_remove(node) followed by gc_list_append(node, list).
 218  */
 219 static void
 220 gc_list_move(PyGC_Head *node, PyGC_Head *list)
 221 {
 222     PyGC_Head *new_prev;
 223     PyGC_Head *current_prev = node->gc.gc_prev;
 224     PyGC_Head *current_next = node->gc.gc_next;
 225     /* Unlink from current list. */
 226     current_prev->gc.gc_next = current_next;
 227     current_next->gc.gc_prev = current_prev;
 228     /* Relink at end of new list. */
 229     new_prev = node->gc.gc_prev = list->gc.gc_prev;
 230     new_prev->gc.gc_next = list->gc.gc_prev = node;
 231     node->gc.gc_next = list;
 232 }
 233 
 234 /* append list `from` onto list `to`; `from` becomes an empty list */
 235 static void
 236 gc_list_merge(PyGC_Head *from, PyGC_Head *to)
 237 {
 238     PyGC_Head *tail;
 239     assert(from != to);
 240     if (!gc_list_is_empty(from)) {
 241         tail = to->gc.gc_prev;
 242         tail->gc.gc_next = from->gc.gc_next;
 243         tail->gc.gc_next->gc.gc_prev = tail;
 244         to->gc.gc_prev = from->gc.gc_prev;
 245         to->gc.gc_prev->gc.gc_next = to;
 246     }
 247     gc_list_init(from);
 248 }
 249 
 250 static Py_ssize_t
 251 gc_list_size(PyGC_Head *list)
 252 {
 253     PyGC_Head *gc;
 254     Py_ssize_t n = 0;
 255     for (gc = list->gc.gc_next; gc != list; gc = gc->gc.gc_next) {
 256         n++;
 257     }
 258     return n;
 259 }
 260 
 261 /* Append objects in a GC list to a Python list.
 262  * Return 0 if all OK, < 0 if error (out of memory for list).
 263  */
 264 static int
 265 append_objects(PyObject *py_list, PyGC_Head *gc_list)
 266 {
 267     PyGC_Head *gc;
 268     for (gc = gc_list->gc.gc_next; gc != gc_list; gc = gc->gc.gc_next) {
 269         PyObject *op = FROM_GC(gc);
 270         if (op != py_list) {
 271             if (PyList_Append(py_list, op)) {
 272                 return -1; /* exception */
 273             }
 274         }
 275     }
 276     return 0;
 277 }
 278 
 279 /*** end of list stuff ***/
 280 
 281 
 282 /* Set all gc_refs = ob_refcnt.  After this, gc_refs is > 0 for all objects
 283  * in containers, and is GC_REACHABLE for all tracked gc objects not in
 284  * containers.
 285  */
 286 static void
 287 update_refs(PyGC_Head *containers)
 288 {
 289     PyGC_Head *gc = containers->gc.gc_next;
 290     for (; gc != containers; gc = gc->gc.gc_next) {
 291         assert(gc->gc.gc_refs == GC_REACHABLE);
 292         gc->gc.gc_refs = Py_REFCNT(FROM_GC(gc));
 293         /* Python's cyclic gc should never see an incoming refcount
 294          * of 0:  if something decref'ed to 0, it should have been
 295          * deallocated immediately at that time.
 296          * Possible cause (if the assert triggers):  a tp_dealloc
 297          * routine left a gc-aware object tracked during its teardown
 298          * phase, and did something-- or allowed something to happen --
 299          * that called back into Python.  gc can trigger then, and may
 300          * see the still-tracked dying object.  Before this assert
 301          * was added, such mistakes went on to allow gc to try to
 302          * delete the object again.  In a debug build, that caused
 303          * a mysterious segfault, when _Py_ForgetReference tried
 304          * to remove the object from the doubly-linked list of all
 305          * objects a second time.  In a release build, an actual
 306          * double deallocation occurred, which leads to corruption
 307          * of the allocator's internal bookkeeping pointers.  That's
 308          * so serious that maybe this should be a release-build
 309          * check instead of an assert?
 310          */
 311         assert(gc->gc.gc_refs != 0);
 312     }
 313 }
 314 
 315 /* A traversal callback for subtract_refs. */
 316 static int
 317 visit_decref(PyObject *op, void *data)
 318 {
 319     assert(op != NULL);
 320     if (PyObject_IS_GC(op)) {
 321         PyGC_Head *gc = AS_GC(op);
 322         /* We're only interested in gc_refs for objects in the
 323          * generation being collected, which can be recognized
 324          * because only they have positive gc_refs.
 325          */
 326         assert(gc->gc.gc_refs != 0); /* else refcount was too small */
 327         if (gc->gc.gc_refs > 0)
 328             gc->gc.gc_refs--;
 329     }
 330     return 0;
 331 }
 332 
 333 /* Subtract internal references from gc_refs.  After this, gc_refs is >= 0
 334  * for all objects in containers, and is GC_REACHABLE for all tracked gc
 335  * objects not in containers.  The ones with gc_refs > 0 are directly
 336  * reachable from outside containers, and so can't be collected.
 337  */
 338 static void
 339 subtract_refs(PyGC_Head *containers)
 340 {
 341     traverseproc traverse;
 342     PyGC_Head *gc = containers->gc.gc_next;
 343     for (; gc != containers; gc=gc->gc.gc_next) {
 344         traverse = Py_TYPE(FROM_GC(gc))->tp_traverse;
 345         (void) traverse(FROM_GC(gc),
 346                        (visitproc)visit_decref,
 347                        NULL);
 348     }
 349 }
 350 
 351 /* A traversal callback for move_unreachable. */
 352 static int
 353 visit_reachable(PyObject *op, PyGC_Head *reachable)
 354 {
 355     if (PyObject_IS_GC(op)) {
 356         PyGC_Head *gc = AS_GC(op);
 357         const Py_ssize_t gc_refs = gc->gc.gc_refs;
 358 
 359         if (gc_refs == 0) {
 360             /* This is in move_unreachable's 'young' list, but
 361              * the traversal hasn't yet gotten to it.  All
 362              * we need to do is tell move_unreachable that it's
 363              * reachable.
 364              */
 365             gc->gc.gc_refs = 1;
 366         }
 367         else if (gc_refs == GC_TENTATIVELY_UNREACHABLE) {
 368             /* This had gc_refs = 0 when move_unreachable got
 369              * to it, but turns out it's reachable after all.
 370              * Move it back to move_unreachable's 'young' list,
 371              * and move_unreachable will eventually get to it
 372              * again.
 373              */
 374             gc_list_move(gc, reachable);
 375             gc->gc.gc_refs = 1;
 376         }
 377         /* Else there's nothing to do.
 378          * If gc_refs > 0, it must be in move_unreachable's 'young'
 379          * list, and move_unreachable will eventually get to it.
 380          * If gc_refs == GC_REACHABLE, it's either in some other
 381          * generation so we don't care about it, or move_unreachable
 382          * already dealt with it.
 383          * If gc_refs == GC_UNTRACKED, it must be ignored.
 384          */
 385          else {
 386             assert(gc_refs > 0
 387                    || gc_refs == GC_REACHABLE
 388                    || gc_refs == GC_UNTRACKED);
 389          }
 390     }
 391     return 0;
 392 }
 393 
 394 /* Move the unreachable objects from young to unreachable.  After this,
 395  * all objects in young have gc_refs = GC_REACHABLE, and all objects in
 396  * unreachable have gc_refs = GC_TENTATIVELY_UNREACHABLE.  All tracked
 397  * gc objects not in young or unreachable still have gc_refs = GC_REACHABLE.
 398  * All objects in young after this are directly or indirectly reachable
 399  * from outside the original young; and all objects in unreachable are
 400  * not.
 401  */
 402 static void
 403 move_unreachable(PyGC_Head *young, PyGC_Head *unreachable)
 404 {
 405     PyGC_Head *gc = young->gc.gc_next;
 406 
 407     /* Invariants:  all objects "to the left" of us in young have gc_refs
 408      * = GC_REACHABLE, and are indeed reachable (directly or indirectly)
 409      * from outside the young list as it was at entry.  All other objects
 410      * from the original young "to the left" of us are in unreachable now,
 411      * and have gc_refs = GC_TENTATIVELY_UNREACHABLE.  All objects to the
 412      * left of us in 'young' now have been scanned, and no objects here
 413      * or to the right have been scanned yet.
 414      */
 415 
 416     while (gc != young) {
 417         PyGC_Head *next;
 418 
 419         if (gc->gc.gc_refs) {
 420             /* gc is definitely reachable from outside the
 421              * original 'young'.  Mark it as such, and traverse
 422              * its pointers to find any other objects that may
 423              * be directly reachable from it.  Note that the
 424              * call to tp_traverse may append objects to young,
 425              * so we have to wait until it returns to determine
 426              * the next object to visit.
 427              */
 428             PyObject *op = FROM_GC(gc);
 429             traverseproc traverse = Py_TYPE(op)->tp_traverse;
 430             assert(gc->gc.gc_refs > 0);
 431             gc->gc.gc_refs = GC_REACHABLE;
 432             (void) traverse(op,
 433                             (visitproc)visit_reachable,
 434                             (void *)young);
 435             next = gc->gc.gc_next;
 436             if (PyTuple_CheckExact(op)) {
 437                 _PyTuple_MaybeUntrack(op);
 438             }
 439             else if (PyDict_CheckExact(op)) {
 440                 _PyDict_MaybeUntrack(op);
 441             }
 442         }
 443         else {
 444             /* This *may* be unreachable.  To make progress,
 445              * assume it is.  gc isn't directly reachable from
 446              * any object we've already traversed, but may be
 447              * reachable from an object we haven't gotten to yet.
 448              * visit_reachable will eventually move gc back into
 449              * young if that's so, and we'll see it again.
 450              */
 451             next = gc->gc.gc_next;
 452             gc_list_move(gc, unreachable);
 453             gc->gc.gc_refs = GC_TENTATIVELY_UNREACHABLE;
 454         }
 455         gc = next;
 456     }
 457 }
 458 
 459 /* Return true if object has a finalization method.
 460  * CAUTION:  An instance of an old-style class has to be checked for a
 461  *__del__ method, and earlier versions of this used to call PyObject_HasAttr,
 462  * which in turn could call the class's __getattr__ hook (if any).  That
 463  * could invoke arbitrary Python code, mutating the object graph in arbitrary
 464  * ways, and that was the source of some excruciatingly subtle bugs.
 465  */
 466 static int
 467 has_finalizer(PyObject *op)
 468 {
 469     if (PyInstance_Check(op)) {
 470         assert(delstr != NULL);
 471         return _PyInstance_Lookup(op, delstr) != NULL;
 472     }
 473     else if (PyType_HasFeature(op->ob_type, Py_TPFLAGS_HEAPTYPE))
 474         return op->ob_type->tp_del != NULL;
 475     else if (PyGen_CheckExact(op))
 476         return PyGen_NeedsFinalizing((PyGenObject *)op);
 477     else
 478         return 0;
 479 }
 480 
 481 /* Move the objects in unreachable with __del__ methods into `finalizers`.
 482  * Objects moved into `finalizers` have gc_refs set to GC_REACHABLE; the
 483  * objects remaining in unreachable are left at GC_TENTATIVELY_UNREACHABLE.
 484  */
 485 static void
 486 move_finalizers(PyGC_Head *unreachable, PyGC_Head *finalizers)
 487 {
 488     PyGC_Head *gc;
 489     PyGC_Head *next;
 490 
 491     /* March over unreachable.  Move objects with finalizers into
 492      * `finalizers`.
 493      */
 494     for (gc = unreachable->gc.gc_next; gc != unreachable; gc = next) {
 495         PyObject *op = FROM_GC(gc);
 496 
 497         assert(IS_TENTATIVELY_UNREACHABLE(op));
 498         next = gc->gc.gc_next;
 499 
 500         if (has_finalizer(op)) {
 501             gc_list_move(gc, finalizers);
 502             gc->gc.gc_refs = GC_REACHABLE;
 503         }
 504     }
 505 }
 506 
 507 /* A traversal callback for move_finalizer_reachable. */
 508 static int
 509 visit_move(PyObject *op, PyGC_Head *tolist)
 510 {
 511     if (PyObject_IS_GC(op)) {
 512         if (IS_TENTATIVELY_UNREACHABLE(op)) {
 513             PyGC_Head *gc = AS_GC(op);
 514             gc_list_move(gc, tolist);
 515             gc->gc.gc_refs = GC_REACHABLE;
 516         }
 517     }
 518     return 0;
 519 }
 520 
 521 /* Move objects that are reachable from finalizers, from the unreachable set
 522  * into finalizers set.
 523  */
 524 static void
 525 move_finalizer_reachable(PyGC_Head *finalizers)
 526 {
 527     traverseproc traverse;
 528     PyGC_Head *gc = finalizers->gc.gc_next;
 529     for (; gc != finalizers; gc = gc->gc.gc_next) {
 530         /* Note that the finalizers list may grow during this. */
 531         traverse = Py_TYPE(FROM_GC(gc))->tp_traverse;
 532         (void) traverse(FROM_GC(gc),
 533                         (visitproc)visit_move,
 534                         (void *)finalizers);
 535     }
 536 }
 537 
 538 /* Clear all weakrefs to unreachable objects, and if such a weakref has a
 539  * callback, invoke it if necessary.  Note that it's possible for such
 540  * weakrefs to be outside the unreachable set -- indeed, those are precisely
 541  * the weakrefs whose callbacks must be invoked.  See gc_weakref.txt for
 542  * overview & some details.  Some weakrefs with callbacks may be reclaimed
 543  * directly by this routine; the number reclaimed is the return value.  Other
 544  * weakrefs with callbacks may be moved into the `old` generation.  Objects
 545  * moved into `old` have gc_refs set to GC_REACHABLE; the objects remaining in
 546  * unreachable are left at GC_TENTATIVELY_UNREACHABLE.  When this returns,
 547  * no object in `unreachable` is weakly referenced anymore.
 548  */
 549 static int
 550 handle_weakrefs(PyGC_Head *unreachable, PyGC_Head *old)
 551 {
 552     PyGC_Head *gc;
 553     PyObject *op;               /* generally FROM_GC(gc) */
 554     PyWeakReference *wr;        /* generally a cast of op */
 555     PyGC_Head wrcb_to_call;     /* weakrefs with callbacks to call */
 556     PyGC_Head *next;
 557     int num_freed = 0;
 558 
 559     gc_list_init(&wrcb_to_call);
 560 
 561     /* Clear all weakrefs to the objects in unreachable.  If such a weakref
 562      * also has a callback, move it into `wrcb_to_call` if the callback
 563      * needs to be invoked.  Note that we cannot invoke any callbacks until
 564      * all weakrefs to unreachable objects are cleared, lest the callback
 565      * resurrect an unreachable object via a still-active weakref.  We
 566      * make another pass over wrcb_to_call, invoking callbacks, after this
 567      * pass completes.
 568      */
 569     for (gc = unreachable->gc.gc_next; gc != unreachable; gc = next) {
 570         PyWeakReference **wrlist;
 571 
 572         op = FROM_GC(gc);
 573         assert(IS_TENTATIVELY_UNREACHABLE(op));
 574         next = gc->gc.gc_next;
 575 
 576         if (! PyType_SUPPORTS_WEAKREFS(Py_TYPE(op)))
 577             continue;
 578 
 579         /* It supports weakrefs.  Does it have any? */
 580         wrlist = (PyWeakReference **)
 581                                 PyObject_GET_WEAKREFS_LISTPTR(op);
 582 
 583         /* `op` may have some weakrefs.  March over the list, clear
 584          * all the weakrefs, and move the weakrefs with callbacks
 585          * that must be called into wrcb_to_call.
 586          */
 587         for (wr = *wrlist; wr != NULL; wr = *wrlist) {
 588             PyGC_Head *wrasgc;                  /* AS_GC(wr) */
 589 
 590             /* _PyWeakref_ClearRef clears the weakref but leaves
 591              * the callback pointer intact.  Obscure:  it also
 592              * changes *wrlist.
 593              */
 594             assert(wr->wr_object == op);
 595             _PyWeakref_ClearRef(wr);
 596             assert(wr->wr_object == Py_None);
 597             if (wr->wr_callback == NULL)
 598                 continue;                       /* no callback */
 599 
 600     /* Headache time.  `op` is going away, and is weakly referenced by
 601      * `wr`, which has a callback.  Should the callback be invoked?  If wr
 602      * is also trash, no:
 603      *
 604      * 1. There's no need to call it.  The object and the weakref are
 605      *    both going away, so it's legitimate to pretend the weakref is
 606      *    going away first.  The user has to ensure a weakref outlives its
 607      *    referent if they want a guarantee that the wr callback will get
 608      *    invoked.
 609      *
 610      * 2. It may be catastrophic to call it.  If the callback is also in
 611      *    cyclic trash (CT), then although the CT is unreachable from
 612      *    outside the current generation, CT may be reachable from the
 613      *    callback.  Then the callback could resurrect insane objects.
 614      *
 615      * Since the callback is never needed and may be unsafe in this case,
 616      * wr is simply left in the unreachable set.  Note that because we
 617      * already called _PyWeakref_ClearRef(wr), its callback will never
 618      * trigger.
 619      *
 620      * OTOH, if wr isn't part of CT, we should invoke the callback:  the
 621      * weakref outlived the trash.  Note that since wr isn't CT in this
 622      * case, its callback can't be CT either -- wr acted as an external
 623      * root to this generation, and therefore its callback did too.  So
 624      * nothing in CT is reachable from the callback either, so it's hard
 625      * to imagine how calling it later could create a problem for us.  wr
 626      * is moved to wrcb_to_call in this case.
 627      */
 628             if (IS_TENTATIVELY_UNREACHABLE(wr))
 629                 continue;
 630             assert(IS_REACHABLE(wr));
 631 
 632             /* Create a new reference so that wr can't go away
 633              * before we can process it again.
 634              */
 635             Py_INCREF(wr);
 636 
 637             /* Move wr to wrcb_to_call, for the next pass. */
 638             wrasgc = AS_GC(wr);
 639             assert(wrasgc != next); /* wrasgc is reachable, but
 640                                        next isn't, so they can't
 641                                        be the same */
 642             gc_list_move(wrasgc, &wrcb_to_call);
 643         }
 644     }
 645 
 646     /* Invoke the callbacks we decided to honor.  It's safe to invoke them
 647      * because they can't reference unreachable objects.
 648      */
 649     while (! gc_list_is_empty(&wrcb_to_call)) {
 650         PyObject *temp;
 651         PyObject *callback;
 652 
 653         gc = wrcb_to_call.gc.gc_next;
 654         op = FROM_GC(gc);
 655         assert(IS_REACHABLE(op));
 656         assert(PyWeakref_Check(op));
 657         wr = (PyWeakReference *)op;
 658         callback = wr->wr_callback;
 659         assert(callback != NULL);
 660 
 661         /* copy-paste of weakrefobject.c's handle_callback() */
 662         temp = PyObject_CallFunctionObjArgs(callback, wr, NULL);
 663         if (temp == NULL)
 664             PyErr_WriteUnraisable(callback);
 665         else
 666             Py_DECREF(temp);
 667 
 668         /* Give up the reference we created in the first pass.  When
 669          * op's refcount hits 0 (which it may or may not do right now),
 670          * op's tp_dealloc will decref op->wr_callback too.  Note
 671          * that the refcount probably will hit 0 now, and because this
 672          * weakref was reachable to begin with, gc didn't already
 673          * add it to its count of freed objects.  Example:  a reachable
 674          * weak value dict maps some key to this reachable weakref.
 675          * The callback removes this key->weakref mapping from the
 676          * dict, leaving no other references to the weakref (excepting
 677          * ours).
 678          */
 679         Py_DECREF(op);
 680         if (wrcb_to_call.gc.gc_next == gc) {
 681             /* object is still alive -- move it */
 682             gc_list_move(gc, old);
 683         }
 684         else
 685             ++num_freed;
 686     }
 687 
 688     return num_freed;
 689 }
 690 
 691 static void
 692 debug_instance(char *msg, PyInstanceObject *inst)
 693 {
 694     char *cname;
 695     /* simple version of instance_repr */
 696     PyObject *classname = inst->in_class->cl_name;
 697     if (classname != NULL && PyString_Check(classname))
 698         cname = PyString_AsString(classname);
 699     else
 700         cname = "?";
 701     PySys_WriteStderr("gc: %.100s <%.100s instance at %p>\n",
 702                       msg, cname, inst);
 703 }
 704 
 705 static void
 706 debug_cycle(char *msg, PyObject *op)
 707 {
 708     if ((debug & DEBUG_INSTANCES) && PyInstance_Check(op)) {
 709         debug_instance(msg, (PyInstanceObject *)op);
 710     }
 711     else if (debug & DEBUG_OBJECTS) {
 712         PySys_WriteStderr("gc: %.100s <%.100s %p>\n",
 713                           msg, Py_TYPE(op)->tp_name, op);
 714     }
 715 }
 716 
 717 /* Handle uncollectable garbage (cycles with finalizers, and stuff reachable
 718  * only from such cycles).
 719  * If DEBUG_SAVEALL, all objects in finalizers are appended to the module
 720  * garbage list (a Python list), else only the objects in finalizers with
 721  * __del__ methods are appended to garbage.  All objects in finalizers are
 722  * merged into the old list regardless.
 723  * Returns 0 if all OK, <0 on error (out of memory to grow the garbage list).
 724  * The finalizers list is made empty on a successful return.
 725  */
 726 static int
 727 handle_finalizers(PyGC_Head *finalizers, PyGC_Head *old)
 728 {
 729     PyGC_Head *gc = finalizers->gc.gc_next;
 730 
 731     if (garbage == NULL) {
 732         garbage = PyList_New(0);
 733         if (garbage == NULL)
 734             Py_FatalError("gc couldn't create gc.garbage list");
 735     }
 736     for (; gc != finalizers; gc = gc->gc.gc_next) {
 737         PyObject *op = FROM_GC(gc);
 738 
 739         if ((debug & DEBUG_SAVEALL) || has_finalizer(op)) {
 740             if (PyList_Append(garbage, op) < 0)
 741                 return -1;
 742         }
 743     }
 744 
 745     gc_list_merge(finalizers, old);
 746     return 0;
 747 }
 748 
 749 /* Break reference cycles by clearing the containers involved.  This is
 750  * tricky business as the lists can be changing and we don't know which
 751  * objects may be freed.  It is possible I screwed something up here.
 752  */
 753 static void
 754 delete_garbage(PyGC_Head *collectable, PyGC_Head *old)
 755 {
 756     inquiry clear;
 757 
 758     while (!gc_list_is_empty(collectable)) {
 759         PyGC_Head *gc = collectable->gc.gc_next;
 760         PyObject *op = FROM_GC(gc);
 761 
 762         assert(IS_TENTATIVELY_UNREACHABLE(op));
 763         if (debug & DEBUG_SAVEALL) {
 764             PyList_Append(garbage, op);
 765         }
 766         else {
 767             if ((clear = Py_TYPE(op)->tp_clear) != NULL) {
 768                 Py_INCREF(op);
 769                 clear(op);
 770                 Py_DECREF(op);
 771             }
 772         }
 773         if (collectable->gc.gc_next == gc) {
 774             /* object is still alive, move it, it may die later */
 775             gc_list_move(gc, old);
 776             gc->gc.gc_refs = GC_REACHABLE;
 777         }
 778     }
 779 }
 780 
 781 /* Clear all free lists
 782  * All free lists are cleared during the collection of the highest generation.
 783  * Allocated items in the free list may keep a pymalloc arena occupied.
 784  * Clearing the free lists may give back memory to the OS earlier.
 785  */
 786 static void
 787 clear_freelists(void)
 788 {
 789     (void)PyMethod_ClearFreeList();
 790     (void)PyFrame_ClearFreeList();
 791     (void)PyCFunction_ClearFreeList();
 792     (void)PyTuple_ClearFreeList();
 793 #ifdef Py_USING_UNICODE
 794     (void)PyUnicode_ClearFreeList();
 795 #endif
 796     (void)PyInt_ClearFreeList();
 797     (void)PyFloat_ClearFreeList();
 798 }
 799 
 800 static double
 801 get_time(void)
 802 {
 803     double result = 0;
 804     if (tmod != NULL) {
 805         PyObject *f = PyObject_CallMethod(tmod, "time", NULL);
 806         if (f == NULL) {
 807             PyErr_Clear();
 808         }
 809         else {
 810             if (PyFloat_Check(f))
 811                 result = PyFloat_AsDouble(f);
 812             Py_DECREF(f);
 813         }
 814     }
 815     return result;
 816 }
 817 
 818 /* This is the main function.  Read this to understand how the
 819  * collection process works. */
 820 static Py_ssize_t
 821 collect(int generation)
 822 {
 823     int i;
 824     Py_ssize_t m = 0; /* # objects collected */
 825     Py_ssize_t n = 0; /* # unreachable objects that couldn't be collected */
 826     PyGC_Head *young; /* the generation we are examining */
 827     PyGC_Head *old; /* next older generation */
 828     PyGC_Head unreachable; /* non-problematic unreachable trash */
 829     PyGC_Head finalizers;  /* objects with, & reachable from, __del__ */
 830     PyGC_Head *gc;
 831     double t1 = 0.0;
 832 
 833     if (delstr == NULL) {
 834         delstr = PyString_InternFromString("__del__");
 835         if (delstr == NULL)
 836             Py_FatalError("gc couldn't allocate \"__del__\"");
 837     }
 838 
 839     if (debug & DEBUG_STATS) {
 840         PySys_WriteStderr("gc: collecting generation %d...\n",
 841                           generation);
 842         PySys_WriteStderr("gc: objects in each generation:");
 843         for (i = 0; i < NUM_GENERATIONS; i++)
 844             PySys_WriteStderr(" %" PY_FORMAT_SIZE_T "d",
 845                               gc_list_size(GEN_HEAD(i)));
 846         t1 = get_time();
 847         PySys_WriteStderr("\n");
 848     }
 849 
 850     /* update collection and allocation counters */
 851     if (generation+1 < NUM_GENERATIONS)
 852         generations[generation+1].count += 1;
 853     for (i = 0; i <= generation; i++)
 854         generations[i].count = 0;
 855 
 856     /* merge younger generations with one we are currently collecting */
 857     for (i = 0; i < generation; i++) {
 858         gc_list_merge(GEN_HEAD(i), GEN_HEAD(generation));
 859     }
 860 
 861     /* handy references */
 862     young = GEN_HEAD(generation);
 863     if (generation < NUM_GENERATIONS-1)
 864         old = GEN_HEAD(generation+1);
 865     else
 866         old = young;
 867 
 868     /* Using ob_refcnt and gc_refs, calculate which objects in the
 869      * container set are reachable from outside the set (i.e., have a
 870      * refcount greater than 0 when all the references within the
 871      * set are taken into account).
 872      */
 873     update_refs(young);
 874     subtract_refs(young);
 875 
 876     /* Leave everything reachable from outside young in young, and move
 877      * everything else (in young) to unreachable.
 878      * NOTE:  This used to move the reachable objects into a reachable
 879      * set instead.  But most things usually turn out to be reachable,
 880      * so it's more efficient to move the unreachable things.
 881      */
 882     gc_list_init(&unreachable);
 883     move_unreachable(young, &unreachable);
 884 
 885     /* Move reachable objects to next generation. */
 886     if (young != old) {
 887         if (generation == NUM_GENERATIONS - 2) {
 888             long_lived_pending += gc_list_size(young);
 889         }
 890         gc_list_merge(young, old);
 891     }
 892     else {
 893         long_lived_pending = 0;
 894         long_lived_total = gc_list_size(young);
 895     }
 896 
 897     /* All objects in unreachable are trash, but objects reachable from
 898      * finalizers can't safely be deleted.  Python programmers should take
 899      * care not to create such things.  For Python, finalizers means
 900      * instance objects with __del__ methods.  Weakrefs with callbacks
 901      * can also call arbitrary Python code but they will be dealt with by
 902      * handle_weakrefs().
 903      */
 904     gc_list_init(&finalizers);
 905     move_finalizers(&unreachable, &finalizers);
 906     /* finalizers contains the unreachable objects with a finalizer;
 907      * unreachable objects reachable *from* those are also uncollectable,
 908      * and we move those into the finalizers list too.
 909      */
 910     move_finalizer_reachable(&finalizers);
 911 
 912     /* Collect statistics on collectable objects found and print
 913      * debugging information.
 914      */
 915     for (gc = unreachable.gc.gc_next; gc != &unreachable;
 916                     gc = gc->gc.gc_next) {
 917         m++;
 918         if (debug & DEBUG_COLLECTABLE) {
 919             debug_cycle("collectable", FROM_GC(gc));
 920         }
 921     }
 922 
 923     /* Clear weakrefs and invoke callbacks as necessary. */
 924     m += handle_weakrefs(&unreachable, old);
 925 
 926     /* Call tp_clear on objects in the unreachable set.  This will cause
 927      * the reference cycles to be broken.  It may also cause some objects
 928      * in finalizers to be freed.
 929      */
 930     delete_garbage(&unreachable, old);
 931 
 932     /* Collect statistics on uncollectable objects found and print
 933      * debugging information. */
 934     for (gc = finalizers.gc.gc_next;
 935          gc != &finalizers;
 936          gc = gc->gc.gc_next) {
 937         n++;
 938         if (debug & DEBUG_UNCOLLECTABLE)
 939             debug_cycle("uncollectable", FROM_GC(gc));
 940     }
 941     if (debug & DEBUG_STATS) {
 942         double t2 = get_time();
 943         if (m == 0 && n == 0)
 944             PySys_WriteStderr("gc: done");
 945         else
 946             PySys_WriteStderr(
 947                 "gc: done, "
 948                 "%" PY_FORMAT_SIZE_T "d unreachable, "
 949                 "%" PY_FORMAT_SIZE_T "d uncollectable",
 950                 n+m, n);
 951         if (t1 && t2) {
 952             PySys_WriteStderr(", %.4fs elapsed", t2-t1);
 953         }
 954         PySys_WriteStderr(".\n");
 955     }
 956 
 957     /* Append instances in the uncollectable set to a Python
 958      * reachable list of garbage.  The programmer has to deal with
 959      * this if they insist on creating this type of structure.
 960      */
 961     (void)handle_finalizers(&finalizers, old);
 962 
 963     /* Clear free list only during the collection of the highest
 964      * generation */
 965     if (generation == NUM_GENERATIONS-1) {
 966         clear_freelists();
 967     }
 968 
 969     if (PyErr_Occurred()) {
 970         if (gc_str == NULL)
 971             gc_str = PyString_FromString("garbage collection");
 972         PyErr_WriteUnraisable(gc_str);
 973         Py_FatalError("unexpected exception during garbage collection");
 974     }
 975     return n+m;
 976 }
 977 
 978 static Py_ssize_t
 979 collect_generations(void)
 980 {
 981     int i;
 982     Py_ssize_t n = 0;
 983 
 984     /* Find the oldest generation (highest numbered) where the count
 985      * exceeds the threshold.  Objects in the that generation and
 986      * generations younger than it will be collected. */
 987     for (i = NUM_GENERATIONS-1; i >= 0; i--) {
 988         if (generations[i].count > generations[i].threshold) {
 989             /* Avoid quadratic performance degradation in number
 990                of tracked objects. See comments at the beginning
 991                of this file, and issue #4074.
 992             */
 993             if (i == NUM_GENERATIONS - 1
 994                 && long_lived_pending < long_lived_total / 4)
 995                 continue;
 996             n = collect(i);
 997             break;
 998         }
 999     }
1000     return n;
1001 }
1002 
1003 PyDoc_STRVAR(gc_enable__doc__,
1004 "enable() -> None\n"
1005 "\n"
1006 "Enable automatic garbage collection.\n");
1007 
1008 static PyObject *
1009 gc_enable(PyObject *self, PyObject *noargs)
1010 {
1011     enabled = 1;
1012     Py_INCREF(Py_None);
1013     return Py_None;
1014 }
1015 
1016 PyDoc_STRVAR(gc_disable__doc__,
1017 "disable() -> None\n"
1018 "\n"
1019 "Disable automatic garbage collection.\n");
1020 
1021 static PyObject *
1022 gc_disable(PyObject *self, PyObject *noargs)
1023 {
1024     enabled = 0;
1025     Py_INCREF(Py_None);
1026     return Py_None;
1027 }
1028 
1029 PyDoc_STRVAR(gc_isenabled__doc__,
1030 "isenabled() -> status\n"
1031 "\n"
1032 "Returns true if automatic garbage collection is enabled.\n");
1033 
1034 static PyObject *
1035 gc_isenabled(PyObject *self, PyObject *noargs)
1036 {
1037     return PyBool_FromLong((long)enabled);
1038 }
1039 
1040 PyDoc_STRVAR(gc_collect__doc__,
1041 "collect([generation]) -> n\n"
1042 "\n"
1043 "With no arguments, run a full collection.  The optional argument\n"
1044 "may be an integer specifying which generation to collect.  A ValueError\n"
1045 "is raised if the generation number is invalid.\n\n"
1046 "The number of unreachable objects is returned.\n");
1047 
1048 static PyObject *
1049 gc_collect(PyObject *self, PyObject *args, PyObject *kws)
1050 {
1051     static char *keywords[] = {"generation", NULL};
1052     int genarg = NUM_GENERATIONS - 1;
1053     Py_ssize_t n;
1054 
1055     if (!PyArg_ParseTupleAndKeywords(args, kws, "|i", keywords, &genarg))
1056         return NULL;
1057 
1058     else if (genarg < 0 || genarg >= NUM_GENERATIONS) {
1059         PyErr_SetString(PyExc_ValueError, "invalid generation");
1060         return NULL;
1061     }
1062 
1063     if (collecting)
1064         n = 0; /* already collecting, don't do anything */
1065     else {
1066         collecting = 1;
1067         n = collect(genarg);
1068         collecting = 0;
1069     }
1070 
1071     return PyInt_FromSsize_t(n);
1072 }
1073 
1074 PyDoc_STRVAR(gc_set_debug__doc__,
1075 "set_debug(flags) -> None\n"
1076 "\n"
1077 "Set the garbage collection debugging flags. Debugging information is\n"
1078 "written to sys.stderr.\n"
1079 "\n"
1080 "flags is an integer and can have the following bits turned on:\n"
1081 "\n"
1082 "  DEBUG_STATS - Print statistics during collection.\n"
1083 "  DEBUG_COLLECTABLE - Print collectable objects found.\n"
1084 "  DEBUG_UNCOLLECTABLE - Print unreachable but uncollectable objects found.\n"
1085 "  DEBUG_INSTANCES - Print instance objects.\n"
1086 "  DEBUG_OBJECTS - Print objects other than instances.\n"
1087 "  DEBUG_SAVEALL - Save objects to gc.garbage rather than freeing them.\n"
1088 "  DEBUG_LEAK - Debug leaking programs (everything but STATS).\n");
1089 
1090 static PyObject *
1091 gc_set_debug(PyObject *self, PyObject *args)
1092 {
1093     if (!PyArg_ParseTuple(args, "i:set_debug", &debug))
1094         return NULL;
1095 
1096     Py_INCREF(Py_None);
1097     return Py_None;
1098 }
1099 
1100 PyDoc_STRVAR(gc_get_debug__doc__,
1101 "get_debug() -> flags\n"
1102 "\n"
1103 "Get the garbage collection debugging flags.\n");
1104 
1105 static PyObject *
1106 gc_get_debug(PyObject *self, PyObject *noargs)
1107 {
1108     return Py_BuildValue("i", debug);
1109 }
1110 
1111 PyDoc_STRVAR(gc_set_thresh__doc__,
1112 "set_threshold(threshold0, [threshold1, threshold2]) -> None\n"
1113 "\n"
1114 "Sets the collection thresholds.  Setting threshold0 to zero disables\n"
1115 "collection.\n");
1116 
1117 static PyObject *
1118 gc_set_thresh(PyObject *self, PyObject *args)
1119 {
1120     int i;
1121     if (!PyArg_ParseTuple(args, "i|ii:set_threshold",
1122                           &generations[0].threshold,
1123                           &generations[1].threshold,
1124                           &generations[2].threshold))
1125         return NULL;
1126     for (i = 2; i < NUM_GENERATIONS; i++) {
1127         /* generations higher than 2 get the same threshold */
1128         generations[i].threshold = generations[2].threshold;
1129     }
1130 
1131     Py_INCREF(Py_None);
1132     return Py_None;
1133 }
1134 
1135 PyDoc_STRVAR(gc_get_thresh__doc__,
1136 "get_threshold() -> (threshold0, threshold1, threshold2)\n"
1137 "\n"
1138 "Return the current collection thresholds\n");
1139 
1140 static PyObject *
1141 gc_get_thresh(PyObject *self, PyObject *noargs)
1142 {
1143     return Py_BuildValue("(iii)",
1144                          generations[0].threshold,
1145                          generations[1].threshold,
1146                          generations[2].threshold);
1147 }
1148 
1149 PyDoc_STRVAR(gc_get_count__doc__,
1150 "get_count() -> (count0, count1, count2)\n"
1151 "\n"
1152 "Return the current collection counts\n");
1153 
1154 static PyObject *
1155 gc_get_count(PyObject *self, PyObject *noargs)
1156 {
1157     return Py_BuildValue("(iii)",
1158                          generations[0].count,
1159                          generations[1].count,
1160                          generations[2].count);
1161 }
1162 
1163 static int
1164 referrersvisit(PyObject* obj, PyObject *objs)
1165 {
1166     Py_ssize_t i;
1167     for (i = 0; i < PyTuple_GET_SIZE(objs); i++)
1168         if (PyTuple_GET_ITEM(objs, i) == obj)
1169             return 1;
1170     return 0;
1171 }
1172 
1173 static int
1174 gc_referrers_for(PyObject *objs, PyGC_Head *list, PyObject *resultlist)
1175 {
1176     PyGC_Head *gc;
1177     PyObject *obj;
1178     traverseproc traverse;
1179     for (gc = list->gc.gc_next; gc != list; gc = gc->gc.gc_next) {
1180         obj = FROM_GC(gc);
1181         traverse = Py_TYPE(obj)->tp_traverse;
1182         if (obj == objs || obj == resultlist)
1183             continue;
1184         if (traverse(obj, (visitproc)referrersvisit, objs)) {
1185             if (PyList_Append(resultlist, obj) < 0)
1186                 return 0; /* error */
1187         }
1188     }
1189     return 1; /* no error */
1190 }
1191 
1192 PyDoc_STRVAR(gc_get_referrers__doc__,
1193 "get_referrers(*objs) -> list\n\
1194 Return the list of objects that directly refer to any of objs.");
1195 
1196 static PyObject *
1197 gc_get_referrers(PyObject *self, PyObject *args)
1198 {
1199     int i;
1200     PyObject *result = PyList_New(0);
1201     if (!result) return NULL;
1202 
1203     for (i = 0; i < NUM_GENERATIONS; i++) {
1204         if (!(gc_referrers_for(args, GEN_HEAD(i), result))) {
1205             Py_DECREF(result);
1206             return NULL;
1207         }
1208     }
1209     return result;
1210 }
1211 
1212 /* Append obj to list; return true if error (out of memory), false if OK. */
1213 static int
1214 referentsvisit(PyObject *obj, PyObject *list)
1215 {
1216     return PyList_Append(list, obj) < 0;
1217 }
1218 
1219 PyDoc_STRVAR(gc_get_referents__doc__,
1220 "get_referents(*objs) -> list\n\
1221 Return the list of objects that are directly referred to by objs.");
1222 
1223 static PyObject *
1224 gc_get_referents(PyObject *self, PyObject *args)
1225 {
1226     Py_ssize_t i;
1227     PyObject *result = PyList_New(0);
1228 
1229     if (result == NULL)
1230         return NULL;
1231 
1232     for (i = 0; i < PyTuple_GET_SIZE(args); i++) {
1233         traverseproc traverse;
1234         PyObject *obj = PyTuple_GET_ITEM(args, i);
1235 
1236         if (! PyObject_IS_GC(obj))
1237             continue;
1238         traverse = Py_TYPE(obj)->tp_traverse;
1239         if (! traverse)
1240             continue;
1241         if (traverse(obj, (visitproc)referentsvisit, result)) {
1242             Py_DECREF(result);
1243             return NULL;
1244         }
1245     }
1246     return result;
1247 }
1248 
1249 PyDoc_STRVAR(gc_get_objects__doc__,
1250 "get_objects() -> [...]\n"
1251 "\n"
1252 "Return a list of objects tracked by the collector (excluding the list\n"
1253 "returned).\n");
1254 
1255 static PyObject *
1256 gc_get_objects(PyObject *self, PyObject *noargs)
1257 {
1258     int i;
1259     PyObject* result;
1260 
1261     result = PyList_New(0);
1262     if (result == NULL)
1263         return NULL;
1264     for (i = 0; i < NUM_GENERATIONS; i++) {
1265         if (append_objects(result, GEN_HEAD(i))) {
1266             Py_DECREF(result);
1267             return NULL;
1268         }
1269     }
1270     return result;
1271 }
1272 
1273 PyDoc_STRVAR(gc_is_tracked__doc__,
1274 "is_tracked(obj) -> bool\n"
1275 "\n"
1276 "Returns true if the object is tracked by the garbage collector.\n"
1277 "Simple atomic objects will return false.\n"
1278 );
1279 
1280 static PyObject *
1281 gc_is_tracked(PyObject *self, PyObject *obj)
1282 {
1283     PyObject *result;
1284 
1285     if (PyObject_IS_GC(obj) && IS_TRACKED(obj))
1286         result = Py_True;
1287     else
1288         result = Py_False;
1289     Py_INCREF(result);
1290     return result;
1291 }
1292 
1293 
1294 PyDoc_STRVAR(gc__doc__,
1295 "This module provides access to the garbage collector for reference cycles.\n"
1296 "\n"
1297 "enable() -- Enable automatic garbage collection.\n"
1298 "disable() -- Disable automatic garbage collection.\n"
1299 "isenabled() -- Returns true if automatic collection is enabled.\n"
1300 "collect() -- Do a full collection right now.\n"
1301 "get_count() -- Return the current collection counts.\n"
1302 "set_debug() -- Set debugging flags.\n"
1303 "get_debug() -- Get debugging flags.\n"
1304 "set_threshold() -- Set the collection thresholds.\n"
1305 "get_threshold() -- Return the current the collection thresholds.\n"
1306 "get_objects() -- Return a list of all objects tracked by the collector.\n"
1307 "is_tracked() -- Returns true if a given object is tracked.\n"
1308 "get_referrers() -- Return the list of objects that refer to an object.\n"
1309 "get_referents() -- Return the list of objects that an object refers to.\n");
1310 
1311 static PyMethodDef GcMethods[] = {
1312     {"enable",             gc_enable,     METH_NOARGS,  gc_enable__doc__},
1313     {"disable",            gc_disable,    METH_NOARGS,  gc_disable__doc__},
1314     {"isenabled",          gc_isenabled,  METH_NOARGS,  gc_isenabled__doc__},
1315     {"set_debug",          gc_set_debug,  METH_VARARGS, gc_set_debug__doc__},
1316     {"get_debug",          gc_get_debug,  METH_NOARGS,  gc_get_debug__doc__},
1317     {"get_count",          gc_get_count,  METH_NOARGS,  gc_get_count__doc__},
1318     {"set_threshold",  gc_set_thresh, METH_VARARGS, gc_set_thresh__doc__},
1319     {"get_threshold",  gc_get_thresh, METH_NOARGS,  gc_get_thresh__doc__},
1320     {"collect",            (PyCFunction)gc_collect,
1321         METH_VARARGS | METH_KEYWORDS,           gc_collect__doc__},
1322     {"get_objects",    gc_get_objects,METH_NOARGS,  gc_get_objects__doc__},
1323     {"is_tracked",     gc_is_tracked, METH_O,       gc_is_tracked__doc__},
1324     {"get_referrers",  gc_get_referrers, METH_VARARGS,
1325         gc_get_referrers__doc__},
1326     {"get_referents",  gc_get_referents, METH_VARARGS,
1327         gc_get_referents__doc__},
1328     {NULL,      NULL}           /* Sentinel */
1329 };
1330 
1331 PyMODINIT_FUNC
1332 initgc(void)
1333 {
1334     PyObject *m;
1335 
1336     m = Py_InitModule4("gc",
1337                           GcMethods,
1338                           gc__doc__,
1339                           NULL,
1340                           PYTHON_API_VERSION);
1341     if (m == NULL)
1342         return;
1343 
1344     if (garbage == NULL) {
1345         garbage = PyList_New(0);
1346         if (garbage == NULL)
1347             return;
1348     }
1349     Py_INCREF(garbage);
1350     if (PyModule_AddObject(m, "garbage", garbage) < 0)
1351         return;
1352 
1353     /* Importing can't be done in collect() because collect()
1354      * can be called via PyGC_Collect() in Py_Finalize().
1355      * This wouldn't be a problem, except that <initialized> is
1356      * reset to 0 before calling collect which trips up
1357      * the import and triggers an assertion.
1358      */
1359     if (tmod == NULL) {
1360         tmod = PyImport_ImportModuleNoBlock("time");
1361         if (tmod == NULL)
1362             PyErr_Clear();
1363     }
1364 
1365 #define ADD_INT(NAME) if (PyModule_AddIntConstant(m, #NAME, NAME) < 0) return
1366     ADD_INT(DEBUG_STATS);
1367     ADD_INT(DEBUG_COLLECTABLE);
1368     ADD_INT(DEBUG_UNCOLLECTABLE);
1369     ADD_INT(DEBUG_INSTANCES);
1370     ADD_INT(DEBUG_OBJECTS);
1371     ADD_INT(DEBUG_SAVEALL);
1372     ADD_INT(DEBUG_LEAK);
1373 #undef ADD_INT
1374 }
1375 
1376 /* API to invoke gc.collect() from C */
1377 Py_ssize_t
1378 PyGC_Collect(void)
1379 {
1380     Py_ssize_t n;
1381 
1382     if (collecting)
1383         n = 0; /* already collecting, don't do anything */
1384     else {
1385         collecting = 1;
1386         n = collect(NUM_GENERATIONS - 1);
1387         collecting = 0;
1388     }
1389 
1390     return n;
1391 }
1392 
1393 /* for debugging */
1394 void
1395 _PyGC_Dump(PyGC_Head *g)
1396 {
1397     _PyObject_Dump(FROM_GC(g));
1398 }
1399 
1400 /* extension modules might be compiled with GC support so these
1401    functions must always be available */
1402 
1403 #undef PyObject_GC_Track
1404 #undef PyObject_GC_UnTrack
1405 #undef PyObject_GC_Del
1406 #undef _PyObject_GC_Malloc
1407 
1408 void
1409 PyObject_GC_Track(void *op)
1410 {
1411     _PyObject_GC_TRACK(op);
1412 }
1413 
1414 /* for binary compatibility with 2.2 */
1415 void
1416 _PyObject_GC_Track(PyObject *op)
1417 {
1418     PyObject_GC_Track(op);
1419 }
1420 
1421 void
1422 PyObject_GC_UnTrack(void *op)
1423 {
1424     /* Obscure:  the Py_TRASHCAN mechanism requires that we be able to
1425      * call PyObject_GC_UnTrack twice on an object.
1426      */
1427     if (IS_TRACKED(op))
1428         _PyObject_GC_UNTRACK(op);
1429 }
1430 
1431 /* for binary compatibility with 2.2 */
1432 void
1433 _PyObject_GC_UnTrack(PyObject *op)
1434 {
1435     PyObject_GC_UnTrack(op);
1436 }
1437 
1438 PyObject *
1439 _PyObject_GC_Malloc(size_t basicsize)
1440 {
1441     PyObject *op;
1442     PyGC_Head *g;
1443     if (basicsize > PY_SSIZE_T_MAX - sizeof(PyGC_Head))
1444         return PyErr_NoMemory();
1445     g = (PyGC_Head *)PyObject_MALLOC(
1446         sizeof(PyGC_Head) + basicsize);
1447     if (g == NULL)
1448         return PyErr_NoMemory();
1449     g->gc.gc_refs = GC_UNTRACKED;
1450     generations[0].count++; /* number of allocated GC objects */
1451     if (generations[0].count > generations[0].threshold &&
1452         enabled &&
1453         generations[0].threshold &&
1454         !collecting &&
1455         !PyErr_Occurred()) {
1456         collecting = 1;
1457         collect_generations();
1458         collecting = 0;
1459     }
1460     op = FROM_GC(g);
1461     return op;
1462 }
1463 
1464 PyObject *
1465 _PyObject_GC_New(PyTypeObject *tp)
1466 {
1467     PyObject *op = _PyObject_GC_Malloc(_PyObject_SIZE(tp));
1468     if (op != NULL)
1469         op = PyObject_INIT(op, tp);
1470     return op;
1471 }
1472 
1473 PyVarObject *
1474 _PyObject_GC_NewVar(PyTypeObject *tp, Py_ssize_t nitems)
1475 {
1476     const size_t size = _PyObject_VAR_SIZE(tp, nitems);
1477     PyVarObject *op = (PyVarObject *) _PyObject_GC_Malloc(size);
1478     if (op != NULL)
1479         op = PyObject_INIT_VAR(op, tp, nitems);
1480     return op;
1481 }
1482 
1483 PyVarObject *
1484 _PyObject_GC_Resize(PyVarObject *op, Py_ssize_t nitems)
1485 {
1486     const size_t basicsize = _PyObject_VAR_SIZE(Py_TYPE(op), nitems);
1487     PyGC_Head *g = AS_GC(op);
1488     if (basicsize > PY_SSIZE_T_MAX - sizeof(PyGC_Head))
1489         return (PyVarObject *)PyErr_NoMemory();
1490     g = (PyGC_Head *)PyObject_REALLOC(g,  sizeof(PyGC_Head) + basicsize);
1491     if (g == NULL)
1492         return (PyVarObject *)PyErr_NoMemory();
1493     op = (PyVarObject *) FROM_GC(g);
1494     Py_SIZE(op) = nitems;
1495     return op;
1496 }
1497 
1498 void
1499 PyObject_GC_Del(void *op)
1500 {
1501     PyGC_Head *g = AS_GC(op);
1502     if (IS_TRACKED(op))
1503         gc_list_remove(g);
1504     if (generations[0].count > 0) {
1505         generations[0].count--;
1506     }
1507     PyObject_FREE(g);
1508 }
1509 
1510 /* for binary compatibility with 2.2 */
1511 #undef _PyObject_GC_Del
1512 void
1513 _PyObject_GC_Del(PyObject *op)
1514 {
1515     PyObject_GC_Del(op);
1516 }