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

4.2.33 · D3 · Coding › Operating Systems › Directory structure — tree, DAG (hard links, symbolic links)

Yeh page parent topic ki "theory ko kaam mein lagao" companion hai. Hum koi nayi theory introduce nahi karenge — balki hum har tarah ki situation enumerate karenge jo yeh topic throw kar sakta hai, phir har ek ke liye ek worked example solve karenge. Agar koi symbol dikhta hai (jaise link count $n$ ), woh parent mein define hua tha; hum use yahan re-anchor karte hain taaki tumhe kabhi scroll back na karna pade.

Scenario matrix

Is topic ke "inputs" ko teen knobs ki tarah socho: kaunsi tarah ka link (hard / soft), target ke saath kya hota hai (created / deleted / renamed), aur hum kaunsi boundary cross karte hain (same FS / other FS / ek directory). Interesting behaviour corners par rehta hai.

Cell	Case class	Kya special / degenerate hai	Covered by
C1	Hard link, count upar phir neeche jaata hai, data bachta hai	ordinary DAG case	Example 1
C2	Hard link, count $n = 0$ tak pahunchta hai	degenerate: data actually free hota hai	Example 2
C3	Open handle inode ko hold karta hai jab $n = 0$ ho	free rule ka limiting case	Example 3
C4	Symlink ek live target vs ek deleted target par	dangling / broken-link boundary	Example 4
C5	Symlink target renamed (deleted nahi)	text-vs-inode subtlety	Example 5
C6	Cross-filesystem attempt	hard fail hota hai, soft succeed karta hai	Example 6
C7	Ek directory se link	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: ek mixed `ls -li` table count karo	link counts cold padhna	Example 10

Recall Do numbers jo tumhe har example mein track karne chahiye

Har example asal mein do counters ke baare mein hai. Link count $n$ kya hai? ::: directory entries (dentries) ki sankhya jo ek inode ko point karti hain (on-disk). Open-handle count $f$ kya hai? ::: open file descriptors ki sankhya jo processes inode par hold karte hain (in-memory). Exact free condition kya hai? ::: data freed $⟺ (n = 0) \land (f = 0)$ .

Example 1 — Hard link, count upar phir neeche (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)

In chaar lines ke baad, inode par link count kya hai, aur kya tum abhi bhi c.txt ke zariye data padh sakte ho?

Forecast: aage padhne se pehle final count aur kya c.txt kaam karega guess karo.

Neeche di gayi figure $n$ ko ek running bar chart ke roop mein track karti hai, script ki har line ke liye ek bar — dekho yeh kaise chadhta hai phir girta hai.

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

Line (i): echo hi > a.txt ek brand-new inode (isse inode 42 kaho) create karta hai jisme ek directory entry a.txt hai. Yeh step kyun? Ek fresh file bilkul ek naam se start hoti hai, toh $n = 1$ (pehla bar).
Line (ii): ln a.txt b.txt usi inode 42 mein ek doosra dentry add karta hai. Yeh step kyun? Hard link usi inode ke liye ek aur naam hai — parent note ka rule hai $n \leftarrow n + 1$ , toh $n = 2$ (bar chadhta hai).
Line (iii): ln a.txt c.txt ek teesra dentry add karta hai. Yeh step kyun? Wohi rule phir: $n \leftarrow n + 1$ , toh $n = 3$ (bar peak par).
Line (iv): rm b.txt unlink call karta hai, jo naam b.txt hata deta hai aur decrement karta hai: $n \leftarrow n - 1$ , toh $n = 2$ (bar girta hai, figure mein coral step). Yeh step kyun? rm ek naam remove karta hai, data nahi. Data tab tak bachta hai jab tak $n > 0$ ho.

Final count $n = 1 + 1 + 1 - 1 = 2$ . Kyunki $n = 2 > 0$ hai, blocks alive hain, toh cat c.txt hi print karta hai. ✅

Verify: Surviving names count karo: a.txt, c.txt → exactly 2 dentries → $n = 2$ . Match karta hai. c.txt abhi bhi inode 42 ko reference karta hai, toh read succeed karti hai.

Example 2 — Count zero hit karta hai, data free hota hai (cell C2, degenerate)

Forecast: kis rm par actual data marega?

