1 #include "Python.h"
2
3 /* A simple arena block structure.
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.
8
9 TODO(jhylton): Think about a realloc API, maybe just for the last
10 allocation?
11 */
12
13 #define DEFAULT_BLOCK_SIZE 8192
14 #define ALIGNMENT 8
15
16 typedef struct _block {
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;
22
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;
27
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;
33
34 /* Pointer to the first allocatable byte owned by this block. Read-
35 * only after initialization.
36 */
37 void *ab_mem;
38 } block;
39
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 */
44
45 struct _arena {
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;
51
52 /* Pointer to the block currently used for allocation. It's
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;
58
59 /* A Python list object containing references to all the PyObject
60 pointers associated with this area. They will be DECREFed
61 when the arena is freed.
62 */
63 PyObject *a_objects;
64
65 #if defined(Py_DEBUG)
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;
72 #endif
73 };
74
75 static block *
block_new(size_t size)76 block_new(size_t size)
77 {
78 /* Allocate header and block as one unit.
79 ab_mem points just past header. */
80 block *b = (block *)PyMem_Malloc(sizeof(block) + size);
81 if (!b)
82 return NULL;
83 b->ab_size = size;
84 b->ab_mem = (void *)(b + 1);
85 b->ab_next = NULL;
86 b->ab_offset = (char *)_Py_ALIGN_UP(b->ab_mem, ALIGNMENT) -
87 (char *)(b->ab_mem);
88 return b;
89 }
90
91 static void
block_free(block * b)92 block_free(block *b) {
93 while (b) {
94 block *next = b->ab_next;
95 PyMem_Free(b);
96 b = next;
97 }
98 }
99
100 static void *
block_alloc(block * b,size_t size)101 block_alloc(block *b, size_t size)
102 {
103 void *p;
104 assert(b);
105 size = _Py_SIZE_ROUND_UP(size, ALIGNMENT);
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 }
120
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;
125 }
126
127 PyArena *
PyArena_New()128 PyArena_New()
129 {
130 PyArena* arena = (PyArena *)PyMem_Malloc(sizeof(PyArena));
131 if (!arena)
132 return (PyArena*)PyErr_NoMemory();
133
134 arena->a_head = block_new(DEFAULT_BLOCK_SIZE);
135 arena->a_cur = arena->a_head;
136 if (!arena->a_head) {
137 PyMem_Free((void *)arena);
138 return (PyArena*)PyErr_NoMemory();
139 }
140 arena->a_objects = PyList_New(0);
141 if (!arena->a_objects) {
142 block_free(arena->a_head);
143 PyMem_Free((void *)arena);
144 return (PyArena*)PyErr_NoMemory();
145 }
146 #if defined(Py_DEBUG)
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;
152 #endif
153 return arena;
154 }
155
156 void
PyArena_Free(PyArena * arena)157 PyArena_Free(PyArena *arena)
158 {
159 assert(arena);
160 #if defined(Py_DEBUG)
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 */
168 #endif
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 */
174
175 Py_DECREF(arena->a_objects);
176 PyMem_Free(arena);
177 }
178
179 void *
PyArena_Malloc(PyArena * arena,size_t size)180 PyArena_Malloc(PyArena *arena, size_t size)
181 {
182 void *p = block_alloc(arena->a_cur, size);
183 if (!p)
184 return PyErr_NoMemory();
185 #if defined(Py_DEBUG)
186 arena->total_allocs++;
187 arena->total_size += size;
188 #endif
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;
192 #if defined(Py_DEBUG)
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;
197 #endif
198 }
199 return p;
200 }
201
202 int
PyArena_AddPyObject(PyArena * arena,PyObject * obj)203 PyArena_AddPyObject(PyArena *arena, PyObject *obj)
204 {
205 int r = PyList_Append(arena->a_objects, obj);
206 if (r >= 0) {
207 Py_DECREF(obj);
208 }
209 return r;
210 }
211