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 NULL;
 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 NULL;
 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 NULL;
 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 NULL;
 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 }