Extension labs · lab 24 · File system · ★★★★☆

Atomic rename

xv6 has no way to rename a file. You can ln old new and then rm old, which is how early Unix mv worked, but that is two system calls and two transactions, and it cannot move a directory at all. In this lab you add rename(old, new): one system call that moves a name within a directory or between directories, replaces an existing file in the same step, and moves whole directories, all inside one transaction of the log.

Each piece of the job looks small: write one directory entry, clear another, fix a link count. The questions come from doing them together. A crash between two steps must not leave both names, or neither. Two directories must be locked at once, and the tree’s existing rule, parent before child, says nothing about two directories that are not related: what order do you pick, and what does your choice do to the code that already locks inodes? How do you notice that someone is moving a directory into its own subtree, when xv6 keeps no parent pointers in memory? And does all of it fit in the ten blocks a transaction may write?

The reference solution is six commits. It survived 30 random kills of QEMU in the middle of renaming, with the file system consistent every time, and it never deadlocked on three harts under a load that, with the race window widened, deadlocked both obvious alternatives.

Read first: Tour 17: Sleep-locks, Tour 18: Lock ordering: how xv6 avoids deadlock, Tour 31: The log: begin_op, commit and group commit, Tour 32: Crash recovery, Tour 33: The life of an inode, Tour 34: Path lookup, Tour 35: Creating and naming files, Tour 51: The lock-order graph, measured · Locks and interrupt state

What this lab teaches

Why one transaction is the unit of atomicity on disk, what it costs (the number of distinct blocks one rename can dirty), and how to check that against MAXOPBLOCKS by counting rather than guessing.
How to order locks that the existing order does not cover, and how to check a proposed order against every piece of code that already nests the same locks, including code you did not touch.
How to ask a question about the shape of the directory tree (is this directory above that one?) without breaking the lock order, and what has to stay frozen while you ask it.
Why work done without a lock must be checked again once the lock is held, and what the check has to compare.
What a directory carries besides its name: its .. entry and the link it adds to its parent, and what breaks, sometimes much later, when one of them is wrong.
How a sleep-lock deadlock looks on a live machine: processes asleep holding each other’s locks, idle harts, and a file system that soon stops for everyone.

The reference branch

ext/24-rename in ShowMeTheStack/xv6-riscv-labs, branched from the frozen commit 06aad25; 6 commits.

git clone https://github.com/ShowMeTheStack/xv6-riscv-labs
cd xv6-riscv-labs
git checkout -b my-rename 06aad25   # start your own
git diff 06aad25 origin/ext/24-rename   # only when you want the answer

1. The spec

The system call. int rename(const char *old, const char *new) gives the file or directory named old the name new and returns 0, or returns -1 and changes nothing.

old and new may be in the same directory or in different directories.
If new exists and is not a directory, it is replaced: its directory entry now names old’s inode and it loses one link, in the same transaction. If that was its last link and nobody has it open, it is freed.
If old and new are already names for the same inode (two hard links, or the same name twice), rename does nothing and returns 0, as POSIX says.
Moving a directory to another parent updates its .. entry and both parents’ link counts.
rename fails, changing nothing, if: old does not exist; either last path element is . or ..; new is an existing directory (simplification: POSIX allows replacing an empty one); old is a directory and new exists; the move would put a directory inside itself or below itself; the new parent has been removed, or a directory move would push its link count past NLINK_MAX; the new parent has no room and no free block; or a concurrent create, unlink or rename changed either name between the rename’s first look and the moment it holds the locks (it does not retry, even where POSIX would succeed).
“Changes nothing” has one exception inherited from base xv6: on a disk with exactly one free block left, bmap can allocate a directory’s indirect block and then fail on the data block; the empty indirect block stays allocated. The disk stays consistent.
The two names must be on the same device (xv6 has only one, so this never fails).

Atomicity. The whole rename is one transaction. After a crash and recovery, exactly one of the two outcomes is on disk: the state before the rename or the state after it.

What must not change. Every existing system call behaves as before, and usertests -q prints ALL TESTS PASSED on 3 harts.

The programs. mv old new calls rename once; if new is an existing directory it moves old into it, as Unix mv does. renametest checks everything above:

$ renametest
renametest: same directory: OK
renametest: across directories: OK
renametest: replace a file: OK
renametest: move a directory: OK
renametest: refuse a cycle: OK
renametest: refusals: OK
renametest: concurrent: 1600 renames, 400 refused cycles in 110 ticks
renametest: concurrent: OK
renametest: ALL OK (crash consistency: see renametest crash)

same directory, across directories: the inode keeps its number, link count and content; the old name is gone. Across directories is tried with the new parent below, beside and above the old one.
replace a file: the replaced file, still open, reports 0 links and is still readable through its file descriptor; a rename between two hard links to one file changes nothing.
move a directory: its subtree moves along, its .. names the new parent, and the parents’ link counts move by one.
refuse a cycle, refusals: every refused rename returns -1 and changes nothing.
concurrent: seven processes on three harts. Two rename files between ct/a and ct/b in opposite directions (ct/a/x ↔ ct/b/y, ct/b/z ↔ ct/a/w), one between ct/a/s and ct/a (ct/a/s/q ↔ ct/a/q), and one moves the directory m between ct/a and ct/b, each time also trying to move m’s parent into m (which must fail). Meanwhile one keeps trying to unlink("ct/a/s"), which must always fail because ct/a/s is not empty, and two churn names (t, u) in ct/a and ct/b. The setup is chosen to catch one tempting lock order (think question 3 says which). Afterwards every name, m’s .. and every link count is checked. A watchdog prints not finished after 60 seconds if the workers hang.

Crash consistency cannot be checked from inside: renametest crash moves a file f and a directory d between cr/a and cr/b until the machine dies, and renametest check, after a reboot, checks that each has exactly one name, that d’s .. and both parents’ link counts agree with where d is, and that f still holds its content. A driver outside xv6 kills QEMU at a random moment; this lab’s runs did it 30 times, and also ran an fsck-style checker on the disk image afterwards.

2. Think first

Answer each question in your head (or on paper) before opening a hint. Hints get more specific; the reference answer comes last.

1Why does rename need the kernel at all?

Early Unix had no rename. mv old new was a user program that called link(old, new) and then unlink(old). In this tree you could write that mv today. What can go wrong with it? Think about three things: what is on the disk if the machine dies between the two calls, what another process sees between them, and what mv does when old is a directory. Commit to an answer before reading the hints.

Check yourself

1warm-upChoose one

A user-space mv does link("a/f", "b/f") and then unlink("a/f"). The machine loses power after link returned and before unlink began. After the reboot and log recovery, what is on the disk?

Neither name exists, because the inode was being moved.Both a/f and b/f exist, naming the same inode, whose nlink is 2.Both names exist, but nlink is 1, so the file system is corrupt.Only a/f exists, because recovery rolls back the incomplete rename.

2solidTrue or false, and why

True or false: a user-space mv built from link and unlink can move a directory, as long as it also fixes the directory’s .. entry afterwards.

TrueFalse

Why?

sys_link refuses to link a directory (kernel/sysfile.c:139), so the first step already fails.It can; this is how mv worked on early Unix.A user program cannot write a directory’s entries, so it cannot fix ...

2What has to change on disk, and in which order?

Start with the easy case: both names in one directory, rename("a/x", "a/y"). List every on-disk change. Then: a/y already exists and is a file. What else changes, and what if some process has a/y open? Which of your steps can fail after the transaction has begun, and what must the order of your steps be so that a failure leaves nothing changed? Finally, which inode locks do you need, and in what order?

Check yourself

1solidPut in order

Put the reference’s steps for rename("a/x", "a/y"), where a/y exists and is a file nobody has open, in the order they happen.

unlock a
iput the old y, which frees it
begin_op
end_op
point the entry y at x’s inode and decrement the old y’s nlink
clear the entry x
lock a

2solidChoose one

Process A has a/y open for reading. Process B runs rename("a/x", "a/y"). What happens to the file that used to be a/y?

It is freed at once, and A’s next read returns garbage.Its nlink drops to 0, A keeps reading it, and it is freed when A closes it.It is freed at once, but A’s reads still work because the data is cached.rename fails, because a file that is open cannot be replaced.

3warm-upClick the line

sys_unlink holds two inode locks at once when it removes a directory. Click the line where it takes the second one.

kernel/sysfile.c

begin_op();
if ((dp = nameiparent(path, name)) == 0) {
  end_op();
  return -1;
}
217
ilock(dp);
219
// Cannot unlink "." or "..".
if (namecmp(name, ".") == 0 || namecmp(name, "..") == 0)
  goto bad;
223
if ((ip = dirlookup(dp, name, &off)) == 0)
  goto bad;
ilock(ip);
227
if (ip->nlink < 1)
  panic("unlink: nlink < 1");
if (ip->type == T_DIR && !isdirempty(ip)) {
  iunlockput(ip);
  goto bad;
}

Your pick: none yet (click a line in the code)

3Two directories, two locks. In what order?

Now rename("a/x", "b/y"): both a and b must be locked while the two entries change, or another process could see neither name or both. Suppose every rename locks the old parent, then the new parent. On another hart, at the same moment, someone runs rename("b/z", "a/w"). What happens? The file system already has an order for inode locks: what is it, and does it say anything about a and b? Propose a rule that works for every pair of directories, and check it against the code that already holds two inode locks. One more pair to check it against: rename("a/s/q", "a/q") on one hart while sys_unlink tries to remove the directory a/s on another.

The reference design

The naive order deadlocks. One rename locks a then b; the other locks b then a:

time	hart 0: `rename(a/x, b/y)`	hart 1: `rename(b/z, a/w)`
1	locks `a`	locks `b`
2	`ilock(b)`: sleeps, held by hart 1’s process	`ilock(a)`: sleeps, held by hart 0’s process
3	asleep forever	asleep forever

