blob: 8ec5dfccb88a51671729b428bfd8d44df029afe6 [file] [log] [blame]
Tim Peters1221c0a2002-03-23 00:20:15 +00001#include "Python.h"
2
3#ifdef WITH_PYMALLOC
4
Neil Schemenauera35c6882001-02-27 04:45:05 +00005/* An object allocator for Python.
6
7 Here is an introduction to the layers of the Python memory architecture,
8 showing where the object allocator is actually used (layer +2), It is
9 called for every object allocation and deallocation (PyObject_New/Del),
10 unless the object-specific allocators implement a proprietary allocation
11 scheme (ex.: ints use a simple free list). This is also the place where
12 the cyclic garbage collector operates selectively on container objects.
13
14
15 Object-specific allocators
16 _____ ______ ______ ________
17 [ int ] [ dict ] [ list ] ... [ string ] Python core |
18+3 | <----- Object-specific memory -----> | <-- Non-object memory --> |
19 _______________________________ | |
20 [ Python's object allocator ] | |
21+2 | ####### Object memory ####### | <------ Internal buffers ------> |
22 ______________________________________________________________ |
23 [ Python's raw memory allocator (PyMem_ API) ] |
24+1 | <----- Python memory (under PyMem manager's control) ------> | |
25 __________________________________________________________________
26 [ Underlying general-purpose allocator (ex: C library malloc) ]
27 0 | <------ Virtual memory allocated for the python process -------> |
28
29 =========================================================================
30 _______________________________________________________________________
31 [ OS-specific Virtual Memory Manager (VMM) ]
32-1 | <--- Kernel dynamic storage allocation & management (page-based) ---> |
33 __________________________________ __________________________________
34 [ ] [ ]
35-2 | <-- Physical memory: ROM/RAM --> | | <-- Secondary storage (swap) --> |
36
37*/
38/*==========================================================================*/
39
40/* A fast, special-purpose memory allocator for small blocks, to be used
41 on top of a general-purpose malloc -- heavily based on previous art. */
42
43/* Vladimir Marangozov -- August 2000 */
44
45/*
46 * "Memory management is where the rubber meets the road -- if we do the wrong
47 * thing at any level, the results will not be good. And if we don't make the
48 * levels work well together, we are in serious trouble." (1)
49 *
50 * (1) Paul R. Wilson, Mark S. Johnstone, Michael Neely, and David Boles,
51 * "Dynamic Storage Allocation: A Survey and Critical Review",
52 * in Proc. 1995 Int'l. Workshop on Memory Management, September 1995.
53 */
54
55/* #undef WITH_MEMORY_LIMITS */ /* disable mem limit checks */
Neil Schemenauera35c6882001-02-27 04:45:05 +000056
57/*==========================================================================*/
58
59/*
Neil Schemenauera35c6882001-02-27 04:45:05 +000060 * Allocation strategy abstract:
61 *
62 * For small requests, the allocator sub-allocates <Big> blocks of memory.
63 * Requests greater than 256 bytes are routed to the system's allocator.
Tim Petersce7fb9b2002-03-23 00:28:57 +000064 *
Neil Schemenauera35c6882001-02-27 04:45:05 +000065 * Small requests are grouped in size classes spaced 8 bytes apart, due
66 * to the required valid alignment of the returned address. Requests of
67 * a particular size are serviced from memory pools of 4K (one VMM page).
68 * Pools are fragmented on demand and contain free lists of blocks of one
69 * particular size class. In other words, there is a fixed-size allocator
70 * for each size class. Free pools are shared by the different allocators
71 * thus minimizing the space reserved for a particular size class.
72 *
73 * This allocation strategy is a variant of what is known as "simple
74 * segregated storage based on array of free lists". The main drawback of
75 * simple segregated storage is that we might end up with lot of reserved
76 * memory for the different free lists, which degenerate in time. To avoid
77 * this, we partition each free list in pools and we share dynamically the
78 * reserved space between all free lists. This technique is quite efficient
79 * for memory intensive programs which allocate mainly small-sized blocks.
80 *
81 * For small requests we have the following table:
82 *
83 * Request in bytes Size of allocated block Size class idx
84 * ----------------------------------------------------------------
85 * 1-8 8 0
86 * 9-16 16 1
87 * 17-24 24 2
88 * 25-32 32 3
89 * 33-40 40 4
90 * 41-48 48 5
91 * 49-56 56 6
92 * 57-64 64 7
93 * 65-72 72 8
94 * ... ... ...
95 * 241-248 248 30
96 * 249-256 256 31
Tim Petersce7fb9b2002-03-23 00:28:57 +000097 *
Neil Schemenauera35c6882001-02-27 04:45:05 +000098 * 0, 257 and up: routed to the underlying allocator.
99 */
100
101/*==========================================================================*/
102
103/*
104 * -- Main tunable settings section --
105 */
106
107/*
108 * Alignment of addresses returned to the user. 8-bytes alignment works
109 * on most current architectures (with 32-bit or 64-bit address busses).
110 * The alignment value is also used for grouping small requests in size
111 * classes spaced ALIGNMENT bytes apart.
112 *
113 * You shouldn't change this unless you know what you are doing.
114 */
Neil Schemenauera35c6882001-02-27 04:45:05 +0000115#define ALIGNMENT 8 /* must be 2^N */
116#define ALIGNMENT_SHIFT 3
117#define ALIGNMENT_MASK (ALIGNMENT - 1)
118
119/*
120 * Max size threshold below which malloc requests are considered to be
121 * small enough in order to use preallocated memory pools. You can tune
122 * this value according to your application behaviour and memory needs.
123 *
124 * The following invariants must hold:
125 * 1) ALIGNMENT <= SMALL_REQUEST_THRESHOLD <= 256
Tim Petersd97a1c02002-03-30 06:09:22 +0000126 * 2) SMALL_REQUEST_THRESHOLD is evenly divisible by ALIGNMENT
Neil Schemenauera35c6882001-02-27 04:45:05 +0000127 *
128 * Although not required, for better performance and space efficiency,
129 * it is recommended that SMALL_REQUEST_THRESHOLD is set to a power of 2.
130 */
Tim Petersd97a1c02002-03-30 06:09:22 +0000131#define SMALL_REQUEST_THRESHOLD 256
Neil Schemenauera35c6882001-02-27 04:45:05 +0000132#define NB_SMALL_SIZE_CLASSES (SMALL_REQUEST_THRESHOLD / ALIGNMENT)
133
134/*
135 * The system's VMM page size can be obtained on most unices with a
136 * getpagesize() call or deduced from various header files. To make
137 * things simpler, we assume that it is 4K, which is OK for most systems.
138 * It is probably better if this is the native page size, but it doesn't
139 * have to be.
140 */
Neil Schemenauera35c6882001-02-27 04:45:05 +0000141#define SYSTEM_PAGE_SIZE (4 * 1024)
142#define SYSTEM_PAGE_SIZE_MASK (SYSTEM_PAGE_SIZE - 1)
143
144/*
145 * Maximum amount of memory managed by the allocator for small requests.
146 */
Neil Schemenauera35c6882001-02-27 04:45:05 +0000147#ifdef WITH_MEMORY_LIMITS
148#ifndef SMALL_MEMORY_LIMIT
149#define SMALL_MEMORY_LIMIT (64 * 1024 * 1024) /* 64 MB -- more? */
150#endif
151#endif
152
153/*
154 * The allocator sub-allocates <Big> blocks of memory (called arenas) aligned
155 * on a page boundary. This is a reserved virtual address space for the
156 * current process (obtained through a malloc call). In no way this means
157 * that the memory arenas will be used entirely. A malloc(<Big>) is usually
158 * an address range reservation for <Big> bytes, unless all pages within this
159 * space are referenced subsequently. So malloc'ing big blocks and not using
160 * them does not mean "wasting memory". It's an addressable range wastage...
161 *
162 * Therefore, allocating arenas with malloc is not optimal, because there is
163 * some address space wastage, but this is the most portable way to request
Tim Petersd97a1c02002-03-30 06:09:22 +0000164 * memory from the system across various platforms.
Neil Schemenauera35c6882001-02-27 04:45:05 +0000165 */
Tim Peters3c83df22002-03-30 07:04:41 +0000166#define ARENA_SIZE (256 << 10) /* 256KB */
Neil Schemenauera35c6882001-02-27 04:45:05 +0000167
168#ifdef WITH_MEMORY_LIMITS
169#define MAX_ARENAS (SMALL_MEMORY_LIMIT / ARENA_SIZE)
170#endif
171
172/*
173 * Size of the pools used for small blocks. Should be a power of 2,
Tim Petersc2ce91a2002-03-30 21:36:04 +0000174 * between 1K and SYSTEM_PAGE_SIZE, that is: 1k, 2k, 4k.
Neil Schemenauera35c6882001-02-27 04:45:05 +0000175 */
Neil Schemenauera35c6882001-02-27 04:45:05 +0000176#define POOL_SIZE SYSTEM_PAGE_SIZE /* must be 2^N */
177#define POOL_SIZE_MASK SYSTEM_PAGE_SIZE_MASK
Neil Schemenauera35c6882001-02-27 04:45:05 +0000178
179/*
180 * -- End of tunable settings section --
181 */
182
183/*==========================================================================*/
184
185/*
186 * Locking
187 *
188 * To reduce lock contention, it would probably be better to refine the
189 * crude function locking with per size class locking. I'm not positive
190 * however, whether it's worth switching to such locking policy because
191 * of the performance penalty it might introduce.
192 *
193 * The following macros describe the simplest (should also be the fastest)
194 * lock object on a particular platform and the init/fini/lock/unlock
195 * operations on it. The locks defined here are not expected to be recursive
196 * because it is assumed that they will always be called in the order:
197 * INIT, [LOCK, UNLOCK]*, FINI.
198 */
199
200/*
201 * Python's threads are serialized, so object malloc locking is disabled.
202 */
203#define SIMPLELOCK_DECL(lock) /* simple lock declaration */
204#define SIMPLELOCK_INIT(lock) /* allocate (if needed) and initialize */
205#define SIMPLELOCK_FINI(lock) /* free/destroy an existing lock */
206#define SIMPLELOCK_LOCK(lock) /* acquire released lock */
207#define SIMPLELOCK_UNLOCK(lock) /* release acquired lock */
208
209/*
210 * Basic types
211 * I don't care if these are defined in <sys/types.h> or elsewhere. Axiom.
212 */
Neil Schemenauera35c6882001-02-27 04:45:05 +0000213#undef uchar
214#define uchar unsigned char /* assuming == 8 bits */
215
Neil Schemenauera35c6882001-02-27 04:45:05 +0000216#undef uint
217#define uint unsigned int /* assuming >= 16 bits */
218
219#undef ulong
220#define ulong unsigned long /* assuming >= 32 bits */
221
Tim Petersd97a1c02002-03-30 06:09:22 +0000222#undef uptr
223#define uptr Py_uintptr_t
224
Neil Schemenauera35c6882001-02-27 04:45:05 +0000225/* When you say memory, my mind reasons in terms of (pointers to) blocks */
226typedef uchar block;
227
228/* Pool for small blocks */
229struct pool_header {
Tim Petersb2336522001-03-11 18:36:13 +0000230 union { block *_padding;
Neil Schemenauera35c6882001-02-27 04:45:05 +0000231 uint count; } ref; /* number of allocated blocks */
232 block *freeblock; /* pool's free list head */
233 struct pool_header *nextpool; /* next pool of this size class */
234 struct pool_header *prevpool; /* previous pool "" */
Tim Peters1d99af82002-03-30 10:35:09 +0000235 uint arenaindex; /* index into arenas of base adr */
Neil Schemenauera35c6882001-02-27 04:45:05 +0000236 uint szidx; /* block size class index */
237 uint capacity; /* pool capacity in # of blocks */
238};
239
240typedef struct pool_header *poolp;
241
242#undef ROUNDUP
243#define ROUNDUP(x) (((x) + ALIGNMENT_MASK) & ~ALIGNMENT_MASK)
244#define POOL_OVERHEAD ROUNDUP(sizeof(struct pool_header))
245
246#define DUMMY_SIZE_IDX 0xffff /* size class of newly cached pools */
247
Tim Petersd97a1c02002-03-30 06:09:22 +0000248/* Round pointer P down to the closest pool-aligned address <= P, as a poolp */
249#define POOL_ADDR(P) \
250 ((poolp)((uptr)(P) & ~(uptr)POOL_SIZE_MASK))
251
Neil Schemenauera35c6882001-02-27 04:45:05 +0000252/*==========================================================================*/
253
254/*
255 * This malloc lock
256 */
Tim Petersb2336522001-03-11 18:36:13 +0000257SIMPLELOCK_DECL(_malloc_lock);
258#define LOCK() SIMPLELOCK_LOCK(_malloc_lock)
259#define UNLOCK() SIMPLELOCK_UNLOCK(_malloc_lock)
260#define LOCK_INIT() SIMPLELOCK_INIT(_malloc_lock)
261#define LOCK_FINI() SIMPLELOCK_FINI(_malloc_lock)
Neil Schemenauera35c6882001-02-27 04:45:05 +0000262
263/*
Tim Peters1e16db62002-03-31 01:05:22 +0000264 * Pool table -- headed, circular, doubly-linked lists of partially used pools.
265
266This is involved. For an index i, usedpools[i+i] is the header for a list of
267all partially used pools holding small blocks with "size class idx" i. So
268usedpools[0] corresponds to blocks of size 8, usedpools[2] to blocks of size
26916, and so on: index 2*i <-> blocks of size (i+1)<<ALIGNMENT_SHIFT.
270
271The partially used pools for a given index are linked together via their
272pool_header's prevpool and nextpool members. "Partially used" means at least
273one block in the pool is currently allocated, *and* at least one block in the
274pool is not currently allocated.
275
276When all blocks in a pool are allocated, the pool is unlinked from the list,
277and isn't linked to from anything anymore (you can't find it then from
278anything obmalloc.c knows about); the pool's own prevpool and nextpool
279pointers are set to point to itself. The comments say the pool "is full" then.
280
281When a small block is returned to pymalloc, there are two cases. If its pool
282was full, its pool is relinked into the appropriate usedpools[] list, at the
283front (so the next allocation of the same size class will be taken from this
284pool). Else its pool was not full, the pool is already in a usedpools[]
285list, and isn't moved. Instead the block is just linked to the front of the
286pool's own freeblock singly-linked list. However, if that makes the pool
287entirely free of allocated blocks (the comments say the pool "is empty" then),
288the pool is unlinked from usedpools[], and inserted at the front of the
289(file static) singly-linked freepools list, via the pool header's nextpool
290member; prevpool is meaningless in this case. Pools put on the freepools
291list can be changed to belong to a different size class.
292
293Major obscurity: While the usedpools vector is declared to have poolp
294entries, it doesn't really. It really contains two pointers per (conceptual)
295poolp entry, the nextpool and prevpool members of a pool_header. The
296excruciating initialization code below fools C so that
297
298 usedpool[i+i]
299
300"acts like" a genuine poolp, but only so long as you only reference its
301nextpool and prevpool members. The "- 2*sizeof(block *)" gibberish is
302compensating for that a pool_header's nextpool and prevpool members
303immediately follow a pool_header's first two members:
304
305 union { block *_padding;
306 uint count; } ref;
307 block *freeblock;
308
309each of which consume sizeof(block *) bytes. So what usedpools[i+i] really
310contains is a fudged-up pointer p such that *if* C believes it's a poolp
311pointer, then p->nextpool and p->prevpool are both p (meaning that the headed
312circular list is empty).
313
314It's unclear why the usedpools setup is so convoluted. It could be to
315minimize the amount of cache required to hold this heavily-referenced table
316(which only *needs* the two interpool pointer members of a pool_header). OTOH,
317referencing code has to remember to "double the index" and doing so isn't
318free, usedpools[0] isn't a strictly legal pointer, and we're crucially relying
319on that C doesn't insert any padding anywhere in a pool_header at or before
320the prevpool member.
321**************************************************************************** */
322
Neil Schemenauera35c6882001-02-27 04:45:05 +0000323#define PTA(x) ((poolp )((uchar *)&(usedpools[2*(x)]) - 2*sizeof(block *)))
324#define PT(x) PTA(x), PTA(x)
325
326static poolp usedpools[2 * ((NB_SMALL_SIZE_CLASSES + 7) / 8) * 8] = {
327 PT(0), PT(1), PT(2), PT(3), PT(4), PT(5), PT(6), PT(7)
328#if NB_SMALL_SIZE_CLASSES > 8
329 , PT(8), PT(9), PT(10), PT(11), PT(12), PT(13), PT(14), PT(15)
330#if NB_SMALL_SIZE_CLASSES > 16
331 , PT(16), PT(17), PT(18), PT(19), PT(20), PT(21), PT(22), PT(23)
332#if NB_SMALL_SIZE_CLASSES > 24
333 , PT(24), PT(25), PT(26), PT(27), PT(28), PT(29), PT(30), PT(31)
334#if NB_SMALL_SIZE_CLASSES > 32
335 , PT(32), PT(33), PT(34), PT(35), PT(36), PT(37), PT(38), PT(39)
336#if NB_SMALL_SIZE_CLASSES > 40
337 , PT(40), PT(41), PT(42), PT(43), PT(44), PT(45), PT(46), PT(47)
338#if NB_SMALL_SIZE_CLASSES > 48
339 , PT(48), PT(49), PT(50), PT(51), PT(52), PT(53), PT(54), PT(55)
340#if NB_SMALL_SIZE_CLASSES > 56
341 , PT(56), PT(57), PT(58), PT(59), PT(60), PT(61), PT(62), PT(63)
342#endif /* NB_SMALL_SIZE_CLASSES > 56 */
343#endif /* NB_SMALL_SIZE_CLASSES > 48 */
344#endif /* NB_SMALL_SIZE_CLASSES > 40 */
345#endif /* NB_SMALL_SIZE_CLASSES > 32 */
346#endif /* NB_SMALL_SIZE_CLASSES > 24 */
347#endif /* NB_SMALL_SIZE_CLASSES > 16 */
348#endif /* NB_SMALL_SIZE_CLASSES > 8 */
349};
350
351/*
352 * Free (cached) pools
353 */
354static poolp freepools = NULL; /* free list for cached pools */
355
Tim Petersd97a1c02002-03-30 06:09:22 +0000356/*==========================================================================*/
357/* Arena management. */
Neil Schemenauera35c6882001-02-27 04:45:05 +0000358
Tim Petersd97a1c02002-03-30 06:09:22 +0000359/* arenas is a vector of arena base addresses, in order of allocation time.
360 * arenas currently contains narenas entries, and has space allocated
361 * for at most maxarenas entries.
362 *
363 * CAUTION: See the long comment block about thread safety in new_arena():
364 * the code currently relies in deep ways on that this vector only grows,
365 * and only grows by appending at the end. For now we never return an arena
366 * to the OS.
367 */
Tim Petersc2ce91a2002-03-30 21:36:04 +0000368static uptr *volatile arenas = NULL; /* the pointer itself is volatile */
369static volatile uint narenas = 0;
Tim Peters1d99af82002-03-30 10:35:09 +0000370static uint maxarenas = 0;
Tim Petersd97a1c02002-03-30 06:09:22 +0000371
Tim Peters3c83df22002-03-30 07:04:41 +0000372/* Number of pools still available to be allocated in the current arena. */
373static uint nfreepools = 0;
Tim Petersd97a1c02002-03-30 06:09:22 +0000374
Tim Peters3c83df22002-03-30 07:04:41 +0000375/* Free space start address in current arena. This is pool-aligned. */
Tim Petersd97a1c02002-03-30 06:09:22 +0000376static block *arenabase = NULL;
377
378#if 0
379static ulong wasmine = 0;
380static ulong wasntmine = 0;
381
382static void
383dumpem(void *ptr)
384{
385 if (ptr)
386 printf("inserted new arena at %08x\n", ptr);
Tim Peters1d99af82002-03-30 10:35:09 +0000387 printf("# arenas %u\n", narenas);
Tim Petersd97a1c02002-03-30 06:09:22 +0000388 printf("was mine %lu wasn't mine %lu\n", wasmine, wasntmine);
389}
390#define INCMINE ++wasmine
391#define INCTHEIRS ++wasntmine
392
393#else
394#define dumpem(ptr)
395#define INCMINE
396#define INCTHEIRS
397#endif
398
399/* Allocate a new arena and return its base address. If we run out of
400 * memory, return NULL.
401 */
402static block *
403new_arena(void)
404{
Tim Peters3c83df22002-03-30 07:04:41 +0000405 uint excess; /* number of bytes above pool alignment */
406 block *bp = (block *)PyMem_MALLOC(ARENA_SIZE);
Tim Petersd97a1c02002-03-30 06:09:22 +0000407 if (bp == NULL)
408 return NULL;
409
Tim Peters3c83df22002-03-30 07:04:41 +0000410 /* arenabase <- first pool-aligned address in the arena
411 nfreepools <- number of whole pools that fit after alignment */
412 arenabase = bp;
413 nfreepools = ARENA_SIZE / POOL_SIZE;
Tim Petersc2ce91a2002-03-30 21:36:04 +0000414 assert(POOL_SIZE * nfreepools == ARENA_SIZE);
Tim Peters3c83df22002-03-30 07:04:41 +0000415 excess = (uint)bp & POOL_SIZE_MASK;
416 if (excess != 0) {
417 --nfreepools;
418 arenabase += POOL_SIZE - excess;
419 }
Tim Petersd97a1c02002-03-30 06:09:22 +0000420
421 /* Make room for a new entry in the arenas vector. */
422 if (arenas == NULL) {
Tim Petersc2ce91a2002-03-30 21:36:04 +0000423 assert(narenas == 0 && maxarenas == 0);
Tim Petersd97a1c02002-03-30 06:09:22 +0000424 arenas = (uptr *)PyMem_MALLOC(16 * sizeof(*arenas));
425 if (arenas == NULL)
426 goto error;
427 maxarenas = 16;
Tim Petersd97a1c02002-03-30 06:09:22 +0000428 }
429 else if (narenas == maxarenas) {
430 /* Grow arenas. Don't use realloc: if this fails, we
431 * don't want to lose the base addresses we already have.
Tim Petersc2ce91a2002-03-30 21:36:04 +0000432 *
Tim Petersd97a1c02002-03-30 06:09:22 +0000433 * Exceedingly subtle: Someone may be calling the pymalloc
434 * free via PyMem_{DEL, Del, FREE, Free} without holding the
435 *.GIL. Someone else may simultaneously be calling the
436 * pymalloc malloc while holding the GIL via, e.g.,
437 * PyObject_New. Now the pymalloc free may index into arenas
438 * for an address check, while the pymalloc malloc calls
439 * new_arena and we end up here to grow a new arena *and*
440 * grow the arenas vector. If the value for arenas pymalloc
441 * free picks up "vanishes" during this resize, anything may
442 * happen, and it would be an incredibly rare bug. Therefore
443 * the code here takes great pains to make sure that, at every
444 * moment, arenas always points to an intact vector of
445 * addresses. It doesn't matter whether arenas points to a
446 * wholly up-to-date vector when pymalloc free checks it in
447 * this case, because the only legal (and that even this is
448 * legal is debatable) way to call PyMem_{Del, etc} while not
449 * holding the GIL is if the memory being released is not
450 * object memory, i.e. if the address check in pymalloc free
451 * is supposed to fail. Having an incomplete vector can't
452 * make a supposed-to-fail case succeed by mistake (it could
453 * only make a supposed-to-succeed case fail by mistake).
Tim Petersc2ce91a2002-03-30 21:36:04 +0000454 *
455 * In addition, without a lock we can't know for sure when
456 * an old vector is no longer referenced, so we simply let
457 * old vectors leak.
458 *
459 * And on top of that, since narenas and arenas can't be
460 * changed as-a-pair atomically without a lock, we're also
461 * careful to declare them volatile and ensure that we change
462 * arenas first. This prevents another thread from picking
463 * up an narenas value too large for the arenas value it
464 * reads up (arenas never shrinks).
465 *
Tim Petersd97a1c02002-03-30 06:09:22 +0000466 * Read the above 50 times before changing anything in this
467 * block.
468 */
Tim Peters1d99af82002-03-30 10:35:09 +0000469 uptr *p;
Tim Petersc2ce91a2002-03-30 21:36:04 +0000470 uint newmax = maxarenas << 1;
Tim Peters1d99af82002-03-30 10:35:09 +0000471 if (newmax <= maxarenas) /* overflow */
472 goto error;
473 p = (uptr *)PyMem_MALLOC(newmax * sizeof(*arenas));
Tim Petersd97a1c02002-03-30 06:09:22 +0000474 if (p == NULL)
475 goto error;
476 memcpy(p, arenas, narenas * sizeof(*arenas));
Tim Petersc2ce91a2002-03-30 21:36:04 +0000477 arenas = p; /* old arenas deliberately leaked */
Tim Petersd97a1c02002-03-30 06:09:22 +0000478 maxarenas = newmax;
479 }
480
481 /* Append the new arena address to arenas. */
482 assert(narenas < maxarenas);
483 arenas[narenas] = (uptr)bp;
Tim Peters1d99af82002-03-30 10:35:09 +0000484 ++narenas; /* can't overflow, since narenas < maxarenas before */
Tim Petersd97a1c02002-03-30 06:09:22 +0000485 dumpem(bp);
486 return bp;
487
488error:
489 PyMem_FREE(bp);
Tim Peters7b85b4a2002-03-30 10:42:09 +0000490 nfreepools = 0;
Tim Petersd97a1c02002-03-30 06:09:22 +0000491 return NULL;
492}
493
494/* Return true if and only if P is an address that was allocated by
495 * pymalloc. I must be the index into arenas that the address claims
496 * to come from.
Tim Petersc2ce91a2002-03-30 21:36:04 +0000497 *
Tim Petersd97a1c02002-03-30 06:09:22 +0000498 * Tricky: Letting B be the arena base address in arenas[I], P belongs to the
499 * arena if and only if
Tim Peters3c83df22002-03-30 07:04:41 +0000500 * B <= P < B + ARENA_SIZE
Tim Petersd97a1c02002-03-30 06:09:22 +0000501 * Subtracting B throughout, this is true iff
Tim Peters3c83df22002-03-30 07:04:41 +0000502 * 0 <= P-B < ARENA_SIZE
Tim Petersd97a1c02002-03-30 06:09:22 +0000503 * By using unsigned arithmetic, the "0 <=" half of the test can be skipped.
Tim Petersc2ce91a2002-03-30 21:36:04 +0000504 *
505 * Obscure: A PyMem "free memory" function can call the pymalloc free or
506 * realloc before the first arena has been allocated. arenas is still
507 * NULL in that case. We're relying on that narenas is also 0 in that case,
508 * so the (I) < narenas must be false, saving us from trying to index into
509 * a NULL arenas.
Tim Petersd97a1c02002-03-30 06:09:22 +0000510 */
511#define ADDRESS_IN_RANGE(P, I) \
Tim Peters3c83df22002-03-30 07:04:41 +0000512 ((I) < narenas && (uptr)(P) - arenas[I] < (uptr)ARENA_SIZE)
Neil Schemenauera35c6882001-02-27 04:45:05 +0000513/*==========================================================================*/
514
515/* malloc */
516
517/*
518 * The basic blocks are ordered by decreasing execution frequency,
519 * which minimizes the number of jumps in the most common cases,
520 * improves branching prediction and instruction scheduling (small
521 * block allocations typically result in a couple of instructions).
522 * Unless the optimizer reorders everything, being too smart...
523 */
524
525void *
Neil Schemenauer25f3dc22002-03-18 21:06:21 +0000526_PyMalloc_Malloc(size_t nbytes)
Neil Schemenauera35c6882001-02-27 04:45:05 +0000527{
528 block *bp;
529 poolp pool;
530 poolp next;
531 uint size;
532
Neil Schemenauera35c6882001-02-27 04:45:05 +0000533 /*
534 * This implicitly redirects malloc(0)
535 */
536 if ((nbytes - 1) < SMALL_REQUEST_THRESHOLD) {
537 LOCK();
538 /*
539 * Most frequent paths first
540 */
541 size = (uint )(nbytes - 1) >> ALIGNMENT_SHIFT;
542 pool = usedpools[size + size];
543 if (pool != pool->nextpool) {
544 /*
545 * There is a used pool for this size class.
546 * Pick up the head block of its free list.
547 */
548 ++pool->ref.count;
549 bp = pool->freeblock;
550 if ((pool->freeblock = *(block **)bp) != NULL) {
551 UNLOCK();
552 return (void *)bp;
553 }
554 /*
555 * Reached the end of the free list, try to extend it
556 */
557 if (pool->ref.count < pool->capacity) {
558 /*
559 * There is room for another block
560 */
561 size++;
562 size <<= ALIGNMENT_SHIFT; /* block size */
563 pool->freeblock = (block *)pool + \
564 POOL_OVERHEAD + \
565 pool->ref.count * size;
566 *(block **)(pool->freeblock) = NULL;
567 UNLOCK();
568 return (void *)bp;
569 }
570 /*
571 * Pool is full, unlink from used pools
572 */
573 next = pool->nextpool;
574 pool = pool->prevpool;
575 next->prevpool = pool;
576 pool->nextpool = next;
577 UNLOCK();
578 return (void *)bp;
579 }
580 /*
581 * Try to get a cached free pool
582 */
583 pool = freepools;
584 if (pool != NULL) {
585 /*
586 * Unlink from cached pools
587 */
588 freepools = pool->nextpool;
589 init_pool:
590 /*
591 * Frontlink to used pools
592 */
593 next = usedpools[size + size]; /* == prev */
594 pool->nextpool = next;
595 pool->prevpool = next;
596 next->nextpool = pool;
597 next->prevpool = pool;
598 pool->ref.count = 1;
599 if (pool->szidx == size) {
600 /*
601 * Luckily, this pool last contained blocks
602 * of the same size class, so its header
603 * and free list are already initialized.
604 */
605 bp = pool->freeblock;
606 pool->freeblock = *(block **)bp;
607 UNLOCK();
608 return (void *)bp;
609 }
610 /*
611 * Initialize the pool header and free list
612 * then return the first block.
613 */
614 pool->szidx = size;
615 size++;
616 size <<= ALIGNMENT_SHIFT; /* block size */
617 bp = (block *)pool + POOL_OVERHEAD;
618 pool->freeblock = bp + size;
619 *(block **)(pool->freeblock) = NULL;
620 pool->capacity = (POOL_SIZE - POOL_OVERHEAD) / size;
621 UNLOCK();
622 return (void *)bp;
623 }
624 /*
625 * Allocate new pool
626 */
Tim Peters3c83df22002-03-30 07:04:41 +0000627 if (nfreepools) {
Neil Schemenauera35c6882001-02-27 04:45:05 +0000628 commit_pool:
Tim Peters3c83df22002-03-30 07:04:41 +0000629 --nfreepools;
630 pool = (poolp)arenabase;
Neil Schemenauera35c6882001-02-27 04:45:05 +0000631 arenabase += POOL_SIZE;
Tim Petersd97a1c02002-03-30 06:09:22 +0000632 pool->arenaindex = narenas - 1;
Neil Schemenauera35c6882001-02-27 04:45:05 +0000633 pool->szidx = DUMMY_SIZE_IDX;
634 goto init_pool;
635 }
636 /*
637 * Allocate new arena
638 */
639#ifdef WITH_MEMORY_LIMITS
Tim Petersd97a1c02002-03-30 06:09:22 +0000640 if (!(narenas < MAX_ARENAS)) {
Neil Schemenauera35c6882001-02-27 04:45:05 +0000641 UNLOCK();
642 goto redirect;
643 }
644#endif
Tim Petersd97a1c02002-03-30 06:09:22 +0000645 bp = new_arena();
646 if (bp != NULL)
647 goto commit_pool;
648 UNLOCK();
649 goto redirect;
Neil Schemenauera35c6882001-02-27 04:45:05 +0000650 }
651
652 /* The small block allocator ends here. */
653
Tim Petersd97a1c02002-03-30 06:09:22 +0000654redirect:
Neil Schemenauera35c6882001-02-27 04:45:05 +0000655 /*
656 * Redirect the original request to the underlying (libc) allocator.
657 * We jump here on bigger requests, on error in the code above (as a
658 * last chance to serve the request) or when the max memory limit
659 * has been reached.
660 */
Neil Schemenauer25f3dc22002-03-18 21:06:21 +0000661 return (void *)PyMem_MALLOC(nbytes);
Neil Schemenauera35c6882001-02-27 04:45:05 +0000662}
663
664/* free */
665
666void
Neil Schemenauer25f3dc22002-03-18 21:06:21 +0000667_PyMalloc_Free(void *p)
Neil Schemenauera35c6882001-02-27 04:45:05 +0000668{
669 poolp pool;
670 poolp next, prev;
671 uint size;
Neil Schemenauera35c6882001-02-27 04:45:05 +0000672
Neil Schemenauera35c6882001-02-27 04:45:05 +0000673 if (p == NULL) /* free(NULL) has no effect */
674 return;
675
Tim Petersd97a1c02002-03-30 06:09:22 +0000676 pool = POOL_ADDR(p);
677 if (ADDRESS_IN_RANGE(p, pool->arenaindex)) {
678 /* We allocated this address. */
Tim Petersd97a1c02002-03-30 06:09:22 +0000679 LOCK();
Tim Peters1e16db62002-03-31 01:05:22 +0000680 INCMINE;
Tim Petersd97a1c02002-03-30 06:09:22 +0000681 /*
682 * At this point, the pool is not empty
683 */
684 if ((*(block **)p = pool->freeblock) == NULL) {
685 /*
686 * Pool was full
687 */
688 pool->freeblock = (block *)p;
689 --pool->ref.count;
690 /*
691 * Frontlink to used pools
692 * This mimics LRU pool usage for new allocations and
693 * targets optimal filling when several pools contain
694 * blocks of the same size class.
695 */
696 size = pool->szidx;
697 next = usedpools[size + size];
698 prev = next->prevpool;
699 pool->nextpool = next;
700 pool->prevpool = prev;
701 next->prevpool = pool;
702 prev->nextpool = pool;
703 UNLOCK();
704 return;
705 }
706 /*
707 * Pool was not full
708 */
709 pool->freeblock = (block *)p;
710 if (--pool->ref.count != 0) {
711 UNLOCK();
712 return;
713 }
714 /*
715 * Pool is now empty, unlink from used pools
716 */
717 next = pool->nextpool;
718 prev = pool->prevpool;
719 next->prevpool = prev;
720 prev->nextpool = next;
721 /*
722 * Frontlink to free pools
723 * This ensures that previously freed pools will be allocated
724 * later (being not referenced, they are perhaps paged out).
725 */
726 pool->nextpool = freepools;
727 freepools = pool;
728 UNLOCK();
Neil Schemenauera35c6882001-02-27 04:45:05 +0000729 return;
730 }
731
Tim Petersd97a1c02002-03-30 06:09:22 +0000732 /* We did not allocate this address. */
733 INCTHEIRS;
734 PyMem_FREE(p);
Neil Schemenauera35c6882001-02-27 04:45:05 +0000735}
736
737/* realloc */
738
739void *
Neil Schemenauer25f3dc22002-03-18 21:06:21 +0000740_PyMalloc_Realloc(void *p, size_t nbytes)
Neil Schemenauera35c6882001-02-27 04:45:05 +0000741{
742 block *bp;
743 poolp pool;
744 uint size;
745
Neil Schemenauera35c6882001-02-27 04:45:05 +0000746 if (p == NULL)
Neil Schemenauer25f3dc22002-03-18 21:06:21 +0000747 return _PyMalloc_Malloc(nbytes);
Neil Schemenauera35c6882001-02-27 04:45:05 +0000748
749 /* realloc(p, 0) on big blocks is redirected. */
Tim Petersd97a1c02002-03-30 06:09:22 +0000750 pool = POOL_ADDR(p);
751 if (ADDRESS_IN_RANGE(p, pool->arenaindex)) {
Neil Schemenauera35c6882001-02-27 04:45:05 +0000752 /* We're in charge of this block */
Tim Petersd97a1c02002-03-30 06:09:22 +0000753 INCMINE;
Neil Schemenauera35c6882001-02-27 04:45:05 +0000754 size = (pool->szidx + 1) << ALIGNMENT_SHIFT; /* block size */
755 if (size >= nbytes) {
756 /* Don't bother if a smaller size was requested
757 except for realloc(p, 0) == free(p), ret NULL */
Tim Petersd97a1c02002-03-30 06:09:22 +0000758 /* XXX but Python guarantees that *its* flavor of
759 resize(p, 0) will not do a free or return NULL */
Neil Schemenauera35c6882001-02-27 04:45:05 +0000760 if (nbytes == 0) {
Neil Schemenauer25f3dc22002-03-18 21:06:21 +0000761 _PyMalloc_Free(p);
Neil Schemenauera35c6882001-02-27 04:45:05 +0000762 bp = NULL;
763 }
764 else
765 bp = (block *)p;
766 }
767 else {
Neil Schemenauer25f3dc22002-03-18 21:06:21 +0000768 bp = (block *)_PyMalloc_Malloc(nbytes);
Neil Schemenauera35c6882001-02-27 04:45:05 +0000769 if (bp != NULL) {
770 memcpy(bp, p, size);
Neil Schemenauer25f3dc22002-03-18 21:06:21 +0000771 _PyMalloc_Free(p);
Neil Schemenauera35c6882001-02-27 04:45:05 +0000772 }
773 }
774 }
Tim Petersd97a1c02002-03-30 06:09:22 +0000775 else {
776 /* We haven't allocated this block */
777 INCTHEIRS;
778 if (nbytes <= SMALL_REQUEST_THRESHOLD && nbytes) {
779 /* small request */
780 size = nbytes;
781 bp = (block *)_PyMalloc_Malloc(nbytes);
782 if (bp != NULL) {
783 memcpy(bp, p, size);
784 _PyMalloc_Free(p);
785 }
786 }
787 else
788 bp = (block *)PyMem_REALLOC(p, nbytes);
789 }
Neil Schemenauera35c6882001-02-27 04:45:05 +0000790 return (void *)bp;
791}
792
Tim Peters1221c0a2002-03-23 00:20:15 +0000793#else /* ! WITH_PYMALLOC */
Tim Petersddea2082002-03-23 10:03:50 +0000794
795/*==========================================================================*/
796/* pymalloc not enabled: Redirect the entry points to the PyMem family. */
Tim Peters62c06ba2002-03-23 22:28:18 +0000797
Tim Petersce7fb9b2002-03-23 00:28:57 +0000798void *
799_PyMalloc_Malloc(size_t n)
Tim Peters1221c0a2002-03-23 00:20:15 +0000800{
801 return PyMem_MALLOC(n);
802}
803
Tim Petersce7fb9b2002-03-23 00:28:57 +0000804void *
805_PyMalloc_Realloc(void *p, size_t n)
Tim Peters1221c0a2002-03-23 00:20:15 +0000806{
807 return PyMem_REALLOC(p, n);
808}
809
810void
811_PyMalloc_Free(void *p)
812{
813 PyMem_FREE(p);
814}
815#endif /* WITH_PYMALLOC */
816
Tim Peters62c06ba2002-03-23 22:28:18 +0000817/*==========================================================================*/
818/* Regardless of whether pymalloc is enabled, export entry points for
819 * the object-oriented pymalloc functions.
820 */
821
Tim Petersce7fb9b2002-03-23 00:28:57 +0000822PyObject *
823_PyMalloc_New(PyTypeObject *tp)
Tim Peters1221c0a2002-03-23 00:20:15 +0000824{
825 PyObject *op;
826 op = (PyObject *) _PyMalloc_MALLOC(_PyObject_SIZE(tp));
827 if (op == NULL)
828 return PyErr_NoMemory();
829 return PyObject_INIT(op, tp);
830}
831
832PyVarObject *
833_PyMalloc_NewVar(PyTypeObject *tp, int nitems)
834{
835 PyVarObject *op;
836 const size_t size = _PyObject_VAR_SIZE(tp, nitems);
837 op = (PyVarObject *) _PyMalloc_MALLOC(size);
838 if (op == NULL)
839 return (PyVarObject *)PyErr_NoMemory();
840 return PyObject_INIT_VAR(op, tp, nitems);
841}
842
843void
844_PyMalloc_Del(PyObject *op)
845{
846 _PyMalloc_FREE(op);
847}
Tim Petersddea2082002-03-23 10:03:50 +0000848
849#ifdef PYMALLOC_DEBUG
850/*==========================================================================*/
Tim Peters62c06ba2002-03-23 22:28:18 +0000851/* A x-platform debugging allocator. This doesn't manage memory directly,
852 * it wraps a real allocator, adding extra debugging info to the memory blocks.
853 */
Tim Petersddea2082002-03-23 10:03:50 +0000854
855#define PYMALLOC_CLEANBYTE 0xCB /* uninitialized memory */
856#define PYMALLOC_DEADBYTE 0xDB /* free()ed memory */
857#define PYMALLOC_FORBIDDENBYTE 0xFB /* unusable memory */
858
859static ulong serialno = 0; /* incremented on each debug {m,re}alloc */
860
Tim Peterse0850172002-03-24 00:34:21 +0000861/* serialno is always incremented via calling this routine. The point is
862 to supply a single place to set a breakpoint.
863*/
864static void
Neil Schemenauerbd02b142002-03-28 21:05:38 +0000865bumpserialno(void)
Tim Peterse0850172002-03-24 00:34:21 +0000866{
867 ++serialno;
868}
869
870
Tim Petersddea2082002-03-23 10:03:50 +0000871/* Read 4 bytes at p as a big-endian ulong. */
872static ulong
873read4(const void *p)
874{
Tim Peters62c06ba2002-03-23 22:28:18 +0000875 const uchar *q = (const uchar *)p;
Tim Petersddea2082002-03-23 10:03:50 +0000876 return ((ulong)q[0] << 24) |
877 ((ulong)q[1] << 16) |
878 ((ulong)q[2] << 8) |
879 (ulong)q[3];
880}
881
882/* Write the 4 least-significant bytes of n as a big-endian unsigned int,
883 MSB at address p, LSB at p+3. */
884static void
885write4(void *p, ulong n)
886{
Tim Peters62c06ba2002-03-23 22:28:18 +0000887 uchar *q = (uchar *)p;
888 q[0] = (uchar)((n >> 24) & 0xff);
889 q[1] = (uchar)((n >> 16) & 0xff);
890 q[2] = (uchar)((n >> 8) & 0xff);
891 q[3] = (uchar)( n & 0xff);
Tim Petersddea2082002-03-23 10:03:50 +0000892}
893
Tim Petersddea2082002-03-23 10:03:50 +0000894/* The debug malloc asks for 16 extra bytes and fills them with useful stuff,
895 here calling the underlying malloc's result p:
896
897p[0:4]
898 Number of bytes originally asked for. 4-byte unsigned integer,
899 big-endian (easier to read in a memory dump).
Tim Petersd1139e02002-03-28 07:32:11 +0000900p[4:8]
Tim Petersddea2082002-03-23 10:03:50 +0000901 Copies of PYMALLOC_FORBIDDENBYTE. Used to catch under- writes
902 and reads.
903p[8:8+n]
904 The requested memory, filled with copies of PYMALLOC_CLEANBYTE.
905 Used to catch reference to uninitialized memory.
906 &p[8] is returned. Note that this is 8-byte aligned if PyMalloc
907 handled the request itself.
908p[8+n:8+n+4]
909 Copies of PYMALLOC_FORBIDDENBYTE. Used to catch over- writes
910 and reads.
911p[8+n+4:8+n+8]
912 A serial number, incremented by 1 on each call to _PyMalloc_DebugMalloc
913 and _PyMalloc_DebugRealloc.
914 4-byte unsigned integer, big-endian.
915 If "bad memory" is detected later, the serial number gives an
916 excellent way to set a breakpoint on the next run, to capture the
917 instant at which this block was passed out.
918*/
919
920void *
Tim Petersd1139e02002-03-28 07:32:11 +0000921_PyMalloc_DebugMalloc(size_t nbytes)
Tim Petersddea2082002-03-23 10:03:50 +0000922{
923 uchar *p; /* base address of malloc'ed block */
Tim Peters62c06ba2002-03-23 22:28:18 +0000924 uchar *tail; /* p + 8 + nbytes == pointer to tail pad bytes */
Tim Petersddea2082002-03-23 10:03:50 +0000925 size_t total; /* nbytes + 16 */
926
Tim Peterse0850172002-03-24 00:34:21 +0000927 bumpserialno();
Tim Petersddea2082002-03-23 10:03:50 +0000928 total = nbytes + 16;
929 if (total < nbytes || (total >> 31) > 1) {
930 /* overflow, or we can't represent it in 4 bytes */
931 /* Obscure: can't do (total >> 32) != 0 instead, because
932 C doesn't define what happens for a right-shift of 32
933 when size_t is a 32-bit type. At least C guarantees
934 size_t is an unsigned type. */
935 return NULL;
936 }
937
Tim Petersd1139e02002-03-28 07:32:11 +0000938 p = _PyMalloc_Malloc(total);
Tim Petersddea2082002-03-23 10:03:50 +0000939 if (p == NULL)
940 return NULL;
941
942 write4(p, nbytes);
Tim Petersd1139e02002-03-28 07:32:11 +0000943 p[4] = p[5] = p[6] = p[7] = PYMALLOC_FORBIDDENBYTE;
Tim Petersddea2082002-03-23 10:03:50 +0000944
945 if (nbytes > 0)
946 memset(p+8, PYMALLOC_CLEANBYTE, nbytes);
947
Tim Peters62c06ba2002-03-23 22:28:18 +0000948 tail = p + 8 + nbytes;
949 tail[0] = tail[1] = tail[2] = tail[3] = PYMALLOC_FORBIDDENBYTE;
950 write4(tail + 4, serialno);
Tim Petersddea2082002-03-23 10:03:50 +0000951
952 return p+8;
953}
954
Tim Peters62c06ba2002-03-23 22:28:18 +0000955/* The debug free first checks the 8 bytes on each end for sanity (in
956 particular, that the PYMALLOC_FORBIDDENBYTEs are still intact).
Tim Petersddea2082002-03-23 10:03:50 +0000957 Then fills the original bytes with PYMALLOC_DEADBYTE.
958 Then calls the underlying free.
959*/
960void
Tim Petersd1139e02002-03-28 07:32:11 +0000961_PyMalloc_DebugFree(void *p)
Tim Petersddea2082002-03-23 10:03:50 +0000962{
Tim Peters62c06ba2002-03-23 22:28:18 +0000963 uchar *q = (uchar *)p;
Tim Petersddea2082002-03-23 10:03:50 +0000964 size_t nbytes;
965
Tim Petersddea2082002-03-23 10:03:50 +0000966 if (p == NULL)
967 return;
Tim Petersddea2082002-03-23 10:03:50 +0000968 _PyMalloc_DebugCheckAddress(p);
969 nbytes = read4(q-8);
970 if (nbytes > 0)
971 memset(q, PYMALLOC_DEADBYTE, nbytes);
Tim Petersd1139e02002-03-28 07:32:11 +0000972 _PyMalloc_Free(q-8);
Tim Petersddea2082002-03-23 10:03:50 +0000973}
974
975void *
Tim Petersd1139e02002-03-28 07:32:11 +0000976_PyMalloc_DebugRealloc(void *p, size_t nbytes)
Tim Petersddea2082002-03-23 10:03:50 +0000977{
978 uchar *q = (uchar *)p;
979 size_t original_nbytes;
Tim Peterse0850172002-03-24 00:34:21 +0000980 void *fresh; /* new memory block, if needed */
Tim Petersddea2082002-03-23 10:03:50 +0000981
Tim Petersddea2082002-03-23 10:03:50 +0000982 if (p == NULL)
Tim Petersd1139e02002-03-28 07:32:11 +0000983 return _PyMalloc_DebugMalloc(nbytes);
Tim Petersddea2082002-03-23 10:03:50 +0000984
Tim Petersddea2082002-03-23 10:03:50 +0000985 _PyMalloc_DebugCheckAddress(p);
Tim Petersddea2082002-03-23 10:03:50 +0000986 original_nbytes = read4(q-8);
987 if (nbytes == original_nbytes) {
988 /* note that this case is likely to be common due to the
989 way Python appends to lists */
Tim Peterse0850172002-03-24 00:34:21 +0000990 bumpserialno();
Tim Petersddea2082002-03-23 10:03:50 +0000991 write4(q + nbytes + 4, serialno);
992 return p;
993 }
994
995 if (nbytes < original_nbytes) {
996 /* shrinking -- leave the guts alone, except to
997 fill the excess with DEADBYTE */
998 const size_t excess = original_nbytes - nbytes;
Tim Peterse0850172002-03-24 00:34:21 +0000999 bumpserialno();
Tim Petersddea2082002-03-23 10:03:50 +00001000 write4(q-8, nbytes);
1001 /* kill the excess bytes plus the trailing 8 pad bytes */
Tim Petersddea2082002-03-23 10:03:50 +00001002 q += nbytes;
1003 q[0] = q[1] = q[2] = q[3] = PYMALLOC_FORBIDDENBYTE;
1004 write4(q+4, serialno);
Tim Petersd1139e02002-03-28 07:32:11 +00001005 memset(q+8, PYMALLOC_DEADBYTE, excess);
Tim Petersddea2082002-03-23 10:03:50 +00001006 return p;
1007 }
1008
1009 /* More memory is needed: get it, copy over the first original_nbytes
1010 of the original data, and free the original memory. */
Tim Petersd1139e02002-03-28 07:32:11 +00001011 fresh = _PyMalloc_DebugMalloc(nbytes);
Tim Petersddea2082002-03-23 10:03:50 +00001012 if (fresh != NULL && original_nbytes > 0)
1013 memcpy(fresh, p, original_nbytes);
Tim Petersd1139e02002-03-28 07:32:11 +00001014 _PyMalloc_DebugFree(p);
Tim Petersddea2082002-03-23 10:03:50 +00001015 return fresh;
1016}
1017
1018void
1019_PyMalloc_DebugCheckAddress(const void *p)
1020{
1021 const uchar *q = (const uchar *)p;
Tim Petersd1139e02002-03-28 07:32:11 +00001022 char *msg;
1023 int i;
Tim Petersddea2082002-03-23 10:03:50 +00001024
Tim Petersd1139e02002-03-28 07:32:11 +00001025 if (p == NULL) {
Tim Petersddea2082002-03-23 10:03:50 +00001026 msg = "didn't expect a NULL pointer";
Tim Petersd1139e02002-03-28 07:32:11 +00001027 goto error;
1028 }
Tim Petersddea2082002-03-23 10:03:50 +00001029
Tim Petersd1139e02002-03-28 07:32:11 +00001030 for (i = 4; i >= 1; --i) {
1031 if (*(q-i) != PYMALLOC_FORBIDDENBYTE) {
1032 msg = "bad leading pad byte";
1033 goto error;
1034 }
1035 }
Tim Petersddea2082002-03-23 10:03:50 +00001036
Tim Petersd1139e02002-03-28 07:32:11 +00001037 {
Tim Petersddea2082002-03-23 10:03:50 +00001038 const ulong nbytes = read4(q-8);
1039 const uchar *tail = q + nbytes;
Tim Petersddea2082002-03-23 10:03:50 +00001040 for (i = 0; i < 4; ++i) {
1041 if (tail[i] != PYMALLOC_FORBIDDENBYTE) {
1042 msg = "bad trailing pad byte";
Tim Petersd1139e02002-03-28 07:32:11 +00001043 goto error;
Tim Petersddea2082002-03-23 10:03:50 +00001044 }
1045 }
1046 }
1047
Tim Petersd1139e02002-03-28 07:32:11 +00001048 return;
1049
1050error:
1051 _PyMalloc_DebugDumpAddress(p);
1052 Py_FatalError(msg);
Tim Petersddea2082002-03-23 10:03:50 +00001053}
1054
1055void
1056_PyMalloc_DebugDumpAddress(const void *p)
1057{
1058 const uchar *q = (const uchar *)p;
1059 const uchar *tail;
1060 ulong nbytes, serial;
Tim Petersd1139e02002-03-28 07:32:11 +00001061 int i;
Tim Petersddea2082002-03-23 10:03:50 +00001062
1063 fprintf(stderr, "Debug memory block at address p=%p:\n", p);
1064 if (p == NULL)
1065 return;
1066
1067 nbytes = read4(q-8);
1068 fprintf(stderr, " %lu bytes originally allocated\n", nbytes);
Tim Petersddea2082002-03-23 10:03:50 +00001069
1070 /* In case this is nuts, check the pad bytes before trying to read up
1071 the serial number (the address deref could blow up). */
1072
Tim Petersd1139e02002-03-28 07:32:11 +00001073 fputs(" the 4 pad bytes at p-4 are ", stderr);
1074 if (*(q-4) == PYMALLOC_FORBIDDENBYTE &&
1075 *(q-3) == PYMALLOC_FORBIDDENBYTE &&
Tim Petersddea2082002-03-23 10:03:50 +00001076 *(q-2) == PYMALLOC_FORBIDDENBYTE &&
1077 *(q-1) == PYMALLOC_FORBIDDENBYTE) {
Tim Peters62c06ba2002-03-23 22:28:18 +00001078 fputs("PYMALLOC_FORBIDDENBYTE, as expected\n", stderr);
Tim Petersddea2082002-03-23 10:03:50 +00001079 }
1080 else {
Tim Petersddea2082002-03-23 10:03:50 +00001081 fprintf(stderr, "not all PYMALLOC_FORBIDDENBYTE (0x%02x):\n",
1082 PYMALLOC_FORBIDDENBYTE);
Tim Petersd1139e02002-03-28 07:32:11 +00001083 for (i = 4; i >= 1; --i) {
Tim Petersddea2082002-03-23 10:03:50 +00001084 const uchar byte = *(q-i);
1085 fprintf(stderr, " at p-%d: 0x%02x", i, byte);
1086 if (byte != PYMALLOC_FORBIDDENBYTE)
1087 fputs(" *** OUCH", stderr);
1088 fputc('\n', stderr);
1089 }
1090 }
1091
1092 tail = q + nbytes;
1093 fprintf(stderr, " the 4 pad bytes at tail=%p are ", tail);
1094 if (tail[0] == PYMALLOC_FORBIDDENBYTE &&
1095 tail[1] == PYMALLOC_FORBIDDENBYTE &&
1096 tail[2] == PYMALLOC_FORBIDDENBYTE &&
1097 tail[3] == PYMALLOC_FORBIDDENBYTE) {
Tim Peters62c06ba2002-03-23 22:28:18 +00001098 fputs("PYMALLOC_FORBIDDENBYTE, as expected\n", stderr);
Tim Petersddea2082002-03-23 10:03:50 +00001099 }
1100 else {
Tim Petersddea2082002-03-23 10:03:50 +00001101 fprintf(stderr, "not all PYMALLOC_FORBIDDENBYTE (0x%02x):\n",
1102 PYMALLOC_FORBIDDENBYTE);
1103 for (i = 0; i < 4; ++i) {
1104 const uchar byte = tail[i];
1105 fprintf(stderr, " at tail+%d: 0x%02x",
1106 i, byte);
1107 if (byte != PYMALLOC_FORBIDDENBYTE)
1108 fputs(" *** OUCH", stderr);
1109 fputc('\n', stderr);
1110 }
1111 }
1112
1113 serial = read4(tail+4);
1114 fprintf(stderr, " the block was made by call #%lu to "
1115 "debug malloc/realloc\n", serial);
1116
1117 if (nbytes > 0) {
1118 int i = 0;
Tim Peters62c06ba2002-03-23 22:28:18 +00001119 fputs(" data at p:", stderr);
Tim Petersddea2082002-03-23 10:03:50 +00001120 /* print up to 8 bytes at the start */
1121 while (q < tail && i < 8) {
1122 fprintf(stderr, " %02x", *q);
1123 ++i;
1124 ++q;
1125 }
1126 /* and up to 8 at the end */
1127 if (q < tail) {
1128 if (tail - q > 8) {
Tim Peters62c06ba2002-03-23 22:28:18 +00001129 fputs(" ...", stderr);
Tim Petersddea2082002-03-23 10:03:50 +00001130 q = tail - 8;
1131 }
1132 while (q < tail) {
1133 fprintf(stderr, " %02x", *q);
1134 ++q;
1135 }
1136 }
Tim Peters62c06ba2002-03-23 22:28:18 +00001137 fputc('\n', stderr);
Tim Petersddea2082002-03-23 10:03:50 +00001138 }
1139}
1140
1141#endif /* PYMALLOC_DEBUG */