towboot part 2

Look out, honey, 'cause I'm using technology

• software
• towboot

In the last post, I explained my motivation for why I was writing a bootloader in 2020. For the following parts, you’ll need to learn some stuff first:

learning the basics (background)

A bootloader is basically just glue between the firmware and the kernel. The UEFI API is quite high-level and platform-agnostic, but the Multiboot standard requires dealing with some x86 specifics, which we’ll see shortly.

multiple technologies

UEFI

The Unified Extensible Firmware Interface (UEFI¹) is a standard specifying the API of a computer’s firmware. It’s implemented by most of the desktop systems currently in use. (If you’re reading this on a PC or a laptop, it’s very likely to be UEFI-compatible. Unless it’s an ARM Mac.)

UEFI is designed to be both extensible and backwards compatible. This is realized with so-called “protocols”. Each protocol has a UUID² and may have an optional revision. Both the firmware and applications may support various protocols, but in order for an application to use a protocol it has to be supported by the firmware the application is run on (or by an installed third-party driver or application). For certain protocols the support can vary from device to device on a single system. Each entity (for instance, a device or a file) can support multiple protocols and it’s identified by a handle which is opaque to applications.

The only thing really guaranteed to be available on a UEFI-based system is the System Table. It’s passed to the efi_main function of an application alongside a handle identifying the executed application. It contains a revision, handles for standard input, output and error and pointers to the Boot and Runtime Services and to additional configuration tables.

Boot and Runtime Services

The System Table is available both during the boot process and the normal operation of a system, but the services referenced here are only partially usable after boot.

The Runtime Services are available during the whole runtime of the system and allow access to, for instance, the clock, power management, UEFI variables or the firmware’s update mechanism.

The Boot Services are only available during boot and allow an application to manage memory and task execution, load and run other applications and to access all available protocols.

Protocols

The following protocols may be nice for building a bootloader:

• Loaded Image Protocol

  Using this protocol, we can obtain information about the loaded application, such as the parent application (if there is one), the device the application was loaded from (and the application’s path inside of the device), the application’s command line, the size of the application and the memory address it was loaded to.

• Simple File System Protocol / File Protocol

  These two protocols combined provide file-based access to devices with a file system the firmware (or an installed third-party driver) supports. This gives us at least access to FAT12/16/32 volumes.

• Simple Text Input Protocol / Simple Text Output Protocol

  They provide text-based access to the console.

• Graphics Output Protocol

  This one allows access to the framebuffer to display 2D graphics and supports getting and setting the display mode. The framebuffer can still be used even after exiting Boot Services.

There are many more protocols which we could potentially use (block-based access to the hard disk or mouse input, for instance), but they are not exactly needed to write a bootloader.

UEFI applications and their execution environment

UEFI applications are relocatable PE (Portable Executable) files that the firmware or another UEFI application loads.

They are executed in the same CPU mode as the firmware, so (in most cases) 64-Bit Mode, with the memory mapped 1:1 (virtual addresses are physical addresses)³.

The firmware supports many different booting modes, the relevant ones for us are:

• Boot variables

  Operating systems installed on the device write their bootloader (and its command line) to a new UEFI variable named BootXXXX (where XXXX is a four-digit hexadecimal number) and add the number to the BootOrder variable.

• Removable media

  Operating systems installed on a medium place their bootloader at \EFI\BOOT\BOOTarch.EFI (where arch is the name of the architecture, so IA32 for i686 or x64 for x86_64). That way, a single boot medium can support multiple architectures, but it’s not possible to supply command line arguments in this case.

Alternatives

Older systems may have a BIOS. The firmware calls the bootloader in this case by loading the first sector from the hard disk into memory and then jumping into it with the CPU still being in Real Mode. If we were to write a bootloader for a BIOS system we’d need to use larger parts of assembly code and divide the program up in multiple pieces with the first one fitting into the boot sector. Also, interfacing with the firmware (for instance, to load the rest of the bootloader or even an operating system) requires still being in Real Mode and it’s done by calling interrupts. The BIOS has no support for a file system, so we’d need to implement this on our own (with very limited space for the program).

There are not many systems in use today with a real BIOS, but most UEFI implementations still support this boot method by using a Compatibility Support Module (CSM).

On virtual machines however, legacy boot is still common, sadly, and in many cases the default when creating a new instance.

Rust

Rust is a system programming language developed originally by Mozilla Research. It allows writing low-level code using both high-level abstractions and assembly code (if necessary). The compiler checks type- and memory-safety of the program, excluding code explicitly marked as unsafe. It comes with cargo, a tool that manages (among others) cross-compilation, tests, dependencies⁴ and building the program.

Compiling UEFI applications is supported by Rust itself as the i686-unknown-uefi and x86_64-unknown-uefi targets. They are rated as “Tier 2” which means that they are guaranteed to build, but not to actually work. They are also no_std, which means that they only support parts of the Rust standard library (core and alloc, among others) and they can only be cross-compiled.

