1 //: Reclaiming memory when it's no longer used.
  2 //: The top of the address layer has the complete life cycle of memory.
  3 
  4 :(scenario new_reclaim)
  5 def main [
  6   1:address:num <- new number:type
  7   2:num <- copy 1:address:num  # because 1 will get reset during abandon below
  8   1:address:num <- copy 0  # abandon
  9   3:address:num <- new number:type  # must be same size as abandoned memory to reuse
 10   4:num <- copy 3:address:num
 11   5:bool <- equal 2:num, 4:num
 12 ]
 13 # both allocations should have returned the same address
 14 +mem: storing 1 in location 5
 15 
 16 :(before "End Decrement Refcount(old_address, payload_type, payload_size)")
 17 if (old_refcount == 0) {
 18   trace(9999, "mem") << "automatically abandoning " << old_address << end();
 19   abandon(old_address, payload_type, payload_size);
 20 }
 21 
 22 //: When abandoning addresses we'll save them to a 'free list', segregated by size.
 23 
 24 :(before "End routine Fields")
 25 map<int, int> free_list;
 26 
 27 :(code)
 28 void abandon(int address, const type_tree* payload_type, int payload_size) {
 29   trace(9999, "abandon") << "updating refcounts inside " << address << ": " << to_string(payload_type) << end();
 30 //?   Total_free += size;
 31 //?   ++Num_free;
 32 //?   cerr << "abandon: " << size << '\n';
 33   // decrement any contained refcounts
 34   if (is_mu_array(payload_type)) {
 35   ¦ reagent/*local*/ element;
 36   ¦ element.type = copy_array_element(payload_type);
 37   ¦ int array_length = get_or_insert(Memory, address+/*skip refcount*/1);
 38   ¦ assert(element.type->name != "array");
 39   ¦ int element_size = size_of(element);
 40   ¦ for (int i = 0;  i < array_length;  ++i) {
 41   ¦ ¦ element.set_value(address + /*skip refcount and length*/2 + i*element_size);
 42   ¦ ¦ decrement_any_refcounts(element);
 43   ¦ }
 44   }
 45   else if (is_mu_container(payload_type) || is_mu_exclusive_container(payload_type)) {
 46   ¦ reagent tmp;
 47   ¦ tmp.type = new type_tree(*payload_type);
 48   ¦ tmp.set_value(address + /*skip refcount*/1);
 49   ¦ decrement_any_refcounts(tmp);
 50   }
 51   // clear memory
 52   for (int curr = address;  curr < address+payload_size;  ++curr)
 53   ¦ put(Memory, curr, 0);
 54   // append existing free list to address
 55   trace(9999, "abandon") << "saving " << address << " in free-list of size " << payload_size << end();
 56   put(Memory, address, get_or_insert(Current_routine->free_list, payload_size));
 57   put(Current_routine->free_list, payload_size, address);
 58 }
 59 
 60 :(after "Allocate Special-cases")
 61 if (get_or_insert(Current_routine->free_list, size)) {
 62   trace(9999, "abandon") << "picking up space from free-list of size " << size << end();
 63   int result = get_or_insert(Current_routine->free_list, size);
 64   trace(9999, "mem") << "new alloc from free list: " << result << end();
 65   put(Current_routine->free_list, size, get_or_insert(Memory, result));
 66   put(Memory, result, 0);
 67   for (int curr = result;  curr < result+size;  ++curr) {
 68   ¦ if (get_or_insert(Memory, curr) != 0) {
 69   ¦ ¦ raise << maybe(current_recipe_name()) << "memory in free list was not zeroed out: " << curr << '/' << result << "; somebody wrote to us after free!!!\n" << end();
 70   ¦ ¦ break;  // always fatal
 71   ¦ }
 72   }
 73   return result;
 74 }
 75 
 76 :(scenario new_differing_size_no_reclaim)
 77 def main [
 78   1:address:num <- new number:type
 79   2:num <- copy 1:address:num
 80   1:address:num <- copy 0  # abandon
 81   3:address:array:num <- new number:type, 2  # different size
 82   4:num <- copy 3:address:array:num
 83   5:bool <- equal 2:num, 4:num
 84 ]
 85 # no reuse
 86 +mem: storing 0 in location 5
 87 
 88 :(scenario new_reclaim_array)
 89 def main [
 90   1:address:array:num <- new number:type, 2
 91   2:num <- copy 1:address:array:num
 92   1:address:array:num <- copy 0  # abandon
 93   3:address:array:num <- new number:type, 2  # same size
 94   4:num <- copy 3:address:array:num
 95   5:bool <- equal 2:num, 4:num
 96 ]
 97 # both calls to new returned identical addresses
 98 +mem: storing 1 in location 5
 99 
