Introduction

Overview

Maestro is a Unix-like kernel written in Rust. It follows the POSIX specifications.

This documentation is a global overview on the way the Maestro kernel and its interfaces work. It is not intended to be an exhaustive documentation.

License

The kernel and this documentation are distributed under the AGPL-3.0 license.

External Documentation

This page lists the external documentation that is used for the development of the kernel.

Hardware technical references

• Intel® 64 and IA-32 Architectures Software Developer Manuals
• UEFI specification documents
• PCI Local Bus Specification

Software interfaces references

• Multiboot2 Specification
• POSIX Technical Standard Base Specifications

ELF

• Tool Interface Standard (TIS) Executable and Linking Format (ELF) Specification
• ELF-64 Object File Format

System V

• System V Application Binary Interface - Intel386 Architecture Processor Supplement
• System V Application Binary Interface AMD64 Architecture Processor Supplement

Miscellaneous

• OSDev

Installer

Since the kernel cannot run by itself, the installer can be used to build it.

The utility on the installer’s repository produces an ISO file which can be run on a virtual or physical machine to install the operating system on it.

For more information, check the documentation of the installer on its repository.

Build a system from scratch

This guide describes how to build an operating system from scratch. If you are just willing to quickly install a system, the best option is to use the installer.

An intermediate system (such as a Linux distribution) is required to perform the installation from scratch.

BIOS setup

While the kernel partially supports UEFI, it must boot using the legacy bios.

This is due to the fact that the only way the kernel currently uses to display information on the screen is via the VGA text mode, which is not supported under UEFI.

Make sure legacy boot is enabled in your BIOS, or the kernel will not show anything on screen.

Kernel compilation

First cd into the kernel’s crate with:

cd kernel/

Configuration

The configuration file located at build-config.toml allows to specify which features have to be enabled in the kernel.

A default configuration is available in the file default.build-config.toml. If build-config.toml does not exist, the default configuration is used instead.

Build

After creating the configuration, the kernel can be built using the following commands:

cargo build               # Debug mode
cargo build --release     # Release mode

The default architecture is x86_64. To specify another architecture, add the following parameter to the build command: --target arch/<arch>/<arch>.json, where <arch> is the selected architecture.

The list of available architecture can be retrieved by typing:

ls -1 arch/

Disk creation (QEMU)

This section is for QEMU only. If building for a physical machine, skip it.

A disk can be created using the command:

dd if=/dev/zero of=qemu_disk count=1G status=progress

The count option can be tweaked to modify the size of the disk.

Disk preparation

Create partition table

If you don’t plan to install a bootloader, this section can be skipped.

The partition table can be created using the fdisk command.

Example:

fdisk /dev/sdX

where X is the letter associated to the disk on which you want to install the system.

Be careful! This is a destructive operating. Selecting the wrong disk might corrupt your system

Either GPT (recommended) or MBR partition tables can be used.

It is recommended to create at least two partitions:

• a boot partition for GRUB (approximately 200MB)
• a main partition for the system

Create filesystems

For each partition, create a filesystem using the mkfs command.

If you don’t have a partition table, you can just create a filesystem on the whole disk.

Example:

mkfs.ext2 /dev/sdXX

Be careful! This is a destructive operating. Selecting the wrong disk or partition might corrupt your system

The only filesystem that is currently supported is ext2.

Build the system

Now comes the moment to populate the filesystem.

First, mount the main partition’s filesystem:

mkdir mnt
mount <device file> mnt

When building for QEMU, use the qemu_disk file as device file.

Files hierarchy

Create a UNIX system files hierarchy:

mkdir -pv mnt/{bin,boot,dev,etc,home,lib,media,mnt,opt,proc,root,run,sbin,srv,sys,tmp,usr,var}
mkdir -pv mnt/etc/{opt,sysconfig}
mkdir -pv mnt/lib/firmware
mkdir -pv mnt/media/{floppy,cdrom}
mkdir -pv mnt/run/{lock,log}
mkdir -pv mnt/usr/{bin,include,lib,local,sbin,share,src}
mkdir -pv mnt/usr/share/{color,dict,doc,info,locale,man,misc,terminfo,zoneinfo}
mkdir -pv mnt/usr/local/{bin,include,lib,sbin,share,src}
mkdir -pv mnt/usr/local/share/{color,dict,doc,info,locale,man,misc,terminfo,zoneinfo}
mkdir -pv mnt/var/{cache,lib,local,log,mail,opt,spool}
mkdir -pv mnt/var/lib/{color,misc,locate}

Install packages

You can decide to compile and install packages by hand, or you can use maestro’s package manager.

The minimum recommended packages are:

• bash: shell
• blimp: package manager
• coreutils: GNU coreutils
• maestro-ps2: keyboard driver
• maestro-utils: system utility commands
• solfege: the boot system

Make sure to cross compile packages so that they are compatible with the kernel.

Install the bootloader

You might skip this section if running the OS using QEMU at the condition that you run the kernel only using the cargo run command. This is because GRUB2 is already present in the ISO file that is generated by this command.

If this is not the case, it is recommended to install GRUB2 or any other Multiboot2-compatible bootloader.

First, mount the boot partition:

mount /dev/sdXX mnt/boot

Install GRUB:

grub-install --target=i386-pc --boot-directory=mnt/boot /dev/sdXX

Write the grub.cfg file:

cat <<EOF >mnt/boot/grub/grub.cfg
menuentry "Maestro" {
	multiboot2 /maestro -root 8 X
}
EOF

where X is the partition number of the main filesystem, starting at 1.

Then, copy the kernel you compiled before:

cp -v target/<arch>/<profile>/maestro mnt/boot/

Set hostname

Set the hostname of the machine my writing it into the /etc/hostname file.

echo "myhostname" >mnt/etc/hostname

Create users and groups

You must at least create the root user for the system to work correctly. It is also recommended to create at least one other user with the name of your choice.

TODO

The end

Finally, unmount the filesystem:

umount mnt

The OS is now ready to be used! Have fun!

Booting

The kernel booting sequence is supervised by the Multiboot2 standard.

Command line arguments

Multiboot allows passing command line arguments to the kernel at boot. The following arguments are supported:

• -root <major> <minor> (required): Tells the major/minor version numbers of the VFS’s root device
• -init <path>: Tells the path of the binary to be run as the first process instead of the default path
• -silent: Tells the kernel not to show logs on screen while booting

Memory remapping

The kernel is divided into two parts:

• Booting stub, located at 0x100000 on virtual memory
• Main kernel code, located at different positions depending on the architecture in virtual memory:
  • x86: 0xc0200000
  • x86_64: 0xffff800000200000

Because GRUB loads the whole kernel at 0x100000, it is required to remap the memory to use the main code of the kernel. This is done through paging.

TODO: Add schematics of memory mapping

The mapping of memory at 0x100000 is removed later because it is not required anymore.

Init process

The init process is the first program to be run by the kernel, which is in charge of initializing the system.

The program must be located at /sbin/init, or another path if specified as a command line argument.

The init process has PID 1 and is running as the superuser (uid: 0, gid: 0). If this process is killed, the kernel panics.

TTY

The TTY (TeleTypeWriter) is the main interface with the kernel.

The TTY (partially) supports:

• POSIX terminal interface (Wikipedia)
• ANSI escape codes (Wikipedia)

If running with the VGA text mode, the TTY can only display the following characters:

Process

A process is a program being executed by the kernel. Each process has a unique PID which is allocated at creation.

State

A process can have the following states:

The Running state is the only state in which a process can be executed.

The following state transitions are valid:

stateDiagram-v2
    [*] --> Running

    Running --> IntSleeping
    Running --> Sleeping
    Running --> Stopped
    Running --> Zombie

    IntSleeping --> Running
    Sleeping --> Running
    Stopped --> Running

    Zombie --> [*]

