#include "Python.h"

#include "internal/mem.h"

#include "internal/pystate.h"

#include <stdbool.h>

/* Defined in tracemalloc.c */

extern void _PyMem_DumpTraceback(int fd, const void *ptr);

/* Python's malloc wrappers (see pymem.h) */

#undef uint

#define uint unsigned int /* assuming >= 16 bits */

/* Forward declaration */

static void* _PyMem_DebugRawMalloc(void *ctx, size_t size);

static void* _PyMem_DebugRawCalloc(void *ctx, size_t nelem, size_t elsize);

static void* _PyMem_DebugRawRealloc(void *ctx, void *ptr, size_t size);

static void _PyMem_DebugRawFree(void *ctx, void *p);

static void* _PyMem_DebugMalloc(void *ctx, size_t size);

static void* _PyMem_DebugCalloc(void *ctx, size_t nelem, size_t elsize);

static void* _PyMem_DebugRealloc(void *ctx, void *ptr, size_t size);

static void _PyMem_DebugFree(void *ctx, void *p);

static void _PyObject_DebugDumpAddress(const void *p);

static void _PyMem_DebugCheckAddress(char api_id, const void *p);

#if defined(__has_feature) /* Clang */

#if __has_feature(address_sanitizer) /* is ASAN enabled? */

#define ATTRIBUTE_NO_ADDRESS_SAFETY_ANALYSIS \

__attribute__((no_address_safety_analysis))

#else

#define ATTRIBUTE_NO_ADDRESS_SAFETY_ANALYSIS

#endif

#else

#if defined(__SANITIZE_ADDRESS__) /* GCC 4.8.x, is ASAN enabled? */

#define ATTRIBUTE_NO_ADDRESS_SAFETY_ANALYSIS \

__attribute__((no_address_safety_analysis))

#else

#define ATTRIBUTE_NO_ADDRESS_SAFETY_ANALYSIS

#endif

#endif

#ifdef WITH_PYMALLOC

#ifdef MS_WINDOWS

# include <windows.h>

#elif defined(HAVE_MMAP)

# include <sys/mman.h>

# ifdef MAP_ANONYMOUS

# define ARENAS_USE_MMAP

# endif

#endif

/* Forward declaration */

static void* _PyObject_Malloc(void *ctx, size_t size);

static void* _PyObject_Calloc(void *ctx, size_t nelem, size_t elsize);

static void _PyObject_Free(void *ctx, void *p);

static void* _PyObject_Realloc(void *ctx, void *ptr, size_t size);

#endif

static void *

_PyMem_RawMalloc(void *ctx, size_t size)

{

/* PyMem_RawMalloc(0) means malloc(1). Some systems would return NULL

for malloc(0), which would be treated as an error. Some platforms would

return a pointer with no memory behind it, which would break pymalloc.

To solve these problems, allocate an extra byte. */

if (size == 0)

size = 1;

return malloc(size);

}

static void *

_PyMem_RawCalloc(void *ctx, size_t nelem, size_t elsize)

{

/* PyMem_RawCalloc(0, 0) means calloc(1, 1). Some systems would return NULL

for calloc(0, 0), which would be treated as an error. Some platforms

would return a pointer with no memory behind it, which would break

pymalloc. To solve these problems, allocate an extra byte. */

if (nelem == 0 || elsize == 0) {

nelem = 1;

elsize = 1;

}

return calloc(nelem, elsize);

}

static void *

_PyMem_RawRealloc(void *ctx, void *ptr, size_t size)

{

if (size == 0)

size = 1;

return realloc(ptr, size);

}

static void

_PyMem_RawFree(void *ctx, void *ptr)

{

free(ptr);

}

#ifdef MS_WINDOWS

static void *

_PyObject_ArenaVirtualAlloc(void *ctx, size_t size)

{

return VirtualAlloc(NULL, size,

MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);

}

static void

_PyObject_ArenaVirtualFree(void *ctx, void *ptr, size_t size)

{

VirtualFree(ptr, 0, MEM_RELEASE);

}

#elif defined(ARENAS_USE_MMAP)

static void *

_PyObject_ArenaMmap(void *ctx, size_t size)

{

void *ptr;

ptr = mmap(NULL, size, PROT_READ|PROT_WRITE,

MAP_PRIVATE|MAP_ANONYMOUS, -1, 0);

if (ptr == MAP_FAILED)

return NULL;

assert(ptr != NULL);

return ptr;

}

static void

