gc.c 32.9 KB
Newer Older
1
/*
2
 * This file is part of the MicroPython project, http://micropython.org/
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
 *
 * The MIT License (MIT)
 *
 * Copyright (c) 2013, 2014 Damien P. George
 *
 * 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.
 */

27
#include <assert.h>
Damien's avatar
Damien committed
28 29 30
#include <stdio.h>
#include <string.h>

31 32
#include "py/gc.h"
#include "py/runtime.h"
mux's avatar
mux committed
33

34
#if MICROPY_ENABLE_GC && !MICROPY_ENABLE_IMMORTAL_GC
35

36
#if MICROPY_DEBUG_VERBOSE // print debugging info
37
#define DEBUG_PRINT (1)
38
#define DEBUG_printf DEBUG_printf
39
#else // don't print debugging info
40
#define DEBUG_PRINT (0)
41
#define DEBUG_printf(...) (void)0
42 43
#endif

44 45 46
// make this 1 to dump the heap each time it changes
#define EXTENSIVE_HEAP_PROFILING (0)

47 48 49 50
// make this 1 to zero out swept memory to more eagerly
// detect untraced object still in use
#define CLEAR_ON_SWEEP (0)

51 52
#define WORDS_PER_BLOCK ((MICROPY_BYTES_PER_GC_BLOCK) / BYTES_PER_WORD)
#define BYTES_PER_BLOCK (MICROPY_BYTES_PER_GC_BLOCK)
Damien's avatar
Damien committed
53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76

// 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)

#define BLOCK_SHIFT(block) (2 * ((block) & (BLOCKS_PER_ATB - 1)))
77 78 79 80 81 82 83
#define ATB_GET_KIND(block) ((MP_STATE_MEM(gc_alloc_table_start)[(block) / BLOCKS_PER_ATB] >> BLOCK_SHIFT(block)) & 3)
#define ATB_ANY_TO_FREE(block) do { MP_STATE_MEM(gc_alloc_table_start)[(block) / BLOCKS_PER_ATB] &= (~(AT_MARK << BLOCK_SHIFT(block))); } while (0)
#define ATB_FREE_TO_HEAD(block) do { MP_STATE_MEM(gc_alloc_table_start)[(block) / BLOCKS_PER_ATB] |= (AT_HEAD << BLOCK_SHIFT(block)); } while (0)
#define ATB_FREE_TO_TAIL(block) do { MP_STATE_MEM(gc_alloc_table_start)[(block) / BLOCKS_PER_ATB] |= (AT_TAIL << BLOCK_SHIFT(block)); } while (0)
#define ATB_HEAD_TO_MARK(block) do { MP_STATE_MEM(gc_alloc_table_start)[(block) / BLOCKS_PER_ATB] |= (AT_MARK << BLOCK_SHIFT(block)); } while (0)
#define ATB_MARK_TO_HEAD(block) do { MP_STATE_MEM(gc_alloc_table_start)[(block) / BLOCKS_PER_ATB] &= (~(AT_TAIL << BLOCK_SHIFT(block))); } while (0)

84 85
#define BLOCK_FROM_PTR(ptr) (((byte*)(ptr) - MP_STATE_MEM(gc_pool_start)) / BYTES_PER_BLOCK)
#define PTR_FROM_BLOCK(block) (((block) * BYTES_PER_BLOCK + (uintptr_t)MP_STATE_MEM(gc_pool_start)))
Damien's avatar
Damien committed
86 87
#define ATB_FROM_BLOCK(bl) ((bl) / BLOCKS_PER_ATB)

88 89 90 91 92 93
#if MICROPY_ENABLE_FINALISER
// FTB = finaliser table byte
// if set, then the corresponding block may have a finaliser

#define BLOCKS_PER_FTB (8)

94 95 96
#define FTB_GET(block) ((MP_STATE_MEM(gc_finaliser_table_start)[(block) / BLOCKS_PER_FTB] >> ((block) & 7)) & 1)
#define FTB_SET(block) do { MP_STATE_MEM(gc_finaliser_table_start)[(block) / BLOCKS_PER_FTB] |= (1 << ((block) & 7)); } while (0)
#define FTB_CLEAR(block) do { MP_STATE_MEM(gc_finaliser_table_start)[(block) / BLOCKS_PER_FTB] &= (~(1 << ((block) & 7))); } while (0)
97 98
#endif

99
#if MICROPY_PY_THREAD && !MICROPY_PY_THREAD_GIL
100 101 102 103 104 105 106
#define GC_ENTER() mp_thread_mutex_lock(&MP_STATE_MEM(gc_mutex), 1)
#define GC_EXIT() mp_thread_mutex_unlock(&MP_STATE_MEM(gc_mutex))
#else
#define GC_ENTER()
#define GC_EXIT()
#endif

