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