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 : 17776 : 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 : 17776 : size_t total_byte_len = (byte *)end - (byte *)start;
131 : : #if MICROPY_ENABLE_FINALISER
132 : 17776 : area->gc_alloc_table_byte_len = (total_byte_len - ALLOC_TABLE_GAP_BYTE)
133 : 17776 : * MP_BITS_PER_BYTE
134 : 17776 : / (
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 : 17776 : area->gc_alloc_table_start = (byte *)start;
144 : :
145 : : #if MICROPY_ENABLE_FINALISER
146 : 17776 : size_t gc_finaliser_table_byte_len = (area->gc_alloc_table_byte_len * BLOCKS_PER_ATB + BLOCKS_PER_FTB - 1) / BLOCKS_PER_FTB;
147 : 17776 : area->gc_finaliser_table_start = area->gc_alloc_table_start + area->gc_alloc_table_byte_len + ALLOC_TABLE_GAP_BYTE;
148 : : #endif
149 : :
150 : 17776 : size_t gc_pool_block_len = area->gc_alloc_table_byte_len * BLOCKS_PER_ATB;
151 : 17776 : area->gc_pool_start = (byte *)end - gc_pool_block_len * BYTES_PER_BLOCK;
152 : 17776 : area->gc_pool_end = end;
153 : :
154 : : #if MICROPY_ENABLE_FINALISER
155 [ - + ]: 17776 : 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 : 17776 : 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 : 17776 : area->gc_last_free_atb_index = 0;
167 : 17776 : area->gc_last_used_block = 0;
168 : :
169 : : #if MICROPY_GC_SPLIT_HEAP
170 : 17776 : area->next = NULL;
171 : : #endif
172 : :
173 : 17776 : DEBUG_printf("GC layout:\n");
174 : 17776 : 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 : 17776 : 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 : 17776 : 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 : 17776 : }
188 : :
189 : 7516 : void gc_init(void *start, void *end) {
190 : : // align end pointer on block boundary
191 : 7516 : end = (void *)((uintptr_t)end & (~(BYTES_PER_BLOCK - 1)));
192 : 7516 : DEBUG_printf("Initializing GC heap: %p..%p = " UINT_FMT " bytes\n", start, end, (byte *)end - (byte *)start);
193 : :
194 : 7516 : 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 : 7516 : MP_STATE_MEM(gc_last_free_area) = &MP_STATE_MEM(area);
199 : : #endif
200 : :
201 : : // unlock the GC
202 : 7516 : MP_STATE_THREAD(gc_lock_depth) = 0;
203 : :
204 : : // allow auto collection
205 : 7516 : 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 : 7516 : MP_STATE_MEM(gc_alloc_threshold) = (size_t)-1;
210 : 7516 : MP_STATE_MEM(gc_alloc_amount) = 0;
211 : : #endif
212 : :
213 : : #if MICROPY_PY_THREAD && !MICROPY_PY_THREAD_GIL
214 : 7516 : mp_thread_mutex_init(&MP_STATE_MEM(gc_mutex));
215 : : #endif
216 : 7516 : }
217 : :
218 : : #if MICROPY_GC_SPLIT_HEAP
219 : 10260 : void gc_add(void *start, void *end) {
220 : : // Place the area struct at the start of the area.
221 : 10260 : mp_state_mem_area_t *area = (mp_state_mem_area_t *)start;
222 : 10260 : start = (void *)((uintptr_t)start + sizeof(mp_state_mem_area_t));
223 : :
224 : 10260 : end = (void *)((uintptr_t)end & (~(BYTES_PER_BLOCK - 1)));
225 : 10260 : DEBUG_printf("Adding GC heap: %p..%p = " UINT_FMT " bytes\n", start, end, (byte *)end - (byte *)start);
226 : :
227 : : // Init this area
228 : 10260 : gc_setup_area(area, start, end);
229 : :
230 : : // Find the last registered area in the linked list
231 : 10260 : mp_state_mem_area_t *prev_area = &MP_STATE_MEM(area);
232 [ + + ]: 20520 : while (prev_area->next != NULL) {
233 : : prev_area = prev_area->next;
234 : : }
235 : :
236 : : // Add this area to the linked list
237 : 10260 : prev_area->next = area;
238 : 10260 : }
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 : 253 : 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 : 253 : MP_STATE_THREAD(gc_lock_depth)++;
338 : 253 : }
339 : :
340 : 253 : void gc_unlock(void) {
341 : : // This does not need to be atomic, See comment above in gc_lock.
342 : 253 : MP_STATE_THREAD(gc_lock_depth)--;
343 : 253 : }
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 : 24594505 : static inline mp_state_mem_area_t *gc_get_ptr_area(const void *ptr) {
353 : 24594505 : if (((uintptr_t)(ptr) & (BYTES_PER_BLOCK - 1)) != 0) { // must be aligned on a block
354 : : return NULL;
355 : : }
356 [ + - + + : 55582053 : for (mp_state_mem_area_t *area = &MP_STATE_MEM(area); area != NULL; area = NEXT_AREA(area)) {
+ - + + +
+ ]
357 [ + + + + : 41103809 : if (ptr >= (void *)area->gc_pool_start // must be above start of pool
+ + + + +
+ ]
358 [ - + - + : 5917095 : && 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 : 18599 : 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 : 18599 : size_t sp = 0;
393 : 8362859 : 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 : 4190729 : size_t n_blocks = 0;
400 : 4318503 : do {
401 : 4318503 : n_blocks += 1;
402 [ + + ]: 4318503 : } 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 [ - + ]: 4190729 : assert(area->gc_pool_start + (block + n_blocks) * BYTES_PER_BLOCK <= area->gc_pool_end);
406 : :
407 : : // check this block's children
408 : 4190729 : void **ptrs = (void **)PTR_FROM_BLOCK(area, block);
409 [ + + ]: 21464741 : for (size_t i = n_blocks * BYTES_PER_BLOCK / sizeof(void *); i > 0; i--, ptrs++) {
410 : 17274012 : MICROPY_GC_HOOK_LOOP(i);
411 : 17274012 : 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 [ + + ]: 17274012 : mp_state_mem_area_t *ptr_area = gc_get_ptr_area(ptr);
416 [ + + ]: 14291891 : if (!ptr_area) {
417 : : // Not a heap-allocated pointer (might even be random data).
418 : 13096476 : continue;
419 : : }
420 : : #else
421 : : if (!VERIFY_PTR(ptr)) {
422 : : continue;
423 : : }
424 : : mp_state_mem_area_t *ptr_area = area;
425 : : #endif
426 : 4177536 : size_t ptr_block = BLOCK_FROM_PTR(ptr_area, ptr);
427 [ + + ]: 4177536 : if (ATB_GET_KIND(ptr_area, ptr_block) != AT_HEAD) {
428 : : // This block is already marked.
429 : 5124 : continue;
430 : : }
431 : : // An unmarked head. Mark it, and push it on gc stack.
432 : 4172412 : TRACE_MARK(ptr_block, ptr);
433 : 4172412 : ATB_HEAD_TO_MARK(ptr_area, ptr_block);
434 [ + + ]: 4172412 : if (sp < MICROPY_ALLOC_GC_STACK_SIZE) {
435 : 4172130 : MP_STATE_MEM(gc_block_stack)[sp] = ptr_block;
436 : : #if MICROPY_GC_SPLIT_HEAP
437 : 4172130 : MP_STATE_MEM(gc_area_stack)[sp] = ptr_area;
438 : : #endif
439 : 4172130 : 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 [ + + ]: 4190729 : if (sp == 0) {
447 : : break; // No, stack is empty, we're done.
448 : : }
449 : :
450 : : // pop the next block off the stack
451 : 4172130 : sp -= 1;
452 : 4172130 : block = MP_STATE_MEM(gc_block_stack)[sp];
453 : : #if MICROPY_GC_SPLIT_HEAP
454 : 4172130 : area = MP_STATE_MEM(gc_area_stack)[sp];
455 : : #endif
456 : : }
457 : 18599 : }
458 : :
459 : 16137 : static void gc_deal_with_stack_overflow(void) {
460 [ + + ]: 16140 : 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 : 16137 : }
479 : :
480 : 16137 : static void gc_sweep(void) {
481 : : #if MICROPY_PY_GC_COLLECT_RETVAL
482 : 16137 : MP_STATE_MEM(gc_collected) = 0;
483 : : #endif
484 : : // free unmarked heads and their tails
485 : 16137 : int free_tail = 0;
486 : : #if MICROPY_GC_SPLIT_HEAP_AUTO
487 : : mp_state_mem_area_t *prev_area = NULL;
488 : : #endif
489 [ + + ]: 43821 : for (mp_state_mem_area_t *area = &MP_STATE_MEM(area); area != NULL; area = NEXT_AREA(area)) {
490 : 27684 : size_t end_block = area->gc_alloc_table_byte_len * BLOCKS_PER_ATB;
491 [ + + ]: 27684 : if (area->gc_last_used_block < end_block) {
492 : 27682 : end_block = area->gc_last_used_block + 1;
493 : : }
494 : :
495 : 27684 : size_t last_used_block = 0;
496 : :
497 [ + + ]: 8432251 : for (size_t block = 0; block < end_block; block++) {
498 : 8404567 : MICROPY_GC_HOOK_LOOP(block);
499 [ + + + + ]: 8404567 : switch (ATB_GET_KIND(area, block)) {
500 : 2812701 : case AT_HEAD:
501 : : #if MICROPY_ENABLE_FINALISER
502 [ + + ]: 2812701 : if (FTB_GET(area, block)) {
503 : 4443 : mp_obj_base_t *obj = (mp_obj_base_t *)PTR_FROM_BLOCK(area, block);
504 [ + - ]: 4443 : if (obj->type != NULL) {
505 : : // if the object has a type then see if it has a __del__ method
506 : 4443 : mp_obj_t dest[2];
507 : 4443 : mp_load_method_maybe(MP_OBJ_FROM_PTR(obj), MP_QSTR___del__, dest);
508 [ + - ]: 4443 : if (dest[0] != MP_OBJ_NULL) {
509 : : // load_method returned a method, execute it in a protected environment
510 : : #if MICROPY_ENABLE_SCHEDULER
511 : 4443 : mp_sched_lock();
512 : : #endif
513 : 4443 : mp_call_function_1_protected(dest[0], dest[1]);
514 : : #if MICROPY_ENABLE_SCHEDULER
515 : 4443 : mp_sched_unlock();
516 : : #endif
517 : : }
518 : : }
519 : : // clear finaliser flag
520 : 4443 : FTB_CLEAR(area, block);
521 : : }
522 : : #endif
523 : 2812701 : free_tail = 1;
524 : 2812701 : DEBUG_printf("gc_sweep(%p)\n", (void *)PTR_FROM_BLOCK(area, block));
525 : : #if MICROPY_PY_GC_COLLECT_RETVAL
526 : 2812701 : MP_STATE_MEM(gc_collected)++;
527 : : #endif
528 : : // fall through to free the head
529 : 3779981 : MP_FALLTHROUGH
530 : :
531 : 967280 : case AT_TAIL:
532 [ + + ]: 3779981 : if (free_tail) {
533 : 3652561 : 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 : 4189541 : case AT_MARK:
543 : 4189541 : ATB_MARK_TO_HEAD(area, block);
544 : 4189541 : free_tail = 0;
545 : 4189541 : last_used_block = block;
546 : 4189541 : break;
547 : : }
548 : : }
549 : :
550 : 27684 : 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 : 16137 : }
564 : :
565 : 12721 : void gc_collect_start(void) {
566 : 12721 : GC_ENTER();
567 : 12721 : MP_STATE_THREAD(gc_lock_depth)++;
568 : : #if MICROPY_GC_ALLOC_THRESHOLD
569 : 12721 : MP_STATE_MEM(gc_alloc_amount) = 0;
570 : : #endif
571 : 12721 : 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 : 12721 : void **ptrs = (void **)(void *)&mp_state_ctx;
577 : 12721 : size_t root_start = offsetof(mp_state_ctx_t, thread.dict_locals);
578 : 12721 : size_t root_end = offsetof(mp_state_ctx_t, vm.qstr_last_chunk);
579 : 12721 : 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 : 12721 : }
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 : 6189693 : 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 : 6189693 : return ptrs[i];
601 : : }
602 : :
603 : 38517 : 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 [ + + ]: 6228210 : for (size_t i = 0; i < len; i++) {
608 : 6189693 : MICROPY_GC_HOOK_LOOP(i);
609 : 6189693 : void *ptr = gc_get_ptr(ptrs, i);
610 : : #if MICROPY_GC_SPLIT_HEAP
611 [ + + ]: 6189693 : mp_state_mem_area_t *area = gc_get_ptr_area(ptr);
612 [ + + ]: 4389841 : if (!area) {
613 : 6163739 : continue;
614 : : }
615 : : #else
616 : : if (!VERIFY_PTR(ptr)) {
617 : : continue;
618 : : }
619 : : #endif
620 : 25954 : size_t block = BLOCK_FROM_PTR(area, ptr);
621 [ + + ]: 25954 : if (ATB_GET_KIND(area, block) == AT_HEAD) {
622 : : // An unmarked head: mark it, and mark all its children
623 : 17129 : ATB_HEAD_TO_MARK(area, block);
624 : : #if MICROPY_GC_SPLIT_HEAP
625 : 17129 : gc_mark_subtree(area, block);
626 : : #else
627 : : gc_mark_subtree(block);
628 : : #endif
629 : : }
630 : : }
631 : 38517 : }
632 : :
633 : 16137 : void gc_collect_end(void) {
634 : 16137 : gc_deal_with_stack_overflow();
635 : 16137 : gc_sweep();
636 : : #if MICROPY_GC_SPLIT_HEAP
637 : 16137 : MP_STATE_MEM(gc_last_free_area) = &MP_STATE_MEM(area);
638 : : #endif
639 [ + + ]: 43821 : for (mp_state_mem_area_t *area = &MP_STATE_MEM(area); area != NULL; area = NEXT_AREA(area)) {
640 : 27684 : area->gc_last_free_atb_index = 0;
641 : : }
642 : 16137 : MP_STATE_THREAD(gc_lock_depth)--;
643 : 16137 : GC_EXIT();
644 : 16137 : }
645 : :
646 : 3416 : void gc_sweep_all(void) {
647 : 3416 : GC_ENTER();
648 : 3416 : MP_STATE_THREAD(gc_lock_depth)++;
649 : 3416 : MP_STATE_MEM(gc_stack_overflow) = 0;
650 : 3416 : gc_collect_end();
651 : 3416 : }
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 : 3958910 : void *gc_alloc(size_t n_bytes, unsigned int alloc_flags) {
727 : 3958910 : bool has_finaliser = alloc_flags & GC_ALLOC_FLAG_HAS_FINALISER;
728 : 3958910 : size_t n_blocks = ((n_bytes + BYTES_PER_BLOCK - 1) & (~(BYTES_PER_BLOCK - 1))) / BYTES_PER_BLOCK;
729 : 3958910 : DEBUG_printf("gc_alloc(" UINT_FMT " bytes -> " UINT_FMT " blocks)\n", n_bytes, n_blocks);
730 : :
731 : : // check for 0 allocation
732 [ + + ]: 3958910 : if (n_blocks == 0) {
733 : : return NULL;
734 : : }
735 : :
736 : : // check if GC is locked
737 [ + + ]: 3954235 : if (MP_STATE_THREAD(gc_lock_depth) > 0) {
738 : : return NULL;
739 : : }
740 : :
741 : 3953575 : GC_ENTER();
742 : :
743 : 3954547 : mp_state_mem_area_t *area;
744 : 3954547 : size_t i;
745 : 3954547 : size_t end_block;
746 : 3954547 : size_t start_block;
747 : 3954547 : size_t n_free;
748 : 3954547 : 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 [ + + + + ]: 3954547 : 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 : 3971093 : for (;;) {
763 : :
764 : : #if MICROPY_GC_SPLIT_HEAP
765 : 3962820 : 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 [ + + ]: 3985144 : for (; area != NULL; area = NEXT_AREA(area), i = 0) {
772 : 3972730 : n_free = 0;
773 [ + + ]: 138177406 : for (i = area->gc_last_free_atb_index; i < area->gc_alloc_table_byte_len; i++) {
774 : 138155082 : MICROPY_GC_HOOK_LOOP(i);
775 : 138155082 : byte a = area->gc_alloc_table_start[i];
776 : : // *FORMAT-OFF*
777 [ + + + + ]: 138155082 : if (ATB_0_IS_FREE(a)) { if (++n_free >= n_blocks) { i = i * BLOCKS_PER_ATB + 0; goto found; } } else { n_free = 0; }
778 [ + + + + ]: 137158628 : if (ATB_1_IS_FREE(a)) { if (++n_free >= n_blocks) { i = i * BLOCKS_PER_ATB + 1; goto found; } } else { n_free = 0; }
779 [ + + + + ]: 136166291 : if (ATB_2_IS_FREE(a)) { if (++n_free >= n_blocks) { i = i * BLOCKS_PER_ATB + 2; goto found; } } else { n_free = 0; }
780 [ + + + + ]: 135174874 : 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 [ + + ]: 22324 : if (n_blocks == 1) {
789 : 13177 : area->gc_last_free_atb_index = (i + 1) / BLOCKS_PER_ATB; // or (size_t)-1
790 : : }
791 : : #endif
792 : : }
793 : :
794 : 12414 : GC_EXIT();
795 : : // nothing found!
796 [ + + ]: 12414 : 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 : 8273 : DEBUG_printf("gc_alloc(" UINT_FMT "): no free mem, triggering GC\n", n_bytes);
806 : 8273 : gc_collect();
807 : 8273 : collected = 1;
808 : 8273 : GC_ENTER();
809 : : }
810 : :
811 : : // found, ending at block i inclusive
812 : 3950406 : found:
813 : : // get starting and end blocks, both inclusive
814 : 3950406 : end_block = i;
815 : 3950406 : 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 [ + + ]: 3950406 : if (n_free == 1) {
823 : : #if MICROPY_GC_SPLIT_HEAP
824 : 3196831 : MP_STATE_MEM(gc_last_free_area) = area;
825 : : #endif
826 : 3196831 : area->gc_last_free_atb_index = (i + 1) / BLOCKS_PER_ATB;
827 : : }
828 : :
829 : 3950406 : area->gc_last_used_block = MAX(area->gc_last_used_block, end_block);
830 : :
831 : : // mark first block as used head
832 : 3950406 : 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 [ + + ]: 7002199 : for (size_t bl = start_block + 1; bl <= end_block; bl++) {
837 : 3051793 : 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 : 3950406 : void *ret_ptr = (void *)(area->gc_pool_start + start_block * BYTES_PER_BLOCK);
843 : 3950406 : DEBUG_printf("gc_alloc(%p)\n", ret_ptr);
844 : :
845 : : #if MICROPY_GC_ALLOC_THRESHOLD
846 : 3950406 : MP_STATE_MEM(gc_alloc_amount) += n_blocks;
847 : : #endif
848 : :
849 : 3950406 : GC_EXIT();
850 : :
851 : : #if MICROPY_GC_CONSERVATIVE_CLEAR
852 : : // be conservative and zero out all the newly allocated blocks
853 : 3950356 : 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 [ + + ]: 3950356 : if (has_finaliser) {
865 : : // clear type pointer in case it is never set
866 : 8553 : ((mp_obj_base_t *)ret_ptr)->type = NULL;
867 : : // set mp_obj flag only if it has a finaliser
868 : 8553 : GC_ENTER();
869 : 8553 : FTB_SET(area, start_block);
870 : 8553 : 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 : : // force the freeing of a piece of memory
884 : : // TODO: freeing here does not call finaliser
885 : 641035 : void gc_free(void *ptr) {
886 [ + + ]: 641035 : if (MP_STATE_THREAD(gc_lock_depth) > 0) {
887 : : // Cannot free while the GC is locked. However free is an optimisation
888 : : // to reclaim the memory immediately, this means it will now be left
889 : : // until the next collection.
890 : : return;
891 : : }
892 : :
893 : 641030 : GC_ENTER();
894 : :
895 : 641283 : DEBUG_printf("gc_free(%p)\n", ptr);
896 : :
897 [ + + ]: 641283 : if (ptr == NULL) {
898 : : // free(NULL) is a no-op
899 : 11584 : GC_EXIT();
900 : 11584 : return;
901 : : }
902 : :
903 : : // get the GC block number corresponding to this pointer
904 : 629699 : mp_state_mem_area_t *area;
905 : : #if MICROPY_GC_SPLIT_HEAP
906 [ + - ]: 629699 : area = gc_get_ptr_area(ptr);
907 [ - + ]: 629699 : assert(area);
908 : : #else
909 : : assert(VERIFY_PTR(ptr));
910 : : area = &MP_STATE_MEM(area);
911 : : #endif
912 : :
913 : 629699 : size_t block = BLOCK_FROM_PTR(area, ptr);
914 [ - + ]: 629699 : assert(ATB_GET_KIND(area, block) == AT_HEAD);
915 : :
916 : : #if MICROPY_ENABLE_FINALISER
917 : 629699 : FTB_CLEAR(area, block);
918 : : #endif
919 : :
920 : : #if MICROPY_GC_SPLIT_HEAP
921 [ + + ]: 629699 : if (MP_STATE_MEM(gc_last_free_area) != area) {
922 : : // We freed something but it isn't the current area. Reset the
923 : : // last free area to the start for a rescan. Note that this won't
924 : : // give much of a performance hit, since areas that are completely
925 : : // filled will likely be skipped (the gc_last_free_atb_index
926 : : // points to the last block).
927 : : // The reason why this is necessary is because it is not possible
928 : : // to see which area came first (like it is possible to adjust
929 : : // gc_last_free_atb_index based on whether the freed block is
930 : : // before the last free block).
931 : 649 : MP_STATE_MEM(gc_last_free_area) = &MP_STATE_MEM(area);
932 : : }
933 : : #endif
934 : :
935 : : // set the last_free pointer to this block if it's earlier in the heap
936 [ + + ]: 629699 : if (block / BLOCKS_PER_ATB < area->gc_last_free_atb_index) {
937 : 92689 : area->gc_last_free_atb_index = block / BLOCKS_PER_ATB;
938 : : }
939 : :
940 : : // free head and all of its tail blocks
941 : 3064561 : do {
942 : 3064561 : ATB_ANY_TO_FREE(area, block);
943 : 3064561 : block += 1;
944 [ + + ]: 3064561 : } while (ATB_GET_KIND(area, block) == AT_TAIL);
945 : :
946 : 629699 : GC_EXIT();
947 : :
948 : : #if EXTENSIVE_HEAP_PROFILING
949 : : gc_dump_alloc_table(&mp_plat_print);
950 : : #endif
951 : : }
952 : :
953 : 26 : size_t gc_nbytes(const void *ptr) {
954 : 26 : GC_ENTER();
955 : :
956 : 26 : mp_state_mem_area_t *area;
957 : : #if MICROPY_GC_SPLIT_HEAP
958 [ + - ]: 26 : area = gc_get_ptr_area(ptr);
959 : : #else
960 : : if (VERIFY_PTR(ptr)) {
961 : : area = &MP_STATE_MEM(area);
962 : : } else {
963 : : area = NULL;
964 : : }
965 : : #endif
966 : :
967 [ + + ]: 26 : if (area) {
968 : 24 : size_t block = BLOCK_FROM_PTR(area, ptr);
969 [ + - ]: 24 : if (ATB_GET_KIND(area, block) == AT_HEAD) {
970 : : // work out number of consecutive blocks in the chain starting with this on
971 : : size_t n_blocks = 0;
972 : 152 : do {
973 : 152 : n_blocks += 1;
974 [ + + ]: 152 : } while (ATB_GET_KIND(area, block + n_blocks) == AT_TAIL);
975 : 24 : GC_EXIT();
976 : 24 : return n_blocks * BYTES_PER_BLOCK;
977 : : }
978 : : }
979 : :
980 : : // invalid pointer
981 : 2 : GC_EXIT();
982 : 2 : return 0;
983 : : }
984 : :
985 : 536770 : void *gc_realloc(void *ptr_in, size_t n_bytes, bool allow_move) {
986 : : // check for pure allocation
987 [ + + ]: 536770 : if (ptr_in == NULL) {
988 : 35667 : return gc_alloc(n_bytes, false);
989 : : }
990 : :
991 : : // check for pure free
992 [ + + ]: 501103 : if (n_bytes == 0) {
993 : 2 : gc_free(ptr_in);
994 : 2 : return NULL;
995 : : }
996 : :
997 [ + + ]: 501101 : if (MP_STATE_THREAD(gc_lock_depth) > 0) {
998 : : return NULL;
999 : : }
1000 : :
1001 : 501075 : void *ptr = ptr_in;
1002 : :
1003 : 501075 : GC_ENTER();
1004 : :
1005 : : // get the GC block number corresponding to this pointer
1006 : 501075 : mp_state_mem_area_t *area;
1007 : : #if MICROPY_GC_SPLIT_HEAP
1008 [ + - ]: 501075 : area = gc_get_ptr_area(ptr);
1009 [ - + ]: 501075 : assert(area);
1010 : : #else
1011 : : assert(VERIFY_PTR(ptr));
1012 : : area = &MP_STATE_MEM(area);
1013 : : #endif
1014 : 501075 : size_t block = BLOCK_FROM_PTR(area, ptr);
1015 [ - + ]: 501075 : assert(ATB_GET_KIND(area, block) == AT_HEAD);
1016 : :
1017 : : // compute number of new blocks that are requested
1018 : 501075 : size_t new_blocks = (n_bytes + BYTES_PER_BLOCK - 1) / BYTES_PER_BLOCK;
1019 : :
1020 : : // Get the total number of consecutive blocks that are already allocated to
1021 : : // this chunk of memory, and then count the number of free blocks following
1022 : : // it. Stop if we reach the end of the heap, or if we find enough extra
1023 : : // free blocks to satisfy the realloc. Note that we need to compute the
1024 : : // total size of the existing memory chunk so we can correctly and
1025 : : // efficiently shrink it (see below for shrinking code).
1026 : 501075 : size_t n_free = 0;
1027 : 501075 : size_t n_blocks = 1; // counting HEAD block
1028 : 501075 : size_t max_block = area->gc_alloc_table_byte_len * BLOCKS_PER_ATB;
1029 [ + + ]: 9707852 : for (size_t bl = block + n_blocks; bl < max_block; bl++) {
1030 : 9707823 : byte block_type = ATB_GET_KIND(area, bl);
1031 [ + + ]: 9707823 : if (block_type == AT_TAIL) {
1032 : 9072889 : n_blocks++;
1033 : 9072889 : continue;
1034 : : }
1035 [ + + ]: 634934 : if (block_type == AT_FREE) {
1036 : 561618 : n_free++;
1037 [ + + ]: 561618 : if (n_blocks + n_free >= new_blocks) {
1038 : : // stop as soon as we find enough blocks for n_bytes
1039 : : break;
1040 : : }
1041 : 133888 : continue;
1042 : : }
1043 : : break;
1044 : : }
1045 : :
1046 : : // return original ptr if it already has the requested number of blocks
1047 [ + + ]: 501075 : if (new_blocks == n_blocks) {
1048 : 271661 : GC_EXIT();
1049 : 271661 : return ptr_in;
1050 : : }
1051 : :
1052 : : // check if we can shrink the allocated area
1053 [ + + ]: 229414 : if (new_blocks < n_blocks) {
1054 : : // free unneeded tail blocks
1055 [ + + ]: 51249 : for (size_t bl = block + new_blocks, count = n_blocks - new_blocks; count > 0; bl++, count--) {
1056 : 26753 : ATB_ANY_TO_FREE(area, bl);
1057 : : }
1058 : :
1059 : : #if MICROPY_GC_SPLIT_HEAP
1060 [ + + ]: 24496 : if (MP_STATE_MEM(gc_last_free_area) != area) {
1061 : : // See comment in gc_free.
1062 : 38 : MP_STATE_MEM(gc_last_free_area) = &MP_STATE_MEM(area);
1063 : : }
1064 : : #endif
1065 : :
1066 : : // set the last_free pointer to end of this block if it's earlier in the heap
1067 [ + + ]: 24496 : if ((block + new_blocks) / BLOCKS_PER_ATB < area->gc_last_free_atb_index) {
1068 : 902 : area->gc_last_free_atb_index = (block + new_blocks) / BLOCKS_PER_ATB;
1069 : : }
1070 : :
1071 : 24496 : GC_EXIT();
1072 : :
1073 : : #if EXTENSIVE_HEAP_PROFILING
1074 : : gc_dump_alloc_table(&mp_plat_print);
1075 : : #endif
1076 : :
1077 : 24496 : return ptr_in;
1078 : : }
1079 : :
1080 : : // check if we can expand in place
1081 [ + + ]: 204918 : if (new_blocks <= n_blocks + n_free) {
1082 : : // mark few more blocks as used tail
1083 : 171125 : size_t end_block = block + new_blocks;
1084 [ + + ]: 420883 : for (size_t bl = block + n_blocks; bl < end_block; bl++) {
1085 [ - + ]: 249758 : assert(ATB_GET_KIND(area, bl) == AT_FREE);
1086 : 249758 : ATB_FREE_TO_TAIL(area, bl);
1087 : : }
1088 : :
1089 : 171125 : area->gc_last_used_block = MAX(area->gc_last_used_block, end_block);
1090 : :
1091 : 171125 : GC_EXIT();
1092 : :
1093 : : #if MICROPY_GC_CONSERVATIVE_CLEAR
1094 : : // be conservative and zero out all the newly allocated blocks
1095 : 171125 : memset((byte *)ptr_in + n_blocks * BYTES_PER_BLOCK, 0, (new_blocks - n_blocks) * BYTES_PER_BLOCK);
1096 : : #else
1097 : : // zero out the additional bytes of the newly allocated blocks (see comment above in gc_alloc)
1098 : : memset((byte *)ptr_in + n_bytes, 0, new_blocks * BYTES_PER_BLOCK - n_bytes);
1099 : : #endif
1100 : :
1101 : : #if EXTENSIVE_HEAP_PROFILING
1102 : : gc_dump_alloc_table(&mp_plat_print);
1103 : : #endif
1104 : :
1105 : 171125 : return ptr_in;
1106 : : }
1107 : :
1108 : : #if MICROPY_ENABLE_FINALISER
1109 : 33793 : bool ftb_state = FTB_GET(area, block);
1110 : : #else
1111 : : bool ftb_state = false;
1112 : : #endif
1113 : :
1114 : 33793 : GC_EXIT();
1115 : :
1116 [ + + ]: 33793 : if (!allow_move) {
1117 : : // not allowed to move memory block so return failure
1118 : : return NULL;
1119 : : }
1120 : :
1121 : : // can't resize inplace; try to find a new contiguous chain
1122 : 20927 : void *ptr_out = gc_alloc(n_bytes, ftb_state);
1123 : :
1124 : : // check that the alloc succeeded
1125 [ + + ]: 20927 : if (ptr_out == NULL) {
1126 : : return NULL;
1127 : : }
1128 : :
1129 : 20919 : DEBUG_printf("gc_realloc(%p -> %p)\n", ptr_in, ptr_out);
1130 : 20919 : memcpy(ptr_out, ptr_in, n_blocks * BYTES_PER_BLOCK);
1131 : 20919 : gc_free(ptr_in);
1132 : 20919 : return ptr_out;
1133 : : }
1134 : :
1135 : 18 : void gc_dump_info(const mp_print_t *print) {
1136 : 18 : gc_info_t info;
1137 : 18 : gc_info(&info);
1138 : 18 : mp_printf(print, "GC: total: %u, used: %u, free: %u",
1139 : 18 : (uint)info.total, (uint)info.used, (uint)info.free);
1140 : : #if MICROPY_GC_SPLIT_HEAP_AUTO
1141 : : mp_printf(print, ", max new split: %u", (uint)info.max_new_split);
1142 : : #endif
1143 : 18 : mp_printf(print, "\n No. of 1-blocks: %u, 2-blocks: %u, max blk sz: %u, max free sz: %u\n",
1144 : 18 : (uint)info.num_1block, (uint)info.num_2block, (uint)info.max_block, (uint)info.max_free);
1145 : 18 : }
1146 : :
1147 : 4 : void gc_dump_alloc_table(const mp_print_t *print) {
1148 : 4 : GC_ENTER();
1149 : 4 : static const size_t DUMP_BYTES_PER_LINE = 64;
1150 [ + + ]: 20 : for (mp_state_mem_area_t *area = &MP_STATE_MEM(area); area != NULL; area = NEXT_AREA(area)) {
1151 : : #if !EXTENSIVE_HEAP_PROFILING
1152 : : // When comparing heap output we don't want to print the starting
1153 : : // pointer of the heap because it changes from run to run.
1154 : 16 : mp_printf(print, "GC memory layout; from %p:", area->gc_pool_start);
1155 : : #endif
1156 [ + + ]: 1248 : for (size_t bl = 0; bl < area->gc_alloc_table_byte_len * BLOCKS_PER_ATB; bl++) {
1157 [ + + ]: 1236 : if (bl % DUMP_BYTES_PER_LINE == 0) {
1158 : : // a new line of blocks
1159 : : {
1160 : : // check if this line contains only free blocks
1161 : : size_t bl2 = bl;
1162 [ + + + + ]: 258608 : while (bl2 < area->gc_alloc_table_byte_len * BLOCKS_PER_ATB && ATB_GET_KIND(area, bl2) == AT_FREE) {
1163 : 258584 : bl2++;
1164 : : }
1165 [ + + ]: 24 : if (bl2 - bl >= 2 * DUMP_BYTES_PER_LINE) {
1166 : : // there are at least 2 lines containing only free blocks, so abbreviate their printing
1167 : 16 : mp_printf(print, "\n (%u lines all free)", (uint)(bl2 - bl) / DUMP_BYTES_PER_LINE);
1168 : 16 : bl = bl2 & (~(DUMP_BYTES_PER_LINE - 1));
1169 [ + + ]: 16 : if (bl >= area->gc_alloc_table_byte_len * BLOCKS_PER_ATB) {
1170 : : // got to end of heap
1171 : : break;
1172 : : }
1173 : : }
1174 : : }
1175 : : // print header for new line of blocks
1176 : : // (the cast to uint32_t is for 16-bit ports)
1177 : 20 : mp_printf(print, "\n%08x: ", (uint)(bl * BYTES_PER_BLOCK));
1178 : : }
1179 : 1232 : int c = ' ';
1180 [ + + - + ]: 1232 : switch (ATB_GET_KIND(area, bl)) {
1181 : : case AT_FREE:
1182 : : c = '.';
1183 : : break;
1184 : : /* this prints out if the object is reachable from BSS or STACK (for unix only)
1185 : : case AT_HEAD: {
1186 : : c = 'h';
1187 : : void **ptrs = (void**)(void*)&mp_state_ctx;
1188 : : mp_uint_t len = offsetof(mp_state_ctx_t, vm.stack_top) / sizeof(mp_uint_t);
1189 : : for (mp_uint_t i = 0; i < len; i++) {
1190 : : mp_uint_t ptr = (mp_uint_t)ptrs[i];
1191 : : if (gc_get_ptr_area(ptr) && BLOCK_FROM_PTR(ptr) == bl) {
1192 : : c = 'B';
1193 : : break;
1194 : : }
1195 : : }
1196 : : if (c == 'h') {
1197 : : ptrs = (void**)&c;
1198 : : len = ((mp_uint_t)MP_STATE_THREAD(stack_top) - (mp_uint_t)&c) / sizeof(mp_uint_t);
1199 : : for (mp_uint_t i = 0; i < len; i++) {
1200 : : mp_uint_t ptr = (mp_uint_t)ptrs[i];
1201 : : if (gc_get_ptr_area(ptr) && BLOCK_FROM_PTR(ptr) == bl) {
1202 : : c = 'S';
1203 : : break;
1204 : : }
1205 : : }
1206 : : }
1207 : : break;
1208 : : }
1209 : : */
1210 : : /* this prints the uPy object type of the head block */
1211 : 76 : case AT_HEAD: {
1212 : 76 : void **ptr = (void **)(area->gc_pool_start + bl * BYTES_PER_BLOCK);
1213 [ + - ]: 76 : if (*ptr == &mp_type_tuple) {
1214 : : c = 'T';
1215 [ + + ]: 76 : } else if (*ptr == &mp_type_list) {
1216 : : c = 'L';
1217 [ + - ]: 72 : } else if (*ptr == &mp_type_dict) {
1218 : : c = 'D';
1219 [ + - + - ]: 72 : } else if (*ptr == &mp_type_str || *ptr == &mp_type_bytes) {
1220 : : c = 'S';
1221 : : }
1222 : : #if MICROPY_PY_BUILTINS_BYTEARRAY
1223 [ + - ]: 72 : else if (*ptr == &mp_type_bytearray) {
1224 : : c = 'A';
1225 : : }
1226 : : #endif
1227 : : #if MICROPY_PY_ARRAY
1228 [ + - ]: 72 : else if (*ptr == &mp_type_array) {
1229 : : c = 'A';
1230 : : }
1231 : : #endif
1232 : : #if MICROPY_PY_BUILTINS_FLOAT
1233 [ + - ]: 72 : else if (*ptr == &mp_type_float) {
1234 : : c = 'F';
1235 : : }
1236 : : #endif
1237 [ + + ]: 72 : else if (*ptr == &mp_type_fun_bc) {
1238 : : c = 'B';
1239 [ + - ]: 68 : } else if (*ptr == &mp_type_module) {
1240 : : c = 'M';
1241 : : } else {
1242 : 68 : c = 'h';
1243 : : #if 0
1244 : : // This code prints "Q" for qstr-pool data, and "q" for qstr-str
1245 : : // data. It can be useful to see how qstrs are being allocated,
1246 : : // but is disabled by default because it is very slow.
1247 : : for (qstr_pool_t *pool = MP_STATE_VM(last_pool); c == 'h' && pool != NULL; pool = pool->prev) {
1248 : : if ((qstr_pool_t *)ptr == pool) {
1249 : : c = 'Q';
1250 : : break;
1251 : : }
1252 : : for (const byte **q = pool->qstrs, **q_top = pool->qstrs + pool->len; q < q_top; q++) {
1253 : : if ((const byte *)ptr == *q) {
1254 : : c = 'q';
1255 : : break;
1256 : : }
1257 : : }
1258 : : }
1259 : : #endif
1260 : : }
1261 : : break;
1262 : : }
1263 : 92 : case AT_TAIL:
1264 : 92 : c = '=';
1265 : 92 : break;
1266 : 0 : case AT_MARK:
1267 : 0 : c = 'm';
1268 : 0 : break;
1269 : : }
1270 : 1232 : mp_printf(print, "%c", c);
1271 : : }
1272 : 16 : mp_print_str(print, "\n");
1273 : : }
1274 : 4 : GC_EXIT();
1275 : 4 : }
1276 : :
1277 : : #endif // MICROPY_ENABLE_GC
|
