Unix-style OS kernel
Pintos x86 kernel in C, extended into a sandbox
One machine, many untrusted programs: keep each one away from the kernel and from the others, bound what it can take, and still run programs bigger than RAM.
Course projects 1–2, then extended solo (sandbox, VM, fuzzing)
01 / The problem
What needed solving
Stanford's Pintos is a teaching kernel for x86: out of the box it passes 7 of 27 scheduler tests and none of the user-program tests. My university course work (projects 1 and 2) added the scheduler and the system-call layer.
After the course I extended it towards the problem cloud platforms face: running code you don't trust. That meant validating every pointer a program hands the kernel, real inter-process communication, resource limits a fork bomb can't escape, and demand-paged virtual memory.
Every capability is backed by tests, and the design choice that matters most for performance (which page to evict) is backed by measurements rather than opinion.
7 of 27
02 / Constraints
What the design had to respect
Programs are hostile
Bad pointers, buffers bigger than RAM, fork bombs and CPU hogs must kill only the offender, never the kernel.
A uniprocessor that still races
Timer preemption and threads that block on disk I/O can interleave between any two instructions, so locking has to be designed, not hoped for.
The stock tests stay stock
The original Pintos test suites are never edited; new behaviour gets new suites.
Claims need numbers
The eviction policy is selectable at boot so it can be measured on the same workload, with several seeds per configuration.
03 / Architecture
How it fits together
The architecture as text
Parts
- User program (untrusted, ring 3): Any program the kernel runs. It is assumed hostile: bad pointers, huge buffers, fork bombs and CPU hogs are all tested.
- System calls (int $0x30 handler): The POSIX-style system-call layer: 19 calls, documented one by one against POSIX.
- User memory (validate · pin): Checks every user pointer against the process's page table before the kernel touches it; under virtual memory it faults the pages in and pins them for the whole call.
- Virtual memory (SPT · page faults): Demand paging: lazy loading of executables, stack growth, memory-mapped files, and a supplemental page table that knows where every page lives.
- Processes (exec · wait · exit): Process lifecycle with a load handshake (exec reports a load failure to the parent) and parent–child exit-status tracking.
- File I/O (per-process fds): Per-process file-descriptor tables over a global file-system lock.
- Frame table (clock eviction): Tracks every physical frame and picks a victim when memory runs out. The policy is selectable at boot (clock, FIFO, random) so it can be measured.
- Pipes & dup2 (ring buffer · condvars): pipe, dup2 and exec_redirect (a posix_spawn-style redirect): enough to build a shell with pipelines.
- Resource limits (cgroups-lite tree): Per-subtree caps on processes and pages, and per-process caps on file descriptors and CPU time. A fork bomb is contained, a CPU hog is killed.
- Scheduler (donation · MLFQS): Preemptive priority scheduling with nested priority donation, and a 4.4BSD-style multi-level feedback queue in 17.14 fixed point. The timer charges each process's CPU budget.
- File system (stock Pintos): The disk-backed file system: executables, data files, and the backing store for memory-mapped files.
- Swap (swap slots on disk): Holds evicted anonymous pages (stack, heap) until they're needed again.
Connections
- User program → System calls: int $0x30 with arguments on the user stack
- System calls → User memory: validate every pointer and buffer
- User memory → Virtual memory: fault in and pin the buffer's pages
- Virtual memory → Frame table: get a frame, evicting if needed
- Frame table → Swap: write the victim out
- Virtual memory → File system: lazy load and mmap write-back
- System calls → Processes: exec, wait, exit
- System calls → File I/O: open, read, write, close
- File I/O → File system: under the file-system lock
- System calls → Pipes & dup2: pipe, dup2, exec_redirect
- System calls → Resource limits: setlimit, getlimit
- Processes → Resource limits: admission check at exec
- Resource limits → Scheduler: CPU budget charged by the timer
04 / Follow one request
Follow one system call
STEP 01
The program traps into the kernel
read() executes int $0x30. The handler reads the call number and arguments from the user stack, and validates the stack pointer itself first.
STEP 02
Every pointer is checked
The buffer's whole range is checked against the process's page table. A bad pointer kills only this process; the kernel never dereferences it.
STEP 03
The buffer is faulted in and pinned
The buffer's pages aren't resident, so the VM layer loads them and marks them unevictable, at most 64 KB at a time. This happens before any lock is taken.
STEP 04
Memory is full: clock picks a victim
No free frame. The clock hand sweeps, gives recently used pages a second chance, and evicts one; its contents go to swap. The page's owner can't free that frame while it's being written out.
STEP 05
The file is read under the lock
Only now is the file-system lock taken. Because the buffer is pinned, the read can't fault while holding the lock, so the classic read-into-unloaded-buffer deadlock can't happen.
STEP 06
Unpinned, returned, and charged
The pages are unpinned and read() returns n. Meanwhile the timer has charged this process's CPU budget against its resource group; a process over budget is killed, not the kernel.
05 / Key decisions
The choices, and what they cost
DECISION 01
Check the page table before touching user memory
- CHOSE
- one module that validates every user pointer and buffer against the page table, copying paths into kernel memory first
- OVER
- letting the first access fault and recovering in the handler (get_user/put_user)
- BECAUSE
- every decision about user memory lives in one auditable place, and copying strings removes the time-of-check/time-of-use gap.
- TRADE-OFF
- a page-table walk per call is slower than optimistic access; the fault handler stays as a safety net.
DECISION 02
Pin before you lock
- CHOSE
- faulting in and pinning a call's buffer pages before taking the file-system lock
- OVER
- taking the lock first and handling faults inside it
- BECAUSE
- a fault under the lock would need the same lock to read the page back: a deadlock. Pinning first makes it impossible by construction.
- TRADE-OFF
- pinned frames can't be evicted, so a huge buffer could pin all of RAM; buffers are now pinned at most 64 KB at a time.
DECISION 03
Clock eviction, measured against FIFO and random
- CHOSE
- second-chance clock as the default, with the policy selectable at boot
- OVER
- FIFO (simplest) or random
- BECAUSE
- on the parallel scan clock needed 3 swap-ins against 320 for FIFO, and FIFO finished 0 of 5 runs of the write-heavy merge sort.
- TRADE-OFF
- on the write-heavy workload random slightly beat clock on evictions; the claim is 'clock is the safe default', not 'clock always wins'.
DECISION 04
Resource limits as a tree, like cgroups
- CHOSE
- resource groups in a tree, where every admission and page charge walks from the leaf to the root, all or nothing
- OVER
- per-process limits, or flat groups a process can split off
- BECAUSE
- a per-process child limit can't stop a fork bomb, and a flat group can be escaped by creating a new one.
- TRADE-OFF
- every charge walks the tree, and group lifetimes need reference counting.
06 / The hardest bug
Symptom to regression test
A parent process died returning into address 0
SYMPTOM
Under the eviction benchmark, page-parallel (several processes faulting at once) failed now and then at 4 MB of RAM and almost every time at 5 MB: the parent died at eip=0, returning into address zero.
HOW IT WAS FOUND
eip=0 means a corrupted return address, so a stack page's contents had been lost across a page-out and page-in while the parent was blocked in wait. I read the swap path adversarially, looking for every place the frame lock is dropped across I/O.
ROOT CAUSE
Two races. swap_in freed its swap slot before reading it, so a concurrent swap_out could take the slot and overwrite it mid-read. And after the evictor cleared a page's mapping but before it recorded where the data went, the owner could fault and the loader would zero-fill a page whose data was still on its way to swap.
FIX
Read first, free second in swap_in, and an 'evicting' barrier: a faulting owner waits on a condition variable until the evictor has recorded where the page went.
WHAT GUARDS IT NOW
page-parallel went from 0 of 5 to 5 of 5 passing runs at 5 MB, the vm suite stays green, and the benchmark matrix re-runs it across policies, memory sizes and seeds.
07 / Results
Measured, with the file that proves each number
CI on the main branch, live from GitHub:
- 245
tests passing in CI across six suites
threads 27, userprog 80, ipc 11, vm 113, limits 6, hardening 8
source ↗ for tests passing in CI across six suites (opens GitHub) - 116,000
fuzzed system calls
v2.1 campaign: userprog 100,000 + vm 8,000 + limits 8,000
source ↗ for fuzzed system calls (opens GitHub) - 0 panics
kernel panics during the fuzz campaign
v2.1 campaign
source ↗ for kernel panics during the fuzz campaign (opens GitHub) - 5 kernel bugs
found by review and fuzzing, each fixed with a regression test
v2.1 hardening
source ↗ for found by review and fuzzing, each fixed with a regression test (opens GitHub) - about 100×
fewer swap-ins with clock than FIFO
page-parallel, 4 MB RAM
source ↗ for fewer swap-ins with clock than FIFO (opens GitHub) - 27/27
scheduler tests (stock Pintos: 7/27)
threads suite
source ↗ for scheduler tests (stock Pintos: 7/27) (opens GitHub) - 80/80
system-call and process tests
userprog suite
source ↗ for system-call and process tests (opens GitHub)
08 / What I'd do differently
With hindsight
- Fuzz and attack the sandbox from the first milestone. Five bugs, including a sandbox escape and a use-after-free, were found only by a later review and an extended fuzzer, after every suite was already green.
- Measure the neighbour slowdown properly: the test proves a well-behaved process finishes beside a fork bomb, but I'd run it alone and with abusers ten times each to put a number on the cost.
- Split exec into a real fork and execve, so an unmodified shell can run.