/*

* This file is part of the MicroPython project, http://micropython.org/

*

* The MIT License (MIT)

*

* Copyright (c) 2013, 2014 Damien P. George

* Copyright (c) 2014 Paul Sokolovsky

*

* Permission is hereby granted, free of charge, to any person obtaining a copy

* of this software and associated documentation files (the "Software"), to deal

* in the Software without restriction, including without limitation the rights

* to use, copy, modify, merge, publish, distribute, sublicense, and/or sell

* copies of the Software, and to permit persons to whom the Software is

* furnished to do so, subject to the following conditions:

*

* The above copyright notice and this permission notice shall be included in

* all copies or substantial portions of the Software.

*

* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR

* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,

* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE

* AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER

* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,

* OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN

* THE SOFTWARE.

*/

#include <assert.h>

#include <stdio.h>

#include <string.h>

#include "py/gc.h"

#include "py/runtime.h"

#if MICROPY_DEBUG_VALGRIND

#include <valgrind/memcheck.h>

#endif

// CIRCUITPY-CHANGE

#include "supervisor/shared/safe_mode.h"

#include "supervisor/shared/serial.h"

#if CIRCUITPY_MEMORYMONITOR

#include "shared-module/memorymonitor/__init__.h"

#endif

#if MICROPY_ENABLE_GC

#if MICROPY_DEBUG_VERBOSE // print debugging info

#define DEBUG_PRINT (1)

#define DEBUG_printf DEBUG_printf

#else // don't print debugging info

#define DEBUG_PRINT (0)

#define DEBUG_printf(...) (void)0

#endif

// CIRCUITPY-CHANGE

// Uncomment this if you want to use a debugger to capture state at every allocation and free.

// #define LOG_HEAP_ACTIVITY 1

// make this 1 to dump the heap each time it changes

#define EXTENSIVE_HEAP_PROFILING (0)

// make this 1 to zero out swept memory to more eagerly

// detect untraced object still in use

#define CLEAR_ON_SWEEP (0)

#define WORDS_PER_BLOCK ((MICROPY_BYTES_PER_GC_BLOCK) / MP_BYTES_PER_OBJ_WORD)

#define BYTES_PER_BLOCK (MICROPY_BYTES_PER_GC_BLOCK)

// ATB = allocation table byte

// 0b00 = FREE -- free block

// 0b01 = HEAD -- head of a chain of blocks

// 0b10 = TAIL -- in the tail of a chain of blocks

// 0b11 = MARK -- marked head block

#define AT_FREE (0)

#define AT_HEAD (1)

#define AT_TAIL (2)

#define AT_MARK (3)

#define BLOCKS_PER_ATB (4)

#define ATB_MASK_0 (0x03)

#define ATB_MASK_1 (0x0c)

#define ATB_MASK_2 (0x30)

#define ATB_MASK_3 (0xc0)

#define ATB_0_IS_FREE(a) (((a) & ATB_MASK_0) == 0)

#define ATB_1_IS_FREE(a) (((a) & ATB_MASK_1) == 0)

#define ATB_2_IS_FREE(a) (((a) & ATB_MASK_2) == 0)

#define ATB_3_IS_FREE(a) (((a) & ATB_MASK_3) == 0)

#if MICROPY_GC_SPLIT_HEAP

#define NEXT_AREA(area) ((area)->next)

#else

#define NEXT_AREA(area) (NULL)

#endif

#define BLOCK_SHIFT(block) (2 * ((block) & (BLOCKS_PER_ATB - 1)))

#define ATB_GET_KIND(area, block) (((area)->gc_alloc_table_start[(block) / BLOCKS_PER_ATB] >> BLOCK_SHIFT(block)) & 3)

#define ATB_ANY_TO_FREE(area, block) do { area->gc_alloc_table_start[(block) / BLOCKS_PER_ATB] &= (~(AT_MARK << BLOCK_SHIFT(block))); } while (0)

#define ATB_FREE_TO_HEAD(area, block) do { area->gc_alloc_table_start[(block) / BLOCKS_PER_ATB] |= (AT_HEAD << BLOCK_SHIFT(block)); } while (0)

#define ATB_FREE_TO_TAIL(area, block) do { area->gc_alloc_table_start[(block) / BLOCKS_PER_ATB] |= (AT_TAIL << BLOCK_SHIFT(block)); } while (0)

#define ATB_HEAD_TO_MARK(area, block) do { area->gc_alloc_table_start[(block) / BLOCKS_PER_ATB] |= (AT_MARK << BLOCK_SHIFT(block)); } while (0)

#define ATB_MARK_TO_HEAD(area, block) do { area->gc_alloc_table_start[(block) / BLOCKS_PER_ATB] &= (~(AT_TAIL << BLOCK_SHIFT(block))); } while (0)

#define BLOCK_FROM_PTR(area, ptr) (((byte *)(ptr) - area->gc_pool_start) / BYTES_PER_BLOCK)

#define PTR_FROM_BLOCK(area, block) (((block) * BYTES_PER_BLOCK + (uintptr_t)area->gc_pool_start))

// After the ATB, there must be a byte filled with AT_FREE so that gc_mark_tree