Devices

Devices are represented by two types of files: Block Devices and Char Devices.

Each device file is also associated with a major and minor number, allowing to identify it.

Those files are usually present in the /dev directory.

Device type abbreviations:

• C = Char Device
• B = Block Device

The following sections describe devices that may be present on the system. This list may be extended by kernel modules and as such, doesn’t include every possible devices.

Default devices list

The following devices are present on the system by default.

Dynamic devices

This section describes devices that may or may not be present depending on the system’s peripherals.

Filesystem

A filesystem is a representation of a files hierarchy on a storage device.

The following filesystems are natively supported:

• ext2: a common filesystem in UNIX environments. Now obsolete (to be replaced by ext4)

kernfs

A kernfs is a special kind of filesystem that do not store any information on any storage device. Its purpose is to provide a file interface to easily transmit information to the userspace.

Native kernfs kinds include:

• tmpfs: storage for temporary files on RAM
• procfs: provides information about processes
• sysfs: provides information about the system

Virtual FileSystem

The VFS is a filesystem that has no representation on any storage device. Rather, it is built from other filesystems that are assembled together to form the system’s files hierarchy.

Mounting a filesystem is the action of adding a filesystem to the VFS so that it becomes accessible to users.

The directory on which a filesystem is mounted is called a mountpoint.

tmpfs

The tmpfs provides temporary storage on RAM for any file. It is usually mounted at the path /tmp.

Since files are stored in RAM, they are all removed when the system is shutdown on reboot.

The main goal is to provide fast access to files that do not require persistence.

procfs

The procfs is a filesystem providing information for each running processes. Its structure is based on the one from Linux.

Each process has its own directory at the root of the filesystem. The name of the directory is the PID of the process in decimal.

A process’s directory contains files with information about the process.

TODO: list files

Userspace

The userspace is the place where user programs run. It is meant to have an interface close to Linux.

A program running in userspace is initialized using the System V ABI specification (see external documentation).

System call

System calls are the main way for programs to communicate with the kernel.

The system call table can be found at the root of the module kernel::syscall.

ABI by architecture

Note: the end bound of errno ranges are exclusive

x86 (32 bits)

x86_64

Compatibility mode

The kernel supports running 32-bit programs on 64-bit kernels. The ABI is the same as kernels compiled for 32-bit.

ELF

ELF (Executable and Linkable Format) is an executable format supported by the kernel, which can be used to represent programs.

The specification of this format can be found on the page External Documentation.

Script

A script can be run directly by the kernel by specifying its interpreter use a shebang.

The syntax of a shebang is the following:

#!interpreter-path [optional-arg]

The shebang is placed at the top of the script file.

Description:

• interpreter-path is the path to the interpreter program. The interpreter can itself be a script, up to 4 recursions
• optional-arg is an optional argument to be appended to the interpreter

Debug

This section describes debugging features integrated to the kernel.

Selftesting

Unit tests and integration tests are present in the kernel.

To run them, use the command:

cargo test

GDB

GDB can be attached to the kernel in order to debug it. To do so, run the script located at scripts/gdb.sh.

The script runs the kernel with QEMU, using the disk present in the file qemu_disk and automatically attaches GDB to it. To begin execution, just type the continue command on GDB.

Logging

The kernel can transmit logs to another machine (the host machine if running in a virtual machine) using the serial port.

On QEMU, logs can be saved to the serial.log file by setting the QEMUFLAGS environment variable:

QEMUFLAGS="-serial file:serial.log" cargo run

Tracing

The memtrace feature allows to trace usage of memory allocators. This is a debug feature, so it is not meant to be used in production.

To use it, compile the kernel with the memtrace feature:

cargo build --features memtrace

When run, the kernel will then write tracing data to the COM2 serial port.

This data can then be fed to kern-profile to generate a FlameGraph.

