1 //: Run a second routine concurrently using 'start-running', without any
  2 //: guarantees on how the operations in each are interleaved with each other.
  3 
  4 :(scenario scheduler)
  5 def f1 [
  6   start-running f2
  7   # wait for f2 to run
  8   {
  9     jump-unless 1:num, -1
 10   }
 11 ]
 12 def f2 [
 13   1:num <- copy 1
 14 ]
 15 +schedule: f1
 16 +schedule: f2
 17 
 18 //: first, add a deadline to run(routine)
 19 :(before "End Globals")
 20 int Scheduling_interval = 500;
 21 :(before "End routine Fields")
 22 int instructions_run_this_scheduling_slice;
 23 :(before "End routine Constructor")
 24 instructions_run_this_scheduling_slice = 0;
 25 :(after "Running One Instruction")
 26  ++Current_routine->instructions_run_this_scheduling_slice;
 27 :(replace{} "bool should_continue_running(const routine* current_routine)")
 28 bool should_continue_running(const routine* current_routine) {
 29   assert(current_routine == Current_routine);  // argument passed in just to make caller readable above
 30   return Current_routine->state == RUNNING
 31       && Current_routine->instructions_run_this_scheduling_slice < Scheduling_interval;
 32 }
 33 :(after "stop_running_current_routine:")
 34 // Reset instructions_run_this_scheduling_slice
 35 Current_routine->instructions_run_this_scheduling_slice = 0;
 36 
 37 //: now the rest of the scheduler is clean
 38 
 39 :(before "struct routine")
 40 enum routine_state {
 41   RUNNING,
 42   COMPLETED,
 43   // End routine States
 44 };
 45 :(before "End routine Fields")
 46 enum routine_state state;
 47 :(before "End routine Constructor")
 48 state = RUNNING;
 49 
 50 :(before "End Globals")
 51 vector<routine*> Routines;
 52 int Current_routine_index = 0;
 53 :(before "End Reset")
 54 Scheduling_interval = 500;
 55 for (int i = 0;  i < SIZE(Routines);  ++i)
 56   delete Routines.at(i);
 57 Routines.clear();
 58 Current_routine = NULL;
 59 :(replace{} "void run(const recipe_ordinal r)")
 60 void run(const recipe_ordinal r) {
 61   run(new routine(r));
 62 }
 63 
 64 :(code)
 65 void run(routine* rr) {
 66   Routines.push_back(rr);
 67   Current_routine_index = 0, Current_routine = Routines.at(0);
 68   while (!all_routines_done()) {
 69     skip_to_next_routine();
 70     assert(Current_routine);
 71     assert(Current_routine->state == RUNNING);
 72     trace(9990, "schedule") << current_routine_label() << end();
 73     run_current_routine();
 74     // Scheduler State Transitions
 75     if (Current_routine->completed())
 76       Current_routine->state = COMPLETED;
 77     // End Scheduler State Transitions
 78 
 79     // Scheduler Cleanup
 80     // End Scheduler Cleanup
 81   }
 82   // End Run Routine
 83 }
 84 
 85 bool all_routines_done() {
 86   for (int i = 0;  i < SIZE(Routines);  ++i) {
 87     if (Routines.at(i)->state == RUNNING)
 88       return false;
 89   }
 90   return true;
 91 }
 92 
 93 // skip Current_routine_index past non-RUNNING routines
 94 void skip_to_next_routine() {
 95   assert(!Routines.empty());
 96   assert(Current_routine_index < SIZE(Routines));
 97   for (int i = (Current_routine_index+1)%SIZE(Routines);  i != Current_routine_index;  i = (i+1)%SIZE(Routines)) {
 98     if (Routines.at(i)->state == RUNNING) {
 99       Current_routine_index = i;
100       Current_routine = Routines.at(i);
101       return;
102     }
103   }
104 }
105 
106 string current_routine_label() {
107   return routine_label(Current_routine);
108 }
109 
110 string routine_label(routine* r) {
111   ostringstream result;
112   const call_stack& calls = r->calls;
113   for (call_stack::const_iterator p = calls.begin();  p != calls.end();  ++p) {
114     if (p != calls.begin()) result << '/';
115     result << get(Recipe, p->running_recipe).name;
116   }
117   return result.str();
118 }
119 
120 //: special case for the very first routine
121 :(replace{} "void run_main(int argc, char* argv[])")
122 void run_main(int argc, char* argv[]) {
123   recipe_ordinal r = get(Recipe_ordinal, "main");
124   assert(r);
125   routine* main_routine = new routine(r);
126   // pass in commandline args as ingredients to main
127   // todo: test this
128   Current_routine = main_routine;
129   for (int i = 1;  i < argc;  ++i) {
130     vector<double> arg;
131     arg.push_back(new_mu_text(argv[i]));
132     assert(get(Memory, arg.back()) == 0);
133     current_call().ingredient_atoms.push_back(arg);
134   }
135   run(main_routine);
136 }
137 
138 //:: To schedule new routines to run, call 'start-running'.
139 
140 //: 'start-running' will return a unique id for the routine that was created.
141 //: routine id is a number, but don't do any arithmetic on it
142 :(before "End routine Fields")
143 int id;
144 :(before "End Globals")
145 int Next_routine_id = 1;
146 :(before "End Reset")
147 Next_routine_id = 1;
148 :(before "End routine Constructor")
149 id = Next_routine_id;
150 ++Next_routine_id;
151 
152 //: routines save the routine that spawned them
153 :(before "End routine Fields")
154 // todo: really should be routine_id, but that's less efficient.
155 int parent_index;  // only < 0 if there's no parent_index
156 :(before "End routine Constructor")
157 parent_index = -1;
158 
159 :(before "End Primitive Recipe Declarations")
160 START_RUNNING,
161 :(before "End Primitive Recipe Numbers")
162 put(Recipe_ordinal, "start-running", START_RUNNING);
163 :(before "End Primitive Recipe Checks")
164 case START_RUNNING: {
165   if (inst.ingredients.empty()) {
166     raise << maybe(get(Recipe, r).name) << "'start-running' requires at least one ingredient: the recipe to start running\n" << end();
167     break;
168   }
169   if (!is_mu_recipe(inst.ingredients.at(0))) {
170     raise << maybe(get(Recipe, r).name) << "first ingredient of 'start-running' should be a recipe, but got '" << to_string(inst.ingredients.at(0)) << "'\n" << end();
171     break;
172   }
173   break;
174 }
175 :(before "End Primitive Recipe Implementations")
176 case START_RUNNING: {
177   routine* new_routine = new routine(ingredients.at(0).at(0));
178   new_routine->parent_index = Current_routine_index;
179   // populate ingredients
180   for (int i = /*skip callee*/1;  i < SIZE(current_instruction().ingredients);  ++i) {
181     new_routine->calls.front().ingredient_atoms.push_back(ingredients.at(i));
182     reagent/*copy*/ ingredient = current_instruction().ingredients.at(i);
183     new_routine->calls.front().ingredients.push_back(ingredient);
184     // End Populate start-running Ingredient
185   }
186   Routines.push_back(new_routine);
187   products.resize(1);
188   products.at(0).push_back(new_routine->id);
189   break;
190 }
191 
192 :(scenario scheduler_runs_single_routine)
193 % Scheduling_interval = 1;
194 def f1 [
195   1:num <- copy 0
196   2:num <- copy 0
197 ]
198 +schedule: f1
199 +run: {1: "number"} <- copy {0: "literal"}
200 +schedule: f1
201 +run: {2: "number"} <- copy {0: "literal"}
202 
203 :(scenario scheduler_interleaves_routines)
204 % Scheduling_interval = 1;
205 def f1 [
206   start-running f2
207   1:num <- copy 0
208   2:num <- copy 0
209 ]
210 def f2 [
211   3:num <- copy 0
212   4:num <- copy 0
213 ]
214 +schedule: f1
215 +run: start-running {f2: "recipe-literal"}
216 +schedule: f2
217 +run: {3: "number"} <- copy {0: "literal"}
218 +schedule: f1
219 +run: {1: "number"} <- copy {0: "literal"}
220 +schedule: f2
221 +run: {4: "number"} <- copy {0: "literal"}
222 +schedule: f1
223 +run: {2: "number"} <- copy {0: "literal"}
224 
225 :(scenario start_running_takes_ingredients)
226 def f1 [
227   start-running f2, 3
228   # wait for f2 to run
229   {
230     jump-unless 1:num, -1
231   }
232 ]
233 def f2 [
234   1:num <- next-ingredient
235   2:num <- add 1:num, 1
236 ]
237 +mem: storing 4 in location 2
238 
239 //: type-checking for 'start-running'
240 
241 :(scenario start_running_checks_types)
242 % Hide_errors = true;
243 def f1 [
244   start-running f2, 3
245 ]
246 def f2 n:&:num [
247 ]
248 +error: f1: ingredient 0 has the wrong type at 'start-running f2, 3'
249 
250 // 'start-running' only uses the ingredients of the callee, not its products
251 :(before "End is_indirect_call_with_ingredients Special-cases")
252 if (r == START_RUNNING) return true;
253 
254 //: back to testing 'start-running'
255 
256 :(scenario start_running_returns_routine_id)
257 def f1 [
258   1:num <- start-running f2
259 ]
260 def f2 [
261   12:num <- copy 44
262 ]
263 +mem: storing 2 in location 1
264 
265 //: this scenario will require some careful setup in escaped C++
266 //: (straining our tangle capabilities to near-breaking point)
267 :(scenario scheduler_skips_completed_routines)
268 % recipe_ordinal f1 = load("recipe f1 [\n1:num <- copy 0\n]\n").front();
269 % recipe_ordinal f2 = load("recipe f2 [\n2:num <- copy 0\n]\n").front();
270 % Routines.push_back(new routine(f1));  // f1 meant to run
271 % Routines.push_back(new routine(f2));
272 % Routines.back()->state = COMPLETED;  // f2 not meant to run
273 # must have at least one routine without escaping
274 def f3 [
275   3:num <- copy 0
276 ]
277 # by interleaving '+' lines with '-' lines, we allow f1 and f3 to run in any order
278 +schedule: f1
279 +mem: storing 0 in location 1
280 -schedule: f2
281 -mem: storing 0 in location 2
282 +schedule: f3
283 +mem: storing 0 in location 3
284 
285 :(scenario scheduler_starts_at_middle_of_routines)
286 % Routines.push_back(new routine(COPY));
287 % Routines.back()->state = COMPLETED;
288 def f1 [
289   1:num <- copy 0
290   2:num <- copy 0
291 ]
292 +schedule: f1
293 -run: idle
294 
295 //:: Errors in a routine cause it to terminate.
296 
297 :(scenario scheduler_terminates_routines_after_errors)
298 % Hide_errors = true;
299 % Scheduling_interval = 2;
300 def f1 [
301   start-running f2
302   1:num <- copy 0
303   2:num <- copy 0
304 ]
305 def f2 [
306   # divide by 0 twice
307   3:num <- divide-with-remainder 4, 0
308   4:num <- divide-with-remainder 4, 0
309 ]
310 # f2 should stop after first divide by 0
311 +error: f2: divide by zero in '3:num <- divide-with-remainder 4, 0'
312 -error: f2: divide by zero in '4:num <- divide-with-remainder 4, 0'
313 
314 :(after "operator<<(ostream& os, end /*unused*/)")
315   if (Trace_stream && Trace_stream->curr_label == "error" && Current_routine) {
316     Current_routine->state = COMPLETED;
317   }
318 
319 //:: Routines are marked completed when their parent completes.
320 
321 :(scenario scheduler_kills_orphans)
322 def main [
323   start-running f1
324   # f1 never actually runs because its parent completes without waiting for it
325 ]
326 def f1 [
327   1:num <- copy 0
328 ]
329 -schedule: f1
330 
331 :(before "End Scheduler Cleanup")
332 for (int i = 0;  i < SIZE(Routines);  ++i) {
333   if (Routines.at(i)->state == COMPLETED) continue;
334   if (Routines.at(i)->parent_index < 0) continue;  // root thread
335   // structured concurrency: http://250bpm.com/blog:71
336   if (has_completed_parent(i)) {
337     Routines.at(i)->state = COMPLETED;
338   }
339 }
340 
341 :(code)
342 bool has_completed_parent(int routine_index) {
343   for (int j = routine_index;  j >= 0;  j = Routines.at(j)->parent_index) {
344     if (Routines.at(j)->state == COMPLETED)
345       return true;
346   }
347   return false;
348 }
349 
350 //:: 'routine-state' can tell if a given routine id is running
351 
352 :(scenario routine_state_test)
353 % Scheduling_interval = 2;
354 def f1 [
355   1:num/child-id <- start-running f2
356   12:num <- copy 0  # race condition since we don't care about location 12
357   # thanks to Scheduling_interval, f2's one instruction runs in between here and completes
358   2:num/state <- routine-state 1:num/child-id
359 ]
360 def f2 [
361   12:num <- copy 0
362   # trying to run a second instruction marks routine as completed
363 ]
364 # recipe f2 should be in state COMPLETED
365 +mem: storing 1 in location 2
366 
367 :(before "End Primitive Recipe Declarations")
368 ROUTINE_STATE,
369 :(before "End Primitive Recipe Numbers")
370 put(Recipe_ordinal, "routine-state", ROUTINE_STATE);
371 :(before "End Primitive Recipe Checks")
372 case ROUTINE_STATE: {
373   if (SIZE(inst.ingredients) != 1) {
374     raise << maybe(get(Recipe, r).name) << "'routine-state' requires exactly one ingredient, but got '" << to_original_string(inst) << "'\n" << end();
375     break;
376   }
377   if (!is_mu_number(inst.ingredients.at(0))) {
378     raise << maybe(get(Recipe, r).name) << "first ingredient of 'routine-state' should be a routine id generated by 'start-running', but got '" << inst.ingredients.at(0).original_string << "'\n" << end();
379     break;
380   }
381   break;
382 }
383 :(before "End Primitive Recipe Implementations")
384 case ROUTINE_STATE: {
385   int id = ingredients.at(0).at(0);
386   int result = -1;
387   for (int i = 0;  i < SIZE(Routines);  ++i) {
388     if (Routines.at(i)->id == id) {
389       result = Routines.at(i)->state;
390       break;
391     }
392   }
393   products.resize(1);
394   products.at(0).push_back(result);
395   break;
396 }
397 
398 //:: miscellaneous helpers
399 
400 :(before "End Primitive Recipe Declarations")
401 STOP,
402 :(before "End Primitive Recipe Numbers")
403 put(Recipe_ordinal, "stop", STOP);
404 :(before "End Primitive Recipe Checks")
405 case STOP: {
406   if (SIZE(inst.ingredients) != 1) {
407     raise << maybe(get(Recipe, r).name) << "'stop' requires exactly one ingredient, but got '" << to_original_string(inst) << "'\n" << end();
408     break;
409   }
410   if (!is_mu_number(inst.ingredients.at(0))) {
411     raise << maybe(get(Recipe, r).name) << "first ingredient of 'stop' should be a routine id generated by 'start-running', but got '" << inst.ingredients.at(0).original_string << "'\n" << end();
412     break;
413   }
414   break;
415 }
416 :(before "End Primitive Recipe Implementations")
417 case STOP: {
418   int id = ingredients.at(0).at(0);
419   for (int i = 0;  i < SIZE(Routines);  ++i) {
420     if (Routines.at(i)->id == id) {
421       Routines.at(i)->state = COMPLETED;
422       break;
423     }
424   }
425   break;
426 }
427 
428 :(before "End Primitive Recipe Declarations")
429 _DUMP_ROUTINES,
430 :(before "End Primitive Recipe Numbers")
431 put(Recipe_ordinal, "$dump-routines", _DUMP_ROUTINES);
432 :(before "End Primitive Recipe Checks")
433 case _DUMP_ROUTINES: {
434   break;
435 }
436 :(before "End Primitive Recipe Implementations")
437 case _DUMP_ROUTINES: {
438   for (int i = 0;  i < SIZE(Routines);  ++i) {
439     cerr << i << ": " << Routines.at(i)->id << ' ' << Routines.at(i)->state << ' ' << Routines.at(i)->parent_index << '\n';
440   }
441   break;
442 }
443 
444 //: support for stopping routines after some number of cycles
445 
446 :(scenario routine_discontinues_past_limit)
447 % Scheduling_interval = 2;
448 def f1 [
449   1:num/child-id <- start-running f2
450   limit-time 1:num/child-id, 10
451   # padding loop just to make sure f2 has time to completed
452   2:num <- copy 20
453   2:num <- subtract 2:num, 1
454   jump-if 2:num, -2:offset
455 ]
456 def f2 [
457   jump -1:offset  # run forever
458   $print [should never get here], 10/newline
459 ]
460 # f2 terminates
461 +schedule: discontinuing routine 2
462 
463 :(before "End routine States")
464 DISCONTINUED,
465 :(before "End Scheduler State Transitions")
466 if (Current_routine->limit >= 0) {
467   if (Current_routine->limit <= Scheduling_interval) {
468     trace("schedule") << "discontinuing routine " << Current_routine->id << end();
469     Current_routine->state = DISCONTINUED;
470     Current_routine->limit = 0;
471   }
472   else {
473     Current_routine->limit -= Scheduling_interval;
474   }
475 }
476 
477 :(before "End Test Teardown")
478 if (Passed && any_routines_with_error())
479   raise << "some routines died with errors\n" << end();
480 :(before "End Mu Test Teardown")
481 if (Passed && any_routines_with_error())
482   raise << Current_scenario->name << ": some routines died with errors\n" << end();
483 
484 :(code)
485 bool any_routines_with_error() {
486   for (int i = 0;  i < SIZE(Routines);  ++i) {
487     if (Routines.at(i)->state == DISCONTINUED)
488       return true;
489   }
490   return false;
491 }
492 
493 :(before "End routine Fields")
494 int limit;
495 :(before "End routine Constructor")
496 limit = -1;  /* no limit */
497 
498 :(before "End Primitive Recipe Declarations")
499 LIMIT_TIME,
500 :(before "End Primitive Recipe Numbers")
501 put(Recipe_ordinal, "limit-time", LIMIT_TIME);
502 :(before "End Primitive Recipe Checks")
503 case LIMIT_TIME: {
504   if (SIZE(inst.ingredients) != 2) {
505     raise << maybe(get(Recipe, r).name) << "'limit-time' requires exactly two ingredient, but got '" << to_original_string(inst) << "'\n" << end();
506     break;
507   }
508   if (!is_mu_number(inst.ingredients.at(0))) {
509     raise << maybe(get(Recipe, r).name) << "first ingredient of 'limit-time' should be a routine id generated by 'start-running', but got '" << inst.ingredients.at(0).original_string << "'\n" << end();
510     break;
511   }
512   if (!is_mu_number(inst.ingredients.at(1))) {
513     raise << maybe(get(Recipe, r).name) << "second ingredient of 'limit-time' should be a number (of instructions to run for), but got '" << inst.ingredients.at(1).original_string << "'\n" << end();
514     break;
515   }
516   break;
517 }
518 :(before "End Primitive Recipe Implementations")
519 case LIMIT_TIME: {
520   int id = ingredients.at(0).at(0);
521   for (int i = 0;  i < SIZE(Routines);  ++i) {
522     if (Routines.at(i)->id == id) {
523       Routines.at(i)->limit = ingredients.at(1).at(0);
524       break;
525     }
526   }
527   break;
528 }
529 
530 :(before "End routine Fields")
531 int instructions_run;
532 :(before "End routine Constructor")
533 instructions_run = 0;
534 :(before "Reset instructions_run_this_scheduling_slice")
535 Current_routine->instructions_run += Current_routine->instructions_run_this_scheduling_slice;
536 :(before "End Primitive Recipe Declarations")
537 NUMBER_OF_INSTRUCTIONS,
538 :(before "End Primitive Recipe Numbers")
539 put(Recipe_ordinal, "number-of-instructions", NUMBER_OF_INSTRUCTIONS);
540 :(before "End Primitive Recipe Checks")
541 case NUMBER_OF_INSTRUCTIONS: {
542   if (SIZE(inst.ingredients) != 1) {
543     raise << maybe(get(Recipe, r).name) << "'number-of-instructions' requires exactly one ingredient, but got '" << to_original_string(inst) << "'\n" << end();
544     break;
545   }
546   if (!is_mu_number(inst.ingredients.at(0))) {
547     raise << maybe(get(Recipe, r).name) << "first ingredient of 'number-of-instructions' should be a routine id generated by 'start-running', but got '" << inst.ingredients.at(0).original_string << "'\n" << end();
548     break;
549   }
550   break;
551 }
552 :(before "End Primitive Recipe Implementations")
553 case NUMBER_OF_INSTRUCTIONS: {
554   int id = ingredients.at(0).at(0);
555   int result = -1;
556   for (int i = 0;  i < SIZE(Routines);  ++i) {
557     if (Routines.at(i)->id == id) {
558       result = Routines.at(i)->instructions_run;
559       break;
560     }
561   }
562   products.resize(1);
563   products.at(0).push_back(result);
564   break;
565 }
566 
567 :(scenario number_of_instructions)
568 def f1 [
569   10:num/child-id <- start-running f2
570   {
571     loop-unless 20:num
572   }
573   11:num <- number-of-instructions 10:num
574 ]
575 def f2 [
576   # 2 instructions worth of work
577   1:num <- copy 34
578   20:num <- copy 1
579 ]
580 # f2 runs an extra instruction for the implicit return added by the
581 # fill_in_return_ingredients transform
582 +mem: storing 3 in location 11
583 
584 :(scenario number_of_instructions_across_multiple_scheduling_intervals)
585 % Scheduling_interval = 1;
586 def f1 [
587   10:num/child-id <- start-running f2
588   {
589     loop-unless 20:num
590   }
591   11:num <- number-of-instructions 10:num
592 ]
593 def f2 [
594   # 4 instructions worth of work
595   1:num <- copy 34
596   2:num <- copy 1
597   2:num <- copy 3
598   20:num <- copy 1
599 ]
600 # f2 runs an extra instruction for the implicit return added by the
601 # fill_in_return_ingredients transform
602 +mem: storing 5 in location 11
603 
604 //:: make sure that each routine gets a different alloc to start
605 
606 :(scenario new_concurrent)
607 def f1 [
608   start-running f2
609   1:&:num/raw <- new number:type
610   # wait for f2 to complete
611   {
612     loop-unless 4:num/raw
613   }
614 ]
615 def f2 [
616   2:&:num/raw <- new number:type
617   # hack: assumes scheduler implementation
618   3:bool/raw <- equal 1:&:num/raw, 2:&:num/raw
619   # signal f2 complete
620   4:num/raw <- copy 1
621 ]
622 +mem: storing 0 in location 3