Reenigne blog

After I posted 8086 microcode disassembled, Ken Shirriff sent me a high-resolution image of the microcode ROM from the 80386. I didn't expect I would ever do anything with it for a couple of reasons: one is that it's absolutely huge (94720 bits) compared to the 8086 one (10752 bits) so (even with bitract or similar) it would be extremely tedious to transcode and check. The other reason is that I wouldn't know where to start with it - at least with the 8086 there was a patent which gave the general outline and some chunks of code which I could search for. The 80386 was a complete black box. I knew what it did and had a rough idea of how it might work but that turning that into something that I could search for in a big blob of binary seemed like an insurmountable challenge.

Some years later, I was talking to GloriousCow and Smartest Blob (possibly amongst others) on Discord and they mentioned that it would be interesting to get high resolution images of the 80386 die and try to extract the microcode from it. I mentioned that the first part had already been done but that turning the image into a binary blob and a binary blob into intelligible microcode seemed too hard. Well, they may have taken that as a bit of a challenge - they threw various bits of image processing, neural networks, and human-aided automation at the problem and a few days later had the binary blob extracted from the image and cross-checked.

Disassembling it was still quite a challenge, though! We found various patterns and gradually figured out how to rearrange it into μ-ops on one axis and μ-op bits on the other. Then on the order in which to read the μ-ops (helped by a block of unused μ-ops at one end). And how to divide up the μ-op bits into fields. From the 8086 microcode work I assumed that two of the fields would be source and destination registers to copy from. I also knew that the 80386 could do an ALU operation in 2 cycles, suggesting that there had to be a field to specify a second input to the ALU in order that the microcode for these operations could load both operands to the ALU in the first cycle and then the output to the destination on the second cycle. There was also a pattern that occurred with some regularity that we suspected might indicate the end of an instruction (we were right).

Ken helped too by tracing various lines and bits of logic on the 80386 die so that we could see how things were connected up. Gradually the picture become clearer. Each time we figured something out it gave a clue as to the meaning of other chunks of microcode that used the same construct. At the same time we were working on decoding the instruction decoder (which consists of multiple smaller PLAs) and the protection test PLA. Eventually we got to the point where we could associate 386 instructions with chunks of microcode, and things became much clearer.

The 80386 is much faster on a per-cycle basis than the 8086 for most instructions, a feat which it achieves by throwing a lot more transistors at the problem - many algorithms which are implemented by microcode in the 8086 are essentially "hardware accelerated" in the 80386 so I realised early on that more of the 80386 microcode would be setting up these accelerators instead of embodying algorithms directly. Figuring out the interfaces between the accelerators (like the multiply and divide hardware, the barrel shifter, and the protection test unit) and the microcode was a lot of the work.

How many different instructions does the 80386 have, according to the microcode? What are they?

The microcode has 215 entry points from the decoding ROM - quite an increase over the 60 of the 8086! Part of this is new instructions, and part is that instructions are handled by different routines depending on such things as whether their operands are registers or memory, whether the CPU is in real or protected mode, and whether REP prefixes are in operation. I won't list them all here but you can find them in the fields.txt file if you're interested (along with all the subroutines and shared code). It's not very meaningful to list the top-level microcode routine size since many of them do a small amount of work and them jump to a routine shared with another entry point. It's also not meaningful to list the number of opcodes each entry point handles, as the instruction decoder uses more than just the opcode to determine which routine to use.

Are there any instructions not handled by the microcode?

Surprisingly, no! Unlike the 8086 (and also unlike modern CPUs), the 80386 is always executing a μ-op and there is microcode for every instruction.

Does the microcode contain any "junk code" that doesn't do anything?

The routine from 0x849 to 0x856 inclusive (marked as "unused?" in the microcode disassembly) doesn't seem to have any entry points associated with it. I'm not completely sure what it does, but it has a lot in common with the routine #PF (PAGE_FAULT) routine at 0x8e9-0x8f5 - both end up doing an interrupt 0x0e with the error code set to the last error code from the paging unit. But this routine sets CR2 to some mysterious value from the paging unit instead of the fault linear address. All the other microcode seems to be designed to implement the documented behaviour of the CPU (or undocumented behaviour in the case of the routines that handle interaction with the ICE (In-Circuit Emulator) hardware used for low-level debugging.

