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 : 17160 : 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 : 17160 : size_t total_byte_len = (byte *)end - (byte *)start;
131 : : #if MICROPY_ENABLE_FINALISER
132 : 17160 : area->gc_alloc_table_byte_len = (total_byte_len - ALLOC_TABLE_GAP_BYTE)
133 : 17160 : * MP_BITS_PER_BYTE
134 : 17160 : / (
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 : 17160 : area->gc_alloc_table_start = (byte *)start;
144 : :
145 : : #if MICROPY_ENABLE_FINALISER
146 : 17160 : size_t gc_finaliser_table_byte_len = (area->gc_alloc_table_byte_len * BLOCKS_PER_ATB + BLOCKS_PER_FTB - 1) / BLOCKS_PER_FTB;
147 : 17160 : area->gc_finaliser_table_start = area->gc_alloc_table_start + area->gc_alloc_table_byte_len + ALLOC_TABLE_GAP_BYTE;
148 : : #endif
149 : :
150 : 17160 : size_t gc_pool_block_len = area->gc_alloc_table_byte_len * BLOCKS_PER_ATB;
151 : 17160 : area->gc_pool_start = (byte *)end - gc_pool_block_len * BYTES_PER_BLOCK;
152 : 17160 : area->gc_pool_end = end;
153 : :
154 : : #if MICROPY_ENABLE_FINALISER
155 [ - + ]: 17160 : 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 : 17160 : 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 : 17160 : area->gc_last_free_atb_index = 0;
167 : 17160 : area->gc_last_used_block = 0;
168 : :
169 : : #if MICROPY_GC_SPLIT_HEAP
170 : 17160 : area->next = NULL;
171 : : #endif
172 : :
173 : 17160 : DEBUG_printf("GC layout:\n");
174 : 17160 : 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 : 17160 : 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 : 17160 : 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 : 17160 : }
188 : :
189 : 7362 : void gc_init(void *start, void *end) {
190 : : // align end pointer on block boundary
191 : 7362 : end = (void *)((uintptr_t)end & (~(BYTES_PER_BLOCK - 1)));
192 : 7362 : DEBUG_printf("Initializing GC heap: %p..%p = " UINT_FMT " bytes\n", start, end, (byte *)end - (byte *)start);
193 : :
194 : 7362 : 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 : 7362 : MP_STATE_MEM(gc_last_free_area) = &MP_STATE_MEM(area);
199 : : #endif
200 : :
201 : : // unlock the GC
202 : 7362 : MP_STATE_THREAD(gc_lock_depth) = 0;
203 : :
204 : : // allow auto collection
205 : 7362 : 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 : 7362 : MP_STATE_MEM(gc_alloc_threshold) = (size_t)-1;
210 : 7362 : MP_STATE_MEM(gc_alloc_amount) = 0;
211 : : #endif
212 : :
213 : : #if MICROPY_PY_THREAD && !MICROPY_PY_THREAD_GIL
214 : 7362 : mp_thread_mutex_init(&MP_STATE_MEM(gc_mutex));
215 : : #endif
216 : 7362 : }
217 : :
218 : : #if MICROPY_GC_SPLIT_HEAP
219 : 9798 : void gc_add(void *start, void *end) {
220 : : // Place the area struct at the start of the area.
221 : 9798 : mp_state_mem_area_t *area = (mp_state_mem_area_t *)start;
222 : 9798 : start = (void *)((uintptr_t)start + sizeof(mp_state_mem_area_t));
223 : :
224 : 9798 : end = (void *)((uintptr_t)end & (~(BYTES_PER_BLOCK - 1)));
225 : 9798 : DEBUG_printf("Adding GC heap: %p..%p = " UINT_FMT " bytes\n", start, end, (byte *)end - (byte *)start);
226 : :
227 : : // Init this area
228 : 9798 : gc_setup_area(area, start, end);
229 : :
230 : : // Find the last registered area in the linked list
231 : 9798 : mp_state_mem_area_t *prev_area = &MP_STATE_MEM(area);
232 [ + + ]: 19596 : while (prev_area->next != NULL) {
233 : : prev_area = prev_area->next;
234 : : }
235 : :
236 : : // Add this area to the linked list
237 : 9798 : prev_area->next = area;
238 : 9798 : }
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 : : size_t total_heap = 0;
286 : : for (mp_state_mem_area_t *area = &MP_STATE_MEM(area);
287 : : area != NULL;
288 : : area = NEXT_AREA(area)) {
289 : : total_heap += area->gc_pool_end - area->gc_alloc_table_start;
290 : : total_heap += ALLOC_TABLE_GAP_BYTE + sizeof(mp_state_mem_area_t);
291 : : }
292 : :
293 : : DEBUG_printf("total_heap " UINT_FMT " bytes\n", total_heap);
294 : :
295 : : size_t to_alloc = MIN(avail, MAX(total_heap, needed));
296 : :
297 : : mp_state_mem_area_t *new_heap = MP_PLAT_ALLOC_HEAP(to_alloc);
298 : :
299 : : DEBUG_printf("MP_PLAT_ALLOC_HEAP " UINT_FMT " = %p\n",
300 : : to_alloc, new_heap);
301 : :
302 : : if (new_heap == NULL) {
303 : : // This should only fail:
304 : : // - In a threaded environment if another thread has
305 : : // allocated while this function ran.
306 : : // - If there is a bug in gc_get_max_new_split().
307 : : return false;
308 : : }
309 : :
310 : : gc_add(new_heap, (void *)new_heap + to_alloc);
311 : :
312 : : return true;
313 : : }
314 : : #endif
315 : :
316 : : #endif
317 : :
318 : 233 : void gc_lock(void) {
319 : : // This does not need to be atomic or have the GC mutex because:
320 : : // - each thread has its own gc_lock_depth so there are no races between threads;
321 : : // - a hard interrupt will only change gc_lock_depth during its execution, and
322 : : // upon return will restore the value of gc_lock_depth.
323 : 233 : MP_STATE_THREAD(gc_lock_depth)++;
324 : 233 : }
325 : :
326 : 233 : void gc_unlock(void) {
327 : : // This does not need to be atomic, See comment above in gc_lock.
328 : 233 : MP_STATE_THREAD(gc_lock_depth)--;
329 : 233 : }
330 : :
331 : 110 : bool gc_is_locked(void) {
332 : 110 : return MP_STATE_THREAD(gc_lock_depth) != 0;
333 : : }
334 : :
335 : : #if MICROPY_GC_SPLIT_HEAP
336 : : // Returns the area to which this pointer belongs, or NULL if it isn't
337 : : // allocated on the GC-managed heap.
338 : 29927752 : STATIC inline mp_state_mem_area_t *gc_get_ptr_area(const void *ptr) {
339 : 29927752 : if (((uintptr_t)(ptr) & (BYTES_PER_BLOCK - 1)) != 0) { // must be aligned on a block
340 : : return NULL;
341 : : }
342 [ + - + + : 59712763 : for (mp_state_mem_area_t *area = &MP_STATE_MEM(area); area != NULL; area = NEXT_AREA(area)) {
+ - + + +
+ ]
343 [ + + + + : 43331573 : if (ptr >= (void *)area->gc_pool_start // must be above start of pool
+ + + + +
+ ]
344 [ - + - + : 7533371 : && ptr < (void *)area->gc_pool_end) { // must be below end of pool
- + + + +
+ ]
345 : : return area;
346 : : }
347 : : }
348 : : return NULL;
349 : : }
350 : : #endif
351 : :
352 : : // ptr should be of type void*
353 : : #define VERIFY_PTR(ptr) ( \
354 : : ((uintptr_t)(ptr) & (BYTES_PER_BLOCK - 1)) == 0 /* must be aligned on a block */ \
355 : : && ptr >= (void *)MP_STATE_MEM(area).gc_pool_start /* must be above start of pool */ \
356 : : && ptr < (void *)MP_STATE_MEM(area).gc_pool_end /* must be below end of pool */ \
357 : : )
358 : :
359 : : #ifndef TRACE_MARK
360 : : #if DEBUG_PRINT
361 : : #define TRACE_MARK(block, ptr) DEBUG_printf("gc_mark(%p)\n", ptr)
362 : : #else
363 : : #define TRACE_MARK(block, ptr)
364 : : #endif
365 : : #endif
366 : :
367 : : // Take the given block as the topmost block on the stack. Check all it's
368 : : // children: mark the unmarked child blocks and put those newly marked
369 : : // blocks on the stack. When all children have been checked, pop off the
370 : : // topmost block on the stack and repeat with that one.
371 : : #if MICROPY_GC_SPLIT_HEAP
372 : 19850 : STATIC void gc_mark_subtree(mp_state_mem_area_t *area, size_t block)
373 : : #else
374 : : STATIC void gc_mark_subtree(size_t block)
375 : : #endif
376 : : {
377 : : // Start with the block passed in the argument.
378 : 19850 : size_t sp = 0;
379 : 8492624 : for (;;) {
380 : : #if !MICROPY_GC_SPLIT_HEAP
381 : : mp_state_mem_area_t *area = &MP_STATE_MEM(area);
382 : : #endif
383 : :
384 : : // work out number of consecutive blocks in the chain starting with this one
385 : 4256237 : size_t n_blocks = 0;
386 : 4384406 : do {
387 : 4384406 : n_blocks += 1;
388 [ + + ]: 4384406 : } while (ATB_GET_KIND(area, block + n_blocks) == AT_TAIL);
389 : :
390 : : // check that the consecutive blocks didn't overflow past the end of the area
391 [ - + ]: 4256237 : assert(area->gc_pool_start + (block + n_blocks) * BYTES_PER_BLOCK <= area->gc_pool_end);
392 : :
393 : : // check this block's children
394 : 4256237 : void **ptrs = (void **)PTR_FROM_BLOCK(area, block);
395 [ + + ]: 21793861 : for (size_t i = n_blocks * BYTES_PER_BLOCK / sizeof(void *); i > 0; i--, ptrs++) {
396 : 17537624 : MICROPY_GC_HOOK_LOOP(i);
397 : 17537624 : void *ptr = *ptrs;
398 : : // If this is a heap pointer that hasn't been marked, mark it and push
399 : : // it's children to the stack.
400 : : #if MICROPY_GC_SPLIT_HEAP
401 [ + + ]: 17537624 : mp_state_mem_area_t *ptr_area = gc_get_ptr_area(ptr);
402 [ + + ]: 14488416 : if (!ptr_area) {
403 : : // Not a heap-allocated pointer (might even be random data).
404 : 13295174 : continue;
405 : : }
406 : : #else
407 : : if (!VERIFY_PTR(ptr)) {
408 : : continue;
409 : : }
410 : : mp_state_mem_area_t *ptr_area = area;
411 : : #endif
412 : 4242450 : size_t ptr_block = BLOCK_FROM_PTR(ptr_area, ptr);
413 [ + + ]: 4242450 : if (ATB_GET_KIND(ptr_area, ptr_block) != AT_HEAD) {
414 : : // This block is already marked.
415 : 5509 : continue;
416 : : }
417 : : // An unmarked head. Mark it, and push it on gc stack.
418 : 4236941 : TRACE_MARK(ptr_block, ptr);
419 : 4236941 : ATB_HEAD_TO_MARK(ptr_area, ptr_block);
420 [ + + ]: 4236941 : if (sp < MICROPY_ALLOC_GC_STACK_SIZE) {
421 : 4236387 : MP_STATE_MEM(gc_block_stack)[sp] = ptr_block;
422 : : #if MICROPY_GC_SPLIT_HEAP
423 : 4236387 : MP_STATE_MEM(gc_area_stack)[sp] = ptr_area;
424 : : #endif
425 : 4236387 : sp += 1;
426 : : } else {
427 : 554 : MP_STATE_MEM(gc_stack_overflow) = 1;
428 : : }
429 : : }
430 : :
431 : : // Are there any blocks on the stack?
432 [ + + ]: 4256237 : if (sp == 0) {
433 : : break; // No, stack is empty, we're done.
434 : : }
435 : :
436 : : // pop the next block off the stack
437 : 4236387 : sp -= 1;
438 : 4236387 : block = MP_STATE_MEM(gc_block_stack)[sp];
439 : : #if MICROPY_GC_SPLIT_HEAP
440 : 4236387 : area = MP_STATE_MEM(gc_area_stack)[sp];
441 : : #endif
442 : : }
443 : 19850 : }
444 : :
445 : 15974 : STATIC void gc_deal_with_stack_overflow(void) {
446 [ + + ]: 15979 : while (MP_STATE_MEM(gc_stack_overflow)) {
447 : 5 : MP_STATE_MEM(gc_stack_overflow) = 0;
448 : :
449 : : // scan entire memory looking for blocks which have been marked but not their children
450 [ + + ]: 25 : for (mp_state_mem_area_t *area = &MP_STATE_MEM(area); area != NULL; area = NEXT_AREA(area)) {
451 [ + + ]: 323800 : for (size_t block = 0; block < area->gc_alloc_table_byte_len * BLOCKS_PER_ATB; block++) {
452 : 323780 : MICROPY_GC_HOOK_LOOP(block);
453 : : // trace (again) if mark bit set
454 [ + + ]: 323780 : if (ATB_GET_KIND(area, block) == AT_MARK) {
455 : : #if MICROPY_GC_SPLIT_HEAP
456 : 2976 : gc_mark_subtree(area, block);
457 : : #else
458 : : gc_mark_subtree(block);
459 : : #endif
460 : : }
461 : : }
462 : : }
463 : : }
464 : 15974 : }
465 : :
466 : 15974 : STATIC void gc_sweep(void) {
467 : : #if MICROPY_PY_GC_COLLECT_RETVAL
468 : 15974 : MP_STATE_MEM(gc_collected) = 0;
469 : : #endif
470 : : // free unmarked heads and their tails
471 : 15974 : int free_tail = 0;
472 : : #if MICROPY_GC_SPLIT_HEAP_AUTO
473 : : mp_state_mem_area_t *prev_area = NULL;
474 : : #endif
475 [ + + ]: 43006 : for (mp_state_mem_area_t *area = &MP_STATE_MEM(area); area != NULL; area = NEXT_AREA(area)) {
476 : 27032 : size_t end_block = area->gc_alloc_table_byte_len * BLOCKS_PER_ATB;
477 [ + + ]: 27032 : if (area->gc_last_used_block < end_block) {
478 : 27031 : end_block = area->gc_last_used_block + 1;
479 : : }
480 : :
481 : 27032 : size_t last_used_block = 0;
482 : :
483 [ + + ]: 8467259 : for (size_t block = 0; block < end_block; block++) {
484 : 8440227 : MICROPY_GC_HOOK_LOOP(block);
485 [ + + + + ]: 8440227 : switch (ATB_GET_KIND(area, block)) {
486 : 2697638 : case AT_HEAD:
487 : : #if MICROPY_ENABLE_FINALISER
488 [ + + ]: 2697638 : if (FTB_GET(area, block)) {
489 : 4186 : mp_obj_base_t *obj = (mp_obj_base_t *)PTR_FROM_BLOCK(area, block);
490 [ + - ]: 4186 : if (obj->type != NULL) {
491 : : // if the object has a type then see if it has a __del__ method
492 : 4186 : mp_obj_t dest[2];
493 : 4186 : mp_load_method_maybe(MP_OBJ_FROM_PTR(obj), MP_QSTR___del__, dest);
494 [ + - ]: 4186 : if (dest[0] != MP_OBJ_NULL) {
495 : : // load_method returned a method, execute it in a protected environment
496 : : #if MICROPY_ENABLE_SCHEDULER
497 : 4186 : mp_sched_lock();
498 : : #endif
499 : 4186 : mp_call_function_1_protected(dest[0], dest[1]);
500 : : #if MICROPY_ENABLE_SCHEDULER
501 : 4186 : mp_sched_unlock();
502 : : #endif
503 : : }
504 : : }
505 : : // clear finaliser flag
506 : 4186 : FTB_CLEAR(area, block);
507 : : }
508 : : #endif
509 : 2697638 : free_tail = 1;
510 : 2697638 : DEBUG_printf("gc_sweep(%p)\n", (void *)PTR_FROM_BLOCK(area, block));
511 : : #if MICROPY_PY_GC_COLLECT_RETVAL
512 : 2697638 : MP_STATE_MEM(gc_collected)++;
513 : : #endif
514 : : // fall through to free the head
515 : 3700604 : MP_FALLTHROUGH
516 : :
517 : 1002966 : case AT_TAIL:
518 [ + + ]: 3700604 : if (free_tail) {
519 : 3573156 : ATB_ANY_TO_FREE(area, block);
520 : : #if CLEAR_ON_SWEEP
521 : : memset((void *)PTR_FROM_BLOCK(area, block), 0, BYTES_PER_BLOCK);
522 : : #endif
523 : : } else {
524 : : last_used_block = block;
525 : : }
526 : : break;
527 : :
528 : 4253815 : case AT_MARK:
529 : 4253815 : ATB_MARK_TO_HEAD(area, block);
530 : 4253815 : free_tail = 0;
531 : 4253815 : last_used_block = block;
532 : 4253815 : break;
533 : : }
534 : : }
535 : :
536 : 27032 : area->gc_last_used_block = last_used_block;
537 : :
538 : : #if MICROPY_GC_SPLIT_HEAP_AUTO
539 : : // Free any empty area, aside from the first one
540 : : if (last_used_block == 0 && prev_area != NULL) {
541 : : DEBUG_printf("gc_sweep free empty area %p\n", area);
542 : : NEXT_AREA(prev_area) = NEXT_AREA(area);
543 : : MP_PLAT_FREE_HEAP(area);
544 : : area = prev_area;
545 : : }
546 : : prev_area = area;
547 : : #endif
548 : : }
549 : 15974 : }
550 : :
551 : 12712 : void gc_collect_start(void) {
552 : 12712 : GC_ENTER();
553 : 12712 : MP_STATE_THREAD(gc_lock_depth)++;
554 : : #if MICROPY_GC_ALLOC_THRESHOLD
555 : 12712 : MP_STATE_MEM(gc_alloc_amount) = 0;
556 : : #endif
557 : 12712 : MP_STATE_MEM(gc_stack_overflow) = 0;
558 : :
559 : : // Trace root pointers. This relies on the root pointers being organised
560 : : // correctly in the mp_state_ctx structure. We scan nlr_top, dict_locals,
561 : : // dict_globals, then the root pointer section of mp_state_vm.
562 : 12712 : void **ptrs = (void **)(void *)&mp_state_ctx;
563 : 12712 : size_t root_start = offsetof(mp_state_ctx_t, thread.dict_locals);
564 : 12712 : size_t root_end = offsetof(mp_state_ctx_t, vm.qstr_last_chunk);
565 : 12712 : gc_collect_root(ptrs + root_start / sizeof(void *), (root_end - root_start) / sizeof(void *));
566 : :
567 : : #if MICROPY_ENABLE_PYSTACK
568 : : // Trace root pointers from the Python stack.
569 : : ptrs = (void **)(void *)MP_STATE_THREAD(pystack_start);
570 : : gc_collect_root(ptrs, (MP_STATE_THREAD(pystack_cur) - MP_STATE_THREAD(pystack_start)) / sizeof(void *));
571 : : #endif
572 : 12712 : }
573 : :
574 : : // Address sanitizer needs to know that the access to ptrs[i] must always be
575 : : // considered OK, even if it's a load from an address that would normally be
576 : : // prohibited (due to being undefined, in a red zone, etc).
577 : : #if defined(__GNUC__) && (__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 8))
578 : : __attribute__((no_sanitize_address))
579 : : #endif
580 : 11377014 : static void *gc_get_ptr(void **ptrs, int i) {
581 : : #if MICROPY_DEBUG_VALGRIND
582 : : if (!VALGRIND_CHECK_MEM_IS_ADDRESSABLE(&ptrs[i], sizeof(*ptrs))) {
583 : : return NULL;
584 : : }
585 : : #endif
586 : 11377014 : return ptrs[i];
587 : : }
588 : :
589 : 45163 : void gc_collect_root(void **ptrs, size_t len) {
590 : : #if !MICROPY_GC_SPLIT_HEAP
591 : : mp_state_mem_area_t *area = &MP_STATE_MEM(area);
592 : : #endif
593 [ + + ]: 11422177 : for (size_t i = 0; i < len; i++) {
594 : 11377014 : MICROPY_GC_HOOK_LOOP(i);
595 : 11377014 : void *ptr = gc_get_ptr(ptrs, i);
596 : : #if MICROPY_GC_SPLIT_HEAP
597 [ + + ]: 11377014 : mp_state_mem_area_t *area = gc_get_ptr_area(ptr);
598 [ + + ]: 6159752 : if (!area) {
599 : 11352484 : continue;
600 : : }
601 : : #else
602 : : if (!VERIFY_PTR(ptr)) {
603 : : continue;
604 : : }
605 : : #endif
606 : 24530 : size_t block = BLOCK_FROM_PTR(area, ptr);
607 [ + + ]: 24530 : if (ATB_GET_KIND(area, block) == AT_HEAD) {
608 : : // An unmarked head: mark it, and mark all its children
609 : 16874 : ATB_HEAD_TO_MARK(area, block);
610 : : #if MICROPY_GC_SPLIT_HEAP
611 : 16874 : gc_mark_subtree(area, block);
612 : : #else
613 : : gc_mark_subtree(block);
614 : : #endif
615 : : }
616 : : }
617 : 45163 : }
618 : :
619 : 15974 : void gc_collect_end(void) {
620 : 15974 : gc_deal_with_stack_overflow();
621 : 15974 : gc_sweep();
622 : : #if MICROPY_GC_SPLIT_HEAP
623 : 15974 : MP_STATE_MEM(gc_last_free_area) = &MP_STATE_MEM(area);
624 : : #endif
625 [ + + ]: 43006 : for (mp_state_mem_area_t *area = &MP_STATE_MEM(area); area != NULL; area = NEXT_AREA(area)) {
626 : 27032 : area->gc_last_free_atb_index = 0;
627 : : }
628 : 15974 : MP_STATE_THREAD(gc_lock_depth)--;
629 : 15974 : GC_EXIT();
630 : 15974 : }
631 : :
632 : 3262 : void gc_sweep_all(void) {
633 : 3262 : GC_ENTER();
634 : 3262 : MP_STATE_THREAD(gc_lock_depth)++;
635 : 3262 : MP_STATE_MEM(gc_stack_overflow) = 0;
636 : 3262 : gc_collect_end();
637 : 3262 : }
638 : :
639 : 26 : void gc_info(gc_info_t *info) {
640 : 26 : GC_ENTER();
641 : 26 : info->total = 0;
642 : 26 : info->used = 0;
643 : 26 : info->free = 0;
644 : 26 : info->max_free = 0;
645 : 26 : info->num_1block = 0;
646 : 26 : info->num_2block = 0;
647 : 26 : info->max_block = 0;
648 [ + + ]: 130 : for (mp_state_mem_area_t *area = &MP_STATE_MEM(area); area != NULL; area = NEXT_AREA(area)) {
649 : 104 : bool finish = false;
650 : 104 : info->total += area->gc_pool_end - area->gc_pool_start;
651 [ + + ]: 1683760 : for (size_t block = 0, len = 0, len_free = 0; !finish;) {
652 : 1683656 : MICROPY_GC_HOOK_LOOP(block);
653 : 1683656 : size_t kind = ATB_GET_KIND(area, block);
654 [ + + + - ]: 1683656 : switch (kind) {
655 : 1682250 : case AT_FREE:
656 : 1682250 : info->free += 1;
657 : 1682250 : len_free += 1;
658 : 1682250 : len = 0;
659 : 1682250 : break;
660 : :
661 : 628 : case AT_HEAD:
662 : 628 : info->used += 1;
663 : 628 : len = 1;
664 : 628 : break;
665 : :
666 : 778 : case AT_TAIL:
667 : 778 : info->used += 1;
668 : 778 : len += 1;
669 : 778 : break;
670 : :
671 : : case AT_MARK:
672 : : // shouldn't happen
673 : : break;
674 : : }
675 : :
676 : 1683656 : block++;
677 : 1683656 : finish = (block == area->gc_alloc_table_byte_len * BLOCKS_PER_ATB);
678 : : // Get next block type if possible
679 [ + + ]: 1683656 : if (!finish) {
680 : 1683552 : kind = ATB_GET_KIND(area, block);
681 : : }
682 : :
683 [ + + + + ]: 1683656 : if (finish || kind == AT_FREE || kind == AT_HEAD) {
684 [ + + ]: 1682878 : if (len == 1) {
685 : 348 : info->num_1block += 1;
686 [ + + ]: 1682530 : } else if (len == 2) {
687 : 148 : info->num_2block += 1;
688 : : }
689 [ + + ]: 1682878 : if (len > info->max_block) {
690 : 82 : info->max_block = len;
691 : : }
692 [ + + ]: 1682878 : if (finish || kind == AT_HEAD) {
693 [ + + ]: 706 : if (len_free > info->max_free) {
694 : 124 : info->max_free = len_free;
695 : : }
696 : : len_free = 0;
697 : : }
698 : : }
699 : : }
700 : : }
701 : :
702 : 26 : info->used *= BYTES_PER_BLOCK;
703 : 26 : info->free *= BYTES_PER_BLOCK;
704 : :
705 : : #if MICROPY_GC_SPLIT_HEAP_AUTO
706 : : info->max_new_split = gc_get_max_new_split();
707 : : #endif
708 : :
709 : 26 : GC_EXIT();
710 : 26 : }
711 : :
712 : 3752828 : void *gc_alloc(size_t n_bytes, unsigned int alloc_flags) {
713 : 3752828 : bool has_finaliser = alloc_flags & GC_ALLOC_FLAG_HAS_FINALISER;
714 : 3752828 : size_t n_blocks = ((n_bytes + BYTES_PER_BLOCK - 1) & (~(BYTES_PER_BLOCK - 1))) / BYTES_PER_BLOCK;
715 : 3752828 : DEBUG_printf("gc_alloc(" UINT_FMT " bytes -> " UINT_FMT " blocks)\n", n_bytes, n_blocks);
716 : :
717 : : // check for 0 allocation
718 [ + + ]: 3752828 : if (n_blocks == 0) {
719 : : return NULL;
720 : : }
721 : :
722 : : // check if GC is locked
723 [ + + ]: 3748266 : if (MP_STATE_THREAD(gc_lock_depth) > 0) {
724 : : return NULL;
725 : : }
726 : :
727 : 3747709 : GC_ENTER();
728 : :
729 : 3748472 : mp_state_mem_area_t *area;
730 : 3748472 : size_t i;
731 : 3748472 : size_t end_block;
732 : 3748472 : size_t start_block;
733 : 3748472 : size_t n_free;
734 : 3748472 : int collected = !MP_STATE_MEM(gc_auto_collect_enabled);
735 : : #if MICROPY_GC_SPLIT_HEAP_AUTO
736 : : bool added = false;
737 : : #endif
738 : :
739 : : #if MICROPY_GC_ALLOC_THRESHOLD
740 [ + + + + ]: 3748472 : if (!collected && MP_STATE_MEM(gc_alloc_amount) >= MP_STATE_MEM(gc_alloc_threshold)) {
741 : 24 : GC_EXIT();
742 : 24 : gc_collect();
743 : 24 : collected = 1;
744 : 24 : GC_ENTER();
745 : : }
746 : : #endif
747 : :
748 : 3765020 : for (;;) {
749 : :
750 : : #if MICROPY_GC_SPLIT_HEAP
751 : 3756746 : area = MP_STATE_MEM(gc_last_free_area);
752 : : #else
753 : : area = &MP_STATE_MEM(area);
754 : : #endif
755 : :
756 : : // look for a run of n_blocks available blocks
757 [ + + ]: 3782622 : for (; area != NULL; area = NEXT_AREA(area), i = 0) {
758 : 3770206 : n_free = 0;
759 [ + + ]: 145892047 : for (i = area->gc_last_free_atb_index; i < area->gc_alloc_table_byte_len; i++) {
760 : 145866171 : MICROPY_GC_HOOK_LOOP(i);
761 : 145866171 : byte a = area->gc_alloc_table_start[i];
762 : : // *FORMAT-OFF*
763 [ + + + + ]: 145866171 : if (ATB_0_IS_FREE(a)) { if (++n_free >= n_blocks) { i = i * BLOCKS_PER_ATB + 0; goto found; } } else { n_free = 0; }
764 [ + + + + ]: 144905609 : if (ATB_1_IS_FREE(a)) { if (++n_free >= n_blocks) { i = i * BLOCKS_PER_ATB + 1; goto found; } } else { n_free = 0; }
765 [ + + + + ]: 143993195 : if (ATB_2_IS_FREE(a)) { if (++n_free >= n_blocks) { i = i * BLOCKS_PER_ATB + 2; goto found; } } else { n_free = 0; }
766 [ + + + + ]: 143035612 : if (ATB_3_IS_FREE(a)) { if (++n_free >= n_blocks) { i = i * BLOCKS_PER_ATB + 3; goto found; } } else { n_free = 0; }
767 : : // *FORMAT-ON*
768 : : }
769 : :
770 : : // No free blocks found on this heap. Mark this heap as
771 : : // filled, so we won't try to find free space here again until
772 : : // space is freed.
773 : : #if MICROPY_GC_SPLIT_HEAP
774 [ + + ]: 25876 : if (n_blocks == 1) {
775 : 13175 : area->gc_last_free_atb_index = (i + 1) / BLOCKS_PER_ATB; // or (size_t)-1
776 : : }
777 : : #endif
778 : : }
779 : :
780 : 12416 : GC_EXIT();
781 : : // nothing found!
782 [ + + ]: 12416 : if (collected) {
783 : : #if MICROPY_GC_SPLIT_HEAP_AUTO
784 : : if (!added && gc_try_add_heap(n_bytes)) {
785 : : added = true;
786 : : continue;
787 : : }
788 : : #endif
789 : : return NULL;
790 : : }
791 : 8274 : DEBUG_printf("gc_alloc(" UINT_FMT "): no free mem, triggering GC\n", n_bytes);
792 : 8274 : gc_collect();
793 : 8274 : collected = 1;
794 : 8274 : GC_ENTER();
795 : : }
796 : :
797 : : // found, ending at block i inclusive
798 : 3744330 : found:
799 : : // get starting and end blocks, both inclusive
800 : 3744330 : end_block = i;
801 : 3744330 : start_block = i - n_free + 1;
802 : :
803 : : // Set last free ATB index to block after last block we found, for start of
804 : : // next scan. To reduce fragmentation, we only do this if we were looking
805 : : // for a single free block, which guarantees that there are no free blocks
806 : : // before this one. Also, whenever we free or shink a block we must check
807 : : // if this index needs adjusting (see gc_realloc and gc_free).
808 [ + + ]: 3744330 : if (n_free == 1) {
809 : : #if MICROPY_GC_SPLIT_HEAP
810 : 3070206 : MP_STATE_MEM(gc_last_free_area) = area;
811 : : #endif
812 : 3070206 : area->gc_last_free_atb_index = (i + 1) / BLOCKS_PER_ATB;
813 : : }
814 : :
815 : 3744330 : area->gc_last_used_block = MAX(area->gc_last_used_block, end_block);
816 : :
817 : : // mark first block as used head
818 : 3744330 : ATB_FREE_TO_HEAD(area, start_block);
819 : :
820 : : // mark rest of blocks as used tail
821 : : // TODO for a run of many blocks can make this more efficient
822 [ + + ]: 6466974 : for (size_t bl = start_block + 1; bl <= end_block; bl++) {
823 : 2722644 : ATB_FREE_TO_TAIL(area, bl);
824 : : }
825 : :
826 : : // get pointer to first block
827 : : // we must create this pointer before unlocking the GC so a collection can find it
828 : 3744330 : void *ret_ptr = (void *)(area->gc_pool_start + start_block * BYTES_PER_BLOCK);
829 : 3744330 : DEBUG_printf("gc_alloc(%p)\n", ret_ptr);
830 : :
831 : : #if MICROPY_GC_ALLOC_THRESHOLD
832 : 3744330 : MP_STATE_MEM(gc_alloc_amount) += n_blocks;
833 : : #endif
834 : :
835 : 3744330 : GC_EXIT();
836 : :
837 : : #if MICROPY_GC_CONSERVATIVE_CLEAR
838 : : // be conservative and zero out all the newly allocated blocks
839 : 3744177 : memset((byte *)ret_ptr, 0, (end_block - start_block + 1) * BYTES_PER_BLOCK);
840 : : #else
841 : : // zero out the additional bytes of the newly allocated blocks
842 : : // This is needed because the blocks may have previously held pointers
843 : : // to the heap and will not be set to something else if the caller
844 : : // doesn't actually use the entire block. As such they will continue
845 : : // to point to the heap and may prevent other blocks from being reclaimed.
846 : : memset((byte *)ret_ptr + n_bytes, 0, (end_block - start_block + 1) * BYTES_PER_BLOCK - n_bytes);
847 : : #endif
848 : :
849 : : #if MICROPY_ENABLE_FINALISER
850 [ + + ]: 3744177 : if (has_finaliser) {
851 : : // clear type pointer in case it is never set
852 : 8288 : ((mp_obj_base_t *)ret_ptr)->type = NULL;
853 : : // set mp_obj flag only if it has a finaliser
854 : 8288 : GC_ENTER();
855 : 8288 : FTB_SET(area, start_block);
856 : 8288 : GC_EXIT();
857 : : }
858 : : #else
859 : : (void)has_finaliser;
860 : : #endif
861 : :
862 : : #if EXTENSIVE_HEAP_PROFILING
863 : : gc_dump_alloc_table(&mp_plat_print);
864 : : #endif
865 : :
866 : : return ret_ptr;
867 : : }
868 : :
869 : : /*
870 : : void *gc_alloc(mp_uint_t n_bytes) {
871 : : return _gc_alloc(n_bytes, false);
872 : : }
873 : :
874 : : void *gc_alloc_with_finaliser(mp_uint_t n_bytes) {
875 : : return _gc_alloc(n_bytes, true);
876 : : }
877 : : */
878 : :
879 : : // force the freeing of a piece of memory
880 : : // TODO: freeing here does not call finaliser
881 : 549390 : void gc_free(void *ptr) {
882 [ + # ]: 549390 : if (MP_STATE_THREAD(gc_lock_depth) > 0) {
883 : : // Cannot free while the GC is locked. However free is an optimisation
884 : : // to reclaim the memory immediately, this means it will now be left
885 : : // until the next collection.
886 : : return;
887 : : }
888 : :
889 : 549312 : GC_ENTER();
890 : :
891 : 549579 : DEBUG_printf("gc_free(%p)\n", ptr);
892 : :
893 [ + + ]: 549579 : if (ptr == NULL) {
894 : : // free(NULL) is a no-op
895 : 10909 : GC_EXIT();
896 : 10909 : return;
897 : : }
898 : :
899 : : // get the GC block number corresponding to this pointer
900 : 538670 : mp_state_mem_area_t *area;
901 : : #if MICROPY_GC_SPLIT_HEAP
902 [ + - ]: 538670 : area = gc_get_ptr_area(ptr);
903 [ - + ]: 538670 : assert(area);
904 : : #else
905 : : assert(VERIFY_PTR(ptr));
906 : : area = &MP_STATE_MEM(area);
907 : : #endif
908 : :
909 : 538670 : size_t block = BLOCK_FROM_PTR(area, ptr);
910 [ - + ]: 538670 : assert(ATB_GET_KIND(area, block) == AT_HEAD);
911 : :
912 : : #if MICROPY_ENABLE_FINALISER
913 : 538670 : FTB_CLEAR(area, block);
914 : : #endif
915 : :
916 : : #if MICROPY_GC_SPLIT_HEAP
917 [ + + ]: 538670 : if (MP_STATE_MEM(gc_last_free_area) != area) {
918 : : // We freed something but it isn't the current area. Reset the
919 : : // last free area to the start for a rescan. Note that this won't
920 : : // give much of a performance hit, since areas that are completely
921 : : // filled will likely be skipped (the gc_last_free_atb_index
922 : : // points to the last block).
923 : : // The reason why this is necessary is because it is not possible
924 : : // to see which area came first (like it is possible to adjust
925 : : // gc_last_free_atb_index based on whether the freed block is
926 : : // before the last free block).
927 : 500 : MP_STATE_MEM(gc_last_free_area) = &MP_STATE_MEM(area);
928 : : }
929 : : #endif
930 : :
931 : : // set the last_free pointer to this block if it's earlier in the heap
932 [ + + ]: 538670 : if (block / BLOCKS_PER_ATB < area->gc_last_free_atb_index) {
933 : 86584 : area->gc_last_free_atb_index = block / BLOCKS_PER_ATB;
934 : : }
935 : :
936 : : // free head and all of its tail blocks
937 : 2591703 : do {
938 : 2591703 : ATB_ANY_TO_FREE(area, block);
939 : 2591703 : block += 1;
940 [ + + ]: 2591703 : } while (ATB_GET_KIND(area, block) == AT_TAIL);
941 : :
942 : 538670 : GC_EXIT();
943 : :
944 : : #if EXTENSIVE_HEAP_PROFILING
945 : : gc_dump_alloc_table(&mp_plat_print);
946 : : #endif
947 : : }
948 : :
949 : 26 : size_t gc_nbytes(const void *ptr) {
950 : 26 : GC_ENTER();
951 : :
952 : 26 : mp_state_mem_area_t *area;
953 : : #if MICROPY_GC_SPLIT_HEAP
954 [ + - ]: 26 : area = gc_get_ptr_area(ptr);
955 : : #else
956 : : if (VERIFY_PTR(ptr)) {
957 : : area = &MP_STATE_MEM(area);
958 : : } else {
959 : : area = NULL;
960 : : }
961 : : #endif
962 : :
963 [ + + ]: 26 : if (area) {
964 : 24 : size_t block = BLOCK_FROM_PTR(area, ptr);
965 [ + - ]: 24 : if (ATB_GET_KIND(area, block) == AT_HEAD) {
966 : : // work out number of consecutive blocks in the chain starting with this on
967 : : size_t n_blocks = 0;
968 : 152 : do {
969 : 152 : n_blocks += 1;
970 [ + + ]: 152 : } while (ATB_GET_KIND(area, block + n_blocks) == AT_TAIL);
971 : 24 : GC_EXIT();
972 : 24 : return n_blocks * BYTES_PER_BLOCK;
973 : : }
974 : : }
975 : :
976 : : // invalid pointer
977 : 2 : GC_EXIT();
978 : 2 : return 0;
979 : : }
980 : :
981 : : #if 0
982 : : // old, simple realloc that didn't expand memory in place
983 : : void *gc_realloc(void *ptr, mp_uint_t n_bytes) {
984 : : mp_uint_t n_existing = gc_nbytes(ptr);
985 : : if (n_bytes <= n_existing) {
986 : : return ptr;
987 : : } else {
988 : : bool has_finaliser;
989 : : if (ptr == NULL) {
990 : : has_finaliser = false;
991 : : } else {
992 : : #if MICROPY_ENABLE_FINALISER
993 : : has_finaliser = FTB_GET(BLOCK_FROM_PTR((mp_uint_t)ptr));
994 : : #else
995 : : has_finaliser = false;
996 : : #endif
997 : : }
998 : : void *ptr2 = gc_alloc(n_bytes, has_finaliser);
999 : : if (ptr2 == NULL) {
1000 : : return ptr2;
1001 : : }
1002 : : memcpy(ptr2, ptr, n_existing);
1003 : : gc_free(ptr);
1004 : : return ptr2;
1005 : : }
1006 : : }
1007 : :
1008 : : #else // Alternative gc_realloc impl
1009 : :
1010 : 515819 : void *gc_realloc(void *ptr_in, size_t n_bytes, bool allow_move) {
1011 : : // check for pure allocation
1012 [ + + ]: 515819 : if (ptr_in == NULL) {
1013 : 41373 : return gc_alloc(n_bytes, false);
1014 : : }
1015 : :
1016 : : // check for pure free
1017 [ + + ]: 474446 : if (n_bytes == 0) {
1018 : 2 : gc_free(ptr_in);
1019 : 2 : return NULL;
1020 : : }
1021 : :
1022 [ + + ]: 474444 : if (MP_STATE_THREAD(gc_lock_depth) > 0) {
1023 : : return NULL;
1024 : : }
1025 : :
1026 : 474418 : void *ptr = ptr_in;
1027 : :
1028 : 474418 : GC_ENTER();
1029 : :
1030 : : // get the GC block number corresponding to this pointer
1031 : 474418 : mp_state_mem_area_t *area;
1032 : : #if MICROPY_GC_SPLIT_HEAP
1033 [ + - ]: 474418 : area = gc_get_ptr_area(ptr);
1034 [ - + ]: 474418 : assert(area);
1035 : : #else
1036 : : assert(VERIFY_PTR(ptr));
1037 : : area = &MP_STATE_MEM(area);
1038 : : #endif
1039 : 474418 : size_t block = BLOCK_FROM_PTR(area, ptr);
1040 [ - + ]: 474418 : assert(ATB_GET_KIND(area, block) == AT_HEAD);
1041 : :
1042 : : // compute number of new blocks that are requested
1043 : 474418 : size_t new_blocks = (n_bytes + BYTES_PER_BLOCK - 1) / BYTES_PER_BLOCK;
1044 : :
1045 : : // Get the total number of consecutive blocks that are already allocated to
1046 : : // this chunk of memory, and then count the number of free blocks following
1047 : : // it. Stop if we reach the end of the heap, or if we find enough extra
1048 : : // free blocks to satisfy the realloc. Note that we need to compute the
1049 : : // total size of the existing memory chunk so we can correctly and
1050 : : // efficiently shrink it (see below for shrinking code).
1051 : 474418 : size_t n_free = 0;
1052 : 474418 : size_t n_blocks = 1; // counting HEAD block
1053 : 474418 : size_t max_block = area->gc_alloc_table_byte_len * BLOCKS_PER_ATB;
1054 [ + + ]: 9023416 : for (size_t bl = block + n_blocks; bl < max_block; bl++) {
1055 : 9023382 : byte block_type = ATB_GET_KIND(area, bl);
1056 [ + + ]: 9023382 : if (block_type == AT_TAIL) {
1057 : 8416632 : n_blocks++;
1058 : 8416632 : continue;
1059 : : }
1060 [ + + ]: 606750 : if (block_type == AT_FREE) {
1061 : 537087 : n_free++;
1062 [ + + ]: 537087 : if (n_blocks + n_free >= new_blocks) {
1063 : : // stop as soon as we find enough blocks for n_bytes
1064 : : break;
1065 : : }
1066 : 132366 : continue;
1067 : : }
1068 : : break;
1069 : : }
1070 : :
1071 : : // return original ptr if it already has the requested number of blocks
1072 [ + + ]: 474418 : if (new_blocks == n_blocks) {
1073 : 263008 : GC_EXIT();
1074 : 263008 : return ptr_in;
1075 : : }
1076 : :
1077 : : // check if we can shrink the allocated area
1078 [ + + ]: 211410 : if (new_blocks < n_blocks) {
1079 : : // free unneeded tail blocks
1080 [ + + ]: 50276 : for (size_t bl = block + new_blocks, count = n_blocks - new_blocks; count > 0; bl++, count--) {
1081 : 26185 : ATB_ANY_TO_FREE(area, bl);
1082 : : }
1083 : :
1084 : : #if MICROPY_GC_SPLIT_HEAP
1085 [ + + ]: 24091 : if (MP_STATE_MEM(gc_last_free_area) != area) {
1086 : : // See comment in gc_free.
1087 : 22 : MP_STATE_MEM(gc_last_free_area) = &MP_STATE_MEM(area);
1088 : : }
1089 : : #endif
1090 : :
1091 : : // set the last_free pointer to end of this block if it's earlier in the heap
1092 [ + + ]: 24091 : if ((block + new_blocks) / BLOCKS_PER_ATB < area->gc_last_free_atb_index) {
1093 : 876 : area->gc_last_free_atb_index = (block + new_blocks) / BLOCKS_PER_ATB;
1094 : : }
1095 : :
1096 : 24091 : GC_EXIT();
1097 : :
1098 : : #if EXTENSIVE_HEAP_PROFILING
1099 : : gc_dump_alloc_table(&mp_plat_print);
1100 : : #endif
1101 : :
1102 : 24091 : return ptr_in;
1103 : : }
1104 : :
1105 : : // check if we can expand in place
1106 [ + + ]: 187319 : if (new_blocks <= n_blocks + n_free) {
1107 : : // mark few more blocks as used tail
1108 : 155396 : size_t end_block = block + new_blocks;
1109 [ + + ]: 387568 : for (size_t bl = block + n_blocks; bl < end_block; bl++) {
1110 [ - + ]: 232172 : assert(ATB_GET_KIND(area, bl) == AT_FREE);
1111 : 232172 : ATB_FREE_TO_TAIL(area, bl);
1112 : : }
1113 : :
1114 : 155396 : area->gc_last_used_block = MAX(area->gc_last_used_block, end_block);
1115 : :
1116 : 155396 : GC_EXIT();
1117 : :
1118 : : #if MICROPY_GC_CONSERVATIVE_CLEAR
1119 : : // be conservative and zero out all the newly allocated blocks
1120 : 155396 : memset((byte *)ptr_in + n_blocks * BYTES_PER_BLOCK, 0, (new_blocks - n_blocks) * BYTES_PER_BLOCK);
1121 : : #else
1122 : : // zero out the additional bytes of the newly allocated blocks (see comment above in gc_alloc)
1123 : : memset((byte *)ptr_in + n_bytes, 0, new_blocks * BYTES_PER_BLOCK - n_bytes);
1124 : : #endif
1125 : :
1126 : : #if EXTENSIVE_HEAP_PROFILING
1127 : : gc_dump_alloc_table(&mp_plat_print);
1128 : : #endif
1129 : :
1130 : 155396 : return ptr_in;
1131 : : }
1132 : :
1133 : : #if MICROPY_ENABLE_FINALISER
1134 : 31923 : bool ftb_state = FTB_GET(area, block);
1135 : : #else
1136 : : bool ftb_state = false;
1137 : : #endif
1138 : :
1139 : 31923 : GC_EXIT();
1140 : :
1141 [ + + ]: 31923 : if (!allow_move) {
1142 : : // not allowed to move memory block so return failure
1143 : : return NULL;
1144 : : }
1145 : :
1146 : : // can't resize inplace; try to find a new contiguous chain
1147 : 20256 : void *ptr_out = gc_alloc(n_bytes, ftb_state);
1148 : :
1149 : : // check that the alloc succeeded
1150 [ + + ]: 20256 : if (ptr_out == NULL) {
1151 : : return NULL;
1152 : : }
1153 : :
1154 : 20248 : DEBUG_printf("gc_realloc(%p -> %p)\n", ptr_in, ptr_out);
1155 : 20248 : memcpy(ptr_out, ptr_in, n_blocks * BYTES_PER_BLOCK);
1156 : 20248 : gc_free(ptr_in);
1157 : 20248 : return ptr_out;
1158 : : }
1159 : : #endif // Alternative gc_realloc impl
1160 : :
1161 : 18 : void gc_dump_info(const mp_print_t *print) {
1162 : 18 : gc_info_t info;
1163 : 18 : gc_info(&info);
1164 : 18 : mp_printf(print, "GC: total: %u, used: %u, free: %u",
1165 : 18 : (uint)info.total, (uint)info.used, (uint)info.free);
1166 : : #if MICROPY_GC_SPLIT_HEAP_AUTO
1167 : : mp_printf(print, ", max new split: %u", (uint)info.max_new_split);
1168 : : #endif
1169 : 18 : mp_printf(print, "\n No. of 1-blocks: %u, 2-blocks: %u, max blk sz: %u, max free sz: %u\n",
1170 : 18 : (uint)info.num_1block, (uint)info.num_2block, (uint)info.max_block, (uint)info.max_free);
1171 : 18 : }
1172 : :
1173 : 4 : void gc_dump_alloc_table(const mp_print_t *print) {
1174 : 4 : GC_ENTER();
1175 : 4 : static const size_t DUMP_BYTES_PER_LINE = 64;
1176 [ + + ]: 20 : for (mp_state_mem_area_t *area = &MP_STATE_MEM(area); area != NULL; area = NEXT_AREA(area)) {
1177 : : #if !EXTENSIVE_HEAP_PROFILING
1178 : : // When comparing heap output we don't want to print the starting
1179 : : // pointer of the heap because it changes from run to run.
1180 : 16 : mp_printf(print, "GC memory layout; from %p:", area->gc_pool_start);
1181 : : #endif
1182 [ + + ]: 1248 : for (size_t bl = 0; bl < area->gc_alloc_table_byte_len * BLOCKS_PER_ATB; bl++) {
1183 [ + + ]: 1236 : if (bl % DUMP_BYTES_PER_LINE == 0) {
1184 : : // a new line of blocks
1185 : : {
1186 : : // check if this line contains only free blocks
1187 : : size_t bl2 = bl;
1188 [ + + + + ]: 258608 : while (bl2 < area->gc_alloc_table_byte_len * BLOCKS_PER_ATB && ATB_GET_KIND(area, bl2) == AT_FREE) {
1189 : 258584 : bl2++;
1190 : : }
1191 [ + + ]: 24 : if (bl2 - bl >= 2 * DUMP_BYTES_PER_LINE) {
1192 : : // there are at least 2 lines containing only free blocks, so abbreviate their printing
1193 : 16 : mp_printf(print, "\n (%u lines all free)", (uint)(bl2 - bl) / DUMP_BYTES_PER_LINE);
1194 : 16 : bl = bl2 & (~(DUMP_BYTES_PER_LINE - 1));
1195 [ + + ]: 16 : if (bl >= area->gc_alloc_table_byte_len * BLOCKS_PER_ATB) {
1196 : : // got to end of heap
1197 : : break;
1198 : : }
1199 : : }
1200 : : }
1201 : : // print header for new line of blocks
1202 : : // (the cast to uint32_t is for 16-bit ports)
1203 : 20 : mp_printf(print, "\n%08x: ", (uint)(bl * BYTES_PER_BLOCK));
1204 : : }
1205 : 1232 : int c = ' ';
1206 [ + + - + ]: 1232 : switch (ATB_GET_KIND(area, bl)) {
1207 : : case AT_FREE:
1208 : : c = '.';
1209 : : break;
1210 : : /* this prints out if the object is reachable from BSS or STACK (for unix only)
1211 : : case AT_HEAD: {
1212 : : c = 'h';
1213 : : void **ptrs = (void**)(void*)&mp_state_ctx;
1214 : : mp_uint_t len = offsetof(mp_state_ctx_t, vm.stack_top) / sizeof(mp_uint_t);
1215 : : for (mp_uint_t i = 0; i < len; i++) {
1216 : : mp_uint_t ptr = (mp_uint_t)ptrs[i];
1217 : : if (gc_get_ptr_area(ptr) && BLOCK_FROM_PTR(ptr) == bl) {
1218 : : c = 'B';
1219 : : break;
1220 : : }
1221 : : }
1222 : : if (c == 'h') {
1223 : : ptrs = (void**)&c;
1224 : : len = ((mp_uint_t)MP_STATE_THREAD(stack_top) - (mp_uint_t)&c) / sizeof(mp_uint_t);
1225 : : for (mp_uint_t i = 0; i < len; i++) {
1226 : : mp_uint_t ptr = (mp_uint_t)ptrs[i];
1227 : : if (gc_get_ptr_area(ptr) && BLOCK_FROM_PTR(ptr) == bl) {
1228 : : c = 'S';
1229 : : break;
1230 : : }
1231 : : }
1232 : : }
1233 : : break;
1234 : : }
1235 : : */
1236 : : /* this prints the uPy object type of the head block */
1237 : 76 : case AT_HEAD: {
1238 : 76 : void **ptr = (void **)(area->gc_pool_start + bl * BYTES_PER_BLOCK);
1239 [ + - ]: 76 : if (*ptr == &mp_type_tuple) {
1240 : : c = 'T';
1241 [ + + ]: 76 : } else if (*ptr == &mp_type_list) {
1242 : : c = 'L';
1243 [ + - ]: 72 : } else if (*ptr == &mp_type_dict) {
1244 : : c = 'D';
1245 [ + - + - ]: 72 : } else if (*ptr == &mp_type_str || *ptr == &mp_type_bytes) {
1246 : : c = 'S';
1247 : : }
1248 : : #if MICROPY_PY_BUILTINS_BYTEARRAY
1249 [ + - ]: 72 : else if (*ptr == &mp_type_bytearray) {
1250 : : c = 'A';
1251 : : }
1252 : : #endif
1253 : : #if MICROPY_PY_ARRAY
1254 [ + - ]: 72 : else if (*ptr == &mp_type_array) {
1255 : : c = 'A';
1256 : : }
1257 : : #endif
1258 : : #if MICROPY_PY_BUILTINS_FLOAT
1259 [ + - ]: 72 : else if (*ptr == &mp_type_float) {
1260 : : c = 'F';
1261 : : }
1262 : : #endif
1263 [ + + ]: 72 : else if (*ptr == &mp_type_fun_bc) {
1264 : : c = 'B';
1265 [ + - ]: 68 : } else if (*ptr == &mp_type_module) {
1266 : : c = 'M';
1267 : : } else {
1268 : 68 : c = 'h';
1269 : : #if 0
1270 : : // This code prints "Q" for qstr-pool data, and "q" for qstr-str
1271 : : // data. It can be useful to see how qstrs are being allocated,
1272 : : // but is disabled by default because it is very slow.
1273 : : for (qstr_pool_t *pool = MP_STATE_VM(last_pool); c == 'h' && pool != NULL; pool = pool->prev) {
1274 : : if ((qstr_pool_t *)ptr == pool) {
1275 : : c = 'Q';
1276 : : break;
1277 : : }
1278 : : for (const byte **q = pool->qstrs, **q_top = pool->qstrs + pool->len; q < q_top; q++) {
1279 : : if ((const byte *)ptr == *q) {
1280 : : c = 'q';
1281 : : break;
1282 : : }
1283 : : }
1284 : : }
1285 : : #endif
1286 : : }
1287 : : break;
1288 : : }
1289 : 96 : case AT_TAIL:
1290 : 96 : c = '=';
1291 : 96 : break;
1292 : 0 : case AT_MARK:
1293 : 0 : c = 'm';
1294 : 0 : break;
1295 : : }
1296 : 1232 : mp_printf(print, "%c", c);
1297 : : }
1298 : 16 : mp_print_str(print, "\n");
1299 : : }
1300 : 4 : GC_EXIT();
1301 : 4 : }
1302 : :
1303 : : #if 0
1304 : : // For testing the GC functions
1305 : : void gc_test(void) {
1306 : : mp_uint_t len = 500;
1307 : : mp_uint_t *heap = malloc(len);
1308 : : gc_init(heap, heap + len / sizeof(mp_uint_t));
1309 : : void *ptrs[100];
1310 : : {
1311 : : mp_uint_t **p = gc_alloc(16, false);
1312 : : p[0] = gc_alloc(64, false);
1313 : : p[1] = gc_alloc(1, false);
1314 : : p[2] = gc_alloc(1, false);
1315 : : p[3] = gc_alloc(1, false);
1316 : : mp_uint_t ***p2 = gc_alloc(16, false);
1317 : : p2[0] = p;
1318 : : p2[1] = p;
1319 : : ptrs[0] = p2;
1320 : : }
1321 : : for (int i = 0; i < 25; i += 2) {
1322 : : mp_uint_t *p = gc_alloc(i, false);
1323 : : printf("p=%p\n", p);
1324 : : if (i & 3) {
1325 : : // ptrs[i] = p;
1326 : : }
1327 : : }
1328 : :
1329 : : printf("Before GC:\n");
1330 : : gc_dump_alloc_table(&mp_plat_print);
1331 : : printf("Starting GC...\n");
1332 : : gc_collect_start();
1333 : : gc_collect_root(ptrs, sizeof(ptrs) / sizeof(void *));
1334 : : gc_collect_end();
1335 : : printf("After GC:\n");
1336 : : gc_dump_alloc_table(&mp_plat_print);
1337 : : }
1338 : : #endif
1339 : :
1340 : : #endif // MICROPY_ENABLE_GC
|
