← Back to branch summary

~ubuntu-branches/ubuntu/maverick/python3.1/maverick

« back to all changes in this revision

Viewing changes to Python/pyarena.c

  • Committer: Bazaar Package Importer
  • Author(s): Matthias Klose
  • Date: 2009-03-23 00:01:27 UTC
  • Revision ID: james.westby@ubuntu.com-20090323000127-5fstfxju4ufrhthq
Tags: upstream-3.1~a1+20090322
Import upstream version 3.1~a1+20090322

Show diffs side-by-side

added added

removed removed

Lines of Context:
Python/pyarena.c
 
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
block_new(size_t size)
 
80
{
 
81
        /* Allocate header and block as one unit.
 
82
           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;
 
89
        b->ab_offset = ROUNDUP((Py_uintptr_t)(b->ab_mem)) - 
 
90
          (Py_uintptr_t)(b->ab_mem);
 
91
        return b;
 
92
}
 
93
 
 
94
static void
 
95
block_free(block *b) {
 
96
        while (b) {
 
97
                block *next = b->ab_next;
 
98
                free(b);
 
99
                b = next;
 
100
        }
 
101
}
 
102
 
 
103
static void *
 
104
block_alloc(block *b, size_t size)
 
105
{
 
106
        void *p;
 
107
        assert(b);
 
108
        size = ROUNDUP(size);
 
109
        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
                block *newbl = block_new(
 
115
                                size < DEFAULT_BLOCK_SIZE ?
 
116
                                DEFAULT_BLOCK_SIZE : size);
 
117
                if (!newbl)
 
118
                        return NULL;
 
119
                assert(!b->ab_next);
 
120
                b->ab_next = newbl;
 
121
                b = newbl;
 
122
        }
 
123
 
 
124
        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;
 
128
}
 
129
 
 
130
PyArena *
 
131
PyArena_New()
 
132
{
 
133
        PyArena* arena = (PyArena *)malloc(sizeof(PyArena));
 
134
        if (!arena)
 
135
                return (PyArena*)PyErr_NoMemory();
 
136
 
 
137
        arena->a_head = block_new(DEFAULT_BLOCK_SIZE);
 
138
        arena->a_cur = arena->a_head;
 
139
        if (!arena->a_head) {
 
140
                free((void *)arena);
 
141
                return (PyArena*)PyErr_NoMemory();
 
142
        }
 
143
        arena->a_objects = PyList_New(0);
 
144
        if (!arena->a_objects) {
 
145
                block_free(arena->a_head);
 
146
                free((void *)arena);
 
147
                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
        return arena;
 
157
}
 
158
 
 
159
void
 
160
PyArena_Free(PyArena *arena)
 
161
{
 
162
        int r;
 
163
        assert(arena);
 
164
#if defined(Py_DEBUG)
 
165
        /*
 
166
        fprintf(stderr,
 
167
                "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
 
173
        block_free(arena->a_head);
 
174
        /* This property normally holds, except when the code being compiled
 
175
           is sys.getobjects(0), in which case there will be two references.
 
176
        assert(arena->a_objects->ob_refcnt == 1);
 
177
        */
 
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);
 
185
        Py_DECREF(arena->a_objects);
 
186
        free(arena);
 
187
}
 
188
 
 
189
void *
 
190
PyArena_Malloc(PyArena *arena, size_t size)
 
191
{
 
192
        void *p = block_alloc(arena->a_cur, size);
 
193
        if (!p)
 
194
                return PyErr_NoMemory();
 
195
#if defined(Py_DEBUG)
 
196
        arena->total_allocs++;
 
197
        arena->total_size += size;
 
198
#endif
 
199
        /* Reset cur if we allocated a new block. */
 
200
        if (arena->a_cur->ab_next) {
 
201
                arena->a_cur = arena->a_cur->ab_next;
 
202
#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)
 
206
                        ++arena->total_big_blocks;
 
207
#endif
 
208
        }
 
209
        return p;
 
210
}
 
211
 
 
212
int
 
213
PyArena_AddPyObject(PyArena *arena, PyObject *obj)
 
214
{
 
215
        int r = PyList_Append(arena->a_objects, obj);
 
216
        if (r >= 0) {
 
217
                Py_DECREF(obj);
 
218
        }
 
219
        return r;
 
220
}