107 108 109
// TODO waste less memory; currently requires that all entries in alloc_table have a corresponding block in pool
void gc_init(void *start, void *end) {
    // align end pointer on block boundary
110
    end = (void*)((uintptr_t)end & (~(BYTES_PER_BLOCK - 1)));
111
    DEBUG_printf("Initializing GC heap: %p..%p = " UINT_FMT " bytes\n", start, end, (byte*)end - (byte*)start);
112 113 114 115 116 117

    // calculate parameters for GC (T=total, A=alloc table, F=finaliser table, P=pool; all in bytes):
    // T = A + F + P
    //     F = A * BLOCKS_PER_ATB / BLOCKS_PER_FTB
    //     P = A * BLOCKS_PER_ATB * BYTES_PER_BLOCK
    // => T = A * (1 + BLOCKS_PER_ATB / BLOCKS_PER_FTB + BLOCKS_PER_ATB * BYTES_PER_BLOCK)
118
    size_t total_byte_len = (byte*)end - (byte*)start;
119
#if MICROPY_ENABLE_FINALISER
120
    MP_STATE_MEM(gc_alloc_table_byte_len) = total_byte_len * BITS_PER_BYTE / (BITS_PER_BYTE + BITS_PER_BYTE * BLOCKS_PER_ATB / BLOCKS_PER_FTB + BITS_PER_BYTE * BLOCKS_PER_ATB * BYTES_PER_BLOCK);
121
#else
122
    MP_STATE_MEM(gc_alloc_table_byte_len) = total_byte_len / (1 + BITS_PER_BYTE / 2 * BYTES_PER_BLOCK);
123 124
#endif

125
    MP_STATE_MEM(gc_alloc_table_start) = (byte*)start;
mux's avatar
mux committed
126

127
#if MICROPY_ENABLE_FINALISER
128
    size_t gc_finaliser_table_byte_len = (MP_STATE_MEM(gc_alloc_table_byte_len) * BLOCKS_PER_ATB + BLOCKS_PER_FTB - 1) / BLOCKS_PER_FTB;
129
    MP_STATE_MEM(gc_finaliser_table_start) = MP_STATE_MEM(gc_alloc_table_start) + MP_STATE_MEM(gc_alloc_table_byte_len);
130
#endif
mux's avatar
mux committed
131

132
    size_t gc_pool_block_len = MP_STATE_MEM(gc_alloc_table_byte_len) * BLOCKS_PER_ATB;
133 134
    MP_STATE_MEM(gc_pool_start) = (byte*)end - gc_pool_block_len * BYTES_PER_BLOCK;
    MP_STATE_MEM(gc_pool_end) = end;
135

136
#if MICROPY_ENABLE_FINALISER
137
    assert(MP_STATE_MEM(gc_pool_start) >= MP_STATE_MEM(gc_finaliser_table_start) + gc_finaliser_table_byte_len);
138 139
#endif

140
    // clear ATBs
141
    memset(MP_STATE_MEM(gc_alloc_table_start), 0, MP_STATE_MEM(gc_alloc_table_byte_len));
142

143 144
#if MICROPY_ENABLE_FINALISER
    // clear FTBs
145
    memset(MP_STATE_MEM(gc_finaliser_table_start), 0, gc_finaliser_table_byte_len);
146
#endif
mux's avatar
mux committed
147

Damien George's avatar
Damien George committed
148
    // set last free ATB index to start of heap
149
    MP_STATE_MEM(gc_last_free_atb_index) = 0;
Damien George's avatar
Damien George committed
150

151
    // unlock the GC
152
    MP_STATE_MEM(gc_lock_depth) = 0;
153

154
    // allow auto collection
155
    MP_STATE_MEM(gc_auto_collect_enabled) = 1;
156

157 158 159 160 161 162
    #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

163 164 165 166
    #if MICROPY_PY_THREAD
    mp_thread_mutex_init(&MP_STATE_MEM(gc_mutex));
    #endif

167
    DEBUG_printf("GC layout:\n");
168
    DEBUG_printf("  alloc table at %p, length " UINT_FMT " bytes, " UINT_FMT " blocks\n", MP_STATE_MEM(gc_alloc_table_start), MP_STATE_MEM(gc_alloc_table_byte_len), MP_STATE_MEM(gc_alloc_table_byte_len) * BLOCKS_PER_ATB);
169
#if MICROPY_ENABLE_FINALISER
170
    DEBUG_printf("  finaliser table at %p, length " UINT_FMT " bytes, " UINT_FMT " blocks\n", MP_STATE_MEM(gc_finaliser_table_start), gc_finaliser_table_byte_len, gc_finaliser_table_byte_len * BLOCKS_PER_FTB);
171
#endif
172
    DEBUG_printf("  pool at %p, length " UINT_FMT " bytes, " UINT_FMT " blocks\n", MP_STATE_MEM(gc_pool_start), gc_pool_block_len * BYTES_PER_BLOCK, gc_pool_block_len);
173 174
}