// cannot erroneously conclude that a block extends past the end of the GC heap

// due to bit patterns in the FTB (or first block, if finalizers are disabled)

// being interpreted as AT_TAIL.

#define ALLOC_TABLE_GAP_BYTE (1)

#if MICROPY_ENABLE_FINALISER

// FTB = finaliser table byte

// if set, then the corresponding block may have a finaliser

#define BLOCKS_PER_FTB (8)

#define FTB_GET(area, block) ((area->gc_finaliser_table_start[(block) / BLOCKS_PER_FTB] >> ((block) & 7)) & 1)

#define FTB_SET(area, block) do { area->gc_finaliser_table_start[(block) / BLOCKS_PER_FTB] |= (1 << ((block) & 7)); } while (0)

#define FTB_CLEAR(area, block) do { area->gc_finaliser_table_start[(block) / BLOCKS_PER_FTB] &= (~(1 << ((block) & 7))); } while (0)

#endif

// CIRCUITPY-CHANGE: Add selective collect table to skip scanning large buffers without pointers

// CTB = collect table byte

// if set, then the corresponding block should be collected during GC

#define BLOCKS_PER_CTB (8)

#define CTB_GET(area, block) ((area->gc_collect_table_start[(block) / BLOCKS_PER_CTB] >> ((block) & 7)) & 1)

#define CTB_SET(area, block) do { area->gc_collect_table_start[(block) / BLOCKS_PER_CTB] |= (1 << ((block) & 7)); } while (0)

#define CTB_CLEAR(area, block) do { area->gc_collect_table_start[(block) / BLOCKS_PER_CTB] &= (~(1 << ((block) & 7))); } while (0)

#if MICROPY_PY_THREAD && !MICROPY_PY_THREAD_GIL

#define GC_MUTEX_INIT() mp_thread_recursive_mutex_init(&MP_STATE_MEM(gc_mutex))

#define GC_ENTER() mp_thread_recursive_mutex_lock(&MP_STATE_MEM(gc_mutex), 1)

#define GC_EXIT() mp_thread_recursive_mutex_unlock(&MP_STATE_MEM(gc_mutex))

#else

// Either no threading, or assume callers to gc_collect() hold the GIL

#define GC_MUTEX_INIT()

#define GC_ENTER()

#define GC_EXIT()

#endif

// CIRCUITPY-CHANGE

#ifdef LOG_HEAP_ACTIVITY

volatile uint32_t change_me;

#pragma GCC push_options

#pragma GCC optimize ("O0")

void __attribute__ ((noinline)) gc_log_change(uint32_t start_block, uint32_t length) {

change_me += start_block;

change_me += length; // Break on this line.

}

#pragma GCC pop_options

#endif

// Static functions for individual steps of the GC mark/sweep sequence

static void gc_collect_start_common(void);

static void *gc_get_ptr(void **ptrs, int i);

#if MICROPY_GC_SPLIT_HEAP

static void gc_mark_subtree(mp_state_mem_area_t *area, size_t block);

#else

static void gc_mark_subtree(size_t block);

#endif

static void gc_deal_with_stack_overflow(void);

static void gc_sweep_run_finalisers(void);

static void gc_sweep_free_blocks(void);

// TODO waste less memory; currently requires that all entries in alloc_table have a corresponding block in pool

