User:Johnburger/OS/Bootstrap

Introduction

The expression 'booting an Operating System' comes from the earlier term 'bootstrap the OS'—a reference to the concept of "lifting yourself up by your own bootstraps". The idea of starting from a very simple starting point, and incrementally adding functionality, building on what was built before until the complete system is ready, is not literally like that impossibility—but when starting out and looking down the l-o-o-n-g road ahead, it can seem just as impossible!

If you want to write your own OS, you need to organise to get it into the computer's memory. That means you need a bootloader of some description—unless you simply burn it into the boot ROM! For a PC this isn't really feasible, so you can either leverage an existing one (something like GRUB or UEFI) or roll your own. Of course, the bootloader is only the first step: you then need to turn the current machine environment (memory contents, peripheral state, loaded programs, etc.) into what your OS needs to actually do its thing—you cannot avoid writing the bootstrap process for your OS, since otherwise it'd be someone else's!

Booting an x86

Most computers, when first powered on, have a very limited guaranteed start state. For example, the Intel® x86 series of processors start up with little more than the Code Segment:Instruction Pointer (CS:IP) register pair at (16 bytes before) the top of the computer's address space! (All data segments are loaded with 0x0000.) It is incumbent on the computer manufacturer to ensure that there is an executable instruction there—and that the instruction knows where it is (it needs to JMP somewhere else in fewer than 16 bytes!) and what it cannot (yet) do. A perfect example: at that point the RAM isn't even set up yet, so cannot be relied upon to store data, so there can be no stack. The code here simply has to have been written in assembly language.

A more esoteric example: as described above, the CS:IP in the original 8086 and the successor 80186 is defined to start at F000:FFF0, which, with the x86 real-mode segmentation mechanism, references the physical memory location 0xF_FFF0. The 8086/'186 has a 20-bit address bus, therefore a 1MB address space, so this is 16 bytes less than the top of addressable memory. The successor 80286 has 24-bit address bus, therefore a 16MB address space. The 80386 has a 32-bit address bus, therefore a 4GB address space. But all these extra addresses cannot be accessed unless the processor is in Protected Mode—yet it is defined to start up in Real Mode, with a maximum of 1MB of addressable memory.

Does that mean that the computer manufacturer has to put ROM in the original location (0x000F_FFF0), with RAM both below and above it? How inconvenient! Well, yes—and no. "Yes", because in order to run legacy software that expects the original PC's memory map, the original memory map needs to exist. But "no", because they can add a software-settable electronic switch that can move the addresses between the top of the 'old' address space to the top of the 'new' address space. That way, part of switching into Protected Mode would be to also set the switch to move the BIOS from the 1MB area to the 16MB or 4GB area.