echo + ln ke baad: $n = 2$ (inode 42 ke liye do naam). Yeh step kyun? Example 1 jaisi hi up-count logic.
rm a.txt: $n \leftarrow n - 1 = 1$ . Data free nahi hua. Yeh step kyun? Free rule hai $(n = 0) \land (f = 0)$ . Yahan $n = 1$ hai, toh condition false hai.
rm b.txt: $n \leftarrow n - 1 = 0$ . Ab $n = 0$ aur $f = 0$ . Yeh step kyun? $(n = 0) \land (f = 0)$ ke dono halves true hain, toh kernel inode aur uske data blocks ko free list mein wapas kar deta hai.

Data sirf doosre rm par free hota hai, pehle par nahi.

Verify: Parent se reachability argument: "koi bhi path data tak pahunch sakta hai" $\Leftrightarrow$ "kam se kam ek dentry exist karta hai" $\Leftrightarrow n > 0$ . Dono removals ke baad, zero dentries exist karti hain, toh koi path nahi pahunch sakta — freeing sahi hai. $2 - 1 - 1 = 0$ . ✅

Example 3 — Open handle data ko $n = 0$ par bhi alive rakhta hai (cell C3, limiting)

Forecast: kya rm space free karta hai jabki writer abhi bhi chal raha hai?

Figure do counters $n$ (lavender) aur $f$ (mint) ko timelines ke roop mein dikhati hai; data tab tak jeeta hai jab tak dono floor par na aa jaayein.

rm log.txt → unlink → $n \leftarrow 0$ , lekin $f$ abhi bhi $1$ hai. Yeh step kyun? Aakhri (aur ek hi) naam chala gaya, toh dentry count zero ho jaata hai — lavender line girती hai.
Writer abhi bhi ek open file descriptor hold karta hai → $f = 1$ . Yeh step kyun? Poora free rule hai $(n = 0) \land (f = 0)$ . Yahan $f = 1$ hai, toh AND false hai — data free nahi hua (mint line abhi bhi high hai).
Blocks tab release hote hain jab process fd close kare (ya exit ho jaaye), jisse $f = 0$ ho jaata hai jabki $n$ pehle se $0$ hai. Yeh step kyun? Sirf jab dono references gayab hote hain tab AND true hota hai — dono lines floor par.

Verify: Free condition ka truth table:

$n$ $f$ free?

1 1 nahi

0 1 nahi ← yeh example, mid-write

1 0 nahi

0 0 haan ← close ke baad

Sirf aakhri row free karta hai. "Space reclaimed on close" se match karta hai. ✅

$n$	$f$	free?
1	1	nahi
0	1	nahi ← yeh example, mid-write
1	0	nahi
0	0	haan ← close ke baad

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

Worked example Statement

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

(a) Ab a.txt ka link count kya hai? (b) cat s.txt — kya hoga? (c) Phir rm a.txt aur dobara cat s.txt — kya hoga?

Forecast: kya symlink banana a.txt ka count change karta hai?

ln -s a.txt s.txt ek naya inode 99 banata hai jiska data block sirf string "a.txt" store karta hai. Yeh step kyun? Ek symlink ek special file hai jo ek path string hold karti hai — "Hard counts, Soft doesn't." Toh a.txt ka count $n = 1$ rehta hai. → answer (a) 1 hai.
cat s.txt: kernel inode 99 padhta hai, dekhta hai type l hai, text "a.txt" padhta hai, a.txt par lookup restart karta hai, inode 42 dhundhta hai, hi print karta hai. → answer (b) hi hai. Yeh step kyun? Symlink resolve karna = "string padho, phir path lookup dobara chalao."
rm a.txt: a.txt ka count $1 \to 0$ ho jaata hai, $f = 0$ hai, toh inode 42 free ho jaata hai. Ab s.txt abhi bhi "a.txt" store karta hai lekin woh naam gaya. Yeh step kyun? Symlink ne kabhi inode 42 ka count nahi chhoa, toh kuch bhi usse protect nahi kar raha tha.
cat s.txt: "a.txt" ka lookup fail → No such file or directory — ek dangling link. → answer (c) yeh error hai.

Verify: Count par sign check: symlink creation ne target ke count mein $0$ add kiya ( $1 + 0 = 1$ ), jabki ek hard link ne $1$ add kiya hota. Dangling behaviour exactly "signpost points at nothing" picture hai. ✅

Example 5 — Symlink sirf tab rename survive karta hai jab naam match kare (cell C5)

