Step 1 of 15

The tree on the disk

cat calls open("/a/b/c", O_RDONLY). Here is what the three commands before it left on the disk, read from the image and from a traced kernel:

A directory is a file whose content is an array of 16-byte entries (struct dirent): a 2-byte inode number and a 14-byte name. Nothing else. There is no “path” anywhere on the disk; a path is a recipe for a walk through these tables. c itself is inode 26, a 3-byte file holding hi\n in block 1008.

Step 2 of 15

open hands the string to namei

sys_open copied the path into a kernel buffer with argstr, started a transaction with begin_op, and, since there is no O_CREATE, called namei(path) (kernel/sysfile.c:350).

namei and nameiparent are two faces of one function, namex. namei wants the inode the whole path names. nameiparent wants the directory that would contain the last element, plus that element’s name. namei passes a 14-byte name buffer in its own frame on cat’s kernel stack, because namex needs scratch space for each element.

Why is lookup inside a transaction? Reading never writes the disk. But namex drops references with iput, and if one of those turned out to be the last reference to a deleted directory, iput would free it, which writes. So every caller that can make namex drop a reference runs it between begin_op and end_op (the comment at line 690). The one exception, userinit's namei("/") (kernel/proc.c:226), never enters the loop, so it never calls iput.

Every step that follows cat runs on cat’s kernel stack (The stacks of xv6), a single 4 KiB page that was empty when cat executed ecall (kernel/trampoline.S:76 loaded its top into sp). The path itself is there too: argstr copied "/a/b/c" into sys_open’s local path[128] (kernel/sysfile.c:331), so namex walks a kernel copy that cat cannot change halfway through. (The later steps that follow ls, sh and rm run on those processes’ own kernel stacks.)

Step 3 of 15

Where to start, root or cwd

The path begins with /, so the walk starts at the root: iget(ROOTDEV, ROOTINO), device 1, inode 1. A path without a leading / would start at the process’s current directory, myproc()->cwd, with idup taking an extra reference to it (step 13).

Either way ip now holds a reference, not a lock. The root’s in-memory entry never leaves the inode table while any process has / as its current directory, so in our trace it was read from disk once, at boot, and never again.

Step 4 of 15

skipelem cuts off one name at a time

skipelem skips slashes, copies the next element into name, skips the slashes after it, and returns the rest. For our path, the loop at kernel/fs.c:701 calls it four times:

Extra slashes vanish: "//a///b" gives the same walk. A returned empty string, as after call 3, tells the caller “that was the last element”, which is how nameiparent knows when to stop.

Names longer than DIRSIZ (14) are cut to 14 bytes, without a terminating zero (line 677). That works because names are compared with namecmp, a strncmp limited to 14 bytes. So "abcdefghijklmnop" and "abcdefghijklmnXY" name the same file.

Step 5 of 15

Lock the directory, and check that it is one

First element, a. namex locks the current inode, the root, with ilock. It must: it is about to read the directory’s size and content, and the inode’s sleep lock is what makes them stable.

Two checks:

• type != T_DIR: you cannot look up a name in a file. cat /README/x fails here, on the second iteration, with cannot open.
• nlink == 0: the directory has been deleted, though someone still holds a reference. Step 11 shows why this check exists.

(Lines 704 and 708, the failure exits, release the lock; the state box shows the path where both checks pass.)

Both failures use iunlockput: unlock, and drop the reference. Every exit from namex returns or releases exactly the references it took.

Step 6 of 15

dirlookup scans the root for "a"

dirlookup reads the directory 16 bytes at a time with readi, skipping empty slots (inum == 0) and comparing names. There is no index and no hashing: a linear scan. For a, the 25th entry (offset 384), that is 25 calls to readi, each one a bread and brelse of block 47 (all hits in the buffer cache) and a 16-byte copy.

On a match, it returns iget(1, 24): a referenced, unlocked, possibly not yet valid inode for a. It does not lock it. That is the subject of the next step.

Step 7 of 15

Let go of the parent before touching the child

next is a, referenced but unlocked. Line 720 unlocks and puts the root, and line 721 moves on: ip = a. At the top of the loop, a will be locked.

So between the two locks there is a moment when cat holds no inode lock, only a reference to a. Another process could change a in that moment (add or remove an entry, or, if a were empty, even unlink a from the root; step 11 shows the check that catches that). That is acceptable: the reference keeps a’s in-memory entry alive and meaning inode 24, and whatever a looks like when cat locks it is what the lookup sees.

What the order buys is that namex never holds two inode locks. The next step shows what would happen if it did.

Step 8 of 15

Why not hold both? Two ways to deadlock

Imagine a version of namex that locks next first and only then unlocks ip (“lock coupling”). Directories are a tree for /-paths, but .. points up, so two walks can go in opposite directions:

A classic deadlock: each holds what the other wants. It needs no other hart, either. Looking up . makes dirlookup return the same inode (. in a names inode 24), so ilock(next) while holding ip would wait for a lock this very process holds. (cat ./a/./b/c works in xv6 precisely because namex unlocks first. Each . makes dirlookup return the very same struct inode, with ref raised by iget. Line 720 unlocks it and drops one reference, which cannot free it because next still holds one, and line 721 sets ip = next, the same pointer, so the next ilock finds it unlocked. Under lock coupling, acquiresleep would find locked == 1 and sleep forever; it does not check who holds the lock, so the kernel would hang, not panic.)

