1 #ifndef Py_INTERNAL_OBMALLOC_H 2 #define Py_INTERNAL_OBMALLOC_H 3 #ifdef __cplusplus 4 extern "C" { 5 #endif 6 7 #ifndef Py_BUILD_CORE 8 # error "this header requires Py_BUILD_CORE define" 9 #endif 10 11 12 typedef unsigned int pymem_uint; /* assuming >= 16 bits */ 13 14 #undef uint 15 #define uint pymem_uint 16 17 18 /* An object allocator for Python. 19 20 Here is an introduction to the layers of the Python memory architecture, 21 showing where the object allocator is actually used (layer +2), It is 22 called for every object allocation and deallocation (PyObject_New/Del), 23 unless the object-specific allocators implement a proprietary allocation 24 scheme (ex.: ints use a simple free list). This is also the place where 25 the cyclic garbage collector operates selectively on container objects. 26 27 28 Object-specific allocators 29 _____ ______ ______ ________ 30 [ int ] [ dict ] [ list ] ... [ string ] Python core | 31 +3 | <----- Object-specific memory -----> | <-- Non-object memory --> | 32 _______________________________ | | 33 [ Python's object allocator ] | | 34 +2 | ####### Object memory ####### | <------ Internal buffers ------> | 35 ______________________________________________________________ | 36 [ Python's raw memory allocator (PyMem_ API) ] | 37 +1 | <----- Python memory (under PyMem manager's control) ------> | | 38 __________________________________________________________________ 39 [ Underlying general-purpose allocator (ex: C library malloc) ] 40 0 | <------ Virtual memory allocated for the python process -------> | 41 42 ========================================================================= 43 _______________________________________________________________________ 44 [ OS-specific Virtual Memory Manager (VMM) ] 45 -1 | <--- Kernel dynamic storage allocation & management (page-based) ---> | 46 __________________________________ __________________________________ 47 [ ] [ ] 48 -2 | <-- Physical memory: ROM/RAM --> | | <-- Secondary storage (swap) --> | 49 50 */ 51 /*==========================================================================*/ 52 53 /* A fast, special-purpose memory allocator for small blocks, to be used 54 on top of a general-purpose malloc -- heavily based on previous art. */ 55 56 /* Vladimir Marangozov -- August 2000 */ 57 58 /* 59 * "Memory management is where the rubber meets the road -- if we do the wrong 60 * thing at any level, the results will not be good. And if we don't make the 61 * levels work well together, we are in serious trouble." (1) 62 * 63 * (1) Paul R. Wilson, Mark S. Johnstone, Michael Neely, and David Boles, 64 * "Dynamic Storage Allocation: A Survey and Critical Review", 65 * in Proc. 1995 Int'l. Workshop on Memory Management, September 1995. 66 */ 67 68 /* #undef WITH_MEMORY_LIMITS */ /* disable mem limit checks */ 69 70 /*==========================================================================*/ 71 72 /* 73 * Allocation strategy abstract: 74 * 75 * For small requests, the allocator sub-allocates <Big> blocks of memory. 76 * Requests greater than SMALL_REQUEST_THRESHOLD bytes are routed to the 77 * system's allocator. 78 * 79 * Small requests are grouped in size classes spaced 8 bytes apart, due 80 * to the required valid alignment of the returned address. Requests of 81 * a particular size are serviced from memory pools of 4K (one VMM page). 82 * Pools are fragmented on demand and contain free lists of blocks of one 83 * particular size class. In other words, there is a fixed-size allocator 84 * for each size class. Free pools are shared by the different allocators 85 * thus minimizing the space reserved for a particular size class. 86 * 87 * This allocation strategy is a variant of what is known as "simple 88 * segregated storage based on array of free lists". The main drawback of 89 * simple segregated storage is that we might end up with lot of reserved 90 * memory for the different free lists, which degenerate in time. To avoid 91 * this, we partition each free list in pools and we share dynamically the 92 * reserved space between all free lists. This technique is quite efficient 93 * for memory intensive programs which allocate mainly small-sized blocks. 94 * 95 * For small requests we have the following table: 96 * 97 * Request in bytes Size of allocated block Size class idx 98 * ---------------------------------------------------------------- 99 * 1-8 8 0 100 * 9-16 16 1 101 * 17-24 24 2 102 * 25-32 32 3 103 * 33-40 40 4 104 * 41-48 48 5 105 * 49-56 56 6 106 * 57-64 64 7 107 * 65-72 72 8 108 * ... ... ... 109 * 497-504 504 62 110 * 505-512 512 63 111 * 112 * 0, SMALL_REQUEST_THRESHOLD + 1 and up: routed to the underlying 113 * 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 buses). 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 131 #if SIZEOF_VOID_P > 4 132 #define ALIGNMENT 16 /* must be 2^N */ 133 #define ALIGNMENT_SHIFT 4 134 #else 135 #define ALIGNMENT 8 /* must be 2^N */ 136 #define ALIGNMENT_SHIFT 3 137 #endif 138 139 /* Return the number of bytes in size class I, as a uint. */ 140 #define INDEX2SIZE(I) (((pymem_uint)(I) + 1) << ALIGNMENT_SHIFT) 141 142 /* 143 * Max size threshold below which malloc requests are considered to be 144 * small enough in order to use preallocated memory pools. You can tune 145 * this value according to your application behaviour and memory needs. 146 * 147 * Note: a size threshold of 512 guarantees that newly created dictionaries 148 * will be allocated from preallocated memory pools on 64-bit. 149 * 150 * The following invariants must hold: 151 * 1) ALIGNMENT <= SMALL_REQUEST_THRESHOLD <= 512 152 * 2) SMALL_REQUEST_THRESHOLD is evenly divisible by ALIGNMENT 153 * 154 * Although not required, for better performance and space efficiency, 155 * it is recommended that SMALL_REQUEST_THRESHOLD is set to a power of 2. 156 */ 157 #define SMALL_REQUEST_THRESHOLD 512 158 #define NB_SMALL_SIZE_CLASSES (SMALL_REQUEST_THRESHOLD / ALIGNMENT) 159 160 /* 161 * The system's VMM page size can be obtained on most unices with a 162 * getpagesize() call or deduced from various header files. To make 163 * things simpler, we assume that it is 4K, which is OK for most systems. 164 * It is probably better if this is the native page size, but it doesn't 165 * have to be. In theory, if SYSTEM_PAGE_SIZE is larger than the native page 166 * size, then `POOL_ADDR(p)->arenaindex' could rarely cause a segmentation 167 * violation fault. 4K is apparently OK for all the platforms that python 168 * currently targets. 169 */ 170 #define SYSTEM_PAGE_SIZE (4 * 1024) 171 172 /* 173 * Maximum amount of memory managed by the allocator for small requests. 174 */ 175 #ifdef WITH_MEMORY_LIMITS 176 #ifndef SMALL_MEMORY_LIMIT 177 #define SMALL_MEMORY_LIMIT (64 * 1024 * 1024) /* 64 MB -- more? */ 178 #endif 179 #endif 180 181 #if !defined(WITH_PYMALLOC_RADIX_TREE) 182 /* Use radix-tree to track arena memory regions, for address_in_range(). 183 * Enable by default since it allows larger pool sizes. Can be disabled 184 * using -DWITH_PYMALLOC_RADIX_TREE=0 */ 185 #define WITH_PYMALLOC_RADIX_TREE 1 186 #endif 187 188 #if SIZEOF_VOID_P > 4 189 /* on 64-bit platforms use larger pools and arenas if we can */ 190 #define USE_LARGE_ARENAS 191 #if WITH_PYMALLOC_RADIX_TREE 192 /* large pools only supported if radix-tree is enabled */ 193 #define USE_LARGE_POOLS 194 #endif 195 #endif 196 197 /* 198 * The allocator sub-allocates <Big> blocks of memory (called arenas) aligned 199 * on a page boundary. This is a reserved virtual address space for the 200 * current process (obtained through a malloc()/mmap() call). In no way this 201 * means that the memory arenas will be used entirely. A malloc(<Big>) is 202 * usually an address range reservation for <Big> bytes, unless all pages within 203 * this space are referenced subsequently. So malloc'ing big blocks and not 204 * using them does not mean "wasting memory". It's an addressable range 205 * wastage... 206 * 207 * Arenas are allocated with mmap() on systems supporting anonymous memory 208 * mappings to reduce heap fragmentation. 209 */ 210 #ifdef USE_LARGE_ARENAS 211 #define ARENA_BITS 20 /* 1 MiB */ 212 #else 213 #define ARENA_BITS 18 /* 256 KiB */ 214 #endif 215 #define ARENA_SIZE (1 << ARENA_BITS) 216 #define ARENA_SIZE_MASK (ARENA_SIZE - 1) 217 218 #ifdef WITH_MEMORY_LIMITS 219 #define MAX_ARENAS (SMALL_MEMORY_LIMIT / ARENA_SIZE) 220 #endif 221 222 /* 223 * Size of the pools used for small blocks. Must be a power of 2. 224 */ 225 #ifdef USE_LARGE_POOLS 226 #define POOL_BITS 14 /* 16 KiB */ 227 #else 228 #define POOL_BITS 12 /* 4 KiB */ 229 #endif 230 #define POOL_SIZE (1 << POOL_BITS) 231 #define POOL_SIZE_MASK (POOL_SIZE - 1) 232 233 #if !WITH_PYMALLOC_RADIX_TREE 234 #if POOL_SIZE != SYSTEM_PAGE_SIZE 235 # error "pool size must be equal to system page size" 236 #endif 237 #endif 238 239 #define MAX_POOLS_IN_ARENA (ARENA_SIZE / POOL_SIZE) 240 #if MAX_POOLS_IN_ARENA * POOL_SIZE != ARENA_SIZE 241 # error "arena size not an exact multiple of pool size" 242 #endif 243 244 /* 245 * -- End of tunable settings section -- 246 */ 247 248 /*==========================================================================*/ 249 250 /* When you say memory, my mind reasons in terms of (pointers to) blocks */ 251 typedef uint8_t pymem_block; 252 253 /* Pool for small blocks. */ 254 struct pool_header { 255 union { pymem_block *_padding; 256 uint count; } ref; /* number of allocated blocks */ 257 pymem_block *freeblock; /* pool's free list head */ 258 struct pool_header *nextpool; /* next pool of this size class */ 259 struct pool_header *prevpool; /* previous pool "" */ 260 uint arenaindex; /* index into arenas of base adr */ 261 uint szidx; /* block size class index */ 262 uint nextoffset; /* bytes to virgin block */ 263 uint maxnextoffset; /* largest valid nextoffset */ 264 }; 265 266 typedef struct pool_header *poolp; 267 268 /* Record keeping for arenas. */ 269 struct arena_object { 270 /* The address of the arena, as returned by malloc. Note that 0 271 * will never be returned by a successful malloc, and is used 272 * here to mark an arena_object that doesn't correspond to an 273 * allocated arena. 274 */ 275 uintptr_t address; 276 277 /* Pool-aligned pointer to the next pool to be carved off. */ 278 pymem_block* pool_address; 279 280 /* The number of available pools in the arena: free pools + never- 281 * allocated pools. 282 */ 283 uint nfreepools; 284 285 /* The total number of pools in the arena, whether or not available. */ 286 uint ntotalpools; 287 288 /* Singly-linked list of available pools. */ 289 struct pool_header* freepools; 290 291 /* Whenever this arena_object is not associated with an allocated 292 * arena, the nextarena member is used to link all unassociated 293 * arena_objects in the singly-linked `unused_arena_objects` list. 294 * The prevarena member is unused in this case. 295 * 296 * When this arena_object is associated with an allocated arena 297 * with at least one available pool, both members are used in the 298 * doubly-linked `usable_arenas` list, which is maintained in 299 * increasing order of `nfreepools` values. 300 * 301 * Else this arena_object is associated with an allocated arena 302 * all of whose pools are in use. `nextarena` and `prevarena` 303 * are both meaningless in this case. 304 */ 305 struct arena_object* nextarena; 306 struct arena_object* prevarena; 307 }; 308 309 #define POOL_OVERHEAD _Py_SIZE_ROUND_UP(sizeof(struct pool_header), ALIGNMENT) 310 311 #define DUMMY_SIZE_IDX 0xffff /* size class of newly cached pools */ 312 313 /* Round pointer P down to the closest pool-aligned address <= P, as a poolp */ 314 #define POOL_ADDR(P) ((poolp)_Py_ALIGN_DOWN((P), POOL_SIZE)) 315 316 /* Return total number of blocks in pool of size index I, as a uint. */ 317 #define NUMBLOCKS(I) ((pymem_uint)(POOL_SIZE - POOL_OVERHEAD) / INDEX2SIZE(I)) 318 319 /*==========================================================================*/ 320 321 /* 322 * Pool table -- headed, circular, doubly-linked lists of partially used pools. 323 324 This is involved. For an index i, usedpools[i+i] is the header for a list of 325 all partially used pools holding small blocks with "size class idx" i. So 326 usedpools[0] corresponds to blocks of size 8, usedpools[2] to blocks of size 327 16, and so on: index 2*i <-> blocks of size (i+1)<<ALIGNMENT_SHIFT. 328 329 Pools are carved off an arena's highwater mark (an arena_object's pool_address 330 member) as needed. Once carved off, a pool is in one of three states forever 331 after: 332 333 used == partially used, neither empty nor full 334 At least one block in the pool is currently allocated, and at least one 335 block in the pool is not currently allocated (note this implies a pool 336 has room for at least two blocks). 337 This is a pool's initial state, as a pool is created only when malloc 338 needs space. 339 The pool holds blocks of a fixed size, and is in the circular list headed 340 at usedpools[i] (see above). It's linked to the other used pools of the 341 same size class via the pool_header's nextpool and prevpool members. 342 If all but one block is currently allocated, a malloc can cause a 343 transition to the full state. If all but one block is not currently 344 allocated, a free can cause a transition to the empty state. 345 346 full == all the pool's blocks are currently allocated 347 On transition to full, a pool is unlinked from its usedpools[] list. 348 It's not linked to from anything then anymore, and its nextpool and 349 prevpool members are meaningless until it transitions back to used. 350 A free of a block in a full pool puts the pool back in the used state. 351 Then it's linked in at the front of the appropriate usedpools[] list, so 352 that the next allocation for its size class will reuse the freed block. 353 354 empty == all the pool's blocks are currently available for allocation 355 On transition to empty, a pool is unlinked from its usedpools[] list, 356 and linked to the front of its arena_object's singly-linked freepools list, 357 via its nextpool member. The prevpool member has no meaning in this case. 358 Empty pools have no inherent size class: the next time a malloc finds 359 an empty list in usedpools[], it takes the first pool off of freepools. 360 If the size class needed happens to be the same as the size class the pool 361 last had, some pool initialization can be skipped. 362 363 364 Block Management 365 366 Blocks within pools are again carved out as needed. pool->freeblock points to 367 the start of a singly-linked list of free blocks within the pool. When a 368 block is freed, it's inserted at the front of its pool's freeblock list. Note 369 that the available blocks in a pool are *not* linked all together when a pool 370 is initialized. Instead only "the first two" (lowest addresses) blocks are 371 set up, returning the first such block, and setting pool->freeblock to a 372 one-block list holding the second such block. This is consistent with that 373 pymalloc strives at all levels (arena, pool, and block) never to touch a piece 374 of memory until it's actually needed. 375 376 So long as a pool is in the used state, we're certain there *is* a block 377 available for allocating, and pool->freeblock is not NULL. If pool->freeblock 378 points to the end of the free list before we've carved the entire pool into 379 blocks, that means we simply haven't yet gotten to one of the higher-address 380 blocks. The offset from the pool_header to the start of "the next" virgin 381 block is stored in the pool_header nextoffset member, and the largest value 382 of nextoffset that makes sense is stored in the maxnextoffset member when a 383 pool is initialized. All the blocks in a pool have been passed out at least 384 once when and only when nextoffset > maxnextoffset. 385 386 387 Major obscurity: While the usedpools vector is declared to have poolp 388 entries, it doesn't really. It really contains two pointers per (conceptual) 389 poolp entry, the nextpool and prevpool members of a pool_header. The 390 excruciating initialization code below fools C so that 391 392 usedpool[i+i] 393 394 "acts like" a genuine poolp, but only so long as you only reference its 395 nextpool and prevpool members. The "- 2*sizeof(pymem_block *)" gibberish is 396 compensating for that a pool_header's nextpool and prevpool members 397 immediately follow a pool_header's first two members: 398 399 union { pymem_block *_padding; 400 uint count; } ref; 401 pymem_block *freeblock; 402 403 each of which consume sizeof(pymem_block *) bytes. So what usedpools[i+i] really 404 contains is a fudged-up pointer p such that *if* C believes it's a poolp 405 pointer, then p->nextpool and p->prevpool are both p (meaning that the headed 406 circular list is empty). 407 408 It's unclear why the usedpools setup is so convoluted. It could be to 409 minimize the amount of cache required to hold this heavily-referenced table 410 (which only *needs* the two interpool pointer members of a pool_header). OTOH, 411 referencing code has to remember to "double the index" and doing so isn't 412 free, usedpools[0] isn't a strictly legal pointer, and we're crucially relying 413 on that C doesn't insert any padding anywhere in a pool_header at or before 414 the prevpool member. 415 **************************************************************************** */ 416 417 #define OBMALLOC_USED_POOLS_SIZE (2 * ((NB_SMALL_SIZE_CLASSES + 7) / 8) * 8) 418 419 struct _obmalloc_pools { 420 poolp used[OBMALLOC_USED_POOLS_SIZE]; 421 }; 422 423 424 /*========================================================================== 425 Arena management. 426 427 `arenas` is a vector of arena_objects. It contains maxarenas entries, some of 428 which may not be currently used (== they're arena_objects that aren't 429 currently associated with an allocated arena). Note that arenas proper are 430 separately malloc'ed. 431 432 Prior to Python 2.5, arenas were never free()'ed. Starting with Python 2.5, 433 we do try to free() arenas, and use some mild heuristic strategies to increase 434 the likelihood that arenas eventually can be freed. 435 436 unused_arena_objects 437 438 This is a singly-linked list of the arena_objects that are currently not 439 being used (no arena is associated with them). Objects are taken off the 440 head of the list in new_arena(), and are pushed on the head of the list in 441 PyObject_Free() when the arena is empty. Key invariant: an arena_object 442 is on this list if and only if its .address member is 0. 443 444 usable_arenas 445 446 This is a doubly-linked list of the arena_objects associated with arenas 447 that have pools available. These pools are either waiting to be reused, 448 or have not been used before. The list is sorted to have the most- 449 allocated arenas first (ascending order based on the nfreepools member). 450 This means that the next allocation will come from a heavily used arena, 451 which gives the nearly empty arenas a chance to be returned to the system. 452 In my unscientific tests this dramatically improved the number of arenas 453 that could be freed. 454 455 Note that an arena_object associated with an arena all of whose pools are 456 currently in use isn't on either list. 457 458 Changed in Python 3.8: keeping usable_arenas sorted by number of free pools 459 used to be done by one-at-a-time linear search when an arena's number of 460 free pools changed. That could, overall, consume time quadratic in the 461 number of arenas. That didn't really matter when there were only a few 462 hundred arenas (typical!), but could be a timing disaster when there were 463 hundreds of thousands. See bpo-37029. 464 465 Now we have a vector of "search fingers" to eliminate the need to search: 466 nfp2lasta[nfp] returns the last ("rightmost") arena in usable_arenas 467 with nfp free pools. This is NULL if and only if there is no arena with 468 nfp free pools in usable_arenas. 469 */ 470 471 /* How many arena_objects do we initially allocate? 472 * 16 = can allocate 16 arenas = 16 * ARENA_SIZE = 4MB before growing the 473 * `arenas` vector. 474 */ 475 #define INITIAL_ARENA_OBJECTS 16 476 477 struct _obmalloc_mgmt { 478 /* Array of objects used to track chunks of memory (arenas). */ 479 struct arena_object* arenas; 480 /* Number of slots currently allocated in the `arenas` vector. */ 481 uint maxarenas; 482 483 /* The head of the singly-linked, NULL-terminated list of available 484 * arena_objects. 485 */ 486 struct arena_object* unused_arena_objects; 487 488 /* The head of the doubly-linked, NULL-terminated at each end, list of 489 * arena_objects associated with arenas that have pools available. 490 */ 491 struct arena_object* usable_arenas; 492 493 /* nfp2lasta[nfp] is the last arena in usable_arenas with nfp free pools */ 494 struct arena_object* nfp2lasta[MAX_POOLS_IN_ARENA + 1]; 495 496 /* Number of arenas allocated that haven't been free()'d. */ 497 size_t narenas_currently_allocated; 498 499 /* Total number of times malloc() called to allocate an arena. */ 500 size_t ntimes_arena_allocated; 501 /* High water mark (max value ever seen) for narenas_currently_allocated. */ 502 size_t narenas_highwater; 503 504 Py_ssize_t raw_allocated_blocks; 505 }; 506 507 508 #if WITH_PYMALLOC_RADIX_TREE 509 /*==========================================================================*/ 510 /* radix tree for tracking arena usage. If enabled, used to implement 511 address_in_range(). 512 513 memory address bit allocation for keys 514 515 64-bit pointers, IGNORE_BITS=0 and 2^20 arena size: 516 15 -> MAP_TOP_BITS 517 15 -> MAP_MID_BITS 518 14 -> MAP_BOT_BITS 519 20 -> ideal aligned arena 520 ---- 521 64 522 523 64-bit pointers, IGNORE_BITS=16, and 2^20 arena size: 524 16 -> IGNORE_BITS 525 10 -> MAP_TOP_BITS 526 10 -> MAP_MID_BITS 527 8 -> MAP_BOT_BITS 528 20 -> ideal aligned arena 529 ---- 530 64 531 532 32-bit pointers and 2^18 arena size: 533 14 -> MAP_BOT_BITS 534 18 -> ideal aligned arena 535 ---- 536 32 537 538 */ 539 540 #if SIZEOF_VOID_P == 8 541 542 /* number of bits in a pointer */ 543 #define POINTER_BITS 64 544 545 /* High bits of memory addresses that will be ignored when indexing into the 546 * radix tree. Setting this to zero is the safe default. For most 64-bit 547 * machines, setting this to 16 would be safe. The kernel would not give 548 * user-space virtual memory addresses that have significant information in 549 * those high bits. The main advantage to setting IGNORE_BITS > 0 is that less 550 * virtual memory will be used for the top and middle radix tree arrays. Those 551 * arrays are allocated in the BSS segment and so will typically consume real 552 * memory only if actually accessed. 553 */ 554 #define IGNORE_BITS 0 555 556 /* use the top and mid layers of the radix tree */ 557 #define USE_INTERIOR_NODES 558 559 #elif SIZEOF_VOID_P == 4 560 561 #define POINTER_BITS 32 562 #define IGNORE_BITS 0 563 564 #else 565 566 /* Currently this code works for 64-bit or 32-bit pointers only. */ 567 #error "obmalloc radix tree requires 64-bit or 32-bit pointers." 568 569 #endif /* SIZEOF_VOID_P */ 570 571 /* arena_coverage_t members require this to be true */ 572 #if ARENA_BITS >= 32 573 # error "arena size must be < 2^32" 574 #endif 575 576 /* the lower bits of the address that are not ignored */ 577 #define ADDRESS_BITS (POINTER_BITS - IGNORE_BITS) 578 579 #ifdef USE_INTERIOR_NODES 580 /* number of bits used for MAP_TOP and MAP_MID nodes */ 581 #define INTERIOR_BITS ((ADDRESS_BITS - ARENA_BITS + 2) / 3) 582 #else 583 #define INTERIOR_BITS 0 584 #endif 585 586 #define MAP_TOP_BITS INTERIOR_BITS 587 #define MAP_TOP_LENGTH (1 << MAP_TOP_BITS) 588 #define MAP_TOP_MASK (MAP_TOP_LENGTH - 1) 589 590 #define MAP_MID_BITS INTERIOR_BITS 591 #define MAP_MID_LENGTH (1 << MAP_MID_BITS) 592 #define MAP_MID_MASK (MAP_MID_LENGTH - 1) 593 594 #define MAP_BOT_BITS (ADDRESS_BITS - ARENA_BITS - 2*INTERIOR_BITS) 595 #define MAP_BOT_LENGTH (1 << MAP_BOT_BITS) 596 #define MAP_BOT_MASK (MAP_BOT_LENGTH - 1) 597 598 #define MAP_BOT_SHIFT ARENA_BITS 599 #define MAP_MID_SHIFT (MAP_BOT_BITS + MAP_BOT_SHIFT) 600 #define MAP_TOP_SHIFT (MAP_MID_BITS + MAP_MID_SHIFT) 601 602 #define AS_UINT(p) ((uintptr_t)(p)) 603 #define MAP_BOT_INDEX(p) ((AS_UINT(p) >> MAP_BOT_SHIFT) & MAP_BOT_MASK) 604 #define MAP_MID_INDEX(p) ((AS_UINT(p) >> MAP_MID_SHIFT) & MAP_MID_MASK) 605 #define MAP_TOP_INDEX(p) ((AS_UINT(p) >> MAP_TOP_SHIFT) & MAP_TOP_MASK) 606 607 #if IGNORE_BITS > 0 608 /* Return the ignored part of the pointer address. Those bits should be same 609 * for all valid pointers if IGNORE_BITS is set correctly. 610 */ 611 #define HIGH_BITS(p) (AS_UINT(p) >> ADDRESS_BITS) 612 #else 613 #define HIGH_BITS(p) 0 614 #endif 615 616 617 /* This is the leaf of the radix tree. See arena_map_mark_used() for the 618 * meaning of these members. */ 619 typedef struct { 620 int32_t tail_hi; 621 int32_t tail_lo; 622 } arena_coverage_t; 623 624 typedef struct arena_map_bot { 625 /* The members tail_hi and tail_lo are accessed together. So, it 626 * better to have them as an array of structs, rather than two 627 * arrays. 628 */ 629 arena_coverage_t arenas[MAP_BOT_LENGTH]; 630 } arena_map_bot_t; 631 632 #ifdef USE_INTERIOR_NODES 633 typedef struct arena_map_mid { 634 struct arena_map_bot *ptrs[MAP_MID_LENGTH]; 635 } arena_map_mid_t; 636 637 typedef struct arena_map_top { 638 struct arena_map_mid *ptrs[MAP_TOP_LENGTH]; 639 } arena_map_top_t; 640 #endif 641 642 struct _obmalloc_usage { 643 /* The root of radix tree. Note that by initializing like this, the memory 644 * should be in the BSS. The OS will only memory map pages as the MAP_MID 645 * nodes get used (OS pages are demand loaded as needed). 646 */ 647 #ifdef USE_INTERIOR_NODES 648 arena_map_top_t arena_map_root; 649 /* accounting for number of used interior nodes */ 650 int arena_map_mid_count; 651 int arena_map_bot_count; 652 #else 653 arena_map_bot_t arena_map_root; 654 #endif 655 }; 656 657 #endif /* WITH_PYMALLOC_RADIX_TREE */ 658 659 660 struct _obmalloc_global_state { 661 int dump_debug_stats; 662 Py_ssize_t interpreter_leaks; 663 }; 664 665 struct _obmalloc_state { 666 struct _obmalloc_pools pools; 667 struct _obmalloc_mgmt mgmt; 668 #if WITH_PYMALLOC_RADIX_TREE 669 struct _obmalloc_usage usage; 670 #endif 671 }; 672 673 674 #undef uint 675 676 677 /* Allocate memory directly from the O/S virtual memory system, 678 * where supported. Otherwise fallback on malloc */ 679 void *_PyObject_VirtualAlloc(size_t size); 680 void _PyObject_VirtualFree(void *, size_t size); 681 682 683 /* This function returns the number of allocated memory blocks, regardless of size */ 684 extern Py_ssize_t _Py_GetGlobalAllocatedBlocks(void); 685 #define _Py_GetAllocatedBlocks() \ 686 _Py_GetGlobalAllocatedBlocks() 687 extern Py_ssize_t _PyInterpreterState_GetAllocatedBlocks(PyInterpreterState *); 688 extern void _PyInterpreterState_FinalizeAllocatedBlocks(PyInterpreterState *); 689 extern int _PyMem_init_obmalloc(PyInterpreterState *interp); 690 extern bool _PyMem_obmalloc_state_on_heap(PyInterpreterState *interp); 691 692 693 #ifdef WITH_PYMALLOC 694 // Export the symbol for the 3rd party 'guppy3' project 695 PyAPI_FUNC(int) _PyObject_DebugMallocStats(FILE *out); 696 #endif 697 698 699 #ifdef __cplusplus 700 } 701 #endif 702 #endif // !Py_INTERNAL_OBMALLOC_H 703