ext4 structure — superblock, block groups, inodes: Worked examples

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

The scenario matrix

Ext4 geometry ke baare mein har question actually chand shapes mein se ek hota hai. Ye full list hai — baad ke har example mein us cell ka tag lagaa hai jo wo fill karta hai.

#	Case class	Kya tricky hai	Example
A	Inode → block group (normal)	1-based offset	Ex 1
B	Inode → block group (boundary)	inode exactly ek group edge pe	Ex 2
C	Degenerate input: inode 1	sabse chhotaa legal inode, off-by-one trap	Ex 3
D	Capacity from geometry	metadata overhead vs raw size	Ex 4
E	Zero/limiting: tiny disk	disk ek group se chhotaa	Ex 5
F	Inode table sizing	inodes ek alag fixed pool hain	Ex 6
G	Real-world word problem	"millions of tiny files" — space se pehle inodes khatam	Ex 7
H	Extents vs old pointers	fragmented file ke liye kitne extent records	Ex 8
I	Exam twist: different block size	geometry $B$ ke saath scale hoti hai; 4096 hardcode mat karo	Ex 9
J	Usable data blocks per group	SAARE metadata blocks subtract karna	Ex 10

Do symbols baar baar aate hain, toh inhe ek baar pin kar lete hain, plain words mein:

Definition Teen operators jo tumhe precisely padhne aane chahiye

$⌊ x ⌋$ = floor: fractional part phenk do, wo whole number rakho jo $x$ pe ya usse neeche ho. Jaise $⌊ 6.9 ⌋ = 6$ .
$⌈ x ⌉$ = ceiling: upar round karo, wo next whole number jo $x$ pe ya usse upar ho. Jaise $⌈ 6.1 ⌉ = 7$ aur $⌈ 0.5 ⌉ = 1$ . Hume ye tab chahiye jab koi cheez poori cover honi ho — aadha block ya aadha group nahi ho sakta, isliye hamesha upar round karte hain.
$a mod m$ = $a$ ko $m$ se divide karne ka remainder: $m$ ke jitne bhi poore copies fit hon unhe hatane ke baad jo bachta hai. Precisely $a mod m = a - m ⌊ a / m ⌋$ , aur result hamesha $0 \dots m - 1$ mein hota hai. Jaise $49999 mod 8192 = 847$ kyunki $49999 - 6 \times 8192 = 847$ .

Group number ke liye floor kyun lekin "X ko fill karne mein kitne blocks" ke liye ceiling kyun: floor jawab deta hai "main kis slot mein hoon?" (tum us group ke andar ho jise tum poora cross kar chuke ho), ceiling jawab deti hai "is cheez ko hold karne ke liye mujhe kitne whole blocks reserve karne honge?" (koi bhi leftover ek aur poora block maangti hai). Same picture, opposite rounding.

Recall Woh ek formula jo cells A, B, C solve karta hai

Ek inode jiska number $N$ ho (numbering 1 se shuru hoti hai) aur $I$ inodes per group ho:

Group number ::: $⌊ \frac{N - 1}{I} ⌋$
Us group ki inode table ke andar index ::: $(N - 1) mod I$
1 kyun subtract karte hain? ::: inode numbers 1-based hain, array slots 0-based hain; ye skip karne par tum har boundary pe ek group off ho jaate ho.

Mapping ki ek picture (Case A se pehle ye padho)

Neeche wala figure poora page ek image mein hai: left pe, inode-number line $I$ ke equal groups mein kati hui hai; right pe, ek single block group ka physical layout (superblock backup → bitmaps → inode table → data). Har worked example bas "main kaun sa arrow follow kar raha hoon?" hai.

Figure — ext4 structure — superblock, block groups, inodes

Words mein: inode numbers $1 \dots I$ group 0 mein rehte hain, $I + 1 \dots 2 I$ group 1 mein, aur aage bhi aise hi — vertical dashed lines woh group boundaries hain jahan Case B exactly land karta hai. Ek group ke andar (right panel), pehle kuch blocks metadata ke liye hain; end mein badi green stretch hai jahan file data actually jaata hai (woh green stretch hi Case J count karta hai).

Case A — Inode to block group, the ordinary case

Upar wale figure mein blue arrow follow karo: wo inode $50000$ ko left number-line se kisi group box mein le jaata hai.

Step 1 — 0-based pe shift karo. $N - 1 = 50000 - 1 = 49999$ Ye step kyun? Formula count karta hai ki $N$ se pehle kitne inodes aate hain. Inode 1 "zeroth" inode hai, isliye hum 1 subtract karte hain taaki 1-based label ko 0-based position mein badlen.

