Step 1 of 16

cat asks for README by name

cat calls open("README", O_RDONLY). It names the file, but the kernel works with inode numbers. Turning one into the other is Tour 34: Path lookup's subject. This tour picks up the inode as soon as the name has been found, and follows it until close(fd) on line 40.

Keep in mind what an inode is: the file itself, without its name. Its type, size, link count and the list of its data blocks, 64 bytes on disk (dinode (on-disk inode)), sixteen to a block. Inode 2 sits in block 33 (the first inode block), next to the root directory’s inode 1.

Step 2 of 16

dirlookup finds the entry and asks iget for the inode

sys_open called namei, which locked the root directory (inode 1) and called dirlookup to search it for README. The third entry, at byte offset 32 of block 47, is {2, "README"}.

dirlookup does not return the entry. It returns an inode pointer, obtained from iget(1, 2): device 1, inode 2. Every new reference to an inode starts in iget (only idup adds to a reference someone already holds), so there is exactly one place where in-memory inodes are handed out.

Note what cat holds right now: the root directory’s sleep-lock. Looking up a name means reading the directory, and nobody may change the directory while it is being read.

All of this runs on cat’s kernel stack, the one page of kernel memory that belongs to its process slot (The stacks of xv6). It was empty when cat executed ecall: uservec saved cat’s user sp in the trapframe and loaded the kernel stack’s top (kernel/trampoline.S:76). Every call since has pushed a frame, and two of them hold the strings this lookup works with:

cat's kernel stack (one 4 KiB page)
  top ─► usertrap
         syscall
         sys_open    path[128]: "README", copied in by argstr
         namei       name[14]:  scratch for one path element
         namex
         dirlookup   ◄─ sp

cat’s user stack, where main waits for open to return, is not touched until the system call ends.

Step 3 of 16

iget gives inode 2 a slot, under itable.lock

The inode table (itable) is an array of NINODE = 50 struct inodes shared by the whole kernel. iget takes itable.lock and scans it:

• An entry with ref > 0 and the same device and number? Then inode 2 is already in memory: ref++ and return it.
• Otherwise remember the first entry with ref == 0.

Nobody is using inode 2, so it takes the first free entry. In our trace that was slot 2 (slot 0 holds the root directory, kept alive by every process’s current directory; slot 1 holds console, kept alive by the open console files). It writes dev = 1, inum = 2, ref = 1, valid = 0, and releases the lock.

iget does not read the disk. It runs under a spinlock, and reading the disk means sleeping. So the entry it returns is a reservation: the right number, a reference, and no contents yet.

Step 4 of 16

Two harts, one inode number

Why must the scan and the claim happen under one lock? Suppose wc README on hart 0 calls iget(1, 2) at the same moment as cat. Without itable.lock:

If both pick slot 2, its ref is 1 although two processes use it, and the first iput frees the slot under the other’s feet. If they pick different slots, there are two copies of inode 2 in memory, each with its own sleep-lock. Locking one does not exclude the other, and each iupdate would overwrite the other’s changes on disk.

With the lock, the scans are serialized:

One inode, one entry, one lock, and a ref that counts both users. That is the invariant iget exists to keep.

Step 5 of 16

Back in namex, the directory is let go

namex now holds two references: one to the root (its ip) and one to README (next), but it has locked only the root. It calls iunlockput on the root (unlock, then iput, which drops the root’s ref by one: the processes’ current directories keep it far above zero) and returns README’s inode, unlocked.

This is the first sign of a design choice that runs through xv6: getting a reference (iget) and locking (ilock) are separate. A reference says “this entry must stay inode 2”. A lock says “I am looking at or changing inode 2’s contents now”. You can hold a reference for a long time, a lock only briefly. Tour 34: Path lookup shows why the lookup needs that separation to avoid deadlock.

Step 6 of 16

ilock locks the inode, and reads it the first time

sys_open calls ilock (kernel/sysfile.c:354). It takes the inode’s sleep lock with acquiresleep; if another process held it, cat would sleep here instead of spinning.

Now valid is 0, so ilock fills the entry in: bread block 33 (IBLOCK(2, sb) = 2/16 + 33), find the 64-byte dinode at index 2, and copy it: type = 2 (file), nlink = 1, size = 2441, addrs = {48, 49, 50, 0, …}. Then valid = 1.

This is the right place for the disk read, for two reasons. The caller holds a sleep-lock, so sleeping on the disk is allowed. And the lock makes sure only one process loads the entry; a second process locking it afterwards sees valid == 1 and skips the read.