_PyObject_ArenaMunmap(void *ctx, void *ptr, size_t size)

{

munmap(ptr, size);

}

#else

static void *

_PyObject_ArenaMalloc(void *ctx, size_t size)

{

return malloc(size);

}

static void

_PyObject_ArenaFree(void *ctx, void *ptr, size_t size)

{

free(ptr);

}

#endif

#define PYRAW_FUNCS _PyMem_RawMalloc, _PyMem_RawCalloc, _PyMem_RawRealloc, _PyMem_RawFree

#ifdef WITH_PYMALLOC

# define PYOBJ_FUNCS _PyObject_Malloc, _PyObject_Calloc, _PyObject_Realloc, _PyObject_Free

#else

# define PYOBJ_FUNCS PYRAW_FUNCS

#endif

#define PYMEM_FUNCS PYOBJ_FUNCS

typedef struct {

/* We tag each block with an API ID in order to tag API violations */

char api_id;

PyMemAllocatorEx alloc;

} debug_alloc_api_t;

static struct {

debug_alloc_api_t raw;

debug_alloc_api_t mem;

debug_alloc_api_t obj;

} _PyMem_Debug = {

{'r', {NULL, PYRAW_FUNCS}},

{'m', {NULL, PYMEM_FUNCS}},

{'o', {NULL, PYOBJ_FUNCS}}

};

#define PYRAWDBG_FUNCS \

_PyMem_DebugRawMalloc, _PyMem_DebugRawCalloc, _PyMem_DebugRawRealloc, _PyMem_DebugRawFree

#define PYDBG_FUNCS \

_PyMem_DebugMalloc, _PyMem_DebugCalloc, _PyMem_DebugRealloc, _PyMem_DebugFree

#define _PyMem_Raw _PyRuntime.mem.allocators.raw

static const PyMemAllocatorEx _pymem_raw = {

#ifdef Py_DEBUG

&_PyMem_Debug.raw, PYRAWDBG_FUNCS

#else

NULL, PYRAW_FUNCS

#endif

};

#define _PyMem _PyRuntime.mem.allocators.mem

static const PyMemAllocatorEx _pymem = {

#ifdef Py_DEBUG

&_PyMem_Debug.mem, PYDBG_FUNCS

#else

NULL, PYMEM_FUNCS

#endif

};

#define _PyObject _PyRuntime.mem.allocators.obj

static const PyMemAllocatorEx _pyobject = {

#ifdef Py_DEBUG

&_PyMem_Debug.obj, PYDBG_FUNCS

#else

NULL, PYOBJ_FUNCS

#endif

};

int

_PyMem_SetupAllocators(const char *opt)

{

if (opt == NULL || *opt == '\0') {

/* PYTHONMALLOC is empty or is not set or ignored (-E/-I command line

options): use default allocators */

#ifdef Py_DEBUG

# ifdef WITH_PYMALLOC

opt = "pymalloc_debug";

# else

opt = "malloc_debug";

# endif

#else

/* !Py_DEBUG */

# ifdef WITH_PYMALLOC

opt = "pymalloc";

# else

opt = "malloc";

# endif

#endif

}

if (strcmp(opt, "debug") == 0) {

PyMem_SetupDebugHooks();

}

else if (strcmp(opt, "malloc") == 0 || strcmp(opt, "malloc_debug") == 0)

{

PyMemAllocatorEx alloc = {NULL, PYRAW_FUNCS};

PyMem_SetAllocator(PYMEM_DOMAIN_RAW, &alloc);

PyMem_SetAllocator(PYMEM_DOMAIN_MEM, &alloc);

PyMem_SetAllocator(PYMEM_DOMAIN_OBJ, &alloc);

if (strcmp(opt, "malloc_debug") == 0)

PyMem_SetupDebugHooks();

}

#ifdef WITH_PYMALLOC

else if (strcmp(opt, "pymalloc") == 0

|| strcmp(opt, "pymalloc_debug") == 0)

{

PyMemAllocatorEx raw_alloc = {NULL, PYRAW_FUNCS};

PyMemAllocatorEx mem_alloc = {NULL, PYMEM_FUNCS};

PyMemAllocatorEx obj_alloc = {NULL, PYOBJ_FUNCS};

PyMem_SetAllocator(PYMEM_DOMAIN_RAW, &raw_alloc);

PyMem_SetAllocator(PYMEM_DOMAIN_MEM, &mem_alloc);

PyMem_SetAllocator(PYMEM_DOMAIN_OBJ, &obj_alloc);

if (strcmp(opt, "pymalloc_debug") == 0)

PyMem_SetupDebugHooks();

}

#endif

else {

/* unknown allocator */

return -1;

}

return 0;

}

