blob: 444092e08db2b1660bf7f13d8791968b61a7b9e8 [file] [log] [blame]
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +00001/*
Tim Peters88396172002-06-30 17:56:40 +00002
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +00003 Reference Cycle Garbage Collection
4 ==================================
5
Neil Schemenauerb2c2c9e2000-10-04 16:34:09 +00006 Neil Schemenauer <nas@arctrix.com>
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +00007
8 Based on a post on the python-dev list. Ideas from Guido van Rossum,
9 Eric Tiedemann, and various others.
10
Neil Schemenauer43411b52001-08-30 00:05:51 +000011 http://www.arctrix.com/nas/python/gc/
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +000012 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
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +000019*/
20
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +000021#include "Python.h"
22
Neil Schemenauer43411b52001-08-30 00:05:51 +000023/* Get an object's GC head */
24#define AS_GC(o) ((PyGC_Head *)(o)-1)
25
26/* Get the object given the GC head */
27#define FROM_GC(g) ((PyObject *)(((PyGC_Head *)g)+1))
28
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +000029/*** Global GC state ***/
30
Neil Schemenauer2880ae52002-05-04 05:35:20 +000031struct gc_generation {
32 PyGC_Head head;
33 int threshold; /* collection threshold */
34 int count; /* count of allocations or collections of younger
35 generations */
36};
37
38#define NUM_GENERATIONS 3
39#define GEN_HEAD(n) (&generations[n].head)
40
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +000041/* linked lists of container objects */
Neil Schemenauer2880ae52002-05-04 05:35:20 +000042static struct gc_generation generations[NUM_GENERATIONS] = {
43 /* PyGC_Head, threshold, count */
44 {{{GEN_HEAD(0), GEN_HEAD(0), 0}}, 700, 0},
45 {{{GEN_HEAD(1), GEN_HEAD(1), 0}}, 10, 0},
46 {{{GEN_HEAD(2), GEN_HEAD(2), 0}}, 10, 0},
47};
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +000048
Neil Schemenauer2880ae52002-05-04 05:35:20 +000049PyGC_Head *_PyGC_generation0 = GEN_HEAD(0);
50
Vladimir Marangozovf9d20c32000-08-06 22:45:31 +000051static int enabled = 1; /* automatic collection enabled? */
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +000052
Neil Schemenauer43411b52001-08-30 00:05:51 +000053/* true if we are currently running the collector */
Tim Petersbf384c22003-04-06 00:11:39 +000054static int collecting = 0;
Neil Schemenauer43411b52001-08-30 00:05:51 +000055
Tim Peters6fc13d92002-07-02 18:12:35 +000056/* list of uncollectable objects */
Tim Petersbf384c22003-04-06 00:11:39 +000057static PyObject *garbage = NULL;
Tim Peters6fc13d92002-07-02 18:12:35 +000058
59/* Python string to use if unhandled exception occurs */
Tim Petersbf384c22003-04-06 00:11:39 +000060static PyObject *gc_str = NULL;
Tim Peters6fc13d92002-07-02 18:12:35 +000061
Tim Peters93ad66d2003-04-05 17:15:44 +000062/* Python string used to look for __del__ attribute. */
63static PyObject *delstr = NULL;
Jeremy Hyltonce136e92003-04-04 19:59:06 +000064
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +000065/* set for debugging information */
66#define DEBUG_STATS (1<<0) /* print collection statistics */
67#define DEBUG_COLLECTABLE (1<<1) /* print collectable objects */
68#define DEBUG_UNCOLLECTABLE (1<<2) /* print uncollectable objects */
69#define DEBUG_INSTANCES (1<<3) /* print instances */
70#define DEBUG_OBJECTS (1<<4) /* print other objects */
Neil Schemenauer544de1e2000-09-22 15:22:38 +000071#define DEBUG_SAVEALL (1<<5) /* save all garbage in gc.garbage */
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +000072#define DEBUG_LEAK DEBUG_COLLECTABLE | \
73 DEBUG_UNCOLLECTABLE | \
74 DEBUG_INSTANCES | \
Neil Schemenauer544de1e2000-09-22 15:22:38 +000075 DEBUG_OBJECTS | \
76 DEBUG_SAVEALL
Jeremy Hyltonb709df32000-09-01 02:47:25 +000077static int debug;
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +000078
Tim Peters6fc13d92002-07-02 18:12:35 +000079/*--------------------------------------------------------------------------
80gc_refs values.
Neil Schemenauer43411b52001-08-30 00:05:51 +000081
Tim Peters6fc13d92002-07-02 18:12:35 +000082Between collections, every gc'ed object has one of two gc_refs values:
83
84GC_UNTRACKED
85 The initial state; objects returned by PyObject_GC_Malloc are in this
86 state. The object doesn't live in any generation list, and its
87 tp_traverse slot must not be called.
88
89GC_REACHABLE
90 The object lives in some generation list, and its tp_traverse is safe to
91 call. An object transitions to GC_REACHABLE when PyObject_GC_Track
92 is called.
93
94During a collection, gc_refs can temporarily take on other states:
95
96>= 0
97 At the start of a collection, update_refs() copies the true refcount
98 to gc_refs, for each object in the generation being collected.
99 subtract_refs() then adjusts gc_refs so that it equals the number of
100 times an object is referenced directly from outside the generation
101 being collected.
Martin v. Löwis774348c2002-11-09 19:54:06 +0000102 gc_refs remains >= 0 throughout these steps.
Tim Peters6fc13d92002-07-02 18:12:35 +0000103
104GC_TENTATIVELY_UNREACHABLE
105 move_unreachable() then moves objects not reachable (whether directly or
106 indirectly) from outside the generation into an "unreachable" set.
107 Objects that are found to be reachable have gc_refs set to GC_REACHABLE
108 again. Objects that are found to be unreachable have gc_refs set to
109 GC_TENTATIVELY_UNREACHABLE. It's "tentatively" because the pass doing
110 this can't be sure until it ends, and GC_TENTATIVELY_UNREACHABLE may
111 transition back to GC_REACHABLE.
112
113 Only objects with GC_TENTATIVELY_UNREACHABLE still set are candidates
114 for collection. If it's decided not to collect such an object (e.g.,
115 it has a __del__ method), its gc_refs is restored to GC_REACHABLE again.
116----------------------------------------------------------------------------
117*/
Tim Petersea405632002-07-02 00:52:30 +0000118#define GC_UNTRACKED _PyGC_REFS_UNTRACKED
119#define GC_REACHABLE _PyGC_REFS_REACHABLE
120#define GC_TENTATIVELY_UNREACHABLE _PyGC_REFS_TENTATIVELY_UNREACHABLE
Tim Peters19b74c72002-07-01 03:52:19 +0000121
Tim Peters6fc13d92002-07-02 18:12:35 +0000122#define IS_TRACKED(o) ((AS_GC(o))->gc.gc_refs != GC_UNTRACKED)
Tim Peters19b74c72002-07-01 03:52:19 +0000123#define IS_REACHABLE(o) ((AS_GC(o))->gc.gc_refs == GC_REACHABLE)
124#define IS_TENTATIVELY_UNREACHABLE(o) ( \
125 (AS_GC(o))->gc.gc_refs == GC_TENTATIVELY_UNREACHABLE)
Neil Schemenauera2b11ec2002-05-21 15:53:24 +0000126
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000127/*** list functions ***/
128
129static void
130gc_list_init(PyGC_Head *list)
131{
Tim Peters9e4ca102001-10-11 18:31:31 +0000132 list->gc.gc_prev = list;
133 list->gc.gc_next = list;
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000134}
135
Neil Schemenauer2880ae52002-05-04 05:35:20 +0000136static int
137gc_list_is_empty(PyGC_Head *list)
138{
139 return (list->gc.gc_next == list);
140}
141
Tim Peterse2d59182004-11-01 01:39:08 +0000142#if 0
143/* This became unused after gc_list_move() was introduced. */
144/* Append `node` to `list`. */
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000145static void
146gc_list_append(PyGC_Head *node, PyGC_Head *list)
147{
Tim Peters9e4ca102001-10-11 18:31:31 +0000148 node->gc.gc_next = list;
149 node->gc.gc_prev = list->gc.gc_prev;
150 node->gc.gc_prev->gc.gc_next = node;
151 list->gc.gc_prev = node;
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000152}
Tim Peterse2d59182004-11-01 01:39:08 +0000153#endif
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000154
Tim Peterse2d59182004-11-01 01:39:08 +0000155/* Remove `node` from the gc list it's currently in. */
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000156static void
157gc_list_remove(PyGC_Head *node)
158{
Tim Peters9e4ca102001-10-11 18:31:31 +0000159 node->gc.gc_prev->gc.gc_next = node->gc.gc_next;
160 node->gc.gc_next->gc.gc_prev = node->gc.gc_prev;
161 node->gc.gc_next = NULL; /* object is not currently tracked */
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000162}
163
Tim Peterse2d59182004-11-01 01:39:08 +0000164/* Move `node` from the gc list it's currently in (which is not explicitly
165 * named here) to the end of `list`. This is semantically the same as
166 * gc_list_remove(node) followed by gc_list_append(node, list).
167 */
168static void
169gc_list_move(PyGC_Head *node, PyGC_Head *list)
170{
Tim Petersbc1d1b82004-11-01 16:39:57 +0000171 PyGC_Head *new_prev;
Tim Peterse2d59182004-11-01 01:39:08 +0000172 PyGC_Head *current_prev = node->gc.gc_prev;
173 PyGC_Head *current_next = node->gc.gc_next;
Tim Petersbc1d1b82004-11-01 16:39:57 +0000174 /* Unlink from current list. */
Tim Peterse2d59182004-11-01 01:39:08 +0000175 current_prev->gc.gc_next = current_next;
176 current_next->gc.gc_prev = current_prev;
Tim Petersbc1d1b82004-11-01 16:39:57 +0000177 /* Relink at end of new list. */
178 new_prev = node->gc.gc_prev = list->gc.gc_prev;
Tim Peterse2d59182004-11-01 01:39:08 +0000179 new_prev->gc.gc_next = list->gc.gc_prev = node;
Tim Petersbc1d1b82004-11-01 16:39:57 +0000180 node->gc.gc_next = list;
Tim Peterse2d59182004-11-01 01:39:08 +0000181}
182
183/* append list `from` onto list `to`; `from` becomes an empty list */
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000184static void
185gc_list_merge(PyGC_Head *from, PyGC_Head *to)
186{
187 PyGC_Head *tail;
Tim Peterse2d59182004-11-01 01:39:08 +0000188 assert(from != to);
Neil Schemenauer2880ae52002-05-04 05:35:20 +0000189 if (!gc_list_is_empty(from)) {
Tim Peters9e4ca102001-10-11 18:31:31 +0000190 tail = to->gc.gc_prev;
191 tail->gc.gc_next = from->gc.gc_next;
192 tail->gc.gc_next->gc.gc_prev = tail;
193 to->gc.gc_prev = from->gc.gc_prev;
194 to->gc.gc_prev->gc.gc_next = to;
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000195 }
196 gc_list_init(from);
197}
198
Neal Norwitz7b216c52006-03-04 20:01:53 +0000199static Py_ssize_t
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000200gc_list_size(PyGC_Head *list)
201{
202 PyGC_Head *gc;
Neal Norwitz7b216c52006-03-04 20:01:53 +0000203 Py_ssize_t n = 0;
Tim Peters9e4ca102001-10-11 18:31:31 +0000204 for (gc = list->gc.gc_next; gc != list; gc = gc->gc.gc_next) {
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000205 n++;
206 }
207 return n;
208}
209
Tim Peters259272b2003-04-06 19:41:39 +0000210/* Append objects in a GC list to a Python list.
211 * Return 0 if all OK, < 0 if error (out of memory for list).
212 */
213static int
214append_objects(PyObject *py_list, PyGC_Head *gc_list)
215{
216 PyGC_Head *gc;
217 for (gc = gc_list->gc.gc_next; gc != gc_list; gc = gc->gc.gc_next) {
218 PyObject *op = FROM_GC(gc);
219 if (op != py_list) {
220 if (PyList_Append(py_list, op)) {
221 return -1; /* exception */
222 }
223 }
224 }
225 return 0;
226}
227
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000228/*** end of list stuff ***/
229
230
Tim Peters19b74c72002-07-01 03:52:19 +0000231/* Set all gc_refs = ob_refcnt. After this, gc_refs is > 0 for all objects
232 * in containers, and is GC_REACHABLE for all tracked gc objects not in
233 * containers.
Tim Peters88396172002-06-30 17:56:40 +0000234 */
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000235static void
236update_refs(PyGC_Head *containers)
237{
Tim Peters9e4ca102001-10-11 18:31:31 +0000238 PyGC_Head *gc = containers->gc.gc_next;
Tim Petersea405632002-07-02 00:52:30 +0000239 for (; gc != containers; gc = gc->gc.gc_next) {
240 assert(gc->gc.gc_refs == GC_REACHABLE);
Tim Peters9e4ca102001-10-11 18:31:31 +0000241 gc->gc.gc_refs = FROM_GC(gc)->ob_refcnt;
Tim Peters780c4972003-11-14 00:01:17 +0000242 /* Python's cyclic gc should never see an incoming refcount
243 * of 0: if something decref'ed to 0, it should have been
244 * deallocated immediately at that time.
245 * Possible cause (if the assert triggers): a tp_dealloc
246 * routine left a gc-aware object tracked during its teardown
247 * phase, and did something-- or allowed something to happen --
248 * that called back into Python. gc can trigger then, and may
249 * see the still-tracked dying object. Before this assert
250 * was added, such mistakes went on to allow gc to try to
251 * delete the object again. In a debug build, that caused
252 * a mysterious segfault, when _Py_ForgetReference tried
253 * to remove the object from the doubly-linked list of all
254 * objects a second time. In a release build, an actual
255 * double deallocation occurred, which leads to corruption
256 * of the allocator's internal bookkeeping pointers. That's
257 * so serious that maybe this should be a release-build
258 * check instead of an assert?
259 */
260 assert(gc->gc.gc_refs != 0);
Tim Petersea405632002-07-02 00:52:30 +0000261 }
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000262}
263
Tim Peters19b74c72002-07-01 03:52:19 +0000264/* A traversal callback for subtract_refs. */
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000265static int
266visit_decref(PyObject *op, void *data)
267{
Tim Peters93cd83e2002-06-30 21:31:03 +0000268 assert(op != NULL);
Tim Peters19b74c72002-07-01 03:52:19 +0000269 if (PyObject_IS_GC(op)) {
270 PyGC_Head *gc = AS_GC(op);
271 /* We're only interested in gc_refs for objects in the
272 * generation being collected, which can be recognized
273 * because only they have positive gc_refs.
274 */
Tim Petersaab713b2002-07-02 22:15:28 +0000275 assert(gc->gc.gc_refs != 0); /* else refcount was too small */
Tim Peters19b74c72002-07-01 03:52:19 +0000276 if (gc->gc.gc_refs > 0)
277 gc->gc.gc_refs--;
278 }
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000279 return 0;
280}
281
Tim Peters19b74c72002-07-01 03:52:19 +0000282/* Subtract internal references from gc_refs. After this, gc_refs is >= 0
283 * for all objects in containers, and is GC_REACHABLE for all tracked gc
284 * objects not in containers. The ones with gc_refs > 0 are directly
285 * reachable from outside containers, and so can't be collected.
286 */
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000287static void
288subtract_refs(PyGC_Head *containers)
289{
290 traverseproc traverse;
Tim Peters9e4ca102001-10-11 18:31:31 +0000291 PyGC_Head *gc = containers->gc.gc_next;
292 for (; gc != containers; gc=gc->gc.gc_next) {
Neil Schemenauer43411b52001-08-30 00:05:51 +0000293 traverse = FROM_GC(gc)->ob_type->tp_traverse;
294 (void) traverse(FROM_GC(gc),
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000295 (visitproc)visit_decref,
296 NULL);
297 }
298}
299
Tim Peters19b74c72002-07-01 03:52:19 +0000300/* A traversal callback for move_unreachable. */
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000301static int
Tim Peters19b74c72002-07-01 03:52:19 +0000302visit_reachable(PyObject *op, PyGC_Head *reachable)
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000303{
Tim Petersea405632002-07-02 00:52:30 +0000304 if (PyObject_IS_GC(op)) {
Tim Peters19b74c72002-07-01 03:52:19 +0000305 PyGC_Head *gc = AS_GC(op);
Martin v. Löwis6db0e002006-03-01 16:56:25 +0000306 const Py_ssize_t gc_refs = gc->gc.gc_refs;
Tim Peters19b74c72002-07-01 03:52:19 +0000307
308 if (gc_refs == 0) {
309 /* This is in move_unreachable's 'young' list, but
310 * the traversal hasn't yet gotten to it. All
311 * we need to do is tell move_unreachable that it's
312 * reachable.
313 */
314 gc->gc.gc_refs = 1;
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000315 }
Tim Peters19b74c72002-07-01 03:52:19 +0000316 else if (gc_refs == GC_TENTATIVELY_UNREACHABLE) {
317 /* This had gc_refs = 0 when move_unreachable got
318 * to it, but turns out it's reachable after all.
319 * Move it back to move_unreachable's 'young' list,
320 * and move_unreachable will eventually get to it
321 * again.
322 */
Tim Peterse2d59182004-11-01 01:39:08 +0000323 gc_list_move(gc, reachable);
Tim Peters19b74c72002-07-01 03:52:19 +0000324 gc->gc.gc_refs = 1;
325 }
326 /* Else there's nothing to do.
327 * If gc_refs > 0, it must be in move_unreachable's 'young'
328 * list, and move_unreachable will eventually get to it.
329 * If gc_refs == GC_REACHABLE, it's either in some other
330 * generation so we don't care about it, or move_unreachable
Tim Peters6fc13d92002-07-02 18:12:35 +0000331 * already dealt with it.
Tim Petersea405632002-07-02 00:52:30 +0000332 * If gc_refs == GC_UNTRACKED, it must be ignored.
Tim Peters19b74c72002-07-01 03:52:19 +0000333 */
Tim Petersea405632002-07-02 00:52:30 +0000334 else {
335 assert(gc_refs > 0
336 || gc_refs == GC_REACHABLE
337 || gc_refs == GC_UNTRACKED);
338 }
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000339 }
340 return 0;
341}
342
Tim Peters19b74c72002-07-01 03:52:19 +0000343/* Move the unreachable objects from young to unreachable. After this,
344 * all objects in young have gc_refs = GC_REACHABLE, and all objects in
345 * unreachable have gc_refs = GC_TENTATIVELY_UNREACHABLE. All tracked
346 * gc objects not in young or unreachable still have gc_refs = GC_REACHABLE.
347 * All objects in young after this are directly or indirectly reachable
348 * from outside the original young; and all objects in unreachable are
349 * not.
Tim Peters88396172002-06-30 17:56:40 +0000350 */
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000351static void
Tim Peters19b74c72002-07-01 03:52:19 +0000352move_unreachable(PyGC_Head *young, PyGC_Head *unreachable)
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000353{
Tim Peters19b74c72002-07-01 03:52:19 +0000354 PyGC_Head *gc = young->gc.gc_next;
355
356 /* Invariants: all objects "to the left" of us in young have gc_refs
357 * = GC_REACHABLE, and are indeed reachable (directly or indirectly)
358 * from outside the young list as it was at entry. All other objects
359 * from the original young "to the left" of us are in unreachable now,
360 * and have gc_refs = GC_TENTATIVELY_UNREACHABLE. All objects to the
361 * left of us in 'young' now have been scanned, and no objects here
362 * or to the right have been scanned yet.
363 */
364
365 while (gc != young) {
366 PyGC_Head *next;
367
Tim Peters6fc13d92002-07-02 18:12:35 +0000368 if (gc->gc.gc_refs) {
369 /* gc is definitely reachable from outside the
370 * original 'young'. Mark it as such, and traverse
371 * its pointers to find any other objects that may
372 * be directly reachable from it. Note that the
373 * call to tp_traverse may append objects to young,
374 * so we have to wait until it returns to determine
375 * the next object to visit.
376 */
377 PyObject *op = FROM_GC(gc);
378 traverseproc traverse = op->ob_type->tp_traverse;
379 assert(gc->gc.gc_refs > 0);
380 gc->gc.gc_refs = GC_REACHABLE;
381 (void) traverse(op,
382 (visitproc)visit_reachable,
383 (void *)young);
384 next = gc->gc.gc_next;
385 }
386 else {
Tim Peters19b74c72002-07-01 03:52:19 +0000387 /* This *may* be unreachable. To make progress,
388 * assume it is. gc isn't directly reachable from
389 * any object we've already traversed, but may be
390 * reachable from an object we haven't gotten to yet.
391 * visit_reachable will eventually move gc back into
392 * young if that's so, and we'll see it again.
393 */
394 next = gc->gc.gc_next;
Tim Peterse2d59182004-11-01 01:39:08 +0000395 gc_list_move(gc, unreachable);
Tim Peters19b74c72002-07-01 03:52:19 +0000396 gc->gc.gc_refs = GC_TENTATIVELY_UNREACHABLE;
397 }
Tim Peters19b74c72002-07-01 03:52:19 +0000398 gc = next;
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000399 }
400}
401
Tim Peters86b993b2003-04-05 17:35:54 +0000402/* Return true if object has a finalization method.
403 * CAUTION: An instance of an old-style class has to be checked for a
Tim Petersf6b80452003-04-07 19:21:15 +0000404 *__del__ method, and earlier versions of this used to call PyObject_HasAttr,
405 * which in turn could call the class's __getattr__ hook (if any). That
406 * could invoke arbitrary Python code, mutating the object graph in arbitrary
407 * ways, and that was the source of some excruciatingly subtle bugs.
Tim Peters86b993b2003-04-05 17:35:54 +0000408 */
Neil Schemenauera765c122001-11-01 17:35:23 +0000409static int
410has_finalizer(PyObject *op)
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000411{
Tim Peters86b993b2003-04-05 17:35:54 +0000412 if (PyInstance_Check(op)) {
Tim Peters86b993b2003-04-05 17:35:54 +0000413 assert(delstr != NULL);
Tim Petersf6b80452003-04-07 19:21:15 +0000414 return _PyInstance_Lookup(op, delstr) != NULL;
Tim Peters86b993b2003-04-05 17:35:54 +0000415 }
Phillip J. Eby0d6615f2005-08-02 00:46:46 +0000416 else
Tim Peters86b993b2003-04-05 17:35:54 +0000417 return op->ob_type->tp_del != NULL;
Neil Schemenauera765c122001-11-01 17:35:23 +0000418}
419
Tim Petersead8b7a2004-10-30 23:09:22 +0000420/* Move the objects in unreachable with __del__ methods into `finalizers`.
421 * Objects moved into `finalizers` have gc_refs set to GC_REACHABLE; the
422 * objects remaining in unreachable are left at GC_TENTATIVELY_UNREACHABLE.
Jeremy Hyltonce136e92003-04-04 19:59:06 +0000423 */
Neil Schemenauera765c122001-11-01 17:35:23 +0000424static void
Tim Petersead8b7a2004-10-30 23:09:22 +0000425move_finalizers(PyGC_Head *unreachable, PyGC_Head *finalizers)
Neil Schemenauera765c122001-11-01 17:35:23 +0000426{
Tim Petersead8b7a2004-10-30 23:09:22 +0000427 PyGC_Head *gc;
428 PyGC_Head *next;
Tim Petersf6b80452003-04-07 19:21:15 +0000429
Tim Petersead8b7a2004-10-30 23:09:22 +0000430 /* March over unreachable. Move objects with finalizers into
431 * `finalizers`.
432 */
433 for (gc = unreachable->gc.gc_next; gc != unreachable; gc = next) {
Neil Schemenauer43411b52001-08-30 00:05:51 +0000434 PyObject *op = FROM_GC(gc);
Jeremy Hyltonce136e92003-04-04 19:59:06 +0000435
Tim Petersf6ae7a42003-04-05 18:40:50 +0000436 assert(IS_TENTATIVELY_UNREACHABLE(op));
Tim Petersead8b7a2004-10-30 23:09:22 +0000437 next = gc->gc.gc_next;
Tim Petersf6ae7a42003-04-05 18:40:50 +0000438
Tim Petersf6b80452003-04-07 19:21:15 +0000439 if (has_finalizer(op)) {
Tim Peterse2d59182004-11-01 01:39:08 +0000440 gc_list_move(gc, finalizers);
Tim Petersf6b80452003-04-07 19:21:15 +0000441 gc->gc.gc_refs = GC_REACHABLE;
Jeremy Hyltonce136e92003-04-04 19:59:06 +0000442 }
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000443 }
444}
445
Tim Peters19b74c72002-07-01 03:52:19 +0000446/* A traversal callback for move_finalizer_reachable. */
447static int
448visit_move(PyObject *op, PyGC_Head *tolist)
449{
450 if (PyObject_IS_GC(op)) {
Tim Petersea405632002-07-02 00:52:30 +0000451 if (IS_TENTATIVELY_UNREACHABLE(op)) {
Tim Peters19b74c72002-07-01 03:52:19 +0000452 PyGC_Head *gc = AS_GC(op);
Tim Peterse2d59182004-11-01 01:39:08 +0000453 gc_list_move(gc, tolist);
Tim Peters19b74c72002-07-01 03:52:19 +0000454 gc->gc.gc_refs = GC_REACHABLE;
455 }
456 }
457 return 0;
458}
459
460/* Move objects that are reachable from finalizers, from the unreachable set
Tim Petersf6b80452003-04-07 19:21:15 +0000461 * into finalizers set.
Tim Peters19b74c72002-07-01 03:52:19 +0000462 */
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000463static void
Tim Petersf6b80452003-04-07 19:21:15 +0000464move_finalizer_reachable(PyGC_Head *finalizers)
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000465{
466 traverseproc traverse;
Tim Peters9e4ca102001-10-11 18:31:31 +0000467 PyGC_Head *gc = finalizers->gc.gc_next;
Tim Petersbf384c22003-04-06 00:11:39 +0000468 for (; gc != finalizers; gc = gc->gc.gc_next) {
469 /* Note that the finalizers list may grow during this. */
Neil Schemenauer43411b52001-08-30 00:05:51 +0000470 traverse = FROM_GC(gc)->ob_type->tp_traverse;
Tim Peters88396172002-06-30 17:56:40 +0000471 (void) traverse(FROM_GC(gc),
Tim Petersbf384c22003-04-06 00:11:39 +0000472 (visitproc)visit_move,
Tim Petersf6b80452003-04-07 19:21:15 +0000473 (void *)finalizers);
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000474 }
475}
476
Tim Petersead8b7a2004-10-30 23:09:22 +0000477/* Clear all weakrefs to unreachable objects, and if such a weakref has a
478 * callback, invoke it if necessary. Note that it's possible for such
479 * weakrefs to be outside the unreachable set -- indeed, those are precisely
480 * the weakrefs whose callbacks must be invoked. See gc_weakref.txt for
481 * overview & some details. Some weakrefs with callbacks may be reclaimed
482 * directly by this routine; the number reclaimed is the return value. Other
483 * weakrefs with callbacks may be moved into the `old` generation. Objects
484 * moved into `old` have gc_refs set to GC_REACHABLE; the objects remaining in
485 * unreachable are left at GC_TENTATIVELY_UNREACHABLE. When this returns,
486 * no object in `unreachable` is weakly referenced anymore.
Tim Peters403a2032003-11-20 21:21:46 +0000487 */
488static int
Tim Petersead8b7a2004-10-30 23:09:22 +0000489handle_weakrefs(PyGC_Head *unreachable, PyGC_Head *old)
Tim Peters403a2032003-11-20 21:21:46 +0000490{
Tim Petersead8b7a2004-10-30 23:09:22 +0000491 PyGC_Head *gc;
492 PyObject *op; /* generally FROM_GC(gc) */
493 PyWeakReference *wr; /* generally a cast of op */
Tim Petersead8b7a2004-10-30 23:09:22 +0000494 PyGC_Head wrcb_to_call; /* weakrefs with callbacks to call */
Tim Petersead8b7a2004-10-30 23:09:22 +0000495 PyGC_Head *next;
Tim Peters403a2032003-11-20 21:21:46 +0000496 int num_freed = 0;
497
Tim Petersead8b7a2004-10-30 23:09:22 +0000498 gc_list_init(&wrcb_to_call);
Tim Peters403a2032003-11-20 21:21:46 +0000499
Tim Petersead8b7a2004-10-30 23:09:22 +0000500 /* Clear all weakrefs to the objects in unreachable. If such a weakref
501 * also has a callback, move it into `wrcb_to_call` if the callback
Tim Peterscc2a8662004-10-31 22:12:43 +0000502 * needs to be invoked. Note that we cannot invoke any callbacks until
503 * all weakrefs to unreachable objects are cleared, lest the callback
504 * resurrect an unreachable object via a still-active weakref. We
505 * make another pass over wrcb_to_call, invoking callbacks, after this
506 * pass completes.
Tim Petersead8b7a2004-10-30 23:09:22 +0000507 */
508 for (gc = unreachable->gc.gc_next; gc != unreachable; gc = next) {
509 PyWeakReference **wrlist;
510
511 op = FROM_GC(gc);
512 assert(IS_TENTATIVELY_UNREACHABLE(op));
513 next = gc->gc.gc_next;
514
515 if (! PyType_SUPPORTS_WEAKREFS(op->ob_type))
516 continue;
517
518 /* It supports weakrefs. Does it have any? */
519 wrlist = (PyWeakReference **)
520 PyObject_GET_WEAKREFS_LISTPTR(op);
521
522 /* `op` may have some weakrefs. March over the list, clear
523 * all the weakrefs, and move the weakrefs with callbacks
Tim Peterscc2a8662004-10-31 22:12:43 +0000524 * that must be called into wrcb_to_call.
Tim Petersead8b7a2004-10-30 23:09:22 +0000525 */
526 for (wr = *wrlist; wr != NULL; wr = *wrlist) {
527 PyGC_Head *wrasgc; /* AS_GC(wr) */
528
529 /* _PyWeakref_ClearRef clears the weakref but leaves
530 * the callback pointer intact. Obscure: it also
531 * changes *wrlist.
532 */
533 assert(wr->wr_object == op);
534 _PyWeakref_ClearRef(wr);
535 assert(wr->wr_object == Py_None);
536 if (wr->wr_callback == NULL)
537 continue; /* no callback */
538
539 /* Headache time. `op` is going away, and is weakly referenced by
540 * `wr`, which has a callback. Should the callback be invoked? If wr
541 * is also trash, no:
542 *
543 * 1. There's no need to call it. The object and the weakref are
544 * both going away, so it's legitimate to pretend the weakref is
545 * going away first. The user has to ensure a weakref outlives its
546 * referent if they want a guarantee that the wr callback will get
547 * invoked.
548 *
549 * 2. It may be catastrophic to call it. If the callback is also in
550 * cyclic trash (CT), then although the CT is unreachable from
551 * outside the current generation, CT may be reachable from the
552 * callback. Then the callback could resurrect insane objects.
553 *
554 * Since the callback is never needed and may be unsafe in this case,
Tim Peterscc2a8662004-10-31 22:12:43 +0000555 * wr is simply left in the unreachable set. Note that because we
556 * already called _PyWeakref_ClearRef(wr), its callback will never
557 * trigger.
Tim Petersead8b7a2004-10-30 23:09:22 +0000558 *
559 * OTOH, if wr isn't part of CT, we should invoke the callback: the
560 * weakref outlived the trash. Note that since wr isn't CT in this
561 * case, its callback can't be CT either -- wr acted as an external
562 * root to this generation, and therefore its callback did too. So
563 * nothing in CT is reachable from the callback either, so it's hard
564 * to imagine how calling it later could create a problem for us. wr
565 * is moved to wrcb_to_call in this case.
Tim Petersead8b7a2004-10-30 23:09:22 +0000566 */
Tim Peterscc2a8662004-10-31 22:12:43 +0000567 if (IS_TENTATIVELY_UNREACHABLE(wr))
568 continue;
569 assert(IS_REACHABLE(wr));
570
Tim Petersead8b7a2004-10-30 23:09:22 +0000571 /* Create a new reference so that wr can't go away
572 * before we can process it again.
573 */
574 Py_INCREF(wr);
575
Tim Peterscc2a8662004-10-31 22:12:43 +0000576 /* Move wr to wrcb_to_call, for the next pass. */
Tim Petersead8b7a2004-10-30 23:09:22 +0000577 wrasgc = AS_GC(wr);
Tim Peterscc2a8662004-10-31 22:12:43 +0000578 assert(wrasgc != next); /* wrasgc is reachable, but
579 next isn't, so they can't
580 be the same */
Tim Peterse2d59182004-11-01 01:39:08 +0000581 gc_list_move(wrasgc, &wrcb_to_call);
Tim Petersead8b7a2004-10-30 23:09:22 +0000582 }
583 }
584
Tim Peterscc2a8662004-10-31 22:12:43 +0000585 /* Invoke the callbacks we decided to honor. It's safe to invoke them
586 * because they can't reference unreachable objects.
Tim Petersead8b7a2004-10-30 23:09:22 +0000587 */
588 while (! gc_list_is_empty(&wrcb_to_call)) {
589 PyObject *temp;
590 PyObject *callback;
591
592 gc = wrcb_to_call.gc.gc_next;
593 op = FROM_GC(gc);
594 assert(IS_REACHABLE(op));
595 assert(PyWeakref_Check(op));
596 wr = (PyWeakReference *)op;
597 callback = wr->wr_callback;
598 assert(callback != NULL);
599
600 /* copy-paste of weakrefobject.c's handle_callback() */
601 temp = PyObject_CallFunction(callback, "O", wr);
602 if (temp == NULL)
603 PyErr_WriteUnraisable(callback);
604 else
605 Py_DECREF(temp);
606
607 /* Give up the reference we created in the first pass. When
608 * op's refcount hits 0 (which it may or may not do right now),
Tim Peterscc2a8662004-10-31 22:12:43 +0000609 * op's tp_dealloc will decref op->wr_callback too. Note
610 * that the refcount probably will hit 0 now, and because this
611 * weakref was reachable to begin with, gc didn't already
612 * add it to its count of freed objects. Example: a reachable
613 * weak value dict maps some key to this reachable weakref.
614 * The callback removes this key->weakref mapping from the
615 * dict, leaving no other references to the weakref (excepting
616 * ours).
Tim Petersead8b7a2004-10-30 23:09:22 +0000617 */
618 Py_DECREF(op);
619 if (wrcb_to_call.gc.gc_next == gc) {
620 /* object is still alive -- move it */
Tim Peterse2d59182004-11-01 01:39:08 +0000621 gc_list_move(gc, old);
Tim Petersead8b7a2004-10-30 23:09:22 +0000622 }
623 else
624 ++num_freed;
625 }
626
Tim Peters403a2032003-11-20 21:21:46 +0000627 return num_freed;
628}
629
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000630static void
Jeremy Hylton06257772000-08-31 15:10:24 +0000631debug_instance(char *msg, PyInstanceObject *inst)
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000632{
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000633 char *cname;
Neil Schemenauera765c122001-11-01 17:35:23 +0000634 /* simple version of instance_repr */
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000635 PyObject *classname = inst->in_class->cl_name;
636 if (classname != NULL && PyString_Check(classname))
637 cname = PyString_AsString(classname);
638 else
639 cname = "?";
Jeremy Hylton06257772000-08-31 15:10:24 +0000640 PySys_WriteStderr("gc: %.100s <%.100s instance at %p>\n",
641 msg, cname, inst);
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000642}
643
644static void
Jeremy Hylton06257772000-08-31 15:10:24 +0000645debug_cycle(char *msg, PyObject *op)
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000646{
647 if ((debug & DEBUG_INSTANCES) && PyInstance_Check(op)) {
Jeremy Hylton06257772000-08-31 15:10:24 +0000648 debug_instance(msg, (PyInstanceObject *)op);
Neil Schemenauer544de1e2000-09-22 15:22:38 +0000649 }
650 else if (debug & DEBUG_OBJECTS) {
Jeremy Hylton06257772000-08-31 15:10:24 +0000651 PySys_WriteStderr("gc: %.100s <%.100s %p>\n",
652 msg, op->ob_type->tp_name, op);
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000653 }
654}
655
Tim Petersbf384c22003-04-06 00:11:39 +0000656/* Handle uncollectable garbage (cycles with finalizers, and stuff reachable
657 * only from such cycles).
Tim Petersf6b80452003-04-07 19:21:15 +0000658 * If DEBUG_SAVEALL, all objects in finalizers are appended to the module
659 * garbage list (a Python list), else only the objects in finalizers with
660 * __del__ methods are appended to garbage. All objects in finalizers are
661 * merged into the old list regardless.
Tim Peters259272b2003-04-06 19:41:39 +0000662 * Returns 0 if all OK, <0 on error (out of memory to grow the garbage list).
663 * The finalizers list is made empty on a successful return.
Tim Petersbf384c22003-04-06 00:11:39 +0000664 */
Tim Peters259272b2003-04-06 19:41:39 +0000665static int
Tim Petersf6b80452003-04-07 19:21:15 +0000666handle_finalizers(PyGC_Head *finalizers, PyGC_Head *old)
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000667{
Tim Petersf6b80452003-04-07 19:21:15 +0000668 PyGC_Head *gc = finalizers->gc.gc_next;
669
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000670 if (garbage == NULL) {
671 garbage = PyList_New(0);
Tim Petersbf384c22003-04-06 00:11:39 +0000672 if (garbage == NULL)
673 Py_FatalError("gc couldn't create gc.garbage list");
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000674 }
Tim Petersf6b80452003-04-07 19:21:15 +0000675 for (; gc != finalizers; gc = gc->gc.gc_next) {
676 PyObject *op = FROM_GC(gc);
677
678 if ((debug & DEBUG_SAVEALL) || has_finalizer(op)) {
679 if (PyList_Append(garbage, op) < 0)
680 return -1;
681 }
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000682 }
Tim Petersf6b80452003-04-07 19:21:15 +0000683
Tim Peters259272b2003-04-06 19:41:39 +0000684 gc_list_merge(finalizers, old);
685 return 0;
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000686}
687
Neil Schemenauer544de1e2000-09-22 15:22:38 +0000688/* Break reference cycles by clearing the containers involved. This is
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000689 * tricky business as the lists can be changing and we don't know which
Tim Peters19b74c72002-07-01 03:52:19 +0000690 * objects may be freed. It is possible I screwed something up here.
691 */
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000692static void
Jeremy Hyltonce136e92003-04-04 19:59:06 +0000693delete_garbage(PyGC_Head *collectable, PyGC_Head *old)
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000694{
695 inquiry clear;
696
Jeremy Hyltonce136e92003-04-04 19:59:06 +0000697 while (!gc_list_is_empty(collectable)) {
698 PyGC_Head *gc = collectable->gc.gc_next;
Neil Schemenauer43411b52001-08-30 00:05:51 +0000699 PyObject *op = FROM_GC(gc);
Tim Peters88396172002-06-30 17:56:40 +0000700
Tim Peters19b74c72002-07-01 03:52:19 +0000701 assert(IS_TENTATIVELY_UNREACHABLE(op));
Neil Schemenauer544de1e2000-09-22 15:22:38 +0000702 if (debug & DEBUG_SAVEALL) {
703 PyList_Append(garbage, op);
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000704 }
Neil Schemenauer544de1e2000-09-22 15:22:38 +0000705 else {
706 if ((clear = op->ob_type->tp_clear) != NULL) {
707 Py_INCREF(op);
Jeremy Hylton8a135182002-06-06 23:23:55 +0000708 clear(op);
Neil Schemenauer544de1e2000-09-22 15:22:38 +0000709 Py_DECREF(op);
710 }
711 }
Jeremy Hyltonce136e92003-04-04 19:59:06 +0000712 if (collectable->gc.gc_next == gc) {
Neil Schemenauer544de1e2000-09-22 15:22:38 +0000713 /* object is still alive, move it, it may die later */
Tim Peterse2d59182004-11-01 01:39:08 +0000714 gc_list_move(gc, old);
Tim Peters19b74c72002-07-01 03:52:19 +0000715 gc->gc.gc_refs = GC_REACHABLE;
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000716 }
717 }
718}
719
720/* This is the main function. Read this to understand how the
721 * collection process works. */
Neal Norwitz7b216c52006-03-04 20:01:53 +0000722static Py_ssize_t
Neil Schemenauer2880ae52002-05-04 05:35:20 +0000723collect(int generation)
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000724{
Neil Schemenauer2880ae52002-05-04 05:35:20 +0000725 int i;
Neal Norwitz7b216c52006-03-04 20:01:53 +0000726 Py_ssize_t m = 0; /* # objects collected */
727 Py_ssize_t n = 0; /* # unreachable objects that couldn't be collected */
Neil Schemenauer2880ae52002-05-04 05:35:20 +0000728 PyGC_Head *young; /* the generation we are examining */
729 PyGC_Head *old; /* next older generation */
Tim Peters403a2032003-11-20 21:21:46 +0000730 PyGC_Head unreachable; /* non-problematic unreachable trash */
731 PyGC_Head finalizers; /* objects with, & reachable from, __del__ */
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000732 PyGC_Head *gc;
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000733
Tim Peters93ad66d2003-04-05 17:15:44 +0000734 if (delstr == NULL) {
735 delstr = PyString_InternFromString("__del__");
736 if (delstr == NULL)
737 Py_FatalError("gc couldn't allocate \"__del__\"");
738 }
739
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000740 if (debug & DEBUG_STATS) {
Neil Schemenauer2880ae52002-05-04 05:35:20 +0000741 PySys_WriteStderr("gc: collecting generation %d...\n",
742 generation);
743 PySys_WriteStderr("gc: objects in each generation:");
744 for (i = 0; i < NUM_GENERATIONS; i++) {
745 PySys_WriteStderr(" %ld", gc_list_size(GEN_HEAD(i)));
746 }
747 PySys_WriteStderr("\n");
748 }
749
750 /* update collection and allocation counters */
751 if (generation+1 < NUM_GENERATIONS)
752 generations[generation+1].count += 1;
753 for (i = 0; i <= generation; i++)
Neil Schemenauerc9051642002-06-28 19:16:04 +0000754 generations[i].count = 0;
Neil Schemenauer2880ae52002-05-04 05:35:20 +0000755
756 /* merge younger generations with one we are currently collecting */
757 for (i = 0; i < generation; i++) {
758 gc_list_merge(GEN_HEAD(i), GEN_HEAD(generation));
759 }
760
761 /* handy references */
762 young = GEN_HEAD(generation);
Tim Peters19b74c72002-07-01 03:52:19 +0000763 if (generation < NUM_GENERATIONS-1)
Neil Schemenauer2880ae52002-05-04 05:35:20 +0000764 old = GEN_HEAD(generation+1);
Tim Peters19b74c72002-07-01 03:52:19 +0000765 else
766 old = young;
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000767
768 /* Using ob_refcnt and gc_refs, calculate which objects in the
Tim Petersead8b7a2004-10-30 23:09:22 +0000769 * container set are reachable from outside the set (i.e., have a
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000770 * refcount greater than 0 when all the references within the
Tim Petersead8b7a2004-10-30 23:09:22 +0000771 * set are taken into account).
Tim Peters19b74c72002-07-01 03:52:19 +0000772 */
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000773 update_refs(young);
774 subtract_refs(young);
775
Tim Peters19b74c72002-07-01 03:52:19 +0000776 /* Leave everything reachable from outside young in young, and move
777 * everything else (in young) to unreachable.
778 * NOTE: This used to move the reachable objects into a reachable
779 * set instead. But most things usually turn out to be reachable,
780 * so it's more efficient to move the unreachable things.
781 */
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000782 gc_list_init(&unreachable);
Tim Peters19b74c72002-07-01 03:52:19 +0000783 move_unreachable(young, &unreachable);
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000784
Tim Peters19b74c72002-07-01 03:52:19 +0000785 /* Move reachable objects to next generation. */
786 if (young != old)
787 gc_list_merge(young, old);
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000788
Tim Peters19b74c72002-07-01 03:52:19 +0000789 /* All objects in unreachable are trash, but objects reachable from
790 * finalizers can't safely be deleted. Python programmers should take
791 * care not to create such things. For Python, finalizers means
Tim Peters403a2032003-11-20 21:21:46 +0000792 * instance objects with __del__ methods. Weakrefs with callbacks
Tim Petersead8b7a2004-10-30 23:09:22 +0000793 * can also call arbitrary Python code but they will be dealt with by
794 * handle_weakrefs().
Tim Petersf6b80452003-04-07 19:21:15 +0000795 */
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000796 gc_list_init(&finalizers);
Tim Petersead8b7a2004-10-30 23:09:22 +0000797 move_finalizers(&unreachable, &finalizers);
Tim Petersbf384c22003-04-06 00:11:39 +0000798 /* finalizers contains the unreachable objects with a finalizer;
Tim Peters403a2032003-11-20 21:21:46 +0000799 * unreachable objects reachable *from* those are also uncollectable,
800 * and we move those into the finalizers list too.
Tim Petersbf384c22003-04-06 00:11:39 +0000801 */
Tim Petersf6b80452003-04-07 19:21:15 +0000802 move_finalizer_reachable(&finalizers);
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000803
804 /* Collect statistics on collectable objects found and print
Tim Peters403a2032003-11-20 21:21:46 +0000805 * debugging information.
806 */
Tim Petersf6b80452003-04-07 19:21:15 +0000807 for (gc = unreachable.gc.gc_next; gc != &unreachable;
Tim Peters9e4ca102001-10-11 18:31:31 +0000808 gc = gc->gc.gc_next) {
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000809 m++;
Jeremy Hylton06257772000-08-31 15:10:24 +0000810 if (debug & DEBUG_COLLECTABLE) {
Neil Schemenauer43411b52001-08-30 00:05:51 +0000811 debug_cycle("collectable", FROM_GC(gc));
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000812 }
813 }
Tim Petersead8b7a2004-10-30 23:09:22 +0000814
815 /* Clear weakrefs and invoke callbacks as necessary. */
816 m += handle_weakrefs(&unreachable, old);
817
Tim Petersfb2ab4d2003-04-07 22:41:24 +0000818 /* Call tp_clear on objects in the unreachable set. This will cause
819 * the reference cycles to be broken. It may also cause some objects
820 * in finalizers to be freed.
821 */
Tim Petersf6b80452003-04-07 19:21:15 +0000822 delete_garbage(&unreachable, old);
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000823
824 /* Collect statistics on uncollectable objects found and print
825 * debugging information. */
Tim Peters50c61d52003-04-06 01:50:50 +0000826 for (gc = finalizers.gc.gc_next;
Tim Petersbf384c22003-04-06 00:11:39 +0000827 gc != &finalizers;
828 gc = gc->gc.gc_next) {
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000829 n++;
Tim Petersbf384c22003-04-06 00:11:39 +0000830 if (debug & DEBUG_UNCOLLECTABLE)
Neil Schemenauer43411b52001-08-30 00:05:51 +0000831 debug_cycle("uncollectable", FROM_GC(gc));
Tim Petersbf384c22003-04-06 00:11:39 +0000832 }
Jeremy Hylton06257772000-08-31 15:10:24 +0000833 if (debug & DEBUG_STATS) {
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000834 if (m == 0 && n == 0) {
Jeremy Hylton06257772000-08-31 15:10:24 +0000835 PySys_WriteStderr("gc: done.\n");
Neil Schemenauer544de1e2000-09-22 15:22:38 +0000836 }
837 else {
Jeremy Hylton06257772000-08-31 15:10:24 +0000838 PySys_WriteStderr(
839 "gc: done, %ld unreachable, %ld uncollectable.\n",
840 n+m, n);
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000841 }
842 }
843
844 /* Append instances in the uncollectable set to a Python
845 * reachable list of garbage. The programmer has to deal with
Tim Petersbf384c22003-04-06 00:11:39 +0000846 * this if they insist on creating this type of structure.
847 */
Tim Petersf6b80452003-04-07 19:21:15 +0000848 (void)handle_finalizers(&finalizers, old);
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000849
Jeremy Hyltonb709df32000-09-01 02:47:25 +0000850 if (PyErr_Occurred()) {
Tim Petersf6b80452003-04-07 19:21:15 +0000851 if (gc_str == NULL)
Tim Petersfb2ab4d2003-04-07 22:41:24 +0000852 gc_str = PyString_FromString("garbage collection");
Jeremy Hyltonb709df32000-09-01 02:47:25 +0000853 PyErr_WriteUnraisable(gc_str);
854 Py_FatalError("unexpected exception during garbage collection");
855 }
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000856 return n+m;
857}
858
Neal Norwitz7b216c52006-03-04 20:01:53 +0000859static Py_ssize_t
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000860collect_generations(void)
861{
Neil Schemenauer2880ae52002-05-04 05:35:20 +0000862 int i;
Neal Norwitz7b216c52006-03-04 20:01:53 +0000863 Py_ssize_t n = 0;
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000864
Neil Schemenauer2880ae52002-05-04 05:35:20 +0000865 /* Find the oldest generation (higest numbered) where the count
866 * exceeds the threshold. Objects in the that generation and
867 * generations younger than it will be collected. */
868 for (i = NUM_GENERATIONS-1; i >= 0; i--) {
869 if (generations[i].count > generations[i].threshold) {
870 n = collect(i);
871 break;
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000872 }
873 }
874 return n;
875}
876
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +0000877PyDoc_STRVAR(gc_enable__doc__,
Vladimir Marangozovf9d20c32000-08-06 22:45:31 +0000878"enable() -> None\n"
879"\n"
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +0000880"Enable automatic garbage collection.\n");
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000881
Vladimir Marangozovf9d20c32000-08-06 22:45:31 +0000882static PyObject *
Tim Peters50c61d52003-04-06 01:50:50 +0000883gc_enable(PyObject *self, PyObject *noargs)
Vladimir Marangozovf9d20c32000-08-06 22:45:31 +0000884{
Vladimir Marangozovf9d20c32000-08-06 22:45:31 +0000885 enabled = 1;
Vladimir Marangozovf9d20c32000-08-06 22:45:31 +0000886 Py_INCREF(Py_None);
887 return Py_None;
888}
889
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +0000890PyDoc_STRVAR(gc_disable__doc__,
Vladimir Marangozovf9d20c32000-08-06 22:45:31 +0000891"disable() -> None\n"
892"\n"
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +0000893"Disable automatic garbage collection.\n");
Vladimir Marangozovf9d20c32000-08-06 22:45:31 +0000894
895static PyObject *
Tim Peters50c61d52003-04-06 01:50:50 +0000896gc_disable(PyObject *self, PyObject *noargs)
Vladimir Marangozovf9d20c32000-08-06 22:45:31 +0000897{
Vladimir Marangozovf9d20c32000-08-06 22:45:31 +0000898 enabled = 0;
Vladimir Marangozovf9d20c32000-08-06 22:45:31 +0000899 Py_INCREF(Py_None);
900 return Py_None;
901}
902
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +0000903PyDoc_STRVAR(gc_isenabled__doc__,
Vladimir Marangozovf9d20c32000-08-06 22:45:31 +0000904"isenabled() -> status\n"
905"\n"
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +0000906"Returns true if automatic garbage collection is enabled.\n");
Vladimir Marangozovf9d20c32000-08-06 22:45:31 +0000907
908static PyObject *
Tim Peters50c61d52003-04-06 01:50:50 +0000909gc_isenabled(PyObject *self, PyObject *noargs)
Vladimir Marangozovf9d20c32000-08-06 22:45:31 +0000910{
Raymond Hettinger674d56b2004-01-04 04:00:13 +0000911 return PyBool_FromLong((long)enabled);
Vladimir Marangozovf9d20c32000-08-06 22:45:31 +0000912}
913
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +0000914PyDoc_STRVAR(gc_collect__doc__,
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000915"collect() -> n\n"
916"\n"
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +0000917"Run a full collection. The number of unreachable objects is returned.\n");
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000918
919static PyObject *
Tim Peters50c61d52003-04-06 01:50:50 +0000920gc_collect(PyObject *self, PyObject *noargs)
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000921{
Neal Norwitz7b216c52006-03-04 20:01:53 +0000922 Py_ssize_t n;
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000923
Tim Peters50c61d52003-04-06 01:50:50 +0000924 if (collecting)
Neil Schemenauere8c40cb2001-10-31 23:09:35 +0000925 n = 0; /* already collecting, don't do anything */
Neil Schemenauere8c40cb2001-10-31 23:09:35 +0000926 else {
927 collecting = 1;
Neil Schemenauer2880ae52002-05-04 05:35:20 +0000928 n = collect(NUM_GENERATIONS - 1);
Neil Schemenauere8c40cb2001-10-31 23:09:35 +0000929 collecting = 0;
930 }
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000931
Neal Norwitz7b216c52006-03-04 20:01:53 +0000932 return PyInt_FromSsize_t(n);
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000933}
934
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +0000935PyDoc_STRVAR(gc_set_debug__doc__,
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000936"set_debug(flags) -> None\n"
937"\n"
938"Set the garbage collection debugging flags. Debugging information is\n"
939"written to sys.stderr.\n"
940"\n"
941"flags is an integer and can have the following bits turned on:\n"
942"\n"
943" DEBUG_STATS - Print statistics during collection.\n"
944" DEBUG_COLLECTABLE - Print collectable objects found.\n"
945" DEBUG_UNCOLLECTABLE - Print unreachable but uncollectable objects found.\n"
946" DEBUG_INSTANCES - Print instance objects.\n"
947" DEBUG_OBJECTS - Print objects other than instances.\n"
Neil Schemenauer544de1e2000-09-22 15:22:38 +0000948" DEBUG_SAVEALL - Save objects to gc.garbage rather than freeing them.\n"
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +0000949" DEBUG_LEAK - Debug leaking programs (everything but STATS).\n");
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000950
951static PyObject *
Vladimir Marangozovf9d20c32000-08-06 22:45:31 +0000952gc_set_debug(PyObject *self, PyObject *args)
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000953{
Neil Schemenauer7760cff2000-09-22 22:35:36 +0000954 if (!PyArg_ParseTuple(args, "i:set_debug", &debug))
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000955 return NULL;
956
957 Py_INCREF(Py_None);
958 return Py_None;
959}
960
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +0000961PyDoc_STRVAR(gc_get_debug__doc__,
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000962"get_debug() -> flags\n"
963"\n"
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +0000964"Get the garbage collection debugging flags.\n");
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000965
966static PyObject *
Tim Peters50c61d52003-04-06 01:50:50 +0000967gc_get_debug(PyObject *self, PyObject *noargs)
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000968{
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000969 return Py_BuildValue("i", debug);
970}
971
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +0000972PyDoc_STRVAR(gc_set_thresh__doc__,
Neal Norwitz2a47c0f2002-01-29 00:53:41 +0000973"set_threshold(threshold0, [threshold1, threshold2]) -> None\n"
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000974"\n"
975"Sets the collection thresholds. Setting threshold0 to zero disables\n"
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +0000976"collection.\n");
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000977
978static PyObject *
Vladimir Marangozovf9d20c32000-08-06 22:45:31 +0000979gc_set_thresh(PyObject *self, PyObject *args)
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000980{
Neil Schemenauer2880ae52002-05-04 05:35:20 +0000981 int i;
982 if (!PyArg_ParseTuple(args, "i|ii:set_threshold",
983 &generations[0].threshold,
984 &generations[1].threshold,
985 &generations[2].threshold))
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000986 return NULL;
Neil Schemenauer2880ae52002-05-04 05:35:20 +0000987 for (i = 2; i < NUM_GENERATIONS; i++) {
988 /* generations higher than 2 get the same threshold */
989 generations[i].threshold = generations[2].threshold;
990 }
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000991
992 Py_INCREF(Py_None);
993 return Py_None;
994}
995
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +0000996PyDoc_STRVAR(gc_get_thresh__doc__,
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000997"get_threshold() -> (threshold0, threshold1, threshold2)\n"
998"\n"
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +0000999"Return the current collection thresholds\n");
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +00001000
1001static PyObject *
Tim Peters50c61d52003-04-06 01:50:50 +00001002gc_get_thresh(PyObject *self, PyObject *noargs)
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +00001003{
Neil Schemenauer2880ae52002-05-04 05:35:20 +00001004 return Py_BuildValue("(iii)",
1005 generations[0].threshold,
1006 generations[1].threshold,
1007 generations[2].threshold);
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +00001008}
1009
Neil Schemenauer48c70342001-08-09 15:38:31 +00001010static int
Martin v. Löwis560da622001-11-24 09:24:51 +00001011referrersvisit(PyObject* obj, PyObject *objs)
Neil Schemenauer48c70342001-08-09 15:38:31 +00001012{
Martin v. Löwisc8fe77b2001-11-29 18:08:31 +00001013 int i;
1014 for (i = 0; i < PyTuple_GET_SIZE(objs); i++)
1015 if (PyTuple_GET_ITEM(objs, i) == obj)
1016 return 1;
Neil Schemenauer48c70342001-08-09 15:38:31 +00001017 return 0;
1018}
1019
Neil Schemenauer17e7be62001-08-10 14:46:47 +00001020static int
Martin v. Löwis560da622001-11-24 09:24:51 +00001021gc_referrers_for(PyObject *objs, PyGC_Head *list, PyObject *resultlist)
Neil Schemenauer48c70342001-08-09 15:38:31 +00001022{
1023 PyGC_Head *gc;
1024 PyObject *obj;
1025 traverseproc traverse;
Tim Peters9e4ca102001-10-11 18:31:31 +00001026 for (gc = list->gc.gc_next; gc != list; gc = gc->gc.gc_next) {
Neil Schemenauer43411b52001-08-30 00:05:51 +00001027 obj = FROM_GC(gc);
Neil Schemenauer48c70342001-08-09 15:38:31 +00001028 traverse = obj->ob_type->tp_traverse;
1029 if (obj == objs || obj == resultlist)
1030 continue;
Martin v. Löwis560da622001-11-24 09:24:51 +00001031 if (traverse(obj, (visitproc)referrersvisit, objs)) {
Neil Schemenauer17e7be62001-08-10 14:46:47 +00001032 if (PyList_Append(resultlist, obj) < 0)
1033 return 0; /* error */
Neil Schemenauer48c70342001-08-09 15:38:31 +00001034 }
1035 }
Neil Schemenauer17e7be62001-08-10 14:46:47 +00001036 return 1; /* no error */
Neil Schemenauer48c70342001-08-09 15:38:31 +00001037}
1038
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00001039PyDoc_STRVAR(gc_get_referrers__doc__,
Martin v. Löwis560da622001-11-24 09:24:51 +00001040"get_referrers(*objs) -> list\n\
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00001041Return the list of objects that directly refer to any of objs.");
Neil Schemenauer48c70342001-08-09 15:38:31 +00001042
Neil Schemenauer17e7be62001-08-10 14:46:47 +00001043static PyObject *
Martin v. Löwis560da622001-11-24 09:24:51 +00001044gc_get_referrers(PyObject *self, PyObject *args)
Neil Schemenauer48c70342001-08-09 15:38:31 +00001045{
Neil Schemenauer2880ae52002-05-04 05:35:20 +00001046 int i;
Neil Schemenauer48c70342001-08-09 15:38:31 +00001047 PyObject *result = PyList_New(0);
Neil Schemenauer2880ae52002-05-04 05:35:20 +00001048 for (i = 0; i < NUM_GENERATIONS; i++) {
1049 if (!(gc_referrers_for(args, GEN_HEAD(i), result))) {
1050 Py_DECREF(result);
1051 return NULL;
1052 }
Neil Schemenauer17e7be62001-08-10 14:46:47 +00001053 }
Neil Schemenauer48c70342001-08-09 15:38:31 +00001054 return result;
1055}
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +00001056
Tim Peters0f81ab62003-04-08 16:39:48 +00001057/* Append obj to list; return true if error (out of memory), false if OK. */
Jeremy Hylton5bd378b2003-04-03 16:28:38 +00001058static int
Tim Peters730f5532003-04-08 17:17:17 +00001059referentsvisit(PyObject *obj, PyObject *list)
Jeremy Hylton5bd378b2003-04-03 16:28:38 +00001060{
Tim Peters0f81ab62003-04-08 16:39:48 +00001061 return PyList_Append(list, obj) < 0;
Jeremy Hylton5bd378b2003-04-03 16:28:38 +00001062}
1063
Tim Peters730f5532003-04-08 17:17:17 +00001064PyDoc_STRVAR(gc_get_referents__doc__,
1065"get_referents(*objs) -> list\n\
Jeremy Hylton059b0942003-04-03 16:29:13 +00001066Return the list of objects that are directly referred to by objs.");
Jeremy Hylton5bd378b2003-04-03 16:28:38 +00001067
1068static PyObject *
Tim Peters730f5532003-04-08 17:17:17 +00001069gc_get_referents(PyObject *self, PyObject *args)
Jeremy Hylton5bd378b2003-04-03 16:28:38 +00001070{
1071 int i;
1072 PyObject *result = PyList_New(0);
Tim Peters0f81ab62003-04-08 16:39:48 +00001073
1074 if (result == NULL)
1075 return NULL;
1076
Jeremy Hylton5bd378b2003-04-03 16:28:38 +00001077 for (i = 0; i < PyTuple_GET_SIZE(args); i++) {
Tim Peters0f81ab62003-04-08 16:39:48 +00001078 traverseproc traverse;
Tim Peters93ad66d2003-04-05 17:15:44 +00001079 PyObject *obj = PyTuple_GET_ITEM(args, i);
Tim Peters0f81ab62003-04-08 16:39:48 +00001080
1081 if (! PyObject_IS_GC(obj))
Jeremy Hylton5bd378b2003-04-03 16:28:38 +00001082 continue;
Tim Peters0f81ab62003-04-08 16:39:48 +00001083 traverse = obj->ob_type->tp_traverse;
1084 if (! traverse)
1085 continue;
Tim Peters730f5532003-04-08 17:17:17 +00001086 if (traverse(obj, (visitproc)referentsvisit, result)) {
Tim Peters0f81ab62003-04-08 16:39:48 +00001087 Py_DECREF(result);
Jeremy Hylton5bd378b2003-04-03 16:28:38 +00001088 return NULL;
Tim Peters0f81ab62003-04-08 16:39:48 +00001089 }
Jeremy Hylton5bd378b2003-04-03 16:28:38 +00001090 }
1091 return result;
1092}
1093
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00001094PyDoc_STRVAR(gc_get_objects__doc__,
Neil Schemenauerc7c8d8e2001-08-09 15:58:59 +00001095"get_objects() -> [...]\n"
1096"\n"
1097"Return a list of objects tracked by the collector (excluding the list\n"
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00001098"returned).\n");
Neil Schemenauerc7c8d8e2001-08-09 15:58:59 +00001099
Neil Schemenauerc7c8d8e2001-08-09 15:58:59 +00001100static PyObject *
Tim Peters50c61d52003-04-06 01:50:50 +00001101gc_get_objects(PyObject *self, PyObject *noargs)
Neil Schemenauerc7c8d8e2001-08-09 15:58:59 +00001102{
Neil Schemenauer2880ae52002-05-04 05:35:20 +00001103 int i;
Neil Schemenauerc7c8d8e2001-08-09 15:58:59 +00001104 PyObject* result;
1105
Neil Schemenauerc7c8d8e2001-08-09 15:58:59 +00001106 result = PyList_New(0);
Tim Peters50c61d52003-04-06 01:50:50 +00001107 if (result == NULL)
Martin v. Löwisf8a6f242001-12-02 18:31:02 +00001108 return NULL;
Neil Schemenauer2880ae52002-05-04 05:35:20 +00001109 for (i = 0; i < NUM_GENERATIONS; i++) {
1110 if (append_objects(result, GEN_HEAD(i))) {
1111 Py_DECREF(result);
1112 return NULL;
1113 }
Martin v. Löwis155aad12001-12-02 12:21:34 +00001114 }
Neil Schemenauerc7c8d8e2001-08-09 15:58:59 +00001115 return result;
1116}
1117
1118
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00001119PyDoc_STRVAR(gc__doc__,
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +00001120"This module provides access to the garbage collector for reference cycles.\n"
1121"\n"
Vladimir Marangozovf9d20c32000-08-06 22:45:31 +00001122"enable() -- Enable automatic garbage collection.\n"
1123"disable() -- Disable automatic garbage collection.\n"
1124"isenabled() -- Returns true if automatic collection is enabled.\n"
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +00001125"collect() -- Do a full collection right now.\n"
1126"set_debug() -- Set debugging flags.\n"
1127"get_debug() -- Get debugging flags.\n"
1128"set_threshold() -- Set the collection thresholds.\n"
1129"get_threshold() -- Return the current the collection thresholds.\n"
Neil Schemenauerc7c8d8e2001-08-09 15:58:59 +00001130"get_objects() -- Return a list of all objects tracked by the collector.\n"
Jeremy Hylton5bd378b2003-04-03 16:28:38 +00001131"get_referrers() -- Return the list of objects that refer to an object.\n"
Tim Peters730f5532003-04-08 17:17:17 +00001132"get_referents() -- Return the list of objects that an object refers to.\n");
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +00001133
1134static PyMethodDef GcMethods[] = {
Tim Peters50c61d52003-04-06 01:50:50 +00001135 {"enable", gc_enable, METH_NOARGS, gc_enable__doc__},
1136 {"disable", gc_disable, METH_NOARGS, gc_disable__doc__},
1137 {"isenabled", gc_isenabled, METH_NOARGS, gc_isenabled__doc__},
Vladimir Marangozovf9d20c32000-08-06 22:45:31 +00001138 {"set_debug", gc_set_debug, METH_VARARGS, gc_set_debug__doc__},
Tim Peters50c61d52003-04-06 01:50:50 +00001139 {"get_debug", gc_get_debug, METH_NOARGS, gc_get_debug__doc__},
Vladimir Marangozovf9d20c32000-08-06 22:45:31 +00001140 {"set_threshold", gc_set_thresh, METH_VARARGS, gc_set_thresh__doc__},
Tim Peters50c61d52003-04-06 01:50:50 +00001141 {"get_threshold", gc_get_thresh, METH_NOARGS, gc_get_thresh__doc__},
1142 {"collect", gc_collect, METH_NOARGS, gc_collect__doc__},
1143 {"get_objects", gc_get_objects,METH_NOARGS, gc_get_objects__doc__},
Martin v. Löwis560da622001-11-24 09:24:51 +00001144 {"get_referrers", gc_get_referrers, METH_VARARGS,
1145 gc_get_referrers__doc__},
Tim Peters730f5532003-04-08 17:17:17 +00001146 {"get_referents", gc_get_referents, METH_VARARGS,
1147 gc_get_referents__doc__},
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +00001148 {NULL, NULL} /* Sentinel */
1149};
1150
Jason Tishler6bc06ec2003-09-04 11:59:50 +00001151PyMODINIT_FUNC
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +00001152initgc(void)
1153{
1154 PyObject *m;
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +00001155
1156 m = Py_InitModule4("gc",
1157 GcMethods,
1158 gc__doc__,
1159 NULL,
1160 PYTHON_API_VERSION);
Neal Norwitz1ac754f2006-01-19 06:09:39 +00001161 if (m == NULL)
1162 return;
Tim Peters11558872003-04-06 23:30:52 +00001163
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +00001164 if (garbage == NULL) {
1165 garbage = PyList_New(0);
Tim Peters11558872003-04-06 23:30:52 +00001166 if (garbage == NULL)
1167 return;
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +00001168 }
Neil Schemenauer3b1cbf92005-06-18 17:37:06 +00001169 Py_INCREF(garbage);
Tim Peters11558872003-04-06 23:30:52 +00001170 if (PyModule_AddObject(m, "garbage", garbage) < 0)
1171 return;
1172#define ADD_INT(NAME) if (PyModule_AddIntConstant(m, #NAME, NAME) < 0) return
1173 ADD_INT(DEBUG_STATS);
1174 ADD_INT(DEBUG_COLLECTABLE);
1175 ADD_INT(DEBUG_UNCOLLECTABLE);
1176 ADD_INT(DEBUG_INSTANCES);
1177 ADD_INT(DEBUG_OBJECTS);
1178 ADD_INT(DEBUG_SAVEALL);
1179 ADD_INT(DEBUG_LEAK);
1180#undef ADD_INT
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +00001181}
1182
Guido van Rossume13ddc92003-04-17 17:29:22 +00001183/* API to invoke gc.collect() from C */
Neal Norwitz7b216c52006-03-04 20:01:53 +00001184Py_ssize_t
Guido van Rossume13ddc92003-04-17 17:29:22 +00001185PyGC_Collect(void)
1186{
Neal Norwitz7b216c52006-03-04 20:01:53 +00001187 Py_ssize_t n;
Guido van Rossume13ddc92003-04-17 17:29:22 +00001188
1189 if (collecting)
1190 n = 0; /* already collecting, don't do anything */
1191 else {
1192 collecting = 1;
1193 n = collect(NUM_GENERATIONS - 1);
1194 collecting = 0;
1195 }
1196
1197 return n;
1198}
1199
Neil Schemenauer43411b52001-08-30 00:05:51 +00001200/* for debugging */
Guido van Rossume13ddc92003-04-17 17:29:22 +00001201void
1202_PyGC_Dump(PyGC_Head *g)
Neil Schemenauer43411b52001-08-30 00:05:51 +00001203{
1204 _PyObject_Dump(FROM_GC(g));
1205}
1206
Neil Schemenauer43411b52001-08-30 00:05:51 +00001207/* extension modules might be compiled with GC support so these
1208 functions must always be available */
1209
Neil Schemenauerfec4eb12002-04-12 02:41:03 +00001210#undef PyObject_GC_Track
1211#undef PyObject_GC_UnTrack
1212#undef PyObject_GC_Del
1213#undef _PyObject_GC_Malloc
1214
Neil Schemenauer43411b52001-08-30 00:05:51 +00001215void
Neil Schemenauerfec4eb12002-04-12 02:41:03 +00001216PyObject_GC_Track(void *op)
Neil Schemenauer43411b52001-08-30 00:05:51 +00001217{
1218 _PyObject_GC_TRACK(op);
1219}
1220
Neil Schemenauerfec4eb12002-04-12 02:41:03 +00001221/* for binary compatibility with 2.2 */
Neil Schemenauer43411b52001-08-30 00:05:51 +00001222void
Neil Schemenauerfec4eb12002-04-12 02:41:03 +00001223_PyObject_GC_Track(PyObject *op)
1224{
1225 PyObject_GC_Track(op);
1226}
1227
1228void
1229PyObject_GC_UnTrack(void *op)
Neil Schemenauer43411b52001-08-30 00:05:51 +00001230{
Tim Peters803526b2002-07-07 05:13:56 +00001231 /* Obscure: the Py_TRASHCAN mechanism requires that we be able to
1232 * call PyObject_GC_UnTrack twice on an object.
1233 */
Neil Schemenauera2b11ec2002-05-21 15:53:24 +00001234 if (IS_TRACKED(op))
Guido van Rossumff413af2002-03-28 20:34:59 +00001235 _PyObject_GC_UNTRACK(op);
Neil Schemenauer43411b52001-08-30 00:05:51 +00001236}
1237
Neil Schemenauerfec4eb12002-04-12 02:41:03 +00001238/* for binary compatibility with 2.2 */
1239void
1240_PyObject_GC_UnTrack(PyObject *op)
1241{
1242 PyObject_GC_UnTrack(op);
1243}
1244
Neil Schemenauer43411b52001-08-30 00:05:51 +00001245PyObject *
Neil Schemenauerfec4eb12002-04-12 02:41:03 +00001246_PyObject_GC_Malloc(size_t basicsize)
Neil Schemenauer43411b52001-08-30 00:05:51 +00001247{
1248 PyObject *op;
Neil Schemenauerfec4eb12002-04-12 02:41:03 +00001249 PyGC_Head *g = PyObject_MALLOC(sizeof(PyGC_Head) + basicsize);
Neil Schemenauer43411b52001-08-30 00:05:51 +00001250 if (g == NULL)
Jeremy Hylton8a135182002-06-06 23:23:55 +00001251 return PyErr_NoMemory();
Tim Petersea405632002-07-02 00:52:30 +00001252 g->gc.gc_refs = GC_UNTRACKED;
Neil Schemenauer2880ae52002-05-04 05:35:20 +00001253 generations[0].count++; /* number of allocated GC objects */
1254 if (generations[0].count > generations[0].threshold &&
Neil Schemenauer43411b52001-08-30 00:05:51 +00001255 enabled &&
Neil Schemenauer2880ae52002-05-04 05:35:20 +00001256 generations[0].threshold &&
Neil Schemenauer43411b52001-08-30 00:05:51 +00001257 !collecting &&
1258 !PyErr_Occurred()) {
1259 collecting = 1;
Neil Schemenauer2880ae52002-05-04 05:35:20 +00001260 collect_generations();
Neil Schemenauer43411b52001-08-30 00:05:51 +00001261 collecting = 0;
1262 }
1263 op = FROM_GC(g);
Neil Schemenauer43411b52001-08-30 00:05:51 +00001264 return op;
1265}
1266
1267PyObject *
1268_PyObject_GC_New(PyTypeObject *tp)
1269{
Neil Schemenauerfec4eb12002-04-12 02:41:03 +00001270 PyObject *op = _PyObject_GC_Malloc(_PyObject_SIZE(tp));
Tim Petersfa8efab2002-04-28 01:57:25 +00001271 if (op != NULL)
1272 op = PyObject_INIT(op, tp);
1273 return op;
Neil Schemenauer43411b52001-08-30 00:05:51 +00001274}
1275
1276PyVarObject *
Martin v. Löwis18e16552006-02-15 17:27:45 +00001277_PyObject_GC_NewVar(PyTypeObject *tp, Py_ssize_t nitems)
Neil Schemenauer43411b52001-08-30 00:05:51 +00001278{
Neil Schemenauerfec4eb12002-04-12 02:41:03 +00001279 const size_t size = _PyObject_VAR_SIZE(tp, nitems);
1280 PyVarObject *op = (PyVarObject *) _PyObject_GC_Malloc(size);
Tim Petersfa8efab2002-04-28 01:57:25 +00001281 if (op != NULL)
1282 op = PyObject_INIT_VAR(op, tp, nitems);
1283 return op;
Neil Schemenauer43411b52001-08-30 00:05:51 +00001284}
1285
1286PyVarObject *
Martin v. Löwis41290682006-02-16 14:56:14 +00001287_PyObject_GC_Resize(PyVarObject *op, Py_ssize_t nitems)
Neil Schemenauer43411b52001-08-30 00:05:51 +00001288{
Tim Petersf2a67da2001-10-07 03:54:51 +00001289 const size_t basicsize = _PyObject_VAR_SIZE(op->ob_type, nitems);
Neil Schemenauer43411b52001-08-30 00:05:51 +00001290 PyGC_Head *g = AS_GC(op);
Neil Schemenauerfec4eb12002-04-12 02:41:03 +00001291 g = PyObject_REALLOC(g, sizeof(PyGC_Head) + basicsize);
Neil Schemenauer43411b52001-08-30 00:05:51 +00001292 if (g == NULL)
1293 return (PyVarObject *)PyErr_NoMemory();
1294 op = (PyVarObject *) FROM_GC(g);
Tim Peters6d483d32001-10-06 21:27:34 +00001295 op->ob_size = nitems;
Neil Schemenauer43411b52001-08-30 00:05:51 +00001296 return op;
1297}
1298
1299void
Neil Schemenauerfec4eb12002-04-12 02:41:03 +00001300PyObject_GC_Del(void *op)
Neil Schemenauer43411b52001-08-30 00:05:51 +00001301{
Neil Schemenauer43411b52001-08-30 00:05:51 +00001302 PyGC_Head *g = AS_GC(op);
Neil Schemenauera2b11ec2002-05-21 15:53:24 +00001303 if (IS_TRACKED(op))
Neil Schemenauer43411b52001-08-30 00:05:51 +00001304 gc_list_remove(g);
Neil Schemenauer2880ae52002-05-04 05:35:20 +00001305 if (generations[0].count > 0) {
1306 generations[0].count--;
Neil Schemenauer43411b52001-08-30 00:05:51 +00001307 }
Neil Schemenauerfec4eb12002-04-12 02:41:03 +00001308 PyObject_FREE(g);
Neil Schemenauer43411b52001-08-30 00:05:51 +00001309}
1310
Neil Schemenauerfec4eb12002-04-12 02:41:03 +00001311/* for binary compatibility with 2.2 */
1312#undef _PyObject_GC_Del
1313void
1314_PyObject_GC_Del(PyObject *op)
1315{
1316 PyObject_GC_Del(op);
1317}