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
gc_init(void * start,void * end)109 void 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_THREAD(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
gc_lock(void)176 void gc_lock(void) {
177 // This does not need to be atomic or have the GC mutex because:
178 // - each thread has its own gc_lock_depth so there are no races between threads;
179 // - a hard interrupt will only change gc_lock_depth during its execution, and
180 // upon return will restore the value of gc_lock_depth.
181 MP_STATE_THREAD(gc_lock_depth)++;
182 }
183
gc_unlock(void)184 void gc_unlock(void) {
185 // This does not need to be atomic, See comment above in gc_lock.
186 MP_STATE_THREAD(gc_lock_depth)--;
187 }
188
gc_is_locked(void)189 bool gc_is_locked(void) {
190 return MP_STATE_THREAD(gc_lock_depth) != 0;
191 }
192
193 // ptr should be of type void*
194 #define VERIFY_PTR(ptr) ( \
195 ((uintptr_t)(ptr) & (BYTES_PER_BLOCK - 1)) == 0 /* must be aligned on a block */ \
196 && ptr >= (void *)MP_STATE_MEM(gc_pool_start) /* must be above start of pool */ \
197 && ptr < (void *)MP_STATE_MEM(gc_pool_end) /* must be below end of pool */ \
198 )
199
200 #ifndef TRACE_MARK
201 #if DEBUG_PRINT
202 #define TRACE_MARK(block, ptr) DEBUG_printf("gc_mark(%p)\n", ptr)
203 #else
204 #define TRACE_MARK(block, ptr)
205 #endif
206 #endif
207
208 // Take the given block as the topmost block on the stack. Check all it's
209 // children: mark the unmarked child blocks and put those newly marked
210 // blocks on the stack. When all children have been checked, pop off the
211 // topmost block on the stack and repeat with that one.
gc_mark_subtree(size_t block)212 STATIC void gc_mark_subtree(size_t block) {
213 // Start with the block passed in the argument.
214 size_t sp = 0;
215 for (;;) {
216 // work out number of consecutive blocks in the chain starting with this one
217 size_t n_blocks = 0;
218 do {
219 n_blocks += 1;
220 } while (ATB_GET_KIND(block + n_blocks) == AT_TAIL);
221
222 // check this block's children
223 void **ptrs = (void **)PTR_FROM_BLOCK(block);
224 for (size_t i = n_blocks * BYTES_PER_BLOCK / sizeof(void *); i > 0; i--, ptrs++) {
225 void *ptr = *ptrs;
226 if (VERIFY_PTR(ptr)) {
227 // Mark and push this pointer
228 size_t childblock = BLOCK_FROM_PTR(ptr);
229 if (ATB_GET_KIND(childblock) == AT_HEAD) {
230 // an unmarked head, mark it, and push it on gc stack
231 TRACE_MARK(childblock, ptr);
232 ATB_HEAD_TO_MARK(childblock);
233 if (sp < MICROPY_ALLOC_GC_STACK_SIZE) {
234 MP_STATE_MEM(gc_stack)[sp++] = childblock;
235 } else {
236 MP_STATE_MEM(gc_stack_overflow) = 1;
237 }
238 }
239 }
240 }
241
242 // Are there any blocks on the stack?
243 if (sp == 0) {
244 break; // No, stack is empty, we're done.
245 }
246
247 // pop the next block off the stack
248 block = MP_STATE_MEM(gc_stack)[--sp];
249 }
250 }
251
gc_deal_with_stack_overflow(void)252 STATIC void gc_deal_with_stack_overflow(void) {
253 while (MP_STATE_MEM(gc_stack_overflow)) {
254 MP_STATE_MEM(gc_stack_overflow) = 0;
255
256 // scan entire memory looking for blocks which have been marked but not their children
257 for (size_t block = 0; block < MP_STATE_MEM(gc_alloc_table_byte_len) * BLOCKS_PER_ATB; block++) {
258 // trace (again) if mark bit set
259 if (ATB_GET_KIND(block) == AT_MARK) {
260 gc_mark_subtree(block);
261 }
262 }
263 }
264 }
265
gc_sweep(void)266 STATIC void gc_sweep(void) {
267 #if MICROPY_PY_GC_COLLECT_RETVAL
268 MP_STATE_MEM(gc_collected) = 0;
269 #endif
270 // free unmarked heads and their tails
271 int free_tail = 0;
272 for (size_t block = 0; block < MP_STATE_MEM(gc_alloc_table_byte_len) * BLOCKS_PER_ATB; block++) {
273 switch (ATB_GET_KIND(block)) {
274 case AT_HEAD:
275 #if MICROPY_ENABLE_FINALISER
276 if (FTB_GET(block)) {
277 mp_obj_base_t *obj = (mp_obj_base_t *)PTR_FROM_BLOCK(block);
278 if (obj->type != NULL) {
279 // if the object has a type then see if it has a __del__ method
280 mp_obj_t dest[2];
281 mp_load_method_maybe(MP_OBJ_FROM_PTR(obj), MP_QSTR___del__, dest);
282 if (dest[0] != MP_OBJ_NULL) {
283 // load_method returned a method, execute it in a protected environment
284 #if MICROPY_ENABLE_SCHEDULER
285 mp_sched_lock();
286 #endif
287 mp_call_function_1_protected(dest[0], dest[1]);
288 #if MICROPY_ENABLE_SCHEDULER
289 mp_sched_unlock();
290 #endif
291 }
292 }
293 // clear finaliser flag
294 FTB_CLEAR(block);
295 }
296 #endif
297 free_tail = 1;
298 DEBUG_printf("gc_sweep(%p)\n", (void *)PTR_FROM_BLOCK(block));
299 #if MICROPY_PY_GC_COLLECT_RETVAL
300 MP_STATE_MEM(gc_collected)++;
301 #endif
302 // fall through to free the head
303 MP_FALLTHROUGH
304
305 case AT_TAIL:
306 if (free_tail) {
307 ATB_ANY_TO_FREE(block);
308 #if CLEAR_ON_SWEEP
309 memset((void *)PTR_FROM_BLOCK(block), 0, BYTES_PER_BLOCK);
310 #endif
311 }
312 break;
313
314 case AT_MARK:
315 ATB_MARK_TO_HEAD(block);
316 free_tail = 0;
317 break;
318 }
319 }
320 }
321
gc_collect_start(void)322 void gc_collect_start(void) {
323 GC_ENTER();
324 MP_STATE_THREAD(gc_lock_depth)++;
325 #if MICROPY_GC_ALLOC_THRESHOLD
326 MP_STATE_MEM(gc_alloc_amount) = 0;
327 #endif
328 MP_STATE_MEM(gc_stack_overflow) = 0;
329
330 // Trace root pointers. This relies on the root pointers being organised
331 // correctly in the mp_state_ctx structure. We scan nlr_top, dict_locals,
332 // dict_globals, then the root pointer section of mp_state_vm.
333 void **ptrs = (void **)(void *)&mp_state_ctx;
334 size_t root_start = offsetof(mp_state_ctx_t, thread.dict_locals);
335 size_t root_end = offsetof(mp_state_ctx_t, vm.qstr_last_chunk);
336 gc_collect_root(ptrs + root_start / sizeof(void *), (root_end - root_start) / sizeof(void *));
337
338 #if MICROPY_ENABLE_PYSTACK
339 // Trace root pointers from the Python stack.
340 ptrs = (void **)(void *)MP_STATE_THREAD(pystack_start);
341 gc_collect_root(ptrs, (MP_STATE_THREAD(pystack_cur) - MP_STATE_THREAD(pystack_start)) / sizeof(void *));
342 #endif
343 }
344
345 // Address sanitizer needs to know that the access to ptrs[i] must always be
346 // considered OK, even if it's a load from an address that would normally be
347 // prohibited (due to being undefined, in a red zone, etc).
348 #if defined(__GNUC__) && (__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 8))
349 __attribute__((no_sanitize_address))
350 #endif
gc_get_ptr(void ** ptrs,int i)351 static void *gc_get_ptr(void **ptrs, int i) {
352 return ptrs[i];
353 }
354
gc_collect_root(void ** ptrs,size_t len)355 void gc_collect_root(void **ptrs, size_t len) {
356 for (size_t i = 0; i < len; i++) {
357 void *ptr = gc_get_ptr(ptrs, i);
358 if (VERIFY_PTR(ptr)) {
359 size_t block = BLOCK_FROM_PTR(ptr);
360 if (ATB_GET_KIND(block) == AT_HEAD) {
361 // An unmarked head: mark it, and mark all its children
362 TRACE_MARK(block, ptr);
363 ATB_HEAD_TO_MARK(block);
364 gc_mark_subtree(block);
365 }
366 }
367 }
368 }
369
gc_collect_end(void)370 void gc_collect_end(void) {
371 gc_deal_with_stack_overflow();
372 gc_sweep();
373 MP_STATE_MEM(gc_last_free_atb_index) = 0;
374 MP_STATE_THREAD(gc_lock_depth)--;
375 GC_EXIT();
376 }
377
gc_sweep_all(void)378 void gc_sweep_all(void) {
379 GC_ENTER();
380 MP_STATE_THREAD(gc_lock_depth)++;
381 MP_STATE_MEM(gc_stack_overflow) = 0;
382 gc_collect_end();
383 }
384
gc_info(gc_info_t * info)385 void gc_info(gc_info_t *info) {
386 GC_ENTER();
387 info->total = MP_STATE_MEM(gc_pool_end) - MP_STATE_MEM(gc_pool_start);
388 info->used = 0;
389 info->free = 0;
390 info->max_free = 0;
391 info->num_1block = 0;
392 info->num_2block = 0;
393 info->max_block = 0;
394 bool finish = false;
395 for (size_t block = 0, len = 0, len_free = 0; !finish;) {
396 size_t kind = ATB_GET_KIND(block);
397 switch (kind) {
398 case AT_FREE:
399 info->free += 1;
400 len_free += 1;
401 len = 0;
402 break;
403
404 case AT_HEAD:
405 info->used += 1;
406 len = 1;
407 break;
408
409 case AT_TAIL:
410 info->used += 1;
411 len += 1;
412 break;
413
414 case AT_MARK:
415 // shouldn't happen
416 break;
417 }
418
419 block++;
420 finish = (block == MP_STATE_MEM(gc_alloc_table_byte_len) * BLOCKS_PER_ATB);
421 // Get next block type if possible
422 if (!finish) {
423 kind = ATB_GET_KIND(block);
424 }
425
426 if (finish || kind == AT_FREE || kind == AT_HEAD) {
427 if (len == 1) {
428 info->num_1block += 1;
429 } else if (len == 2) {
430 info->num_2block += 1;
431 }
432 if (len > info->max_block) {
433 info->max_block = len;
434 }
435 if (finish || kind == AT_HEAD) {
436 if (len_free > info->max_free) {
437 info->max_free = len_free;
438 }
439 len_free = 0;
440 }
441 }
442 }
443
444 info->used *= BYTES_PER_BLOCK;
445 info->free *= BYTES_PER_BLOCK;
446 GC_EXIT();
447 }
448
gc_alloc(size_t n_bytes,unsigned int alloc_flags)449 void *gc_alloc(size_t n_bytes, unsigned int alloc_flags) {
450 bool has_finaliser = alloc_flags & GC_ALLOC_FLAG_HAS_FINALISER;
451 size_t n_blocks = ((n_bytes + BYTES_PER_BLOCK - 1) & (~(BYTES_PER_BLOCK - 1))) / BYTES_PER_BLOCK;
452 DEBUG_printf("gc_alloc(" UINT_FMT " bytes -> " UINT_FMT " blocks)\n", n_bytes, n_blocks);
453
454 // check for 0 allocation
455 if (n_blocks == 0) {
456 return NULL;
457 }
458
459 // check if GC is locked
460 if (MP_STATE_THREAD(gc_lock_depth) > 0) {
461 return NULL;
462 }
463
464 GC_ENTER();
465
466 size_t i;
467 size_t end_block;
468 size_t start_block;
469 size_t n_free;
470 int collected = !MP_STATE_MEM(gc_auto_collect_enabled);
471
472 #if MICROPY_GC_ALLOC_THRESHOLD
473 if (!collected && MP_STATE_MEM(gc_alloc_amount) >= MP_STATE_MEM(gc_alloc_threshold)) {
474 GC_EXIT();
475 gc_collect();
476 collected = 1;
477 GC_ENTER();
478 }
479 #endif
480
481 for (;;) {
482
483 // look for a run of n_blocks available blocks
484 n_free = 0;
485 for (i = MP_STATE_MEM(gc_last_free_atb_index); i < MP_STATE_MEM(gc_alloc_table_byte_len); i++) {
486 byte a = MP_STATE_MEM(gc_alloc_table_start)[i];
487 // *FORMAT-OFF*
488 if (ATB_0_IS_FREE(a)) { if (++n_free >= n_blocks) { i = i * BLOCKS_PER_ATB + 0; goto found; } } else { n_free = 0; }
489 if (ATB_1_IS_FREE(a)) { if (++n_free >= n_blocks) { i = i * BLOCKS_PER_ATB + 1; goto found; } } else { n_free = 0; }
490 if (ATB_2_IS_FREE(a)) { if (++n_free >= n_blocks) { i = i * BLOCKS_PER_ATB + 2; goto found; } } else { n_free = 0; }
491 if (ATB_3_IS_FREE(a)) { if (++n_free >= n_blocks) { i = i * BLOCKS_PER_ATB + 3; goto found; } } else { n_free = 0; }
492 // *FORMAT-ON*
493 }
494
495 GC_EXIT();
496 // nothing found!
497 if (collected) {
498 return NULL;
499 }
500 DEBUG_printf("gc_alloc(" UINT_FMT "): no free mem, triggering GC\n", n_bytes);
501 gc_collect();
502 collected = 1;
503 GC_ENTER();
504 }
505
506 // found, ending at block i inclusive
507 found:
508 // get starting and end blocks, both inclusive
509 end_block = i;
510 start_block = i - n_free + 1;
511
512 // Set last free ATB index to block after last block we found, for start of
513 // next scan. To reduce fragmentation, we only do this if we were looking
514 // for a single free block, which guarantees that there are no free blocks
515 // before this one. Also, whenever we free or shink a block we must check
516 // if this index needs adjusting (see gc_realloc and gc_free).
517 if (n_free == 1) {
518 MP_STATE_MEM(gc_last_free_atb_index) = (i + 1) / BLOCKS_PER_ATB;
519 }
520
521 // mark first block as used head
522 ATB_FREE_TO_HEAD(start_block);
523
524 // mark rest of blocks as used tail
525 // TODO for a run of many blocks can make this more efficient
526 for (size_t bl = start_block + 1; bl <= end_block; bl++) {
527 ATB_FREE_TO_TAIL(bl);
528 }
529
530 // get pointer to first block
531 // we must create this pointer before unlocking the GC so a collection can find it
532 void *ret_ptr = (void *)(MP_STATE_MEM(gc_pool_start) + start_block * BYTES_PER_BLOCK);
533 DEBUG_printf("gc_alloc(%p)\n", ret_ptr);
534
535 #if MICROPY_GC_ALLOC_THRESHOLD
536 MP_STATE_MEM(gc_alloc_amount) += n_blocks;
537 #endif
538
539 GC_EXIT();
540
541 #if MICROPY_GC_CONSERVATIVE_CLEAR
542 // be conservative and zero out all the newly allocated blocks
543 memset((byte *)ret_ptr, 0, (end_block - start_block + 1) * BYTES_PER_BLOCK);
544 #else
545 // zero out the additional bytes of the newly allocated blocks
546 // This is needed because the blocks may have previously held pointers
547 // to the heap and will not be set to something else if the caller
548 // doesn't actually use the entire block. As such they will continue
549 // to point to the heap and may prevent other blocks from being reclaimed.
550 memset((byte *)ret_ptr + n_bytes, 0, (end_block - start_block + 1) * BYTES_PER_BLOCK - n_bytes);
551 #endif
552
553 #if MICROPY_ENABLE_FINALISER
554 if (has_finaliser) {
555 // clear type pointer in case it is never set
556 ((mp_obj_base_t *)ret_ptr)->type = NULL;
557 // set mp_obj flag only if it has a finaliser
558 GC_ENTER();
559 FTB_SET(start_block);
560 GC_EXIT();
561 }
562 #else
563 (void)has_finaliser;
564 #endif
565
566 #if EXTENSIVE_HEAP_PROFILING
567 gc_dump_alloc_table();
568 #endif
569
570 return ret_ptr;
571 }
572
573 /*
574 void *gc_alloc(mp_uint_t n_bytes) {
575 return _gc_alloc(n_bytes, false);
576 }
577
578 void *gc_alloc_with_finaliser(mp_uint_t n_bytes) {
579 return _gc_alloc(n_bytes, true);
580 }
581 */
582
583 // force the freeing of a piece of memory
584 // TODO: freeing here does not call finaliser
gc_free(void * ptr)585 void gc_free(void *ptr) {
586 if (MP_STATE_THREAD(gc_lock_depth) > 0) {
587 // TODO how to deal with this error?
588 return;
589 }
590
591 GC_ENTER();
592
593 DEBUG_printf("gc_free(%p)\n", ptr);
594
595 if (ptr == NULL) {
596 GC_EXIT();
597 } else {
598 // get the GC block number corresponding to this pointer
599 assert(VERIFY_PTR(ptr));
600 size_t block = BLOCK_FROM_PTR(ptr);
601 assert(ATB_GET_KIND(block) == AT_HEAD);
602
603 #if MICROPY_ENABLE_FINALISER
604 FTB_CLEAR(block);
605 #endif
606
607 // set the last_free pointer to this block if it's earlier in the heap
608 if (block / BLOCKS_PER_ATB < MP_STATE_MEM(gc_last_free_atb_index)) {
609 MP_STATE_MEM(gc_last_free_atb_index) = block / BLOCKS_PER_ATB;
610 }
611
612 // free head and all of its tail blocks
613 do {
614 ATB_ANY_TO_FREE(block);
615 block += 1;
616 } while (ATB_GET_KIND(block) == AT_TAIL);
617
618 GC_EXIT();
619
620 #if EXTENSIVE_HEAP_PROFILING
621 gc_dump_alloc_table();
622 #endif
623 }
624 }
625
gc_nbytes(const void * ptr)626 size_t gc_nbytes(const void *ptr) {
627 GC_ENTER();
628 if (VERIFY_PTR(ptr)) {
629 size_t block = BLOCK_FROM_PTR(ptr);
630 if (ATB_GET_KIND(block) == AT_HEAD) {
631 // work out number of consecutive blocks in the chain starting with this on
632 size_t n_blocks = 0;
633 do {
634 n_blocks += 1;
635 } while (ATB_GET_KIND(block + n_blocks) == AT_TAIL);
636 GC_EXIT();
637 return n_blocks * BYTES_PER_BLOCK;
638 }
639 }
640
641 // invalid pointer
642 GC_EXIT();
643 return 0;
644 }
645
646 #if 0
647 // old, simple realloc that didn't expand memory in place
648 void *gc_realloc(void *ptr, mp_uint_t n_bytes) {
649 mp_uint_t n_existing = gc_nbytes(ptr);
650 if (n_bytes <= n_existing) {
651 return ptr;
652 } else {
653 bool has_finaliser;
654 if (ptr == NULL) {
655 has_finaliser = false;
656 } else {
657 #if MICROPY_ENABLE_FINALISER
658 has_finaliser = FTB_GET(BLOCK_FROM_PTR((mp_uint_t)ptr));
659 #else
660 has_finaliser = false;
661 #endif
662 }
663 void *ptr2 = gc_alloc(n_bytes, has_finaliser);
664 if (ptr2 == NULL) {
665 return ptr2;
666 }
667 memcpy(ptr2, ptr, n_existing);
668 gc_free(ptr);
669 return ptr2;
670 }
671 }
672
673 #else // Alternative gc_realloc impl
674
gc_realloc(void * ptr_in,size_t n_bytes,bool allow_move)675 void *gc_realloc(void *ptr_in, size_t n_bytes, bool allow_move) {
676 // check for pure allocation
677 if (ptr_in == NULL) {
678 return gc_alloc(n_bytes, false);
679 }
680
681 // check for pure free
682 if (n_bytes == 0) {
683 gc_free(ptr_in);
684 return NULL;
685 }
686
687 if (MP_STATE_THREAD(gc_lock_depth) > 0) {
688 return NULL;
689 }
690
691 void *ptr = ptr_in;
692
693 GC_ENTER();
694
695 // get the GC block number corresponding to this pointer
696 assert(VERIFY_PTR(ptr));
697 size_t block = BLOCK_FROM_PTR(ptr);
698 assert(ATB_GET_KIND(block) == AT_HEAD);
699
700 // compute number of new blocks that are requested
701 size_t new_blocks = (n_bytes + BYTES_PER_BLOCK - 1) / BYTES_PER_BLOCK;
702
703 // Get the total number of consecutive blocks that are already allocated to
704 // this chunk of memory, and then count the number of free blocks following
705 // it. Stop if we reach the end of the heap, or if we find enough extra
706 // free blocks to satisfy the realloc. Note that we need to compute the
707 // total size of the existing memory chunk so we can correctly and
708 // efficiently shrink it (see below for shrinking code).
709 size_t n_free = 0;
710 size_t n_blocks = 1; // counting HEAD block
711 size_t max_block = MP_STATE_MEM(gc_alloc_table_byte_len) * BLOCKS_PER_ATB;
712 for (size_t bl = block + n_blocks; bl < max_block; bl++) {
713 byte block_type = ATB_GET_KIND(bl);
714 if (block_type == AT_TAIL) {
715 n_blocks++;
716 continue;
717 }
718 if (block_type == AT_FREE) {
719 n_free++;
720 if (n_blocks + n_free >= new_blocks) {
721 // stop as soon as we find enough blocks for n_bytes
722 break;
723 }
724 continue;
725 }
726 break;
727 }
728
729 // return original ptr if it already has the requested number of blocks
730 if (new_blocks == n_blocks) {
731 GC_EXIT();
732 return ptr_in;
733 }
734
735 // check if we can shrink the allocated area
736 if (new_blocks < n_blocks) {
737 // free unneeded tail blocks
738 for (size_t bl = block + new_blocks, count = n_blocks - new_blocks; count > 0; bl++, count--) {
739 ATB_ANY_TO_FREE(bl);
740 }
741
742 // set the last_free pointer to end of this block if it's earlier in the heap
743 if ((block + new_blocks) / BLOCKS_PER_ATB < MP_STATE_MEM(gc_last_free_atb_index)) {
744 MP_STATE_MEM(gc_last_free_atb_index) = (block + new_blocks) / BLOCKS_PER_ATB;
745 }
746
747 GC_EXIT();
748
749 #if EXTENSIVE_HEAP_PROFILING
750 gc_dump_alloc_table();
751 #endif
752
753 return ptr_in;
754 }
755
756 // check if we can expand in place
757 if (new_blocks <= n_blocks + n_free) {
758 // mark few more blocks as used tail
759 for (size_t bl = block + n_blocks; bl < block + new_blocks; bl++) {
760 assert(ATB_GET_KIND(bl) == AT_FREE);
761 ATB_FREE_TO_TAIL(bl);
762 }
763
764 GC_EXIT();
765
766 #if MICROPY_GC_CONSERVATIVE_CLEAR
767 // be conservative and zero out all the newly allocated blocks
768 memset((byte *)ptr_in + n_blocks * BYTES_PER_BLOCK, 0, (new_blocks - n_blocks) * BYTES_PER_BLOCK);
769 #else
770 // zero out the additional bytes of the newly allocated blocks (see comment above in gc_alloc)
771 memset((byte *)ptr_in + n_bytes, 0, new_blocks * BYTES_PER_BLOCK - n_bytes);
772 #endif
773
774 #if EXTENSIVE_HEAP_PROFILING
775 gc_dump_alloc_table();
776 #endif
777
778 return ptr_in;
779 }
780
781 #if MICROPY_ENABLE_FINALISER
782 bool ftb_state = FTB_GET(block);
783 #else
784 bool ftb_state = false;
785 #endif
786
787 GC_EXIT();
788
789 if (!allow_move) {
790 // not allowed to move memory block so return failure
791 return NULL;
792 }
793
794 // can't resize inplace; try to find a new contiguous chain
795 void *ptr_out = gc_alloc(n_bytes, ftb_state);
796
797 // check that the alloc succeeded
798 if (ptr_out == NULL) {
799 return NULL;
800 }
801
802 DEBUG_printf("gc_realloc(%p -> %p)\n", ptr_in, ptr_out);
803 memcpy(ptr_out, ptr_in, n_blocks * BYTES_PER_BLOCK);
804 gc_free(ptr_in);
805 return ptr_out;
806 }
807 #endif // Alternative gc_realloc impl
808
gc_dump_info(void)809 void gc_dump_info(void) {
810 gc_info_t info;
811 gc_info(&info);
812 mp_printf(&mp_plat_print, "GC: total: %u, used: %u, free: %u\n",
813 (uint)info.total, (uint)info.used, (uint)info.free);
814 mp_printf(&mp_plat_print, " No. of 1-blocks: %u, 2-blocks: %u, max blk sz: %u, max free sz: %u\n",
815 (uint)info.num_1block, (uint)info.num_2block, (uint)info.max_block, (uint)info.max_free);
816 }
817
gc_dump_alloc_table(void)818 void gc_dump_alloc_table(void) {
819 GC_ENTER();
820 static const size_t DUMP_BYTES_PER_LINE = 64;
821 #if !EXTENSIVE_HEAP_PROFILING
822 // When comparing heap output we don't want to print the starting
823 // pointer of the heap because it changes from run to run.
824 mp_printf(&mp_plat_print, "GC memory layout; from %p:", MP_STATE_MEM(gc_pool_start));
825 #endif
826 for (size_t bl = 0; bl < MP_STATE_MEM(gc_alloc_table_byte_len) * BLOCKS_PER_ATB; bl++) {
827 if (bl % DUMP_BYTES_PER_LINE == 0) {
828 // a new line of blocks
829 {
830 // check if this line contains only free blocks
831 size_t bl2 = bl;
832 while (bl2 < MP_STATE_MEM(gc_alloc_table_byte_len) * BLOCKS_PER_ATB && ATB_GET_KIND(bl2) == AT_FREE) {
833 bl2++;
834 }
835 if (bl2 - bl >= 2 * DUMP_BYTES_PER_LINE) {
836 // there are at least 2 lines containing only free blocks, so abbreviate their printing
837 mp_printf(&mp_plat_print, "\n (%u lines all free)", (uint)(bl2 - bl) / DUMP_BYTES_PER_LINE);
838 bl = bl2 & (~(DUMP_BYTES_PER_LINE - 1));
839 if (bl >= MP_STATE_MEM(gc_alloc_table_byte_len) * BLOCKS_PER_ATB) {
840 // got to end of heap
841 break;
842 }
843 }
844 }
845 // print header for new line of blocks
846 // (the cast to uint32_t is for 16-bit ports)
847 // mp_printf(&mp_plat_print, "\n%05x: ", (uint)(PTR_FROM_BLOCK(bl) & (uint32_t)0xfffff));
848 mp_printf(&mp_plat_print, "\n%05x: ", (uint)((bl * BYTES_PER_BLOCK) & (uint32_t)0xfffff));
849 }
850 int c = ' ';
851 switch (ATB_GET_KIND(bl)) {
852 case AT_FREE:
853 c = '.';
854 break;
855 /* this prints out if the object is reachable from BSS or STACK (for unix only)
856 case AT_HEAD: {
857 c = 'h';
858 void **ptrs = (void**)(void*)&mp_state_ctx;
859 mp_uint_t len = offsetof(mp_state_ctx_t, vm.stack_top) / sizeof(mp_uint_t);
860 for (mp_uint_t i = 0; i < len; i++) {
861 mp_uint_t ptr = (mp_uint_t)ptrs[i];
862 if (VERIFY_PTR(ptr) && BLOCK_FROM_PTR(ptr) == bl) {
863 c = 'B';
864 break;
865 }
866 }
867 if (c == 'h') {
868 ptrs = (void**)&c;
869 len = ((mp_uint_t)MP_STATE_THREAD(stack_top) - (mp_uint_t)&c) / sizeof(mp_uint_t);
870 for (mp_uint_t i = 0; i < len; i++) {
871 mp_uint_t ptr = (mp_uint_t)ptrs[i];
872 if (VERIFY_PTR(ptr) && BLOCK_FROM_PTR(ptr) == bl) {
873 c = 'S';
874 break;
875 }
876 }
877 }
878 break;
879 }
880 */
881 /* this prints the uPy object type of the head block */
882 case AT_HEAD: {
883 void **ptr = (void **)(MP_STATE_MEM(gc_pool_start) + bl * BYTES_PER_BLOCK);
884 if (*ptr == &mp_type_tuple) {
885 c = 'T';
886 } else if (*ptr == &mp_type_list) {
887 c = 'L';
888 } else if (*ptr == &mp_type_dict) {
889 c = 'D';
890 } else if (*ptr == &mp_type_str || *ptr == &mp_type_bytes) {
891 c = 'S';
892 }
893 #if MICROPY_PY_BUILTINS_BYTEARRAY
894 else if (*ptr == &mp_type_bytearray) {
895 c = 'A';
896 }
897 #endif
898 #if MICROPY_PY_ARRAY
899 else if (*ptr == &mp_type_array) {
900 c = 'A';
901 }
902 #endif
903 #if MICROPY_PY_BUILTINS_FLOAT
904 else if (*ptr == &mp_type_float) {
905 c = 'F';
906 }
907 #endif
908 else if (*ptr == &mp_type_fun_bc) {
909 c = 'B';
910 } else if (*ptr == &mp_type_module) {
911 c = 'M';
912 } else {
913 c = 'h';
914 #if 0
915 // This code prints "Q" for qstr-pool data, and "q" for qstr-str
916 // data. It can be useful to see how qstrs are being allocated,
917 // but is disabled by default because it is very slow.
918 for (qstr_pool_t *pool = MP_STATE_VM(last_pool); c == 'h' && pool != NULL; pool = pool->prev) {
919 if ((qstr_pool_t *)ptr == pool) {
920 c = 'Q';
921 break;
922 }
923 for (const byte **q = pool->qstrs, **q_top = pool->qstrs + pool->len; q < q_top; q++) {
924 if ((const byte *)ptr == *q) {
925 c = 'q';
926 break;
927 }
928 }
929 }
930 #endif
931 }
932 break;
933 }
934 case AT_TAIL:
935 c = '=';
936 break;
937 case AT_MARK:
938 c = 'm';
939 break;
940 }
941 mp_printf(&mp_plat_print, "%c", c);
942 }
943 mp_print_str(&mp_plat_print, "\n");
944 GC_EXIT();
945 }
946
947 #if 0
948 // For testing the GC functions
949 void gc_test(void) {
950 mp_uint_t len = 500;
951 mp_uint_t *heap = malloc(len);
952 gc_init(heap, heap + len / sizeof(mp_uint_t));
953 void *ptrs[100];
954 {
955 mp_uint_t **p = gc_alloc(16, false);
956 p[0] = gc_alloc(64, false);
957 p[1] = gc_alloc(1, false);
958 p[2] = gc_alloc(1, false);
959 p[3] = gc_alloc(1, false);
960 mp_uint_t ***p2 = gc_alloc(16, false);
961 p2[0] = p;
962 p2[1] = p;
963 ptrs[0] = p2;
964 }
965 for (int i = 0; i < 25; i += 2) {
966 mp_uint_t *p = gc_alloc(i, false);
967 printf("p=%p\n", p);
968 if (i & 3) {
969 // ptrs[i] = p;
970 }
971 }
972
973 printf("Before GC:\n");
974 gc_dump_alloc_table();
975 printf("Starting GC...\n");
976 gc_collect_start();
977 gc_collect_root(ptrs, sizeof(ptrs) / sizeof(void *));
978 gc_collect_end();
979 printf("After GC:\n");
980 gc_dump_alloc_table();
981 }
982 #endif
983
984 #endif // MICROPY_ENABLE_GC
985