LCOV - code coverage report
Current view: top level - py - gc.c (source / functions) Hit Total Coverage
Test: unix_coverage_v1.24.0-247-g112f65776.info Lines: 423 426 99.3 %
Date: 2025-02-04 09:50:29 Functions: 22 22 100.0 %
Branches: 234 266 88.0 %

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

Generated by: LCOV version 1.15-5-g462f71d