288
288
update_refs(PyGC_Head *containers)
290
PyGC_Head *gc = containers->gc.gc_next;
291
for (; gc != containers; gc = gc->gc.gc_next) {
292
assert(gc->gc.gc_refs == GC_REACHABLE);
293
gc->gc.gc_refs = Py_REFCNT(FROM_GC(gc));
294
/* Python's cyclic gc should never see an incoming refcount
295
* of 0: if something decref'ed to 0, it should have been
296
* deallocated immediately at that time.
297
* Possible cause (if the assert triggers): a tp_dealloc
298
* routine left a gc-aware object tracked during its teardown
299
* phase, and did something-- or allowed something to happen --
300
* that called back into Python. gc can trigger then, and may
301
* see the still-tracked dying object. Before this assert
302
* was added, such mistakes went on to allow gc to try to
303
* delete the object again. In a debug build, that caused
304
* a mysterious segfault, when _Py_ForgetReference tried
305
* to remove the object from the doubly-linked list of all
306
* objects a second time. In a release build, an actual
307
* double deallocation occurred, which leads to corruption
308
* of the allocator's internal bookkeeping pointers. That's
309
* so serious that maybe this should be a release-build
310
* check instead of an assert?
312
assert(gc->gc.gc_refs != 0);
290
PyGC_Head *gc = containers->gc.gc_next;
291
for (; gc != containers; gc = gc->gc.gc_next) {
292
assert(gc->gc.gc_refs == GC_REACHABLE);
293
gc->gc.gc_refs = Py_REFCNT(FROM_GC(gc));
294
/* Python's cyclic gc should never see an incoming refcount
295
* of 0: if something decref'ed to 0, it should have been
296
* deallocated immediately at that time.
297
* Possible cause (if the assert triggers): a tp_dealloc
298
* routine left a gc-aware object tracked during its teardown
299
* phase, and did something-- or allowed something to happen --
300
* that called back into Python. gc can trigger then, and may
301
* see the still-tracked dying object. Before this assert
302
* was added, such mistakes went on to allow gc to try to
303
* delete the object again. In a debug build, that caused
304
* a mysterious segfault, when _Py_ForgetReference tried
305
* to remove the object from the doubly-linked list of all
306
* objects a second time. In a release build, an actual
307
* double deallocation occurred, which leads to corruption
308
* of the allocator's internal bookkeeping pointers. That's
309
* so serious that maybe this should be a release-build
310
* check instead of an assert?
312
assert(gc->gc.gc_refs != 0);
316
316
/* A traversal callback for subtract_refs. */
318
318
visit_decref(PyObject *op, void *data)
321
if (PyObject_IS_GC(op)) {
322
PyGC_Head *gc = AS_GC(op);
323
/* We're only interested in gc_refs for objects in the
324
* generation being collected, which can be recognized
325
* because only they have positive gc_refs.
327
assert(gc->gc.gc_refs != 0); /* else refcount was too small */
328
if (gc->gc.gc_refs > 0)
321
if (PyObject_IS_GC(op)) {
322
PyGC_Head *gc = AS_GC(op);
323
/* We're only interested in gc_refs for objects in the
324
* generation being collected, which can be recognized
325
* because only they have positive gc_refs.
327
assert(gc->gc.gc_refs != 0); /* else refcount was too small */
328
if (gc->gc.gc_refs > 0)
334
334
/* Subtract internal references from gc_refs. After this, gc_refs is >= 0
340
340
subtract_refs(PyGC_Head *containers)
342
traverseproc traverse;
343
PyGC_Head *gc = containers->gc.gc_next;
344
for (; gc != containers; gc=gc->gc.gc_next) {
345
traverse = Py_TYPE(FROM_GC(gc))->tp_traverse;
346
(void) traverse(FROM_GC(gc),
347
(visitproc)visit_decref,
342
traverseproc traverse;
343
PyGC_Head *gc = containers->gc.gc_next;
344
for (; gc != containers; gc=gc->gc.gc_next) {
345
traverse = Py_TYPE(FROM_GC(gc))->tp_traverse;
346
(void) traverse(FROM_GC(gc),
347
(visitproc)visit_decref,
352
352
/* A traversal callback for move_unreachable. */
354
354
visit_reachable(PyObject *op, PyGC_Head *reachable)
356
if (PyObject_IS_GC(op)) {
357
PyGC_Head *gc = AS_GC(op);
358
const Py_ssize_t gc_refs = gc->gc.gc_refs;
356
if (PyObject_IS_GC(op)) {
357
PyGC_Head *gc = AS_GC(op);
358
const Py_ssize_t gc_refs = gc->gc.gc_refs;
361
/* This is in move_unreachable's 'young' list, but
362
* the traversal hasn't yet gotten to it. All
363
* we need to do is tell move_unreachable that it's
368
else if (gc_refs == GC_TENTATIVELY_UNREACHABLE) {
369
/* This had gc_refs = 0 when move_unreachable got
370
* to it, but turns out it's reachable after all.
371
* Move it back to move_unreachable's 'young' list,
372
* and move_unreachable will eventually get to it
375
gc_list_move(gc, reachable);
378
/* Else there's nothing to do.
379
* If gc_refs > 0, it must be in move_unreachable's 'young'
380
* list, and move_unreachable will eventually get to it.
381
* If gc_refs == GC_REACHABLE, it's either in some other
382
* generation so we don't care about it, or move_unreachable
383
* already dealt with it.
384
* If gc_refs == GC_UNTRACKED, it must be ignored.
388
|| gc_refs == GC_REACHABLE
389
|| gc_refs == GC_UNTRACKED);
361
/* This is in move_unreachable's 'young' list, but
362
* the traversal hasn't yet gotten to it. All
363
* we need to do is tell move_unreachable that it's
368
else if (gc_refs == GC_TENTATIVELY_UNREACHABLE) {
369
/* This had gc_refs = 0 when move_unreachable got
370
* to it, but turns out it's reachable after all.
371
* Move it back to move_unreachable's 'young' list,
372
* and move_unreachable will eventually get to it
375
gc_list_move(gc, reachable);
378
/* Else there's nothing to do.
379
* If gc_refs > 0, it must be in move_unreachable's 'young'
380
* list, and move_unreachable will eventually get to it.
381
* If gc_refs == GC_REACHABLE, it's either in some other
382
* generation so we don't care about it, or move_unreachable
383
* already dealt with it.
384
* If gc_refs == GC_UNTRACKED, it must be ignored.
388
|| gc_refs == GC_REACHABLE
389
|| gc_refs == GC_UNTRACKED);
395
395
/* Move the unreachable objects from young to unreachable. After this,
404
404
move_unreachable(PyGC_Head *young, PyGC_Head *unreachable)
406
PyGC_Head *gc = young->gc.gc_next;
408
/* Invariants: all objects "to the left" of us in young have gc_refs
409
* = GC_REACHABLE, and are indeed reachable (directly or indirectly)
410
* from outside the young list as it was at entry. All other objects
411
* from the original young "to the left" of us are in unreachable now,
412
* and have gc_refs = GC_TENTATIVELY_UNREACHABLE. All objects to the
413
* left of us in 'young' now have been scanned, and no objects here
414
* or to the right have been scanned yet.
417
while (gc != young) {
420
if (gc->gc.gc_refs) {
421
/* gc is definitely reachable from outside the
422
* original 'young'. Mark it as such, and traverse
423
* its pointers to find any other objects that may
424
* be directly reachable from it. Note that the
425
* call to tp_traverse may append objects to young,
426
* so we have to wait until it returns to determine
427
* the next object to visit.
429
PyObject *op = FROM_GC(gc);
430
traverseproc traverse = Py_TYPE(op)->tp_traverse;
431
assert(gc->gc.gc_refs > 0);
432
gc->gc.gc_refs = GC_REACHABLE;
434
(visitproc)visit_reachable,
436
next = gc->gc.gc_next;
437
if (PyTuple_CheckExact(op)) {
438
_PyTuple_MaybeUntrack(op);
440
else if (PyDict_CheckExact(op)) {
441
_PyDict_MaybeUntrack(op);
445
/* This *may* be unreachable. To make progress,
446
* assume it is. gc isn't directly reachable from
447
* any object we've already traversed, but may be
448
* reachable from an object we haven't gotten to yet.
449
* visit_reachable will eventually move gc back into
450
* young if that's so, and we'll see it again.
452
next = gc->gc.gc_next;
453
gc_list_move(gc, unreachable);
454
gc->gc.gc_refs = GC_TENTATIVELY_UNREACHABLE;
406
PyGC_Head *gc = young->gc.gc_next;
408
/* Invariants: all objects "to the left" of us in young have gc_refs
409
* = GC_REACHABLE, and are indeed reachable (directly or indirectly)
410
* from outside the young list as it was at entry. All other objects
411
* from the original young "to the left" of us are in unreachable now,
412
* and have gc_refs = GC_TENTATIVELY_UNREACHABLE. All objects to the
413
* left of us in 'young' now have been scanned, and no objects here
414
* or to the right have been scanned yet.
417
while (gc != young) {
420
if (gc->gc.gc_refs) {
421
/* gc is definitely reachable from outside the
422
* original 'young'. Mark it as such, and traverse
423
* its pointers to find any other objects that may
424
* be directly reachable from it. Note that the
425
* call to tp_traverse may append objects to young,
426
* so we have to wait until it returns to determine
427
* the next object to visit.
429
PyObject *op = FROM_GC(gc);
430
traverseproc traverse = Py_TYPE(op)->tp_traverse;
431
assert(gc->gc.gc_refs > 0);
432
gc->gc.gc_refs = GC_REACHABLE;
434
(visitproc)visit_reachable,
436
next = gc->gc.gc_next;
437
if (PyTuple_CheckExact(op)) {
438
_PyTuple_MaybeUntrack(op);
440
else if (PyDict_CheckExact(op)) {
441
_PyDict_MaybeUntrack(op);
445
/* This *may* be unreachable. To make progress,
446
* assume it is. gc isn't directly reachable from
447
* any object we've already traversed, but may be
448
* reachable from an object we haven't gotten to yet.
449
* visit_reachable will eventually move gc back into
450
* young if that's so, and we'll see it again.
452
next = gc->gc.gc_next;
453
gc_list_move(gc, unreachable);
454
gc->gc.gc_refs = GC_TENTATIVELY_UNREACHABLE;
460
460
/* Return true if object has a finalization method. */
462
462
has_finalizer(PyObject *op)
464
if (PyGen_CheckExact(op))
465
return PyGen_NeedsFinalizing((PyGenObject *)op);
467
return op->ob_type->tp_del != NULL;
464
if (PyGen_CheckExact(op))
465
return PyGen_NeedsFinalizing((PyGenObject *)op);
467
return op->ob_type->tp_del != NULL;
470
470
/* Move the objects in unreachable with __del__ methods into `finalizers`.
539
539
handle_weakrefs(PyGC_Head *unreachable, PyGC_Head *old)
542
PyObject *op; /* generally FROM_GC(gc) */
543
PyWeakReference *wr; /* generally a cast of op */
544
PyGC_Head wrcb_to_call; /* weakrefs with callbacks to call */
548
gc_list_init(&wrcb_to_call);
550
/* Clear all weakrefs to the objects in unreachable. If such a weakref
551
* also has a callback, move it into `wrcb_to_call` if the callback
552
* needs to be invoked. Note that we cannot invoke any callbacks until
553
* all weakrefs to unreachable objects are cleared, lest the callback
554
* resurrect an unreachable object via a still-active weakref. We
555
* make another pass over wrcb_to_call, invoking callbacks, after this
558
for (gc = unreachable->gc.gc_next; gc != unreachable; gc = next) {
559
PyWeakReference **wrlist;
562
assert(IS_TENTATIVELY_UNREACHABLE(op));
563
next = gc->gc.gc_next;
565
if (! PyType_SUPPORTS_WEAKREFS(Py_TYPE(op)))
568
/* It supports weakrefs. Does it have any? */
569
wrlist = (PyWeakReference **)
570
PyObject_GET_WEAKREFS_LISTPTR(op);
572
/* `op` may have some weakrefs. March over the list, clear
573
* all the weakrefs, and move the weakrefs with callbacks
574
* that must be called into wrcb_to_call.
576
for (wr = *wrlist; wr != NULL; wr = *wrlist) {
577
PyGC_Head *wrasgc; /* AS_GC(wr) */
579
/* _PyWeakref_ClearRef clears the weakref but leaves
580
* the callback pointer intact. Obscure: it also
583
assert(wr->wr_object == op);
584
_PyWeakref_ClearRef(wr);
585
assert(wr->wr_object == Py_None);
586
if (wr->wr_callback == NULL)
587
continue; /* no callback */
589
/* Headache time. `op` is going away, and is weakly referenced by
590
* `wr`, which has a callback. Should the callback be invoked? If wr
593
* 1. There's no need to call it. The object and the weakref are
594
* both going away, so it's legitimate to pretend the weakref is
595
* going away first. The user has to ensure a weakref outlives its
596
* referent if they want a guarantee that the wr callback will get
599
* 2. It may be catastrophic to call it. If the callback is also in
600
* cyclic trash (CT), then although the CT is unreachable from
601
* outside the current generation, CT may be reachable from the
602
* callback. Then the callback could resurrect insane objects.
604
* Since the callback is never needed and may be unsafe in this case,
605
* wr is simply left in the unreachable set. Note that because we
606
* already called _PyWeakref_ClearRef(wr), its callback will never
609
* OTOH, if wr isn't part of CT, we should invoke the callback: the
610
* weakref outlived the trash. Note that since wr isn't CT in this
611
* case, its callback can't be CT either -- wr acted as an external
612
* root to this generation, and therefore its callback did too. So
613
* nothing in CT is reachable from the callback either, so it's hard
614
* to imagine how calling it later could create a problem for us. wr
615
* is moved to wrcb_to_call in this case.
617
if (IS_TENTATIVELY_UNREACHABLE(wr))
619
assert(IS_REACHABLE(wr));
621
/* Create a new reference so that wr can't go away
622
* before we can process it again.
626
/* Move wr to wrcb_to_call, for the next pass. */
628
assert(wrasgc != next); /* wrasgc is reachable, but
629
next isn't, so they can't
631
gc_list_move(wrasgc, &wrcb_to_call);
635
/* Invoke the callbacks we decided to honor. It's safe to invoke them
636
* because they can't reference unreachable objects.
638
while (! gc_list_is_empty(&wrcb_to_call)) {
642
gc = wrcb_to_call.gc.gc_next;
644
assert(IS_REACHABLE(op));
645
assert(PyWeakref_Check(op));
646
wr = (PyWeakReference *)op;
647
callback = wr->wr_callback;
648
assert(callback != NULL);
650
/* copy-paste of weakrefobject.c's handle_callback() */
651
temp = PyObject_CallFunctionObjArgs(callback, wr, NULL);
653
PyErr_WriteUnraisable(callback);
657
/* Give up the reference we created in the first pass. When
658
* op's refcount hits 0 (which it may or may not do right now),
659
* op's tp_dealloc will decref op->wr_callback too. Note
660
* that the refcount probably will hit 0 now, and because this
661
* weakref was reachable to begin with, gc didn't already
662
* add it to its count of freed objects. Example: a reachable
663
* weak value dict maps some key to this reachable weakref.
664
* The callback removes this key->weakref mapping from the
665
* dict, leaving no other references to the weakref (excepting
669
if (wrcb_to_call.gc.gc_next == gc) {
670
/* object is still alive -- move it */
671
gc_list_move(gc, old);
542
PyObject *op; /* generally FROM_GC(gc) */
543
PyWeakReference *wr; /* generally a cast of op */
544
PyGC_Head wrcb_to_call; /* weakrefs with callbacks to call */
548
gc_list_init(&wrcb_to_call);
550
/* Clear all weakrefs to the objects in unreachable. If such a weakref
551
* also has a callback, move it into `wrcb_to_call` if the callback
552
* needs to be invoked. Note that we cannot invoke any callbacks until
553
* all weakrefs to unreachable objects are cleared, lest the callback
554
* resurrect an unreachable object via a still-active weakref. We
555
* make another pass over wrcb_to_call, invoking callbacks, after this
558
for (gc = unreachable->gc.gc_next; gc != unreachable; gc = next) {
559
PyWeakReference **wrlist;
562
assert(IS_TENTATIVELY_UNREACHABLE(op));
563
next = gc->gc.gc_next;
565
if (! PyType_SUPPORTS_WEAKREFS(Py_TYPE(op)))
568
/* It supports weakrefs. Does it have any? */
569
wrlist = (PyWeakReference **)
570
PyObject_GET_WEAKREFS_LISTPTR(op);
572
/* `op` may have some weakrefs. March over the list, clear
573
* all the weakrefs, and move the weakrefs with callbacks
574
* that must be called into wrcb_to_call.
576
for (wr = *wrlist; wr != NULL; wr = *wrlist) {
577
PyGC_Head *wrasgc; /* AS_GC(wr) */
579
/* _PyWeakref_ClearRef clears the weakref but leaves
580
* the callback pointer intact. Obscure: it also
583
assert(wr->wr_object == op);
584
_PyWeakref_ClearRef(wr);
585
assert(wr->wr_object == Py_None);
586
if (wr->wr_callback == NULL)
587
continue; /* no callback */
589
/* Headache time. `op` is going away, and is weakly referenced by
590
* `wr`, which has a callback. Should the callback be invoked? If wr
593
* 1. There's no need to call it. The object and the weakref are
594
* both going away, so it's legitimate to pretend the weakref is
595
* going away first. The user has to ensure a weakref outlives its
596
* referent if they want a guarantee that the wr callback will get
599
* 2. It may be catastrophic to call it. If the callback is also in
600
* cyclic trash (CT), then although the CT is unreachable from
601
* outside the current generation, CT may be reachable from the
602
* callback. Then the callback could resurrect insane objects.
604
* Since the callback is never needed and may be unsafe in this case,
605
* wr is simply left in the unreachable set. Note that because we
606
* already called _PyWeakref_ClearRef(wr), its callback will never
609
* OTOH, if wr isn't part of CT, we should invoke the callback: the
610
* weakref outlived the trash. Note that since wr isn't CT in this
611
* case, its callback can't be CT either -- wr acted as an external
612
* root to this generation, and therefore its callback did too. So
613
* nothing in CT is reachable from the callback either, so it's hard
614
* to imagine how calling it later could create a problem for us. wr
615
* is moved to wrcb_to_call in this case.
617
if (IS_TENTATIVELY_UNREACHABLE(wr))
619
assert(IS_REACHABLE(wr));
621
/* Create a new reference so that wr can't go away
622
* before we can process it again.
626
/* Move wr to wrcb_to_call, for the next pass. */
628
assert(wrasgc != next); /* wrasgc is reachable, but
629
next isn't, so they can't
631
gc_list_move(wrasgc, &wrcb_to_call);
635
/* Invoke the callbacks we decided to honor. It's safe to invoke them
636
* because they can't reference unreachable objects.
638
while (! gc_list_is_empty(&wrcb_to_call)) {
642
gc = wrcb_to_call.gc.gc_next;
644
assert(IS_REACHABLE(op));
645
assert(PyWeakref_Check(op));
646
wr = (PyWeakReference *)op;
647
callback = wr->wr_callback;
648
assert(callback != NULL);
650
/* copy-paste of weakrefobject.c's handle_callback() */
651
temp = PyObject_CallFunctionObjArgs(callback, wr, NULL);
653
PyErr_WriteUnraisable(callback);
657
/* Give up the reference we created in the first pass. When
658
* op's refcount hits 0 (which it may or may not do right now),
659
* op's tp_dealloc will decref op->wr_callback too. Note
660
* that the refcount probably will hit 0 now, and because this
661
* weakref was reachable to begin with, gc didn't already
662
* add it to its count of freed objects. Example: a reachable
663
* weak value dict maps some key to this reachable weakref.
664
* The callback removes this key->weakref mapping from the
665
* dict, leaving no other references to the weakref (excepting
669
if (wrcb_to_call.gc.gc_next == gc) {
670
/* object is still alive -- move it */
671
gc_list_move(gc, old);
681
681
debug_cycle(char *msg, PyObject *op)
683
PySys_WriteStderr("gc: %.100s <%.100s %p>\n",
684
msg, Py_TYPE(op)->tp_name, op);
683
PySys_WriteStderr("gc: %.100s <%.100s %p>\n",
684
msg, Py_TYPE(op)->tp_name, op);
687
687
/* Handle uncollectable garbage (cycles with finalizers, and stuff reachable
697
697
handle_finalizers(PyGC_Head *finalizers, PyGC_Head *old)
699
PyGC_Head *gc = finalizers->gc.gc_next;
701
if (garbage == NULL) {
702
garbage = PyList_New(0);
704
Py_FatalError("gc couldn't create gc.garbage list");
706
for (; gc != finalizers; gc = gc->gc.gc_next) {
707
PyObject *op = FROM_GC(gc);
709
if ((debug & DEBUG_SAVEALL) || has_finalizer(op)) {
710
if (PyList_Append(garbage, op) < 0)
715
gc_list_merge(finalizers, old);
699
PyGC_Head *gc = finalizers->gc.gc_next;
701
if (garbage == NULL) {
702
garbage = PyList_New(0);
704
Py_FatalError("gc couldn't create gc.garbage list");
706
for (; gc != finalizers; gc = gc->gc.gc_next) {
707
PyObject *op = FROM_GC(gc);
709
if ((debug & DEBUG_SAVEALL) || has_finalizer(op)) {
710
if (PyList_Append(garbage, op) < 0)
715
gc_list_merge(finalizers, old);
719
/* Break reference cycles by clearing the containers involved. This is
719
/* Break reference cycles by clearing the containers involved. This is
720
720
* tricky business as the lists can be changing and we don't know which
721
721
* objects may be freed. It is possible I screwed something up here.
724
724
delete_garbage(PyGC_Head *collectable, PyGC_Head *old)
728
while (!gc_list_is_empty(collectable)) {
729
PyGC_Head *gc = collectable->gc.gc_next;
730
PyObject *op = FROM_GC(gc);
732
assert(IS_TENTATIVELY_UNREACHABLE(op));
733
if (debug & DEBUG_SAVEALL) {
734
PyList_Append(garbage, op);
737
if ((clear = Py_TYPE(op)->tp_clear) != NULL) {
743
if (collectable->gc.gc_next == gc) {
744
/* object is still alive, move it, it may die later */
745
gc_list_move(gc, old);
746
gc->gc.gc_refs = GC_REACHABLE;
728
while (!gc_list_is_empty(collectable)) {
729
PyGC_Head *gc = collectable->gc.gc_next;
730
PyObject *op = FROM_GC(gc);
732
assert(IS_TENTATIVELY_UNREACHABLE(op));
733
if (debug & DEBUG_SAVEALL) {
734
PyList_Append(garbage, op);
737
if ((clear = Py_TYPE(op)->tp_clear) != NULL) {
743
if (collectable->gc.gc_next == gc) {
744
/* object is still alive, move it, it may die later */
745
gc_list_move(gc, old);
746
gc->gc.gc_refs = GC_REACHABLE;
751
751
/* Clear all free lists
787
787
static Py_ssize_t
788
788
collect(int generation)
791
Py_ssize_t m = 0; /* # objects collected */
792
Py_ssize_t n = 0; /* # unreachable objects that couldn't be collected */
793
PyGC_Head *young; /* the generation we are examining */
794
PyGC_Head *old; /* next older generation */
795
PyGC_Head unreachable; /* non-problematic unreachable trash */
796
PyGC_Head finalizers; /* objects with, & reachable from, __del__ */
800
if (delstr == NULL) {
801
delstr = PyUnicode_InternFromString("__del__");
803
Py_FatalError("gc couldn't allocate \"__del__\"");
806
if (debug & DEBUG_STATS) {
808
PySys_WriteStderr("gc: collecting generation %d...\n",
810
PySys_WriteStderr("gc: objects in each generation:");
811
for (i = 0; i < NUM_GENERATIONS; i++)
812
PySys_WriteStderr(" %" PY_FORMAT_SIZE_T "d",
813
gc_list_size(GEN_HEAD(i)));
814
PySys_WriteStderr("\n");
817
/* update collection and allocation counters */
818
if (generation+1 < NUM_GENERATIONS)
819
generations[generation+1].count += 1;
820
for (i = 0; i <= generation; i++)
821
generations[i].count = 0;
823
/* merge younger generations with one we are currently collecting */
824
for (i = 0; i < generation; i++) {
825
gc_list_merge(GEN_HEAD(i), GEN_HEAD(generation));
828
/* handy references */
829
young = GEN_HEAD(generation);
830
if (generation < NUM_GENERATIONS-1)
831
old = GEN_HEAD(generation+1);
835
/* Using ob_refcnt and gc_refs, calculate which objects in the
836
* container set are reachable from outside the set (i.e., have a
837
* refcount greater than 0 when all the references within the
838
* set are taken into account).
841
subtract_refs(young);
843
/* Leave everything reachable from outside young in young, and move
844
* everything else (in young) to unreachable.
845
* NOTE: This used to move the reachable objects into a reachable
846
* set instead. But most things usually turn out to be reachable,
847
* so it's more efficient to move the unreachable things.
849
gc_list_init(&unreachable);
850
move_unreachable(young, &unreachable);
852
/* Move reachable objects to next generation. */
854
if (generation == NUM_GENERATIONS - 2) {
855
long_lived_pending += gc_list_size(young);
857
gc_list_merge(young, old);
860
long_lived_pending = 0;
861
long_lived_total = gc_list_size(young);
864
/* All objects in unreachable are trash, but objects reachable from
865
* finalizers can't safely be deleted. Python programmers should take
866
* care not to create such things. For Python, finalizers means
867
* instance objects with __del__ methods. Weakrefs with callbacks
868
* can also call arbitrary Python code but they will be dealt with by
871
gc_list_init(&finalizers);
872
move_finalizers(&unreachable, &finalizers);
873
/* finalizers contains the unreachable objects with a finalizer;
874
* unreachable objects reachable *from* those are also uncollectable,
875
* and we move those into the finalizers list too.
877
move_finalizer_reachable(&finalizers);
879
/* Collect statistics on collectable objects found and print
880
* debugging information.
882
for (gc = unreachable.gc.gc_next; gc != &unreachable;
883
gc = gc->gc.gc_next) {
885
if (debug & DEBUG_COLLECTABLE) {
886
debug_cycle("collectable", FROM_GC(gc));
890
/* Clear weakrefs and invoke callbacks as necessary. */
891
m += handle_weakrefs(&unreachable, old);
893
/* Call tp_clear on objects in the unreachable set. This will cause
894
* the reference cycles to be broken. It may also cause some objects
895
* in finalizers to be freed.
897
delete_garbage(&unreachable, old);
899
/* Collect statistics on uncollectable objects found and print
900
* debugging information. */
901
for (gc = finalizers.gc.gc_next;
903
gc = gc->gc.gc_next) {
905
if (debug & DEBUG_UNCOLLECTABLE)
906
debug_cycle("uncollectable", FROM_GC(gc));
908
if (debug & DEBUG_STATS) {
909
double t2 = get_time();
910
if (m == 0 && n == 0)
911
PySys_WriteStderr("gc: done");
915
"%" PY_FORMAT_SIZE_T "d unreachable, "
916
"%" PY_FORMAT_SIZE_T "d uncollectable",
919
PySys_WriteStderr(", %.4fs elapsed", t2-t1);
921
PySys_WriteStderr(".\n");
924
/* Append instances in the uncollectable set to a Python
925
* reachable list of garbage. The programmer has to deal with
926
* this if they insist on creating this type of structure.
928
(void)handle_finalizers(&finalizers, old);
930
/* Clear free list only during the collection of the highest
932
if (generation == NUM_GENERATIONS-1) {
936
if (PyErr_Occurred()) {
938
gc_str = PyUnicode_FromString("garbage collection");
939
PyErr_WriteUnraisable(gc_str);
940
Py_FatalError("unexpected exception during garbage collection");
791
Py_ssize_t m = 0; /* # objects collected */
792
Py_ssize_t n = 0; /* # unreachable objects that couldn't be collected */
793
PyGC_Head *young; /* the generation we are examining */
794
PyGC_Head *old; /* next older generation */
795
PyGC_Head unreachable; /* non-problematic unreachable trash */
796
PyGC_Head finalizers; /* objects with, & reachable from, __del__ */
800
if (delstr == NULL) {
801
delstr = PyUnicode_InternFromString("__del__");
803
Py_FatalError("gc couldn't allocate \"__del__\"");
806
if (debug & DEBUG_STATS) {
807
PySys_WriteStderr("gc: collecting generation %d...\n",
809
PySys_WriteStderr("gc: objects in each generation:");
810
for (i = 0; i < NUM_GENERATIONS; i++)
811
PySys_WriteStderr(" %" PY_FORMAT_SIZE_T "d",
812
gc_list_size(GEN_HEAD(i)));
814
PySys_WriteStderr("\n");
817
/* update collection and allocation counters */
818
if (generation+1 < NUM_GENERATIONS)
819
generations[generation+1].count += 1;
820
for (i = 0; i <= generation; i++)
821
generations[i].count = 0;
823
/* merge younger generations with one we are currently collecting */
824
for (i = 0; i < generation; i++) {
825
gc_list_merge(GEN_HEAD(i), GEN_HEAD(generation));
828
/* handy references */
829
young = GEN_HEAD(generation);
830
if (generation < NUM_GENERATIONS-1)
831
old = GEN_HEAD(generation+1);
835
/* Using ob_refcnt and gc_refs, calculate which objects in the
836
* container set are reachable from outside the set (i.e., have a
837
* refcount greater than 0 when all the references within the
838
* set are taken into account).
841
subtract_refs(young);
843
/* Leave everything reachable from outside young in young, and move
844
* everything else (in young) to unreachable.
845
* NOTE: This used to move the reachable objects into a reachable
846
* set instead. But most things usually turn out to be reachable,
847
* so it's more efficient to move the unreachable things.
849
gc_list_init(&unreachable);
850
move_unreachable(young, &unreachable);
852
/* Move reachable objects to next generation. */
854
if (generation == NUM_GENERATIONS - 2) {
855
long_lived_pending += gc_list_size(young);
857
gc_list_merge(young, old);
860
long_lived_pending = 0;
861
long_lived_total = gc_list_size(young);
864
/* All objects in unreachable are trash, but objects reachable from
865
* finalizers can't safely be deleted. Python programmers should take
866
* care not to create such things. For Python, finalizers means
867
* instance objects with __del__ methods. Weakrefs with callbacks
868
* can also call arbitrary Python code but they will be dealt with by
871
gc_list_init(&finalizers);
872
move_finalizers(&unreachable, &finalizers);
873
/* finalizers contains the unreachable objects with a finalizer;
874
* unreachable objects reachable *from* those are also uncollectable,
875
* and we move those into the finalizers list too.
877
move_finalizer_reachable(&finalizers);
879
/* Collect statistics on collectable objects found and print
880
* debugging information.
882
for (gc = unreachable.gc.gc_next; gc != &unreachable;
883
gc = gc->gc.gc_next) {
885
if (debug & DEBUG_COLLECTABLE) {
886
debug_cycle("collectable", FROM_GC(gc));
890
/* Clear weakrefs and invoke callbacks as necessary. */
891
m += handle_weakrefs(&unreachable, old);
893
/* Call tp_clear on objects in the unreachable set. This will cause
894
* the reference cycles to be broken. It may also cause some objects
895
* in finalizers to be freed.
897
delete_garbage(&unreachable, old);
899
/* Collect statistics on uncollectable objects found and print
900
* debugging information. */
901
for (gc = finalizers.gc.gc_next;
903
gc = gc->gc.gc_next) {
905
if (debug & DEBUG_UNCOLLECTABLE)
906
debug_cycle("uncollectable", FROM_GC(gc));
908
if (debug & DEBUG_STATS) {
909
double t2 = get_time();
910
if (m == 0 && n == 0)
911
PySys_WriteStderr("gc: done");
915
"%" PY_FORMAT_SIZE_T "d unreachable, "
916
"%" PY_FORMAT_SIZE_T "d uncollectable",
919
PySys_WriteStderr(", %.4fs elapsed", t2-t1);
921
PySys_WriteStderr(".\n");
924
/* Append instances in the uncollectable set to a Python
925
* reachable list of garbage. The programmer has to deal with
926
* this if they insist on creating this type of structure.
928
(void)handle_finalizers(&finalizers, old);
930
/* Clear free list only during the collection of the highest
932
if (generation == NUM_GENERATIONS-1) {
936
if (PyErr_Occurred()) {
938
gc_str = PyUnicode_FromString("garbage collection");
939
PyErr_WriteUnraisable(gc_str);
940
Py_FatalError("unexpected exception during garbage collection");
945
945
static Py_ssize_t
946
946
collect_generations(void)
951
/* Find the oldest generation (highest numbered) where the count
952
* exceeds the threshold. Objects in the that generation and
953
* generations younger than it will be collected. */
954
for (i = NUM_GENERATIONS-1; i >= 0; i--) {
955
if (generations[i].count > generations[i].threshold) {
956
/* Avoid quadratic performance degradation in number
957
of tracked objects. See comments at the beginning
958
of this file, and issue #4074.
960
if (i == NUM_GENERATIONS - 1
961
&& long_lived_pending < long_lived_total / 4)
951
/* Find the oldest generation (highest numbered) where the count
952
* exceeds the threshold. Objects in the that generation and
953
* generations younger than it will be collected. */
954
for (i = NUM_GENERATIONS-1; i >= 0; i--) {
955
if (generations[i].count > generations[i].threshold) {
956
/* Avoid quadratic performance degradation in number
957
of tracked objects. See comments at the beginning
958
of this file, and issue #4074.
960
if (i == NUM_GENERATIONS - 1
961
&& long_lived_pending < long_lived_total / 4)
970
970
PyDoc_STRVAR(gc_enable__doc__,
1274
1274
"get_referents() -- Return the list of objects that an object refers to.\n");
1276
1276
static PyMethodDef GcMethods[] = {
1277
{"enable", gc_enable, METH_NOARGS, gc_enable__doc__},
1278
{"disable", gc_disable, METH_NOARGS, gc_disable__doc__},
1279
{"isenabled", gc_isenabled, METH_NOARGS, gc_isenabled__doc__},
1280
{"set_debug", gc_set_debug, METH_VARARGS, gc_set_debug__doc__},
1281
{"get_debug", gc_get_debug, METH_NOARGS, gc_get_debug__doc__},
1282
{"get_count", gc_get_count, METH_NOARGS, gc_get_count__doc__},
1283
{"set_threshold", gc_set_thresh, METH_VARARGS, gc_set_thresh__doc__},
1284
{"get_threshold", gc_get_thresh, METH_NOARGS, gc_get_thresh__doc__},
1285
{"collect", (PyCFunction)gc_collect,
1286
METH_VARARGS | METH_KEYWORDS, gc_collect__doc__},
1287
{"get_objects", gc_get_objects,METH_NOARGS, gc_get_objects__doc__},
1288
{"is_tracked", gc_is_tracked, METH_O, gc_is_tracked__doc__},
1289
{"get_referrers", gc_get_referrers, METH_VARARGS,
1290
gc_get_referrers__doc__},
1291
{"get_referents", gc_get_referents, METH_VARARGS,
1292
gc_get_referents__doc__},
1293
{NULL, NULL} /* Sentinel */
1277
{"enable", gc_enable, METH_NOARGS, gc_enable__doc__},
1278
{"disable", gc_disable, METH_NOARGS, gc_disable__doc__},
1279
{"isenabled", gc_isenabled, METH_NOARGS, gc_isenabled__doc__},
1280
{"set_debug", gc_set_debug, METH_VARARGS, gc_set_debug__doc__},
1281
{"get_debug", gc_get_debug, METH_NOARGS, gc_get_debug__doc__},
1282
{"get_count", gc_get_count, METH_NOARGS, gc_get_count__doc__},
1283
{"set_threshold", gc_set_thresh, METH_VARARGS, gc_set_thresh__doc__},
1284
{"get_threshold", gc_get_thresh, METH_NOARGS, gc_get_thresh__doc__},
1285
{"collect", (PyCFunction)gc_collect,
1286
METH_VARARGS | METH_KEYWORDS, gc_collect__doc__},
1287
{"get_objects", gc_get_objects,METH_NOARGS, gc_get_objects__doc__},
1288
{"is_tracked", gc_is_tracked, METH_O, gc_is_tracked__doc__},
1289
{"get_referrers", gc_get_referrers, METH_VARARGS,
1290
gc_get_referrers__doc__},
1291
{"get_referents", gc_get_referents, METH_VARARGS,
1292
gc_get_referents__doc__},
1293
{NULL, NULL} /* Sentinel */
1296
1296
static struct PyModuleDef gcmodule = {
1297
PyModuleDef_HEAD_INIT,
1297
PyModuleDef_HEAD_INIT,
1310
1310
PyInit_gc(void)
1314
m = PyModule_Create(&gcmodule);
1319
if (garbage == NULL) {
1320
garbage = PyList_New(0);
1321
if (garbage == NULL)
1325
if (PyModule_AddObject(m, "garbage", garbage) < 0)
1328
/* Importing can't be done in collect() because collect()
1329
* can be called via PyGC_Collect() in Py_Finalize().
1330
* This wouldn't be a problem, except that <initialized> is
1331
* reset to 0 before calling collect which trips up
1332
* the import and triggers an assertion.
1335
tmod = PyImport_ImportModuleNoBlock("time");
1314
m = PyModule_Create(&gcmodule);
1319
if (garbage == NULL) {
1320
garbage = PyList_New(0);
1321
if (garbage == NULL)
1325
if (PyModule_AddObject(m, "garbage", garbage) < 0)
1328
/* Importing can't be done in collect() because collect()
1329
* can be called via PyGC_Collect() in Py_Finalize().
1330
* This wouldn't be a problem, except that <initialized> is
1331
* reset to 0 before calling collect which trips up
1332
* the import and triggers an assertion.
1335
tmod = PyImport_ImportModuleNoBlock("time");
1340
1340
#define ADD_INT(NAME) if (PyModule_AddIntConstant(m, #NAME, NAME) < 0) return NULL
1341
ADD_INT(DEBUG_STATS);
1342
ADD_INT(DEBUG_COLLECTABLE);
1343
ADD_INT(DEBUG_UNCOLLECTABLE);
1344
ADD_INT(DEBUG_SAVEALL);
1345
ADD_INT(DEBUG_LEAK);
1341
ADD_INT(DEBUG_STATS);
1342
ADD_INT(DEBUG_COLLECTABLE);
1343
ADD_INT(DEBUG_UNCOLLECTABLE);
1344
ADD_INT(DEBUG_SAVEALL);
1345
ADD_INT(DEBUG_LEAK);
1350
1350
/* API to invoke gc.collect() from C */
1352
1352
PyGC_Collect(void)
1357
n = 0; /* already collecting, don't do anything */
1360
n = collect(NUM_GENERATIONS - 1);
1357
n = 0; /* already collecting, don't do anything */
1360
n = collect(NUM_GENERATIONS - 1);
1367
1367
/* for debugging */
1369
1369
_PyGC_Dump(PyGC_Head *g)
1371
_PyObject_Dump(FROM_GC(g));
1371
_PyObject_Dump(FROM_GC(g));
1374
1374
/* extension modules might be compiled with GC support so these
1413
1413
_PyObject_GC_Malloc(size_t basicsize)
1417
if (basicsize > PY_SSIZE_T_MAX - sizeof(PyGC_Head))
1418
return PyErr_NoMemory();
1419
g = (PyGC_Head *)PyObject_MALLOC(
1420
sizeof(PyGC_Head) + basicsize);
1422
return PyErr_NoMemory();
1423
g->gc.gc_refs = GC_UNTRACKED;
1424
generations[0].count++; /* number of allocated GC objects */
1425
if (generations[0].count > generations[0].threshold &&
1427
generations[0].threshold &&
1429
!PyErr_Occurred()) {
1431
collect_generations();
1417
if (basicsize > PY_SSIZE_T_MAX - sizeof(PyGC_Head))
1418
return PyErr_NoMemory();
1419
g = (PyGC_Head *)PyObject_MALLOC(
1420
sizeof(PyGC_Head) + basicsize);
1422
return PyErr_NoMemory();
1423
g->gc.gc_refs = GC_UNTRACKED;
1424
generations[0].count++; /* number of allocated GC objects */
1425
if (generations[0].count > generations[0].threshold &&
1427
generations[0].threshold &&
1429
!PyErr_Occurred()) {
1431
collect_generations();
1439
1439
_PyObject_GC_New(PyTypeObject *tp)
1441
PyObject *op = _PyObject_GC_Malloc(_PyObject_SIZE(tp));
1443
op = PyObject_INIT(op, tp);
1441
PyObject *op = _PyObject_GC_Malloc(_PyObject_SIZE(tp));
1443
op = PyObject_INIT(op, tp);
1448
1448
_PyObject_GC_NewVar(PyTypeObject *tp, Py_ssize_t nitems)
1450
const size_t size = _PyObject_VAR_SIZE(tp, nitems);
1451
PyVarObject *op = (PyVarObject *) _PyObject_GC_Malloc(size);
1453
op = PyObject_INIT_VAR(op, tp, nitems);
1450
const size_t size = _PyObject_VAR_SIZE(tp, nitems);
1451
PyVarObject *op = (PyVarObject *) _PyObject_GC_Malloc(size);
1453
op = PyObject_INIT_VAR(op, tp, nitems);
1458
1458
_PyObject_GC_Resize(PyVarObject *op, Py_ssize_t nitems)
1460
const size_t basicsize = _PyObject_VAR_SIZE(Py_TYPE(op), nitems);
1461
PyGC_Head *g = AS_GC(op);
1462
if (basicsize > PY_SSIZE_T_MAX - sizeof(PyGC_Head))
1463
return (PyVarObject *)PyErr_NoMemory();
1464
g = (PyGC_Head *)PyObject_REALLOC(g, sizeof(PyGC_Head) + basicsize);
1466
return (PyVarObject *)PyErr_NoMemory();
1467
op = (PyVarObject *) FROM_GC(g);
1468
Py_SIZE(op) = nitems;
1460
const size_t basicsize = _PyObject_VAR_SIZE(Py_TYPE(op), nitems);
1461
PyGC_Head *g = AS_GC(op);
1462
if (basicsize > PY_SSIZE_T_MAX - sizeof(PyGC_Head))
1463
return (PyVarObject *)PyErr_NoMemory();
1464
g = (PyGC_Head *)PyObject_REALLOC(g, sizeof(PyGC_Head) + basicsize);
1466
return (PyVarObject *)PyErr_NoMemory();
1467
op = (PyVarObject *) FROM_GC(g);
1468
Py_SIZE(op) = nitems;
1473
1473
PyObject_GC_Del(void *op)
1475
PyGC_Head *g = AS_GC(op);
1478
if (generations[0].count > 0) {
1479
generations[0].count--;
1475
PyGC_Head *g = AS_GC(op);
1478
if (generations[0].count > 0) {
1479
generations[0].count--;
1484
1484
/* for binary compatibility with 2.2 */