#undef PYRAW_FUNCS

#undef PYMEM_FUNCS

#undef PYOBJ_FUNCS

#undef PYRAWDBG_FUNCS

#undef PYDBG_FUNCS

static const PyObjectArenaAllocator _PyObject_Arena = {NULL,

#ifdef MS_WINDOWS

_PyObject_ArenaVirtualAlloc, _PyObject_ArenaVirtualFree

#elif defined(ARENAS_USE_MMAP)

_PyObject_ArenaMmap, _PyObject_ArenaMunmap

#else

_PyObject_ArenaMalloc, _PyObject_ArenaFree

#endif

};

void

_PyObject_Initialize(struct _pyobj_runtime_state *state)

{

state->allocator_arenas = _PyObject_Arena;

}

void

_PyMem_Initialize(struct _pymem_runtime_state *state)

{

state->allocators.raw = _pymem_raw;

state->allocators.mem = _pymem;

state->allocators.obj = _pyobject;

#ifdef WITH_PYMALLOC

Py_BUILD_ASSERT(NB_SMALL_SIZE_CLASSES == 64);

for (int i = 0; i < 8; i++) {

for (int j = 0; j < 8; j++) {

int x = i * 8 + j;

poolp *addr = &(state->usedpools[2*(x)]);

poolp val = (poolp)((uint8_t *)addr - 2*sizeof(pyblock *));

state->usedpools[x * 2] = val;

state->usedpools[x * 2 + 1] = val;

};

};

#endif /* WITH_PYMALLOC */

}

#ifdef WITH_PYMALLOC

static int

_PyMem_DebugEnabled(void)

{

return (_PyObject.malloc == _PyMem_DebugMalloc);

}

int

_PyMem_PymallocEnabled(void)

{

if (_PyMem_DebugEnabled()) {

return (_PyMem_Debug.obj.alloc.malloc == _PyObject_Malloc);

}

else {

return (_PyObject.malloc == _PyObject_Malloc);

}

}

#endif

void

PyMem_SetupDebugHooks(void)

{

PyMemAllocatorEx alloc;

alloc.malloc = _PyMem_DebugRawMalloc;

alloc.calloc = _PyMem_DebugRawCalloc;

alloc.realloc = _PyMem_DebugRawRealloc;

alloc.free = _PyMem_DebugRawFree;

if (_PyMem_Raw.malloc != _PyMem_DebugRawMalloc) {

alloc.ctx = &_PyMem_Debug.raw;

PyMem_GetAllocator(PYMEM_DOMAIN_RAW, &_PyMem_Debug.raw.alloc);

PyMem_SetAllocator(PYMEM_DOMAIN_RAW, &alloc);

}

alloc.malloc = _PyMem_DebugMalloc;

alloc.calloc = _PyMem_DebugCalloc;

alloc.realloc = _PyMem_DebugRealloc;

alloc.free = _PyMem_DebugFree;

if (_PyMem.malloc != _PyMem_DebugMalloc) {

alloc.ctx = &_PyMem_Debug.mem;

PyMem_GetAllocator(PYMEM_DOMAIN_MEM, &_PyMem_Debug.mem.alloc);

PyMem_SetAllocator(PYMEM_DOMAIN_MEM, &alloc);

}

if (_PyObject.malloc != _PyMem_DebugMalloc) {

alloc.ctx = &_PyMem_Debug.obj;

PyMem_GetAllocator(PYMEM_DOMAIN_OBJ, &_PyMem_Debug.obj.alloc);

PyMem_SetAllocator(PYMEM_DOMAIN_OBJ, &alloc);

}

}

void

PyMem_GetAllocator(PyMemAllocatorDomain domain, PyMemAllocatorEx *allocator)

{

switch(domain)

{

case PYMEM_DOMAIN_RAW: *allocator = _PyMem_Raw; break;

case PYMEM_DOMAIN_MEM: *allocator = _PyMem; break;

case PYMEM_DOMAIN_OBJ: *allocator = _PyObject; break;

default:

/* unknown domain: set all attributes to NULL */

allocator->ctx = NULL;

allocator->malloc = NULL;

allocator->calloc = NULL;

allocator->realloc = NULL;

allocator->free = NULL;

}

}

void

