Allocation methods and free space

matrix.c is 12 KB. Blocks are 4 KB. So it needs 3 blocks.

The inode has to record which 3.

That sounds trivial until the compile finishes and produces matrix at 1.4 MB — 350 blocks. Now the inode has to record 350 block numbers, in order, in a structure that itself has to be small enough to read quickly.

Why & what

Three ways to record where a file's blocks are.

• Contiguous. Store a start block and a length. Two numbers for any file. Reading is as fast as the disk can go, because the blocks are adjacent. The problem is that a file cannot grow into occupied space, and free space fragments exactly as in Topic 6.2. It is the same external fragmentation, on disk instead of in RAM.
• Linked. Each block contains a pointer to the next. Files grow freely and free space never fragments — any block will do. The problem is random access. Reaching block 300 means reading blocks 0 through 299 first, because the only way to find each block is through the previous one. On a spinning disk that is 300 seeks.
• Indexed. One block, the index block, holds the list of all the file's block numbers. Read the index once and you can reach any block directly. Random access is fast and files still grow. The cost is a whole 4 KB block per file, even for a file of 40 bytes.

What a real inode does. It is indexed, but in layers, which fixes the small file cost.

• 12 direct pointers — the first 12 blocks, listed straight in the inode. That covers files up to 48 KB. matrix.c at 3 blocks needs nothing else.
• Single indirect — one pointer to a block full of pointers. With 4 KB blocks and 4-byte pointers, that is 1,024 more blocks, or 4 MB.
• Double indirect — a block of pointers to blocks of pointers. 4 GB.
• Triple indirect — one more layer. 4 TB.

matrix at 350 blocks uses the 12 direct pointers plus 338 entries from a single indirect block. It never touches the double or triple levels.

The design is deliberately unfair, and correctly so: small files pay nothing, and only enormous files pay for the extra reads.

Tracking free space. The OS also has to remember which blocks are unused. The usual answer is a bit vector — one bit per block, 1 for free, 0 for used. A 512 GB disk with 4 KB blocks needs about 16 MB of bits. That is cheap, and finding a run of free blocks becomes a fast scan for consecutive 1s.

How it works

Appending to build.log:

1. The OS finds a free block by scanning the bit vector for a 1.
2. It flips that bit to 0 so nothing else claims the block.
3. It writes the data into the block.
4. It adds the block number to the inode. Direct pointer if there is room, otherwise into the indirect block — allocating that indirect block too if it does not exist yet.
5. It updates the inode's size and timestamp.

Common confusion

"Indexed allocation is strictly better." It costs a full block per file. On a disk with a million small files that is 4 GB spent on index blocks. The layered inode exists precisely because pure indexed allocation is wasteful at the small end.

"Linked allocation is useless." It was used by FAT, and it works well for files that are only ever read start to finish. FAT's improvement was to move all the pointers into one table at the front of the disk, so following the chain does not require reading every data block.

"External fragmentation is a memory problem." It happens anywhere variable sized things are packed into a fixed space. Contiguous file allocation suffers from it for exactly the reasons Topic 6.2 gave, and disk defragmentation is the same compaction idea.

Interview angle

"Compare the three allocation methods." Build the answer around random access and growth: contiguous is fast but cannot grow, linked grows but has no random access, indexed gives both at the cost of an index block.

"How large a file can an inode address?" Walk the four levels with numbers. With 4 KB blocks and 1,024 pointers per block: 48 KB, then 4 MB, then 4 GB, then 4 TB. Being able to derive the 1,024 rather than recite it — block size divided by pointer size — is what makes the answer convincing.