/* An object allocator for Python. Here is an introduction to the layers of the Python memory architecture, showing where the object allocator is actually used (layer +2), It is called for every object allocation and deallocation (PyObject_New/Del), unless the object-specific allocators implement a proprietary allocation scheme (ex.: ints use a simple free list). This is also the place where the cyclic garbage collector operates selectively on container objects. Object-specific allocators _____ ______ ______ ________ [ int ] [ dict ] [ list ] ... [ string ] Python core | +3 | <----- Object-specific memory -----> | <-- Non-object memory --> | _______________________________ | | [ Python's object allocator ] | | +2 | ####### Object memory ####### | <------ Internal buffers ------> | ______________________________________________________________ | [ Python's raw memory allocator (PyMem_ API) ] | +1 | <----- Python memory (under PyMem manager's control) ------> | | __________________________________________________________________ [ Underlying general-purpose allocator (ex: C library malloc) ] 0 | <------ Virtual memory allocated for the python process -------> | ========================================================================= _______________________________________________________________________ [ OS-specific Virtual Memory Manager (VMM) ] -1 | <--- Kernel dynamic storage allocation & management (page-based) ---> | __________________________________ __________________________________ [ ] [ ] -2 | <-- Physical memory: ROM/RAM --> | | <-- Secondary storage (swap) --> | */ /*==========================================================================*/ /* A fast, special-purpose memory allocator for small blocks, to be used on top of a general-purpose malloc -- heavily based on previous art. */ /* Vladimir Marangozov -- August 2000 */ /* * "Memory management is where the rubber meets the road -- if we do the wrong * thing at any level, the results will not be good. And if we don't make the * levels work well together, we are in serious trouble." (1) * * (1) Paul R. Wilson, Mark S. Johnstone, Michael Neely, and David Boles, * "Dynamic Storage Allocation: A Survey and Critical Review", * in Proc. 1995 Int'l. Workshop on Memory Management, September 1995. */ /* #undef WITH_MEMORY_LIMITS */ /* disable mem limit checks */ #define WITH_MALLOC_HOOKS /* for profiling & debugging */ /*==========================================================================*/ /* * Public functions exported by this allocator. * * -- Define and use these names in your code to obtain or release memory -- */ #define _THIS_MALLOC PyCore_OBJECT_MALLOC_FUNC #define _THIS_CALLOC /* unused */ #define _THIS_REALLOC PyCore_OBJECT_REALLOC_FUNC #define _THIS_FREE PyCore_OBJECT_FREE_FUNC /* * Underlying allocator's functions called by this allocator. * The underlying allocator is usually the one which comes with libc. * * -- Don't use these functions in your code (to avoid mixing allocators) -- * * Redefine these __only__ if you are using a 3rd party general purpose * allocator which exports functions with names _other_ than the standard * malloc, calloc, realloc, free. */ #define _SYSTEM_MALLOC PyCore_MALLOC_FUNC #define _SYSTEM_CALLOC /* unused */ #define _SYSTEM_REALLOC PyCore_REALLOC_FUNC #define _SYSTEM_FREE PyCore_FREE_FUNC /* * If malloc hooks are needed, names of the hooks' set & fetch * functions exported by this allocator. */ #ifdef WITH_MALLOC_HOOKS #define _SET_HOOKS _PyCore_ObjectMalloc_SetHooks #define _FETCH_HOOKS _PyCore_ObjectMalloc_FetchHooks #endif /*==========================================================================*/ /* * Allocation strategy abstract: * * For small requests, the allocator sub-allocates blocks of memory. * Requests greater than 256 bytes are routed to the system's allocator. * * Small requests are grouped in size classes spaced 8 bytes apart, due * to the required valid alignment of the returned address. Requests of * a particular size are serviced from memory pools of 4K (one VMM page). * Pools are fragmented on demand and contain free lists of blocks of one * particular size class. In other words, there is a fixed-size allocator * for each size class. Free pools are shared by the different allocators * thus minimizing the space reserved for a particular size class. * * This allocation strategy is a variant of what is known as "simple * segregated storage based on array of free lists". The main drawback of * simple segregated storage is that we might end up with lot of reserved * memory for the different free lists, which degenerate in time. To avoid * this, we partition each free list in pools and we share dynamically the * reserved space between all free lists. This technique is quite efficient * for memory intensive programs which allocate mainly small-sized blocks. * * For small requests we have the following table: * * Request in bytes Size of allocated block Size class idx * ---------------------------------------------------------------- * 1-8 8 0 * 9-16 16 1 * 17-24 24 2 * 25-32 32 3 * 33-40 40 4 * 41-48 48 5 * 49-56 56 6 * 57-64 64 7 * 65-72 72 8 * ... ... ... * 241-248 248 30 * 249-256 256 31 * * 0, 257 and up: routed to the underlying allocator. */ /*==========================================================================*/ /* * -- Main tunable settings section -- */ /* * Alignment of addresses returned to the user. 8-bytes alignment works * on most current architectures (with 32-bit or 64-bit address busses). * The alignment value is also used for grouping small requests in size * classes spaced ALIGNMENT bytes apart. * * You shouldn't change this unless you know what you are doing. */ #define ALIGNMENT 8 /* must be 2^N */ #define ALIGNMENT_SHIFT 3 #define ALIGNMENT_MASK (ALIGNMENT - 1) /* * Max size threshold below which malloc requests are considered to be * small enough in order to use preallocated memory pools. You can tune * this value according to your application behaviour and memory needs. * * The following invariants must hold: * 1) ALIGNMENT <= SMALL_REQUEST_THRESHOLD <= 256 * 2) SMALL_REQUEST_THRESHOLD == N * ALIGNMENT * * Although not required, for better performance and space efficiency, * it is recommended that SMALL_REQUEST_THRESHOLD is set to a power of 2. */ /* * For Python compiled on systems with 32 bit pointers and integers, * a value of 64 (= 8 * 8) is a reasonable speed/space tradeoff for * the object allocator. To adjust automatically this threshold for * systems with 64 bit pointers, we make this setting depend on a * Python-specific slot size unit = sizeof(long) + sizeof(void *), * which is expected to be 8, 12 or 16 bytes. */ #define _PYOBJECT_THRESHOLD ((SIZEOF_LONG + SIZEOF_VOID_P) * ALIGNMENT) #define SMALL_REQUEST_THRESHOLD _PYOBJECT_THRESHOLD /* must be N * ALIGNMENT */ #define NB_SMALL_SIZE_CLASSES (SMALL_REQUEST_THRESHOLD / ALIGNMENT) /* * The system's VMM page size can be obtained on most unices with a * getpagesize() call or deduced from various header files. To make * things simpler, we assume that it is 4K, which is OK for most systems. * It is probably better if this is the native page size, but it doesn't * have to be. */ #define SYSTEM_PAGE_SIZE (4 * 1024) #define SYSTEM_PAGE_SIZE_MASK (SYSTEM_PAGE_SIZE - 1) /* * Maximum amount of memory managed by the allocator for small requests. */ #ifdef WITH_MEMORY_LIMITS #ifndef SMALL_MEMORY_LIMIT #define SMALL_MEMORY_LIMIT (64 * 1024 * 1024) /* 64 MB -- more? */ #endif #endif /* * The allocator sub-allocates blocks of memory (called arenas) aligned * on a page boundary. This is a reserved virtual address space for the * current process (obtained through a malloc call). In no way this means * that the memory arenas will be used entirely. A malloc() is usually * an address range reservation for bytes, unless all pages within this * space are referenced subsequently. So malloc'ing big blocks and not using * them does not mean "wasting memory". It's an addressable range wastage... * * Therefore, allocating arenas with malloc is not optimal, because there is * some address space wastage, but this is the most portable way to request * memory from the system accross various platforms. */ #define ARENA_SIZE (256 * 1024 - SYSTEM_PAGE_SIZE) /* 256k - 1p */ #ifdef WITH_MEMORY_LIMITS #define MAX_ARENAS (SMALL_MEMORY_LIMIT / ARENA_SIZE) #endif /* * Size of the pools used for small blocks. Should be a power of 2, * between 1K and SYSTEM_PAGE_SIZE, that is: 1k, 2k, 4k, eventually 8k. */ #define POOL_SIZE SYSTEM_PAGE_SIZE /* must be 2^N */ #define POOL_SIZE_MASK SYSTEM_PAGE_SIZE_MASK #define POOL_MAGIC 0x74D3A651 /* authentication id */ #define ARENA_NB_POOLS (ARENA_SIZE / POOL_SIZE) #define ARENA_NB_PAGES (ARENA_SIZE / SYSTEM_PAGE_SIZE) /* * -- End of tunable settings section -- */ /*==========================================================================*/ /* * Locking * * To reduce lock contention, it would probably be better to refine the * crude function locking with per size class locking. I'm not positive * however, whether it's worth switching to such locking policy because * of the performance penalty it might introduce. * * The following macros describe the simplest (should also be the fastest) * lock object on a particular platform and the init/fini/lock/unlock * operations on it. The locks defined here are not expected to be recursive * because it is assumed that they will always be called in the order: * INIT, [LOCK, UNLOCK]*, FINI. */ /* * Python's threads are serialized, so object malloc locking is disabled. */ #define SIMPLELOCK_DECL(lock) /* simple lock declaration */ #define SIMPLELOCK_INIT(lock) /* allocate (if needed) and initialize */ #define SIMPLELOCK_FINI(lock) /* free/destroy an existing lock */ #define SIMPLELOCK_LOCK(lock) /* acquire released lock */ #define SIMPLELOCK_UNLOCK(lock) /* release acquired lock */ /* * Basic types * I don't care if these are defined in or elsewhere. Axiom. */ #undef uchar #define uchar unsigned char /* assuming == 8 bits */ #undef ushort #define ushort unsigned short /* assuming >= 16 bits */ #undef uint #define uint unsigned int /* assuming >= 16 bits */ #undef ulong #define ulong unsigned long /* assuming >= 32 bits */ #undef off_t #define off_t uint /* 16 bits <= off_t <= 64 bits */ /* When you say memory, my mind reasons in terms of (pointers to) blocks */ typedef uchar block; /* Pool for small blocks */ struct pool_header { union { block *_padding; uint count; } ref; /* number of allocated blocks */ block *freeblock; /* pool's free list head */ struct pool_header *nextpool; /* next pool of this size class */ struct pool_header *prevpool; /* previous pool "" */ struct pool_header *pooladdr; /* pool address (always aligned) */ uint magic; /* pool magic number */ uint szidx; /* block size class index */ uint capacity; /* pool capacity in # of blocks */ }; typedef struct pool_header *poolp; #undef ROUNDUP #define ROUNDUP(x) (((x) + ALIGNMENT_MASK) & ~ALIGNMENT_MASK) #define POOL_OVERHEAD ROUNDUP(sizeof(struct pool_header)) #define DUMMY_SIZE_IDX 0xffff /* size class of newly cached pools */ /*==========================================================================*/ /* * This malloc lock */ SIMPLELOCK_DECL(_malloc_lock); #define LOCK() SIMPLELOCK_LOCK(_malloc_lock) #define UNLOCK() SIMPLELOCK_UNLOCK(_malloc_lock) #define LOCK_INIT() SIMPLELOCK_INIT(_malloc_lock) #define LOCK_FINI() SIMPLELOCK_FINI(_malloc_lock) /* * Pool table -- doubly linked lists of partially used pools */ #define PTA(x) ((poolp )((uchar *)&(usedpools[2*(x)]) - 2*sizeof(block *))) #define PT(x) PTA(x), PTA(x) static poolp usedpools[2 * ((NB_SMALL_SIZE_CLASSES + 7) / 8) * 8] = { PT(0), PT(1), PT(2), PT(3), PT(4), PT(5), PT(6), PT(7) #if NB_SMALL_SIZE_CLASSES > 8 , PT(8), PT(9), PT(10), PT(11), PT(12), PT(13), PT(14), PT(15) #if NB_SMALL_SIZE_CLASSES > 16 , PT(16), PT(17), PT(18), PT(19), PT(20), PT(21), PT(22), PT(23) #if NB_SMALL_SIZE_CLASSES > 24 , PT(24), PT(25), PT(26), PT(27), PT(28), PT(29), PT(30), PT(31) #if NB_SMALL_SIZE_CLASSES > 32 , PT(32), PT(33), PT(34), PT(35), PT(36), PT(37), PT(38), PT(39) #if NB_SMALL_SIZE_CLASSES > 40 , PT(40), PT(41), PT(42), PT(43), PT(44), PT(45), PT(46), PT(47) #if NB_SMALL_SIZE_CLASSES > 48 , PT(48), PT(49), PT(50), PT(51), PT(52), PT(53), PT(54), PT(55) #if NB_SMALL_SIZE_CLASSES > 56 , PT(56), PT(57), PT(58), PT(59), PT(60), PT(61), PT(62), PT(63) #endif /* NB_SMALL_SIZE_CLASSES > 56 */ #endif /* NB_SMALL_SIZE_CLASSES > 48 */ #endif /* NB_SMALL_SIZE_CLASSES > 40 */ #endif /* NB_SMALL_SIZE_CLASSES > 32 */ #endif /* NB_SMALL_SIZE_CLASSES > 24 */ #endif /* NB_SMALL_SIZE_CLASSES > 16 */ #endif /* NB_SMALL_SIZE_CLASSES > 8 */ }; /* * Free (cached) pools */ static poolp freepools = NULL; /* free list for cached pools */ /* * Arenas */ static uint arenacnt = 0; /* number of allocated arenas */ static uint watermark = ARENA_NB_POOLS; /* number of pools allocated from the current arena */ static block *arenalist = NULL; /* list of allocated arenas */ static block *arenabase = NULL; /* free space start address in current arena */ /* * Hooks */ #ifdef WITH_MALLOC_HOOKS static void *(*malloc_hook)(size_t) = NULL; static void *(*calloc_hook)(size_t, size_t) = NULL; static void *(*realloc_hook)(void *, size_t) = NULL; static void (*free_hook)(void *) = NULL; #endif /* !WITH_MALLOC_HOOKS */ /*==========================================================================*/ /* malloc */ /* * The basic blocks are ordered by decreasing execution frequency, * which minimizes the number of jumps in the most common cases, * improves branching prediction and instruction scheduling (small * block allocations typically result in a couple of instructions). * Unless the optimizer reorders everything, being too smart... */ void * _THIS_MALLOC(size_t nbytes) { block *bp; poolp pool; poolp next; uint size; #ifdef WITH_MALLOC_HOOKS if (malloc_hook != NULL) return (*malloc_hook)(nbytes); #endif /* * This implicitly redirects malloc(0) */ if ((nbytes - 1) < SMALL_REQUEST_THRESHOLD) { LOCK(); /* * Most frequent paths first */ size = (uint )(nbytes - 1) >> ALIGNMENT_SHIFT; pool = usedpools[size + size]; if (pool != pool->nextpool) { /* * There is a used pool for this size class. * Pick up the head block of its free list. */ ++pool->ref.count; bp = pool->freeblock; if ((pool->freeblock = *(block **)bp) != NULL) { UNLOCK(); return (void *)bp; } /* * Reached the end of the free list, try to extend it */ if (pool->ref.count < pool->capacity) { /* * There is room for another block */ size++; size <<= ALIGNMENT_SHIFT; /* block size */ pool->freeblock = (block *)pool + \ POOL_OVERHEAD + \ pool->ref.count * size; *(block **)(pool->freeblock) = NULL; UNLOCK(); return (void *)bp; } /* * Pool is full, unlink from used pools */ next = pool->nextpool; pool = pool->prevpool; next->prevpool = pool; pool->nextpool = next; UNLOCK(); return (void *)bp; } /* * Try to get a cached free pool */ pool = freepools; if (pool != NULL) { /* * Unlink from cached pools */ freepools = pool->nextpool; init_pool: /* * Frontlink to used pools */ next = usedpools[size + size]; /* == prev */ pool->nextpool = next; pool->prevpool = next; next->nextpool = pool; next->prevpool = pool; pool->ref.count = 1; if (pool->szidx == size) { /* * Luckily, this pool last contained blocks * of the same size class, so its header * and free list are already initialized. */ bp = pool->freeblock; pool->freeblock = *(block **)bp; UNLOCK(); return (void *)bp; } /* * Initialize the pool header and free list * then return the first block. */ pool->szidx = size; size++; size <<= ALIGNMENT_SHIFT; /* block size */ bp = (block *)pool + POOL_OVERHEAD; pool->freeblock = bp + size; *(block **)(pool->freeblock) = NULL; pool->capacity = (POOL_SIZE - POOL_OVERHEAD) / size; UNLOCK(); return (void *)bp; } /* * Allocate new pool */ if (watermark < ARENA_NB_POOLS) { /* commit malloc(POOL_SIZE) from the current arena */ commit_pool: watermark++; pool = (poolp )arenabase; arenabase += POOL_SIZE; pool->pooladdr = pool; pool->magic = (uint )POOL_MAGIC; pool->szidx = DUMMY_SIZE_IDX; goto init_pool; } /* * Allocate new arena */ #ifdef WITH_MEMORY_LIMITS if (!(arenacnt < MAX_ARENAS)) { UNLOCK(); goto redirect; } #endif /* * With malloc, we can't avoid loosing one page address space * per arena due to the required alignment on page boundaries. */ bp = (block *)_SYSTEM_MALLOC(ARENA_SIZE + SYSTEM_PAGE_SIZE); if (bp == NULL) { UNLOCK(); goto redirect; } /* * Keep a reference in the list of allocated arenas. We might * want to release (some of) them in the future. The first * word is never used, no matter whether the returned address * is page-aligned or not, so we safely store a pointer in it. */ *(block **)bp = arenalist; arenalist = bp; arenacnt++; watermark = 0; /* Page-round up */ arenabase = bp + (SYSTEM_PAGE_SIZE - ((off_t )bp & SYSTEM_PAGE_SIZE_MASK)); goto commit_pool; } /* The small block allocator ends here. */ redirect: /* * Redirect the original request to the underlying (libc) allocator. * We jump here on bigger requests, on error in the code above (as a * last chance to serve the request) or when the max memory limit * has been reached. */ return (void *)_SYSTEM_MALLOC(nbytes); } /* free */ void _THIS_FREE(void *p) { poolp pool; poolp next, prev; uint size; off_t offset; #ifdef WITH_MALLOC_HOOKS if (free_hook != NULL) { (*free_hook)(p); return; } #endif if (p == NULL) /* free(NULL) has no effect */ return; offset = (off_t )p & POOL_SIZE_MASK; pool = (poolp )((block *)p - offset); if (pool->pooladdr != pool || pool->magic != (uint )POOL_MAGIC) { _SYSTEM_FREE(p); return; } LOCK(); /* * At this point, the pool is not empty */ if ((*(block **)p = pool->freeblock) == NULL) { /* * Pool was full */ pool->freeblock = (block *)p; --pool->ref.count; /* * Frontlink to used pools * This mimics LRU pool usage for new allocations and * targets optimal filling when several pools contain * blocks of the same size class. */ size = pool->szidx; next = usedpools[size + size]; prev = next->prevpool; pool->nextpool = next; pool->prevpool = prev; next->prevpool = pool; prev->nextpool = pool; UNLOCK(); return; } /* * Pool was not full */ pool->freeblock = (block *)p; if (--pool->ref.count != 0) { UNLOCK(); return; } /* * Pool is now empty, unlink from used pools */ next = pool->nextpool; prev = pool->prevpool; next->prevpool = prev; prev->nextpool = next; /* * Frontlink to free pools * This ensures that previously freed pools will be allocated * later (being not referenced, they are perhaps paged out). */ pool->nextpool = freepools; freepools = pool; UNLOCK(); return; } /* realloc */ void * _THIS_REALLOC(void *p, size_t nbytes) { block *bp; poolp pool; uint size; #ifdef WITH_MALLOC_HOOKS if (realloc_hook != NULL) return (*realloc_hook)(p, nbytes); #endif if (p == NULL) return _THIS_MALLOC(nbytes); /* realloc(p, 0) on big blocks is redirected. */ pool = (poolp )((block *)p - ((off_t )p & POOL_SIZE_MASK)); if (pool->pooladdr != pool || pool->magic != (uint )POOL_MAGIC) { /* We haven't allocated this block */ if (!(nbytes > SMALL_REQUEST_THRESHOLD) && nbytes) { /* small request */ size = nbytes; goto malloc_copy_free; } bp = (block *)_SYSTEM_REALLOC(p, nbytes); } else { /* We're in charge of this block */ size = (pool->szidx + 1) << ALIGNMENT_SHIFT; /* block size */ if (size >= nbytes) { /* Don't bother if a smaller size was requested except for realloc(p, 0) == free(p), ret NULL */ if (nbytes == 0) { _THIS_FREE(p); bp = NULL; } else bp = (block *)p; } else { malloc_copy_free: bp = (block *)_THIS_MALLOC(nbytes); if (bp != NULL) { memcpy(bp, p, size); _THIS_FREE(p); } } } return (void *)bp; } /* calloc */ /* -- unused -- void * _THIS_CALLOC(size_t nbel, size_t elsz) { void *p; size_t nbytes; #ifdef WITH_MALLOC_HOOKS if (calloc_hook != NULL) return (*calloc_hook)(nbel, elsz); #endif nbytes = nbel * elsz; p = _THIS_MALLOC(nbytes); if (p != NULL) memset(p, 0, nbytes); return p; } */ /*==========================================================================*/ /* * Hooks */ #ifdef WITH_MALLOC_HOOKS void _SET_HOOKS( void *(*malloc_func)(size_t), void *(*calloc_func)(size_t, size_t), void *(*realloc_func)(void *, size_t), void (*free_func)(void *) ) { LOCK(); malloc_hook = malloc_func; calloc_hook = calloc_func; realloc_hook = realloc_func; free_hook = free_func; UNLOCK(); } void _FETCH_HOOKS( void *(**malloc_funcp)(size_t), void *(**calloc_funcp)(size_t, size_t), void *(**realloc_funcp)(void *, size_t), void (**free_funcp)(void *) ) { LOCK(); *malloc_funcp = malloc_hook; *calloc_funcp = calloc_hook; *realloc_funcp = realloc_hook; *free_funcp = free_hook; UNLOCK(); } #endif /* !WITH_MALLOC_HOOKS */