If the disk says type == 0, the inode is free, and someone is using a dangling inode number. That is a kernel bug, and ilock panics (line 317).

If block 33 is not in the cache, bread sleeps in virtio_disk_rw until the disk interrupt. Then cat’s frames, usertrap down to ilock, bread, virtio_disk_rw, sleep and sched, simply stay where they are on cat’s kernel stack, and swtch moves hart 1’s sp to hart 1’s scheduler stack (kernel/swtch.S:26). When the disk wakes cat, whichever hart’s scheduler runs it switches back onto this same kernel stack, and ilock continues as if nothing happened.

Step 7 of 16

The open file keeps the reference, not the lock

sys_open allocates a open file (struct file) (filealloc) and a descriptor (fdalloc: descriptor 3, the lowest free one), and stores the inode pointer in f->ip. The reference that iget created now belongs to the file: it is not taken again, and it will be given back by the iput in fileclose.

Then iunlock on line 391. cat keeps the reference for as long as the file is open, but holds the lock only inside each system call. If open kept the lock, every other process touching README (another cat, ls, rm) would wait until cat closed it.

State of inode 2 now: ref = 1, valid = 1, unlocked, nlink = 1.

Step 8 of 16

Each read locks it again, briefly

cat reads 512 bytes at a time. Each read comes to fileread, which does ilock, readi, iunlock. valid is 1 now, so ilock reads no disk block for the inode; it only waits for the sleep-lock if someone else holds it.

Inside the lock, readi uses size and addrs[] to find the data (block 48 for offsets 0–1023) and copies it to cat’s buffer. The lock makes the read see a consistent inode: no size from before a write and addrs from after it. The details of reading are Tour 36: Reading and writing a file.

2441 bytes take five reads with data (4 × 512 + 393) and a sixth that returns 0.

Between open and this read, cat returned to user mode, and its kernel stack emptied: sys_open’s frames, path and name included, are gone, and this read starts again at the top of the page. Nothing the kernel needs from one system call to the next can live on a kernel stack. That is exactly why the reference is kept in the struct file (step 7), not in a local variable.

Step 9 of 16

Meanwhile rm takes away the last name

rm README on hart 2 is in sys_unlink. Its dirlookup called iget(1, 2) and found cat’s entry, so ref became 2. It locked the root directory, then inode 2 (it may have slept in ilock while cat was inside readi).

It clears the directory entry (16 zero bytes at offset 32 of block 47), unlocks the root, and then:

• nlink--: 1 → 0. No name refers to inode 2 any more.
• iupdate logs block 33 with nlink = 0.
• iunlockput: iput sees ref == 2, so this is not the last reference. It only decrements ref to 1.

rm’s transaction commits blocks 47 and 33 (our trace: commit pid 4 n=2: 47 33, pid 4 because that run had one extra command before it). On disk, inode 2 is now allocated, with zero links, its data still in blocks 48–50.

Step 10 of 16

cat keeps reading a file with no name

cat’s next read locks inode 2 and calls readi as if nothing had happened. And for cat, nothing has: the inode’s size and addrs are unchanged, and blocks 48–50 still hold the text. In our run, cat printed the rest of README, including its last section, after rm’s transaction had committed.

This is the Unix rule: deleting removes a name. The file lives as long as anything refers to it, which here is cat’s open file. ref (references in memory) and nlink (names on disk) are counted separately because they answer different questions:

Step 11 of 16

close drops the file, and the file drops the inode

cat reaches the end and calls close(3). sys_close clears ofile[3] and calls fileclose. Under ftable.lock the file’s own ref drops from 1 to 0, so this was the last descriptor using it; the entry is marked free and copied to ff.

Then, with no spinlock held, the file gives up its inode reference: begin_op, iput, end_op. Why a transaction just to drop a reference? Because iput may delete the file, and deleting writes the bitmap and the inode block. This iput will.

(Had rm not run, this iput would see nlink == 1, simply drop ref to 0, and the transaction would commit nothing. Slot 2 would become free while still holding inode 2’s data with valid == 1, but the next iget(1, 2) would not reuse it: iget matches only entries with ref > 0. Our trace confirms it: every new command that used directory a in our path experiments printed ilock read inum 24 again. The inode table holds inodes in use; it is not a cache of recently used ones.)

Step 12 of 16

