towboot part 7

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

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 ECTS1 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.)

offset what? notes
0 magic required, 0x1BADB002
4 flags required
8 checksum required
————— —————————- —————————————————
12 header_addr present if flags[16] is set
16 load_addr present if flags[16] is set
20 load_end_addr present if flags[16] is set
24 bss_end_addr present if flags[16] is set
28 entry_addr present if flags[16] is set
————— —————————- —————————————————
32 mode_type present if flags[2] is set
36 width present if flags[2] is set
40 height present if flags[2] is set
44 depth present if flags[2] is set

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.2 If this is not given, the kernel is loaded as an ELF binary.3

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:

offset what? notes
0 flags required
————- —————————- ————————————————————
4 mem_lower present if flags[0] is set, outdated
8 mem_upper
————- —————————- ————————————————————
12 boot_device present if flags[1] is set, outdated
————- —————————- ————————————————————
16 cmdline present if flags[2] is set
————- —————————- ————————————————————
20 mods_count present if flags[3] is set
24 mods_addr
————- —————————- ————————————————————
28 - 40 syms present if flags[4] or flags[5] is set
————- —————————- ————————————————————
44 mmap_length present if flags[6] is set
48 mmap_addr
————- —————————- ————————————————————
52 drives_length present if flags[7] is set, outdated
56 drives_addr
————- —————————- ————————————————————
60 config_table present if flags[8] is set, outdated
————- —————————- ————————————————————
64 boot_loader_name present if flags[9] is set
————- —————————- ————————————————————
68 apm_table present if flags[10] is set, outdated
————- —————————- ————————————————————
72 vbe_control_info present if flags[11] is set, outdated
76 vbe_mode_info
80 vbe_mode
82 vbe_interface_seg
84 vbe_interface_off
86 vbe_interface_len
————- —————————- ————————————————————
88 framebuffer_addr present if flags[12] is set
96 framebuffer_pitch
100 framebuffer_width
104 framebuffer_height
108 framebuffer_bpp
109 framebuffer_type
110-115 color_info

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 string4. 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.5

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 fixed6.

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)

offset what? notes
0 magic 0xe85250d6
4 arch
8 length
12 checksum
16- tags dynamically sized
- end tag

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

offset what? notes
0 total size
4 reserved
8- tags dynamically sized
- end tag

And how does such a tag look like?

offset what? notes
0 type
4 size
8- other fields dynamically sized

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.7

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:

use core::mem::size_of;

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 = size_of::<TagType>() + 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 = size_of::<TagType>() + 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.8

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 it9.

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::Multiboot, 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:

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.


  1. European Credit Transfer and Accumulation System, not the train thingy 

  2. The header_addr field is used to synchronise the positions in the file and in memory. I really don’t think it’s intuitive. 

  3. Or as some other executable format. The specification requires ELF support but gives bootloaders the option to implement other ones as well. But I doubt that anyone ever did that. 

  4. null-terminated and everything 

  5. Practically, GRUB places them at very low addresses. And since everyone is just using GRUB, this is what kernels expect. 

  6. Well, not all bits in the flag are used. So, add new fields at the end and take one bit. This should be no problem in the kernel (older kernels just ignore the part of the memory) and it also just needs minor adjustments for the bootloader.

    But that is not what happened. 

  7. In C, this could probably be solved by realloc, and well, yes, in Rust, this could also be a Vec<u8>, but this constant transmuting just isn’t very nice. 

  8. Even if it were, this wouldn’t solve our problem: Function parameters are also passed on the stack — and Box::new is a function call — even if the result is placed on the heap in the end. The actual magic happens in Box::new

  9. I may have been involved in writing this. 


Kommentare

Die eingegebenen Daten und der Anfang der IP-Adresse werden gespeichert. Die E-Mail-Adresse wird für Gravatar und Benachrichtungen genutzt, Letzteres nur falls gewünscht. - Fragen oder Bitte um Löschung? E-Mail an (mein Vorname)@ytvwld.de.