Mu - 073wait.cc

  1 //: Routines can be put in a 'waiting' state, from which it will be ready to
  2 //: run again when a specific memory location changes its value. This is Mu's
  3 //: basic technique for orchestrating the order in which different routines
  4 //: operate.
  5 
  6 :(scenario wait_for_location)
  7 def f1 [
  8   10:num <- copy 34
  9   start-running f2
 10   20:location <- copy 10/unsafe
 11   wait-for-reset-then-set 20:location
 12   # wait for f2 to run and reset location 1
 13   30:num <- copy 10:num
 14 ]
 15 def f2 [
 16   10:location <- copy 0/unsafe
 17 ]
 18 +schedule: f1
 19 +run: waiting for location 10 to reset
 20 +schedule: f2
 21 +schedule: waking up routine 1
 22 +schedule: f1
 23 +mem: storing 1 in location 30
 24 
 25 //: define the new state that all routines can be in
 26 
 27 :(before "End routine States")
 28 WAITING,
 29 :(before "End routine Fields")
 30 // only if state == WAITING
 31 int waiting_on_location;
 32 :(before "End routine Constructor")
 33 waiting_on_location = 0;
 34 
 35 :(before "End Mu Test Teardown")
 36 if (Passed && any_routines_waiting())
 37   raise << Current_scenario->name << ": deadlock!\n" << end();
 38 :(before "End Run Routine")
 39 if (any_routines_waiting()) {
 40   raise << "deadlock!\n" << end();
 41   dump_waiting_routines();
 42 }
 43 :(before "End Test Teardown")
 44 if (Passed && any_routines_with_error())
 45   raise << "some routines died with errors\n" << end();
 46 :(code)
 47 bool any_routines_waiting() {
 48   for (int i = 0;  i < SIZE(Routines);  ++i) {
 49   ¦ if (Routines.at(i)->state == WAITING)
 50   ¦ ¦ return true;
 51   }
 52   return false;
 53 }
 54 void dump_waiting_routines() {
 55   for (int i = 0;  i < SIZE(Routines);  ++i) {
 56   ¦ if (Routines.at(i)->state == WAITING)
 57   ¦ ¦ cerr << i << ": " << routine_label(Routines.at(i)) << '\n';
 58   }
 59 }
 60 
 61 :(scenario wait_for_location_can_deadlock)
 62 % Hide_errors = true;
 63 def main [
 64   10:num <- copy 1
 65   20:location <- copy 10/unsafe
 66   wait-for-reset-then-set 20:location
 67 ]
 68 +error: deadlock!
 69 
 70 //: Primitive recipe to put routines in that state.
 71 //: This primitive is also known elsewhere as compare-and-set (CAS). Used to
 72 //: build locks.
 73 
 74 :(before "End Primitive Recipe Declarations")
 75 WAIT_FOR_RESET_THEN_SET,
 76 :(before "End Primitive Recipe Numbers")
 77 put(Recipe_ordinal, "wait-for-reset-then-set", WAIT_FOR_RESET_THEN_SET);
 78 :(before "End Primitive Recipe Checks")
 79 case WAIT_FOR_RESET_THEN_SET: {
 80   if (SIZE(inst.ingredients) != 1) {
 81   ¦ raise << maybe(get(Recipe, r).name) << "'wait-for-reset-then-set' requires exactly one ingredient, but got '" << inst.original_string << "'\n" << end();
 82   ¦ break;
 83   }
 84   if (!is_mu_location(inst.ingredients.at(0))) {
 85   ¦ raise << maybe(get(Recipe, r).name) << "'wait-for-reset-then-set' requires a location ingredient, but got '" << inst.ingredients.at(0).original_string << "'\n" << end();
 86   }
 87   break;
 88 }
 89 :(before "End Primitive Recipe Implementations")
 90 case WAIT_FOR_RESET_THEN_SET: {
 91   int loc = static_cast<int>(ingredients.at(0).at(0));
 92   trace(9998, "run") << "wait: *" << loc << " = " << get_or_insert(Memory, loc) << end();
 93   if (get_or_insert(Memory, loc) == 0) {
 94   ¦ trace(9998, "run") << "location " << loc << " is already 0; setting" << end();
 95   ¦ put(Memory, loc, 1);
 96   ¦ break;
 97   }
 98   trace(9998, "run") << "waiting for location " << loc << " to reset" << end();
 99   Current_routine->state = WAITING;
100   Current_routine->waiting_on_location = loc;
101   break;
102 }
103 
104 //: Counterpart to unlock a lock.
105 :(before "End Primitive Recipe Declarations")
106 RESET,
107 :(before "End Primitive Recipe Numbers")
108 put(Recipe_ordinal, "reset", RESET);
109 :(before "End Primitive Recipe Checks")
110 case RESET: {
111   if (SIZE(inst.ingredients) != 1) {
112   ¦ raise << maybe(get(Recipe, r).name) << "'reset' requires exactly one ingredient, but got '" << inst.original_string << "'\n" << end();
113   ¦ break;
114   }
115   if (!is_mu_location(inst.ingredients.at(0))) {
116   ¦ raise << maybe(get(Recipe, r).name) << "'reset' requires a location ingredient, but got '" << inst.ingredients.at(0).original_string << "'\n" << end();
117   }
118   break;
119 }
120 :(before "End Primitive Recipe Implementations")
121 case RESET: {
122   int loc = static_cast<int>(ingredients.at(0).at(0));
123   put(Memory, loc, 0);
124   trace(9998, "run") << "reset: *" << loc << " = " << get_or_insert(Memory, loc) << end();
125   break;
126 }
127 
128 //: scheduler tweak to get routines out of that state
129 
130 :(before "End Scheduler State Transitions")
131 for (int i = 0;  i < SIZE(Routines);  ++i) {
132   if (Routines.at(i)->state != WAITING) continue;
133   int loc = Routines.at(i)->waiting_on_location;
134   if (loc && get_or_insert(Memory, loc) == 0) {
135   ¦ trace(9999, "schedule") << "waking up routine " << Routines.at(i)->id << end();
136   ¦ put(Memory, loc, 1);
137   ¦ Routines.at(i)->state = RUNNING;
138   ¦ Routines.at(i)->waiting_on_location = 0;
139   }
140 }
141 
142 //: Primitive to help compute locations to wait on.
143 //: Only supports elements immediately inside containers; no arrays or
144 //: containers within containers yet.
145 
146 :(scenario get_location)
147 def main [
148   12:num <- copy 34
149   13:num <- copy 35
150   15:location <- get-location 12:point, 1:offset
151 ]
152 +mem: storing 13 in location 15
153 
154 :(before "End Primitive Recipe Declarations")
155 GET_LOCATION,
156 :(before "End Primitive Recipe Numbers")
157 put(Recipe_ordinal, "get-location", GET_LOCATION);
158 :(before "End Primitive Recipe Checks")
159 case GET_LOCATION: {
160   if (SIZE(inst.ingredients) != 2) {
161   ¦ raise << maybe(get(Recipe, r).name) << "'get-location' expects exactly 2 ingredients in '" << inst.original_string << "'\n" << end();
162   ¦ break;
163   }
164   reagent/*copy*/ base = inst.ingredients.at(0);
165   if (!canonize_type(base)) break;
166   if (!base.type) {
167   ¦ raise << maybe(get(Recipe, r).name) << "first ingredient of 'get-location' should be a container, but got '" << inst.ingredients.at(0).original_string << "'\n" << end();
168   ¦ break;
169   }
170   const type_tree* base_root_type = base.type->atom ? base.type : base.type->left;
171   if (!base_root_type->atom || base_root_type->value == 0 || !contains_key(Type, base_root_type->value) || get(Type, base_root_type->value).kind != CONTAINER) {
172   ¦ raise << maybe(get(Recipe, r).name) << "first ingredient of 'get-location' should be a container, but got '" << inst.ingredients.at(0).original_string << "'\n" << end();
173   ¦ break;
174   }
175   type_ordinal base_type = base.type->value;
176   const reagent& offset = inst.ingredients.at(1);
177   if (!is_literal(offset) || !is_mu_scalar(offset)) {
178   ¦ raise << maybe(get(Recipe, r).name) << "second ingredient of 'get-location' should have type 'offset', but got '" << inst.ingredients.at(1).original_string << "'\n" << end();
179   ¦ break;
180   }
181   int offset_value = 0;
182   //: later layers will permit non-integer offsets
183   if (is_integer(offset.name)) {
184   ¦ offset_value = to_integer(offset.name);
185   ¦ if (offset_value < 0 || offset_value >= SIZE(get(Type, base_type).elements)) {
186   ¦ ¦ raise << maybe(get(Recipe, r).name) << "invalid offset " << offset_value << " for '" << get(Type, base_type).name << "'\n" << end();
187   ¦ ¦ break;
188   ¦ }
189   }
190   else {
191   ¦ offset_value = offset.value;
192   }
193   if (inst.products.empty()) break;
194   if (!is_mu_location(inst.products.at(0))) {
195   ¦ raise << maybe(get(Recipe, r).name) << "'get-location " << base.original_string << ", " << offset.original_string << "' should write to type location but '" << inst.products.at(0).name << "' has type '" << names_to_string_without_quotes(inst.products.at(0).type) << "'\n" << end();
196   ¦ break;
197   }
198   break;
199 }
200 :(before "End Primitive Recipe Implementations")
201 case GET_LOCATION: {
202   reagent/*copy*/ base = current_instruction().ingredients.at(0);
203   canonize(base);
204   int base_address = base.value;
205   if (base_address == 0) {
206   ¦ raise << maybe(current_recipe_name()) << "tried to access location 0 in '" << to_original_string(current_instructionspan class="Delimiter">:(before &quot;End Rewrite Instruction(curr)&quot;)</span>
<span class="Comment">// rewrite `assume-screen width, height` to</span>
<span class="Comment">// `screen:address &lt;- init-fake-screen width, height`</span>
<span class="CommentedCode">//? cout &lt;&lt; &quot;before: &quot; &lt;&lt; curr.to_string() &lt;&lt; '\n'; //? 1</span>
if <span class="Delimiter">(</span>curr<span class="Delimiter">.</span>name == <span class="Constant">&quot;assume-screen&quot;</span><span class="Delimiter">)</span> <span class="Delimiter">{</span>
  curr<span class="Delimiter">.</span>operation = Recipe_number[<span class="Constant">&quot;init-fake-screen&quot;</span>]<span class="Delimiter">;</span>
  assert<span class="Delimiter">(</span>curr<span class="Delimiter">.</span>products<span class="Delimiter">.</span>empty<span class="Delimiter">());</span>
  curr<span class="Delimiter">.</span>products<span class="Delimiter">.</span>push_back<span class="Delimiter">(</span>reagent<span class="Delimiter">(</span><span class="Constant">&quot;screen:address&quot;</span><span class="Delimiter">));</span>
  curr<span class="Delimiter">.</span>products<span class="Delimiter">.</span>at<span class="Delimiter">(</span><span class="Constant">0</span><span class="Delimiter">).</span>set_value<span class="Delimiter">(</span>SCREEN<span class="Delimiter">);</span>
<span class="CommentedCode">//? cout &lt;&lt; &quot;after: &quot; &lt;&lt; curr.to_string() &lt;&lt; '\n'; //? 1</span>
<span class="CommentedCode">//? cout &lt;&lt; &quot;AAA &quot; &lt;&lt; Recipe_number[&quot;init-fake-screen&quot;] &lt;&lt; '\n'; //? 1</span>
<span class="Delimiter">}</span>

<span class="Comment">//: screen-should-contain is a regular instruction</span>
<span class="Delimiter">:(before &quot;End Primitive Recipe Declarations&quot;)</span>
SCREEN_SHOULD_CONTAIN<span class="Delimiter">,</span>
<span class="Delimiter">:(before &quot;End Primitive Recipe Numbers&quot;)</span>
Recipe_number[<span class="Constant">&quot;screen-should-contain&quot;</span>] = SCREEN_SHOULD_CONTAIN<span class="Delimiter">;</span>
<span class="Delimiter">:(before &quot;End Primitive Recipe Implementations&quot;)</span>
case SCREEN_SHOULD_CONTAIN: <span class="Delimiter">{</span>
<span class="CommentedCode">//?   cout &lt;&lt; &quot;AAA\n&quot;; //? 1</span>
  check_screen<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="Identifier">break</span><span class="Delimiter">;</span>
<span class="Delimiter">}</span>

<span class="Delimiter">:(code)</span>
void check_screen<span class="Delimiter">(</span>const string&amp; contents<span class="Delimiter">)</span> <span class="Delimiter">{</span>
<span class="CommentedCode">//?   cerr &lt;&lt; &quot;Checking screen\n&quot;; //? 1</span>
  assert<span class="Delimiter">(</span>!Current_routine<span class="Delimiter">-&gt;</span>calls<span class="Delimiter">.</span>front<span class="Delimiter">().</span>default_space<span class="Delimiter">);</span>  <span class="Comment">// not supported</span>
  index_t screen_location = Memory[SCREEN]<span class="Delimiter">;</span>
  int data_offset = find_element_name<span class="Delimiter">(</span>Type_number[<span class="Constant">&quot;screen&quot;</span>]<span class="Delimiter">,</span> <span class="Constant">&quot;data&quot;</span><span class="Delimiter">);</span>
  assert<span class="Delimiter">(</span>data_offset &gt;= <span class="Constant">0</span><span class="Delimiter">);</span>
  index_t screen_data_location = screen_location+data_offset<span class="Delimiter">;</span>  <span class="Comment">// type: address:array:character</span>
  index_t screen_data_start = Memory[screen_data_location]<span class="Delimiter">;</span>  <span class="Comment">// type: array:character</span>
  int width_offset = find_element_name<span class="Delimiter">(</span>Type_number[<span class="Constant">&quot;screen&quot;</span>]<span class="Delimiter">,</span> <span class="Constant">&quot;num-columns&quot;</span><span class="Delimiter">);</span>
  size_t screen_width = Memory[screen_location+width_offset]<span class="Delimiter">;</span>
  int height_offset = find_element_name<span class="Delimiter">(</span>Type_number[<span class="Constant">&quot;screen&quot;</span>]<span class="Delimiter">,</span> <span class="Constant">&quot;num-rows&quot;</span><span class="Delimiter">);</span>
  size_t screen_height = Memory[screen_location+height_offset]<span class="Delimiter">;</span>
  string expected_contents<span class="Delimiter">;</span>
  istringstream in<span class="Delimiter">(</span>contents<span class="Delimiter">);</span>
  in &gt;&gt; std::noskipws<span class="Delimiter">;</span>
  for <span class="Delimiter">(</span>index_t row = <span class="Constant">0</span><span class="Delimiter">;</span> row &lt; screen_height<span class="Delimiter">;</span> ++row<span class="Delimiter">)</span> <span class="Delimiter">{</span>
    skip_whitespace_and_comments<span class="Delimiter">(</span>in<span class="Delimiter">);</span>
    assert<span class="Delimiter">(</span>!in<span class="Delimiter">.</span>eof<span class="Delimiter">());</span>
    assert<span class="Delimiter">(</span>in<span class="Delimiter">.</span>get<span class="Delimiter">()</span> == <span class="Constant">'.'</span><span class="Delimiter">);</span>
    for <span class="Delimiter">(</span>index_t column = <span class="Constant">0</span><span class="Delimiter">;</span> column &lt; screen_width<span class="Delimiter">;</span> ++column<span class="Delimiter">)</span> <span class="Delimiter">{</span>
      assert<span class="Delimiter">(</span>!in<span class="Delimiter">.</span>eof<span class="Delimiter">());</span>
      expected_contents += in<span class="Delimiter">.</span>get<span class="Delimiter">();</span>
    <span class="Delimiter">}</span>
    assert<span class="Delimiter">(</span>in<span class="Delimiter">.</span>get<span class="Delimiter">()</span> == <span class="Constant">'.'</span><span class="Delimiter">);</span>
  <span class="Delimiter">}</span>
  skip_whitespace_and_comments<span class="Delimiter">(</span>in<span class="Delimiter">);</span>
<span class="CommentedCode">//?   assert(in.get() == ']');</span>
  trace<span class="Delimiter">(</span><span class="Constant">&quot;run&quot;</span><span class="Delimiter">)</span> &lt;&lt; <span class="Constant">&quot;checking screen size at &quot;</span> &lt;&lt; screen_data_start<span class="Delimiter">;</span>
<span class="CommentedCode">//?   cout &lt;&lt; expected_contents.size() &lt;&lt; '\n'; //? 1</span>
  if <span class="Delimiter">(</span>Memory[screen_data_start] &gt; static_cast&lt;signed&gt;<span class="Delimiter">(</span>expected_contents<span class="Delimiter">.</span>size<span class="Delimiter">()))</span>
    raise &lt;&lt; <span class="Constant">&quot;expected contents are larger than screen size &quot;</span> &lt;&lt; Memory[screen_data_start] &lt;&lt; <span class="cSpecial">'\n'</span><span class="Delimiter">;</span>
  ++screen_data_start<span class="Delimiter">;</span>  <span class="Comment">// now skip length</span>
  for <span class="Delimiter">(</span>index_t i = <span class="Constant">0</span><span class="Delimiter">;</span> i &lt; expected_contents<span class="Delimiter">.</span>size<span class="Delimiter">();</span> ++i<span class="Delimiter">)</span> <span class="Delimiter">{</span>
    trace<span class="Delimiter">(</span><span class="Constant">&quot;run&quot;</span><span class="Delimiter">)</span> &lt;&lt; <span class="Constant">&quot;checking location &quot;</span> &lt;&lt; screen_data_start+i<span class="Delimiter">;</span>
<span class="CommentedCode">//?     cerr &lt;&lt; &quot;comparing &quot; &lt;&lt; i/screen_width &lt;&lt; &quot;, &quot; &lt;&lt; i%screen_width &lt;&lt; &quot;: &quot; &lt;&lt; Memory[screen_data_start+i] &lt;&lt; &quot; vs &quot; &lt;&lt; (int)expected_contents.at(i) &lt;&lt; '\n'; //? 1</span>
    if <span class="Delimiter">((</span>!Memory[screen_data_start+i] &amp;&amp; !isspace<span class="Delimiter">(</span>expected_contents<span class="Delimiter">.</span>at<span class="Delimiter">(</span>i<span class="Delimiter">)))</span>  <span class="Comment">// uninitialized memory =&gt; spaces</span>
        || <span class="Delimiter">(</span>Memory[screen_data_start+i] &amp;&amp; Memory[screen_data_start+i] != expected_contents<span class="Delimiter">.</span>at<span class="Delimiter">(</span>i<span class="Delimiter">)))</span> <span class="Delimiter">{</span>
<span class="CommentedCode">//?       cerr &lt;&lt; &quot;CCC &quot; &lt;&lt; Trace_stream &lt;&lt; &quot; &quot; &lt;&lt; Hide_warnings &lt;&lt; '\n'; //? 1</span>
      if <span class="Delimiter">(</span>Current_scenario &amp;&amp; !Hide_warnings<span class="Delimiter">)</span> <span class="Delimiter">{</span>
        <span class="Comment">// genuine test in a mu file</span>
        raise &lt;&lt; <span class="Constant">&quot;</span><span class="cSpecial">\n</span><span class="Constant">F - &quot;</span> &lt;&lt; Current_scenario<span class="Delimiter">-&gt;</span>name &lt;&lt; <span class="Constant">&quot;: expected screen location (&quot;</span> &lt;&lt; i/screen_width &lt;&lt; <span class="Constant">&quot;, &quot;</span> &lt;&lt; i%screen_width &lt;&lt; <span class="Constant">&quot;) to contain '&quot;</span> &lt;&lt; expected_contents<span class="Delimiter">.</span>at<span class="Delimiter">(</span>i<span class="Delimiter">)</span> &lt;&lt; <span class="Constant">&quot;' instead of '&quot;</span> &lt;&lt; static_cast&lt;char&gt;<span class="Delimiter">(</span>Memory[screen_data_start+i]<span class="Delimiter">)</span> &lt;&lt; <span class="Constant">&quot;'</span><span class="cSpecial">\n</span><span class="Constant">&quot;</span><span class="Delimiter">;</span>
        dump_screen<span class="Delimiter">();</span>
      <span class="Delimiter">}</span>
      else <span class="Delimiter">{</span>
        <span class="Comment">// just testing check_screen</span>
        raise &lt;&lt; <span class="Constant">&quot;expected screen location (&quot;</span> &lt;&lt; i/screen_width &lt;&lt; <span class="Constant">&quot;, &quot;</span> &lt;&lt; i%screen_width &lt;&lt; <span class="Constant">&quot;) to contain '&quot;</span> &lt;&lt; expected_contents<span class="Delimiter">.</span>at<span class="Delimiter">(</span>i<span class="Delimiter">)</span> &lt;&lt; <span class="Constant">&quot;' instead of '&quot;</span> &lt;&lt; static_cast&lt;char&gt;<span class="Delimiter">(</span>Memory[screen_data_start+i]<span class="Delimiter">)</span> &lt;&lt; <span class="Constant">&quot;'</span><span class="cSpecial">\n</span><span class="Constant">&quot;</span><span class="Delimiter">;</span>
      <span class="Delimiter">}</span>
      if <span class="Delimiter">(</span>!Hide_warnings<span class="Delimiter">)</span> <span class="Delimiter">{</span>
        Passed = <span class="Constant">false</span><span class="Delimiter">;</span>
        ++Num_failures<span class="Delimiter">;</span>
      <span class="Delimiter">}</span>
      <span class="Identifier">return</span><span class="Delimiter">;</span>
    <span class="Delimiter">}</