Step 2 — Group size se divide karo, whole part rakho. $group = ⌊ \frac{49999}{8192} ⌋ = ⌊ 6.103 \dots ⌋ = 6$ Ye step kyun? Har group mein exactly $I = 8192$ inodes hote hain. Integer division "hamare se pehle kitne full groups fit hote hain" ही group number hai. Floor fractional part phenk deta hai kyunki tum "group 6.1" mein nahi ho sakte.

Step 3 — Remainder slot deta hai. $(N - 1) mod I = 49999 mod 8192 = 49999 - 6 \times 8192 = 49999 - 49152 = 847$ Ye step kyun? Remainder hai "hum group 6 mein kitna andar hain" — inode table ki row (figure ka right panel).

Verify: inode ko (group, index) se reconstruct karo: $6 \times 8192 + 847 + 1 = 49152 + 847 + 1 = 50000$ . ✅ ( $+ 1$ 0-based shift ko undo karta hai).

Case B — Boundary: ek inode jo exactly group edge pe baith jaata hai

Figure mein, ye dono inodes pehli dashed boundary line ke dono taraf baithe hain.

Step 1 — Inode 8192 karo. $⌊ \frac{8192 - 1}{8192} ⌋ = ⌊ \frac{8191}{8192} ⌋ = ⌊ 0.9998 \dots ⌋ = 0$ Ye step kyun? $8191 < 8192$ , isliye whole part $0$ hai. Inode 8192, group 0 ka last inode hai (index $8191$ ).

Step 2 — Inode 8193 karo. $⌊ \frac{8193 - 1}{8192} ⌋ = ⌊ \frac{8192}{8192} ⌋ = 1$ Ye step kyun? Ab numerator exactly group size ke barabar hai, isliye whole part $1$ ho jaata hai. Inode 8193, group 1 ka first inode hai (index $0$ ).

Verify: group 0 mein inodes $1 \dots 8192$ hain (exactly $8192$ inodes), group 1 $8193$ se shuru hota hai. Count check out hota hai. ✅

Case C — Degenerate input: sabse chhotaa legal inode

Ye figure ke left pe bilkul pehla slot hai.

Step 1 — Formula ko literally apply karo. $group = ⌊ \frac{1 - 1}{8192} ⌋ = ⌊ \frac{0}{8192} ⌋ = 0, index = 0 mod 8192 = 0$ Ye step kyun? Formula $- 1$ karne ki yahi poori wajah hai: pehla inode group 0 ke slot 0 pe map hona chahiye. Agar hum $- 1$ bhool jaate toh bhi yahan group 0 milta (kyunki $⌊ 1/8192 ⌋ = 0$ ), isliye ye case bug ko chhupaata hai — yahi wajah hai ki tumhe boundaries test karni chahiye (Ex 2), sirf inode 1 nahi.

Verify: $0 \times 8192 + 0 + 1 = 1$ reconstruct karo. ✅ Sabse chhotaa inode pehle slot pe map hota hai, jaisa hona chahiye.

Case D — Pure geometry se capacity

Step 1 — Dono sizes ko same unit (MiB) mein daalo. $10 GiB = 10 \times 1024 MiB = 10240 MiB$ Ye step kyun? Tum size ko group-size se tab tak divide nahi kar sakte jab tak units match na hon. GiB aur MiB mix karna yahan #1 arithmetic error hai.

Step 2 — Group size se divide karo. $\frac{10240 MiB}{128 MiB/group} = 80 groups$ Ye step kyun? Groups ki number bas total-size ÷ size-per-group hai. Metadata (bitmaps, inode table, superblock backups) har group ke andar se carved out hota hai, isliye ye group count nahi badalta — ye group ke andar usable data blocks mein se khaata hai.

Verify: $80 \times 128 = 10240$ MiB $= 10$ GiB exactly. ✅ Clean kyunki $10240$ , $128$ ka multiple hai.

Case E — Limiting case: ek group se chhotaa disk

Step 1 — Raw ratio compute karo. $\frac{64 MiB}{128 MiB} = 0.5$ Ye step kyun? Disk aadha group hai. Lekin aadha block group nahi ho sakta — group layout ki unit hai.

Step 2 — Ceiling se upar round karo. $groups = ⌈ 0.5 ⌉ = 1 (lekin single group sirf half-full hai)$ Ye step kyun? Hum ceiling (upar define ki gayi) use karte hain kyunki group ka ek fraction bhi ek poore group mein rehne ki demand karta hai. ext4 ek group banata hai aur simply usme fewer blocks track karta hai: block bitmap phir bhi ek full block occupies karta hai, lekin uski bahut si bits "beyond end of device" ko used mark karti hain. Isliye ek chhotaa disk proportionally zyada metadata overhead leta hai — woh degenerate case jahan "ek bitmap block" data ke liye oversized hai.

