Branch data     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                 :    1309977 : block_new(size_t size)
      78                 :            : {
      79                 :            :     /* Allocate header and block as one unit.
      80                 :            :        ab_mem points just past header. */
      81                 :    1309977 :     block *b = (block *)PyMem_Malloc(sizeof(block) + size);
      82         [ -  + ]:    1309977 :     if (!b)
      83                 :          0 :         return NULL;
      84                 :    1309977 :     b->ab_size = size;
      85                 :    1309977 :     b->ab_mem = (void *)(b + 1);
      86                 :    1309977 :     b->ab_next = NULL;
      87                 :    1309977 :     b->ab_offset = (char *)_Py_ALIGN_UP(b->ab_mem, ALIGNMENT) -
      88                 :    1309977 :             (char *)(b->ab_mem);
      89                 :    1309977 :     return b;
      90                 :            : }
      91                 :            : 
      92                 :            : static void
      93                 :     126917 : block_free(block *b) {
      94         [ +  + ]:    1436883 :     while (b) {
      95                 :    1309966 :         block *next = b->ab_next;
      96                 :    1309966 :         PyMem_Free(b);
      97                 :    1309966 :         b = next;
      98                 :            :     }
      99                 :     126917 : }
     100                 :            : 
     101                 :            : static void *
     102                 :  282045770 : block_alloc(block *b, size_t size)
     103                 :            : {
     104                 :            :     void *p;
     105                 :            :     assert(b);
     106                 :  282045770 :     size = _Py_SIZE_ROUND_UP(size, ALIGNMENT);
     107         [ +  + ]:  282045770 :     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                 :    1183058 :         block *newbl = block_new(
     113                 :            :                         size < DEFAULT_BLOCK_SIZE ?
     114                 :            :                         DEFAULT_BLOCK_SIZE : size);
     115         [ -  + ]:    1183058 :         if (!newbl)
     116                 :          0 :             return NULL;
     117                 :            :         assert(!b->ab_next);
     118                 :    1183058 :         b->ab_next = newbl;
     119                 :    1183058 :         b = newbl;
     120                 :            :     }
     121                 :            : 
     122                 :            :     assert(b->ab_offset + size <= b->ab_size);
     123                 :  282045770 :     p = (void *)(((char *)b->ab_mem) + b->ab_offset);
     124                 :  282045770 :     b->ab_offset += size;
     125                 :  282045770 :     return p;
     126                 :            : }
     127                 :            : 
     128                 :            : PyArena *
     129                 :     126936 : _PyArena_New(void)
     130                 :            : {
     131                 :     126936 :     PyArena* arena = (PyArena *)PyMem_Malloc(sizeof(PyArena));
     132         [ +  + ]:     126936 :     if (!arena)
     133                 :            :         return (PyArena*)PyErr_NoMemory();
     134                 :            : 
     135                 :     126919 :     arena->a_head = block_new(DEFAULT_BLOCK_SIZE);
     136                 :     126919 :     arena->a_cur = arena->a_head;
     137         [ -  + ]:     126919 :     if (!arena->a_head) {
     138                 :          0 :         PyMem_Free((void *)arena);
     139                 :            :         return (PyArena*)PyErr_NoMemory();
     140                 :            :     }
     141                 :     126919 :     arena->a_objects = PyList_New(0);
     142         [ -  + ]:     126919 :     if (!arena->a_objects) {
     143                 :          0 :         block_free(arena->a_head);
     144                 :          0 :         PyMem_Free((void *)arena);
     145                 :            :         return (PyArena*)PyErr_NoMemory();
     146                 :            :     }
     147                 :            : #if defined(Py_DEBUG)
     148                 :            :     arena->total_allocs = 0;
     149                 :            :     arena->total_size = 0;
     150                 :            :     arena->total_blocks = 1;
     151                 :            :     arena->total_block_size = DEFAULT_BLOCK_SIZE;
     152                 :            :     arena->total_big_blocks = 0;
     153                 :            : #endif
     154                 :     126919 :     return arena;
     155                 :            : }
     156                 :            : 
     157                 :            : void
     158                 :     126917 : _PyArena_Free(PyArena *arena)
     159                 :            : {
     160                 :            :     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                 :     126917 :     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                 :     126917 :     Py_DECREF(arena->a_objects);
     177                 :     126917 :     PyMem_Free(arena);
     178                 :     126917 : }
     179                 :            : 
     180                 :            : void *
     181                 :  282045770 : _PyArena_Malloc(PyArena *arena, size_t size)
     182                 :            : {
     183                 :  282045770 :     void *p = block_alloc(arena->a_cur, size);
     184         [ -  + ]:  282045770 :     if (!p)
     185                 :            :         return PyErr_NoMemory();
     186                 :            : #if defined(Py_DEBUG)
     187                 :            :     arena->total_allocs++;
     188                 :            :     arena->total_size += size;
     189                 :            : #endif
     190                 :            :     /* Reset cur if we allocated a new block. */
     191         [ +  + ]:  282045770 :     if (arena->a_cur->ab_next) {
     192                 :    1183058 :         arena->a_cur = arena->a_cur->ab_next;
     193                 :            : #if defined(Py_DEBUG)
     194                 :            :         arena->total_blocks++;
     195                 :            :         arena->total_block_size += arena->a_cur->ab_size;
     196                 :            :         if (arena->a_cur->ab_size > DEFAULT_BLOCK_SIZE)
     197                 :            :             ++arena->total_big_blocks;
     198                 :            : #endif
     199                 :            :     }
     200                 :  282045770 :     return p;
     201                 :            : }
     202                 :            : 
     203                 :            : int
     204                 :   81359972 : _PyArena_AddPyObject(PyArena *arena, PyObject *obj)
     205                 :            : {
     206                 :   81359972 :     int r = PyList_Append(arena->a_objects, obj);
     207         [ +  - ]:   81359972 :     if (r >= 0) {
     208                 :   81359972 :         Py_DECREF(obj);
     209                 :            :     }
     210                 :   81359972 :     return r;
     211                 :            : }