Glossary

.align

.globl / .global

.section

__attribute__

atomic operation and memory ordering

Different harts may see each other’s writes late or in a different order than they were written, and the compiler may reorder memory accesses too. The GCC built-ins used by xv6 fix this:

• __atomic_store_n(&flag, 1, __ATOMIC_RELEASE): every memory write this hart did before this store is visible to any hart that reads flag == 1 with an acquire load.
• __atomic_load_n(&flag, __ATOMIC_ACQUIRE): once this load sees the new value, reads that come after it see everything the releasing hart wrote before its store.

Used as a pair, they make a one-way “ready” signal. See kernel/main.c.

compound literal

It behaves like a variable you never had to name. Inside a function it has automatic storage, like a local variable: it exists until the enclosing block ends. xv6 uses one in forkret to build the argv array for kexec without declaring a separate array.

empty parentheses in a C declaration

format string

In printk("hart %d starting\n", cpuid()), the text hart , starting and the newline are printed literally, and %d is replaced by the next argument in decimal. %% prints a single %.

Kernel printk understands %d, %ld, %lld, %u, %lu, %llu, %x, %lx, %llx, %p, %c, %s and %%, with no widths, padding or precision; see kernel/printk.c. User-space printf (user/printf.c) has its own, similar set.

inline assembly (asm volatile)

static inline

static_assert

Compare assert(condition) from <assert.h>, which checks when the program runs and aborts it if the condition is false. A static assertion costs nothing at run time and catches the problem before the program can produce wrong output, but it only works for conditions the compiler can evaluate, such as sizeof(int) == 4. mkfs/mkfs.c uses one, and carries a fallback macro that is used wherever static_assert is not already defined as a macro: with pre-C11 compilers, and with GCC in C23 mode on glibc, where it is a keyword and not a macro.

variadic function

The function itself cannot find out how many extra arguments there are or what their types are; the caller must tell it some other way. printk learns both from its format string: each %d means “the next argument is an int”.

va_list ap;            // cursor over the extra arguments
va_start(ap, fmt);     // start after the last named parameter
int x = va_arg(ap, int);  // take the next one, as an int
va_end(ap);            // finish

Arguments smaller than int (such as char) are promoted to int when passed, and float to double. Calling va_arg with a type that does not match what was passed, or reading more arguments than were passed, is undefined behavior: the compiler does not check it. That is why xv6 marks printk with __attribute__((format(printf, 1, 2))), which makes the compiler check calls against the format string.

volatile

designated initializer

Designated initializers come from C99. They let a table be written in terms of symbolic indices, so that the order of the lines does not matter and a gap in the numbering leaves a zero (null) entry instead of shifting everything after it:

static char *names[] = { [3] = "three", [1] = "one" };  // names[0] and names[2] are 0

function pointer

A function’s name used without parentheses is its address, so f = sys_fork; stores a pointer and f() calls sys_fork. An array of function pointers is a common way to dispatch on a number, as syscalls does:

static uint64 (*syscalls[])(void) = { [SYS_fork] = sys_fork, ... };
p->trapframe->a0 = syscalls[num]();

A cast can turn an integer address into a function pointer, as forkret does to call userret at its trampoline page address.

-c / -o / -E / -x / -S / -t

-ffile-prefix-map

-fno-builtin-NAME

-fno-common

-fno-omit-frame-pointer

-fno-pie / -no-pie

-fno-stack-protector

-g / -ggdb / -gdwarf-2

-I.

-march=rv64gc

-mcmodel=medany

-MD

-nostdlib

-O

-std=gnu99

-Wall / -Werror / -Wno-...

16550 UART registers

On QEMU’s virt machine they sit at UART0 = 0x10000000 (register n at 0x10000000 + n), accessed with memory-mapped I/O. The ones xv6 uses, and the bits it uses:

While LCR bit 7 (DLAB) is 1, offsets 0 and 1 instead reach the low (DLL) and high (DLM) bytes of the baud-rate divisor; the bit rate is the input clock divided by 16 × divisor. xv6 sets the divisor in uartinit and then clears DLAB.

With the FIFOs enabled, the chip queues up to 16 bytes in each direction; LSR bit 0 then means “the receive FIFO is not empty” and bit 5 means “the transmit FIFO is empty”. Offsets 4, 6 and 7 (modem control, modem status, scratch) exist but xv6 never touches them. See kernel/uart.c.

address space

Switching satp switches the address space. The kernel runs on kernel_pagetable; the trampoline code in kernel/trampoline.S switches to a process’s page table on the way to user mode and back to the kernel’s on every trap. Because user memory is not mapped in the kernel’s address space, the kernel reaches it by translating user addresses in software (copyin, copyout).

argc and argv (program arguments)

When you type echo hi, the shell calls exec("echo", argv) with argv = {"echo", "hi", 0}. The kernel (kexec) copies the strings and the pointer array onto the new program’s user stack and starts the program with argc in register a0 and the address of the array in a1, which is exactly where the RISC-V calling convention puts the first two arguments of a function. xv6 allows at most MAXARG - 1 = 31 arguments.

background job (&)

xv6’s shell gets this effect with an extra process. The child it forks for the command line forks again, lets the grandchild run the command, and exits immediately. The shell’s wait returns right away and it prints the next prompt.

The grandchild is now an orphan: its parent has exited. The kernel hands it to init (reparent), whose endless wait loop (user/init.c) collects it when it finishes, so it does not stay a zombie forever. xv6 has no job control: you cannot list, stop or bring back background jobs, and their output can appear in the middle of your next command line.

block

The disk device itself works in 512-byte sectors, so one xv6 block is two sectors; virtio_disk_rw converts a block number into a sector number by multiplying by 2. Everything above the driver (the buffer cache, the log, the file system in kernel/fs.c) thinks only in blocks. How the 2000 blocks of fs.img are used is described under disk layout (xv6 file system).

boot

boot stack (stack0)

stack0 is 4096 * NCPU bytes in the kernel’s .bss, at 0x80007890 in this build. Hart h starts with sp = stack0 + (h + 1) * 4096, the top of its slice: 0x80008890 for hart 0, 0x80009890 for hart 1, 0x8000a890 for hart 2. The address is physical while paging is off, and stays valid after kvminithart turns paging on, because the kernel maps its data at the same virtual address (direct map).

There are no guard pages between or around the slices. A hart that overflowed its slice would silently overwrite the top of the slice below (where that hart keeps its start, main and scheduler frames) or, for hart 0, kernel variables such as ticks. See The stacks of xv6.

buffer cache

xv6 has NBUF (30) buffers. They are kept on a list ordered by how recently they were released, so that when a new block is needed the least recently used free buffer is recycled. A buffer that the log has modified but not yet written home is pinned (bpin) so that it cannot be recycled and lose the change.

byte order (endianness)

