Line data    Source code

       1             : #include "Python.h"
       2             : #include "pycore_pyarena.h"       // PyArena
       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             : 
      17             : typedef struct _block {
      18             :     /* Total number of bytes owned by this block available to pass out.
      19             :      * Read-only after initialization.  The first such byte starts at
      20             :      * ab_mem.
      21             :      */
      22             :     size_t ab_size;
      23             : 
      24             :     /* Total number of bytes already passed out.  The next byte available
      25             :      * to pass out starts at ab_mem + ab_offset.
      26             :      */
      27             :     size_t ab_offset;
      28             : 
      29             :     /* An arena maintains a singly-linked, NULL-terminated list of
      30             :      * all blocks owned by the arena.  These are linked via the
      31             :      * ab_next member.
      32             :      */
      33             :     struct _block *ab_next;
      34             : 
      35             :     /* Pointer to the first allocatable byte owned by this block.  Read-
      36             :      * only after initialization.
      37             :      */
      38             :     void *ab_mem;
      39             : } block;
      40             : 
      41             : /* The arena manages two kinds of memory, blocks of raw memory
      42             :    and a list of PyObject* pointers.  PyObjects are decrefed
      43             :    when the arena is freed.
      44             : */
      45             : 
      46             : struct _arena {
      47             :     /* Pointer to the first block allocated for the arena, never NULL.
      48             :        It is used only to find the first block when the arena is
      49             :        being freed.
      50             :      */
      51             :     block *a_head;
      52             : 
      53             :     /* Pointer to the block currently used for allocation.  Its
      54             :        ab_next field should be NULL.  If it is not-null after a
      55             :        call to block_alloc(), it means a new block has been allocated
      56             :        and a_cur should be reset to point it.
      57             :      */
      58             :     block *a_cur;
      59             : 
      60             :     /* A Python list object containing references to all the PyObject
      61             :        pointers associated with this arena.  They will be DECREFed
      62             :        when the arena is freed.
      63             :     */
      64             :     PyObject *a_objects;
      65             : 
      66             : #if defined(Py_DEBUG)
      67             :     /* Debug output */
      68             :     size_t total_allocs;
      69             :     size_t total_size;
      70             :     size_t total_blocks;
      71             :     size_t total_block_size;
      72             :     size_t total_big_blocks;
      73             : #endif
      74             : };
      75             : 
      76             : static block *
      77     1316240 : block_new(size_t size)
      78             : {
      79             :     /* Allocate header and block as one unit.
      80             :        ab_mem points just past header. */
      81     1316240 :     block *b = (block *)PyMem_Malloc(sizeof(block) + size);
      82     1316240 :     if (!b)
      83           0 :         return NULL;
      84     1316240 :     b->ab_size = size;
      85     1316240 :     b->ab_mem = (void *)(b + 1);
      86     1316240 :     b->ab_next = NULL;
      87     1316240 :     b->ab_offset = (char *)_Py_ALIGN_UP(b->ab_mem, ALIGNMENT) -
      88     1316240 :             (char *)(b->ab_mem);
      89     1316240 :     return b;
      90             : }
      91             : 
      92             : static void
      93      128549 : block_free(block *b) {
      94     1444780 :     while (b) {
      95     1316230 :         block *next = b->ab_next;
      96     1316230 :         PyMem_Free(b);
      97     1316230 :         b = next;
      98             :     }
      99      128549 : }
     100             : 
     101             : static void *
     102   283191000 : block_alloc(block *b, size_t size)
     103             : {
     104             :     void *p;
     105   283191000 :     assert(b);
     106   283191000 :     size = _Py_SIZE_ROUND_UP(size, ALIGNMENT);
     107   283191000 :     if (b->ab_offset + size > b->ab_size) {
     108             :         /* If we need to allocate more memory than will fit in
     109             :            the default block, allocate a one-off block that is
     110             :            exactly the right size. */
     111             :         /* TODO(jhylton): Think about space waste at end of block */
     112     1187690 :         block *newbl = block_new(
     113             :                         size < DEFAULT_BLOCK_SIZE ?
     114             :                         DEFAULT_BLOCK_SIZE : size);
     115     1187690 :         if (!newbl)
     116           0 :             return NULL;
     117     1187690 :         assert(!b->ab_next);
     118     1187690 :         b->ab_next = newbl;
     119     1187690 :         b = newbl;
     120             :     }
     121             : 
     122   283191000 :     assert(b->ab_offset + size <= b->ab_size);
     123   283191000 :     p = (void *)(((char *)b->ab_mem) + b->ab_offset);
     124   283191000 :     b->ab_offset += size;
     125   283191000 :     return p;
     126             : }
     127             : 
     128             : PyArena *
     129      128568 : _PyArena_New(void)
     130             : {
     131      128568 :     PyArena* arena = (PyArena *)PyMem_Malloc(sizeof(PyArena));
     132      128568 :     if (!arena)
     133          17 :         return (PyArena*)PyErr_NoMemory();
     134             : 
     135      128551 :     arena->a_head = block_new(DEFAULT_BLOCK_SIZE);
     136      128551 :     arena->a_cur = arena->a_head;
     137      128551 :     if (!arena->a_head) {
     138           0 :         PyMem_Free((void *)arena);
     139           0 :         return (PyArena*)PyErr_NoMemory();
     140             :     }
     141      128551 :     arena->a_objects = PyList_New(0);
     142      128551 :     if (!arena->a_objects) {
     143           0 :         block_free(arena->a_head);
     144           0 :         PyMem_Free((void *)arena);
     145           0 :         return (PyArena*)PyErr_NoMemory();
     146             :     }
     147             : #if defined(Py_DEBUG)
     148      128551 :     arena->total_allocs = 0;
     149      128551 :     arena->total_size = 0;
     150      128551 :     arena->total_blocks = 1;
     151      128551 :     arena->total_block_size = DEFAULT_BLOCK_SIZE;
     152      128551 :     arena->total_big_blocks = 0;
     153             : #endif
     154      128551 :     return arena;
     155             : }
     156             : 
     157             : void
     158      128549 : _PyArena_Free(PyArena *arena)
     159             : {
     160      128549 :     assert(arena);
     161             : #if defined(Py_DEBUG)
     162             :     /*
     163             :     fprintf(stderr,
     164             :         "alloc=%zu size=%zu blocks=%zu block_size=%zu big=%zu objects=%zu\n",
     165             :         arena->total_allocs, arena->total_size, arena->total_blocks,
     166             :         arena->total_block_size, arena->total_big_blocks,
     167             :         PyList_Size(arena->a_objects));
     168             :     */
     169             : #endif
     170      128549 :     block_free(arena->a_head);
     171             :     /* This property normally holds, except when the code being compiled
     172             :        is sys.getobjects(0), in which case there will be two references.
     173             :     assert(arena->a_objects->ob_refcnt == 1);
     174             :     */
     175             : 
     176      128549 :     Py_DECREF(arena->a_objects);
     177      128549 :     PyMem_Free(arena);
     178      128549 : }
     179             : 
     180             : void *
     181   283191000 : _PyArena_Malloc(PyArena *arena, size_t size)
     182             : {
     183   283191000 :     void *p = block_alloc(arena->a_cur, size);
     184   283191000 :     if (!p)
     185           0 :         return PyErr_NoMemory();
     186             : #if defined(Py_DEBUG)
     187   283191000 :     arena->total_allocs++;
     188   283191000 :     arena->total_size += size;
     189             : #endif
     190             :     /* Reset cur if we allocated a new block. */
     191   283191000 :     if (arena->a_cur->ab_next) {
     192     1187690 :         arena->a_cur = arena->a_cur->ab_next;
     193             : #if defined(Py_DEBUG)
     194     1187690 :         arena->total_blocks++;
     195     1187690 :         arena->total_block_size += arena->a_cur->ab_size;
     196     1187690 :         if (arena->a_cur->ab_size > DEFAULT_BLOCK_SIZE)
     197        1025 :             ++arena->total_big_blocks;
     198             : #endif
     199             :     }
     200   283191000 :     return p;
     201             : }
     202             : 
     203             : int
     204    81669700 : _PyArena_AddPyObject(PyArena *arena, PyObject *obj)
     205             : {
     206    81669700 :     int r = PyList_Append(arena->a_objects, obj);
     207    81669700 :     if (r >= 0) {
     208    81669700 :         Py_DECREF(obj);
     209             :     }
     210    81669700 :     return r;
     211             : }