Part 7 of 7 · 3 min read
Exercises
Easy
Easy 1: Direct reach (20 minutes)
How many bytes do 12 direct pointers reach with 8 KiB blocks?
Done when: 98,304 bytes (96 KiB).
Hint
12 times 8,192.
Easy 2: Pointers per block (20 minutes)
A block is 4 KiB and a pointer is 4 bytes. How many pointers does an indirect block hold, and how many bytes does a single indirect block add?
Done when: 1,024, and 4 MiB.
Hint
4,096 divided by 4. Then times 4,096.
Easy 3: Blocks of a file (20 minutes)
A file has 100,000 bytes. How many 4 KiB blocks does it need?
Done when: 25.
Hint
divide by 4,096 and round up.
Medium
Medium 1: Reads to a byte (45 minutes)
With the inode in memory, how many disk reads are needed to read a byte at offset 10 MiB, at offset 30 KiB and at offset 3 GiB? Use 4 KiB blocks, 12 direct pointers and 1,024 pointers per indirect block.
Done when: 3 reads (block 2,560 is in the double range), 1 read (block 7 is direct) and 3 reads (block 786,432 is in the double range).
Hint
divide the offset by 4,096 to get the block number. Compare it with 12, 1,036 and 1,049,612.
Medium 2: A FAT (45 minutes)
A disk of 256 GiB uses clusters of 32 KiB and 4-byte FAT entries. How big is the FAT?
Done when: 8,388,608 entries and 32 MiB.
Hint
256 GiB / 32 KiB = 8,388,608 clusters. Times 4 bytes.
Medium 3: Run the experiment (45 minutes)
Compile the program of section 4 and run it in a directory on a mounted ext4 image or disk. Run filefrag on the three files.
Done when: your extent counts, and a sentence about why they differ from mine if they do.
Hint
filefrag -v shows each extent.
Hard
Hard 1: Limits of extents (90 minutes)
An ext4 extent can cover up to 32,768 blocks. With 4 KiB blocks, how many extents does a contiguous file of 10 GiB need at least, and how many extents fit in the inode itself?
Done when: 80 extents, and 4 in the inode, so that a larger count needs a tree of extent blocks.
Hint
10 GiB / (32,768 x 4,096) gives the count. The inode holds a 12-byte header and four 12-byte extents.
Hard 2: Make it worse (90 minutes)
Change the program of section 4 to interleave five files, not two, with 400 blocks each, and run filefrag. Then change it to call posix_fallocate on each file first. Report the extent counts.
Done when: a table of five files with and without fallocate, and a sentence on how the growth pattern changed the count.
Hint
use an array of file descriptors and a loop over blocks.
Hard 3: Compare the methods (90 minutes)
For a file of 1 GiB, with 4 KiB blocks, list how much metadata each method needs: contiguous, linked (in the blocks), FAT (4-byte entries), direct and indirect pointers (4 bytes), and extents (assume 1 extent of 12 bytes if contiguous).
Done when: a table with 8 bytes for contiguous (start and length), 1 MiB for the FAT entries (262,144 x 4 bytes), about 1 MiB for the indirect pointers, about 1 MiB of pointers inside the data blocks for linked, and 12 bytes for one extent.
Hint
1 GiB has 262,144 blocks of 4 KiB.