user/grind.c

Purpose and headers

The comment is the whole specification: random system calls, in parallel, forever. kernel/stat.h supplies struct stat and kernel/fcntl.h the O_ flags. kernel/param.h, kernel/fs.h, kernel/syscall.h, kernel/memlayout.h and kernel/riscv.h are included but nothing from them is used in this file.

do_rand(): the Park–Miller "minimal standard" generator

This is a Lehmer pseudo-random number generator, the “minimal standard” proposed by Park and Miller in 1988 and copied here from FreeBSD’s C library. Each call computes

x_new = 16807 × x mod (2³¹ − 1)

where 16807 = 7⁵ and 2³¹ − 1 = 2147483647 is a prime. For any starting x between 1 and 2³¹ − 2, the sequence visits every number in that range before repeating. The numbers are not random, but they are spread out well enough to choose operations. A starting value of 0 would be useless (0 × 16807 is 0 forever), which is why lines 29–30 map the stored value into the range 1 … 0x7ffffffe first.

Lines 31–35 use Schrage’s method to compute the product modulo 2³¹ − 1 without overflowing 32-bit arithmetic: write 2³¹ − 1 = 127773 × 16807 + 2836 (as the comment says), split x into hi = x / 127773 and lo = x % 127773, and then 16807 * lo - 2836 * hi equals 16807 × x mod (2³¹ − 1), or that minus 2³¹ − 1 if it is negative. Every intermediate value stays below 2³¹. On xv6’s 64-bit RISC-V a long is 64 bits, so the direct product would not overflow anyway; the method matters on 32-bit machines, where the code was written.

The result is shifted down by one (line 37) to the range 0 … 0x7ffffffd, stored back as the new state and returned. The next call adds the 1 back on line 30.

rand(): one shared random stream

rand_next is the generator’s state (its seed at the start). It is a global, so fork copies it: every child starts with its parent’s current value, and changes in one process do not affect another. iter and main change it before and after forking so that each worker gets a different stream.

go(): set up a worker

go is the body of one worker; which_child (0 or 1) only selects the progress letter. Its locals:

• fd is a file descriptor that several operations share: one opens a file into it, others read or write through it, so writes can go to a file that the other worker has meanwhile unlinked. It starts as -1, an invalid descriptor, which is deliberate: close(-1), read(-1, …) and write(-1, …) must fail cleanly (in argfd).
• buf is static so its 999 bytes live in the program’s data, not on the one-page user stack. 999 is not a multiple of the 1024-byte block size or of any power of two, so writes start and end in the middle of disk blocks.
• break0 records the size of the process’s memory at the start (sbrk(0) returns the current end without changing it), so that operation 16 can shrink back to it.

Lines 58–63 make sure the directory /grindir exists (mkdir fails harmlessly if it does; both workers try) and that chdir into it works, then return to /. Every relative path below is relative to /.

The main loop, and a progress mark

Each pass picks one operation. Every 500 passes the worker writes one letter, A for worker 0 and B for worker 1, with a single write so the letters from the two workers never mix within a character. In QEMU at this commit, each worker did about 2000 operations in 90 seconds (four letters each).

rand() % 23 gives 0 … 22. Operations 1 to 22 follow; 0 matches no branch, so about one pass in 23 does nothing.

Operations 1–4: create and remove a and b through tangled paths

These create and delete the two shared names /a and /b, but always through paths with .. in them. grindir/../a is /a; grindir/../grindir/../b is /b. Each such lookup goes through namex, which follows the .. entry of grindir back to the root, one component at a time, locking each directory in turn.

1 and 2 create and immediately close a file (sys_open → create, then sys_close). 3 unlinks /a. 4 changes into grindir, unlinks ../b (resolved from there), and changes back. Only the chdir is checked: grindir must always exist. The opens and unlinks may fail, for example if the other worker turned a into a directory.

Operations 5–8: keep a file open while others change it

5 and 6 close the shared descriptor and open /a or /b in it (/./grindir/./../b tests . components too). 7 writes 999 bytes through it and 8 reads 999 bytes.