Verify: actually present blocks $= 64 MiB /4096 = 64 \times 1024 \times 1024/4096 = 16384$ blocks. Ye ek full bitmap ki $32768$ bits se kam hai, isliye ek bitmap unhe sab cover kar leta hai room to spare ke saath. ✅ Exactly ek group confirm hota hai.

Case F — Inode table sizing (inodes ek alag pool hain)

Step 1 — Inode table ke total bytes. $8192 \times 256 = 2, 097, 152 bytes$ Ye step kyun? Inode table ek plain array hai: (count) × (ek record ka size).

Step 2 — Bytes ko blocks mein convert karo, upar round karke. $⌈ \frac{2 , 097 , 152}{4096} ⌉ = ⌈ 512.0 ⌉ = 512 blocks per group$ Ye step kyun? Disk whole blocks mein allocate hoti hai, isliye generally tumhe upar round karna hota hai (ceiling) — agar array $2, 097, 200$ bytes hota toh bhi $513$ blocks chahiye honge kyunki leftover bytes ek aur whole block maangti hain. Yahan ye evenly divide ho jaata hai, isliye ceiling aur floor dono $512$ par agree karte hain. $512$ blocks, $2$ bitmap blocks ko dwarf karta hai — inode tables fixed metadata ka bulk hoti hain.

Verify: $512 \times 4096 = 2, 097, 152$ . ✅ Aur $512$ blocks $= 2$ MiB, $128$ MiB group mein se — group ka lagbhag $1.6%$ inode table hai.

Case G — Real-world word problem: inodes khatam hona

Step 1 — Volume par total inodes. $80 groups \times 8192 inodes/group = 655, 360 inodes$ Ye step kyun? Inodes mkfs time pe pre-allocate hote hain — ek fixed pool. Har file ko exactly ek chahiye. Ek baar saare $655, 360$ use ho jaayein, koi nayi file nahi ban sakti chahe free bytes kitne bhi hon.

Step 2 — Space side check karo (upper bound). Worst case lo jahan har file phir bhi ek full $4096$ -byte block occupy kare: $655, 360 \times 4096 = 2, 684, 354, 560 bytes$ Convert karo GiB mein (1 GiB $= 102 4^{3} = 1, 073, 741, 824$ bytes): $\frac{2 , 684 , 354 , 560}{1 , 073 , 741 , 824} = 2.5 GiB$ Ye step kyun? Is worst case mein bhi $10$ GiB mein se sirf $2.5$ GiB touch hota hai — ye confirm karta hai ki do resources decouple ho gaye: files (inodes) apni limit hit kar gayi jabki bytes nahi.

Step 3 — Diagnose karo. df -i $100%$ inodes used dikhaaega; df space free dikhaaega. Fix: files delete karo ya reformat karo zyada inodes ke saath (mkfs.ext4 -N ya -i bytes-per-inode).

Verify: failure count inode pool ke barabar hai: $655, 360 = 80 \times 8192$ , aur worst-case space $655, 360 \times 4096 = 2, 684, 354, 560$ bytes $= 2.5$ GiB exactly. ✅

Case H — Extents vs old block pointers

Figure padhna: top blue bar ek $400$ -block file hai jo contiguously stored hai — ye ek single extent record mein collapse ho jaati hai (start $= 5000$ , length $= 400$ ), right side pe ek arrow se dikhaya gaya hai. Neeche teen bars (green / orange / red) same file hain jo disk par 3 separated runs mein toot gayi hai — ab tumhe 3 extent records chahiye, ek har contiguous run ke liye, phir bhi inode ke 4 inline slots mein fit ho jaate hain. Bottom par gray line yaad dilaati hai ki ext2/3 har block ke liye ek pointer store karta ( $400$ of them) plus ek indirect block ke saath. Pedagogical punch: extent count fragments ki sankhya ke saath badhta hai, blocks ki sankhya ke saath nahi.

Step 1 — Contiguous file. $400$ blocks ka ek run $\Rightarrow$ 1 extent (figure mein top bar). Ye step kyun? Extent ka poora point yehi hai ki contiguity ek (start, length) pair mein collapse ho jaati hai. $400$ blocks, ek record.

Step 2 — 3-piece file. Teen runs $\Rightarrow$ 3 extents, saare inode ke $4$ inline slots mein fit ho jaate hain (B-tree ki zaroorat nahi). Ye step kyun? Ek extent contiguous run ke liye, block ke liye nahi. $3 \leq 4$ , isliye koi external tree nahi.

