1 #include "Python.h" 2 #include "pyarena.h" 3 4 /* A simple arena block structure. 5 6 Measurements with standard library modules suggest the average 7 allocation is about 20 bytes and that most compiles use a single 8 block. 9 10 TODO(jhylton): Think about a realloc API, maybe just for the last 11 allocation? 12 */ 13 14 #define DEFAULT_BLOCK_SIZE 8192 15 #define ALIGNMENT 8 16 #define ALIGNMENT_MASK (ALIGNMENT - 1) 17 #define ROUNDUP(x) (((x) + ALIGNMENT_MASK) & ~ALIGNMENT_MASK) 18 19 typedef struct _block { 20 /* Total number of bytes owned by this block available to pass out. 21 * Read-only after initialization. The first such byte starts at 22 * ab_mem. 23 */ 24 size_t ab_size; 25 26 /* Total number of bytes already passed out. The next byte available 27 * to pass out starts at ab_mem + ab_offset. 28 */ 29 size_t ab_offset; 30 31 /* An arena maintains a singly-linked, NULL-terminated list of 32 * all blocks owned by the arena. These are linked via the 33 * ab_next member. 34 */ 35 struct _block *ab_next; 36 37 /* Pointer to the first allocatable byte owned by this block. Read- 38 * only after initialization. 39 */ 40 void *ab_mem; 41 } block; 42 43 /* The arena manages two kinds of memory, blocks of raw memory 44 and a list of PyObject* pointers. PyObjects are decrefed 45 when the arena is freed. 46 */ 47 48 struct _arena { 49 /* Pointer to the first block allocated for the arena, never NULL. 50 It is used only to find the first block when the arena is 51 being freed. 52 */ 53 block *a_head; 54 55 /* Pointer to the block currently used for allocation. It's 56 ab_next field should be NULL. If it is not-null after a 57 call to block_alloc(), it means a new block has been allocated 58 and a_cur should be reset to point it. 59 */ 60 block *a_cur; 61 62 /* A Python list object containing references to all the PyObject 63 pointers associated with this area. They will be DECREFed 64 when the arena is freed. 65 */ 66 PyObject *a_objects; 67 68 #if defined(Py_DEBUG) 69 /* Debug output */ 70 size_t total_allocs; 71 size_t total_size; 72 size_t total_blocks; 73 size_t total_block_size; 74 size_t total_big_blocks; 75 #endif 76 }; 77 78 static block * 79 block_new(size_t size) 80 { 81 /* Allocate header and block as one unit. 82 ab_mem points just past header. */ 83 block *b = (block *)malloc(sizeof(block) + size); 84 if (!b) 85 return NULL; 86 b->ab_size = size; 87 b->ab_mem = (void *)(b + 1); 88 b->ab_next = NULL; 89 b->ab_offset = ROUNDUP((Py_uintptr_t)(b->ab_mem)) - 90 (Py_uintptr_t)(b->ab_mem); 91 return b; 92 } 93 94 static void 95 block_free(block *b) { 96 while (b) { 97 block *next = b->ab_next; 98 free(b); 99 b = next; 100 } 101 } 102 103 static void * 104 block_alloc(block *b, size_t size) 105 { 106 void *p; 107 assert(b); 108 size = ROUNDUP(size); 109 if (b->ab_offset + size > b->ab_size) { 110 /* If we need to allocate more memory than will fit in 111 the default block, allocate a one-off block that is 112 exactly the right size. */ 113 /* TODO(jhylton): Think about space waste at end of block */ 114 block *newbl = block_new( 115 size < DEFAULT_BLOCK_SIZE ? 116 DEFAULT_BLOCK_SIZE : size); 117 if (!newbl) 118 return NULL; 119 assert(!b->ab_next); 120 b->ab_next = newbl; 121 b = newbl; 122 } 123 124 assert(b->ab_offset + size <= b->ab_size); 125 p = (void *)(((char *)b->ab_mem) + b->ab_offset); 126 b->ab_offset += size; 127 return p; 128 } 129 130 PyArena * 131 PyArena_New() 132 { 133 PyArena* arena = (PyArena *)malloc(sizeof(PyArena)); 134 if (!arena) 135 return (PyArena*)PyErr_NoMemory(); 136 137 arena->a_head = block_new(DEFAULT_BLOCK_SIZE); 138 arena->a_cur = arena->a_head; 139 if (!arena->a_head) { 140 free((void *)arena); 141 return (PyArena*)PyErr_NoMemory(); 142 } 143 arena->a_objects = PyList_New(0); 144 if (!arena->a_objects) { 145 block_free(arena->a_head); 146 free((void *)arena); 147 return (PyArena*)PyErr_NoMemory(); 148 } 149 #if defined(Py_DEBUG) 150 arena->total_allocs = 0; 151 arena->total_size = 0; 152 arena->total_blocks = 1; 153 arena->total_block_size = DEFAULT_BLOCK_SIZE; 154 arena->total_big_blocks = 0; 155 #endif 156 return arena; 157 } 158 159 void 160 PyArena_Free(PyArena *arena) 161 { 162 assert(arena); 163 #if defined(Py_DEBUG) 164 /* 165 fprintf(stderr, 166 "alloc=%d size=%d blocks=%d block_size=%d big=%d objects=%d\n", 167 arena->total_allocs, arena->total_size, arena->total_blocks, 168 arena->total_block_size, arena->total_big_blocks, 169 PyList_Size(arena->a_objects)); 170 */ 171 #endif 172 block_free(arena->a_head); 173 /* This property normally holds, except when the code being compiled 174 is sys.getobjects(0), in which case there will be two references. 175 assert(arena->a_objects->ob_refcnt == 1); 176 */ 177 178 Py_DECREF(arena->a_objects); 179 free(arena); 180 } 181 182 void * 183 PyArena_Malloc(PyArena *arena, size_t size) 184 { 185 void *p = block_alloc(arena->a_cur, size); 186 if (!p) 187 return PyErr_NoMemory(); 188 #if defined(Py_DEBUG) 189 arena->total_allocs++; 190 arena->total_size += size; 191 #endif 192 /* Reset cur if we allocated a new block. */ 193 if (arena->a_cur->ab_next) { 194 arena->a_cur = arena->a_cur->ab_next; 195 #if defined(Py_DEBUG) 196 arena->total_blocks++; 197 arena->total_block_size += arena->a_cur->ab_size; 198 if (arena->a_cur->ab_size > DEFAULT_BLOCK_SIZE) 199 ++arena->total_big_blocks; 200 #endif 201 } 202 return p; 203 } 204 205 int 206 PyArena_AddPyObject(PyArena *arena, PyObject *obj) 207 { 208 int r = PyList_Append(arena->a_objects, obj); 209 if (r >= 0) { 210 Py_DECREF(obj); 211 } 212 return r; 213 } 214