Between these steps, the other worker may unlink the file, recreate a new file under the same name, or link the name to something else. Writing to an open file whose name is gone is legal: the inode stays alive, with link count (nlink) 0, until the descriptor is closed, and then the final iput frees it. This is exactly the orphaned inode situation that user/forphan.c tests for crashes; here it is the normal path through filewrite → writei and fileclose → iput that gets exercised, thousands of times.

Operations 9–10: a directory with the same name as a file

9 tries to make /a a directory, create /a/a inside it (through the path a/../a/./a), and remove it again. 10 does the same with /b, written as /../b, which tests that .. in the root directory leads back to the root (the root’s .. entry points to itself, as mkfs/mkfs.c creates it).

Whether these succeed depends on what a or b currently is. If it is a file, mkdir fails and so does the path through it, because a file is not a directory. While such a directory is not empty (the other worker may be between the create and the unlink of this same operation), plain unlinks of a or b fail, because sys_unlink refuses to remove a non-empty directory.

Operations 11–12: hard links between a and b

11 removes /b and makes it a second name for /a; 12 does the reverse. Both use paths that leave the root (../b from / is /b). link (sys_link) fails if the source is a directory or the target name exists, and must undo its link-count increment when it fails (sys_link's bad: path). A hard link means that unlinking a no longer frees the file, because the count is still 1 for b; a wrong count here would free a file that still has a name or leak one that has none.

Operations 13–14: fork, exit, and orphans

13 is the plain cycle: fork a child that exits at once, and wait for it (kfork, kexit, kwait). The parent’s copy of the memory, open files (including fd) and current directory must all be duplicated and then released without leaks.

14 forks a child that forks twice more, making four processes, and all of them exit without waiting. The worker waits only for its direct child; the grandchildren are orphans that reparent hands to init, which reaps them (user/init.c). This exercises the parent-pointer bookkeeping in kexit, reparent and kwait, now protected by wait_lock. In 2019, before wait_lock existed, reparent could deadlock on per-process locks (fixed in commit d175bea, six weeks before grind was added).

A fork failure is treated as a real error: with only a handful of processes per worker, the 64-entry process table should never be full, so failure means slots are leaking.

Operations 15–16: grow and shrink memory

15 grows the process’s memory by 6011 bytes with sbrk (sys_sbrk → growproc → uvmalloc); 6011 is deliberately not a multiple of the 4096-byte page size, so the end of memory moves into the middle of pages. 16 shrinks it back to the starting size break0 (uvmdealloc), freeing the pages.

The result is not checked; in principle an sbrk failure would be tolerated, but since operation 16 resets to break0 just as often, the extra memory stays at a few pages.

Operation 17: kill a child in the middle of a file system call

The child creates /a, possibly a slow operation that writes several disk blocks. Meanwhile the parent does a chdir through a roundabout path that ends at / (checked: it must succeed) and then kills the child. Depending on timing, the child is still inside open, has finished, or has already exited.

kkill only sets p->killed and, if the child is sleeping, makes it runnable. The child dies the next time it is about to return to user space (usertrap calls kexit), so a file-system operation is never abandoned half-way through its transaction: a sleeping child woken in begin_op checks its condition again and goes back to sleep if needed. A bug here could leave the log’s count of outstanding operations wrong, which would hang every later file-system call.

Operation 18: a process kills itself

The child kills itself. The kill call returns normally, but on the way back to user space usertrap sees the flag and calls kexit(-1), so the exit(0) on line 151 is never reached. The parent’s wait(0) collects a child that died with status -1.

Operation 19: four processes sharing one pipe

The worker creates a pipe and forks a child; the child forks twice, so four processes share both ends. Each writes one byte and then reads one byte. Since every process writes before it reads, there are always at least as many bytes written as read, so no read can wait forever.

This exercises pipewrite and piperead with several readers and writers on different CPUs, which must take the pipe’s lock and use sleep and wakeup correctly, and pipeclose when the last reference to each end goes away (each of the four processes holds both ends until it exits; the worker closes its own copies on lines 177–178). The parent waits only for its direct child; the other three become orphans for init. A failed read or write prints a message but does not stop the worker.

Operation 20: create a file inside a deleted directory

In a child, so that the chdir does not affect the worker: replace /a with a new empty directory, move into it, and delete its name (../a) while standing in it, the same setup as user/dorphan.c. The directory now has link count 0 but is still the child’s current directory. Then the child tries to create x in it.

At this commit that open fails during the path lookup: namex refuses to go through a directory whose link count is 0 (kernel/fs.c:707), so nameiparent returns 0 and create gives up. create has a second check of its own (kernel/sysfile.c:269) for a directory unlinked in the moment after the lookup. Both checks were added in August 2026 (commit 9da28f5) after the same kind of sequence caused panic: ilock: no type; before them, the new file could be linked into the doomed directory and leak with it. When the child exits, closing its current directory (kexit → iput) frees the orphaned directory.

Any step may also fail because the other worker changed /a in the meantime; then the child ends up doing something else harmless, such as creating and removing /x.

Operation 21: resources must not run out

As the comment says, this must always succeed. It creates /c, writes one byte, checks with fstat that the size is 1 and the inode number is sane, and removes it. Unlike most operations, every step except the unlinks is checked.

Its purpose is to detect leaks. After thousands of operations, if any path forgot to free an inode, a block, a file-table entry or a descriptor, the open or the write would eventually fail (or the kernel would panic, as iget does when the in-memory inode table is full). The i-number check catches a corrupted inode: the disk image has 200 inodes (NINODES in mkfs/mkfs.c), and inode 0 is never used, so valid numbers are 1–199. Anything above 200 is certainly corrupt (the check is one too generous).

The other worker may run operation 21 at the same moment. Then both open the same c, or one unlinks the other’s; each still writes one byte at offset 0 through its own descriptor, so the size is still 1 and the checks still hold.

Operation 22: the pipeline echo hi | cat

This builds by hand what the shell does for echo hi | cat (see pipeline (a | b) and fork and exec), with one extra pipe so the worker can read the result:

echo hi  --aa-->  cat  --bb-->  worker

The first child replaces its standard output with the write end of aa (close(1) then dup, which returns the lowest free descriptor, 1) and runs /echo through the path grindir/../echo, exercising kexec with a path containing ... The second child makes aa’s read end its standard input and bb’s write end its standard output, and runs /cat.

Every process closes the pipe ends it does not use. That is essential: cat sees end-of-file only when every write end of aa is closed, and if the worker or cat itself kept one open, cat would wait forever and so would the worker’s wait.

The worker reads three bytes from bb, waits for both children, and checks that both exited with status 0 and that it received exactly hi\n. The children exit with distinct statuses (1, 2, 4, 5, 6), which the worker prints, so a failed run tells you which step broke; if a fork fails, the worker itself exits with 3 or 7.

The loop never ends

go has no normal way out. A worker ends only by calling exit(1) (or another non-zero status) after a failed check, or by being killed by iter.

iter(): start worker 0

One iteration of the test. It first removes a and b left over from a previous iteration (this fails harmlessly if they are non-empty directories). Then it forks worker 0, which changes its copy of the seed (rand_next ^= 31) so it does not replay the same operations as worker 1, and runs go. The exit(0) after go is never reached.

iter() uses empty parentheses, an empty parentheses in a C declaration; iter(void) would be the modern spelling.

iter(): start worker 1

The same for worker 1, with a different change to the seed (^= 7177). Both workers now run concurrently on different CPUs, against the same root directory.

iter(): wait for a failure, then stop the other worker

The first wait returns only when one worker exits, which, since workers loop forever, means it found an error. Its status is non-zero, so iter kills both workers (the one already reaped has no process left, so that kill fails harmlessly), waits for the survivor, and exits. Initialising st1 to -1 makes the kill happen even if wait failed without storing a status.

With a correct kernel, iter stays in the first wait forever.

main(): run iterations forever

Each iteration runs in its own child process, so whatever state a failed iteration leaves behind (open files, memory, the current directory) dies with it, and the next starts clean. After an iteration ends, main pauses for 20 clock ticks (about two seconds, sys_pause), adds 1 to the seed so the next iteration takes a different random path, and starts again. If fork fails, it pauses and retries.

grind therefore never exits. A kernel bug shows up as a printed grind: … message, a kernel panic (which stops xv6), or the stream of A and B stopping, which means something is stuck: a lost wakeup, a deadlock, or a leaked transaction.