Filesystem Block Allocation

The last lesson stopped at the inode number. This one opens the inode: how a file of any size, from 0 bytes to hundreds of kilobytes, finds the disk blocks that hold its bytes. Your program will decode a real 64-byte on-disk inode from hex, follow its direct and indirect pointers, and answer the question every read() asks: which block, and which bytes of it, hold file offsets a to b?

The on-disk inode

xv6's struct dinode is exactly 64 bytes, little-endian:

The first 12 addresses are direct: addrs[i] is the disk block holding bytes i * B to (i + 1) * B - 1 of the file (B is the block size). The 13th points to an indirect block: a block that holds B / 4 more block numbers. A block number of 0 means "no block" because block 0 is the boot block and can never belong to a file. A zero entry in the middle of a file is a hole: the file is sparse, and reading it yields zeros without storing them.

The mapping function: bmap

Given a file's logical block number n (the file offset divided by B):

1. n < 12: the answer is addrs[n].
2. n < 12 + B/4: read the indirect block addrs[12], and the answer is entry n - 12.
3. otherwise the offset is beyond what this inode can address (EFBIG).

For B = 1024 that is 12 + 256 = 268 blocks, a maximum file of 274,432 bytes. Classic xv6 with 512-byte blocks reaches only 140 blocks (71,680 bytes), the limit the exercise generalises. Real systems add more levels: ext2 has a double and a triple indirect block, and ext4 replaces pointer lists with extents (start block plus length), which describe a contiguous run in a few bytes.

From byte range to blocks

A read(offset, length) is turned into one block access per block it touches. Clip the request to the file size. For each logical block n from offset / B to (end - 1) / B, the bytes used are from max(offset, n * B) - n * B to min(end, (n + 1) * B) - n * B (end exclusive) inside that block.

A worked example

Block size 1024 and a file of 3000 bytes whose inode begins 02 00 00 00 00 00 01 00 B8 0B 00 00 ...: type 2, nlink 1, size 0x0BB8 = 3000, and addrs of 28, 29, 30, 0, .... Three blocks are needed (ceil(3000 / 1024)):

Common mistakes

• Treating block 0 as a valid block. It means "hole".
• Off-by-one at the boundaries: offset 1023 is in block 0, offset 1024 in block 1, and the last block of a file whose size is an exact multiple of B is full.
• Forgetting that the indirect block itself uses disk space, so a file with indirect data blocks occupies one more block than its data.
• Reading past the end of the file instead of clipping.

Your exercise

The starter decodes the inode and the blocks. You write bmap, the block count and the byte-range split.