Python code coverage for Objects/obmalloc.c

#	count	content
1	n/a	#include "Python.h"
2	n/a
3	n/a	#include <stdbool.h>
4	n/a
5	n/a
6	n/a	/* Defined in tracemalloc.c */
7	n/a	extern void _PyMem_DumpTraceback(int fd, const void *ptr);
8	n/a
9	n/a
10	n/a	/* Python's malloc wrappers (see pymem.h) */
11	n/a
12	n/a	#undef uint
13	n/a	#define uint unsigned int /* assuming >= 16 bits */
14	n/a
15	n/a	/* Forward declaration */
16	n/a	static void* _PyMem_DebugRawMalloc(void *ctx, size_t size);
17	n/a	static void* _PyMem_DebugRawCalloc(void *ctx, size_t nelem, size_t elsize);
18	n/a	static void* _PyMem_DebugRawRealloc(void ctx, void ptr, size_t size);
19	n/a	static void _PyMem_DebugRawFree(void ctx, void p);
20	n/a
21	n/a	static void* _PyMem_DebugMalloc(void *ctx, size_t size);
22	n/a	static void* _PyMem_DebugCalloc(void *ctx, size_t nelem, size_t elsize);
23	n/a	static void* _PyMem_DebugRealloc(void ctx, void ptr, size_t size);
24	n/a	static void _PyMem_DebugFree(void ctx, void p);
25	n/a
26	n/a	static void _PyObject_DebugDumpAddress(const void *p);
27	n/a	static void _PyMem_DebugCheckAddress(char api_id, const void *p);
28	n/a
29	n/a	#if defined(__has_feature) /* Clang */
30	n/a	#if __has_feature(address_sanitizer) /* is ASAN enabled? */
31	n/a	#define ATTRIBUTE_NO_ADDRESS_SAFETY_ANALYSIS \
32	n/a	__attribute__((no_address_safety_analysis))
33	n/a	#else
34	n/a	#define ATTRIBUTE_NO_ADDRESS_SAFETY_ANALYSIS
35	n/a	#endif
36	n/a	#else
37	n/a	#if defined(__SANITIZE_ADDRESS__) /* GCC 4.8.x, is ASAN enabled? */
38	n/a	#define ATTRIBUTE_NO_ADDRESS_SAFETY_ANALYSIS \
39	n/a	__attribute__((no_address_safety_analysis))
40	n/a	#else
41	n/a	#define ATTRIBUTE_NO_ADDRESS_SAFETY_ANALYSIS
42	n/a	#endif
43	n/a	#endif
44	n/a
45	n/a	#ifdef WITH_PYMALLOC
46	n/a
47	n/a	#ifdef MS_WINDOWS
48	n/a	# include <windows.h>
49	n/a	#elif defined(HAVE_MMAP)
50	n/a	# include <sys/mman.h>
51	n/a	# ifdef MAP_ANONYMOUS
52	n/a	# define ARENAS_USE_MMAP
53	n/a	# endif
54	n/a	#endif
55	n/a
56	n/a	/* Forward declaration */
57	n/a	static void* _PyObject_Malloc(void *ctx, size_t size);
58	n/a	static void* _PyObject_Calloc(void *ctx, size_t nelem, size_t elsize);
59	n/a	static void _PyObject_Free(void ctx, void p);
60	n/a	static void* _PyObject_Realloc(void ctx, void ptr, size_t size);
61	n/a	#endif
62	n/a
63	n/a
64	n/a	static void *
65	n/a	_PyMem_RawMalloc(void *ctx, size_t size)
66	n/a	{
67	n/a	/* PyMem_RawMalloc(0) means malloc(1). Some systems would return NULL
68	n/a	for malloc(0), which would be treated as an error. Some platforms would
69	n/a	return a pointer with no memory behind it, which would break pymalloc.
70	n/a	To solve these problems, allocate an extra byte. */
71	n/a	if (size == 0)
72	n/a	size = 1;
73	n/a	return malloc(size);
74	n/a	}
75	n/a
76	n/a	static void *
77	n/a	_PyMem_RawCalloc(void *ctx, size_t nelem, size_t elsize)
78	n/a	{
79	n/a	/* PyMem_RawCalloc(0, 0) means calloc(1, 1). Some systems would return NULL
80	n/a	for calloc(0, 0), which would be treated as an error. Some platforms
81	n/a	would return a pointer with no memory behind it, which would break
82	n/a	pymalloc. To solve these problems, allocate an extra byte. */
83	n/a	if (nelem == 0 \|\| elsize == 0) {
84	n/a	nelem = 1;
85	n/a	elsize = 1;
86	n/a	}
87	n/a	return calloc(nelem, elsize);
88	n/a	}
89	n/a
90	n/a	static void *
91	n/a	_PyMem_RawRealloc(void ctx, void ptr, size_t size)
92	n/a	{
93	n/a	if (size == 0)
94	n/a	size = 1;
95	n/a	return realloc(ptr, size);
96	n/a	}
97	n/a
98	n/a	static void
99	n/a	_PyMem_RawFree(void ctx, void ptr)
100	n/a	{
101	n/a	free(ptr);
102	n/a	}
103	n/a
104	n/a
105	n/a	#ifdef MS_WINDOWS
106	n/a	static void *
107	n/a	_PyObject_ArenaVirtualAlloc(void *ctx, size_t size)
108	n/a	{
109	n/a	return VirtualAlloc(NULL, size,
110	n/a	MEM_COMMIT \| MEM_RESERVE, PAGE_READWRITE);
111	n/a	}
112	n/a
113	n/a	static void
114	n/a	_PyObject_ArenaVirtualFree(void ctx, void ptr, size_t size)
115	n/a	{
116	n/a	VirtualFree(ptr, 0, MEM_RELEASE);
117	n/a	}
118	n/a
119	n/a	#elif defined(ARENAS_USE_MMAP)
120	n/a	static void *
121	n/a	_PyObject_ArenaMmap(void *ctx, size_t size)
122	n/a	{
123	n/a	void *ptr;
124	n/a	ptr = mmap(NULL, size, PROT_READ\|PROT_WRITE,
125	n/a	MAP_PRIVATE\|MAP_ANONYMOUS, -1, 0);
126	n/a	if (ptr == MAP_FAILED)
127	n/a	return NULL;
128	n/a	assert(ptr != NULL);
129	n/a	return ptr;
130	n/a	}
131	n/a
132	n/a	static void
133	n/a	_PyObject_ArenaMunmap(void ctx, void ptr, size_t size)
134	n/a	{
135	n/a	munmap(ptr, size);
136	n/a	}
137	n/a
138	n/a	#else
139	n/a	static void *
140	n/a	_PyObject_ArenaMalloc(void *ctx, size_t size)
141	n/a	{
142	n/a	return malloc(size);
143	n/a	}
144	n/a
145	n/a	static void
146	n/a	_PyObject_ArenaFree(void ctx, void ptr, size_t size)
147	n/a	{
148	n/a	free(ptr);
149	n/a	}
150	n/a	#endif
151	n/a
152	n/a
153	n/a	#define PYRAW_FUNCS _PyMem_RawMalloc, _PyMem_RawCalloc, _PyMem_RawRealloc, _PyMem_RawFree
154	n/a	#ifdef WITH_PYMALLOC
155	n/a	# define PYOBJ_FUNCS _PyObject_Malloc, _PyObject_Calloc, _PyObject_Realloc, _PyObject_Free
156	n/a	#else
157	n/a	# define PYOBJ_FUNCS PYRAW_FUNCS
158	n/a	#endif
159	n/a	#define PYMEM_FUNCS PYOBJ_FUNCS
160	n/a
161	n/a	typedef struct {
162	n/a	/* We tag each block with an API ID in order to tag API violations */
163	n/a	char api_id;
164	n/a	PyMemAllocatorEx alloc;
165	n/a	} debug_alloc_api_t;
166	n/a	static struct {
167	n/a	debug_alloc_api_t raw;
168	n/a	debug_alloc_api_t mem;
169	n/a	debug_alloc_api_t obj;
170	n/a	} _PyMem_Debug = {
171	n/a	{'r', {NULL, PYRAW_FUNCS}},
172	n/a	{'m', {NULL, PYMEM_FUNCS}},
173	n/a	{'o', {NULL, PYOBJ_FUNCS}}
174	n/a	};
175	n/a
176	n/a	#define PYRAWDBG_FUNCS \
177	n/a	_PyMem_DebugRawMalloc, _PyMem_DebugRawCalloc, _PyMem_DebugRawRealloc, _PyMem_DebugRawFree
178	n/a	#define PYDBG_FUNCS \
179	n/a	_PyMem_DebugMalloc, _PyMem_DebugCalloc, _PyMem_DebugRealloc, _PyMem_DebugFree
180	n/a
181	n/a	static PyMemAllocatorEx _PyMem_Raw = {
182	n/a	#ifdef Py_DEBUG
183	n/a	&_PyMem_Debug.raw, PYRAWDBG_FUNCS
184	n/a	#else
185	n/a	NULL, PYRAW_FUNCS
186	n/a	#endif
187	n/a	};
188	n/a
189	n/a	static PyMemAllocatorEx _PyMem = {
190	n/a	#ifdef Py_DEBUG
191	n/a	&_PyMem_Debug.mem, PYDBG_FUNCS
192	n/a	#else
193	n/a	NULL, PYMEM_FUNCS
194	n/a	#endif
195	n/a	};
196	n/a
197	n/a	static PyMemAllocatorEx _PyObject = {
198	n/a	#ifdef Py_DEBUG
199	n/a	&_PyMem_Debug.obj, PYDBG_FUNCS
200	n/a	#else
201	n/a	NULL, PYOBJ_FUNCS
202	n/a	#endif
203	n/a	};
204	n/a
205	n/a	int
206	n/a	_PyMem_SetupAllocators(const char *opt)
207	n/a	{
208	n/a	if (opt == NULL \|\| *opt == '\0') {
209	n/a	/* PYTHONMALLOC is empty or is not set or ignored (-E/-I command line
210	n/a	options): use default allocators */
211	n/a	#ifdef Py_DEBUG
212	n/a	# ifdef WITH_PYMALLOC
213	n/a	opt = "pymalloc_debug";
214	n/a	# else
215	n/a	opt = "malloc_debug";
216	n/a	# endif
217	n/a	#else
218	n/a	/* !Py_DEBUG */
219	n/a	# ifdef WITH_PYMALLOC
220	n/a	opt = "pymalloc";
221	n/a	# else
222	n/a	opt = "malloc";
223	n/a	# endif
224	n/a	#endif
225	n/a	}
226	n/a
227	n/a	if (strcmp(opt, "debug") == 0) {
228	n/a	PyMem_SetupDebugHooks();
229	n/a	}
230	n/a	else if (strcmp(opt, "malloc") == 0 \|\| strcmp(opt, "malloc_debug") == 0)
231	n/a	{
232	n/a	PyMemAllocatorEx alloc = {NULL, PYRAW_FUNCS};
233	n/a
234	n/a	PyMem_SetAllocator(PYMEM_DOMAIN_RAW, &alloc);
235	n/a	PyMem_SetAllocator(PYMEM_DOMAIN_MEM, &alloc);
236	n/a	PyMem_SetAllocator(PYMEM_DOMAIN_OBJ, &alloc);
237	n/a
238	n/a	if (strcmp(opt, "malloc_debug") == 0)
239	n/a	PyMem_SetupDebugHooks();
240	n/a	}
241	n/a	#ifdef WITH_PYMALLOC
242	n/a	else if (strcmp(opt, "pymalloc") == 0
243	n/a	\|\| strcmp(opt, "pymalloc_debug") == 0)
244	n/a	{
245	n/a	PyMemAllocatorEx raw_alloc = {NULL, PYRAW_FUNCS};
246	n/a	PyMemAllocatorEx mem_alloc = {NULL, PYMEM_FUNCS};
247	n/a	PyMemAllocatorEx obj_alloc = {NULL, PYOBJ_FUNCS};
248	n/a
249	n/a	PyMem_SetAllocator(PYMEM_DOMAIN_RAW, &raw_alloc);
250	n/a	PyMem_SetAllocator(PYMEM_DOMAIN_MEM, &mem_alloc);
251	n/a	PyMem_SetAllocator(PYMEM_DOMAIN_OBJ, &obj_alloc);
252	n/a
253	n/a	if (strcmp(opt, "pymalloc_debug") == 0)
254	n/a	PyMem_SetupDebugHooks();
255	n/a	}
256	n/a	#endif
257	n/a	else {
258	n/a	/* unknown allocator */
259	n/a	return -1;
260	n/a	}
261	n/a	return 0;
262	n/a	}
263	n/a
264	n/a	#undef PYRAW_FUNCS
265	n/a	#undef PYMEM_FUNCS
266	n/a	#undef PYOBJ_FUNCS
267	n/a	#undef PYRAWDBG_FUNCS
268	n/a	#undef PYDBG_FUNCS
269	n/a
270	n/a	static PyObjectArenaAllocator _PyObject_Arena = {NULL,
271	n/a	#ifdef MS_WINDOWS
272	n/a	_PyObject_ArenaVirtualAlloc, _PyObject_ArenaVirtualFree
273	n/a	#elif defined(ARENAS_USE_MMAP)
274	n/a	_PyObject_ArenaMmap, _PyObject_ArenaMunmap
275	n/a	#else
276	n/a	_PyObject_ArenaMalloc, _PyObject_ArenaFree
277	n/a	#endif
278	n/a	};
279	n/a
280	n/a	#ifdef WITH_PYMALLOC
281	n/a	static int
282	n/a	_PyMem_DebugEnabled(void)
283	n/a	{
284	n/a	return (_PyObject.malloc == _PyMem_DebugMalloc);
285	n/a	}
286	n/a
287	n/a	int
288	n/a	_PyMem_PymallocEnabled(void)
289	n/a	{
290	n/a	if (_PyMem_DebugEnabled()) {
291	n/a	return (_PyMem_Debug.obj.alloc.malloc == _PyObject_Malloc);
292	n/a	}
293	n/a	else {
294	n/a	return (_PyObject.malloc == _PyObject_Malloc);
295	n/a	}
296	n/a	}
297	n/a	#endif
298	n/a
299	n/a	void
300	n/a	PyMem_SetupDebugHooks(void)
301	n/a	{
302	n/a	PyMemAllocatorEx alloc;
303	n/a
304	n/a	alloc.malloc = _PyMem_DebugRawMalloc;
305	n/a	alloc.calloc = _PyMem_DebugRawCalloc;
306	n/a	alloc.realloc = _PyMem_DebugRawRealloc;
307	n/a	alloc.free = _PyMem_DebugRawFree;
308	n/a
309	n/a	if (_PyMem_Raw.malloc != _PyMem_DebugRawMalloc) {
310	n/a	alloc.ctx = &_PyMem_Debug.raw;
311	n/a	PyMem_GetAllocator(PYMEM_DOMAIN_RAW, &_PyMem_Debug.raw.alloc);
312	n/a	PyMem_SetAllocator(PYMEM_DOMAIN_RAW, &alloc);
313	n/a	}
314	n/a
315	n/a	alloc.malloc = _PyMem_DebugMalloc;
316	n/a	alloc.calloc = _PyMem_DebugCalloc;
317	n/a	alloc.realloc = _PyMem_DebugRealloc;
318	n/a	alloc.free = _PyMem_DebugFree;
319	n/a
320	n/a	if (_PyMem.malloc != _PyMem_DebugMalloc) {
321	n/a	alloc.ctx = &_PyMem_Debug.mem;
322	n/a	PyMem_GetAllocator(PYMEM_DOMAIN_MEM, &_PyMem_Debug.mem.alloc);
323	n/a	PyMem_SetAllocator(PYMEM_DOMAIN_MEM, &alloc);
324	n/a	}
325	n/a
326	n/a	if (_PyObject.malloc != _PyMem_DebugMalloc) {
327	n/a	alloc.ctx = &_PyMem_Debug.obj;
328	n/a	PyMem_GetAllocator(PYMEM_DOMAIN_OBJ, &_PyMem_Debug.obj.alloc);
329	n/a	PyMem_SetAllocator(PYMEM_DOMAIN_OBJ, &alloc);
330	n/a	}
331	n/a	}
332	n/a
333	n/a	void
334	n/a	PyMem_GetAllocator(PyMemAllocatorDomain domain, PyMemAllocatorEx *allocator)
335	n/a	{
336	n/a	switch(domain)
337	n/a	{
338	n/a	case PYMEM_DOMAIN_RAW: *allocator = _PyMem_Raw; break;
339	n/a	case PYMEM_DOMAIN_MEM: *allocator = _PyMem; break;
340	n/a	case PYMEM_DOMAIN_OBJ: *allocator = _PyObject; break;
341	n/a	default:
342	n/a	/* unknown domain: set all attributes to NULL */
343	n/a	allocator->ctx = NULL;
344	n/a	allocator->malloc = NULL;
345	n/a	allocator->calloc = NULL;
346	n/a	allocator->realloc = NULL;
347	n/a	allocator->free = NULL;
348	n/a	}
349	n/a	}
350	n/a
351	n/a	void
352	n/a	PyMem_SetAllocator(PyMemAllocatorDomain domain, PyMemAllocatorEx *allocator)
353	n/a	{
354	n/a	switch(domain)
355	n/a	{
356	n/a	case PYMEM_DOMAIN_RAW: _PyMem_Raw = *allocator; break;
357	n/a	case PYMEM_DOMAIN_MEM: _PyMem = *allocator; break;
358	n/a	case PYMEM_DOMAIN_OBJ: _PyObject = *allocator; break;
359	n/a	/* ignore unknown domain */
360	n/a	}
361	n/a	}
362	n/a
363	n/a	void
364	n/a	PyObject_GetArenaAllocator(PyObjectArenaAllocator *allocator)
365	n/a	{
366	n/a	*allocator = _PyObject_Arena;
367	n/a	}
368	n/a
369	n/a	void
370	n/a	PyObject_SetArenaAllocator(PyObjectArenaAllocator *allocator)
371	n/a	{
372	n/a	_PyObject_Arena = *allocator;
373	n/a	}
374	n/a
375	n/a	void *
376	n/a	PyMem_RawMalloc(size_t size)
377	n/a	{
378	n/a	/*
379	n/a	* Limit ourselves to PY_SSIZE_T_MAX bytes to prevent security holes.
380	n/a	* Most python internals blindly use a signed Py_ssize_t to track
381	n/a	* things without checking for overflows or negatives.
382	n/a	* As size_t is unsigned, checking for size < 0 is not required.
383	n/a	*/
384	n/a	if (size > (size_t)PY_SSIZE_T_MAX)
385	n/a	return NULL;
386	n/a	return _PyMem_Raw.malloc(_PyMem_Raw.ctx, size);
387	n/a	}
388	n/a
389	n/a	void *
390	n/a	PyMem_RawCalloc(size_t nelem, size_t elsize)
391	n/a	{
392	n/a	/* see PyMem_RawMalloc() */
393	n/a	if (elsize != 0 && nelem > (size_t)PY_SSIZE_T_MAX / elsize)
394	n/a	return NULL;
395	n/a	return _PyMem_Raw.calloc(_PyMem_Raw.ctx, nelem, elsize);
396	n/a	}
397	n/a
398	n/a	void*
399	n/a	PyMem_RawRealloc(void *ptr, size_t new_size)
400	n/a	{
401	n/a	/* see PyMem_RawMalloc() */
402	n/a	if (new_size > (size_t)PY_SSIZE_T_MAX)
403	n/a	return NULL;
404	n/a	return _PyMem_Raw.realloc(_PyMem_Raw.ctx, ptr, new_size);
405	n/a	}
406	n/a
407	n/a	void PyMem_RawFree(void *ptr)
408	n/a	{
409	n/a	_PyMem_Raw.free(_PyMem_Raw.ctx, ptr);
410	n/a	}
411	n/a
412	n/a	void *
413	n/a	PyMem_Malloc(size_t size)
414	n/a	{
415	n/a	/* see PyMem_RawMalloc() */
416	n/a	if (size > (size_t)PY_SSIZE_T_MAX)
417	n/a	return NULL;
418	n/a	return _PyMem.malloc(_PyMem.ctx, size);
419	n/a	}
420	n/a
421	n/a	void *
422	n/a	PyMem_Calloc(size_t nelem, size_t elsize)
423	n/a	{
424	n/a	/* see PyMem_RawMalloc() */
425	n/a	if (elsize != 0 && nelem > (size_t)PY_SSIZE_T_MAX / elsize)
426	n/a	return NULL;
427	n/a	return _PyMem.calloc(_PyMem.ctx, nelem, elsize);
428	n/a	}
429	n/a
430	n/a	void *
431	n/a	PyMem_Realloc(void *ptr, size_t new_size)
432	n/a	{
433	n/a	/* see PyMem_RawMalloc() */
434	n/a	if (new_size > (size_t)PY_SSIZE_T_MAX)
435	n/a	return NULL;
436	n/a	return _PyMem.realloc(_PyMem.ctx, ptr, new_size);
437	n/a	}
438	n/a
439	n/a	void
440	n/a	PyMem_Free(void *ptr)
441	n/a	{
442	n/a	_PyMem.free(_PyMem.ctx, ptr);
443	n/a	}
444	n/a
445	n/a	char *
446	n/a	_PyMem_RawStrdup(const char *str)
447	n/a	{
448	n/a	size_t size;
449	n/a	char *copy;
450	n/a
451	n/a	size = strlen(str) + 1;
452	n/a	copy = PyMem_RawMalloc(size);
453	n/a	if (copy == NULL)
454	n/a	return NULL;
455	n/a	memcpy(copy, str, size);
456	n/a	return copy;
457	n/a	}
458	n/a
459	n/a	char *
460	n/a	_PyMem_Strdup(const char *str)
461	n/a	{
462	n/a	size_t size;
463	n/a	char *copy;
464	n/a
465	n/a	size = strlen(str) + 1;
466	n/a	copy = PyMem_Malloc(size);
467	n/a	if (copy == NULL)
468	n/a	return NULL;
469	n/a	memcpy(copy, str, size);
470	n/a	return copy;
471	n/a	}
472	n/a
473	n/a	void *
474	n/a	PyObject_Malloc(size_t size)
475	n/a	{
476	n/a	/* see PyMem_RawMalloc() */
477	n/a	if (size > (size_t)PY_SSIZE_T_MAX)
478	n/a	return NULL;
479	n/a	return _PyObject.malloc(_PyObject.ctx, size);
480	n/a	}
481	n/a
482	n/a	void *
483	n/a	PyObject_Calloc(size_t nelem, size_t elsize)
484	n/a	{
485	n/a	/* see PyMem_RawMalloc() */
486	n/a	if (elsize != 0 && nelem > (size_t)PY_SSIZE_T_MAX / elsize)
487	n/a	return NULL;
488	n/a	return _PyObject.calloc(_PyObject.ctx, nelem, elsize);
489	n/a	}
490	n/a
491	n/a	void *
492	n/a	PyObject_Realloc(void *ptr, size_t new_size)
493	n/a	{
494	n/a	/* see PyMem_RawMalloc() */
495	n/a	if (new_size > (size_t)PY_SSIZE_T_MAX)
496	n/a	return NULL;
497	n/a	return _PyObject.realloc(_PyObject.ctx, ptr, new_size);
498	n/a	}
499	n/a
500	n/a	void
501	n/a	PyObject_Free(void *ptr)
502	n/a	{
503	n/a	_PyObject.free(_PyObject.ctx, ptr);
504	n/a	}
505	n/a
506	n/a
507	n/a	#ifdef WITH_PYMALLOC
508	n/a
509	n/a	#ifdef WITH_VALGRIND
510	n/a	#include <valgrind/valgrind.h>
511	n/a
512	n/a	/* If we're using GCC, use __builtin_expect() to reduce overhead of
513	n/a	the valgrind checks */
514	n/a	#if defined(__GNUC__) && (__GNUC__ > 2) && defined(__OPTIMIZE__)
515	n/a	# define UNLIKELY(value) __builtin_expect((value), 0)
516	n/a	#else
517	n/a	# define UNLIKELY(value) (value)
518	n/a	#endif
519	n/a
520	n/a	/* -1 indicates that we haven't checked that we're running on valgrind yet. */
521	n/a	static int running_on_valgrind = -1;
522	n/a	#endif
523	n/a
524	n/a	/* An object allocator for Python.
525	n/a
526	n/a	Here is an introduction to the layers of the Python memory architecture,
527	n/a	showing where the object allocator is actually used (layer +2), It is
528	n/a	called for every object allocation and deallocation (PyObject_New/Del),
529	n/a	unless the object-specific allocators implement a proprietary allocation
530	n/a	scheme (ex.: ints use a simple free list). This is also the place where
531	n/a	the cyclic garbage collector operates selectively on container objects.
532	n/a
533	n/a
534	n/a	Object-specific allocators
535	n/a	_____ ______ ______ ________
536	n/a	[ int ] [ dict ] [ list ] ... [ string ] Python core \|
537	n/a	+3 \| <----- Object-specific memory -----> \| <-- Non-object memory --> \|
538	n/a	_______________________________ \| \|
539	n/a	[ Python's object allocator ] \| \|
540	n/a	+2 \| ####### Object memory ####### \| <------ Internal buffers ------> \|
541	n/a	______________________________________________________________ \|
542	n/a	[ Python's raw memory allocator (PyMem_ API) ] \|
543	n/a	+1 \| <----- Python memory (under PyMem manager's control) ------> \| \|
544	n/a	__________________________________________________________________
545	n/a	[ Underlying general-purpose allocator (ex: C library malloc) ]
546	n/a	0 \| <------ Virtual memory allocated for the python process -------> \|
547	n/a
548	n/a	=========================================================================
549	n/a	_______________________________________________________________________
550	n/a	[ OS-specific Virtual Memory Manager (VMM) ]
551	n/a	-1 \| <--- Kernel dynamic storage allocation & management (page-based) ---> \|
552	n/a	__________________________________ __________________________________
553	n/a	[ ] [ ]
554	n/a	-2 \| <-- Physical memory: ROM/RAM --> \| \| <-- Secondary storage (swap) --> \|
555	n/a
556	n/a	*/
557	n/a	/==========================================================================/
558	n/a
559	n/a	/* A fast, special-purpose memory allocator for small blocks, to be used
560	n/a	on top of a general-purpose malloc -- heavily based on previous art. */
561	n/a
562	n/a	/* Vladimir Marangozov -- August 2000 */
563	n/a
564	n/a	/*
565	n/a	* "Memory management is where the rubber meets the road -- if we do the wrong
566	n/a	* thing at any level, the results will not be good. And if we don't make the
567	n/a	* levels work well together, we are in serious trouble." (1)
568	n/a	*
569	n/a	* (1) Paul R. Wilson, Mark S. Johnstone, Michael Neely, and David Boles,
570	n/a	* "Dynamic Storage Allocation: A Survey and Critical Review",
571	n/a	* in Proc. 1995 Int'l. Workshop on Memory Management, September 1995.
572	n/a	*/
573	n/a
574	n/a	/* #undef WITH_MEMORY_LIMITS / / disable mem limit checks */
575	n/a
576	n/a	/==========================================================================/
577	n/a
578	n/a	/*
579	n/a	* Allocation strategy abstract:
580	n/a	*
581	n/a	* For small requests, the allocator sub-allocates <Big> blocks of memory.
582	n/a	* Requests greater than SMALL_REQUEST_THRESHOLD bytes are routed to the
583	n/a	* system's allocator.
584	n/a	*
585	n/a	* Small requests are grouped in size classes spaced 8 bytes apart, due
586	n/a	* to the required valid alignment of the returned address. Requests of
587	n/a	* a particular size are serviced from memory pools of 4K (one VMM page).
588	n/a	* Pools are fragmented on demand and contain free lists of blocks of one
589	n/a	* particular size class. In other words, there is a fixed-size allocator
590	n/a	* for each size class. Free pools are shared by the different allocators
591	n/a	* thus minimizing the space reserved for a particular size class.
592	n/a	*
593	n/a	* This allocation strategy is a variant of what is known as "simple
594	n/a	* segregated storage based on array of free lists". The main drawback of
595	n/a	* simple segregated storage is that we might end up with lot of reserved
596	n/a	* memory for the different free lists, which degenerate in time. To avoid
597	n/a	* this, we partition each free list in pools and we share dynamically the
598	n/a	* reserved space between all free lists. This technique is quite efficient
599	n/a	* for memory intensive programs which allocate mainly small-sized blocks.
600	n/a	*
601	n/a	* For small requests we have the following table:
602	n/a	*
603	n/a	* Request in bytes Size of allocated block Size class idx
604	n/a	* ----------------------------------------------------------------
605	n/a	* 1-8 8 0
606	n/a	* 9-16 16 1
607	n/a	* 17-24 24 2
608	n/a	* 25-32 32 3
609	n/a	* 33-40 40 4
610	n/a	* 41-48 48 5
611	n/a	* 49-56 56 6
612	n/a	* 57-64 64 7
613	n/a	* 65-72 72 8
614	n/a	* ... ... ...
615	n/a	* 497-504 504 62
616	n/a	* 505-512 512 63
617	n/a	*
618	n/a	* 0, SMALL_REQUEST_THRESHOLD + 1 and up: routed to the underlying
619	n/a	* allocator.
620	n/a	*/
621	n/a
622	n/a	/==========================================================================/
623	n/a
624	n/a	/*
625	n/a	* -- Main tunable settings section --
626	n/a	*/
627	n/a
628	n/a	/*
629	n/a	* Alignment of addresses returned to the user. 8-bytes alignment works
630	n/a	* on most current architectures (with 32-bit or 64-bit address busses).
631	n/a	* The alignment value is also used for grouping small requests in size
632	n/a	* classes spaced ALIGNMENT bytes apart.
633	n/a	*
634	n/a	* You shouldn't change this unless you know what you are doing.
635	n/a	*/
636	n/a	#define ALIGNMENT 8 /* must be 2^N */
637	n/a	#define ALIGNMENT_SHIFT 3
638	n/a
639	n/a	/* Return the number of bytes in size class I, as a uint. */
640	n/a	#define INDEX2SIZE(I) (((uint)(I) + 1) << ALIGNMENT_SHIFT)
641	n/a
642	n/a	/*
643	n/a	* Max size threshold below which malloc requests are considered to be
644	n/a	* small enough in order to use preallocated memory pools. You can tune
645	n/a	* this value according to your application behaviour and memory needs.
646	n/a	*
647	n/a	* Note: a size threshold of 512 guarantees that newly created dictionaries
648	n/a	* will be allocated from preallocated memory pools on 64-bit.
649	n/a	*
650	n/a	* The following invariants must hold:
651	n/a	* 1) ALIGNMENT <= SMALL_REQUEST_THRESHOLD <= 512
652	n/a	* 2) SMALL_REQUEST_THRESHOLD is evenly divisible by ALIGNMENT
653	n/a	*
654	n/a	* Although not required, for better performance and space efficiency,
655	n/a	* it is recommended that SMALL_REQUEST_THRESHOLD is set to a power of 2.
656	n/a	*/
657	n/a	#define SMALL_REQUEST_THRESHOLD 512
658	n/a	#define NB_SMALL_SIZE_CLASSES (SMALL_REQUEST_THRESHOLD / ALIGNMENT)
659	n/a
660	n/a	/*
661	n/a	* The system's VMM page size can be obtained on most unices with a
662	n/a	* getpagesize() call or deduced from various header files. To make
663	n/a	* things simpler, we assume that it is 4K, which is OK for most systems.
664	n/a	* It is probably better if this is the native page size, but it doesn't
665	n/a	* have to be. In theory, if SYSTEM_PAGE_SIZE is larger than the native page
666	n/a	* size, then `POOL_ADDR(p)->arenaindex' could rarely cause a segmentation
667	n/a	* violation fault. 4K is apparently OK for all the platforms that python
668	n/a	* currently targets.
669	n/a	*/
670	n/a	#define SYSTEM_PAGE_SIZE (4 * 1024)
671	n/a	#define SYSTEM_PAGE_SIZE_MASK (SYSTEM_PAGE_SIZE - 1)
672	n/a
673	n/a	/*
674	n/a	* Maximum amount of memory managed by the allocator for small requests.
675	n/a	*/
676	n/a	#ifdef WITH_MEMORY_LIMITS
677	n/a	#ifndef SMALL_MEMORY_LIMIT
678	n/a	#define SMALL_MEMORY_LIMIT (64 * 1024 * 1024) /* 64 MB -- more? */
679	n/a	#endif
680	n/a	#endif
681	n/a
682	n/a	/*
683	n/a	* The allocator sub-allocates <Big> blocks of memory (called arenas) aligned
684	n/a	* on a page boundary. This is a reserved virtual address space for the
685	n/a	* current process (obtained through a malloc()/mmap() call). In no way this
686	n/a	* means that the memory arenas will be used entirely. A malloc(<Big>) is
687	n/a	* usually an address range reservation for <Big> bytes, unless all pages within
688	n/a	* this space are referenced subsequently. So malloc'ing big blocks and not
689	n/a	* using them does not mean "wasting memory". It's an addressable range
690	n/a	* wastage...
691	n/a	*
692	n/a	* Arenas are allocated with mmap() on systems supporting anonymous memory
693	n/a	* mappings to reduce heap fragmentation.
694	n/a	*/
695	n/a	#define ARENA_SIZE (256 << 10) /* 256KB */
696	n/a
697	n/a	#ifdef WITH_MEMORY_LIMITS
698	n/a	#define MAX_ARENAS (SMALL_MEMORY_LIMIT / ARENA_SIZE)
699	n/a	#endif
700	n/a
701	n/a	/*
702	n/a	* Size of the pools used for small blocks. Should be a power of 2,
703	n/a	* between 1K and SYSTEM_PAGE_SIZE, that is: 1k, 2k, 4k.
704	n/a	*/
705	n/a	#define POOL_SIZE SYSTEM_PAGE_SIZE /* must be 2^N */
706	n/a	#define POOL_SIZE_MASK SYSTEM_PAGE_SIZE_MASK
707	n/a
708	n/a	/*
709	n/a	* -- End of tunable settings section --
710	n/a	*/
711	n/a
712	n/a	/==========================================================================/
713	n/a
714	n/a	/*
715	n/a	* Locking
716	n/a	*
717	n/a	* To reduce lock contention, it would probably be better to refine the
718	n/a	* crude function locking with per size class locking. I'm not positive
719	n/a	* however, whether it's worth switching to such locking policy because
720	n/a	* of the performance penalty it might introduce.
721	n/a	*
722	n/a	* The following macros describe the simplest (should also be the fastest)
723	n/a	* lock object on a particular platform and the init/fini/lock/unlock
724	n/a	* operations on it. The locks defined here are not expected to be recursive
725	n/a	* because it is assumed that they will always be called in the order:
726	n/a	* INIT, [LOCK, UNLOCK]*, FINI.
727	n/a	*/
728	n/a
729	n/a	/*
730	n/a	* Python's threads are serialized, so object malloc locking is disabled.
731	n/a	*/
732	n/a	#define SIMPLELOCK_DECL(lock) /* simple lock declaration */
733	n/a	#define SIMPLELOCK_INIT(lock) /* allocate (if needed) and initialize */
734	n/a	#define SIMPLELOCK_FINI(lock) /* free/destroy an existing lock */
735	n/a	#define SIMPLELOCK_LOCK(lock) /* acquire released lock */
736	n/a	#define SIMPLELOCK_UNLOCK(lock) /* release acquired lock */
737	n/a
738	n/a	/* When you say memory, my mind reasons in terms of (pointers to) blocks */
739	n/a	typedef uint8_t block;
740	n/a
741	n/a	/* Pool for small blocks. */
742	n/a	struct pool_header {
743	n/a	union { block *_padding;
744	n/a	uint count; } ref; /* number of allocated blocks */
745	n/a	block freeblock; / pool's free list head */
746	n/a	struct pool_header nextpool; / next pool of this size class */
747	n/a	struct pool_header prevpool; / previous pool "" */
748	n/a	uint arenaindex; /* index into arenas of base adr */
749	n/a	uint szidx; /* block size class index */
750	n/a	uint nextoffset; /* bytes to virgin block */
751	n/a	uint maxnextoffset; /* largest valid nextoffset */
752	n/a	};
753	n/a
754	n/a	typedef struct pool_header *poolp;
755	n/a
756	n/a	/* Record keeping for arenas. */
757	n/a	struct arena_object {
758	n/a	/* The address of the arena, as returned by malloc. Note that 0
759	n/a	* will never be returned by a successful malloc, and is used
760	n/a	* here to mark an arena_object that doesn't correspond to an
761	n/a	* allocated arena.
762	n/a	*/
763	n/a	uintptr_t address;
764	n/a
765	n/a	/* Pool-aligned pointer to the next pool to be carved off. */
766	n/a	block* pool_address;
767	n/a
768	n/a	/* The number of available pools in the arena: free pools + never-
769	n/a	* allocated pools.
770	n/a	*/
771	n/a	uint nfreepools;
772	n/a
773	n/a	/* The total number of pools in the arena, whether or not available. */
774	n/a	uint ntotalpools;
775	n/a
776	n/a	/* Singly-linked list of available pools. */
777	n/a	struct pool_header* freepools;
778	n/a
779	n/a	/* Whenever this arena_object is not associated with an allocated
780	n/a	* arena, the nextarena member is used to link all unassociated
781	n/a	* arena_objects in the singly-linked `unused_arena_objects` list.
782	n/a	* The prevarena member is unused in this case.
783	n/a	*
784	n/a	* When this arena_object is associated with an allocated arena
785	n/a	* with at least one available pool, both members are used in the
786	n/a	* doubly-linked `usable_arenas` list, which is maintained in
787	n/a	* increasing order of `nfreepools` values.
788	n/a	*
789	n/a	* Else this arena_object is associated with an allocated arena
790	n/a	* all of whose pools are in use. `nextarena` and `prevarena`
791	n/a	* are both meaningless in this case.
792	n/a	*/
793	n/a	struct arena_object* nextarena;
794	n/a	struct arena_object* prevarena;
795	n/a	};
796	n/a
797	n/a	#define POOL_OVERHEAD _Py_SIZE_ROUND_UP(sizeof(struct pool_header), ALIGNMENT)
798	n/a
799	n/a	#define DUMMY_SIZE_IDX 0xffff /* size class of newly cached pools */
800	n/a
801	n/a	/* Round pointer P down to the closest pool-aligned address <= P, as a poolp */
802	n/a	#define POOL_ADDR(P) ((poolp)_Py_ALIGN_DOWN((P), POOL_SIZE))
803	n/a
804	n/a	/* Return total number of blocks in pool of size index I, as a uint. */
805	n/a	#define NUMBLOCKS(I) ((uint)(POOL_SIZE - POOL_OVERHEAD) / INDEX2SIZE(I))
806	n/a
807	n/a	/==========================================================================/
808	n/a
809	n/a	/*
810	n/a	* This malloc lock
811	n/a	*/
812	n/a	SIMPLELOCK_DECL(_malloc_lock)
813	n/a	#define LOCK() SIMPLELOCK_LOCK(_malloc_lock)
814	n/a	#define UNLOCK() SIMPLELOCK_UNLOCK(_malloc_lock)
815	n/a	#define LOCK_INIT() SIMPLELOCK_INIT(_malloc_lock)
816	n/a	#define LOCK_FINI() SIMPLELOCK_FINI(_malloc_lock)
817	n/a
818	n/a	/*
819	n/a	* Pool table -- headed, circular, doubly-linked lists of partially used pools.
820	n/a
821	n/a	This is involved. For an index i, usedpools[i+i] is the header for a list of
822	n/a	all partially used pools holding small blocks with "size class idx" i. So
823	n/a	usedpools[0] corresponds to blocks of size 8, usedpools[2] to blocks of size
824	n/a	16, and so on: index 2*i <-> blocks of size (i+1)<<ALIGNMENT_SHIFT.
825	n/a
826	n/a	Pools are carved off an arena's highwater mark (an arena_object's pool_address
827	n/a	member) as needed. Once carved off, a pool is in one of three states forever
828	n/a	after:
829	n/a
830	n/a	used == partially used, neither empty nor full
831	n/a	At least one block in the pool is currently allocated, and at least one
832	n/a	block in the pool is not currently allocated (note this implies a pool
833	n/a	has room for at least two blocks).
834	n/a	This is a pool's initial state, as a pool is created only when malloc
835	n/a	needs space.
836	n/a	The pool holds blocks of a fixed size, and is in the circular list headed
837	n/a	at usedpools[i] (see above). It's linked to the other used pools of the
838	n/a	same size class via the pool_header's nextpool and prevpool members.
839	n/a	If all but one block is currently allocated, a malloc can cause a
840	n/a	transition to the full state. If all but one block is not currently
841	n/a	allocated, a free can cause a transition to the empty state.
842	n/a
843	n/a	full == all the pool's blocks are currently allocated
844	n/a	On transition to full, a pool is unlinked from its usedpools[] list.
845	n/a	It's not linked to from anything then anymore, and its nextpool and
846	n/a	prevpool members are meaningless until it transitions back to used.
847	n/a	A free of a block in a full pool puts the pool back in the used state.
848	n/a	Then it's linked in at the front of the appropriate usedpools[] list, so
849	n/a	that the next allocation for its size class will reuse the freed block.
850	n/a
851	n/a	empty == all the pool's blocks are currently available for allocation
852	n/a	On transition to empty, a pool is unlinked from its usedpools[] list,
853	n/a	and linked to the front of its arena_object's singly-linked freepools list,
854	n/a	via its nextpool member. The prevpool member has no meaning in this case.
855	n/a	Empty pools have no inherent size class: the next time a malloc finds
856	n/a	an empty list in usedpools[], it takes the first pool off of freepools.
857	n/a	If the size class needed happens to be the same as the size class the pool
858	n/a	last had, some pool initialization can be skipped.
859	n/a
860	n/a
861	n/a	Block Management
862	n/a
863	n/a	Blocks within pools are again carved out as needed. pool->freeblock points to
864	n/a	the start of a singly-linked list of free blocks within the pool. When a
865	n/a	block is freed, it's inserted at the front of its pool's freeblock list. Note
866	n/a	that the available blocks in a pool are not linked all together when a pool
867	n/a	is initialized. Instead only "the first two" (lowest addresses) blocks are
868	n/a	set up, returning the first such block, and setting pool->freeblock to a
869	n/a	one-block list holding the second such block. This is consistent with that
870	n/a	pymalloc strives at all levels (arena, pool, and block) never to touch a piece
871	n/a	of memory until it's actually needed.
872	n/a
873	n/a	So long as a pool is in the used state, we're certain there is a block
874	n/a	available for allocating, and pool->freeblock is not NULL. If pool->freeblock
875	n/a	points to the end of the free list before we've carved the entire pool into
876	n/a	blocks, that means we simply haven't yet gotten to one of the higher-address
877	n/a	blocks. The offset from the pool_header to the start of "the next" virgin
878	n/a	block is stored in the pool_header nextoffset member, and the largest value
879	n/a	of nextoffset that makes sense is stored in the maxnextoffset member when a
880	n/a	pool is initialized. All the blocks in a pool have been passed out at least
881	n/a	once when and only when nextoffset > maxnextoffset.
882	n/a
883	n/a
884	n/a	Major obscurity: While the usedpools vector is declared to have poolp
885	n/a	entries, it doesn't really. It really contains two pointers per (conceptual)
886	n/a	poolp entry, the nextpool and prevpool members of a pool_header. The
887	n/a	excruciating initialization code below fools C so that
888	n/a
889	n/a	usedpool[i+i]
890	n/a
891	n/a	"acts like" a genuine poolp, but only so long as you only reference its
892	n/a	nextpool and prevpool members. The "- 2sizeof(block )" gibberish is
893	n/a	compensating for that a pool_header's nextpool and prevpool members
894	n/a	immediately follow a pool_header's first two members:
895	n/a
896	n/a	union { block *_padding;
897	n/a	uint count; } ref;
898	n/a	block *freeblock;
899	n/a
900	n/a	each of which consume sizeof(block *) bytes. So what usedpools[i+i] really
901	n/a	contains is a fudged-up pointer p such that if C believes it's a poolp
902	n/a	pointer, then p->nextpool and p->prevpool are both p (meaning that the headed
903	n/a	circular list is empty).
904	n/a
905	n/a	It's unclear why the usedpools setup is so convoluted. It could be to
906	n/a	minimize the amount of cache required to hold this heavily-referenced table
907	n/a	(which only needs the two interpool pointer members of a pool_header). OTOH,
908	n/a	referencing code has to remember to "double the index" and doing so isn't
909	n/a	free, usedpools[0] isn't a strictly legal pointer, and we're crucially relying
910	n/a	on that C doesn't insert any padding anywhere in a pool_header at or before
911	n/a	the prevpool member.
912	n/a	**************************************************************************** */
913	n/a
914	n/a	#define PTA(x) ((poolp )((uint8_t )&(usedpools[2(x)]) - 2sizeof(block )))
915	n/a	#define PT(x) PTA(x), PTA(x)
916	n/a
917	n/a	static poolp usedpools[2 * ((NB_SMALL_SIZE_CLASSES + 7) / 8) * 8] = {
918	n/a	PT(0), PT(1), PT(2), PT(3), PT(4), PT(5), PT(6), PT(7)
919	n/a	#if NB_SMALL_SIZE_CLASSES > 8
920	n/a	, PT(8), PT(9), PT(10), PT(11), PT(12), PT(13), PT(14), PT(15)
921	n/a	#if NB_SMALL_SIZE_CLASSES > 16
922	n/a	, PT(16), PT(17), PT(18), PT(19), PT(20), PT(21), PT(22), PT(23)
923	n/a	#if NB_SMALL_SIZE_CLASSES > 24
924	n/a	, PT(24), PT(25), PT(26), PT(27), PT(28), PT(29), PT(30), PT(31)
925	n/a	#if NB_SMALL_SIZE_CLASSES > 32
926	n/a	, PT(32), PT(33), PT(34), PT(35), PT(36), PT(37), PT(38), PT(39)
927	n/a	#if NB_SMALL_SIZE_CLASSES > 40
928	n/a	, PT(40), PT(41), PT(42), PT(43), PT(44), PT(45), PT(46), PT(47)
929	n/a	#if NB_SMALL_SIZE_CLASSES > 48
930	n/a	, PT(48), PT(49), PT(50), PT(51), PT(52), PT(53), PT(54), PT(55)
931	n/a	#if NB_SMALL_SIZE_CLASSES > 56
932	n/a	, PT(56), PT(57), PT(58), PT(59), PT(60), PT(61), PT(62), PT(63)
933	n/a	#if NB_SMALL_SIZE_CLASSES > 64
934	n/a	#error "NB_SMALL_SIZE_CLASSES should be less than 64"
935	n/a	#endif /* NB_SMALL_SIZE_CLASSES > 64 */
936	n/a	#endif /* NB_SMALL_SIZE_CLASSES > 56 */
937	n/a	#endif /* NB_SMALL_SIZE_CLASSES > 48 */
938	n/a	#endif /* NB_SMALL_SIZE_CLASSES > 40 */
939	n/a	#endif /* NB_SMALL_SIZE_CLASSES > 32 */
940	n/a	#endif /* NB_SMALL_SIZE_CLASSES > 24 */
941	n/a	#endif /* NB_SMALL_SIZE_CLASSES > 16 */
942	n/a	#endif /* NB_SMALL_SIZE_CLASSES > 8 */
943	n/a	};
944	n/a
945	n/a	/*==========================================================================
946	n/a	Arena management.
947	n/a
948	n/a	`arenas` is a vector of arena_objects. It contains maxarenas entries, some of
949	n/a	which may not be currently used (== they're arena_objects that aren't
950	n/a	currently associated with an allocated arena). Note that arenas proper are
951	n/a	separately malloc'ed.
952	n/a
953	n/a	Prior to Python 2.5, arenas were never free()'ed. Starting with Python 2.5,
954	n/a	we do try to free() arenas, and use some mild heuristic strategies to increase
955	n/a	the likelihood that arenas eventually can be freed.
956	n/a
957	n/a	unused_arena_objects
958	n/a
959	n/a	This is a singly-linked list of the arena_objects that are currently not
960	n/a	being used (no arena is associated with them). Objects are taken off the
961	n/a	head of the list in new_arena(), and are pushed on the head of the list in
962	n/a	PyObject_Free() when the arena is empty. Key invariant: an arena_object
963	n/a	is on this list if and only if its .address member is 0.
964	n/a
965	n/a	usable_arenas
966	n/a
967	n/a	This is a doubly-linked list of the arena_objects associated with arenas
968	n/a	that have pools available. These pools are either waiting to be reused,
969	n/a	or have not been used before. The list is sorted to have the most-
970	n/a	allocated arenas first (ascending order based on the nfreepools member).
971	n/a	This means that the next allocation will come from a heavily used arena,
972	n/a	which gives the nearly empty arenas a chance to be returned to the system.
973	n/a	In my unscientific tests this dramatically improved the number of arenas
974	n/a	that could be freed.
975	n/a
976	n/a	Note that an arena_object associated with an arena all of whose pools are
977	n/a	currently in use isn't on either list.
978	n/a	*/
979	n/a
980	n/a	/* Array of objects used to track chunks of memory (arenas). */
981	n/a	static struct arena_object* arenas = NULL;
982	n/a	/* Number of slots currently allocated in the `arenas` vector. */
983	n/a	static uint maxarenas = 0;
984	n/a
985	n/a	/* The head of the singly-linked, NULL-terminated list of available
986	n/a	* arena_objects.
987	n/a	*/
988	n/a	static struct arena_object* unused_arena_objects = NULL;
989	n/a
990	n/a	/* The head of the doubly-linked, NULL-terminated at each end, list of
991	n/a	* arena_objects associated with arenas that have pools available.
992	n/a	*/
993	n/a	static struct arena_object* usable_arenas = NULL;
994	n/a
995	n/a	/* How many arena_objects do we initially allocate?
996	n/a	* 16 = can allocate 16 arenas = 16 * ARENA_SIZE = 4MB before growing the
997	n/a	* `arenas` vector.
998	n/a	*/
999	n/a	#define INITIAL_ARENA_OBJECTS 16
1000	n/a
1001	n/a	/* Number of arenas allocated that haven't been free()'d. */
1002	n/a	static size_t narenas_currently_allocated = 0;
1003	n/a
1004	n/a	/* Total number of times malloc() called to allocate an arena. */
1005	n/a	static size_t ntimes_arena_allocated = 0;
1006	n/a	/* High water mark (max value ever seen) for narenas_currently_allocated. */
1007	n/a	static size_t narenas_highwater = 0;
1008	n/a
1009	n/a	static Py_ssize_t _Py_AllocatedBlocks = 0;
1010	n/a
1011	n/a	Py_ssize_t
1012	n/a	_Py_GetAllocatedBlocks(void)
1013	n/a	{
1014	n/a	return _Py_AllocatedBlocks;
1015	n/a	}
1016	n/a
1017	n/a
1018	n/a	/* Allocate a new arena. If we run out of memory, return NULL. Else
1019	n/a	* allocate a new arena, and return the address of an arena_object
1020	n/a	* describing the new arena. It's expected that the caller will set
1021	n/a	* `usable_arenas` to the return value.
1022	n/a	*/
1023	n/a	static struct arena_object*
1024	n/a	new_arena(void)
1025	n/a	{
1026	n/a	struct arena_object* arenaobj;
1027	n/a	uint excess; /* number of bytes above pool alignment */
1028	n/a	void *address;
1029	n/a	static int debug_stats = -1;
1030	n/a
1031	n/a	if (debug_stats == -1) {
1032	n/a	char *opt = Py_GETENV("PYTHONMALLOCSTATS");
1033	n/a	debug_stats = (opt != NULL && *opt != '\0');
1034	n/a	}
1035	n/a	if (debug_stats)
1036	n/a	_PyObject_DebugMallocStats(stderr);
1037	n/a
1038	n/a	if (unused_arena_objects == NULL) {
1039	n/a	uint i;
1040	n/a	uint numarenas;
1041	n/a	size_t nbytes;
1042	n/a
1043	n/a	/* Double the number of arena objects on each allocation.
1044	n/a	* Note that it's possible for `numarenas` to overflow.
1045	n/a	*/
1046	n/a	numarenas = maxarenas ? maxarenas << 1 : INITIAL_ARENA_OBJECTS;
1047	n/a	if (numarenas <= maxarenas)
1048	n/a	return NULL; /* overflow */
1049	n/a	#if SIZEOF_SIZE_T <= SIZEOF_INT
1050	n/a	if (numarenas > SIZE_MAX / sizeof(*arenas))
1051	n/a	return NULL; /* overflow */
1052	n/a	#endif
1053	n/a	nbytes = numarenas * sizeof(*arenas);
1054	n/a	arenaobj = (struct arena_object *)PyMem_RawRealloc(arenas, nbytes);
1055	n/a	if (arenaobj == NULL)
1056	n/a	return NULL;
1057	n/a	arenas = arenaobj;
1058	n/a
1059	n/a	/* We might need to fix pointers that were copied. However,
1060	n/a	* new_arena only gets called when all the pages in the
1061	n/a	* previous arenas are full. Thus, there are no pointers
1062	n/a	* into the old array. Thus, we don't have to worry about
1063	n/a	* invalid pointers. Just to be sure, some asserts:
1064	n/a	*/
1065	n/a	assert(usable_arenas == NULL);
1066	n/a	assert(unused_arena_objects == NULL);
1067	n/a
1068	n/a	/* Put the new arenas on the unused_arena_objects list. */
1069	n/a	for (i = maxarenas; i < numarenas; ++i) {
1070	n/a	arenas[i].address = 0; /* mark as unassociated */
1071	n/a	arenas[i].nextarena = i < numarenas - 1 ?
1072	n/a	&arenas[i+1] : NULL;
1073	n/a	}
1074	n/a
1075	n/a	/* Update globals. */
1076	n/a	unused_arena_objects = &arenas[maxarenas];
1077	n/a	maxarenas = numarenas;
1078	n/a	}
1079	n/a
1080	n/a	/* Take the next available arena object off the head of the list. */
1081	n/a	assert(unused_arena_objects != NULL);
1082	n/a	arenaobj = unused_arena_objects;
1083	n/a	unused_arena_objects = arenaobj->nextarena;
1084	n/a	assert(arenaobj->address == 0);
1085	n/a	address = _PyObject_Arena.alloc(_PyObject_Arena.ctx, ARENA_SIZE);
1086	n/a	if (address == NULL) {
1087	n/a	/* The allocation failed: return NULL after putting the
1088	n/a	* arenaobj back.
1089	n/a	*/
1090	n/a	arenaobj->nextarena = unused_arena_objects;
1091	n/a	unused_arena_objects = arenaobj;
1092	n/a	return NULL;
1093	n/a	}
1094	n/a	arenaobj->address = (uintptr_t)address;
1095	n/a
1096	n/a	++narenas_currently_allocated;
1097	n/a	++ntimes_arena_allocated;
1098	n/a	if (narenas_currently_allocated > narenas_highwater)
1099	n/a	narenas_highwater = narenas_currently_allocated;
1100	n/a	arenaobj->freepools = NULL;
1101	n/a	/* pool_address <- first pool-aligned address in the arena
1102	n/a	nfreepools <- number of whole pools that fit after alignment */
1103	n/a	arenaobj->pool_address = (block*)arenaobj->address;
1104	n/a	arenaobj->nfreepools = ARENA_SIZE / POOL_SIZE;
1105	n/a	assert(POOL_SIZE * arenaobj->nfreepools == ARENA_SIZE);
1106	n/a	excess = (uint)(arenaobj->address & POOL_SIZE_MASK);
1107	n/a	if (excess != 0) {
1108	n/a	--arenaobj->nfreepools;
1109	n/a	arenaobj->pool_address += POOL_SIZE - excess;
1110	n/a	}
1111	n/a	arenaobj->ntotalpools = arenaobj->nfreepools;
1112	n/a
1113	n/a	return arenaobj;
1114	n/a	}
1115	n/a
1116	n/a	/*
1117	n/a	address_in_range(P, POOL)
1118	n/a
1119	n/a	Return true if and only if P is an address that was allocated by pymalloc.
1120	n/a	POOL must be the pool address associated with P, i.e., POOL = POOL_ADDR(P)
1121	n/a	(the caller is asked to compute this because the macro expands POOL more than
1122	n/a	once, and for efficiency it's best for the caller to assign POOL_ADDR(P) to a
1123	n/a	variable and pass the latter to the macro; because address_in_range is
1124	n/a	called on every alloc/realloc/free, micro-efficiency is important here).
1125	n/a
1126	n/a	Tricky: Let B be the arena base address associated with the pool, B =
1127	n/a	arenas[(POOL)->arenaindex].address. Then P belongs to the arena if and only if
1128	n/a
1129	n/a	B <= P < B + ARENA_SIZE
1130	n/a
1131	n/a	Subtracting B throughout, this is true iff
1132	n/a
1133	n/a	0 <= P-B < ARENA_SIZE
1134	n/a
1135	n/a	By using unsigned arithmetic, the "0 <=" half of the test can be skipped.
1136	n/a
1137	n/a	Obscure: A PyMem "free memory" function can call the pymalloc free or realloc
1138	n/a	before the first arena has been allocated. `arenas` is still NULL in that
1139	n/a	case. We're relying on that maxarenas is also 0 in that case, so that
1140	n/a	(POOL)->arenaindex < maxarenas must be false, saving us from trying to index
1141	n/a	into a NULL arenas.
1142	n/a
1143	n/a	Details: given P and POOL, the arena_object corresponding to P is AO =
1144	n/a	arenas[(POOL)->arenaindex]. Suppose obmalloc controls P. Then (barring wild
1145	n/a	stores, etc), POOL is the correct address of P's pool, AO.address is the
1146	n/a	correct base address of the pool's arena, and P must be within ARENA_SIZE of
1147	n/a	AO.address. In addition, AO.address is not 0 (no arena can start at address 0
1148	n/a	(NULL)). Therefore address_in_range correctly reports that obmalloc
1149	n/a	controls P.
1150	n/a
1151	n/a	Now suppose obmalloc does not control P (e.g., P was obtained via a direct
1152	n/a	call to the system malloc() or realloc()). (POOL)->arenaindex may be anything
1153	n/a	in this case -- it may even be uninitialized trash. If the trash arenaindex
1154	n/a	is >= maxarenas, the macro correctly concludes at once that obmalloc doesn't
1155	n/a	control P.
1156	n/a
1157	n/a	Else arenaindex is < maxarena, and AO is read up. If AO corresponds to an
1158	n/a	allocated arena, obmalloc controls all the memory in slice AO.address :
1159	n/a	AO.address+ARENA_SIZE. By case assumption, P is not controlled by obmalloc,
1160	n/a	so P doesn't lie in that slice, so the macro correctly reports that P is not
1161	n/a	controlled by obmalloc.
1162	n/a
1163	n/a	Finally, if P is not controlled by obmalloc and AO corresponds to an unused
1164	n/a	arena_object (one not currently associated with an allocated arena),
1165	n/a	AO.address is 0, and the second test in the macro reduces to:
1166	n/a
1167	n/a	P < ARENA_SIZE
1168	n/a
1169	n/a	If P >= ARENA_SIZE (extremely likely), the macro again correctly concludes
1170	n/a	that P is not controlled by obmalloc. However, if P < ARENA_SIZE, this part
1171	n/a	of the test still passes, and the third clause (AO.address != 0) is necessary
1172	n/a	to get the correct result: AO.address is 0 in this case, so the macro
1173	n/a	correctly reports that P is not controlled by obmalloc (despite that P lies in
1174	n/a	slice AO.address : AO.address + ARENA_SIZE).
1175	n/a
1176	n/a	Note: The third (AO.address != 0) clause was added in Python 2.5. Before
1177	n/a	2.5, arenas were never free()'ed, and an arenaindex < maxarena always
1178	n/a	corresponded to a currently-allocated arena, so the "P is not controlled by
1179	n/a	obmalloc, AO corresponds to an unused arena_object, and P < ARENA_SIZE" case
1180	n/a	was impossible.
1181	n/a
1182	n/a	Note that the logic is excruciating, and reading up possibly uninitialized
1183	n/a	memory when P is not controlled by obmalloc (to get at (POOL)->arenaindex)
1184	n/a	creates problems for some memory debuggers. The overwhelming advantage is
1185	n/a	that this test determines whether an arbitrary address is controlled by
1186	n/a	obmalloc in a small constant time, independent of the number of arenas
1187	n/a	obmalloc controls. Since this test is needed at every entry point, it's
1188	n/a	extremely desirable that it be this fast.
1189	n/a	*/
1190	n/a
1191	n/a	static bool ATTRIBUTE_NO_ADDRESS_SAFETY_ANALYSIS
1192	n/a	address_in_range(void *p, poolp pool)
1193	n/a	{
1194	n/a	// Since address_in_range may be reading from memory which was not allocated
1195	n/a	// by Python, it is important that pool->arenaindex is read only once, as
1196	n/a	// another thread may be concurrently modifying the value without holding
1197	n/a	// the GIL. The following dance forces the compiler to read pool->arenaindex
1198	n/a	// only once.
1199	n/a	uint arenaindex = ((volatile uint )&pool->arenaindex);
1200	n/a	return arenaindex < maxarenas &&
1201	n/a	(uintptr_t)p - arenas[arenaindex].address < ARENA_SIZE &&
1202	n/a	arenas[arenaindex].address != 0;
1203	n/a	}
1204	n/a
1205	n/a	/==========================================================================/
1206	n/a
1207	n/a	/* malloc. Note that nbytes==0 tries to return a non-NULL pointer, distinct
1208	n/a	* from all other currently live pointers. This may not be possible.
1209	n/a	*/
1210	n/a
1211	n/a	/*
1212	n/a	* The basic blocks are ordered by decreasing execution frequency,
1213	n/a	* which minimizes the number of jumps in the most common cases,
1214	n/a	* improves branching prediction and instruction scheduling (small
1215	n/a	* block allocations typically result in a couple of instructions).
1216	n/a	* Unless the optimizer reorders everything, being too smart...
1217	n/a	*/
1218	n/a
1219	n/a	static void *
1220	n/a	_PyObject_Alloc(int use_calloc, void *ctx, size_t nelem, size_t elsize)
1221	n/a	{
1222	n/a	size_t nbytes;
1223	n/a	block *bp;
1224	n/a	poolp pool;
1225	n/a	poolp next;
1226	n/a	uint size;
1227	n/a
1228	n/a	_Py_AllocatedBlocks++;
1229	n/a
1230	n/a	assert(nelem <= PY_SSIZE_T_MAX / elsize);
1231	n/a	nbytes = nelem * elsize;
1232	n/a
1233	n/a	#ifdef WITH_VALGRIND
1234	n/a	if (UNLIKELY(running_on_valgrind == -1))
1235	n/a	running_on_valgrind = RUNNING_ON_VALGRIND;
1236	n/a	if (UNLIKELY(running_on_valgrind))
1237	n/a	goto redirect;
1238	n/a	#endif
1239	n/a
1240	n/a	if (nelem == 0 \|\| elsize == 0)
1241	n/a	goto redirect;
1242	n/a
1243	n/a	if ((nbytes - 1) < SMALL_REQUEST_THRESHOLD) {
1244	n/a	LOCK();
1245	n/a	/*
1246	n/a	* Most frequent paths first
1247	n/a	*/
1248	n/a	size = (uint)(nbytes - 1) >> ALIGNMENT_SHIFT;
1249	n/a	pool = usedpools[size + size];
1250	n/a	if (pool != pool->nextpool) {
1251	n/a	/*
1252	n/a	* There is a used pool for this size class.
1253	n/a	* Pick up the head block of its free list.
1254	n/a	*/
1255	n/a	++pool->ref.count;
1256	n/a	bp = pool->freeblock;
1257	n/a	assert(bp != NULL);
1258	n/a	if ((pool->freeblock = (block *)bp) != NULL) {
1259	n/a	UNLOCK();
1260	n/a	if (use_calloc)
1261	n/a	memset(bp, 0, nbytes);
1262	n/a	return (void *)bp;
1263	n/a	}
1264	n/a	/*
1265	n/a	* Reached the end of the free list, try to extend it.
1266	n/a	*/
1267	n/a	if (pool->nextoffset <= pool->maxnextoffset) {
1268	n/a	/* There is room for another block. */
1269	n/a	pool->freeblock = (block*)pool +
1270	n/a	pool->nextoffset;
1271	n/a	pool->nextoffset += INDEX2SIZE(size);
1272	n/a	(block *)(pool->freeblock) = NULL;
1273	n/a	UNLOCK();
1274	n/a	if (use_calloc)
1275	n/a	memset(bp, 0, nbytes);
1276	n/a	return (void *)bp;
1277	n/a	}
1278	n/a	/* Pool is full, unlink from used pools. */
1279	n/a	next = pool->nextpool;
1280	n/a	pool = pool->prevpool;
1281	n/a	next->prevpool = pool;
1282	n/a	pool->nextpool = next;
1283	n/a	UNLOCK();
1284	n/a	if (use_calloc)
1285	n/a	memset(bp, 0, nbytes);
1286	n/a	return (void *)bp;
1287	n/a	}
1288	n/a
1289	n/a	/* There isn't a pool of the right size class immediately
1290	n/a	* available: use a free pool.
1291	n/a	*/
1292	n/a	if (usable_arenas == NULL) {
1293	n/a	/* No arena has a free pool: allocate a new arena. */
1294	n/a	#ifdef WITH_MEMORY_LIMITS
1295	n/a	if (narenas_currently_allocated >= MAX_ARENAS) {
1296	n/a	UNLOCK();
1297	n/a	goto redirect;
1298	n/a	}
1299	n/a	#endif
1300	n/a	usable_arenas = new_arena();
1301	n/a	if (usable_arenas == NULL) {
1302	n/a	UNLOCK();
1303	n/a	goto redirect;
1304	n/a	}
1305	n/a	usable_arenas->nextarena =
1306	n/a	usable_arenas->prevarena = NULL;
1307	n/a	}
1308	n/a	assert(usable_arenas->address != 0);
1309	n/a
1310	n/a	/* Try to get a cached free pool. */
1311	n/a	pool = usable_arenas->freepools;
1312	n/a	if (pool != NULL) {
1313	n/a	/* Unlink from cached pools. */
1314	n/a	usable_arenas->freepools = pool->nextpool;
1315	n/a
1316	n/a	/* This arena already had the smallest nfreepools
1317	n/a	* value, so decreasing nfreepools doesn't change
1318	n/a	* that, and we don't need to rearrange the
1319	n/a	* usable_arenas list. However, if the arena has
1320	n/a	* become wholly allocated, we need to remove its
1321	n/a	* arena_object from usable_arenas.
1322	n/a	*/
1323	n/a	--usable_arenas->nfreepools;
1324	n/a	if (usable_arenas->nfreepools == 0) {
1325	n/a	/* Wholly allocated: remove. */
1326	n/a	assert(usable_arenas->freepools == NULL);
1327	n/a	assert(usable_arenas->nextarena == NULL \|\|
1328	n/a	usable_arenas->nextarena->prevarena ==
1329	n/a	usable_arenas);
1330	n/a
1331	n/a	usable_arenas = usable_arenas->nextarena;
1332	n/a	if (usable_arenas != NULL) {
1333	n/a	usable_arenas->prevarena = NULL;
1334	n/a	assert(usable_arenas->address != 0);
1335	n/a	}
1336	n/a	}
1337	n/a	else {
1338	n/a	/* nfreepools > 0: it must be that freepools
1339	n/a	* isn't NULL, or that we haven't yet carved
1340	n/a	* off all the arena's pools for the first
1341	n/a	* time.
1342	n/a	*/
1343	n/a	assert(usable_arenas->freepools != NULL \|\|
1344	n/a	usable_arenas->pool_address <=
1345	n/a	(block*)usable_arenas->address +
1346	n/a	ARENA_SIZE - POOL_SIZE);
1347	n/a	}
1348	n/a	init_pool:
1349	n/a	/* Frontlink to used pools. */
1350	n/a	next = usedpools[size + size]; /* == prev */
1351	n/a	pool->nextpool = next;
1352	n/a	pool->prevpool = next;
1353	n/a	next->nextpool = pool;
1354	n/a	next->prevpool = pool;
1355	n/a	pool->ref.count = 1;
1356	n/a	if (pool->szidx == size) {
1357	n/a	/* Luckily, this pool last contained blocks
1358	n/a	* of the same size class, so its header
1359	n/a	* and free list are already initialized.
1360	n/a	*/
1361	n/a	bp = pool->freeblock;
1362	n/a	assert(bp != NULL);
1363	n/a	pool->freeblock = (block *)bp;
1364	n/a	UNLOCK();
1365	n/a	if (use_calloc)
1366	n/a	memset(bp, 0, nbytes);
1367	n/a	return (void *)bp;
1368	n/a	}
1369	n/a	/*
1370	n/a	* Initialize the pool header, set up the free list to
1371	n/a	* contain just the second block, and return the first
1372	n/a	* block.
1373	n/a	*/
1374	n/a	pool->szidx = size;
1375	n/a	size = INDEX2SIZE(size);
1376	n/a	bp = (block *)pool + POOL_OVERHEAD;
1377	n/a	pool->nextoffset = POOL_OVERHEAD + (size << 1);
1378	n/a	pool->maxnextoffset = POOL_SIZE - size;
1379	n/a	pool->freeblock = bp + size;
1380	n/a	(block *)(pool->freeblock) = NULL;
1381	n/a	UNLOCK();
1382	n/a	if (use_calloc)
1383	n/a	memset(bp, 0, nbytes);
1384	n/a	return (void *)bp;
1385	n/a	}
1386	n/a
1387	n/a	/* Carve off a new pool. */
1388	n/a	assert(usable_arenas->nfreepools > 0);
1389	n/a	assert(usable_arenas->freepools == NULL);
1390	n/a	pool = (poolp)usable_arenas->pool_address;
1391	n/a	assert((block)pool <= (block)usable_arenas->address +
1392	n/a	ARENA_SIZE - POOL_SIZE);
1393	n/a	pool->arenaindex = (uint)(usable_arenas - arenas);
1394	n/a	assert(&arenas[pool->arenaindex] == usable_arenas);
1395	n/a	pool->szidx = DUMMY_SIZE_IDX;
1396	n/a	usable_arenas->pool_address += POOL_SIZE;
1397	n/a	--usable_arenas->nfreepools;
1398	n/a
1399	n/a	if (usable_arenas->nfreepools == 0) {
1400	n/a	assert(usable_arenas->nextarena == NULL \|\|
1401	n/a	usable_arenas->nextarena->prevarena ==
1402	n/a	usable_arenas);
1403	n/a	/* Unlink the arena: it is completely allocated. */
1404	n/a	usable_arenas = usable_arenas->nextarena;
1405	n/a	if (usable_arenas != NULL) {
1406	n/a	usable_arenas->prevarena = NULL;
1407	n/a	assert(usable_arenas->address != 0);
1408	n/a	}
1409	n/a	}
1410	n/a
1411	n/a	goto init_pool;
1412	n/a	}
1413	n/a
1414	n/a	/* The small block allocator ends here. */
1415	n/a
1416	n/a	redirect:
1417	n/a	/* Redirect the original request to the underlying (libc) allocator.
1418	n/a	* We jump here on bigger requests, on error in the code above (as a
1419	n/a	* last chance to serve the request) or when the max memory limit
1420	n/a	* has been reached.
1421	n/a	*/
1422	n/a	{
1423	n/a	void *result;
1424	n/a	if (use_calloc)
1425	n/a	result = PyMem_RawCalloc(nelem, elsize);
1426	n/a	else
1427	n/a	result = PyMem_RawMalloc(nbytes);
1428	n/a	if (!result)
1429	n/a	_Py_AllocatedBlocks--;
1430	n/a	return result;
1431	n/a	}
1432	n/a	}
1433	n/a
1434	n/a	static void *
1435	n/a	_PyObject_Malloc(void *ctx, size_t nbytes)
1436	n/a	{
1437	n/a	return _PyObject_Alloc(0, ctx, 1, nbytes);
1438	n/a	}
1439	n/a
1440	n/a	static void *
1441	n/a	_PyObject_Calloc(void *ctx, size_t nelem, size_t elsize)
1442	n/a	{
1443	n/a	return _PyObject_Alloc(1, ctx, nelem, elsize);
1444	n/a	}
1445	n/a
1446	n/a	/* free */
1447	n/a
1448	n/a	static void
1449	n/a	_PyObject_Free(void ctx, void p)
1450	n/a	{
1451	n/a	poolp pool;
1452	n/a	block *lastfree;
1453	n/a	poolp next, prev;
1454	n/a	uint size;
1455	n/a
1456	n/a	if (p == NULL) /* free(NULL) has no effect */
1457	n/a	return;
1458	n/a
1459	n/a	_Py_AllocatedBlocks--;
1460	n/a
1461	n/a	#ifdef WITH_VALGRIND
1462	n/a	if (UNLIKELY(running_on_valgrind > 0))
1463	n/a	goto redirect;
1464	n/a	#endif
1465	n/a
1466	n/a	pool = POOL_ADDR(p);
1467	n/a	if (address_in_range(p, pool)) {
1468	n/a	/* We allocated this address. */
1469	n/a	LOCK();
1470	n/a	/* Link p to the start of the pool's freeblock list. Since
1471	n/a	* the pool had at least the p block outstanding, the pool
1472	n/a	* wasn't empty (so it's already in a usedpools[] list, or
1473	n/a	* was full and is in no list -- it's not in the freeblocks
1474	n/a	* list in any case).
1475	n/a	*/
1476	n/a	assert(pool->ref.count > 0); /* else it was empty */
1477	n/a	(block *)p = lastfree = pool->freeblock;
1478	n/a	pool->freeblock = (block *)p;
1479	n/a	if (lastfree) {
1480	n/a	struct arena_object* ao;
1481	n/a	uint nf; /* ao->nfreepools */
1482	n/a
1483	n/a	/* freeblock wasn't NULL, so the pool wasn't full,
1484	n/a	* and the pool is in a usedpools[] list.
1485	n/a	*/
1486	n/a	if (--pool->ref.count != 0) {
1487	n/a	/* pool isn't empty: leave it in usedpools */
1488	n/a	UNLOCK();
1489	n/a	return;
1490	n/a	}
1491	n/a	/* Pool is now empty: unlink from usedpools, and
1492	n/a	* link to the front of freepools. This ensures that
1493	n/a	* previously freed pools will be allocated later
1494	n/a	* (being not referenced, they are perhaps paged out).
1495	n/a	*/
1496	n/a	next = pool->nextpool;
1497	n/a	prev = pool->prevpool;
1498	n/a	next->prevpool = prev;
1499	n/a	prev->nextpool = next;
1500	n/a
1501	n/a	/* Link the pool to freepools. This is a singly-linked
1502	n/a	* list, and pool->prevpool isn't used there.
1503	n/a	*/
1504	n/a	ao = &arenas[pool->arenaindex];
1505	n/a	pool->nextpool = ao->freepools;
1506	n/a	ao->freepools = pool;
1507	n/a	nf = ++ao->nfreepools;
1508	n/a
1509	n/a	/* All the rest is arena management. We just freed
1510	n/a	* a pool, and there are 4 cases for arena mgmt:
1511	n/a	* 1. If all the pools are free, return the arena to
1512	n/a	* the system free().
1513	n/a	* 2. If this is the only free pool in the arena,
1514	n/a	* add the arena back to the `usable_arenas` list.
1515	n/a	* 3. If the "next" arena has a smaller count of free
1516	n/a	* pools, we have to "slide this arena right" to
1517	n/a	* restore that usable_arenas is sorted in order of
1518	n/a	* nfreepools.
1519	n/a	* 4. Else there's nothing more to do.
1520	n/a	*/
1521	n/a	if (nf == ao->ntotalpools) {
1522	n/a	/* Case 1. First unlink ao from usable_arenas.
1523	n/a	*/
1524	n/a	assert(ao->prevarena == NULL \|\|
1525	n/a	ao->prevarena->address != 0);
1526	n/a	assert(ao ->nextarena == NULL \|\|
1527	n/a	ao->nextarena->address != 0);
1528	n/a
1529	n/a	/* Fix the pointer in the prevarena, or the
1530	n/a	* usable_arenas pointer.
1531	n/a	*/
1532	n/a	if (ao->prevarena == NULL) {
1533	n/a	usable_arenas = ao->nextarena;
1534	n/a	assert(usable_arenas == NULL \|\|
1535	n/a	usable_arenas->address != 0);
1536	n/a	}
1537	n/a	else {
1538	n/a	assert(ao->prevarena->nextarena == ao);
1539	n/a	ao->prevarena->nextarena =
1540	n/a	ao->nextarena;
1541	n/a	}
1542	n/a	/* Fix the pointer in the nextarena. */
1543	n/a	if (ao->nextarena != NULL) {
1544	n/a	assert(ao->nextarena->prevarena == ao);
1545	n/a	ao->nextarena->prevarena =
1546	n/a	ao->prevarena;
1547	n/a	}
1548	n/a	/* Record that this arena_object slot is
1549	n/a	* available to be reused.
1550	n/a	*/
1551	n/a	ao->nextarena = unused_arena_objects;
1552	n/a	unused_arena_objects = ao;
1553	n/a
1554	n/a	/* Free the entire arena. */
1555	n/a	_PyObject_Arena.free(_PyObject_Arena.ctx,
1556	n/a	(void *)ao->address, ARENA_SIZE);
1557	n/a	ao->address = 0; /* mark unassociated */
1558	n/a	--narenas_currently_allocated;
1559	n/a
1560	n/a	UNLOCK();
1561	n/a	return;
1562	n/a	}
1563	n/a	if (nf == 1) {
1564	n/a	/* Case 2. Put ao at the head of
1565	n/a	* usable_arenas. Note that because
1566	n/a	* ao->nfreepools was 0 before, ao isn't
1567	n/a	* currently on the usable_arenas list.
1568	n/a	*/
1569	n/a	ao->nextarena = usable_arenas;
1570	n/a	ao->prevarena = NULL;
1571	n/a	if (usable_arenas)
1572	n/a	usable_arenas->prevarena = ao;
1573	n/a	usable_arenas = ao;
1574	n/a	assert(usable_arenas->address != 0);
1575	n/a
1576	n/a	UNLOCK();
1577	n/a	return;
1578	n/a	}
1579	n/a	/* If this arena is now out of order, we need to keep
1580	n/a	* the list sorted. The list is kept sorted so that
1581	n/a	* the "most full" arenas are used first, which allows
1582	n/a	* the nearly empty arenas to be completely freed. In
1583	n/a	* a few un-scientific tests, it seems like this
1584	n/a	* approach allowed a lot more memory to be freed.
1585	n/a	*/
1586	n/a	if (ao->nextarena == NULL \|\|
1587	n/a	nf <= ao->nextarena->nfreepools) {
1588	n/a	/* Case 4. Nothing to do. */
1589	n/a	UNLOCK();
1590	n/a	return;
1591	n/a	}
1592	n/a	/* Case 3: We have to move the arena towards the end
1593	n/a	* of the list, because it has more free pools than
1594	n/a	* the arena to its right.
1595	n/a	* First unlink ao from usable_arenas.
1596	n/a	*/
1597	n/a	if (ao->prevarena != NULL) {
1598	n/a	/* ao isn't at the head of the list */
1599	n/a	assert(ao->prevarena->nextarena == ao);
1600	n/a	ao->prevarena->nextarena = ao->nextarena;
1601	n/a	}
1602	n/a	else {
1603	n/a	/* ao is at the head of the list */
1604	n/a	assert(usable_arenas == ao);
1605	n/a	usable_arenas = ao->nextarena;
1606	n/a	}
1607	n/a	ao->nextarena->prevarena = ao->prevarena;
1608	n/a
1609	n/a	/* Locate the new insertion point by iterating over
1610	n/a	* the list, using our nextarena pointer.
1611	n/a	*/
1612	n/a	while (ao->nextarena != NULL &&
1613	n/a	nf > ao->nextarena->nfreepools) {
1614	n/a	ao->prevarena = ao->nextarena;
1615	n/a	ao->nextarena = ao->nextarena->nextarena;
1616	n/a	}
1617	n/a
1618	n/a	/* Insert ao at this point. */
1619	n/a	assert(ao->nextarena == NULL \|\|
1620	n/a	ao->prevarena == ao->nextarena->prevarena);
1621	n/a	assert(ao->prevarena->nextarena == ao->nextarena);
1622	n/a
1623	n/a	ao->prevarena->nextarena = ao;
1624	n/a	if (ao->nextarena != NULL)
1625	n/a	ao->nextarena->prevarena = ao;
1626	n/a
1627	n/a	/* Verify that the swaps worked. */
1628	n/a	assert(ao->nextarena == NULL \|\|
1629	n/a	nf <= ao->nextarena->nfreepools);
1630	n/a	assert(ao->prevarena == NULL \|\|
1631	n/a	nf > ao->prevarena->nfreepools);
1632	n/a	assert(ao->nextarena == NULL \|\|
1633	n/a	ao->nextarena->prevarena == ao);
1634	n/a	assert((usable_arenas == ao &&
1635	n/a	ao->prevarena == NULL) \|\|
1636	n/a	ao->prevarena->nextarena == ao);
1637	n/a
1638	n/a	UNLOCK();
1639	n/a	return;
1640	n/a	}
1641	n/a	/* Pool was full, so doesn't currently live in any list:
1642	n/a	* link it to the front of the appropriate usedpools[] list.
1643	n/a	* This mimics LRU pool usage for new allocations and
1644	n/a	* targets optimal filling when several pools contain
1645	n/a	* blocks of the same size class.
1646	n/a	*/
1647	n/a	--pool->ref.count;
1648	n/a	assert(pool->ref.count > 0); /* else the pool is empty */
1649	n/a	size = pool->szidx;
1650	n/a	next = usedpools[size + size];
1651	n/a	prev = next->prevpool;
1652	n/a	/* insert pool before next: prev <-> pool <-> next */
1653	n/a	pool->nextpool = next;
1654	n/a	pool->prevpool = prev;
1655	n/a	next->prevpool = pool;
1656	n/a	prev->nextpool = pool;
1657	n/a	UNLOCK();
1658	n/a	return;
1659	n/a	}
1660	n/a
1661	n/a	#ifdef WITH_VALGRIND
1662	n/a	redirect:
1663	n/a	#endif
1664	n/a	/* We didn't allocate this address. */
1665	n/a	PyMem_RawFree(p);
1666	n/a	}
1667	n/a
1668	n/a	/* realloc. If p is NULL, this acts like malloc(nbytes). Else if nbytes==0,
1669	n/a	* then as the Python docs promise, we do not treat this like free(p), and
1670	n/a	* return a non-NULL result.
1671	n/a	*/
1672	n/a
1673	n/a	static void *
1674	n/a	_PyObject_Realloc(void ctx, void p, size_t nbytes)
1675	n/a	{
1676	n/a	void *bp;
1677	n/a	poolp pool;
1678	n/a	size_t size;
1679	n/a
1680	n/a	if (p == NULL)
1681	n/a	return _PyObject_Alloc(0, ctx, 1, nbytes);
1682	n/a
1683	n/a	#ifdef WITH_VALGRIND
1684	n/a	/* Treat running_on_valgrind == -1 the same as 0 */
1685	n/a	if (UNLIKELY(running_on_valgrind > 0))
1686	n/a	goto redirect;
1687	n/a	#endif
1688	n/a
1689	n/a	pool = POOL_ADDR(p);
1690	n/a	if (address_in_range(p, pool)) {
1691	n/a	/* We're in charge of this block */
1692	n/a	size = INDEX2SIZE(pool->szidx);
1693	n/a	if (nbytes <= size) {
1694	n/a	/* The block is staying the same or shrinking. If
1695	n/a	* it's shrinking, there's a tradeoff: it costs
1696	n/a	* cycles to copy the block to a smaller size class,
1697	n/a	* but it wastes memory not to copy it. The
1698	n/a	* compromise here is to copy on shrink only if at
1699	n/a	* least 25% of size can be shaved off.
1700	n/a	*/
1701	n/a	if (4 * nbytes > 3 * size) {
1702	n/a	/* It's the same,
1703	n/a	* or shrinking and new/old > 3/4.
1704	n/a	*/
1705	n/a	return p;
1706	n/a	}
1707	n/a	size = nbytes;
1708	n/a	}
1709	n/a	bp = _PyObject_Alloc(0, ctx, 1, nbytes);
1710	n/a	if (bp != NULL) {
1711	n/a	memcpy(bp, p, size);
1712	n/a	_PyObject_Free(ctx, p);
1713	n/a	}
1714	n/a	return bp;
1715	n/a	}
1716	n/a	#ifdef WITH_VALGRIND
1717	n/a	redirect:
1718	n/a	#endif
1719	n/a	/* We're not managing this block. If nbytes <=
1720	n/a	* SMALL_REQUEST_THRESHOLD, it's tempting to try to take over this
1721	n/a	* block. However, if we do, we need to copy the valid data from
1722	n/a	* the C-managed block to one of our blocks, and there's no portable
1723	n/a	* way to know how much of the memory space starting at p is valid.
1724	n/a	* As bug 1185883 pointed out the hard way, it's possible that the
1725	n/a	* C-managed block is "at the end" of allocated VM space, so that
1726	n/a	* a memory fault can occur if we try to copy nbytes bytes starting
1727	n/a	* at p. Instead we punt: let C continue to manage this block.
1728	n/a	*/
1729	n/a	if (nbytes)
1730	n/a	return PyMem_RawRealloc(p, nbytes);
1731	n/a	/* C doesn't define the result of realloc(p, 0) (it may or may not
1732	n/a	* return NULL then), but Python's docs promise that nbytes==0 never
1733	n/a	* returns NULL. We don't pass 0 to realloc(), to avoid that endcase
1734	n/a	* to begin with. Even then, we can't be sure that realloc() won't
1735	n/a	* return NULL.
1736	n/a	*/
1737	n/a	bp = PyMem_RawRealloc(p, 1);
1738	n/a	return bp ? bp : p;
1739	n/a	}
1740	n/a
1741	n/a	#else /* ! WITH_PYMALLOC */
1742	n/a
1743	n/a	/==========================================================================/
1744	n/a	/* pymalloc not enabled: Redirect the entry points to malloc. These will
1745	n/a	* only be used by extensions that are compiled with pymalloc enabled. */
1746	n/a
1747	n/a	Py_ssize_t
1748	n/a	_Py_GetAllocatedBlocks(void)
1749	n/a	{
1750	n/a	return 0;
1751	n/a	}
1752	n/a
1753	n/a	#endif /* WITH_PYMALLOC */
1754	n/a
1755	n/a
1756	n/a	/==========================================================================/
1757	n/a	/* A x-platform debugging allocator. This doesn't manage memory directly,
1758	n/a	* it wraps a real allocator, adding extra debugging info to the memory blocks.
1759	n/a	*/
1760	n/a
1761	n/a	/* Special bytes broadcast into debug memory blocks at appropriate times.
1762	n/a	* Strings of these are unlikely to be valid addresses, floats, ints or
1763	n/a	* 7-bit ASCII.
1764	n/a	*/
1765	n/a	#undef CLEANBYTE
1766	n/a	#undef DEADBYTE
1767	n/a	#undef FORBIDDENBYTE
1768	n/a	#define CLEANBYTE 0xCB /* clean (newly allocated) memory */
1769	n/a	#define DEADBYTE 0xDB /* dead (newly freed) memory */
1770	n/a	#define FORBIDDENBYTE 0xFB /* untouchable bytes at each end of a block */
1771	n/a
1772	n/a	static size_t serialno = 0; /* incremented on each debug {m,re}alloc */
1773	n/a
1774	n/a	/* serialno is always incremented via calling this routine. The point is
1775	n/a	* to supply a single place to set a breakpoint.
1776	n/a	*/
1777	n/a	static void
1778	n/a	bumpserialno(void)
1779	n/a	{
1780	n/a	++serialno;
1781	n/a	}
1782	n/a
1783	n/a	#define SST SIZEOF_SIZE_T
1784	n/a
1785	n/a	/* Read sizeof(size_t) bytes at p as a big-endian size_t. */
1786	n/a	static size_t
1787	n/a	read_size_t(const void *p)
1788	n/a	{
1789	n/a	const uint8_t q = (const uint8_t )p;
1790	n/a	size_t result = *q++;
1791	n/a	int i;
1792	n/a
1793	n/a	for (i = SST; --i > 0; ++q)
1794	n/a	result = (result << 8) \| *q;
1795	n/a	return result;
1796	n/a	}
1797	n/a
1798	n/a	/* Write n as a big-endian size_t, MSB at address p, LSB at
1799	n/a	* p + sizeof(size_t) - 1.
1800	n/a	*/
1801	n/a	static void
1802	n/a	write_size_t(void *p, size_t n)
1803	n/a	{
1804	n/a	uint8_t q = (uint8_t )p + SST - 1;
1805	n/a	int i;
1806	n/a
1807	n/a	for (i = SST; --i >= 0; --q) {
1808	n/a	*q = (uint8_t)(n & 0xff);
1809	n/a	n >>= 8;
1810	n/a	}
1811	n/a	}
1812	n/a
1813	n/a	/* Let S = sizeof(size_t). The debug malloc asks for 4*S extra bytes and
1814	n/a	fills them with useful stuff, here calling the underlying malloc's result p:
1815	n/a
1816	n/a	p[0: S]
1817	n/a	Number of bytes originally asked for. This is a size_t, big-endian (easier
1818	n/a	to read in a memory dump).
1819	n/a	p[S]
1820	n/a	API ID. See PEP 445. This is a character, but seems undocumented.
1821	n/a	p[S+1: 2*S]
1822	n/a	Copies of FORBIDDENBYTE. Used to catch under- writes and reads.
1823	n/a	p[2S: 2S+n]
1824	n/a	The requested memory, filled with copies of CLEANBYTE.
1825	n/a	Used to catch reference to uninitialized memory.
1826	n/a	&p[2*S] is returned. Note that this is 8-byte aligned if pymalloc
1827	n/a	handled the request itself.
1828	n/a	p[2S+n: 2S+n+S]
1829	n/a	Copies of FORBIDDENBYTE. Used to catch over- writes and reads.
1830	n/a	p[2S+n+S: 2S+n+2*S]
1831	n/a	A serial number, incremented by 1 on each call to _PyMem_DebugMalloc
1832	n/a	and _PyMem_DebugRealloc.
1833	n/a	This is a big-endian size_t.
1834	n/a	If "bad memory" is detected later, the serial number gives an
1835	n/a	excellent way to set a breakpoint on the next run, to capture the
1836	n/a	instant at which this block was passed out.
1837	n/a	*/
1838	n/a
1839	n/a	static void *
1840	n/a	_PyMem_DebugRawAlloc(int use_calloc, void *ctx, size_t nbytes)
1841	n/a	{
1842	n/a	debug_alloc_api_t api = (debug_alloc_api_t )ctx;
1843	n/a	uint8_t p; / base address of malloc'ed block */
1844	n/a	uint8_t tail; / p + 2SST + nbytes == pointer to tail pad bytes /
1845	n/a	size_t total; /* nbytes + 4SST /
1846	n/a
1847	n/a	bumpserialno();
1848	n/a	total = nbytes + 4*SST;
1849	n/a	if (nbytes > PY_SSIZE_T_MAX - 4*SST)
1850	n/a	/* overflow: can't represent total as a Py_ssize_t */
1851	n/a	return NULL;
1852	n/a
1853	n/a	if (use_calloc)
1854	n/a	p = (uint8_t *)api->alloc.calloc(api->alloc.ctx, 1, total);
1855	n/a	else
1856	n/a	p = (uint8_t *)api->alloc.malloc(api->alloc.ctx, total);
1857	n/a	if (p == NULL)
1858	n/a	return NULL;
1859	n/a
1860	n/a	/* at p, write size (SST bytes), id (1 byte), pad (SST-1 bytes) */
1861	n/a	write_size_t(p, nbytes);
1862	n/a	p[SST] = (uint8_t)api->api_id;
1863	n/a	memset(p + SST + 1, FORBIDDENBYTE, SST-1);
1864	n/a
1865	n/a	if (nbytes > 0 && !use_calloc)
1866	n/a	memset(p + 2*SST, CLEANBYTE, nbytes);
1867	n/a
1868	n/a	/* at tail, write pad (SST bytes) and serialno (SST bytes) */
1869	n/a	tail = p + 2*SST + nbytes;
1870	n/a	memset(tail, FORBIDDENBYTE, SST);
1871	n/a	write_size_t(tail + SST, serialno);
1872	n/a
1873	n/a	return p + 2*SST;
1874	n/a	}
1875	n/a
1876	n/a	static void *
1877	n/a	_PyMem_DebugRawMalloc(void *ctx, size_t nbytes)
1878	n/a	{
1879	n/a	return _PyMem_DebugRawAlloc(0, ctx, nbytes);
1880	n/a	}
1881	n/a
1882	n/a	static void *
1883	n/a	_PyMem_DebugRawCalloc(void *ctx, size_t nelem, size_t elsize)
1884	n/a	{
1885	n/a	size_t nbytes;
1886	n/a	assert(elsize == 0 \|\| nelem <= PY_SSIZE_T_MAX / elsize);
1887	n/a	nbytes = nelem * elsize;
1888	n/a	return _PyMem_DebugRawAlloc(1, ctx, nbytes);
1889	n/a	}
1890	n/a
1891	n/a	/* The debug free first checks the 2*SST bytes on each end for sanity (in
1892	n/a	particular, that the FORBIDDENBYTEs with the api ID are still intact).
1893	n/a	Then fills the original bytes with DEADBYTE.
1894	n/a	Then calls the underlying free.
1895	n/a	*/
1896	n/a	static void
1897	n/a	_PyMem_DebugRawFree(void ctx, void p)
1898	n/a	{
1899	n/a	debug_alloc_api_t api = (debug_alloc_api_t )ctx;
1900	n/a	uint8_t q = (uint8_t )p - 2SST; / address returned from malloc */
1901	n/a	size_t nbytes;
1902	n/a
1903	n/a	if (p == NULL)
1904	n/a	return;
1905	n/a	_PyMem_DebugCheckAddress(api->api_id, p);
1906	n/a	nbytes = read_size_t(q);
1907	n/a	nbytes += 4*SST;
1908	n/a	if (nbytes > 0)
1909	n/a	memset(q, DEADBYTE, nbytes);
1910	n/a	api->alloc.free(api->alloc.ctx, q);
1911	n/a	}
1912	n/a
1913	n/a	static void *
1914	n/a	_PyMem_DebugRawRealloc(void ctx, void p, size_t nbytes)
1915	n/a	{
1916	n/a	debug_alloc_api_t api = (debug_alloc_api_t )ctx;
1917	n/a	uint8_t q = (uint8_t )p, *oldq;
1918	n/a	uint8_t *tail;
1919	n/a	size_t total; /* nbytes + 4SST /
1920	n/a	size_t original_nbytes;
1921	n/a	int i;
1922	n/a
1923	n/a	if (p == NULL)
1924	n/a	return _PyMem_DebugRawAlloc(0, ctx, nbytes);
1925	n/a
1926	n/a	_PyMem_DebugCheckAddress(api->api_id, p);
1927	n/a	bumpserialno();
1928	n/a	original_nbytes = read_size_t(q - 2*SST);
1929	n/a	total = nbytes + 4*SST;
1930	n/a	if (nbytes > PY_SSIZE_T_MAX - 4*SST)
1931	n/a	/* overflow: can't represent total as a Py_ssize_t */
1932	n/a	return NULL;
1933	n/a
1934	n/a	/* Resize and add decorations. We may get a new pointer here, in which
1935	n/a	* case we didn't get the chance to mark the old memory with DEADBYTE,
1936	n/a	* but we live with that.
1937	n/a	*/
1938	n/a	oldq = q;
1939	n/a	q = (uint8_t )api->alloc.realloc(api->alloc.ctx, q - 2SST, total);
1940	n/a	if (q == NULL)
1941	n/a	return NULL;
1942	n/a
1943	n/a	if (q == oldq && nbytes < original_nbytes) {
1944	n/a	/* shrinking: mark old extra memory dead */
1945	n/a	memset(q + nbytes, DEADBYTE, original_nbytes - nbytes);
1946	n/a	}
1947	n/a
1948	n/a	write_size_t(q, nbytes);
1949	n/a	assert(q[SST] == (uint8_t)api->api_id);
1950	n/a	for (i = 1; i < SST; ++i)
1951	n/a	assert(q[SST + i] == FORBIDDENBYTE);
1952	n/a	q += 2*SST;
1953	n/a
1954	n/a	tail = q + nbytes;
1955	n/a	memset(tail, FORBIDDENBYTE, SST);
1956	n/a	write_size_t(tail + SST, serialno);
1957	n/a
1958	n/a	if (nbytes > original_nbytes) {
1959	n/a	/* growing: mark new extra memory clean */
1960	n/a	memset(q + original_nbytes, CLEANBYTE,
1961	n/a	nbytes - original_nbytes);
1962	n/a	}
1963	n/a
1964	n/a	return q;
1965	n/a	}
1966	n/a
1967	n/a	static void
1968	n/a	_PyMem_DebugCheckGIL(void)
1969	n/a	{
1970	n/a	#ifdef WITH_THREAD
1971	n/a	if (!PyGILState_Check())
1972	n/a	Py_FatalError("Python memory allocator called "
1973	n/a	"without holding the GIL");
1974	n/a	#endif
1975	n/a	}
1976	n/a
1977	n/a	static void *
1978	n/a	_PyMem_DebugMalloc(void *ctx, size_t nbytes)
1979	n/a	{
1980	n/a	_PyMem_DebugCheckGIL();
1981	n/a	return _PyMem_DebugRawMalloc(ctx, nbytes);
1982	n/a	}
1983	n/a
1984	n/a	static void *
1985	n/a	_PyMem_DebugCalloc(void *ctx, size_t nelem, size_t elsize)
1986	n/a	{
1987	n/a	_PyMem_DebugCheckGIL();
1988	n/a	return _PyMem_DebugRawCalloc(ctx, nelem, elsize);
1989	n/a	}
1990	n/a
1991	n/a	static void
1992	n/a	_PyMem_DebugFree(void ctx, void ptr)
1993	n/a	{
1994	n/a	_PyMem_DebugCheckGIL();
1995	n/a	_PyMem_DebugRawFree(ctx, ptr);
1996	n/a	}
1997	n/a
1998	n/a	static void *
1999	n/a	_PyMem_DebugRealloc(void ctx, void ptr, size_t nbytes)
2000	n/a	{
2001	n/a	_PyMem_DebugCheckGIL();
2002	n/a	return _PyMem_DebugRawRealloc(ctx, ptr, nbytes);
2003	n/a	}
2004	n/a
2005	n/a	/* Check the forbidden bytes on both ends of the memory allocated for p.
2006	n/a	* If anything is wrong, print info to stderr via _PyObject_DebugDumpAddress,
2007	n/a	* and call Py_FatalError to kill the program.
2008	n/a	* The API id, is also checked.
2009	n/a	*/
2010	n/a	static void
2011	n/a	_PyMem_DebugCheckAddress(char api, const void *p)
2012	n/a	{
2013	n/a	const uint8_t q = (const uint8_t )p;
2014	n/a	char msgbuf[64];
2015	n/a	char *msg;
2016	n/a	size_t nbytes;
2017	n/a	const uint8_t *tail;
2018	n/a	int i;
2019	n/a	char id;
2020	n/a
2021	n/a	if (p == NULL) {
2022	n/a	msg = "didn't expect a NULL pointer";
2023	n/a	goto error;
2024	n/a	}
2025	n/a
2026	n/a	/* Check the API id */
2027	n/a	id = (char)q[-SST];
2028	n/a	if (id != api) {
2029	n/a	msg = msgbuf;
2030	n/a	snprintf(msg, sizeof(msgbuf), "bad ID: Allocated using API '%c', verified using API '%c'", id, api);
2031	n/a	msgbuf[sizeof(msgbuf)-1] = 0;
2032	n/a	goto error;
2033	n/a	}
2034	n/a
2035	n/a	/* Check the stuff at the start of p first: if there's underwrite
2036	n/a	* corruption, the number-of-bytes field may be nuts, and checking
2037	n/a	* the tail could lead to a segfault then.
2038	n/a	*/
2039	n/a	for (i = SST-1; i >= 1; --i) {
2040	n/a	if (*(q-i) != FORBIDDENBYTE) {
2041	n/a	msg = "bad leading pad byte";
2042	n/a	goto error;
2043	n/a	}
2044	n/a	}
2045	n/a
2046	n/a	nbytes = read_size_t(q - 2*SST);
2047	n/a	tail = q + nbytes;
2048	n/a	for (i = 0; i < SST; ++i) {
2049	n/a	if (tail[i] != FORBIDDENBYTE) {
2050	n/a	msg = "bad trailing pad byte";
2051	n/a	goto error;
2052	n/a	}
2053	n/a	}
2054	n/a
2055	n/a	return;
2056	n/a
2057	n/a	error:
2058	n/a	_PyObject_DebugDumpAddress(p);
2059	n/a	Py_FatalError(msg);
2060	n/a	}
2061	n/a
2062	n/a	/* Display info to stderr about the memory block at p. */
2063	n/a	static void
2064	n/a	_PyObject_DebugDumpAddress(const void *p)
2065	n/a	{
2066	n/a	const uint8_t q = (const uint8_t )p;
2067	n/a	const uint8_t *tail;
2068	n/a	size_t nbytes, serial;
2069	n/a	int i;
2070	n/a	int ok;
2071	n/a	char id;
2072	n/a
2073	n/a	fprintf(stderr, "Debug memory block at address p=%p:", p);
2074	n/a	if (p == NULL) {
2075	n/a	fprintf(stderr, "\n");
2076	n/a	return;
2077	n/a	}
2078	n/a	id = (char)q[-SST];
2079	n/a	fprintf(stderr, " API '%c'\n", id);
2080	n/a
2081	n/a	nbytes = read_size_t(q - 2*SST);
2082	n/a	fprintf(stderr, " %" PY_FORMAT_SIZE_T "u bytes originally "
2083	n/a	"requested\n", nbytes);
2084	n/a
2085	n/a	/* In case this is nuts, check the leading pad bytes first. */
2086	n/a	fprintf(stderr, " The %d pad bytes at p-%d are ", SST-1, SST-1);
2087	n/a	ok = 1;
2088	n/a	for (i = 1; i <= SST-1; ++i) {
2089	n/a	if (*(q-i) != FORBIDDENBYTE) {
2090	n/a	ok = 0;
2091	n/a	break;
2092	n/a	}
2093	n/a	}
2094	n/a	if (ok)
2095	n/a	fputs("FORBIDDENBYTE, as expected.\n", stderr);
2096	n/a	else {
2097	n/a	fprintf(stderr, "not all FORBIDDENBYTE (0x%02x):\n",
2098	n/a	FORBIDDENBYTE);
2099	n/a	for (i = SST-1; i >= 1; --i) {
2100	n/a	const uint8_t byte = *(q-i);
2101	n/a	fprintf(stderr, " at p-%d: 0x%02x", i, byte);
2102	n/a	if (byte != FORBIDDENBYTE)
2103	n/a	fputs(" *** OUCH", stderr);
2104	n/a	fputc('\n', stderr);
2105	n/a	}
2106	n/a
2107	n/a	fputs(" Because memory is corrupted at the start, the "
2108	n/a	"count of bytes requested\n"
2109	n/a	" may be bogus, and checking the trailing pad "
2110	n/a	"bytes may segfault.\n", stderr);
2111	n/a	}
2112	n/a
2113	n/a	tail = q + nbytes;
2114	n/a	fprintf(stderr, " The %d pad bytes at tail=%p are ", SST, tail);
2115	n/a	ok = 1;
2116	n/a	for (i = 0; i < SST; ++i) {
2117	n/a	if (tail[i] != FORBIDDENBYTE) {
2118	n/a	ok = 0;
2119	n/a	break;
2120	n/a	}
2121	n/a	}
2122	n/a	if (ok)
2123	n/a	fputs("FORBIDDENBYTE, as expected.\n", stderr);
2124	n/a	else {
2125	n/a	fprintf(stderr, "not all FORBIDDENBYTE (0x%02x):\n",
2126	n/a	FORBIDDENBYTE);
2127	n/a	for (i = 0; i < SST; ++i) {
2128	n/a	const uint8_t byte = tail[i];
2129	n/a	fprintf(stderr, " at tail+%d: 0x%02x",
2130	n/a	i, byte);
2131	n/a	if (byte != FORBIDDENBYTE)
2132	n/a	fputs(" *** OUCH", stderr);
2133	n/a	fputc('\n', stderr);
2134	n/a	}
2135	n/a	}
2136	n/a
2137	n/a	serial = read_size_t(tail + SST);
2138	n/a	fprintf(stderr, " The block was made by call #%" PY_FORMAT_SIZE_T
2139	n/a	"u to debug malloc/realloc.\n", serial);
2140	n/a
2141	n/a	if (nbytes > 0) {
2142	n/a	i = 0;
2143	n/a	fputs(" Data at p:", stderr);
2144	n/a	/* print up to 8 bytes at the start */
2145	n/a	while (q < tail && i < 8) {
2146	n/a	fprintf(stderr, " %02x", *q);
2147	n/a	++i;
2148	n/a	++q;
2149	n/a	}
2150	n/a	/* and up to 8 at the end */
2151	n/a	if (q < tail) {
2152	n/a	if (tail - q > 8) {
2153	n/a	fputs(" ...", stderr);
2154	n/a	q = tail - 8;
2155	n/a	}
2156	n/a	while (q < tail) {
2157	n/a	fprintf(stderr, " %02x", *q);
2158	n/a	++q;
2159	n/a	}
2160	n/a	}
2161	n/a	fputc('\n', stderr);
2162	n/a	}
2163	n/a	fputc('\n', stderr);
2164	n/a
2165	n/a	fflush(stderr);
2166	n/a	_PyMem_DumpTraceback(fileno(stderr), p);
2167	n/a	}
2168	n/a
2169	n/a
2170	n/a	static size_t
2171	n/a	printone(FILE out, const char msg, size_t value)
2172	n/a	{
2173	n/a	int i, k;
2174	n/a	char buf[100];
2175	n/a	size_t origvalue = value;
2176	n/a
2177	n/a	fputs(msg, out);
2178	n/a	for (i = (int)strlen(msg); i < 35; ++i)
2179	n/a	fputc(' ', out);
2180	n/a	fputc('=', out);
2181	n/a
2182	n/a	/* Write the value with commas. */
2183	n/a	i = 22;
2184	n/a	buf[i--] = '\0';
2185	n/a	buf[i--] = '\n';
2186	n/a	k = 3;
2187	n/a	do {
2188	n/a	size_t nextvalue = value / 10;
2189	n/a	unsigned int digit = (unsigned int)(value - nextvalue * 10);
2190	n/a	value = nextvalue;
2191	n/a	buf[i--] = (char)(digit + '0');
2192	n/a	--k;
2193	n/a	if (k == 0 && value && i >= 0) {
2194	n/a	k = 3;
2195	n/a	buf[i--] = ',';
2196	n/a	}
2197	n/a	} while (value && i >= 0);
2198	n/a
2199	n/a	while (i >= 0)
2200	n/a	buf[i--] = ' ';
2201	n/a	fputs(buf, out);
2202	n/a
2203	n/a	return origvalue;
2204	n/a	}
2205	n/a
2206	n/a	void
2207	n/a	_PyDebugAllocatorStats(FILE *out,
2208	n/a	const char *block_name, int num_blocks, size_t sizeof_block)
2209	n/a	{
2210	n/a	char buf1[128];
2211	n/a	char buf2[128];
2212	n/a	PyOS_snprintf(buf1, sizeof(buf1),
2213	n/a	"%d %ss * %" PY_FORMAT_SIZE_T "d bytes each",
2214	n/a	num_blocks, block_name, sizeof_block);
2215	n/a	PyOS_snprintf(buf2, sizeof(buf2),
2216	n/a	"%48s ", buf1);
2217	n/a	(void)printone(out, buf2, num_blocks * sizeof_block);
2218	n/a	}
2219	n/a
2220	n/a
2221	n/a	#ifdef WITH_PYMALLOC
2222	n/a
2223	n/a	#ifdef Py_DEBUG
2224	n/a	/* Is target in the list? The list is traversed via the nextpool pointers.
2225	n/a	* The list may be NULL-terminated, or circular. Return 1 if target is in
2226	n/a	* list, else 0.
2227	n/a	*/
2228	n/a	static int
2229	n/a	pool_is_in_list(const poolp target, poolp list)
2230	n/a	{
2231	n/a	poolp origlist = list;
2232	n/a	assert(target != NULL);
2233	n/a	if (list == NULL)
2234	n/a	return 0;
2235	n/a	do {
2236	n/a	if (target == list)
2237	n/a	return 1;
2238	n/a	list = list->nextpool;
2239	n/a	} while (list != NULL && list != origlist);
2240	n/a	return 0;
2241	n/a	}
2242	n/a	#endif
2243	n/a
2244	n/a	/* Print summary info to "out" about the state of pymalloc's structures.
2245	n/a	* In Py_DEBUG mode, also perform some expensive internal consistency
2246	n/a	* checks.
2247	n/a	*/
2248	n/a	void
2249	n/a	_PyObject_DebugMallocStats(FILE *out)
2250	n/a	{
2251	n/a	uint i;
2252	n/a	const uint numclasses = SMALL_REQUEST_THRESHOLD >> ALIGNMENT_SHIFT;
2253	n/a	/* # of pools, allocated blocks, and free blocks per class index */
2254	n/a	size_t numpools[SMALL_REQUEST_THRESHOLD >> ALIGNMENT_SHIFT];
2255	n/a	size_t numblocks[SMALL_REQUEST_THRESHOLD >> ALIGNMENT_SHIFT];
2256	n/a	size_t numfreeblocks[SMALL_REQUEST_THRESHOLD >> ALIGNMENT_SHIFT];
2257	n/a	/* total # of allocated bytes in used and full pools */
2258	n/a	size_t allocated_bytes = 0;
2259	n/a	/* total # of available bytes in used pools */
2260	n/a	size_t available_bytes = 0;
2261	n/a	/* # of free pools + pools not yet carved out of current arena */
2262	n/a	uint numfreepools = 0;
2263	n/a	/* # of bytes for arena alignment padding */
2264	n/a	size_t arena_alignment = 0;
2265	n/a	/* # of bytes in used and full pools used for pool_headers */
2266	n/a	size_t pool_header_bytes = 0;
2267	n/a	/* # of bytes in used and full pools wasted due to quantization,
2268	n/a	* i.e. the necessarily leftover space at the ends of used and
2269	n/a	* full pools.
2270	n/a	*/
2271	n/a	size_t quantization = 0;
2272	n/a	/* # of arenas actually allocated. */
2273	n/a	size_t narenas = 0;
2274	n/a	/* running total -- should equal narenas * ARENA_SIZE */
2275	n/a	size_t total;
2276	n/a	char buf[128];
2277	n/a
2278	n/a	fprintf(out, "Small block threshold = %d, in %u size classes.\n",
2279	n/a	SMALL_REQUEST_THRESHOLD, numclasses);
2280	n/a
2281	n/a	for (i = 0; i < numclasses; ++i)
2282	n/a	numpools[i] = numblocks[i] = numfreeblocks[i] = 0;
2283	n/a
2284	n/a	/* Because full pools aren't linked to from anything, it's easiest
2285	n/a	* to march over all the arenas. If we're lucky, most of the memory
2286	n/a	* will be living in full pools -- would be a shame to miss them.
2287	n/a	*/
2288	n/a	for (i = 0; i < maxarenas; ++i) {
2289	n/a	uint j;
2290	n/a	uintptr_t base = arenas[i].address;
2291	n/a
2292	n/a	/* Skip arenas which are not allocated. */
2293	n/a	if (arenas[i].address == (uintptr_t)NULL)
2294	n/a	continue;
2295	n/a	narenas += 1;
2296	n/a
2297	n/a	numfreepools += arenas[i].nfreepools;
2298	n/a
2299	n/a	/* round up to pool alignment */
2300	n/a	if (base & (uintptr_t)POOL_SIZE_MASK) {
2301	n/a	arena_alignment += POOL_SIZE;
2302	n/a	base &= ~(uintptr_t)POOL_SIZE_MASK;
2303	n/a	base += POOL_SIZE;
2304	n/a	}
2305	n/a
2306	n/a	/* visit every pool in the arena */
2307	n/a	assert(base <= (uintptr_t) arenas[i].pool_address);
2308	n/a	for (j = 0; base < (uintptr_t) arenas[i].pool_address;
2309	n/a	++j, base += POOL_SIZE) {
2310	n/a	poolp p = (poolp)base;
2311	n/a	const uint sz = p->szidx;
2312	n/a	uint freeblocks;
2313	n/a
2314	n/a	if (p->ref.count == 0) {
2315	n/a	/* currently unused */
2316	n/a	#ifdef Py_DEBUG
2317	n/a	assert(pool_is_in_list(p, arenas[i].freepools));
2318	n/a	#endif
2319	n/a	continue;
2320	n/a	}
2321	n/a	++numpools[sz];
2322	n/a	numblocks[sz] += p->ref.count;
2323	n/a	freeblocks = NUMBLOCKS(sz) - p->ref.count;
2324	n/a	numfreeblocks[sz] += freeblocks;
2325	n/a	#ifdef Py_DEBUG
2326	n/a	if (freeblocks > 0)
2327	n/a	assert(pool_is_in_list(p, usedpools[sz + sz]));
2328	n/a	#endif
2329	n/a	}
2330	n/a	}
2331	n/a	assert(narenas == narenas_currently_allocated);
2332	n/a
2333	n/a	fputc('\n', out);
2334	n/a	fputs("class size num pools blocks in use avail blocks\n"
2335	n/a	"----- ---- --------- ------------- ------------\n",
2336	n/a	out);
2337	n/a
2338	n/a	for (i = 0; i < numclasses; ++i) {
2339	n/a	size_t p = numpools[i];
2340	n/a	size_t b = numblocks[i];
2341	n/a	size_t f = numfreeblocks[i];
2342	n/a	uint size = INDEX2SIZE(i);
2343	n/a	if (p == 0) {
2344	n/a	assert(b == 0 && f == 0);
2345	n/a	continue;
2346	n/a	}
2347	n/a	fprintf(out, "%5u %6u "
2348	n/a	"%11" PY_FORMAT_SIZE_T "u "
2349	n/a	"%15" PY_FORMAT_SIZE_T "u "
2350	n/a	"%13" PY_FORMAT_SIZE_T "u\n",
2351	n/a	i, size, p, b, f);
2352	n/a	allocated_bytes += b * size;
2353	n/a	available_bytes += f * size;
2354	n/a	pool_header_bytes += p * POOL_OVERHEAD;
2355	n/a	quantization += p * ((POOL_SIZE - POOL_OVERHEAD) % size);
2356	n/a	}
2357	n/a	fputc('\n', out);
2358	n/a	if (_PyMem_DebugEnabled())
2359	n/a	(void)printone(out, "# times object malloc called", serialno);
2360	n/a	(void)printone(out, "# arenas allocated total", ntimes_arena_allocated);
2361	n/a	(void)printone(out, "# arenas reclaimed", ntimes_arena_allocated - narenas);
2362	n/a	(void)printone(out, "# arenas highwater mark", narenas_highwater);
2363	n/a	(void)printone(out, "# arenas allocated current", narenas);
2364	n/a
2365	n/a	PyOS_snprintf(buf, sizeof(buf),
2366	n/a	"%" PY_FORMAT_SIZE_T "u arenas * %d bytes/arena",
2367	n/a	narenas, ARENA_SIZE);
2368	n/a	(void)printone(out, buf, narenas * ARENA_SIZE);
2369	n/a
2370	n/a	fputc('\n', out);
2371	n/a
2372	n/a	total = printone(out, "# bytes in allocated blocks", allocated_bytes);
2373	n/a	total += printone(out, "# bytes in available blocks", available_bytes);
2374	n/a
2375	n/a	PyOS_snprintf(buf, sizeof(buf),
2376	n/a	"%u unused pools * %d bytes", numfreepools, POOL_SIZE);
2377	n/a	total += printone(out, buf, (size_t)numfreepools * POOL_SIZE);
2378	n/a
2379	n/a	total += printone(out, "# bytes lost to pool headers", pool_header_bytes);
2380	n/a	total += printone(out, "# bytes lost to quantization", quantization);
2381	n/a	total += printone(out, "# bytes lost to arena alignment", arena_alignment);
2382	n/a	(void)printone(out, "Total", total);
2383	n/a	}
2384	n/a
2385	n/a	#endif /* #ifdef WITH_PYMALLOC */