x86 Kernel Development & Relocatable Binaries – What I learned about Toolchains and Relocatable Code

This post is roughly a summary of the obscure knowledge I learned about toolchains and relocatable code in the last couple of years by studying the code of the microkernels NOVA and Hedron, my professional hands-on experience with kernel development, and several learning projects. I present some of the “hard and not obvious” properties of producing kernel binaries, information that only stands “between the lines” in existing projects, and topics I didn’t find information for anywhere else in that form. Everything here is something that I wish I had learned in university, or at least in a nice blog post when I started getting into kernel development.

In this post, I assume that you have good knowledge of kernels, x86_64, toolchains, and related stuff! This blog post focuses on the x86_64 architecture. Furthermore, it focuses on answering the high-level “what [to do]” and “why [to do it that way]” questions, not specific implementations, as I did this in other blog posts.

Terminology & Background

• Boot process: The process of initializing the platform in a way that useful workloads can execute. Responsibilities (such as entering 64-bit long mode) are distributed between the firmware, the bootloader, and the kernel.
• Executable or Binary: Code in a container-format with additional meta-info. Examples are ELF and PE32+/EFI.
• Loader: Code that loads an executable into memory with the help of associated meta information. For example, an ELF loader or an PE32+ loader.
• Address space: The space of addresses in which the code and the referenced data run. This can be physical address space if paging is not activated (yet) or a virtual address space when paging is activated.
• Physical address space: The address space the hardware operates on in the end. Note that RAM is mapped somewhere in physical address space. The RAM can also be fragmented in physical address space because of intermediate MMIO regions or firmware code.
• Link address: Address of a symbol assigned by the linker during linking. Address where code is supposed to live in its address space. When instruction use absolute addresses, they rely on the link address of referenced symbols. For truly position independent code, which only uses relative adressing, this is mostly an irrelevant meta information.
• Load address: Physical address where code is actually loaded during runtime. Mostly relevant when your exectuable is loaded into physical address space. In virtual memory, this is abstracted away and only needed if you want to to find the physical location of certain symbols.
• Relocation: Code was moved and doesn’t run at the desired link address specified in the executable’s metadata.
• Relocation sections/Relocation information: Meta information of an executable for a loader. This usually holds information with that the loader can patch the binary’s code at load time for its address space.
• Static executable: Code is supposed to be run at the specified link address.
• Position-independent executable: Code can be safely relocated in its address space if the loader applies all provided additional relocation information before the binary starts (binary patching). Examples are PE32+ binaries or ELF DYN executables.
• Static relocatable executable: An rather obscure and rare but technically possible thing. A binary that is marked as static executable but has a position-independent portion (“boot code”; usually written in assembly) at the beginning. This boot code can detect its relocation, live-patch itself, and for example set up a virtual address space, and then jump to the statically linked code from the compiled high-level language. Examples are NOVA, Hedron, and PhipsBoot.

General Remarks about Compiling & Linking

Compiling and linking are two independent steps that do not necessarily need to get along with each other. You can have object files with relocation information and discard them in a linker script to produce a static executable. 🤪 However, this almost always produces very weird, unintended, or even undefined behavior – just don’t do it! So, in the scope of this blog post, I assume that compilers are aware of the relocation model of the final executable. Everything else is almost always dark arts magic and non-standard behavior.

Some instructions on x86_64 only operate on absolute addresses, some support absolute and relative addresses. Compilers will use their heuristics along with the specified relocation model to emit code using relative or absolute addressing, but you will likely almost get a mixture for any non-tiny project. Hence, the emitted instructions usually can’t be limited to just static or just relative addressing.

General Remarks about the Boot Process

x86_64 is complex and has many modes. 64-bit long mode with paging is not the per-se default! Depending on the firmware you are targeting, you can’t assume all code of your kernel can be 64-bit code. Oh and yes, x86_64 has different opcodes for 16-bit code, 32-bit code, and 64-bit code! 32-bit code can’t run in 64-bit long mode (at least when compatibility mode is not active – hell, x86 is complex.)

Motivation

In my learning projects and studiying of existing projects, I was always more interested in the assembling of the kernel, the toolchain, and the boot process than creating a feature-kernel. My mental model for this blog post is: Assume you are about to write a kernel for x86_64 that boots into 64-bit mode and enables you to do something useful on the hardware. The kernel should be written in a high-level language. We want to run on a broad set of x86_64 platforms. These things come with challenges. In the following, I explain all the pain I had with these requirements in the past and which solutions there are.

Kernel Binary Challenges

Depending on the architecture, the platform, the firmware, and your bootloader, kernel binaries have to be special compared to regular user applications. Special in the sense that

• the LOAD segments of the executable file and their contents need to be specifically assembled together to cope with the environment the kernel starts in (such as being continuous in physical memory),
• the executable file format (such as ELF or EFI/PE32+),
• the kernel being relocatable in the address space it is loaded into, and
• the presence or absence of relocation information in the binary.

