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

WHAT the columns mean: the first number is the inode; the number after permissions (2, 2, 1) is the link count.

• a.txt → inode 42, b.txt → inode 42, s.txt → inode 99.
• a.txt and b.txt share inode 42, so they are the same file (a hard-link pair). Their link count is 2, confirming exactly two names point at inode 42.
• s.txt has its own inode 99 and type char l — it is a symlink, a different file whose data is the text "a.txt".

• a.txt, b.txt: type char - → a regular file.
• s.txt: type char ==l== → a symbolic link. The type char is the very first character of the permission string.

• ln a.txt b.txt: add a name → $n=1+1=2$.
• ln a.txt c.txt: add a name → $n=2+1=3$.
• rm b.txt: rm calls unlink, remove a name → $n=3-1=2$. Final link count = 2 (names a.txt and c.txt remain). The data is fully intact.

• A symlink does not bump the target's count: a.txt stays at $n=1$.
• Two inodes now exist: inode for a.txt, and a separate inode for s.txt (its data = the string "a.txt"). Contrast with a hard link, which would have made count $2$ and created no new inode.

The full free condition from the parent note is: free when $n=0$ AND open$=0$.

See the figure below. Directory d has two entries x and y, both pointing at the same inode (call it 42). That inode therefore has in-degree 2 (two incoming edges). A tree requires every node to have exactly one parent/incoming edge, so this is not a tree — it is a DAG. No cycle exists (edges only go parent→child), so it is acyclic.

WHY it fails: a hard link is a (name, inode_number) entry, and inode numbers are only meaningful within one filesystem. ~ and /mnt/usb are different filesystems, so inode 42 on the USB has no meaning in the home filesystem — hence Invalid cross-device link (EXDEV). Fix: use a symlink, which stores a path string, not an inode number, and so crosses filesystems freely:

ln -s /mnt/usb/movie.mp4 ~/film

Symlinks can do it:

ln -s loop b        # b -> loop
ln -s b loop        # loop -> b
cat loop            # resolves loop->b->loop->b->...

Each resolution jumps to another path, and the two paths point at each other, so name resolution never terminates on its own. How the kernel stops it: it caps the symlink chain depth (commonly ~40 hops) and returns ==ELOOP== ("Too many levels of symbolic links"). Why hard links can't cause this: directory hard links are forbidden for users, so hard links can only add names to file inodes — no cycle among directories is possible, keeping the directory graph a DAG.

A directory's incoming references are: (1) its name in its parent, plus (2) its own . entry (which points at itself), plus (3) one .. entry from each child subdirectory (each child's .. points back at this directory).

• Empty d: name (1) + . (1) + zero children = $n=2$.
• After mkdir d/sub: the new child sub contributes a .. pointing at d, so $n=2+1=3$.
• General formula, with $k$ = number of immediate subdirectories: $n_{\text{dir}}=2+k$ WHY the "2": the constant 2 is the directory's own name plus its . self-link — present even when empty. Each subdirectory then adds exactly one via its ...

Solve $5=2+k\Rightarrow k=3$ immediate subdirectories. Regular files do not affect this count: a regular file's name is its own inode's link count, not the directory's. Only subdirectories add a .. back-reference, so the directory's link count reveals its number of child directories — a neat forensic trick used by tools like find.

Hard link changes target's count by ::: +1 (creation) or −1 (unlink) Symlink changes target's count by ::: 0 (it stores text, not an inode reference) Data freed exactly when ::: link count $n=0$ AND no process has it open Empty directory link count ::: 2 (its name + its own .) Directory link count formula ::: $n=2+k$, where $k$ = number of subdirectories Cross-filesystem link must be a ::: symlink (hard links can't cross filesystems) Kernel error stopping symlink cycles ::: ELOOP