user/usertests.c
About this file
usertests is xv6’s test suite: one user program, about seventy small tests, each a C
function that pokes at the kernel through system calls and checks the
answers. Many are regression tests for bugs that were once real.
Tests come in two tables. quicktests holds most of them; slowtests holds a few
that fill the disk or make huge directories. drivetests runs the tables in order, and
run runs each test in its own forked child: the test fails if that
child exits with a non-zero status. Each test gets its own name as s, and most use it
as the prefix of their error messages. Before and after a run, countfree counts free memory
pages, so a kernel that leaks pages fails even when every test passed.
At the xv6 shell prompt you type usertests (all tests), usertests -q (quick tests
only), or usertests copyin (one test by name). -c repeats until something fails;
-C repeats forever and ignores failures. Only one argument is accepted, so options
cannot be combined. A run prints
usertests starting
test copyin: OK
test copyout: OK
...
ALL TESTS PASSED
A failing test prints FAILED and the run stops with SOME TESTS FAILED (with -C it
carries on). Leaked pages print FAILED -- lost some free pages. Kernel
usertrap(): unexpected scause lines between tests are expected when the test still
says OK. From the host, ./test-xv6.py usertests runs it under QEMU.
Headers, including kernel headers
A user program normally needs only user/user.h (the system-call and library
declarations) plus the types and stat structure. usertests also includes kernel
headers to test against the kernel’s own limits: kernel/param.h gives
MAXOPBLOCKS and MAXPATH, kernel/fs.h gives
BSIZE, MAXFILE and DIRSIZ,
kernel/fcntl.h the O_ flags for open, and kernel/memlayout.h and
kernel/riscv.h the addresses and page size (KERNBASE,
MAXVA, PGSIZE) that the memory tests aim at.
kernel/syscall.h is included but no SYS_ number is used anywhere in this file
at this commit.
What the file says about itself
The opening comment is accurate but incomplete. Besides “no arguments” and a test
name, main also accepts -q, -c and -C (see the file
summary). “Based on the exit status” is the key rule for anyone writing a test: a
test signals failure by calling exit with a non-zero value. A test that detects a
problem and only returns is reported as OK, because
run calls exit(0) after the test function returns. Two tests
below fall into that trap (line 777 and line 897).
The usertrap messages come from usertrap (kernel/trap.c:76),
which prints them when a process causes an exception the kernel cannot handle, and
then kills that process. Several later tests do that on purpose.
A shared buffer bigger than one transaction
buf is a global scratch buffer used by many tests. Its size,
(MAXOPBLOCKS + 2) * BSIZE = (10 + 2) * 1024 = 12288 bytes, is deliberately larger
than the 10 blocks one file-system transaction may write. (The kernel already
splits any write larger than 3072 bytes into several transactions,
kernel/file.c:153; the size here simply guarantees that a full-buffer write is
more than one transaction could ever hold.)
The tests do not interfere through this global: each one runs in its own forked
process, and fork gives the child a private copy of all memory.
The quick tests start here
Almost every test from here to quicktests is in the quick table, the tests -q
runs (the exception is fsfull, which nothing calls). The slow ones follow that
table.
copyin: refuse to read memory the process does not own
write makes the kernel read from user memory: it copies the bytes at the user’s
pointer with copyin (through either_copyin). This test hands
write five pointers that a correct kernel must refuse:
0x80000000(KERNBASE, 2 GiB): where RAM starts. The kernel maps it in its own page table, but a user page table does not.0x3fffffe000and0x3ffffff000: the trapframe and trampoline page pages (kernel/memlayout.h:63,kernel/memlayout.h:48). They are mapped in every user page table, but without thePTE_Ubit, sowalkaddrrefuses them (kernel/vm.c:135).0x4000000000:MAXVAitself, the first address past the user range.walkpanics on such an address (kernel/vm.c:101), so the copy code must reject it first (kernel/vm.c:127).0xffffffffffffffff: all ones, where address arithmetic overflows.
Each address is tried on three kinds of open file (struct file) (an inode file, the console and a pipe), because each has its own copy loop and each must handle the failure. A broken kernel either panics or returns a positive count.
The five addresses to try: the start of RAM (2 GiB), the trapframe page, the trampoline
page, the first address past MAXVA, and the largest 64-bit value.
Create the file fresh each round; it is unlinked again on line 52.
Ask the kernel to copy 8192 bytes from the bad address into a file. The first call to
copyin fails, so writei writes nothing and filewrite
returns -1 (kernel/file.c:173). Anything >= 0 is a failure.
The same from the console (descriptor 1). consolewrite returns how many
bytes it copied before the error (kernel/console.c:72), here 0, so 0 is accepted
as well as -1.
The same into a pipe. pipewrite copies one byte at a time and returns -1
if the very first byte fails (kernel/pipe.c:96–99).
copyout: refuse to write into memory the process may not write
The mirror image of copyin: read makes the kernel write into
user memory with copyout. The addresses are the same, plus 0.
Address 0 is mapped: it is the start of the program’s code. But the ELF file
marks the code segment read and execute only, so kexec maps it without
PTE_W (kernel/exec.c:19), and copyout refuses pages without PTE_W
(kernel/vm.c:364). Without that check, read could overwrite the program’s own
code even though the hardware forbids the program to store there. That is also why
copyin leaves 0 out: reading code is allowed.
The data source is the README file, which make copies into fs.img, and a
pipe. readi returns -1 when the copy fails (kernel/fs.c:526);
piperead returns -1 if the very first byte fails (kernel/pipe.c:133).
The same addresses as copyin plus 0, the start of the program’s
read-only code.
Read up to 8192 bytes of README into the bad address. readi returns -1 at
the first failed copyout.
Put one byte into the pipe first, so the read below has data and does not sleep
waiting for a writer.
piperead takes the byte out of the pipe and tries to store it at addr.
copyinstr1: bad pointers as path names
Path names reach the kernel by a different route from write data: argstr
calls fetchstr, which calls copyinstr (kernel/syscall.c:29),
a loop that copies one byte at a time until it sees the terminating zero. The test
passes the same bad addresses as copyin as the path for
open(..., O_CREATE | O_WRONLY) and expects -1 each time. O_CREATE matters: if the
kernel misread the name, it would create a file with a garbage name instead of
failing quietly.
The bad address is the path argument. sys_open copies it with
argstr (kernel/sysfile.c:338), which must fail.
copyinstr2: a string exactly one byte too long
A boundary test. System calls that take a path copy it into a kernel array of
MAXPATH (128) bytes, such as path in sys_open. Here the user
string has 128 xs and its zero in byte 129. A correct copyinstr copies
at most 128 bytes, never sees the zero, and returns -1. An off-by-one version would
store the zero one byte past the end of the kernel array, on the
kernel stack, overwriting whatever lies there.
The test tries four path-taking calls (unlink, open, link, exec),
because each one calls argstr itself. Then it checks the same limit for exec’s
arguments, which sys_exec copies into one-page kernel buffers
(kernel/sysfile.c:484).
Two printfs (lines 171 and 188) print fd where they mean ret; only the
error message is affected.
Build a string of exactly MAXPATH (128) xs; its terminating zero is the
129th byte. b has room for it in user space, but the kernel’s path array does not.
unlink copies the path with argstr into a 128-byte array; the copy must
fail because no zero appears within 128 bytes.
sys_link copies both names into MAXPATH arrays; the first copy already fails.
sys_exec also copies its path with argstr (kernel/sysfile.c:466).
A 4097-byte array: 4096 xs and a zero. static puts it in the program’s .bss section
instead of on the stack, which is only one page and too small to hold it.
Pass three such strings as arguments to echo. sys_exec copies each into
a one-page (4096-byte) kernel buffer with fetchstr(uarg, argv[i], PGSIZE)
(kernel/sysfile.c:484); 4096 characters plus the zero do not fit, so exec must
fail. Had it succeeded, echo would run and exit with 0.
A status no other path produces, so the parent can tell “exec failed as it should” (747) from “exec succeeded and echo exited 0”.
The status from wait is what the child passed to exit; anything but 747 means
exec did not fail.
copyinstr3: a string that runs off the end of memory
This time the string is short but has no terminating zero inside the process’s
memory at all: its one x is the very last byte the process owns. copyinstr
copies the x, moves to the next page, finds it unmapped and beyond p->sz, and
must return -1 (kernel/vm.c:463). A kernel that read past the last page, or
treated “ran out of memory” as “end of string”, would accept the one-letter name x.
The setup makes sure the top of memory is page aligned, so the byte after the x is
in a page that is not mapped at all.
As in copyinstr2, the printf on line 241 prints fd where it means ret.
Grow memory by two pages, then grow again if needed until sbrk(0), the current end
of memory, is a multiple of the page size. If it still is not, the test cannot set up
its trap and gives up.
Put an x in the last byte the process owns. Writing it also proves the page is
really there. b points to a “string” that has no terminating zero before the end of
memory.
copyinstr copies the x, crosses into the next page, and must fail there
instead of reading beyond the end of the process.
rwsbrk: memory given back must stay given back
The process grows its memory by two pages with sbrk and immediately shrinks it
again. growproc and uvmdealloc free those pages and remove
their PTEs. The test then asks write to read from, and read to write
into, the second of those pages.
This matters more in this xv6 than in older ones, because the kernel’s copy routines
now create missing pages: if walkaddr finds no mapping, they call
vmfault to support lazy sbrk. The only thing stopping vmfault from
giving the process back the page it just returned is the check va >= psz
(kernel/vm.c:463), with psz the process size p->sz. Both calls must return -1.
The test dates from the change that made read and write return an error when the
copy fails (git log commit 6750608, which changed readi and
writei); before it, read and write on a file returned the count of
bytes copied so far.
Grow by two pages; a is the old end of memory, the start of the new region. This is
the eager sbrk (sbrk passes SBRK_EAGER), so the pages are really
allocated and mapped.
Shrink by the same amount. growproc calls uvmdealloc, which
unmaps the pages and frees them.
Ask write to read 1024 bytes from the freed region. The test uses a + PGSIZE
rather than a because, if a was not page aligned, the page containing a is still
partly the process’s and still mapped; a + PGSIZE is surely in a freed page.
Ask read to store into the freed region. copyout finds no mapping, and
vmfault must refuse to create one because the address is at or above
p->sz.
Explicit success. Returning would have the same effect, since
run calls exit(0) after the test.
truncate1: O_TRUNC and other descriptors on the same file
open with O_TRUNC empties an existing file: sys_open calls
itrunc (kernel/sysfile.c:387), which frees the file’s blocks and sets
its size to 0. The interesting question is what happens to other descriptors
already open on that file. Each struct file has its own offset, which truncation
does not touch.
So fd2, which had read 4 bytes, still has offset 4 after the truncation. Reading at
an offset past the end returns 0 (kernel/fs.c:515). After 6 new bytes are
written, fd3 (offset 0) sees all 6, and fd2 (offset 4) sees the last 2. A
kernel that cached the size per descriptor, or failed to free and reuse blocks
correctly, would report other counts.
The aaa and bbb lines are leftover debugging output.
Create the file (or empty it, if it exists) and write 4 bytes.
Truncate the file again while fd2 is open with offset 4. The size becomes 0.
A new descriptor starts at offset 0 and must see an empty file.
fd2’s offset (4) is now past the end of the file; readi returns 0 for
that (kernel/fs.c:515).
fd1 is at offset 0, so this write is allowed and makes the file 6 bytes long.
fd2, still at offset 4, now gets the last 2 of the 6 bytes.
truncate2: writing past the end after a truncate
fd1 has written 4 bytes, so its offset is 4. Opening the file again with O_TRUNC
makes the size 0 under fd1’s feet. The next write through fd1 would start at
offset 4, beyond the end of the file.
POSIX systems allow this and fill the gap with zeros. xv6 does not:
writei returns -1 for any write that starts beyond the current size
(kernel/fs.c:549–550), and filewrite passes that -1 on. The
comment above the test says it plainly: the test checks that this case is refused
cleanly rather than crashing the kernel.
Create the file and leave fd1 at offset 4 after writing.
A second open with O_TRUNC sets the size to 0 while fd1 is still open.
This write would start at offset 4 in a 0-byte file. writei returns -1
(kernel/fs.c:549), and the system call must report -1, not crash.
truncate3: truncating while another process writes
Two processes race on one file. The child, 100 times, opens it, writes 10 bytes at
offset 0, closes it, and reads it back. The parent, 150 times, opens it with
O_TRUNC (freeing all its blocks) and writes 3 bytes.
Every write and truncate takes the inode’s sleep lock (ilock) inside
a transaction (reads take the sleeplock without one), so they should happen
one at a time: a truncate never runs in the
middle of a write. If that locking were wrong, a write could put data into a block
that a concurrent truncate had just freed, and the kernel would panic or a write
would come back short. Because the child always writes at offset 0, its writes
should succeed no matter how the two interleave.
The parent ends with exit(xstatus) so that a failure in the child also fails the
test.
Create an empty file and close it straight away, so both processes can open it by name.
The child: open, write 10 bytes at offset 0, close, then reopen and read. Each open gets a new descriptor at offset 0, so its write is always legal.
The parent: truncate and write 3 bytes, 150 times, racing the child.
iputtest: chdir must drop the old directory inside a transaction
The test makes a directory, moves into it, and deletes it while it is still the
current directory. This is legal: sys_unlink only checks that the
directory is empty. The directory’s link count (nlink) drops to 0, but its
inode stays in memory because p->cwd still holds a
reference.
chdir("/") then drops that last reference with iput. Because nothing
links to the inode any more, iput frees it on disk, and that writes blocks.
Every disk write must be part of a transaction; log_write panics
with log_write outside of trans otherwise (kernel/log.c:231). So the test
checks that sys_chdir calls iput(p->cwd) between begin_op and
end_op (kernel/sysfile.c:452). If it did not, the kernel would panic.
Remove the directory from inside it. ../iputdir names this very directory through
its parent.
Leaving drops the last reference to the unlinked directory; this is the iput that
must be inside a transaction.
exitiputtest: exit must drop the cwd inside a transaction
The same trap as iputtest, sprung by a different call. The child leaves an
unlinked directory as its current directory and exits. kexit must drop
p->cwd with iput inside begin_op/end_op (kernel/proc.c:342–344), or the
freeing of the directory would hit the “outside of transaction” panic.
The child does the work so that the parent’s own current directory stays /; the
parent passes on the child’s status with exit(xstatus).
The child exits with an unlinked directory as its current directory; kexit
does the final iput.
openiputtest: an error path in open that frees an inode
The child tries to open a directory for writing, which sys_open refuses
(kernel/sysfile.c:355). On that error path it calls iunlockput on the inode it
looked up. Meanwhile the parent unlinks the directory. The child holds the inode’s
lock from its ilock (kernel/sysfile.c:354) until that iunlockput, and
unlink needs the same lock (kernel/sysfile.c:226), so the dangerous order is
narrower: if the whole unlink completes between the child’s namei and its ilock,
the child holds the last reference, so its iput frees the inode, which writes to disk and must be inside the transaction.
sys_open does have one (kernel/sysfile.c:341).
As the comment says, the window is so small that the test only proves anything
with a kernel modified to pause right after namei. With the normal kernel it
passes either way: if the parent wins the race, the child’s lookup fails and
open returns -1 as well. pause(1) waits one clock tick (about 0.1 s) to give
the child time to reach the lookup.
Opening a directory with O_RDWR must fail (kernel/sysfile.c:355). The error path
is the iunlockput under test.
Wait one tick, then unlink the directory, hoping to complete the unlink between the
child’s namei and its ilock.
opentest: open an existing file and a missing one
The simplest file-system test. echo exists in the root directory (every user
program is copied into fs.img by make), so opening it read-only must succeed;
doesnotexist does not, so opening it without O_CREATE must fail. The path goes
through sys_open and namei. usertests never changes
directory itself; it inherits / from the shell (and init), which is why the
relative name echo works.
writetest: write a small file and read it back
Creates small, writes 100 pairs of 10-byte strings (2000 bytes, two blocks),
reopens it, reads all 2000 bytes back in one call, and unlinks it. This covers the
ordinary path: create, filewrite and writei
allocating blocks with bmap, readi across a block boundary,
and sys_unlink freeing the file when its last descriptor is gone. Any
short count fails the test. The contents are not checked, only the lengths.
writebig: the largest file xv6 allows
Writes MAXFILE blocks: 12 direct blocks plus 256 reached through the
indirect block, 268 blocks or 274,432 bytes. That is the largest file xv6’s
inode can describe. Each block starts with its own number, written as an int
in the first 4 bytes, so the read-back checks both the count and the order.
What this catches: a mistake in bmap's indirect-block path (data landing
in the wrong block, or two file blocks sharing one disk block), a wrong limit in
writei (kernel/fs.c:551), or balloc running out of
blocks. Each write of one block is its own small transaction.
MAXFILE (268) iterations, one block each.
Stamp the block with its index in the first 4 bytes of buf.
Every block must carry its own index: this catches blocks written to the wrong place.
createtest: many files in one directory
Creates 52 empty files named a plus one more character, then unlinks them all.
The second characters are '0' + i, so they run from 0 through 9 and on through
punctuation and letters up to c; the names only need to be distinct.
The 52 names take 52 × 16 = 832 bytes of entries. On a fresh file system most of
them fill empty slots left in the root directory’s first block (mkfs rounds its
size up to a full block), and the rest spill into a newly allocated second block.
The unlinks leave empty slots that later calls to dirlink reuse, so on a
second run the directory does not grow. Return values are not checked, so this test
only fails if the kernel panics.
dirtest: mkdir, chdir and remove a directory
Makes dir0, enters it, leaves it with .., and removes it. It exercises
sys_mkdir (which writes the . and .. entries in create),
sys_chdir, .. lookup in namex, and removal of an empty
directory by sys_unlink, which also lowers the parent’s
link count (nlink) for the vanished ...
exectest: redirect output, then exec
This is how a shell runs echo OK > echo-ok. The child closes its standard
output, opens a file, which gets descriptor 1 because the kernel always hands out
the lowest free number (fdalloc), and then calls exec. The new program
keeps the process’s open files, so echo writes OK into the file without knowing
it was redirected.
The parent checks that the child exited with status 0 (from echo’s exit(0))
and that the file starts with OK. This exercises kexec loading a
program from disk and the rule that exec replaces memory but keeps the
file descriptors.
If exec succeeds, the code after it never runs, as the comment on line 715 says.
Keep a copy of standard output in errfd, so the child can still report errors after
descriptor 1 is redirected.
Close descriptor 1, then open the file. fdalloc returns the lowest free
descriptor, which is now 1, so the file becomes standard output. This is how
I/O redirection works in the shell.
Check that assumption; if the file got another number, echo’s output would go to
the console.
Replace the child with echo OK. On success this never returns; echo writes OK\n
to descriptor 1, the file, and exits with 0.
Wait for the child. A mismatched pid only prints a message, but a wrong status fails the test below.
The file must start with OK, proving that echo ran and wrote to the redirected
descriptor.
pipe1: data through a pipe arrives complete and in order
The child writes 5 chunks of 1033 bytes into a pipe, each byte the low 8 bits of a running counter. The parent reads with request sizes 1, 2, 4, 8, … (capped at the buffer size) and checks every byte against its own counter.
The sizes are chosen to stress pipewrite and piperead. The
kernel’s pipe buffer holds 512 bytes (kernel/pipe.c:11), so each 1033-byte write
must fill the buffer, sleep until the reader drains it, and continue; the data wraps
around the circular buffer at changing positions; and reads ask for less and more
than is available. Lost, duplicated or reordered bytes show up as a mismatch.
At the end, read must return 0 once the child has exited and the last write end
is closed. If the parent had not closed its own write end (line 770), it would
wait forever.
Fill the buffer with consecutive numbers. buf is char, so each byte keeps only the
low 8 bits of seq.
Write 1033 bytes, more than the 512-byte pipe buffer holds, so this call must block partway and resume after the parent reads.
Keep reading until read returns 0, which happens once the child has exited and
closed its write end and the pipe is empty.
Compare only the low 8 bits, matching what the child stored.
A bug in the test: on a mismatch it prints a message but returns instead of calling
exit(1), so run exits with 0 and the test is reported OK.
The other failure paths here use exit(1).
Double the next request size, up to the size of buf: 1, 2, 4,
…, 8192, then 12288.
killstatus: a killed process exits with status -1
kill in xv6 does not stop a process at once. kkill only sets
p->killed (kernel/proc.c:611) and wakes the victim if it is sleeping; the victim notices the next time it is in
usertrap (on a system call, kernel/trap.c:57, or any other trap,
kernel/trap.c:81) and calls kexit(-1). This test checks that the parent’s
wait then reports exactly -1.
The child loops on getpid so it enters the kernel constantly. Repeating 100 times
covers the different moments at which the kill can arrive: while the child is in
user code, in the middle of a system call, or not yet running.
The child loops on a cheap system call, so it enters usertrap all the time
and sees killed within one call.
Wait one clock tick so the child is usually running before the kill arrives.
Ask the kernel to kill the child. This only sets a flag; it does not wait for the child to die.
A killed process exits through kexit(-1) in usertrap, so its status
must be -1.
killzero: kill(0) must not poison the next process
A regression test for a bug fixed just before this commit (git log commit
bd77f8e, “prevent kill(0) from marking UNUSED proc as killed”).
An unused slot in the process table has pid 0, because freeproc resets
it. Before the fix, kkill searched for pid == 0, found the first unused
slot, and set its killed flag. allocproc does not clear killed (only
freeproc does, kernel/proc.c:168), and it picks the first unused slot,
normally the same one. So the next fork usually produced a child that was already
killed: at its first trap into the kernel (here typically the exit(7) system
call) usertrap ended it with status -1. The fix is
the check at kernel/proc.c:605.
The trigger: ask to kill “process 0”. No process has pid 0; only unused slots do.
With the fix, kkill returns -1 at once.
The child’s very first system call is exit. If its slot had been marked killed,
usertrap would end it with -1 before exit(7) ran.
Seeing 7 means the child was not born killed.
preempt: CPU-hogging processes cannot starve the others
Two children spin forever without making a system call. If the kernel never took
the CPU away from a running process, they would occupy two CPUs indefinitely, and
the third child and the parent could only run on a third CPU. xv6 preempts with the
timer interrupt: every tick usertrap calls yield
(kernel/trap.c:85–86), so the scheduler can run someone else.
The test passes if the parent receives the third child’s byte through the pipe and
can then kill and reap all three. Killing spinners also tests that a timer interrupt
alone (no system call) is enough for a process to notice killed.
As the comment says, it proves something only with at most two CPUs. xv6 boots with
three by default (CPUS := 3 in the Makefile), so a free CPU usually exists and
the test would pass even without preemption. The output shows kill... wait... before OK.
The first child spins forever in user code. It makes no system calls, so only a timer interrupt can take its CPU away.
The third child sends one byte through a pipe, then also spins forever. It can send the byte only if it gets a CPU.
The parent blocks until that byte arrives. With two CPUs taken by spinners, this happens only if the scheduler preempts them.
Another return where exit(1) was probably meant: the test would be reported OK,
and the three spinning children would be left running forever.
Kill the three children and reap them. A spinner notices killed on its next timer
interrupt (kernel/trap.c:81). wait(0) passes a null pointer: the parent does not
need the statuses.
exitwait: exit and wait, 100 times
The parent forks a child that exits at once with status i, then waits for it,
checking that kwait returns the right PID (process ID) and status. It is a race
test: the child may already be a zombie when the parent calls wait, or the
parent may already be asleep in wait when the child exits.
The kernel code that makes both orders work is the pairing of wait_lock and the
child’s p->lock. kexit holds the child’s p->lock from setting
ZOMBIE until it has switched away; kwait takes that lock
(kernel/proc.c:384) before freeing the slot, so the slot is never freed and reused
while the child is still running on its kernel stack. The sleep and wakeup under
wait_lock makes sure the parent’s sleep cannot miss the child’s wakeup.
kwait must return the pid of the child it reaped; this parent has only one.
The status must be the i the child passed to exit, copied out of the
zombie's xstate.
The child exits at once, so its exit races with the parent’s call to wait.
reparent: children of an exiting parent must not leak
Each round, the test’s child forks a grandchild and exits at once. The grandchild
also exits. Whichever order these happen in, the grandchild loses its parent, and
reparent must hand it to init (user/init.c), whose wait loop
reaps it.
If reparenting ever lost a process, it would stay a zombie forever, occupying
one of the 64 (NPROC) slots in the process table. 200 rounds is more
than 64, so leaked zombies would fill the table and a fork would fail.
The child cannot report that failure through its exit status, because the parent
waits with wait(0) and ignores it. Instead the child kills the parent itself
(line 959): the parent then exits with -1, and run reports
FAILED.
Remember the test process’s pid, so a grandchild-level failure can be reported by killing it.
The child forks a grandchild and, without waiting for it, exits on line 962. The grandchild runs the same line 962 and exits too.
A failing fork most likely means leaked processes have filled the table. Kill the
test process so the failure is reported.
twochildren: two exits at the same moment
1000 times, the parent forks two children that both exit immediately, then waits
twice. With several CPUs, both children can be in kexit at the same time,
each calling wakeup on the same parent while the parent may be anywhere in
kwait. The test checks only that both wait calls return, so it fails by
hanging (a lost wakeup) or by a kernel panic, not by a message.
forkfork: forking on several CPUs at once
Two children each fork and reap 200 grandchildren, concurrently. On a
multiprocessor this has several CPUs inside kfork, allocproc,
kexit and kwait at the same time, competing for the
process-table locks, pid_lock (in allocpid) and
wait_lock. A missing lock shows up as two processes given the same slot
or PID (process ID), a panic, or a hang. If any grandchild fork fails, its parent exits
with 1 and the test reports fork in child failed.
forkforkfork: a fork bomb that must stop cleanly
The child starts a fork bomb: every process loops forever, forking a copy of
itself each time round, so the number of processes doubles until the 64-slot
process table is full. At that point fork fails, and the kernel must report it
as -1 (allocproc returns 0) instead of crashing.
The way to stop the bomb is a file. A process that sees a fork fail creates
stopforking, and every process checks for that file each time round and exits
when it appears. The parent also creates it after about two seconds, in case
fork never fails.
Most of the processes are grandchildren or deeper, so when their parents exit they
are handed to init (reparent), which has to reap dozens of
zombies at once. The final pause(10) gives them a second to finish
before the next test needs free process slots.
Each process checks whether it is time to stop.
Fork again. If the process table is full, fork returns -1, and this process raises
the stop signal by creating the file.
20 ticks; a tick is about 0.1 s (kernel/trap.c:177), so this is about two seconds.
Create the stop file, in case no fork ever failed.
Wait another second for the orphaned processes to see the file, exit, and be reaped
by init.
reparent2: regression test for an exit/wait deadlock
The comment describes two bugs fixed in 2019 (git log commit d175bea). Back
then each process’s parent field was protected by per-process locks, and exit
had to lock its parent and then itself and its children. Handing children to init
could take locks in an order that deadlocked against init’s own wait. And
because the parent could change while exit waited for the lock, exit sometimes
released a different parent’s lock than it had acquired, which triggered
panic: release.
Today one global lock, wait_lock (kernel/proc.c:27), protects every
parent field and is always taken before any p->lock, so neither bug can occur.
The test stays as a guard: 800 times, a child forks twice (4 processes in all) and
they all exit at once. Each one that outlives its parent is handed to init, so
init keeps receiving new children while it is reaping others.
Two forks make four processes (the child, two of its children, and one grandchild),
all exiting immediately. As each parent exits, its living children are reparented to
init, possibly while init is in wait.
mem: use up all memory, free it, allocate again
The child calls malloc for 10001-byte blocks until it fails, so the process
grows with sbrk until the kernel runs out of physical pages. uvmalloc
then has to undo the partial growth and return an error (kernel/vm.c:229), not
panic. Then the child frees every block and asks for 20 KiB. That request is bigger
than any single freed block, so it succeeds only if free in
user/umalloc.c merged neighbouring free blocks back together.
Doing this in a child matters: when the child exits, all its pages go back to the
kernel, which drivetests later verifies by counting free pages.
The special case for status -1 is for students’ versions of xv6 from a lab that
makes sbrk lazy: there, running out of memory can show up as a page fault that
kills the child instead of malloc returning 0.
Allocate until malloc returns 0, chaining the blocks into a list: the first 8
bytes of each block hold a pointer to the previous block. The list needs no memory of
its own.
Walk the list and free every block. Each next pointer is read before the block holding it is freed.
20 KiB is more than any one freed block, so this fits only if free merged
adjacent blocks.
-1 is the status of a process killed by the kernel, for example after an unexpected page fault. The test accepts it for the reason in the comment above.
sharedfd: two processes writing through one descriptor
After fork, parent and child hold the same struct file, because
kfork copies descriptors with filedup
(kernel/proc.c:287). So they share one offset. Both write 1000 ten-byte
chunks through it, the child cs and the parent ps, at the same time.
If the shared offset works, every chunk lands at a fresh offset and the file ends up
with exactly 10000 of each letter. filewrite makes that so by calling
writei and advancing f->off while holding the inode’s
sleep lock (kernel/file.c:161–164): one process’s write and offset update
finish before the other’s begin. If two writes read the same offset before either
advanced it, one chunk would overwrite another and a count would come up short.
After fork, both processes run the same loop. They choose different letters, c
for the child and p for the parent, and buf here is a local array, not the global.
Both processes write through the same fd, which refers to one shared struct file
and so one shared offset.
Read the file back and count the letters. The file is a whole number of 10-byte
chunks, so every read fills buf completely.
Both counts must be exactly 1000 × 10: no chunk lost or overwritten.
fourfiles: four processes allocate blocks at once
Four children each write 6000 bytes into their own file at the same time, so
several CPUs can be inside balloc at once, searching the same
free bitmap block for free blocks. The buffer cache gives each block
buffer a sleep lock, so only one process at a time examines and updates the
bitmap. Without that, two files could be handed the same disk block.
The check reads each file back and requires 6000 bytes, all equal to that file’s own digit. A shared block would show up as another file’s digit.
Each child fills its copy of buf with its own digit, 0 to 3.
createdelete: four processes edit one directory
Four children create and delete files in the same directory at the same
time, each with its own first letter (p, q, r, s). Each creates 20 files and,
after every even-numbered one, deletes the file with half that number, so files 1
to 9 end up deleted and files 0 and 10 to 19 remain.
Every create and delete reads and rewrites directory entries of the same
directory inode; create and sys_unlink hold its
sleep lock while doing so. A locking mistake could let two processes claim the
same free slot (dirlink), losing one entry, or let an unlink clear the
wrong one. The parent then checks for exactly the expected survivors and removes
them.
After creating file number i (for even i > 0), delete file number i / 2. Over
the run, files 1 to 9 are deleted.
Files 0 and 10 to 19 of every child must exist; files 1 to 9 must not.
unlinkread: an unlinked file lives on while open
Unix lets you delete a file that is still open: the name goes away at once, but the
inode and its data stay until the last descriptor is closed. In xv6,
sys_unlink lowers the link count (nlink) to 0, and iput frees
the inode only when both the link count and the in-memory
reference count reach zero (kernel/fs.c:357).
The test unlinks unlinkread while fd is open, creates a new file under the same
name, and checks that fd still reads the old hello and can still be written.
The final close is what frees the old inode.
Open the file again and keep fd open across the unlink.
Remove the name. The link count (nlink) becomes 0, but fd still references the inode.
A new file under the old name. It gets a different inode, so it must not affect fd.
fd still reads the old 5 bytes, hello, not the new file’s yyy.
Writing to an unlinked but open file must also work.
The last reference goes away; now iput frees the old inode and its blocks.
linktest: hard links and the cases link must refuse
link("lf1", "lf2") gives the same inode a second name, a
hard link. After lf1 is unlinked, the data must still be reachable as lf2.
Then three calls that sys_link must refuse:
- linking to a name that already exists (
dirlinkfails), - linking from a name that does not exist (
nameifails), - linking a directory (
.), refused atkernel/sysfile.c:139. Links to directories could create loops in the tree.
On the first of these, sys_link has already increased the link count before it
discovers the clash, so its bad: path (kernel/sysfile.c:176) must lower it
again. A mistake there would leave lf2 with a count of 2, so the unlink on
line 1415 would not free it. The test itself would not notice: the leak shows up
only as a lost inode.
The new name lf2 already exists, so the link must fail.
lf2 was just removed, so the source does not exist.
. is a directory; sys_link refuses to link directories.
concreate: race create and link on the same names
For each of 40 names C0, C1, …, the parent and a fresh child both try to make
the name exist at the same moment. Depending on i, each one either creates it with
open(O_CREATE) or makes it a hard link to C0. So two processes race to add
the same name to the same directory, sometimes by different system calls.
Exactly one directory entry per name must result. create and
dirlink both check whether the name exists and add it while holding the
directory’s sleep lock, so the second process finds the name already there:
create opens the existing file, and link fails. If the check and the add were not
under one lock, both could see “absent” and both add an entry.
A local struct laid out like dirent: a 2-byte inode number and a 14-byte
name, 16 bytes in all.
Who links and who creates depends on i: the parent links when i % 3 == 1, the
child when i % 5 == 1, and otherwise each creates. For i = 1, 16 and 31 both link.
Read the directory itself and count the C files
The parent opens . and reads it as raw data. In xv6 a directory is a file of
16-byte entries (dirent): a 2-byte inode number and a 14-byte
name. Reading it with read is allowed because the directory is opened read-only.
The local struct de has the same layout as struct dirent.
Every C name must appear exactly once: a duplicate means the race above added two
entries, and fewer than 40 means one was lost.
Read the directory 16 bytes, one entry, at a time.
An entry with inode number 0 is a free slot.
Pick out two-character names starting with C and turn the second character back
into the index i.
The same name seen twice: two processes both added it.
Race open against unlink
Now, for each name, one process opens and closes it six times while the other
unlinks it six times (for i % 3 == 2, both unlink). Only the first unlink can
succeed; the rest must fail cleanly.
This exercises the hand-off between lookup and freeing. An open that has found the
name holds a reference, so iput in the unlinking process must not free the
inode until that open’s close. And once the name is gone, the repeated unlinks
must fail at the lookup instead of lowering the link count a second time. Several
names are hard links to C0, so unlinking them only lowers C0’s
link count (nlink).
For i % 3 == 0 the child opens and the parent unlinks; for i % 3 == 1 the roles
are swapped; for i % 3 == 2 both unlink.
linkunlink: random link, unlink and create on one name
Parent and child each perform 100 random operations on the name x: create it,
make it a link to the cat program, or remove it. The pseudo-random numbers come
from a linear congruential generator, seeded differently in each process so they do
different things: a small case of randomized testing.
The comment says what it looks for: deadlocks. sys_unlink
locks the directory and then, while still holding it, the file’s inode.
sys_link needs both too, but it releases the file’s lock
(kernel/sysfile.c:153) before taking the directory’s. If it held the file’s
lock while waiting for the directory’s, it could wait on an unlink that is in turn
waiting for the file: each would hold what the other needs.
Linking cat is harmless: unlinking x again only lowers cat’s
link count (nlink) back to 1.
Different seeds in parent and child, so the two processes make different choices.
Advance the generator. The multiplier and increment are the classic constants from
the example rand in the C standard; unsigned arithmetic wraps around without
undefined behavior.
Make x another name for the cat program. This fails harmlessly if x already
exists.
subdir: build a two-level tree
A tour of path name resolution in namex. The test builds /dd
containing a file ff and a subdirectory dd, which contains ff. Along the way it
checks that a non-empty directory cannot be unlinked (isdirempty,
kernel/sysfile.c:230), that an absolute path (/dd/dd) and relative paths reach
the same place, and that dd/dd/../ff names dd/ff (contents ff, not FF).
It also makes a second link dd/dd/ffff and removes the original name.
Because file names are fixed, a leftover dd from an earlier failed run makes
the first mkdir fail.
dd contains ff, so it is not empty and must not be removable.
An absolute path: namex starts from the root instead of the current directory.
.. inside dd/dd leads back to dd, so this opens dd/ff. Its content ff
(lowercase) distinguishes it from dd/dd/ff, which holds FF.
Give dd/dd/ff a second name, then remove the first. The file lives on as
dd/dd/ffff.
Walk up and down with ..
Four chdirs with .. in them. Starting in /dd, dd/../../dd goes down to
/dd/dd, up twice to /, and down to /dd again. dd/../../../dd goes one more
level up than exists: .. in the root directory points to the root itself (that is
how mkfs builds it), so the extra .. stays at / and the path still ends in
/dd. ./.. returns to /. Then the second link made earlier must still give
the 2 bytes FF, and the removed name must stay gone.
Change into dd. The following paths are relative to /dd.
One .. too many: the root’s .. is the root, so the path still works.
Back to /, so the rest of the test uses paths relative to the root.
Operations that must fail
A list of requests that namex, create and the system calls must
reject, each with its reason:
dd/ff/ff:ffis a file, not a directory, so nothing can be inside it (kernel/fs.c:703). Tried withopen,link,mkdirandunlink.dd/xx/ff:xxdoes not exist.open("dd", O_CREATE):createfinds an existing directory where a file was asked for (kernel/sysfile.c:283).open("dd", O_RDWR)andO_WRONLY: directories cannot be opened for writing (kernel/sysfile.c:355); only the kernel writes directory entries.link("dd/ff", "dd/dd/ffff"),mkdir("dd/dd/ffff"): the new name exists.chdir("dd/ff"): not a directory (kernel/sysfile.c:446).
Each must return -1 without changing anything.
Tear the tree down in order
Removal must go from the bottom up. unlink("dd") fails while dd/dd still exists,
and succeeds after dd/dd is gone. Removing a subdirectory also lowers the parent’s
link count (nlink) (the subdirectory’s .. entry counted as a link to it,
kernel/sysfile.c:238), which is what lets dd be freed completely.
The error message on line 1714 says dd/dd/ff where the call is about dd/dd/ffff.
dd still contains dd/dd, so this must fail.
bigwrite: writes bigger than one transaction
A single file-system transaction may write at most MAXOPBLOCKS (10)
blocks, so filewrite splits a large write into pieces of 3 blocks
(3072 bytes) and commits each in its own transaction (kernel/file.c:153–172).
This test writes sizes from 499 up to just under 12 KiB, in steps of 471 bytes so
the pieces start and end at many different offsets within a block, twice per file.
The comment says “larger than the log”, which overstates it: the largest write here
touches 13 data blocks (the second 12274-byte write spans file blocks 11 to 23),
more than one transaction may use but less than the 30-block log
(LOGBLOCKS). A write that skipped the split would use more log space than
begin_op reserved for it; that only overflows the log (and makes
log_write panic with too big a transaction) when other file-system
operations are running at the same time, so bigwrite alone would not catch it.
Mainly it checks that a split write still reports the full count.
Sizes 499, 970, 1441, …, up to 12274, the largest below 12288 bytes (12 blocks’ worth).
Each write must report the full size, even though the kernel commits it as several
transactions.
bigfile: write a file in odd-sized pieces and read it back
Writes 20 chunks of 600 bytes, chunk i filled with the byte value i, and then
reads the file back in 300-byte pieces, checking that every piece holds the right
value and that the total is 12,000 bytes.
Neither size is a multiple of the 1024-byte block size, so almost
every write and read starts or ends in the middle of a block, and many cross
from one block into the next. That exercises the offset arithmetic in
writei and readi (off % BSIZE, BSIZE - off % BSIZE) and the
block lookup in bmap. The file needs 12 blocks, exactly the 12 direct
blocks of an inode, so it never reaches the indirect block.
Each 600-byte chunk is read back as two 300-byte halves, which is why read number i
must contain the value i / 2. Checking the first and last byte of each half is
enough to catch data from the wrong chunk or the wrong place. A short read before the
end, a wrong byte, or a wrong total fails the test with exit(1).
An enum is a common way to give a name to an integer constant inside a function.
SZ = 600 is deliberately not a divisor of the 1024-byte block size.
Fills the chunk with the byte value i, so each 600-byte region of the file is
recognizable when read back.
Reads half a chunk at a time. Reads therefore start at offsets 0, 300, 600, …, most of them in the middle of a block, and some (such as 900 to 1200) cross a block boundary.
Read number i covers half of chunk i / 2. Checking the first and last byte is
enough to catch data from the wrong chunk.
fourteen: path components longer than DIRSIZ
A directory entry stores a name in exactly DIRSIZ = 14 bytes, with no room
for a terminating NUL when the name is 14 characters long (kernel/fs.h:54). This
test checks the two rules that follow from that layout:
- a 14-character name is stored and found again correctly, even though it is not NUL-terminated on disk;
- a longer name is silently cut to its first 14 characters, both when creating and
when looking up. The cut happens in
skipelem, which copies at mostDIRSIZbytes of each path element (kernel/fs.c:676), and comparisons usenamecmp, which compares at mostDIRSIZbytes.
So 123456789012345 and 12345678901234 name the same thing. The test creates a
directory with the 14-character name, then a subdirectory and a file through
15-character spellings, opens the
file through the 14-character ones, and checks that creating an existing directory
through either spelling fails. Any mismatch means the kernel stored or compared names
wrongly.
Exactly 14 characters: the name fills all DIRSIZ bytes of the directory entry, with no
NUL after it.
The second component has 15 characters. skipelem keeps only the first 14,
so this creates 12345678901234/12345678901234.
All three 15-character components are cut to 14 characters, so the new file is
12345678901234/12345678901234/12345678901234, inside the two directories just made.
Opening by the 14-character spelling must find the file created under the 15-character one.
This directory already exists, so mkdir must fail; create finds the
existing entry with dirlookup.
The same check through the other spelling. The error message prints the two path
components in the wrong order; it should say 123456789012345/12345678901234.
The first two unlinks fail, because they name the inner directory (under its two spellings), which still contains the file. Then the file is removed, the 15-character spelling of the same file fails because it is already gone, and the inner directory (now empty) and the outer one are removed.
rmdot: the kernel refuses to unlink . and ..
Every directory contains the entries . (itself) and .. (its parent). Removing
either would break the tree: .. is how a path climbs upward, and the parent’s
link count (nlink) counts the child’s .. entry. sys_unlink refuses both
names explicitly (kernel/sysfile.c:221).
The test tries all the ways to name them: . and .. from inside the directory,
then dots/. and dots/.. from outside, where the final path element is still .
or ... Every attempt must fail. Finally it removes the now-empty dots itself,
which must succeed. A kernel that let unlink(".") through would corrupt link
counts; the test notices because the call returned 0.
unlink(".") must fail. Removing the entry would make the directory unreachable through
its own . and corrupt link counts.
The same refusal when . is the last element of a longer path:
nameiparent returns dots with the name ., and
sys_unlink checks that name (kernel/sysfile.c:221).
dirfile: a plain file cannot be used as a directory
Creates an ordinary file dirfile and then tries every operation that needs a
directory in that position: chdir into it, open or create dirfile/xx, mkdir,
unlink and link under it. All must fail.
The checks live in two places. sys_chdir tests the type of its target
(kernel/sysfile.c:446). Path lookup in namex refuses to look inside
anything that is not a directory (kernel/fs.c:703), so every path that goes
through dirfile fails, whichever system call uses it. The link attempt also
tests a cleanup path: sys_link raises the link count of README before it
looks up the new name, and must lower it again when that lookup fails.
The last part checks the rules for opening a directory: sys_open refuses
to open one for writing (kernel/sysfile.c:355), and a directory opened read-only
cannot be written through its descriptor, because the open file (struct file) is marked not
writable and filewrite rejects it.
README exists, so sys_link raises its link count before it fails to look up
dirfile/xx. It must then lower the count again at its bad: label
(kernel/sysfile.c:176–182).
fd is a read-only descriptor for a directory. filewrite returns -1
because the open file is not writable (kernel/file.c:139).
iref: path lookup must not leak inode references
The kernel keeps in-memory copies of inodes in a table of only NINODE = 50
slots. Each lookup takes a reference on the inodes it passes through and must drop it
again with iput; a lookup that forgets one leaves a slot permanently in
use, and once all 50 are taken iget panics with iget: no inodes.
The test repeats a batch of lookups NINODE + 1 times, each time one directory
deeper, so that a leak of even one reference per iteration would exhaust the table.
The batch deliberately includes failing lookups, because error paths are where
references are most easily forgotten: the empty name "", and README, which does
not exist inside irefd. The source comment names the case that motivated the test:
when nameiparent is given a path with no elements, namex must
still iput the starting directory before returning failure
(kernel/fs.c:723).
The return values are ignored; the test fails only by crashing the kernel. Cleanup climbs back up and removes the 51 nested directories.
NINODE + 1 = 51 rounds: one more than the in-memory inode table holds, so even a leak
of one reference per round would fill it.
mkdir(""): the path has no elements at all. nameiparent fails, and must
drop its reference to the current directory first (kernel/fs.c:723–726).
README is looked up relative to the current directory irefd, where it does not
exist, so this fails early inside sys_link. That is another error path that
must release its references.
The cleanup climbs back up one level at a time and removes each irefd, deepest first.
Each one is empty by then, because its child was removed in the previous round.
forktest: fork fails cleanly when resources run out
Forks up to 1000 children, each of which exits at once, until fork returns -1. Then
it waits for all of them. It checks that at least one fork worked, that fork did fail
before 1000 (there are not enough resources for 1000 processes), that wait returns
exactly as many children as were created, and that one more wait reports “no
children” with -1.
When fork fails, kfork must undo whatever it had already set up, or later
tests would find less memory. The leak check in drivetests would catch that.
The source comment is outdated for this configuration. It says that inside usertests
memory runs out before process slots do. But xv6 now has 128 MiB of RAM and
NPROC = 64 slots, and a usertests process needs only a few dozen pages. So
the process table fills first: allocproc finds no UNUSED slot. Run in QEMU
with a print added, the loop stops at n = 60: 64 slots minus init, the shell,
usertests and the test’s own process.
As the block note explains, the last sentence of this comment no longer holds:
process slots (NPROC) run out first.
fork returned -1: no free process slot (or no memory). This is the expected way out of
the loop.
Each child exits at once, so the children use no CPU time. They remain as zombies, still occupying process slots, until the parent waits for them.
Succeeding 1000 times would mean the kernel creates processes without limit, which it cannot have the resources for.
With all children reaped, wait must report “no children” with -1
(kwait), not hang and not return a stale pid.
sbrkbasic: sbrk fails cleanly, grows byte by byte, and survives fork
sbrk moves the process’s break, the end of its memory, and returns the old
break. In this xv6, sbrk asks for eager allocation (SBRK_EAGER): the
kernel allocates and maps the pages immediately, through sys_sbrk,
growproc and uvmalloc.
The test has three parts:
- A child asks for 1 GiB, far more than the 128 MiB of RAM. The call must fail with
SBRK_ERROR, or (with a lazy kernel) touching the memory must get the child killed. Only a child that writes to every page and survives exits with 1. - The parent grows its memory 1 byte at a time, 5000 times. Each call must return exactly the previous break, and each new byte must be writable, including the ones that land on a freshly allocated page.
- After a
fork, parent and child each grow by 2 more bytes. Both must see the same break, which checks thatkforkcopied the sizep->szalong with the memory.
The test ends with exit(xstatus) in the parent, so the child’s verdict becomes the
test’s verdict.
1 GiB is about eight times the machine’s memory. With eager allocation,
uvmalloc runs out partway, frees what it got, and sbrk returns
SBRK_ERROR.
This loop runs only if sbrk claimed success. With lazy allocation, touching one byte
per page would eventually find no memory, and vmfault's failure would get the
child killed. Reaching exit(1) means the kernel really gave out 1 GiB.
sbrk(1) must return exactly the previous break, even when the byte lands on a page
that was allocated by an earlier call.
Writes the new byte. If the kernel had moved the break without mapping the page behind it, this store would fault and the test process would be killed.
Runs in both parent and child. The second call must return a + 1, so both processes
must have started from break a: the child inherited p->sz exactly.
sbrkmuch: grow to 100 MiB, shrink, regrow
Grows the process until its break is at 100 MiB (BIG), most of the machine’s 128
MiB, and writes to the very last byte. Then it checks deallocation: shrinking by one
page with a negative argument must move the break down, and growing again must
return a page that is zero, not the page that still held the 99 written earlier.
That last check is the interesting one. Shrinking goes through growproc
to uvmdealloc, which unmaps the pages and frees them. Growing goes through
uvmalloc, which takes a fresh page from kalloc and zeroes it
(kernel/vm.c:233). If the kernel had only lowered p->sz without unmapping, the
new mapping would hit the old one and mappages would panic with
mappages: remap; if it handed back a page without zeroing, the 99 would leak into
the “new” memory. Either way the test (or the kernel) fails.
Finally it shrinks all the way back to where it started, so the 100 MiB returns to the free list before the next test.
The size needed to put the break exactly at 100 MiB. amt is about 100 MB, which fits in
the int that sbrk takes.
The very last byte below the new break must be mapped and writable.
Shrinks by one page. uvmdealloc unmaps the page holding lastaddr and frees
it.
After the shrink and regrow, lastaddr is in a new page, which uvmalloc
zeroed. Seeing the old 99 means the page was never released, or was reused without
being cleared.
The inner sbrk(0) is the current break, so this shrinks by exactly the amount grown
since oldbrk.
kernmem: user code cannot read kernel memory
The kernel lives at KERNBASE (0x80000000, 2 GiB) and above in physical
memory, and in the kernel’s own page table. A user process’s page table has no
mappings there at all, so a user load from those addresses must cause a
page fault and kill the process.
The test tries 40 addresses, spaced 50,000 bytes apart over the first 2 MB of physical
memory, where the kernel’s code and data begin. Each attempt happens in its
own child, because the first successful fault kills the process that made it. In the
kernel, the fault arrives in usertrap as a load page fault (cause 13).
vmfault refuses it because the address is above the process size
(kernel/vm.c:463), so usertrap marks the process killed and it exits with
status -1 (kernel/trap.c:78). That -1 is what the parent waits for.
40 addresses, 50,000 bytes apart, starting at KERNBASE, where the kernel’s
code begins.
The *a is evaluated before printf is called, so the fault happens before anything
is printed. Reaching the printf means the read worked.
-1 is the status usertrap gives a process it kills (kernel/trap.c:82).
Any other status means the child got past the read.
MAXVAplus: no writes at or above MAXVA
MAXVA (0x4000000000, 2^38) is the end of the address range xv6 uses. The
test tries to write at MAXVA, then 2 * MAXVA, 4 * MAXVA, and so on, doubling
until the bit falls off the top of the 64-bit value: 26 addresses, from 2^38 to 2^63.
Each write must kill the child that makes it.
These addresses are invalid twice over. In Sv39 a virtual address must have
bits 63–39 equal to bit 38; none of these do, so the hardware raises a page fault
without even consulting the page table. And in software, vmfault refuses
them because they are above the process size. Run in QEMU, each child produces a
usertrap(): unexpected scause 0xf message (a store page fault) with stval equal
to the address, and is killed.
The test matters because the kernel’s page-table code must never be asked to look up
such an address: walk panics on any va >= MAXVA (kernel/vm.c:101).
volatile makes the compiler keep a in memory and perform every read and write of it.
That stops it from reasoning about the values a takes in this loop and transforming
the loop or the store below.
Shifting left moves the single set bit up one place each round: 2^38, 2^39, …, 2^63. The next shift pushes it out of the 64-bit value, leaving 0, which ends the loop.
The store must fault. It never reaches the page table: the address is not valid in Sv39, and it is above the process size.
sbrkfail: a failed allocation must give back what it took
When uvmalloc runs out of memory partway through a large request, it must
free the pages it already allocated for that request (kernel/vm.c:228–231). This
test makes that happen and then checks that no memory was lost.
Ten children in turn each try to grow to 100 MiB. The first one succeeds and keeps the
memory; with 128 MiB of RAM only the first can get its 100 MiB, and later ones fail
partway. Each child reports success or
failure through a pipe and then waits to be killed, still holding whatever it
got. While they are all still alive, the parent asks for one page. That page can only
come from memory released by the failed attempts, so if a failed uvmalloc leaked
its partial allocation, nothing is left and the parent’s sbrk fails: failed sbrk leaked memory.
After killing and reaping the children, a last child asks for 1000 MiB, which must
fail with SBRK_ERROR rather than succeed or crash.
If no child’s allocation ever failed, the test prints a hint but continues: in that case it has not tested what it meant to.
Each child tries to grow to 100 MiB. Only the first one or so can succeed with 128 MiB
of RAM; later ones fail partway, after uvmalloc has already allocated some
pages, and must give those back (kernel/vm.c:228–231).
Reports the outcome to the parent through the pipe: 0 for failure, 1 for
success.
The child keeps its memory and sleeps until it is killed. pause sleeps for a number
of timer ticks (sys_pause).
Waiting for the child’s byte means the parent forks the next child only after this one has finished trying. So the attempts happen one at a time, and each one sees the memory left by the previous ones.
The real check. The successful children still hold their memory, so this page can only come from memory that failed attempts released.
kkill marks the child as killed and wakes it from its sleep. It exits with -1
when it next passes through usertrap (kernel/trap.c:81–82), and wait
reaps it.
1000 MiB. 10 * BIG = 1,048,576,000 still fits in a signed 32-bit int, so this really
is a request for that much, which must fail.
sbrkarg: system calls can use freshly sbrk'd memory
Passes newly allocated memory to system calls in both directions: as the source
buffer of a write (the kernel reads it with copyin) and as the array that
pipe fills in (the kernel writes it with copyout).
With this kernel’s eager sbrk the pages are already mapped, so both calls simply
work. The test exists for kernels that allocate lazily (as the “lazy allocation” lab
versions of xv6 do, and as sbrklazy does here): there, the kernel itself must
notice an unmapped but legal page while copying and allocate it, the way
copyin and copyout call vmfault in this kernel (kernel/vm.c:389–393).
A kernel that treated such a page as a bad pointer would make write or pipe fail.
The file is unlinked right after it is opened; the open descriptor keeps it alive
until close.
The kernel reads the new page with copyin to write it to the file. The page
is all zeros.
The kernel writes the two new descriptors into the new page with
copyout (sys_pipe).
validatetest: wild string pointers must not crash the kernel
Calls link("nosuchfile", p) with p stepping one page at a time from 0 to about
1.1 MB. The new-name pointer covers the program’s own text and data, its stack
guard page, its stack, and then hundreds of pages that are not mapped at all.
sys_link copies both names in with argstr before doing anything
else (kernel/sysfile.c:129). For an unmapped page or the guard page,
copyinstr fails cleanly and link returns -1. For a mapped page, the
kernel reads whatever bytes are there as a name, and link then fails because
nosuchfile does not exist. Either way the answer is -1; the real test is that the
kernel never faults while reading a user pointer. A kernel page fault would make
kerneltrap panic.
p steps one page at a time through about 1.1 MB of address space, 276 values in all.
p is the new name. The kernel copies both names before doing anything else, so this
is a test of copyinstr on each page.
bsstest: uninitialized globals start out zero
C promises that a global variable without an initializer, like uninit here, starts
out as all zeros. Such variables go in the .bss section section, which takes no space in
the executable file: the ELF program header (segment) just says the segment is larger in
memory (memsz) than in the file (filesz).
It is the kernel’s job to supply the zeros. kexec allocates the whole
memsz with uvmalloc, which zeroes every page it hands out
(kernel/vm.c:233), and then copies in only filesz bytes. The test scans all 10,000
bytes; any non-zero byte means the kernel exposed stale memory.
10,000 bytes in .bss section. Because it has no initializer, it takes no space in the executable file; the kernel must provide it as zeros.
bigargtest: exec rejects arguments too big for the stack
The new program’s arguments are copied onto its one-page user stack. If they do
not fit, kexec must fail instead of writing below the stack, into the
guard page and the program’s data.
A child builds 31 arguments (MAXARG - 1) of 399 spaces each, about 12 KB in total,
three times the 4096-byte stack, and calls exec("echo", ...). sys_exec
can still fetch them (one kernel page per string), but kexec checks each string
against the stack bottom and gives up (kernel/exec.c:104), freeing the new
page table at its bad: label.
The child cannot report failure through its exit status, because if exec wrongly
succeeded, echo would run and exit with 0 too. So it leaves a file instead:
bigarg-ok exists only if exec returned, and the parent checks for it.
static places the 32-pointer array in the program’s .bss section rather than on the
one-page stack. Its elements start out as 0.
One 400-byte buffer of spaces, ending in a NUL: a 399-character string. All 31 argument pointers below point at this same buffer.
31 arguments plus the NULL that ends the list: the most sys_exec accepts
(MAXARG = 32). Copied onto the new stack, they need 31 × 400 = 12,400 bytes,
three times its 4096.
Must fail and return. kexec sees that the strings would go below the stack
(kernel/exec.c:104) and jumps to bad:.
Reached only if exec returned. The file is the child’s way of saying so: if exec
had succeeded, echo would also exit with status 0, so the status alone cannot tell.
fsfull: an old, unused test that fills the disk
Creates files f0000, f0001, … and writes each one block at a time until a write
comes up short, stopping when a file gets no data at all; then deletes them.
This function is never run. It takes no char *s parameter, so it does not fit
the struct test type, and it appears in neither quicktests nor slowtests.
Its comment is also outdated: balloc no longer panics when the disk is
full; it prints balloc: out of blocks and returns 0
(kernel/fs.c:88), and the callers fail cleanly. The test that now checks
disk-full behavior is diskfull.
Each file stops at MAXFILE blocks (268 KiB), because writei
refuses to write past that size.
No char *s parameter, unlike every other test: this function cannot go in the test
tables, and nothing calls it.
Writes one block at a time until a write comes up short, that is, the disk is full or the file has reached its maximum size.
argptest: a buffer at the very end of memory with count -1
Asks read to put -1 bytes into a buffer that starts at the last byte of the
process’s memory (sbrk(0) - 1). The result is ignored; the test passes as long as
the kernel does not crash.
The test was added in 2016, for the x86 version of xv6, to check how the kernel
validated a pointer argument whose size is negative. In this kernel the case is cut off at the top:
fileread rejects any negative count before touching the buffer
(kernel/file.c:111), a check added in commit 2534832.
sbrk(0) - 1 is the last byte of the process’s memory, and -1 asks for an impossible
number of bytes. fileread rejects a negative count at once
(kernel/file.c:111).
stacktest: there is a guard page below the user stack
Below each user stack, kexec leaves one guard page: mapped, but with
the user-access bit cleared by uvmclear (kernel/exec.c:95). A stack
that overflows into it causes a page fault instead of quietly overwriting the
program’s data, which sits right below.
A child reads from one stack-size below its current stack pointer. The stack is
USERSTACK = 1 page and the stack pointer is somewhere inside it, so that
address is inside the guard page. The read must fault. In usertrap,
vmfault declines to help, since the page is already mapped
(kernel/vm.c:466), so the child is killed and exits with -1. In QEMU the child
reports scause 0xd (load page fault) with stval inside the guard page.
Unusually, this test’s parent itself calls exit, turning -1 into 0 (pass) and any
other status into failure.
r_sp reads the stack pointer register with one instruction. It comes from
kernel/riscv.h, which this user program includes.
One stack-size (USERSTACK pages) below a pointer inside the one-page stack
is an address inside the guard page.
*sp is evaluated before printf runs, so the fault happens before anything is
printed.
-1 means the kernel killed the child, which is the expected outcome. This test’s own process then exits with 0 for a pass. Any other status is passed on as the failure.
nowrite: writes to forbidden addresses must fault
Each child writes to one forbidden address and must be killed for it. If the write goes through, the child prints a message and exits with 0, and the parent turns that into a failure. The addresses cover each kind of protection:
0, the program’s own code: mapped, but without write permission;0x80000000, where the kernel lives: not mapped in a user page table;TRAPFRAMEandTRAMPOLINE, the top two pages: mapped, but without the user bit, so only the kernel may touch them;MAXVAand0xffffffffffffffff: outside the range xv6 ever maps.
In every case the store raises a store page fault (cause 15), and
vmfault refuses it: the address is either already mapped or above the
process size. Run in QEMU, all six children print scause 0xf and are killed,
including the last, even though a 4-byte store to an address ending in f is also
misaligned.
Compare copyout, which enforces the same read-only rule for the kernel’s
own writes into user memory (kernel/vm.c:363–365).
One address per kind of protection: read-only program text, kernel memory,
TRAPFRAME, TRAMPOLINE, MAXVA, and the very top of the
64-bit range.
A volatile pointer, so the compiler must really perform the store; storing through
an address like 0 could otherwise be treated as undefined behavior and optimized
unpredictably.
0 means the store worked and the child reached exit(0). The kernel’s kill would have
produced -1.
pgbug: a wild pointer above MAXVA used to crash the kernel
A regression test for a bug fixed in 2019 (commit 402e7b5). The pointer
0xeaeb0b5b00002f5e is far above MAXVA. Back then,
copyinstr cast the page address to a 32-bit uint, which chopped off the
high bits. walkaddr checked the truncated address, which was mapped, but the
copy then added the full, untruncated offset to the physical address, so the kernel
read from a wild address and took a page fault of its own, which is a panic.
The fix removed the cast and made walkaddr reject addresses at or above
MAXVA (kernel/vm.c:127). Today exec(big, ...) fails when
argstr cannot copy the path, and pipe(big) fails when
copyout refuses the destination (kernel/vm.c:352). Both return
values are ignored: the test passes if the kernel survives to run exit(0).
A global, so the address is loaded at run time from the data segment. Bits 63–32 hold
0xeaeb0b5b; the low 32 bits, 0x00002f5e, look like a plausible small user address.
That is what made the old 32-bit truncation so dangerous.
The path pointer is invalid, so sys_exec fails at its first
argstr (kernel/sysfile.c:466); argv is never looked at.
The kernel would write the two new descriptors to big; copyout refuses the
address, so pipe closes the new pipe and returns -1.
sbrkbugs: shrinking memory in awkward amounts
A regression test for bugs in uvmdealloc, each run in its own
child: shrink to size 0, shrink into the middle of the first page, and shrink by 10
bytes, too little to free a page. Each case once panicked the kernel. The children’s
exit statuses are ignored (wait(0)); the test passes if the kernel survives.
The interesting part is that in the first two cases the child shrinks away the very
code it is running, and in the third its stack. So none of the children reaches its
exit(0). Running the test in QEMU shows what happens:
- cases 1 and 2: the
sys_sbrksystem call stub (code page 5) is gone when the kernel returns to it, so the next instruction fetch faults (scause 0xc) and the child is killed; - case 3: the code survives (the break is set in page 10), but the stack page above
it does not. The
sbrkwrapper reloads its return address from the stack, that load faults (scause 0xd), and the child is killed before callingsbrk(-10).
So with this build’s memory layout the third case no longer tests what its comment
describes. What all three still test is that kexit and
uvmfree can tear down a process whose memory has been cut to an odd size.
Shrinks the process to size 0, freeing every page, including the code that is running.
The kernel must set p->sz to 0, so that when the process exits, uvmfree
has nothing left to free. The old bug, as the comment says, left p->sz at a wrong
value, and exit then panicked.
“user page fault here”: the child never reaches exit(0). Its next instruction
fetch faults, and the kernel kills it.
Shrinks to 3500 bytes, inside the first page. uvmdealloc must keep page 0,
since PGROUNDUP(3500) is 4096, and free everything above it.
Sets the break at 10 pages + 2048 bytes, in the middle of a page. In this build that frees the child’s stack.
Intended to shrink by 10 bytes without freeing a page. Commit e1a3730 (2019) fixed
uvmdealloc for this case, which used to compute a nonsensical range to unmap.
As the block note explains, in this build the child is killed just before it gets here.
sbrklast: copying to and from the last, partial page
Arranges for the process size to end 10 bytes short of a page boundary: grow to a
page boundary, add a page, add 10 bytes (which maps one more page), then shrink by 20
bytes. The shrink drops the page that held the extra 10 bytes (uvmdealloc
frees whole pages above the rounded-up new size), so the last mapped page is now
only partly inside the process.
Then it uses an address 64 bytes below the end in three system calls: as a path for
open (copyinstr), as the source of a write (copyin) and as
the destination of a read (copyout). The page is mapped and the
addresses are below p->sz, so all three must work and the byte must survive the
round trip. A kernel that got the arithmetic around a partial last page wrong, for
example by unmapping one page too many, would fail here.
The test leaves a file named x behind; it never unlinks it.
Rounds the break up to a page boundary, so the following steps land at known offsets within pages.
+10 bytes maps one more page; -20 bytes then unmaps it again. The break ends 10 bytes below a page boundary.
64 bytes below the break, in the last page that is still mapped.
The page holds the path x, which copyinstr must be able to read.
sbrk8000: a negative argument that looks like a large positive one
sbrk takes an int. The constant 0x80000004 does not fit in a 32-bit signed
int, so it arrives as -2,147,483,644: a request to shrink by about 2 GiB, more than
the process has.
sys_sbrk sends negative requests to growproc, which computes
the new size as sz + n in unsigned 64-bit arithmetic. Because n is larger than
sz, the sum wraps around to a huge number. uvmdealloc sees a “new size”
that is not smaller than the old one and does nothing. So the call changes nothing
and returns the old break.
The test then reads and writes the last byte of memory. That only works if the kernel
neither grew the process by 2 GiB (treating the value as unsigned) nor freed pages
because of a wrapped-around size. lazy_copy relies on the same behavior.
0x80000004 converted to int is -2,147,483,644, a request to shrink by about 2 GiB.
The kernel treats it as a no-op (see the block note).
Reads and writes the last byte of memory. If the break had moved in either direction, this would fault or touch the wrong page.
badarg: exec with a bad argument pointer must not leak memory
A regression test for commit d940fd1 (2019). sys_exec copies each
argument string into a page of its own from kalloc. It allocates the page
before copying, so when the copy fails (here because 0xffffffff is far above the
process’s memory), it must free that page on the way out
(kernel/sysfile.c:495–497). Before the fix it did not.
Repeating the bad call 50,000 times would leak about 195 MiB at one page per call,
more than the 128 MiB of RAM. A leaking kernel therefore runs out of memory long
before the loop ends, and the leak check in drivetests would catch even a smaller
leak. The test itself checks nothing; it exits 0 if it gets through.
About 4 GB, far above this process’s memory: fetchstr fails to copy the
string.
sys_exec has already taken a page from kalloc for this argument
when the copy fails. It must free it on its bad: path (kernel/sysfile.c:495–497).
lazy_alloc: a 1 GiB lazy region, touched sparsely
sbrklazy grows the process without allocating anything:
sys_sbrk only raises p->sz (kernel/sysproc.c:54–63). A page gets
real memory the first time the program touches it. The access raises a
page fault, and usertrap calls vmfault, which allocates a
zeroed page and maps it (kernel/trap.c:71–74). The faulting instruction is then
run again and succeeds.
This test reserves 1 GiB, eight times the machine’s RAM, so it can only pass if the allocation really is lazy. It then writes to one page in every 64 (each page stores its own address) and reads all of them back. That touches 4096 pages, 16 MiB.
When the test process exits, uvmfree walks the whole 1 GiB range, and
uvmunmap skips the pages that were never mapped (kernel/vm.c:203–206).
The leak check in drivetests confirms that the 4096 pages came back.
1 GiB, eight times the machine’s physical memory. It still fits in int (2^30), the
argument type of sbrklazy.
Reserves 1 GiB without allocating any of it, and returns the old break.
Touches one page in 64. Each first touch causes a page fault that
vmfault handles by mapping a zeroed page. Each page stores its own address,
so a page mapped in the wrong place would be noticed.
lazy_unmap: shrinking really unmaps lazily allocated pages
Reserves 1 GiB lazily, touches one page in every 4096 (16 MiB apart, 64 pages in
all), and then checks each of them in a separate child. The child shrinks the
process by the whole 1 GiB and writes to the page again. That write must kill the
child: the page is now beyond the process size, and vmfault refuses it. If
the old page were still mapped, the write would succeed, the child would exit 0, and
the test would report memory not unmapped.
Two kernel paths are involved. A negative sbrklazy is not lazy at all:
sys_sbrk sends every negative request to growproc and
uvmdealloc (kernel/sysproc.c:50), which free the pages. And each
fork copies a process whose size is over 1 GiB, which works only because
uvmcopy skips pages that were never allocated (kernel/vm.c:306–310).
Otherwise each child would need 1 GiB of RAM.
PGSIZE * PGSIZE = 16 MiB: touches one page in 4096, 64 pages in all.
A negative argument makes even sbrklazy shrink at once (kernel/sysproc.c:50).
The touched pages are unmapped and freed.
Must fault: the address is now above the process size, so vmfault refuses
it and the child is killed. Exiting with 0 means the old page was still mapped.
lazy_copy: system calls meeting lazy and invalid addresses
Three separate checks on how the kernel’s copying functions treat unusual user addresses.
- A lazy page as a system-call argument. The path given to
opensits in a page thatsbrklazyreserved but nobody touched yet. Whencopyinstrfinds no mapping, it callsvmfaultitself (kernel/vm.c:419–424), which allocates a zeroed page, so the path is the empty string. The result ofopenis ignored (the empty path in fact opens the current directory, and the descriptor is never closed), so the test only catches a kernel panic. - Shrinking by more than the whole size.
sbrk(-(sz + 1))must leave the process alone and return the old size. The new sizesz + nwraps around, as insbrk8000, souvmdeallocdoes nothing. - Addresses no copy may use.
readinto, andwritefrom, six addresses must fail: two unmapped pages just below theTRAPFRAME, the trapframe andTRAMPOLINEpages (mapped, but not for user access), andMAXVAand twice MAXVA. Each fails insidecopyoutorcopyin, soreadreturns -1 throughreadi, andwritereturns -1 becausewriteicopied 0 of the 512 bytes.
p + 8192 is 8 KiB into the new lazy region, on a page nobody has touched.
copyinstr faults it in (kernel/vm.c:419–424), finds a 0 byte at once, and
open receives the empty path.
Asks to shrink by one byte more than the whole process. The new size sz + n wraps
around to a huge number, which uvmdealloc treats as “not smaller”, so nothing
happens and sbrk returns the old break.
Two unmapped pages just below TRAPFRAME (0x3fffffe000), the trapframe
page, the TRAMPOLINE page (0x3ffffff000), MAXVA
(0x4000000000) and twice MAXVA.
Reading into a bad address: copyout fails inside readi, which
returns -1.
Writing from a bad address: copyin fails inside writei, which
copies nothing, so filewrite returns -1.
lazy_copyinstr: a path that runs into a lazy page
Places a one-character path, /, in the last byte of the first of two lazily
reserved pages. Storing it faults that page in, while the second page, starting at
p[4096], stays unmapped. When copyinstr copies the
path, it reads /, reaches the end of the page, and looks for the terminating NUL on
the next page. That page has no mapping yet, so copyinstr calls
vmfault (kernel/vm.c:421–424), which maps a fresh zeroed page. Its
first byte, 0, ends the string.
The test passes if open succeeds and fstat reports that what it opened is a
directory (T_DIR), the root. A copyinstr that gave up at the page boundary, or
did not handle lazy pages, would make open fail.
The first sbrk rounds the break up to a page boundary, so that p[4095] and
p[4096] fall on opposite sides of a page boundary.
Rounds the break up to the next page boundary (or adds a whole page if it is already on one), using ordinary eager allocation.
Two more pages, reserved lazily. Neither is mapped yet.
The last byte before the boundary is in the first lazy page; this store faults it in.
The second lazy page, starting at p[4096], is still unmapped.
The path starts one byte before a page boundary. copyinstr reads /, moves
to the next page, faults it in through vmfault, and finds a 0 byte there.
lazy_sbrk: growing right up to the trapframe
Grows the process lazily, 1 GiB at a time, until it is almost 256 GiB
(MAXVA), then sets the break exactly one page below
TRAPFRAME, the highest a process may grow. It then allocates that last
page eagerly, checks it is zero-filled, and checks that growing by even one more byte
fails, whether eagerly or lazily.
The top two pages of every address space, the trapframe and the
trampoline page, are already mapped. Commit 8402fc9 (2025) added this test, which at
first panicked the kernel: nothing stopped sbrk from growing into those pages, and
mappages panicked on the existing mapping. The companion commit c71a6c4
made both kinds of growth stop at TRAPFRAME: growproc checks
eager requests (kernel/proc.c:243), and sys_sbrk checks lazy ones,
including overflow of the addition (kernel/sysproc.c:58–61).
Some of the error checks are dead code. A pointer is never less than 0, so
p < 0 and p1 < 0 are always false; the compiled code
(user/usertests.asm) contains no test for them at all. The checks that work are the
exact comparisons with the expected address and with -1.
Exiting this process is a lot of work: uvmfree visits each of the roughly
67 million page numbers below its size, even though almost none are mapped.
255 steps of 1 GiB each, all lazy, so no memory is allocated. The value returned by
the first sbrklazy is discarded at once; the loop takes the new break from
sbrklazy(0). The p < 0 check between the two calls can never be true (see the
block note), and the compiler drops it.
The distance from the current break to one page below TRAPFRAME. It is less
than 1 GiB, so it fits in an int.
Lazily grows so that the break is exactly one page below TRAPFRAME, leaving
room for exactly one more page.
Eagerly allocates the page [TRAPFRAME - PGSIZE, TRAPFRAME). growproc
allows it because sz + n equals TRAPFRAME, which is not greater than it.
The page must be writable and zero-filled like any newly allocated memory.
One more byte, eager or lazy, would reach the trapframe page; both must fail. Comparing
with -1 as a uint64 is the correct way to test for SBRK_ERROR.
partial_write: a failed write must still log what it changed
A regression test for a write-ahead log bug fixed in commit fb0fed8 (2026). The test’s own comment at the top lists the steps.
The file starts as A. The test writes 2 bytes starting at the last byte of its
memory: the first byte, X, is valid, and the second is beyond the process size.
Inside writei, copyin copies the X into the cached disk block
and then fails on the second byte. So the block in the buffer cache has been
changed, even though write reports failure (-1).
The bug: on that error path writei released the block without calling
log_write. The block was modified but not logged, so nothing would ever
write it to disk, and nothing kept it in the cache. Reading the file right away still
showed X from the cache. But once the block was evicted, a later read fetched the
old A from disk. The fix logs the block on the error path too
(kernel/fs.c:560–564).
To force the eviction, the test writes 64 KiB to another file, far more than the 30
buffers of the cache (NBUF), and then reads the byte again. Note the
design decision this reveals: xv6 keeps the partial change and reports an error,
instead of undoing it.
The last byte of the process’s memory gets X; the byte after it, p[0], is beyond the
process size.
The 2-byte write copies X into the file’s cached block, then fails on the second byte.
The call must return -1.
Right after the failed write, the block is still in the buffer cache, so this read
shows X even on the buggy kernel.
64 writes of 1 KiB each pass 64 blocks through the 30-buffer cache, which pushes the
testfile block out.
This read must come from disk. Without the fix it returns the old A.
unlinkcwd: looking up paths from a deleted directory
A regression test for commit 9da28f5 (2026), which fixed a panic found with
these shell commands: mkdir /a; mkdir /a/b; cd /a/b; rm /a/b; rm /a; ls ...
After the two unlinks, the current directory b has no names left (link count 0),
but it stays in memory because the process’s cwd still refers to it. Its parent
a, though, is gone completely: its inode was freed. b’s .. entry still holds
a’s old inode number. Looking up .. from b used to fetch that freed inode,
and ilock panicked with ilock: no type.
The fix makes namex refuse to search any directory whose link count is 0
(kernel/fs.c:707), and makes create refuse to create entries in one
(kernel/sysfile.c:269). So open("../") and open("../c", O_CREATE) must fail.
The test only prints a message if they succeed; the failure that really matters, a
kernel panic, would stop the whole run.
The current directory is /a/b. Both directories are then removed; b survives in
memory only as this process’s current directory.
../ from the deleted b. Before the fix, this lookup reached the freed inode of a
and panicked. Any descriptor here would be at least 3, so > 0 detects success.
Must not create a file in a directory that no longer exists.
The table of quick tests
quicktests lists every test that runs in a few seconds or less, in the order
runtests runs them. Each entry pairs a test function with its name: the name is
what usertests <name> matches and what the output prints. The first 38 entries are
defined in the first half of this file.
The order is roughly from basic to demanding: copying data across the user/kernel
boundary, then files, processes, and concurrent file-system work, then memory
(sbrk, lazy allocation, protection), and last the newest regression tests. Order
matters little for correctness, because each test runs in its own process and most
tests clean up their files. It does matter for diagnosis: a failure in a basic test early on
explains later failures. The table ends with a {0, 0} entry, so that loops over it
need no separate length.
Together with slowtests, run, runtests, countfree, drivetests and
main, this table is the test harness.
One test: a function pointer to the test and its name. Every test function takes
the name as its argument s, so its error messages can say which test failed. The same
statement declares the type struct test and defines the array quicktests.
Tests (from the first half of this file) that pass bad addresses to the kernel’s
copying functions copyin, copyout and copyinstr.
Basic file-system and exec tests: truncation, inode reference counts, opening, creating and writing files, directories, and running a program.
Process tests: pipes, kill, preemption, exit and wait, reparenting to init,
nested forks, and running out of memory.
File-system tests with more pressure: shared and concurrent writes, concurrent create
and delete, links, subdirectories, large files and names, and the tests in this half
from bigfile to iref.
fork exhaustion and the memory tests of this half: sbrk growth and failure,
memory protection, exec’s limits, and lazy allocation with sbrklazy.
The two newest regression tests, both from 2026.
The end marker. runtests stops at the entry whose name is 0.
bigdir: a directory with 500 entries
Creates one file bd and gives it 500 more names in the current directory with
link, then removes all 501 names. Every link makes dirlink scan the
directory for a free slot and dirlookup scan it for a duplicate, so the
test exercises linear search over a large directory. At the end, the file’s
link count (nlink) goes from 501 down to 0, and the inode is freed when the last name
goes.
The comment “directory that uses indirect blocks” is outdated. With 16-byte entries and 1024-byte blocks, the 12 direct blocks hold 768 entries. Even with the root directory’s own two dozen or so entries, about 525 are in use, so the directory never reaches its indirect block. The comment dates from the x86 xv6, whose blocks were 512 bytes, which would put the same entries well past the 12 direct blocks.
The names are x plus two characters, computed from i / 64 and i % 64 by adding
them to '0'. That gives characters from 0 to o in ASCII, never / or NUL, and
a different name for each i.
manywrites: concurrent writers, looking for deadlock
Four children write to the disk at the same time, each to its own file (ba to
bd), for 30 rounds. In each round child ci writes the 12 KiB buf ci + 1 times
and then deletes the file. Each 12 KiB write is split by filewrite into
four transactions of 3 KiB (kernel/file.c:153).
So four processes on several CPUs keep calling begin_op and
end_op, filling and committing the write-ahead log, and sending
requests to the virtio disk driver at once. As the comment says, the goal is to
provoke a deadlock in the disk driver, a bug that only shows up when requests
overlap. A deadlock would make the test hang rather than fail; howmany can be raised
to run longer.
Each child exits with 1 on any error, and the parent passes the first non-zero status on as its own.
badwrite: a write from a bad buffer must not leak a disk block
A regression test for commit 7c7ed20 (2019). Writing one byte to an empty file
makes writei allocate the file’s first data block with bmap
before it copies the byte from the user. Here the copy then fails, because
0xffffffffff is not a valid user address. The bug was that writei wrote the inode
back to disk only when the file had grown, so on this failure path the newly
allocated block was never recorded in the on-disk inode. After close, the
in-memory copy has no references, and iget never hands out a slot’s cached
contents once its count is 0: it recycles the slot as invalid. So when unlink later
freed the file, it re-read the inode from disk, which did not list the block, and the
block was lost for good. Today writei calls iupdate unconditionally
(kernel/fs.c:573–576).
The test repeats create, bad write, close, delete 600 times, then checks that one
honest 1-byte write still succeeds. If every round leaked a block, the disk would
eventually be full and that last write would fail. (balloc no longer
panics when the disk is full, despite the comment.) The comment’s caveat applies:
the freshly built file-system image has roughly 990 free blocks, so 600 rounds alone
might not use them all up.
execout: exec when memory is almost gone
kexec allocates memory at many points: a new page table, the
program’s segments, the stack, and the pages sys_exec uses for argument
strings. If any allocation fails, exec must free everything it already took and
return -1, leaving the old program intact. This test makes allocations fail at as
many different points as it can.
For each avail from 0 to 14, a child first takes all free memory, one page at a
time, and then gives back avail pages. Then it tries to run echo. With 0 pages
free, exec fails at its first allocation; with a few more, it gets further before
failing; eventually there is enough and echo runs. Closing descriptor 1 first keeps
echo’s output, if it runs at all, off the screen.
The children’s exit statuses are ignored. The test passes if the kernel does not
panic. Any page lost on a failure path is caught by the leak check in
drivetests. Commit 5860dcd (2020) added this test and fixed the exec bugs it
found.
diskfull: run out of disk blocks, then keep going
Fills the disk and then checks that operations needing a new block fail cleanly instead of panicking.
First it creates files big0, big1, … and writes each one full
(MAXFILE blocks), until a write fails because balloc found no
free block. A fresh file system has about 990 free blocks, so this takes about four
files.
Then it creates up to 128 empty files. An empty file needs an inode but no data
block, so these succeed while the root directory still has free slots in the blocks
it already owns. Once it needs one more block for its entries, dirlink
fails, and create must undo the half-made inode. Finally it calls mkdir,
which must fail too, because a new directory needs a block for its . and ..
entries (kernel/sysfile.c:302).
Commits 872fa88 and 8621be8 (2022) made these paths tolerate a full disk; before,
balloc panicked. Everything is deleted at the end. Note that when a write fails,
the file is closed twice (lines 3240 and 3244); the second close returns -1
harmlessly.
outofinodes: run out of inodes
The disk has room for only 200 inodes (NINODES in mkfs/mkfs.c), and every file
uses one. This test creates up to 1024 empty files and expects creation to fail
somewhere along the way. When it does, ialloc must print
ialloc: no inodes and return 0 (kernel/fs.c:219), and open must return -1.
Before commit 7c1810e (2022) the kernel panicked instead.
The test stops creating at the first failure and then deletes every name it might
have made, so the inodes come back for the following tests. The names zz00 to
zzOO come from the same digit-plus-offset trick as in bigdir.
linkoverflow: link count must not overflow
A file’s link count (nlink) is a short, at most 32767. Before commit fa4789f (2026),
the link call that would give a file its 32768th name wrapped the count around to
-32768. Now
sys_link refuses to go past NLINK_MAX (kernel/sysfile.c:145).
The test creates /lof and links it up to 32768 times. A single directory cannot
hold that many entries, because a directory file is at most MAXFILE blocks,
so the links are spread over 64 directories /d_aa to /d_dp, 512 names in each.
When link fails, the test uses stat to check that the count stopped at the
maximum; a failure earlier than that is a real error. After the loop, the count must
not be negative.
This test is not run: its entry in slowtests is commented out, because it is
extremely slow (commit 35b0884). It also cleans up only /lof itself, leaving the 64
directories and 32766 links behind.
The table of slow tests
Tests that take a long time, mostly because they fill the disk or the inode table or
write a lot of data. drivetests runs them after the quick tests, unless
usertests -q asked for the quick tests only. The format and the {0, 0} end marker
are the same as in quicktests.
linkoverflow is commented out because it takes too long, even for the slow tests.
Run it by uncommenting this line (it cannot be selected by name while it is not in a
table).
run(): one test in its own process
Runs one test function in a fresh child process and turns the child’s exit status into a verdict: 0 is a pass, anything else a failure.
A separate process for every test is the key design choice of this
test harness. A test may run its process out of memory, close its standard
output, change its working directory, unmap its own stack, or get killed by the
kernel, and none of that affects the harness or the next test. When the child is
killed for a bad memory access, usertrap makes it exit with -1, which
counts as a failure here. That is why the tests that expect a kill (like
kernmem) check for -1 in their own children and turn it into a normal exit code.
The kernel’s usertrap(): unexpected scause ... messages often appear in the middle
of the test name: OK line. The file’s header comment says they can be ignored when
the test prints OK.
The parameter void f(char *) is written like a function, but C adjusts a function
parameter type to a pointer, so it means exactly void (*f)(char *).
Printed before the test starts and without a newline, so the verdict appears on the same line, unless the test or the kernel prints something in between.
The child runs the test. A test fails by calling exit(1) (or being killed); if the
function returns normally, the child exits with 0, a pass.
The test process is the harness’s only child, so wait returns its status. A test’s
own children that it did not reap are given to init when it exits, so they cannot
confuse this wait.
Returns 1 for a pass and 0 for a failure, so callers can write if (!run(...)).
runtests(): run one table, or one test from it
Walks a test table until its {0, 0} end marker, running either every test or, if
justone names a test, only that one. Returns how many tests it ran, or -1 if one
failed and the run should stop.
continuous comes from main: with -C (value 2) a failure
is reported by run but does not stop the run; otherwise the first failure prints
SOME TESTS FAILED and ends this table.
Loops until the entry whose name is 0, the end marker of the table.
With no name given, every test runs. With a name, only the exact match runs. That
could be in either table, which is why drivetests searches the slow table too.
Without -C, the first failure ends the whole run. With -C, run has already
printed FAILED and the loop goes on.
countfree(): count free memory pages from user space
A user program cannot ask the kernel how much memory is free; xv6 has no such system
call. So countfree measures it: it grows its own memory one page at a time with the
eager sbrk, which takes a real page from kalloc each time, until the
kernel says no. The number of successful calls is the number of free pages. Then it
gives everything back in one shrink.
The count is a little lower than the true number of free pages, because some free
pages become page-table pages for the growing process. That does not matter, because
drivetests only compares two counts taken the same way in the same process. The
page-table pages stay with the process after the shrink (uvmunmap frees
only the data pages), so the second count does not pay for them again.
For a moment the whole machine has no free memory. That is safe here because nothing else is running while the harness counts.
Remembers the current break so it can be restored exactly afterwards.
Each successful sbrk(PGSIZE) took one page from kalloc. The loop ends
when uvmalloc finds no free page and sbrk returns SBRK_ERROR.
One shrink back to the starting break returns all the counted pages to the free list.
drivetests(): run everything, then check for leaked memory
Runs the quick tests, then (unless quick) the slow tests, and around them compares
free memory before and after. If fewer pages are free at the end than at the start,
some test made the kernel lose memory, even if every test said OK. Several tests
(badarg, execout, sbrkfail, the lazy-allocation tests) rely on this check
to catch the leaks they are designed to provoke.
With continuous set (-c or -C) the whole sequence repeats forever, which is a
way to find bugs that appear only rarely, such as races. -c stops at the first
failure; -C reports failures and keeps going.
Returns 0 for success and 1 for failure; main turns that into the program’s exit status.
A do ... while loop: the body runs once, and again for as long as continuous is set.
Free pages before any test runs.
Quick tests first. A failure ends drivetests with 1 unless -C was given. Otherwise
n is how many tests ran, added to ntests.
Then the slow tests, unless -q. With a single test name, this searches the slow table
too, without announcing it.
The leak check. Fewer free pages now than before means some kernel path lost pages: allocated them and never freed them, even after every test process exited.
A test name that matched nothing in either table is an error, probably a typo.
main(): parse the command line
usertests accepts at most one argument:
| Command | Meaning |
|---|---|
usertests |
all quick and slow tests, once |
usertests -q |
quick tests only |
usertests -c |
all tests, repeated until one fails |
usertests -C |
all tests, repeated forever, failures reported but ignored |
usertests name |
only the test called name, from either table |
Options cannot be combined: the usage message lists [-c] [-C] [-q] [testname] as if
they could, but any second argument is rejected.
The program ends by printing ALL TESTS PASSED. test-xv6.py waits for exactly that
line after typing usertests, usertests -q or usertests <name> into xv6’s shell
(test-xv6.py:203–206), so this one line
is what the project’s automated testing checks.
The three options, each valid only as the sole argument. -q skips the slow tests,
-c repeats until a failure, -C repeats forever.
Any other single argument that does not start with - is taken as a test name.
More than one argument, or an unknown option.
A non-zero exit status tells whoever ran usertests that something failed.
The line test-xv6.py waits for. The shell prints its prompt after this, when
usertests exits.