Lab 24 · reveal · 16 steps · 6 commits
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.
Each step shows one change on the branch ext/24-rename, the code around it, and the state of the machine when that code runs.
sp = 0x3fffff9e40 in the recorded runkernel/sysfile.cStep 1 of 16 · commit 1: Add a rename system call that refuses everything
The story of this tour was recorded on three harts with gdb attached to the finished
branch: at a fresh shell you type mkdir a, mkdir b, mkdir a/d, echo hi > a/x,
then mv a/x a/y (pid 7), mv a/y b/y (pid 8), echo old > b/t, mv b/y b/t
(pid 10), mv a/d b (pid 11), mv b b/d/e (pid 12, refused) and mv b/d a (pid 13).
In this image a is inode 26, b 27, a/d 28, x 29 and t 30. Later steps add
renametest’s crash runs.
Commit 1 is the plumbing, the same five places as any new system call
(Tour 5: Life of a system call): SYS_rename is 23 in kernel/syscall.h, the table in
kernel/syscall.c gets [SYS_rename] = sys_rename, user/usys.pl emits the
li a7, SYS_rename; ecall stub, and user/user.h declares
int rename(const char *, const char *).
The handler fetches both paths with argstr, which copies them from user memory
into kernel arrays of MAXPATH bytes, and fails. Two paths cost 256 bytes of
kernel stack, out of 4096.
The state is pid 7’s, recorded at the start of sys_rename on the finished branch:
hart 0, no lock held, interrupts on (as for every system call after usertrap's
intr_on), noff 0.
a's inode lock (inode 26, sleep-lock)kernel/fs.cStep 2 of 16 · commit 2: Rename within one directory
Commit 2 adds one helper next to dirlink. dirset(dp, off, inum) reads the entry
at byte offset off, changes its inode number, and writes it back: inode 0 frees the
entry (zeroing the name too, exactly as sys_unlink does,
kernel/sysfile.c:235-kernel/sysfile.c:237); any other number makes the same
name refer to another inode.
Compare it with dirlink just above. dirlink looks for a free slot and may
extend the directory, which can need a new block and fail. dirset only touches an
entry that exists, inside the directory’s size, so writei's bmap finds a
block already allocated: it cannot run out of space, and a short write is a kernel
bug, hence panic. That difference decides the order of the rename’s steps.
The caller holds the directory’s lock, as readi and writei require. In the
recorded mv a/x a/y, pid 7 held a (inode 26) when it cleared the old entry at
offset 48: x was the fourth entry, after ., .. and d. Holding a sleep-lock
does not turn interrupts off: noff stayed 0 and SIE 1 (Locks and interrupt state).
a's inode lock (inode 26, sleep-lock)kernel/sysfile.cStep 3 of 16 · commit 2: Rename within one directory
The whole body is one transaction: begin_op on line 291, end_op at the end.
Inside, nameiparent resolves both paths to their parent directories and last
names. Line 295 refuses . and .. as either last name, as sys_unlink does
(kernel/sysfile.c:221): renaming a/. would mean locking a twice. Line 297
refuses two directories for now.
Line 300 locks the directory, and the rest of this step happens under that one lock,
so no other process can see a moment where x is gone and y is not there yet.
dirlookup finds x and its offset (off1), and y if it exists (off2).
Both come back referenced but unlocked.tp == ip: the two names already lead to the same inode (mv a/x a/x, or two hard
links). POSIX says do nothing and succeed. Without this test, the code below would
point y’s entry at the same inode, drop its link count by one and then clear x:
one name and an nlink one too low.itype takes it alone for a moment. That is parent
before child, and the type cannot change while the rename holds a reference.For mv a/x a/y, gdb recorded pid 7 on hart 0 here with a’s lock and nothing else;
x is inode 29, y did not exist (tp 0).
b's inode lock (inode 27, sleep-lock)t's inode lock (inode 30, sleep-lock)Step 4 of 16 · commit 2: Rename within one directory
The scene is mv b/y b/t (pid 10, on hart 2): t exists, a file containing old.
Its entry, at offset 48 of b, is pointed at y’s inode (29) with dirset, and the
file that was t (inode 30) loses a link. That needs t’s lock, taken after b’s:
parent, then child, the order of sys_unlink. gdb saw exactly these two
sleep-locks held by pid 10.
If t had not existed, dirlink (line 318) would have added the entry. It is the
only step that can fail (a new block for the directory), so it comes first; on
failure nothing has been changed. Then line 321 clears y’s old entry, which cannot
fail.
Notice what is not here: no write to inode 29. A rename takes one name away and
gives one, so the moved inode’s nlink stays as it was.
Line 328 is where the replaced file dies. t has nlink 0 now and nobody has it
open, so this iput frees its block and its inode, still inside the transaction,
before end_op. At end_op gdb read log.lh.n = 3 for this rename; by our
count they are b’s data block, the inode block holding inodes 16 to 31 (b, y,
t), and the bitmap block, for t’s freed data block.
stack0hart 0’s slice of stack0kernel/sysfile.cStep 5 of 16 · commit 3: Rename across directories: a rename lock, ancestor first
Commit 3 allows two different parent directories, and the first thing it needs is a
way to order two directory locks that the tree does not order (think question 3).
renamelock is one sleep-lock for the whole file system, taken by every rename
between two directories before it looks at the tree and held to the end. Linux has the
same thing, s_vfs_rename_mutex.
It is a sleep-lock because its holder reads directories from disk while holding it:
the lookups, and the walk two steps from now. A spinlock would forbid that (sched
panics with sched locks).
main calls renameinit on hart 0 right after fileinit, one new line in
main.c, with interrupts still off and the other harts waiting for started.
initsleeplock only fills in the fields; nothing is shared yet.
Its place in the lock order: after begin_op, before every inode lock. 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). It is safe there because nobody holding an inode lock waits for it, 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; the cost of this
order is that a rename waiting for the lock already holds one of the log’s three
reservations.)
renamelock (sleep-lock)b's inode lock (inode 27, sleep-lock)kernel/sysfile.cStep 6 of 16 · commit 3: Rename across directories: a rename lock, ancestor first
isancestor(a, b): is directory a the same as b, or above it? xv6 keeps no
parent pointers in memory, so the only way to know is to read .. entries from b
up to the root, as namex does for a path with .. in it.
The rules this function follows are the ones that make it safe:
.., and line 335 unlocks it before the next one is locked. Locking a parent
while holding a child is the reverse of the file system’s order.renamelock is held, so no directory can move during the walk, and the answer
is still true when the rename uses it.nlink 0 has been removed; its .. may point at an inode that has
since been freed and reused. The walk stops and says no; the rename then fails at
its re-checks under the locks (samename, or dp2->nlink == 0).The comparison ip != a is between in-memory inode pointers: one inode has one
table entry while anyone holds a reference, and the caller holds references to both.
Recorded: mv a/d b (pid 11, hart 2) inside a walk, holding renamelock and only b
(inode 27). This walk is commit 4’s cycle check, “is d above b?”: b’s .. leads
to the root, so no. Its second walk, for the lock order (“is b above a?”), locked
only a. noff 0, SIE 1 throughout.
renamelock (sleep-lock)kernel/sysfile.cStep 7 of 16 · commit 3: Rename across directories: a rename lock, ancestor first
The new shape of sys_rename. Everything that depends on the shape of the tree is
decided before any parent is held, because deciding it needs walks that may hold no
inode lock.
twodirs is decided by pointer: nameiparent returns referenced inodes, and the
same directory always comes back as the same table entry. Only then is renamelock
taken (line 365), so renames within one directory never wait for it.
lookup locks a directory, finds the name, and unlocks; itype locks the found
inode alone. So the code never holds a directory and a child, or two children, at this
stage. The results are references, not locks: they guarantee the inodes cannot be
freed, not that the names still lead to them a moment later.
Line 380 keeps directories out for one more commit.
gdb, mv a/y b/y (pid 8, hart 0), inside the first lookup: renamelock is held by
pid 8, log.outstanding is 1 (this rename’s transaction), and no inode lock yet.
renamelock (sleep-lock)a's inode lock (inode 26, sleep-lock)b's inode lock (inode 27, sleep-lock)Step 8 of 16 · commit 3: Rename across directories: a rename lock, ancestor first
The heart of the lab, in eight lines. If the new parent dp2 is above the old parent
dp1, lock it first; otherwise lock dp1 first. Three cases:
| parents | order | why it cannot deadlock |
|---|---|---|
dp1 above dp2 (a → a/b) |
dp1, dp2 |
parent before child, like sys_unlink |
dp2 above dp1 (a/b → a) |
dp2, dp1 |
the same rule |
unrelated (a → b) |
dp1, dp2 |
only one two-directory rename at a time holds two unrelated directories |
The naive “always dp1 first” differs only in the second row, and that row is the
one that collides with sys_unlink (clinic 1); the unrelated row collides with
another rename going the other way, which renamelock now excludes.
Recorded for mv a/y b/y: pid 8 holds renamelock, a (26) and b (27), all
sleep-locks; noff 0. For mv b/d a (pid 13), the unrelated case again, the walk
isancestor(a, b) locked only b, whose .. is the root, so the answer was no and
the order was dp1 first: b, then a.
renamelock (sleep-lock)a's inode lock (inode 26, sleep-lock)b's inode lock (inode 27, sleep-lock)Step 9 of 16 · commit 3: Rename across directories: a rename lock, ancestor first
The lookups were made with each directory locked for a moment. Since then another
process may have unlinked a/y, renamed it within a, or created b/y; none of
those take renamelock. So with both parents locked, samename looks both names up
again and compares with the inodes the decisions were made about. Any difference: -1,
nothing changed. The comparison is safe because the rename holds references to ip
and tp, so neither inode can be freed and its number reused for something else.
The same lines check that dp2 still has links: a directory removed after
nameiparent returned it must not receive an entry (the same guard as
create and sys_link, kernel/sysfile.c:161).
From here the code is commit 2’s, with dp2 in place of dp1 for the new name.
The cleanup at out releases renamelock after the parents are unlocked, and the
iput of a replaced file still comes before end_op.
Recorded: mv a/y b/y, pid 8 in samename with renamelock, a and b. At its
end_op, log.lh.n was 3: by our count b’s data block, the inode block of a
and b, and a’s data block.
renamelock (sleep-lock)b/d's inode lock (inode 28, sleep-lock)kernel/sysfile.cStep 10 of 16 · commit 4: Move directories between parents
Commit 4 lets directories move between parents. The first condition: the directory
being moved (ip) must not be the new parent or above it. The walk is the one commit
3 wrote for the lock order, and it runs at the same point, before any parent is
locked.
mv b b/d/e (pid 12): ip is b (27), dp2 is b/d (28). gdb stopped in the walk
with renamelock and b/d locked: the next .. is b, which is ip, so the
answer is yes and the rename returns -1 (mv b b/d/e: failed on the console). It
logged 0 blocks.
Without this line, clinic 3: mv a a/c/b detaches a and everything below it into
a loop that no path reaches and no link count ever releases, and mv a a/b locks a
twice and sleeps on itself.
Why renamelock is essential here, and not just for the lock order: rename(a, b/a2)
and rename(b, a/b2) could each pass this check if they ran at the same time, and
together build the loop. With the lock, the second sees the first’s result.
renamelock (sleep-lock)a's inode lock (inode 26, sleep-lock)b's inode lock (inode 27, sleep-lock)Step 11 of 16 · commit 4: Move directories between parents
A moved directory’s .. will add one to the new parent’s link count, and nlink is
a short: create already refuses a new subdirectory when the parent is at
NLINK_MAX (kernel/sysfile.c:274-kernel/sysfile.c:278). The same guard, at
the same moment: under the parent’s lock, before anything is written.
mv a/d b (pid 11) passed it with b at nlink 1. gdb recorded pid 11 here holding
renamelock, a (26) and b (27), and then at dirlink adding d to b; the
old entry was cleared at offset 32 of a.
renamelock (sleep-lock)a's inode lock (inode 26, sleep-lock)b's inode lock (inode 27, sleep-lock)d's inode lock (inode 28, sleep-lock)Step 12 of 16 · commit 4: Move directories between parents
The entries have moved; now the directory’s own bookkeeping. d’s .. names a,
and that entry is one of a’s links (a directory’s nlink is its entry in its
parent plus its subdirectories’ ..). Both must move to b.
Line 419 locks d, after both parents. Anyone holding d waits only for d’s
descendants, and after the cycle check neither parent is below d; that d and b
may be unrelated is safe because of renamelock. dirlookup finds
.. (offset 16: the second entry, as create wrote it) and the sanity check makes
sure it names the old parent; dirset points it at b. Then a loses a link and b
gains one.
This is the most locks one rename holds: gdb saw pid 11 with four sleep-locks and the
log already holding 3 blocks of this transaction (b’s and a’s data blocks and
their shared inode block). The .. write adds d’s first block: 4 at end_op,
within the 10 of kernel/param.h:9. Think question 7 has the worst case, 8.
Counted the way Tour 51: The lock-order graph, measured counts (buffer sleep-locks included), this rename reaches
five sleep-locks at once: renamelock, a, b, d, and d’s buffer inside
dirset’s writei. (The worst-case dirlink reaches five too: renamelock, both
parents, the indirect block’s buffer and the bitmap’s.) Tour 51’s measured workload
never held more than three in one process, four only with a program built to force
it. Every pair in this chain is ordered: by the tree, by renamelock, or inode before
buffer.
Step 13 of 16 · commit 4: Move directories between parents
Nothing in log.c changes; this is why the rename is atomic. Every block the rename
wrote sits pinned in the buffer cache, listed in log.lh. At end_op, with no other
operation outstanding, commit copies them into the log (write_log), writes the
header with their count (write_head, line 207), copies them home, and clears the
header. The header write is the one moment the rename happens on disk.
We crashed the reference on both sides of it. QEMU halted under gdb, renametest crash
(pid 3), break sys_rename, then a breakpoint in commit, and gdb’s kill on the
first hit, with log.lh.n 3: cr/b’s data block (1116), the inode block (34) and
cr/a’s data block (1115), for rename("cr/a/f", "cr/b/f").
renametest check found f in cr/a (1 name). The rename never happened.recovering tail 0 dst 1116,
tail 1 dst 34, tail 2 dst 1115, and the check found f in cr/b (1 name). The
rename happened completely, although none of its blocks had reached its home
location before the kill.Both disks passed the host checker. (In the first run the process had moved from hart 1,
where it entered sys_rename, to hart 0 by the time it committed: it had slept on a
disk read in between. The state shown is from the second run.)
user/mv.cStep 14 of 16 · commit 5: Add mv, a user command for rename
The user command is short because the kernel does the work. The one thing it adds is
Unix mv’s convenience: if new is an existing directory, the target becomes
new/<last element of old>, so mv a/d b means rename("a/d", "b/d"). The kernel’s
rename never does that itself; it refuses to replace a directory.
stat costs a lookup of new before the rename, outside the rename’s
transaction: if another process removes b in between, the rename fails, which is
the right answer for the state the kernel then sees.
user/renametest.cStep 15 of 16 · commit 6: Add renametest
The concurrent test is built from the deadlocks of think question 3 and the races of
questions 4 and 5. Two workers rename files between ct/a and ct/b in opposite
directions: with the naive order, that is the unrelated-directories deadlock. One
renames between ct/a/s and ct/a: the child-before-parent case. One moves the
directory m between ct/a and ct/b and each time tries to move m’s current
parent into m, which must fail: concurrent directory moves and the cycle check. Until
those four finish, one worker tries unlink("ct/a/s") (it must always fail, the
directory is not empty, but it locks ct/a and then ct/a/s, the existing order), and
two churn the names t and u, so that names change between a rename’s first look
and its locks. Line 255 creates s before a, giving it the lower inode number: that
is what an inode-number order gets wrong (clinic 2), and line 264 checks the setup.
After the run every name, m’s .., and every link count is checked.
A watchdog child prints a message if the workers are not done after 3 * rounds
ticks; a deadlock otherwise just hangs. Be honest about its power: neither wrong lock
order deadlocked in our runs without help, because the window between the two ilock
calls is a few instructions wide. With a delay loop widening it, both did (clinics 1
and 2), and the reference did not. The concurrent part did fail on clinic 5’s kernel (the
.. bug) in our run: there, a cycle attempt can succeed.
On the reference, the 200-round run (1600 renames and 400 refused cycles) took 110 and 121 ticks in the verify runs; the time varies a lot from run to run.
Step 16 of 16 · commit 6: Add renametest
A program cannot kill the machine it runs on at a random moment and then check the
result, so the crash test has two halves and a driver outside. renametest crash
builds cr/a/f and the directory cr/a/d (once), then moves both back and forth
between cr/a and cr/b forever, starting from wherever they are. The driver, a
python3 script on the host using only the standard library (so it runs on Linux,
macOS and WSL), starts QEMU, sends the command, waits a random 0.2 to 4 seconds, and
kills QEMU with SIGKILL (Popen.kill()). Then it boots the same disk image and runs
renametest check, which tests the invariants a half-done rename would break: each
name exactly once, d’s .. naming the directory it is in, the parents’ link counts
matching, f’s content intact. Finally a checker on the host walks the image.
In 30 such runs, every disk was consistent; 14 of the reboots replayed a committed
rename from the log (4 times 3 blocks, a file move; 10 times 4 blocks, a directory
move), so the kills did land inside renames, after their commit point. The plain
renametest run says only that this exists (see renametest crash): it cannot claim
what it did not check.
Lab 24 · wrap-up
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.
Keys: ← → step · Home start