blob: c0c091e228028679f399daff6900421a81fd4e0c [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 */
54static int collecting;
55
Tim Peters6fc13d92002-07-02 18:12:35 +000056/* list of uncollectable objects */
57static PyObject *garbage;
58
59/* Python string to use if unhandled exception occurs */
60static PyObject *gc_str;
61
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +000062/* set for debugging information */
63#define DEBUG_STATS (1<<0) /* print collection statistics */
64#define DEBUG_COLLECTABLE (1<<1) /* print collectable objects */
65#define DEBUG_UNCOLLECTABLE (1<<2) /* print uncollectable objects */
66#define DEBUG_INSTANCES (1<<3) /* print instances */
67#define DEBUG_OBJECTS (1<<4) /* print other objects */
Neil Schemenauer544de1e2000-09-22 15:22:38 +000068#define DEBUG_SAVEALL (1<<5) /* save all garbage in gc.garbage */
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +000069#define DEBUG_LEAK DEBUG_COLLECTABLE | \
70 DEBUG_UNCOLLECTABLE | \
71 DEBUG_INSTANCES | \
Neil Schemenauer544de1e2000-09-22 15:22:38 +000072 DEBUG_OBJECTS | \
73 DEBUG_SAVEALL
Jeremy Hyltonb709df32000-09-01 02:47:25 +000074static int debug;
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +000075
Tim Peters6fc13d92002-07-02 18:12:35 +000076/*--------------------------------------------------------------------------
77gc_refs values.
Neil Schemenauer43411b52001-08-30 00:05:51 +000078
Tim Peters6fc13d92002-07-02 18:12:35 +000079Between collections, every gc'ed object has one of two gc_refs values:
80
81GC_UNTRACKED
82 The initial state; objects returned by PyObject_GC_Malloc are in this
83 state. The object doesn't live in any generation list, and its
84 tp_traverse slot must not be called.
85
86GC_REACHABLE
87 The object lives in some generation list, and its tp_traverse is safe to
88 call. An object transitions to GC_REACHABLE when PyObject_GC_Track
89 is called.
90
91During a collection, gc_refs can temporarily take on other states:
92
93>= 0
94 At the start of a collection, update_refs() copies the true refcount
95 to gc_refs, for each object in the generation being collected.
96 subtract_refs() then adjusts gc_refs so that it equals the number of
97 times an object is referenced directly from outside the generation
98 being collected.
Martin v. Löwis774348c2002-11-09 19:54:06 +000099 gc_refs remains >= 0 throughout these steps.
Tim Peters6fc13d92002-07-02 18:12:35 +0000100
101GC_TENTATIVELY_UNREACHABLE
102 move_unreachable() then moves objects not reachable (whether directly or
103 indirectly) from outside the generation into an "unreachable" set.
104 Objects that are found to be reachable have gc_refs set to GC_REACHABLE
105 again. Objects that are found to be unreachable have gc_refs set to
106 GC_TENTATIVELY_UNREACHABLE. It's "tentatively" because the pass doing
107 this can't be sure until it ends, and GC_TENTATIVELY_UNREACHABLE may
108 transition back to GC_REACHABLE.
109
110 Only objects with GC_TENTATIVELY_UNREACHABLE still set are candidates
111 for collection. If it's decided not to collect such an object (e.g.,
112 it has a __del__ method), its gc_refs is restored to GC_REACHABLE again.
113----------------------------------------------------------------------------
114*/
Tim Petersea405632002-07-02 00:52:30 +0000115#define GC_UNTRACKED _PyGC_REFS_UNTRACKED
116#define GC_REACHABLE _PyGC_REFS_REACHABLE
117#define GC_TENTATIVELY_UNREACHABLE _PyGC_REFS_TENTATIVELY_UNREACHABLE
Tim Peters19b74c72002-07-01 03:52:19 +0000118
Tim Peters6fc13d92002-07-02 18:12:35 +0000119#define IS_TRACKED(o) ((AS_GC(o))->gc.gc_refs != GC_UNTRACKED)
Tim Peters19b74c72002-07-01 03:52:19 +0000120#define IS_REACHABLE(o) ((AS_GC(o))->gc.gc_refs == GC_REACHABLE)
121#define IS_TENTATIVELY_UNREACHABLE(o) ( \
122 (AS_GC(o))->gc.gc_refs == GC_TENTATIVELY_UNREACHABLE)
Neil Schemenauera2b11ec2002-05-21 15:53:24 +0000123
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000124/*** list functions ***/
125
126static void
127gc_list_init(PyGC_Head *list)
128{
Tim Peters9e4ca102001-10-11 18:31:31 +0000129 list->gc.gc_prev = list;
130 list->gc.gc_next = list;
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000131}
132
Neil Schemenauer2880ae52002-05-04 05:35:20 +0000133static int
134gc_list_is_empty(PyGC_Head *list)
135{
136 return (list->gc.gc_next == list);
137}
138
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000139static void
140gc_list_append(PyGC_Head *node, PyGC_Head *list)
141{
Tim Peters9e4ca102001-10-11 18:31:31 +0000142 node->gc.gc_next = list;
143 node->gc.gc_prev = list->gc.gc_prev;
144 node->gc.gc_prev->gc.gc_next = node;
145 list->gc.gc_prev = node;
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000146}
147
148static void
149gc_list_remove(PyGC_Head *node)
150{
Tim Peters9e4ca102001-10-11 18:31:31 +0000151 node->gc.gc_prev->gc.gc_next = node->gc.gc_next;
152 node->gc.gc_next->gc.gc_prev = node->gc.gc_prev;
153 node->gc.gc_next = NULL; /* object is not currently tracked */
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000154}
155
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000156/* append a list onto another list, from becomes an empty list */
157static void
158gc_list_merge(PyGC_Head *from, PyGC_Head *to)
159{
160 PyGC_Head *tail;
Neil Schemenauer2880ae52002-05-04 05:35:20 +0000161 if (!gc_list_is_empty(from)) {
Tim Peters9e4ca102001-10-11 18:31:31 +0000162 tail = to->gc.gc_prev;
163 tail->gc.gc_next = from->gc.gc_next;
164 tail->gc.gc_next->gc.gc_prev = tail;
165 to->gc.gc_prev = from->gc.gc_prev;
166 to->gc.gc_prev->gc.gc_next = to;
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000167 }
168 gc_list_init(from);
169}
170
171static long
172gc_list_size(PyGC_Head *list)
173{
174 PyGC_Head *gc;
175 long n = 0;
Tim Peters9e4ca102001-10-11 18:31:31 +0000176 for (gc = list->gc.gc_next; gc != list; gc = gc->gc.gc_next) {
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000177 n++;
178 }
179 return n;
180}
181
182/*** end of list stuff ***/
183
184
Tim Peters19b74c72002-07-01 03:52:19 +0000185/* Set all gc_refs = ob_refcnt. After this, gc_refs is > 0 for all objects
186 * in containers, and is GC_REACHABLE for all tracked gc objects not in
187 * containers.
Tim Peters88396172002-06-30 17:56:40 +0000188 */
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000189static void
190update_refs(PyGC_Head *containers)
191{
Tim Peters9e4ca102001-10-11 18:31:31 +0000192 PyGC_Head *gc = containers->gc.gc_next;
Tim Petersea405632002-07-02 00:52:30 +0000193 for (; gc != containers; gc = gc->gc.gc_next) {
194 assert(gc->gc.gc_refs == GC_REACHABLE);
Tim Peters9e4ca102001-10-11 18:31:31 +0000195 gc->gc.gc_refs = FROM_GC(gc)->ob_refcnt;
Tim Petersea405632002-07-02 00:52:30 +0000196 }
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000197}
198
Tim Peters19b74c72002-07-01 03:52:19 +0000199/* A traversal callback for subtract_refs. */
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000200static int
201visit_decref(PyObject *op, void *data)
202{
Tim Peters93cd83e2002-06-30 21:31:03 +0000203 assert(op != NULL);
Tim Peters19b74c72002-07-01 03:52:19 +0000204 if (PyObject_IS_GC(op)) {
205 PyGC_Head *gc = AS_GC(op);
206 /* We're only interested in gc_refs for objects in the
207 * generation being collected, which can be recognized
208 * because only they have positive gc_refs.
209 */
Tim Petersaab713b2002-07-02 22:15:28 +0000210 assert(gc->gc.gc_refs != 0); /* else refcount was too small */
Tim Peters19b74c72002-07-01 03:52:19 +0000211 if (gc->gc.gc_refs > 0)
212 gc->gc.gc_refs--;
213 }
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000214 return 0;
215}
216
Tim Peters19b74c72002-07-01 03:52:19 +0000217/* Subtract internal references from gc_refs. After this, gc_refs is >= 0
218 * for all objects in containers, and is GC_REACHABLE for all tracked gc
219 * objects not in containers. The ones with gc_refs > 0 are directly
220 * reachable from outside containers, and so can't be collected.
221 */
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000222static void
223subtract_refs(PyGC_Head *containers)
224{
225 traverseproc traverse;
Tim Peters9e4ca102001-10-11 18:31:31 +0000226 PyGC_Head *gc = containers->gc.gc_next;
227 for (; gc != containers; gc=gc->gc.gc_next) {
Neil Schemenauer43411b52001-08-30 00:05:51 +0000228 traverse = FROM_GC(gc)->ob_type->tp_traverse;
229 (void) traverse(FROM_GC(gc),
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000230 (visitproc)visit_decref,
231 NULL);
232 }
233}
234
Tim Peters19b74c72002-07-01 03:52:19 +0000235/* A traversal callback for move_unreachable. */
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000236static int
Tim Peters19b74c72002-07-01 03:52:19 +0000237visit_reachable(PyObject *op, PyGC_Head *reachable)
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000238{
Tim Petersea405632002-07-02 00:52:30 +0000239 if (PyObject_IS_GC(op)) {
Tim Peters19b74c72002-07-01 03:52:19 +0000240 PyGC_Head *gc = AS_GC(op);
241 const int gc_refs = gc->gc.gc_refs;
242
243 if (gc_refs == 0) {
244 /* This is in move_unreachable's 'young' list, but
245 * the traversal hasn't yet gotten to it. All
246 * we need to do is tell move_unreachable that it's
247 * reachable.
248 */
249 gc->gc.gc_refs = 1;
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000250 }
Tim Peters19b74c72002-07-01 03:52:19 +0000251 else if (gc_refs == GC_TENTATIVELY_UNREACHABLE) {
252 /* This had gc_refs = 0 when move_unreachable got
253 * to it, but turns out it's reachable after all.
254 * Move it back to move_unreachable's 'young' list,
255 * and move_unreachable will eventually get to it
256 * again.
257 */
258 gc_list_remove(gc);
259 gc_list_append(gc, reachable);
260 gc->gc.gc_refs = 1;
261 }
262 /* Else there's nothing to do.
263 * If gc_refs > 0, it must be in move_unreachable's 'young'
264 * list, and move_unreachable will eventually get to it.
265 * If gc_refs == GC_REACHABLE, it's either in some other
266 * generation so we don't care about it, or move_unreachable
Tim Peters6fc13d92002-07-02 18:12:35 +0000267 * already dealt with it.
Tim Petersea405632002-07-02 00:52:30 +0000268 * If gc_refs == GC_UNTRACKED, it must be ignored.
Tim Peters19b74c72002-07-01 03:52:19 +0000269 */
Tim Petersea405632002-07-02 00:52:30 +0000270 else {
271 assert(gc_refs > 0
272 || gc_refs == GC_REACHABLE
273 || gc_refs == GC_UNTRACKED);
274 }
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000275 }
276 return 0;
277}
278
Tim Peters19b74c72002-07-01 03:52:19 +0000279/* Move the unreachable objects from young to unreachable. After this,
280 * all objects in young have gc_refs = GC_REACHABLE, and all objects in
281 * unreachable have gc_refs = GC_TENTATIVELY_UNREACHABLE. All tracked
282 * gc objects not in young or unreachable still have gc_refs = GC_REACHABLE.
283 * All objects in young after this are directly or indirectly reachable
284 * from outside the original young; and all objects in unreachable are
285 * not.
Tim Peters88396172002-06-30 17:56:40 +0000286 */
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000287static void
Tim Peters19b74c72002-07-01 03:52:19 +0000288move_unreachable(PyGC_Head *young, PyGC_Head *unreachable)
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000289{
Tim Peters19b74c72002-07-01 03:52:19 +0000290 PyGC_Head *gc = young->gc.gc_next;
291
292 /* Invariants: all objects "to the left" of us in young have gc_refs
293 * = GC_REACHABLE, and are indeed reachable (directly or indirectly)
294 * from outside the young list as it was at entry. All other objects
295 * from the original young "to the left" of us are in unreachable now,
296 * and have gc_refs = GC_TENTATIVELY_UNREACHABLE. All objects to the
297 * left of us in 'young' now have been scanned, and no objects here
298 * or to the right have been scanned yet.
299 */
300
301 while (gc != young) {
302 PyGC_Head *next;
303
Tim Peters6fc13d92002-07-02 18:12:35 +0000304 if (gc->gc.gc_refs) {
305 /* gc is definitely reachable from outside the
306 * original 'young'. Mark it as such, and traverse
307 * its pointers to find any other objects that may
308 * be directly reachable from it. Note that the
309 * call to tp_traverse may append objects to young,
310 * so we have to wait until it returns to determine
311 * the next object to visit.
312 */
313 PyObject *op = FROM_GC(gc);
314 traverseproc traverse = op->ob_type->tp_traverse;
315 assert(gc->gc.gc_refs > 0);
316 gc->gc.gc_refs = GC_REACHABLE;
317 (void) traverse(op,
318 (visitproc)visit_reachable,
319 (void *)young);
320 next = gc->gc.gc_next;
321 }
322 else {
Tim Peters19b74c72002-07-01 03:52:19 +0000323 /* This *may* be unreachable. To make progress,
324 * assume it is. gc isn't directly reachable from
325 * any object we've already traversed, but may be
326 * reachable from an object we haven't gotten to yet.
327 * visit_reachable will eventually move gc back into
328 * young if that's so, and we'll see it again.
329 */
330 next = gc->gc.gc_next;
331 gc_list_remove(gc);
332 gc_list_append(gc, unreachable);
333 gc->gc.gc_refs = GC_TENTATIVELY_UNREACHABLE;
334 }
Tim Peters19b74c72002-07-01 03:52:19 +0000335 gc = next;
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000336 }
337}
338
Tim Peters88396172002-06-30 17:56:40 +0000339/* return true if object has a finalization method */
Neil Schemenauera765c122001-11-01 17:35:23 +0000340static int
341has_finalizer(PyObject *op)
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000342{
Jeremy Hylton06257772000-08-31 15:10:24 +0000343 static PyObject *delstr = NULL;
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000344 if (delstr == NULL) {
345 delstr = PyString_InternFromString("__del__");
Jeremy Hylton06257772000-08-31 15:10:24 +0000346 if (delstr == NULL)
347 Py_FatalError("PyGC: can't initialize __del__ string");
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000348 }
Guido van Rossum40307142002-08-09 17:39:14 +0000349 return PyInstance_Check(op) ? PyObject_HasAttr(op, delstr) :
350 PyType_HasFeature(op->ob_type, Py_TPFLAGS_HEAPTYPE) ?
351 op->ob_type->tp_del != NULL : 0;
Neil Schemenauera765c122001-11-01 17:35:23 +0000352}
353
354/* Move all objects with finalizers (instances with __del__) */
355static void
356move_finalizers(PyGC_Head *unreachable, PyGC_Head *finalizers)
357{
358 PyGC_Head *next;
359 PyGC_Head *gc = unreachable->gc.gc_next;
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000360 for (; gc != unreachable; gc=next) {
Neil Schemenauer43411b52001-08-30 00:05:51 +0000361 PyObject *op = FROM_GC(gc);
Tim Peters9e4ca102001-10-11 18:31:31 +0000362 next = gc->gc.gc_next;
Neil Schemenauera765c122001-11-01 17:35:23 +0000363 if (has_finalizer(op)) {
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000364 gc_list_remove(gc);
365 gc_list_append(gc, finalizers);
Tim Peters19b74c72002-07-01 03:52:19 +0000366 gc->gc.gc_refs = GC_REACHABLE;
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000367 }
368 }
369}
370
Tim Peters19b74c72002-07-01 03:52:19 +0000371/* A traversal callback for move_finalizer_reachable. */
372static int
373visit_move(PyObject *op, PyGC_Head *tolist)
374{
375 if (PyObject_IS_GC(op)) {
Tim Petersea405632002-07-02 00:52:30 +0000376 if (IS_TENTATIVELY_UNREACHABLE(op)) {
Tim Peters19b74c72002-07-01 03:52:19 +0000377 PyGC_Head *gc = AS_GC(op);
378 gc_list_remove(gc);
379 gc_list_append(gc, tolist);
380 gc->gc.gc_refs = GC_REACHABLE;
381 }
382 }
383 return 0;
384}
385
386/* Move objects that are reachable from finalizers, from the unreachable set
387 * into the finalizers set.
388 */
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000389static void
390move_finalizer_reachable(PyGC_Head *finalizers)
391{
392 traverseproc traverse;
Tim Peters9e4ca102001-10-11 18:31:31 +0000393 PyGC_Head *gc = finalizers->gc.gc_next;
394 for (; gc != finalizers; gc=gc->gc.gc_next) {
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000395 /* careful, finalizers list is growing here */
Neil Schemenauer43411b52001-08-30 00:05:51 +0000396 traverse = FROM_GC(gc)->ob_type->tp_traverse;
Tim Peters88396172002-06-30 17:56:40 +0000397 (void) traverse(FROM_GC(gc),
Neil Schemenauer43411b52001-08-30 00:05:51 +0000398 (visitproc)visit_move,
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000399 (void *)finalizers);
400 }
401}
402
403static void
Jeremy Hylton06257772000-08-31 15:10:24 +0000404debug_instance(char *msg, PyInstanceObject *inst)
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000405{
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000406 char *cname;
Neil Schemenauera765c122001-11-01 17:35:23 +0000407 /* simple version of instance_repr */
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000408 PyObject *classname = inst->in_class->cl_name;
409 if (classname != NULL && PyString_Check(classname))
410 cname = PyString_AsString(classname);
411 else
412 cname = "?";
Jeremy Hylton06257772000-08-31 15:10:24 +0000413 PySys_WriteStderr("gc: %.100s <%.100s instance at %p>\n",
414 msg, cname, inst);
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000415}
416
417static void
Jeremy Hylton06257772000-08-31 15:10:24 +0000418debug_cycle(char *msg, PyObject *op)
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000419{
420 if ((debug & DEBUG_INSTANCES) && PyInstance_Check(op)) {
Jeremy Hylton06257772000-08-31 15:10:24 +0000421 debug_instance(msg, (PyInstanceObject *)op);
Neil Schemenauer544de1e2000-09-22 15:22:38 +0000422 }
423 else if (debug & DEBUG_OBJECTS) {
Jeremy Hylton06257772000-08-31 15:10:24 +0000424 PySys_WriteStderr("gc: %.100s <%.100s %p>\n",
425 msg, op->ob_type->tp_name, op);
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000426 }
427}
428
429/* Handle uncollectable garbage (cycles with finalizers). */
430static void
431handle_finalizers(PyGC_Head *finalizers, PyGC_Head *old)
432{
433 PyGC_Head *gc;
434 if (garbage == NULL) {
435 garbage = PyList_New(0);
436 }
Tim Peters9e4ca102001-10-11 18:31:31 +0000437 for (gc = finalizers->gc.gc_next; gc != finalizers;
438 gc = finalizers->gc.gc_next) {
Neil Schemenauer43411b52001-08-30 00:05:51 +0000439 PyObject *op = FROM_GC(gc);
Neil Schemenauera765c122001-11-01 17:35:23 +0000440 if ((debug & DEBUG_SAVEALL) || has_finalizer(op)) {
441 /* If SAVEALL is not set then just append objects with
442 * finalizers to the list of garbage. All objects in
443 * the finalizers list are reachable from those
Tim Peters19b74c72002-07-01 03:52:19 +0000444 * objects.
445 */
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000446 PyList_Append(garbage, op);
447 }
Tim Peters88396172002-06-30 17:56:40 +0000448 /* object is now reachable again */
Tim Peters19b74c72002-07-01 03:52:19 +0000449 assert(IS_REACHABLE(op));
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000450 gc_list_remove(gc);
451 gc_list_append(gc, old);
452 }
453}
454
Neil Schemenauer544de1e2000-09-22 15:22:38 +0000455/* Break reference cycles by clearing the containers involved. This is
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000456 * tricky business as the lists can be changing and we don't know which
Tim Peters19b74c72002-07-01 03:52:19 +0000457 * objects may be freed. It is possible I screwed something up here.
458 */
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000459static void
460delete_garbage(PyGC_Head *unreachable, PyGC_Head *old)
461{
462 inquiry clear;
463
Neil Schemenauer2880ae52002-05-04 05:35:20 +0000464 while (!gc_list_is_empty(unreachable)) {
Tim Peters9e4ca102001-10-11 18:31:31 +0000465 PyGC_Head *gc = unreachable->gc.gc_next;
Neil Schemenauer43411b52001-08-30 00:05:51 +0000466 PyObject *op = FROM_GC(gc);
Tim Peters88396172002-06-30 17:56:40 +0000467
Tim Peters19b74c72002-07-01 03:52:19 +0000468 assert(IS_TENTATIVELY_UNREACHABLE(op));
Neil Schemenauer544de1e2000-09-22 15:22:38 +0000469 if (debug & DEBUG_SAVEALL) {
470 PyList_Append(garbage, op);
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000471 }
Neil Schemenauer544de1e2000-09-22 15:22:38 +0000472 else {
473 if ((clear = op->ob_type->tp_clear) != NULL) {
474 Py_INCREF(op);
Jeremy Hylton8a135182002-06-06 23:23:55 +0000475 clear(op);
Neil Schemenauer544de1e2000-09-22 15:22:38 +0000476 Py_DECREF(op);
477 }
478 }
Tim Peters9e4ca102001-10-11 18:31:31 +0000479 if (unreachable->gc.gc_next == gc) {
Neil Schemenauer544de1e2000-09-22 15:22:38 +0000480 /* object is still alive, move it, it may die later */
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000481 gc_list_remove(gc);
482 gc_list_append(gc, old);
Tim Peters19b74c72002-07-01 03:52:19 +0000483 gc->gc.gc_refs = GC_REACHABLE;
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000484 }
485 }
486}
487
488/* This is the main function. Read this to understand how the
489 * collection process works. */
490static long
Neil Schemenauer2880ae52002-05-04 05:35:20 +0000491collect(int generation)
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000492{
Neil Schemenauer2880ae52002-05-04 05:35:20 +0000493 int i;
Tim Peters19b74c72002-07-01 03:52:19 +0000494 long m = 0; /* # objects collected */
495 long n = 0; /* # unreachable objects that couldn't be collected */
Neil Schemenauer2880ae52002-05-04 05:35:20 +0000496 PyGC_Head *young; /* the generation we are examining */
497 PyGC_Head *old; /* next older generation */
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000498 PyGC_Head unreachable;
499 PyGC_Head finalizers;
500 PyGC_Head *gc;
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000501
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000502 if (debug & DEBUG_STATS) {
Neil Schemenauer2880ae52002-05-04 05:35:20 +0000503 PySys_WriteStderr("gc: collecting generation %d...\n",
504 generation);
505 PySys_WriteStderr("gc: objects in each generation:");
506 for (i = 0; i < NUM_GENERATIONS; i++) {
507 PySys_WriteStderr(" %ld", gc_list_size(GEN_HEAD(i)));
508 }
509 PySys_WriteStderr("\n");
510 }
511
512 /* update collection and allocation counters */
513 if (generation+1 < NUM_GENERATIONS)
514 generations[generation+1].count += 1;
515 for (i = 0; i <= generation; i++)
Neil Schemenauerc9051642002-06-28 19:16:04 +0000516 generations[i].count = 0;
Neil Schemenauer2880ae52002-05-04 05:35:20 +0000517
518 /* merge younger generations with one we are currently collecting */
519 for (i = 0; i < generation; i++) {
520 gc_list_merge(GEN_HEAD(i), GEN_HEAD(generation));
521 }
522
523 /* handy references */
524 young = GEN_HEAD(generation);
Tim Peters19b74c72002-07-01 03:52:19 +0000525 if (generation < NUM_GENERATIONS-1)
Neil Schemenauer2880ae52002-05-04 05:35:20 +0000526 old = GEN_HEAD(generation+1);
Tim Peters19b74c72002-07-01 03:52:19 +0000527 else
528 old = young;
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000529
530 /* Using ob_refcnt and gc_refs, calculate which objects in the
531 * container set are reachable from outside the set (ie. have a
532 * refcount greater than 0 when all the references within the
Tim Peters19b74c72002-07-01 03:52:19 +0000533 * set are taken into account
534 */
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000535 update_refs(young);
536 subtract_refs(young);
537
Tim Peters19b74c72002-07-01 03:52:19 +0000538 /* Leave everything reachable from outside young in young, and move
539 * everything else (in young) to unreachable.
540 * NOTE: This used to move the reachable objects into a reachable
541 * set instead. But most things usually turn out to be reachable,
542 * so it's more efficient to move the unreachable things.
543 */
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000544 gc_list_init(&unreachable);
Tim Peters19b74c72002-07-01 03:52:19 +0000545 move_unreachable(young, &unreachable);
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000546
Tim Peters19b74c72002-07-01 03:52:19 +0000547 /* Move reachable objects to next generation. */
548 if (young != old)
549 gc_list_merge(young, old);
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000550
Tim Peters19b74c72002-07-01 03:52:19 +0000551 /* All objects in unreachable are trash, but objects reachable from
552 * finalizers can't safely be deleted. Python programmers should take
553 * care not to create such things. For Python, finalizers means
554 * instance objects with __del__ methods.
555 */
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000556 gc_list_init(&finalizers);
557 move_finalizers(&unreachable, &finalizers);
558 move_finalizer_reachable(&finalizers);
559
560 /* Collect statistics on collectable objects found and print
561 * debugging information. */
Tim Peters9e4ca102001-10-11 18:31:31 +0000562 for (gc = unreachable.gc.gc_next; gc != &unreachable;
563 gc = gc->gc.gc_next) {
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000564 m++;
Jeremy Hylton06257772000-08-31 15:10:24 +0000565 if (debug & DEBUG_COLLECTABLE) {
Neil Schemenauer43411b52001-08-30 00:05:51 +0000566 debug_cycle("collectable", FROM_GC(gc));
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000567 }
568 }
Tim Peters19b74c72002-07-01 03:52:19 +0000569 /* Call tp_clear on objects in the collectable set. This will cause
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000570 * the reference cycles to be broken. It may also cause some objects in
571 * finalizers to be freed */
572 delete_garbage(&unreachable, old);
573
574 /* Collect statistics on uncollectable objects found and print
575 * debugging information. */
Tim Peters9e4ca102001-10-11 18:31:31 +0000576 for (gc = finalizers.gc.gc_next; gc != &finalizers;
577 gc = gc->gc.gc_next) {
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000578 n++;
Jeremy Hylton06257772000-08-31 15:10:24 +0000579 if (debug & DEBUG_UNCOLLECTABLE) {
Neil Schemenauer43411b52001-08-30 00:05:51 +0000580 debug_cycle("uncollectable", FROM_GC(gc));
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000581 }
582 }
Jeremy Hylton06257772000-08-31 15:10:24 +0000583 if (debug & DEBUG_STATS) {
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000584 if (m == 0 && n == 0) {
Jeremy Hylton06257772000-08-31 15:10:24 +0000585 PySys_WriteStderr("gc: done.\n");
Neil Schemenauer544de1e2000-09-22 15:22:38 +0000586 }
587 else {
Jeremy Hylton06257772000-08-31 15:10:24 +0000588 PySys_WriteStderr(
589 "gc: done, %ld unreachable, %ld uncollectable.\n",
590 n+m, n);
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000591 }
592 }
593
594 /* Append instances in the uncollectable set to a Python
595 * reachable list of garbage. The programmer has to deal with
596 * this if they insist on creating this type of structure. */
597 handle_finalizers(&finalizers, old);
598
Jeremy Hyltonb709df32000-09-01 02:47:25 +0000599 if (PyErr_Occurred()) {
Neil Schemenauer544de1e2000-09-22 15:22:38 +0000600 if (gc_str == NULL) {
601 gc_str = PyString_FromString("garbage collection");
602 }
Jeremy Hyltonb709df32000-09-01 02:47:25 +0000603 PyErr_WriteUnraisable(gc_str);
604 Py_FatalError("unexpected exception during garbage collection");
605 }
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000606 return n+m;
607}
608
609static long
610collect_generations(void)
611{
Neil Schemenauer2880ae52002-05-04 05:35:20 +0000612 int i;
Vladimir Marangozovb16714b2000-07-10 05:37:39 +0000613 long n = 0;
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000614
Neil Schemenauer2880ae52002-05-04 05:35:20 +0000615 /* Find the oldest generation (higest numbered) where the count
616 * exceeds the threshold. Objects in the that generation and
617 * generations younger than it will be collected. */
618 for (i = NUM_GENERATIONS-1; i >= 0; i--) {
619 if (generations[i].count > generations[i].threshold) {
620 n = collect(i);
621 break;
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000622 }
623 }
624 return n;
625}
626
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +0000627PyDoc_STRVAR(gc_enable__doc__,
Vladimir Marangozovf9d20c32000-08-06 22:45:31 +0000628"enable() -> None\n"
629"\n"
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +0000630"Enable automatic garbage collection.\n");
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000631
Vladimir Marangozovf9d20c32000-08-06 22:45:31 +0000632static PyObject *
633gc_enable(PyObject *self, PyObject *args)
634{
635
636 if (!PyArg_ParseTuple(args, ":enable")) /* check no args */
637 return NULL;
638
639 enabled = 1;
640
641 Py_INCREF(Py_None);
642 return Py_None;
643}
644
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +0000645PyDoc_STRVAR(gc_disable__doc__,
Vladimir Marangozovf9d20c32000-08-06 22:45:31 +0000646"disable() -> None\n"
647"\n"
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +0000648"Disable automatic garbage collection.\n");
Vladimir Marangozovf9d20c32000-08-06 22:45:31 +0000649
650static PyObject *
651gc_disable(PyObject *self, PyObject *args)
652{
653
654 if (!PyArg_ParseTuple(args, ":disable")) /* check no args */
655 return NULL;
656
657 enabled = 0;
658
659 Py_INCREF(Py_None);
660 return Py_None;
661}
662
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +0000663PyDoc_STRVAR(gc_isenabled__doc__,
Vladimir Marangozovf9d20c32000-08-06 22:45:31 +0000664"isenabled() -> status\n"
665"\n"
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +0000666"Returns true if automatic garbage collection is enabled.\n");
Vladimir Marangozovf9d20c32000-08-06 22:45:31 +0000667
668static PyObject *
669gc_isenabled(PyObject *self, PyObject *args)
670{
671
672 if (!PyArg_ParseTuple(args, ":isenabled")) /* check no args */
673 return NULL;
674
675 return Py_BuildValue("i", enabled);
676}
677
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +0000678PyDoc_STRVAR(gc_collect__doc__,
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000679"collect() -> n\n"
680"\n"
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +0000681"Run a full collection. The number of unreachable objects is returned.\n");
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000682
683static PyObject *
Vladimir Marangozovf9d20c32000-08-06 22:45:31 +0000684gc_collect(PyObject *self, PyObject *args)
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000685{
686 long n;
687
Fred Drakecc1be242000-07-12 04:42:23 +0000688 if (!PyArg_ParseTuple(args, ":collect")) /* check no args */
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000689 return NULL;
690
Neil Schemenauere8c40cb2001-10-31 23:09:35 +0000691 if (collecting) {
692 n = 0; /* already collecting, don't do anything */
693 }
694 else {
695 collecting = 1;
Neil Schemenauer2880ae52002-05-04 05:35:20 +0000696 n = collect(NUM_GENERATIONS - 1);
Neil Schemenauere8c40cb2001-10-31 23:09:35 +0000697 collecting = 0;
698 }
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000699
Neil Schemenauer7760cff2000-09-22 22:35:36 +0000700 return Py_BuildValue("l", n);
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000701}
702
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +0000703PyDoc_STRVAR(gc_set_debug__doc__,
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000704"set_debug(flags) -> None\n"
705"\n"
706"Set the garbage collection debugging flags. Debugging information is\n"
707"written to sys.stderr.\n"
708"\n"
709"flags is an integer and can have the following bits turned on:\n"
710"\n"
711" DEBUG_STATS - Print statistics during collection.\n"
712" DEBUG_COLLECTABLE - Print collectable objects found.\n"
713" DEBUG_UNCOLLECTABLE - Print unreachable but uncollectable objects found.\n"
714" DEBUG_INSTANCES - Print instance objects.\n"
715" DEBUG_OBJECTS - Print objects other than instances.\n"
Neil Schemenauer544de1e2000-09-22 15:22:38 +0000716" DEBUG_SAVEALL - Save objects to gc.garbage rather than freeing them.\n"
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +0000717" DEBUG_LEAK - Debug leaking programs (everything but STATS).\n");
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000718
719static PyObject *
Vladimir Marangozovf9d20c32000-08-06 22:45:31 +0000720gc_set_debug(PyObject *self, PyObject *args)
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000721{
Neil Schemenauer7760cff2000-09-22 22:35:36 +0000722 if (!PyArg_ParseTuple(args, "i:set_debug", &debug))
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000723 return NULL;
724
725 Py_INCREF(Py_None);
726 return Py_None;
727}
728
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +0000729PyDoc_STRVAR(gc_get_debug__doc__,
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000730"get_debug() -> flags\n"
731"\n"
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +0000732"Get the garbage collection debugging flags.\n");
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000733
734static PyObject *
Vladimir Marangozovf9d20c32000-08-06 22:45:31 +0000735gc_get_debug(PyObject *self, PyObject *args)
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000736{
Fred Drakecc1be242000-07-12 04:42:23 +0000737 if (!PyArg_ParseTuple(args, ":get_debug")) /* no args */
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000738 return NULL;
739
740 return Py_BuildValue("i", debug);
741}
742
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +0000743PyDoc_STRVAR(gc_set_thresh__doc__,
Neal Norwitz2a47c0f2002-01-29 00:53:41 +0000744"set_threshold(threshold0, [threshold1, threshold2]) -> None\n"
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000745"\n"
746"Sets the collection thresholds. Setting threshold0 to zero disables\n"
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +0000747"collection.\n");
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000748
749static PyObject *
Vladimir Marangozovf9d20c32000-08-06 22:45:31 +0000750gc_set_thresh(PyObject *self, PyObject *args)
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000751{
Neil Schemenauer2880ae52002-05-04 05:35:20 +0000752 int i;
753 if (!PyArg_ParseTuple(args, "i|ii:set_threshold",
754 &generations[0].threshold,
755 &generations[1].threshold,
756 &generations[2].threshold))
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000757 return NULL;
Neil Schemenauer2880ae52002-05-04 05:35:20 +0000758 for (i = 2; i < NUM_GENERATIONS; i++) {
759 /* generations higher than 2 get the same threshold */
760 generations[i].threshold = generations[2].threshold;
761 }
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000762
763 Py_INCREF(Py_None);
764 return Py_None;
765}
766
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +0000767PyDoc_STRVAR(gc_get_thresh__doc__,
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000768"get_threshold() -> (threshold0, threshold1, threshold2)\n"
769"\n"
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +0000770"Return the current collection thresholds\n");
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000771
772static PyObject *
Vladimir Marangozovf9d20c32000-08-06 22:45:31 +0000773gc_get_thresh(PyObject *self, PyObject *args)
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000774{
Fred Drakecc1be242000-07-12 04:42:23 +0000775 if (!PyArg_ParseTuple(args, ":get_threshold")) /* no args */
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000776 return NULL;
777
Neil Schemenauer2880ae52002-05-04 05:35:20 +0000778 return Py_BuildValue("(iii)",
779 generations[0].threshold,
780 generations[1].threshold,
781 generations[2].threshold);
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000782}
783
Neil Schemenauer48c70342001-08-09 15:38:31 +0000784static int
Martin v. Löwis560da622001-11-24 09:24:51 +0000785referrersvisit(PyObject* obj, PyObject *objs)
Neil Schemenauer48c70342001-08-09 15:38:31 +0000786{
Martin v. Löwisc8fe77b2001-11-29 18:08:31 +0000787 int i;
788 for (i = 0; i < PyTuple_GET_SIZE(objs); i++)
789 if (PyTuple_GET_ITEM(objs, i) == obj)
790 return 1;
Neil Schemenauer48c70342001-08-09 15:38:31 +0000791 return 0;
792}
793
Neil Schemenauer17e7be62001-08-10 14:46:47 +0000794static int
Martin v. Löwis560da622001-11-24 09:24:51 +0000795gc_referrers_for(PyObject *objs, PyGC_Head *list, PyObject *resultlist)
Neil Schemenauer48c70342001-08-09 15:38:31 +0000796{
797 PyGC_Head *gc;
798 PyObject *obj;
799 traverseproc traverse;
Tim Peters9e4ca102001-10-11 18:31:31 +0000800 for (gc = list->gc.gc_next; gc != list; gc = gc->gc.gc_next) {
Neil Schemenauer43411b52001-08-30 00:05:51 +0000801 obj = FROM_GC(gc);
Neil Schemenauer48c70342001-08-09 15:38:31 +0000802 traverse = obj->ob_type->tp_traverse;
803 if (obj == objs || obj == resultlist)
804 continue;
Martin v. Löwis560da622001-11-24 09:24:51 +0000805 if (traverse(obj, (visitproc)referrersvisit, objs)) {
Neil Schemenauer17e7be62001-08-10 14:46:47 +0000806 if (PyList_Append(resultlist, obj) < 0)
807 return 0; /* error */
Neil Schemenauer48c70342001-08-09 15:38:31 +0000808 }
809 }
Neil Schemenauer17e7be62001-08-10 14:46:47 +0000810 return 1; /* no error */
Neil Schemenauer48c70342001-08-09 15:38:31 +0000811}
812
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +0000813PyDoc_STRVAR(gc_get_referrers__doc__,
Martin v. Löwis560da622001-11-24 09:24:51 +0000814"get_referrers(*objs) -> list\n\
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +0000815Return the list of objects that directly refer to any of objs.");
Neil Schemenauer48c70342001-08-09 15:38:31 +0000816
Neil Schemenauer17e7be62001-08-10 14:46:47 +0000817static PyObject *
Martin v. Löwis560da622001-11-24 09:24:51 +0000818gc_get_referrers(PyObject *self, PyObject *args)
Neil Schemenauer48c70342001-08-09 15:38:31 +0000819{
Neil Schemenauer2880ae52002-05-04 05:35:20 +0000820 int i;
Neil Schemenauer48c70342001-08-09 15:38:31 +0000821 PyObject *result = PyList_New(0);
Neil Schemenauer2880ae52002-05-04 05:35:20 +0000822 for (i = 0; i < NUM_GENERATIONS; i++) {
823 if (!(gc_referrers_for(args, GEN_HEAD(i), result))) {
824 Py_DECREF(result);
825 return NULL;
826 }
Neil Schemenauer17e7be62001-08-10 14:46:47 +0000827 }
Neil Schemenauer48c70342001-08-09 15:38:31 +0000828 return result;
829}
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000830
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +0000831PyDoc_STRVAR(gc_get_objects__doc__,
Neil Schemenauerc7c8d8e2001-08-09 15:58:59 +0000832"get_objects() -> [...]\n"
833"\n"
834"Return a list of objects tracked by the collector (excluding the list\n"
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +0000835"returned).\n");
Neil Schemenauerc7c8d8e2001-08-09 15:58:59 +0000836
837/* appending objects in a GC list to a Python list */
Martin v. Löwis155aad12001-12-02 12:21:34 +0000838static int
Neil Schemenauerc7c8d8e2001-08-09 15:58:59 +0000839append_objects(PyObject *py_list, PyGC_Head *gc_list)
840{
841 PyGC_Head *gc;
Tim Peters9e4ca102001-10-11 18:31:31 +0000842 for (gc = gc_list->gc.gc_next; gc != gc_list; gc = gc->gc.gc_next) {
Neil Schemenauer43411b52001-08-30 00:05:51 +0000843 PyObject *op = FROM_GC(gc);
Neil Schemenauerc7c8d8e2001-08-09 15:58:59 +0000844 if (op != py_list) {
Martin v. Löwis155aad12001-12-02 12:21:34 +0000845 if (PyList_Append(py_list, op)) {
846 return -1; /* exception */
847 }
Neil Schemenauerc7c8d8e2001-08-09 15:58:59 +0000848 }
849 }
Martin v. Löwis155aad12001-12-02 12:21:34 +0000850 return 0;
Neil Schemenauerc7c8d8e2001-08-09 15:58:59 +0000851}
852
853static PyObject *
854gc_get_objects(PyObject *self, PyObject *args)
855{
Neil Schemenauer2880ae52002-05-04 05:35:20 +0000856 int i;
Neil Schemenauerc7c8d8e2001-08-09 15:58:59 +0000857 PyObject* result;
858
859 if (!PyArg_ParseTuple(args, ":get_objects")) /* check no args */
860 return NULL;
861 result = PyList_New(0);
Martin v. Löwisf8a6f242001-12-02 18:31:02 +0000862 if (result == NULL) {
863 return NULL;
864 }
Neil Schemenauer2880ae52002-05-04 05:35:20 +0000865 for (i = 0; i < NUM_GENERATIONS; i++) {
866 if (append_objects(result, GEN_HEAD(i))) {
867 Py_DECREF(result);
868 return NULL;
869 }
Martin v. Löwis155aad12001-12-02 12:21:34 +0000870 }
Neil Schemenauerc7c8d8e2001-08-09 15:58:59 +0000871 return result;
872}
873
874
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +0000875PyDoc_STRVAR(gc__doc__,
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000876"This module provides access to the garbage collector for reference cycles.\n"
877"\n"
Vladimir Marangozovf9d20c32000-08-06 22:45:31 +0000878"enable() -- Enable automatic garbage collection.\n"
879"disable() -- Disable automatic garbage collection.\n"
880"isenabled() -- Returns true if automatic collection is enabled.\n"
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000881"collect() -- Do a full collection right now.\n"
882"set_debug() -- Set debugging flags.\n"
883"get_debug() -- Get debugging flags.\n"
884"set_threshold() -- Set the collection thresholds.\n"
885"get_threshold() -- Return the current the collection thresholds.\n"
Neil Schemenauerc7c8d8e2001-08-09 15:58:59 +0000886"get_objects() -- Return a list of all objects tracked by the collector.\n"
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +0000887"get_referrers() -- Return the list of objects that refer to an object.\n");
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000888
889static PyMethodDef GcMethods[] = {
Neil Schemenauer544de1e2000-09-22 15:22:38 +0000890 {"enable", gc_enable, METH_VARARGS, gc_enable__doc__},
891 {"disable", gc_disable, METH_VARARGS, gc_disable__doc__},
Vladimir Marangozovf9d20c32000-08-06 22:45:31 +0000892 {"isenabled", gc_isenabled, METH_VARARGS, gc_isenabled__doc__},
893 {"set_debug", gc_set_debug, METH_VARARGS, gc_set_debug__doc__},
894 {"get_debug", gc_get_debug, METH_VARARGS, gc_get_debug__doc__},
895 {"set_threshold", gc_set_thresh, METH_VARARGS, gc_set_thresh__doc__},
896 {"get_threshold", gc_get_thresh, METH_VARARGS, gc_get_thresh__doc__},
Neil Schemenauer544de1e2000-09-22 15:22:38 +0000897 {"collect", gc_collect, METH_VARARGS, gc_collect__doc__},
Neil Schemenauerc7c8d8e2001-08-09 15:58:59 +0000898 {"get_objects", gc_get_objects,METH_VARARGS, gc_get_objects__doc__},
Martin v. Löwis560da622001-11-24 09:24:51 +0000899 {"get_referrers", gc_get_referrers, METH_VARARGS,
900 gc_get_referrers__doc__},
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000901 {NULL, NULL} /* Sentinel */
902};
903
904void
905initgc(void)
906{
907 PyObject *m;
908 PyObject *d;
909
910 m = Py_InitModule4("gc",
911 GcMethods,
912 gc__doc__,
913 NULL,
914 PYTHON_API_VERSION);
915 d = PyModule_GetDict(m);
916 if (garbage == NULL) {
917 garbage = PyList_New(0);
918 }
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000919 PyDict_SetItemString(d, "garbage", garbage);
920 PyDict_SetItemString(d, "DEBUG_STATS",
921 PyInt_FromLong(DEBUG_STATS));
922 PyDict_SetItemString(d, "DEBUG_COLLECTABLE",
923 PyInt_FromLong(DEBUG_COLLECTABLE));
924 PyDict_SetItemString(d, "DEBUG_UNCOLLECTABLE",
925 PyInt_FromLong(DEBUG_UNCOLLECTABLE));
926 PyDict_SetItemString(d, "DEBUG_INSTANCES",
927 PyInt_FromLong(DEBUG_INSTANCES));
928 PyDict_SetItemString(d, "DEBUG_OBJECTS",
929 PyInt_FromLong(DEBUG_OBJECTS));
Neil Schemenauer544de1e2000-09-22 15:22:38 +0000930 PyDict_SetItemString(d, "DEBUG_SAVEALL",
931 PyInt_FromLong(DEBUG_SAVEALL));
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000932 PyDict_SetItemString(d, "DEBUG_LEAK",
933 PyInt_FromLong(DEBUG_LEAK));
934}
935
Neil Schemenauer43411b52001-08-30 00:05:51 +0000936/* for debugging */
937void _PyGC_Dump(PyGC_Head *g)
938{
939 _PyObject_Dump(FROM_GC(g));
940}
941
Neil Schemenauer43411b52001-08-30 00:05:51 +0000942/* extension modules might be compiled with GC support so these
943 functions must always be available */
944
Neil Schemenauerfec4eb12002-04-12 02:41:03 +0000945#undef PyObject_GC_Track
946#undef PyObject_GC_UnTrack
947#undef PyObject_GC_Del
948#undef _PyObject_GC_Malloc
949
Neil Schemenauer43411b52001-08-30 00:05:51 +0000950void
Neil Schemenauerfec4eb12002-04-12 02:41:03 +0000951PyObject_GC_Track(void *op)
Neil Schemenauer43411b52001-08-30 00:05:51 +0000952{
953 _PyObject_GC_TRACK(op);
954}
955
Neil Schemenauerfec4eb12002-04-12 02:41:03 +0000956/* for binary compatibility with 2.2 */
Neil Schemenauer43411b52001-08-30 00:05:51 +0000957void
Neil Schemenauerfec4eb12002-04-12 02:41:03 +0000958_PyObject_GC_Track(PyObject *op)
959{
960 PyObject_GC_Track(op);
961}
962
963void
964PyObject_GC_UnTrack(void *op)
Neil Schemenauer43411b52001-08-30 00:05:51 +0000965{
Tim Peters803526b2002-07-07 05:13:56 +0000966 /* Obscure: the Py_TRASHCAN mechanism requires that we be able to
967 * call PyObject_GC_UnTrack twice on an object.
968 */
Neil Schemenauera2b11ec2002-05-21 15:53:24 +0000969 if (IS_TRACKED(op))
Guido van Rossumff413af2002-03-28 20:34:59 +0000970 _PyObject_GC_UNTRACK(op);
Neil Schemenauer43411b52001-08-30 00:05:51 +0000971}
972
Neil Schemenauerfec4eb12002-04-12 02:41:03 +0000973/* for binary compatibility with 2.2 */
974void
975_PyObject_GC_UnTrack(PyObject *op)
976{
977 PyObject_GC_UnTrack(op);
978}
979
Neil Schemenauer43411b52001-08-30 00:05:51 +0000980PyObject *
Neil Schemenauerfec4eb12002-04-12 02:41:03 +0000981_PyObject_GC_Malloc(size_t basicsize)
Neil Schemenauer43411b52001-08-30 00:05:51 +0000982{
983 PyObject *op;
Neil Schemenauerfec4eb12002-04-12 02:41:03 +0000984 PyGC_Head *g = PyObject_MALLOC(sizeof(PyGC_Head) + basicsize);
Neil Schemenauer43411b52001-08-30 00:05:51 +0000985 if (g == NULL)
Jeremy Hylton8a135182002-06-06 23:23:55 +0000986 return PyErr_NoMemory();
Tim Petersea405632002-07-02 00:52:30 +0000987 g->gc.gc_refs = GC_UNTRACKED;
Neil Schemenauer2880ae52002-05-04 05:35:20 +0000988 generations[0].count++; /* number of allocated GC objects */
989 if (generations[0].count > generations[0].threshold &&
Neil Schemenauer43411b52001-08-30 00:05:51 +0000990 enabled &&
Neil Schemenauer2880ae52002-05-04 05:35:20 +0000991 generations[0].threshold &&
Neil Schemenauer43411b52001-08-30 00:05:51 +0000992 !collecting &&
993 !PyErr_Occurred()) {
994 collecting = 1;
Neil Schemenauer2880ae52002-05-04 05:35:20 +0000995 collect_generations();
Neil Schemenauer43411b52001-08-30 00:05:51 +0000996 collecting = 0;
997 }
998 op = FROM_GC(g);
Neil Schemenauer43411b52001-08-30 00:05:51 +0000999 return op;
1000}
1001
1002PyObject *
1003_PyObject_GC_New(PyTypeObject *tp)
1004{
Neil Schemenauerfec4eb12002-04-12 02:41:03 +00001005 PyObject *op = _PyObject_GC_Malloc(_PyObject_SIZE(tp));
Tim Petersfa8efab2002-04-28 01:57:25 +00001006 if (op != NULL)
1007 op = PyObject_INIT(op, tp);
1008 return op;
Neil Schemenauer43411b52001-08-30 00:05:51 +00001009}
1010
1011PyVarObject *
Tim Peters6d483d32001-10-06 21:27:34 +00001012_PyObject_GC_NewVar(PyTypeObject *tp, int nitems)
Neil Schemenauer43411b52001-08-30 00:05:51 +00001013{
Neil Schemenauerfec4eb12002-04-12 02:41:03 +00001014 const size_t size = _PyObject_VAR_SIZE(tp, nitems);
1015 PyVarObject *op = (PyVarObject *) _PyObject_GC_Malloc(size);
Tim Petersfa8efab2002-04-28 01:57:25 +00001016 if (op != NULL)
1017 op = PyObject_INIT_VAR(op, tp, nitems);
1018 return op;
Neil Schemenauer43411b52001-08-30 00:05:51 +00001019}
1020
1021PyVarObject *
Tim Peters6d483d32001-10-06 21:27:34 +00001022_PyObject_GC_Resize(PyVarObject *op, int nitems)
Neil Schemenauer43411b52001-08-30 00:05:51 +00001023{
Tim Petersf2a67da2001-10-07 03:54:51 +00001024 const size_t basicsize = _PyObject_VAR_SIZE(op->ob_type, nitems);
Neil Schemenauer43411b52001-08-30 00:05:51 +00001025 PyGC_Head *g = AS_GC(op);
Neil Schemenauerfec4eb12002-04-12 02:41:03 +00001026 g = PyObject_REALLOC(g, sizeof(PyGC_Head) + basicsize);
Neil Schemenauer43411b52001-08-30 00:05:51 +00001027 if (g == NULL)
1028 return (PyVarObject *)PyErr_NoMemory();
1029 op = (PyVarObject *) FROM_GC(g);
Tim Peters6d483d32001-10-06 21:27:34 +00001030 op->ob_size = nitems;
Neil Schemenauer43411b52001-08-30 00:05:51 +00001031 return op;
1032}
1033
1034void
Neil Schemenauerfec4eb12002-04-12 02:41:03 +00001035PyObject_GC_Del(void *op)
Neil Schemenauer43411b52001-08-30 00:05:51 +00001036{
Neil Schemenauer43411b52001-08-30 00:05:51 +00001037 PyGC_Head *g = AS_GC(op);
Neil Schemenauera2b11ec2002-05-21 15:53:24 +00001038 if (IS_TRACKED(op))
Neil Schemenauer43411b52001-08-30 00:05:51 +00001039 gc_list_remove(g);
Neil Schemenauer2880ae52002-05-04 05:35:20 +00001040 if (generations[0].count > 0) {
1041 generations[0].count--;
Neil Schemenauer43411b52001-08-30 00:05:51 +00001042 }
Neil Schemenauerfec4eb12002-04-12 02:41:03 +00001043 PyObject_FREE(g);
Neil Schemenauer43411b52001-08-30 00:05:51 +00001044}
1045
Neil Schemenauerfec4eb12002-04-12 02:41:03 +00001046/* for binary compatibility with 2.2 */
1047#undef _PyObject_GC_Del
1048void
1049_PyObject_GC_Del(PyObject *op)
1050{
1051 PyObject_GC_Del(op);
1052}