Extension labs
Twenty-five extensions to xv6, each a git branch from the frozen commit. Every lab runs the same way: read the spec, think through the design with hints that get more specific, build it yourself, study real bugs and the symptoms they caused, then walk through the reference solution one commit at a time, with the machine state at every step. Every reference branch passes xv6's full usertests on three harts.
The system-call and trap path
1trace: logging system callsYou add a new system call, trace(mask), and a command, trace MASK command args....
While a process’s mask has bit i set, the kernel prints one line each time system call
number i returns: 3: syscall r2A kernel backtrace on panicWhen this kernel panics it prints one line, such as panic: sched locks, and stops. The
line names the check that failed, not the path that led to it. In this lab you add
backtrace(), which prints the 3ps: a safe snapshot of the process tableYou add a system call, procinfo(struct pinfo *buf, int max), that copies one record per
in-use slot of the process table into a user buffer: pid, parent’s pid, state, size, name,
and the hart the proc4CPU time accounting and a time commandYou teach the kernel to keep, for every process, how much time it spent running in user
mode and how much in the kernel, and you add a time command:
$ time cputest spin 1000
real 1.955
user 1.950
sys
Traps and control flow
5sigalarm and sigreturn: calling a user handler from a timerYou add two system calls. sigalarm(n, handler) asks the kernel to call handler in user
space after every n timer ticks of CPU time the process uses; sigreturn(), called at
the end of the handler, puts6Ctrl-C: interrupting the foreground jobIn this tree, Ctrl-C is just a byte. Type cat, press Ctrl-C, and the UART
delivers 0x03 to consoleintr, which stores it in the input buffer like any letter.
cat keeps waiting. A program that computes 7A sampling profilerWhere does a program spend its time? A sampling profiler answers without changing the
program: every so often, it stops the program, writes down where it was, and lets it go
on. After a few hundred sa
Scheduling
8Stride scheduling with niceThe scheduler in this tree gives every runnable process the same treatment: each of the
three harts walks the process table in slot order and runs whatever is
RUNNABLE, one timer tick at a time. A com9User threads: clone, join and futexEvery xv6 process has exactly one thread: one page table, one trapframe, one kernel stack,
one stream of instructions. In this lab you add threads. clone(fn, arg, stack) starts a
new thread that runs
Memory
10A shared read-only page: system calls without a trapgetpid() asks the kernel for one integer it already knows. To get it, the process executes
ecall, the hart traps, uservec saves 31 registers, the kernel switches page tables,
usertrap and syscall run,11Copy-on-write forkIn this tree kfork copies every page of the parent with uvmcopy: one kalloc and
one 4096-byte memmove per page. Most of that work is wasted. The shell forks a child that
calls exec a few microseconds 12Demand-paged execIn this tree kexec reads a whole program into memory before the program runs its first
instruction. For each loadable segment of the ELF file it allocates every page and
fills it with readi (loadseg).13A growable user stackIn this tree every user program gets exactly one page of stack. kexec places a
guard page and a single stack page right after the program’s data, and the heap grows
from just above them. A recursive f14SuperpagesEvery user page in this tree is 4096 bytes, mapped by a PTE (page-table entry) in a level-0 page-table
page that walk reaches through two higher levels. A process that grows its heap by
4 megabytes ge15mmap and munmap of filesIn this tree a process reaches a file’s bytes only through read and write: the kernel
copies them between the buffer cache and a buffer the program owns. In this lab you
add mmap, which puts part of a16Swapping to diskIn this tree a process can use only as much memory as there are free pages. When
kalloc finds its free list empty, sbrk fails and a lazy page fault kills the process.
In this lab you make the kernel t17Direct user access with sstatus.SUMEvery time a system call reads or writes user memory, this tree’s copyin and
copyout translate the user’s address in software: walkaddr walks the process’s page
table, finds the physical page, and the
Concurrency
18Per-CPU free lists in kallocIn this tree every page of physical memory is handed out from one list, kmem.freelist,
under one spinlock, kmem.lock. Every kalloc and every kfree on every
hart takes that lock, even when the three ha19A hashed buffer cacheIn this tree every bread and brelse, on every hart, takes one spinlock:
bcache.lock (kernel/bio.c:26). While one hart scans the 30 buffers for a block,
every other hart that wants any block spins. In 20Ticket spinlocksEvery spinlock in this tree is one word and one atomic swap. When the holder lets go,
the next hart whose amoswap happens to reach the word first takes the lock. Nothing
remembers who has been waiting21Lockdep-lite: a runtime lock-order checkerTwo harts deadlock when each holds a lock the other wants. Tour 52: Breaking the lock rules built one on
purpose: a copy of the kernel whose kfork takes wait_lock while it still holds the new
child’s
File system
22Doubly-indirect blocks: large filesIn this tree a file can have at most 268 blocks: 12 whose numbers sit in the
inode itself, and 256 more listed in one indirect block.
At 1024 bytes a block, that is 268 KiB, and write refuses to go fu23Symbolic linksIn this tree a name in a directory is a hard link: a struct dirent holding an inode
number. Two names can share one inode, but only inside one file system, never for a
directory, and the inode stays a24Atomic renamexv6 has no way to rename a file. You can ln old new and then rm old, which is how
early Unix mv worked, but that is two system calls and two transactions,
and it cannot move a directory at all. In thi