#include "Python.h"

#include <stdbool.h>

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

#undef uint

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

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

#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

#ifdef WITH_PYMALLOC

#ifdef MS_WINDOWS

# include <windows.h>

#elif defined(HAVE_MMAP)

# include <sys/mman.h>

# ifdef MAP_ANONYMOUS

# define ARENAS_USE_MMAP

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

static void *

_PyMem_RawMalloc(void *ctx, size_t size)

{

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

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

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

}

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

}

#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

# define PYOBJ_FUNCS PYRAW_FUNCS

#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

static PyMemAllocatorEx _PyMem_Raw = {

#ifdef Py_DEBUG

&_PyMem_Debug.raw, PYRAWDBG_FUNCS

NULL, PYRAW_FUNCS

};

static PyMemAllocatorEx _PyMem = {

#ifdef Py_DEBUG

&_PyMem_Debug.mem, PYDBG_FUNCS

NULL, PYMEM_FUNCS

};

static PyMemAllocatorEx _PyObject = {

#ifdef Py_DEBUG

&_PyMem_Debug.obj, PYDBG_FUNCS

NULL, PYOBJ_FUNCS

};

_PyMem_SetupAllocators(const char *opt)

{

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

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

#ifdef Py_DEBUG

# ifdef WITH_PYMALLOC

opt = "pymalloc_debug";

opt = "malloc_debug";

/* !Py_DEBUG */

# ifdef WITH_PYMALLOC

opt = "pymalloc";

opt = "malloc";

}

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

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;

}

}

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

}

}

PyObject_GetArenaAllocator(PyObjectArenaAllocator *allocator)

{

*allocator = _PyObject_Arena;

}

PyObject_SetArenaAllocator(PyObjectArenaAllocator *allocator)

{

_PyObject_Arena = *allocator;

}

void *

PyMem_RawMalloc(size_t size)

{

/*

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

}

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

}

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

}

PyObject_Free(void *ptr)

{

_PyObject.free(_PyObject.ctx, ptr);

}

#ifdef WITH_PYMALLOC

#ifdef WITH_VALGRIND

#include <valgrind/valgrind.h>

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

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

# define UNLIKELY(value) (value)

static int running_on_valgrind = -1;

/* #undef WITH_MEMORY_LIMITS */ /* disable mem limit checks */

#define ALIGNMENT 8 /* must be 2^N */

#define ALIGNMENT_SHIFT 3

#define INDEX2SIZE(I) (((uint)(I) + 1) << ALIGNMENT_SHIFT)

#define SMALL_REQUEST_THRESHOLD 512

#define NB_SMALL_SIZE_CLASSES (SMALL_REQUEST_THRESHOLD / ALIGNMENT)

#define SYSTEM_PAGE_SIZE (4 * 1024)

#define SYSTEM_PAGE_SIZE_MASK (SYSTEM_PAGE_SIZE - 1)

#ifdef WITH_MEMORY_LIMITS

#ifndef SMALL_MEMORY_LIMIT

#define SMALL_MEMORY_LIMIT (64 * 1024 * 1024) /* 64 MB -- more? */

#define ARENA_SIZE (256 << 10) /* 256KB */

#ifdef WITH_MEMORY_LIMITS

#define MAX_ARENAS (SMALL_MEMORY_LIMIT / ARENA_SIZE)

#define POOL_SIZE SYSTEM_PAGE_SIZE /* must be 2^N */

#define POOL_SIZE_MASK SYSTEM_PAGE_SIZE_MASK

#define SIMPLELOCK_DECL(lock) /* simple lock declaration */

#define SIMPLELOCK_INIT(lock) /* allocate (if needed) and initialize */

#define SIMPLELOCK_FINI(lock) /* free/destroy an existing lock */

#define SIMPLELOCK_LOCK(lock) /* acquire released lock */

#define SIMPLELOCK_UNLOCK(lock) /* release acquired lock */

typedef uint8_t block;

struct pool_header {

};

typedef struct pool_header *poolp;

struct arena_object {

};

#define POOL_OVERHEAD _Py_SIZE_ROUND_UP(sizeof(struct pool_header), ALIGNMENT)

#define DUMMY_SIZE_IDX 0xffff /* size class of newly cached pools */

#define POOL_ADDR(P) ((poolp)_Py_ALIGN_DOWN((P), POOL_SIZE))

#define NUMBLOCKS(I) ((uint)(POOL_SIZE - POOL_OVERHEAD) / INDEX2SIZE(I))

SIMPLELOCK_DECL(_malloc_lock)

#define LOCK() SIMPLELOCK_LOCK(_malloc_lock)

#define UNLOCK() SIMPLELOCK_UNLOCK(_malloc_lock)

#define LOCK_INIT() SIMPLELOCK_INIT(_malloc_lock)

#define LOCK_FINI() SIMPLELOCK_FINI(_malloc_lock)

#define PTA(x) ((poolp )((uint8_t *)&(usedpools[2*(x)]) - 2*sizeof(block *)))

#define PT(x) PTA(x), PTA(x)

static poolp usedpools[2 * ((NB_SMALL_SIZE_CLASSES + 7) / 8) * 8] = {

PT(0), PT(1), PT(2), PT(3), PT(4), PT(5), PT(6), PT(7)

#if NB_SMALL_SIZE_CLASSES > 8

, PT(8), PT(9), PT(10), PT(11), PT(12), PT(13), PT(14), PT(15)

#if NB_SMALL_SIZE_CLASSES > 16

, PT(16), PT(17), PT(18), PT(19), PT(20), PT(21), PT(22), PT(23)

#if NB_SMALL_SIZE_CLASSES > 24

, PT(24), PT(25), PT(26), PT(27), PT(28), PT(29), PT(30), PT(31)

#if NB_SMALL_SIZE_CLASSES > 32

, PT(32), PT(33), PT(34), PT(35), PT(36), PT(37), PT(38), PT(39)

#if NB_SMALL_SIZE_CLASSES > 40

, PT(40), PT(41), PT(42), PT(43), PT(44), PT(45), PT(46), PT(47)

#if NB_SMALL_SIZE_CLASSES > 48

, PT(48), PT(49), PT(50), PT(51), PT(52), PT(53), PT(54), PT(55)

#if NB_SMALL_SIZE_CLASSES > 56

, PT(56), PT(57), PT(58), PT(59), PT(60), PT(61), PT(62), PT(63)

#if NB_SMALL_SIZE_CLASSES > 64

#error "NB_SMALL_SIZE_CLASSES should be less than 64"

#endif /* NB_SMALL_SIZE_CLASSES > 64 */

#endif /* NB_SMALL_SIZE_CLASSES > 56 */

#endif /* NB_SMALL_SIZE_CLASSES > 48 */

#endif /* NB_SMALL_SIZE_CLASSES > 40 */

#endif /* NB_SMALL_SIZE_CLASSES > 32 */

#endif /* NB_SMALL_SIZE_CLASSES > 24 */

#endif /* NB_SMALL_SIZE_CLASSES > 16 */

#endif /* NB_SMALL_SIZE_CLASSES > 8 */

};

static struct arena_object* arenas = NULL;

static uint maxarenas = 0;

static struct arena_object* unused_arena_objects = NULL;

static struct arena_object* usable_arenas = NULL;

#define INITIAL_ARENA_OBJECTS 16