The uefi-rs crate provides access to the API and maps it to mostly safe data structures and methods.

To build a UEFI application, we currently need to use a nightly version of the Rust toolchain.

Alternatives

UEFI applications are usually written in C using either gnu-efi or the EFI Development Kit. But while these have better UEFI support, C makes structuring the software much harder as there is no built-in support for either namespaces, dependency management or build automation. Using gnu-efi to build a UEFI application is further complicated by the different calling conventions and executable file formats between the GNU toolchain and UEFI. C also does not provide type- or memory-safety which makes bugs in the code much, much, much easier to miss.⁵

There are also other crates providing UEFI bindings, but they either only support x86_64 or do not map the types as nicely (returning bare C-style UCS-2 strings, for instance).

Multiboot

Multiboot (version 1, version 2) is a standard specifying the interaction between kernels and bootloaders. It emerged from of the GNU GRUB project which acts as a sort of reference implementation on the bootloader side. There is another GNU project implementing the kernel side: gnumach, GNU HURD‘s kernel.

There are currently two major versions of Multiboot in use: 0.9.96 (which I’ll just call Multiboot 1) and 2.0 (I’ll call it Multiboot 2). While Multiboot 2 is modular and more flexible, version 1 remains popular⁶, so it’s the one I’ll describe here. (It’s also the one I’m implementing). The information passed in version 2 is very similar, it’s mostly the structure of the headers which is different.

The standard allows a bootloader to load a kernel and modules such as an initial ramdisk image (both of which can have a command line) and boot it, passing information about the system.

The Rust bindings for Multiboot are provided by the multiboot crate, for which I added support for setting values and parsing the Multiboot headers (see the next post for more details).

Passing information from the kernel to the bootloader

The kernel image contains static information in the form of the Multiboot header. It starts with a magic value (so that it can be found by the bootloader by just scanning through the image), some bitflags and a checksum. It may contain more information depending on which flags are set.

These flags may require the bootloader to align the loaded modules at 4KB for the kernel to be able to map them directly as pages, they may require the bootloader to pass memory information, they may require the bootloader to pass video mode information (in this case, the kernel may specify a preferred mode), or they may require the bootloader to load the kernel as a flat binary with no regards to the actual file format⁷ of the kernel (in this case, the kernel must specify its entry point and what parts of the image to load where).

Additional flags could be introduced in the future, but this has not happened since at least 2010.

Information passed from the bootloader to the kernel

The bootloader places a Multiboot information struct somewhere in memory and a pointer to it in the EBX register. It also places a magic value in the EAX register to let the kernel know that it was booted by a Multiboot-compliant bootloader.

This struct starts with bitflags and may contain more information depending on the flags set. This may be:

• Memory information

  Either just values for the legacy “lower” and “upper” memory (see the section about x86 below) or (additionally) a detailed map of the entire memory can be passed. The latter one is passed as a pointer to an array of information structs, each containing their own size and the start address, the length and the type of the memory region, and the total size of the memory map in bytes.

• Boot device information

  This is modeled after the legacy BIOS boot interface, so it’s not really that applicable for UEFI.

• Kernel command line

• Module information

  This is passed as a pointer to (and the number of entries in) an array of information structs, each containing a start address, an end address and a command line.

• Symbol information

• Drives information

  This is passed as a pointer to an array of information structs, each containing their own size and the number, mode, cylinders, heads, sectors⁸ and ports of the drive, and the total size of the array in bytes. Same as the boot device information, this is modeled after legacy interfaces.

• Config table

  This is a pointer to the result of a legacy BIOS call, idk.

• Bootloader name

• APM table

  This contains a pointer to a legacy Advanced Power Management table, a predecessor of the Advanced Configuration and Power Interface (ACPI) that’s currently in use.

• VBE

  This contains information about the video interface of the legacy VESA BIOS Extensions which have been replaced by the GOP in UEFI.

• Framebuffer information

  See one of the next paragraphs for more information.

Text is passed as a pointer to a C-style string. Each of these structs and strings can be anywhere in memory, although the standard requires them to be under 4GB in most cases.

Machine state

The standard requires more from the bootloader than just filling in the correct values to EAX and EBX before jumping to the kernel’s entry point: It requires the CPU to be in 32-bit Protected Mode, without paging⁹ or interrupts. (See the part about x86 below for details about how to get there.)

Video modes

The standard allows for both text- and pixel-based video modes, but only UEFI’s GOP 2D graphics interface supports access via a framebuffer¹⁰. (The Simple Text Input Protocol or Simple Text Output Protocol can only be used by calling their methods which requires the kernel to be UEFI aware. Which it’s not if it’s Multiboot 1 compliant. It could be for Multiboot 2, though.)

A pointer to this framebuffer can be passed from the bootloader to the kernel as part of the Multiboot Information struct, alongside information such as width, height, color depth and the pixel format.

Alternatives

There do not seem to be any operating system agnostic alternatives.¹¹ Both Linux and NetBSD roll their own boot protocol, although the Linux kernel also supports being loaded as a UEFI application and NetBSD also supports Multiboot.

