blob: f4cc474f412166e7625fd5fba683bcfb63b2ad72 [file] [log] [blame]
Neal Norwitzadb69fc2005-12-17 20:54:49 +00001#include "Python.h"
2#include "pyarena.h"
3
Tim Petersf6386302006-03-02 21:41:18 +00004/* A simple arena block structure.
Jeremy Hylton56820c22006-02-28 19:57:06 +00005
6 Measurements with standard library modules suggest the average
7 allocation is about 20 bytes and that most compiles use a single
8 block.
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00009
10 TODO(jhylton): Think about a realloc API, maybe just for the last
11 allocation?
Jeremy Hylton56820c22006-02-28 19:57:06 +000012*/
Neal Norwitzadb69fc2005-12-17 20:54:49 +000013
Jeremy Hylton77f1bb22006-02-28 17:53:04 +000014#define DEFAULT_BLOCK_SIZE 8192
Thomas Wouters49fd7fa2006-04-21 10:40:58 +000015#define ALIGNMENT 8
16#define ALIGNMENT_MASK (ALIGNMENT - 1)
17#define ROUNDUP(x) (((x) + ALIGNMENT_MASK) & ~ALIGNMENT_MASK)
18
Jeremy Hylton77f1bb22006-02-28 17:53:04 +000019typedef struct _block {
Tim Petersf6386302006-03-02 21:41:18 +000020 /* 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 */
Jeremy Hylton08533fd2006-02-28 18:29:00 +000024 size_t ab_size;
Tim Petersf6386302006-03-02 21:41:18 +000025
26 /* Total number of bytes already passed out. The next byte available
27 * to pass out starts at ab_mem + ab_offset.
28 */
Jeremy Hylton08533fd2006-02-28 18:29:00 +000029 size_t ab_offset;
Tim Petersf6386302006-03-02 21:41:18 +000030
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 */
Jeremy Hylton08533fd2006-02-28 18:29:00 +000035 struct _block *ab_next;
Tim Petersf6386302006-03-02 21:41:18 +000036
37 /* Pointer to the first allocatable byte owned by this block. Read-
38 * only after initialization.
39 */
Jeremy Hylton08533fd2006-02-28 18:29:00 +000040 void *ab_mem;
Jeremy Hylton77f1bb22006-02-28 17:53:04 +000041} block;
Neal Norwitzadb69fc2005-12-17 20:54:49 +000042
Jeremy Hylton99b4ee62006-02-28 18:52:28 +000043/* 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*/
Tim Peters8cfaa0e2006-03-02 20:37:32 +000047
Neal Norwitzadb69fc2005-12-17 20:54:49 +000048struct _arena {
Thomas Wouters49fd7fa2006-04-21 10:40:58 +000049 /* 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 */
Jeremy Hylton08533fd2006-02-28 18:29:00 +000053 block *a_head;
Thomas Wouters49fd7fa2006-04-21 10:40:58 +000054
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 */
Jeremy Hylton08533fd2006-02-28 18:29:00 +000060 block *a_cur;
Thomas Wouters49fd7fa2006-04-21 10:40:58 +000061
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 */
Jeremy Hylton99b4ee62006-02-28 18:52:28 +000066 PyObject *a_objects;
Thomas Wouters49fd7fa2006-04-21 10:40:58 +000067
Jeremy Hylton56820c22006-02-28 19:57:06 +000068#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
Neal Norwitzadb69fc2005-12-17 20:54:49 +000076};
77
Jeremy Hylton77f1bb22006-02-28 17:53:04 +000078static block *
79block_new(size_t size)
80{
Tim Peters8cfaa0e2006-03-02 20:37:32 +000081 /* Allocate header and block as one unit.
Jeremy Hylton08533fd2006-02-28 18:29:00 +000082 ab_mem points just past header. */
83 block *b = (block *)malloc(sizeof(block) + size);
84 if (!b)
85 return NULL;
86 b->ab_size = size;
87 b->ab_mem = (void *)(b + 1);
88 b->ab_next = NULL;
Thomas Wouters49fd7fa2006-04-21 10:40:58 +000089 b->ab_offset = ROUNDUP((Py_uintptr_t)(b->ab_mem)) -
90 (Py_uintptr_t)(b->ab_mem);
Jeremy Hylton08533fd2006-02-28 18:29:00 +000091 return b;
Neal Norwitzadb69fc2005-12-17 20:54:49 +000092}
93
94static void
Jeremy Hylton77f1bb22006-02-28 17:53:04 +000095block_free(block *b) {
Jeremy Hylton08533fd2006-02-28 18:29:00 +000096 while (b) {
97 block *next = b->ab_next;
98 free(b);
99 b = next;
100 }
Neal Norwitzadb69fc2005-12-17 20:54:49 +0000101}
102
Jeremy Hylton77f1bb22006-02-28 17:53:04 +0000103static void *
104block_alloc(block *b, size_t size)
105{
Jeremy Hylton08533fd2006-02-28 18:29:00 +0000106 void *p;
107 assert(b);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +0000108 size = ROUNDUP(size);
Jeremy Hylton08533fd2006-02-28 18:29:00 +0000109 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 */
Thomas Wouters49fd7fa2006-04-21 10:40:58 +0000114 block *newbl = block_new(
Jeremy Hylton08533fd2006-02-28 18:29:00 +0000115 size < DEFAULT_BLOCK_SIZE ?
116 DEFAULT_BLOCK_SIZE : size);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +0000117 if (!newbl)
Jeremy Hylton08533fd2006-02-28 18:29:00 +0000118 return NULL;
119 assert(!b->ab_next);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +0000120 b->ab_next = newbl;
121 b = newbl;
Jeremy Hylton08533fd2006-02-28 18:29:00 +0000122 }
Jeremy Hylton77f1bb22006-02-28 17:53:04 +0000123
Jeremy Hylton08533fd2006-02-28 18:29:00 +0000124 assert(b->ab_offset + size <= b->ab_size);
125 p = (void *)(((char *)b->ab_mem) + b->ab_offset);
126 b->ab_offset += size;
127 return p;
Jeremy Hylton77f1bb22006-02-28 17:53:04 +0000128}
Neal Norwitzadb69fc2005-12-17 20:54:49 +0000129
130PyArena *
131PyArena_New()
132{
Jeremy Hylton08533fd2006-02-28 18:29:00 +0000133 PyArena* arena = (PyArena *)malloc(sizeof(PyArena));
134 if (!arena)
Thomas Wouters0e3f5912006-08-11 14:57:12 +0000135 return (PyArena*)PyErr_NoMemory();
Neal Norwitzadb69fc2005-12-17 20:54:49 +0000136
Jeremy Hylton08533fd2006-02-28 18:29:00 +0000137 arena->a_head = block_new(DEFAULT_BLOCK_SIZE);
138 arena->a_cur = arena->a_head;
Jeremy Hylton99b4ee62006-02-28 18:52:28 +0000139 if (!arena->a_head) {
140 free((void *)arena);
Thomas Wouters0e3f5912006-08-11 14:57:12 +0000141 return (PyArena*)PyErr_NoMemory();
Jeremy Hylton99b4ee62006-02-28 18:52:28 +0000142 }
Jeremy Hylton56820c22006-02-28 19:57:06 +0000143 arena->a_objects = PyList_New(0);
Jeremy Hylton99b4ee62006-02-28 18:52:28 +0000144 if (!arena->a_objects) {
145 block_free(arena->a_head);
146 free((void *)arena);
Thomas Wouters0e3f5912006-08-11 14:57:12 +0000147 return (PyArena*)PyErr_NoMemory();
Jeremy Hylton99b4ee62006-02-28 18:52:28 +0000148 }
Jeremy Hylton56820c22006-02-28 19:57:06 +0000149#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
Jeremy Hylton08533fd2006-02-28 18:29:00 +0000156 return arena;
Neal Norwitzadb69fc2005-12-17 20:54:49 +0000157}
158
159void
160PyArena_Free(PyArena *arena)
161{
Thomas Wouters49fd7fa2006-04-21 10:40:58 +0000162 int r;
Jeremy Hylton08533fd2006-02-28 18:29:00 +0000163 assert(arena);
Jeremy Hylton56820c22006-02-28 19:57:06 +0000164#if defined(Py_DEBUG)
165 /*
Tim Peters8cfaa0e2006-03-02 20:37:32 +0000166 fprintf(stderr,
Jeremy Hylton56820c22006-02-28 19:57:06 +0000167 "alloc=%d size=%d blocks=%d block_size=%d big=%d objects=%d\n",
168 arena->total_allocs, arena->total_size, arena->total_blocks,
169 arena->total_block_size, arena->total_big_blocks,
170 PyList_Size(arena->a_objects));
171 */
172#endif
Jeremy Hylton08533fd2006-02-28 18:29:00 +0000173 block_free(arena->a_head);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +0000174 /* This property normally holds, except when the code being compiled
175 is sys.getobjects(0), in which case there will be two references.
Jeremy Hylton99b4ee62006-02-28 18:52:28 +0000176 assert(arena->a_objects->ob_refcnt == 1);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +0000177 */
178
179 /* Clear all the elements from the list. This is necessary
180 to guarantee that they will be DECREFed. */
181 r = PyList_SetSlice(arena->a_objects,
182 0, PyList_GET_SIZE(arena->a_objects), NULL);
183 assert(r == 0);
184 assert(PyList_GET_SIZE(arena->a_objects) == 0);
Jeremy Hylton99b4ee62006-02-28 18:52:28 +0000185 Py_DECREF(arena->a_objects);
Jeremy Hylton08533fd2006-02-28 18:29:00 +0000186 free(arena);
Neal Norwitzadb69fc2005-12-17 20:54:49 +0000187}
188
189void *
Tim Peters8cfaa0e2006-03-02 20:37:32 +0000190PyArena_Malloc(PyArena *arena, size_t size)
Neal Norwitzadb69fc2005-12-17 20:54:49 +0000191{
Jeremy Hylton08533fd2006-02-28 18:29:00 +0000192 void *p = block_alloc(arena->a_cur, size);
193 if (!p)
Thomas Wouters0e3f5912006-08-11 14:57:12 +0000194 return PyErr_NoMemory();
Jeremy Hylton56820c22006-02-28 19:57:06 +0000195#if defined(Py_DEBUG)
196 arena->total_allocs++;
197 arena->total_size += size;
198#endif
Jeremy Hylton08533fd2006-02-28 18:29:00 +0000199 /* Reset cur if we allocated a new block. */
200 if (arena->a_cur->ab_next) {
201 arena->a_cur = arena->a_cur->ab_next;
Jeremy Hylton56820c22006-02-28 19:57:06 +0000202#if defined(Py_DEBUG)
203 arena->total_blocks++;
204 arena->total_block_size += arena->a_cur->ab_size;
205 if (arena->a_cur->ab_size > DEFAULT_BLOCK_SIZE)
Tim Peters6fd92dc2006-03-02 21:14:45 +0000206 ++arena->total_big_blocks;
Jeremy Hylton56820c22006-02-28 19:57:06 +0000207#endif
Jeremy Hylton08533fd2006-02-28 18:29:00 +0000208 }
209 return p;
Neal Norwitzadb69fc2005-12-17 20:54:49 +0000210}
211
212int
Tim Peters8cfaa0e2006-03-02 20:37:32 +0000213PyArena_AddPyObject(PyArena *arena, PyObject *obj)
Neal Norwitzadb69fc2005-12-17 20:54:49 +0000214{
Jeremy Hylton224003b2006-03-01 15:02:24 +0000215 int r = PyList_Append(arena->a_objects, obj);
216 if (r >= 0) {
217 Py_DECREF(obj);
218 }
219 return r;
Neal Norwitzadb69fc2005-12-17 20:54:49 +0000220}