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 '" << to_original_string(inst) << "'\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 '" << to_original_string(inst) << "'\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("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 '" << to_original_string(inst) << "'\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_instruction()) << "'\n" << end();
207     break;
208   }
209   const type_tree* base_type = get_base_type(base.type);
210   int offset = ingredients.at(1).at(0);
211   if (offset < 0 || offset >= SIZE(get(Type, base_type->value).elements)) break;  // copied from Check above
212   int result = base_address;
213   for (int i = 0;  i < offset;  ++i)
214     result += size_of(element_type(base.type, i));
215   trace(9998, "run") << "address to copy is " << result << end();
216   products.resize(1);
217   products.at(0).push_back(result);
218   break;
219 }
220 
221 :(code)
222 bool is_mu_location(reagent/*copy*/ x) {
223   if (!canonize_type(x)) return false;
224   if (!x.type) return false;
225   if (!x.type->atom) return false;
226   return x.type->value == get(Type_ordinal, "location");
227 }
228 
229 :(scenario get_location_out_of_bounds)
230 % Hide_errors = true;
231 def main [
232   12:num <- copy 34
233   13:num <- copy 35
234   14:num <- copy 36
235   get-location 12:point-number/raw, 2:offset  # point-number occupies 3 locations but has only 2 fields; out of bounds
236 ]
237 +error: main: invalid offset 2 for 'point-number'
238 
239 :(scenario get_location_out_of_bounds_2)
240 % Hide_errors = true;
241 def main [
242   12:num <- copy 34
243   13:num <- copy 35
244   14:num <- copy 36
245   get-location 12:point-number/raw, -1:offset
246 ]
247 +error: main: invalid offset -1 for 'point-number'
248 
249 :(scenario get_location_product_type_mismatch)
250 % Hide_errors = true;
251 container boolbool [
252   x:bool
253   y:bool
254 ]
255 def main [
256   12:bool <- copy 1
257   13:bool <- copy 0
258   15:bool <- get-location 12:boolbool, 1:offset
259 ]
260 +error: main: 'get-location 12:boolbool, 1:offset' should write to type location but '15' has type 'boolean'
261 
262 :(scenario get_location_indirect)
263 # 'get-location' can read from container address
264 def main [
265   1:num <- copy 10
266   10:num <- copy 34
267   11:num <- copy 35
268   4:location <- get-location 1:&:point/lookup, 0:offset
269 ]
270 +mem: storing 10 in location 4
271 
272 :(scenario get_location_indirect_2)
273 def main [
274   1:num <- copy 10
275   10:num <- copy 34
276   11:num <- copy 35
277   4:&:num <- copy 20/unsafe
278   4:&:location/lookup <- get-location 1:&:point/lookup, 0:offset
279 ]
280 +mem: storing 10 in location 20
281 
282 //: allow waiting on a routine to complete
283 
284 :(scenario wait_for_routine)
285 def f1 [
286   # add a few routines to run
287   1:num/routine <- start-running f2
288   2:num/routine <- start-running f3
289   wait-for-routine 1:num/routine
290   # now wait for f2 to *complete* and modify location 13 before using its value
291   20:num <- copy 13:num
292 ]
293 def f2 [
294   10:num <- copy 0  # just padding
295   switch  # simulate a block; routine f1 shouldn't restart at this point
296   13:num <- copy 34
297 ]
298 def f3 [
299   # padding routine just to help simulate the block in f2 using 'switch'
300   11:num <- copy 0
301   12:num <- copy 0
302 ]
303 +schedule: f1
304 +run: waiting for routine 2
305 +schedule: f2
306 +schedule: f3
307 +schedule: f2
308 +schedule: waking up routine 1
309 +schedule: f1
310 # if we got the synchronization wrong we'd be storing 0 in location 20
311 +mem: storing 34 in location 20
312 
313 :(before "End routine Fields")
314 // only if state == WAITING
315 int waiting_on_routine;
316 :(before "End routine Constructor")
317 waiting_on_routine = 0;
318 
319 :(before "End Primitive Recipe Declarations")
320 WAIT_FOR_ROUTINE,
321 :(before "End Primitive Recipe Numbers")
322 put(Recipe_ordinal, "wait-for-routine", WAIT_FOR_ROUTINE);
323 :(before "End Primitive Recipe Checks")
324 case WAIT_FOR_ROUTINE: {
325   if (SIZE(inst.ingredients) != 1) {
326     raise << maybe(get(Recipe, r).name) << "'wait-for-routine' requires exactly one ingredient, but got '" << to_original_string(inst) << "'\n" << end();
327     break;
328   }
329   if (!is_mu_number(inst.ingredients.at(0))) {
330     raise << maybe(get(Recipe, r).name) << "first ingredient of 'wait-for-routine' should be a routine id generated by 'start-running', but got '" << inst.ingredients.at(0).original_string << "'\n" << end();
331     break;
332   }
333   break;
334 }
335 :(before "End Primitive Recipe Implementations")
336 case WAIT_FOR_ROUTINE: {
337   if (ingredients.at(0).at(0) == Current_routine->id) {
338     raise << maybe(current_recipe_name()) << "routine can't wait for itself! '" << to_original_string(current_instruction()) << "'\n" << end();
339     break;
340   }
341   Current_routine->state = WAITING;
342   Current_routine->waiting_on_routine = ingredients.at(0).at(0);
343   trace(9998, "run") << "waiting for routine " << ingredients.at(0).at(0) << end();
344   break;
345 }
346 
347 :(before "End Scheduler State Transitions")
348 // Wake up any routines waiting for other routines to complete.
349 // Important: this must come after the scheduler loop above giving routines
350 // waiting for locations to change a chance to wake up.
351 for (int i = 0;  i < SIZE(Routines);  ++i) {
352   if (Routines.at(i)->state != WAITING) continue;
353   routine* waiter = Routines.at(i);
354   if (!waiter->waiting_on_routine) continue;
355   int id = waiter->waiting_on_routine;
356   assert(id != waiter->id);  // routine can't wait on itself
357   for (int j = 0;  j < SIZE(Routines);  ++j) {
358     const routine* waitee = Routines.at(j);
359     if (waitee->id == id && waitee->state != RUNNING && waitee->state != WAITING) {
360       // routine is COMPLETED or DISCONTINUED
361       trace("schedule") << "waking up routine " << waiter->id << end();
362       waiter->state = RUNNING;
363       waiter->waiting_on_routine = 0;
364     }
365   }
366 }
367 
368 //: yield voluntarily to let some other routine run
369 
370 :(before "End Primitive Recipe Declarations")
371 SWITCH,
372 :(before "End Primitive Recipe Numbers")
373 put(Recipe_ordinal, "switch", SWITCH);
374 :(before "End Primitive Recipe Checks")
375 case SWITCH: {
376   break;
377 }
378 :(before "End Primitive Recipe Implementations")
379 case SWITCH: {
380   ++current_step_index();
381   goto stop_running_current_routine;
382 }
383 
384 :(scenario switch_preempts_current_routine)
385 def f1 [
386   start-running f2
387   1:num <- copy 34
388   switch
389   3:num <- copy 36
390 ]
391 def f2 [
392   2:num <- copy 35
393 ]
394 +mem: storing 34 in location 1
395 # context switch
396 +mem: storing 35 in location 2
397 # back to original thread
398 +mem: storing 36 in location 3
399 
400 //:: helpers for manipulating routines in tests
401 //:
402 //: Managing arbitrary scenarios requires the ability to:
403 //:   a) check if a routine is blocked
404 //:   b) restart a blocked routine ('restart')
405 //:
406 //: A routine is blocked either if it's waiting or if it explicitly signals
407 //: that it's blocked (even as it periodically wakes up and polls for some
408 //: event).
409 //:
410 //: Signalling blockedness might well be a huge hack. But Mu doesn't have Unix
411 //: signals to avoid polling with, because signals are also pretty hacky.
412 
413 :(before "End routine Fields")
414 bool blocked;
415 :(before "End routine Constructor")
416 blocked = false;
417 
418 :(before "End Primitive Recipe Declarations")
419 CURRENT_ROUTINE_IS_BLOCKED,
420 :(before "End Primitive Recipe Numbers")
421 put(Recipe_ordinal, "current-routine-is-blocked", CURRENT_ROUTINE_IS_BLOCKED);
422 :(before "End Primitive Recipe Checks")
423 case CURRENT_ROUTINE_IS_BLOCKED: {
424   if (!inst.ingredients.empty()) {
425     raise << maybe(get(Recipe, r).name) << "'current-routine-is-blocked' should have no ingredients, but got '" << to_original_string(inst) << "'\n" << end();
426     break;
427   }
428   break;
429 }
430 :(before "End Primitive Recipe Implementations")
431 case CURRENT_ROUTINE_IS_BLOCKED: {
432   Current_routine->blocked = true;
433   break;
434 }
435 
436 :(before "End Primitive Recipe Declarations")
437 CURRENT_ROUTINE_IS_UNBLOCKED,
438 :(before "End Primitive Recipe Numbers")
439 put(Recipe_ordinal, "current-routine-is-unblocked", CURRENT_ROUTINE_IS_UNBLOCKED);
440 :(before "End Primitive Recipe Checks")
441 case CURRENT_ROUTINE_IS_UNBLOCKED: {
442   if (!inst.ingredients.empty()) {
443     raise << maybe(get(Recipe, r).name) << "'current-routine-is-unblocked' should have no ingredients, but got '" << to_original_string(inst) << "'\n" << end();
444     break;
445   }
446   break;
447 }
448 :(before "End Primitive Recipe Implementations")
449 case CURRENT_ROUTINE_IS_UNBLOCKED: {
450   Current_routine->blocked = false;
451   break;
452 }
453 
454 //: also allow waiting on a routine to block
455 //: (just for tests; use wait_for_routine above wherever possible)
456 
457 :(scenario wait_for_routine_to_block)
458 def f1 [
459   1:num/routine <- start-running f2
460   wait-for-routine-to-block 1:num/routine
461   # now wait for f2 to run and modify location 10 before using its value
462   11:num <- copy 10:num
463 ]
464 def f2 [
465   10:num <- copy 34
466 ]
467 +schedule: f1
468 +run: waiting for routine 2 to block
469 +schedule: f2
470 +schedule: waking up routine 1 because routine 2 is blocked
471 +schedule: f1
472 # if we got the synchronization wrong we'd be storing 0 in location 11
473 +mem: storing 34 in location 11
474 
475 :(before "End routine Fields")
476 // only if state == WAITING
477 int waiting_on_routine_to_block;
478 :(before "End routine Constructor")
479 waiting_on_routine_to_block = 0;
480 
481 :(before "End Primitive Recipe Declarations")
482 WAIT_FOR_ROUTINE_TO_BLOCK,
483 :(before "End Primitive Recipe Numbers")
484 put(Recipe_ordinal, "wait-for-routine-to-block", WAIT_FOR_ROUTINE_TO_BLOCK);
485 :(before "End Primitive Recipe Checks")
486 case WAIT_FOR_ROUTINE_TO_BLOCK: {
487   if (SIZE(inst.ingredients) != 1) {
488     raise << maybe(get(Recipe, r).name) << "'wait-for-routine-to-block' requires exactly one ingredient, but got '" << to_original_string(inst) << "'\n" << end();
489     break;
490   }
491   if (!is_mu_number(inst.ingredients.at(0))) {
492     raise << maybe(get(Recipe, r).name) << "first ingredient of 'wait-for-routine-to-block' should be a routine id generated by 'start-running', but got '" << inst.ingredients.at(0).original_string << "'\n" << end();
493     break;
494   }
495   break;
496 }
497 :(before "End Primitive Recipe Implementations")
498 case WAIT_FOR_ROUTINE_TO_BLOCK: {
499   if (ingredients.at(0).at(0) == Current_routine->id) {
500     raise << maybe(current_recipe_name()) << "routine can't wait for itself! '" << to_original_string(current_instruction()) << "'\n" << end();
501     break;
502   }
503   Current_routine->state = WAITING;
504   Current_routine->waiting_on_routine_to_block = ingredients.at(0).at(0);
505   trace(9998, "run") << "waiting for routine " << ingredients.at(0).at(0) << " to block" << end();
506   break;
507 }
508 
509 :(before "End Scheduler State Transitions")
510 // Wake up any routines waiting for other routines to stop running.
511 for (int i = 0;  i < SIZE(Routines);  ++i) {
512   if (Routines.at(i)->state != WAITING) continue;
513   routine* waiter = Routines.at(i);
514   if (!waiter->waiting_on_routine_to_block) continue;
515   int id = waiter->waiting_on_routine_to_block;
516   assert(id != waiter->id);  // routine can't wait on itself
517   for (int j = 0;  j < SIZE(Routines);  ++j) {
518     const routine* waitee = Routines.at(j);
519     if (waitee->id != id) continue;
520     if (waitee->state != RUNNING || waitee->blocked) {
521       trace("schedule") << "waking up routine " << waiter->id << " because routine " << waitee->id << " is blocked" << end();
522       waiter->state = RUNNING;
523       waiter->waiting_on_routine_to_block = 0;
524     }
525   }
526 }
527 
528 //: helper for restarting blocking routines in tests
529 
530 :(before "End Primitive Recipe Declarations")
531 RESTART,
532 :(before "End Primitive Recipe Numbers")
533 put(Recipe_ordinal, "restart", RESTART);
534 :(before "End Primitive Recipe Checks")
535 case RESTART: {
536   if (SIZE(inst.ingredients) != 1) {
537     raise << maybe(get(Recipe, r).name) << "'restart' requires exactly one ingredient, but got '" << to_original_string(inst) << "'\n" << end();
538     break;
539   }
540   if (!is_mu_number(inst.ingredients.at(0))) {
541     raise << maybe(get(Recipe, r).name) << "first ingredient of 'restart' should be a routine id generated by 'start-running', but got '" << inst.ingredients.at(0).original_string << "'\n" << end();
542     break;
543   }
544   break;
545 }
546 :(before "End Primitive Recipe Implementations")
547 case RESTART: {
548   int id = ingredients.at(0).at(0);
549   for (int i = 0;  i < SIZE(Routines);  ++i) {
550     if (Routines.at(i)->id == id) {
551       if (Routines.at(i)->state == WAITING)
552         Routines.at(i)->state = RUNNING;
553       Routines.at(i)->blocked = false;
554       break;
555     }
556   }
557   break;
558 }
559 
560 :(scenario cannot_restart_completed_routine)
561 % Scheduling_interval = 1;
562 def main [
563   local-scope
564   r:num/routine-id <- start-running f
565   x:num <- copy 0  # wait for f to be scheduled
566   # r is COMPLETED by this point
567   restart r  # should have no effect
568   x:num <- copy 0  # give f time to be scheduled (though it shouldn't be)
569 ]
570 def f [
571   1:num/raw <- copy 1
572 ]
573 # shouldn't crash
574 
575 :(scenario restart_blocked_routine)
576 % Scheduling_interval = 1;
577 def main [
578   local-scope
579   r:num/routine-id <- start-running f
580   wait-for-routine-to-block r  # get past the block in f below
581   restart r
582   wait-for-routine-to-block r  # should run f to completion
583 ]
584 # function with one block
585 def f [
586   current-routine-is-blocked
587   # 8 instructions of padding, many more than 'main' above
588   1:num <- add 1:num, 1
589   1:num <- add 1:num, 1
590   1:num <- add 1:num, 1
591   1:num <- add 1:num, 1
592   1:num <- add 1:num, 1
593   1:num <- add 1:num, 1
594   1:num <- add 1:num, 1
595   1:num <- add 1:num, 1
596   1:num <- add 1:num, 1
597 ]
598 # make sure all of f ran
599 +mem: storing 8 in location 1