PyMem_SetAllocator(PyMemAllocatorDomain domain, PyMemAllocatorEx *allocator)

{

switch(domain)

{

case PYMEM_DOMAIN_RAW: _PyMem_Raw = *allocator; break;

case PYMEM_DOMAIN_MEM: _PyMem = *allocator; break;

case PYMEM_DOMAIN_OBJ: _PyObject = *allocator; break;

/* ignore unknown domain */

}

}

void

PyObject_GetArenaAllocator(PyObjectArenaAllocator *allocator)

{

*allocator = _PyRuntime.obj.allocator_arenas;

}

void

PyObject_SetArenaAllocator(PyObjectArenaAllocator *allocator)

{

_PyRuntime.obj.allocator_arenas = *allocator;

}

void *

PyMem_RawMalloc(size_t size)

{

/*

* Limit ourselves to PY_SSIZE_T_MAX bytes to prevent security holes.

* Most python internals blindly use a signed Py_ssize_t to track

* things without checking for overflows or negatives.

* As size_t is unsigned, checking for size < 0 is not required.

*/

if (size > (size_t)PY_SSIZE_T_MAX)

return NULL;

return _PyMem_Raw.malloc(_PyMem_Raw.ctx, size);

}

void *

PyMem_RawCalloc(size_t nelem, size_t elsize)

{

/* see PyMem_RawMalloc() */

if (elsize != 0 && nelem > (size_t)PY_SSIZE_T_MAX / elsize)

return NULL;

return _PyMem_Raw.calloc(_PyMem_Raw.ctx, nelem, elsize);

}

void*

PyMem_RawRealloc(void *ptr, size_t new_size)

{

/* see PyMem_RawMalloc() */

if (new_size > (size_t)PY_SSIZE_T_MAX)

return NULL;

return _PyMem_Raw.realloc(_PyMem_Raw.ctx, ptr, new_size);

}

void

PyMem_RawFree(void *ptr)

{

_PyMem_Raw.free(_PyMem_Raw.ctx, ptr);

}

void *

PyMem_Malloc(size_t size)

{

/* see PyMem_RawMalloc() */

if (size > (size_t)PY_SSIZE_T_MAX)

return NULL;

return _PyMem.malloc(_PyMem.ctx, size);

}

void *

PyMem_Calloc(size_t nelem, size_t elsize)

{

/* see PyMem_RawMalloc() */

if (elsize != 0 && nelem > (size_t)PY_SSIZE_T_MAX / elsize)

return NULL;

return _PyMem.calloc(_PyMem.ctx, nelem, elsize);

}

void *

PyMem_Realloc(void *ptr, size_t new_size)

{

/* see PyMem_RawMalloc() */

if (new_size > (size_t)PY_SSIZE_T_MAX)

return NULL;

return _PyMem.realloc(_PyMem.ctx, ptr, new_size);

}

void

PyMem_Free(void *ptr)

{

_PyMem.free(_PyMem.ctx, ptr);

}

char *

_PyMem_RawStrdup(const char *str)

{

size_t size;

char *copy;

size = strlen(str) + 1;

copy = PyMem_RawMalloc(size);

if (copy == NULL)

return NULL;

memcpy(copy, str, size);

return copy;

}

char *

_PyMem_Strdup(const char *str)

{

size_t size;

char *copy;

size = strlen(str) + 1;

copy = PyMem_Malloc(size);

if (copy == NULL)

return NULL;

memcpy(copy, str, size);

return copy;

}

void *

PyObject_Malloc(size_t size)

{

/* see PyMem_RawMalloc() */

if (size > (size_t)PY_SSIZE_T_MAX)

return NULL;

return _PyObject.malloc(_PyObject.ctx, size);

}

void *

PyObject_Calloc(size_t nelem, size_t elsize)

{

/* see PyMem_RawMalloc() */

if (elsize != 0 && nelem > (size_t)PY_SSIZE_T_MAX / elsize)

return NULL;

return _PyObject.calloc(_PyObject.ctx, nelem, elsize);

}

void *

PyObject_Realloc(void *ptr, size_t new_size)

{

/* see PyMem_RawMalloc() */

if (new_size > (size_t)PY_SSIZE_T_MAX)

return NULL;

return _PyObject.realloc(_PyObject.ctx, ptr, new_size);

}

void

PyObject_Free(void *ptr)

{

_PyObject.free(_PyObject.ctx, ptr);

}

#ifdef WITH_PYMALLOC

#ifdef WITH_VALGRIND

