Step 1 of 17

The shell asks for a new file

The shell forks first; the child (pid 3) parses the line. The parser turns > newfile into a redirection with mode O_WRONLY | O_CREATE | O_TRUNC: write only, create the file if it is missing, empty it if it exists. Then runcmd closes descriptor 1 and calls open("newfile", mode) (user/sh.c:86).

Note >> on line 397: O_WRONLY | O_CREATE, no O_TRUNC. xv6 has no O_APPEND, so >> does not append; it overwrites from the start of the file (Tour 36: Reading and writing a file).

Everything from here on is pid 3 in the kernel. The path is relative (newfile, no /), so the walk will start from the shell’s current directory, /.

Step 2 of 17

One transaction for the whole open

sys_open fetches the mode and copies the path into the kernel with argstr. Then begin_op: everything create writes, and the O_TRUNC, will be one transaction (Tour 31: The log: begin_op, commit and group commit). If the power fails, newfile will exist completely or not at all (Tour 32: Crash recovery).

With O_CREATE, it calls create(path, T_FILE, 0, 0). The same function makes directories for sys_mkdir and device files for sys_mknod; major and minor matter only for devices.

From here to the end of create, the shell runs on its kernel stack (The stacks of xv6), which was empty at the ecall until uservec pointed sp at its top (kernel/trampoline.S:76). The path argstr copied lives there, in sys_open’s local path[128], and create will add a frame with its own name[14] for the last element.

Step 3 of 17

Find the parent, lock it, check it still exists

nameiparent walks the path but stops before the last element (Tour 34: Path lookup). For newfile it returns the current directory, / (inode 1), referenced and unlocked, and copies "newfile" into name.

Line 267 locks the parent, and create keeps that lock until the very end (line 315). Every decision from here on (does the name exist? where does the entry go?) is made and acted on under one lock.

Then two checks:

• dp->nlink == 0: the directory was deleted between nameiparent and this lock (it was unlocked in between). Creating a file there would put it in a directory no path reaches. Added in commit 9da28f5.
• For a new directory, dp->nlink >= NLINK_MAX: its .. would overflow the parent’s 16-bit link count (commit fa4789f).

Step 4 of 17

Is the name already taken?

dirlookup scans the root for newfile, all 64 slots of its 1024-byte block (the root was made one block long by mkfs). Not found.

Had it been found, as with echo hi > README, create would unlock the parent and lock the existing inode instead. For T_FILE requests, an existing file or device is fine: open simply opens it (and O_TRUNC will empty it). Anything else, such as mkdir of an existing name or open(O_CREATE) on a directory, fails.

Notice the order there: iunlockput the parent, then ilock the child. Here this is required, not a nicety. create never refuses the names . and .. (only sys_unlink does): for open(".", O_CREATE), dirlookup returns the parent itself, and locking it while still holding it would deadlock the process against itself; for x/.. it would lock x’s parent while holding x, the reverse of the parent-first order. Unlocking first makes both cases safe; they simply fail, because the existing inode is a directory.

Step 5 of 17

ialloc scans for a free inode

ialloc looks at every inode in order, from 1 up, reading each one’s block with bread: inodes 1–15 in block 33, then 16 onwards in block 34. A dinode with type == 0 is free. On a fresh boot inodes 1–23 are used (the root, README, 20 programs, and console), so the 24th one checked, inode 24 at byte 512 of block 34, is the first free one.

It claims it in the buffer: zero all 64 bytes, set type = T_FILE, log_write. The on-disk type field is the allocation bit; there is no separate inode bitmap. Then brelse and iget(1, 24): a referenced, unlocked, not-yet-valid entry.

That is 24 bread/brelse pairs to find one inode. They hit the buffer cache (block 34 was read at boot for console), so it costs time, not disk reads.

Step 6 of 17

Initialize the new inode, parent still locked

ilock on inode 24 reads block 34 again (from the cache) and copies the freshly zeroed dinode with its new type. Then create sets major, minor and nlink = 1, and iupdate logs block 34 a second time (absorbed: still one log entry).

nlink = 1 is set before the directory entry exists. For a moment, in memory, the inode claims a link it does not have. That is harmless: it is all one transaction, so the disk never sees the inode without its entry, and the failure path (step 8) corrects the count if the entry cannot be written.

