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