175
void gc_lock(void) {
176
    GC_ENTER();
177
    MP_STATE_MEM(gc_lock_depth)++;
178
    GC_EXIT();
179 180 181
}

void gc_unlock(void) {
182
    GC_ENTER();
183
    MP_STATE_MEM(gc_lock_depth)--;
184
    GC_EXIT();
185 186
}

187
bool gc_is_locked(void) {
188
    return MP_STATE_MEM(gc_lock_depth) != 0;
189 190
}

191
// ptr should be of type void*
192
#define VERIFY_PTR(ptr) ( \
193 194 195
        ((uintptr_t)(ptr) & (BYTES_PER_BLOCK - 1)) == 0      /* must be aligned on a block */ \
        && ptr >= (void*)MP_STATE_MEM(gc_pool_start)     /* must be above start of pool */ \
        && ptr < (void*)MP_STATE_MEM(gc_pool_end)        /* must be below end of pool */ \
196 197
    )

198 199 200 201 202 203 204 205
#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

206 207 208 209 210 211
// 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.
212
    size_t sp = 0;
213
    for (;;) {
214
        // work out number of consecutive blocks in the chain starting with this one
215
        size_t n_blocks = 0;
Damien's avatar
Damien committed
216 217 218 219 220
        do {
            n_blocks += 1;
        } while (ATB_GET_KIND(block + n_blocks) == AT_TAIL);

        // check this block's children
221 222 223
        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;
224 225 226 227 228 229 230
            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);
231 232
                    if (sp < MICROPY_ALLOC_GC_STACK_SIZE) {
                        MP_STATE_MEM(gc_stack)[sp++] = childblock;
233 234 235 236 237
                    } else {
                        MP_STATE_MEM(gc_stack_overflow) = 1;
                    }
                }
            }
Damien's avatar
Damien committed
238
        }
239 240

        // Are there any blocks on the stack?
241
        if (sp == 0) {
242 243 244 245
            break; // No, stack is empty, we're done.
        }

        // pop the next block off the stack
246
        block = MP_STATE_MEM(gc_stack)[--sp];
Damien's avatar
Damien committed
247 248 249
    }
}

250
STATIC void gc_deal_with_stack_overflow(void) {
251 252
    while (MP_STATE_MEM(gc_stack_overflow)) {
        MP_STATE_MEM(gc_stack_overflow) = 0;
Damien's avatar
Damien committed
253 254

        // scan entire memory looking for blocks which have been marked but not their children
255
        for (size_t block = 0; block < MP_STATE_MEM(gc_alloc_table_byte_len) * BLOCKS_PER_ATB; block++) {
Damien's avatar
Damien committed
256 257
            // trace (again) if mark bit set
            if (ATB_GET_KIND(block) == AT_MARK) {
258
                gc_mark_subtree(block);
Damien's avatar
Damien committed
259 260 261 262 263
            }
        }
    }
}

