This article first appeared on this date in O’Reilly’s ONLamp.com online publication. The content was deleted sometime in 2019 but I was lucky enough to find a copy in the WayBack Machine. I reformatted the text to fit the style of this site and fixed broken links, but otherwise the content is a verbatim reproduction of what was originally published.

The i386 architecture is full of cruft required to maintain compatibility with old machines that go back as far as the 8086 series. Technically speaking, these features aren’t necessary anymore because any recent computer based on this architecture uses a full 32-bit operating system that could work perfectly fine without the legacy code. Unfortunately, the compatibility hacks remain in place and hurt the development of new software.

One of the details that has not changed for years is the i386 boot process. It was designed back in the days when computers had only floppy disk drives and machines had limited firmware. Since then, the procedure has not suffered any change and it makes some tasks very complex; one of these is the configuration of multiple operating systems (OSes) on a single machine.

The new firmware for Intel-based machines, the Extensible Firmware Interface (EFI), resolves this issue by providing a more versatile boot process. Other architectures have already provided improved firmware with nicer boot mechanisms, including, for example, the ability to load and execute an ELF image straight from the machine initialization code. Such is the case with OpenFirmware as shipped in PowerPC Macintoshes.

Even though alternative firmware implementations exist, the i386 architecture as we known it today will still be with us for a long time. Therefore, it would be nice to resolve some of its limitations through software. This is what The Multiboot Specification attempts to do in the boot area: provide the ability to boot any operating system from a single boot loader, hence simulating an improved firmware.

I recently modified the NetBSD’s kernel to become Multiboot-compliant. There are many code references in the text, but the main idea behind the essay is to introduce Multiboot and show you that a real-world operating system can easily be converted to support this specification. Please note that all code references point to the netbsd-4 stable branch to ensure that the code remains consistent with the explanations given here.

The i386 Boot Process

The traditional i386 architecture uses a very simple firmware known as the Basic Input/Output System, or BIOS. The BIOS is in charge of initializing the hardware after powering up the machine and provides a low-level interface to access it from boot loaders and OSes. Unfortunately, it has inherited a lot of deficiencies from the past: these services are available from real mode only and they do not provide high-level abstractions for the underlying hardware.

To put things in perspective, the BIOS is unable to access any on-disk filesystem (not even FAT) and therefore cannot directly load any executable such as the OS kernel. Instead, all the BIOS does is load the first sector of the selected boot disk into a specific memory location (07C0h:0000h) and transfer the execution control to it. To make things worse, each OS kernel has traditionally provided its own boot code tailored to its needs. For example, the old MS-DOS OS loaded from a FAT disk and executed in real mode; on the other hand, newer systems can boot from a large variety of filesystems (FAT, NTFS, Ext2, and more) and need to run in protected mode from the very beginning because their kernels are too big to fit into the first megabyte of memory (all the memory addressable from real mode).

The fact that each OS needs its own boot loader causes a lot of problems when setting up several different systems on a single machine and poses a lot of questions that the user will most likely be unable to answer. What do you install in the MBR? Where do you put each boot loader? Why do you need to configure each of them independently? Why do you need more than one?

It could be very convenient if there was a generic interface that decoupled the load and bootstrapping of an OS kernel from its boot loader. This way, an OS developer could focus exclusively on the task at hand and forget about writing a boot loader. Similarly, boot loader developers could join forces to write a more complete utility or, alternatively, write their own with minimal code, while being able to boot any OS that supported such interfaces (ideally all OSes). The good thing is that the GRUB developers already had this idea in the past and developed such an interface: Multiboot.

The Multiboot Specification

The Multiboot Specification (MS) defines a protocol between boot loaders and OS kernels that allows any Multiboot-compliant boot loader to load and execute any Multiboot-compliant OS kernel. This permits the end user to install a single boot loader in his machine and use it to boot any system directly, without having to chain-load different boot utilities.

In order to accomplish this abstraction, the MS defines two items:

• The Multiboot Header (MH)

  This is a 4-byte aligned data structure located within the first 8 KB of the OS kernel image. It provides a magic number used to identify the file as being Multiboot-compliant, a set of flags indicating specific kernel needs, and additional fields describing the structure of the binary. The latter are only used if the kernel is in the a.out format (with some exceptions); using ELF makes things much simpler and also more versatile.

