xv6, line by line

tours

Guided tours

Each tour follows one path through the running system, from the first instruction to the hardware and back, across C, assembly and the linker script. At every step you see the real code, the state of the machine (which hart, which mode, which stack, which page table, which locks are held, and whether interrupts can arrive) and what the other CPUs might be doing at that moment.

Start here: a learning path

Boot and build

1From make qemu to a disk image and a kernelBefore xv6 can run a single instruction, two files must exist: kernel/kernel, the program the three CPUs will execute, and fs.img, the disk they will read init and the shell from. You type make qemu, about a hundred…21 steps · ~34 min✓2Power-on to main, on every hart at onceQEMU has built a machine with three CPUs (harts), copied kernel/kernel into RAM at 0x80000000, and released all three harts at the same instant. None of them knows it is not alone. They run the same instructions,…17 steps · ~28 min✓3main: one hart builds the kernel, the others waitThree harts have just arrived in main, in supervisor mode, each on its own boot stack, with paging and interrupts off (Tour 2: Power-on to main, on every hart at once). Line 13 splits them. Hart 0 goes off to…19 steps · ~33 min✓4From the first process to the shell promptAt the end of main, the kernel is built but nothing is running. There is no init program in memory, no shell, no user code at all: just one entry in the process table, marked RUNNABLE, with an empty address space.…27 steps · ~46 min✓

Traps and system calls

5Life of a system callYou type echo hi at the xv6 shell, and two letters appear on your screen. Between those two events, a user program asks the kernel for help, the CPU changes privilege mode twice, two page tables take turns, a process…26 steps · ~42 min✓6System-call arguments and user pointersYou type cat README. Before cat can print a single byte, it must ask the kernel to open a file, and to do that it hands the kernel a pointer: the address of the string "README" in its own memory. That…20 steps · ~35 min✓7The trampoline and the trapframeTour 5: Life of a system call crossed the user/kernel border twice and moved on quickly. This tour stays at the border. It is 83 instructions long, written in assembly, and runs while the hart belongs to nobody: no…21 steps · ~41 min✓8Traps taken inside the kernelIn Tour 5: Life of a system call a trap came from user mode: the program asked for help, and the trampoline page switched page tables, saved 31 registers and found a kernel stack. This tour is about the other kind of…21 steps · ~36 min✓9Device interrupts and the PLICYou type cat README. To print the first line, cat needs the file’s first data block, block 48 of the disk, and nobody has read it since boot. The kernel hands the request to the disk and puts cat to sleep. Some time…22 steps · ~39 min✓10Exceptions and faultsA system call is a trap the program asks for. An exception is a trap the program did not ask for: it touched memory it has no page for, wrote to its own code, or executed an instruction it is not allowed to execute.…22 steps · ~39 min✓

Time and scheduling

11From a timer tick to a context switchA program that never makes a system call never asks the kernel for anything. So how does the kernel ever get the CPU back from it? This tour answers that by following one tick of the clock on hart 1, from the moment…20 steps · ~34 min✓12One scheduler per hartxv6 has no central scheduler that hands out work. Instead every hart runs its own copy of the same loop, scheduler, forever, and all three loops walk the same table of 64 processes, proc[], looking for one marked…16 steps · ~27 min✓13swtch and the lock handed across a context switchEverywhere else in xv6, the thread that acquires a spinlock releases it. A context switch breaks that rule on purpose. When a process gives up its CPU, it acquires its own p->lock, and the scheduler releases it.…21 steps · ~31 min✓14pause(n) and the tick counterxv6 has exactly one notion of time: ticks, a counter that goes up by one about ten times a second. Only hart 0 increments it. Every process that wants to wait for time to pass, through the pause system call, sleeps…18 steps · ~26 min✓

Concurrency primitives

