diff options
author | Kartik K. Agaram <vc@akkartik.com> | 2017-11-03 00:40:05 -0700 |
---|---|---|
committer | Kartik K. Agaram <vc@akkartik.com> | 2017-11-03 01:49:36 -0700 |
commit | a3195d440d2f0e99400db78e5a4386691c94a9a0 (patch) | |
tree | 00ee3bff640edccd27abaa387073418105699334 | |
parent | 850822ffbfd441d05161452be28b54f882b1b378 (diff) | |
download | mu-a3195d440d2f0e99400db78e5a4386691c94a9a0.tar.gz |
4103 - continuations no longer cause memory corruption
-rw-r--r-- | 076continuation.cc | 105 | ||||
-rw-r--r-- | continuation1.mu | 23 | ||||
-rw-r--r-- | continuation2.mu | 27 | ||||
-rw-r--r-- | continuation3.mu | 21 |
4 files changed, 171 insertions, 5 deletions
diff --git a/076continuation.cc b/076continuation.cc index 3e57f226..4cfeddd5 100644 --- a/076continuation.cc +++ b/076continuation.cc @@ -8,11 +8,33 @@ //: calls the provided function. //: * 'return-continuation-until-mark' copies the top of the stack //: until the mark, and returns it as the result of -//: call-with-continuation-mark (which might be a distant ancestor on the call -//: stack; intervening calls don't return) +//: 'call-with-continuation-mark' (which might be a distant ancestor on the +//: call stack; intervening calls don't return) //: //: The resulting slice of the stack can now be called just like a regular //: function. +//: +//: See the example programs continuation*.mu to get a sense for the +//: possibilities. +//: +//: Refinements: +//: * You can call a single continuation multiple times, and it will preserve +//: the state of its local variables at each stack frame between calls. +//: The stack frames of a continuation are not destroyed until the +//: continuation goes out of scope. See continuation1.mu. +//: * 'return-continuation-until-mark' doesn't consume the mark, so you can +//: return multiple continuations based on a single mark. In combination +//: with the fact that 'return-continuation-until-mark' can return from +//: regular calls, just as long as there was an earlier call to +//: 'call-with-continuation-mark', this gives us a way to create resumable +//: functions. See continuation5.mu. +//: +//: Caveats: +//: * At the moment we can't statically type-check continuations. So we raise +//: runtime errors for a call that doesn't return a continuation when the +//: caller expects, or one that returns a continuation when the caller +//: doesn't expect it. This shouldn't cause memory corruption, though. +//: There should still be no way to lookup addresses that aren't allocated. :(before "End Mu Types Initialization") type_ordinal continuation = Type_ordinal["continuation"] = Next_type_ordinal++; @@ -113,10 +135,10 @@ case CALL_WITH_CONTINUATION_MARK: { //: todo: implement delimited continuations in Mu's memory :(before "End Globals") map<long long int, call_stack> Delimited_continuation; -long long int Next_delimited_continuation_id = 0; +long long int Next_delimited_continuation_id = 1; // 0 is null just like an address :(before "End Reset") Delimited_continuation.clear(); -Next_delimited_continuation_id = 0; +Next_delimited_continuation_id = 1; :(before "End Primitive Recipe Declarations") RETURN_CONTINUATION_UNTIL_MARK, @@ -142,6 +164,7 @@ case RETURN_CONTINUATION_UNTIL_MARK: { raise << maybe(current_recipe_name()) << " " << get(Recipe, p->running_recipe).name << '\n' << end(); break; } + trace("run") << "creating continuation " << Next_delimited_continuation_id << end(); Delimited_continuation[Next_delimited_continuation_id] = call_stack(Current_routine->calls.begin(), base); while (Current_routine->calls.begin() != base) { if (Trace_stream) { @@ -170,12 +193,21 @@ if (current_instruction().ingredients.at(0).type->atom && current_instruction().ingredients.at(0).type->name == "continuation") { // copy multiple calls on to current call stack assert(scalar(ingredients.at(0))); + trace("run") << "calling continuation " << ingredients.at(0).at(0) << end(); if (Delimited_continuation.find(ingredients.at(0).at(0)) == Delimited_continuation.end()) raise << maybe(current_recipe_name()) << "no such delimited continuation " << current_instruction().ingredients.at(0).original_string << '\n' << end(); const call_stack& new_calls = Delimited_continuation[ingredients.at(0).at(0)]; const call& caller = (SIZE(new_calls) > 1) ? *++new_calls.begin() : Current_routine->calls.front(); - for (call_stack::const_reverse_iterator p = new_calls.rbegin(); p != new_calls.rend(); ++p) + for (call_stack::const_reverse_iterator p = new_calls.rbegin(); p != new_calls.rend(); ++p) { Current_routine->calls.push_front(*p); + // ensure that the presence of a continuation keeps its stack frames from being reclaimed + int space_address = Current_routine->calls.front().default_space; + if (space_address != 0) { + int refcount = get_or_insert(Memory, space_address); + trace(9999, "mem") << "incrementing refcount of " << space_address << ": " << refcount << " -> " << refcount+1 << end(); + put(Memory, space_address, refcount+1); + } + } if (Trace_stream) { Trace_stream->callstack_depth += SIZE(new_calls); trace("trace") << "calling delimited continuation; growing callstack depth to " << Trace_stream->callstack_depth << end(); @@ -186,3 +218,66 @@ if (current_instruction().ingredients.at(0).type->atom finish_call_housekeeping(to_instruction(caller), ingredients); continue; } + +//: Ensure that the presence of a continuation keeps its stack frames from being reclaimed. + +:(scenario continuations_preserve_local_scopes) +def main [ + local-scope + k:continuation <- call-with-continuation-mark f + call k + return 34 +] +def f [ + local-scope + g +] +def g [ + local-scope + return-continuation-until-mark + a:num <- copy 35 +] +# entering main ++mem: new alloc: 1000 ++run: {k: "continuation"} <- call-with-continuation-mark {f: "recipe-literal"} +# entering f ++mem: new alloc: 1004 +# entering g ++mem: new alloc: 1007 +# return control to main ++run: return-continuation-until-mark +# no allocs abandoned yet +# finish running main ++run: call {k: "continuation"} ++run: return {34: "literal"} +# now k is reclaimed ++mem: trying to reclaim local k:continuation +# at this point all allocs in the continuation are abandoned ++mem: automatically abandoning 1007 ++mem: automatically abandoning 1004 +# finally the alloc for main is abandoned ++mem: automatically abandoning 1000 + +:(after "Begin Decrement Refcounts(canonized_x)") +if (is_mu_continuation(canonized_x)) { + int continuation_id = get_or_insert(Memory, canonized_x.value); + trace("run") << "reclaiming continuation " << continuation_id << end(); + if (continuation_id == 0) return; + const call_stack& continuation_calls = get(Delimited_continuation, continuation_id); + // temporarily push the stack frames for the continuation one last time on to the call stack + for (call_stack::const_reverse_iterator p = continuation_calls.rbegin(); p != continuation_calls.rend(); ++p) + Current_routine->calls.push_front(*p); + // reclaim their spaces while popping them + // (because reclaim_default_space() relies on the default-space being reclaimed being at the top of the stack) + for (call_stack::const_iterator p = continuation_calls.begin(); p != continuation_calls.end(); ++p) { + reclaim_default_space(); + Current_routine->calls.pop_front(); + } + return; +} + +:(code) +bool is_mu_continuation(reagent/*copy*/ x) { + canonize_type(x); + return x.type && x.type->atom && x.type->value == get(Type_ordinal, "continuation"); +} diff --git a/continuation1.mu b/continuation1.mu new file mode 100644 index 00000000..23e92f8f --- /dev/null +++ b/continuation1.mu @@ -0,0 +1,23 @@ +# example program showing that 'return-continuation-until-mark' can 'pause' a +# function call, returning a continuation, and that calling the continuation +# can 'resume' the paused function call. + +def main [ + local-scope + k:continuation <- call-with-continuation-mark create-yielder + { + x:num, done?:bool <- call k # should return 1 + break-if done? + $print x 10/newline + loop + } +] + +def create-yielder -> n:num, done?:bool [ + local-scope + load-ingredients + n <- copy 0 + return-continuation-until-mark + done?:bool <- greater-or-equal n, 3 + n <- add n, 1 +] diff --git a/continuation2.mu b/continuation2.mu new file mode 100644 index 00000000..dda9d566 --- /dev/null +++ b/continuation2.mu @@ -0,0 +1,27 @@ +# example program showing that a 'paused' continuation can be 'resumed' +# multiple times from the same point (but with changes to data) + +def main [ + local-scope + l:&:list:num <- copy 0 + l <- push 3, l + l <- push 2, l + l <- push 1, l + k:continuation <- call-with-continuation-mark create-yielder, l + { + x:num, done?:bool <- call k + break-if done? + $print x 10/newline + loop + } +] + +def create-yielder l:&:list:num -> n:num, done?:bool [ + local-scope + load-ingredients + return-continuation-until-mark + done? <- equal l, 0 + return-if done?, 0 + n <- first l + l <- rest l +] diff --git a/continuation3.mu b/continuation3.mu new file mode 100644 index 00000000..043828d5 --- /dev/null +++ b/continuation3.mu @@ -0,0 +1,21 @@ +# example program showing that a function call can be 'paused' multiple times, +# creating different continuation values + +def main [ + local-scope + $print [caller 0] 10/newline + k:continuation <- call-with-continuation-mark f + $print [caller 1] 10/newline + k <- call k + $print [caller 2] 10/newline + call k +] + +def f [ + local-scope + $print [callee 0] 10/newline + return-continuation-until-mark + $print [callee 1] 10/newline + return-continuation-until-mark + $print [callee 2] 10/newline +] |