Line data Source code
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 : #define ALIGNMENT_MASK (ALIGNMENT - 1)
16 : #define ROUNDUP(x) (((x) + ALIGNMENT_MASK) & ~ALIGNMENT_MASK)
17 :
18 : typedef struct _block {
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;
24 :
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;
29 :
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;
35 :
36 : /* Pointer to the first allocatable byte owned by this block. Read-
37 : * only after initialization.
38 : */
39 : void *ab_mem;
40 : } block;
41 :
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 : */
46 :
47 : struct _arena {
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;
53 :
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;
60 :
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;
66 :
67 : #if defined(Py_DEBUG)
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;
74 : #endif
75 : };
76 :
77 : static block *
78 5 : block_new(size_t size)
79 : {
80 : /* Allocate header and block as one unit.
81 : ab_mem points just past header. */
82 5 : block *b = (block *)malloc(sizeof(block) + size);
83 5 : if (!b)
84 0 : return NULL;
85 5 : b->ab_size = size;
86 5 : b->ab_mem = (void *)(b + 1);
87 5 : b->ab_next = NULL;
88 10 : b->ab_offset = ROUNDUP((Py_uintptr_t)(b->ab_mem)) -
89 5 : (Py_uintptr_t)(b->ab_mem);
90 5 : return b;
91 : }
92 :
93 : static void
94 3 : block_free(block *b) {
95 11 : while (b) {
96 5 : block *next = b->ab_next;
97 5 : free(b);
98 5 : b = next;
99 : }
100 3 : }
101 :
102 : static void *
103 1420 : block_alloc(block *b, size_t size)
104 : {
105 : void *p;
106 : assert(b);
107 1420 : size = ROUNDUP(size);
108 1420 : 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 2 : block *newbl = block_new(
114 : size < DEFAULT_BLOCK_SIZE ?
115 : DEFAULT_BLOCK_SIZE : size);
116 2 : if (!newbl)
117 0 : return NULL;
118 : assert(!b->ab_next);
119 2 : b->ab_next = newbl;
120 2 : b = newbl;
121 : }
122 :
123 : assert(b->ab_offset + size <= b->ab_size);
124 1420 : p = (void *)(((char *)b->ab_mem) + b->ab_offset);
125 1420 : b->ab_offset += size;
126 1420 : return p;
127 : }
128 :
129 : PyArena *
130 3 : PyArena_New()
131 : {
132 3 : PyArena* arena = (PyArena *)malloc(sizeof(PyArena));
133 3 : if (!arena)
134 0 : return (PyArena*)PyErr_NoMemory();
135 :
136 3 : arena->a_head = block_new(DEFAULT_BLOCK_SIZE);
137 3 : arena->a_cur = arena->a_head;
138 3 : if (!arena->a_head) {
139 0 : free((void *)arena);
140 0 : return (PyArena*)PyErr_NoMemory();
141 : }
142 3 : arena->a_objects = PyList_New(0);
143 3 : if (!arena->a_objects) {
144 0 : block_free(arena->a_head);
145 0 : free((void *)arena);
146 0 : return (PyArena*)PyErr_NoMemory();
147 : }
148 : #if defined(Py_DEBUG)
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;
154 : #endif
155 3 : return arena;
156 : }
157 :
158 : void
159 3 : PyArena_Free(PyArena *arena)
160 : {
161 : int r;
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 3 : 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 : /* Clear all the elements from the list. This is necessary
179 : to guarantee that they will be DECREFed. */
180 3 : r = PyList_SetSlice(arena->a_objects,
181 3 : 0, PyList_GET_SIZE(arena->a_objects), NULL);
182 : assert(r == 0);
183 : assert(PyList_GET_SIZE(arena->a_objects) == 0);
184 3 : Py_DECREF(arena->a_objects);
185 3 : free(arena);
186 3 : }
187 :
188 : void *
189 1420 : PyArena_Malloc(PyArena *arena, size_t size)
190 : {
191 1420 : void *p = block_alloc(arena->a_cur, size);
192 1420 : if (!p)
193 0 : return PyErr_NoMemory();
194 : #if defined(Py_DEBUG)
195 : arena->total_allocs++;
196 : arena->total_size += size;
197 : #endif
198 : /* Reset cur if we allocated a new block. */
199 1420 : if (arena->a_cur->ab_next) {
200 2 : arena->a_cur = arena->a_cur->ab_next;
201 : #if defined(Py_DEBUG)
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;
206 : #endif
207 : }
208 1420 : return p;
209 : }
210 :
211 : int
212 662 : PyArena_AddPyObject(PyArena *arena, PyObject *obj)
213 : {
214 662 : int r = PyList_Append(arena->a_objects, obj);
215 662 : if (r >= 0) {
216 662 : Py_DECREF(obj);
217 : }
218 662 : return r;
219 : }
|