Further, you may need 16-bit code, 32-bit code, and 64-bit code in the same kernel binary to bring up your bootstrap processor (BSP) and the application processors (APs) to life and fully initialize all of them to 64-bit long mode! In short, you need a non-standardly configured toolchain.

Why a Relocatable Kernel?

There is no single guaranteed address range of available RAM on the variety of x86_64 platforms. Experience shows that 8M – 16M works on a couple of different platforms, but this is not guaranteed. So, our kernel should be moveable to a different location by the firmware/the bootloader.

Typical Kernel Boot Flows

For simplicity, we only look at the following two common bootflows for kernels on x86_64, which are widely used in the open-source world:

• BIOS/legacy-boot:
  • firmware hand-off to GRUB loaded from MBR
  • GRUB loads your ELF kernel via Multiboot (v1 or v2)
  • kernel starts in 32-bit protected mode without paging
    • kernel needs to start up with assembly routine to set up at least the stack
• UEFI boot:
  • firmware hand-off to EFI file loaded from disk
  • hand-off to EFI image (kernel) in 64-bit long mode (with paging)
    • entry code can be written in C++ or Rust; no assembly routine needed

If your kernel project only targets UEFI platforms, things are very easy for you! You can directly create your binary from a high-level language, you do not need an assembly routine at the beginning, you can use all kind of high-level nostd-compatible Rust or C++ features and libraries, and your kernel is relocatable for free on top because of the PE32+ format!

But, there is still a legacy world! This is what makes things interesting. The legacy world is becoming smaller and smaller as UEFI is usually the default, tho.

Constructing a relocatable kernel for legacy BIOS boot

Now we are finally where the fun begins. When we want to create a kernel for legacy BIOS boot that works on a broad variety of x86 platforms, without wanting the complexity of BIOS bootloaders in our operating system project, we are effectively limited to GRUB and Multiboot2. Multiboot2 brings us into 32-bit protected mode without paging. GRUB (even until version 2.12) can only load static ELF binaries, because relocation sections are not implemented yet. So, what to do?

We want to be relocatable, but we are lacking of a feature-complete ELF loader. 😬 We could patch GRUB, sure. But it takes time for testing and upstreaming everything. That’s a risk. But there’s another solution for this, which I call “static relocatable executable”. I learned this concept from studying Hedron, which inherited it from NOVA. I do not know whether Udo Steinberg, the creator of NOVA, “invented” that mechanism or found it elsewhere.

The basic idea is the following: You construct a static binary that consists of a “boot” section written in assembly and a “kernel” section written in a high-level language. All is linked together into a single binary whose LOAD segments are continuous in physical memory. GRUB relocates the binary as it has the relocatable Multiboot2 header tag. However, as no binary patching is applied by GRUB when it loads the ELF, it just “dumbly” relocates the binary by a static offset: GRUB moves it around in memory, not more and not less.

The entry of the binary (in the ELF header, for example) points to the boot section written in assembly. Here, special care is taken to only use relative addressing. At points where this is not possible, we calculate our relocation offset and add it to the known link address of certain symbols. This way, we are position independent. But there are also a few cases of instructions that only work on absolute addresses. To name concrete examples: ljmp and ldgdt.

The solution is to live-patch the instructions to their actual physical load address. While this sounds incredibly complex, it is effectively within reasonable limits. Hedron does it, NOVA does it, any my PhipsBoot project as well. However, this is only possible when using assembly language due to the low-level nature of that process.

With these techniques in mind, we can set up page tables and jump into the 64-bit long mode. There, we can set up the stack, and finally jump to the virtual address our high-level code was linked to. Using this strategy, effectively we are relocatable in physical address space (the address space we were loaded into) but not relocatable in virtual address space, which is fine.

Practical Alternatives to GRUB for legacy boot

If you are targeting legacy x86 boot and have the freedom to choose and install your own stage 1 bootloader, you can have a look at Limine, which is much superior to GRUB. It also brings your kernel into 64-bit mode right away.

Takeaways

• x86 is complex
• UEFI firmware makes operating system projects so much easier compared to legacy BIOS boot
  • You either write your kernel as EFI binary right away or
  • You write an OS-specific loader as EFI application. In that loader, you can use ELF libraries to implement a feature-complete ELF loader that applies relocations.
• On legacy BIOS, you can use something different than GRUB but this increases the complexity of your operating system project by an order of magnitude, IMHO.
• When you are lacking off a feature-complete ELF loader in your boot process, you are limited. If you have one, you can even construct a kernel that is relocatable in physical and virtual address space!
• Kernel development and toolchains are fun.
• Being relocatable in virtual address space is something different than being relocatable in physical address space.
• In some cases the whole toolchain need special non-standard configurations to properly assemble kernel binaries with the right structure.
• You can have object files with relocation information and discard them in a linker script to produce a static executable. 🤪 Just don’t do this.
• Some instructions on x86_64 only operate on absolute addresses, some support absolute and relative addresses. You can’t have x86 code that uses 100% relative addressing.