• The Multiboot Information Structure (MIS)

  This is a data structure constructed by the boot loader and passed to the OS kernel as part of the boot process. It includes information such as which disk is the boot disk, a memory map, the kernel parameters, where additional kernel modules are in memory (if loaded at boot time), etc.

There is some interaction between the two structures in the sense that the MH may request the boot loader to set some fields in the MIS for a successful boot. If the boot loader cannot fulfill the kernel’s needs, the load will fail gracefully.

If you’re making good use of these two structures, it’s trivial to write a simple binary file that acts as an OS kernel—that is, a binary that is able to run standalone on the machine without any other OS. See the boot.S, kernel.c, and related files that form the example kernel distributed alongside GRUB in the docs directory.

It is also interesting to note that a Multiboot-compliant boot loader will enter protected mode and set up a preliminary GDT for a flat memory model, so the kernel needn’t do this by itself. Of course, the kernel will have to reload the GDT with values of its own later in the initialization process, but the one set up by the boot loader is enough to get started. In some sense, it’s possible to write the OS kernel as if the real mode did not exist at all, as happens on other (saner) platforms.

The NetBSD/i386 Boot Process

NetBSD/i386 uses a two-stage boot loader. The first stage gets installed into a known physical location—typically, the first sector of the hard disk or partition in which the system is installed and spans over some other reserved free space in the filesystem. This little program, which is generally limited in size, has the required knowledge to read the second stage boot loader and transfer the execution control to it; this one installs into the root filesystem as /boot, so its physical location may vary across reboots: there is nothing in the filesystem that binds a file to specific disk blocks.

Once the second stage boot loader receives control, it enters the flat protected mode (no paging, segments spanning the whole memory space), loads the kernel from disk, and runs it; it also accepts user input to choose which kernel to boot and which options to pass to it, if any. This loader also passes boot-time information to the kernel by means of the bootinfo framework. Simply put, this is a table that contains information, all gathered by the boot loader, about the machine and execution environment, including:

• Amount of available memory
• The boot device
• The kernel’s filename
• Where the console is attached (e.g., serial line, local video card)

The src/sys/arch/x86/include/bootinfo.h file holds the complete list of possible values for bootinfo items. bootinfo is similar to the MIS, although the information it includes is slightly different and, in some specific cases, more complete. In fact, this was one of the main headaches when adapting the NetBSD kernel to support Multiboot.

Later on, the kernel gets the execution control and proceeds by:

1. Storing the boot information (bootinfo or MIS) in a safe place. See the native_loader function in src/sys/arch/i386/i386/machdep.c.

2. Detecting the CPU model in use (e.g., 386, 486, Pentium).

3. Setting up a preliminary page directory and the corresponding page tables to remap the kernel’s virtual addresses above 0xC01000000.

4. Enabling memory paging and jumping to high memory.

5. Continuing to boot and processing the boot information during its initialization.

One tricky thing is that the NetBSD kernel runs, by design, at very high memory addresses (0xC0100000 and higher) for efficiency reasons: doing this allows the mapping of the kernel inside the processes’ virtual address spaces without interferences. However, as mentioned earlier, the boot loader does not enable paging so it is impossible for it to put the kernel at such high addresses (unless the machine has lots of physical memory, but that is not the idea).

The ELF file format resolves this issue: each section in the image (text, data, bss, and so on) specifies which address is its starting virtual address, but also specifies its physical load address. The NetBSD kernel’s linker script takes advantage of this to generate an ELF image mapped over 0xC0100000 but placed at the 0x00100000 physical address. Note that the address is not 0x00000000 to ensure that the kernel does not overwrite any BIOS code and/or data stored below the first megabyte (the only address space accessible from real mode) when loaded.

Before paging is enabled, the kernel code is critical because it must be careful to not use the raw addresses generated by the linker (as they point to unavailable memory positions). The RELOC macro resolves this by converting a given virtual address to its corresponding physical location. Fortunately, once paging works, no more problems appear and this is basically a non-issue.

