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

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

Do objects ka ek quick reminder jis par sab kuch depend karta hai, taaki koi bhi symbol use hone se pehle define ho jaye:

Level 1 — Recognition

Exercise 1.1

Is ls -li output ko dekhkar, har entry ka inode number batao aur kaho ki kaun se do entries same file hain:

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

Recall Solution

Columns ka matlab: pehla number inode hai; permissions ke baad wala number (2, 2, 1) link count hai.

a.txt → inode 42, b.txt → inode 42, s.txt → inode 99.
a.txt aur b.txt inode 42 share karte hain, isliye yeh same file hain (ek hard-link pair). Unka link count 2 hai, jo confirm karta hai ki exactly do names inode 42 par point karti hain.
s.txt ka apna khud ka inode 99 hai aur type char l hai — yah ek symlink hai, ek alag file jiska data text "a.txt" hai.

Exercise 1.2

Upar ki har row ke liye ls -l type character aur uska matlab batao.

Recall Solution

a.txt, b.txt: type char - → ek regular file.
s.txt: type char ==l== → ek symbolic link. Type char permission string ka bilkul pehla character hota hai.

Level 2 — Application

Exercise 2.1

echo hi > a.txt se shuru karo (fresh inode, count 1). Yeh commands order mein chalao:

ln a.txt b.txt
ln a.txt c.txt
rm b.txt

Har command ke baad inode ka link count kya hai?

Recall Solution

ln a.txt b.txt: ek name add karo → $n = 1 + 1 = 2$ .
ln a.txt c.txt: ek name add karo → $n = 2 + 1 = 3$ .
rm b.txt: rm ne unlink call kiya, ek name hatao → $n = 3 - 1 = 2$ . Final link count = 2 (names a.txt aur c.txt bacha hain). Data bilkul intact hai.

Exercise 2.2

Same fresh a.txt (count 1). Chalao:

ln -s a.txt s.txt

Ab a.txt ka link count kya hai, aur kitne inodes exist karte hain?

Recall Solution

Ek symlink target ka count nahi badhata: a.txt $n = 1$ par hi rehta hai.
Ab do inodes exist karte hain: a.txt ke liye inode, aur s.txt ke liye ek alag inode (iska data = string "a.txt"). Hard link se compare karo, jisse count $2$ ho jaata aur koi naya inode nahi banta.

Ek file ka inode 42 hai jiska link count $n = 2$ hai: names a.txt aur b.txt. Ek process a.txt open karti hai (open file descriptor hold karta hai), phir koi rm a.txt aur rm b.txt chalaata hai. $n$ , "open" count trace karo, aur exactly batao kab data blocks free honge.

Recall Solution

Parent note se full free condition: free tab hogi jab $n = 0$ AND open $= 0$ .

Step	$n$	open fds	data alive?
start	2	1	yes
`rm a.txt`	1	1	yes (abhi bhi ek name hai)
`rm b.txt`	0	1	yes — $n = 0$ hai lekin ek process abhi bhi ise open hold kar rahi hai
process closes fd	0	0	abhi freed
Toh blocks tabhi free hote hain jab process apna descriptor close kare, `rm b.txt` par nahi. Isliye ek running program ek "deleted" log file ko padhta reh sakta hai.

Exercise 3.2

Yeh karne ke baad namespace graph draw/describe karo:

mkdir d ; echo hi > d/x ; ln d/x d/y

Kya yah tree hai ya DAG? Us node ko identify karo jiska in-degree $> 1$ ho.

Recall Solution

Neeche diya figure dekho. Directory d mein do entries x aur y hain, dono same inode (use 42 kaho) par point karti hain. Us inode ka isliye in-degree 2 hai (do incoming edges). Ek tree mein har node ka exactly ek parent/incoming edge hona zaroori hai, isliye yah tree nahi hai — yah ek DAG hai. Koi cycle nahi hai (edges sirf parent→child jaati hain), isliye yah acyclic hai.

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

Level 4 — Synthesis

Exercise 4.1

Aapko ~/film ko /mnt/usb/movie.mp4 par point karna hai, jo ek alag filesystem par hai. Ek colleague ln /mnt/usb/movie.mp4 ~/film try karta hai aur Invalid cross-device link milta hai. Error explain karo aur correct one-line command do.

