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

Symbolic links

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.

Read first: Tour 31: The log: begin_op, commit and group commit, Tour 33: The life of an inode, Tour 34: Path lookup, Tour 35: Creating and naming files, Tour 36: Reading and writing a file · Locks and interrupt state

What this lab teaches

How the inode types of this tree (T_DIR, T_FILE, T_DEVICE) are used by open, create, namex and unlink, and how a fourth type fits in without changing the on-disk format.
Where a file system can keep a small piece of variable-length data such as a link’s target, and what has to happen inside one log transaction when it is written.
How many blocks one file-system operation may write (MAXOPBLOCKS), and how to count them for a new operation.
Which inode sleep-locks namex takes, in which order, and what that means for code that looks up a path while it holds an inode lock. What a self-deadlock on a sleep-lock looks like in this tree, and how one stuck process can stop every file-system write.
Why a loop in the kernel needs a bound, what a process that never leaves the kernel does to kill and to the log, and what a kernel stack overflow looks like through the guard page.
What unlink, link and the link count mean for a symbolic link.

The reference branch

ext/23-symlink in ShowMeTheStack/xv6-riscv-labs, branched from the frozen commit 06aad25; 7 commits.

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

1. The spec

Behaviour.

int symlink(char *target, char *path) creates a new inode of type T_SYMLINK (4, in kernel/stat.h) at path, whose content is the bytes of target (without the final NUL; the inode’s size is the target’s length). target is not looked up: it may name nothing yet. It returns 0, or -1 if path already exists, its directory does not exist, or target is empty. If the disk is full, it returns -1 and leaves nothing behind: the name does not exist afterwards, and a retry with free space succeeds.
open(path, flags) follows links: while the inode it found is a T_SYMLINK, it replaces it by the inode that the link’s target names, at most MAXSYMLINK (10) times. More links than that (a cycle, or a chain of 11) make open fail with -1. A target that does not exist makes open fail.
A relative target is taken from the link’s own directory: a link d/l with target f means d/f, whatever the current directory of the process that opens it.
With O_NOFOLLOW (0x800, in kernel/fcntl.h), open returns the link itself, for reading only: read returns the target’s bytes and fstat reports T_SYMLINK.
open with O_CREATE of an existing link follows it (so echo hi > link writes the target); if the target does not exist, open fails. It does not create the target.
A link that leads to a directory can be opened read-only, like the directory itself.

Only open follows, and only the last name of a path. This is the design decision of the lab, worked out in the think section. namex is unchanged, so a link in the middle of a path is not a directory to it: open("dl/f") fails when dl is a link to a directory. sys_chdir and kexec look their path up with namei and do not follow either: cd dl fails, and running a program through a link fails. ls dl opens dl and reads the directory’s entries, but then cannot stat any of them (dl/f has dl as a middle component): it prints one ls: cannot stat dl/<name> line per entry. unlink and link act on the link itself, never on its target.

What must not change. Every existing behaviour of open, mkdir, mknod, link, unlink and chdir on paths without links; the on-disk format (a link is an ordinary inode with one data block); usertests -q must print ALL TESTS PASSED on 3 harts.

The test program, symlinktest, checks everything above itself and prints one line per check (the counts in the worker lines, and their order, vary from run to run):

$ 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

basic: /stt/l1 → /stt/a; reading through the link gives the file’s data, fstat gives the file’s inode number, and a write through the link changes the file.
relative: /stt/rl → a opens /stt/a, from / (where there is no a) and as ../rl from /stt/sub.
dangling: a link to a name that does not exist cannot be opened, until the name is created.
nofollow: O_NOFOLLOW gives the link: type T_SYMLINK, size 6, link count 1, data /stt/a; it cannot be opened for writing. The target’s link count is still 1.
chain: c1 → c2 → … → c10 → /stt/a opens (10 links); c0 → c1 does not (11). A link to a link opens too.
cycle: x → y → x, and s → s, fail (also with O_CREATE) and do not hang.
directory: /stt/dlink → d opens read-only as a directory whose entries include f; opening it for writing fails. Then the honest part: /stt/dlink/f and chdir("/stt/dlink") fail.
create through a link: O_CREATE through a dangling link fails and creates nothing; through a live one it truncates and writes the target.
unlink, hard link, inode freed: unlink removes the link, not the target; a hard link to a link raises the link’s count to 2; an unlinked link’s inode is freed (the next new file gets its inode number).
errors: empty target, existing name, missing directory.
concurrent: three processes on three harts create, remove and open four links /stt/c/l0 … l3 2,000 times each, with targets that are a file t or another of the links, so chains and cycles form and break all the time. Every open through links must reach t or fail, every link read must hold a whole target, and each worker must have succeeded at least once at both (otherwise the check proves nothing). The worker lines show how often.

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.

1What is a symbolic link, on disk?

A link must remember a path name of up to MAXPATH - 1 = 127 bytes. Before writing any code, decide where those bytes live. In the directory entry? In some field of the target? Somewhere in a new kind of inode? And what does the rest of the system (mkfs, ls, stati, fstat) need to know about your decision?

Check yourself

1warm-upChoose one

ln -s /stt/a /stt/l1 has run on the reference branch. Where are the six bytes /stt/a stored?

In a new field of /stt/a’s inode, which counts and lists the links to it.In the name field of l1’s directory entry in /stt.In the first data block of the link’s own inode (inode type T_SYMLINK, size 6).In the inode’s addrs[] array, where the block numbers normally go.

2solidType a number

A program opens /stt/l1 (target /stt/a) with O_RDONLY | O_NOFOLLOW and calls fstat. What is st.size?

decimal, 0x hex or 0b binary

2Making one, inside one transaction

symlink(target, path) must make a new name in a directory, a new inode, and write the target into it. Existing code already makes “new name, new inode”: in what state does it leave things, and in what order does it do them? If you reuse it as it is and then write the target, can another process, on another hart, find the link before the target is in it? What is left behind if the disk fills up halfway? Where must begin_op and end_op go, and how many disk blocks can this one operation dirty: is that within the limit every operation must respect?

The reference design

create does “new name, new inode”: it locks the parent directory, checks the name is free, calls ialloc, locks the new inode, sets nlink to 1, adds the directory entry with dirlink, unlocks the directory and returns the new inode, locked. Calling it and then writei would almost work: the name would be visible before the target is written, but anyone who found it would sleep in ilock until the target was there. The real trouble is failure. If writei finds the disk full, the name is already in the directory. A sys_symlink that does exactly that, run on a full disk, shows the result: symlink returned -1 but left a link of size 0 at the name, so even a retry after freeing space failed until someone ran rm.

So the reference does create's steps itself, in a different order: lock the directory, check the name, ialloc and lock the new inode, write the target, and only then dirlink the name. The name appears only when the link is complete. If either write fails, it sets the inode’s nlink to 0, and iunlockput's iput frees the inode and any block it got; the directory never changed. Recorded on a full disk: symfull: symlink returned -1, /lk does not exist, and after freeing space symlink again returned 0. The two inode locks are taken in create's order, directory before new inode, parent before child, as everywhere in this file system.

