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