Step 1 of 21

You ask for a running system

make qemu names a target. Line 182 says what it depends on, and line 183 is the one command that produces it. Before running that command, make must make sure that every prerequisite exists and is up to date:

qemu
├── check-qemu-version         (QEMU at least 7.2)
├── kernel/kernel              ← 27 object files + kernel/kernel.ld
│     ├── kernel/entry.o       ← kernel/entry.S
│     ├── kernel/start.o       ← kernel/start.c + headers
│     └── ... 25 more
└── fs.img                     ← mkfs/mkfs, README, 20 user programs
      ├── mkfs/mkfs            ← mkfs/mkfs.c (compiled for YOUR machine)
      └── user/_cat, _echo, _init, _sh, ...
            └── user/cat.o + the user library (ulib.o, usys.o, ...)

make walks this graph from the leaves up. A file is rebuilt only if it is missing or older than something it depends on. That is why a second make qemu starts QEMU almost at once: everything is already newer than its sources.

make builds the prerequisites left to right: first the silent QEMU version check, then the kernel, then the disk (mkfs before the user programs it will copy), and finally it runs the emulator. This tour follows roughly that order.

Step 2 of 21

Finding a compiler for a CPU you do not have

Your computer’s CPU is probably an x86-64 or an ARM chip. xv6 runs on a 64-bit RISC-V CPU. Your system’s normal gcc produces the wrong machine code, so the kernel must be built with a cross-compiler / toolchain: a compiler that runs here but produces code for RISC-V.

Lines 38–53 try the common names for such a toolchain until one answers, and set TOOLPREFIX to its prefix: riscv64-unknown-elf-, riscv64-linux-gnu- or riscv64-elf- are the usual ones, depending on how your toolchain was installed. Lines 58–61 then set:

This site writes every toolchain command that way: ${TOOLPREFIX}gcc, ${TOOLPREFIX}objdump, ${TOOLPREFIX}readelf and so on. TOOLPREFIX is your RISC-V toolchain’s prefix, the same one the Makefile detects; to run the commands yourself, set it in your shell with export TOOLPREFIX=riscv64-unknown-elf- or whichever you have. On Debian/Ubuntu/WSL, gdb-multiarch also works as the debugger. The commands make prints below are shown the same way; on your screen they start with your prefix.

The test on each line runs that objdump -i and greps its list of file formats for elf64-big (a RISC-V objdump lists elf64-bigriscv). In practice it asks “does a tool by this name exist and run”; the prefix itself is what picks RISC-V.

Line 55 also fixes the emulator: qemu-system-riscv64, which pretends to be a whole RISC-V computer, CPUs, memory and devices included (QEMU).

Step 3 of 21

The kernel is 27 object files

OBJS lists every piece of the kernel, one object file per source file. make will build each from its .c or .S file and then link them into one program.

The order matters only once: $K/entry.o is first. The linker copies code into the output in the order of its inputs, so the first instruction of kernel/entry.S lands first, at 0x80000000, where every hart will start. kernel/kernel.ld:13 makes sure of it a second way, by naming the file kernel/entry.o: with entry.o moved to the end of the link, its code still lands first. (The (_entry) after the name asks for a section called _entry, and there is none; kernel/entry.S puts _entry in plain .text. It is the file name that does the work.)

Notice what is not here: no C library. There is no printf from your system, no malloc, no memcpy. The kernel brings its own: printk, kalloc, and the routines in kernel/string.c. A kernel cannot borrow a library that itself assumes a kernel underneath.

Step 4 of 21

Compiling one C file, with the real flags

There is no rule in the Makefile that says how to build kernel/main.o from kernel/main.c. make has a built-in one: $(CC) $(CFLAGS) -c -o $@ $<. So the command it prints is (shortened only where ... shows):

