Directory structure — tree, DAG (hard links, symbolic links): Visual walkthrough

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

Hum har word ko earn karenge: box, inode number, name, link count, tree, DAG, symlink. Kuch bhi assume nahi kiya gaya.

Step 1 — Bytes ka ek box jisme number hai, lekin naam nahi

KYA HAI. Ek shelf par rakha physical box imagine karo. Box ke andar tumhare file ka actual content hai — bytes. Box ke baahr ek number paint kiya hua hai, maan lo 42. Yeh box-with-a-number wahi hai jise Unix inode kehta hai (dekho Inodes and File Metadata)।

YAHAN SE KYUN shuru karein. Kyunki poore chapter mein sabse important design choice yeh hai: box apna number jaanta hai, lekin box apna naam NAHI jaanta. Naam bilkul alag jagah rehta hai. Agar hum yeh separation clearly nahi dekhte, toh hard links aur symlinks magic lagte hain. Hain nahi.

PICTURE. Box bytes aur ek chota counter rakhta hai jo hum Step 3 mein define karenge. Uska number hai (42) lekin koi label nahi hai jisme "a.txt" likha ho — woh label side mein hai, attached nahi hai.

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

Step 2 — Ek naam ek room mein sticker hai, box ka hissa nahi

KYA HAI. Ek directory khud ek aisa box hai jiske contents ek list of stickers hain. Har sticker ek pair hota hai:

$human name ("a.txt", which box 42)$

$"a.txt"$ — woh naam jo human padhta hai. Yeh "jo tum type karte ho" wala kaam kar raha hai.
$42$ — inode number. Yeh "shelf par kaun sa box" wala kaam kar raha hai.

Aise pair ko directory entry ya dentry kehte hain.

KYUN. Ab hum filesystem ke ek kaam ka jawab de sakte hain — "diye gaye naam se data kahan hai?" — room ki sticker list mein naam dhundhkar, number padhkar, aur us box par chale jaake. Naam aur box sirf is sticker ke zariye connected hain.

PICTURE. Ek room (directory) mein ek sticker hai a.txt → 42, aur sticker se box 42 tak ek arrow. Sticker room ki wall par chipki hai, box par kabhi nahi.

Step 3 — Box par counter: link count

KYA HAI. Har box par ek chota integer paint hota hai: link count $n$ .

$n = # {stickers currently pointing at this box}$

$# {\dots}$ — "is set mein kitni cheezein hain," yaani unhe count karo.
Set mein har woh dentry (sticker) hai jiska number is inode ke number ke barabar hai.

Abhi, ek sticker a.txt → 42 ke saath, $n = 1$ hai.

COUNTER KYUN? Kyunki humein eventually jaanna hai box ko throw karna kab safe hai. Aisa box throw karna jiska koi naam abhi bhi point kar raha hai filesystem ko corrupt kar dega. Counter is sawaal ka jawab deta hai "kya koi abhi bhi yahan point kar raha hai?" poori disk scan kiye bina. Yeh bilkul reference counting hai.

PICTURE. Box 42 apne counter ke saath jo 1 padhta hai, ek sticker arrow us par land kar raha hai.

Step 4 — Ek naam, ek parent: yeh ek TREE hai

KYA HAI. Maano har box ka exactly ek sticker hai, aur har room exactly ek parent room ke andar hai. Rooms ko circles se draw karo aur "contains" ko neeche point karte arrows se. Result ki ek special shape hogi.

KYUN MATTERS. Ek aisi shape jisme har node ka exactly ek parent ho (root / ko chhodkar, jo top par hai) aur koi loops nahi hain, use tree kehte hain (dekho Graphs — Trees vs DAGs)। Tree mein har box exactly ek path se reachable hai — toh ek naam woh file hi hai, aur delete karna trivial hai: ek sticker hatao, box $n = 0$ ho jaata hai, use free karo.

PICTURE. Root / top par; neeche do rooms; unke neeche files. Kisi bhi node mein arrow-count exactly 1 hai — yeh tree ki signature hai.

Step 5 — Usi box ke liye doosra sticker: tree toot jaata hai

KYA HAI. Ek command run karo: ln a.txt b.txt. Yeh box ko copy nahi karta. Yeh ek doosra sticker b.txt → 42 add karta hai aur counter bump karta hai: $n : 1 \to 2$ .

$two stickers n = 2 = {a.txt \to 42, b.txt \to 42}$

Dono stickers equal hain — koi "original" nahi hai aur koi "copy" nahi hai. Dono first-class hard links hain.

YEH TURNING POINT KYUN HAI. Box 42 ko ab dekho: do arrows us mein point kar rahe hain. Ek tree mein, har node mein zyada se zyada ek arrow point karta hai. Do incoming arrows wala node tree mein nahi ho sakta. Shape abhi badal gayi.

PICTURE. Do stickers (possibly alag) rooms mein, dono arrows box 42 par land kar rahe hain, jiska counter ab 2 padhta hai.

Step 6 — Yeh DAG kyun hai, sirf "ek graph" nahi: koi loops allowed nahi

KYA HAI. Kai incoming arrows wale box ka matlab hai kai paths same data tak pahunch sakte hain — shape ab ek graph hai, tree nahi. Lekin yeh ek special graph hai: hum ek directory ko apne kisi ancestor ki taraf wापस point karne se rokते hain, isliye tum kabhi circle mein nahi chal sakte. Ek directed graph jisme arrows hain lekin koi cycles nahi hain, use Directed Acyclic Graph (DAG) kehte hain.