Recall Solution

YEH KYUN FAIL HOTA HAI: ek hard link ek (name, inode_number) entry hai, aur inode numbers sirf ek filesystem ke andar meaningful hote hain. ~ aur /mnt/usb alag filesystems hain, isliye USB par inode 42 ka home filesystem mein koi matlab nahi — isliye Invalid cross-device link (EXDEV). Fix: ek symlink use karo, jo path string store karta hai, inode number nahi, aur isliye filesystems ke paar freely ja sakta hai:

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

Exercise 4.2

Ek aisa scenario design karo jahan links create karna accidentally infinite traversal cause kare, aur explain karo ki kernel isse kaise rokta hai. Kaun sa link type yah kar sakta hai?

Recall Solution

Symlinks yah kar sakte hain:

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

Har resolution doosre path par jump karta hai, aur do paths ek doosre ko point karte hain, isliye name resolution apne aap kabhi terminate nahi hoti. Kernel isse kaise rokta hai: yah symlink chain depth cap karta hai (commonly ~40 hops) aur ==ELOOP== return karta hai ("Too many levels of symbolic links"). Hard links yah kyun nahi kar sakte: directory hard links users ke liye forbidden hain, isliye hard links sirf file inodes ko names add kar sakte hain — directories ke beech koi cycle possible nahi, jo directory graph ko DAG banaye rakhta hai.

Level 5 — Mastery

Exercise 5.1

Ek directory d fresh banayi gayi hai aur empty hai. Uska link count kya hai, aur yah 1 kyun nahi hai? Phir aap mkdir d/sub chalate ho. Ab d ka link count kya hai? Ek directory ke link count ka formula $k$ subdirectories ki sankhya ke terms mein derive karo.

Recall Solution

Ek directory ke incoming references hain: (1) uska naam uske parent mein, plus (2) uski apni . entry (jo khud par point karti hai), plus (3) har ek child subdirectory se ek .. entry (har child ka .. is directory par wapas point karta hai).

Empty d: naam (1) + . (1) + zero children = $n = 2$ .
mkdir d/sub ke baad: naya child sub ek .. contribute karta hai jo d par point karta hai, isliye $n = 2 + 1 = 3$ .
General formula, jahan $k$ = immediate subdirectories ki sankhya: $n_{dir} = 2 + k$ "2" kyun: constant 2 directory ka apna naam plus uski . self-link hai — empty hone par bhi present. Har subdirectory phir apne .. se exactly ek add karta hai.

Exercise 5.2

$n_{dir} = 2 + k$ use karte hue, ek directory ls -ld mein link count 5 dikhati hai. Uske kitne immediate subdirectories hain? Kya yah count uske andar ke regular (non-directory) files include karta hai?

Recall Solution

Solve karo $5 = 2 + k \Rightarrow k = 3$ immediate subdirectories. Regular files is count ko affect nahi karte: ek regular file ka naam uske apne inode ke link count mein hota hai, directory ka nahi. Sirf subdirectories ek .. back-reference add karte hain, isliye directory ka link count uske child directories ki sankhya reveal karta hai — ek neat forensic trick jo find jaise tools use karte hain.

Recall One-line self-test reveals

Hard link target ke count ko badalta hai ::: +1 (creation) ya −1 (unlink) se Symlink target ke count ko badalta hai ::: 0 se (yah text store karta hai, inode reference nahi) Data exactly tab free hota hai jab ::: link count $n = 0$ AND koi process ise open nahi rakh raha Empty directory link count ::: 2 (uska naam + uska apna .) Directory link count formula ::: $n = 2 + k$ , jahan $k$ = subdirectories ki sankhya Cross-filesystem link hona chahiye ek ::: symlink (hard links filesystems cross nahi kar sakte) Symlink cycles rokne wala kernel error ::: ELOOP

Connections

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

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

Level 1 — Recognition

Exercise 1.1

Exercise 1.2

Level 2 — Application

Exercise 2.1

Exercise 2.2

Level 3 — Analysis

Exercise 3.1

Exercise 3.2

Level 4 — Synthesis

Exercise 4.1

Exercise 4.2

Level 5 — Mastery

Exercise 5.1

Exercise 5.2

Connections