Inode locks are sleep-locks, so neither hart spins: both processes are SLEEPING in acquiresleep and the harts go idle. Soon the whole file system stops: both processes are inside a transaction, so no commit can happen, and every other process blocks in begin_op. Clinic 1 shows exactly this, recorded with gdb (with a delay loop added between the two locks: without it the window is a few instructions wide and our runs did not hit it).

The naive order also breaks the existing rule. rename("a/s/q", "a/q") locks a/s (old parent) then a (new parent): child before parent. sys_unlink of a/s locks a, then a/s (kernel/sysfile.c:218, kernel/sysfile.c:226). That pair deadlocks too; clinic 1 caught it once.

What the tree gives you. “Lock the directory higher in the tree first” agrees with every existing path: sys_unlink and create hold a parent and its child, namex holds one directory at a time, sys_link never holds two (kernel/sysfile.c:153). So for renames where one parent is above the other, lock that one first. That leaves two problems.

Unrelated directories, like a and b: neither is above the other.
The tree changes: a rename on another hart can move a under b while you are deciding.

The reference’s rule. A global sleep-lock, renamelock, is taken by every rename between two directories, after begin_op and before any inode lock, and held to the end. Under it:

The tree’s shape is frozen: only a two-directory rename can change which directory is above which (sys_unlink removes only empty directories, create adds only new, empty ones, a rename within one directory does not change a ..).
If one parent is above the other, it is locked first: consistent with parent-before-child.
If they are unrelated, the old parent is locked first. That is safe because the only code that ever holds two unrelated directories is a two-directory rename, and there is only one of those at a time. A cycle in the waits-for graph would need someone else holding b while waiting (directly or not) for a; every other path only waits downwards, and nothing below b is a or above it.

This is what Linux does: renames between directories take a per-file-system mutex (s_vfs_rename_mutex) and lock the ancestor first.

Why not inode-number order? It is the textbook answer for unrelated locks, and it fails here. ct/a/s can have a lower inode number than its parent ct/a (create s first, then move it under a; renametest does exactly that). Then rename("ct/a/s/q", "ct/a/q") locks s then a, while sys_unlink of ct/a/s locks a then s. A rule for renames must agree with the order the rest of the file system already uses, and inode numbers know nothing about the tree. Clinic 2 records this deadlock.

Why a sleep-lock, and why after begin_op? It is held across disk reads (directory lookups, the walk of the next question), so it cannot be a spinlock. It is taken after begin_op because only nameiparent tells the rename whether two directories are involved, and nameiparent must run inside a transaction (its iput may free an inode). That position is safe: nobody holding an inode lock ever waits for renamelock, and its holder never waits for log space or a commit before releasing it. (Taking it before begin_op in every rename would also be deadlock-free; a variant that did that passed renametest, usertests -q and two runs of renametest concurrent 1000.) The price of the reference’s order: a rename waiting for renamelock already holds a log reservation. The log admits at most three operations at once (30 log blocks, 10 reserved each), so two renames queued on the lock can occupy two of the three slots while other file-system calls wait in begin_op.

Check yourself

1solidChoose one

With the naive order (old parent, then new parent), rename(ct/a/x, ct/b/y) and rename(ct/b/z, ct/a/w) deadlock on two harts. What does gdb show when attached a minute later?

Both processes SLEEPING in acquiresleep, each holding one directory’s sleep-lock; all three harts idle; other file-system processes asleep in begin_op.Both renames fail with -1 after a timeout.Two harts spinning in acquire at 100% CPU, the third running other processes.panic: sched locks

2deepChoose one

A classmate proposes: “lock the two parents in inode-number order, lower first, with the global rename lock as well”. Which existing operation can deadlock with such a rename?

unlink of a directory, which locks the parent and then the child, when the child has the lower inode number.Another rename between the same two directories.None: the global rename lock serializes everything that holds two directories.Path lookup, which locks each directory on the path in turn.

3warm-upTrue or false, and why

True or false: while two processes are deadlocked on two inode sleep-locks, the harts they ran on are spinning at full speed.

TrueFalse

Why?

The harts run the deadlock detector.Interrupts are off while a sleep-lock is held, so the harts stop.acquiresleep sleeps while the lock is held, so the harts run other processes or wait for interrupts in the scheduler.

4Which directory is above which?

Your rule needs one fact: is b above a in the tree (or the other way round)? xv6 keeps no parent pointers in memory. How do you find out, which locks may you hold while you do, and why is the answer still true a moment later when you use it? And since the answer must be known before the parents are locked: what about the lookups of x and y themselves, which also need a directory lock?

The reference design

Walk up. Starting from b, read its .. entry, then that directory’s .., and so on, until you reach a (so a is above b) or the root (it is not). The reference’s isancestor(a, b) does that. It locks each directory only while reading its .., like namex. It must not run while the rename holds the parents’ locks: walking up from b while holding b locks b’s parent while holding b, child before parent, and sys_unlink of b (parent, then b) would deadlock with it.

Why the answer stays true. The walk’s result describes the tree at the moment of the walk. It is still true when the parents are locked only because renamelock is held the whole time: no other two-directory rename can move a directory, and nothing else changes the chain of .. entries above a live directory. (A directory with nlink 0 has been removed; the walk stops there, and the rename fails later, at its checks under the locks.)

The names, again. The walk happens before the parents are locked, and the cycle check of the next question needs to know which inode x is. So the reference looks up both names first, each with only its directory locked for a moment, decides everything about the tree, and only then locks the parents. Between the lookup and the lock, another process may have changed a name: unlink(a/x), or create(b/y). So, with the parents locked, it looks both names up again and compares the results with what it decided on (samename). If either name now leads somewhere else, the rename returns -1.

The comparison is by in-memory inode pointer, and that is safe: the rename holds a reference to each inode it looked up, so neither can be freed and its inode number reused in the meantime (iput frees only at ref 1).

Also note what the lookup does not do: it never holds a while locking x. To learn x’s type it locks x alone, for a moment (itype): an inode’s type never changes while someone holds a reference to it. So the rename never holds two files at once, which matters because hard links can make the same two files siblings in two directories, in opposite roles. It does hold one parent and then a child of the other parent (dp2, then the moved directory, in a later step), and those can be siblings with no tree order between them: that, too, is safe only because renamelock keeps every other two-directory rename out.

Check yourself

1solidTrue or false, and why

True or false: it would be fine to walk up through .. while holding the locks of both parents, since the walk only reads directories.

TrueFalse

Why?

Walking up locks an ancestor while holding its descendant, the reverse of the parent-before-child order that unlink and create use.The walk would return a wrong answer because the parents are locked.dirlookup would panic on a locked directory.

2deepChoose one

After locking both parents, the reference looks up old and new again and gives up if either now names a different inode than in its first lookup. Which interleaving is this check for?

None; it is only a sanity check.Another process unlinked or replaced one of the names (or created new) after the first lookup, while neither parent was locked.Another two-directory rename moved one of the parents.The inode was freed and its number reused for a new file with the same name.

5Moving a directory into itself

mv a a/c/b: the directory a would become an entry inside its own subdirectory. Suppose nothing stops it. Work out what the tree looks like afterwards: what can ls reach, what are the link counts of a and a/c, and can xv6 ever reclaim those inodes? Then: how do you detect such a move, and what about mv a a/b, where the new parent is a?

Check yourself

1solidChoose one

A kernel without the cycle check runs mkdir a; mkdir a/c; echo hi > a/c/f; mv a a/c/b. What does an fsck-style check of the disk report afterwards?

Nothing: the disk is consistent, a has just moved.a’s link count is 0, so ireclaim frees it at the next boot.The kernel panics during the rename.a, a/c and a/c/f are allocated, have positive link counts, and are not reachable from /.

6What else moves with a directory?

mv a/d b/d, where d is a directory. Its entry moves, as for a file. What else on disk names a because of d, and must now name b? How do the link counts of a and b change, and why? What limit applies to b? Finally, suppose you forget one of these: which later operations go wrong, and is one of them a check you wrote yourself?

Check yourself

1solidMatch the pairs

rename("a/d", "b/d") where d is a directory with no subdirectories. Match each inode to what happens to its nlink.

abd

2deepTrue or false, and why

True or false: if a rename forgets to rewrite a moved directory’s .. (but fixes the link counts), the only symptom is that cd .. from inside it goes to the wrong place.

TrueFalse

Why?

It is harmless, because fsck would repair it at the next boot.The kernel panics with rename: … at once.The cycle check walks .. entries, so it can be fooled into allowing a move that creates a loop; and the old parent can be removed while .. still names it.

7Does one rename fit in one transaction?

A transaction may write at most MAXOPBLOCKS distinct blocks (kernel/param.h:9). Count them for the most expensive rename you can construct: moving a directory from one parent to another. Which blocks get written? Can the new parent grow? Can the count ever exceed 10? Count, don’t guess.

The reference design

The blocks a directory move can dirty, each logged once however often it is written:

block	when
the new parent’s data block that receives the entry	always: a block with a free slot, or a new block if every slot is in use
the new parent’s indirect block	only if the new block lies beyond the 12 direct blocks (allocated first if it is the 13th)
the bitmap block	only if a block was allocated (one bitmap block covers all 2000 blocks)
the old parent’s data block	always: the cleared entry
the moved directory’s first data block	always: its `..` entry
the new parent’s inode block	always: `writei` rewrites the inode, and `nlink + 1`
the old parent’s inode block	always: `writei` and `nlink - 1`
the moved directory’s inode block	always: `writei` rewrites it after the `..` change

At most 8, and fewer when blocks coincide: the three inode blocks are distinct only if the three inode numbers fall in three different groups of 16. A counting copy of the kernel printed the logged blocks for each rename at its end_op:

rename	blocks logged
a file, within one directory	2
a file, to another directory	3
replacing a 3-block file in another directory	5
a directory, to another parent	5
a directory, into a parent whose last block is full	5
a directory, into a parent with 12 full blocks, three inodes in three inode blocks	8

The last line is the worst case: new data block, indirect block, bitmap, three inode blocks, the old parent’s block and the moved directory’s block. 8 ≤ 10: it fits, and begin_op‘s reservation of 10 per operation is never exceeded. A file replacement can dirty at most 6 (two directories’ data and inode blocks, the replaced file’s inode block, the bitmap block for its freed blocks; the replaced file’s indirect block is only read).

Two things make the count small: absorption (the three directories’ inodes often share an inode block, which is why ordinary moves cost 3 to 5), and the fact that the replaced file’s blocks are freed by clearing bits in one bitmap block, not by writing the blocks themselves.

Check yourself

1solidType a number

On the counting kernel, what is the largest number of distinct blocks one rename logged (a directory moved into a parent that needed its indirect block, with the three directories’ inodes in three different inode blocks)?

decimal, 0x hex or 0b binary

2solidChoose all that apply

The counting kernel logged 3 blocks for rename("m/g", "m/a/g"), a file moving from m to m/a, where the inodes of m and m/a are in the same inode block. Which blocks were they?

3. Build it

Start.

git checkout -b my-rename 06aad25

Add the test program first: copy the spec’s checks into user/renametest.c, add $U/_renametest\ and $U/_mv\ to UPROGS in the Makefile. It will not compile until rename exists, which is milestone 1.

Milestones, in an order that keeps the system bootable after each one.

The plumbing. SYS_rename in kernel/syscall.h, the table entry in kernel/syscall.c, entry("rename") in user/usys.pl, the prototype in user/user.h, and a sys_rename in sysfile.c that fetches both strings with argstr and returns -1. Test: usertests -q; renametest prints FAIL lines.
One directory. Same parent only (return -1 otherwise). Lock the directory, look up both names, handle the “same inode” case, write the new name first, then clear the old one. A small helper that rewrites one existing entry in place (by offset) serves both the replace case and, later, ... Test: renametest’s first test, usertests -q.
Two directories, files only. The global sleep-lock (initialize it at boot, after iinit), the upward walk, lookups before locking, the parent order, the re-check under the locks. Refuse directories across parents for now. Test: renametest’s first three tests and concurrent, then usertests -q.
Directories. The cycle check, .., the two link counts. Test: all of renametest, then usertests -q, then renametest again.
Crash consistency. Run renametest crash, then kill QEMU from another terminal on the host: pkill -KILL -f qemu-system-riscv64 works on Linux, macOS and WSL alike. Boot the same fs.img again (make qemu does not rebuild it when nothing changed) and run renametest check. Repeat with random delays; a small python3 script using only the standard library (subprocess, random, time) can start QEMU, type the command, sleep a random time and call Popen.kill(), on any of the three.

Debugging advice.

A hang in concurrent: the watchdog prints not finished after 60 seconds. Attach gdb to the running QEMU and dump the process table (state, chan) and every inode whose lock.locked is set, with lock.pid. A process sleeping on an inode lock’s address holds another lock that someone else wants: you have a cycle, and the dump names it. The kernel stack of a sleeping process can be walked from p->context.s0 with the frame pointers (*(fp-8) is the return address, *(fp-16) the caller’s fp).
Rare deadlocks need volume: renametest concurrent 1000 runs only the concurrent part, 1000 rounds. Several QEMUs in parallel help more than one long run.
Crashes at a chosen moment: start QEMU halted (make qemu-gdb), break sys_rename, continue, then a breakpoint in commit before or after write_head (kernel/log.c:207), and gdb’s kill ends QEMU on the spot.
Checking a disk image: an fsck-style script on the host (walk from inode 1, compare link counts with the entries found, check .., compare the bitmap with the blocks in use) finds what ls cannot: unreachable loops and wrong counts. Written in python3 with only the standard library (struct to decode fs.img), it runs the same on Linux, macOS and WSL.
panic: rename: .. (the reference’s sanity check) means a directory’s .. did not name its old parent when you went to rewrite it: an earlier bug left it wrong.

4. Debugging clinic

Each of these bugs was put into the reference solution on purpose and run on three harts. The symptom is exactly what happened. Try to explain it before revealing why.

1The naive order, old parent then new parent

No global lock and no tree order: lock the parent of old, then the parent of new (everything else as in the reference). The recorded runs also had a delay loop between the two locks, an experiment to make the race likely (see why):

   twodirs = (dp1 != dp2);
-  if (twodirs)
-    acquiresleep(&renamelock);
...
-  if (twodirs && isancestor(dp2, dp1)) {
+  ilock(dp1);
+  for (volatile int w_ = 0; w_ < 1000000; w_++) // widen the window
+    ;
+  if (twodirs)
     ilock(dp2);
-    ilock(dp1);
-  } else {
-    ilock(dp1);
-    if (twodirs)
-      ilock(dp2);
-  }
...
 out:
-  if (twodirs)
-    releasesleep(&renamelock);

What happened when we ran it

$ renametest concurrent 1000
renametest: concurrent: not finished after 300 seconds

# gdb, attached to the running QEMU:
[...]
=== harts ===
  Id   Target Id                    Frame 