15Spinlocks from the hardware upTwo harts want the same page of memory at the same moment. There is one list of free pages in the whole machine, kmem.freelist, and if both harts pop it at once they can both walk away with the same page. Two…18 steps · ~34 min✓16sleep and wakeup, and the lost-wakeup problemYou type cat README | wc at the shell. Two programs start at almost the same moment on two different harts. wc asks the pipe for data before cat has written anything, so wc must wait. A few microseconds later cat, on…22 steps · ~40 min✓17Sleep-locksYou type ls | grep README. The shell’s child forks two processes, and a moment later both call exec at almost the same instant, on two different harts: ls (pid 4) on hart 1 and grep (pid 5) on hart 2. To load a…23 steps · ~41 min✓18Lock ordering: how xv6 avoids deadlockOne lock can never deadlock a correct program. Two locks can. If hart 1 holds lock A and waits for B while hart 2 holds B and waits for A, both wait forever, and soon every other hart that touches A or B joins them.…23 steps · ~47 min✓19Memory ordering across hartsWhen you read a C program you assume that its statements happen in the order you wrote them. On one hart that assumption is safe: whatever the compiler and the CPU do behind the scenes, a hart always sees its own…20 steps · ~39 min✓

Processes

20forkYou type ls at the $ prompt and press Enter. Before a single line of ls runs, the shell has to make a second copy of itself: a new process with its own memory, its own kernel stack and its own process ID, but the…20 steps · ~37 min✓21exit, wait and zombiesls has printed its listing. On hart 2 it calls exit(0). On hart 0, the shell has been asleep inside wait(0) since it forked ls. In the next few microseconds the two must meet: the dying process has to tell its…19 steps · ~31 min✓22execThe shell’s child (pid 3) is a copy of the shell (Tour 20: fork). It has parsed the command line, found the single word ls, and now calls exec("ls", argv). When that call succeeds, the process is no longer…18 steps · ~29 min✓23killkill 5 sounds like an order: stop process 5, now. In xv6 it is closer to a note left on the victim’s desk. kkill sets a flag, p->killed, and if the victim is asleep, nudges it awake. That is all. The victim itself…17 steps · ~27 min✓

Memory

24The kernel page table and turning paging onUntil now, every address the kernel used went straight to physical memory. That cannot last: user processes need their own private views of memory, kernel stacks need guard pages, and the trampoline must appear at…19 steps · ~31 min✓25A user address spaceThe shell sh (pid 2) believes it owns a private memory that starts at address 0 and runs up to 256 GiB. Its code is at 0x0, its command buffer at 0x2020, its stack near 0x5000. Every other process believes the same…17 steps · ~27 min✓26sbrk, eager and lazy, and page faultsA program that needs more memory asks the kernel to move the end of its address space up. xv6 offers two ways to do it. sbrk(n) is eager: the kernel allocates and maps every page right away. sbrklazy(n) is lazy: the…18 steps · ~29 min✓27The physical page allocatorEvery page table, every page of user memory, every kernel stack, trapframe and pipe buffer in xv6 comes from one place: a linked list of free 4096-byte pages managed by kalloc and kfree in kernel/kalloc.c. The whole…15 steps · ~27 min✓28Crossing the user/kernel boundary in memoryYou type ls README. To print one line, ls makes two system calls that carry pointers across the user/kernel boundary in opposite directions: open("README", …) hands the kernel the address of a string in…15 steps · ~26 min✓

File system

