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