Step 3 — ext2/3 se contrast karo. Purana scheme har data block ke liye ek 4-byte pointer store karta hai: $400$ pointers. Pehle $12$ direct hain; baaki ( $400 - 12 = 388$ ) ek single indirect block mein rehte hain. Woh indirect block $B /4 = 4096/4 = 1024$ pointers hold karta hai (hum $4$ se divide karte hain kyunki har pointer $4$ bytes ka hai), jo $\geq 388$ hai, isliye ek indirect block kaafi hai. Net: ext2/3 ko metadata ka $1$ extra indirect block chahiye plus $400$ pointer entries — versus ext4 ke $1$ extent record ke. Ye step kyun? Dikhata hai ki extents kyun jeetthe hain: metadata fragments ki sankhya ke saath badhti hai, blocks ki sankhya ke saath nahi.

Verify: contiguous ⇒ $1$ extent; ext2/3 indirect block $4096/4 = 1024$ pointers hold karta hai $\geq 388$ needed, isliye exactly ek indirect block kaafi hai. ✅

Case I — Exam twist: block size badal do

Step 1 — Definition se blocks per group recompute karo. $blocks per group = 8 B = 8 \times 1024 = 8192 blocks$ Ye step kyun? $32768$ kabhi bhi ek constant nahi tha — ye $8 B$ tha, $B = 4096$ par evaluate kiya gaya. Bitmap constraint (ek bit per block, ek bitmap block per group) $B$ ke saath scale karti hai. Number yaad karna formula ki jagah trap hai.

Step 2 — Group size in bytes. $8 B^{2} = 8 \times 102 4^{2} = 8 \times 1, 048, 576 = 8, 388, 608 bytes = 8 MiB$ Ye step kyun? Group size hai (blocks/group) × (bytes/block) $= 8 B \times B = 8 B^{2}$ . $B$ mein quadratic — $B$ ko $4 \times$ shrink karne se group size $16 \times$ shrink hoti hai ( $128 MiB \to 8 MiB$ ).

Verify: $8192 \times 1024 = 8, 388, 608 = 8 MiB$ . Aur 4 KiB case se ratio: $128 MiB /8 MiB = 16 = 4^{2}$ . ✅ Quadratic scaling confirm hua.

Case J — Usable data blocks per group

Ye pehle figure ke right panel mein green data stretch hai — metadata blocks ke baad jo kuch bhi hai.

Step 1 — Har group ke metadata blocks list karo. $sb backup 1 + GDT 1 + block bitmap 1 + inode bitmap 1 + inode table 512 = 516 blocks$ Ye step kyun? Tum sirf "bitmaps" subtract nahi kar sakte — group carry karta hai wo har fixed structure blocks khaata hai. Ek term miss karna usual exam slip hai. (Superblock backup ke bina groups wo 2 blocks bachate hain, lekin worst case quote karna safe hai.)

Step 2 — Group total se subtract karo. $32768 - 516 = 32252 data blocks per group$ Ye step kyun? Data blocks wo sab hain jo saari fixed metadata carved out hone ke baad bachta hai — ye woh number hai jismein ek group actually files store kar sakta hai.

Step 3 — Overhead as a percentage. $\frac{516}{32768} \approx 0.01575 = 1.575 %$ Ye step kyun? Loss ko fraction mein badalna metadata "tax" batata hai. Yahan $2%$ se kam — inode tables ise dominate karti hain.

Verify: $32252 + 516 = 32768$ (har block ka hisaab), aur $32252 \times 4096 = 132, 104, 192$ bytes $\approx 126$ MiB usable data per $128$ MiB group. ✅

Poori chain, ek nazar mein

Self-test

Recall Quick recall

Group of inode 8192 with I=8192 ::: group 0 (group 0 ka last inode, kyunki floor(8191/8192)=0) Blocks per group when B=1024 ::: 8×1024 = 8192 blocks (8 MiB group) Extents for a perfectly contiguous 400-block file ::: exactly 1 extent Why does a 64 MiB disk still get a full bitmap block ::: bitmap ek whole block hoti hai chahe kuch bhi ho; unused bits ko used mark kar diya jaata hai df shows free space but files won't create — cause ::: inode pool exhausted (separate fixed pool); df -i check karo Usable data blocks per group (B=4096, 512-block inode table, 4 other metadata blocks) ::: 32768 − 516 = 32252 data blocks What does $a mod m$ equal precisely ::: $a - m ⌊ a / m ⌋$ , hamesha $0 \dots m - 1$ range mein Why ceiling (not floor) for "how many blocks to store X bytes" ::: koi bhi leftover bytes ek aur whole block maangti hain, isliye upar round karte hain

See also: Bitmaps for allocation · Hard links vs Symbolic links · ext2 vs ext3 vs ext4 · Journaling · Virtual File System · Disk Scheduling · Memory Management · back to Operating Systems.