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     reagent/*copy*/ ingredient = current_instruction().ingredients.at(i);
182     new_routine->calls.front().ingredients.push_back(ingredient);
183     vector<double> new_ingredient_atoms = deep_copy(ingredient);
184     new_routine->calls.front().ingredient_atoms.push_back(new_ingredient_atoms);
185     // End Populate start-running Ingredient
186   }
187   Routines.push_back(new_routine);
188   products.resize(1);
189   products.at(0).push_back(new_routine->id);
190   break;
191 }
192 
193 :(scenario scheduler_runs_single_routine)
194 % Scheduling_interval = 1;
195 def f1 [
196   1:num <- copy 0
197   2:num <- copy 0
198 ]
199 +schedule: f1
200 +run: {1: "number"} <- copy {0: "literal"}
201 +schedule: f1
202 +run: {2: "number"} <- copy {0: "literal"}
203 
204 :(scenario scheduler_interleaves_routines)
205 % Scheduling_interval = 1;
206 def f1 [
207   start-running f2
208   1:num <- copy 0
209   2:num <- copy 0
210 ]
211 def f2 [
212   3:num <- copy 0
213   4:num <- copy 0
214 ]
215 +schedule: f1
216 +run: start-running {f2: "recipe-literal"}
217 +schedule: f2
218 +run: {3: "number"} <- copy {0: "literal"}
219 +schedule: f1
220 +run: {1: "number"} <- copy {0: "literal"}
221 +schedule: f2
222 +run: {4: "number"} <- copy {0: "literal"}
223 +schedule: f1
224 +run: {2: "number"} <- copy {0: "literal"}
225 
226 :(scenario start_running_takes_ingredients)
227 def f1 [
228   start-running f2, 3
229   # wait for f2 to run
230   {
231     jump-unless 1:num, -1
232   }
233 ]
234 def f2 [
235   1:num <- next-ingredient
236   2:num <- add 1:num, 1
237 ]
238 +mem: storing 4 in location 2
239 
240 //: type-checking for 'start-running'
241 
242 :(scenario start_running_checks_types)
243 % Hide_errors = true;
244 def f1 [
245   start-running f2, 3
246 ]
247 def f2 n:&:num [
248 ]
249 +error: f1: ingredient 0 has the wrong type at 'start-running f2, 3'
250 
251 // 'start-running' only uses the ingredients of the callee, not its products
252 :(before "End is_indirect_call_with_ingredients Special-cases")
253 if (r == START_RUNNING) return true;
254 
255 //: back to testing 'start-running'
256 
257 :(scenario start_running_returns_routine_id)
258 def f1 [
259   1:num <- start-running f2
260 ]
261 def f2 [
262   12:num <- copy 44
263 ]
264 +mem: storing 2 in location 1
265 
266 //: this scenario will require some careful setup in escaped C++
267 //: (straining our tangle capabilities to near-breaking point)
268 :(scenario scheduler_skips_completed_routines)
269 % recipe_ordinal f1 = load("recipe f1 [\n1:num <- copy 0\n]\n").front();
270 % recipe_ordinal f2 = load("recipe f2 [\n2:num <- copy 0\n]\n").front();
271 % Routines.push_back(new routine(f1));  // f1 meant to run
272 % Routines.push_back(new routine(f2));
273 % Routines.back()->state = COMPLETED;  // f2 not meant to run
274 # must have at least one routine without escaping
275 def f3 [
276   3:num <- copy 0
277 ]
278 # by interleaving '+' lines with '-' lines, we allow f1 and f3 to run in any order
279 +schedule: f1
280 +mem: storing 0 in location 1
281 -schedule: f2
282 -mem: storing 0 in location 2
283 +schedule: f3
284 +mem: storing 0 in location 3
285 
286 :(scenario scheduler_starts_at_middle_of_routines)
287 % Routines.push_back(new routine(COPY));
288 % Routines.back()->state = COMPLETED;
289 def f1 [
290   1:num <- copy 0
291   2:num <- copy 0
292 ]
293 +schedule: f1
294 -run: idle
295 
296 //:: Errors in a routine cause it to terminate.
297 
298 :(scenario scheduler_terminates_routines_after_errors)
299 % Hide_errors = true;
300 % Scheduling_interval = 2;
301 def f1 [
302   start-running f2
303   1:num <- copy 0
304   2:num <- copy 0
305 ]
306 def f2 [
307   # divide by 0 twice
308   3:num <- divide-with-remainder 4, 0
309   4:num <- divide-with-remainder 4, 0
310 ]
311 # f2 should stop after first divide by 0
312 +error: f2: divide by zero in '3:num <- divide-with-remainder 4, 0'
313 -error: f2: divide by zero in '4:num <- divide-with-remainder 4, 0'
314 
315 :(after "operator<<(ostream& os, unused end)")
316   if (Trace_stream && Trace_stream->curr_label == "error" && Current_routine) {
317     Current_routine->state = COMPLETED;
318   }
319 
320 //:: Routines are marked completed when their parent completes.
321 
322 :(scenario scheduler_kills_orphans)
323 def main [
324   start-running f1
325   # f1 never actually runs because its parent completes without waiting for it
326 ]
327 def f1 [
328   1:num <- copy 0
329 ]
330 -schedule: f1
331 
332 :(before "End Scheduler Cleanup")
333 for (int i = 0;  i < SIZE(Routines);  ++i) {
334   if (Routines.at(i)->state == COMPLETED) continue;
335   if (Routines.at(i)->parent_index < 0) continue;  // root thread
336   // structured concurrency: http://250bpm.com/blog:71
337   if (has_completed_parent(i)) {
338     Routines.at(i)->state = COMPLETED;
339   }
340 }
341 
342 :(code)
343 bool has_completed_parent(int routine_index) {
344   for (int j = routine_index;  j >= 0;  j = Routines.at(j)->parent_index) {
345     if (Routines.at(j)->state == COMPLETED)
346       return true;
347   }
348   return false;
349 }
350 
351 //:: 'routine-state' can tell if a given routine id is running
352 
353 :(scenario routine_state_test)
354 % Scheduling_interval = 2;
355 def f1 [
356   1:num/child-id <- start-running f2
357   12:num <- copy 0  # race condition since we don't care about location 12
358   # thanks to Scheduling_interval, f2's one instruction runs in between here and completes
359   2:num/state <- routine-state 1:num/child-id
360 ]
361 def f2 [
362   12:num <- copy 0
363   # trying to run a second instruction marks routine as completed
364 ]
365 # recipe f2 should be in state COMPLETED
366 +mem: storing 1 in location 2
367 
368 :(before "End Primitive Recipe Declarations")
369 ROUTINE_STATE,
370 :(before "End Primitive Recipe Numbers")
371 put(Recipe_ordinal, "routine-state", ROUTINE_STATE);
372 :(before "End Primitive Recipe Checks")
373 case ROUTINE_STATE: {
374   if (SIZE(inst.ingredients) != 1) {
375     raise << maybe(get(Recipe, r).name) << "'routine-state' requires exactly one ingredient, but got '" << to_original_string(inst) << "'\n" << end();
376     break;
377   }
378   if (!is_mu_number(inst.ingredients.at(0))) {
379     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();
380     break;
381   }
382   break;
383 }
384 :(before "End Primitive Recipe Implementations")
385 case ROUTINE_STATE: {
386   int id = ingredients.at(0).at(0);
387   int result = -1;
388   for (int i = 0;  i < SIZE(Routines);  ++i) {
389     if (Routines.at(i)->id == id) {
390       result = Routines.at(i)->state;
391       break;
392     }
393   }
394   products.resize(1);
395   products.at(0).push_back(result);
396   break;
397 }
398 
399 //:: miscellaneous helpers
400 
401 :(before "End Primitive Recipe Declarations")
402 STOP,
403 :(before "End Primitive Recipe Numbers")
404 put(Recipe_ordinal, "stop", STOP);
405 :(before "End Primitive Recipe Checks")
406 case STOP: {
407   if (SIZE(inst.ingredients) != 1) {
408     raise << maybe(get(Recipe, r).name) << "'stop' requires exactly one ingredient, but got '" << to_original_string(inst) << "'\n" << end();
409     break;
410   }
411   if (!is_mu_number(inst.ingredients.at(0))) {
412     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();
413     break;
414   }
415   break;
416 }
417 :(before "End Primitive Recipe Implementations")
418 case STOP: {
419   int id = ingredients.at(0).at(0);
420   for (int i = 0;  i < SIZE(Routines);  ++i) {
421     if (Routines.at(i)->id == id) {
422       Routines.at(i)->state = COMPLETED;
423       break;
424     }
425   }
426   break;
427 }
428 
429 :(before "End Primitive Recipe Declarations")
430 _DUMP_ROUTINES,
431 :(before "End Primitive Recipe Numbers")
432 put(Recipe_ordinal, "$dump-routines", _DUMP_ROUTINES);
433 :(before "End Primitive Recipe Checks")
434 case _DUMP_ROUTINES: {
435   break;
436 }
437 :(before "End Primitive Recipe Implementations")
438 case _DUMP_ROUTINES: {
439   for (int i = 0;  i < SIZE(Routines);  ++i) {
440     cerr << i << ": " << Routines.at(i)->id << ' ' << Routines.at(i)->state << ' ' << Routines.at(i)->parent_index << '\n';
441   }
442   break;
443 }
444 
445 //: support for stopping routines after some number of cycles
446 
447 :(scenario routine_discontinues_past_limit)
448 % Scheduling_interval = 2;
449 def f1 [
450   1:num/child-id <- start-running f2
451   limit-time 1:num/child-id, 10
452   # padding loop just to make sure f2 has time to completed
453   2:num <- copy 20
454   2:num <- subtract 2:num, 1
455   jump-if 2:num, -2:offset
456 ]
457 def f2 [
458   jump -1:offset  # run forever
459   $print [should never get here], 10/newline
460 ]
461 # f2 terminates
462 +schedule: discontinuing routine 2
463 
464 :(before "End routine States")
465 DISCONTINUED,
466 :(before "End Scheduler State Transitions")
467 if (Current_routine->limit >= 0) {
468   if (Current_routine->limit <= Scheduling_interval) {
469     trace("schedule") << "discontinuing routine " << Current_routine->id << end();
470     Current_routine->state = DISCONTINUED;
471     Current_routine->limit = 0;
472   }
473   else {
474     Current_routine->limit -= Scheduling_interval;
475   }
476 }
477 
478 :(before "End Test Teardown")
479 if (Passed && any_routines_with_error())
480   raise << "some routines died with errors\n" << end();
481 :(before "End Mu Test Teardown")
482 if (Passed && any_routines_with_error())
483   raise << Current_scenario->name << ": some routines died with errors\n" << end();
484 
485 :(code)
486 bool any_routines_with_error() {
487   for (int i = 0;  i < SIZE(Routines);  ++i) {
488     if (Routines.at(i)->state == DISCONTINUED)
489       return true;
490   }
491   return false;
492 }
493 
494 :(before "End routine Fields")
495 int limit;
496 :(before "End routine Constructor")
497 limit = -1;  /* no limit */
498 
499 :(before "End Primitive Recipe Declarations")
500 LIMIT_TIME,
501 :(before "End Primitive Recipe Numbers")
502 put(Recipe_ordinal, "limit-time", LIMIT_TIME);
503 :(before "End Primitive Recipe Checks")
504 case LIMIT_TIME: {
505   if (SIZE(inst.ingredients) != 2) {
506     raise << maybe(get(Recipe, r).name) << "'limit-time' requires exactly two ingredient, but got '" << to_original_string(inst) << "'\n" << end();
507     break;
508   }
509   if (!is_mu_number(inst.ingredients.at(0))) {
510     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();
511     break;
512   }
513   if (!is_mu_number(inst.ingredients.at(1))) {
514     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();
515     break;
516   }
517   break;
518 }
519 :(before "End Primitive Recipe Implementations")
520 case LIMIT_TIME: {
521   int id = ingredients.at(0).at(0);
522   for (int i = 0;  i < SIZE(Routines);  ++i) {
523     if (Routines.at(i)->id == id) {
524       Routines.at(i)->limit = ingredients.at(1).at(0);
525       break;
526     }
527   }
528   break;
529 }
530 
531 :(before "End routine Fields")
532 int instructions_run;
533 :(before "End routine Constructor")
534 instructions_run = 0;
535 :(before "Reset instructions_run_this_scheduling_slice")
536 Current_routine->instructions_run += Current_routine->instructions_run_this_scheduling_slice;
537 :(before "End Primitive Recipe Declarations")
538 NUMBER_OF_INSTRUCTIONS,
539 :(before "End Primitive Recipe Numbers")
540 put(Recipe_ordinal, "number-of-instructions", NUMBER_OF_INSTRUCTIONS);
541 :(before "End Primitive Recipe Checks")
542 case NUMBER_OF_INSTRUCTIONS: {
543   if (SIZE(inst.ingredients) != 1) {
544     raise << maybe(get(Recipe, r).name) << "'number-of-instructions' requires exactly one ingredient, but got '" << to_original_string(inst) << "'\n" << end();
545     break;
546   }
547   if (!is_mu_number(inst.ingredients.at(0))) {
548     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();
549     break;
550   }
551   break;
552 }
553 :(before "End Primitive Recipe Implementations")
554 case NUMBER_OF_INSTRUCTIONS: {
555   int id = ingredients.at(0).at(0);
556   int result = -1;
557   for (int i = 0;  i < SIZE(Routines);  ++i) {
558     if (Routines.at(i)->id == id) {
559       result = Routines.at(i)->instructions_run;
560       break;
561     }
562   }
563   products.resize(1);
564   products.at(0).push_back(result);
565   break;
566 }
567 
568 :(scenario number_of_instructions)
569 def f1 [
570   10:num/child-id <- start-running f2
571   {
572     loop-unless 20:num
573   }
574   11:num <- number-of-instructions 10:num
575 ]
576 def f2 [
577   # 2 instructions worth of work
578   1:num <- copy 34
579   20:num <- copy 1
580 ]
581 # f2 runs an extra instruction for the implicit return added by the
582 # fill_in_return_ingredients transform
583 +mem: storing 3 in location 11
584 
585 :(scenario number_of_instructions_across_multiple_scheduling_intervals)
586 % Scheduling_interval = 1;
587 def f1 [
588   10:num/child-id <- start-running f2
589   {
590     loop-unless 20:num
591   }
592   11:num <- number-of-instructions 10:num
593 ]
594 def f2 [
595   # 4 instructions worth of work
596   1:num <- copy 34
597   2:num <- copy 1
598   2:num <- copy 3
599   20:num <- copy 1
600 ]
601 # f2 runs an extra instruction for the implicit return added by the
602 # fill_in_return_ingredients transform
603 +mem: storing 5 in location 11
604 
605 //:: make sure that each routine gets a different alloc to start
606 
607 :(scenario new_concurrent)
608 def f1 [
609   start-running f2
610   1:&:num/raw <- new number:type
611   # wait for f2 to complete
612   {
613     loop-unless 4:num/raw
614   }
615 ]
616 def f2 [
617   2:&:num/raw <- new number:type
618   # hack: assumes scheduler implementation
619   3:bool/raw <- equal 1:&:num/raw, 2:&:num/raw
620   # signal f2 complete
621   4:num/raw <- copy 1
622 ]
623 +mem: storing 0 in location 3