Post by edorfaus in Code sharing megathread

Viewing post in Code sharing megathread

... Heh. You just led me to finding an easily reproduced crash. (Well, I can reproduce it easily anyway, and I expect you can too.)

One of my first thoughts on hearing that fact about IFJMP/JMP was not so much that it wasn't realistic (which it indeed isn't), but that it was risky. So I decided to test what I had in mind, to see what effect it would actually have. I figured it could be anything from already being handled, to locking up in an infinite loop, to crashing (which is what it turned out to be).

Up to you how to fix this (assuming you don't want to keep that crash), there are ways to do it without making these instructions take a cycle. (Though those ways are probably more complicated to implement, depending on how your code works right now - I haven't really looked at it.)

I'll also note that this crash only happens with JMP - the equivalent test case with IFJMP seems to take a cycle on each instruction in the debugger, and doesn't crash the game without the debugger either. As far as I can tell, it takes a cycle whether or not the condition matches. So, are you sure it isn't just JMP that has this behaviour?

Test steps: with the computer selected, enter the following program, compile it, compile to ROM, and start the computer. (If in debug mode, click the step button.)

JMP 0 1
JMP 2 1

Expected result: Game continues to work fine; virtual computer can be turned off to change the program, etc.. (If in debug mode, debugger continues to work.)

Actual result: Game crashes with a "Segmentation fault" message in the terminal (not in the log file).

CliffracerX6 years ago

Huh, maybe IFJMP doesn't auto-run what it jumps to after all? I'll have a look at that later.

As for the crash - that's...odd. I understand why it's crashing (function recursion and all), but I'd expect it to just lock up and stop responding, rather than have a segmentation fault. Best idea I've got would probably be to have it automatically halt and stop execution if a given clock cycle for the TC-06 takes more than a certain amount of time, or maybe if a certain function runs more than a certain number of times per tick. I'm loathe to add an op-code limiter, considering it would, well, limit possible programs, but...it might be necessary. Or I just say it's a feature, not a bug? Putting in stuff that will obviously blow up the computer should, well, blow up the computer.

I have a feeling why it crashes is that it makes temporary variables (a lot, actually) in each function, and when that function's getting run recursively, the data piles up fast, so fast the garbage collector can't catch up, and thusly, the program segfaults a moment later when it runs out of memory to put stuff in.

edorfaus6 years ago(+1)

I kind of mostly expected it to lock up as well, actually, but that's not what I got.

About blowing up the computer; in any regular computer, this kind of loop wouldn't actually blow it up - it would just make it sit there apparently doing nothing, while actually working very hard (at changing the instruction pointer).

With the semantics of immediately running the targeted instructions, I can see it being a problem for the TC-06 though - but since those semantics aren't documented, and no other computer works that way, having JMP work that way here is rather unexpected. Having it blow up the computer is thus not obvious, and would probably surprise most developers.

While my test case is indeed obvious, that's because it was constructed to be (for demonstration purposes), and was already in a context where we talked about the JMP semantics. I can easily see some player accidentally creating such a loop if they're not careful enough while changing their program - and if the game crashes, then their program is probably lost, so they can't really figure out what the problem was later, either. They're more likely to think the game just crashed on its own, not due to the program they put in.

So if you want it to blow up the computer, maybe detect it and blow up the virtual computer instead of the game itself?

(Come to think of it, these semantics might be the cause of some trouble I had with figuring out how the jump offsets work by looking in the debugger - if, after executing a JMP instruction, it shows that the next instruction to be executed is the one _after_ the one I was trying to jump to, then the most obvious explanation seems to be that the jump offset was wrong, not that the computer already executed the targeted instruction. I'm not sure if this was really it, though, because I think I've mostly been using IFJMP, not so much JMP.)

About the crash; if you're using recursion for JMP, then it's probably a stack overflow - that's a common reason for getting a segmentation fault, especially if the system uses guard pages to protect the rest of the program's memory from such overflows.

