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