Step 1 of 22

The recorder's hook in acquire

wc (pid 5) has just won the swap on line 37 for its pipe’s lock and recorded lk->cpu on line 41. In the measured copy of the kernel, one call was added right after line 41. That is the moment the lock is truly held and interrupts are off (push_off on line 24), so the recorder cannot be interrupted on this hart.

The recorder keeps, per hart, a small stack of the spinlocks that hart holds. When acquire succeeds, it does three things:

1. For every lock already on this hart’s stack, it counts an edge “held → this one”. Here the stack is empty, so pi->lock gets no incoming edge.
2. It notes whether the hart is inside an interrupt handler (a counter set around devintr) and the current noff.
3. It pushes pi->lock. release pops it again.

Locks are grouped into classes by name: all 64 p->locks are one class proc, every pipe’s lock is pipe. The edges are class edges, which matters later.

A single push_off that is not part of an acquire (in myproc or uartputc_sync) is recorded only when it sets a new nesting record or reaches noff 3.

Step 2 of 22

Sleep-locks are tracked per process

A sleep-lock is held across sleep, and its holder may wake up on another hart. So a per-hart list would lose it. The recorder keeps a second list per process slot, pushed in acquiresleep once lines 31–32 have set locked and pid, and popped in releasesleep.

Here rm holds directory d and is locking the file f inside it (sys_unlink). When f’s lock is granted, the recorder counts a sleep-lock → sleep-lock edge inode → inode. When rm later takes bcache.lock inside bread, it counts inode → bcache for each inode it holds. Sleep-lock → spinlock edges are not counted inside interrupt handlers: a handler runs on whatever process it interrupted but does not act for it.

Two counting details matter when you read the numbers. An acquisition adds one edge per lock already held, so with two inodes held, one buffer acquisition counts twice. And the inner spinlock lk->lk is its own class (inode.lk, buffer.lk, uart.lk). One artifact follows: releasesleep takes lk->lk (line 39) before the hook pops the sleep-lock, so every sleep-lock appears “held” while its own inner spinlock is taken (tx_lock → lk->lk, for one). Those edges are not real nesting, and we ignore them.

Notice line 32: myproc does a push_off of its own, so for a moment noff is 2 here. That extra level shows up in the deepest-nesting results.

Step 3 of 22

Reading the results with Ctrl-P

The recorder prints its tables at the end of procdump, which runs when you type Ctrl-P, inside the UART interrupt, holding cons.lock. Only init and sh existed and both were asleep, so the interrupt was taken in some hart’s scheduler, with a kernelvec frame on the scheduler stack.

The first line of output:

LS BEGIN maxnoff=3 maxsleep=3 edgeoverflow=0

The deepest noff on any hart was 3; the most sleep-locks held by one process at once was 3; and no edge was lost. Then one line per class:

p->lock dominates because wakeup and the scheduler loop each take all 64 of them. Only five spinlock classes were ever taken in an interrupt handler. (The recorder does not check sleep-locks for interrupt context, hence “n/a”.)

One edge in the output exists only because of this readout. procdump calls printk, which takes pr.lock while cons.lock is held: cons.lock → pr.lock, 5 times, all in this interrupt.

Step 4 of 22

Edge 1: wait_lock → p->lock, in kexit

Here is the whole graph. Now the arrows one at a time, starting with the only order xv6 writes down: wait_lock “must be acquired before any p->lock” (kernel/proc.c:26).

wc is exiting. Line 347 takes wait_lock; then three places take p->locks under it:

413,952 is exactly 6,468 × 64: every wakeup walks all 64 slots. The 6,721 own-lock acquisitions match the 6,721 exits in that run, and the 6,722 forks: everyone who was forked, except the sh still alive, exited.

Line 360 releases wait_lock while p->lock stays held into sched. Releasing out of order is harmless; only the order of acquiring can create a wait.

Step 5 of 22

Edge 2: wait_lock → child's p->lock → kmem.lock, the deepest spinlock nesting

The parent side. kwait holds wait_lock (line 376, or 417 after a sleep), takes a child’s lock on line 384, and if the child is a ZOMBIE, frees it on line 398. freeproc calls kfree for the trapframe and every page of the child’s memory, each taking kmem.lock. So this hart holds three spinlocks: noff is 3.

This is the most common of the three noff-3 paths: 227,333 kmem.lock acquisitions at noff 3 in the main run, one per page freed, while reaping about 6,700 children. The second run split them by where wait_lock came from: 65,772 under the first acquire (line 376), 161,314 under the re-acquire after a sleep (line 417). The parent usually had to wait for its child.