${TOOLPREFIX}gcc -Wall -Werror -Wno-unknown-attributes -O -fno-omit-frame-pointer
  -ggdb -gdwarf-2 -ffile-prefix-map=<your xv6 dir>=. -march=rv64gc -std=gnu99 -MD
  -mcmodel=medany -ffreestanding -fno-common -nostdlib -fno-builtin-strncpy ...
  -fno-builtin-vprintf -I. -fno-stack-protector -fno-pie -no-pie
  -c -o kernel/main.o kernel/main.c

The flags that make this a kernel compile:

• -march=rv64gc: emit 64-bit RISC-V with the common extensions (multiply, atomics, floating point, compressed 2-byte instructions). The atomic instructions matter: amoswap, which every spinlock uses, is part of the A extension that g includes.
• -mcmodel=medany: compute addresses relative to the current instruction, so code can live at 0x80000000 and above.
• -ffreestanding and the -fno-builtin-* list: do not assume a hosted C library, and do not treat calls to memset, printf, strlen… as the standard functions the compiler knows. xv6 has its own versions with its own behavior (kernel/string.c, printk). gcc may still emit calls to memset/memcpy on its own (for example for struct copies), which is one reason string.c defines them. (-nostdlib only matters when gcc links, and the kernel is linked by calling ld directly, so here it is just a safeguard.)
• -fno-stack-protector, -fno-pie -no-pie: no hidden runtime support that a bare machine cannot provide. Lines 81–89 add these only if this compiler understands them.
• -O -ggdb -fno-omit-frame-pointer: optimize a little but keep the code debuggable with gdb.

Step 5 of 21

What the compiler made of main.c

kernel/main.o is a RISC-V ELF object file (.o), not a program. Its code starts at address 0, because the compiler has no idea where the linker will put it. And it is full of holes. Disassembling it (${TOOLPREFIX}objdump -dr kernel/main.o) shows:

0000000000000000 <main>:
   0: 1141       addi sp,sp,-16
   ...
   8: 00000097   auipc ra,0x0
                 8: R_RISCV_CALL_PLT  cpuid
   c: 000080e7   jalr  ra
  10: 00000717   auipc a4,0x0
                 10: R_RISCV_PCREL_HI20  started

auipc ra,0x0 is a placeholder. The line below it is a relocation, a note to the linker: “when you know where cpuid is, patch this instruction”. main.c calls cpuid but does not define it; proc.o does. Each object file is compiled alone, knowing only the declarations in kernel/defs.h.

The same happens to started, the flag on line 7. In main.o its address is a relocation too. Only after linking will it be a real address: 0x8000786c, a single 4-byte variable that all three harts will read in Tour 3: main: one hart builds the kernel, the others wait.

Step 6 of 21

-MD teaches make which headers matter

The -MD flag in CFLAGS makes the compiler write a second file while it compiles: kernel/main.d, a tiny Makefile fragment listing every header main.c actually included:

kernel/main.o: kernel/main.c kernel/types.h kernel/param.h \
 kernel/memlayout.h kernel/riscv.h kernel/defs.h

Line 157 pulls all those fragments into the Makefile (-include does nothing if they do not exist yet, as on a first build; -include). From the second build on, make knows that changing kernel/param.h, say NCPU, must recompile main.o and every other file that includes it.

Without this, a header change would leave stale object files compiled against the old definition. For a kernel, where two files must agree on the exact layout of struct proc or struct spinlock, that is a recipe for corrupting memory in ways that look like a concurrency bug.

Step 7 of 21

Assembling a .S file

Four kernel files are assembly: entry.S, swtch.S, trampoline.S and kernelvec.S (user programs add a fifth, the generated usys.S). kernel/entry.S is the first code any hart runs. Its rule is Makefile:98:

${TOOLPREFIX}gcc -march=rv64gc -g -ffile-prefix-map=<dir>=. -c -o kernel/entry.o kernel/entry.S

