ext4 structure — superblock, block groups, inodes: Exercises

4.2.35 · D4 · Coding › Operating Systems › ext4 structure — superblock, block groups, inodes

Yeh page ek self-test ladder hai. Solution ko cover karo, problem try karo, phir reveal karo. Har symbol jo yahan use hua hai woh parent topic mein Operating Systems ke under build kiya gaya tha. Agar kisi formula ke kyun pe atko, pehle woh note dobara padho — yahan hum sirf apply karte hain.

Do constants baar baar aate hain, toh inhe ek baar pin kar lo:

Figure — ext4 structure — superblock, block groups, inodes

Level 1 — Recognition

(Kya tum piece ko naam de sakte ho aur sahi fact pull kar sakte ho?)

L1.1

Q: Primary superblock kis byte offset pe rehta hai, aur offset 0 pe kyun nahi?

Recall Solution

Answer: byte offset 1024. Device ke pehle 1024 bytes boot sector ke liye reserved hain (legacy space jahan boot code reh sakta tha). Filesystem wahan kuch likhne ki permission nahi rakhta, isliye uska "ID card" — superblock — iske turant baad shuru hota hai, byte offset 1024 pe. Offset 0 off-limits hai, yeh filesystem territory nahi hai.

L1.2

Q: $B = 4096$ wale ek block group mein, order mein, chaar/paanch regions hote hain. Unhe group ke start se list karo.

Recall Solution

Order mein:

(optional) Superblock backup + Group Descriptor Table backup — sirf kuch groups mein.
Block bitmap (1 block) — is group ke blocks ka used/free map.
Inode bitmap (1 block) — is group ke inodes ka used/free map.
Inode table — inode records ki array.
Data blocks — actual file contents.

Mnemonic order: bits unse pehle aate hain jinhe woh count karte hain — tum free space map karte ho (bitmaps) records (inode table) aur payload (data) rakhne se pehle.

L1.3

Q: Root directory / ka inode number kya hai, aur reserved inodes ki range kya hai?

Recall Solution

Root inode 2 hai. Inodes 1–10 reserved hain (inode 1 = bad-blocks list, inode 2 = root, inode 11 = lost+found by convention). Root = 2 hardcode karna path resolution ko ek fixed jagah deta hai shuru karne ke liye.

Level 2 — Application

(Numbers ko geometry formulas mein plug karo.)

L2.1

Q: $B = 4096$ bytes ke saath, blocks per group kitne hain, aur MiB per group kitne hain?

Recall Solution

Blocks per group = ek bitmap block mein bits = $8 B$ . $8 \times 4096 = 32768 blocks per group$ Har block 4096 bytes ka hai, toh: $32768 \times 4096 = 134, 217, 728 bytes = 128 MiB per group$ ( $134, 217, 728/1024/1024 = 128$ .)

L2.2

Q: Ek disk $B = 1024$ bytes (1 KiB) ke saath format ki gayi hai. Blocks per group kitne hain, aur group mein kitne KiB hain?

Recall Solution

Blocks per group = $8 B = 8 \times 1024 = 8192$ blocks. Size = $8192 \times 1024 = 8, 388, 608$ bytes $= 8192$ KiB $= 8$ MiB per group. Dhyan do: chhota block → chhota group. Bitmap hamesha exactly ek block fit karta hai, toh $B$ ko chhota karne se dono bit-count aur block-size shrink hote hain, aur group size $8 B^{2}$ bytes ke roop mein scale karta hai.

L2.3

Q: $B = 4096$ ke liye, ek 20 GiB disk. Kitne block groups hain (metadata overhead ignore karte hue)?

Recall Solution

Group size = 128 MiB. Total = $20 \times 1024 = 20480$ MiB. $\frac{20480 MiB}{128 MiB} = 160 block groups$

Level 3 — Analysis

(Ab 1-based / 0-based reasoning kaata hai.)

L3.1

