Part 1 of 7 · 2 min read
Why this page comes third
In this module you will
- Compare contiguous, linked, FAT, indexed and extent allocation by speed, waste and flexibility.
- Compute the maximum file size of an inode with direct and indirect pointers.
- Count the disk reads needed to reach a given byte offset of a file.
- Explain external fragmentation, and measure the extents of a file with
filefrag. - Compare a bitmap with a free list, and compute the size of a bitmap.
Page 2 showed the inode, with its list of data blocks. This page asks how that list is built and how the file system finds free blocks to add to it. The choice affects how fast a file is read in order, how fast a byte in the middle is found, and how much space is lost. Level 8 showed that the arm and the page cost of a device make order matter, so the choice here is about locality as much as about bookkeeping.
About this example About this example
Real: The C program in section 4 was compiled with gcc -Wall -Wextra and run on a fresh 64 MiB ext4 image (4 KiB blocks, no journal) on a Linux test machine (kernel 6.18, e2fsprogs 1.47.0). The filefrag figures of 20, 20 and 1 extents are from that run.
Scripted: The pointer counts of 12 direct and one, two and three indirect pointers describe the classic Unix inode, and the maximum sizes are computed. The file sizes and offsets in the examples are made up to show the idea.
Not real: The test file system uses extents, so it never needs the indirect blocks of section 3. The page explains them because many systems and exams use them, and because they show the cost of index structures. The fragmented layout depends on the allocator and may differ on other machines.