towboot part 7

If Multiboot is so good, then why isn't there a Multiboot 2?

• software
• towboot

About two-and-a-half years ago, I released the first version of my bootloader, towboot (see the first post for how and why that happened). It supports UEFI-based x86 systems and Multiboot-comptible kernels.

But there isn’t just a version 1 of Multiboot, there is also a version 2. It’s not that much newer or that much better and there are still various operating systems using Multiboot 1, but still, I thought that it would be nice to add support for the newer version (and get ECTS¹ for that).

So, let’s see how it went.

Spoiler: It worked. There has been a new release of towboot for a few months with support for Multiboot 2.

Now that all suspense is gone, here comes detail:

recap: What is Multiboot and why is anyone using it?

The Multiboot specification describes an interface between bootlader and kernels and it has been implemented by many of them. I described why I’m using it in more detail in a previous post.

But what do these structs — kernel header and boot information — actually look like?

(I’m stealing this from the really nice multiboot crate.)

As you can see, this is a fixed layout: This struct has a fixed size and if some of that isn’t needed, then this space is (presumably) empty. Implementing this in Rust is pretty easy: Just write some getters that check that the relevant flags bits are set.

The first block is the most basic one — the header of the header, so to say. This is needed to find the header (by just scanning through the kernel image) and to verify if it’s correct.

The second block is for loading the kernel: Where to begin, where to end, where to actually place it in memory and where to jump to start executing.² If this is not given, the kernel is loaded as an ELF binary.³

The last block contains the display mode the kernel wants to start with — be it graphical or text based.

The information passed from the bootloader to the kernel looks pretty similar:

As you can see, the presence of these blocks is (again) controlled by bitflags. Stuff with an unknown size is passed as pointers – eg. cmdline is a C-style string⁴. Arrays are passed as a tuple of number of entries and pointer to the first entry. Theoretically, they can be placed anywhere in (the lower 4GB of) memory.⁵

Many of these things are outdated and no longer exist on modern systems.

And this is a problem. One reason being that it carries useless empty space along, but this is not that bad. The real problem here is that you can’t easily add new fields here — the size is fixed⁶.

So, this is why Multiboot 2 was needed.

everything is better in version 2

Because version 2 is dynamic and it looks like this:

(again, I’ve taken this from the relevant crate: multiboot2)

The information passed from the bootloader to the kernel looks like this:

And how does such a tag look like?

So, for a kernel this is pretty handy: Everything is together in memory. No pointers, just vibes offsets.

For the bootloader, however, this is where things get messy: You can’t just easily allocate such tags. If they at least had the same size, I could’ve put them in a Vec, but unfortunately, they’re not.⁷

So, what happens when a struct has a dynamic size? This shouldn’t be a problem, right?

daylight savings time

These structs are called dynamically sized types (DSTs) and they implement !Sized. They’re pretty easy to define:

enum TagType {
    TagA,
    TagB,
}

#[repr(C)]
struct Tag {
    ty: TagType,
    size: u32,
    data: [u8],
}

impl Tag {
    pub fn new(ty: TagType, data: &[u8]) -> Self {
        let size = core::mem::size_of::<TagType>() + core::mem::size_of::<u32>() + data.len();
        Self { ty, size: size.try_into().unwrap(), data }
    }
}

Wait, no, why doesn’t this compile?

error[E0277]: the size for values of type `[u8]` cannot be known at compilation time
  --> src/lib.rs:13:45
   |
