summary refs log tree commit diff stats
path: root/doc
diff options
context:
space:
mode:
authorhut <hut@lavabit.com>2010-12-22 02:16:34 +0100
committerhut <hut@lavabit.com>2010-12-22 02:16:34 +0100
commitd3ec909839a1b110232d932d0d01a2ed032fae80 (patch)
treef597f9a4e87cb16810504dc1e6b5ad29cc0822be /doc
parentcc69d0d8867b02ea8c9fa96a58e46a2ce31b24ce (diff)
downloadranger-d3ec909839a1b110232d932d0d01a2ed032fae80.tar.gz
core.actions: Fixed colors in help
Diffstat (limited to 'doc')
0 files changed, 0 insertions, 0 deletions
ref='003trace.cc.html#L174'>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 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 '" << to_original_string(inst) << "'\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("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 '" << to_original_string(inst) << "'\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 '" << to_original_string(inst) << "'\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 '" << to_original_string(inst) << "'\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("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 '" << to_original_string(inst) << "'\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