Lab 23 · reveal · 16 steps · 7 commits
In this tree a name in a directory is a hard link: a struct dirent holding an inode
number. Two names can share one inode, but only inside one file system, never for a
directory, and the inode stays alive while any name points at it. A symbolic link is a
different idea: a small file whose content is a path name, which open replaces by the
thing that path names. It may point at a directory, at a name that does not exist yet, or
at another link.
You add a fourth inode type, a symlink(target, path) system call, and following in
open. The code is short. The questions are not. Which system calls should follow a
link, and what happens to the ones that do not? Where in the inode does the target go,
and inside which transaction? A link can name itself, or its own directory: what may the
kernel hold while it looks a target up, given the order in which namex takes inode
locks? What stops a cycle of links, and what does the machine look like if nothing does?
A relative target like f: relative to what?
The reference solution is seven small commits. With it, ln -s f d/l makes a link whose
creation logs a handful of disk blocks, and opening a file through one link costs about twice
as much as opening it directly, because following is a second path lookup.
Each step shows one change on the branch ext/23-symlink, the code around it, and the state of the machine when that code runs.
kernel/stat.hStep 1 of 16 · commit 1: Add T_SYMLINK, O_NOFOLLOW and MAXSYMLINK
The story of this tour was recorded in one boot of the finished branch, on three
harts, with gdb attached from boot. You type mkdir d (it becomes inode 25), echo hi > d/f (inode
26), ln -s f d/l (ln is pid 5; the link becomes inode 27) and cat d/l (pid 6),
which prints hi. Later steps follow pid 5 through symlink and pid 6 through
open.
Commit 1 only defines things. T_SYMLINK is the value 4 in the type field that every
inode already has, on disk (struct dinode) and in memory (struct inode). Nothing
about the shape of an inode changes: a link is an inode with a size and data blocks,
like a file, whose data happens to be a path. That is why mkfs and the on-disk format
need no change, only a rebuild, since this header is shared.
Every piece of code that tests type now has a value it has never seen. Code that asks
“is it a directory?” (like namex at kernel/fs.c:703) treats a link as “not a
directory”, which is exactly the behaviour the spec promises for links in the middle of
a path.
kernel/fcntl.hStep 2 of 16 · commit 1: Add T_SYMLINK, O_NOFOLLOW and MAXSYMLINK
O_NOFOLLOW is a new bit for open’s mode, 0x800, next to O_CREATE (0x200) and
O_TRUNC (0x400). The low two bits are not separate flags but an access mode
(O_RDONLY 0, O_WRONLY 1, O_RDWR 2), so a new flag must take a bit above them. The
other lines only change their padding so the values line up.
The same commit adds MAXSYMLINK (10) to kernel/param.h: the most links one open
will follow. It is a constant of the kernel, like MAXPATH, and user programs may
include param.h to see it (the test does, to build a chain of exactly 10 and one of
11).
kernel/syscall.cStep 3 of 16 · commit 2: Add the symlink system call
A new system call needs four small pieces outside its own code: a number
(SYS_symlink 23 in syscall.h), a user-side stub (entry("symlink") in usys.pl,
which generates li a7, SYS_symlink, ecall, ret), a prototype in user.h, and this table entry
(line 134) with its extern (line 106). syscall indexes the table with a7 from the trapframe; the
arguments stay in a0 and a1 until sys_symlink fetches them. See Tour 5: Life of a system call for the
whole path.
The table is static and never written, so three harts read it without a lock.
0x3fffff9000kernel/sysfile.cStep 4 of 16 · commit 2: Add the symlink system call
Both strings are copied into the kernel first, with argstr, into two MAXPATH
buffers on the kernel stack: 256 of this function’s 288-byte frame. argstr
returns the length, which sys_symlink keeps in n: it is how many bytes the target
is, and soon the size of the new inode. An empty target is refused.
Then begin_op joins (or opens) a log transaction, reserving room for
MAXOPBLOCKS = 10 blocks, and nameiparent finds the directory d and puts the
last name, l, in name. Everything up to end_op is one operation in the log, so
a crash leaves either the whole link or nothing.
No lock is held at the focus lines (noff 0), and interrupts are on, as in any system
call after usertrap's intr_on. The inode sleep-locks taken next do not change
that: sleep-locks are not counted in noff, and gdb saw noff 0 and sstatus =
0x200000022 (SIE set) at every stop in this function.
sp = 0x3fffff9e80inode 25 (d) lock (sleep-lock)inode 27 (the new link) lock (sleep-lock)Step 5 of 16 · commit 2: Add the symlink system call
These are create's first steps, written out: lock the parent, refuse a removed
directory (nlink 0) or an existing name, take a fresh inode from ialloc with type
4, lock it, set nlink to 1 and write it back. Why not call create? Because it
adds the directory entry before returning, and the reference wants the name to appear
last (next step).
gdb stopped right after ialloc: d (inode 25) locked by pid 5, the new inode 27,
name = "l", on hart 1, and the log holding 1 block: 34, the inode block for inodes
16 to 31, which ialloc marked allocated (the iupdate that follows writes the
same block, absorbed).
Two inode sleep-locks are held at once, in the order parent, then child: the order
namex, create and sys_unlink use. Nobody else can know inode 27 yet, and
nobody can search d while it is locked.
sp = 0x3fffff9e80inode 25 (d) lock (sleep-lock)inode 27 (the new link) lock (sleep-lock)Step 6 of 16 · commit 2: Add the symlink system call
writei at offset 0, n bytes from a kernel address (user_src = 0): the bytes of
the target, without the NUL. gdb at the call (hart 1): inode 27, type 4, nlink 1,
size 0, n = 1 (the target is f), 1 block in the log. At the dirlink that
follows, ln was on hart 2: inside writei it had given up the CPU (to wait for a
sleep-lock or the disk, or at a timer interrupt; gdb did not show which) and was
rescheduled on another hart, holding both inode sleep-locks, which
is allowed for sleep-locks. The log then held 3 blocks: 34, 46 (the free-block
bitmap, where balloc marked the new block used) and 1073 (the link’s data, zeroed
by balloc and then written). After dirlink wrote the entry (l, 27) into
d’s block 1071: 4 blocks, size 1, addrs[0] = 1073.
Only now does the name exist, and the link it names is complete. If writei or
dirlink finds the disk full, no entry was written; nlink goes back to 0 and
iunlockput's iput frees the inode with itrunc and ifree, inside this
transaction. A test that fills the disk confirmed it on this branch: symlink returned -1, /lk does not exist, and after freeing space symlink again returned 0.
Then both locks go, child first (the order of release does not matter for
deadlock), and end_op, the last operation outstanding, commits: the 4 blocks go to
the log on disk, the header is written, then the blocks are installed at their homes
(Tour 31: The log: begin_op, commit and group commit).
sp = 0x3fffff9e60, base 0x3fffff9000inode 27 (the link d/l) lock (sleep-lock)kernel/sysfile.cStep 7 of 16 · commit 3: Follow symbolic links in open
Now cat d/l. sys_open found inode 27 with namei and locked it with ilock,
as it always did. follow takes over a locked inode and returns a locked inode that
is not a link (or 0).
gdb stopped at this line (341 here, 365 on the finished branch, whose loop is the
same): inode 27, type
4, size 1, locked by pid 6; depth 0; log.outstanding 1 (this open is a
transaction too, though it will write nothing). In this build follow is inlined into
sys_open; gdb still shows it as a frame.
Line 339 is the cycle breaker: the 11th time round, if the inode is still a link, give
up. Lines 341-344 read the target: exactly size bytes, then a 0, because the writer
stored no NUL. The test n <= 0 refuses an empty link, which symlink never makes
(it writes the name last) but which a damaged disk could hold; n >= MAXPATH cannot happen for a link made by symlink, but
target has only MAXPATH bytes, and a check here costs nothing.
Step 8 of 16 · commit 3: Follow symbolic links in open
The most important two lines of the lab are in this order: iunlockput first,
namei second. Between them this process holds no inode lock at all; gdb right
after it (line 372 on the finished branch, 348 here): inode 27 lock.locked 0, ref 0, and the target
"f" safe in the local buffer.
Why it matters: namei runs namex, which locks each directory on the path, one
at a time, parent before child, and the target can name anything, including a path
through this very link (s → s/x) or the link’s own directory (d/up → .). Look
up with the link still locked and the first makes acquiresleep wait for a lock its
own caller holds, the second takes child-then-parent against sys_unlink's
parent-then-child. Clinic 1 has both, recorded: processes asleep for ever, and soon the
whole log.
What is still held is the transaction: log.outstanding stays 1 across the lookup.
That is required, since namex may call iput, which may free an inode.
At this commit, line 348 looks up the target as it is: f from cat’s current
directory /. There is no /f, so open fails here. Commit 4 fixes that.
inode 26 (d/f) lock (sleep-lock)kernel/sysfile.cStep 9 of 16 · commit 3: Follow symbolic links in open
Following happens after the inode is found and locked, by either branch, and only
without O_NOFOLLOW. With O_NOFOLLOW the link itself goes on through sys_open,
and read on the descriptor reads its data, the target.
The old check “a directory may only be opened read-only” sat in the else branch,
before any following (kernel/sysfile.c:355). It must now look at the inode open
will return, so it moves here, and covers links opened with O_NOFOLLOW too.
(omode & ~O_NOFOLLOW) != O_RDONLY keeps the old meaning exactly: any write bit, or
O_CREATE, or O_TRUNC, refuses a directory, but O_NOFOLLOW alone does not count as
a write. Clinic 6 leaves the check where it was: a link to a directory then opens it
for writing, and the shell corrupts it.
gdb at line 394 (418 on the finished branch): inode 26 (d/f), type 2, locked by pid 6,
omode 0. The rest of sys_open is unchanged: it never knows a link was involved.
kernel/sysfile.cStep 10 of 16 · commit 4: Resolve relative targets in the link's directory
path is sys_open’s own MAXPATH buffer, still holding the name open was called
with. resolve rewrites it in place to name the target: strip trailing slashes,
then the link’s own name, keeping the directory part including its final /; an
absolute target throws even that away. gdb stopped here with path = "d/l" and
target = "f": dirlen ends at 2, and safestrcpy writes f after d/, giving
d/f.
The test at line 342 refuses a result that would not fit. safestrcpy would
truncate silently, and a truncated path names the wrong file.
Why is the directory part right? Because only the last component of a path is ever
followed: everything before the last / was walked by namex as real directories.
In a design that follows links in the middle of a path, the link’s directory is not a
prefix of the string any more, and this trick would not work.
kernel/sysfile.cStep 11 of 16 · commit 4: Resolve relative targets in the link's directory
The only change in follow is what it looks up: path, freshly rewritten by
resolve, instead of target. Since each round rewrites path, the next link in a
chain is resolved against its own directory. /stt/c1 → c2 → … in the test, or a
link in d pointing at ../e/l2 whose target is relative to e, all come out right.
gdb at line 371 (374 on the finished branch; the ilock of the new inode): namei returned inode 26, not yet
locked; still no lock held. After the ilock, the loop tests the type again: a
file, so the loop ends and follow returns inode 26 locked.
An instrumented copy of the kernel, printing path at the end of sys_open, showed
this rewriting from outside: for an open of /m/1 (a link to f) it printed
/m/f. sys_open’s copy of the name has been replaced, which is harmless: nothing
after the follow uses it.
the existing inode's lock (sleep-lock)kernel/sysfile.cStep 12 of 16 · commit 5: Let open with O_CREATE follow an existing link
The shell opens the file of > with O_WRONLY | O_CREATE | O_TRUNC, so that path
goes through create, not namei. For an existing name, create used to accept
only a file or a device and refuse anything else: echo hi > link failed. Now an
existing link is handed back too (still locked), and sys_open follows it like any
other.
Only for T_FILE requests, that is, only for open. mkdir and mknod of an
existing name still fail, link or not (and symlink does its own check, without
create): a name is never silently reused.
If the target does not exist, follow fails and open returns -1; it does not create
the target, unlike Linux. Recorded by hand on the finished branch: echo bye > d/l
wrote bye into d/f.
(The state here is reasoned from the code: no gdb breakpoint was set in this branch.)
Step 13 of 16 · commit 6: Add ln -s to make symbolic links from the shell
The user side of the story’s first command: ln -s f d/l is argv = {"ln", "-s", "f", "d/l"}, four arguments, and symlink("f", "d/l") is the system call of the
previous steps (pid 5 entered the kernel on hart 2 and gdb found it there).
The target is passed on exactly as typed: ln does not make it absolute, and the
kernel does not look it up. So ln -s f d/l means “f, next to the link”, that is
d/f. Recorded on the finished branch:
$ ln -s f d/l
$ cat d/l
hi
$ ln -s d dl
$ ls dl
ls: cannot stat dl/.
ls: cannot stat dl/..
ls: cannot stat dl/f
ls: cannot stat dl/l
$ cat dl/f
cat: cannot open dl/f
$ cd dl
cannot cd dl
ls dl opens dl (followed: the directory d) and reads its entries, then stats
dl/., dl/f, …, where dl is a middle component, which is not followed. That is
the spec’s honest corner, visible from the shell.
user/symlinktest.cStep 14 of 16 · commit 7: Add symlinktest, a test program for symbolic links
A limit is only tested if both sides of it are: c1 is a chain of exactly
MAXSYMLINK links and must open; c0 is one more and must not. The relative targets
(c2, c3 …) make the chain a test of resolve too: the test runs from /, where
no c2 exists.
cycle (below) checks that two links naming each other, and a link naming itself, make
open fail rather than hang, with O_CREATE as well as without.
The rest of the program checks every line of the spec, including the parts that are deliberately not followed, so the reference cannot drift into following them without a test failing.
Step 15 of 16 · commit 7: Add symlinktest, a test program for symbolic links
Three children, one per hart if the scheduler spreads them, each 2,000 rounds of a
random choice among: make a link l0…l3 (target t, or another of the links),
remove one, open one following, open one with O_NOFOLLOW. Links appear, disappear
and point at each other while the other workers follow them.
What may never happen: an open through links that returns something other than the
file t (a half-made link, a recycled inode), or an O_NOFOLLOW read that returns
anything but a whole target. What may happen, and does: an open that fails because a
link in its chain vanished, or because the links currently form a cycle.
The last lines matter as much as the checks: a run in which no worker ever got through
proves nothing. On commit 3 (relative targets taken from /), every follow failed,
and a version of this test without that requirement still printed concurrent: OK;
now each worker
must succeed at least once, and the counts are printed. On the finished branch:
83 to 121 successful opens through links per worker, 238 to 253 links read.
inode 25 (d) lock (sleep-lock)inode 27 (the link) lock (sleep-lock)Step 16 of 16 · commit 7: Add symlinktest, a test program for symbolic links
sys_unlink is untouched by the branch, and it does the right thing. It finds the
parent with nameiparent and the entry with dirlookup; neither follows a
link, so rm d/l removes the link, never d/f. It clears the entry, drops the
link’s nlink to 0, and the final iput (inside iunlockput) sees ref 1 and
nlink 0: it runs itrunc, which frees the data block holding the target, and
ifree marks the inode free. symlinktest checks that last part from user space:
the next file created gets the unlinked link’s inode number.
The target’s nlink is never involved: a symbolic link is not counted anywhere in its
target, which is what lets a link dangle and lets a target be removed while links to
it exist. A hard link to a link (link("rl", "rl2")) is counted, in the link’s own
nlink, which the test sees as 2.
Recorded on the finished branch: rm d/l, then cat d/f still printed bye.
(The state shows the moment both inodes are locked, parent then child, at
kernel/sysfile.c:226; it is reasoned from the code. This is the lock order that the
buggy follow of clinic 1 collided with.)
Lab 23 · wrap-up
On the branch (ext/23-symlink, 7 commits; every commit builds with make kernel/kernel fs.img), run on 3 harts (-smp 3 -m 128M), one boot (the disk image also held the
symfull test program described below):
$ symlinktest
symlinktest: basic: OK
symlinktest: relative: OK
symlinktest: dangling: OK
symlinktest: nofollow: OK
symlinktest: chain: OK
symlinktest: cycle: OK
symlinktest: directory: OK
symlinktest: not followed in the middle of a path or by chdir: OK
symlinktest: create through a link: OK
symlinktest: unlink: OK
symlinktest: hard link to a symlink: OK
symlinktest: unlinked symlink's inode freed: OK
symlinktest: errors: OK
symlinktest: worker 1: 256 links made, 256 removed, 115 opened through links, 250 links read
symlinktest: worker 2: 241 links made, 244 removed, 121 opened through links, 253 links read
symlinktest: worker 0: 263 links made, 258 removed, 83 opened through links, 238 links read
symlinktest: concurrent: OK
symlinktest: ALL OK
$ usertests -q
usertests starting
test copyin: OK
test copyout: OK
[...]
test unlinkcwd: OK
ALL TESTS PASSED
$ symlinktest
[...]
symlinktest: worker 1: 248 links made, 257 removed, 122 opened through links, 256 links read
symlinktest: worker 0: 262 links made, 262 removed, 96 opened through links, 240 links read
symlinktest: worker 2: 248 links made, 237 removed, 125 opened through links, 235 links read
symlinktest: concurrent: OK
symlinktest: ALL OK
Every line is a check the program made itself. usertests -q passing shows that every
path without links behaves as before: open’s moved directory check still refuses
writable directories, create still refuses to reuse names for mkdir and mknod,
and nothing leaked (usertests counts free pages). The second symlinktest, after
usertests, shows the file system left in a state where everything still works.
A full disk. A test program symfull (not on the branch)
fills the disk with files, calls symlink, looks for the name, frees one file and tries
again. On the branch, another boot:
$ symfull
balloc: out of blocks
symfull: disk full after 886 data blocks
balloc: out of blocks
symfull: symlink returned -1
symfull: /lk does not exist
symfull: open /lk following: -1
symfull: after freeing space, symlink again returned 0
$ ls lk
lk 2 2 2441
The failed symlink left nothing behind, and the retry worked (ls lk follows the
link to README, inode 2). With a sys_symlink that calls create first, the same
program printed /lk exists: type 4 size 0 nlink 1 and the retry returned -1.
By hand, on the same branch:
$ ln -s /echo e
$ e hi
exec e failed
$ ls e
e 2 4 36960
$ ln -s /README r
$ wc r
48 336 2441 r
exec does not follow (as the spec says), ls and wc, which open, do.
The intermediate commits behave as the reveal says. With symlinktest built on commit 2
(no following): 11 checks fail, not followed …, unlinked symlink's inode freed and
errors pass. On commit 3: relative, chain, directory, create through a link,
hard link to a symlink and concurrent fail. On commit 4: only create through a link
fails.
Keys: ← → step · Home start