#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 *ptr);

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;

}

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

/* pymalloc allocator

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...

Return 1 if pymalloc allocated memory and wrote the pointer into *ptr_p.

Return 0 if pymalloc failed to allocate the memory block: on bigger

requests, on error in the code below (as a last chance to serve the request)

or when the max memory limit has been reached. */

static int

pymalloc_alloc(void *ctx, void **ptr_p, size_t nbytes)

{

pyblock *bp;

poolp pool;

poolp next;

uint size;

#ifdef WITH_VALGRIND

if (UNLIKELY(running_on_valgrind == -1)) {

running_on_valgrind = RUNNING_ON_VALGRIND;

}

if (UNLIKELY(running_on_valgrind)) {

return 0;

}

#endif

if (nbytes == 0) {

return 0;

}

if (nbytes > SMALL_REQUEST_THRESHOLD) {

return 0;

}

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) {

goto success;

}

/*

* 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;

goto success;

}

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

next = pool->nextpool;

pool = pool->prevpool;

next->prevpool = pool;

pool->nextpool = next;

goto success;

}

/* 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) {

goto failed;

}

#endif

_PyRuntime.mem.usable_arenas = new_arena();

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

goto failed;

}

_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;

goto success;

}

/*

* 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;

goto success;

}

/* 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;

success:

UNLOCK();

assert(bp != NULL);

*ptr_p = (void *)bp;

return 1;

failed:

UNLOCK();

return 0;

}

static void *

_PyObject_Malloc(void *ctx, size_t nbytes)

{

void* ptr;

if (pymalloc_alloc(ctx, &ptr, nbytes)) {

_PyRuntime.mem.num_allocated_blocks++;

return ptr;

}

ptr = PyMem_RawMalloc(nbytes);

if (ptr != NULL) {

_PyRuntime.mem.num_allocated_blocks++;

}

return ptr;

}

static void *

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

{

void* ptr;

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

size_t nbytes = nelem * elsize;

if (pymalloc_alloc(ctx, &ptr, nbytes)) {

memset(ptr, 0, nbytes);

_PyRuntime.mem.num_allocated_blocks++;

return ptr;

}

ptr = PyMem_RawCalloc(nelem, elsize);

if (ptr != NULL) {

_PyRuntime.mem.num_allocated_blocks++;

}

return ptr;

}