100 :(scenario abandon_on_overwrite)
101 def main [
102   1:address:num <- new number:type
103   # over-writing one allocation with another
104   1:address:num <- new number:type
105   1:address:num <- copy 0
106 ]
107 +run: {1: ("address" "number")} <- new {number: "type"}
108 +mem: incrementing refcount of 1000: 0 -> 1
109 +run: {1: ("address" "number")} <- new {number: "type"}
110 +mem: automatically abandoning 1000
111 
112 :(scenario abandon_after_call)
113 def main [
114   1:address:num <- new number:type
115   # passing in addresses to recipes increments refcount
116   foo 1:address:num
117   1:address:num <- copy 0
118 ]
119 def foo [
120   2:address:num <- next-ingredient
121   # return does NOT yet decrement refcount; memory must be explicitly managed
122   2:address:num <- copy 0
123 ]
124 +run: {1: ("address" "number")} <- new {number: "type"}
125 +mem: incrementing refcount of 1000: 0 -> 1
126 +run: foo {1: ("address" "number")}
127 # leave ambiguous precisely when the next increment happens
128 +mem: incrementing refcount of 1000: 1 -> 2
129 +run: {2: ("address" "number")} <- copy {0: "literal"}
130 +mem: decrementing refcount of 1000: 2 -> 1
131 +run: {1: ("address" "number")} <- copy {0: "literal"}
132 +mem: decrementing refcount of 1000: 1 -> 0
133 +mem: automatically abandoning 1000
134 
135 :(scenario abandon_on_overwrite_array)
136 def main [
137   1:num <- copy 30
138   # allocate an array
139   10:address:array:num <- new number:type, 20
140   11:num <- copy 10:address:array:num  # doesn't increment refcount
141   # allocate another array in its place, implicitly freeing the previous allocation
142   10:address:array:num <- new number:type, 25
143 ]
144 +run: {10: ("address" "array" "number")} <- new {number: "type"}, {25: "literal"}
145 # abandoned array is of old size (20, not 25)
146 +abandon: saving 1000 in free-list of size 22
147 
148 :(scenario refcounts_abandon_address_in_container)
149 # container containing an address
150 container foo [
151   x:address:num
152 ]
153 def main [
154   1:address:num <- new number:type
155   2:address:foo <- new foo:type
156   *2:address:foo <- put *2:address:foo, x:offset, 1:address:num
157   1:address:num <- copy 0
158   2:address:foo <- copy 0
159 ]
160 +run: {1: ("address" "number")} <- new {number: "type"}
161 +mem: incrementing refcount of 1000: 0 -> 1
162 +run: {2: ("address" "foo")} <- new {foo: "type"}
163 +mem: incrementing refcount of 1002: 0 -> 1
164 +run: {2: ("address" "foo"), "lookup": ()} <- put {2: ("address" "foo"), "lookup": ()}, {x: "offset"}, {1: ("address" "number")}
165 +mem: incrementing refcount of 1000: 1 -> 2
166 +run: {1: ("address" "number")} <- copy {0: "literal"}
167 +mem: decrementing refcount of 1000: 2 -> 1
168 +run: {2: ("address" "foo")} <- copy {0: "literal"}
169 # start abandoning container containing address
170 +mem: decrementing refcount of 1002: 1 -> 0
171 # nested abandon
172 +mem: decrementing refcount of 1000: 1 -> 0
173 +abandon: saving 1000 in free-list of size 2
174 # actually abandon the container containing address
175 +abandon: saving 1002 in free-list of size 2
176 
177 # todo: move past dilated reagent
178 :(scenario refcounts_abandon_address_in_array)
179 def main [
180   1:address:num <- new number:type
181   2:address:array:address:num <- new {(address number): type}, 3
182   *2:address:array:address:num <- put-index *2:address:array:address:num, 1, 1:address:num
183   1:address:num <- copy 0
184   2:address:array:address:num <- copy 0
185 ]
186 +run: {1: ("address" "number")} <- new {number: "type"}
187 +mem: incrementing refcount of 1000: 0 -> 1
188 +run: {2: ("address" "array" "address" "number"), "lookup": ()} <- put-index {2: ("address" "array" "address" "number"), "lookup": ()}, {1: "literal"}, {1: ("address" "number")}
189 +mem: incrementing refcount of 1000: 1 -> 2
190 +run: {1: ("address" "number")} <- copy {0: "literal"}
191 +mem: decrementing refcount of 1000: 2 -> 1
192 +run: {2: ("address" "array" "address" "number")} <- copy {0: "literal"}
193 # nested abandon
194 +mem: decrementing refcount of 1000: 1 -> 0
195 +abandon: saving 1000 in free-list of size 2
196 
197 :(scenario refcounts_abandon_address_in_container_in_array)
198 # container containing an address
199 container foo [
200   x:address:num
201 ]
202 def main [
203   1:address:num <- new number:type
204   2:address:array:foo <- new foo:type, 3
205   3:foo <- merge 1:address:num
206   *2:address:array:foo <- put-index *2:address:array:foo, 1, 3:foo
207   1:address:num <- copy 0
208   3:foo <- merge 0
209   2:address:array:foo <- copy 0
210 ]
211 +run: {1: ("address" "number")} <- new {number: "type"}
212 +mem: incrementing refcount of 1000: 0 -> 1
213 +run: {3: "foo"} <- merge {1: ("address" "number")}
214 +mem: incrementing refcount of 1000: 1 -> 2
215 +run: {2: ("address" "array" "foo"), "lookup": ()} <- put-index {2: ("address" "array" "foo"), "lookup": ()}, {1: "literal"}, {3: "foo"}
216 +mem: incrementing refcount of 1000: 2 -> 3
217 +run: {1: ("address" "number")} <- copy {0: "literal"}
218 +mem: decrementing refcount of 1000: 3 -> 2
219 +run: {3: "foo"} <- merge {0: "literal"}
220 +mem: decrementing refcount of 1000: 2 -> 1
221 +run: {2: ("address" "array" "foo")} <- copy {0: "literal"}
222 # nested abandon
223 +mem: decrementing refcount of 1000: 1 -> 0
224 +abandon: saving 1000 in free-list of size 2
225 
226 :(scenario refcounts_abandon_array_within_container)
227 container foo [
228   x:address:array:num
229 ]
230 def main [
231   1:address:array:num <- new number:type, 3
232   2:foo <- merge 1:address:array:num
233   1:address:array:num <- copy 0
234   2:foo <- copy 0
235 ]
236 +run: {1: ("address" "array" "number")} <- new {number: "type"}, {3: "literal"}
237 +mem: incrementing refcount of 1000: 0 -> 1
238 +run: {2: "foo"} <- merge {1: ("address" "array" "number")}
239 +mem: incrementing refcount of 1000: 1 -> 2
240 +run: {1: ("address" "array" "number")} <- copy {0: "literal"}
241 +mem: decrementing refcount of 1000: 2 -> 1
242 +run: {2: "foo"} <- copy {0: "literal"}
243 +mem: decrementing refcount of 1000: 1 -> 0
244 +mem: automatically abandoning 1000
245 # make sure we save it in a free-list of the appropriate size
246 +abandon: saving 1000 in free-list of size 5