LCOV - code coverage report
Current view: top level - py - gc.c (source / functions) Hit Total Coverage
Test: unix_coverage_v1.23.0-37-gd7d77d91b.info Lines: 409 412 99.3 %
Date: 2024-06-12 04:17:08 Functions: 20 20 100.0 %
Branches: 221 250 88.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_DEBUG_VALGRIND
      36                 :            : #include <valgrind/memcheck.h>
      37                 :            : #endif
      38                 :            : 
      39                 :            : #if MICROPY_ENABLE_GC
      40                 :            : 
      41                 :            : #if MICROPY_DEBUG_VERBOSE // print debugging info
      42                 :            : #define DEBUG_PRINT (1)
      43                 :            : #define DEBUG_printf DEBUG_printf
      44                 :            : #else // don't print debugging info
      45                 :            : #define DEBUG_PRINT (0)
      46                 :            : #define DEBUG_printf(...) (void)0
      47                 :            : #endif
      48                 :            : 
      49                 :            : // make this 1 to dump the heap each time it changes
      50                 :            : #define EXTENSIVE_HEAP_PROFILING (0)
      51                 :            : 
      52                 :            : // make this 1 to zero out swept memory to more eagerly
      53                 :            : // detect untraced object still in use
      54                 :            : #define CLEAR_ON_SWEEP (0)
      55                 :            : 
      56                 :            : #define WORDS_PER_BLOCK ((MICROPY_BYTES_PER_GC_BLOCK) / MP_BYTES_PER_OBJ_WORD)
      57                 :            : #define BYTES_PER_BLOCK (MICROPY_BYTES_PER_GC_BLOCK)
      58                 :            : 
      59                 :            : // ATB = allocation table byte
      60                 :            : // 0b00 = FREE -- free block
      61                 :            : // 0b01 = HEAD -- head of a chain of blocks
      62                 :            : // 0b10 = TAIL -- in the tail of a chain of blocks
      63                 :            : // 0b11 = MARK -- marked head block
      64                 :            : 
      65                 :            : #define AT_FREE (0)
      66                 :            : #define AT_HEAD (1)
      67                 :            : #define AT_TAIL (2)
      68                 :            : #define AT_MARK (3)
      69                 :            : 
      70                 :            : #define BLOCKS_PER_ATB (4)
      71                 :            : #define ATB_MASK_0 (0x03)
      72                 :            : #define ATB_MASK_1 (0x0c)
      73                 :            : #define ATB_MASK_2 (0x30)
      74                 :            : #define ATB_MASK_3 (0xc0)
      75                 :            : 
      76                 :            : #define ATB_0_IS_FREE(a) (((a) & ATB_MASK_0) == 0)
      77                 :            : #define ATB_1_IS_FREE(a) (((a) & ATB_MASK_1) == 0)
      78                 :            : #define ATB_2_IS_FREE(a) (((a) & ATB_MASK_2) == 0)
      79                 :            : #define ATB_3_IS_FREE(a) (((a) & ATB_MASK_3) == 0)
      80                 :            : 
      81                 :            : #if MICROPY_GC_SPLIT_HEAP
      82                 :            : #define NEXT_AREA(area) ((area)->next)
      83                 :            : #else
      84                 :            : #define NEXT_AREA(area) (NULL)
      85                 :            : #endif
      86                 :            : 
      87                 :            : #define BLOCK_SHIFT(block) (2 * ((block) & (BLOCKS_PER_ATB - 1)))
      88                 :            : #define ATB_GET_KIND(area, block) (((area)->gc_alloc_table_start[(block) / BLOCKS_PER_ATB] >> BLOCK_SHIFT(block)) & 3)
      89                 :            : #define ATB_ANY_TO_FREE(area, block) do { area->gc_alloc_table_start[(block) / BLOCKS_PER_ATB] &= (~(AT_MARK << BLOCK_SHIFT(block))); } while (0)
      90                 :            : #define ATB_FREE_TO_HEAD(area, block) do { area->gc_alloc_table_start[(block) / BLOCKS_PER_ATB] |= (AT_HEAD << BLOCK_SHIFT(block)); } while (0)
      91                 :            : #define ATB_FREE_TO_TAIL(area, block) do { area->gc_alloc_table_start[(block) / BLOCKS_PER_ATB] |= (AT_TAIL << BLOCK_SHIFT(block)); } while (0)
      92                 :            : #define ATB_HEAD_TO_MARK(area, block) do { area->gc_alloc_table_start[(block) / BLOCKS_PER_ATB] |= (AT_MARK << BLOCK_SHIFT(block)); } while (0)
      93                 :            : #define ATB_MARK_TO_HEAD(area, block) do { area->gc_alloc_table_start[(block) / BLOCKS_PER_ATB] &= (~(AT_TAIL << BLOCK_SHIFT(block))); } while (0)
      94                 :            : 
      95                 :            : #define BLOCK_FROM_PTR(area, ptr) (((byte *)(ptr) - area->gc_pool_start) / BYTES_PER_BLOCK)
      96                 :            : #define PTR_FROM_BLOCK(area, block) (((block) * BYTES_PER_BLOCK + (uintptr_t)area->gc_pool_start))
      97                 :            : 
      98                 :            : // After the ATB, there must be a byte filled with AT_FREE so that gc_mark_tree
      99                 :            : // cannot erroneously conclude that a block extends past the end of the GC heap
     100                 :            : // due to bit patterns in the FTB (or first block, if finalizers are disabled)
     101                 :            : // being interpreted as AT_TAIL.
     102                 :            : #define ALLOC_TABLE_GAP_BYTE (1)
     103                 :            : 
     104                 :            : #if MICROPY_ENABLE_FINALISER
     105                 :            : // FTB = finaliser table byte
     106                 :            : // if set, then the corresponding block may have a finaliser
     107                 :            : 
     108                 :            : #define BLOCKS_PER_FTB (8)
     109                 :            : 
     110                 :            : #define FTB_GET(area, block) ((area->gc_finaliser_table_start[(block) / BLOCKS_PER_FTB] >> ((block) & 7)) & 1)
     111                 :            : #define FTB_SET(area, block) do { area->gc_finaliser_table_start[(block) / BLOCKS_PER_FTB] |= (1 << ((block) & 7)); } while (0)
     112                 :            : #define FTB_CLEAR(area, block) do { area->gc_finaliser_table_start[(block) / BLOCKS_PER_FTB] &= (~(1 << ((block) & 7))); } while (0)
     113                 :            : #endif
     114                 :            : 
     115                 :            : #if MICROPY_PY_THREAD && !MICROPY_PY_THREAD_GIL
     116                 :            : #define GC_ENTER() mp_thread_mutex_lock(&MP_STATE_MEM(gc_mutex), 1)
     117                 :            : #define GC_EXIT() mp_thread_mutex_unlock(&MP_STATE_MEM(gc_mutex))
     118                 :            : #else
     119                 :            : #define GC_ENTER()
     120                 :            : #define GC_EXIT()
     121                 :            : #endif
     122                 :            : 
     123                 :            : // TODO waste less memory; currently requires that all entries in alloc_table have a corresponding block in pool
     124                 :      17424 : static void gc_setup_area(mp_state_mem_area_t *area, void *start, void *end) {
     125                 :            :     // calculate parameters for GC (T=total, A=alloc table, F=finaliser table, P=pool; all in bytes):
     126                 :            :     // T = A + F + P
     127                 :            :     //     F = A * BLOCKS_PER_ATB / BLOCKS_PER_FTB
     128                 :            :     //     P = A * BLOCKS_PER_ATB * BYTES_PER_BLOCK
     129                 :            :     // => T = A * (1 + BLOCKS_PER_ATB / BLOCKS_PER_FTB + BLOCKS_PER_ATB * BYTES_PER_BLOCK)
     130                 :      17424 :     size_t total_byte_len = (byte *)end - (byte *)start;
     131                 :            :     #if MICROPY_ENABLE_FINALISER
     132                 :      17424 :     area->gc_alloc_table_byte_len = (total_byte_len - ALLOC_TABLE_GAP_BYTE)
     133                 :      17424 :         * MP_BITS_PER_BYTE
     134                 :      17424 :         / (
     135                 :            :             MP_BITS_PER_BYTE
     136                 :            :             + MP_BITS_PER_BYTE * BLOCKS_PER_ATB / BLOCKS_PER_FTB
     137                 :            :             + MP_BITS_PER_BYTE * BLOCKS_PER_ATB * BYTES_PER_BLOCK
     138                 :            :             );
     139                 :            :     #else
     140                 :            :     area->gc_alloc_table_byte_len = (total_byte_len - ALLOC_TABLE_GAP_BYTE) / (1 + MP_BITS_PER_BYTE / 2 * BYTES_PER_BLOCK);
     141                 :            :     #endif
     142                 :            : 
     143                 :      17424 :     area->gc_alloc_table_start = (byte *)start;
     144                 :            : 
     145                 :            :     #if MICROPY_ENABLE_FINALISER
     146                 :      17424 :     size_t gc_finaliser_table_byte_len = (area->gc_alloc_table_byte_len * BLOCKS_PER_ATB + BLOCKS_PER_FTB - 1) / BLOCKS_PER_FTB;
     147                 :      17424 :     area->gc_finaliser_table_start = area->gc_alloc_table_start + area->gc_alloc_table_byte_len + ALLOC_TABLE_GAP_BYTE;
     148                 :            :     #endif
     149                 :            : 
     150                 :      17424 :     size_t gc_pool_block_len = area->gc_alloc_table_byte_len * BLOCKS_PER_ATB;
     151                 :      17424 :     area->gc_pool_start = (byte *)end - gc_pool_block_len * BYTES_PER_BLOCK;
     152                 :      17424 :     area->gc_pool_end = end;
     153                 :            : 
     154                 :            :     #if MICROPY_ENABLE_FINALISER
     155         [ -  + ]:      17424 :     assert(area->gc_pool_start >= area->gc_finaliser_table_start + gc_finaliser_table_byte_len);
     156                 :            :     #endif
     157                 :            : 
     158                 :            :     #if MICROPY_ENABLE_FINALISER
     159                 :            :     // clear ATB's and FTB's
     160                 :      17424 :     memset(area->gc_alloc_table_start, 0, gc_finaliser_table_byte_len + area->gc_alloc_table_byte_len + ALLOC_TABLE_GAP_BYTE);
     161                 :            :     #else
     162                 :            :     // clear ATB's
     163                 :            :     memset(area->gc_alloc_table_start, 0, area->gc_alloc_table_byte_len + ALLOC_TABLE_GAP_BYTE);
     164                 :            :     #endif
     165                 :            : 
     166                 :      17424 :     area->gc_last_free_atb_index = 0;
     167                 :      17424 :     area->gc_last_used_block = 0;
     168                 :            : 
     169                 :            :     #if MICROPY_GC_SPLIT_HEAP
     170                 :      17424 :     area->next = NULL;
     171                 :            :     #endif
     172                 :            : 
     173                 :      17424 :     DEBUG_printf("GC layout:\n");
     174                 :      17424 :     DEBUG_printf("  alloc table at %p, length " UINT_FMT " bytes, "
     175                 :            :         UINT_FMT " blocks\n",
     176                 :            :         area->gc_alloc_table_start, area->gc_alloc_table_byte_len,
     177                 :            :         area->gc_alloc_table_byte_len * BLOCKS_PER_ATB);
     178                 :            :     #if MICROPY_ENABLE_FINALISER
     179                 :      17424 :     DEBUG_printf("  finaliser table at %p, length " UINT_FMT " bytes, "
     180                 :            :         UINT_FMT " blocks\n", area->gc_finaliser_table_start,
     181                 :            :         gc_finaliser_table_byte_len,
     182                 :            :         gc_finaliser_table_byte_len * BLOCKS_PER_FTB);
     183                 :            :     #endif
     184                 :      17424 :     DEBUG_printf("  pool at %p, length " UINT_FMT " bytes, "
     185                 :            :         UINT_FMT " blocks\n", area->gc_pool_start,
     186                 :            :         gc_pool_block_len * BYTES_PER_BLOCK, gc_pool_block_len);
     187                 :      17424 : }
     188                 :            : 
     189                 :       7428 : void gc_init(void *start, void *end) {
     190                 :            :     // align end pointer on block boundary
     191                 :       7428 :     end = (void *)((uintptr_t)end & (~(BYTES_PER_BLOCK - 1)));
     192                 :       7428 :     DEBUG_printf("Initializing GC heap: %p..%p = " UINT_FMT " bytes\n", start, end, (byte *)end - (byte *)start);
     193                 :            : 
     194                 :       7428 :     gc_setup_area(&MP_STATE_MEM(area), start, end);
     195                 :            : 
     196                 :            :     // set last free ATB index to start of heap
     197                 :            :     #if MICROPY_GC_SPLIT_HEAP
     198                 :       7428 :     MP_STATE_MEM(gc_last_free_area) = &MP_STATE_MEM(area);
     199                 :            :     #endif
     200                 :            : 
     201                 :            :     // unlock the GC
     202                 :       7428 :     MP_STATE_THREAD(gc_lock_depth) = 0;
     203                 :            : 
     204                 :            :     // allow auto collection
     205                 :       7428 :     MP_STATE_MEM(gc_auto_collect_enabled) = 1;
     206                 :            : 
     207                 :            :     #if MICROPY_GC_ALLOC_THRESHOLD
     208                 :            :     // by default, maxuint for gc threshold, effectively turning gc-by-threshold off
     209                 :       7428 :     MP_STATE_MEM(gc_alloc_threshold) = (size_t)-1;
     210                 :       7428 :     MP_STATE_MEM(gc_alloc_amount) = 0;
     211                 :            :     #endif
     212                 :            : 
     213                 :            :     #if MICROPY_PY_THREAD && !MICROPY_PY_THREAD_GIL
     214                 :       7428 :     mp_thread_mutex_init(&MP_STATE_MEM(gc_mutex));
     215                 :            :     #endif
     216                 :       7428 : }
     217                 :            : 
     218                 :            : #if MICROPY_GC_SPLIT_HEAP
     219                 :       9996 : void gc_add(void *start, void *end) {
     220                 :            :     // Place the area struct at the start of the area.
     221                 :       9996 :     mp_state_mem_area_t *area = (mp_state_mem_area_t *)start;
     222                 :       9996 :     start = (void *)((uintptr_t)start + sizeof(mp_state_mem_area_t));
     223                 :            : 
     224                 :       9996 :     end = (void *)((uintptr_t)end & (~(BYTES_PER_BLOCK - 1)));
     225                 :       9996 :     DEBUG_printf("Adding GC heap: %p..%p = " UINT_FMT " bytes\n", start, end, (byte *)end - (byte *)start);
     226                 :            : 
     227                 :            :     // Init this area
     228                 :       9996 :     gc_setup_area(area, start, end);
     229                 :            : 
     230                 :            :     // Find the last registered area in the linked list
     231                 :       9996 :     mp_state_mem_area_t *prev_area = &MP_STATE_MEM(area);
     232         [ +  + ]:      19992 :     while (prev_area->next != NULL) {
     233                 :            :         prev_area = prev_area->next;
     234                 :            :     }
     235                 :            : 
     236                 :            :     // Add this area to the linked list
     237                 :       9996 :     prev_area->next = area;
     238                 :       9996 : }
     239                 :            : 
     240                 :            : #if MICROPY_GC_SPLIT_HEAP_AUTO
     241                 :            : // Try to automatically add a heap area large enough to fulfill 'failed_alloc'.
     242                 :            : static bool gc_try_add_heap(size_t failed_alloc) {
     243                 :            :     // 'needed' is the size of a heap large enough to hold failed_alloc, with
     244                 :            :     // the additional metadata overheads as calculated in gc_setup_area().
     245                 :            :     //
     246                 :            :     // Rather than reproduce all of that logic here, we approximate that adding
     247                 :            :     // (13/512) is enough overhead for sufficiently large heap areas (the
     248                 :            :     // overhead converges to 3/128, but there's some fixed overhead and some
     249                 :            :     // rounding up of partial block sizes).
     250                 :            :     size_t needed = failed_alloc + MAX(2048, failed_alloc * 13 / 512);
     251                 :            : 
     252                 :            :     size_t avail = gc_get_max_new_split();
     253                 :            : 
     254                 :            :     DEBUG_printf("gc_try_add_heap failed_alloc " UINT_FMT ", "
     255                 :            :         "needed " UINT_FMT ", avail " UINT_FMT " bytes \n",
     256                 :            :         failed_alloc,
     257                 :            :         needed,
     258                 :            :         avail);
     259                 :            : 
     260                 :            :     if (avail < needed) {
     261                 :            :         // Can't fit this allocation, or system heap has nearly run out anyway
     262                 :            :         return false;
     263                 :            :     }
     264                 :            : 
     265                 :            :     // Deciding how much to grow the total heap by each time is tricky:
     266                 :            :     //
     267                 :            :     // - Grow by too small amounts, leads to heap fragmentation issues.
     268                 :            :     //
     269                 :            :     // - Grow by too large amounts, may lead to system heap running out of
     270                 :            :     //   space.
     271                 :            :     //
     272                 :            :     // Currently, this implementation is:
     273                 :            :     //
     274                 :            :     // - At minimum, aim to double the total heap size each time we add a new
     275                 :            :     //   heap.  i.e. without any large single allocations, total size will be
     276                 :            :     //   64KB -> 128KB -> 256KB -> 512KB -> 1MB, etc
     277                 :            :     //
     278                 :            :     // - If the failed allocation is too large to fit in that size, the new
     279                 :            :     //   heap is made exactly large enough for that allocation. Future growth
     280                 :            :     //   will double the total heap size again.
     281                 :            :     //
     282                 :            :     // - If the new heap won't fit in the available free space, add the largest
     283                 :            :     //   new heap that will fit (this may lead to failed system heap allocations
     284                 :            :     //   elsewhere, but some allocation will likely fail in this circumstance!)
     285                 :            : 
     286                 :            :     // Compute total number of blocks in the current heap.
     287                 :            :     size_t total_blocks = 0;
     288                 :            :     for (mp_state_mem_area_t *area = &MP_STATE_MEM(area);
     289                 :            :          area != NULL;
     290                 :            :          area = NEXT_AREA(area)) {
     291                 :            :         total_blocks += area->gc_alloc_table_byte_len * BLOCKS_PER_ATB;
     292                 :            :     }
     293                 :            : 
     294                 :            :     // Compute bytes needed to build a heap with total_blocks blocks.
     295                 :            :     size_t total_heap =
     296                 :            :         total_blocks / BLOCKS_PER_ATB
     297                 :            :         #if MICROPY_ENABLE_FINALISER
     298                 :            :         + total_blocks / BLOCKS_PER_FTB
     299                 :            :         #endif
     300                 :            :         + total_blocks * BYTES_PER_BLOCK
     301                 :            :         + ALLOC_TABLE_GAP_BYTE
     302                 :            :         + sizeof(mp_state_mem_area_t);
     303                 :            : 
     304                 :            :     // Round up size to the nearest multiple of BYTES_PER_BLOCK.
     305                 :            :     total_heap = (total_heap + BYTES_PER_BLOCK - 1) & (~(BYTES_PER_BLOCK - 1));
     306                 :            : 
     307                 :            :     DEBUG_printf("total_heap " UINT_FMT " bytes\n", total_heap);
     308                 :            : 
     309                 :            :     size_t to_alloc = MIN(avail, MAX(total_heap, needed));
     310                 :            : 
     311                 :            :     mp_state_mem_area_t *new_heap = MP_PLAT_ALLOC_HEAP(to_alloc);
     312                 :            : 
     313                 :            :     DEBUG_printf("MP_PLAT_ALLOC_HEAP " UINT_FMT " = %p\n",
     314                 :            :         to_alloc, new_heap);
     315                 :            : 
     316                 :            :     if (new_heap == NULL) {
     317                 :            :         // This should only fail:
     318                 :            :         // - In a threaded environment if another thread has
     319                 :            :         //   allocated while this function ran.
     320                 :            :         // - If there is a bug in gc_get_max_new_split().
     321                 :            :         return false;
     322                 :            :     }
     323                 :            : 
     324                 :            :     gc_add(new_heap, (void *)new_heap + to_alloc);
     325                 :            : 
     326                 :            :     return true;
     327                 :            : }
     328                 :            : #endif
     329                 :            : 
     330                 :            : #endif
     331                 :            : 
     332                 :        233 : void gc_lock(void) {
     333                 :            :     // This does not need to be atomic or have the GC mutex because:
     334                 :            :     // - each thread has its own gc_lock_depth so there are no races between threads;
     335                 :            :     // - a hard interrupt will only change gc_lock_depth during its execution, and
     336                 :            :     //   upon return will restore the value of gc_lock_depth.
     337                 :        233 :     MP_STATE_THREAD(gc_lock_depth)++;
     338                 :        233 : }
     339                 :            : 
     340                 :        233 : void gc_unlock(void) {
     341                 :            :     // This does not need to be atomic, See comment above in gc_lock.
     342                 :        233 :     MP_STATE_THREAD(gc_lock_depth)--;
     343                 :        233 : }
     344                 :            : 
     345                 :        110 : bool gc_is_locked(void) {
     346                 :        110 :     return MP_STATE_THREAD(gc_lock_depth) != 0;
     347                 :            : }
     348                 :            : 
     349                 :            : #if MICROPY_GC_SPLIT_HEAP
     350                 :            : // Returns the area to which this pointer belongs, or NULL if it isn't
     351                 :            : // allocated on the GC-managed heap.
     352                 :   29686838 : static inline mp_state_mem_area_t *gc_get_ptr_area(const void *ptr) {
     353                 :   29686838 :     if (((uintptr_t)(ptr) & (BYTES_PER_BLOCK - 1)) != 0) {   // must be aligned on a block
     354                 :            :         return NULL;
     355                 :            :     }
     356   [ +  -  +  +  :   58862596 :     for (mp_state_mem_area_t *area = &MP_STATE_MEM(area); area != NULL; area = NEXT_AREA(area)) {
          +  -  +  +  +  
                      + ]
     357   [ +  +  +  +  :   42624875 :         if (ptr >= (void *)area->gc_pool_start   // must be above start of pool
          +  +  +  +  +  
                      + ]
     358   [ -  +  -  +  :    7414844 :             && ptr < (void *)area->gc_pool_end) {   // must be below end of pool
          -  +  +  +  +  
                      + ]
     359                 :            :             return area;
     360                 :            :         }
     361                 :            :     }
     362                 :            :     return NULL;
     363                 :            : }
     364                 :            : #endif
     365                 :            : 
     366                 :            : // ptr should be of type void*
     367                 :            : #define VERIFY_PTR(ptr) ( \
     368                 :            :     ((uintptr_t)(ptr) & (BYTES_PER_BLOCK - 1)) == 0          /* must be aligned on a block */ \
     369                 :            :     && ptr >= (void *)MP_STATE_MEM(area).gc_pool_start      /* must be above start of pool */ \
     370                 :            :     && ptr < (void *)MP_STATE_MEM(area).gc_pool_end         /* must be below end of pool */ \
     371                 :            :     )
     372                 :            : 
     373                 :            : #ifndef TRACE_MARK
     374                 :            : #if DEBUG_PRINT
     375                 :            : #define TRACE_MARK(block, ptr) DEBUG_printf("gc_mark(%p)\n", ptr)
     376                 :            : #else
     377                 :            : #define TRACE_MARK(block, ptr)
     378                 :            : #endif
     379                 :            : #endif
     380                 :            : 
     381                 :            : // Take the given block as the topmost block on the stack. Check all it's
     382                 :            : // children: mark the unmarked child blocks and put those newly marked
     383                 :            : // blocks on the stack. When all children have been checked, pop off the
     384                 :            : // topmost block on the stack and repeat with that one.
     385                 :            : #if MICROPY_GC_SPLIT_HEAP
     386                 :      18365 : static void gc_mark_subtree(mp_state_mem_area_t *area, size_t block)
     387                 :            : #else
     388                 :            : static void gc_mark_subtree(size_t block)
     389                 :            : #endif
     390                 :            : {
     391                 :            :     // Start with the block passed in the argument.
     392                 :      18365 :     size_t sp = 0;
     393                 :    8361627 :     for (;;) {
     394                 :            :         #if !MICROPY_GC_SPLIT_HEAP
     395                 :            :         mp_state_mem_area_t *area = &MP_STATE_MEM(area);
     396                 :            :         #endif
     397                 :            : 
     398                 :            :         // work out number of consecutive blocks in the chain starting with this one
     399                 :    4189996 :         size_t n_blocks = 0;
     400                 :    4315918 :         do {
     401                 :    4315918 :             n_blocks += 1;
     402         [ +  + ]:    4315918 :         } while (ATB_GET_KIND(area, block + n_blocks) == AT_TAIL);
     403                 :            : 
     404                 :            :         // check that the consecutive blocks didn't overflow past the end of the area
     405         [ -  + ]:    4189996 :         assert(area->gc_pool_start + (block + n_blocks) * BYTES_PER_BLOCK <= area->gc_pool_end);
     406                 :            : 
     407                 :            :         // check this block's children
     408                 :    4189996 :         void **ptrs = (void **)PTR_FROM_BLOCK(area, block);
     409         [ +  + ]:   21453668 :         for (size_t i = n_blocks * BYTES_PER_BLOCK / sizeof(void *); i > 0; i--, ptrs++) {
     410                 :   17263672 :             MICROPY_GC_HOOK_LOOP(i);
     411                 :   17263672 :             void *ptr = *ptrs;
     412                 :            :             // If this is a heap pointer that hasn't been marked, mark it and push
     413                 :            :             // it's children to the stack.
     414                 :            :             #if MICROPY_GC_SPLIT_HEAP
     415         [ +  + ]:   17263672 :             mp_state_mem_area_t *ptr_area = gc_get_ptr_area(ptr);
     416         [ +  + ]:   14287140 :             if (!ptr_area) {
     417                 :            :                 // Not a heap-allocated pointer (might even be random data).
     418                 :   13087378 :                 continue;
     419                 :            :             }
     420                 :            :             #else
     421                 :            :             if (!VERIFY_PTR(ptr)) {
     422                 :            :                 continue;
     423                 :            :             }
     424                 :            :             mp_state_mem_area_t *ptr_area = area;
     425                 :            :             #endif
     426                 :    4176294 :             size_t ptr_block = BLOCK_FROM_PTR(ptr_area, ptr);
     427         [ +  + ]:    4176294 :             if (ATB_GET_KIND(ptr_area, ptr_block) != AT_HEAD) {
     428                 :            :                 // This block is already marked.
     429                 :       4381 :                 continue;
     430                 :            :             }
     431                 :            :             // An unmarked head. Mark it, and push it on gc stack.
     432                 :    4171913 :             TRACE_MARK(ptr_block, ptr);
     433                 :    4171913 :             ATB_HEAD_TO_MARK(ptr_area, ptr_block);
     434         [ +  + ]:    4171913 :             if (sp < MICROPY_ALLOC_GC_STACK_SIZE) {
     435                 :    4171631 :                 MP_STATE_MEM(gc_block_stack)[sp] = ptr_block;
     436                 :            :                 #if MICROPY_GC_SPLIT_HEAP
     437                 :    4171631 :                 MP_STATE_MEM(gc_area_stack)[sp] = ptr_area;
     438                 :            :                 #endif
     439                 :    4171631 :                 sp += 1;
     440                 :            :             } else {
     441                 :        282 :                 MP_STATE_MEM(gc_stack_overflow) = 1;
     442                 :            :             }
     443                 :            :         }
     444                 :            : 
     445                 :            :         // Are there any blocks on the stack?
     446         [ +  + ]:    4189996 :         if (sp == 0) {
     447                 :            :             break; // No, stack is empty, we're done.
     448                 :            :         }
     449                 :            : 
     450                 :            :         // pop the next block off the stack
     451                 :    4171631 :         sp -= 1;
     452                 :    4171631 :         block = MP_STATE_MEM(gc_block_stack)[sp];
     453                 :            :         #if MICROPY_GC_SPLIT_HEAP
     454                 :    4171631 :         area = MP_STATE_MEM(gc_area_stack)[sp];
     455                 :            :         #endif
     456                 :            :     }
     457                 :      18365 : }
     458                 :            : 
     459                 :      16051 : static void gc_deal_with_stack_overflow(void) {
     460         [ +  + ]:      16054 :     while (MP_STATE_MEM(gc_stack_overflow)) {
     461                 :          3 :         MP_STATE_MEM(gc_stack_overflow) = 0;
     462                 :            : 
     463                 :            :         // scan entire memory looking for blocks which have been marked but not their children
     464         [ +  + ]:         15 :         for (mp_state_mem_area_t *area = &MP_STATE_MEM(area); area != NULL; area = NEXT_AREA(area)) {
     465         [ +  + ]:     194280 :             for (size_t block = 0; block < area->gc_alloc_table_byte_len * BLOCKS_PER_ATB; block++) {
     466                 :     194268 :                 MICROPY_GC_HOOK_LOOP(block);
     467                 :            :                 // trace (again) if mark bit set
     468         [ +  + ]:     194268 :                 if (ATB_GET_KIND(area, block) == AT_MARK) {
     469                 :            :                     #if MICROPY_GC_SPLIT_HEAP
     470                 :       1470 :                     gc_mark_subtree(area, block);
     471                 :            :                     #else
     472                 :            :                     gc_mark_subtree(block);
     473                 :            :                     #endif
     474                 :            :                 }
     475                 :            :             }
     476                 :            :         }
     477                 :            :     }
     478                 :      16051 : }
     479                 :            : 
     480                 :      16051 : static void gc_sweep(void) {
     481                 :            :     #if MICROPY_PY_GC_COLLECT_RETVAL
     482                 :      16051 :     MP_STATE_MEM(gc_collected) = 0;
     483                 :            :     #endif
     484                 :            :     // free unmarked heads and their tails
     485                 :      16051 :     int free_tail = 0;
     486                 :            :     #if MICROPY_GC_SPLIT_HEAP_AUTO
     487                 :            :     mp_state_mem_area_t *prev_area = NULL;
     488                 :            :     #endif
     489         [ +  + ]:      43391 :     for (mp_state_mem_area_t *area = &MP_STATE_MEM(area); area != NULL; area = NEXT_AREA(area)) {
     490                 :      27340 :         size_t end_block = area->gc_alloc_table_byte_len * BLOCKS_PER_ATB;
     491         [ +  + ]:      27340 :         if (area->gc_last_used_block < end_block) {
     492                 :      27339 :             end_block = area->gc_last_used_block + 1;
     493                 :            :         }
     494                 :            : 
     495                 :      27340 :         size_t last_used_block = 0;
     496                 :            : 
     497         [ +  + ]:    8398284 :         for (size_t block = 0; block < end_block; block++) {
     498                 :    8370944 :             MICROPY_GC_HOOK_LOOP(block);
     499   [ +  +  +  + ]:    8370944 :             switch (ATB_GET_KIND(area, block)) {
     500                 :    2700857 :                 case AT_HEAD:
     501                 :            :                     #if MICROPY_ENABLE_FINALISER
     502         [ +  + ]:    2700857 :                     if (FTB_GET(area, block)) {
     503                 :       4286 :                         mp_obj_base_t *obj = (mp_obj_base_t *)PTR_FROM_BLOCK(area, block);
     504         [ +  - ]:       4286 :                         if (obj->type != NULL) {
     505                 :            :                             // if the object has a type then see if it has a __del__ method
     506                 :       4286 :                             mp_obj_t dest[2];
     507                 :       4286 :                             mp_load_method_maybe(MP_OBJ_FROM_PTR(obj), MP_QSTR___del__, dest);
     508         [ +  - ]:       4286 :                             if (dest[0] != MP_OBJ_NULL) {
     509                 :            :                                 // load_method returned a method, execute it in a protected environment
     510                 :            :                                 #if MICROPY_ENABLE_SCHEDULER
     511                 :       4286 :                                 mp_sched_lock();
     512                 :            :                                 #endif
     513                 :       4286 :                                 mp_call_function_1_protected(dest[0], dest[1]);
     514                 :            :                                 #if MICROPY_ENABLE_SCHEDULER
     515                 :       4286 :                                 mp_sched_unlock();
     516                 :            :                                 #endif
     517                 :            :                             }
     518                 :            :                         }
     519                 :            :                         // clear finaliser flag
     520                 :       4286 :                         FTB_CLEAR(area, block);
     521                 :            :                     }
     522                 :            :                     #endif
     523                 :    2700857 :                     free_tail = 1;
     524                 :    2700857 :                     DEBUG_printf("gc_sweep(%p)\n", (void *)PTR_FROM_BLOCK(area, block));
     525                 :            :                     #if MICROPY_PY_GC_COLLECT_RETVAL
     526                 :    2700857 :                     MP_STATE_MEM(gc_collected)++;
     527                 :            :                     #endif
     528                 :            :                     // fall through to free the head
     529                 :    3656090 :                     MP_FALLTHROUGH
     530                 :            : 
     531                 :     955233 :                 case AT_TAIL:
     532         [ +  + ]:    3656090 :                     if (free_tail) {
     533                 :    3530522 :                         ATB_ANY_TO_FREE(area, block);
     534                 :            :                         #if CLEAR_ON_SWEEP
     535                 :            :                         memset((void *)PTR_FROM_BLOCK(area, block), 0, BYTES_PER_BLOCK);
     536                 :            :                         #endif
     537                 :            :                     } else {
     538                 :            :                         last_used_block = block;
     539                 :            :                     }
     540                 :            :                     break;
     541                 :            : 
     542                 :    4188808 :                 case AT_MARK:
     543                 :    4188808 :                     ATB_MARK_TO_HEAD(area, block);
     544                 :    4188808 :                     free_tail = 0;
     545                 :    4188808 :                     last_used_block = block;
     546                 :    4188808 :                     break;
     547                 :            :             }
     548                 :            :         }
     549                 :            : 
     550                 :      27340 :         area->gc_last_used_block = last_used_block;
     551                 :            : 
     552                 :            :         #if MICROPY_GC_SPLIT_HEAP_AUTO
     553                 :            :         // Free any empty area, aside from the first one
     554                 :            :         if (last_used_block == 0 && prev_area != NULL) {
     555                 :            :             DEBUG_printf("gc_sweep free empty area %p\n", area);
     556                 :            :             NEXT_AREA(prev_area) = NEXT_AREA(area);
     557                 :            :             MP_PLAT_FREE_HEAP(area);
     558                 :            :             area = prev_area;
     559                 :            :         }
     560                 :            :         prev_area = area;
     561                 :            :         #endif
     562                 :            :     }
     563                 :      16051 : }
     564                 :            : 
     565                 :      12723 : void gc_collect_start(void) {
     566                 :      12723 :     GC_ENTER();
     567                 :      12723 :     MP_STATE_THREAD(gc_lock_depth)++;
     568                 :            :     #if MICROPY_GC_ALLOC_THRESHOLD
     569                 :      12723 :     MP_STATE_MEM(gc_alloc_amount) = 0;
     570                 :            :     #endif
     571                 :      12723 :     MP_STATE_MEM(gc_stack_overflow) = 0;
     572                 :            : 
     573                 :            :     // Trace root pointers.  This relies on the root pointers being organised
     574                 :            :     // correctly in the mp_state_ctx structure.  We scan nlr_top, dict_locals,
     575                 :            :     // dict_globals, then the root pointer section of mp_state_vm.
     576                 :      12723 :     void **ptrs = (void **)(void *)&mp_state_ctx;
     577                 :      12723 :     size_t root_start = offsetof(mp_state_ctx_t, thread.dict_locals);
     578                 :      12723 :     size_t root_end = offsetof(mp_state_ctx_t, vm.qstr_last_chunk);
     579                 :      12723 :     gc_collect_root(ptrs + root_start / sizeof(void *), (root_end - root_start) / sizeof(void *));
     580                 :            : 
     581                 :            :     #if MICROPY_ENABLE_PYSTACK
     582                 :            :     // Trace root pointers from the Python stack.
     583                 :            :     ptrs = (void **)(void *)MP_STATE_THREAD(pystack_start);
     584                 :            :     gc_collect_root(ptrs, (MP_STATE_THREAD(pystack_cur) - MP_STATE_THREAD(pystack_start)) / sizeof(void *));
     585                 :            :     #endif
     586                 :      12723 : }
     587                 :            : 
     588                 :            : // Address sanitizer needs to know that the access to ptrs[i] must always be
     589                 :            : // considered OK, even if it's a load from an address that would normally be
     590                 :            : // prohibited (due to being undefined, in a red zone, etc).
     591                 :            : #if defined(__GNUC__) && (__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 8))
     592                 :            : __attribute__((no_sanitize_address))
     593                 :            : #endif
     594                 :   11401827 : static void *gc_get_ptr(void **ptrs, int i) {
     595                 :            :     #if MICROPY_DEBUG_VALGRIND
     596                 :            :     if (!VALGRIND_CHECK_MEM_IS_ADDRESSABLE(&ptrs[i], sizeof(*ptrs))) {
     597                 :            :         return NULL;
     598                 :            :     }
     599                 :            :     #endif
     600                 :   11401827 :     return ptrs[i];
     601                 :            : }
     602                 :            : 
     603                 :      45228 : void gc_collect_root(void **ptrs, size_t len) {
     604                 :            :     #if !MICROPY_GC_SPLIT_HEAP
     605                 :            :     mp_state_mem_area_t *area = &MP_STATE_MEM(area);
     606                 :            :     #endif
     607         [ +  + ]:   11447055 :     for (size_t i = 0; i < len; i++) {
     608                 :   11401827 :         MICROPY_GC_HOOK_LOOP(i);
     609                 :   11401827 :         void *ptr = gc_get_ptr(ptrs, i);
     610                 :            :         #if MICROPY_GC_SPLIT_HEAP
     611         [ +  + ]:   11401827 :         mp_state_mem_area_t *area = gc_get_ptr_area(ptr);
     612         [ +  + ]:    6151147 :         if (!area) {
     613                 :   11377553 :             continue;
     614                 :            :         }
     615                 :            :         #else
     616                 :            :         if (!VERIFY_PTR(ptr)) {
     617                 :            :             continue;
     618                 :            :         }
     619                 :            :         #endif
     620                 :      24274 :         size_t block = BLOCK_FROM_PTR(area, ptr);
     621         [ +  + ]:      24274 :         if (ATB_GET_KIND(area, block) == AT_HEAD) {
     622                 :            :             // An unmarked head: mark it, and mark all its children
     623                 :      16895 :             ATB_HEAD_TO_MARK(area, block);
     624                 :            :             #if MICROPY_GC_SPLIT_HEAP
     625                 :      16895 :             gc_mark_subtree(area, block);
     626                 :            :             #else
     627                 :            :             gc_mark_subtree(block);
     628                 :            :             #endif
     629                 :            :         }
     630                 :            :     }
     631                 :      45228 : }
     632                 :            : 
     633                 :      16051 : void gc_collect_end(void) {
     634                 :      16051 :     gc_deal_with_stack_overflow();
     635                 :      16051 :     gc_sweep();
     636                 :            :     #if MICROPY_GC_SPLIT_HEAP
     637                 :      16051 :     MP_STATE_MEM(gc_last_free_area) = &MP_STATE_MEM(area);
     638                 :            :     #endif
     639         [ +  + ]:      43391 :     for (mp_state_mem_area_t *area = &MP_STATE_MEM(area); area != NULL; area = NEXT_AREA(area)) {
     640                 :      27340 :         area->gc_last_free_atb_index = 0;
     641                 :            :     }
     642                 :      16051 :     MP_STATE_THREAD(gc_lock_depth)--;
     643                 :      16051 :     GC_EXIT();
     644                 :      16051 : }
     645                 :            : 
     646                 :       3328 : void gc_sweep_all(void) {
     647                 :       3328 :     GC_ENTER();
     648                 :       3328 :     MP_STATE_THREAD(gc_lock_depth)++;
     649                 :       3328 :     MP_STATE_MEM(gc_stack_overflow) = 0;
     650                 :       3328 :     gc_collect_end();
     651                 :       3328 : }
     652                 :            : 
     653                 :         26 : void gc_info(gc_info_t *info) {
     654                 :         26 :     GC_ENTER();
     655                 :         26 :     info->total = 0;
     656                 :         26 :     info->used = 0;
     657                 :         26 :     info->free = 0;
     658                 :         26 :     info->max_free = 0;
     659                 :         26 :     info->num_1block = 0;
     660                 :         26 :     info->num_2block = 0;
     661                 :         26 :     info->max_block = 0;
     662         [ +  + ]:        130 :     for (mp_state_mem_area_t *area = &MP_STATE_MEM(area); area != NULL; area = NEXT_AREA(area)) {
     663                 :        104 :         bool finish = false;
     664                 :        104 :         info->total += area->gc_pool_end - area->gc_pool_start;
     665         [ +  + ]:    1683760 :         for (size_t block = 0, len = 0, len_free = 0; !finish;) {
     666                 :    1683656 :             MICROPY_GC_HOOK_LOOP(block);
     667                 :    1683656 :             size_t kind = ATB_GET_KIND(area, block);
     668   [ +  +  +  - ]:    1683656 :             switch (kind) {
     669                 :    1682304 :                 case AT_FREE:
     670                 :    1682304 :                     info->free += 1;
     671                 :    1682304 :                     len_free += 1;
     672                 :    1682304 :                     len = 0;
     673                 :    1682304 :                     break;
     674                 :            : 
     675                 :        628 :                 case AT_HEAD:
     676                 :        628 :                     info->used += 1;
     677                 :        628 :                     len = 1;
     678                 :        628 :                     break;
     679                 :            : 
     680                 :        724 :                 case AT_TAIL:
     681                 :        724 :                     info->used += 1;
     682                 :        724 :                     len += 1;
     683                 :        724 :                     break;
     684                 :            : 
     685                 :            :                 case AT_MARK:
     686                 :            :                     // shouldn't happen
     687                 :            :                     break;
     688                 :            :             }
     689                 :            : 
     690                 :    1683656 :             block++;
     691                 :    1683656 :             finish = (block == area->gc_alloc_table_byte_len * BLOCKS_PER_ATB);
     692                 :            :             // Get next block type if possible
     693         [ +  + ]:    1683656 :             if (!finish) {
     694                 :    1683552 :                 kind = ATB_GET_KIND(area, block);
     695                 :            :             }
     696                 :            : 
     697   [ +  +  +  + ]:    1683656 :             if (finish || kind == AT_FREE || kind == AT_HEAD) {
     698         [ +  + ]:    1682932 :                 if (len == 1) {
     699                 :        402 :                     info->num_1block += 1;
     700         [ +  + ]:    1682530 :                 } else if (len == 2) {
     701                 :         94 :                     info->num_2block += 1;
     702                 :            :                 }
     703         [ +  + ]:    1682932 :                 if (len > info->max_block) {
     704                 :         82 :                     info->max_block = len;
     705                 :            :                 }
     706         [ +  + ]:    1682932 :                 if (finish || kind == AT_HEAD) {
     707         [ +  + ]:        706 :                     if (len_free > info->max_free) {
     708                 :        124 :                         info->max_free = len_free;
     709                 :            :                     }
     710                 :            :                     len_free = 0;
     711                 :            :                 }
     712                 :            :             }
     713                 :            :         }
     714                 :            :     }
     715                 :            : 
     716                 :         26 :     info->used *= BYTES_PER_BLOCK;
     717                 :         26 :     info->free *= BYTES_PER_BLOCK;
     718                 :            : 
     719                 :            :     #if MICROPY_GC_SPLIT_HEAP_AUTO
     720                 :            :     info->max_new_split = gc_get_max_new_split();
     721                 :            :     #endif
     722                 :            : 
     723                 :         26 :     GC_EXIT();
     724                 :         26 : }
     725                 :            : 
     726                 :    3753839 : void *gc_alloc(size_t n_bytes, unsigned int alloc_flags) {
     727                 :    3753839 :     bool has_finaliser = alloc_flags & GC_ALLOC_FLAG_HAS_FINALISER;
     728                 :    3753839 :     size_t n_blocks = ((n_bytes + BYTES_PER_BLOCK - 1) & (~(BYTES_PER_BLOCK - 1))) / BYTES_PER_BLOCK;
     729                 :    3753839 :     DEBUG_printf("gc_alloc(" UINT_FMT " bytes -> " UINT_FMT " blocks)\n", n_bytes, n_blocks);
     730                 :            : 
     731                 :            :     // check for 0 allocation
     732         [ +  + ]:    3753839 :     if (n_blocks == 0) {
     733                 :            :         return NULL;
     734                 :            :     }
     735                 :            : 
     736                 :            :     // check if GC is locked
     737         [ +  + ]:    3749166 :     if (MP_STATE_THREAD(gc_lock_depth) > 0) {
     738                 :            :         return NULL;
     739                 :            :     }
     740                 :            : 
     741                 :    3748789 :     GC_ENTER();
     742                 :            : 
     743                 :    3750242 :     mp_state_mem_area_t *area;
     744                 :    3750242 :     size_t i;
     745                 :    3750242 :     size_t end_block;
     746                 :    3750242 :     size_t start_block;
     747                 :    3750242 :     size_t n_free;
     748                 :    3750242 :     int collected = !MP_STATE_MEM(gc_auto_collect_enabled);
     749                 :            :     #if MICROPY_GC_SPLIT_HEAP_AUTO
     750                 :            :     bool added = false;
     751                 :            :     #endif
     752                 :            : 
     753                 :            :     #if MICROPY_GC_ALLOC_THRESHOLD
     754   [ +  +  +  + ]:    3750242 :     if (!collected && MP_STATE_MEM(gc_alloc_amount) >= MP_STATE_MEM(gc_alloc_threshold)) {
     755                 :         24 :         GC_EXIT();
     756                 :         24 :         gc_collect();
     757                 :         24 :         collected = 1;
     758                 :         24 :         GC_ENTER();
     759                 :            :     }
     760                 :            :     #endif
     761                 :            : 
     762                 :    3766792 :     for (;;) {
     763                 :            : 
     764                 :            :         #if MICROPY_GC_SPLIT_HEAP
     765                 :    3758517 :         area = MP_STATE_MEM(gc_last_free_area);
     766                 :            :         #else
     767                 :            :         area = &MP_STATE_MEM(area);
     768                 :            :         #endif
     769                 :            : 
     770                 :            :         // look for a run of n_blocks available blocks
     771         [ +  + ]:    3784405 :         for (; area != NULL; area = NEXT_AREA(area), i = 0) {
     772                 :    3771989 :             n_free = 0;
     773         [ +  + ]:  158387029 :             for (i = area->gc_last_free_atb_index; i < area->gc_alloc_table_byte_len; i++) {
     774                 :  158361141 :                 MICROPY_GC_HOOK_LOOP(i);
     775                 :  158361141 :                 byte a = area->gc_alloc_table_start[i];
     776                 :            :                 // *FORMAT-OFF*
     777   [ +  +  +  + ]:  158361141 :                 if (ATB_0_IS_FREE(a)) { if (++n_free >= n_blocks) { i = i * BLOCKS_PER_ATB + 0; goto found; } } else { n_free = 0; }
     778   [ +  +  +  + ]:  157425195 :                 if (ATB_1_IS_FREE(a)) { if (++n_free >= n_blocks) { i = i * BLOCKS_PER_ATB + 1; goto found; } } else { n_free = 0; }
     779   [ +  +  +  + ]:  156483514 :                 if (ATB_2_IS_FREE(a)) { if (++n_free >= n_blocks) { i = i * BLOCKS_PER_ATB + 2; goto found; } } else { n_free = 0; }
     780   [ +  +  +  + ]:  155554896 :                 if (ATB_3_IS_FREE(a)) { if (++n_free >= n_blocks) { i = i * BLOCKS_PER_ATB + 3; goto found; } } else { n_free = 0; }
     781                 :            :                 // *FORMAT-ON*
     782                 :            :             }
     783                 :            : 
     784                 :            :             // No free blocks found on this heap. Mark this heap as
     785                 :            :             // filled, so we won't try to find free space here again until
     786                 :            :             // space is freed.
     787                 :            :             #if MICROPY_GC_SPLIT_HEAP
     788         [ +  + ]:      25888 :             if (n_blocks == 1) {
     789                 :      13160 :                 area->gc_last_free_atb_index = (i + 1) / BLOCKS_PER_ATB; // or (size_t)-1
     790                 :            :             }
     791                 :            :             #endif
     792                 :            :         }
     793                 :            : 
     794                 :      12416 :         GC_EXIT();
     795                 :            :         // nothing found!
     796         [ +  + ]:      12416 :         if (collected) {
     797                 :            :             #if MICROPY_GC_SPLIT_HEAP_AUTO
     798                 :            :             if (!added && gc_try_add_heap(n_bytes)) {
     799                 :            :                 added = true;
     800                 :            :                 continue;
     801                 :            :             }
     802                 :            :             #endif
     803                 :            :             return NULL;
     804                 :            :         }
     805                 :       8275 :         DEBUG_printf("gc_alloc(" UINT_FMT "): no free mem, triggering GC\n", n_bytes);
     806                 :       8275 :         gc_collect();
     807                 :       8275 :         collected = 1;
     808                 :       8275 :         GC_ENTER();
     809                 :            :     }
     810                 :            : 
     811                 :            :     // found, ending at block i inclusive
     812                 :    3746101 : found:
     813                 :            :     // get starting and end blocks, both inclusive
     814                 :    3746101 :     end_block = i;
     815                 :    3746101 :     start_block = i - n_free + 1;
     816                 :            : 
     817                 :            :     // Set last free ATB index to block after last block we found, for start of
     818                 :            :     // next scan.  To reduce fragmentation, we only do this if we were looking
     819                 :            :     // for a single free block, which guarantees that there are no free blocks
     820                 :            :     // before this one.  Also, whenever we free or shink a block we must check
     821                 :            :     // if this index needs adjusting (see gc_realloc and gc_free).
     822         [ +  + ]:    3746101 :     if (n_free == 1) {
     823                 :            :         #if MICROPY_GC_SPLIT_HEAP
     824                 :    3086696 :         MP_STATE_MEM(gc_last_free_area) = area;
     825                 :            :         #endif
     826                 :    3086696 :         area->gc_last_free_atb_index = (i + 1) / BLOCKS_PER_ATB;
     827                 :            :     }
     828                 :            : 
     829                 :    3746101 :     area->gc_last_used_block = MAX(area->gc_last_used_block, end_block);
     830                 :            : 
     831                 :            :     // mark first block as used head
     832                 :    3746101 :     ATB_FREE_TO_HEAD(area, start_block);
     833                 :            : 
     834                 :            :     // mark rest of blocks as used tail
     835                 :            :     // TODO for a run of many blocks can make this more efficient
     836         [ +  + ]:    6416982 :     for (size_t bl = start_block + 1; bl <= end_block; bl++) {
     837                 :    2670881 :         ATB_FREE_TO_TAIL(area, bl);
     838                 :            :     }
     839                 :            : 
     840                 :            :     // get pointer to first block
     841                 :            :     // we must create this pointer before unlocking the GC so a collection can find it
     842                 :    3746101 :     void *ret_ptr = (void *)(area->gc_pool_start + start_block * BYTES_PER_BLOCK);
     843                 :    3746101 :     DEBUG_printf("gc_alloc(%p)\n", ret_ptr);
     844                 :            : 
     845                 :            :     #if MICROPY_GC_ALLOC_THRESHOLD
     846                 :    3746101 :     MP_STATE_MEM(gc_alloc_amount) += n_blocks;
     847                 :            :     #endif
     848                 :            : 
     849                 :    3746101 :     GC_EXIT();
     850                 :            : 
     851                 :            :     #if MICROPY_GC_CONSERVATIVE_CLEAR
     852                 :            :     // be conservative and zero out all the newly allocated blocks
     853                 :    3745975 :     memset((byte *)ret_ptr, 0, (end_block - start_block + 1) * BYTES_PER_BLOCK);
     854                 :            :     #else
     855                 :            :     // zero out the additional bytes of the newly allocated blocks
     856                 :            :     // This is needed because the blocks may have previously held pointers
     857                 :            :     // to the heap and will not be set to something else if the caller
     858                 :            :     // doesn't actually use the entire block.  As such they will continue
     859                 :            :     // to point to the heap and may prevent other blocks from being reclaimed.
     860                 :            :     memset((byte *)ret_ptr + n_bytes, 0, (end_block - start_block + 1) * BYTES_PER_BLOCK - n_bytes);
     861                 :            :     #endif
     862                 :            : 
     863                 :            :     #if MICROPY_ENABLE_FINALISER
     864         [ +  + ]:    3745975 :     if (has_finaliser) {
     865                 :            :         // clear type pointer in case it is never set
     866                 :       8388 :         ((mp_obj_base_t *)ret_ptr)->type = NULL;
     867                 :            :         // set mp_obj flag only if it has a finaliser
     868                 :       8388 :         GC_ENTER();
     869                 :       8388 :         FTB_SET(area, start_block);
     870                 :       8388 :         GC_EXIT();
     871                 :            :     }
     872                 :            :     #else
     873                 :            :     (void)has_finaliser;
     874                 :            :     #endif
     875                 :            : 
     876                 :            :     #if EXTENSIVE_HEAP_PROFILING
     877                 :            :     gc_dump_alloc_table(&mp_plat_print);
     878                 :            :     #endif
     879                 :            : 
     880                 :            :     return ret_ptr;
     881                 :            : }
     882                 :            : 
     883                 :            : /*
     884                 :            : void *gc_alloc(mp_uint_t n_bytes) {
     885                 :            :     return _gc_alloc(n_bytes, false);
     886                 :            : }
     887                 :            : 
     888                 :            : void *gc_alloc_with_finaliser(mp_uint_t n_bytes) {
     889                 :            :     return _gc_alloc(n_bytes, true);
     890                 :            : }
     891                 :            : */
     892                 :            : 
     893                 :            : // force the freeing of a piece of memory
     894                 :            : // TODO: freeing here does not call finaliser
     895                 :     548414 : void gc_free(void *ptr) {
     896         [ +  - ]:     548414 :     if (MP_STATE_THREAD(gc_lock_depth) > 0) {
     897                 :            :         // Cannot free while the GC is locked. However free is an optimisation
     898                 :            :         // to reclaim the memory immediately, this means it will now be left
     899                 :            :         // until the next collection.
     900                 :            :         return;
     901                 :            :     }
     902                 :            : 
     903                 :     548403 :     GC_ENTER();
     904                 :            : 
     905                 :     548541 :     DEBUG_printf("gc_free(%p)\n", ptr);
     906                 :            : 
     907         [ +  + ]:     548541 :     if (ptr == NULL) {
     908                 :            :         // free(NULL) is a no-op
     909                 :      11303 :         GC_EXIT();
     910                 :      11303 :         return;
     911                 :            :     }
     912                 :            : 
     913                 :            :     // get the GC block number corresponding to this pointer
     914                 :     537238 :     mp_state_mem_area_t *area;
     915                 :            :     #if MICROPY_GC_SPLIT_HEAP
     916         [ +  - ]:     537238 :     area = gc_get_ptr_area(ptr);
     917         [ -  + ]:     537238 :     assert(area);
     918                 :            :     #else
     919                 :            :     assert(VERIFY_PTR(ptr));
     920                 :            :     area = &MP_STATE_MEM(area);
     921                 :            :     #endif
     922                 :            : 
     923                 :     537238 :     size_t block = BLOCK_FROM_PTR(area, ptr);
     924         [ -  + ]:     537238 :     assert(ATB_GET_KIND(area, block) == AT_HEAD);
     925                 :            : 
     926                 :            :     #if MICROPY_ENABLE_FINALISER
     927                 :     537238 :     FTB_CLEAR(area, block);
     928                 :            :     #endif
     929                 :            : 
     930                 :            :     #if MICROPY_GC_SPLIT_HEAP
     931         [ +  + ]:     537238 :     if (MP_STATE_MEM(gc_last_free_area) != area) {
     932                 :            :         // We freed something but it isn't the current area. Reset the
     933                 :            :         // last free area to the start for a rescan. Note that this won't
     934                 :            :         // give much of a performance hit, since areas that are completely
     935                 :            :         // filled will likely be skipped (the gc_last_free_atb_index
     936                 :            :         // points to the last block).
     937                 :            :         // The reason why this is necessary is because it is not possible
     938                 :            :         // to see which area came first (like it is possible to adjust
     939                 :            :         // gc_last_free_atb_index based on whether the freed block is
     940                 :            :         // before the last free block).
     941                 :        617 :         MP_STATE_MEM(gc_last_free_area) = &MP_STATE_MEM(area);
     942                 :            :     }
     943                 :            :     #endif
     944                 :            : 
     945                 :            :     // set the last_free pointer to this block if it's earlier in the heap
     946         [ +  + ]:     537238 :     if (block / BLOCKS_PER_ATB < area->gc_last_free_atb_index) {
     947                 :      91446 :         area->gc_last_free_atb_index = block / BLOCKS_PER_ATB;
     948                 :            :     }
     949                 :            : 
     950                 :            :     // free head and all of its tail blocks
     951                 :    2590770 :     do {
     952                 :    2590770 :         ATB_ANY_TO_FREE(area, block);
     953                 :    2590770 :         block += 1;
     954         [ +  + ]:    2590770 :     } while (ATB_GET_KIND(area, block) == AT_TAIL);
     955                 :            : 
     956                 :     537238 :     GC_EXIT();
     957                 :            : 
     958                 :            :     #if EXTENSIVE_HEAP_PROFILING
     959                 :            :     gc_dump_alloc_table(&mp_plat_print);
     960                 :            :     #endif
     961                 :            : }
     962                 :            : 
     963                 :         26 : size_t gc_nbytes(const void *ptr) {
     964                 :         26 :     GC_ENTER();
     965                 :            : 
     966                 :         26 :     mp_state_mem_area_t *area;
     967                 :            :     #if MICROPY_GC_SPLIT_HEAP
     968         [ +  - ]:         26 :     area = gc_get_ptr_area(ptr);
     969                 :            :     #else
     970                 :            :     if (VERIFY_PTR(ptr)) {
     971                 :            :         area = &MP_STATE_MEM(area);
     972                 :            :     } else {
     973                 :            :         area = NULL;
     974                 :            :     }
     975                 :            :     #endif
     976                 :            : 
     977         [ +  + ]:         26 :     if (area) {
     978                 :         24 :         size_t block = BLOCK_FROM_PTR(area, ptr);
     979         [ +  - ]:         24 :         if (ATB_GET_KIND(area, block) == AT_HEAD) {
     980                 :            :             // work out number of consecutive blocks in the chain starting with this on
     981                 :            :             size_t n_blocks = 0;
     982                 :        152 :             do {
     983                 :        152 :                 n_blocks += 1;
     984         [ +  + ]:        152 :             } while (ATB_GET_KIND(area, block + n_blocks) == AT_TAIL);
     985                 :         24 :             GC_EXIT();
     986                 :         24 :             return n_blocks * BYTES_PER_BLOCK;
     987                 :            :         }
     988                 :            :     }
     989                 :            : 
     990                 :            :     // invalid pointer
     991                 :          2 :     GC_EXIT();
     992                 :          2 :     return 0;
     993                 :            : }
     994                 :            : 
     995                 :            : #if 0
     996                 :            : // old, simple realloc that didn't expand memory in place
     997                 :            : void *gc_realloc(void *ptr, mp_uint_t n_bytes) {
     998                 :            :     mp_uint_t n_existing = gc_nbytes(ptr);
     999                 :            :     if (n_bytes <= n_existing) {
    1000                 :            :         return ptr;
    1001                 :            :     } else {
    1002                 :            :         bool has_finaliser;
    1003                 :            :         if (ptr == NULL) {
    1004                 :            :             has_finaliser = false;
    1005                 :            :         } else {
    1006                 :            :             #if MICROPY_ENABLE_FINALISER
    1007                 :            :             has_finaliser = FTB_GET(BLOCK_FROM_PTR((mp_uint_t)ptr));
    1008                 :            :             #else
    1009                 :            :             has_finaliser = false;
    1010                 :            :             #endif
    1011                 :            :         }
    1012                 :            :         void *ptr2 = gc_alloc(n_bytes, has_finaliser);
    1013                 :            :         if (ptr2 == NULL) {
    1014                 :            :             return ptr2;
    1015                 :            :         }
    1016                 :            :         memcpy(ptr2, ptr, n_existing);
    1017                 :            :         gc_free(ptr);
    1018                 :            :         return ptr2;
    1019                 :            :     }
    1020                 :            : }
    1021                 :            : 
    1022                 :            : #else // Alternative gc_realloc impl
    1023                 :            : 
    1024                 :     525497 : void *gc_realloc(void *ptr_in, size_t n_bytes, bool allow_move) {
    1025                 :            :     // check for pure allocation
    1026         [ +  + ]:     525497 :     if (ptr_in == NULL) {
    1027                 :      41395 :         return gc_alloc(n_bytes, false);
    1028                 :            :     }
    1029                 :            : 
    1030                 :            :     // check for pure free
    1031         [ +  + ]:     484102 :     if (n_bytes == 0) {
    1032                 :          2 :         gc_free(ptr_in);
    1033                 :          2 :         return NULL;
    1034                 :            :     }
    1035                 :            : 
    1036         [ +  + ]:     484100 :     if (MP_STATE_THREAD(gc_lock_depth) > 0) {
    1037                 :            :         return NULL;
    1038                 :            :     }
    1039                 :            : 
    1040                 :     484072 :     void *ptr = ptr_in;
    1041                 :            : 
    1042                 :     484072 :     GC_ENTER();
    1043                 :            : 
    1044                 :            :     // get the GC block number corresponding to this pointer
    1045                 :     484075 :     mp_state_mem_area_t *area;
    1046                 :            :     #if MICROPY_GC_SPLIT_HEAP
    1047         [ +  - ]:     484075 :     area = gc_get_ptr_area(ptr);
    1048         [ -  + ]:     484075 :     assert(area);
    1049                 :            :     #else
    1050                 :            :     assert(VERIFY_PTR(ptr));
    1051                 :            :     area = &MP_STATE_MEM(area);
    1052                 :            :     #endif
    1053                 :     484075 :     size_t block = BLOCK_FROM_PTR(area, ptr);
    1054         [ -  + ]:     484075 :     assert(ATB_GET_KIND(area, block) == AT_HEAD);
    1055                 :            : 
    1056                 :            :     // compute number of new blocks that are requested
    1057                 :     484075 :     size_t new_blocks = (n_bytes + BYTES_PER_BLOCK - 1) / BYTES_PER_BLOCK;
    1058                 :            : 
    1059                 :            :     // Get the total number of consecutive blocks that are already allocated to
    1060                 :            :     // this chunk of memory, and then count the number of free blocks following
    1061                 :            :     // it.  Stop if we reach the end of the heap, or if we find enough extra
    1062                 :            :     // free blocks to satisfy the realloc.  Note that we need to compute the
    1063                 :            :     // total size of the existing memory chunk so we can correctly and
    1064                 :            :     // efficiently shrink it (see below for shrinking code).
    1065                 :     484075 :     size_t n_free = 0;
    1066                 :     484075 :     size_t n_blocks = 1; // counting HEAD block
    1067                 :     484075 :     size_t max_block = area->gc_alloc_table_byte_len * BLOCKS_PER_ATB;
    1068         [ +  + ]:    9269014 :     for (size_t bl = block + n_blocks; bl < max_block; bl++) {
    1069                 :    9268986 :         byte block_type = ATB_GET_KIND(area, bl);
    1070         [ +  + ]:    9268986 :         if (block_type == AT_TAIL) {
    1071                 :    8651885 :             n_blocks++;
    1072                 :    8651885 :             continue;
    1073                 :            :         }
    1074         [ +  + ]:     617101 :         if (block_type == AT_FREE) {
    1075                 :     546204 :             n_free++;
    1076         [ +  + ]:     546204 :             if (n_blocks + n_free >= new_blocks) {
    1077                 :            :                 // stop as soon as we find enough blocks for n_bytes
    1078                 :            :                 break;
    1079                 :            :             }
    1080                 :     133054 :             continue;
    1081                 :            :         }
    1082                 :            :         break;
    1083                 :            :     }
    1084                 :            : 
    1085                 :            :     // return original ptr if it already has the requested number of blocks
    1086         [ +  + ]:     484075 :     if (new_blocks == n_blocks) {
    1087                 :     266133 :         GC_EXIT();
    1088                 :     266133 :         return ptr_in;
    1089                 :            :     }
    1090                 :            : 
    1091                 :            :     // check if we can shrink the allocated area
    1092         [ +  + ]:     217942 :     if (new_blocks < n_blocks) {
    1093                 :            :         // free unneeded tail blocks
    1094         [ +  + ]:      50729 :         for (size_t bl = block + new_blocks, count = n_blocks - new_blocks; count > 0; bl++, count--) {
    1095                 :      26409 :             ATB_ANY_TO_FREE(area, bl);
    1096                 :            :         }
    1097                 :            : 
    1098                 :            :         #if MICROPY_GC_SPLIT_HEAP
    1099         [ +  + ]:      24320 :         if (MP_STATE_MEM(gc_last_free_area) != area) {
    1100                 :            :             // See comment in gc_free.
    1101                 :         15 :             MP_STATE_MEM(gc_last_free_area) = &MP_STATE_MEM(area);
    1102                 :            :         }
    1103                 :            :         #endif
    1104                 :            : 
    1105                 :            :         // set the last_free pointer to end of this block if it's earlier in the heap
    1106         [ +  + ]:      24320 :         if ((block + new_blocks) / BLOCKS_PER_ATB < area->gc_last_free_atb_index) {
    1107                 :        895 :             area->gc_last_free_atb_index = (block + new_blocks) / BLOCKS_PER_ATB;
    1108                 :            :         }
    1109                 :            : 
    1110                 :      24320 :         GC_EXIT();
    1111                 :            : 
    1112                 :            :         #if EXTENSIVE_HEAP_PROFILING
    1113                 :            :         gc_dump_alloc_table(&mp_plat_print);
    1114                 :            :         #endif
    1115                 :            : 
    1116                 :      24320 :         return ptr_in;
    1117                 :            :     }
    1118                 :            : 
    1119                 :            :     // check if we can expand in place
    1120         [ +  + ]:     193622 :     if (new_blocks <= n_blocks + n_free) {
    1121                 :            :         // mark few more blocks as used tail
    1122                 :     161095 :         size_t end_block = block + new_blocks;
    1123         [ +  + ]:     399896 :         for (size_t bl = block + n_blocks; bl < end_block; bl++) {
    1124         [ -  + ]:     238801 :             assert(ATB_GET_KIND(area, bl) == AT_FREE);
    1125                 :     238801 :             ATB_FREE_TO_TAIL(area, bl);
    1126                 :            :         }
    1127                 :            : 
    1128                 :     161095 :         area->gc_last_used_block = MAX(area->gc_last_used_block, end_block);
    1129                 :            : 
    1130                 :     161095 :         GC_EXIT();
    1131                 :            : 
    1132                 :            :         #if MICROPY_GC_CONSERVATIVE_CLEAR
    1133                 :            :         // be conservative and zero out all the newly allocated blocks
    1134                 :     161095 :         memset((byte *)ptr_in + n_blocks * BYTES_PER_BLOCK, 0, (new_blocks - n_blocks) * BYTES_PER_BLOCK);
    1135                 :            :         #else
    1136                 :            :         // zero out the additional bytes of the newly allocated blocks (see comment above in gc_alloc)
    1137                 :            :         memset((byte *)ptr_in + n_bytes, 0, new_blocks * BYTES_PER_BLOCK - n_bytes);
    1138                 :            :         #endif
    1139                 :            : 
    1140                 :            :         #if EXTENSIVE_HEAP_PROFILING
    1141                 :            :         gc_dump_alloc_table(&mp_plat_print);
    1142                 :            :         #endif
    1143                 :            : 
    1144                 :     161095 :         return ptr_in;
    1145                 :            :     }
    1146                 :            : 
    1147                 :            :     #if MICROPY_ENABLE_FINALISER
    1148                 :      32527 :     bool ftb_state = FTB_GET(area, block);
    1149                 :            :     #else
    1150                 :            :     bool ftb_state = false;
    1151                 :            :     #endif
    1152                 :            : 
    1153                 :      32527 :     GC_EXIT();
    1154                 :            : 
    1155         [ +  + ]:      32527 :     if (!allow_move) {
    1156                 :            :         // not allowed to move memory block so return failure
    1157                 :            :         return NULL;
    1158                 :            :     }
    1159                 :            : 
    1160                 :            :     // can't resize inplace; try to find a new contiguous chain
    1161                 :      20412 :     void *ptr_out = gc_alloc(n_bytes, ftb_state);
    1162                 :            : 
    1163                 :            :     // check that the alloc succeeded
    1164         [ +  + ]:      20412 :     if (ptr_out == NULL) {
    1165                 :            :         return NULL;
    1166                 :            :     }
    1167                 :            : 
    1168                 :      20404 :     DEBUG_printf("gc_realloc(%p -> %p)\n", ptr_in, ptr_out);
    1169                 :      20404 :     memcpy(ptr_out, ptr_in, n_blocks * BYTES_PER_BLOCK);
    1170                 :      20404 :     gc_free(ptr_in);
    1171                 :      20404 :     return ptr_out;
    1172                 :            : }
    1173                 :            : #endif // Alternative gc_realloc impl
    1174                 :            : 
    1175                 :         18 : void gc_dump_info(const mp_print_t *print) {
    1176                 :         18 :     gc_info_t info;
    1177                 :         18 :     gc_info(&info);
    1178                 :         18 :     mp_printf(print, "GC: total: %u, used: %u, free: %u",
    1179                 :         18 :         (uint)info.total, (uint)info.used, (uint)info.free);
    1180                 :            :     #if MICROPY_GC_SPLIT_HEAP_AUTO
    1181                 :            :     mp_printf(print, ", max new split: %u", (uint)info.max_new_split);
    1182                 :            :     #endif
    1183                 :         18 :     mp_printf(print, "\n No. of 1-blocks: %u, 2-blocks: %u, max blk sz: %u, max free sz: %u\n",
    1184                 :         18 :         (uint)info.num_1block, (uint)info.num_2block, (uint)info.max_block, (uint)info.max_free);
    1185                 :         18 : }
    1186                 :            : 
    1187                 :          4 : void gc_dump_alloc_table(const mp_print_t *print) {
    1188                 :          4 :     GC_ENTER();
    1189                 :          4 :     static const size_t DUMP_BYTES_PER_LINE = 64;
    1190         [ +  + ]:         20 :     for (mp_state_mem_area_t *area = &MP_STATE_MEM(area); area != NULL; area = NEXT_AREA(area)) {
    1191                 :            :         #if !EXTENSIVE_HEAP_PROFILING
    1192                 :            :         // When comparing heap output we don't want to print the starting
    1193                 :            :         // pointer of the heap because it changes from run to run.
    1194                 :         16 :         mp_printf(print, "GC memory layout; from %p:", area->gc_pool_start);
    1195                 :            :         #endif
    1196         [ +  + ]:       1248 :         for (size_t bl = 0; bl < area->gc_alloc_table_byte_len * BLOCKS_PER_ATB; bl++) {
    1197         [ +  + ]:       1236 :             if (bl % DUMP_BYTES_PER_LINE == 0) {
    1198                 :            :                 // a new line of blocks
    1199                 :            :                 {
    1200                 :            :                     // check if this line contains only free blocks
    1201                 :            :                     size_t bl2 = bl;
    1202   [ +  +  +  + ]:     258608 :                     while (bl2 < area->gc_alloc_table_byte_len * BLOCKS_PER_ATB && ATB_GET_KIND(area, bl2) == AT_FREE) {
    1203                 :     258584 :                         bl2++;
    1204                 :            :                     }
    1205         [ +  + ]:         24 :                     if (bl2 - bl >= 2 * DUMP_BYTES_PER_LINE) {
    1206                 :            :                         // there are at least 2 lines containing only free blocks, so abbreviate their printing
    1207                 :         16 :                         mp_printf(print, "\n       (%u lines all free)", (uint)(bl2 - bl) / DUMP_BYTES_PER_LINE);
    1208                 :         16 :                         bl = bl2 & (~(DUMP_BYTES_PER_LINE - 1));
    1209         [ +  + ]:         16 :                         if (bl >= area->gc_alloc_table_byte_len * BLOCKS_PER_ATB) {
    1210                 :            :                             // got to end of heap
    1211                 :            :                             break;
    1212                 :            :                         }
    1213                 :            :                     }
    1214                 :            :                 }
    1215                 :            :                 // print header for new line of blocks
    1216                 :            :                 // (the cast to uint32_t is for 16-bit ports)
    1217                 :         20 :                 mp_printf(print, "\n%08x: ", (uint)(bl * BYTES_PER_BLOCK));
    1218                 :            :             }
    1219                 :       1232 :             int c = ' ';
    1220   [ +  +  -  + ]:       1232 :             switch (ATB_GET_KIND(area, bl)) {
    1221                 :            :                 case AT_FREE:
    1222                 :            :                     c = '.';
    1223                 :            :                     break;
    1224                 :            :                 /* this prints out if the object is reachable from BSS or STACK (for unix only)
    1225                 :            :                 case AT_HEAD: {
    1226                 :            :                     c = 'h';
    1227                 :            :                     void **ptrs = (void**)(void*)&mp_state_ctx;
    1228                 :            :                     mp_uint_t len = offsetof(mp_state_ctx_t, vm.stack_top) / sizeof(mp_uint_t);
    1229                 :            :                     for (mp_uint_t i = 0; i < len; i++) {
    1230                 :            :                         mp_uint_t ptr = (mp_uint_t)ptrs[i];
    1231                 :            :                         if (gc_get_ptr_area(ptr) && BLOCK_FROM_PTR(ptr) == bl) {
    1232                 :            :                             c = 'B';
    1233                 :            :                             break;
    1234                 :            :                         }
    1235                 :            :                     }
    1236                 :            :                     if (c == 'h') {
    1237                 :            :                         ptrs = (void**)&c;
    1238                 :            :                         len = ((mp_uint_t)MP_STATE_THREAD(stack_top) - (mp_uint_t)&c) / sizeof(mp_uint_t);
    1239                 :            :                         for (mp_uint_t i = 0; i < len; i++) {
    1240                 :            :                             mp_uint_t ptr = (mp_uint_t)ptrs[i];
    1241                 :            :                             if (gc_get_ptr_area(ptr) && BLOCK_FROM_PTR(ptr) == bl) {
    1242                 :            :                                 c = 'S';
    1243                 :            :                                 break;
    1244                 :            :                             }
    1245                 :            :                         }
    1246                 :            :                     }
    1247                 :            :                     break;
    1248                 :            :                 }
    1249                 :            :                 */
    1250                 :            :                 /* this prints the uPy object type of the head block */
    1251                 :         76 :                 case AT_HEAD: {
    1252                 :         76 :                     void **ptr = (void **)(area->gc_pool_start + bl * BYTES_PER_BLOCK);
    1253         [ +  - ]:         76 :                     if (*ptr == &mp_type_tuple) {
    1254                 :            :                         c = 'T';
    1255         [ +  + ]:         76 :                     } else if (*ptr == &mp_type_list) {
    1256                 :            :                         c = 'L';
    1257         [ +  - ]:         72 :                     } else if (*ptr == &mp_type_dict) {
    1258                 :            :                         c = 'D';
    1259   [ +  -  +  - ]:         72 :                     } else if (*ptr == &mp_type_str || *ptr == &mp_type_bytes) {
    1260                 :            :                         c = 'S';
    1261                 :            :                     }
    1262                 :            :                     #if MICROPY_PY_BUILTINS_BYTEARRAY
    1263         [ +  - ]:         72 :                     else if (*ptr == &mp_type_bytearray) {
    1264                 :            :                         c = 'A';
    1265                 :            :                     }
    1266                 :            :                     #endif
    1267                 :            :                     #if MICROPY_PY_ARRAY
    1268         [ +  - ]:         72 :                     else if (*ptr == &mp_type_array) {
    1269                 :            :                         c = 'A';
    1270                 :            :                     }
    1271                 :            :                     #endif
    1272                 :            :                     #if MICROPY_PY_BUILTINS_FLOAT
    1273         [ +  - ]:         72 :                     else if (*ptr == &mp_type_float) {
    1274                 :            :                         c = 'F';
    1275                 :            :                     }
    1276                 :            :                     #endif
    1277         [ +  + ]:         72 :                     else if (*ptr == &mp_type_fun_bc) {
    1278                 :            :                         c = 'B';
    1279         [ +  - ]:         68 :                     } else if (*ptr == &mp_type_module) {
    1280                 :            :                         c = 'M';
    1281                 :            :                     } else {
    1282                 :         68 :                         c = 'h';
    1283                 :            :                         #if 0
    1284                 :            :                         // This code prints "Q" for qstr-pool data, and "q" for qstr-str
    1285                 :            :                         // data.  It can be useful to see how qstrs are being allocated,
    1286                 :            :                         // but is disabled by default because it is very slow.
    1287                 :            :                         for (qstr_pool_t *pool = MP_STATE_VM(last_pool); c == 'h' && pool != NULL; pool = pool->prev) {
    1288                 :            :                             if ((qstr_pool_t *)ptr == pool) {
    1289                 :            :                                 c = 'Q';
    1290                 :            :                                 break;
    1291                 :            :                             }
    1292                 :            :                             for (const byte **q = pool->qstrs, **q_top = pool->qstrs + pool->len; q < q_top; q++) {
    1293                 :            :                                 if ((const byte *)ptr == *q) {
    1294                 :            :                                     c = 'q';
    1295                 :            :                                     break;
    1296                 :            :                                 }
    1297                 :            :                             }
    1298                 :            :                         }
    1299                 :            :                         #endif
    1300                 :            :                     }
    1301                 :            :                     break;
    1302                 :            :                 }
    1303                 :         92 :                 case AT_TAIL:
    1304                 :         92 :                     c = '=';
    1305                 :         92 :                     break;
    1306                 :          0 :                 case AT_MARK:
    1307                 :          0 :                     c = 'm';
    1308                 :          0 :                     break;
    1309                 :            :             }
    1310                 :       1232 :             mp_printf(print, "%c", c);
    1311                 :            :         }
    1312                 :         16 :         mp_print_str(print, "\n");
    1313                 :            :     }
    1314                 :          4 :     GC_EXIT();
    1315                 :          4 : }
    1316                 :            : 
    1317                 :            : #if 0
    1318                 :            : // For testing the GC functions
    1319                 :            : void gc_test(void) {
    1320                 :            :     mp_uint_t len = 500;
    1321                 :            :     mp_uint_t *heap = malloc(len);
    1322                 :            :     gc_init(heap, heap + len / sizeof(mp_uint_t));
    1323                 :            :     void *ptrs[100];
    1324                 :            :     {
    1325                 :            :         mp_uint_t **p = gc_alloc(16, false);
    1326                 :            :         p[0] = gc_alloc(64, false);
    1327                 :            :         p[1] = gc_alloc(1, false);
    1328                 :            :         p[2] = gc_alloc(1, false);
    1329                 :            :         p[3] = gc_alloc(1, false);
    1330                 :            :         mp_uint_t ***p2 = gc_alloc(16, false);
    1331                 :            :         p2[0] = p;
    1332                 :            :         p2[1] = p;
    1333                 :            :         ptrs[0] = p2;
    1334                 :            :     }
    1335                 :            :     for (int i = 0; i < 25; i += 2) {
    1336                 :            :         mp_uint_t *p = gc_alloc(i, false);
    1337                 :            :         printf("p=%p\n", p);
    1338                 :            :         if (i & 3) {
    1339                 :            :             // ptrs[i] = p;
    1340                 :            :         }
    1341                 :            :     }
    1342                 :            : 
    1343                 :            :     printf("Before GC:\n");
    1344                 :            :     gc_dump_alloc_table(&mp_plat_print);
    1345                 :            :     printf("Starting GC...\n");
    1346                 :            :     gc_collect_start();
    1347                 :            :     gc_collect_root(ptrs, sizeof(ptrs) / sizeof(void *));
    1348                 :            :     gc_collect_end();
    1349                 :            :     printf("After GC:\n");
    1350                 :            :     gc_dump_alloc_table(&mp_plat_print);
    1351                 :            : }
    1352                 :            : #endif
    1353                 :            : 
    1354                 :            : #endif // MICROPY_ENABLE_GC

Generated by: LCOV version 1.15-5-g462f71d