Does the microcode have any hidden features, opcodes or easter eggs that have not yet been documented?

I am not totally sure about this as I don't have a real 386 machine to try it on, but I may have found a flaw in the IO permission bitmap handling that was used by some protected-mode OSes to grant user-mode processes limited access to IO ports (a practice that might be considered horrifyingly insecure by modern standards). When a 4-byte port access occurs then it seems like the microcode only checks the permission bits for the first 3 addresses. So if such an access were to be performed at the edge of the IO-port space that the process has permission for, the final byte of the access could erroneously succeed and potentially access some hardware register that the OS did not expect make user-accessible. This is quite an obscure bug so not too surprising that it was missed without the microcode disassembly. However, it is rare for a security bug in such a ubiquitous piece of hardware to go unnoticed for more than 40 years! It is possible that it only happened in some versions of the CPU. Or that I have misunderstood how the routine works and it is actually correct after all. This microcode does not seem to be from an early version of the 80386, though - there is no sign of the XBTS/IBTS instructions except in the decoder.

How can I learn to understand the microcode disassembly?

Where can I download the disassembly?

You can find it at the x86 microcode repository on github. Start with the parts.txt file which says what all the other files are, or microcode_10.txt to jump right into the disassembly.

Credits

Thank you to Daniel Balsom (gloriouscow), Smartest Blob, nand2mario, and Ken Shirriff.

