1 #ifndef Py_INTERNAL_PYMEM_H
2 #define Py_INTERNAL_PYMEM_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 "objimpl.h"
12 #include "pymem.h"
13
14
15 /* GC runtime state */
16
17 /* If we change this, we need to change the default value in the
18 signature of gc.collect. */
19 #define NUM_GENERATIONS 3
20
21 /*
22 NOTE: about the counting of long-lived objects.
23
24 To limit the cost of garbage collection, there are two strategies;
25 - make each collection faster, e.g. by scanning fewer objects
26 - do less collections
27 This heuristic is about the latter strategy.
28
29 In addition to the various configurable thresholds, we only trigger a
30 full collection if the ratio
31 long_lived_pending / long_lived_total
32 is above a given value (hardwired to 25%).
33
34 The reason is that, while "non-full" collections (i.e., collections of
35 the young and middle generations) will always examine roughly the same
36 number of objects -- determined by the aforementioned thresholds --,
37 the cost of a full collection is proportional to the total number of
38 long-lived objects, which is virtually unbounded.
39
40 Indeed, it has been remarked that doing a full collection every
41 <constant number> of object creations entails a dramatic performance
42 degradation in workloads which consist in creating and storing lots of
43 long-lived objects (e.g. building a large list of GC-tracked objects would
44 show quadratic performance, instead of linear as expected: see issue #4074).
45
46 Using the above ratio, instead, yields amortized linear performance in
47 the total number of objects (the effect of which can be summarized
48 thusly: "each full garbage collection is more and more costly as the
49 number of objects grows, but we do fewer and fewer of them").
50
51 This heuristic was suggested by Martin von Löwis on python-dev in
52 June 2008. His original analysis and proposal can be found at:
53 http://mail.python.org/pipermail/python-dev/2008-June/080579.html
54 */
55
56 /*
57 NOTE: about untracking of mutable objects.
58
59 Certain types of container cannot participate in a reference cycle, and
60 so do not need to be tracked by the garbage collector. Untracking these
61 objects reduces the cost of garbage collections. However, determining
62 which objects may be untracked is not free, and the costs must be
63 weighed against the benefits for garbage collection.
64
65 There are two possible strategies for when to untrack a container:
66
67 i) When the container is created.
68 ii) When the container is examined by the garbage collector.
69
70 Tuples containing only immutable objects (integers, strings etc, and
71 recursively, tuples of immutable objects) do not need to be tracked.
72 The interpreter creates a large number of tuples, many of which will
73 not survive until garbage collection. It is therefore not worthwhile
74 to untrack eligible tuples at creation time.
75
76 Instead, all tuples except the empty tuple are tracked when created.
77 During garbage collection it is determined whether any surviving tuples
78 can be untracked. A tuple can be untracked if all of its contents are
79 already not tracked. Tuples are examined for untracking in all garbage
80 collection cycles. It may take more than one cycle to untrack a tuple.
81
82 Dictionaries containing only immutable objects also do not need to be
83 tracked. Dictionaries are untracked when created. If a tracked item is
84 inserted into a dictionary (either as a key or value), the dictionary
85 becomes tracked. During a full garbage collection (all generations),
86 the collector will untrack any dictionaries whose contents are not
87 tracked.
88
89 The module provides the python function is_tracked(obj), which returns
90 the CURRENT tracking status of the object. Subsequent garbage
91 collections may change the tracking status of the object.
92
93 Untracking of certain containers was introduced in issue #4688, and
94 the algorithm was refined in response to issue #14775.
95 */
96
97 struct gc_generation {
98 PyGC_Head head;
99 int threshold; /* collection threshold */
100 int count; /* count of allocations or collections of younger
101 generations */
102 };
103
104 /* Running stats per generation */
105 struct gc_generation_stats {
106 /* total number of collections */
107 Py_ssize_t collections;
108 /* total number of collected objects */
109 Py_ssize_t collected;
110 /* total number of uncollectable objects (put into gc.garbage) */
111 Py_ssize_t uncollectable;
112 };
113
114 struct _gc_runtime_state {
115 /* List of objects that still need to be cleaned up, singly linked
116 * via their gc headers' gc_prev pointers. */
117 PyObject *trash_delete_later;
118 /* Current call-stack depth of tp_dealloc calls. */
119 int trash_delete_nesting;
120
121 int enabled;
122 int debug;
123 /* linked lists of container objects */
124 struct gc_generation generations[NUM_GENERATIONS];
125 PyGC_Head *generation0;
126 /* a permanent generation which won't be collected */
127 struct gc_generation permanent_generation;
128 struct gc_generation_stats generation_stats[NUM_GENERATIONS];
129 /* true if we are currently running the collector */
130 int collecting;
131 /* list of uncollectable objects */
132 PyObject *garbage;
133 /* a list of callbacks to be invoked when collection is performed */
134 PyObject *callbacks;
135 /* This is the number of objects that survived the last full
136 collection. It approximates the number of long lived objects
137 tracked by the GC.
138
139 (by "full collection", we mean a collection of the oldest
140 generation). */
141 Py_ssize_t long_lived_total;
142 /* This is the number of objects that survived all "non-full"
143 collections, and are awaiting to undergo a full collection for
144 the first time. */
145 Py_ssize_t long_lived_pending;
146 };
147
148 PyAPI_FUNC(void) _PyGC_Initialize(struct _gc_runtime_state *);
149
150
151 /* Set the memory allocator of the specified domain to the default.
152 Save the old allocator into *old_alloc if it's non-NULL.
153 Return on success, or return -1 if the domain is unknown. */
154 PyAPI_FUNC(int) _PyMem_SetDefaultAllocator(
155 PyMemAllocatorDomain domain,
156 PyMemAllocatorEx *old_alloc);
157
158 /* Special bytes broadcast into debug memory blocks at appropriate times.
159 Strings of these are unlikely to be valid addresses, floats, ints or
160 7-bit ASCII.
161
162 - PYMEM_CLEANBYTE: clean (newly allocated) memory
163 - PYMEM_DEADBYTE dead (newly freed) memory
164 - PYMEM_FORBIDDENBYTE: untouchable bytes at each end of a block
165
166 Byte patterns 0xCB, 0xDB and 0xFB have been replaced with 0xCD, 0xDD and
167 0xFD to use the same values than Windows CRT debug malloc() and free().
168 If modified, _PyMem_IsPtrFreed() should be updated as well. */
169 #define PYMEM_CLEANBYTE 0xCD
170 #define PYMEM_DEADBYTE 0xDD
171 #define PYMEM_FORBIDDENBYTE 0xFD
172
173 /* Heuristic checking if a pointer value is newly allocated
174 (uninitialized), newly freed or NULL (is equal to zero).
175
176 The pointer is not dereferenced, only the pointer value is checked.
177
178 The heuristic relies on the debug hooks on Python memory allocators which
179 fills newly allocated memory with CLEANBYTE (0xCD) and newly freed memory
180 with DEADBYTE (0xDD). Detect also "untouchable bytes" marked
181 with FORBIDDENBYTE (0xFD). */
_PyMem_IsPtrFreed(void * ptr)182 static inline int _PyMem_IsPtrFreed(void *ptr)
183 {
184 uintptr_t value = (uintptr_t)ptr;
185 #if SIZEOF_VOID_P == 8
186 return (value == 0
187 || value == (uintptr_t)0xCDCDCDCDCDCDCDCD
188 || value == (uintptr_t)0xDDDDDDDDDDDDDDDD
189 || value == (uintptr_t)0xFDFDFDFDFDFDFDFD);
190 #elif SIZEOF_VOID_P == 4
191 return (value == 0
192 || value == (uintptr_t)0xCDCDCDCD
193 || value == (uintptr_t)0xDDDDDDDD
194 || value == (uintptr_t)0xFDFDFDFD);
195 #else
196 # error "unknown pointer size"
197 #endif
198 }
199
200 PyAPI_FUNC(int) _PyMem_GetAllocatorName(
201 const char *name,
202 PyMemAllocatorName *allocator);
203
204 /* Configure the Python memory allocators.
205 Pass PYMEM_ALLOCATOR_DEFAULT to use default allocators.
206 PYMEM_ALLOCATOR_NOT_SET does nothing. */
207 PyAPI_FUNC(int) _PyMem_SetupAllocators(PyMemAllocatorName allocator);
208
209 #ifdef __cplusplus
210 }
211 #endif
212 #endif /* !Py_INTERNAL_PYMEM_H */
213