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