Now pid 3 holds two inode locks: the parent and the child. Every path in xv6 that holds two inode locks takes a directory first and then something named inside it (sys_unlink does the same), never the reverse; paths that might break this give up the first lock: namex holds one at a time, and create unlocks the parent before locking an existing entry (step 4). So no cycle of waiting can form (Locks and interrupt state).

Step 7 of 17

dirlink writes the name into the parent

dirlink first checks once more that the name is absent (redundant for create, which just checked under the same lock, but sys_link relies on it). Then it looks for an empty slot, an entry with inum == 0. Entry 24, at offset 384, is the first.

It fills a dirent with inum = 24 and the name (strncpy pads with zeros up to 14 bytes, and leaves a 14-character name unterminated), and writeis the 16 bytes. writei logs block 47, and then iupdates the root inode, logging block 33.

While writei has block 47 locked, pid 3 holds three sleep-locks (two inodes and a buffer), the most any process held at once in an instrumented run of the whole test suite (Locks and interrupt state). Yet the irq strip reads noff 0 and interrupts are on: sleep-locks are not push_off levels, and lk->lk inside each is held only within acquiresleep and releasesleep (Locks and interrupt state).

If no slot were free, the loop would end with off == dp->size, and writei at that offset would grow the directory by one entry, allocating a new block through bmap if needed. That is the step that can fail: out of disk space.

Step 8 of 17

When dirlink fails, iput cleans up

dirlink succeeded for newfile, so create skips to line 315: iunlockput the parent, and return the new inode locked to sys_open.

The fail: path is worth reading anyway. The inode is already allocated on disk (in the log). To undo it, create sets nlink = 0 and calls iunlockput. This is the last reference to an inode with no links, so iput truncates it and frees it (Tour 33: The life of an inode). There is no separate “deallocate” code: an unnamed, unreferenced inode is garbage, and iput is the garbage collector.

Because all of this is in the open transaction, the allocation and its undoing commit together: the disk never sees inode 24 allocated.

Step 9 of 17

A slot in the file table

Back in sys_open (kernel/sysfile.c:368), the inode needs an open file (struct file). filealloc scans the NFILE = 100 struct files for one with ref == 0 and sets ref = 1, all under ftable.lock, a spinlock (so interrupts are off on hart 1 for the scan).

The pattern is the same as iget's: the scan for a free entry and the claim (ref = 1) must happen under one lock, or two harts could claim the same struct file.

Step 10 of 17

fdalloc, and the file is open

fdalloc gives the lowest free descriptor in this process’s ofile[] table. The shell closed 1 just before, so it is 1: this is how redirection works in Unix. No lock: only pid 3 uses its own table (Tour 5: Life of a system call).

The file is FD_INODE, offset 0, not readable, writable. O_TRUNC calls itrunc on an inode with no blocks: it changes nothing but logs block 34 once more (absorbed). Then iunlock and end_op, which commits. Our trace of exactly this command:

[commit pid 3 n=3: 34 47 33]

The new inode, the directory entry, the directory’s inode. Three blocks, eight disk writes (Tour 32: Crash recovery), and newfile exists. Then the child execs echo, which inherits descriptor 1.

Step 11 of 17

link gives an inode a second name

Now ln newfile alias. sys_link does not copy anything: it adds a second directory entry for inode 24.

It looks up newfile with namei and locks it. Directories cannot be linked (line 139): a second name for a directory would let the tree have cycles and give a directory two parents but only one ... The count is capped at NLINK_MAX (commit fa4789f; nlink is a 16-bit short). Then nlink++ (1 → 2), iupdate, and unlock before going on.

Again the count goes up before the name exists. If the second half fails, the bad: path at line 176 locks the inode again and takes it back down. Inside one transaction, nobody on disk ever sees the difference.

Step 12 of 17

link, second half: lock the new parent, not both

nameiparent finds alias’s directory, /, and it is locked. Inode 24 is not locked now. Why give it up? / is newfile’s parent. Holding inode 24 while locking / would be child-then-parent, and a concurrent rm newfile (sys_unlink) locks / and then inode 24:

Holding one inode lock at a time avoids the question.

Two checks guard the write:

• dp->nlink == 0: the target directory was deleted meanwhile. Linking into it would leak inode 24 with a link count one too high forever. Commit a12cd83 (August 2026) added this, copying the guard create already had.
• dp->dev != ip->dev: a link cannot cross devices, since an inode number means something only on its own disk. (xv6 has one disk, so this never fires.)