static void gc_setup_area(mp_state_mem_area_t *area, void *start, void *end) {

// CIRCUITPY-CHANGE: Updated calculation to include selective collect table

// calculate parameters for GC (T=total, A=alloc table, F=finaliser table, C=collect table, P=pool; all in bytes):

// T = A + F + C + P

// F = A * BLOCKS_PER_ATB / BLOCKS_PER_FTB

// C = A * BLOCKS_PER_ATB / BLOCKS_PER_CTB

// P = A * BLOCKS_PER_ATB * BYTES_PER_BLOCK

size_t total_byte_len = (byte *)end - (byte *)start;

// Calculate the denominator for the alloc table size calculation

size_t bits_per_block = MP_BITS_PER_BYTE / BLOCKS_PER_ATB; // Start with bits for ATB

#if MICROPY_ENABLE_FINALISER

bits_per_block += MP_BITS_PER_BYTE / BLOCKS_PER_FTB; // Add bits for FTB

#endif

#if MICROPY_ENABLE_SELECTIVE_COLLECT

bits_per_block += MP_BITS_PER_BYTE / BLOCKS_PER_CTB; // Add bits for CTB

#endif

bits_per_block += MP_BITS_PER_BYTE * BYTES_PER_BLOCK; // Add bits for the block itself

// Calculate the allocation table size

size_t available_bits = (total_byte_len - ALLOC_TABLE_GAP_BYTE) * MP_BITS_PER_BYTE;

size_t blocks = available_bits / bits_per_block;

area->gc_alloc_table_byte_len = blocks / BLOCKS_PER_ATB;

// Set up all the table pointers

area->gc_alloc_table_start = (byte *)start;

byte *next_table = area->gc_alloc_table_start + area->gc_alloc_table_byte_len + ALLOC_TABLE_GAP_BYTE;

// Total number of blocks in the pool

size_t gc_pool_block_len = area->gc_alloc_table_byte_len * BLOCKS_PER_ATB;

// Calculate table sizes and set start pointers

#if MICROPY_ENABLE_FINALISER

size_t gc_finaliser_table_byte_len = (gc_pool_block_len + BLOCKS_PER_FTB - 1) / BLOCKS_PER_FTB;

area->gc_finaliser_table_start = next_table;

next_table += gc_finaliser_table_byte_len;

#endif

#if MICROPY_ENABLE_SELECTIVE_COLLECT

size_t gc_collect_table_byte_len = (gc_pool_block_len + BLOCKS_PER_CTB - 1) / BLOCKS_PER_CTB;

area->gc_collect_table_start = next_table;

next_table += gc_collect_table_byte_len;

#endif

// Set pool pointers

area->gc_pool_start = (byte *)end - gc_pool_block_len * BYTES_PER_BLOCK;

area->gc_pool_end = end;

// Verify enough space between last table and start of pool

assert(area->gc_pool_start >= next_table);

// Clear all tables

size_t tables_size = next_table - area->gc_alloc_table_start;

memset(area->gc_alloc_table_start, 0, tables_size);

area->gc_last_free_atb_index = 0;

area->gc_last_used_block = 0;

#if MICROPY_GC_SPLIT_HEAP

area->next = NULL;

#endif

DEBUG_printf("GC layout:\n");

DEBUG_printf(" alloc table at %p, length " UINT_FMT " bytes, "

UINT_FMT " blocks\n",

area->gc_alloc_table_start, area->gc_alloc_table_byte_len,

area->gc_alloc_table_byte_len * BLOCKS_PER_ATB);

#if MICROPY_ENABLE_FINALISER

DEBUG_printf(" finaliser table at %p, length " UINT_FMT " bytes, "

UINT_FMT " blocks\n", area->gc_finaliser_table_start,

gc_finaliser_table_byte_len,

gc_finaliser_table_byte_len * BLOCKS_PER_FTB);

#endif

#if MICROPY_ENABLE_SELECTIVE_COLLECT

DEBUG_printf(" collect table at %p, length " UINT_FMT " bytes, "

UINT_FMT " blocks\n", area->gc_collect_table_start,

gc_collect_table_byte_len,

gc_collect_table_byte_len * BLOCKS_PER_CTB);

#endif

DEBUG_printf(" pool at %p, length " UINT_FMT " bytes, "

UINT_FMT " blocks\n", area->gc_pool_start,

gc_pool_block_len * BYTES_PER_BLOCK, gc_pool_block_len);

}

void gc_init(void *start, void *end) {

// align end pointer on block boundary

end = (void *)((uintptr_t)end & (~(BYTES_PER_BLOCK - 1)));

DEBUG_printf("Initializing GC heap: %p..%p = " UINT_FMT " bytes\n", start, end, (byte *)end - (byte *)start);

gc_setup_area(&MP_STATE_MEM(area), start, end);

// set last free ATB index to start of heap

#if MICROPY_GC_SPLIT_HEAP

MP_STATE_MEM(gc_last_free_area) = &MP_STATE_MEM(area);

#endif

// unlock the GC

MP_STATE_THREAD(gc_lock_depth) = 0;

// allow auto collection

MP_STATE_MEM(gc_auto_collect_enabled) = 1;

#if MICROPY_GC_ALLOC_THRESHOLD

// by default, maxuint for gc threshold, effectively turning gc-by-threshold off

MP_STATE_MEM(gc_alloc_threshold) = (size_t)-1;

MP_STATE_MEM(gc_alloc_amount) = 0;

#endif

GC_MUTEX_INIT();

}

#if MICROPY_GC_SPLIT_HEAP

void gc_add(void *start, void *end) {

// Place the area struct at the start of the area.

mp_state_mem_area_t *area = (mp_state_mem_area_t *)start;

start = (void *)((uintptr_t)start + sizeof(mp_state_mem_area_t));

end = (void *)((uintptr_t)end & (~(BYTES_PER_BLOCK - 1)));

DEBUG_printf("Adding GC heap: %p..%p = " UINT_FMT " bytes\n", start, end, (byte *)end - (byte *)start);

// Init this area

gc_setup_area(area, start, end);

// Find the last registered area in the linked list

mp_state_mem_area_t *prev_area = &MP_STATE_MEM(area);

while (prev_area->next != NULL) {

prev_area = prev_area->next;

}

// Add this area to the linked list

prev_area->next = area;

}

#if MICROPY_GC_SPLIT_HEAP_AUTO

// CIRCUITPY-CHANGE: Added function to compute heap size with selective collect table

