A week ago I released my really tiny RISC-V emulator. It was just complicated enough to
run Linux. It’s gotten a lot of traction. People like Joshua Ashton have used it as a
template for writing their own minimal RISC-V emulators. Many people have been asking me,
“Can your emulator run Doom?” After some tinkering, I found out that in its original state,
{{no}}. Doom needs to write to a graphics output device which my emulator, as it stands,
doesn’t have. And, as it turned out, there was even a bug lurking deep in my emulator
that Doom hit. Once all of that resolved, it turned out that Doom could indeed work!
Six years ago I started working on “Embedded Doom” or “Emdoom”,
where my goal was to make a truly embedded port of Doom. One that was extremely simple with
everything compiled in. And, one that could run on RAM-constrained systems. And to that
effect I mostly succeeded as it should be able to run on systems with less than 512kB of RAM.
Maybe someday I’ll make a video deep diving into some of the cooler parts of Doom that I
found when porting this 6 years ago, for now I’m interested in porting this to run on my
RISC-V emulator. The most interesting blockers were that I wanted a way to accept input and a
way to output the video of the game without making my emulator any more sophisticated.
Thankfully, the user input and video driver for Doom are all centered in i_video.c. This
file contains the basic I/O for the game, so I can put all of my code specific to
this platform there. For keyboard input, re-used the code I wrote for the emulator
and started to work on a way to do character video output instead of graphical output.
One annoyance is that all of the content for Doom revolves around a 320x200 pixel screen,
and I am not about to re-create all of the content (though it would be appreciated if
you did to make it possible to render to a lower resolution.) BUT, we can just ignore 7/8ths of the
pixels and sample out a 160x50 pixels. We can use ANSI codes to send a foreground (text) and
background color. If a pixel is really bright, we can treat the foreground color like an LSB
and the background color like an MSB. We then use ANSI codes to set the cursor’s position to
the top left of the screen and can begin scanning through the pixels. If a character’s foreground or
background color is different than the previously outputted one, we can use the ANSI codes to change
the color of that pixel. If the color is the same, we can just print a character.
For those not in the know ANSI, or VT100, codes are sequences of characters you can
print and they will tell the terminal to do things like set the cursor position,
set/disable bold, foreground/background color,
or even make the terminal go {{bonk}}. While the origin of escape codes have been debated,
arguably back to the 1870s with Baudot code. The syntax we use today was formalized in 1975
with the VT100. Windows dragged its feet until 2016 when they made ANSI codes a first-class
citizen in Windows command-line apps. You can switch to ANSI escape mode in Windows
with the command “system(“”)” which works in all console applications- even Python!
I actually prototyped this video output and player input module on my regular Desktop
Linux system in a regular terminal before going the RISC-V version.
If we wanted to use the emulated Linux terminal output in the kernel,
this would be PAINFULLY slow. But there’s nothing stopping us from just writing to the
hard-coded address 0x10,000,000 to output our codes. And considering we’re going to
be outputting 8k characters + color updates for around 40kB per frame, it matters that we go fast.
Before I could start trying to run this in my emulator,
I was stopped by bugs that were introduced when I tried to further
optimize DOOM. Notably removing network code and making it possible to change player count.
Part of that was that I wanted to change the number of max players from 4 to MAX_PLAYERS,
so that allocated arrays could be smaller. I knew of some places that needed to be
updated in code so I fixed those. But I didn’t realize there were more. On
my desktop it seemed like everything worked fine but the cracks started to
appear. I started seeing some things that shouldn’t be possible happening.
I got the hint that it was memory corruption of some kind because I
printed everywhere that a specific variable was updated, but somehow,
it’s value was still changing. So, it had to be other code overwriting this variable in RAM.
I wanted to talk about several techniques I’ve used when debugging these weird problems.
First, I used a .map file to see a map of everything in RAM. I found the variable that
was inexplicably being changed and I could see right before, there was the array “playeringame.”
Hmmm. It wouldn’t be hard to search the code for all cases where playeringame was modified.
Next I would normally use Valgrind which is great for memory leaks, finding uninitialized
variables and access faults. But, because Doom only compiles to 32-bit, Valgrind was a dead end.
Next up: libasan, or the “Address Sanitizer” by compiling with “-fsanitize=address”
“-static-libasan” GCC emits a lot more code to make sure everything it’s doing
is kosher. Running libasan actually did discover a bug, which I quickly patched,
but for some reason didn’t identify this bug, only some of the effects caused because of it.
To complete the quartet of debugging tools, I opened GDB,
and added a memory-change breakpoint on the variable that was being corrupted and ran
the program. The first time the breakpoint was hit, it was because the variable was
actually being changed. But the next time the breakpoint was hit it had nothing to do
with the variable I was watching. I had nabbed the buffer overflow in the act.
Thanks to a little bit of elbow grease, and two quick bug fixes,
I saved a couple of bytes of ram and everything worked.
It was now time to run EmDoom on my RISC-V emulator.
If I use the system and target the flat file image, we can just use almost the same
compile flags as we used for hello_linux, and emdoom just gloms everything together
into a single binary file and much to my surprise it ran on the first try.
Well, until I tried to start the game.
Some people think NOMMU means no protection at all. Quite the
contrary. Most memory access violations are to addresses below 0x10,000,000 or above
0xf0000000 - we can catch those. In spite of our emulator being the size of a walnut,
we can do the proper thing and percolate traps back up to the Linux running inside the VM. This
also works for all other types of traps like invalid opcodes, ebreak, unaligned access,
etc. The emulated kernel can properly handle printing the core dump and crashing the program
in the virtualized environment (and print this mildly helpful message to our kernel log!)
Anyway, we did get an access violation. Was it the WFI? Was it the todo about
not knowing the privilege level for traps? Maybe not enough stack? {No, no, and no}
One of the “optimizations” I made was to turn off the extra checks Doom can
do. Turning on RANGECHECK showed an assert that ought not be hit.
As I tracked the problem, eventually I found a call
to FixedMul and it looked like that function was misbehaving.
{pause}
Yeahh.
This makes me cringe because of a separate bug having to do with 64-bit math that I
never got to the bottom of. So, let’s roll up our sleeves. It's time to find and fix this bug.
Let’s do our objdump trick to get the assembly.
MULH, that is a very rare instruction to see. It’s used when multiplying two
32-bit numbers to get the most significant 32-bits and discard the lower bits when
multiplying 32-bit numbers. But it’s supposed to operate on signed numbers.
I had to debug the input and output of each assembly instruction before
I was able to finally identify the problem.
Do you see it? Registers are always stored as 32-bit unsigned
numbers. When we convert this to a 64-bit signed number, GCC doesn’t know to do the sign-extension,
and instead of multiplying by -5 for instance, we are now multiplying by 4,294,967,291.
Interestingly, because math, this is only an issue for using negative numbers,
and specifically the MULH command.
If we typecast first to an int32_t no actual operations are happening,
but GCC now knows that we should be multiplying by a negative number.
After a 2.5 hour debugging session pulling out my hair,
3 lines of code changed and everything just was {chef's kiss}
We’re only getting about 25FPS, but mostly because we’re using a text terminal to output
on. Perf details can be addressed at a later time. Point is, from here on out,
whenever anyone asks if my tiny RISC-V emulator runs Doom, I can finally say {yes}.
… even if pressing “back” causes the player to
launch forward as if fired out of a cannon for some reason?