29A disk read, end to endYou type cat README. The first 512 bytes cat asks for live in disk block 48: in a fresh fs.img from this build, README is inode 2, its data blocks are 48, 49 and 50, and it is 2,441 bytes long (read straight out of…18 steps · ~30 min✓30The buffer cachexv6 keeps exactly 30 disk blocks in memory at a time. Every file-system operation, on every hart, goes through those 30 buffers: reading a directory, allocating a block, updating an inode, writing the log. The buffer…19 steps · ~30 min✓31The log: begin_op, commit and group commitAppending to a file changes several disk blocks: the free-block bitmap, the new data blocks, and the inode that points to them. If the power fails after some of those writes and before others, the disk is left…18 steps · ~30 min✓32Crash recoveryYou type echo hi > f on a freshly made disk, and the power goes out. Not before the command, not after it: in the middle of the kernel writing its changes to the disk. When the machine comes back, is there a file…20 steps · ~33 min✓33The life of an inodeYou type cat README &; rm README. Two programs start at once: cat opens README and starts printing it, and on another hart rm deletes it. And yet cat prints the whole file, to the last line. Only when cat closes…16 steps · ~27 min✓34Path lookupA program says open("/a/b/c"). The disk has no idea what /a/b/c means. It knows inode numbers and blocks. Somewhere between the two, the kernel must walk from the root directory to a, from a to b, from b to…15 steps · ~23 min✓35Creating and naming filesecho hi > newfile creates a file. That sounds like one action, but on the disk it is three: an inode must be found and marked used, a directory entry must be written that names it, and the directory’s own inode is…17 steps · ~26 min✓36Reading and writing a filewc README reads 2441 bytes, 512 at a time. echo hi > f writes three bytes, two of them in one write and the newline in another, and the second lands right after the first. Both look trivial from user space. In the…20 steps · ~29 min✓

Devices and putting it all together

37A keystroke's journeyThe shell has printed $ and is waiting. You press l, then s, then Enter. Within a fraction of a millisecond each letter appears on your screen, and after Enter the shell has the line "ls\n" in its buffer.…19 steps · ~37 min✓38Output to the console from three hartsThere is one screen and three harts. When several programs print at once, whose bytes go out first, and how finely can they be mixed? The answer in xv6 is precise, and it is decided by locks: a sleep lock that…15 steps · ~27 min✓39Pipesls | wc prints 24 96 608: ls produced 608 bytes and wc counted them, yet ls never knew wc existed, and neither program ever touched a file. Between them sat a pipe: 512 bytes of kernel memory, two counters, one…19 steps · ~32 min✓40Capstone: the shell running ls | wcYou type seven characters and press Enter:25 steps · ~45 min✓

The dance of privilege

41Every transition: mode, stack and page tableFreeze xv6 at any instruction, on any hart, and ask three questions. Which privilege mode? User, supervisor or machine. Which stack? Whatever memory sp points into. Which page table? Whatever satp names. If you can…20 steps · ~27 min✓42One hart's stacks, from power-on to the first user instructionEvery instruction a CPU executes runs with some value in sp, and that value is always a claim: “this is my stack.” This tour follows the claim on hart 0 from the moment QEMU powers it on, when sp is simply 0, to the…21 steps · ~30 min✓43A system call, CSR by CSRTour 5: Life of a system call followed echo hi’s write(1, "hi", 2) through the kernel’s layers. This tour follows the same system call with a different lens: the control and status registers (CSRs) and the…20 steps · ~31 min✓44One interrupt, three landing sitesA timer interrupt is the same event every time: on some hart, the clock passes stimecmp. But where it lands depends entirely on what that hart was doing. There are exactly three possibilities in xv6, and they differ…19 steps · ~28 min✓45One complete time slice on three hartsThis tour follows one complete time slice on one hart, from start to finish, and at every step it answers the master question (Mode, stack and page table: the master question): which mode, which stack, which page…19 steps · ~34 min✓46Boot: returning from a trap that never happenedA RISC-V hart can lower its privilege in exactly one way: by returning from a trap. mret returns from a machine-mode trap, sret from a supervisor-mode trap. There is no “enter supervisor mode” instruction. So to get…17 steps · ~25 min✓47Where a suspended process livesA process that is not running is not anywhere in the CPU. No hart holds its registers, no pc points into its code. Yet some hart can pick it up at any moment and continue it as if nothing had happened. So everything…17 steps · ~28 min✓48Breaking the invariantsThe transitions of this group work because a handful of rules hold at every instant: a lock here, interrupts off there, a page mapped twice, a register copied before it can be lost. The code states some of them as…18 steps · ~29 min✓

Locks and interrupt state

49Every lock in one ls | wcTour 40: Capstone: the shell running ls | wc drove ls | wc from the keyboard to the answer. This tour drives it again and counts every lock on the way: every acquire of a spinlock, every acquiresleep of a sleep-lock,…21 steps · ~36 min✓50noff and intena through a sleep, a yield and an interruptEvery hart keeps three small facts about interrupts. SIE is one bit in sstatus: may an interrupt be taken right now? noff (mycpu()->noff) counts how many push_off calls are still open. intena (mycpu()->intena)…22 steps · ~37 min✓51The lock-order graph, measuredTour 18: Lock ordering: how xv6 avoids deadlock derived xv6’s lock order by reading the code: find each place that holds two locks, check that it agrees with the others. This tour does the opposite. We let the…22 steps · ~38 min✓52Breaking the lock rulesxv6’s locking rests on a short list of rules: never acquire a lock you already hold; never sleep holding a spinlock; keep interrupts off while you hold one; let intena travel with the thread; register for a wakeup…17 steps · ~33 min✓