Python code coverage for Modules/gcmodule.c

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