From 514f0e34aa25317e069d9a154fe76826829a8d88 Mon Sep 17 00:00:00 2001 From: "Kartik K. Agaram" Date: Sun, 22 Oct 2017 23:14:19 -0700 Subject: 4089 Clean up how we reclaim local scopes. It used to work like this (commit 3216): 1. Update refcounts of products after every instruction, EXCEPT: a) when instruction is a non-primitive and the callee starts with 'local-scope' (because it's already not decremented in 'return') OR: b) when instruction is primitive 'next-ingredient' or 'next-ingredient-without-typechecking', and its result is saved to a variable in the default space (because it's already incremented at the time of the call) 2. If a function starts with 'local-scope', force it to be reclaimed before each return. However, since locals may be returned, *very carefully* don't reclaim those. (See the logic in the old `escaping` and `should_update_refcount` functions.) However, this approach had issues. We needed two separate commands for 'local-scope' (reclaim locals on exit) and 'new-default-space' (programmer takes charge of reclaiming locals). The hard-coded reclamation duplicated refcounting logic. In addition to adding complexity, this implementation failed to work if a function overwrites default-space after setting up a local-scope (the old default-space is leaked). It also fails in the presence of continuations. Calling a continuation more than once was guaranteed to corrupt memory (commit 3986). After this commit, reclaiming local scopes now works like this: Update refcounts of products for every PRIMITIVE instruction. For non-primitive instructions, all the work happens in the `return` instruction: increment refcount of ingredients to `return` (unless -- one last bit of ugliness -- they aren't saved in the caller) decrement the refcount of the default-space use existing infrastructure for reclaiming as necessary if reclaiming default-space, first decrement refcount of each local again, use existing infrastructure for reclaiming as necessary This commit (finally!) completes the bulk[1] of step 2 of the plan in commit 3991. It was very hard until I gave up trying to tweak the existing implementation and just test-drove layer 43 from scratch. [1] There's still potential for memory corruption if we abuse `default-space`. I should probably try to add warnings about that at some point (todo in layer 45). --- 001help.cc | 4 + 003trace.cc | 1 - 020run.cc | 8 +- 028call_return.cc | 4 +- 036refcount.cc | 21 ++--- 043space.cc | 175 ++++++++++++++++++-------------------- 045closure_name.cc | 5 +- 053recipe_header.cc | 4 - 057immutable.cc | 2 +- 062convert_ingredients_to_text.cc | 9 ++ 071deep_copy.cc | 7 +- counters.mu | 2 +- 12 files changed, 124 insertions(+), 118 deletions(-) diff --git a/001help.cc b/001help.cc index 45ab7bf1..814bdde7 100644 --- a/001help.cc +++ b/001help.cc @@ -256,3 +256,7 @@ using std::cerr; using std::string; #define unused __attribute__((unused)) + +#include +using std::min; +using std::max; diff --git a/003trace.cc b/003trace.cc index ea0c2882..e388b0f7 100644 --- a/003trace.cc +++ b/003trace.cc @@ -386,7 +386,6 @@ using std::list; using std::map; #include using std::set; -#include #include using std::istringstream; diff --git a/020run.cc b/020run.cc index c4df88bd..d1bc77f4 100644 --- a/020run.cc +++ b/020run.cc @@ -95,15 +95,15 @@ void run_current_routine() { } //: used by a later layer if (write_products) { - Writing_products_of_instruction = true; if (SIZE(products) < SIZE(current_instruction().products)) { raise << SIZE(products) << " vs " << SIZE(current_instruction().products) << ": failed to write to all products in '" << to_original_string(current_instruction()) << "'\n" << end(); } else { - for (int i = 0; i < SIZE(current_instruction().products); ++i) + for (int i = 0; i < SIZE(current_instruction().products); ++i) { + // Writing Instruction Product(i) write_memory(current_instruction().products.at(i), products.at(i)); + } } - Writing_products_of_instruction = false; } // End Running One Instruction if (fall_through_to_next_instruction) @@ -111,8 +111,6 @@ void run_current_routine() { } stop_running_current_routine:; } -:(before "End Globals") -bool Writing_products_of_instruction = false; :(code) //: hook replaced in a later layer diff --git a/028call_return.cc b/028call_return.cc index 0227acee..d77e1fa7 100644 --- a/028call_return.cc +++ b/028call_return.cc @@ -35,7 +35,7 @@ case RETURN: { } :(before "End Primitive Recipe Implementations") case RETURN: { - // Starting Reply + // Begin Return if (Trace_stream) { trace(9999, "trace") << current_instruction().name << ": decrementing callstack depth from " << Trace_stream->callstack_depth << end(); --Trace_stream->callstack_depth; @@ -51,7 +51,7 @@ case RETURN: { trace(9998, "run") << "result " << i << " is " << to_string(ingredients.at(i)) << end(); // make return products available to caller copy(ingredients.begin(), ingredients.end(), inserter(products, products.begin())); - // End Reply + // End Return break; // continue to process rest of *caller* instruction } diff --git a/036refcount.cc b/036refcount.cc index 477dc011..1f31bcbb 100644 --- a/036refcount.cc +++ b/036refcount.cc @@ -17,8 +17,12 @@ def main [ +run: {2: ("address" "number")} <- copy {0: "literal"} +mem: decrementing refcount of 1000: 1 -> 0 -:(before "End write_memory(x) Special-cases") -update_any_refcounts(x, data); +:(after "Writing Instruction Product(i)") +if (is_primitive(current_instruction().operation)) { + reagent/*copy*/ tmp = current_instruction().products.at(i); + canonize(tmp); + update_any_refcounts(tmp, products.at(i)); +} :(before "End Globals") bool Reclaim_memory = true; @@ -30,17 +34,10 @@ else if (is_equal(*arg, "--no-reclaim")) { :(code) void update_any_refcounts(const reagent& canonized_x, const vector& data) { if (!Reclaim_memory) return; - if (!should_update_refcounts()) return; increment_any_refcounts(canonized_x, data); // increment first so we don't reclaim on x <- copy x decrement_any_refcounts(canonized_x); } -//: escape hatch for a later layer -bool should_update_refcounts() { - // End should_update_refcounts() Special-cases - return true; -} - void increment_any_refcounts(const reagent& canonized_x, const vector& data) { if (is_mu_address(canonized_x)) { assert(scalar(data)); @@ -60,8 +57,8 @@ void increment_refcount(int new_address) { } void decrement_any_refcounts(const reagent& canonized_x) { - if (is_mu_address(canonized_x)) { - assert(canonized_x.value); + // Begin Decrement Refcounts(canonized_x) + if (is_mu_address(canonized_x) && canonized_x.value != 0) { assert(!canonized_x.metadata.size); decrement_refcount(get_or_insert(Memory, canonized_x.value), payload_type(canonized_x.type), payload_size(canonized_x)); } @@ -1057,7 +1054,7 @@ if (Run_profiler) { Num_refcount_updates[caller_frame.running_recipe][caller_frame.running_step_index] += (Total_refcount_updates - initial_num_refcount_updates); initial_num_refcount_updates = Total_refcount_updates; -:(after "Starting Reply") +:(after "Begin Return") if (Run_profiler) { Num_refcount_updates[current_call().running_recipe][current_call().running_step_index] += (Total_refcount_updates - initial_num_refcount_updates); diff --git a/043space.cc b/043space.cc index 378b20a9..2f11c6c2 100644 --- a/043space.cc +++ b/043space.cc @@ -4,6 +4,10 @@ //: //: Spaces are often called 'scopes' in other languages. Stack frames are a //: limited form of space that can't outlive callers. +//: +//: Warning: messing with 'default-space' can corrupt memory. Don't do things +//: like initialize default-space with some other function's default-space. +//: Later we'll see how to chain spaces safely. //: Under the hood, a space is an array of locations in memory. :(before "End Mu Types Initialization") @@ -157,12 +161,12 @@ def main [ :(before "Read element" following "case INDEX:") element.properties.push_back(pair("raw", NULL)); -//:: 'new-default-space' is a convenience operation to automatically deduce +//:: 'local-scope' is a convenience operation to automatically deduce //:: the amount of space to allocate in a default space with names -:(scenario new_default_space) +:(scenario local_scope) def main [ - new-default-space + local-scope x:num <- copy 0 y:num <- copy 3 ] @@ -176,12 +180,12 @@ if (x.name == "number-of-locals") if (s == "number-of-locals") return true; :(before "End Rewrite Instruction(curr, recipe result)") -// rewrite 'new-default-space' to +// rewrite 'local-scope' to // ``` // default-space:space <- new location:type, number-of-locals:literal // ``` // where number-of-locals is Name[recipe][""] -if (curr.name == "new-default-space") { +if (curr.name == "local-scope") { rewrite_default_space_instruction(curr); } :(code) @@ -209,10 +213,9 @@ if (x.name == "number-of-locals") { return; } -//:: 'local-scope' is like 'new-default-space' except that we'll reclaim the -//:: default-space when the routine exits +//:: try to reclaim the default-space when a recipe returns -:(scenario local_scope) +:(scenario local_scope_reclaimed_on_return) def main [ 1:num <- foo 2:num <- foo @@ -226,104 +229,102 @@ def foo [ # both calls to foo should have received the same default-space +mem: storing 1 in location 3 -:(scenario local_scope_frees_up_addresses) -def main [ - local-scope - x:text <- new [abc] -] -+mem: clearing x:text - -:(before "End Rewrite Instruction(curr, recipe result)") -if (curr.name == "local-scope") { - rewrite_default_space_instruction(curr); -} - //: todo: do this in a transform, rather than magically in the 'return' instruction :(after "Falling Through End Of Recipe") -try_reclaim_locals(); -:(after "Starting Reply") -try_reclaim_locals(); - +reclaim_default_space(); +:(after "Begin Return") +reclaim_default_space(); :(code) -void try_reclaim_locals() { +void reclaim_default_space() { if (!Reclaim_memory) return; - // only reclaim routines starting with 'local-scope' const recipe_ordinal r = get(Recipe_ordinal, current_recipe_name()); const recipe& exiting_recipe = get(Recipe, r); - if (exiting_recipe.steps.empty()) return; - const instruction& inst = exiting_recipe.steps.at(0); - if (inst.name_before_rewrite != "local-scope") return; - // reclaim any local variables unless they're being returned - vector zeros; + if (!starts_by_setting_default_space(exiting_recipe)) return; + // Reclaim default-space + decrement_refcount(current_call().default_space, + exiting_recipe.steps.at(0).products.at(0).type->right, + /*refcount*/1 + /*array length*/1 + /*number-of-locals*/Name[r][""]); +} +bool starts_by_setting_default_space(const recipe& r) { + return !r.steps.empty() + && !r.steps.at(0).products.empty() + && r.steps.at(0).products.at(0).name == "default-space"; +} + +//: + +:(scenario local_scope_reclaims_locals) +def main [ + local-scope + x:text <- new [abc] +] +# x ++mem: automatically abandoning 1004 +# local-scope ++mem: automatically abandoning 1000 + +:(before "Reclaim default-space") +if (get_or_insert(Memory, current_call().default_space) <= 1) { + set reclaimed_locals; + trace(9999, "mem") << "trying to reclaim locals" << end(); for (int i = /*leave default space for last*/1; i < SIZE(exiting_recipe.steps); ++i) { const instruction& inst = exiting_recipe.steps.at(i); for (int i = 0; i < SIZE(inst.products); ++i) { - const reagent& product = inst.products.at(i); + reagent/*copy*/ product = inst.products.at(i); + if (reclaimed_locals.find(product.name) != reclaimed_locals.end()) continue; + reclaimed_locals.insert(product.name); // local variables only if (has_property(product, "lookup")) continue; if (has_property(product, "raw")) continue; // tests often want to check such locations after they run - if (escaping(product)) continue; // End Checks For Reclaiming Locals - trace(9999, "mem") << "clearing " << product.original_string << end(); - zeros.resize(size_of(product)); - write_memory(product, zeros); + trace(9999, "mem") << "trying to reclaim local " << product.original_string << end(); + canonize(product); + decrement_any_refcounts(product); } } - trace(9999, "mem") << "automatically abandoning " << current_call().default_space << end(); - abandon(current_call().default_space, - inst.products.at(0).type->right, - /*refcount*/1 + /*array length*/1 + /*number-of-locals*/Name[r][""]); } -//: Reclaiming local variables above requires remembering what name an -//: instruction had before any rewrites or transforms. -:(before "End instruction Fields") -string name_before_rewrite; -:(before "End instruction Clear") -name_before_rewrite.clear(); -:(before "End next_instruction(curr)") -curr->name_before_rewrite = curr->name; +:(scenario local_variables_can_outlive_call) +def main [ + local-scope + x:&:num <- new num:type + y:space <- copy default-space:space +] +-mem: automatically abandoning 1005 +//: + +:(scenario local_scope_does_not_reclaim_escaping_locals) +def main [ + 1:text <- foo +] +def foo [ + local-scope + x:text <- new [abc] + return x:text +] +# local-scope ++mem: automatically abandoning 1000 +# x +-mem: automatically abandoning 1004 + +:(after "Begin Return") // before reclaiming default-space +increment_refcounts_of_return_ingredients(ingredients); :(code) -// is this reagent one of the values returned by the current (return) instruction? -// is the corresponding ingredient saved in the caller? -bool escaping(const reagent& r) { - assert(Current_routine); // run-time only - // nothing escapes when you fall through past end of recipe - if (current_step_index() >= SIZE(Current_routine->steps())) return false; - for (long long i = 0; i < SIZE(current_instruction().ingredients); ++i) { - if (r == current_instruction().ingredients.at(i)) { - if (caller_uses_product(i)) - return true; +void increment_refcounts_of_return_ingredients(const vector >& ingredients) { + assert(current_instruction().operation == RETURN); + if (SIZE(Current_routine->calls) == 1) // no caller to receive result + return; + const instruction& caller_instruction = to_instruction(*++Current_routine->calls.begin()); + for (int i = 0; i < min(SIZE(current_instruction().ingredients), SIZE(caller_instruction.products)); ++i) { + if (!is_dummy(caller_instruction.products.at(i))) { + // no need to canonize ingredient because we ignore its value + increment_any_refcounts(current_instruction().ingredients.at(i), ingredients.at(i)); } } - return false; -} - -//: since we don't decrement refcounts for escaping values above, make sure we -//: don't increment them when the caller saves them either - -:(before "End should_update_refcounts() Special-cases") -if (Writing_products_of_instruction) { - const instruction& inst = current_instruction(); - // should_update_refcounts() Special-cases When Writing Products Of Primitive Instructions - if (is_primitive(inst.operation)) return true; - if (!contains_key(Recipe, inst.operation)) return true; - const recipe& callee = get(Recipe, inst.operation); - if (callee.steps.empty()) return true; - return callee.steps.at(0).name_before_rewrite != "local-scope"; // callees that call local-scope are already dealt with before return } -:(code) -bool caller_uses_product(int product_index) { - assert(Current_routine); // run-time only - assert(!Current_routine->calls.empty()); - if (Current_routine->calls.size() == 1) return false; - const call& caller = *++Current_routine->calls.begin(); - const instruction& caller_inst = to_instruction(caller); - if (product_index >= SIZE(caller_inst.products)) return false; - return !is_dummy(caller_inst.products.at(product_index)); -} +//: :(scenario local_scope_frees_up_addresses_inside_containers) container foo [ @@ -336,10 +337,6 @@ def main [ y:foo <- merge 34, x:&:num # x and y are both cleared when main returns ] -+mem: clearing x:&:num -+mem: decrementing refcount of 1006: 2 -> 1 -+mem: clearing y:foo -+mem: decrementing refcount of 1006: 1 -> 0 +mem: automatically abandoning 1006 :(scenario local_scope_returns_addresses_inside_containers) @@ -407,10 +404,8 @@ void check_default_space(const recipe_ordinal r) { if (!contains_non_special_name(r)) return; trace(9991, "transform") << "--- check that recipe " << caller.name << " sets default-space" << end(); if (caller.steps.empty()) return; - if (caller.steps.at(0).products.empty() - || caller.steps.at(0).products.at(0).name != "default-space") { + if (!starts_by_setting_default_space(caller)) raise << caller.name << " does not seem to start with 'local-scope' or 'default-space'\n" << end(); - } } :(after "Load Mu Prelude") Hide_missing_default_space_errors = false; diff --git a/045closure_name.cc b/045closure_name.cc index 7852b92e..f7c0082f 100644 --- a/045closure_name.cc +++ b/045closure_name.cc @@ -2,6 +2,9 @@ //: spaces together. When a variable has a property of /space:1, it looks up //: the variable in the chained/surrounding space. /space:2 looks up the //: surrounding space of the surrounding space, etc. +//: +//: todo: warn on default-space abuse. default-space for one function should +//: never come from another, otherwise memory will be corrupted. :(scenario closure) def main [ @@ -149,7 +152,7 @@ def f [ //: extra test for try_reclaim_locals() from previous layers :(scenario local_scope_ignores_nonlocal_spaces) def new-scope [ - new-default-space + local-scope x:&:num <- new number:type *x:&:num <- copy 34 return default-space:space diff --git a/053recipe_header.cc b/053recipe_header.cc index 9e01db42..513cfc4e 100644 --- a/053recipe_header.cc +++ b/053recipe_header.cc @@ -640,7 +640,3 @@ void check_recipe_header_constraints(const recipe_ordinal r) { raise << "recipe 'main' must return at most a single product, a number\n" << end(); } } - -:(before "End Includes") -using std::min; -using std::max; diff --git a/057immutable.cc b/057immutable.cc index e1a17a84..4657ade0 100644 --- a/057immutable.cc +++ b/057immutable.cc @@ -321,7 +321,7 @@ def main [ run-closure b:&:num, a:space ] def new-closure [ - new-default-space + local-scope x:&:num <- new number:type return default-space ] diff --git a/062convert_ingredients_to_text.cc b/062convert_ingredients_to_text.cc index cf639b9e..abbacb1e 100644 --- a/062convert_ingredients_to_text.cc +++ b/062convert_ingredients_to_text.cc @@ -143,6 +143,15 @@ bool is_static_array(const reagent& x) { return !x.type->atom && x.type->left->atom && x.type->left->name == "array"; } +//: Supporting 'append' above requires remembering what name an instruction +//: had before any rewrites or transforms. +:(before "End instruction Fields") +string name_before_rewrite; +:(before "End instruction Clear") +name_before_rewrite.clear(); +:(before "End next_instruction(curr)") +curr->name_before_rewrite = curr->name; + :(scenarios run) :(scenario append_other_types_to_text) def main [ diff --git a/071deep_copy.cc b/071deep_copy.cc index 96f2671c..ffeb00bd 100644 --- a/071deep_copy.cc +++ b/071deep_copy.cc @@ -263,6 +263,8 @@ int deep_copy_address(const reagent& canonized_in, map& addresses_copi if (contains_key(addresses_copied, in_address)) { int out = get(addresses_copied, in_address); trace(9991, "run") << "deep-copy: copy already exists: " << out << end(); + assert(contains_key(Memory, out)); // refcount must already be incremented + ++get(Memory, out); return out; } int out = allocate(payload_size(canonized_in)); @@ -405,9 +407,9 @@ def main [ y:&:foo <- deep-copy x 1:num/raw <- get *y, p:offset y2:&:foo <- get *y, q:offset - stash y [vs] y2 2:bool/raw <- equal y, y2 # is it still a cycle? 3:bool/raw <- equal x, y # is it the same cycle? + # not bothering cleaning up; both cycles leak memory ] +mem: storing 34 in location 1 # deep copy also contains a cycle @@ -415,6 +417,9 @@ def main [ # but it's a completely different (disjoint) cycle +mem: storing 0 in location 3 +//: todo: version of deep_copy_cycles that breaks cycles at end and verifies no memory leaks +//: needs approximate matching over scenario traces + :(scenario deep_copy_skips_channel) # ugly! dummy 'channel' type if we happen to be building without that layer % if (!contains_key(Type_ordinal, "channel")) get_or_insert(Type, put(Type_ordinal, "channel", Next_type_ordinal++)).name = "channel"; diff --git a/counters.mu b/counters.mu index 417f7f79..f0e514d7 100644 --- a/counters.mu +++ b/counters.mu @@ -3,7 +3,7 @@ def new-counter n:num -> default-space:space [ default-space <- new location:type, 30 - load-ingredients + load-ingredients # initialize n ] def increment-counter outer:space/names:new-counter, x:num -> n:num/space:1 [ -- cgit 1.4.1-2-gfad0