#include <valgrind/valgrind.h>

/* If we're using GCC, use __builtin_expect() to reduce overhead of

the valgrind checks */

#if defined(__GNUC__) && (__GNUC__ > 2) && defined(__OPTIMIZE__)

# define UNLIKELY(value) __builtin_expect((value), 0)

#else

# define UNLIKELY(value) (value)

#endif

/* -1 indicates that we haven't checked that we're running on valgrind yet. */

static int running_on_valgrind = -1;

#endif

Py_ssize_t

_Py_GetAllocatedBlocks(void)

{

return _PyRuntime.mem.num_allocated_blocks;

}

/* Allocate a new arena. If we run out of memory, return NULL. Else

* allocate a new arena, and return the address of an arena_object

* describing the new arena. It's expected that the caller will set

* `usable_arenas` to the return value.

*/

static struct arena_object*

new_arena(void)

{

struct arena_object* arenaobj;

uint excess; /* number of bytes above pool alignment */

void *address;

static int debug_stats = -1;

if (debug_stats == -1) {

char *opt = Py_GETENV("PYTHONMALLOCSTATS");

debug_stats = (opt != NULL && *opt != '\0');

}

if (debug_stats)

_PyObject_DebugMallocStats(stderr);

if (_PyRuntime.mem.unused_arena_objects == NULL) {

uint i;

uint numarenas;

size_t nbytes;

/* Double the number of arena objects on each allocation.

* Note that it's possible for `numarenas` to overflow.

*/

numarenas = _PyRuntime.mem.maxarenas ? _PyRuntime.mem.maxarenas << 1 : INITIAL_ARENA_OBJECTS;

if (numarenas <= _PyRuntime.mem.maxarenas)

return NULL; /* overflow */

#if SIZEOF_SIZE_T <= SIZEOF_INT

if (numarenas > SIZE_MAX / sizeof(*_PyRuntime.mem.arenas))

return NULL; /* overflow */

#endif

nbytes = numarenas * sizeof(*_PyRuntime.mem.arenas);

arenaobj = (struct arena_object *)PyMem_RawRealloc(_PyRuntime.mem.arenas, nbytes);

if (arenaobj == NULL)

return NULL;

_PyRuntime.mem.arenas = arenaobj;

/* We might need to fix pointers that were copied. However,

* new_arena only gets called when all the pages in the

* previous arenas are full. Thus, there are *no* pointers

* into the old array. Thus, we don't have to worry about

* invalid pointers. Just to be sure, some asserts:

*/

assert(_PyRuntime.mem.usable_arenas == NULL);

assert(_PyRuntime.mem.unused_arena_objects == NULL);

/* Put the new arenas on the unused_arena_objects list. */

for (i = _PyRuntime.mem.maxarenas; i < numarenas; ++i) {

_PyRuntime.mem.arenas[i].address = 0; /* mark as unassociated */

_PyRuntime.mem.arenas[i].nextarena = i < numarenas - 1 ?

&_PyRuntime.mem.arenas[i+1] : NULL;

}

/* Update globals. */

_PyRuntime.mem.unused_arena_objects = &_PyRuntime.mem.arenas[_PyRuntime.mem.maxarenas];

_PyRuntime.mem.maxarenas = numarenas;

}

/* Take the next available arena object off the head of the list. */

assert(_PyRuntime.mem.unused_arena_objects != NULL);

arenaobj = _PyRuntime.mem.unused_arena_objects;

_PyRuntime.mem.unused_arena_objects = arenaobj->nextarena;

assert(arenaobj->address == 0);

address = _PyRuntime.obj.allocator_arenas.alloc(_PyRuntime.obj.allocator_arenas.ctx, ARENA_SIZE);

if (address == NULL) {

/* The allocation failed: return NULL after putting the

* arenaobj back.

*/

arenaobj->nextarena = _PyRuntime.mem.unused_arena_objects;

_PyRuntime.mem.unused_arena_objects = arenaobj;

return NULL;

}

arenaobj->address = (uintptr_t)address;

++_PyRuntime.mem.narenas_currently_allocated;

++_PyRuntime.mem.ntimes_arena_allocated;

if (_PyRuntime.mem.narenas_currently_allocated > _PyRuntime.mem.narenas_highwater)

_PyRuntime.mem.narenas_highwater = _PyRuntime.mem.narenas_currently_allocated;

arenaobj->freepools = NULL;

/* pool_address <- first pool-aligned address in the arena

nfreepools <- number of whole pools that fit after alignment */

arenaobj->pool_address = (pyblock*)arenaobj->address;

arenaobj->nfreepools = ARENA_SIZE / POOL_SIZE;

assert(POOL_SIZE * arenaobj->nfreepools == ARENA_SIZE);

excess = (uint)(arenaobj->address & POOL_SIZE_MASK);

if (excess != 0) {

--arenaobj->nfreepools;

arenaobj->pool_address += POOL_SIZE - excess;

}

arenaobj->ntotalpools = arenaobj->nfreepools;

return arenaobj;

}