264
STATIC void gc_sweep(void) {
265
    #if MICROPY_PY_GC_COLLECT_RETVAL
266
    MP_STATE_MEM(gc_collected) = 0;
267
    #endif
Damien's avatar
Damien committed
268 269
    // free unmarked heads and their tails
    int free_tail = 0;
270
    for (size_t block = 0; block < MP_STATE_MEM(gc_alloc_table_byte_len) * BLOCKS_PER_ATB; block++) {
Damien's avatar
Damien committed
271 272
        switch (ATB_GET_KIND(block)) {
            case AT_HEAD:
273 274
#if MICROPY_ENABLE_FINALISER
                if (FTB_GET(block)) {
275 276
                    mp_obj_base_t *obj = (mp_obj_base_t*)PTR_FROM_BLOCK(block);
                    if (obj->type != NULL) {
277 278
                        // if the object has a type then see if it has a __del__ method
                        mp_obj_t dest[2];
279
                        mp_load_method_maybe(MP_OBJ_FROM_PTR(obj), MP_QSTR___del__, dest);
280
                        if (dest[0] != MP_OBJ_NULL) {
281 282 283 284 285 286 287 288
                            // 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
289
                        }
mux's avatar
mux committed
290
                    }
291 292
                    // clear finaliser flag
                    FTB_CLEAR(block);
mux's avatar
mux committed
293
                }
294
#endif
Damien's avatar
Damien committed
295
                free_tail = 1;
296
                DEBUG_printf("gc_sweep(%p)\n", PTR_FROM_BLOCK(block));
297
                #if MICROPY_PY_GC_COLLECT_RETVAL
298
                MP_STATE_MEM(gc_collected)++;
299
                #endif
Damien's avatar
Damien committed
300 301 302 303 304
                // fall through to free the head

            case AT_TAIL:
                if (free_tail) {
                    ATB_ANY_TO_FREE(block);
305 306 307
                    #if CLEAR_ON_SWEEP
                    memset((void*)PTR_FROM_BLOCK(block), 0, BYTES_PER_BLOCK);
                    #endif
Damien's avatar
Damien committed
308 309 310 311 312 313 314 315 316 317 318
                }
                break;

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

319
void gc_collect_start(void) {
320 321
    GC_ENTER();
    MP_STATE_MEM(gc_lock_depth)++;
322 323 324
    #if MICROPY_GC_ALLOC_THRESHOLD
    MP_STATE_MEM(gc_alloc_amount) = 0;
    #endif
325
    MP_STATE_MEM(gc_stack_overflow) = 0;
326

327 328 329
    // 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.
330 331 332
    #if defined(MP_STATE_PTR)
    void **ptrs = (void**)(void*)MP_STATE_PTR;
    #else
333
    void **ptrs = (void**)(void*)&mp_state_ctx;
334
    #endif
335
    gc_collect_root(ptrs, offsetof(mp_state_ctx_t, vm.qstr_last_chunk) / sizeof(void*));
336

337
    #if MICROPY_ENABLE_PYSTACK
338
    // Trace root pointers from the Python stack.
339 340 341
    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
Damien's avatar
Damien committed
342 343
}

344 345 346
void gc_collect_root(void **ptrs, size_t len) {
    for (size_t i = 0; i < len; i++) {
        void *ptr = ptrs[i];
347 348 349
        if (VERIFY_PTR(ptr)) {
            size_t block = BLOCK_FROM_PTR(ptr);
            if (ATB_GET_KIND(block) == AT_HEAD) {
350
                // An unmarked head: mark it, and mark all its children
351 352
                TRACE_MARK(block, ptr);
                ATB_HEAD_TO_MARK(block);
353
                gc_mark_subtree(block);
354 355
            }
        }
Damien's avatar
Damien committed
356 357 358
    }
}

359
void gc_collect_end(void) {
Damien's avatar
Damien committed
360 361
    gc_deal_with_stack_overflow();
    gc_sweep();
362
    MP_STATE_MEM(gc_last_free_atb_index) = 0;
363 364
    MP_STATE_MEM(gc_lock_depth)--;
    GC_EXIT();
365
}
Damien's avatar
Damien committed
366

367
void gc_info(gc_info_t *info) {
368
    GC_ENTER();
369
    info->total = MP_STATE_MEM(gc_pool_end) - MP_STATE_MEM(gc_pool_start);
370 371
    info->used = 0;
    info->free = 0;
372
    info->max_free = 0;
373 374 375
    info->num_1block = 0;
    info->num_2block = 0;
    info->max_block = 0;
376
    bool finish = false;
377
    for (size_t block = 0, len = 0, len_free = 0; !finish;) {
378
        size_t kind = ATB_GET_KIND(block);
379
        switch (kind) {
Damien's avatar
Damien committed
380
            case AT_FREE:
381
                info->free += 1;
382
                len_free += 1;
383
                len = 0;
Damien's avatar
Damien committed
384 385 386
                break;

            case AT_HEAD:
387 388 389 390
                info->used += 1;
                len = 1;
                break;

Damien's avatar
Damien committed
391
            case AT_TAIL:
392 393
                info->used += 1;
                len += 1;
Damien's avatar
Damien committed
394 395 396
                break;

            case AT_MARK:
397
                // shouldn't happen
Damien's avatar
Damien committed
398 399
                break;
        }
400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416

        block++;
        finish = (block == MP_STATE_MEM(gc_alloc_table_byte_len) * BLOCKS_PER_ATB);
        // Get next block type if possible
        if (!finish) {
            kind = ATB_GET_KIND(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;
            }
417 418 419 420 421 422
            if (finish || kind == AT_HEAD) {
                if (len_free > info->max_free) {
                    info->max_free = len_free;
                }
                len_free = 0;
            }
423
        }
Damien's avatar
Damien committed
424 425
    }

426 427
    info->used *= BYTES_PER_BLOCK;
    info->free *= BYTES_PER_BLOCK;
428
    GC_EXIT();
Damien's avatar
Damien committed
429 430
}

431
void *gc_alloc(size_t n_bytes, bool has_finaliser) {
432
    size_t n_blocks = ((n_bytes + BYTES_PER_BLOCK - 1) & (~(BYTES_PER_BLOCK - 1))) / BYTES_PER_BLOCK;
433
    DEBUG_printf("gc_alloc(" UINT_FMT " bytes -> " UINT_FMT " blocks)\n", n_bytes, n_blocks);
Damien's avatar
Damien committed
434

435 436
    // check for 0 allocation
    if (n_blocks == 0) {
437
        return NULL;
438 439
    }

440 441 442 443 444
    GC_ENTER();

    // check if GC is locked
    if (MP_STATE_MEM(gc_lock_depth) > 0) {
        GC_EXIT();
Damien's avatar
Damien committed
445 446 447
        return NULL;
    }

448 449 450 451
    size_t i;
    size_t end_block;
    size_t start_block;
    size_t n_free = 0;
452
    int collected = !MP_STATE_MEM(gc_auto_collect_enabled);
453 454 455 456 457 458 459 460 461

    #if MICROPY_GC_ALLOC_THRESHOLD
    if (!collected && MP_STATE_MEM(gc_alloc_amount) >= MP_STATE_MEM(gc_alloc_threshold)) {
        GC_EXIT();
        gc_collect();
        GC_ENTER();
    }
    #endif

Damien's avatar
Damien committed
462 463 464
    for (;;) {

        // look for a run of n_blocks available blocks
465 466
        for (i = MP_STATE_MEM(gc_last_free_atb_index); i < MP_STATE_MEM(gc_alloc_table_byte_len); i++) {
            byte a = MP_STATE_MEM(gc_alloc_table_start)[i];
Damien George's avatar
Damien George committed
467 468 469 470 471
            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; }
        }
Damien's avatar
Damien committed
472

473
        GC_EXIT();
Damien's avatar
Damien committed
474 475 476 477
        // nothing found!
        if (collected) {
            return NULL;
        }
478
        DEBUG_printf("gc_alloc(" UINT_FMT "): no free mem, triggering GC\n", n_bytes);
Damien's avatar
Damien committed
479 480
        gc_collect();
        collected = 1;
481
        GC_ENTER();
Damien's avatar
Damien committed
482 483 484 485 486 487 488 489
    }

    // found, ending at block i inclusive
found:
    // get starting and end blocks, both inclusive
    end_block = i;
    start_block = i - n_free + 1;

490 491 492
    // 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
493 494
    // 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).
495
    if (n_free == 1) {
496
        MP_STATE_MEM(gc_last_free_atb_index) = (i + 1) / BLOCKS_PER_ATB;
497
    }
Damien George's avatar
Damien George committed
498

Damien's avatar
Damien committed
499 500 501 502 503
    // mark first block as used head
    ATB_FREE_TO_HEAD(start_block);

    // mark rest of blocks as used tail
    // TODO for a run of many blocks can make this more efficient
504
    for (size_t bl = start_block + 1; bl <= end_block; bl++) {
Damien's avatar
Damien committed
505 506 507
        ATB_FREE_TO_TAIL(bl);
    }

508
    // get pointer to first block
509
    // we must create this pointer before unlocking the GC so a collection can find it
510
    void *ret_ptr = (void*)(MP_STATE_MEM(gc_pool_start) + start_block * BYTES_PER_BLOCK);
511
    DEBUG_printf("gc_alloc(%p)\n", ret_ptr);
512

513 514 515 516
    #if MICROPY_GC_ALLOC_THRESHOLD
    MP_STATE_MEM(gc_alloc_amount) += n_blocks;
    #endif

517 518
    GC_EXIT();

519 520 521 522
    #if MICROPY_GC_CONSERVATIVE_CLEAR
    // be conservative and zero out all the newly allocated blocks
    memset((byte*)ret_ptr, 0, (end_block - start_block + 1) * BYTES_PER_BLOCK);
    #else
523
    // zero out the additional bytes of the newly allocated blocks
524 525 526 527
    // This is needed because the blocks may have previously held pointers
    // to the heap and will not be set to something else if the caller
    // doesn't actually use the entire block.  As such they will continue
    // to point to the heap and may prevent other blocks from being reclaimed.
528
    memset((byte*)ret_ptr + n_bytes, 0, (end_block - start_block + 1) * BYTES_PER_BLOCK - n_bytes);
529
    #endif
530

531
    #if MICROPY_ENABLE_FINALISER
532
    if (has_finaliser) {
533
        // clear type pointer in case it is never set
534
        ((mp_obj_base_t*)ret_ptr)->type = NULL;
535
        // set mp_obj flag only if it has a finaliser
536
        GC_ENTER();
537
        FTB_SET(start_block);
538
        GC_EXIT();
mux's avatar
mux committed
539
    }
540 541 542
    #else
    (void)has_finaliser;
    #endif
mux's avatar
mux committed
543

544 545 546 547
    #if EXTENSIVE_HEAP_PROFILING
    gc_dump_alloc_table();
    #endif

548
    return ret_ptr;
Damien's avatar
Damien committed
549 550
}

551
/*
552
void *gc_alloc(mp_uint_t n_bytes) {
mux's avatar
mux committed
553 554 555
    return _gc_alloc(n_bytes, false);
}

556
void *gc_alloc_with_finaliser(mp_uint_t n_bytes) {
mux's avatar
mux committed
557 558
    return _gc_alloc(n_bytes, true);
}
559
*/
mux's avatar
mux committed
560

561
// force the freeing of a piece of memory
562
// TODO: freeing here does not call finaliser
563
void gc_free(void *ptr) {
564
    GC_ENTER();
565
    if (MP_STATE_MEM(gc_lock_depth) > 0) {
566
        // TODO how to deal with this error?
567
        GC_EXIT();
568
        return;
569 570
    }

stijn's avatar
stijn committed
571
    DEBUG_printf("gc_free(%p)\n", ptr);
572

573 574 575 576 577
    if (ptr == NULL) {
        GC_EXIT();
    } else {
        // get the GC block number corresponding to this pointer
        assert(VERIFY_PTR(ptr));
578
        size_t block = BLOCK_FROM_PTR(ptr);
579
        assert(ATB_GET_KIND(block) == AT_HEAD);
580

581 582 583
        #if MICROPY_ENABLE_FINALISER
        FTB_CLEAR(block);
        #endif
584

585 586 587
        // 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;
588
        }
589 590 591 592 593 594 595

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

596
        GC_EXIT();
597 598 599 600

        #if EXTENSIVE_HEAP_PROFILING
        gc_dump_alloc_table();
        #endif
601 602 603
    }
}

604
size_t gc_nbytes(const void *ptr) {
605
    GC_ENTER();
606
    if (VERIFY_PTR(ptr)) {
607
        size_t block = BLOCK_FROM_PTR(ptr);
Damien's avatar
Damien committed
608 609
        if (ATB_GET_KIND(block) == AT_HEAD) {
            // work out number of consecutive blocks in the chain starting with this on
610
            size_t n_blocks = 0;
Damien's avatar
Damien committed
611 612 613
            do {
                n_blocks += 1;
            } while (ATB_GET_KIND(block + n_blocks) == AT_TAIL);
614
            GC_EXIT();
Damien's avatar
Damien committed
615 616 617 618 619
            return n_blocks * BYTES_PER_BLOCK;
        }
    }

    // invalid pointer
620
    GC_EXIT();
Damien's avatar
Damien committed
621 622 623
    return 0;
}

mux's avatar
mux committed
624
#if 0
625
// old, simple realloc that didn't expand memory in place
626 627
void *gc_realloc(void *ptr, mp_uint_t n_bytes) {
    mp_uint_t n_existing = gc_nbytes(ptr);
628 629 630
    if (n_bytes <= n_existing) {
        return ptr;
    } else {
631 632 633 634
        bool has_finaliser;
        if (ptr == NULL) {
            has_finaliser = false;
        } else {
635
#if MICROPY_ENABLE_FINALISER
636
            has_finaliser = FTB_GET(BLOCK_FROM_PTR((mp_uint_t)ptr));
637
#else
638
            has_finaliser = false;
639
#endif
640 641
        }
        void *ptr2 = gc_alloc(n_bytes, has_finaliser);
642 643 644 645 646 647 648 649
        if (ptr2 == NULL) {
            return ptr2;
        }
        memcpy(ptr2, ptr, n_existing);
        gc_free(ptr);
        return ptr2;
    }
}
650 651

#else // Alternative gc_realloc impl
652

653
void *gc_realloc(void *ptr_in, size_t n_bytes, bool allow_move) {
654
    // check for pure allocation
mux's avatar
mux committed
655
    if (ptr_in == NULL) {
656
        return gc_alloc(n_bytes, false);
mux's avatar
mux committed
657 658
    }

659 660 661 662 663 664
    // check for pure free
    if (n_bytes == 0) {
        gc_free(ptr_in);
        return NULL;
    }

665
    void *ptr = ptr_in;
666

667 668
    GC_ENTER();

669 670 671 672 673
    if (MP_STATE_MEM(gc_lock_depth) > 0) {
        GC_EXIT();
        return NULL;
    }

674 675 676 677 678
    // get the GC block number corresponding to this pointer
    assert(VERIFY_PTR(ptr));
    size_t block = BLOCK_FROM_PTR(ptr);
    assert(ATB_GET_KIND(block) == AT_HEAD);

679
    // compute number of new blocks that are requested
680
    size_t new_blocks = (n_bytes + BYTES_PER_BLOCK - 1) / BYTES_PER_BLOCK;
mux's avatar
mux committed
681

682 683 684 685 686 687
    // Get the total number of consecutive blocks that are already allocated to
    // this chunk of memory, and then count the number of free blocks following
    // it.  Stop if we reach the end of the heap, or if we find enough extra
    // free blocks to satisfy the realloc.  Note that we need to compute the
    // total size of the existing memory chunk so we can correctly and
    // efficiently shrink it (see below for shrinking code).
688 689 690 691
    size_t n_free   = 0;
    size_t n_blocks = 1; // counting HEAD block
    size_t max_block = MP_STATE_MEM(gc_alloc_table_byte_len) * BLOCKS_PER_ATB;
    for (size_t bl = block + n_blocks; bl < max_block; bl++) {
692 693 694 695
        byte block_type = ATB_GET_KIND(bl);
        if (block_type == AT_TAIL) {
            n_blocks++;
            continue;
mux's avatar
mux committed
696
        }
697 698 699 700 701 702 703
        if (block_type == AT_FREE) {
            n_free++;
            if (n_blocks + n_free >= new_blocks) {
                // stop as soon as we find enough blocks for n_bytes
                break;
            }
            continue;
704 705 706 707 708 709
        }
        break;
    }

    // return original ptr if it already has the requested number of blocks
    if (new_blocks == n_blocks) {
710
        GC_EXIT();
711 712
        return ptr_in;
    }
mux's avatar
mux committed
713

714 715 716
    // check if we can shrink the allocated area
    if (new_blocks < n_blocks) {
        // free unneeded tail blocks
717
        for (size_t bl = block + new_blocks, count = n_blocks - new_blocks; count > 0; bl++, count--) {
718
            ATB_ANY_TO_FREE(bl);
719
        }
720 721

        // set the last_free pointer to end of this block if it's earlier in the heap
722 723
        if ((block + new_blocks) / BLOCKS_PER_ATB < MP_STATE_MEM(gc_last_free_atb_index)) {
            MP_STATE_MEM(gc_last_free_atb_index) = (block + new_blocks) / BLOCKS_PER_ATB;
724 725
        }

726 727
        GC_EXIT();

728 729 730 731
        #if EXTENSIVE_HEAP_PROFILING
        gc_dump_alloc_table();
        #endif

732 733
        return ptr_in;
    }
734

735 736 737
    // check if we can expand in place
    if (new_blocks <= n_blocks + n_free) {
        // mark few more blocks as used tail
738
        for (size_t bl = block + n_blocks; bl < block + new_blocks; bl++) {
739 740 741
            assert(ATB_GET_KIND(bl) == AT_FREE);
            ATB_FREE_TO_TAIL(bl);
        }
742

743 744
        GC_EXIT();

745 746 747 748
        #if MICROPY_GC_CONSERVATIVE_CLEAR
        // be conservative and zero out all the newly allocated blocks
        memset((byte*)ptr_in + n_blocks * BYTES_PER_BLOCK, 0, (new_blocks - n_blocks) * BYTES_PER_BLOCK);
        #else
749
        // zero out the additional bytes of the newly allocated blocks (see comment above in gc_alloc)
750
        memset((byte*)ptr_in + n_bytes, 0, new_blocks * BYTES_PER_BLOCK - n_bytes);
751
        #endif
752

753 754 755 756
        #if EXTENSIVE_HEAP_PROFILING
        gc_dump_alloc_table();
        #endif

757 758
        return ptr_in;
    }
mux's avatar
mux committed
759

760 761 762 763 764 765
    #if MICROPY_ENABLE_FINALISER
    bool ftb_state = FTB_GET(block);
    #else
    bool ftb_state = false;
    #endif

766 767
    GC_EXIT();

768 769 770 771 772
    if (!allow_move) {
        // not allowed to move memory block so return failure
        return NULL;
    }

773
    // can't resize inplace; try to find a new contiguous chain
774
    void *ptr_out = gc_alloc(n_bytes, ftb_state);
775 776 777 778

    // check that the alloc succeeded
    if (ptr_out == NULL) {
        return NULL;
Damien's avatar
Damien committed
779
    }
mux's avatar
mux committed
780

stijn's avatar
stijn committed
781
    DEBUG_printf("gc_realloc(%p -> %p)\n", ptr_in, ptr_out);
782 783 784
    memcpy(ptr_out, ptr_in, n_blocks * BYTES_PER_BLOCK);
    gc_free(ptr_in);
    return ptr_out;
Damien's avatar
Damien committed
785
}
786
#endif // Alternative gc_realloc impl
mux's avatar
mux committed
787

788 789
#if EXTENSIVE_HEAP_PROFILING || MICROPY_PY_MICROPYTHON_MEM_INFO

790
void gc_dump_info(void) {
791 792
    gc_info_t info;
    gc_info(&info);
793 794
    mp_printf(&mp_plat_print, "GC: total: %u, used: %u, free: %u\n",
        (uint)info.total, (uint)info.used, (uint)info.free);
795 796
    mp_printf(&mp_plat_print, " No. of 1-blocks: %u, 2-blocks: %u, max blk sz: %u, max free sz: %u\n",
           (uint)info.num_1block, (uint)info.num_2block, (uint)info.max_block, (uint)info.max_free);
797 798
}

799
void gc_dump_alloc_table(void) {
800
    GC_ENTER();
801
    static const size_t DUMP_BYTES_PER_LINE = 64;
802 803 804
    #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.
805
    mp_printf(&mp_plat_print, "GC memory layout; from %p:", MP_STATE_MEM(gc_pool_start));
806
    #endif
807
    for (size_t bl = 0; bl < MP_STATE_MEM(gc_alloc_table_byte_len) * BLOCKS_PER_ATB; bl++) {
808 809 810 811
        if (bl % DUMP_BYTES_PER_LINE == 0) {
            // a new line of blocks
            {
                // check if this line contains only free blocks
812
                size_t bl2 = bl;
813
                while (bl2 < MP_STATE_MEM(gc_alloc_table_byte_len) * BLOCKS_PER_ATB && ATB_GET_KIND(bl2) == AT_FREE) {
814 815 816 817
                    bl2++;
                }
                if (bl2 - bl >= 2 * DUMP_BYTES_PER_LINE) {
                    // there are at least 2 lines containing only free blocks, so abbreviate their printing
818
                    mp_printf(&mp_plat_print, "\n       (%u lines all free)", (uint)(bl2 - bl) / DUMP_BYTES_PER_LINE);
819
                    bl = bl2 & (~(DUMP_BYTES_PER_LINE - 1));
820
                    if (bl >= MP_STATE_MEM(gc_alloc_table_byte_len) * BLOCKS_PER_ATB) {
821
                        // got to end of heap
822 823 824 825 826
                        break;
                    }
                }
            }
            // print header for new line of blocks
827
            // (the cast to uint32_t is for 16-bit ports)
828
            //mp_printf(&mp_plat_print, "\n%05x: ", (uint)(PTR_FROM_BLOCK(bl) & (uint32_t)0xfffff));
829
            mp_printf(&mp_plat_print, "\n%05x: ", (uint)((bl * BYTES_PER_BLOCK) & (uint32_t)0xfffff));
830 831
        }
        int c = ' ';
832
        switch (ATB_GET_KIND(bl)) {
833
            case AT_FREE: c = '.'; break;
834 835 836
            /* this prints out if the object is reachable from BSS or STACK (for unix only)
            case AT_HEAD: {
                c = 'h';
837 838
                void **ptrs = (void**)(void*)&mp_state_ctx;
                mp_uint_t len = offsetof(mp_state_ctx_t, vm.stack_top) / sizeof(mp_uint_t);
839 840 841 842 843 844 845 846 847
                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;
848
                    len = ((mp_uint_t)MP_STATE_THREAD(stack_top) - (mp_uint_t)&c) / sizeof(mp_uint_t);
849 850 851 852 853 854 855 856 857 858 859
                    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;
            }
            */
860
            /* this prints the uPy object type of the head block */
861
            case AT_HEAD: {
862 863 864 865
                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'; }
866
                else if (*ptr == &mp_type_str || *ptr == &mp_type_bytes) { c = 'S'; }
867 868 869 870 871 872
                #if MICROPY_PY_BUILTINS_BYTEARRAY
                else if (*ptr == &mp_type_bytearray) { c = 'A'; }
                #endif
                #if MICROPY_PY_ARRAY
                else if (*ptr == &mp_type_array) { c = 'A'; }
                #endif
873
                #if MICROPY_PY_BUILTINS_FLOAT
874
                else if (*ptr == &mp_type_float) { c = 'F'; }
875
                #endif
876 877
                else if (*ptr == &mp_type_fun_bc) { c = 'B'; }
                else if (*ptr == &mp_type_module) { c = 'M'; }
878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897
                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
                }
898 899
                break;
            }
900
            case AT_TAIL: c = '='; break;
901
            case AT_MARK: c = 'm'; break;
902
        }
903
        mp_printf(&mp_plat_print, "%c", c);
904
    }
905
    mp_print_str(&mp_plat_print, "\n");
906
    GC_EXIT();
907 908
}

