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 : 16992 : 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 : 16992 : size_t total_byte_len = (byte *)end - (byte *)start;
131 : : #if MICROPY_ENABLE_FINALISER
132 : 16992 : area->gc_alloc_table_byte_len = (total_byte_len - ALLOC_TABLE_GAP_BYTE) * MP_BITS_PER_BYTE / (MP_BITS_PER_BYTE + MP_BITS_PER_BYTE * BLOCKS_PER_ATB / BLOCKS_PER_FTB + MP_BITS_PER_BYTE * BLOCKS_PER_ATB * BYTES_PER_BLOCK);
133 : : #else
134 : : area->gc_alloc_table_byte_len = (total_byte_len - ALLOC_TABLE_GAP_BYTE) / (1 + MP_BITS_PER_BYTE / 2 * BYTES_PER_BLOCK);
135 : : #endif
136 : :
137 : 16992 : area->gc_alloc_table_start = (byte *)start;
138 : :
139 : : #if MICROPY_ENABLE_FINALISER
140 : 16992 : size_t gc_finaliser_table_byte_len = (area->gc_alloc_table_byte_len * BLOCKS_PER_ATB + BLOCKS_PER_FTB - 1) / BLOCKS_PER_FTB;
141 : 16992 : area->gc_finaliser_table_start = area->gc_alloc_table_start + area->gc_alloc_table_byte_len + ALLOC_TABLE_GAP_BYTE;
142 : : #endif
143 : :
144 : 16992 : size_t gc_pool_block_len = area->gc_alloc_table_byte_len * BLOCKS_PER_ATB;
145 : 16992 : area->gc_pool_start = (byte *)end - gc_pool_block_len * BYTES_PER_BLOCK;
146 : 16992 : area->gc_pool_end = end;
147 : :
148 : : #if MICROPY_ENABLE_FINALISER
149 [ - + ]: 16992 : assert(area->gc_pool_start >= area->gc_finaliser_table_start + gc_finaliser_table_byte_len);
150 : : #endif
151 : :
152 : : #if MICROPY_ENABLE_FINALISER
153 : : // clear ATBs and FTBs
154 : 16992 : memset(area->gc_alloc_table_start, 0, gc_finaliser_table_byte_len + area->gc_alloc_table_byte_len + ALLOC_TABLE_GAP_BYTE);
155 : : #else
156 : : // clear ATBs
157 : : memset(area->gc_alloc_table_start, 0, area->gc_alloc_table_byte_len + ALLOC_TABLE_GAP_BYTE);
158 : : #endif
159 : :
160 : 16992 : area->gc_last_free_atb_index = 0;
161 : :
162 : : #if MICROPY_GC_SPLIT_HEAP
163 : 16992 : area->next = NULL;
164 : : #endif
165 : :
166 : 16992 : DEBUG_printf("GC layout:\n");
167 : 16992 : DEBUG_printf(" alloc table at %p, length " UINT_FMT " bytes, " UINT_FMT " blocks\n", MP_STATE_MEM(area).gc_alloc_table_start, MP_STATE_MEM(area).gc_alloc_table_byte_len, MP_STATE_MEM(area).gc_alloc_table_byte_len * BLOCKS_PER_ATB);
168 : : #if MICROPY_ENABLE_FINALISER
169 : 16992 : DEBUG_printf(" finaliser table at %p, length " UINT_FMT " bytes, " UINT_FMT " blocks\n", MP_STATE_MEM(area).gc_finaliser_table_start, gc_finaliser_table_byte_len, gc_finaliser_table_byte_len * BLOCKS_PER_FTB);
170 : : #endif
171 : 16992 : DEBUG_printf(" pool at %p, length " UINT_FMT " bytes, " UINT_FMT " blocks\n", MP_STATE_MEM(area).gc_pool_start, gc_pool_block_len * BYTES_PER_BLOCK, gc_pool_block_len);
172 : 16992 : }
173 : :
174 : 7320 : void gc_init(void *start, void *end) {
175 : : // align end pointer on block boundary
176 : 7320 : end = (void *)((uintptr_t)end & (~(BYTES_PER_BLOCK - 1)));
177 : 7320 : DEBUG_printf("Initializing GC heap: %p..%p = " UINT_FMT " bytes\n", start, end, (byte *)end - (byte *)start);
178 : :
179 : 7320 : gc_setup_area(&MP_STATE_MEM(area), start, end);
180 : :
181 : : // set last free ATB index to start of heap
182 : : #if MICROPY_GC_SPLIT_HEAP
183 : 7320 : MP_STATE_MEM(gc_last_free_area) = &MP_STATE_MEM(area);
184 : : #endif
185 : :
186 : : // unlock the GC
187 : 7320 : MP_STATE_THREAD(gc_lock_depth) = 0;
188 : :
189 : : // allow auto collection
190 : 7320 : MP_STATE_MEM(gc_auto_collect_enabled) = 1;
191 : :
192 : : #if MICROPY_GC_ALLOC_THRESHOLD
193 : : // by default, maxuint for gc threshold, effectively turning gc-by-threshold off
194 : 7320 : MP_STATE_MEM(gc_alloc_threshold) = (size_t)-1;
195 : 7320 : MP_STATE_MEM(gc_alloc_amount) = 0;
196 : : #endif
197 : :
198 : : #if MICROPY_PY_THREAD && !MICROPY_PY_THREAD_GIL
199 : 7320 : mp_thread_mutex_init(&MP_STATE_MEM(gc_mutex));
200 : : #endif
201 : 7320 : }
202 : :
203 : : #if MICROPY_GC_SPLIT_HEAP
204 : 9672 : void gc_add(void *start, void *end) {
205 : : // Place the area struct at the start of the area.
206 : 9672 : mp_state_mem_area_t *area = (mp_state_mem_area_t *)start;
207 : 9672 : start = (void *)((uintptr_t)start + sizeof(mp_state_mem_area_t));
208 : :
209 : 9672 : end = (void *)((uintptr_t)end & (~(BYTES_PER_BLOCK - 1)));
210 : 9672 : DEBUG_printf("Adding GC heap: %p..%p = " UINT_FMT " bytes\n", start, end, (byte *)end - (byte *)start);
211 : :
212 : : // Init this area
213 : 9672 : gc_setup_area(area, start, end);
214 : :
215 : : // Find the last registered area in the linked list
216 : 9672 : mp_state_mem_area_t *prev_area = &MP_STATE_MEM(area);
217 [ + + ]: 19344 : while (prev_area->next != NULL) {
218 : : prev_area = prev_area->next;
219 : : }
220 : :
221 : : // Add this area to the linked list
222 : 9672 : prev_area->next = area;
223 : 9672 : }
224 : : #endif
225 : :
226 : 233 : void gc_lock(void) {
227 : : // This does not need to be atomic or have the GC mutex because:
228 : : // - each thread has its own gc_lock_depth so there are no races between threads;
229 : : // - a hard interrupt will only change gc_lock_depth during its execution, and
230 : : // upon return will restore the value of gc_lock_depth.
231 : 233 : MP_STATE_THREAD(gc_lock_depth)++;
232 : 233 : }
233 : :
234 : 233 : void gc_unlock(void) {
235 : : // This does not need to be atomic, See comment above in gc_lock.
236 : 233 : MP_STATE_THREAD(gc_lock_depth)--;
237 : 233 : }
238 : :
239 : 110 : bool gc_is_locked(void) {
240 : 110 : return MP_STATE_THREAD(gc_lock_depth) != 0;
241 : : }
242 : :
243 : : #if MICROPY_GC_SPLIT_HEAP
244 : : // Returns the area to which this pointer belongs, or NULL if it isn't
245 : : // allocated on the GC-managed heap.
246 : 29087368 : STATIC inline mp_state_mem_area_t *gc_get_ptr_area(const void *ptr) {
247 : 29087368 : if (((uintptr_t)(ptr) & (BYTES_PER_BLOCK - 1)) != 0) { // must be aligned on a block
248 : : return NULL;
249 : : }
250 [ + - + + : 59429593 : for (mp_state_mem_area_t *area = &MP_STATE_MEM(area); area != NULL; area = NEXT_AREA(area)) {
+ - + + +
+ ]
251 [ + + + + : 43256831 : if (ptr >= (void *)area->gc_pool_start // must be above start of pool
+ + + + +
+ ]
252 [ - + - + : 7146400 : && ptr < (void *)area->gc_pool_end) { // must be below end of pool
- + + + +
+ ]
253 : : return area;
254 : : }
255 : : }
256 : : return NULL;
257 : : }
258 : : #endif
259 : :
260 : : // ptr should be of type void*
261 : : #define VERIFY_PTR(ptr) ( \
262 : : ((uintptr_t)(ptr) & (BYTES_PER_BLOCK - 1)) == 0 /* must be aligned on a block */ \
263 : : && ptr >= (void *)MP_STATE_MEM(area).gc_pool_start /* must be above start of pool */ \
264 : : && ptr < (void *)MP_STATE_MEM(area).gc_pool_end /* must be below end of pool */ \
265 : : )
266 : :
267 : : #ifndef TRACE_MARK
268 : : #if DEBUG_PRINT
269 : : #define TRACE_MARK(block, ptr) DEBUG_printf("gc_mark(%p)\n", ptr)
270 : : #else
271 : : #define TRACE_MARK(block, ptr)
272 : : #endif
273 : : #endif
274 : :
275 : : // Take the given block as the topmost block on the stack. Check all it's
276 : : // children: mark the unmarked child blocks and put those newly marked
277 : : // blocks on the stack. When all children have been checked, pop off the
278 : : // topmost block on the stack and repeat with that one.
279 : : #if MICROPY_GC_SPLIT_HEAP
280 : 19854 : STATIC void gc_mark_subtree(mp_state_mem_area_t *area, size_t block)
281 : : #else
282 : : STATIC void gc_mark_subtree(size_t block)
283 : : #endif
284 : : {
285 : : // Start with the block passed in the argument.
286 : 19854 : size_t sp = 0;
287 : 8362126 : for (;;) {
288 : : MICROPY_GC_HOOK_LOOP
289 : :
290 : : #if !MICROPY_GC_SPLIT_HEAP
291 : : mp_state_mem_area_t * area = &MP_STATE_MEM(area);
292 : : #endif
293 : :
294 : : // work out number of consecutive blocks in the chain starting with this one
295 : 4190990 : size_t n_blocks = 0;
296 : 4377804 : do {
297 : 4377804 : n_blocks += 1;
298 [ + + ]: 4377804 : } while (ATB_GET_KIND(area, block + n_blocks) == AT_TAIL);
299 : :
300 : : // check that the consecutive blocks didn't overflow past the end of the area
301 [ - + ]: 4190990 : assert(area->gc_pool_start + (block + n_blocks) * BYTES_PER_BLOCK <= area->gc_pool_end);
302 : :
303 : : // check this block's children
304 : 4190990 : void **ptrs = (void **)PTR_FROM_BLOCK(area, block);
305 [ + + ]: 21702206 : for (size_t i = n_blocks * BYTES_PER_BLOCK / sizeof(void *); i > 0; i--, ptrs++) {
306 : : MICROPY_GC_HOOK_LOOP
307 : 17511216 : void *ptr = *ptrs;
308 : : // If this is a heap pointer that hasn't been marked, mark it and push
309 : : // it's children to the stack.
310 : : #if MICROPY_GC_SPLIT_HEAP
311 [ + + ]: 17511216 : mp_state_mem_area_t *ptr_area = gc_get_ptr_area(ptr);
312 [ + + ]: 14539305 : if (!ptr_area) {
313 : : // Not a heap-allocated pointer (might even be random data).
314 : 13333979 : continue;
315 : : }
316 : : #else
317 : : if (!VERIFY_PTR(ptr)) {
318 : : continue;
319 : : }
320 : : mp_state_mem_area_t *ptr_area = area;
321 : : #endif
322 : 4177237 : size_t ptr_block = BLOCK_FROM_PTR(ptr_area, ptr);
323 [ + + ]: 4177237 : if (ATB_GET_KIND(ptr_area, ptr_block) != AT_HEAD) {
324 : : // This block is already marked.
325 : 5547 : continue;
326 : : }
327 : : // An unmarked head. Mark it, and push it on gc stack.
328 : 4171690 : TRACE_MARK(ptr_block, ptr);
329 : 4171690 : ATB_HEAD_TO_MARK(ptr_area, ptr_block);
330 [ + + ]: 4171690 : if (sp < MICROPY_ALLOC_GC_STACK_SIZE) {
331 : 4171136 : MP_STATE_MEM(gc_block_stack)[sp] = ptr_block;
332 : : #if MICROPY_GC_SPLIT_HEAP
333 : 4171136 : MP_STATE_MEM(gc_area_stack)[sp] = ptr_area;
334 : : #endif
335 : 4171136 : sp += 1;
336 : : } else {
337 : 554 : MP_STATE_MEM(gc_stack_overflow) = 1;
338 : : }
339 : : }
340 : :
341 : : // Are there any blocks on the stack?
342 [ + + ]: 4190990 : if (sp == 0) {
343 : : break; // No, stack is empty, we're done.
344 : : }
345 : :
346 : : // pop the next block off the stack
347 : 4171136 : sp -= 1;
348 : 4171136 : block = MP_STATE_MEM(gc_block_stack)[sp];
349 : : #if MICROPY_GC_SPLIT_HEAP
350 : 4171136 : area = MP_STATE_MEM(gc_area_stack)[sp];
351 : : #endif
352 : : }
353 : 19854 : }
354 : :
355 : 15928 : STATIC void gc_deal_with_stack_overflow(void) {
356 [ + + ]: 15933 : while (MP_STATE_MEM(gc_stack_overflow)) {
357 : 5 : MP_STATE_MEM(gc_stack_overflow) = 0;
358 : :
359 : : // scan entire memory looking for blocks which have been marked but not their children
360 [ + + ]: 25 : for (mp_state_mem_area_t *area = &MP_STATE_MEM(area); area != NULL; area = NEXT_AREA(area)) {
361 [ + + ]: 323800 : for (size_t block = 0; block < area->gc_alloc_table_byte_len * BLOCKS_PER_ATB; block++) {
362 : : MICROPY_GC_HOOK_LOOP
363 : : // trace (again) if mark bit set
364 [ + + ]: 323780 : if (ATB_GET_KIND(area, block) == AT_MARK) {
365 : : #if MICROPY_GC_SPLIT_HEAP
366 : 2971 : gc_mark_subtree(area, block);
367 : : #else
368 : : gc_mark_subtree(block);
369 : : #endif
370 : : }
371 : : }
372 : : }
373 : : }
374 : 15928 : }
375 : :
376 : 15928 : STATIC void gc_sweep(void) {
377 : : #if MICROPY_PY_GC_COLLECT_RETVAL
378 : 15928 : MP_STATE_MEM(gc_collected) = 0;
379 : : #endif
380 : : // free unmarked heads and their tails
381 : 15928 : int free_tail = 0;
382 [ + + ]: 42776 : for (mp_state_mem_area_t *area = &MP_STATE_MEM(area); area != NULL; area = NEXT_AREA(area)) {
383 [ + + ]: 237262400 : for (size_t block = 0; block < area->gc_alloc_table_byte_len * BLOCKS_PER_ATB; block++) {
384 : : MICROPY_GC_HOOK_LOOP
385 [ + + + + ]: 237235552 : switch (ATB_GET_KIND(area, block)) {
386 : 2672932 : case AT_HEAD:
387 : : #if MICROPY_ENABLE_FINALISER
388 [ + + ]: 2672932 : if (FTB_GET(area, block)) {
389 : 4060 : mp_obj_base_t *obj = (mp_obj_base_t *)PTR_FROM_BLOCK(area, block);
390 [ + - ]: 4060 : if (obj->type != NULL) {
391 : : // if the object has a type then see if it has a __del__ method
392 : 4060 : mp_obj_t dest[2];
393 : 4060 : mp_load_method_maybe(MP_OBJ_FROM_PTR(obj), MP_QSTR___del__, dest);
394 [ + - ]: 4060 : if (dest[0] != MP_OBJ_NULL) {
395 : : // load_method returned a method, execute it in a protected environment
396 : : #if MICROPY_ENABLE_SCHEDULER
397 : 4060 : mp_sched_lock();
398 : : #endif
399 : 4060 : mp_call_function_1_protected(dest[0], dest[1]);
400 : : #if MICROPY_ENABLE_SCHEDULER
401 : 4060 : mp_sched_unlock();
402 : : #endif
403 : : }
404 : : }
405 : : // clear finaliser flag
406 : 4060 : FTB_CLEAR(area, block);
407 : : }
408 : : #endif
409 : 2672932 : free_tail = 1;
410 : 2672932 : DEBUG_printf("gc_sweep(%p)\n", (void *)PTR_FROM_BLOCK(area, block));
411 : : #if MICROPY_PY_GC_COLLECT_RETVAL
412 : 2672932 : MP_STATE_MEM(gc_collected)++;
413 : : #endif
414 : : // fall through to free the head
415 : 3645892 : MP_FALLTHROUGH
416 : :
417 : 972960 : case AT_TAIL:
418 [ + + ]: 3645892 : if (free_tail) {
419 : 3459799 : ATB_ANY_TO_FREE(area, block);
420 : : #if CLEAR_ON_SWEEP
421 : : memset((void *)PTR_FROM_BLOCK(area, block), 0, BYTES_PER_BLOCK);
422 : : #endif
423 : : }
424 : : break;
425 : :
426 : 4188573 : case AT_MARK:
427 : 4188573 : ATB_MARK_TO_HEAD(area, block);
428 : 4188573 : free_tail = 0;
429 : 4188573 : break;
430 : : }
431 : : }
432 : : }
433 : 15928 : }
434 : :
435 : 12707 : void gc_collect_start(void) {
436 : 12707 : GC_ENTER();
437 : 12708 : MP_STATE_THREAD(gc_lock_depth)++;
438 : : #if MICROPY_GC_ALLOC_THRESHOLD
439 : 12708 : MP_STATE_MEM(gc_alloc_amount) = 0;
440 : : #endif
441 : 12708 : MP_STATE_MEM(gc_stack_overflow) = 0;
442 : :
443 : : // Trace root pointers. This relies on the root pointers being organised
444 : : // correctly in the mp_state_ctx structure. We scan nlr_top, dict_locals,
445 : : // dict_globals, then the root pointer section of mp_state_vm.
446 : 12708 : void **ptrs = (void **)(void *)&mp_state_ctx;
447 : 12708 : size_t root_start = offsetof(mp_state_ctx_t, thread.dict_locals);
448 : 12708 : size_t root_end = offsetof(mp_state_ctx_t, vm.qstr_last_chunk);
449 : 12708 : gc_collect_root(ptrs + root_start / sizeof(void *), (root_end - root_start) / sizeof(void *));
450 : :
451 : : #if MICROPY_ENABLE_PYSTACK
452 : : // Trace root pointers from the Python stack.
453 : : ptrs = (void **)(void *)MP_STATE_THREAD(pystack_start);
454 : : gc_collect_root(ptrs, (MP_STATE_THREAD(pystack_cur) - MP_STATE_THREAD(pystack_start)) / sizeof(void *));
455 : : #endif
456 : 12708 : }
457 : :
458 : : // Address sanitizer needs to know that the access to ptrs[i] must always be
459 : : // considered OK, even if it's a load from an address that would normally be
460 : : // prohibited (due to being undefined, in a red zone, etc).
461 : : #if defined(__GNUC__) && (__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 8))
462 : : __attribute__((no_sanitize_address))
463 : : #endif
464 : 10586192 : static void *gc_get_ptr(void **ptrs, int i) {
465 : : #if MICROPY_DEBUG_VALGRIND
466 : : if (!VALGRIND_CHECK_MEM_IS_ADDRESSABLE(&ptrs[i], sizeof(*ptrs))) {
467 : : return NULL;
468 : : }
469 : : #endif
470 : 10586192 : return ptrs[i];
471 : : }
472 : :
473 : 45134 : void gc_collect_root(void **ptrs, size_t len) {
474 : : #if !MICROPY_GC_SPLIT_HEAP
475 : : mp_state_mem_area_t *area = &MP_STATE_MEM(area);
476 : : #endif
477 [ + + ]: 10631326 : for (size_t i = 0; i < len; i++) {
478 : : MICROPY_GC_HOOK_LOOP
479 : 10586192 : void *ptr = gc_get_ptr(ptrs, i);
480 : : #if MICROPY_GC_SPLIT_HEAP
481 [ + + ]: 10586192 : mp_state_mem_area_t *area = gc_get_ptr_area(ptr);
482 [ + + ]: 5835889 : if (!area) {
483 : 10560995 : continue;
484 : : }
485 : : #else
486 : : if (!VERIFY_PTR(ptr)) {
487 : : continue;
488 : : }
489 : : #endif
490 : 25197 : size_t block = BLOCK_FROM_PTR(area, ptr);
491 [ + + ]: 25197 : if (ATB_GET_KIND(area, block) == AT_HEAD) {
492 : : // An unmarked head: mark it, and mark all its children
493 : 16883 : ATB_HEAD_TO_MARK(area, block);
494 : : #if MICROPY_GC_SPLIT_HEAP
495 : 16883 : gc_mark_subtree(area, block);
496 : : #else
497 : : gc_mark_subtree(block);
498 : : #endif
499 : : }
500 : : }
501 : 45134 : }
502 : :
503 : 15928 : void gc_collect_end(void) {
504 : 15928 : gc_deal_with_stack_overflow();
505 : 15928 : gc_sweep();
506 : : #if MICROPY_GC_SPLIT_HEAP
507 : 15928 : MP_STATE_MEM(gc_last_free_area) = &MP_STATE_MEM(area);
508 : : #endif
509 [ + + ]: 42776 : for (mp_state_mem_area_t *area = &MP_STATE_MEM(area); area != NULL; area = NEXT_AREA(area)) {
510 : 26848 : area->gc_last_free_atb_index = 0;
511 : : }
512 : 15928 : MP_STATE_THREAD(gc_lock_depth)--;
513 : 15928 : GC_EXIT();
514 : 15928 : }
515 : :
516 : 3220 : void gc_sweep_all(void) {
517 : 3220 : GC_ENTER();
518 : 3220 : MP_STATE_THREAD(gc_lock_depth)++;
519 : 3220 : MP_STATE_MEM(gc_stack_overflow) = 0;
520 : 3220 : gc_collect_end();
521 : 3220 : }
522 : :
523 : 26 : void gc_info(gc_info_t *info) {
524 : 26 : GC_ENTER();
525 : 26 : info->total = 0;
526 : 26 : info->used = 0;
527 : 26 : info->free = 0;
528 : 26 : info->max_free = 0;
529 : 26 : info->num_1block = 0;
530 : 26 : info->num_2block = 0;
531 : 26 : info->max_block = 0;
532 [ + + ]: 130 : for (mp_state_mem_area_t *area = &MP_STATE_MEM(area); area != NULL; area = NEXT_AREA(area)) {
533 : 104 : bool finish = false;
534 : 104 : info->total += area->gc_pool_end - area->gc_pool_start;
535 [ + + ]: 1683760 : for (size_t block = 0, len = 0, len_free = 0; !finish;) {
536 : 1683656 : size_t kind = ATB_GET_KIND(area, block);
537 [ + + + - ]: 1683656 : switch (kind) {
538 : 1682286 : case AT_FREE:
539 : 1682286 : info->free += 1;
540 : 1682286 : len_free += 1;
541 : 1682286 : len = 0;
542 : 1682286 : break;
543 : :
544 : 598 : case AT_HEAD:
545 : 598 : info->used += 1;
546 : 598 : len = 1;
547 : 598 : break;
548 : :
549 : 772 : case AT_TAIL:
550 : 772 : info->used += 1;
551 : 772 : len += 1;
552 : 772 : break;
553 : :
554 : : case AT_MARK:
555 : : // shouldn't happen
556 : : break;
557 : : }
558 : :
559 : 1683656 : block++;
560 : 1683656 : finish = (block == area->gc_alloc_table_byte_len * BLOCKS_PER_ATB);
561 : : // Get next block type if possible
562 [ + + ]: 1683656 : if (!finish) {
563 : 1683552 : kind = ATB_GET_KIND(area, block);
564 : : }
565 : :
566 [ + + + + ]: 1683656 : if (finish || kind == AT_FREE || kind == AT_HEAD) {
567 [ + + ]: 1682884 : if (len == 1) {
568 : 322 : info->num_1block += 1;
569 [ + + ]: 1682562 : } else if (len == 2) {
570 : 148 : info->num_2block += 1;
571 : : }
572 [ + + ]: 1682884 : if (len > info->max_block) {
573 : 82 : info->max_block = len;
574 : : }
575 [ + + ]: 1682884 : if (finish || kind == AT_HEAD) {
576 [ + + ]: 676 : if (len_free > info->max_free) {
577 : 124 : info->max_free = len_free;
578 : : }
579 : : len_free = 0;
580 : : }
581 : : }
582 : : }
583 : : }
584 : :
585 : 26 : info->used *= BYTES_PER_BLOCK;
586 : 26 : info->free *= BYTES_PER_BLOCK;
587 : 26 : GC_EXIT();
588 : 26 : }
589 : :
590 : 3716748 : void *gc_alloc(size_t n_bytes, unsigned int alloc_flags) {
591 : 3716748 : bool has_finaliser = alloc_flags & GC_ALLOC_FLAG_HAS_FINALISER;
592 : 3716748 : size_t n_blocks = ((n_bytes + BYTES_PER_BLOCK - 1) & (~(BYTES_PER_BLOCK - 1))) / BYTES_PER_BLOCK;
593 : 3716748 : DEBUG_printf("gc_alloc(" UINT_FMT " bytes -> " UINT_FMT " blocks)\n", n_bytes, n_blocks);
594 : :
595 : : // check for 0 allocation
596 [ + + ]: 3716748 : if (n_blocks == 0) {
597 : : return NULL;
598 : : }
599 : :
600 : : // check if GC is locked
601 [ + + ]: 3712214 : if (MP_STATE_THREAD(gc_lock_depth) > 0) {
602 : : return NULL;
603 : : }
604 : :
605 : 3711638 : GC_ENTER();
606 : :
607 : 3713170 : mp_state_mem_area_t *area;
608 : 3713170 : size_t i;
609 : 3713170 : size_t end_block;
610 : 3713170 : size_t start_block;
611 : 3713170 : size_t n_free;
612 : 3713170 : int collected = !MP_STATE_MEM(gc_auto_collect_enabled);
613 : :
614 : : #if MICROPY_GC_ALLOC_THRESHOLD
615 [ + + + + ]: 3713170 : if (!collected && MP_STATE_MEM(gc_alloc_amount) >= MP_STATE_MEM(gc_alloc_threshold)) {
616 : 24 : GC_EXIT();
617 : 24 : gc_collect();
618 : 24 : collected = 1;
619 : 24 : GC_ENTER();
620 : : }
621 : : #endif
622 : :
623 : 3729714 : for (;;) {
624 : :
625 : : #if MICROPY_GC_SPLIT_HEAP
626 : 3721442 : area = MP_STATE_MEM(gc_last_free_area);
627 : : #else
628 : : area = &MP_STATE_MEM(area);
629 : : #endif
630 : :
631 : : // look for a run of n_blocks available blocks
632 [ + + ]: 3742098 : for (; area != NULL; area = NEXT_AREA(area), i = 0) {
633 : 3729685 : n_free = 0;
634 [ + + ]: 116942805 : for (i = area->gc_last_free_atb_index; i < area->gc_alloc_table_byte_len; i++) {
635 : 116922149 : byte a = area->gc_alloc_table_start[i];
636 : : // *FORMAT-OFF*
637 [ + + + + ]: 116922149 : if (ATB_0_IS_FREE(a)) { if (++n_free >= n_blocks) { i = i * BLOCKS_PER_ATB + 0; goto found; } } else { n_free = 0; }
638 [ + + + + ]: 116012509 : if (ATB_1_IS_FREE(a)) { if (++n_free >= n_blocks) { i = i * BLOCKS_PER_ATB + 1; goto found; } } else { n_free = 0; }
639 [ + + + + ]: 115058211 : if (ATB_2_IS_FREE(a)) { if (++n_free >= n_blocks) { i = i * BLOCKS_PER_ATB + 2; goto found; } } else { n_free = 0; }
640 [ + + + + ]: 114135957 : if (ATB_3_IS_FREE(a)) { if (++n_free >= n_blocks) { i = i * BLOCKS_PER_ATB + 3; goto found; } } else { n_free = 0; }
641 : : // *FORMAT-ON*
642 : : }
643 : :
644 : : // No free blocks found on this heap. Mark this heap as
645 : : // filled, so we won't try to find free space here again until
646 : : // space is freed.
647 : : #if MICROPY_GC_SPLIT_HEAP
648 [ + + ]: 20656 : if (n_blocks == 1) {
649 : 13154 : area->gc_last_free_atb_index = (i + 1) / BLOCKS_PER_ATB; // or (size_t)-1
650 : : }
651 : : #endif
652 : : }
653 : :
654 : 12413 : GC_EXIT();
655 : : // nothing found!
656 [ + + ]: 12413 : if (collected) {
657 : : return NULL;
658 : : }
659 : 8272 : DEBUG_printf("gc_alloc(" UINT_FMT "): no free mem, triggering GC\n", n_bytes);
660 : 8272 : gc_collect();
661 : 8272 : collected = 1;
662 : 8272 : GC_ENTER();
663 : : }
664 : :
665 : : // found, ending at block i inclusive
666 : 3709029 : found:
667 : : // get starting and end blocks, both inclusive
668 : 3709029 : end_block = i;
669 : 3709029 : start_block = i - n_free + 1;
670 : :
671 : : // Set last free ATB index to block after last block we found, for start of
672 : : // next scan. To reduce fragmentation, we only do this if we were looking
673 : : // for a single free block, which guarantees that there are no free blocks
674 : : // before this one. Also, whenever we free or shink a block we must check
675 : : // if this index needs adjusting (see gc_realloc and gc_free).
676 [ + + ]: 3709029 : if (n_free == 1) {
677 : : #if MICROPY_GC_SPLIT_HEAP
678 : 3045074 : MP_STATE_MEM(gc_last_free_area) = area;
679 : : #endif
680 : 3045074 : area->gc_last_free_atb_index = (i + 1) / BLOCKS_PER_ATB;
681 : : }
682 : :
683 : : // mark first block as used head
684 : 3709029 : ATB_FREE_TO_HEAD(area, start_block);
685 : :
686 : : // mark rest of blocks as used tail
687 : : // TODO for a run of many blocks can make this more efficient
688 [ + + ]: 6285490 : for (size_t bl = start_block + 1; bl <= end_block; bl++) {
689 : 2576461 : ATB_FREE_TO_TAIL(area, bl);
690 : : }
691 : :
692 : : // get pointer to first block
693 : : // we must create this pointer before unlocking the GC so a collection can find it
694 : 3709029 : void *ret_ptr = (void *)(area->gc_pool_start + start_block * BYTES_PER_BLOCK);
695 : 3709029 : DEBUG_printf("gc_alloc(%p)\n", ret_ptr);
696 : :
697 : : #if MICROPY_GC_ALLOC_THRESHOLD
698 : 3709029 : MP_STATE_MEM(gc_alloc_amount) += n_blocks;
699 : : #endif
700 : :
701 : 3709029 : GC_EXIT();
702 : :
703 : : #if MICROPY_GC_CONSERVATIVE_CLEAR
704 : : // be conservative and zero out all the newly allocated blocks
705 : 3708904 : memset((byte *)ret_ptr, 0, (end_block - start_block + 1) * BYTES_PER_BLOCK);
706 : : #else
707 : : // zero out the additional bytes of the newly allocated blocks
708 : : // This is needed because the blocks may have previously held pointers
709 : : // to the heap and will not be set to something else if the caller
710 : : // doesn't actually use the entire block. As such they will continue
711 : : // to point to the heap and may prevent other blocks from being reclaimed.
712 : : memset((byte *)ret_ptr + n_bytes, 0, (end_block - start_block + 1) * BYTES_PER_BLOCK - n_bytes);
713 : : #endif
714 : :
715 : : #if MICROPY_ENABLE_FINALISER
716 [ + + ]: 3708904 : if (has_finaliser) {
717 : : // clear type pointer in case it is never set
718 : 8162 : ((mp_obj_base_t *)ret_ptr)->type = NULL;
719 : : // set mp_obj flag only if it has a finaliser
720 : 8162 : GC_ENTER();
721 : 8162 : FTB_SET(area, start_block);
722 : 8162 : GC_EXIT();
723 : : }
724 : : #else
725 : : (void)has_finaliser;
726 : : #endif
727 : :
728 : : #if EXTENSIVE_HEAP_PROFILING
729 : : gc_dump_alloc_table(&mp_plat_print);
730 : : #endif
731 : :
732 : : return ret_ptr;
733 : : }
734 : :
735 : : /*
736 : : void *gc_alloc(mp_uint_t n_bytes) {
737 : : return _gc_alloc(n_bytes, false);
738 : : }
739 : :
740 : : void *gc_alloc_with_finaliser(mp_uint_t n_bytes) {
741 : : return _gc_alloc(n_bytes, true);
742 : : }
743 : : */
744 : :
745 : : // force the freeing of a piece of memory
746 : : // TODO: freeing here does not call finaliser
747 : 538620 : void gc_free(void *ptr) {
748 [ + # ]: 538620 : if (MP_STATE_THREAD(gc_lock_depth) > 0) {
749 : : // TODO how to deal with this error?
750 : : return;
751 : : }
752 : :
753 : 538600 : GC_ENTER();
754 : :
755 : 538711 : DEBUG_printf("gc_free(%p)\n", ptr);
756 : :
757 [ + + ]: 538711 : if (ptr == NULL) {
758 : : // free(NULL) is a no-op
759 : 10632 : GC_EXIT();
760 : 10632 : return;
761 : : }
762 : :
763 : : // get the GC block number corresponding to this pointer
764 : 528079 : mp_state_mem_area_t *area;
765 : : #if MICROPY_GC_SPLIT_HEAP
766 [ + - ]: 528079 : area = gc_get_ptr_area(ptr);
767 [ - + ]: 528079 : assert(area);
768 : : #else
769 : : assert(VERIFY_PTR(ptr));
770 : : area = &MP_STATE_MEM(area);
771 : : #endif
772 : :
773 : 528079 : size_t block = BLOCK_FROM_PTR(area, ptr);
774 [ - + ]: 528079 : assert(ATB_GET_KIND(area, block) == AT_HEAD);
775 : :
776 : : #if MICROPY_ENABLE_FINALISER
777 : 528079 : FTB_CLEAR(area, block);
778 : : #endif
779 : :
780 : : #if MICROPY_GC_SPLIT_HEAP
781 [ + + ]: 528079 : if (MP_STATE_MEM(gc_last_free_area) != area) {
782 : : // We freed something but it isn't the current area. Reset the
783 : : // last free area to the start for a rescan. Note that this won't
784 : : // give much of a performance hit, since areas that are completely
785 : : // filled will likely be skipped (the gc_last_free_atb_index
786 : : // points to the last block).
787 : : // The reason why this is necessary is because it is not possible
788 : : // to see which area came first (like it is possible to adjust
789 : : // gc_last_free_atb_index based on whether the freed block is
790 : : // before the last free block).
791 : 488 : MP_STATE_MEM(gc_last_free_area) = &MP_STATE_MEM(area);
792 : : }
793 : : #endif
794 : :
795 : : // set the last_free pointer to this block if it's earlier in the heap
796 [ + + ]: 528079 : if (block / BLOCKS_PER_ATB < area->gc_last_free_atb_index) {
797 : 86638 : area->gc_last_free_atb_index = block / BLOCKS_PER_ATB;
798 : : }
799 : :
800 : : // free head and all of its tail blocks
801 : 2516538 : do {
802 : 2516538 : ATB_ANY_TO_FREE(area, block);
803 : 2516538 : block += 1;
804 [ + + ]: 2516538 : } while (ATB_GET_KIND(area, block) == AT_TAIL);
805 : :
806 : 528079 : GC_EXIT();
807 : :
808 : : #if EXTENSIVE_HEAP_PROFILING
809 : : gc_dump_alloc_table(&mp_plat_print);
810 : : #endif
811 : : }
812 : :
813 : 26 : size_t gc_nbytes(const void *ptr) {
814 : 26 : GC_ENTER();
815 : :
816 : 26 : mp_state_mem_area_t *area;
817 : : #if MICROPY_GC_SPLIT_HEAP
818 [ + - ]: 26 : area = gc_get_ptr_area(ptr);
819 : : #else
820 : : if (VERIFY_PTR(ptr)) {
821 : : area = &MP_STATE_MEM(area);
822 : : } else {
823 : : area = NULL;
824 : : }
825 : : #endif
826 : :
827 [ + + ]: 26 : if (area) {
828 : 24 : size_t block = BLOCK_FROM_PTR(area, ptr);
829 [ + - ]: 24 : if (ATB_GET_KIND(area, block) == AT_HEAD) {
830 : : // work out number of consecutive blocks in the chain starting with this on
831 : : size_t n_blocks = 0;
832 : 152 : do {
833 : 152 : n_blocks += 1;
834 [ + + ]: 152 : } while (ATB_GET_KIND(area, block + n_blocks) == AT_TAIL);
835 : 24 : GC_EXIT();
836 : 24 : return n_blocks * BYTES_PER_BLOCK;
837 : : }
838 : : }
839 : :
840 : : // invalid pointer
841 : 2 : GC_EXIT();
842 : 2 : return 0;
843 : : }
844 : :
845 : : #if 0
846 : : // old, simple realloc that didn't expand memory in place
847 : : void *gc_realloc(void *ptr, mp_uint_t n_bytes) {
848 : : mp_uint_t n_existing = gc_nbytes(ptr);
849 : : if (n_bytes <= n_existing) {
850 : : return ptr;
851 : : } else {
852 : : bool has_finaliser;
853 : : if (ptr == NULL) {
854 : : has_finaliser = false;
855 : : } else {
856 : : #if MICROPY_ENABLE_FINALISER
857 : : has_finaliser = FTB_GET(BLOCK_FROM_PTR((mp_uint_t)ptr));
858 : : #else
859 : : has_finaliser = false;
860 : : #endif
861 : : }
862 : : void *ptr2 = gc_alloc(n_bytes, has_finaliser);
863 : : if (ptr2 == NULL) {
864 : : return ptr2;
865 : : }
866 : : memcpy(ptr2, ptr, n_existing);
867 : : gc_free(ptr);
868 : : return ptr2;
869 : : }
870 : : }
871 : :
872 : : #else // Alternative gc_realloc impl
873 : :
874 : 503222 : void *gc_realloc(void *ptr_in, size_t n_bytes, bool allow_move) {
875 : : // check for pure allocation
876 [ + + ]: 503222 : if (ptr_in == NULL) {
877 : 41339 : return gc_alloc(n_bytes, false);
878 : : }
879 : :
880 : : // check for pure free
881 [ + + ]: 461883 : if (n_bytes == 0) {
882 : 2 : gc_free(ptr_in);
883 : 2 : return NULL;
884 : : }
885 : :
886 [ + + ]: 461881 : if (MP_STATE_THREAD(gc_lock_depth) > 0) {
887 : : return NULL;
888 : : }
889 : :
890 : 461855 : void *ptr = ptr_in;
891 : :
892 : 461855 : GC_ENTER();
893 : :
894 : : // get the GC block number corresponding to this pointer
895 : 461855 : mp_state_mem_area_t *area;
896 : : #if MICROPY_GC_SPLIT_HEAP
897 [ + - ]: 461855 : area = gc_get_ptr_area(ptr);
898 [ - + ]: 461855 : assert(area);
899 : : #else
900 : : assert(VERIFY_PTR(ptr));
901 : : area = &MP_STATE_MEM(area);
902 : : #endif
903 : 461855 : size_t block = BLOCK_FROM_PTR(area, ptr);
904 [ - + ]: 461855 : assert(ATB_GET_KIND(area, block) == AT_HEAD);
905 : :
906 : : // compute number of new blocks that are requested
907 : 461855 : size_t new_blocks = (n_bytes + BYTES_PER_BLOCK - 1) / BYTES_PER_BLOCK;
908 : :
909 : : // Get the total number of consecutive blocks that are already allocated to
910 : : // this chunk of memory, and then count the number of free blocks following
911 : : // it. Stop if we reach the end of the heap, or if we find enough extra
912 : : // free blocks to satisfy the realloc. Note that we need to compute the
913 : : // total size of the existing memory chunk so we can correctly and
914 : : // efficiently shrink it (see below for shrinking code).
915 : 461855 : size_t n_free = 0;
916 : 461855 : size_t n_blocks = 1; // counting HEAD block
917 : 461855 : size_t max_block = area->gc_alloc_table_byte_len * BLOCKS_PER_ATB;
918 [ + + ]: 6627241 : for (size_t bl = block + n_blocks; bl < max_block; bl++) {
919 : 6627211 : byte block_type = ATB_GET_KIND(area, bl);
920 [ + + ]: 6627211 : if (block_type == AT_TAIL) {
921 : 6033870 : n_blocks++;
922 : 6033870 : continue;
923 : : }
924 [ + + ]: 593341 : if (block_type == AT_FREE) {
925 : 525326 : n_free++;
926 [ + + ]: 525326 : if (n_blocks + n_free >= new_blocks) {
927 : : // stop as soon as we find enough blocks for n_bytes
928 : : break;
929 : : }
930 : 131516 : continue;
931 : : }
932 : : break;
933 : : }
934 : :
935 : : // return original ptr if it already has the requested number of blocks
936 [ + + ]: 461855 : if (new_blocks == n_blocks) {
937 : 259876 : GC_EXIT();
938 : 259876 : return ptr_in;
939 : : }
940 : :
941 : : // check if we can shrink the allocated area
942 [ + + ]: 201979 : if (new_blocks < n_blocks) {
943 : : // free unneeded tail blocks
944 [ + + ]: 48166 : for (size_t bl = block + new_blocks, count = n_blocks - new_blocks; count > 0; bl++, count--) {
945 : 24938 : ATB_ANY_TO_FREE(area, bl);
946 : : }
947 : :
948 : : #if MICROPY_GC_SPLIT_HEAP
949 [ + + ]: 23228 : if (MP_STATE_MEM(gc_last_free_area) != area) {
950 : : // See comment in gc_free.
951 : 13 : MP_STATE_MEM(gc_last_free_area) = &MP_STATE_MEM(area);
952 : : }
953 : : #endif
954 : :
955 : : // set the last_free pointer to end of this block if it's earlier in the heap
956 [ + + ]: 23228 : if ((block + new_blocks) / BLOCKS_PER_ATB < area->gc_last_free_atb_index) {
957 : 732 : area->gc_last_free_atb_index = (block + new_blocks) / BLOCKS_PER_ATB;
958 : : }
959 : :
960 : 23228 : GC_EXIT();
961 : :
962 : : #if EXTENSIVE_HEAP_PROFILING
963 : : gc_dump_alloc_table(&mp_plat_print);
964 : : #endif
965 : :
966 : 23228 : return ptr_in;
967 : : }
968 : :
969 : : // check if we can expand in place
970 [ + + ]: 178751 : if (new_blocks <= n_blocks + n_free) {
971 : : // mark few more blocks as used tail
972 [ + + ]: 371716 : for (size_t bl = block + n_blocks; bl < block + new_blocks; bl++) {
973 [ - + ]: 223884 : assert(ATB_GET_KIND(area, bl) == AT_FREE);
974 : 223884 : ATB_FREE_TO_TAIL(area, bl);
975 : : }
976 : :
977 : 147832 : GC_EXIT();
978 : :
979 : : #if MICROPY_GC_CONSERVATIVE_CLEAR
980 : : // be conservative and zero out all the newly allocated blocks
981 : 147832 : memset((byte *)ptr_in + n_blocks * BYTES_PER_BLOCK, 0, (new_blocks - n_blocks) * BYTES_PER_BLOCK);
982 : : #else
983 : : // zero out the additional bytes of the newly allocated blocks (see comment above in gc_alloc)
984 : : memset((byte *)ptr_in + n_bytes, 0, new_blocks * BYTES_PER_BLOCK - n_bytes);
985 : : #endif
986 : :
987 : : #if EXTENSIVE_HEAP_PROFILING
988 : : gc_dump_alloc_table(&mp_plat_print);
989 : : #endif
990 : :
991 : 147832 : return ptr_in;
992 : : }
993 : :
994 : : #if MICROPY_ENABLE_FINALISER
995 : 30919 : bool ftb_state = FTB_GET(area, block);
996 : : #else
997 : : bool ftb_state = false;
998 : : #endif
999 : :
1000 : 30919 : GC_EXIT();
1001 : :
1002 [ + + ]: 30919 : if (!allow_move) {
1003 : : // not allowed to move memory block so return failure
1004 : : return NULL;
1005 : : }
1006 : :
1007 : : // can't resize inplace; try to find a new contiguous chain
1008 : 19693 : void *ptr_out = gc_alloc(n_bytes, ftb_state);
1009 : :
1010 : : // check that the alloc succeeded
1011 [ + + ]: 19693 : if (ptr_out == NULL) {
1012 : : return NULL;
1013 : : }
1014 : :
1015 : 19685 : DEBUG_printf("gc_realloc(%p -> %p)\n", ptr_in, ptr_out);
1016 : 19685 : memcpy(ptr_out, ptr_in, n_blocks * BYTES_PER_BLOCK);
1017 : 19685 : gc_free(ptr_in);
1018 : 19685 : return ptr_out;
1019 : : }
1020 : : #endif // Alternative gc_realloc impl
1021 : :
1022 : 18 : void gc_dump_info(const mp_print_t *print) {
1023 : 18 : gc_info_t info;
1024 : 18 : gc_info(&info);
1025 : 18 : mp_printf(print, "GC: total: %u, used: %u, free: %u\n",
1026 : 18 : (uint)info.total, (uint)info.used, (uint)info.free);
1027 : 18 : mp_printf(print, " No. of 1-blocks: %u, 2-blocks: %u, max blk sz: %u, max free sz: %u\n",
1028 : 18 : (uint)info.num_1block, (uint)info.num_2block, (uint)info.max_block, (uint)info.max_free);
1029 : 18 : }
1030 : :
1031 : 4 : void gc_dump_alloc_table(const mp_print_t *print) {
1032 : 4 : GC_ENTER();
1033 : 4 : static const size_t DUMP_BYTES_PER_LINE = 64;
1034 [ + + ]: 20 : for (mp_state_mem_area_t *area = &MP_STATE_MEM(area); area != NULL; area = NEXT_AREA(area)) {
1035 : : #if !EXTENSIVE_HEAP_PROFILING
1036 : : // When comparing heap output we don't want to print the starting
1037 : : // pointer of the heap because it changes from run to run.
1038 : 16 : mp_printf(print, "GC memory layout; from %p:", area->gc_pool_start);
1039 : : #endif
1040 [ + + ]: 1248 : for (size_t bl = 0; bl < area->gc_alloc_table_byte_len * BLOCKS_PER_ATB; bl++) {
1041 [ + + ]: 1236 : if (bl % DUMP_BYTES_PER_LINE == 0) {
1042 : : // a new line of blocks
1043 : : {
1044 : : // check if this line contains only free blocks
1045 : : size_t bl2 = bl;
1046 [ + + + + ]: 258604 : while (bl2 < area->gc_alloc_table_byte_len * BLOCKS_PER_ATB && ATB_GET_KIND(area, bl2) == AT_FREE) {
1047 : 258580 : bl2++;
1048 : : }
1049 [ + + ]: 24 : if (bl2 - bl >= 2 * DUMP_BYTES_PER_LINE) {
1050 : : // there are at least 2 lines containing only free blocks, so abbreviate their printing
1051 : 16 : mp_printf(print, "\n (%u lines all free)", (uint)(bl2 - bl) / DUMP_BYTES_PER_LINE);
1052 : 16 : bl = bl2 & (~(DUMP_BYTES_PER_LINE - 1));
1053 [ + + ]: 16 : if (bl >= area->gc_alloc_table_byte_len * BLOCKS_PER_ATB) {
1054 : : // got to end of heap
1055 : : break;
1056 : : }
1057 : : }
1058 : : }
1059 : : // print header for new line of blocks
1060 : : // (the cast to uint32_t is for 16-bit ports)
1061 : 20 : mp_printf(print, "\n%08x: ", (uint)(bl * BYTES_PER_BLOCK));
1062 : : }
1063 : 1232 : int c = ' ';
1064 [ + + - + ]: 1232 : switch (ATB_GET_KIND(area, bl)) {
1065 : : case AT_FREE:
1066 : : c = '.';
1067 : : break;
1068 : : /* this prints out if the object is reachable from BSS or STACK (for unix only)
1069 : : case AT_HEAD: {
1070 : : c = 'h';
1071 : : void **ptrs = (void**)(void*)&mp_state_ctx;
1072 : : mp_uint_t len = offsetof(mp_state_ctx_t, vm.stack_top) / sizeof(mp_uint_t);
1073 : : for (mp_uint_t i = 0; i < len; i++) {
1074 : : mp_uint_t ptr = (mp_uint_t)ptrs[i];
1075 : : if (gc_get_ptr_area(ptr) && BLOCK_FROM_PTR(ptr) == bl) {
1076 : : c = 'B';
1077 : : break;
1078 : : }
1079 : : }
1080 : : if (c == 'h') {
1081 : : ptrs = (void**)&c;
1082 : : len = ((mp_uint_t)MP_STATE_THREAD(stack_top) - (mp_uint_t)&c) / sizeof(mp_uint_t);
1083 : : for (mp_uint_t i = 0; i < len; i++) {
1084 : : mp_uint_t ptr = (mp_uint_t)ptrs[i];
1085 : : if (gc_get_ptr_area(ptr) && BLOCK_FROM_PTR(ptr) == bl) {
1086 : : c = 'S';
1087 : : break;
1088 : : }
1089 : : }
1090 : : }
1091 : : break;
1092 : : }
1093 : : */
1094 : : /* this prints the uPy object type of the head block */
1095 : 72 : case AT_HEAD: {
1096 : 72 : void **ptr = (void **)(area->gc_pool_start + bl * BYTES_PER_BLOCK);
1097 [ + - ]: 72 : if (*ptr == &mp_type_tuple) {
1098 : : c = 'T';
1099 [ + - ]: 72 : } else if (*ptr == &mp_type_list) {
1100 : : c = 'L';
1101 [ + - ]: 72 : } else if (*ptr == &mp_type_dict) {
1102 : : c = 'D';
1103 [ + - + - ]: 72 : } else if (*ptr == &mp_type_str || *ptr == &mp_type_bytes) {
1104 : : c = 'S';
1105 : : }
1106 : : #if MICROPY_PY_BUILTINS_BYTEARRAY
1107 [ + - ]: 72 : else if (*ptr == &mp_type_bytearray) {
1108 : : c = 'A';
1109 : : }
1110 : : #endif
1111 : : #if MICROPY_PY_ARRAY
1112 [ + - ]: 72 : else if (*ptr == &mp_type_array) {
1113 : : c = 'A';
1114 : : }
1115 : : #endif
1116 : : #if MICROPY_PY_BUILTINS_FLOAT
1117 [ + - ]: 72 : else if (*ptr == &mp_type_float) {
1118 : : c = 'F';
1119 : : }
1120 : : #endif
1121 [ + + ]: 72 : else if (*ptr == &mp_type_fun_bc) {
1122 : : c = 'B';
1123 [ + - ]: 68 : } else if (*ptr == &mp_type_module) {
1124 : : c = 'M';
1125 : : } else {
1126 : 68 : c = 'h';
1127 : : #if 0
1128 : : // This code prints "Q" for qstr-pool data, and "q" for qstr-str
1129 : : // data. It can be useful to see how qstrs are being allocated,
1130 : : // but is disabled by default because it is very slow.
1131 : : for (qstr_pool_t *pool = MP_STATE_VM(last_pool); c == 'h' && pool != NULL; pool = pool->prev) {
1132 : : if ((qstr_pool_t *)ptr == pool) {
1133 : : c = 'Q';
1134 : : break;
1135 : : }
1136 : : for (const byte **q = pool->qstrs, **q_top = pool->qstrs + pool->len; q < q_top; q++) {
1137 : : if ((const byte *)ptr == *q) {
1138 : : c = 'q';
1139 : : break;
1140 : : }
1141 : : }
1142 : : }
1143 : : #endif
1144 : : }
1145 : : break;
1146 : : }
1147 : 96 : case AT_TAIL:
1148 : 96 : c = '=';
1149 : 96 : break;
1150 : 0 : case AT_MARK:
1151 : 0 : c = 'm';
1152 : 0 : break;
1153 : : }
1154 : 1232 : mp_printf(print, "%c", c);
1155 : : }
1156 : 16 : mp_print_str(print, "\n");
1157 : : }
1158 : 4 : GC_EXIT();
1159 : 4 : }
1160 : :
1161 : : #if 0
1162 : : // For testing the GC functions
1163 : : void gc_test(void) {
1164 : : mp_uint_t len = 500;
1165 : : mp_uint_t *heap = malloc(len);
1166 : : gc_init(heap, heap + len / sizeof(mp_uint_t));
1167 : : void *ptrs[100];
1168 : : {
1169 : : mp_uint_t **p = gc_alloc(16, false);
1170 : : p[0] = gc_alloc(64, false);
1171 : : p[1] = gc_alloc(1, false);
1172 : : p[2] = gc_alloc(1, false);
1173 : : p[3] = gc_alloc(1, false);
1174 : : mp_uint_t ***p2 = gc_alloc(16, false);
1175 : : p2[0] = p;
1176 : : p2[1] = p;
1177 : : ptrs[0] = p2;
1178 : : }
1179 : : for (int i = 0; i < 25; i += 2) {
1180 : : mp_uint_t *p = gc_alloc(i, false);
1181 : : printf("p=%p\n", p);
1182 : : if (i & 3) {
1183 : : // ptrs[i] = p;
1184 : : }
1185 : : }
1186 : :
1187 : : printf("Before GC:\n");
1188 : : gc_dump_alloc_table(&mp_plat_print);
1189 : : printf("Starting GC...\n");
1190 : : gc_collect_start();
1191 : : gc_collect_root(ptrs, sizeof(ptrs) / sizeof(void *));
1192 : : gc_collect_end();
1193 : : printf("After GC:\n");
1194 : : gc_dump_alloc_table(&mp_plat_print);
1195 : : }
1196 : : #endif
1197 : :
1198 : : #endif // MICROPY_ENABLE_GC
|
