AppPkg/Applications/Python/Python-2.7.10/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     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     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     Py_DECREF(arena->a_objects);
 179     free(arena);
 180 }
 181
 182 void *
 183 PyArena_Malloc(PyArena *arena, size_t size)
 184 {
 185     void *p = block_alloc(arena->a_cur, size);
 186     if (!p)
 187         return PyErr_NoMemory();
 188 #if defined(Py_DEBUG)
 189     arena->total_allocs++;
 190     arena->total_size += size;
 191 #endif
 192     /* Reset cur if we allocated a new block. */
 193     if (arena->a_cur->ab_next) {
 194         arena->a_cur = arena->a_cur->ab_next;
 195 #if defined(Py_DEBUG)
 196         arena->total_blocks++;
 197         arena->total_block_size += arena->a_cur->ab_size;
 198         if (arena->a_cur->ab_size > DEFAULT_BLOCK_SIZE)
 199             ++arena->total_big_blocks;
 200 #endif
 201     }
 202     return p;
 203 }
 204
 205 int
 206 PyArena_AddPyObject(PyArena *arena, PyObject *obj)
 207 {
 208     int r = PyList_Append(arena->a_objects, obj);
 209     if (r >= 0) {
 210         Py_DECREF(obj);
 211     }
 212     return r;
 213 }