Dokumentation

Assignment 3: Paging

The goal of this assignment is to have basic paging functionality in StuBS.

In fact, StuBS already does paging (since it is required for x64 to work), hidden in longmode.asm using 2 MB huge pages identity mapping the first four gigabyte of physical memory. However, this is quite inflexible and rather unreadable (on purpose, obviously 😈). Hence, you should introduce a high[er]-level paging management and isolate user processes from each other.

In order to simplify the initialization, you may stick to the concept of a lower-half kernel: the virtual address space from 0x0 up to 64 MiB belongs to the kernel, everything above is user land.

Detecting Physical Memory

In order to create the data structures for paging, we first have to determine the available physical memory.

The BIOS offers mechanisms to retrieve a memory map of the system. However, we are not able to call these functions from long mode. Luckily, Multiboot compliant boot loaders (like GRUB, PXELINUX or – partially – even Qemu/KVM with the --kernel parameter) can perform this call for you before loading your kernel. You have to enable this feature in boot/multiboot/config.inc by setting the MULTIBOOT_MEMORY_INFO bit in the MULTIBOOT_HEADER_FLAGS.

The boot loader hands your kernel a pointer (via ebx) to a data structure with the required information – for your convenience, the parsing is already implemented in Multiboot::Memory, you don't have to do anything except calling Multiboot::getMemoryMap()!

With this information, you'll (theoretically) be able to create a list of free/unused memory blocks. Beware, however, that the regions may overlap and Multiboot::Memory::isAvailable() can even be contradictory. Always act defensively and give priority to memory marked as unavailable.

Please be aware, that the BIOS will not take the location of your kernel (the section.ld defines the symbols ___KERNEL_START___ and ___KERNEL_END___) or any initial ramdisk into account. Moreover, you should ignore the memory up to the first mega byte (0x0 – 0x00100000) and exclude the so-called ISA memory hole from 15 MiB (0x00F00000) to 16 MiB (0x00FFFFFF) from your list.

Page Frame Allocator

To ease the paging, it is essential to provide an allocator for (4 KiB) page frames with an interface allowing one to retrieve (and pass back) kernel (below 64 MiB) or user (above 64 MiB) page frames.

The allocator has to manage the available (unused) page frames, which in your case are initially identical to the unused physical memory. Since hardware nowadays can be equipped with several terabytes of memory, you have to employ an adequate data structure to be able to manage this almost arbitrary amount of pages – for example a linked list (or priority queue), managing a single continuous 4 KiB aligned page range in each entry. To simplify things and avoid a chicken-and-egg-problem, you are already provided with a malloc implementation in alloc.h utils/alloc.cc (however, its total capacity is just 4 MiB and should not be exceeded/increased).

Attention
Under no circumstances must the allocator handout a reserved page frame, nor must it provide the same page frame twice (unless it was passed back in between).
Note
You should verify the correctness of your page frame allocator before proceeding (or you might end up in debug hell), e.g. by writing (and checking) a predefined pattern to each free page returned by the allocator (within the first 4 GiB, of course, since longmode.asm doesn't map more memory).

Paging Data Structures

Although implementing the data structures for the 4-Level Paging may sound like a lot of work, a detailed look at the structure entries required for 4 KiB paging reveals a lot of similarities between the levels – with a lot of potential to reuse code.

There is no need to support huge pages (2 MiB / 1 GiB), nor do you have to support additional features like cache or protection keys. It is sufficient to enforce access privileges for a page (user mode, writeable and – for 7.5 ECTS – the non-executable bit, see below) on the lowest level only: in the page table entry. All other paging levels should have their access privilege bits set in such a way that they do not restrict read, write or execute access.

See also

Non-Exectuable (NX) Bit (7.5 ECTS)

On x64, it is possible to mark a page explicitly as (non-)executable, which can hugly improve the security of your system – and probably even assist you in detecting bugs during development.

Your data structures should be able to activate and utilize the NX bit as long as the hardware supports it.

Deployment

Test your paging code by creating a single kernel(-only) mapping: The kernel space (everything below 64 MiB) should be identity mapped (physical and virtual addresses are equal) with the first page (starting at address 0x0) as exception: You should not map this page to be able to easily detect NULL-pointer dereferencing issues.

Don't forget to include the I/O APIC & LAPIC addresses (which reside beyond the kernel space). It is also possible to remap them into kernel space, however, this has a lot of pitfalls on multi core systems and is therefore not recommended for this assignment.

After you've successfully activated your kernel mapping and verified the correct behavior of your applications, you are able to continue to isolate the threads: Each thread should have its own mapping that gets activated during a thread switch in the Dispatcher.

Attention
While it might be tempting for performance reasons to reuse (rather than duplicate) the paging data structures in multiple threads, for simplicity we strongly recommend using separate mappings with distinct page tables for each thread in this and upcoming assignments.

The initial stack pointer of every thread should always be the same virtual address (e.g., 0x8000 0000 0000), the page frame allocator will provide you the userspace memory for the stacks. You can use the previous kernel mapping as blue print.

Note
Although a page fault handler is not required (yet), it could still improve your debug experience if your interrupt_handler is able to handle page faults (especially since the cr2 register contains the faulted address...).