obmalloc.c revision d16e01cf75a2663c74c2e36beda6397546a8ae52
11221c0a435135143632d986e861d9243d3d2ad35Tim Peters#include "Python.h" 21221c0a435135143632d986e861d9243d3d2ad35Tim Peters 31221c0a435135143632d986e861d9243d3d2ad35Tim Peters#ifdef WITH_PYMALLOC 41221c0a435135143632d986e861d9243d3d2ad35Tim Peters 5d16e01cf75a2663c74c2e36beda6397546a8ae52Benjamin Peterson#ifdef HAVE_MMAP 6d16e01cf75a2663c74c2e36beda6397546a8ae52Benjamin Peterson #include <sys/mman.h> 7d16e01cf75a2663c74c2e36beda6397546a8ae52Benjamin Peterson #ifdef MAP_ANONYMOUS 8d16e01cf75a2663c74c2e36beda6397546a8ae52Benjamin Peterson #define ARENAS_USE_MMAP 9d16e01cf75a2663c74c2e36beda6397546a8ae52Benjamin Peterson #endif 10d16e01cf75a2663c74c2e36beda6397546a8ae52Benjamin Peterson#endif 11d16e01cf75a2663c74c2e36beda6397546a8ae52Benjamin Peterson 1291c12ebc3dc6472ea486ab5e4aa38139283d48adBenjamin Peterson#ifdef WITH_VALGRIND 1391c12ebc3dc6472ea486ab5e4aa38139283d48adBenjamin Peterson#include <valgrind/valgrind.h> 1491c12ebc3dc6472ea486ab5e4aa38139283d48adBenjamin Peterson 1591c12ebc3dc6472ea486ab5e4aa38139283d48adBenjamin Peterson/* If we're using GCC, use __builtin_expect() to reduce overhead of 1691c12ebc3dc6472ea486ab5e4aa38139283d48adBenjamin Peterson the valgrind checks */ 1791c12ebc3dc6472ea486ab5e4aa38139283d48adBenjamin Peterson#if defined(__GNUC__) && (__GNUC__ > 2) && defined(__OPTIMIZE__) 1891c12ebc3dc6472ea486ab5e4aa38139283d48adBenjamin Peterson# define UNLIKELY(value) __builtin_expect((value), 0) 1991c12ebc3dc6472ea486ab5e4aa38139283d48adBenjamin Peterson#else 2091c12ebc3dc6472ea486ab5e4aa38139283d48adBenjamin Peterson# define UNLIKELY(value) (value) 2191c12ebc3dc6472ea486ab5e4aa38139283d48adBenjamin Peterson#endif 2291c12ebc3dc6472ea486ab5e4aa38139283d48adBenjamin Peterson 2391c12ebc3dc6472ea486ab5e4aa38139283d48adBenjamin Peterson/* -1 indicates that we haven't checked that we're running on valgrind yet. */ 2491c12ebc3dc6472ea486ab5e4aa38139283d48adBenjamin Petersonstatic int running_on_valgrind = -1; 2591c12ebc3dc6472ea486ab5e4aa38139283d48adBenjamin Peterson#endif 2691c12ebc3dc6472ea486ab5e4aa38139283d48adBenjamin Peterson 27a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer/* An object allocator for Python. 28a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 29a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer Here is an introduction to the layers of the Python memory architecture, 30a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer showing where the object allocator is actually used (layer +2), It is 31a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer called for every object allocation and deallocation (PyObject_New/Del), 32a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer unless the object-specific allocators implement a proprietary allocation 33a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer scheme (ex.: ints use a simple free list). This is also the place where 34a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer the cyclic garbage collector operates selectively on container objects. 35a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 36a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 37c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou Object-specific allocators 38a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer _____ ______ ______ ________ 39a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer [ int ] [ dict ] [ list ] ... [ string ] Python core | 40a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer+3 | <----- Object-specific memory -----> | <-- Non-object memory --> | 41a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer _______________________________ | | 42a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer [ Python's object allocator ] | | 43a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer+2 | ####### Object memory ####### | <------ Internal buffers ------> | 44a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer ______________________________________________________________ | 45a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer [ Python's raw memory allocator (PyMem_ API) ] | 46a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer+1 | <----- Python memory (under PyMem manager's control) ------> | | 47a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer __________________________________________________________________ 48a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer [ Underlying general-purpose allocator (ex: C library malloc) ] 49a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 0 | <------ Virtual memory allocated for the python process -------> | 50a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 51a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer ========================================================================= 52a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer _______________________________________________________________________ 53a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer [ OS-specific Virtual Memory Manager (VMM) ] 54a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer-1 | <--- Kernel dynamic storage allocation & management (page-based) ---> | 55a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer __________________________________ __________________________________ 56a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer [ ] [ ] 57a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer-2 | <-- Physical memory: ROM/RAM --> | | <-- Secondary storage (swap) --> | 58a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 59a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer*/ 60a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer/*==========================================================================*/ 61a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 62a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer/* A fast, special-purpose memory allocator for small blocks, to be used 63a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer on top of a general-purpose malloc -- heavily based on previous art. */ 64a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 65a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer/* Vladimir Marangozov -- August 2000 */ 66a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 67a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer/* 68a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * "Memory management is where the rubber meets the road -- if we do the wrong 69a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * thing at any level, the results will not be good. And if we don't make the 70a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * levels work well together, we are in serious trouble." (1) 71a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * 72a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * (1) Paul R. Wilson, Mark S. Johnstone, Michael Neely, and David Boles, 73a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * "Dynamic Storage Allocation: A Survey and Critical Review", 74a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * in Proc. 1995 Int'l. Workshop on Memory Management, September 1995. 75a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer */ 76a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 77c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou/* #undef WITH_MEMORY_LIMITS */ /* disable mem limit checks */ 78a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 79a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer/*==========================================================================*/ 80a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 81a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer/* 82a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * Allocation strategy abstract: 83a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * 84a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * For small requests, the allocator sub-allocates <Big> blocks of memory. 85d16e01cf75a2663c74c2e36beda6397546a8ae52Benjamin Peterson * Requests greater than SMALL_REQUEST_THRESHOLD bytes are routed to the 86d16e01cf75a2663c74c2e36beda6397546a8ae52Benjamin Peterson * system's allocator. 87ce7fb9b5151f7238bdbaeb16c3041c9990ca8e9dTim Peters * 88a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * Small requests are grouped in size classes spaced 8 bytes apart, due 89a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * to the required valid alignment of the returned address. Requests of 90a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * a particular size are serviced from memory pools of 4K (one VMM page). 91a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * Pools are fragmented on demand and contain free lists of blocks of one 92a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * particular size class. In other words, there is a fixed-size allocator 93a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * for each size class. Free pools are shared by the different allocators 94a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * thus minimizing the space reserved for a particular size class. 95a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * 96a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * This allocation strategy is a variant of what is known as "simple 97a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * segregated storage based on array of free lists". The main drawback of 98a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * simple segregated storage is that we might end up with lot of reserved 99a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * memory for the different free lists, which degenerate in time. To avoid 100a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * this, we partition each free list in pools and we share dynamically the 101a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * reserved space between all free lists. This technique is quite efficient 102a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * for memory intensive programs which allocate mainly small-sized blocks. 103a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * 104a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * For small requests we have the following table: 105a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * 106c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * Request in bytes Size of allocated block Size class idx 107a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * ---------------------------------------------------------------- 108a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * 1-8 8 0 109c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * 9-16 16 1 110c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * 17-24 24 2 111c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * 25-32 32 3 112c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * 33-40 40 4 113c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * 41-48 48 5 114c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * 49-56 56 6 115c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * 57-64 64 7 116c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * 65-72 72 8 117c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * ... ... ... 118d16e01cf75a2663c74c2e36beda6397546a8ae52Benjamin Peterson * 497-504 504 62 119d16e01cf75a2663c74c2e36beda6397546a8ae52Benjamin Peterson * 505-512 512 63 120ce7fb9b5151f7238bdbaeb16c3041c9990ca8e9dTim Peters * 121d16e01cf75a2663c74c2e36beda6397546a8ae52Benjamin Peterson * 0, SMALL_REQUEST_THRESHOLD + 1 and up: routed to the underlying 122d16e01cf75a2663c74c2e36beda6397546a8ae52Benjamin Peterson * allocator. 123a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer */ 124a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 125a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer/*==========================================================================*/ 126a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 127a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer/* 128a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * -- Main tunable settings section -- 129a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer */ 130a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 131a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer/* 132a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * Alignment of addresses returned to the user. 8-bytes alignment works 133a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * on most current architectures (with 32-bit or 64-bit address busses). 134a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * The alignment value is also used for grouping small requests in size 135a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * classes spaced ALIGNMENT bytes apart. 136a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * 137a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * You shouldn't change this unless you know what you are doing. 138a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer */ 139c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou#define ALIGNMENT 8 /* must be 2^N */ 140c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou#define ALIGNMENT_SHIFT 3 141c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou#define ALIGNMENT_MASK (ALIGNMENT - 1) 142a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 143e70ddf3a99e5394faf17d78d0764929ae795b674Tim Peters/* Return the number of bytes in size class I, as a uint. */ 144e70ddf3a99e5394faf17d78d0764929ae795b674Tim Peters#define INDEX2SIZE(I) (((uint)(I) + 1) << ALIGNMENT_SHIFT) 145e70ddf3a99e5394faf17d78d0764929ae795b674Tim Peters 146a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer/* 147a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * Max size threshold below which malloc requests are considered to be 148a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * small enough in order to use preallocated memory pools. You can tune 149a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * this value according to your application behaviour and memory needs. 150a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * 151a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * The following invariants must hold: 152c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * 1) ALIGNMENT <= SMALL_REQUEST_THRESHOLD <= 256 153c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * 2) SMALL_REQUEST_THRESHOLD is evenly divisible by ALIGNMENT 154a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * 155d16e01cf75a2663c74c2e36beda6397546a8ae52Benjamin Peterson * Note: a size threshold of 512 guarantees that newly created dictionaries 156d16e01cf75a2663c74c2e36beda6397546a8ae52Benjamin Peterson * will be allocated from preallocated memory pools on 64-bit. 157d16e01cf75a2663c74c2e36beda6397546a8ae52Benjamin Peterson * 158a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * Although not required, for better performance and space efficiency, 159a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * it is recommended that SMALL_REQUEST_THRESHOLD is set to a power of 2. 160a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer */ 161d16e01cf75a2663c74c2e36beda6397546a8ae52Benjamin Peterson#define SMALL_REQUEST_THRESHOLD 512 162c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou#define NB_SMALL_SIZE_CLASSES (SMALL_REQUEST_THRESHOLD / ALIGNMENT) 163a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 164a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer/* 165a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * The system's VMM page size can be obtained on most unices with a 166a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * getpagesize() call or deduced from various header files. To make 167a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * things simpler, we assume that it is 4K, which is OK for most systems. 168a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * It is probably better if this is the native page size, but it doesn't 169ecc6e6a54ed4bb22b8b78dc1eca9183992ac3f40Tim Peters * have to be. In theory, if SYSTEM_PAGE_SIZE is larger than the native page 170ecc6e6a54ed4bb22b8b78dc1eca9183992ac3f40Tim Peters * size, then `POOL_ADDR(p)->arenaindex' could rarely cause a segmentation 171ecc6e6a54ed4bb22b8b78dc1eca9183992ac3f40Tim Peters * violation fault. 4K is apparently OK for all the platforms that python 1728c1402869ba0cb0a690a5168ac4067483d39e02eMartin v. Löwis * currently targets. 173a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer */ 174c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou#define SYSTEM_PAGE_SIZE (4 * 1024) 175c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou#define SYSTEM_PAGE_SIZE_MASK (SYSTEM_PAGE_SIZE - 1) 176a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 177a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer/* 178a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * Maximum amount of memory managed by the allocator for small requests. 179a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer */ 180a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer#ifdef WITH_MEMORY_LIMITS 181a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer#ifndef SMALL_MEMORY_LIMIT 182c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou#define SMALL_MEMORY_LIMIT (64 * 1024 * 1024) /* 64 MB -- more? */ 183a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer#endif 184a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer#endif 185a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 186a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer/* 187a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * The allocator sub-allocates <Big> blocks of memory (called arenas) aligned 188a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * on a page boundary. This is a reserved virtual address space for the 189d16e01cf75a2663c74c2e36beda6397546a8ae52Benjamin Peterson * current process (obtained through a malloc()/mmap() call). In no way this 190d16e01cf75a2663c74c2e36beda6397546a8ae52Benjamin Peterson * means that the memory arenas will be used entirely. A malloc(<Big>) is 191d16e01cf75a2663c74c2e36beda6397546a8ae52Benjamin Peterson * usually an address range reservation for <Big> bytes, unless all pages within 192d16e01cf75a2663c74c2e36beda6397546a8ae52Benjamin Peterson * this space are referenced subsequently. So malloc'ing big blocks and not 193d16e01cf75a2663c74c2e36beda6397546a8ae52Benjamin Peterson * using them does not mean "wasting memory". It's an addressable range 194d16e01cf75a2663c74c2e36beda6397546a8ae52Benjamin Peterson * wastage... 195a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * 196d16e01cf75a2663c74c2e36beda6397546a8ae52Benjamin Peterson * Arenas are allocated with mmap() on systems supporting anonymous memory 197d16e01cf75a2663c74c2e36beda6397546a8ae52Benjamin Peterson * mappings to reduce heap fragmentation. 198a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer */ 199c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou#define ARENA_SIZE (256 << 10) /* 256KB */ 200a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 201a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer#ifdef WITH_MEMORY_LIMITS 202c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou#define MAX_ARENAS (SMALL_MEMORY_LIMIT / ARENA_SIZE) 203a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer#endif 204a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 205a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer/* 206a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * Size of the pools used for small blocks. Should be a power of 2, 207c2ce91af5fbe71c5e12d78b0021701233aacde31Tim Peters * between 1K and SYSTEM_PAGE_SIZE, that is: 1k, 2k, 4k. 208a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer */ 209c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou#define POOL_SIZE SYSTEM_PAGE_SIZE /* must be 2^N */ 210c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou#define POOL_SIZE_MASK SYSTEM_PAGE_SIZE_MASK 211a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 212a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer/* 213a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * -- End of tunable settings section -- 214a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer */ 215a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 216a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer/*==========================================================================*/ 217a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 218a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer/* 219a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * Locking 220a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * 221a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * To reduce lock contention, it would probably be better to refine the 222a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * crude function locking with per size class locking. I'm not positive 223a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * however, whether it's worth switching to such locking policy because 224a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * of the performance penalty it might introduce. 225a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * 226a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * The following macros describe the simplest (should also be the fastest) 227a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * lock object on a particular platform and the init/fini/lock/unlock 228a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * operations on it. The locks defined here are not expected to be recursive 229a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * because it is assumed that they will always be called in the order: 230a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * INIT, [LOCK, UNLOCK]*, FINI. 231a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer */ 232a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 233a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer/* 234a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * Python's threads are serialized, so object malloc locking is disabled. 235a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer */ 236c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou#define SIMPLELOCK_DECL(lock) /* simple lock declaration */ 237c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou#define SIMPLELOCK_INIT(lock) /* allocate (if needed) and initialize */ 238c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou#define SIMPLELOCK_FINI(lock) /* free/destroy an existing lock */ 239c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou#define SIMPLELOCK_LOCK(lock) /* acquire released lock */ 240c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou#define SIMPLELOCK_UNLOCK(lock) /* release acquired lock */ 241a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 242a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer/* 243a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * Basic types 244a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * I don't care if these are defined in <sys/types.h> or elsewhere. Axiom. 245a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer */ 246a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer#undef uchar 247c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou#define uchar unsigned char /* assuming == 8 bits */ 248a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 249a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer#undef uint 250c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou#define uint unsigned int /* assuming >= 16 bits */ 251a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 252a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer#undef ulong 253c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou#define ulong unsigned long /* assuming >= 32 bits */ 254a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 255d97a1c008c4a7ae04c55c8de2cdb71a9ea43656aTim Peters#undef uptr 256c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou#define uptr Py_uintptr_t 257d97a1c008c4a7ae04c55c8de2cdb71a9ea43656aTim Peters 258a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer/* When you say memory, my mind reasons in terms of (pointers to) blocks */ 259a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauertypedef uchar block; 260a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 261e70ddf3a99e5394faf17d78d0764929ae795b674Tim Peters/* Pool for small blocks. */ 262a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauerstruct pool_header { 263c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou union { block *_padding; 264918c90ce06d6189f8d24d1dba842382a5cb447d4Stefan Krah uint count; } ref; /* number of allocated blocks */ 265c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou block *freeblock; /* pool's free list head */ 266c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou struct pool_header *nextpool; /* next pool of this size class */ 267c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou struct pool_header *prevpool; /* previous pool "" */ 268c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou uint arenaindex; /* index into arenas of base adr */ 269c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou uint szidx; /* block size class index */ 270c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou uint nextoffset; /* bytes to virgin block */ 271c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou uint maxnextoffset; /* largest valid nextoffset */ 272a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer}; 273a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 274a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauertypedef struct pool_header *poolp; 275a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 276cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters/* Record keeping for arenas. */ 277cf79aace07a57d480605f4a5aa8b9ca68567792eTim Petersstruct arena_object { 278c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* The address of the arena, as returned by malloc. Note that 0 279c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * will never be returned by a successful malloc, and is used 280c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * here to mark an arena_object that doesn't correspond to an 281c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * allocated arena. 282c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 283c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou uptr address; 284c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 285c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Pool-aligned pointer to the next pool to be carved off. */ 286c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou block* pool_address; 287c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 288c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* The number of available pools in the arena: free pools + never- 289c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * allocated pools. 290c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 291c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou uint nfreepools; 292c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 293c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* The total number of pools in the arena, whether or not available. */ 294c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou uint ntotalpools; 295c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 296c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Singly-linked list of available pools. */ 297c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou struct pool_header* freepools; 298c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 299c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Whenever this arena_object is not associated with an allocated 300c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * arena, the nextarena member is used to link all unassociated 301c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * arena_objects in the singly-linked `unused_arena_objects` list. 302c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * The prevarena member is unused in this case. 303c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * 304c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * When this arena_object is associated with an allocated arena 305c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * with at least one available pool, both members are used in the 306c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * doubly-linked `usable_arenas` list, which is maintained in 307c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * increasing order of `nfreepools` values. 308c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * 309c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * Else this arena_object is associated with an allocated arena 310c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * all of whose pools are in use. `nextarena` and `prevarena` 311c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * are both meaningless in this case. 312c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 313c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou struct arena_object* nextarena; 314c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou struct arena_object* prevarena; 315cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters}; 316cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters 317a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer#undef ROUNDUP 318c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou#define ROUNDUP(x) (((x) + ALIGNMENT_MASK) & ~ALIGNMENT_MASK) 319c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou#define POOL_OVERHEAD ROUNDUP(sizeof(struct pool_header)) 320a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 321c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou#define DUMMY_SIZE_IDX 0xffff /* size class of newly cached pools */ 322a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 323d97a1c008c4a7ae04c55c8de2cdb71a9ea43656aTim Peters/* Round pointer P down to the closest pool-aligned address <= P, as a poolp */ 324e70ddf3a99e5394faf17d78d0764929ae795b674Tim Peters#define POOL_ADDR(P) ((poolp)((uptr)(P) & ~(uptr)POOL_SIZE_MASK)) 325e70ddf3a99e5394faf17d78d0764929ae795b674Tim Peters 32616bcb6b1afc46f2f73e207bc0484f016c51f0fd9Tim Peters/* Return total number of blocks in pool of size index I, as a uint. */ 32716bcb6b1afc46f2f73e207bc0484f016c51f0fd9Tim Peters#define NUMBLOCKS(I) ((uint)(POOL_SIZE - POOL_OVERHEAD) / INDEX2SIZE(I)) 328d97a1c008c4a7ae04c55c8de2cdb71a9ea43656aTim Peters 329a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer/*==========================================================================*/ 330a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 331a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer/* 332a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * This malloc lock 333a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer */ 334d1fedb6ab59547f914a1958804a0658b68e4d6b2Jeremy HyltonSIMPLELOCK_DECL(_malloc_lock) 335c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou#define LOCK() SIMPLELOCK_LOCK(_malloc_lock) 336c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou#define UNLOCK() SIMPLELOCK_UNLOCK(_malloc_lock) 337c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou#define LOCK_INIT() SIMPLELOCK_INIT(_malloc_lock) 338c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou#define LOCK_FINI() SIMPLELOCK_FINI(_malloc_lock) 339a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 340a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer/* 3411e16db6d3b542b5cc146245055be0a04263c4e5eTim Peters * Pool table -- headed, circular, doubly-linked lists of partially used pools. 3421e16db6d3b542b5cc146245055be0a04263c4e5eTim Peters 3431e16db6d3b542b5cc146245055be0a04263c4e5eTim PetersThis is involved. For an index i, usedpools[i+i] is the header for a list of 3441e16db6d3b542b5cc146245055be0a04263c4e5eTim Petersall partially used pools holding small blocks with "size class idx" i. So 3451e16db6d3b542b5cc146245055be0a04263c4e5eTim Petersusedpools[0] corresponds to blocks of size 8, usedpools[2] to blocks of size 3461e16db6d3b542b5cc146245055be0a04263c4e5eTim Peters16, and so on: index 2*i <-> blocks of size (i+1)<<ALIGNMENT_SHIFT. 3471e16db6d3b542b5cc146245055be0a04263c4e5eTim Peters 348cf79aace07a57d480605f4a5aa8b9ca68567792eTim PetersPools are carved off an arena's highwater mark (an arena_object's pool_address 349cf79aace07a57d480605f4a5aa8b9ca68567792eTim Petersmember) as needed. Once carved off, a pool is in one of three states forever 350cf79aace07a57d480605f4a5aa8b9ca68567792eTim Petersafter: 351338e010b45d7bd411e2bbcedcd8ef195be40c2beTim Peters 352338e010b45d7bd411e2bbcedcd8ef195be40c2beTim Petersused == partially used, neither empty nor full 353338e010b45d7bd411e2bbcedcd8ef195be40c2beTim Peters At least one block in the pool is currently allocated, and at least one 354338e010b45d7bd411e2bbcedcd8ef195be40c2beTim Peters block in the pool is not currently allocated (note this implies a pool 355338e010b45d7bd411e2bbcedcd8ef195be40c2beTim Peters has room for at least two blocks). 356338e010b45d7bd411e2bbcedcd8ef195be40c2beTim Peters This is a pool's initial state, as a pool is created only when malloc 357338e010b45d7bd411e2bbcedcd8ef195be40c2beTim Peters needs space. 358338e010b45d7bd411e2bbcedcd8ef195be40c2beTim Peters The pool holds blocks of a fixed size, and is in the circular list headed 359338e010b45d7bd411e2bbcedcd8ef195be40c2beTim Peters at usedpools[i] (see above). It's linked to the other used pools of the 360338e010b45d7bd411e2bbcedcd8ef195be40c2beTim Peters same size class via the pool_header's nextpool and prevpool members. 361338e010b45d7bd411e2bbcedcd8ef195be40c2beTim Peters If all but one block is currently allocated, a malloc can cause a 362338e010b45d7bd411e2bbcedcd8ef195be40c2beTim Peters transition to the full state. If all but one block is not currently 363338e010b45d7bd411e2bbcedcd8ef195be40c2beTim Peters allocated, a free can cause a transition to the empty state. 364338e010b45d7bd411e2bbcedcd8ef195be40c2beTim Peters 365338e010b45d7bd411e2bbcedcd8ef195be40c2beTim Petersfull == all the pool's blocks are currently allocated 366338e010b45d7bd411e2bbcedcd8ef195be40c2beTim Peters On transition to full, a pool is unlinked from its usedpools[] list. 367338e010b45d7bd411e2bbcedcd8ef195be40c2beTim Peters It's not linked to from anything then anymore, and its nextpool and 368338e010b45d7bd411e2bbcedcd8ef195be40c2beTim Peters prevpool members are meaningless until it transitions back to used. 369338e010b45d7bd411e2bbcedcd8ef195be40c2beTim Peters A free of a block in a full pool puts the pool back in the used state. 370338e010b45d7bd411e2bbcedcd8ef195be40c2beTim Peters Then it's linked in at the front of the appropriate usedpools[] list, so 371338e010b45d7bd411e2bbcedcd8ef195be40c2beTim Peters that the next allocation for its size class will reuse the freed block. 372338e010b45d7bd411e2bbcedcd8ef195be40c2beTim Peters 373338e010b45d7bd411e2bbcedcd8ef195be40c2beTim Petersempty == all the pool's blocks are currently available for allocation 374338e010b45d7bd411e2bbcedcd8ef195be40c2beTim Peters On transition to empty, a pool is unlinked from its usedpools[] list, 375cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters and linked to the front of its arena_object's singly-linked freepools list, 376338e010b45d7bd411e2bbcedcd8ef195be40c2beTim Peters via its nextpool member. The prevpool member has no meaning in this case. 377338e010b45d7bd411e2bbcedcd8ef195be40c2beTim Peters Empty pools have no inherent size class: the next time a malloc finds 378338e010b45d7bd411e2bbcedcd8ef195be40c2beTim Peters an empty list in usedpools[], it takes the first pool off of freepools. 379338e010b45d7bd411e2bbcedcd8ef195be40c2beTim Peters If the size class needed happens to be the same as the size class the pool 380e70ddf3a99e5394faf17d78d0764929ae795b674Tim Peters last had, some pool initialization can be skipped. 381338e010b45d7bd411e2bbcedcd8ef195be40c2beTim Peters 382338e010b45d7bd411e2bbcedcd8ef195be40c2beTim Peters 383338e010b45d7bd411e2bbcedcd8ef195be40c2beTim PetersBlock Management 384338e010b45d7bd411e2bbcedcd8ef195be40c2beTim Peters 385338e010b45d7bd411e2bbcedcd8ef195be40c2beTim PetersBlocks within pools are again carved out as needed. pool->freeblock points to 386338e010b45d7bd411e2bbcedcd8ef195be40c2beTim Petersthe start of a singly-linked list of free blocks within the pool. When a 387338e010b45d7bd411e2bbcedcd8ef195be40c2beTim Petersblock is freed, it's inserted at the front of its pool's freeblock list. Note 388338e010b45d7bd411e2bbcedcd8ef195be40c2beTim Petersthat the available blocks in a pool are *not* linked all together when a pool 389e70ddf3a99e5394faf17d78d0764929ae795b674Tim Petersis initialized. Instead only "the first two" (lowest addresses) blocks are 390e70ddf3a99e5394faf17d78d0764929ae795b674Tim Petersset up, returning the first such block, and setting pool->freeblock to a 391e70ddf3a99e5394faf17d78d0764929ae795b674Tim Petersone-block list holding the second such block. This is consistent with that 392e70ddf3a99e5394faf17d78d0764929ae795b674Tim Peterspymalloc strives at all levels (arena, pool, and block) never to touch a piece 393e70ddf3a99e5394faf17d78d0764929ae795b674Tim Petersof memory until it's actually needed. 394e70ddf3a99e5394faf17d78d0764929ae795b674Tim Peters 395e70ddf3a99e5394faf17d78d0764929ae795b674Tim PetersSo long as a pool is in the used state, we're certain there *is* a block 39652aefc8a7b9e9ebda6c1b98a831a273e0b07bf96Tim Petersavailable for allocating, and pool->freeblock is not NULL. If pool->freeblock 39752aefc8a7b9e9ebda6c1b98a831a273e0b07bf96Tim Peterspoints to the end of the free list before we've carved the entire pool into 39852aefc8a7b9e9ebda6c1b98a831a273e0b07bf96Tim Petersblocks, that means we simply haven't yet gotten to one of the higher-address 39952aefc8a7b9e9ebda6c1b98a831a273e0b07bf96Tim Petersblocks. The offset from the pool_header to the start of "the next" virgin 40052aefc8a7b9e9ebda6c1b98a831a273e0b07bf96Tim Petersblock is stored in the pool_header nextoffset member, and the largest value 40152aefc8a7b9e9ebda6c1b98a831a273e0b07bf96Tim Petersof nextoffset that makes sense is stored in the maxnextoffset member when a 40252aefc8a7b9e9ebda6c1b98a831a273e0b07bf96Tim Peterspool is initialized. All the blocks in a pool have been passed out at least 40352aefc8a7b9e9ebda6c1b98a831a273e0b07bf96Tim Petersonce when and only when nextoffset > maxnextoffset. 404338e010b45d7bd411e2bbcedcd8ef195be40c2beTim Peters 4051e16db6d3b542b5cc146245055be0a04263c4e5eTim Peters 4061e16db6d3b542b5cc146245055be0a04263c4e5eTim PetersMajor obscurity: While the usedpools vector is declared to have poolp 4071e16db6d3b542b5cc146245055be0a04263c4e5eTim Petersentries, it doesn't really. It really contains two pointers per (conceptual) 4081e16db6d3b542b5cc146245055be0a04263c4e5eTim Peterspoolp entry, the nextpool and prevpool members of a pool_header. The 4091e16db6d3b542b5cc146245055be0a04263c4e5eTim Petersexcruciating initialization code below fools C so that 4101e16db6d3b542b5cc146245055be0a04263c4e5eTim Peters 4111e16db6d3b542b5cc146245055be0a04263c4e5eTim Peters usedpool[i+i] 4121e16db6d3b542b5cc146245055be0a04263c4e5eTim Peters 4131e16db6d3b542b5cc146245055be0a04263c4e5eTim Peters"acts like" a genuine poolp, but only so long as you only reference its 4141e16db6d3b542b5cc146245055be0a04263c4e5eTim Petersnextpool and prevpool members. The "- 2*sizeof(block *)" gibberish is 4151e16db6d3b542b5cc146245055be0a04263c4e5eTim Peterscompensating for that a pool_header's nextpool and prevpool members 4161e16db6d3b542b5cc146245055be0a04263c4e5eTim Petersimmediately follow a pool_header's first two members: 4171e16db6d3b542b5cc146245055be0a04263c4e5eTim Peters 418c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou union { block *_padding; 419918c90ce06d6189f8d24d1dba842382a5cb447d4Stefan Krah uint count; } ref; 420c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou block *freeblock; 4211e16db6d3b542b5cc146245055be0a04263c4e5eTim Peters 4221e16db6d3b542b5cc146245055be0a04263c4e5eTim Peterseach of which consume sizeof(block *) bytes. So what usedpools[i+i] really 4231e16db6d3b542b5cc146245055be0a04263c4e5eTim Peterscontains is a fudged-up pointer p such that *if* C believes it's a poolp 4241e16db6d3b542b5cc146245055be0a04263c4e5eTim Peterspointer, then p->nextpool and p->prevpool are both p (meaning that the headed 4251e16db6d3b542b5cc146245055be0a04263c4e5eTim Peterscircular list is empty). 4261e16db6d3b542b5cc146245055be0a04263c4e5eTim Peters 4271e16db6d3b542b5cc146245055be0a04263c4e5eTim PetersIt's unclear why the usedpools setup is so convoluted. It could be to 4281e16db6d3b542b5cc146245055be0a04263c4e5eTim Petersminimize the amount of cache required to hold this heavily-referenced table 4291e16db6d3b542b5cc146245055be0a04263c4e5eTim Peters(which only *needs* the two interpool pointer members of a pool_header). OTOH, 4301e16db6d3b542b5cc146245055be0a04263c4e5eTim Petersreferencing code has to remember to "double the index" and doing so isn't 4311e16db6d3b542b5cc146245055be0a04263c4e5eTim Petersfree, usedpools[0] isn't a strictly legal pointer, and we're crucially relying 4321e16db6d3b542b5cc146245055be0a04263c4e5eTim Peterson that C doesn't insert any padding anywhere in a pool_header at or before 4331e16db6d3b542b5cc146245055be0a04263c4e5eTim Petersthe prevpool member. 4341e16db6d3b542b5cc146245055be0a04263c4e5eTim Peters**************************************************************************** */ 4351e16db6d3b542b5cc146245055be0a04263c4e5eTim Peters 436c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou#define PTA(x) ((poolp )((uchar *)&(usedpools[2*(x)]) - 2*sizeof(block *))) 437c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou#define PT(x) PTA(x), PTA(x) 438a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 439a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauerstatic poolp usedpools[2 * ((NB_SMALL_SIZE_CLASSES + 7) / 8) * 8] = { 440c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou PT(0), PT(1), PT(2), PT(3), PT(4), PT(5), PT(6), PT(7) 441a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer#if NB_SMALL_SIZE_CLASSES > 8 442c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou , PT(8), PT(9), PT(10), PT(11), PT(12), PT(13), PT(14), PT(15) 443a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer#if NB_SMALL_SIZE_CLASSES > 16 444c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou , PT(16), PT(17), PT(18), PT(19), PT(20), PT(21), PT(22), PT(23) 445a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer#if NB_SMALL_SIZE_CLASSES > 24 446c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou , PT(24), PT(25), PT(26), PT(27), PT(28), PT(29), PT(30), PT(31) 447a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer#if NB_SMALL_SIZE_CLASSES > 32 448c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou , PT(32), PT(33), PT(34), PT(35), PT(36), PT(37), PT(38), PT(39) 449a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer#if NB_SMALL_SIZE_CLASSES > 40 450c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou , PT(40), PT(41), PT(42), PT(43), PT(44), PT(45), PT(46), PT(47) 451a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer#if NB_SMALL_SIZE_CLASSES > 48 452c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou , PT(48), PT(49), PT(50), PT(51), PT(52), PT(53), PT(54), PT(55) 453a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer#if NB_SMALL_SIZE_CLASSES > 56 454c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou , PT(56), PT(57), PT(58), PT(59), PT(60), PT(61), PT(62), PT(63) 455d16e01cf75a2663c74c2e36beda6397546a8ae52Benjamin Peterson#if NB_SMALL_SIZE_CLASSES > 64 456d16e01cf75a2663c74c2e36beda6397546a8ae52Benjamin Peterson#error "NB_SMALL_SIZE_CLASSES should be less than 64" 457d16e01cf75a2663c74c2e36beda6397546a8ae52Benjamin Peterson#endif /* NB_SMALL_SIZE_CLASSES > 64 */ 458a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer#endif /* NB_SMALL_SIZE_CLASSES > 56 */ 459a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer#endif /* NB_SMALL_SIZE_CLASSES > 48 */ 460a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer#endif /* NB_SMALL_SIZE_CLASSES > 40 */ 461a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer#endif /* NB_SMALL_SIZE_CLASSES > 32 */ 462a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer#endif /* NB_SMALL_SIZE_CLASSES > 24 */ 463a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer#endif /* NB_SMALL_SIZE_CLASSES > 16 */ 464a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer#endif /* NB_SMALL_SIZE_CLASSES > 8 */ 465a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer}; 466a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 467cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters/*========================================================================== 468cf79aace07a57d480605f4a5aa8b9ca68567792eTim PetersArena management. 469cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters 470cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters`arenas` is a vector of arena_objects. It contains maxarenas entries, some of 471cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peterswhich may not be currently used (== they're arena_objects that aren't 472cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peterscurrently associated with an allocated arena). Note that arenas proper are 473cf79aace07a57d480605f4a5aa8b9ca68567792eTim Petersseparately malloc'ed. 474cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters 475cf79aace07a57d480605f4a5aa8b9ca68567792eTim PetersPrior to Python 2.5, arenas were never free()'ed. Starting with Python 2.5, 476cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peterswe do try to free() arenas, and use some mild heuristic strategies to increase 477cf79aace07a57d480605f4a5aa8b9ca68567792eTim Petersthe likelihood that arenas eventually can be freed. 478cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters 479cf79aace07a57d480605f4a5aa8b9ca68567792eTim Petersunused_arena_objects 480cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters 481cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters This is a singly-linked list of the arena_objects that are currently not 482cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters being used (no arena is associated with them). Objects are taken off the 483cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters head of the list in new_arena(), and are pushed on the head of the list in 484cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters PyObject_Free() when the arena is empty. Key invariant: an arena_object 485cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters is on this list if and only if its .address member is 0. 486cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters 487cf79aace07a57d480605f4a5aa8b9ca68567792eTim Petersusable_arenas 488cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters 489cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters This is a doubly-linked list of the arena_objects associated with arenas 490cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters that have pools available. These pools are either waiting to be reused, 491cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters or have not been used before. The list is sorted to have the most- 492cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters allocated arenas first (ascending order based on the nfreepools member). 493cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters This means that the next allocation will come from a heavily used arena, 494cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters which gives the nearly empty arenas a chance to be returned to the system. 495cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters In my unscientific tests this dramatically improved the number of arenas 496cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters that could be freed. 497cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters 498cf79aace07a57d480605f4a5aa8b9ca68567792eTim PetersNote that an arena_object associated with an arena all of whose pools are 499cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peterscurrently in use isn't on either list. 500cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters*/ 501cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters 502cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters/* Array of objects used to track chunks of memory (arenas). */ 503cf79aace07a57d480605f4a5aa8b9ca68567792eTim Petersstatic struct arena_object* arenas = NULL; 504cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters/* Number of slots currently allocated in the `arenas` vector. */ 505cf79aace07a57d480605f4a5aa8b9ca68567792eTim Petersstatic uint maxarenas = 0; 506cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters 507cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters/* The head of the singly-linked, NULL-terminated list of available 508cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters * arena_objects. 509a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer */ 510cf79aace07a57d480605f4a5aa8b9ca68567792eTim Petersstatic struct arena_object* unused_arena_objects = NULL; 511a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 512cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters/* The head of the doubly-linked, NULL-terminated at each end, list of 513cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters * arena_objects associated with arenas that have pools available. 514cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters */ 515cf79aace07a57d480605f4a5aa8b9ca68567792eTim Petersstatic struct arena_object* usable_arenas = NULL; 516d97a1c008c4a7ae04c55c8de2cdb71a9ea43656aTim Peters 517cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters/* How many arena_objects do we initially allocate? 518cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters * 16 = can allocate 16 arenas = 16 * ARENA_SIZE = 4MB before growing the 519cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters * `arenas` vector. 520a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer */ 521cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters#define INITIAL_ARENA_OBJECTS 16 522a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 523cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters/* Number of arenas allocated that haven't been free()'d. */ 5249ea89d2a1972a527bee508c3fb8cd42a86908da1Tim Petersstatic size_t narenas_currently_allocated = 0; 525d97a1c008c4a7ae04c55c8de2cdb71a9ea43656aTim Peters 526cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters#ifdef PYMALLOC_DEBUG 527cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters/* Total number of times malloc() called to allocate an arena. */ 5289ea89d2a1972a527bee508c3fb8cd42a86908da1Tim Petersstatic size_t ntimes_arena_allocated = 0; 529cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters/* High water mark (max value ever seen) for narenas_currently_allocated. */ 5309ea89d2a1972a527bee508c3fb8cd42a86908da1Tim Petersstatic size_t narenas_highwater = 0; 531cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters#endif 532d97a1c008c4a7ae04c55c8de2cdb71a9ea43656aTim Peters 533cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters/* Allocate a new arena. If we run out of memory, return NULL. Else 534cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters * allocate a new arena, and return the address of an arena_object 535cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters * describing the new arena. It's expected that the caller will set 536cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters * `usable_arenas` to the return value. 537d97a1c008c4a7ae04c55c8de2cdb71a9ea43656aTim Peters */ 538cf79aace07a57d480605f4a5aa8b9ca68567792eTim Petersstatic struct arena_object* 539d97a1c008c4a7ae04c55c8de2cdb71a9ea43656aTim Petersnew_arena(void) 540d97a1c008c4a7ae04c55c8de2cdb71a9ea43656aTim Peters{ 541c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou struct arena_object* arenaobj; 542c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou uint excess; /* number of bytes above pool alignment */ 543d97a1c008c4a7ae04c55c8de2cdb71a9ea43656aTim Peters 5440e871188e8cd9a4e41be7c734e250bfce2d92d56Tim Peters#ifdef PYMALLOC_DEBUG 545c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (Py_GETENV("PYTHONMALLOCSTATS")) 546c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou _PyObject_DebugMallocStats(); 5470e871188e8cd9a4e41be7c734e250bfce2d92d56Tim Peters#endif 548c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (unused_arena_objects == NULL) { 549c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou uint i; 550c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou uint numarenas; 551c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou size_t nbytes; 552c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 553c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Double the number of arena objects on each allocation. 554c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * Note that it's possible for `numarenas` to overflow. 555c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 556c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou numarenas = maxarenas ? maxarenas << 1 : INITIAL_ARENA_OBJECTS; 557c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (numarenas <= maxarenas) 558c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return NULL; /* overflow */ 5599fa5a2828c8007dfb678b883d65aecac93e995e4Martin v. Löwis#if SIZEOF_SIZE_T <= SIZEOF_INT 560c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (numarenas > PY_SIZE_MAX / sizeof(*arenas)) 561c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return NULL; /* overflow */ 5629fa5a2828c8007dfb678b883d65aecac93e995e4Martin v. Löwis#endif 563c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou nbytes = numarenas * sizeof(*arenas); 564c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou arenaobj = (struct arena_object *)realloc(arenas, nbytes); 565c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (arenaobj == NULL) 566c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return NULL; 567c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou arenas = arenaobj; 568c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 569c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* We might need to fix pointers that were copied. However, 570c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * new_arena only gets called when all the pages in the 571c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * previous arenas are full. Thus, there are *no* pointers 572c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * into the old array. Thus, we don't have to worry about 573c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * invalid pointers. Just to be sure, some asserts: 574c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 575c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(usable_arenas == NULL); 576c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(unused_arena_objects == NULL); 577c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 578c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Put the new arenas on the unused_arena_objects list. */ 579c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou for (i = maxarenas; i < numarenas; ++i) { 580c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou arenas[i].address = 0; /* mark as unassociated */ 581c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou arenas[i].nextarena = i < numarenas - 1 ? 582c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou &arenas[i+1] : NULL; 583c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 584c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 585c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Update globals. */ 586c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou unused_arena_objects = &arenas[maxarenas]; 587c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou maxarenas = numarenas; 588c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 589c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 590c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Take the next available arena object off the head of the list. */ 591c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(unused_arena_objects != NULL); 592c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou arenaobj = unused_arena_objects; 593c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou unused_arena_objects = arenaobj->nextarena; 594c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(arenaobj->address == 0); 595d16e01cf75a2663c74c2e36beda6397546a8ae52Benjamin Peterson#ifdef ARENAS_USE_MMAP 596d16e01cf75a2663c74c2e36beda6397546a8ae52Benjamin Peterson arenaobj->address = (uptr)mmap(NULL, ARENA_SIZE, PROT_READ|PROT_WRITE, 597d16e01cf75a2663c74c2e36beda6397546a8ae52Benjamin Peterson MAP_PRIVATE|MAP_ANONYMOUS, -1, 0); 598d16e01cf75a2663c74c2e36beda6397546a8ae52Benjamin Peterson#else 599c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou arenaobj->address = (uptr)malloc(ARENA_SIZE); 600d16e01cf75a2663c74c2e36beda6397546a8ae52Benjamin Peterson#endif 601c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (arenaobj->address == 0) { 602c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* The allocation failed: return NULL after putting the 603c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * arenaobj back. 604c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 605c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou arenaobj->nextarena = unused_arena_objects; 606c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou unused_arena_objects = arenaobj; 607c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return NULL; 608c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 609c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 610c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou ++narenas_currently_allocated; 611cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters#ifdef PYMALLOC_DEBUG 612c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou ++ntimes_arena_allocated; 613c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (narenas_currently_allocated > narenas_highwater) 614c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou narenas_highwater = narenas_currently_allocated; 615cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters#endif 616c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou arenaobj->freepools = NULL; 617c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* pool_address <- first pool-aligned address in the arena 618c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou nfreepools <- number of whole pools that fit after alignment */ 619c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou arenaobj->pool_address = (block*)arenaobj->address; 620c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou arenaobj->nfreepools = ARENA_SIZE / POOL_SIZE; 621c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(POOL_SIZE * arenaobj->nfreepools == ARENA_SIZE); 622c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou excess = (uint)(arenaobj->address & POOL_SIZE_MASK); 623c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (excess != 0) { 624c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou --arenaobj->nfreepools; 625c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou arenaobj->pool_address += POOL_SIZE - excess; 626c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 627c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou arenaobj->ntotalpools = arenaobj->nfreepools; 628c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 629c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return arenaobj; 630d97a1c008c4a7ae04c55c8de2cdb71a9ea43656aTim Peters} 631d97a1c008c4a7ae04c55c8de2cdb71a9ea43656aTim Peters 632cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters/* 633cf79aace07a57d480605f4a5aa8b9ca68567792eTim PetersPy_ADDRESS_IN_RANGE(P, POOL) 634cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters 635cf79aace07a57d480605f4a5aa8b9ca68567792eTim PetersReturn true if and only if P is an address that was allocated by pymalloc. 636cf79aace07a57d480605f4a5aa8b9ca68567792eTim PetersPOOL must be the pool address associated with P, i.e., POOL = POOL_ADDR(P) 637cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters(the caller is asked to compute this because the macro expands POOL more than 638cf79aace07a57d480605f4a5aa8b9ca68567792eTim Petersonce, and for efficiency it's best for the caller to assign POOL_ADDR(P) to a 639cf79aace07a57d480605f4a5aa8b9ca68567792eTim Petersvariable and pass the latter to the macro; because Py_ADDRESS_IN_RANGE is 640cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peterscalled on every alloc/realloc/free, micro-efficiency is important here). 641cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters 642cf79aace07a57d480605f4a5aa8b9ca68567792eTim PetersTricky: Let B be the arena base address associated with the pool, B = 643cf79aace07a57d480605f4a5aa8b9ca68567792eTim Petersarenas[(POOL)->arenaindex].address. Then P belongs to the arena if and only if 644cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters 645c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou B <= P < B + ARENA_SIZE 646cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters 647cf79aace07a57d480605f4a5aa8b9ca68567792eTim PetersSubtracting B throughout, this is true iff 648cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters 649c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 0 <= P-B < ARENA_SIZE 650cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters 651cf79aace07a57d480605f4a5aa8b9ca68567792eTim PetersBy using unsigned arithmetic, the "0 <=" half of the test can be skipped. 652cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters 653cf79aace07a57d480605f4a5aa8b9ca68567792eTim PetersObscure: A PyMem "free memory" function can call the pymalloc free or realloc 654cf79aace07a57d480605f4a5aa8b9ca68567792eTim Petersbefore the first arena has been allocated. `arenas` is still NULL in that 655cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peterscase. We're relying on that maxarenas is also 0 in that case, so that 656cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters(POOL)->arenaindex < maxarenas must be false, saving us from trying to index 657cf79aace07a57d480605f4a5aa8b9ca68567792eTim Petersinto a NULL arenas. 658cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters 659cf79aace07a57d480605f4a5aa8b9ca68567792eTim PetersDetails: given P and POOL, the arena_object corresponding to P is AO = 660cf79aace07a57d480605f4a5aa8b9ca68567792eTim Petersarenas[(POOL)->arenaindex]. Suppose obmalloc controls P. Then (barring wild 661cf79aace07a57d480605f4a5aa8b9ca68567792eTim Petersstores, etc), POOL is the correct address of P's pool, AO.address is the 662cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peterscorrect base address of the pool's arena, and P must be within ARENA_SIZE of 663cf79aace07a57d480605f4a5aa8b9ca68567792eTim PetersAO.address. In addition, AO.address is not 0 (no arena can start at address 0 664cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters(NULL)). Therefore Py_ADDRESS_IN_RANGE correctly reports that obmalloc 665cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peterscontrols P. 666cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters 667cf79aace07a57d480605f4a5aa8b9ca68567792eTim PetersNow suppose obmalloc does not control P (e.g., P was obtained via a direct 668cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peterscall to the system malloc() or realloc()). (POOL)->arenaindex may be anything 669cf79aace07a57d480605f4a5aa8b9ca68567792eTim Petersin this case -- it may even be uninitialized trash. If the trash arenaindex 670cf79aace07a57d480605f4a5aa8b9ca68567792eTim Petersis >= maxarenas, the macro correctly concludes at once that obmalloc doesn't 671cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peterscontrol P. 672cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters 673cf79aace07a57d480605f4a5aa8b9ca68567792eTim PetersElse arenaindex is < maxarena, and AO is read up. If AO corresponds to an 674cf79aace07a57d480605f4a5aa8b9ca68567792eTim Petersallocated arena, obmalloc controls all the memory in slice AO.address : 675cf79aace07a57d480605f4a5aa8b9ca68567792eTim PetersAO.address+ARENA_SIZE. By case assumption, P is not controlled by obmalloc, 676cf79aace07a57d480605f4a5aa8b9ca68567792eTim Petersso P doesn't lie in that slice, so the macro correctly reports that P is not 677cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peterscontrolled by obmalloc. 678cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters 679cf79aace07a57d480605f4a5aa8b9ca68567792eTim PetersFinally, if P is not controlled by obmalloc and AO corresponds to an unused 680cf79aace07a57d480605f4a5aa8b9ca68567792eTim Petersarena_object (one not currently associated with an allocated arena), 681cf79aace07a57d480605f4a5aa8b9ca68567792eTim PetersAO.address is 0, and the second test in the macro reduces to: 682cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters 683c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou P < ARENA_SIZE 684cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters 685cf79aace07a57d480605f4a5aa8b9ca68567792eTim PetersIf P >= ARENA_SIZE (extremely likely), the macro again correctly concludes 686cf79aace07a57d480605f4a5aa8b9ca68567792eTim Petersthat P is not controlled by obmalloc. However, if P < ARENA_SIZE, this part 687cf79aace07a57d480605f4a5aa8b9ca68567792eTim Petersof the test still passes, and the third clause (AO.address != 0) is necessary 688cf79aace07a57d480605f4a5aa8b9ca68567792eTim Petersto get the correct result: AO.address is 0 in this case, so the macro 689cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peterscorrectly reports that P is not controlled by obmalloc (despite that P lies in 690cf79aace07a57d480605f4a5aa8b9ca68567792eTim Petersslice AO.address : AO.address + ARENA_SIZE). 691cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters 692cf79aace07a57d480605f4a5aa8b9ca68567792eTim PetersNote: The third (AO.address != 0) clause was added in Python 2.5. Before 693cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters2.5, arenas were never free()'ed, and an arenaindex < maxarena always 694cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peterscorresponded to a currently-allocated arena, so the "P is not controlled by 695cf79aace07a57d480605f4a5aa8b9ca68567792eTim Petersobmalloc, AO corresponds to an unused arena_object, and P < ARENA_SIZE" case 696cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peterswas impossible. 697cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters 698cf79aace07a57d480605f4a5aa8b9ca68567792eTim PetersNote that the logic is excruciating, and reading up possibly uninitialized 699cf79aace07a57d480605f4a5aa8b9ca68567792eTim Petersmemory when P is not controlled by obmalloc (to get at (POOL)->arenaindex) 700cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peterscreates problems for some memory debuggers. The overwhelming advantage is 701cf79aace07a57d480605f4a5aa8b9ca68567792eTim Petersthat this test determines whether an arbitrary address is controlled by 702cf79aace07a57d480605f4a5aa8b9ca68567792eTim Petersobmalloc in a small constant time, independent of the number of arenas 703cf79aace07a57d480605f4a5aa8b9ca68567792eTim Petersobmalloc controls. Since this test is needed at every entry point, it's 704cf79aace07a57d480605f4a5aa8b9ca68567792eTim Petersextremely desirable that it be this fast. 7055a72e76b6938941547dd25f9198db7d17fa36960Antoine Pitrou 7065a72e76b6938941547dd25f9198db7d17fa36960Antoine PitrouSince Py_ADDRESS_IN_RANGE may be reading from memory which was not allocated 7075a72e76b6938941547dd25f9198db7d17fa36960Antoine Pitrouby Python, it is important that (POOL)->arenaindex is read only once, as 7085a72e76b6938941547dd25f9198db7d17fa36960Antoine Pitrouanother thread may be concurrently modifying the value without holding the 7095a72e76b6938941547dd25f9198db7d17fa36960Antoine PitrouGIL. To accomplish this, the arenaindex_temp variable is used to store 7105a72e76b6938941547dd25f9198db7d17fa36960Antoine Pitrou(POOL)->arenaindex for the duration of the Py_ADDRESS_IN_RANGE macro's 7115a72e76b6938941547dd25f9198db7d17fa36960Antoine Pitrouexecution. The caller of the macro is responsible for declaring this 7125a72e76b6938941547dd25f9198db7d17fa36960Antoine Pitrouvariable. 713cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters*/ 714c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou#define Py_ADDRESS_IN_RANGE(P, POOL) \ 7155a72e76b6938941547dd25f9198db7d17fa36960Antoine Pitrou ((arenaindex_temp = (POOL)->arenaindex) < maxarenas && \ 7165a72e76b6938941547dd25f9198db7d17fa36960Antoine Pitrou (uptr)(P) - arenas[arenaindex_temp].address < (uptr)ARENA_SIZE && \ 7175a72e76b6938941547dd25f9198db7d17fa36960Antoine Pitrou arenas[arenaindex_temp].address != 0) 718cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters 7197eb3c9196da5be52a670d6d8dd24939a3c27b594Neal Norwitz 7207eb3c9196da5be52a670d6d8dd24939a3c27b594Neal Norwitz/* This is only useful when running memory debuggers such as 7217eb3c9196da5be52a670d6d8dd24939a3c27b594Neal Norwitz * Purify or Valgrind. Uncomment to use. 7227eb3c9196da5be52a670d6d8dd24939a3c27b594Neal Norwitz * 7236819210b9e4e5719a6f7f9c1725f8fa70a8936f6Martin v. Löwis#define Py_USING_MEMORY_DEBUGGER 724e86b07cc9ad51baa4f5a2854f8a03e7d1b77b817Martin v. Löwis */ 7257eb3c9196da5be52a670d6d8dd24939a3c27b594Neal Norwitz 7267eb3c9196da5be52a670d6d8dd24939a3c27b594Neal Norwitz#ifdef Py_USING_MEMORY_DEBUGGER 7277eb3c9196da5be52a670d6d8dd24939a3c27b594Neal Norwitz 7287eb3c9196da5be52a670d6d8dd24939a3c27b594Neal Norwitz/* Py_ADDRESS_IN_RANGE may access uninitialized memory by design 7297eb3c9196da5be52a670d6d8dd24939a3c27b594Neal Norwitz * This leads to thousands of spurious warnings when using 7307eb3c9196da5be52a670d6d8dd24939a3c27b594Neal Norwitz * Purify or Valgrind. By making a function, we can easily 7317eb3c9196da5be52a670d6d8dd24939a3c27b594Neal Norwitz * suppress the uninitialized memory reads in this one function. 7327eb3c9196da5be52a670d6d8dd24939a3c27b594Neal Norwitz * So we won't ignore real errors elsewhere. 7337eb3c9196da5be52a670d6d8dd24939a3c27b594Neal Norwitz * 7347eb3c9196da5be52a670d6d8dd24939a3c27b594Neal Norwitz * Disable the macro and use a function. 7357eb3c9196da5be52a670d6d8dd24939a3c27b594Neal Norwitz */ 7367eb3c9196da5be52a670d6d8dd24939a3c27b594Neal Norwitz 7377eb3c9196da5be52a670d6d8dd24939a3c27b594Neal Norwitz#undef Py_ADDRESS_IN_RANGE 7387eb3c9196da5be52a670d6d8dd24939a3c27b594Neal Norwitz 739ab772274700baf17e708e8c8d82c78efbaa038cdNeal Norwitz#if defined(__GNUC__) && ((__GNUC__ == 3) && (__GNUC_MINOR__ >= 1) || \ 740918c90ce06d6189f8d24d1dba842382a5cb447d4Stefan Krah (__GNUC__ >= 4)) 741e5e5aa4ea693d18bfc8a5bb352a75e9154da6af9Neal Norwitz#define Py_NO_INLINE __attribute__((__noinline__)) 742e5e5aa4ea693d18bfc8a5bb352a75e9154da6af9Neal Norwitz#else 743e5e5aa4ea693d18bfc8a5bb352a75e9154da6af9Neal Norwitz#define Py_NO_INLINE 744e5e5aa4ea693d18bfc8a5bb352a75e9154da6af9Neal Norwitz#endif 745e5e5aa4ea693d18bfc8a5bb352a75e9154da6af9Neal Norwitz 746e5e5aa4ea693d18bfc8a5bb352a75e9154da6af9Neal Norwitz/* Don't make static, to try to ensure this isn't inlined. */ 747e5e5aa4ea693d18bfc8a5bb352a75e9154da6af9Neal Norwitzint Py_ADDRESS_IN_RANGE(void *P, poolp pool) Py_NO_INLINE; 748e5e5aa4ea693d18bfc8a5bb352a75e9154da6af9Neal Norwitz#undef Py_NO_INLINE 7497eb3c9196da5be52a670d6d8dd24939a3c27b594Neal Norwitz#endif 750338e010b45d7bd411e2bbcedcd8ef195be40c2beTim Peters 751a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer/*==========================================================================*/ 752a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 75384c1b974675b9252e1f5764a399ff9455fbf73e0Tim Peters/* malloc. Note that nbytes==0 tries to return a non-NULL pointer, distinct 75484c1b974675b9252e1f5764a399ff9455fbf73e0Tim Peters * from all other currently live pointers. This may not be possible. 75584c1b974675b9252e1f5764a399ff9455fbf73e0Tim Peters */ 756a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 757a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer/* 758a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * The basic blocks are ordered by decreasing execution frequency, 759a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * which minimizes the number of jumps in the most common cases, 760a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * improves branching prediction and instruction scheduling (small 761a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * block allocations typically result in a couple of instructions). 762a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer * Unless the optimizer reorders everything, being too smart... 763a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer */ 764a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 765d2560cd37c8d38c9eb79bcfce9d780b0753a3cb5Neil Schemenauer#undef PyObject_Malloc 766a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauervoid * 767d2560cd37c8d38c9eb79bcfce9d780b0753a3cb5Neil SchemenauerPyObject_Malloc(size_t nbytes) 768a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer{ 769c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou block *bp; 770c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou poolp pool; 771c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou poolp next; 772c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou uint size; 773a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 77491c12ebc3dc6472ea486ab5e4aa38139283d48adBenjamin Peterson#ifdef WITH_VALGRIND 775c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (UNLIKELY(running_on_valgrind == -1)) 776c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou running_on_valgrind = RUNNING_ON_VALGRIND; 777c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (UNLIKELY(running_on_valgrind)) 778c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou goto redirect; 77991c12ebc3dc6472ea486ab5e4aa38139283d48adBenjamin Peterson#endif 78091c12ebc3dc6472ea486ab5e4aa38139283d48adBenjamin Peterson 781c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* 782c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * Limit ourselves to PY_SSIZE_T_MAX bytes to prevent security holes. 783c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * Most python internals blindly use a signed Py_ssize_t to track 784c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * things without checking for overflows or negatives. 785c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * As size_t is unsigned, checking for nbytes < 0 is not required. 786c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 787c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (nbytes > PY_SSIZE_T_MAX) 788c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return NULL; 789c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 790c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* 791c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * This implicitly redirects malloc(0). 792c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 793c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if ((nbytes - 1) < SMALL_REQUEST_THRESHOLD) { 794c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou LOCK(); 795c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* 796c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * Most frequent paths first 797c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 798c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou size = (uint)(nbytes - 1) >> ALIGNMENT_SHIFT; 799c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou pool = usedpools[size + size]; 800c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (pool != pool->nextpool) { 801c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* 802c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * There is a used pool for this size class. 803c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * Pick up the head block of its free list. 804c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 805c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou ++pool->ref.count; 806c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou bp = pool->freeblock; 807c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(bp != NULL); 808c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if ((pool->freeblock = *(block **)bp) != NULL) { 809c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou UNLOCK(); 810c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return (void *)bp; 811c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 812c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* 813c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * Reached the end of the free list, try to extend it. 814c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 815c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (pool->nextoffset <= pool->maxnextoffset) { 816c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* There is room for another block. */ 817c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou pool->freeblock = (block*)pool + 818c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou pool->nextoffset; 819c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou pool->nextoffset += INDEX2SIZE(size); 820c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou *(block **)(pool->freeblock) = NULL; 821c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou UNLOCK(); 822c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return (void *)bp; 823c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 824c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Pool is full, unlink from used pools. */ 825c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou next = pool->nextpool; 826c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou pool = pool->prevpool; 827c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou next->prevpool = pool; 828c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou pool->nextpool = next; 829c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou UNLOCK(); 830c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return (void *)bp; 831c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 832c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 833c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* There isn't a pool of the right size class immediately 834c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * available: use a free pool. 835c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 836c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (usable_arenas == NULL) { 837c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* No arena has a free pool: allocate a new arena. */ 838cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters#ifdef WITH_MEMORY_LIMITS 839c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (narenas_currently_allocated >= MAX_ARENAS) { 840c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou UNLOCK(); 841c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou goto redirect; 842c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 843cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters#endif 844c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou usable_arenas = new_arena(); 845c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (usable_arenas == NULL) { 846c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou UNLOCK(); 847c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou goto redirect; 848c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 849c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou usable_arenas->nextarena = 850c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou usable_arenas->prevarena = NULL; 851c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 852c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(usable_arenas->address != 0); 853c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 854c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Try to get a cached free pool. */ 855c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou pool = usable_arenas->freepools; 856c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (pool != NULL) { 857c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Unlink from cached pools. */ 858c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou usable_arenas->freepools = pool->nextpool; 859c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 860c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* This arena already had the smallest nfreepools 861c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * value, so decreasing nfreepools doesn't change 862c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * that, and we don't need to rearrange the 863c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * usable_arenas list. However, if the arena has 864c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * become wholly allocated, we need to remove its 865c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * arena_object from usable_arenas. 866c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 867c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou --usable_arenas->nfreepools; 868c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (usable_arenas->nfreepools == 0) { 869c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Wholly allocated: remove. */ 870c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(usable_arenas->freepools == NULL); 871c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(usable_arenas->nextarena == NULL || 872c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou usable_arenas->nextarena->prevarena == 873c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou usable_arenas); 874c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 875c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou usable_arenas = usable_arenas->nextarena; 876c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (usable_arenas != NULL) { 877c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou usable_arenas->prevarena = NULL; 878c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(usable_arenas->address != 0); 879c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 880c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 881c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou else { 882c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* nfreepools > 0: it must be that freepools 883c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * isn't NULL, or that we haven't yet carved 884c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * off all the arena's pools for the first 885c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * time. 886c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 887c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(usable_arenas->freepools != NULL || 888c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou usable_arenas->pool_address <= 889c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou (block*)usable_arenas->address + 890c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou ARENA_SIZE - POOL_SIZE); 891c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 892c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou init_pool: 893c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Frontlink to used pools. */ 894c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou next = usedpools[size + size]; /* == prev */ 895c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou pool->nextpool = next; 896c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou pool->prevpool = next; 897c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou next->nextpool = pool; 898c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou next->prevpool = pool; 899c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou pool->ref.count = 1; 900c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (pool->szidx == size) { 901c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Luckily, this pool last contained blocks 902c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * of the same size class, so its header 903c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * and free list are already initialized. 904c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 905c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou bp = pool->freeblock; 906c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou pool->freeblock = *(block **)bp; 907c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou UNLOCK(); 908c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return (void *)bp; 909c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 910c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* 911c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * Initialize the pool header, set up the free list to 912c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * contain just the second block, and return the first 913c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * block. 914c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 915c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou pool->szidx = size; 916c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou size = INDEX2SIZE(size); 917c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou bp = (block *)pool + POOL_OVERHEAD; 918c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou pool->nextoffset = POOL_OVERHEAD + (size << 1); 919c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou pool->maxnextoffset = POOL_SIZE - size; 920c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou pool->freeblock = bp + size; 921c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou *(block **)(pool->freeblock) = NULL; 922c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou UNLOCK(); 923c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return (void *)bp; 924c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 925c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 926c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Carve off a new pool. */ 927c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(usable_arenas->nfreepools > 0); 928c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(usable_arenas->freepools == NULL); 929c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou pool = (poolp)usable_arenas->pool_address; 930c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert((block*)pool <= (block*)usable_arenas->address + 931c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou ARENA_SIZE - POOL_SIZE); 932c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou pool->arenaindex = usable_arenas - arenas; 933c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(&arenas[pool->arenaindex] == usable_arenas); 934c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou pool->szidx = DUMMY_SIZE_IDX; 935c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou usable_arenas->pool_address += POOL_SIZE; 936c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou --usable_arenas->nfreepools; 937c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 938c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (usable_arenas->nfreepools == 0) { 939c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(usable_arenas->nextarena == NULL || 940c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou usable_arenas->nextarena->prevarena == 941c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou usable_arenas); 942c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Unlink the arena: it is completely allocated. */ 943c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou usable_arenas = usable_arenas->nextarena; 944c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (usable_arenas != NULL) { 945c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou usable_arenas->prevarena = NULL; 946c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(usable_arenas->address != 0); 947c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 948c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 949c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 950c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou goto init_pool; 951c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 952c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 953c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* The small block allocator ends here. */ 954a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 955d97a1c008c4a7ae04c55c8de2cdb71a9ea43656aTim Petersredirect: 956c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Redirect the original request to the underlying (libc) allocator. 957c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * We jump here on bigger requests, on error in the code above (as a 958c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * last chance to serve the request) or when the max memory limit 959c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * has been reached. 960c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 961c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (nbytes == 0) 962c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou nbytes = 1; 963c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return (void *)malloc(nbytes); 964a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer} 965a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 966a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer/* free */ 967a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 968d2560cd37c8d38c9eb79bcfce9d780b0753a3cb5Neil Schemenauer#undef PyObject_Free 969a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauervoid 970d2560cd37c8d38c9eb79bcfce9d780b0753a3cb5Neil SchemenauerPyObject_Free(void *p) 971a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer{ 972c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou poolp pool; 973c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou block *lastfree; 974c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou poolp next, prev; 975c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou uint size; 9765a72e76b6938941547dd25f9198db7d17fa36960Antoine Pitrou#ifndef Py_USING_MEMORY_DEBUGGER 9775a72e76b6938941547dd25f9198db7d17fa36960Antoine Pitrou uint arenaindex_temp; 9785a72e76b6938941547dd25f9198db7d17fa36960Antoine Pitrou#endif 979a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 980c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (p == NULL) /* free(NULL) has no effect */ 981c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return; 982a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 98391c12ebc3dc6472ea486ab5e4aa38139283d48adBenjamin Peterson#ifdef WITH_VALGRIND 984c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (UNLIKELY(running_on_valgrind > 0)) 985c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou goto redirect; 98691c12ebc3dc6472ea486ab5e4aa38139283d48adBenjamin Peterson#endif 98791c12ebc3dc6472ea486ab5e4aa38139283d48adBenjamin Peterson 988c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou pool = POOL_ADDR(p); 989c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (Py_ADDRESS_IN_RANGE(p, pool)) { 990c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* We allocated this address. */ 991c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou LOCK(); 992c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Link p to the start of the pool's freeblock list. Since 993c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * the pool had at least the p block outstanding, the pool 994c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * wasn't empty (so it's already in a usedpools[] list, or 995c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * was full and is in no list -- it's not in the freeblocks 996c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * list in any case). 997c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 998c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(pool->ref.count > 0); /* else it was empty */ 999c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou *(block **)p = lastfree = pool->freeblock; 1000c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou pool->freeblock = (block *)p; 1001c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (lastfree) { 1002c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou struct arena_object* ao; 1003c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou uint nf; /* ao->nfreepools */ 1004c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1005c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* freeblock wasn't NULL, so the pool wasn't full, 1006c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * and the pool is in a usedpools[] list. 1007c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 1008c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (--pool->ref.count != 0) { 1009c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* pool isn't empty: leave it in usedpools */ 1010c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou UNLOCK(); 1011c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return; 1012c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1013c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Pool is now empty: unlink from usedpools, and 1014c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * link to the front of freepools. This ensures that 1015c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * previously freed pools will be allocated later 1016c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * (being not referenced, they are perhaps paged out). 1017c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 1018c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou next = pool->nextpool; 1019c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou prev = pool->prevpool; 1020c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou next->prevpool = prev; 1021c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou prev->nextpool = next; 1022c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1023c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Link the pool to freepools. This is a singly-linked 1024c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * list, and pool->prevpool isn't used there. 1025c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 1026c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou ao = &arenas[pool->arenaindex]; 1027c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou pool->nextpool = ao->freepools; 1028c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou ao->freepools = pool; 1029c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou nf = ++ao->nfreepools; 1030c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1031c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* All the rest is arena management. We just freed 1032c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * a pool, and there are 4 cases for arena mgmt: 1033c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * 1. If all the pools are free, return the arena to 1034c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * the system free(). 1035c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * 2. If this is the only free pool in the arena, 1036c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * add the arena back to the `usable_arenas` list. 1037c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * 3. If the "next" arena has a smaller count of free 1038c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * pools, we have to "slide this arena right" to 1039c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * restore that usable_arenas is sorted in order of 1040c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * nfreepools. 1041c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * 4. Else there's nothing more to do. 1042c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 1043c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (nf == ao->ntotalpools) { 1044c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Case 1. First unlink ao from usable_arenas. 1045c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 1046c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(ao->prevarena == NULL || 1047c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou ao->prevarena->address != 0); 1048c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(ao ->nextarena == NULL || 1049c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou ao->nextarena->address != 0); 1050c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1051c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Fix the pointer in the prevarena, or the 1052c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * usable_arenas pointer. 1053c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 1054c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (ao->prevarena == NULL) { 1055c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou usable_arenas = ao->nextarena; 1056c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(usable_arenas == NULL || 1057c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou usable_arenas->address != 0); 1058c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1059c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou else { 1060c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(ao->prevarena->nextarena == ao); 1061c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou ao->prevarena->nextarena = 1062c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou ao->nextarena; 1063c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1064c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Fix the pointer in the nextarena. */ 1065c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (ao->nextarena != NULL) { 1066c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(ao->nextarena->prevarena == ao); 1067c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou ao->nextarena->prevarena = 1068c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou ao->prevarena; 1069c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1070c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Record that this arena_object slot is 1071c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * available to be reused. 1072c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 1073c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou ao->nextarena = unused_arena_objects; 1074c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou unused_arena_objects = ao; 1075c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1076c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Free the entire arena. */ 1077d16e01cf75a2663c74c2e36beda6397546a8ae52Benjamin Peterson#ifdef ARENAS_USE_MMAP 1078d16e01cf75a2663c74c2e36beda6397546a8ae52Benjamin Peterson munmap((void *)ao->address, ARENA_SIZE); 1079d16e01cf75a2663c74c2e36beda6397546a8ae52Benjamin Peterson#else 1080c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou free((void *)ao->address); 1081d16e01cf75a2663c74c2e36beda6397546a8ae52Benjamin Peterson#endif 1082c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou ao->address = 0; /* mark unassociated */ 1083c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou --narenas_currently_allocated; 1084c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1085c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou UNLOCK(); 1086c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return; 1087c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1088c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (nf == 1) { 1089c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Case 2. Put ao at the head of 1090c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * usable_arenas. Note that because 1091c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * ao->nfreepools was 0 before, ao isn't 1092c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * currently on the usable_arenas list. 1093c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 1094c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou ao->nextarena = usable_arenas; 1095c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou ao->prevarena = NULL; 1096c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (usable_arenas) 1097c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou usable_arenas->prevarena = ao; 1098c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou usable_arenas = ao; 1099c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(usable_arenas->address != 0); 1100c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1101c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou UNLOCK(); 1102c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return; 1103c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1104c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* If this arena is now out of order, we need to keep 1105c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * the list sorted. The list is kept sorted so that 1106c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * the "most full" arenas are used first, which allows 1107c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * the nearly empty arenas to be completely freed. In 1108c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * a few un-scientific tests, it seems like this 1109c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * approach allowed a lot more memory to be freed. 1110c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 1111c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (ao->nextarena == NULL || 1112c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou nf <= ao->nextarena->nfreepools) { 1113c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Case 4. Nothing to do. */ 1114c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou UNLOCK(); 1115c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return; 1116c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1117c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Case 3: We have to move the arena towards the end 1118c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * of the list, because it has more free pools than 1119c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * the arena to its right. 1120c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * First unlink ao from usable_arenas. 1121c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 1122c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (ao->prevarena != NULL) { 1123c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* ao isn't at the head of the list */ 1124c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(ao->prevarena->nextarena == ao); 1125c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou ao->prevarena->nextarena = ao->nextarena; 1126c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1127c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou else { 1128c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* ao is at the head of the list */ 1129c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(usable_arenas == ao); 1130c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou usable_arenas = ao->nextarena; 1131c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1132c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou ao->nextarena->prevarena = ao->prevarena; 1133c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1134c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Locate the new insertion point by iterating over 1135c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * the list, using our nextarena pointer. 1136c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 1137c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou while (ao->nextarena != NULL && 1138c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou nf > ao->nextarena->nfreepools) { 1139c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou ao->prevarena = ao->nextarena; 1140c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou ao->nextarena = ao->nextarena->nextarena; 1141c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1142c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1143c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Insert ao at this point. */ 1144c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(ao->nextarena == NULL || 1145c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou ao->prevarena == ao->nextarena->prevarena); 1146c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(ao->prevarena->nextarena == ao->nextarena); 1147c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1148c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou ao->prevarena->nextarena = ao; 1149c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (ao->nextarena != NULL) 1150c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou ao->nextarena->prevarena = ao; 1151c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1152c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Verify that the swaps worked. */ 1153c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(ao->nextarena == NULL || 1154c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou nf <= ao->nextarena->nfreepools); 1155c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(ao->prevarena == NULL || 1156c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou nf > ao->prevarena->nfreepools); 1157c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(ao->nextarena == NULL || 1158c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou ao->nextarena->prevarena == ao); 1159c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert((usable_arenas == ao && 1160c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou ao->prevarena == NULL) || 1161c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou ao->prevarena->nextarena == ao); 1162c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1163c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou UNLOCK(); 1164c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return; 1165c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1166c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Pool was full, so doesn't currently live in any list: 1167c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * link it to the front of the appropriate usedpools[] list. 1168c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * This mimics LRU pool usage for new allocations and 1169c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * targets optimal filling when several pools contain 1170c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * blocks of the same size class. 1171c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 1172c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou --pool->ref.count; 1173c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(pool->ref.count > 0); /* else the pool is empty */ 1174c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou size = pool->szidx; 1175c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou next = usedpools[size + size]; 1176c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou prev = next->prevpool; 1177c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* insert pool before next: prev <-> pool <-> next */ 1178c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou pool->nextpool = next; 1179c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou pool->prevpool = prev; 1180c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou next->prevpool = pool; 1181c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou prev->nextpool = pool; 1182c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou UNLOCK(); 1183c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return; 1184c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1185d97a1c008c4a7ae04c55c8de2cdb71a9ea43656aTim Peters 118691c12ebc3dc6472ea486ab5e4aa38139283d48adBenjamin Peterson#ifdef WITH_VALGRIND 118791c12ebc3dc6472ea486ab5e4aa38139283d48adBenjamin Petersonredirect: 118891c12ebc3dc6472ea486ab5e4aa38139283d48adBenjamin Peterson#endif 1189c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* We didn't allocate this address. */ 1190c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou free(p); 1191a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer} 1192a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 119384c1b974675b9252e1f5764a399ff9455fbf73e0Tim Peters/* realloc. If p is NULL, this acts like malloc(nbytes). Else if nbytes==0, 119484c1b974675b9252e1f5764a399ff9455fbf73e0Tim Peters * then as the Python docs promise, we do not treat this like free(p), and 119584c1b974675b9252e1f5764a399ff9455fbf73e0Tim Peters * return a non-NULL result. 119684c1b974675b9252e1f5764a399ff9455fbf73e0Tim Peters */ 1197a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 1198d2560cd37c8d38c9eb79bcfce9d780b0753a3cb5Neil Schemenauer#undef PyObject_Realloc 1199a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauervoid * 1200d2560cd37c8d38c9eb79bcfce9d780b0753a3cb5Neil SchemenauerPyObject_Realloc(void *p, size_t nbytes) 1201a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer{ 1202c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou void *bp; 1203c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou poolp pool; 1204c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou size_t size; 12055a72e76b6938941547dd25f9198db7d17fa36960Antoine Pitrou#ifndef Py_USING_MEMORY_DEBUGGER 12065a72e76b6938941547dd25f9198db7d17fa36960Antoine Pitrou uint arenaindex_temp; 12075a72e76b6938941547dd25f9198db7d17fa36960Antoine Pitrou#endif 1208c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1209c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (p == NULL) 1210c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return PyObject_Malloc(nbytes); 1211c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1212c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* 1213c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * Limit ourselves to PY_SSIZE_T_MAX bytes to prevent security holes. 1214c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * Most python internals blindly use a signed Py_ssize_t to track 1215c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * things without checking for overflows or negatives. 1216c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * As size_t is unsigned, checking for nbytes < 0 is not required. 1217c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 1218c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (nbytes > PY_SSIZE_T_MAX) 1219c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return NULL; 12200470bab69783c13447cb634fa403ef1067fe56d1Gregory P. Smith 122191c12ebc3dc6472ea486ab5e4aa38139283d48adBenjamin Peterson#ifdef WITH_VALGRIND 1222c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Treat running_on_valgrind == -1 the same as 0 */ 1223c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (UNLIKELY(running_on_valgrind > 0)) 1224c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou goto redirect; 122591c12ebc3dc6472ea486ab5e4aa38139283d48adBenjamin Peterson#endif 122691c12ebc3dc6472ea486ab5e4aa38139283d48adBenjamin Peterson 1227c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou pool = POOL_ADDR(p); 1228c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (Py_ADDRESS_IN_RANGE(p, pool)) { 1229c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* We're in charge of this block */ 1230c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou size = INDEX2SIZE(pool->szidx); 1231c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (nbytes <= size) { 1232c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* The block is staying the same or shrinking. If 1233c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * it's shrinking, there's a tradeoff: it costs 1234c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * cycles to copy the block to a smaller size class, 1235c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * but it wastes memory not to copy it. The 1236c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * compromise here is to copy on shrink only if at 1237c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * least 25% of size can be shaved off. 1238c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 1239c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (4 * nbytes > 3 * size) { 1240c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* It's the same, 1241c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * or shrinking and new/old > 3/4. 1242c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 1243c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return p; 1244c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1245c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou size = nbytes; 1246c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1247c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou bp = PyObject_Malloc(nbytes); 1248c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (bp != NULL) { 1249c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou memcpy(bp, p, size); 1250c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou PyObject_Free(p); 1251c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1252c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return bp; 1253c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 125491c12ebc3dc6472ea486ab5e4aa38139283d48adBenjamin Peterson#ifdef WITH_VALGRIND 125591c12ebc3dc6472ea486ab5e4aa38139283d48adBenjamin Peterson redirect: 125691c12ebc3dc6472ea486ab5e4aa38139283d48adBenjamin Peterson#endif 1257c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* We're not managing this block. If nbytes <= 1258c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * SMALL_REQUEST_THRESHOLD, it's tempting to try to take over this 1259c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * block. However, if we do, we need to copy the valid data from 1260c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * the C-managed block to one of our blocks, and there's no portable 1261c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * way to know how much of the memory space starting at p is valid. 1262c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * As bug 1185883 pointed out the hard way, it's possible that the 1263c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * C-managed block is "at the end" of allocated VM space, so that 1264c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * a memory fault can occur if we try to copy nbytes bytes starting 1265c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * at p. Instead we punt: let C continue to manage this block. 1266c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 1267c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (nbytes) 1268c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return realloc(p, nbytes); 1269c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* C doesn't define the result of realloc(p, 0) (it may or may not 1270c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * return NULL then), but Python's docs promise that nbytes==0 never 1271c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * returns NULL. We don't pass 0 to realloc(), to avoid that endcase 1272c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * to begin with. Even then, we can't be sure that realloc() won't 1273c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * return NULL. 1274c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 1275c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou bp = realloc(p, 1); 1276c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return bp ? bp : p; 1277a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer} 1278a35c688055c72e9442f6a82c3ec0e09654077975Neil Schemenauer 1279c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou#else /* ! WITH_PYMALLOC */ 1280ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters 1281ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters/*==========================================================================*/ 1282d2560cd37c8d38c9eb79bcfce9d780b0753a3cb5Neil Schemenauer/* pymalloc not enabled: Redirect the entry points to malloc. These will 1283d2560cd37c8d38c9eb79bcfce9d780b0753a3cb5Neil Schemenauer * only be used by extensions that are compiled with pymalloc enabled. */ 128462c06ba6a9aa388555d826b4adb5d8981d74f4b2Tim Peters 1285ce7fb9b5151f7238bdbaeb16c3041c9990ca8e9dTim Petersvoid * 1286d2560cd37c8d38c9eb79bcfce9d780b0753a3cb5Neil SchemenauerPyObject_Malloc(size_t n) 12871221c0a435135143632d986e861d9243d3d2ad35Tim Peters{ 1288c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return PyMem_MALLOC(n); 12891221c0a435135143632d986e861d9243d3d2ad35Tim Peters} 12901221c0a435135143632d986e861d9243d3d2ad35Tim Peters 1291ce7fb9b5151f7238bdbaeb16c3041c9990ca8e9dTim Petersvoid * 1292d2560cd37c8d38c9eb79bcfce9d780b0753a3cb5Neil SchemenauerPyObject_Realloc(void *p, size_t n) 12931221c0a435135143632d986e861d9243d3d2ad35Tim Peters{ 1294c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return PyMem_REALLOC(p, n); 12951221c0a435135143632d986e861d9243d3d2ad35Tim Peters} 12961221c0a435135143632d986e861d9243d3d2ad35Tim Peters 12971221c0a435135143632d986e861d9243d3d2ad35Tim Petersvoid 1298d2560cd37c8d38c9eb79bcfce9d780b0753a3cb5Neil SchemenauerPyObject_Free(void *p) 12991221c0a435135143632d986e861d9243d3d2ad35Tim Peters{ 1300c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou PyMem_FREE(p); 13011221c0a435135143632d986e861d9243d3d2ad35Tim Peters} 13021221c0a435135143632d986e861d9243d3d2ad35Tim Peters#endif /* WITH_PYMALLOC */ 13031221c0a435135143632d986e861d9243d3d2ad35Tim Peters 1304ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters#ifdef PYMALLOC_DEBUG 1305ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters/*==========================================================================*/ 130662c06ba6a9aa388555d826b4adb5d8981d74f4b2Tim Peters/* A x-platform debugging allocator. This doesn't manage memory directly, 130762c06ba6a9aa388555d826b4adb5d8981d74f4b2Tim Peters * it wraps a real allocator, adding extra debugging info to the memory blocks. 130862c06ba6a9aa388555d826b4adb5d8981d74f4b2Tim Peters */ 1309ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters 1310f6fb501c577ede5c3681a703925abf36e69bc5b9Tim Peters/* Special bytes broadcast into debug memory blocks at appropriate times. 1311f6fb501c577ede5c3681a703925abf36e69bc5b9Tim Peters * Strings of these are unlikely to be valid addresses, floats, ints or 1312f6fb501c577ede5c3681a703925abf36e69bc5b9Tim Peters * 7-bit ASCII. 1313f6fb501c577ede5c3681a703925abf36e69bc5b9Tim Peters */ 1314f6fb501c577ede5c3681a703925abf36e69bc5b9Tim Peters#undef CLEANBYTE 1315f6fb501c577ede5c3681a703925abf36e69bc5b9Tim Peters#undef DEADBYTE 1316f6fb501c577ede5c3681a703925abf36e69bc5b9Tim Peters#undef FORBIDDENBYTE 1317f6fb501c577ede5c3681a703925abf36e69bc5b9Tim Peters#define CLEANBYTE 0xCB /* clean (newly allocated) memory */ 1318889f61dcfbdccf4d1de7da354ee6165e488e4665Tim Peters#define DEADBYTE 0xDB /* dead (newly freed) memory */ 1319f6fb501c577ede5c3681a703925abf36e69bc5b9Tim Peters#define FORBIDDENBYTE 0xFB /* untouchable bytes at each end of a block */ 1320ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters 132102ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónsson/* We tag each block with an API ID in order to tag API violations */ 132202ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónsson#define _PYMALLOC_MEM_ID 'm' /* the PyMem_Malloc() API */ 132302ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónsson#define _PYMALLOC_OBJ_ID 'o' /* The PyObject_Malloc() API */ 132402ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónsson 1325c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitroustatic size_t serialno = 0; /* incremented on each debug {m,re}alloc */ 1326ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters 1327e085017ab7121b27be315d36ef0c25ed51484023Tim Peters/* serialno is always incremented via calling this routine. The point is 13289ea89d2a1972a527bee508c3fb8cd42a86908da1Tim Peters * to supply a single place to set a breakpoint. 13299ea89d2a1972a527bee508c3fb8cd42a86908da1Tim Peters */ 1330e085017ab7121b27be315d36ef0c25ed51484023Tim Petersstatic void 1331bd02b14255f99feef90121cf654989b9fe827210Neil Schemenauerbumpserialno(void) 1332e085017ab7121b27be315d36ef0c25ed51484023Tim Peters{ 1333c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou ++serialno; 1334e085017ab7121b27be315d36ef0c25ed51484023Tim Peters} 1335e085017ab7121b27be315d36ef0c25ed51484023Tim Peters 13369ea89d2a1972a527bee508c3fb8cd42a86908da1Tim Peters#define SST SIZEOF_SIZE_T 1337e085017ab7121b27be315d36ef0c25ed51484023Tim Peters 13389ea89d2a1972a527bee508c3fb8cd42a86908da1Tim Peters/* Read sizeof(size_t) bytes at p as a big-endian size_t. */ 13399ea89d2a1972a527bee508c3fb8cd42a86908da1Tim Petersstatic size_t 13409ea89d2a1972a527bee508c3fb8cd42a86908da1Tim Petersread_size_t(const void *p) 1341ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters{ 1342c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou const uchar *q = (const uchar *)p; 1343c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou size_t result = *q++; 1344c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou int i; 13459ea89d2a1972a527bee508c3fb8cd42a86908da1Tim Peters 1346c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou for (i = SST; --i > 0; ++q) 1347c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou result = (result << 8) | *q; 1348c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return result; 1349ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters} 1350ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters 13519ea89d2a1972a527bee508c3fb8cd42a86908da1Tim Peters/* Write n as a big-endian size_t, MSB at address p, LSB at 13529ea89d2a1972a527bee508c3fb8cd42a86908da1Tim Peters * p + sizeof(size_t) - 1. 13539ea89d2a1972a527bee508c3fb8cd42a86908da1Tim Peters */ 1354ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Petersstatic void 13559ea89d2a1972a527bee508c3fb8cd42a86908da1Tim Peterswrite_size_t(void *p, size_t n) 1356ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters{ 1357c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou uchar *q = (uchar *)p + SST - 1; 1358c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou int i; 13599ea89d2a1972a527bee508c3fb8cd42a86908da1Tim Peters 1360c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou for (i = SST; --i >= 0; --q) { 1361c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou *q = (uchar)(n & 0xff); 1362c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou n >>= 8; 1363c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1364ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters} 1365ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters 136608d821582faab8f3b6eeab1b1fd7520417b82b80Tim Peters#ifdef Py_DEBUG 136708d821582faab8f3b6eeab1b1fd7520417b82b80Tim Peters/* Is target in the list? The list is traversed via the nextpool pointers. 136808d821582faab8f3b6eeab1b1fd7520417b82b80Tim Peters * The list may be NULL-terminated, or circular. Return 1 if target is in 136908d821582faab8f3b6eeab1b1fd7520417b82b80Tim Peters * list, else 0. 137008d821582faab8f3b6eeab1b1fd7520417b82b80Tim Peters */ 137108d821582faab8f3b6eeab1b1fd7520417b82b80Tim Petersstatic int 137208d821582faab8f3b6eeab1b1fd7520417b82b80Tim Peterspool_is_in_list(const poolp target, poolp list) 137308d821582faab8f3b6eeab1b1fd7520417b82b80Tim Peters{ 1374c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou poolp origlist = list; 1375c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(target != NULL); 1376c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (list == NULL) 1377c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return 0; 1378c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou do { 1379c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (target == list) 1380c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return 1; 1381c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou list = list->nextpool; 1382c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } while (list != NULL && list != origlist); 1383c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return 0; 138408d821582faab8f3b6eeab1b1fd7520417b82b80Tim Peters} 138508d821582faab8f3b6eeab1b1fd7520417b82b80Tim Peters 138608d821582faab8f3b6eeab1b1fd7520417b82b80Tim Peters#else 138708d821582faab8f3b6eeab1b1fd7520417b82b80Tim Peters#define pool_is_in_list(X, Y) 1 138808d821582faab8f3b6eeab1b1fd7520417b82b80Tim Peters 1389c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou#endif /* Py_DEBUG */ 139008d821582faab8f3b6eeab1b1fd7520417b82b80Tim Peters 13919ea89d2a1972a527bee508c3fb8cd42a86908da1Tim Peters/* Let S = sizeof(size_t). The debug malloc asks for 4*S extra bytes and 13929ea89d2a1972a527bee508c3fb8cd42a86908da1Tim Peters fills them with useful stuff, here calling the underlying malloc's result p: 1393ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters 13949ea89d2a1972a527bee508c3fb8cd42a86908da1Tim Petersp[0: S] 13959ea89d2a1972a527bee508c3fb8cd42a86908da1Tim Peters Number of bytes originally asked for. This is a size_t, big-endian (easier 13969ea89d2a1972a527bee508c3fb8cd42a86908da1Tim Peters to read in a memory dump). 13979ea89d2a1972a527bee508c3fb8cd42a86908da1Tim Petersp[S: 2*S] 1398f6fb501c577ede5c3681a703925abf36e69bc5b9Tim Peters Copies of FORBIDDENBYTE. Used to catch under- writes and reads. 13999ea89d2a1972a527bee508c3fb8cd42a86908da1Tim Petersp[2*S: 2*S+n] 1400f6fb501c577ede5c3681a703925abf36e69bc5b9Tim Peters The requested memory, filled with copies of CLEANBYTE. 1401ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters Used to catch reference to uninitialized memory. 14029ea89d2a1972a527bee508c3fb8cd42a86908da1Tim Peters &p[2*S] is returned. Note that this is 8-byte aligned if pymalloc 1403ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters handled the request itself. 14049ea89d2a1972a527bee508c3fb8cd42a86908da1Tim Petersp[2*S+n: 2*S+n+S] 1405f6fb501c577ede5c3681a703925abf36e69bc5b9Tim Peters Copies of FORBIDDENBYTE. Used to catch over- writes and reads. 14069ea89d2a1972a527bee508c3fb8cd42a86908da1Tim Petersp[2*S+n+S: 2*S+n+2*S] 1407d2560cd37c8d38c9eb79bcfce9d780b0753a3cb5Neil Schemenauer A serial number, incremented by 1 on each call to _PyObject_DebugMalloc 1408d2560cd37c8d38c9eb79bcfce9d780b0753a3cb5Neil Schemenauer and _PyObject_DebugRealloc. 14099ea89d2a1972a527bee508c3fb8cd42a86908da1Tim Peters This is a big-endian size_t. 1410ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters If "bad memory" is detected later, the serial number gives an 1411ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters excellent way to set a breakpoint on the next run, to capture the 1412ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters instant at which this block was passed out. 1413ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters*/ 1414ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters 141502ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónsson/* debug replacements for the PyMem_* memory API */ 141602ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónssonvoid * 141702ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónsson_PyMem_DebugMalloc(size_t nbytes) 141802ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónsson{ 1419c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return _PyObject_DebugMallocApi(_PYMALLOC_MEM_ID, nbytes); 142002ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónsson} 142102ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónssonvoid * 142202ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónsson_PyMem_DebugRealloc(void *p, size_t nbytes) 142302ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónsson{ 1424c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return _PyObject_DebugReallocApi(_PYMALLOC_MEM_ID, p, nbytes); 142502ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónsson} 142602ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónssonvoid 142702ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónsson_PyMem_DebugFree(void *p) 142802ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónsson{ 1429c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou _PyObject_DebugFreeApi(_PYMALLOC_MEM_ID, p); 143002ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónsson} 143102ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónsson 143202ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónsson/* debug replacements for the PyObject_* memory API */ 1433ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Petersvoid * 1434d2560cd37c8d38c9eb79bcfce9d780b0753a3cb5Neil Schemenauer_PyObject_DebugMalloc(size_t nbytes) 1435ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters{ 1436c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return _PyObject_DebugMallocApi(_PYMALLOC_OBJ_ID, nbytes); 143702ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónsson} 143802ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónssonvoid * 143902ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónsson_PyObject_DebugRealloc(void *p, size_t nbytes) 144002ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónsson{ 1441c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return _PyObject_DebugReallocApi(_PYMALLOC_OBJ_ID, p, nbytes); 144202ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónsson} 144302ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónssonvoid 144402ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónsson_PyObject_DebugFree(void *p) 144502ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónsson{ 1446c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou _PyObject_DebugFreeApi(_PYMALLOC_OBJ_ID, p); 144702ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónsson} 144802ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónssonvoid 1449b331802f976c85954efbeb7a49f2591951460be2Kristján Valur Jónsson_PyObject_DebugCheckAddress(const void *p) 145002ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónsson{ 1451c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou _PyObject_DebugCheckAddressApi(_PYMALLOC_OBJ_ID, p); 145202ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónsson} 145302ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónsson 145402ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónsson 145502ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónsson/* generic debug memory api, with an "id" to identify the API in use */ 145602ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónssonvoid * 145702ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónsson_PyObject_DebugMallocApi(char id, size_t nbytes) 145802ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónsson{ 1459c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou uchar *p; /* base address of malloc'ed block */ 1460c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou uchar *tail; /* p + 2*SST + nbytes == pointer to tail pad bytes */ 1461c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou size_t total; /* nbytes + 4*SST */ 1462c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1463c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou bumpserialno(); 1464c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou total = nbytes + 4*SST; 1465c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (total < nbytes) 1466c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* overflow: can't represent total as a size_t */ 1467c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return NULL; 1468c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1469c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou p = (uchar *)PyObject_Malloc(total); 1470c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (p == NULL) 1471c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return NULL; 1472c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1473c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* at p, write size (SST bytes), id (1 byte), pad (SST-1 bytes) */ 1474c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou write_size_t(p, nbytes); 1475c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou p[SST] = (uchar)id; 1476c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou memset(p + SST + 1 , FORBIDDENBYTE, SST-1); 1477c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1478c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (nbytes > 0) 1479c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou memset(p + 2*SST, CLEANBYTE, nbytes); 1480c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1481c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* at tail, write pad (SST bytes) and serialno (SST bytes) */ 1482c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou tail = p + 2*SST + nbytes; 1483c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou memset(tail, FORBIDDENBYTE, SST); 1484c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou write_size_t(tail + SST, serialno); 1485c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1486c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return p + 2*SST; 1487ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters} 1488ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters 14899ea89d2a1972a527bee508c3fb8cd42a86908da1Tim Peters/* The debug free first checks the 2*SST bytes on each end for sanity (in 149002ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónsson particular, that the FORBIDDENBYTEs with the api ID are still intact). 1491f6fb501c577ede5c3681a703925abf36e69bc5b9Tim Peters Then fills the original bytes with DEADBYTE. 1492ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters Then calls the underlying free. 1493ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters*/ 1494ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Petersvoid 149502ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónsson_PyObject_DebugFreeApi(char api, void *p) 1496ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters{ 1497c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou uchar *q = (uchar *)p - 2*SST; /* address returned from malloc */ 1498c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou size_t nbytes; 1499c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1500c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (p == NULL) 1501c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return; 1502c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou _PyObject_DebugCheckAddressApi(api, p); 1503c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou nbytes = read_size_t(q); 1504c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou nbytes += 4*SST; 1505c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (nbytes > 0) 1506c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou memset(q, DEADBYTE, nbytes); 1507c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou PyObject_Free(q); 1508ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters} 1509ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters 1510ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Petersvoid * 151102ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónsson_PyObject_DebugReallocApi(char api, void *p, size_t nbytes) 1512ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters{ 1513c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou uchar *q = (uchar *)p; 1514c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou uchar *tail; 1515c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou size_t total; /* nbytes + 4*SST */ 1516c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou size_t original_nbytes; 1517c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou int i; 1518c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1519c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (p == NULL) 1520c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return _PyObject_DebugMallocApi(api, nbytes); 1521c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1522c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou _PyObject_DebugCheckAddressApi(api, p); 1523c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou bumpserialno(); 1524c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou original_nbytes = read_size_t(q - 2*SST); 1525c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou total = nbytes + 4*SST; 1526c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (total < nbytes) 1527c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* overflow: can't represent total as a size_t */ 1528c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return NULL; 1529c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1530c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (nbytes < original_nbytes) { 1531c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* shrinking: mark old extra memory dead */ 1532c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou memset(q + nbytes, DEADBYTE, original_nbytes - nbytes + 2*SST); 1533c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1534c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1535c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Resize and add decorations. We may get a new pointer here, in which 1536c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * case we didn't get the chance to mark the old memory with DEADBYTE, 1537c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * but we live with that. 1538c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 1539c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou q = (uchar *)PyObject_Realloc(q - 2*SST, total); 1540c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (q == NULL) 1541c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return NULL; 1542c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1543c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou write_size_t(q, nbytes); 1544c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(q[SST] == (uchar)api); 1545c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou for (i = 1; i < SST; ++i) 1546c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(q[SST + i] == FORBIDDENBYTE); 1547c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou q += 2*SST; 1548c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou tail = q + nbytes; 1549c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou memset(tail, FORBIDDENBYTE, SST); 1550c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou write_size_t(tail + SST, serialno); 1551c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1552c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (nbytes > original_nbytes) { 1553c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* growing: mark new extra memory clean */ 1554c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou memset(q + original_nbytes, CLEANBYTE, 1555918c90ce06d6189f8d24d1dba842382a5cb447d4Stefan Krah nbytes - original_nbytes); 1556c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1557c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1558c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return q; 1559ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters} 1560ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters 15617ccfadf3a88fb83ffa9cee2a3ff41910aa5a00ecTim Peters/* Check the forbidden bytes on both ends of the memory allocated for p. 1562d2560cd37c8d38c9eb79bcfce9d780b0753a3cb5Neil Schemenauer * If anything is wrong, print info to stderr via _PyObject_DebugDumpAddress, 15637ccfadf3a88fb83ffa9cee2a3ff41910aa5a00ecTim Peters * and call Py_FatalError to kill the program. 156402ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónsson * The API id, is also checked. 15657ccfadf3a88fb83ffa9cee2a3ff41910aa5a00ecTim Peters */ 15667ccfadf3a88fb83ffa9cee2a3ff41910aa5a00ecTim Peters void 156702ca57ce4c728c4a18d31a6a3f2681bcd1aea2daKristján Valur Jónsson_PyObject_DebugCheckAddressApi(char api, const void *p) 1568ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters{ 1569c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou const uchar *q = (const uchar *)p; 1570c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou char msgbuf[64]; 1571c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou char *msg; 1572c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou size_t nbytes; 1573c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou const uchar *tail; 1574c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou int i; 1575c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou char id; 1576c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1577c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (p == NULL) { 1578c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou msg = "didn't expect a NULL pointer"; 1579c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou goto error; 1580c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1581c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1582c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Check the API id */ 1583c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou id = (char)q[-SST]; 1584c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (id != api) { 1585c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou msg = msgbuf; 1586c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou snprintf(msg, sizeof(msgbuf), "bad ID: Allocated using API '%c', verified using API '%c'", id, api); 1587c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou msgbuf[sizeof(msgbuf)-1] = 0; 1588c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou goto error; 1589c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1590c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1591c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Check the stuff at the start of p first: if there's underwrite 1592c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * corruption, the number-of-bytes field may be nuts, and checking 1593c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * the tail could lead to a segfault then. 1594c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 1595c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou for (i = SST-1; i >= 1; --i) { 1596c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (*(q-i) != FORBIDDENBYTE) { 1597c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou msg = "bad leading pad byte"; 1598c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou goto error; 1599c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1600c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1601c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1602c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou nbytes = read_size_t(q - 2*SST); 1603c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou tail = q + nbytes; 1604c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou for (i = 0; i < SST; ++i) { 1605c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (tail[i] != FORBIDDENBYTE) { 1606c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou msg = "bad trailing pad byte"; 1607c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou goto error; 1608c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1609c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1610c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1611c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return; 1612d1139e043c74fd2495ded3cb534c7e0a339532e2Tim Peters 1613d1139e043c74fd2495ded3cb534c7e0a339532e2Tim Peterserror: 1614c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou _PyObject_DebugDumpAddress(p); 1615c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou Py_FatalError(msg); 1616ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters} 1617ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters 16187ccfadf3a88fb83ffa9cee2a3ff41910aa5a00ecTim Peters/* Display info to stderr about the memory block at p. */ 1619ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Petersvoid 1620d2560cd37c8d38c9eb79bcfce9d780b0753a3cb5Neil Schemenauer_PyObject_DebugDumpAddress(const void *p) 1621ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters{ 1622c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou const uchar *q = (const uchar *)p; 1623c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou const uchar *tail; 1624c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou size_t nbytes, serial; 1625c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou int i; 1626c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou int ok; 1627c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou char id; 1628c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1629c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou fprintf(stderr, "Debug memory block at address p=%p:", p); 1630c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (p == NULL) { 1631c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou fprintf(stderr, "\n"); 1632c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return; 1633c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1634c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou id = (char)q[-SST]; 1635c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou fprintf(stderr, " API '%c'\n", id); 1636c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1637c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou nbytes = read_size_t(q - 2*SST); 1638c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou fprintf(stderr, " %" PY_FORMAT_SIZE_T "u bytes originally " 1639c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou "requested\n", nbytes); 1640c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1641c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* In case this is nuts, check the leading pad bytes first. */ 1642c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou fprintf(stderr, " The %d pad bytes at p-%d are ", SST-1, SST-1); 1643c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou ok = 1; 1644c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou for (i = 1; i <= SST-1; ++i) { 1645c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (*(q-i) != FORBIDDENBYTE) { 1646c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou ok = 0; 1647c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou break; 1648c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1649c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1650c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (ok) 1651c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou fputs("FORBIDDENBYTE, as expected.\n", stderr); 1652c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou else { 1653c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou fprintf(stderr, "not all FORBIDDENBYTE (0x%02x):\n", 1654c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou FORBIDDENBYTE); 1655c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou for (i = SST-1; i >= 1; --i) { 1656c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou const uchar byte = *(q-i); 1657c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou fprintf(stderr, " at p-%d: 0x%02x", i, byte); 1658c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (byte != FORBIDDENBYTE) 1659c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou fputs(" *** OUCH", stderr); 1660c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou fputc('\n', stderr); 1661c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1662c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1663c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou fputs(" Because memory is corrupted at the start, the " 1664c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou "count of bytes requested\n" 1665c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou " may be bogus, and checking the trailing pad " 1666c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou "bytes may segfault.\n", stderr); 1667c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1668c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1669c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou tail = q + nbytes; 1670c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou fprintf(stderr, " The %d pad bytes at tail=%p are ", SST, tail); 1671c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou ok = 1; 1672c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou for (i = 0; i < SST; ++i) { 1673c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (tail[i] != FORBIDDENBYTE) { 1674c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou ok = 0; 1675c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou break; 1676c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1677c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1678c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (ok) 1679c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou fputs("FORBIDDENBYTE, as expected.\n", stderr); 1680c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou else { 1681c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou fprintf(stderr, "not all FORBIDDENBYTE (0x%02x):\n", 1682918c90ce06d6189f8d24d1dba842382a5cb447d4Stefan Krah FORBIDDENBYTE); 1683c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou for (i = 0; i < SST; ++i) { 1684c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou const uchar byte = tail[i]; 1685c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou fprintf(stderr, " at tail+%d: 0x%02x", 1686918c90ce06d6189f8d24d1dba842382a5cb447d4Stefan Krah i, byte); 1687c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (byte != FORBIDDENBYTE) 1688c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou fputs(" *** OUCH", stderr); 1689c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou fputc('\n', stderr); 1690c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1691c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1692c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1693c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou serial = read_size_t(tail + SST); 1694c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou fprintf(stderr, " The block was made by call #%" PY_FORMAT_SIZE_T 1695c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou "u to debug malloc/realloc.\n", serial); 1696c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1697c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (nbytes > 0) { 1698c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou i = 0; 1699c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou fputs(" Data at p:", stderr); 1700c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* print up to 8 bytes at the start */ 1701c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou while (q < tail && i < 8) { 1702c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou fprintf(stderr, " %02x", *q); 1703c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou ++i; 1704c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou ++q; 1705c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1706c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* and up to 8 at the end */ 1707c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (q < tail) { 1708c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (tail - q > 8) { 1709c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou fputs(" ...", stderr); 1710c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou q = tail - 8; 1711c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1712c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou while (q < tail) { 1713c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou fprintf(stderr, " %02x", *q); 1714c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou ++q; 1715c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1716c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1717c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou fputc('\n', stderr); 1718c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1719ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters} 1720ddea208be9e2a8fa281e25ebbc890378dd2aa286Tim Peters 17219ea89d2a1972a527bee508c3fb8cd42a86908da1Tim Petersstatic size_t 17229ea89d2a1972a527bee508c3fb8cd42a86908da1Tim Petersprintone(const char* msg, size_t value) 172316bcb6b1afc46f2f73e207bc0484f016c51f0fd9Tim Peters{ 1724c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou int i, k; 1725c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou char buf[100]; 1726c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou size_t origvalue = value; 1727c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1728c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou fputs(msg, stderr); 1729c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou for (i = (int)strlen(msg); i < 35; ++i) 1730c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou fputc(' ', stderr); 1731c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou fputc('=', stderr); 1732c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1733c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Write the value with commas. */ 1734c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou i = 22; 1735c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou buf[i--] = '\0'; 1736c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou buf[i--] = '\n'; 1737c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou k = 3; 1738c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou do { 1739c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou size_t nextvalue = value / 10; 17408e830a06643384d0c33432207585e5b0702d18a5Benjamin Peterson unsigned int digit = (unsigned int)(value - nextvalue * 10); 1741c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou value = nextvalue; 1742c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou buf[i--] = (char)(digit + '0'); 1743c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou --k; 1744c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (k == 0 && value && i >= 0) { 1745c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou k = 3; 1746c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou buf[i--] = ','; 1747c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1748c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } while (value && i >= 0); 1749c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1750c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou while (i >= 0) 1751c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou buf[i--] = ' '; 1752c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou fputs(buf, stderr); 1753c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1754c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return origvalue; 175516bcb6b1afc46f2f73e207bc0484f016c51f0fd9Tim Peters} 175616bcb6b1afc46f2f73e207bc0484f016c51f0fd9Tim Peters 175708d821582faab8f3b6eeab1b1fd7520417b82b80Tim Peters/* Print summary info to stderr about the state of pymalloc's structures. 175808d821582faab8f3b6eeab1b1fd7520417b82b80Tim Peters * In Py_DEBUG mode, also perform some expensive internal consistency 175908d821582faab8f3b6eeab1b1fd7520417b82b80Tim Peters * checks. 176008d821582faab8f3b6eeab1b1fd7520417b82b80Tim Peters */ 17617ccfadf3a88fb83ffa9cee2a3ff41910aa5a00ecTim Petersvoid 17620e871188e8cd9a4e41be7c734e250bfce2d92d56Tim Peters_PyObject_DebugMallocStats(void) 17637ccfadf3a88fb83ffa9cee2a3ff41910aa5a00ecTim Peters{ 1764c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou uint i; 1765c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou const uint numclasses = SMALL_REQUEST_THRESHOLD >> ALIGNMENT_SHIFT; 1766c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* # of pools, allocated blocks, and free blocks per class index */ 1767c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou size_t numpools[SMALL_REQUEST_THRESHOLD >> ALIGNMENT_SHIFT]; 1768c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou size_t numblocks[SMALL_REQUEST_THRESHOLD >> ALIGNMENT_SHIFT]; 1769c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou size_t numfreeblocks[SMALL_REQUEST_THRESHOLD >> ALIGNMENT_SHIFT]; 1770c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* total # of allocated bytes in used and full pools */ 1771c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou size_t allocated_bytes = 0; 1772c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* total # of available bytes in used pools */ 1773c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou size_t available_bytes = 0; 1774c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* # of free pools + pools not yet carved out of current arena */ 1775c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou uint numfreepools = 0; 1776c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* # of bytes for arena alignment padding */ 1777c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou size_t arena_alignment = 0; 1778c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* # of bytes in used and full pools used for pool_headers */ 1779c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou size_t pool_header_bytes = 0; 1780c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* # of bytes in used and full pools wasted due to quantization, 1781c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * i.e. the necessarily leftover space at the ends of used and 1782c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * full pools. 1783c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 1784c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou size_t quantization = 0; 1785c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* # of arenas actually allocated. */ 1786c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou size_t narenas = 0; 1787c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* running total -- should equal narenas * ARENA_SIZE */ 1788c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou size_t total; 1789c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou char buf[128]; 1790c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1791c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou fprintf(stderr, "Small block threshold = %d, in %u size classes.\n", 1792918c90ce06d6189f8d24d1dba842382a5cb447d4Stefan Krah SMALL_REQUEST_THRESHOLD, numclasses); 1793c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1794c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou for (i = 0; i < numclasses; ++i) 1795c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou numpools[i] = numblocks[i] = numfreeblocks[i] = 0; 1796c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1797c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Because full pools aren't linked to from anything, it's easiest 1798c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * to march over all the arenas. If we're lucky, most of the memory 1799c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou * will be living in full pools -- would be a shame to miss them. 1800c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 1801c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou for (i = 0; i < maxarenas; ++i) { 1802c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou uint j; 1803c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou uptr base = arenas[i].address; 1804c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1805c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Skip arenas which are not allocated. */ 1806c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (arenas[i].address == (uptr)NULL) 1807c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou continue; 1808c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou narenas += 1; 1809c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1810c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou numfreepools += arenas[i].nfreepools; 1811c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1812c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* round up to pool alignment */ 1813c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (base & (uptr)POOL_SIZE_MASK) { 1814c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou arena_alignment += POOL_SIZE; 1815c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou base &= ~(uptr)POOL_SIZE_MASK; 1816c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou base += POOL_SIZE; 1817c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1818c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1819c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* visit every pool in the arena */ 1820c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(base <= (uptr) arenas[i].pool_address); 1821c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou for (j = 0; 1822c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou base < (uptr) arenas[i].pool_address; 1823c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou ++j, base += POOL_SIZE) { 1824c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou poolp p = (poolp)base; 1825c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou const uint sz = p->szidx; 1826c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou uint freeblocks; 1827c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1828c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (p->ref.count == 0) { 1829c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* currently unused */ 1830c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(pool_is_in_list(p, arenas[i].freepools)); 1831c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou continue; 1832c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1833c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou ++numpools[sz]; 1834c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou numblocks[sz] += p->ref.count; 1835c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou freeblocks = NUMBLOCKS(sz) - p->ref.count; 1836c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou numfreeblocks[sz] += freeblocks; 183708d821582faab8f3b6eeab1b1fd7520417b82b80Tim Peters#ifdef Py_DEBUG 1838c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (freeblocks > 0) 1839c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(pool_is_in_list(p, usedpools[sz + sz])); 184008d821582faab8f3b6eeab1b1fd7520417b82b80Tim Peters#endif 1841c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1842c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1843c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(narenas == narenas_currently_allocated); 1844c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1845c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou fputc('\n', stderr); 1846c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou fputs("class size num pools blocks in use avail blocks\n" 1847c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou "----- ---- --------- ------------- ------------\n", 1848918c90ce06d6189f8d24d1dba842382a5cb447d4Stefan Krah stderr); 1849c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1850c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou for (i = 0; i < numclasses; ++i) { 1851c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou size_t p = numpools[i]; 1852c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou size_t b = numblocks[i]; 1853c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou size_t f = numfreeblocks[i]; 1854c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou uint size = INDEX2SIZE(i); 1855c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (p == 0) { 1856c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(b == 0 && f == 0); 1857c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou continue; 1858c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1859c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou fprintf(stderr, "%5u %6u " 1860c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou "%11" PY_FORMAT_SIZE_T "u " 1861c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou "%15" PY_FORMAT_SIZE_T "u " 1862c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou "%13" PY_FORMAT_SIZE_T "u\n", 1863918c90ce06d6189f8d24d1dba842382a5cb447d4Stefan Krah i, size, p, b, f); 1864c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou allocated_bytes += b * size; 1865c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou available_bytes += f * size; 1866c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou pool_header_bytes += p * POOL_OVERHEAD; 1867c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou quantization += p * ((POOL_SIZE - POOL_OVERHEAD) % size); 1868c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1869c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou fputc('\n', stderr); 1870c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou (void)printone("# times object malloc called", serialno); 1871c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1872c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou (void)printone("# arenas allocated total", ntimes_arena_allocated); 1873c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou (void)printone("# arenas reclaimed", ntimes_arena_allocated - narenas); 1874c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou (void)printone("# arenas highwater mark", narenas_highwater); 1875c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou (void)printone("# arenas allocated current", narenas); 1876c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1877c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou PyOS_snprintf(buf, sizeof(buf), 1878c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou "%" PY_FORMAT_SIZE_T "u arenas * %d bytes/arena", 1879c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou narenas, ARENA_SIZE); 1880c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou (void)printone(buf, narenas * ARENA_SIZE); 1881c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1882c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou fputc('\n', stderr); 1883c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1884c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou total = printone("# bytes in allocated blocks", allocated_bytes); 1885c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou total += printone("# bytes in available blocks", available_bytes); 1886c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1887c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou PyOS_snprintf(buf, sizeof(buf), 1888c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou "%u unused pools * %d bytes", numfreepools, POOL_SIZE); 1889c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou total += printone(buf, (size_t)numfreepools * POOL_SIZE); 1890c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 1891c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou total += printone("# bytes lost to pool headers", pool_header_bytes); 1892c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou total += printone("# bytes lost to quantization", quantization); 1893c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou total += printone("# bytes lost to arena alignment", arena_alignment); 1894c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou (void)printone("Total", total); 18957ccfadf3a88fb83ffa9cee2a3ff41910aa5a00ecTim Peters} 18967ccfadf3a88fb83ffa9cee2a3ff41910aa5a00ecTim Peters 1897c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou#endif /* PYMALLOC_DEBUG */ 18987eb3c9196da5be52a670d6d8dd24939a3c27b594Neal Norwitz 18997eb3c9196da5be52a670d6d8dd24939a3c27b594Neal Norwitz#ifdef Py_USING_MEMORY_DEBUGGER 1900cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters/* Make this function last so gcc won't inline it since the definition is 1901cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters * after the reference. 1902cf79aace07a57d480605f4a5aa8b9ca68567792eTim Peters */ 19037eb3c9196da5be52a670d6d8dd24939a3c27b594Neal Norwitzint 19047eb3c9196da5be52a670d6d8dd24939a3c27b594Neal NorwitzPy_ADDRESS_IN_RANGE(void *P, poolp pool) 19057eb3c9196da5be52a670d6d8dd24939a3c27b594Neal Norwitz{ 19065a72e76b6938941547dd25f9198db7d17fa36960Antoine Pitrou uint arenaindex_temp = pool->arenaindex; 19075a72e76b6938941547dd25f9198db7d17fa36960Antoine Pitrou 19085a72e76b6938941547dd25f9198db7d17fa36960Antoine Pitrou return arenaindex_temp < maxarenas && 19095a72e76b6938941547dd25f9198db7d17fa36960Antoine Pitrou (uptr)P - arenas[arenaindex_temp].address < (uptr)ARENA_SIZE && 19105a72e76b6938941547dd25f9198db7d17fa36960Antoine Pitrou arenas[arenaindex_temp].address != 0; 19117eb3c9196da5be52a670d6d8dd24939a3c27b594Neal Norwitz} 19127eb3c9196da5be52a670d6d8dd24939a3c27b594Neal Norwitz#endif 1913