gc.c 22.2 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/*
 * This file is part of the Micro Python project, http://micropython.org/
 *
 * 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
#include <stdio.h>
#include <string.h>
mux's avatar
mux committed
30
#include <stdbool.h>
Damien's avatar
Damien committed
31

32
#include "mpconfig.h"
33
#include "misc.h"
Damien's avatar
Damien committed
34
35
#include "gc.h"

mux's avatar
mux committed
36
37
#include "qstr.h"
#include "obj.h"
mux's avatar
mux committed
38
#include "runtime.h"
mux's avatar
mux committed
39

40
41
#if MICROPY_ENABLE_GC

stijn's avatar
stijn committed
42
#if 0 // print debugging info
43
#define DEBUG_PRINT (1)
44
#define DEBUG_printf DEBUG_printf
45
#else // don't print debugging info
46
#define DEBUG_printf(...) (void)0
47
48
#endif

Damien's avatar
Damien committed
49
50
51
52
#define WORDS_PER_BLOCK (4)
#define BYTES_PER_BLOCK (WORDS_PER_BLOCK * BYTES_PER_WORD)
#define STACK_SIZE (64) // tunable; minimum is 1

53
54
STATIC byte *gc_alloc_table_start;
STATIC machine_uint_t gc_alloc_table_byte_len;
55
56
57
#if MICROPY_ENABLE_FINALISER
STATIC byte *gc_finaliser_table_start;
#endif
58
59
STATIC machine_uint_t *gc_pool_start;
STATIC machine_uint_t *gc_pool_end;
Damien's avatar
Damien committed
60

61
62
63
STATIC int gc_stack_overflow;
STATIC machine_uint_t gc_stack[STACK_SIZE];
STATIC machine_uint_t *gc_sp;
64
STATIC machine_uint_t gc_lock_depth;
Damien's avatar
Damien committed
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

// 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)))
#define ATB_GET_KIND(block) ((gc_alloc_table_start[(block) / BLOCKS_PER_ATB] >> BLOCK_SHIFT(block)) & 3)
#define ATB_ANY_TO_FREE(block) do { gc_alloc_table_start[(block) / BLOCKS_PER_ATB] &= (~(AT_MARK << BLOCK_SHIFT(block))); } while (0)
#define ATB_FREE_TO_HEAD(block) do { gc_alloc_table_start[(block) / BLOCKS_PER_ATB] |= (AT_HEAD << BLOCK_SHIFT(block)); } while (0)
#define ATB_FREE_TO_TAIL(block) do { gc_alloc_table_start[(block) / BLOCKS_PER_ATB] |= (AT_TAIL << BLOCK_SHIFT(block)); } while (0)
#define ATB_HEAD_TO_MARK(block) do { gc_alloc_table_start[(block) / BLOCKS_PER_ATB] |= (AT_MARK << BLOCK_SHIFT(block)); } while (0)
#define ATB_MARK_TO_HEAD(block) do { gc_alloc_table_start[(block) / BLOCKS_PER_ATB] &= (~(AT_TAIL << BLOCK_SHIFT(block))); } while (0)

#define BLOCK_FROM_PTR(ptr) (((ptr) - (machine_uint_t)gc_pool_start) / BYTES_PER_BLOCK)
#define PTR_FROM_BLOCK(block) (((block) * BYTES_PER_BLOCK + (machine_uint_t)gc_pool_start))
#define ATB_FROM_BLOCK(bl) ((bl) / BLOCKS_PER_ATB)

100
101
102
103
104
105
106
107
108
109
110
#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(block) ((gc_finaliser_table_start[(block) / BLOCKS_PER_FTB] >> ((block) & 7)) & 1)
#define FTB_SET(block) do { gc_finaliser_table_start[(block) / BLOCKS_PER_FTB] |= (1 << ((block) & 7)); } while (0)
#define FTB_CLEAR(block) do { gc_finaliser_table_start[(block) / BLOCKS_PER_FTB] &= (~(1 << ((block) & 7))); } while (0)
#endif

111
112
113
114
// 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
    end = (void*)((machine_uint_t)end & (~(BYTES_PER_BLOCK - 1)));
115
    DEBUG_printf("Initializing GC heap: %p..%p = " UINT_FMT " bytes\n", start, end, (byte*)end - (byte*)start);
116
117
118
119
120
121

    // 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)
122
    machine_uint_t total_byte_len = (byte*)end - (byte*)start;
123
124
125
126
127
128
#if MICROPY_ENABLE_FINALISER
    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);
#else
    gc_alloc_table_byte_len = total_byte_len / (1 + BITS_PER_BYTE / 2 * BYTES_PER_BLOCK);
#endif

129
130

    gc_alloc_table_start = (byte*)start;
mux's avatar
mux committed
131

132
133
134
135
#if MICROPY_ENABLE_FINALISER
    machine_uint_t gc_finaliser_table_byte_len = (gc_alloc_table_byte_len * BLOCKS_PER_ATB) / BLOCKS_PER_FTB;
    gc_finaliser_table_start = gc_alloc_table_start + gc_alloc_table_byte_len;
#endif
mux's avatar
mux committed
136

137
    machine_uint_t gc_pool_block_len = gc_alloc_table_byte_len * BLOCKS_PER_ATB;
138
139
    gc_pool_start = (machine_uint_t*)((byte*)end - gc_pool_block_len * BYTES_PER_BLOCK);
    gc_pool_end = (machine_uint_t*)end;
140
141
142
143

    // clear ATBs
    memset(gc_alloc_table_start, 0, gc_alloc_table_byte_len);

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

149
150
151
152
153
154
155
    // allocate first block because gc_pool_start points there and it will never
    // be freed, so allocating 1 block with null pointers will minimise memory loss
    ATB_FREE_TO_HEAD(0);
    for (int i = 0; i < WORDS_PER_BLOCK; i++) {
        gc_pool_start[i] = 0;
    }

156
    // unlock the GC
157
    gc_lock_depth = 0;
158

159
    DEBUG_printf("GC layout:\n");
160
161
162
163
164
    DEBUG_printf("  alloc table at %p, length " UINT_FMT " bytes, " UINT_FMT " blocks\n", gc_alloc_table_start, gc_alloc_table_byte_len, 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", gc_finaliser_table_start, gc_finaliser_table_byte_len, gc_finaliser_table_byte_len * BLOCKS_PER_FTB);
#endif
    DEBUG_printf("  pool at %p, length " UINT_FMT " bytes, " UINT_FMT " blocks\n", gc_pool_start, gc_pool_block_len * BYTES_PER_BLOCK, gc_pool_block_len);
165
166
}

167
168
169
170
171
172
173
174
void gc_lock(void) {
    gc_lock_depth++;
}

void gc_unlock(void) {
    gc_lock_depth--;
}

175
176
177
178
bool gc_is_locked(void) {
    return gc_lock_depth != 0;
}

179
180
181
182
183
184
#define VERIFY_PTR(ptr) ( \
        (ptr & (BYTES_PER_BLOCK - 1)) == 0          /* must be aligned on a block */ \
        && ptr >= (machine_uint_t)gc_pool_start     /* must be above start of pool */ \
        && ptr < (machine_uint_t)gc_pool_end        /* must be below end of pool */ \
    )

