blob: aefb787e554f9661f2df538ac70070ceeaad55c8 [file] [log] [blame]
Neal Norwitzadb69fc2005-12-17 20:54:49 +00001#include "Python.h"
Neal Norwitzadb69fc2005-12-17 20:54:49 +00002
Tim Petersf6386302006-03-02 21:41:18 +00003/* A simple arena block structure.
Jeremy Hylton56820c22006-02-28 19:57:06 +00004
5 Measurements with standard library modules suggest the average
6 allocation is about 20 bytes and that most compiles use a single
7 block.
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00008
9 TODO(jhylton): Think about a realloc API, maybe just for the last
10 allocation?
Jeremy Hylton56820c22006-02-28 19:57:06 +000011*/
Neal Norwitzadb69fc2005-12-17 20:54:49 +000012
Jeremy Hylton77f1bb22006-02-28 17:53:04 +000013#define DEFAULT_BLOCK_SIZE 8192
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000014#define ALIGNMENT 8
Thomas Wouters49fd7fa2006-04-21 10:40:58 +000015
Jeremy Hylton77f1bb22006-02-28 17:53:04 +000016typedef struct _block {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000017 /* 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;
Tim Petersf6386302006-03-02 21:41:18 +000022
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000023 /* 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;
Tim Petersf6386302006-03-02 21:41:18 +000027
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000028 /* 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;
Tim Petersf6386302006-03-02 21:41:18 +000033
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000034 /* Pointer to the first allocatable byte owned by this block. Read-
35 * only after initialization.
36 */
37 void *ab_mem;
Jeremy Hylton77f1bb22006-02-28 17:53:04 +000038} block;
Neal Norwitzadb69fc2005-12-17 20:54:49 +000039
Jeremy Hylton99b4ee62006-02-28 18:52:28 +000040/* 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*/
Tim Peters8cfaa0e2006-03-02 20:37:32 +000044
Neal Norwitzadb69fc2005-12-17 20:54:49 +000045struct _arena {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000046 /* 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;
Thomas Wouters49fd7fa2006-04-21 10:40:58 +000051
Quan Tian3bd0d622018-10-20 05:30:03 +080052 /* Pointer to the block currently used for allocation. Its
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000053 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;
Thomas Wouters49fd7fa2006-04-21 10:40:58 +000058
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000059 /* A Python list object containing references to all the PyObject
Quan Tian3bd0d622018-10-20 05:30:03 +080060 pointers associated with this arena. They will be DECREFed
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000061 when the arena is freed.
62 */
63 PyObject *a_objects;
Thomas Wouters49fd7fa2006-04-21 10:40:58 +000064
Jeremy Hylton56820c22006-02-28 19:57:06 +000065#if defined(Py_DEBUG)
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000066 /* 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;
Jeremy Hylton56820c22006-02-28 19:57:06 +000072#endif
Neal Norwitzadb69fc2005-12-17 20:54:49 +000073};
74
Jeremy Hylton77f1bb22006-02-28 17:53:04 +000075static block *
76block_new(size_t size)
77{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000078 /* Allocate header and block as one unit.
79 ab_mem points just past header. */
Victor Stinnerc6632e72013-07-07 17:18:53 +020080 block *b = (block *)PyMem_Malloc(sizeof(block) + size);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000081 if (!b)
82 return NULL;
83 b->ab_size = size;
84 b->ab_mem = (void *)(b + 1);
85 b->ab_next = NULL;
Antoine Pitrouca8aa4a2012-09-20 20:56:47 +020086 b->ab_offset = (char *)_Py_ALIGN_UP(b->ab_mem, ALIGNMENT) -
87 (char *)(b->ab_mem);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000088 return b;
Neal Norwitzadb69fc2005-12-17 20:54:49 +000089}
90
91static void
Jeremy Hylton77f1bb22006-02-28 17:53:04 +000092block_free(block *b) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000093 while (b) {
94 block *next = b->ab_next;
Victor Stinnerc6632e72013-07-07 17:18:53 +020095 PyMem_Free(b);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000096 b = next;
97 }
Neal Norwitzadb69fc2005-12-17 20:54:49 +000098}
99
Jeremy Hylton77f1bb22006-02-28 17:53:04 +0000100static void *
101block_alloc(block *b, size_t size)
102{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000103 void *p;
104 assert(b);
Antoine Pitrouca8aa4a2012-09-20 20:56:47 +0200105 size = _Py_SIZE_ROUND_UP(size, ALIGNMENT);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000106 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 }
Jeremy Hylton77f1bb22006-02-28 17:53:04 +0000120
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000121 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;
Jeremy Hylton77f1bb22006-02-28 17:53:04 +0000125}
Neal Norwitzadb69fc2005-12-17 20:54:49 +0000126
127PyArena *
128PyArena_New()
129{
Victor Stinnerc6632e72013-07-07 17:18:53 +0200130 PyArena* arena = (PyArena *)PyMem_Malloc(sizeof(PyArena));
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000131 if (!arena)
132 return (PyArena*)PyErr_NoMemory();
Neal Norwitzadb69fc2005-12-17 20:54:49 +0000133
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000134 arena->a_head = block_new(DEFAULT_BLOCK_SIZE);
135 arena->a_cur = arena->a_head;
136 if (!arena->a_head) {
Victor Stinnerc6632e72013-07-07 17:18:53 +0200137 PyMem_Free((void *)arena);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000138 return (PyArena*)PyErr_NoMemory();
139 }
140 arena->a_objects = PyList_New(0);
141 if (!arena->a_objects) {
142 block_free(arena->a_head);
Victor Stinnerc6632e72013-07-07 17:18:53 +0200143 PyMem_Free((void *)arena);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000144 return (PyArena*)PyErr_NoMemory();
145 }
Jeremy Hylton56820c22006-02-28 19:57:06 +0000146#if defined(Py_DEBUG)
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000147 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;
Jeremy Hylton56820c22006-02-28 19:57:06 +0000152#endif
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000153 return arena;
Neal Norwitzadb69fc2005-12-17 20:54:49 +0000154}
155
156void
157PyArena_Free(PyArena *arena)
158{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000159 assert(arena);
Jeremy Hylton56820c22006-02-28 19:57:06 +0000160#if defined(Py_DEBUG)
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000161 /*
162 fprintf(stderr,
Serhiy Storchakad53fe5f2019-03-13 22:59:55 +0200163 "alloc=%zu size=%zu blocks=%zu block_size=%zu big=%zu objects=%zu\n",
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000164 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 */
Jeremy Hylton56820c22006-02-28 19:57:06 +0000168#endif
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000169 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 */
Thomas Wouters49fd7fa2006-04-21 10:40:58 +0000174
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000175 Py_DECREF(arena->a_objects);
Victor Stinnerc6632e72013-07-07 17:18:53 +0200176 PyMem_Free(arena);
Neal Norwitzadb69fc2005-12-17 20:54:49 +0000177}
178
179void *
Tim Peters8cfaa0e2006-03-02 20:37:32 +0000180PyArena_Malloc(PyArena *arena, size_t size)
Neal Norwitzadb69fc2005-12-17 20:54:49 +0000181{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000182 void *p = block_alloc(arena->a_cur, size);
183 if (!p)
184 return PyErr_NoMemory();
Jeremy Hylton56820c22006-02-28 19:57:06 +0000185#if defined(Py_DEBUG)
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000186 arena->total_allocs++;
187 arena->total_size += size;
Jeremy Hylton56820c22006-02-28 19:57:06 +0000188#endif
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000189 /* Reset cur if we allocated a new block. */
190 if (arena->a_cur->ab_next) {
191 arena->a_cur = arena->a_cur->ab_next;
Jeremy Hylton56820c22006-02-28 19:57:06 +0000192#if defined(Py_DEBUG)
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000193 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;
Jeremy Hylton56820c22006-02-28 19:57:06 +0000197#endif
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000198 }
199 return p;
Neal Norwitzadb69fc2005-12-17 20:54:49 +0000200}
201
202int
Tim Peters8cfaa0e2006-03-02 20:37:32 +0000203PyArena_AddPyObject(PyArena *arena, PyObject *obj)
Neal Norwitzadb69fc2005-12-17 20:54:49 +0000204{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000205 int r = PyList_Append(arena->a_objects, obj);
206 if (r >= 0) {
207 Py_DECREF(obj);
208 }
209 return r;
Neal Norwitzadb69fc2005-12-17 20:54:49 +0000210}