Step 1 of 23

Two locks, two harts, one cycle

Start with the mechanism every rule in this tour protects against. Hart 1 holds lock A and calls acquire(&B). push_off has turned interrupts off, and the amoswap loop on line 37 spins until B.locked is 0 (Tour 15: Spinlocks from the hardware up).

If hart 2 is holding B and spinning in this same loop for A, neither loop can ever finish:

Because spinlock waiters spin with interrupts off, even the timer cannot rescue them: no hart can be preempted, so no scheduler ever runs again. The whole machine is dead.

Lines 25–26 catch only the smallest cycle, a hart waiting for itself: holding notices that this hart already owns lk and panics with acquire. A cycle that involves two harts has no such check. It must be made impossible by design, and the design is a fixed order: if every path takes A before B, then nobody can hold B while waiting for A, and the cycle at t2 cannot form.

Step 2 of 23

Rule 1: wait_lock before any p->lock

The only place xv6 writes a lock order down is this comment: wait_lock “must be acquired before any p->lock”.

Why do these two locks ever nest? wait_lock protects the family tree: every p->parent field (kernel/proc.h:93). Each p->lock protects one process’s state, chan, killed, xstate and pid. Parents and children meet in two places that need both:

• kexit must reparent its children and wake its parent (family tree) and become a ZOMBIE (its own state).
• kwait must find its children (family tree) and check whether each is a ZOMBIE (the child’s state).

Both take wait_lock first and a p->lock second. The next three steps visit them, and kfork, the one place that is tempted to go the other way. The family-tree logic itself (why the parent’s wakeup cannot be lost) belongs to Tour 21: exit, wait and zombies; here we only care about the order.

Step 3 of 23

kfork lets go of the child before touching the family tree

The scene: you typed cat README | wc. The subshell (pid 3) has already forked cat (pid 4) and is now forking wc (pid 5) on hart 1.

allocproc returned the new struct proc with its p->lock held, so all of the copying above runs with np->lock held. Then look at line 294: release(&np->lock). Only after that does line 296 take wait_lock to set np->parent, and line 300 re-takes np->lock to mark the child RUNNABLE.

Releasing and re-acquiring looks wasteful. It is the price of Rule 1. Holding np->lock while acquiring wait_lock would be the forbidden order, p->lock then wait_lock. The others box shows the deadlock it would cause.

The copying itself nests a few locks under np->lock: uvmcopy calls kalloc (kmem.lock), filedup takes ftable.lock, idup takes itable.lock; earlier, allocproc took pid_lock (allocpid) and kmem.lock with the child’s lock held. pid_lock, kmem.lock and ftable.lock never lead back to a p->lock. itable.lock can, through iput's acquiresleep (kernel/fs.c:362), which closes the one class-level cycle p->lock → itable.lock → lk->lk → p->lock. It cannot deadlock, because iput does this only when ref == 1, so its acquiresleep never waits (step 16, Locks and interrupt state). A measured run confirms that these four are the only locks this kernel ever takes while holding a p->lock (Tour 51: The lock-order graph, measured, Locks and interrupt state).

Is it safe to let go of np->lock in between? Yes: np->state is still USED, so no scheduler will run it (scheduler only picks RUNNABLE), and no wait will reap it (it is not a ZOMBIE).

Step 4 of 23

kexit takes wait_lock, then wakes the parent

Now the other side of that timeline, as the code really runs. cat (pid 4) has closed its files and dropped its working directory. Line 347 takes wait_lock.

reparent hands any children of cat to init. It reads and writes pp->parent, which wait_lock protects, so it takes no p->lock at all, except inside wakeup(initproc) when it finds a child to hand over.

Line 353, wakeup(p->parent), wakes the subshell (pid 3) in case it is sleeping in wait. Inside wakeup, hart 2 takes each of the 64 p->locks one at a time, while still holding wait_lock. That is the wait_lock → p->lock order, 64 times over.

Notice that cat itself reads p->parent here. It may only do so holding wait_lock, because its parent could be exiting on another hart and reparenting cat to init at this very moment.

Step 5 of 23

kexit becomes a zombie holding both

Line 355 takes cat’s own p->lock while still holding wait_lock: Rule 1 again, in its plainest form. Then xstate and state = ZOMBIE are written under both locks.

Then the order of the releases gets interesting. Line 360 releases wait_lock, but p->lock stays held into sched and is released by the scheduler on the other side of swtch (Tour 13: swtch and the lock handed across a context switch). Releasing in a different order from acquiring is fine: deadlock comes from the order in which you wait, and releasing never waits.