The 4-byte number 0x10203040 is stored as the bytes 40 30 20 10 on a little-endian machine and 10 20 30 40 on a big-endian one. Inside one program this never matters: the CPU reads back what it wrote. It matters as soon as bytes travel between machines, for example a disk image written by one computer and read by another.

mkfs/mkfs.c runs on your computer but writes numbers that the RISC-V kernel will read, so it converts them with xint and xshort, which always produce the little-endian layout. Almost every computer you are likely to build on (x86-64, 64-bit ARM) is little-endian too, so on them these functions change nothing.

calling convention

console

The first user program, init, creates /console with mknod (device number CONSOLE = 1) and opens it as file descriptors 0, 1 and 2 (standard input, output and error). Every process it starts inherits them, so the shell and the programs it runs read and write the console without opening anything.

A read or write on such a descriptor goes through the device table devsw to consoleread or consolewrite in kernel/console.c. Kernel messages bypass the file layer and go straight to the UART through printk and consputc.

context switch

Every xv6 process has a kernel thread: its kernel stack plus the registers saved in p->context. Each CPU’s scheduler is a thread too, with its registers in cpus[i].context. A switch from process A to process B is two switches: A to the scheduler (in sched) and the scheduler to B (in scheduler).

swtch saves only ra, sp and the callee-saved registers s0–s11. The rest are either already saved by the C code that called swtch (because the calling convention lets a call destroy them) or belong to the CPU rather than the thread (such as tp). The user registers are not involved: they were saved in the trapframe when the process entered the kernel.

crash recovery

critical section

A lock does not protect code; it protects data. Every piece of code that touches the data must hold the same lock, or the lock protects nothing. That is why xv6 writes, next to each shared variable, which lock guards it (for example the comments in struct proc, kernel/proc.h:85).

Keeping critical sections short matters: other CPUs that want the same lock spin, doing no useful work, until it is released.

CSR (control and status register)

Each CSR has a name and a 12-bit number. Its name usually starts with the lowest privilege mode allowed to access it: m... CSRs (like mstatus) are for machine mode only, s... CSRs (like sstatus) for supervisor mode and above. Touching a CSR from a mode that is not allowed raises an illegal-instruction exception. xv6 wraps every CSR it uses in a tiny C function in kernel/riscv.h, such as r_mstatus and w_mstatus.

deadlock

Two ways it happens in a kernel like xv6:

• Lock ordering. CPU 1 holds lock A and waits for B; CPU 2 holds B and waits for A. xv6 prevents this by always acquiring locks in a fixed global order. For processes: wait_lock before any p->lock (kernel/proc.c:23).
• Interrupt on the same CPU. Code holds lock A; an interrupt arrives on the same CPU and its handler tries to acquire A. The handler spins forever, because the code that would release A cannot run until the handler returns. xv6 prevents this by turning interrupts off while any spinlock is held; see interrupts and spinlocks (push_off / pop_off).

acquire also panics if a CPU tries to take a lock it already holds, which would otherwise deadlock the CPU with itself.

The measured order of every lock in the kernel is on Locks and interrupt state; see also lock order.

device interrupt

The path through xv6:

1. The device signals the PLIC. If that source is enabled for a hart’s supervisor mode and its priority is above the hart’s threshold (plicinithart), the PLIC raises the hart’s external-interrupt line.
2. The hart takes a trap with scause = 0x8000000000000009 once interrupts are enabled (see trap cause (scause values)).
3. devintr asks the PLIC which device it was (plic_claim), calls that driver’s handler (uartintr or virtio_disk_intr), then tells the PLIC it is done (plic_complete).

Timer interrupts are not device interrupts in this sense: they come from the hart’s own timer (Sstc), not through the PLIC.

dinode (on-disk inode)

Defined as struct dinode in kernel/fs.h. Inode number i lives in block i / 16 + sb.inodestart (IBLOCK), at slot i % 16. A type of 0 means the inode is free. The kernel copies a dinode into the in-memory struct inode in ilock and back out in iupdate.

direct map

kvmmake builds the direct map: everything from KERNBASE (0x80000000) to PHYSTOP, plus the UART, virtio and PLIC registers. The exceptions are the TRAMPOLINE page and the per-process kernel stacks, mapped at high virtual addresses that do not match their physical ones.

This is what lets walk follow page-table pointers, which are physical addresses, and what lets copyin and copyout reach a user page through its physical address.

directory

The entry format is struct dirent in kernel/fs.h. An entry whose inode number is 0 is an unused slot. Every directory contains . (itself) and .. (its parent); in the root directory both refer to the root, inode 1. dirlookup searches a directory and dirlink adds an entry.

disk layout (xv6 file system)

For the default fs.img (FSSIZE = 2000 blocks of 1024 bytes):

DMA (direct memory access)

Because the device uses physical addresses and knows nothing of page tables, a driver must hand it physical addresses. In xv6 the kernel’s own memory is mapped at virtual addresses equal to physical ones, so virtio_disk_rw can pass kernel pointers such as b->data directly. (On QEMU the “device” is software in QEMU that accesses the guest’s RAM, but the driver sees the same behavior as with real DMA.)

exception

exec

exec(path, argv) does not return if it succeeds: the code that called it no longer exists. If it fails (no such file, not an executable, out of memory), it returns -1 and the old program continues. Unix creates new programs by combining fork, which duplicates a process, with exec in the child; the gap between the two is where the shell sets up redirections and pipes.

In xv6 the work is split between sys_exec, which copies the arguments into the kernel, and kexec in kernel/exec.c, which builds the new memory image.

exit status

In xv6, kexit stores the status in the dying process’s p->xstate and the process becomes a zombie until its parent calls wait(&status); kwait then copies xstate out to the parent. A user program that returns from main exits with main’s return value, because the library’s start function calls exit(main(...)) (user/ulib.c).

The convention is only a convention. Nothing in the kernel treats 0 specially, and xv6’s own shell (user/sh.c) passes 0 to wait and so never looks at the status at all. Several xv6 utilities (mkdir, rm, ln, kill) exit with 0 even when the operation failed. On Unix systems whose shells do test the status (make, &&, if), that would hide errors; in xv6 nobody checks.

file descriptor

Descriptors are per process: descriptor 3 in one process and descriptor 3 in another can name entirely different files. By convention 0 is standard input, 1 standard output and 2 standard error; in xv6 all three start out as the console, opened by /init and inherited by every process after it.

A new descriptor is always the lowest free number (fdalloc). fork copies the whole table, so parent and child share the same open files (filedup); exec keeps it unchanged, so a program inherits the descriptors of the program that ran it. The shell builds redirections and pipelines from these rules: close descriptor 1, then open or dup something, and it lands in slot 1.

The same descriptor can refer to a file on disk, a device such as the console, or one end of a pipe; read and write work the same way on all of them.

fork and exec

Splitting “make a process” from “load a program” looks wasteful but gives the child a window to adjust its own state between the two calls: close and reopen descriptors (I/O redirection), connect pipes (pipeline (a | b)), change directory. exec keeps open descriptors, so the new program inherits the result without knowing anything about it. The shell (user/sh.c) is built on this pattern.