Only… they don't have to. Intel thought about this, and helped manufacturers using the '286 (and above) who didn't want to worry about legacy with a simple trick. At startup, the CPU still initialises the CS:IP as F000:FFF0—since it's in Real Mode, they had no choice. But they also 'fake' CS to reference the address lines above the original 20 lines as 1 too. That means that at startup, the actual first instruction executed is at 0xFF_FFF0 (for '286), 0xFFFF_FFF0 (for '386, '486 and Pentium™), 0xF_FFFF_FFF0 (for Pentium Pro™) etc.—the top of the CPU's address space!

But if those address lines are stuck at 1, how can code less than 1MB be accessed? Those 'phantom' address bits are defined to remain 1 until CS is loaded with a new value, either by a far JMP, far CALL, or interrupt—upon which they'll be loaded with 0 if the processor is still in Real Mode. This means that the bootstrap code has to carefully NOT load CS until it has somehow established code in the original 1MB (either by 'flipping' the aforementioned switch, or simply putting code in RAM there to execute)—or it has entered Protected Mode and can access the whole address space.

BIOS Boot

While the above is interesting in its own right—and describes just how limited the CPU's execution environment is at first power-on—most developers don't need to worry about any of this. In fact, most developers don't have to worry about the bootstrap process at all! They just wait (impatiently) for it to take place, then start working with a fully-booted OS. But for the OS developer, the bootstrap process is part of the problem of getting an OS up and working.

Luckily, much of the hard work to boot a PC has been done by the computer manufacturer. They provide a BIOS, to not only get the CPU into a much more well-defined state (albeit still in Real Mode…), but also to provide services that the nascent OS can leverage.

For example, the original IBM® PC™ boots from the floppy disk (if one is fitted). There has been a LOT of code executed to get each part of the PC ready, and typically the last thing that the BIOS does is attempt to load the very first sector of the floppy into RAM at 0x0_7C00. If the load is successful, AND the 512-byte sector has the signature 0xAA55 at 0x0_7DFE (indicating that the code knows it is a boot block), then the BIOS simply JMPs to (or CALLs) 0x0000:7C00 (or sometimes, annoyingly, 0x07C0:0000…). And as far as the BIOS is concerned, its job is done. (If that code were to do a RET, the BIOS may very well try the next configured boot mechanism—but that's only in newer BIOSes.)

That 512-byte sector (510 bytes, given the required 2-byte BIOS signature) has to start the OS boot process. There is no way that the entire OS can fit in 510 bytes, so at best all it can do is go looking for the rest of the OS on the floppy—using the BIOS' services to do the loading. After all, the boot sector can't hold the driver code for the floppy as well as the boot loader—not least because the floppy driver code may be proprietary to the computer manufacturer! That is the whole point of the BIOS: to provide standard entry points for different services, that are each implemented with code specific to the peripherals supplied with the PC. The history of the PC has been so long that now most standard peripherals have a standard programmatical interface (all driver code can thus be the same), but when the PC was first designed it was recognised that this was not going to be the case at the beginning.

This historical design is still extant in BIOSes today. Exactly the same thing happens in today's PCs—except that the boot sector is usually loaded from a hard disk (or perhaps a USB stick) rather than a floppy (see below). There has been a relatively recent press to modernise this process: the Unified Extensible Firmware Interface (UEFI) is slowly replacing the traditional BIOS in new machines (not least due to Microsoft® requiring it for Windows™ 10 compliance), and with it the assumptions of what the starting environment is for a boot loader (for one thing, it's already switched to Protected Mode!). But there are sufficient legacy PCs out there—and UEFI allows Legacy booting—that it is still worth the effort to understand and even implement a from-BIOS boot system. And then this can be adapted to suit the UEFI environment: after all, the UEFI environment is further down the desired path to a fully-booted OS, so there are some things the boot loader simply doesn't have to do any more!

BIOS Environment

Assuming that the BIOS has just loaded your code into RAM from the boot media (either floppy, hard disk or USB stick) and JMPed to it, the default x86 (legacy) BIOS environment is quite limited—but far more useful than the original power-on state! You can expect the following:

• The CPU is in Real Mode;
• The A20 Gate is (probably) OFF. See A20 Gate below.
• The screen is (probably) in 80x25 text mode—even if splash-screen graphics were used during the boot process, it should have reverted to text mode for legacy reasons;
• The CS:IP code register pair are either 0x0000:7C00 or 0x07C0:0000 (both correlate to physical address 0x0_7C00);
• The real-mode Interrupt Vector Table (IVT) is at 0x0_0000, with various default CPU exception handlers, BIOS interrupt handlers, and hardware IRQ handlers set up;
• The SS:SP stack register pair is set up somewhere in RAM—but this is often (*gasp!*) 0x0_0400—which is right at the end of the IVT.
  (And remember, stacks grow DOWN—so every PUSH, CALL or INT is corrupting the IVT…);
• The BIOS Data Area (BDA) is at 0X0_0400. This is used by the various BIOS services as storage for their state. For example:
  • The keyboard state and buffer, holding which keys have been pressed;
  • The current video mode, including the number of (text) rows and columns;
  • Information about other hardware, such as COM ports and printer ports;
• The 512 bytes loaded from the boot media are at 0x0_7C00—nicely matching the contents of CS:IP;
• The Extended BIOS Data Area (EBDA) is at the top of (real-mode) RAM—something like 0x9_FC00. You can find out where from the BIOS;
• The DL register (probably) holds the BIOS identifier for the boot media (either 0x00 or 0x80);
• The ES:SI data register pair may hold the location of the hard disk boot partition's information in the Master Boot Record (MBR)—usually at 0x0_07xx. See Hard Disk Boot Environment below.

Floppy Boot Environment

If the boot sector was loaded from a floppy disk, the above information (except for ES:SI) is complete. The DL register should contain 0x00.

Hard Disk Boot Environment

While it is possible to put your boot sector in the first sector of the hard disk (in which case it's almost as though it was loaded from a floppy, except for DL holding 0x80), it is probably better to take advantage of the hard disk's partitioning system. Most hard disks are usually partitioned into a number of regions, each with a dedicated role: maybe a boot or recovery partition, or (for Linux) a swap partition. Of course the biggest partition is usually where the OS is installed—although there may be an OS boot partition and a user data partition. These all appear as separate "volumes" or "drives" to the OS, even though in reality they're merely regions on the same physical disk.

The most common mechanism to partition a hard drive is the legacy Master Boot Record (MBR) partition table, created by such commands as fdisk or diskpart. The more recent GUID Partition Table (GPT) mechanism uses a more generic (and complicated) system. The MBR mechanism is going to be assumed for the rest of this article.

Master Boot Record (MBR)

The MBR is an example of a "chain loader". This is a bootloader that attempts to load another bootloader. That bootloader in turn could load yet another, or actually start to load the OS. The MBR doesn't care—as long as the next loader meets a couple of criteria, it will JMP into it.

The first thing the MBR does is move itself out of the way, and JMP to the new location. The usual relocation point is 0x0_0600, freeing up the previous 0x0_7C00 location as the load point for the next bootloader. The new bootloader doesn't even have to know that it was loaded second: it may not even care.

The next thing the MBR does is examine its own boot sector. The final two bytes are the boot signature 0xAA55, but the previous 64 bytes are configured as a four-entry partition table, with each 16-byte partition entry describing a partition (region with a start sector and size) on the disk (or left as all zeroes). That leaves 512-2-64=446 bytes for code to let the MBR "do its thing". The MBR looks through the table at each entry, looking for one marked as the boot partition. If it doesn't find it, it prints an error message and stops.

If it finds an entry marked as a boot partition, it uses the information in the entry to load the first sector of that region into 0x0_7C00. If that is not successful, or the last two bytes of that new sector are not the boot signature 0xAA55, it prints an error message and stops.

Otherwise, it simply JMPs to the new boot sector's entry point. That boot sector could take advantage of knowing that the MBR (probably) used ES:SI to search the partition table for the partition entry, in which case the new boot sector now knows where on the disk it starts, and how large its partition is!

To write your bootloader into the beginning of the partition rather than the beginning of the hard disk requires more work: rather than a sector number of 1, the installer needs to parse the partition table itself to work out what the start sector should be. But that's the installer's job—an article in its own right!

USB Stick Boot Environment

A USB-enabled BIOS can boot off a USB stick by treating it as a pretend hard disk. If the BIOS is implemented correctly, the boot loader doesn't even know that it isn't loading off a hard disk, since the standard BIOS calls will "just work". Depending on how large the USB stick is, it may or may not even have its own MBR—in all respects, the boot loader can boot from the USB stick as though it was a hard disk (see above). As a development environment target, a USB stick is actually quite useful: it's cheap, easily removable so the main OS can be booted back into, and not so much of a worry that you might "trash" the whole stick—just use the main OS to reformat it and try again.

CD-ROM Boot Environment

A CD-ROM is also viable boot media, as can be seen by the numerous so-called "Live CDs" that are circulating to allow you to try a different OS before actually installing it. You can burn a CD-ROM image onto a CD, or just use the virtual image stored in a .iso file as the starting point for a Virtual Machine (see VMware, Microsoft Virtual PC and Bochs).

Because the layout of a CD-ROM is so different from earlier media (for one thing, it's designed to be read by a wide variety of different computers, so its native format is nothing like any others!), it was designed to also support legacy modes. It can be marked to pretend to be a floppy (with tiny storage), a hard disk, or none of the above—just used natively. The first two modes mean that all the previous boot environments are available—but as soon as your OS boots, all pretence is gone and the OS will need to continue to access it as a true CD-ROM. That means that the early part of the bootstrap code can be the same as before, but true CD-ROM drivers and file system code would be needed after that.

Bootstrap Phases

Now that your OS bootstrap code is about to start executing… what should it do first? What must it do, what is easier done earlier rather than later, and what can be postponed until last? It of course depends on what features of the computer the OS will take advantage of, and how the OS will arbitrate its services to the programs that will run under its umbrella. Given an end goal of a completely booted OS, getting there from here depends a lot on what you want the OS to do.

I think of the bootstrap process as a series of phases. Assuming a BIOS boot:

• There are things that need to be done before entering Protected Mode. For example, once in Protected Mode the BIOS is effectively unavailable;
• After entering Protected Mode, the next goal may be Paging Mode—although you can do both of these at the same time, it may be easier to be able to access the whole CPU's address space from Protected Mode before starting Paging;
• After Paging Mode is enabled, there's probably still many things that need to be set up before the system is ready to start executing its first program.

The OS that I'm designing is a full disk-based, multi-processing, multi-threaded, segmented, virtual memory operating system. The OS will be providing all of the services (at a minimum) that the BIOS currently performs—without access to the BIOS. It thus needs to re-implement them inside the OS environment. The OS boot process will therefore be very long and involved, and each of the above phases needs to be carefully planned and implemented to avoid duplicate effort, and wasted space or time. For example, just looking at one aspect of the OS from top down:

1. The booted OS needs to load files from the hard disk as part of its operation;
2. The boot process needs to load various modules of the OS, as files, from the hard disk;
3. The boot sector needs to load non-BIOS-specific code (including the disk reading code!) from the hard disk just to start the bootstrap process.

Since 3. above is needed before even switching to Protected Mode, the boot sector must use the BIOS to load more of the bootstrap code. But since 2. above needs to load modules while in Protected Mode, it means that it needs to understand how to both read from the boot media as well as follow the file system to find the modules to load. It either needs its own cut-down version of what the OS will do, sufficient to load modules for booting but then discarded when boot is complete—or else it uses the OS' actual media-reading code and file system parse code to load the modules. The latter implies that that code is loaded as part of 3. above.

Before Protected Mode

The bootloader needs to be generic, but that means that it has to interrogate the computer that it is running on to find out its setup. That could be a single lookup ("Oh! This is a Raspberry Pi 3 Model B+. I need the following modules..."), but on a PC it is much more complicated! In fact, the only way to know on a PC is to ask the BIOS various questions, or get the BIOS to make various changes in that computer's specific way. And (with only a couple of exceptions) the BIOS is not callable in Protected Mode—all the questions and settings need to be done before doing the switch, or else the bootloader needs to allow back-and-forth transitions between Real Mode and Protected Mode (complicated!). As highlighted above, the most important of the BIOS-reliant functions is simply loading the rest of the bootloader—or at least sufficient so that the OS can start to "fend for itself"!

And of course the bootloader needs to set up the system preparatory to the transition to Protected Mode. According to Intel®, the only explicit requirement before the switch is that a minimal Global Descriptor Table (GDT) needs to be set up. In my design, I also want to set up the Interrupt Descriptor Table (IDT) too: I want to be able to diagnose any exceptions that my code may generate, and switching to Protected Mode and only then setting up the IDT is a lot of Protected Mode code that may go awry before it's ready.

Finally, there is some code that only needs to execute once per boot: it may switch a mode in the computer, or initialise a complicated memory structure. Once run, that code would only sit there taking up space—except that the last thing that the Real Mode bootloader does is to JMP to the Protected Mode code, which could easily be somewhere completely different. That means that the Real Mode code can be simply abandoned: overwritten later in the course of the OS' normal operation, not realising that it was obliterating the very thing that gave it life! Or, less emotively, I often liken the bootloader to a rocket booster stage: something that is discarded after it has fulfilled its function. This looks like a perfect spot for once-off code!

Before Running First Program

By "first program", I really mean "first user program". I like to think that the actual first program any OS should run is its own bootstrap program. By writing that as a standard OS program, it means that it can leverage the services that the OS provides (memory allocation, file services, and even networking), as well as setting up each service as it is being installed. And finally, it can be "unloaded" when it finishes, and not hang around until the OS is shut down.

Of course, that means that the OS' program run-time environment needs to have been designed:

• How do programs call into services like the file system or networking stack?
• How do device drivers provide services to configure what they do?
• How does the OS service requests for resources such as memory?