Why hold wait_lock until the zombie is fully set up? Because the parent scans for zombies holding wait_lock (kwait, next step). With both locks held here, the parent sees cat either before it started exiting or as a finished zombie, never in between.

Step 6 of 23

kwait holds wait_lock, then each child's lock

The subshell (pid 3) is in wait(0) (user/sh.c:121), here running on hart 0. Line 376 took wait_lock; line 382 finds a child by reading pp->parent (allowed, under wait_lock), and line 384 takes that child’s p->lock to read its state. Same order: wait_lock, then a p->lock.

The p->lock is needed for the comment’s reason: “make sure the child isn’t still in exit() or swtch()”. A child that has set ZOMBIE still holds its p->lock until it has fully switched away; the parent must not free the slot (and so let a new process inherit the slot’s kernel stack) while the child is still running on that stack. Kernel stacks themselves are never freed: they belong to slots (The stacks of xv6).

If the zombie is found, the parent may call copyout to deliver the exit status while holding both locks (line 391). copyout may need a fresh page from vmfault → kalloc, which takes kmem.lock: so p->lock → kmem.lock is also part of the order. kmem.lock is a leaf: nobody holding it ever takes another lock. (sh passes 0 here, so this particular wait skips the copy.)

Line 398 nests one level deeper on every reap: freeproc frees the zombie’s pages with kfree, which takes kmem.lock while wait_lock and the child’s p->lock are still held. That is noff 3, the deepest spinlock nesting a measured run found (227,333 times) (Locks and interrupt state, Tour 51: The lock-order graph, measured).

Step 7 of 23

Rule 2: begin_op before any inode lock

The scene: echo hi > x is writing to a file x (in a fresh fs.img, the first file you create gets inode 24). filewrite opens a transaction with begin_op on line 160, and only then, on line 161, takes the inode’s sleep-lock with ilock.

begin_op is not a lock, but it can make a process wait, and anything that waits can be part of a deadlock cycle. It waits when the log might not have room for one more operation, until the current group of operations commits (Tour 31: The log: begin_op, commit and group commit). The commit happens only when the last outstanding operation calls end_op.

So xv6 orders it like a lock: begin_op first, inode locks after. Every file-system system call follows this: sys_open, sys_unlink, sys_link, kexec, filewrite, and kexit (for the iput of its working directory). The next step shows what goes wrong otherwise.

Step 8 of 23

Why begin_op cannot come second

Here is the wait inside begin_op. With LOGBLOCKS = 30 and MAXOPBLOCKS = 10, a new operation must sleep if log.lh.n + (log.outstanding + 1) * 10 > 30: the blocks already logged by this group, plus a worst-case reservation for every running operation and the new one.

Suppose filewrite were written the other way round, ilock first. The log already holds 15 blocks from earlier operations in this group, and rm x (pid 7) is one operation in progress:

The commit needs outstanding to reach 0, which needs rm to call end_op, which needs inode 24, which needs echo to get past begin_op, which needs the commit. With the real order, echo waits at t3 without holding inode 24, rm finishes, and the commit wakes echo.

Step 9 of 23

Rule 3: parent directory before child, in unlink

The scene: rm a/b, where b is an empty directory inside a. nameiparent returned a (unlocked) with name = "b". Line 218 locks a, line 224 looks up b in it, and line 226 locks b. Now rm holds two inode sleep-locks: parent first, then child.

That is the inode order for the whole file system: when a path holds two inode locks, it takes the one higher in the directory tree first. Holding both is necessary here: the entry in a and b’s link count must change together, and if b is a directory it must still be empty (isdirempty) at the moment its entry disappears, which only b’s lock can guarantee.

Which inodes are “parent” and “child” is decided by the directory tree, which is a tree because xv6 forbids hard links to directories (sys_link refuses T_DIR, kernel/sysfile.c:139). On a tree, “ancestor first” is a consistent order. With directory hard links the tree could become a graph with cycles, and the rule would no longer be well defined.

Step 10 of 23

unlink refuses "." and ".."

Line 221 refuses to unlink a final path element named . or ... There are good file-system reasons (removing them would corrupt the directory structure), but both would also break the lock order.

rm a/b/.: dp is b and name is .. dirlookup would return b itself, and line 226 would call ilock on the lock this process already holds. A sleep-lock has no “do I already hold this?” check: acquiresleep would see locked == 1 and sleep, waiting for itself, forever.

rm a/b/..: dp is b, and .. names a, its parent. Line 226 would lock the parent while holding the child, the reverse of Rule 3:

The check on line 221 runs before any lookup, so neither case gets as far as a second lock.