The path through xv6: user fork() is a stub in user/usys.S that executes ecall; the kernel dispatches to sys_fork, which calls kfork. exec() reaches sys_exec and then kexec; wait() reaches kwait.

free bitmap

One 1024-byte bitmap block has 8192 bits (BPB), so the 2000-block default disk needs a single bitmap block. Block b’s bit is bit b % 8 of byte (b % 8192) / 8 in bitmap block b / 8192 + sb.bmapstart (BBLOCK). The bits for the boot block, superblock, log, inode blocks and the bitmap itself are set by mkfs/mkfs.c, so they are never allocated.

free-list allocator

xv6 has two:

• The kernel’s page allocator (kernel/kalloc.c) is the simplest possible case: every block is one 4096-byte page, so any free block fits any request and the list needs no sizes and no ordering.
• The user library’s malloc (user/umalloc.c) is the classic allocator from Kernighan and Ritchie’s The C Programming Language. Blocks have any size (in 16-byte units). The list is circular and sorted by address. malloc takes the first block that is big enough, cutting the request off its end if it is bigger; free puts the block back in address order and merges it with a free neighbor directly before or after it, so that freed memory does not stay split into ever smaller pieces (fragmentation). When nothing fits, the allocator asks the kernel for more memory with sbrk.

Because the bookkeeping lives inside the memory it manages, a program that writes past the end of a malloced block, or frees a block twice, damages the list, and the failure usually shows up much later, somewhere else.

guard page

xv6 has two kinds. Each kernel stack (KSTACK) has an unmapped page below it in the kernel page table; overflowing into it makes the kernel fault and eventually panic (not cleanly: the trap handler’s own register saves spill into the next stack down first). Each user stack has a page below it whose PTE (page-table entry) is valid but has the U bit cleared (uvmclear in kexec), so a user-mode access faults and the process is killed.

hard link

After ln a b, the names a and b refer to the same inode: the same data, the same size, the same inode number (ls shows it in the third column). Writing through one name changes what you read through the other. The inode’s link count (nlink) counts the names; rm a removes only the name a and decrements the count, and the file’s blocks are freed only when the count reaches zero and no process has it open.

Hard links only work inside one file system (an entry stores an inode number, which is only meaningful on its own disk), and xv6 refuses to make one to a directory (sys_link), because a second name for a directory could create a cycle in the tree. Many Unix systems also have symbolic links, files that contain another path; xv6 does not.

hart

Every hart has its own registers, its own program counter and its own copy of most control and status registers. All harts share the same physical memory. xv6 calls them “CPUs” in comments and C names (struct cpu, cpuid) and “harts” when talking to the hardware (mhartid).

heap

A program’s memory has three kinds of storage: global variables (fixed size, decided when the program is linked), local variables on the stack (released when the function returns), and the heap, for data whose size or lifetime is known only while the program runs, such as the parse tree that user/sh.c builds for each command.

The kernel knows nothing about individual heap blocks. It only tracks one number per process, its size p->sz; everything between the end of the stack and p->sz is the heap (see user memory layout). sbrk(n) moves that end up by n bytes and returns the old end. The user-level allocator in user/umalloc.c carves those bytes into blocks, keeps freed blocks on a free list for reuse, and never gives memory back to the kernel.

I/O redirection

The trick depends on one rule: a new file descriptor always gets the lowest free number (fdalloc). For wc > out, the child process that will run wc does close(1) and then open("out", ...). Descriptor 1 is now the lowest free slot, so the file lands there. Then it calls exec; descriptors survive exec, so wc writes “to standard output” as always, and the bytes go into out (user/sh.c).

Because the change happens in the child after fork, the shell’s own descriptors are untouched, and its next prompt still goes to the console.

In xv6, > opens the file with O_TRUNC (empty it first). >> exists in the parser but xv6 has no append mode, so it writes from the beginning of the file without truncating it, overwriting the old bytes instead of adding after them.

indirect block

The 13th address in an inode, addrs[12] (index NDIRECT), points to the indirect block. Its 1024 bytes are read as 256 uint block numbers (NINDIRECT), for the file’s blocks 12 to 267. bmap allocates it the first time a file grows past 12 blocks, and itrunc frees it.

inode

xv6 has two forms of every inode. The on-disk form, dinode (on-disk inode), sits in the inode blocks of the disk. The in-memory form, struct inode, is a copy the kernel keeps in itable while the inode is in use, with extra bookkeeping: a reference count (ref), a valid flag saying whether the copy has been read from disk, and a sleep lock.

The usual way to use one is

ip = iget(dev, inum);   // or namei(path), dirlookup(...)
ilock(ip);              // lock, and read from disk if needed
... use or change ip->size, ip->type, the content ...
iunlock(ip);
iput(ip);               // drop the reference

See kernel/fs.c for the functions and the rules about which lock protects what.

inode number

Called inum in the code. Given the number, the kernel can compute where the inode lives on disk with IBLOCK. fstat reports it to user programs as ino in struct stat.

intena

It is recorded only when noff goes from 0 to 1, so it is 1 in a system call (after usertrap enabled interrupts) and 0 in interrupt handlers, in the scheduler and at boot. It belongs to the kernel thread, not to the hart: sched saves it across swtch and restores it, and the scheduler sets it to 0 after each switch back. When noff is 0 its value is stale and unused. See Locks and interrupt state and Locks and interrupt state.

interrupt

A supervisor-level interrupt is taken only if its bit in sie is set, and either the hart is running in U-mode, or it is in S-mode with the global SIE bit in sstatus set. xv6 enables the individual bits once at boot in start and toggles the global bit with intr_on and intr_off.

interrupts and spinlocks (push_off / pop_off)

Example: sys_pause holds tickslock. If a timer interrupt arrived on the same CPU (on hart 0, which counts ticks), clockintr would try to acquire tickslock and spin forever, since the code that holds it is the code the interrupt paused. With interrupts off the timer interrupt stays pending and is taken right after the release.

Locks nest, so a plain “off on acquire, on on release” would turn interrupts back on when the inner lock is released while the outer one is still held. Instead each CPU keeps two fields in its struct cpu: noff, the nesting depth, and intena, whether interrupts were on before the outermost push_off. Only the pop_off that brings noff back to 0 may turn interrupts on, and only if intena says they were on.

intena belongs to the kernel thread, not the hart: other threads (the scheduler, other processes) overwrite mycpu()->intena while a process is switched out. So sched keeps the process’s value in a local variable across swtch and puts it back, and the scheduler sets it to 0 after every switch back to itself (kernel/proc.c:456). See Locks and interrupt state and Locks and interrupt state.

kernel

kernel stack

