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