dirlink writes {24, "alias"} at offset 400. Our trace of ln on another file in / committed n=3: 34 47 33: the inode’s new nlink, the entry, the root inode.

Step 13 of 17

unlink refuses . and .. before it locks anything else

rm alias. sys_unlink gets the parent with nameiparent, locks it, and immediately rejects the names . and .. (rm . prints rm: . failed to delete).

Removing them would break the tree: a directory without ., or one whose .. no longer leads up. But look also at what would happen next with the locks. For ., dirlookup would return the parent itself, and ilock(ip) on line 226 would wait for a lock this process already holds: a self-deadlock. For .., ip would be the parent’s parent, locked while holding its child: the reverse of the parent-first order. The check on line 221 rules out both before any second lock is taken.

For alias, dirlookup returns inode 24 and its offset, 400, and line 226 locks it: parent first, then child.

Step 14 of 17

Remove the name, then maybe the file

A non-empty directory cannot be removed (isdirempty skips the first two entries, . and ..). For our file:

1. Zero the 16-byte entry at offset 400 with writei. The directory does not shrink; the hole is reused by the next dirlink.
2. Unlock the parent (iunlockput).
3. nlink-- (2 → 1), iupdate, iunlockput inode 24.

newfile still names inode 24, so iput only drops the reference. Our trace of the same rm committed n=3: 47 33 34. Had this been the last link (rm newfile next), the same iput, now holding the last reference to an inode with nlink == 0, would truncate and free it (Tour 33: The life of an inode).

If inode 24 were a directory, line 239 would also decrement the parent’s nlink, because the child’s .. entry, which counted as a link to the parent, is going away.

Step 15 of 17

mkdir: . and .., and who counts as a link

mkdir a runs the same create with T_DIR. After the inode is initialized (nlink = 1), lines 300–304 give the new directory its two entries:

• . → itself. Not counted in nlink (the comment: “avoid cyclic ref count”). If a directory’s own . counted, its nlink could never reach 0 by removing its name, and it could never be freed.
• .. → the parent. This is counted, in the parent: line 311 does dp->nlink++.

So a directory’s nlink is 1 (its name) plus one per subdirectory. On a fresh disk the root goes from nlink 1 to 2 with mkdir a, and a gets nlink 2 once a/b exists, as ls and the image confirm.

The parent’s count is raised only “now that success is guaranteed”, after the dirlink into the parent worked. The writes, from our trace of mkdir a on a fresh disk: commit pid 3 n=5: 34 46 1006 47 33: the new inode, the bitmap and block 1006 (the directory’s first block, for . and ..), the root’s entry, the root’s inode with nlink 2.

Step 16 of 17

Two harts, one name

We ran echo aaa > same &; echo bbbbb > same on a fresh disk: two processes on two harts, both calling create("same") at nearly the same time. Both reach nameiparent and get /. Then:

Both opens succeed, with one inode. ls showed a single same 2 24 6. Each process has its own struct file with its own offset, so their writes land on top of each other at offset 0: in this run cat same printed bbbbb; in another run with a different file name the result was bbb and b on two lines (Tour 36: Reading and writing a file).

Without the parent’s lock held from lookup to dirlink, both could see “not found” at t2, both call ialloc (getting 24 and 25), and both write an entry named same: a directory with a duplicate name, one of which dirlookup would never find. Or both could choose the same free slot, and one entry would overwrite the other, leaving an inode with nlink 1 and no name: leaked forever. The second check inside dirlink would not help, since it too would run before the other’s write.

Step 17 of 17

What it costs to name a file

Creating newfile took: a path walk, two scans of all 64 directory slots for the name (one in create, one repeated in dirlink) and up to 25 for a free slot, 24 inode checks in ialloc, three logged blocks and eight disk writes at commit. Linking and unlinking each touched the same three blocks.

The ideas:

• A file is created by two independent acts: allocating an inode (its type becomes non-zero) and naming it (a dirent). The log makes them one.
• The parent’s lock spans the whole check-then-act: lookup, allocate, link. That is what makes “create if absent” atomic, and what two harts racing on one name rely on.
• Parent before child, and never more than needed. create and unlink hold parent then child; link and namex hold one at a time.
• Counts can run ahead of reality inside a transaction (nlink raised before the entry exists), because nobody outside can see the difference, and the failure paths put them back.
• Freeing is done by iput, whenever the last name and the last reference are both gone, whether after rm, a failed create, or a crash (Tour 32: Crash recovery).