The kernel cannot run on the user stack: user code controls sp and could point it anywhere. So each process slot gets a page of kernel memory, allocated and mapped in the kernel page table at KSTACK(i) for slot i by proc_mapstacks while the kernel boots. The stack belongs to the slot, not to a process: allocproc and freeproc never touch it, and whichever process occupies the slot runs on it. No user page table maps it. The page below each stack is left unmapped as a guard page, so an overflow causes a page fault instead of silently overwriting a neighbor.

On every trap from user mode, sp holds the kernel stack’s address from kernel/trampoline.S:76 to kernel/trampoline.S:118, and the stack is usable from kernel/trampoline.S:92 (kernel page table) until kernel/trampoline.S:111 (user page table). It always starts at the top: the stack is empty whenever the process is in user mode. A process is also back on its kernel stack whenever swtch resumes it. A kernel stack is also where a sleeping or preempted process’s kernel state lives: the call chain that led to sched stays on it until the process runs again, on any hart. A forked child starts with an empty one, not a copy of its parent’s. The scheduler does not run on a kernel stack; it has the hart’s scheduler stack. See The stacks of xv6.

kernelvec frame

The frame lands on whatever stack was active: a process’s kernel stack (an interrupt during a system call) or the hart’s scheduler stack (an interrupt in the scheduler’s interrupt window). It holds ra, gp, t0–t2, a0–a7 and t3–t6; the slots for sp, tp and s0–s11 stay unused.

If the trap was a timer interrupt and the hart has a current process, kerneltrap calls yield, and the process is suspended with the frame in the middle of its kernel stack. It may be resumed on another hart, which is why kernelvec does not restore tp (kernel/kernelvec.S:44). Handlers run with interrupts off, so in normal operation a stack holds at most one such frame. See The stacks of xv6.

line editing (cooked input)

Unix systems call this “canonical” or “cooked” mode, as opposed to “raw” mode, in which a program receives every key the moment it is pressed. xv6 has only the cooked mode, implemented in consoleintr:

Because editing happens in the kernel, a program such as the shell needs no code of its own for backspace: by the time its read returns, the line is already final.

link count (nlink)

It is a different count from the in-memory reference count. A file’s space is freed only when both are zero: no name leads to it and no one has it open. That is why a file removed with rm while another process reads it keeps working until it is closed. In xv6, a directory’s nlink also counts the .. entries of its subdirectories (but not its own .).

lock order

In xv6: sleep-locks before spinlocks, a condition lock (cons.lock, pi->lock, tickslock, log.lock, disk.vdisk_lock, a sleep-lock’s inner spinlock) before p->lock, and wait_lock before any p->lock (the comment at kernel/proc.c:23). p->lock is taken after almost everything; only pid_lock, kmem.lock, ftable.lock and itable.lock are ever taken while holding it: for a process slot being built, and (kmem.lock only) when kwait frees a zombie child under the child’s lock. The graph, measured on a running system, is on Locks and interrupt state.

lost wakeup

xv6 prevents it with sleep_prepare, which records the channel in p->chan while the caller still holds the lock that protects the condition, and with wakeup, which clears p->chan even if the process has not gone to sleep yet. sleep only sleeps if p->chan is still set, so a wakeup that lands between release and sleep() makes sleep() return at once. See sleep and wakeup and Locks and interrupt state.

memory barrier (fence)

Both the compiler and the hardware may reorder memory operations that look independent: the compiler to make code faster, a RISC-V hart because its memory model allows other harts to observe its loads and stores in a different order than the program wrote them. Within one hart this is invisible; between harts it is not.

In xv6 the barriers come from the __atomic built-ins in kernel/spinlock.c:

• acquire's __ATOMIC_ACQUIRE exchange compiles to amoswap.w.aq. The aq bit means no later load or store of this hart can be seen by others before the swap.
• release's __ATOMIC_RELEASE store compiles to fence rw,w followed by sw zero. The fence makes every earlier load and store complete before the store that frees the lock.

Both also restrict the compiler: nothing after the acquire may move above it, and nothing before the release may move below it.

memory-mapped I/O (MMIO)

noff

It lives in struct cpu (kernel/proc.h:25, offset 120), one per hart. Only the pop_off that brings it back to 0 may turn interrupts on, and only if intena says they were on before. sched insists it is exactly 1 (the process’s own p->lock) at every context switch, and panics sched locks otherwise. The deepest value measured in this tree is 3. See Locks and interrupt state.

open file (struct file)

A file descriptor points at an open file, and several descriptors can point at the same one: after dup, or in a parent and child after fork. They then share one offset. Each write to a file reads and advances that offset while holding the file’s inode lock, so a parent and child writing through the same inherited descriptor append after each other instead of overwriting each other. (A very large write is split into pieces of about 3 KB, which may interleave.) The open file’s ref field counts these pointers (reference count); fileclose really closes it only when the count drops to zero.

type says what kind of object is behind it: FD_INODE (a file or directory on disk, with an inode and an offset), FD_DEVICE (a device, with a major number that selects the driver in devsw), or FD_PIPE (one end of a pipe). See kernel/file.h and kernel/file.c.

orphaned inode

Unix lets you delete (unlink) a file that is still open. Unlinking removes the name and drops the link count (nlink) to 0, but the inode and its data must stay until the last open file descriptor or current-directory reference goes away, because a process may still read and write it. In xv6 the final iput (on close, on exit, or on chdir away) sees nlink == 0 and ref == 1, truncates the file and marks the inode free.

If the machine crashes, or QEMU is killed, before that final iput, the unlink is already safely on disk but the free never happens. The inode is then allocated but unreachable: an orphan, leaking an inode and its blocks forever. At boot, fsinit calls ireclaim, which scans every on-disk inode for type != 0 and nlink == 0 and frees each one it finds. user/forphan.c (a file) and user/dorphan.c (a directory) create orphans on purpose so that test-xv6.py can crash xv6 and check that the next boot reclaims them.

page

Because a page starts on a multiple of 4096 (2^12), the low 12 bits of an address are the offset within its page and the remaining bits name the page. RISC-V calls the page number of a physical address its PPN (physical page number): the address shifted right by 12.

PGROUNDDOWN gives the start of the page containing an address; PGROUNDUP rounds a size up to a whole number of pages. The physical pages that hold memory are handed out by the page allocator.

page allocator

page fault

In xv6, usertrap handles load and store page faults from user programs by calling vmfault, which allocates the page if it belongs to memory the process grew lazily (with sbrklazy). Any other user page fault kills the process. A page fault inside the kernel is a bug: kerneltrap panics.

page table

parse tree

For echo hi | wc > out & the shell builds:

BACK
 └─ PIPE
     ├─ EXEC  echo hi
     └─ REDIR  fd 1 → out
         └─ EXEC  wc

Each node is a small struct whose first field says what kind of node it is (EXEC, REDIR, PIPE, LIST, BACK). The tree is built by a recursive-descent parser (parseline and friends in user/sh.c) and executed by walking it recursively (runcmd).

Separating parsing from running keeps both simple: the runner never deals with characters, and the parser never deals with processes.

path name

