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