Step 11 of 23

create, the new-file path, parent then child

create is the mirror image of unlink (Tour 35: Creating and naming files). For echo hi > x, the shell’s open("x", O_WRONLY|O_CREATE|O_TRUNC) (user/sh.c:395), made in the forked shell child before it runs echo, gets here. Line 267 locks the parent, the root directory. If x does not exist yet, ialloc picks a free inode (24 in a fresh image) and line 294 locks it: parent, then child, Rule 3 again.

Could another process have locked inode 24 first, in some other order? No: it was free a moment ago, and the only path to it is the directory entry that line 306 is about to write into the root, which this process is holding locked. A brand-new inode cannot be part of anyone else’s cycle.

For a new directory, line 302 writes .. into the child pointing at the parent. It does this with dirlink on the locked child, using dp->inum, a number. It does not lock dp again, so no child-to-parent acquisition happens even though the data points upward.

Step 12 of 23

create, the existing-name path, lets go of the parent first

Run echo hi > x a second time. Now dirlookup on line 280 finds x. Look at the order on lines 281–282: iunlockput(dp) releases the parent first, then ilock(ip) locks x. Unlike unlink, create never holds parent and child together on this path. The display shows the state from line 282 on: only inode 24 is held.

Holding both would follow Rule 3 only if ip were really a child of dp. The code has no comment explaining the release, but it is necessary: name comes from the user and can be anything, including .. open("a/.", O_CREATE) gives dp = a, name = ".", and dirlookup returns a itself. Locking ip while holding dp would then be a process waiting for its own sleep-lock, the self-deadlock of the previous step. Releasing first makes . harmless: the call locks a again, sees it is a directory, and fails the test on line 283. (.. is harmless for the same reason: nothing is held when the parent’s parent is locked.)

Nothing needs the parent anymore on this path. The entry exists; create only returns the file.

Step 13 of 23

Rule 4: namex holds one inode lock at a time

Path lookup (Tour 34: Path lookup) walks down a path one directory at a time. For a/b/c, namex locks a (line 702), looks up b in it (line 716), then on line 720 unlocks a before the next loop iteration locks b on line 702. It never holds two inode locks.

dirlookup returns the next inode referenced but not locked: iget gives a reference that keeps the in-memory inode from being recycled, and the lock is taken later, separately. The comment at kernel/fs.c:158 says why iget and ilock are separate: it “helps avoid deadlock and races during pathname lookup”.

Lookups going down would actually be fine under Rule 3. The problem is that paths do not only go down. . returns the same directory and .. returns the parent, so a “hold the current one, lock the next” walk would self-deadlock on . and lock child before parent on ... The others box shows the second.

Step 14 of 23

A sleep-lock cannot catch you waiting for yourself

Several of the rules so far exist partly to avoid a process locking the same inode twice. Here is why that would be so bad. acquiresleep is a spinlock lk->lk around a locked flag. If the flag is set, it registers, releases the spinlock and sleeps (lines 26–28), and tries again when woken.

Compare acquire in the first step: it checks holding and panics. Here there is no such check. lk->pid records the holder, and holdingsleep can compare it with the caller, but acquiresleep never does. A process that calls ilock on an inode it already holds goes to sleep waiting for a wakeup that only it could send. No panic, no message: one process hangs forever, and every process that later needs that inode hangs with it.

That is why the code you saw handles . explicitly: sys_unlink refuses it, create and namex release before locking. The rule “never lock an inode you might already hold” has no runtime safety net.

Step 15 of 23

Rule 5: an inode lock may be held while taking itable.lock

dirlookup runs with the directory dp locked. When it finds the name, line 610 calls iget, which takes itable.lock, the spinlock that protects the table of in-memory inodes (which slot holds which inode, and ip->ref). So the order includes inode sleep-lock, then itable.lock.

This is the general shape of xv6: sleep-locks outside, spinlocks inside. A sleep-lock may be held for a long time, across disk I/O and sleeps. A spinlock is held for a few lines with interrupts off, and its holder must never sleep. So a sleep-lock can be taken first and a spinlock second, but a path that holds a spinlock must not go and wait for a sleep-lock: it could not sleep while holding the spinlock, and spinning for a sleep-lock that is held across a disk read would freeze its hart.

itable.lock is held only inside iget, idup and iput, each a few lines long. The next step looks at the one place where the shape is bent.

Step 16 of 23

iput bends the rule, carefully

rm x has removed the last link to x (line 244 of sys_unlink made nlink 0) and now drops its reference with iput. This is the last reference to an unlinked inode, so the file’s data must be freed. That needs the inode’s sleep-lock.