Each piece between slashes is an element. namex resolves a path by looking up each element in turn, using skipelem to split it. Repeated and trailing slashes are ignored, and elements longer than 14 characters are cut to their first 14.

physical memory / physical address

PID (process ID)

The first process (init) gets PID 1. A PID stays attached to its process until the parent’s kwait frees the slot; freeproc then sets the slot’s pid to 0, which is why kkill refuses PID 0.

pipe

In xv6 a pipe is a 512-byte buffer inside the kernel (kernel/pipe.c). A writer that finds it full sleeps until a reader makes room; a reader that finds it empty sleeps until a writer adds data. When every write end has been closed, a reader that has drained the buffer gets end-of-file (read returns 0); when every read end has been closed, write fails.

The shell uses pipes for a | b: it creates a pipe, forks twice, and in each child moves one end onto standard output (for a) or standard input (for b) before exec, so neither program needs to know it is talking to a pipe (user/sh.c).

pipeline (a | b)

The shell creates the pipe, then forks one child per side. The left child moves the pipe’s write end onto descriptor 1, the right child moves the read end onto descriptor 0, both close the original pipe descriptors, and both exec their programs (the same trick as redirection). The shell itself closes both ends and waits for the two children.

Closing every unused end matters. The reader sees end-of-file only when every write end is closed; one forgotten copy of the write end (in the shell, or in the reading child itself) would make wc wait for more input forever.

In xv6, a | b | c is parsed as a | (b | c): the right child of the first pipe is itself a pipeline and forks two children of its own (user/sh.c).

PLIC (platform-level interrupt controller)

PMP (physical memory protection)

privilege mode

The privilege mode decides which instructions and CSRs the hart may use and, through page tables and PMP, which memory it may touch. A program in U-mode cannot, for example, turn off interrupts or change the page table; it must ask the kernel through a system call.

A hart moves to a less privileged mode with a return instruction (mret, sret) and to a more privileged one only through a trap.

process

process state

The scheduler only ever looks for RUNNABLE.

PTE (page-table entry)

Layout of an Sv39 PTE (xv6’s macros in kernel/riscv.h):

A PTE with V = 1 and R = W = X = 0 is not a mapping at all: it points to the next level of the page table. Any of R, W, X set makes it a leaf. PA2PTE and PTE2PA convert between a physical address and the PPN field; PTE_FLAGS extracts bits 9–0.

push_off / pop_off

push_off reads and clears sstatus.SIE in one csrrci, records the old value in intena if noff was 0, and increments noff. pop_off panics if interrupts are on (pop_off - interruptible) or noff is already 0 (pop_off), decrements noff, and sets SIE if it reached 0 and intena is 1. Besides the lock code, myproc and uartputc_sync call them. See interrupts and spinlocks (push_off / pop_off) and Locks and interrupt state.

race condition

The classic example is two harts incrementing a shared counter. count = count + 1 compiles to a load, an add and a store. If both harts load the old value before either stores, both store the same new value and one increment is lost. Nothing crashes; the count is quietly wrong, and only under the right timing.

The cure is to make the load–modify–store sequence a critical section that only one hart can be in at a time, usually with a spinlock.

randomized testing

A hand-written test checks the situations its author imagined. A randomized test picks, at every step, one of many operations at random and runs millions of steps, so it also reaches odd sequences such as “unlink the file another process is writing, then create a directory with the same name”. Because the generator is pseudo-random, a run is determined by its starting value (the seed): changing the seed gives a different sequence, and in principle reusing a seed repeats a run, although with several processes the interleaving of their calls still depends on timing.

user/grind.c is xv6’s randomized test: two processes each draw a number from a Park–Miller generator (do_rand) and perform one of 22 file-system, process or memory operations, forever. Randomized testing that feeds random or malformed inputs rather than random operations is usually called fuzzing.

recursive-descent parser

The xv6 shell’s grammar has four rules, each handled by one function (the exec rule gets help from parseredirs for its redirections):

line  = pipe { "&" } [ ";" line ]          parseline
pipe  = exec [ "|" pipe ]                   parsepipe
exec  = block | redirs { word redirs }      parseexec, parseredirs
block = "(" line ")" redirs                 parseblock

{ } means “zero or more times”, [ ] “optional”. Because block contains a whole line, parentheses can nest to any depth: the recursion handles it. Each function looks at the next token without consuming it (peek) to decide which way to go, and consumes it with gettoken (user/sh.c).

reference count

The pattern always has three parts: something that takes a reference and increments the count (iget, idup, filedup), something that drops one and decrements it (iput, fileclose), and a lock that makes the count’s updates atomic. Forgetting a decrement leaks the object; an extra decrement frees it while it is still in use.

regression test

A regression test usually looks odd out of context: it does something no ordinary program would do, because that is exactly what once broke the system. Its comment often names the bug, and git log -S on the test’s name usually finds the fix that came with it.

Much of usertests (user/usertests.c) is of this kind. For example, killzero calls kill(0) and then forks, because kill(0) once marked an unused process slot as killed and the next process created in that slot died at once. reparent2 forks orphans 800 times because the code that hands orphans to init once deadlocked. Running the whole suite after every change to the kernel checks that none of these bugs has returned.

regular expression

Some examples, with the meanings they have in user/grep.c:

• xv6 matches any line containing the three characters xv6.
• ^xv6 matches lines that start with xv6.
• v6.$ matches lines whose last three characters are v6 followed by any one character.
• a.*c matches lines containing an a followed, anywhere later, by a c.
• ab*c matches ac, abc, abbc, …

Full regular-expression languages (POSIX, Perl) add character classes [a-z], alternation a|b, grouping ( ), +, ? and escapes such as \.. xv6’s matcher has none of these: it cannot search for only a literal . (a . always matches any character), and a * is literal only where it has nothing to repeat, at the start of the pattern or right after another c*. Its whole implementation is three short recursive functions, from Kernighan and Pike’s The Practice of Programming.

save area

Some of them hold a value of sp (a pointer into a stack), but none of them is one. See The stacks of xv6.

scheduler

scheduler stack

Inside the loop, sp sits just below the frames of start, main and scheduler: 0x80008810 on hart 0 in this build (0x80009810 on hart 1, 0x8000a810 on hart 2). swtch saves that value in cpus[i].context.sp when the hart switches to a process, and loads it again when the process calls sched. struct cpu holds only this saved pointer, not the stack itself.

Each hart only ever switches to its own scheduler stack, so no two harts share one. An interrupt taken in the loop’s short interrupt window pushes a kernelvec frame onto it; kerneltrap never yields there, because the hart has no current process. See The stacks of xv6.

shell

A shell has no special privileges. Everything it does goes through the same system calls any program can use: fork and exec to start programs, wait to wait for them, open, close, dup and pipe to arrange their file descriptors (I/O redirection, pipeline (a | b)). That a useful shell fits in about 500 lines of C is a demonstration of how well these few Unix system calls fit together.

