void f()
{
bool run = true;
while (run)
{
g();
}
}
The obvious answer is that g() was smashing the stack. But I ruled that out, because g() was returning to f(), and if g() was smashing the stack, I would expect it to destroy the return address before it destroyed a variable in f().
I tried to solve it for a month, off and on. Every time I tried to get more information, the problem disappeared.
Finally I got desperate enough to look at the assembly output of the compiler, and light dawned. (This was g++ on an ARM, by the way.)
run, the bool in f(), had no address. It lived in register R12. When f() called g(), it pushed the return address. In the implementation of g(), the first thing it did is push R12 so that it could place its own variable in the scratchpad register. So f()'s local variable wound up in g()'s stack frame...
And g() was smashing the stack. Duh.
In particular, it called msgrcv(int msqid, const void msgp, size_t msgsz, int msgflg), which has a highly misleading API. (For those not in the know, this is a POSIX message queue implementation.) It expects msgp to point to a structure like
struct msgbuf {
long mtype; /* message type, must be > 0 */
char mtext[1]; /* message data */
};
The contractors who wrote this code used the size of msgbuf, which is 4 bytes too high, so they were writing four bytes too many, which happened to overwrite the pushed value of R12, which was f()'s run variable. (The queue did not get out of sync, because they made the same mistake on the other side, and wrote four bytes too many as well.)
One more twist: The message queue was actually wrapping communication with another CPU. So whenever an unrelated four bytes on a different CPU were zero, then the loop would exit and f() would terminate.
Around 1991 I was writing a DOS game... In a very rare circumstance the game would crash but it could happen after playing for 15 minutes or more. Sometimes not at all. I couldn't make sense of it.
At some point I decided to rewrite my entire game loop to make the game engine fully deterministic: input, time (frame) at which input happened. So that I could then record myself playing the game and replay it fully deterministically.
Except this was in 1991 and deterministic game engines did not exist back then. The first time I read about one was on a postmortem about Age of Empire on Gamasutra (IIRC). I even wrote to the article's author telling him: "Oh wow, it's the first time I read about a deterministic game engine. I made one in 1991 but since then had never heard about anybody using one." and he answered, as much excited as I was, saying he didn't know about any game doing that in 1991 either and he liked why I came up with it.
Since then it became extremely common: a game like Warcraft III for example, where there can be hundreds of units, has tiny save game files for it only records inputs and the time at which they happened (and btw it of course requires to have a same version of the game engine, or a backward compatible one, to be able to replay the save files).
But Age of Empire (1997) is the first one that I remember describing using such an engine.
Back to my 1991 DOS game... I rewrote the game engine, wrote a simple recorder recording the inputs, and played and played and played until it crashed. I then replayed the game (seen that now I could): and, sure enough, the game crashed. Huge relief. At that point I knew the bug was dead: I could reproduce it, I knew I'd smash it.
Turns out: when the hero had taken an extra allowing it to fire two shot at once and would fire two shots, and the first shot would kill the last thing on the level, then the second shot would keep living it's life during the next level (my logic would keep updating that shot and overwriting memory it wasn't supposed to access), happily corrupting memory until something would make the game crash.
It was tricky because it require a special condition.
And the only way I found to be able to reproduce the bug was to basically invent the concept of a deterministic game engine. Or at the very least independently discover it.
The game was never published but it's how my career started (very long story, for a blog or something).
P.S: if anyone know of a game using a deterministic engine from before 1991, I'm all ears (especially if it's an arcade one: that'd really make my day).