Line 362 calls acquiresleep while holding itable.lock, a spinlock: exactly what the previous step said must not happen. It is safe only because of line 357’s condition. ip->ref == 1 means rm holds the only reference in the system, and to lock an inode you must hold a reference. rm itself unlocked it just before (iunlockput). So nobody holds the sleep-lock, and while itable.lock is held, nobody can get a new reference (iget needs itable.lock). The acquiresleep finds locked == 0 and returns without ever sleeping.

Only then, on line 363, is itable.lock released, and the slow part, itrunc with its disk I/O, runs under the sleep-lock alone.

Count the levels at line 362: itable.lock, then lk->lk inside acquiresleep, then the push_off in its myproc() on line 32: noff 3 for a moment, one of the deepest chains a measured run found (Locks and interrupt state). If acquiresleep ever did sleep here, sched would see noff 2 (itable.lock plus p->lock) and panic with sched locks (Locks and interrupt state).

Step 17 of 23

Rule 6: never hold bcache.lock while waiting for a buffer

cat README opens its file: sys_open locks inode 2 (README) for the first time, and ilock reads its on-disk copy from block 33, the first inode block in this build’s fs.img. bread calls bget.

bget holds bcache.lock, a spinlock, while it searches the cache list. When it finds block 33, line 67 bumps refcnt (so the buffer cannot be recycled), line 68 releases bcache.lock, and only then line 69 waits for the buffer’s sleep-lock. The display shows the state after line 69 returns.

Swapping lines 68 and 69 would break two rules at once. If another process holds block 33’s sleep-lock (perhaps while the disk reads it), acquiresleep would have to sleep holding a spinlock, which sched forbids (it panics with sched locks). And even before that panic, every other hart needing any buffer would be spinning on bcache.lock with interrupts off.

Step 18 of 23

brelse lets go in the same spirit

The other end of a buffer’s life. brelse first releases the buffer’s sleep-lock (line 122), and only then takes bcache.lock (line 124) to drop refcnt and move the buffer to the front of the LRU list.

Here the order would actually be legal the other way round: taking a spinlock while holding a sleep-lock is the normal direction. The point is different: nobody ever waits for a buffer’s sleep-lock while holding bcache.lock. bget drops the spinlock before acquiring the buffer; brelse drops the buffer before taking the spinlock. The opposite nesting does happen, briefly: bpin and bunpin take bcache.lock while the caller still holds the buffer’s sleep-lock. That is the normal direction (sleep-lock outside, spinlock inside), and bcache.lock is a leaf.

The display shows cat still holding README’s inode lock: brelse was called from ilock after copying the on-disk inode out of block 33. Inode lock, then bcache.lock: the familiar “sleep-lock outside, spinlock inside”.

Step 19 of 23

Rule 7: sys_link lets go of the file before finding the new directory

ln a/f b/g adds a second name for file f. sys_link locks f (line 138), bumps its link count and writes it (lines 151–152), and then, on line 153, unlocks f. Only after that does it resolve b/g with nameiparent and lock the directory b (line 157). The display shows the state at line 157: only b is held.

It looks risky: between 153 and 157, f’s link count is already one higher than the number of names. But this is all one transaction: either everything commits or nothing does, and the bad: path undoes the increment if b cannot be used.

Why not keep f locked? Every other path that holds two inode locks takes a directory first and then something named inside it; locking the file f and then the directory b reverses that. And if f also has a name in b, they are literally child and parent, as the others box shows.

Step 20 of 23

Rule 8: a pipe's lock before any p->lock

Back to cat README | wc. cat has copied 512 bytes into the pipe and, on line 105, calls wakeup(&pi->nread) while still holding pi->lock. wakeup takes each process’s p->lock in turn. So: pi->lock, then p->lock.

pipewrite nests the same way in three more places: killed on line 84 takes the writer’s own p->lock, wakeup(&pi->nread) on line 89 (pipe full) takes every p->lock, and sleep_prepare on line 90 takes the writer’s own again. piperead mirrors them. The reverse, holding a p->lock and taking pi->lock, never happens.

This is what lets the waker hold the condition lock while it wakes (Tour 16: sleep and wakeup, and the lost-wakeup problem): the sleeper registered under pi->lock, so a writer holding pi->lock sees a consistent picture, and the p->locks it takes underneath are always inner.

The same pattern repeats across the kernel: tickslock → p->lock in clockintr and sys_pause, cons.lock → p->lock in consoleintr and consoleread, log.lock → p->lock in begin_op and end_op, the disk’s vdisk_lock → p->lock in virtio_disk_rw. Every condition lock sits outside p->lock.

