// force the freeing of a piece of memory
// TODO: freeing here does not call finaliser
void gc_free(void *ptr) {
    if (MP_STATE_MEM(gc_lock_depth) > 0) {
        // TODO how to deal with this error?
        return;
    }

    DEBUG_printf("gc_free(%p)\n", ptr);

    if (VERIFY_PTR(ptr)) {
        size_t block = BLOCK_FROM_PTR(ptr);
        if (ATB_GET_KIND(block) == AT_HEAD) {
            #if MICROPY_ENABLE_FINALISER
            FTB_CLEAR(block);
            #endif
            // set the last_free pointer to this block if it's earlier in the heap
            if (block / BLOCKS_PER_ATB < MP_STATE_MEM(gc_last_free_atb_index)) {
                MP_STATE_MEM(gc_last_free_atb_index) = block / BLOCKS_PER_ATB;
            }

            // free head and all of its tail blocks
            do {
                ATB_ANY_TO_FREE(block);
                block += 1;
            } while (ATB_GET_KIND(block) == AT_TAIL);

            #if EXTENSIVE_HEAP_PROFILING
            gc_dump_alloc_table();
            #endif
        } else {
            assert(!"bad free");
        }
    } else if (ptr != NULL) {
        assert(!"bad free");
    }
}

void gc_collect_end(void) {
    gc_deal_with_stack_overflow();
    gc_sweep();
    MP_STATE_MEM(gc_last_free_atb_index) = 0;
    MP_STATE_MEM(gc_lock_depth)--;
    GC_EXIT();
}

void gc_collect_start(void) {
    gc_lock();
    MP_STATE_MEM(gc_stack_overflow) = 0;
    MP_STATE_MEM(gc_sp) = MP_STATE_MEM(gc_stack);
    // 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;
    gc_collect_root(ptrs, offsetof(mp_state_ctx_t, vm.stack_top) / sizeof(void*));
}

void *m_malloc_maybe(size_t num_bytes) {
    void *ptr = malloc(num_bytes);
#if MICROPY_MEM_STATS
    MP_STATE_MEM(total_bytes_allocated) += num_bytes;
    MP_STATE_MEM(current_bytes_allocated) += num_bytes;
    UPDATE_PEAK();
#endif
    DEBUG_printf("malloc %d : %p\n", num_bytes, ptr);
    return ptr;
}

STATIC void gc_sweep(void) {
    #if MICROPY_PY_GC_COLLECT_RETVAL
    MP_STATE_MEM(gc_collected) = 0;
    #endif
    // free unmarked heads and their tails
    int free_tail = 0;
    for (size_t block = 0; block < MP_STATE_MEM(gc_alloc_table_byte_len) * BLOCKS_PER_ATB; block++) {
        switch (ATB_GET_KIND(block)) {
            case AT_HEAD:
#if MICROPY_ENABLE_FINALISER
                if (FTB_GET(block)) {
                    mp_obj_base_t *obj = (mp_obj_base_t*)PTR_FROM_BLOCK(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(block);
                }
#endif
                free_tail = 1;
                DEBUG_printf("gc_sweep(%p)\n", PTR_FROM_BLOCK(block));
                #if MICROPY_PY_GC_COLLECT_RETVAL
                MP_STATE_MEM(gc_collected)++;
                #endif
                // fall through to free the head

            case AT_TAIL:
                if (free_tail) {
                    ATB_ANY_TO_FREE(block);
                    #if CLEAR_ON_SWEEP
                    memset((void*)PTR_FROM_BLOCK(block), 0, BYTES_PER_BLOCK);
                    #endif
                }
                break;

            case AT_MARK:
                ATB_MARK_TO_HEAD(block);
                free_tail = 0;
                break;
        }
    }
}

void *m_malloc_with_finaliser(size_t num_bytes) {
    void *ptr = malloc_with_finaliser(num_bytes);
    if (ptr == NULL && num_bytes != 0) {
        return m_malloc_fail(num_bytes);
    }
#if MICROPY_MEM_STATS
    MP_STATE_MEM(total_bytes_allocated) += num_bytes;
    MP_STATE_MEM(current_bytes_allocated) += num_bytes;
    UPDATE_PEAK();
#endif
    DEBUG_printf("malloc %d : %p\n", num_bytes, ptr);
    return ptr;
}

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 (size_t block = 0; block < MP_STATE_MEM(gc_alloc_table_byte_len) * BLOCKS_PER_ATB; block++) {
            // trace (again) if mark bit set
            if (ATB_GET_KIND(block) == AT_MARK) {
                gc_mark_subtree(block);
            }
        }
    }
}