static size_t compute_heap_size(size_t total_blocks) {

// Round up to the nearest multiple of BLOCKS_PER_ATB. Partial ATB blocks aren't supported and

// will result in a heap that is too small.

total_blocks = ((total_blocks + BLOCKS_PER_ATB - 1) / BLOCKS_PER_ATB) * BLOCKS_PER_ATB;

size_t atb_bytes = (total_blocks + BLOCKS_PER_ATB - 1) / BLOCKS_PER_ATB;

size_t ftb_bytes = 0;

size_t ctb_bytes = 0;

#if MICROPY_ENABLE_FINALISER

ftb_bytes = (total_blocks + BLOCKS_PER_FTB - 1) / BLOCKS_PER_FTB;

#endif

#if MICROPY_ENABLE_SELECTIVE_COLLECT

ctb_bytes = (total_blocks + BLOCKS_PER_CTB - 1) / BLOCKS_PER_CTB;

#endif

size_t pool_bytes = total_blocks * BYTES_PER_BLOCK;

// Compute bytes needed to build a heap with total_blocks blocks.

size_t total_heap =

sizeof(mp_state_mem_area_t)

+ atb_bytes

+ ALLOC_TABLE_GAP_BYTE

+ ftb_bytes

+ ctb_bytes

+ pool_bytes

+ BYTES_PER_BLOCK; // Extra block of bytes to account for end pointer alignment

// Round up size to the nearest multiple of BYTES_PER_BLOCK.

total_heap = (total_heap + BYTES_PER_BLOCK - 1) / BYTES_PER_BLOCK;

total_heap *= BYTES_PER_BLOCK;

return total_heap;

}

// Try to automatically add a heap area large enough to fulfill 'failed_alloc'.

static bool gc_try_add_heap(size_t failed_alloc) {

// 'needed' is the size of a heap large enough to hold failed_alloc, with

// the additional metadata overheads as calculated in gc_setup_area().

// CIRCUITPY-CHANGE: calculation of how much to grow the heap

size_t total_new_blocks = (failed_alloc + BYTES_PER_BLOCK - 1) / BYTES_PER_BLOCK;

// CIRCUITPY-CHANGE

size_t needed = compute_heap_size(total_new_blocks);

size_t avail = gc_get_max_new_split();

DEBUG_printf("gc_try_add_heap failed_alloc " UINT_FMT ", "

"needed " UINT_FMT ", avail " UINT_FMT " bytes \n",

failed_alloc,

needed,

avail);

if (avail < needed) {

// Can't fit this allocation, or system heap has nearly run out anyway

return false;

}

// Deciding how much to grow the total heap by each time is tricky:

//

// - Grow by too small amounts, leads to heap fragmentation issues.

//

// - Grow by too large amounts, may lead to system heap running out of

// space.

//

// Currently, this implementation is:

//

// - At minimum, aim to double the total heap size each time we add a new

// heap. i.e. without any large single allocations, total size will be

// 64KB -> 128KB -> 256KB -> 512KB -> 1MB, etc

//

// - If the failed allocation is too large to fit in that size, the new

// heap is made exactly large enough for that allocation. Future growth

// will double the total heap size again.

//

// - If the new heap won't fit in the available free space, add the largest

// new heap that will fit (this may lead to failed system heap allocations

// elsewhere, but some allocation will likely fail in this circumstance!)

// Compute total number of blocks in the current heap.

size_t total_blocks = 0;

for (mp_state_mem_area_t *area = &MP_STATE_MEM(area);

area != NULL;

area = NEXT_AREA(area)) {

total_blocks += area->gc_alloc_table_byte_len * BLOCKS_PER_ATB;

}

// CIRCUITPY-CHANGE

size_t total_heap = compute_heap_size(total_blocks);

DEBUG_printf("total_heap " UINT_FMT " bytes\n", total_heap);

size_t to_alloc = MIN(avail, MAX(total_heap, needed));

mp_state_mem_area_t *new_heap = MP_PLAT_ALLOC_HEAP(to_alloc);

DEBUG_printf("MP_PLAT_ALLOC_HEAP " UINT_FMT " = %p\n",

to_alloc, new_heap);

if (new_heap == NULL) {

// This should only fail:

// - In a threaded environment if another thread has

// allocated while this function ran.

// - If there is a bug in gc_get_max_new_split().

return false;

}

gc_add(new_heap, (void *)new_heap + to_alloc);

return true;

}

#endif

#endif

// CIRCUITPY-CHANGE: additional function

void gc_deinit(void) {

// Run any finalisers before we stop using the heap. This will also free

// any additional heap areas (but not the first.)

gc_sweep_all();

memset(&MP_STATE_MEM(area), 0, sizeof(MP_STATE_MEM(area)));

}

void gc_lock(void) {

// This does not need to be atomic or have the GC mutex because:

// - each thread has its own gc_lock_depth so there are no races between threads;

// - a hard interrupt will only change gc_lock_depth during its execution, and

// upon return will restore the value of gc_lock_depth.

MP_STATE_THREAD(gc_lock_depth) += (1 << GC_LOCK_DEPTH_SHIFT);

}

void gc_unlock(void) {

// This does not need to be atomic, See comment above in gc_lock.

MP_STATE_THREAD(gc_lock_depth) -= (1 << GC_LOCK_DEPTH_SHIFT);

}

bool gc_is_locked(void) {

return MP_STATE_THREAD(gc_lock_depth) != 0;

}

// CIRCUITPY-CHANGE: additional function

