Branch data Line data Source code
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_DEBUG_VALGRIND
36 : : #include <valgrind/memcheck.h>
37 : : #endif
38 : :
39 : : #if MICROPY_ENABLE_GC
40 : :
41 : : #if MICROPY_DEBUG_VERBOSE // print debugging info
42 : : #define DEBUG_PRINT (1)
43 : : #define DEBUG_printf DEBUG_printf
44 : : #else // don't print debugging info
45 : : #define DEBUG_PRINT (0)
46 : : #define DEBUG_printf(...) (void)0
47 : : #endif
48 : :
49 : : // make this 1 to dump the heap each time it changes
50 : : #define EXTENSIVE_HEAP_PROFILING (0)
51 : :
52 : : // make this 1 to zero out swept memory to more eagerly
53 : : // detect untraced object still in use
54 : : #define CLEAR_ON_SWEEP (0)
55 : :
56 : : #define WORDS_PER_BLOCK ((MICROPY_BYTES_PER_GC_BLOCK) / MP_BYTES_PER_OBJ_WORD)
57 : : #define BYTES_PER_BLOCK (MICROPY_BYTES_PER_GC_BLOCK)
58 : :
59 : : // ATB = allocation table byte
60 : : // 0b00 = FREE -- free block
61 : : // 0b01 = HEAD -- head of a chain of blocks
62 : : // 0b10 = TAIL -- in the tail of a chain of blocks
63 : : // 0b11 = MARK -- marked head block
64 : :
65 : : #define AT_FREE (0)
66 : : #define AT_HEAD (1)
67 : : #define AT_TAIL (2)
68 : : #define AT_MARK (3)
69 : :
70 : : #define BLOCKS_PER_ATB (4)
71 : : #define ATB_MASK_0 (0x03)
72 : : #define ATB_MASK_1 (0x0c)
73 : : #define ATB_MASK_2 (0x30)
74 : : #define ATB_MASK_3 (0xc0)
75 : :
76 : : #define ATB_0_IS_FREE(a) (((a) & ATB_MASK_0) == 0)
77 : : #define ATB_1_IS_FREE(a) (((a) & ATB_MASK_1) == 0)
78 : : #define ATB_2_IS_FREE(a) (((a) & ATB_MASK_2) == 0)
79 : : #define ATB_3_IS_FREE(a) (((a) & ATB_MASK_3) == 0)
80 : :
81 : : #if MICROPY_GC_SPLIT_HEAP
82 : : #define NEXT_AREA(area) ((area)->next)
83 : : #else
84 : : #define NEXT_AREA(area) (NULL)
85 : : #endif
86 : :
87 : : #define BLOCK_SHIFT(block) (2 * ((block) & (BLOCKS_PER_ATB - 1)))
88 : : #define ATB_GET_KIND(area, block) (((area)->gc_alloc_table_start[(block) / BLOCKS_PER_ATB] >> BLOCK_SHIFT(block)) & 3)
89 : : #define ATB_ANY_TO_FREE(area, block) do { area->gc_alloc_table_start[(block) / BLOCKS_PER_ATB] &= (~(AT_MARK << BLOCK_SHIFT(block))); } while (0)
90 : : #define ATB_FREE_TO_HEAD(area, block) do { area->gc_alloc_table_start[(block) / BLOCKS_PER_ATB] |= (AT_HEAD << BLOCK_SHIFT(block)); } while (0)
91 : : #define ATB_FREE_TO_TAIL(area, block) do { area->gc_alloc_table_start[(block) / BLOCKS_PER_ATB] |= (AT_TAIL << BLOCK_SHIFT(block)); } while (0)
92 : : #define ATB_HEAD_TO_MARK(area, block) do { area->gc_alloc_table_start[(block) / BLOCKS_PER_ATB] |= (AT_MARK << BLOCK_SHIFT(block)); } while (0)
93 : : #define ATB_MARK_TO_HEAD(area, block) do { area->gc_alloc_table_start[(block) / BLOCKS_PER_ATB] &= (~(AT_TAIL << BLOCK_SHIFT(block))); } while (0)
94 : :
95 : : #define BLOCK_FROM_PTR(area, ptr) (((byte *)(ptr) - area->gc_pool_start) / BYTES_PER_BLOCK)
96 : : #define PTR_FROM_BLOCK(area, block) (((block) * BYTES_PER_BLOCK + (uintptr_t)area->gc_pool_start))
97 : :
98 : : // After the ATB, there must be a byte filled with AT_FREE so that gc_mark_tree
99 : : // cannot erroneously conclude that a block extends past the end of the GC heap
100 : : // due to bit patterns in the FTB (or first block, if finalizers are disabled)
101 : : // being interpreted as AT_TAIL.
102 : : #define ALLOC_TABLE_GAP_BYTE (1)
103 : :
104 : : #if MICROPY_ENABLE_FINALISER
105 : : // FTB = finaliser table byte
106 : : // if set, then the corresponding block may have a finaliser
107 : :
108 : : #define BLOCKS_PER_FTB (8)
109 : :
110 : : #define FTB_GET(area, block) ((area->gc_finaliser_table_start[(block) / BLOCKS_PER_FTB] >> ((block) & 7)) & 1)
111 : : #define FTB_SET(area, block) do { area->gc_finaliser_table_start[(block) / BLOCKS_PER_FTB] |= (1 << ((block) & 7)); } while (0)
112 : : #define FTB_CLEAR(area, block) do { area->gc_finaliser_table_start[(block) / BLOCKS_PER_FTB] &= (~(1 << ((block) & 7))); } while (0)
113 : : #endif
114 : :
115 : : #if MICROPY_PY_THREAD && !MICROPY_PY_THREAD_GIL
116 : : #define GC_ENTER() mp_thread_mutex_lock(&MP_STATE_MEM(gc_mutex), 1)
117 : : #define GC_EXIT() mp_thread_mutex_unlock(&MP_STATE_MEM(gc_mutex))
118 : : #else
119 : : #define GC_ENTER()
120 : : #define GC_EXIT()
121 : : #endif
122 : :
123 : : // TODO waste less memory; currently requires that all entries in alloc_table have a corresponding block in pool
124 : 17328 : static void gc_setup_area(mp_state_mem_area_t *area, void *start, void *end) {
125 : : // calculate parameters for GC (T=total, A=alloc table, F=finaliser table, P=pool; all in bytes):
126 : : // T = A + F + P
127 : : // F = A * BLOCKS_PER_ATB / BLOCKS_PER_FTB
128 : : // P = A * BLOCKS_PER_ATB * BYTES_PER_BLOCK
129 : : // => T = A * (1 + BLOCKS_PER_ATB / BLOCKS_PER_FTB + BLOCKS_PER_ATB * BYTES_PER_BLOCK)
130 : 17328 : size_t total_byte_len = (byte *)end - (byte *)start;
131 : : #if MICROPY_ENABLE_FINALISER
132 : 17328 : area->gc_alloc_table_byte_len = (total_byte_len - ALLOC_TABLE_GAP_BYTE)
133 : 17328 : * MP_BITS_PER_BYTE
134 : 17328 : / (
135 : : MP_BITS_PER_BYTE
136 : : + MP_BITS_PER_BYTE * BLOCKS_PER_ATB / BLOCKS_PER_FTB
137 : : + MP_BITS_PER_BYTE * BLOCKS_PER_ATB * BYTES_PER_BLOCK
138 : : );
139 : : #else
140 : : area->gc_alloc_table_byte_len = (total_byte_len - ALLOC_TABLE_GAP_BYTE) / (1 + MP_BITS_PER_BYTE / 2 * BYTES_PER_BLOCK);
141 : : #endif
142 : :
143 : 17328 : area->gc_alloc_table_start = (byte *)start;
144 : :
145 : : #if MICROPY_ENABLE_FINALISER
146 : 17328 : size_t gc_finaliser_table_byte_len = (area->gc_alloc_table_byte_len * BLOCKS_PER_ATB + BLOCKS_PER_FTB - 1) / BLOCKS_PER_FTB;
147 : 17328 : area->gc_finaliser_table_start = area->gc_alloc_table_start + area->gc_alloc_table_byte_len + ALLOC_TABLE_GAP_BYTE;
148 : : #endif
149 : :
150 : 17328 : size_t gc_pool_block_len = area->gc_alloc_table_byte_len * BLOCKS_PER_ATB;
151 : 17328 : area->gc_pool_start = (byte *)end - gc_pool_block_len * BYTES_PER_BLOCK;
152 : 17328 : area->gc_pool_end = end;
153 : :
154 : : #if MICROPY_ENABLE_FINALISER
155 [ - + ]: 17328 : assert(area->gc_pool_start >= area->gc_finaliser_table_start + gc_finaliser_table_byte_len);
156 : : #endif
157 : :
158 : : #if MICROPY_ENABLE_FINALISER
159 : : // clear ATB's and FTB's
160 : 17328 : memset(area->gc_alloc_table_start, 0, gc_finaliser_table_byte_len + area->gc_alloc_table_byte_len + ALLOC_TABLE_GAP_BYTE);
161 : : #else
162 : : // clear ATB's
163 : : memset(area->gc_alloc_table_start, 0, area->gc_alloc_table_byte_len + ALLOC_TABLE_GAP_BYTE);
164 : : #endif
165 : :
166 : 17328 : area->gc_last_free_atb_index = 0;
167 : 17328 : area->gc_last_used_block = 0;
168 : :
169 : : #if MICROPY_GC_SPLIT_HEAP
170 : 17328 : area->next = NULL;
171 : : #endif
172 : :
173 : 17328 : DEBUG_printf("GC layout:\n");
174 : 17328 : DEBUG_printf(" alloc table at %p, length " UINT_FMT " bytes, "
175 : : UINT_FMT " blocks\n",
176 : : area->gc_alloc_table_start, area->gc_alloc_table_byte_len,
177 : : area->gc_alloc_table_byte_len * BLOCKS_PER_ATB);
178 : : #if MICROPY_ENABLE_FINALISER
179 : 17328 : DEBUG_printf(" finaliser table at %p, length " UINT_FMT " bytes, "
180 : : UINT_FMT " blocks\n", area->gc_finaliser_table_start,
181 : : gc_finaliser_table_byte_len,
182 : : gc_finaliser_table_byte_len * BLOCKS_PER_FTB);
183 : : #endif
184 : 17328 : DEBUG_printf(" pool at %p, length " UINT_FMT " bytes, "
185 : : UINT_FMT " blocks\n", area->gc_pool_start,
186 : : gc_pool_block_len * BYTES_PER_BLOCK, gc_pool_block_len);
187 : 17328 : }
188 : :
189 : 7404 : void gc_init(void *start, void *end) {
190 : : // align end pointer on block boundary
191 : 7404 : end = (void *)((uintptr_t)end & (~(BYTES_PER_BLOCK - 1)));
192 : 7404 : DEBUG_printf("Initializing GC heap: %p..%p = " UINT_FMT " bytes\n", start, end, (byte *)end - (byte *)start);
193 : :
194 : 7404 : gc_setup_area(&MP_STATE_MEM(area), start, end);
195 : :
196 : : // set last free ATB index to start of heap
197 : : #if MICROPY_GC_SPLIT_HEAP
198 : 7404 : MP_STATE_MEM(gc_last_free_area) = &MP_STATE_MEM(area);
199 : : #endif
200 : :
201 : : // unlock the GC
202 : 7404 : MP_STATE_THREAD(gc_lock_depth) = 0;
203 : :
204 : : // allow auto collection
205 : 7404 : MP_STATE_MEM(gc_auto_collect_enabled) = 1;
206 : :
207 : : #if MICROPY_GC_ALLOC_THRESHOLD
208 : : // by default, maxuint for gc threshold, effectively turning gc-by-threshold off
209 : 7404 : MP_STATE_MEM(gc_alloc_threshold) = (size_t)-1;
210 : 7404 : MP_STATE_MEM(gc_alloc_amount) = 0;
211 : : #endif
212 : :
213 : : #if MICROPY_PY_THREAD && !MICROPY_PY_THREAD_GIL
214 : 7404 : mp_thread_mutex_init(&MP_STATE_MEM(gc_mutex));
215 : : #endif
216 : 7404 : }
217 : :
218 : : #if MICROPY_GC_SPLIT_HEAP
219 : 9924 : void gc_add(void *start, void *end) {
220 : : // Place the area struct at the start of the area.
221 : 9924 : mp_state_mem_area_t *area = (mp_state_mem_area_t *)start;
222 : 9924 : start = (void *)((uintptr_t)start + sizeof(mp_state_mem_area_t));
223 : :
224 : 9924 : end = (void *)((uintptr_t)end & (~(BYTES_PER_BLOCK - 1)));
225 : 9924 : DEBUG_printf("Adding GC heap: %p..%p = " UINT_FMT " bytes\n", start, end, (byte *)end - (byte *)start);
226 : :
227 : : // Init this area
228 : 9924 : gc_setup_area(area, start, end);
229 : :
230 : : // Find the last registered area in the linked list
231 : 9924 : mp_state_mem_area_t *prev_area = &MP_STATE_MEM(area);
232 [ + + ]: 19848 : while (prev_area->next != NULL) {
233 : : prev_area = prev_area->next;
234 : : }
235 : :
236 : : // Add this area to the linked list
237 : 9924 : prev_area->next = area;
238 : 9924 : }
239 : :
240 : : #if MICROPY_GC_SPLIT_HEAP_AUTO
241 : : // Try to automatically add a heap area large enough to fulfill 'failed_alloc'.
242 : : static bool gc_try_add_heap(size_t failed_alloc) {
243 : : // 'needed' is the size of a heap large enough to hold failed_alloc, with
244 : : // the additional metadata overheads as calculated in gc_setup_area().
245 : : //
246 : : // Rather than reproduce all of that logic here, we approximate that adding
247 : : // (13/512) is enough overhead for sufficiently large heap areas (the
248 : : // overhead converges to 3/128, but there's some fixed overhead and some
249 : : // rounding up of partial block sizes).
250 : : size_t needed = failed_alloc + MAX(2048, failed_alloc * 13 / 512);
251 : :
252 : : size_t avail = gc_get_max_new_split();
253 : :
254 : : DEBUG_printf("gc_try_add_heap failed_alloc " UINT_FMT ", "
255 : : "needed " UINT_FMT ", avail " UINT_FMT " bytes \n",
256 : : failed_alloc,
257 : : needed,
258 : : avail);
259 : :
260 : : if (avail < needed) {
261 : : // Can't fit this allocation, or system heap has nearly run out anyway
262 : : return false;
263 : : }
264 : :
265 : : // Deciding how much to grow the total heap by each time is tricky:
266 : : //
267 : : // - Grow by too small amounts, leads to heap fragmentation issues.
268 : : //
269 : : // - Grow by too large amounts, may lead to system heap running out of
270 : : // space.
271 : : //
272 : : // Currently, this implementation is:
273 : : //
274 : : // - At minimum, aim to double the total heap size each time we add a new
275 : : // heap. i.e. without any large single allocations, total size will be
276 : : // 64KB -> 128KB -> 256KB -> 512KB -> 1MB, etc
277 : : //
278 : : // - If the failed allocation is too large to fit in that size, the new
279 : : // heap is made exactly large enough for that allocation. Future growth
280 : : // will double the total heap size again.
281 : : //
282 : : // - If the new heap won't fit in the available free space, add the largest
283 : : // new heap that will fit (this may lead to failed system heap allocations
284 : : // elsewhere, but some allocation will likely fail in this circumstance!)
285 : :
286 : : // Compute total number of blocks in the current heap.
287 : : size_t total_blocks = 0;
288 : : for (mp_state_mem_area_t *area = &MP_STATE_MEM(area);
289 : : area != NULL;
290 : : area = NEXT_AREA(area)) {
291 : : total_blocks += area->gc_alloc_table_byte_len * BLOCKS_PER_ATB;
292 : : }
293 : :
294 : : // Compute bytes needed to build a heap with total_blocks blocks.
295 : : size_t total_heap =
296 : : total_blocks / BLOCKS_PER_ATB
297 : : #if MICROPY_ENABLE_FINALISER
298 : : + total_blocks / BLOCKS_PER_FTB
299 : : #endif
300 : : + total_blocks * BYTES_PER_BLOCK
301 : : + ALLOC_TABLE_GAP_BYTE
302 : : + sizeof(mp_state_mem_area_t);
303 : :
304 : : // Round up size to the nearest multiple of BYTES_PER_BLOCK.
305 : : total_heap = (total_heap + BYTES_PER_BLOCK - 1) & (~(BYTES_PER_BLOCK - 1));
306 : :
307 : : DEBUG_printf("total_heap " UINT_FMT " bytes\n", total_heap);
308 : :
309 : : size_t to_alloc = MIN(avail, MAX(total_heap, needed));
310 : :
311 : : mp_state_mem_area_t *new_heap = MP_PLAT_ALLOC_HEAP(to_alloc);
312 : :
313 : : DEBUG_printf("MP_PLAT_ALLOC_HEAP " UINT_FMT " = %p\n",
314 : : to_alloc, new_heap);
315 : :
316 : : if (new_heap == NULL) {
317 : : // This should only fail:
318 : : // - In a threaded environment if another thread has
319 : : // allocated while this function ran.
320 : : // - If there is a bug in gc_get_max_new_split().
321 : : return false;
322 : : }
323 : :
324 : : gc_add(new_heap, (void *)new_heap + to_alloc);
325 : :
326 : : return true;
327 : : }
328 : : #endif
329 : :
330 : : #endif
331 : :
332 : 233 : void gc_lock(void) {
333 : : // This does not need to be atomic or have the GC mutex because:
334 : : // - each thread has its own gc_lock_depth so there are no races between threads;
335 : : // - a hard interrupt will only change gc_lock_depth during its execution, and
336 : : // upon return will restore the value of gc_lock_depth.
337 : 233 : MP_STATE_THREAD(gc_lock_depth)++;
338 : 233 : }
339 : :
340 : 233 : void gc_unlock(void) {
341 : : // This does not need to be atomic, See comment above in gc_lock.
342 : 233 : MP_STATE_THREAD(gc_lock_depth)--;
343 : 233 : }
344 : :
345 : 110 : bool gc_is_locked(void) {
346 : 110 : return MP_STATE_THREAD(gc_lock_depth) != 0;
347 : : }
348 : :
349 : : #if MICROPY_GC_SPLIT_HEAP
350 : : // Returns the area to which this pointer belongs, or NULL if it isn't
351 : : // allocated on the GC-managed heap.
352 : 29684922 : static inline mp_state_mem_area_t *gc_get_ptr_area(const void *ptr) {
353 : 29684922 : if (((uintptr_t)(ptr) & (BYTES_PER_BLOCK - 1)) != 0) { // must be aligned on a block
354 : : return NULL;
355 : : }
356 [ + - + + : 58899815 : for (mp_state_mem_area_t *area = &MP_STATE_MEM(area); area != NULL; area = NEXT_AREA(area)) {
+ - + + +
+ ]
357 [ + + + + : 42640360 : if (ptr >= (void *)area->gc_pool_start // must be above start of pool
+ + + + +
+ ]
358 [ - + - + : 7427963 : && ptr < (void *)area->gc_pool_end) { // must be below end of pool
- + + + +
+ ]
359 : : return area;
360 : : }
361 : : }
362 : : return NULL;
363 : : }
364 : : #endif
365 : :
366 : : // ptr should be of type void*
367 : : #define VERIFY_PTR(ptr) ( \
368 : : ((uintptr_t)(ptr) & (BYTES_PER_BLOCK - 1)) == 0 /* must be aligned on a block */ \
369 : : && ptr >= (void *)MP_STATE_MEM(area).gc_pool_start /* must be above start of pool */ \
370 : : && ptr < (void *)MP_STATE_MEM(area).gc_pool_end /* must be below end of pool */ \
371 : : )
372 : :
373 : : #ifndef TRACE_MARK
374 : : #if DEBUG_PRINT
375 : : #define TRACE_MARK(block, ptr) DEBUG_printf("gc_mark(%p)\n", ptr)
376 : : #else
377 : : #define TRACE_MARK(block, ptr)
378 : : #endif
379 : : #endif
380 : :
381 : : // Take the given block as the topmost block on the stack. Check all it's
382 : : // children: mark the unmarked child blocks and put those newly marked
383 : : // blocks on the stack. When all children have been checked, pop off the
384 : : // topmost block on the stack and repeat with that one.
385 : : #if MICROPY_GC_SPLIT_HEAP
386 : 18358 : static void gc_mark_subtree(mp_state_mem_area_t *area, size_t block)
387 : : #else
388 : : static void gc_mark_subtree(size_t block)
389 : : #endif
390 : : {
391 : : // Start with the block passed in the argument.
392 : 18358 : size_t sp = 0;
393 : 8361424 : for (;;) {
394 : : #if !MICROPY_GC_SPLIT_HEAP
395 : : mp_state_mem_area_t *area = &MP_STATE_MEM(area);
396 : : #endif
397 : :
398 : : // work out number of consecutive blocks in the chain starting with this one
399 : 4189891 : size_t n_blocks = 0;
400 : 4315842 : do {
401 : 4315842 : n_blocks += 1;
402 [ + + ]: 4315842 : } while (ATB_GET_KIND(area, block + n_blocks) == AT_TAIL);
403 : :
404 : : // check that the consecutive blocks didn't overflow past the end of the area
405 [ - + ]: 4189891 : assert(area->gc_pool_start + (block + n_blocks) * BYTES_PER_BLOCK <= area->gc_pool_end);
406 : :
407 : : // check this block's children
408 : 4189891 : void **ptrs = (void **)PTR_FROM_BLOCK(area, block);
409 [ + + ]: 21453259 : for (size_t i = n_blocks * BYTES_PER_BLOCK / sizeof(void *); i > 0; i--, ptrs++) {
410 : 17263368 : MICROPY_GC_HOOK_LOOP(i);
411 : 17263368 : void *ptr = *ptrs;
412 : : // If this is a heap pointer that hasn't been marked, mark it and push
413 : : // it's children to the stack.
414 : : #if MICROPY_GC_SPLIT_HEAP
415 [ + + ]: 17263368 : mp_state_mem_area_t *ptr_area = gc_get_ptr_area(ptr);
416 [ + + ]: 14286976 : if (!ptr_area) {
417 : : // Not a heap-allocated pointer (might even be random data).
418 : 13087144 : continue;
419 : : }
420 : : #else
421 : : if (!VERIFY_PTR(ptr)) {
422 : : continue;
423 : : }
424 : : mp_state_mem_area_t *ptr_area = area;
425 : : #endif
426 : 4176224 : size_t ptr_block = BLOCK_FROM_PTR(ptr_area, ptr);
427 [ + + ]: 4176224 : if (ATB_GET_KIND(ptr_area, ptr_block) != AT_HEAD) {
428 : : // This block is already marked.
429 : 4409 : continue;
430 : : }
431 : : // An unmarked head. Mark it, and push it on gc stack.
432 : 4171815 : TRACE_MARK(ptr_block, ptr);
433 : 4171815 : ATB_HEAD_TO_MARK(ptr_area, ptr_block);
434 [ + + ]: 4171815 : if (sp < MICROPY_ALLOC_GC_STACK_SIZE) {
435 : 4171533 : MP_STATE_MEM(gc_block_stack)[sp] = ptr_block;
436 : : #if MICROPY_GC_SPLIT_HEAP
437 : 4171533 : MP_STATE_MEM(gc_area_stack)[sp] = ptr_area;
438 : : #endif
439 : 4171533 : sp += 1;
440 : : } else {
441 : 282 : MP_STATE_MEM(gc_stack_overflow) = 1;
442 : : }
443 : : }
444 : :
445 : : // Are there any blocks on the stack?
446 [ + + ]: 4189891 : if (sp == 0) {
447 : : break; // No, stack is empty, we're done.
448 : : }
449 : :
450 : : // pop the next block off the stack
451 : 4171533 : sp -= 1;
452 : 4171533 : block = MP_STATE_MEM(gc_block_stack)[sp];
453 : : #if MICROPY_GC_SPLIT_HEAP
454 : 4171533 : area = MP_STATE_MEM(gc_area_stack)[sp];
455 : : #endif
456 : : }
457 : 18358 : }
458 : :
459 : 16023 : static void gc_deal_with_stack_overflow(void) {
460 [ + + ]: 16026 : while (MP_STATE_MEM(gc_stack_overflow)) {
461 : 3 : MP_STATE_MEM(gc_stack_overflow) = 0;
462 : :
463 : : // scan entire memory looking for blocks which have been marked but not their children
464 [ + + ]: 15 : for (mp_state_mem_area_t *area = &MP_STATE_MEM(area); area != NULL; area = NEXT_AREA(area)) {
465 [ + + ]: 194280 : for (size_t block = 0; block < area->gc_alloc_table_byte_len * BLOCKS_PER_ATB; block++) {
466 : 194268 : MICROPY_GC_HOOK_LOOP(block);
467 : : // trace (again) if mark bit set
468 [ + + ]: 194268 : if (ATB_GET_KIND(area, block) == AT_MARK) {
469 : : #if MICROPY_GC_SPLIT_HEAP
470 : 1470 : gc_mark_subtree(area, block);
471 : : #else
472 : : gc_mark_subtree(block);
473 : : #endif
474 : : }
475 : : }
476 : : }
477 : : }
478 : 16023 : }
479 : :
480 : 16023 : static void gc_sweep(void) {
481 : : #if MICROPY_PY_GC_COLLECT_RETVAL
482 : 16023 : MP_STATE_MEM(gc_collected) = 0;
483 : : #endif
484 : : // free unmarked heads and their tails
485 : 16023 : int free_tail = 0;
486 : : #if MICROPY_GC_SPLIT_HEAP_AUTO
487 : : mp_state_mem_area_t *prev_area = NULL;
488 : : #endif
489 [ + + ]: 43251 : for (mp_state_mem_area_t *area = &MP_STATE_MEM(area); area != NULL; area = NEXT_AREA(area)) {
490 : 27228 : size_t end_block = area->gc_alloc_table_byte_len * BLOCKS_PER_ATB;
491 [ + + ]: 27228 : if (area->gc_last_used_block < end_block) {
492 : 27227 : end_block = area->gc_last_used_block + 1;
493 : : }
494 : :
495 : 27228 : size_t last_used_block = 0;
496 : :
497 [ + + ]: 8303812 : for (size_t block = 0; block < end_block; block++) {
498 : 8276584 : MICROPY_GC_HOOK_LOOP(block);
499 [ + + + + ]: 8276584 : switch (ATB_GET_KIND(area, block)) {
500 : 2706324 : case AT_HEAD:
501 : : #if MICROPY_ENABLE_FINALISER
502 [ + + ]: 2706324 : if (FTB_GET(area, block)) {
503 : 4262 : mp_obj_base_t *obj = (mp_obj_base_t *)PTR_FROM_BLOCK(area, block);
504 [ + - ]: 4262 : if (obj->type != NULL) {
505 : : // if the object has a type then see if it has a __del__ method
506 : 4262 : mp_obj_t dest[2];
507 : 4262 : mp_load_method_maybe(MP_OBJ_FROM_PTR(obj), MP_QSTR___del__, dest);
508 [ + - ]: 4262 : if (dest[0] != MP_OBJ_NULL) {
509 : : // load_method returned a method, execute it in a protected environment
510 : : #if MICROPY_ENABLE_SCHEDULER
511 : 4262 : mp_sched_lock();
512 : : #endif
513 : 4262 : mp_call_function_1_protected(dest[0], dest[1]);
514 : : #if MICROPY_ENABLE_SCHEDULER
515 : 4262 : mp_sched_unlock();
516 : : #endif
517 : : }
518 : : }
519 : : // clear finaliser flag
520 : 4262 : FTB_CLEAR(area, block);
521 : : }
522 : : #endif
523 : 2706324 : free_tail = 1;
524 : 2706324 : DEBUG_printf("gc_sweep(%p)\n", (void *)PTR_FROM_BLOCK(area, block));
525 : : #if MICROPY_PY_GC_COLLECT_RETVAL
526 : 2706324 : MP_STATE_MEM(gc_collected)++;
527 : : #endif
528 : : // fall through to free the head
529 : 3661080 : MP_FALLTHROUGH
530 : :
531 : 954756 : case AT_TAIL:
532 [ + + ]: 3661080 : if (free_tail) {
533 : 3535483 : ATB_ANY_TO_FREE(area, block);
534 : : #if CLEAR_ON_SWEEP
535 : : memset((void *)PTR_FROM_BLOCK(area, block), 0, BYTES_PER_BLOCK);
536 : : #endif
537 : : } else {
538 : : last_used_block = block;
539 : : }
540 : : break;
541 : :
542 : 4188703 : case AT_MARK:
543 : 4188703 : ATB_MARK_TO_HEAD(area, block);
544 : 4188703 : free_tail = 0;
545 : 4188703 : last_used_block = block;
546 : 4188703 : break;
547 : : }
548 : : }
549 : :
550 : 27228 : area->gc_last_used_block = last_used_block;
551 : :
552 : : #if MICROPY_GC_SPLIT_HEAP_AUTO
553 : : // Free any empty area, aside from the first one
554 : : if (last_used_block == 0 && prev_area != NULL) {
555 : : DEBUG_printf("gc_sweep free empty area %p\n", area);
556 : : NEXT_AREA(prev_area) = NEXT_AREA(area);
557 : : MP_PLAT_FREE_HEAP(area);
558 : : area = prev_area;
559 : : }
560 : : prev_area = area;
561 : : #endif
562 : : }
563 : 16023 : }
564 : :
565 : 12719 : void gc_collect_start(void) {
566 : 12719 : GC_ENTER();
567 : 12719 : MP_STATE_THREAD(gc_lock_depth)++;
568 : : #if MICROPY_GC_ALLOC_THRESHOLD
569 : 12719 : MP_STATE_MEM(gc_alloc_amount) = 0;
570 : : #endif
571 : 12719 : MP_STATE_MEM(gc_stack_overflow) = 0;
572 : :
573 : : // Trace root pointers. This relies on the root pointers being organised
574 : : // correctly in the mp_state_ctx structure. We scan nlr_top, dict_locals,
575 : : // dict_globals, then the root pointer section of mp_state_vm.
576 : 12719 : void **ptrs = (void **)(void *)&mp_state_ctx;
577 : 12719 : size_t root_start = offsetof(mp_state_ctx_t, thread.dict_locals);
578 : 12719 : size_t root_end = offsetof(mp_state_ctx_t, vm.qstr_last_chunk);
579 : 12719 : gc_collect_root(ptrs + root_start / sizeof(void *), (root_end - root_start) / sizeof(void *));
580 : :
581 : : #if MICROPY_ENABLE_PYSTACK
582 : : // Trace root pointers from the Python stack.
583 : : ptrs = (void **)(void *)MP_STATE_THREAD(pystack_start);
584 : : gc_collect_root(ptrs, (MP_STATE_THREAD(pystack_cur) - MP_STATE_THREAD(pystack_start)) / sizeof(void *));
585 : : #endif
586 : 12719 : }
587 : :
588 : : // Address sanitizer needs to know that the access to ptrs[i] must always be
589 : : // considered OK, even if it's a load from an address that would normally be
590 : : // prohibited (due to being undefined, in a red zone, etc).
591 : : #if defined(__GNUC__) && (__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 8))
592 : : __attribute__((no_sanitize_address))
593 : : #endif
594 : 11399734 : static void *gc_get_ptr(void **ptrs, int i) {
595 : : #if MICROPY_DEBUG_VALGRIND
596 : : if (!VALGRIND_CHECK_MEM_IS_ADDRESSABLE(&ptrs[i], sizeof(*ptrs))) {
597 : : return NULL;
598 : : }
599 : : #endif
600 : 11399734 : return ptrs[i];
601 : : }
602 : :
603 : 45211 : void gc_collect_root(void **ptrs, size_t len) {
604 : : #if !MICROPY_GC_SPLIT_HEAP
605 : : mp_state_mem_area_t *area = &MP_STATE_MEM(area);
606 : : #endif
607 [ + + ]: 11444945 : for (size_t i = 0; i < len; i++) {
608 : 11399734 : MICROPY_GC_HOOK_LOOP(i);
609 : 11399734 : void *ptr = gc_get_ptr(ptrs, i);
610 : : #if MICROPY_GC_SPLIT_HEAP
611 [ + + ]: 11399734 : mp_state_mem_area_t *area = gc_get_ptr_area(ptr);
612 [ + + ]: 6173136 : if (!area) {
613 : 11375299 : continue;
614 : : }
615 : : #else
616 : : if (!VERIFY_PTR(ptr)) {
617 : : continue;
618 : : }
619 : : #endif
620 : 24435 : size_t block = BLOCK_FROM_PTR(area, ptr);
621 [ + + ]: 24435 : if (ATB_GET_KIND(area, block) == AT_HEAD) {
622 : : // An unmarked head: mark it, and mark all its children
623 : 16888 : ATB_HEAD_TO_MARK(area, block);
624 : : #if MICROPY_GC_SPLIT_HEAP
625 : 16888 : gc_mark_subtree(area, block);
626 : : #else
627 : : gc_mark_subtree(block);
628 : : #endif
629 : : }
630 : : }
631 : 45211 : }
632 : :
633 : 16023 : void gc_collect_end(void) {
634 : 16023 : gc_deal_with_stack_overflow();
635 : 16023 : gc_sweep();
636 : : #if MICROPY_GC_SPLIT_HEAP
637 : 16023 : MP_STATE_MEM(gc_last_free_area) = &MP_STATE_MEM(area);
638 : : #endif
639 [ + + ]: 43251 : for (mp_state_mem_area_t *area = &MP_STATE_MEM(area); area != NULL; area = NEXT_AREA(area)) {
640 : 27228 : area->gc_last_free_atb_index = 0;
641 : : }
642 : 16023 : MP_STATE_THREAD(gc_lock_depth)--;
643 : 16023 : GC_EXIT();
644 : 16023 : }
645 : :
646 : 3304 : void gc_sweep_all(void) {
647 : 3304 : GC_ENTER();
648 : 3304 : MP_STATE_THREAD(gc_lock_depth)++;
649 : 3304 : MP_STATE_MEM(gc_stack_overflow) = 0;
650 : 3304 : gc_collect_end();
651 : 3304 : }
652 : :
653 : 26 : void gc_info(gc_info_t *info) {
654 : 26 : GC_ENTER();
655 : 26 : info->total = 0;
656 : 26 : info->used = 0;
657 : 26 : info->free = 0;
658 : 26 : info->max_free = 0;
659 : 26 : info->num_1block = 0;
660 : 26 : info->num_2block = 0;
661 : 26 : info->max_block = 0;
662 [ + + ]: 130 : for (mp_state_mem_area_t *area = &MP_STATE_MEM(area); area != NULL; area = NEXT_AREA(area)) {
663 : 104 : bool finish = false;
664 : 104 : info->total += area->gc_pool_end - area->gc_pool_start;
665 [ + + ]: 1683760 : for (size_t block = 0, len = 0, len_free = 0; !finish;) {
666 : 1683656 : MICROPY_GC_HOOK_LOOP(block);
667 : 1683656 : size_t kind = ATB_GET_KIND(area, block);
668 [ + + + - ]: 1683656 : switch (kind) {
669 : 1682304 : case AT_FREE:
670 : 1682304 : info->free += 1;
671 : 1682304 : len_free += 1;
672 : 1682304 : len = 0;
673 : 1682304 : break;
674 : :
675 : 628 : case AT_HEAD:
676 : 628 : info->used += 1;
677 : 628 : len = 1;
678 : 628 : break;
679 : :
680 : 724 : case AT_TAIL:
681 : 724 : info->used += 1;
682 : 724 : len += 1;
683 : 724 : break;
684 : :
685 : : case AT_MARK:
686 : : // shouldn't happen
687 : : break;
688 : : }
689 : :
690 : 1683656 : block++;
691 : 1683656 : finish = (block == area->gc_alloc_table_byte_len * BLOCKS_PER_ATB);
692 : : // Get next block type if possible
693 [ + + ]: 1683656 : if (!finish) {
694 : 1683552 : kind = ATB_GET_KIND(area, block);
695 : : }
696 : :
697 [ + + + + ]: 1683656 : if (finish || kind == AT_FREE || kind == AT_HEAD) {
698 [ + + ]: 1682932 : if (len == 1) {
699 : 402 : info->num_1block += 1;
700 [ + + ]: 1682530 : } else if (len == 2) {
701 : 94 : info->num_2block += 1;
702 : : }
703 [ + + ]: 1682932 : if (len > info->max_block) {
704 : 82 : info->max_block = len;
705 : : }
706 [ + + ]: 1682932 : if (finish || kind == AT_HEAD) {
707 [ + + ]: 706 : if (len_free > info->max_free) {
708 : 124 : info->max_free = len_free;
709 : : }
710 : : len_free = 0;
711 : : }
712 : : }
713 : : }
714 : : }
715 : :
716 : 26 : info->used *= BYTES_PER_BLOCK;
717 : 26 : info->free *= BYTES_PER_BLOCK;
718 : :
719 : : #if MICROPY_GC_SPLIT_HEAP_AUTO
720 : : info->max_new_split = gc_get_max_new_split();
721 : : #endif
722 : :
723 : 26 : GC_EXIT();
724 : 26 : }
725 : :
726 : 3761203 : void *gc_alloc(size_t n_bytes, unsigned int alloc_flags) {
727 : 3761203 : bool has_finaliser = alloc_flags & GC_ALLOC_FLAG_HAS_FINALISER;
728 : 3761203 : size_t n_blocks = ((n_bytes + BYTES_PER_BLOCK - 1) & (~(BYTES_PER_BLOCK - 1))) / BYTES_PER_BLOCK;
729 : 3761203 : DEBUG_printf("gc_alloc(" UINT_FMT " bytes -> " UINT_FMT " blocks)\n", n_bytes, n_blocks);
730 : :
731 : : // check for 0 allocation
732 [ + + ]: 3761203 : if (n_blocks == 0) {
733 : : return NULL;
734 : : }
735 : :
736 : : // check if GC is locked
737 [ + + ]: 3756531 : if (MP_STATE_THREAD(gc_lock_depth) > 0) {
738 : : return NULL;
739 : : }
740 : :
741 : 3755978 : GC_ENTER();
742 : :
743 : 3756550 : mp_state_mem_area_t *area;
744 : 3756550 : size_t i;
745 : 3756550 : size_t end_block;
746 : 3756550 : size_t start_block;
747 : 3756550 : size_t n_free;
748 : 3756550 : int collected = !MP_STATE_MEM(gc_auto_collect_enabled);
749 : : #if MICROPY_GC_SPLIT_HEAP_AUTO
750 : : bool added = false;
751 : : #endif
752 : :
753 : : #if MICROPY_GC_ALLOC_THRESHOLD
754 [ + + + + ]: 3756550 : if (!collected && MP_STATE_MEM(gc_alloc_amount) >= MP_STATE_MEM(gc_alloc_threshold)) {
755 : 24 : GC_EXIT();
756 : 24 : gc_collect();
757 : 24 : collected = 1;
758 : 24 : GC_ENTER();
759 : : }
760 : : #endif
761 : :
762 : 3773092 : for (;;) {
763 : :
764 : : #if MICROPY_GC_SPLIT_HEAP
765 : 3764821 : area = MP_STATE_MEM(gc_last_free_area);
766 : : #else
767 : : area = &MP_STATE_MEM(area);
768 : : #endif
769 : :
770 : : // look for a run of n_blocks available blocks
771 [ + + ]: 3790709 : for (; area != NULL; area = NEXT_AREA(area), i = 0) {
772 : 3778297 : n_free = 0;
773 [ + + ]: 158073628 : for (i = area->gc_last_free_atb_index; i < area->gc_alloc_table_byte_len; i++) {
774 : 158047740 : MICROPY_GC_HOOK_LOOP(i);
775 : 158047740 : byte a = area->gc_alloc_table_start[i];
776 : : // *FORMAT-OFF*
777 [ + + + + ]: 158047740 : if (ATB_0_IS_FREE(a)) { if (++n_free >= n_blocks) { i = i * BLOCKS_PER_ATB + 0; goto found; } } else { n_free = 0; }
778 [ + + + + ]: 157113541 : if (ATB_1_IS_FREE(a)) { if (++n_free >= n_blocks) { i = i * BLOCKS_PER_ATB + 1; goto found; } } else { n_free = 0; }
779 [ + + + + ]: 156162475 : if (ATB_2_IS_FREE(a)) { if (++n_free >= n_blocks) { i = i * BLOCKS_PER_ATB + 2; goto found; } } else { n_free = 0; }
780 [ + + + + ]: 155233917 : if (ATB_3_IS_FREE(a)) { if (++n_free >= n_blocks) { i = i * BLOCKS_PER_ATB + 3; goto found; } } else { n_free = 0; }
781 : : // *FORMAT-ON*
782 : : }
783 : :
784 : : // No free blocks found on this heap. Mark this heap as
785 : : // filled, so we won't try to find free space here again until
786 : : // space is freed.
787 : : #if MICROPY_GC_SPLIT_HEAP
788 [ + + ]: 25888 : if (n_blocks == 1) {
789 : 13158 : area->gc_last_free_atb_index = (i + 1) / BLOCKS_PER_ATB; // or (size_t)-1
790 : : }
791 : : #endif
792 : : }
793 : :
794 : 12412 : GC_EXIT();
795 : : // nothing found!
796 [ + + ]: 12412 : if (collected) {
797 : : #if MICROPY_GC_SPLIT_HEAP_AUTO
798 : : if (!added && gc_try_add_heap(n_bytes)) {
799 : : added = true;
800 : : continue;
801 : : }
802 : : #endif
803 : : return NULL;
804 : : }
805 : 8271 : DEBUG_printf("gc_alloc(" UINT_FMT "): no free mem, triggering GC\n", n_bytes);
806 : 8271 : gc_collect();
807 : 8271 : collected = 1;
808 : 8271 : GC_ENTER();
809 : : }
810 : :
811 : : // found, ending at block i inclusive
812 : 3752409 : found:
813 : : // get starting and end blocks, both inclusive
814 : 3752409 : end_block = i;
815 : 3752409 : start_block = i - n_free + 1;
816 : :
817 : : // Set last free ATB index to block after last block we found, for start of
818 : : // next scan. To reduce fragmentation, we only do this if we were looking
819 : : // for a single free block, which guarantees that there are no free blocks
820 : : // before this one. Also, whenever we free or shink a block we must check
821 : : // if this index needs adjusting (see gc_realloc and gc_free).
822 [ + + ]: 3752409 : if (n_free == 1) {
823 : : #if MICROPY_GC_SPLIT_HEAP
824 : 3092140 : MP_STATE_MEM(gc_last_free_area) = area;
825 : : #endif
826 : 3092140 : area->gc_last_free_atb_index = (i + 1) / BLOCKS_PER_ATB;
827 : : }
828 : :
829 : 3752409 : area->gc_last_used_block = MAX(area->gc_last_used_block, end_block);
830 : :
831 : : // mark first block as used head
832 : 3752409 : ATB_FREE_TO_HEAD(area, start_block);
833 : :
834 : : // mark rest of blocks as used tail
835 : : // TODO for a run of many blocks can make this more efficient
836 [ + + ]: 6426921 : for (size_t bl = start_block + 1; bl <= end_block; bl++) {
837 : 2674512 : ATB_FREE_TO_TAIL(area, bl);
838 : : }
839 : :
840 : : // get pointer to first block
841 : : // we must create this pointer before unlocking the GC so a collection can find it
842 : 3752409 : void *ret_ptr = (void *)(area->gc_pool_start + start_block * BYTES_PER_BLOCK);
843 : 3752409 : DEBUG_printf("gc_alloc(%p)\n", ret_ptr);
844 : :
845 : : #if MICROPY_GC_ALLOC_THRESHOLD
846 : 3752409 : MP_STATE_MEM(gc_alloc_amount) += n_blocks;
847 : : #endif
848 : :
849 : 3752409 : GC_EXIT();
850 : :
851 : : #if MICROPY_GC_CONSERVATIVE_CLEAR
852 : : // be conservative and zero out all the newly allocated blocks
853 : 3752317 : memset((byte *)ret_ptr, 0, (end_block - start_block + 1) * BYTES_PER_BLOCK);
854 : : #else
855 : : // zero out the additional bytes of the newly allocated blocks
856 : : // This is needed because the blocks may have previously held pointers
857 : : // to the heap and will not be set to something else if the caller
858 : : // doesn't actually use the entire block. As such they will continue
859 : : // to point to the heap and may prevent other blocks from being reclaimed.
860 : : memset((byte *)ret_ptr + n_bytes, 0, (end_block - start_block + 1) * BYTES_PER_BLOCK - n_bytes);
861 : : #endif
862 : :
863 : : #if MICROPY_ENABLE_FINALISER
864 [ + + ]: 3752317 : if (has_finaliser) {
865 : : // clear type pointer in case it is never set
866 : 8364 : ((mp_obj_base_t *)ret_ptr)->type = NULL;
867 : : // set mp_obj flag only if it has a finaliser
868 : 8364 : GC_ENTER();
869 : 8364 : FTB_SET(area, start_block);
870 : 8364 : GC_EXIT();
871 : : }
872 : : #else
873 : : (void)has_finaliser;
874 : : #endif
875 : :
876 : : #if EXTENSIVE_HEAP_PROFILING
877 : : gc_dump_alloc_table(&mp_plat_print);
878 : : #endif
879 : :
880 : : return ret_ptr;
881 : : }
882 : :
883 : : /*
884 : : void *gc_alloc(mp_uint_t n_bytes) {
885 : : return _gc_alloc(n_bytes, false);
886 : : }
887 : :
888 : : void *gc_alloc_with_finaliser(mp_uint_t n_bytes) {
889 : : return _gc_alloc(n_bytes, true);
890 : : }
891 : : */
892 : :
893 : : // force the freeing of a piece of memory
894 : : // TODO: freeing here does not call finaliser
895 : 549223 : void gc_free(void *ptr) {
896 [ + # ]: 549223 : if (MP_STATE_THREAD(gc_lock_depth) > 0) {
897 : : // Cannot free while the GC is locked. However free is an optimisation
898 : : // to reclaim the memory immediately, this means it will now be left
899 : : // until the next collection.
900 : : return;
901 : : }
902 : :
903 : 549203 : GC_ENTER();
904 : :
905 : 549363 : DEBUG_printf("gc_free(%p)\n", ptr);
906 : :
907 [ + + ]: 549363 : if (ptr == NULL) {
908 : : // free(NULL) is a no-op
909 : 11284 : GC_EXIT();
910 : 11284 : return;
911 : : }
912 : :
913 : : // get the GC block number corresponding to this pointer
914 : 538079 : mp_state_mem_area_t *area;
915 : : #if MICROPY_GC_SPLIT_HEAP
916 [ + - ]: 538079 : area = gc_get_ptr_area(ptr);
917 [ - + ]: 538079 : assert(area);
918 : : #else
919 : : assert(VERIFY_PTR(ptr));
920 : : area = &MP_STATE_MEM(area);
921 : : #endif
922 : :
923 : 538079 : size_t block = BLOCK_FROM_PTR(area, ptr);
924 [ - + ]: 538079 : assert(ATB_GET_KIND(area, block) == AT_HEAD);
925 : :
926 : : #if MICROPY_ENABLE_FINALISER
927 : 538079 : FTB_CLEAR(area, block);
928 : : #endif
929 : :
930 : : #if MICROPY_GC_SPLIT_HEAP
931 [ + + ]: 538079 : if (MP_STATE_MEM(gc_last_free_area) != area) {
932 : : // We freed something but it isn't the current area. Reset the
933 : : // last free area to the start for a rescan. Note that this won't
934 : : // give much of a performance hit, since areas that are completely
935 : : // filled will likely be skipped (the gc_last_free_atb_index
936 : : // points to the last block).
937 : : // The reason why this is necessary is because it is not possible
938 : : // to see which area came first (like it is possible to adjust
939 : : // gc_last_free_atb_index based on whether the freed block is
940 : : // before the last free block).
941 : 618 : MP_STATE_MEM(gc_last_free_area) = &MP_STATE_MEM(area);
942 : : }
943 : : #endif
944 : :
945 : : // set the last_free pointer to this block if it's earlier in the heap
946 [ + + ]: 538079 : if (block / BLOCKS_PER_ATB < area->gc_last_free_atb_index) {
947 : 91166 : area->gc_last_free_atb_index = block / BLOCKS_PER_ATB;
948 : : }
949 : :
950 : : // free head and all of its tail blocks
951 : 2595682 : do {
952 : 2595682 : ATB_ANY_TO_FREE(area, block);
953 : 2595682 : block += 1;
954 [ + + ]: 2595682 : } while (ATB_GET_KIND(area, block) == AT_TAIL);
955 : :
956 : 538079 : GC_EXIT();
957 : :
958 : : #if EXTENSIVE_HEAP_PROFILING
959 : : gc_dump_alloc_table(&mp_plat_print);
960 : : #endif
961 : : }
962 : :
963 : 26 : size_t gc_nbytes(const void *ptr) {
964 : 26 : GC_ENTER();
965 : :
966 : 26 : mp_state_mem_area_t *area;
967 : : #if MICROPY_GC_SPLIT_HEAP
968 [ + - ]: 26 : area = gc_get_ptr_area(ptr);
969 : : #else
970 : : if (VERIFY_PTR(ptr)) {
971 : : area = &MP_STATE_MEM(area);
972 : : } else {
973 : : area = NULL;
974 : : }
975 : : #endif
976 : :
977 [ + + ]: 26 : if (area) {
978 : 24 : size_t block = BLOCK_FROM_PTR(area, ptr);
979 [ + - ]: 24 : if (ATB_GET_KIND(area, block) == AT_HEAD) {
980 : : // work out number of consecutive blocks in the chain starting with this on
981 : : size_t n_blocks = 0;
982 : 152 : do {
983 : 152 : n_blocks += 1;
984 [ + + ]: 152 : } while (ATB_GET_KIND(area, block + n_blocks) == AT_TAIL);
985 : 24 : GC_EXIT();
986 : 24 : return n_blocks * BYTES_PER_BLOCK;
987 : : }
988 : : }
989 : :
990 : : // invalid pointer
991 : 2 : GC_EXIT();
992 : 2 : return 0;
993 : : }
994 : :
995 : : #if 0
996 : : // old, simple realloc that didn't expand memory in place
997 : : void *gc_realloc(void *ptr, mp_uint_t n_bytes) {
998 : : mp_uint_t n_existing = gc_nbytes(ptr);
999 : : if (n_bytes <= n_existing) {
1000 : : return ptr;
1001 : : } else {
1002 : : bool has_finaliser;
1003 : : if (ptr == NULL) {
1004 : : has_finaliser = false;
1005 : : } else {
1006 : : #if MICROPY_ENABLE_FINALISER
1007 : : has_finaliser = FTB_GET(BLOCK_FROM_PTR((mp_uint_t)ptr));
1008 : : #else
1009 : : has_finaliser = false;
1010 : : #endif
1011 : : }
1012 : : void *ptr2 = gc_alloc(n_bytes, has_finaliser);
1013 : : if (ptr2 == NULL) {
1014 : : return ptr2;
1015 : : }
1016 : : memcpy(ptr2, ptr, n_existing);
1017 : : gc_free(ptr);
1018 : : return ptr2;
1019 : : }
1020 : : }
1021 : :
1022 : : #else // Alternative gc_realloc impl
1023 : :
1024 : 525137 : void *gc_realloc(void *ptr_in, size_t n_bytes, bool allow_move) {
1025 : : // check for pure allocation
1026 [ + + ]: 525137 : if (ptr_in == NULL) {
1027 : 41394 : return gc_alloc(n_bytes, false);
1028 : : }
1029 : :
1030 : : // check for pure free
1031 [ + + ]: 483743 : if (n_bytes == 0) {
1032 : 2 : gc_free(ptr_in);
1033 : 2 : return NULL;
1034 : : }
1035 : :
1036 [ + + ]: 483741 : if (MP_STATE_THREAD(gc_lock_depth) > 0) {
1037 : : return NULL;
1038 : : }
1039 : :
1040 : 483715 : void *ptr = ptr_in;
1041 : :
1042 : 483715 : GC_ENTER();
1043 : :
1044 : : // get the GC block number corresponding to this pointer
1045 : 483715 : mp_state_mem_area_t *area;
1046 : : #if MICROPY_GC_SPLIT_HEAP
1047 [ + - ]: 483715 : area = gc_get_ptr_area(ptr);
1048 [ - + ]: 483715 : assert(area);
1049 : : #else
1050 : : assert(VERIFY_PTR(ptr));
1051 : : area = &MP_STATE_MEM(area);
1052 : : #endif
1053 : 483715 : size_t block = BLOCK_FROM_PTR(area, ptr);
1054 [ - + ]: 483715 : assert(ATB_GET_KIND(area, block) == AT_HEAD);
1055 : :
1056 : : // compute number of new blocks that are requested
1057 : 483715 : size_t new_blocks = (n_bytes + BYTES_PER_BLOCK - 1) / BYTES_PER_BLOCK;
1058 : :
1059 : : // Get the total number of consecutive blocks that are already allocated to
1060 : : // this chunk of memory, and then count the number of free blocks following
1061 : : // it. Stop if we reach the end of the heap, or if we find enough extra
1062 : : // free blocks to satisfy the realloc. Note that we need to compute the
1063 : : // total size of the existing memory chunk so we can correctly and
1064 : : // efficiently shrink it (see below for shrinking code).
1065 : 483715 : size_t n_free = 0;
1066 : 483715 : size_t n_blocks = 1; // counting HEAD block
1067 : 483715 : size_t max_block = area->gc_alloc_table_byte_len * BLOCKS_PER_ATB;
1068 [ + + ]: 9265107 : for (size_t bl = block + n_blocks; bl < max_block; bl++) {
1069 : 9265079 : byte block_type = ATB_GET_KIND(area, bl);
1070 [ + + ]: 9265079 : if (block_type == AT_TAIL) {
1071 : 8648325 : n_blocks++;
1072 : 8648325 : continue;
1073 : : }
1074 [ + + ]: 616754 : if (block_type == AT_FREE) {
1075 : 546014 : n_free++;
1076 [ + + ]: 546014 : if (n_blocks + n_free >= new_blocks) {
1077 : : // stop as soon as we find enough blocks for n_bytes
1078 : : break;
1079 : : }
1080 : 133067 : continue;
1081 : : }
1082 : : break;
1083 : : }
1084 : :
1085 : : // return original ptr if it already has the requested number of blocks
1086 [ + + ]: 483715 : if (new_blocks == n_blocks) {
1087 : 266004 : GC_EXIT();
1088 : 266004 : return ptr_in;
1089 : : }
1090 : :
1091 : : // check if we can shrink the allocated area
1092 [ + + ]: 217711 : if (new_blocks < n_blocks) {
1093 : : // free unneeded tail blocks
1094 [ + + ]: 50685 : for (size_t bl = block + new_blocks, count = n_blocks - new_blocks; count > 0; bl++, count--) {
1095 : 26389 : ATB_ANY_TO_FREE(area, bl);
1096 : : }
1097 : :
1098 : : #if MICROPY_GC_SPLIT_HEAP
1099 [ + + ]: 24296 : if (MP_STATE_MEM(gc_last_free_area) != area) {
1100 : : // See comment in gc_free.
1101 : 15 : MP_STATE_MEM(gc_last_free_area) = &MP_STATE_MEM(area);
1102 : : }
1103 : : #endif
1104 : :
1105 : : // set the last_free pointer to end of this block if it's earlier in the heap
1106 [ + + ]: 24296 : if ((block + new_blocks) / BLOCKS_PER_ATB < area->gc_last_free_atb_index) {
1107 : 886 : area->gc_last_free_atb_index = (block + new_blocks) / BLOCKS_PER_ATB;
1108 : : }
1109 : :
1110 : 24296 : GC_EXIT();
1111 : :
1112 : : #if EXTENSIVE_HEAP_PROFILING
1113 : : gc_dump_alloc_table(&mp_plat_print);
1114 : : #endif
1115 : :
1116 : 24296 : return ptr_in;
1117 : : }
1118 : :
1119 : : // check if we can expand in place
1120 [ + + ]: 193415 : if (new_blocks <= n_blocks + n_free) {
1121 : : // mark few more blocks as used tail
1122 : 160986 : size_t end_block = block + new_blocks;
1123 [ + + ]: 399701 : for (size_t bl = block + n_blocks; bl < end_block; bl++) {
1124 [ - + ]: 238715 : assert(ATB_GET_KIND(area, bl) == AT_FREE);
1125 : 238715 : ATB_FREE_TO_TAIL(area, bl);
1126 : : }
1127 : :
1128 : 160986 : area->gc_last_used_block = MAX(area->gc_last_used_block, end_block);
1129 : :
1130 : 160986 : GC_EXIT();
1131 : :
1132 : : #if MICROPY_GC_CONSERVATIVE_CLEAR
1133 : : // be conservative and zero out all the newly allocated blocks
1134 : 160986 : memset((byte *)ptr_in + n_blocks * BYTES_PER_BLOCK, 0, (new_blocks - n_blocks) * BYTES_PER_BLOCK);
1135 : : #else
1136 : : // zero out the additional bytes of the newly allocated blocks (see comment above in gc_alloc)
1137 : : memset((byte *)ptr_in + n_bytes, 0, new_blocks * BYTES_PER_BLOCK - n_bytes);
1138 : : #endif
1139 : :
1140 : : #if EXTENSIVE_HEAP_PROFILING
1141 : : gc_dump_alloc_table(&mp_plat_print);
1142 : : #endif
1143 : :
1144 : 160986 : return ptr_in;
1145 : : }
1146 : :
1147 : : #if MICROPY_ENABLE_FINALISER
1148 : 32429 : bool ftb_state = FTB_GET(area, block);
1149 : : #else
1150 : : bool ftb_state = false;
1151 : : #endif
1152 : :
1153 : 32429 : GC_EXIT();
1154 : :
1155 [ + + ]: 32429 : if (!allow_move) {
1156 : : // not allowed to move memory block so return failure
1157 : : return NULL;
1158 : : }
1159 : :
1160 : : // can't resize inplace; try to find a new contiguous chain
1161 : 20340 : void *ptr_out = gc_alloc(n_bytes, ftb_state);
1162 : :
1163 : : // check that the alloc succeeded
1164 [ + + ]: 20340 : if (ptr_out == NULL) {
1165 : : return NULL;
1166 : : }
1167 : :
1168 : 20332 : DEBUG_printf("gc_realloc(%p -> %p)\n", ptr_in, ptr_out);
1169 : 20332 : memcpy(ptr_out, ptr_in, n_blocks * BYTES_PER_BLOCK);
1170 : 20332 : gc_free(ptr_in);
1171 : 20332 : return ptr_out;
1172 : : }
1173 : : #endif // Alternative gc_realloc impl
1174 : :
1175 : 18 : void gc_dump_info(const mp_print_t *print) {
1176 : 18 : gc_info_t info;
1177 : 18 : gc_info(&info);
1178 : 18 : mp_printf(print, "GC: total: %u, used: %u, free: %u",
1179 : 18 : (uint)info.total, (uint)info.used, (uint)info.free);
1180 : : #if MICROPY_GC_SPLIT_HEAP_AUTO
1181 : : mp_printf(print, ", max new split: %u", (uint)info.max_new_split);
1182 : : #endif
1183 : 18 : mp_printf(print, "\n No. of 1-blocks: %u, 2-blocks: %u, max blk sz: %u, max free sz: %u\n",
1184 : 18 : (uint)info.num_1block, (uint)info.num_2block, (uint)info.max_block, (uint)info.max_free);
1185 : 18 : }
1186 : :
1187 : 4 : void gc_dump_alloc_table(const mp_print_t *print) {
1188 : 4 : GC_ENTER();
1189 : 4 : static const size_t DUMP_BYTES_PER_LINE = 64;
1190 [ + + ]: 20 : for (mp_state_mem_area_t *area = &MP_STATE_MEM(area); area != NULL; area = NEXT_AREA(area)) {
1191 : : #if !EXTENSIVE_HEAP_PROFILING
1192 : : // When comparing heap output we don't want to print the starting
1193 : : // pointer of the heap because it changes from run to run.
1194 : 16 : mp_printf(print, "GC memory layout; from %p:", area->gc_pool_start);
1195 : : #endif
1196 [ + + ]: 1248 : for (size_t bl = 0; bl < area->gc_alloc_table_byte_len * BLOCKS_PER_ATB; bl++) {
1197 [ + + ]: 1236 : if (bl % DUMP_BYTES_PER_LINE == 0) {
1198 : : // a new line of blocks
1199 : : {
1200 : : // check if this line contains only free blocks
1201 : : size_t bl2 = bl;
1202 [ + + + + ]: 258608 : while (bl2 < area->gc_alloc_table_byte_len * BLOCKS_PER_ATB && ATB_GET_KIND(area, bl2) == AT_FREE) {
1203 : 258584 : bl2++;
1204 : : }
1205 [ + + ]: 24 : if (bl2 - bl >= 2 * DUMP_BYTES_PER_LINE) {
1206 : : // there are at least 2 lines containing only free blocks, so abbreviate their printing
1207 : 16 : mp_printf(print, "\n (%u lines all free)", (uint)(bl2 - bl) / DUMP_BYTES_PER_LINE);
1208 : 16 : bl = bl2 & (~(DUMP_BYTES_PER_LINE - 1));
1209 [ + + ]: 16 : if (bl >= area->gc_alloc_table_byte_len * BLOCKS_PER_ATB) {
1210 : : // got to end of heap
1211 : : break;
1212 : : }
1213 : : }
1214 : : }
1215 : : // print header for new line of blocks
1216 : : // (the cast to uint32_t is for 16-bit ports)
1217 : 20 : mp_printf(print, "\n%08x: ", (uint)(bl * BYTES_PER_BLOCK));
1218 : : }
1219 : 1232 : int c = ' ';
1220 [ + + - + ]: 1232 : switch (ATB_GET_KIND(area, bl)) {
1221 : : case AT_FREE:
1222 : : c = '.';
1223 : : break;
1224 : : /* this prints out if the object is reachable from BSS or STACK (for unix only)
1225 : : case AT_HEAD: {
1226 : : c = 'h';
1227 : : void **ptrs = (void**)(void*)&mp_state_ctx;
1228 : : mp_uint_t len = offsetof(mp_state_ctx_t, vm.stack_top) / sizeof(mp_uint_t);
1229 : : for (mp_uint_t i = 0; i < len; i++) {
1230 : : mp_uint_t ptr = (mp_uint_t)ptrs[i];
1231 : : if (gc_get_ptr_area(ptr) && BLOCK_FROM_PTR(ptr) == bl) {
1232 : : c = 'B';
1233 : : break;
1234 : : }
1235 : : }
1236 : : if (c == 'h') {
1237 : : ptrs = (void**)&c;
1238 : : len = ((mp_uint_t)MP_STATE_THREAD(stack_top) - (mp_uint_t)&c) / sizeof(mp_uint_t);
1239 : : for (mp_uint_t i = 0; i < len; i++) {
1240 : : mp_uint_t ptr = (mp_uint_t)ptrs[i];
1241 : : if (gc_get_ptr_area(ptr) && BLOCK_FROM_PTR(ptr) == bl) {
1242 : : c = 'S';
1243 : : break;
1244 : : }
1245 : : }
1246 : : }
1247 : : break;
1248 : : }
1249 : : */
1250 : : /* this prints the uPy object type of the head block */
1251 : 76 : case AT_HEAD: {
1252 : 76 : void **ptr = (void **)(area->gc_pool_start + bl * BYTES_PER_BLOCK);
1253 [ + - ]: 76 : if (*ptr == &mp_type_tuple) {
1254 : : c = 'T';
1255 [ + + ]: 76 : } else if (*ptr == &mp_type_list) {
1256 : : c = 'L';
1257 [ + - ]: 72 : } else if (*ptr == &mp_type_dict) {
1258 : : c = 'D';
1259 [ + - + - ]: 72 : } else if (*ptr == &mp_type_str || *ptr == &mp_type_bytes) {
1260 : : c = 'S';
1261 : : }
1262 : : #if MICROPY_PY_BUILTINS_BYTEARRAY
1263 [ + - ]: 72 : else if (*ptr == &mp_type_bytearray) {
1264 : : c = 'A';
1265 : : }
1266 : : #endif
1267 : : #if MICROPY_PY_ARRAY
1268 [ + - ]: 72 : else if (*ptr == &mp_type_array) {
1269 : : c = 'A';
1270 : : }
1271 : : #endif
1272 : : #if MICROPY_PY_BUILTINS_FLOAT
1273 [ + - ]: 72 : else if (*ptr == &mp_type_float) {
1274 : : c = 'F';
1275 : : }
1276 : : #endif
1277 [ + + ]: 72 : else if (*ptr == &mp_type_fun_bc) {
1278 : : c = 'B';
1279 [ + - ]: 68 : } else if (*ptr == &mp_type_module) {
1280 : : c = 'M';
1281 : : } else {
1282 : 68 : c = 'h';
1283 : : #if 0
1284 : : // This code prints "Q" for qstr-pool data, and "q" for qstr-str
1285 : : // data. It can be useful to see how qstrs are being allocated,
1286 : : // but is disabled by default because it is very slow.
1287 : : for (qstr_pool_t *pool = MP_STATE_VM(last_pool); c == 'h' && pool != NULL; pool = pool->prev) {
1288 : : if ((qstr_pool_t *)ptr == pool) {
1289 : : c = 'Q';
1290 : : break;
1291 : : }
1292 : : for (const byte **q = pool->qstrs, **q_top = pool->qstrs + pool->len; q < q_top; q++) {
1293 : : if ((const byte *)ptr == *q) {
1294 : : c = 'q';
1295 : : break;
1296 : : }
1297 : : }
1298 : : }
1299 : : #endif
1300 : : }
1301 : : break;
1302 : : }
1303 : 92 : case AT_TAIL:
1304 : 92 : c = '=';
1305 : 92 : break;
1306 : 0 : case AT_MARK:
1307 : 0 : c = 'm';
1308 : 0 : break;
1309 : : }
1310 : 1232 : mp_printf(print, "%c", c);
1311 : : }
1312 : 16 : mp_print_str(print, "\n");
1313 : : }
1314 : 4 : GC_EXIT();
1315 : 4 : }
1316 : :
1317 : : #if 0
1318 : : // For testing the GC functions
1319 : : void gc_test(void) {
1320 : : mp_uint_t len = 500;
1321 : : mp_uint_t *heap = malloc(len);
1322 : : gc_init(heap, heap + len / sizeof(mp_uint_t));
1323 : : void *ptrs[100];
1324 : : {
1325 : : mp_uint_t **p = gc_alloc(16, false);
1326 : : p[0] = gc_alloc(64, false);
1327 : : p[1] = gc_alloc(1, false);
1328 : : p[2] = gc_alloc(1, false);
1329 : : p[3] = gc_alloc(1, false);
1330 : : mp_uint_t ***p2 = gc_alloc(16, false);
1331 : : p2[0] = p;
1332 : : p2[1] = p;
1333 : : ptrs[0] = p2;
1334 : : }
1335 : : for (int i = 0; i < 25; i += 2) {
1336 : : mp_uint_t *p = gc_alloc(i, false);
1337 : : printf("p=%p\n", p);
1338 : : if (i & 3) {
1339 : : // ptrs[i] = p;
1340 : : }
1341 : : }
1342 : :
1343 : : printf("Before GC:\n");
1344 : : gc_dump_alloc_table(&mp_plat_print);
1345 : : printf("Starting GC...\n");
1346 : : gc_collect_start();
1347 : : gc_collect_root(ptrs, sizeof(ptrs) / sizeof(void *));
1348 : : gc_collect_end();
1349 : : printf("After GC:\n");
1350 : : gc_dump_alloc_table(&mp_plat_print);
1351 : : }
1352 : : #endif
1353 : :
1354 : : #endif // MICROPY_ENABLE_GC
|
