From 4f747e6fffa2e80a6d62fac66eb88521e9cfc602 Mon Sep 17 00:00:00 2001 From: Stephen Dolan Date: Sun, 2 Sep 2012 21:45:27 +0100 Subject: [PATCH] Move from Jansson to JV - proper freeing of memory A few more tests, now passes valgrind. --- c/builtin.c | 5 +++++ c/execute.c | 39 +++++++++++++++++++++++++++++++-------- c/forkable_stack.h | 23 +++++++++++++++++------ c/frame_layout.h | 13 +++++++++++++ c/jv.c | 33 ++++++++++++++++++++++++++++++++- c/jv.h | 2 ++ c/main.c | 2 ++ c/testdata | 45 +++++++++++++++++++++++++++++++++++++++------ 8 files changed, 141 insertions(+), 21 deletions(-) diff --git a/c/builtin.c b/c/builtin.c index 0252566..d468e7b 100644 --- a/c/builtin.c +++ b/c/builtin.c @@ -1,15 +1,18 @@ #include "builtin.h" static void f_false(jv input[], jv output[]) { + jv_free(input[0]); output[0] = jv_false(); } static void f_true(jv input[], jv output[]) { + jv_free(input[0]); output[0] = jv_true(); } static void f_plus(jv input[], jv output[]) { + jv_free(input[0]); jv a = input[2]; jv b = input[1]; if (jv_get_kind(a) == JV_KIND_NUMBER && jv_get_kind(b) == JV_KIND_NUMBER) { @@ -19,6 +22,8 @@ static void f_plus(jv input[], jv output[]) { output[0] = jv_array_concat(a, b); } else { output[0] = jv_string("wtf gaize"); + jv_free(a); + jv_free(b); } } diff --git a/c/execute.c b/c/execute.c index 4677936..49cc183 100644 --- a/c/execute.c +++ b/c/execute.c @@ -24,6 +24,7 @@ int pathsize; // number of allocated elements // FIXME mem int path_push(stackval sv, jv val) { + return 0; int pos = sv.pathidx; assert(pos <= pathsize); assert(pos >= 0); @@ -54,17 +55,18 @@ typedef struct { stackval sv; } data_stk_elem; -void stk_push(stackval val) { +void stack_push(stackval val) { data_stk_elem* s = forkable_stack_push(&data_stk, sizeof(data_stk_elem)); s->sv = val; } -stackval stk_pop() { +stackval stack_pop() { data_stk_elem* s = forkable_stack_peek(&data_stk); stackval sv = s->sv; - if (!forkable_stack_pop(&data_stk)) { + if (!forkable_stack_pop_will_free(&data_stk)) { sv.value = jv_copy(sv.value); } + forkable_stack_pop(&data_stk); return sv; } @@ -92,6 +94,14 @@ void stack_switch() { } void stack_restore(){ + while (!forkable_stack_empty(&data_stk) && + forkable_stack_pop_will_free(&data_stk)) { + jv_free(stack_pop().value); + } + while (!forkable_stack_empty(&frame_stk) && + forkable_stack_pop_will_free(&frame_stk)) { + frame_pop(&frame_stk); + } struct forkpoint* fork = forkable_stack_peek(&fork_stk); forkable_stack_restore(&data_stk, &fork->saved_data_stack); forkable_stack_restore(&frame_stk, &fork->saved_call_stack); @@ -114,9 +124,6 @@ static struct closure make_closure(struct forkable_stack* stk, frame_ptr fr, uin } -#define stack_push stk_push -#define stack_pop stk_pop - #define ON_BACKTRACK(op) ((op)+NUM_OPCODES) jv jq_next() { @@ -142,10 +149,12 @@ jv jq_next() { if (i == 0) { param = forkable_stack_peek(&data_stk); } else { + printf(" | "); param = forkable_stack_peek_next(&data_stk, param); } + if (!param) break; jv_dump(jv_copy(param->sv.value)); - if (i < opdesc->stack_in-1) printf(" | "); + printf("<%d>", jv_get_refcnt(param->sv.value)); } if (backtracking) { @@ -294,6 +303,7 @@ jv jq_next() { int idx = jv_number_value(stack_pop().value); stackval array = stack_pop(); if (idx >= jv_array_length(jv_copy(array.value))) { + jv_free(array.value); goto do_backtrack; } else { stack_save(); @@ -314,7 +324,7 @@ jv jq_next() { do_backtrack: case BACKTRACK: { if (forkable_stack_empty(&fork_stk)) { - // FIXME: invalid + // FIXME: invalid jv value return jv_null(); } stack_restore(); @@ -407,6 +417,7 @@ void jq_init(struct bytecode* bc, jv input) { forkable_stack_init(&data_stk, sizeof(stackval) * 1000); // FIXME: lower this number, see if it breaks forkable_stack_init(&frame_stk, 10240); // FIXME: lower this number, see if it breaks forkable_stack_init(&fork_stk, 10240); // FIXME: lower this number, see if it breaks + stack_save(); stack_push(stackval_root(input)); struct closure top = {bc, -1}; @@ -414,6 +425,18 @@ void jq_init(struct bytecode* bc, jv input) { frame_push_backtrack(&frame_stk, bc->code); } +void jq_teardown() { + while (!forkable_stack_empty(&fork_stk)) { + stack_restore(); + } + assert(forkable_stack_empty(&fork_stk)); + assert(forkable_stack_empty(&data_stk)); + assert(forkable_stack_empty(&frame_stk)); + forkable_stack_free(&fork_stk); + forkable_stack_free(&data_stk); + forkable_stack_free(&frame_stk); +} + void run_program(struct bytecode* bc) { char buf[4096]; fgets(buf, sizeof(buf), stdin); diff --git a/c/forkable_stack.h b/c/forkable_stack.h index 9283198..3128a6c 100644 --- a/c/forkable_stack.h +++ b/c/forkable_stack.h @@ -46,6 +46,13 @@ static void forkable_stack_init(struct forkable_stack* s, size_t sz) { forkable_stack_check(s); } +static void forkable_stack_free(struct forkable_stack* s) { + assert(forkable_stack_empty(s)); + assert(s->savedlimit == s->length); + free(s->stk); + s->stk = 0; +} + static void* forkable_stack_push(struct forkable_stack* s, size_t size) { forkable_stack_check(s); int curr = s->pos < s->savedlimit ? s->pos : s->savedlimit; @@ -83,14 +90,16 @@ static void* forkable_stack_peek_next(struct forkable_stack* s, void* top) { } } -// Returns 1 if the object being popped can not be accessed again -// (i.e. was not saved with a fork) -static int forkable_stack_pop(struct forkable_stack* s) { +// Returns 1 if the next forkable_stack_pop will permanently remove an +// object from the stack (i.e. the top object was not saved with a fork) +static int forkable_stack_pop_will_free(struct forkable_stack* s) { + return s->pos < s->savedlimit ? 1 : 0; +} + +static void forkable_stack_pop(struct forkable_stack* s) { forkable_stack_check(s); - int finalpop = s->pos < s->savedlimit ? 1 : 0; struct forkable_stack_header* elem = forkable_stack_peek(s); s->pos = elem->next; - return finalpop; } @@ -114,12 +123,14 @@ static void forkable_stack_switch(struct forkable_stack* s, struct forkable_stac int curr_limit = s->savedlimit; if (curr_pos < curr_limit) s->savedlimit = curr_pos; - state->prevlimit = curr_limit; + //state->prevlimit = curr_limit; FIXME clean up forkable_stack_check(s); } static void forkable_stack_restore(struct forkable_stack* s, struct forkable_stack_state* state) { forkable_stack_check(s); + assert(s->savedlimit <= state->prevpos); + assert(s->savedlimit <= state->prevlimit); s->pos = state->prevpos; s->savedlimit = state->prevlimit; forkable_stack_check(s); diff --git a/c/frame_layout.h b/c/frame_layout.h index 141dbcd..d2218e9 100644 --- a/c/frame_layout.h +++ b/c/frame_layout.h @@ -11,6 +11,8 @@ struct continuation { struct bytecode* bc; stack_idx env; uint16_t* retaddr; + // FIXME: probably not necessary as a separate field + int is_backtrack_frame; }; typedef union frame_elem { @@ -84,6 +86,7 @@ static frame_ptr frame_push(struct forkable_stack* stk, struct closure cl, uint1 cc->bc = cl.bc; cc->env = cl.env; cc->retaddr = retaddr; + cc->is_backtrack_frame = 0; for (int i=0; inlocals; i++) { *frame_local_var(fp, i) = jv_null(); } @@ -93,12 +96,22 @@ static frame_ptr frame_push(struct forkable_stack* stk, struct closure cl, uint1 static frame_ptr frame_push_backtrack(struct forkable_stack* stk, uint16_t* retaddr) { struct continuation cc = *frame_self(frame_current(stk)); frame_ptr fp = forkable_stack_push(stk, sizeof(union frame_elem) * 2); + assert(!cc.is_backtrack_frame); + cc.is_backtrack_frame = 1; cc.retaddr = retaddr; *frame_self(fp) = cc; return fp; } static void frame_pop(struct forkable_stack* stk) { + frame_ptr fp = frame_current(stk); + if (forkable_stack_pop_will_free(stk) && + !frame_self(fp)->is_backtrack_frame) { + int nlocals = frame_self(fp)->bc->nlocals; + for (int i=0; i #include #include +#include #include #include "jv.h" @@ -641,6 +642,21 @@ static int jvp_object_length(jv_complex* object) { return n; } +static int jvp_object_equal(jv_complex* o1, jv_complex* o2) { + int len2 = jvp_object_length(o2); + int len1 = 0; + for (int i=0; istring) continue; + jv* slot2 = jvp_object_read(o2, slot->string); + if (!slot2) return 0; + // FIXME: do less refcounting here + if (!jv_equal(jv_copy(slot->value), jv_copy(*slot2))) return 0; + len1++; + } + return len1 == len2; +} + /* * Objects (public interface) */ @@ -752,6 +768,17 @@ void jv_free(jv j) { } } +int jv_get_refcnt(jv j) { + switch (jv_get_kind(j)) { + case JV_KIND_ARRAY: + case JV_KIND_STRING: + case JV_KIND_OBJECT: + return j.val.complex.ptr->count; + default: + return 1; + } +} + /* * Higher-level operations */ @@ -772,7 +799,11 @@ int jv_equal(jv a, jv b) { case JV_KIND_STRING: { r = jvp_string_equal(&a.val.complex, &b.val.complex); break; - } + } + case JV_KIND_OBJECT: { + r = jvp_object_equal(&a.val.complex, &b.val.complex); + break; + } default: r = 1; break; diff --git a/c/jv.h b/c/jv.h index 7696b03..c03967b 100644 --- a/c/jv.h +++ b/c/jv.h @@ -82,6 +82,8 @@ jv jv_object_iter_key(jv, int); jv jv_object_iter_value(jv, int); +int jv_get_refcnt(jv); + void jv_dump(jv); jv jv_parse(const char* string); diff --git a/c/main.c b/c/main.c index 077268b..4d4081f 100644 --- a/c/main.c +++ b/c/main.c @@ -8,6 +8,7 @@ block compile(const char* str); void jq_init(struct bytecode* bc, jv value); jv jq_next(); +void jq_teardown(); void run_program(struct bytecode* bc); @@ -67,6 +68,7 @@ void run_tests() { pass = 0; }*/ } + jq_teardown(); bytecode_free(bc); tests++; passed+=pass; diff --git a/c/testdata b/c/testdata index 95e4078..2cdaaa5 100644 --- a/c/testdata +++ b/c/testdata @@ -76,6 +76,27 @@ null 2 3 +1,1 +[] +1 +1 + +[.] +[2] +[[2]] + +[[2]] +[3] +[[2]] + +[{}] +[2] +[{}] + +[.[]] +["a"] +["a"] + [(.,1),((.,.[]),(2,3))] ["a","b"] [["a","b"],1,["a","b"],"a","b",2,3] @@ -118,7 +139,7 @@ null 1+1 null -2.0 +2 .+4 15 @@ -143,11 +164,17 @@ def f: (1000,2000); f 1000 2000 -# test backtracking through function calls and returns -# this test is *evil* -[[20,10][1,0] as $x | def f: (100,200) as $y | def g: [$x + $y, .]; . + $x | g; f[0] | [f][0][1] | f] -"woo, testing!" -[[110.0, 130.0], [210.0, 130.0], [110.0, 230.0], [210.0, 230.0], [120.0, 160.0], [220.0, 160.0], [120.0, 260.0], [220.0, 260.0]] +([1,2] + [4,5]) +[1,2,3] +[1,2,4,5] + +true +[1] +true + +[1,2,3] +[5,6] +[1,2,3] def f(x): x | x; f([.], . + [42]) [1,2,3] @@ -160,3 +187,9 @@ def f(x): x | x; f([.], . + [42]) def id(x):x; 2000 as $x | def f(x):1 as $x | id([$x, x, x]); def g(x): 100 as $x | f($x,$x+x); g($x) "more testing" [1,100,2100.0,100,2100.0] + +# test backtracking through function calls and returns +# this test is *evil* +[[20,10][1,0] as $x | def f: (100,200) as $y | def g: [$x + $y, .]; . + $x | g; f[0] | [f][0][1] | f] +"woo, testing!" +[[110.0, 130.0], [210.0, 130.0], [110.0, 230.0], [210.0, 230.0], [120.0, 160.0], [220.0, 160.0], [120.0, 260.0], [220.0, 260.0]] -- 2.40.0