CSE Roadmap

Core tier · about 3 hours · 7 parts

Part 7 of 7 · 3 min read

Exercises

Easy

Easy 1: Inodes per block (20 minutes)

How many inodes of 256 bytes fit in a block of 4 KiB, and how many blocks does a table of 8,192 inodes fill?

Done when: 16, and 512 blocks.

Hint

4,096 divided by 256, then 8,192 divided by that.

Easy 2: Table size (20 minutes)

A file system has 4,096 inodes of 256 bytes. How many bytes and how many 4 KiB blocks does its inode table need?

Done when: 1,048,576 bytes and 256 blocks.

Hint

multiply, then divide by 4,096.

Easy 3: Where is inode 100 (20 minutes)

The table starts at block 35. Find the block and the offset of inode 100.

Done when: block 41 and offset 768.

Hint

block = 35 + 99 / 16 (whole division). Offset = (99 mod 16) x 256.

Medium

Medium 1: Another inode (45 minutes)

Find the block and the offset of inode 2,000, with the table at block 35.

Done when: block 159 and offset 3,840.

Hint

use inode number minus one before dividing.

Medium 2: Count the blocks (45 minutes)

A file has 20,000 bytes. How many 4 KiB blocks does it need, how many bytes are wasted at the end, and what Blockcount (512-byte units) does debugfs print?

Done when: 5 blocks, 480 bytes wasted, and 40 units.

Hint

20,000 / 4,096 = 4.88, so 5 blocks of 4,096 = 20,480 bytes. Units of 512: 5 x 8.

Medium 3: Make your own image (45 minutes)

Make a 16 MiB image with mkfs.ext4 -F -b 4096 -O ^has_journal, mount it through a loop device, create three files of different sizes, unmount and run dumpe2fs and debugfs -R "stat <inode>". Compile the program of section 3 and run it on your image.

Done when: the program's size and link values match debugfs for two inodes, with the output shown.

Hint

on the image, debugfs -R "ls -l /" lists the inode numbers.

Hard

Hard 1: Read the root directory (90 minutes)

Extend the program to read the root inode's first extent (the i_block field at byte 40 of the inode holds an extent header of 12 bytes and then one extent of 12 bytes whose start is in the last 6 bytes) and print each entry of the root directory block: inode number, record length, name length and name.

Done when: the entries ., .., lost+found and your files appear with the inode numbers that ls -i shows.

Hint

the extent's start block is the 32-bit value at byte 8 of the extent (inode byte 60), with the high 16 bits at byte 6.

Hard 2: Run out of inodes (90 minutes)

Make a 16 MiB file system with -N 128, mount it, and create empty files until creation fails. Report the number created, the error, df -i and df.

Done when: 117 files (or a count that you explain if your tools differ), the error ENOSPC, inode use at 100% and block use near 1%.

Hint

mkfs.ext4 -F -N 128 image. Use touch f$n in a loop until it fails.

Hard 3: Size a big disk (90 minutes)

A 4 TiB disk uses 4 KiB blocks and one inode for every 16 KiB. Find the number of block groups, the number of inodes, and the space used by the inode tables at 256 bytes each.

Done when: 32,768 groups, 268,435,456 inodes and 64 GiB (1.6% of the disk).

Hint

groups = 4 TiB / 128 MiB. Inodes = 4 TiB / 16 KiB.