/*

address_in_range(P, POOL)

Return true if and only if P is an address that was allocated by pymalloc.

POOL must be the pool address associated with P, i.e., POOL = POOL_ADDR(P)

(the caller is asked to compute this because the macro expands POOL more than

once, and for efficiency it's best for the caller to assign POOL_ADDR(P) to a

variable and pass the latter to the macro; because address_in_range is

called on every alloc/realloc/free, micro-efficiency is important here).

Tricky: Let B be the arena base address associated with the pool, B =

arenas[(POOL)->arenaindex].address. Then P belongs to the arena if and only if

B <= P < B + ARENA_SIZE

Subtracting B throughout, this is true iff

0 <= P-B < ARENA_SIZE

By using unsigned arithmetic, the "0 <=" half of the test can be skipped.

Obscure: A PyMem "free memory" function can call the pymalloc free or realloc

before the first arena has been allocated. `arenas` is still NULL in that

case. We're relying on that maxarenas is also 0 in that case, so that

(POOL)->arenaindex < maxarenas must be false, saving us from trying to index

into a NULL arenas.

Details: given P and POOL, the arena_object corresponding to P is AO =

arenas[(POOL)->arenaindex]. Suppose obmalloc controls P. Then (barring wild

stores, etc), POOL is the correct address of P's pool, AO.address is the

correct base address of the pool's arena, and P must be within ARENA_SIZE of

AO.address. In addition, AO.address is not 0 (no arena can start at address 0

(NULL)). Therefore address_in_range correctly reports that obmalloc

controls P.

Now suppose obmalloc does not control P (e.g., P was obtained via a direct

call to the system malloc() or realloc()). (POOL)->arenaindex may be anything

in this case -- it may even be uninitialized trash. If the trash arenaindex

is >= maxarenas, the macro correctly concludes at once that obmalloc doesn't

control P.

Else arenaindex is < maxarena, and AO is read up. If AO corresponds to an

allocated arena, obmalloc controls all the memory in slice AO.address :

AO.address+ARENA_SIZE. By case assumption, P is not controlled by obmalloc,

so P doesn't lie in that slice, so the macro correctly reports that P is not

controlled by obmalloc.

Finally, if P is not controlled by obmalloc and AO corresponds to an unused

arena_object (one not currently associated with an allocated arena),

AO.address is 0, and the second test in the macro reduces to:

P < ARENA_SIZE

If P >= ARENA_SIZE (extremely likely), the macro again correctly concludes

that P is not controlled by obmalloc. However, if P < ARENA_SIZE, this part

of the test still passes, and the third clause (AO.address != 0) is necessary

to get the correct result: AO.address is 0 in this case, so the macro

correctly reports that P is not controlled by obmalloc (despite that P lies in

slice AO.address : AO.address + ARENA_SIZE).

Note: The third (AO.address != 0) clause was added in Python 2.5. Before

2.5, arenas were never free()'ed, and an arenaindex < maxarena always

corresponded to a currently-allocated arena, so the "P is not controlled by

obmalloc, AO corresponds to an unused arena_object, and P < ARENA_SIZE" case

was impossible.

Note that the logic is excruciating, and reading up possibly uninitialized

memory when P is not controlled by obmalloc (to get at (POOL)->arenaindex)

creates problems for some memory debuggers. The overwhelming advantage is

that this test determines whether an arbitrary address is controlled by

obmalloc in a small constant time, independent of the number of arenas

obmalloc controls. Since this test is needed at every entry point, it's

extremely desirable that it be this fast.

*/

static bool ATTRIBUTE_NO_ADDRESS_SAFETY_ANALYSIS

address_in_range(void *p, poolp pool)