bool gc_ptr_on_heap(const void *ptr) {

for (mp_state_mem_area_t *area = &MP_STATE_MEM(area); area != NULL; area = NEXT_AREA(area)) {

if (ptr >= (void *)area->gc_pool_start // must be above start of pool

&& ptr < (void *)area->gc_pool_end) { // must be below end of pool

return true;

}

}

return false;

}

#if MICROPY_GC_SPLIT_HEAP

// Returns the area to which this pointer belongs, or NULL if it isn't

// allocated on the GC-managed heap.

static inline mp_state_mem_area_t *gc_get_ptr_area(const void *ptr) {

if (((uintptr_t)(ptr) & (BYTES_PER_BLOCK - 1)) != 0) { // must be aligned on a block

return NULL;

}

for (mp_state_mem_area_t *area = &MP_STATE_MEM(area); area != NULL; area = NEXT_AREA(area)) {

if (ptr >= (void *)area->gc_pool_start // must be above start of pool

&& ptr < (void *)area->gc_pool_end) { // must be below end of pool

return area;

}

}

return NULL;

}

#endif

// ptr should be of type void*

#define VERIFY_PTR(ptr) ( \

((uintptr_t)(ptr) & (BYTES_PER_BLOCK - 1)) == 0 /* must be aligned on a block */ \

&& ptr >= (void *)MP_STATE_MEM(area).gc_pool_start /* must be above start of pool */ \

&& ptr < (void *)MP_STATE_MEM(area).gc_pool_end /* must be below end of pool */ \

)

#ifndef TRACE_MARK

#if DEBUG_PRINT

#define TRACE_MARK(block, ptr) DEBUG_printf("gc_mark(%p)\n", ptr)

#else

#define TRACE_MARK(block, ptr)

#endif

#endif

void gc_collect_start(void) {

gc_collect_start_common();

#if MICROPY_GC_ALLOC_THRESHOLD

MP_STATE_MEM(gc_alloc_amount) = 0;

#endif

// Trace root pointers. This relies on the root pointers being organised

// correctly in the mp_state_ctx structure. We scan nlr_top, dict_locals,

// dict_globals, then the root pointer section of mp_state_vm.

void **ptrs = (void **)(void *)&mp_state_ctx;

size_t root_start = offsetof(mp_state_ctx_t, thread.dict_locals);

size_t root_end = offsetof(mp_state_ctx_t, vm.qstr_last_chunk);

gc_collect_root(ptrs + root_start / sizeof(void *), (root_end - root_start) / sizeof(void *));

#if MICROPY_ENABLE_PYSTACK

// Trace root pointers from the Python stack.

ptrs = (void **)(void *)MP_STATE_THREAD(pystack_start);

gc_collect_root(ptrs, (MP_STATE_THREAD(pystack_cur) - MP_STATE_THREAD(pystack_start)) / sizeof(void *));

#endif

}

static void gc_collect_start_common(void) {

GC_ENTER();

assert((MP_STATE_THREAD(gc_lock_depth) & GC_COLLECT_FLAG) == 0);

MP_STATE_THREAD(gc_lock_depth) |= GC_COLLECT_FLAG;

MP_STATE_MEM(gc_stack_overflow) = 0;

}

void gc_collect_root(void **ptrs, size_t len) {

#if !MICROPY_GC_SPLIT_HEAP

mp_state_mem_area_t *area = &MP_STATE_MEM(area);

#endif

for (size_t i = 0; i < len; i++) {

MICROPY_GC_HOOK_LOOP(i);

void *ptr = gc_get_ptr(ptrs, i);

#if MICROPY_GC_SPLIT_HEAP

mp_state_mem_area_t *area = gc_get_ptr_area(ptr);

if (!area) {

continue;

}

#else

if (!VERIFY_PTR(ptr)) {

continue;

}

#endif

size_t block = BLOCK_FROM_PTR(area, ptr);

if (ATB_GET_KIND(area, block) == AT_HEAD) {

// An unmarked head: mark it, and mark all its children

ATB_HEAD_TO_MARK(area, block);

#if MICROPY_GC_SPLIT_HEAP

gc_mark_subtree(area, block);

#else

gc_mark_subtree(block);

#endif

}

}

}

// Take the given block as the topmost block on the stack. Check all it's

// children: mark the unmarked child blocks and put those newly marked

// blocks on the stack. When all children have been checked, pop off the

// topmost block on the stack and repeat with that one.

// CIRCUITPY-CHANGE: We don't instrument these functions because they occur a lot during GC and

// fill up the output buffer quickly.

#if MICROPY_GC_SPLIT_HEAP

static void MP_NO_INSTRUMENT PLACE_IN_ITCM(gc_mark_subtree)(mp_state_mem_area_t * area, size_t block)

#else

static void MP_NO_INSTRUMENT PLACE_IN_ITCM(gc_mark_subtree)(size_t block)

#endif