Damien's avatar
Damien committed
185
186
#define VERIFY_MARK_AND_PUSH(ptr) \
    do { \
187
        if (VERIFY_PTR(ptr)) { \
Damien's avatar
Damien committed
188
189
190
191
192
193
194
195
196
197
198
199
200
            machine_uint_t _block = BLOCK_FROM_PTR(ptr); \
            if (ATB_GET_KIND(_block) == AT_HEAD) { \
                /* an unmarked head, mark it, and push it on gc stack */ \
                ATB_HEAD_TO_MARK(_block); \
                if (gc_sp < &gc_stack[STACK_SIZE]) { \
                    *gc_sp++ = _block; \
                } else { \
                    gc_stack_overflow = 1; \
                } \
            } \
        } \
    } while (0)

201
STATIC void gc_drain_stack(void) {
Damien's avatar
Damien committed
202
203
204
205
    while (gc_sp > gc_stack) {
        // pop the next block off the stack
        machine_uint_t block = *--gc_sp;

206
        // work out number of consecutive blocks in the chain starting with this one
Damien's avatar
Damien committed
207
208
209
210
211
212
213
214
215
216
217
218
219
220
        machine_uint_t n_blocks = 0;
        do {
            n_blocks += 1;
        } while (ATB_GET_KIND(block + n_blocks) == AT_TAIL);

        // check this block's children
        machine_uint_t *scan = (machine_uint_t*)PTR_FROM_BLOCK(block);
        for (machine_uint_t i = n_blocks * WORDS_PER_BLOCK; i > 0; i--, scan++) {
            machine_uint_t ptr2 = *scan;
            VERIFY_MARK_AND_PUSH(ptr2);
        }
    }
}