Holding at most one lock at a time makes both impossible. Tour 18: Lock ordering: how xv6 avoids deadlock has the general rule; the kernel-wide lock-order graph, in which a second inode lock is only ever taken while a directory is held, on an inode named in it or one create has just allocated for it, is in Locks and interrupt state. The price is the gap in the previous step: a lookup is not one atomic snapshot of the tree, but a series of atomic steps.

Step 9 of 15

Down to a, then b: the inode read on the way

Second iteration, name b. ilock(a) finds valid == 0: inode 24’s entry is new, since no process kept a reference to it after echo hi > a/b/c (pid 5) exited. So ilock reads block 34 (inodes 16–31) and copies inode 24: a directory, nlink 2 (its entry in / and the .. in b), size 48, data in block 1006. Our trace printed ilock read inum 24 from block 34 pid 6.

dirlookup scans three entries (., .., b) of block 1006, finds b at offset 32, and returns iget(1, 25). Unlock a, put a, move on.

Third iteration, name c: the same for inode 25 (also in block 34), whose block 1007 holds ., .. and c. It returns iget(1, 26).

Step 10 of 15

The walk ends, and c comes back unlocked

After the third iteration, path is "", so the fourth skipelem returns 0 and the loop ends. ip is c (inode 26): referenced, unlocked, and never locked by namex. Line 727 returns it.

namex never locked c because it never needed c’s contents. Whether c is a file, a directory or a device is the caller’s business. sys_open locks it next (kernel/sysfile.c:354), checks its type, and keeps the reference in the open file (Tour 33: The life of an inode).

The whole lookup touched four inodes (1, 24, 25, 26) and took three inode locks, one at a time, scanning 25 + 3 + 3 directory entries.

Step 11 of 15

The deleted directory, and a panic fixed in this version

The nlink == 0 check was added in xv6 commit 9da28f5 (August 2026) after this sequence crashed the kernel. We ran it on a fresh disk, first with this check removed in a scratch copy:

$ mkdir /a
$ mkdir /a/b
$ cd /a/b
$ /rm /a/b
$ /rm /a
$ /ls ..
panic: ilock: no type

rm /a/b removed b’s entry and set b’s nlink to 0, but the shell’s cwd still referenced b, so b was not freed, and its .. entry still said inode 24. Then rm /a freed a completely (type = 0). ls .. started at b, found .. = 24, and ilock read a free inode: panic.

With the check, the walk stops at b, because a deleted directory is not a place any path can lead through. The same commands print ls: cannot open ... The commit message’s version uses ../../rm, which works only before the fix. It also notes two other symptoms of the same hole: create could create files in a disconnected directory, and an ialloc / lookup race could hand out the same inode number twice.

Step 12 of 15

nameiparent stops one step early

Go back to echo hi > a/b/c, which created c. create cannot use namei: c does not exist yet. It needs the directory a/b and the name "c", so it calls nameiparent.

The walk is the same until the last element. On the third iteration name is "c" and skipelem returned "". So nameiparent && *path == '\0' is true: line 713 unlocks b and returns it, referenced but unlocked, with "c" left in name. c is never looked up here; that is the caller’s job, under the caller’s own lock of b (Tour 35: Creating and naming files).

Lines 723–726 handle the path with no last element: nameiparent("/") walks zero times and fails, since / has no parent to return. Deleting or creating / is meaningless.

Step 13 of 15

Relative paths start from cwd

If the user types cd a and then /cat b/c (the leading / matters: the shell passes cat to exec unchanged, and exec would look for /a/cat), the walk for b/c starts at line 699: idup(myproc()->cwd). The shell runs cd itself, not in a child, because the current directory belongs to the process (user/sh.c:167).

sys_chdir looks up a with namei, locks it to check it is a directory, unlocks it, and swaps references: iput the old cwd (the root), keep the new one. The iput is inside the transaction for the usual reason: if the old directory had been deleted, this could be its last reference.

Afterwards, /cat b/c forked from the shell inherits cwd = a (kfork calls idup), so the walk for b/c is idup(a), look up b, then c: two iterations instead of three, and this walk never touches the root (only exec’s lookup of /cat does).

Step 14 of 15

Walking while someone else deletes

Suppose rm /a/b/c runs on hart 2 while cat /a/b/c walks on hart 1. sys_unlink uses nameiparent to get b, then locks b and, inside that, c: two locks, parent before child.

Which file cat gets depends on who locks b first:

or, the other way round, rm locks b first, clears the entry, and cat’s dirlookup finds nothing: cannot open. Both are correct outcomes. What can not happen is cat getting an inode that is being freed: the reference from iget is taken under b’s lock, before rm can clear the entry, and it keeps the inode alive (Tour 33: The life of an inode).

Step 15 of 15

What a lookup costs, and what it promises

For /a/b/c, namex did three iterations. Each took a lock, maybe read an inode, scanned a directory linearly with one readi per entry, took a reference to the next inode, and released the lock and the old reference. In all: 31 directory entries read, 3 inode locks, 4 references taken and 3 dropped, two inode loads (24 and 25) that hit the buffer cache.

The ideas worth keeping:

• A path is a sequence of dirlookups; the disk stores only names → numbers, one directory at a time.
• References and locks are separate: namex carries a reference from one step to the next, and holds a lock only while reading one directory.
• One inode lock at a time rules out deadlock with .. and .. The price is that a lookup is a series of atomic steps, not one atomic snapshot.
• A deleted directory may still be referenced (as someone’s cwd), so namex and create check nlink after locking, not before.

One more property, about the stack: namex is a loop, not a recursion. A path with fifty elements uses the same frames on cat’s kernel stack as a path with one, which matters on a stack that is a single page with an unmapped guard page below it.