Data format

The output data is a series of samples. A sample represents an operation on the allocator.

The following operations exist:

Each sample is written one after the other and has the following layout in memory:

Hardware timers

This page describes supported hardware timers, for each architecture.

x86_64 and x86

The frequency of the APIC timer is not known, thus we need to calibrate it (determine its frequency). This is done at boot using the HPET.

Scheduler

For more details about processes, check this page.

The scheduler preempts execution of the currently running process to switch context to another process in its run queue, in order to share CPU-time across processes. Each CPU core has its own scheduler.

When a process transitions into Running state, it is inserted into the run queue of a scheduler. The kernel attempts to balance processes across CPU cores.

Likewise, when a process transitions into another state than Running, it is dequeued (removed from its run queue).

Context switching can be triggered by a timer interrupt or when waiting for a resource to become available (for example). It can also be triggered manually by calling schedule.

If there is no process in a scheduler’s run queue, it shall switch to the idle task, which is a kernel thread with PID 0 that puts the CPU in idle state.

Critical sections

Sometimes, we want to be able to process interrupts, but prevent the scheduler from preempting the process.

In order to achieve this, we have to use critical sections. A critical section is entered by calling preempt_disable, and is exited by calling preempt_enable. To ensure correctness, one should prefer using the critical function.

Note that:

• preempt_enable or critical may preempt the execution context before returning
• calling schedule inside a critical section is invalid (for obvious reasons)

Critical sections can be nested. This is handled with a per-CPU counter.

Synchronization primitives

Spin

Spin is simply a spinlock, the most basic synchronization primitive. A spinlock is acquired by atomically setting its value. Other contexts trying to lock it in the meantime will loop until the value is clear (by unlocking it).

A spinlock does not have context ordering, nor make a process sleep. For this, use a Mutex.

RwLock

RwLock is a read-write lock (also called “pushlock”). It allows locking a resource like a spinlock, except it can accept several readers OR a single writer at once (contrary to the spinlock which accepts only one reader or writer at once).

This is useful to reduce contention when a resource is read often, but rarely written.

Wait queues

The WaitQueue makes a process wait on a resource by putting it in an interruptible sleep state. Processes are ordered in the queue in a FIFO fashion.

A process can wait on a resource until a given condition is fulfilled.

Mutex

A Mutex uses both a Spin and a WaitQueue. It allows locking a resources, putting processes waiting on it to sleep.

Unlocking the mutex wakes the next process in queue.

Intrusive collections

Linked lists are used quite a lot in kernel development.

In Rust, the typical memory layout of a linked list node looks like this underneath:

#![allow(unused)]
fn main() {
struct Node<T> {
    prev: Option<NonNull<Self>>,
    next: Option<NonNull<Self>>,
    val: T,
}
}

This format allows convenient operations because the linked list owns the elements.

However, there is a catch: inserting an element will require allocating memory for Node. Moreover, if T is an Arc (or another container requiring a memory allocation), we now need two memory allocations to store a simple value.

On top of that, kernel development often requires being able to insert an element in a linked list without making a memory allocation.

A simple example is the setpgid instruction, which inserts the process in the new group leader’s list. We don’t want a memory allocation to fail at that moment, since setpgid returning a ENOMEM would be weird.

To solve this issue, one should use intrusive linked lists. In Maestro, this is the List and ListNode structures.

An intrusive linked list is rather easy to implement in C, but trickier in Rust. The memory layout would look like:

#![allow(unused)]
fn main() {
struct Node {
    prev: Option<NonNull<Self>>,
    next: Option<NonNull<Self>>,
}

// Here, Foo is the element inserted in the list (it would be `T` in non-intrusive linked lists)
struct Foo {
    bar: u32,
    node: Node,
}
}

The fundamental difference is that the node is contained inside the value, instead of the opposite.

This layout also allows inserting the same element in several linked lists, without requiring more memory allocations:

#![allow(unused)]
fn main() {
struct Foo {
    bar: u32,
    node1: Node,
    node2: Node,
}
}

In Maestro, all the elements in an intrusive linked list is wrapped in an Arc, which brings several advantages:

• The value is immutable, preventing unsafe modifications of the inner Node (since Node is supposed to be a blackbox managed by List’s helpers)
• The memory allocation is managed by the Arc

An element that is inserted in a List has its reference counter incremented by one, to symbolize the ownership of the list over the element.

When going through the linked list, we may go to the next element by the prev or next pointers in Node. However, they only give access to the Node that is contained in the value, not the value itself.

The pointer to the value can be retrieved simply by subtracting the offset of the node field in the value (which is known at compile-time) from the Node’s pointer.

Unlinking is unsafe

Most operations on an intrusive linked list can be made safe (in the Rust sense), except unlinking: if a ListNode has been inserted in a List, it needs to be removed from that list.

The list points to its first element, which has no way of knowing its list (or it would require maintaining a field specifically for this, which would consume more memory and CPU time).

As such, we need to pass the list to the unlinking function in order to clear this pointer if the element being removed is the first in the list. But there is no way to guarantee at compile time that the caller will pass the list in which the function is actually inserted and not another list.

Passing the wrong list results in the correct list pointing to an element that isn’t in the list anymore, which is both incorrect and unsound (in the Rust sense).

Kernel modules

Kernel modules add features to the kernel at runtime. They are especially useful for implementing drivers.

A kernel module has the same privileges as the kernel itself and runs in the same memory space. As such, one must be careful when trusting a kernel module.

From the point of view of the kernel, the module is a shared library (.so) that is loaded pretty much like a regular one. The kernel relocates the module against itself at load time.

At build time, a kernel module is tricked into thinking the kernel is also a shared library. This is necessary to prevent linking the whole kernel inside each module.

Of course, at runtime the kernel is a normal ELF executable (GRUB does not support relocating the kernel’s ELF anyway).

Kernel module template

A kernel module template is available in mod/template/. It has the following files:

|- Cargo.toml
|- Cargo.lock
|- src/
 |- mod.rs

Cargo.toml:

cargo-features = ["profile-rustflags"]

[package]
name = "hello"
version = "0.1.0"
edition = "2024"

[lib]
path = "src/mod.rs"
crate-type = ["dylib"]

[dependencies]

[profile.release]
panic = "abort"

[profile.dev]
rustflags = [
	"-Cforce-frame-pointers=yes"
]

mod.rs:

#![allow(unused)]
fn main() {
//! <Add documentation for your module here>

#![no_std]
#![no_main]

// Do not include kernel symbols in the module
#[no_link]
extern crate kernel;

// Declare the module, with its dependencies
kernel::module!([]);

/// Called on module load
#[unsafe(no_mangle)]
pub extern "C" fn init() -> bool {
	kernel::println!("Hello world!");
	true
}

/// Called on module unload
#[unsafe(no_mangle)]
pub extern "C" fn fini() {
	kernel::println!("Goodbye!");
}
}

The kernel crate gives access to the kernel’s functions.

The kernel::module macro allows to define the kernel module with its dependencies.

NOTE: if the kernel::module declaration is not present, the module will not work

The following properties have to be taken into account when writing a module:

• init is called once each times the module is loaded. The execution must be not block since it would freeze the system
• fini can be called at all times and must free every resource allocated by the module

On success, init returns true. On failure, it returns false.

In-tree modules

It is recommended (although not mandatory) to keep kernel modules inside the kernel’s repository. As such, they can be maintained with the rest of the kernel.

In-tree modules are located in the mod/ directory.

NOTE: if a module is maintained out of tree, it is important to ensure it has an up-to-date rust-toolchain.toml, such as the version of the Rust toolchain is the same as the kernel (see rust-toolchain.toml at the root of the kernel’s repository).

Versioning

Kernel module versioning is a small subset of the SemVer specification.

