Tim Peters | 1221c0a | 2002-03-23 00:20:15 +0000 | [diff] [blame^] | 1 | #include "Python.h" |
| 2 | |
| 3 | #ifdef WITH_PYMALLOC |
| 4 | |
Neil Schemenauer | a35c688 | 2001-02-27 04:45:05 +0000 | [diff] [blame] | 5 | /* An object allocator for Python. |
| 6 | |
| 7 | Here is an introduction to the layers of the Python memory architecture, |
| 8 | showing where the object allocator is actually used (layer +2), It is |
| 9 | called for every object allocation and deallocation (PyObject_New/Del), |
| 10 | unless the object-specific allocators implement a proprietary allocation |
| 11 | scheme (ex.: ints use a simple free list). This is also the place where |
| 12 | the cyclic garbage collector operates selectively on container objects. |
| 13 | |
| 14 | |
| 15 | Object-specific allocators |
| 16 | _____ ______ ______ ________ |
| 17 | [ int ] [ dict ] [ list ] ... [ string ] Python core | |
| 18 | +3 | <----- Object-specific memory -----> | <-- Non-object memory --> | |
| 19 | _______________________________ | | |
| 20 | [ Python's object allocator ] | | |
| 21 | +2 | ####### Object memory ####### | <------ Internal buffers ------> | |
| 22 | ______________________________________________________________ | |
| 23 | [ Python's raw memory allocator (PyMem_ API) ] | |
| 24 | +1 | <----- Python memory (under PyMem manager's control) ------> | | |
| 25 | __________________________________________________________________ |
| 26 | [ Underlying general-purpose allocator (ex: C library malloc) ] |
| 27 | 0 | <------ Virtual memory allocated for the python process -------> | |
| 28 | |
| 29 | ========================================================================= |
| 30 | _______________________________________________________________________ |
| 31 | [ OS-specific Virtual Memory Manager (VMM) ] |
| 32 | -1 | <--- Kernel dynamic storage allocation & management (page-based) ---> | |
| 33 | __________________________________ __________________________________ |
| 34 | [ ] [ ] |
| 35 | -2 | <-- Physical memory: ROM/RAM --> | | <-- Secondary storage (swap) --> | |
| 36 | |
| 37 | */ |
| 38 | /*==========================================================================*/ |
| 39 | |
| 40 | /* A fast, special-purpose memory allocator for small blocks, to be used |
| 41 | on top of a general-purpose malloc -- heavily based on previous art. */ |
| 42 | |
| 43 | /* Vladimir Marangozov -- August 2000 */ |
| 44 | |
| 45 | /* |
| 46 | * "Memory management is where the rubber meets the road -- if we do the wrong |
| 47 | * thing at any level, the results will not be good. And if we don't make the |
| 48 | * levels work well together, we are in serious trouble." (1) |
| 49 | * |
| 50 | * (1) Paul R. Wilson, Mark S. Johnstone, Michael Neely, and David Boles, |
| 51 | * "Dynamic Storage Allocation: A Survey and Critical Review", |
| 52 | * in Proc. 1995 Int'l. Workshop on Memory Management, September 1995. |
| 53 | */ |
| 54 | |
| 55 | /* #undef WITH_MEMORY_LIMITS */ /* disable mem limit checks */ |
Neil Schemenauer | a35c688 | 2001-02-27 04:45:05 +0000 | [diff] [blame] | 56 | |
| 57 | /*==========================================================================*/ |
| 58 | |
| 59 | /* |
Neil Schemenauer | a35c688 | 2001-02-27 04:45:05 +0000 | [diff] [blame] | 60 | * Allocation strategy abstract: |
| 61 | * |
| 62 | * For small requests, the allocator sub-allocates <Big> blocks of memory. |
| 63 | * Requests greater than 256 bytes are routed to the system's allocator. |
| 64 | * |
| 65 | * Small requests are grouped in size classes spaced 8 bytes apart, due |
| 66 | * to the required valid alignment of the returned address. Requests of |
| 67 | * a particular size are serviced from memory pools of 4K (one VMM page). |
| 68 | * Pools are fragmented on demand and contain free lists of blocks of one |
| 69 | * particular size class. In other words, there is a fixed-size allocator |
| 70 | * for each size class. Free pools are shared by the different allocators |
| 71 | * thus minimizing the space reserved for a particular size class. |
| 72 | * |
| 73 | * This allocation strategy is a variant of what is known as "simple |
| 74 | * segregated storage based on array of free lists". The main drawback of |
| 75 | * simple segregated storage is that we might end up with lot of reserved |
| 76 | * memory for the different free lists, which degenerate in time. To avoid |
| 77 | * this, we partition each free list in pools and we share dynamically the |
| 78 | * reserved space between all free lists. This technique is quite efficient |
| 79 | * for memory intensive programs which allocate mainly small-sized blocks. |
| 80 | * |
| 81 | * For small requests we have the following table: |
| 82 | * |
| 83 | * Request in bytes Size of allocated block Size class idx |
| 84 | * ---------------------------------------------------------------- |
| 85 | * 1-8 8 0 |
| 86 | * 9-16 16 1 |
| 87 | * 17-24 24 2 |
| 88 | * 25-32 32 3 |
| 89 | * 33-40 40 4 |
| 90 | * 41-48 48 5 |
| 91 | * 49-56 56 6 |
| 92 | * 57-64 64 7 |
| 93 | * 65-72 72 8 |
| 94 | * ... ... ... |
| 95 | * 241-248 248 30 |
| 96 | * 249-256 256 31 |
| 97 | * |
| 98 | * 0, 257 and up: routed to the underlying allocator. |
| 99 | */ |
| 100 | |
| 101 | /*==========================================================================*/ |
| 102 | |
| 103 | /* |
| 104 | * -- Main tunable settings section -- |
| 105 | */ |
| 106 | |
| 107 | /* |
| 108 | * Alignment of addresses returned to the user. 8-bytes alignment works |
| 109 | * on most current architectures (with 32-bit or 64-bit address busses). |
| 110 | * The alignment value is also used for grouping small requests in size |
| 111 | * classes spaced ALIGNMENT bytes apart. |
| 112 | * |
| 113 | * You shouldn't change this unless you know what you are doing. |
| 114 | */ |
| 115 | |
| 116 | #define ALIGNMENT 8 /* must be 2^N */ |
| 117 | #define ALIGNMENT_SHIFT 3 |
| 118 | #define ALIGNMENT_MASK (ALIGNMENT - 1) |
| 119 | |
| 120 | /* |
| 121 | * Max size threshold below which malloc requests are considered to be |
| 122 | * small enough in order to use preallocated memory pools. You can tune |
| 123 | * this value according to your application behaviour and memory needs. |
| 124 | * |
| 125 | * The following invariants must hold: |
| 126 | * 1) ALIGNMENT <= SMALL_REQUEST_THRESHOLD <= 256 |
| 127 | * 2) SMALL_REQUEST_THRESHOLD == N * ALIGNMENT |
| 128 | * |
| 129 | * Although not required, for better performance and space efficiency, |
| 130 | * it is recommended that SMALL_REQUEST_THRESHOLD is set to a power of 2. |
| 131 | */ |
| 132 | |
| 133 | /* |
| 134 | * For Python compiled on systems with 32 bit pointers and integers, |
| 135 | * a value of 64 (= 8 * 8) is a reasonable speed/space tradeoff for |
| 136 | * the object allocator. To adjust automatically this threshold for |
| 137 | * systems with 64 bit pointers, we make this setting depend on a |
| 138 | * Python-specific slot size unit = sizeof(long) + sizeof(void *), |
| 139 | * which is expected to be 8, 12 or 16 bytes. |
| 140 | */ |
| 141 | |
| 142 | #define _PYOBJECT_THRESHOLD ((SIZEOF_LONG + SIZEOF_VOID_P) * ALIGNMENT) |
| 143 | |
| 144 | #define SMALL_REQUEST_THRESHOLD _PYOBJECT_THRESHOLD /* must be N * ALIGNMENT */ |
| 145 | |
| 146 | #define NB_SMALL_SIZE_CLASSES (SMALL_REQUEST_THRESHOLD / ALIGNMENT) |
| 147 | |
| 148 | /* |
| 149 | * The system's VMM page size can be obtained on most unices with a |
| 150 | * getpagesize() call or deduced from various header files. To make |
| 151 | * things simpler, we assume that it is 4K, which is OK for most systems. |
| 152 | * It is probably better if this is the native page size, but it doesn't |
| 153 | * have to be. |
| 154 | */ |
| 155 | |
| 156 | #define SYSTEM_PAGE_SIZE (4 * 1024) |
| 157 | #define SYSTEM_PAGE_SIZE_MASK (SYSTEM_PAGE_SIZE - 1) |
| 158 | |
| 159 | /* |
| 160 | * Maximum amount of memory managed by the allocator for small requests. |
| 161 | */ |
| 162 | |
| 163 | #ifdef WITH_MEMORY_LIMITS |
| 164 | #ifndef SMALL_MEMORY_LIMIT |
| 165 | #define SMALL_MEMORY_LIMIT (64 * 1024 * 1024) /* 64 MB -- more? */ |
| 166 | #endif |
| 167 | #endif |
| 168 | |
| 169 | /* |
| 170 | * The allocator sub-allocates <Big> blocks of memory (called arenas) aligned |
| 171 | * on a page boundary. This is a reserved virtual address space for the |
| 172 | * current process (obtained through a malloc call). In no way this means |
| 173 | * that the memory arenas will be used entirely. A malloc(<Big>) is usually |
| 174 | * an address range reservation for <Big> bytes, unless all pages within this |
| 175 | * space are referenced subsequently. So malloc'ing big blocks and not using |
| 176 | * them does not mean "wasting memory". It's an addressable range wastage... |
| 177 | * |
| 178 | * Therefore, allocating arenas with malloc is not optimal, because there is |
| 179 | * some address space wastage, but this is the most portable way to request |
| 180 | * memory from the system accross various platforms. |
| 181 | */ |
| 182 | |
| 183 | #define ARENA_SIZE (256 * 1024 - SYSTEM_PAGE_SIZE) /* 256k - 1p */ |
| 184 | |
| 185 | #ifdef WITH_MEMORY_LIMITS |
| 186 | #define MAX_ARENAS (SMALL_MEMORY_LIMIT / ARENA_SIZE) |
| 187 | #endif |
| 188 | |
| 189 | /* |
| 190 | * Size of the pools used for small blocks. Should be a power of 2, |
| 191 | * between 1K and SYSTEM_PAGE_SIZE, that is: 1k, 2k, 4k, eventually 8k. |
| 192 | */ |
| 193 | |
| 194 | #define POOL_SIZE SYSTEM_PAGE_SIZE /* must be 2^N */ |
| 195 | #define POOL_SIZE_MASK SYSTEM_PAGE_SIZE_MASK |
| 196 | #define POOL_MAGIC 0x74D3A651 /* authentication id */ |
| 197 | |
| 198 | #define ARENA_NB_POOLS (ARENA_SIZE / POOL_SIZE) |
| 199 | #define ARENA_NB_PAGES (ARENA_SIZE / SYSTEM_PAGE_SIZE) |
| 200 | |
| 201 | /* |
| 202 | * -- End of tunable settings section -- |
| 203 | */ |
| 204 | |
| 205 | /*==========================================================================*/ |
| 206 | |
| 207 | /* |
| 208 | * Locking |
| 209 | * |
| 210 | * To reduce lock contention, it would probably be better to refine the |
| 211 | * crude function locking with per size class locking. I'm not positive |
| 212 | * however, whether it's worth switching to such locking policy because |
| 213 | * of the performance penalty it might introduce. |
| 214 | * |
| 215 | * The following macros describe the simplest (should also be the fastest) |
| 216 | * lock object on a particular platform and the init/fini/lock/unlock |
| 217 | * operations on it. The locks defined here are not expected to be recursive |
| 218 | * because it is assumed that they will always be called in the order: |
| 219 | * INIT, [LOCK, UNLOCK]*, FINI. |
| 220 | */ |
| 221 | |
| 222 | /* |
| 223 | * Python's threads are serialized, so object malloc locking is disabled. |
| 224 | */ |
| 225 | #define SIMPLELOCK_DECL(lock) /* simple lock declaration */ |
| 226 | #define SIMPLELOCK_INIT(lock) /* allocate (if needed) and initialize */ |
| 227 | #define SIMPLELOCK_FINI(lock) /* free/destroy an existing lock */ |
| 228 | #define SIMPLELOCK_LOCK(lock) /* acquire released lock */ |
| 229 | #define SIMPLELOCK_UNLOCK(lock) /* release acquired lock */ |
| 230 | |
| 231 | /* |
| 232 | * Basic types |
| 233 | * I don't care if these are defined in <sys/types.h> or elsewhere. Axiom. |
| 234 | */ |
| 235 | |
| 236 | #undef uchar |
| 237 | #define uchar unsigned char /* assuming == 8 bits */ |
| 238 | |
| 239 | #undef ushort |
| 240 | #define ushort unsigned short /* assuming >= 16 bits */ |
| 241 | |
| 242 | #undef uint |
| 243 | #define uint unsigned int /* assuming >= 16 bits */ |
| 244 | |
| 245 | #undef ulong |
| 246 | #define ulong unsigned long /* assuming >= 32 bits */ |
| 247 | |
| 248 | #undef off_t |
| 249 | #define off_t uint /* 16 bits <= off_t <= 64 bits */ |
| 250 | |
| 251 | /* When you say memory, my mind reasons in terms of (pointers to) blocks */ |
| 252 | typedef uchar block; |
| 253 | |
| 254 | /* Pool for small blocks */ |
| 255 | struct pool_header { |
Tim Peters | b233652 | 2001-03-11 18:36:13 +0000 | [diff] [blame] | 256 | union { block *_padding; |
Neil Schemenauer | a35c688 | 2001-02-27 04:45:05 +0000 | [diff] [blame] | 257 | uint count; } ref; /* number of allocated blocks */ |
| 258 | block *freeblock; /* pool's free list head */ |
| 259 | struct pool_header *nextpool; /* next pool of this size class */ |
| 260 | struct pool_header *prevpool; /* previous pool "" */ |
| 261 | struct pool_header *pooladdr; /* pool address (always aligned) */ |
| 262 | uint magic; /* pool magic number */ |
| 263 | uint szidx; /* block size class index */ |
| 264 | uint capacity; /* pool capacity in # of blocks */ |
| 265 | }; |
| 266 | |
| 267 | typedef struct pool_header *poolp; |
| 268 | |
| 269 | #undef ROUNDUP |
| 270 | #define ROUNDUP(x) (((x) + ALIGNMENT_MASK) & ~ALIGNMENT_MASK) |
| 271 | #define POOL_OVERHEAD ROUNDUP(sizeof(struct pool_header)) |
| 272 | |
| 273 | #define DUMMY_SIZE_IDX 0xffff /* size class of newly cached pools */ |
| 274 | |
| 275 | /*==========================================================================*/ |
| 276 | |
| 277 | /* |
| 278 | * This malloc lock |
| 279 | */ |
Tim Peters | b233652 | 2001-03-11 18:36:13 +0000 | [diff] [blame] | 280 | SIMPLELOCK_DECL(_malloc_lock); |
| 281 | #define LOCK() SIMPLELOCK_LOCK(_malloc_lock) |
| 282 | #define UNLOCK() SIMPLELOCK_UNLOCK(_malloc_lock) |
| 283 | #define LOCK_INIT() SIMPLELOCK_INIT(_malloc_lock) |
| 284 | #define LOCK_FINI() SIMPLELOCK_FINI(_malloc_lock) |
Neil Schemenauer | a35c688 | 2001-02-27 04:45:05 +0000 | [diff] [blame] | 285 | |
| 286 | /* |
| 287 | * Pool table -- doubly linked lists of partially used pools |
| 288 | */ |
| 289 | #define PTA(x) ((poolp )((uchar *)&(usedpools[2*(x)]) - 2*sizeof(block *))) |
| 290 | #define PT(x) PTA(x), PTA(x) |
| 291 | |
| 292 | static poolp usedpools[2 * ((NB_SMALL_SIZE_CLASSES + 7) / 8) * 8] = { |
| 293 | PT(0), PT(1), PT(2), PT(3), PT(4), PT(5), PT(6), PT(7) |
| 294 | #if NB_SMALL_SIZE_CLASSES > 8 |
| 295 | , PT(8), PT(9), PT(10), PT(11), PT(12), PT(13), PT(14), PT(15) |
| 296 | #if NB_SMALL_SIZE_CLASSES > 16 |
| 297 | , PT(16), PT(17), PT(18), PT(19), PT(20), PT(21), PT(22), PT(23) |
| 298 | #if NB_SMALL_SIZE_CLASSES > 24 |
| 299 | , PT(24), PT(25), PT(26), PT(27), PT(28), PT(29), PT(30), PT(31) |
| 300 | #if NB_SMALL_SIZE_CLASSES > 32 |
| 301 | , PT(32), PT(33), PT(34), PT(35), PT(36), PT(37), PT(38), PT(39) |
| 302 | #if NB_SMALL_SIZE_CLASSES > 40 |
| 303 | , PT(40), PT(41), PT(42), PT(43), PT(44), PT(45), PT(46), PT(47) |
| 304 | #if NB_SMALL_SIZE_CLASSES > 48 |
| 305 | , PT(48), PT(49), PT(50), PT(51), PT(52), PT(53), PT(54), PT(55) |
| 306 | #if NB_SMALL_SIZE_CLASSES > 56 |
| 307 | , PT(56), PT(57), PT(58), PT(59), PT(60), PT(61), PT(62), PT(63) |
| 308 | #endif /* NB_SMALL_SIZE_CLASSES > 56 */ |
| 309 | #endif /* NB_SMALL_SIZE_CLASSES > 48 */ |
| 310 | #endif /* NB_SMALL_SIZE_CLASSES > 40 */ |
| 311 | #endif /* NB_SMALL_SIZE_CLASSES > 32 */ |
| 312 | #endif /* NB_SMALL_SIZE_CLASSES > 24 */ |
| 313 | #endif /* NB_SMALL_SIZE_CLASSES > 16 */ |
| 314 | #endif /* NB_SMALL_SIZE_CLASSES > 8 */ |
| 315 | }; |
| 316 | |
| 317 | /* |
| 318 | * Free (cached) pools |
| 319 | */ |
| 320 | static poolp freepools = NULL; /* free list for cached pools */ |
| 321 | |
| 322 | /* |
| 323 | * Arenas |
| 324 | */ |
| 325 | static uint arenacnt = 0; /* number of allocated arenas */ |
| 326 | static uint watermark = ARENA_NB_POOLS; /* number of pools allocated from |
| 327 | the current arena */ |
| 328 | static block *arenalist = NULL; /* list of allocated arenas */ |
| 329 | static block *arenabase = NULL; /* free space start address in |
| 330 | current arena */ |
| 331 | |
Neil Schemenauer | a35c688 | 2001-02-27 04:45:05 +0000 | [diff] [blame] | 332 | /*==========================================================================*/ |
| 333 | |
| 334 | /* malloc */ |
| 335 | |
| 336 | /* |
| 337 | * The basic blocks are ordered by decreasing execution frequency, |
| 338 | * which minimizes the number of jumps in the most common cases, |
| 339 | * improves branching prediction and instruction scheduling (small |
| 340 | * block allocations typically result in a couple of instructions). |
| 341 | * Unless the optimizer reorders everything, being too smart... |
| 342 | */ |
| 343 | |
| 344 | void * |
Neil Schemenauer | 25f3dc2 | 2002-03-18 21:06:21 +0000 | [diff] [blame] | 345 | _PyMalloc_Malloc(size_t nbytes) |
Neil Schemenauer | a35c688 | 2001-02-27 04:45:05 +0000 | [diff] [blame] | 346 | { |
| 347 | block *bp; |
| 348 | poolp pool; |
| 349 | poolp next; |
| 350 | uint size; |
| 351 | |
Neil Schemenauer | a35c688 | 2001-02-27 04:45:05 +0000 | [diff] [blame] | 352 | /* |
| 353 | * This implicitly redirects malloc(0) |
| 354 | */ |
| 355 | if ((nbytes - 1) < SMALL_REQUEST_THRESHOLD) { |
| 356 | LOCK(); |
| 357 | /* |
| 358 | * Most frequent paths first |
| 359 | */ |
| 360 | size = (uint )(nbytes - 1) >> ALIGNMENT_SHIFT; |
| 361 | pool = usedpools[size + size]; |
| 362 | if (pool != pool->nextpool) { |
| 363 | /* |
| 364 | * There is a used pool for this size class. |
| 365 | * Pick up the head block of its free list. |
| 366 | */ |
| 367 | ++pool->ref.count; |
| 368 | bp = pool->freeblock; |
| 369 | if ((pool->freeblock = *(block **)bp) != NULL) { |
| 370 | UNLOCK(); |
| 371 | return (void *)bp; |
| 372 | } |
| 373 | /* |
| 374 | * Reached the end of the free list, try to extend it |
| 375 | */ |
| 376 | if (pool->ref.count < pool->capacity) { |
| 377 | /* |
| 378 | * There is room for another block |
| 379 | */ |
| 380 | size++; |
| 381 | size <<= ALIGNMENT_SHIFT; /* block size */ |
| 382 | pool->freeblock = (block *)pool + \ |
| 383 | POOL_OVERHEAD + \ |
| 384 | pool->ref.count * size; |
| 385 | *(block **)(pool->freeblock) = NULL; |
| 386 | UNLOCK(); |
| 387 | return (void *)bp; |
| 388 | } |
| 389 | /* |
| 390 | * Pool is full, unlink from used pools |
| 391 | */ |
| 392 | next = pool->nextpool; |
| 393 | pool = pool->prevpool; |
| 394 | next->prevpool = pool; |
| 395 | pool->nextpool = next; |
| 396 | UNLOCK(); |
| 397 | return (void *)bp; |
| 398 | } |
| 399 | /* |
| 400 | * Try to get a cached free pool |
| 401 | */ |
| 402 | pool = freepools; |
| 403 | if (pool != NULL) { |
| 404 | /* |
| 405 | * Unlink from cached pools |
| 406 | */ |
| 407 | freepools = pool->nextpool; |
| 408 | init_pool: |
| 409 | /* |
| 410 | * Frontlink to used pools |
| 411 | */ |
| 412 | next = usedpools[size + size]; /* == prev */ |
| 413 | pool->nextpool = next; |
| 414 | pool->prevpool = next; |
| 415 | next->nextpool = pool; |
| 416 | next->prevpool = pool; |
| 417 | pool->ref.count = 1; |
| 418 | if (pool->szidx == size) { |
| 419 | /* |
| 420 | * Luckily, this pool last contained blocks |
| 421 | * of the same size class, so its header |
| 422 | * and free list are already initialized. |
| 423 | */ |
| 424 | bp = pool->freeblock; |
| 425 | pool->freeblock = *(block **)bp; |
| 426 | UNLOCK(); |
| 427 | return (void *)bp; |
| 428 | } |
| 429 | /* |
| 430 | * Initialize the pool header and free list |
| 431 | * then return the first block. |
| 432 | */ |
| 433 | pool->szidx = size; |
| 434 | size++; |
| 435 | size <<= ALIGNMENT_SHIFT; /* block size */ |
| 436 | bp = (block *)pool + POOL_OVERHEAD; |
| 437 | pool->freeblock = bp + size; |
| 438 | *(block **)(pool->freeblock) = NULL; |
| 439 | pool->capacity = (POOL_SIZE - POOL_OVERHEAD) / size; |
| 440 | UNLOCK(); |
| 441 | return (void *)bp; |
| 442 | } |
| 443 | /* |
| 444 | * Allocate new pool |
| 445 | */ |
| 446 | if (watermark < ARENA_NB_POOLS) { |
| 447 | /* commit malloc(POOL_SIZE) from the current arena */ |
| 448 | commit_pool: |
| 449 | watermark++; |
| 450 | pool = (poolp )arenabase; |
| 451 | arenabase += POOL_SIZE; |
| 452 | pool->pooladdr = pool; |
| 453 | pool->magic = (uint )POOL_MAGIC; |
| 454 | pool->szidx = DUMMY_SIZE_IDX; |
| 455 | goto init_pool; |
| 456 | } |
| 457 | /* |
| 458 | * Allocate new arena |
| 459 | */ |
| 460 | #ifdef WITH_MEMORY_LIMITS |
| 461 | if (!(arenacnt < MAX_ARENAS)) { |
| 462 | UNLOCK(); |
| 463 | goto redirect; |
| 464 | } |
| 465 | #endif |
| 466 | /* |
| 467 | * With malloc, we can't avoid loosing one page address space |
| 468 | * per arena due to the required alignment on page boundaries. |
| 469 | */ |
Neil Schemenauer | 25f3dc2 | 2002-03-18 21:06:21 +0000 | [diff] [blame] | 470 | bp = (block *)PyMem_MALLOC(ARENA_SIZE + SYSTEM_PAGE_SIZE); |
Neil Schemenauer | a35c688 | 2001-02-27 04:45:05 +0000 | [diff] [blame] | 471 | if (bp == NULL) { |
| 472 | UNLOCK(); |
| 473 | goto redirect; |
| 474 | } |
| 475 | /* |
| 476 | * Keep a reference in the list of allocated arenas. We might |
| 477 | * want to release (some of) them in the future. The first |
| 478 | * word is never used, no matter whether the returned address |
| 479 | * is page-aligned or not, so we safely store a pointer in it. |
| 480 | */ |
| 481 | *(block **)bp = arenalist; |
| 482 | arenalist = bp; |
| 483 | arenacnt++; |
| 484 | watermark = 0; |
| 485 | /* Page-round up */ |
| 486 | arenabase = bp + (SYSTEM_PAGE_SIZE - |
| 487 | ((off_t )bp & SYSTEM_PAGE_SIZE_MASK)); |
| 488 | goto commit_pool; |
| 489 | } |
| 490 | |
| 491 | /* The small block allocator ends here. */ |
| 492 | |
| 493 | redirect: |
| 494 | |
| 495 | /* |
| 496 | * Redirect the original request to the underlying (libc) allocator. |
| 497 | * We jump here on bigger requests, on error in the code above (as a |
| 498 | * last chance to serve the request) or when the max memory limit |
| 499 | * has been reached. |
| 500 | */ |
Neil Schemenauer | 25f3dc2 | 2002-03-18 21:06:21 +0000 | [diff] [blame] | 501 | return (void *)PyMem_MALLOC(nbytes); |
Neil Schemenauer | a35c688 | 2001-02-27 04:45:05 +0000 | [diff] [blame] | 502 | } |
| 503 | |
| 504 | /* free */ |
| 505 | |
| 506 | void |
Neil Schemenauer | 25f3dc2 | 2002-03-18 21:06:21 +0000 | [diff] [blame] | 507 | _PyMalloc_Free(void *p) |
Neil Schemenauer | a35c688 | 2001-02-27 04:45:05 +0000 | [diff] [blame] | 508 | { |
| 509 | poolp pool; |
| 510 | poolp next, prev; |
| 511 | uint size; |
| 512 | off_t offset; |
| 513 | |
Neil Schemenauer | a35c688 | 2001-02-27 04:45:05 +0000 | [diff] [blame] | 514 | if (p == NULL) /* free(NULL) has no effect */ |
| 515 | return; |
| 516 | |
| 517 | offset = (off_t )p & POOL_SIZE_MASK; |
| 518 | pool = (poolp )((block *)p - offset); |
| 519 | if (pool->pooladdr != pool || pool->magic != (uint )POOL_MAGIC) { |
Neil Schemenauer | 25f3dc2 | 2002-03-18 21:06:21 +0000 | [diff] [blame] | 520 | PyMem_FREE(p); |
Neil Schemenauer | a35c688 | 2001-02-27 04:45:05 +0000 | [diff] [blame] | 521 | return; |
| 522 | } |
| 523 | |
| 524 | LOCK(); |
| 525 | /* |
| 526 | * At this point, the pool is not empty |
| 527 | */ |
| 528 | if ((*(block **)p = pool->freeblock) == NULL) { |
| 529 | /* |
| 530 | * Pool was full |
| 531 | */ |
| 532 | pool->freeblock = (block *)p; |
| 533 | --pool->ref.count; |
| 534 | /* |
| 535 | * Frontlink to used pools |
| 536 | * This mimics LRU pool usage for new allocations and |
| 537 | * targets optimal filling when several pools contain |
| 538 | * blocks of the same size class. |
| 539 | */ |
| 540 | size = pool->szidx; |
| 541 | next = usedpools[size + size]; |
| 542 | prev = next->prevpool; |
| 543 | pool->nextpool = next; |
| 544 | pool->prevpool = prev; |
| 545 | next->prevpool = pool; |
| 546 | prev->nextpool = pool; |
| 547 | UNLOCK(); |
| 548 | return; |
| 549 | } |
| 550 | /* |
| 551 | * Pool was not full |
| 552 | */ |
| 553 | pool->freeblock = (block *)p; |
| 554 | if (--pool->ref.count != 0) { |
| 555 | UNLOCK(); |
| 556 | return; |
| 557 | } |
| 558 | /* |
| 559 | * Pool is now empty, unlink from used pools |
| 560 | */ |
| 561 | next = pool->nextpool; |
| 562 | prev = pool->prevpool; |
| 563 | next->prevpool = prev; |
| 564 | prev->nextpool = next; |
| 565 | /* |
| 566 | * Frontlink to free pools |
| 567 | * This ensures that previously freed pools will be allocated |
| 568 | * later (being not referenced, they are perhaps paged out). |
| 569 | */ |
| 570 | pool->nextpool = freepools; |
| 571 | freepools = pool; |
| 572 | UNLOCK(); |
| 573 | return; |
| 574 | } |
| 575 | |
| 576 | /* realloc */ |
| 577 | |
| 578 | void * |
Neil Schemenauer | 25f3dc2 | 2002-03-18 21:06:21 +0000 | [diff] [blame] | 579 | _PyMalloc_Realloc(void *p, size_t nbytes) |
Neil Schemenauer | a35c688 | 2001-02-27 04:45:05 +0000 | [diff] [blame] | 580 | { |
| 581 | block *bp; |
| 582 | poolp pool; |
| 583 | uint size; |
| 584 | |
Neil Schemenauer | a35c688 | 2001-02-27 04:45:05 +0000 | [diff] [blame] | 585 | if (p == NULL) |
Neil Schemenauer | 25f3dc2 | 2002-03-18 21:06:21 +0000 | [diff] [blame] | 586 | return _PyMalloc_Malloc(nbytes); |
Neil Schemenauer | a35c688 | 2001-02-27 04:45:05 +0000 | [diff] [blame] | 587 | |
| 588 | /* realloc(p, 0) on big blocks is redirected. */ |
| 589 | pool = (poolp )((block *)p - ((off_t )p & POOL_SIZE_MASK)); |
| 590 | if (pool->pooladdr != pool || pool->magic != (uint )POOL_MAGIC) { |
| 591 | /* We haven't allocated this block */ |
| 592 | if (!(nbytes > SMALL_REQUEST_THRESHOLD) && nbytes) { |
| 593 | /* small request */ |
| 594 | size = nbytes; |
| 595 | goto malloc_copy_free; |
| 596 | } |
Neil Schemenauer | 25f3dc2 | 2002-03-18 21:06:21 +0000 | [diff] [blame] | 597 | bp = (block *)PyMem_REALLOC(p, nbytes); |
Neil Schemenauer | a35c688 | 2001-02-27 04:45:05 +0000 | [diff] [blame] | 598 | } |
| 599 | else { |
| 600 | /* We're in charge of this block */ |
| 601 | size = (pool->szidx + 1) << ALIGNMENT_SHIFT; /* block size */ |
| 602 | if (size >= nbytes) { |
| 603 | /* Don't bother if a smaller size was requested |
| 604 | except for realloc(p, 0) == free(p), ret NULL */ |
| 605 | if (nbytes == 0) { |
Neil Schemenauer | 25f3dc2 | 2002-03-18 21:06:21 +0000 | [diff] [blame] | 606 | _PyMalloc_Free(p); |
Neil Schemenauer | a35c688 | 2001-02-27 04:45:05 +0000 | [diff] [blame] | 607 | bp = NULL; |
| 608 | } |
| 609 | else |
| 610 | bp = (block *)p; |
| 611 | } |
| 612 | else { |
| 613 | |
| 614 | malloc_copy_free: |
| 615 | |
Neil Schemenauer | 25f3dc2 | 2002-03-18 21:06:21 +0000 | [diff] [blame] | 616 | bp = (block *)_PyMalloc_Malloc(nbytes); |
Neil Schemenauer | a35c688 | 2001-02-27 04:45:05 +0000 | [diff] [blame] | 617 | if (bp != NULL) { |
| 618 | memcpy(bp, p, size); |
Neil Schemenauer | 25f3dc2 | 2002-03-18 21:06:21 +0000 | [diff] [blame] | 619 | _PyMalloc_Free(p); |
Neil Schemenauer | a35c688 | 2001-02-27 04:45:05 +0000 | [diff] [blame] | 620 | } |
| 621 | } |
| 622 | } |
| 623 | return (void *)bp; |
| 624 | } |
| 625 | |
| 626 | /* calloc */ |
| 627 | |
| 628 | /* -- unused -- |
| 629 | void * |
Neil Schemenauer | 25f3dc2 | 2002-03-18 21:06:21 +0000 | [diff] [blame] | 630 | _PyMalloc_Calloc(size_t nbel, size_t elsz) |
Neil Schemenauer | a35c688 | 2001-02-27 04:45:05 +0000 | [diff] [blame] | 631 | { |
| 632 | void *p; |
| 633 | size_t nbytes; |
| 634 | |
Neil Schemenauer | a35c688 | 2001-02-27 04:45:05 +0000 | [diff] [blame] | 635 | nbytes = nbel * elsz; |
Neil Schemenauer | 25f3dc2 | 2002-03-18 21:06:21 +0000 | [diff] [blame] | 636 | p = _PyMalloc_Malloc(nbytes); |
Neil Schemenauer | a35c688 | 2001-02-27 04:45:05 +0000 | [diff] [blame] | 637 | if (p != NULL) |
| 638 | memset(p, 0, nbytes); |
| 639 | return p; |
| 640 | } |
| 641 | */ |
| 642 | |
Tim Peters | 1221c0a | 2002-03-23 00:20:15 +0000 | [diff] [blame^] | 643 | #else /* ! WITH_PYMALLOC */ |
| 644 | void |
| 645 | *_PyMalloc_Malloc(size_t n) |
| 646 | { |
| 647 | return PyMem_MALLOC(n); |
| 648 | } |
| 649 | |
| 650 | void |
| 651 | *_PyMalloc_Realloc(void *p, size_t n) |
| 652 | { |
| 653 | return PyMem_REALLOC(p, n); |
| 654 | } |
| 655 | |
| 656 | void |
| 657 | _PyMalloc_Free(void *p) |
| 658 | { |
| 659 | PyMem_FREE(p); |
| 660 | } |
| 661 | #endif /* WITH_PYMALLOC */ |
| 662 | |
| 663 | PyObject |
| 664 | *_PyMalloc_New(PyTypeObject *tp) |
| 665 | { |
| 666 | PyObject *op; |
| 667 | op = (PyObject *) _PyMalloc_MALLOC(_PyObject_SIZE(tp)); |
| 668 | if (op == NULL) |
| 669 | return PyErr_NoMemory(); |
| 670 | return PyObject_INIT(op, tp); |
| 671 | } |
| 672 | |
| 673 | PyVarObject * |
| 674 | _PyMalloc_NewVar(PyTypeObject *tp, int nitems) |
| 675 | { |
| 676 | PyVarObject *op; |
| 677 | const size_t size = _PyObject_VAR_SIZE(tp, nitems); |
| 678 | op = (PyVarObject *) _PyMalloc_MALLOC(size); |
| 679 | if (op == NULL) |
| 680 | return (PyVarObject *)PyErr_NoMemory(); |
| 681 | return PyObject_INIT_VAR(op, tp, nitems); |
| 682 | } |
| 683 | |
| 684 | void |
| 685 | _PyMalloc_Del(PyObject *op) |
| 686 | { |
| 687 | _PyMalloc_FREE(op); |
| 688 | } |