Everything sits between one begin_op and one end_op, so a crash leaves either the whole link (inode, target and name) or nothing. Forget them and the first log_write panics (clinic 3). (The log gives atomicity across crashes, not isolation: other processes see cached blocks at once. What keeps them out of a half-made link here is the order of the writes and the two locks.)

How many blocks? Recorded with gdb, and with an instrumented kernel that printed the log just before end_op: ln -s f d/l logged 4 blocks (the inode block holding both the new link and d, the bitmap block, the link’s new data block and d’s data block); a link whose inode falls in a different inode block from its directory’s logged 5; and a link whose directory needed a new data block also logged 5. Each iupdate of an inode in a block already logged is absorbed. The worst case, reasoned from bmap rather than measured, adds the directory’s indirect block the first time a directory grows past 12 blocks: 6, under the MAXOPBLOCKS of 10 that begin_op reserves.

An empty target is refused: namei("") returns the current directory in this tree, which no one would mean.

Check yourself

1solidPut in order

Put the steps of ln -s f d/l on the reference branch in the order they happen (d is inode 25; the new link becomes inode 27).

ialloc gives inode 27, which is locked and gets nlink 1
begin_op reserves room in the log for this operation
iunlockput releases inode 27 and then d, and end_op commits the transaction
writei stores the byte f in a new data block of inode 27
sys_symlink locks directory d and checks that the name l is free
dirlink writes the entry (l, 27) into d

2solidTrue or false, and why

True or false: on the reference branch, a process on another hart can find the name d/l while its target is not yet written.

TrueFalse

Why?

It can find it, but open follows the empty target and fails, which is harmless.The entry (l, 27) is written by dirlink only after writei has stored the target.The log transaction makes the new entry invisible until end_op commits it.

3deepType a number

In the recorded run, the new link (inode 27) and its directory d (inode 25) lie in the same inode block (16 inodes per block), d has room in its existing data block, and the link’s target needs one new data block. How many distinct blocks are in the log when sys_symlink calls end_op?

decimal, 0x hex or 0b binary

3Which calls follow a link?

Every path in this tree is looked up by namex, through namei or nameiparent. You could follow links inside namex, for every component of every path, or only in some system calls, only for the last component. The spec fixes the choice for this lab; before you accept it, argue it yourself. For open, chdir, exec, unlink, link, mkdir and the middle of a path: what would following cost, and what would not following cost? Which of them must not follow a link even in Unix?

Check yourself

1solidChoose all that apply

On the reference branch, dl is a link to the directory d, which contains the file f. Which of these succeed?

4What may you hold while you look up the target?

open has found the link and holds its inode’s sleep-lock (it called ilock to read the type). It reads the target. Now it must look the target up. In which order do you do “release the link” and “look up the target”, and why does it matter? Think of a link whose target leads through the link itself, like s → s/x, and of a link to its own directory, d/up → ., while another process removes d/up.

Check yourself

1deepChoose one

A buggy follow calls namei(target) while it still holds the link’s lock, and releases the link only afterwards. You type ln -s s/x s and then cat s &. What happens?

open returns -1 after MAXSYMLINK follows.cat sleeps forever in acquiresleep, waiting for the lock of inode s, which cat itself holds; nothing is printed.cat prints “cannot open s” because s/x does not exist.The kernel panics with acquire, because a lock was taken twice.

2deepChoose all that apply

With the same buggy follow (lookup while holding the link), which of these situations can hang?

open of self, where self → selfopen of s, where s → s/xopen of d/up, where d/up → ., while another process unlinks d/upopen of x, where x → y and y → x

5What stops a cycle?

x → y and y → x is legal to create: symlink does not look its target up. So open must stop somehow. Choose a mechanism. Then predict what the machine looks like if you forget it: the follow loop never ends. Does the system hang? Can you kill the process? What happens to other processes’ file operations? And if you had written follow as a recursive function instead of a loop?

Check yourself

1warm-upType a number

MAXSYMLINK is 10. A chain of links ends in a regular file: c1 → c2 → … → cN → file. What is the largest N for which open("c1") still succeeds on the reference branch?

decimal, 0x hex or 0b binary

2solidChoose one

A kernel without the depth limit (the loop version). You type cat x & with x → y → x, then kill the cat process. What do you observe?

The whole machine freezes at once; nothing answers.The shell keeps working, ^P keeps showing cat as run even after kill, and after a few more file creations, file operations start to hang.kill stops it: the loop ends at the next timer interrupt.The kernel panics with a stack overflow.

6Relative to what?

ln -s f d/l stores the target f. A process whose current directory is / opens d/l. The spec says that means d/f. What would namei("f") give instead, and why is the spec’s meaning the only useful one? Then: how can open compute d/f with the information it has? What if the target is ../e/f? What if it is a chain of relative links in different directories?

Check yourself

1solidChoose one

A process whose current directory is /home opens /a/b/l, a link with target ../c/f. Which path does the reference look up next?

/a/b/l/…/c/f/a/b/…/c/f…/c/f, looked up from /home/home/…/c/f

7What else changes, and what does not?

Go through sys_open line by line with links in mind, then the other calls. Which existing checks can a link now slip past? What should O_CREATE do with an existing link, and O_NOFOLLOW with a request to write? What does unlink do to a link, and to its target? Does a symbolic link change anybody’s link count?

Check yourself

1warm-upTrue or false, and why

True or false: symlink("/stt/a", "/stt/l1") increases the link count (nlink) of /stt/a.

TrueFalse

Why?

The symlink stores a path in its own inode; /stt/a’s inode is never read or written.nlink only counts open file descriptors.Symbolic links are counted, but only after the first open through them.

2solidChoose one

A version of sys_open follows links but keeps the old “directories are read-only” check where it was, before follow. dl → d, a directory. You type echo xx > dl and then ls d. What happens?

echo writes into directory d itself, overwriting its first entry, and ls d panics with ilock: no type.echo fails, because d is a directory.echo replaces the link dl by a file containing xx.echo creates a new file named dl inside d.

3. Build it

Start.

git checkout -b my-symlink 06aad25

Write the test program first: copy the spec’s list of checks into user/symlinktest.c. It cannot compile until T_SYMLINK, O_NOFOLLOW and the symlink stub exist, so add $U/_symlinktest\ to UPROGS in the Makefile at milestone 2.

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

Definitions. T_SYMLINK 4 in kernel/stat.h, O_NOFOLLOW 0x800 in kernel/fcntl.h (pick a bit no other flag uses), MAXSYMLINK 10 in kernel/param.h. Test: make rebuilds everything, usertests -q still passes.
The system call. The four places every new system call needs (syscall.h, the table in syscall.c, usys.pl, user.h), then sys_symlink in sysfile.c. Test: symlinktest runs; not followed in the middle of a path or by chdir, errors and unlinked symlink's inode freed already pass, the other 11 checks fail. (Even nofollow fails: nothing refuses to open a link for writing yet.)
Following in open. The loop, the depth limit, O_NOFOLLOW, and the moved type check. Test: basic, dangling, cycle pass; checks with relative targets still fail. Then usertests -q.
Relative targets. Test: relative, chain, directory pass.
O_CREATE through a link. Test: create through a link, then the whole of symlinktest, then usertests -q, then symlinktest again.
ln -s. Try it by hand: ln -s README r, wc r, echo hi > r2, ln -s r2 r3, echo bye > r3, cat r2.

