Directory structure — tree, DAG (hard links, symbolic links): Worked examples

This page is the "put the theory to work" companion to the parent topic. We will not introduce new theory — instead we enumerate every kind of situation the topic can throw at you, then solve one worked example for each. If a symbol shows up (like the link count $n$ ), it was defined in the parent; we re-anchor it here so you never have to scroll back.

The scenario matrix

Think of the "inputs" to this topic as three knobs: which kind of link (hard / soft), what happens to the target (created / deleted / renamed), and what boundary we cross (same FS / other FS / a directory). The interesting behaviour lives at the corners.

Cell	Case class	What's special / degenerate	Covered by
C1	Hard link, count goes up then down, data survives	ordinary DAG case	Example 1
C2	Hard link, count reaches $n = 0$	degenerate: data actually freed	Example 2
C3	Open handle holds inode while $n = 0$	limiting case of the free rule	Example 3
C4	Symlink to a live target vs a deleted target	dangling / broken-link boundary	Example 4
C5	Symlink target renamed (not deleted)	text-vs-inode subtlety	Example 5
C6	Cross-filesystem attempt	hard fails, soft succeeds	Example 6
C7	Link to a directory	hard forbidden, soft allowed	Example 7
C8	Symlink chain / loop (limiting `ELOOP`)	traversal cycle, depth cap	Example 8
C9	Real-world word problem (versioned release)	applied reasoning	Example 9
C10	Exam twist: count a mixed `ls -li` table	reading link counts cold	Example 10

Recall The two numbers you must track in every example

Every example is really about two counters. What is the link count $n$ ? ::: the number of directory entries (dentries) pointing at an inode (on-disk). What is the open-handle count $f$ ? ::: the number of open file descriptors processes hold on the inode (in-memory). What is the exact free condition? ::: data freed $⟺ (n = 0) \land (f = 0)$ .

Example 1 — Hard link, count up then down (cell C1)

Worked example Statement

$ echo hi > a.txt      # (i)
$ ln a.txt b.txt       # (ii)
$ ln a.txt c.txt       # (iii)
$ rm b.txt             # (iv)

After these four lines, what is the link count on the inode, and can you still read the data via c.txt?

Forecast: guess the final count and whether c.txt works before reading on.

The figure below tracks $n$ as a running bar chart, one bar per line of the script — watch it climb then dip.

Figure — Directory structure — tree, DAG (hard links, symbolic links)

Line (i): echo hi > a.txt creates a brand-new inode (call it inode 42) with one directory entry a.txt. Why this step? A fresh file starts with exactly one name, so $n = 1$ (first bar).
Line (ii): ln a.txt b.txt adds a second dentry to the same inode 42. Why this step? A hard link is another name for the same inode — the parent note's rule is $n \leftarrow n + 1$ , so $n = 2$ (bar rises).
Line (iii): ln a.txt c.txt adds a third dentry. Why this step? Same rule again: $n \leftarrow n + 1$ , so $n = 3$ (bar peaks).
Line (iv): rm b.txt calls unlink, which removes the name b.txt and decrements: $n \leftarrow n - 1$ , so $n = 2$ (bar dips, the coral step in the figure). Why this step? rm removes a name, not data. Data survives while $n > 0$ .

Final count $n = 1 + 1 + 1 - 1 = 2$ . Since $n = 2 > 0$ , the blocks are alive, so cat c.txt prints hi. ✅

Verify: Count the surviving names: a.txt, c.txt → exactly 2 dentries → $n = 2$ . Matches. c.txt still references inode 42, so the read succeeds.

Example 2 — Count hits zero, data freed (cell C2, degenerate)

Forecast: at which rm does the actual data die?

After echo + ln: $n = 2$ (two names for inode 42). Why this step? Same up-count logic as Example 1.
rm a.txt: $n \leftarrow n - 1 = 1$ . Data not freed. Why this step? The free rule is $(n = 0) \land (f = 0)$ . Here $n = 1$ , so the condition is false.
rm b.txt: $n \leftarrow n - 1 = 0$ . Now $n = 0$ and $f = 0$ . Why this step? Both halves of $(n = 0) \land (f = 0)$ are true, so the kernel returns the inode and its data blocks to the free list.

The data is freed only at the second rm, not the first.

Verify: Reachability argument from the parent: "any path can reach the data" $\Leftrightarrow$ "at least one dentry exists" $\Leftrightarrow n > 0$ . After both removals, zero dentries exist, so no path reaches it — freeing is correct. $2 - 1 - 1 = 0$ . ✅

Example 3 — Open handle keeps data alive at $n = 0$ (cell C3, limiting)

Forecast: does rm free the space while the writer is still running?

The figure shows the two counters $n$ (lavender) and $f$ (mint) as timelines; the data lives until both hit the floor.