x86

I chose the x86 family of platforms as the target for our little bootloader. To be even more precise: the bootloader is built to run on both the i686 platform (32-bit) and on the x86_64 platform (64-bit). This covers most of the desktop hardware currently in use.¹²

During most of the boot process the CPU architecture is not important (see the next post for details), but the machine state required by Multiboot when jumping to the kernel requires us to understand a few x86 specifics. They can best be used by writing (inline) assembly.

Modes

A modern x86_64-based CPU has multiple modes for executing code:

• Long Mode

  • 64-Bit Mode

  • Compatibility Mode (32-Bit)

• Legacy Mode

  • Protected Mode (32-Bit or 16-Bit)

  • Virtual-8086 Mode (16-Bit)

  • Real Mode (16-Bit)

(A 32-bit x86-based CPU is missing Long Mode and its submodes.)

While UEFI applications are running in either 32-bit Protected Mode or 64-Bit Mode (depending on the system), Multiboot requires the CPU to be in 32-bit Protected Mode, without paging or interrupts.

Switching from 64-Bit Mode to 32-bit Protected Mode requires switching to Compatibility Mode, first. Luckily, rustc automatically generates the necessary instructions for that when compiling 32-bit inline assembly for a 64-bit target.¹³ What we still have to do ourselves is disabling interrupts, paging, PAE and Long Mode (thus switching from Compatibility Mode to 32-Bit Protected Mode). All of this can be done by idempotent instructions, so there is no need to check whether the CPU already is in 32-bit Protected Mode or whether PAE or paging is enabled, yay.¹⁴

Memory

Modern x86_64 CPUs physically support 256TB of memory (and much more virtually). But this has not always been the case:

The first x86_64 CPUs only physically supported 128GB of memory, The i686 CPU only supported 4GB virtually and (with PAE) 64GB physically. So, if the machine is in the state the Multiboot standard requires, the kernel only has access to the first 4GB of memory.

In Real Mode (modeled after the 8086), only the first 1MB of memory is accessible. Typically, the region between 640KB and 1MB is not freely usable, because it is used for memory-mapped IO, for instance. The term “lower memory” refers to those first 640KB of memory that are freely usable for an application in Real Mode.

“Upper memory” then refers to the next freely usable chunk of memory, starting at 1MB up to about 10MB, in practice. This is the memory an application running on a 286 (which had a 24-bit address bus) could use, historically. Nowadays, much bigger chunks of continuous memory are available at higher addresses, but the Multiboot standard still references those two terms.

Alternatives

While Multiboot 2 does also support MIPS (see section 3.2 of the spec) and UEFI does also support Itanium, ARM and RISC-V (see section 3.5.1.1 of the spec), i686 and x86_64 are currently the only platforms which are supported by both. They are also the ones most commonly in use for desktop systems.¹²

ELF

A Multiboot-compliant bootloader has to support loading kernels in the Executable and Linkable Format.

An ELF file consists of an ELF header which contains information about the architecture and operating system the executable is supposed to be run on, the address of the program’s entry point, references to the Program Header which contains the information on how to load the program, to the Section Header which contains information about all parts of the image (in addition to code, that may be symbols, for example) and more.

Each entry (of both Program and Section Header) contains the data’s size, its offset inside the file and a virtual and/or physical address where it should be loaded to (these addresses may be zero, indicating that this part of the file does not need to be loaded).

Rust bindings for interacting with ELF files are provided by the goblin crate.¹⁵

Alternatives

To be Multiboot-compliant, a bootloader also has to support loading a flat binary as described in the Multiboot header.

It can also support additional executable file formats, but that’s not required.

There are other crates for parsing ELF files, but they only support 64-bit files or do not allow for editing the section headers (which we need to load the symbols).

TOML

Tom’s Obvious Minimal Language is a simple, yet type-safe and well-defined configuration file format. Also, good Rust bindings exist for it.¹⁶

See the next post for more details on what different kinds of settings can be configured and why the configuration is stored in a file.

Alternatives

INI is a very simple format for configuration files, but it is not standardized and has no support for nested values or other data types than strings. Also, the seemingly only INI parsing crate with no_std support does just produce a stream of options.

JSON is a format for (de-)serializing JavaScript objects. It does not support comments.¹⁷

CBOR or another binary file format could be used. But this would require special tooling for editing the configuration. This tooling would also have to be available for multiple operating systems.

Another alternative would be creating a domain-specific language and writing a parser for it, but no.

Alternatives

There are existing bootloaders supporting both UEFI and Multiboot:

GRUB

GNU GRUB is a widely used bootloader which supports various platforms and operating system interfaces. It also includes a menu where entries can be interactively edited. It’s configured via a complex scripting language. GRUB acts as a sort of reference implementation of the Multiboot standard on the bootloader side.

Syslinux

Syslinux is a very lightweight bootloader. It supports multiple platforms and some operating system interfaces. Its current release is from the last decade, namely 2014.