{

// Start with the block passed in the argument.

size_t sp = 0;

for (;;) {

#if !MICROPY_GC_SPLIT_HEAP

mp_state_mem_area_t *area = &MP_STATE_MEM(area);

#endif

// work out number of consecutive blocks in the chain starting with this one

size_t n_blocks = 0;

do {

n_blocks += 1;

} while (ATB_GET_KIND(area, block + n_blocks) == AT_TAIL);

// check that the consecutive blocks didn't overflow past the end of the area

assert(area->gc_pool_start + (block + n_blocks) * BYTES_PER_BLOCK <= area->gc_pool_end);

// CIRCUITPY-CHANGE

// check if this block should be collected

#if MICROPY_ENABLE_SELECTIVE_COLLECT

bool should_scan = CTB_GET(area, block);

#else

bool should_scan = true;

#endif

// Only scan the block's children if it's not a leaf

if (should_scan) {

// check this block's children

void **ptrs = (void **)PTR_FROM_BLOCK(area, block);

for (size_t i = n_blocks * BYTES_PER_BLOCK / sizeof(void *); i > 0; i--, ptrs++) {

MICROPY_GC_HOOK_LOOP(i);

void *ptr = *ptrs;

// If this is a heap pointer that hasn't been marked, mark it and push

// it's children to the stack.

#if MICROPY_GC_SPLIT_HEAP

mp_state_mem_area_t *ptr_area = gc_get_ptr_area(ptr);

if (!ptr_area) {

// Not a heap-allocated pointer (might even be random data).

continue;

}

#else

if (!VERIFY_PTR(ptr)) {

continue;

}

mp_state_mem_area_t *ptr_area = area;

#endif

size_t ptr_block = BLOCK_FROM_PTR(ptr_area, ptr);

if (ATB_GET_KIND(ptr_area, ptr_block) != AT_HEAD) {

// This block is already marked.

continue;

}

// An unmarked head. Mark it, and push it on gc stack.

TRACE_MARK(ptr_block, ptr);

ATB_HEAD_TO_MARK(ptr_area, ptr_block);

if (sp < MICROPY_ALLOC_GC_STACK_SIZE) {

MP_STATE_MEM(gc_block_stack)[sp] = ptr_block;

#if MICROPY_GC_SPLIT_HEAP

MP_STATE_MEM(gc_area_stack)[sp] = ptr_area;

#endif

sp += 1;

} else {

MP_STATE_MEM(gc_stack_overflow) = 1;

}

}

}

// Are there any blocks on the stack?

if (sp == 0) {

break; // No, stack is empty, we're done.

}

// pop the next block off the stack

sp -= 1;

block = MP_STATE_MEM(gc_block_stack)[sp];

#if MICROPY_GC_SPLIT_HEAP

area = MP_STATE_MEM(gc_area_stack)[sp];

#endif

}

}

void gc_sweep_all(void) {

gc_collect_start_common();

gc_collect_end();

}

void gc_collect_end(void) {

gc_deal_with_stack_overflow();

gc_sweep_run_finalisers();

gc_sweep_free_blocks();

#if MICROPY_GC_SPLIT_HEAP

MP_STATE_MEM(gc_last_free_area) = &MP_STATE_MEM(area);

#endif

for (mp_state_mem_area_t *area = &MP_STATE_MEM(area); area != NULL; area = NEXT_AREA(area)) {

area->gc_last_free_atb_index = 0;

}

MP_STATE_THREAD(gc_lock_depth) &= ~GC_COLLECT_FLAG;

GC_EXIT();

}

static void gc_deal_with_stack_overflow(void) {

while (MP_STATE_MEM(gc_stack_overflow)) {

MP_STATE_MEM(gc_stack_overflow) = 0;

// scan entire memory looking for blocks which have been marked but not their children

for (mp_state_mem_area_t *area = &MP_STATE_MEM(area); area != NULL; area = NEXT_AREA(area)) {

for (size_t block = 0; block < area->gc_alloc_table_byte_len * BLOCKS_PER_ATB; block++) {

MICROPY_GC_HOOK_LOOP(block);

// trace (again) if mark bit set

if (ATB_GET_KIND(area, block) == AT_MARK) {

#if MICROPY_GC_SPLIT_HEAP

gc_mark_subtree(area, block);

#else

gc_mark_subtree(block);

#endif

}

}

}

}

}

// Run finalisers for all to-be-freed blocks

static void gc_sweep_run_finalisers(void) {

#if MICROPY_ENABLE_FINALISER

for (const mp_state_mem_area_t *area = &MP_STATE_MEM(area); area != NULL; area = NEXT_AREA(area)) {

assert(area->gc_last_used_block <= area->gc_alloc_table_byte_len * BLOCKS_PER_ATB);

// Small speed optimisation: skip over empty FTB blocks

size_t ftb_end = area->gc_last_used_block / BLOCKS_PER_FTB; // index is inclusive

for (size_t ftb_idx = 0; ftb_idx <= ftb_end; ftb_idx++) {

byte ftb = area->gc_finaliser_table_start[ftb_idx];

size_t block = ftb_idx * BLOCKS_PER_FTB;

while (ftb) {

MICROPY_GC_HOOK_LOOP(block);

if (ftb & 1) { // FTB_GET(area, block) shortcut

if (ATB_GET_KIND(area, block) == AT_HEAD) {

mp_obj_base_t *obj = (mp_obj_base_t *)PTR_FROM_BLOCK(area, block);

if (obj->type != NULL) {

// if the object has a type then see if it has a __del__ method

mp_obj_t dest[2];

mp_load_method_maybe(MP_OBJ_FROM_PTR(obj), MP_QSTR___del__, dest);

if (dest[0] != MP_OBJ_NULL) {

// load_method returned a method, execute it in a protected environment

#if MICROPY_ENABLE_SCHEDULER

mp_sched_lock();

#endif

mp_call_function_1_protected(dest[0], dest[1]);

#if MICROPY_ENABLE_SCHEDULER

mp_sched_unlock();

#endif

}

}

// clear finaliser flag

FTB_CLEAR(area, block);

}

}

ftb >>= 1;

block++;

}

}

}

#endif // MICROPY_ENABLE_FINALISER

}