Forecast: rename delete nahi hai — kya signpost use dhundh lega?

s literal text "report.txt" store karta hai. Yeh step kyun? Symlinks naam se resolve hote hain, inode number se nahi.
mv directory entry ka naam report.txt se report_final.txt kar deta hai (wohi inode, bas ek naya naam). Yeh step kyun? Data aur inode untouched hain, lekin woh naam jo symlink dhundh raha hai ab exist nahi karta.
s ka resolution "report.txt" dhundha karta hai → nahi mila → s ab dangling hai, chahe data bilkul sahi se ek naye naam ke under alive ho. Yeh step kyun? Yahi sharp difference hai hard link ke muqable: ek hard link inode ko point karta hai aur renames se koi fark nahi padta.

Verify: Contrast case — agar s ek hard link hota (ln report.txt s), toh woh inode ko point karta; mv sirf doosra naam change karta, toh cat s abhi bhi data print karta. Do links, do behaviours, ek rename — exactly "points at path vs points at inode" distinction. ✅

Example 6 — Cross-filesystem: hard fail hota hai, soft jeet jaata hai (cell C6)

Worked example Statement

/mnt/usb/movie.mp4 ek USB filesystem par rehta hai. Apni home directory se (root filesystem par) tum dono try karte ho:

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

Kaun succeed karta hai, aur kyun?

Forecast: kaunsa Invalid cross-device link deta hai?

(a) hard link fail hota hai EXDEV: Invalid cross-device link ke saath. Yeh step kyun? Hard link ek inode number store karta hai, aur inode numbers sirf ek filesystem ke andar meaningful hote hain. USB par inode 500 aur root par inode 500 alag files hain, toh ~ mein ek dentry legally ek USB inode ko naam nahi de sakta.
(b) soft link succeed karta hai. Yeh step kyun? Ek symlink sirf ek path string "/mnt/usb/movie.mp4" store karta hai. Strings ko fark nahi padta ki woh kaun sa filesystem cross kar rahi hain; resolution bas us path se namei() dobara run karta hai.

Verify: Parent se constraint table — "cross-filesystem? Hard = No, Soft = Yes." Mechanism (inode number FS-local hai vs path universal hai) us table row ke peeche ka kyun hai. ✅

Example 7 — Ek directory se link karna (cell C7)

Forecast: OS inme se ek kyun refuse karega?

Figure dekho: left par, ek directory se uske ancestor ki taraf ek hard link ek loop band kar deta hai (dashed coral arrow) — black parent-arrow ko neeche follow karna aur coral arrow ko upar follow karna forever circle karega. Right par, butter-yellow symlink sirf /var/log mein ek text signpost hai; aisi signposts ka ek loop bhi kernel ke hop cap se cut off ho jaata hai.

(a) directory ko hard link → refuse hua (EPERM/Operation not permitted users ke liye). Yeh step kyun? Jaise left panel dikhata hai, har directory mein pehle se . aur .. hain. Agar users ek directory ko ancestor mein hard-link kar sakein, toh tum directories mein ek cycle bana lete, aur ek recursive walk (find, du, recursive rm) forever loop karta. Saath hi link-count-as-reachability idea toot jaata hai. Toh kernel ise ban karta hai.
(b) directory ko symlink → allowed. Yeh step kyun? Jaise right panel dikhata hai, symlink sirf text hai; kernel symlink-chain depth cap karta hai (e.g. ~40 hops ke baad ELOOP), toh yahan accidental loops bhi terminate hote hain.

Verify: Parent se DAG rule: hum directories mein cycles forbid karte hain taaki traversal terminate ho. Ek directory hard link ek cycle inject karega → banned. Ek symlink cycle depth cap se bounded hai → allowed. Consistent. ✅

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

Forecast: error predict karo aur yeh bounded kyun hai.

a "b" store karta hai, b "a" store karta hai — signposts ka ek two-node cycle. Yeh step kyun? Har symlink naam se doosre ko resolve karta hai, toh lookup ping-pong karta hai a → b → a → b ….
Agar unbounded hota, toh namei() kabhi terminate na hoti. Toh kernel hops count karta hai aur ek fixed limit (commonly 40) exceed hone par abort karta hai, ELOOP: Too many levels of symbolic links return karta hai. Yeh step kyun? Yahi limiting-value safeguard hai: hard links ke unlike (jo construction se kabhi cycle nahi bana sakte), symlinks bana sakte hain, toh depth cap safety net hai.