kwait also takes its own p->lock under wait_lock, in killed (line 408) and sleep_prepare (line 414), 3,953 times each. But never while holding a child’s: line 403 releases the child first. So no path ever holds two p->locks, and there is no p->lock → p->lock edge in the data.

Step 6 of 22

Edges 3–6: kfork holds the child's lock over four leaves

allocproc returns the new slot with its p->lock held (kernel/proc.c:115), and kfork keeps it while it builds the child. Every lock taken in that window becomes a p->lock → X edge. The second run’s breakdown, for 6,722 forks:

20,205 is almost exactly 3 × 6,722: nearly every process had three open files (fds 0, 1, 2) to share with its child.

Why is this safe? All four are leaves: code holding pid_lock, kmem.lock or ftable.lock acquires nothing, and the recorder confirms none of them has an outgoing edge. itable.lock has exactly one, in iput, which step 13 deals with. A leaf can never be part of a cycle, because a cycle needs every member to wait while holding.

Step 7 of 22

kfork lets go before taking wait_lock

kfork needs wait_lock to set np->parent. Holding np->lock while asking for it would create p->lock → wait_lock, the reverse of edge 1. So line 294 releases the child first.

The recorder confirms both halves. Of 6,722 acquisitions of wait_lock at line 296, the number made while holding anything: 0. Of 6,722 acquisitions of np->lock at line 300: 0.

What if line 294 were moved below line 298? A two-hart deadlock with kexit:

Then every other fork, exit and wait piles up on wait_lock. In the graph this is the arrow p->lock → wait_lock, which would close a two-node cycle with edge 1.

Step 8 of 22

The rarest edge in the graph, once per boot

The p->lock → itable.lock edge had two sources. 6,722 came from idup in kfork. Exactly one came from here: userinit, on hart 0 during boot, holding the first process’s lock from allocproc, calls namei("/"), which reaches iget on kernel/fs.c:697 and takes itable.lock.

namei("/") with no further path elements never locks the inode, so no sleep-lock is involved, and nothing can sleep here: hart 0 is still on its boot stack, before any scheduler runs, with interrupts off since power-on (intena 0).

It is the same edge kfork creates, so it adds no risk. But a measurement that started after boot would never have seen it.

Step 9 of 22

Edges 7–12: every condition lock sits above p->lock

Most edges into p->lock come from three small functions: wakeup (here), and sleep_prepare and killed, which take the caller’s own p->lock. Whoever calls them while holding a condition lock creates that lock → p->lock. The second run, counting p->lock acquisitions (one wakeup is 64 of them):

848,064 is exactly 13,251 × 64: one wakeup(&log) per end_op, and the second run had 13,251 file-system operations.

Never the reverse. A p->lock holder acquires only the four leaves of step 6. That makes p->lock almost a leaf itself, and that is why every condition lock can safely call wakeup while holding its own lock.

Step 10 of 22

The locks interrupt handlers take

An interrupt handler is just one more acquirer, so its edges belong in the graph. The main run found exactly five classes taken inside devintr:

Apart from cons.lock → pr.lock, which only the Ctrl-P readout creates, handlers add no new order: vdisk_lock → p->lock here is the same edge virtio_disk_rw creates in process context. What handlers add is a different danger, a deadlock with the same hart. That is why every one of these five locks is taken with interrupts off everywhere, and why noff > 0 always means SIE = 0 (Locks and interrupt state): a handler can only start on a hart that holds no spinlock at all.

A lock taken by a handler can also never be a sleep-lock: a handler runs on borrowed time and must not sleep. (The recorder does not watch for this; the code has no acquiresleep reachable from devintr.)

Step 11 of 22

Edge 13: log.lock → bcache.lock

log_write records a modified block under log.lock and, the first time a block joins the transaction, pins it in the cache with bpin, which takes bcache.lock: log.lock → bcache.lock, 6,537 times in the second run. Its callers:

The total is less than the 13,991 calls to log_write: a block already in the log is absorbed (line 235) and not pinned again.

bcache.lock is a leaf: in bget, brelse, bpin and bunpin, nothing is acquired under it. And look at the display: two sleep-locks and two spinlocks. Except in iput (next step), sleep-locks always sit outside spinlocks. noff counts only the two spinlocks.

Step 12 of 22

Edge 14: itable.lock → an inode's sleep-lock, the second noff 3

The only place a spinlock is held while a sleep-lock is acquired. When iput drops the last reference to a file with no links, line 362 calls acquiresleep with itable.lock held. Inside, lk->lk is taken, and myproc on kernel/sleeplock.c:32 pushes once more: noff 3, the second of the three deepest paths. 344 times in the main run, each one a file being deleted for good. The second run’s 344 split as: 336 from sys_unlink (rm), 5 from fileclose (an unlinked file closed last), 2 from kexit dropping its working directory, 1 from sys_chdir.

