11221c0a435135143632d986e861d9243d3d2ad35Tim Peters#include "Python.h" 21221c0a435135143632d986e861d9243d3d2ad35Tim Peters 3b529c249214096a6e08a50399692d124c26dba29Benjamin Peterson#if defined(__has_feature) /* Clang */ 4b529c249214096a6e08a50399692d124c26dba29Benjamin Peterson #if __has_feature(address_sanitizer) /* is ASAN enabled? */ 5b529c249214096a6e08a50399692d124c26dba29Benjamin Peterson #define ATTRIBUTE_NO_ADDRESS_SAFETY_ANALYSIS \ 6b529c249214096a6e08a50399692d124c26dba29Benjamin Peterson __attribute__((no_address_safety_analysis)) \ 7b529c249214096a6e08a50399692d124c26dba29Benjamin Peterson __attribute__ ((noinline)) 8b529c249214096a6e08a50399692d124c26dba29Benjamin Peterson #else 9b529c249214096a6e08a50399692d124c26dba29Benjamin Peterson #define ATTRIBUTE_NO_ADDRESS_SAFETY_ANALYSIS 10b529c249214096a6e08a50399692d124c26dba29Benjamin Peterson #endif 11b529c249214096a6e08a50399692d124c26dba29Benjamin Peterson#else 12b529c249214096a6e08a50399692d124c26dba29Benjamin Peterson #if defined(__SANITIZE_ADDRESS__) /* GCC 4.8.x, is ASAN enabled? */ 13b529c249214096a6e08a50399692d124c26dba29Benjamin Peterson #define ATTRIBUTE_NO_ADDRESS_SAFETY_ANALYSIS \ 14b529c249214096a6e08a50399692d124c26dba29Benjamin Peterson __attribute__((no_address_safety_analysis)) \ 15b529c249214096a6e08a50399692d124c26dba29Benjamin Peterson __attribute__ ((noinline)) 16b529c249214096a6e08a50399692d124c26dba29Benjamin Peterson #else 17b529c249214096a6e08a50399692d124c26dba29Benjamin Peterson #define ATTRIBUTE_NO_ADDRESS_SAFETY_ANALYSIS 18b529c249214096a6e08a50399692d124c26dba29Benjamin Peterson #endif 19b529c249214096a6e08a50399692d124c26dba29Benjamin Peterson#endif 20b529c249214096a6e08a50399692d124c26dba29Benjamin Peterson 211221c0a435135143632d986e861d9243d3d2ad35Tim Peters#ifdef WITH_PYMALLOC 221221c0a435135143632d986e861d9243d3d2ad35Tim Peters 23d16e01cf75a2663c74c2e36beda6397546a8ae52Benjamin Peterson#ifdef HAVE_MMAP 24d16e01cf75a2663c74c2e36beda6397546a8ae52Benjamin Peterson #include <sys/mman.h> 25d16e01cf75a2663c74c2e36beda6397546a8ae52Benjamin Peterson #ifdef MAP_ANONYMOUS 26d16e01cf75a2663c74c2e36beda6397546a8ae52Benjamin Peterson #define ARENAS_USE_MMAP 27d16e01cf75a2663c74c2e36beda6397546a8ae52Benjamin Peterson #endif 28d16e01cf75a2663c74c2e36beda6397546a8ae52Benjamin Peterson#endif 29d16e01cf75a2663c74c2e36beda6397546a8ae52Benjamin Peterson 3091c12ebc3dc6472ea486ab5e4aa38139283d48adBenjamin Peterson#ifdef WITH_VALGRIND 3191c12ebc3dc6472ea486ab5e4aa38139283d48adBenjamin Peterson#include <valgrind/valgrind.h> 3291c12ebc3dc6472ea486ab5e4aa38139283d48adBenjamin Peterson 3391c12ebc3dc6472ea486ab5e4aa38139283d48adBenjamin Peterson/* If we're using GCC, use __builtin_expect() to reduce overhead of 3491c12ebc3dc6472ea486ab5e4aa38139283d48adBenjamin Peterson the valgrind checks */ 3591c12ebc3dc6472ea486ab5e4aa38139283d48adBenjamin Peterson#if defined(__GNUC__) && (__GNUC__ > 2) && defined(__OPTIMIZE__) 3691c12ebc3dc6472ea486ab5e4aa38139283d48adBenjamin Peterson# define UNLIKELY(value) __builtin_expect((value), 0) 3791c12ebc3dc6472ea486ab5e4aa38139283d48adBenjamin Peterson#else 3891c12ebc3dc6472ea486ab5e4aa38139283d48adBenjamin Peterson# define UNLIKELY(value) (value) 3991c12ebc3dc6472ea486ab5e4aa38139283d48adBenjamin Peterson#endif 4091c12ebc3dc6472ea486ab5e4aa38139283d48adBenjamin Peterson 4191c12ebc3dc6472ea486ab5e4aa38139283d48adBenjamin Peterson/* -1 indicates that we haven't checked that we're running on valgrind yet. */ 4291c12ebc3dc6472ea486ab5e4aa38139283d48adBenjamin Petersonstatic int running_on_valgrind = -1; 4391c12ebc3dc6472ea486ab5e4aa38139283d48adBenjamin Peterson#endif 4491c12ebc3dc6472ea486ab5e4aa38139283d48adBenjamin Peterson 45a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer/* An object allocator for Python. 46a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 47a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer Here is an introduction to the layers of the Python memory architecture, 48a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer showing where the object allocator is actually used (layer +2), It is 49a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer called for every object allocation and deallocation (PyObject_New/Del), 50a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer unless the object-specific allocators implement a proprietary allocation 51a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer scheme (ex.: ints use a simple free list). This is also the place where 52a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer the cyclic garbage collector operates selectively on container objects. 53a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 54a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 55c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou Object-specific allocators 56a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer _____ ______ ______ ________ 57a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer [ int ] [ dict ] [ list ] ... [ string ] Python core | 58a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer+3 | <----- Object-specific memory -----> | <-- Non-object memory --> | 59a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer _______________________________ | | 60a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer [ Python's object allocator ] | | 61a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer+2 | ####### Object memory ####### | <------ Internal buffers ------> | 62a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer ______________________________________________________________ | 63a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer [ Python's raw memory allocator (PyMem_ API) ] | 64a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer+1 | <----- Python memory (under PyMem manager's control) ------> | | 65a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer __________________________________________________________________ 66a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer [ Underlying general-purpose allocator (ex: C library malloc) ] 67a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 0 | <------ Virtual memory allocated for the python process -------> | 68a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 69a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer ========================================================================= 70a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer _______________________________________________________________________ 71a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer [ OS-specific Virtual Memory Manager (VMM) ] 72a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer-1 | <--- Kernel dynamic storage allocation & management (page-based) ---> | 73a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer __________________________________ __________________________________ 74a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer [ ] [ ] 75a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer-2 | <-- Physical memory: ROM/RAM --> | | <-- Secondary storage (swap) --> | 76a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 77a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer*/ 78a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer/*==========================================================================*/ 79a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 80a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer/* A fast, special-purpose memory allocator for small blocks, to be used 81a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer on top of a general-purpose malloc -- heavily based on previous art. */ 82a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 83a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer/* Vladimir Marangozov -- August 2000 */ 84a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 85a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer/* 86a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * "Memory management is where the rubber meets the road -- if we do the wrong 87a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * thing at any level, the results will not be good. And if we don't make the 88a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * levels work well together, we are in serious trouble." (1) 89a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * 90a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * (1) Paul R. Wilson, Mark S. Johnstone, Michael Neely, and David Boles, 91a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * "Dynamic Storage Allocation: A Survey and Critical Review", 92a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * in Proc. 1995 Int'l. Workshop on Memory Management, September 1995. 93a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer */ 94a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 95c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou/* #undef WITH_MEMORY_LIMITS */ /* disable mem limit checks */ 96a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 97a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer/*==========================================================================*/ 98a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 99a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer/* 100a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * Allocation strategy abstract: 101a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * 102a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * For small requests, the allocator sub-allocates <Big> blocks of memory. 103d16e01cf75a2663c74c2e36beda6397546a8ae52Benjamin Peterson * Requests greater than SMALL_REQUEST_THRESHOLD bytes are routed to the 104d16e01cf75a2663c74c2e36beda6397546a8ae52Benjamin Peterson * system's allocator. 105ce7fb9b5151f7238bdbaeb16c3041c9990ca8e9dTim Peters * 106a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * Small requests are grouped in size classes spaced 8 bytes apart, due 107a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * to the required valid alignment of the returned address. Requests of 108a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * a particular size are serviced from memory pools of 4K (one VMM page). 109a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * Pools are fragmented on demand and contain free lists of blocks of one 110a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * particular size class. In other words, there is a fixed-size allocator 111a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * for each size class. Free pools are shared by the different allocators 112a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * thus minimizing the space reserved for a particular size class. 113a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * 114a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * This allocation strategy is a variant of what is known as "simple 115a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * segregated storage based on array of free lists". The main drawback of 116a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * simple segregated storage is that we might end up with lot of reserved 117a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * memory for the different free lists, which degenerate in time. To avoid 118a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * this, we partition each free list in pools and we share dynamically the 119a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * reserved space between all free lists. This technique is quite efficient 120a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * for memory intensive programs which allocate mainly small-sized blocks. 121a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * 122a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * For small requests we have the following table: 123a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * 124c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * Request in bytes Size of allocated block Size class idx 125a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * ---------------------------------------------------------------- 126a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * 1-8 8 0 127c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * 9-16 16 1 128c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * 17-24 24 2 129c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * 25-32 32 3 130c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * 33-40 40 4 131c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * 41-48 48 5 132c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * 49-56 56 6 133c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * 57-64 64 7 134c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * 65-72 72 8 135c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * ... ... ... 136d16e01cf75a2663c74c2e36beda6397546a8ae52Benjamin Peterson * 497-504 504 62 137d16e01cf75a2663c74c2e36beda6397546a8ae52Benjamin Peterson * 505-512 512 63 138ce7fb9b5151f7238bdbaeb16c3041c9990ca8e9dTim Peters * 139d16e01cf75a2663c74c2e36beda6397546a8ae52Benjamin Peterson * 0, SMALL_REQUEST_THRESHOLD + 1 and up: routed to the underlying 140d16e01cf75a2663c74c2e36beda6397546a8ae52Benjamin Peterson * allocator. 141a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer */ 142a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 143a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer/*==========================================================================*/ 144a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 145a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer/* 146a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * -- Main tunable settings section -- 147a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer */ 148a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 149a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer/* 150a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * Alignment of addresses returned to the user. 8-bytes alignment works 151a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * on most current architectures (with 32-bit or 64-bit address busses). 152a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * The alignment value is also used for grouping small requests in size 153a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * classes spaced ALIGNMENT bytes apart. 154a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * 155a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * You shouldn't change this unless you know what you are doing. 156a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer */ 157c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou#define ALIGNMENT 8 /* must be 2^N */ 158c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou#define ALIGNMENT_SHIFT 3 159c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou#define ALIGNMENT_MASK (ALIGNMENT - 1) 160a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 161e70ddf3a99e5394faf17d78d0764929ae795b674Tim Peters/* Return the number of bytes in size class I, as a uint. */ 162e70ddf3a99e5394faf17d78d0764929ae795b674Tim Peters#define INDEX2SIZE(I) (((uint)(I) + 1) << ALIGNMENT_SHIFT) 163e70ddf3a99e5394faf17d78d0764929ae795b674Tim Peters 164a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer/* 165a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * Max size threshold below which malloc requests are considered to be 166a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * small enough in order to use preallocated memory pools. You can tune 167a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * this value according to your application behaviour and memory needs. 168a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * 169a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * The following invariants must hold: 1701edd2f6241df29eb2ae67c3ad9fa3872670d47e9Benjamin Peterson * 1) ALIGNMENT <= SMALL_REQUEST_THRESHOLD <= 512 171c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * 2) SMALL_REQUEST_THRESHOLD is evenly divisible by ALIGNMENT 172a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * 173d16e01cf75a2663c74c2e36beda6397546a8ae52Benjamin Peterson * Note: a size threshold of 512 guarantees that newly created dictionaries 174d16e01cf75a2663c74c2e36beda6397546a8ae52Benjamin Peterson * will be allocated from preallocated memory pools on 64-bit. 175d16e01cf75a2663c74c2e36beda6397546a8ae52Benjamin Peterson * 176a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * Although not required, for better performance and space efficiency, 177a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * it is recommended that SMALL_REQUEST_THRESHOLD is set to a power of 2. 178a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer */ 179d16e01cf75a2663c74c2e36beda6397546a8ae52Benjamin Peterson#define SMALL_REQUEST_THRESHOLD 512 180c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou#define NB_SMALL_SIZE_CLASSES (SMALL_REQUEST_THRESHOLD / ALIGNMENT) 181a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 182a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer/* 183a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * The system's VMM page size can be obtained on most unices with a 184a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * getpagesize() call or deduced from various header files. To make 185a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * things simpler, we assume that it is 4K, which is OK for most systems. 186a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * It is probably better if this is the native page size, but it doesn't 187ecc6e6a54ed4bb22b8b78dc1eca9183992ac3f40Tim Peters * have to be. In theory, if SYSTEM_PAGE_SIZE is larger than the native page 188ecc6e6a54ed4bb22b8b78dc1eca9183992ac3f40Tim Peters * size, then `POOL_ADDR(p)->arenaindex' could rarely cause a segmentation 189ecc6e6a54ed4bb22b8b78dc1eca9183992ac3f40Tim Peters * violation fault. 4K is apparently OK for all the platforms that python 1908c1402869ba0cb0a690a5168ac4067483d39e02eMartin v. Löwis * currently targets. 191a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer */ 192c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou#define SYSTEM_PAGE_SIZE (4 * 1024) 193c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou#define SYSTEM_PAGE_SIZE_MASK (SYSTEM_PAGE_SIZE - 1) 194a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 195a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer/* 196a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * Maximum amount of memory managed by the allocator for small requests. 197a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer */ 198a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer#ifdef WITH_MEMORY_LIMITS 199a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer#ifndef SMALL_MEMORY_LIMIT 200c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou#define SMALL_MEMORY_LIMIT (64 * 1024 * 1024) /* 64 MB -- more? */ 201a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer#endif 202a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer#endif 203a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 204a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer/* 205a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * The allocator sub-allocates <Big> blocks of memory (called arenas) aligned 206a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * on a page boundary. This is a reserved virtual address space for the 207d16e01cf75a2663c74c2e36beda6397546a8ae52Benjamin Peterson * current process (obtained through a malloc()/mmap() call). In no way this 208d16e01cf75a2663c74c2e36beda6397546a8ae52Benjamin Peterson * means that the memory arenas will be used entirely. A malloc(<Big>) is 209d16e01cf75a2663c74c2e36beda6397546a8ae52Benjamin Peterson * usually an address range reservation for <Big> bytes, unless all pages within 210d16e01cf75a2663c74c2e36beda6397546a8ae52Benjamin Peterson * this space are referenced subsequently. So malloc'ing big blocks and not 211d16e01cf75a2663c74c2e36beda6397546a8ae52Benjamin Peterson * using them does not mean "wasting memory". It's an addressable range 212d16e01cf75a2663c74c2e36beda6397546a8ae52Benjamin Peterson * wastage... 213a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * 214d16e01cf75a2663c74c2e36beda6397546a8ae52Benjamin Peterson * Arenas are allocated with mmap() on systems supporting anonymous memory 215d16e01cf75a2663c74c2e36beda6397546a8ae52Benjamin Peterson * mappings to reduce heap fragmentation. 216a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer */ 217c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou#define ARENA_SIZE (256 << 10) /* 256KB */ 218a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 219a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer#ifdef WITH_MEMORY_LIMITS 220c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou#define MAX_ARENAS (SMALL_MEMORY_LIMIT / ARENA_SIZE) 221a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer#endif 222a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 223a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer/* 224a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * Size of the pools used for small blocks. Should be a power of 2, 225c2ce91af5fbe71c5e12d78b0021701233aacde31Tim Peters * between 1K and SYSTEM_PAGE_SIZE, that is: 1k, 2k, 4k. 226a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer */ 227c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou#define POOL_SIZE SYSTEM_PAGE_SIZE /* must be 2^N */ 228c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou#define POOL_SIZE_MASK SYSTEM_PAGE_SIZE_MASK 229a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 230a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer/* 231a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * -- End of tunable settings section -- 232a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer */ 233a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 234a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer/*==========================================================================*/ 235a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 236a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer/* 237a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * Locking 238a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * 239a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * To reduce lock contention, it would probably be better to refine the 240a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * crude function locking with per size class locking. I'm not positive 241a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * however, whether it's worth switching to such locking policy because 242a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * of the performance penalty it might introduce. 243a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * 244a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * The following macros describe the simplest (should also be the fastest) 245a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * lock object on a particular platform and the init/fini/lock/unlock 246a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * operations on it. The locks defined here are not expected to be recursive 247a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * because it is assumed that they will always be called in the order: 248a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * INIT, [LOCK, UNLOCK]*, FINI. 249a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer */ 250a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 251a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer/* 252a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * Python's threads are serialized, so object malloc locking is disabled. 253a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer */ 254c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou#define SIMPLELOCK_DECL(lock) /* simple lock declaration */ 255c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou#define SIMPLELOCK_INIT(lock) /* allocate (if needed) and initialize */ 256c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou#define SIMPLELOCK_FINI(lock) /* free/destroy an existing lock */ 257c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou#define SIMPLELOCK_LOCK(lock) /* acquire released lock */ 258c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou#define SIMPLELOCK_UNLOCK(lock) /* release acquired lock */ 259a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 260a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer/* 261a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * Basic types 262a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * I don't care if these are defined in <sys/types.h> or elsewhere. Axiom. 263a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer */ 264a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer#undef uchar 265c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou#define uchar unsigned char /* assuming == 8 bits */ 266a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 267a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer#undef uint 268c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou#define uint unsigned int /* assuming >= 16 bits */ 269a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 270a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer#undef ulong 271c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou#define ulong unsigned long /* assuming >= 32 bits */ 272a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 273d97a1c008c4a7ae04c55c8de2cdb71a9ea43656aTim Peters#undef uptr 274c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou#define uptr Py_uintptr_t 275d97a1c008c4a7ae04c55c8de2cdb71a9ea43656aTim Peters 276a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer/* When you say memory, my mind reasons in terms of (pointers to) blocks */ 277a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauertypedef uchar block; 278a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 279e70ddf3a99e5394faf17d78d0764929ae795b674Tim Peters/* Pool for small blocks. */ 280a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauerstruct pool_header { 281c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou union { block *_padding; 282918c90ce06d6189f8d24d1dba842382a5cb447d4Stefan Krah uint count; } ref; /* number of allocated blocks */ 283c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou block *freeblock; /* pool's free list head */ 284c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou struct pool_header *nextpool; /* next pool of this size class */ 285c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou struct pool_header *prevpool; /* previous pool "" */ 286c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou uint arenaindex; /* index into arenas of base adr */ 287c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou uint szidx; /* block size class index */ 288c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou uint nextoffset; /* bytes to virgin block */ 289c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou uint maxnextoffset; /* largest valid nextoffset */ 290a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer}; 291a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 292a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauertypedef struct pool_header *poolp; 293a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 294cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters/* Record keeping for arenas. */ 295cf79aace07a57d480605f4a5aa8b9ca68567792eTim Petersstruct arena_object { 296c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* The address of the arena, as returned by malloc. Note that 0 297c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * will never be returned by a successful malloc, and is used 298c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * here to mark an arena_object that doesn't correspond to an 299c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * allocated arena. 300c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 301c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou uptr address; 302c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 303c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Pool-aligned pointer to the next pool to be carved off. */ 304c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou block* pool_address; 305c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 306c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* The number of available pools in the arena: free pools + never- 307c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * allocated pools. 308c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 309c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou uint nfreepools; 310c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 311c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* The total number of pools in the arena, whether or not available. */ 312c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou uint ntotalpools; 313c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 314c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Singly-linked list of available pools. */ 315c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou struct pool_header* freepools; 316c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 317c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Whenever this arena_object is not associated with an allocated 318c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * arena, the nextarena member is used to link all unassociated 319c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * arena_objects in the singly-linked `unused_arena_objects` list. 320c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * The prevarena member is unused in this case. 321c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * 322c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * When this arena_object is associated with an allocated arena 323c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * with at least one available pool, both members are used in the 324c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * doubly-linked `usable_arenas` list, which is maintained in 325c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * increasing order of `nfreepools` values. 326c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * 327c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * Else this arena_object is associated with an allocated arena 328c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * all of whose pools are in use. `nextarena` and `prevarena` 329c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * are both meaningless in this case. 330c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 331c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou struct arena_object* nextarena; 332c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou struct arena_object* prevarena; 333cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters}; 334cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters 335a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer#undef ROUNDUP 336c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou#define ROUNDUP(x) (((x) + ALIGNMENT_MASK) & ~ALIGNMENT_MASK) 337c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou#define POOL_OVERHEAD ROUNDUP(sizeof(struct pool_header)) 338a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 339c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou#define DUMMY_SIZE_IDX 0xffff /* size class of newly cached pools */ 340a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 341d97a1c008c4a7ae04c55c8de2cdb71a9ea43656aTim Peters/* Round pointer P down to the closest pool-aligned address <= P, as a poolp */ 342e70ddf3a99e5394faf17d78d0764929ae795b674Tim Peters#define POOL_ADDR(P) ((poolp)((uptr)(P) & ~(uptr)POOL_SIZE_MASK)) 343e70ddf3a99e5394faf17d78d0764929ae795b674Tim Peters 34416bcb6b1afc46f2f73e207bc0484f016c51f0fd9Tim Peters/* Return total number of blocks in pool of size index I, as a uint. */ 34516bcb6b1afc46f2f73e207bc0484f016c51f0fd9Tim Peters#define NUMBLOCKS(I) ((uint)(POOL_SIZE - POOL_OVERHEAD) / INDEX2SIZE(I)) 346d97a1c008c4a7ae04c55c8de2cdb71a9ea43656aTim Peters 347a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer/*==========================================================================*/ 348a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 349a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer/* 350a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * This malloc lock 351a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer */ 352d1fedb6ab59547f914a1958804a0658b68e4d6b2Jeremy HyltonSIMPLELOCK_DECL(_malloc_lock) 353c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou#define LOCK() SIMPLELOCK_LOCK(_malloc_lock) 354c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou#define UNLOCK() SIMPLELOCK_UNLOCK(_malloc_lock) 355c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou#define LOCK_INIT() SIMPLELOCK_INIT(_malloc_lock) 356c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou#define LOCK_FINI() SIMPLELOCK_FINI(_malloc_lock) 357a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 358a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer/* 3591e16db6d3b542b5cc146245055be0a04263c4e5eTim Peters * Pool table -- headed, circular, doubly-linked lists of partially used pools. 3601e16db6d3b542b5cc146245055be0a04263c4e5eTim Peters 3611e16db6d3b542b5cc146245055be0a04263c4e5eTim PetersThis is involved. For an index i, usedpools[i+i] is the header for a list of 3621e16db6d3b542b5cc146245055be0a04263c4e5eTim Petersall partially used pools holding small blocks with "size class idx" i. So 3631e16db6d3b542b5cc146245055be0a04263c4e5eTim Petersusedpools[0] corresponds to blocks of size 8, usedpools[2] to blocks of size 3641e16db6d3b542b5cc146245055be0a04263c4e5eTim Peters16, and so on: index 2*i <-> blocks of size (i+1)<<ALIGNMENT_SHIFT. 3651e16db6d3b542b5cc146245055be0a04263c4e5eTim Peters 366cf79aace07a57d480605f4a5aa8b9ca68567792eTim PetersPools are carved off an arena's highwater mark (an arena_object's pool_address 367cf79aace07a57d480605f4a5aa8b9ca68567792eTim Petersmember) as needed. Once carved off, a pool is in one of three states forever 368cf79aace07a57d480605f4a5aa8b9ca68567792eTim Petersafter: 369338e010b45d7bd411e2bbcedcd8ef195be40c2beTim Peters 370338e010b45d7bd411e2bbcedcd8ef195be40c2beTim Petersused == partially used, neither empty nor full 371338e010b45d7bd411e2bbcedcd8ef195be40c2beTim Peters At least one block in the pool is currently allocated, and at least one 372338e010b45d7bd411e2bbcedcd8ef195be40c2beTim Peters block in the pool is not currently allocated (note this implies a pool 373338e010b45d7bd411e2bbcedcd8ef195be40c2beTim Peters has room for at least two blocks). 374338e010b45d7bd411e2bbcedcd8ef195be40c2beTim Peters This is a pool's initial state, as a pool is created only when malloc 375338e010b45d7bd411e2bbcedcd8ef195be40c2beTim Peters needs space. 376338e010b45d7bd411e2bbcedcd8ef195be40c2beTim Peters The pool holds blocks of a fixed size, and is in the circular list headed 377338e010b45d7bd411e2bbcedcd8ef195be40c2beTim Peters at usedpools[i] (see above). It's linked to the other used pools of the 378338e010b45d7bd411e2bbcedcd8ef195be40c2beTim Peters same size class via the pool_header's nextpool and prevpool members. 379338e010b45d7bd411e2bbcedcd8ef195be40c2beTim Peters If all but one block is currently allocated, a malloc can cause a 380338e010b45d7bd411e2bbcedcd8ef195be40c2beTim Peters transition to the full state. If all but one block is not currently 381338e010b45d7bd411e2bbcedcd8ef195be40c2beTim Peters allocated, a free can cause a transition to the empty state. 382338e010b45d7bd411e2bbcedcd8ef195be40c2beTim Peters 383338e010b45d7bd411e2bbcedcd8ef195be40c2beTim Petersfull == all the pool's blocks are currently allocated 384338e010b45d7bd411e2bbcedcd8ef195be40c2beTim Peters On transition to full, a pool is unlinked from its usedpools[] list. 385338e010b45d7bd411e2bbcedcd8ef195be40c2beTim Peters It's not linked to from anything then anymore, and its nextpool and 386338e010b45d7bd411e2bbcedcd8ef195be40c2beTim Peters prevpool members are meaningless until it transitions back to used. 387338e010b45d7bd411e2bbcedcd8ef195be40c2beTim Peters A free of a block in a full pool puts the pool back in the used state. 388338e010b45d7bd411e2bbcedcd8ef195be40c2beTim Peters Then it's linked in at the front of the appropriate usedpools[] list, so 389338e010b45d7bd411e2bbcedcd8ef195be40c2beTim Peters that the next allocation for its size class will reuse the freed block. 390338e010b45d7bd411e2bbcedcd8ef195be40c2beTim Peters 391338e010b45d7bd411e2bbcedcd8ef195be40c2beTim Petersempty == all the pool's blocks are currently available for allocation 392338e010b45d7bd411e2bbcedcd8ef195be40c2beTim Peters On transition to empty, a pool is unlinked from its usedpools[] list, 393cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters and linked to the front of its arena_object's singly-linked freepools list, 394338e010b45d7bd411e2bbcedcd8ef195be40c2beTim Peters via its nextpool member. The prevpool member has no meaning in this case. 395338e010b45d7bd411e2bbcedcd8ef195be40c2beTim Peters Empty pools have no inherent size class: the next time a malloc finds 396338e010b45d7bd411e2bbcedcd8ef195be40c2beTim Peters an empty list in usedpools[], it takes the first pool off of freepools. 397338e010b45d7bd411e2bbcedcd8ef195be40c2beTim Peters If the size class needed happens to be the same as the size class the pool 398e70ddf3a99e5394faf17d78d0764929ae795b674Tim Peters last had, some pool initialization can be skipped. 399338e010b45d7bd411e2bbcedcd8ef195be40c2beTim Peters 400338e010b45d7bd411e2bbcedcd8ef195be40c2beTim Peters 401338e010b45d7bd411e2bbcedcd8ef195be40c2beTim PetersBlock Management 402338e010b45d7bd411e2bbcedcd8ef195be40c2beTim Peters 403338e010b45d7bd411e2bbcedcd8ef195be40c2beTim PetersBlocks within pools are again carved out as needed. pool->freeblock points to 404338e010b45d7bd411e2bbcedcd8ef195be40c2beTim Petersthe start of a singly-linked list of free blocks within the pool. When a 405338e010b45d7bd411e2bbcedcd8ef195be40c2beTim Petersblock is freed, it's inserted at the front of its pool's freeblock list. Note 406338e010b45d7bd411e2bbcedcd8ef195be40c2beTim Petersthat the available blocks in a pool are *not* linked all together when a pool 407e70ddf3a99e5394faf17d78d0764929ae795b674Tim Petersis initialized. Instead only "the first two" (lowest addresses) blocks are 408e70ddf3a99e5394faf17d78d0764929ae795b674Tim Petersset up, returning the first such block, and setting pool->freeblock to a 409e70ddf3a99e5394faf17d78d0764929ae795b674Tim Petersone-block list holding the second such block. This is consistent with that 410e70ddf3a99e5394faf17d78d0764929ae795b674Tim Peterspymalloc strives at all levels (arena, pool, and block) never to touch a piece 411e70ddf3a99e5394faf17d78d0764929ae795b674Tim Petersof memory until it's actually needed. 412e70ddf3a99e5394faf17d78d0764929ae795b674Tim Peters 413e70ddf3a99e5394faf17d78d0764929ae795b674Tim PetersSo long as a pool is in the used state, we're certain there *is* a block 41452aefc8a7b9e9ebda6c1b98a831a273e0b07bf96Tim Petersavailable for allocating, and pool->freeblock is not NULL. If pool->freeblock 41552aefc8a7b9e9ebda6c1b98a831a273e0b07bf96Tim Peterspoints to the end of the free list before we've carved the entire pool into 41652aefc8a7b9e9ebda6c1b98a831a273e0b07bf96Tim Petersblocks, that means we simply haven't yet gotten to one of the higher-address 41752aefc8a7b9e9ebda6c1b98a831a273e0b07bf96Tim Petersblocks. The offset from the pool_header to the start of "the next" virgin 41852aefc8a7b9e9ebda6c1b98a831a273e0b07bf96Tim Petersblock is stored in the pool_header nextoffset member, and the largest value 41952aefc8a7b9e9ebda6c1b98a831a273e0b07bf96Tim Petersof nextoffset that makes sense is stored in the maxnextoffset member when a 42052aefc8a7b9e9ebda6c1b98a831a273e0b07bf96Tim Peterspool is initialized. All the blocks in a pool have been passed out at least 42152aefc8a7b9e9ebda6c1b98a831a273e0b07bf96Tim Petersonce when and only when nextoffset > maxnextoffset. 422338e010b45d7bd411e2bbcedcd8ef195be40c2beTim Peters 4231e16db6d3b542b5cc146245055be0a04263c4e5eTim Peters 4241e16db6d3b542b5cc146245055be0a04263c4e5eTim PetersMajor obscurity: While the usedpools vector is declared to have poolp 4251e16db6d3b542b5cc146245055be0a04263c4e5eTim Petersentries, it doesn't really. It really contains two pointers per (conceptual) 4261e16db6d3b542b5cc146245055be0a04263c4e5eTim Peterspoolp entry, the nextpool and prevpool members of a pool_header. The 4271e16db6d3b542b5cc146245055be0a04263c4e5eTim Petersexcruciating initialization code below fools C so that 4281e16db6d3b542b5cc146245055be0a04263c4e5eTim Peters 4291e16db6d3b542b5cc146245055be0a04263c4e5eTim Peters usedpool[i+i] 4301e16db6d3b542b5cc146245055be0a04263c4e5eTim Peters 4311e16db6d3b542b5cc146245055be0a04263c4e5eTim Peters"acts like" a genuine poolp, but only so long as you only reference its 4321e16db6d3b542b5cc146245055be0a04263c4e5eTim Petersnextpool and prevpool members. The "- 2*sizeof(block *)" gibberish is 4331e16db6d3b542b5cc146245055be0a04263c4e5eTim Peterscompensating for that a pool_header's nextpool and prevpool members 4341e16db6d3b542b5cc146245055be0a04263c4e5eTim Petersimmediately follow a pool_header's first two members: 4351e16db6d3b542b5cc146245055be0a04263c4e5eTim Peters 436c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou union { block *_padding; 437918c90ce06d6189f8d24d1dba842382a5cb447d4Stefan Krah uint count; } ref; 438c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou block *freeblock; 4391e16db6d3b542b5cc146245055be0a04263c4e5eTim Peters 4401e16db6d3b542b5cc146245055be0a04263c4e5eTim Peterseach of which consume sizeof(block *) bytes. So what usedpools[i+i] really 4411e16db6d3b542b5cc146245055be0a04263c4e5eTim Peterscontains is a fudged-up pointer p such that *if* C believes it's a poolp 4421e16db6d3b542b5cc146245055be0a04263c4e5eTim Peterspointer, then p->nextpool and p->prevpool are both p (meaning that the headed 4431e16db6d3b542b5cc146245055be0a04263c4e5eTim Peterscircular list is empty). 4441e16db6d3b542b5cc146245055be0a04263c4e5eTim Peters 4451e16db6d3b542b5cc146245055be0a04263c4e5eTim PetersIt's unclear why the usedpools setup is so convoluted. It could be to 4461e16db6d3b542b5cc146245055be0a04263c4e5eTim Petersminimize the amount of cache required to hold this heavily-referenced table 4471e16db6d3b542b5cc146245055be0a04263c4e5eTim Peters(which only *needs* the two interpool pointer members of a pool_header). OTOH, 4481e16db6d3b542b5cc146245055be0a04263c4e5eTim Petersreferencing code has to remember to "double the index" and doing so isn't 4491e16db6d3b542b5cc146245055be0a04263c4e5eTim Petersfree, usedpools[0] isn't a strictly legal pointer, and we're crucially relying 4501e16db6d3b542b5cc146245055be0a04263c4e5eTim Peterson that C doesn't insert any padding anywhere in a pool_header at or before 4511e16db6d3b542b5cc146245055be0a04263c4e5eTim Petersthe prevpool member. 4521e16db6d3b542b5cc146245055be0a04263c4e5eTim Peters**************************************************************************** */ 4531e16db6d3b542b5cc146245055be0a04263c4e5eTim Peters 454c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou#define PTA(x) ((poolp )((uchar *)&(usedpools[2*(x)]) - 2*sizeof(block *))) 455c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou#define PT(x) PTA(x), PTA(x) 456a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 457a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauerstatic poolp usedpools[2 * ((NB_SMALL_SIZE_CLASSES + 7) / 8) * 8] = { 458c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou PT(0), PT(1), PT(2), PT(3), PT(4), PT(5), PT(6), PT(7) 459a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer#if NB_SMALL_SIZE_CLASSES > 8 460c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou , PT(8), PT(9), PT(10), PT(11), PT(12), PT(13), PT(14), PT(15) 461a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer#if NB_SMALL_SIZE_CLASSES > 16 462c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou , PT(16), PT(17), PT(18), PT(19), PT(20), PT(21), PT(22), PT(23) 463a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer#if NB_SMALL_SIZE_CLASSES > 24 464c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou , PT(24), PT(25), PT(26), PT(27), PT(28), PT(29), PT(30), PT(31) 465a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer#if NB_SMALL_SIZE_CLASSES > 32 466c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou , PT(32), PT(33), PT(34), PT(35), PT(36), PT(37), PT(38), PT(39) 467a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer#if NB_SMALL_SIZE_CLASSES > 40 468c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou , PT(40), PT(41), PT(42), PT(43), PT(44), PT(45), PT(46), PT(47) 469a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer#if NB_SMALL_SIZE_CLASSES > 48 470c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou , PT(48), PT(49), PT(50), PT(51), PT(52), PT(53), PT(54), PT(55) 471a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer#if NB_SMALL_SIZE_CLASSES > 56 472c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou , PT(56), PT(57), PT(58), PT(59), PT(60), PT(61), PT(62), PT(63) 473d16e01cf75a2663c74c2e36beda6397546a8ae52Benjamin Peterson#if NB_SMALL_SIZE_CLASSES > 64 474d16e01cf75a2663c74c2e36beda6397546a8ae52Benjamin Peterson#error "NB_SMALL_SIZE_CLASSES should be less than 64" 475d16e01cf75a2663c74c2e36beda6397546a8ae52Benjamin Peterson#endif /* NB_SMALL_SIZE_CLASSES > 64 */ 476a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer#endif /* NB_SMALL_SIZE_CLASSES > 56 */ 477a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer#endif /* NB_SMALL_SIZE_CLASSES > 48 */ 478a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer#endif /* NB_SMALL_SIZE_CLASSES > 40 */ 479a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer#endif /* NB_SMALL_SIZE_CLASSES > 32 */ 480a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer#endif /* NB_SMALL_SIZE_CLASSES > 24 */ 481a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer#endif /* NB_SMALL_SIZE_CLASSES > 16 */ 482a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer#endif /* NB_SMALL_SIZE_CLASSES > 8 */ 483a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer}; 484a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 485cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters/*========================================================================== 486cf79aace07a57d480605f4a5aa8b9ca68567792eTim PetersArena management. 487cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters 488cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters`arenas` is a vector of arena_objects. It contains maxarenas entries, some of 489cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peterswhich may not be currently used (== they're arena_objects that aren't 490cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peterscurrently associated with an allocated arena). Note that arenas proper are 491cf79aace07a57d480605f4a5aa8b9ca68567792eTim Petersseparately malloc'ed. 492cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters 493cf79aace07a57d480605f4a5aa8b9ca68567792eTim PetersPrior to Python 2.5, arenas were never free()'ed. Starting with Python 2.5, 494cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peterswe do try to free() arenas, and use some mild heuristic strategies to increase 495cf79aace07a57d480605f4a5aa8b9ca68567792eTim Petersthe likelihood that arenas eventually can be freed. 496cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters 497cf79aace07a57d480605f4a5aa8b9ca68567792eTim Petersunused_arena_objects 498cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters 499cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters This is a singly-linked list of the arena_objects that are currently not 500cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters being used (no arena is associated with them). Objects are taken off the 501cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters head of the list in new_arena(), and are pushed on the head of the list in 502cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters PyObject_Free() when the arena is empty. Key invariant: an arena_object 503cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters is on this list if and only if its .address member is 0. 504cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters 505cf79aace07a57d480605f4a5aa8b9ca68567792eTim Petersusable_arenas 506cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters 507cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters This is a doubly-linked list of the arena_objects associated with arenas 508cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters that have pools available. These pools are either waiting to be reused, 509cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters or have not been used before. The list is sorted to have the most- 510cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters allocated arenas first (ascending order based on the nfreepools member). 511cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters This means that the next allocation will come from a heavily used arena, 512cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters which gives the nearly empty arenas a chance to be returned to the system. 513cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters In my unscientific tests this dramatically improved the number of arenas 514cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters that could be freed. 515cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters 516cf79aace07a57d480605f4a5aa8b9ca68567792eTim PetersNote that an arena_object associated with an arena all of whose pools are 517cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peterscurrently in use isn't on either list. 518cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters*/ 519cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters 520cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters/* Array of objects used to track chunks of memory (arenas). */ 521cf79aace07a57d480605f4a5aa8b9ca68567792eTim Petersstatic struct arena_object* arenas = NULL; 522cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters/* Number of slots currently allocated in the `arenas` vector. */ 523cf79aace07a57d480605f4a5aa8b9ca68567792eTim Petersstatic uint maxarenas = 0; 524cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters 525cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters/* The head of the singly-linked, NULL-terminated list of available 526cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters * arena_objects. 527a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer */ 528cf79aace07a57d480605f4a5aa8b9ca68567792eTim Petersstatic struct arena_object* unused_arena_objects = NULL; 529a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 530cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters/* The head of the doubly-linked, NULL-terminated at each end, list of 531cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters * arena_objects associated with arenas that have pools available. 532cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters */ 533cf79aace07a57d480605f4a5aa8b9ca68567792eTim Petersstatic struct arena_object* usable_arenas = NULL; 534d97a1c008c4a7ae04c55c8de2cdb71a9ea43656aTim Peters 535cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters/* How many arena_objects do we initially allocate? 536cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters * 16 = can allocate 16 arenas = 16 * ARENA_SIZE = 4MB before growing the 537cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters * `arenas` vector. 538a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer */ 539cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters#define INITIAL_ARENA_OBJECTS 16 540a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 541cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters/* Number of arenas allocated that haven't been free()'d. */ 5429ea89d2a1972a527bee508c3fb8cd42a86908da1Tim Petersstatic size_t narenas_currently_allocated = 0; 543d97a1c008c4a7ae04c55c8de2cdb71a9ea43656aTim Peters 544cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters#ifdef PYMALLOC_DEBUG 545cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters/* Total number of times malloc() called to allocate an arena. */ 5469ea89d2a1972a527bee508c3fb8cd42a86908da1Tim Petersstatic size_t ntimes_arena_allocated = 0; 547cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters/* High water mark (max value ever seen) for narenas_currently_allocated. */ 5489ea89d2a1972a527bee508c3fb8cd42a86908da1Tim Petersstatic size_t narenas_highwater = 0; 549cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters#endif 550d97a1c008c4a7ae04c55c8de2cdb71a9ea43656aTim Peters 551cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters/* Allocate a new arena. If we run out of memory, return NULL. Else 552cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters * allocate a new arena, and return the address of an arena_object 553cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters * describing the new arena. It's expected that the caller will set 554cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters * `usable_arenas` to the return value. 555d97a1c008c4a7ae04c55c8de2cdb71a9ea43656aTim Peters */ 556cf79aace07a57d480605f4a5aa8b9ca68567792eTim Petersstatic struct arena_object* 557d97a1c008c4a7ae04c55c8de2cdb71a9ea43656aTim Petersnew_arena(void) 558d97a1c008c4a7ae04c55c8de2cdb71a9ea43656aTim Peters{ 559c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou struct arena_object* arenaobj; 560c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou uint excess; /* number of bytes above pool alignment */ 561cee4f034385902659ec1ade666e17537eb2bc399Charles-François Natali void *address; 562cee4f034385902659ec1ade666e17537eb2bc399Charles-François Natali int err; 563d97a1c008c4a7ae04c55c8de2cdb71a9ea43656aTim Peters 5640e871188e8cd9a4e41be7c734e250bfce2d92d56Tim Peters#ifdef PYMALLOC_DEBUG 565c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (Py_GETENV("PYTHONMALLOCSTATS")) 566c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou _PyObject_DebugMallocStats(); 5670e871188e8cd9a4e41be7c734e250bfce2d92d56Tim Peters#endif 568c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (unused_arena_objects == NULL) { 569c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou uint i; 570c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou uint numarenas; 571c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou size_t nbytes; 572c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 573c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Double the number of arena objects on each allocation. 574c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * Note that it's possible for `numarenas` to overflow. 575c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 576c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou numarenas = maxarenas ? maxarenas << 1 : INITIAL_ARENA_OBJECTS; 577c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (numarenas <= maxarenas) 578c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return NULL; /* overflow */ 5799fa5a2828c8007dfb678b883d65aecac93e995e4Martin v. Löwis#if SIZEOF_SIZE_T <= SIZEOF_INT 580c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (numarenas > PY_SIZE_MAX / sizeof(*arenas)) 581c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return NULL; /* overflow */ 5829fa5a2828c8007dfb678b883d65aecac93e995e4Martin v. Löwis#endif 583c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou nbytes = numarenas * sizeof(*arenas); 584c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou arenaobj = (struct arena_object *)realloc(arenas, nbytes); 585c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (arenaobj == NULL) 586c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return NULL; 587c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou arenas = arenaobj; 588c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 589c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* We might need to fix pointers that were copied. However, 590c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * new_arena only gets called when all the pages in the 591c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * previous arenas are full. Thus, there are *no* pointers 592c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * into the old array. Thus, we don't have to worry about 593c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * invalid pointers. Just to be sure, some asserts: 594c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 595c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(usable_arenas == NULL); 596c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(unused_arena_objects == NULL); 597c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 598c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Put the new arenas on the unused_arena_objects list. */ 599c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou for (i = maxarenas; i < numarenas; ++i) { 600c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou arenas[i].address = 0; /* mark as unassociated */ 601c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou arenas[i].nextarena = i < numarenas - 1 ? 602c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou &arenas[i+1] : NULL; 603c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 604c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 605c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Update globals. */ 606c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou unused_arena_objects = &arenas[maxarenas]; 607c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou maxarenas = numarenas; 608c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 609c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 610c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Take the next available arena object off the head of the list. */ 611c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(unused_arena_objects != NULL); 612c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou arenaobj = unused_arena_objects; 613c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou unused_arena_objects = arenaobj->nextarena; 614c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(arenaobj->address == 0); 615d16e01cf75a2663c74c2e36beda6397546a8ae52Benjamin Peterson#ifdef ARENAS_USE_MMAP 616cee4f034385902659ec1ade666e17537eb2bc399Charles-François Natali address = mmap(NULL, ARENA_SIZE, PROT_READ|PROT_WRITE, 617cee4f034385902659ec1ade666e17537eb2bc399Charles-François Natali MAP_PRIVATE|MAP_ANONYMOUS, -1, 0); 618cee4f034385902659ec1ade666e17537eb2bc399Charles-François Natali err = (address == MAP_FAILED); 619d16e01cf75a2663c74c2e36beda6397546a8ae52Benjamin Peterson#else 620cee4f034385902659ec1ade666e17537eb2bc399Charles-François Natali address = malloc(ARENA_SIZE); 621cee4f034385902659ec1ade666e17537eb2bc399Charles-François Natali err = (address == 0); 622d16e01cf75a2663c74c2e36beda6397546a8ae52Benjamin Peterson#endif 623cee4f034385902659ec1ade666e17537eb2bc399Charles-François Natali if (err) { 624c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* The allocation failed: return NULL after putting the 625c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * arenaobj back. 626c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 627c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou arenaobj->nextarena = unused_arena_objects; 628c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou unused_arena_objects = arenaobj; 629c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return NULL; 630c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 631cee4f034385902659ec1ade666e17537eb2bc399Charles-François Natali arenaobj->address = (uptr)address; 632c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 633c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou ++narenas_currently_allocated; 634cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters#ifdef PYMALLOC_DEBUG 635c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou ++ntimes_arena_allocated; 636c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (narenas_currently_allocated > narenas_highwater) 637c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou narenas_highwater = narenas_currently_allocated; 638cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters#endif 639c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou arenaobj->freepools = NULL; 640c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* pool_address <- first pool-aligned address in the arena 641c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou nfreepools <- number of whole pools that fit after alignment */ 642c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou arenaobj->pool_address = (block*)arenaobj->address; 643c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou arenaobj->nfreepools = ARENA_SIZE / POOL_SIZE; 644c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(POOL_SIZE * arenaobj->nfreepools == ARENA_SIZE); 645c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou excess = (uint)(arenaobj->address & POOL_SIZE_MASK); 646c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (excess != 0) { 647c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou --arenaobj->nfreepools; 648c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou arenaobj->pool_address += POOL_SIZE - excess; 649c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 650c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou arenaobj->ntotalpools = arenaobj->nfreepools; 651c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 652c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return arenaobj; 653d97a1c008c4a7ae04c55c8de2cdb71a9ea43656aTim Peters} 654d97a1c008c4a7ae04c55c8de2cdb71a9ea43656aTim Peters 655cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters/* 656cf79aace07a57d480605f4a5aa8b9ca68567792eTim PetersPy_ADDRESS_IN_RANGE(P, POOL) 657cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters 658cf79aace07a57d480605f4a5aa8b9ca68567792eTim PetersReturn true if and only if P is an address that was allocated by pymalloc. 659cf79aace07a57d480605f4a5aa8b9ca68567792eTim PetersPOOL must be the pool address associated with P, i.e., POOL = POOL_ADDR(P) 660cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters(the caller is asked to compute this because the macro expands POOL more than 661cf79aace07a57d480605f4a5aa8b9ca68567792eTim Petersonce, and for efficiency it's best for the caller to assign POOL_ADDR(P) to a 662cf79aace07a57d480605f4a5aa8b9ca68567792eTim Petersvariable and pass the latter to the macro; because Py_ADDRESS_IN_RANGE is 663cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peterscalled on every alloc/realloc/free, micro-efficiency is important here). 664cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters 665cf79aace07a57d480605f4a5aa8b9ca68567792eTim PetersTricky: Let B be the arena base address associated with the pool, B = 666cf79aace07a57d480605f4a5aa8b9ca68567792eTim Petersarenas[(POOL)->arenaindex].address. Then P belongs to the arena if and only if 667cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters 668c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou B <= P < B + ARENA_SIZE 669cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters 670cf79aace07a57d480605f4a5aa8b9ca68567792eTim PetersSubtracting B throughout, this is true iff 671cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters 672c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 0 <= P-B < ARENA_SIZE 673cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters 674cf79aace07a57d480605f4a5aa8b9ca68567792eTim PetersBy using unsigned arithmetic, the "0 <=" half of the test can be skipped. 675cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters 676cf79aace07a57d480605f4a5aa8b9ca68567792eTim PetersObscure: A PyMem "free memory" function can call the pymalloc free or realloc 677cf79aace07a57d480605f4a5aa8b9ca68567792eTim Petersbefore the first arena has been allocated. `arenas` is still NULL in that 678cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peterscase. We're relying on that maxarenas is also 0 in that case, so that 679cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters(POOL)->arenaindex < maxarenas must be false, saving us from trying to index 680cf79aace07a57d480605f4a5aa8b9ca68567792eTim Petersinto a NULL arenas. 681cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters 682cf79aace07a57d480605f4a5aa8b9ca68567792eTim PetersDetails: given P and POOL, the arena_object corresponding to P is AO = 683cf79aace07a57d480605f4a5aa8b9ca68567792eTim Petersarenas[(POOL)->arenaindex]. Suppose obmalloc controls P. Then (barring wild 684cf79aace07a57d480605f4a5aa8b9ca68567792eTim Petersstores, etc), POOL is the correct address of P's pool, AO.address is the 685cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peterscorrect base address of the pool's arena, and P must be within ARENA_SIZE of 686cf79aace07a57d480605f4a5aa8b9ca68567792eTim PetersAO.address. In addition, AO.address is not 0 (no arena can start at address 0 687cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters(NULL)). Therefore Py_ADDRESS_IN_RANGE correctly reports that obmalloc 688cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peterscontrols P. 689cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters 690cf79aace07a57d480605f4a5aa8b9ca68567792eTim PetersNow suppose obmalloc does not control P (e.g., P was obtained via a direct 691cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peterscall to the system malloc() or realloc()). (POOL)->arenaindex may be anything 692cf79aace07a57d480605f4a5aa8b9ca68567792eTim Petersin this case -- it may even be uninitialized trash. If the trash arenaindex 693cf79aace07a57d480605f4a5aa8b9ca68567792eTim Petersis >= maxarenas, the macro correctly concludes at once that obmalloc doesn't 694cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peterscontrol P. 695cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters 696cf79aace07a57d480605f4a5aa8b9ca68567792eTim PetersElse arenaindex is < maxarena, and AO is read up. If AO corresponds to an 697cf79aace07a57d480605f4a5aa8b9ca68567792eTim Petersallocated arena, obmalloc controls all the memory in slice AO.address : 698cf79aace07a57d480605f4a5aa8b9ca68567792eTim PetersAO.address+ARENA_SIZE. By case assumption, P is not controlled by obmalloc, 699cf79aace07a57d480605f4a5aa8b9ca68567792eTim Petersso P doesn't lie in that slice, so the macro correctly reports that P is not 700cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peterscontrolled by obmalloc. 701cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters 702cf79aace07a57d480605f4a5aa8b9ca68567792eTim PetersFinally, if P is not controlled by obmalloc and AO corresponds to an unused 703cf79aace07a57d480605f4a5aa8b9ca68567792eTim Petersarena_object (one not currently associated with an allocated arena), 704cf79aace07a57d480605f4a5aa8b9ca68567792eTim PetersAO.address is 0, and the second test in the macro reduces to: 705cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters 706c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou P < ARENA_SIZE 707cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters 708cf79aace07a57d480605f4a5aa8b9ca68567792eTim PetersIf P >= ARENA_SIZE (extremely likely), the macro again correctly concludes 709cf79aace07a57d480605f4a5aa8b9ca68567792eTim Petersthat P is not controlled by obmalloc. However, if P < ARENA_SIZE, this part 710cf79aace07a57d480605f4a5aa8b9ca68567792eTim Petersof the test still passes, and the third clause (AO.address != 0) is necessary 711cf79aace07a57d480605f4a5aa8b9ca68567792eTim Petersto get the correct result: AO.address is 0 in this case, so the macro 712cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peterscorrectly reports that P is not controlled by obmalloc (despite that P lies in 713cf79aace07a57d480605f4a5aa8b9ca68567792eTim Petersslice AO.address : AO.address + ARENA_SIZE). 714cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters 715cf79aace07a57d480605f4a5aa8b9ca68567792eTim PetersNote: The third (AO.address != 0) clause was added in Python 2.5. Before 716cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters2.5, arenas were never free()'ed, and an arenaindex < maxarena always 717cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peterscorresponded to a currently-allocated arena, so the "P is not controlled by 718cf79aace07a57d480605f4a5aa8b9ca68567792eTim Petersobmalloc, AO corresponds to an unused arena_object, and P < ARENA_SIZE" case 719cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peterswas impossible. 720cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters 721cf79aace07a57d480605f4a5aa8b9ca68567792eTim PetersNote that the logic is excruciating, and reading up possibly uninitialized 722cf79aace07a57d480605f4a5aa8b9ca68567792eTim Petersmemory when P is not controlled by obmalloc (to get at (POOL)->arenaindex) 723cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peterscreates problems for some memory debuggers. The overwhelming advantage is 724cf79aace07a57d480605f4a5aa8b9ca68567792eTim Petersthat this test determines whether an arbitrary address is controlled by 725cf79aace07a57d480605f4a5aa8b9ca68567792eTim Petersobmalloc in a small constant time, independent of the number of arenas 726cf79aace07a57d480605f4a5aa8b9ca68567792eTim Petersobmalloc controls. Since this test is needed at every entry point, it's 727cf79aace07a57d480605f4a5aa8b9ca68567792eTim Petersextremely desirable that it be this fast. 7285a72e76b6938941547dd25f9198db7d17fa36960Antoine Pitrou 7295a72e76b6938941547dd25f9198db7d17fa36960Antoine PitrouSince Py_ADDRESS_IN_RANGE may be reading from memory which was not allocated 7305a72e76b6938941547dd25f9198db7d17fa36960Antoine Pitrouby Python, it is important that (POOL)->arenaindex is read only once, as 7315a72e76b6938941547dd25f9198db7d17fa36960Antoine Pitrouanother thread may be concurrently modifying the value without holding the 7325a72e76b6938941547dd25f9198db7d17fa36960Antoine PitrouGIL. To accomplish this, the arenaindex_temp variable is used to store 7335a72e76b6938941547dd25f9198db7d17fa36960Antoine Pitrou(POOL)->arenaindex for the duration of the Py_ADDRESS_IN_RANGE macro's 7345a72e76b6938941547dd25f9198db7d17fa36960Antoine Pitrouexecution. The caller of the macro is responsible for declaring this 7355a72e76b6938941547dd25f9198db7d17fa36960Antoine Pitrouvariable. 736cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters*/ 737c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou#define Py_ADDRESS_IN_RANGE(P, POOL) \ 7385a72e76b6938941547dd25f9198db7d17fa36960Antoine Pitrou ((arenaindex_temp = (POOL)->arenaindex) < maxarenas && \ 7395a72e76b6938941547dd25f9198db7d17fa36960Antoine Pitrou (uptr)(P) - arenas[arenaindex_temp].address < (uptr)ARENA_SIZE && \ 7405a72e76b6938941547dd25f9198db7d17fa36960Antoine Pitrou arenas[arenaindex_temp].address != 0) 741cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters 7427eb3c9196da5be52a670d6d8dd24939a3c27b594Neal Norwitz 7437eb3c9196da5be52a670d6d8dd24939a3c27b594Neal Norwitz/* This is only useful when running memory debuggers such as 7447eb3c9196da5be52a670d6d8dd24939a3c27b594Neal Norwitz * Purify or Valgrind. Uncomment to use. 7457eb3c9196da5be52a670d6d8dd24939a3c27b594Neal Norwitz * 7466819210b9e4e5719a6f7f9c1725f8fa70a8936f6Martin v. Löwis#define Py_USING_MEMORY_DEBUGGER 747e86b07cc9ad51baa4f5a2854f8a03e7d1b77b817Martin v. Löwis */ 7487eb3c9196da5be52a670d6d8dd24939a3c27b594Neal Norwitz 7497eb3c9196da5be52a670d6d8dd24939a3c27b594Neal Norwitz#ifdef Py_USING_MEMORY_DEBUGGER 7507eb3c9196da5be52a670d6d8dd24939a3c27b594Neal Norwitz 7517eb3c9196da5be52a670d6d8dd24939a3c27b594Neal Norwitz/* Py_ADDRESS_IN_RANGE may access uninitialized memory by design 7527eb3c9196da5be52a670d6d8dd24939a3c27b594Neal Norwitz * This leads to thousands of spurious warnings when using 7537eb3c9196da5be52a670d6d8dd24939a3c27b594Neal Norwitz * Purify or Valgrind. By making a function, we can easily 7547eb3c9196da5be52a670d6d8dd24939a3c27b594Neal Norwitz * suppress the uninitialized memory reads in this one function. 7557eb3c9196da5be52a670d6d8dd24939a3c27b594Neal Norwitz * So we won't ignore real errors elsewhere. 7567eb3c9196da5be52a670d6d8dd24939a3c27b594Neal Norwitz * 7577eb3c9196da5be52a670d6d8dd24939a3c27b594Neal Norwitz * Disable the macro and use a function. 7587eb3c9196da5be52a670d6d8dd24939a3c27b594Neal Norwitz */ 7597eb3c9196da5be52a670d6d8dd24939a3c27b594Neal Norwitz 7607eb3c9196da5be52a670d6d8dd24939a3c27b594Neal Norwitz#undef Py_ADDRESS_IN_RANGE 7617eb3c9196da5be52a670d6d8dd24939a3c27b594Neal Norwitz 762ab772274700baf17e708e8c8d82c78efbaa038cdNeal Norwitz#if defined(__GNUC__) && ((__GNUC__ == 3) && (__GNUC_MINOR__ >= 1) || \ 763918c90ce06d6189f8d24d1dba842382a5cb447d4Stefan Krah (__GNUC__ >= 4)) 764e5e5aa4ea693d18bfc8a5bb352a75e9154da6af9Neal Norwitz#define Py_NO_INLINE __attribute__((__noinline__)) 765e5e5aa4ea693d18bfc8a5bb352a75e9154da6af9Neal Norwitz#else 766e5e5aa4ea693d18bfc8a5bb352a75e9154da6af9Neal Norwitz#define Py_NO_INLINE 767e5e5aa4ea693d18bfc8a5bb352a75e9154da6af9Neal Norwitz#endif 768e5e5aa4ea693d18bfc8a5bb352a75e9154da6af9Neal Norwitz 769e5e5aa4ea693d18bfc8a5bb352a75e9154da6af9Neal Norwitz/* Don't make static, to try to ensure this isn't inlined. */ 770e5e5aa4ea693d18bfc8a5bb352a75e9154da6af9Neal Norwitzint Py_ADDRESS_IN_RANGE(void *P, poolp pool) Py_NO_INLINE; 771e5e5aa4ea693d18bfc8a5bb352a75e9154da6af9Neal Norwitz#undef Py_NO_INLINE 7727eb3c9196da5be52a670d6d8dd24939a3c27b594Neal Norwitz#endif 773338e010b45d7bd411e2bbcedcd8ef195be40c2beTim Peters 774a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer/*==========================================================================*/ 775a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 77684c1b974675b9252e1f5764a399ff9455fbf73e0Tim Peters/* malloc. Note that nbytes==0 tries to return a non-NULL pointer, distinct 77784c1b974675b9252e1f5764a399ff9455fbf73e0Tim Peters * from all other currently live pointers. This may not be possible. 77884c1b974675b9252e1f5764a399ff9455fbf73e0Tim Peters */ 779a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 780a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer/* 781a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * The basic blocks are ordered by decreasing execution frequency, 782a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * which minimizes the number of jumps in the most common cases, 783a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * improves branching prediction and instruction scheduling (small 784a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * block allocations typically result in a couple of instructions). 785a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * Unless the optimizer reorders everything, being too smart... 786a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer */ 787a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 788d2560cd37c8d38c9eb79bcfce9d780b0753a3cb5Neil Schemenauer#undef PyObject_Malloc 789a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauervoid * 790d2560cd37c8d38c9eb79bcfce9d780b0753a3cb5Neil SchemenauerPyObject_Malloc(size_t nbytes) 791a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer{ 792c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou block *bp; 793c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou poolp pool; 794c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou poolp next; 795c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou uint size; 796a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 79791c12ebc3dc6472ea486ab5e4aa38139283d48adBenjamin Peterson#ifdef WITH_VALGRIND 798c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (UNLIKELY(running_on_valgrind == -1)) 799c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou running_on_valgrind = RUNNING_ON_VALGRIND; 800c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (UNLIKELY(running_on_valgrind)) 801c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou goto redirect; 80291c12ebc3dc6472ea486ab5e4aa38139283d48adBenjamin Peterson#endif 80391c12ebc3dc6472ea486ab5e4aa38139283d48adBenjamin Peterson 804c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* 805c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * Limit ourselves to PY_SSIZE_T_MAX bytes to prevent security holes. 806c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * Most python internals blindly use a signed Py_ssize_t to track 807c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * things without checking for overflows or negatives. 808c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * As size_t is unsigned, checking for nbytes < 0 is not required. 809c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 810c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (nbytes > PY_SSIZE_T_MAX) 811c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return NULL; 812c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 813c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* 814c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * This implicitly redirects malloc(0). 815c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 816c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if ((nbytes - 1) < SMALL_REQUEST_THRESHOLD) { 817c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou LOCK(); 818c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* 819c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * Most frequent paths first 820c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 821c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou size = (uint)(nbytes - 1) >> ALIGNMENT_SHIFT; 822c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou pool = usedpools[size + size]; 823c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (pool != pool->nextpool) { 824c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* 825c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * There is a used pool for this size class. 826c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * Pick up the head block of its free list. 827c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 828c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou ++pool->ref.count; 829c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou bp = pool->freeblock; 830c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(bp != NULL); 831c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if ((pool->freeblock = *(block **)bp) != NULL) { 832c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou UNLOCK(); 833c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return (void *)bp; 834c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 835c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* 836c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * Reached the end of the free list, try to extend it. 837c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 838c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (pool->nextoffset <= pool->maxnextoffset) { 839c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* There is room for another block. */ 840c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou pool->freeblock = (block*)pool + 841c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou pool->nextoffset; 842c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou pool->nextoffset += INDEX2SIZE(size); 843c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou *(block **)(pool->freeblock) = NULL; 844c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou UNLOCK(); 845c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return (void *)bp; 846c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 847c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Pool is full, unlink from used pools. */ 848c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou next = pool->nextpool; 849c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou pool = pool->prevpool; 850c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou next->prevpool = pool; 851c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou pool->nextpool = next; 852c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou UNLOCK(); 853c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return (void *)bp; 854c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 855c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 856c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* There isn't a pool of the right size class immediately 857c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * available: use a free pool. 858c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 859c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (usable_arenas == NULL) { 860c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* No arena has a free pool: allocate a new arena. */ 861cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters#ifdef WITH_MEMORY_LIMITS 862c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (narenas_currently_allocated >= MAX_ARENAS) { 863c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou UNLOCK(); 864c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou goto redirect; 865c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 866cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters#endif 867c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou usable_arenas = new_arena(); 868c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (usable_arenas == NULL) { 869c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou UNLOCK(); 870c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou goto redirect; 871c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 872c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou usable_arenas->nextarena = 873c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou usable_arenas->prevarena = NULL; 874c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 875c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(usable_arenas->address != 0); 876c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 877c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Try to get a cached free pool. */ 878c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou pool = usable_arenas->freepools; 879c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (pool != NULL) { 880c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Unlink from cached pools. */ 881c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou usable_arenas->freepools = pool->nextpool; 882c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 883c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* This arena already had the smallest nfreepools 884c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * value, so decreasing nfreepools doesn't change 885c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * that, and we don't need to rearrange the 886c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * usable_arenas list. However, if the arena has 887c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * become wholly allocated, we need to remove its 888c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * arena_object from usable_arenas. 889c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 890c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou --usable_arenas->nfreepools; 891c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (usable_arenas->nfreepools == 0) { 892c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Wholly allocated: remove. */ 893c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(usable_arenas->freepools == NULL); 894c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(usable_arenas->nextarena == NULL || 895c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou usable_arenas->nextarena->prevarena == 896c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou usable_arenas); 897c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 898c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou usable_arenas = usable_arenas->nextarena; 899c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (usable_arenas != NULL) { 900c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou usable_arenas->prevarena = NULL; 901c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(usable_arenas->address != 0); 902c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 903c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 904c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou else { 905c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* nfreepools > 0: it must be that freepools 906c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * isn't NULL, or that we haven't yet carved 907c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * off all the arena's pools for the first 908c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * time. 909c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 910c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(usable_arenas->freepools != NULL || 911c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou usable_arenas->pool_address <= 912c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou (block*)usable_arenas->address + 913c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou ARENA_SIZE - POOL_SIZE); 914c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 915c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou init_pool: 916c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Frontlink to used pools. */ 917c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou next = usedpools[size + size]; /* == prev */ 918c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou pool->nextpool = next; 919c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou pool->prevpool = next; 920c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou next->nextpool = pool; 921c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou next->prevpool = pool; 922c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou pool->ref.count = 1; 923c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (pool->szidx == size) { 924c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Luckily, this pool last contained blocks 925c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * of the same size class, so its header 926c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * and free list are already initialized. 927c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 928c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou bp = pool->freeblock; 929c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou pool->freeblock = *(block **)bp; 930c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou UNLOCK(); 931c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return (void *)bp; 932c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 933c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* 934c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * Initialize the pool header, set up the free list to 935c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * contain just the second block, and return the first 936c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * block. 937c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 938c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou pool->szidx = size; 939c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou size = INDEX2SIZE(size); 940c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou bp = (block *)pool + POOL_OVERHEAD; 941c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou pool->nextoffset = POOL_OVERHEAD + (size << 1); 942c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou pool->maxnextoffset = POOL_SIZE - size; 943c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou pool->freeblock = bp + size; 944c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou *(block **)(pool->freeblock) = NULL; 945c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou UNLOCK(); 946c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return (void *)bp; 947c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 948c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 949c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Carve off a new pool. */ 950c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(usable_arenas->nfreepools > 0); 951c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(usable_arenas->freepools == NULL); 952c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou pool = (poolp)usable_arenas->pool_address; 953c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert((block*)pool <= (block*)usable_arenas->address + 954c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou ARENA_SIZE - POOL_SIZE); 955c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou pool->arenaindex = usable_arenas - arenas; 956c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(&arenas[pool->arenaindex] == usable_arenas); 957c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou pool->szidx = DUMMY_SIZE_IDX; 958c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou usable_arenas->pool_address += POOL_SIZE; 959c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou --usable_arenas->nfreepools; 960c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 961c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (usable_arenas->nfreepools == 0) { 962c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(usable_arenas->nextarena == NULL || 963c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou usable_arenas->nextarena->prevarena == 964c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou usable_arenas); 965c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Unlink the arena: it is completely allocated. */ 966c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou usable_arenas = usable_arenas->nextarena; 967c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (usable_arenas != NULL) { 968c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou usable_arenas->prevarena = NULL; 969c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(usable_arenas->address != 0); 970c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 971c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 972c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 973c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou goto init_pool; 974c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 975c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 976c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* The small block allocator ends here. */ 977a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 978d97a1c008c4a7ae04c55c8de2cdb71a9ea43656aTim Petersredirect: 979c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Redirect the original request to the underlying (libc) allocator. 980c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * We jump here on bigger requests, on error in the code above (as a 981c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * last chance to serve the request) or when the max memory limit 982c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * has been reached. 983c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 984c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (nbytes == 0) 985c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou nbytes = 1; 986c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return (void *)malloc(nbytes); 987a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer} 988a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 989a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer/* free */ 990a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 991d2560cd37c8d38c9eb79bcfce9d780b0753a3cb5Neil Schemenauer#undef PyObject_Free 992b529c249214096a6e08a50399692d124c26dba29Benjamin PetersonATTRIBUTE_NO_ADDRESS_SAFETY_ANALYSIS 993a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauervoid 994d2560cd37c8d38c9eb79bcfce9d780b0753a3cb5Neil SchemenauerPyObject_Free(void *p) 995a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer{ 996c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou poolp pool; 997c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou block *lastfree; 998c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou poolp next, prev; 999c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou uint size; 10005a72e76b6938941547dd25f9198db7d17fa36960Antoine Pitrou#ifndef Py_USING_MEMORY_DEBUGGER 10015a72e76b6938941547dd25f9198db7d17fa36960Antoine Pitrou uint arenaindex_temp; 10025a72e76b6938941547dd25f9198db7d17fa36960Antoine Pitrou#endif 1003a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 1004c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (p == NULL) /* free(NULL) has no effect */ 1005c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return; 1006a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 100791c12ebc3dc6472ea486ab5e4aa38139283d48adBenjamin Peterson#ifdef WITH_VALGRIND 1008c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (UNLIKELY(running_on_valgrind > 0)) 1009c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou goto redirect; 101091c12ebc3dc6472ea486ab5e4aa38139283d48adBenjamin Peterson#endif 101191c12ebc3dc6472ea486ab5e4aa38139283d48adBenjamin Peterson 1012c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou pool = POOL_ADDR(p); 1013c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (Py_ADDRESS_IN_RANGE(p, pool)) { 1014c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* We allocated this address. */ 1015c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou LOCK(); 1016c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Link p to the start of the pool's freeblock list. Since 1017c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * the pool had at least the p block outstanding, the pool 1018c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * wasn't empty (so it's already in a usedpools[] list, or 1019c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * was full and is in no list -- it's not in the freeblocks 1020c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * list in any case). 1021c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 1022c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(pool->ref.count > 0); /* else it was empty */ 1023c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou *(block **)p = lastfree = pool->freeblock; 1024c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou pool->freeblock = (block *)p; 1025c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (lastfree) { 1026c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou struct arena_object* ao; 1027c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou uint nf; /* ao->nfreepools */ 1028c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1029c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* freeblock wasn't NULL, so the pool wasn't full, 1030c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * and the pool is in a usedpools[] list. 1031c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 1032c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (--pool->ref.count != 0) { 1033c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* pool isn't empty: leave it in usedpools */ 1034c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou UNLOCK(); 1035c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return; 1036c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1037c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Pool is now empty: unlink from usedpools, and 1038c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * link to the front of freepools. This ensures that 1039c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * previously freed pools will be allocated later 1040c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * (being not referenced, they are perhaps paged out). 1041c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 1042c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou next = pool->nextpool; 1043c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou prev = pool->prevpool; 1044c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou next->prevpool = prev; 1045c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou prev->nextpool = next; 1046c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1047c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Link the pool to freepools. This is a singly-linked 1048c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * list, and pool->prevpool isn't used there. 1049c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 1050c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou ao = &arenas[pool->arenaindex]; 1051c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou pool->nextpool = ao->freepools; 1052c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou ao->freepools = pool; 1053c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou nf = ++ao->nfreepools; 1054c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1055c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* All the rest is arena management. We just freed 1056c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * a pool, and there are 4 cases for arena mgmt: 1057c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * 1. If all the pools are free, return the arena to 1058c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * the system free(). 1059c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * 2. If this is the only free pool in the arena, 1060c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * add the arena back to the `usable_arenas` list. 1061c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * 3. If the "next" arena has a smaller count of free 1062c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * pools, we have to "slide this arena right" to 1063c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * restore that usable_arenas is sorted in order of 1064c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * nfreepools. 1065c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * 4. Else there's nothing more to do. 1066c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 1067c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (nf == ao->ntotalpools) { 1068c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Case 1. First unlink ao from usable_arenas. 1069c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 1070c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(ao->prevarena == NULL || 1071c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou ao->prevarena->address != 0); 1072c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(ao ->nextarena == NULL || 1073c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou ao->nextarena->address != 0); 1074c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1075c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Fix the pointer in the prevarena, or the 1076c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * usable_arenas pointer. 1077c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 1078c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (ao->prevarena == NULL) { 1079c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou usable_arenas = ao->nextarena; 1080c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(usable_arenas == NULL || 1081c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou usable_arenas->address != 0); 1082c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1083c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou else { 1084c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(ao->prevarena->nextarena == ao); 1085c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou ao->prevarena->nextarena = 1086c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou ao->nextarena; 1087c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1088c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Fix the pointer in the nextarena. */ 1089c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (ao->nextarena != NULL) { 1090c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(ao->nextarena->prevarena == ao); 1091c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou ao->nextarena->prevarena = 1092c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou ao->prevarena; 1093c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1094c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Record that this arena_object slot is 1095c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * available to be reused. 1096c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 1097c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou ao->nextarena = unused_arena_objects; 1098c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou unused_arena_objects = ao; 1099c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1100c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Free the entire arena. */ 1101d16e01cf75a2663c74c2e36beda6397546a8ae52Benjamin Peterson#ifdef ARENAS_USE_MMAP 1102d16e01cf75a2663c74c2e36beda6397546a8ae52Benjamin Peterson munmap((void *)ao->address, ARENA_SIZE); 1103d16e01cf75a2663c74c2e36beda6397546a8ae52Benjamin Peterson#else 1104c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou free((void *)ao->address); 1105d16e01cf75a2663c74c2e36beda6397546a8ae52Benjamin Peterson#endif 1106c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou ao->address = 0; /* mark unassociated */ 1107c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou --narenas_currently_allocated; 1108c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1109c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou UNLOCK(); 1110c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return; 1111c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1112c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (nf == 1) { 1113c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Case 2. Put ao at the head of 1114c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * usable_arenas. Note that because 1115c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * ao->nfreepools was 0 before, ao isn't 1116c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * currently on the usable_arenas list. 1117c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 1118c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou ao->nextarena = usable_arenas; 1119c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou ao->prevarena = NULL; 1120c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (usable_arenas) 1121c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou usable_arenas->prevarena = ao; 1122c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou usable_arenas = ao; 1123c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(usable_arenas->address != 0); 1124c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1125c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou UNLOCK(); 1126c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return; 1127c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1128c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* If this arena is now out of order, we need to keep 1129c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * the list sorted. The list is kept sorted so that 1130c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * the "most full" arenas are used first, which allows 1131c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * the nearly empty arenas to be completely freed. In 1132c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * a few un-scientific tests, it seems like this 1133c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * approach allowed a lot more memory to be freed. 1134c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 1135c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (ao->nextarena == NULL || 1136c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou nf <= ao->nextarena->nfreepools) { 1137c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Case 4. Nothing to do. */ 1138c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou UNLOCK(); 1139c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return; 1140c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1141c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Case 3: We have to move the arena towards the end 1142c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * of the list, because it has more free pools than 1143c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * the arena to its right. 1144c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * First unlink ao from usable_arenas. 1145c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 1146c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (ao->prevarena != NULL) { 1147c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* ao isn't at the head of the list */ 1148c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(ao->prevarena->nextarena == ao); 1149c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou ao->prevarena->nextarena = ao->nextarena; 1150c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1151c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou else { 1152c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* ao is at the head of the list */ 1153c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(usable_arenas == ao); 1154c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou usable_arenas = ao->nextarena; 1155c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1156c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou ao->nextarena->prevarena = ao->prevarena; 1157c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1158c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Locate the new insertion point by iterating over 1159c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * the list, using our nextarena pointer. 1160c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 1161c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou while (ao->nextarena != NULL && 1162c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou nf > ao->nextarena->nfreepools) { 1163c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou ao->prevarena = ao->nextarena; 1164c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou ao->nextarena = ao->nextarena->nextarena; 1165c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1166c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1167c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Insert ao at this point. */ 1168c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(ao->nextarena == NULL || 1169c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou ao->prevarena == ao->nextarena->prevarena); 1170c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(ao->prevarena->nextarena == ao->nextarena); 1171c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1172c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou ao->prevarena->nextarena = ao; 1173c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (ao->nextarena != NULL) 1174c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou ao->nextarena->prevarena = ao; 1175c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1176c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Verify that the swaps worked. */ 1177c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(ao->nextarena == NULL || 1178c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou nf <= ao->nextarena->nfreepools); 1179c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(ao->prevarena == NULL || 1180c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou nf > ao->prevarena->nfreepools); 1181c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(ao->nextarena == NULL || 1182c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou ao->nextarena->prevarena == ao); 1183c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert((usable_arenas == ao && 1184c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou ao->prevarena == NULL) || 1185c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou ao->prevarena->nextarena == ao); 1186c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1187c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou UNLOCK(); 1188c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return; 1189c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1190c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Pool was full, so doesn't currently live in any list: 1191c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * link it to the front of the appropriate usedpools[] list. 1192c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * This mimics LRU pool usage for new allocations and 1193c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * targets optimal filling when several pools contain 1194c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * blocks of the same size class. 1195c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 1196c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou --pool->ref.count; 1197c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(pool->ref.count > 0); /* else the pool is empty */ 1198c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou size = pool->szidx; 1199c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou next = usedpools[size + size]; 1200c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou prev = next->prevpool; 1201c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* insert pool before next: prev <-> pool <-> next */ 1202c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou pool->nextpool = next; 1203c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou pool->prevpool = prev; 1204c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou next->prevpool = pool; 1205c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou prev->nextpool = pool; 1206c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou UNLOCK(); 1207c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return; 1208c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1209d97a1c008c4a7ae04c55c8de2cdb71a9ea43656aTim Peters 121091c12ebc3dc6472ea486ab5e4aa38139283d48adBenjamin Peterson#ifdef WITH_VALGRIND 121191c12ebc3dc6472ea486ab5e4aa38139283d48adBenjamin Petersonredirect: 121291c12ebc3dc6472ea486ab5e4aa38139283d48adBenjamin Peterson#endif 1213c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* We didn't allocate this address. */ 1214c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou free(p); 1215a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer} 1216a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 121784c1b974675b9252e1f5764a399ff9455fbf73e0Tim Peters/* realloc. If p is NULL, this acts like malloc(nbytes). Else if nbytes==0, 121884c1b974675b9252e1f5764a399ff9455fbf73e0Tim Peters * then as the Python docs promise, we do not treat this like free(p), and 121984c1b974675b9252e1f5764a399ff9455fbf73e0Tim Peters * return a non-NULL result. 122084c1b974675b9252e1f5764a399ff9455fbf73e0Tim Peters */ 1221a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 1222d2560cd37c8d38c9eb79bcfce9d780b0753a3cb5Neil Schemenauer#undef PyObject_Realloc 1223b529c249214096a6e08a50399692d124c26dba29Benjamin PetersonATTRIBUTE_NO_ADDRESS_SAFETY_ANALYSIS 1224a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauervoid * 1225d2560cd37c8d38c9eb79bcfce9d780b0753a3cb5Neil SchemenauerPyObject_Realloc(void *p, size_t nbytes) 1226a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer{ 1227c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou void *bp; 1228c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou poolp pool; 1229c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou size_t size; 12305a72e76b6938941547dd25f9198db7d17fa36960Antoine Pitrou#ifndef Py_USING_MEMORY_DEBUGGER 12315a72e76b6938941547dd25f9198db7d17fa36960Antoine Pitrou uint arenaindex_temp; 12325a72e76b6938941547dd25f9198db7d17fa36960Antoine Pitrou#endif 1233c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1234c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (p == NULL) 1235c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return PyObject_Malloc(nbytes); 1236c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1237c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* 1238c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * Limit ourselves to PY_SSIZE_T_MAX bytes to prevent security holes. 1239c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * Most python internals blindly use a signed Py_ssize_t to track 1240c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * things without checking for overflows or negatives. 1241c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * As size_t is unsigned, checking for nbytes < 0 is not required. 1242c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 1243c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (nbytes > PY_SSIZE_T_MAX) 1244c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return NULL; 12450470bab69783c13447cb634fa403ef1067fe56d1Gregory P. Smith 124691c12ebc3dc6472ea486ab5e4aa38139283d48adBenjamin Peterson#ifdef WITH_VALGRIND 1247c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Treat running_on_valgrind == -1 the same as 0 */ 1248c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (UNLIKELY(running_on_valgrind > 0)) 1249c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou goto redirect; 125091c12ebc3dc6472ea486ab5e4aa38139283d48adBenjamin Peterson#endif 125191c12ebc3dc6472ea486ab5e4aa38139283d48adBenjamin Peterson 1252c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou pool = POOL_ADDR(p); 1253c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (Py_ADDRESS_IN_RANGE(p, pool)) { 1254c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* We're in charge of this block */ 1255c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou size = INDEX2SIZE(pool->szidx); 1256c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (nbytes <= size) { 1257c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* The block is staying the same or shrinking. If 1258c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * it's shrinking, there's a tradeoff: it costs 1259c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * cycles to copy the block to a smaller size class, 1260c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * but it wastes memory not to copy it. The 1261c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * compromise here is to copy on shrink only if at 1262c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * least 25% of size can be shaved off. 1263c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 1264c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (4 * nbytes > 3 * size) { 1265c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* It's the same, 1266c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * or shrinking and new/old > 3/4. 1267c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 1268c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return p; 1269c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1270c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou size = nbytes; 1271c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1272c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou bp = PyObject_Malloc(nbytes); 1273c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (bp != NULL) { 1274c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou memcpy(bp, p, size); 1275c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou PyObject_Free(p); 1276c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1277c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return bp; 1278c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 127991c12ebc3dc6472ea486ab5e4aa38139283d48adBenjamin Peterson#ifdef WITH_VALGRIND 128091c12ebc3dc6472ea486ab5e4aa38139283d48adBenjamin Peterson redirect: 128191c12ebc3dc6472ea486ab5e4aa38139283d48adBenjamin Peterson#endif 1282c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* We're not managing this block. If nbytes <= 1283c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * SMALL_REQUEST_THRESHOLD, it's tempting to try to take over this 1284c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * block. However, if we do, we need to copy the valid data from 1285c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * the C-managed block to one of our blocks, and there's no portable 1286c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * way to know how much of the memory space starting at p is valid. 1287c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * As bug 1185883 pointed out the hard way, it's possible that the 1288c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * C-managed block is "at the end" of allocated VM space, so that 1289c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * a memory fault can occur if we try to copy nbytes bytes starting 1290c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * at p. Instead we punt: let C continue to manage this block. 1291c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 1292c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (nbytes) 1293c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return realloc(p, nbytes); 1294c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* C doesn't define the result of realloc(p, 0) (it may or may not 1295c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * return NULL then), but Python's docs promise that nbytes==0 never 1296c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * returns NULL. We don't pass 0 to realloc(), to avoid that endcase 1297c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * to begin with. Even then, we can't be sure that realloc() won't 1298c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * return NULL. 1299c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 1300c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou bp = realloc(p, 1); 1301c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return bp ? bp : p; 1302a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer} 1303a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 1304c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou#else /* ! WITH_PYMALLOC */ 1305ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters 1306ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters/*==========================================================================*/ 1307d2560cd37c8d38c9eb79bcfce9d780b0753a3cb5Neil Schemenauer/* pymalloc not enabled: Redirect the entry points to malloc. These will 1308d2560cd37c8d38c9eb79bcfce9d780b0753a3cb5Neil Schemenauer * only be used by extensions that are compiled with pymalloc enabled. */ 130962c06ba6a9aa388555d826b4adb5d8981d74f4b2Tim Peters 1310ce7fb9b5151f7238bdbaeb16c3041c9990ca8e9dTim Petersvoid * 1311d2560cd37c8d38c9eb79bcfce9d780b0753a3cb5Neil SchemenauerPyObject_Malloc(size_t n) 13121221c0a435135143632d986e861d9243d3d2ad35Tim Peters{ 1313c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return PyMem_MALLOC(n); 13141221c0a435135143632d986e861d9243d3d2ad35Tim Peters} 13151221c0a435135143632d986e861d9243d3d2ad35Tim Peters 1316ce7fb9b5151f7238bdbaeb16c3041c9990ca8e9dTim Petersvoid * 1317d2560cd37c8d38c9eb79bcfce9d780b0753a3cb5Neil SchemenauerPyObject_Realloc(void *p, size_t n) 13181221c0a435135143632d986e861d9243d3d2ad35Tim Peters{ 1319c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return PyMem_REALLOC(p, n); 13201221c0a435135143632d986e861d9243d3d2ad35Tim Peters} 13211221c0a435135143632d986e861d9243d3d2ad35Tim Peters 13221221c0a435135143632d986e861d9243d3d2ad35Tim Petersvoid 1323d2560cd37c8d38c9eb79bcfce9d780b0753a3cb5Neil SchemenauerPyObject_Free(void *p) 13241221c0a435135143632d986e861d9243d3d2ad35Tim Peters{ 1325c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou PyMem_FREE(p); 13261221c0a435135143632d986e861d9243d3d2ad35Tim Peters} 13271221c0a435135143632d986e861d9243d3d2ad35Tim Peters#endif /* WITH_PYMALLOC */ 13281221c0a435135143632d986e861d9243d3d2ad35Tim Peters 1329ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters#ifdef PYMALLOC_DEBUG 1330ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters/*==========================================================================*/ 133162c06ba6a9aa388555d826b4adb5d8981d74f4b2Tim Peters/* A x-platform debugging allocator. This doesn't manage memory directly, 133262c06ba6a9aa388555d826b4adb5d8981d74f4b2Tim Peters * it wraps a real allocator, adding extra debugging info to the memory blocks. 133362c06ba6a9aa388555d826b4adb5d8981d74f4b2Tim Peters */ 1334ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters 1335f6fb501c577ede5c3681a703925abf36e69bc5b9Tim Peters/* Special bytes broadcast into debug memory blocks at appropriate times. 1336f6fb501c577ede5c3681a703925abf36e69bc5b9Tim Peters * Strings of these are unlikely to be valid addresses, floats, ints or 1337f6fb501c577ede5c3681a703925abf36e69bc5b9Tim Peters * 7-bit ASCII. 1338f6fb501c577ede5c3681a703925abf36e69bc5b9Tim Peters */ 1339f6fb501c577ede5c3681a703925abf36e69bc5b9Tim Peters#undef CLEANBYTE 1340f6fb501c577ede5c3681a703925abf36e69bc5b9Tim Peters#undef DEADBYTE 1341f6fb501c577ede5c3681a703925abf36e69bc5b9Tim Peters#undef FORBIDDENBYTE 1342f6fb501c577ede5c3681a703925abf36e69bc5b9Tim Peters#define CLEANBYTE 0xCB /* clean (newly allocated) memory */ 1343889f61dcfbdccf4d1de7da354ee6165e488e4665Tim Peters#define DEADBYTE 0xDB /* dead (newly freed) memory */ 1344f6fb501c577ede5c3681a703925abf36e69bc5b9Tim Peters#define FORBIDDENBYTE 0xFB /* untouchable bytes at each end of a block */ 1345ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters 134602ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónsson/* We tag each block with an API ID in order to tag API violations */ 134702ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónsson#define _PYMALLOC_MEM_ID 'm' /* the PyMem_Malloc() API */ 134802ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónsson#define _PYMALLOC_OBJ_ID 'o' /* The PyObject_Malloc() API */ 134902ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónsson 1350c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitroustatic size_t serialno = 0; /* incremented on each debug {m,re}alloc */ 1351ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters 1352e085017ab7121b27be315d36ef0c25ed51484023Tim Peters/* serialno is always incremented via calling this routine. The point is 13539ea89d2a1972a527bee508c3fb8cd42a86908da1Tim Peters * to supply a single place to set a breakpoint. 13549ea89d2a1972a527bee508c3fb8cd42a86908da1Tim Peters */ 1355e085017ab7121b27be315d36ef0c25ed51484023Tim Petersstatic void 1356bd02b14255f99feef90121cf654989b9fe827210Neil Schemenauerbumpserialno(void) 1357e085017ab7121b27be315d36ef0c25ed51484023Tim Peters{ 1358c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou ++serialno; 1359e085017ab7121b27be315d36ef0c25ed51484023Tim Peters} 1360e085017ab7121b27be315d36ef0c25ed51484023Tim Peters 13619ea89d2a1972a527bee508c3fb8cd42a86908da1Tim Peters#define SST SIZEOF_SIZE_T 1362e085017ab7121b27be315d36ef0c25ed51484023Tim Peters 13639ea89d2a1972a527bee508c3fb8cd42a86908da1Tim Peters/* Read sizeof(size_t) bytes at p as a big-endian size_t. */ 13649ea89d2a1972a527bee508c3fb8cd42a86908da1Tim Petersstatic size_t 13659ea89d2a1972a527bee508c3fb8cd42a86908da1Tim Petersread_size_t(const void *p) 1366ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters{ 1367c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou const uchar *q = (const uchar *)p; 1368c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou size_t result = *q++; 1369c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou int i; 13709ea89d2a1972a527bee508c3fb8cd42a86908da1Tim Peters 1371c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou for (i = SST; --i > 0; ++q) 1372c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou result = (result << 8) | *q; 1373c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return result; 1374ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters} 1375ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters 13769ea89d2a1972a527bee508c3fb8cd42a86908da1Tim Peters/* Write n as a big-endian size_t, MSB at address p, LSB at 13779ea89d2a1972a527bee508c3fb8cd42a86908da1Tim Peters * p + sizeof(size_t) - 1. 13789ea89d2a1972a527bee508c3fb8cd42a86908da1Tim Peters */ 1379ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Petersstatic void 13809ea89d2a1972a527bee508c3fb8cd42a86908da1Tim Peterswrite_size_t(void *p, size_t n) 1381ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters{ 1382c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou uchar *q = (uchar *)p + SST - 1; 1383c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou int i; 13849ea89d2a1972a527bee508c3fb8cd42a86908da1Tim Peters 1385c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou for (i = SST; --i >= 0; --q) { 1386c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou *q = (uchar)(n & 0xff); 1387c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou n >>= 8; 1388c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1389ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters} 1390ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters 139108d821582faab8f3b6eeab1b1fd7520417b82b80Tim Peters#ifdef Py_DEBUG 139208d821582faab8f3b6eeab1b1fd7520417b82b80Tim Peters/* Is target in the list? The list is traversed via the nextpool pointers. 139308d821582faab8f3b6eeab1b1fd7520417b82b80Tim Peters * The list may be NULL-terminated, or circular. Return 1 if target is in 139408d821582faab8f3b6eeab1b1fd7520417b82b80Tim Peters * list, else 0. 139508d821582faab8f3b6eeab1b1fd7520417b82b80Tim Peters */ 139608d821582faab8f3b6eeab1b1fd7520417b82b80Tim Petersstatic int 139708d821582faab8f3b6eeab1b1fd7520417b82b80Tim Peterspool_is_in_list(const poolp target, poolp list) 139808d821582faab8f3b6eeab1b1fd7520417b82b80Tim Peters{ 1399c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou poolp origlist = list; 1400c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(target != NULL); 1401c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (list == NULL) 1402c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return 0; 1403c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou do { 1404c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (target == list) 1405c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return 1; 1406c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou list = list->nextpool; 1407c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } while (list != NULL && list != origlist); 1408c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return 0; 140908d821582faab8f3b6eeab1b1fd7520417b82b80Tim Peters} 141008d821582faab8f3b6eeab1b1fd7520417b82b80Tim Peters 141108d821582faab8f3b6eeab1b1fd7520417b82b80Tim Peters#else 141208d821582faab8f3b6eeab1b1fd7520417b82b80Tim Peters#define pool_is_in_list(X, Y) 1 141308d821582faab8f3b6eeab1b1fd7520417b82b80Tim Peters 1414c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou#endif /* Py_DEBUG */ 141508d821582faab8f3b6eeab1b1fd7520417b82b80Tim Peters 14169ea89d2a1972a527bee508c3fb8cd42a86908da1Tim Peters/* Let S = sizeof(size_t). The debug malloc asks for 4*S extra bytes and 14179ea89d2a1972a527bee508c3fb8cd42a86908da1Tim Peters fills them with useful stuff, here calling the underlying malloc's result p: 1418ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters 14199ea89d2a1972a527bee508c3fb8cd42a86908da1Tim Petersp[0: S] 14209ea89d2a1972a527bee508c3fb8cd42a86908da1Tim Peters Number of bytes originally asked for. This is a size_t, big-endian (easier 14219ea89d2a1972a527bee508c3fb8cd42a86908da1Tim Peters to read in a memory dump). 14229ea89d2a1972a527bee508c3fb8cd42a86908da1Tim Petersp[S: 2*S] 1423f6fb501c577ede5c3681a703925abf36e69bc5b9Tim Peters Copies of FORBIDDENBYTE. Used to catch under- writes and reads. 14249ea89d2a1972a527bee508c3fb8cd42a86908da1Tim Petersp[2*S: 2*S+n] 1425f6fb501c577ede5c3681a703925abf36e69bc5b9Tim Peters The requested memory, filled with copies of CLEANBYTE. 1426ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters Used to catch reference to uninitialized memory. 14279ea89d2a1972a527bee508c3fb8cd42a86908da1Tim Peters &p[2*S] is returned. Note that this is 8-byte aligned if pymalloc 1428ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters handled the request itself. 14299ea89d2a1972a527bee508c3fb8cd42a86908da1Tim Petersp[2*S+n: 2*S+n+S] 1430f6fb501c577ede5c3681a703925abf36e69bc5b9Tim Peters Copies of FORBIDDENBYTE. Used to catch over- writes and reads. 14319ea89d2a1972a527bee508c3fb8cd42a86908da1Tim Petersp[2*S+n+S: 2*S+n+2*S] 1432d2560cd37c8d38c9eb79bcfce9d780b0753a3cb5Neil Schemenauer A serial number, incremented by 1 on each call to _PyObject_DebugMalloc 1433d2560cd37c8d38c9eb79bcfce9d780b0753a3cb5Neil Schemenauer and _PyObject_DebugRealloc. 14349ea89d2a1972a527bee508c3fb8cd42a86908da1Tim Peters This is a big-endian size_t. 1435ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters If "bad memory" is detected later, the serial number gives an 1436ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters excellent way to set a breakpoint on the next run, to capture the 1437ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters instant at which this block was passed out. 1438ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters*/ 1439ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters 144002ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónsson/* debug replacements for the PyMem_* memory API */ 144102ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónssonvoid * 144202ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónsson_PyMem_DebugMalloc(size_t nbytes) 144302ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónsson{ 1444c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return _PyObject_DebugMallocApi(_PYMALLOC_MEM_ID, nbytes); 144502ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónsson} 144602ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónssonvoid * 144702ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónsson_PyMem_DebugRealloc(void *p, size_t nbytes) 144802ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónsson{ 1449c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return _PyObject_DebugReallocApi(_PYMALLOC_MEM_ID, p, nbytes); 145002ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónsson} 145102ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónssonvoid 145202ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónsson_PyMem_DebugFree(void *p) 145302ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónsson{ 1454c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou _PyObject_DebugFreeApi(_PYMALLOC_MEM_ID, p); 145502ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónsson} 145602ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónsson 145702ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónsson/* debug replacements for the PyObject_* memory API */ 1458ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Petersvoid * 1459d2560cd37c8d38c9eb79bcfce9d780b0753a3cb5Neil Schemenauer_PyObject_DebugMalloc(size_t nbytes) 1460ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters{ 1461c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return _PyObject_DebugMallocApi(_PYMALLOC_OBJ_ID, nbytes); 146202ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónsson} 146302ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónssonvoid * 146402ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónsson_PyObject_DebugRealloc(void *p, size_t nbytes) 146502ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónsson{ 1466c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return _PyObject_DebugReallocApi(_PYMALLOC_OBJ_ID, p, nbytes); 146702ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónsson} 146802ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónssonvoid 146902ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónsson_PyObject_DebugFree(void *p) 147002ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónsson{ 1471c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou _PyObject_DebugFreeApi(_PYMALLOC_OBJ_ID, p); 147202ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónsson} 147302ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónssonvoid 1474b331802f976c85954efbeb7a49f2591951460be2Kristján Valur Jónsson_PyObject_DebugCheckAddress(const void *p) 147502ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónsson{ 1476c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou _PyObject_DebugCheckAddressApi(_PYMALLOC_OBJ_ID, p); 147702ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónsson} 147802ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónsson 147902ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónsson 148002ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónsson/* generic debug memory api, with an "id" to identify the API in use */ 148102ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónssonvoid * 148202ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónsson_PyObject_DebugMallocApi(char id, size_t nbytes) 148302ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónsson{ 1484c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou uchar *p; /* base address of malloc'ed block */ 1485c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou uchar *tail; /* p + 2*SST + nbytes == pointer to tail pad bytes */ 1486c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou size_t total; /* nbytes + 4*SST */ 1487c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1488c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou bumpserialno(); 1489c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou total = nbytes + 4*SST; 1490c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (total < nbytes) 1491c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* overflow: can't represent total as a size_t */ 1492c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return NULL; 1493c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1494c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou p = (uchar *)PyObject_Malloc(total); 1495c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (p == NULL) 1496c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return NULL; 1497c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1498c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* at p, write size (SST bytes), id (1 byte), pad (SST-1 bytes) */ 1499c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou write_size_t(p, nbytes); 1500c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou p[SST] = (uchar)id; 1501c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou memset(p + SST + 1 , FORBIDDENBYTE, SST-1); 1502c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1503c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (nbytes > 0) 1504c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou memset(p + 2*SST, CLEANBYTE, nbytes); 1505c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1506c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* at tail, write pad (SST bytes) and serialno (SST bytes) */ 1507c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou tail = p + 2*SST + nbytes; 1508c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou memset(tail, FORBIDDENBYTE, SST); 1509c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou write_size_t(tail + SST, serialno); 1510c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1511c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return p + 2*SST; 1512ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters} 1513ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters 15149ea89d2a1972a527bee508c3fb8cd42a86908da1Tim Peters/* The debug free first checks the 2*SST bytes on each end for sanity (in 151502ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónsson particular, that the FORBIDDENBYTEs with the api ID are still intact). 1516f6fb501c577ede5c3681a703925abf36e69bc5b9Tim Peters Then fills the original bytes with DEADBYTE. 1517ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters Then calls the underlying free. 1518ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters*/ 1519ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Petersvoid 152002ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónsson_PyObject_DebugFreeApi(char api, void *p) 1521ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters{ 1522c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou uchar *q = (uchar *)p - 2*SST; /* address returned from malloc */ 1523c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou size_t nbytes; 1524c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1525c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (p == NULL) 1526c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return; 1527c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou _PyObject_DebugCheckAddressApi(api, p); 1528c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou nbytes = read_size_t(q); 1529c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou nbytes += 4*SST; 1530c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (nbytes > 0) 1531c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou memset(q, DEADBYTE, nbytes); 1532c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou PyObject_Free(q); 1533ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters} 1534ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters 1535ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Petersvoid * 153602ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónsson_PyObject_DebugReallocApi(char api, void *p, size_t nbytes) 1537ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters{ 1538c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou uchar *q = (uchar *)p; 1539c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou uchar *tail; 1540c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou size_t total; /* nbytes + 4*SST */ 1541c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou size_t original_nbytes; 1542c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou int i; 1543c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1544c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (p == NULL) 1545c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return _PyObject_DebugMallocApi(api, nbytes); 1546c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1547c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou _PyObject_DebugCheckAddressApi(api, p); 1548c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou bumpserialno(); 1549c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou original_nbytes = read_size_t(q - 2*SST); 1550c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou total = nbytes + 4*SST; 1551c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (total < nbytes) 1552c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* overflow: can't represent total as a size_t */ 1553c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return NULL; 1554c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1555c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (nbytes < original_nbytes) { 1556c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* shrinking: mark old extra memory dead */ 1557c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou memset(q + nbytes, DEADBYTE, original_nbytes - nbytes + 2*SST); 1558c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1559c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1560c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Resize and add decorations. We may get a new pointer here, in which 1561c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * case we didn't get the chance to mark the old memory with DEADBYTE, 1562c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * but we live with that. 1563c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 1564c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou q = (uchar *)PyObject_Realloc(q - 2*SST, total); 1565c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (q == NULL) 1566c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return NULL; 1567c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1568c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou write_size_t(q, nbytes); 1569c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(q[SST] == (uchar)api); 1570c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou for (i = 1; i < SST; ++i) 1571c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(q[SST + i] == FORBIDDENBYTE); 1572c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou q += 2*SST; 1573c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou tail = q + nbytes; 1574c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou memset(tail, FORBIDDENBYTE, SST); 1575c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou write_size_t(tail + SST, serialno); 1576c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1577c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (nbytes > original_nbytes) { 1578c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* growing: mark new extra memory clean */ 1579c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou memset(q + original_nbytes, CLEANBYTE, 1580918c90ce06d6189f8d24d1dba842382a5cb447d4Stefan Krah nbytes - original_nbytes); 1581c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1582c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1583c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return q; 1584ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters} 1585ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters 15867ccfadf3a88fb83ffa9cee2a3ff41910aa5a00ecTim Peters/* Check the forbidden bytes on both ends of the memory allocated for p. 1587d2560cd37c8d38c9eb79bcfce9d780b0753a3cb5Neil Schemenauer * If anything is wrong, print info to stderr via _PyObject_DebugDumpAddress, 15887ccfadf3a88fb83ffa9cee2a3ff41910aa5a00ecTim Peters * and call Py_FatalError to kill the program. 158902ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónsson * The API id, is also checked. 15907ccfadf3a88fb83ffa9cee2a3ff41910aa5a00ecTim Peters */ 15917ccfadf3a88fb83ffa9cee2a3ff41910aa5a00ecTim Peters void 159202ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónsson_PyObject_DebugCheckAddressApi(char api, const void *p) 1593ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters{ 1594c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou const uchar *q = (const uchar *)p; 1595c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou char msgbuf[64]; 1596c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou char *msg; 1597c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou size_t nbytes; 1598c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou const uchar *tail; 1599c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou int i; 1600c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou char id; 1601c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1602c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (p == NULL) { 1603c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou msg = "didn't expect a NULL pointer"; 1604c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou goto error; 1605c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1606c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1607c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Check the API id */ 1608c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou id = (char)q[-SST]; 1609c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (id != api) { 1610c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou msg = msgbuf; 1611c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou snprintf(msg, sizeof(msgbuf), "bad ID: Allocated using API '%c', verified using API '%c'", id, api); 1612c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou msgbuf[sizeof(msgbuf)-1] = 0; 1613c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou goto error; 1614c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1615c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1616c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Check the stuff at the start of p first: if there's underwrite 1617c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * corruption, the number-of-bytes field may be nuts, and checking 1618c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * the tail could lead to a segfault then. 1619c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 1620c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou for (i = SST-1; i >= 1; --i) { 1621c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (*(q-i) != FORBIDDENBYTE) { 1622c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou msg = "bad leading pad byte"; 1623c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou goto error; 1624c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1625c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1626c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1627c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou nbytes = read_size_t(q - 2*SST); 1628c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou tail = q + nbytes; 1629c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou for (i = 0; i < SST; ++i) { 1630c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (tail[i] != FORBIDDENBYTE) { 1631c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou msg = "bad trailing pad byte"; 1632c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou goto error; 1633c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1634c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1635c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1636c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return; 1637d1139e043c74fd2495ded3cb534c7e0a339532e2Tim Peters 1638d1139e043c74fd2495ded3cb534c7e0a339532e2Tim Peterserror: 1639c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou _PyObject_DebugDumpAddress(p); 1640c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou Py_FatalError(msg); 1641ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters} 1642ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters 16437ccfadf3a88fb83ffa9cee2a3ff41910aa5a00ecTim Peters/* Display info to stderr about the memory block at p. */ 1644ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Petersvoid 1645d2560cd37c8d38c9eb79bcfce9d780b0753a3cb5Neil Schemenauer_PyObject_DebugDumpAddress(const void *p) 1646ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters{ 1647c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou const uchar *q = (const uchar *)p; 1648c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou const uchar *tail; 1649c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou size_t nbytes, serial; 1650c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou int i; 1651c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou int ok; 1652c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou char id; 1653c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1654c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou fprintf(stderr, "Debug memory block at address p=%p:", p); 1655c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (p == NULL) { 1656c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou fprintf(stderr, "\n"); 1657c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return; 1658c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1659c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou id = (char)q[-SST]; 1660c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou fprintf(stderr, " API '%c'\n", id); 1661c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1662c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou nbytes = read_size_t(q - 2*SST); 1663c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou fprintf(stderr, " %" PY_FORMAT_SIZE_T "u bytes originally " 1664c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou "requested\n", nbytes); 1665c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1666c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* In case this is nuts, check the leading pad bytes first. */ 1667c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou fprintf(stderr, " The %d pad bytes at p-%d are ", SST-1, SST-1); 1668c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou ok = 1; 1669c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou for (i = 1; i <= SST-1; ++i) { 1670c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (*(q-i) != FORBIDDENBYTE) { 1671c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou ok = 0; 1672c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou break; 1673c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1674c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1675c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (ok) 1676c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou fputs("FORBIDDENBYTE, as expected.\n", stderr); 1677c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou else { 1678c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou fprintf(stderr, "not all FORBIDDENBYTE (0x%02x):\n", 1679c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou FORBIDDENBYTE); 1680c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou for (i = SST-1; i >= 1; --i) { 1681c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou const uchar byte = *(q-i); 1682c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou fprintf(stderr, " at p-%d: 0x%02x", i, byte); 1683c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (byte != FORBIDDENBYTE) 1684c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou fputs(" *** OUCH", stderr); 1685c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou fputc('\n', stderr); 1686c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1687c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1688c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou fputs(" Because memory is corrupted at the start, the " 1689c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou "count of bytes requested\n" 1690c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou " may be bogus, and checking the trailing pad " 1691c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou "bytes may segfault.\n", stderr); 1692c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1693c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1694c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou tail = q + nbytes; 1695c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou fprintf(stderr, " The %d pad bytes at tail=%p are ", SST, tail); 1696c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou ok = 1; 1697c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou for (i = 0; i < SST; ++i) { 1698c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (tail[i] != FORBIDDENBYTE) { 1699c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou ok = 0; 1700c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou break; 1701c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1702c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1703c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (ok) 1704c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou fputs("FORBIDDENBYTE, as expected.\n", stderr); 1705c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou else { 1706c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou fprintf(stderr, "not all FORBIDDENBYTE (0x%02x):\n", 1707918c90ce06d6189f8d24d1dba842382a5cb447d4Stefan Krah FORBIDDENBYTE); 1708c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou for (i = 0; i < SST; ++i) { 1709c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou const uchar byte = tail[i]; 1710c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou fprintf(stderr, " at tail+%d: 0x%02x", 1711918c90ce06d6189f8d24d1dba842382a5cb447d4Stefan Krah i, byte); 1712c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (byte != FORBIDDENBYTE) 1713c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou fputs(" *** OUCH", stderr); 1714c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou fputc('\n', stderr); 1715c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1716c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1717c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1718c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou serial = read_size_t(tail + SST); 1719c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou fprintf(stderr, " The block was made by call #%" PY_FORMAT_SIZE_T 1720c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou "u to debug malloc/realloc.\n", serial); 1721c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1722c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (nbytes > 0) { 1723c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou i = 0; 1724c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou fputs(" Data at p:", stderr); 1725c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* print up to 8 bytes at the start */ 1726c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou while (q < tail && i < 8) { 1727c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou fprintf(stderr, " %02x", *q); 1728c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou ++i; 1729c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou ++q; 1730c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1731c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* and up to 8 at the end */ 1732c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (q < tail) { 1733c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (tail - q > 8) { 1734c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou fputs(" ...", stderr); 1735c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou q = tail - 8; 1736c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1737c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou while (q < tail) { 1738c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou fprintf(stderr, " %02x", *q); 1739c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou ++q; 1740c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1741c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1742c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou fputc('\n', stderr); 1743c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1744ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters} 1745ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters 17469ea89d2a1972a527bee508c3fb8cd42a86908da1Tim Petersstatic size_t 17479ea89d2a1972a527bee508c3fb8cd42a86908da1Tim Petersprintone(const char* msg, size_t value) 174816bcb6b1afc46f2f73e207bc0484f016c51f0fd9Tim Peters{ 1749c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou int i, k; 1750c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou char buf[100]; 1751c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou size_t origvalue = value; 1752c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1753c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou fputs(msg, stderr); 1754c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou for (i = (int)strlen(msg); i < 35; ++i) 1755c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou fputc(' ', stderr); 1756c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou fputc('=', stderr); 1757c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1758c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Write the value with commas. */ 1759c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou i = 22; 1760c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou buf[i--] = '\0'; 1761c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou buf[i--] = '\n'; 1762c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou k = 3; 1763c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou do { 1764c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou size_t nextvalue = value / 10; 17658e830a06643384d0c33432207585e5b0702d18a5Benjamin Peterson unsigned int digit = (unsigned int)(value - nextvalue * 10); 1766c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou value = nextvalue; 1767c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou buf[i--] = (char)(digit + '0'); 1768c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou --k; 1769c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (k == 0 && value && i >= 0) { 1770c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou k = 3; 1771c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou buf[i--] = ','; 1772c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1773c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } while (value && i >= 0); 1774c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1775c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou while (i >= 0) 1776c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou buf[i--] = ' '; 1777c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou fputs(buf, stderr); 1778c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1779c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return origvalue; 178016bcb6b1afc46f2f73e207bc0484f016c51f0fd9Tim Peters} 178116bcb6b1afc46f2f73e207bc0484f016c51f0fd9Tim Peters 178208d821582faab8f3b6eeab1b1fd7520417b82b80Tim Peters/* Print summary info to stderr about the state of pymalloc's structures. 178308d821582faab8f3b6eeab1b1fd7520417b82b80Tim Peters * In Py_DEBUG mode, also perform some expensive internal consistency 178408d821582faab8f3b6eeab1b1fd7520417b82b80Tim Peters * checks. 178508d821582faab8f3b6eeab1b1fd7520417b82b80Tim Peters */ 17867ccfadf3a88fb83ffa9cee2a3ff41910aa5a00ecTim Petersvoid 17870e871188e8cd9a4e41be7c734e250bfce2d92d56Tim Peters_PyObject_DebugMallocStats(void) 17887ccfadf3a88fb83ffa9cee2a3ff41910aa5a00ecTim Peters{ 1789c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou uint i; 1790c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou const uint numclasses = SMALL_REQUEST_THRESHOLD >> ALIGNMENT_SHIFT; 1791c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* # of pools, allocated blocks, and free blocks per class index */ 1792c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou size_t numpools[SMALL_REQUEST_THRESHOLD >> ALIGNMENT_SHIFT]; 1793c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou size_t numblocks[SMALL_REQUEST_THRESHOLD >> ALIGNMENT_SHIFT]; 1794c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou size_t numfreeblocks[SMALL_REQUEST_THRESHOLD >> ALIGNMENT_SHIFT]; 1795c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* total # of allocated bytes in used and full pools */ 1796c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou size_t allocated_bytes = 0; 1797c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* total # of available bytes in used pools */ 1798c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou size_t available_bytes = 0; 1799c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* # of free pools + pools not yet carved out of current arena */ 1800c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou uint numfreepools = 0; 1801c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* # of bytes for arena alignment padding */ 1802c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou size_t arena_alignment = 0; 1803c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* # of bytes in used and full pools used for pool_headers */ 1804c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou size_t pool_header_bytes = 0; 1805c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* # of bytes in used and full pools wasted due to quantization, 1806c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * i.e. the necessarily leftover space at the ends of used and 1807c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * full pools. 1808c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 1809c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou size_t quantization = 0; 1810c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* # of arenas actually allocated. */ 1811c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou size_t narenas = 0; 1812c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* running total -- should equal narenas * ARENA_SIZE */ 1813c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou size_t total; 1814c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou char buf[128]; 1815c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1816c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou fprintf(stderr, "Small block threshold = %d, in %u size classes.\n", 1817918c90ce06d6189f8d24d1dba842382a5cb447d4Stefan Krah SMALL_REQUEST_THRESHOLD, numclasses); 1818c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1819c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou for (i = 0; i < numclasses; ++i) 1820c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou numpools[i] = numblocks[i] = numfreeblocks[i] = 0; 1821c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1822c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Because full pools aren't linked to from anything, it's easiest 1823c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * to march over all the arenas. If we're lucky, most of the memory 1824c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * will be living in full pools -- would be a shame to miss them. 1825c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 1826c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou for (i = 0; i < maxarenas; ++i) { 1827c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou uint j; 1828c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou uptr base = arenas[i].address; 1829c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1830c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Skip arenas which are not allocated. */ 1831c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (arenas[i].address == (uptr)NULL) 1832c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou continue; 1833c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou narenas += 1; 1834c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1835c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou numfreepools += arenas[i].nfreepools; 1836c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1837c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* round up to pool alignment */ 1838c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (base & (uptr)POOL_SIZE_MASK) { 1839c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou arena_alignment += POOL_SIZE; 1840c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou base &= ~(uptr)POOL_SIZE_MASK; 1841c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou base += POOL_SIZE; 1842c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1843c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1844c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* visit every pool in the arena */ 1845c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(base <= (uptr) arenas[i].pool_address); 1846c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou for (j = 0; 1847c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou base < (uptr) arenas[i].pool_address; 1848c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou ++j, base += POOL_SIZE) { 1849c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou poolp p = (poolp)base; 1850c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou const uint sz = p->szidx; 1851c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou uint freeblocks; 1852c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1853c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (p->ref.count == 0) { 1854c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* currently unused */ 1855c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(pool_is_in_list(p, arenas[i].freepools)); 1856c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou continue; 1857c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1858c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou ++numpools[sz]; 1859c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou numblocks[sz] += p->ref.count; 1860c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou freeblocks = NUMBLOCKS(sz) - p->ref.count; 1861c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou numfreeblocks[sz] += freeblocks; 186208d821582faab8f3b6eeab1b1fd7520417b82b80Tim Peters#ifdef Py_DEBUG 1863c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (freeblocks > 0) 1864c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(pool_is_in_list(p, usedpools[sz + sz])); 186508d821582faab8f3b6eeab1b1fd7520417b82b80Tim Peters#endif 1866c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1867c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1868c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(narenas == narenas_currently_allocated); 1869c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1870c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou fputc('\n', stderr); 1871c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou fputs("class size num pools blocks in use avail blocks\n" 1872c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou "----- ---- --------- ------------- ------------\n", 1873918c90ce06d6189f8d24d1dba842382a5cb447d4Stefan Krah stderr); 1874c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1875c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou for (i = 0; i < numclasses; ++i) { 1876c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou size_t p = numpools[i]; 1877c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou size_t b = numblocks[i]; 1878c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou size_t f = numfreeblocks[i]; 1879c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou uint size = INDEX2SIZE(i); 1880c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (p == 0) { 1881c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(b == 0 && f == 0); 1882c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou continue; 1883c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1884c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou fprintf(stderr, "%5u %6u " 1885c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou "%11" PY_FORMAT_SIZE_T "u " 1886c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou "%15" PY_FORMAT_SIZE_T "u " 1887c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou "%13" PY_FORMAT_SIZE_T "u\n", 1888918c90ce06d6189f8d24d1dba842382a5cb447d4Stefan Krah i, size, p, b, f); 1889c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou allocated_bytes += b * size; 1890c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou available_bytes += f * size; 1891c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou pool_header_bytes += p * POOL_OVERHEAD; 1892c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou quantization += p * ((POOL_SIZE - POOL_OVERHEAD) % size); 1893c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1894c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou fputc('\n', stderr); 1895c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou (void)printone("# times object malloc called", serialno); 1896c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1897c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou (void)printone("# arenas allocated total", ntimes_arena_allocated); 1898c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou (void)printone("# arenas reclaimed", ntimes_arena_allocated - narenas); 1899c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou (void)printone("# arenas highwater mark", narenas_highwater); 1900c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou (void)printone("# arenas allocated current", narenas); 1901c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1902c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou PyOS_snprintf(buf, sizeof(buf), 1903c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou "%" PY_FORMAT_SIZE_T "u arenas * %d bytes/arena", 1904c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou narenas, ARENA_SIZE); 1905c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou (void)printone(buf, narenas * ARENA_SIZE); 1906c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1907c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou fputc('\n', stderr); 1908c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1909c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou total = printone("# bytes in allocated blocks", allocated_bytes); 1910c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou total += printone("# bytes in available blocks", available_bytes); 1911c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1912c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou PyOS_snprintf(buf, sizeof(buf), 1913c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou "%u unused pools * %d bytes", numfreepools, POOL_SIZE); 1914c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou total += printone(buf, (size_t)numfreepools * POOL_SIZE); 1915c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1916c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou total += printone("# bytes lost to pool headers", pool_header_bytes); 1917c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou total += printone("# bytes lost to quantization", quantization); 1918c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou total += printone("# bytes lost to arena alignment", arena_alignment); 1919c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou (void)printone("Total", total); 19207ccfadf3a88fb83ffa9cee2a3ff41910aa5a00ecTim Peters} 19217ccfadf3a88fb83ffa9cee2a3ff41910aa5a00ecTim Peters 1922c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou#endif /* PYMALLOC_DEBUG */ 19237eb3c9196da5be52a670d6d8dd24939a3c27b594Neal Norwitz 19247eb3c9196da5be52a670d6d8dd24939a3c27b594Neal Norwitz#ifdef Py_USING_MEMORY_DEBUGGER 1925cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters/* Make this function last so gcc won't inline it since the definition is 1926cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters * after the reference. 1927cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters */ 19287eb3c9196da5be52a670d6d8dd24939a3c27b594Neal Norwitzint 19297eb3c9196da5be52a670d6d8dd24939a3c27b594Neal NorwitzPy_ADDRESS_IN_RANGE(void *P, poolp pool) 19307eb3c9196da5be52a670d6d8dd24939a3c27b594Neal Norwitz{ 19315a72e76b6938941547dd25f9198db7d17fa36960Antoine Pitrou uint arenaindex_temp = pool->arenaindex; 19325a72e76b6938941547dd25f9198db7d17fa36960Antoine Pitrou 19335a72e76b6938941547dd25f9198db7d17fa36960Antoine Pitrou return arenaindex_temp < maxarenas && 19345a72e76b6938941547dd25f9198db7d17fa36960Antoine Pitrou (uptr)P - arenas[arenaindex_temp].address < (uptr)ARENA_SIZE && 19355a72e76b6938941547dd25f9198db7d17fa36960Antoine Pitrou arenas[arenaindex_temp].address != 0; 19367eb3c9196da5be52a670d6d8dd24939a3c27b594Neal Norwitz} 19377eb3c9196da5be52a670d6d8dd24939a3c27b594Neal Norwitz#endif 1938