I've mentioned before that I have a system for remotely running programs on my XT. Of course, since I'm running native code (mostly written in assembly code) on a machine without any kind of memory protection (and especially since I'm sometimes doing crazy things like disabling DRAM refresh), these programs will inevitably sometimes crash the entire machine. I don't want to have to go and reset it manually every time this happens, so I needed a remote reset switch.

I found this post on the Vintage Computer Forums describing a modification that is almost exactly what I want. Th exactly the modification I wanted to make, except that it's connected to a manual switch. It's trivial to go from a switch that grounds a line to programmatically grounding a line, though, so I just hooked it to the Arduino-based keyboard port manufacturing test device hack I already had, and now sending a particular byte over the serial line causes the Arduino to ground the power good line for 250ms and thereby reset the XT.

Before I bought my XT (but when I was planning on getting one) I knew I'd need a monitor for it. Fortunately for me, the region I was living in had recently transitioned from analog to digital TV signals, so a lot of people were disposing of TVs that were perfectly good apart from not having a built in ATSC decoder. So I didn't have to walk past very many yard sales before I found an ideal little 13" Orion TV1334A. The only downside was that it didn't have a remote control, which I discovered that I needed to change the brightness and contrast (without changing the brightness and contrast, the old-style CGA has rather poor composite output). I tried to make a fake remote using an Arduino, an IR LED that I pulled out of an old DVD remote, IRemote and LIRC's remotes database, but unfortunately I found that the latter did not contain codes for the TV1334A.

Fortunately I was able to find a suitable remote on eBay for a reasonable price (albeit still slightly more than I paid for the TV, which annoys me slightly). If I had just done that to start with that would probably be the end of it, but now that I've gone to the trouble of writing some IR code for the Arduino I want to be able to use it! This isn't as useless as it might sound, because it would be nice to be able to control the TV from the computer - to turn it on from another room, run a CGA program remotely, view the result over a webcam and then turn it off again.

In order to program the microcontrollers for interval bars, I needed a programmer. This is a device which connects to the chip and to a computer, and which allows one to transfer a program from the computer to the chip. You can buy them for $40 or so but I decided to make my own - since I already have an Arduino to act as a low level computer interface, I could make it very cheaply. The only complicated bit is the 13V power supply - I used this little boost converter circuit.

The Arduino program is fairly straightforward - it just reads a hex file over the serial serial line, checks the checksums and converts it to the sequence of signals according to the PIC12's programming specifications. It has facilities for reading back the microcontroller's contents and passing them back to the computer as well, and also a way of calibrating the clock rate. I added this not because I accidentally overwrote the OSCCAL and backup OSCCAL values (well, I did, but I had already read them at that point so I knew what they were) but because I wanted to know what the effect of the OSCCAL value was and if the factory programmed one was optimal.

I discovered that it wasn't quite the best (the preprogrammed value of 0x24 gave a within-spec clock speed of 996.5KHz but 0x26 gave a clock speed of 1002.0KHz). I also discovered that (with the one part I tested) the low bit of the OSCCAL was ignored and the top 7 bits interpreted as a signed quantity between -64 and 63 gave an extremely linear relationship to frequencies between 587.1KHz and 1230.1KHz with a resolution of about 5KHz. I also discovered that the frequency stability was very good - a standard deviation of only about 30Hz.

Here's the schematic for the programmer:

To build the programmer, edit the second line of build_programmer.bat to point to your Arduino installation (if it's somewhere other than C:\Program Files\Arduino) and run it. To upload it to the Arduino you'll need WinAVR, modify upload.bat to point to your WinAVR installation and run it. We can't use the avrdude from the Arduino installation here because it won't toggle the line to reset (that's normally done by the Arduino software).

To use the programmer, connect to it with a serial monitor (like the one in the Arduino IDE). There are several one-character commands:

• W - Write program from Arduino to PIC.
• O - Write program from Arduino to PIC, including OSCCAL value (necessary if write failed, or if we want to use a different OSCCAL value).
• P - Write program from Arduino to PIC, including OSCCAL value and backup OSCCAL value - only use if the backup OSCCAL value got screwed up somehow.
• R - Read program from PIC to Arduino.
• U - Upload program from PC to Arduino (follow this with the contents of your hex file).
• L - Download program from Arduino to PC.
• T - Start timing mode.
• Q - Stop timing mode.
• A - Perform automatic calibration.
• B - Output a nybble to port B (for debugging purposes.)

The returned status codes are as follows:

• K - Success.
• EF - Error: config fuses didn't verify.
• EV - Error: Program, OSCCAL, user IDs or backup OSCCAL didn't verify.
• ER - Address in hex file out of range.
• EU - Unknown record type in hex file.
• EZ - Non-zero byte count in end-of-file marker in hex file.
• EC - Hex file checksum failure.
• EH - Incorrect hex digit.
• E: - colon expected but not received.

In automatic calibration mode, the Arduino also sends calibration information as three numbers per line: OSCCAL value (3 digits), frequency in Hz (7 digits) and standard deviation of frequency in Hz (5 digits).

Don't overdo it with the automatic calibration - it reprograms the PIC with each possible OSCCAL value so you'll wear out the flash if you do it too much.

There are currently two major ways in which programming languages deal with memory. One is explicit deallocation (as used by C, C++ and assembly language) and the other is garbage collection, which is used by almost everything else.

Explicit deallocation is generally thought of as being very error prone and difficult to get right, but if your language has good features to support it (like destructors in C++) it can be very nearly as easy as garbage collection. It also has some other advantages over garbage collection:

1. Less actual memory is needed to accomplish any given task (most garbage collected languages need about twice the memory for any given task as a non-garbage collected language).
2. Non-memory resources can be cleared up in the same way as memory.
3. Everything is deterministic (which is not the case if you have a garbage collector running on a separate thread).
4. Most garbage collectors need to pause your program to work, making them unsuitable for hard real-time systems.
5. Locality of reference is better preserved, leading to more cache-friendly memory access patterns.

Garbage collection also has it's own advantages:

1. You never need to deallocate memory explicitly - the computer essentially emulates infinite memory for you.
2. You don't need to explicitly break (or avoid making) cycles of references - the garbage collector will find them.
3. With a moving collector, allocation can be much faster (requiring just a pointer increment).
4. If you can always arrange for garbage collection to happen in time that would otherwise be idle, the system can be faster overall.
5. With a moving collector, memory fragmentation can be avoided.

Generally I prefer explicit deallocation to garbage collection. This might be because my parents drummed it into me as a child that I should put away my toys when I finished playing with them, not leave them lying around to be tidied away my someone else. The one thing that does bother me about explicit deallocation, though, is the possibility of memory fragmentation. Lately I have been wondering if would be possible to fix this problem whilst retaining the advantages of explicit deallocation. Specifically what got me thinking about this is the crazy memory tricks I implemented for my fractal plotter, and how to generalize it to other programs. The result is something I call ravioli allocation (code here although it doesn't actually do anything at the time of writing).

The idea there is that you have a pile of objects which each take the same amount of memory. So there is a simple algorithm for keeping them defragmented - whenever you deallocate an object, move the highest object in memory into the space it vacated.

There are two difficulties with doing this more generally:

1. To move object X, you have to know where all the pointers pointing to it are so you can fix them up. This caused many long and painful debugging sessions with my fractal program.
2. All the objects have to be the same size.

The second problem can be solved if the objects are large enough to hold two pointers, by simulating arrays and structures using binary trees (though access time for elements increases a bit - from O(1) to O(log n)).

The first problem can be solved by linking together in a linked list all the pointers which point to the same thing. The list needs to be a doubly linked list because we need to be able to remove a pointer from the list it's in. So, each "high level" pointer really consists of three "low level" pointers - one to the referent itself and two for the previous and next "high level" pointers in the list. An object itself will also need space for two other "low level" pointers - one to the first element of the linked list of pointers pointing to that object, and one to tell the allocator whether it contains 0, 1 or 2 "high level" pointers (this can also be used as a vtable pointer for other purposes).

To avoid splitting objects across cache lines, we want the size of each object to be a power of two, so they will need to be able to hold 8 "low level" pointers (i.e. be 32 bytes on 32-bit systems, 64 bytes on 64-bit systems). That means that each 32-bit object can store 6 32-bit integers or 24 characters. On a 64-bit machine, an object could store 12 32-bit integers or 48 characters. So the small string optimization is very natural with ravioli allocation.

Once we have the ability to move objects around for defragmentation purposes, we might want to move them around for other purposes too. For example, if we expect that whenever object A is used, object B is also very likely to be used (and vice versa) we might want to put them on the same cache line. We can also set up separate memory arenas for separate purposes and move objects between them to improve locality for paging purposes.

One big downside of this system seems to be that deallocation (or moving an object in general) can be quite an expensive operation - chasing one pointer (and one potential cache miss) for each pointer that points to the moved object. However, I suspect that this wouldn't be as expensive as it sounds most of the time, since the objects that we move will tend to be ones which were allocated recently (since they will be in higher memory locations) and won't have been around long enough to have accumulated too many pointers. The objects that tend to have a lot of objects pointing to them will tend to be long lived and will migrate towards the beginning of memory (even if they don't start off there). However, walking this linked list should probably be done with non-temporal loads to avoid polluting the cache with a bunch of objects that you don't really care about. Also, consider the average case - each object can only point to two other objects, which means that the average number of pointers pointing to an object will be at most 2. And there is the nice property that a routine which doesn't deallocate data that it didn't allocate, also won't move data that it didn't allocate, so performance of small routines can be quantified nicely.

There is a fair bit of overhead to all these linked lists - 44% in the best case (one big array) and 300% in the worst case (a linked list of small records). However, some of this is offset against existing overhead (heap information, vtable pointers, fragmentation, existing binary tree pointers, reference counts[1]) so for real programs the costs might be much smaller or even negative.

Multithreading might seem to be a problem at first - one thread can't hold on to a pointer to an object in another thread's heap. However, you can transfer data to or from another thread if the other thread is in a known (waiting) state. You have to be careful transferring data between threads, but that's true anyway.

Local (stack) variables present a bit of a problem - they can't hold pointers (unless you walk the entire stack looking for pointers whenever you deallocate something). One way would be to store "how to get there" (from a global root object which is allocated first and never moves) instead of "where it is" on the stack. Another would be for the stack itself to be allocated on the heap. This is probably the faster solution, and has some nice implications for implementing things like arbitrary closures and continuations. Hardware support would definitely help here though.

[1] There is a nice synergy between ravioli allocation and reference counting - whenever you change a pointer you remove it from its linked list, and if the linked list then contains zero entries you know you can remove the object you just stopped referencing. Cycles must be explicitly broken, though - you can't have a raw/weak pointer (because it would go stale when the object it referred to moved).

Edit 14th July 2013:

Here's a good rant against garbage collection.