Visual walkthrough — ext4 structure — superblock, block groups, inodes

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

Hum sab kuch zero se banate hain. Agar aapne kabhi bit, byte, ya floor bracket nahi dekha, Step 1 se shuru karo aur skip mat karo.

---

Step 1 — Ek disk blocks ka flat array hai

KYA. Poori disk ko ek lambi row of identical boxes ki tarah socho. Har box ek block hai — storage ka ek fixed chunk, commonly $4096$ bytes (yaani $4$ KiB). Hum inhe $0,1,2,\dots ,N-1$ number karte hain.

KYO. Hardware humein koi meaning nahi deta — na "files", na "free space", bas numbered boxes. ext4 jo bhi clever kaam karta hai wo in boxes ke baare mein notes likhne ka tarika hai — kuch boxes ke andar hi. Toh pehli picture bas ye naked row hai.

PICTURE. Neeche di gayi row dekho. Box ke neeche label uska block number hai. Abhi kuch nahi keh raha ki kaunse boxes use ho rahe hain — yahi wo problem hai jo hume solve karni hai.

---

Step 2 — Sawaal: "kaunse boxes free hain?"

KYA. ext4 koi file store karne se pehle, use jaanna hai ki kaunse blocks already liye hue hain. Hume har block ke liye ek compact yes/no answer chahiye: used ($1$) ya free ($0$).

KYO bitmap, list nahi? Hum free block numbers ki ek list rakh sakte the, lekin numbers ki list bulky aur search karne mein slow hoti hai. Iske badle hum ek bitmap use karte hain: ek bit per block. Bit $i$ ek chhota sawaal answer karta hai — "kya block $i$ use ho raha hai?" Ye sabse sasta possible per-block record hai: exactly ek switch har ek ke liye. (General technique ke liye Bitmaps for allocation dekho.)

PICTURE. Neeche, Step 1 ke har block ke upar ek bit baitha hua hai. Ek magenta bit ($1$) = used, ek pale bit ($0$) = free. Bits ki ye strip hi bitmap hai.

---

Step 3 — Bitmap ko kahan store karein? Ek block ke andar.

KYA. Bitmap bhi data hai, toh use blocks mein rehna hoga. ext4 ek clean choice karta hai: block bitmap exactly EK block hai.

KYO exactly ek? Do reasons, dono simplicity aur speed ke baare mein:

1. Ek block ek read hai — OS ek hi disk access mein ek region ka poora "free map" grab kar leta hai.
2. Fixed-size bitmap ka matlab hai geometry predictable hai: har region identical dikhta hai, toh mkfs cheezein search karne ki bajay arithmetic se place kar sakta hai.

PICTURE. Hum ek block (orange) lete hain, use blow up karte hain, aur dikhate hain ki ye $8B$ bits ka ek grid hai — kyunki ye $B$ bytes ka hai aur har byte $8$ bits ka hai.

---

Step 4 — Killer constraint → blocks per group

KYA. Ab Step 2 aur Step 3 combine karo. Bitmap $k$ blocks track karta hai ($k$ bits chahiye). Bitmap hai ek block ($8B$ bits hold karta hai). Ek bit kisi aisi block ko describe nahi kar sakta jiske liye jagah nahi, toh:

$k\le 8B.$

Hum sabse bada region lete hain jo ek bitmap fully cover kar sakta hai, toh hum set karte hain $k=8B$. Wo region ek block group hai.

KYO maximum set karo? Bade groups = kam groups = kam repeated metadata aur file ki apni map ke saath better locality. Lekin hum $8B$ exceed nahi kar sakte, kyunki bit number $8B+1$ block mein simply exist nahi karta. Toh maximum woh sweet spot hai jo constraint hume free mein deta hai.

PICTURE. Left mein, $8B$ bits wala ek bitmap block. Usme se arrows fan out hote hain, har bit exactly ek data block ko point karta hai right mein $8B$ blocks ke ek region mein. Har arrow land karta hai; koi leftover nahi. Wo region ek block group hai.

---

Step 5 — Real number plug in karo

KYA. Common $B=4096$ bytes substitute karo.

KYO. Formula abstract hai; ek smart 12-saal ke bacche ko apni khud ki disk par actual megabytes dikhne chahiye.

$\text{blocks per group}=8\times 4096=32768.$

Ab utne blocks ko bytes mein convert karo:

$32768\text{blocks}\times 4096\frac{\text{bytes}}{\text{block}}=134,217,728\text{bytes}=128\text{MiB}.$

PICTURE. Ek single block group scale ke saath ek labelled bar ki tarah draw kiya gaya: front mein ek patla orange bitmap slice, phir ek patla inode-bitmap slice, phir inode table, phir $32768$ data blocks ka wide band — poore bar par "128 MiB" tag laga hai.

---

Step 6 — Disk ko groups se tile karna (aur leftover case)

KYA. Poori disk bas yahi $128$-MiB groups end to end laaye hue hai. Ek $10$ GiB disk ke liye:

$\text{number of groups}=\frac{10\times 1024\text{MiB}}{128\text{MiB}}=\frac{10240}{128}=80.$

KYO division. Total capacity ÷ group size = kitne groups fit hote hain. Har numerator/denominator MiB unit carry karta hai, jo cancel ho jaati hai, ek pure count rehta hai.

EDGE CASE — disk poora multiple nahi hai. Real disks rarely evenly divide hoti hain. Agar last group partial hogi, toh ext4 use ek short final group ki tarah rakhta hai: uski bitmap mein phir bhi $8B$ bits hote hain lekin extra bits (un blocks ke liye jo exist nahi karte) permanently used ($1$) mark ho jaate hain toh allocator unhe kabhi nahi deta.

PICTURE. Groups G0…G3 equal orange bars ki tarah dikhaye gaye hain, phir ek chhota final bar jiska non-existent tail hatched hai aur "bits forced to 1 — never allocated" mark kiya gaya hai.

---

Step 7 — Inodes ke liye same idea → group-of-an-inode formula

KYA. Inodes pre-numbered records hain ($1,2,3,\dots$). Ye bhi groups mein evenly split hote hain: har group mein $I$ inodes ka ek fixed count. Ye jaanne ke liye ki inode $N$ kis group mein rehta hai:

$\text{group}=\lfloor \frac{N-1}{I}\rfloor .$

KYO 1 subtract karo? Inode numbers 1-based hain (wo $1$ se start hote hain), lekin ek group ki table ke andar positions 0-based hain (wo $0$ se start hote hain). $-1$ counting-from-one se counting-from-zero mein shift karta hai. Floor bracket $\lfloor \cdot \rfloor$ ka matlab hai "fractional part phenko" — ye answer karta hai "inode $N$ tak pahunchne se pehle kitne poore groups fit hote hain?"

KYO floor aur round nahi? Rounding ek boundary inode ko agale group mein dhakkel sakta hai. Floor kabhi overshoot nahi karta: ye aapko us group mein land karata hai jo actually $N$ contain karta hai.

PICTURE. Inodes ki ek number line $I$ ke groups mein cut ki gayi hai. Inode $N$ ek segment ke andar baitha hai; ek labelled bracket $(N-1)$ start se count kiya hua dikhata hai, aur floor arrow group index par snap down karta hai.

---

Ek-picture summary

Upar sab kuch ek hi chain hai: ek byte 8 bits hai → ek block $8B$ bits hold karta hai → ek bitmap block sirf $8B$ blocks track kar sakta hai → toh ek block group hai $8B$ blocks → unhe disk par tile karo → inodes ko same tarah number karo aur kisi bhi ek ko floor-divide se locate karo. Neeche ki figure us poore logical waterfall ko ek single flow mein compress karti hai.

Recall Feynman retelling — apne plain words mein bol ke dikhao

Ek disk bas ek bahut badi shelf hai identical boxes ki, har box ek $4096$ bytes ka block. Inhe use karne ke liye, ext4 ko ek checklist chahiye ki kaunse boxes full hain. Wo checklist har box ke liye ek bit ki tarah likhti hai — full ya empty — aur poori checklist ek single box mein thuns deti hai. Lekin ek box sirf $8\times 4096=32768$ bits hold karta hai, toh ek checklist sirf $32768$ boxes track kar sakti hai. Isliye exactly ek block group $32768$ blocks = $128$ MiB hai: checklist itne se zyada nahi dekh sakti. Poori disk ko inhi $128$-MiB chunks mein kaato; ek leftover partial chunk bas apne imaginary boxes ko "full" mark kar deta hai taki koi unhe use na kare. Inodes (chhote record cards, ek per file) $1$ se number kiye gaye hain aur same even tarike se split hote hain, toh karta number $N$ kis chunk mein rehta hai ye jaanne ke liye $1$ subtract karo (kyunki cards $1$ se count karte hain lekin slots $0$ se) aur cards-per-chunk se divide karo, fraction phenko. Bas yahi poori geometry hai — ek bitmap box hi har cheez ka size decide karta hai.

Recall Quick self-test

Blocks per group formula, words mein? ::: Ek bitmap block $8B$ bits hold karta hai, har bit ek block track karta hai, toh ek group $8B$ blocks ka hai. 4 KiB blocks ke liye 128 MiB kyun? ::: $8\times 4096=32768$ blocks, times $4096$ bytes $=128$ MiB. Inode-group formula mein $-1$ kyun? ::: Inodes $1$ se count karte hain, table slots $0$ se; $-1$ unke beech convert karta hai. Partial final group ka kya hota hai? ::: Non-existent blocks ke uske bitmap bits $1$ (used) force ho jaate hain toh allocator unhe skip kar deta hai.

Ye bhi dekho: Operating Systems · ext2 vs ext3 vs ext4 · Hard links vs Symbolic links · Virtual File System · Journaling · Disk Scheduling · Memory Management.