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 }