Exercises — ext4 structure — superblock, block groups, inodes

Answer: byte offset 1024. The first 1024 bytes of the whole device are reserved for a boot sector (legacy space where boot code could sit). The filesystem is not allowed to scribble there, so its "ID card" — the superblock — starts immediately after, at byte offset 1024. Offset 0 is off-limits, not filesystem territory.

In order:

1. (optional) Superblock backup + Group Descriptor Table backup — only in some groups.
2. Block bitmap (1 block) — used/free map of this group's blocks.
3. Inode bitmap (1 block) — used/free map of this group's inodes.
4. Inode table — the array of inode records.
5. Data blocks — actual file contents.

Mnemonic order: bits before the things they count — you map free space (bitmaps) before you place records (inode table) and payload (data).

Root is inode 2. Inodes 1–10 are reserved (inode 1 = bad-blocks list, inode 2 = root, inode 11 = lost+found by convention). Hardcoding root = 2 gives path resolution a fixed place to begin.

Blocks per group = bits in one bitmap block = $8B$. $8\times 4096=32768\text{ blocks per group}$ Each block is 4096 bytes, so: $32768\times 4096=134,217,728\text{ bytes}=128\text{ MiB per group}$ ($134,217,728/1024/1024=128$.)

Blocks per group = $8B=8\times 1024=8192$ blocks. Size = $8192\times 1024=8,388,608$ bytes $=8192$ KiB $=8$ MiB per group. Notice: smaller block → smaller group. The bitmap always fits exactly one block, so shrinking $B$ shrinks both the bit-count and the block-size, and group size scales as $8B^2$ bytes.

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

Inode numbers are 1-based, array indices are 0-based, so subtract 1 first. $\text{group}=\lfloor \frac{50000-1}{8192}\rfloor =\lfloor \frac{49999}{8192}\rfloor =\lfloor 6.103\dots \rfloor =6$ Index within that group: $(50000-1)\mathrm{mod}8192=49999-6\times 8192=49999-49152=847$ Group 6, index 847.

Correct: $\lfloor (8193-1)/8192\rfloor =\lfloor 8192/8192\rfloor =\lfloor 1.0\rfloor =1$. Inode 8193 is the first inode of group 1 — index $(8193-1)\mathrm{mod}8192=0$. ✓ Wrong (no −1): $\lfloor 8193/8192\rfloor =\lfloor 1.000\dots \rfloor =1$ — coincidentally right here. Now try inode 8192 (last of group 0): correct $\lfloor 8191/8192\rfloor =0$ ✓; wrong $\lfloor 8192/8192\rfloor =1$ ✗ — off by one group exactly at the boundary. That is where the bug hides.

Bytes of inode table per group: $8192\times 256=2,097,152\text{ bytes}$ In 4096-byte blocks: $\frac{2,097,152}{4096}=512\text{ blocks per group}$ So 512 of a group's 32768 blocks are pre-spent on inode records — before any file data exists.

(a) $100\text{ KiB}=102400$ bytes. $\lceil 102400/4096\rceil =\lceil 25.0\rceil =25$ blocks (it divides evenly: $25\times 4096=102400$). (b) One extent = "logical blocks $\mathrm{0..24}$ → physical blocks $p..p+24$", so 1 extent if fully contiguous. (c) Old ext2/3 would need ~25 individual block pointers (and an indirect block once you exceed the 12 direct slots). Extents replace all of that with one record → smaller inode footprint, fewer reads to map the file. This is the ext4 improvement.

It can start because root is a fixed inode: inode 2.

1. Read inode 2 (/) → its data block is a directory listing → find entry home → gives home's inode #.
2. Read home's inode → its data → find ada → gives ada's inode #.
3. Read ada's inode → its data → find x.txt → gives the file's inode #.
4. Read the file's inode → its extents → physical data blocks → the bytes.

Pattern: inode → data (directory) → name lookup → next inode, repeated per path component, then one final inode → extents → data. Each / in the path = one such hop. This is the mechanism Virtual File System exposes uniformly across filesystems.

Inodes are a separate, fixed pool allocated at mkfs time (see L3.3 — the table is pre-sized). Millions of tiny/empty files can exhaust inodes while data blocks remain free. df shows block usage; the inode pool is invisible to it. Confirm with: df -i If the IUse% column reads 100%, the pool is exhausted — no bytes will help; you'd need to delete files or reformat with more inodes.

Chain of constraints:

• One block = $B$ bytes = $8B$ bits (8 bits per byte).
• The block bitmap is one block, so it has $8B$ bits, and one bit ↔ one block. Therefore blocks per group $=8B$.
• Each block is $B$ bytes, so group size $=(8B)\times B=8B^2$ bytes. ∎

For $B=4096$: $8\times 4096^2=8\times 16,777,216=134,217,728$ bytes. $134,217,728/1024^2=128$ MiB. ✓ Key insight: the single choice of $B$ fixes the entire geometry — bitmap-fits-one-block is the master constraint.

Groups: $10\times 1024\text{ MiB}/128\text{ MiB}=80$ groups. Total inodes $=80\times 8192=655,360$ inodes. df -i total ≈ 655,360 (minus reserved inodes 1–10 shown as used). So this disk can hold at most ~655k files no matter how tiny — a hard ceiling set at format time.

A group carrying a backup spends extra blocks on: 1 superblock copy + the Group Descriptor Table copy. Those blocks are unavailable for file data, so a backup-bearing group has a slightly smaller data region than a plain group. ext4 (with the sparse_super feature) places backups only in groups numbered $0,1$, and powers of $3,5,7$ (e.g. group 3, 9, 25, 49...). Why not all? A backup in every group wastes a lot of space on redundancy that is only needed once for recovery. A handful of well-spread copies is enough for fsck to rebuild — this is the classic redundancy-vs-overhead trade, the same spirit as Journaling (protect just enough metadata, not everything twice).

Blocks per group formula? ::: $8B$ (bits in one bitmap block, $B$ = block size in bytes). Group of inode $N$ with $I$ per group? ::: $\lfloor (N-1)/I\rfloor$ — subtract 1 for 1-based numbering. Which gauge shows inode exhaustion? ::: df -i, not df.