221
STATIC void gc_deal_with_stack_overflow(void) {
Damien's avatar
Damien committed
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
    while (gc_stack_overflow) {
        gc_stack_overflow = 0;
        gc_sp = gc_stack;

        // scan entire memory looking for blocks which have been marked but not their children
        for (machine_uint_t block = 0; block < gc_alloc_table_byte_len * BLOCKS_PER_ATB; block++) {
            // trace (again) if mark bit set
            if (ATB_GET_KIND(block) == AT_MARK) {
                *gc_sp++ = block;
                gc_drain_stack();
            }
        }
    }
}

237
238
239
240
#if MICROPY_PY_GC_COLLECT_RETVAL
uint gc_collected;
#endif

241
STATIC void gc_sweep(void) {
242
243
244
    #if MICROPY_PY_GC_COLLECT_RETVAL
    gc_collected = 0;
    #endif
Damien's avatar
Damien committed
245
246
247
248
249
    // free unmarked heads and their tails
    int free_tail = 0;
    for (machine_uint_t block = 0; block < gc_alloc_table_byte_len * BLOCKS_PER_ATB; block++) {
        switch (ATB_GET_KIND(block)) {
            case AT_HEAD:
250
251
252
253
254
255
256
257
258
259
260
#if MICROPY_ENABLE_FINALISER
                if (FTB_GET(block)) {
                    mp_obj_t obj = (mp_obj_t)PTR_FROM_BLOCK(block);
                    if (((mp_obj_base_t*)obj)->type != MP_OBJ_NULL) {
                        // if the object has a type then see if it has a __del__ method
                        mp_obj_t dest[2];
                        mp_load_method_maybe(obj, MP_QSTR___del__, dest);
                        if (dest[0] != MP_OBJ_NULL) {
                            // load_method returned a method
                            mp_call_method_n_kw(0, 0, dest);
                        }
mux's avatar
mux committed
261
                    }
262
263
                    // clear finaliser flag
                    FTB_CLEAR(block);
mux's avatar
mux committed
264
                }
265
#endif
Damien's avatar
Damien committed
266
                free_tail = 1;
267
268
269
                #if MICROPY_PY_GC_COLLECT_RETVAL
                gc_collected++;
                #endif
Damien's avatar
Damien committed
270
271
272
273
                // fall through to free the head

            case AT_TAIL:
                if (free_tail) {
stijn's avatar
stijn committed
274
                    DEBUG_printf("gc_sweep(%p)\n",PTR_FROM_BLOCK(block));
Damien's avatar
Damien committed
275
276
277
278
279
280
281
282
283
284
285
286
                    ATB_ANY_TO_FREE(block);
                }
                break;

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

287
void gc_collect_start(void) {
288
    gc_lock();
Damien's avatar
Damien committed
289
290
291
292
293
294
295
296
297
298
299
300
    gc_stack_overflow = 0;
    gc_sp = gc_stack;
}

void gc_collect_root(void **ptrs, machine_uint_t len) {
    for (machine_uint_t i = 0; i < len; i++) {
        machine_uint_t ptr = (machine_uint_t)ptrs[i];
        VERIFY_MARK_AND_PUSH(ptr);
        gc_drain_stack();
    }
}

301
void gc_collect_end(void) {
Damien's avatar
Damien committed
302
303
    gc_deal_with_stack_overflow();
    gc_sweep();
304
    gc_unlock();
305
}
Damien's avatar
Damien committed
306

307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
void gc_info(gc_info_t *info) {
    info->total = (gc_pool_end - gc_pool_start) * sizeof(machine_uint_t);
    info->used = 0;
    info->free = 0;
    info->num_1block = 0;
    info->num_2block = 0;
    info->max_block = 0;
    for (machine_uint_t block = 0, len = 0; block < gc_alloc_table_byte_len * BLOCKS_PER_ATB; block++) {
        machine_uint_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) {
Damien's avatar
Damien committed
327
            case AT_FREE:
328
329
                info->free += 1;
                len = 0;
Damien's avatar
Damien committed
330
331
332
                break;

            case AT_HEAD:
333
334
335
336
                info->used += 1;
                len = 1;
                break;

Damien's avatar
Damien committed
337
            case AT_TAIL:
338
339
                info->used += 1;
                len += 1;
Damien's avatar
Damien committed
340
341
342
                break;

            case AT_MARK:
343
                // shouldn't happen
Damien's avatar
Damien committed
344
345
346
347
                break;
        }
    }

348
349
    info->used *= BYTES_PER_BLOCK;
    info->free *= BYTES_PER_BLOCK;
Damien's avatar
Damien committed
350
351
}

352
void *gc_alloc(machine_uint_t n_bytes, bool has_finaliser) {
Damien's avatar
Damien committed
353
    machine_uint_t n_blocks = ((n_bytes + BYTES_PER_BLOCK - 1) & (~(BYTES_PER_BLOCK - 1))) / BYTES_PER_BLOCK;
354
    DEBUG_printf("gc_alloc(" UINT_FMT " bytes -> " UINT_FMT " blocks)\n", n_bytes, n_blocks);
Damien's avatar
Damien committed
355

356
357
358
    // check if GC is locked
    if (gc_lock_depth > 0) {
        return NULL;
359
360
    }

Damien's avatar
Damien committed
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
    // check for 0 allocation
    if (n_blocks == 0) {
        return NULL;
    }

    machine_uint_t i;
    machine_uint_t end_block;
    machine_uint_t start_block;
    machine_uint_t n_free = 0;
    int collected = 0;
    for (;;) {

        // look for a run of n_blocks available blocks
        for (i = 0; i < gc_alloc_table_byte_len; i++) {
            byte a = gc_alloc_table_start[i];
            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; }
        }

        // nothing found!
        if (collected) {
            return NULL;
        }
386
        DEBUG_printf("gc_alloc(" UINT_FMT "): no free mem, triggering GC\n", n_bytes);
Damien's avatar
Damien committed
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
        gc_collect();
        collected = 1;
    }

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

    // 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
    for (machine_uint_t bl = start_block + 1; bl <= end_block; bl++) {
        ATB_FREE_TO_TAIL(bl);
    }

406
    // get pointer to first block
407
    void *ret_ptr = (void*)(gc_pool_start + start_block * WORDS_PER_BLOCK);
408
    DEBUG_printf("gc_alloc(%p)\n", ret_ptr);
409

410
    // zero out the additional bytes of the newly allocated blocks
411
412
413
414
    // 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.
415
    memset((byte*)ret_ptr + n_bytes, 0, (end_block - start_block + 1) * BYTES_PER_BLOCK - n_bytes);
416

417
418
#if MICROPY_ENABLE_FINALISER
    if (has_finaliser) {
419
420
        // clear type pointer in case it is never set
        ((mp_obj_base_t*)ret_ptr)->type = MP_OBJ_NULL;
421
422
        // set mp_obj flag only if it has a finaliser
        FTB_SET(start_block);
mux's avatar
mux committed
423
    }
424
#endif
mux's avatar
mux committed
425

426
    return ret_ptr;
Damien's avatar
Damien committed
427
428
}

429
/*
mux's avatar
mux committed
430
431
432
433
void *gc_alloc(machine_uint_t n_bytes) {
    return _gc_alloc(n_bytes, false);
}

434
void *gc_alloc_with_finaliser(machine_uint_t n_bytes) {
mux's avatar
mux committed
435
436
    return _gc_alloc(n_bytes, true);
}
437
*/
mux's avatar
mux committed
438

439
440
// force the freeing of a piece of memory
void gc_free(void *ptr_in) {
441
442
443
    if (gc_lock_depth > 0) {
        // TODO how to deal with this error?
        return;
444
445
    }

446
    machine_uint_t ptr = (machine_uint_t)ptr_in;
stijn's avatar
stijn committed
447
    DEBUG_printf("gc_free(%p)\n", ptr);
448
449
450
451
452
453
454
455
456
457
458
459
460

    if (VERIFY_PTR(ptr)) {
        machine_uint_t block = BLOCK_FROM_PTR(ptr);
        if (ATB_GET_KIND(block) == AT_HEAD) {
            // free head and all of its tail blocks
            do {
                ATB_ANY_TO_FREE(block);
                block += 1;
            } while (ATB_GET_KIND(block) == AT_TAIL);
        }
    }
}

Damien's avatar
Damien committed
461
462
463
machine_uint_t gc_nbytes(void *ptr_in) {
    machine_uint_t ptr = (machine_uint_t)ptr_in;

464
    if (VERIFY_PTR(ptr)) {
Damien's avatar
Damien committed
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
        machine_uint_t block = BLOCK_FROM_PTR(ptr);
        if (ATB_GET_KIND(block) == AT_HEAD) {
            // work out number of consecutive blocks in the chain starting with this on
            machine_uint_t n_blocks = 0;
            do {
                n_blocks += 1;
            } while (ATB_GET_KIND(block + n_blocks) == AT_TAIL);
            return n_blocks * BYTES_PER_BLOCK;
        }
    }

    // invalid pointer
    return 0;
}

mux's avatar
mux committed
480
#if 0
481
// old, simple realloc that didn't expand memory in place
482
483
484
485
486
void *gc_realloc(void *ptr, machine_uint_t n_bytes) {
    machine_uint_t n_existing = gc_nbytes(ptr);
    if (n_bytes <= n_existing) {
        return ptr;
    } else {
487
488
489
490
        bool has_finaliser;
        if (ptr == NULL) {
            has_finaliser = false;
        } else {
491
#if MICROPY_ENABLE_FINALISER
492
            has_finaliser = FTB_GET(BLOCK_FROM_PTR((machine_uint_t)ptr));
493
#else
494
            has_finaliser = false;
495
#endif
496
497
        }
        void *ptr2 = gc_alloc(n_bytes, has_finaliser);
498
499
500
501
502
503
504
505
        if (ptr2 == NULL) {
            return ptr2;
        }
        memcpy(ptr2, ptr, n_existing);
        gc_free(ptr);
        return ptr2;
    }
}
506
507

#else // Alternative gc_realloc impl
508

mux's avatar
mux committed
509
void *gc_realloc(void *ptr_in, machine_uint_t n_bytes) {
510
511
    if (gc_lock_depth > 0) {
        return NULL;
512
513
    }

514
    // check for pure allocation
mux's avatar
mux committed
515
    if (ptr_in == NULL) {
516
        return gc_alloc(n_bytes, false);
mux's avatar
mux committed
517
518
    }

519
520
521
522
523
524
525
    machine_uint_t ptr = (machine_uint_t)ptr_in;

    // sanity check the ptr
    if (!VERIFY_PTR(ptr)) {
        return NULL;
    }

526
527
528
    // get first block
    machine_uint_t block = BLOCK_FROM_PTR(ptr);

529
530
531
532
    // sanity check the ptr is pointing to the head of a block
    if (ATB_GET_KIND(block) != AT_HEAD) {
        return NULL;
    }
mux's avatar
mux committed
533

534
    // compute number of new blocks that are requested
535
    machine_uint_t new_blocks = (n_bytes + BYTES_PER_BLOCK - 1) / BYTES_PER_BLOCK;
mux's avatar
mux committed
536

537
538
539
540
541
542
543
544
545
    // get the number of consecutive tail blocks and
    // the number of free blocks after last tail block
    // stop if we reach (or are at) end of heap
    machine_uint_t n_free   = 0;
    machine_uint_t n_blocks = 1; // counting HEAD block
    machine_uint_t max_block = gc_alloc_table_byte_len * BLOCKS_PER_ATB;
    while (block + n_blocks + n_free < max_block) {
        if (n_blocks + n_free >= new_blocks) {
            // stop as soon as we find enough blocks for n_bytes
546
            break;
mux's avatar
mux committed
547
        }
548
549
550
551
552
553
554
555
556
557
558
559
560
        byte block_type = ATB_GET_KIND(block + n_blocks + n_free);
        switch (block_type) {
            case AT_FREE: n_free++; continue;
            case AT_TAIL: n_blocks++; continue;
            case AT_MARK: assert(0);
        }
        break;
    }

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

562
563
564
565
566
    // check if we can shrink the allocated area
    if (new_blocks < n_blocks) {
        // free unneeded tail blocks
        for (machine_uint_t bl = block + new_blocks; ATB_GET_KIND(bl) == AT_TAIL; bl++) {
            ATB_ANY_TO_FREE(bl);
567
        }
568
569
        return ptr_in;
    }
570

571
572
573
574
575
576
577
    // check if we can expand in place
    if (new_blocks <= n_blocks + n_free) {
        // mark few more blocks as used tail
        for (machine_uint_t bl = block + n_blocks; bl < block + new_blocks; bl++) {
            assert(ATB_GET_KIND(bl) == AT_FREE);
            ATB_FREE_TO_TAIL(bl);
        }
578

579
        // zero out the additional bytes of the newly allocated blocks (see comment above in gc_alloc)
580
        memset((byte*)ptr_in + n_bytes, 0, new_blocks * BYTES_PER_BLOCK - n_bytes);
581

582
583
        return ptr_in;
    }
mux's avatar
mux committed
584

585
586
    // can't resize inplace; try to find a new contiguous chain
    void *ptr_out = gc_alloc(n_bytes,
587
#if MICROPY_ENABLE_FINALISER
588
        FTB_GET(block)
589
#else
590
        false
591
#endif
592
593
594
595
596
    );

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

stijn's avatar
stijn committed
599
    DEBUG_printf("gc_realloc(%p -> %p)\n", ptr_in, ptr_out);
600
601
602
    memcpy(ptr_out, ptr_in, n_blocks * BYTES_PER_BLOCK);
    gc_free(ptr_in);
    return ptr_out;
Damien's avatar
Damien committed
603
}
604
#endif // Alternative gc_realloc impl
mux's avatar
mux committed
605

606
607
608
609
610
611
612
613
void gc_dump_info() {
    gc_info_t info;
    gc_info(&info);
    printf("GC: total: " UINT_FMT ", used: " UINT_FMT ", free: " UINT_FMT "\n", info.total, info.used, info.free);
    printf(" No. of 1-blocks: " UINT_FMT ", 2-blocks: " UINT_FMT ", max blk sz: " UINT_FMT "\n",
           info.num_1block, info.num_2block, info.max_block);
}

614
void gc_dump_alloc_table(void) {
615
    printf("GC memory layout; from %p:", gc_pool_start);
616
    for (machine_uint_t bl = 0; bl < gc_alloc_table_byte_len * BLOCKS_PER_ATB; bl++) {
617
618
619
620
        if (bl % 64 == 0) {
            printf("\n%04x: ", (uint)bl);
        }
        int c = ' ';
621
        switch (ATB_GET_KIND(bl)) {
622
623
            case AT_FREE: c = '.'; break;
            case AT_HEAD: c = 'h'; break;
624
625
626
627
628
629
630
631
632
633
634
635
            /* this prints the uPy object type of the head block
            case AT_HEAD: {
                machine_uint_t *ptr = gc_pool_start + bl * WORDS_PER_BLOCK;
                if (*ptr == (machine_uint_t)&mp_type_tuple) { c = 'T'; }
                else if (*ptr == (machine_uint_t)&mp_type_list) { c = 'L'; }
                else if (*ptr == (machine_uint_t)&mp_type_dict) { c = 'D'; }
                else if (*ptr == (machine_uint_t)&mp_type_float) { c = 'F'; }
                else if (*ptr == (machine_uint_t)&mp_type_fun_bc) { c = 'B'; }
                else { c = 'h'; }
                break;
            }
            */
636
637
            case AT_TAIL: c = 't'; break;
            case AT_MARK: c = 'm'; break;
638
        }
639
        printf("%c", c);
640
    }
641
    printf("\n");
642
643
}

644
#if DEBUG_PRINT
645
646
void gc_test(void) {
    machine_uint_t len = 500;
Damien's avatar
Damien committed
647
648
649
650
    machine_uint_t *heap = malloc(len);
    gc_init(heap, heap + len / sizeof(machine_uint_t));
    void *ptrs[100];
    {
651
652
653
654
655
656
        machine_uint_t **p = gc_alloc(16, false);
        p[0] = gc_alloc(64, false);
        p[1] = gc_alloc(1, false);
        p[2] = gc_alloc(1, false);
        p[3] = gc_alloc(1, false);
        machine_uint_t ***p2 = gc_alloc(16, false);
Damien's avatar
Damien committed
657
658
659
660
        p2[0] = p;
        p2[1] = p;
        ptrs[0] = p2;
    }
661
    for (int i = 0; i < 25; i+=2) {
662
        machine_uint_t *p = gc_alloc(i, false);
Damien's avatar
Damien committed
663
664
665
666
667
668
        printf("p=%p\n", p);
        if (i & 3) {
            //ptrs[i] = p;
        }
    }

669
    printf("Before GC:\n");
670
    gc_dump_alloc_table();
671
672
673
674
675
    printf("Starting GC...\n");
    gc_collect_start();
    gc_collect_root(ptrs, sizeof(ptrs) / sizeof(void*));
    gc_collect_end();
    printf("After GC:\n");
676
    gc_dump_alloc_table();
Damien's avatar
Damien committed
677
}
678
#endif
679
680

#endif // MICROPY_ENABLE_GC