// Free unmarked heads and their tails

static void gc_sweep_free_blocks(void) {

#if MICROPY_PY_GC_COLLECT_RETVAL

MP_STATE_MEM(gc_collected) = 0;

#endif

int free_tail = 0;

#if MICROPY_GC_SPLIT_HEAP_AUTO

mp_state_mem_area_t *prev_area = NULL;

#endif

for (mp_state_mem_area_t *area = &MP_STATE_MEM(area); area != NULL; area = NEXT_AREA(area)) {

size_t last_used_block = 0;

assert(area->gc_last_used_block <= area->gc_alloc_table_byte_len * BLOCKS_PER_ATB);

for (size_t block = 0; block <= area->gc_last_used_block; block++) {

MICROPY_GC_HOOK_LOOP(block);

switch (ATB_GET_KIND(area, block)) {

case AT_HEAD:

free_tail = 1;

DEBUG_printf("gc_sweep_free_blocks(%p)\n", (void *)PTR_FROM_BLOCK(area, block));

#if MICROPY_PY_GC_COLLECT_RETVAL

MP_STATE_MEM(gc_collected)++;

#endif

// fall through to free the head

MP_FALLTHROUGH

case AT_TAIL:

if (free_tail) {

ATB_ANY_TO_FREE(area, block);

#if CLEAR_ON_SWEEP

memset((void *)PTR_FROM_BLOCK(area, block), 0, BYTES_PER_BLOCK);

#endif

} else {

last_used_block = block;

}

break;

case AT_MARK:

ATB_MARK_TO_HEAD(area, block);

free_tail = 0;

last_used_block = block;

break;

}

}

area->gc_last_used_block = last_used_block;

#if MICROPY_GC_SPLIT_HEAP_AUTO

// Free any empty area, aside from the first one

if (last_used_block == 0 && prev_area != NULL) {

DEBUG_printf("gc_sweep_free_blocks free empty area %p\n", area);

NEXT_AREA(prev_area) = NEXT_AREA(area);

MP_PLAT_FREE_HEAP(area);

area = prev_area;

}

prev_area = area;

#endif

}

}

// CIRCUITPY-CHANGE: add function

void gc_collect_ptr(void *ptr) {

void *ptrs[1] = { ptr };

gc_collect_root(ptrs, 1);

}

// Address sanitizer needs to know that the access to ptrs[i] must always be

// considered OK, even if it's a load from an address that would normally be

// prohibited (due to being undefined, in a red zone, etc).

#if defined(__GNUC__) && (__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 8))

__attribute__((no_sanitize_address))

#endif

// CIRCUITPY-CHANGE

static void *MP_NO_INSTRUMENT PLACE_IN_ITCM(gc_get_ptr)(void **ptrs, int i) {

#if MICROPY_DEBUG_VALGRIND

if (!VALGRIND_CHECK_MEM_IS_ADDRESSABLE(&ptrs[i], sizeof(*ptrs))) {

return NULL;

}

#endif

return ptrs[i];

}

void gc_info(gc_info_t *info) {

GC_ENTER();

info->total = 0;

info->used = 0;

info->free = 0;

info->max_free = 0;

info->num_1block = 0;

info->num_2block = 0;

info->max_block = 0;

for (mp_state_mem_area_t *area = &MP_STATE_MEM(area); area != NULL; area = NEXT_AREA(area)) {

bool finish = false;

info->total += area->gc_pool_end - area->gc_pool_start;

for (size_t block = 0, len = 0, len_free = 0; !finish;) {

MICROPY_GC_HOOK_LOOP(block);

size_t kind = ATB_GET_KIND(area, block);

switch (kind) {

case AT_FREE:

info->free += 1;

len_free += 1;

len = 0;

break;

case AT_HEAD:

info->used += 1;

len = 1;

break;

case AT_TAIL:

info->used += 1;

len += 1;

break;

case AT_MARK:

// shouldn't happen

break;

}

block++;

finish = (block == area->gc_alloc_table_byte_len * BLOCKS_PER_ATB);

// Get next block type if possible

if (!finish) {

kind = ATB_GET_KIND(area, block);

}

if (finish || kind == AT_FREE || kind == AT_HEAD) {

if (len == 1) {

info->num_1block += 1;

} else if (len == 2) {

info->num_2block += 1;

}

if (len > info->max_block) {

info->max_block = len;

}

if (finish || kind == AT_HEAD) {

if (len_free > info->max_free) {

info->max_free = len_free;

}

len_free = 0;

}

}

}

}

info->used *= BYTES_PER_BLOCK;

info->free *= BYTES_PER_BLOCK;

#if MICROPY_GC_SPLIT_HEAP_AUTO

info->max_new_split = gc_get_max_new_split();

#endif

GC_EXIT();

}