A few commands cannot be ordinary programs because they must change the shell’s own process state. In xv6 the only one is cd: the current directory belongs to a process, so a child that changed directory and exited would leave the shell where it was.

If the shell exits (for example when you type Ctrl-D at the prompt), /init (user/init.c) starts a new one.

sleep and wakeup

The usual pattern, with lk the lock protecting the condition:

acquire(&lk);
while (!condition) {
  sleep_prepare(chan);
  release(&lk);
  sleep();
  acquire(&lk);
}

and on the other side acquire(&lk); make condition true; wakeup(chan); release(&lk);. uartwrite uses a variant without a condition lock: it registers first and then tests the device; a wakeup arriving after the registration clears p->chan, so sleep returns at once.

The lost-wakeup problem. If a process checked the condition, released the lock and only then registered on the channel, the event could happen in between: the waker calls wakeup, finds nobody on the channel, and the process then sleeps forever.

xv6 closes the gap in two halves. sleep_prepare records the channel in p->chan while the condition lock is still held, so any wakeup that happens after the check finds the process registered. wakeup clears p->chan, even if the process has not gone to sleep yet, and sleep only sleeps if p->chan is still set. So a wakeup that arrives between release(&lk) and sleep() makes sleep() return at once instead of being lost.

A wakeup means “something changed”, not “the condition is true”: several processes may be woken and only one may get the resource, and kkill wakes sleepers too. That is why callers re-check the condition in a while loop.

This differs from the MIT xv6 book and older trees, where sleep(chan, lk) takes the condition lock as an argument. See Locks and interrupt state and lost wakeup.

sleep lock

A struct sleeplock (kernel/sleeplock.h) is a locked flag guarded by a small spinlock. A process that finds it held calls sleep and is woken by releasesleep (see sleep and wakeup).

Differences from a spinlock: a process may hold a sleep lock while it sleeps or is switched out, and holding a sleep lock does not by itself turn interrupts off. In exchange, only a process can use one: an interrupt handler cannot sleep, so it can never take a sleep lock.

Ownership is by process: holdingsleep compares the holder’s PID, because a holder can sleep and resume on another hart. See Locks and interrupt state.

spinlock

The lock is one word, locked: 0 means free, 1 means held. acquire uses an atomic swap (amoswap) to write 1 and get the old value back in one indivisible step; if the old value was 0, this CPU now holds the lock, otherwise it tries again. release stores 0. Both include a memory barrier (fence) so that the protected data is never read or written outside the lock.

Spinning wastes the CPU, so spinlocks suit short critical sections. A process must not sleep or give up the CPU while holding one (only the process’s own p->lock, which sched requires, is allowed). For long waits, such as disk I/O, xv6 uses a sleep lock. See also interrupts and spinlocks (push_off / pop_off), deadlock and Locks and interrupt state.

Sstc extension

stack

xv6 has three kinds. Apart from a few instructions at power-on and two short stretches in the trampoline (The stacks of xv6), each hart is on exactly one of them, whichever memory its sp points into:

• a user stack per process, for the program’s own code;
• a kernel stack per process slot, for kernel code running on a process’s behalf;
• a boot stack (stack0) per hart, a slice of stack0, which becomes the hart’s scheduler stack once boot is over.

Only four instructions ever move sp from one stack to another (stack pointer and the active stack). The trapframe and the context structures that save registers are not stacks (save area). See The stacks of xv6.

stack pointer and the active stack

Each hart has its own sp. Apart from a few instructions at power-on and two short stretches in the trampoline (The stacks of xv6), each hart is on exactly one stack, and with three harts up to three stacks are in use at once. The four instructions that move sp to another stack are:

Traps, sret and mret never change sp. Neither does kernelvec, which pushes its frame onto the stack that is already active. See The stacks of xv6.

standard input, output and error

The program does not open them; it inherits them. In xv6, init opens the console as descriptor 0 and duplicates it into 1 and 2 (user/init.c), and every later process inherits these through fork and exec. The shell can replace any of them before running a program: cat < f makes descriptor 0 the file f, ls > out makes descriptor 1 the file out, and ls | wc connects descriptor 1 of ls to descriptor 0 of wc through a pipe.

Keeping errors on a separate descriptor matters when output is redirected: cat a b > out should put the contents in out but still show “cannot open b” on the screen. That only works if the message goes to descriptor 2 (fprintf(2, ...)), not to descriptor 1 (printf(...)). Some xv6 utilities get this wrong.

A program that reads its input from descriptor 0 when given no file names, and writes its results to descriptor 1, works as a filter: it can sit anywhere in a pipeline. cat, grep and wc are filters in this sense.

stress test

Most kernel bugs that survive careful reading are timing bugs: a race condition that needs two CPUs to be in exactly the wrong place, or a leak that matters only after thousands of operations. A stress test makes such events likely by running many operations concurrently and for a long time.

Its success criterion is usually weak: the kernel did not panic, did not hang, and a few simple invariants still hold (a newly created file can be written and has size 1, wait returns the right number of children). xv6’s stress tests are user/grind.c (random system calls, forever), user/forktest.c (fill the process table), user/stressfs.c and user/logstress.c (concurrent file writers), and many tests in user/usertests.c.

superblock

Written once by mkfs/mkfs.c when fs.img is built, read once at boot by readsb into the global sb, and never changed. See disk layout (xv6 file system) for the values on the default disk.

Sv39

A virtual address is split into five fields:

 63      39 38    30 29    21 20    12 11         0
+----------+--------+--------+--------+------------+
|  unused  | L2 idx | L1 idx | L0 idx |   offset   |
+----------+--------+--------+--------+------------+
   25 bits   9 bits   9 bits   9 bits    12 bits

Bits 63–39 must be copies of bit 38; xv6 keeps bit 38 at 0 (MAXVA), so they are 0. To translate, the hardware:

1. takes the root page-table page from satp and reads entry L2 idx;
2. if that PTE is valid and not a leaf, reads entry L1 idx of the page it points to;
3. does the same with L0 idx at the last level, which yields a leaf PTE;
4. checks the leaf’s permission bits against the access, and forms the physical address as the leaf’s PPN × 4096 + offset.

An invalid PTE at any level, or a permission mismatch, raises a page fault. Each index is 9 bits because 2^9 = 512 eight-byte PTEs fill exactly one page. Sv39 also allows leaves at the upper levels (2 MiB and 1 GiB “superpages”); xv6 never creates them. The translated results are cached in the TLB (translation lookaside buffer). xv6’s walk performs the same steps in software.

Svadu extension (A and D bits)

system call

system call arguments

A user program calls a system call stub like an ordinary C function, so the calling convention has already put the arguments in a0, a1, … The stub executes ecall without touching them; uservec saves them into the trapframe.

Everything that arrives this way is untrusted. Integers can be anything, and pointers may point at memory the process does not own, at kernel memory, or nowhere. The kernel therefore never dereferences a user pointer directly: it copies data in and out with copyin, copyinstr and copyout, which translate the address through the process’s own page table and fail if the address is not valid user memory.

