1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
|
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
<html>
<head>
<meta http-equiv="content-type" content="text/html; charset=UTF-8">
<title>Mu - 042new.cc</title>
<meta name="Generator" content="Vim/7.4">
<meta name="plugin-version" content="vim7.4_v1">
<meta name="syntax" content="cpp">
<meta name="settings" content="use_css,pre_wrap,no_foldcolumn,expand_tabs,prevent_copy=">
<meta name="colorscheme" content="minimal">
<style type="text/css">
<!--
pre { white-space: pre-wrap; font-family: monospace; color: #d0d0d0; background-color: #000000; }
body { font-family: monospace; color: #d0d0d0; background-color: #000000; }
* { font-size: 1em; }
.cSpecial { color: #008000; }
.Identifier { color: #008080; }
.Constant { color: #008080; }
.Comment { color: #8080ff; }
.Delimiter { color: #c000c0; }
.Special { color: #ff6060; }
.CommentedCode { color: #6c6c6c; }
.SalientComment { color: #00ffff; }
.traceContains { color: #008000; }
-->
</style>
<script type='text/javascript'>
<!--
-->
</script>
</head>
<body>
<pre id='vimCodeElement'>
<span class="Comment">//: A simple memory allocator to create space for new variables at runtime.</span>
<span class="Delimiter">:(scenarios run)</span>
<span class="Delimiter">:(scenario new)</span>
<span class="Comment"># call new two times with identical arguments; you should get back different results</span>
recipe main [
<span class="Constant">1</span>:address:number/<span class="Special">raw <- </span>new number:type
<span class="Constant">2</span>:address:number/<span class="Special">raw <- </span>new number:type
<span class="Constant">3</span>:boolean/<span class="Special">raw <- </span>equal <span class="Constant">1</span>:address:number/<span class="Special">raw</span><span class="Delimiter">,</span> <span class="Constant">2</span>:address:number/<span class="Special">raw</span>
]
<span class="traceContains">+mem: storing 0 in location 3</span>
<span class="Delimiter">:(before "End Globals")</span>
long long int Reserved_for_tests = <span class="Constant">1000</span><span class="Delimiter">;</span>
long long int Memory_allocated_until = Reserved_for_tests<span class="Delimiter">;</span>
long long int Initial_memory_per_routine = <span class="Constant">100000</span><span class="Delimiter">;</span>
<span class="Delimiter">:(before "End Setup")</span>
Memory_allocated_until = Reserved_for_tests<span class="Delimiter">;</span>
Initial_memory_per_routine = <span class="Constant">100000</span><span class="Delimiter">;</span>
<span class="Delimiter">:(before "End routine Fields")</span>
long long int alloc<span class="Delimiter">,</span> alloc_max<span class="Delimiter">;</span>
<span class="Delimiter">:(before "End routine Constructor")</span>
alloc = Memory_allocated_until<span class="Delimiter">;</span>
Memory_allocated_until += Initial_memory_per_routine<span class="Delimiter">;</span>
alloc_max = Memory_allocated_until<span class="Delimiter">;</span>
trace<span class="Delimiter">(</span>Primitive_recipe_depth<span class="Delimiter">,</span> <span class="Constant">"new"</span><span class="Delimiter">)</span> << <span class="Constant">"routine allocated memory from "</span> << alloc << <span class="Constant">" to "</span> << alloc_max<span class="Delimiter">;</span>
<span class="SalientComment">//:: First handle 'type' operands.</span>
<span class="Delimiter">:(before "End Mu Types Initialization")</span>
Type_number[<span class="Constant">"type"</span>] = <span class="Constant">0</span><span class="Delimiter">;</span>
<span class="Delimiter">:(after "Per-recipe Transforms")</span>
<span class="Comment">// replace type names with type_numbers</span>
if <span class="Delimiter">(</span>inst<span class="Delimiter">.</span>operation == Recipe_number[<span class="Constant">"new"</span>]<span class="Delimiter">)</span> <span class="Delimiter">{</span>
<span class="Comment">// End NEW Transform Special-cases</span>
<span class="Comment">// first arg must be of type 'type'</span>
assert<span class="Delimiter">(</span>SIZE<span class="Delimiter">(</span>inst<span class="Delimiter">.</span>ingredients<span class="Delimiter">)</span> >= <span class="Constant">1</span><span class="Delimiter">);</span>
assert<span class="Delimiter">(</span>isa_literal<span class="Delimiter">(</span>inst<span class="Delimiter">.</span>ingredients<span class="Delimiter">.</span>at<span class="Delimiter">(</span><span class="Constant">0</span><span class="Delimiter">)));</span>
if <span class="Delimiter">(</span>inst<span class="Delimiter">.</span>ingredients<span class="Delimiter">.</span>at<span class="Delimiter">(</span><span class="Constant">0</span><span class="Delimiter">).</span>properties<span class="Delimiter">.</span>at<span class="Delimiter">(</span><span class="Constant">0</span><span class="Delimiter">).</span>second<span class="Delimiter">.</span>at<span class="Delimiter">(</span><span class="Constant">0</span><span class="Delimiter">)</span> != <span class="Constant">"type"</span><span class="Delimiter">)</span>
raise << <span class="Constant">"tried to allocate non-type "</span> << inst<span class="Delimiter">.</span>ingredients<span class="Delimiter">.</span>at<span class="Delimiter">(</span><span class="Constant">0</span><span class="Delimiter">).</span>to_string<span class="Delimiter">()</span> << <span class="Constant">" in recipe "</span> << Recipe[r]<span class="Delimiter">.</span>name << <span class="cSpecial">'\n'</span> << die<span class="Delimiter">();</span>
if <span class="Delimiter">(</span>Type_number<span class="Delimiter">.</span>find<span class="Delimiter">(</span>inst<span class="Delimiter">.</span>ingredients<span class="Delimiter">.</span>at<span class="Delimiter">(</span><span class="Constant">0</span><span class="Delimiter">).</span>name<span class="Delimiter">)</span> == Type_number<span class="Delimiter">.</span>end<span class="Delimiter">())</span>
raise << <span class="Constant">"unknown type "</span> << inst<span class="Delimiter">.</span>ingredients<span class="Delimiter">.</span>at<span class="Delimiter">(</span><span class="Constant">0</span><span class="Delimiter">).</span>name << <span class="Constant">" in recipe "</span> << Recipe[r]<span class="Delimiter">.</span>name << <span class="cSpecial">'\n'</span> << die<span class="Delimiter">();</span>
<span class="CommentedCode">//? cerr << "type " << inst.ingredients.at(0).name << " => " << Type_number[inst.ingredients.at(0).name] << '\n'; //? 1</span>
inst<span class="Delimiter">.</span>ingredients<span class="Delimiter">.</span>at<span class="Delimiter">(</span><span class="Constant">0</span><span class="Delimiter">).</span>set_value<span class="Delimiter">(</span>Type_number[inst<span class="Delimiter">.</span>ingredients<span class="Delimiter">.</span>at<span class="Delimiter">(</span><span class="Constant">0</span><span class="Delimiter">).</span>name]<span class="Delimiter">);</span>
trace<span class="Delimiter">(</span>Primitive_recipe_depth<span class="Delimiter">,</span> <span class="Constant">"new"</span><span class="Delimiter">)</span> << inst<span class="Delimiter">.</span>ingredients<span class="Delimiter">.</span>at<span class="Delimiter">(</span><span class="Constant">0</span><span class="Delimiter">).</span>name << <span class="Constant">" -> "</span> << inst<span class="Delimiter">.</span>ingredients<span class="Delimiter">.</span>at<span class="Delimiter">(</span><span class="Constant">0</span><span class="Delimiter">).</span>value<span class="Delimiter">;</span>
end_new_transform:<span class="Delimiter">;</span>
<span class="Delimiter">}</span>
<span class="SalientComment">//:: Now implement the primitive recipe.</span>
<span class="Comment">//: todo: build 'new' in mu itself</span>
<span class="Delimiter">:(before "End Primitive Recipe Declarations")</span>
NEW<span class="Delimiter">,</span>
<span class="Delimiter">:(before "End Primitive Recipe Numbers")</span>
Recipe_number[<span class="Constant">"new"</span>] = NEW<span class="Delimiter">;</span>
<span class="Delimiter">:(before "End Primitive Recipe Implementations")</span>
case NEW: <span class="Delimiter">{</span>
<span class="Comment">// compute the space we need</span>
long long int size = <span class="Constant">0</span><span class="Delimiter">;</span>
long long int array_length = <span class="Constant">0</span><span class="Delimiter">;</span>
<span class="Delimiter">{</span>
vector<type_number> type<span class="Delimiter">;</span>
assert<span class="Delimiter">(</span>isa_literal<span class="Delimiter">(</span>current_instruction<span class="Delimiter">().</span>ingredients<span class="Delimiter">.</span>at<span class="Delimiter">(</span><span class="Constant">0</span><span class="Delimiter">)));</span>
type<span class="Delimiter">.</span>push_back<span class="Delimiter">(</span>current_instruction<span class="Delimiter">().</span>ingredients<span class="Delimiter">.</span>at<span class="Delimiter">(</span><span class="Constant">0</span><span class="Delimiter">).</span>value<span class="Delimiter">);</span>
<span class="CommentedCode">//? trace(Primitive_recipe_depth, "mem") << "type " << current_instruction().ingredients.at(0).to_string() << ' ' << type.size() << ' ' << type.back() << " has size " << size_of(type); //? 1</span>
if <span class="Delimiter">(</span>SIZE<span class="Delimiter">(</span>current_instruction<span class="Delimiter">().</span>ingredients<span class="Delimiter">)</span> > <span class="Constant">1</span><span class="Delimiter">)</span> <span class="Delimiter">{</span>
<span class="Comment">// array</span>
array_length = ingredients<span class="Delimiter">.</span>at<span class="Delimiter">(</span><span class="Constant">1</span><span class="Delimiter">).</span>at<span class="Delimiter">(</span><span class="Constant">0</span><span class="Delimiter">);</span>
trace<span class="Delimiter">(</span>Primitive_recipe_depth<span class="Delimiter">,</span> <span class="Constant">"mem"</span><span class="Delimiter">)</span> << <span class="Constant">"array size is "</span> << array_length<span class="Delimiter">;</span>
size = array_length*size_of<span class="Delimiter">(</span>type<span class="Delimiter">)</span> + <span class="Comment">/*</span><span class="Comment">space for length</span><span class="Comment">*/</span><span class="Constant">1</span><span class="Delimiter">;</span>
<span class="Delimiter">}</span>
else <span class="Delimiter">{</span>
<span class="Comment">// scalar</span>
size = size_of<span class="Delimiter">(</span>type<span class="Delimiter">);</span>
<span class="Delimiter">}</span>
<span class="Delimiter">}</span>
<span class="Comment">// compute the region of memory to return</span>
<span class="Comment">// really crappy at the moment</span>
ensure_space<span class="Delimiter">(</span>size<span class="Delimiter">);</span>
const long long int result = Current_routine<span class="Delimiter">-></span>alloc<span class="Delimiter">;</span>
trace<span class="Delimiter">(</span>Primitive_recipe_depth<span class="Delimiter">,</span> <span class="Constant">"mem"</span><span class="Delimiter">)</span> << <span class="Constant">"new alloc: "</span> << result<span class="Delimiter">;</span>
<span class="CommentedCode">//? trace(Primitive_recipe_depth, "mem") << "size: " << size << " locations"; //? 1</span>
<span class="Comment">// save result</span>
products<span class="Delimiter">.</span>resize<span class="Delimiter">(</span><span class="Constant">1</span><span class="Delimiter">);</span>
products<span class="Delimiter">.</span>at<span class="Delimiter">(</span><span class="Constant">0</span><span class="Delimiter">).</span>push_back<span class="Delimiter">(</span>result<span class="Delimiter">);</span>
<span class="Comment">// initialize allocated space</span>
for <span class="Delimiter">(</span>long long int address = result<span class="Delimiter">;</span> address < result+size<span class="Delimiter">;</span> ++address<span class="Delimiter">)</span> <span class="Delimiter">{</span>
Memory[address] = <span class="Constant">0</span><span class="Delimiter">;</span>
<span class="Delimiter">}</span>
if <span class="Delimiter">(</span>SIZE<span class="Delimiter">(</span>current_instruction<span class="Delimiter">().</span>ingredients<span class="Delimiter">)</span> > <span class="Constant">1</span><span class="Delimiter">)</span> <span class="Delimiter">{</span>
Memory[result] = array_length<span class="Delimiter">;</span>
<span class="Delimiter">}</span>
<span class="Comment">// bump</span>
Current_routine<span class="Delimiter">-></span>alloc += size<span class="Delimiter">;</span>
<span class="Comment">// no support for reclaiming memory</span>
assert<span class="Delimiter">(</span>Current_routine<span class="Delimiter">-></span>alloc <= Current_routine<span class="Delimiter">-></span>alloc_max<span class="Delimiter">);</span>
<span class="Identifier">break</span><span class="Delimiter">;</span>
<span class="Delimiter">}</span>
<span class="Delimiter">:(code)</span>
void ensure_space<span class="Delimiter">(</span>long long int size<span class="Delimiter">)</span> <span class="Delimiter">{</span>
assert<span class="Delimiter">(</span>size <= Initial_memory_per_routine<span class="Delimiter">);</span>
<span class="CommentedCode">//? cout << Current_routine->alloc << " " << Current_routine->alloc_max << " " << size << '\n'; //? 1</span>
if <span class="Delimiter">(</span>Current_routine<span class="Delimiter">-></span>alloc + size > Current_routine<span class="Delimiter">-></span>alloc_max<span class="Delimiter">)</span> <span class="Delimiter">{</span>
<span class="Comment">// waste the remaining space and create a new chunk</span>
Current_routine<span class="Delimiter">-></span>alloc = Memory_allocated_until<span class="Delimiter">;</span>
Memory_allocated_until += Initial_memory_per_routine<span class="Delimiter">;</span>
Current_routine<span class="Delimiter">-></span>alloc_max = Memory_allocated_until<span class="Delimiter">;</span>
trace<span class="Delimiter">(</span>Primitive_recipe_depth<span class="Delimiter">,</span> <span class="Constant">"new"</span><span class="Delimiter">)</span> << <span class="Constant">"routine allocated memory from "</span> << Current_routine<span class="Delimiter">-></span>alloc << <span class="Constant">" to "</span> << Current_routine<span class="Delimiter">-></span>alloc_max<span class="Delimiter">;</span>
<span class="Delimiter">}</span>
<span class="Delimiter">}</span>
<span class="Delimiter">:(scenario new_initializes)</span>
<span class="Special">% Memory_allocated_until = 10;</span>
<span class="Special">% Memory[Memory_allocated_until] = 1;</span>
recipe main [
<span class="Constant">1</span>:address:number<span class="Special"> <- </span>new number:type
<span class="Constant">2</span>:number<span class="Special"> <- </span>copy <span class="Constant">1</span>:address:number/deref
]
<span class="traceContains">+mem: storing 0 in location 2</span>
<span class="Delimiter">:(scenario new_array)</span>
recipe main [
<span class="Constant">1</span>:address:array:number/<span class="Special">raw <- </span>new number:type<span class="Delimiter">,</span> <span class="Constant">5</span>:literal
<span class="Constant">2</span>:address:number/<span class="Special">raw <- </span>new number:type
<span class="Constant">3</span>:number/<span class="Special">raw <- </span>subtract <span class="Constant">2</span>:address:number/<span class="Special">raw</span><span class="Delimiter">,</span> <span class="Constant">1</span>:address:array:number/<span class="Special">raw</span>
]
<span class="traceContains">+run: 1:address:array:number/raw <- new number:type, 5:literal</span>
<span class="traceContains">+mem: array size is 5</span>
<span class="Comment"># don't forget the extra location for array size</span>
<span class="traceContains">+mem: storing 6 in location 3</span>
<span class="Comment">//: Make sure that each routine gets a different alloc to start.</span>
<span class="Delimiter">:(scenario new_concurrent)</span>
recipe f1 [
start-running f2:recipe
<span class="Constant">1</span>:address:number/<span class="Special">raw <- </span>new number:type
<span class="Comment"># wait for f2 to complete</span>
<span class="Delimiter">{</span>
loop-unless <span class="Constant">4</span>:number/<span class="Special">raw</span>
<span class="Delimiter">}</span>
]
recipe f2 [
<span class="Constant">2</span>:address:number/<span class="Special">raw <- </span>new number:type
<span class="Comment"># hack: assumes scheduler implementation</span>
<span class="Constant">3</span>:boolean/<span class="Special">raw <- </span>equal <span class="Constant">1</span>:address:number/<span class="Special">raw</span><span class="Delimiter">,</span> <span class="Constant">2</span>:address:number/<span class="Special">raw</span>
<span class="Comment"># signal f2 complete</span>
<span class="Constant">4</span>:number/<span class="Special">raw <- </span>copy <span class="Constant">1</span>:literal
]
<span class="traceContains">+mem: storing 0 in location 3</span>
<span class="Comment">//: If a routine runs out of its initial allocation, it should allocate more.</span>
<span class="Delimiter">:(scenario new_overflow)</span>
<span class="Special">% Initial_memory_per_routine = 2;</span>
recipe main [
<span class="Constant">1</span>:address:number/<span class="Special">raw <- </span>new number:type
<span class="Constant">2</span>:address:point/<span class="Special">raw <- </span>new point:type <span class="Comment"># not enough room in initial page</span>
]
<span class="traceContains">+new: routine allocated memory from 1000 to 1002</span>
<span class="traceContains">+new: routine allocated memory from 1002 to 1004</span>
<span class="SalientComment">//:: Next, extend 'new' to handle a string literal argument.</span>
<span class="Delimiter">:(scenario new_string)</span>
recipe main [
<span class="Constant">1</span>:address:array:character<span class="Special"> <- </span>new [abc def]
<span class="Constant">2</span>:character<span class="Special"> <- </span>index <span class="Constant">1</span>:address:array:character/deref<span class="Delimiter">,</span> <span class="Constant">5</span>:literal
]
<span class="Comment"># number code for 'e'</span>
<span class="traceContains">+mem: storing 101 in location 2</span>
<span class="Delimiter">:(before "End NEW Transform Special-cases")</span>
if <span class="Delimiter">(</span>inst<span class="Delimiter">.</span>ingredients<span class="Delimiter">.</span>at<span class="Delimiter">(</span><span class="Constant">0</span><span class="Delimiter">).</span>properties<span class="Delimiter">.</span>at<span class="Delimiter">(</span><span class="Constant">0</span><span class="Delimiter">).</span>second<span class="Delimiter">.</span>at<span class="Delimiter">(</span><span class="Constant">0</span><span class="Delimiter">)</span> == <span class="Constant">"literal-string"</span><span class="Delimiter">)</span> <span class="Delimiter">{</span>
<span class="Comment">// skip transform</span>
inst<span class="Delimiter">.</span>ingredients<span class="Delimiter">.</span>at<span class="Delimiter">(</span><span class="Constant">0</span><span class="Delimiter">).</span>initialized = <span class="Constant">true</span><span class="Delimiter">;</span>
<span class="Identifier">goto</span> end_new_transform<span class="Delimiter">;</span>
<span class="Delimiter">}</span>
<span class="Delimiter">:(after "case NEW" following "Primitive Recipe Implementations")</span>
if <span class="Delimiter">(</span>isa_literal<span class="Delimiter">(</span>current_instruction<span class="Delimiter">().</span>ingredients<span class="Delimiter">.</span>at<span class="Delimiter">(</span><span class="Constant">0</span><span class="Delimiter">))</span>
&& current_instruction<span class="Delimiter">().</span>ingredients<span class="Delimiter">.</span>at<span class="Delimiter">(</span><span class="Constant">0</span><span class="Delimiter">).</span>properties<span class="Delimiter">.</span>at<span class="Delimiter">(</span><span class="Constant">0</span><span class="Delimiter">).</span>second<span class="Delimiter">.</span>at<span class="Delimiter">(</span><span class="Constant">0</span><span class="Delimiter">)</span> == <span class="Constant">"literal-string"</span><span class="Delimiter">)</span> <span class="Delimiter">{</span>
<span class="Comment">// allocate an array just large enough for it</span>
long long int string_length = SIZE<span class="Delimiter">(</span>current_instruction<span class="Delimiter">().</span>ingredients<span class="Delimiter">.</span>at<span class="Delimiter">(</span><span class="Constant">0</span><span class="Delimiter">).</span>name<span class="Delimiter">);</span>
<span class="CommentedCode">//? cout << "string_length is " << string_length << '\n'; //? 1</span>
ensure_space<span class="Delimiter">(</span>string_length+<span class="Constant">1</span><span class="Delimiter">);</span> <span class="Comment">// don't forget the extra location for array size</span>
products<span class="Delimiter">.</span>resize<span class="Delimiter">(</span><span class="Constant">1</span><span class="Delimiter">);</span>
products<span class="Delimiter">.</span>at<span class="Delimiter">(</span><span class="Constant">0</span><span class="Delimiter">).</span>push_back<span class="Delimiter">(</span>Current_routine<span class="Delimiter">-></span>alloc<span class="Delimiter">);</span>
<span class="Comment">// initialize string</span>
<span class="CommentedCode">//? cout << "new string literal: " << current_instruction().ingredients.at(0).name << '\n'; //? 1</span>
Memory[Current_routine<span class="Delimiter">-></span>alloc++] = string_length<span class="Delimiter">;</span>
for <span class="Delimiter">(</span>long long int i = <span class="Constant">0</span><span class="Delimiter">;</span> i < string_length<span class="Delimiter">;</span> ++i<span class="Delimiter">)</span> <span class="Delimiter">{</span>
Memory[Current_routine<span class="Delimiter">-></span>alloc++] = current_instruction<span class="Delimiter">().</span>ingredients<span class="Delimiter">.</span>at<span class="Delimiter">(</span><span class="Constant">0</span><span class="Delimiter">).</span>name<span class="Delimiter">.</span>at<span class="Delimiter">(</span>i<span class="Delimiter">);</span>
<span class="Delimiter">}</span>
<span class="Comment">// mu strings are not null-terminated in memory</span>
<span class="Identifier">break</span><span class="Delimiter">;</span>
<span class="Delimiter">}</span>
<span class="Comment">//: Allocate more to routine when initializing a literal string</span>
<span class="Delimiter">:(scenario new_string_overflow)</span>
<span class="Special">% Initial_memory_per_routine = 2;</span>
recipe main [
<span class="Constant">1</span>:address:number/<span class="Special">raw <- </span>new number:type
<span class="Constant">2</span>:address:array:character/<span class="Special">raw <- </span>new [a] <span class="Comment"># not enough room in initial page, if you take the array size into account</span>
]
<span class="traceContains">+new: routine allocated memory from 1000 to 1002</span>
<span class="traceContains">+new: routine allocated memory from 1002 to 1004</span>
</pre>
</body>
</html>
<!-- vim: set foldmethod=manual : -->
|