STATIC mp_obj_t gc_threshold(size_t n_args, const mp_obj_t *args) {
    if (n_args == 0) {
        if (MP_STATE_MEM(gc_alloc_threshold) == (size_t)-1) {
            return MP_OBJ_NEW_SMALL_INT(-1);
        }
        return mp_obj_new_int(MP_STATE_MEM(gc_alloc_threshold) * MICROPY_BYTES_PER_GC_BLOCK);
    }
    mp_int_t val = mp_obj_get_int(args[0]);
    if (val < 0) {
        MP_STATE_MEM(gc_alloc_threshold) = (size_t)-1;
    } else {
        MP_STATE_MEM(gc_alloc_threshold) = val / MICROPY_BYTES_PER_GC_BLOCK;
    }
    return mp_const_none;
}

/// \function collect()
/// Run a garbage collection.
STATIC mp_obj_t py_gc_collect(void) {
    gc_collect();
#if MICROPY_PY_GC_COLLECT_RETVAL
    return MP_OBJ_NEW_SMALL_INT(MP_STATE_MEM(gc_collected));
#else
    return mp_const_none;
#endif
}

void gc_info(gc_info_t *info) {
    info->total = MP_STATE_MEM(gc_pool_end) - MP_STATE_MEM(gc_pool_start);
    info->used = 0;
    info->free = 0;
    info->num_1block = 0;
    info->num_2block = 0;
    info->max_block = 0;
    for (size_t block = 0, len = 0; block < MP_STATE_MEM(gc_alloc_table_byte_len) * BLOCKS_PER_ATB; block++) {
        size_t kind = ATB_GET_KIND(block);
        if (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;
            }
        }
        switch (kind) {
            case AT_FREE:
                info->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;
        }
    }

    info->used *= BYTES_PER_BLOCK;
    info->free *= BYTES_PER_BLOCK;
}

STATIC void gc_drain_stack(void) {
    while (MP_STATE_MEM(gc_sp) > MP_STATE_MEM(gc_stack)) {
        // pop the next block off the stack
        size_t block = *--MP_STATE_MEM(gc_sp);

        // 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(block + n_blocks) == AT_TAIL);

        // check this block's children
        void **ptrs = (void**)PTR_FROM_BLOCK(block);
        for (size_t i = n_blocks * BYTES_PER_BLOCK / sizeof(void*); i > 0; i--, ptrs++) {
            void *ptr = *ptrs;
            VERIFY_MARK_AND_PUSH(ptr);
        }
    }
}