Debugging advice. Start QEMU halted with make qemu-gdb (it picks its own gdb port and writes it into .gdbinit) when you need breakpoints from boot.

In this build follow and resolve are static, called once, and inlined into sys_open. Breakpoints by line number (break sysfile.c:371) still work, and bt shows them as inline frames, but some locals print as <optimized out>.
A hang inside the file system is almost always a sleep-lock or the log. Type ^P to see who is sleeping, then attach gdb and print every inode in itable whose ref is above 0, with lock.locked and lock.pid, and every process’s chan. A process whose chan equals &itable.inode[i].lock is waiting for that inode; if it is also that lock’s pid, it is waiting for itself. chan equal to &log means it waits in begin_op: print log.outstanding and log.lh.n.
panic: log_write outside of trans: a write to a buffer with no begin_op around it. Break on panic and bt.
If a link “sometimes” works, print the target buffer with x/24xb right after readi: look at the bytes after the target.

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.

1Looking up the target while holding the link’s lock

The natural order “read the target, look it up, then let go of the link”:

     target[n] = 0;
-    // release the link before looking up its target: namei locks
-    // directories, and the target may lead through this very link.
-    iunlockput(ip);
-    if (resolve(path, target) < 0 || (ip = namei(path)) == 0)
-      return 0;
+    if (resolve(path, target) < 0 || (next = namei(path)) == 0)
+      goto bad;
+    iunlockput(ip);
+    ip = next;
     ilock(ip);

Two runs on this kernel, 3 harts: links typed at the shell followed by seven small file creations, then (a fresh boot) a helper program clinic23 (not on the branch): one process loops symlink(".", "/dd/up") + unlink("/dd/up") 2,000 times while its parent opens /dd/up 2,000 times. After each hang, ^P, and gdb attached to print the process table, the inodes in use and the log.

What happened when we ran it

$ ln -s self self
$ cat self
cat: cannot open self
$ ln -s s/x s
$ cat s &
$
1 sleep  init
2 sleep  sh
7 sleep  cat
echo a > f1
$ echo b > f2
$ echo c > f3
$ echo d > f4
$ echo e > f5
$ echo f > f6
echo g > f7

1 sleep  init
2 sleep  sh
13 sleep  echo
7 sleep  cat
[...]
pid 13 echo state 2 chan 0x8001f970
pid 7 cat state 2 chan 0x8001e000
[...]
inode 27 type 4 ref 2 nlink 1 locked 1 by pid 7, &lock = 0x8001e000
inode 33 type 2 ref 1 nlink 1 locked 0 by pid 0, &lock = 0x8001e088
[...]
$1 = 1
$2 = 0
$3 = 11
$4 = (struct log *) 0x8001f970 <log>

(another boot)
$ clinic23 2000

1 sleep  init
2 sleep  sh
3 sleep  clinic23
4 sleep  clinic23
[...]
pid 3 clinic23 state 2 chan 0x8001e000
pid 4 clinic23 state 2 chan 0x8001e088
[...]
inode 26 type 1 ref 2 nlink 1 locked 1 by pid 4, &lock = 0x8001e000
inode 27 type 4 ref 2 nlink 1 locked 1 by pid 3, &lock = 0x8001e088

self → self works. The lookup of self never locks self: namex locks only the directories it searches (kernel/fs.c:702) and returns the last component unlocked (kernel/fs.c:727). So the buggy loop gets a second reference to the same inode, releases the first, locks it again, and after 10 rounds gives up: cannot open. A test with only this case would pass.

s → s/x hangs, alone. cat (pid 7) holds s, inode 27, and calls namei("s/x"). namex reaches s as a middle component and calls ilock on it (kernel/fs.c:702), that is acquiresleep on a sleep-lock that pid 7 holds. acquiresleep does not check who holds the lock (kernel/sleeplock.c:25): it sleeps until the holder releases it, and the holder is itself. gdb shows it: pid 7 sleeps on channel 0x8001e000, which is the address of inode 27’s lock, locked 1 by pid 7. Nothing panics, nothing is printed.

Then the file system stops. cat is stuck inside a transaction: its begin_op raised log.outstanding to 1 and its end_op will never run. Other operations still start and finish, but with outstanding never reaching 0 nothing is committed, and their blocks stay in the log: after f1 … f5 it held 10 blocks (gdb, in an earlier run of this clinic that stopped there). The sixth echo f > f6 still created f6 (gdb found its inode, 33, open), and that pushed the log to 11 blocks; its next file-system call, a write, found 11 + (1 + 1) × 10 > 30 in begin_op (kernel/log.c:138) and slept on the channel &log (0x8001f970), for ever. (Which echo is the first to hang depends on how many blocks each creation adds: another run, with a slightly different disk image, got through the sixth.) The shell waits for it, so the typed echo g > f7 is never run. One process holding one inode lock has stopped every file-system write on all three harts. (In that earlier run, a later ls printed the root directory up to console 3 25 0, then ls: cannot stat ./self (a cycle, refused as it should be), and then nothing more. The next entry is s; that ls hung stat-ing it, on the lock cat holds, is reasoned, not observed with gdb.)

d/up → .: two processes, opposite orders. clinic23 never finished. pid 3, the opener, holds the link up (inode 27, type 4) and sleeps on 0x8001e000, the lock of inode 26 (type 1, the directory /dd): it was looking up /dd/., and namex locks /dd as a middle component. pid 4 holds /dd and sleeps on 0x8001e088, the lock of up: that is sys_unlink, which locks the directory and then the entry (kernel/sysfile.c:218, kernel/sysfile.c:226). The rule everybody else follows is “parent before child”; the buggy follow takes a child (the link) and then its parent. log.outstanding was 2: both are inside transactions, so the rest of the file system follows them down as above.

The fix is not a smarter order but holding nothing: copy the target out, release the link, then look up.

2No limit on the number of links followed