Holding a spinlock while taking a sleep-lock is normally forbidden: if it slept, sched would panic with sched locks. It cannot sleep because of line 357: ref == 1 means this process holds the only reference, and a process must hold a reference to hold or wait for the sleep-lock. Line 363 releases itable.lock before the slow itrunc.

Had it ever slept, sched would have panicked. In 344 tries, it never did.

Step 13 of 22

The one cycle, and why it cannot close

Put three measured edges side by side:

1. p->lock → itable.lock: kfork's idup (step 6).
2. itable.lock → inode lk->lk: iput (step 12).
3. inode lk->lk → p->lock: here, releasesleep calls wakeup holding lk->lk (761,344 times), and acquiresleep calls sleep_prepare holding it.

That is a cycle among spinlock classes. A deadlock along it would need three harts:

Hart 1’s iput only reaches that acquiresleep when I->ref == 1, and the one reference belongs to hart 1’s own process, which has already unlocked I. Hart 0 can only be inside releasesleep or acquiresleep on I if its process holds a reference to I. There is none to hold. Hart 0’s column is impossible, so the cycle cannot close.

The lesson: a class graph over-approximates. Deadlock is about lock instances: the 50 inode locks are 50 locks, and this argument shows that the particular instance in the middle edge is never the one in the last edge. A checker that sees only classes would report this cycle.

Step 14 of 22

Edge 15 and the third noff 3: Ctrl-P

The readout itself produced the third noff-3 path. consoleintr holds cons.lock, procdump → printk holds pr.lock, and every character goes out through uartputc_sync, whose push_off on line 106 adds a third level. The main run reached noff 3 here 27 times, once per character printed, all inside the interrupt handler.

So the three deepest paths are:

Reading the code finds no path to 4 outside a panic. printk is never called with two spinlocks held except here, and kfree/kalloc take nothing more.

Step 15 of 22

Why the spinlock graph has no other cycle

allocproc scans slots taking each p->lock with nothing held (line 115), and under the one it keeps, takes pid_lock (line 125 → allocpid). That is the shape of the whole spinlock graph. Give each class a rank:

Every measured spinlock → spinlock edge goes from a lower rank to a higher one, except itable.lock → lk->lk (step 13). Within rank 1 the edges are wait_lock → kmem, log.lock → bcache, cons.lock → pr: all into rank 3. No two rank-1 locks are ever held together. A path can only move to higher ranks, so it can never come back to a lock that is waiting on it.

This is why the scheduler is safe too: scheduler takes p->lock with nothing held, 4.1 million times in the second run, and under it takes nothing.

Step 16 of 22

Sleep-locks: parent directory, then child, in create

Now the sleep-locks. The inode → inode edge was recorded 736 times in the main run. The second run’s call chains show only two places that hold two inode sleep-locks at once:

Here, x does not exist, so ialloc picks a free inode and line 294 locks it while dp is held: parent, then child. The child is brand new; no one else can be holding it.

The existing-name path is different. Line 281 unlocks dp before line 282 locks ip. The data agree: create:282 never appears holding another inode. That release is what makes open("a/.", O_CREATE) safe: dirlookup returns a itself, and locking it while holding it would be a sleep-lock waiting for itself. acquiresleep has no check for that; the process would sleep forever.

Step 17 of 22

unlink, namex and link

sys_unlink locks the directory d (line 218), looks up f (line 224) and locks it (line 226). Line 221 refuses . and .. before any lookup: . would be the same lock again, and .. would be a parent locked under its child.

Just as telling is where the edge never appeared:

• namex locks each directory on line 702. In the second run no ilock from namex was ever made while holding another inode. Line 720 unlocks the current directory before the loop locks the next, so .. in a path is harmless.
• sys_link locks the file (line 138), but line 153 unlocks it before line 157 locks the new directory. Its dirlink holds only the directory.
• kexec, filewrite, fileread and sys_chdir hold one inode at a time.

On a tree, “ancestor before descendant” is a consistent order, and xv6 keeps the tree a tree by refusing hard links to directories (line 139). The two holders above both take a directory and then something named inside it.

Step 18 of 22

Inode → buffer → buffer: three sleep-locks, and four

Every file operation holds an inode while it reads buffers: inode → buffer. Two places hold two buffers under an inode. bmap holds the indirect block (line 445) while balloc reads the bitmap block (line 75) and then bzero reads the new block; itrunc holds the indirect block while bfree reads the bitmap. The main run’s maximum, 3 sleep-locks, came in two shapes:

The code allows 4: create holds two inodes, and if dirlink must grow a directory past its 12 direct blocks (768 entries of 16 bytes), bmap holds the indirect block under both. No test makes a directory that large. So we wrote a program that fills dd with one file and 765 hard links (768 entries counting . and ..), then creates dd/new. The recorder printed maxsleep=4 with exactly this chain.

