blob: 0f137b963fe292adf6f679aaab52c18e8e47b52f [file] [log] [blame]
Damiendcced922013-10-21 23:45:08 +01001#include <stdio.h>
Damiendcced922013-10-21 23:45:08 +01002#include <string.h>
mux4f7e9f52014-04-03 23:55:12 +02003#include <stdbool.h>
Damiendcced922013-10-21 23:45:08 +01004
Damiend99b0522013-12-21 18:17:45 +00005#include "mpconfig.h"
Paul Sokolovskye807fa82014-04-02 20:36:32 +03006#include "misc.h"
Damiendcced922013-10-21 23:45:08 +01007#include "gc.h"
8
mux4f7e9f52014-04-03 23:55:12 +02009#include "misc.h"
10#include "qstr.h"
11#include "obj.h"
muxcc849f72014-04-05 15:49:03 +020012#include "runtime.h"
mux4f7e9f52014-04-03 23:55:12 +020013
Damien Georged3ebe482014-01-07 15:20:33 +000014#if MICROPY_ENABLE_GC
15
Paul Sokolovskyaf19cbd2014-02-10 21:45:54 +020016#if 0 // print debugging info
17#define DEBUG_PRINT (1)
Paul Sokolovsky44739e22014-02-16 18:11:42 +020018#define DEBUG_printf DEBUG_printf
Paul Sokolovskyaf19cbd2014-02-10 21:45:54 +020019#else // don't print debugging info
Damien George41eb6082014-02-26 22:40:35 +000020#define DEBUG_printf(...) (void)0
Paul Sokolovskyaf19cbd2014-02-10 21:45:54 +020021#endif
22
Damiendcced922013-10-21 23:45:08 +010023typedef unsigned char byte;
24
Damiendcced922013-10-21 23:45:08 +010025#define WORDS_PER_BLOCK (4)
26#define BYTES_PER_BLOCK (WORDS_PER_BLOCK * BYTES_PER_WORD)
27#define STACK_SIZE (64) // tunable; minimum is 1
28
Paul Sokolovsky520e2f52014-02-12 18:31:30 +020029STATIC byte *gc_alloc_table_start;
30STATIC machine_uint_t gc_alloc_table_byte_len;
Damien George12bab722014-04-05 20:35:48 +010031#if MICROPY_ENABLE_FINALISER
32STATIC byte *gc_finaliser_table_start;
33#endif
Paul Sokolovsky520e2f52014-02-12 18:31:30 +020034STATIC machine_uint_t *gc_pool_start;
35STATIC machine_uint_t *gc_pool_end;
Damiendcced922013-10-21 23:45:08 +010036
Paul Sokolovsky520e2f52014-02-12 18:31:30 +020037STATIC int gc_stack_overflow;
38STATIC machine_uint_t gc_stack[STACK_SIZE];
39STATIC machine_uint_t *gc_sp;
Damien George12bab722014-04-05 20:35:48 +010040STATIC bool gc_lock;
Damiendcced922013-10-21 23:45:08 +010041
Damiendcced922013-10-21 23:45:08 +010042// ATB = allocation table byte
43// 0b00 = FREE -- free block
44// 0b01 = HEAD -- head of a chain of blocks
45// 0b10 = TAIL -- in the tail of a chain of blocks
46// 0b11 = MARK -- marked head block
47
48#define AT_FREE (0)
49#define AT_HEAD (1)
50#define AT_TAIL (2)
51#define AT_MARK (3)
52
53#define BLOCKS_PER_ATB (4)
54#define ATB_MASK_0 (0x03)
55#define ATB_MASK_1 (0x0c)
56#define ATB_MASK_2 (0x30)
57#define ATB_MASK_3 (0xc0)
58
59#define ATB_0_IS_FREE(a) (((a) & ATB_MASK_0) == 0)
60#define ATB_1_IS_FREE(a) (((a) & ATB_MASK_1) == 0)
61#define ATB_2_IS_FREE(a) (((a) & ATB_MASK_2) == 0)
62#define ATB_3_IS_FREE(a) (((a) & ATB_MASK_3) == 0)
63
64#define BLOCK_SHIFT(block) (2 * ((block) & (BLOCKS_PER_ATB - 1)))
65#define ATB_GET_KIND(block) ((gc_alloc_table_start[(block) / BLOCKS_PER_ATB] >> BLOCK_SHIFT(block)) & 3)
66#define ATB_ANY_TO_FREE(block) do { gc_alloc_table_start[(block) / BLOCKS_PER_ATB] &= (~(AT_MARK << BLOCK_SHIFT(block))); } while (0)
67#define ATB_FREE_TO_HEAD(block) do { gc_alloc_table_start[(block) / BLOCKS_PER_ATB] |= (AT_HEAD << BLOCK_SHIFT(block)); } while (0)
68#define ATB_FREE_TO_TAIL(block) do { gc_alloc_table_start[(block) / BLOCKS_PER_ATB] |= (AT_TAIL << BLOCK_SHIFT(block)); } while (0)
69#define ATB_HEAD_TO_MARK(block) do { gc_alloc_table_start[(block) / BLOCKS_PER_ATB] |= (AT_MARK << BLOCK_SHIFT(block)); } while (0)
70#define ATB_MARK_TO_HEAD(block) do { gc_alloc_table_start[(block) / BLOCKS_PER_ATB] &= (~(AT_TAIL << BLOCK_SHIFT(block))); } while (0)
71
Damiendcced922013-10-21 23:45:08 +010072#define BLOCK_FROM_PTR(ptr) (((ptr) - (machine_uint_t)gc_pool_start) / BYTES_PER_BLOCK)
73#define PTR_FROM_BLOCK(block) (((block) * BYTES_PER_BLOCK + (machine_uint_t)gc_pool_start))
74#define ATB_FROM_BLOCK(bl) ((bl) / BLOCKS_PER_ATB)
75
Damien George12bab722014-04-05 20:35:48 +010076#if MICROPY_ENABLE_FINALISER
77// FTB = finaliser table byte
78// if set, then the corresponding block may have a finaliser
79
80#define BLOCKS_PER_FTB (8)
81
82#define FTB_GET(block) ((gc_finaliser_table_start[(block) / BLOCKS_PER_FTB] >> ((block) & 7)) & 1)
83#define FTB_SET(block) do { gc_finaliser_table_start[(block) / BLOCKS_PER_FTB] |= (1 << ((block) & 7)); } while (0)
84#define FTB_CLEAR(block) do { gc_finaliser_table_start[(block) / BLOCKS_PER_FTB] &= (~(1 << ((block) & 7))); } while (0)
85#endif
86
Damienbb5316b2013-10-22 21:12:29 +010087// TODO waste less memory; currently requires that all entries in alloc_table have a corresponding block in pool
88void gc_init(void *start, void *end) {
89 // align end pointer on block boundary
90 end = (void*)((machine_uint_t)end & (~(BYTES_PER_BLOCK - 1)));
Damien George12bab722014-04-05 20:35:48 +010091 DEBUG_printf("Initializing GC heap: %p..%p = %ld bytes\n", start, end, end - start);
Damienbb5316b2013-10-22 21:12:29 +010092
Damien George12bab722014-04-05 20:35:48 +010093 // calculate parameters for GC (T=total, A=alloc table, F=finaliser table, P=pool; all in bytes):
94 // T = A + F + P
95 // F = A * BLOCKS_PER_ATB / BLOCKS_PER_FTB
96 // P = A * BLOCKS_PER_ATB * BYTES_PER_BLOCK
97 // => T = A * (1 + BLOCKS_PER_ATB / BLOCKS_PER_FTB + BLOCKS_PER_ATB * BYTES_PER_BLOCK)
98 machine_uint_t total_byte_len = end - start;
99#if MICROPY_ENABLE_FINALISER
100 gc_alloc_table_byte_len = total_byte_len * BITS_PER_BYTE / (BITS_PER_BYTE + BITS_PER_BYTE * BLOCKS_PER_ATB / BLOCKS_PER_FTB + BITS_PER_BYTE * BLOCKS_PER_ATB * BYTES_PER_BLOCK);
101#else
102 gc_alloc_table_byte_len = total_byte_len / (1 + BITS_PER_BYTE / 2 * BYTES_PER_BLOCK);
103#endif
104
105
Damienbb5316b2013-10-22 21:12:29 +0100106 gc_alloc_table_start = (byte*)start;
mux4f7e9f52014-04-03 23:55:12 +0200107
Damien George12bab722014-04-05 20:35:48 +0100108#if MICROPY_ENABLE_FINALISER
109 machine_uint_t gc_finaliser_table_byte_len = (gc_alloc_table_byte_len * BLOCKS_PER_ATB) / BLOCKS_PER_FTB;
110 gc_finaliser_table_start = gc_alloc_table_start + gc_alloc_table_byte_len;
111#endif
mux4f7e9f52014-04-03 23:55:12 +0200112
Damien George12bab722014-04-05 20:35:48 +0100113 machine_uint_t gc_pool_block_len = gc_alloc_table_byte_len * BLOCKS_PER_ATB;
114 gc_pool_start = end - gc_pool_block_len * BYTES_PER_BLOCK;
Damienbb5316b2013-10-22 21:12:29 +0100115 gc_pool_end = end;
116
117 // clear ATBs
118 memset(gc_alloc_table_start, 0, gc_alloc_table_byte_len);
119
Damien George12bab722014-04-05 20:35:48 +0100120#if MICROPY_ENABLE_FINALISER
121 // clear FTBs
122 memset(gc_finaliser_table_start, 0, gc_finaliser_table_byte_len);
123#endif
mux4f7e9f52014-04-03 23:55:12 +0200124
Damienbb5316b2013-10-22 21:12:29 +0100125 // allocate first block because gc_pool_start points there and it will never
126 // be freed, so allocating 1 block with null pointers will minimise memory loss
127 ATB_FREE_TO_HEAD(0);
128 for (int i = 0; i < WORDS_PER_BLOCK; i++) {
129 gc_pool_start[i] = 0;
130 }
131
Damien George12bab722014-04-05 20:35:48 +0100132 // unlock the GC
133 gc_lock = false;
134
Paul Sokolovskyaf19cbd2014-02-10 21:45:54 +0200135 DEBUG_printf("GC layout:\n");
Damien George12bab722014-04-05 20:35:48 +0100136 DEBUG_printf(" alloc table at %p, length " UINT_FMT " bytes, " UINT_FMT " blocks\n", gc_alloc_table_start, gc_alloc_table_byte_len, gc_alloc_table_byte_len * BLOCKS_PER_ATB);
137#if MICROPY_ENABLE_FINALISER
138 DEBUG_printf(" finaliser table at %p, length " UINT_FMT " bytes, " UINT_FMT " blocks\n", gc_finaliser_table_start, gc_finaliser_table_byte_len, gc_finaliser_table_byte_len * BLOCKS_PER_FTB);
139#endif
140 DEBUG_printf(" pool at %p, length " UINT_FMT " bytes, " UINT_FMT " blocks\n", gc_pool_start, gc_pool_block_len * BYTES_PER_BLOCK, gc_pool_block_len);
Damienbb5316b2013-10-22 21:12:29 +0100141}
142
Damienfd8b6bc2013-10-22 20:26:36 +0100143#define VERIFY_PTR(ptr) ( \
144 (ptr & (BYTES_PER_BLOCK - 1)) == 0 /* must be aligned on a block */ \
145 && ptr >= (machine_uint_t)gc_pool_start /* must be above start of pool */ \
146 && ptr < (machine_uint_t)gc_pool_end /* must be below end of pool */ \
147 )
148
Damiendcced922013-10-21 23:45:08 +0100149#define VERIFY_MARK_AND_PUSH(ptr) \
150 do { \
Damienfd8b6bc2013-10-22 20:26:36 +0100151 if (VERIFY_PTR(ptr)) { \
Damiendcced922013-10-21 23:45:08 +0100152 machine_uint_t _block = BLOCK_FROM_PTR(ptr); \
153 if (ATB_GET_KIND(_block) == AT_HEAD) { \
154 /* an unmarked head, mark it, and push it on gc stack */ \
155 ATB_HEAD_TO_MARK(_block); \
156 if (gc_sp < &gc_stack[STACK_SIZE]) { \
157 *gc_sp++ = _block; \
158 } else { \
159 gc_stack_overflow = 1; \
160 } \
161 } \
162 } \
163 } while (0)
164
Paul Sokolovsky520e2f52014-02-12 18:31:30 +0200165STATIC void gc_drain_stack(void) {
Damiendcced922013-10-21 23:45:08 +0100166 while (gc_sp > gc_stack) {
167 // pop the next block off the stack
168 machine_uint_t block = *--gc_sp;
169
Damieneefcc792013-10-22 15:25:25 +0100170 // work out number of consecutive blocks in the chain starting with this one
Damiendcced922013-10-21 23:45:08 +0100171 machine_uint_t n_blocks = 0;
172 do {
173 n_blocks += 1;
174 } while (ATB_GET_KIND(block + n_blocks) == AT_TAIL);
175
176 // check this block's children
177 machine_uint_t *scan = (machine_uint_t*)PTR_FROM_BLOCK(block);
178 for (machine_uint_t i = n_blocks * WORDS_PER_BLOCK; i > 0; i--, scan++) {
179 machine_uint_t ptr2 = *scan;
180 VERIFY_MARK_AND_PUSH(ptr2);
181 }
182 }
183}
184
Paul Sokolovsky520e2f52014-02-12 18:31:30 +0200185STATIC void gc_deal_with_stack_overflow(void) {
Damiendcced922013-10-21 23:45:08 +0100186 while (gc_stack_overflow) {
187 gc_stack_overflow = 0;
188 gc_sp = gc_stack;
189
190 // scan entire memory looking for blocks which have been marked but not their children
191 for (machine_uint_t block = 0; block < gc_alloc_table_byte_len * BLOCKS_PER_ATB; block++) {
192 // trace (again) if mark bit set
193 if (ATB_GET_KIND(block) == AT_MARK) {
194 *gc_sp++ = block;
195 gc_drain_stack();
196 }
197 }
198 }
199}
200
Paul Sokolovsky520e2f52014-02-12 18:31:30 +0200201STATIC void gc_sweep(void) {
Damiendcced922013-10-21 23:45:08 +0100202 // free unmarked heads and their tails
203 int free_tail = 0;
204 for (machine_uint_t block = 0; block < gc_alloc_table_byte_len * BLOCKS_PER_ATB; block++) {
205 switch (ATB_GET_KIND(block)) {
206 case AT_HEAD:
Damien George12bab722014-04-05 20:35:48 +0100207#if MICROPY_ENABLE_FINALISER
208 if (FTB_GET(block)) {
209 mp_obj_t obj = (mp_obj_t)PTR_FROM_BLOCK(block);
210 if (((mp_obj_base_t*)obj)->type != MP_OBJ_NULL) {
211 // if the object has a type then see if it has a __del__ method
212 mp_obj_t dest[2];
213 mp_load_method_maybe(obj, MP_QSTR___del__, dest);
214 if (dest[0] != MP_OBJ_NULL) {
215 // load_method returned a method
216 mp_call_method_n_kw(0, 0, dest);
217 }
mux4f7e9f52014-04-03 23:55:12 +0200218 }
Damien George12bab722014-04-05 20:35:48 +0100219 // clear finaliser flag
220 FTB_CLEAR(block);
mux4f7e9f52014-04-03 23:55:12 +0200221 }
Damien George12bab722014-04-05 20:35:48 +0100222#endif
Damiendcced922013-10-21 23:45:08 +0100223 free_tail = 1;
224 // fall through to free the head
225
226 case AT_TAIL:
227 if (free_tail) {
228 ATB_ANY_TO_FREE(block);
229 }
230 break;
231
232 case AT_MARK:
233 ATB_MARK_TO_HEAD(block);
234 free_tail = 0;
235 break;
236 }
237 }
238}
239
Damien8b3a7c22013-10-23 20:20:17 +0100240void gc_collect_start(void) {
Damien George12bab722014-04-05 20:35:48 +0100241 gc_lock = true;
Damiendcced922013-10-21 23:45:08 +0100242 gc_stack_overflow = 0;
243 gc_sp = gc_stack;
244}
245
246void gc_collect_root(void **ptrs, machine_uint_t len) {
247 for (machine_uint_t i = 0; i < len; i++) {
248 machine_uint_t ptr = (machine_uint_t)ptrs[i];
249 VERIFY_MARK_AND_PUSH(ptr);
250 gc_drain_stack();
251 }
252}
253
Damien8b3a7c22013-10-23 20:20:17 +0100254void gc_collect_end(void) {
Damiendcced922013-10-21 23:45:08 +0100255 gc_deal_with_stack_overflow();
256 gc_sweep();
Damien George12bab722014-04-05 20:35:48 +0100257 gc_lock = false;
Damieneefcc792013-10-22 15:25:25 +0100258}
Damiendcced922013-10-21 23:45:08 +0100259
Damieneefcc792013-10-22 15:25:25 +0100260void gc_info(gc_info_t *info) {
261 info->total = (gc_pool_end - gc_pool_start) * sizeof(machine_uint_t);
262 info->used = 0;
263 info->free = 0;
264 info->num_1block = 0;
265 info->num_2block = 0;
266 info->max_block = 0;
267 for (machine_uint_t block = 0, len = 0; block < gc_alloc_table_byte_len * BLOCKS_PER_ATB; block++) {
268 machine_uint_t kind = ATB_GET_KIND(block);
269 if (kind == AT_FREE || kind == AT_HEAD) {
270 if (len == 1) {
271 info->num_1block += 1;
272 } else if (len == 2) {
273 info->num_2block += 1;
274 }
275 if (len > info->max_block) {
276 info->max_block = len;
277 }
278 }
279 switch (kind) {
Damiendcced922013-10-21 23:45:08 +0100280 case AT_FREE:
Damieneefcc792013-10-22 15:25:25 +0100281 info->free += 1;
282 len = 0;
Damiendcced922013-10-21 23:45:08 +0100283 break;
284
285 case AT_HEAD:
Damieneefcc792013-10-22 15:25:25 +0100286 info->used += 1;
287 len = 1;
288 break;
289
Damiendcced922013-10-21 23:45:08 +0100290 case AT_TAIL:
Damieneefcc792013-10-22 15:25:25 +0100291 info->used += 1;
292 len += 1;
Damiendcced922013-10-21 23:45:08 +0100293 break;
294
295 case AT_MARK:
Damieneefcc792013-10-22 15:25:25 +0100296 // shouldn't happen
Damiendcced922013-10-21 23:45:08 +0100297 break;
298 }
299 }
300
Damieneefcc792013-10-22 15:25:25 +0100301 info->used *= BYTES_PER_BLOCK;
302 info->free *= BYTES_PER_BLOCK;
Damiendcced922013-10-21 23:45:08 +0100303}
304
Damien George12bab722014-04-05 20:35:48 +0100305void *gc_alloc(machine_uint_t n_bytes, bool has_finaliser) {
Damiendcced922013-10-21 23:45:08 +0100306 machine_uint_t n_blocks = ((n_bytes + BYTES_PER_BLOCK - 1) & (~(BYTES_PER_BLOCK - 1))) / BYTES_PER_BLOCK;
Damien Georgece1162a2014-02-26 22:55:59 +0000307 DEBUG_printf("gc_alloc(" UINT_FMT " bytes -> " UINT_FMT " blocks)\n", n_bytes, n_blocks);
Damiendcced922013-10-21 23:45:08 +0100308
Damien George12bab722014-04-05 20:35:48 +0100309 if (gc_lock) {
310 // TODO
311 }
312
Damiendcced922013-10-21 23:45:08 +0100313 // check for 0 allocation
314 if (n_blocks == 0) {
315 return NULL;
316 }
317
318 machine_uint_t i;
319 machine_uint_t end_block;
320 machine_uint_t start_block;
321 machine_uint_t n_free = 0;
322 int collected = 0;
323 for (;;) {
324
325 // look for a run of n_blocks available blocks
326 for (i = 0; i < gc_alloc_table_byte_len; i++) {
327 byte a = gc_alloc_table_start[i];
328 if (ATB_0_IS_FREE(a)) { if (++n_free >= n_blocks) { i = i * BLOCKS_PER_ATB + 0; goto found; } } else { n_free = 0; }
329 if (ATB_1_IS_FREE(a)) { if (++n_free >= n_blocks) { i = i * BLOCKS_PER_ATB + 1; goto found; } } else { n_free = 0; }
330 if (ATB_2_IS_FREE(a)) { if (++n_free >= n_blocks) { i = i * BLOCKS_PER_ATB + 2; goto found; } } else { n_free = 0; }
331 if (ATB_3_IS_FREE(a)) { if (++n_free >= n_blocks) { i = i * BLOCKS_PER_ATB + 3; goto found; } } else { n_free = 0; }
332 }
333
334 // nothing found!
335 if (collected) {
336 return NULL;
337 }
Paul Sokolovsky723a6ed2014-02-11 18:01:38 +0200338 DEBUG_printf("gc_alloc(" UINT_FMT "): no free mem, triggering GC\n", n_bytes);
Damiendcced922013-10-21 23:45:08 +0100339 gc_collect();
340 collected = 1;
341 }
342
343 // found, ending at block i inclusive
344found:
345 // get starting and end blocks, both inclusive
346 end_block = i;
347 start_block = i - n_free + 1;
348
349 // mark first block as used head
350 ATB_FREE_TO_HEAD(start_block);
351
352 // mark rest of blocks as used tail
353 // TODO for a run of many blocks can make this more efficient
354 for (machine_uint_t bl = start_block + 1; bl <= end_block; bl++) {
355 ATB_FREE_TO_TAIL(bl);
356 }
357
Damien George12bab722014-04-05 20:35:48 +0100358 // get pointer to first block
359 void *ret_ptr = (void*)(gc_pool_start + start_block * WORDS_PER_BLOCK);
muxcc849f72014-04-05 15:49:03 +0200360
Damien George12bab722014-04-05 20:35:48 +0100361#if MICROPY_ENABLE_FINALISER
362 if (has_finaliser) {
363 // clear type pointer in case it is never set
364 ((mp_obj_base_t*)ret_ptr)->type = MP_OBJ_NULL;
365 // set mp_obj flag only if it has a finaliser
366 FTB_SET(start_block);
367 }
368#endif
369
370 return ret_ptr;
Damiendcced922013-10-21 23:45:08 +0100371}
372
Damien George12bab722014-04-05 20:35:48 +0100373/*
mux4f7e9f52014-04-03 23:55:12 +0200374void *gc_alloc(machine_uint_t n_bytes) {
375 return _gc_alloc(n_bytes, false);
376}
377
Damien George12bab722014-04-05 20:35:48 +0100378void *gc_alloc_with_finaliser(machine_uint_t n_bytes) {
mux4f7e9f52014-04-03 23:55:12 +0200379 return _gc_alloc(n_bytes, true);
380}
Damien George12bab722014-04-05 20:35:48 +0100381*/
mux4f7e9f52014-04-03 23:55:12 +0200382
Damienfd8b6bc2013-10-22 20:26:36 +0100383// force the freeing of a piece of memory
384void gc_free(void *ptr_in) {
Damien George12bab722014-04-05 20:35:48 +0100385 if (gc_lock) {
386 // TODO
387 }
388
Damienfd8b6bc2013-10-22 20:26:36 +0100389 machine_uint_t ptr = (machine_uint_t)ptr_in;
390
391 if (VERIFY_PTR(ptr)) {
392 machine_uint_t block = BLOCK_FROM_PTR(ptr);
393 if (ATB_GET_KIND(block) == AT_HEAD) {
394 // free head and all of its tail blocks
395 do {
396 ATB_ANY_TO_FREE(block);
397 block += 1;
398 } while (ATB_GET_KIND(block) == AT_TAIL);
399 }
400 }
401}
402
Damiendcced922013-10-21 23:45:08 +0100403machine_uint_t gc_nbytes(void *ptr_in) {
404 machine_uint_t ptr = (machine_uint_t)ptr_in;
405
Damienfd8b6bc2013-10-22 20:26:36 +0100406 if (VERIFY_PTR(ptr)) {
Damiendcced922013-10-21 23:45:08 +0100407 machine_uint_t block = BLOCK_FROM_PTR(ptr);
408 if (ATB_GET_KIND(block) == AT_HEAD) {
409 // work out number of consecutive blocks in the chain starting with this on
410 machine_uint_t n_blocks = 0;
411 do {
412 n_blocks += 1;
413 } while (ATB_GET_KIND(block + n_blocks) == AT_TAIL);
414 return n_blocks * BYTES_PER_BLOCK;
415 }
416 }
417
418 // invalid pointer
419 return 0;
420}
421
mux87826762014-03-12 21:00:23 +0200422#if 0
Damien George6fc765c2014-03-07 00:21:51 +0000423// use this realloc for now, one below is broken
424void *gc_realloc(void *ptr, machine_uint_t n_bytes) {
425 machine_uint_t n_existing = gc_nbytes(ptr);
426 if (n_bytes <= n_existing) {
427 return ptr;
428 } else {
429 // TODO check if we can grow inplace
430 void *ptr2 = gc_alloc(n_bytes);
431 if (ptr2 == NULL) {
432 return ptr2;
433 }
434 memcpy(ptr2, ptr, n_existing);
435 gc_free(ptr);
436 return ptr2;
437 }
438}
mux87826762014-03-12 21:00:23 +0200439#else
muxfbaa1472014-03-05 23:23:04 +0200440void *gc_realloc(void *ptr_in, machine_uint_t n_bytes) {
Damien George12bab722014-04-05 20:35:48 +0100441 if (gc_lock) {
442 // TODO
443 }
444
muxfbaa1472014-03-05 23:23:04 +0200445 void *ptr_out = NULL;
Damien George73d57932014-03-06 00:02:16 +0000446 machine_uint_t block = 0;
muxfbaa1472014-03-05 23:23:04 +0200447 machine_uint_t ptr = (machine_uint_t)ptr_in;
448
449 if (ptr_in == NULL) {
Damien George12bab722014-04-05 20:35:48 +0100450 return gc_alloc(n_bytes, false);
Damiendcced922013-10-21 23:45:08 +0100451 }
muxfbaa1472014-03-05 23:23:04 +0200452
Damien George470184e2014-03-12 22:44:11 +0000453 if (VERIFY_PTR(ptr) // verify pointer
454 && (block = BLOCK_FROM_PTR(ptr)) // get first block
455 && ATB_GET_KIND(block) == AT_HEAD) { // make sure it's a HEAD block
muxfbaa1472014-03-05 23:23:04 +0200456
457 byte block_type;
458 machine_uint_t n_free = 0;
Damien George470184e2014-03-12 22:44:11 +0000459 machine_uint_t n_blocks = 1; // counting HEAD block
mux87826762014-03-12 21:00:23 +0200460 machine_uint_t max_block = gc_alloc_table_byte_len * BLOCKS_PER_ATB;
muxfbaa1472014-03-05 23:23:04 +0200461
Damien George470184e2014-03-12 22:44:11 +0000462 // get the number of consecutive tail blocks and
463 // the number of free blocks after last tail block
464 // stop if we reach (or are at) end of heap
mux87826762014-03-12 21:00:23 +0200465 while ((block + n_blocks + n_free) < max_block
Damien George470184e2014-03-12 22:44:11 +0000466 // stop as soon as we find enough blocks for n_bytes
mux87826762014-03-12 21:00:23 +0200467 && (n_bytes > ((n_blocks+n_free) * BYTES_PER_BLOCK))
Damien George470184e2014-03-12 22:44:11 +0000468 // stop if block is HEAD
mux87826762014-03-12 21:00:23 +0200469 && (block_type = ATB_GET_KIND(block + n_blocks + n_free)) != AT_HEAD) {
muxfbaa1472014-03-05 23:23:04 +0200470 switch (block_type) {
471 case AT_FREE: n_free++; break;
472 case AT_TAIL: n_blocks++; break;
473 default: break;
474 }
mux87826762014-03-12 21:00:23 +0200475 }
Damien George470184e2014-03-12 22:44:11 +0000476 // number of allocated bytes
muxfbaa1472014-03-05 23:23:04 +0200477 machine_uint_t n_existing = n_blocks * BYTES_PER_BLOCK;
478
Damien George470184e2014-03-12 22:44:11 +0000479 // check if realloc'ing to a smaller size
muxfbaa1472014-03-05 23:23:04 +0200480 if (n_bytes <= n_existing) {
481 ptr_out = ptr_in;
Damien George470184e2014-03-12 22:44:11 +0000482 // free unneeded tail blocks
Damien George73d57932014-03-06 00:02:16 +0000483 for (machine_uint_t bl = block + n_blocks; ATB_GET_KIND(bl) == AT_TAIL; bl++) {
484 ATB_ANY_TO_FREE(bl);
muxfbaa1472014-03-05 23:23:04 +0200485 }
486
Damien George470184e2014-03-12 22:44:11 +0000487 // check if we can expand in place
mux87826762014-03-12 21:00:23 +0200488 } else if (n_bytes <= (n_existing + (n_free * BYTES_PER_BLOCK))) {
Damien George470184e2014-03-12 22:44:11 +0000489 // number of blocks needed to expand +1 if there's a remainder
muxfbaa1472014-03-05 23:23:04 +0200490 machine_uint_t n_diff = ( n_bytes - n_existing)/BYTES_PER_BLOCK+
491 ((n_bytes - n_existing)%BYTES_PER_BLOCK!=0);
492
493 DEBUG_printf("gc_realloc: expanding " UINT_FMT " blocks (" UINT_FMT " bytes) to " UINT_FMT " blocks (" UINT_FMT " bytes)\n",
494 n_existing/BYTES_PER_BLOCK, n_existing, n_existing/BYTES_PER_BLOCK+n_diff, n_existing + n_diff*BYTES_PER_BLOCK);
495
Damien George470184e2014-03-12 22:44:11 +0000496 // mark rest of blocks as used tail
Damien George73d57932014-03-06 00:02:16 +0000497 for (machine_uint_t bl = block + n_blocks; bl < (block + n_blocks + n_diff); bl++) {
muxfbaa1472014-03-05 23:23:04 +0200498 ATB_FREE_TO_TAIL(bl);
499 }
500 ptr_out = ptr_in;
501
Damien George470184e2014-03-12 22:44:11 +0000502 // try to find a new contiguous chain
Damien George12bab722014-04-05 20:35:48 +0100503 } else if ((ptr_out = gc_alloc(n_bytes,
504#if MICROPY_ENABLE_FINALISER
505 FTB_GET(block)
506#else
507 false
508#endif
509 )) != NULL) {
Damien George470184e2014-03-12 22:44:11 +0000510 DEBUG_printf("gc_realloc: allocating new block\n");
muxfbaa1472014-03-05 23:23:04 +0200511 memcpy(ptr_out, ptr_in, n_existing);
512 gc_free(ptr_in);
513 }
514 }
515
516 return ptr_out;
Damiendcced922013-10-21 23:45:08 +0100517}
mux87826762014-03-12 21:00:23 +0200518
Damien George6fc765c2014-03-07 00:21:51 +0000519#endif
Damiendcced922013-10-21 23:45:08 +0100520
Paul Sokolovsky723a6ed2014-02-11 18:01:38 +0200521void gc_dump_info() {
522 gc_info_t info;
523 gc_info(&info);
524 printf("GC: total: " UINT_FMT ", used: " UINT_FMT ", free: " UINT_FMT "\n", info.total, info.used, info.free);
525 printf(" No. of 1-blocks: " UINT_FMT ", 2-blocks: " UINT_FMT ", max blk sz: " UINT_FMT "\n",
526 info.num_1block, info.num_2block, info.max_block);
527}
528
Damien Georgece1162a2014-02-26 22:55:59 +0000529void gc_dump_alloc_table(void) {
530 printf("GC memory layout:");
Damieneefcc792013-10-22 15:25:25 +0100531 for (machine_uint_t bl = 0; bl < gc_alloc_table_byte_len * BLOCKS_PER_ATB; bl++) {
Damien Georgece1162a2014-02-26 22:55:59 +0000532 if (bl % 64 == 0) {
533 printf("\n%04x: ", (uint)bl);
Damieneefcc792013-10-22 15:25:25 +0100534 }
Damien Georgece1162a2014-02-26 22:55:59 +0000535 int c = ' ';
536 switch (ATB_GET_KIND(bl)) {
537 case AT_FREE: c = '.'; break;
538 case AT_HEAD: c = 'h'; break;
539 case AT_TAIL: c = 't'; break;
540 case AT_MARK: c = 'm'; break;
541 }
542 printf("%c", c);
Damieneefcc792013-10-22 15:25:25 +0100543 }
Damien Georgece1162a2014-02-26 22:55:59 +0000544 printf("\n");
Damieneefcc792013-10-22 15:25:25 +0100545}
546
Damien Georgece1162a2014-02-26 22:55:59 +0000547#if DEBUG_PRINT
Paul Sokolovskyaf19cbd2014-02-10 21:45:54 +0200548void gc_test(void) {
549 machine_uint_t len = 500;
Damiendcced922013-10-21 23:45:08 +0100550 machine_uint_t *heap = malloc(len);
551 gc_init(heap, heap + len / sizeof(machine_uint_t));
552 void *ptrs[100];
553 {
Damien George12bab722014-04-05 20:35:48 +0100554 machine_uint_t **p = gc_alloc(16, false);
555 p[0] = gc_alloc(64, false);
556 p[1] = gc_alloc(1, false);
557 p[2] = gc_alloc(1, false);
558 p[3] = gc_alloc(1, false);
559 machine_uint_t ***p2 = gc_alloc(16, false);
Damiendcced922013-10-21 23:45:08 +0100560 p2[0] = p;
561 p2[1] = p;
562 ptrs[0] = p2;
563 }
Paul Sokolovskyaf19cbd2014-02-10 21:45:54 +0200564 for (int i = 0; i < 25; i+=2) {
Damien George12bab722014-04-05 20:35:48 +0100565 machine_uint_t *p = gc_alloc(i, false);
Damiendcced922013-10-21 23:45:08 +0100566 printf("p=%p\n", p);
567 if (i & 3) {
568 //ptrs[i] = p;
569 }
570 }
571
Paul Sokolovskyaf19cbd2014-02-10 21:45:54 +0200572 printf("Before GC:\n");
Damien Georgece1162a2014-02-26 22:55:59 +0000573 gc_dump_alloc_table();
Paul Sokolovskyaf19cbd2014-02-10 21:45:54 +0200574 printf("Starting GC...\n");
575 gc_collect_start();
576 gc_collect_root(ptrs, sizeof(ptrs) / sizeof(void*));
577 gc_collect_end();
578 printf("After GC:\n");
Damien Georgece1162a2014-02-26 22:55:59 +0000579 gc_dump_alloc_table();
Damiendcced922013-10-21 23:45:08 +0100580}
Paul Sokolovskyaf19cbd2014-02-10 21:45:54 +0200581#endif
Damien Georged3ebe482014-01-07 15:20:33 +0000582
583#endif // MICROPY_ENABLE_GC