An introduction to how legacy BIOS boot works on x86 computers, as background for my project to create a compiler contained entirely within the code of a master boot record.
This post is Part 0 of a series of posts about my project to create a C compiler within a boot sector. The code for the project is on github.
Note: any statements I make in this series are only in reference to x86-compatible CPUs. This is the type of CPU found in most consumer desktops. The Intel i3, i5, etc. series and the AMD Ryzen lines of CPUs are examples of these processors, but x86 computers date back as far as 1978! Additionally, I am only discussing the legacy BIOS boot system, as legacy boot gets down to a level of assembly that I am interested in. Modern computers (newer than about 2008) will often use UEFI, an alternate startup environment, instead. In fact, several recent computers are dropping support for BIOS entirely.
To almost every user of computers, the process of starting their computer goes like this:
To those that are more technically inclined, they may know what an operating system is and understand that there's a step after "start computer" that involves picking the correct disk or partition to select, which then loads the appropriate OS.
This, of course, isn't the full story (though it's a perfectly acceptable mental model for just about everyone). There are several steps that go on throughout this process that are critical to providing you with the operating system you expect, but are nicely packaged away so that you don't need to think about them (unless you're a nerd like me that wants to think about them). Part 0 of this series will explain these steps, as background for future parts, which will go into detail about the code that I wrote.
When you turn on your computer, power starts being
supplied to the CPU. The CPU will detect this and go through
its reset sequence. This sequence initializes the CPU into a
known state, mostly by zeroing out registers, with a few
exceptions for various status registers1. After this, the CPU
fetches the first instruction from address
0xFFFF_FFF0. The motherboard on your computer
has this address (and many others) connected to the BIOS
code, which is stored in its own flash memory on the
motherboard. The BIOS then does its own setup:
To explain how a boot device is loaded, first we need to talk about "sectors". A sector is a 512 byte block of data on a hard drive. The name comes from the physical layout of hard drives. Hard drives are composed of spinning disks, which are divided into concentric rings, which are further divided into "disk sectors"3. The following diagram is adapted from this diagram on wikipedia by Heron2 and MistWiz.
In modern storage media, including solid state drives, and flash drives, these physical sectors no longer exist. However, in the interests of compatibility, and because the terminology was so well established, the 512 byte "sector" name remains.
On a storage medium designed to be booted from, the first
sector (also called the "boot sector") has some special
properties. For a drive to be considered bootable, the final
two bytes of the boot sector must be the boot signature
bytes 0x55 0xAA4. This signature is
checked by most BIOSes as a basic verification measure to
prevent loading a drive that's not meant to be booted from.
Some BIOSes may perform additional checks on the boot
sector, such as requiring that the sector be a valid Master
Boot Record (MBR). If these checks pass, the boot sector
is loaded into memory at addresses
0x7C00-0x7DFF (512 bytes), and then the BIOS
passes code execution to the start of the boot sector, at
address 0x7C00.
When the BIOS jumps to 0x7C00, this is the
first place where we, as a random software programmer, can
gain control of code. It is fairly easy to create a USB with
some bytes on it and boot from it. However, the BIOS is
not nice to us, writing code in this
environment is not easy. The IBM PC was a very influential
and widely available x86 computer for consumers and this
resulted in other computer manufacturer wanting to copy
IBM's success. They began to create "IBM compatible"
computers, which provided support for all the same software
that the IBM PC could use. This included reverse engineering
IBM's BIOS to replicate the same functionality. That is
where the first problem lies. Reverse engineering is
difficult and may have run into legal issues, so the IBM
clones were never perfect5. Every BIOS has subtle
quirks, outright bugs, or other differences in behavior.
When writing code for a boot sector, you have to be careful
to not rely on the BIOS having done
anything in particular. When the BIOS
transfers control to your boot sector, only the following
are guaranteed:
That's it. Really. You don't even know the contents of
the instruction pointer! Even though the physical address of
the code is at 0x7C00, Real Mode uses "segment
registers" to be able to use 20 bit addresses, instead of
16-bit. The memory location to load instructions from is
defined as cs * 16 + ip6. There are 1985
different combinations of cs and
ip that point to physical address
0x7C00, though in practice only 2 of the
combinations are common. When coding in this environment,
you get to do just about everything yourself. The BIOS
contains some basic input and output functions, but those
again aren't standardized and are sometimes buggy, so you
have to be cautious about using any that aren't extremely
common.
The boot sector only has 446 bytes of usable code — 512 bytes in the sector, minus 2 for the boot signature, minus at least 64 bytes for the partition table. This is not enough space to do very much, and definitely not enough to write any large programs like a whole operating system. What boot sectors tend to do is load more data from the disk that they booted from (often, but not necessarily, directly following the boot sector), and jump to that code, which has much more room to work with, only limited by the storage medium size and the amount of available memory that you can access in real mode.
Some boot loaders are even more complicated, in that the program that they load up searches the start of every partition on the current drive for additional boot records, and presents them to the user as options. If one of these partitions is selected, the bootloader will handle the partition similarly to how the BIOS handled the boot sector. GRUB is an example of a bootloader that can transfer control to other partition boot records.
This larger "second stage" of the boot loader is responsible for the setup that the computer needs. Without the space restrictions of 446 bytes of data, they can do a lot more. Typically this involves the setup needed to bring the CPU into a nicer environment. Most operating systems use 64-bit "Long Mode", which enables the use of more registers, larger registers, better addressing modes, and more accessible memory7. The boot loader will then transfer control to the operating system. The rest of the operating system from this point on is almost always written in a higher language than assembly, such as C for the Linux kernel.
It is at this point that the standard model of "wait a bit and then the computer becomes usable" matches reality again. You wait for your operating system to do whatever it needs to to start up, and this can vary based on just about anything, nothing is standard from here. Eventually, you get a pretty little desktop show up, or for some people that have very different preferences for using their computer, dropped into a nice terminal and asked to log in.
While none of this post was directly related to any code that I wrote at all, I believe that it is important to understand the environment I am coding in. 446 bytes to work with, with minimal help from the existing software on the computer, and in the most restrictive mode of the CPU. It's like my code got dropped in a jungle, without even clothes on its back, and told "good luck, make something out of this". Every other system that you have used tries to get out of this state as quickly as possible.
However, I have a unique interest in this sort of thing, and so I decided "What if I could write a single boot sector that had all I ever needed?". A previous attempt at exploring this space left me with a hex editor in a boot sector, but I quickly ended up only using it to transfer pre-assembled files from my computer over the serial port, and transferring bytes to directly execute seemed to be against the spirit of my initial goal. In a moment of enlightenment, I realized that I could write a compiler in this limited environment, using the knowledge I gained from that previous project. Others have done this before, but in different ways, and typically those cases do not have a proper MBR, opting to use the whole 510 bytes of code instead of 446, foregoing compatibility with hardware that does checks. I happen to have such hardware, on a spare computer that I use for testing, so I needed to write a smaller version. And thus, a compiler for (a subset of) C was born.
The next part of this series will be more about the code I wrote. I will go over the high level concepts of the compiler, what exact requirements I had, the terrible version of C that this compiles, and some of the ideas that I liked from other projects and integrated into my own.