13 |     pub fn new(ty: TagType, data: &[u8]) -> Self {
   |                                             ^^^^ doesn't have a size known at compile-time
   |
   = help: within `Tag`, the trait `Sized` is not implemented for `[u8]`
note: required because it appears within the type `Tag`
  --> src/lib.rs:6:8
   |
6  | struct Tag {
   |        ^^^
   = note: the return type of a function must have a statically known size
(...)

Sooo, everything that’s on the stack must have its size known at compile time, so it must be Sized.

Okay, that’s easy, I know this, just use a Box!

impl Tag {
    pub fn new(ty: TagType, data: &[u8]) -> Box<Self> {
        let size = core::mem::size_of::<TagType>() + core::mem::size_of::<u32>() + data.len();
        Box::new(Self { ty, size: size.try_into().unwrap(), data })
    }
}

Oh, this also doesn’t work:

(...)
error[E0277]: the size for values of type `[u8]` cannot be known at compilation time
  --> src/lib.rs:15:18
   |
15 |         Box::new(Self { ty, size: size.try_into().unwrap(), data })
   |                  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ doesn't have a size known at compile-time
   |
   = help: within `Tag`, the trait `Sized` is not implemented for `[u8]`
note: required because it appears within the type `Tag`
  --> src/lib.rs:6:8
   |
6  | struct Tag {
   |        ^^^
   = note: structs must have a statically known size to be initialized

DSTs cannot be simply initialized. The Rustonomicon has a solution, but I don’t think it’s very usable.⁸

So, how do you create an instance of a DST? It’s not that easy: You have to manually put the stuff in memory and then cast it to a Box by calling Box::from_raw. At least this is how the multiboot2 crate does it⁹.

And there’s another weird thing in there:

ptr_meta::from_raw_parts_mut(ptr.cast(), T::dst_size(base_tag))

fat pointers

A Box is basically just a wrapper around a pointer: it is heap-allocated memory, but it is owned, so it comes with a Drop implementation.

It doesn’t contain the size of the memory piece, though. That is stored in the pointer.

Well, maybe. Usually, a pointer is just a number in memory — the size of the memory it is referencing comes from the type. Because, usually, types have a fixed size that is known at compile time. This is called a thin pointer.

A fat pointer also contains the size of the referenced value — as you can see on the call above, it consists of a thin void pointer and the size of the variable part of the struct (this is important! it is not the whole size! don’t ask me how I know!).

can we fix it?

So, now we can create individual tags. What’s left is a builder like this:

struct InfoBuilder {
    basic_memory_info_tag: Option<BasicMemoryInfoTag>,
    // ...,    
}

impl InfoBuilder {
    const fn new() -> Self {
        Self {
            basic_memory_info_tag: None,
            // ...
        }
    }

    pub fn basic_memory_info_tag(mut self, tag: BasicMemoryInfoTag) -> Self {
        self.basic_memory_info_tag = Some(tag);
        self
    }

    // ...
}

It’s more complicated than that, but even this small example poses a problem: You can’t just wrap it.

struct Wrapper {
    builder: InfoBuilder
}

impl Wrapper {
    pub fn new() -> Self {
        Self { builder: InfoBuilder::new() }
    }

    pub fn set_memory_info(&mut self, lower: u32, upper: u32) {
        let tag = BasicMemoryInfoTag::new(lower, upper);
        self.builder = self.builder.basic_memory_info_tag(tag);
    }

    pub fn build(self) -> Option<i32> {
        self.builder.build()
    }
}

error[E0507]: cannot move out of `self.builder` which is behind a mutable reference
  --> src/main.rs:30:24
   |
30 |         self.builder = self.builder.basic_memory_info_tag(tag);
   |                        ^^^^^^^^^^^^ ------------ `self.builder` moved due to this method call
   |                        |
   |                        move occurs because `self.builder` has type `Builder`, which does not implement the `Copy` trait
   |
note: `Builder::basic_memory_info_tag` takes ownership of the receiver `self`, which moves `self.builder`
  --> src/main.rs:10:22
   |
10 |     pub fn basic_memory_info_tag(mut self, tag: BasicMemoryInfoTag) -> Self {
   |                      ^^^^

For more information about this error, try `rustc --explain E0507`.

Cell::update also doesn’t work because the builder isn’t Copy. The trick is to wrap it in an Option because then it’s Default (the default is None). I have written a crate for this in the hope that it might be useful.

Why am I wrapping this builder? Well, I’m trying to keep the code path for Multiboot 1 and 2 similar.

The builder also has a build(self) function that outputs bytes, but this is not too interesting.

self-referential structs

Some structs can not be easily owned. multiboot::information::Information, for example, wraps MultibootInfo. So, to use it, it makes sense to keep both around. But you can’t just create a new struct that contains both of them as fields, because of lifetimes. ouroboros solves this.

the fun part

And now that we can finally create these tags, what kind of fun stuff can we put in there? Multiboot 2 has many cool tags:

UEFI

The kernel can specify that it is UEFI compatible, so we don’t need to fumble around with the machine state anymore (which is hard), we can keep the system the way it is and just jump to the kernel. The kernel needs to support both x86 and x86_64 for this to work on all systems, though.

The kernel can also signal to the bootloader that it doesn’t need to terminate the Boot Services.

The bootloader can pass the System Table pointer, the image handle and the UEFI memory map. This was a larger problem because the previous implementation consumed the memory map when converting it from the UEFI representation to the Multiboot one. Also, after getting the memory map from the firmware, the bootloader is not allowed to allocate or deallocate anymore (as this might invalidate the existing memory map).

kernel relocations

The kernel can now be relocatable. I didn’t find any kernel that supports this, so I didn’t implement it either.

MIPS

Multiboot 2 is now also specified for MIPS. This is cool and all, but there is no UEFI on MIPS, so this is not useful for us.

ARM would be cool (and someone even requested it), but Multiboot 2 is not specified for ARM.

64-bit

UEFI-aware kernels might be booted directly in Long Mode, so that’s cool.

strings now have a length

They’re UTF-8, but they’re still zero-terminated.

SMBIOS and ACPI

Intel’s (now obsolete) Wired for Management Baseline Specification had some pretty novel ideas in the Nineties: one of the surviving ones is the System Management BIOS. It holds information about the hardware in a system and allows the operating system to query it. UEFI provides pointers to these tables which the bootloader can then pass onto the kernel.

We can handle the Advanced Configuration and Power Interface in a pretty similar way.

“Pretty similar” means that the acpi-rsdp crate had no getters for all fields.

booting real kernels

I’ve searched all of the existing internet (GitHub) for operating systems that have kernels that are compatible with Multiboot 2 and tried booting them. It worked! This is NetBSD:

Lemon OS, HelenOS did also work. OpenIndiana, L4Re and Theseus OS didn’t work (though this might be fixable).

what’s left to do?

Nothing major, hopefully. The biggest thingy from the previous post is done. Secure Boot is not really applicable for hobbyist and research operating systems (and no operating system aimed at end-users is using Multiboot as the primary boot protocol). The load improvements probably aren’t needed.

64-bit kernels already work via the EFI entry point – support for non-UEFI 64-bit kernels shouldn’t be too hard, either (if there are any). Relative file paths would be nice.

what’s going to happen

I’ll keep toying around with operating systems, both for fun and for grades, so keep watching this space.