LOOPS FORBID KYUN? Do reasons, dono picture mein dikhte hain:

Traversal rukni chahiye. find aur du jaise tools arrows follow karte hain. Ek loop unhe hamesha ke liye ghoomta rakhta.
Counter jhooth bol deta. Agar ek directory apne ancestor ki taraf wapis point kar sakti, toh "mujh tak kitne stickers pahunchte hain" ka count kabhi 0 tak nahi girta, toh box kabhi free nahi ho sakta.

Isliye kernel user-created hard links to directories ban karta hai — sirf special automatic . aur .. entries allowed hain, aur kernel unhe carefully handle karta hai.

PICTURE. Left: ek valid DAG — ek file tak kai paths, saare arrows neeche flow kar rahe hain, koi loop nahi. Right (crossed out): ek child directory se uske ancestor tak ek forbidden back-arrow, cycle banaate hue.

Step 7 — Soft link: ek signpost, doosra naam nahi

KYA HAI. ln -s a.txt s.txt run karo. Yeh ek brand-new box (ek naya inode, maan lo 99) banata hai jiske contents text string "a.txt" hain. Yeh ek symbolic link (symlink) hai. Ise resolve karne ka matlab hai: string padho, phir us string se name lookup restart karo.

Importantly, ise create karne se box 42 ka counter touch nahi hota:

$n_{42} = 1 (unchanged), n_{99} = 1 (its own single name)$

DOOSRE TARAH KA LINK KYUN? Kyunki ek hard link ek inode number store karta hai, jo ek filesystem ke andar hi meaningful hai aur directory ki taraf point nahi kar sakta (loop danger). Ek symlink sirf text store karta hai, isliye woh freely filesystems ke paar aur directories ki taraf point kar sakta hai — bas koi guarantee nahi ki target abhi bhi exist karta hai.

PICTURE. Box 99 ek chota signpost hai jo text "a.txt" hold karta hai; ek dashed arrow usse nikalta hai aur sticker a.txt par land karta hai, seedha box 42 par nahi. Box 42 ka counter abhi bhi 1 padhta hai.

Step 8 — Degenerate cases: edges par kya hota hai

KYA AUR KYUN (har edge figure mein dikhaya gaya hai).

Ek hard link delete karo jab $n = 2$ ho. rm a.txt → unlink() → $n : 2 \to 1$ . Box survive karta hai, b.txt ke zariye accessible rehta hai. Box free nahi hota kyunki $n > 0$ hai.
Aakhri hard link delete karo ( $n : 1 \to 0$ ). Ab koi sticker point-in nahi karta; agar koi program ise open nahi rakh raha, bytes free ho jaate hain. Yeh ekmaatra tarika hai kisi box ke marne ka.
Open-file exception ( $n = 0$ lekin koi program abhi bhi use open rakhe hue hai). Bytes tab tak alive rehte hain jab tak aakhri program use close nahi karta — ek classic "unlinked-but-open" temp file.
Symlink ka target delete karo. Sticker a.txt gayab ho jaata hai, lekin symlink box 99 abhi bhi text "a.txt" rakhta hai. Resolution ab fail hoti hai → ek dangling (broken) link. Dhyan raho ki target ka count kabhi bump nahi hua tha, toh woh protect nahi tha.

PICTURE. Char mini-panels: (1) $n : 2 \to 1$ survive karta hai, (2) $n : 1 \to 0$ free ho jaata hai, (3) $n = 0$ lekin open → abhi bhi alive, (4) symlink kisi cheez ki taraf point kar raha hai jo hai hi nahi.

Ek-picture summary

Upar sab kuch ek diagram mein collapse ho jaata hai: ek tree jisme ek extra hard link hai (ise DAG banata hua) aur side mein ek symlink jo ek naam ki taraf point kar raha hai. Ise trace karo aur tum poore chapter ko re-derive kar sakte ho.

Recall Feynman retelling — plain words mein walkthrough

Ek shelf imagine karo jisme numbered boxes bhari hain. Ek box tumhara saamaan aur ek chota tally counter rakhta hai, lekin koi label nahi — labels rooms ki walls par chipke stickers hain. Apna saamaan dhundhne ke liye tum ek sticker padhte ho, box number lete ho, aur us box tak jaate ho. Step 1–2: box + sticker. Step 3: box count karta hai ki kitne stickers uski taraf point kar rahe hain. Step 4: agar har box ka exactly ek sticker hai aur rooms seedhe nest hote hain, toh poora map ek family tree hai — har cheez tak ek path. Step 5: jis instant tum ek doosra sticker lagaate ho (kisi bhi room mein) jo same box number kahe, box ke ab do stickers ho jaate hain, uska counter 2 padhta hai, aur do paths ek box tak pahunchte hain — tree bas toot gayi. Step 6: yeh ab ek web hai, lekin ek well-behaved wala: hum kabhi ek room ko apne khud ke grandparent ki taraf point karne nahi dete, isliye tum kabhi circles mein nahi chal sakte — yeh ek DAG hai. Step 7: ek soft link alag hai — yeh ek chota note-box hai jo sirf kehta hai "jaao aur a.txt wala sticker dhundho." Yeh kisi ka counter bump nahi karta. Step 8: do-counter box se ek sticker peelo aur saamaan survive karta hai; aakhri wala peelo aur saamaan phek diya jaata hai — unless koi dost box abhi bhi open rakhe hue hai. Note waale naam ko hata do, aur note kisi cheez ki taraf point karta hai jo hai hi nahi. Yahi poori kahaani hai.

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