Q: Inodes-per-group = 8192. Inode number 50000 kis block group mein hai, aur us group ki inode table ke andar uska index kya hai?

Recall Solution

Inode numbers 1-based hain, array indices 0-based hain, isliye pehle 1 ghataao. $group = ⌊ \frac{50000 - 1}{8192} ⌋ = ⌊ \frac{49999}{8192} ⌋ = ⌊ 6.103 \dots ⌋ = 6$ Us group ke andar index: $(50000 - 1) mod 8192 = 49999 - 6 \times 8192 = 49999 - 49152 = 847$ Group 6, index 847.

L3.2

Q: Same $I = 8192$ inodes/group. Danger dikhao: inode 8193 ke liye group sahi tarike se compute karo, phir dikhao ki galat (no −1) formula kya deta hai.

Recall Solution

Sahi: $⌊(8193 - 1) /8192 ⌋ = ⌊ 8192/8192 ⌋ = ⌊ 1.0 ⌋ = 1$ . Inode 8193 group 1 ka pehla inode hai — index $(8193 - 1) mod 8192 = 0$ . ✓ Galat (no −1): $⌊ 8193/8192 ⌋ = ⌊ 1.000 \dots ⌋ = 1$ — yahan coincidentally sahi hai. Ab inode 8192 try karo (group 0 ka aakhri): sahi $⌊ 8191/8192 ⌋ = 0$ ✓; galat $⌊ 8192/8192 ⌋ = 1$ ✗ — exactly boundary pe ek group off. Bug wahaan chhupa rehta hai.

L3.3

Q: $B = 4096$ , inodes/group = 8192, inode size = 256 bytes. Ek group ki inode table kitne blocks occupy karta hai?

Recall Solution

Per group inode table ke bytes: $8192 \times 256 = 2, 097, 152 bytes$ 4096-byte blocks mein: $\frac{2 , 097 , 152}{4096} = 512 blocks per group$ Toh ek group ke 32768 blocks mein se 512 blocks inode records pe pehle se kharch ho jaate hain — koi file data aane se pehle hi.

Level 4 — Synthesis

(Kai rules ko milaakar ek answer banao.)

L4.1

Q: $B = 4096$ . Ek file 100 KiB ki hai. (a) Kitne 4-KiB data blocks? (b) Agar perfectly contiguously laid out ho, toh minimum kitne extents describe karte hain? (c) Yeh old indirect pointers se behtar kyun hai?

Recall Solution

(a) $100 KiB = 102400$ bytes. $⌈ 102400/4096 ⌉ = ⌈ 25.0 ⌉ = 25$ blocks (exactly divide hota hai: $25 \times 4096 = 102400$ ). (b) Ek extent = "logical blocks $0..24$ → physical blocks $p .. p + 24$ ", toh 1 extent agar fully contiguous hai. (c) Old ext2/3 ko ~25 individual block pointers chahiye hote (aur ek indirect block jab 12 direct slots exceed ho jaate). Extents sab kuch ek record se replace karte hain → chhota inode footprint, file map karne ke liye kam reads. Yahi ext4 improvement hai.

L4.2

Q: /home/ada/x.txt resolve karo — har inode read list karo, order mein, aur batao har read kya produce karta hai. Batao chain shuru kyun ho sakti hai.

Recall Solution

Yeh shuru ho sakti hai kyunki root ek fixed inode hai: inode 2.

Inode 2 (/) padho → uska data block ek directory listing hai → entry home dhundho → home ka inode # milta hai.
home ka inode padho → uska data → ada dhundho → ada ka inode # milta hai.
ada ka inode padho → uska data → x.txt dhundho → file ka inode # milta hai.
File ka inode padho → uske extents → physical data blocks → bytes.

Pattern: inode → data (directory) → name lookup → next inode, har path component ke liye repeat, phir ek final inode → extents → data. Path mein har / = ek aisa hop. Yahi mechanism hai jo Virtual File System filesystems ke across uniformly expose karta hai.