909 910
#endif // EXTENSIVE_HEAP_PROFILING || MICROPY_PY_MICROPYTHON_MEM_INFO

911
#if DEBUG_PRINT
912
void gc_test(void) {
913 914 915
    mp_uint_t len = 500;
    mp_uint_t *heap = malloc(len);
    gc_init(heap, heap + len / sizeof(mp_uint_t));
Damien's avatar
Damien committed
916 917
    void *ptrs[100];
    {
918
        mp_uint_t **p = gc_alloc(16, false);
919 920 921 922
        p[0] = gc_alloc(64, false);
        p[1] = gc_alloc(1, false);
        p[2] = gc_alloc(1, false);
        p[3] = gc_alloc(1, false);
923
        mp_uint_t ***p2 = gc_alloc(16, false);
Damien's avatar
Damien committed
924 925 926 927
        p2[0] = p;
        p2[1] = p;
        ptrs[0] = p2;
    }
928
    for (int i = 0; i < 25; i+=2) {
929
        mp_uint_t *p = gc_alloc(i, false);
Damien's avatar
Damien committed
930 931 932 933 934 935
        printf("p=%p\n", p);
        if (i & 3) {
            //ptrs[i] = p;
        }
    }

936
    printf("Before GC:\n");
937
    gc_dump_alloc_table();
938 939 940 941 942
    printf("Starting GC...\n");
    gc_collect_start();
    gc_collect_root(ptrs, sizeof(ptrs) / sizeof(void*));
    gc_collect_end();
    printf("After GC:\n");
943
    gc_dump_alloc_table();
Damien's avatar
Damien committed
944
}
945
#endif
946

947
#endif // MICROPY_ENABLE_GC && !MICROPY_ENABLE_IMMORTAL_GC