gcc runs the C preprocessor over a capital-.S file (so #include works, as in trampoline.S) and then the assembler. The output has some surprises:

• la sp, stack0 (line 12) is a pseudo-instruction. It becomes two real instructions, auipc sp + addi sp, with relocations against stack0.
• li a0, 1024*4 becomes lui a0,0x1: the assembler does the multiplication.
• call start becomes auipc ra + jalr ra, 8 bytes, with a relocation.

The .o file is 32 bytes of code. After linking, call start has shrunk to a single 4-byte jal 80000058 <start>: the linker saw that start was close enough and relaxed the call. That is why spin ends up at 0x8000001a, not 0x8000001e.

Step 8 of 21

The trampoline asks for a page of its own

Most code goes into a section called .text. kernel/trampoline.S puts its code in a section with a made-up name, trampsec. The name means nothing to the assembler; it exists so that the linker script can find this code and treat it specially.

Why special? The trampoline is the code that switches between user and kernel page tables (trampoline page). The kernel will map this one page at the same virtual address, the highest page xv6 uses (MAXVA - PGSIZE), in the kernel’s page table and in every process’s page table. To map it alone, it must start on a page boundary and fit in one 4096-byte page, with nothing else sharing the page.

The assembler cannot guarantee that. It only knows about this one file. The linker, which sees everything, will: next step.

Step 9 of 21

Linking 27 objects into one kernel

Once every object exists, line 94 runs:

${TOOLPREFIX}ld -z max-page-size=4096 -T kernel/kernel.ld -o kernel/kernel
               kernel/entry.o kernel/start.o ... kernel/virtio_disk.o
${TOOLPREFIX}ld: warning: kernel/kernel has a LOAD segment with RWX permissions

The linker resolves every relocation: main.o’s call to cpuid is patched with cpuid’s final address, and so on, thousands of times. It refuses to finish if a function is called but defined nowhere.

The warning is real and harmless here. kernel.ld places code and data back to back without asking for separate segments, so ld puts all of them in one loadable segment marked read, write and execute. Nothing enforces those flags: QEMU just copies the bytes into RAM, and paging is off at first. Protection comes later, from the kernel’s own page table, which maps code read-and-execute and data read-and-write (Tour 24: The kernel page table and turning paging on).

Lines 95–96 then write two files for humans: kernel/kernel.asm, the whole kernel disassembled with the C source interleaved, and kernel/kernel.sym, one line per symbol with its address. Every address in these tours comes from them.

Step 10 of 21

kernel.ld puts the code at 0x80000000

The linker script decides where everything goes. Line 10 starts at 0x80000000 because on QEMU’s virt machine, RAM starts there and the boot ROM jumps there. In this build, from kernel/kernel.sym:

The kernel’s ordinary code ends somewhere below 0x80006000. Line 15 pads to the next page, line 17 places trampsec there, line 18 pads again, and the ASSERT on line 19 stops the build if the trampoline ever outgrows its page. So the trampoline is exactly one page, 0x80006000–0x80007000, and etext is page-aligned.

That alignment is not cosmetic. kvmmake will map KERNBASE–etext as read+execute and everything above as read+write, page by page. If etext fell in the middle of a page, one page would have to be both.

Step 11 of 21

kernel.ld lays out the data, and marks the end

After the code come the constants, the initialized data, and the zero-initialized data (.bss section). In this build:

Almost all of the kernel’s data is in .bss. The biggest objects are the tables every hart will share: bcache (0x86c0 bytes at 0x800157e8), stack0 (0x8000 bytes at 0x80007890: one 4 KiB boot stack for each of up to 8 CPUs, which each hart keeps for good as its scheduler stack; see The stacks of xv6), proc (64 processes, 0x5a00 bytes at 0x8000fdd0), the inode table, the file table, and cpus.

.bss takes no space in the file: the program header records a memory size (0x20bb0) larger than the file size (0x7860), and QEMU provides zeroed memory. So of kernel/kernel’s 287,512 bytes, only 0x7860 (30,816) are code and data that get loaded; the rest is symbols and debugging information.

end is where the kernel stops and free memory begins. kinit will hand every page from end (rounded up to 0x80021000) to 0x88000000 to the page allocator.

Step 12 of 21

User programs, the user library and the system-call stubs

The disk needs programs, and user programs are built differently from the kernel.

• Each is linked from its own object file plus ULIB, the tiny user library: ulib.o (string functions and start), printf.o, umalloc.o, and usys.o.
• usys.S does not exist in the source tree. Lines 111–112 generate it by running the Perl script user/usys.pl, which prints one three-instruction system call stub per system call: li a7, SYS_<name>; ecall; ret. Generating it keeps the stubs in step with kernel/syscall.h.
• The pattern rule on line 106 makes user/_init from user/init.o, linked with user/user.ld instead of the kernel’s script. The leading underscore keeps your own system from confusing user/_cat with its cat.

The real link command for the first program in the list:

${TOOLPREFIX}ld -z max-page-size=4096 -T user/user.ld -o user/_cat
               user/cat.o user/ulib.o user/usys.o user/printf.o user/umalloc.o

Step 13 of 21

Every user program starts at address 0

The kernel is linked at 0x80000000; every user program is linked at 0. Two programs at the same address cannot both live in physical memory there, and they do not have to: each process will get its own page table that maps its virtual address 0 to wherever its pages really are (Tour 25: A user address space).

For user/_init in this build (${TOOLPREFIX}readelf -l):

There is no ENTRY line, so ld uses the symbol start as the entry point: start in user/ulib.c, at 0xbc in _init. That number will reappear in Tour 4: From the first process to the shell prompt as the very first user-mode program counter.

The data segment starts on a fresh page (line 23) so that kexec can map the code pages without write permission and the data pages with it.

Step 14 of 21

mkfs is compiled for your computer, not for RISC-V

Look at the compiler on line 124: plain gcc, not $(CC). The real command is

gcc -Wno-unknown-attributes -I. -o mkfs/mkfs mkfs/mkfs.c

mkfs/mkfs.c is not part of xv6. It is a tool that runs now, on your computer, to write the disk image xv6 will boot from. It includes the kernel’s own kernel/fs.h and kernel/param.h (line 123 lists them as prerequisites), so the disk it writes uses exactly the block size, inode layout and directory format the kernel will expect. Change struct dinode in fs.h, and both sides rebuild.

One subtlety: the image must be in RISC-V byte order (little-endian), whatever your computer uses. xint and xshort in mkfs.c put every multi-byte number into that order explicitly (byte order (endianness)).

Step 15 of 21

fs.img depends on every user program

UPROGS lists the 20 programs that will be on the disk. The rule on lines 154–155 says fs.img depends on mkfs, the README, and all of them, and the command runs mkfs with the image name followed by every file to copy in:

mkfs/mkfs fs.img README user/_cat user/_echo user/_forktest ... user/_sync

The order on this command line becomes the order of files in the root directory and the order of their inode numbers: README gets inode 2, cat 3, echo 4, and so on, down to sync at 22. Root, the directory itself, is inode 1.

mkfs strips user/ and the leading _, so user/_sh becomes /sh. user/init.c:34 runs it with exec("sh", …), a path looked up from the root directory.

Step 16 of 21

mkfs plans the disk

The disk layout (xv6 file system) is decided by four constants: FSSIZE = 2000 blocks of BSIZE = 1024 bytes, LOGBLOCKS = 30, and NINODES = 200 (line 23). The first thing mkfs prints is the result:

nmeta 47 (boot, super, log blocks 31, inode blocks 13, bitmap blocks 1) blocks 1953 total 2000

Line 114 first writes 2000 blocks of zeros, so fs.img is exactly 2000 × 1024 = 2,048,000 bytes. The superblock records logstart = 2, inodestart = 33, bmapstart = 46. Those three numbers are all the kernel needs to find everything else: the first thing the kernel’s file system does at boot, readsb, is to read block 1 (Tour 4: From the first process to the shell prompt).

Step 17 of 21

The root directory and the files

ialloc hands out inode numbers in order from 1, so the root directory gets inode 1, as ROOTINO requires (line 122 checks). Its first two entries are . and .., both pointing at itself.

Then each file on the command line gets the next inode, a directory entry in root (a 16-byte directory record: 2-byte inode number, 14-byte name), and its bytes copied in with iappend. What this build’s fs.img contains:

Why is init, which is about 2.5 KB of code and data, 37 KB on disk? The programs are compiled with -ggdb, and the debugging information is copied too. kexec will load only the parts the ELF headers ask for.

Notice there is no console file. mkfs creates only directories and regular files. The device file appears at first boot, when init finds it missing and creates it (Tour 4: From the first process to the shell prompt).

Step 18 of 21

iappend hands out blocks in order

iappend adds bytes to the end of a file. When the write crosses into a new block, it takes the next free block number, freeblock++, starting at 47. There is no allocator and no search: this is a fresh disk, and blocks are handed out like tickets.

The first 12 blocks of a file go straight into the inode’s addrs[0..11] (inode). Beyond that, iappend allocates an indirect block, a block holding up to 256 more block numbers. For init (37,296 bytes = 37 blocks):

• blocks 189–200: the first 12 data blocks, listed in the inode;
• block 201: the indirect block;
• blocks 202–226: the remaining 25 data blocks.

kill, the next file, starts at 227. usertests, at 205 blocks, is the largest file on the disk; even it fits within one indirect block.

Every block is read, changed and written back with rsect and wsect, which lseek in the image file to block × 1024. To mkfs, the disk is just an ordinary file on your computer.

Step 19 of 21

Marking the used blocks

After the last file, freeblock is 1006. Back in main, line 176 calls balloc, which sets bits 0 through 1005 of the bitmap and writes it to block 46:

balloc: first 1006 blocks have been allocated
balloc: write bitmap block at sector 46

Blocks 0–46 are the metadata and 47–1005 hold the root directory and 21 files, so the kernel will find 994 free blocks (1006–1999) when a program creates a file.

mkfs exits, and fs.img is done. This 2-megabyte file on your computer is the xv6 disk. When xv6 later writes a file, QEMU writes into it, and those changes persist until make clean deletes it, or until make rebuilds it because mkfs, README or a user program changed (the Makefile comment on lines 126–129 is about keeping that from happening needlessly).

Note one thing mkfs can do that the kernel never can: it writes blocks in any order with no thought for crashes or for other CPUs. It is a single program on an idle disk. The kernel will need a log for crashes (Tour 31: The log: begin_op, commit and group commit) and locks for its three harts.

Step 20 of 21

The QEMU command line

Everything is built. Line 183 runs (this build, all options expanded):

qemu-system-riscv64 -machine virt -bios none -kernel kernel/kernel -m 128M -smp 3
  -nographic -global virtio-mmio.force-legacy=false
  -drive file=fs.img,if=none,format=raw,id=x0
  -device virtio-blk-device,drive=x0,bus=virtio-mmio-bus.0

force-legacy=false selects the modern virtio interface, which virtio_disk_init insists on (it checks for version 2). Try make qemu CPUS=1 and the same kernel boots on one hart; nothing in the kernel is compiled for a particular count, up to NCPU = 8.

Step 21 of 21

What the build decided, and what it left to the harts

QEMU creates three harts and lets them go. From here on the story belongs to the machine, starting at Tour 2: Power-on to main, on every hart at once.

Look back at what the build fixed in advance:

• Addresses. Every function and global has a final address (main at 0x80000e5e, started at 0x8000786c). All three harts will use these same addresses.
• Sizes. The process table holds 64 entries, the buffer cache 30 blocks, the boot stacks 8 CPUs’ worth. These are arrays in .bss, not allocated at run time.
• The disk. 2000 blocks, init at inode 7, sh at inode 13, block 47 holding the root directory.

And what it could not fix: which hart does what, and when. The build produced one kernel image and zero locks. In Tour 2: Power-on to main, on every hart at once the three harts run the same first instructions without any lock at all, because each touches only its own registers and its own stack. In Tour 3: main: one hart builds the kernel, the others wait, hart 0 starts writing the shared tables the linker just laid out, creating the first spinlocks (cons.lock, pr.lock, kmem.lock, …) as it goes, while harts 1 and 2 wait on a flag.