Step 19 of 22

Buffer → buffer in commit, with nothing else held

write_log holds a log block (to, line 193) while it reads the home block (from, line 194). install_trans does the reverse copy with the same nesting: log block (line 76), then home block (line 77). In the second run each made 6,537 such pairs, one per block committed.

Could a log block → home block wait close a cycle? Only if someone held the home block and waited for a log block, and only the commit path touches log blocks. Moreover, commit runs only when log.outstanding is 0, with committing set so every new begin_op waits. No file-system operation is inside a transaction during it. A reader in fileread (which uses no transaction) might hold the home block for a moment, but it never waits for anything the commit holds.

The recorder confirms the context: none of its three-sleep-lock snapshots involves write_log or install_trans, so the committing process held no inode, and log.lock had been released at kernel/log.c:172.

Step 20 of 22

begin_op behaves like the outermost lock

begin_op is not a lock, but it can make a process wait, until a commit, so it belongs in the order. The rule: call it before any inode lock, and call end_op only after releasing them. If begin_op waited while holding an inode that an operation already inside the transaction needs, that operation could never reach its end_op, and the commit it waits for would never come (Tour 18: Lock ordering: how xv6 avoids deadlock has the timeline).

Is that rule written down? Not as such. The comments say that every file-system call must be bracketed by begin_op/end_op (kernel/log.c:18) and that iput and namex must run inside a transaction (kernel/fs.c:347, kernel/fs.c:690). The ordering lives in the code: in every caller (sys_open, sys_unlink, sys_link, sys_mkdir, sys_mknod, sys_chdir, kexec, filewrite, fileclose, kexit, ireclaim), begin_op comes first.

The recorder checked it at run time. Line 131 ran 13,251 times in the second run, and the number of times the process held any lock then, spinlock or sleep-lock, was 0. The same for end_op’s line 159. begin_op had to wait 1,136 times (lines 134–143), each time holding nothing.

Step 21 of 22

What the run never did

A measurement shows edges that happened, not edges that can happen. We compared every acquire, acquiresleep, wakeup, sleep_prepare and killed call site against the second run’s call chains. Paths the workload never reached:

• Copies into lazily allocated pages under a lock. copyout, copyin and copyinstr call vmfault, whose kalloc (line 469) takes kmem.lock. Under pi->lock (piperead, pipewrite), cons.lock (consoleread) and wait_lock + child’s p->lock (kwait's copyout), that gives pi->lock → kmem.lock, cons.lock → kmem.lock, and a second route to noff 3.
• printk under an inode: ialloc's “no inodes” and balloc's “out of blocks” run with the directory or file locked: inode → pr.lock.
• Four sleep-locks (previous steps), sys_sync going to sleep, sys_uptime, ireclaim finding an orphan at boot, and the failure paths of allocproc, kfork and create.

Our test program then drove the first group, all on-disk inodes in use, and the deep directory. Each one appeared: pi->lock → kmem.lock from both piperead and pipewrite, cons.lock → kmem.lock, inode → pr.lock from ialloc, and noff 3 through kwait’s copyout. All of them point into leaves, so none can close a cycle.

Step 22 of 22

What keeps the graph true

None of xv6’s lock checks looks at order. acquire, release and pop_off catch misuse by one hart; iunlock, brelse and bwrite check holdingsleep; and these lines in sched insist that a process switch away holding exactly one spinlock, its own p->lock. That last check is what pins p->lock at the bottom of every condition lock: a sleeper must release pi->lock before sleep, so the condition lock is always the outer one.

What the measurement adds to Tour 18: Lock ordering: how xv6 avoids deadlock:

• The graph has 15 spinlock → spinlock edges (counting every lk->lk as one class), all pointing down the ranks of step 15, except itable.lock → lk->lk, which closes the one cycle among spinlock classes; the ref == 1 argument rules it out between instances, as it does the sleep-lock cycle inode → itable.lock → inode.
• p->lock is almost a leaf: four leaves under it, only for a slot being born or a zombie being freed.
• The deepest nesting is noff 3, on three paths, the commonest 227,333 times (pages freed while reaping about 6,700 children); the most sleep-locks held at once was 3, and 4 is reachable.
• Besides every inode + buffer pair, six places hold two sleep-locks of the same kind: create, unlink, bmap, itrunc, write_log, install_trans, and iput holds a spinlock over one.

The cost of the discipline is small: a release and re-acquire in kfork, one in bget, one in create, one in sys_link, a refusal in sys_unlink. In exchange, three harts took nearly 29 million locks without one deadlock.