Line data Source code
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 346 : block_new(size_t size)
80 : {
81 : /* Allocate header and block as one unit.
82 : ab_mem points just past header. */
83 346 : block *b = (block *)malloc(sizeof(block) + size);
84 346 : if (!b)
85 0 : return NULL;
86 346 : b->ab_size = size;
87 346 : b->ab_mem = (void *)(b + 1);
88 346 : b->ab_next = NULL;
89 692 : b->ab_offset = ROUNDUP((Py_uintptr_t)(b->ab_mem)) -
90 346 : (Py_uintptr_t)(b->ab_mem);
91 346 : return b;
92 : }
93 :
94 : static void
95 63 : block_free(block *b) {
96 472 : while (b) {
97 346 : block *next = b->ab_next;
98 346 : free(b);
99 346 : b = next;
100 : }
101 63 : }
102 :
103 : static void *
104 57570 : block_alloc(block *b, size_t size)
105 : {
106 : void *p;
107 : assert(b);
108 57570 : size = ROUNDUP(size);
109 57570 : 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 283 : block *newbl = block_new(
115 : size < DEFAULT_BLOCK_SIZE ?
116 : DEFAULT_BLOCK_SIZE : size);
117 283 : if (!newbl)
118 0 : return NULL;
119 : assert(!b->ab_next);
120 283 : b->ab_next = newbl;
121 283 : b = newbl;
122 : }
123 :
124 : assert(b->ab_offset + size <= b->ab_size);
125 57570 : p = (void *)(((char *)b->ab_mem) + b->ab_offset);
126 57570 : b->ab_offset += size;
127 57570 : return p;
128 : }
129 :
130 : PyArena *
131 63 : PyArena_New()
132 : {
133 63 : PyArena* arena = (PyArena *)malloc(sizeof(PyArena));
134 63 : if (!arena)
135 0 : return (PyArena*)PyErr_NoMemory();
136 :
137 63 : arena->a_head = block_new(DEFAULT_BLOCK_SIZE);
138 63 : arena->a_cur = arena->a_head;
139 63 : if (!arena->a_head) {
140 0 : free((void *)arena);
141 0 : return (PyArena*)PyErr_NoMemory();
142 : }
143 63 : arena->a_objects = PyList_New(0);
144 63 : if (!arena->a_objects) {
145 0 : block_free(arena->a_head);
146 0 : free((void *)arena);
147 0 : 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 63 : return arena;
157 : }
158 :
159 : void
160 63 : 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 63 : 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 63 : Py_DECREF(arena->a_objects);
179 63 : free(arena);
180 63 : }
181 :
182 : void *
183 57570 : PyArena_Malloc(PyArena *arena, size_t size)
184 : {
185 57570 : void *p = block_alloc(arena->a_cur, size);
186 57570 : if (!p)
187 0 : 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 57570 : if (arena->a_cur->ab_next) {
194 283 : 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 57570 : return p;
203 : }
204 :
205 : int
206 26680 : PyArena_AddPyObject(PyArena *arena, PyObject *obj)
207 : {
208 26680 : int r = PyList_Append(arena->a_objects, obj);
209 26680 : if (r >= 0) {
210 26680 : Py_DECREF(obj);
211 : }
212 26680 : return r;
213 : }
|