Verify: Resolver ko ek counter ki tarah model karo jo 0 se start hota hai, har hop par increment hota hai, $> 40$ par fail hota hai. Loop $a \to b$ ke liye, counter $1, 2, 3, \dots$ chalta hai aur provably finite steps mein 40 cross karta hai → ELOOP ke saath terminate hota hai. Toh yeh hang nahi kar sakta. ✅

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

Forecast: hard link ya symlink? Aur "instant" kyun lagta hai?

current ko ek symlink banao: ln -s /srv/www/v1 current. Yeh step kyun? Tumhe ek directory ko point karna hai aur sambhavtah mounts ke across — sirf symlink directory ko point kar sakta hai (Example 7). Woh ek path bhi store karta hai, toh re-pointing ek single text change hai.
Switch karne ke liye, symlink atomically replace karo: ln -sfn /srv/www/v2 current (-s ise symlink banata hai, -f existing current overwrite karta hai, -n ise old directory mein jaane se rokta hai). Equivalently, mv -T newlink current. Yeh step kyun? Symlink replace karna ek rename operation hai → server ya toh old target ya new target dekhta hai, kabhi half state nahi. Reversible: usi tarah se v1 par wapas point karo.
Count bookkeeping: directories v1 aur v2 apne khud ke link counts unchanged rakhte hain (symlink $0$ add karta hai). Sirf ek inode — current symlink — ka stored text swap hota hai. Yeh step kyun? "Soft doesn't count," toh yeh poora scheme har real directory ke $n$ ko untouched chhod deta hai.

Verify: Impact tally: directory v1 count change $= 0$ , v2 count change $= 0$ , involved symlink inodes ki sankhya $= 1$ . Switch ke across total link-count deltas $= 0$ . "Symlink creation/repoint kabhi target count nahi badhata" se match karta hai. ✅

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

Worked example Statement

Yeh listing di gayi hai, answer karo: (a) disk par kitne distinct regular-file data blobs hain? (b) kaun si entries data share karti hain? (c) kaun sa symlink hai, aur kya woh apne target ko deletion se protect karta hai?

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

Columns hain: inode number, permissions (pehla char = type), link count $n$ , owner, group, size, naam.

Forecast: inodes count karo, names nahi.

Pehla column (inode number) aur permissions column ka pehla character (type) padho: - = regular file, l = symlink. Yeh step kyun? Distinct data = distinct inode numbers, distinct names nahi; aur type char batata hai ki inode real data hold karta hai ya sirf ek path string.
Present inode numbers: 42, 99, 71. Inode 99 ek symlink hai (type l) jiska "data" sirf text a.txt hai (size 5 = "a.txt" ki length). Toh distinct regular-file data blobs inode 42 aur inode 71 hain → 2. → (a) answer 2 (plus 1 symlink inode, jo koi khud ka file data store nahi karta). Yeh step kyun? Hume symlink inode ko data blob ki tarah count nahi karna chahiye — woh ek signpost hai.
a.txt aur b.txt dono inode 42 dikhate hain link count 2 ke saath → woh ek data blob share karne wale do hard links hain. → (b) a.txt ⇄ b.txt data share karte hain. Yeh step kyun? Wohi inode number + count $2$ = do naam, ek inode.
s.txt (inode 99, type l) symlink hai; woh text "a.txt" store karta hai. Usne inode 42 ke count mein contribute nahi kiya (jo $2$ hai = do hard links). Ab twist: naam a.txt delete karne par inode 42 ka data b.txt ke zariye alive rehta hai (count $2 \to 1$ girta hai), lekin s.txt naam "a.txt" se resolve karta hai, jo ab gaya → s.txt dangling ho jaata hai. Toh symlink apne target ko protect nahi karta aur khud us naam ke delete/renames ke liye fragile hai. → (c) s.txt symlink hai; woh apne target ko protect nahi karta. Yeh step kyun? Symlinks naam se resolve hote hain (Example 5); "Soft doesn't count."

Verify: Cross-checks: listing mein inode-42 dentries ki sankhya $= 2$ → printed count 2 se match karta hai. Woh inodes jinka printed count 1 hai: s.txt(99) aur c.txt(71) → har naam exactly ek baar aata hai → match karta hai. Distinct regular-file data inodes $= {42, 71}$ , size $= 2$ . Sab 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