Module b2_paging

Expand description

§BST - A2: Paging

The goal of this task is to extend RStuBS with basic paging functionality, to isolate applications from each other, and to separate kernel and user code. We later want to be able to load an arbitrary number of user applications from an initial RAM disk (initrd).

This assignment includes the management of the free physical memory which is then used by the kernel and the user applications.

§Questions

What is paging? How does it differ from segmentation?
Who implements the paging mechanism?
Who defines the policy?

§Motivation

In assignment 1, we started to isolate user applications from the kernel by limiting the available instructions (using x86 rings). This is, however, not enough. Applications can still access and modify the kernel memory and the code/data from each other. In this assignment, we want to give each application its own address space, preventing it from accessing arbitrary data.

A virtual address space for an application looks like this:

+------+---------+--------+--+--------+---+-----------+-------+------------+---+
| null | deivces | kernel |  | initrd |   | user code | ... <-| user stack | X |
+------+---------+--------+--+--------+---+-----------+-------+------------+---+
0     4KiB      1MiB      ?  ?        ? 32MiB         ?       ?            | 4GiB
                 |                        |                                |
             0x0010_0000             0x0200_0000                      0xffff_f000

The memory below the 32MiB kernel boundary should be identity-mapped in supervisor mode to only be accessible from ring 0. This kernel region is shared between all applications. The user range above 32MiB, however, is different for each application and not an identity mapping.

It makes sense to permanently not map the first page (from address 0x0) (to provoke a page fault when accessed).

The second half of the memory map between 32MiB and 4GiB contains the user memory. Directly at the 32MiB boundary is the beginning of the user program code. The user stack is at the end of the memory map at 0xffff_f000, growing downwards. We leave a single page (X) free behind it because Rust forbids accessing the end of the memory map, as this breaks bounds checking and some optimization (similar to the access to a null pointer).

§Paging

We need sufficient abstractions for the page tables and their entries (the next assignment will also need them). These abstractions could also be put into crate::arch::paging, and you can reuse the Physical type in your page table entry bitfield.

Then, we can set up the kernel mapping and page tables. We also need functions to set a page directory in the CR3 register and activate paging by updating the CR0.

Detailed information on paging can be found in the Intel manual in Chapter 4.
We recommend first setting up only one mapping for the kernel area, handing it over to the CPU, and testing the correct functionality.
Pay attention to the IOAPIC and the LAPIC memory.

§Dynamic Memory Management

To dynamically create these mappings and their page tables, we need a page frame allocator that manages the available physical memory.

Luckily, a (multiboot compliant) bootloader already provides the operating system with a list of all available memory ranges not occupied by devices. It is important to note that the memory already occupied by the kernel image and multiboot modules (we are coming back to this) are not automatically excluded from this list, but must be explicitly filtered out. Furthermore, the area up to 1 MiB should not be used as many devices are mapped there.

Warning: The areas specified by Multiboot can overlap and be contradictory. In case of doubt, non-free (reserved) takes precedence.

Since parsing the Multiboot structure is a bit quirky, we have already included a multiboot crate for this. The required multiboot pointer is stored in crate::MBOOT_PTR. The multiboot memory ranges can be used to initialize the kernel and user page allocators. The kernel page allocator manages the free physical pages below the kernel boundary, and the user allocator everything above it.

We would recommend implementing the free memory management using a bitmap.

§Allocators in Rust

Rust allows defining custom allocators with the global_allocator attribute. Usually, one would use implement “slab” allocator for smaller allocations, but to make things easier you can just use the page allocator directly, wasting a bit of memory for everything smaller than a page.

#[global_allocator]
static mut GLOBAL_ALLOC: YourKernelAlloc = YourKernelAlloc;

After doing this, you can use the alloc standard library that contains a lot of useful data structures like Vectors, BTreeMaps, etc. Just add the following lines to the main.rs file (before the mod ...; statements).

#[macro_use]
extern crate alloc;

§Threads and Scheduler

The scheduler must now manage an arbitrary number of threads loaded from an initial RAM disk (initrd, see below). It is advisable to use a dynamic data structure to manage the threads.

The page directories and page tables should be set up for each application thread with the above-mentioned memory mapping. The kernel page tables can be shared between all page directories. If the dispatcher switches to another process in Scheduler::dispatch, the mapping of the next process must also become active.

If everything works, processes cannot access the memory areas of other processes and not the always-visible kernel area. Syscalls and interrupts should work again, and the kernel can easily access the memory of the currently interrupted process.

§New System Calls for Memory Management

Two additional system calls are needed to allow user programs to manage memory dynamically.