Step 21 of 23

sched enforces "only p->lock"

Why does p->lock have to be the innermost lock, below every condition lock? Look at what sched demands. A process that gives up the CPU must hold exactly one spinlock: its own p->lock (line 485 checks it is held, line 487 checks that noff, this hart’s push_off depth, which here counts the spinlocks it holds, is exactly 1; Locks and interrupt state).

wc got here from piperead through sleep. Before calling sleep(), piperead released pi->lock (kernel/pipe.c:125); sleep() then took only wc’s p->lock. A process cannot switch away holding pi->lock, because other harts would spin on it, interrupts off, until wc happened to run again.

What wc leaves behind when it switches away is its kernel stack, frozen in place: usertrap → syscall → sys_read → fileread → piperead → sleep → sched, 336 bytes at the top of its page, with swtch saving the stack pointer into p->context before moving hart 2 to its scheduler stack (kernel/swtch.S:26). Nothing on that stack records which locks are held. Sleep-locks live in their structs, but a spinlock’s “held” is a property of the hart: lk->cpu and this hart’s noff. Any other spinlock carried across the switch would still name hart 2 as its holder while wc slept, and if wc woke on another hart, its release would fail the holding check and panic. (p->lock is the one exception: the scheduler on the same hart releases it, Tour 13: swtch and the lock handed across a context switch.)

This check enforces the half of Rule 8 that sleepers depend on: no process may switch away holding a condition lock. Any path that tried would panic with sched locks. And because a sleeping process holds p->lock across swtch (released by the scheduler, as in Tour 13: swtch and the lock handed across a context switch), anything taken after p->lock would be held across the switch too. Only lock types that a process being built or freed needs are taken under a p->lock (pid_lock, kmem.lock, ftable.lock, itable.lock, in kfork/allocproc, and kmem.lock in freeproc), and none of them is held across a switch. The one that can lead back, itable.lock, does so only inside iput with ref == 1, where it never waits.

Step 22 of 23

Leaves at the bottom of the order

Some locks never have anything below them. rm x decrements the link count and iupdate writes the inode into block 34 (inode 24 lives there: 24 / 16 + 33). log_write is called with the inode’s and the buffer’s sleep-locks held and takes log.lock. Inside, bpin takes bcache.lock. So the chain here is four deep:

inode sleep-lock → buffer sleep-lock → log.lock → bcache.lock

bcache.lock is a leaf: no code holding it takes another lock. So is kmem.lock (kalloc, kfree) and pid_lock (allocpid). A leaf lock can never be part of a cycle, because a cycle needs every member to be waiting while holding.

The disk follows the same shape. With a buffer’s sleep-lock held, virtio_disk_rw takes vdisk_lock; while waiting it calls sleep_prepare (p->lock) and drops vdisk_lock before sleep. Its interrupt handler, virtio_disk_intr, holds vdisk_lock and calls wakeup (p->lock). Consistent again: vdisk_lock → p->lock.

Step 23 of 23

The whole order on one page

Collecting the rules. Read each row as “may be held while taking anything in a lower row, never the reverse”:

(Simplified: the log’s write_log and install_trans hold a log block, then a home block; bmap and itrunc hold an indirect block while balloc/bfree lock a bitmap block. The UART’s tx_lock sleep-lock is taken with nothing held, and only lk->lk and p->lock nest under it. pr.lock is reached from cons.lock when Ctrl-P runs procdump → printk.)

Taken as lock types, p->lock → itable.lock (kfork’s idup) → lk->lk (iput) → p->lock is a loop. It cannot deadlock because iput only does this when it holds the only reference.

Other consistent nestings you met along the way: p->lock → pid_lock/kmem.lock (allocproc, freeproc); p->lock → ftable.lock/itable.lock (the child’s lock in kfork, over filedup and idup); wait_lock/pi->lock/cons.lock → kmem.lock (copyout/copyin → vmfault → kalloc); inode lock → ftable.lock (sys_open's filealloc); buffer sleep-lock → vdisk_lock (bread/bwrite).

Three habits keep the table true: release before you acquire when the order would be wrong (kfork, bget, sys_link, create); refuse inputs that would force a bad order (. and .. in unlink); and never wait while holding a spinlock, which sched checks. Only one comment states an order explicitly (kernel/proc.c:26); others state lock rules (kernel/proc.c:472, kernel/fs.c:161, kernel/log.c:175, kernel/sysfile.c:220). The rest is in the code you just walked through.