14710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#include "Python.h" 24710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#include "pyarena.h" 34710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 44710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm/* A simple arena block structure. 54710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 64710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Measurements with standard library modules suggest the average 74710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm allocation is about 20 bytes and that most compiles use a single 84710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm block. 94710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 104710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm TODO(jhylton): Think about a realloc API, maybe just for the last 114710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm allocation? 124710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm*/ 134710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 144710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#define DEFAULT_BLOCK_SIZE 8192 154710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#define ALIGNMENT 8 164710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#define ALIGNMENT_MASK (ALIGNMENT - 1) 174710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#define ROUNDUP(x) (((x) + ALIGNMENT_MASK) & ~ALIGNMENT_MASK) 184710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 194710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmtypedef struct _block { 204710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* Total number of bytes owned by this block available to pass out. 214710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * Read-only after initialization. The first such byte starts at 224710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * ab_mem. 234710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm */ 244710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm size_t ab_size; 254710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 264710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* Total number of bytes already passed out. The next byte available 274710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * to pass out starts at ab_mem + ab_offset. 284710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm */ 294710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm size_t ab_offset; 304710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 314710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* An arena maintains a singly-linked, NULL-terminated list of 324710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * all blocks owned by the arena. These are linked via the 334710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * ab_next member. 344710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm */ 354710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm struct _block *ab_next; 364710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 374710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* Pointer to the first allocatable byte owned by this block. Read- 384710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * only after initialization. 394710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm */ 404710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm void *ab_mem; 414710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} block; 424710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 434710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm/* The arena manages two kinds of memory, blocks of raw memory 444710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm and a list of PyObject* pointers. PyObjects are decrefed 454710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm when the arena is freed. 464710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm*/ 474710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 484710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstruct _arena { 494710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* Pointer to the first block allocated for the arena, never NULL. 504710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm It is used only to find the first block when the arena is 514710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm being freed. 524710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm */ 534710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm block *a_head; 544710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 554710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* Pointer to the block currently used for allocation. It's 564710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm ab_next field should be NULL. If it is not-null after a 574710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm call to block_alloc(), it means a new block has been allocated 584710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm and a_cur should be reset to point it. 594710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm */ 604710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm block *a_cur; 614710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 624710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* A Python list object containing references to all the PyObject 634710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm pointers associated with this area. They will be DECREFed 644710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm when the arena is freed. 654710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm */ 664710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyObject *a_objects; 674710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 684710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#if defined(Py_DEBUG) 694710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* Debug output */ 704710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm size_t total_allocs; 714710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm size_t total_size; 724710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm size_t total_blocks; 734710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm size_t total_block_size; 744710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm size_t total_big_blocks; 754710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#endif 764710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm}; 774710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 784710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic block * 794710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmblock_new(size_t size) 804710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 814710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* Allocate header and block as one unit. 824710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm ab_mem points just past header. */ 834710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm block *b = (block *)malloc(sizeof(block) + size); 844710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (!b) 854710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 864710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm b->ab_size = size; 874710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm b->ab_mem = (void *)(b + 1); 884710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm b->ab_next = NULL; 894710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm b->ab_offset = ROUNDUP((Py_uintptr_t)(b->ab_mem)) - 904710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (Py_uintptr_t)(b->ab_mem); 914710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return b; 924710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 934710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 944710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic void 954710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmblock_free(block *b) { 964710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm while (b) { 974710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm block *next = b->ab_next; 984710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm free(b); 994710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm b = next; 1004710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 1014710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 1024710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1034710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic void * 1044710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmblock_alloc(block *b, size_t size) 1054710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 1064710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm void *p; 1074710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assert(b); 1084710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm size = ROUNDUP(size); 1094710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (b->ab_offset + size > b->ab_size) { 1104710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* If we need to allocate more memory than will fit in 1114710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm the default block, allocate a one-off block that is 1124710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm exactly the right size. */ 1134710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* TODO(jhylton): Think about space waste at end of block */ 1144710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm block *newbl = block_new( 1154710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm size < DEFAULT_BLOCK_SIZE ? 1164710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm DEFAULT_BLOCK_SIZE : size); 1174710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (!newbl) 1184710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 1194710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assert(!b->ab_next); 1204710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm b->ab_next = newbl; 1214710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm b = newbl; 1224710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 1234710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1244710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assert(b->ab_offset + size <= b->ab_size); 1254710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm p = (void *)(((char *)b->ab_mem) + b->ab_offset); 1264710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm b->ab_offset += size; 1274710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return p; 1284710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 1294710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1304710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmPyArena * 1314710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmPyArena_New() 1324710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 1334710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyArena* arena = (PyArena *)malloc(sizeof(PyArena)); 1344710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (!arena) 1354710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return (PyArena*)PyErr_NoMemory(); 1364710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1374710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm arena->a_head = block_new(DEFAULT_BLOCK_SIZE); 1384710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm arena->a_cur = arena->a_head; 1394710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (!arena->a_head) { 1404710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm free((void *)arena); 1414710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return (PyArena*)PyErr_NoMemory(); 1424710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 1434710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm arena->a_objects = PyList_New(0); 1444710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (!arena->a_objects) { 1454710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm block_free(arena->a_head); 1464710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm free((void *)arena); 1474710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return (PyArena*)PyErr_NoMemory(); 1484710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 1494710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#if defined(Py_DEBUG) 1504710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm arena->total_allocs = 0; 1514710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm arena->total_size = 0; 1524710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm arena->total_blocks = 1; 1534710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm arena->total_block_size = DEFAULT_BLOCK_SIZE; 1544710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm arena->total_big_blocks = 0; 1554710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#endif 1564710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return arena; 1574710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 1584710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1594710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmvoid 1604710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmPyArena_Free(PyArena *arena) 1614710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 1624710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm int r; 1634710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assert(arena); 1644710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#if defined(Py_DEBUG) 1654710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* 1664710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm fprintf(stderr, 1674710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm "alloc=%d size=%d blocks=%d block_size=%d big=%d objects=%d\n", 1684710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm arena->total_allocs, arena->total_size, arena->total_blocks, 1694710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm arena->total_block_size, arena->total_big_blocks, 1704710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyList_Size(arena->a_objects)); 1714710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm */ 1724710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#endif 1734710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm block_free(arena->a_head); 1744710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* This property normally holds, except when the code being compiled 1754710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm is sys.getobjects(0), in which case there will be two references. 1764710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assert(arena->a_objects->ob_refcnt == 1); 1774710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm */ 1784710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1794710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* Clear all the elements from the list. This is necessary 1804710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm to guarantee that they will be DECREFed. */ 1814710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm r = PyList_SetSlice(arena->a_objects, 1824710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, PyList_GET_SIZE(arena->a_objects), NULL); 1834710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assert(r == 0); 1844710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assert(PyList_GET_SIZE(arena->a_objects) == 0); 1854710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(arena->a_objects); 1864710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm free(arena); 1874710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 1884710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1894710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmvoid * 1904710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmPyArena_Malloc(PyArena *arena, size_t size) 1914710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 1924710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm void *p = block_alloc(arena->a_cur, size); 1934710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (!p) 1944710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return PyErr_NoMemory(); 1954710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#if defined(Py_DEBUG) 1964710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm arena->total_allocs++; 1974710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm arena->total_size += size; 1984710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#endif 1994710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* Reset cur if we allocated a new block. */ 2004710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (arena->a_cur->ab_next) { 2014710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm arena->a_cur = arena->a_cur->ab_next; 2024710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#if defined(Py_DEBUG) 2034710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm arena->total_blocks++; 2044710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm arena->total_block_size += arena->a_cur->ab_size; 2054710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (arena->a_cur->ab_size > DEFAULT_BLOCK_SIZE) 2064710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm ++arena->total_big_blocks; 2074710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#endif 2084710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 2094710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return p; 2104710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 2114710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2124710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmint 2134710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmPyArena_AddPyObject(PyArena *arena, PyObject *obj) 2144710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 2154710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm int r = PyList_Append(arena->a_objects, obj); 2164710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (r >= 0) { 2174710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(obj); 2184710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 2194710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return r; 2204710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 221