{

// Since address_in_range may be reading from memory which was not allocated

// by Python, it is important that pool->arenaindex is read only once, as

// another thread may be concurrently modifying the value without holding

// the GIL. The following dance forces the compiler to read pool->arenaindex

// only once.

uint arenaindex = *((volatile uint *)&pool->arenaindex);

return arenaindex < _PyRuntime.mem.maxarenas &&

(uintptr_t)p - _PyRuntime.mem.arenas[arenaindex].address < ARENA_SIZE &&

_PyRuntime.mem.arenas[arenaindex].address != 0;

}

/*==========================================================================*/

/* malloc. Note that nbytes==0 tries to return a non-NULL pointer, distinct

* from all other currently live pointers. This may not be possible.

*/

/*

* The basic blocks are ordered by decreasing execution frequency,

* which minimizes the number of jumps in the most common cases,

* improves branching prediction and instruction scheduling (small

* block allocations typically result in a couple of instructions).

* Unless the optimizer reorders everything, being too smart...

*/

static void *

_PyObject_Alloc(int use_calloc, void *ctx, size_t nelem, size_t elsize)

{

size_t nbytes;

pyblock *bp;

poolp pool;

poolp next;

uint size;

_PyRuntime.mem.num_allocated_blocks++;

assert(elsize == 0 || nelem <= PY_SSIZE_T_MAX / elsize);

nbytes = nelem * elsize;

#ifdef WITH_VALGRIND

if (UNLIKELY(running_on_valgrind == -1))

running_on_valgrind = RUNNING_ON_VALGRIND;

if (UNLIKELY(running_on_valgrind))

goto redirect;

#endif

if (nelem == 0 || elsize == 0)

goto redirect;

if ((nbytes - 1) < SMALL_REQUEST_THRESHOLD) {

LOCK();

/*

* Most frequent paths first

*/

size = (uint)(nbytes - 1) >> ALIGNMENT_SHIFT;

pool = _PyRuntime.mem.usedpools[size + size];

if (pool != pool->nextpool) {

/*

* There is a used pool for this size class.

* Pick up the head block of its free list.

*/

++pool->ref.count;

bp = pool->freeblock;

assert(bp != NULL);

if ((pool->freeblock = *(pyblock **)bp) != NULL) {

UNLOCK();

if (use_calloc)

memset(bp, 0, nbytes);

return (void *)bp;

}

/*

* Reached the end of the free list, try to extend it.

*/

if (pool->nextoffset <= pool->maxnextoffset) {

/* There is room for another block. */

pool->freeblock = (pyblock*)pool +

pool->nextoffset;

pool->nextoffset += INDEX2SIZE(size);

*(pyblock **)(pool->freeblock) = NULL;

UNLOCK();

if (use_calloc)

memset(bp, 0, nbytes);

return (void *)bp;

}

/* Pool is full, unlink from used pools. */

next = pool->nextpool;

pool = pool->prevpool;

next->prevpool = pool;

pool->nextpool = next;

UNLOCK();

if (use_calloc)

memset(bp, 0, nbytes);

return (void *)bp;

}

/* There isn't a pool of the right size class immediately

* available: use a free pool.

*/

if (_PyRuntime.mem.usable_arenas == NULL) {

/* No arena has a free pool: allocate a new arena. */

#ifdef WITH_MEMORY_LIMITS

if (_PyRuntime.mem.narenas_currently_allocated >= MAX_ARENAS) {

UNLOCK();

goto redirect;

}

#endif

_PyRuntime.mem.usable_arenas = new_arena();

if (_PyRuntime.mem.usable_arenas == NULL) {

UNLOCK();

goto redirect;

}

_PyRuntime.mem.usable_arenas->nextarena =

_PyRuntime.mem.usable_arenas->prevarena = NULL;

}

assert(_PyRuntime.mem.usable_arenas->address != 0);

/* Try to get a cached free pool. */

pool = _PyRuntime.mem.usable_arenas->freepools;

if (pool != NULL) {

/* Unlink from cached pools. */

_PyRuntime.mem.usable_arenas->freepools = pool->nextpool;

/* This arena already had the smallest nfreepools

* value, so decreasing nfreepools doesn't change

* that, and we don't need to rearrange the

* usable_arenas list. However, if the arena has

* become wholly allocated, we need to remove its

* arena_object from usable_arenas.

*/

--_PyRuntime.mem.usable_arenas->nfreepools;

if (_PyRuntime.mem.usable_arenas->nfreepools == 0) {

/* Wholly allocated: remove. */

assert(_PyRuntime.mem.usable_arenas->freepools == NULL);

assert(_PyRuntime.mem.usable_arenas->nextarena == NULL ||

_PyRuntime.mem.usable_arenas->nextarena->prevarena ==

_PyRuntime.mem.usable_arenas);

_PyRuntime.mem.usable_arenas = _PyRuntime.mem.usable_arenas->nextarena;

if (_PyRuntime.mem.usable_arenas != NULL) {

_PyRuntime.mem.usable_arenas->prevarena = NULL;

assert(_PyRuntime.mem.usable_arenas->address != 0);

}

}

else {

/* nfreepools > 0: it must be that freepools

* isn't NULL, or that we haven't yet carved

* off all the arena's pools for the first

* time.

*/

assert(_PyRuntime.mem.usable_arenas->freepools != NULL ||

_PyRuntime.mem.usable_arenas->pool_address <=

(pyblock*)_PyRuntime.mem.usable_arenas->address +

ARENA_SIZE - POOL_SIZE);

}

init_pool:

/* Frontlink to used pools. */

next = _PyRuntime.mem.usedpools[size + size]; /* == prev */

pool->nextpool = next;

pool->prevpool = next;

next->nextpool = pool;

next->prevpool = pool;

pool->ref.count = 1;

if (pool->szidx == size) {

/* Luckily, this pool last contained blocks

* of the same size class, so its header

* and free list are already initialized.

*/

bp = pool->freeblock;

assert(bp != NULL);

pool->freeblock = *(pyblock **)bp;

UNLOCK();

if (use_calloc)

memset(bp, 0, nbytes);

return (void *)bp;

}

/*

* Initialize the pool header, set up the free list to

* contain just the second block, and return the first

* block.

*/

pool->szidx = size;

size = INDEX2SIZE(size);

bp = (pyblock *)pool + POOL_OVERHEAD;

pool->nextoffset = POOL_OVERHEAD + (size << 1);

pool->maxnextoffset = POOL_SIZE - size;

pool->freeblock = bp + size;

*(pyblock **)(pool->freeblock) = NULL;

UNLOCK();

if (use_calloc)

memset(bp, 0, nbytes);

return (void *)bp;

}

/* Carve off a new pool. */

assert(_PyRuntime.mem.usable_arenas->nfreepools > 0);

assert(_PyRuntime.mem.usable_arenas->freepools == NULL);

pool = (poolp)_PyRuntime.mem.usable_arenas->pool_address;

assert((pyblock*)pool <= (pyblock*)_PyRuntime.mem.usable_arenas->address +

ARENA_SIZE - POOL_SIZE);

pool->arenaindex = (uint)(_PyRuntime.mem.usable_arenas - _PyRuntime.mem.arenas);

assert(&_PyRuntime.mem.arenas[pool->arenaindex] == _PyRuntime.mem.usable_arenas);

pool->szidx = DUMMY_SIZE_IDX;

_PyRuntime.mem.usable_arenas->pool_address += POOL_SIZE;

--_PyRuntime.mem.usable_arenas->nfreepools;

if (_PyRuntime.mem.usable_arenas->nfreepools == 0) {

assert(_PyRuntime.mem.usable_arenas->nextarena == NULL ||

_PyRuntime.mem.usable_arenas->nextarena->prevarena ==

_PyRuntime.mem.usable_arenas);

/* Unlink the arena: it is completely allocated. */

_PyRuntime.mem.usable_arenas = _PyRuntime.mem.usable_arenas->nextarena;

if (_PyRuntime.mem.usable_arenas != NULL) {

_PyRuntime.mem.usable_arenas->prevarena = NULL;

assert(_PyRuntime.mem.usable_arenas->address != 0);

}

}

goto init_pool;

}

/* The small block allocator ends here. */

redirect:

/* Redirect the original request to the underlying (libc) allocator.

* We jump here on bigger requests, on error in the code above (as a

* last chance to serve the request) or when the max memory limit

* has been reached.

*/

{

void *result;

if (use_calloc)

result = PyMem_RawCalloc(nelem, elsize);

else

result = PyMem_RawMalloc(nbytes);

if (!result)

_PyRuntime.mem.num_allocated_blocks--;

return result;

}

}

static void *

_PyObject_Malloc(void *ctx, size_t nbytes)

{

return _PyObject_Alloc(0, ctx, 1, nbytes);

}

static void *

_PyObject_Calloc(void *ctx, size_t nelem, size_t elsize)

{

return _PyObject_Alloc(1, ctx, nelem, elsize);

}

/* free */

static void

_PyObject_Free(void *ctx, void *p)

{

poolp pool;

pyblock *lastfree;