* 1    Thread 1.1 (CPU#0 [halted ]) s_sstatus (x=2) at kernel/riscv.h:67
  2    Thread 1.2 (CPU#1 [halted ]) s_sstatus (x=2) at kernel/riscv.h:67
  3    Thread 1.3 (CPU#2 [halted ]) s_sstatus (x=2) at kernel/riscv.h:67
=== processes ===
proc[0] pid 1 init state 2 chan 0x80010e00
proc[1] pid 2 sh state 2 chan 0x80010f68
proc[2] pid 3 renametest state 2 chan 0x800110d0
proc[3] pid 4 renametest state 2 chan 0x800209a0
proc[4] pid 5 renametest state 2 chan 0x8001f0b8
proc[5] pid 6 renametest state 2 chan 0x8001f140
proc[6] pid 7 renametest state 2 chan 0x800209a0
proc[7] pid 8 renametest state 2 chan 0x800209a0
proc[8] pid 9 renametest state 2 chan 0x800209a0
proc[9] pid 10 renametest state 2 chan 0x800209a0
proc[10] pid 11 renametest state 2 chan 0x800209a0
=== held sleep-locks ===
renamelock: locked 0 pid 0 at 0x80021aa0
inode 28 (type 1): lock at 0x8001f0b8 held by pid 6
inode 29 (type 1): lock at 0x8001f140 held by pid 5
=== kernel stacks of sleeping renametest processes (frame-pointer walk) ===
[...]
pid 5:
sleep + 32 in section .text
acquiresleep + 44 in section .text
ilock + 26 in section .text
sys_rename + 322 in section .text
syscall + 58 in section .text
usertrap + 166 in section .text
No symbol matches $ra.
pid 6:
sleep + 32 in section .text
acquiresleep + 44 in section .text
ilock + 26 in section .text
sys_rename + 322 in section .text
syscall + 58 in section .text
usertrap + 166 in section .text
No symbol matches $ra.
pid 7:
sleep + 32 in section .text
begin_op + 100 in section .text
sys_rename + 54 in section .text
[...]
pid 9:
sleep + 32 in section .text
begin_op + 100 in section .text
sys_open + 46 in section .text
[...]

Read the dump as a waits-for graph. renametest concurrent creates ct, ct/s, ct/a and ct/b in that order, so ct/a is inode 28 and ct/b inode 29; their locks are at 0x8001f0b8 and 0x8001f140. The workers are pids 5 to 11 (pid 4 is the watchdog). pid 5 moves x between ct/a and ct/b: it holds ct/b and sleeps on ct/a’s lock, so it was in rename("ct/b/y", "ct/a/x"), old parent first. pid 6 moves z the other way: it holds ct/a and sleeps on ct/b’s lock, in rename("ct/a/w", "ct/b/z"). sys_rename + 322 returns to the second ilock (line 390 of this copy). Each holds what the other wants: the deadlock of think question 3, exactly.

Everything else follows from it:

The harts are idle, not spinning. Inode locks are sleep-locks, so both waiters are SLEEPING (state 2) and the scheduler has nothing to run: each hart is halted at the instruction after wfi in scheduler (the inlined intr_on that gdb shows as s_sstatus).
The file system stops. pids 5 and 6 are inside their transactions and will never call end_op, so the log can never commit. Every other worker sleeps in begin_op on 0x800209a0, which is &log: pids 7 and 8 (the ct/a/s renamer and the directory mover) in sys_rename, pids 9 to 11 (the unlinker and the two churners, in their exists("ct/stop") checks, which open a file) in sys_open. So does pid 4, the watchdog: it printed its message and then called exit, which needs a transaction to drop its working directory. Any new command that touches the file system would join them.
Nothing panics, nothing prints except the watchdog’s line.

How often. Without the delay loop, this kernel passed all 4 runs of renametest concurrent 1000: the window is the few instructions between the two ilock calls. With the delay loop after the first lock, 4 of 6 runs deadlocked: twice the two file movers (this dump), twice a file mover against the directory mover. The reference kernel with the same delay loop finished both of its concurrent 1000 runs. (With a simpler test that had no directory mover or churners, the unwidened naive kernel deadlocked once in 11 runs, between the ct/a/s renamer and the unlinker: the child-before-parent case.)

The lesson of lab 11’s clinic 1 again: a lock order that is wrong can pass a test many times. You find this bug by reasoning about the order, and you confirm it by making the window wide.

2Inode-number order instead of the tree

The global lock stays; the parents are locked lower inode number first. As in clinic 1, the recorded runs had a delay loop between the two locks:

-  if (twodirs && isancestor(dp2, dp1)) {
+  if (twodirs && dp2->inum < dp1->inum) {
     ilock(dp2);
+  for (volatile int w_ = 0; w_ < 1000000; w_++) // widen the window
+    ;
     ilock(dp1);
   } else {
     ilock(dp1);
+  for (volatile int w_ = 0; w_ < 1000000; w_++) // widen the window
+    ;
     if (twodirs)
       ilock(dp2);

What happened when we ran it

$ renametest concurrent 1000
renametest: concurrent: not finished after 300 seconds

# gdb, attached to the running QEMU:
[...]
=== harts ===
  Id   Target Id                    Frame 
* 1    Thread 1.1 (CPU#0 [halted ]) s_sstatus (x=2) at kernel/riscv.h:67
  2    Thread 1.2 (CPU#1 [halted ]) s_sstatus (x=2) at kernel/riscv.h:67
  3    Thread 1.3 (CPU#2 [halted ]) s_sstatus (x=2) at kernel/riscv.h:67
=== processes ===
proc[0] pid 1 init state 2 chan 0x80010e00
proc[1] pid 2 sh state 2 chan 0x80010f68
proc[2] pid 3 renametest state 2 chan 0x800110d0
proc[3] pid 4 renametest state 2 chan 0x800209a0
proc[4] pid 5 renametest state 2 chan 0x800209a0
proc[5] pid 6 renametest state 2 chan 0x800209a0
proc[6] pid 7 renametest state 2 chan 0x8001f0b8
proc[7] pid 8 renametest state 2 chan 0x800209a0
proc[8] pid 9 renametest state 2 chan 0x8001f030
proc[9] pid 10 renametest state 2 chan 0x800209a0
proc[10] pid 11 renametest state 2 chan 0x800209a0
=== held sleep-locks ===
renamelock: locked 1 pid 7 at 0x80021aa0
inode 27 (type 1): lock at 0x8001f030 held by pid 7
inode 28 (type 1): lock at 0x8001f0b8 held by pid 9
=== kernel stacks of sleeping renametest processes (frame-pointer walk) ===
[...]
pid 7:
sleep + 32 in section .text
acquiresleep + 44 in section .text
ilock + 26 in section .text
sys_rename + 906 in section .text
syscall + 58 in section .text
usertrap + 166 in section .text
No symbol matches $ra.
[...]
pid 9:
sleep + 32 in section .text
acquiresleep + 44 in section .text
ilock + 26 in section .text
sys_unlink + 120 in section .text
syscall + 58 in section .text
usertrap + 166 in section .text
No symbol matches $ra.
[...]

3No cycle check

The test that refuses to move a directory into its own subtree is missing:

-  if (twodirs && type1 == T_DIR && isancestor(ip, dp2))
-    goto out;

What happened when we ran it

$ mkdir a
$ mkdir a/c
$ echo hi > a/c/f
$ ls a/c
.              1 27 48
..             1 26 48
f              2 28 3
$ mv a a/c/b
$ ls a
ls: cannot open a
$ ls a/c/b
ls: cannot open a/c/b
$ mkdir a
$ ls a
.              1 29 32
..             1 1 1024
$

# the disk image afterwards, checked on the host:
fsck: inode 26 (type 1, nlink 2) is not reachable from /
fsck: inode 27 (type 1, nlink 2) is not reachable from /
fsck: inode 28 (type 2, nlink 1) is not reachable from /
fsck: 29 inodes in use, 26 reachable, 1071 data blocks; 3 problems

# another boot: mkdir a, then mv a a/b; the shell never returns. gdb:
proc[2] pid 4 mv state 2 chan 0x8001f030
=== held sleep-locks ===
renamelock: locked 1 pid 4 at 0x80021aa0
inode 1 (type 1): lock at 0x8001ef20 held by pid 4
inode 26 (type 1): lock at 0x8001f030 held by pid 4
pid 4:
sleep + 32 in section .text
acquiresleep + 44 in section .text
ilock + 26 in section .text
sys_rename + 588 in section .text

4Two transactions, to make the new name durable first

A tempting idea: commit the new entry before removing the old one, so the file can never be lost. It ends the transaction in the middle (all locks still held):

   } else if (dirlink(dp2, name2, ip->inum) < 0) {
     goto unlock; // no free block for the new entry: nothing changed
   }
+  end_op(); // make the new name durable first
+  begin_op();
   dirset(dp1, off1, 0); // old disappears

To crash at exactly the wrong moment: QEMU started halted under gdb, a breakpoint on the new begin_op() line, renametest crash, and gdb’s kill at the first hit. Then the same disk image was booted twice more.

What happened when we ran it

Thread 2 hit Breakpoint 1, sys_rename () at kernel/sysfile.c:415
[...]
pid 3 (renametest): rename("cr/a/f", "cr/b/f")
log: lh.n 0, outstanding 0, committing 0
[Inferior 1 (process 1) killed]

# boot 2, same fs.img:
$ renametest check
renametest: failed: f has not exactly one name
renametest: check: f in cr/a (2 names), d in cr/a (1 name)
renametest: check: FAIL
$ ls cr/a
.              1 27 64
..             1 26 64
f              2 29 5
d              1 30 32
$ ls cr/b
.              1 28 48
..             1 26 64
f              2 29 5
# the image after boot 2, checked on the host:
fsck: inode 29 /cr/b/f: nlink 1, but 2 links found
fsck: 30 inodes in use, 30 reachable, 1072 data blocks; 1 problems

# boot 3, same fs.img:
$ rm cr/a/f
$ cat cr/b/f
panic: ilock: no type

5Forgetting to fix `..`

The directory’s link counts move from the old parent to the new one, but its .. entry is not rewritten:

   if (twodirs && type1 == T_DIR) {
     // ip's ".." must name its new parent, and the link that ".."
     // is moves from dp1 to dp2.
-    ilock(ip);
-    if ((pp = dirlookup(ip, "..", &off)) != dp1)
-      panic("rename: ..");
-    iput(pp);
-    dirset(ip, off, dp2->inum);
-    iunlock(ip);
     dp1->nlink--;
     iupdate(dp1);

What happened when we ran it

$ renametest
renametest: same directory: OK
renametest: across directories: OK
renametest: replace a file: OK
renametest: failed: rt/c/d/.. is not rt/c
renametest: move a directory: FAIL
renametest: failed: moved rt/c below itself
renametest: refuse a cycle: FAIL
renametest: failed: replaced a directory
renametest: refusals: FAIL
renametest: failed: a worker's rename or unlink did the wrong thing
renametest: concurrent: 1600 renames, 400 refused cycles in 70 ticks
renametest: concurrent: FAIL
renametest: SOME TESTS FAILED

# another boot:
$ mkdir a
$ mkdir b
$ mkdir a/d
$ mv a/d b
$ ls b/d/..
.              1 26 48
..             1 1 1024
$ rm a
$ ls b/d/..
panic: ilock: no type

# the disk image after the panic, checked on the host:
fsck: /b/d: entry '..' -> free inode 26
fsck: inode 27 /b: nlink 2, but 1 links found
fsck: 27 inodes in use, 27 reachable, 1069 data blocks; 2 problems

5. The reference solution

Take the guided tour through the reference solution, one commit at a time, with the machine state at every step:

Open the reveal tour →

Or read the commits

75cbfbe Add a rename system call that refuses everything
kernel/syscall.c
@@ -102,8 +102,9 @@ extern uint64 sys_unlink(void);
102102extern uint64 sys_link(void);
103103extern uint64 sys_mkdir(void);
104104extern uint64 sys_close(void);
105105extern uint64 sys_sync(void);
106extern uint64 sys_rename(void);
106107
107108// An array mapping syscall numbers from syscall.h
108109// to the function that handles the system call.
109110static uint64 (*syscalls[])(void) = {
@@ -129,8 +130,9 @@ static uint64 (*syscalls[])(void) = {
129130 [SYS_link] = sys_link,
130131 [SYS_mkdir] = sys_mkdir,
131132 [SYS_close] = sys_close,
132133 [SYS_sync] = sys_sync,
134 [SYS_rename] = sys_rename,
133135 // clang-format on
134136};
135137
136138void
kernel/syscall.h
@@ -20,4 +20,5 @@
2020#define SYS_link 19
2121#define SYS_mkdir 20
2222#define SYS_close 21
2323#define SYS_sync 22
24#define SYS_rename 23
kernel/sysfile.c
@@ -254,8 +254,20 @@ bad:
254254 end_op();
255255 return -1;
256256}
257257
258// Give the file or directory old the name new, in one step:
259// old disappears and new appears in the same transaction.
260uint64
261sys_rename(void)
262{
263 char old[MAXPATH], new[MAXPATH];
264
265 if (argstr(0, old, MAXPATH) < 0 || argstr(1, new, MAXPATH) < 0)
266 return -1;
267 return -1; // not yet
268}
269
258270static struct inode *
259271create(char *path, short type, short major, short minor)
260272{
261273 struct inode *ip, *dp;
user/user.h
@@ -24,8 +24,9 @@ int getpid(void);
2424char *sys_sbrk(int, int);
2525int pause(int);
2626int uptime(void);
2727int sync(void);
28int rename(const char *, const char *);
2829
2930// ulib.c
3031int stat(const char *, struct stat *);
3132char *strcpy(char *, const char *);
user/usys.pl
@@ -42,4 +42,5 @@ entry("getpid");
4242entry("sbrk");
4343entry("pause");
4444entry("uptime");
4545entry("sync");
46entry("rename");
20dba9f Rename within one directory
kernel/defs.h
@@ -38,8 +38,9 @@ int filewrite(struct file*, uint64, int n);
3838// fs.c
3939void fsinit(int);
4040int dirlink(struct inode*, char*, uint);
4141struct inode* dirlookup(struct inode*, char*, uint*);
42void dirset(struct inode*, uint, uint);
4243struct inode* ialloc(uint, short);
4344struct inode* idup(struct inode*);
4445void iinit();
4546void ilock(struct inode*);
kernel/fs.c
@@ -644,8 +644,26 @@ dirlink(struct inode *dp, char *name, uint inum)
644644
645645 return 0;
646646}
647647
648// Point the entry at byte offset off in directory dp at inode
649// inum, keeping its name; inum 0 frees the entry, as unlink does.
650// Caller must hold dp->lock. The entry exists, so its block is
651// already allocated and the write cannot run out of space.
652void
653dirset(struct inode *dp, uint off, uint inum)
654{
655 struct dirent de;
656
657 if (readi(dp, 0, (uint64)&de, off, sizeof(de)) != sizeof(de))
658 panic("dirset: readi");
659 if (inum == 0)
660 memset(&de, 0, sizeof(de));
661 de.inum = inum;
662 if (writei(dp, 0, (uint64)&de, off, sizeof(de)) != sizeof(de))
663 panic("dirset: writei");
664}
665
648666// Paths
649667
650668// Copy the next path element from path into name.
651669// Return a pointer to the element following the copied one.
kernel/sysfile.c
@@ -254,18 +254,87 @@ bad:
254254 end_op();
255255 return -1;
256256}
257257
258// Is name "." or ".."?
259static int
260isdots(char *name)
261{
262 return namecmp(name, ".") == 0 || namecmp(name, "..") == 0;
263}
264
265// The type of ip, which the caller must not have locked.
266// An inode's type cannot change while we hold a reference to it.
267static short
268itype(struct inode *ip)
269{
270 short type;
271
272 ilock(ip);
273 type = ip->type;
274 iunlock(ip);
275 return type;
276}
277
258278// Give the file or directory old the name new, in one step:
259279// old disappears and new appears in the same transaction.
260280uint64
261281sys_rename(void)
262282{
263 char old[MAXPATH], new[MAXPATH];
283 char name1[DIRSIZ], name2[DIRSIZ], old[MAXPATH], new[MAXPATH];
284 struct inode *dp1 = 0, *dp2 = 0, *ip = 0, *tp = 0;
285 uint off1, off2;
286 int r = -1;
264287
265288 if (argstr(0, old, MAXPATH) < 0 || argstr(1, new, MAXPATH) < 0)
266289 return -1;
267 return -1; // not yet
290
291 begin_op();
292 if ((dp1 = nameiparent(old, name1)) == 0 ||
293 (dp2 = nameiparent(new, name2)) == 0)
294 goto out;
295 if (isdots(name1) || isdots(name2))
296 goto out;
297 if (dp1 != dp2)
298 goto out; // two directories: not yet
299
300 ilock(dp1);
301 if ((ip = dirlookup(dp1, name1, &off1)) == 0)
302 goto unlock;
303 tp = dirlookup(dp1, name2, &off2);
304 if (tp == ip) { // two names for one file: nothing to do
305 r = 0;
306 goto unlock;
307 }
308 // Replace only a non-directory, and only with a non-directory.
309 if (tp != 0 && (itype(ip) == T_DIR || itype(tp) == T_DIR))
310 goto unlock;
311
312 if (tp != 0) {
313 ilock(tp);
314 dirset(dp1, off2, ip->inum); // new now names ip
315 tp->nlink--;
316 iupdate(tp);
317 iunlock(tp);
318 } else if (dirlink(dp1, name2, ip->inum) < 0) {
319 goto unlock; // no free block for the new entry: nothing changed
320 }
321 dirset(dp1, off1, 0); // old disappears
322 r = 0;
323
324unlock:
325 iunlock(dp1);
326out:
327 if (tp)
328 iput(tp); // frees tp if that was its last link
329 if (ip)
330 iput(ip);
331 if (dp2)
332 iput(dp2);
333 if (dp1)
334 iput(dp1);
335 end_op();
336 return r;
268337}
269338
270339static struct inode *
271340create(char *path, short type, short major, short minor)
cbac631 Rename across directories: a rename lock, ancestor first
kernel/defs.h
@@ -130,8 +130,11 @@ char* safestrcpy(char*, const char*, int);
130130int strlen(const char*);
131131int strncmp(const char*, const char*, uint);
132132char* strncpy(char*, const char*, int);
133133
134// sysfile.c
135void renameinit(void);
136
134137// syscall.c
135138void argint(int, int*);
136139int argstr(int, char*, int);
137140void argaddr(int, uint64 *);
kernel/main.c
@@ -26,8 +26,9 @@ main()
2626 plicinithart(); // ask PLIC for device interrupts
2727 binit(); // buffer cache
2828 iinit(); // inode table
2929 fileinit(); // file table
30 renameinit(); // the rename lock
3031 virtio_disk_init(); // emulated hard disk
3132 userinit(); // first user process
3233
3334 __atomic_store_n(&started, 1, __ATOMIC_RELEASE);
kernel/sysfile.c
@@ -254,8 +254,20 @@ bad:
254254 end_op();
255255 return -1;
256256}
257257
258// The rename lock. A rename between two directories holds it
259// from its first look at the tree to the end, so only one such
260// rename at a time can be deciding which directory lies inside
261// which, or changing it (Linux calls it s_vfs_rename_mutex).
262static struct sleeplock renamelock;
263
264void
265renameinit(void)
266{
267 initsleeplock(&renamelock, "rename");
268}
269
258270// Is name "." or ".."?
259271static int
260272isdots(char *name)
261273{
@@ -274,57 +286,137 @@ itype(struct inode *ip)
274286 iunlock(ip);
275287 return type;
276288}
277289
290// Look up name in directory dp, which the caller must not have
291// locked. Returns the inode, referenced but not locked, or 0.
292static struct inode *
293lookup(struct inode *dp, char *name)
294{
295 struct inode *ip;
296
297 ilock(dp);
298 ip = dirlookup(dp, name, 0);
299 iunlock(dp);
300 return ip;
301}
302
303// With dp locked: does name in dp still refer to ip (0: to
304// nothing)? If it does, *poff is set to the entry's offset.
305static int
306samename(struct inode *dp, char *name, struct inode *ip, uint *poff)
307{
308 struct inode *x;
309
310 x = dirlookup(dp, name, poff);
311 if (x != 0)
312 iput(x); // still referenced by its directory entry: not freed
313 return x == ip;
314}
315
316// Is directory a the same as directory b, or above it in the
317// tree? Walks up from b through ".." entries, locking one
318// directory at a time. The caller holds renamelock, so no
319// directory moves during the walk, and holds no inode lock:
320// locking upwards while holding one could deadlock.
321static int
322isancestor(struct inode *a, struct inode *b)
323{
324 struct inode *ip, *next;
325 int r;
326
327 ip = idup(b);
328 while (ip != a && ip->inum != ROOTINO) {
329 ilock(ip);
330 if (ip->nlink == 0) { // removed; the caller's checks will fail
331 iunlockput(ip);
332 return 0;
333 }
334 next = dirlookup(ip, "..", 0);
335 iunlockput(ip);
336 ip = next;
337 }
338 r = (ip == a);
339 iput(ip);
340 return r;
341}
342
278343// Give the file or directory old the name new, in one step:
279344// old disappears and new appears in the same transaction.
280345uint64
281346sys_rename(void)
282347{
283348 char name1[DIRSIZ], name2[DIRSIZ], old[MAXPATH], new[MAXPATH];
284349 struct inode *dp1 = 0, *dp2 = 0, *ip = 0, *tp = 0;
350 short type1;
285351 uint off1, off2;
286 int r = -1;
352 int twodirs = 0, r = -1;
287353
288354 if (argstr(0, old, MAXPATH) < 0 || argstr(1, new, MAXPATH) < 0)
289355 return -1;
290356
291357 begin_op();
292358 if ((dp1 = nameiparent(old, name1)) == 0 ||
293359 (dp2 = nameiparent(new, name2)) == 0)
294360 goto out;
295 if (isdots(name1) || isdots(name2))
361 if (isdots(name1) || isdots(name2) || dp1->dev != dp2->dev)
296362 goto out;
297 if (dp1 != dp2)
298 goto out; // two directories: not yet
363 twodirs = (dp1 != dp2);
364 if (twodirs)
365 acquiresleep(&renamelock);
299366
300 ilock(dp1);
301 if ((ip = dirlookup(dp1, name1, &off1)) == 0)
302 goto unlock;
303 tp = dirlookup(dp1, name2, &off2);
367 // What do the names refer to? Decide everything that depends
368 // on the shape of the tree now, while no inode is locked.
369 if ((ip = lookup(dp1, name1)) == 0)
370 goto out;
371 tp = lookup(dp2, name2);
304372 if (tp == ip) { // two names for one file: nothing to do
305373 r = 0;
306 goto unlock;
374 goto out;
307375 }
376 type1 = itype(ip);
308377 // Replace only a non-directory, and only with a non-directory.
309 if (tp != 0 && (itype(ip) == T_DIR || itype(tp) == T_DIR))
378 if (tp != 0 && (type1 == T_DIR || itype(tp) == T_DIR))
379 goto out;
380 if (twodirs && type1 == T_DIR)
381 goto out; // moving a directory: not yet
382
383 // Lock the parents, the one higher in the tree first. Two
384 // unrelated directories can be locked in either order, because
385 // renamelock keeps every other two-directory rename out.
386 if (twodirs && isancestor(dp2, dp1)) {
387 ilock(dp2);
388 ilock(dp1);
389 } else {
390 ilock(dp1);
391 if (twodirs)
392 ilock(dp2);
393 }
394 // The names were looked up unlocked: do they still mean the
395 // same? (And is dp2 still in the tree?)
396 if (!samename(dp1, name1, ip, &off1) || !samename(dp2, name2, tp, &off2) ||
397 dp2->nlink == 0)
310398 goto unlock;
311399
312400 if (tp != 0) {
313401 ilock(tp);
314 dirset(dp1, off2, ip->inum); // new now names ip
402 dirset(dp2, off2, ip->inum); // new now names ip
315403 tp->nlink--;
316404 iupdate(tp);
317405 iunlock(tp);
318 } else if (dirlink(dp1, name2, ip->inum) < 0) {
406 } else if (dirlink(dp2, name2, ip->inum) < 0) {
319407 goto unlock; // no free block for the new entry: nothing changed
320408 }
321409 dirset(dp1, off1, 0); // old disappears
322410 r = 0;
323411
324412unlock:
325413 iunlock(dp1);
414 if (twodirs)
415 iunlock(dp2);
326416out:
417 if (twodirs)
418 releasesleep(&renamelock);
327419 if (tp)
328420 iput(tp); // frees tp if that was its last link
329421 if (ip)
330422 iput(ip);
9925c12 Move directories between parents
kernel/sysfile.c
@@ -345,11 +345,11 @@ isancestor(struct inode *a, struct inode *b)
345345uint64
346346sys_rename(void)
347347{
348348 char name1[DIRSIZ], name2[DIRSIZ], old[MAXPATH], new[MAXPATH];
349 struct inode *dp1 = 0, *dp2 = 0, *ip = 0, *tp = 0;
349 struct inode *dp1 = 0, *dp2 = 0, *ip = 0, *tp = 0, *pp;
350350 short type1;
351 uint off1, off2;
351 uint off1, off2, off;
352352 int twodirs = 0, r = -1;
353353
354354 if (argstr(0, old, MAXPATH) < 0 || argstr(1, new, MAXPATH) < 0)
355355 return -1;
@@ -376,10 +376,12 @@ sys_rename(void)
376376 type1 = itype(ip);
377377 // Replace only a non-directory, and only with a non-directory.
378378 if (tp != 0 && (type1 == T_DIR || itype(tp) == T_DIR))
379379 goto out;
380 if (twodirs && type1 == T_DIR)
381 goto out; // moving a directory: not yet
380 // A directory may not move into itself or below itself: it
381 // would leave the tree, taking a loop of directories with it.
382 if (twodirs && type1 == T_DIR && isancestor(ip, dp2))
383 goto out;
382384
383385 // Lock the parents, the one higher in the tree first. Two
384386 // unrelated directories can be locked in either order, because
385387 // renamelock keeps every other two-directory rename out.
@@ -395,8 +397,11 @@ sys_rename(void)
395397 // same? (And is dp2 still in the tree?)
396398 if (!samename(dp1, name1, ip, &off1) || !samename(dp2, name2, tp, &off2) ||
397399 dp2->nlink == 0)
398400 goto unlock;
401 // A directory's ".." will add a link to dp2.
402 if (twodirs && type1 == T_DIR && dp2->nlink >= NLINK_MAX)
403 goto unlock;
399404
400405 if (tp != 0) {
401406 ilock(tp);
402407 dirset(dp2, off2, ip->inum); // new now names ip
@@ -406,8 +411,23 @@ sys_rename(void)
406411 } else if (dirlink(dp2, name2, ip->inum) < 0) {
407412 goto unlock; // no free block for the new entry: nothing changed
408413 }
409414 dirset(dp1, off1, 0); // old disappears
415
416 if (twodirs && type1 == T_DIR) {
417 // ip's ".." must name its new parent, and the link that ".."
418 // is moves from dp1 to dp2.
419 ilock(ip);
420 if ((pp = dirlookup(ip, "..", &off)) != dp1)
421 panic("rename: ..");
422 iput(pp);
423 dirset(ip, off, dp2->inum);
424 iunlock(ip);
425 dp1->nlink--;
426 iupdate(dp1);
427 dp2->nlink++;
428 iupdate(dp2);
429 }
410430 r = 0;
411431
412432unlock:
413433 iunlock(dp1);
3e0347c Add mv, a user command for rename
Makefile
@@ -138,8 +138,9 @@ UPROGS=\
138138 $U/_kill\
139139 $U/_ln\
140140 $U/_ls\
141141 $U/_mkdir\
142 $U/_mv\
142143 $U/_rm\
143144 $U/_sh\
144145 $U/_stressfs\
145146 $U/_usertests\
user/mv.c
@@ -0,0 +1,38 @@
1#include "kernel/types.h"
2#include "kernel/stat.h"
3#include "user/user.h"
4
5// mv old new: give old the name new. If new is an existing
6// directory, move old into it under its own last name.
7int
8main(int argc, char *argv[])
9{
10 char buf[128], *new, *base, *p;
11 struct stat st;
12
13 if (argc != 3) {
14 fprintf(2, "Usage: mv old new\n");
15 exit(1);
16 }
17 new = argv[2];
18 if (stat(new, &st) == 0 && st.type == T_DIR) {
19 base = argv[1];
20 for (p = argv[1]; *p; p++)
21 if (*p == '/' && p[1] != '\0')
22 base = p + 1;
23 if (strlen(new) + 1 + strlen(base) + 1 > sizeof(buf)) {
24 fprintf(2, "mv: path too long\n");
25 exit(1);
26 }
27 strcpy(buf, new);
28 p = buf + strlen(buf);
29 *p++ = '/';
30 strcpy(p, base);
31 new = buf;
32 }
33 if (rename(argv[1], new) < 0) {
34 fprintf(2, "mv %s %s: failed\n", argv[1], new);
35 exit(1);
36 }
37 exit(0);
38}
521d3aa Add renametest
Makefile
@@ -150,8 +150,9 @@ UPROGS=\
150150 $U/_logstress\
151151 $U/_forphan\
152152 $U/_dorphan\
153153 $U/_sync\
154 $U/_renametest\
154155
155156fs.img: mkfs/mkfs README $(UPROGS)
156157 mkfs/mkfs fs.img README $(UPROGS)
157158
user/renametest.c
@@ -0,0 +1,425 @@
1// renametest: tests for rename().
2//
3// renametest functional tests, then seven processes renaming
4// between two directories at once on all harts.
5// renametest concurrent N only the concurrent test, N rounds.
6// renametest crash renames back and forth until the machine is
7// killed; renametest check, after a reboot, says
8// whether every rename happened completely or not
9// at all. A driver outside xv6 must do the killing.
10
11#include "kernel/types.h"
12#include "kernel/stat.h"
13#include "kernel/fcntl.h"
14#include "kernel/fs.h"
15#include "user/user.h"
16
17static int failures;
18
19static void
20writefile(char *path, char *s)
21{
22 int fd = open(path, O_CREATE | O_WRONLY | O_TRUNC);
23 if (fd < 0 || write(fd, s, strlen(s)) != strlen(s)) {
24 printf("renametest: cannot write %s\n", path);
25 exit(1);
26 }
27 close(fd);
28}
29
30// Does the file hold exactly s?
31static int
32holds(char *path, char *s)
33{
34 char buf[64];
35 int fd, n;
36
37 if ((fd = open(path, O_RDONLY)) < 0)
38 return 0;
39 n = read(fd, buf, sizeof(buf));
40 close(fd);
41 return n == strlen(s) && memcmp(buf, s, n) == 0;
42}
43
44static int
45exists(char *path)
46{
47 struct stat st;
48 return stat(path, &st) == 0;
49}
50
51static uint
52ino(char *path)
53{
54 struct stat st;
55 if (stat(path, &st) < 0)
56 return 0;
57 return st.ino;
58}
59
60static int
61nlink(char *path)
62{
63 struct stat st;
64 if (stat(path, &st) < 0)
65 return -1;
66 return st.nlink;
67}
68
69// Record one check; print the first failure of each test.
70static int bad;
71static void
72expect(int ok, char *what)
73{
74 if (!ok && bad++ == 0)
75 printf("renametest: failed: %s\n", what);
76}
77
78static void
79result(char *test)
80{
81 printf("renametest: %s: %s\n", test, bad ? "FAIL" : "OK");
82 failures += bad != 0;
83 bad = 0;
84}
85
86// Remove path and everything under it.
87static void
88rmrf(char *path)
89{
90 char buf[128], *p;
91 struct dirent de;
92 struct stat st;
93 int fd;
94
95 if (stat(path, &st) < 0)
96 return;
97 if (st.type == T_DIR && (fd = open(path, O_RDONLY)) >= 0) {
98 strcpy(buf, path);
99 p = buf + strlen(buf);
100 *p++ = '/';
101 while (read(fd, &de, sizeof(de)) == sizeof(de)) {
102 if (de.inum == 0 || strcmp(de.name, ".") == 0 ||
103 strcmp(de.name, "..") == 0)
104 continue;
105 memmove(p, de.name, DIRSIZ);
106 p[DIRSIZ] = 0;
107 rmrf(buf);
108 }
109 close(fd);
110 }
111 unlink(path);
112}
113
114static void
115samedir(void)
116{
117 uint i;
118
119 writefile("rt/f1", "one");
120 i = ino("rt/f1");
121 expect(rename("rt/f1", "rt/f2") == 0, "rename rt/f1 rt/f2");
122 expect(!exists("rt/f1"), "rt/f1 still exists");
123 expect(ino("rt/f2") == i, "rt/f2 is not the same inode");
124 expect(nlink("rt/f2") == 1, "rt/f2 nlink is not 1");
125 expect(holds("rt/f2", "one"), "rt/f2 lost its content");
126 result("same directory");
127}
128
129static void
130crossdir(void)
131{
132 uint i = ino("rt/f2");
133
134 mkdir("rt/a");
135 mkdir("rt/a/b");
136 // down: the old parent is above the new one
137 expect(rename("rt/f2", "rt/a/b/f") == 0, "rename rt/f2 rt/a/b/f");
138 // sideways: unrelated parents
139 mkdir("rt/c");
140 expect(rename("rt/a/b/f", "rt/c/f") == 0, "rename rt/a/b/f rt/c/f");
141 // up: the new parent is above the old one
142 expect(rename("rt/c/f", "rt/f3") == 0, "rename rt/c/f rt/f3");
143 expect(!exists("rt/f2") && !exists("rt/a/b/f") && !exists("rt/c/f"),
144 "an old name still exists");
145 expect(ino("rt/f3") == i && nlink("rt/f3") == 1, "rt/f3 inode or nlink");
146 expect(holds("rt/f3", "one"), "rt/f3 lost its content");
147 result("across directories");
148}
149
150static void
151replace(void)
152{
153 struct stat st;
154 char buf[8];
155 uint i;
156 int fd;
157
158 writefile("rt/new", "new");
159 writefile("rt/old", "old!");
160 i = ino("rt/new");
161 fd = open("rt/old", O_RDONLY); // keeps the replaced file alive
162 expect(rename("rt/new", "rt/old") == 0, "rename rt/new rt/old");
163 expect(!exists("rt/new"), "rt/new still exists");
164 expect(ino("rt/old") == i && holds("rt/old", "new"), "rt/old is not new");
165 expect(fstat(fd, &st) == 0 && st.nlink == 0, "replaced file nlink not 0");
166 expect(read(fd, buf, 4) == 4 && memcmp(buf, "old!", 4) == 0,
167 "replaced file unreadable while open");
168 close(fd); // its last reference: the kernel frees it now
169
170 // two names for one file: rename does nothing, successfully
171 link("rt/old", "rt/h");
172 expect(rename("rt/old", "rt/h") == 0, "rename of a file onto itself");
173 expect(exists("rt/old") && exists("rt/h") && nlink("rt/h") == 2,
174 "hard links changed");
175 unlink("rt/h");
176 result("replace a file");
177}
178
179static void
180movedir(void)
181{
182 int na, nc, nd;
183
184 mkdir("rt/a/d");
185 mkdir("rt/a/d/e");
186 na = nlink("rt/a"); // 1 + subdirectories b and d
187 nc = nlink("rt/c");
188 nd = nlink("rt/a/d");
189 expect(rename("rt/a/d", "rt/c/d") == 0, "rename rt/a/d rt/c/d");
190 expect(!exists("rt/a/d") && exists("rt/c/d/e"), "the subtree did not move");
191 expect(ino("rt/c/d/..") == ino("rt/c"), "rt/c/d/.. is not rt/c");
192 expect(ino("rt/c/d/e/..") == ino("rt/c/d"), "rt/c/d/e/.. is wrong");
193 expect(nlink("rt/a") == na - 1, "old parent nlink");
194 expect(nlink("rt/c") == nc + 1, "new parent nlink");
195 expect(nlink("rt/c/d") == nd, "moved directory nlink");
196 // within one directory nothing but the name changes
197 expect(rename("rt/c/d", "rt/c/d2") == 0, "rename rt/c/d rt/c/d2");
198 expect(ino("rt/c/d2/..") == ino("rt/c") && nlink("rt/c") == nc + 1,
199 "rename within rt/c changed .. or nlink");
200 result("move a directory");
201}
202
203static void
204cycle(void)
205{
206 int nc = nlink("rt/c");
207
208 expect(rename("rt/c", "rt/c/x") < 0, "moved rt/c into itself");
209 expect(rename("rt/c", "rt/c/d2/e/x") < 0, "moved rt/c below itself");
210 expect(rename("rt", "rt/a/b/x") < 0, "moved rt below itself");
211 expect(exists("rt/c/d2/e") && nlink("rt/c") == nc, "rt/c changed");
212 result("refuse a cycle");
213}
214
215static void
216refusals(void)
217{
218 writefile("rt/g", "g");
219 expect(rename("rt/c/.", "rt/x") < 0, "renamed rt/c/.");
220 expect(rename("rt/c/..", "rt/x") < 0, "renamed rt/c/..");
221 expect(rename("rt/g", "rt/c/..") < 0, "renamed onto rt/c/..");
222 expect(rename("rt/g", "rt/c") < 0, "replaced a directory");
223 expect(rename("rt/c", "rt/g") < 0, "replaced a file with a directory");
224 expect(rename("rt/nothere", "rt/x") < 0, "renamed a missing file");
225 expect(rename("/", "rt/x") < 0, "renamed /");
226 expect(rename("rt/g", "rt/nothere/x") < 0, "renamed into a missing dir");
227 expect(holds("rt/g", "g") && exists("rt/c/d2") && !exists("rt/x"),
228 "a refused rename changed something");
229 result("refusals");
230}
231
232static int rounds = 200;
233
234// Seven processes on three harts. Two rename files between ct/a
235// and ct/b in opposite directions; one renames between ct/a and
236// its subdirectory ct/a/s; one moves the directory m between
237// ct/a and ct/b, and each time also tries to move m's current
238// parent into m, which must fail. Those four do a fixed number of
239// rounds. Until they finish, one process keeps trying to unlink
240// ct/a/s (which must fail: it is not empty), and two churn names
241// in ct/a and ct/b (create, rename onto an existing file, rename
242// away, unlink), so that names change under the other renames.
243static void
244concurrent(void)
245{
246 static char *moves[3][2] = {
247 {"ct/a/x", "ct/b/y"},
248 {"ct/b/z", "ct/a/w"},
249 {"ct/a/s/q", "ct/a/q"},
250 };
251 int i, j, pid, xs, watchdog, t0, done, ok;
252
253 rmrf("ct");
254 mkdir("ct");
255 mkdir("ct/s");
256 mkdir("ct/a");
257 mkdir("ct/b");
258 rename("ct/s", "ct/a/s");
259 writefile("ct/a/x", "x");
260 writefile("ct/b/z", "z");
261 writefile("ct/a/s/q", "q");
262 writefile("ct/a/s/keep", "keep");
263 mkdir("ct/a/m");
264 expect(ino("ct/a/s") < ino("ct/a"), "setup: ct/a/s numbered after ct/a");
265
266 t0 = uptime();
267
268 watchdog = fork();
269 if (watchdog == 0) {
270 pause(3 * rounds); // 60 seconds for the usual 200 rounds
271 printf("renametest: concurrent: not finished after %d seconds\n",
272 3 * rounds / 10);
273 exit(0);
274 }
275 for (i = 0; i < 7; i++) {
276 if (fork() == 0) {
277 int nbad = 0;
278 if (i < 3) {
279 for (j = 0; j < rounds; j++) {
280 nbad += rename(moves[i][0], moves[i][1]) < 0;
281 nbad += rename(moves[i][1], moves[i][0]) < 0;
282 }
283 } else if (i == 3) {
284 for (j = 0; j < rounds; j++) {
285 nbad += rename("ct/a/m", "ct/b/m") < 0;
286 nbad += rename("ct/b", "ct/b/m/x") == 0; // a cycle
287 nbad += rename("ct/b/m", "ct/a/m") < 0;
288 nbad += rename("ct/a", "ct/a/m/x") == 0; // a cycle
289 }
290 } else if (i == 4) {
291 while (!exists("ct/stop"))
292 nbad += unlink("ct/a/s") == 0;
293 } else {
294 // churners: their own renames may fail when the other
295 // churner got there first; only the totals are checked
296 while (!exists("ct/stop")) {
297 if (i == 5) {
298 close(open("ct/a/t", O_CREATE | O_WRONLY));
299 rename("ct/a/t", "ct/b/t");
300 } else {
301 rename("ct/b/t", "ct/a/u");
302 unlink("ct/a/u");
303 }
304 }
305 }
306 exit(nbad);
307 }
308 }
309 for (done = 0; done < 7;) {
310 pid = wait(&xs);
311 if (pid == watchdog) {
312 watchdog = -1;
313 continue;
314 }
315 expect(xs == 0, "a worker's rename or unlink did the wrong thing");
316 if (++done == 4)
317 writefile("ct/stop", ""); // the fixed-round workers are done
318 }
319 if (watchdog > 0) {
320 kill(watchdog);
321 wait(0);
322 }
323 expect(exists("ct/a/x") && exists("ct/b/z") && exists("ct/a/s/q") &&
324 exists("ct/a/m"),
325 "a file or directory is missing");
326 expect(!exists("ct/b/y") && !exists("ct/a/w") && !exists("ct/a/q") &&
327 !exists("ct/b/m"),
328 "a file or directory has two names");
329 // link counts: ct holds a and b, ct/a holds s and m, ct/b none
330 expect(nlink("ct/a") == 3 && nlink("ct/b") == 1 && nlink("ct") == 3,
331 "a directory's link count is wrong");
332 expect(ino("ct/a/m/..") == ino("ct/a"), "ct/a/m/.. is not ct/a");
333 ok = nlink("ct/a/x") == 1 && nlink("ct/b/z") == 1 && nlink("ct/a/s/q") == 1;
334 expect(ok && (!exists("ct/b/t") || nlink("ct/b/t") == 1) &&
335 (!exists("ct/a/t") || nlink("ct/a/t") == 1),
336 "a file's link count is wrong");
337 printf("renametest: concurrent: %d renames, %d refused cycles in %d ticks\n",
338 8 * rounds, 2 * rounds, uptime() - t0);
339 result("concurrent");
340 rmrf("ct");
341}
342
343// Crash mode: f is a file and d a directory, each in cr/a or
344// cr/b; each round moves both to the other directory.
345static void
346crash(void)
347{
348 char *fa = "cr/a/f", *fb = "cr/b/f", *da = "cr/a/d", *db = "cr/b/d";
349 int n, fin, din;
350
351 if (!exists("cr")) {
352 mkdir("cr");
353 mkdir("cr/a");
354 mkdir("cr/b");
355 writefile(fa, "crash");
356 mkdir(da);
357 }
358 fin = exists(fa); // is f in cr/a?
359 din = exists(da);
360 printf("renametest: crash: renaming until killed\n");
361 for (n = 1;; n++) {
362 if (rename(fin ? fa : fb, fin ? fb : fa) < 0)
363 printf("renametest: crash: cannot move f\n");
364 fin = !fin;
365 if (rename(din ? da : db, din ? db : da) < 0)
366 printf("renametest: crash: cannot move d\n");
367 din = !din;
368 if (n % 50 == 0)
369 printf("renametest: crash: %d rounds\n", n);
370 }
371}
372
373static void
374check(void)
375{
376 int fa = exists("cr/a/f"), fb = exists("cr/b/f");
377 int da = exists("cr/a/d"), db = exists("cr/b/d");
378 char *f = fa ? "cr/a/f" : "cr/b/f";
379
380 expect(fa + fb == 1, "f has not exactly one name");
381 expect(da + db == 1, "d has not exactly one name");
382 expect(nlink(f) == 1 && holds(f, "crash"), "f nlink or content");
383 expect(ino(da ? "cr/a/d/.." : "cr/b/d/..") == ino(da ? "cr/a" : "cr/b"),
384 "d's .. is not its parent");
385 expect(nlink("cr/a") == 1 + da && nlink("cr/b") == 1 + db,
386 "parent nlink does not match where d is");
387 printf("renametest: check: f in cr/%s (%d name%s), d in cr/%s (%d name%s)\n",
388 fa ? "a" : "b", fa + fb, fa + fb == 1 ? "" : "s", da ? "a" : "b",
389 da + db, da + db == 1 ? "" : "s");
390 result("check");
391}
392
393int
394main(int argc, char *argv[])
395{
396 if (argc == 2 && strcmp(argv[1], "crash") == 0)
397 crash();
398 if (argc == 3 && strcmp(argv[1], "concurrent") == 0) {
399 rounds = atoi(argv[2]);
400 concurrent();
401 exit(failures);
402 }
403 if (argc == 2 && strcmp(argv[1], "check") == 0) {
404 check();
405 exit(failures);
406 }
407 rmrf("rt");
408 if (mkdir("rt") < 0) {
409 printf("renametest: mkdir rt failed\n");
410 exit(1);
411 }
412 samedir();
413 crossdir();
414 replace();
415 movedir();
416 cycle();
417 refusals();
418 concurrent();
419 rmrf("rt");
420 if (failures)
421 printf("renametest: SOME TESTS FAILED\n");
422 else
423 printf("renametest: ALL OK (crash consistency: see renametest crash)\n");
424 exit(failures);
425}

6. Verify and measure

On the branch (ext/24-rename, 6 commits), built with the project toolchain and run on 3 harts (-smp 3 -m 128M), in one boot:

$ renametest
renametest: same directory: OK
renametest: across directories: OK
renametest: replace a file: OK
renametest: move a directory: OK
renametest: refuse a cycle: OK
renametest: refusals: OK
renametest: concurrent: 1600 renames, 400 refused cycles in 110 ticks
renametest: concurrent: OK
renametest: ALL OK (crash consistency: see renametest crash)
$ usertests -q
usertests starting
test copyin: OK
[...]
test unlinkcwd: OK
ALL TESTS PASSED
$ renametest
[...]
renametest: concurrent: 1600 renames, 400 refused cycles in 121 ticks
renametest: concurrent: OK
renametest: ALL OK (crash consistency: see renametest crash)
$ renametest concurrent 1000
renametest: concurrent: 8000 renames, 2000 refused cycles in 471 ticks
renametest: concurrent: OK

The host checker on that disk image afterwards: fsck: 29 inodes in use, 29 reachable, 1072 data blocks; clean. usertests -q also passed at each of commits 1 to 5 (commit 6 only adds the test program), so every intermediate state of the branch is a working kernel.

Crash consistency, 30 runs of: fresh disk image, renametest crash, SIGKILL to QEMU after a random 0.2 to 4 seconds, reboot on the same image, renametest check, then the host checker. Three of the 30 summary lines, as the driver wrote them:

run 1 delay 0.3 last=[] recovered_blocks=4 renametest: check: f in cr/b (1 name), d in cr/b (1 name) renametest: check: OK  | fsck: 30 inodes in use, 30 reachable, 1074 data blocks; clean
run 2 delay 3.28 last=[] recovered_blocks=0 renametest: check: f in cr/a (1 name), d in cr/b (1 name) renametest: check: OK  | fsck: 30 inodes in use, 30 reachable, 1074 data blocks; clean
run 4 delay 2.71 last=[] recovered_blocks=4 renametest: check: f in cr/a (1 name), d in cr/a (1 name) renametest: check: OK  | fsck: 30 inodes in use, 30 reachable, 1074 data blocks; clean

All 30 checks printed OK and all 30 images were clean. recovered_blocks counts the recovering tail lines at boot: 14 of the 30 kills landed after a rename’s commit record and before the log was cleared, and the reboot finished that rename (3 blocks for a file move, 4 for a directory move); the other 16 found an empty log. The two gdb-controlled kills of the reveal (just before and just after write_head) gave the old state and the new state respectively, each with exactly one name.

What this shows: the rename is all-or-nothing on disk; the .. entry and both link counts always agree with where the directory is, also after concurrent directory moves and refused cycles; nothing that usertests exercises changed; and seven processes on three harts finish. What it does not show: renametest’s concurrent part would not have caught the naive or the inode-number order without help (clinics 1 and 2). The argument that the reference cannot deadlock is the lock order, not the test.

Blocks per rename. A copy of the kernel printed log.lh.n and the logged block numbers at each rename’s end_op, with a scratch program (not on the branch) that sets up each case:

rename	dp1, dp2, moved inode	blocks logged	which
file, same directory	27, 27, 30	2	1157 (`m` data), 34 (inodes 16 to 31)
file, `m` → `m/a`	27, 31, 30	3	1160, 34, 1157
file replacing a 3-block file, `m/a` → `m/b`	31, 32, 30 (replaced: 33)	5	1161, 35, 1160, 34, 46 (bitmap)
directory, `m/a` → `m/b`	31, 32, 33	5	1161, 35, 1160, 34, 1162 (its `..`)
directory into a parent with one full block	32, 34, 33	5	46, 1164 (new block), 35, 1161, 1162
directory into a parent with 12 full blocks, inodes in 3 inode blocks	51, 85, 68	8	46, 1179 (indirect), 1180 (new block), 38, 1165, 36, 1166, 37

In this image the inode blocks start at block 33 (16 inodes each) and the bitmap is block 46. The worst case is 8 of the 10 blocks begin_op reserves. The replaced file’s three data blocks cost one block (46): freeing clears bits in the bitmap.

What a split transaction costs. The same 30-kill crash test against clinic 4’s kernel (new entry committed, then the old one removed in a second transaction): 17 of 30 checks failed, every time with one inode under two names and a link count of 1 (f in cr/a (2 names) or d in cr/a (2 names)); the host checker flagged each of those 17 images (1 to 3 problems: a wrong link count, a directory reached twice, a wrong ..). The single transaction: 0 of 30.

Deadlocks found (all on 3 harts, final renametest):

kernel	runs	deadlocked
naive order	4 × `concurrent 1000`	0
naive order, delay after the first lock	6 × `concurrent 1000`	4 (2 file mover vs file mover, 2 file mover vs directory mover)
inode-number order	4 × `concurrent 1000`	0
inode-number order, delay after the first lock	2 × `renametest`, 4 × `concurrent 1000`	2 (rename vs unlink, both in `concurrent 1000`)
reference, delay after the first lock	2 × `concurrent 1000`	0

Time. The 200-round concurrent part (1600 renames, 400 refused cycles) took 110 and 121 ticks in the two verify runs, and renametest concurrent 1000 471 ticks; across the other runs above, concurrent 1000 took between 371 and 790 ticks (measured while the computer was busy with other work; your times will differ). These numbers vary too much to compare the lock orders by speed; correctness is the point here.

7. Go further

Replace an empty directory. POSIX allows rename(dir1, dir2) when dir2 is an empty directory. You must lock dir2 (a child of the new parent) and check it is empty under its lock, as sys_unlink does, and nlink bookkeeping now involves four inodes. It also teaches why isdirempty must be checked with the lock held.
Atomic replace for applications. Write a small “save” program: write a new file x.tmp, then rename("x.tmp", "x"). Kill QEMU at random moments and show that x is always the complete old or the complete new content. This is how real editors save. (Which ordering guarantee does xv6’s log give between the data writes and the rename?)
A finer lock. renamelock serializes all two-directory renames in the file system. Measure how often concurrent waits for it (count sleeps in acquiresleep on it), then think about what a per-subtree scheme would need, and why Linux kept a single per-file-system mutex.
Lockdep for sleep-locks. Lab 21’s lock-order checker records orders between inode sleep-locks too. Combine it with this lab, run renametest concurrent with the naive order, and see it report the cycle before the deadlock happens.
An in-kernel fsck. Port the host checker’s ideas into a boot-time check that walks from the root and reports unreachable inodes and wrong link counts, like ireclaim but for more than nlink == 0.

1. The spec

2. Think first

1Why does rename need the kernel at all?

The reference design

Check yourself

2What has to change on disk, and in which order?

The reference design

Check yourself

3Two directories, two locks. In what order?

The reference design

Check yourself

4Which directory is above which?

The reference design

Check yourself

5Moving a directory into itself

The reference design

Check yourself

6What else moves with a directory?

The reference design

Check yourself

7Does one rename fit in one transaction?

The reference design

Check yourself

3. Build it

4. Debugging clinic

1The naive order, old parent then new parent

What happened when we ran it

2Inode-number order instead of the tree

What happened when we ran it

3No cycle check

What happened when we ran it

4Two transactions, to make the new name durable first

What happened when we ran it

5Forgetting to fix ..

What happened when we ran it

5. The reference solution

Or read the commits

6. Verify and measure

7. Go further

5Forgetting to fix `..`