LCOV - code coverage report
Current view: top level - py - gc.c (source / functions) Hit Total Coverage
Test: unix_coverage_v1.19.1-724-gfb7d21153.info Lines: 391 394 99.2 %
Date: 2022-12-01 09:37:31 Functions: 20 20 100.0 %
Branches: 215 246 87.4 %

           Branch data     Line data    Source code
       1                 :            : /*
       2                 :            :  * This file is part of the MicroPython project, http://micropython.org/
       3                 :            :  *
       4                 :            :  * The MIT License (MIT)
       5                 :            :  *
       6                 :            :  * Copyright (c) 2013, 2014 Damien P. George
       7                 :            :  * Copyright (c) 2014 Paul Sokolovsky
       8                 :            :  *
       9                 :            :  * Permission is hereby granted, free of charge, to any person obtaining a copy
      10                 :            :  * of this software and associated documentation files (the "Software"), to deal
      11                 :            :  * in the Software without restriction, including without limitation the rights
      12                 :            :  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
      13                 :            :  * copies of the Software, and to permit persons to whom the Software is
      14                 :            :  * furnished to do so, subject to the following conditions:
      15                 :            :  *
      16                 :            :  * The above copyright notice and this permission notice shall be included in
      17                 :            :  * all copies or substantial portions of the Software.
      18                 :            :  *
      19                 :            :  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
      20                 :            :  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
      21                 :            :  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
      22                 :            :  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
      23                 :            :  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
      24                 :            :  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
      25                 :            :  * THE SOFTWARE.
      26                 :            :  */
      27                 :            : 
      28                 :            : #include <assert.h>
      29                 :            : #include <stdio.h>
      30                 :            : #include <string.h>
      31                 :            : 
      32                 :            : #include "py/gc.h"
      33                 :            : #include "py/runtime.h"
      34                 :            : 
      35                 :            : #if MICROPY_ENABLE_GC
      36                 :            : 
      37                 :            : #if MICROPY_DEBUG_VERBOSE // print debugging info
      38                 :            : #define DEBUG_PRINT (1)
      39                 :            : #define DEBUG_printf DEBUG_printf
      40                 :            : #else // don't print debugging info
      41                 :            : #define DEBUG_PRINT (0)
      42                 :            : #define DEBUG_printf(...) (void)0
      43                 :            : #endif
      44                 :            : 
      45                 :            : // make this 1 to dump the heap each time it changes
      46                 :            : #define EXTENSIVE_HEAP_PROFILING (0)
      47                 :            : 
      48                 :            : // make this 1 to zero out swept memory to more eagerly
      49                 :            : // detect untraced object still in use
      50                 :            : #define CLEAR_ON_SWEEP (0)
      51                 :            : 
      52                 :            : #define WORDS_PER_BLOCK ((MICROPY_BYTES_PER_GC_BLOCK) / MP_BYTES_PER_OBJ_WORD)
      53                 :            : #define BYTES_PER_BLOCK (MICROPY_BYTES_PER_GC_BLOCK)
      54                 :            : 
      55                 :            : // ATB = allocation table byte
      56                 :            : // 0b00 = FREE -- free block
      57                 :            : // 0b01 = HEAD -- head of a chain of blocks
      58                 :            : // 0b10 = TAIL -- in the tail of a chain of blocks
      59                 :            : // 0b11 = MARK -- marked head block
      60                 :            : 
      61                 :            : #define AT_FREE (0)
      62                 :            : #define AT_HEAD (1)
      63                 :            : #define AT_TAIL (2)
      64                 :            : #define AT_MARK (3)
      65                 :            : 
      66                 :            : #define BLOCKS_PER_ATB (4)
      67                 :            : #define ATB_MASK_0 (0x03)
      68                 :            : #define ATB_MASK_1 (0x0c)
      69                 :            : #define ATB_MASK_2 (0x30)
      70                 :            : #define ATB_MASK_3 (0xc0)
      71                 :            : 
      72                 :            : #define ATB_0_IS_FREE(a) (((a) & ATB_MASK_0) == 0)
      73                 :            : #define ATB_1_IS_FREE(a) (((a) & ATB_MASK_1) == 0)
      74                 :            : #define ATB_2_IS_FREE(a) (((a) & ATB_MASK_2) == 0)
      75                 :            : #define ATB_3_IS_FREE(a) (((a) & ATB_MASK_3) == 0)
      76                 :            : 
      77                 :            : #if MICROPY_GC_SPLIT_HEAP
      78                 :            : #define NEXT_AREA(area) (area->next)
      79                 :            : #else
      80                 :            : #define NEXT_AREA(area) (NULL)
      81                 :            : #endif
      82                 :            : 
      83                 :            : #define BLOCK_SHIFT(block) (2 * ((block) & (BLOCKS_PER_ATB - 1)))
      84                 :            : #define ATB_GET_KIND(area, block) (((area)->gc_alloc_table_start[(block) / BLOCKS_PER_ATB] >> BLOCK_SHIFT(block)) & 3)
      85                 :            : #define ATB_ANY_TO_FREE(area, block) do { area->gc_alloc_table_start[(block) / BLOCKS_PER_ATB] &= (~(AT_MARK << BLOCK_SHIFT(block))); } while (0)
      86                 :            : #define ATB_FREE_TO_HEAD(area, block) do { area->gc_alloc_table_start[(block) / BLOCKS_PER_ATB] |= (AT_HEAD << BLOCK_SHIFT(block)); } while (0)
      87                 :            : #define ATB_FREE_TO_TAIL(area, block) do { area->gc_alloc_table_start[(block) / BLOCKS_PER_ATB] |= (AT_TAIL << BLOCK_SHIFT(block)); } while (0)
      88                 :            : #define ATB_HEAD_TO_MARK(area, block) do { area->gc_alloc_table_start[(block) / BLOCKS_PER_ATB] |= (AT_MARK << BLOCK_SHIFT(block)); } while (0)
      89                 :            : #define ATB_MARK_TO_HEAD(area, block) do { area->gc_alloc_table_start[(block) / BLOCKS_PER_ATB] &= (~(AT_TAIL << BLOCK_SHIFT(block))); } while (0)
      90                 :            : 
      91                 :            : #define BLOCK_FROM_PTR(area, ptr) (((byte *)(ptr) - area->gc_pool_start) / BYTES_PER_BLOCK)
      92                 :            : #define PTR_FROM_BLOCK(area, block) (((block) * BYTES_PER_BLOCK + (uintptr_t)area->gc_pool_start))
      93                 :            : 
      94                 :            : #if MICROPY_ENABLE_FINALISER
      95                 :            : // FTB = finaliser table byte
      96                 :            : // if set, then the corresponding block may have a finaliser
      97                 :            : 
      98                 :            : #define BLOCKS_PER_FTB (8)
      99                 :            : 
     100                 :            : #define FTB_GET(area, block) ((area->gc_finaliser_table_start[(block) / BLOCKS_PER_FTB] >> ((block) & 7)) & 1)
     101                 :            : #define FTB_SET(area, block) do { area->gc_finaliser_table_start[(block) / BLOCKS_PER_FTB] |= (1 << ((block) & 7)); } while (0)
     102                 :            : #define FTB_CLEAR(area, block) do { area->gc_finaliser_table_start[(block) / BLOCKS_PER_FTB] &= (~(1 << ((block) & 7))); } while (0)
     103                 :            : #endif
     104                 :            : 
     105                 :            : #if MICROPY_PY_THREAD && !MICROPY_PY_THREAD_GIL
     106                 :            : #define GC_ENTER() mp_thread_mutex_lock(&MP_STATE_MEM(gc_mutex), 1)
     107                 :            : #define GC_EXIT() mp_thread_mutex_unlock(&MP_STATE_MEM(gc_mutex))
     108                 :            : #else
     109                 :            : #define GC_ENTER()
     110                 :            : #define GC_EXIT()
     111                 :            : #endif
     112                 :            : 
     113                 :            : // TODO waste less memory; currently requires that all entries in alloc_table have a corresponding block in pool
     114                 :      12816 : STATIC void gc_setup_area(mp_state_mem_area_t *area, void *start, void *end) {
     115                 :            :     // calculate parameters for GC (T=total, A=alloc table, F=finaliser table, P=pool; all in bytes):
     116                 :            :     // T = A + F + P
     117                 :            :     //     F = A * BLOCKS_PER_ATB / BLOCKS_PER_FTB
     118                 :            :     //     P = A * BLOCKS_PER_ATB * BYTES_PER_BLOCK
     119                 :            :     // => T = A * (1 + BLOCKS_PER_ATB / BLOCKS_PER_FTB + BLOCKS_PER_ATB * BYTES_PER_BLOCK)
     120                 :      12816 :     size_t total_byte_len = (byte *)end - (byte *)start;
     121                 :            :     #if MICROPY_ENABLE_FINALISER
     122                 :      12816 :     area->gc_alloc_table_byte_len = total_byte_len * MP_BITS_PER_BYTE / (MP_BITS_PER_BYTE + MP_BITS_PER_BYTE * BLOCKS_PER_ATB / BLOCKS_PER_FTB + MP_BITS_PER_BYTE * BLOCKS_PER_ATB * BYTES_PER_BLOCK);
     123                 :            :     #else
     124                 :            :     area->gc_alloc_table_byte_len = total_byte_len / (1 + MP_BITS_PER_BYTE / 2 * BYTES_PER_BLOCK);
     125                 :            :     #endif
     126                 :            : 
     127                 :      12816 :     area->gc_alloc_table_start = (byte *)start;
     128                 :            : 
     129                 :            :     #if MICROPY_ENABLE_FINALISER
     130                 :      12816 :     size_t gc_finaliser_table_byte_len = (area->gc_alloc_table_byte_len * BLOCKS_PER_ATB + BLOCKS_PER_FTB - 1) / BLOCKS_PER_FTB;
     131                 :      12816 :     area->gc_finaliser_table_start = area->gc_alloc_table_start + area->gc_alloc_table_byte_len;
     132                 :            :     #endif
     133                 :            : 
     134                 :      12816 :     size_t gc_pool_block_len = area->gc_alloc_table_byte_len * BLOCKS_PER_ATB;
     135                 :      12816 :     area->gc_pool_start = (byte *)end - gc_pool_block_len * BYTES_PER_BLOCK;
     136                 :      12816 :     area->gc_pool_end = end;
     137                 :            : 
     138                 :            :     #if MICROPY_ENABLE_FINALISER
     139         [ -  + ]:      12816 :     assert(area->gc_pool_start >= area->gc_finaliser_table_start + gc_finaliser_table_byte_len);
     140                 :            :     #endif
     141                 :            : 
     142                 :            :     // clear ATBs
     143                 :      12816 :     memset(area->gc_alloc_table_start, 0, area->gc_alloc_table_byte_len);
     144                 :            : 
     145                 :            :     #if MICROPY_ENABLE_FINALISER
     146                 :            :     // clear FTBs
     147                 :      12816 :     memset(area->gc_finaliser_table_start, 0, gc_finaliser_table_byte_len);
     148                 :            :     #endif
     149                 :            : 
     150                 :      12816 :     area->gc_last_free_atb_index = 0;
     151                 :            : 
     152                 :            :     #if MICROPY_GC_SPLIT_HEAP
     153                 :      12816 :     area->next = NULL;
     154                 :            :     #endif
     155                 :      12816 : }
     156                 :            : 
     157                 :       3204 : void gc_init(void *start, void *end) {
     158                 :            :     // align end pointer on block boundary
     159                 :       3204 :     end = (void *)((uintptr_t)end & (~(BYTES_PER_BLOCK - 1)));
     160                 :       3204 :     DEBUG_printf("Initializing GC heap: %p..%p = " UINT_FMT " bytes\n", start, end, (byte *)end - (byte *)start);
     161                 :            : 
     162                 :       3204 :     gc_setup_area(&MP_STATE_MEM(area), start, end);
     163                 :            : 
     164                 :            :     // set last free ATB index to start of heap
     165                 :            :     #if MICROPY_GC_SPLIT_HEAP
     166                 :       3204 :     MP_STATE_MEM(gc_last_free_area) = &MP_STATE_MEM(area);
     167                 :            :     #endif
     168                 :            : 
     169                 :            :     // unlock the GC
     170                 :       3204 :     MP_STATE_THREAD(gc_lock_depth) = 0;
     171                 :            : 
     172                 :            :     // allow auto collection
     173                 :       3204 :     MP_STATE_MEM(gc_auto_collect_enabled) = 1;
     174                 :            : 
     175                 :            :     #if MICROPY_GC_ALLOC_THRESHOLD
     176                 :            :     // by default, maxuint for gc threshold, effectively turning gc-by-threshold off
     177                 :       3204 :     MP_STATE_MEM(gc_alloc_threshold) = (size_t)-1;
     178                 :       3204 :     MP_STATE_MEM(gc_alloc_amount) = 0;
     179                 :            :     #endif
     180                 :            : 
     181                 :            :     #if MICROPY_PY_THREAD && !MICROPY_PY_THREAD_GIL
     182                 :       3204 :     mp_thread_mutex_init(&MP_STATE_MEM(gc_mutex));
     183                 :            :     #endif
     184                 :            : 
     185                 :       3204 :     DEBUG_printf("GC layout:\n");
     186                 :       3204 :     DEBUG_printf("  alloc table at %p, length " UINT_FMT " bytes, " UINT_FMT " blocks\n", MP_STATE_MEM(gc_alloc_table_start), MP_STATE_MEM(gc_alloc_table_byte_len), MP_STATE_MEM(gc_alloc_table_byte_len) * BLOCKS_PER_ATB);
     187                 :            :     #if MICROPY_ENABLE_FINALISER
     188                 :       3204 :     DEBUG_printf("  finaliser table at %p, length " UINT_FMT " bytes, " UINT_FMT " blocks\n", MP_STATE_MEM(gc_finaliser_table_start), gc_finaliser_table_byte_len, gc_finaliser_table_byte_len * BLOCKS_PER_FTB);
     189                 :            :     #endif
     190                 :       3204 :     DEBUG_printf("  pool at %p, length " UINT_FMT " bytes, " UINT_FMT " blocks\n", MP_STATE_MEM(gc_pool_start), gc_pool_block_len * BYTES_PER_BLOCK, gc_pool_block_len);
     191                 :       3204 : }
     192                 :            : 
     193                 :            : #if MICROPY_GC_SPLIT_HEAP
     194                 :       9612 : void gc_add(void *start, void *end) {
     195                 :            :     // Place the area struct at the start of the area.
     196                 :       9612 :     mp_state_mem_area_t *area = (mp_state_mem_area_t *)start;
     197                 :       9612 :     start = (void *)((uintptr_t)start + sizeof(mp_state_mem_area_t));
     198                 :            : 
     199                 :       9612 :     end = (void *)((uintptr_t)end & (~(BYTES_PER_BLOCK - 1)));
     200                 :       9612 :     DEBUG_printf("Adding GC heap: %p..%p = " UINT_FMT " bytes\n", start, end, (byte *)end - (byte *)start);
     201                 :            : 
     202                 :            :     // Init this area
     203                 :       9612 :     gc_setup_area(area, start, end);
     204                 :            : 
     205                 :            :     // Find the last registered area in the linked list
     206                 :       9612 :     mp_state_mem_area_t *prev_area = &MP_STATE_MEM(area);
     207         [ +  + ]:      19224 :     while (prev_area->next != NULL) {
     208                 :            :         prev_area = prev_area->next;
     209                 :            :     }
     210                 :            : 
     211                 :            :     // Add this area to the linked list
     212                 :       9612 :     prev_area->next = area;
     213                 :       9612 : }
     214                 :            : #endif
     215                 :            : 
     216                 :        233 : void gc_lock(void) {
     217                 :            :     // This does not need to be atomic or have the GC mutex because:
     218                 :            :     // - each thread has its own gc_lock_depth so there are no races between threads;
     219                 :            :     // - a hard interrupt will only change gc_lock_depth during its execution, and
     220                 :            :     //   upon return will restore the value of gc_lock_depth.
     221                 :        233 :     MP_STATE_THREAD(gc_lock_depth)++;
     222                 :        233 : }
     223                 :            : 
     224                 :        233 : void gc_unlock(void) {
     225                 :            :     // This does not need to be atomic, See comment above in gc_lock.
     226                 :        233 :     MP_STATE_THREAD(gc_lock_depth)--;
     227                 :        233 : }
     228                 :            : 
     229                 :        110 : bool gc_is_locked(void) {
     230                 :        110 :     return MP_STATE_THREAD(gc_lock_depth) != 0;
     231                 :            : }
     232                 :            : 
     233                 :            : #if MICROPY_GC_SPLIT_HEAP
     234                 :            : // Returns the area to which this pointer belongs, or NULL if it isn't
     235                 :            : // allocated on the GC-managed heap.
     236                 :   12962950 : STATIC inline mp_state_mem_area_t *gc_get_ptr_area(const void *ptr) {
     237                 :   12962950 :     if (((uintptr_t)(ptr) & (BYTES_PER_BLOCK - 1)) != 0) {   // must be aligned on a block
     238                 :            :         return NULL;
     239                 :            :     }
     240   [ +  -  +  +  :   38258944 :     for (mp_state_mem_area_t *area = &MP_STATE_MEM(area); area != NULL; area = NEXT_AREA(area)) {
          +  -  +  +  +  
                      + ]
     241   [ +  +  +  +  :   32204403 :         if (ptr >= (void *)area->gc_pool_start   // must be above start of pool
          +  +  +  +  +  
                      + ]
     242   [ -  +  -  +  :    3899045 :             && ptr < (void *)area->gc_pool_end) {   // must be below end of pool
          -  +  +  +  +  
                      + ]
     243                 :            :             return area;
     244                 :            :         }
     245                 :            :     }
     246                 :            :     return NULL;
     247                 :            : }
     248                 :            : #endif
     249                 :            : 
     250                 :            : // ptr should be of type void*
     251                 :            : #define VERIFY_PTR(ptr) ( \
     252                 :            :     ((uintptr_t)(ptr) & (BYTES_PER_BLOCK - 1)) == 0          /* must be aligned on a block */ \
     253                 :            :     && ptr >= (void *)MP_STATE_MEM(area).gc_pool_start      /* must be above start of pool */ \
     254                 :            :     && ptr < (void *)MP_STATE_MEM(area).gc_pool_end         /* must be below end of pool */ \
     255                 :            :     )
     256                 :            : 
     257                 :            : #ifndef TRACE_MARK
     258                 :            : #if DEBUG_PRINT
     259                 :            : #define TRACE_MARK(block, ptr) DEBUG_printf("gc_mark(%p)\n", ptr)
     260                 :            : #else
     261                 :            : #define TRACE_MARK(block, ptr)
     262                 :            : #endif
     263                 :            : #endif
     264                 :            : 
     265                 :            : // Take the given block as the topmost block on the stack. Check all it's
     266                 :            : // children: mark the unmarked child blocks and put those newly marked
     267                 :            : // blocks on the stack. When all children have been checked, pop off the
     268                 :            : // topmost block on the stack and repeat with that one.
     269                 :            : #if MICROPY_GC_SPLIT_HEAP
     270                 :       7763 : STATIC void gc_mark_subtree(mp_state_mem_area_t *area, size_t block)
     271                 :            : #else
     272                 :            : STATIC void gc_mark_subtree(size_t block)
     273                 :            : #endif
     274                 :            : {
     275                 :            :     // Start with the block passed in the argument.
     276                 :       7763 :     size_t sp = 0;
     277                 :    5466207 :     for (;;) {
     278                 :            :         MICROPY_GC_HOOK_LOOP
     279                 :            : 
     280                 :            :         #if !MICROPY_GC_SPLIT_HEAP
     281                 :            :         mp_state_mem_area_t * area = &MP_STATE_MEM(area);
     282                 :            :         #endif
     283                 :            : 
     284                 :            :         // work out number of consecutive blocks in the chain starting with this one
     285                 :    2736985 :         size_t n_blocks = 0;
     286                 :    2924697 :         do {
     287                 :    2924697 :             n_blocks += 1;
     288         [ +  + ]:    2924697 :         } while (ATB_GET_KIND(area, block + n_blocks) == AT_TAIL);
     289                 :            : 
     290                 :            :         // check this block's children
     291                 :    2736985 :         void **ptrs = (void **)PTR_FROM_BLOCK(area, block);
     292         [ +  + ]:   14435773 :         for (size_t i = n_blocks * BYTES_PER_BLOCK / sizeof(void *); i > 0; i--, ptrs++) {
     293                 :            :             MICROPY_GC_HOOK_LOOP
     294                 :   11698788 :             void *ptr = *ptrs;
     295                 :            :             // If this is a heap pointer that hasn't been marked, mark it and push
     296                 :            :             // it's children to the stack.
     297                 :            :             #if MICROPY_GC_SPLIT_HEAP
     298         [ +  + ]:   11698788 :             mp_state_mem_area_t *ptr_area = gc_get_ptr_area(ptr);
     299         [ +  + ]:    8658797 :             if (!ptr_area) {
     300                 :            :                 // Not a heap-allocated pointer (might even be random data).
     301                 :    8963153 :                 continue;
     302                 :            :             }
     303                 :            :             #else
     304                 :            :             if (!VERIFY_PTR(ptr)) {
     305                 :            :                 continue;
     306                 :            :             }
     307                 :            :             mp_state_mem_area_t *ptr_area = area;
     308                 :            :             #endif
     309                 :    2735635 :             size_t ptr_block = BLOCK_FROM_PTR(ptr_area, ptr);
     310         [ +  + ]:    2735635 :             if (ATB_GET_KIND(ptr_area, ptr_block) != AT_HEAD) {
     311                 :            :                 // This block is already marked.
     312                 :       5860 :                 continue;
     313                 :            :             }
     314                 :            :             // An unmarked head. Mark it, and push it on gc stack.
     315                 :    2729775 :             TRACE_MARK(ptr_block, ptr);
     316                 :    2729775 :             ATB_HEAD_TO_MARK(ptr_area, ptr_block);
     317         [ +  + ]:    2729775 :             if (sp < MICROPY_ALLOC_GC_STACK_SIZE) {
     318                 :    2729222 :                 MP_STATE_MEM(gc_block_stack)[sp] = ptr_block;
     319                 :            :                 #if MICROPY_GC_SPLIT_HEAP
     320                 :    2729222 :                 MP_STATE_MEM(gc_area_stack)[sp] = ptr_area;
     321                 :            :                 #endif
     322                 :    2729222 :                 sp += 1;
     323                 :            :             } else {
     324                 :        553 :                 MP_STATE_MEM(gc_stack_overflow) = 1;
     325                 :            :             }
     326                 :            :         }
     327                 :            : 
     328                 :            :         // Are there any blocks on the stack?
     329         [ +  + ]:    2736985 :         if (sp == 0) {
     330                 :            :             break; // No, stack is empty, we're done.
     331                 :            :         }
     332                 :            : 
     333                 :            :         // pop the next block off the stack
     334                 :    2729222 :         sp -= 1;
     335                 :    2729222 :         block = MP_STATE_MEM(gc_block_stack)[sp];
     336                 :            :         #if MICROPY_GC_SPLIT_HEAP
     337                 :    2729222 :         area = MP_STATE_MEM(gc_area_stack)[sp];
     338                 :            :         #endif
     339                 :            :     }
     340                 :       7763 : }
     341                 :            : 
     342                 :       3622 : STATIC void gc_deal_with_stack_overflow(void) {
     343         [ +  + ]:       3627 :     while (MP_STATE_MEM(gc_stack_overflow)) {
     344                 :          5 :         MP_STATE_MEM(gc_stack_overflow) = 0;
     345                 :            : 
     346                 :            :         // scan entire memory looking for blocks which have been marked but not their children
     347         [ +  + ]:         25 :         for (mp_state_mem_area_t *area = &MP_STATE_MEM(area); area != NULL; area = NEXT_AREA(area)) {
     348         [ +  + ]:     323860 :             for (size_t block = 0; block < area->gc_alloc_table_byte_len * BLOCKS_PER_ATB; block++) {
     349                 :            :                 MICROPY_GC_HOOK_LOOP
     350                 :            :                 // trace (again) if mark bit set
     351         [ +  + ]:     323840 :                 if (ATB_GET_KIND(area, block) == AT_MARK) {
     352                 :            :                     #if MICROPY_GC_SPLIT_HEAP
     353                 :       2983 :                     gc_mark_subtree(area, block);
     354                 :            :                     #else
     355                 :            :                     gc_mark_subtree(block);
     356                 :            :                     #endif
     357                 :            :                 }
     358                 :            :             }
     359                 :            :         }
     360                 :            :     }
     361                 :       3622 : }
     362                 :            : 
     363                 :       3622 : STATIC void gc_sweep(void) {
     364                 :            :     #if MICROPY_PY_GC_COLLECT_RETVAL
     365                 :       3622 :     MP_STATE_MEM(gc_collected) = 0;
     366                 :            :     #endif
     367                 :            :     // free unmarked heads and their tails
     368                 :       3622 :     int free_tail = 0;
     369         [ +  + ]:      18110 :     for (mp_state_mem_area_t *area = &MP_STATE_MEM(area); area != NULL; area = NEXT_AREA(area)) {
     370         [ +  + ]:  234604184 :         for (size_t block = 0; block < area->gc_alloc_table_byte_len * BLOCKS_PER_ATB; block++) {
     371                 :            :             MICROPY_GC_HOOK_LOOP
     372   [ +  +  +  + ]:  234589696 :             switch (ATB_GET_KIND(area, block)) {
     373                 :    2656858 :                 case AT_HEAD:
     374                 :            :                     #if MICROPY_ENABLE_FINALISER
     375         [ +  + ]:    2656858 :                     if (FTB_GET(area, block)) {
     376                 :       4036 :                         mp_obj_base_t *obj = (mp_obj_base_t *)PTR_FROM_BLOCK(area, block);
     377         [ +  - ]:       4036 :                         if (obj->type != NULL) {
     378                 :            :                             // if the object has a type then see if it has a __del__ method
     379                 :       4036 :                             mp_obj_t dest[2];
     380                 :       4036 :                             mp_load_method_maybe(MP_OBJ_FROM_PTR(obj), MP_QSTR___del__, dest);
     381         [ +  - ]:       4036 :                             if (dest[0] != MP_OBJ_NULL) {
     382                 :            :                                 // load_method returned a method, execute it in a protected environment
     383                 :            :                                 #if MICROPY_ENABLE_SCHEDULER
     384                 :       4036 :                                 mp_sched_lock();
     385                 :            :                                 #endif
     386                 :       4036 :                                 mp_call_function_1_protected(dest[0], dest[1]);
     387                 :            :                                 #if MICROPY_ENABLE_SCHEDULER
     388                 :       4036 :                                 mp_sched_unlock();
     389                 :            :                                 #endif
     390                 :            :                             }
     391                 :            :                         }
     392                 :            :                         // clear finaliser flag
     393                 :       4036 :                         FTB_CLEAR(area, block);
     394                 :            :                     }
     395                 :            :                     #endif
     396                 :    2656858 :                     free_tail = 1;
     397                 :    2656858 :                     DEBUG_printf("gc_sweep(%p)\n", (void *)PTR_FROM_BLOCK(area, block));
     398                 :            :                     #if MICROPY_PY_GC_COLLECT_RETVAL
     399                 :    2656858 :                     MP_STATE_MEM(gc_collected)++;
     400                 :            :                     #endif
     401                 :            :                     // fall through to free the head
     402                 :    3622747 :                     MP_FALLTHROUGH
     403                 :            : 
     404                 :     965889 :                 case AT_TAIL:
     405         [ +  + ]:    3622747 :                     if (free_tail) {
     406                 :    3435757 :                         ATB_ANY_TO_FREE(area, block);
     407                 :            :                         #if CLEAR_ON_SWEEP
     408                 :            :                         memset((void *)PTR_FROM_BLOCK(area, block), 0, BYTES_PER_BLOCK);
     409                 :            :                         #endif
     410                 :            :                     }
     411                 :            :                     break;
     412                 :            : 
     413                 :    2734555 :                 case AT_MARK:
     414                 :    2734555 :                     ATB_MARK_TO_HEAD(area, block);
     415                 :    2734555 :                     free_tail = 0;
     416                 :    2734555 :                     break;
     417                 :            :             }
     418                 :            :         }
     419                 :            :     }
     420                 :       3622 : }
     421                 :            : 
     422                 :        422 : void gc_collect_start(void) {
     423                 :        422 :     GC_ENTER();
     424                 :        422 :     MP_STATE_THREAD(gc_lock_depth)++;
     425                 :            :     #if MICROPY_GC_ALLOC_THRESHOLD
     426                 :        422 :     MP_STATE_MEM(gc_alloc_amount) = 0;
     427                 :            :     #endif
     428                 :        422 :     MP_STATE_MEM(gc_stack_overflow) = 0;
     429                 :            : 
     430                 :            :     // Trace root pointers.  This relies on the root pointers being organised
     431                 :            :     // correctly in the mp_state_ctx structure.  We scan nlr_top, dict_locals,
     432                 :            :     // dict_globals, then the root pointer section of mp_state_vm.
     433                 :        422 :     void **ptrs = (void **)(void *)&mp_state_ctx;
     434                 :        422 :     size_t root_start = offsetof(mp_state_ctx_t, thread.dict_locals);
     435                 :        422 :     size_t root_end = offsetof(mp_state_ctx_t, vm.qstr_last_chunk);
     436                 :        422 :     gc_collect_root(ptrs + root_start / sizeof(void *), (root_end - root_start) / sizeof(void *));
     437                 :            : 
     438                 :            :     #if MICROPY_ENABLE_PYSTACK
     439                 :            :     // Trace root pointers from the Python stack.
     440                 :            :     ptrs = (void **)(void *)MP_STATE_THREAD(pystack_start);
     441                 :            :     gc_collect_root(ptrs, (MP_STATE_THREAD(pystack_cur) - MP_STATE_THREAD(pystack_start)) / sizeof(void *));
     442                 :            :     #endif
     443                 :        422 : }
     444                 :            : 
     445                 :            : // Address sanitizer needs to know that the access to ptrs[i] must always be
     446                 :            : // considered OK, even if it's a load from an address that would normally be
     447                 :            : // prohibited (due to being undefined, in a red zone, etc).
     448                 :            : #if defined(__GNUC__) && (__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 8))
     449                 :            : __attribute__((no_sanitize_address))
     450                 :            : #endif
     451                 :     278957 : static void *gc_get_ptr(void **ptrs, int i) {
     452                 :     278957 :     return ptrs[i];
     453                 :            : }
     454                 :            : 
     455                 :       2217 : void gc_collect_root(void **ptrs, size_t len) {
     456                 :            :     #if !MICROPY_GC_SPLIT_HEAP
     457                 :            :     mp_state_mem_area_t *area = &MP_STATE_MEM(area);
     458                 :            :     #endif
     459         [ +  + ]:     281174 :     for (size_t i = 0; i < len; i++) {
     460                 :            :         MICROPY_GC_HOOK_LOOP
     461                 :     278957 :         void *ptr = gc_get_ptr(ptrs, i);
     462                 :            :         #if MICROPY_GC_SPLIT_HEAP
     463         [ +  + ]:     278957 :         mp_state_mem_area_t *area = gc_get_ptr_area(ptr);
     464         [ +  + ]:     145612 :         if (!area) {
     465                 :     264722 :             continue;
     466                 :            :         }
     467                 :            :         #else
     468                 :            :         if (!VERIFY_PTR(ptr)) {
     469                 :            :             continue;
     470                 :            :         }
     471                 :            :         #endif
     472                 :      14235 :         size_t block = BLOCK_FROM_PTR(area, ptr);
     473         [ +  + ]:      14235 :         if (ATB_GET_KIND(area, block) == AT_HEAD) {
     474                 :            :             // An unmarked head: mark it, and mark all its children
     475                 :       4780 :             ATB_HEAD_TO_MARK(area, block);
     476                 :            :             #if MICROPY_GC_SPLIT_HEAP
     477                 :       4780 :             gc_mark_subtree(area, block);
     478                 :            :             #else
     479                 :            :             gc_mark_subtree(block);
     480                 :            :             #endif
     481                 :            :         }
     482                 :            :     }
     483                 :       2217 : }
     484                 :            : 
     485                 :       3622 : void gc_collect_end(void) {
     486                 :       3622 :     gc_deal_with_stack_overflow();
     487                 :       3622 :     gc_sweep();
     488                 :            :     #if MICROPY_GC_SPLIT_HEAP
     489                 :       3622 :     MP_STATE_MEM(gc_last_free_area) = &MP_STATE_MEM(area);
     490                 :            :     #endif
     491         [ +  + ]:      18110 :     for (mp_state_mem_area_t *area = &MP_STATE_MEM(area); area != NULL; area = NEXT_AREA(area)) {
     492                 :      14488 :         area->gc_last_free_atb_index = 0;
     493                 :            :     }
     494                 :       3622 :     MP_STATE_THREAD(gc_lock_depth)--;
     495                 :       3622 :     GC_EXIT();
     496                 :       3622 : }
     497                 :            : 
     498                 :       3200 : void gc_sweep_all(void) {
     499                 :       3200 :     GC_ENTER();
     500                 :       3200 :     MP_STATE_THREAD(gc_lock_depth)++;
     501                 :       3200 :     MP_STATE_MEM(gc_stack_overflow) = 0;
     502                 :       3200 :     gc_collect_end();
     503                 :       3200 : }
     504                 :            : 
     505                 :         26 : void gc_info(gc_info_t *info) {
     506                 :         26 :     GC_ENTER();
     507                 :         26 :     info->total = 0;
     508                 :         26 :     info->used = 0;
     509                 :         26 :     info->free = 0;
     510                 :         26 :     info->max_free = 0;
     511                 :         26 :     info->num_1block = 0;
     512                 :         26 :     info->num_2block = 0;
     513                 :         26 :     info->max_block = 0;
     514         [ +  + ]:        130 :     for (mp_state_mem_area_t *area = &MP_STATE_MEM(area); area != NULL; area = NEXT_AREA(area)) {
     515                 :        104 :         bool finish = false;
     516                 :        104 :         info->total += area->gc_pool_end - area->gc_pool_start;
     517         [ +  + ]:    1684072 :         for (size_t block = 0, len = 0, len_free = 0; !finish;) {
     518                 :    1683968 :             size_t kind = ATB_GET_KIND(area, block);
     519   [ +  +  +  - ]:    1683968 :             switch (kind) {
     520                 :    1682598 :                 case AT_FREE:
     521                 :    1682598 :                     info->free += 1;
     522                 :    1682598 :                     len_free += 1;
     523                 :    1682598 :                     len = 0;
     524                 :    1682598 :                     break;
     525                 :            : 
     526                 :        598 :                 case AT_HEAD:
     527                 :        598 :                     info->used += 1;
     528                 :        598 :                     len = 1;
     529                 :        598 :                     break;
     530                 :            : 
     531                 :        772 :                 case AT_TAIL:
     532                 :        772 :                     info->used += 1;
     533                 :        772 :                     len += 1;
     534                 :        772 :                     break;
     535                 :            : 
     536                 :            :                 case AT_MARK:
     537                 :            :                     // shouldn't happen
     538                 :            :                     break;
     539                 :            :             }
     540                 :            : 
     541                 :    1683968 :             block++;
     542                 :    1683968 :             finish = (block == area->gc_alloc_table_byte_len * BLOCKS_PER_ATB);
     543                 :            :             // Get next block type if possible
     544         [ +  + ]:    1683968 :             if (!finish) {
     545                 :    1683864 :                 kind = ATB_GET_KIND(area, block);
     546                 :            :             }
     547                 :            : 
     548   [ +  +  +  + ]:    1683968 :             if (finish || kind == AT_FREE || kind == AT_HEAD) {
     549         [ +  + ]:    1683196 :                 if (len == 1) {
     550                 :        322 :                     info->num_1block += 1;
     551         [ +  + ]:    1682874 :                 } else if (len == 2) {
     552                 :        148 :                     info->num_2block += 1;
     553                 :            :                 }
     554         [ +  + ]:    1683196 :                 if (len > info->max_block) {
     555                 :         82 :                     info->max_block = len;
     556                 :            :                 }
     557         [ +  + ]:    1683196 :                 if (finish || kind == AT_HEAD) {
     558         [ +  + ]:        676 :                     if (len_free > info->max_free) {
     559                 :        124 :                         info->max_free = len_free;
     560                 :            :                     }
     561                 :            :                     len_free = 0;
     562                 :            :                 }
     563                 :            :             }
     564                 :            :         }
     565                 :            :     }
     566                 :            : 
     567                 :         26 :     info->used *= BYTES_PER_BLOCK;
     568                 :         26 :     info->free *= BYTES_PER_BLOCK;
     569                 :         26 :     GC_EXIT();
     570                 :         26 : }
     571                 :            : 
     572                 :    3191092 : void *gc_alloc(size_t n_bytes, unsigned int alloc_flags) {
     573                 :    3191092 :     bool has_finaliser = alloc_flags & GC_ALLOC_FLAG_HAS_FINALISER;
     574                 :    3191092 :     size_t n_blocks = ((n_bytes + BYTES_PER_BLOCK - 1) & (~(BYTES_PER_BLOCK - 1))) / BYTES_PER_BLOCK;
     575                 :    3191092 :     DEBUG_printf("gc_alloc(" UINT_FMT " bytes -> " UINT_FMT " blocks)\n", n_bytes, n_blocks);
     576                 :            : 
     577                 :            :     // check for 0 allocation
     578         [ +  + ]:    3191092 :     if (n_blocks == 0) {
     579                 :            :         return NULL;
     580                 :            :     }
     581                 :            : 
     582                 :            :     // check if GC is locked
     583         [ +  + ]:    3186559 :     if (MP_STATE_THREAD(gc_lock_depth) > 0) {
     584                 :            :         return NULL;
     585                 :            :     }
     586                 :            : 
     587                 :    3186038 :     GC_ENTER();
     588                 :            : 
     589                 :    3186843 :     mp_state_mem_area_t *area;
     590                 :    3186843 :     size_t i;
     591                 :    3186843 :     size_t end_block;
     592                 :    3186843 :     size_t start_block;
     593                 :    3186843 :     size_t n_free;
     594                 :    3186843 :     int collected = !MP_STATE_MEM(gc_auto_collect_enabled);
     595                 :            : 
     596                 :            :     #if MICROPY_GC_ALLOC_THRESHOLD
     597   [ +  +  +  + ]:    3186843 :     if (!collected && MP_STATE_MEM(gc_alloc_amount) >= MP_STATE_MEM(gc_alloc_threshold)) {
     598                 :         24 :         GC_EXIT();
     599                 :         24 :         gc_collect();
     600                 :         24 :         collected = 1;
     601                 :         24 :         GC_ENTER();
     602                 :            :     }
     603                 :            :     #endif
     604                 :            : 
     605                 :    3187007 :     for (;;) {
     606                 :            : 
     607                 :            :         #if MICROPY_GC_SPLIT_HEAP
     608                 :    3186925 :         area = MP_STATE_MEM(gc_last_free_area);
     609                 :            :         #else
     610                 :            :         area = &MP_STATE_MEM(area);
     611                 :            :         #endif
     612                 :            : 
     613                 :            :         // look for a run of n_blocks available blocks
     614         [ +  + ]:    3198188 :         for (; area != NULL; area = NEXT_AREA(area), i = 0) {
     615                 :    3198060 :             n_free = 0;
     616         [ +  + ]:  120125639 :             for (i = area->gc_last_free_atb_index; i < area->gc_alloc_table_byte_len; i++) {
     617                 :  120114376 :                 byte a = area->gc_alloc_table_start[i];
     618                 :            :                 // *FORMAT-OFF*
     619   [ +  +  +  + ]:  120114376 :                 if (ATB_0_IS_FREE(a)) { if (++n_free >= n_blocks) { i = i * BLOCKS_PER_ATB + 0; goto found; } } else { n_free = 0; }
     620   [ +  +  +  + ]:  119319024 :                 if (ATB_1_IS_FREE(a)) { if (++n_free >= n_blocks) { i = i * BLOCKS_PER_ATB + 1; goto found; } } else { n_free = 0; }
     621   [ +  +  +  + ]:  118518363 :                 if (ATB_2_IS_FREE(a)) { if (++n_free >= n_blocks) { i = i * BLOCKS_PER_ATB + 2; goto found; } } else { n_free = 0; }
     622   [ +  +  +  + ]:  117717863 :                 if (ATB_3_IS_FREE(a)) { if (++n_free >= n_blocks) { i = i * BLOCKS_PER_ATB + 3; goto found; } } else { n_free = 0; }
     623                 :            :                 // *FORMAT-ON*
     624                 :            :             }
     625                 :            : 
     626                 :            :             // No free blocks found on this heap. Mark this heap as
     627                 :            :             // filled, so we won't try to find free space here again until
     628                 :            :             // space is freed.
     629                 :            :             #if MICROPY_GC_SPLIT_HEAP
     630         [ +  + ]:      11263 :             if (n_blocks == 1) {
     631                 :        886 :                 area->gc_last_free_atb_index = (i + 1) / BLOCKS_PER_ATB; // or (size_t)-1
     632                 :            :             }
     633                 :            :             #endif
     634                 :            :         }
     635                 :            : 
     636                 :        128 :         GC_EXIT();
     637                 :            :         // nothing found!
     638         [ +  + ]:        128 :         if (collected) {
     639                 :            :             return NULL;
     640                 :            :         }
     641                 :         82 :         DEBUG_printf("gc_alloc(" UINT_FMT "): no free mem, triggering GC\n", n_bytes);
     642                 :         82 :         gc_collect();
     643                 :         82 :         collected = 1;
     644                 :         82 :         GC_ENTER();
     645                 :            :     }
     646                 :            : 
     647                 :            :     // found, ending at block i inclusive
     648                 :    3186797 : found:
     649                 :            :     // get starting and end blocks, both inclusive
     650                 :    3186797 :     end_block = i;
     651                 :    3186797 :     start_block = i - n_free + 1;
     652                 :            : 
     653                 :            :     // Set last free ATB index to block after last block we found, for start of
     654                 :            :     // next scan.  To reduce fragmentation, we only do this if we were looking
     655                 :            :     // for a single free block, which guarantees that there are no free blocks
     656                 :            :     // before this one.  Also, whenever we free or shink a block we must check
     657                 :            :     // if this index needs adjusting (see gc_realloc and gc_free).
     658         [ +  + ]:    3186797 :     if (n_free == 1) {
     659                 :            :         #if MICROPY_GC_SPLIT_HEAP
     660                 :    2518392 :         MP_STATE_MEM(gc_last_free_area) = area;
     661                 :            :         #endif
     662                 :    2518392 :         area->gc_last_free_atb_index = (i + 1) / BLOCKS_PER_ATB;
     663                 :            :     }
     664                 :            : 
     665                 :            :     // mark first block as used head
     666                 :    3186797 :     ATB_FREE_TO_HEAD(area, start_block);
     667                 :            : 
     668                 :            :     // mark rest of blocks as used tail
     669                 :            :     // TODO for a run of many blocks can make this more efficient
     670         [ +  + ]:    5780190 :     for (size_t bl = start_block + 1; bl <= end_block; bl++) {
     671                 :    2593393 :         ATB_FREE_TO_TAIL(area, bl);
     672                 :            :     }
     673                 :            : 
     674                 :            :     // get pointer to first block
     675                 :            :     // we must create this pointer before unlocking the GC so a collection can find it
     676                 :    3186797 :     void *ret_ptr = (void *)(area->gc_pool_start + start_block * BYTES_PER_BLOCK);
     677                 :    3186797 :     DEBUG_printf("gc_alloc(%p)\n", ret_ptr);
     678                 :            : 
     679                 :            :     #if MICROPY_GC_ALLOC_THRESHOLD
     680                 :    3186797 :     MP_STATE_MEM(gc_alloc_amount) += n_blocks;
     681                 :            :     #endif
     682                 :            : 
     683                 :    3186797 :     GC_EXIT();
     684                 :            : 
     685                 :            :     #if MICROPY_GC_CONSERVATIVE_CLEAR
     686                 :            :     // be conservative and zero out all the newly allocated blocks
     687                 :    3186661 :     memset((byte *)ret_ptr, 0, (end_block - start_block + 1) * BYTES_PER_BLOCK);
     688                 :            :     #else
     689                 :            :     // zero out the additional bytes of the newly allocated blocks
     690                 :            :     // This is needed because the blocks may have previously held pointers
     691                 :            :     // to the heap and will not be set to something else if the caller
     692                 :            :     // doesn't actually use the entire block.  As such they will continue
     693                 :            :     // to point to the heap and may prevent other blocks from being reclaimed.
     694                 :            :     memset((byte *)ret_ptr + n_bytes, 0, (end_block - start_block + 1) * BYTES_PER_BLOCK - n_bytes);
     695                 :            :     #endif
     696                 :            : 
     697                 :            :     #if MICROPY_ENABLE_FINALISER
     698         [ +  + ]:    3186661 :     if (has_finaliser) {
     699                 :            :         // clear type pointer in case it is never set
     700                 :       4042 :         ((mp_obj_base_t *)ret_ptr)->type = NULL;
     701                 :            :         // set mp_obj flag only if it has a finaliser
     702                 :       4042 :         GC_ENTER();
     703                 :       4042 :         FTB_SET(area, start_block);
     704                 :       4042 :         GC_EXIT();
     705                 :            :     }
     706                 :            :     #else
     707                 :            :     (void)has_finaliser;
     708                 :            :     #endif
     709                 :            : 
     710                 :            :     #if EXTENSIVE_HEAP_PROFILING
     711                 :            :     gc_dump_alloc_table();
     712                 :            :     #endif
     713                 :            : 
     714                 :            :     return ret_ptr;
     715                 :            : }
     716                 :            : 
     717                 :            : /*
     718                 :            : void *gc_alloc(mp_uint_t n_bytes) {
     719                 :            :     return _gc_alloc(n_bytes, false);
     720                 :            : }
     721                 :            : 
     722                 :            : void *gc_alloc_with_finaliser(mp_uint_t n_bytes) {
     723                 :            :     return _gc_alloc(n_bytes, true);
     724                 :            : }
     725                 :            : */
     726                 :            : 
     727                 :            : // force the freeing of a piece of memory
     728                 :            : // TODO: freeing here does not call finaliser
     729                 :     540343 : void gc_free(void *ptr) {
     730         [ +  # ]:     540343 :     if (MP_STATE_THREAD(gc_lock_depth) > 0) {
     731                 :            :         // TODO how to deal with this error?
     732                 :            :         return;
     733                 :            :     }
     734                 :            : 
     735                 :     540336 :     GC_ENTER();
     736                 :            : 
     737                 :     540426 :     DEBUG_printf("gc_free(%p)\n", ptr);
     738                 :            : 
     739         [ +  + ]:     540426 :     if (ptr == NULL) {
     740                 :            :         // free(NULL) is a no-op
     741                 :      10601 :         GC_EXIT();
     742                 :      10601 :         return;
     743                 :            :     }
     744                 :            : 
     745                 :            :     // get the GC block number corresponding to this pointer
     746                 :     529825 :     mp_state_mem_area_t *area;
     747                 :            :     #if MICROPY_GC_SPLIT_HEAP
     748         [ +  - ]:     529825 :     area = gc_get_ptr_area(ptr);
     749         [ -  + ]:     529825 :     assert(area);
     750                 :            :     #else
     751                 :            :     assert(VERIFY_PTR(ptr));
     752                 :            :     area = &MP_STATE_MEM(area);
     753                 :            :     #endif
     754                 :            : 
     755                 :     529825 :     size_t block = BLOCK_FROM_PTR(area, ptr);
     756         [ -  + ]:     529825 :     assert(ATB_GET_KIND(area, block) == AT_HEAD);
     757                 :            : 
     758                 :            :     #if MICROPY_ENABLE_FINALISER
     759                 :     529825 :     FTB_CLEAR(area, block);
     760                 :            :     #endif
     761                 :            : 
     762                 :            :     #if MICROPY_GC_SPLIT_HEAP
     763         [ +  + ]:     529825 :     if (MP_STATE_MEM(gc_last_free_area) != area) {
     764                 :            :         // We freed something but it isn't the current area. Reset the
     765                 :            :         // last free area to the start for a rescan. Note that this won't
     766                 :            :         // give much of a performance hit, since areas that are completely
     767                 :            :         // filled will likely be skipped (the gc_last_free_atb_index
     768                 :            :         // points to the last block).
     769                 :            :         // The reason why this is necessary is because it is not possible
     770                 :            :         // to see which area came first (like it is possible to adjust
     771                 :            :         // gc_last_free_atb_index based on whether the freed block is
     772                 :            :         // before the last free block).
     773                 :        499 :         MP_STATE_MEM(gc_last_free_area) = &MP_STATE_MEM(area);
     774                 :            :     }
     775                 :            :     #endif
     776                 :            : 
     777                 :            :     // set the last_free pointer to this block if it's earlier in the heap
     778         [ +  + ]:     529825 :     if (block / BLOCKS_PER_ATB < area->gc_last_free_atb_index) {
     779                 :      84743 :         area->gc_last_free_atb_index = block / BLOCKS_PER_ATB;
     780                 :            :     }
     781                 :            : 
     782                 :            :     // free head and all of its tail blocks
     783                 :    2542880 :     do {
     784                 :    2542880 :         ATB_ANY_TO_FREE(area, block);
     785                 :    2542880 :         block += 1;
     786         [ +  + ]:    2542880 :     } while (ATB_GET_KIND(area, block) == AT_TAIL);
     787                 :            : 
     788                 :     529825 :     GC_EXIT();
     789                 :            : 
     790                 :            :     #if EXTENSIVE_HEAP_PROFILING
     791                 :            :     gc_dump_alloc_table();
     792                 :            :     #endif
     793                 :            : }
     794                 :            : 
     795                 :         26 : size_t gc_nbytes(const void *ptr) {
     796                 :         26 :     GC_ENTER();
     797                 :            : 
     798                 :         26 :     mp_state_mem_area_t *area;
     799                 :            :     #if MICROPY_GC_SPLIT_HEAP
     800         [ +  - ]:         26 :     area = gc_get_ptr_area(ptr);
     801                 :            :     #else
     802                 :            :     if (VERIFY_PTR(ptr)) {
     803                 :            :         area = &MP_STATE_MEM(area);
     804                 :            :     } else {
     805                 :            :         area = NULL;
     806                 :            :     }
     807                 :            :     #endif
     808                 :            : 
     809         [ +  + ]:         26 :     if (area) {
     810                 :         24 :         size_t block = BLOCK_FROM_PTR(area, ptr);
     811         [ +  - ]:         24 :         if (ATB_GET_KIND(area, block) == AT_HEAD) {
     812                 :            :             // work out number of consecutive blocks in the chain starting with this on
     813                 :            :             size_t n_blocks = 0;
     814                 :        152 :             do {
     815                 :        152 :                 n_blocks += 1;
     816         [ +  + ]:        152 :             } while (ATB_GET_KIND(area, block + n_blocks) == AT_TAIL);
     817                 :         24 :             GC_EXIT();
     818                 :         24 :             return n_blocks * BYTES_PER_BLOCK;
     819                 :            :         }
     820                 :            :     }
     821                 :            : 
     822                 :            :     // invalid pointer
     823                 :          2 :     GC_EXIT();
     824                 :          2 :     return 0;
     825                 :            : }
     826                 :            : 
     827                 :            : #if 0
     828                 :            : // old, simple realloc that didn't expand memory in place
     829                 :            : void *gc_realloc(void *ptr, mp_uint_t n_bytes) {
     830                 :            :     mp_uint_t n_existing = gc_nbytes(ptr);
     831                 :            :     if (n_bytes <= n_existing) {
     832                 :            :         return ptr;
     833                 :            :     } else {
     834                 :            :         bool has_finaliser;
     835                 :            :         if (ptr == NULL) {
     836                 :            :             has_finaliser = false;
     837                 :            :         } else {
     838                 :            :             #if MICROPY_ENABLE_FINALISER
     839                 :            :             has_finaliser = FTB_GET(BLOCK_FROM_PTR((mp_uint_t)ptr));
     840                 :            :             #else
     841                 :            :             has_finaliser = false;
     842                 :            :             #endif
     843                 :            :         }
     844                 :            :         void *ptr2 = gc_alloc(n_bytes, has_finaliser);
     845                 :            :         if (ptr2 == NULL) {
     846                 :            :             return ptr2;
     847                 :            :         }
     848                 :            :         memcpy(ptr2, ptr, n_existing);
     849                 :            :         gc_free(ptr);
     850                 :            :         return ptr2;
     851                 :            :     }
     852                 :            : }
     853                 :            : 
     854                 :            : #else // Alternative gc_realloc impl
     855                 :            : 
     856                 :     496718 : void *gc_realloc(void *ptr_in, size_t n_bytes, bool allow_move) {
     857                 :            :     // check for pure allocation
     858         [ +  + ]:     496718 :     if (ptr_in == NULL) {
     859                 :      41336 :         return gc_alloc(n_bytes, false);
     860                 :            :     }
     861                 :            : 
     862                 :            :     // check for pure free
     863         [ +  + ]:     455382 :     if (n_bytes == 0) {
     864                 :          2 :         gc_free(ptr_in);
     865                 :          2 :         return NULL;
     866                 :            :     }
     867                 :            : 
     868         [ +  + ]:     455380 :     if (MP_STATE_THREAD(gc_lock_depth) > 0) {
     869                 :            :         return NULL;
     870                 :            :     }
     871                 :            : 
     872                 :     455354 :     void *ptr = ptr_in;
     873                 :            : 
     874                 :     455354 :     GC_ENTER();
     875                 :            : 
     876                 :            :     // get the GC block number corresponding to this pointer
     877                 :     455354 :     mp_state_mem_area_t *area;
     878                 :            :     #if MICROPY_GC_SPLIT_HEAP
     879         [ +  - ]:     455354 :     area = gc_get_ptr_area(ptr);
     880         [ -  + ]:     455354 :     assert(area);
     881                 :            :     #else
     882                 :            :     assert(VERIFY_PTR(ptr));
     883                 :            :     area = &MP_STATE_MEM(area);
     884                 :            :     #endif
     885                 :     455354 :     size_t block = BLOCK_FROM_PTR(area, ptr);
     886         [ -  + ]:     455354 :     assert(ATB_GET_KIND(area, block) == AT_HEAD);
     887                 :            : 
     888                 :            :     // compute number of new blocks that are requested
     889                 :     455354 :     size_t new_blocks = (n_bytes + BYTES_PER_BLOCK - 1) / BYTES_PER_BLOCK;
     890                 :            : 
     891                 :            :     // Get the total number of consecutive blocks that are already allocated to
     892                 :            :     // this chunk of memory, and then count the number of free blocks following
     893                 :            :     // it.  Stop if we reach the end of the heap, or if we find enough extra
     894                 :            :     // free blocks to satisfy the realloc.  Note that we need to compute the
     895                 :            :     // total size of the existing memory chunk so we can correctly and
     896                 :            :     // efficiently shrink it (see below for shrinking code).
     897                 :     455354 :     size_t n_free = 0;
     898                 :     455354 :     size_t n_blocks = 1; // counting HEAD block
     899                 :     455354 :     size_t max_block = area->gc_alloc_table_byte_len * BLOCKS_PER_ATB;
     900         [ +  + ]:    6581623 :     for (size_t bl = block + n_blocks; bl < max_block; bl++) {
     901                 :    6581597 :         byte block_type = ATB_GET_KIND(area, bl);
     902         [ +  + ]:    6581597 :         if (block_type == AT_TAIL) {
     903                 :    5994878 :             n_blocks++;
     904                 :    5994878 :             continue;
     905                 :            :         }
     906         [ +  + ]:     586719 :         if (block_type == AT_FREE) {
     907                 :     520462 :             n_free++;
     908         [ +  + ]:     520462 :             if (n_blocks + n_free >= new_blocks) {
     909                 :            :                 // stop as soon as we find enough blocks for n_bytes
     910                 :            :                 break;
     911                 :            :             }
     912                 :     131391 :             continue;
     913                 :            :         }
     914                 :            :         break;
     915                 :            :     }
     916                 :            : 
     917                 :            :     // return original ptr if it already has the requested number of blocks
     918         [ +  + ]:     455354 :     if (new_blocks == n_blocks) {
     919                 :     257445 :         GC_EXIT();
     920                 :     257445 :         return ptr_in;
     921                 :            :     }
     922                 :            : 
     923                 :            :     // check if we can shrink the allocated area
     924         [ +  + ]:     197909 :     if (new_blocks < n_blocks) {
     925                 :            :         // free unneeded tail blocks
     926         [ +  + ]:      45498 :         for (size_t bl = block + new_blocks, count = n_blocks - new_blocks; count > 0; bl++, count--) {
     927                 :      23602 :             ATB_ANY_TO_FREE(area, bl);
     928                 :            :         }
     929                 :            : 
     930                 :            :         #if MICROPY_GC_SPLIT_HEAP
     931         [ +  + ]:      21896 :         if (MP_STATE_MEM(gc_last_free_area) != area) {
     932                 :            :             // See comment in gc_free.
     933                 :         12 :             MP_STATE_MEM(gc_last_free_area) = &MP_STATE_MEM(area);
     934                 :            :         }
     935                 :            :         #endif
     936                 :            : 
     937                 :            :         // set the last_free pointer to end of this block if it's earlier in the heap
     938         [ +  + ]:      21896 :         if ((block + new_blocks) / BLOCKS_PER_ATB < area->gc_last_free_atb_index) {
     939                 :        653 :             area->gc_last_free_atb_index = (block + new_blocks) / BLOCKS_PER_ATB;
     940                 :            :         }
     941                 :            : 
     942                 :      21896 :         GC_EXIT();
     943                 :            : 
     944                 :            :         #if EXTENSIVE_HEAP_PROFILING
     945                 :            :         gc_dump_alloc_table();
     946                 :            :         #endif
     947                 :            : 
     948                 :      21896 :         return ptr_in;
     949                 :            :     }
     950                 :            : 
     951                 :            :     // check if we can expand in place
     952         [ +  + ]:     176013 :     if (new_blocks <= n_blocks + n_free) {
     953                 :            :         // mark few more blocks as used tail
     954         [ +  + ]:     368544 :         for (size_t bl = block + n_blocks; bl < block + new_blocks; bl++) {
     955         [ -  + ]:     222243 :             assert(ATB_GET_KIND(area, bl) == AT_FREE);
     956                 :     222243 :             ATB_FREE_TO_TAIL(area, bl);
     957                 :            :         }
     958                 :            : 
     959                 :     146301 :         GC_EXIT();
     960                 :            : 
     961                 :            :         #if MICROPY_GC_CONSERVATIVE_CLEAR
     962                 :            :         // be conservative and zero out all the newly allocated blocks
     963                 :     146301 :         memset((byte *)ptr_in + n_blocks * BYTES_PER_BLOCK, 0, (new_blocks - n_blocks) * BYTES_PER_BLOCK);
     964                 :            :         #else
     965                 :            :         // zero out the additional bytes of the newly allocated blocks (see comment above in gc_alloc)
     966                 :            :         memset((byte *)ptr_in + n_bytes, 0, new_blocks * BYTES_PER_BLOCK - n_bytes);
     967                 :            :         #endif
     968                 :            : 
     969                 :            :         #if EXTENSIVE_HEAP_PROFILING
     970                 :            :         gc_dump_alloc_table();
     971                 :            :         #endif
     972                 :            : 
     973                 :     146301 :         return ptr_in;
     974                 :            :     }
     975                 :            : 
     976                 :            :     #if MICROPY_ENABLE_FINALISER
     977                 :      29712 :     bool ftb_state = FTB_GET(area, block);
     978                 :            :     #else
     979                 :            :     bool ftb_state = false;
     980                 :            :     #endif
     981                 :            : 
     982                 :      29712 :     GC_EXIT();
     983                 :            : 
     984         [ +  + ]:      29712 :     if (!allow_move) {
     985                 :            :         // not allowed to move memory block so return failure
     986                 :            :         return NULL;
     987                 :            :     }
     988                 :            : 
     989                 :            :     // can't resize inplace; try to find a new contiguous chain
     990                 :      18633 :     void *ptr_out = gc_alloc(n_bytes, ftb_state);
     991                 :            : 
     992                 :            :     // check that the alloc succeeded
     993         [ +  + ]:      18633 :     if (ptr_out == NULL) {
     994                 :            :         return NULL;
     995                 :            :     }
     996                 :            : 
     997                 :      18625 :     DEBUG_printf("gc_realloc(%p -> %p)\n", ptr_in, ptr_out);
     998                 :      18625 :     memcpy(ptr_out, ptr_in, n_blocks * BYTES_PER_BLOCK);
     999                 :      18625 :     gc_free(ptr_in);
    1000                 :      18625 :     return ptr_out;
    1001                 :            : }
    1002                 :            : #endif // Alternative gc_realloc impl
    1003                 :            : 
    1004                 :         18 : void gc_dump_info(void) {
    1005                 :         18 :     gc_info_t info;
    1006                 :         18 :     gc_info(&info);
    1007                 :         18 :     mp_printf(&mp_plat_print, "GC: total: %u, used: %u, free: %u\n",
    1008                 :         18 :         (uint)info.total, (uint)info.used, (uint)info.free);
    1009                 :         18 :     mp_printf(&mp_plat_print, " No. of 1-blocks: %u, 2-blocks: %u, max blk sz: %u, max free sz: %u\n",
    1010                 :         18 :         (uint)info.num_1block, (uint)info.num_2block, (uint)info.max_block, (uint)info.max_free);
    1011                 :         18 : }
    1012                 :            : 
    1013                 :          4 : void gc_dump_alloc_table(void) {
    1014                 :          4 :     GC_ENTER();
    1015                 :          4 :     static const size_t DUMP_BYTES_PER_LINE = 64;
    1016         [ +  + ]:         20 :     for (mp_state_mem_area_t *area = &MP_STATE_MEM(area); area != NULL; area = NEXT_AREA(area)) {
    1017                 :            :         #if !EXTENSIVE_HEAP_PROFILING
    1018                 :            :         // When comparing heap output we don't want to print the starting
    1019                 :            :         // pointer of the heap because it changes from run to run.
    1020                 :         16 :         mp_printf(&mp_plat_print, "GC memory layout; from %p:", area->gc_pool_start);
    1021                 :            :         #endif
    1022         [ +  - ]:        528 :         for (size_t bl = 0; bl < area->gc_alloc_table_byte_len * BLOCKS_PER_ATB; bl++) {
    1023         [ +  + ]:        528 :             if (bl % DUMP_BYTES_PER_LINE == 0) {
    1024                 :            :                 // a new line of blocks
    1025                 :            :                 {
    1026                 :            :                     // check if this line contains only free blocks
    1027                 :            :                     size_t bl2 = bl;
    1028   [ +  +  +  + ]:     258652 :                     while (bl2 < area->gc_alloc_table_byte_len * BLOCKS_PER_ATB && ATB_GET_KIND(area, bl2) == AT_FREE) {
    1029                 :     258628 :                         bl2++;
    1030                 :            :                     }
    1031         [ +  + ]:         24 :                     if (bl2 - bl >= 2 * DUMP_BYTES_PER_LINE) {
    1032                 :            :                         // there are at least 2 lines containing only free blocks, so abbreviate their printing
    1033                 :         16 :                         mp_printf(&mp_plat_print, "\n       (%u lines all free)", (uint)(bl2 - bl) / DUMP_BYTES_PER_LINE);
    1034                 :         16 :                         bl = bl2 & (~(DUMP_BYTES_PER_LINE - 1));
    1035         [ -  + ]:         16 :                         if (bl >= area->gc_alloc_table_byte_len * BLOCKS_PER_ATB) {
    1036                 :            :                             // got to end of heap
    1037                 :            :                             break;
    1038                 :            :                         }
    1039                 :            :                     }
    1040                 :            :                 }
    1041                 :            :                 // print header for new line of blocks
    1042                 :            :                 // (the cast to uint32_t is for 16-bit ports)
    1043                 :            :                 // mp_printf(&mp_plat_print, "\n%05x: ", (uint)(PTR_FROM_BLOCK(area, bl) & (uint32_t)0xfffff));
    1044                 :          8 :                 mp_printf(&mp_plat_print, "\n%05x: ", (uint)((bl * BYTES_PER_BLOCK) & (uint32_t)0xfffff));
    1045                 :            :             }
    1046                 :        512 :             int c = ' ';
    1047   [ +  +  -  + ]:        512 :             switch (ATB_GET_KIND(area, bl)) {
    1048                 :            :                 case AT_FREE:
    1049                 :            :                     c = '.';
    1050                 :            :                     break;
    1051                 :            :                 /* this prints out if the object is reachable from BSS or STACK (for unix only)
    1052                 :            :                 case AT_HEAD: {
    1053                 :            :                     c = 'h';
    1054                 :            :                     void **ptrs = (void**)(void*)&mp_state_ctx;
    1055                 :            :                     mp_uint_t len = offsetof(mp_state_ctx_t, vm.stack_top) / sizeof(mp_uint_t);
    1056                 :            :                     for (mp_uint_t i = 0; i < len; i++) {
    1057                 :            :                         mp_uint_t ptr = (mp_uint_t)ptrs[i];
    1058                 :            :                         if (gc_get_ptr_area(ptr) && BLOCK_FROM_PTR(ptr) == bl) {
    1059                 :            :                             c = 'B';
    1060                 :            :                             break;
    1061                 :            :                         }
    1062                 :            :                     }
    1063                 :            :                     if (c == 'h') {
    1064                 :            :                         ptrs = (void**)&c;
    1065                 :            :                         len = ((mp_uint_t)MP_STATE_THREAD(stack_top) - (mp_uint_t)&c) / sizeof(mp_uint_t);
    1066                 :            :                         for (mp_uint_t i = 0; i < len; i++) {
    1067                 :            :                             mp_uint_t ptr = (mp_uint_t)ptrs[i];
    1068                 :            :                             if (gc_get_ptr_area(ptr) && BLOCK_FROM_PTR(ptr) == bl) {
    1069                 :            :                                 c = 'S';
    1070                 :            :                                 break;
    1071                 :            :                             }
    1072                 :            :                         }
    1073                 :            :                     }
    1074                 :            :                     break;
    1075                 :            :                 }
    1076                 :            :                 */
    1077                 :            :                 /* this prints the uPy object type of the head block */
    1078                 :         72 :                 case AT_HEAD: {
    1079                 :         72 :                     void **ptr = (void **)(area->gc_pool_start + bl * BYTES_PER_BLOCK);
    1080         [ +  - ]:         72 :                     if (*ptr == &mp_type_tuple) {
    1081                 :            :                         c = 'T';
    1082         [ +  - ]:         72 :                     } else if (*ptr == &mp_type_list) {
    1083                 :            :                         c = 'L';
    1084         [ +  - ]:         72 :                     } else if (*ptr == &mp_type_dict) {
    1085                 :            :                         c = 'D';
    1086   [ +  -  +  - ]:         72 :                     } else if (*ptr == &mp_type_str || *ptr == &mp_type_bytes) {
    1087                 :            :                         c = 'S';
    1088                 :            :                     }
    1089                 :            :                     #if MICROPY_PY_BUILTINS_BYTEARRAY
    1090         [ +  - ]:         72 :                     else if (*ptr == &mp_type_bytearray) {
    1091                 :            :                         c = 'A';
    1092                 :            :                     }
    1093                 :            :                     #endif
    1094                 :            :                     #if MICROPY_PY_ARRAY
    1095         [ +  - ]:         72 :                     else if (*ptr == &mp_type_array) {
    1096                 :            :                         c = 'A';
    1097                 :            :                     }
    1098                 :            :                     #endif
    1099                 :            :                     #if MICROPY_PY_BUILTINS_FLOAT
    1100         [ +  - ]:         72 :                     else if (*ptr == &mp_type_float) {
    1101                 :            :                         c = 'F';
    1102                 :            :                     }
    1103                 :            :                     #endif
    1104         [ +  + ]:         72 :                     else if (*ptr == &mp_type_fun_bc) {
    1105                 :            :                         c = 'B';
    1106         [ +  - ]:         68 :                     } else if (*ptr == &mp_type_module) {
    1107                 :            :                         c = 'M';
    1108                 :            :                     } else {
    1109                 :         68 :                         c = 'h';
    1110                 :            :                         #if 0
    1111                 :            :                         // This code prints "Q" for qstr-pool data, and "q" for qstr-str
    1112                 :            :                         // data.  It can be useful to see how qstrs are being allocated,
    1113                 :            :                         // but is disabled by default because it is very slow.
    1114                 :            :                         for (qstr_pool_t *pool = MP_STATE_VM(last_pool); c == 'h' && pool != NULL; pool = pool->prev) {
    1115                 :            :                             if ((qstr_pool_t *)ptr == pool) {
    1116                 :            :                                 c = 'Q';
    1117                 :            :                                 break;
    1118                 :            :                             }
    1119                 :            :                             for (const byte **q = pool->qstrs, **q_top = pool->qstrs + pool->len; q < q_top; q++) {
    1120                 :            :                                 if ((const byte *)ptr == *q) {
    1121                 :            :                                     c = 'q';
    1122                 :            :                                     break;
    1123                 :            :                                 }
    1124                 :            :                             }
    1125                 :            :                         }
    1126                 :            :                         #endif
    1127                 :            :                     }
    1128                 :            :                     break;
    1129                 :            :                 }
    1130                 :         96 :                 case AT_TAIL:
    1131                 :         96 :                     c = '=';
    1132                 :         96 :                     break;
    1133                 :          0 :                 case AT_MARK:
    1134                 :          0 :                     c = 'm';
    1135                 :          0 :                     break;
    1136                 :            :             }
    1137                 :        512 :             mp_printf(&mp_plat_print, "%c", c);
    1138                 :            :         }
    1139                 :         16 :         mp_print_str(&mp_plat_print, "\n");
    1140                 :            :     }
    1141                 :          4 :     GC_EXIT();
    1142                 :          4 : }
    1143                 :            : 
    1144                 :            : #if 0
    1145                 :            : // For testing the GC functions
    1146                 :            : void gc_test(void) {
    1147                 :            :     mp_uint_t len = 500;
    1148                 :            :     mp_uint_t *heap = malloc(len);
    1149                 :            :     gc_init(heap, heap + len / sizeof(mp_uint_t));
    1150                 :            :     void *ptrs[100];
    1151                 :            :     {
    1152                 :            :         mp_uint_t **p = gc_alloc(16, false);
    1153                 :            :         p[0] = gc_alloc(64, false);
    1154                 :            :         p[1] = gc_alloc(1, false);
    1155                 :            :         p[2] = gc_alloc(1, false);
    1156                 :            :         p[3] = gc_alloc(1, false);
    1157                 :            :         mp_uint_t ***p2 = gc_alloc(16, false);
    1158                 :            :         p2[0] = p;
    1159                 :            :         p2[1] = p;
    1160                 :            :         ptrs[0] = p2;
    1161                 :            :     }
    1162                 :            :     for (int i = 0; i < 25; i += 2) {
    1163                 :            :         mp_uint_t *p = gc_alloc(i, false);
    1164                 :            :         printf("p=%p\n", p);
    1165                 :            :         if (i & 3) {
    1166                 :            :             // ptrs[i] = p;
    1167                 :            :         }
    1168                 :            :     }
    1169                 :            : 
    1170                 :            :     printf("Before GC:\n");
    1171                 :            :     gc_dump_alloc_table();
    1172                 :            :     printf("Starting GC...\n");
    1173                 :            :     gc_collect_start();
    1174                 :            :     gc_collect_root(ptrs, sizeof(ptrs) / sizeof(void *));
    1175                 :            :     gc_collect_end();
    1176                 :            :     printf("After GC:\n");
    1177                 :            :     gc_dump_alloc_table();
    1178                 :            : }
    1179                 :            : #endif
    1180                 :            : 
    1181                 :            : #endif // MICROPY_ENABLE_GC

Generated by: LCOV version 1.15-5-g462f71d