1/*
2 * This file is part of the MicroPython project, http://micropython.org/
3 *
4 * The MIT License (MIT)
5 *
6 * Copyright (c) 2013, 2014 Damien P. George
7 * Copyright (c) 2014 Paul Sokolovsky
8 *
9 * Permission is hereby granted, free of charge, to any person obtaining a copy
10 * of this software and associated documentation files (the "Software"), to deal
11 * in the Software without restriction, including without limitation the rights
12 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
13 * copies of the Software, and to permit persons to whom the Software is
14 * furnished to do so, subject to the following conditions:
15 *
16 * The above copyright notice and this permission notice shall be included in
17 * all copies or substantial portions of the Software.
18 *
19 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
20 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
21 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
22 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
23 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
24 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
25 * THE SOFTWARE.
26 */
27
28#include <assert.h>
29#include <stdio.h>
30#include <string.h>
31
32#include "py/gc.h"
33#include "py/runtime.h"
34
35#if MICROPY_ENABLE_GC
36
37#if MICROPY_DEBUG_VERBOSE // print debugging info
38#define DEBUG_PRINT (1)
39#define DEBUG_printf DEBUG_printf
40#else // don't print debugging info
41#define DEBUG_PRINT (0)
42#define DEBUG_printf(...) (void)0
43#endif
44
45// make this 1 to dump the heap each time it changes
46#define EXTENSIVE_HEAP_PROFILING (0)
47
48// make this 1 to zero out swept memory to more eagerly
49// detect untraced object still in use
50#define CLEAR_ON_SWEEP (0)
51
52#define WORDS_PER_BLOCK ((MICROPY_BYTES_PER_GC_BLOCK) / MP_BYTES_PER_OBJ_WORD)
53#define BYTES_PER_BLOCK (MICROPY_BYTES_PER_GC_BLOCK)
54
55// ATB = allocation table byte
56// 0b00 = FREE -- free block
57// 0b01 = HEAD -- head of a chain of blocks
58// 0b10 = TAIL -- in the tail of a chain of blocks
59// 0b11 = MARK -- marked head block
60
61#define AT_FREE (0)
62#define AT_HEAD (1)
63#define AT_TAIL (2)
64#define AT_MARK (3)
65
66#define BLOCKS_PER_ATB (4)
67#define ATB_MASK_0 (0x03)
68#define ATB_MASK_1 (0x0c)
69#define ATB_MASK_2 (0x30)
70#define ATB_MASK_3 (0xc0)
71
72#define ATB_0_IS_FREE(a) (((a) & ATB_MASK_0) == 0)
73#define ATB_1_IS_FREE(a) (((a) & ATB_MASK_1) == 0)
74#define ATB_2_IS_FREE(a) (((a) & ATB_MASK_2) == 0)
75#define ATB_3_IS_FREE(a) (((a) & ATB_MASK_3) == 0)
76
77#define BLOCK_SHIFT(block) (2 * ((block) & (BLOCKS_PER_ATB - 1)))
78#define ATB_GET_KIND(block) ((MP_STATE_MEM(gc_alloc_table_start)[(block) / BLOCKS_PER_ATB] >> BLOCK_SHIFT(block)) & 3)
79#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)
80#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)
81#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)
82#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)
83#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)
86#define PTR_FROM_BLOCK(block) (((block) * BYTES_PER_BLOCK + (uintptr_t)MP_STATE_MEM(gc_pool_start)))
87#define ATB_FROM_BLOCK(bl) ((bl) / BLOCKS_PER_ATB)
88
89#if MICROPY_ENABLE_FINALISER
90// FTB = finaliser table byte
91// if set, then the corresponding block may have a finaliser
92
93#define BLOCKS_PER_FTB (8)
94
95#define FTB_GET(block) ((MP_STATE_MEM(gc_finaliser_table_start)[(block) / BLOCKS_PER_FTB] >> ((block) & 7)) & 1)
96#define FTB_SET(block) do { MP_STATE_MEM(gc_finaliser_table_start)[(block) / BLOCKS_PER_FTB] |= (1 << ((block) & 7)); } while (0)
97#define FTB_CLEAR(block) do { MP_STATE_MEM(gc_finaliser_table_start)[(block) / BLOCKS_PER_FTB] &= (~(1 << ((block) & 7))); } while (0)
98#endif
99
100#if MICROPY_PY_THREAD && !MICROPY_PY_THREAD_GIL
101#define GC_ENTER() mp_thread_mutex_lock(&MP_STATE_MEM(gc_mutex), 1)
102#define GC_EXIT() mp_thread_mutex_unlock(&MP_STATE_MEM(gc_mutex))
103#else
104#define GC_ENTER()
105#define GC_EXIT()
106#endif
107
108// TODO waste less memory; currently requires that all entries in alloc_table have a corresponding block in pool
109void gc_init(void *start, void *end) {
110 // align end pointer on block boundary
111 end = (void *)((uintptr_t)end & (~(BYTES_PER_BLOCK - 1)));
112 DEBUG_printf("Initializing GC heap: %p..%p = " UINT_FMT " bytes\n", start, end, (byte *)end - (byte *)start);
113
114 // calculate parameters for GC (T=total, A=alloc table, F=finaliser table, P=pool; all in bytes):
115 // T = A + F + P
116 // F = A * BLOCKS_PER_ATB / BLOCKS_PER_FTB
117 // P = A * BLOCKS_PER_ATB * BYTES_PER_BLOCK
118 // => T = A * (1 + BLOCKS_PER_ATB / BLOCKS_PER_FTB + BLOCKS_PER_ATB * BYTES_PER_BLOCK)
119 size_t total_byte_len = (byte *)end - (byte *)start;
120 #if MICROPY_ENABLE_FINALISER
121 MP_STATE_MEM(gc_alloc_table_byte_len) = total_byte_len * MP_BITS_PER_BYTE / (MP_BITS_PER_BYTE + MP_BITS_PER_BYTE * BLOCKS_PER_ATB / BLOCKS_PER_FTB + MP_BITS_PER_BYTE * BLOCKS_PER_ATB * BYTES_PER_BLOCK);
122 #else
123 MP_STATE_MEM(gc_alloc_table_byte_len) = total_byte_len / (1 + MP_BITS_PER_BYTE / 2 * BYTES_PER_BLOCK);
124 #endif
125
126 MP_STATE_MEM(gc_alloc_table_start) = (byte *)start;
127
128 #if MICROPY_ENABLE_FINALISER
129 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;
130 MP_STATE_MEM(gc_finaliser_table_start) = MP_STATE_MEM(gc_alloc_table_start) + MP_STATE_MEM(gc_alloc_table_byte_len);
131 #endif
132
133 size_t gc_pool_block_len = MP_STATE_MEM(gc_alloc_table_byte_len) * BLOCKS_PER_ATB;
134 MP_STATE_MEM(gc_pool_start) = (byte *)end - gc_pool_block_len * BYTES_PER_BLOCK;
135 MP_STATE_MEM(gc_pool_end) = end;
136
137 #if MICROPY_ENABLE_FINALISER
138 assert(MP_STATE_MEM(gc_pool_start) >= MP_STATE_MEM(gc_finaliser_table_start) + gc_finaliser_table_byte_len);
139 #endif
140
141 // clear ATBs
142 memset(MP_STATE_MEM(gc_alloc_table_start), 0, MP_STATE_MEM(gc_alloc_table_byte_len));
143
144 #if MICROPY_ENABLE_FINALISER
145 // clear FTBs
146 memset(MP_STATE_MEM(gc_finaliser_table_start), 0, gc_finaliser_table_byte_len);
147 #endif
148
149 // set last free ATB index to start of heap
150 MP_STATE_MEM(gc_last_free_atb_index) = 0;
151
152 // unlock the GC
153 MP_STATE_MEM(gc_lock_depth) = 0;
154
155 // allow auto collection
156 MP_STATE_MEM(gc_auto_collect_enabled) = 1;
157
158 #if MICROPY_GC_ALLOC_THRESHOLD
159 // by default, maxuint for gc threshold, effectively turning gc-by-threshold off
160 MP_STATE_MEM(gc_alloc_threshold) = (size_t)-1;
161 MP_STATE_MEM(gc_alloc_amount) = 0;
162 #endif
163
164 #if MICROPY_PY_THREAD && !MICROPY_PY_THREAD_GIL
165 mp_thread_mutex_init(&MP_STATE_MEM(gc_mutex));
166 #endif
167
168 DEBUG_printf("GC layout:\n");
169 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);
170 #if MICROPY_ENABLE_FINALISER
171 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);
172 #endif
173 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);
174}
175
176void gc_lock(void) {
177 GC_ENTER();
178 MP_STATE_MEM(gc_lock_depth)++;
179 GC_EXIT();
180}
181
182void gc_unlock(void) {
183 GC_ENTER();
184 MP_STATE_MEM(gc_lock_depth)--;
185 GC_EXIT();
186}
187
188bool gc_is_locked(void) {
189 return MP_STATE_MEM(gc_lock_depth) != 0;
190}
191
192// ptr should be of type void*
193#define VERIFY_PTR(ptr) ( \
194 ((uintptr_t)(ptr) & (BYTES_PER_BLOCK - 1)) == 0 /* must be aligned on a block */ \
195 && ptr >= (void *)MP_STATE_MEM(gc_pool_start) /* must be above start of pool */ \
196 && ptr < (void *)MP_STATE_MEM(gc_pool_end) /* must be below end of pool */ \
197 )
198
199#ifndef TRACE_MARK
200#if DEBUG_PRINT
201#define TRACE_MARK(block, ptr) DEBUG_printf("gc_mark(%p)\n", ptr)
202#else
203#define TRACE_MARK(block, ptr)
204#endif
205#endif
206
207// Take the given block as the topmost block on the stack. Check all it's
208// children: mark the unmarked child blocks and put those newly marked
209// blocks on the stack. When all children have been checked, pop off the
210// topmost block on the stack and repeat with that one.
211STATIC void gc_mark_subtree(size_t block) {
212 // Start with the block passed in the argument.
213 size_t sp = 0;
214 for (;;) {
215 // work out number of consecutive blocks in the chain starting with this one
216 size_t n_blocks = 0;
217 do {
218 n_blocks += 1;
219 } while (ATB_GET_KIND(block + n_blocks) == AT_TAIL);
220
221 // check this block's children
222 void **ptrs = (void **)PTR_FROM_BLOCK(block);
223 for (size_t i = n_blocks * BYTES_PER_BLOCK / sizeof(void *); i > 0; i--, ptrs++) {
224 void *ptr = *ptrs;
225 if (VERIFY_PTR(ptr)) {
226 // Mark and push this pointer
227 size_t childblock = BLOCK_FROM_PTR(ptr);
228 if (ATB_GET_KIND(childblock) == AT_HEAD) {
229 // an unmarked head, mark it, and push it on gc stack
230 TRACE_MARK(childblock, ptr);
231 ATB_HEAD_TO_MARK(childblock);
232 if (sp < MICROPY_ALLOC_GC_STACK_SIZE) {
233 MP_STATE_MEM(gc_stack)[sp++] = childblock;
234 } else {
235 MP_STATE_MEM(gc_stack_overflow) = 1;
236 }
237 }
238 }
239 }
240
241 // Are there any blocks on the stack?
242 if (sp == 0) {
243 break; // No, stack is empty, we're done.
244 }
245
246 // pop the next block off the stack
247 block = MP_STATE_MEM(gc_stack)[--sp];
248 }
249}
250
251STATIC void gc_deal_with_stack_overflow(void) {
252 while (MP_STATE_MEM(gc_stack_overflow)) {
253 MP_STATE_MEM(gc_stack_overflow) = 0;
254
255 // scan entire memory looking for blocks which have been marked but not their children
256 for (size_t block = 0; block < MP_STATE_MEM(gc_alloc_table_byte_len) * BLOCKS_PER_ATB; block++) {
257 // trace (again) if mark bit set
258 if (ATB_GET_KIND(block) == AT_MARK) {
259 gc_mark_subtree(block);
260 }
261 }
262 }
263}
264
265STATIC void gc_sweep(void) {
266 #if MICROPY_PY_GC_COLLECT_RETVAL
267 MP_STATE_MEM(gc_collected) = 0;
268 #endif
269 // free unmarked heads and their tails
270 int free_tail = 0;
271 for (size_t block = 0; block < MP_STATE_MEM(gc_alloc_table_byte_len) * BLOCKS_PER_ATB; block++) {
272 switch (ATB_GET_KIND(block)) {
273 case AT_HEAD:
274 #if MICROPY_ENABLE_FINALISER
275 if (FTB_GET(block)) {
276 mp_obj_base_t *obj = (mp_obj_base_t *)PTR_FROM_BLOCK(block);
277 if (obj->type != NULL) {
278 // if the object has a type then see if it has a __del__ method
279 mp_obj_t dest[2];
280 mp_load_method_maybe(MP_OBJ_FROM_PTR(obj), MP_QSTR___del__, dest);
281 if (dest[0] != MP_OBJ_NULL) {
282 // load_method returned a method, execute it in a protected environment
283 #if MICROPY_ENABLE_SCHEDULER
284 mp_sched_lock();
285 #endif
286 mp_call_function_1_protected(dest[0], dest[1]);
287 #if MICROPY_ENABLE_SCHEDULER
288 mp_sched_unlock();
289 #endif
290 }
291 }
292 // clear finaliser flag
293 FTB_CLEAR(block);
294 }
295 #endif
296 free_tail = 1;
297 DEBUG_printf("gc_sweep(%p)\n", (void *)PTR_FROM_BLOCK(block));
298 #if MICROPY_PY_GC_COLLECT_RETVAL
299 MP_STATE_MEM(gc_collected)++;
300 #endif
301 // fall through to free the head
302 MP_FALLTHROUGH
303
304 case AT_TAIL:
305 if (free_tail) {
306 ATB_ANY_TO_FREE(block);
307 #if CLEAR_ON_SWEEP
308 memset((void *)PTR_FROM_BLOCK(block), 0, BYTES_PER_BLOCK);
309 #endif
310 }
311 break;
312
313 case AT_MARK:
314 ATB_MARK_TO_HEAD(block);
315 free_tail = 0;
316 break;
317 }
318 }
319}
320
321void gc_collect_start(void) {
322 GC_ENTER();
323 MP_STATE_MEM(gc_lock_depth)++;
324 #if MICROPY_GC_ALLOC_THRESHOLD
325 MP_STATE_MEM(gc_alloc_amount) = 0;
326 #endif
327 MP_STATE_MEM(gc_stack_overflow) = 0;
328
329 // Trace root pointers. This relies on the root pointers being organised
330 // correctly in the mp_state_ctx structure. We scan nlr_top, dict_locals,
331 // dict_globals, then the root pointer section of mp_state_vm.
332 void **ptrs = (void **)(void *)&mp_state_ctx;
333 size_t root_start = offsetof(mp_state_ctx_t, thread.dict_locals);
334 size_t root_end = offsetof(mp_state_ctx_t, vm.qstr_last_chunk);
335 gc_collect_root(ptrs + root_start / sizeof(void *), (root_end - root_start) / sizeof(void *));
336
337 #if MICROPY_ENABLE_PYSTACK
338 // Trace root pointers from the Python stack.
339 ptrs = (void **)(void *)MP_STATE_THREAD(pystack_start);
340 gc_collect_root(ptrs, (MP_STATE_THREAD(pystack_cur) - MP_STATE_THREAD(pystack_start)) / sizeof(void *));
341 #endif
342}
343
344void gc_collect_root(void **ptrs, size_t len) {
345 for (size_t i = 0; i < len; i++) {
346 void *ptr = ptrs[i];
347 if (VERIFY_PTR(ptr)) {
348 size_t block = BLOCK_FROM_PTR(ptr);
349 if (ATB_GET_KIND(block) == AT_HEAD) {
350 // An unmarked head: mark it, and mark all its children
351 TRACE_MARK(block, ptr);
352 ATB_HEAD_TO_MARK(block);
353 gc_mark_subtree(block);
354 }
355 }
356 }
357}
358
359void gc_collect_end(void) {
360 gc_deal_with_stack_overflow();
361 gc_sweep();
362 MP_STATE_MEM(gc_last_free_atb_index) = 0;
363 MP_STATE_MEM(gc_lock_depth)--;
364 GC_EXIT();
365}
366
367void gc_sweep_all(void) {
368 GC_ENTER();
369 MP_STATE_MEM(gc_lock_depth)++;
370 MP_STATE_MEM(gc_stack_overflow) = 0;
371 gc_collect_end();
372}
373
374void gc_info(gc_info_t *info) {
375 GC_ENTER();
376 info->total = MP_STATE_MEM(gc_pool_end) - MP_STATE_MEM(gc_pool_start);
377 info->used = 0;
378 info->free = 0;
379 info->max_free = 0;
380 info->num_1block = 0;
381 info->num_2block = 0;
382 info->max_block = 0;
383 bool finish = false;
384 for (size_t block = 0, len = 0, len_free = 0; !finish;) {
385 size_t kind = ATB_GET_KIND(block);
386 switch (kind) {
387 case AT_FREE:
388 info->free += 1;
389 len_free += 1;
390 len = 0;
391 break;
392
393 case AT_HEAD:
394 info->used += 1;
395 len = 1;
396 break;
397
398 case AT_TAIL:
399 info->used += 1;
400 len += 1;
401 break;
402
403 case AT_MARK:
404 // shouldn't happen
405 break;
406 }
407
408 block++;
409 finish = (block == MP_STATE_MEM(gc_alloc_table_byte_len) * BLOCKS_PER_ATB);
410 // Get next block type if possible
411 if (!finish) {
412 kind = ATB_GET_KIND(block);
413 }
414
415 if (finish || kind == AT_FREE || kind == AT_HEAD) {
416 if (len == 1) {
417 info->num_1block += 1;
418 } else if (len == 2) {
419 info->num_2block += 1;
420 }
421 if (len > info->max_block) {
422 info->max_block = len;
423 }
424 if (finish || kind == AT_HEAD) {
425 if (len_free > info->max_free) {
426 info->max_free = len_free;
427 }
428 len_free = 0;
429 }
430 }
431 }
432
433 info->used *= BYTES_PER_BLOCK;
434 info->free *= BYTES_PER_BLOCK;
435 GC_EXIT();
436}
437
438void *gc_alloc(size_t n_bytes, unsigned int alloc_flags) {
439 bool has_finaliser = alloc_flags & GC_ALLOC_FLAG_HAS_FINALISER;
440 size_t n_blocks = ((n_bytes + BYTES_PER_BLOCK - 1) & (~(BYTES_PER_BLOCK - 1))) / BYTES_PER_BLOCK;
441 DEBUG_printf("gc_alloc(" UINT_FMT " bytes -> " UINT_FMT " blocks)\n", n_bytes, n_blocks);
442
443 // check for 0 allocation
444 if (n_blocks == 0) {
445 return NULL;
446 }
447
448 GC_ENTER();
449
450 // check if GC is locked
451 if (MP_STATE_MEM(gc_lock_depth) > 0) {
452 GC_EXIT();
453 return NULL;
454 }
455
456 size_t i;
457 size_t end_block;
458 size_t start_block;
459 size_t n_free;
460 int collected = !MP_STATE_MEM(gc_auto_collect_enabled);
461
462 #if MICROPY_GC_ALLOC_THRESHOLD
463 if (!collected && MP_STATE_MEM(gc_alloc_amount) >= MP_STATE_MEM(gc_alloc_threshold)) {
464 GC_EXIT();
465 gc_collect();
466 collected = 1;
467 GC_ENTER();
468 }
469 #endif
470
471 for (;;) {
472
473 // look for a run of n_blocks available blocks
474 n_free = 0;
475 for (i = MP_STATE_MEM(gc_last_free_atb_index); i < MP_STATE_MEM(gc_alloc_table_byte_len); i++) {
476 byte a = MP_STATE_MEM(gc_alloc_table_start)[i];
477 // *FORMAT-OFF*
478 if (ATB_0_IS_FREE(a)) { if (++n_free >= n_blocks) { i = i * BLOCKS_PER_ATB + 0; goto found; } } else { n_free = 0; }
479 if (ATB_1_IS_FREE(a)) { if (++n_free >= n_blocks) { i = i * BLOCKS_PER_ATB + 1; goto found; } } else { n_free = 0; }
480 if (ATB_2_IS_FREE(a)) { if (++n_free >= n_blocks) { i = i * BLOCKS_PER_ATB + 2; goto found; } } else { n_free = 0; }
481 if (ATB_3_IS_FREE(a)) { if (++n_free >= n_blocks) { i = i * BLOCKS_PER_ATB + 3; goto found; } } else { n_free = 0; }
482 // *FORMAT-ON*
483 }
484
485 GC_EXIT();
486 // nothing found!
487 if (collected) {
488 return NULL;
489 }
490 DEBUG_printf("gc_alloc(" UINT_FMT "): no free mem, triggering GC\n", n_bytes);
491 gc_collect();
492 collected = 1;
493 GC_ENTER();
494 }
495
496 // found, ending at block i inclusive
497found:
498 // get starting and end blocks, both inclusive
499 end_block = i;
500 start_block = i - n_free + 1;
501
502 // Set last free ATB index to block after last block we found, for start of
503 // next scan. To reduce fragmentation, we only do this if we were looking
504 // for a single free block, which guarantees that there are no free blocks
505 // before this one. Also, whenever we free or shink a block we must check
506 // if this index needs adjusting (see gc_realloc and gc_free).
507 if (n_free == 1) {
508 MP_STATE_MEM(gc_last_free_atb_index) = (i + 1) / BLOCKS_PER_ATB;
509 }
510
511 // mark first block as used head
512 ATB_FREE_TO_HEAD(start_block);
513
514 // mark rest of blocks as used tail
515 // TODO for a run of many blocks can make this more efficient
516 for (size_t bl = start_block + 1; bl <= end_block; bl++) {
517 ATB_FREE_TO_TAIL(bl);
518 }
519
520 // get pointer to first block
521 // we must create this pointer before unlocking the GC so a collection can find it
522 void *ret_ptr = (void *)(MP_STATE_MEM(gc_pool_start) + start_block * BYTES_PER_BLOCK);
523 DEBUG_printf("gc_alloc(%p)\n", ret_ptr);
524
525 #if MICROPY_GC_ALLOC_THRESHOLD
526 MP_STATE_MEM(gc_alloc_amount) += n_blocks;
527 #endif
528
529 GC_EXIT();
530
531 #if MICROPY_GC_CONSERVATIVE_CLEAR
532 // be conservative and zero out all the newly allocated blocks
533 memset((byte *)ret_ptr, 0, (end_block - start_block + 1) * BYTES_PER_BLOCK);
534 #else
535 // zero out the additional bytes of the newly allocated blocks
536 // This is needed because the blocks may have previously held pointers
537 // to the heap and will not be set to something else if the caller
538 // doesn't actually use the entire block. As such they will continue
539 // to point to the heap and may prevent other blocks from being reclaimed.
540 memset((byte *)ret_ptr + n_bytes, 0, (end_block - start_block + 1) * BYTES_PER_BLOCK - n_bytes);
541 #endif
542
543 #if MICROPY_ENABLE_FINALISER
544 if (has_finaliser) {
545 // clear type pointer in case it is never set
546 ((mp_obj_base_t *)ret_ptr)->type = NULL;
547 // set mp_obj flag only if it has a finaliser
548 GC_ENTER();
549 FTB_SET(start_block);
550 GC_EXIT();
551 }
552 #else
553 (void)has_finaliser;
554 #endif
555
556 #if EXTENSIVE_HEAP_PROFILING
557 gc_dump_alloc_table();
558 #endif
559
560 return ret_ptr;
561}
562
563/*
564void *gc_alloc(mp_uint_t n_bytes) {
565 return _gc_alloc(n_bytes, false);
566}
567
568void *gc_alloc_with_finaliser(mp_uint_t n_bytes) {
569 return _gc_alloc(n_bytes, true);
570}
571*/
572
573// force the freeing of a piece of memory
574// TODO: freeing here does not call finaliser
575void gc_free(void *ptr) {
576 GC_ENTER();
577 if (MP_STATE_MEM(gc_lock_depth) > 0) {
578 // TODO how to deal with this error?
579 GC_EXIT();
580 return;
581 }
582
583 DEBUG_printf("gc_free(%p)\n", ptr);
584
585 if (ptr == NULL) {
586 GC_EXIT();
587 } else {
588 // get the GC block number corresponding to this pointer
589 assert(VERIFY_PTR(ptr));
590 size_t block = BLOCK_FROM_PTR(ptr);
591 assert(ATB_GET_KIND(block) == AT_HEAD);
592
593 #if MICROPY_ENABLE_FINALISER
594 FTB_CLEAR(block);
595 #endif
596
597 // set the last_free pointer to this block if it's earlier in the heap
598 if (block / BLOCKS_PER_ATB < MP_STATE_MEM(gc_last_free_atb_index)) {
599 MP_STATE_MEM(gc_last_free_atb_index) = block / BLOCKS_PER_ATB;
600 }
601
602 // free head and all of its tail blocks
603 do {
604 ATB_ANY_TO_FREE(block);
605 block += 1;
606 } while (ATB_GET_KIND(block) == AT_TAIL);
607
608 GC_EXIT();
609
610 #if EXTENSIVE_HEAP_PROFILING
611 gc_dump_alloc_table();
612 #endif
613 }
614}
615
616size_t gc_nbytes(const void *ptr) {
617 GC_ENTER();
618 if (VERIFY_PTR(ptr)) {
619 size_t block = BLOCK_FROM_PTR(ptr);
620 if (ATB_GET_KIND(block) == AT_HEAD) {
621 // work out number of consecutive blocks in the chain starting with this on
622 size_t n_blocks = 0;
623 do {
624 n_blocks += 1;
625 } while (ATB_GET_KIND(block + n_blocks) == AT_TAIL);
626 GC_EXIT();
627 return n_blocks * BYTES_PER_BLOCK;
628 }
629 }
630
631 // invalid pointer
632 GC_EXIT();
633 return 0;
634}
635
636#if 0
637// old, simple realloc that didn't expand memory in place
638void *gc_realloc(void *ptr, mp_uint_t n_bytes) {
639 mp_uint_t n_existing = gc_nbytes(ptr);
640 if (n_bytes <= n_existing) {
641 return ptr;
642 } else {
643 bool has_finaliser;
644 if (ptr == NULL) {
645 has_finaliser = false;
646 } else {
647 #if MICROPY_ENABLE_FINALISER
648 has_finaliser = FTB_GET(BLOCK_FROM_PTR((mp_uint_t)ptr));
649 #else
650 has_finaliser = false;
651 #endif
652 }
653 void *ptr2 = gc_alloc(n_bytes, has_finaliser);
654 if (ptr2 == NULL) {
655 return ptr2;
656 }
657 memcpy(ptr2, ptr, n_existing);
658 gc_free(ptr);
659 return ptr2;
660 }
661}
662
663#else // Alternative gc_realloc impl
664
665void *gc_realloc(void *ptr_in, size_t n_bytes, bool allow_move) {
666 // check for pure allocation
667 if (ptr_in == NULL) {
668 return gc_alloc(n_bytes, false);
669 }
670
671 // check for pure free
672 if (n_bytes == 0) {
673 gc_free(ptr_in);
674 return NULL;
675 }
676
677 void *ptr = ptr_in;
678
679 GC_ENTER();
680
681 if (MP_STATE_MEM(gc_lock_depth) > 0) {
682 GC_EXIT();
683 return NULL;
684 }
685
686 // get the GC block number corresponding to this pointer
687 assert(VERIFY_PTR(ptr));
688 size_t block = BLOCK_FROM_PTR(ptr);
689 assert(ATB_GET_KIND(block) == AT_HEAD);
690
691 // compute number of new blocks that are requested
692 size_t new_blocks = (n_bytes + BYTES_PER_BLOCK - 1) / BYTES_PER_BLOCK;
693
694 // Get the total number of consecutive blocks that are already allocated to
695 // this chunk of memory, and then count the number of free blocks following
696 // it. Stop if we reach the end of the heap, or if we find enough extra
697 // free blocks to satisfy the realloc. Note that we need to compute the
698 // total size of the existing memory chunk so we can correctly and
699 // efficiently shrink it (see below for shrinking code).
700 size_t n_free = 0;
701 size_t n_blocks = 1; // counting HEAD block
702 size_t max_block = MP_STATE_MEM(gc_alloc_table_byte_len) * BLOCKS_PER_ATB;
703 for (size_t bl = block + n_blocks; bl < max_block; bl++) {
704 byte block_type = ATB_GET_KIND(bl);
705 if (block_type == AT_TAIL) {
706 n_blocks++;
707 continue;
708 }
709 if (block_type == AT_FREE) {
710 n_free++;
711 if (n_blocks + n_free >= new_blocks) {
712 // stop as soon as we find enough blocks for n_bytes
713 break;
714 }
715 continue;
716 }
717 break;
718 }
719
720 // return original ptr if it already has the requested number of blocks
721 if (new_blocks == n_blocks) {
722 GC_EXIT();
723 return ptr_in;
724 }
725
726 // check if we can shrink the allocated area
727 if (new_blocks < n_blocks) {
728 // free unneeded tail blocks
729 for (size_t bl = block + new_blocks, count = n_blocks - new_blocks; count > 0; bl++, count--) {
730 ATB_ANY_TO_FREE(bl);
731 }
732
733 // set the last_free pointer to end of this block if it's earlier in the heap
734 if ((block + new_blocks) / BLOCKS_PER_ATB < MP_STATE_MEM(gc_last_free_atb_index)) {
735 MP_STATE_MEM(gc_last_free_atb_index) = (block + new_blocks) / BLOCKS_PER_ATB;
736 }
737
738 GC_EXIT();
739
740 #if EXTENSIVE_HEAP_PROFILING
741 gc_dump_alloc_table();
742 #endif
743
744 return ptr_in;
745 }
746
747 // check if we can expand in place
748 if (new_blocks <= n_blocks + n_free) {
749 // mark few more blocks as used tail
750 for (size_t bl = block + n_blocks; bl < block + new_blocks; bl++) {
751 assert(ATB_GET_KIND(bl) == AT_FREE);
752 ATB_FREE_TO_TAIL(bl);
753 }
754
755 GC_EXIT();
756
757 #if MICROPY_GC_CONSERVATIVE_CLEAR
758 // be conservative and zero out all the newly allocated blocks
759 memset((byte *)ptr_in + n_blocks * BYTES_PER_BLOCK, 0, (new_blocks - n_blocks) * BYTES_PER_BLOCK);
760 #else
761 // zero out the additional bytes of the newly allocated blocks (see comment above in gc_alloc)
762 memset((byte *)ptr_in + n_bytes, 0, new_blocks * BYTES_PER_BLOCK - n_bytes);
763 #endif
764
765 #if EXTENSIVE_HEAP_PROFILING
766 gc_dump_alloc_table();
767 #endif
768
769 return ptr_in;
770 }
771
772 #if MICROPY_ENABLE_FINALISER
773 bool ftb_state = FTB_GET(block);
774 #else
775 bool ftb_state = false;
776 #endif
777
778 GC_EXIT();
779
780 if (!allow_move) {
781 // not allowed to move memory block so return failure
782 return NULL;
783 }
784
785 // can't resize inplace; try to find a new contiguous chain
786 void *ptr_out = gc_alloc(n_bytes, ftb_state);
787
788 // check that the alloc succeeded
789 if (ptr_out == NULL) {
790 return NULL;
791 }
792
793 DEBUG_printf("gc_realloc(%p -> %p)\n", ptr_in, ptr_out);
794 memcpy(ptr_out, ptr_in, n_blocks * BYTES_PER_BLOCK);
795 gc_free(ptr_in);
796 return ptr_out;
797}
798#endif // Alternative gc_realloc impl
799
800void gc_dump_info(void) {
801 gc_info_t info;
802 gc_info(&info);
803 mp_printf(&mp_plat_print, "GC: total: %u, used: %u, free: %u\n",
804 (uint)info.total, (uint)info.used, (uint)info.free);
805 mp_printf(&mp_plat_print, " No. of 1-blocks: %u, 2-blocks: %u, max blk sz: %u, max free sz: %u\n",
806 (uint)info.num_1block, (uint)info.num_2block, (uint)info.max_block, (uint)info.max_free);
807}
808
809void gc_dump_alloc_table(void) {
810 GC_ENTER();
811 static const size_t DUMP_BYTES_PER_LINE = 64;
812 #if !EXTENSIVE_HEAP_PROFILING
813 // When comparing heap output we don't want to print the starting
814 // pointer of the heap because it changes from run to run.
815 mp_printf(&mp_plat_print, "GC memory layout; from %p:", MP_STATE_MEM(gc_pool_start));
816 #endif
817 for (size_t bl = 0; bl < MP_STATE_MEM(gc_alloc_table_byte_len) * BLOCKS_PER_ATB; bl++) {
818 if (bl % DUMP_BYTES_PER_LINE == 0) {
819 // a new line of blocks
820 {
821 // check if this line contains only free blocks
822 size_t bl2 = bl;
823 while (bl2 < MP_STATE_MEM(gc_alloc_table_byte_len) * BLOCKS_PER_ATB && ATB_GET_KIND(bl2) == AT_FREE) {
824 bl2++;
825 }
826 if (bl2 - bl >= 2 * DUMP_BYTES_PER_LINE) {
827 // there are at least 2 lines containing only free blocks, so abbreviate their printing
828 mp_printf(&mp_plat_print, "\n (%u lines all free)", (uint)(bl2 - bl) / DUMP_BYTES_PER_LINE);
829 bl = bl2 & (~(DUMP_BYTES_PER_LINE - 1));
830 if (bl >= MP_STATE_MEM(gc_alloc_table_byte_len) * BLOCKS_PER_ATB) {
831 // got to end of heap
832 break;
833 }
834 }
835 }
836 // print header for new line of blocks
837 // (the cast to uint32_t is for 16-bit ports)
838 // mp_printf(&mp_plat_print, "\n%05x: ", (uint)(PTR_FROM_BLOCK(bl) & (uint32_t)0xfffff));
839 mp_printf(&mp_plat_print, "\n%05x: ", (uint)((bl * BYTES_PER_BLOCK) & (uint32_t)0xfffff));
840 }
841 int c = ' ';
842 switch (ATB_GET_KIND(bl)) {
843 case AT_FREE:
844 c = '.';
845 break;
846 /* this prints out if the object is reachable from BSS or STACK (for unix only)
847 case AT_HEAD: {
848 c = 'h';
849 void **ptrs = (void**)(void*)&mp_state_ctx;
850 mp_uint_t len = offsetof(mp_state_ctx_t, vm.stack_top) / sizeof(mp_uint_t);
851 for (mp_uint_t i = 0; i < len; i++) {
852 mp_uint_t ptr = (mp_uint_t)ptrs[i];
853 if (VERIFY_PTR(ptr) && BLOCK_FROM_PTR(ptr) == bl) {
854 c = 'B';
855 break;
856 }
857 }
858 if (c == 'h') {
859 ptrs = (void**)&c;
860 len = ((mp_uint_t)MP_STATE_THREAD(stack_top) - (mp_uint_t)&c) / sizeof(mp_uint_t);
861 for (mp_uint_t i = 0; i < len; i++) {
862 mp_uint_t ptr = (mp_uint_t)ptrs[i];
863 if (VERIFY_PTR(ptr) && BLOCK_FROM_PTR(ptr) == bl) {
864 c = 'S';
865 break;
866 }
867 }
868 }
869 break;
870 }
871 */
872 /* this prints the uPy object type of the head block */
873 case AT_HEAD: {
874 void **ptr = (void **)(MP_STATE_MEM(gc_pool_start) + bl * BYTES_PER_BLOCK);
875 if (*ptr == &mp_type_tuple) {
876 c = 'T';
877 } else if (*ptr == &mp_type_list) {
878 c = 'L';
879 } else if (*ptr == &mp_type_dict) {
880 c = 'D';
881 } else if (*ptr == &mp_type_str || *ptr == &mp_type_bytes) {
882 c = 'S';
883 }
884 #if MICROPY_PY_BUILTINS_BYTEARRAY
885 else if (*ptr == &mp_type_bytearray) {
886 c = 'A';
887 }
888 #endif
889 #if MICROPY_PY_ARRAY
890 else if (*ptr == &mp_type_array) {
891 c = 'A';
892 }
893 #endif
894 #if MICROPY_PY_BUILTINS_FLOAT
895 else if (*ptr == &mp_type_float) {
896 c = 'F';
897 }
898 #endif
899 else if (*ptr == &mp_type_fun_bc) {
900 c = 'B';
901 } else if (*ptr == &mp_type_module) {
902 c = 'M';
903 } else {
904 c = 'h';
905 #if 0
906 // This code prints "Q" for qstr-pool data, and "q" for qstr-str
907 // data. It can be useful to see how qstrs are being allocated,
908 // but is disabled by default because it is very slow.
909 for (qstr_pool_t *pool = MP_STATE_VM(last_pool); c == 'h' && pool != NULL; pool = pool->prev) {
910 if ((qstr_pool_t *)ptr == pool) {
911 c = 'Q';
912 break;
913 }
914 for (const byte **q = pool->qstrs, **q_top = pool->qstrs + pool->len; q < q_top; q++) {
915 if ((const byte *)ptr == *q) {
916 c = 'q';
917 break;
918 }
919 }
920 }
921 #endif
922 }
923 break;
924 }
925 case AT_TAIL:
926 c = '=';
927 break;
928 case AT_MARK:
929 c = 'm';
930 break;
931 }
932 mp_printf(&mp_plat_print, "%c", c);
933 }
934 mp_print_str(&mp_plat_print, "\n");
935 GC_EXIT();
936}
937
938#if 0
939// For testing the GC functions
940void gc_test(void) {
941 mp_uint_t len = 500;
942 mp_uint_t *heap = malloc(len);
943 gc_init(heap, heap + len / sizeof(mp_uint_t));
944 void *ptrs[100];
945 {
946 mp_uint_t **p = gc_alloc(16, false);
947 p[0] = gc_alloc(64, false);
948 p[1] = gc_alloc(1, false);
949 p[2] = gc_alloc(1, false);
950 p[3] = gc_alloc(1, false);
951 mp_uint_t ***p2 = gc_alloc(16, false);
952 p2[0] = p;
953 p2[1] = p;
954 ptrs[0] = p2;
955 }
956 for (int i = 0; i < 25; i += 2) {
957 mp_uint_t *p = gc_alloc(i, false);
958 printf("p=%p\n", p);
959 if (i & 3) {
960 // ptrs[i] = p;
961 }
962 }
963
964 printf("Before GC:\n");
965 gc_dump_alloc_table();
966 printf("Starting GC...\n");
967 gc_collect_start();
968 gc_collect_root(ptrs, sizeof(ptrs) / sizeof(void *));
969 gc_collect_end();
970 printf("After GC:\n");
971 gc_dump_alloc_table();
972}
973#endif
974
975#endif // MICROPY_ENABLE_GC
976