LCOV - code coverage report
Current view: top level - py - gc.c (source / functions) Hit Total Coverage
Test: unix_coverage_v1.19.1-992-g38e7b842c.info Lines: 391 394 99.2 %
Date: 2023-03-23 12:38:05 Functions: 20 20 100.0 %
Branches: 218 248 87.9 %

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

Generated by: LCOV version 1.15-5-g462f71d