Filesystem Block Allocation

The File Systems lesson gave you the map — inodes, directories, path resolution. This lesson builds the engine room: how an inode actually points at a file's data on disk, and the elegant trick that lets a fixed-size inode address files from one byte to gigabytes. It's a data-structure problem with a beautiful answer, and it's the design inside ext2/3/4 — the filesystems your Linux machine runs right now.

The problem: fixed inode, variable file

An inode is a small, fixed-size record (the File Systems lesson: type, permissions, size, timestamps, and — the part we tackle now — pointers to the data blocks). But files aren't fixed size: a config file is 200 bytes, a video is 4 GB. How does a fixed record point at a variable amount of data?

The naive answer — "store a list of all the file's block numbers in the inode" — fails immediately: a 4 GB file at 4 KiB blocks is a million block numbers, which won't fit in a small inode. You need a scheme that's cheap for small files (most files are tiny) and scales to huge ones. The classic Unix answer is a multi-level pointer tree, and you'll build its core.

Direct pointers: the fast path for small files

The inode holds a handful of direct pointers — classically 12 — each naming one data block. A file that fits in 12 blocks (48 KiB at 4 KiB blocks) is fully described right in the inode: one disk read gets the inode, and it already knows every data block. Since the overwhelming majority of files are small, this fast path handles most of the filesystem with zero indirection. Design for the common case — the direct pointers are that principle in silicon.

inode
├─ direct[0] → data block
├─ direct[1] → data block
│   … up to direct[11]

The single-indirect block: the scaling trick

When a file outgrows the direct pointers, the inode's single-indirect pointer activates. It points not at data, but at a block full of pointers — an entire disk block used as an array of block numbers. With 4 KiB blocks and 4-byte pointers, that's 4096 / 4 = 1024 more data blocks addressable through one extra level:

inode
├─ direct[0..11]        → 12 data blocks
└─ single_indirect      → [ptr, ptr, ptr, … 1024 of them] → 1024 data blocks

The cost is one extra disk read (fetch the indirect block, then the data) and one extra allocated block (the indirect block is real storage — your exercise counts it in the total). The payoff: 12 + 1024 = 1036 blocks ≈ 4 MB, from a fixed inode. Real filesystems continue the pattern — double-indirect (a block of pointers to blocks of pointers → a million data blocks) and triple-indirect (→ a billion), each level multiplying capacity by block_size/4 at the cost of one more read. That geometric growth is why a 12-direct + 3-indirect-level inode addresses terabytes: small files stay one-read fast, huge files pay a bounded handful of extra reads. Your exercise implements the first two tiers — direct, and the single-indirect that reveals the whole idea.

Allocation is the frame allocator, again

Where do these blocks come from? A free-block bitmap — one bit per disk block, allocate the lowest free one — which is precisely the physical frame allocator you built two chapters ago, applied to disk instead of RAM. The same structure, the same first-fit scan, the same double-free hazard. Filesystems and memory managers are the same problem (hand out fixed-size units from a pool) at different latencies, and recognizing that is a real systems insight: once you've built one bitmap allocator, you've built them all.

Your exercise: Inode Block Allocation

FS block_size n_direct sets the geometry; WRITE bytes reports the blocks a file needs (data blocks via ceil, plus one indirect block only when data exceeds the direct count — counted in the total); CAPACITY reports the max addressable file size. The graded edges are the boundaries: exactly filling the direct blocks (no indirect yet!), one block past (indirect appears, total jumps by 2 — the data block and the indirect block), the block_size/4 pointers-per-block math varying with block size, and the zero-byte file needing zero blocks. It's the arithmetic of the structure that stores every file you own.