X-Git-Url: https://git.gag.com/?a=blobdiff_plain;f=src%2Flisp%2Fao_lisp_mem.c;h=0dfad1d7c87bcc6286b924698730a63a849c3dcb;hb=8bf6b8989a4f365467fae38a03570d277f362ac2;hp=e7ece96036ae1d31ce17f5d1a4a463385d3453f3;hpb=c0a56550cf647a1647392557e82bcaa96934cd51;p=fw%2Faltos diff --git a/src/lisp/ao_lisp_mem.c b/src/lisp/ao_lisp_mem.c index e7ece960..0dfad1d7 100644 --- a/src/lisp/ao_lisp_mem.c +++ b/src/lisp/ao_lisp_mem.c @@ -36,10 +36,6 @@ uint8_t ao_lisp_pool[AO_LISP_POOL + AO_LISP_POOL_EXTRA] __attribute__((aligned(4 #endif -#if 0 -#define MDBG_POOL -#endif - #if DBG_MEM int dbg_move_depth; int dbg_mem = DBG_MEM_START; @@ -148,6 +144,7 @@ struct ao_lisp_root { static struct ao_lisp_cons *save_cons[2]; static char *save_string[2]; +static struct ao_lisp_stack *save_stack[3]; static ao_poly save_poly[2]; static const struct ao_lisp_root ao_lisp_root[] = { @@ -159,6 +156,18 @@ static const struct ao_lisp_root ao_lisp_root[] = { .type = &ao_lisp_cons_type, .addr = (void **) &save_cons[1], }, + { + .type = &ao_lisp_stack_type, + .addr = (void **) &save_stack[0] + }, + { + .type = &ao_lisp_stack_type, + .addr = (void **) &save_stack[1] + }, + { + .type = &ao_lisp_stack_type, + .addr = (void **) &save_stack[2] + }, { .type = &ao_lisp_string_type, .addr = (void **) &save_string[0] @@ -214,8 +223,16 @@ static const struct ao_lisp_root ao_lisp_root[] = { static const void ** const ao_lisp_cache[] = { (const void **) &ao_lisp_cons_free_list, (const void **) &ao_lisp_stack_free_list, + (const void **) &ao_lisp_frame_free_list[0], + (const void **) &ao_lisp_frame_free_list[1], + (const void **) &ao_lisp_frame_free_list[2], + (const void **) &ao_lisp_frame_free_list[3], }; +#if AO_LISP_FRAME_FREE != 4 +#error Unexpected AO_LISP_FRAME_FREE value +#endif + #define AO_LISP_CACHE (sizeof (ao_lisp_cache) / sizeof (ao_lisp_cache[0])) #define AO_LISP_BUSY_SIZE ((AO_LISP_POOL + 31) / 32) @@ -248,23 +265,6 @@ static inline uint16_t pool_offset(void *addr) { return ((uint8_t *) addr) - ao_lisp_pool; } -/* - * Convert back and forth between 'poly's used - * as short addresses in the pool and addresses. - * These are used in the chunk code. - */ -static inline ao_poly pool_poly(void *addr) { -#if DBG_MEM - if (!AO_LISP_IS_POOL(addr)) - ao_lisp_abort(); -#endif - return ((uint8_t *) addr) - AO_LISP_POOL_BASE; -} - -static inline void *pool_ref(ao_poly p) { - return AO_LISP_POOL_BASE + p; -} - static inline void mark(uint8_t *tag, int offset) { int byte = offset >> 5; int bit = (offset >> 2) & 7; @@ -303,37 +303,70 @@ note_cons(void *addr) } } -static uint16_t chunk_low; +static uint16_t chunk_low, chunk_high; static uint16_t chunk_first, chunk_last; +static int chunk_busy; static void note_chunk(uint16_t addr, uint16_t size) { - int i; + int l, r; - if (addr < chunk_low) + if (addr < chunk_low || chunk_high <= addr) return; - for (i = 0; i < AO_LISP_NCHUNK; i++) { - if (ao_lisp_chunk[i].size && ao_lisp_chunk[i].old_addr == addr) { + /* Binary search for the location */ + l = 0; + r = chunk_busy - 1; + while (l <= r) { + int m = (l + r) >> 1; + if (ao_lisp_chunk[m].old_addr < addr) + l = m + 1; + else + r = m - 1; + } + /* + * The correct location is always in 'l', with r = l-1 being + * the entry before the right one + */ + #if DBG_MEM - if (ao_lisp_chunk[i].size != size) - ao_lisp_abort(); + /* Off the right side */ + if (l >= AO_LISP_NCHUNK) + ao_lisp_abort(); + + /* Off the left side */ + if (l == 0 && chunk_busy && addr > ao_lisp_chunk[0].old_addr) + ao_lisp_abort(); #endif - return; - } - if (ao_lisp_chunk[i].old_addr > addr) { - memmove(&ao_lisp_chunk[i+1], - &ao_lisp_chunk[i], - (AO_LISP_NCHUNK - (i+1)) * sizeof (struct ao_lisp_chunk)); - ao_lisp_chunk[i].size = 0; - } - if (ao_lisp_chunk[i].size == 0) { - ao_lisp_chunk[i].old_addr = addr; - ao_lisp_chunk[i].size = size; - return; - } - } + + /* Shuffle existing entries right */ + int end = min(AO_LISP_NCHUNK, chunk_busy + 1); + + memmove(&ao_lisp_chunk[l+1], + &ao_lisp_chunk[l], + (end - (l+1)) * sizeof (struct ao_lisp_chunk)); + + /* Add new entry */ + ao_lisp_chunk[l].old_addr = addr; + ao_lisp_chunk[l].size = size; + + /* Increment the number of elements up to the size of the array */ + if (chunk_busy < AO_LISP_NCHUNK) + chunk_busy++; + + /* Set the top address if the array is full */ + if (chunk_busy == AO_LISP_NCHUNK) + chunk_high = ao_lisp_chunk[AO_LISP_NCHUNK-1].old_addr + + ao_lisp_chunk[AO_LISP_NCHUNK-1].size; +} + +static void +reset_chunks(void) +{ + memset(ao_lisp_chunk, '\0', sizeof (ao_lisp_chunk)); + chunk_high = ao_lisp_top; + chunk_busy = 0; } /* @@ -414,6 +447,7 @@ static const struct ao_lisp_type const *ao_lisp_types[AO_LISP_NUM_TYPE] = { [AO_LISP_BUILTIN] = &ao_lisp_builtin_type, [AO_LISP_FRAME] = &ao_lisp_frame_type, [AO_LISP_LAMBDA] = &ao_lisp_lambda_type, + [AO_LISP_STACK] = &ao_lisp_stack_type, }; static int @@ -428,15 +462,20 @@ ao_lisp_poly_mark_ref(ao_poly *p, uint8_t do_note_cons) return ao_lisp_poly_mark(*p, do_note_cons); } -int ao_lisp_collects; +int ao_lisp_collects[2]; +int ao_lisp_freed[2]; +int ao_lisp_loops[2]; -void -ao_lisp_collect(void) +int ao_lisp_last_top; + +int +ao_lisp_collect(uint8_t style) { + int ret; int i; int top; -#if DBG_MEM int loops = 0; +#if DBG_MEM int marked; int moved; struct ao_lisp_record *mark_record = NULL, *move_record = NULL; @@ -445,18 +484,23 @@ ao_lisp_collect(void) marked = moved = 0; #endif - ++ao_lisp_collects; + /* The first time through, we're doing a full collect */ + if (ao_lisp_last_top == 0) + style = AO_LISP_COLLECT_FULL; /* Clear references to all caches */ for (i = 0; i < (int) AO_LISP_CACHE; i++) *ao_lisp_cache[i] = NULL; - chunk_low = 0; - top = 0; + if (style == AO_LISP_COLLECT_FULL) { + chunk_low = top = 0; + } else { + chunk_low = top = ao_lisp_last_top; + } for (;;) { - MDBG_DO(loops++); + loops++; MDBG_MOVE("move chunks from %d to %d\n", chunk_low, top); /* Find the sizes of the first chunk of objects to move */ - memset(ao_lisp_chunk, '\0', sizeof (ao_lisp_chunk)); + reset_chunks(); walk(ao_lisp_mark_ref, ao_lisp_poly_mark_ref); #if DBG_MEM marked = total_marked; @@ -490,7 +534,6 @@ ao_lisp_collect(void) MDBG_MOVE("chunk %d %d not moving\n", ao_lisp_chunk[i].old_addr, ao_lisp_chunk[i].size); - chunk_low = ao_lisp_chunk[i].old_addr + size; } chunk_first = i; @@ -510,7 +553,6 @@ ao_lisp_collect(void) &ao_lisp_pool[ao_lisp_chunk[i].old_addr], size); top += size; - chunk_low = ao_lisp_chunk[i].old_addr + size; } chunk_last = i; @@ -533,13 +575,26 @@ ao_lisp_collect(void) if (chunk_last != AO_LISP_NCHUNK) break; + + chunk_low = chunk_high; } + + /* Compute amount of memory freed */ + ret = ao_lisp_top - top; + + /* Collect stats */ + ++ao_lisp_collects[style]; + ao_lisp_freed[style] += ret; + ao_lisp_loops[style] += loops; + ao_lisp_top = top; + if (style == AO_LISP_COLLECT_FULL) + ao_lisp_last_top = top; MDBG_DO(memset(ao_lisp_chunk, '\0', sizeof (ao_lisp_chunk)); walk(ao_lisp_mark_ref, ao_lisp_poly_mark_ref)); -// printf ("collect. top %d loops %d\n", top, loops); + return ret; } /* @@ -729,45 +784,6 @@ ao_lisp_poly_move(ao_poly *ref, uint8_t do_note_cons) return ret; } -#ifdef MDBG_POOL -static int AO_LISP_POOL_CUR = AO_LISP_POOL / 8; - -static void -ao_lisp_poison(void) -{ - int i; - - printf("poison\n"); - ao_lisp_mark_busy(); - for (i = 0; i < AO_LISP_POOL_CUR; i += 4) { - uint32_t *a = (uint32_t *) &ao_lisp_pool[i]; - if (!busy_object(ao_lisp_busy, a)) - *a = 0xBEEFBEEF; - } - for (i = 0; i < AO_LISP_POOL_CUR; i += 2) { - ao_poly *a = (uint16_t *) &ao_lisp_pool[i]; - ao_poly p = *a; - - if (!ao_lisp_is_const(p)) { - void *r = ao_lisp_ref(p); - - if (ao_lisp_pool <= (uint8_t *) r && - (uint8_t *) r <= ao_lisp_pool + AO_LISP_POOL_CUR) - { - if (!busy_object(ao_lisp_busy, r)) { - printf("missing reference from %d to %d\n", - (int) ((uint8_t *) a - ao_lisp_pool), - (int) ((uint8_t *) r - ao_lisp_pool)); - } - } - } - } -} - -#else -#define AO_LISP_POOL_CUR AO_LISP_POOL -#endif - #if DBG_MEM void ao_lisp_validate(void) @@ -781,7 +797,6 @@ int dbg_allocs; #endif - void * ao_lisp_alloc(int size) { @@ -790,26 +805,10 @@ ao_lisp_alloc(int size) MDBG_DO(++dbg_allocs); MDBG_DO(if (dbg_validate) ao_lisp_validate()); size = ao_lisp_size_round(size); - if (ao_lisp_top + size > AO_LISP_POOL_CUR) { -#ifdef MDBG_POOL - if (AO_LISP_POOL_CUR < AO_LISP_POOL) { - AO_LISP_POOL_CUR += AO_LISP_POOL / 8; - ao_lisp_poison(); - } else -#endif - ao_lisp_collect(); -#ifdef MDBG_POOL + if (ao_lisp_top + size > AO_LISP_POOL) { + if (!ao_lisp_collect(AO_LISP_COLLECT_INCREMENTAL) && + !ao_lisp_collect(AO_LISP_COLLECT_FULL)) { - int i; - - for (i = ao_lisp_top; i < AO_LISP_POOL; i += 4) { - uint32_t *p = (uint32_t *) &ao_lisp_pool[i]; - *p = 0xbeefbeef; - } - } -#endif - - if (ao_lisp_top + size > AO_LISP_POOL) { ao_lisp_error(AO_LISP_OOM, "out of memory"); return NULL; } @@ -833,6 +832,20 @@ ao_lisp_cons_fetch(int id) return cons; } +void +ao_lisp_stack_stash(int id, struct ao_lisp_stack *stack) +{ + save_stack[id] = stack; +} + +struct ao_lisp_stack * +ao_lisp_stack_fetch(int id) +{ + struct ao_lisp_stack *stack = save_stack[id]; + save_stack[id] = NULL; + return stack; +} + void ao_lisp_string_stash(int id, char *string) {