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 32struct 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 */ 43static 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 50PyGC_Head *_PyGC_generation0 = GEN_HEAD(0); 51 52static int enabled = 1; /* automatic collection enabled? */ 53 54/* true if we are currently running the collector */ 55static int collecting = 0; 56 57/* list of uncollectable objects */ 58static PyObject *garbage = NULL; 59 60/* Python string to use if unhandled exception occurs */ 61static PyObject *gc_str = NULL; 62 63/* Python string used to look for __del__ attribute. */ 64static 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*/ 71static 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*/ 77static 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 127static int debug; 128static PyObject *tmod = NULL; 129 130/*-------------------------------------------------------------------------- 131gc_refs values. 132 133Between collections, every gc'ed object has one of two gc_refs values: 134 135GC_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 140GC_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 145During 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 155GC_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 180static void 181gc_list_init(PyGC_Head *list) 182{ 183 list->gc.gc_prev = list; 184 list->gc.gc_next = list; 185} 186 187static int 188gc_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`. */ 196static void 197gc_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. */ 207static void 208gc_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 */ 219static void 220gc_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 */ 235static void 236gc_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 250static Py_ssize_t 251gc_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 */ 264static int 265append_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 */ 286static void 287update_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. */ 316static int 317visit_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 */ 338static void 339subtract_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. */ 352static int 353visit_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 */ 402static void 403move_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 */ 466static int 467has_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 */ 485static void 486move_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. */ 508static int 509visit_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 */ 524static void 525move_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 */ 549static int 550handle_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 691static void 692debug_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 705static void 706debug_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 */ 726static int 727handle_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 */ 753static void 754delete_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 */ 786static void 787clear_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 800static double 801get_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. */ 820static Py_ssize_t 821collect(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 978static Py_ssize_t 979collect_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 1003PyDoc_STRVAR(gc_enable__doc__, 1004"enable() -> None\n" 1005"\n" 1006"Enable automatic garbage collection.\n"); 1007 1008static PyObject * 1009gc_enable(PyObject *self, PyObject *noargs) 1010{ 1011 enabled = 1; 1012 Py_INCREF(Py_None); 1013 return Py_None; 1014} 1015 1016PyDoc_STRVAR(gc_disable__doc__, 1017"disable() -> None\n" 1018"\n" 1019"Disable automatic garbage collection.\n"); 1020 1021static PyObject * 1022gc_disable(PyObject *self, PyObject *noargs) 1023{ 1024 enabled = 0; 1025 Py_INCREF(Py_None); 1026 return Py_None; 1027} 1028 1029PyDoc_STRVAR(gc_isenabled__doc__, 1030"isenabled() -> status\n" 1031"\n" 1032"Returns true if automatic garbage collection is enabled.\n"); 1033 1034static PyObject * 1035gc_isenabled(PyObject *self, PyObject *noargs) 1036{ 1037 return PyBool_FromLong((long)enabled); 1038} 1039 1040PyDoc_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 1048static PyObject * 1049gc_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 1074PyDoc_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 1090static PyObject * 1091gc_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 1100PyDoc_STRVAR(gc_get_debug__doc__, 1101"get_debug() -> flags\n" 1102"\n" 1103"Get the garbage collection debugging flags.\n"); 1104 1105static PyObject * 1106gc_get_debug(PyObject *self, PyObject *noargs) 1107{ 1108 return Py_BuildValue("i", debug); 1109} 1110 1111PyDoc_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 1117static PyObject * 1118gc_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 1135PyDoc_STRVAR(gc_get_thresh__doc__, 1136"get_threshold() -> (threshold0, threshold1, threshold2)\n" 1137"\n" 1138"Return the current collection thresholds\n"); 1139 1140static PyObject * 1141gc_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 1149PyDoc_STRVAR(gc_get_count__doc__, 1150"get_count() -> (count0, count1, count2)\n" 1151"\n" 1152"Return the current collection counts\n"); 1153 1154static PyObject * 1155gc_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 1163static int 1164referrersvisit(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 1173static int 1174gc_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 1192PyDoc_STRVAR(gc_get_referrers__doc__, 1193"get_referrers(*objs) -> list\n\ 1194Return the list of objects that directly refer to any of objs."); 1195 1196static PyObject * 1197gc_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. */ 1213static int 1214referentsvisit(PyObject *obj, PyObject *list) 1215{ 1216 return PyList_Append(list, obj) < 0; 1217} 1218 1219PyDoc_STRVAR(gc_get_referents__doc__, 1220"get_referents(*objs) -> list\n\ 1221Return the list of objects that are directly referred to by objs."); 1222 1223static PyObject * 1224gc_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 1249PyDoc_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 1255static PyObject * 1256gc_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 1273PyDoc_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 1280static PyObject * 1281gc_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 1294PyDoc_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 1311static 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 1331PyMODINIT_FUNC 1332initgc(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 */ 1377Py_ssize_t 1378PyGC_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 */ 1394void 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 1408void 1409PyObject_GC_Track(void *op) 1410{ 1411 _PyObject_GC_TRACK(op); 1412} 1413 1414/* for binary compatibility with 2.2 */ 1415void 1416_PyObject_GC_Track(PyObject *op) 1417{ 1418 PyObject_GC_Track(op); 1419} 1420 1421void 1422PyObject_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 */ 1432void 1433_PyObject_GC_UnTrack(PyObject *op) 1434{ 1435 PyObject_GC_UnTrack(op); 1436} 1437 1438PyObject * 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 1464PyObject * 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 1473PyVarObject * 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 1483PyVarObject * 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 1498void 1499PyObject_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 1512void 1513_PyObject_GC_Del(PyObject *op) 1514{ 1515 PyObject_GC_Del(op); 1516} 1517