system call number

The numbers are defined once, in kernel/syscall.h, and that header is included by both sides: by kernel/syscall.c to build the dispatch table, and by the generated user stubs in user/usys.S (user/usys.pl), each of which is three instructions:

li a7, SYS_fork
ecall
ret

Because the number is the only thing that connects the two sides, user programs and the kernel must be built from the same syscall.h.

system call stub

C cannot express “trap into the kernel”, so the boundary between a user program and the kernel is crossed in assembly. xv6 generates all its stubs with the Perl script user/usys.pl; the output is user/usys.S, for example:

write:
 li a7, SYS_write   # 16, from kernel/syscall.h
 ecall              # trap into the kernel
 ret                # back to the C caller; a0 holds the result

The stub does not touch the arguments. The C calling convention has already put them in a0, a1, … before the call, and that is exactly where the kernel looks for them (system call arguments). On the kernel side, syscall reads a7 from the trapframe, calls the matching sys_ function, and stores its return value in the saved a0, which the stub’s ret hands back to the caller.

Real C libraries work the same way, though their stubs usually also convert the kernel’s error return into the errno variable. xv6 has no errno: a failing call returns -1 and the program learns nothing more.

test harness

A harness separates what is tested (the individual test functions) from how tests are run. That lets the same tests be run all at once, one at a time by name, or over and over, without changing the tests themselves.

usertests’s harness runs every test in a child process created with fork, so a test that crashes, is killed by the kernel, or deliberately ruins its own memory cannot take the harness down with it. The child’s exit status is the verdict: 0 means the test passed, anything else (1 from the test itself, or -1 when the kernel killed it) means it failed. Before and after the whole run, the harness also counts free memory pages (countfree), so a kernel that leaks memory fails even if every individual test passed.

One level up, test-xv6.py is a harness for the harness: it boots xv6 in QEMU, types usertests at the shell and waits for the line ALL TESTS PASSED. The project’s continuous integration (CI) job runs it on every change.

timer interrupt

TLB (translation lookaside buffer)

trampoline page

RISC-V’s trap hardware does not change satp: a trap from user mode lands in the kernel with the user page table still installed. The handler’s first instructions must therefore be mapped in the user page table, and after the instruction that switches to the kernel page table, the next instruction must be found at the same address in the kernel page table. Mapping one physical page at the same virtual address in both solves this.

The page is mapped without PTE_U, so user code cannot read or run it; supervisor mode can. It sits at the very top of the usable virtual address range, TRAMPOLINE = MAXVA - PGSIZE = 0x3ffffff000, so it never collides with user memory that grows up from address 0. The kernel maps it in kvmmake (kernel/vm.c:47); each process’s page table gets it in proc_pagetable (kernel/proc.c:189).

transaction

trap

On a trap the hart saves where it was (in mepc or sepc) and why (in mcause or scause), switches to the handler’s privilege mode (the same or a higher one, never lower), and jumps to the handler address held in mtvec or stvec. Which of the two sets is used is decided by trap delegation.

trap cause (scause values)

The values xv6 tests for:

Other exception codes include 2 (illegal instruction), 5 (load access fault), 7 (store/AMO access fault) and 12 (instruction page fault). xv6 handles none of them: from user mode the process is killed, and in the kernel kerneltrap panics.

trap delegation

By default (on QEMU, where the delegation registers start at 0) every trap is handled in machine mode. xv6’s kernel runs in supervisor mode and wants to handle traps itself, so start delegates all of them. Delegation only applies to traps that happen while the hart is in S or U mode; a trap in M mode always stays in M mode.

trapframe

Each process has one, allocated by allocproc and pointed to by p->trapframe. The same physical page is visible at two addresses:

• at TRAPFRAME (just below the trampoline page page) in the process’s own page table, which is where uservec and userret use it, because they run while the user page table is still (or already) installed;
• at its ordinary direct-mapped physical address in the kernel, which is how C code reaches it through p->trapframe.

Its layout is struct trapframe: four kernel fields (kernel_satp, kernel_sp, kernel_trap, kernel_hartid) plus epc, the saved user PC, followed by 31 user registers. The assembly in kernel/trampoline.S uses the byte offsets written in the comments there, so the struct and the assembly must be changed together.

The kernel also uses the trapframe to talk to the user program: system call arguments are read from its a0–a5 slots, the call number from a7, and the return value is written into its a0 slot (syscall).

UART

user memory layout

MAXVA       0x4000000000  +---------------------------+
TRAMPOLINE  0x3ffffff000  | trampoline code    R X    |  (not user-accessible)
TRAPFRAME   0x3fffffe000  | trapframe          R W    |  (not user-accessible)
                          +---------------------------+
                          |        unmapped           |
            p->sz  ---->  +---------------------------+
                          | heap (sbrk)        R W U  |
                          +---------------------------+
                          | stack (USERSTACK)  R W U  |
                          | guard page         R W    |  (U cleared)
                          +---------------------------+
                          | data, bss          R W U  |
                          | text, rodata       R X U  |
            0             +---------------------------+

p->sz is the size of everything from 0 up to the top of the heap. kexec builds the lower part; proc_pagetable maps the top two pages. See kernel/memlayout.h.

user stack

kexec creates it, copies the program’s argument strings and argc and argv (program arguments) array to its top, and sets the saved sp to point at argv. The stack does not grow: a program whose stack needs more than the page runs into the guard page and is killed. (The guard is only one page: a single stack frame larger than 4 KiB can jump over it and land in the program’s data.) It is separate from the kernel stack the kernel uses while handling the process’s system calls and traps. See user memory layout.

The stack is mapped only in the process’s own page table. A single instruction moves sp onto it, userret's ld sp, 48(a0) (kernel/trampoline.S:118), but the hart can use it only from the sret at kernel/trampoline.S:153, when the mode becomes user (supervisor code cannot use user pages). It stops being usable at the next trap, which returns to supervisor mode, and uservec then saves the user’s sp in the trapframe and loads the kernel stack’s address (kernel/trampoline.S:76). kfork copies it along with the rest of user memory (uvmcopy); it is freed by freeproc when the parent’s kwait collects the process. See The stacks of xv6.

virtio

virtqueue

All three parts live in ordinary RAM that the driver allocates; the driver tells the device their physical addresses once, at initialization. After that, submitting a request is a matter of writing memory plus one write to a notify register, and completion is signalled by the device writing the used ring and raising an interrupt. This is the “split virtqueue” layout of the virtio 1.x specification. See kernel/virtio.h and kernel/virtio_disk.c.

virtual memory

write-ahead log

After a crash, the recovery code looks at the log. If the “complete” record (xv6’s log header with a non-zero count) is there, it copies the logged blocks to their places again, finishing the job; if not, it ignores the log, and none of the changes happened. Either way the disk ends up with all of a transaction's changes or none of them. xv6’s log is a redo log of whole blocks: it records new block contents, never old ones, and replaying it twice gives the same result as replaying it once.