void m_free(void *ptr, size_t num_bytes) {
#else
void m_free(void *ptr) {
#endif
    free(ptr);
#if MICROPY_MEM_STATS
    MP_STATE_MEM(current_bytes_allocated) -= num_bytes;
#endif
    DEBUG_printf("free %p, %d\n", ptr, num_bytes);
}

void gc_collect_start(void) {
    GC_ENTER();
    MP_STATE_MEM(gc_lock_depth)++;
    #if MICROPY_GC_ALLOC_THRESHOLD
    MP_STATE_MEM(gc_alloc_amount) = 0;
    #endif
    MP_STATE_MEM(gc_stack_overflow) = 0;

    // 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;
    gc_collect_root(ptrs, offsetof(mp_state_ctx_t, vm.qstr_last_chunk) / 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
}

// 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.
STATIC void gc_mark_subtree(size_t block) {
    // Start with the block passed in the argument.
    size_t sp = 0;
    for (;;) {
        // 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(block + n_blocks) == AT_TAIL);

        // check this block's children
        void **ptrs = (void**)PTR_FROM_BLOCK(block);
        for (size_t i = n_blocks * BYTES_PER_BLOCK / sizeof(void*); i > 0; i--, ptrs++) {
            void *ptr = *ptrs;
            if (VERIFY_PTR(ptr)) {
                // Mark and push this pointer
                size_t childblock = BLOCK_FROM_PTR(ptr);
                if (ATB_GET_KIND(childblock) == AT_HEAD) {
                    // an unmarked head, mark it, and push it on gc stack
                    TRACE_MARK(childblock, ptr);
                    ATB_HEAD_TO_MARK(childblock);
                    if (sp < MICROPY_ALLOC_GC_STACK_SIZE) {
                        MP_STATE_MEM(gc_stack)[sp++] = childblock;
                    } 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
        block = MP_STATE_MEM(gc_stack)[--sp];
    }
}

void *m_realloc_maybe(void *ptr, size_t old_num_bytes, size_t new_num_bytes, bool allow_move) {
#else
void *m_realloc_maybe(void *ptr, size_t new_num_bytes, bool allow_move) {
#endif
    void *new_ptr = realloc_ext(ptr, new_num_bytes, allow_move);
#if MICROPY_MEM_STATS
    // At first thought, "Total bytes allocated" should only grow,
    // after all, it's *total*. But consider for example 2K block
    // shrunk to 1K and then grown to 2K again. It's still 2K
    // allocated total. If we process only positive increments,
    // we'll count 3K.
    // Also, don't count failed reallocs.
    if (!(new_ptr == NULL && new_num_bytes != 0)) {
        size_t diff = new_num_bytes - old_num_bytes;
        MP_STATE_MEM(total_bytes_allocated) += diff;
        MP_STATE_MEM(current_bytes_allocated) += diff;
        UPDATE_PEAK();
    }
#endif
    DEBUG_printf("realloc %p, %d, %d : %p\n", ptr, old_num_bytes, new_num_bytes, new_ptr);
    return new_ptr;
}

void gc_collect_end(void) {
    gc_deal_with_stack_overflow();
    gc_sweep();
    MP_STATE_MEM(gc_last_free_atb_index) = 0;
    gc_unlock();
}

bool gc_is_locked(void) {
    return MP_STATE_MEM(gc_lock_depth) != 0;
}

size_t m_get_total_bytes_allocated(void) {
    return MP_STATE_MEM(total_bytes_allocated);
}

void gc_dump_alloc_table(void) {
    static const size_t DUMP_BYTES_PER_LINE = 64;
    #if !EXTENSIVE_HEAP_PROFILING
    // When comparing heap output we don't want to print the starting
    // pointer of the heap because it changes from run to run.
    mp_printf(&mp_plat_print, "GC memory layout; from %p:", MP_STATE_MEM(gc_pool_start));
    #endif
    for (size_t bl = 0; bl < MP_STATE_MEM(gc_alloc_table_byte_len) * BLOCKS_PER_ATB; bl++) {
        if (bl % DUMP_BYTES_PER_LINE == 0) {
            // a new line of blocks
            {
                // check if this line contains only free blocks
                size_t bl2 = bl;
                while (bl2 < MP_STATE_MEM(gc_alloc_table_byte_len) * BLOCKS_PER_ATB && ATB_GET_KIND(bl2) == AT_FREE) {
                    bl2++;
                }
                if (bl2 - bl >= 2 * DUMP_BYTES_PER_LINE) {
                    // there are at least 2 lines containing only free blocks, so abbreviate their printing
                    mp_printf(&mp_plat_print, "\n       (%u lines all free)", (uint)(bl2 - bl) / DUMP_BYTES_PER_LINE);
                    bl = bl2 & (~(DUMP_BYTES_PER_LINE - 1));
                    if (bl >= MP_STATE_MEM(gc_alloc_table_byte_len) * BLOCKS_PER_ATB) {
                        // got to end of heap
                        break;
                    }
                }
            }
            // print header for new line of blocks
            // (the cast to uint32_t is for 16-bit ports)
            #if EXTENSIVE_HEAP_PROFILING
            mp_printf(&mp_plat_print, "\n%05x: ", (uint)((bl * BYTES_PER_BLOCK) & (uint32_t)0xfffff));
            #else
            mp_printf(&mp_plat_print, "\n%05x: ", (uint)(PTR_FROM_BLOCK(bl) & (uint32_t)0xfffff));
            #endif
        }
        int c = ' ';
        switch (ATB_GET_KIND(bl)) {
            case AT_FREE: c = '.'; break;
            /* this prints out if the object is reachable from BSS or STACK (for unix only)
            case AT_HEAD: {
                c = 'h';
                void **ptrs = (void**)(void*)&mp_state_ctx;
                mp_uint_t len = offsetof(mp_state_ctx_t, vm.stack_top) / sizeof(mp_uint_t);
                for (mp_uint_t i = 0; i < len; i++) {
                    mp_uint_t ptr = (mp_uint_t)ptrs[i];
                    if (VERIFY_PTR(ptr) && BLOCK_FROM_PTR(ptr) == bl) {
                        c = 'B';
                        break;
                    }
                }
                if (c == 'h') {
                    ptrs = (void**)&c;
                    len = ((mp_uint_t)MP_STATE_VM(stack_top) - (mp_uint_t)&c) / sizeof(mp_uint_t);
                    for (mp_uint_t i = 0; i < len; i++) {
                        mp_uint_t ptr = (mp_uint_t)ptrs[i];
                        if (VERIFY_PTR(ptr) && BLOCK_FROM_PTR(ptr) == bl) {
                            c = 'S';
                            break;
                        }
                    }
                }
                break;
            }
            */
            /* this prints the uPy object type of the head block */
            case AT_HEAD: {
                void **ptr = (void**)(MP_STATE_MEM(gc_pool_start) + bl * BYTES_PER_BLOCK);
                if (*ptr == &mp_type_tuple) { c = 'T'; }
                else if (*ptr == &mp_type_list) { c = 'L'; }
                else if (*ptr == &mp_type_dict) { c = 'D'; }
                #if MICROPY_PY_BUILTINS_FLOAT
                else if (*ptr == &mp_type_float) { c = 'F'; }
                #endif
                else if (*ptr == &mp_type_fun_bc) { c = 'B'; }
                else if (*ptr == &mp_type_module) { c = 'M'; }
                else {
                    c = 'h';
                    #if 0
                    // This code prints "Q" for qstr-pool data, and "q" for qstr-str
                    // data.  It can be useful to see how qstrs are being allocated,
                    // but is disabled by default because it is very slow.
                    for (qstr_pool_t *pool = MP_STATE_VM(last_pool); c == 'h' && pool != NULL; pool = pool->prev) {
                        if ((qstr_pool_t*)ptr == pool) {
                            c = 'Q';
                            break;
                        }
                        for (const byte **q = pool->qstrs, **q_top = pool->qstrs + pool->len; q < q_top; q++) {
                            if ((const byte*)ptr == *q) {
                                c = 'q';
                                break;
                            }
                        }
                    }
                    #endif
                }
                break;
            }
            case AT_TAIL: c = 't'; break;
            case AT_MARK: c = 'm'; break;
        }
        mp_printf(&mp_plat_print, "%c", c);
//.........这里部分代码省略.........

/// \function enable()
/// Enable the garbage collector.
STATIC mp_obj_t gc_enable(void) {
    MP_STATE_MEM(gc_auto_collect_enabled) = 1;
    return mp_const_none;
}