rm log.txt → unlink → $n \leftarrow 0$ , but $f$ is still $1$ . Why this step? The last (and only) name is gone, so the dentry count drops to zero — the lavender line drops.
The writer still holds an open file descriptor → $f = 1$ . Why this step? The full free rule is $(n = 0) \land (f = 0)$ . Here $f = 1$ , so the AND is false — data not freed (mint line still high).
The blocks are released the instant the process closes the fd (or exits), making $f = 0$ while $n$ is already $0$ . Why this step? Only when both references vanish does the AND become true — both lines on the floor.

Verify: Truth table of the free condition:

$n$ $f$ free?

1 1 no

0 1 no ← this example, mid-write

1 0 no

0 0 yes ← after close

Only the last row frees. Matches "space reclaimed on close". ✅

$n$	$f$	free?
1	1	no
0	1	no ← this example, mid-write
1	0	no
0	0	yes ← after close

Example 4 — Symlink to live vs deleted target (cell C4)

Worked example Statement

$ echo hi > a.txt       # inode 42, n=1
$ ln -s a.txt s.txt     # inode 99, its data is the TEXT "a.txt"

(a) What is a.txt's link count now? (b) cat s.txt — what happens? (c) Then rm a.txt and cat s.txt again — what happens?

Forecast: does making the symlink change a.txt's count?

ln -s a.txt s.txt makes a new inode 99 whose data block just stores the string "a.txt". Why this step? A symlink is a special file holding a path string — "Hard counts, Soft doesn't." So a.txt's count stays $n = 1$ . → answer (a) is 1.
cat s.txt: kernel reads inode 99, sees it's type l, reads the text "a.txt", restarts lookup on a.txt, finds inode 42, prints hi. → answer (b) is hi. Why this step? Resolving a symlink = "read the string, then re-run path lookup."
rm a.txt: a.txt's count goes $1 \to 0$ , $f = 0$ , so inode 42 is freed. Now s.txt still stores "a.txt" but that name is gone. Why this step? The symlink never touched inode 42's count, so nothing protected it.
cat s.txt: lookup of "a.txt" fails → No such file or directory — a dangling link. → answer (c) is the error.

Verify: Sign check on counts: symlink creation added $0$ to the target's count ( $1 + 0 = 1$ ), while a hard link would have added $1$ . The dangling behaviour is exactly the "signpost points at nothing" picture. ✅

Example 5 — Symlink survives a rename only if the name matches (cell C5)

Forecast: rename isn't delete — will the signpost still find it?

s stores the literal text "report.txt". Why this step? Symlinks resolve by name, not by inode number.
mv changes the directory entry name from report.txt to report_final.txt (same inode, just a new name). Why this step? The data and inode are untouched, but the name the symlink hunts for no longer exists.
Resolution of s looks up "report.txt" → not found → s is now dangling, even though the data is perfectly alive under a new name. Why this step? This is the sharp difference vs a hard link: a hard link points at the inode and would not care about renames.

Verify: Contrast case — if s had been a hard link (ln report.txt s), it points at the inode; mv only changes the other name, so cat s would still print the data. Two links, two behaviours, one rename — exactly the "points at path vs points at inode" distinction. ✅

Example 6 — Cross-filesystem: hard fails, soft wins (cell C6)

Worked example Statement

/mnt/usb/movie.mp4 lives on a USB filesystem. From your home directory (on the root filesystem) you try both:

$ ln    /mnt/usb/movie.mp4 ~/film     # (a) hard
$ ln -s /mnt/usb/movie.mp4 ~/film     # (b) soft

Which succeeds, and why?

Forecast: which one gives Invalid cross-device link?

(a) hard link fails with EXDEV: Invalid cross-device link. Why this step? A hard link stores an inode number, and inode numbers are only meaningful within one filesystem. Inode 500 on the USB and inode 500 on root are different files, so a dentry in ~ cannot legally name a USB inode.
(b) soft link succeeds. Why this step? A symlink stores only a path string "/mnt/usb/movie.mp4". Strings don't care which filesystem they cross; resolution just re-runs namei() from that path.

Verify: Constraint table from the parent — "cross-filesystem? Hard = No, Soft = Yes." The mechanism (inode number is FS-local vs path is universal) is the why behind that table row. ✅

Example 7 — Linking to a directory (cell C7)

Forecast: why would the OS refuse one of these?

Look at the figure: on the left, a hard link from a directory back toward its ancestor closes a loop (the dashed coral arrow) — a recursive walk following the black parent-arrow down and the coral arrow up would circle forever. On the right, the butter-yellow symlink is just a text signpost into /var/log; even a loop of such signposts is cut off by the kernel's hop cap.

(a) hard link to a directory → refused (EPERM/Operation not permitted for users). Why this step? As the left panel shows, every directory already has . and ... If users could hard-link a directory into an ancestor, you'd create a cycle among directories, and a recursive walk (find, du, recursive rm) would loop forever. Also the link-count-as-reachability idea breaks. So the kernel bans it.
(b) symlink to a directory → allowed. Why this step? As the right panel shows, a symlink is just text; the kernel caps symlink-chain depth (e.g. ELOOP after ~40 hops), so even accidental loops terminate.