iput sees the last reference to a nameless inode

iput takes itable.lock and decides: ref == 1 (only cat’s reference), valid == 1, nlink == 0. So last = 1. It also copies dev and inum into local variables; step 14 explains why.

Line 362 then takes the inode’s sleep-lock while holding a spinlock. Normally that is forbidden: acquiresleep may sleep, and xv6 panics (sched locks, kernel/proc.c:488) if a thread tries to sleep while holding any spinlock other than its own p->lock. On a kernel without that check it could deadlock. Here it cannot sleep. ref == 1 means cat holds the only reference, and no process can lock an inode without holding a reference. So the sleep-lock is free, and acquiresleep takes it at once.

Why take it at all, if nobody can contend? Because the rule for every inode field other than ref, dev and inum is “hold the sleep-lock” (kernel/fs.c:174), and itrunc and iupdate are written for callers that follow it (their comments say “Caller must hold ip->lock”; they do not check). iput follows the rule even where it could get away without it.

(The state box shows the moment after line 362 returns. Inside acquiresleep, cat also briefly holds inode 2’s inner spinlock lk->lk.) Count the levels in there: itable.lock, then lk->lk, then the push_off in myproc() on kernel/sleeplock.c:32: noff 3, one of only three paths on which an instrumented kernel ever reached that depth (Locks and interrupt state). Had acquiresleep found the lock taken, it would have released lk->lk and called sleep with itable.lock still held, and sched would have panicked with noff 2 (Locks and interrupt state).

Step 13 of 16

Truncate, with only the sleep-lock held

iput released itable.lock (line 363) before calling itrunc, because truncating reads and writes blocks, which sleeps.

itrunc walks addrs[]: blocks 48, 49 and 50 are freed in the bitmap with bfree (all three bits are in block 46) and the pointers are zeroed. README has no indirect block, so lines 477–487 do nothing. Then size = 0 and iupdate writes the emptied inode into block 33.

Back in iput, valid = 0 (the entry no longer describes anything) and the sleep-lock is released. Note that the on-disk type is still 2. The inode is truncated but not yet free: no ialloc can take inode 2 yet.

Step 14 of 16

Drop the reference, then free the number

iput re-takes itable.lock, decrements ref to 0 and releases it (lines 370–374). Slot 2 is free. Only then, on line 377, does ifree read block 33 and write type = 0 for inode 2, through the log. From this moment inode number 2 can be allocated again.

ifree uses the local dev and inum, not ip->dev and ip->inum. Once ref is 0 and the lock released, another hart’s iget may recycle slot 2 for a completely different inode and overwrite those fields.

cat’s transaction commits blocks 46 (the bitmap) and 33 (the inode). Our trace: commit pid 6 n=2: 46 33 (pid 6 rather than 5, for the reason given in step 9). Afterwards ls README prints ls: cannot open README, and the three blocks are free.

Step 15 of 16

The race this order prevents

Until xv6 commit d7e85f1 (August 2026), iput wrote type = 0 (via iupdate) before decrementing ref. From that moment, inode 2 looked free to anyone reading block 33. The inode’s sleep-lock, still held for a few more lines, did not help, because ialloc and iget never take it. Then iput released the sleep-lock and went to take itable.lock; for that last stretch it held no lock at all and interrupts were on, so a timer interrupt could stretch the window to a whole time slice (kerneltrap calls yield on a timer tick, kernel/trap.c:157). Here is what ialloc on another hart could do in it:

Result: inode 2 is allocated on disk with nlink == 0, and nobody holds it. It is an orphan on a running system, leaked until the next boot’s ireclaim (Tour 32: Crash recovery).

The fix is the order you just saw: the number becomes allocatable (ifree) only after ref is 0. Then at t3 iget cannot find a live entry for inode 2, takes a fresh slot with valid = 0, and reads the inode from disk.

Step 16 of 16

An inode's whole life, in four states

The source comment names four independent properties of an inode. In this tour you saw each one change:

Two locks divide the work. itable.lock, a spinlock, guards which inode an entry holds and how many users it has; it is held for microseconds and never across a disk access. The per-inode sleep-lock guards what the inode contains, and may be held while the disk works. The file system’s correctness, including the ordering fix in iput, rests on keeping those two jobs apart.

Cost of the whole life: one bread of block 33 for ilock (probably a buffer-cache hit, since the root inode lives there too), a lock and unlock per read, and two transactions for the deletion (one by rm, one by the last close).