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

1. What is a directory, really?

2. Tree structure (the default)

WHY a tree is convenient: unique path ⇒ unique name ⇒ deletion is trivial (one entry, free the inode). HOW we walk it: start at /, split path on /, look up each component's inode in the current directory, repeat.

Even a "pure tree" secretly has two special entries in every directory:

. → the directory's own inode
.. → the parent's inode

These make the directory graph technically cyclic for directories, which is exactly why we ban user-created directory hard links (more below).

3. Hard links → the DAG

Worked example Hard link in action

$ echo hi > a.txt        # inode 42, link count = 1
$ ln a.txt b.txt         # b.txt → inode 42, link count = 2
$ ls -li
42 -rw-r--r-- 2 ... a.txt
42 -rw-r--r-- 2 ... b.txt   # SAME inode 42, count "2"
$ rm a.txt               # count -> 1, data still alive
$ cat b.txt
hi                       # still readable!

Why this step? rm a.txt only removes the name and decrements the count; data survives because b.txt still references inode 42.

Constraints on hard links (and WHY):

Cannot cross filesystems — inode numbers are only meaningful within one filesystem.
Cannot hard-link directories (for users) — would create cycles, breaking traversal & making link count undefined for "reachability". (Kernel itself uses ./.. carefully.)

4. Symbolic (soft) links

Worked example Symlink behaviour

$ echo hi > a.txt          # inode 42
$ ln -s a.txt s.txt        # s.txt is inode 99, data = "a.txt"
$ ls -li
42 -rw-r--r-- 1 ... a.txt
99 lrwxrwxrwx 1 ... s.txt -> a.txt   # NEW inode, type 'l'
$ rm a.txt
$ cat s.txt
cat: s.txt: No such file or directory   # dangling!

Why this step? s.txt only stored the text "a.txt"; once that name vanishes, resolution fails. Note a.txt link count stayed 1 — symlink creation does not bump the target's count.

Worked example Symlinks CAN do what hard links can't

$ ln -s /mnt/usb/movie.mp4 ~/film    # cross-filesystem: fine!
$ ln -s /var/log mylog               # link to a DIRECTORY: fine!

Why this step? A symlink stores only a path string, so it has no inode-number / same-filesystem restriction and no cycle danger for traversal (the kernel limits symlink chain depth, e.g. ELOOP after ~40 hops).

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

5. Side-by-side (the 80/20 table)

Property	Hard link	Symbolic link
Points to	inode	path string
Own inode?	No (shares target's)	Yes (separate inode)
Bumps target link count?	Yes	No
Survives target deletion?	Yes (until count 0)	No → dangling
Cross-filesystem?	No	Yes
Link to directory?	No (users)	Yes
`ls -l` type char	`-` (normal)	==`l`==

Common mistake Steel-manned misconceptions

A) "rm deletes the file." Why it feels right: in everyday use one name = one file. The truth: rm calls unlink, which removes a name and decrements the link count. Data dies only at count 0 (and no open fd). Fix: think "unlink", not "delete".

B) "A symlink keeps the file alive like a hard link." Why it feels right: both "point to" the file. The truth: a symlink stores text, doesn't touch the link count, so deleting the target breaks it. Fix: hard link = reference (counted); symlink = pointer (uncounted).

C) "Copying a hard-linked file copies one and leaves the other." Why it feels right: they look like two files. The truth: editing in place via either name changes the same data. Fix: one inode, two doors into the same room.

D) "Filesystem is a tree." Why it feels right: it looks like one in a file explorer. The truth: with hard links it's a DAG; with symlinks you can even create traversal cycles (which is why kernels cap symlink depth). Fix: tree is the default, DAG is reality.

Recall Feynman: explain it to a 12-year-old

Imagine a big toy box (the data) with a label number painted on it. A hard link is a sticker on the wall that says "toy box #42." You can put many stickers in different rooms all saying "#42" — they all open the same box. The box keeps a little counter of how many stickers point to it; the box is only thrown away when the last sticker is removed. A symbolic link is different: it's a sticky note that just says "go to the kitchen and look for the box called teddy." If someone renames the kitchen box, your sticky note now points nowhere — a dead note. Because many stickers can point to one box, the map of names isn't a simple family tree anymore; it's a web that never loops back on itself — a DAG.

Connections

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

What does a directory entry (dentry) map?

A human-readable name to an inode number.

Where is a file's name stored — inode or directory?

In the directory (the inode holds metadata + data pointers, not the name).

Why is a filesystem with hard links a DAG instead of a tree?

Multiple paths/names can reach the same inode (in-degree >1), but directory cycles are forbidden, so it's acyclic.

What is a hard link?

An additional directory entry pointing to the same inode; a true co-equal name.

What is the inode link count and when are data blocks freed?

Number of dentries referencing the inode; blocks freed only when link count = 0 AND no process has it open.

Does creating a symlink change the target's link count?

No — a symlink has its own inode and only stores the target's path as text.

What is a dangling symlink?

A symlink whose target path no longer exists, so resolution fails.

Two things a symlink can do that a hard link cannot?

Cross filesystems, and link to a directory.

Why can't users hard-link directories?

It could create cycles, breaking traversal and reference counting.

What does rm actually call, and what does it do?

unlink(); removes one name and decrements the inode link count.

ls -l first character for a symlink?

'l'.

Mnemonic for hard vs soft links?

Hard points at the HEART (inode); Soft points at the SPOT (path). Hard counts, Soft doesn't.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, filesystem ka asli kaam ek hi hai: naam do, data dhoondh ke do. Iske liye Unix mein name aur data ko alag rakhte hain. Data + metadata ek structure mein hota hai jise inode kehte hain, aur directory sirf ek table hai jisme (naam, inode number) ke pairs hote hain. Isi separation ki wajah se ek hi file ke kai naam ho sakte hain.

Hard link ka matlab — ek aur directory entry jo same inode ko point karti hai. Dono naam barabar hain, koi "asli" koi "copy" nahi. Inode ek link count rakhta hai = kitne naam usse point kar rahe hain. rm actually unlink call karta hai jo count ko 1 kam karta hai; data tabhi delete hota hai jab count 0 ho jaye (aur koi process file open na rakhe). Isiliye agar a.txt aur b.txt hard link hain, rm a.txt ke baad bhi b.txt se data padh sakte ho.

Symbolic link (symlink) thoda alag hai — ye ek alag inode wali special file hai jiske andar bas ek path ka text likha hota hai, jaise sticky note "wahan jao". Symlink target ki link count nahi badhata. Isliye agar target delete ho gaya to symlink dangling (toot jaata) ho jaata hai. Plus point: symlink dusre filesystem par bhi point kar sakta hai aur directory ko bhi link kar sakta hai — hard link ye dono nahi kar sakta.

Ek line yaad rakho: Hard = HEART (inode) pe point, counted; Soft = SPOT (path) pe point, not counted. Jaise hi ek file ke do alag path ban jaate hain, structure tree nahi rehta — wo DAG ban jaata hai (cycles allowed nahi, isliye directory hard links ban allowed nahi).

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

1. What is a directory, really?

2. Tree structure (the default)

3. Hard links → the DAG

4. Symbolic (soft) links

5. Side-by-side (the 80/20 table)

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Operating Systems

Connections