// CIRCUITPY-CHANGE: New function.

// C code may be used when the VM heap isn't active. This function

// allows that code to test if it is. It can use the outer pool if needed.

bool gc_alloc_possible(void) {

return MP_STATE_MEM(area).gc_pool_start != 0;

}

void *gc_alloc(size_t n_bytes, unsigned int alloc_flags) {

bool has_finaliser = alloc_flags & GC_ALLOC_FLAG_HAS_FINALISER;

size_t n_blocks = ((n_bytes + BYTES_PER_BLOCK - 1) & (~(BYTES_PER_BLOCK - 1))) / BYTES_PER_BLOCK;

DEBUG_printf("gc_alloc(" UINT_FMT " bytes -> " UINT_FMT " blocks)\n", n_bytes, n_blocks);

// check for 0 allocation

if (n_blocks == 0) {

return NULL;

}

// check if GC is locked

if (MP_STATE_THREAD(gc_lock_depth) > 0) {

return NULL;

}

GC_ENTER();

mp_state_mem_area_t *area;

size_t i;

size_t end_block;

size_t start_block;

size_t n_free;

int collected = !MP_STATE_MEM(gc_auto_collect_enabled);

#if MICROPY_GC_SPLIT_HEAP_AUTO

bool added = false;

#endif

#if MICROPY_GC_ALLOC_THRESHOLD

if (!collected && MP_STATE_MEM(gc_alloc_amount) >= MP_STATE_MEM(gc_alloc_threshold)) {

GC_EXIT();

gc_collect();

collected = 1;

GC_ENTER();

}

#endif

for (;;) {

#if MICROPY_GC_SPLIT_HEAP

area = MP_STATE_MEM(gc_last_free_area);

#else

area = &MP_STATE_MEM(area);

#endif

// CIRCUITPY-CHANGE

if (area == 0) {

reset_into_safe_mode(SAFE_MODE_GC_ALLOC_OUTSIDE_VM);

}

// look for a run of n_blocks available blocks

for (; area != NULL; area = NEXT_AREA(area), i = 0) {

n_free = 0;

for (i = area->gc_last_free_atb_index; i < area->gc_alloc_table_byte_len; i++) {

MICROPY_GC_HOOK_LOOP(i);

byte a = area->gc_alloc_table_start[i];

// *FORMAT-OFF*

if (ATB_0_IS_FREE(a)) { if (++n_free >= n_blocks) { i = i * BLOCKS_PER_ATB + 0; goto found; } } else { n_free = 0; }

if (ATB_1_IS_FREE(a)) { if (++n_free >= n_blocks) { i = i * BLOCKS_PER_ATB + 1; goto found; } } else { n_free = 0; }

if (ATB_2_IS_FREE(a)) { if (++n_free >= n_blocks) { i = i * BLOCKS_PER_ATB + 2; goto found; } } else { n_free = 0; }

if (ATB_3_IS_FREE(a)) { if (++n_free >= n_blocks) { i = i * BLOCKS_PER_ATB + 3; goto found; } } else { n_free = 0; }

// *FORMAT-ON*

}

// No free blocks found on this heap. Mark this heap as

// filled, so we won't try to find free space here again until

// space is freed.

#if MICROPY_GC_SPLIT_HEAP

if (n_blocks == 1) {

area->gc_last_free_atb_index = (i + 1) / BLOCKS_PER_ATB; // or (size_t)-1

}

#endif

}

GC_EXIT();

// nothing found!

if (collected) {

#if MICROPY_GC_SPLIT_HEAP_AUTO

if (!added && gc_try_add_heap(n_bytes)) {

added = true;

continue;

}

#endif

// CIRCUITPY-CHANGE

#if CIRCUITPY_DEBUG

gc_dump_alloc_table(&mp_plat_print);

#endif

return NULL;

}

DEBUG_printf("gc_alloc(" UINT_FMT "): no free mem, triggering GC\n", n_bytes);

gc_collect();

collected = 1;

GC_ENTER();

}

// found, ending at block i inclusive

found:

// get starting and end blocks, both inclusive

end_block = i;

start_block = i - n_free + 1;

// Set last free ATB index to block after last block we found, for start of

// next scan. To reduce fragmentation, we only do this if we were looking

// for a single free block, which guarantees that there are no free blocks

// before this one. Also, whenever we free or shink a block we must check

// if this index needs adjusting (see gc_realloc and gc_free).

if (n_free == 1) {

#if MICROPY_GC_SPLIT_HEAP

MP_STATE_MEM(gc_last_free_area) = area;

#endif

area->gc_last_free_atb_index = (i + 1) / BLOCKS_PER_ATB;

}

// CIRCUITPY-CHANGE

#ifdef LOG_HEAP_ACTIVITY

gc_log_change(start_block, end_block - start_block + 1);

#endif