The depth check is left out:

   for (depth = 0; ip->type == T_SYMLINK; depth++) {
-    if (depth >= MAXSYMLINK) // probably a cycle
-      goto bad;
     n = ip->size;

A second variant writes follow recursively, also without a limit: after looking up the target and locking it, it returns follow(ip, path). (In this build, with -O, GCC keeps that as a real call, not a jump: jal 80004d3e <follow> inside follow; its frame is 176 bytes.)

What happened when we ran it

$ ln -s y x
$ ln -s x y
$ cat x &
$
1 sleep  init
2 sleep  sh
6 run    cat
kill 6
$
1 sleep  init
2 sleep  sh
6 run    cat
[...]
pid 6 cat state 4 chan (nil) killed 1
[...]
* 1    Thread 1.1 (CPU#0 [running]) intr_get () at kernel/riscv.h:327
  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

(another boot: the same three commands, `echo hi`, a `kill` of a wrong pid, then five small files)
$ echo e > f5
$ echo f > f6
echo g > f7

1 sleep  init
2 sleep  sh
14 sleep  echo
6 run    cat
[...]
pid 14 echo state 2 chan 0x8001f970
[...]
$3 = 11

(the recursive version, another boot)
$ ln -s y x
$ ln -s x y
$ cat x
scause=0xf sepc=0x80005786 stval=0x3fffff8000
panic: kerneltrap

# gdb, the same run:
=== first follow in cat: sp 0x3fffff9f00 pid 5 kstack 0x3fffff9000
follow call 18: sp 0x3fffff9350
follow call 19: sp 0x3fffff92a0
=== kernelvec entry 1 after 19 follow calls in cat: sepc 0x80000bb0 stval 0x3fffff8ff8 sp 0x3fffff8fe0 pid 5 kstack 0x3fffff9000
push_off + 2 in section .text
=== kernelvec entry 2 after 19 follow calls in cat: sepc 0x80005782 stval 0x3fffff8ee0 sp 0x3fffff8ee0 pid 5 kstack 0x3fffff9000
[...]
=== kernelvec entry 16 after 19 follow calls in cat: sepc 0x80005782 stval 0x3fffff80e0 sp 0x3fffff80e0 pid 5 kstack 0x3fffff9000
=== kernelvec entry 17 after 19 follow calls in cat: sepc 0x80005786 stval 0x3fffff8000 sp 0x3fffff7fe0 pid 5 kstack 0x3fffff9000

The loop version: busy, unkillable, and slowly fatal. cat follows x, y, x … forever inside sys_open. It holds no spinlock between iterations and interrupts are on (it is a system call), so the timer still preempts it: the shell answered, kill 6 ran, and ^P worked. gdb showed cat RUNNING (state 4) on hart 0 while the other two harts were halted in wfi, idle.

kkill set killed (gdb: killed 1), but cat was still run ten seconds later. A process acts on killed in usertrap (kernel/trap.c:81), on its way back to user space, and in a few sleep loops; this one never leaves the kernel and never sleeps. Interrupts taken while it runs go through kerneltrap, which may yield but never checks killed.

And it is inside a transaction that will never end, exactly as in clinic 1: five file creations went through, the sixth echo created its file and then slept in begin_op (channel 0x8001f970 is &log; the log held 11 blocks). A cycle of two links, opened once, ends every file-system write until reboot.

The recursive version: a kernel stack overflow, caught by the guard page. Each call puts a 176-byte frame (with the 128-byte target buffer) on cat’s kernel stack, the page 0x3fffff9000–0x3fffffa000. The first call had sp = 0x3fffff9f00; the 19th was at 0x3fffff92a0. Inside the next lookup, push_off's first store went to 0x3fffff8ff8, below the stack page, into the unmapped guard page: a store page fault (scause 15) in supervisor mode, so the trap goes to kernelvec. But kernelvec saves registers on the current stack, which is the overflowing one: its first store faults again, and again, each nested trap moving sp down 256 bytes through the guard page (16 times). The 16th entry’s addi takes sp to 0x3fffff7fe0, below the guard page, into the kernel stack page of the next slot, which is mapped: two stores succeed, and the store at sp + 32 = 0x3fffff8000 touches the guard page once more. That is entry 17, whose 256-byte frame (from 0x3fffff7ee0) is entirely mapped, so kerneltrap finally runs and panics with entry 17’s values. The message reports that last fault, in kernelvec, not in follow: when a kernel stack overflows, the panic’s sepc points at the trap code, and stval near a page boundary below kstack is the clue.

With a limit of 10, the loop and the recursion are both harmless; the recursion would use about 1.8 KiB of the 4 KiB stack, which is one more reason the reference uses a loop.

3No begin_op and end_op around symlink

sys_symlink does all its work without a transaction:

-  begin_op();
   if ((dp = nameiparent(path, name)) == 0) {
-    end_op();
     return -1;
   }

(and the two end_op calls further down removed as well).

What happened when we ran it

$ ln -s README l
panic: log_write outside of trans

4Reading the target without its length

The writer stores the target without a NUL, as the reference does. The reader asks readi for a whole MAXPATH and forgets to terminate:

-    n = ip->size;
-    if (n <= 0 || n >= MAXPATH || readi(ip, 0, (uint64)target, 0, n) != n)
-      goto bad;
-    target[n] = 0;
+    if ((n = readi(ip, 0, (uint64)target, 0, MAXPATH)) <= 0)
+      goto bad;

What happened when we ran it

$ symlinktest
symlinktest: basic: OK
symlinktest: relative: FAIL
symlinktest: dangling: FAIL
symlinktest: nofollow: OK
symlinktest: chain: FAIL
symlinktest: cycle: OK
symlinktest: directory: FAIL
symlinktest: not followed in the middle of a path or by chdir: OK
symlinktest: create through a link: FAIL
symlinktest: unlink: OK
symlinktest: hard link to a symlink: FAIL
symlinktest: unlinked symlink's inode freed: OK
symlinktest: errors: OK
symlinktest: worker 0: 256 links made, 254 removed, 0 opened through links, 234 links read
symlinktest: worker 1: 244 links made, 248 removed, 0 opened through links, 259 links read
symlinktest: worker 2: 253 links made, 249 removed, 0 opened through links, 251 links read
symlinktest: concurrent: FAIL
symlinktest: SOME TESTS FAILED

# gdb (another boot, a build of this bug whose sys_symlink adds the name before
# writing the target; follow is the same), right after readi, in symlinktest:
=== hit 4: follow in symlinktest, after readi (370)
$16 = 3
$17 = 0x3fffff9e78 "a"
0x3fffff9e78:	0x61	0x00	0x00	0x00	0x00	0x00	0x00	0x00
[...]
=== hit 5: follow in symlinktest, after readi (370)
$21 = 3
$22 = 0x3fffff9e78 "a\f"
0x3fffff9e78:	0x61	0x0c	0x00	0x80	0x00	0x00	0x00	0x00
[...]
=== hit 6: follow in symlinktest, after readi (370)
$26 = 3
$27 = 0x3fffff9e78 "/stt/later\001\200"

5O_NOFOLLOW is ignored

open always follows:

-  if (!(omode & O_NOFOLLOW) && (ip = follow(ip, path)) == 0) {
+  if ((ip = follow(ip, path)) == 0) {

What happened when we ran it

$ symlinktest
symlinktest: basic: OK
symlinktest: relative: OK
symlinktest: dangling: OK
symlinktest: nofollow: FAIL
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: FAIL
symlinktest: unlinked symlink's inode freed: FAIL
symlinktest: errors: OK
worker 0: bad link /stt/c/l3: 'target'
worker 2: bad link /stt/c/l3: 'target'
worker 1: bad link /stt/c/l3: 'target'
symlinktest: concurrent: FAIL
symlinktest: SOME TESTS FAILED
$ usertests -q
usertests starting
[...]
ALL TESTS PASSED

6The directory check stays where it was

Following is added below the else branch, but the old “directories are read-only” test stays inside it, before the follow, and checks only T_DIR:

     ilock(ip);
+    if (ip->type == T_DIR && omode != O_RDONLY) {
+      iunlockput(ip);
+      end_op();
+      return -1;
+    }
   }
[...]
-  // a directory, or a link opened with O_NOFOLLOW, is read-only.
-  if ((ip->type == T_DIR || ip->type == T_SYMLINK) &&
-      (omode & ~O_NOFOLLOW) != O_RDONLY) {
+  // a link opened with O_NOFOLLOW is read-only.
+  if (ip->type == T_SYMLINK && (omode & ~O_NOFOLLOW) != O_RDONLY) {

What happened when we ran it

$ symlinktest
[...]
symlinktest: directory: FAIL
[...]
symlinktest: SOME TESTS FAILED

(another boot)
$ mkdir d
$ echo hi > d/f
$ ln -s d dl
$ ls d
.              1 25 48
..             1 1 1024
f              2 26 3
$ echo xx > dl
$ ls d
panic: ilock: no type

# gdb, breakpoint on panic:
#1  0x00000000800032d8 in ilock (ip=ip@entry=0x8001e078 <itable+432>) at kernel/fs.c:317
#2  0x000000008000524a in sys_open () at kernel/sysfile.c:409
[...]
$17 = 30840
$18 = 1
$19 = 1960
$20 = 200

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

b0c836c Add T_SYMLINK, O_NOFOLLOW and MAXSYMLINK
kernel/fcntl.h
@@ -1,5 +1,6 @@
1#define O_RDONLY 0x000
2#define O_WRONLY 0x001
3#define O_RDWR 0x002
4#define O_CREATE 0x200
5#define O_TRUNC 0x400
1#define O_RDONLY 0x000
2#define O_WRONLY 0x001
3#define O_RDWR 0x002
4#define O_CREATE 0x200
5#define O_TRUNC 0x400
6#define O_NOFOLLOW 0x800 // open a symbolic link itself, not its target
kernel/param.h
@@ -11,4 +11,5 @@
1111#define NBUF (MAXOPBLOCKS * 3) // size of disk block cache
1212#define FSSIZE 2000 // size of file system in blocks
1313#define MAXPATH 128 // maximum file path name
1414#define USERSTACK 1 // user stack pages
15#define MAXSYMLINK 10 // max symbolic links followed by open
kernel/stat.h
@@ -1,7 +1,8 @@
1#define T_DIR 1 // Directory
2#define T_FILE 2 // File
3#define T_DEVICE 3 // Device
1#define T_DIR 1 // Directory
2#define T_FILE 2 // File
3#define T_DEVICE 3 // Device
4#define T_SYMLINK 4 // Symbolic link: the data is a path name
45
56struct stat {
67 int dev; // File system's disk device
78 uint ino; // Inode number
3aeb563 Add the symlink system call
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_symlink(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_symlink] = sys_symlink,
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_symlink 23
kernel/sysfile.c
@@ -393,8 +393,65 @@ sys_open(void)
393393
394394 return fd;
395395}
396396
397// Create path as a symbolic link whose content is target.
398// target is not looked up: it may name nothing yet.
399uint64
400sys_symlink(void)
401{
402 char target[MAXPATH], path[MAXPATH], name[DIRSIZ];
403 struct inode *dp, *ip;
404 int n;
405
406 if ((n = argstr(0, target, MAXPATH)) < 0 || argstr(1, path, MAXPATH) < 0)
407 return -1;
408 if (n == 0) // an empty target names nothing
409 return -1;
410
411 begin_op();
412 if ((dp = nameiparent(path, name)) == 0) {
413 end_op();
414 return -1;
415 }
416 ilock(dp);
417 // as in create(): no new names in a removed directory,
418 // and never a name that exists.
419 if (dp->nlink == 0)
420 goto bad;
421 if ((ip = dirlookup(dp, name, 0)) != 0) {
422 iput(ip);
423 goto bad;
424 }
425 if ((ip = ialloc(dp->dev, T_SYMLINK)) == 0)
426 goto bad;
427 ilock(ip);
428 ip->nlink = 1;
429 iupdate(ip);
430
431 // write the target before the name exists, so that no one
432 // can ever find a link without one. The NUL is not stored:
433 // the size of the inode is the length of the target.
434 if (writei(ip, 0, (uint64)target, 0, n) != n ||
435 dirlink(dp, name, ip->inum) < 0) {
436 // out of disk blocks: no name was made, and iput frees
437 // the inode and any block it got.
438 ip->nlink = 0;
439 iupdate(ip);
440 iunlockput(ip);
441 goto bad;
442 }
443 iunlockput(ip);
444 iunlockput(dp);
445 end_op();
446 return 0;
447
448bad:
449 iunlockput(dp);
450 end_op();
451 return -1;
452}
453
397454uint64
398455sys_mkdir(void)
399456{
400457 char path[MAXPATH];
user/user.h
@@ -16,8 +16,9 @@ int open(const char *, int);
1616int mknod(const char *, short, short);
1717int unlink(const char *);
1818int fstat(int fd, struct stat *);
1919int link(const char *, const char *);
20int symlink(const char *, const char *);
2021int mkdir(const char *);
2122int chdir(const char *);
2223int dup(int);
2324int getpid(void);
user/usys.pl
@@ -42,4 +42,5 @@ entry("getpid");
4242entry("sbrk");
4343entry("pause");
4444entry("uptime");
4545entry("sync");
46entry("symlink");
653c94b Follow symbolic links in open
kernel/sysfile.c
@@ -324,8 +324,39 @@ fail:
324324 iunlockput(dp);
325325 return 0;
326326}
327327
328// ip is a locked inode. While it is a symbolic link, replace it
329// by the inode its target names, following at most MAXSYMLINK
330// links. Returns a locked inode that is not a link, or 0 (with
331// ip released) if a target is missing or there are too many links.
332static struct inode *
333follow(struct inode *ip)
334{
335 char target[MAXPATH];
336 int n, depth;
337
338 for (depth = 0; ip->type == T_SYMLINK; depth++) {
339 if (depth >= MAXSYMLINK) // probably a cycle
340 goto bad;
341 n = ip->size;
342 if (n <= 0 || n >= MAXPATH || readi(ip, 0, (uint64)target, 0, n) != n)
343 goto bad;
344 target[n] = 0;
345 // release the link before looking up its target: namei locks
346 // directories, and the target may lead through this very link.
347 iunlockput(ip);
348 if ((ip = namei(target)) == 0)
349 return 0;
350 ilock(ip);
351 }
352 return ip;
353
354bad:
355 iunlockput(ip);
356 return 0;
357}
358
328359uint64
329360sys_open(void)
330361{
331362 char path[MAXPATH];
@@ -351,13 +382,21 @@ sys_open(void)
351382 end_op();
352383 return -1;
353384 }
354385 ilock(ip);
355 if (ip->type == T_DIR && omode != O_RDONLY) {
356 iunlockput(ip);
357 end_op();
358 return -1;
359 }
386 }
387
388 if (!(omode & O_NOFOLLOW) && (ip = follow(ip)) == 0) {
389 end_op();
390 return -1;
391 }
392
393 // a directory, or a link opened with O_NOFOLLOW, is read-only.
394 if ((ip->type == T_DIR || ip->type == T_SYMLINK) &&
395 (omode & ~O_NOFOLLOW) != O_RDONLY) {
396 iunlockput(ip);
397 end_op();
398 return -1;
360399 }
361400
362401 if (ip->type == T_DEVICE && (ip->major < 0 || ip->major >= NDEV)) {
363402 iunlockput(ip);
f2cb5b7 Resolve relative targets in the link's directory
kernel/sysfile.c
@@ -324,14 +324,35 @@ fail:
324324 iunlockput(dp);
325325 return 0;
326326}
327327
328// ip is a locked inode. While it is a symbolic link, replace it
329// by the inode its target names, following at most MAXSYMLINK
330// links. Returns a locked inode that is not a link, or 0 (with
331// ip released) if a target is missing or there are too many links.
328// path names a symbolic link whose content is target. Change
329// path to name what target names: target itself if it starts
330// with '/', otherwise target in the link's directory.
331static int
332resolve(char *path, char *target)
333{
334 int dirlen = strlen(path);
335
336 while (dirlen > 0 && path[dirlen - 1] == '/') // trailing slashes
337 dirlen--;
338 while (dirlen > 0 && path[dirlen - 1] != '/') // the link's name
339 dirlen--;
340 if (target[0] == '/')
341 dirlen = 0;
342 if (dirlen + strlen(target) >= MAXPATH)
343 return -1;
344 safestrcpy(path + dirlen, target, MAXPATH - dirlen);
345 return 0;
346}
347
348// ip is a locked inode, found by the name path (a MAXPATH buffer).
349// While ip is a symbolic link, replace it by the inode its target
350// names, following at most MAXSYMLINK links. Returns a locked
351// inode that is not a link, or 0 (with ip released) if a target
352// is missing or there are too many links.
332353static struct inode *
333follow(struct inode *ip)
354follow(struct inode *ip, char *path)
334355{
335356 char target[MAXPATH];
336357 int n, depth;
337358
@@ -344,9 +365,9 @@ follow(struct inode *ip)
344365 target[n] = 0;
345366 // release the link before looking up its target: namei locks
346367 // directories, and the target may lead through this very link.
347368 iunlockput(ip);
348 if ((ip = namei(target)) == 0)
369 if (resolve(path, target) < 0 || (ip = namei(path)) == 0)
349370 return 0;
350371 ilock(ip);
351372 }
352373 return ip;
@@ -384,9 +405,9 @@ sys_open(void)
384405 }
385406 ilock(ip);
386407 }
387408
388 if (!(omode & O_NOFOLLOW) && (ip = follow(ip)) == 0) {
409 if (!(omode & O_NOFOLLOW) && (ip = follow(ip, path)) == 0) {
389410 end_op();
390411 return -1;
391412 }
392413
b84332a Let open with O_CREATE follow an existing link
kernel/sysfile.c
@@ -279,9 +279,12 @@ create(char *path, short type, short major, short minor)
279279
280280 if ((ip = dirlookup(dp, name, 0)) != 0) {
281281 iunlockput(dp);
282282 ilock(ip);
283 if (type == T_FILE && (ip->type == T_FILE || ip->type == T_DEVICE))
283 // open(O_CREATE) of an existing name: a file or device is
284 // used as it is, and a symbolic link is left for open to follow.
285 if (type == T_FILE && (ip->type == T_FILE || ip->type == T_DEVICE ||
286 ip->type == T_SYMLINK))
284287 return ip;
285288 iunlockput(ip);
286289 return 0;
287290 }
5671d7a Add ln -s to make symbolic links from the shell
user/ln.c
@@ -4,10 +4,15 @@
44
55int
66main(int argc, char *argv[])
77{
8 if (argc == 4 && strcmp(argv[1], "-s") == 0) {
9 if (symlink(argv[2], argv[3]) < 0)
10 fprintf(2, "symlink %s %s: failed\n", argv[2], argv[3]);
11 exit(0);
12 }
813 if (argc != 3) {
9 fprintf(2, "Usage: ln old new\n");
14 fprintf(2, "Usage: ln [-s] old new\n");
1015 exit(1);
1116 }
1217 if (link(argv[1], argv[2]) < 0)
1318 fprintf(2, "link %s %s: failed\n", argv[1], argv[2]);
c818d2d Add symlinktest, a test program for symbolic links
Makefile
@@ -149,8 +149,9 @@ UPROGS=\
149149 $U/_logstress\
150150 $U/_forphan\
151151 $U/_dorphan\
152152 $U/_sync\
153 $U/_symlinktest\
153154
154155fs.img: mkfs/mkfs README $(UPROGS)
155156 mkfs/mkfs fs.img README $(UPROGS)
156157
user/symlinktest.c
@@ -0,0 +1,390 @@
1// Tests for symbolic links: symlink(), and open() following them.
2// Every check is done by the program itself; each prints OK or FAIL.
3
4#include "kernel/types.h"
5#include "kernel/stat.h"
6#include "kernel/fcntl.h"
7#include "kernel/fs.h"
8#include "kernel/param.h"
9#include "user/user.h"
10
11static int failed;
12
13static void
14result(char *name, int ok)
15{
16 printf("symlinktest: %s: %s\n", name, ok ? "OK" : "FAIL");
17 if (!ok)
18 failed = 1;
19}
20
21// write s into a new (or truncated) file.
22static int
23mkfile(char *path, char *s)
24{
25 int fd = open(path, O_CREATE | O_WRONLY | O_TRUNC);
26 if (fd < 0)
27 return -1;
28 int n = write(fd, s, strlen(s));
29 close(fd);
30 return n == strlen(s) ? 0 : -1;
31}
32
33// does opening path (with flags) give exactly the bytes s?
34static int
35hasdata(char *path, int flags, char *s)
36{
37 char buf[64];
38 int fd, n;
39
40 if ((fd = open(path, O_RDONLY | flags)) < 0)
41 return 0;
42 n = read(fd, buf, sizeof(buf) - 1);
43 close(fd);
44 if (n < 0)
45 return 0;
46 buf[n] = 0;
47 return strcmp(buf, s) == 0;
48}
49
50// fstat of path opened with flags; -1 if it cannot be opened.
51static int
52statof(char *path, int flags, struct stat *st)
53{
54 int fd, r;
55
56 if ((fd = open(path, O_RDONLY | flags)) < 0)
57 return -1;
58 r = fstat(fd, st);
59 close(fd);
60 return r;
61}
62
63static void
64cleanup(void)
65{
66 char name[32];
67 int i;
68
69 char *names[] = {"/stt/a", "/stt/l1", "/stt/l2", "/stt/rl", "/stt/rl2",
70 "/stt/later", "/stt/dl", "/stt/x", "/stt/y", "/stt/s",
71 "/stt/d/f", "/stt/d", "/stt/dlink", "/stt/sub", "/stt/b",
72 "/stt/lb", "/stt/f2", "/stt/tmp", "/stt/c/t", 0};
73 for (i = 0; names[i]; i++)
74 unlink(names[i]);
75 for (i = 0; i <= MAXSYMLINK; i++) {
76 strcpy(name, "/stt/c0");
77 name[6] = '0' + i % 10;
78 if (i == 10)
79 strcpy(name, "/stt/c10");
80 unlink(name);
81 }
82 for (i = 0; i < 4; i++) {
83 strcpy(name, "/stt/c/l0");
84 name[8] = '0' + i;
85 unlink(name);
86 }
87 unlink("/stt/c");
88 unlink("/stt");
89}
90
91static void
92basic(void)
93{
94 struct stat st, sa;
95 int fd, ok;
96
97 ok = symlink("/stt/a", "/stt/l1") == 0 && hasdata("/stt/l1", 0, "hello");
98 ok = ok && statof("/stt/l1", 0, &st) == 0 && statof("/stt/a", 0, &sa) == 0;
99 ok = ok && st.type == T_FILE && st.ino == sa.ino;
100 // writing through the link changes the target.
101 if (ok && (fd = open("/stt/l1", O_WRONLY)) >= 0) {
102 ok = write(fd, "HELLO", 5) == 5;
103 close(fd);
104 } else
105 ok = 0;
106 ok = ok && hasdata("/stt/a", 0, "HELLO");
107 result("basic", ok);
108}
109
110static void
111relative(void)
112{
113 int ok;
114
115 // "a" means a in the link's directory /stt, not in the
116 // current directory /, where there is no a.
117 ok = symlink("a", "/stt/rl") == 0 && open("/a", O_RDONLY) < 0;
118 ok = ok && hasdata("/stt/rl", 0, "HELLO");
119 ok = ok && mkdir("/stt/sub") == 0 && chdir("/stt/sub") == 0;
120 ok = ok && hasdata("../rl", 0, "HELLO");
121 chdir("/");
122 result("relative", ok);
123}
124
125static void
126dangling(void)
127{
128 int ok;
129
130 ok = symlink("/stt/later", "/stt/dl") == 0 && open("/stt/dl", O_RDONLY) < 0;
131 ok = ok && mkfile("/stt/later", "later") == 0 && hasdata("/stt/dl", 0, "later");
132 result("dangling", ok);
133}
134
135static void
136nofollow(void)
137{
138 struct stat st, sa;
139 int ok;
140
141 ok = statof("/stt/l1", O_NOFOLLOW, &st) == 0;
142 ok = ok && st.type == T_SYMLINK && st.size == 6 && st.nlink == 1;
143 ok = ok && hasdata("/stt/l1", O_NOFOLLOW, "/stt/a");
144 ok = ok && open("/stt/l1", O_RDWR | O_NOFOLLOW) < 0;
145 // the target's link count does not count symbolic links.
146 ok = ok && statof("/stt/a", 0, &sa) == 0 && sa.nlink == 1;
147 result("nofollow", ok);
148}
149
150static void
151chain(void)
152{
153 char name[16], target[16];
154 int i, ok = 1;
155
156 // c10 -> /stt/a, c9 -> c10, ..., c0 -> c1.
157 for (i = 0; i <= MAXSYMLINK; i++) {
158 strcpy(name, "/stt/c0");
159 name[6] = '0' + i;
160 strcpy(target, "c1");
161 target[1] = '0' + i + 1;
162 if (i == 9)
163 strcpy(target, "c10");
164 if (i == 10) {
165 strcpy(name, "/stt/c10");
166 strcpy(target, "/stt/a");
167 }
168 if (symlink(target, name) < 0)
169 ok = 0;
170 }
171 // from c1, MAXSYMLINK links lead to a; from c0, one too many.
172 ok = ok && hasdata("/stt/c1", 0, "HELLO");
173 ok = ok && open("/stt/c0", O_RDONLY) < 0;
174 ok = ok && symlink("/stt/l1", "/stt/l2") == 0 && hasdata("/stt/l2", 0, "HELLO");
175 result("chain", ok);
176}
177
178static void
179cycle(void)
180{
181 int ok;
182
183 ok = symlink("y", "/stt/x") == 0 && symlink("x", "/stt/y") == 0;
184 ok = ok && open("/stt/x", O_RDONLY) < 0;
185 ok = ok && symlink("s", "/stt/s") == 0 && open("/stt/s", O_RDONLY) < 0;
186 ok = ok && open("/stt/s", O_CREATE | O_RDWR) < 0;
187 result("cycle", ok);
188}
189
190static void
191directory(void)
192{
193 struct stat st, sd;
194 struct dirent de;
195 int fd, found = 0, ok;
196
197 ok = mkdir("/stt/d") == 0 && mkfile("/stt/d/f", "f") == 0;
198 ok = ok && symlink("d", "/stt/dlink") == 0;
199 ok = ok && statof("/stt/dlink", 0, &st) == 0 && statof("/stt/d", 0, &sd) == 0;
200 ok = ok && st.type == T_DIR && st.ino == sd.ino;
201 if (ok && (fd = open("/stt/dlink", O_RDONLY)) >= 0) {
202 while (read(fd, &de, sizeof(de)) == sizeof(de))
203 if (de.inum != 0 && strcmp(de.name, "f") == 0)
204 found = 1;
205 close(fd);
206 }
207 ok = ok && found;
208 ok = ok && open("/stt/dlink", O_RDWR) < 0;
209 result("directory", ok);
210
211 // only open follows, and only the last name in the path.
212 ok = open("/stt/dlink/f", O_RDONLY) < 0 && chdir("/stt/dlink") < 0;
213 result("not followed in the middle of a path or by chdir", ok);
214}
215
216static void
217createthrough(void)
218{
219 int ok;
220
221 // O_CREATE through a dangling link does not create the target.
222 ok = symlink("b", "/stt/lb") == 0;
223 ok = ok && open("/stt/lb", O_CREATE | O_WRONLY) < 0 && open("/stt/b", 0) < 0;
224 ok = ok && mkfile("/stt/b", "old") == 0 && mkfile("/stt/lb", "bb") == 0;
225 ok = ok && hasdata("/stt/b", 0, "bb");
226 result("create through a link", ok);
227}
228
229static void
230unlinks(void)
231{
232 struct stat st, sa;
233 int ok, ino;
234
235 // unlink removes the link, not the target.
236 ok = unlink("/stt/l1") == 0 && open("/stt/l1", O_RDONLY) < 0;
237 ok = ok && statof("/stt/a", 0, &sa) == 0 && sa.nlink == 1;
238 ok = ok && hasdata("/stt/a", 0, "HELLO");
239 result("unlink", ok);
240
241 // a hard link to a symbolic link counts in the link's nlink.
242 ok = link("/stt/rl", "/stt/rl2") == 0;
243 ok = ok && statof("/stt/rl2", O_NOFOLLOW, &st) == 0;
244 ok = ok && st.type == T_SYMLINK && st.nlink == 2;
245 ok = ok && unlink("/stt/rl") == 0 && hasdata("/stt/rl2", 0, "HELLO");
246 result("hard link to a symlink", ok);
247
248 // the inode of an unlinked symlink is freed: the next file gets it.
249 ok = symlink("/stt/a", "/stt/tmp") == 0;
250 ok = ok && statof("/stt/tmp", O_NOFOLLOW, &st) == 0;
251 ino = st.ino;
252 ok = ok && unlink("/stt/tmp") == 0 && mkfile("/stt/f2", "x") == 0;
253 ok = ok && statof("/stt/f2", 0, &st) == 0 && st.ino == ino;
254 result("unlinked symlink's inode freed", ok);
255}
256
257static void
258errors(void)
259{
260 int ok;
261
262 ok = symlink("", "/stt/e") < 0;
263 ok = ok && symlink("/stt/x", "/stt/a") < 0;
264 ok = ok && symlink("/stt/a", "/stt/nodir/x") < 0;
265 result("errors", ok);
266}
267
268// 3 processes create, remove and open the links /stt/c/l0..l3,
269// whose targets are t (a file) or another of the links. Each must
270// have reached t through links, and read links, at least once.
271static int
272worker(int id, int rounds, int out)
273{
274 char name[16], target[16], buf[16];
275 struct stat st;
276 unsigned int r = id * 7919 + 1;
277 int i, fd, n, made = 0, gone = 0, followed = 0, seen = 0;
278
279 for (i = 0; i < rounds; i++) {
280 r = r * 1103515245 + 12345;
281 strcpy(name, "/stt/c/l0");
282 name[8] = '0' + (r >> 8) % 4;
283 switch ((r >> 16) % 4) {
284 case 0:
285 if ((r >> 20) % 3 == 0)
286 strcpy(target, "t");
287 else {
288 strcpy(target, "l0");
289 target[1] = '0' + (r >> 24) % 4;
290 }
291 if (symlink(target, name) == 0)
292 made++;
293 break;
294 case 1:
295 if (unlink(name) == 0)
296 gone++;
297 break;
298 case 2: // following must end at t, or fail
299 if ((fd = open(name, O_RDONLY)) >= 0) {
300 n = read(fd, buf, sizeof(buf) - 1);
301 if (fstat(fd, &st) < 0 || st.type != T_FILE || n != 6 ||
302 memcmp(buf, "target", 6) != 0) {
303 printf("worker %d: bad follow of %s\n", id, name);
304 return 1;
305 }
306 followed++;
307 close(fd);
308 }
309 break;
310 case 3: // the link itself must hold a whole target
311 if ((fd = open(name, O_RDONLY | O_NOFOLLOW)) >= 0) {
312 n = read(fd, buf, sizeof(buf) - 1);
313 buf[n < 0 ? 0 : n] = 0;
314 if (fstat(fd, &st) < 0 || st.type != T_SYMLINK ||
315 (strcmp(buf, "t") != 0 &&
316 (n != 2 || buf[0] != 'l' || buf[1] < '0' || buf[1] > '3'))) {
317 printf("worker %d: bad link %s: '%s'\n", id, name, buf);
318 return 1;
319 }
320 seen++;
321 close(fd);
322 }
323 break;
324 }
325 }
326 // one small write into a pipe is not interleaved with others.
327 int counts[5] = {id, made, gone, followed, seen};
328 if (write(out, counts, sizeof(counts)) != sizeof(counts))
329 return 1;
330 // a run in which nothing was followed or read proves nothing.
331 return followed > 0 && seen > 0 ? 0 : 1;
332}
333
334static void
335concurrent(int rounds)
336{
337 int i, pid, xs, ok, fds[2], c[5];
338
339 ok = mkdir("/stt/c") == 0 && mkfile("/stt/c/t", "target") == 0;
340 ok = ok && pipe(fds) == 0;
341 for (i = 0; ok && i < 3; i++) {
342 pid = fork();
343 if (pid < 0)
344 ok = 0;
345 if (pid == 0) {
346 close(fds[0]);
347 exit(worker(i, rounds, fds[1]));
348 }
349 }
350 close(fds[1]);
351 for (i = 0; i < 3; i++) {
352 if (wait(&xs) < 0 || xs != 0)
353 ok = 0;
354 }
355 while (read(fds[0], c, sizeof(c)) == sizeof(c))
356 printf("symlinktest: worker %d: %d links made, %d removed, "
357 "%d opened through links, %d links read\n",
358 c[0], c[1], c[2], c[3], c[4]);
359 close(fds[0]);
360 result("concurrent", ok);
361}
362
363int
364main(int argc, char *argv[])
365{
366 int rounds = 2000;
367
368 if (argc > 1)
369 rounds = atoi(argv[1]);
370 chdir("/");
371 cleanup();
372 if (mkdir("/stt") < 0 || mkfile("/stt/a", "hello") < 0) {
373 printf("symlinktest: cannot set up /stt\n");
374 exit(1);
375 }
376 basic();
377 relative();
378 dangling();
379 nofollow();
380 chain();
381 cycle();
382 directory();
383 createthrough();
384 unlinks();
385 errors();
386 concurrent(rounds);
387 cleanup();
388 printf("symlinktest: %s\n", failed ? "SOME TESTS FAILED" : "ALL OK");
389 exit(failed);
390}

6. Verify and measure

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.

What a link costs on disk, and in the log. An instrumented copy of the kernel printed the log just before sys_symlink’s end_op (instrumentation not on the branch):

link	blocks logged
`d/l`, link and `d` in the same inode block (the reveal’s run)	4: inode block, `d`’s entries, bitmap, link data
`/m/1` … `/m/3` (same inode block as `/m`)	4
`/m/4` … `/m/a` (a new inode block)	5
`/g/l`, in a directory whose first block was full	5: inode block, bitmap (once, for two new blocks), the new directory block, `/g`’s inode block, link data
`l1` in `/`	5

Every link uses one inode and one whole 1024-byte block, whatever the length of its target. A transaction never came near the MAXOPBLOCKS of 10 that begin_op reserves.

What following costs. The same instrumented kernel counted calls to bread during one open (all were cache hits: 0 disk reads), and the plain branch timed 10,000 open+close pairs with uptime (one tick is about 0.1 s; measured while the computer was busy with other work, so your times will differ and only the ratios mean much):

`open` of	`bread` calls	10,000 opens
`/m/f` (the file)	33	113 ticks
`/m/1` → `f` (1 link)	68	233 ticks
`/m/a` → `9` → … → `1` → `f` (10 links)	428	1,485 ticks

A link roughly doubles the cost of an open, because following is a second full path lookup. After the first lookup and one bread for the link’s own block, the resolved path is looked up again from the start: dirlookup reads the entries of / up to m, then those of /m, once more, one bread per 16-byte entry. Ten links cost about thirteen lookups. That is the price of the simple design (look up the whole resolved path again from the start), and one reason real kernels cache name lookups.

7. Go further

Follow links in the middle of a path. Move following into namex: when a middle component is a link, splice its target in front of the rest of the path and go on, with one depth count for the whole lookup. Then cd dl, cat dl/f and running programs through links work. You will have to decide, for each caller of namei and nameiparent, whether its last component is followed, and redo this lab’s locking argument inside namex, where a directory is locked.
lstat and readlink. O_NOFOLLOW + fstat + read is a workable lstat and readlink; add them as system calls and teach ls to show links (type 4) with their targets instead of following them.
Fast symlinks. Store targets shorter than 52 bytes in addrs[] itself instead of a data block, as ext2 does: no block, one fewer bitmap update, and a lookup that reads no data block. Count the blocks saved with the measurement above.
O_CREATE through a dangling link. Make open(link, O_CREATE) create the missing target, as Linux does. Work out which directory it must be created in, and what must be locked while you do.