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. 

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

Enabling memory paging and jumping to high memory. 

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!