Versions MUST have the following format: X.Y.Z where:

• X is a positive number (including zero) representing the major version
• Y is a positive number (including zero) representing the minor version
• Z is a positive number (including zero) representing the patch version

The same rules as the SemVer specification apply for those numbers.

Backus-Naur Form

<version> ::= <major> "." <minor> "." <patch>

Interface references

The references to the kernel’s internals and module interfaces can be found here.

Building

The procedure to build a kernel module is the following:

• Build the kernel
• cd into the root of the module’s root directory (containing the module’s Cargo.toml)
• Set (optional) environment variables:
  • ARCH: architecture to build for (default: x86_64)
  • CMD: the cargo command to use (default: build)
  • PROFILE: the profile to build for. This is usually debug or release (default: debug)
• Build the module

Example:

ARCH="x86" PROFILE="debug" ../build

Then, the built module can be found at target/<arch>/<profile>/lib<name>.so

NOTE: It is important that the specified profile and architecture match the compiled kernel’s, otherwise compilation will not work

Allocators

This page describes memory allocators that are implemented inside the kernel.

Buddy allocator

The buddy allocator is the primary allocator which provides memory pages to all other allocators.

This allocator takes most of the memory on the system and works by recursively dividing them in two until a block of the required size is available.

Freeing memory works the other way around, by merging adjacent free blocks.

More details are available on Wikipedia.

Since this allocator provides at least one page of memory per allocation, smaller objects need another allocator to subdivide pages into usable chunks. This is the role of malloc.

malloc

The kernel has its own version of the malloc function to allow memory allocations internal to the kernel.

The implementation is a located in kernel::memory::malloc.

Functions:

• alloc: Allocates the given amount of bytes and returns a pointer to the chunk
• realloc: Changes the size of an allocation
• free: Frees a previously allocated chunk

The allocator works using memory pages provided by the buddy allocator.

Allocated chunks are guaranteed to:

• Be accessible from kernelspace
• Not overlap with other chunks
• Be aligned in memory

Safe interface

It is recommended to use the safe interface through the Alloc structure instead of the low-level functions described above.

vmem

Virtual memory allows the kernel to provide each process with its own memory space, independent of other processes.

Refer to the documentation of the target CPU architecture for details on the way virtual memory works.

Memory map

The memory space of each process is divided into several chunks. Those chunks are described for each architecture in the following sections.

x86 (32-bit)

x86_64

Memory space

A memory space is a virtual memory context on which reside one or more process. It allows isolation of processes from each others.

Some processes may share the same memory space, for example using the clone system call.

A memory space contains the following components:

• Memory mapping: a region of virtual memory in use
• Memory gap: a region of virtual memory which is free, ready for allocations

A process can interact with its memory space using system calls such as mmap, munmap, mlock, munlock and mprotect.

Lazy allocations

A memory mapping is supposed to point to a physical memory in order to work properly. However, allocating physical memory directly when the memory mapping is created or cloned takes significant resources that might not be used.

For example, when using the fork system call, the whole memory space has to be duplicated, often to be quickly followed by a call to execve, which removes the whole memory space.

To prevent this problem, physical memory is allocated lazily.

To do so, the kernel maps the virtual memory in read-only. Then, when an attempt to modify the memory (write) occurs, the CPU triggers a page fault, which can then be handled by the kernel to make the actual allocation

The following cases can occur:

• simple allocation (example: mmap): The virtual memory is mapped to a default page which contains only zeros. When the kernel receives a page fault for this mapping, it allocates a new physical page and maps it at the appropriate location
• duplication (example: fork): The virtual memory of the new memory space is mapped to the same physical memory as the original. Then writing is disabled on both. When a page fault is received, the kernel performs the same operation as the previous point, except the data present on the page is also copied.

Once the allocation has been made, the kernel enables writing permission on the mapping, then resume the execution. This procedure is totally transparent from the process’s point of view.