Verify: The DAG rule from the parent: we forbid cycles among directories so traversal terminates. A directory hard link would inject a cycle → banned. A symlink cycle is bounded by the depth cap → allowed. Consistent. ✅

Example 8 — Symlink loop and the `ELOOP` limit (cell C8, limiting)

Forecast: predict the error and why it's bounded.

a stores "b", b stores "a" — a two-node cycle of signposts. Why this step? Each symlink resolves to the other by name, so lookup ping-pongs a → b → a → b ….
If unbounded, namei() would never terminate. So the kernel counts hops and aborts once the chain exceeds a fixed limit (commonly 40), returning ELOOP: Too many levels of symbolic links. Why this step? This is the limiting-value safeguard: unlike hard links (which can never form a cycle by construction), symlinks can, so the depth cap is the safety net.

Verify: Model the resolver as a counter starting at 0, incrementing each hop, failing at $> 40$ . For the loop $a \to b$ , the counter marches $1, 2, 3, \dots$ and provably crosses 40 in finite steps → terminates with ELOOP. So it cannot hang. ✅

Example 9 — Real-world word problem: atomic release swap (cell C9)

Forecast: hard link or symlink? And why does it feel "instant"?

Make current a symlink: ln -s /srv/www/v1 current. Why this step? You need to point at a directory and possibly across mounts — only a symlink can point at a directory (Example 7). It also stores a path, so re-pointing is a single text change.
To switch, atomically replace the symlink: ln -sfn /srv/www/v2 current (the -s makes it a symlink, -f overwrites the existing current, -n stops it from diving into the old directory). Equivalently, mv -T newlink current. Why this step? Replacing the symlink is one rename operation → the server sees either the old target or the new target, never a half state. Reversible: point back to v1 the same way.
Count bookkeeping: the directories v1 and v2 keep their own link counts unchanged (a symlink adds $0$ ). Only one inode — the current symlink — has its stored text swapped. Why this step? "Soft doesn't count," so this whole scheme leaves every real directory's $n$ untouched.

Verify: Impact tally: directory v1 count change $= 0$ , v2 count change $= 0$ , number of symlink inodes involved $= 1$ . Total link-count deltas across the switch $= 0$ . Matches "symlink creation/repoint never bumps target count." ✅

Example 10 — Exam twist: read the `ls -li` table cold (cell C10)

Worked example Statement

Given this listing, answer: (a) how many distinct regular-file data blobs are on disk? (b) which entries share data? (c) which is a symlink, and does it protect its target from deletion?

42 -rw-r--r-- 2 root root 3 a.txt
42 -rw-r--r-- 2 root root 3 b.txt
99 lrwxrwxrwx 1 root root 5 s.txt -> a.txt
71 -rw-r--r-- 1 root root 8 c.txt

The columns are: inode number, permissions (first char = type), link count $n$ , owner, group, size, name.

Forecast: count the inodes, not the names.

Read the first column (inode number) and the first character of the permissions column (the type): - = regular file, l = symlink. Why this step? Distinct data = distinct inode numbers, not distinct names; and the type char tells you whether an inode holds real data or just a path string.
Inode numbers present: 42, 99, 71. Inode 99 is a symlink (type l) whose "data" is merely the text a.txt (size 5 = length of "a.txt"). So the distinct regular-file data blobs are inode 42 and inode 71 → 2. → (a) answer 2 (plus 1 symlink inode, which stores no file data of its own). Why this step? We must not count the symlink inode as a data blob — it's a signpost.
a.txt and b.txt both show inode 42 with link count 2 → they are two hard links sharing one data blob. → (b) a.txt ⇄ b.txt share data. Why this step? Same inode number + count $2$ = two names, one inode.
s.txt (inode 99, type l) is the symlink; it stores the text "a.txt". It did not contribute to inode 42's count (which is $2$ = the two hard links). Now the twist: deleting the name a.txt leaves inode 42's data alive via b.txt (count drops $2 \to 1$ ), but s.txt resolves by the name "a.txt", which is now gone → s.txt dangles. So the symlink does not protect its target and is itself fragile to renames/deletes of that name. → (c) s.txt is the symlink; it does not protect its target. Why this step? Symlinks resolve by name (Example 5); "Soft doesn't count."

Verify: Cross-checks: number of inode-42 dentries in the listing $= 2$ → matches printed count 2. Inodes whose printed count is 1: s.txt(99) and c.txt(71) → each name appears exactly once → matches. Distinct regular-file data inodes $= {42, 71}$ , size $= 2$ . All consistent. ✅

Connections

Inodes and File Metadata
Reference Counting and Garbage Collection
Path Resolution and the namei() routine
Unix system calls — link, unlink, symlink, stat
Mount points and Virtual File System (VFS)
Graphs — Trees vs DAGs
File System Implementation — Block Allocation