A stack overflow is not something GC can help with, not just because all of those objects are still technically reachable (it must assume the recursed-into method will return eventually), but because the call stack contains not just the pointers to those objects, but also other things like the return address, which obviously can't be removed anyway before the called method returns. (Unless you used proper tail recursion, but I don't know if .NET/Mono supports that.) So even if you didn't have any local temporary variables, an infinite recursion would still overflow the stack, though it would probably take longer to do so (as in, freeze a bit first, then crash, instead of crashing quickly).

As for how to fix it without introducing limitations, I'll suggest a solution I've used to protect similarly recursive code: keep a set of states, initially empty, and check if that set already contains the state I'm about to call from/to - if it does, then abort to avoid a loop, otherwise, add the state and do the call.

The most tricky bit is usually to figure out what that state should be, especially to maintain reasonable performance - but here I think it's actually pretty easy. As far as I can tell, none of the JMP instructions can modify any state that any of the JMP instructions depend on to figure out where they're going to jump to. (And if you hit a non-JMP instruction, which could change that state, then you're done jumping anyway.) So the only state that seems to matter is which JMP instruction you're about to execute, which is completely determined by its address, which is a simple integer. I don't expect a (rather small) set of integers to cause any performance issues.

To be specific, I think that you can keep a set of addresses, which starts out empty at the start of a clock cycle - and when you're about to execute a JMP instruction, you first check to see if its address is already in the set. If it is, then you have already executed this instruction in this clock cycle, so you're in a loop. In that case, don't actually do the jump, just return. Otherwise, you add the address to the set, and do the jump (aka recursive call).

I believe this would have the effect of making the computer seem to stop at the first instruction in the loop, since it would go around the loop and find the same instruction, and stop there. Then, the next clock cycle, it would do the same thing again, stopping at the same place.

(Note that you can't just keep the address of the first JMP of the clock cycle, since that might be jumping into a loop that it isn't itself a part of.)

With this solution, the computer would at most go through every instruction in memory once per clock cycle (if they're all a big loop), which wouldn't be good if you have a custom mode with a lot of memory, but would at least be better than an infinite recursion. If that computer has enough memory, you could still overflow the stack that way, but that's impossible to avoid with a recursive solution (without tail recursion anyway).

Of course, this is just a suggestion for your consideration. You might have better ideas. (Also, feel free to tell me to shut up if you'd prefer to figure out how to do things on your own (or at least without me butting in).)

P.S. I just remembered - the TIS-100 has an explicit "Halt and Catch Fire" instruction. IIRC it just rebooted the (virtual) computer though. I think there was an achievement for finding (and running) it.

P.P.S. I just thought of an even simpler test case. "JMP 0 0". Which sounds like the kind of thing I might put in as a placeholder, intending to look up the numbers I need to insert later. Which it would be easy to forget to actually do...

CliffracerX6 years ago

So it wouldn't blow your COMPUTER up, but your fans might fly to pieces trying to cool it down. :p

I'll include a documentation update with the next update - JMP and IFJMP should definitely have some more detailing, both on the running functions/explodey aspect, and just in general, considering they're both heavily influenced by Redcode and thusly likely to confuse folks.

I know it's not immediately related to the JMP discussion, but should I think about adding an auto-save whenever you compile a program? E.G, to [ProgramName].autosave.casm? That way if your game explodes, you're not gonna lose your code. Same for the drive, maybe do an autosave of it at regular intervals?

An in-game flame-out animation might be kinda fun - if it detects the loop, the halt light comes on and steam comes outta the box.

public List<int> runAddresses; //assume it's initialized elsewhere
public int currentCounter; //self-evident
public int[] RAM; //self-evident
void TimedUpdate() //this runs at the computer's clockrate to execute code and such
{
    //code surrounding halts and such goes here
    runAddresses.Clear();
    DoProcess();
}
void DoProcess() //this actually executes op-codes & whatnot
{
    runAddresses.Add(currentCounter);
    int data,opCode,arguments; //data is the memory data at RAM[currentCounter], and arguments is the last 28 bits of said data
    //insert all the other functions and such
    if(opCode==4) //JMP
    {
        int destAddress; //assume this is set by reading the arguments & whatnot
        if(runAddresses.Contains(destAddress))
        {
            DoFlameout();
        }
    }
}

Rough pseudocode for how to integrate the recursive loop prevention as you suggested it. Clear the list of run addresses before running op-codes, and add the current program counter to the list of run addresses at the beginning of the op-code-runner function. If the list of run addresses contains whatever JMP is supposed to be jumping to, cause a flame-out animation & halt the processor, rather than running it.

This SHOULD catch all possible recursive JMP loops that'd cause a stack overflow, without breaking things like the Blinkenlights loop. Only situation I can think of would be something with self-modifying code looping, but...that shouldn't even be an issue (since a non-JMP call will reset the list of addresses) in the current version of the game. A multithreaded two-core version of the TC-06 could encounter problems with that, if your modification was happening on the other processor, though. :/

I do appreciate the suggestions & bug reports - thank you for providing them!

(As for halting and catching fire - I think that should literally just be "run JMP 0 0 for a special surprise" or something :P)

edorfaus6 years ago(+1)

Some kind of auto-save would probably be a good idea, yes - much like for a text editor, since it includes one - and I do agree that it should not auto-save by overwriting the proper (manual) save file(s). I believe the approach you suggest should work - not sure if it's the best one, or whether it should be a game-wide auto-save file, I suppose it depends on how/when you want to detect and load it. (As in, on game start, or when a user tries to load a previous save, or when they re-enter a level with any auto-save file, or what. Also consider asking first instead of just loading, in case the auto-save itself got corrupted enough to crash the game when loaded.) Whether to auto-save the entire game state in one file, or several, probably depends on what features you want to have as well - e.g. if you want to allow save/load of disk state separately from program or level, keeping them separate (and separately restorable) is probably better, but keeping the entire auto-save in one file would probably be easier if you (maybe later) find you want to save other parts of the game state as well (e.g. which stage of a tutorial the player was at).

To be honest, I think that's the largest and in many ways most difficult part of creating something like this - deciding how exactly you want it to work, to be properly user-friendly. I don't have any real answers for that part, it's not really my field - so you should consider anything I say about it to be just suggestions for things to consider when you make your own decisions about it.

Your pseudocode is pretty much it, yes - or close enough anyway. (Assuming the recursion only happens in the else branch of the inner if.) Not exactly what I had in mind (ends up halting at a different instruction), but I believe it should work.

Actually, come to think of it, assuming that no instruction should be able to be repeated (via recursion) in the same clock cycle without a flameout, there's a slightly simpler and safer variant that would catch loops of any instruction, not just a JMP. The additional safety comes from the code being concentrated in fewer places, and not needing to be duplicated for each relevant instruction.

... (the rest is same as before...)
void DoProcess() //this actually executes op-codes & whatnot
{
    if(runAddresses.Contains(currentCounter))
    {
        DoFlameout();
        return;
    }
    runAddresses.Add(currentCounter);
    ... code for each instruction goes here, no further checks needed...
}

Of course, if you ever add any instructions that should be able to re-run the same address immediately (e.g. an "overwrite self and immediately re-execute" instruction), this won't work and you'd have to spread it out per instruction again. But I'd suggest against adding something like that, since it's rather dangerous (it could overwrite itself with itself, and then there's a loop again. Better to say that the overwrite requires a clock cycle, even if the implicit jump-to-self that follows doesn't).

And yes, this solution would somewhat limit a two-core version of the PC, but logically, if such a loop would break a single-core CPU, then it should also break the core that ran the loop in a two-core setup as well, even if the other core would still work afterwards. (Which it might not, since the first core breaking might also break something on the motherboard that the second core needs to function.) It's also easy to work around - just ensure that your busy loop includes a non-JMP instruction to give the second core a moment between instructions to modify the first core's memory. (It's kind of arguable whether it matters which of the two instructions it modifies...) Or use IFJMP instead, since that's not instant. (Unless you intend to make it be?)

itch.io

Viewing post in Code sharing megathread