zombie

kexit cannot mark its own slot UNUSED: another CPU could then reuse the slot, kernel stack included, while it is still running on it. It also must keep its exit status somewhere until the parent asks. So it stores the status in p->xstate, sets p->state = ZOMBIE and switches away for good. The parent’s kwait later copies out the status and calls freeproc. If the parent exits first, the zombie is handed to init (reparent), whose endless wait loop (user/init.c) collects it.

-T / -Ttext / -N / -e / -z max-page-size

. (location counter)

ALIGN

ASSERT

ENTRY

OUTPUT_ARCH

PROVIDE

SECTIONS

$(shell ...)

$(wildcard ...)

-include

.PHONY

.PRECIOUS

CURDIR

ifndef / ifneq / endif

make automatic variables ($@ $< $^ $*)

QEMU options

mcounteren

medeleg / mideleg

menvcfg

mepc

mhartid

mie

mstatus

pmpaddr0 / pmpcfg0

Entry 0’s settings are the low byte of pmpcfg0:

With A = 1 (TOR, “top of range”), entry 0 covers addresses from 0 up to (not including) pmpaddr0 × 4.

satp

xv6 builds this value with MAKE_SATP.

sepc / scause / stval / sip / sscratch

sie

SIE (sstatus bit 1)

A trap clears it (saving the old value in SPIE) and sret restores it. In xv6 it is cleared by push_off's csrrci and by intr_off, and set by pop_off (only at noff 0), usertrap's intr_on for a system call, and the scheduler's one-instruction window. Whenever noff is above 0, SIE is 0. In user mode, supervisor interrupts are taken whatever SIE says, and wfi wakes on a pending interrupt even with SIE 0. See Locks and interrupt state and Locks and interrupt state.

sstatus

stimecmp

stvec

time

add

addi (add immediate)

amoswap.w (atomic swap)

It belongs to the “A” (atomic) extension, included in rv64gc. xv6’s acquire is the only place in the kernel that uses it (amoswap.w.aq a5,a5,(s1) in kernel/kernel.asm). With the aq bit set, no later memory operation of the same hart can be observed by other harts before the swap; see memory barrier (fence).

call

csrr (read CSR)

csrrc (read and clear CSR bits)

csrs / csrc (set / clear CSR bits)

csrw (write CSR)

ecall

fence

fence.i

j (jump)

jalr (jump and link register)

la (load address)

li (load immediate)

mret (return from machine mode)

In detail, mret:

1. sets the privilege mode to mstatus.MPP, then sets MPP to U (the lowest mode);
2. copies mstatus.MPIE into mstatus.MIE (restoring the machine interrupt enable) and sets MPIE to 1;
3. sets the program counter to mepc.

mul (multiply)

mv (move)

ret

sd / ld (store / load doubleword)

sfence.vma

sret (return from supervisor mode)

In detail, sret:

1. sets the privilege mode to sstatus.SPP (0 = user, 1 = supervisor), then sets SPP to 0 (user);
2. copies sstatus.SPIE into sstatus.SIE (restoring the interrupt enable that was in force before the trap) and sets SPIE to 1;
3. sets the program counter to sepc.

It is the mirror image of what the hardware does on trap entry (save the mode in SPP, save SIE in SPIE, clear SIE, save the PC in sepc). xv6 also uses it to enter user mode for the first time, by filling SPP, SPIE and sepc itself (prepare_return).

wfi (wait for interrupt)

a0–a7 (argument registers, x10–x17)

gp (global pointer, x3)

ra (return address, x1)

s0–s11 (saved registers)

sp (stack pointer, x2)

t0–t6 (temporary registers)

tp (thread pointer, x4)

zero (x0)

.bss section

.data section

.rodata section

.text section

C preprocessor

C runtime start-up code

A C program’s life does not begin in main. The operating system starts a program at its entry point, an address recorded in the ELF header, and something there has to turn the raw starting state (registers, a stack) into an ordinary call to main, and has to deal with main returning, which the kernel knows nothing about.

On Linux this is the file crt0.o or crt1.o (“C runtime”), whose entry symbol is _start, and it does much more: it sets up the C library, the environment variables and atexit handlers. xv6 needs only the essentials, written in C:

void start(int argc, char **argv) { exit(main(argc, argv)); }

kexec puts argc in a0 and argv in a1, so by the calling convention they arrive as start’s two parameters. user/user.ld names no entry symbol, and GNU ld then picks the symbol called start.

continuous integration (CI)

A CI configuration lists jobs; each job names a kind of machine to run on and a sequence of steps (shell commands). If any command exits with a non-zero status the job fails, and GitHub marks the commit or pull request with a red cross. xv6’s jobs build the kernel and fs.img on Linux and macOS, check the formatting, and on Linux run test-xv6.py, which boots xv6 in QEMU and runs usertests and the crash tests.

cross-compiler / toolchain

disk image (fs.img)

ELF

entry point

freestanding (vs. hosted) C

gdb (the GNU debugger)

QEMU contains a small gdb stub: with the -gdb tcp::PORT option it listens on a TCP port and lets gdb control the emulated machine through gdb’s remote protocol. gdb then sees the emulated harts as threads, can stop them anywhere, even in the kernel’s first instruction, and uses the symbols and line numbers in kernel/kernel (compiled with -ggdb) to show you C source. The commands gdb runs at start-up come from .gdbinit, generated from .gdbinit.tmpl-riscv by the Makefile (Makefile:185).

A few commands to start with: b kvminithart (breakpoint on a function), c (continue), si (step one instruction), n (next C line), info registers, x/4x ADDR (show memory), bt (stack backtrace).

linker (ld)

linker script

make / Makefile

A rule looks like this (the recipe line must start with a tab):

target: prerequisite1 prerequisite2
	command that builds target

Variables are set with = (expanded every time they are used), := (expanded once, now), += (append) or ?= (set only if not set yet), and used as $(NAME), or $X for a one-letter name. A pattern rule such as %.o: %.S is a template for many targets; % matches any stem. If no rule in the Makefile matches, make falls back to its built-in implicit rules, such as compiling x.c into x.o with $(CC) $(CFLAGS) -c.

object file (.o)

program header (segment)

The loader (kexec in xv6) only needs the program headers, not the finer-grained section headers that linkers and debuggers use. An xv6 user program has two loadable segments: code plus read-only data (readable and executable) at address 0, and data plus bss (readable and writable) at the next page boundary (all except _forktest, which is linked without user.ld and has a single read-write-execute segment). You can list them with ${TOOLPREFIX}readelf -l user/_cat (TOOLPREFIX is your RISC-V toolchain’s prefix; see Tour 1: From make qemu to a disk image and a kernel).

pseudo-instruction

QEMU

section

small data sections (.sdata, .sbss, .srodata)

symbol