From 29c890b4599b3bbdbd09a5915ea68a63f4e0a9ac Mon Sep 17 00:00:00 2001 From: Keith Packard Date: Fri, 11 Nov 2016 21:11:13 -0800 Subject: [PATCH] altos/lisp: Make sure memmove only happens once per object. Other GC fixes The memmove may be overlapping, so make sure it happens only once by just checking whether move_size has been set, rather than looking at ao_lisp_moving; that doesn't get set when moving a noted cons as that still needs to be walked at a later time. Fix up the various looping move functions to all use the same pattern. Atom was busted. Signed-off-by: Keith Packard --- src/lisp/ao_lisp_atom.c | 12 +++++- src/lisp/ao_lisp_cons.c | 23 ++++++++--- src/lisp/ao_lisp_eval.c | 6 ++- src/lisp/ao_lisp_frame.c | 6 +-- src/lisp/ao_lisp_mem.c | 85 ++++++++++++++++++++++------------------ 5 files changed, 81 insertions(+), 51 deletions(-) diff --git a/src/lisp/ao_lisp_atom.c b/src/lisp/ao_lisp_atom.c index efa4f621..e1d9b082 100644 --- a/src/lisp/ao_lisp_atom.c +++ b/src/lisp/ao_lisp_atom.c @@ -46,11 +46,19 @@ static void atom_mark(void *addr) static void atom_move(void *addr) { struct ao_lisp_atom *atom = addr; + int ret; for (;;) { - if (ao_lisp_poly_move(&atom->next, 0)) + struct ao_lisp_atom *next = ao_lisp_poly_atom(atom->next); + + if (!next) break; - atom = ao_lisp_poly_atom(atom->next); + ret = ao_lisp_move_memory((void **) &next, atom_size(next)); + if (next != ao_lisp_poly_atom(atom->next)) + atom->next = ao_lisp_atom_poly(next); + if (ret) + break; + atom = next; } } diff --git a/src/lisp/ao_lisp_cons.c b/src/lisp/ao_lisp_cons.c index b75ffaa0..c7d8382f 100644 --- a/src/lisp/ao_lisp_cons.c +++ b/src/lisp/ao_lisp_cons.c @@ -49,6 +49,8 @@ static void cons_move(void *addr) (void) ao_lisp_poly_move(&cons->car, 1); cdr = ao_lisp_poly_cons(cons->cdr); + if (!cdr) + break; ret = ao_lisp_move_memory((void **) &cdr, sizeof (struct ao_lisp_cons)); if (cdr != ao_lisp_poly_cons(cons->cdr)) cons->cdr = ao_lisp_cons_poly(cdr); @@ -64,20 +66,29 @@ const struct ao_lisp_type ao_lisp_cons_type = { .move = cons_move, }; +static ao_poly cons_car; +static struct ao_lisp_cons *cons_cdr; +static int been_here; + struct ao_lisp_cons * ao_lisp_cons_cons(ao_poly car, struct ao_lisp_cons *cdr) { struct ao_lisp_cons *cons; - ao_lisp_root_add(&ao_lisp_cons_type, &cdr); - ao_lisp_root_poly_add(&car); + if (!been_here) { + ao_lisp_root_add(&ao_lisp_cons_type, &cons_cdr); + ao_lisp_root_poly_add(&cons_car); + been_here = 1; + } + cons_car = car; + cons_cdr = cdr; cons = ao_lisp_alloc(sizeof (struct ao_lisp_cons)); - ao_lisp_root_clear(&car); - ao_lisp_root_clear(&cdr); if (!cons) return NULL; - cons->car = car; - cons->cdr = ao_lisp_cons_poly(cdr); + cons->car = cons_car; + cons->cdr = ao_lisp_cons_poly(cons_cdr); + cons_car = AO_LISP_NIL; + cons_cdr = NULL; return cons; } diff --git a/src/lisp/ao_lisp_eval.c b/src/lisp/ao_lisp_eval.c index ae2436b8..1c929869 100644 --- a/src/lisp/ao_lisp_eval.c +++ b/src/lisp/ao_lisp_eval.c @@ -32,6 +32,7 @@ stack_mark(void *addr) ao_lisp_poly_mark(stack->values, 0); /* no need to mark values_tail */ ao_lisp_poly_mark(stack->frame, 0); + ao_lisp_poly_mark(stack->list, 0); stack = ao_lisp_poly_stack(stack->prev); if (ao_lisp_mark_memory(stack, sizeof (struct ao_lisp_stack))) break; @@ -47,12 +48,15 @@ stack_move(void *addr) while (stack) { struct ao_lisp_stack *prev; - int ret; + int ret; (void) ao_lisp_poly_move(&stack->sexprs, 0); (void) ao_lisp_poly_move(&stack->values, 0); (void) ao_lisp_poly_move(&stack->values_tail, 0); (void) ao_lisp_poly_move(&stack->frame, 0); + (void) ao_lisp_poly_move(&stack->list, 0); prev = ao_lisp_poly_stack(stack->prev); + if (!prev) + break; ret = ao_lisp_move_memory((void **) &prev, sizeof (struct ao_lisp_stack)); if (prev != ao_lisp_poly_stack(stack->prev)) diff --git a/src/lisp/ao_lisp_frame.c b/src/lisp/ao_lisp_frame.c index 90344719..082860ee 100644 --- a/src/lisp/ao_lisp_frame.c +++ b/src/lisp/ao_lisp_frame.c @@ -83,9 +83,9 @@ frame_move(void *addr) ao_lisp_poly_move(&v->val, 0); } next = ao_lisp_poly_frame(frame->next); - ret = 1; - if (next) - ret = ao_lisp_move_memory((void **) &next, frame_size(next)); + if (!next) + break; + ret = ao_lisp_move_memory((void **) &next, frame_size(next)); if (next != ao_lisp_poly_frame(frame->next)) frame->next = ao_lisp_frame_poly(next); if (ret) diff --git a/src/lisp/ao_lisp_mem.c b/src/lisp/ao_lisp_mem.c index 1fb1b459..31ee9e1e 100644 --- a/src/lisp/ao_lisp_mem.c +++ b/src/lisp/ao_lisp_mem.c @@ -36,22 +36,20 @@ uint8_t ao_lisp_pool[AO_LISP_POOL] __attribute__((aligned(4))); #endif #if 0 +#include #define MDBG_INCLUDE -#define MDBG_DUMP 1 -#define MDBG_MOVE 0 +#if 1 +#define MDBG_MOVE(...) do { int d; for (d = 0; d < move_depth; d++) printf (" "); printf(__VA_ARGS__); } while (0) +#endif #define MDBG_OFFSET(a) ((int) ((uint8_t *) (a) - ao_lisp_pool)) #define MDBG(...) printf(__VA_ARGS__) #define MDBG_DO(a) a -static int move_dump = MDBG_MOVE; static int move_depth; -#define MDBG_RESET() (move_depth = 0) -#define MDBG_MOVE(...) do { if(move_dump) { int d; for (d = 0; d < move_depth; d++) printf (" "); printf(__VA_ARGS__); } } while (0) #define MDBG_MOVE_IN() (move_depth++) -#define MDBG_MOVE_OUT() (move_depth--) +#define MDBG_MOVE_OUT() (assert(--move_depth >= 0)) #else #define MDBG(...) #define MDBG_DO(a) -#define MDBG_RESET() #define MDBG_MOVE(...) #define MDBG_MOVE_IN() #define MDBG_MOVE_OUT() @@ -68,10 +66,12 @@ struct ao_lisp_root { static struct ao_lisp_root ao_lisp_root[AO_LISP_ROOT]; -static uint8_t ao_lisp_busy[AO_LISP_POOL / 32]; -static uint8_t ao_lisp_moving[AO_LISP_POOL / 32]; -static uint8_t ao_lisp_cons_note[AO_LISP_POOL / 32]; -static uint8_t ao_lisp_cons_last[AO_LISP_POOL / 32]; +#define AO_LISP_BUSY_SIZE ((AO_LISP_POOL + 31) / 32) + +static uint8_t ao_lisp_busy[AO_LISP_BUSY_SIZE]; +static uint8_t ao_lisp_moving[AO_LISP_BUSY_SIZE]; +static uint8_t ao_lisp_cons_note[AO_LISP_BUSY_SIZE]; +static uint8_t ao_lisp_cons_last[AO_LISP_BUSY_SIZE]; static uint8_t ao_lisp_cons_noted; uint16_t ao_lisp_top; @@ -167,9 +167,9 @@ busy_object(uint8_t *tag, void *addr) { static void note_cons(void *addr) { - MDBG_MOVE("note cons %d\n", MDBG_OFFSET(addr)); if (AO_LISP_IS_POOL(addr)) { int offset = (uint8_t *) addr - ao_lisp_pool; + MDBG_MOVE("note cons %d\n", MDBG_OFFSET(addr)); ao_lisp_cons_noted = 1; mark(ao_lisp_cons_note, offset); } @@ -180,9 +180,9 @@ note_cons(void *addr) */ static void -walk_all(uint8_t *tag, - int (*visit_addr)(const struct ao_lisp_type *type, void **addr), - int (*visit_poly)(ao_poly *p, uint8_t do_note_cons)) +walk(uint8_t *tag, + int (*visit_addr)(const struct ao_lisp_type *type, void **addr), + int (*visit_poly)(ao_poly *p, uint8_t do_note_cons)) { int i; @@ -193,13 +193,13 @@ walk_all(uint8_t *tag, if (ao_lisp_root[i].type) { void **a = ao_lisp_root[i].addr, *v; if (a && (v = *a)) { - MDBG("root %d\n", MDBG_OFFSET(v)); + MDBG("root ptr %d\n", MDBG_OFFSET(v)); visit_addr(ao_lisp_root[i].type, a); } } else { ao_poly *a = (ao_poly *) ao_lisp_root[i].addr, p; if (a && (p = *a)) { - MDBG("root 0x%04x\n", p); + MDBG("root poly %d\n", MDBG_OFFSET(ao_lisp_ref(p))); visit_poly(a, 0); } } @@ -211,7 +211,7 @@ walk_all(uint8_t *tag, for (i = 0; i < AO_LISP_POOL; i += 4) { if (busy(ao_lisp_cons_last, i)) { void *v = ao_lisp_pool + i; - MDBG("cons %d\n", MDBG_OFFSET(v)); + MDBG("root cons %d\n", MDBG_OFFSET(v)); visit_addr(&ao_lisp_cons_type, &v); } } @@ -221,12 +221,6 @@ walk_all(uint8_t *tag, static void *move_old, *move_new; static int move_size; -static void -move_object(void) -{ - walk_all(ao_lisp_moving, ao_lisp_move, ao_lisp_poly_move); -} - #if MDBG_DUMP static void dump_busy(void) @@ -273,12 +267,6 @@ ao_lisp_poly_mark_ref(ao_poly *p, uint8_t do_note_cons) return ao_lisp_poly_mark(*p, do_note_cons); } -static void -ao_lisp_mark_busy(void) -{ - walk_all(ao_lisp_busy, ao_lisp_mark_ref, ao_lisp_poly_mark_ref); -} - void ao_lisp_collect(void) { @@ -287,7 +275,7 @@ ao_lisp_collect(void) MDBG("collect\n"); /* Mark */ - ao_lisp_mark_busy(); + walk(ao_lisp_busy, ao_lisp_mark_ref, ao_lisp_poly_mark_ref); DUMP_BUSY(); /* Compact */ @@ -300,10 +288,11 @@ ao_lisp_collect(void) while(i < ao_lisp_top) { if (busy(ao_lisp_busy, i)) { MDBG("busy %d -> %d\n", i, top); + MDBG_MOVE_IN(); move_old = &ao_lisp_pool[i]; move_new = &ao_lisp_pool[top]; move_size = 0; - move_object(); + walk(ao_lisp_moving, ao_lisp_move, ao_lisp_poly_move); MDBG("\tbusy size %d\n", move_size); if (move_size == 0) ao_lisp_abort(); @@ -318,6 +307,7 @@ ao_lisp_collect(void) #if MDBG_MOVE DUMP_BUSY(); #endif + MDBG_MOVE_OUT(); } else { i += 4; } @@ -331,9 +321,15 @@ ao_lisp_mark(const struct ao_lisp_type *type, void *addr) { if (!addr) return 1; - if (mark_object(ao_lisp_busy, addr, type->size(addr))) + MDBG_MOVE_IN(); + MDBG_MOVE("mark %d\n", MDBG_OFFSET(addr)); + if (mark_object(ao_lisp_busy, addr, type->size(addr))) { + MDBG_MOVE("already marked\n"); + MDBG_MOVE_OUT(); return 1; + } type->mark(addr); + MDBG_MOVE_OUT(); return 0; } @@ -345,6 +341,7 @@ ao_lisp_poly_mark(ao_poly p, uint8_t do_note_cons) if (!p) return 1; if (type == AO_LISP_CONS && do_note_cons) { + MDBG_MOVE("note cons %d\n", MDBG_OFFSET(ao_lisp_ref(p))); note_cons(ao_lisp_ref(p)); return 0; } else { @@ -371,7 +368,7 @@ void * ao_lisp_move_map(void *addr) { if (addr == move_old) { - if (busy_object(ao_lisp_moving, addr)) + if (move_size != 0) return move_new; } return addr; @@ -382,7 +379,13 @@ check_move(void *addr, int size) { if (addr == move_old) { MDBG_MOVE("mapping %d -> %d\n", MDBG_OFFSET(addr), MDBG_OFFSET(move_new)); - if (!busy_object(ao_lisp_moving, addr)) { + if (move_size && move_size != ((size + 3) & ~3)) + ao_lisp_abort(); + + /* Only copy the object once, otherwise we may + * smash stuff + */ + if (move_size == 0) { MDBG_MOVE(" copy %d\n", size); memmove(move_new, move_old, size); move_size = (size + 3) & ~3; @@ -397,7 +400,7 @@ ao_lisp_move(const struct ao_lisp_type *type, void **ref) { void *addr = *ref; uint8_t *a = addr; - int size = type->size(addr); + int size = type->size(ao_lisp_move_map(addr)); if (!addr) return 1; @@ -462,9 +465,13 @@ ao_lisp_poly_move(ao_poly *ref, uint8_t do_note_cons) type = ao_lisp_poly_base_type(p); addr = ao_lisp_ref(p); + + if ((uint8_t *) addr < ao_lisp_pool || ao_lisp_pool + AO_LISP_POOL <= (uint8_t*) addr) + return 1; + if (type == AO_LISP_CONS && do_note_cons) { - note_cons(addr); addr = check_move(addr, sizeof (struct ao_lisp_cons)); + note_cons(addr); ret = 1; } else { @@ -482,8 +489,8 @@ ao_lisp_poly_move(ao_poly *ref, uint8_t do_note_cons) if (addr != ao_lisp_ref(p)) { ao_poly np = ao_lisp_poly(addr, p & AO_LISP_TYPE_MASK); - MDBG("poly %d moved %04x -> %04x\n", - type, p, np); + MDBG("poly %d moved %d -> %d\n", + type, MDBG_OFFSET(ao_lisp_ref(p)), MDBG_OFFSET(ao_lisp_ref(np))); *ref = np; } return ret; -- 2.30.2