5 /* An object allocator for Python.
7 Here is an introduction to the layers of the Python memory architecture,
8 showing where the object allocator is actually used (layer +2), It is
9 called for every object allocation and deallocation (PyObject_New/Del),
10 unless the object-specific allocators implement a proprietary allocation
11 scheme (ex.: ints use a simple free list). This is also the place where
12 the cyclic garbage collector operates selectively on container objects.
15 Object-specific allocators
16 _____ ______ ______ ________
17 [ int ] [ dict ] [ list ] ... [ string ] Python core |
18 +3 | <----- Object-specific memory -----> | <-- Non-object memory --> |
19 _______________________________ | |
20 [ Python's object allocator ] | |
21 +2 | ####### Object memory ####### | <------ Internal buffers ------> |
22 ______________________________________________________________ |
23 [ Python's raw memory allocator (PyMem_ API) ] |
24 +1 | <----- Python memory (under PyMem manager's control) ------> | |
25 __________________________________________________________________
26 [ Underlying general-purpose allocator (ex: C library malloc) ]
27 0 | <------ Virtual memory allocated for the python process -------> |
29 =========================================================================
30 _______________________________________________________________________
31 [ OS-specific Virtual Memory Manager (VMM) ]
32 -1 | <--- Kernel dynamic storage allocation & management (page-based) ---> |
33 __________________________________ __________________________________
35 -2 | <-- Physical memory: ROM/RAM --> | | <-- Secondary storage (swap) --> |
38 /*==========================================================================*/
40 /* A fast, special-purpose memory allocator for small blocks, to be used
41 on top of a general-purpose malloc -- heavily based on previous art. */
43 /* Vladimir Marangozov -- August 2000 */
46 * "Memory management is where the rubber meets the road -- if we do the wrong
47 * thing at any level, the results will not be good. And if we don't make the
48 * levels work well together, we are in serious trouble." (1)
50 * (1) Paul R. Wilson, Mark S. Johnstone, Michael Neely, and David Boles,
51 * "Dynamic Storage Allocation: A Survey and Critical Review",
52 * in Proc. 1995 Int'l. Workshop on Memory Management, September 1995.
55 /* #undef WITH_MEMORY_LIMITS */ /* disable mem limit checks */
57 /*==========================================================================*/
60 * Allocation strategy abstract:
62 * For small requests, the allocator sub-allocates <Big> blocks of memory.
63 * Requests greater than 256 bytes are routed to the system's allocator.
65 * Small requests are grouped in size classes spaced 8 bytes apart, due
66 * to the required valid alignment of the returned address. Requests of
67 * a particular size are serviced from memory pools of 4K (one VMM page).
68 * Pools are fragmented on demand and contain free lists of blocks of one
69 * particular size class. In other words, there is a fixed-size allocator
70 * for each size class. Free pools are shared by the different allocators
71 * thus minimizing the space reserved for a particular size class.
73 * This allocation strategy is a variant of what is known as "simple
74 * segregated storage based on array of free lists". The main drawback of
75 * simple segregated storage is that we might end up with lot of reserved
76 * memory for the different free lists, which degenerate in time. To avoid
77 * this, we partition each free list in pools and we share dynamically the
78 * reserved space between all free lists. This technique is quite efficient
79 * for memory intensive programs which allocate mainly small-sized blocks.
81 * For small requests we have the following table:
83 * Request in bytes Size of allocated block Size class idx
84 * ----------------------------------------------------------------
98 * 0, 257 and up: routed to the underlying allocator.
101 /*==========================================================================*/
104 * -- Main tunable settings section --
108 * Alignment of addresses returned to the user. 8-bytes alignment works
109 * on most current architectures (with 32-bit or 64-bit address busses).
110 * The alignment value is also used for grouping small requests in size
111 * classes spaced ALIGNMENT bytes apart.
113 * You shouldn't change this unless you know what you are doing.
115 #define ALIGNMENT 8 /* must be 2^N */
116 #define ALIGNMENT_SHIFT 3
117 #define ALIGNMENT_MASK (ALIGNMENT - 1)
119 /* Return the number of bytes in size class I, as a uint. */
120 #define INDEX2SIZE(I) (((uint)(I) + 1) << ALIGNMENT_SHIFT)
123 * Max size threshold below which malloc requests are considered to be
124 * small enough in order to use preallocated memory pools. You can tune
125 * this value according to your application behaviour and memory needs.
127 * The following invariants must hold:
128 * 1) ALIGNMENT <= SMALL_REQUEST_THRESHOLD <= 256
129 * 2) SMALL_REQUEST_THRESHOLD is evenly divisible by ALIGNMENT
131 * Although not required, for better performance and space efficiency,
132 * it is recommended that SMALL_REQUEST_THRESHOLD is set to a power of 2.
134 #define SMALL_REQUEST_THRESHOLD 256
135 #define NB_SMALL_SIZE_CLASSES (SMALL_REQUEST_THRESHOLD / ALIGNMENT)
138 * The system's VMM page size can be obtained on most unices with a
139 * getpagesize() call or deduced from various header files. To make
140 * things simpler, we assume that it is 4K, which is OK for most systems.
141 * It is probably better if this is the native page size, but it doesn't
142 * have to be. In theory, if SYSTEM_PAGE_SIZE is larger than the native page
143 * size, then `POOL_ADDR(p)->arenaindex' could rarely cause a segmentation
144 * violation fault. 4K is apparently OK for all the platforms that python
147 #define SYSTEM_PAGE_SIZE (4 * 1024)
148 #define SYSTEM_PAGE_SIZE_MASK (SYSTEM_PAGE_SIZE - 1)
151 * Maximum amount of memory managed by the allocator for small requests.
153 #ifdef WITH_MEMORY_LIMITS
154 #ifndef SMALL_MEMORY_LIMIT
155 #define SMALL_MEMORY_LIMIT (64 * 1024 * 1024) /* 64 MB -- more? */
160 * The allocator sub-allocates <Big> blocks of memory (called arenas) aligned
161 * on a page boundary. This is a reserved virtual address space for the
162 * current process (obtained through a malloc call). In no way this means
163 * that the memory arenas will be used entirely. A malloc(<Big>) is usually
164 * an address range reservation for <Big> bytes, unless all pages within this
165 * space are referenced subsequently. So malloc'ing big blocks and not using
166 * them does not mean "wasting memory". It's an addressable range wastage...
168 * Therefore, allocating arenas with malloc is not optimal, because there is
169 * some address space wastage, but this is the most portable way to request
170 * memory from the system across various platforms.
172 #define ARENA_SIZE (256 << 10) /* 256KB */
174 #ifdef WITH_MEMORY_LIMITS
175 #define MAX_ARENAS (SMALL_MEMORY_LIMIT / ARENA_SIZE)
179 * Size of the pools used for small blocks. Should be a power of 2,
180 * between 1K and SYSTEM_PAGE_SIZE, that is: 1k, 2k, 4k.
182 #define POOL_SIZE SYSTEM_PAGE_SIZE /* must be 2^N */
183 #define POOL_SIZE_MASK SYSTEM_PAGE_SIZE_MASK
186 * -- End of tunable settings section --
189 /*==========================================================================*/
194 * To reduce lock contention, it would probably be better to refine the
195 * crude function locking with per size class locking. I'm not positive
196 * however, whether it's worth switching to such locking policy because
197 * of the performance penalty it might introduce.
199 * The following macros describe the simplest (should also be the fastest)
200 * lock object on a particular platform and the init/fini/lock/unlock
201 * operations on it. The locks defined here are not expected to be recursive
202 * because it is assumed that they will always be called in the order:
203 * INIT, [LOCK, UNLOCK]*, FINI.
207 * Python's threads are serialized, so object malloc locking is disabled.
209 #define SIMPLELOCK_DECL(lock) /* simple lock declaration */
210 #define SIMPLELOCK_INIT(lock) /* allocate (if needed) and initialize */
211 #define SIMPLELOCK_FINI(lock) /* free/destroy an existing lock */
212 #define SIMPLELOCK_LOCK(lock) /* acquire released lock */
213 #define SIMPLELOCK_UNLOCK(lock) /* release acquired lock */
217 * I don't care if these are defined in <sys/types.h> or elsewhere. Axiom.
220 #define uchar unsigned char /* assuming == 8 bits */
223 #define uint unsigned int /* assuming >= 16 bits */
226 #define ulong unsigned long /* assuming >= 32 bits */
229 #define uptr Py_uintptr_t
231 /* When you say memory, my mind reasons in terms of (pointers to) blocks */
234 /* Pool for small blocks. */
236 union { block
*_padding
;
237 uint count
; } ref
; /* number of allocated blocks */
238 block
*freeblock
; /* pool's free list head */
239 struct pool_header
*nextpool
; /* next pool of this size class */
240 struct pool_header
*prevpool
; /* previous pool "" */
241 uint arenaindex
; /* index into arenas of base adr */
242 uint szidx
; /* block size class index */
243 uint nextoffset
; /* bytes to virgin block */
244 uint maxnextoffset
; /* largest valid nextoffset */
247 typedef struct pool_header
*poolp
;
249 /* Record keeping for arenas. */
250 struct arena_object
{
251 /* The address of the arena, as returned by malloc. Note that 0
252 * will never be returned by a successful malloc, and is used
253 * here to mark an arena_object that doesn't correspond to an
258 /* Pool-aligned pointer to the next pool to be carved off. */
261 /* The number of available pools in the arena: free pools + never-
266 /* The total number of pools in the arena, whether or not available. */
269 /* Singly-linked list of available pools. */
270 struct pool_header
* freepools
;
272 /* Whenever this arena_object is not associated with an allocated
273 * arena, the nextarena member is used to link all unassociated
274 * arena_objects in the singly-linked `unused_arena_objects` list.
275 * The prevarena member is unused in this case.
277 * When this arena_object is associated with an allocated arena
278 * with at least one available pool, both members are used in the
279 * doubly-linked `usable_arenas` list, which is maintained in
280 * increasing order of `nfreepools` values.
282 * Else this arena_object is associated with an allocated arena
283 * all of whose pools are in use. `nextarena` and `prevarena`
284 * are both meaningless in this case.
286 struct arena_object
* nextarena
;
287 struct arena_object
* prevarena
;
291 #define ROUNDUP(x) (((x) + ALIGNMENT_MASK) & ~ALIGNMENT_MASK)
292 #define POOL_OVERHEAD ROUNDUP(sizeof(struct pool_header))
294 #define DUMMY_SIZE_IDX 0xffff /* size class of newly cached pools */
296 /* Round pointer P down to the closest pool-aligned address <= P, as a poolp */
297 #define POOL_ADDR(P) ((poolp)((uptr)(P) & ~(uptr)POOL_SIZE_MASK))
299 /* Return total number of blocks in pool of size index I, as a uint. */
300 #define NUMBLOCKS(I) ((uint)(POOL_SIZE - POOL_OVERHEAD) / INDEX2SIZE(I))
302 /*==========================================================================*/
307 SIMPLELOCK_DECL(_malloc_lock
)
308 #define LOCK() SIMPLELOCK_LOCK(_malloc_lock)
309 #define UNLOCK() SIMPLELOCK_UNLOCK(_malloc_lock)
310 #define LOCK_INIT() SIMPLELOCK_INIT(_malloc_lock)
311 #define LOCK_FINI() SIMPLELOCK_FINI(_malloc_lock)
314 * Pool table -- headed, circular, doubly-linked lists of partially used pools.
316 This is involved. For an index i, usedpools[i+i] is the header for a list of
317 all partially used pools holding small blocks with "size class idx" i. So
318 usedpools[0] corresponds to blocks of size 8, usedpools[2] to blocks of size
319 16, and so on: index 2*i <-> blocks of size (i+1)<<ALIGNMENT_SHIFT.
321 Pools are carved off an arena's highwater mark (an arena_object's pool_address
322 member) as needed. Once carved off, a pool is in one of three states forever
325 used == partially used, neither empty nor full
326 At least one block in the pool is currently allocated, and at least one
327 block in the pool is not currently allocated (note this implies a pool
328 has room for at least two blocks).
329 This is a pool's initial state, as a pool is created only when malloc
331 The pool holds blocks of a fixed size, and is in the circular list headed
332 at usedpools[i] (see above). It's linked to the other used pools of the
333 same size class via the pool_header's nextpool and prevpool members.
334 If all but one block is currently allocated, a malloc can cause a
335 transition to the full state. If all but one block is not currently
336 allocated, a free can cause a transition to the empty state.
338 full == all the pool's blocks are currently allocated
339 On transition to full, a pool is unlinked from its usedpools[] list.
340 It's not linked to from anything then anymore, and its nextpool and
341 prevpool members are meaningless until it transitions back to used.
342 A free of a block in a full pool puts the pool back in the used state.
343 Then it's linked in at the front of the appropriate usedpools[] list, so
344 that the next allocation for its size class will reuse the freed block.
346 empty == all the pool's blocks are currently available for allocation
347 On transition to empty, a pool is unlinked from its usedpools[] list,
348 and linked to the front of its arena_object's singly-linked freepools list,
349 via its nextpool member. The prevpool member has no meaning in this case.
350 Empty pools have no inherent size class: the next time a malloc finds
351 an empty list in usedpools[], it takes the first pool off of freepools.
352 If the size class needed happens to be the same as the size class the pool
353 last had, some pool initialization can be skipped.
358 Blocks within pools are again carved out as needed. pool->freeblock points to
359 the start of a singly-linked list of free blocks within the pool. When a
360 block is freed, it's inserted at the front of its pool's freeblock list. Note
361 that the available blocks in a pool are *not* linked all together when a pool
362 is initialized. Instead only "the first two" (lowest addresses) blocks are
363 set up, returning the first such block, and setting pool->freeblock to a
364 one-block list holding the second such block. This is consistent with that
365 pymalloc strives at all levels (arena, pool, and block) never to touch a piece
366 of memory until it's actually needed.
368 So long as a pool is in the used state, we're certain there *is* a block
369 available for allocating, and pool->freeblock is not NULL. If pool->freeblock
370 points to the end of the free list before we've carved the entire pool into
371 blocks, that means we simply haven't yet gotten to one of the higher-address
372 blocks. The offset from the pool_header to the start of "the next" virgin
373 block is stored in the pool_header nextoffset member, and the largest value
374 of nextoffset that makes sense is stored in the maxnextoffset member when a
375 pool is initialized. All the blocks in a pool have been passed out at least
376 once when and only when nextoffset > maxnextoffset.
379 Major obscurity: While the usedpools vector is declared to have poolp
380 entries, it doesn't really. It really contains two pointers per (conceptual)
381 poolp entry, the nextpool and prevpool members of a pool_header. The
382 excruciating initialization code below fools C so that
386 "acts like" a genuine poolp, but only so long as you only reference its
387 nextpool and prevpool members. The "- 2*sizeof(block *)" gibberish is
388 compensating for that a pool_header's nextpool and prevpool members
389 immediately follow a pool_header's first two members:
391 union { block *_padding;
395 each of which consume sizeof(block *) bytes. So what usedpools[i+i] really
396 contains is a fudged-up pointer p such that *if* C believes it's a poolp
397 pointer, then p->nextpool and p->prevpool are both p (meaning that the headed
398 circular list is empty).
400 It's unclear why the usedpools setup is so convoluted. It could be to
401 minimize the amount of cache required to hold this heavily-referenced table
402 (which only *needs* the two interpool pointer members of a pool_header). OTOH,
403 referencing code has to remember to "double the index" and doing so isn't
404 free, usedpools[0] isn't a strictly legal pointer, and we're crucially relying
405 on that C doesn't insert any padding anywhere in a pool_header at or before
407 **************************************************************************** */
409 #define PTA(x) ((poolp )((uchar *)&(usedpools[2*(x)]) - 2*sizeof(block *)))
410 #define PT(x) PTA(x), PTA(x)
412 static poolp usedpools
[2 * ((NB_SMALL_SIZE_CLASSES
+ 7) / 8) * 8] = {
413 PT(0), PT(1), PT(2), PT(3), PT(4), PT(5), PT(6), PT(7)
414 #if NB_SMALL_SIZE_CLASSES > 8
415 , PT(8), PT(9), PT(10), PT(11), PT(12), PT(13), PT(14), PT(15)
416 #if NB_SMALL_SIZE_CLASSES > 16
417 , PT(16), PT(17), PT(18), PT(19), PT(20), PT(21), PT(22), PT(23)
418 #if NB_SMALL_SIZE_CLASSES > 24
419 , PT(24), PT(25), PT(26), PT(27), PT(28), PT(29), PT(30), PT(31)
420 #if NB_SMALL_SIZE_CLASSES > 32
421 , PT(32), PT(33), PT(34), PT(35), PT(36), PT(37), PT(38), PT(39)
422 #if NB_SMALL_SIZE_CLASSES > 40
423 , PT(40), PT(41), PT(42), PT(43), PT(44), PT(45), PT(46), PT(47)
424 #if NB_SMALL_SIZE_CLASSES > 48
425 , PT(48), PT(49), PT(50), PT(51), PT(52), PT(53), PT(54), PT(55)
426 #if NB_SMALL_SIZE_CLASSES > 56
427 , PT(56), PT(57), PT(58), PT(59), PT(60), PT(61), PT(62), PT(63)
428 #endif /* NB_SMALL_SIZE_CLASSES > 56 */
429 #endif /* NB_SMALL_SIZE_CLASSES > 48 */
430 #endif /* NB_SMALL_SIZE_CLASSES > 40 */
431 #endif /* NB_SMALL_SIZE_CLASSES > 32 */
432 #endif /* NB_SMALL_SIZE_CLASSES > 24 */
433 #endif /* NB_SMALL_SIZE_CLASSES > 16 */
434 #endif /* NB_SMALL_SIZE_CLASSES > 8 */
437 /*==========================================================================
440 `arenas` is a vector of arena_objects. It contains maxarenas entries, some of
441 which may not be currently used (== they're arena_objects that aren't
442 currently associated with an allocated arena). Note that arenas proper are
443 separately malloc'ed.
445 Prior to Python 2.5, arenas were never free()'ed. Starting with Python 2.5,
446 we do try to free() arenas, and use some mild heuristic strategies to increase
447 the likelihood that arenas eventually can be freed.
451 This is a singly-linked list of the arena_objects that are currently not
452 being used (no arena is associated with them). Objects are taken off the
453 head of the list in new_arena(), and are pushed on the head of the list in
454 PyObject_Free() when the arena is empty. Key invariant: an arena_object
455 is on this list if and only if its .address member is 0.
459 This is a doubly-linked list of the arena_objects associated with arenas
460 that have pools available. These pools are either waiting to be reused,
461 or have not been used before. The list is sorted to have the most-
462 allocated arenas first (ascending order based on the nfreepools member).
463 This means that the next allocation will come from a heavily used arena,
464 which gives the nearly empty arenas a chance to be returned to the system.
465 In my unscientific tests this dramatically improved the number of arenas
468 Note that an arena_object associated with an arena all of whose pools are
469 currently in use isn't on either list.
472 /* Array of objects used to track chunks of memory (arenas). */
473 static struct arena_object
* arenas
= NULL
;
474 /* Number of slots currently allocated in the `arenas` vector. */
475 static uint maxarenas
= 0;
477 /* The head of the singly-linked, NULL-terminated list of available
480 static struct arena_object
* unused_arena_objects
= NULL
;
482 /* The head of the doubly-linked, NULL-terminated at each end, list of
483 * arena_objects associated with arenas that have pools available.
485 static struct arena_object
* usable_arenas
= NULL
;
487 /* How many arena_objects do we initially allocate?
488 * 16 = can allocate 16 arenas = 16 * ARENA_SIZE = 4MB before growing the
491 #define INITIAL_ARENA_OBJECTS 16
493 /* Number of arenas allocated that haven't been free()'d. */
494 static size_t narenas_currently_allocated
= 0;
496 #ifdef PYMALLOC_DEBUG
497 /* Total number of times malloc() called to allocate an arena. */
498 static size_t ntimes_arena_allocated
= 0;
499 /* High water mark (max value ever seen) for narenas_currently_allocated. */
500 static size_t narenas_highwater
= 0;
503 /* Allocate a new arena. If we run out of memory, return NULL. Else
504 * allocate a new arena, and return the address of an arena_object
505 * describing the new arena. It's expected that the caller will set
506 * `usable_arenas` to the return value.
508 static struct arena_object
*
511 struct arena_object
* arenaobj
;
512 uint excess
; /* number of bytes above pool alignment */
514 #ifdef PYMALLOC_DEBUG
515 if (Py_GETENV("PYTHONMALLOCSTATS"))
516 _PyObject_DebugMallocStats();
518 if (unused_arena_objects
== NULL
) {
523 /* Double the number of arena objects on each allocation.
524 * Note that it's possible for `numarenas` to overflow.
526 numarenas
= maxarenas
? maxarenas
<< 1 : INITIAL_ARENA_OBJECTS
;
527 if (numarenas
<= maxarenas
)
528 return NULL
; /* overflow */
529 if (numarenas
> PY_SIZE_MAX
/ sizeof(*arenas
))
530 return NULL
; /* overflow */
531 nbytes
= numarenas
* sizeof(*arenas
);
532 arenaobj
= (struct arena_object
*)realloc(arenas
, nbytes
);
533 if (arenaobj
== NULL
)
537 /* We might need to fix pointers that were copied. However,
538 * new_arena only gets called when all the pages in the
539 * previous arenas are full. Thus, there are *no* pointers
540 * into the old array. Thus, we don't have to worry about
541 * invalid pointers. Just to be sure, some asserts:
543 assert(usable_arenas
== NULL
);
544 assert(unused_arena_objects
== NULL
);
546 /* Put the new arenas on the unused_arena_objects list. */
547 for (i
= maxarenas
; i
< numarenas
; ++i
) {
548 arenas
[i
].address
= 0; /* mark as unassociated */
549 arenas
[i
].nextarena
= i
< numarenas
- 1 ?
553 /* Update globals. */
554 unused_arena_objects
= &arenas
[maxarenas
];
555 maxarenas
= numarenas
;
558 /* Take the next available arena object off the head of the list. */
559 assert(unused_arena_objects
!= NULL
);
560 arenaobj
= unused_arena_objects
;
561 unused_arena_objects
= arenaobj
->nextarena
;
562 assert(arenaobj
->address
== 0);
563 arenaobj
->address
= (uptr
)malloc(ARENA_SIZE
);
564 if (arenaobj
->address
== 0) {
565 /* The allocation failed: return NULL after putting the
568 arenaobj
->nextarena
= unused_arena_objects
;
569 unused_arena_objects
= arenaobj
;
573 ++narenas_currently_allocated
;
574 #ifdef PYMALLOC_DEBUG
575 ++ntimes_arena_allocated
;
576 if (narenas_currently_allocated
> narenas_highwater
)
577 narenas_highwater
= narenas_currently_allocated
;
579 arenaobj
->freepools
= NULL
;
580 /* pool_address <- first pool-aligned address in the arena
581 nfreepools <- number of whole pools that fit after alignment */
582 arenaobj
->pool_address
= (block
*)arenaobj
->address
;
583 arenaobj
->nfreepools
= ARENA_SIZE
/ POOL_SIZE
;
584 assert(POOL_SIZE
* arenaobj
->nfreepools
== ARENA_SIZE
);
585 excess
= (uint
)(arenaobj
->address
& POOL_SIZE_MASK
);
587 --arenaobj
->nfreepools
;
588 arenaobj
->pool_address
+= POOL_SIZE
- excess
;
590 arenaobj
->ntotalpools
= arenaobj
->nfreepools
;
596 Py_ADDRESS_IN_RANGE(P, POOL)
598 Return true if and only if P is an address that was allocated by pymalloc.
599 POOL must be the pool address associated with P, i.e., POOL = POOL_ADDR(P)
600 (the caller is asked to compute this because the macro expands POOL more than
601 once, and for efficiency it's best for the caller to assign POOL_ADDR(P) to a
602 variable and pass the latter to the macro; because Py_ADDRESS_IN_RANGE is
603 called on every alloc/realloc/free, micro-efficiency is important here).
605 Tricky: Let B be the arena base address associated with the pool, B =
606 arenas[(POOL)->arenaindex].address. Then P belongs to the arena if and only if
608 B <= P < B + ARENA_SIZE
610 Subtracting B throughout, this is true iff
612 0 <= P-B < ARENA_SIZE
614 By using unsigned arithmetic, the "0 <=" half of the test can be skipped.
616 Obscure: A PyMem "free memory" function can call the pymalloc free or realloc
617 before the first arena has been allocated. `arenas` is still NULL in that
618 case. We're relying on that maxarenas is also 0 in that case, so that
619 (POOL)->arenaindex < maxarenas must be false, saving us from trying to index
622 Details: given P and POOL, the arena_object corresponding to P is AO =
623 arenas[(POOL)->arenaindex]. Suppose obmalloc controls P. Then (barring wild
624 stores, etc), POOL is the correct address of P's pool, AO.address is the
625 correct base address of the pool's arena, and P must be within ARENA_SIZE of
626 AO.address. In addition, AO.address is not 0 (no arena can start at address 0
627 (NULL)). Therefore Py_ADDRESS_IN_RANGE correctly reports that obmalloc
630 Now suppose obmalloc does not control P (e.g., P was obtained via a direct
631 call to the system malloc() or realloc()). (POOL)->arenaindex may be anything
632 in this case -- it may even be uninitialized trash. If the trash arenaindex
633 is >= maxarenas, the macro correctly concludes at once that obmalloc doesn't
636 Else arenaindex is < maxarena, and AO is read up. If AO corresponds to an
637 allocated arena, obmalloc controls all the memory in slice AO.address :
638 AO.address+ARENA_SIZE. By case assumption, P is not controlled by obmalloc,
639 so P doesn't lie in that slice, so the macro correctly reports that P is not
640 controlled by obmalloc.
642 Finally, if P is not controlled by obmalloc and AO corresponds to an unused
643 arena_object (one not currently associated with an allocated arena),
644 AO.address is 0, and the second test in the macro reduces to:
648 If P >= ARENA_SIZE (extremely likely), the macro again correctly concludes
649 that P is not controlled by obmalloc. However, if P < ARENA_SIZE, this part
650 of the test still passes, and the third clause (AO.address != 0) is necessary
651 to get the correct result: AO.address is 0 in this case, so the macro
652 correctly reports that P is not controlled by obmalloc (despite that P lies in
653 slice AO.address : AO.address + ARENA_SIZE).
655 Note: The third (AO.address != 0) clause was added in Python 2.5. Before
656 2.5, arenas were never free()'ed, and an arenaindex < maxarena always
657 corresponded to a currently-allocated arena, so the "P is not controlled by
658 obmalloc, AO corresponds to an unused arena_object, and P < ARENA_SIZE" case
661 Note that the logic is excruciating, and reading up possibly uninitialized
662 memory when P is not controlled by obmalloc (to get at (POOL)->arenaindex)
663 creates problems for some memory debuggers. The overwhelming advantage is
664 that this test determines whether an arbitrary address is controlled by
665 obmalloc in a small constant time, independent of the number of arenas
666 obmalloc controls. Since this test is needed at every entry point, it's
667 extremely desirable that it be this fast.
669 #define Py_ADDRESS_IN_RANGE(P, POOL) \
670 ((POOL)->arenaindex < maxarenas && \
671 (uptr)(P) - arenas[(POOL)->arenaindex].address < (uptr)ARENA_SIZE && \
672 arenas[(POOL)->arenaindex].address != 0)
675 /* This is only useful when running memory debuggers such as
676 * Purify or Valgrind. Uncomment to use.
679 #define Py_USING_MEMORY_DEBUGGER
681 #ifdef Py_USING_MEMORY_DEBUGGER
683 /* Py_ADDRESS_IN_RANGE may access uninitialized memory by design
684 * This leads to thousands of spurious warnings when using
685 * Purify or Valgrind. By making a function, we can easily
686 * suppress the uninitialized memory reads in this one function.
687 * So we won't ignore real errors elsewhere.
689 * Disable the macro and use a function.
692 #undef Py_ADDRESS_IN_RANGE
694 #if defined(__GNUC__) && ((__GNUC__ == 3) && (__GNUC_MINOR__ >= 1) || \
696 #define Py_NO_INLINE __attribute__((__noinline__))
701 /* Don't make static, to try to ensure this isn't inlined. */
702 int Py_ADDRESS_IN_RANGE(void *P
, poolp pool
) Py_NO_INLINE
;
706 /*==========================================================================*/
708 /* malloc. Note that nbytes==0 tries to return a non-NULL pointer, distinct
709 * from all other currently live pointers. This may not be possible.
713 * The basic blocks are ordered by decreasing execution frequency,
714 * which minimizes the number of jumps in the most common cases,
715 * improves branching prediction and instruction scheduling (small
716 * block allocations typically result in a couple of instructions).
717 * Unless the optimizer reorders everything, being too smart...
720 #undef PyObject_Malloc
722 PyObject_Malloc(size_t nbytes
)
730 * This implicitly redirects malloc(0).
732 if ((nbytes
- 1) < SMALL_REQUEST_THRESHOLD
) {
735 * Most frequent paths first
737 size
= (uint
)(nbytes
- 1) >> ALIGNMENT_SHIFT
;
738 pool
= usedpools
[size
+ size
];
739 if (pool
!= pool
->nextpool
) {
741 * There is a used pool for this size class.
742 * Pick up the head block of its free list.
745 bp
= pool
->freeblock
;
747 if ((pool
->freeblock
= *(block
**)bp
) != NULL
) {
752 * Reached the end of the free list, try to extend it.
754 if (pool
->nextoffset
<= pool
->maxnextoffset
) {
755 /* There is room for another block. */
756 pool
->freeblock
= (block
*)pool
+
758 pool
->nextoffset
+= INDEX2SIZE(size
);
759 *(block
**)(pool
->freeblock
) = NULL
;
763 /* Pool is full, unlink from used pools. */
764 next
= pool
->nextpool
;
765 pool
= pool
->prevpool
;
766 next
->prevpool
= pool
;
767 pool
->nextpool
= next
;
772 /* There isn't a pool of the right size class immediately
773 * available: use a free pool.
775 if (usable_arenas
== NULL
) {
776 /* No arena has a free pool: allocate a new arena. */
777 #ifdef WITH_MEMORY_LIMITS
778 if (narenas_currently_allocated
>= MAX_ARENAS
) {
783 usable_arenas
= new_arena();
784 if (usable_arenas
== NULL
) {
788 usable_arenas
->nextarena
=
789 usable_arenas
->prevarena
= NULL
;
791 assert(usable_arenas
->address
!= 0);
793 /* Try to get a cached free pool. */
794 pool
= usable_arenas
->freepools
;
796 /* Unlink from cached pools. */
797 usable_arenas
->freepools
= pool
->nextpool
;
799 /* This arena already had the smallest nfreepools
800 * value, so decreasing nfreepools doesn't change
801 * that, and we don't need to rearrange the
802 * usable_arenas list. However, if the arena has
803 * become wholly allocated, we need to remove its
804 * arena_object from usable_arenas.
806 --usable_arenas
->nfreepools
;
807 if (usable_arenas
->nfreepools
== 0) {
808 /* Wholly allocated: remove. */
809 assert(usable_arenas
->freepools
== NULL
);
810 assert(usable_arenas
->nextarena
== NULL
||
811 usable_arenas
->nextarena
->prevarena
==
814 usable_arenas
= usable_arenas
->nextarena
;
815 if (usable_arenas
!= NULL
) {
816 usable_arenas
->prevarena
= NULL
;
817 assert(usable_arenas
->address
!= 0);
821 /* nfreepools > 0: it must be that freepools
822 * isn't NULL, or that we haven't yet carved
823 * off all the arena's pools for the first
826 assert(usable_arenas
->freepools
!= NULL
||
827 usable_arenas
->pool_address
<=
828 (block
*)usable_arenas
->address
+
829 ARENA_SIZE
- POOL_SIZE
);
832 /* Frontlink to used pools. */
833 next
= usedpools
[size
+ size
]; /* == prev */
834 pool
->nextpool
= next
;
835 pool
->prevpool
= next
;
836 next
->nextpool
= pool
;
837 next
->prevpool
= pool
;
839 if (pool
->szidx
== size
) {
840 /* Luckily, this pool last contained blocks
841 * of the same size class, so its header
842 * and free list are already initialized.
844 bp
= pool
->freeblock
;
845 pool
->freeblock
= *(block
**)bp
;
850 * Initialize the pool header, set up the free list to
851 * contain just the second block, and return the first
855 size
= INDEX2SIZE(size
);
856 bp
= (block
*)pool
+ POOL_OVERHEAD
;
857 pool
->nextoffset
= POOL_OVERHEAD
+ (size
<< 1);
858 pool
->maxnextoffset
= POOL_SIZE
- size
;
859 pool
->freeblock
= bp
+ size
;
860 *(block
**)(pool
->freeblock
) = NULL
;
865 /* Carve off a new pool. */
866 assert(usable_arenas
->nfreepools
> 0);
867 assert(usable_arenas
->freepools
== NULL
);
868 pool
= (poolp
)usable_arenas
->pool_address
;
869 assert((block
*)pool
<= (block
*)usable_arenas
->address
+
870 ARENA_SIZE
- POOL_SIZE
);
871 pool
->arenaindex
= usable_arenas
- arenas
;
872 assert(&arenas
[pool
->arenaindex
] == usable_arenas
);
873 pool
->szidx
= DUMMY_SIZE_IDX
;
874 usable_arenas
->pool_address
+= POOL_SIZE
;
875 --usable_arenas
->nfreepools
;
877 if (usable_arenas
->nfreepools
== 0) {
878 assert(usable_arenas
->nextarena
== NULL
||
879 usable_arenas
->nextarena
->prevarena
==
881 /* Unlink the arena: it is completely allocated. */
882 usable_arenas
= usable_arenas
->nextarena
;
883 if (usable_arenas
!= NULL
) {
884 usable_arenas
->prevarena
= NULL
;
885 assert(usable_arenas
->address
!= 0);
892 /* The small block allocator ends here. */
895 /* Redirect the original request to the underlying (libc) allocator.
896 * We jump here on bigger requests, on error in the code above (as a
897 * last chance to serve the request) or when the max memory limit
902 return (void *)malloc(nbytes
);
909 PyObject_Free(void *p
)
916 if (p
== NULL
) /* free(NULL) has no effect */
920 if (Py_ADDRESS_IN_RANGE(p
, pool
)) {
921 /* We allocated this address. */
923 /* Link p to the start of the pool's freeblock list. Since
924 * the pool had at least the p block outstanding, the pool
925 * wasn't empty (so it's already in a usedpools[] list, or
926 * was full and is in no list -- it's not in the freeblocks
929 assert(pool
->ref
.count
> 0); /* else it was empty */
930 *(block
**)p
= lastfree
= pool
->freeblock
;
931 pool
->freeblock
= (block
*)p
;
933 struct arena_object
* ao
;
934 uint nf
; /* ao->nfreepools */
936 /* freeblock wasn't NULL, so the pool wasn't full,
937 * and the pool is in a usedpools[] list.
939 if (--pool
->ref
.count
!= 0) {
940 /* pool isn't empty: leave it in usedpools */
944 /* Pool is now empty: unlink from usedpools, and
945 * link to the front of freepools. This ensures that
946 * previously freed pools will be allocated later
947 * (being not referenced, they are perhaps paged out).
949 next
= pool
->nextpool
;
950 prev
= pool
->prevpool
;
951 next
->prevpool
= prev
;
952 prev
->nextpool
= next
;
954 /* Link the pool to freepools. This is a singly-linked
955 * list, and pool->prevpool isn't used there.
957 ao
= &arenas
[pool
->arenaindex
];
958 pool
->nextpool
= ao
->freepools
;
959 ao
->freepools
= pool
;
960 nf
= ++ao
->nfreepools
;
962 /* All the rest is arena management. We just freed
963 * a pool, and there are 4 cases for arena mgmt:
964 * 1. If all the pools are free, return the arena to
966 * 2. If this is the only free pool in the arena,
967 * add the arena back to the `usable_arenas` list.
968 * 3. If the "next" arena has a smaller count of free
969 * pools, we have to "slide this arena right" to
970 * restore that usable_arenas is sorted in order of
972 * 4. Else there's nothing more to do.
974 if (nf
== ao
->ntotalpools
) {
975 /* Case 1. First unlink ao from usable_arenas.
977 assert(ao
->prevarena
== NULL
||
978 ao
->prevarena
->address
!= 0);
979 assert(ao
->nextarena
== NULL
||
980 ao
->nextarena
->address
!= 0);
982 /* Fix the pointer in the prevarena, or the
983 * usable_arenas pointer.
985 if (ao
->prevarena
== NULL
) {
986 usable_arenas
= ao
->nextarena
;
987 assert(usable_arenas
== NULL
||
988 usable_arenas
->address
!= 0);
991 assert(ao
->prevarena
->nextarena
== ao
);
992 ao
->prevarena
->nextarena
=
995 /* Fix the pointer in the nextarena. */
996 if (ao
->nextarena
!= NULL
) {
997 assert(ao
->nextarena
->prevarena
== ao
);
998 ao
->nextarena
->prevarena
=
1001 /* Record that this arena_object slot is
1002 * available to be reused.
1004 ao
->nextarena
= unused_arena_objects
;
1005 unused_arena_objects
= ao
;
1007 /* Free the entire arena. */
1008 free((void *)ao
->address
);
1009 ao
->address
= 0; /* mark unassociated */
1010 --narenas_currently_allocated
;
1016 /* Case 2. Put ao at the head of
1017 * usable_arenas. Note that because
1018 * ao->nfreepools was 0 before, ao isn't
1019 * currently on the usable_arenas list.
1021 ao
->nextarena
= usable_arenas
;
1022 ao
->prevarena
= NULL
;
1024 usable_arenas
->prevarena
= ao
;
1026 assert(usable_arenas
->address
!= 0);
1031 /* If this arena is now out of order, we need to keep
1032 * the list sorted. The list is kept sorted so that
1033 * the "most full" arenas are used first, which allows
1034 * the nearly empty arenas to be completely freed. In
1035 * a few un-scientific tests, it seems like this
1036 * approach allowed a lot more memory to be freed.
1038 if (ao
->nextarena
== NULL
||
1039 nf
<= ao
->nextarena
->nfreepools
) {
1040 /* Case 4. Nothing to do. */
1044 /* Case 3: We have to move the arena towards the end
1045 * of the list, because it has more free pools than
1046 * the arena to its right.
1047 * First unlink ao from usable_arenas.
1049 if (ao
->prevarena
!= NULL
) {
1050 /* ao isn't at the head of the list */
1051 assert(ao
->prevarena
->nextarena
== ao
);
1052 ao
->prevarena
->nextarena
= ao
->nextarena
;
1055 /* ao is at the head of the list */
1056 assert(usable_arenas
== ao
);
1057 usable_arenas
= ao
->nextarena
;
1059 ao
->nextarena
->prevarena
= ao
->prevarena
;
1061 /* Locate the new insertion point by iterating over
1062 * the list, using our nextarena pointer.
1064 while (ao
->nextarena
!= NULL
&&
1065 nf
> ao
->nextarena
->nfreepools
) {
1066 ao
->prevarena
= ao
->nextarena
;
1067 ao
->nextarena
= ao
->nextarena
->nextarena
;
1070 /* Insert ao at this point. */
1071 assert(ao
->nextarena
== NULL
||
1072 ao
->prevarena
== ao
->nextarena
->prevarena
);
1073 assert(ao
->prevarena
->nextarena
== ao
->nextarena
);
1075 ao
->prevarena
->nextarena
= ao
;
1076 if (ao
->nextarena
!= NULL
)
1077 ao
->nextarena
->prevarena
= ao
;
1079 /* Verify that the swaps worked. */
1080 assert(ao
->nextarena
== NULL
||
1081 nf
<= ao
->nextarena
->nfreepools
);
1082 assert(ao
->prevarena
== NULL
||
1083 nf
> ao
->prevarena
->nfreepools
);
1084 assert(ao
->nextarena
== NULL
||
1085 ao
->nextarena
->prevarena
== ao
);
1086 assert((usable_arenas
== ao
&&
1087 ao
->prevarena
== NULL
) ||
1088 ao
->prevarena
->nextarena
== ao
);
1093 /* Pool was full, so doesn't currently live in any list:
1094 * link it to the front of the appropriate usedpools[] list.
1095 * This mimics LRU pool usage for new allocations and
1096 * targets optimal filling when several pools contain
1097 * blocks of the same size class.
1100 assert(pool
->ref
.count
> 0); /* else the pool is empty */
1102 next
= usedpools
[size
+ size
];
1103 prev
= next
->prevpool
;
1104 /* insert pool before next: prev <-> pool <-> next */
1105 pool
->nextpool
= next
;
1106 pool
->prevpool
= prev
;
1107 next
->prevpool
= pool
;
1108 prev
->nextpool
= pool
;
1113 /* We didn't allocate this address. */
1117 /* realloc. If p is NULL, this acts like malloc(nbytes). Else if nbytes==0,
1118 * then as the Python docs promise, we do not treat this like free(p), and
1119 * return a non-NULL result.
1122 #undef PyObject_Realloc
1124 PyObject_Realloc(void *p
, size_t nbytes
)
1131 return PyObject_Malloc(nbytes
);
1133 pool
= POOL_ADDR(p
);
1134 if (Py_ADDRESS_IN_RANGE(p
, pool
)) {
1135 /* We're in charge of this block */
1136 size
= INDEX2SIZE(pool
->szidx
);
1137 if (nbytes
<= size
) {
1138 /* The block is staying the same or shrinking. If
1139 * it's shrinking, there's a tradeoff: it costs
1140 * cycles to copy the block to a smaller size class,
1141 * but it wastes memory not to copy it. The
1142 * compromise here is to copy on shrink only if at
1143 * least 25% of size can be shaved off.
1145 if (4 * nbytes
> 3 * size
) {
1147 * or shrinking and new/old > 3/4.
1153 bp
= PyObject_Malloc(nbytes
);
1155 memcpy(bp
, p
, size
);
1160 /* We're not managing this block. If nbytes <=
1161 * SMALL_REQUEST_THRESHOLD, it's tempting to try to take over this
1162 * block. However, if we do, we need to copy the valid data from
1163 * the C-managed block to one of our blocks, and there's no portable
1164 * way to know how much of the memory space starting at p is valid.
1165 * As bug 1185883 pointed out the hard way, it's possible that the
1166 * C-managed block is "at the end" of allocated VM space, so that
1167 * a memory fault can occur if we try to copy nbytes bytes starting
1168 * at p. Instead we punt: let C continue to manage this block.
1171 return realloc(p
, nbytes
);
1172 /* C doesn't define the result of realloc(p, 0) (it may or may not
1173 * return NULL then), but Python's docs promise that nbytes==0 never
1174 * returns NULL. We don't pass 0 to realloc(), to avoid that endcase
1175 * to begin with. Even then, we can't be sure that realloc() won't
1182 #else /* ! WITH_PYMALLOC */
1184 /*==========================================================================*/
1185 /* pymalloc not enabled: Redirect the entry points to malloc. These will
1186 * only be used by extensions that are compiled with pymalloc enabled. */
1189 PyObject_Malloc(size_t n
)
1191 return PyMem_MALLOC(n
);
1195 PyObject_Realloc(void *p
, size_t n
)
1197 return PyMem_REALLOC(p
, n
);
1201 PyObject_Free(void *p
)
1205 #endif /* WITH_PYMALLOC */
1207 #ifdef PYMALLOC_DEBUG
1208 /*==========================================================================*/
1209 /* A x-platform debugging allocator. This doesn't manage memory directly,
1210 * it wraps a real allocator, adding extra debugging info to the memory blocks.
1213 /* Special bytes broadcast into debug memory blocks at appropriate times.
1214 * Strings of these are unlikely to be valid addresses, floats, ints or
1219 #undef FORBIDDENBYTE
1220 #define CLEANBYTE 0xCB /* clean (newly allocated) memory */
1221 #define DEADBYTE 0xDB /* dead (newly freed) memory */
1222 #define FORBIDDENBYTE 0xFB /* untouchable bytes at each end of a block */
1224 static size_t serialno
= 0; /* incremented on each debug {m,re}alloc */
1226 /* serialno is always incremented via calling this routine. The point is
1227 * to supply a single place to set a breakpoint.
1235 #define SST SIZEOF_SIZE_T
1237 /* Read sizeof(size_t) bytes at p as a big-endian size_t. */
1239 read_size_t(const void *p
)
1241 const uchar
*q
= (const uchar
*)p
;
1242 size_t result
= *q
++;
1245 for (i
= SST
; --i
> 0; ++q
)
1246 result
= (result
<< 8) | *q
;
1250 /* Write n as a big-endian size_t, MSB at address p, LSB at
1251 * p + sizeof(size_t) - 1.
1254 write_size_t(void *p
, size_t n
)
1256 uchar
*q
= (uchar
*)p
+ SST
- 1;
1259 for (i
= SST
; --i
>= 0; --q
) {
1260 *q
= (uchar
)(n
& 0xff);
1266 /* Is target in the list? The list is traversed via the nextpool pointers.
1267 * The list may be NULL-terminated, or circular. Return 1 if target is in
1271 pool_is_in_list(const poolp target
, poolp list
)
1273 poolp origlist
= list
;
1274 assert(target
!= NULL
);
1280 list
= list
->nextpool
;
1281 } while (list
!= NULL
&& list
!= origlist
);
1286 #define pool_is_in_list(X, Y) 1
1288 #endif /* Py_DEBUG */
1290 /* Let S = sizeof(size_t). The debug malloc asks for 4*S extra bytes and
1291 fills them with useful stuff, here calling the underlying malloc's result p:
1294 Number of bytes originally asked for. This is a size_t, big-endian (easier
1295 to read in a memory dump).
1297 Copies of FORBIDDENBYTE. Used to catch under- writes and reads.
1299 The requested memory, filled with copies of CLEANBYTE.
1300 Used to catch reference to uninitialized memory.
1301 &p[2*S] is returned. Note that this is 8-byte aligned if pymalloc
1302 handled the request itself.
1304 Copies of FORBIDDENBYTE. Used to catch over- writes and reads.
1305 p[2*S+n+S: 2*S+n+2*S]
1306 A serial number, incremented by 1 on each call to _PyObject_DebugMalloc
1307 and _PyObject_DebugRealloc.
1308 This is a big-endian size_t.
1309 If "bad memory" is detected later, the serial number gives an
1310 excellent way to set a breakpoint on the next run, to capture the
1311 instant at which this block was passed out.
1315 _PyObject_DebugMalloc(size_t nbytes
)
1317 uchar
*p
; /* base address of malloc'ed block */
1318 uchar
*tail
; /* p + 2*SST + nbytes == pointer to tail pad bytes */
1319 size_t total
; /* nbytes + 4*SST */
1322 total
= nbytes
+ 4*SST
;
1324 /* overflow: can't represent total as a size_t */
1327 p
= (uchar
*)PyObject_Malloc(total
);
1331 write_size_t(p
, nbytes
);
1332 memset(p
+ SST
, FORBIDDENBYTE
, SST
);
1335 memset(p
+ 2*SST
, CLEANBYTE
, nbytes
);
1337 tail
= p
+ 2*SST
+ nbytes
;
1338 memset(tail
, FORBIDDENBYTE
, SST
);
1339 write_size_t(tail
+ SST
, serialno
);
1344 /* The debug free first checks the 2*SST bytes on each end for sanity (in
1345 particular, that the FORBIDDENBYTEs are still intact).
1346 Then fills the original bytes with DEADBYTE.
1347 Then calls the underlying free.
1350 _PyObject_DebugFree(void *p
)
1352 uchar
*q
= (uchar
*)p
- 2*SST
; /* address returned from malloc */
1357 _PyObject_DebugCheckAddress(p
);
1358 nbytes
= read_size_t(q
);
1360 memset(q
, DEADBYTE
, nbytes
);
1365 _PyObject_DebugRealloc(void *p
, size_t nbytes
)
1367 uchar
*q
= (uchar
*)p
;
1369 size_t total
; /* nbytes + 4*SST */
1370 size_t original_nbytes
;
1374 return _PyObject_DebugMalloc(nbytes
);
1376 _PyObject_DebugCheckAddress(p
);
1378 original_nbytes
= read_size_t(q
- 2*SST
);
1379 total
= nbytes
+ 4*SST
;
1381 /* overflow: can't represent total as a size_t */
1384 if (nbytes
< original_nbytes
) {
1385 /* shrinking: mark old extra memory dead */
1386 memset(q
+ nbytes
, DEADBYTE
, original_nbytes
- nbytes
);
1389 /* Resize and add decorations. */
1390 q
= (uchar
*)PyObject_Realloc(q
- 2*SST
, total
);
1394 write_size_t(q
, nbytes
);
1395 for (i
= 0; i
< SST
; ++i
)
1396 assert(q
[SST
+ i
] == FORBIDDENBYTE
);
1399 memset(tail
, FORBIDDENBYTE
, SST
);
1400 write_size_t(tail
+ SST
, serialno
);
1402 if (nbytes
> original_nbytes
) {
1403 /* growing: mark new extra memory clean */
1404 memset(q
+ original_nbytes
, CLEANBYTE
,
1405 nbytes
- original_nbytes
);
1411 /* Check the forbidden bytes on both ends of the memory allocated for p.
1412 * If anything is wrong, print info to stderr via _PyObject_DebugDumpAddress,
1413 * and call Py_FatalError to kill the program.
1416 _PyObject_DebugCheckAddress(const void *p
)
1418 const uchar
*q
= (const uchar
*)p
;
1425 msg
= "didn't expect a NULL pointer";
1429 /* Check the stuff at the start of p first: if there's underwrite
1430 * corruption, the number-of-bytes field may be nuts, and checking
1431 * the tail could lead to a segfault then.
1433 for (i
= SST
; i
>= 1; --i
) {
1434 if (*(q
-i
) != FORBIDDENBYTE
) {
1435 msg
= "bad leading pad byte";
1440 nbytes
= read_size_t(q
- 2*SST
);
1442 for (i
= 0; i
< SST
; ++i
) {
1443 if (tail
[i
] != FORBIDDENBYTE
) {
1444 msg
= "bad trailing pad byte";
1452 _PyObject_DebugDumpAddress(p
);
1456 /* Display info to stderr about the memory block at p. */
1458 _PyObject_DebugDumpAddress(const void *p
)
1460 const uchar
*q
= (const uchar
*)p
;
1462 size_t nbytes
, serial
;
1466 fprintf(stderr
, "Debug memory block at address p=%p:\n", p
);
1470 nbytes
= read_size_t(q
- 2*SST
);
1471 fprintf(stderr
, " %" PY_FORMAT_SIZE_T
"u bytes originally "
1472 "requested\n", nbytes
);
1474 /* In case this is nuts, check the leading pad bytes first. */
1475 fprintf(stderr
, " The %d pad bytes at p-%d are ", SST
, SST
);
1477 for (i
= 1; i
<= SST
; ++i
) {
1478 if (*(q
-i
) != FORBIDDENBYTE
) {
1484 fputs("FORBIDDENBYTE, as expected.\n", stderr
);
1486 fprintf(stderr
, "not all FORBIDDENBYTE (0x%02x):\n",
1488 for (i
= SST
; i
>= 1; --i
) {
1489 const uchar byte
= *(q
-i
);
1490 fprintf(stderr
, " at p-%d: 0x%02x", i
, byte
);
1491 if (byte
!= FORBIDDENBYTE
)
1492 fputs(" *** OUCH", stderr
);
1493 fputc('\n', stderr
);
1496 fputs(" Because memory is corrupted at the start, the "
1497 "count of bytes requested\n"
1498 " may be bogus, and checking the trailing pad "
1499 "bytes may segfault.\n", stderr
);
1503 fprintf(stderr
, " The %d pad bytes at tail=%p are ", SST
, tail
);
1505 for (i
= 0; i
< SST
; ++i
) {
1506 if (tail
[i
] != FORBIDDENBYTE
) {
1512 fputs("FORBIDDENBYTE, as expected.\n", stderr
);
1514 fprintf(stderr
, "not all FORBIDDENBYTE (0x%02x):\n",
1516 for (i
= 0; i
< SST
; ++i
) {
1517 const uchar byte
= tail
[i
];
1518 fprintf(stderr
, " at tail+%d: 0x%02x",
1520 if (byte
!= FORBIDDENBYTE
)
1521 fputs(" *** OUCH", stderr
);
1522 fputc('\n', stderr
);
1526 serial
= read_size_t(tail
+ SST
);
1527 fprintf(stderr
, " The block was made by call #%" PY_FORMAT_SIZE_T
1528 "u to debug malloc/realloc.\n", serial
);
1532 fputs(" Data at p:", stderr
);
1533 /* print up to 8 bytes at the start */
1534 while (q
< tail
&& i
< 8) {
1535 fprintf(stderr
, " %02x", *q
);
1539 /* and up to 8 at the end */
1542 fputs(" ...", stderr
);
1546 fprintf(stderr
, " %02x", *q
);
1550 fputc('\n', stderr
);
1555 printone(const char* msg
, size_t value
)
1559 size_t origvalue
= value
;
1562 for (i
= (int)strlen(msg
); i
< 35; ++i
)
1566 /* Write the value with commas. */
1572 size_t nextvalue
= value
/ 10;
1573 uint digit
= (uint
)(value
- nextvalue
* 10);
1575 buf
[i
--] = (char)(digit
+ '0');
1577 if (k
== 0 && value
&& i
>= 0) {
1581 } while (value
&& i
>= 0);
1590 /* Print summary info to stderr about the state of pymalloc's structures.
1591 * In Py_DEBUG mode, also perform some expensive internal consistency
1595 _PyObject_DebugMallocStats(void)
1598 const uint numclasses
= SMALL_REQUEST_THRESHOLD
>> ALIGNMENT_SHIFT
;
1599 /* # of pools, allocated blocks, and free blocks per class index */
1600 size_t numpools
[SMALL_REQUEST_THRESHOLD
>> ALIGNMENT_SHIFT
];
1601 size_t numblocks
[SMALL_REQUEST_THRESHOLD
>> ALIGNMENT_SHIFT
];
1602 size_t numfreeblocks
[SMALL_REQUEST_THRESHOLD
>> ALIGNMENT_SHIFT
];
1603 /* total # of allocated bytes in used and full pools */
1604 size_t allocated_bytes
= 0;
1605 /* total # of available bytes in used pools */
1606 size_t available_bytes
= 0;
1607 /* # of free pools + pools not yet carved out of current arena */
1608 uint numfreepools
= 0;
1609 /* # of bytes for arena alignment padding */
1610 size_t arena_alignment
= 0;
1611 /* # of bytes in used and full pools used for pool_headers */
1612 size_t pool_header_bytes
= 0;
1613 /* # of bytes in used and full pools wasted due to quantization,
1614 * i.e. the necessarily leftover space at the ends of used and
1617 size_t quantization
= 0;
1618 /* # of arenas actually allocated. */
1620 /* running total -- should equal narenas * ARENA_SIZE */
1624 fprintf(stderr
, "Small block threshold = %d, in %u size classes.\n",
1625 SMALL_REQUEST_THRESHOLD
, numclasses
);
1627 for (i
= 0; i
< numclasses
; ++i
)
1628 numpools
[i
] = numblocks
[i
] = numfreeblocks
[i
] = 0;
1630 /* Because full pools aren't linked to from anything, it's easiest
1631 * to march over all the arenas. If we're lucky, most of the memory
1632 * will be living in full pools -- would be a shame to miss them.
1634 for (i
= 0; i
< maxarenas
; ++i
) {
1637 uptr base
= arenas
[i
].address
;
1639 /* Skip arenas which are not allocated. */
1640 if (arenas
[i
].address
== (uptr
)NULL
)
1644 poolsinarena
= arenas
[i
].ntotalpools
;
1645 numfreepools
+= arenas
[i
].nfreepools
;
1647 /* round up to pool alignment */
1648 if (base
& (uptr
)POOL_SIZE_MASK
) {
1649 arena_alignment
+= POOL_SIZE
;
1650 base
&= ~(uptr
)POOL_SIZE_MASK
;
1654 /* visit every pool in the arena */
1655 assert(base
<= (uptr
) arenas
[i
].pool_address
);
1657 base
< (uptr
) arenas
[i
].pool_address
;
1658 ++j
, base
+= POOL_SIZE
) {
1659 poolp p
= (poolp
)base
;
1660 const uint sz
= p
->szidx
;
1663 if (p
->ref
.count
== 0) {
1664 /* currently unused */
1665 assert(pool_is_in_list(p
, arenas
[i
].freepools
));
1669 numblocks
[sz
] += p
->ref
.count
;
1670 freeblocks
= NUMBLOCKS(sz
) - p
->ref
.count
;
1671 numfreeblocks
[sz
] += freeblocks
;
1674 assert(pool_is_in_list(p
, usedpools
[sz
+ sz
]));
1678 assert(narenas
== narenas_currently_allocated
);
1680 fputc('\n', stderr
);
1681 fputs("class size num pools blocks in use avail blocks\n"
1682 "----- ---- --------- ------------- ------------\n",
1685 for (i
= 0; i
< numclasses
; ++i
) {
1686 size_t p
= numpools
[i
];
1687 size_t b
= numblocks
[i
];
1688 size_t f
= numfreeblocks
[i
];
1689 uint size
= INDEX2SIZE(i
);
1691 assert(b
== 0 && f
== 0);
1694 fprintf(stderr
, "%5u %6u "
1695 "%11" PY_FORMAT_SIZE_T
"u "
1696 "%15" PY_FORMAT_SIZE_T
"u "
1697 "%13" PY_FORMAT_SIZE_T
"u\n",
1699 allocated_bytes
+= b
* size
;
1700 available_bytes
+= f
* size
;
1701 pool_header_bytes
+= p
* POOL_OVERHEAD
;
1702 quantization
+= p
* ((POOL_SIZE
- POOL_OVERHEAD
) % size
);
1704 fputc('\n', stderr
);
1705 (void)printone("# times object malloc called", serialno
);
1707 (void)printone("# arenas allocated total", ntimes_arena_allocated
);
1708 (void)printone("# arenas reclaimed", ntimes_arena_allocated
- narenas
);
1709 (void)printone("# arenas highwater mark", narenas_highwater
);
1710 (void)printone("# arenas allocated current", narenas
);
1712 PyOS_snprintf(buf
, sizeof(buf
),
1713 "%" PY_FORMAT_SIZE_T
"u arenas * %d bytes/arena",
1714 narenas
, ARENA_SIZE
);
1715 (void)printone(buf
, narenas
* ARENA_SIZE
);
1717 fputc('\n', stderr
);
1719 total
= printone("# bytes in allocated blocks", allocated_bytes
);
1720 total
+= printone("# bytes in available blocks", available_bytes
);
1722 PyOS_snprintf(buf
, sizeof(buf
),
1723 "%u unused pools * %d bytes", numfreepools
, POOL_SIZE
);
1724 total
+= printone(buf
, (size_t)numfreepools
* POOL_SIZE
);
1726 total
+= printone("# bytes lost to pool headers", pool_header_bytes
);
1727 total
+= printone("# bytes lost to quantization", quantization
);
1728 total
+= printone("# bytes lost to arena alignment", arena_alignment
);
1729 (void)printone("Total", total
);
1732 #endif /* PYMALLOC_DEBUG */
1734 #ifdef Py_USING_MEMORY_DEBUGGER
1735 /* Make this function last so gcc won't inline it since the definition is
1736 * after the reference.
1739 Py_ADDRESS_IN_RANGE(void *P
, poolp pool
)
1741 return pool
->arenaindex
< maxarenas
&&
1742 (uptr
)P
- arenas
[pool
->arenaindex
].address
< (uptr
)ARENA_SIZE
&&
1743 arenas
[pool
->arenaindex
].address
!= 0;