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