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