Damien | dcced92 | 2013-10-21 23:45:08 +0100 | [diff] [blame] | 1 | #include <stdio.h> |
Damien | dcced92 | 2013-10-21 23:45:08 +0100 | [diff] [blame] | 2 | #include <string.h> |
mux | 4f7e9f5 | 2014-04-03 23:55:12 +0200 | [diff] [blame] | 3 | #include <stdbool.h> |
Damien | dcced92 | 2013-10-21 23:45:08 +0100 | [diff] [blame] | 4 | |
Damien | d99b052 | 2013-12-21 18:17:45 +0000 | [diff] [blame] | 5 | #include "mpconfig.h" |
Paul Sokolovsky | e807fa8 | 2014-04-02 20:36:32 +0300 | [diff] [blame] | 6 | #include "misc.h" |
Damien | dcced92 | 2013-10-21 23:45:08 +0100 | [diff] [blame] | 7 | #include "gc.h" |
| 8 | |
mux | 4f7e9f5 | 2014-04-03 23:55:12 +0200 | [diff] [blame] | 9 | #include "misc.h" |
| 10 | #include "qstr.h" |
| 11 | #include "obj.h" |
mux | cc849f7 | 2014-04-05 15:49:03 +0200 | [diff] [blame] | 12 | #include "runtime.h" |
mux | 4f7e9f5 | 2014-04-03 23:55:12 +0200 | [diff] [blame] | 13 | |
Damien George | d3ebe48 | 2014-01-07 15:20:33 +0000 | [diff] [blame] | 14 | #if MICROPY_ENABLE_GC |
| 15 | |
Paul Sokolovsky | af19cbd | 2014-02-10 21:45:54 +0200 | [diff] [blame] | 16 | #if 0 // print debugging info |
| 17 | #define DEBUG_PRINT (1) |
Paul Sokolovsky | 44739e2 | 2014-02-16 18:11:42 +0200 | [diff] [blame] | 18 | #define DEBUG_printf DEBUG_printf |
Paul Sokolovsky | af19cbd | 2014-02-10 21:45:54 +0200 | [diff] [blame] | 19 | #else // don't print debugging info |
Damien George | 41eb608 | 2014-02-26 22:40:35 +0000 | [diff] [blame] | 20 | #define DEBUG_printf(...) (void)0 |
Paul Sokolovsky | af19cbd | 2014-02-10 21:45:54 +0200 | [diff] [blame] | 21 | #endif |
| 22 | |
Damien | dcced92 | 2013-10-21 23:45:08 +0100 | [diff] [blame] | 23 | typedef unsigned char byte; |
| 24 | |
Damien | dcced92 | 2013-10-21 23:45:08 +0100 | [diff] [blame] | 25 | #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 Sokolovsky | 520e2f5 | 2014-02-12 18:31:30 +0200 | [diff] [blame] | 29 | STATIC byte *gc_alloc_table_start; |
| 30 | STATIC machine_uint_t gc_alloc_table_byte_len; |
Damien George | 12bab72 | 2014-04-05 20:35:48 +0100 | [diff] [blame^] | 31 | #if MICROPY_ENABLE_FINALISER |
| 32 | STATIC byte *gc_finaliser_table_start; |
| 33 | #endif |
Paul Sokolovsky | 520e2f5 | 2014-02-12 18:31:30 +0200 | [diff] [blame] | 34 | STATIC machine_uint_t *gc_pool_start; |
| 35 | STATIC machine_uint_t *gc_pool_end; |
Damien | dcced92 | 2013-10-21 23:45:08 +0100 | [diff] [blame] | 36 | |
Paul Sokolovsky | 520e2f5 | 2014-02-12 18:31:30 +0200 | [diff] [blame] | 37 | STATIC int gc_stack_overflow; |
| 38 | STATIC machine_uint_t gc_stack[STACK_SIZE]; |
| 39 | STATIC machine_uint_t *gc_sp; |
Damien George | 12bab72 | 2014-04-05 20:35:48 +0100 | [diff] [blame^] | 40 | STATIC bool gc_lock; |
Damien | dcced92 | 2013-10-21 23:45:08 +0100 | [diff] [blame] | 41 | |
Damien | dcced92 | 2013-10-21 23:45:08 +0100 | [diff] [blame] | 42 | // 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 | |
Damien | dcced92 | 2013-10-21 23:45:08 +0100 | [diff] [blame] | 72 | #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 George | 12bab72 | 2014-04-05 20:35:48 +0100 | [diff] [blame^] | 76 | #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 | |
Damien | bb5316b | 2013-10-22 21:12:29 +0100 | [diff] [blame] | 87 | // TODO waste less memory; currently requires that all entries in alloc_table have a corresponding block in pool |
| 88 | void 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 George | 12bab72 | 2014-04-05 20:35:48 +0100 | [diff] [blame^] | 91 | DEBUG_printf("Initializing GC heap: %p..%p = %ld bytes\n", start, end, end - start); |
Damien | bb5316b | 2013-10-22 21:12:29 +0100 | [diff] [blame] | 92 | |
Damien George | 12bab72 | 2014-04-05 20:35:48 +0100 | [diff] [blame^] | 93 | // 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 | |
Damien | bb5316b | 2013-10-22 21:12:29 +0100 | [diff] [blame] | 106 | gc_alloc_table_start = (byte*)start; |
mux | 4f7e9f5 | 2014-04-03 23:55:12 +0200 | [diff] [blame] | 107 | |
Damien George | 12bab72 | 2014-04-05 20:35:48 +0100 | [diff] [blame^] | 108 | #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 |
mux | 4f7e9f5 | 2014-04-03 23:55:12 +0200 | [diff] [blame] | 112 | |
Damien George | 12bab72 | 2014-04-05 20:35:48 +0100 | [diff] [blame^] | 113 | 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; |
Damien | bb5316b | 2013-10-22 21:12:29 +0100 | [diff] [blame] | 115 | gc_pool_end = end; |
| 116 | |
| 117 | // clear ATBs |
| 118 | memset(gc_alloc_table_start, 0, gc_alloc_table_byte_len); |
| 119 | |
Damien George | 12bab72 | 2014-04-05 20:35:48 +0100 | [diff] [blame^] | 120 | #if MICROPY_ENABLE_FINALISER |
| 121 | // clear FTBs |
| 122 | memset(gc_finaliser_table_start, 0, gc_finaliser_table_byte_len); |
| 123 | #endif |
mux | 4f7e9f5 | 2014-04-03 23:55:12 +0200 | [diff] [blame] | 124 | |
Damien | bb5316b | 2013-10-22 21:12:29 +0100 | [diff] [blame] | 125 | // 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 George | 12bab72 | 2014-04-05 20:35:48 +0100 | [diff] [blame^] | 132 | // unlock the GC |
| 133 | gc_lock = false; |
| 134 | |
Paul Sokolovsky | af19cbd | 2014-02-10 21:45:54 +0200 | [diff] [blame] | 135 | DEBUG_printf("GC layout:\n"); |
Damien George | 12bab72 | 2014-04-05 20:35:48 +0100 | [diff] [blame^] | 136 | 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); |
Damien | bb5316b | 2013-10-22 21:12:29 +0100 | [diff] [blame] | 141 | } |
| 142 | |
Damien | fd8b6bc | 2013-10-22 20:26:36 +0100 | [diff] [blame] | 143 | #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 | |
Damien | dcced92 | 2013-10-21 23:45:08 +0100 | [diff] [blame] | 149 | #define VERIFY_MARK_AND_PUSH(ptr) \ |
| 150 | do { \ |
Damien | fd8b6bc | 2013-10-22 20:26:36 +0100 | [diff] [blame] | 151 | if (VERIFY_PTR(ptr)) { \ |
Damien | dcced92 | 2013-10-21 23:45:08 +0100 | [diff] [blame] | 152 | 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 Sokolovsky | 520e2f5 | 2014-02-12 18:31:30 +0200 | [diff] [blame] | 165 | STATIC void gc_drain_stack(void) { |
Damien | dcced92 | 2013-10-21 23:45:08 +0100 | [diff] [blame] | 166 | while (gc_sp > gc_stack) { |
| 167 | // pop the next block off the stack |
| 168 | machine_uint_t block = *--gc_sp; |
| 169 | |
Damien | eefcc79 | 2013-10-22 15:25:25 +0100 | [diff] [blame] | 170 | // work out number of consecutive blocks in the chain starting with this one |
Damien | dcced92 | 2013-10-21 23:45:08 +0100 | [diff] [blame] | 171 | 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 Sokolovsky | 520e2f5 | 2014-02-12 18:31:30 +0200 | [diff] [blame] | 185 | STATIC void gc_deal_with_stack_overflow(void) { |
Damien | dcced92 | 2013-10-21 23:45:08 +0100 | [diff] [blame] | 186 | 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 Sokolovsky | 520e2f5 | 2014-02-12 18:31:30 +0200 | [diff] [blame] | 201 | STATIC void gc_sweep(void) { |
Damien | dcced92 | 2013-10-21 23:45:08 +0100 | [diff] [blame] | 202 | // 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 George | 12bab72 | 2014-04-05 20:35:48 +0100 | [diff] [blame^] | 207 | #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 | } |
mux | 4f7e9f5 | 2014-04-03 23:55:12 +0200 | [diff] [blame] | 218 | } |
Damien George | 12bab72 | 2014-04-05 20:35:48 +0100 | [diff] [blame^] | 219 | // clear finaliser flag |
| 220 | FTB_CLEAR(block); |
mux | 4f7e9f5 | 2014-04-03 23:55:12 +0200 | [diff] [blame] | 221 | } |
Damien George | 12bab72 | 2014-04-05 20:35:48 +0100 | [diff] [blame^] | 222 | #endif |
Damien | dcced92 | 2013-10-21 23:45:08 +0100 | [diff] [blame] | 223 | 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 | |
Damien | 8b3a7c2 | 2013-10-23 20:20:17 +0100 | [diff] [blame] | 240 | void gc_collect_start(void) { |
Damien George | 12bab72 | 2014-04-05 20:35:48 +0100 | [diff] [blame^] | 241 | gc_lock = true; |
Damien | dcced92 | 2013-10-21 23:45:08 +0100 | [diff] [blame] | 242 | gc_stack_overflow = 0; |
| 243 | gc_sp = gc_stack; |
| 244 | } |
| 245 | |
| 246 | void 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 | |
Damien | 8b3a7c2 | 2013-10-23 20:20:17 +0100 | [diff] [blame] | 254 | void gc_collect_end(void) { |
Damien | dcced92 | 2013-10-21 23:45:08 +0100 | [diff] [blame] | 255 | gc_deal_with_stack_overflow(); |
| 256 | gc_sweep(); |
Damien George | 12bab72 | 2014-04-05 20:35:48 +0100 | [diff] [blame^] | 257 | gc_lock = false; |
Damien | eefcc79 | 2013-10-22 15:25:25 +0100 | [diff] [blame] | 258 | } |
Damien | dcced92 | 2013-10-21 23:45:08 +0100 | [diff] [blame] | 259 | |
Damien | eefcc79 | 2013-10-22 15:25:25 +0100 | [diff] [blame] | 260 | void 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) { |
Damien | dcced92 | 2013-10-21 23:45:08 +0100 | [diff] [blame] | 280 | case AT_FREE: |
Damien | eefcc79 | 2013-10-22 15:25:25 +0100 | [diff] [blame] | 281 | info->free += 1; |
| 282 | len = 0; |
Damien | dcced92 | 2013-10-21 23:45:08 +0100 | [diff] [blame] | 283 | break; |
| 284 | |
| 285 | case AT_HEAD: |
Damien | eefcc79 | 2013-10-22 15:25:25 +0100 | [diff] [blame] | 286 | info->used += 1; |
| 287 | len = 1; |
| 288 | break; |
| 289 | |
Damien | dcced92 | 2013-10-21 23:45:08 +0100 | [diff] [blame] | 290 | case AT_TAIL: |
Damien | eefcc79 | 2013-10-22 15:25:25 +0100 | [diff] [blame] | 291 | info->used += 1; |
| 292 | len += 1; |
Damien | dcced92 | 2013-10-21 23:45:08 +0100 | [diff] [blame] | 293 | break; |
| 294 | |
| 295 | case AT_MARK: |
Damien | eefcc79 | 2013-10-22 15:25:25 +0100 | [diff] [blame] | 296 | // shouldn't happen |
Damien | dcced92 | 2013-10-21 23:45:08 +0100 | [diff] [blame] | 297 | break; |
| 298 | } |
| 299 | } |
| 300 | |
Damien | eefcc79 | 2013-10-22 15:25:25 +0100 | [diff] [blame] | 301 | info->used *= BYTES_PER_BLOCK; |
| 302 | info->free *= BYTES_PER_BLOCK; |
Damien | dcced92 | 2013-10-21 23:45:08 +0100 | [diff] [blame] | 303 | } |
| 304 | |
Damien George | 12bab72 | 2014-04-05 20:35:48 +0100 | [diff] [blame^] | 305 | void *gc_alloc(machine_uint_t n_bytes, bool has_finaliser) { |
Damien | dcced92 | 2013-10-21 23:45:08 +0100 | [diff] [blame] | 306 | machine_uint_t n_blocks = ((n_bytes + BYTES_PER_BLOCK - 1) & (~(BYTES_PER_BLOCK - 1))) / BYTES_PER_BLOCK; |
Damien George | ce1162a | 2014-02-26 22:55:59 +0000 | [diff] [blame] | 307 | DEBUG_printf("gc_alloc(" UINT_FMT " bytes -> " UINT_FMT " blocks)\n", n_bytes, n_blocks); |
Damien | dcced92 | 2013-10-21 23:45:08 +0100 | [diff] [blame] | 308 | |
Damien George | 12bab72 | 2014-04-05 20:35:48 +0100 | [diff] [blame^] | 309 | if (gc_lock) { |
| 310 | // TODO |
| 311 | } |
| 312 | |
Damien | dcced92 | 2013-10-21 23:45:08 +0100 | [diff] [blame] | 313 | // 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 Sokolovsky | 723a6ed | 2014-02-11 18:01:38 +0200 | [diff] [blame] | 338 | DEBUG_printf("gc_alloc(" UINT_FMT "): no free mem, triggering GC\n", n_bytes); |
Damien | dcced92 | 2013-10-21 23:45:08 +0100 | [diff] [blame] | 339 | gc_collect(); |
| 340 | collected = 1; |
| 341 | } |
| 342 | |
| 343 | // found, ending at block i inclusive |
| 344 | found: |
| 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 George | 12bab72 | 2014-04-05 20:35:48 +0100 | [diff] [blame^] | 358 | // get pointer to first block |
| 359 | void *ret_ptr = (void*)(gc_pool_start + start_block * WORDS_PER_BLOCK); |
mux | cc849f7 | 2014-04-05 15:49:03 +0200 | [diff] [blame] | 360 | |
Damien George | 12bab72 | 2014-04-05 20:35:48 +0100 | [diff] [blame^] | 361 | #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; |
Damien | dcced92 | 2013-10-21 23:45:08 +0100 | [diff] [blame] | 371 | } |
| 372 | |
Damien George | 12bab72 | 2014-04-05 20:35:48 +0100 | [diff] [blame^] | 373 | /* |
mux | 4f7e9f5 | 2014-04-03 23:55:12 +0200 | [diff] [blame] | 374 | void *gc_alloc(machine_uint_t n_bytes) { |
| 375 | return _gc_alloc(n_bytes, false); |
| 376 | } |
| 377 | |
Damien George | 12bab72 | 2014-04-05 20:35:48 +0100 | [diff] [blame^] | 378 | void *gc_alloc_with_finaliser(machine_uint_t n_bytes) { |
mux | 4f7e9f5 | 2014-04-03 23:55:12 +0200 | [diff] [blame] | 379 | return _gc_alloc(n_bytes, true); |
| 380 | } |
Damien George | 12bab72 | 2014-04-05 20:35:48 +0100 | [diff] [blame^] | 381 | */ |
mux | 4f7e9f5 | 2014-04-03 23:55:12 +0200 | [diff] [blame] | 382 | |
Damien | fd8b6bc | 2013-10-22 20:26:36 +0100 | [diff] [blame] | 383 | // force the freeing of a piece of memory |
| 384 | void gc_free(void *ptr_in) { |
Damien George | 12bab72 | 2014-04-05 20:35:48 +0100 | [diff] [blame^] | 385 | if (gc_lock) { |
| 386 | // TODO |
| 387 | } |
| 388 | |
Damien | fd8b6bc | 2013-10-22 20:26:36 +0100 | [diff] [blame] | 389 | 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 | |
Damien | dcced92 | 2013-10-21 23:45:08 +0100 | [diff] [blame] | 403 | machine_uint_t gc_nbytes(void *ptr_in) { |
| 404 | machine_uint_t ptr = (machine_uint_t)ptr_in; |
| 405 | |
Damien | fd8b6bc | 2013-10-22 20:26:36 +0100 | [diff] [blame] | 406 | if (VERIFY_PTR(ptr)) { |
Damien | dcced92 | 2013-10-21 23:45:08 +0100 | [diff] [blame] | 407 | 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 | |
mux | 8782676 | 2014-03-12 21:00:23 +0200 | [diff] [blame] | 422 | #if 0 |
Damien George | 6fc765c | 2014-03-07 00:21:51 +0000 | [diff] [blame] | 423 | // use this realloc for now, one below is broken |
| 424 | void *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 | } |
mux | 8782676 | 2014-03-12 21:00:23 +0200 | [diff] [blame] | 439 | #else |
mux | fbaa147 | 2014-03-05 23:23:04 +0200 | [diff] [blame] | 440 | void *gc_realloc(void *ptr_in, machine_uint_t n_bytes) { |
Damien George | 12bab72 | 2014-04-05 20:35:48 +0100 | [diff] [blame^] | 441 | if (gc_lock) { |
| 442 | // TODO |
| 443 | } |
| 444 | |
mux | fbaa147 | 2014-03-05 23:23:04 +0200 | [diff] [blame] | 445 | void *ptr_out = NULL; |
Damien George | 73d5793 | 2014-03-06 00:02:16 +0000 | [diff] [blame] | 446 | machine_uint_t block = 0; |
mux | fbaa147 | 2014-03-05 23:23:04 +0200 | [diff] [blame] | 447 | machine_uint_t ptr = (machine_uint_t)ptr_in; |
| 448 | |
| 449 | if (ptr_in == NULL) { |
Damien George | 12bab72 | 2014-04-05 20:35:48 +0100 | [diff] [blame^] | 450 | return gc_alloc(n_bytes, false); |
Damien | dcced92 | 2013-10-21 23:45:08 +0100 | [diff] [blame] | 451 | } |
mux | fbaa147 | 2014-03-05 23:23:04 +0200 | [diff] [blame] | 452 | |
Damien George | 470184e | 2014-03-12 22:44:11 +0000 | [diff] [blame] | 453 | 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 |
mux | fbaa147 | 2014-03-05 23:23:04 +0200 | [diff] [blame] | 456 | |
| 457 | byte block_type; |
| 458 | machine_uint_t n_free = 0; |
Damien George | 470184e | 2014-03-12 22:44:11 +0000 | [diff] [blame] | 459 | machine_uint_t n_blocks = 1; // counting HEAD block |
mux | 8782676 | 2014-03-12 21:00:23 +0200 | [diff] [blame] | 460 | machine_uint_t max_block = gc_alloc_table_byte_len * BLOCKS_PER_ATB; |
mux | fbaa147 | 2014-03-05 23:23:04 +0200 | [diff] [blame] | 461 | |
Damien George | 470184e | 2014-03-12 22:44:11 +0000 | [diff] [blame] | 462 | // 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 |
mux | 8782676 | 2014-03-12 21:00:23 +0200 | [diff] [blame] | 465 | while ((block + n_blocks + n_free) < max_block |
Damien George | 470184e | 2014-03-12 22:44:11 +0000 | [diff] [blame] | 466 | // stop as soon as we find enough blocks for n_bytes |
mux | 8782676 | 2014-03-12 21:00:23 +0200 | [diff] [blame] | 467 | && (n_bytes > ((n_blocks+n_free) * BYTES_PER_BLOCK)) |
Damien George | 470184e | 2014-03-12 22:44:11 +0000 | [diff] [blame] | 468 | // stop if block is HEAD |
mux | 8782676 | 2014-03-12 21:00:23 +0200 | [diff] [blame] | 469 | && (block_type = ATB_GET_KIND(block + n_blocks + n_free)) != AT_HEAD) { |
mux | fbaa147 | 2014-03-05 23:23:04 +0200 | [diff] [blame] | 470 | switch (block_type) { |
| 471 | case AT_FREE: n_free++; break; |
| 472 | case AT_TAIL: n_blocks++; break; |
| 473 | default: break; |
| 474 | } |
mux | 8782676 | 2014-03-12 21:00:23 +0200 | [diff] [blame] | 475 | } |
Damien George | 470184e | 2014-03-12 22:44:11 +0000 | [diff] [blame] | 476 | // number of allocated bytes |
mux | fbaa147 | 2014-03-05 23:23:04 +0200 | [diff] [blame] | 477 | machine_uint_t n_existing = n_blocks * BYTES_PER_BLOCK; |
| 478 | |
Damien George | 470184e | 2014-03-12 22:44:11 +0000 | [diff] [blame] | 479 | // check if realloc'ing to a smaller size |
mux | fbaa147 | 2014-03-05 23:23:04 +0200 | [diff] [blame] | 480 | if (n_bytes <= n_existing) { |
| 481 | ptr_out = ptr_in; |
Damien George | 470184e | 2014-03-12 22:44:11 +0000 | [diff] [blame] | 482 | // free unneeded tail blocks |
Damien George | 73d5793 | 2014-03-06 00:02:16 +0000 | [diff] [blame] | 483 | for (machine_uint_t bl = block + n_blocks; ATB_GET_KIND(bl) == AT_TAIL; bl++) { |
| 484 | ATB_ANY_TO_FREE(bl); |
mux | fbaa147 | 2014-03-05 23:23:04 +0200 | [diff] [blame] | 485 | } |
| 486 | |
Damien George | 470184e | 2014-03-12 22:44:11 +0000 | [diff] [blame] | 487 | // check if we can expand in place |
mux | 8782676 | 2014-03-12 21:00:23 +0200 | [diff] [blame] | 488 | } else if (n_bytes <= (n_existing + (n_free * BYTES_PER_BLOCK))) { |
Damien George | 470184e | 2014-03-12 22:44:11 +0000 | [diff] [blame] | 489 | // number of blocks needed to expand +1 if there's a remainder |
mux | fbaa147 | 2014-03-05 23:23:04 +0200 | [diff] [blame] | 490 | 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 George | 470184e | 2014-03-12 22:44:11 +0000 | [diff] [blame] | 496 | // mark rest of blocks as used tail |
Damien George | 73d5793 | 2014-03-06 00:02:16 +0000 | [diff] [blame] | 497 | for (machine_uint_t bl = block + n_blocks; bl < (block + n_blocks + n_diff); bl++) { |
mux | fbaa147 | 2014-03-05 23:23:04 +0200 | [diff] [blame] | 498 | ATB_FREE_TO_TAIL(bl); |
| 499 | } |
| 500 | ptr_out = ptr_in; |
| 501 | |
Damien George | 470184e | 2014-03-12 22:44:11 +0000 | [diff] [blame] | 502 | // try to find a new contiguous chain |
Damien George | 12bab72 | 2014-04-05 20:35:48 +0100 | [diff] [blame^] | 503 | } 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 George | 470184e | 2014-03-12 22:44:11 +0000 | [diff] [blame] | 510 | DEBUG_printf("gc_realloc: allocating new block\n"); |
mux | fbaa147 | 2014-03-05 23:23:04 +0200 | [diff] [blame] | 511 | memcpy(ptr_out, ptr_in, n_existing); |
| 512 | gc_free(ptr_in); |
| 513 | } |
| 514 | } |
| 515 | |
| 516 | return ptr_out; |
Damien | dcced92 | 2013-10-21 23:45:08 +0100 | [diff] [blame] | 517 | } |
mux | 8782676 | 2014-03-12 21:00:23 +0200 | [diff] [blame] | 518 | |
Damien George | 6fc765c | 2014-03-07 00:21:51 +0000 | [diff] [blame] | 519 | #endif |
Damien | dcced92 | 2013-10-21 23:45:08 +0100 | [diff] [blame] | 520 | |
Paul Sokolovsky | 723a6ed | 2014-02-11 18:01:38 +0200 | [diff] [blame] | 521 | void 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 George | ce1162a | 2014-02-26 22:55:59 +0000 | [diff] [blame] | 529 | void gc_dump_alloc_table(void) { |
| 530 | printf("GC memory layout:"); |
Damien | eefcc79 | 2013-10-22 15:25:25 +0100 | [diff] [blame] | 531 | for (machine_uint_t bl = 0; bl < gc_alloc_table_byte_len * BLOCKS_PER_ATB; bl++) { |
Damien George | ce1162a | 2014-02-26 22:55:59 +0000 | [diff] [blame] | 532 | if (bl % 64 == 0) { |
| 533 | printf("\n%04x: ", (uint)bl); |
Damien | eefcc79 | 2013-10-22 15:25:25 +0100 | [diff] [blame] | 534 | } |
Damien George | ce1162a | 2014-02-26 22:55:59 +0000 | [diff] [blame] | 535 | 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); |
Damien | eefcc79 | 2013-10-22 15:25:25 +0100 | [diff] [blame] | 543 | } |
Damien George | ce1162a | 2014-02-26 22:55:59 +0000 | [diff] [blame] | 544 | printf("\n"); |
Damien | eefcc79 | 2013-10-22 15:25:25 +0100 | [diff] [blame] | 545 | } |
| 546 | |
Damien George | ce1162a | 2014-02-26 22:55:59 +0000 | [diff] [blame] | 547 | #if DEBUG_PRINT |
Paul Sokolovsky | af19cbd | 2014-02-10 21:45:54 +0200 | [diff] [blame] | 548 | void gc_test(void) { |
| 549 | machine_uint_t len = 500; |
Damien | dcced92 | 2013-10-21 23:45:08 +0100 | [diff] [blame] | 550 | machine_uint_t *heap = malloc(len); |
| 551 | gc_init(heap, heap + len / sizeof(machine_uint_t)); |
| 552 | void *ptrs[100]; |
| 553 | { |
Damien George | 12bab72 | 2014-04-05 20:35:48 +0100 | [diff] [blame^] | 554 | 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); |
Damien | dcced92 | 2013-10-21 23:45:08 +0100 | [diff] [blame] | 560 | p2[0] = p; |
| 561 | p2[1] = p; |
| 562 | ptrs[0] = p2; |
| 563 | } |
Paul Sokolovsky | af19cbd | 2014-02-10 21:45:54 +0200 | [diff] [blame] | 564 | for (int i = 0; i < 25; i+=2) { |
Damien George | 12bab72 | 2014-04-05 20:35:48 +0100 | [diff] [blame^] | 565 | machine_uint_t *p = gc_alloc(i, false); |
Damien | dcced92 | 2013-10-21 23:45:08 +0100 | [diff] [blame] | 566 | printf("p=%p\n", p); |
| 567 | if (i & 3) { |
| 568 | //ptrs[i] = p; |
| 569 | } |
| 570 | } |
| 571 | |
Paul Sokolovsky | af19cbd | 2014-02-10 21:45:54 +0200 | [diff] [blame] | 572 | printf("Before GC:\n"); |
Damien George | ce1162a | 2014-02-26 22:55:59 +0000 | [diff] [blame] | 573 | gc_dump_alloc_table(); |
Paul Sokolovsky | af19cbd | 2014-02-10 21:45:54 +0200 | [diff] [blame] | 574 | 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 George | ce1162a | 2014-02-26 22:55:59 +0000 | [diff] [blame] | 579 | gc_dump_alloc_table(); |
Damien | dcced92 | 2013-10-21 23:45:08 +0100 | [diff] [blame] | 580 | } |
Paul Sokolovsky | af19cbd | 2014-02-10 21:45:54 +0200 | [diff] [blame] | 581 | #endif |
Damien George | d3ebe48 | 2014-01-07 15:20:33 +0000 | [diff] [blame] | 582 | |
| 583 | #endif // MICROPY_ENABLE_GC |