1 #ifndef Py_INTERNAL_GC_H
2 #define Py_INTERNAL_GC_H
3 #ifdef __cplusplus
4 extern "C" {
5 #endif
6
7 #ifndef Py_BUILD_CORE
8 # error "this header requires Py_BUILD_CORE define"
9 #endif
10
11 #include "pycore_freelist.h" // _PyFreeListState
12
13 /* GC information is stored BEFORE the object structure. */
14 typedef struct {
15 // Pointer to next object in the list.
16 // 0 means the object is not tracked
17 uintptr_t _gc_next;
18
19 // Pointer to previous object in the list.
20 // Lowest two bits are used for flags documented later.
21 uintptr_t _gc_prev;
22 } PyGC_Head;
23
24 #define _PyGC_Head_UNUSED PyGC_Head
25
26
27 /* Get an object's GC head */
_Py_AS_GC(PyObject * op)28 static inline PyGC_Head* _Py_AS_GC(PyObject *op) {
29 char *gc = ((char*)op) - sizeof(PyGC_Head);
30 return (PyGC_Head*)gc;
31 }
32
33 /* Get the object given the GC head */
_Py_FROM_GC(PyGC_Head * gc)34 static inline PyObject* _Py_FROM_GC(PyGC_Head *gc) {
35 char *op = ((char *)gc) + sizeof(PyGC_Head);
36 return (PyObject *)op;
37 }
38
39
40 /* Bit flags for ob_gc_bits (in Py_GIL_DISABLED builds)
41 *
42 * Setting the bits requires a relaxed store. The per-object lock must also be
43 * held, except when the object is only visible to a single thread (e.g. during
44 * object initialization or destruction).
45 *
46 * Reading the bits requires using a relaxed load, but does not require holding
47 * the per-object lock.
48 */
49 #ifdef Py_GIL_DISABLED
50 # define _PyGC_BITS_TRACKED (1) // Tracked by the GC
51 # define _PyGC_BITS_FINALIZED (2) // tp_finalize was called
52 # define _PyGC_BITS_UNREACHABLE (4)
53 # define _PyGC_BITS_FROZEN (8)
54 # define _PyGC_BITS_SHARED (16)
55 # define _PyGC_BITS_SHARED_INLINE (32)
56 # define _PyGC_BITS_DEFERRED (64) // Use deferred reference counting
57 #endif
58
59 #ifdef Py_GIL_DISABLED
60
61 static inline void
_PyObject_SET_GC_BITS(PyObject * op,uint8_t new_bits)62 _PyObject_SET_GC_BITS(PyObject *op, uint8_t new_bits)
63 {
64 uint8_t bits = _Py_atomic_load_uint8_relaxed(&op->ob_gc_bits);
65 _Py_atomic_store_uint8_relaxed(&op->ob_gc_bits, bits | new_bits);
66 }
67
68 static inline int
_PyObject_HAS_GC_BITS(PyObject * op,uint8_t bits)69 _PyObject_HAS_GC_BITS(PyObject *op, uint8_t bits)
70 {
71 return (_Py_atomic_load_uint8_relaxed(&op->ob_gc_bits) & bits) != 0;
72 }
73
74 static inline void
_PyObject_CLEAR_GC_BITS(PyObject * op,uint8_t bits_to_clear)75 _PyObject_CLEAR_GC_BITS(PyObject *op, uint8_t bits_to_clear)
76 {
77 uint8_t bits = _Py_atomic_load_uint8_relaxed(&op->ob_gc_bits);
78 _Py_atomic_store_uint8_relaxed(&op->ob_gc_bits, bits & ~bits_to_clear);
79 }
80
81 #endif
82
83 /* True if the object is currently tracked by the GC. */
_PyObject_GC_IS_TRACKED(PyObject * op)84 static inline int _PyObject_GC_IS_TRACKED(PyObject *op) {
85 #ifdef Py_GIL_DISABLED
86 return _PyObject_HAS_GC_BITS(op, _PyGC_BITS_TRACKED);
87 #else
88 PyGC_Head *gc = _Py_AS_GC(op);
89 return (gc->_gc_next != 0);
90 #endif
91 }
92 #define _PyObject_GC_IS_TRACKED(op) _PyObject_GC_IS_TRACKED(_Py_CAST(PyObject*, op))
93
94 /* True if the object may be tracked by the GC in the future, or already is.
95 This can be useful to implement some optimizations. */
_PyObject_GC_MAY_BE_TRACKED(PyObject * obj)96 static inline int _PyObject_GC_MAY_BE_TRACKED(PyObject *obj) {
97 if (!PyObject_IS_GC(obj)) {
98 return 0;
99 }
100 if (PyTuple_CheckExact(obj)) {
101 return _PyObject_GC_IS_TRACKED(obj);
102 }
103 return 1;
104 }
105
106 #ifdef Py_GIL_DISABLED
107
108 /* True if memory the object references is shared between
109 * multiple threads and needs special purpose when freeing
110 * those references due to the possibility of in-flight
111 * lock-free reads occurring. The object is responsible
112 * for calling _PyMem_FreeDelayed on the referenced
113 * memory. */
_PyObject_GC_IS_SHARED(PyObject * op)114 static inline int _PyObject_GC_IS_SHARED(PyObject *op) {
115 return _PyObject_HAS_GC_BITS(op, _PyGC_BITS_SHARED);
116 }
117 #define _PyObject_GC_IS_SHARED(op) _PyObject_GC_IS_SHARED(_Py_CAST(PyObject*, op))
118
_PyObject_GC_SET_SHARED(PyObject * op)119 static inline void _PyObject_GC_SET_SHARED(PyObject *op) {
120 _PyObject_SET_GC_BITS(op, _PyGC_BITS_SHARED);
121 }
122 #define _PyObject_GC_SET_SHARED(op) _PyObject_GC_SET_SHARED(_Py_CAST(PyObject*, op))
123
124 /* True if the memory of the object is shared between multiple
125 * threads and needs special purpose when freeing due to
126 * the possibility of in-flight lock-free reads occurring.
127 * Objects with this bit that are GC objects will automatically
128 * delay-freed by PyObject_GC_Del. */
_PyObject_GC_IS_SHARED_INLINE(PyObject * op)129 static inline int _PyObject_GC_IS_SHARED_INLINE(PyObject *op) {
130 return _PyObject_HAS_GC_BITS(op, _PyGC_BITS_SHARED_INLINE);
131 }
132 #define _PyObject_GC_IS_SHARED_INLINE(op) \
133 _PyObject_GC_IS_SHARED_INLINE(_Py_CAST(PyObject*, op))
134
_PyObject_GC_SET_SHARED_INLINE(PyObject * op)135 static inline void _PyObject_GC_SET_SHARED_INLINE(PyObject *op) {
136 _PyObject_SET_GC_BITS(op, _PyGC_BITS_SHARED_INLINE);
137 }
138 #define _PyObject_GC_SET_SHARED_INLINE(op) \
139 _PyObject_GC_SET_SHARED_INLINE(_Py_CAST(PyObject*, op))
140
141 #endif
142
143 /* Bit flags for _gc_prev */
144 /* Bit 0 is set when tp_finalize is called */
145 #define _PyGC_PREV_MASK_FINALIZED (1)
146 /* Bit 1 is set when the object is in generation which is GCed currently. */
147 #define _PyGC_PREV_MASK_COLLECTING (2)
148 /* The (N-2) most significant bits contain the real address. */
149 #define _PyGC_PREV_SHIFT (2)
150 #define _PyGC_PREV_MASK (((uintptr_t) -1) << _PyGC_PREV_SHIFT)
151
152 /* set for debugging information */
153 #define _PyGC_DEBUG_STATS (1<<0) /* print collection statistics */
154 #define _PyGC_DEBUG_COLLECTABLE (1<<1) /* print collectable objects */
155 #define _PyGC_DEBUG_UNCOLLECTABLE (1<<2) /* print uncollectable objects */
156 #define _PyGC_DEBUG_SAVEALL (1<<5) /* save all garbage in gc.garbage */
157 #define _PyGC_DEBUG_LEAK _PyGC_DEBUG_COLLECTABLE | \
158 _PyGC_DEBUG_UNCOLLECTABLE | \
159 _PyGC_DEBUG_SAVEALL
160
161 typedef enum {
162 // GC was triggered by heap allocation
163 _Py_GC_REASON_HEAP,
164
165 // GC was called during shutdown
166 _Py_GC_REASON_SHUTDOWN,
167
168 // GC was called by gc.collect() or PyGC_Collect()
169 _Py_GC_REASON_MANUAL
170 } _PyGC_Reason;
171
172 // Lowest bit of _gc_next is used for flags only in GC.
173 // But it is always 0 for normal code.
_PyGCHead_NEXT(PyGC_Head * gc)174 static inline PyGC_Head* _PyGCHead_NEXT(PyGC_Head *gc) {
175 uintptr_t next = gc->_gc_next;
176 return (PyGC_Head*)next;
177 }
_PyGCHead_SET_NEXT(PyGC_Head * gc,PyGC_Head * next)178 static inline void _PyGCHead_SET_NEXT(PyGC_Head *gc, PyGC_Head *next) {
179 gc->_gc_next = (uintptr_t)next;
180 }
181
182 // Lowest two bits of _gc_prev is used for _PyGC_PREV_MASK_* flags.
_PyGCHead_PREV(PyGC_Head * gc)183 static inline PyGC_Head* _PyGCHead_PREV(PyGC_Head *gc) {
184 uintptr_t prev = (gc->_gc_prev & _PyGC_PREV_MASK);
185 return (PyGC_Head*)prev;
186 }
_PyGCHead_SET_PREV(PyGC_Head * gc,PyGC_Head * prev)187 static inline void _PyGCHead_SET_PREV(PyGC_Head *gc, PyGC_Head *prev) {
188 uintptr_t uprev = (uintptr_t)prev;
189 assert((uprev & ~_PyGC_PREV_MASK) == 0);
190 gc->_gc_prev = ((gc->_gc_prev & ~_PyGC_PREV_MASK) | uprev);
191 }
192
_PyGC_FINALIZED(PyObject * op)193 static inline int _PyGC_FINALIZED(PyObject *op) {
194 #ifdef Py_GIL_DISABLED
195 return _PyObject_HAS_GC_BITS(op, _PyGC_BITS_FINALIZED);
196 #else
197 PyGC_Head *gc = _Py_AS_GC(op);
198 return ((gc->_gc_prev & _PyGC_PREV_MASK_FINALIZED) != 0);
199 #endif
200 }
_PyGC_SET_FINALIZED(PyObject * op)201 static inline void _PyGC_SET_FINALIZED(PyObject *op) {
202 #ifdef Py_GIL_DISABLED
203 _PyObject_SET_GC_BITS(op, _PyGC_BITS_FINALIZED);
204 #else
205 PyGC_Head *gc = _Py_AS_GC(op);
206 gc->_gc_prev |= _PyGC_PREV_MASK_FINALIZED;
207 #endif
208 }
_PyGC_CLEAR_FINALIZED(PyObject * op)209 static inline void _PyGC_CLEAR_FINALIZED(PyObject *op) {
210 #ifdef Py_GIL_DISABLED
211 _PyObject_CLEAR_GC_BITS(op, _PyGC_BITS_FINALIZED);
212 #else
213 PyGC_Head *gc = _Py_AS_GC(op);
214 gc->_gc_prev &= ~_PyGC_PREV_MASK_FINALIZED;
215 #endif
216 }
217
218
219 /* GC runtime state */
220
221 /* If we change this, we need to change the default value in the
222 signature of gc.collect. */
223 #define NUM_GENERATIONS 3
224 /*
225 NOTE: about untracking of mutable objects.
226
227 Certain types of container cannot participate in a reference cycle, and
228 so do not need to be tracked by the garbage collector. Untracking these
229 objects reduces the cost of garbage collections. However, determining
230 which objects may be untracked is not free, and the costs must be
231 weighed against the benefits for garbage collection.
232
233 There are two possible strategies for when to untrack a container:
234
235 i) When the container is created.
236 ii) When the container is examined by the garbage collector.
237
238 Tuples containing only immutable objects (integers, strings etc, and
239 recursively, tuples of immutable objects) do not need to be tracked.
240 The interpreter creates a large number of tuples, many of which will
241 not survive until garbage collection. It is therefore not worthwhile
242 to untrack eligible tuples at creation time.
243
244 Instead, all tuples except the empty tuple are tracked when created.
245 During garbage collection it is determined whether any surviving tuples
246 can be untracked. A tuple can be untracked if all of its contents are
247 already not tracked. Tuples are examined for untracking in all garbage
248 collection cycles. It may take more than one cycle to untrack a tuple.
249
250 Dictionaries containing only immutable objects also do not need to be
251 tracked. Dictionaries are untracked when created. If a tracked item is
252 inserted into a dictionary (either as a key or value), the dictionary
253 becomes tracked. During a full garbage collection (all generations),
254 the collector will untrack any dictionaries whose contents are not
255 tracked.
256
257 The module provides the python function is_tracked(obj), which returns
258 the CURRENT tracking status of the object. Subsequent garbage
259 collections may change the tracking status of the object.
260
261 Untracking of certain containers was introduced in issue #4688, and
262 the algorithm was refined in response to issue #14775.
263 */
264
265 struct gc_generation {
266 PyGC_Head head;
267 int threshold; /* collection threshold */
268 int count; /* count of allocations or collections of younger
269 generations */
270 };
271
272 /* Running stats per generation */
273 struct gc_generation_stats {
274 /* total number of collections */
275 Py_ssize_t collections;
276 /* total number of collected objects */
277 Py_ssize_t collected;
278 /* total number of uncollectable objects (put into gc.garbage) */
279 Py_ssize_t uncollectable;
280 };
281
282 struct _gc_runtime_state {
283 /* List of objects that still need to be cleaned up, singly linked
284 * via their gc headers' gc_prev pointers. */
285 PyObject *trash_delete_later;
286 /* Current call-stack depth of tp_dealloc calls. */
287 int trash_delete_nesting;
288
289 /* Is automatic collection enabled? */
290 int enabled;
291 int debug;
292 /* linked lists of container objects */
293 struct gc_generation generations[NUM_GENERATIONS];
294 PyGC_Head *generation0;
295 /* a permanent generation which won't be collected */
296 struct gc_generation permanent_generation;
297 struct gc_generation_stats generation_stats[NUM_GENERATIONS];
298 /* true if we are currently running the collector */
299 int collecting;
300 /* list of uncollectable objects */
301 PyObject *garbage;
302 /* a list of callbacks to be invoked when collection is performed */
303 PyObject *callbacks;
304
305 /* This is the number of objects that survived the last full
306 collection. It approximates the number of long lived objects
307 tracked by the GC.
308
309 (by "full collection", we mean a collection of the oldest
310 generation). */
311 Py_ssize_t long_lived_total;
312 /* This is the number of objects that survived all "non-full"
313 collections, and are awaiting to undergo a full collection for
314 the first time. */
315 Py_ssize_t long_lived_pending;
316
317 #ifdef Py_GIL_DISABLED
318 /* gh-117783: Deferred reference counting is not fully implemented yet, so
319 as a temporary measure we treat objects using deferred reference
320 counting as immortal. The value may be zero, one, or a negative number:
321 0: immortalize deferred RC objects once the first thread is created
322 1: immortalize all deferred RC objects immediately
323 <0: suppressed; don't immortalize objects */
324 int immortalize;
325 #endif
326 };
327
328 #ifdef Py_GIL_DISABLED
329 struct _gc_thread_state {
330 /* Thread-local allocation count. */
331 Py_ssize_t alloc_count;
332 };
333 #endif
334
335
336 extern void _PyGC_InitState(struct _gc_runtime_state *);
337
338 extern Py_ssize_t _PyGC_Collect(PyThreadState *tstate, int generation,
339 _PyGC_Reason reason);
340 extern void _PyGC_CollectNoFail(PyThreadState *tstate);
341
342 /* Freeze objects tracked by the GC and ignore them in future collections. */
343 extern void _PyGC_Freeze(PyInterpreterState *interp);
344 /* Unfreezes objects placing them in the oldest generation */
345 extern void _PyGC_Unfreeze(PyInterpreterState *interp);
346 /* Number of frozen objects */
347 extern Py_ssize_t _PyGC_GetFreezeCount(PyInterpreterState *interp);
348
349 extern PyObject *_PyGC_GetObjects(PyInterpreterState *interp, int generation);
350 extern PyObject *_PyGC_GetReferrers(PyInterpreterState *interp, PyObject *objs);
351
352 // Functions to clear types free lists
353 extern void _PyGC_ClearAllFreeLists(PyInterpreterState *interp);
354 extern void _Py_ScheduleGC(PyThreadState *tstate);
355 extern void _Py_RunGC(PyThreadState *tstate);
356
357 #ifdef Py_GIL_DISABLED
358 // gh-117783: Immortalize objects that use deferred reference counting
359 extern void _PyGC_ImmortalizeDeferredObjects(PyInterpreterState *interp);
360 #endif
361
362 #ifdef __cplusplus
363 }
364 #endif
365 #endif /* !Py_INTERNAL_GC_H */
366