Mu - 071deep

From 81a324bec3e992d6a979830c5bcae89ac7cdf40c Mon Sep 17 00:00:00 2001 From: "Kartik K. Agaram" Date: Wed, 13 Sep 2017 21:11:24 -0700 Subject: 3995 --- html/071deep_copy.cc.html | 525 ++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 525 insertions(+) create mode 100644 html/071deep_copy.cc.html (limited to 'html/071deep_copy.cc.html') diff --git a/html/071deep_copy.cc.html b/html/071deep_copy.cc.html new file mode 100644 index 00000000..56fb82fe --- /dev/null +++ b/html/071deep_copy.cc.html @@ -0,0 +1,525 @@ + + + + +Mu - 071deep_copy.cc + + + + + + + + + + +
+  1 // To recursively copy containers and any addresses they contain, use
+  2 // 'deep-copy'.
+  3 //
+  4 // Invariant: After a deep-copy its ingredient and result will point to no
+  5 // common addresses.
+  6 // Implications: Refcounts of all data pointed to by the original ingredient
+  7 // will remain unchanged. Refcounts of all data pointed to by the (newly
+  8 // created) result will be 1, in the absence of cycles.
+  9 //
+ 10 // We do handle cycles in the ingredient, however. All cycles are translated
+ 11 // to new cycles in the product.
+ 12 
+ 13 :(scenario deep_copy_number)
+ 14 def main [
+ 15   local-scope
+ 16   x:num <- copy 34
+ 17   y:num <- deep-copy x
+ 18   10:bool/raw <- equal x, y
+ 19 ]
+ 20 # non-address primitives are identical
+ 21 +mem: storing 1 in location 10
+ 22 
+ 23 :(scenario deep_copy_container_without_address)
+ 24 container foo [
+ 25   x:num
+ 26   y:num
+ 27 ]
+ 28 def main [
+ 29   local-scope
+ 30   a:foo <- merge 34, 35
+ 31   b:foo <- deep-copy a
+ 32   10:bool/raw <- equal a, b
+ 33 ]
+ 34 # containers are identical as long as they don't contain addresses
+ 35 +mem: storing 1 in location 10
+ 36 
+ 37 :(scenario deep_copy_address)
+ 38 % Memory_allocated_until = 200;
+ 39 def main [
+ 40   # avoid all memory allocations except the implicit ones inside deep-copy, so
+ 41   # that the result is deterministic
+ 42   1:&:num <- copy 100/unsafe  # pretend allocation
+ 43   *1:&:num <- copy 34
+ 44   2:&:num <- deep-copy 1:&:num
+ 45   10:bool <- equal 1:&:num, 2:&:num
+ 46   11:bool <- equal *1:&:num, *2:&:num
+ 47   2:&:num <- copy 0
+ 48 ]
+ 49 # the result of deep-copy is a new address
+ 50 +mem: storing 0 in location 10
+ 51 # however, the contents are identical
+ 52 +mem: storing 1 in location 11
+ 53 # the result of deep-copy gets a refcount of 1
+ 54 # (its address 202 = 200 base + 2 for temporary space inside deep-copy)
+ 55 +run: {2: ("address" "number")} <- copy {0: "literal"}
+ 56 +mem: decrementing refcount of 202: 1 -> 0
+ 57 +abandon: saving 202 in free-list of size 2
+ 58 
+ 59 :(scenario deep_copy_address_to_container)
+ 60 % Memory_allocated_until = 200;
+ 61 def main [
+ 62   # avoid all memory allocations except the implicit ones inside deep-copy, so
+ 63   # that the result is deterministic
+ 64   1:&:point <- copy 100/unsafe  # pretend allocation
+ 65   *1:&:point <- merge 34, 35
+ 66   2:&:point <- deep-copy 1:&:point
+ 67   10:bool <- equal 1:&:point, 2:&:point
+ 68   11:bool <- equal *1:&:point, *2:&:point
+ 69 ]
+ 70 # the result of deep-copy is a new address
+ 71 +mem: storing 0 in location 10
+ 72 # however, the contents are identical
+ 73 +mem: storing 1 in location 11
+ 74 
+ 75 :(scenario deep_copy_address_to_address)
+ 76 % Memory_allocated_until = 200;
+ 77 def main [
+ 78   # avoid all memory allocations except the implicit ones inside deep-copy, so
+ 79   # that the result is deterministic
+ 80   1:&:&:num <- copy 100/unsafe  # pretend allocation
+ 81   *1:&:&:num <- copy 150/unsafe
+ 82   **1:&:&:num <- copy 34
+ 83   2:&:&:num <- deep-copy 1:&:&:num
+ 84   10:bool <- equal 1:&:&:num, 2:&:&:num
+ 85   11:bool <- equal *1:&:&:num, *2:&:&:num
+ 86   12:bool <- equal **1:&:&:num, **2:&:&:num
+ 87 ]
+ 88 # the result of deep-copy is a new address
+ 89 +mem: storing 0 in location 10
+ 90 # any addresses in it or pointed to it are also new
+ 91 +mem: storing 0 in location 11
+ 92 # however, the non-address contents are identical
+ 93 +mem: storing 1 in location 12
+ 94 
+ 95 :(scenario deep_copy_array)
+ 96 % Memory_allocated_until = 200;
+ 97 def main [
+ 98   # avoid all memory allocations except the implicit ones inside deep-copy, so
+ 99   # that the result is deterministic
+100   100:num <- copy 1  # pretend refcount
+101   101:num <- copy 3  # pretend array length
+102   1:&:@:num <- copy 100/unsafe  # pretend allocation
+103   put-index *1:&:@:num, 0, 34
+104   put-index *1:&:@:num, 1, 35
+105   put-index *1:&:@:num, 2, 36
+106   stash [old:], *1:&:@:num
+107   2:&:@:num <- deep-copy 1:&:@:num
+108   stash 2:&:@:num
+109   stash [new:], *2:&:@:num
+110   10:bool <- equal 1:&:@:num, 2:&:@:num
+111   11:bool <- equal *1:&:@:num, *2:&:@:num
+112 ]
+113 +app: old: 3 34 35 36
+114 +app: new: 3 34 35 36
+115 # the result of deep-copy is a new address
+116 +mem: storing 0 in location 10
+117 # however, the contents are identical
+118 +mem: storing 1 in location 11
+119 
+120 :(scenario deep_copy_container_with_address)
+121 container foo [
+122   x:num
+123   y:&:num
+124 ]
+125 def main [
+126   local-scope
+127   y0:&:num <- new number:type
+128   *y0 <- copy 35
+129   a:foo <- merge 34, y0
+130   b:foo <- deep-copy a
+131   10:bool/raw <- equal a, b
+132   y1:&:num <- get b, y:offset
+133   11:bool/raw <- equal y0, y1
+134   12:num/raw <- copy *y1
+135 ]
+136 # containers containing addresses are not identical to their deep copies
+137 +mem: storing 0 in location 10
+138 # the addresses they contain are not identical either
+139 +mem: storing 0 in location 11
+140 +mem: storing 35 in location 12
+141 
+142 :(scenario deep_copy_exclusive_container_with_address)
+143 exclusive-container foo [
+144   x:num
+145   y:&:num
+146 ]
+147 def main [
+148   local-scope
+149   y0:&:num <- new number:type
+150   *y0 <- copy 34
+151   a:foo <- merge 1/y, y0
+152   b:foo <- deep-copy a
+153   10:bool/raw <- equal a, b
+154   y1:&:num, z:bool <- maybe-convert b, y:variant
+155   11:bool/raw <- equal y0, y1
+156   12:num/raw <- copy *y1
+157 ]
+158 # exclusive containers containing addresses are not identical to their deep copies
+159 +mem: storing 0 in location 10
+160 # the addresses they contain are not identical either
+161 +mem: storing 0 in location 11
+162 +mem: storing 34 in location 12
+163 
+164 :(scenario deep_copy_exclusive_container_with_container_with_address)
+165 exclusive-container foo [
+166   x:num
+167   y:bar  # inline
+168 ]
+169 container bar [
+170   x:&:num
+171 ]
+172 def main [
+173   local-scope
+174   y0:&:num <- new number:type
+175   *y0 <- copy 34
+176   a:bar <- merge y0
+177   b:foo <- merge 1/y, a
+178   c:foo <- deep-copy b
+179   10:bool/raw <- equal b, c
+180   d:bar, z:bool <- maybe-convert c, y:variant
+181   y1:&:num <- get d, x:offset
+182   11:bool/raw <- equal y0, y1
+183   12:num/raw <- copy *y1
+184 ]
+185 # exclusive containers containing addresses are not identical to their deep copies
+186 +mem: storing 0 in location 10
+187 # sub-containers containing addresses are not identical either
+188 +mem: storing 0 in location 11
+189 +mem: storing 34 in location 12
+190 
+191 :(before "End Primitive Recipe Declarations")
+192 DEEP_COPY,
+193 :(before "End Primitive Recipe Numbers")
+194 put(Recipe_ordinal, "deep-copy", DEEP_COPY);
+195 :(before "End Primitive Recipe Checks")
+196 case DEEP_COPY: {
+197   if (SIZE(inst.ingredients) != 1) {
+198   ¦ raise << maybe(get(Recipe, r).name) << "'deep-copy' takes exactly one ingredient rather than '" << to_original_string(inst) << "'\n" << end();
+199   ¦ break;
+200   }
+201   if (SIZE(inst.products) != 1) {
+202   ¦ raise << maybe(get(Recipe, r).name) << "'deep-copy' takes exactly one ingredient rather than '" << to_original_string(inst) << "'\n" << end();
+203   ¦ break;
+204   }
+205   if (!types_strictly_match(inst.ingredients.at(0), inst.products.at(0))) {
+206   ¦ raise << maybe(get(Recipe, r).name) << "'deep-copy' requires its ingredient and product to be the same type, but got '" << to_original_string(inst) << "'\n" << end();
+207   ¦ break;
+208   }
+209   break;
+210 }
+211 :(before "End Primitive Recipe Implementations")
+212 case DEEP_COPY: {
+213   products.push_back(deep_copy(current_instruction().ingredients.at(0)));
+214   break;
+215 }
+216 
+217 :(code)
+218 vector<double> deep_copy(const reagent& in) {
+219   // allocate a tiny bit of temporary space for deep_copy()
+220   trace(9991, "run") << "deep-copy: allocating space for temporary" << end();
+221   reagent tmp("tmp:address:number");
+222   tmp.set_value(allocate(1));
+223   map<int, int> addresses_copied;
+224   vector<double> result = deep_copy(in, addresses_copied, tmp);
+225   // reclaim Mu memory allocated for tmp
+226   trace(9991, "run") << "deep-copy: reclaiming temporary" << end();
+227   abandon(tmp.value, payload_type(tmp.type), payload_size(tmp));
+228   // reclaim host memory allocated for tmp.type when tmp goes out of scope
+229   return result;
+230 }
+231 
+232 vector<double> deep_copy(reagent/*copy*/ in, map<int, int>& addresses_copied, const reagent& tmp) {
+233   canonize(in);
+234   if (is_mu_address(in)) {
+235   ¦ // hack: skip primitive containers that do their own locking; they're designed to be shared between routines
+236   ¦ type_tree* payload = in.type->right;
+237   ¦ if (payload->left->name == "channel" || payload->left->name == "resources")
+238   ¦ ¦ return read_memory(in);
+239   }
+240   vector<double> result;
+241   if (is_mu_address(in))
+242   ¦ result.push_back(deep_copy_address(in, addresses_copied, tmp));
+243   else
+244   ¦ deep_copy(in, addresses_copied, tmp, result);
+245   return result;
+246 }
+247 
+248 // deep-copy an address and return a new address
+249 int deep_copy_address(const reagent& canonized_in, map<int, int>& addresses_copied, const reagent& tmp) {
+250   if (canonized_in.value == 0) return 0;
+251   int in_address = payload_address(canonized_in);
+252   trace(9991, "run") << "deep-copy: copying address " << in_address << end();
+253   if (contains_key(addresses_copied, in_address)) {
+254   ¦ int out = get(addresses_copied, in_address);
+255   ¦ trace(9991, "run") << "deep-copy: copy already exists: " << out << end();
+256   ¦ return out;
+257   }
+258   int out = allocate(payload_size(canonized_in));
+259   trace(9991, "run") << "deep-copy: new address is " << out << end();
+260   put(addresses_copied, in_address, out);
+261   reagent/*copy*/ payload = canonized_in;
+262   payload.properties.push_back(pair<string, string_tree*>("lookup", NULL));
+263   trace(9991, "run") << "recursing on payload " << payload.value << ' ' << to_string(payload) << end();
+264   vector<double> data = deep_copy(payload, addresses_copied, tmp);
+265   trace(9991, "run") << "deep-copy: writing result " << out << ": " << to_string(data) << end();
+266   // HACK: write_memory interface isn't ideal for this situation; we need
+267   // a temporary location to help copy the payload.
+268   trace(9991, "run") << "deep-copy: writing temporary " << tmp.value << ": " << out << end();
+269   put(Memory, tmp.value, out);
+270   payload.set_value(tmp.value);  // now modified for output
+271   vector<double> old_data = read_memory(payload);
+272   trace(9991, "run") << "deep-copy: really writing to " << payload.value << ' ' << to_string(payload) << " (old value " << to_string(old_data) << " new value " << to_string(data) << ")" << end();
+273   write_memory(payload, data);
+274   trace(9991, "run") << "deep-copy: output is " << to_string(data) << end();
+275   return out;
+276 }
+277 
+278 // deep-copy a non-address and return a vector of locations
+279 void deep_copy(const reagent& canonized_in, map<int, int>& addresses_copied, const reagent& tmp, vector<double>& out) {
+280   assert(!is_mu_address(canonized_in));
+281   vector<double> data = read_memory(canonized_in);
+282   out.insert(out.end(), data.begin(), data.end());
+283   if (!contains_key(Container_metadata, canonized_in.type)) return;
+284   trace(9991, "run") << "deep-copy: scanning for addresses in " << to_string(data) << end();
+285   const container_metadata& metadata = get(Container_metadata, canonized_in.type);
+286   for (map<set<tag_condition_info>, set<address_element_info> >::const_iterator p = metadata.address.begin();  p != metadata.address.end();  ++p) {
+287   ¦ if (!all_match(data, p->first)) continue;
+288   ¦ for (set<address_element_info>::const_iterator info = p->second.begin();  info != p->second.end();  ++info) {
+289   ¦ ¦ // hack: skip primitive containers that do their own locking; they're designed to be shared between routines
+290   ¦ ¦ if (!info->payload_type->atom && info->payload_type->left->name == "channel")
+291   ¦ ¦ ¦ continue;
+292   ¦ ¦ if (info->payload_type->atom && info->payload_type->name == "resources")
+293   ¦ ¦ ¦ continue;
+294   ¦ ¦ // construct a fake reagent that reads directly from the appropriate
+295   ¦ ¦ // field of the container
+296   ¦ ¦ reagent curr;
+297   ¦ ¦ if (info->payload_type->atom)
+298   ¦ ¦ ¦ curr.type = new type_tree(new type_tree("address"), new type_tree(new type_tree(info->payload_type->name), NULL));
+299   ¦ ¦ else
+300   ¦ ¦ ¦ curr.type = new type_tree(new type_tree("address"), new type_tree(*info->payload_type));
+301   ¦ ¦ curr.set_value(canonized_in.value + info->offset);
+302   ¦ ¦ curr.properties.push_back(pair<string, string_tree*>("raw", NULL));
+303   ¦ ¦ trace(9991, "run") << "deep-copy: copying address " << curr.value << end();
+304   ¦ ¦ out.at(info->offset) = deep_copy_address(curr, addresses_copied, tmp);
+305   ¦ }
+306   }
+307 }
+308 
+309 int payload_address(reagent/*copy*/ x) {
+310   x.properties.push_back(pair<string, string_tree*>("lookup", NULL));
+311   canonize(x);
+312   return x.value;
+313 }
+314 
+315 :(scenario deep_copy_stress_test_1)
+316 container foo1 [
+317   p:&:num
+318 ]
+319 container foo2 [
+320   p:&:foo1
+321 ]
+322 exclusive-container foo3 [
+323   p:&:foo1
+324   q:&:foo2
+325 ]
+326 def main [
+327   local-scope
+328   x:&:num <- new number:type
+329   *x <- copy 34
+330   a:&:foo1 <- new foo1:type
+331   *a <- merge x
+332   b:&:foo2 <- new foo2:type
+333   *b <- merge a
+334   c:foo3 <- merge 1/q, b
+335   d:foo3 <- deep-copy c
+336   e:&:foo2, z:bool <- maybe-convert d, q:variant
+337   f:&:foo1 <- get *e, p:offset
+338   g:&:num <- get *f, p:offset
+339   1:num/raw <- copy *g
+340 ]
+341 +mem: storing 34 in location 1
+342 
+343 :(scenario deep_copy_stress_test_2)
+344 container foo1 [
+345   p:&:num
+346 ]
+347 container foo2 [
+348   p:&:foo1
+349 ]
+350 exclusive-container foo3 [
+351   p:&:foo1
+352   q:&:foo2
+353 ]
+354 container foo4 [
+355   p:num
+356   q:&:foo3
+357 ]
+358 def main [
+359   local-scope
+360   x:&:num <- new number:type
+361   *x <- copy 34
+362   a:&:foo1 <- new foo1:type
+363   *a <- merge x
+364   b:&:foo2 <- new foo2:type
+365   *b <- merge a
+366   c:&:foo3 <- new foo3:type
+367   *c <- merge 1/q, b
+368   d:foo4 <- merge 35, c
+369   e:foo4 <- deep-copy d
+370   f:&:foo3 <- get e, q:offset
+371   g:&:foo2, z:bool <- maybe-convert *f, q:variant
+372   h:&:foo1 <- get *g, p:offset
+373   y:&:num <- get *h, p:offset
+374   1:num/raw <- copy *y
+375 ]
+376 +mem: storing 34 in location 1
+377 
+378 :(scenario deep_copy_cycles)
+379 container foo [
+380   p:num
+381   q:&:foo
+382 ]
+383 def main [
+384   local-scope
+385   x:&:foo <- new foo:type
+386   *x <- put *x, p:offset, 34
+387   *x <- put *x, q:offset, x  # create a cycle
+388   y:&:foo <- deep-copy x
+389   1:num/raw <- get *y, p:offset
+390   y2:&:foo <- get *y, q:offset
+391   stash y [vs] y2
+392   2:bool/raw <- equal y, y2  # is it still a cycle?
+393   3:bool/raw <- equal x, y  # is it the same cycle?
+394 ]
+395 +mem: storing 34 in location 1
+396 # deep copy also contains a cycle
+397 +mem: storing 1 in location 2
+398 # but it's a completely different (disjoint) cycle
+399 +mem: storing 0 in location 3
+400 
+401 :(scenario deep_copy_skips_channel)
+402 # ugly! dummy 'channel' type if we happen to be building without that layer
+403 % if (!contains_key(Type_ordinal, "channel")) get_or_insert(Type, put(Type_ordinal, "channel", Next_type_ordinal++)).name = "channel";
+404 def main [
+405   local-scope
+406   x:&:channel:num <- new {(channel num): type}
+407   y:&:channel:num <- deep-copy x
+408   10:bool/raw <- equal x, y
+409 ]
+410 # channels are never deep-copied
+411 +mem: storing 1 in location 10
+412 
+413 :(scenario deep_copy_skips_nested_channel)
+414 # ugly! dummy 'channel' type if we happen to be building without that layer
+415 % if (!contains_key(Type_ordinal, "channel")) get_or_insert(Type, put(Type_ordinal, "channel", Next_type_ordinal++)).name = "channel";
+416 container foo [
+417   c:&:channel:num
+418 ]
+419 def main [
+420   local-scope
+421   x:&:foo <- new foo:type
+422   y:&:foo <- deep-copy x
+423   xc:&:channel:num <- get *x, c:offset
+424   yc:&:channel:num <- get *y, c:offset
+425   10:bool/raw <- equal xc, yc
+426 ]
+427 # channels are never deep-copied
+428 +mem: storing 1 in location 10
+429 
+430 :(scenario deep_copy_skips_resources)
+431 # ugly! dummy 'resources' type if we happen to be building without that layer
+432 % if (!contains_key(Type_ordinal, "resources")) get_or_insert(Type, put(Type_ordinal, "resources", Next_type_ordinal++)).name = "resources";
+433 def main [
+434   local-scope
+435   x:&:resources <- new resources:type
+436   y:&:resources <- deep-copy x
+437   10:bool/raw <- equal x, y
+438 ]
+439 # resources are never deep-copied
+440 +mem: storing 1 in location 10
+441 
+442 :(scenario deep_copy_skips_nested_resources)
+443 # ugly! dummy 'resources' type if we happen to be building without that layer
+444 % if (!contains_key(Type_ordinal, "resources")) get_or_insert(Type, put(Type_ordinal, "resources", Next_type_ordinal++)).name = "resources";
+445 container foo [
+446   c:&:resources
+447 ]
+448 def main [
+449   local-scope
+450   x:&:foo <- new foo:type
+451   y:&:foo <- deep-copy x
+452   xc:&:resources <- get *x, c:offset
+453   yc:&:resources <- get *y, c:offset
+454   10:bool/raw <- equal xc, yc
+455 ]
+456 # resources are never deep-copied
+457 +mem: storing 1 in location 10
+
+ + + -- cgit 1.4.1-2-gfad0