L4.3

Q: Ek user nayi files banana band ho jaata hai jabki df 40% free space dikhata hai. ext4 terms mein diagnose karo aur confirm karne ke liye exact command batao.

Recall Solution

Inodes ek alag, fixed pool hai jo mkfs time pe allocate hoti hai (L3.3 dekho — table pre-sized hoti hai). Laakhon tiny/empty files inodes exhaust kar sakti hain jabki data blocks free rehte hain. df block usage dikhata hai; inode pool uske liye invisible hai. Confirm karo: df -i Agar IUse% column 100% padhe, toh pool exhausted hai — koi bytes help nahi karenge; aapko files delete karni hongi ya zyada inodes ke saath reformat karna hoga.

Level 5 — Mastery

(Design-level: constraints se geometry derive karo, edge cases ke baare mein reason karo.)

L5.1

Q: Prove karo ki block size $B$ bytes ke liye, ek block group ka size bytes mein $8 B^{2}$ hota hai. Phir $B = 4096$ ke liye evaluate karo aur confirm karo ki yeh 128 MiB ke barabar hai.

Recall Solution

Chain of constraints:

Ek block = $B$ bytes = $8 B$ bits (8 bits per byte).
Block bitmap ek block ka hai, toh usmein $8 B$ bits hain, aur ek bit ↔ ek block. Isliye blocks per group $= 8 B$ .
Har block $B$ bytes ka hai, toh group size $= (8 B) \times B = 8 B^{2}$ bytes. ∎

$B = 4096$ ke liye: $8 \times 409 6^{2} = 8 \times 16, 777, 216 = 134, 217, 728$ bytes. $134, 217, 728/102 4^{2} = 128$ MiB. ✓ Key insight: $B$ ka sirf ek choice poori geometry fix kar deta hai — bitmap-fits-one-block hi master constraint hai.

L5.2

Q: $B = 4096$ , inodes/group = 8192. Ek 10 GiB disk. Poore filesystem mein total inode count estimate karo (metadata reserve ignore karo). Phir batao df -i total kya report karega.

Recall Solution

Groups: $10 \times 1024 MiB /128 MiB = 80$ groups. Total inodes $= 80 \times 8192 = 655, 360$ inodes. df -i total ≈ 655,360 (minus reserved inodes 1–10 jo used dikhe). Toh is disk pe chahe files kitni bhi chhoti hon, maximum ~655k files hi ho sakti hain — ek hard ceiling jo format time pe set hoti hai.

L5.3

Q: Degenerate case: jab ek group superblock+GDT backup carry karta hai uski usable data region mein kya hota hai, versus jab nahi karta? Reason karo ki ext4 har group mein backup kyun nahi rakhta.

Recall Solution

Backup carry karne wala group extra blocks kharch karta hai: 1 superblock copy + Group Descriptor Table copy. Woh blocks file data ke liye unavailable hain, toh backup-bearing group ki data region plain group se thodi chhoti hoti hai. ext4 (sparse_super feature ke saath) backups sirf $0, 1$ aur $3, 5, 7$ ki powers wale groups mein rakhta hai (jaise group 3, 9, 25, 49...). Har group mein kyun nahi? Har group mein backup redundancy pe bahut space waste karta hai jo recovery ke liye sirf ek baar chahiye. Kuch ache tarah se spread copies fsck ke liye rebuild karne ke liye kaafi hain — yeh classic redundancy-vs-overhead trade hai, wahi spirit jaise Journaling mein hai (sirf utna metadata protect karo jitna zaroori hai, sab kuch twice nahi).

Recall Jaane se pehle ek-line self-quiz

Blocks per group formula? ::: $8 B$ (ek bitmap block mein bits, $B$ = block size in bytes). Group of inode $N$ with $I$ per group? ::: $⌊(N - 1) / I ⌋$ — 1-based numbering ke liye 1 ghataao. Which gauge shows inode exhaustion? ::: df -i, df nahi.