pub fn map(len: usize) -> Result<&'static mut [u8], Error>;
pub fn unmap(mem: &'static mut [u8]) -> Result<(), Error>;

The map system call adds new memory to the user application. This memory must be large enough to store the [u8] slice in it and may span over multiple pages. For this, the operating system must find a suitable gap in the user address space and insert free pages there. The memory should initially be zeroed out. If the allocation succeeds, map should return a reference to the new memory, and otherwise a meaningful error code. unmap does the inverse, freeing a previously mapped range. Remember to invalidate any TLB entries for freed pages.

Useful core library functions for slices are from_raw_parts_mut and as_ptr.

pub fn exit() -> !;

The exit system call terminates the current process and releases all associated resources. Under no circumstances should this system call return to the application. To validate memory release, the state of free memory management should be displayed. After all applications have ended, exactly as much free memory should be available as before the start of the first application.

§Separation of Kernel and User Code

To more easily isolate the kernel and applications, RStuBS should be compiled separately from the applications. For this, the applications must be moved to a separate crate. In addition, a syscall library should be created, which contains the syscall stubs for the applications. With the help of this library, each application can now be compiled individually without linking directly against the kernel. Additionally, another linker script is required that describes the structure of the executable file. This script should define a meaningful start address (0x0200_0000 for 32MiB); otherwise, it essentially resembles the kernel’s linker script (src/arch/i686/link.ld).

The directory structure might look like this:

rstubs/
    src/
        ...
    syscall/
        src/
            lib.rs
        Cargo.toml
    user/
        src/
            arch/
                link.ld
            bin/
                app1.rs
                app2.rs
        build.rs
        Cargo.toml
    build.rs
    Cargo.toml

You can create the new crates with cargo init user and cargo init --lib syscall.

Add a build.rs to the user code that selects the correct linker script (see the top-level build.rs) and the syscall library as a dependency to the user/Cargo.toml. Cargo compiles all rust files in src/bin as separate binaries (similar to a main.rs). Consequently, every application must have its own start function, which also should be the first element in the text section of the linker script (just add *(.text.start) to the beginning of the text section). Additionally, we need a simple panic handler for each application.

// user/src/bin/foo.rs
#![no_std]
#![no_main]

use core::panic::PanicInfo;

#[no_mangle]
pub extern "C" fn start() -> ! {
    syscall::println!(dbg: "Hi");
}

#[panic_handler]
fn panic(info: &PanicInfo) -> ! {
    syscall::println!(dbg: "{info}");
    syscall::exit();
}

The top-level rstubs crate now has two more dependencies: A build dependency to the user applications and a normal dependency to the syscall library, which contains all data structures that are shared between kernel and user.

#...

# Tell rust-analyzer that the user bins are part of our project
[workspace]
members = ["user"]

[dependencies]
# ...
syscall = { path = "syscall" }

[build-dependencies]
user = { path = "user", artifact = "bin", target = "target" }

This build dependency tells cargo to build the application binaries and to give us paths to them in the top-level build script, where we can further strip and bundle them.

We aim to bundle the applications into a single initial RAM disk (initrd) that can be loaded with multiboot-compliant bootloaders (GRUB, QEMU…). This is a two-step process: first, we generate so-called “flat” binaries from the individual application ELFs with objcopy (or llvm-objcopy). These are complete memory images of the programs that can be executed directly (without an ELF loader at runtime).

objcopy -O binary --set-section-flags .bss=alloc,load,contents <app> <output>

Secondly, we want to bundle all applications into a single binary with the following format.

+-------------+-------------+-------------+-------------+
| app lengths | app1 page 1 | app1 page 2 | app2 page 1 |
+-------------+-------------+-------------+-------------+
0           4KiB          8KiB          12KiB         16KiB

The app lengths page contains a large array with the size of all apps in pages and is then followed by their code, which is padded so that every app starts at a multiple of 4KiB.

These two steps should be added to the top-level build.rs:

fn main() {
    // ...

    // bundle user applications
    // - find all environment variables starting with `CARGO_BIN_FILE_USER_`
    // - flatten the referenced binaries with objcopy

    // create initrd
    // - create a header with the app lengths
    // - add the app code with the correct padding

    // store it into the build directory alongisde the kernel
    let target = env::var("TARGET").unwrap();
    let profile = env::var("PROFILE").unwrap();
    let image_path = PathBuf::from_iter(["target", &target, &profile, "initrd"]);
    std::fs::write(image_path, output /* <- your byte buffer */ ).unwrap();
}

You can execute other tools from the build script with Command.
If you use “-” as the output argument for llvm-objcopy, the code is not written to a file but returned to the stdout, which can be used directly in the build script.

On the kernel side, the multiboot crate helps us parse the multiboot data structures, including the provided modules, which contain the initrd. However, the initrd itself must be parsed manually, and the kernel should be able to load an arbitrary number of apps. To have more space in the kernel area, it is advisable to copy the initrd to a suitable location during initialization, and free the initrd memory area.

§Checklist

Init allocators with free memory from multiboot
Setup kernel page tables
Load applications from the initrd (copy code to user pages and create stack)
Setup a user page directory for every thread (kernel page tables can be shared)
Activate paging before running the first app
Test: Try writing to kernel memory

Module b2_pagingCopy item path