Making NetBSD Multiboot-Compliant

Due to some limitations in the native NetBSD boot loader, I needed to boot NetBSD using GRUB in a spare machine I used for kernel testing. When doing so, I found that native NetBSD boot support in GRUB is very rudimentary, and even broken in several situations. For example, it does not set up the ksyms correctly, so ddb(4) backtraces are very difficult to understand. In addition, the upstream code does not support passing boot-time options to the kernel, but fortunately pkgsrc includes some local patches to resolve this issue.

There were two different solutions to my problems: fix GRUB to include full support for native NetBSD boots or make the NetBSD kernel Multiboot-compliant. I chose the latter because I personally like the idea behind Multiboot: it is more in the line of defining an abstract interface between two different system components. More importantly, though, is that changing the NetBSD kernel alone has the advantage that the code in GRUB will not rot: the GRUB developers are the main developers of The Multiboot Specification and, because it has no NetBSD-specific bits in it, they don’t need to have a NetBSD system available to ensure it is supported.

The first step was to define some high-level data structures to represent and manage the MH and the MIS from within the kernel—something easy thanks to the detailed documentation about them. The results are in src/sys/arch/i386/include/multiboot.h.

Then, the obvious move was to add an MH to the kernel so that GRUB could recognize it. To ensure that it was within the first 8KB of the image, I added it in the text section of src/sys/arch/i386/i386/locore.S alongside the kernel’s entry point. This was not easy at all: the kernel’s linker script had a bug that made the sections’ physical addresses point to the virtual addresses. This forced me to use the address fields in the MH to indicate where to load the file, but GRUB was not honoring them for ELF files. I had to come up with a fix for GRUB until a fellow developer, Pavel Cahyna, fixed the problem from its root: he rewrote the linker script to generate the appropriate physical addresses. Nowadays, those extra fields in the MH are not used, and a mainstream GRUB image (distributed in virtually any GNU/Linux distribution) can boot a NetBSD kernel.

With the kernel recognized as a Multiboot binary, I had to add the necessary code to parse the MIS during boot and convert it to the native bootinfo format to minimize changes in the overall kernel. Keep in mind that I was just adding another entry point to the kernel, not removing the old one, so both needed to coexist. This was tricky because of the virtual address space change that happens during bootstrap, as explained earlier: some MIS handling needed to happen before the kernel enabled paging to avoid corrupting important information (basically, the ksyms). The C code that handles this is rather delicate and, therefore, I kept it as short as possible. Once the kernel has enabled paging, the real MIS parsing is done and the kernel continues its boot procedure. You can see all of this in the src/sys/arch/i386/i386/multiboot.c source file.

At last, I would like to comment on another area that was difficult to manage. The native boot loader loads the NetBSD kernel and stores it in memory following a specific memory layout: the kernel is first, followed by an integer that registers how many symbols the kernel has, followed by a minimal ELF image that contains the kernel’s symbol and string tables. When using GRUB, these tables load in different and unpredictable locations. A first step in resolving this problem was to reserve some space in the kernel to copy the symbols table to the appropriate place on the fly, but this proved to be a very ugly hack. A recent fix moved the symbols table to just after the kernel (taking care not to overwrite it or other important information during the move). The kernel also has a specific function to initialize the ksyms global table based on a memory region (not necessarily a complete ELF image). You can see this in the ksyms_init_explicit function defined in src/sys/kern/kern_ksyms.c.

Conclusion

If all operating systems supported The Multiboot Specification, users would be happier than they are now: a very advanced boot loader supporting all operating systems would most likely exist, and its installation could be trivial. Plus, these users would not need to care about the installation of an OS disabling another OS.

Personally, I found the process of making the NetBSD kernel Multiboot-compliant to be a very interesting and instructive task. Furthermore, because almost all Linux distributions nowadays install GRUB by default, it is now a lot easier to set up a dual-boot machine with both Linux and NetBSD. Further steps involve splitting the kernel in two different sections within the ELF binary in order to map each of them at separate virtual addresses. This could simplify some of the issues that arise in the code that runs before paging is enabled.

Now it is your turn to adapt your favorite operating system to this protocol and attempt to get your modifications into the mainstream sources!