rust-kernel

# Rustbelt

**Rustbelt** is Tyler's hobby x86_64 kernel written in Rust. It started from
the 2nd edition of Philipp Oppermann's
[Writing an OS in Rust](https://os.phil-opp.com/) and keeps going past the end
of it. It boots in QEMU straight into **its own shell**: a user-mode program
that has a Unix feel with DOS touches. It offers `ls`, `cat`, pipes and
redirection, plus `dir`, `type`, `ver`, and drive letters like `C:` and `D:`.

Under the shell:
- **VGA text and serial output.** The kernel prints to the VGA text screen and
  to the serial port (COM1).
- **CPU exceptions.** It handles breakpoints, page faults, and double faults
  (on their own stack).
- **Timer and keyboard.** The timer drives an uptime clock and preemption. The
  PS/2 keyboard feeds a tty with cooked and raw modes.
- **Memory.** It walks and edits its own page tables. It has a kernel heap
  with a fixed-size-block allocator.
- **Multitasking.** It multitasks two ways: an **async/await executor** and
  **preemptive kernel threads**.
- **User programs.** Small Rust ELF binaries run in **ring 3** as processes,
  each with its own address space. Their memory is freed when they exit. They
  talk to the kernel through about 25 `syscall`s, numbered like Linux's:
  `read`, `write`, `open`, `stat`, `getdents64`, `pipe`, `uname`... Two are
  our own: `spawn` and `wait`.
- **Files.** Files live behind a Linux-style **VFS**: a ramfs at `/` and
  `/tmp`, and a **FAT32** partition mounted at `/mnt/disk0`. That partition is
  on a second **virtio-blk** disk, found by **PCI** enumeration with its
  **GPT/MBR** partitions parsed. The shell and its programs are loaded from
  that disk.

It has a `cargo test` suite that runs inside QEMU, and a headless self-test
that drives the shell with a script.

Most code follows the blog_os sources (MIT / Apache-2.0) closely, with extra
comments. Everything else is new: the serial mirroring, uptime clock, demo
features and scripts, and everything past chapter 12. That covers preemptive
threads, user mode, syscalls, ELF loading, the VFS, PCI, virtio-blk,
partitions, FAT32 and the shell.

![Rustbelt shell session: ls, cat with a drive letter, a pipe, run --trace](boot.png)

## What's installed (on this box)

| Tool | Version | Why |
|---|---|---|
| rustup | 1.29.2 | toolchain manager (in `~/.cargo/bin`, ahead of Debian's `/usr/bin/cargo`) |
| Rust nightly | rustc 1.101.0-nightly (2026-10-29) | custom JSON targets + `build-std` are nightly-only |
| `rust-src` component | – | source of `core`, recompiled for our bare-metal target |
| `llvm-tools-preview` component | – | `llvm-objcopy` etc., used by `bootimage` |
| `bootimage` (cargo subcommand) | 0.10.5 | links kernel + bootloader into a bootable disk image |
| QEMU (`qemu-system-x86`, `qemu-system-gui`) | 10.0.13 | the emulator we boot in (`-gui` adds the GTK/SDL window) |
| `dosfstools`, `mtools`, `fdisk` | Debian packages | `build.rs` makes the FAT32 test disk with `sfdisk` + `mkfs.vfat` + `mmd`/`mcopy` |

`rust-toolchain.toml` pins the project to nightly with the two components, so
`cargo` inside this directory picks them up automatically. It also installs
the built-in `x86_64-unknown-none` target, used to compile the user programs.

Crates: `bootloader` 0.9.35 (BIOS bootloader used by the 2nd edition),
`volatile` 0.2, `spin` 0.5, `x86_64` 0.15, `uart_16550` 0.3, `lazy_static` 1.5,
`pic8259` 0.11 (interrupt controller), `pc-keyboard` 0.7 (scancode decoding),
`linked_list_allocator` 0.9 (fallback heap allocator), `fatfs` (git, `no_std` +
`alloc`; FAT12/16/32 reading and writing).

Fresh setup on another machine:

```sh
curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | sh   # rustup
rustup toolchain install nightly -c rust-src -c llvm-tools-preview -t x86_64-unknown-none
cargo install bootimage
sudo apt install qemu-system-x86 qemu-system-gui dosfstools mtools fdisk
```

## Build and run

```sh
cargo bootimage                     # build -> target/x86_64-rust_kernel/debug/bootimage-rust_kernel.bin
cargo run                           # build + boot in a QEMU window; serial output also prints in the terminal
```

**Using it:** `cargo run` opens a QEMU window. The kernel prints a few boot
lines, then you're at the shell prompt `C:/ $`. Click into the window and type,
for example `help`, `cd D:`, `ls` or `cat readme.txt | wc`. See
[The shell](#the-shell-stage-7) for everything it can do. Everything on the
screen is also mirrored to your terminal over serial. Typing `exit` ends the
shell, and the kernel starts a fresh one.

To get the mouse and keyboard back from QEMU, press Ctrl+Alt+G. To quit, close
the window or press Ctrl+C in the terminal. Over SSH without X, use
`cargo run -- -display curses` to see the VGA screen right in your terminal,
and quit from another terminal with `pkill qemu-system`.

Headless (no window, good for SSH / scripts):

```sh
./scripts/run-headless.sh                 # boot, the shell runs disk/scripts/selftest.sh, QEMU exits;
                                          # passes if the shell exits 0 AND the expected lines appear
./scripts/run-headless.sh stack-overflow  # deliberately overflow the stack; passes if the double-fault handler catches it
./scripts/run-headless.sh page-fault      # write to unmapped 0xdeadbeaf; passes if the page-fault handler catches it
cargo run --features headless -- -display none                 # the self-test via cargo
                                          # (QEMU's exit status is 33 = success; cargo just reports it as non-zero)
cargo run --features demos                # the earlier stages' demos first, then the shell
./scripts/screenshot.sh [out.png] [session.txt] [expected...]
                                          # boot, type a shell session via QEMU monitor `sendkey`
                                          # (one command per line; {BS} = Backspace, {UP} = up arrow),
                                          # check the expected texts appear, save the VGA screen
                                          # (default: the session in boot.png); exits 1 if text is missing
```

Cargo features (in `Cargo.toml`):

| Feature | Effect |
|---|---|
| (none) | boot, start the shell on the console (the default) |
| `headless` | the shell runs `/mnt/disk0/scripts/selftest.sh` instead of reading the keyboard; its exit code becomes QEMU's (0 -> success); a 60 s timer safety net fails the run if it hangs; panics exit with failure |
| `demos` | before the shell: the breakpoint, paging and heap demos, threads A/B/C, the async example, and the `hello`/`evil`/`spin`/`demo` programs of stages 2-6 |
| `stack-overflow` | after boot, recurse forever to test the double-fault handler (with `headless`: exit success when caught) |
| `page-fault` | after boot, write to unmapped address `0xdeadbeaf` (with `headless`: exit success when caught) |

Expected serial output of `./scripts/run-headless.sh`. Boot is quick now
that the demos are behind a feature; most of the output is the shell running
`disk/scripts/selftest.sh`. Each command is echoed after its prompt. The
`[process] started/exited` lines are the kernel's own log. They go to serial
only, so the VGA screen shows just the shell session (and kernel messages
such as a killed process).

```
Rustbelt 0.7.0 -- a hobby x86_64 kernel in Rust
[pci] 00:00.0 8086:1237 host bridge
... (7 PCI devices)
[pci] 7 devices on the PCI bus
[disk] vda: virtio-blk, 131072 sectors (64 MiB)
[disk] vda: GPT partition table, 1 partition(s)
[disk] vda1: start 2048 sectors 126976 type Microsoft basic data (FAT/exFAT/NTFS) name "fat32"
[disk] vda1: FAT32 volume "TYLERDISK" mounted at /mnt/disk0
[vfs] mounted ramfs at /
[vfs] mounted ramfs at /tmp
[vfs] mounted fat32 at /mnt/disk0
C:/ $ ver
Rustbelt 0.7.0 (stage 7: shell) x86_64
C:/ $ drives
C:  /            ramfs
D:  /mnt/disk0   fat32
C:/ $ pwd
/
C:/ $ cd D:
D:/ $ ls
[process] started pid 2 (ls), entry 0x8000402c00
bin/        notes/      readme.txt  scripts/
[process] pid 2 (ls) exited with code 0
D:/ $ ls -l notes
[process] started pid 3 (ls), entry 0x8000402c00
       125  todo.txt
[process] pid 3 (ls) exited with code 0
D:/ $ type D:/readme.txt
[process] started pid 4 (cat), entry 0x8000400260
Hello from the FAT32 disk! This file lives on a virtio-blk disk, in a GPT
partition, in a FAT32 file system -- read through the kernel's VFS.
In the Rustbelt shell this disk is drive D: -- try `cd D:` and `ls`.
[process] pid 4 (cat) exited with code 0
D:/ $ cat d:notes/todo.txt | grep -i EXT | wc -l
[process] started pid 5 (cat), entry 0x8000400260
[process] started pid 6 (grep), entry 0x8000400610
[process] pid 5 (cat) exited with code 0
[process] started pid 7 (wc), entry 0x8000400260
[process] pid 6 (grep) exited with code 0
1
[process] pid 7 (wc) exited with code 0
D:/ $ dir bin | wc -l
[process] started pid 8 (ls), entry 0x8000402c00
[process] started pid 9 (wc), entry 0x8000400260
[process] pid 8 (ls) exited with code 0
15
[process] pid 9 (wc) exited with code 0
D:/ $ echo first line > C:/tmp/out.txt
D:/ $ echo second line >> /tmp/out.txt
D:/ $ cat < /tmp/out.txt
[process] started pid 10 (cat), entry 0x8000400260
first line
second line
[process] pid 10 (cat) exited with code 0
D:/ $ md /tmp/work
[process] started pid 11 (mkdir), entry 0x8000400100
[process] pid 11 (mkdir) exited with code 0
D:/ $ copy D:/notes/todo.txt /tmp/work
[process] started pid 12 (cp), entry 0x8000400670
[process] pid 12 (cp) exited with code 0
D:/ $ touch /tmp/work/empty.txt
[process] started pid 13 (touch), entry 0x8000400100
[process] pid 13 (touch) exited with code 0
D:/ $ ls -l C:/tmp/work
[process] started pid 14 (ls), entry 0x8000402c00
         0  empty.txt
       125  todo.txt
[process] pid 14 (ls) exited with code 0
D:/ $ del /tmp/work/todo.txt /tmp/work/empty.txt /tmp/work
[process] started pid 15 (rm), entry 0x8000400100
[process] pid 15 (rm) exited with code 0
D:/ $ grep "D:" readme.txt
[process] started pid 16 (grep), entry 0x8000400610
In the Rustbelt shell this disk is drive D: -- try `cd D:` and `ls`.
[process] pid 16 (grep) exited with code 0
D:/ $ alias ll="ls -l"
D:/ $ ll C:/tmp
[process] started pid 17 (ls), entry 0x8000402c00
        23  out.txt
[process] pid 17 (ls) exited with code 0
D:/ $ run --trace cat D:/notes/todo.txt
[process] started pid 18 (cat), entry 0x8000400260
[trace 18] open("/mnt/disk0/notes/todo.txt", 0o0) = 3
[trace 18] read(3, "Done: the shell (cd, ls, cat, run, start"..., 512) = 125
Done: the shell (cd, ls, cat, run, start, pipes, redirection, drive letters).
Next: more file systems -- ext2, exFAT, btrfs.
[trace 18] write(1, "Done: the shell (cd, ls, cat, run, start"..., 125) = 125
[trace 18] read(3, "", 512) = 0
[trace 18] close(3) = 0
[trace 18] exit(0)
[process] pid 18 (cat) exited with code 0
D:/ $ start sleep 1
[process] started pid 19 (sleep), entry 0x8000400000
[pid 19] sleep started in the background
D:/ $ jobs
[pid 19] running  start sleep 1
D:/ $ wait
[process] pid 19 (sleep) exited with code 0
[done] pid 19 (start sleep 1), exit code 0
D:/ $ run evil
[process] started pid 20 (evil), entry 0x80004000f0
[evil] pid 20: reading kernel memory at 0x200000...
[kernel] user page fault: address Ok(VirtAddr(0x200000)), error PageFaultErrorCode(PROTECTION_VIOLATION | USER_MODE)
[kernel] page fault in user mode at rip 0x800040017e
[process] pid 20 (evil) killed: page fault
[exit code 139]
D:/ $ nosuchprogram
sh: nosuchprogram: command not found (try `help`)
D:/ $ cd Q:
cd: there is no drive Q: (see `drives`)
D:/ $ cd C:/tmp
C:/tmp $ pwd
/tmp
C:/tmp $ exit 0
[process] pid 1 (sh) exited with code 0
[ok] shell self-test finished: Exited(0)
[memory] 10 frames in use
[run-headless] all 14+2 expected shell lines found
[run-headless] kernel exited OK
```

The run ends with `[memory] 10 frames in use`, even though 20 processes have
come and gone. That shows exited processes give their page tables, code and
stacks back.

The kernel boots from the bootimage on the first (IDE) disk; the scripts and
`Cargo.toml` attach a **second** disk, `target/disk.img`, as
`-drive file=target/disk.img,format=raw,if=virtio,snapshot=on`. `snapshot=on`
makes QEMU throw away writes when it exits, so every boot and every test sees
the same fresh image even though the kernel writes to it.

## Tests

```sh
cargo test                        # everything (lib unit tests + tests/*.rs), each booted in QEMU headless
cargo test --lib                  # just the unit tests inside src/
cargo test --test heap_allocation # one integration test
```

Each test binary is its own little kernel: `bootimage runner` boots it with the
`test-args` from `Cargo.toml` (no display, serial to stdout, isa-debug-exit) and
treats QEMU exit code 33 as a pass. Output looks like:

```
Running 5 tests
heap_allocation::large_allocation_uses_fallback...  [ok]
heap_allocation::large_vec...                       [ok]
heap_allocation::many_boxes...                      [ok]
heap_allocation::many_boxes_long_lived...           [ok]
heap_allocation::simple_allocation...               [ok]
```

| Test | What it checks |
|---|---|
| lib (`src/*.rs` `#[test_case]`s) | trivial assertion, breakpoint handler returns, VGA `println!` writes the right cells |
| `tests/basic_boot.rs` | printing works straight after boot, before any `init()` |
| `tests/heap_allocation.rs` | Box, big Vec, 100 K short-lived boxes (memory reuse), same with one long-lived box, >2 KiB fallback allocation |
| `tests/should_panic.rs` | a failing `assert_eq!` reaches the panic handler (`harness = false`) |
| `tests/stack_overflow.rs` | stack overflow lands in the double-fault handler on the IST stack (`harness = false`) |
| `tests/executor.rs` | `SimpleExecutor` runs an async fn to completion; the waker-based `Executor` interleaves two tasks that `yield_now().await` (a1 b1 a2 b2 a3 b3) |
| `tests/shell.rs` | **the shell**: tokenizer (operators without spaces, quotes, comments), parser (pipelines, `<` `>` `>>`, `&`, error cases), drive-letter assignment from a mount table, `D:/x` -> `/mnt/disk0/x` translation and back for the prompt; then the real `/bin/sh` runs a script (cd with a drive letter, ls, a pipe, `>`/`>>`/`<`, `ver`, `exit 3`) with its stdout in a pipe and the output is checked; background jobs (`start`, `jobs`, `wait`); 20 processes started and reaped leave `frames_in_use` unchanged |
| `tests/user_mode.rs` | programs loaded from the FAT disk: `hello` exits 0, `demo` passes all its checks (exit 0), `evil` is killed with code 139, `spin` is preempted; spawn with arguments + trace + exit code 7, then reaped; a child's stdout into a pipe; spawn errors (`ENOENT`, `ENOEXEC`, `EISDIR`, `ECHILD`); `wait` with `WNOHANG` returns `EAGAIN` while the child runs; ELF loader rejects garbage; user pointers give `EFAULT` (length 0 is fine); `sleep` blocks for the right number of ticks; a `WaitQueue` wakes its waiter |
| `tests/vfs.rs` | read `/hello.txt` to EOF, path normalisation (`.`, `..`, relative to a cwd), `ENOENT`/`ENOTDIR`/`EINVAL`/`EISDIR`/`EEXIST`, `/tmp` is a separate ramfs, longest-prefix mounts, sparse writes zero-fill, listing, remove (`ENOTEMPTY`, `EBUSY` on mount points), seek/stat/truncate, `getdents64` record layout, pipes pass bytes and report EOF / `EPIPE` |
| `tests/block.rs` | PCI scan finds the virtio disk; sector 1 of the image is the GPT header; multi-sector reads equal single-sector reads; write + read back; out-of-range and partial-sector requests fail; the GPT partition is registered as `vda1` (with a FAT32 boot sector); MBR parsing on a RAM disk |
| `tests/fat.rs` | the FAT32 volume is mounted at `/mnt/disk0` with the expected files (`bin`, `notes`, `readme.txt`, `scripts`); read `readme.txt`; every program in `bin/` is a valid ELF; create/write/read/truncate/remove a 10 KB file; directories with long names, `ENOTEMPTY`; the `BlockIo` adapter handles unaligned reads and writes |
| `tests/threads.rs` | two busy-looping threads that never yield both make progress while the main thread busy-waits too (only possible with preemption); a thread can exit and the others keep running |

How it works: `#![feature(custom_test_frameworks)]` collects every `#[test_case]`
function and passes them to `rust_kernel::test_runner` (in `src/lib.rs`), which
prints each name to serial, runs it, prints `[ok]`, then exits QEMU with success.
A panic goes to `test_panic_handler`, which prints `[failed]` and exits with failure.

Extra args after `--` in `cargo run -- ...` are appended to the QEMU command
line, e.g. `cargo run -- -d int -no-reboot` to log every interrupt and stop on
triple faults, or `cargo run -- -s -S` to wait for `gdb` on port 1234.

## Project layout

```
.cargo/config.toml        build-std (core, alloc) + custom target + scripts/runner.sh as the cargo runner
rust-toolchain.toml       pin nightly + rust-src + llvm-tools-preview
x86_64-rust_kernel.json   custom target: no OS, no red zone, soft-float, abort on panic, rust-lld
Cargo.toml                deps, features, test settings, QEMU run/test args
src/lib.rs                the kernel library: module list, init(), kprintln!, test framework, exit_qemu
src/main.rs               the bootable binary: kernel_main (init, then a thread that runs the shell and
                          restarts it when it exits), the `demos` feature's demos, panic handler
src/gdt.rs                GDT (kernel + user segments) + TSS (double-fault IST stack, rsp0 per thread)
src/interrupts.rs         IDT; breakpoint / page fault / GPF / invalid opcode / double fault handlers
                          (faults from ring 3 kill the process); 8259 PIC;
                          timer handler (uptime, ticks, calls the thread scheduler),
                          keyboard handler (just queues the scancode)
src/memory.rs             OffsetPageTable setup from CR3, example mapping, BootInfoFrameAllocator,
                          global frame allocator + free list, per-process address spaces (and freeing
                          them), user pointer checks
src/allocator.rs          heap location/size, init_heap (maps heap pages), #[global_allocator], Locked<A>
src/allocator/bump.rs     bump allocator (not active, for learning)
src/allocator/fixed_size_block.rs  fixed-size-block allocator (ACTIVE), falls back to linked_list_allocator
src/task/mod.rs           async: Task (pinned boxed future + id), yield_now()
src/task/simple_executor.rs  first executor: polls every task in a loop (no wakers)
src/task/executor.rs      real executor: task queue + wakers, sleeps with hlt when idle
src/task/keyboard.rs      lock-free scancode queue, ScancodeStream, async keyboard task (keys -> tty)
src/thread.rs             preemptive threads: spawn, round-robin schedule(), asm context switch,
                          per-thread kernel stack (TSS.rsp0) + CR3 switching
src/syscall.rs            syscall/sysret MSR setup, asm entry stub, dispatch + all syscalls (table at the top)
src/process.rs            Process (pid, parent, cwd, args, fd table, exit status), spawn from a path or
                          ELF bytes, iretq into ring 3, exit/kill, wait (reaping)
src/pci.rs                PCI bus scan through config ports 0xCF8/0xCFC, device names
src/block/mod.rs          BlockDevice trait, device registry (vda, vda1...), RamDisk (for tests)
src/block/virtio_blk.rs   legacy virtio-blk driver: one virtqueue, polled, bounce buffer
src/block/partition.rs    MBR + GPT parsing, Partition = a BlockDevice window onto its disk
src/elf.rs                minimal ELF64 loader (PT_LOAD segments -> user pages)
src/errno.rs              Linux errno numbers
src/tty.rs                console line discipline (cooked: echo + line editing; raw: every key, arrows
                          as escape sequences) + Console (the File behind fds 0/1/2)
src/fs/mod.rs             VFS: Inode + FileSystem traits, mount table, path normalize/lookup/create/remove,
                          init (boot files), mount_disks (FAT partitions -> /mnt/diskN)
src/fs/file.rs            File trait (what an fd points to), InodeFile (inode + offset), Stat, getdents64
src/fs/ramfs.rs           in-memory filesystem
src/fs/fat.rs             FAT32 via the fatfs crate: BlockIo adapter + FatFs/FatInode for the VFS
src/fs/pipe.rs            pipes: a byte queue with a blocking read end and a write end
build.rs                  compiles user/*.rs to ELF files, then builds target/disk.img (GPT + FAT32)
disk/                     files copied onto the FAT32 disk (readme.txt, notes/todo.txt,
                          scripts/selftest.sh = the headless shell session)
user/ulib.rs              tiny user-space "libc": syscall wrappers, println!/eprintln!, a 64 KiB heap
                          (Vec/String), line reading, strerror, _start, panic handler
user/link.ld              linker script for user programs (base 0x80_0040_0000)
user/sh.rs                the shell: line editor, builtins, aliases, PATH, pipes, redirection, jobs
user/shparse.rs           the shell's parser + drive letters (also compiled into tests/shell.rs)
user/{ls,cat,wc,grep,mkdir,rm,touch,cp,sleep}.rs   the shell's tools
user/{hello,evil,spin,demo,child}.rs  test/demo programs (all programs go to /mnt/disk0/bin)
src/vga_buffer.rs         VGA text-mode writer, print!/println!, print_at (status line), backspace
src/serial.rs             COM1 UART writer + serial_print!/serial_println!
tests/                    integration tests, one QEMU-booted kernel each
scripts/runner.sh         `cargo run`/`cargo test` runner: `bootimage runner` + stale-image fix
scripts/run-headless.sh   headless boot + shell self-test, timeout, exit-code and output checks
scripts/screenshot.sh     headless boot + a typed shell session + PNG screenshot via QEMU monitor
boot.png                  screenshot of the VGA screen (a shell session)
```

## What the interrupt code does (chapters 5-7)

- **CPU exceptions / IDT** (`interrupts.rs`): the IDT maps vector numbers to handler
  functions written with `extern "x86-interrupt"` (nightly `abi_x86_interrupt`), so
  the compiler saves all registers and returns with `iretq`. `_start` fires an
  `int3` on purpose; the breakpoint handler prints the stack frame and execution
  continues. A page-fault handler prints the faulting address from CR2.
- **Double faults** (`gdt.rs`): a stack overflow hits the guard page -> page fault ->
  the CPU can't push the exception frame on the broken stack -> double fault ->
  same again -> *triple fault* = machine reset. We load our own GDT containing a
  TSS whose Interrupt Stack Table entry 0 points at a separate 20 KiB static stack,
  and mark the double-fault IDT entry to use it. Try `./scripts/run-headless.sh stack-overflow`.
- **Hardware interrupts**: the two 8259 PICs are remapped to vectors 32-47 (0-31 are
  CPU exceptions) and then `sti` enables interrupts. The timer (IRQ 0, ~18.2 Hz)
  bumps an atomic tick counter and redraws the uptime clock; the keyboard (IRQ 1)
  reads the scancode from port 0x60 and queues it; an async task decodes it with
  `pc-keyboard` (US layout, scancode set 1) and echoes it (see Multitasking below). Each handler must send End-Of-Interrupt to the
  PIC or no further interrupts arrive. `print!`/`serial_print!` disable interrupts
  while holding their lock, otherwise an interrupt handler printing while
  `_start` holds the lock would deadlock. The idle loop uses `hlt`, so QEMU
  doesn't burn a host CPU core.

## Memory (chapters 8-11)

**Paging.** Every address the kernel uses is *virtual*. The CPU translates it with
a 4-level page table tree (level 4 -> 3 -> 2 -> 1 -> 4 KiB page); 9 bits of the
address index each level, the low 12 bits are the offset in the page. CR3 holds the
*physical* address of the level-4 table (here `0x1000`). The `page-fault` feature
writes to `0xdeadbeaf`, which no table maps, and the page-fault handler reports
the address (from CR2) and the reason (`CAUSED_BY_WRITE`, not `PROTECTION_VIOLATION`
-> the page simply isn't present).

**Reaching page tables.** Page tables contain physical addresses, but we can only
dereference virtual ones. With the bootloader's `map_physical_memory` feature, all of
physical RAM is also mapped at `physical_memory_offset` (`0x18000000000` here), so
`virt = offset + phys`. `memory::init` wraps that in the x86_64 crate's
`OffsetPageTable`, which can `translate_addr` (walk the tables) and `map_to` (add entries).

**Virtual memory layout** (as set up by bootloader 0.9 in this build):

| Virtual address | What |
|---|---|
| `0xb8000` | VGA text buffer (identity-mapped: virt = phys) |
| `0x200000`... | kernel code + data (the ELF; maps to phys around `0x400000`) |
| `0x0100_0000_0000`... | kernel stack (80 pages, guard page below it) |
| `0x0180_0000_0000`... | all physical memory (`physical_memory_offset`) |
| `0x4444_4444_0000` | kernel heap, 4 MiB (also holds thread stacks) (we map it in `allocator::init_heap`) |
| `0xdead_beaf_000` | demo page we map to the VGA frame (writes "New!" on screen) |

The "New!" demo writes to screen row 20 through the new mapping; by the time you look,
later lines have scrolled it up, so in `boot.png` it overwrote the start of the first line.

**Physical frames.** `BootInfoFrameAllocator` hands out 4 KiB frames from the regions
the BIOS memory map marks `Usable` (~121 MiB of QEMU's default 128 MiB). It never frees;
fine for now.

**Heap.** `allocator::init_heap` maps the 1024 pages (4 MiB) of `HEAP_START..+HEAP_SIZE` to fresh
frames, then gives the range to the `#[global_allocator]`. From then on the `alloc`
crate (`Box`, `Vec`, `Rc`, `String`, `BTreeMap`...) works. `alloc` is compiled for our
target by `build-std` in `.cargo/config.toml`.

**Allocator designs** (`src/allocator/`): the *bump* allocator just moves a pointer
forward and can only reclaim memory when every allocation is freed (it fails the
`many_boxes_long_lived` test). The `linked_list_allocator` crate keeps a list of free
regions (first fit, slower, but reuses any freed memory). The active
*fixed-size-block* allocator rounds each request up to 8/16/.../2048 bytes and keeps
one free list per size, so alloc/free are O(1) pops/pushes; bigger requests and empty
lists fall back to the linked-list allocator. Switch allocators by editing one line in
`src/allocator.rs`.

## Multitasking (async/await + threads)

### Cooperative: async/await (`src/task/`, phil-opp chapter 12)

An `async fn` compiles into a state machine (a `Future`). An *executor* calls
`poll` on it; the future runs until it has to wait, then returns `Pending` and
remembers a `Waker`. Whoever makes progress possible later (here: the keyboard
interrupt) calls `waker.wake()`, which puts the task's id back into the
executor's queue. When the queue is empty, the executor `hlt`s -- carefully:
it disables interrupts, checks the queue, and then uses `sti; hlt` as one step
(`enable_and_hlt`), so a wakeup arriving in between can't be missed.

The keyboard interrupt handler now does almost nothing: read the scancode from
port 0x60 and push it into a fixed-size lock-free queue (`crossbeam_queue::ArrayQueue`),
then wake the keyboard task (`futures_util::task::AtomicWaker`). No locks in the
interrupt handler means no deadlock if the interrupt arrives while the task
holds one. The task (`print_keypresses`) is an `async` loop over a
`ScancodeStream` that decodes and echoes characters.

"Cooperative" means a task only gives up the CPU at an `.await`. A task that
loops forever without awaiting freezes every other task. Upside: switching is
cheap (just return from `poll`), and all tasks share one stack.

### Preemptive: kernel threads (`src/thread.rs`, beyond the blog series)

Each thread has its own 64 KiB stack (a `Vec<u8>` on the heap). On every timer
interrupt (~18 times a second) the handler sends the EOI to the PIC and then
calls `thread::schedule()`, which picks the next thread round-robin and calls
`switch_context(&mut old.rsp, new.rsp)` (a dozen lines of `global_asm!`):

```
push rbp, rbx, r12, r13, r14, r15   ; callee-saved regs of the OLD thread, onto its stack
mov  [rdi], rsp                     ; remember where the old stack ends
mov  rsp, rsi                       ; ---- now on the NEW thread's stack ----
pop  r15, r14, r13, r12, rbx, rbp   ; its callee-saved regs
ret                                 ; return to wherever IT called switch_context
```

Why only those six registers? `switch_context` is called like a normal
function, so the compiler already saved the caller-saved registers, and the
`x86-interrupt` handler around it saved everything the interrupted code was
using (plus the CPU pushed RIP/RSP/RFLAGS). So a paused thread's complete
state sits on its own stack; the scheduler only stores its `rsp`. The new
thread "returns" from `schedule()`, from its timer handler, and `iretq`s back to
where it was interrupted.

A brand-new thread was never interrupted, so `spawn` hand-builds a stack that
looks as if `switch_context` had saved it: six register slots (r12 = the
thread's function) and a return address pointing to `thread_trampoline`, which
moves r12 into rdi and calls `thread_start(entry)`. That re-enables interrupts
(we arrive from inside the timer interrupt, where they're off), runs the
function, and marks the thread finished when it returns. The code that booted
the kernel becomes thread 0, "main", which runs the async executor.

Preemption means even `loop {}` can't hog the CPU (thread C in the demo is a
pure busy loop). The price: any code can be interrupted anywhere, so shared
data needs locks, and a lock that the timer handler might also want must be
taken with interrupts disabled. Here: the print macros and `print_at` already
hold their spinlocks with interrupts off (`without_interrupts`), so a thread
can't be switched away while holding them; the scheduler lock is only taken
with interrupts off and is released *before* switching (the next thread would
otherwise wait forever for a lock held by a paused thread).

**The locking rule:** a lock that is *ever* taken with interrupts off must
*always* be taken with interrupts off. Otherwise: thread T takes the lock with
interrupts on, gets preempted, and some code running with interrupts off (so
it can never be preempted back to T) spins on that lock forever. Stage 6 hit
exactly this with the heap allocator: wait-queue code runs with interrupts off
and allocates, so `GlobalAlloc::alloc`/`dealloc` now take the heap lock inside
`without_interrupts`.

**Blocking (stage 6).** A thread can be *blocked*: the scheduler skips it until
someone wakes it. Two ways to be woken:

- `sleep_ticks(n)` sets `wake_at = now + n`; `schedule()` (run on every timer
  tick) unblocks it once that tick has passed (the `sleep_ms` syscall rounds
  up to 55 ms ticks).
- A `WaitQueue` (a list of waiting thread ids). `wait_until(|| condition)`
  turns interrupts off, checks the condition, and if it's false puts the
  thread on the queue, marks it blocked and switches away; when woken it checks
  again. `wake_all()` unblocks everyone on the queue. Checking with interrupts
  off is what prevents a *lost wakeup* (the event firing between "check" and
  "sleep"). Users: the console (`read(0)` waits for Enter; the keyboard path
  wakes it), pipes (reader waits for data or EOF) and `wait(pid)` (parent
  waits on the child's `exited` queue).

If every thread is blocked, the scheduler idles with `sti; hlt` until an
interrupt makes something runnable.

**Stack size and the canary.** Stage 6 first used 16 KiB stacks and crashed
with a ring-0 jump to address 0: the syscall -> VFS -> FAT -> ELF loader path in
an unoptimized debug build used more than that, overflowed into the heap and
smashed a neighbour. Now stacks are 64 KiB, and the lowest 8 bytes of each
hold a canary value (`0x5AFE_57AC_C0DE_CAFE`). `schedule()` checks it on every
switch and panics with "kernel stack overflow in thread" if it changed: a
cheap stand-in for a real guard page. Finished threads' stacks are freed (the
next `spawn` drops them, since a thread can't free the stack it's running on).

Known simplifications (good exercises): no guard page under thread stacks (the
canary only catches overflows after the fact); no priorities; a single CPU,
so `spin::Mutex` is enough.

## User mode, syscalls and processes

The user programs in `user/` run in **ring 3** as separate processes, each
with its own address space and file-descriptor table. The shell and its
tools are described in [The shell](#the-shell-stage-7). These are the test
and demo programs from stages 5 and 6 (run them from the shell: `run hello`,
`run evil`...):

| Program | What it does |
|---|---|
| `hello` | prints "Hello from user mode!", `getpid`, reads `/hello.txt` from the ramfs, creates and reads back `/tmp/note.txt`, checks error cases (`ENOENT`, `EBADF`, `EFAULT`, `ENOSYS`), exits with the number of failed checks (0) |
| `evil` | reads kernel memory at `0x200000` -> page fault in ring 3 -> the kernel kills it and keeps going |
| `spin` | busy-loops ~2 s with no syscalls; it still gets preempted (threads A/B/C keep printing) |
| `demo` | stage 6 checks: cwd, reads `/mnt/disk0/readme.txt`, `stat`/`fstat`/`lseek`, lists `bin/` with `getdents64`, `chdir` errors, `mkdir`/`unlink`/`rmdir` on ramfs and FAT, a pipe from a child, arguments, `wait` exit codes (42, 139 for killed `evil`), `ECHILD`/`ENOENT`/`ENOEXEC`, `sleep_ms`; exits with the number of failed checks |
| `child` | helper for `demo` and tests: `child pipe` writes a line to stdout, `child cat` copies stdin to stdout, `child 42` exits with 42, otherwise prints its arguments |

All of them are read from `/mnt/disk0/bin/`, on the FAT32 partition of the
virtio disk; they're not compiled into the kernel any more.

### Rings in one paragraph

The CPU's *current privilege level* (CPL) is the low 2 bits of the CS register:
0 = kernel, 3 = user. In ring 3 the CPU refuses privileged instructions (`hlt`,
`cli`, writing CR3, `in`/`out`...) and refuses to touch any page whose page-table
entries lack the `USER_ACCESSIBLE` bit. User code can only get back into ring 0
through doors the kernel set up: interrupts/exceptions (via the IDT) and the
`syscall` instruction (via the LSTAR MSR). Every such door switches to a kernel
stack, so a user program can't corrupt kernel state through its own stack pointer.

### GDT and TSS (`src/gdt.rs`)

```
0x00 null
0x08 kernel code (ring 0)       0x10 kernel data (ring 0)
0x18 user data   (ring 3) |3    0x20 user code   (ring 3) |3
0x28 TSS (16 bytes: two slots)
```

The odd order (user *data* before user *code*) is forced by `sysret`: it loads
SS = STAR[63:48] + 8 and CS = STAR[63:48] + 16, so the two user segments must
be adjacent in that order. The TSS has two jobs: IST[0] is the double-fault
stack (stage 2), and **`rsp0`** is the stack the CPU switches to when an
interrupt arrives while in ring 3. Each thread has its own kernel stack, so the
scheduler writes the next thread's stack top into `TSS.rsp0` on every switch
(`gdt::set_kernel_stack`).

### The syscall path (`src/syscall.rs`)

`syscall` was chosen over `int 0x80`: it's what Linux uses on x86_64, it's
faster, and the setup is only four MSRs. The catch is that, unlike an
interrupt, `syscall` does **not** switch stacks -- the entry code must.

Setup (`syscall::init`): `EFER.SCE = 1` (enable), `STAR` = the selectors above,
`LSTAR` = address of `syscall_entry`, `SFMASK = IF|DF|TF` (so we enter with
interrupts off until we're on a kernel stack).

One call, step by step:

1. User code puts the number in `rax`, args in `rdi, rsi, rdx` (Linux ABI; we
   also save `r10, r8, r9`) and executes `syscall`.
2. CPU: `rcx` = user RIP, `r11` = user RFLAGS, CS/SS = kernel, RFLAGS &= ~SFMASK,
   RIP = LSTAR. RSP is still the *user* stack.
3. `syscall_entry` (asm): stash user RSP in a global, load this thread's kernel
   stack top (set by the scheduler), push user RSP, `rcx`, `r11` and the args.
4. Shuffle into the C ABI and call `dispatch(nr, a1..a5)` in Rust with
   interrupts re-enabled (so a long syscall, e.g. a blocking `read`, can be preempted).
5. `dispatch` validates user pointers (`user_slice`: range must be inside the
   user half *and* mapped with `USER_ACCESSIBLE` in the current page table),
   runs the call, and returns a value or `-errno` in `rax`.
6. `cli`, pop everything back, restore user RSP, `sysretq` (RIP = rcx,
   RFLAGS = r11, CPL = 3).

Single CPU, so the "current kernel stack" and "saved user RSP" are plain
globals; SMP kernels use per-CPU data reached with `swapgs`.

Numbers are Linux's wherever Linux has the same call, so man pages and
`strace` habits mostly apply. Args 4 and 5 go in `r10` and `r8` like Linux.

| nr | name | args | notes |
|---|---|---|---|
| 0 | `read` | fd, buf, len | console: blocks until Enter; pipe: blocks until data or EOF |
| 1 | `write` | fd, buf, len | console = VGA + serial; pipe: `EPIPE` once the reader is gone |
| 2 | `open` | path, path_len, flags | `O_CREAT` 0o100, `O_TRUNC` 0o1000, `O_APPEND` 0o2000 (every write goes to the end: `>>`); directories can be opened (for `getdents64`) |
| 3 | `close` | fd | |
| 4 | `stat` | path, path_len, *Stat | |
| 5 | `fstat` | fd, *Stat | |
| 8 | `lseek` | fd, offset, whence | `SEEK_SET/CUR/END` = 0/1/2; `ESPIPE` on console/pipes |
| 16 | `ioctl` | fd, request, arg | only `TTY_SET_RAW` (1): console raw mode on (arg 1) / off (0); returns the old mode, `ENOTTY` if fd isn't the console |
| 22 | `pipe` | *[u32; 2] | [read end, write end] |
| 24 | `sched_yield` | | |
| 35 | `sleep_ms` | ms | **ours**: Linux nr 35 is `nanosleep(timespec)` |
| 39 | `getpid` | | |
| 60 | `exit` | code | |
| 61 | `wait` | pid, flags | **simpler than Linux `wait4`**: blocks, returns the exit code (139 = killed, like a shell shows SIGSEGV), reaps the child (freeing its memory); `ECHILD` if not your child; flags `WNOHANG` (1): don't block, `EAGAIN` while it's still running |
| 63 | `uname` | *utsname | Linux's struct: 6 NUL-padded 65-byte fields: "Rustbelt", "qemu", "0.7.0", "stage 7: shell", "x86_64", "(none)" |
| 79 | `getcwd` | buf, len | returns the length (no NUL); `ERANGE` if too small |
| 80 | `chdir` | path, path_len | per-process cwd, inherited by spawned children |
| 83 | `mkdir` | path, path_len | |
| 84 | `rmdir` | path, path_len | empty directories only (`ENOTEMPTY`); `EBUSY` on a mount point |
| 87 | `unlink` | path, path_len | files only (`EISDIR`) |
| 217 | `getdents64` | fd, buf, len | real Linux `struct linux_dirent64` records (ino, off, reclen, type, name\0) |
| 500 | `spawn` | path, path_len, argv, argv_len, *SpawnOptions | **ours**: start a program, returns its pid |
| 501 | `mounts` | buf, len | **ours** (Linux reads `/proc/mounts`): the mount table as text, one `path fstype` line per mount, in mount order; returns the length, `ERANGE` if too small. The shell assigns drive letters from it |

Deviations from Linux worth knowing:

- **Paths are pointer + length**, not NUL-terminated C strings (easier to
  validate, and Rust `&str`s aren't NUL-terminated). Relative paths start at
  the process's cwd; `.` and `..` are resolved in the kernel (`fs::normalize`).
- **`Stat` is tiny**: `#[repr(C)] struct Stat { kind: u64, size: u64 }`, kind
  1 = file, 2 = directory, 3 = console, 4 = pipe. No inode numbers, owners,
  modes or times yet.
- **spawn instead of fork + exec.** `fork` copies the whole address space (or
  needs copy-on-write page tables to be fast) and `exec` immediately throws the
  copy away. `spawn` does the useful part in one step, like Windows
  `CreateProcess` or POSIX `posix_spawn`. What Unix shells do between fork and
  exec -- pointing fds 0/1/2 at a pipe or a file -- is spawn's `SpawnOptions`:
  `{ stdin, stdout, stderr: i64 (one of *my* fds, -1 = same as mine), flags }`.
  `flags = SPAWN_TRACE` (1) prints every syscall the child makes, as
  `[trace pid] open("notes/todo.txt", 0o0) = 3` in strace style (strings
  shown, errors as `-2 ENOENT`), which is what the shell's `run --trace`
  uses. fork + exec could still be added later.
- **argv** is passed as one buffer with NUL-separated arguments
  (`"child\0with\0three args"`; empty = just the program name). The kernel
  copies the strings onto the new process's stack and starts `_start` with
  `rdi = argc`, `rsi = pointer to argc [ptr, len] pairs` (Rust-friendly
  slices instead of C's `char **argv`). `ulib` wraps that as `argc()`/`arg(i)`.

Errors are negative errno values like Linux (`-2` ENOENT, `-9` EBADF, `-14`
EFAULT, `-38` ENOSYS...). Unknown numbers return `-ENOSYS`.

### Address spaces (`src/memory.rs`, `src/process.rs`)

Each process gets a fresh level-4 page table. The kernel's L4 entries are
**copied** into it (so the kernel, heap, physical-memory map and thread stacks
are mapped in every address space and the kernel keeps working after a CR3
switch), and L4 slot 1 is the process's own:

```
0x0000_0000_0020_0000   kernel code (bootloader 0.9 puts it here)        shared, ring 0 only
0x0000_0080_0000_0000   USER_START (L4 slot 1)                           per process
0x0000_0080_0040_0000     program (.text R-X, .rodata R--, .data/.bss RW-)
0x0000_00ff_ffff_b000     user stack (16 KiB, RW-, grows down)
0x0000_0100_0000_0000   USER_END
0x0000_0100_0020_0000   boot stack (L4 slot 2)                           shared
0x0000_0180_0000_0000   all physical memory (phys_mem_offset, slot 3)    shared
0x0000_4444_4444_0000   kernel heap (thread kernel stacks live here)     shared
```

Real kernels put the kernel in the upper half (`0xffff_8000_...`) and give
user space the whole lower half. With bootloader 0.9 the kernel sits low, so
here user space is one 512 GiB slot that the kernel doesn't use. Only user
pages have `USER_ACCESSIBLE`, which is why `evil` faults: the page at
`0x200000` *is* mapped, just not for ring 3 (`PROTECTION_VIOLATION | USER_MODE`).
`.text` is not writable and everything else is `NO_EXECUTE` (when EFER.NXE is on).

A **process** = a kernel thread (`thread.rs`, it already has a kernel stack and
gets preempted) + a CR3 value + a `Process` struct (pid, name, fd table, exit
status). The scheduler, on each switch, sets `TSS.rsp0` and the syscall kernel
stack to the next thread's stack and writes CR3 if it differs. A new process's
thread starts in the kernel, then `iretq`s into ring 3 with a hand-built frame
(SS=user data, RSP=user stack, RFLAGS=IF, CS=user code, RIP=ELF entry).

When ring-3 code faults (page fault with `USER_MODE`, general protection fault
or invalid opcode with CS RPL 3), the handler calls `process::exit_current`
instead of panicking: the process is marked `Killed`, its thread exits, the
scheduler picks someone else. A fault in ring 0 still panics -- that's a kernel bug.

### ELF loading and building user programs (`src/elf.rs`, `build.rs`, `user/`)

`build.rs` compiles each `user/*.rs` with plain `rustc` for the built-in
`x86_64-unknown-none` target (no build-std needed: it ships a precompiled
`core` and uses soft-float, so no SSE state to save). Flags worth knowing:
`-C relocation-model=static` (no dynamic loader), `-C code-model=large`
(the program lives above 4 GiB; the default model assumes 32-bit addresses
and fails with "relocation overflow"), `-T user/link.ld` (one PT_LOAD
segment per permission, page-aligned). The large code model names its
sections `.ltext`/`.lrodata`/`.ldata`/`.lbss`, so the linker script lists
those too -- forgetting that put the code into a non-executable segment and
every program died at its first instruction. The ELFs (~15-20 KB) used to be
embedded in the kernel with `include_bytes!`; since stage 6 `build.rs` copies
them onto the FAT32 disk image instead and `process::spawn_path` reads them
through the VFS (see "Disks" below).

`user/ulib.rs` is a tiny libc-equivalent included by each program: the
`syscall` inline asm, wrappers, `print!/println!/eprintln!`, `_start` (calls
`main`, then `exit` with its return value) and a panic handler (`exit(101)`).
Since stage 7 it also has a **heap**: a 64 KiB array in `.bss` with a
power-of-two size-class allocator (free list per size) as the
`#[global_allocator]`. A program that says `extern crate alloc;` can use
`Vec`, `String` and `format!`; the `x86_64-unknown-none` target ships a
precompiled `alloc` too.

The loader (~160 lines, no crate) checks the header (magic, 64-bit, little
endian, x86_64, `ET_EXEC`), and for every `PT_LOAD` segment: checks it's
inside the user range, maps zeroed frames with flags from the segment
(`W` -> writable, no `X` -> NX), copies `filesz` bytes through the
physical-memory map and leaves the rest (`.bss`) zero. It refuses (`ENOEXEC`)
a file where two segments with different permissions share a page. A page
has one set of permissions, so the second segment would silently get the
first one's. This happened for real in stage 7: `sleep` has no `.data`, so
the linker put its `.bss` on the read-only `.rodata` page, and `sleep` died
on its first write to a static. `user/link.ld` now aligns the location
counter before `.data`, not just the (empty, hence dropped) section.

### VFS (`src/fs/`) and file descriptors

Designed like Linux's so real filesystems can plug in later:

- `trait Inode` (`fs/mod.rs`): a file or directory: `kind`, `size`,
  `read_at(offset, buf)`, `write_at`, `truncate`, `lookup(name)`,
  `create(name, kind)`, `list` (names + kinds), `remove(name)`.
  Methods have default impls returning an error, so a read-only fs implements
  only what it supports.
- `trait FileSystem`: `name()` and `root() -> Arc<dyn Inode>`. A disk filesystem
  will hold its block device and parsed superblock.
- **Mount table**: `mount("/tmp", fs)`; `lookup(path)` picks the longest mount
  point that prefixes the path, then walks the rest with `Inode::lookup`.
  Boot mounts a ramfs on `/` (`/hello.txt`, `/etc/motd`, `/tmp`, `/mnt`), a
  second, separate ramfs on `/tmp`, and each FAT partition at `/mnt/diskN`.
  `fs::normalize(cwd, path)` turns any path into a clean absolute one first.
- `trait File` (`fs/file.rs`): what a file descriptor points to: `read(buf)`,
  `write(buf)`, `seek`, `stat`, `getdents`. `InodeFile` = an inode + its own offset (two opens of the same
  file have separate offsets, like Linux's `struct file`). `tty::Console` is
  another `File`: writes go to VGA+serial, reads come from the keyboard line
  buffer. `fs/pipe.rs` gives two more: a pipe's read and write ends.
- **fd table**: `Vec<Option<Arc<dyn File>>>` per process (max 16), fds 0-2 =
  Console. `open` = `fs::lookup` (or `fs::create` with `O_CREAT`) + `InodeFile::open`
  + first free slot.

Keyboard input for `read(0)` goes through a small tty line discipline
(`src/tty.rs`), like Linux's termios:

- **Cooked mode** (the default): the kernel echoes the characters and
  Backspace edits the current line. Enter makes the line, with its `\n`,
  available to readers. Programs like `cat` with no arguments see this.
- **Raw mode** (`ioctl(0, TTY_SET_RAW, 1)`): every key goes to the reader at
  once and nothing is echoed. Backspace is `\x08`, and the arrows, Home, End
  and Delete arrive as ANSI escape sequences (`ESC [ A` = up...). The shell
  uses this while you edit a line, so it can do the echo and history itself.
  It switches back to cooked before running a program. Raw mode is also
  switched off automatically if its owner process exits.

The console understands two control characters on output. `\x08` moves back
one column and blanks it, and `\x0c` (form feed) clears the screen, which is
what `cls` writes.

**Process cleanup.** When `wait` reaps a process, `memory::free_address_space`
walks L4 slot 1 (the user half) and frees every page, page table and the L4
table. Freed frames go on a free list that `alloc_frame` uses first. The list
is an intrusive linked list: each free frame stores the address of the next
one, written through the physical-memory map, so it needs no heap. The
exiting process disables interrupts before publishing its exit status. That
way the parent can't free the address space while the dying thread might
still run on it.

Known simplifications (exercises): a process nobody waits for keeps its memory; orphans aren't reparented; no signals; user pointer
checks walk the page table but don't guard against another thread unmapping
the page mid-syscall (there's no `munmap` yet, so that's fine for now).

## Disks: PCI, virtio-blk, partitions, FAT32 (stage 6)

```
/mnt/disk0/readme.txt
   VFS (fs/mod.rs)          longest mount prefix -> FatFs, rest "readme.txt"
   FatInode (fs/fat.rs)     fatfs crate: clusters, FAT chains, directory entries
   BlockIo adapter          byte offsets -> whole 512-byte sectors
   Partition vda1           sector + 2048, bounds-checked
   VirtioBlk vda            virtqueue request to QEMU
   PCI                      found the device and its I/O port at boot
```

**PCI** (`src/pci.rs`). Every PCI device has a 256-byte configuration space
(vendor/device id, class code, BARs = where its registers live). On a PC you
read it by writing `bus/device/function/offset` to port `0xCF8` and reading
port `0xCFC`. `pci::scan()` tries every bus/device/function, keeps the ones
whose vendor id isn't `0xFFFF`, and prints them with a class name. QEMU's
default machine has 7: host bridge, ISA/IDE/ACPI parts of the PIIX chipset,
VGA, the e1000 network card, and our disk, `1af4:1001`.

**Why virtio-blk and not ATA PIO?** ATA PIO is simpler (a few port writes,
then 256 `in` instructions per sector) but it's a 1980s interface that only
emulators and old hardware have. virtio is what QEMU/KVM and cloud VMs
actually use, and it teaches the pattern every modern device uses: the driver
and device share **queues of descriptors in RAM**. The legacy (virtio 0.9.5)
interface is used, through I/O port BAR0, because it needs no MMIO mapping or
PCI capability parsing; QEMU's device is "transitional" and speaks both.

**virtio-blk in one paragraph** (`src/block/virtio_blk.rs`, ~280 lines).
Reset the device, set ACKNOWLEDGE + DRIVER, accept no optional features,
read the queue size, allocate the virtqueue (descriptor table + available
ring + used ring, physically contiguous: `memory::alloc_contiguous_frames`)
and give its page number to the device, set DRIVER_OK. A request is a chain
of three descriptors: a 16-byte header (`IN` = read or `OUT` = write, sector
number), the data buffer, and a 1-byte status the device fills in. Put the
chain's head in the available ring, write the queue number to the notify
port, then **poll** the used ring until the device hands it back. Data goes
through a one-page **bounce buffer** whose physical address we know (heap
buffers are virtually contiguous but not physically). Interrupts are switched
off for the device (`VRING_AVAIL_F_NO_INTERRUPT`); polling is fine because QEMU
completes requests almost instantly. Exercises: IRQ-driven completion (block
the thread on a wait queue), several requests in flight, virtio 1.0 "modern"
MMIO.

**`BlockDevice`** (`src/block/mod.rs`): `sector_count()`,
`read_sectors(lba, buf)`, `write_sectors(lba, buf)`, buffers a whole number of
512-byte sectors. Devices get Linux-style names in a registry
(`block::devices()`, `block::get("vda1")`). `RamDisk` is a `Vec<u8>` disk used
by tests.

**Partitions** (`src/block/partition.rs`). Sector 0 is the MBR: four 16-byte
entries at offset 446 and the `55 AA` signature. A single entry of type `0xEE`
is a "protective MBR" meaning *look for a GPT*: sector 1 has the `EFI PART`
header, which says where the partition entry array is (128 bytes each: type
GUID, unique GUID, first/last LBA, UTF-16 name). Each partition becomes a
`Partition` -- itself a `BlockDevice` that adds its start sector and refuses
to go past its end -- registered as `vda1`, `vda2`... CRCs aren't checked yet.

**FAT32 via the `fatfs` crate** (`src/fs/fat.rs`). `fatfs` does the
filesystem logic; it wants something implementing its `Read + Write + Seek`
traits on *bytes*. `BlockIo` is that adapter: it keeps a byte position, sends
whole aligned sectors straight to the device, and handles partial sectors
through a one-sector buffer (read the sector, change the bytes, write it back).
Writes go straight through, so `flush` has nothing to do. (`fatfs` 0.3 from
crates.io depends on the abandoned `core_io` crate, which doesn't build on
current nightlies, so `Cargo.toml` pins a git revision of the 0.4 branch with
its own `no_std` IO traits.) For the VFS, `FatFs` holds the `fatfs::FileSystem`
in an `Arc<Mutex<..>>`, and a `FatInode` is just *(that filesystem, a path, a
kind)*: each call reopens its path from the root. Slower than caching
directory entries, but simple and never stale. Lookups are case-insensitive,
like FAT itself. No timestamps (`NullTimeProvider`) and long file names on.

**The test disk** (`build.rs`). After compiling the user programs,
`build.rs` makes `target/disk.img` (64 MiB): `sfdisk` writes a GPT with one
"Microsoft basic data" partition at sector 2048, `mkfs.vfat -F 32 -s 1 -n
TYLERDISK` formats a separate partition image (1 sector per cluster so 62 MiB
is enough clusters for FAT32), `mmd`/`mcopy` (mtools, which edit FAT images
without mounting, so no root) copy in `disk/` and `bin/<programs>`, and the
partition image is spliced into the disk at sector 2048. If a tool is missing
the build stops with `sudo apt install dosfstools mtools fdisk`
(`mkfs.vfat` lives in `/usr/sbin`, which isn't in a normal user's `PATH` on
Debian, so `build.rs` looks there too). Look inside it from Linux:

```sh
/usr/sbin/sfdisk -l target/disk.img             # not in a normal user's PATH on Debian
export MTOOLS_SKIP_CHECK=1                     # mtools: don't complain about the small-cluster FAT32
mdir -i target/disk.img@@1M ::/bin          # @@1M = partition offset (2048 * 512)
mtype -i target/disk.img@@1M ::/readme.txt
```

## The shell (stage 7)

`/bin/sh` on the disk (`user/sh.rs`, about 550 lines) is an ordinary ring-3
program. It uses nothing but the syscalls above. Its design is a **hybrid**:
Unix navigation and pipes, with DOS-style program running and drive letters
on top. At boot a kernel thread starts it on the console and waits for it.
When it exits, the thread starts a new one, the way `init` respawns a login
shell.

```
Rustbelt shell. Type `help` for commands. Drives: C: = /, D: = /mnt/disk0
C:/ $ cd d:
D:/ $ ls
bin/        notes/      readme.txt  scripts/
D:/ $ type readme.txt | grep -i rustbelt
In the Rustbelt shell this disk is drive D: -- try `cd D:` and `ls`.
D:/ $ ls bin | wc -l
15
D:/ $ echo first > C:/tmp/a.txt
D:/ $ echo second >> C:/tmp/a.txt
D:/ $ wc < C:/tmp/a.txt
      2       2      13
D:/ $ run --trace cat notes/todo.txt
[trace 8] open("notes/todo.txt", 0o0) = 3
[trace 8] read(3, "Done: the shell (cd, ls, cat, run, start"..., 512) = 125
Done: the shell (cd, ls, cat, run, start, pipes, redirection, drive letters).
Next: more file systems -- ext2, exFAT, btrfs.
[trace 8] write(1, "Done: the shell (cd, ls, cat, run, start"..., 125) = 125
[trace 8] read(3, "", 512) = 0
[trace 8] close(3) = 0
[trace 8] exit(0)
D:/ $ start sleep 5
[pid 9] sleep started in the background
D:/ $ jobs
[pid 9] running  start sleep 5
D:/ $ run evil
[evil] pid 10: reading kernel memory at 0x200000...
[process] pid 10 (evil) killed: page fault
[exit code 139]
D:/ $ ver
Rustbelt 0.7.0 (stage 7: shell) x86_64
D:/ $                      <- Enter on an empty line, a few seconds later
[done] pid 9 (start sleep 5), exit code 0
D:/ $
```

### Commands

| Command | What it does |
|---|---|
| `cd [dir]` | change directory (`cd` alone = `C:/`); `cd D:` goes to the root of drive D |
| `pwd` | print the current directory as a Unix path (the prompt shows the drive form) |
| `echo text...` | print the arguments |
| `ver` | kernel name and version, from the `uname` syscall |
| `drives` | the drive letters and what they map to |
| `alias [name=value]` | list aliases or define one: `alias ll="ls -l"` |
| `history` | the commands typed so far |
| `jobs` / `wait [pid]` | list background jobs / wait for them (all, or one pid) |
| `cls`, `clear` | clear the screen |
| `help` | the command list |
| `exit [code]` | leave the shell (with the last command's exit code, or `code`) |
| `run [--trace] prog args` | run a program in the foreground; `--trace` prints every syscall it makes |
| `start prog args` | run it in the background and print its pid (same as `prog args &`) |
| `prog args` | a bare name is looked up in each drive's `bin` directory, in order: `C:/bin`, `D:/bin`... |

Programs in `D:/bin` (`user/*.rs`, each 30-150 lines):

| Program | What it does |
|---|---|
| `ls [-l] [path...]` | list a directory, sorted; in columns on the console, one name per line into a pipe or file (like real `ls`); `-l` shows sizes and `<DIR>` |
| `cat [file...]` | print files, or stdin (also for `-`) |
| `wc [-l] [file...]` | lines, words, bytes |
| `grep [-i] [-v] [-n] text [file...]` | lines containing `text` (plain text, no regexes); exit code 0 = found, 1 = not found |
| `mkdir dir...` | create directories |
| `rm path...` | delete files or empty directories |
| `touch file...` | create empty files |
| `cp src dest` | copy a file (into `dest` if it's a directory) |
| `sleep N` / `sleep 250ms` | wait (blocks in the kernel, no busy loop) |
| `hello`, `demo`, `evil`, `spin`, `child` | the stage 5/6 test programs: `run demo` runs all the stage 6 syscall checks |

Built-in aliases are the DOS names: `dir` = `ls`, `type` = `cat`,
`del` = `rm`, `md` = `mkdir`, `copy` = `cp`.

**Line editing**: Backspace, and Up/Down to browse the history. Left/Right
and Tab aren't supported yet. **Scripts**: `sh file` runs the commands in a
file and echoes each one after its prompt. If stdin isn't the console
(`sh < file`, `cat file | sh`), the shell reads commands from it the same
way. `#` starts a comment.

### Pipes and redirection

`a | b | c`, `> file` (create or truncate), `>> file` (append) and `< file`
can be combined: `cat < in.txt | grep x | wc -l > count.txt`. The operators
don't need spaces around them (`ls|wc`). Quotes (`'...'` or `"..."`) group
words and hide operators. There are no variables or escapes.

How a pipeline runs (`Shell::run_pipeline`): for each stage, the shell picks
its stdin and stdout and spawns it.
- **stdin**: the `< file`, else the read end of the previous stage's pipe,
  else the shell's own stdin.
- **stdout**: a new `pipe()` to the next stage, overridden by `> file`, else
  the shell's own stdout.
- **Spawning**: the stage starts with `spawn(path, argv, SpawnOptions { stdin,
  stdout, ... })`.

Then the shell **closes its own copies** of all pipe ends and files. A reader
only sees end-of-file once every write end is closed, and the shell holds
one. Last, it waits for every stage; the last stage's exit code is the
pipeline's. A builtin can be a stage too (`help | grep run`): it just writes
to the pipe. Pipes have no size limit here, so that can't block.

### Drive letters

Drive letters are only shell syntax. The kernel keeps one Unix tree:

- **Mapping**: `C:` is `/`. `D:`, `E:`... go to the mounts under `/mnt`,
  in the order they were mounted. The shell reads them from the `mounts`
  syscall before every prompt, so a newly mounted disk would get a letter
  right away. Other mounts, such as `/tmp`, stay under C: (`C:/tmp`).
- **Translation**: every unquoted word that starts with a known letter is
  translated before any syscall sees it (`shparse::translate`):
  - `D:/notes/todo.txt` becomes `/mnt/disk0/notes/todo.txt`.
  - `d:` becomes `/mnt/disk0` (any case).
  - `D:notes` becomes `/mnt/disk0/notes`, since drives don't have their own
    current directory.

  Quote a word to keep it literal: `grep "D:" readme.txt`.
- **Prompt**: the prompt goes the other way (`shparse::display`). The longest
  matching drive path wins, so `/mnt/disk0/bin` shows as `D:/bin`.
- **Unknown letters**: these are left alone, so `cd Q:` says
  `there is no drive Q:`.

### How the pieces fit

- `user/shparse.rs`: the tokenizer, the parser (`Pipeline` of `Command`s,
  each with words and redirections) and the drive-letter functions. All of
  them are pure functions with no syscalls. The same file is compiled into
  the shell *and* into `tests/shell.rs` (`#[path = "../user/shparse.rs"]`),
  so the parser is unit-tested inside the kernel test suite.
- `user/sh.rs`: the main loop runs these steps: refresh the drives, report
  finished background jobs (`wait` with `WNOHANG`), print the prompt, read a
  line, then run it. Before running, each command goes through `prepare()`:
  it translates drive letters, expands aliases, and strips `run` /
  `run --trace` / `start` prefixes. The command then runs as a builtin or is
  spawned with the right fds.
- **Kernel support added for the shell**:
  - `ioctl` (raw mode), `uname`, `mounts`, `wait` flags and `O_APPEND`.
  - Freeing process memory, so a long session doesn't run out of frames.
  - strace-style `--trace` output.
  - The `\x08` and `\x0c` console controls.
  - A fix for the `|` key (see Notes).

## Roadmap

Done: all 12 chapters of the 2nd edition, plus preemptive kernel threads,
user mode + syscalls, ELF loading, a VFS with a ramfs, PCI, virtio-blk,
MBR/GPT partitions, FAT32, blocking threads, pipes, spawn/wait, process
memory cleanup, and the shell.

- [x] Freestanding binary — [phil-opp](https://os.phil-opp.com/freestanding-rust-binary/)
- [x] Minimal kernel booting in QEMU — [phil-opp](https://os.phil-opp.com/minimal-rust-kernel/), [OSDev: Bare Bones](https://wiki.osdev.org/Bare_Bones)
- [x] VGA text mode printing — [phil-opp](https://os.phil-opp.com/vga-text-mode/), [OSDev: Printing to Screen](https://wiki.osdev.org/Printing_To_Screen)
- [x] Serial output + QEMU exit — [phil-opp: Testing](https://os.phil-opp.com/testing/), [OSDev: Serial Ports](https://wiki.osdev.org/Serial_Ports)
- [x] CPU exceptions / IDT — breakpoint & page fault handlers. [phil-opp: CPU Exceptions](https://os.phil-opp.com/cpu-exceptions/), [OSDev: IDT](https://wiki.osdev.org/Interrupt_Descriptor_Table), [OSDev: Exceptions](https://wiki.osdev.org/Exceptions)
- [x] GDT / TSS / double faults — separate IST stack so stack overflows don't triple-fault. [phil-opp: Double Faults](https://os.phil-opp.com/double-fault-exceptions/), [OSDev: GDT](https://wiki.osdev.org/Global_Descriptor_Table), [OSDev: TSS](https://wiki.osdev.org/Task_State_Segment)
- [x] Testing — `cargo test` in QEMU, custom test framework, integration tests. [phil-opp: Testing](https://os.phil-opp.com/testing/)
- [x] Hardware interrupts — 8259 PIC, timer, PS/2 keyboard echo, `hlt` idle loop. [phil-opp: Hardware Interrupts](https://os.phil-opp.com/hardware-interrupts/), [OSDev: 8259 PIC](https://wiki.osdev.org/8259_PIC), [OSDev: PIT](https://wiki.osdev.org/Programmable_Interval_Timer), [OSDev: PS/2 Keyboard](https://wiki.osdev.org/PS/2_Keyboard) (later: [APIC](https://wiki.osdev.org/APIC))

- [x] Introduction to paging — CR3, page fault demo. [phil-opp](https://os.phil-opp.com/paging-introduction/), [OSDev: Paging](https://wiki.osdev.org/Paging)
- [x] Paging implementation — OffsetPageTable, translation, frame allocator, example mapping. [phil-opp](https://os.phil-opp.com/paging-implementation/), [OSDev: Page Frame Allocation](https://wiki.osdev.org/Page_Frame_Allocation)
- [x] Heap allocation — `alloc`, heap mapping, global allocator. [phil-opp](https://os.phil-opp.com/heap-allocation/), [OSDev: Memory Allocation](https://wiki.osdev.org/Memory_Allocation)
- [x] Allocator designs — bump, linked list (crate), fixed-size block (active). [phil-opp](https://os.phil-opp.com/allocator-designs/)

- [x] Async/await — Task, simple executor, waker-based executor, lock-free async keyboard task (with Backspace). [phil-opp: Async/Await](https://os.phil-opp.com/async-await/), [OSDev: Multitasking Systems](https://wiki.osdev.org/Multitasking_Systems)
- [x] Preemptive kernel threads — own stacks, timer-driven round-robin, asm context switch. [OSDev: Brendan's Multi-tasking Tutorial](https://wiki.osdev.org/Brendan%27s_Multi-tasking_Tutorial), [OSDev: Context Switching](https://wiki.osdev.org/Context_Switching)

- [x] User mode (ring 3) & syscalls — GDT user segments, TSS.rsp0 per thread, `syscall`/`sysret`, per-process page tables, user faults kill the process. [OSDev: Getting to Ring 3](https://wiki.osdev.org/Getting_to_Ring_3), [OSDev: System Calls](https://wiki.osdev.org/System_Calls), [OSDev: SYSENTER/SYSCALL](https://wiki.osdev.org/SYSENTER)
- [x] ELF loading — hand-written PT_LOAD loader, user programs built by `build.rs`. [OSDev: ELF](https://wiki.osdev.org/ELF), [OSDev: ELF Tutorial](https://wiki.osdev.org/ELF_Tutorial)
- [x] VFS skeleton + ramfs — Inode/FileSystem/File traits, mount table, fd table, `open/read/write/close`. [OSDev: VFS](https://wiki.osdev.org/VFS), [Linux VFS overview](https://www.kernel.org/doc/html/latest/filesystems/vfs.html)
- [x] PCI enumeration + virtio-blk driver + `BlockDevice` trait — [OSDev: PCI](https://wiki.osdev.org/PCI), [OSDev: Virtio](https://wiki.osdev.org/Virtio), [virtio spec (legacy interface)](https://docs.oasis-open.org/virtio/virtio/v1.2/virtio-v1.2.html)
- [x] MBR + GPT partitions — [OSDev: MBR](https://wiki.osdev.org/MBR_(x86)), [OSDev: GPT](https://wiki.osdev.org/GPT)
- [x] FAT32 through `fatfs`, mounted at `/mnt/disk0`; programs loaded from disk — [OSDev: FAT](https://wiki.osdev.org/FAT)
- [x] Blocking threads + wait queues, pipes, `spawn`/`wait`, cwd, `stat`/`lseek`/`getdents64` — [OSDev: Blocking Process](https://wiki.osdev.org/Blocking_Process)
- [x] Shell as a user program: line editing, builtins, PATH, pipes, redirection, background jobs, drive letters, `run --trace` — [OSDev: Shell](https://wiki.osdev.org/Shell)
- [x] Process cleanup: frame free list, address spaces freed on reap

### Filesystem roadmap (Tyler's plan)

Everything below plugs into the VFS above: a filesystem is a `FileSystem`
whose `root()` returns `Inode`s; mounting it is one `fs::mount` call.

1. **ramfs / tmpfs** — done (`src/fs/ramfs.rs`).
2. **Block device driver** — done: `BlockDevice` trait + legacy virtio-blk
   (stage 6). Still to do: a block cache, IRQ-driven completion, maybe an
   ATA PIO driver for comparison ([OSDev: ATA PIO Mode](https://wiki.osdev.org/ATA_PIO_Mode)).
3. **Partition tables** — done: MBR + GPT (no CRC checks yet).
4. **FAT32** — done via the `fatfs` crate (`src/fs/fat.rs`). A good exercise
   later: a hand-written read-only FAT32 to see what the crate does.
5. **ext2** — written by hand: superblock, block groups, inode table, direct/indirect
   blocks, directory entries. The classic "learn how Unix filesystems work" step,
   and the base for understanding ext4 later. [OSDev: Ext2](https://wiki.osdev.org/Ext2),
   [The Second Extended File System (Dave Poirier)](https://www.nongnu.org/ext2-doc/ext2.html)
6. **End goals:**
   - **exFAT** — because it works on literally anything (cameras, phones,
     Windows, macOS, Linux), so a kernel that speaks exFAT can share USB sticks
     and SD cards with every other machine. Allocation bitmap + FAT-like cluster
     chains + directory entry sets with checksums.
     [Microsoft exFAT specification](https://learn.microsoft.com/en-us/windows/win32/fileio/exfat-specification)
   - **btrfs** (read-only first) — because most of Tyler's Linux systems will use
     btrfs going forward, so this kernel could read their disks. Much bigger:
     copy-on-write B-trees, the chunk tree (logical -> physical mapping), the
     root/fs trees, checksums, compression (zlib/lzo/zstd). Read-only means
     parsing the superblock, chunk tree and fs tree -- no transactions or
     space allocation. [btrfs on-disk format](https://btrfs.readthedocs.io/en/latest/dev/On-disk-format.html),
     [btrfs docs](https://btrfs.readthedocs.io/)
7. **NTFS** — last, maybe never.

Other next stages:

- **Shell extras**: Left/Right cursor movement, Tab completion of file
  names, `$?` and environment variables, Ctrl+C to kill the foreground job
  (that needs signals or a kill syscall).
- **More programs**: `more`/`less` (needs raw mode and screen size), an editor.

Small exercises along the way: guard pages under thread stacks, a timer-based
async `sleep` future, speed up the PIT
([OSDev: PIT](https://wiki.osdev.org/Programmable_Interval_Timer)), add handlers for
divide error / general protection fault, make `BootInfoFrameAllocator` O(1), add a
`mem` stat (bytes allocated) to the allocator.

Other good references: [OSDev wiki main page](https://wiki.osdev.org/Expanded_Main_Page),
[Intel SDM](https://www.intel.com/content/www/us/en/developer/articles/technical/intel-sdms.html),
the [blog_os repo](https://github.com/phil-opp/blog_os) (one branch per post, e.g. `post-04`),
and for a UEFI/framebuffer setup later, the newer [`bootloader` 0.11](https://github.com/rust-osdev/bootloader) crate.

## Notes / gotchas

- The target JSON changes occasionally with new nightlies (e.g. `target-pointer-width`
  became an integer, `rustc-abi` was added). If a nightly update breaks the build,
  compare with the latest `x86_64-blog_os.json` in the blog_os repo, or pin a date in
  `rust-toolchain.toml` (`channel = "nightly-2026-10-29"`).
- The "packages contain code that will be rejected by a future version of Rust: core"
  warning comes from building `core` with build-std and is harmless.
- `bootimage` prints "`CARGO_MANIFEST_DIR` env variable not set" when run outside
  `cargo run`; also harmless.
- `cargo test` with build-std breaks ("duplicate lang item in crate `core`: `sized`")
  if `Cargo.toml` sets `panic = "abort"` in `[profile.*]`. The target JSON already
  sets `"panic-strategy": "abort"`, so the profile settings were removed.
- Stale disk image when switching cargo features: cargo re-uses a previously built
  kernel ELF with an *old* mtime, so bootimage thinks its cached image is current
  and boots the wrong build. `scripts/runner.sh` and the scripts `touch` the ELF
  first to avoid this. If you call `cargo bootimage --features ...` by hand after
  switching features, `touch target/x86_64-rust_kernel/debug/rust_kernel` first.
- `build.rs` reruns when `user/`, `disk/` or `build.rs` change and rebuilds
  `target/disk.img`. QEMU opens it with `snapshot=on`, so the kernel's writes
  (the tests create and delete files) never reach the file on disk.
- Debug builds use a lot of stack: deep call chains (syscall -> VFS -> fatfs
  -> ELF loader) needed more than 16 KiB. If you see a weird ring-0 fault at
  address 0 or "kernel stack overflow in thread", suspect the stack first.
- **The `\ |` key**: pc-keyboard 0.7's scancode set 1 decodes it (scancode
  0x2B) as `KeyCode::Oem7`, but its US 104-key layout only maps `Oem5` to
  `\` and `|`. So that key typed nothing, which went unnoticed until the
  shell needed `|`. `task/keyboard.rs` renames `Oem7` to `Oem5` before
  decoding.
- User programs: the linker drops empty output sections, and their
  `ALIGN(4K)` with them. A program without `.data` then had its `.bss` on the
  read-only `.rodata` page (see "ELF loading"). `user/link.ld` uses
  `. = ALIGN(4K);` before `.data`, and the loader now rejects such files.